25 ms·

Clang vs. Clang

248 points by dchest 2y ago

josephcsible 2y ago
> compiler writers refuse to take responsibility for the bugs they introduced, even though the compiled code worked fine before the "optimizations". The excuse for not taking responsibility is that there are "language standards" saying that these bugs should be blamed on millions of programmers writing code that bumps into "undefined behavior" But that's not an excuse for having a bug; it's the exact evidence that it's not a bug at all. Calling the compiler buggy for not doing what you want when you commit Undefined Behavior is like calling dd buggy for destroying your data when you call it with the wrong arguments.
- nabla9 2y ago
  Optimizing compilers that don't allow disabling all optimizations makes it impossible to write secure code with them. Must do it with assembly.
  - exe34 2y ago
    clang::optnone
    - nabla9 2y ago
      "Optimizing compilers that don't allow disabling __all__ optimizations"
      - exe34 2y ago
        do these exist? who's using them?
      - layer8 2y ago
        It’s not well-defined what counts as an optimization. For example, should every single source-level read access of a memory location go through all cache levels down to main memory, instead of, for example, caching values in registers? That would be awfully slow. But that question is one reason for UB.
        kevingadd 2y ago
        Or writing code that relies on inlining and/or tail call optimization to successfully run at all without running out of stack... We've got some code that doesn't run if compiled O0 due to that.
  - cmeacham98 2y ago
    If your "secure" code is not secure because of a compiler optimization it is fundamentally incorrect and broken.
    - nabla9 2y ago
      It's secure code we use. I'm sure you know who DJB is.
      - jjuhl 2y ago
        Why is knowing who the author is relevant? Either what he posts is correct or it is not, who the person is is irrelevant.
    - hedgehog 2y ago
      There is a fundamental difference of priorities between the two worlds. For most general application code any optimization is fine as long as the output is correct. In security critical code information leakage from execution time and resource usage on the chip matters but that essentially means you need to get away from data-dependent memory access patterns and flow control.
      - account42 2y ago
        Then such code needs to be written in a language that actually makes the relevant timing guarantees. That language may be C with appropriate extensions but it certainly is not C with whining that compilers don't apply my special requirements to all code.
        hedgehog 2y ago
        That argument would make more sense if such a language was widely available but today in practice it isn't so we live in the universe of less ideal solutions. Actually it doesn't really respond to DJB's point anyway, his case here is that the downstream labor cost of compiler churn exceeds the actual return in performance gains from new features and that a change in policy could give security-related code a more predictable target without requiring a whole new language or toolchain. For what it's worth I think the better solution will end up being something like constant-time function annotations (not stopping new compiler features) but I don't discount his view that absent human nature maybe we would be better of focusing compiler dev on correctness and stability.
  - bluGill 2y ago
    If you have ub then you have a bug and there is some system that will show it. It isn't hard to write code without ub.
    - bigstrat2003 2y ago
      It is, in fact, pretty hard as evidenced by how often programmers fail at it. The macho attitude of "it's not hard, just write good code" is divorced from observable reality.
      - bluGill 2y ago
        People write buffer overflows because and memory leaks they are not coreful. The rest of ub are things I have never seen despite running sanitizers and a large codebase.
        saagarjha 2y ago
        Perhaps you’re not looking all that hard.
        bluGill 2y ago
        Sanitizers are very good at finding ub.
        deleted 2y ago
        [deleted]
        saagarjha 2y ago
        Sure. That's just a function of how much UB there is, rather than them catching it all.
      - tbrownaw 2y ago
        Staying under the speed limit is, in fact, pretty hard as evidenced by how often drivers fail at it.
  - Rusky 2y ago
    Disabling all optimizations isn't even enough- fundamentally what you need is a much narrower specification for how the source language maps to its output. Even -O0 doesn't give you that, and in fact will often be counterproductive (e.g. you'll get branches in places that the optimizer would have removed them). The problem with this is that no general purpose compiler wants to tie its own hands behind its back in this way, for the benefit of one narrow use case. It's not just that it would cost performance for everyone else, but also that it requires a totally different approach to specification and backwards compatibility, not to mention deep changes to compiler architecture. You almost may as well just design a new language, at that point.
    - amluto 2y ago
      > You almost may as well just design a new language, at that point. Forget “almost”. Go compile this C code: void foo(int *ptr) { free(ptr); *ptr = 42; } This is UB. And it has nothing whatsoever to do with optimizations — any sensible translation to machine code is a use-after-free, and an attacker can probably find a way to exploit that machine code to run arbitrary code and format your disk. If you don’t like this, use a language without UB. But djb wants something different, I think: a way to tell the compiler not to introduce timing dependencies on certain values. This is a nice idea, but it needs hardware support! Your CPU may well implement ALU instructions with data-dependent timing. Intel, for example, reserves the right to do this unless you set an MSR to tell it not to. And you cannot set that MSR from user code, so what exactly is a compiler supposed to do? https://www.intel.com/content/www/us/en/developer/articles/technical/software-security-guidance/best-practices/data-operand-independent-timing-isa-guidance.html https://www.intel.com/content/www/us/en/developer/articles/t...
      - Rusky 2y ago
        I am not talking about UB at all. I am talking about the same constant-time stuff that djb's post is talking about.
        SAI_Peregrinus 2y ago
- thayne 2y ago
  The problem is that c and c++ have a ridiculous amount of undefined behavior, and it is extremely difficult to avoid all of it. One of the advantages of rust is it confines any potential UB to unsafe blocks. But even in rust, which has defined behavior in a lot of places that are UB in c, if you venture into unsafe code, it is remarkable easy to accidentally run into subtle UB issues.
  - layer8 2y ago
    It’s true that UB is not intuitive at first, but “ridiculous amount” and “difficult to avoid” is overstating it. You have to have a proof-writing mindset when coding, but you do get sensitized to the pitfalls once you read up on what the language constructs actually guarantee (and don’t guarantee), and it’s not that much more difficult than, say, avoiding panics in Rust.
    - pjmlp 2y ago
      So surely you know by hear the circa 200 use cases documented in ISO C, and the even greater list documented in ISO C++ standard documents. Because, me despite knowing both since the 1990's, I rather leave that to static analysis tools.
    - tomjakubowski 2y ago
      In my experience it is very easy to accidentally introduce iterator invalidation: it starts with calling a callback while iterating, add some layers of indirection, and eventually somebody will add some innocent looking code deep down the call stack which ends up mutating the collection while it's being iterated.
      - layer8 2y ago
        I can tell you that this happens in Java as well, which doesn’t have undefined behavior. That’s just the nature of mutable state in combination with algorithms that only work while the state remains unmodified.
        2y ago
- js2 2y ago
  I think you're replying to a strawman. Here's the full quote: > The excuse for not taking responsibility is that there are "language standards" saying that these bugs should be blamed on millions of programmers writing code that bumps into "undefined behavior", rather than being blamed on the much smaller group of compiler writers subsequently changing how this code behaves. These "language standards" are written by the compiler writers. > Evidently the compiler writers find it more important to continue developing "optimizations" than to have computer systems functioning as expected. Developing "optimizations" seems to be a very large part of what compiler writers are paid to do. The argument is that the compiler writers are themselves the ones deciding what is and isn't undefined, and they are defining those standards in such a way as to allow themselves latitude for further optimizations. Those optimizations then break previously working code. The compiler writers could instead choose to prioritize backwards compatibility, but they don't. Further, these optimizations don't meaningfully improve the performance of real world code, so the trade-off of breaking code isn't even worth it. That's the argument you need to rebut.
  - quohort 2y ago
    Perhaps the solution is also to reign in the language standard to support stricter use cases. For example, what if there was a constant-time { ... }; block in the same way you have extern "C" { ... }; . Not only would it allow you to have optimizations outside of the block, it would also force the compiler to ensure that a given block of code is always constant-time (as a security check done by the compiler).
    - munificent 2y ago
      > Perhaps the solution is also to reign in the language standard to support stricter use cases. Here's a nine-year-old comment from the author asking for exactly that: https://groups.google.com/g/boring-crypto/c/48qa1kWignU/m/o8GGp2K1DAAJ https://groups.google.com/g/boring-crypto/c/48qa1kWignU/m/o8...
      - fuhsnn 2y ago
        That thread already spawned a GCC-wiki page https://gcc.gnu.org/wiki/boringcc https://gcc.gnu.org/wiki/boringcc, with a quote in bold: >The only thing stopping gcc from becoming the desired boringcc is to find the people willing to do the work. And frankly, nine years is enough time to build a C compiler from scratch.
- duped 2y ago
  I think this is actually a mistake by the author since the rant is mostly focused on implementation defined behavior, not undefined. The examples they give are all perfectly valid code. The specific bugs they're talking about seem to be compiler optimizations that replace bit twiddling arithmetic into branches, which isn't a safe optimization if the bit twiddling happens in a cryptographic context because it opens the door for timing attacks. I don't think it's correct to call either the source code or compiler buggy, it's the C standard that is under specified to the author's liking and it creates security bugs on some targets. Ultimately though I can agree with the C standard authors that they cannot define the behavior of hardware, they can only define the semantics for the language itself. Crypto guys will have to suffer because the blame is on the hardware for these bugs, not the software.
  - gabrielhidasy 2y ago
    Where suffer means "not be lazy, implement the assembly for your primitives in a lib, optimize it as best as you can without compromising security, do not let the compiler 'improve' it"
    - Dylan16807 2y ago
      But then you're not writing C, except maybe as some wrappers. Wanting to use C isn't laziness. Making it nearly unfeasible to use C is the most suffering a C compiler can inflict.
      - g15jv2dp 2y ago
        There's no reason that C should be suitable for every purpose under the sun.
        Dylan16807 2y ago
        Fiddling some bits cross-platform is supposed to be one of them.
- moomin 2y ago
  There are only two models of UB that are useful to compiler users: 1) This is a bad idea and refuse to compile. 2) Do something sensible and stable. Silently fail and generate impossible to predict code is a third model that is only of use to compiler writers. Hiding behind the spec benefits no actual user.
  - opnitro 2y ago
    I think this is a point of view that seems sensible, but probably hasn't really thought through how this works. For example some_array[i] What should the compiler emit here? Should it emit a bounds check? In the event the bounds check fails, what should it do? It is only through the practice of undefined behavior that the compiler can consistently generate code that avoids the bounds check. (We don't need it, because if `i` is out-of-bounds then it's undefined behavior and illegal). If you think this is bad, then you're arguing against memory unsafe languages in general. A sane position is the one the Rust takes, which is by default, yes indeed you should always generate the bounds check (unless you can prove it always succeeds). But there will likely always be hot inner loops where we need to discharge the bounds checks statically. Ideally that would be done with some kind of formal reasoning support, but the industry is far that atm. For a more in depth read: https://blog.regehr.org/archives/213 https://blog.regehr.org/archives/213
    - Dylan16807 2y ago
      > What should the compiler emit here? It should emit an instruction to access memory location some_array + i. That's all most people that complain about optimizations on undefined behavior want. Sometimes there are questions that are hard to answer, but in a situation like this, the answer is "Try it and hope it doesn't corrupt memory." The behavior that's not wanted is for the compiler to wildly change behavior on purpose when something is undefined. For example, the compiler could optimize if(foo) { misbehaving_code(); return puppies; } else { delete_data(); } into delete_data();
      - g15jv2dp 2y ago
