by As we all should know already, memory is not an infinite resource despite looking like it. Given our current scenario where hardware is relatively cheap, when writing programs with high-level languages such as JavaScript or Python, we don’t have to worry about allocating resources for variables and we usually do not have to think about how big can that number get during our program execution because the underlying engine is smart enough to optimize the resources for the requested operations. The following article will explore one of the problems we can face when dealing with manual memory allocation: overflow and underflow.
Binary operations
First of all, what is overflow? As the name suggests, when you keep filling a bucket, it will eventually spill the excess. In other words, reserved memory space can only store the exact amount it was designed to store. Underflow is quite the opposite. It would be like you keep removing the content from that bucket and all of sudden it’s full again.
Let’s do an exercise first. For the moment, consider we only work with unsigned integers (integers greater than or equal to zero):
Imagine we have a space that can hold only 4 bits:
Starts from 0000, and goes up to 1111.
With this reserved space, we can count from 0 to 15. If we sum 1 to 15, we would have to allocate one more bit. So, assume we have a variable a pointing to this address of 4 bits, and we increment it by one.
- 1111 + 0001 = 1 0000
The variable a, can only see the 4 bits from the right. The 5th does not even need to exist physically. The result we achieve, then, shows variable a, holding the value of zero instead of sixteen (in decimal). The most significant bit is thrown away because it does not have enough memory space to be stored.
Alright, let’s assume we can use more space. 8 bits instead of 4.
- 0000 1111 + 0000 0001 = 0001 0000
Perfect. Allocating more memory to this data will now postpone our overflow problem to 1111 1111 (255 decimal).
What about the underflow? Instead of throwing one bit away, the behavior is to lend one bit from nowhere to make the subtraction work.
Assuming we allocated 4 bits as:
- 0001 (1 decimal)
And we subtracted twice the amount of 1:
- 0001 – 0001 = 0000
- 0000 – 0001 = (1) 0000 – 0001 = 1111.
So, subtracting 1 from 0, using 4 bits, results in 15 decimal.
The same logic can be applied to any memory space amount you can imagine.
Two’s Complement
Now that we have already revisited the binary math with limited bit space, it’s worth bringing up the Two’s Complement concept. This is used to represent signed numbers other than the unsigned ones we represented so far. Under and overflow can still happen but this time instead of hitting the maximum or minimum value for that memory space, the number will be negative.
Quickly explaining how Two’s Complement work, with 8 bits:
- unsigned integer: 1111 1111 (255)
- signed integer: 1111 1111 (-1)
Two’s complement uses the first bit to indicate the sign, being that the most negative number. Naturally, losing that first bit limits the count from -128 to 127 dec.
So:
- 1111 1111 -> (1000 0000) + (0111 1111) -> -128 + 127 = -1
Thus if we have an 8 bit variable that holds a value of 120 (0111 1000), and we increment it by 8 (0000 1000), we obtain (1000 000) despite all bits being successfully written in the available memory space, one bit was written at the most significant bit that represents the sign. 120 + 8 = -128.
After explaining how it works, we can better understand some interesting bugs that happen. For this article, I brought examples of classic games that used very limited hardware at the time of their development.
The Pac-Man case:
The game is really simple. Eating little dots on the screen while running away from colorful ghosts. Sometimes you grab a power-up and then you can chase the ghosts. After finishing eating all dots on the screen, the player is promoted to the next level with increased difficulty. The game goes as described until the player loses all of his "lives", forcing them to buy another coin to insert in the arcade and keep playing. But what if the player keeps winning and never dies?
The original logic was really simple and didn’t predict players going beyond level 255. When hitting level 255, the screen got messy, random drawings appeared on screen and the game became unplayable. This bug gives us a hint that something may have overflowed; something that held only 8 bits.
Image obtained as a screenshot from the video [2] that explains the bug in detail.
I am not going to replicate the awesome explanation on the referred video [2] gave, so I suggest the reader to watch it later if you are interested.
The TLDR of the bug is that each level had a set of fruits that represented the number of the level. The set could hold from 1 to 7 fruits, drawn from a list of 20 icons. The address that holds the level, as we can imagine, started as 0000 0000, and to draw the level, the formula was to add 1; the value zero recorded on memory means level 1. Following this logic to the value 1111 1111 recorded as the current level, the game then asks to draw the fruit on the screen. Adding 1 to the current level would say that the player is on level zero. There we have it, the overflow.
The instructions to iterate the fruit drawings stored on the game’s memory would lose the bounds and start drawing everything that was on the near memory addresses 255 times.
Chrono Trigger:
This well-known RPG has a bug in its Nintendo DS version. The Dream Devourer [3] boss, which has 32000 health points, stored in 16 bits. At this point, we may tell that the maximum number this variable can hold is 1111 1111 1111 1111. In an unsigned integer usage, that can represent 65.536. In this game’s case, this memory space holds a signed integer, that holds from -32768 to 32767 dec. As seen in how signed numbers are read by the computer, the overflow may now appear as a possible exploit. Dream Devourer with its 32000 HP (0111 1101 0000 0000) can be healed to achieve negative HP. Increasing the monster’s health by 767 (0000 0010 1111 1111) will make the computer interpret the health status as -1, so it should be dead.
That’s it. I’ve left some more links in the references for those whoever is curious about more bugs that people found across the years [4]. You can search on the internet and you’ll find many calculators/converters from dec to bin/bin to dec so you can better understand how it works. There are also related topics that involve overflow but with a buffer. Those allow you to read or write memory space that you are not allowed to.
References:
[1] Integer overflow and underflow: https://youtu.be/JNu_9U4qq8E
[2] Pac-man Kill Screen explained: https://youtu.be/NKKfW8X9uYk
[3] Dream Devourer: https://chrono.fandom.com/wiki/Dream_Devourer
[4] Integer overflow in an RPG: https://www.reddit.com/r/programming/comments/1aigv9/integer_overflow_in_an_rpg_defeat_a_boss_by
[5] List of Glitches – Pokemon Red and Blue: https://bulbapedia.bulbagarden.net/wiki/List_ofglitches(Generation_I)#Red_and_Blue
[6] From Missingno to Heartbleed: Buffer Exploits and Buffer Overflows: https://youtu.be/rE5dW3BTpn4
We want to work with you. Check out our "What We Do" section!
