Especially for security-critical operations, it is often a good idea to disassemble the relevant sections of the binary and ensure that things are handled appropriately. Optimizations can result in security controls not working as expected.
The more I read stuff like this, the more I come to the conclusion that actual security critial real time software should probably be compiled without any (agressive) optimisations
You will be hard pressed to find a compiler that has a high level safety certification that covers optimizations. Most safety manuals I am aware of explicitly forbid enabling optimizations.
Different compilers produce different binaries, different compiler settings result in different binaries.
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...
If they don't have a way to test and look at machine code on these architectures... then how can they know their workarounds for compiler optimisations are working?
These are not workarounds. The code looks complicated only because it tries to be portable and fast. Otherwise just the last #else block would be enough.
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"."
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.
Boringssl used to use assembly until they figured out this trick of scaring the compiler away by justing putting an assembly directive in the function:
I am pretty sure the code is entirely correct when meant for GCC or Clang. Standards-noncompliance (because of inline assembly) is another issue, of course; but one could argue that GCC and Clang are the de facto standard.
The problem would be someone working on the GCC optimizer deciding, “Wouldn’t it be great if we could do all our fancy optimizations on functions with inline assembly?”
Volatile only says that the clobbered memory is not listed. Nothing would stop the compiler from statically analyzing the assembly to make smarter decisions if it chose to do so. This would be trivial with an empty asm block.
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...
Only on UNIX clones, and even then there are no guarantees of backward compatibility between compiler revisions regarding implementation specific, unspecified and undefined behaviours.
I'm not familiar with writing code to wipe memory, but couldn't you just use volatile keyword? Volatile writes are not supposed to be optimized away, and pointers to non-volatile types can be cast to pointers to volatile types.
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?
Volatile is a hacky way to avoid optimizations and plays hell with normal language semantics. For example, you can't memcpy or memset volatile pointers or pointers to volatiles.
Imo if you don't want the compiler to optimize something, tell it not to. For example in GCC:
If you wanted to make that portable, there are equivalents in clang and msvc so you'd want to use some #defines here and there. Of course disabling optimizations/inlining in functions has a performance hit, but I think if you're so concerned with code being ignored the tradeoff is appropriate.
Windows even provides a SecureZeroMemory API because solving this problem reliably at the language level is hard. I see the sodium_memzero function you linked to calls Windows' SecureZeroMemory. :)
Secure code can absolutely be correct and be optimised in a way that reduces its security.
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.
But the C language has notion of how long anything takes. You cannot write a C program with two branches that take the same time in the first place, for the optimisation to upset that.
If some code does not work as expected, the compiler is broken.
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.
> Especially for security-critical operations, it is often a good idea to disassemble the relevant sections of the binary and ensure that things are handled appropriately.
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.
If a compiler issues code that elides a bound check or crashes for good source, it is broken.
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.
You would expect for this code to call do_something() for the first len values in a[], which will be the result on a lot of compilers.
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.
The code is wrong, and the compiler has no correct option to use. Whatever it decides to do is ok.
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;
}
If you pass two strings that differ on the first character, do you expect it to run through all the characters or return at the first? Both will have exactly the same result, and compilers know how to convert one into the other. If you use code that returns early on a function that verifies user password hashes on a web site, you'll just leak all of your users passwords.
The first function is wrong because it leaves the compiler the discretion to do something dangerous. But isn't that the same problem as the second function? The compiler has much more discretion in the first case, all the way to nasal demons and flying monkeys, but that's little consolation when the discretion it does have in the second case is to do exactly the thing that makes the function insecure. "Whatever it decides to do is ok," but some of the things it can decide to do will leak your password hashes.
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.
> 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.
The article comes across as a bit confused. As far as I can see, these are all examples of plain concurrency-unsafe code rather than anything to do with the optimizer.
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.
> Can the optimiser really unroll the loop and only check the need_to_stop variable once!?
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.
In addition to what plorkyeran said: While volatile alone doesn't synchronize accesses between threads, it is enough to ensure that the variable is read separately in each iteration of the loop—though it might just be read from the L1 cache and not take into account writes from other cores.
> the compiler is free to assume that it won't be changed asynchronously.
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 modern language standards (C++11/C11 and newer) explicitly take multicore machines into account, and the memory model was specifically designed knowing the capabilities of hardware.
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 code is simply incorrect. Use locking (pthread_mutex_lock, pthread_mutex_trylock, pthread_mutex_unlock) if you need to do something like that. C and C++ have the same memory model, but this would be wrong in any language.
Oh, right! All Linux has to do then is link pthread into the kernel and all their problems will magically go away.</snark>
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.
The Linux kernel has chosen to adopt a memory model and a threading model. This was done even before C++11/C11 defined a memory model, and the two systems are quite similar and can mostly be built on top of one another (READ_ONCE/WRITE_ONCE is sort of the odd man out, but it works if you assume the semantics of volatile are "do not eliminate or rematerialize this load/store," which is a correct model if you look at compiler implementations).
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.
59 comments
[ 4.8 ms ] story [ 122 ms ] threadEdit: 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:
If you wanted to make that portable, there are equivalents in clang and msvc so you'd want to use some #defines here and there. Of course disabling optimizations/inlining in functions has a performance hit, but I think if you're so concerned with code being ignored the tradeoff is appropriate.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.
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:
If you pass two strings that differ on the first character, do you expect it to run through all the characters or return at the first? Both will have exactly the same result, and compilers know how to convert one into the other. If you use code that returns early on a function that verifies user password hashes on a web site, you'll just leak all of your users passwords.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.
> 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.
while (!need_to_stop) /* BUGGY!!! */ do_something_quickly();
Can the optimiser really unroll the loop and only check the need_to_stop variable once!?
Is this the same for C++ or is does the new memory model prevent it?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.
Am I allowed to read this?