GIANTSAN: Efficient Memory Sanitization with Segment Folding

A memory sanitizer catches out-of-bounds and use-after-free bugs by checking every access against metadata, but the popular location-based kind (like AddressSanitizer) is slow because it must load one shadow byte for every eight memory bytes — checking a kilobyte means 128 loads; this work from Hong Kong builds GiantSan, which notices that almost every stretch of memory a safe program touches is entirely valid, and pre-folds runs of valid bytes into power-of-two summaries so a region of any size can be checked in constant time — cutting AddressSanitizer's overhead by 59 percent while catching more bugs.

Why this problem is worth solving

The efficiency gap traces to a specific design choice, so it is worth being precise about how the two families of sanitizers differ.

The specific cost is a quantity the paper names, and it is what everything hinges on.

What people did before, and where it broke

• Pointer-based bound tracking (Softbound, Delta Pointers). Attach a bound to each pointer and propagate it through arithmetic. Where it broke. Propagation fails on pointer-integer casts and uninstrumented binary libraries, so once a bound is lost the sanitizer cannot protect that pointer or its descendants — too incompatible for real-world testing.
• AddressSanitizer-style per-byte shadow (location-based). Record each segment’s addressability in one shadow byte and check each access. Where it broke. The low protection density means a large region needs one load per eight bytes, so checks and metadata loads dominate and roughly double execution time.
• Rounded-up allocation bounds (Baggy Bounds, LFP). Round every allocation up to a power of two so its bound fits in tiny metadata that can be fetched directly. Where it broke. The rounded bound is larger than the real object, so accesses past the object but within the rounded region go undetected — many false negatives, unsuitable for finding bugs.
• Token authentication and redzone tricks (HWASan, in-band redzones). Tag pointers and memory with matching tokens, or fill padding with patterns, to detect strays. Where it broke. Each check still safeguards only a small region, so they inherit the same low-protection-density inefficiency, and small redzones can be jumped over entirely.
• The gap. Every efficient approach either gave up compatibility (pointer-based), gave up precision (rounded bounds), or kept the low density that makes location-based checks slow. What was missing was a way to keep the compatible per-byte model but let one metadata load safeguard a large region — which is exactly what practical sanitization needs.

How GiantSan works

The idea

Fold a run of identical metadata into one summary, so one load stands for many. The waste in a location-based sanitizer is that it re-reads the same answer over and over: to clear a thousand-byte region it loads a hundred and twenty-eight shadow bytes that almost all say the same thing, “this segment is fine.” GiantSan’s core move is to summarize away that repetition — it folds runs of consecutive valid segments into a single summary that records how long the valid run is, in powers of two, so one load of a deep fold certifies a large stretch of memory at once. Collapsing a flood of identical, same-target operations into a single summarizing action, so that one thing stands in for many and the per-item cost disappears, is the same move the key-value store concurrency work covered elsewhere on this site makes, folding a queue of writes to one item into a single batched update instead of applying each separately.

Optimize relentlessly for the common case, which is that everything is fine. The reason folding pays off so much is a fact about real programs: almost every segment a correctly-executing program touches is valid, because bugs are the rare exception, not the rule. GiantSan builds its whole checking algorithm around this — a cheap fast path reads a single summary that covers more than half of any safe region and confirms the access in one load, handling the overwhelming majority of checks, while a rarely-taken slow path deals with the leftover cases, and even that stays constant-time. Making the overwhelmingly common case nearly free and paying the fuller cost only in the uncommon case that genuinely needs it is the same discipline the CXL memory work covered elsewhere on this site follows, fronting an expensive lookup with a cheap check that almost always says “nothing to do here” and skipping the costly path.

Check whole operations, and reuse a loaded bound instead of reloading it. Once one load can certify a large region, two further savings open up. First, the sanitizer can protect an entire logical memory operation — a whole memset, a whole loop — with one region check, rather than checking each of its instructions separately. Second, it can cache the bound it discovers and reuse it: as a loop walks a buffer, later accesses fall within the already-loaded bound and need no new metadata, and GiantSan extends the cached bound only on demand, when an access finally runs past it. Loading a resource once and reusing it across many subsequent operations, rather than re-paying to fetch it every time, is the same economy the serverless orchestration work covered elsewhere on this site practices, keeping a warm resource around so a stream of requests can be served without repeating the setup cost.

Following a large memset through GiantSan

That is why location-based checks dominate runtime on large operations.

Why it works

