[Cryptography] bounded pointers in C

[Ben Laurie]

On 18 April 2014 01:46, John Gilmore <gnu at toad.com> wrote:
>> Well first of all, strings and arrays. I don't want a bounds-unchecked
>> string or array, not ever - even if bounds checking is
>> resource-consuming and there is no possibility of out-of-range inputs,
>> someone else might come along later and change the code.
>>
>> I don't want to have to even think about whether a string or array is
>> bounds checked; just whether the default behaviour when an out-of-range
>> input is detected is suitable.
>>
>> So, where would you change it? K+R? ANSI? I don't know, but in 35 years
>> they never got around to fixing it.
>
> This is fixed in ANSI C.  The language definition does not require
> implementations to check pointer or array bounds -- but everything in
> the language that prevented implementations from doing it was removed.
> Accessing outside the legitimate boundaries of the object is
> "undefined" in the language, and the compiler can do what it wants
> when that happens, including make the program die instantly.
>
> We have had many such implementations over the years -- but none of
> them have become popular, or even standard.
>
> A "bounded pointers" implementation of gcc was built in the late
> 1990s-2000 by Greg McGary (see
> http://gcc.gnu.org/ml/gcc/2000-04/msg00137.html).  It worked well
> enough to compile and run GNU libc and the GNU textutils and
> fileutils.  This was some sort of official GCC project, even.  But
> apparently it was never adopted into mainline gcc -- I don't know why
> not.  See https://sourceware.org/ml/libc-alpha/2012-01/msg00131.html ,
> http://gcc.gnu.org/ml/gcc/2001-02/msg00583.html ,
> http://gcc.gnu.org/ml/gcc/2001-02/msg00278.html
> He seems to be greg at mcgary.org and was contributing to GCC mailing
> lists as late as 2009.  Apparently the code lived on a branch
> of the GCC source tree ("bounded-pointers-branch") so that branch
> may still be accessible somewhere.  Indeed, doing this command:
>
>   svn co svn://gcc.gnu.org/svn/gcc/branches/bounded-pointers-branch
>
> seems to have brought me some code, which might be Gary's latest code,
> or might not be.  The last changes in it seem to be from about 2000,
> according to the ChangeLog.  But I can't get it to build -- the
> configuration files seem messed up.

Hmm. Any info on how this works (or worked)? All bounded pointers
implementations I've seen have required some kind of code annotation
to make them work properly (e.g. explicit fat pointers). Can it really
be done without source modification?

Our research CPU, CHERI
(https://www.cl.cam.ac.uk/research/security/ctsrd/cheri.html) makes
bounded (and permissioned) pointers a first-class part of the CPU - we
have a version of LLVM that uses annotations to generate assembler
that takes advantage of these pointers.

> Others built similar but less straightforward bounds checkers, like
> "Mudflap" (http://gcc.fyxm.net/summit/2003/mudflap.pdf), but
> apparently that isn't popular, standard, or available in any public
> GCC release either.
>
> And many other C environments, such as "Saber C" and "Purify" have
> done similar checks.  It isn't rocket science.  It works.
>
> Actually building and maintaining C implementations that check pointer
> boundaries seems to require a level of intense desire that so far
> *nobody* has created or sustained for more than a year or two.
>
>         John
>
>
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography