Temporal

References:

[1] CETS: Compiler-Enforced Temporal Safety for C, ISMM, 2010. [paper]

Basics

Temporal safety

Temporal safety erros include:

  • dangling pointer dereferences (referencing an object that has been deallocated);
    • dangling pointer to stack;
    • dangling pointer to reallocated heap objects;
  • double free’s (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).

    Location-based temporal checking

Use location (or address) to determine whether it is allocated or not. Metadata records the allocated/deallocated status of each location.
Update the metadata upon all memory allocations/deallocations. Metadtata is checked during memory access.

  • Cannot detect the re-allocated dangling pointers.

Meta-data can be implemented in

  • tree structure, such as splay tree.
  • shadowspace, a large, directly accessed memory region, a hashtable, or a trie-based data structure.

Identifier-based temporal checking

Associates a unique (never reused) identifier with each memory allocation.

Per-pointer metadata via fat pointers Pointers are extended into multi-words.

  • Memory layout thus is changed.
  • Interfacing with libraries is challenging.
  • SoftBound: disjoint pointer-based metadata shadowspace for compatibility, but no temporal.

Set-based indentifier checking

Set data structure (such as hash table) is used to track allocation/deallocation.

  • O(1) lookups.
  • overheads on every memory reference.

Lock-and-key identifier checking

Every pointer is a tuple consisting of an address and a key. Every object in the heap begins with a lock. A pointer to an object in the heap is valid only if the key in the pointer matches the lock in the object.

  • A new key value is created when a new heap object is created; When an object is reclaimed, its lock is changed to some arbitrary value, so that the keys in any remaining pointers will not match.
  • Overhead: add extra words of storage for every pointer and every object in the heap; comparing the lock and key on every memory access.

Research Works

Created Jul 5, 2019 // Last Updated Jul 17, 2021

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

... what would you change?