• Folding runs of identical metadata replaces many loads with one. Checking a large region meant loading a shadow byte for every eight bytes, hundreds for a kilobyte → but summarizing a run of valid segments into one power-of-two fold lets a single load stand for the whole run → so a region of any size is checked with a constant number of loads instead of one per segment.
• A monotone encoding makes the fold check a single comparison. The summary must be read and interpreted on every check, which could itself be costly → but encoding it so smaller values mean longer addressable runs turns “is this folded to at least degree k” into one integer comparison → so the check is not just fewer loads but each load is trivially cheap.
• Two overlapping power-of-two folds cover any range in constant time. A region of arbitrary size does not align to a single summary → but any run of valid segments is covered by an overlapping prefix and suffix, each the largest power of two below the run length → so checking those two folds suffices, giving the first constant-time arbitrary-size region check for a location-based sanitizer.
• Optimizing for the common safe case keeps the fast path cheap. Handling every possible layout in one check would be complex and slow → but almost every region a correct program touches is entirely addressable, so a fast check covering that case with one load suffices most of the time, with a rare slow path for the rest → so the average check pays almost nothing.
• Operation-level checks and cached bounds cut redundant work. Checking each instruction separately reloads metadata for every access, and low-density metadata cannot be usefully cached → but a high-density fold lets one check cover a whole operation and lets a loop reuse a cached bound until it is exceeded → so repeated accesses on the same buffer stop re-paying for metadata.

What it costs (trade-offs and scope)

• It cannot catch sub-object overflows. Like every location-based sanitizer, GiantSan checks whether an access leaves the whole allocation, not whether one struct field overruns into a neighbor; catching that needs pointer-based tools that require type information and run much slower.
• Its speedup is one-directional. The folding summarizes low addresses to high, so forward and random buffer traversals run as fast or faster than AddressSanitizer, but reverse traversals are about 1.4 times slower; these are rare (well under one percent in the benchmarks) and underflow is less dangerous than overflow, but the guarantee is one-sided.
• Detection still rests on redzones and quarantine, which can be bypassed. Temporal-error detection uses delayed memory reuse that a program can occasionally slip past, and spatial detection still uses redzones — though an anchor-based check reduces the dependence on their size, which is what lets it catch bugs AddressSanitizer misses.
• On standard suites its detection matches AddressSanitizer, not exceeds it. The extra bugs it finds come specifically from reducing redzone dependence; on the general test suites it detects exactly what AddressSanitizer does, missing the same handful of uninitialized-value non-overflows.
• The gains lean on compiler static analysis. Operation-level protection needs the compiler to recognize operations via constant propagation, loop-bound, and alias analysis; where that analysis fails, the benefit shrinks back toward instruction-level checking.
• It is a prototype on one platform. Implemented in LLVM and Clang for x86 and evaluated on SPEC CPU 2017 plus a few real projects, not across architectures or the full space of workloads.
• It shares the memory costs of its predecessors. The fold degree fits cleverly into the existing shadow byte, but it still carries the shadow-memory, redzone, and quarantine memory overhead of location-based sanitization.

The evaluation

Check yourself

Sources

The paper is “GiantSan: Efficient Memory Sanitization with Segment Folding” by Hao Ling, Heqing Huang, Chengpeng Wang, Yuandao Cai, and Charles Zhang, published at ASPLOS 2024, DOI 10.1145/3620665.3640391. The authors are at the Hong Kong University of Science and Technology and the City University of Hong Kong; GiantSan is open-source.

This explainer is written from the full 17-page text. Everything above comes from the paper’s own sections: the introduction and background contrasting pointer-based and location-based sanitizers, motivating location-based methods’ compatibility and their low-protection-density inefficiency (AddressSanitizer needing 128 shadow loads for a kilobyte, about 80 percent of overhead from checks and loads), and distinguishing instruction-level from operation-level protection; the design of the binary segment-folding shadow encoding with its monotone state codes fitting in one eight-bit shadow byte, the constant-time region-check algorithm with its fast and slow paths using an overlapping prefix and suffix of power-of-two folds, the on-demand quasi-bound history caching, operation-level check generation via static analysis, and the anchor-based enhancement that reduces redzone-size dependence; and the evaluation on SPEC CPU 2017 (geomean overhead 46.04 percent versus 112.58 for AddressSanitizer and 74.89 for ASan—, a 59.10 and 38.52 percent reduction; ablation showing about 53 percent of checks optimized), the detectability study on the Juliet Test Suite, Linux Flaw Project, and Magma (matching AddressSanitizer on standard cases, 463 more PHP detections via the anchor enhancement, far fewer false negatives than the rounded-bound LFP), and the reverse-traversal limitation and sub-object and quarantine caveats.