CETS: Compiler Enforced Temporal Safety for C

Reference:

Temporal errors include:

  • dangling pointer dereferences (referencing an object that has been deallocated),
  • double frees (calling free() on the same object multiple times),
  • invalid frees (calling free() with a non-heap address or pointer to the middle of a heap-allocated region).

CETS: Compiler Enforced Temporal Safety.

Movivation

Temporal errors are challenging. Prior proposals suffer from one or more of the following deficiencies:

  • high runtime overheads,
  • high memory overheads,
  • failure to detect all temporal errors (for example, to the stack, to reallocated heap locations, or in the face of arbitrary casts)
  • requiring annotations inserted by the programmer,
  • or altering memory layout (which breaks compatibility with existing C code).

Example: Widely used Valgrind Memcheck tool1:

  • Fail to detect dangling pointers to reallocated data locations;
  • Exhibits runtime overheads in excess of 10x.

Overview

CETS: Compiler Enforced Temporal Safety.

Combination of two existing techniques:

  • An identifier-based scheme, which assigns a unique key for each allocation region to identify dangling pointers 2 3 4.
  • This per-pointer metadata is tracked using a disjoint shadowspace, yielding high compatibility because memory layout is unchanged.

Optimization in prototype implementation:

  • temporal-check elimination optimizations (analogous to, but different from, bounds-check elimination optimizations 5 6 7)
  • reduces the number of checks by 70% on average.

Design and Implementation

CETS’s temporal safety properties can be guaranteed only if spatial safety is enforced too (otherwise metadata corruption could occure).

CETS lock and key implementation

CETS avoids the compatibility problems of fat pointers by borrowing the shadowspace mechanisms commonly used in location-based approaches to support per-pointer metadata without changing memory layout. See Figure 2 below:

image

Each pointer with two additional word-sized fields:

  • (1) a unique allocation key
  • (2) a lock address that points to a lock location, which is queried on temporal checks 3 4.

Each allocated memory object is associated with a unique key.

Usage of lock and key:

  • Whenever memory region is allocated:
    • 1. a unique key is associated with the region of the allocated memory;
    • 2. a lock location is allocated;
    • 3. the lock value is initialized to the key value.
    • Invariant Property: the pointer is not a dangling pointer if and only if the pointer’s key and the value of the lock match.
  • When a memory region is deallocated:
    • 1. the lock location associated with the memory region is set to INVALID_KEY.
    • The lock location can be reused but only as another lock value, and never for some other purpose.
    • 2. the memory region is marked for possible reuse.
    • Invariant Property: Dangling pointers holding the old key will never be used for a successful dereference since the lock is either invalid or has a different lock value.
  • A mapping from keys to freeable pointers
    • defenses to temporal errors:
      • 1. free on pointers that are not returned by malloc().
      • 2. call free twice:
    • There is at most one freeable pointer associated with that key (i.e., the one originally returned by malloc()). (LLM: only one in all cases??? how about pointer assigned to another one, or passed to another function then freed there???).

Metadata operations

  • Initialization.
  • Heap allocation.
  • Pointer metadata propagation.
  • Dangling pointer check.
  • Heap deallocation.
  • Allocation/deallocation of lock addresses.
  • Call stack allocations and deallocations.
    • A key and corresponding lock address is associated with each stack frame.
    • This key and lock pair is given to any pointer derived from the stack pointer (and thus points to an object on the stack).
  • Metadata propagation with function calls.
    • When pointers are passed as arguments or returned from functions, the key and lock address must also travel with them.
    • Uses procedure cloning to transform every function declaration and function call site to include additional arguments for key and lock address. (LLM: backward compatibility is sacrificed.)

Formal Model of Memory Safety

todo

Evaluation

Overhead 8:

48% for temporal check;

116% for both spatial and temporal check.

  1. N. Nethercote and J. Seward. Valgrind: A Framework for Heavy-weight Dynamic Binary Instrumentation. In Proceedings of the SIGPLAN 2007 Conference on Programming Language Design and Implementation, June 2007. ↩
  2. T. M. Austin, S. E. Breach, and G. S. Sohi. Efficient Detection of All Pointer and Array Access Errors. In Proceedings of the SIGPLAN 1994 Conference on Programming Language Design and Implementation, June 1994. ↩
  3. H. Patil and C. N. Fischer. Low-Cost, Concurrent Checking of Pointer and Array Accesses in C Programs. Software — Practice & Experience, 27(1):87–110, 1997. ↩
  4. W. Xu, D. C. DuVarney, and R. Sekar. An Efficient and Backwards-Compatible Transformation to Ensure Memory Safety of C Programs. In Proceedings of the 12th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE), 2004. ↩
  5. R. Bodı́k, R. Gupta, and V. Sarkar.ABCD: Eliminating Array Bounds Checks on Demand. In Proceedings of the SIGPLAN 2000 Conference on Programming Language Design and Implementation, June 2000. ↩
  6. R. Gupta. A Fresh Look at Optimizing Array Bound Checking. In Proceedings of the SIGPLAN 1990 Conference on Programming Language Design and Implementation, June 1990. ↩
  7. T. Würthinger, C. Wimmer, and H. Mössenböck. Array Bounds Check Elimination for the Java HotSpot Client Compiler. In Proceedings of the 5th International Symposium on Principles and Practice of Programming in Java, 2007. ↩
  8. CETS: Compiler-Enforced Temporal Safety for C, ISMM, 2010. ↩
Created Jul 23, 2019 // Last Updated Jul 17, 2021

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

... what would you change?