Handling Integer Overflow in Swift

Photo by Zac Harris on Unsplash

Sometimes we can get complacent and take things for granted when we are developing are app. I bet you rarely give Swift’s Integer type much consideration. It just works as you expect until that time. Well this most innocuous and uncomplicated type can actually be the cause of a major problem in your application — Integer Overflow.

MITRE’s Common Weekness Enumeration, a community-develooped list of software and hardware weakness types describes an integer overflow as follows:

An integer overflow or wraparound when an integer value is incremented to a value that is too large to store in the associated representation. When this occurs, the value may wrap to become a very small or negative number. While this may be intended behavior in circumstances that rely on wrapping, it can have security consequences if the wrap is unexpected. This is especially the case if the integer overflow can be triggered using user-supplied inputs. This becomes security-critical when the result is used to control looping, make a security decision, or determine the offset or size in behaviors such as memory allocation, copying, concatenation, etc.

Integer Types and Bounds

Swift provides signed and unsigned integers in 8, 16, 32, and 64 bit forms. These integers follow a naming convention similar to C, in that an 8-bit unsigned integer is of type UInt8, and a 32-bit signed integer is of type Int32. Like all types in Swift, these integer types have capitalized names.

Here is a quick list of the various Integer types and the minimum and maximum values they can hold:

The problem of integer overflow boils down to what happens if you take the biggest integer value a UInt64 can hold 18,446,744,073,709,551,615 (which coincidentally also happens to be Mark Zuckerberg’s bank account balance) and add 1 to it? CRASH!!!!!!

An Example demonstrating the problem

Below is a function in Swift that will generate all the numbers in the Fibonacci Sequence up to the upperBound.

If you run this little program, you will print the first 93 numbers of the Fibonacci Sequence and then a crash will occur with the error message error: Execution was interrupted, reason: EXC_BAD_INSTRUCTION (code=EXC_I386_INVOP, subcode=0x0).

The algorithm is generating some big numbers …

fib(87) : 679891637638612258
fib(88) : 1100087778366101931
fib(89) : 1779979416004714189
fib(90) : 2880067194370816120
fib(91) : 4660046610375530309
fib(92) : 7540113804746346429
fib(93) : 12200160415121876738

The Solution

When I ran into this problem recently, my first thought was to investigate whether Swift had a BigInt type like both Java and Javascript. Unfortunately, as of June of 2021, BigInt has not made it into Swift’s standard library. So how do we solve the Integer Overflow problem in Swift for those times when 64 bits isn’t big enough to hold the value you wish to store? The answer is to store each of the two numbers in a String and use our grade school addition algorithm to add the digits one by one. Then, using this algorithm to do the fibonacci add.

The string addition algortithm looks like :

Note that this is also a LeetCode question https://leetcode.com/problems/add-strings/

Now that we figured out the basic algorithm for addition, we can build a custom BigInt type.

And use the new BigInt type to refactor our Fibonacci applicaiton.

Running again handles 100 Fibonacci numbers with no problem.

fib(84) : 160500643816367088
fib(85) : 259695496911122585
fib(86) : 420196140727489673
fib(87) : 679891637638612258
fib(88) : 1100087778366101931
fib(89) : 1779979416004714189
fib(90) : 2880067194370816120
fib(91) : 4660046610375530309
fib(92) : 7540113804746346429
fib(93) : 12200160415121876738
fib(94) : 19740274219868223167
fib(95) : 31940434634990099905
fib(96) : 51680708854858323072
fib(97) : 83621143489848422977
fib(98) : 135301852344706746049
fib(99) : 218922995834555169026
fib(100) : 354224848179261915075

Of course, we could have used the implementation of BigInt Apple has provided in the Apple GitHub repo, but that wouldn’t have made for nearly as good an article.

We have looked at how we can identify and solve the integer overflow problem in Swift. This is a situation that can easily be encountered in practice and I hope next time you are doing some mathematical operations in your application this article will have provided some food for thought.

Keep coding my friends.