Integer storage & overflow using Haskell

I was curious to see how integer overflow, truncation and type conversion behavior manifested itself in Haskell programs. I also wanted to see what type of warnings were produced and what was allowed or not. Whether it was possible to to detect it. Yes, these are the type of things I think about.

The reference I always go back to when auditing C code for these issues, is Mark Dowd's The Art of Software Security Assessments, specifically chapter 6. Take a look at http://pentest.cryptocity.net/code-audits/. While you're there that whole website is full of great material from a number of excellent courses.

So, let's take a look at the following haskell integer datatypes.

Word(x):  Unsigned integer, bounded

Int(x): Signed integer, bounded.

Integer: Signed integer, unbounded.

(x) refers to size specifiers for Word and Int size (8/16/32/64)

The system used was:

Linux ubuntu 3.2.0-29-generic #46-Ubuntu SMP Fri Jul 27 17:03:23 UTC 2012 x86_64 x86_64 x86_64

GHCi, version 7.4.1

We will look at a few examples in the following areas:

- Basic Representation
- Truncation
- Arithmetic Overflow
- Basic Type Conversion
- Type Conversions in Operations
- Rotate signed extensions

Focusing primarily on the Int and Word types, as Integer is supposed to be signed and unbounded.

Basic Representation

Beginning with a few basic assignments 

Prelude Data.Word Data.Int> 1000 :: Int16 

1000
Prelude Data.Word Data.Int> 1000 :: Word16
1000
Prelude Data.Word Data.Int> -1000 :: Int16
1000

(which is 1111101000)

Consider the Unsigned Word8 type with a range of [0,255]

Prelude Data.Word Data.Int> let a=254::Word8

Prelude Data.Word Data.Int> a

254

Prelude Data.Word Data.Int> let a=256::Word8

Prelude Data.Word Data.Int> a

0

Prelude Data.Word Data.Int> let a=257::Word8

Prelude Data.Word Data.Int> a

1

One interesting thing is the interpreter doesn't complain about assigning a negative number to a unsigned type. 

Prelude Data.Word Data.Int> let a = -100 :: Word8

Prelude Data.Word Data.Int> :t a

a :: Word8

Prelude Data.Word Data.Int> a

156

Where does the 156 come from? Well the 2's complete representation of -100 is 10011100 which when treated as unsigned binary number is 156. (http://en.wikipedia.org/wiki/Two's_complement)

Now I looked for a means to detect if a overflow or out-of-range assignment had occurred but I could not find a mechanism in the exception handling or other documents. One reference stated that overflows are considered programmer errors and are up to the programmer to detect/correct (http://www.haskell.org/haskellwiki/Error_vs._Exception). If there is a mechanism please do let me know. 

Or something like some of the C techniques to programmatically check. 

Truncation

Next the signed Int8 type with a range of [-128 127] is assigned a value which is too large. 

Prelude Data.Word Data.Int> 1000 :: Int8 

232
1111101000
11101000 = 232

The value is simply truncated to the lower 8 bits and displayed

Prelude Data.Word Data.Int> 1000 :: Int8 

-24
1111101000
11101000 (Treated as Two's Complement) = -24

In this case the value is truncated to the lower 8 bits and rendered as a two's complement.

Arithmetic Overflow

Now for a simple case integer addition overflow.

Prelude Data.Word Data.Int> let b = 1 :: Int8

Prelude Data.Word Data.Int> let c = 127 :: Int8

Prelude Data.Word Data.Int> let d = b + c

Prelude Data.Word Data.Int> d

-128

Prelude Data.Word Data.Int> :t d

d :: Int8

What I found interesting is that the Int8 type was propagated to the result regardless of the overflow. 

Prelude Data.Word Data.Int> let a= -128 :: Int8

Prelude Data.Word Data.Int> let b= -1 :: Int8

Prelude Data.Word Data.Int> let c = a + b

Prelude Data.Word Data.Int> :t c

c :: Int8

Prelude Data.Word Data.Int> c

127

And now with Word8 [0 255], we see the type is propagated and the value wraps.  

Prelude Data.Word Data.Int> let a = 5 :: Word8

Prelude Data.Word Data.Int> let b = 255 :: Word8

Prelude Data.Word Data.Int> let c = a + b

Prelude Data.Word Data.Int> c

4

Prelude Data.Word Data.Int> :t c

c :: Word8

In a later post will take a look at sign extensions in shift / rotations, type conversions (with to/fromIntegral) and greater examination of the Integer type.