9 ms·

The Arm64 memory tagging extension in Linux

85 points by clktmr 6y ago

londons_explore 6y ago
How does this impact software that does memory pointer comparisons? Eg. Store pointers to all these objects into a std::set? The memory tag will now form part of the keys to this set, and would affect iteration order etc... It could cause breakage in existing applications.
- flohofwoe 6y ago
  Memory allocators are already returning more or less "random" pointers, so using pointers for sorting is already a bad idea. Even using pointers for equality-comparison isn't usually a good idea because the same memory location might be reused when the allocator recycles memory (those tags could actually help with making such "recycled" pointers unique over time).
  - sherincall 6y ago
    Be that as it may, existing software that used to work will no longer work, and the developers might not be around/able to fix it. There are also cases of custom suballocators or arrays of objects - Looking at an address makes it possibly to figure out which array it belongs to. This code would break. Granted, it would still be possible to do all this if you just mask off the tag bits, but it requires a software change.
    - pm215 6y ago
      The "suballocate out of some arrays" code should not break, because the whole array would be allocated at once and so would have the same tag for the whole range. Code that does a simple "is this pointer value inside the "array_base + size" range" continues to work, because array_base has whatever tag malloc() handed out for that array, and so do the pointer values that the suballocator handed out. I think for MTE to break your code you would have to be doing some pretty weird stuff with pointer arithmetic (beyond just the usual "technically maybe this is undefined behaviour but it works" level stuff). It's always the case that some software that does things that are not valid-by-the-language-standard might break if run on a newer version of the OS or a newer system library version (remember the big flap about glibc memcpy() changing its behaviour when called for overlapping regions?). You don't want to break lots of software gratuitously, but sometimes the tradeoff is worth making.
  - jackewiehose 6y ago
    Using pointers for sorting is fine as long as you don't care about the order (parent referenced std::set and it's not uncommon to use a set of pointers if you just want to store some objects). Likewise it's fine to use pointers for equality-comparisons as long as the pointer is valid (of course you have to dismiss the pointer when the memory is freed). I'm pretty sure this memory extension doesn't affect uniqueness of pointers... that would indeed break a lot of software ;-)
    - flohofwoe 6y ago
      > uniqueness of pointers... What I mean is for example: you get a pointer by allocating memory, then free that memory, then you allocate again and get a pointer to the same memory location. Without a tag those two pointers would be equal, even though they come from separate memory allocations. This can be a source of bugs if the pointer is also used as some sort of object id, and I know that at least I stumbled over this embarrassing problem more than once in C++ until I switched to tagged handles :)
      - jackewiehose 6y ago
        You can use the pointer as an object id, but only for living objects. The pointer becomes invalid the moment the memory is freed. Your bug was that you used an invalid pointer.
        Matt3o12_ 6y ago
        But doesn't this feature exactly help with this bug? Two memory allocations should now return different pointers (because the MTE nibble is different) therefore the comparision should fail. Unless ofcourse the application was using this undefined behavior (which would be very buggy since malloc can randomly refuse to reuse the same address even though it was freed and therefore create extremely hard and difficult to track bugs).
        flohofwoe 6y ago
        > Your bug was that you used an invalid pointer. Exactly, but just declaring that a pointer is "invalid" doesn't help much with debugging such dangling pointer problems, while tagged pointers do. It's not like an "invalid pointer" is any different from a "valid pointer" when you look at it. With the extra tag bits, an invalid pointer can actually be identified as such.
- enedil 6y ago
  Comparing pointers not coming from the same allocation is undefined behaviour per C++ standard.
  - gpderetta 6y ago
    ... unless you use std::less and friends which guarantees an unspecified total order among all pointers of the same type. Std::set uses it of course.
londons_explore 6y ago
Where are these keys stored? A 4 bit key for each 16 byte granule of memory in the system sounds substantial. Does the Linux kernel have to give the CPU a memory region to keep those mappings?
- dan-robertson 6y ago
  The keys are stored in the bottom nibble of the top byte of pointers (I.e. bits 56-59)
  - londons_explore 6y ago
    Yes, but they also need to be stored somewhere else for the CPU to compare them against something... Where else are they stored...
    - Liquid_Fire 6y ago
      It's implementation defined (by the hardware). They could be stored in a reserved part of the RAM, or you could build special RAM that can store the extra bits alongside the data, or any other compatible solution.
