C can't do provenance [LWN.net]

C can't do provenance

Posted Sep 29, 2024 22:04 UTC (Sun) by NYKevin (subscriber, #129325)
In reply to: C can't do provenance by joib
Parent article: Linus and Dirk on succession, Rust, and more

> I'm 75% sure that comparing the pointer value of a freed pointer is already UB, although it's somewhat common in practice.

Unfortunately, text in https://en.cppreference.com/w/c/memory/free misled me into thinking the standard allowed this (and then I couldn't find language in the draft standard directly contradicting it).

> Eh, I don't think this will fly at all. Like it or not, pointer<=>integer conversions and roundtrips are a fact of life in the C world , and any proposal must continue to support them.

C23 explicitly says that intptr_t is optional. If you don't provide it, then there is no line in the standard requiring pointer-to-integer conversions to be possible.

> No, why? In the PVNI proposals

Please link to the proposal you are discussing, Google can't find anything by that name. It did find a link to something under open-std.org titled "A Provenance-aware Memory Object Model for C," which does not contain the word "PVNI" anywhere on the page, but the page is not loading for me, so I can't examine it to determine whether it has anything to do with what you are saying.

> there's no requirement for perfect knowledge by the compiler, which is you point out is intractable. It just means the compiler must treat a pointer constructed in such a way as potentially aliasing any escaped pointer (called "exposed" in the PVNI proposals but AFAICS this is more or less the same thing as what compiler people call an address or pointer escaping).

As I have repeatedly explained throughout this thread, provenance is not an optimization. It is a hardware constraint. You can't simply turn it off in difficult cases, because the dereference will trap whether the compiler wants it to or not.

to post comments

C can't do provenance

Posted Sep 29, 2024 22:11 UTC (Sun) by NYKevin (subscriber, #129325) [Link] (4 responses)

Just to further clarify: I am aware that provenance proposals usually do have an escape hatch for "exposed" addresses. But to my understanding, such an escape hatch does not exist on CHERI or other hardware, so any such escape hatch would need to be emulated by the kernel if it's going to work at all. While that is technically possible to implement, it leaves a ton of performance on the table and requires OS support.

C can't do provenance

Posted Sep 30, 2024 7:19 UTC (Mon) by joib (subscriber, #8541) [Link] (3 responses)

I don't think the 'escape hatch' is needed on CHERI, assuming the code uses the (special in CHERI-C) intptr_t type for any pointer<=>integer roundtrips.

The escape hatch is needed for mainstream implementations where the HW does not carry around any provenance information, and the compiler is not tracking provenance once a pointer is 'exposed' (and in some cases, is fundamentally incapable to at compile time).

> it leaves a ton of performance on the table

It would be nice to have some quantitative data backing that statement.

I don't have any quantitative data proving otherwise either, but AFAICS the 'escape hatch' is activated in situations like

1) Pointer a is exposed, creating an integer a1.

2) Some time later, a pointer b is created 'out of thin air'. Maybe b is created via a1, maybe not, the compiler doesn't know.

Now the compiler must assume that a and b potentially alias, and thus some fancy optimizations cannot be done. But crucially, the compiler can still use provenance to reason about pointer c which has not been exposed, and do optimizations related to that pointer accordingly. Given that situations like the above are hopefully somewhat rare, I'm not buying the story about a major performance impact without benchmarks.

I also don't understand what OS support would be needed? Or are you assuming that on mainstream HW the OS would emulate CHERI and "manually" keep track of provenance in the kernel, somehow?

Perhaps this is where we disagree; I see the provenance proposals mainly as an effort to codify existing practices by optimizing compilers. I see CHERI as a separate effort trying to make computing safer by detecting violations at runtime, using provenance as a crucial tool to implement said detection. And there has been some collaboration between the CHERI folks and the ones writing the provenance proposals (which is very nice, I would very much like to see CHERI or something like it becoming mainstream, and it would be a bummer if C would go in an incompatible direction). But I don't think that if any of the provenance proposals is adopted, that it would require implementations to somehow emulate CHERI on non-CHERI hw. C-with-provenance on mainstream hardware would still be as dangerous and error-prone as it is today. Just hopefully with a bit less ambiguity whether something the compiler does is a miscompilation or perfectly allowed, once compilers implement the provenance rules.

C can't do provenance

Posted Sep 30, 2024 19:52 UTC (Mon) by NYKevin (subscriber, #129325) [Link] (2 responses)

> I don't think the 'escape hatch' is needed on CHERI, assuming the code uses the (special in CHERI-C) intptr_t type for any pointer<=>integer roundtrips.

It is required for pointer <=> char[], which in C23 is legal for any type, including all pointers. It is not practically possible for the compiler to emit provenance-preserving operations for every byte that the program manipulates, so I would think it obvious that you have to draw a boundary there.

The other problem is that intptr_t is a number. It is not an opaque object that is allowed to have magical properties. If any part of the program becomes aware of that number, by any means whatsoever, then it is allowed to reconstruct and dereference the pointer (provided the allocation still exists). That means you can flatten it into ASCII base 10 (or any other base), send it to a remote host as JSON (or any other format), receive it back from that same host or a different one, unpack it all back into a pointer, and dereference it. No hardware in the world will ever support tracking provenance across that sequence of operations.

> The escape hatch is needed for mainstream implementations where the HW does not carry around any provenance information, and the compiler is not tracking provenance once a pointer is 'exposed' (and in some cases, is fundamentally incapable to at compile time).

Then you don't need to do anything special. UB means that the standard doesn't cover a situation. It does not mean that the compiler is forbidden from introducing an extension to make UB defined. The compiler can just say in its documentation "as an extension, on all architectures other than X, Y, and Z, provenance does not exist and all pointer <=> data conversions that were valid in C23 are still valid and the resulting pointers may still be dereferenced." Of course, this would be based on some hypothetical future version of the standard, since as I have explained, C23 has no reasonable support for provenance.

The other, far simpler option is for CNext to state that provenance rules only apply to a given platform (or configuration) if the compiler's documentation explicitly says that it does. Frankly, that strikes me as the obvious way to deal with this, and then none of these discussions are even necessary at all.

> It would be nice to have some quantitative data backing that statement.

That statement was specific to hardware that has provenance and requires kernel emulation of exposed pointer dereferences. IMHO it is obvious that kernel emulation is slow, and it does not need to be measured (I don't even know if there are any operating systems that both support CHERI and implement exposed address emulation). Your discussion of platforms that do not have provenance is frankly irrelevant to my statement.

> But I don't think that if any of the provenance proposals is adopted, that it would require implementations to somehow emulate CHERI on non-CHERI hw.

Of course not, I was assuming that all readers were familiar with the definition of UB and the fact that the implementation is encouraged to do whatever makes sense (performance-wise) on a given platform when UB happens. I don't understand how you read this into my comment, when I so explicitly characterized provenance as a hardware feature and disclaimed its relevance to non-CHERI-like platforms.

C can't do provenance

Posted Sep 30, 2024 22:45 UTC (Mon) by Wol (subscriber, #4433) [Link]

> IMHO it is obvious that kernel emulation is slow, and it does not need to be measured (I don't even know if there are any operating systems that both support CHERI and implement exposed address emulation).

The problem with common sense is that it is not common, and rarely makes sense.

As such, a statement like "imho it is obvious" is almost certainly wrong. How often do we hear "it stands to reason", only to discover that said reasoning has missed the obvious and come to a conclusion diametrically opposed to empirical observation.

Cheers,
Wol

C can't do provenance

Posted Oct 1, 2024 11:02 UTC (Tue) by farnz (subscriber, #17727) [Link]

The other, far simpler option is for CNext to state that provenance rules only apply to a given platform (or configuration) if the compiler's documentation explicitly says that it does. Frankly, that strikes me as the obvious way to deal with this, and then none of these discussions are even necessary at all.

The issue is that without provenance rules, alias analysis becomes intractable, since any integer could be cast to a pointer, including in other modules. And without alias analysis, you have to assume that any write through a pointer, including in other threads that have a suitable ordering with your thread, could write to any variable.

Compiler writers handle this by assuming that certain things can't alias, even though the language standard doesn't prohibit that form of aliasing, and then hoping that their gut feelings work out when they write optimizations that assume that (e.g.) an integer and a pointer to a struct don't alias. This works most of the time, since compiler writers aren't evil, and their assumptions match those that programmers tend to make.

Unfortunately, some of the assumptions that compiler authors make contradict each other; each of them technically breaks the letter of the standard (so neither one is "right"), and each of them results in an optimization that improves code without surprising C programmers, but the combination of optimizations that assume different things results in a miscompilation. The intention behind formalizing provenance rules is to get to a place where the standard can be used to determine which of those optimizations is at fault when the combination surprises people.

C can't do provenance

Posted Sep 30, 2024 6:27 UTC (Mon) by joib (subscriber, #8541) [Link]

> C23 explicitly says that intptr_t is optional. If you don't provide it, then there is no line in the standard requiring pointer-to-integer conversions to be possible.

I believe if the implementation provides an integer type large enough to hold a pointer, it must be possible to do such a pointer-to-integer conversion. So even without specifically intptr_t (which, in the history of C is a recent-ish invention anyway as it was introduced only in C99) it can be done, and many C implementation through history have done so.

That being said, I think you're correct in that there's nothing in the standard requiring an implementation to provide such large enough integer types capable of storing a pointer. But that gets into the distinction between the standard and that a lot of C code out there is written under the assumption that such an integer type exists.

Now, CHERI C is a bit special in that they make intptr_t contain the bounds and capability tag, making it possible to do pointer<=>integer roundtrips only with that type. That's probably a good practical compromise between the purity of the capability model, standards conformance, and still allowing roundtripping with a modest porting effort.

> Please link to the proposal you are discussing, Google can't find anything by that name.

It's a typo, I meant PNVI (*sigh*). I think the latest proposal is n3005 at https://open-std.org/JTC1/SC22/WG14/www/docs/n3005.pdf . That link doesn't work for me at the moment but you can find it in the wayback machine.

> As I have repeatedly explained throughout this thread, provenance is not an optimization. It is a hardware constraint. You can't simply turn it off in difficult cases, because the dereference will trap whether the compiler wants it to or not.

Well, for CHERI it's a hardware constraint. But like it or not, non-CHERI hw will be the vast majority for the foreseeable future, and AFAIU there's no plan to make C-with-provenance (if that ever happens) non-implementable on such hardware. For mainstream environments, the practical effect of provenance is to provide compiler writers with guidance on what kinds of optimizations are allowed.