Welcome > Memory Safety > Secure Memory by using Metadata for Pointers > Runtime Bound Checking > Jones Kelly

Jones Kelly

Reference¹

Earlier work:

earlier work

In this work,

pointer representations are not changed.
A table of all known valid storage objects:
- mapping a pointer to an object descriptor;
- the descriptor contains the base, extent and additional information of the object.
All pointer arithmetic and pointer use are checked.
- arithmetic result must refer to the same object;
- every pointer-valued expression must derive its result from one original object.
- Incorrectly derived pointers are replaced with an illegal pointer value ((void *)-2).

Example: pointers to objects.

objects in memory

Permitted operations for pointers above:

objects in memory

Object/pinter tracking: track object when created/deleted:

static: global variables, static variables in functions, and string constants: compiler/linker change.
dynamic: malloc/free/mmap/sbrk: C library change.
stack objects:
- Each object is padded by 1 byte. GCC alloca function.
- De-register: constructor/destructor mechanism. The following compilation happens:
```
int sum (int n, int *a){

int i, s = 0;
for (i = 0; i < n; ++i)
s += a[i];
return s;

}
```

Compiled to

int sum (int n, int *a){

    /* bounds push function enters a function context. A
    * matching call to bounds pop function will
    * delete parameters.
    */
    __bounds_push_function ("sum");

    __bounds_add_parameter_object (&n, sizeof (int), ...);

    __bounds_add_parameter_object (&a, sizeof (int*), ...);

    /* Extra scope created around the function. GCC will
     * call bounds pop function when leaving this
     * scope.
     */
    {
        /* Declare stack objects, and use GCC's destructor
         * mechanism to ensure __bounds_delete_stack_object is
         * called for each variable however we leave scope
         * (even if we leave with goto).
         */
        
        int i;
        __bounds_add_stack_object (&i, sizeof (int), ...);

        int s = u;
        __bounds_add_stack_object (&s, sizeof (int), ...);

        for (i = 0; i < n; ++i)
            s += *(int*)__bounds_check_array_reference(a, i,  sizeof (int), ...);

        __bounds_delete_stack_object(&s);
        
        __bounds_delete_stack_object(&i);
    }
    end;
    __bounds_pop_function("sum"); /* Delete a, n. */
    
    return s;
}

goto example. Figure 4: goto label1 creates b and goto label2 destroys b.

objects by goto

Corner Cases:

pointers passed from unchecked code to checked code:
- If points to registered object: can be derived from another object (registered or unregisterd), cannot detect.
- If points to unregistered object: can detect and report, but allow such error.
pointers passed from checked code to unchecked code:
- unchecked accesses can occur.

Splay trees to look up pointers:

Binary tree where frequently used nodes migrate towards the top of the tree;
on average, the look-up function was iterated 2.11 times per call on a typical large program. unrolled first two iterations of the loop to optimise these cases.

A Brief summary from ICSE 2006²

Jones-Kelly inserts the following checks (ignoring any later optimizaiton) on each arithmetic operation involving a pointer value:

JK1. check the source pointer is not the invalid value (-2);
JK2. find referent object for the source pointer value using the table;
JK3. check that the result pointer value is within the bounds of this referent object plus the extra byte. If the result pointer exceeds the bounds, the result -2 is returned to mark the pointer value as valid.
JK4. Finally, on any load or store, perform checks[JK1-JK3] but JK3 checks the source pointer itself.

Backwards-compatible bounds checking for arrays and pointers in C programs, here. In Automated & Algorithmic Debugging, 1997. ↩
Backwards-Compatible Array Bounds Checking for C with Very Low Overhead, ICSE, 2006. ↩

If you could revise
the fundmental principles of
computer system design
to improve security...

... what would you change?

Jones Kelly

A Brief summary from ICSE 20062

A Brief summary from ICSE 2006²