The Data.Array.* hierarchy is unsafe (or, Segfaulting for fun and profit)

[Simon Marlow]

Spencer Janssen wrote:
> 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.

See Chapter 15 of the Haskell Report, in particular the paragraph

  An implementation is entitlesd to assume the following laws about these
  operations:

   range (l,u) !! index (l,u) i == i -- when i is in scope
   inRange (l,u) i == i `elem` range (l,u)
   map index (range (l,u)) == [0..rangeSize (l,u)]

Your inRange operation doesn't satisfy the second law.

You might well argue that having this assumption is undesirable (and I'd 
probably agree), but haskell-prime at haskell.org is probably a better place to 
start that discussion.

Cheers,
	Simon