Root Cause
Memory/Pointer Tagging In IsoAlloc
November 25th, 2022
Chris Rohlf
In April of 2022 I added an experimental feature to IsoAlloc that implemented a memory tagging model. The idea is very similar to Chrome's MTECheckedPtr which itself is very similar to ARM's upcoming Memory Tagging Extension (MTE) due in ARM v8.5-A.
ARM MTE is a hardware based solution for detecting both spatial and temporal memory safety issues in software with little to no overhead. It works by using the Top Byte Ignore (TBI) feature to transparently tag pointers with metadata or a 'tag'. With MTE this tag is transparently added, verified, and removed from pointers in hardware. MTE errors can be configured to be delivered synchronously or asynchronously.
Pointer tagging as implemented here in IsoAlloc is conceptually very similar, except these operations are implemented in software. There are of course limitations to the IsoAlloc implementation such as performance overhead and less flexibility in how errors are delivered in comparison to MTE. But it is a usable software alternative for systems without TBI or MTE like x86_64. If your target system has TBI you can still use IsoAlloc pointer tagging as described here.
Memory Allocator Support
Implementing a pointer tagging scheme in software is relatively straightforward. On 64 bit architectures such as aarch64 and x86_64 there is only 48 bits of addressable virtual memory which means for canonical addresses (0-0x00007FFFFFFFFFFF) there are 16 unused bits in each pointer. Storing a random 1 byte value in those unused bytes is as simple as:
tagged_pointer = ((random_tag << 56) | raw_pointer);
Where things get more complex is once you want to verify that tag, remove it transparently, and dereference the pointer. Thats where the underlying memory allocator, and smart pointer templates are useful.
The memory allocator that manages memory chunks our tagged pointers point to can also manage the underlying tags throughout the chunks lifetime. The allocator is responsible for generating (and refreshing) the random tag, tagging the pointer, and verifying it anytime the pointer anytime it is dereferenced or when it is passed back into the allocator to functions like free().
Performing these steps in C every time we want to use the pointer is tedious and may require automated code modifications. C++ smart pointer templates can overload various operators to transparently perform the untagging and verification steps before dereferencing the pointer.
IsoAlloc Tagged Pointer Implementation
IsoAlloc has the concept of private zones. Private zone creation returns a handle that can be passed back into the allocator any time an allocation or free request is made. When MEMORY_TAGGING is enabled in the Makefile private zones support returning tagged pointers to chunks within those zones. If we look at private zone creation we can see how memory tagging affects the zone memory layout:
size_t tag_mapping_size = ROUND_UP_PAGE((new_zone->chunk_count * MEM_TAG_SIZE));
if(internal == false) {
total_size += (tag_mapping_size + g_page_size)
new_zone->tagged = true;
} else {
tag_mapping_size = 0;
}
In the code above we first determine how many pages we need to hold a tag for every chunk in the zone. This is easy to compute, each tag is 1 byte, each zone is 4mb total and is divided by the initial chunk size when it is created:
tag_mapping_size = tag_size * (4mb / chunk_size)
For example, a zone holding 128 byte chunks requires 32768 bytes to hold a tag for each chunk:
32768 = 1 * (4194304 / 128)
On most systems each page is 4k, we assume this is true for the remainder of this article. A zone holding 128 byte chunks has 32768 possible chunks which requires 8 pages to hold a tag for each chunk in the zone. The smaller the chunk size, the more pages we need to hold our tags. For chunks that are 1024 bytes or larger we only need a single page to hold all of our tags.
if(new_zone->tagged == true) {
create_guard_page(p + g_page_size + tag_mapping_size);
new_zone->user_pages_start = (p + g_page_size + tag_mapping_size + g_page_size);
uint64_t *_mtp = p + g_page_size;
/* (>> 3) == sizeof(uint64_t) == 8 */
uint64_t tms = tag_mapping_size >> 3;
/* Generate random tags */
for(uint64_t o = 0; o < tms; o++) {
_mtp[o] = us_rand_uint64(&_root->seed);
}
} else {
new_zone->user_pages_start = (p + g_page_size);
}
We can't store our tags in-line with our chunks, as this would leave them vulnerable to spatial memory safety vulnerabilities in adjacent chunks. We can mitigate this by storing our tags in pages separate from the chunks and computing their location based on the chunk offset from the zone base.
The code above declares a pointer, _mtp, just after the initial guard page, and then writes the random tags. Now when a caller invokes iso_alloc_from_zone_tagged we allocate a chunk from the zone normally, and then we call _tag_ptr before returning it.
INTERNAL_HIDDEN uint8_t _iso_alloc_get_mem_tag(void *p, iso_alloc_zone_t *zone) {
void *user_pages_start = UNMASK_USER_PTR(zone);
uint8_t *_mtp = (user_pages_start - g_page_size - ROUND_UP_PAGE(zone->chunk_count * MEM_TAG_SIZE));
const uint64_t chunk_offset = (uint64_t)(p - user_pages_start);
/* Ensure the pointer is a multiple of chunk size */
if(UNLIKELY((chunk_offset & (zone->chunk_size - 1)) != 0)) {
LOG_AND_ABORT("Chunk offset %d not an alignment of %d", chunk_offset, zone->chunk_size);
}
_mtp += (chunk_offset >> zone->chunk_size_pow2);
return *_mtp;
}
INTERNAL_HIDDEN void *_tag_ptr(void *p, iso_alloc_zone_t *zone) {
if(UNLIKELY(p == NULL || zone == NULL)) {
return NULL;
}
const uint64_t tag = _iso_alloc_get_mem_tag(p, zone);
return (void *) ((tag << UNTAGGED_BITS) | (uintptr_t) p);
}
Using the functions above we can allocate a chunk of memory, tag the pointer to that chunk, and return the tagged pointer to the caller. But this isn't really useful until we attempt to use the pointer. In order to use the pointer we need to first remove the tag value, but simply removing the tag and returning the canonical pointer doesn't provide any security value. We need to first lookup what the allocator thinks the tag should be and attempt to remove it from the tagged pointer in such a way that if there is a mismatch we return a bad pointer and the program crashes.
INTERNAL_HIDDEN void *_untag_ptr(void *p, iso_alloc_zone_t *zone) {
if(UNLIKELY(p == NULL || zone == NULL)) {
return NULL;
}
void *untagged_p = (void *) ((uintptr_t) p & TAGGED_PTR_MASK);
const uint64_t tag = _iso_alloc_get_mem_tag(untagged_p, zone);
return (void *) ((tag << UNTAGGED_BITS) ^ (uintptr_t) p);
}
The code above shows how we retrieve the tag using _iso_alloc_get_mem_tag as before. But the line to remove the tag is slightly different. The function XORs the pointer by the tag value.
// _iso_alloc_get_mem_tag returns 0xed, the correct tag for the chunk
((0xed << 56) ^ 0xed000b8066c1a000) = 0xb8066c1a000
// An incorrect tag will result in an incorrect untagged pointer
((0xed << 56) ^ 0xab000b8066c1a000) = 0x46000b8066c1a000
If the tag in the tagged pointer is correct then the XOR operation sets those unused pointer bits to 0 and the canonical pointer is returned. But if the tag in the pointer is incorrect then a non-canonical, and incorrect, address will be returned which should result in the program crashing. All of these operations are relatively cheap to perform.
Memory allocations are requested frequently, and reusing tags can reduce our security guarantees. This is because there is no guarantee these tags won't be leaked into other data structures or spilled into registers. To mitigate this risk each time a chunk is free'd IsoAlloc will refresh it's memory tag so that when that chunk is reallocated it won't have the same value. At the same time this occurs IsoAlloc checks if the zone has seen %25 of its ZONE_ALLOC_RETIRE allocations. If this is true, and the zone has no current allocations, then every tag in the zone will be refreshed.
Example Usage
Using these primitive operations we can build a simple C++ smart pointer template that transparently tags, untags, and dereferences a tagged pointer. Below is an example IsoAllocPtr template. It's constructor takes a private zone handle, and an existing pointer to a chunk allocated from that zone, which it tags and stores as a member variable. It overloads a dereference operator so it can transparently untag and dereference the pointer. For TBI capable systems the iso_alloc_verify_ptr_tag function will verify the tag, and abort if it is incorrect. It does not return a pointer with the tag stripped like iso_alloc_untag_ptr does.
template <typename T>
class IsoAllocPtr {
public:
IsoAllocPtr(iso_alloc_zone_handle *handle, T *ptr) : eptr(nullptr), zone(handle) {
eptr = iso_alloc_tag_ptr((void *) ptr, zone);
}
T *operator->() {
T *p = reinterpret_cast<T *>(iso_alloc_untag_ptr(eptr, zone));
return p;
}
void *eptr;
iso_alloc_zone_handle *zone;
};
The IsoAllocPtr template is a very simple example of an abstraction you can build on top of the C APIs exposed by IsoAlloc for tagging and untagging pointers. Many kinds of models and object contracts can be constructed using the following C APIs:
// Allocates a chunk from zone and returns a tagged pointer void *iso_alloc_from_zone_tagged(iso_alloc_zone_handle *zone) // Tags a pointer from a private zone void *iso_alloc_tag_ptr(void *p, iso_alloc_zone_handle *zone) // Untags a pointer from a private zone void *iso_alloc_untag_ptr(void *p, iso_alloc_zone_handle *zone) // Retrieves the 1 byte tag for an untagged pointer uint8_t iso_alloc_get_mem_tag(void *p, iso_alloc_zone_handle *zone) // Verifies the tag on a tagged pointer, aborts if incorrect void iso_alloc_verify_ptr_tag(void *p, iso_alloc_zone_handle *zone)
You can find the IsoAlloc memory tagging unit tests for C++, C, and invariants.
The IsoAlloc memory tagging implementation will add performance overhead to both the allocation and free paths, but it can help catch bugs during fuzz testing, or introduce constraints around the exploitation of certain vulnerable code patterns.