- userbinator 2y ago
  Calling the compiler buggy for not doing what you want when you commit Undefined Behavior is like calling dd buggy for destroying your data when you call it with the wrong arguments. No, it's like calling dd buggy for deliberately zeroing all your drives when you call it with no arguments. How did we let pedantic brainless "but muh holy standards!!!1" religious brigading triumph over common sense? The standards left things undefined in the hopes that the language would be more widely applicable and implementers would give those areas thought themselves and decide the right thing. Not so that compiler writers can become adversarial smartasses. It even suggests that "behaving in a manner characteristic of the environment" is a possible outcome of UB, which is what "the spirit of C" is all about. In my observations this gross exploitation of UB started with the FOSS compilers, GCC and Clang being the notable examples. MSVC or ICC didn't need to be so crazy, and yet they were very competitive, so I don't believe claims that UB is necessary for optimisation. The good thing about FOSS is that those in power can easily be changed. Perhaps it's time to fork, fix, and fight back.
  - jjnoakes 2y ago
    > The standards left things undefined in the hopes that the language would be more widely applicable and implementers would give those areas thought themselves and decide the right thing. That sounds like implementation-defined behavior, not undefined behavior.
    - userbinator 2y ago
      Same difference. You still have to think about what's right.
      - jjnoakes 2y ago
        They are different by definition.
  - bee_rider 2y ago
    > The good thing about FOSS is that those in power can easily be changed. Perhaps it's time to fork, fix, and fight back. Huzzah! Lead on, then.
- aleksi 2y ago
  Russ Cox has a nice article about it: C and C++ Prioritize Performance over Correctness (https://research.swtch.com/ub https://research.swtch.com/ub)
- GTP 2y ago
  We can debate whether it's reasonable or not to optimize code based on undefined behavior. But we should at least have the compiler emit a warning when this happens. Just like we have the notorious "x makes an integer from a pointer without a cast", we could have warnings for when the compiler decides to not emit the code for an if branch checking for a null pointer or an instruction zeroing some memory right before deallocation (I think this is not UB, but still a source of security issues due to extreme optimizations).
- matheusmoreira 2y ago
  Plenty of undefined behavior is actually perfectly good code the compiler has no business screwing up in any way whatsoever. This is C, we do evil things like cast pointers to other types and overlay structures onto byte buffers. We don't really want to hear about "undefined" nonsense, we want the compiler to accept the input and generate the code we expect it to. If it's undefined, then define it. This attitude turns bugs into security vulnerabilities. There's a reason the Linux kernel is compiled with -fwrapv -fno-strict-aliasing -fno-delete-null-pointer-checks and probably many more sanity restoring flags. Those flags should actually be the default for every C project.
- nine_k 2y ago
  I would say that allowing undefined behavior is a bug in itself. It was an understandable mistake for 1970, especially for such a hacker language as C. But now if a compiler can detect UD, it should warn you about it (and mostly it does by default), and you should treat that warning as an error. So, well, yes, if the bug is due to triggering UD, some blame should fall on the developer, too.
Conscat 2y ago
Fwiw clang has a `clang::optnone` attribute to disable all optimizations on a per-function basis, and GCC has the fantastic `gnu::optimize` attribute which allows you to add or remove optimizations by name, or set the optimization level regardless of compiler flags. `gnu::optimize(0)` is similar to that clang flag. Clang also has `clang::no_builtins` to disable specifically the memcpy and memset optimizations.
- leni536 2y ago
  "The optimize attribute should be used for debugging purposes only. It is not suitable in production code. " https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute...
  - Conscat 2y ago
    That's an interesting note. I wonder why they claim this. As far as I know, `[[gnu::optimize("-fno-tree-loop-distribute-patterns")]]` (or the equivalent #pragma) is required for implementing a memcpy function in C unless you do something funky with the build system.
    - leni536 2y ago
      Maybe that's applied to the TU that defines it? I don't see it in the glibc sources.
      - anarazel 2y ago
        It's indeed used: Definition of macro: https://sourceware.org/git/?p=glibc.git;a=blob;f=include/libc-symbols.h;h=4367aa6740bff6fc6b42b562f5d9a95b6690bc50;hb=HEAD#l808 https://sourceware.org/git/?p=glibc.git;a=blob;f=include/lib... Use: https://sourceware.org/git/?p=glibc.git;a=blob;f=string/memmove.c;h=3fad5f11acdf5d8a5ae1436c1e577f050c5d5193;hb=HEAD#l42 https://sourceware.org/git/?p=glibc.git;a=blob;f=string/memm... For a bunch of other places -fno-builtin-* seems to be used.
ndesaulniers 2y ago
Compile your code with `-O0` and shut up already.
- mananaysiempre 2y ago
  Unfortunately GCC’s codegen for GCC’s x86 intrinsics headers is really remarkably awful at -O0, particularly around constant loads and broadcasts, because those usually use code that’s as naïve as possible and rely on compiler optimizations to actually turn it into a broadcast, immediate, or whatever. (I haven’t checked Clang.)
  - jjuhl 2y ago
    "Unfortunately GCC’s codegen for GCC’s x86 intrinsics headers is really remarkably awful at -O0" - but that kind of seems to be what is asked for..
    - mananaysiempre 2y ago
      No. If I say (e.g.) _mm256_set_epi32(a,b,...,c) with constant arguments (which is the preferred way to make a vector constant), I expect to see 32 aligned bytes in the constant pool and a VMOVDQA in the code, not the mess of VPINSRDs that I’ll get at -O0 and that makes it essentially impossible to write decent vectorized code. The same way that I don’t expect to see a MUL in the assembly when I write sizeof(int) * CHAR_BIT in the source (and IIRC I won’t see one). (Brought to you by a two-week investigation of a mysterious literally 100× slowdown that was caused by the fact that QA always ran a debug build and those are always compiled at -O0.)
      - jjuhl 2y ago
        Seems you want the compiler to do some optimization, to improve the generated code. Or?
        mananaysiempre 2y ago
ziml77 2y ago
Why does the code need to rely on hacks to get around optimizations? Can't they be disabled per-unit by just compiling different files with different optimization flags?
- Someone 2y ago
  You can’t realistically have a C compiler that doesn’t do any optimizations. For one thing, CPU caches are wonders of technology, but a C compiler that only uses registers for computations but stores all results in memory and issues a load for every read will be unbearingly slow. So, you need a register allocator and if you have that, you either need (A) an algorithm to spill data to memory if you run out of registers, or (B) have to refuse to compile such code. If you make choice A, any change to the code for spilling back to memory can affect timings and that can introduce a timing bug in constant-time code that isn’t branch-free. Also, there still is no guarantee that code that is constant-time on CPU X also will be on CPU Y. For example, one CPU has single-cycle 64-bit multiplication, but another doesn’t. If you make choice B, you don’t have a portable language anymore. Different CPUs have different amounts of registers, and they can have different features, so code that runs fine in on one CPU may not do so on another one (even if it has the exact same amount of registers of the same size). Phrased differently: C isn’t a language that supports writing constant-time functions. If you want that, you either have to try hard to beat a C compiler into submission, and you will fail in doing that, or choose a different language, and that likely will be one that is a lot like the assembly language of the target CPU. You could make it _look_ similar between CPUs, but there would be subtle or not so subtle differences in semantics or in what programs the language accepts for different CPUs. Having said that: a seriously dumbed down C compiler (with a simple register allocator that programmers can mostly understand, no constant folding, no optimizations replacing multiplications by bit shifts or divisions by multiplications, 100% honors ‘inline’ phrases, etc.) probably could get close to what people want. It might even have a feature where code that requires register spilling triggers a compiler error. I am not aware of any compiler with that feature, though. I wouldn’t call that C, though, as programs written in it would be a lot less portable.
  - pjmlp 2y ago
TNorthover 2y ago
I'm vaguely sympathetic to these crypto people's end goals (talking about things like constant time evaluation & secret hiding), but it's really not what general purpose compilers are even thinking about most of the time so I doubt it'll ever be more than a hack that mostly works. They'll probably need some kind of specialized compiler of their own if they want to be serious about it. Or carry on with asm.
- Retr0id 2y ago
  The author has written such a compiler: https://cr.yp.to/qhasm.html https://cr.yp.to/qhasm.html (or at least, a prototype for one)
  - jedisct1 2y ago
    Jasmin has largely replaced qhasm.
    - pjmlp 2y ago
      Jasmin is also an assembler for JVM bytecode, love overloaded names.
kstrauser 2y ago
I can't help but feel we're going to think of these as the bad old years, and that at some point we'll have migrated off of C to a language with much less UB. It's so easy to express things in C that compile but that the compiler couldn't possibly guess the intent of because C doesn't have a way to express it. For instance, in Python you can write something like: result = [something(value) for value in set_object] Because Python's set objects are unordered, it's clear that it doesn't matter in which order the items are processed, and that the order of the results doesn't matter. That opens a whole lot of optimizations at the language level that don't rely on brilliant compilers implying what the author meant. Similar code in another language with immutable data can go one step further: since something(value1) can't possibly affect something(value2), it can execute those in parallel with threads or processes or whatever else makes it go fast. Much of the optimization of C compilers is looking at patterns in the code and trying to find faster ways to do what the author probably meant. Because C lacks the ability to express much intent compared to pretty much any newer language, they have the freedom to guess, but also have to make those kinds of inferences to get decent performance. On the plus side, this might be a blessing in disguise like when the Hubble telescope needed glasses. We invented brilliant techniques to make it work despite its limitations. Once we fixed its problems, those same techniques made it perform way better than originally expected. All those C compiler optimizations, applied to a language that's not C, may give us superpowers.
- unclad5968 2y ago
  While all that makes sense in theory none of it has actually demonstrated to be faster than C. The compiler doesn't need to guess what the programmer is trying to do because C is close enough to the actual hardware that the programmer can just tell it what to do.
  - pjmlp 2y ago
    Note that C code has hardly fast outside big iron UNIX, during the 1980's and up to the mid 1990's, any half clever developer could easily outperform the generated machine code, with manually written Assembly code. Hence why games for 8 and 16 bit home computers were mostly written in Assembly, and there were books like the Zen of Assembly Programming. It was the way that optimizating compilers started to exploit UB in C, that finally made it fast enough for modern times. Modern hardware has nothing to do with C abstract machine.
saagarjha 2y ago
I was already rolling my eyes but then I saw the unironic link to “The Death of Optimizing Compilers” and they might as well have fell out of my head. Someone please explain to the crypto people that designing a general-purpose language around side-channel resistance is actually stupid since most people don’t need it, optimizations actually do help quite a lot (…if they didn’t, you wouldn’t be begging for them: -O0 exists), and the model of UB C(++) has is not going away. If you want to make your own dedicated cryptography compiler that does all this stuff I honestly think you should and I would support such a thing but when you think the whole world is conspiring against your attempts to write perfect code maybe it’s you.
- JonChesterfield 2y ago
  The crypto people really want to write slow code. That's what constant time means - your best case is as slow as your worst case. Noone else wants that so there's direct tension when they also want to work in some dialect of a general purpose language.
  - jancsika 2y ago
    > The crypto people really want to write slow code. That's what constant time means - your best case is as slow as your worst case. At least for a hot path constant-time algo, they want all cases to run as slow as the worst case. But just as important-- they want that algo to be fast as is feasible. AFAICT that's the only reason we're talking about C/C++ here. The problem with writing "slow code" would have been that all the big companies who need to go fast would have chosen to roll their own hot-shot implementations for speed of it. That would introduce more risk into the most widely-used cases, while the "safe" version would have been relegated to the least used software. Instead, the guy complaining in the article about compiler determinism wrote fast crypto things in C. AFAICT everybody just uses that. And he continues to complain about the potential of compiler indeterminacy-- indeterminacy in the name of optimization-- breaking the fast crypto things. He also points out that in the cases where optimization really matters-- like ffmpeg-- the hot path code is hand-optimized and not left up to the compiler optimizer. I'd add audio plugins to that. I'd also add fftw, which apparently has a runtime (method-space?) heuristic that checks which of its buttload of hand-optimized routines win the race on your particular cpu.
johnfn 2y ago
> The bugs admitted in the compiler changelogs are just the tip of the iceberg. Whenever possible, compiler writers refuse to take responsibility for the bugs they introduced, even though the compiled code worked fine before the "optimizations". This makes it difficult to read the rest of the article. Really? All compiler authors, as a blanket statement, act in bad faith? Whenever possible? > As a cryptographic example, benchmarks across many CPUs show that the avx2 implementation of kyber768 is about 4 times faster than portable code compiled with an "optimizing" compiler. What? This is an apples to oranges comparison. Compilers optimize all code they parse; optimizing a single algorithm will of course speed up implementations of that specific algorithm, but what about the 99.9999999% of code which is not your particular hand-optimized algorithm?
- marcus0x62 2y ago
  > This makes it difficult to read the rest of the article. Really? All compiler authors, as a blanket statement, act in bad faith? Whenever possible? When I saw the link was to DJB’s site, I figured the post would contain a vitriolic and hyperbolic rant. It’s pretty on-brand for him (although, to be fair, he’s usually right.)
  - josephcsible 2y ago
    > (although, to be fair, he’s usually right.) This is worth emphasizing. I actually can't think of any articles of his other than this one that miss the mark.
    - jonhohle 2y ago
      I’m not sure this one is wrong, especially if you’ve been bitten by underdocumented compiler or framework changes that modify behavior of previously working code. For example, I have a small utility app built against SwiftUI for macOS 13. Compiling on macOS 14 while still linking against frameworks for 13 results in broken UI interaction in a particular critical use case. This was a deliberate change made to migrate devs away from a particular API, but it fails silently at compile time and runtime. Moving the code back to a macOS 13 machine would produce the correct result. As a dev, I can no longer trust that linking against specific library version will produce the same result and now need to think of some tuple of compile host and library version At one point should working code be considered correct and complete when compiler writers change code generation that doesn’t depend on UB? I’m sure it’s worse for JITed languages where constant time operations work in test and for the first few hundred iterations and then are “optimized” into variable time branching instructions on a production host somewhere.
dathinab 2y ago
> [..] whenever possible, compiler writers refuse to take responsibility for the bugs they introduced I have seldomly seen someone discredit their expertise that fast in a blog post. (Especially if you follow the link and realized it's just basic fundamental C stuff of UB not meaning it produces an "arbitrary" value.)
- dataflow 2y ago
  No, I think you're just speaking past each other here. You're using "bug" in reference to the source code. They're using "bug" in reference to the generated program. With UB it's often the case that the source code is buggy but the generated program is still correct. Later the compiler authors introduce a new optimization that generates a buggy program based on UB in the source code, and the finger-pointing starts. Edit: What nobody likes to admit is that all sides share responsibility to the users here, and that is hard to deal with. People just want a single entity to offload the responsibility to, but reality doesn't care. To give an extreme analogy to get the point across: if your battery caught fire just because your CRUD app dereferenced NULL, nobody (well, nobody sane) would point the finger at the app author for forgetting to check for NULL. The compiler, OS, and hardware vendors would be held accountable for their irresponsibly-designed products, "undefined behavior" in the standard be damned. Everyone in the supply chain shares a responsibility to anticipate how their products can be misused and handle them in a reasonable manner. The apportionment of the responsibility depends on the situation and isn't something you can just determine by just asking "was this UB in the ISO standard?"
  - RandomThoughts3 2y ago
    > if your battery caught fire just because your CRUD app dereferenced NULL, nobody (well, nobody sane) would point the finger at the app author for forgetting to check for NULL. I think pretty much anyone sane would and would be right to do so. Incorrect code is, well, incorrect and safety critical code shouldn’t use UB. Plus, it’s your duty as a software producer to use an appropriate toolchain and validate the application produced. You can’t offload the responsibility of your failure to do so to a third party (doesn’t stop people for trying all the time with either their toolchains or a library they use but that shouldn’t be tolerated and be pointed as the failure to properly test and validate it is). I would be ashamed if fingers were pointed towards a compiler provider there unless said provider certified that its compiler wouldn’t do that and somehow lied (but even then, still a testing failure on the software producer part).
leni536 2y ago
C and C++ are unsuitable for writing algorithms with constant-time guarantees. The standards have little to no notion of real time, and compilers don't offer additional guarantees as extensions. But blaming the compiler devs for this is just misguided.
- quietbritishjim 2y ago
  That was my thought reading this article. If you want to produce machine code that performs operations in constant time regardless of the branch taken, you need to use a language that supports expressing that, which C does not.
  - actionfromafar 2y ago
    Heck, CPUs themselves aren't suitable for constant time operations. At any time, some new CPU can be released which changes how quick some operations are.
    - quietbritishjim 2y ago
      Or microcode updates to existing CPUs!
    - IshKebab 2y ago
      Not always. At least for RISC-V there is the Zkt extension which guarantees data independent execution time for some instructions. I assume there's something similar for ARM and x86. It does pretty much require you to write assembly though. I think it would definitely make sense to have some kind of `[constant_time]` attribute for C++ that instructed the compiler to ensure the code is constant time.
    - NohatCoder 2y ago
      It is not a problem that different CPUs have different execution time, the problem is if the same CPU, running the same instruction has a timing difference depending on the data it operates on. In this regard CPUs have actually gotten better, specifically because it is a feature that AMD and Intel has pursued.
quuxplusone 2y ago
The author's Clang patch is interesting, but I wonder if what he really wants is, like, a new optimization level "-Obranchless" which is like O2/O3 but disables all optimizations which might introduce new conditional branches. Presumably optimizations that _remove_ branches are fine; it's just that you don't want any deliberately branchless subexpression being replaced with a branch. Basically like today's "-Og/-Odebug" or "-fno-omit-frame-pointers" but for this specific niche. I'd be interested to see a post comparing the performance and vulnerability of the mentioned crypto code with and without this (hypothetical) -Obranchless.
- quuxplusone 2y ago
  ... except that even my idea fails to help with software math. If the programmer writes `uint128 a, b; ... a /= b` under -Obranchless, does that mean they don't want us calling a C++-runtime software division routine (__udiv3 or however it's spelled) that might contain branches? And if so, then what on earth do we do instead? — well, just give an error at compile time, I guess.
  - nolist_policy 2y ago
    Not branchless, they just need it to be constant-time. That is definitely doable with pure software division.
  - detaro 2y ago
    Yes, a compile failure would IMHO be the only useful result in that case.
o11c 2y ago
Complains about branching, but doesn't even mention `__builtin_expect_with_probability`.
- Retr0id 2y ago
  Why is that relevant?
- dchest 2y ago
  There's no point in mentioning something that doesn't solve the issue.
  - o11c 2y ago
    It's as close an answer as you're going to get while using a language that's unsuitable for the issue. And in practice it's pretty reliable at generating `cmov`s ...
zokier 2y ago
It's free software, they are completely free to fork it make it have whatever semantics they want if they don't like the ISO C semantics. They can't really expect someone else to do that for them for free, and especially this sort of post is not exactly the sort of thing that would any of the compiler people to come to djbs side
Retr0id 2y ago
What I'd really like is a way to express code in a medium/high level language, and provide hand-optimized assembly code alongside it (for as many target architectures as you need). For a first-pass, you could machine-generate that assembly, and then manually verify that it's constant time (for example) and perform additional optimizations over the top of that, by hand. The "compiler"'s job would then be to assert that the behaviour of the source matches the behaviour of the provided assembly. (This is probably a hard/impossible problem to solve in the general case, but I think it'd be solvable in enough cases to be useful) To me this would offer the best of both worlds - readable, auditable source code, alongside high-performance assembly that you know won't randomly break in a future compiler update.
amluto 2y ago
It’s worth noting that, on Intel CPUs, neither clang nor anything else can possibly generate correct code, because correct code does not exist in user mode. https://www.intel.com/content/www/us/en/developer/articles/technical/software-security-guidance/best-practices/data-operand-independent-timing-isa-guidance.html https://www.intel.com/content/www/us/en/developer/articles/t... Look at DOITM in that document — it is simply impossible for a userspace crypto library to set the required bit.
- IAmLiterallyAB 2y ago
  Couldn't you syscall into the kernel to set the flag, then return back into usermode with it set?
  - amluto 2y ago
    So your compiler is supposed to emit a pair of syscalls each function that does integer math? Never mind that a pair of syscalls that do WRMSR may well take longer than whatever crypto operation is between them. I have absolutely nothing good to say about Intel’s design here.
    - pvillano 2y ago
      What's the alternative?
      - amluto 2y ago
        An instruction prefix that makes instructions constant time. A code segment bit (ugly but would work). Different instructions. Making constant time the default. A control register that’s a user register.
        convolvatron 2y ago
        since we already have some reasons to sign in an enclave, why not just design a cryptographic processor which is highly unoptimized and highly predictable. since the majority of codes benefit immensely from the optimizations, it doesn't seem reasonable to cripple them.
