Beyond Tag Collision: Cluster-based Memory Management for Tag-based Sanitizers

Tag-based sanitizers attach a small "key" to each pointer and a matching "lock" tag to its target memory object, enabling runtime verification of pointer-object consistency and helping developers to detect potential memory violations. However, the limited tag encoding space challenges existing studies in assigning distinct tags to memory objects across temporal and spatial dimensions, leading to potential tag collisions. In this paper, we present ClusterTag, a novel cluster-based memory allocator aimed at simultaneously mitigating tag collisions in both temporal and spatial dimensions. The core design of ClusterTag effectively balances the significant mismatch between tag encoding space and memory objects: it divides memory objects into multiple independent clusters, thereby limiting tag collisions to finite chunks within each cluster. To mitigate tag collisions across clusters, we design a cluster-grained heap randomization scheme. This approach introduces random address intervals between clusters and further breaks the entropy limitation of the tag space. ClusterTag has been implemented as an independent memory allocator that seamlessly integrates with tag-based sanitizers such as HWASan, and maintains comparable performance overhead (within 1%) at various randomization densities. Security evaluations on the Juliet dataset indicate that ClusterTag exhibits deterministic results across 500 repeated tests (5,652 reported and 1,530 missed), while the existing three types of tag assignment strategies all exhibit probabilistic false negatives due to tag collisions. Quantitative analysis across three tag collision distance metrics-minimum, average, and unpredictability-demonstrates that ClusterTag achieves balanced improvements across all three, whereas prior tag assignment schemes (random, staggered, fixed) show significant trade-offs in at least one metric.