londons_explore 6y ago
Random read and write of a big memory region could now presumably cause double the number of DRAM accesses, and half the performance, since the tag mapping will need to be read in addition to the actual data. If the read of a memory address could have side effects (as is common with memory mapped hardware), does the hardware give guarantees that the tag will be checked before the memory is read or written? If so, that'll be an even bigger performance hit...
- deleted 6y ago
  [deleted]
- deleted 6y ago
  [deleted]
- bitwize 6y ago
  It seems that the tag mappings will need to live in separate physical RAM, so that info could be pulled from the tagmap RAM chips at the same time as the data is pulled from the data RAM chips. Using multiple RAM chips to increase throughput is an old computer engineering technique; it was, for instance, the entire justification for planar graphics modes in early graphics hardware.
- Retr0spectrum 6y ago
  You're overlooking a) existing page table lookup overhead b) hierarchical caching.
londons_explore 6y ago
4 bit keys seems a bit limiting... I could imagine lots of scenarios where a 1 in 16 chance of an exploit succeeding is still a big issue...
- flohofwoe 6y ago
  IMHO it's less of a security feature, and more of a debugging aid (the overlap with security is when a failed check causes program termination). You might get more fine-grained overflow checks (vs guard pages), or dangling pointer checks (depending on how that key is stored, e.g. more than one key per memory page?). It's faster then doing the same in code (e.g. via 'tagged handles': https://floooh.github.io/2018/06/17/handles-vs-pointers.html https://floooh.github.io/2018/06/17/handles-vs-pointers.html), or memory debugging tools like Valgrind or clang ASAN (and unlike Valgrind or ASAN, the checks are always enabled, also in the "release version").
- robocat 6y ago
  In the most extremely sensitive environments: 1. It still helps with defence in depth 2. The threat of detection prevents attackers that need 100% stealth 3. Failures are likely to be detected which is still valuable as you can now mitigate damage 4. Failures are likely to be detected which helps get software faults fixed - which allows the ecology of security to improve over time
londons_explore 6y ago
It's a shame we're using the top of pointers for other data... It's almost as if we didn't learn from the "3gb memory hole", the "gate a20 memory limit", and countless other times when using special address bits came back to bite system designers as RAM got bigger...
- flohofwoe 6y ago
  Is this really still a problem with virtual memory management? The virtual address space size could be a property of the process (e.g. 48 bits vs the full 64 bits). The vast majority of applications today doesn't even need more than 32-bits of address space and could use the top 32-bits for something else if the memory mapping hardware ignores the unused bits).
- five-robert 6y ago
  2^48 == 256TB. Anyone needs more than 256 Terabytes of RAM?
  - tpxl 6y ago
    I am flirting with the idea of having 1TB of RAM on my servers as a small start-up. Having 256TB in 20 years seems reasonable.
    - bitwize 6y ago
      You're gonna need at least that much to run the Electron apps of 20 years from now...
    - rbanffy 6y ago
      A 128-bit CPU is not something I'd find outlandish in 20 years. OTOH, I was reading my e-mail on a 64-bit workstation (largely by accident, but still). In any case, I'd be quite surprised to see a 64-bit CPU doing such heavy lifting in 2040.
  - throwaway2048 6y ago
    It ought to be enough for anyone
jpcooper 6y ago
So a key is stored in the unused portion of memory pointers which should match the key associated to the memory it points to. I couldn’t figure out from the article where the key is stored in the corresponding memory. Can anyone explain?
- Symmetry 6y ago
  I'd assume the key is stored in the hardware memory translation structures like the TLB.
  - rjsw 6y ago
    It doesn't look like it to me. I did propose storing type values in a TLB a long time ago but haven't run any simulations for it. Had started building some hardware to do type checking on an Atari ST but didn't finish it.
- pm215 6y ago
  mwsealey's comment on the LWN article (in response to somebody asking that question there) has a good explanation of it. Basically exactly where the keys are stored is up to the implementation, but one reasonable implementation is for the memory controller to put them in the top part of the system DRAM (which is then not made available as 'normal' RAM). Architecturally the allocation tag space is entirely separate from system memory, though, and the only way to get at it is with the provided instructions for reading/writing tags, so any particular implementation can put any kind of storage it likes underneath. (A software model, for instance, might just allocate a separate lump of host RAM for storing the tags. QEMU's MTE emulation does that.)
  - jpcooper 6y ago
    Thanks for the explanation.
