Sticky Tags: Efficient and Deterministic Spatial Memory Error Mitigation using Persistent Memory Tags

Sticky Tags: Efficient and Deterministic Spatial Memory Error Mitigation using Persistent Memory Tags Floris Gorter∗, Taddeus Kroes‡, Herbert Bos∗and Cristiano Giuffrida∗ ∗‡Vrije Universiteit Amsterdam ‡taddeuskr[email protected] ∗{f.c.gorter,h.j.bos,c.giuffrida}@vu.nl Abstract—Spatial memory errors such as buffer overflows still rank among the top vulnerabilities in C/C++ programs. Despite much research in the area, the performance overhead of (even partial) mitigations is still too high for practical adoption. To reduce the cost, recent solutions are shifting towards hardwareassisted techniques such as Arm’s Memory Tagging Extension (MTE). Unfortunately, state-of-the-art MTE solutions incur high overhead due to frequent memory (re)tagging, especially on the stack. Moreover, they rely on the secrecy of random memory tags and offer probabilistic security guarantees. In this paper, we first provide evidence that random tagging offers limited protection as attackers can deduce the memory tags by means of speculative probing. We then present StickyTags, a deterministic MTE solution that efficiently mitigates bounded spatial memory errors. By organizing the stack and heap layout into per-size-class regions, we can apply persistent memory tags to each region in a predetermined pattern. Hence, the memory tags need only be initialized once, after which they can be reused by objects of the same size class. This eliminates the need for costly memory retagging and allows for a fixed, round-robin assignment of the tags, surrounding every object with large implicit spatial guards. While the size of such guards is bounded by the 4-bit MTE entropy (16 tags), the protection is efficient and deterministic. Indeed, we show StickyTags significantly outperforms existing solutions with realistic runtime overheads for practical adoption (≤4% on SPEC CPU2006), while fully mitigating 7 out of 8 spatial CVEs evaluated by a recent probabilistic MTE solution. 1. Introduction Spatial memory errors remain a common and impactful security concern. The 2023 CWE ranking lists out-of-bounds writes as the most severe software weakness [1]. Anecdotally, the GWP-ASan project has already found over thirty buffer overflows in the live build of Google Chrome [2], highlighting the need for exploit mitigations. While many existing tools can detect such bugs during software testing [3], [4], [5], [6], [7], [8], [9], [10], post-deployment solutions have found little applicability in the field due to ‡Now at Google their high overhead. Recent reports indicate that mitigations only see real-world deployment if their performance overhead stays below 5% [11]—rendering existing bounds checking solutions impractical [12], [13], [14], [15], [16]. In response, contemporary memory error detection and mitigation systems are shifting towards hardware-assisted solutions to reduce the overhead [6], [7], [17], [18], [19]. In particular, Arm’s Memory Tagging Extension (MTE) is a strong contender to provide spatial memory error mitigation on the cheap. MTE associates every memory location and every pointer with a tag, with the hardware disallowing any dereference if the pointer and memory tags do not match. Unfortunately, even state-of-the-art MTE solutions remain costly due to the need for frequent memory (re)tagging: LLVM’s MemTagSanitizer [20] incurs average and worst-case overheads on SPEC CPU2006 of 15.2% and 3.67x (respectively) for the stack alone (Section 8). Moreover, existing MTE solutions [20], [21], [22], [23], [24] heavily rely on random tags provided by the hardware [25] (which, in turn, impose expensive retagging costs). While such tags are not trivial to predict, at best they offer probabilistic security guarantees with low entropy. In particular, tag collisions between near or neighboring objects may leave the application vulnerable to contiguous overflows and bounded overflows such as type confusion bugs. Moreover, the low (4-bit) entropy of MTE tags leaves applications trivially vulnerable to brute-force attacks against a variety of crash-resistant targets, such as servers [26], web browsers [27], and even kernels, for instance Linux with the default oops mechanism [28]. Unfortunately, the situation is even worse, since, as we show, attackers can find pointer / memory tag matches through speculative probing [29]. More specifically, we show attackers can use a contention-based side channel to deduce whether or not a tag check results in a violation (i.e., tag mismatch). These results confirm, for the first time, conjectures in the community that MTE is vulnerable to side channels [25], [30], [31] and contradict a recent analysis by Google [32]. The net result is that such speculative oracles broaden the brute-force attack surface to non-crash-resistant targets (e.g., Linux without the oops mechanism [29]). In this paper, we present StickyTags, an efficient and deterministic spatial memory error mitigation for the stack and the heap. Rather than aiming for the classic random (re)tagging-based design to detect generic spatial and temporal errors with only probabilistic guarantees, StickyTags focuses on mitigating a specific (but widespread) class of vulnerabilities (bounded spatial errors) with strong performance and security guarantees. In particular, StickyTags offers production-ready overheads below 5% and deterministic security guarantees (where all tags are public and known) bounded by the number of MTE-provided tags. To minimize memory tagging costs, we build on Arm’s recommendation to limit the number of (de)allocations [33]. Rather than rewriting the application, we divide the heap and stack in per-size-class regions—assigning objects to predetermined slots with persistent memory tags already in place. We make sure to initialize the tags only once, and keep them in memory ready to be reused for objects of the same size class. The synergy between organizing memory into size classes and the underlying persistent tags allows us to achieve high performance by eliminating the need for memory retagging. This is especially beneficial on the stack, where the allocation (and hence tagging) frequency is high. As an added advantage and in contrast to state-ofthe-art solutions [20], our stack tagging design also offers increased backwards compatibility with legacy (non-MTE) devices. We detail our compatibility guarantees in Section 5. To provide deterministic security guarantees, we assign tags in a round-robin fashion in each region such that the tag of any object cannot collide with that of a known number of neighboring slots. As a result, our prototype StickyTags effectively creates implicit spatial guards around each object. Even with the current tag size of 4 bits, StickyTags efficiently mitigates spatial memory errors with underand overflow guards of 15 times the size class. Since the smallest class contains objects of 16 bytes (the MTE tagging granularity), each object in this class is protected by implicit spatial guards of 240 bytes in both directions. The spatial guards for larger size classes are proportionally larger. Our evaluation shows that StickyTags significantly outperforms state-of-the-art spatial memory error mitigations. On SPEC CPU2006 and 2017, StickyTags incurs geomean overheads of ≤4% measured both with MTE analogs [34] and MTE devices, bringing spatial memory protection within reach of production systems for the first time. StickyTags is 12x faster on average than MemTagSanitizer (stack tagging) and nearly 2x faster than the Scudo allocator (heap tagging), while fully mitigating 7 out of 8 spatial CVEs evaluated by the recent (probabilistic) MTSan [17]. Contributions. We make the following contributions: •We present the first on-device evidence that speculative probing can leak MTE pointer / memory tag matches, questioning random tagging as a mitigation strategy even for applications not prone to classic brute forcing. •We present a design for deterministic memory tagging for the stack and the heap that uses persistent tags to enable efficient spatial memory guards with MTE. We further study the applicability of persistent spatial guards to x86 architectures, using lightweight compiler instrumentation to compensate for the lack of MTE. •We evaluate our StickyTags prototype and show that StickyTags provides production-ready overheads. Availability. https://github.com/vusec/stickytags 2. Background Spatial memory errors. Spatial memory errors such as buffer overflows occur when a derived pointer erroneously accesses a different object than its base pointer. To prevent exploitation of such bugs, bounds checkers [12], [13], [14], [15], [16], [35] retrofit programs with checks that disallow such illegal accesses. Unfortunately, bounds checkers have not seen widespread adoption due to high overheads. To lower the overhead, other solutions reduce the scope of bounds checking and instead rely on explicit spatial guards bracketing each memory object [2], [3], [4], [9], [36], [37]. Such guards, implemented by means of guard pages [2], [38] or compiler-enforced redzones [3], [4], [36], [37], can detect invalid out-of-bounds reads/writes up to the guard size. This can mitigate contiguous overflows and bounded non-contiguous overflows, such as off-by-N errors and type confusion. In the latter case, unsafe type casts allow attackers to replace an object pointer with a pointer to a larger object type, yielding out-of-bounds reads/writes at a bounded offset up to the largest difference in confusable object sizes [39]. Unfortunately, existing guard-based solutions still incur high overheads and have only found practical adoption in offline testing [3], [37] or online sampling [40]. Memory Tagging Extension. Memory Tagging Extension (MTE) is an Armv8.5+ feature to detect memory errors. It introduces a ‘lock’ and ‘key’ mechanism, with the hardware only permitting reads/writes if the pointer tag (key) matches the memory tag (lock). Checks are supported both in synchronous and asynchronous mode. Pointer tagging relies on Arm’s TBI (Top-Byte Ignore) feature to store a tag in the upper pointer bits. The 4-bit memory tags (16 values in total) are stored separately from application data. Existing MTE solutions [17], [20], [21], [22], [23], [24] often rely on the Arm IRG instruction to assign a random tag to each allocation/deallocation, which scales poorly due to frequent (re)tagging and provides probabilistic security. 3. Speculatively Probing for Random Tags For probabilistic MTE solutions based on random tagging [20], [21], [22], [23], [24], the assumption is that, even if attackers manage to hijack a tagged victim pointer (e.g., via a buffer overflow) to reference a target object, they cannot predict whether the tag of the target object matches the pointer tag—hindering reliable exploitation. However, even without brute-forcing capabilities [26], if attackers can deduce which tags are assigned at runtime, then the random source of the tags has no added benefit. This is because Listing 1 Tested probe gadgets to leak tag matches. 1flush(signal); 2if (/*mispredict */){ 3#ifdef DEP_LOAD 4idx =*oob_ptr; // target tag check 5*(signal+idx); // dependent load 6#else 7*oob_ptr; // target tag check 8*signal; // independent load 9#endif 10 } 11 reload(signal); // is signal cached? attackers can massage memory [41] until the victim pointer’s random tag happens to match the one of the target object— and only then trigger the vulnerability to achieve reliable exploitation in spite of random tagging. We now show attackers can indeed deduce tag assignments via side channels and bypass probabilistic MTE solutions that rely on secret random tags, confirming conjectures from the community [25], [30], [31] with the first evidence on real MTE hardware. Specifically, we show that attackers can leak whether the tag of a given victim pointer matches the tag of a target object using speculative probing [29], [42], [43]. This is possible by repeatedly probing different pointer / (massaged) object pairs using a probe gadget until microarchitectural side channels leak a tag match. For our evaluation, we conducted experiments on rooted Samsung Galaxy S22 and Google Pixel 8 Pro devices, supporting sync/async MTE mode. Our first experiment was on the former device in sync mode, using the standard Spectre probe gadget in Listing 1 (DEP_LOAD case). The gadget speculatively issues an out-of-bounds load via the (tagged) victim pointer (oob_ptr, line 4) followed by a load dependent on the loaded value (at signal+idx, line 5). The dependent load, if completed, fills a cache line and transmits 1 bit of information via a classic Flush+Reload covert channel [44] (i.e., “cache hit” as revealed by timing). We initially expected two possible scenarios for failed (i.e., mismatching) MTE checks on the speculative path: (i) they are fully synchronous and prevent the victim load from passing data to the dependent load, resulting in a 0% cache hit rate; (ii) they are fully asynchronous and allow data to be passed to the dependent load, resulting in a 100% cache hit rate similar to the successful checks. The former scenario would allow the MTE implementation to guarantee speculative memory safety—since the checks hinder any invalid speculative access—but also incur tag leakage—since the attacker can distinguish correct/incorrect tag pairs based on the cache hit rate. The latter scenario, in turn, would yield opposite guarantees (i.e., no tag leakage, no speculative memory safety). However, our first experiment revealed a high cache hit rate (suggesting checks are asynchronous), but not as high as for successful checks. Hence, we can still leak a tag match based on the cache hit rate. Our next question was why the failed check causes the subsequent dependent load to sometimes not complete in the speculation window. One hypothesis is that failed checks 1 2 3 4 5 6 7 8 9 10 Number of checks 0 20% 40% 60% 80% 100% Signal load cache hit rate Correct Tag (Both) Incorrect Tag S22 Incorrect Tag P8 Figure 1: Cache hit rates of a single independent load for correct/incorrect tag match on the Samsung S22 and Google Pixel 8 Pro. occasionally cut the speculation window short. Another is that they create contention on the memory subsystem (by having to act upon the tag violation), causing other memory operations to occasionally stall and fail to complete within the window. To answer this question, we designed another experiment with the simpler probe gadget in Listing 1 (not DEP_LOAD case), which, unlike standard Spectre, drops the second dependent load in favor of an arbitrary (independent) one. Switching to the independent load did not affect our original results and neither did switching to async MTE mode (where checks are very asynchronous even architecturally) or replacing the independent load with an independent store. This all seems to confirm our second hypothesis, with contention on the memory subsystem affecting the cache hit rate (and allowing for tag match leaks). Figure 1 presents our results when repeatedly triggering the simpler probe gadget for matching/mismatching tag pairs as we increase the number of checked out-of-bounds loads in the gadget (by duplicating line 7 in Listing 1). As expected, correct pointer tag / object tag pairs consistently score a cache hit rate of 100%. Incorrect tag pairs, on the other hand, result in an increasingly lower rate as we increase the number of (failed) checks and thus the contention. Moreover, one check is sufficient to leak a tag match (0.2% cache hit rate difference). The figure also includes results for the Pixel 8 Pro, on which we reproduced the behavior discussed for the S22, except that contention seems lower and our probe gadget can identify the correct tag starting from the contention caused by two (rather than one) checks. In summary, the contention caused by tag mismatches provides attackers with a convenient side channel to determine whether a tag mismatch occurred. Crafting probe gadgets is relatively simple: an attacker needs to trigger the target software vulnerability on a speculative path [29] and, unlike standard (and mitigated) Spectre [44], observe a microarchitectural signal from any independent memory operation within the speculation window. On some devices (Pixel 8), additional failed checks within the window may be required, but, since invalid memory accesses are common on speculative paths, this is a relatively minor hurdle for attackers to overcome. Our results provide concrete evidence that tag leakage attacks are possible with easy-to-craft probe gadgets and question the use of probabilistic MTE-based solutions that rely on random tagging as a mitigation—even with lack of brute-forcing capabilities [26]. Furthermore, our findings contradict a recent analysis on MTE by Google, which found no side channels on their tested devices [32]. 4. Threat Model We consider an adversary seeking to exploit an existing spatial memory error in a victim program. We assume attackers can exhaust the tag entropy through classic brute forcing for crash-resistant targets [26], [27], [28] or speculative probing for non-crash-resistant ones [29]. For speculative probing, the standard Spectre [44] threat model applies, with a local attacker mounting cross-privilege (e.g., userto-kernel or guest-to-host) or in-domain (e.g., JavaScript sandbox) attacks [45]. For the latter, attackers also need to bypass any deployed (browser) timer mitigations [46], for instance by crafting their own high-resolution timers [47], [48], [49], [50] or mounting timerless attacks [51], [52]. We consider overflows (and underflows) within the size of our spatial guards. This includes contiguous overflows and bounded non-contiguous overflows, such as constrained out-of-bounds accesses via type confusion, etc. Attackers can launch their spatial memory attacks not just through buffers on the heap, but also on the stack. In addition, they may attack both confidentiality and integrity (reads and writes). We consider temporal memory errors out of scope and subject of extensive literature on orthogonal defenses [53], [54], [55], [56], [57], [58], [59]. 5. StickyTags As later evidenced by our evaluation, frequent memory tagging (normally done for every allocation/deallocation) is a major performance bottleneck of existing MTE-based solutions. To reduce this overhead, StickyTags decreases the number of times it needs to tag memory, by reorganizing memory into regions each containing objects of a particular size class (Figure 2). It tags memory at the first use of an object slot, allowing the tag to persist across the lifetimes of different objects allocated in the same slot. Our persistent memory tags follow a deterministic pattern that assigns tags to slots in round-robin fashion, so for N-bit tags, each tag repeats every 2Nslots. This way, StickyTags protects against buffer underand overflows bounded by the number of tags times the slot size. Conceptually, each memory slot has two implicit spatial guards consisting of the 2N−1surrounding objects on both sides with different tags. The effective size of the guards depends on the size class S: each object is protected by (2N−1)×S guard bytes. With MTE featuring tags of N=4bits, this amounts to 15×S. To quantify this: our smallest (16 bytes) and largest (262 KB) size classes provide bi-directional guards of 240 bytes and 3.75 MB, respectively. HeapStack Validate tags match on loads/stores MTE Hardware Userspace Program Size Class (16 bytes) Size Class (32 bytes) Size Class (16 bytes) Size Class (64 bytes) char buf1[15]; char buf2[16]; char* ptr1 = malloc(60); char* ptr3 = malloc(64); 0 1 2 3 4 5 Tags ... 15 0 1 ... 2 0 0 1 1 0 1 2 ... ... 0 0 0 0 1 1 1 1 2 2 2 2 ... Tags char* ptr2 = malloc(10); [... stack populated ...] Figure 2: Memory organization in StickyTags. The tags are persistent: they remain in place when new objects reuse the memory. Within a size class the objects always use the same slot size, hence the tag layout in a region is constant. After an object is deallocated, a new object can reuse the slot while the underlying memory tags remain unchanged. The tags are repeated to match the size class, e.g., 64-byte objects require four consecutive identical tags. On object allocation, we tag the returned object pointer such that it matches the persistent tag of the corresponding memory location. The MTE hardware compares address tags with memory tags and generates an interrupt upon accesses in case of mismatch. While size classes are common in modern heap allocators [60], [61], and previous work has split the stack into separate regions per variable type to combat type confusions [62], [63], to the best of our knowledge the stack has never been divided into size classes. It is precisely this combination of a size class-based (stack and heap) allocator and persistent memory tags that allows StickyTags to deliver much higher performance than existing solutions. Specifically, StickyTags eliminates the need for retagging memory, because of which it performs well on both the stack, where the allocation (and hence retagging) frequency is typically high, and the heap, where large allocations are not uncommon and hence retagging is costly. 5.1. Persistent Memory Tag Initialization While StickyTags’ one-time tag initialization is key to its performance, it is also challenging. A naive solution is to maintain metadata to track whether the memory tag of a slot has already been initialized, and check it at object allocation time—initializing the tags only if needed. However, this strategy would introduce checks and metadata tracking on the fast path, severely impacting performance. Another option is to immediately tag an entire memory area every time a whole region (i.e., stack/heap chunk) is allocated. However, doing so may result in severe overtagging for memory that is never used, incurring both runtime and memory overhead. This is especially likely because modern applications and allocators tend to keep large amounts of unused memory around for future use. To avoid such shortcomings, StickyTags initializes memory tags only once the memory receives backing. In particular, StickyTags relies on user-level page fault handling to lazily initialize memory tags: upon accessing a memory page for the first time, the hardware triggers a page fault that StickyTags handles by initializing the predetermined memory tags for the page. For this purpose, it only needs to know the base address and size class of the region containing the page, which it obtains from per-region metadata maintained by the allocator. Using this information, StickyTags determines what tags to apply to the page based on the distance of the current page to the base of the region, because the region always starts with tag zero and tags cycle up deterministically (round-robin) from that point. 5.2. Size Classes Stack. For the stack, StickyTags allocates one region per size class of stack objects. Allocating the stack regions using the heap allocator (described below) allows StickyTags to deduce the size class at runtime when handling page faults by consulting the heap metadata. StickyTags uses stack size classes that are multiples of two, which simplifies pointer tagging, as we will explain in the next section. While there is at most one instance of each size class in a single-threaded application, there can be multiple in the case of multi-threading. StickyTags instruments each unsafe stack allocation in the program (as determined by static analysis [64]) to use the base pointer of the associated stack region instead of the regular stack. The regular stack is still used for return addresses, statically safe allocations, and stack objects in uninstrumented libraries. Since stack objects are allocated on each function entry, they require a highly efficient replacement scheme. Therefore, StickyTags decides at compile time which stack region pointer (or simply stack pointer) to use for each stack object and stores the stack pointer in thread-local storage (TLS). Note that StickyTags creates stack regions only for the size classes that it statically determines to be required. Dynamically-sized stack objects (e.g., calls to alloca) cannot benefit from this scheme and, like heap objects, require the allocator to find a region for their size class. Since this is already done for heap objects, StickyTags moves these objects to the heap by transforming them into malloc calls. It inserts calls to free at the end of the object’s lifetime, which it determines using dominance frontiers [65]. In our evaluation we rarely observe unsafe dynamically-sized stack objects. Therefore, moving these to the heap incurs negligible runtime overhead. Heap. For heap allocations, commodity high-performance memory allocators already provide a suitable organization with size classes. For instance, an allocator such as TCMalloc [60] uses slab allocation to efficiently implement per-thread caching of heap objects. StickyTags piggybacks on these efforts and ensures the allocator uses only size classes that are a multiple of 16 bytes—the MTE tagging granularity. See Appendix A for the exact size classes. Listing 2 Tagging stack pointers upon allocation. 1// assuming: 'ptr' is target allocation 2region_base =ptr &(˜((1<< 24)-1)); 3distance =ptr -region_base; 4jumps =distance >> size_class_power; 5tag =jumps &15; 6ptr =ptr |(tag << 56); 5.3. Tag Calculation Whenever StickyTags allocates a memory object, it determines the tag to use for the pointer (i.e., the address) based on the location of the underlying memory. Additionally, upon a page fault, StickyTags applies the appropriate tagging pattern to the faulting page, in accordance to the associated size class. The key insight for tagging is that StickyTags can deterministically calculate the correct tags for all allocation pointers and faulting pages such that both correspond to the same tagging layout. Stack. Since the stack is designed for frequent allocations, it is crucial to optimize pointer tagging even with efficient persistent memory tags. For our purposes, we considered three possible design options. The first maintains an explicit (per-size-class) tag pointer in TLS similar to the stack pointer, which we forward through function calls and increase/decrease accordingly, allowing StickyTags to trivially calculate the next tag to use based on the current tag pointer value. The second option relies instead on the stack pointer to calculate the current (per-size-class) tag value just-intime. The third option is a hybrid design. Specifically, if we ensure that all stack allocations are performed unconditionally (i.e., we perform allocation hoisting), then we can assume complete linearity of the allocations within each size class in a function. As a result, we do not need to recalculate the tag for each allocation (since the tag layout is fixed), and instead need only calculate the first tag in the function for each size class, cache it, and offset subsequent allocations accordingly. With this approach, we effectively calculate and maintain an explicit function-local tag pointer. After inspecting preliminary benchmark results, we quickly discarded the two options based on explicit tag pointer management, as any increased pressure on the register allocators caused by propagating variables proved to undermine performance. Instead, we focused on the second option, optimizing the performance of just-in-time tag calculations as much as possible. Listing 2 presents how StickyTags performs just-in-time pointer tag calculations for stack allocations based on the object address. In particular, by computing the distance of the current address to the base of the region, StickyTags can deduce how many tag cycles fit in this distance, and hence determine the next tag to use. To optimize the calculation, we align the base of each stack region to 16 MB and limit the size of each region to 16 MB. As a result, we can find the base of a stack region by masking (i.e., cutting down) any arbitrary stack object’s pointer to the 16 MB boundary, instead of having to perform a memory load (line 2 of Listing 2). Next, a simple subtraction yields the distance of the object to the base (line 3). We compute how many objects fit in this distance by dividing it by the size class of the region (as a power of two exponent). The computation is efficient: the size class of the allocation (and the corresponding region) is known at compile time, while the stack’s size classes are a multiple of two, allowing us to use right shifts rather than divisions (line 4). By knowing how many objects fit before the current one, StickyTags computes the next tag to use by performing a modulo 16 (the tag cycle size) operation, which is optimized to a bitwise AND (line 5). The last step applies the tag to the upper bits (56-63 with Arm TBI) of the pointer (line 6). Now that StickyTags has tagged the pointers of the allocations, it must ensure that the underlying memory follows the same tagging layout. To apply these persistent memory tags to the stack upon page faults, it uses an algorithm that closely resembles Listing 2. Starting from a faulting address, it obtains the corresponding region base and size class from the heap metadata (since StickyTags allocates stack regions using the heap allocator) and computes the first tag of the page through the same steps as in Listing 2 (lines 3 to 5). Finally, it applies the memory tags by repeatedly executing the STG (store tag) MTE instruction, looping over the page in chunks of the size class, and increasing the tag by one for every object—wrapping around after tag 15. It is important to note that StickyTags tags stack memory upon page faults in a runtime library and hence the inline stack instrumentation (see Listing 2) does not require any MTE instructions. More specifically, StickyTags’ stack tagging instructions do not require STG to store memory tags, which is instead done by the page fault handler, nor LDG to load tags from storage, since the pointer tags are computed based on the stack addresses (and applied using TBI). This comes with the added benefit of providing backwards compatibility with legacy Armv8 devices (supporting TBI, but not MTE). Indeed, if a device does not support MTE, StickyTags can simply not register the page fault handler, thereby making memory tagging fully conditional. In contrast, random tagging solutions such as MemTagSanitizer [20] require unconditional insertion of MTE instructions on the stack, thereby breaking the application binary interface (ABI). As acknowledged by Google, retaining ABI compatibility is crucial to deploy stack tagging in practice— and this is especially the case for systems targeting a wide variety of Arm devices such as Android [66]. Heap. On the heap, StickyTags tags pointers by piggybacking on the existing heap metadata to retrieve the base address and size class of the object’s region. In contrast to the stack, the heap uses size classes that are multiples of 16 bytes to avoid excessive memory overhead as well as potential performance penalties due to internal fragmentation of power-of-two heap allocators [16]. Since the allocation patterns on the heap are generally less intensive, we trade off better memory locality for a slightly more expensive tag calculation. The main complication is that some size classes do not fit perfectly in the memory page granularity, because dividing the page size by a size class that is not a multiple of two results in a non-integer object distribution (e.g., 4096/48). StickyTags addresses this by offsetting the memory tagging initialization accordingly, such that it accounts for memory objects that are partially tagged by a (prior or future) neighboring page fault. The algorithm for tagging heap pointers follows the same structure as for the stack (Listing 2), with the following minor differences: (1) the region base and size class are determined through a metadata lookup, and (2) the jumps calculation (line 4) is a division instead of a right shift (as the size classes are not always a power of two). The result of this division is always an integer, since the offset from the start of the allocation to the region base (distance) is guaranteed to be a multiple of the size class. While StickyTags’ lazy tagging strategy reduces the tagging costs for large objects within a region, the onetime tagging and subsequent checks still incur some residual overhead for huge heap objects. To reduce the cost of both memory tagging and the checks that MTE performs (only) on tagged memory, StickyTags includes an optimization where huge objects are allocated in separate (guarded) memory regions and remain untagged. Huge object allocations (>262 KB) already constitute a special case in TCMalloc: each resides in its own dedicated region (also called a span). Since such huge objects do not have any neighboring objects inside the region, we can simply spatially fence their regions using inaccessible guard pages [10], [38]. Similar optimizations are also present in modern allocators, for instance in the Scudo allocator (Android), which does not tag objects bigger than a threshold (64 KB on Android, 131 KB by default) and instead relies on guard pages [67]. While Scudo does this to avoid (frequently) tagging large regions of memory [67], StickyTags primarily aims to reduce the residual tag checking overhead, since huge objects can reuse previously tagged memory when available. 6. Persistent Spatial Guards on x86 In this section, we show that the principle of persistent spatial guards along with one-time initialization extrapolates well to the x86 architecture, even though x86 does not have memory tagging capabilities. In the absence of MTE, we rely on providing spatial memory error mitigation through more traditional compiler-inserted checks and (padded) explicit spatial guards, commonly called redzones. As before, we reorganize the address space into regions containing objects of the same size class, but now additionally we place redzones at fixed intervals within each region (see Figure 3). By doing so we can optimize redzone management, even eliminating the need for out-of-bound metadata such as a shadow memory. Compared to the implicit spatial guards of MTE, where tags are associated separately from the memory, in the case of x86 the persistent guards are explicit, as they weave between objects to spatially separate them. As a result, each object size (and hence the size class) is inflated by including the redzone on its right side. Note that the redzone on the left is always the right redzone of the Size Class Regions Redzone Slot Padding Figure 3: On x86: Memory is organized in size classes, each containing equally sized slots of a given size class, interleaved by redzones. Objects are padded to fit the slot. Algorithm 1 High-level bounds check. The actual implementation reuses the loaded value for reads instead of calling LOAD BYTE, and unrolls the loop for up to 8 fast checks. REDZONE DISTANCE is different for the heap and the stack. offset ←0 while offset < num accessed bytes do if LOAD BYTE(address +offset)=guard value then region ←GET REGION(address) sc ←GET SIZECLASS(region) dist ←REDZONE DISTANCE(region, address, sc) if dist < 0∨num accessed bytes > dist then RAISE ERROR(out of bounds) offset ←offset +redzone size previous object, except for the first object, for which the left redzone is created along with the region initialization. Existing redzoning solutions (e.g., AddressSanitizer [3]) use a shadow memory to record which memory is accessible, storing one bit of accessibility information for each byte of application memory. This fine-grained metadata management is expensive in both runtime and memory usage, but is necessary for a design in which a memory location containing an object (or padding bytes) can later be used to store a redzone, and vice-versa. Especially if we want the redzones to be reasonably large (e.g., 256 bytes) to approximate the lower-bound security guarantees of our MTE solution, the frequent construction and destruction of redzones is expensive. In contrast, persistent redzones entirely eliminate the need for a shadow memory. The base address and size class of the containing region are known for each memory location, and can be used to determine whether a pointer points to a redzone. Additionally, since the redzones only need to be initialized with guard values (see below) once, we avoid redzone creation becoming a severe performance bottleneck. Accessibility Checks. We insert accessibility checks before each memory read/write. We leverage redzone-aware static analysis at the compiler level to skip unnecessary checks and merge checks of adjacent memory ranges, similar to state-ofthe-art compiler optimizations as seen in related work [36]. The checks consult the metadata of the region containing the accessed memory address, and use its base and size class to determine whether the pointer falls within a redzone. This introduces three memory loads (metadata, region base, and void foo() {char buf [64]; memset(buf, 0, 96); } buf memset checks Figure 4: Fast checks on a stack object with 64-byte redzones. The access spans more than a redzone and is checked by fast-checking every 64 bytes, failing on the second check. size class) and some arithmetic/branching operations which together cause high runtime overhead. We therefore use a guard value, as done by LBC [4], to quickly filter benign memory accesses: a single byte value that is stored in each redzone byte. To avoid writing guard values to a redzone twice, we lazily initialize guard values upon a page fault. Each accessibility check first performs a “fast” check, comparing the byte value at the accessed location to the guard value, only resorting to a regular “slow” check based on region metadata if the values match. Algorithm 1 shows this in detail. Because a memory access can access more bytes than fit in a redzone, one fast check is emitted for each redzone size bytes of the access (see Figure 4). Otherwise, an attacker might abuse a large memory access that starts before the redzone and thus does not contain the guard value in the first byte, but crosses the entire redzone to access the next object slot. As a result, for very large memory accesses, the performance gain of doing fast checks is overcome by the number of fast checks that are needed. Hence, we only emit fast checks if the required number is still beneficial for performance (up to eight, determined experimentally). To optimally benefit from fast checks, the guard value should be uncommon in regular application memory. In summary, on x86 we use explicit persistent spatial guards (i.e., redzones) that allow us to scale to relatively large guard sizes, since we avoid (frequent) redzone creation/destruction becoming a bottleneck by only having to initialize the guards once. Due to a lack of hardware assistance, we rely on compiler-inserted checks to validate memory accesses. As we will show in our evaluation, (large) explicit persistent spatial guards are indeed significantly more efficient than their non-persistent counterparts. However, the use of compiler checks still results in residual overheads unsuitable for production use. 7. Implementation We have implemented our prototypes on Linux on top of the LLVM [68] compiler infrastructure and the TCMalloc [60] memory allocator. We apply our compiler passes after link-time optimizations. This ensures that inserted instrumentation does not interfere with any analysis during optimizations. Our implementations of implicit guards (MTE tags) and explicit guards (redzones on x86) share the memory reorganization and page fault handling logic, and mainly differ with respect to the application of guards. Size Classes. We use TCMalloc [60] as the basis for our allocator. TCMalloc organizes objects into size classes by default. A compiler pass, based on LLVM’s internal SafeStack [69], creates size classes for the stack and also applies the pointer tags. We modified the pass to support one “unsafe” stack per size class. We rely on TCMalloc to allocate memory areas for the stack regions and to determine object size classes at runtime. Large stack objects that do not fit in any of the precomputed size classes are assigned a new, unique size class. This rarely occurs in practice. Page Fault Handling. A dedicated poller thread catches page faults in user mode using Linux’ userfaultfd system call, initializing memory tags and redzones on x86 in the faulting page when it is accessed for the first time. We derive where to apply the tags and redzones from perregion metadata maintained by TCMalloc. Execution of the poller/application threads is interleaved: during page fault handling, the faulting application thread waits for the poller thread to finish. Because only one thread runs at a time, there is no offloaded overhead on a separate core. 8. Evaluation In this section, we evaluate the performance and security of StickyTags. We measure the runtime and memory overhead using the SPEC CPU2006 and CPU2017 benchmarking suites, and compare this to state-of-the-art solutions. To quantify the security impact of StickyTags, we use the Juliet Test Suite [70], existing CVEs [17], and a type confusion vulnerability analysis. Additionally, we investigate the performance accuracy of existing MTE analogs. For additional information and experiments we refer to the Appendix. 8.1. Experimental Setup For the core of our experiments we use a rooted Google Pixel 8 Pro with MTE support. The device contains 12 GB RAM and runs a chroot Debian 12 distribution. We further make use of a Samsung Galaxy S22 (8 GB RAM) and a MacBook Pro (Apple M2, 16 GB RAM, Asahi Linux 6.3, Debian 12). All singlethreaded benchmarks are pinned to a single core. Each measurement reported is the median of five iterations of the same program (using the reference workload for SPEC CPU). For the baseline, we enabled linktime optimizations and used an unmodified TCMalloc as the memory allocator. Note that default TCMalloc has an average speedup of 11.7% compared to the default (non-MTE) Scudo allocator (and 8% to the default GNU heap allocator) and up to 73% for a single benchmark (471.omnetpp), while consuming 3% more memory on average. Unfortunately, we have to exclude SPEC CPU2017 from most of our experiments, because the baseline runs out of memory. The system requirements for SPECspeed 2017 state 16 GB of physical memory, and the Pixel 8 and S22 do not meet this. MTE Hardware. Recent work concerning MTE uses analogs to approximate the overhead of memory tagging 0% 2% 4% 6% 8% 10% 12% 14% 16% Runtime overhead (%) geomean 483.xalancbmk 482.sphinx3 473.astar 471.omnetpp 470.lbm 464.h264ref 462.libquantum 458.sjeng 456.hmmer 453.povray 450.soplex 447.dealII 445.gobmk 444.namd 433.milc 429.mcf 403.gcc 401.bzip2 400.perlbench Sized Stack Tag Stack Ptrs Tag Stack Mem Tag Heap Ptrs Tag Heap Mem ASync Checks Figure 5: Runtime overhead buildup of different components of StickyTags on SPEC CPU2006 using MTE hardware (Pixel 8). since MTE hardware was not widely available [17], [19], [34], [71]. In our evaluation, we measured the performance of StickyTags with actual MTE hardware. First, the Google Pixel 8 (Tensor G3, android14-5.15) supports MTE and allows the feature to be enabled through its developer options. Second, by rooting a Samsung S22 and deploying a custom Exynos (Linux 5.10) kernel, we manage to activate its MTE hardware by explicitly ignoring the nomte kernel parameter. However, on the S22 the locked-down boot monitor does not reserve backing (physical) memory to store the memory tags for uncached data. Consequently, tagging memory works as expected, reading the target data into the cache and setting the memory tags in the cache hierarchy accordingly. However, as soon as the data leaves the cache, the memory tags cannot be swapped to backing memory and effectively vanish. Subsequent accesses to the memory cause a segmentation fault by the MTE checks (since the pointer still has the tag). While the Pixel 8 serves as the main target for evaluation (with completely functional MTE), the S22 nonetheless provides another data point as MTE implementation, allowing us to gain further insights into the performance of MTE’s memory tagging and our design. Additionally, to paint a complete picture with respect to existing work, we also conduct performance experiments with the existing MTE analogs on the S22 (and Apple M2). 8.2. Performance Buildup For our performance evaluation we configured MTE on the Pixel 8 to perform asynchronous checks, which Arm recommends for production usage [72]. Figure 5 displays the runtime overhead of StickyTags on each individual benchmark of the SPEC CPU2006 suite. In total, StickyTags incurs a geomean runtime overhead of 4.0%. The figure breaks down this overhead into six distinct components: using size classes on the stack (1.0%), tagging stack pointers (0.1%), tagging stack memory (0.1%), tagging heap pointers (0.8%), 110 100 1K 10K 100K 1M Number of page faults (log scale) geomean 483.xalancbmk 482.sphinx3 473.astar 471.omnetpp 470.lbm 464.h264ref 462.libquantum 458.sjeng 456.hmmer 453.povray 450.soplex 447.dealII 445.gobmk 444.namd 433.milc 429.mcf 403.gcc 401.bzip2 400.perlbench Stack Heap Figure 6: Number of (4 KB) page faults in SPEC CPU2006. tagging heap memory (0.5%), and the asynchronous checks (1.5%). Note that the heap and stack memory tagging components constitute the overhead of using userfaultfd to one-time initialize the persistent tags upon page faults. From the overhead buildup figure we can conclude that tagging memory is cheap (see geomean bar), which is a logical consequence from our persistent tags design. Moreover, we see that using a stack with size classes can be the largest contributor of overhead in some benchmarks (400.perlbench, 445.gobmk), while overall the slowdown is modest. For the CPU2006 benchmarks, we create an average (geomean) of 7 stack regions (each dedicated to a distinct size class). Then, on average, a maximum of 4 are used per function. Note that these numbers are statically computed, meaning that some stack regions may be unused at runtime depending on the execution path. Excluding the checks, the remaining overhead originates from tagging pointers on the stack and the heap, which correlates with the memory intensity of the applications. For instance, 447.dealII and 483.xalancbmk are known to be relatively heap-intensive, and hence these accordingly experience more overhead from tagging heap pointers. As touched upon before, we may choose to only use size classes that are a multiple of two on the heap, which accelerates the pointer tag calculation, but this may come with other drawbacks such as memory fragmentation. We observe that the overhead implications of enabling asynchronous MTE checks are low but non-negligible. On average, the checks comprise the most significant overhead component, however this is not unexpected, because StickyTags focuses on eliminating tagging overhead. Moreover, the checks clearly show up as the dominant overhead factor in multiple programs. The 471.omnetpp benchmark stands out the most, where the checks incur more than 11% overhead. Upon further inspection with perf [73], we found that for this benchmark the CPU experiences a 19% increase in stalled cycles in the backend, which is likely the result of the asynchronous checks creating additional contention. To better understand the characteristics of our memory System Heap Stack Both StickyTags 3.1% 1.2% 4.0% MemTagSan + Scudo 5.8% 15.2% 20.2% TABLE 1: Runtime overhead comparison between StickyTags, MemTagSanitizer, and Scudo using SPEC CPU2006 (Pixel 8). tagging design, we measured the number of page faults that occur at runtime for both the heap and the stack. Figure 6 displays the results of this experiment. Looking at the aggregate numbers in the figure, it is clear that the stack experiences much fewer page faults than the heap, with the geomeans being 20 and 83,154, respectively. Moreover, we see a logical correlation between the overhead of tagging heap memory being relatively expensive for 403.gcc and the large number of heap page faults for this benchmark. In contrast, 401.bzip2 also experiences a relatively large number of heap page faults, but the heap objects are effectively all huge (>262 KB), which means our huge objects optimization leaves them untagged. Without this optimization, the runtime overhead of 401.bzip2 grows from 6.6% to 7.7%. Additionally, the low number of page faults for the stack highlights the efficacy of our persistent tagging design on the stack. On average, only 20 memory pages need to be tagged throughout the entire lifetime of the evaluated applications, regardless of the intensity of their allocation patterns. 8.3. Comparison to the State of the Art In order to put the performance of StickyTags into perspective, we compared its overhead to state-of-the-art systems. We measured runtime and memory overhead using the SPEC CPU2006 benchmarking suite and evaluated against LLVM’s MemTagSanitizer (stack) and the Scudo heap allocator. The primarily probabilistic Scudo allocator assigns a random tag to every heap allocation and retags the memory upon deallocation. Additionally, Scudo guarantees neighboring objects to have different tags by employing an odd-even tag masking pattern. MemTagSanitizer tags every stack allocation with a “random” tag at the start of its lifetime and resets the tag at the end of it. To avoid scalability issues with random tags requiring an extra live register for each variable, the tags are not completely random. Instead, MemTagSanitizer generates a random base tag for each function, with the following stack variables receiving a tag derived from the base tag. Note that the primary use case of MemTagSanitizer is deployment in production binaries [20]. Unfortunately, MemTagSanitizer causes false positive tag mismatches due to untagged pointers accessing tagged stack memory. Therefore, for the faulting programs (400.perlbench and 471.omnetpp) we modified MemTagSanitizer to only use tag zero to avoid these non-trivial crashes. Table 1 shows the geomean runtime overhead of StickyTags, MemTagSanitizer, and Scudo on the SPEC CPU2006 suite. The table contains the isolated heap and stack overhead, as well as the combination of both. Most notably, we observe that MemTagSanitizer’s stack instrumentation incurs 15.2% overhead, while StickyTags’ stack overhead is [59] M. Erd˝ os, S. Ainsworth, and T. M. Jones, “Minesweeper: a “clean sweep” for drop-in use-after-free prevention,” in ASPLOS, 2022. [60] S. Ghemawat and P. Menage, “TCMalloc: Thread-caching malloc,” 2009. [61] D. Leijen, B. Zorn, and L. de Moura, “Mimalloc: Free list sharding in action,” in APLAS. Springer, 2019. [62] A. Milburn, E. Van Der Kouwe, and C. Giuffrida, “Mitigating information leakage vulnerabilities with type-based data isolation,” in 2022 IEEE Symposium on Security and Privacy (S&P). IEEE, 2022. [63] E. Van Der Kouwe, T. Kroes, C. Ouwehand, H. Bos, and C. Giuffrida, “Type-after-type: Practical and complete type-safe memory reuse,” in ACSAC, 2018, pp. 17–27. [64] LLVM, “Stack Safety Analysis,” Online, https://llvm.org/docs/ StackSafetyAnalysis.html. [65] S. Muchnick, Advanced Compiler Design and Implementation, 1997. [66] “Private email communication with Google (MTE) engineers.” [67] LLVM, “Scudo source,” https://llvm.googlesource.com/scudo/+/ 966620155350ba9e3d09b6bc70b9babc4d222027/combined.h#388. [68] C. Lattner and V. Adve, “LLVM: A compilation framework for lifelong program analysis & transformation,” in CGO, 2004. [69] “Safestack,” https://clang.llvm.org/docs/SafeStack.html. [70] F. B. Jr. and P. Black, “Juliet 1.1 C/C++ and Java Test Suite,” in IEEE Computer, 2012, pp. 88–90. [71] H. Liljestrand, C. Chinea, R. Denis-Courmont, J.-E. Ekberg, and N. Asokan, “Color My World: Deterministic Tagging for Memory Safety,” arXiv preprint arXiv:2204.03781, 2022. [72] Arm, “Arm Memory Tagging Extension,” Online, https://source. android.com/docs/security/test/memory-safety/arm-mte#async-mode. [73] Linux, “Profiling with performance counters.” [74] W. Han, B. Joe, B. Lee, C. Song, and I. Shin, “Enhancing memory error detection for large-scale applications and fuzz testing,” in Network and Distributed Systems Security (NDSS) Symposium, 2018. [75] S. Ainsworth and T. M. Jones, “Markus: Drop-in use-after-free prevention for low-level languages,” in S&P, 2020. [76] M. Phillips, “Globals Tagging - Discussion,” Online, https://groups. google.com/g/llvm-dev/c/FAR7zKNkWh4/m/FIddvBRQAgAJ. [77] J. Devietti, C. Blundell, M. M. Martin, and S. Zdancewic, “Hardbound: Architectural support for spatial safety of the c programming language,” ACM SIGOPS Operating Systems Review, 2008. [78] Arm, “Arm Memory Tagging Extension: Security Update,” Online, https://developer.arm.com/Arm%20Security%20Center/Arm% 20Memory%20Tagging%20Extension. [79] S. Singh and M. Awasthi, “Memory centric characterization and analysis of spec cpu2017 suite,” in ICPE, 2019. Appendix Apple M2: StickyTags with MTE Analogs System SPEC CPU2006 SPEC CPU2017 StickyTags-stack 0.7% 1.0% MemTagSan-stack 14.2% 8.8% StickyTags-heap 0.5% 0.7% Non-persistent-heap 1.6% 1.4% StickyTags-both 1.2% 1.9% MemTagSan + TC 15.8% 10.4% TABLE 4: SPEC CPU runtime overhead summary using MTE analogs for StickyTags, TCMalloc with non-persistent tagging, and MemTagSanitizer. Comparison to the state-of-the-art. In this section, we compare the overhead of StickyTags, TCMalloc with a non-persistent deterministic tagging scheme (described in Section 8.4), and MemTagSanitizer. We make use of MTE analogs on the Apple M2 and the SPEC CPU2006 and 2017 benchmarking suites. Note that the M2 uses pages of size 16 KB, which reduces the number of page faults StickyTags has to handle compared to a 4 KB page size. Unfortunately, the 657.xz s benchmark is known to exhibit an extremely large memory footprint [79], and we have to omit it because the M2 runs out of memory (16 GB). Although the system requirements for SPECspeed 2017 state 16 GB of physical memory, this is insufficient on our machine. Table 4 showcases the geomean runtime overhead we measured. The table contains the isolated heap and stack overhead, as well as the combination of both. Most notably, we observe that MemTagSanitizer’s stack instrumentation incurs 14.2% and 8.8% runtime overhead on CPU2006 and 2017, respectively, while StickyTags’ stack overhead is significantly lower at 0.7% and 1.0%. Moreover, for the heap we measure a runtime overhead of 1.6% and 1.4% on CPU2006 and 2017 for the non-persistent tagging design, while StickyTags manages to (more than) halve this overhead to 0.5% and 0.7%. With the stack and heap combined, StickyTags incurs a low overhead of 1.2% and 1.9%, compared to existing techniques with 15.8% and 10.4%, for SPEC CPU2006 and 2017, respectively. These data points for both the stack and the heap highlight the benefit of our design for persistent memory tags, with which we manage to relieve the pressure of frequent memory tagging. Listing 3 MTE analog for setting and clearing memory tags. The analog is adapted from the original [34] to be inlined. 1#define MTE_SET_TAG_INLINE(ptr, size) asm volatile ( \ 2"mov x2, %0 \n"\ 3"mov x3, %1 \n"\ 4"mov x17, %0 \n"\ 5"cbz %1, 2f \n"\ 6"1: \n"\ 7"mov x16, %0 \n"\ 8"lsr x16, x16, #56 \n"\ 9"and x16, x16, #0xFUL \n"\ 10 "strb w16, [x17, #0x0] \n"\ 11 "add %0, %0, #16 \n"\ 12 "sub %1, %1, #16 \n"\ 13 "add x17, x17, 1 \n"\ 14 "cbnz %1, 1b \n"\ 15 "2: \n"\ 16 "mov %0, x2 \n"\ 17 "mov %1, x3 \n"\ 18 :: "r"(ptr),"r"(size) : "x16","x17","x2","x3","memory") Vulnerability Type Project Program Version CVE-2016-10270 heap libtiff tiffcp 4.0.1 CVE-2016-10271 heap libtiff tiffcrop 4.0.1 CVE-2017-8786 heap pcre2 pcre2test 10.23 CVE-2017-14408 stack mp3gain mp3gain 1.5.2 CVE-2018-20004 stack mxml testmxml 2.12 CVE-2020-21675 stack fig2dev fig2dev 93795dd CVE-2020-21050 stack libsixel img2sixel 2df6437 CVE-2021-20294 stack binutils readelf 2.35 TABLE 5: Program details of the CVE analysis. Heap and stack size classes For the stack we use a total of 15 size classes, all of them being a multiple of two, and the smallest being the MTE tagging granularity. The list of classes consists of: 2Nwith N={4...18}, making the largest class 262144 bytes. For the heap we use a total of 76 size classes, all of them being a multiple of 16, and the smallest being the MTE tagging granularity. These are the default size classes in TCMalloc, with the exception of the first class being 16 instead of 8. Redzone guard value on x86 050 100 150 200 250 value of first byte 0 2 4 % of addresses 20.7% for byte 0 (outside graph) Figure 9: Byte values at dereferenced addresses in SPEC CPU2006. Bin ishows what percentage of dereferenced addresses contains value iin the first byte. Highlighted bin: 223 (default guard value). Occurrences of the guard value in application memory outside a redzone cause a slow check when dereferenced. To achieve high efficiency, it is important to limit the number of slow checks by choosing a guard value that occurs sparsely consistently across different types of programs. To find such values, we instrumented SPEC to log the first byte at the location of each memory access, as seen in Figure 9. •Values 0 and 1 are (unsurprisingly) the most common— as these are default initializers. This extends to a lesser degree to low values under 20. Similarly, the value 255 (used in bitmasks) is best avoided. •Text-processing applications such as 483.xalancbmk, 400.perlbench and 401.bzip show spikes in the range of printable ASCII characters (up to 127) and in particular alphabetic characters (65-90 and 97-122). •Powers of 2 and their multiples are prevalent. •Some benchmarks show recurring spikes at the multiples of some application-specific number. Webservers on x86 Saturation connections Throughput degradation Latency increase 50p 75p 90p 99p Nginx 250 7% 8% 7% 6% 5% Apache 350 8% 9% 10% 11% 15% Lighttpd 500 10% 14% 9% 11% 13% TABLE 6: Web server overhead at saturation: throughput degradation and increase in 50/75/90/99 percentile latency. We have benchmarked both our LTO-enabled TCMalloc baseline and our x86 design (configured to use explicit 158k 409k 437k 200 400 600 800 1000 1200 1400 0% 100% Nginx baseline x86 guards 74k 141k 153k 100 200 300 400 500 600 700 0% 100% throughput (reqs/s) CPU utilization Apache 214k 527k 588k 0 200 400 600 800 1000 1200 1400 0% 100% concurrent connections Lighttpd Figure 10: Web server throughput with increasing client connections. E.g., the Nginx baseline achieves its maximum throughput at saturation (100% CPU) at 250 connections, at which point the throughput degradation is 7% from our x86 persistent guards. persistent spatial guard of 64 bytes) on three major web servers: Nginx 1.17.4, Apache 2.4.41 and Lighttpd 1.4.54. We instrumented loadable modules and non-system libraries (including APR and APR-Util) for all servers. We used two Intel Xeon Silver 4110 machines—server and client—each with 8 hyper-threaded cores at 2.10 GHz and 32 GB of memory, connected by a dedicated 100 Gbit/s network link. We used a Linux 4.15 kernel with sendfile enabled and used a large number of keepalive connections with a short timeout. We ran our experiments with 16 worker processes, requesting 64-byte pages for 30 seconds using the wrk benchmark with an increasing number of concurrent connections. We repeated each experiment 11 times and report the medians here. All standard deviations are less than 1% except for 99-percentile latency for which it goes up to 2.6%. Figure 10 illustrates how we determined saturation points, i.e., the number of connections with the highest throughput at 100% CPU utilization. Table 6 details the throughput and latency impact on x86 for all servers: at saturation, throughput degrades by only 7-10% and 99percentile latency increases by 5-15%. Benchmark ST-heap ST-stack ST-both MTS Scudo Scudo+MTS 400.perlbench 1.02 1.09 1.11 1.36 1.29 1.54 401.bzip2 1.03 1.03 1.07 1.07 1.00 1.08 403.gcc 1.08 1.02 1.10 1.12 1.26 1.36 429.mcf 0.99 1.00 1.00 1.00 1.00 1.01 433.milc 1.01 1.01 1.01 1.02 0.99 1.01 444.namd 1.00 0.98 0.99 1.01 1.01 1.01 445.gobmk 1.00 1.04 1.05 1.25 1.00 1.25 447.dealII 1.06 0.97 1.06 1.02 1.09 1.09 450.soplex 1.01 1.01 1.00 1.00 1.01 1.03 453.povray 1.05 1.04 1.11 1.41 1.04 1.46 456.hmmer 1.01 1.01 0.99 1.01 1.00 1.01 458.sjeng 1.01 1.01 1.02 3.67 1.00 3.69 462.libquantum 1.03 1.00 1.00 1.02 1.01 1.00 464.h264ref 1.01 1.00 1.01 1.01 1.00 1.01 470.lbm 1.02 1.00 1.01 1.01 1.00 1.01 471.omnetpp 1.17 1.01 1.14 1.02 1.20 1.23 473.astar 1.03 0.99 1.02 1.01 1.03 1.03 482.sphinx3 1.02 1.00 1.01 1.00 1.00 1.01 483.xalancbmk 1.06 1.03 1.08 1.23 1.26 1.43 geomean 1.031 1.012 1.040 1.152 1.058 1.202 TABLE 7: Google Pixel 8 Pro SPEC CPU2006 MTE results. MTS=MemTagSanitizer, ST=StickyTags, both=heap+stack. MTE Analogs MTE Hardware Benchmark MTS MTS+heap ST-stack ST-both MTS MTS+heap ST-stack ST-both 400.perlbench 1.22 1.20 1.07 1.09 1.14 1.17 1.07 1.10 401.bzip2 1.10 1.10 1.03 1.04 1.17 1.17 1.03 1.04 403.gcc 1.07 1.17 1.00 1.07 1.11 1.41 1.00 1.08 429.mcf 1.03 1.03 0.99 1.00 1.00 1.01 0.99 1.01 433.milc 1.01 1.01 1.00 1.03 0.99 0.99 0.99 1.01 444.namd 0.98 0.98 0.97 0.97 1.01 1.01 0.97 0.97 445.gobmk 1.48 1.48 1.03 1.03 1.78 1.73 1.03 1.03 447.dealII 0.85 0.99 0.99 1.00 1.00 0.93 0.99 0.99 450.soplex 1.00 1.00 1.00 1.00 1.00 1.03 1.00 1.01 453.povray 1.14 1.14 1.05 1.05 1.39 1.30 1.05 1.05 456.hmmer 0.99 1.00 1.01 1.02 0.99 1.01 1.01 1.02 458.sjeng 4.19 4.20 1.04 1.04 7.33 6.01 1.04 1.04 462.libquantum 1.06 1.07 1.04 1.03 1.10 1.08 1.02 1.02 464.h264ref 1.01 1.01 1.00 1.00 1.02 1.02 1.01 1.01 470.lbm 1.04 1.04 1.04 1.04 1.04 1.04 1.04 1.04 471.omnetpp 0.97 1.01 1.00 1.03 1.01 1.17 1.01 1.04 473.astar 0.99 1.00 1.00 1.01 1.00 1.01 1.00 1.00 482.sphinx3 1.00 1.01 1.00 1.00 0.99 1.01 1.00 1.00 483.xalancbmk 1.28 1.37 1.02 1.07 1.59 2.23 1.02 1.07 geomean 1.140 1.161 1.014 1.027 1.228 1.257 1.014 1.027 TABLE 8: Samsung Galaxy S22 SPEC CPU2006 MTE results. MTS=MemTagSanitizer, ST=StickyTags, both=heap+stack. Benchmark MTS TC-NP MTS+TC ST-stack ST-heap ST-both 600.perlbench s 1.06 1.01 1.07 1.04 1.00 1.05 602.gcc s 1.05 1.06 1.12 1.01 1.02 1.03 605.mcf s 1.00 1.00 1.00 1.00 1.00 1.00 619.lbm s 1.02 1.04 1.06 1.03 1.03 1.06 620.omnetpp s 1.22 1.05 1.27 1.00 1.02 1.03 623.xalancbmk s 1.26 1.00 1.26 1.01 1.00 1.01 625.x264 s 1.41 0.99 1.41 1.01 1.00 1.01 631.deepsjeng s 1.04 1.01 1.05 1.02 1.00 1.02 638.imagick s 1.00 1.00 1.00 1.00 1.00 1.00 641.leela s 1.00 1.00 1.00 1.00 1.00 1.00 644.nab s 1.00 1.00 1.00 1.00 1.00 1.00 657.xz s------ geomean 1.088 1.014 1.104 1.010 1.007 1.019 TABLE 9: MacBook M2 SPEC CPU2017 analogs results. MTS=MemTagSanitizer, ST=StickyTags, TC=TCMalloc, NP=non-persistent. Appendix A. Meta-Review The following meta-review was prepared by the program committee for the 2024 IEEE Symposium on Security and Privacy (S&P) as part of the review process as detailed in the call for papers. A.1. Summary This paper details a speculative attack to leak MTE tags on real hardware. To mitigate the attack, the authors propose a reorganization of heap and unsafe stack objects that provides deterministic, bounded spatial memory safety. A.2. Scientific Contributions •Addresses a Long-Known Issue •Provides a Valuable Step Forward in an Established Field •Identifies an Impactful Vulnerability A.3. Reasons for Acceptance 1) The authors detail a new MTE tag leak side-channel attack. 2) The authors implement a new heap layout to provide deterministic, bounded spatial safety that mitigates the new side-channel attack. 3) The authors provide evaluation on performance and security benefits. A.4. Noteworthy Concerns 1) The memory overhead of 15% is non-trivial for many real world scenarios. 2) Exclusive use of StickyTags as a protection mechanism without an additional Use-After-Free (UaF) mitigation makes exploiting UaF easier, and makes detecting UaF exploits difficult. This is due to the reuse of object classes key to the design of StickyTags. However, the authors note that UaF protections can be deployed, and show this in an evaluation on UaF Juliet testcases.