3 ms·

How would this fix memory safety issues like std::sort(vec1.begin(), vec2.end()) (where vec1 and vec2 are different vectors, of course)? Or strlen(malloc(100))?

deleted 2y ago
[deleted]
o11c 2y ago
With a safe runtime, a pointer is really something like a `struct { u32 allocation_base, allocation_offset;}`. (it may be worth doing fancy variable-bit-width math to allow many small allocations but only a few large ones; it's also likely worth it to have a dedicated "leaf" section of memory that is intended not to contain any pointers) An implementation of `sort` would start with: `assert (begin.allocation_base == end.allocation_base)`. Most likely, this would be implicit when `end - begin` or `begin < end` is called (but not `!=`, which is well-defined between unrelated pointers). If we ignore the uninitialized data (which is not the same kind of UB, and usually not interesting), the `strlen` loop would assert when, after not encountering a NUL, `s.allocation_offset` exceeds `100` (which is known in the allocation metadata).
- tsimionescu 2y ago
  That makes sense, thank you! I'd bet that there are corners of non-UB vlaid programs that would be sensitive to the fact that pointers are no longer simple numbers, but maybe that's wrong or at least could be worked around. I would add that to make this memory safe for multi-threaded programs, you also need to implcitly synchronize on fat pointer accesses, to prevent corrupted pointers from forming.
- badmintonbaseba 2y ago
  Tracking allocations is necessary, but not sufficient. struct S { int arr1[100]; std::string s; int arr2[100]; }; void foo(S& s) { //arr1 and arr2 are in the same complete object //so they are in the same allocation std::sort(std::begin(arr1), std::end(arr2)); } To make it sound you really need to track arrays specifically (including implicit single-element ones), not just allocations. It's surely somewhat feasible, as the constexpr interpreters in compilers do track it, but something like that would probably be way inefficient at runtime.
  - o11c 2y ago
    (if `sizeof(char *)` != `sizeof(int)` it will be detected as an illegal memory access, since at a minimum every word is tagged whether it's a pointer or not. Otherwise ...) That's really an aliasing problem, not specific to arrays. The tricky part about tagging memory with a full type is that a lot of code, even in standards, relies on aliasing that's supposed to be forbidden. Still, even if the `sort` isn't detected (due to the user insisting on permissiveness rather than adding annotations), it would still detect any attempt to use `s` afterward. As for a limited array-specific solution ... I can't think of one that would handle all variants of `sort((int *)&s[0], (int *)&s[1])`. And do we want to forbid `sort(&s.arr[0], (int *)&s.s)`?
- gpderetta 2y ago
  one day we will bring segments and far pointers back.
  - zozbot234 2y ago
    CHERI is pretty much there already
gmueckl 2y ago
These two examples come from bad library design, not bad language design. The first one was fixed with ranges. The second one would be fixed if C used an explicit string type in it's standard library.
- tsimionescu 2y ago
  That is besides the point. The claim was about making C++ memory safe by adjusting the runtime, and I was curious how that could work for cases other than use-after-free.
TinkersW 2y ago
It seems to me that it would handle the sort case fine, you would read/write an invalid page and it would fall over(assuming all allocations had invalid pages at the end of the allocation & no 2 allocations share a page). The strlen could be made safe by having the malloc return the address 100 bytes before the end of the page. If it did make it to the end of the 100 bytes it would fall over safely. Result would be nonsense of course. Of course if you read bytes < than the returned ptr you would have 4k-100 bytes before it fails on bad page.
- NobodyNada 2y ago
  > assuming all allocations had invalid pages at the end of the allocation & no 2 allocations share a page This assumption doesn't hold for real world systems -- most allocations are small, so heap allocators typically support a minimum allocation size of 16 bytes. Requiring each allocation to have its own page would be a 256x memory overhead for these small allocations (assuming 4k pages, and even worse as systems are moving to 16k or 64k page size). Not to mention destroying your TLB. Also, guard pages only solve the problem if the program tries to access the entire array (like when sorting or reading a string). For other types of out-of-bounds array access where an attacker can control the index accessed, they can just pass in an index high enough to jump over the guard page. You can "fix" this with probing, but at that point just bounds-checking is much simpler and more performant.

deleted 2y ago

[deleted]

o11c 2y ago

With a safe runtime, a pointer is really something like a `struct { u32 allocation_base, allocation_offset;}`. (it may be worth doing fancy variable-bit-width math to allow many small allocations but only a few large ones; it's also likely worth it to have a dedicated "leaf" section of memory that is intended not to contain any pointers) An implementation of `sort` would start with: `assert (begin.allocation_base == end.allocation_base)`. Most likely, this would be implicit when `end - begin` or `begin < end` is called (but not `!=`, which is well-defined between unrelated pointers). If we ignore the uninitialized data (which is not the same kind of UB, and usually not interesting), the `strlen` loop would assert when, after not encountering a NUL, `s.allocation_offset` exceeds `100` (which is known in the allocation metadata).

tsimionescu 2y ago
That makes sense, thank you! I'd bet that there are corners of non-UB vlaid programs that would be sensitive to the fact that pointers are no longer simple numbers, but maybe that's wrong or at least could be worked around. I would add that to make this memory safe for multi-threaded programs, you also need to implcitly synchronize on fat pointer accesses, to prevent corrupted pointers from forming.
badmintonbaseba 2y ago
Tracking allocations is necessary, but not sufficient. struct S { int arr1[100]; std::string s; int arr2[100]; }; void foo(S& s) { //arr1 and arr2 are in the same complete object //so they are in the same allocation std::sort(std::begin(arr1), std::end(arr2)); } To make it sound you really need to track arrays specifically (including implicit single-element ones), not just allocations. It's surely somewhat feasible, as the constexpr interpreters in compilers do track it, but something like that would probably be way inefficient at runtime.
- o11c 2y ago
  (if `sizeof(char *)` != `sizeof(int)` it will be detected as an illegal memory access, since at a minimum every word is tagged whether it's a pointer or not. Otherwise ...) That's really an aliasing problem, not specific to arrays. The tricky part about tagging memory with a full type is that a lot of code, even in standards, relies on aliasing that's supposed to be forbidden. Still, even if the `sort` isn't detected (due to the user insisting on permissiveness rather than adding annotations), it would still detect any attempt to use `s` afterward. As for a limited array-specific solution ... I can't think of one that would handle all variants of `sort((int *)&s[0], (int *)&s[1])`. And do we want to forbid `sort(&s.arr[0], (int *)&s.s)`?
gpderetta 2y ago
one day we will bring segments and far pointers back.
- zozbot234 2y ago
  CHERI is pretty much there already

gmueckl 2y ago

These two examples come from bad library design, not bad language design. The first one was fixed with ranges. The second one would be fixed if C used an explicit string type in it's standard library.

tsimionescu 2y ago
That is besides the point. The claim was about making C++ memory safe by adjusting the runtime, and I was curious how that could work for cases other than use-after-free.

TinkersW 2y ago

It seems to me that it would handle the sort case fine, you would read/write an invalid page and it would fall over(assuming all allocations had invalid pages at the end of the allocation & no 2 allocations share a page). The strlen could be made safe by having the malloc return the address 100 bytes before the end of the page. If it did make it to the end of the 100 bytes it would fall over safely. Result would be nonsense of course. Of course if you read bytes < than the returned ptr you would have 4k-100 bytes before it fails on bad page.

NobodyNada 2y ago
> assuming all allocations had invalid pages at the end of the allocation & no 2 allocations share a page This assumption doesn't hold for real world systems -- most allocations are small, so heap allocators typically support a minimum allocation size of 16 bytes. Requiring each allocation to have its own page would be a 256x memory overhead for these small allocations (assuming 4k pages, and even worse as systems are moving to 16k or 64k page size). Not to mention destroying your TLB. Also, guard pages only solve the problem if the program tries to access the entire array (like when sorting or reading a string). For other types of out-of-bounds array access where an attacker can control the index accessed, they can just pass in an index high enough to jump over the guard page. You can "fix" this with probing, but at that point just bounds-checking is much simpler and more performant.