wolf550e 2y ago
> It would be interesting to study what percentage of security failures can be partly or entirely attributed to compiler "optimizations". I bet it's roughly none.
- g-b-r 2y ago
  Oh yeah, because no security failure was ever related to undefined behavior
  - uecker 2y ago
    This is a different question though. A lot of UB issues are related to out-of-bounds accesses and use-after-free. But those are problematic also without optimization. The cases where optimization introduce security issues are more subtle and less common. Signed overflow related issues come to mind, but there I think UB isnow part of the solution via sanitizers (and errors related to unsigned wraparound which is defined is the far more vexing problem) and similar for dereferencing null pointers which can also easily be catched by sanitizers.
- JonChesterfield 2y ago
  Deleting null pointer checks in the Linux kernel is the first one to come to mind
  - wolf550e 2y ago
    That's one CVE, right? How many other vulnerabilities were caused by compiler optimizations, whether they were bugs in the compiler or allowed by the spec?
    - JonChesterfield 2y ago
      You can probably enumerate them by searching for GCC compiler flags in the corresponding bug tracker. Start with ftrapv and fno-strict-aliasing. Those diverge-from-c flags exist to make code slower in exchange for not being broken.
tomcam 2y ago
UB means undefined behavior Somehow it took me long minutes to infer this.
AndyKelley 2y ago
If you don't like C's semantics then how about using a different programming language instead of getting angry at compiler engineers.
- nrr 2y ago
  I'm honestly unsure whether djb would actually find anything other than his qhasm tolerable (yes, even Zig). I find this particular commentary from him unsurprising.
  - renox 2y ago
    Zig will remove many UB but it will add a new nasty one in case of pass by value parameter aliasing with a parameter passed by pointer.. *: https://ziglang.org/documentation/master/#toc-Pass-by-value-Parameters https://ziglang.org/documentation/master/#toc-Pass-by-value-...
