Memory Tagging and how it improves C/C++ memory safety
arxiv.org
arxiv.org
I'm not taking (yet) a position on the relative merits of the bounds-register based MPX approach versus the tagged pointer one presented here, but the comparison should at least be made if at least only to explain why MT would be successful in contrast (MPX has hardly taken the world by storm).
Also, since they appear to be positioning this as something that could be fast enough to run in production (with hardware assist), they should at least take a shot at analyzing the attack surface presented by the probabilistic protection: a figure like 99.6% chance of catching a rogue access makes sense for testing scenarios, but if the adversary is an attacker, can they manipulate those odds to their advantage? The exact tag allocation mechanism becomes pretty important in this case.
See also: https://illumos.org/man/umem_debug
Which was nice to be able to observe, because the code didn't need to do many small allocations.
Also, check how much free ram your computer has when running with ASan. It may be running out of RAM, and e.g. spending a lot of time looking for other memory to free, or even swapping.
https://docs.microsoft.com/en-us/windows-hardware/drivers/de...
https://en.wikipedia.org/wiki/Electric_Fence
I think he might have developed that while at Pixar.
https://stackoverflow.com/a/370362/1424242
Interesting note that with this method in the paper, "Temporal and spatial bugs are detected probabilistically" - and it depends on how many tag bits you choose, which trades addressable space for more tags (higher probability of catching errors.)
> Memory safety in C and C++ remains largely unresolved.
I read the paper's description, and still don't quite understand exactly what they mean by "memory safety". This is not referring to safer programming practices like using the STL with iterators, correct?
BSD's malloc.conf framework does something similar. Though they've managed to be incompatible with one another.
On FreeBSD, activating junking (default off) will fill allocated memory with 0xa5 and deallocated memory with 0x5a.
On OpenBSD, allocated memory uses 0xdb, deallocated memory uses 0xdf, junking is default-enabled for "small chunks" & the start of freed pages (which are also checked for write-after-free on a small delay).
I would assume it's referring to some kind of actual guarantee, which STL doesn't provide even in idiomatic use, due to things like iterator invalidation or subtly broken use of references.
Memory safety generally refers to treating each region of memory as it's expected type, not over-writing or over-reading the bounds of allocated region, not reading unitialized or freed memory, and so on.
It's a correctness problem that often ends up in the news since it's usually unchecked in C and C++ meaning that errors of that type don't necessarily result in predictable exceptions or process termination, but rather all sorts of exciting exploits.
Many higher-level languages have no similar memory safety issue (absent bugs in their implementations) since they exclude features that could result in the above problems, and include explicit runtime checks in places where the compiler or runtime cannot prove that an access is safe.
https://en.wikipedia.org/wiki/Magic_number_(programming)#Mag...
Burroughs Architecture https://www.smecc.org/The%20Architecture%20%20of%20the%20Bur...
Capability-based Computer Systems (book) https://homes.cs.washington.edu/~levy/capabook/
Some new ones using a range of techniques:
SAFE Architecture http://www.crash-safe.org/papers.html
CHERI Architecture http://www.cl.cam.ac.uk/research/security/ctsrd/cheri/
Note: CHERI runs a modified version of FreeBSD on a FPGA board. Quite practical if it can handle that!
Watchdog Architecture https://www.cs.rutgers.edu/~santosh.nagarakatte/softbound/
Hardware-assisted Secure Allocator http://jin.ece.ufl.edu/papers/HASP17.pdf
However by the late 1970s it had been figured out that you could do some of these tricks without dedicated hardware support (mask-boxing of integers, for example on processors that ignored unaligned access you could use the least significant bits for tagging; on ones with address spaces less than the word length you could often do the same with the upper bits). These bits could be used by GC and/or for fast type systems, and by the mid 1980s had pretty much wiped out the advantage of dedicated hardware for Lisp implementations (the lispms started out much faster at tag manipulation but the weight of work on the general purpose machines caused the latter to get better (and cheaper) much faster).
The bigger advantage of hardware support IMHO is the security opportunity for capability management.
That said, I feel like the paper is missing a few details on the implementation. They give the example of a segment size of 64 bytes, and a tag size of 4 bits. Obviously, that doesn't even cover a full 4K page of data. So I presume the segments must repeat, meaning after segment 15 there is another segment 0. This seems to fit into their probability description (An OOB access might hit the next segment with the same ID, but it's unlikely).
The approach still seems a bit limited though. I would assume objects larger then 64 bytes would have to be untagged, since normally you would access them via offsetting from the same base pointer, and that base pointer would always have the same tag. But also, a big problem is that most OOB accesses are likely to hit the region of memory just past the allocated region. So with larger segments you are likely to miss many of these OOB accesses since the tag is still correct.
All that said, I don't think this idea is mentioned in the paper, but you could also vary the size of every set of tags in the address space. So have, say, 20 sets of tags for 64-byte regions, then after that 20 sets of tags for 1024-byte regions, and etc. So there is a mix of small and large regions. There's no guarantee you would have the right amount of different-sized regions, but you can always fall-back to using untagged if you need so it is not a disaster if the numbers are a little off (Besides, of course, the fact that untagged memory loses the security advantages of the tagged memory.
It's sort of the other way around. Replacing "tags" with "colors" since somehow it seems a bit more intuitive, the allocator itself just "colors" different allocations with a different color, rather than splitting up the address space beforehand. The returned pointers are also colored and a fault occurs if any pointer is used to access memory of a different color.
> Obviously, that doesn't even cover a full 4K page of data. So I presume the segments must repeat.
Definitely - every color will be used many times, so they only probabilistically catch any fault, based on mostly the total number of colors (as long as the colors were randomized from run to run it seems like any fault would be quickly caught with a high probability). They mention in in the paper improvements such as ensuring that adjacent regions always have different colors so that linear overruns are caught with 100% probability.
> I would assume objects larger then 64 bytes would have to be untagged, since normally you would access them via offsetting from the same base pointer, and that base pointer would always have the same tag.
Not at all. The 64-bytes is only the granularity of the colors (actually they suggest 16 bytes is a better option): but an arbitrarily large region can have the same color.
Most of the rest of your post follows I think from that misunderstanding: there is no need to change the color every 16 or 64 bytes (they call this quantity TG) - you color the whole region with the same color. The TG value is just the granularity at which it can change, so it's a tradeoff between overhead for small allocations (favoring smaller TG) and total tag storage cost (favoring larger TG).
Now, if that is the case it complicates the setup a fair amount, since now you do need a global 'page-table' like structure holding this information that the allocator configures. And from reading the paper, don't they intended for the kernel to do this checking as well on userspace pointers, indicating the kernel also needs access to this information? It's doable, and better overall, but more complicated.
you can remove the restriction on the number of the colors by using valid upper virtual memory bits to denote type (bibop), as long as you know that the kernel hasnt put anything else there. maybe thats the kernel interaction you were thinking of?
Does not currently detect when the kernel accesses invalid user-space memory
With the software only solution, it's essentially just a variation on ASAN: with the trick that you use some pointer bits to additionally detect some cases that ASAN can't (because ASAN doesn't care about the origin/formation of the pointer: only whether the access is allowed).
Yeah they don't really get into how the shadow memory is managed. If you only had limited or no hardware support, it seems like it would be tricky, especially when you are arbitrarily mapping various chunks of the address space. The ideal for performance is that there is some straightforward relationship between a pointed-to region and the associated tag bits, e.g., just shift the pointer down by lg(TG) bits and then index into a single contiguous region which stores the tag bits, pointed to by some global.
That avoids the need to have any kind of page-table like structure, but it would waste a lot of virtual address space if the range of the pointers was very large or very sparse.
If you had hardware support though, maybe this problem goes away: the hardware could store the bits in "holes" right alongside the actual memory, as how ECC works (they suggest SPARC is doing this), or they could include the information in the TLB alongside the regular mappings (I guess this would need kernel support too).
I didn't see much about kernel-side checks in the paper? Maybe I missed it. The kernel already checks that user pointers are valid in the context of the process that provided them, but of course that is a very coarse check (can the user process as a whole read/write here?), and could still violate semantic memory safety of the process depending on what was passed.
Not if your segments/tags are static and defined beforehand, which is what I thought that were going for (Since that doesn't require any extra memory). But obviously that approach is pretty limited, which was my thinking.
> Yeah they don't really get into how the shadow memory is managed. If you only had limited or no hardware support, it seems like it would be tricky, especially when you are arbitrarily mapping various chunks of the address space. The ideal for performance is that there is some straightforward relationship between a pointed-to region and the associated tag bits, e.g., just shift the pointer down by lg(TG) bits and then index into a single contiguous region which stores the tag bits, pointed to by some global.
This is exactly what I'm thinking as well. If the platform has paging support, in theory this is cheaper then it seems because (besides using up tons of virtual memory) the array can be sparsely allocated, with only the regions actually in used taking up physical memory. But 64bytes is still really coarse, it might be necessary to use a multi-level approach to make the size a bit saner. But since it is just virtual memory, depending on the architecture it may not matter.
Storing it in the page table mappings themselves is an interesting idea. Of course, some architectures have more 'free' space in there then others. And at that point you're talking about likely 4K granularity, not 64 bytes. Still better then nothing of course, but it would definitely decrease the effectiveness for smaller objects.
> I didn't see much about kernel-side checks in the paper? Maybe I missed it. The kernel already checks that user pointers are valid in the context of the process that provided them, but of course that is a very coarse check (can the user process as a whole read/write here?), and could still violate semantic memory safety of the process depending on what was passed.
Someone else asked about this as well, it seems I was led astray. The paper has this line about ASAN:
Does not currently detect when the kernel accesses invalid user-space memory
Yes exactly. The worse case still seems like a doubling of (actual) memory use though: imagine a very sparsely accessed region of memory: even today each access would bring in a whole 4K page (on x86, for example), but now you'd bring in a whole 4K shadow page as well (yes, the access has to be really sparse to get this 1:1 ratio).
> And at that point you're talking about likely 4K granularity, not 64 bytes. Still better then nothing of course, but it would definitely decrease the effectiveness for smaller objects.
I think a 4K granularity is next to useless - you already get that from the hardware/OS paging support. If you want to detect problems on a 4K level, you only need to change your allocator to mmap in a page at a time, which you can even already do on some with tunable ones.
In theory you should be partially saved by the allocator, just because it is going to try and place as much stuff as it can into every page it allocates, as well as allocate multiple pages at once (So they all end-up in a row). An allocator that was aware of the 'shadow' pages should be able to allocate chunks of pages at once that correspond to a single 'shadow' page, ensuring you avoid creating tons of them. The higher alignment requirements mean more wasted memory though, meaning you need to allocate more pages and need then need more 'shadow' pages overall.
The paper suggests anywhere between 14% and 18% RAM overhead (discounting Android apps, which had a range from 6% to 42%) for 64 byte granularity, and that it actually goes down if you choose a smaller granularity like 16, due to the lower alignment requirement.
And of course, you're also talking about doubling memory accesses as well, assuming this is done in software. Every access has to first check the 'shadow' page. Unfortunately both of their implementations are at least partially hardware assisted, so I'm not sure you can use those numbers to just a pure CPU implementation, but they suggest around a 2x slowdown.
> I think a 4K granularity is next to useless - you already get that from the hardware/OS paging support. If you want to detect problems on a 4K level, you only need to change your allocator to mmap in a page at a time, which you can even already do on some with tunable ones.
I would agree. The tagging system can prevent a higher percentage of OOB accesses at the page level in theory, but considering the size of the address-space vs the number of allocations (assuming a 64-bit/48-bit address space) I think the likelihood of an OOB access actually hitting another separate allocation (assuming a mostly random placement) is already pretty low, so the tagging system would make it lower (You now have to hit a random allocation with the correct tag) but not significantly lower then before, and at the cost of performance.