cesaref 6y ago
Not sure if this has been mentioned, but this exact technique (storing extra data in addresses) was used in the early days of the MacOS, with 24 bits for the address, and 8 bits for extra info (not sure if I can remember exactly what they were for). The 68000 only had 24 address lines after all. This allowed a maximum of 16Mb of RAM which was of course far more than would ever be in a computer... By the time the Mac II came out (68020 with 32 bit address bus), it was apparent that this was going to be an issue, and there was an effort to remove this logic. Those early machines were a combination of ROM and loaded OSes, so there was an effort to clean the code for both the distributed OS and the stuff included in the ROMs of the machines. I think if memory serves the Mac IIcx from around '89 or so was the first machine with 32 bit clean roms, and with the right OS version you were good for >16mb of RAM. I've also got a hazy memory of some architecture (i'm going to guess DEC Alpha) which only read from 32 bit boundaries, and where the bottom 2 bits of the address were masked out, so you could store data there too... Anyhow, the real take home from all that was that misusing addresses to store additional information, which might seem like a clever trick is likely to bite you at some point in the future.
- rjsw 6y ago
  The Mac IIci was the first 32 bit clean machine. Plenty of dynamically typed languages have used the bottom bits in an address to store tags. You have two available on a 32 bit machine, three on 64 bit. The SPARCv7 has instructions that will do arithmetic on tagged values.
  - jacobush 6y ago
    AmigaBASIC
- crocktucker 6y ago
  " ... if memory serves ... ", well done.
- Someone 6y ago
  The extra bits stored flags that indicated whether handles were movable, could be purged at will, or came from a resource (on disk) IIRC Excel went a bit further by using the leftover bits and even bit(s) starting at bit 24. That worked until hardware stopped wrapping around memory. Apple created a launch error “program had special memory requirements” which actually meant “this is Excel version so-and-so”. And yes, that can bite you in the future, but the gains today can (appear to) outweigh that. It also is perfectly valid when you control both the side that determines the constraints and the side that runs extremely close to them. For example, Cocoa’s tagged pointers (https://www.mikeash.com/pyblog/friday-qa-2012-07-27-lets-build-tagged-pointers.html https://www.mikeash.com/pyblog/friday-qa-2012-07-27-lets-bui...) are fine, given that Apple both controlled the memory allocator and the library assuming it aligned allocations (they also are safer in that they won’t try to read from addresses that don’t point to valid memory. That’s essential for their use)
swills 6y ago
Is this related to the CHERI stuff? https://vimeo.com/366246134 https://vimeo.com/366246134 https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/ https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/
- saagarjha 6y ago
  It’s similar, but CHERI provides much stronger guarantees. (The ARM implementation will use 128-bit pointers, with the top half being used to store much more granular keys.)
  - cmarinas 6y ago
    CHERI provides spatial protection and is very strong at this but does not handle temporal protection well (use-after-free for example). Once a pointer is given to another code entity/compartment it is hard to revoke the permission since that's tied to the (capability) pointer itself, not the memory it points to. There are workarounds but not that nice. MTE, OTOH, was specifically designed for detecting temporal bugs. For example, a freed object has the allocation tag (stored in memory) changed by the heap allocator so that the original pointer (with the original tag) can no longer access it. Of course, the trade-off is the 4 bits per 16-byte granule that need to be stored somewhere and the probabilistic nature (1 in 16 chance of hitting it). But I think CHERI and MTE would complement each other nicely.
znpy 6y ago
isn't like, memory tagging explicitly forbidden in x86-64 ? iirc it was used in lisp compilers/interpreters to speed up object unboxing (as in answering the question: "what class does the object pointed by this pointer belong to?")
- colejohnson66 6y ago
  Correct. x86-64 mandates “canonical” addresses where all the upper bits must be the same in order to dereference a pointer.[0] So on a processor with 48 physical address lines, the upper 16 must be either all set or all unset. This is obviously to prevent people using those upper bits to store extra data. Of course, this doesn’t stop you from being able to[a], it just makes it harder. [a]: The processor doesn’t know the “type” of a register’s value; It’s just bits. It could be a pointer, integer, floating point, etc. until you tell the processor to do something with it. So one could obviously use those extra bits to store data, then when a dereference is needed, store those bits in another register, dereference, then put the bits back. But that’s a lot of work to save a byte or two. [0]: Intel SDM Volume 1 §3.3.7.1: > In 64-bit mode, an address is considered to be in canonical form if address bits 63 through to the most-significant implemented bit by the microarchitecture are set to either all ones or all zeros.
  - staticassertion 6y ago
    > But that’s a lot of work to save a byte or two. Is it? It's something like two xors on a register. If that's a byte or two per pointer (ie: it's pointer metadata that you'd have to store anyway, which I assume is the use case) that's actually a pretty significant win, and could help reduce cache pressure, thereby buying you back the performance (and then some). Addresses are also XOR'd all the time with a secret as a mitigation, I don't know that there's much of an impact at all.
- imglorp 6y ago
  Absolutely, or in the low bits of word aligned pointers as someone else mentioned above. Emacs Lisp is an example; here's its tagging apparatus. https://git.savannah.gnu.org/cgit/emacs.git/tree/src/lisp.h#n207 https://git.savannah.gnu.org/cgit/emacs.git/tree/src/lisp.h#...
shard 6y ago
Here is a Google engineer explaining how memory tagging extension works in more detail in a white paper. According to the paper, about 2/3 of all CVEs are memory safety bugs, and memory tagging will help with catching undiscovered ones. https://www.usenix.org/system/files/login/articles/login_summer19_03_serebryany.pdf https://www.usenix.org/system/files/login/articles/login_sum...
- pjmlp 6y ago
  It does, as proven by Solaris on SPARC ADI, a similar technic with almost one decade of use by now.
lsllc 6y ago
This sounds a bit like the pkey API and MPK (Memory Protection Keys) on more recent Intel processors. https://www.kernel.org/doc/html/latest/core-api/protection-keys.html https://www.kernel.org/doc/html/latest/core-api/protection-k...
pjmlp 6y ago
They are ignoring Android here as customer of the Linux kernel. Google plans to eventually make MTE a compulsory feature. https://source.android.com/devices/tech/debug/tagged-pointers?hl=en https://source.android.com/devices/tech/debug/tagged-pointer...

85 points by clktmr 6y ago

How does this impact software that does memory pointer comparisons? Eg. Store pointers to all these objects into a std::set? The memory tag will now form part of the keys to this set, and would affect iteration order etc... It could cause breakage in existing applications.

flohofwoe 6y ago
Memory allocators are already returning more or less "random" pointers, so using pointers for sorting is already a bad idea. Even using pointers for equality-comparison isn't usually a good idea because the same memory location might be reused when the allocator recycles memory (those tags could actually help with making such "recycled" pointers unique over time).
- sherincall 6y ago
  Be that as it may, existing software that used to work will no longer work, and the developers might not be around/able to fix it. There are also cases of custom suballocators or arrays of objects - Looking at an address makes it possibly to figure out which array it belongs to. This code would break. Granted, it would still be possible to do all this if you just mask off the tag bits, but it requires a software change.
  - pm215 6y ago
    The "suballocate out of some arrays" code should not break, because the whole array would be allocated at once and so would have the same tag for the whole range. Code that does a simple "is this pointer value inside the "array_base + size" range" continues to work, because array_base has whatever tag malloc() handed out for that array, and so do the pointer values that the suballocator handed out. I think for MTE to break your code you would have to be doing some pretty weird stuff with pointer arithmetic (beyond just the usual "technically maybe this is undefined behaviour but it works" level stuff). It's always the case that some software that does things that are not valid-by-the-language-standard might break if run on a newer version of the OS or a newer system library version (remember the big flap about glibc memcpy() changing its behaviour when called for overlapping regions?). You don't want to break lots of software gratuitously, but sometimes the tradeoff is worth making.
- jackewiehose 6y ago
  Using pointers for sorting is fine as long as you don't care about the order (parent referenced std::set and it's not uncommon to use a set of pointers if you just want to store some objects). Likewise it's fine to use pointers for equality-comparisons as long as the pointer is valid (of course you have to dismiss the pointer when the memory is freed). I'm pretty sure this memory extension doesn't affect uniqueness of pointers... that would indeed break a lot of software ;-)
  - flohofwoe 6y ago
    > uniqueness of pointers... What I mean is for example: you get a pointer by allocating memory, then free that memory, then you allocate again and get a pointer to the same memory location. Without a tag those two pointers would be equal, even though they come from separate memory allocations. This can be a source of bugs if the pointer is also used as some sort of object id, and I know that at least I stumbled over this embarrassing problem more than once in C++ until I switched to tagged handles :)
    - jackewiehose 6y ago
      You can use the pointer as an object id, but only for living objects. The pointer becomes invalid the moment the memory is freed. Your bug was that you used an invalid pointer.
      - Matt3o12_ 6y ago
        But doesn't this feature exactly help with this bug? Two memory allocations should now return different pointers (because the MTE nibble is different) therefore the comparision should fail. Unless ofcourse the application was using this undefined behavior (which would be very buggy since malloc can randomly refuse to reuse the same address even though it was freed and therefore create extremely hard and difficult to track bugs).
      - flohofwoe 6y ago
        > Your bug was that you used an invalid pointer. Exactly, but just declaring that a pointer is "invalid" doesn't help much with debugging such dangling pointer problems, while tagged pointers do. It's not like an "invalid pointer" is any different from a "valid pointer" when you look at it. With the extra tag bits, an invalid pointer can actually be identified as such.
