Clang vs. Clang • Hacker News Board

Re: Clang vs. Clang

#141

Post by Dylan16807 » Sat, Aug 03, 2024, 11:49 PM UTC

opnitro wrote: post #137

moomin wrote: post #134

Earlier quoted context omitted.

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.

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…

> 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();

Re: Clang vs. Clang

#142

Post by gumby » Sat, Aug 03, 2024, 11:50 PM UTC

quohort wrote: post #97

gumby wrote: post #94

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 expre…

> 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.

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.

Re: Clang vs. Clang

#143

Post by skissane » Sat, Aug 03, 2024, 11:50 PM UTC

amluto wrote: post #42

Rusky wrote: post #24

Earlier quoted context omitted.

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 thi…

> 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…

It isn't just UB to dereference `ptr` after `free(ptr)` – it is UB to do anything with its value whatsoever. For example, this is UB:

    void foo(int *ptr)
    {
        assert(ptr != NULL);
        free(ptr);
        assert(ptr != NULL);
    }

Why is that? Well, I think because the C standard authors wanted to support the language being used on platforms with "fat pointers", in which a pointer is not just a memory address, but some kind of complex structure incorporating flags and capabilities (e.g. IBM System/38 and AS/400; Burroughs Large Systems; Intel iAPX 432, BiiN and i960 extended architecture; CHERI and ARM Morello). And, on such a system, they wanted to permit implementors to make `free()` a "pass-by-reference" function, so it would actually modify the value of its argument. (C natively doesn't have pass-by-reference, unlike C++, but there is nothing stopping a compiler adding it as an extension, then using it to implement `free()`.)

See this discussion of the topic from 8 years back: https://news.ycombinator.com/item?id=11235385

> And you cannot set that MSR from user code, so what exactly is a compiler supposed to do?

Set a flag in the executable which requires that MSR to be enabled. Then the OS will set the MSR when it loads the executable, or refuse to load it if it won't.

Another option would be for the OS to expose a user space API to read that MSR. And then the compiler emits a check at the start of security-sensitive code to call that API and abort if the MSR doesn't have the required value. Or maybe even, the OS could let you turn the MSR on/off on a per-thread basis, and just set it during security-sensitive processing.

Obviously, all these approaches require cooperation with the OS vendor, but often the OS vendor and compiler vendor is the same vendor (e.g. Microsoft)–and even when that isn't true, compiler and kernel teams often work closely together.

Re: Clang vs. Clang

#144

Post by dathinab » Sat, Aug 03, 2024, 11:54 PM UTC

mpweiher wrote: post #101

dathinab wrote: post #88

Earlier quoted context omitted.

But C never had been portable assembly. Which I think is somewhat the core of the problem. People treating things in C in ways they just are not. Weather that is C is portable assembly or C the "it's just bit's in memory" view of things (which often is double wrong ignoring stuff like hardware caching). Or stuff like writing const time code based on assuming that the compiler probably, hopefully can't figure out that…

> But C never had been portable assembly. The ANSI C standards committee disagrees with you. "Committee did not want to force programmers into writing portably, to preclude the use of C as a “high-level assembler:” https://www.open-std.org/JTC1/SC22/WG14/www/docs/n897.pdf p 2, line 39. (p10 of the PDF) "C code can be portable. " line 30

The full quote is:

> Although it strove to give programmers the opportunity to write truly portable programs, the C89 Committee did not want to force programmers into writing portably, to preclude the use of C as a “high-level assembler:” the ability to write machine-specific code is one of the strengths of C. It is this principle which largely motivates drawing the distinction between strictly conforming program and conforming program (§4).

This doesn't say that C is a high-level assembly.

It just says that the committee doesn't (at that point in time) wants to force the usage of "portable" C as a mean to prevent the usage of C as high-level assembler. But just because some people use something as high level assembler doesn't mean it is high level assembly (like I did use a spoon as a fork once, it's still a spoon).

Furthermore the fact that they explicitly mention forcing portable C with the terms "to preclude" and not "to break compatibility" or similar I think says a lot about weather or not the committee thought of C as high level assembly.

Most importantly the quote is about the process of making the first C standard which had to make sure to ease the transition from various non standardized C dialects to "standard C" and I'm pretty sure that through the history there had been C dialects/compiler implementations which approached C as high level assembly, but C as in "standard C" is not that.

Re: Clang vs. Clang

#145

Post by gabrielhidasy » Sat, Aug 03, 2024, 11:54 PM UTC

duped wrote: post #95

josephcsible wrote: post #2

> 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…

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 th…

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"

Re: Clang vs. Clang

#146

Post by Dylan16807 » Sun, Aug 04, 2024, 12:02 AM UTC

gabrielhidasy wrote: post #145

duped wrote: post #95

Earlier quoted context omitted.

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 th…

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"

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.

Re: Clang vs. Clang

#147

Post by g15jv2dp » Sun, Aug 04, 2024, 12:07 AM UTC

Dylan16807 wrote: post #141

opnitro wrote: post #137

Earlier quoted context omitted.

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…

> 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 p…

> It should emit an instruction to access memory location some_array + i.

That's definitely what compilers emit. The UB comes from the fact that the compiler cannot guarantee how the actual memory will respond to that. Will the OS kill you? Will your bare metal MCU silently return garbage? Will you corrupt your program state and jump into branches that should never be reached? Who knows. You're advocating for wild behavior but you don't even realize it.

As for your example. No, the compiler couldn't optimize like that. You seem to have some misconceptions about UB. If foo is false in your code, then the behavior is completely defined.

Re: Clang vs. Clang

#148

Post by Dylan16807 » Sun, Aug 04, 2024, 12:10 AM UTC

g15jv2dp wrote: post #147

Dylan16807 wrote: post #141

Earlier quoted context omitted.

> 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 p…

> It should emit an instruction to access memory location some_array + i. That's definitely what compilers emit. The UB comes from the fact that the compiler cannot guarantee how the actual memory will respond to that. Will the OS kill you? Will your bare metal MCU silently return garbage? Will you corrupt your program state and jump into branches that should never be reached? Who knows. You're advocating for wild be…

> If foo is false in your code, then the behavior is completely defined.

That's the point. If foo is false, both versions do the same thing. If foo is true, then it's undefined and it doesn't matter. Therefore, assume foo is false. Remove the branch.

Re: Clang vs. Clang

#149

Post by g15jv2dp » Sun, Aug 04, 2024, 12:11 AM UTC

Dylan16807 wrote: post #146

gabrielhidasy wrote: post #145

Earlier quoted context omitted.

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"

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.

There's no reason that C should be suitable for every purpose under the sun.

Re: Clang vs. Clang

#150

Post by tialaramex » Sun, Aug 04, 2024, 12:12 AM UTC

duped wrote: post #95

josephcsible wrote: post #2

> 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…

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 th…

The blog post does, at the very end, mention the thing you should actually do.

You need a language where you can express what you actually meant, which in this case is "Perform this constant time operation". Having expressed what you meant, now everybody between you and the hardware can co-operate to potentially deliver that.

So long as you write C (or C++) you're ruined, you cannot express what you meant, you are second guessing the compiler authors instead.

I think a language related to WUFFS would be good for this in the crypto world. Crypto people know maths already, so the scariest bits of such a language (e.g. writing out why you believe it's obvious that 0 <= offset + k + n < array_length so that the machine can see that you're correct or explain why you're wrong) wouldn't be intimidating for them. WUFFS doesn't care about constant time, but a similar language could focus on that.