C can't do provenance [LWN.net]

C can't do provenance

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

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.

to post comments

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.