enedil 6y ago
Comparing pointers not coming from the same allocation is undefined behaviour per C++ standard.
- gpderetta 6y ago
  ... unless you use std::less and friends which guarantees an unspecified total order among all pointers of the same type. Std::set uses it of course.

londons_explore 6y ago

Where are these keys stored? A 4 bit key for each 16 byte granule of memory in the system sounds substantial. Does the Linux kernel have to give the CPU a memory region to keep those mappings?

dan-robertson 6y ago
The keys are stored in the bottom nibble of the top byte of pointers (I.e. bits 56-59)
- londons_explore 6y ago
  Yes, but they also need to be stored somewhere else for the CPU to compare them against something... Where else are they stored...
  - Liquid_Fire 6y ago
    It's implementation defined (by the hardware). They could be stored in a reserved part of the RAM, or you could build special RAM that can store the extra bits alongside the data, or any other compatible solution.

londons_explore 6y ago

Random read and write of a big memory region could now presumably cause double the number of DRAM accesses, and half the performance, since the tag mapping will need to be read in addition to the actual data. If the read of a memory address could have side effects (as is common with memory mapped hardware), does the hardware give guarantees that the tag will be checked before the memory is read or written? If so, that'll be an even bigger performance hit...

deleted 6y ago
[deleted]
deleted 6y ago
[deleted]
bitwize 6y ago
It seems that the tag mappings will need to live in separate physical RAM, so that info could be pulled from the tagmap RAM chips at the same time as the data is pulled from the data RAM chips. Using multiple RAM chips to increase throughput is an old computer engineering technique; it was, for instance, the entire justification for planar graphics modes in early graphics hardware.
Retr0spectrum 6y ago
You're overlooking a) existing page table lookup overhead b) hierarchical caching.

