4 ms·

Am I correct in thinking that this is a similar idea to page faults but per allocation rather than per process?

DSMan195276 9y ago
After skimming the paper, I think it's actually closer to segmentation. They just split the address space into X number of segments. The allocator then ensures every allocation lies completely within one of these segments and attaches that segment's ID to the returned pointer. Fundamentally, paging and segmentation are fairly similar though, so you're not wrong, there is just no concept of a 'page-table' here. 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.
- BeeOnRope 9y ago
  > After skimming the paper, I think it's actually closer to segmentation. They just split the address space into X number of segments. The allocator then ensures every allocation lies completely within one of these segments and attaches that segment's ID to the returned pointer. 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).
  - DSMan195276 9y ago
    Reading it again, I guess I missed the "shadow memory" concept they talked about, but they only mention it 5 times and none of those mentions are in the actually explanation of how they do the memory tagging. They do mention it one more time in the AArch64 implementation though, so it does look like you're correct on this. I don't understand why they didn't really make this detail much more clear though, since like you've pointed out it changes a lot about how things work. 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.
    - convolvatron 9y ago
      I dont understand the implication of why the kernel needs to be aware of the checking. the tag bits are architecturally ignored. 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?
      - DSMan195276 9y ago
        I suppose that's what I get for skimming, this paper is a bit weird. I thought they were going to have the kernel check the tags of userspace pointers that are passed to it, because it includes this line in regards to ASAN: Does not currently detect when the kernel accesses invalid user-space memory But after reading the paper again it looks like they never bring this up again so ¯\_(ツ)_/¯
        BeeOnRope 9y ago
        Yeah they aren't clear about it, but I guess the idea is in a hardware supported model with memory tagging you'd presumably get kernel (and more generally "cross process") checking kind of for free since the checks would be pervasive and hardware enforced. 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).

DSMan195276 9y ago

After skimming the paper, I think it's actually closer to segmentation. They just split the address space into X number of segments. The allocator then ensures every allocation lies completely within one of these segments and attaches that segment's ID to the returned pointer. Fundamentally, paging and segmentation are fairly similar though, so you're not wrong, there is just no concept of a 'page-table' here. 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.

BeeOnRope 9y ago
> After skimming the paper, I think it's actually closer to segmentation. They just split the address space into X number of segments. The allocator then ensures every allocation lies completely within one of these segments and attaches that segment's ID to the returned pointer. 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).
- DSMan195276 9y ago
  Reading it again, I guess I missed the "shadow memory" concept they talked about, but they only mention it 5 times and none of those mentions are in the actually explanation of how they do the memory tagging. They do mention it one more time in the AArch64 implementation though, so it does look like you're correct on this. I don't understand why they didn't really make this detail much more clear though, since like you've pointed out it changes a lot about how things work. 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.
  - convolvatron 9y ago
    I dont understand the implication of why the kernel needs to be aware of the checking. the tag bits are architecturally ignored. 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?
    - DSMan195276 9y ago
      I suppose that's what I get for skimming, this paper is a bit weird. I thought they were going to have the kernel check the tags of userspace pointers that are passed to it, because it includes this line in regards to ASAN: Does not currently detect when the kernel accesses invalid user-space memory But after reading the paper again it looks like they never bring this up again so ¯\_(ツ)_/¯
      - BeeOnRope 9y ago
        Yeah they aren't clear about it, but I guess the idea is in a hardware supported model with memory tagging you'd presumably get kernel (and more generally "cross process") checking kind of for free since the checks would be pervasive and hardware enforced. 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).