krackers 2y ago
Refreshing post that conveys a perspective I haven't seen voiced often. See also: https://gavinhoward.com/2023/08/the-scourge-of-00ub/ https://gavinhoward.com/2023/08/the-scourge-of-00ub/
quohort 2y ago
Very interesting article and much-needed criticism of the current standard of heuristic optimization. Before reading this, I thought that a simple compiler could never usefully compete against optimizing compilers (which require more manpower to produce), but perhaps there is a niche use-case for a compiler with better facilities for manual optimization. This article has inspired me to make a simple compiler myself.
- krackers 2y ago
  You don't need to get rid of all optimizations though, just the "unsafe" ones. And you could always make them opt-in instead of opt-out. Now I'm definitely closer to a noob, but compilers already have flags like no-strict-overflow and no-delete-null-pointer-checks. I don't see why we can't make these the default options. It's already "undefined behavior" per the spec, so why not make it do something sensible. The only danger is that some pedant comes along and says that with these assumptions what you're now writing isn't "portable C" and relies on compiler-defined behavior, but in the real world if it does the correct thing I don't think anyone would care: just call your dialect "boringC" instead of C99 or something (borrowing Gavin Howard's term), and the issue disappears.
  - quohort 2y ago
    > And you could always make them opt-in instead of opt-out. > The only danger is that some pedant comes along and says that with these assumptions what you're now writing isn't "portable C" and relies on compiler-defined behavior, but in the real world if it does the correct thing I don't think anyone would care: just call your dialect "boringC" instead of C99 or something (borrowing Gavin Howard's term), and the issue disappears. My idea is to make a new language with some simple syntax like S-expressions. Compilation would be (almost entirely) done with lisp-like macros, but unlike lisp it would be an imperative language rather than a functional language. The main data structure would have to be a hierarchy (analogous to CONS) to facilitate these macros. Optimizations (and Specializations) would be opt-in and would depend on the intrinsics and macros you allow in compilation. For example, you could start writing code with this default data structure, and later swap it out for some more specific data structure like a linked list or a hashtable. The most daunting problem is the issue of how the compiler selects what optimization or specializations to use; Optimizing for something like code size is straightforward, but optimizing for code speed will depend on what branches are taken at runtime. Now I suppose that the language should simply allow the programmer to manually express their preferences (which could be discovered through benchmarks/code studies). I think that this could have a niche for manually-optimized code that requires strict static analysis and straight-forward compilation. It also could have a niche in decompilation/recompilation/reverse-engineering (I think that a similar process can run in reverse to disassemble even obfuscated code, because you could easily write a macro to reverse an ad-hoc obfuscation mechanism). Here is another application of the language: By controlling the macros and intrinsics available at compilation, you could ensure compile-time security of userspace programs. For example, you could have a setup such that speculative execution vulnerabilities and the like are impossible to compile. I think you could safely enforce cooperative multitasking between programs. I'll probably start with a simple assembly language like WASM, then LLVM-IR. Eventually it would have JS/C/Rust bindings to interoperate with normal libraries. Lastly, I would like to make it so you can write routines that are portable between CPUs, GPUs, and even FPGAs, but this would be very difficult and this functionality may better realized with a functional language (e.g. CLASP https://github.com/clasp-developers/clasp https://github.com/clasp-developers/clasp) or may require programmers to work at an uncomfortably high level of abstraction.
gumby 2y ago
I like Bernstein but sometimes he flies off the handle in the wrong direction. This is a good example, which he even half-heartedly acknowledges at the end! A big chunk of the essay is about a side point — how good the gains of optimization might be, which, even with data, would be a use-case dependent decision. But the bulk of his complaint is that C compilers fail to take into account semantics that cannot be expressed in the language. Wow, shocker! At the very end he says “use a language which can express the needed semantics”. The entire essay could have been replaced with that sentence.
- quohort 2y ago
  > A big chunk of the essay is about a side point — how good the gains of optimization might be, which, even with data, would be a use-case dependent decision. I think this was useful context, and it was eye-opening to me.
  - gumby 2y ago
    If you were not aware of this then you might reflect on the part of my comment that he doesn’t bring up: how good/bad are use-case dependent. Every program optimizes for a use case, sometimes pessimizing for others (e.g. an n^2 algo that’s worthwhile because it is believed to only be called on tiny vectors). IMHO he was overgenerous on the optimization improvement of compilers. Often an optimization will make a difference in a tiny fraction of a percent. The value comes from how often that optimization can be applied, and how lots of optimizations can in aggregate make a bigger improvement just as a sand dune is made of tiny grains of sand.
    - quohort 2y ago
      certainly
- bhk 2y ago
  There's an important point to be made here: those who define the semantics of C and C++ shovel an unreasonable amount of behavior into the bucket of "undefined behavior". Much of this has dubious justifications, while making it more difficult to write correct programs.
_orz_ 2y ago
What an interesting discussion. Especially everything about that writing it in Asm would be the solution if you want secure code. Both, gcc and clang, are orders of magnitude better tested than all the closed source applications, developed under tight timelines and that we essentially trust our lives with. To be very clear, there are compiler bugs but those are almost never the problem in the first place. In the vast majority of cases it starts with buggy user code. An now back to handwritten assembly…
jancsika 2y ago
Ok, as far as the efficacy/importance/tradeoff of optimizing compilers... How do Firefox and Chrome perform if they are compiled at -O0?
gok 2y ago
Computer security is not a serious field. There is no other group that honestly feels "do what I meant, not what I said" is a sign of someone else's bug.
inglor_cz 2y ago
Similarly to not checking array bounds, undefined behavior was once introduced in the name of efficiency - back in the ages when the performance difference really mattered. And both are just a major headache now, and belong to reasons why few people start new projects in C. I wonder how many such design decisions, relevant today, but with a potential to screw up future humanity, we are making right now.
red_admiral 2y ago
So, should we be compiling security-critical code with `-O0` then?
GTP 2y ago
As someone that knows C but isn't familiar with compiler internals, I ask: would the disruptive optimizations discussed here kick in even when compiling with ootimizations tured off (-o0)? C has also other issues related to undefined behavior and it being used for what I call "extreme optimizations" (e.g. not emitting code for an if branch that checks for a null pointer). Rust is emerging as an alternative to C that aims to fix many of its problems, but how does it fares in terms of writing constant-time code? Is it similar to C, easier or more complicated?
- josephg 2y ago
  The rust compiler uses LLVM in the backend, so you still get all the same wild, complex compiler tricks at play. One of the most surprising to me is that you can sometimes improve performance by adding asserts in rust's code. For example, if you write this code: for i in 0..1_000_000 { do_stuff(my_array[i]); } Then the compiler will do array bounds checking in each loop iteration. If you instead add an assert!(my_array.len() >= 1_000_000) before the loop, the compiler knows the bounds checks aren't needed and the loop runs faster. But I think being able to rely on llvm's tricks makes rust better. For example, there's usually no overhead from writing functional code in rust using iterators. The compiler generally emits the same machine code as it would if you hand-wrote the equivalent series of for() loops.
lapinot 2y ago
Demonstrating how some languages and some compilers are bad at tasks such as writing constant-time crypto routines is fine. Concluding that all compilers and non-asm languages are bad is a non sequitur. Just because you don't want non-branching code to change into branching code doesn't mean you should have to do register allocation by hand. Write simple domain-specific compilers and languages people.
qalmakka 2y ago
I'm sick and tired of people expecting non-standard behaviour from C/C++ compilers when there are long estabished standards that clearly state what is allowed and what is not. If you are writing something like Unreal Engine and you resort on UB to get all of the performance you can get without writing assembly, then you also need to know you'll have to commit to a certain version of a certain compiler if you want a deterministic behaviour.
orf 2y ago
Man attempts to write constant time algorithms using language that does not support constant time algorithms, but who’s really at fault here? Find out on next weeks episode of “lets blame compilers rather than my choice of language”!
fhgag 2y ago
Timing attacks are a very specialized problem. If you don't care about performance, why not wrap the critical section in: #pragma GCC push_options #pragma GCC optimize ("O0") Exploiting UB in the optimizer can be annoying, but most projects with bad practices from the 1990s have figured it out by now. UBsan helps of course. I'm pretty grateful for aggressive optimizations. I would not want to compile a large C++ codebase with g++ that has itself been compiled with -O0. Even a 20% speedup helps. The only annoying issue with C/C++ compilers is the growing list of false positive warnings (usually 100% false positives in well written projects).
pcwalton 2y ago
> (As a side note, I would expect this conditional branch to slow down more code than it speeds up. But remember that compiler writers measure an "optimization" as successful if they can find any example where the "optimization" saves time.) Wildly false, and I have no idea where the author is getting this idea from. If you regress people's code in LLVM, your patch gets reverted.
afdbcreid 2y ago
A point of the post that I didn't see discussed here is this: > LLVM 11 tends to take 2x longer to compile code with optimizations, and as a result produces code that runs 10-20% faster (with occasional outliers in either direction), compared to LLVM 2.7 which is more than 10 years old. Yes, C code is expected to benefit less from optimizations, since it is already close to assembly. But compiler optimizations in the past decades had enormous impact - because they allowed better languages. Without modern optimizations, C++ would have never been as fast as C, and Rust wouldn't be possible at all. Same arguments apply to Java and JavaScript.
- temac 2y ago
  Rust is possible and proves that you don’t need "optimizations" to optimize, but that optimizations are actually possible. Now that's kind of irrelevent for most of the article focusing about constant versus variable time which is not really an "optimization" problem but already an optimization one, but at least putting appart this rust proves that a langage doesn't need to allow nasal daemons to get good perfs. You just apply the technics when you actually know they are correct, not when you speculate the existence of the mythical perfect programmer (where this hypothesis has actually be disproven by studies on the subject)
  - afdbcreid 2y ago
    I specifically addressed the claim that compiler optimization are worthless. I did not addressed the other claims in the article. In particular, however, Rust relies a lot on Undefined Behavior to optimize well. It manages to hide it (mostly) in the surface language, but in the IR they are necessary to perform well.
e40 2y ago
Was hoping the title was a pun on Spy vs Spy[0]. [0] https://en.wikipedia.org/wiki/Spy_vs._Spy https://en.wikipedia.org/wiki/Spy_vs._Spy
mgaunard 2y ago
Let's consider this function: char* strappend(char const* input, size_t size) { char* ptr = malloc(size + 2); if (!ptr) return 0; memcpy(ptr, input, size); ptr[size] = 'a'; ptr[size + 1] = 'b'; return ptr; } This function is undefined if size is SIZE_T_MAX. Many pieces of code have these sorts of "bugs", but in practice no one cares, because the input required, while theoretically possible, physically is not.
- tmyklebu 2y ago
  It does something unexpected if size is SIZE_T_MAX-1, too. And it's also undefined if input is null and size is zero, which seems more likely to surprise that function's author. This is because memcpy requires valid pointer arguments even if the size is zero. In particular, this usage invokes UB: const char *input = ""; size_t len = strlen(input); char *buf = malloc(len); // may return null if len is zero if (len) memcpy(buf, input, len); char \*buf2 = strappend(buf, len); (Edited for formatting.)
account42 2y ago
Surprised to see such an incoherent and trite rant from djb. Compilers are not your enemy. Optimizing compilers do the things they do because that's what the majority of people using them want. It also mixes in things that have nothing to do with optimizing compilers at all like expecting emulation of 64-bit integers on 32-bit platforms to be constant time when neither the language nor the library in question have ever promised such guarantees. Similar with the constant references to bool as if that's some kind of magical data type where avoiding it gives you whatever guarantees you wish. Sounds more like magical thinking than programming. I'd file this under "why can't the compiler read my mind and do what I want instead of just what I asked it to".