londons_explore 6y ago

4 bit keys seems a bit limiting... I could imagine lots of scenarios where a 1 in 16 chance of an exploit succeeding is still a big issue...

flohofwoe 6y ago
IMHO it's less of a security feature, and more of a debugging aid (the overlap with security is when a failed check causes program termination). You might get more fine-grained overflow checks (vs guard pages), or dangling pointer checks (depending on how that key is stored, e.g. more than one key per memory page?). It's faster then doing the same in code (e.g. via 'tagged handles': https://floooh.github.io/2018/06/17/handles-vs-pointers.html https://floooh.github.io/2018/06/17/handles-vs-pointers.html), or memory debugging tools like Valgrind or clang ASAN (and unlike Valgrind or ASAN, the checks are always enabled, also in the "release version").
robocat 6y ago
In the most extremely sensitive environments: 1. It still helps with defence in depth 2. The threat of detection prevents attackers that need 100% stealth 3. Failures are likely to be detected which is still valuable as you can now mitigate damage 4. Failures are likely to be detected which helps get software faults fixed - which allows the ecology of security to improve over time

londons_explore 6y ago

It's a shame we're using the top of pointers for other data... It's almost as if we didn't learn from the "3gb memory hole", the "gate a20 memory limit", and countless other times when using special address bits came back to bite system designers as RAM got bigger...

flohofwoe 6y ago
Is this really still a problem with virtual memory management? The virtual address space size could be a property of the process (e.g. 48 bits vs the full 64 bits). The vast majority of applications today doesn't even need more than 32-bits of address space and could use the top 32-bits for something else if the memory mapping hardware ignores the unused bits).
five-robert 6y ago
2^48 == 256TB. Anyone needs more than 256 Terabytes of RAM?
- tpxl 6y ago
  I am flirting with the idea of having 1TB of RAM on my servers as a small start-up. Having 256TB in 20 years seems reasonable.
  - bitwize 6y ago
    You're gonna need at least that much to run the Electron apps of 20 years from now...
  - rbanffy 6y ago
    A 128-bit CPU is not something I'd find outlandish in 20 years. OTOH, I was reading my e-mail on a 64-bit workstation (largely by accident, but still). In any case, I'd be quite surprised to see a 64-bit CPU doing such heavy lifting in 2040.
- throwaway2048 6y ago
  It ought to be enough for anyone

jpcooper 6y ago

So a key is stored in the unused portion of memory pointers which should match the key associated to the memory it points to. I couldn’t figure out from the article where the key is stored in the corresponding memory. Can anyone explain?

Symmetry 6y ago
I'd assume the key is stored in the hardware memory translation structures like the TLB.
- rjsw 6y ago
  It doesn't look like it to me. I did propose storing type values in a TLB a long time ago but haven't run any simulations for it. Had started building some hardware to do type checking on an Atari ST but didn't finish it.
pm215 6y ago
mwsealey's comment on the LWN article (in response to somebody asking that question there) has a good explanation of it. Basically exactly where the keys are stored is up to the implementation, but one reasonable implementation is for the memory controller to put them in the top part of the system DRAM (which is then not made available as 'normal' RAM). Architecturally the allocation tag space is entirely separate from system memory, though, and the only way to get at it is with the provided instructions for reading/writing tags, so any particular implementation can put any kind of storage it likes underneath. (A software model, for instance, might just allocate a separate lump of host RAM for storing the tags. QEMU's MTE emulation does that.)
- jpcooper 6y ago
  Thanks for the explanation.

