Fat Pointers for Temporal Memory Safety of C

Jie Zhou, John Criswell, Michael Hicks

TL;DR

This paper introduces an efficient way to eliminate temporal memory safety bugs (like use-after-free) in C by extending Checked C with "fat pointers." By storing security metadata directly within pointers and memory objects rather than in separate tables, the authors achieve significantly lower performance and memory overhead than previous state-of-the-art solutions while maintaining practical backward compatibility.

What Problem Does This Paper Address?

C is notoriously "memory unsafe." While spatial safety (preventing buffer overflows) is a well-studied problem, temporal safety—preventing errors like use-after-free (UAF) or double-free—remains a major security hurdle.

Existing solutions generally fall into two camps:

  1. Disjoint Metadata: They keep security info (keys/locks) in separate data structures like hash tables. This is easy to integrate with legacy code but slow because every pointer access requires a costly table lookup.
  2. Low-Fat Pointers: They hide metadata in unused bits of a 64-bit pointer. These are fast but often have tiny "key spaces" (leading to security misses) or can’t handle large objects or stack-based variables.

The authors aim to provide a "best of both worlds" solution: a comprehensive defense that handles heap, stack, and global memory with low overhead and high security.

Methods

The authors extend Checked C (a spatially-safe C dialect) with new temporally-safe pointer types. Their approach uses two main techniques:

  • Fat Pointers: Instead of a standard 8-byte pointer, they use a 16-byte structure. This "fat" pointer contains the raw memory address plus 8 bytes of metadata (a 32-bit key and a 32-bit offset).
  • In-place Key-Lock Checks: Every memory allocation (on the heap or stack) is prepended with an 8-byte lock. When a pointer is created, it is assigned a unique key that matches the object's lock.
  • The Check: Before every dereference, the compiler inserts a check: if (pointer.key != object.lock) signal_error();. Because the metadata is "in-place," the CPU can calculate the lock's address using the pointer's address and offset, avoiding expensive lookups.
  • Marshalling: To interoperate with legacy C libraries that expect normal 8-byte pointers, the system provides "marshalling" functions that strip the metadata when calling a library and (optionally) attempt to restore it afterward.

Datasets

The authors evaluated their system using several benchmarks and real-world applications:

  • Olden Benchmark Suite: A collection of pointer-intensive programs featuring complex recursive data structures (trees, linked lists).
  • SPEC CPU2006 (429.mcf): A widely used, pointer-heavy vehicle scheduling benchmark.
  • Real-world Applications:
    • thttpd: A lightweight HTTP server.
  • parson: A JSON parsing library.
  • lzfse: A high-performance compression library.
  • curl: The ubiquitous network data transfer tool (specifically its engine and HTTP components).
  • Large-scale Analysis: They analyzed 5.5 million lines of C code (from SPEC CPU2017 and other open-source projects) to determine typical object sizes and justify their 32-bit metadata allotment.

Key Insights and Ideas

  • In-place is King: The "aha moment" is that the performance bottleneck in temporal safety isn't the check itself, but the lookup of the metadata. By making pointers "fat," the metadata is always exactly where the CPU needs it.
  • Language Extension vs. Compiler Transformation: Previous fat-pointer attempts failed because they tried to automatically transform all C code, which broke legacy libraries. By making this a language feature (new pointer types in Checked C), the authors give programmers explicit control over where safety is applied, making it much easier to handle "edge cases" and library boundaries.
  • 32/32 Split is Sufficient: By analyzing millions of lines of code, they proved that a 32-bit key (4 billion unique IDs) and a 32-bit offset (supporting objects up to 4GB) are more than enough for the vast majority of real-world C programs.

Key Results

  • Performance: On the pointer-intensive Olden benchmarks, the fat-pointer approach incurred a 29.1% overhead. This is a massive improvement over CETS (the previous state-of-the-art disjoint metadata approach), which had a 92.2% overhead on the same tests.
  • Memory: Memory overhead was 72% for Checked C vs. 202% for CETS.
  • Real-world Impact: For applications like curl and thttpd, the performance overhead was negligible (around 0.4%), proving the system is practical for production use.
  • Portability: The authors were able to port approximately 1–2 KLoC per person-day, suggesting that retrofitting existing codebases is a manageable task.

Limitations and Future Work

  • Multithreading: The current prototype is not fully thread-safe. A data race between a pointer dereference and a memory free could theoretically bypass the check. The authors suggest using atomic instructions or mutexes to solve this in the future.
  • Manual Effort: While the porting rate is decent, it still requires manual code changes. The authors propose extending automated tools like 3C to help convert raw C pointers to temporally-safe Checked C pointers.
  • Spatial Integration: This specific study focused on temporal safety. A "full" implementation would need to combine these checks with Checked C's existing spatial (bounds) checks, which would likely increase the overhead further.
  • Large Objects: The current prototype doesn't implement the "exceptionally large" pointer types (>4GB) discussed in the design.

Summary updated

Abstract

Temporal memory safety bugs, especially use-after-free and double free bugs, pose a major security threat to C programs. Real-world exploits utilizing these bugs enable attackers to read and write arbitrary memory locations, causing disastrous violations of confidentiality, integrity, and availability. Many previous solutions retrofit temporal memory safety to C, but they all either incur high performance overhead and/or miss detecting certain types of temporal memory safety bugs. In this paper, we propose a temporal memory safety solution that is both efficient and comprehensive. Specifically, we extend Checked C, a spatially-safe extension to C, with temporally-safe pointers. These are implemented by combining two techniques: fat pointers and dynamic key-lock checks. We show that the fat-pointer solution significantly improves running time and memory overhead compared to the disjoint-metadata approach that provides the same level of protection. With empirical program data and hands-on experience porting real-world applications, we also show that our solution is practical in terms of backward compatibility -- one of the major complaints about fat pointers.
BibTeX
@misc{zhou2022fat,
  author = {Jie Zhou and John Criswell and Michael Hicks},
  title = {{Fat Pointers for Temporal Memory Safety of C}},
  year = {2022},
  eprint = {2208.12900},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.12900},
}
Figure