248 points by dchest 2y ago

> compiler writers refuse to take responsibility for the bugs they introduced, even though the compiled code worked fine before the "optimizations". The excuse for not taking responsibility is that there are "language standards" saying that these bugs should be blamed on millions of programmers writing code that bumps into "undefined behavior" But that's not an excuse for having a bug; it's the exact evidence that it's not a bug at all. Calling the compiler buggy for not doing what you want when you commit Undefined Behavior is like calling dd buggy for destroying your data when you call it with the wrong arguments.

nabla9 2y ago
Optimizing compilers that don't allow disabling all optimizations makes it impossible to write secure code with them. Must do it with assembly.
- exe34 2y ago
  clang::optnone
  - nabla9 2y ago
    "Optimizing compilers that don't allow disabling __all__ optimizations"
    - exe34 2y ago
      do these exist? who's using them?
    - layer8 2y ago
      It’s not well-defined what counts as an optimization. For example, should every single source-level read access of a memory location go through all cache levels down to main memory, instead of, for example, caching values in registers? That would be awfully slow. But that question is one reason for UB.
      - kevingadd 2y ago
        Or writing code that relies on inlining and/or tail call optimization to successfully run at all without running out of stack... We've got some code that doesn't run if compiled O0 due to that.
- cmeacham98 2y ago
  If your "secure" code is not secure because of a compiler optimization it is fundamentally incorrect and broken.
  - nabla9 2y ago
    It's secure code we use. I'm sure you know who DJB is.
    - jjuhl 2y ago
      Why is knowing who the author is relevant? Either what he posts is correct or it is not, who the person is is irrelevant.
  - hedgehog 2y ago
    There is a fundamental difference of priorities between the two worlds. For most general application code any optimization is fine as long as the output is correct. In security critical code information leakage from execution time and resource usage on the chip matters but that essentially means you need to get away from data-dependent memory access patterns and flow control.
    - account42 2y ago
      Then such code needs to be written in a language that actually makes the relevant timing guarantees. That language may be C with appropriate extensions but it certainly is not C with whining that compilers don't apply my special requirements to all code.
      - hedgehog 2y ago
        That argument would make more sense if such a language was widely available but today in practice it isn't so we live in the universe of less ideal solutions. Actually it doesn't really respond to DJB's point anyway, his case here is that the downstream labor cost of compiler churn exceeds the actual return in performance gains from new features and that a change in policy could give security-related code a more predictable target without requiring a whole new language or toolchain. For what it's worth I think the better solution will end up being something like constant-time function annotations (not stopping new compiler features) but I don't discount his view that absent human nature maybe we would be better of focusing compiler dev on correctness and stability.
- bluGill 2y ago
  If you have ub then you have a bug and there is some system that will show it. It isn't hard to write code without ub.
  - bigstrat2003 2y ago
    It is, in fact, pretty hard as evidenced by how often programmers fail at it. The macho attitude of "it's not hard, just write good code" is divorced from observable reality.
    - bluGill 2y ago
      People write buffer overflows because and memory leaks they are not coreful. The rest of ub are things I have never seen despite running sanitizers and a large codebase.
      - saagarjha 2y ago
        Perhaps you’re not looking all that hard.
        bluGill 2y ago
        Sanitizers are very good at finding ub.
        deleted 2y ago
        [deleted]
        saagarjha 2y ago
        Sure. That's just a function of how much UB there is, rather than them catching it all.
    - tbrownaw 2y ago
      Staying under the speed limit is, in fact, pretty hard as evidenced by how often drivers fail at it.
- Rusky 2y ago
  Disabling all optimizations isn't even enough- fundamentally what you need is a much narrower specification for how the source language maps to its output. Even -O0 doesn't give you that, and in fact will often be counterproductive (e.g. you'll get branches in places that the optimizer would have removed them). The problem with this is that no general purpose compiler wants to tie its own hands behind its back in this way, for the benefit of one narrow use case. It's not just that it would cost performance for everyone else, but also that it requires a totally different approach to specification and backwards compatibility, not to mention deep changes to compiler architecture. You almost may as well just design a new language, at that point.
  - amluto 2y ago
    > You almost may as well just design a new language, at that point. Forget “almost”. Go compile this C code: void foo(int *ptr) { free(ptr); *ptr = 42; } This is UB. And it has nothing whatsoever to do with optimizations — any sensible translation to machine code is a use-after-free, and an attacker can probably find a way to exploit that machine code to run arbitrary code and format your disk. If you don’t like this, use a language without UB. But djb wants something different, I think: a way to tell the compiler not to introduce timing dependencies on certain values. This is a nice idea, but it needs hardware support! Your CPU may well implement ALU instructions with data-dependent timing. Intel, for example, reserves the right to do this unless you set an MSR to tell it not to. And you cannot set that MSR from user code, so what exactly is a compiler supposed to do? https://www.intel.com/content/www/us/en/developer/articles/technical/software-security-guidance/best-practices/data-operand-independent-timing-isa-guidance.html https://www.intel.com/content/www/us/en/developer/articles/t...
    - Rusky 2y ago
      I am not talking about UB at all. I am talking about the same constant-time stuff that djb's post is talking about.
      - SAI_Peregrinus 2y ago
thayne 2y ago
The problem is that c and c++ have a ridiculous amount of undefined behavior, and it is extremely difficult to avoid all of it. One of the advantages of rust is it confines any potential UB to unsafe blocks. But even in rust, which has defined behavior in a lot of places that are UB in c, if you venture into unsafe code, it is remarkable easy to accidentally run into subtle UB issues.
- layer8 2y ago
  It’s true that UB is not intuitive at first, but “ridiculous amount” and “difficult to avoid” is overstating it. You have to have a proof-writing mindset when coding, but you do get sensitized to the pitfalls once you read up on what the language constructs actually guarantee (and don’t guarantee), and it’s not that much more difficult than, say, avoiding panics in Rust.
  - pjmlp 2y ago
    So surely you know by hear the circa 200 use cases documented in ISO C, and the even greater list documented in ISO C++ standard documents. Because, me despite knowing both since the 1990's, I rather leave that to static analysis tools.
  - tomjakubowski 2y ago
    In my experience it is very easy to accidentally introduce iterator invalidation: it starts with calling a callback while iterating, add some layers of indirection, and eventually somebody will add some innocent looking code deep down the call stack which ends up mutating the collection while it's being iterated.
    - layer8 2y ago
      I can tell you that this happens in Java as well, which doesn’t have undefined behavior. That’s just the nature of mutable state in combination with algorithms that only work while the state remains unmodified.
      - 2y ago
js2 2y ago
I think you're replying to a strawman. Here's the full quote: > The excuse for not taking responsibility is that there are "language standards" saying that these bugs should be blamed on millions of programmers writing code that bumps into "undefined behavior", rather than being blamed on the much smaller group of compiler writers subsequently changing how this code behaves. These "language standards" are written by the compiler writers. > Evidently the compiler writers find it more important to continue developing "optimizations" than to have computer systems functioning as expected. Developing "optimizations" seems to be a very large part of what compiler writers are paid to do. The argument is that the compiler writers are themselves the ones deciding what is and isn't undefined, and they are defining those standards in such a way as to allow themselves latitude for further optimizations. Those optimizations then break previously working code. The compiler writers could instead choose to prioritize backwards compatibility, but they don't. Further, these optimizations don't meaningfully improve the performance of real world code, so the trade-off of breaking code isn't even worth it. That's the argument you need to rebut.
- quohort 2y ago
  Perhaps the solution is also to reign in the language standard to support stricter use cases. For example, what if there was a constant-time { ... }; block in the same way you have extern "C" { ... }; . Not only would it allow you to have optimizations outside of the block, it would also force the compiler to ensure that a given block of code is always constant-time (as a security check done by the compiler).
  - munificent 2y ago
    > Perhaps the solution is also to reign in the language standard to support stricter use cases. Here's a nine-year-old comment from the author asking for exactly that: https://groups.google.com/g/boring-crypto/c/48qa1kWignU/m/o8GGp2K1DAAJ https://groups.google.com/g/boring-crypto/c/48qa1kWignU/m/o8...
    - fuhsnn 2y ago
      That thread already spawned a GCC-wiki page https://gcc.gnu.org/wiki/boringcc https://gcc.gnu.org/wiki/boringcc, with a quote in bold: >The only thing stopping gcc from becoming the desired boringcc is to find the people willing to do the work. And frankly, nine years is enough time to build a C compiler from scratch.
duped 2y ago
I think this is actually a mistake by the author since the rant is mostly focused on implementation defined behavior, not undefined. The examples they give are all perfectly valid code. The specific bugs they're talking about seem to be compiler optimizations that replace bit twiddling arithmetic into branches, which isn't a safe optimization if the bit twiddling happens in a cryptographic context because it opens the door for timing attacks. I don't think it's correct to call either the source code or compiler buggy, it's the C standard that is under specified to the author's liking and it creates security bugs on some targets. Ultimately though I can agree with the C standard authors that they cannot define the behavior of hardware, they can only define the semantics for the language itself. Crypto guys will have to suffer because the blame is on the hardware for these bugs, not the software.
- gabrielhidasy 2y ago
  Where suffer means "not be lazy, implement the assembly for your primitives in a lib, optimize it as best as you can without compromising security, do not let the compiler 'improve' it"
  - Dylan16807 2y ago
    But then you're not writing C, except maybe as some wrappers. Wanting to use C isn't laziness. Making it nearly unfeasible to use C is the most suffering a C compiler can inflict.
    - g15jv2dp 2y ago
      There's no reason that C should be suitable for every purpose under the sun.
      - Dylan16807 2y ago
        Fiddling some bits cross-platform is supposed to be one of them.
moomin 2y ago
There are only two models of UB that are useful to compiler users: 1) This is a bad idea and refuse to compile. 2) Do something sensible and stable. Silently fail and generate impossible to predict code is a third model that is only of use to compiler writers. Hiding behind the spec benefits no actual user.
- opnitro 2y ago
  I think this is a point of view that seems sensible, but probably hasn't really thought through how this works. For example some_array[i] What should the compiler emit here? Should it emit a bounds check? In the event the bounds check fails, what should it do? It is only through the practice of undefined behavior that the compiler can consistently generate code that avoids the bounds check. (We don't need it, because if `i` is out-of-bounds then it's undefined behavior and illegal). If you think this is bad, then you're arguing against memory unsafe languages in general. A sane position is the one the Rust takes, which is by default, yes indeed you should always generate the bounds check (unless you can prove it always succeeds). But there will likely always be hot inner loops where we need to discharge the bounds checks statically. Ideally that would be done with some kind of formal reasoning support, but the industry is far that atm. For a more in depth read: https://blog.regehr.org/archives/213 https://blog.regehr.org/archives/213
  - Dylan16807 2y ago
    > What should the compiler emit here? It should emit an instruction to access memory location some_array + i. That's all most people that complain about optimizations on undefined behavior want. Sometimes there are questions that are hard to answer, but in a situation like this, the answer is "Try it and hope it doesn't corrupt memory." The behavior that's not wanted is for the compiler to wildly change behavior on purpose when something is undefined. For example, the compiler could optimize if(foo) { misbehaving_code(); return puppies; } else { delete_data(); } into delete_data();
    - g15jv2dp 2y ago