cesaref 6y ago

Not sure if this has been mentioned, but this exact technique (storing extra data in addresses) was used in the early days of the MacOS, with 24 bits for the address, and 8 bits for extra info (not sure if I can remember exactly what they were for). The 68000 only had 24 address lines after all. This allowed a maximum of 16Mb of RAM which was of course far more than would ever be in a computer... By the time the Mac II came out (68020 with 32 bit address bus), it was apparent that this was going to be an issue, and there was an effort to remove this logic. Those early machines were a combination of ROM and loaded OSes, so there was an effort to clean the code for both the distributed OS and the stuff included in the ROMs of the machines. I think if memory serves the Mac IIcx from around '89 or so was the first machine with 32 bit clean roms, and with the right OS version you were good for >16mb of RAM. I've also got a hazy memory of some architecture (i'm going to guess DEC Alpha) which only read from 32 bit boundaries, and where the bottom 2 bits of the address were masked out, so you could store data there too... Anyhow, the real take home from all that was that misusing addresses to store additional information, which might seem like a clever trick is likely to bite you at some point in the future.

rjsw 6y ago
The Mac IIci was the first 32 bit clean machine. Plenty of dynamically typed languages have used the bottom bits in an address to store tags. You have two available on a 32 bit machine, three on 64 bit. The SPARCv7 has instructions that will do arithmetic on tagged values.
- jacobush 6y ago
  AmigaBASIC
crocktucker 6y ago
" ... if memory serves ... ", well done.
Someone 6y ago
The extra bits stored flags that indicated whether handles were movable, could be purged at will, or came from a resource (on disk) IIRC Excel went a bit further by using the leftover bits and even bit(s) starting at bit 24. That worked until hardware stopped wrapping around memory. Apple created a launch error “program had special memory requirements” which actually meant “this is Excel version so-and-so”. And yes, that can bite you in the future, but the gains today can (appear to) outweigh that. It also is perfectly valid when you control both the side that determines the constraints and the side that runs extremely close to them. For example, Cocoa’s tagged pointers (https://www.mikeash.com/pyblog/friday-qa-2012-07-27-lets-build-tagged-pointers.html https://www.mikeash.com/pyblog/friday-qa-2012-07-27-lets-bui...) are fine, given that Apple both controlled the memory allocator and the library assuming it aligned allocations (they also are safer in that they won’t try to read from addresses that don’t point to valid memory. That’s essential for their use)

swills 6y ago

Is this related to the CHERI stuff? https://vimeo.com/366246134 https://vimeo.com/366246134 https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/ https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/

saagarjha 6y ago
It’s similar, but CHERI provides much stronger guarantees. (The ARM implementation will use 128-bit pointers, with the top half being used to store much more granular keys.)
- cmarinas 6y ago
  CHERI provides spatial protection and is very strong at this but does not handle temporal protection well (use-after-free for example). Once a pointer is given to another code entity/compartment it is hard to revoke the permission since that's tied to the (capability) pointer itself, not the memory it points to. There are workarounds but not that nice. MTE, OTOH, was specifically designed for detecting temporal bugs. For example, a freed object has the allocation tag (stored in memory) changed by the heap allocator so that the original pointer (with the original tag) can no longer access it. Of course, the trade-off is the 4 bits per 16-byte granule that need to be stored somewhere and the probabilistic nature (1 in 16 chance of hitting it). But I think CHERI and MTE would complement each other nicely.

znpy 6y ago

isn't like, memory tagging explicitly forbidden in x86-64 ? iirc it was used in lisp compilers/interpreters to speed up object unboxing (as in answering the question: "what class does the object pointed by this pointer belong to?")

colejohnson66 6y ago
Correct. x86-64 mandates “canonical” addresses where all the upper bits must be the same in order to dereference a pointer.[0] So on a processor with 48 physical address lines, the upper 16 must be either all set or all unset. This is obviously to prevent people using those upper bits to store extra data. Of course, this doesn’t stop you from being able to[a], it just makes it harder. [a]: The processor doesn’t know the “type” of a register’s value; It’s just bits. It could be a pointer, integer, floating point, etc. until you tell the processor to do something with it. So one could obviously use those extra bits to store data, then when a dereference is needed, store those bits in another register, dereference, then put the bits back. But that’s a lot of work to save a byte or two. [0]: Intel SDM Volume 1 §3.3.7.1: > In 64-bit mode, an address is considered to be in canonical form if address bits 63 through to the most-significant implemented bit by the microarchitecture are set to either all ones or all zeros.
- staticassertion 6y ago
  > But that’s a lot of work to save a byte or two. Is it? It's something like two xors on a register. If that's a byte or two per pointer (ie: it's pointer metadata that you'd have to store anyway, which I assume is the use case) that's actually a pretty significant win, and could help reduce cache pressure, thereby buying you back the performance (and then some). Addresses are also XOR'd all the time with a secret as a mitigation, I don't know that there's much of an impact at all.
imglorp 6y ago
Absolutely, or in the low bits of word aligned pointers as someone else mentioned above. Emacs Lisp is an example; here's its tagging apparatus. https://git.savannah.gnu.org/cgit/emacs.git/tree/src/lisp.h#n207 https://git.savannah.gnu.org/cgit/emacs.git/tree/src/lisp.h#...

shard 6y ago

Here is a Google engineer explaining how memory tagging extension works in more detail in a white paper. According to the paper, about 2/3 of all CVEs are memory safety bugs, and memory tagging will help with catching undiscovered ones. https://www.usenix.org/system/files/login/articles/login_summer19_03_serebryany.pdf https://www.usenix.org/system/files/login/articles/login_sum...

pjmlp 6y ago
It does, as proven by Solaris on SPARC ADI, a similar technic with almost one decade of use by now.

lsllc 6y ago

This sounds a bit like the pkey API and MPK (Memory Protection Keys) on more recent Intel processors. https://www.kernel.org/doc/html/latest/core-api/protection-keys.html https://www.kernel.org/doc/html/latest/core-api/protection-k...

pjmlp 6y ago

They are ignoring Android here as customer of the Linux kernel. Google plans to eventually make MTE a compulsory feature. https://source.android.com/devices/tech/debug/tagged-pointers?hl=en https://source.android.com/devices/tech/debug/tagged-pointer...