Who's afraid of a big bad optimizing compiler?
lwn.net
lwn.net
Edit: More background:
https://wiki.sei.cmu.edu/confluence/display/c/MSC06-C.+Bewar...
https://people.eecs.berkeley.edu/~dawnsong/papers/The%20Corr...
Edit: https://store.developer.arm.com/store/embedded-iot-software-...
Most likely the security controls weren't correct in the first place, which is pretty bad for a security control.
The reality is that the source code is just an input, and even if it's correct or sensible, the control flow in the produced binary is the only truth on a system.
An example is when e.g. zeroing out a buffer containing secrets after usage, this overwrite is stripped by the compiler.
For example, trying to zero a page before freeing it (because is contains sensitive information) is surprisingly hard. Optimizing compilers will consider that since the memory is not going to be accessed it doesn't need to write the zeroes to it. Look at all the contortions libsodium goes to do coerce all the compilers to do the right thing :) https://github.com/jedisct1/libsodium/blob/a26467874a512de30...
Also they know, because it's what those functions they call are for. man explicit_bzero for example. It says:
"The explicit_bzero() function performs the same task as bzero(). It differs from bzero() in that it guarantees that compiler optimizations will not remove the erase operation if the compiler deduces that the operation is "unnecessary"."
What is the purpose of this line?
Why do you think it's there if the C code using volatile is enough on its own?
https://github.com/jedisct1/libsodium/blob/a26467874a512de30...
It's a workaround to prevent optimisations because that happens to be how some compilers are implemented today. Will it be implemented like that tomorrow or in a different compiler? Who knows.
https://github.com/jedisct1/libsodium/commit/27872ca13c713c9...
https://boringssl.googlesource.com/boringssl/+/refs/heads/ma...
https://boringssl.googlesource.com/boringssl/+/ad1907fe73334...
However because inline assembly is non-standard even that is not truly guaranteed. Your relying on the good graces of the optimizers that have broken all the other code paths with their legalistic approach.
I must concede this notion troubles me now that you mentioned it, it is indeed possible that GCC or Clang could decide that there is some other way explicit memset-like stuff should be done; and boringssl could deal with it, they are not a stable API for one thing, and Google employs GCC, LLVM and Clang developers anyway so it would be easier for BoringSSL than the rest of the world to fix the compilers changing stuff...
Edit: Actually looking at your link closer (too many #defines makes my eyes glaze over), it looks like the final else branch appears to use volatile like I mentioned.
I assume all the branches above it are optimizations for different systems?
Imo if you don't want the compiler to optimize something, tell it not to. For example in GCC:
__attribute__((optimize("-O0"), noinline))
void zero_memory(void* memory, size_t sz) {
memset(memory, 0, sz);
}
https://docs.microsoft.com/en-us/previous-versions/windows/d...
For example, to prevent timing attacks positive and negative code paths should take the same amount of time. An optimising compiler could decide that the operations in the negative code path are irrevelant, which in terms of the actual work its doing is true, and remove them. Except now it has reintroduced the timing attack.
Sacrificing correctness for speed is an unfortunate trend. I have written lots of compilers in my life, both toys and "real-world" ones, and I can say with certainty that more than 90% of the bugs appear in the optimizer. Without formal verification or at least very exhaustive testing, optimizations should not be included in compilers. Of course, this is very hard to accomplish in low-level languages.
Is this meaningful? Lots of behaviour is logically unexpected by developers, but well described in the standard and implemented correctly in the compiler.
If the language gives unexpected results, that's closer to the specification problem than a compiler issue.
Security code cares about these things, so has to make use of a best effort, and checking assembly.
The problem there being that a) all code is security-critical if the compiler elides a bounds check or turns it into a buffer overrun or just crashes and allows for DoS, and b) that requires you to inspect the code generated by every compiler that will be used to compile the code, which for published source code could be any compiler in the world, including ones that don't exist yet.
One could choose a popular dev target like Ubuntu LTS and seek to comprehend the relevant optimization behavior for a popular compiler like GCC.
Now part b above is reduced to a single environment to generate a binary for all archs where WASM will run.
If a compiler optimizes your constant time algorithm into a completely equivalent one with varying time, it did nothing wrong, except on security-critical code.
void f(int a[], size_t len) {
size_t i=0;
while(1) {
int val = a[i++];
if(i > len) break;
do_something(val);
}
}
But suppose the true length of a[] is exactly equal to len, and the compiler is aware of that. Then when i is greater than or equal to len, reading a[i] is undefined behavior. That means that either the bounds check is always false and can be elided, or it isn't false which means there is undefined behavior that allows the compiler to do anything it wants, and maybe what it wants is to elide the bounds check as an optimization. So it does and the compiled code will keep executing do_something() on every value in memory after a[].
The code is wrong, but not in a way which is intuitively obvious, and not in way that compilers had historically taken advantage of to such deleterious effect. And you can't figure that out by looking at the compiler output for a compiler that doesn't take that optimization.
This is completely different from the program:
int f (char* a, size_t len_a, char* b, size_t len_b) {
size_t i = 0;
int eq = 1;
while (i < len_a && i < len_b) {
if (a[i] != b[i]) eq = 0;
i++;
}
return eq && i == len_a && i == len_b;
}
Throw in Spectre and it's a huge mess, because it's not just the password hashing function leaking the password hashes, it's anything with an exploitable bounds check that can reach the memory where they're stored.
while (!need_to_stop) /* BUGGY!!! */ do_something_quickly();
Can the optimiser really unroll the loop and only check the need_to_stop variable once!?
if (!need_to_stop)
for (;;) {
do_something_quickly();
do_something_quickly();
do_something_quickly();
do_something_quickly();
....
Yes. The compiler can see that need_to_stop is not changed by any of the code inside the loop, and since it wasn't qualified with "volatile" or using explicit atomic operations the compiler is free to assume that it won't be changed asynchronously. That makes need_to_stop a constant for the duration of the loop, so it should have the same effect (given those assumptions) whether the variable is checked once or before each call to do_something_quickly(). Checking once is considerably more efficient.
EDIT: also, volatile is a bad idea, too, unless you are doing something low-level like a kernel or hacking on memory mapped IO pins. It does not synchronize accesses between threads.
This seems like it might possibly have been a reasonable assumption 30 years ago, when multi-processor machines were tens of thousands of dollars; but now that your watch has 4 cores, non-local variables changing should be considered the norm.
The language standard says that the programmer is not permitted to write data races, even if they are benign. You either need to provide synchronization in the form of locks or explicit memory barriers, or you need to use special atomic variables whose semantics allow concurrent access without synchronization.
Without these rules (or something substantially similar), compilers would instead be forced to add sequentially-consistent memory barriers around every memory access they couldn't prove was only within a single thread (i.e., add it to every single memory access). The resulting performance would be completely unacceptable.
The original purpose of C was to write operating systems; at some point that was basically discarded, and it is now incredibly difficult to write an operating system safely in C anymore. It's like juggling lightsabers.
In practice, the memory model of real hardware systems do a much more thorough job of screwing you up than compiler optimizations, so any practical operating system already needs to build a memory model that can cope with hardware reordering. The only interaction you need with the compiler is a few hooks to stop optimizations, which are quite easy to build in (an empty volatile asm that clobbers memory will prevent reordering of memory operations, for example), and newer language standards actually give you specific mechanisms that give you the building blocks without the need to resort to inline asm tricks.
> The "subscriber link" mechanism allows an LWN.net subscriber to generate a special URL for a subscription-only article. That URL can then be given to others, who will be able to access the article regardless of whether they are subscribed. This feature is made available as a service to LWN subscribers, and in the hope that they will use it to spread the word about their favorite LWN articles.
> If this feature is abused, it will hurt LWN's subscription revenues and defeat the whole point. Subscriber links may go away if that comes about.
but hey...
Sure, the optimizer is usually great at exposing buggy code that relies on undefined behavior, but there's nothing concurrency-specific to that.
As such I think the article would have been better had it been framed from the point of view that it feels like it wants to take, but doesn't: a guide for beginners of things you rely on in non-concurrent code that you can't in concurrent code.
There's more to that topic than what the optimizer does.