userbinator 2y ago
Calling the compiler buggy for not doing what you want when you commit Undefined Behavior is like calling dd buggy for destroying your data when you call it with the wrong arguments. No, it's like calling dd buggy for deliberately zeroing all your drives when you call it with no arguments. How did we let pedantic brainless "but muh holy standards!!!1" religious brigading triumph over common sense? The standards left things undefined in the hopes that the language would be more widely applicable and implementers would give those areas thought themselves and decide the right thing. Not so that compiler writers can become adversarial smartasses. It even suggests that "behaving in a manner characteristic of the environment" is a possible outcome of UB, which is what "the spirit of C" is all about. In my observations this gross exploitation of UB started with the FOSS compilers, GCC and Clang being the notable examples. MSVC or ICC didn't need to be so crazy, and yet they were very competitive, so I don't believe claims that UB is necessary for optimisation. The good thing about FOSS is that those in power can easily be changed. Perhaps it's time to fork, fix, and fight back.
- jjnoakes 2y ago
  > The standards left things undefined in the hopes that the language would be more widely applicable and implementers would give those areas thought themselves and decide the right thing. That sounds like implementation-defined behavior, not undefined behavior.
  - userbinator 2y ago
    Same difference. You still have to think about what's right.
    - jjnoakes 2y ago
      They are different by definition.
- bee_rider 2y ago
  > The good thing about FOSS is that those in power can easily be changed. Perhaps it's time to fork, fix, and fight back. Huzzah! Lead on, then.
aleksi 2y ago
Russ Cox has a nice article about it: C and C++ Prioritize Performance over Correctness (https://research.swtch.com/ub https://research.swtch.com/ub)
GTP 2y ago
We can debate whether it's reasonable or not to optimize code based on undefined behavior. But we should at least have the compiler emit a warning when this happens. Just like we have the notorious "x makes an integer from a pointer without a cast", we could have warnings for when the compiler decides to not emit the code for an if branch checking for a null pointer or an instruction zeroing some memory right before deallocation (I think this is not UB, but still a source of security issues due to extreme optimizations).
matheusmoreira 2y ago
Plenty of undefined behavior is actually perfectly good code the compiler has no business screwing up in any way whatsoever. This is C, we do evil things like cast pointers to other types and overlay structures onto byte buffers. We don't really want to hear about "undefined" nonsense, we want the compiler to accept the input and generate the code we expect it to. If it's undefined, then define it. This attitude turns bugs into security vulnerabilities. There's a reason the Linux kernel is compiled with -fwrapv -fno-strict-aliasing -fno-delete-null-pointer-checks and probably many more sanity restoring flags. Those flags should actually be the default for every C project.
nine_k 2y ago
I would say that allowing undefined behavior is a bug in itself. It was an understandable mistake for 1970, especially for such a hacker language as C. But now if a compiler can detect UD, it should warn you about it (and mostly it does by default), and you should treat that warning as an error. So, well, yes, if the bug is due to triggering UD, some blame should fall on the developer, too.

Conscat 2y ago

Fwiw clang has a `clang::optnone` attribute to disable all optimizations on a per-function basis, and GCC has the fantastic `gnu::optimize` attribute which allows you to add or remove optimizations by name, or set the optimization level regardless of compiler flags. `gnu::optimize(0)` is similar to that clang flag. Clang also has `clang::no_builtins` to disable specifically the memcpy and memset optimizations.

leni536 2y ago
"The optimize attribute should be used for debugging purposes only. It is not suitable in production code. " https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute...
- Conscat 2y ago
  That's an interesting note. I wonder why they claim this. As far as I know, `[[gnu::optimize("-fno-tree-loop-distribute-patterns")]]` (or the equivalent #pragma) is required for implementing a memcpy function in C unless you do something funky with the build system.
  - leni536 2y ago
    Maybe that's applied to the TU that defines it? I don't see it in the glibc sources.
    - anarazel 2y ago
      It's indeed used: Definition of macro: https://sourceware.org/git/?p=glibc.git;a=blob;f=include/libc-symbols.h;h=4367aa6740bff6fc6b42b562f5d9a95b6690bc50;hb=HEAD#l808 https://sourceware.org/git/?p=glibc.git;a=blob;f=include/lib... Use: https://sourceware.org/git/?p=glibc.git;a=blob;f=string/memmove.c;h=3fad5f11acdf5d8a5ae1436c1e577f050c5d5193;hb=HEAD#l42 https://sourceware.org/git/?p=glibc.git;a=blob;f=string/memm... For a bunch of other places -fno-builtin-* seems to be used.

ndesaulniers 2y ago

Compile your code with `-O0` and shut up already.

mananaysiempre 2y ago
Unfortunately GCC’s codegen for GCC’s x86 intrinsics headers is really remarkably awful at -O0, particularly around constant loads and broadcasts, because those usually use code that’s as naïve as possible and rely on compiler optimizations to actually turn it into a broadcast, immediate, or whatever. (I haven’t checked Clang.)
- jjuhl 2y ago
  "Unfortunately GCC’s codegen for GCC’s x86 intrinsics headers is really remarkably awful at -O0" - but that kind of seems to be what is asked for..
  - mananaysiempre 2y ago
    No. If I say (e.g.) _mm256_set_epi32(a,b,...,c) with constant arguments (which is the preferred way to make a vector constant), I expect to see 32 aligned bytes in the constant pool and a VMOVDQA in the code, not the mess of VPINSRDs that I’ll get at -O0 and that makes it essentially impossible to write decent vectorized code. The same way that I don’t expect to see a MUL in the assembly when I write sizeof(int) * CHAR_BIT in the source (and IIRC I won’t see one). (Brought to you by a two-week investigation of a mysterious literally 100× slowdown that was caused by the fact that QA always ran a debug build and those are always compiled at -O0.)
    - jjuhl 2y ago
      Seems you want the compiler to do some optimization, to improve the generated code. Or?
      - mananaysiempre 2y ago

ziml77 2y ago

Why does the code need to rely on hacks to get around optimizations? Can't they be disabled per-unit by just compiling different files with different optimization flags?

Someone 2y ago
You can’t realistically have a C compiler that doesn’t do any optimizations. For one thing, CPU caches are wonders of technology, but a C compiler that only uses registers for computations but stores all results in memory and issues a load for every read will be unbearingly slow. So, you need a register allocator and if you have that, you either need (A) an algorithm to spill data to memory if you run out of registers, or (B) have to refuse to compile such code. If you make choice A, any change to the code for spilling back to memory can affect timings and that can introduce a timing bug in constant-time code that isn’t branch-free. Also, there still is no guarantee that code that is constant-time on CPU X also will be on CPU Y. For example, one CPU has single-cycle 64-bit multiplication, but another doesn’t. If you make choice B, you don’t have a portable language anymore. Different CPUs have different amounts of registers, and they can have different features, so code that runs fine in on one CPU may not do so on another one (even if it has the exact same amount of registers of the same size). Phrased differently: C isn’t a language that supports writing constant-time functions. If you want that, you either have to try hard to beat a C compiler into submission, and you will fail in doing that, or choose a different language, and that likely will be one that is a lot like the assembly language of the target CPU. You could make it _look_ similar between CPUs, but there would be subtle or not so subtle differences in semantics or in what programs the language accepts for different CPUs. Having said that: a seriously dumbed down C compiler (with a simple register allocator that programmers can mostly understand, no constant folding, no optimizations replacing multiplications by bit shifts or divisions by multiplications, 100% honors ‘inline’ phrases, etc.) probably could get close to what people want. It might even have a feature where code that requires register spilling triggers a compiler error. I am not aware of any compiler with that feature, though. I wouldn’t call that C, though, as programs written in it would be a lot less portable.
- pjmlp 2y ago

TNorthover 2y ago

I'm vaguely sympathetic to these crypto people's end goals (talking about things like constant time evaluation & secret hiding), but it's really not what general purpose compilers are even thinking about most of the time so I doubt it'll ever be more than a hack that mostly works. They'll probably need some kind of specialized compiler of their own if they want to be serious about it. Or carry on with asm.

Retr0id 2y ago
The author has written such a compiler: https://cr.yp.to/qhasm.html https://cr.yp.to/qhasm.html (or at least, a prototype for one)
- jedisct1 2y ago
  Jasmin has largely replaced qhasm.
  - pjmlp 2y ago
    Jasmin is also an assembler for JVM bytecode, love overloaded names.

kstrauser 2y ago

I can't help but feel we're going to think of these as the bad old years, and that at some point we'll have migrated off of C to a language with much less UB. It's so easy to express things in C that compile but that the compiler couldn't possibly guess the intent of because C doesn't have a way to express it. For instance, in Python you can write something like: result = [something(value) for value in set_object] Because Python's set objects are unordered, it's clear that it doesn't matter in which order the items are processed, and that the order of the results doesn't matter. That opens a whole lot of optimizations at the language level that don't rely on brilliant compilers implying what the author meant. Similar code in another language with immutable data can go one step further: since something(value1) can't possibly affect something(value2), it can execute those in parallel with threads or processes or whatever else makes it go fast. Much of the optimization of C compilers is looking at patterns in the code and trying to find faster ways to do what the author probably meant. Because C lacks the ability to express much intent compared to pretty much any newer language, they have the freedom to guess, but also have to make those kinds of inferences to get decent performance. On the plus side, this might be a blessing in disguise like when the Hubble telescope needed glasses. We invented brilliant techniques to make it work despite its limitations. Once we fixed its problems, those same techniques made it perform way better than originally expected. All those C compiler optimizations, applied to a language that's not C, may give us superpowers.

unclad5968 2y ago
While all that makes sense in theory none of it has actually demonstrated to be faster than C. The compiler doesn't need to guess what the programmer is trying to do because C is close enough to the actual hardware that the programmer can just tell it what to do.
- pjmlp 2y ago
  Note that C code has hardly fast outside big iron UNIX, during the 1980's and up to the mid 1990's, any half clever developer could easily outperform the generated machine code, with manually written Assembly code. Hence why games for 8 and 16 bit home computers were mostly written in Assembly, and there were books like the Zen of Assembly Programming. It was the way that optimizating compilers started to exploit UB in C, that finally made it fast enough for modern times. Modern hardware has nothing to do with C abstract machine.

saagarjha 2y ago

I was already rolling my eyes but then I saw the unironic link to “The Death of Optimizing Compilers” and they might as well have fell out of my head. Someone please explain to the crypto people that designing a general-purpose language around side-channel resistance is actually stupid since most people don’t need it, optimizations actually do help quite a lot (…if they didn’t, you wouldn’t be begging for them: -O0 exists), and the model of UB C(++) has is not going away. If you want to make your own dedicated cryptography compiler that does all this stuff I honestly think you should and I would support such a thing but when you think the whole world is conspiring against your attempts to write perfect code maybe it’s you.

JonChesterfield 2y ago
The crypto people really want to write slow code. That's what constant time means - your best case is as slow as your worst case. Noone else wants that so there's direct tension when they also want to work in some dialect of a general purpose language.
- jancsika 2y ago
  > The crypto people really want to write slow code. That's what constant time means - your best case is as slow as your worst case. At least for a hot path constant-time algo, they want all cases to run as slow as the worst case. But just as important-- they want that algo to be fast as is feasible. AFAICT that's the only reason we're talking about C/C++ here. The problem with writing "slow code" would have been that all the big companies who need to go fast would have chosen to roll their own hot-shot implementations for speed of it. That would introduce more risk into the most widely-used cases, while the "safe" version would have been relegated to the least used software. Instead, the guy complaining in the article about compiler determinism wrote fast crypto things in C. AFAICT everybody just uses that. And he continues to complain about the potential of compiler indeterminacy-- indeterminacy in the name of optimization-- breaking the fast crypto things. He also points out that in the cases where optimization really matters-- like ffmpeg-- the hot path code is hand-optimized and not left up to the compiler optimizer. I'd add audio plugins to that. I'd also add fftw, which apparently has a runtime (method-space?) heuristic that checks which of its buttload of hand-optimized routines win the race on your particular cpu.

johnfn 2y ago

> The bugs admitted in the compiler changelogs are just the tip of the iceberg. Whenever possible, compiler writers refuse to take responsibility for the bugs they introduced, even though the compiled code worked fine before the "optimizations". This makes it difficult to read the rest of the article. Really? All compiler authors, as a blanket statement, act in bad faith? Whenever possible? > As a cryptographic example, benchmarks across many CPUs show that the avx2 implementation of kyber768 is about 4 times faster than portable code compiled with an "optimizing" compiler. What? This is an apples to oranges comparison. Compilers optimize all code they parse; optimizing a single algorithm will of course speed up implementations of that specific algorithm, but what about the 99.9999999% of code which is not your particular hand-optimized algorithm?

marcus0x62 2y ago
> This makes it difficult to read the rest of the article. Really? All compiler authors, as a blanket statement, act in bad faith? Whenever possible? When I saw the link was to DJB’s site, I figured the post would contain a vitriolic and hyperbolic rant. It’s pretty on-brand for him (although, to be fair, he’s usually right.)
- josephcsible 2y ago
  > (although, to be fair, he’s usually right.) This is worth emphasizing. I actually can't think of any articles of his other than this one that miss the mark.
  - jonhohle 2y ago
    I’m not sure this one is wrong, especially if you’ve been bitten by underdocumented compiler or framework changes that modify behavior of previously working code. For example, I have a small utility app built against SwiftUI for macOS 13. Compiling on macOS 14 while still linking against frameworks for 13 results in broken UI interaction in a particular critical use case. This was a deliberate change made to migrate devs away from a particular API, but it fails silently at compile time and runtime. Moving the code back to a macOS 13 machine would produce the correct result. As a dev, I can no longer trust that linking against specific library version will produce the same result and now need to think of some tuple of compile host and library version At one point should working code be considered correct and complete when compiler writers change code generation that doesn’t depend on UB? I’m sure it’s worse for JITed languages where constant time operations work in test and for the first few hundred iterations and then are “optimized” into variable time branching instructions on a production host somewhere.

dathinab 2y ago

> [..] whenever possible, compiler writers refuse to take responsibility for the bugs they introduced I have seldomly seen someone discredit their expertise that fast in a blog post. (Especially if you follow the link and realized it's just basic fundamental C stuff of UB not meaning it produces an "arbitrary" value.)

dataflow 2y ago
No, I think you're just speaking past each other here. You're using "bug" in reference to the source code. They're using "bug" in reference to the generated program. With UB it's often the case that the source code is buggy but the generated program is still correct. Later the compiler authors introduce a new optimization that generates a buggy program based on UB in the source code, and the finger-pointing starts. Edit: What nobody likes to admit is that all sides share responsibility to the users here, and that is hard to deal with. People just want a single entity to offload the responsibility to, but reality doesn't care. To give an extreme analogy to get the point across: if your battery caught fire just because your CRUD app dereferenced NULL, nobody (well, nobody sane) would point the finger at the app author for forgetting to check for NULL. The compiler, OS, and hardware vendors would be held accountable for their irresponsibly-designed products, "undefined behavior" in the standard be damned. Everyone in the supply chain shares a responsibility to anticipate how their products can be misused and handle them in a reasonable manner. The apportionment of the responsibility depends on the situation and isn't something you can just determine by just asking "was this UB in the ISO standard?"
- RandomThoughts3 2y ago
  > if your battery caught fire just because your CRUD app dereferenced NULL, nobody (well, nobody sane) would point the finger at the app author for forgetting to check for NULL. I think pretty much anyone sane would and would be right to do so. Incorrect code is, well, incorrect and safety critical code shouldn’t use UB. Plus, it’s your duty as a software producer to use an appropriate toolchain and validate the application produced. You can’t offload the responsibility of your failure to do so to a third party (doesn’t stop people for trying all the time with either their toolchains or a library they use but that shouldn’t be tolerated and be pointed as the failure to properly test and validate it is). I would be ashamed if fingers were pointed towards a compiler provider there unless said provider certified that its compiler wouldn’t do that and somehow lied (but even then, still a testing failure on the software producer part).

leni536 2y ago

C and C++ are unsuitable for writing algorithms with constant-time guarantees. The standards have little to no notion of real time, and compilers don't offer additional guarantees as extensions. But blaming the compiler devs for this is just misguided.

quietbritishjim 2y ago
That was my thought reading this article. If you want to produce machine code that performs operations in constant time regardless of the branch taken, you need to use a language that supports expressing that, which C does not.
- actionfromafar 2y ago
  Heck, CPUs themselves aren't suitable for constant time operations. At any time, some new CPU can be released which changes how quick some operations are.
  - quietbritishjim 2y ago
    Or microcode updates to existing CPUs!
  - IshKebab 2y ago
    Not always. At least for RISC-V there is the Zkt extension which guarantees data independent execution time for some instructions. I assume there's something similar for ARM and x86. It does pretty much require you to write assembly though. I think it would definitely make sense to have some kind of `[constant_time]` attribute for C++ that instructed the compiler to ensure the code is constant time.
  - NohatCoder 2y ago
    It is not a problem that different CPUs have different execution time, the problem is if the same CPU, running the same instruction has a timing difference depending on the data it operates on. In this regard CPUs have actually gotten better, specifically because it is a feature that AMD and Intel has pursued.

quuxplusone 2y ago

The author's Clang patch is interesting, but I wonder if what he really wants is, like, a new optimization level "-Obranchless" which is like O2/O3 but disables all optimizations which might introduce new conditional branches. Presumably optimizations that _remove_ branches are fine; it's just that you don't want any deliberately branchless subexpression being replaced with a branch. Basically like today's "-Og/-Odebug" or "-fno-omit-frame-pointers" but for this specific niche. I'd be interested to see a post comparing the performance and vulnerability of the mentioned crypto code with and without this (hypothetical) -Obranchless.

quuxplusone 2y ago
... except that even my idea fails to help with software math. If the programmer writes `uint128 a, b; ... a /= b` under -Obranchless, does that mean they don't want us calling a C++-runtime software division routine (__udiv3 or however it's spelled) that might contain branches? And if so, then what on earth do we do instead? — well, just give an error at compile time, I guess.
- nolist_policy 2y ago
  Not branchless, they just need it to be constant-time. That is definitely doable with pure software division.
- detaro 2y ago
  Yes, a compile failure would IMHO be the only useful result in that case.

o11c 2y ago

Complains about branching, but doesn't even mention `__builtin_expect_with_probability`.

Retr0id 2y ago
Why is that relevant?
dchest 2y ago
There's no point in mentioning something that doesn't solve the issue.
- o11c 2y ago
  It's as close an answer as you're going to get while using a language that's unsuitable for the issue. And in practice it's pretty reliable at generating `cmov`s ...

zokier 2y ago

It's free software, they are completely free to fork it make it have whatever semantics they want if they don't like the ISO C semantics. They can't really expect someone else to do that for them for free, and especially this sort of post is not exactly the sort of thing that would any of the compiler people to come to djbs side

Retr0id 2y ago

What I'd really like is a way to express code in a medium/high level language, and provide hand-optimized assembly code alongside it (for as many target architectures as you need). For a first-pass, you could machine-generate that assembly, and then manually verify that it's constant time (for example) and perform additional optimizations over the top of that, by hand. The "compiler"'s job would then be to assert that the behaviour of the source matches the behaviour of the provided assembly. (This is probably a hard/impossible problem to solve in the general case, but I think it'd be solvable in enough cases to be useful) To me this would offer the best of both worlds - readable, auditable source code, alongside high-performance assembly that you know won't randomly break in a future compiler update.

