[Haskell-cafe] The Data.Array.* hierarchy is unsafe (or, Segfaulting for fun and profit)

[Spencer Janssen]

I've discovered a problem in the array libraries that allows one to  
read arbitrary memory locations without the use of any unsafeFoo  
functions.  Both GHC and Hugs are affected.

 > import Data.Array.IArray
 > import Data.Array.Unboxed

Here is a poorly behaved instance of Ix: inRange and index ignore the  
bounds supplied.

 > newtype EvilIx = E Int deriving (Eq, Ord)
 > instance Ix EvilIx where
 >    inRange _ _ = True
 >    index _ (E i) = i
 >    range (E x, E y) = map E $ range (x, y)

One can read arbitrary memory locations, eventually indexing far  
enough to cause a segmentation fault.

 > main = print [a ! E (2^i) | i <- [0..]]
 >  where
 >    a :: UArray EvilIx Int
 >    a = array (E 0, E 0) []

This problem is not specific to UArrays:

 > main' = print [a ! E (2^i) | i <- [0..]]
 >  where
 >    a :: Array EvilIx String
 >    a = array (E 0, E 0) []

The issue is that the array operators trust the Ix instance to manage  
boundaries correctly.  The solution is to double check the value  
returned by index with the actual length of the array.

I volunteer to write the fix, if I can extract some hints from more  
knowledgeable folk.  There's sizeOfByteArray#, is there an analog for  
an Array#?  I need to know how to find the length of Hugs array  
primitives too.


Cheers,
Spencer Janssen