Ticket #2120 (new bug)

Opened 1 year ago

Last modified 1 week ago

Arrays allow out-of-bounds indexes

Reported by: amthrax Assigned to:
Priority: high Milestone: 6.12.1
Component: libraries (other) Version: 6.8.2
Severity: normal Keywords:
Cc: alexander.dunlap@gmail.com, ghc@henning-thielemann.de Difficulty: Unknown
Test Case: Operating System: Unknown/Multiple
Architecture: Unknown/Multiple

Description

The array changes proposed and recently implemented for ticket #1610 (Make arrays safer) strengthened the requirements on Ix instances, but weakened the requirements on array users. Specifically, array referencing now permits indexes that are not inRange.

For example, 

import Data.Array.IArray

b :: Array (Int,Int) Int
b = listArray ((0,0), (3,3)) (repeat 0)

main = do
  print (b ! (0,5))              -- SHOULD fail, but doesn't
  print (index (bounds b) (0,5)) -- DOES fail

The first line in main should fail because the specified index is not inRange, but doesn't because the (!) operator (specifically Data.Array.Base.safeIndex) now uses unsafeIndex and simply checks that the resulting index is within the linearized bounds of the array. In this case, the unsafe index of (0,5) wraps aroung to the index of (1,1).

A simple fix would be to use index instead of unsafeIndex in the implementation of Data.Array.Base.safeIndex. This would both require the user to use in-bounds references and would require Ix instances to return in-bounds indexes.

Change History

03/14/08 13:36:27 changed by igloo

  • difficulty set to Unknown.

When fixing #1046 and #1610, some people were worried about the performance overhead of checking both that the index was within the range (in terms of the Ix class), and also that we were looking for a value within the real range (i.e. offset in [0..rangeSize)).

We used to do just the first check, which meant that you could access memory that you shouldn't with a funky Ix instance. Now we do just the second check, meaning if you ask for an out-of-range index then you might successfully get a value back.

Would you like to make a proposal for doing both checks?

03/14/08 13:37:56 changed by igloo

See also: http://www.haskell.org/pipermail/haskell-cafe/2008-March/040598.html

03/30/08 07:41:52 changed by igloo

  • milestone set to Not GHC.

04/13/08 18:57:29 changed by ajd

  • cc set to alexander.dunlap@gmail.com.

09/30/08 08:45:17 changed by simonmar

  • architecture changed from Multiple to Unknown/Multiple.

09/30/08 08:54:54 changed by simonmar

  • os changed from Multiple to Unknown/Multiple.

11/01/08 12:48:52 changed by guest

  • cc changed from alexander.dunlap@gmail.com to alexander.dunlap@gmail.com, ghc@henning-thielemann.de.

This is not my Haskell! Checks must be done completely by default. It should be possible however to turn them off by a compiler switch.

11/18/08 06:00:08 changed by simonmar

  • milestone changed from Not GHC to 6.12 branch.

It's not always necessary to do both checks, for example it suffices to do the second check for ordinary one-dimensional integral indices. So perhaps the cost of doing this properly won't be so bad.

Moving this to the 6.12 milestone - it was the GHC project that broke it, so we should fix it again :-)

04/10/09 12:12:15 changed by igloo

  • milestone changed from 6.12 branch to 6.12.1.

04/13/09 10:01:34 changed by igloo

See also #2669.

06/25/09 01:55:54 changed by simonpj

Triggered by this thread http://www.haskell.org/pipermail/haskell-cafe/2009-June/063399.html, I had quick look.

There are two range tests under discussion

  • One tests every index supplied by the client of the array, against the original bounds. We should never leave this test out.
  • The other tests the Int offset computed by index, in case the Ix instance for this type is bogus. We can omit this check iff we trust the instance.

The only safe thing to do (and Haskell is supposed to be a safe language) is to do both checks, thus (in GHC.Arr): 

safeIndex :: Ix i => (i, i) -> Int -> i -> Int
safeIndex (l,u) n i = let i' = index (l,u) i
                      in if (0 <= i') && (i' < n)
                         then i'
                         else error "Error in array index"

(Note the use of index rather than unsafeIndex.) To avoid the double test in the (wildly common) cases of indexing using the (trusted) built-in instances for Int, (Int,Int) etc, we could use a RULE to call version of safeIndex that did only one test.

Furthermore, we should improve the "Error in array index" error message. If we have the first client-oriented test in place, then this second error can read something like "The index method for an Ix instance returned offset N, but the array has size M". I don't see how to say which type, sadly. Typeable is not a superclass of Ix.

Simon

06/25/09 01:57:33 changed by simonpj

  • priority changed from normal to high.

I'll change this to high priority to make sure we get to it for 6.12. Simon