amluto 2y ago

It’s worth noting that, on Intel CPUs, neither clang nor anything else can possibly generate correct code, because correct code does not exist in user mode. https://www.intel.com/content/www/us/en/developer/articles/technical/software-security-guidance/best-practices/data-operand-independent-timing-isa-guidance.html https://www.intel.com/content/www/us/en/developer/articles/t... Look at DOITM in that document — it is simply impossible for a userspace crypto library to set the required bit.

IAmLiterallyAB 2y ago
Couldn't you syscall into the kernel to set the flag, then return back into usermode with it set?
- amluto 2y ago
  So your compiler is supposed to emit a pair of syscalls each function that does integer math? Never mind that a pair of syscalls that do WRMSR may well take longer than whatever crypto operation is between them. I have absolutely nothing good to say about Intel’s design here.
  - pvillano 2y ago
    What's the alternative?
    - amluto 2y ago
      An instruction prefix that makes instructions constant time. A code segment bit (ugly but would work). Different instructions. Making constant time the default. A control register that’s a user register.
      - convolvatron 2y ago
        since we already have some reasons to sign in an enclave, why not just design a cryptographic processor which is highly unoptimized and highly predictable. since the majority of codes benefit immensely from the optimizations, it doesn't seem reasonable to cripple them.

wolf550e 2y ago

> It would be interesting to study what percentage of security failures can be partly or entirely attributed to compiler "optimizations". I bet it's roughly none.

g-b-r 2y ago
Oh yeah, because no security failure was ever related to undefined behavior
- uecker 2y ago
  This is a different question though. A lot of UB issues are related to out-of-bounds accesses and use-after-free. But those are problematic also without optimization. The cases where optimization introduce security issues are more subtle and less common. Signed overflow related issues come to mind, but there I think UB isnow part of the solution via sanitizers (and errors related to unsigned wraparound which is defined is the far more vexing problem) and similar for dereferencing null pointers which can also easily be catched by sanitizers.
JonChesterfield 2y ago
Deleting null pointer checks in the Linux kernel is the first one to come to mind
- wolf550e 2y ago
  That's one CVE, right? How many other vulnerabilities were caused by compiler optimizations, whether they were bugs in the compiler or allowed by the spec?
  - JonChesterfield 2y ago
    You can probably enumerate them by searching for GCC compiler flags in the corresponding bug tracker. Start with ftrapv and fno-strict-aliasing. Those diverge-from-c flags exist to make code slower in exchange for not being broken.

tomcam 2y ago

UB means undefined behavior Somehow it took me long minutes to infer this.

AndyKelley 2y ago

If you don't like C's semantics then how about using a different programming language instead of getting angry at compiler engineers.

nrr 2y ago
I'm honestly unsure whether djb would actually find anything other than his qhasm tolerable (yes, even Zig). I find this particular commentary from him unsurprising.
- renox 2y ago
  Zig will remove many UB but it will add a new nasty one in case of pass by value parameter aliasing with a parameter passed by pointer.. *: https://ziglang.org/documentation/master/#toc-Pass-by-value-Parameters https://ziglang.org/documentation/master/#toc-Pass-by-value-...

krackers 2y ago

Refreshing post that conveys a perspective I haven't seen voiced often. See also: https://gavinhoward.com/2023/08/the-scourge-of-00ub/ https://gavinhoward.com/2023/08/the-scourge-of-00ub/

