From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,8a4455177648cb9e
X-Google-Attributes: gid103376,public
From: Robert A Duff <bobduff@world.std.com>
Subject: Re: Idea: Array Boundary Checks on Write Access Only
Date: 1998/06/17
Message-ID: <wccd8c7px1j.fsf@world.std.com>#1/1
X-Deja-AN: 363637711
Sender: bobduff@world.std.com (Robert A Duff)
References: <35851B64.5BF271C4@cl.cam.ac.uk> <ug1h4ylhp.fsf@gsfc.nasa.gov>
 <35880D14.AC0243A@cl.cam.ac.uk>
Organization: The World Public Access UNIX, Brookline, MA
Newsgroups: comp.lang.ada
Date: 1998-06-17T00:00:00+00:00
List-Id: <comp.lang.ada>


Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk> writes:

> An array read bug has only local consequences, a wrong return
> result (unless the result is an erroneous pointer). An array or
> pointer write bug can cause erroneous behaviour in other completely
> indepentent classes even if the implementation of these is carefully
> scrutinized to be bug free and very carefully shielded against
> wrong parameters.

But integers behave just like pointers, when used as array indices:

    type Int_1_10 is range 1..10;
    type A is array(Int_1_10) of Boolean;
    A_Obj: A;
    
    type B is array(Integer range 1..3) of Int_1_10;
    B_Obj: B := (others => 1);
    
    ... -- lots of code that might change B_Obj, but it's all properly
        -- range-checked, so we know B_Obj(I) is in 1..10, for all I.

Then:
    X: Integer := 1_000_000;
    ... -- might change X
    Y: Int_1_10 := B_Obj(X);
    A_Obj(Y) := True;

With checks turned on, there will be a check on B_Obj(X), to make sure X
is in 1..3.  A good compiler will notice that the result of B_Obj(X)
must be in 1..10, so no check is needed on the assignment to Y, and
likewise no check is needed on A_Obj(Y), since Y must be in 1..10.  But
if we eliminate the check on B_Obj(X), which is a *read*, we end up
doing an evil *write*.  The assignment to A_Obj(Y) will modify some
random bit in memory -- who knows where.

So "reads" aren't so harmless after all.

On the other hand, if we make a rule that the elimination of the first
check must cause the re-insertion of the second check, then it's not
clear what efficiency we've gained.

> There are no bug free systems but in many types of systems, some
> modules (e.g., an encryption module that must not leak secret
> keys) must be especially carefully reviewed, while the huge majority
> of the system is much less critical. This some-modules-only
> review makes only sense if there is a guarantee that no other
> less pedantically reviewed code (user interface, etc.) can
> accidentially or maliciously be caused to overwrite the internal data
> structures of the critical module.

It seems to me that you can't know that, unless the two modules are in
separate address spaces with hardware memory protection preventing
inter-module naughtiness.  No matter how carefully you review module A,
someone can break it accidentally or maliciously in a totally-unrelated
module B, by using any number of unsafe features (such as unchecked
conversion of pointers, machine code insertions, address clauses, &c).
Assuming A and B share the same address space, that is.

- Bob

-- 
Change robert to bob to get my real email address.  Sorry.
-- 
Change robert to bob to get my real email address.  Sorry.