quohort 2y ago

Very interesting article and much-needed criticism of the current standard of heuristic optimization. Before reading this, I thought that a simple compiler could never usefully compete against optimizing compilers (which require more manpower to produce), but perhaps there is a niche use-case for a compiler with better facilities for manual optimization. This article has inspired me to make a simple compiler myself.

krackers 2y ago
You don't need to get rid of all optimizations though, just the "unsafe" ones. And you could always make them opt-in instead of opt-out. Now I'm definitely closer to a noob, but compilers already have flags like no-strict-overflow and no-delete-null-pointer-checks. I don't see why we can't make these the default options. It's already "undefined behavior" per the spec, so why not make it do something sensible. The only danger is that some pedant comes along and says that with these assumptions what you're now writing isn't "portable C" and relies on compiler-defined behavior, but in the real world if it does the correct thing I don't think anyone would care: just call your dialect "boringC" instead of C99 or something (borrowing Gavin Howard's term), and the issue disappears.
- quohort 2y ago
  > And you could always make them opt-in instead of opt-out. > The only danger is that some pedant comes along and says that with these assumptions what you're now writing isn't "portable C" and relies on compiler-defined behavior, but in the real world if it does the correct thing I don't think anyone would care: just call your dialect "boringC" instead of C99 or something (borrowing Gavin Howard's term), and the issue disappears. My idea is to make a new language with some simple syntax like S-expressions. Compilation would be (almost entirely) done with lisp-like macros, but unlike lisp it would be an imperative language rather than a functional language. The main data structure would have to be a hierarchy (analogous to CONS) to facilitate these macros. Optimizations (and Specializations) would be opt-in and would depend on the intrinsics and macros you allow in compilation. For example, you could start writing code with this default data structure, and later swap it out for some more specific data structure like a linked list or a hashtable. The most daunting problem is the issue of how the compiler selects what optimization or specializations to use; Optimizing for something like code size is straightforward, but optimizing for code speed will depend on what branches are taken at runtime. Now I suppose that the language should simply allow the programmer to manually express their preferences (which could be discovered through benchmarks/code studies). I think that this could have a niche for manually-optimized code that requires strict static analysis and straight-forward compilation. It also could have a niche in decompilation/recompilation/reverse-engineering (I think that a similar process can run in reverse to disassemble even obfuscated code, because you could easily write a macro to reverse an ad-hoc obfuscation mechanism). Here is another application of the language: By controlling the macros and intrinsics available at compilation, you could ensure compile-time security of userspace programs. For example, you could have a setup such that speculative execution vulnerabilities and the like are impossible to compile. I think you could safely enforce cooperative multitasking between programs. I'll probably start with a simple assembly language like WASM, then LLVM-IR. Eventually it would have JS/C/Rust bindings to interoperate with normal libraries. Lastly, I would like to make it so you can write routines that are portable between CPUs, GPUs, and even FPGAs, but this would be very difficult and this functionality may better realized with a functional language (e.g. CLASP https://github.com/clasp-developers/clasp https://github.com/clasp-developers/clasp) or may require programmers to work at an uncomfortably high level of abstraction.

gumby 2y ago

I like Bernstein but sometimes he flies off the handle in the wrong direction. This is a good example, which he even half-heartedly acknowledges at the end! A big chunk of the essay is about a side point — how good the gains of optimization might be, which, even with data, would be a use-case dependent decision. But the bulk of his complaint is that C compilers fail to take into account semantics that cannot be expressed in the language. Wow, shocker! At the very end he says “use a language which can express the needed semantics”. The entire essay could have been replaced with that sentence.

quohort 2y ago
> A big chunk of the essay is about a side point — how good the gains of optimization might be, which, even with data, would be a use-case dependent decision. I think this was useful context, and it was eye-opening to me.
- gumby 2y ago
  If you were not aware of this then you might reflect on the part of my comment that he doesn’t bring up: how good/bad are use-case dependent. Every program optimizes for a use case, sometimes pessimizing for others (e.g. an n^2 algo that’s worthwhile because it is believed to only be called on tiny vectors). IMHO he was overgenerous on the optimization improvement of compilers. Often an optimization will make a difference in a tiny fraction of a percent. The value comes from how often that optimization can be applied, and how lots of optimizations can in aggregate make a bigger improvement just as a sand dune is made of tiny grains of sand.
  - quohort 2y ago
    certainly
bhk 2y ago
There's an important point to be made here: those who define the semantics of C and C++ shovel an unreasonable amount of behavior into the bucket of "undefined behavior". Much of this has dubious justifications, while making it more difficult to write correct programs.

_orz_ 2y ago

What an interesting discussion. Especially everything about that writing it in Asm would be the solution if you want secure code. Both, gcc and clang, are orders of magnitude better tested than all the closed source applications, developed under tight timelines and that we essentially trust our lives with. To be very clear, there are compiler bugs but those are almost never the problem in the first place. In the vast majority of cases it starts with buggy user code. An now back to handwritten assembly…

jancsika 2y ago

Ok, as far as the efficacy/importance/tradeoff of optimizing compilers... How do Firefox and Chrome perform if they are compiled at -O0?

gok 2y ago

Computer security is not a serious field. There is no other group that honestly feels "do what I meant, not what I said" is a sign of someone else's bug.

inglor_cz 2y ago

Similarly to not checking array bounds, undefined behavior was once introduced in the name of efficiency - back in the ages when the performance difference really mattered. And both are just a major headache now, and belong to reasons why few people start new projects in C. I wonder how many such design decisions, relevant today, but with a potential to screw up future humanity, we are making right now.

red_admiral 2y ago

So, should we be compiling security-critical code with `-O0` then?

GTP 2y ago

As someone that knows C but isn't familiar with compiler internals, I ask: would the disruptive optimizations discussed here kick in even when compiling with ootimizations tured off (-o0)? C has also other issues related to undefined behavior and it being used for what I call "extreme optimizations" (e.g. not emitting code for an if branch that checks for a null pointer). Rust is emerging as an alternative to C that aims to fix many of its problems, but how does it fares in terms of writing constant-time code? Is it similar to C, easier or more complicated?

josephg 2y ago
The rust compiler uses LLVM in the backend, so you still get all the same wild, complex compiler tricks at play. One of the most surprising to me is that you can sometimes improve performance by adding asserts in rust's code. For example, if you write this code: for i in 0..1_000_000 { do_stuff(my_array[i]); } Then the compiler will do array bounds checking in each loop iteration. If you instead add an assert!(my_array.len() >= 1_000_000) before the loop, the compiler knows the bounds checks aren't needed and the loop runs faster. But I think being able to rely on llvm's tricks makes rust better. For example, there's usually no overhead from writing functional code in rust using iterators. The compiler generally emits the same machine code as it would if you hand-wrote the equivalent series of for() loops.

lapinot 2y ago

Demonstrating how some languages and some compilers are bad at tasks such as writing constant-time crypto routines is fine. Concluding that all compilers and non-asm languages are bad is a non sequitur. Just because you don't want non-branching code to change into branching code doesn't mean you should have to do register allocation by hand. Write simple domain-specific compilers and languages people.

qalmakka 2y ago

I'm sick and tired of people expecting non-standard behaviour from C/C++ compilers when there are long estabished standards that clearly state what is allowed and what is not. If you are writing something like Unreal Engine and you resort on UB to get all of the performance you can get without writing assembly, then you also need to know you'll have to commit to a certain version of a certain compiler if you want a deterministic behaviour.

orf 2y ago

Man attempts to write constant time algorithms using language that does not support constant time algorithms, but who’s really at fault here? Find out on next weeks episode of “lets blame compilers rather than my choice of language”!

fhgag 2y ago

Timing attacks are a very specialized problem. If you don't care about performance, why not wrap the critical section in: #pragma GCC push_options #pragma GCC optimize ("O0") Exploiting UB in the optimizer can be annoying, but most projects with bad practices from the 1990s have figured it out by now. UBsan helps of course. I'm pretty grateful for aggressive optimizations. I would not want to compile a large C++ codebase with g++ that has itself been compiled with -O0. Even a 20% speedup helps. The only annoying issue with C/C++ compilers is the growing list of false positive warnings (usually 100% false positives in well written projects).

pcwalton 2y ago

> (As a side note, I would expect this conditional branch to slow down more code than it speeds up. But remember that compiler writers measure an "optimization" as successful if they can find any example where the "optimization" saves time.) Wildly false, and I have no idea where the author is getting this idea from. If you regress people's code in LLVM, your patch gets reverted.

afdbcreid 2y ago

A point of the post that I didn't see discussed here is this: > LLVM 11 tends to take 2x longer to compile code with optimizations, and as a result produces code that runs 10-20% faster (with occasional outliers in either direction), compared to LLVM 2.7 which is more than 10 years old. Yes, C code is expected to benefit less from optimizations, since it is already close to assembly. But compiler optimizations in the past decades had enormous impact - because they allowed better languages. Without modern optimizations, C++ would have never been as fast as C, and Rust wouldn't be possible at all. Same arguments apply to Java and JavaScript.

temac 2y ago
Rust is possible and proves that you don’t need "optimizations" to optimize, but that optimizations are actually possible. Now that's kind of irrelevent for most of the article focusing about constant versus variable time which is not really an "optimization" problem but already an optimization one, but at least putting appart this rust proves that a langage doesn't need to allow nasal daemons to get good perfs. You just apply the technics when you actually know they are correct, not when you speculate the existence of the mythical perfect programmer (where this hypothesis has actually be disproven by studies on the subject)
- afdbcreid 2y ago
  I specifically addressed the claim that compiler optimization are worthless. I did not addressed the other claims in the article. In particular, however, Rust relies a lot on Undefined Behavior to optimize well. It manages to hide it (mostly) in the surface language, but in the IR they are necessary to perform well.

e40 2y ago

Was hoping the title was a pun on Spy vs Spy[0]. [0] https://en.wikipedia.org/wiki/Spy_vs._Spy https://en.wikipedia.org/wiki/Spy_vs._Spy

mgaunard 2y ago

Let's consider this function: char* strappend(char const* input, size_t size) { char* ptr = malloc(size + 2); if (!ptr) return 0; memcpy(ptr, input, size); ptr[size] = 'a'; ptr[size + 1] = 'b'; return ptr; } This function is undefined if size is SIZE_T_MAX. Many pieces of code have these sorts of "bugs", but in practice no one cares, because the input required, while theoretically possible, physically is not.

tmyklebu 2y ago
It does something unexpected if size is SIZE_T_MAX-1, too. And it's also undefined if input is null and size is zero, which seems more likely to surprise that function's author. This is because memcpy requires valid pointer arguments even if the size is zero. In particular, this usage invokes UB: const char *input = ""; size_t len = strlen(input); char *buf = malloc(len); // may return null if len is zero if (len) memcpy(buf, input, len); char \*buf2 = strappend(buf, len); (Edited for formatting.)

account42 2y ago

Surprised to see such an incoherent and trite rant from djb. Compilers are not your enemy. Optimizing compilers do the things they do because that's what the majority of people using them want. It also mixes in things that have nothing to do with optimizing compilers at all like expecting emulation of 64-bit integers on 32-bit platforms to be constant time when neither the language nor the library in question have ever promised such guarantees. Similar with the constant references to bool as if that's some kind of magical data type where avoiding it gives you whatever guarantees you wish. Sounds more like magical thinking than programming. I'd file this under "why can't the compiler read my mind and do what I want instead of just what I asked it to".