Semantic fuzzing of the Rust compiler and interpreter [pdf] | Hacker News Reader

Semantic fuzzing of the Rust compiler and interpreter [pdf]

ethz.ch

157 pointstodsacerdoti43 comments

> A long-standing miscompilation in the Rust compiler was the incorrect removal of loops even if the compiler cannot tell whether it terminates (#28728).

>This resulted in the Rust compiler apparently “proving” the unresolved Collatz conjecture by optimising this function to return true [1].

    pub fn collatz(n: usize) -> bool {
      match n {
        1 => true,
        n if n % 2 == 0 => collatz(n/2),
        _ => collatz(3\*n + 1),
      }
    }

That's funny. Hey maybe it was just that good!

Collatz conjecture is tested to be true for n < 2^100000 - 1. That is, true for all value represent-able in usize.

Sounds like it was working as intended, then! Doing a great job at it, too.

Sounds, rather, like it was doing the right thing in that case but for the wrong reasons!

Oh yes, that's just LLVM's ConstantFoldCollatzConjecture pass, a basic optimization.

> That is, true for all value represent-able in usize.

A slight understatement!

But exactly the statement you need to fold it to a constant.

But if we pass in an odd value that is more than half of the maximum value represented in a usize, we get an overflow and a panic when we make a recursive call with n * 3 + 1, right? We shouldn't be optimizing those away.

In the default release profile math wraps.

But does it converge using wrapping math for all usize values?

There might be a cycle in theory.

There can be a cycle but IIRC Rust inherits C/C++'s rule that infinite loops without side effects are undefined behaviour. So there are cycles (for example 0) but since there are no side effects and the only way to escape the loop is the `return true` the compiler only has to handle the `return true` path.

Oh sure that is fine, I just wonder if colatz is proven to converge for 32bit/64bit wrapping integer math.

> The source of this bug is LLVM [2] which Rust relies on for optimisations and machine code generation.

So basically rustc_codegen_gcc and cranelift can compile code that don't with LLVM and then introduce (or solve) new bugs?

Note that it's entirely feasible that GCC would do the same in this specific case. This wasn't necessarily a "bug" in LLVM per se, because this is the specified behavior in C and C++, and LLVM was simply implementing those semantics. The fix here was just to allow languages to opt-out of this behavior. Since GCC is also primarily a C/C++ backend, you'd have the same problem unless they offer a similar opt-out.

But in general, yes, if this was unintended behavior of LLVM, then we would expect alternative backends to exhibit differing behavior.

What you're talking about was a bug in LLVM. The paper says:

>Infinite loops and recursions are Undefined Behaviour in C and C++, therefore the compiler can assume that a loop always terminates.

... which is wrong - only C++ requires loops to terminate. C allows non-terminating loops (with some specific requirements), and LLVM was already known to miscompile C in this same way until it was fixed in LLVM 12 with the `mustprogress` attribute.

https://bugs.llvm.org/show_bug.cgi?id=965

https://stackoverflow.com/questions/59925618/how-do-i-make-a...

Then this:

>While LLVM does not require loops to terminate and should compile Rust loops correctly, its code contained assumptions that only hold for C/C++, thus miscompiling Rust code.

... is implied to be a different LLVM bug after the first one was already fixed, ie despite using `mustprogress` LLVM had additional miscompilations for Rust code because of "assumptions that only hold for C/C++". I can't tell which one in table 4.2 it is, though; none of them see to match.

Ah, thank you, I was assuming that C++ inherited this from C.

Eh, 0 is an infinite loop in that function.

It also doesn't implement the collatz conjecture. It implements the collatz-conjecture mod (usize::MAX + 1). I don't know about that modulus specifically, but there are m where the collatz conjecture mod m is false.

https://www.researchgate.net/profile/Cganesa-Moorthy/publica...

Edit: (2^64 - 1) / 3 is an integer and also trivially infinitely loops (by going to 0).

> It implements the collatz-conjecture mod (usize::MAX + 1).

Only if you have overflow checking disabled.

Of course, if overflow checking isn't disabled returning true is wrong because of panicking instead of infinite loops.

Note that in C++, all side-effect-free loops can be assumed to terminate, and thus eliminated.

Assume is a strong word. It's defined by the standard by way of undefined behavior.

A C++ program with a non-terminating side-effect-free loop is malformed, so if we assume the program is not malformed, then we can assume side-effect-free loops terminate.

Which is crazy, because there's always side effect like temperature, fans speed/noise, etc.

That isn't what is meant by "side effect" here. A function with no side effects only modifies its local variables and returns a result. So, if we have

int foo(int a, int b) { int c = bar(a); return b; }

and we can see bar's body, and therefore we can determine that it has no side effects, we can optimize the call to bar away, because we can assume that it terminates and it doesn't affect the result.

But if bar writes to global variables, that's a side effect. If we can't see the body of bar we have to assume that it might.

I'm aware, but I don't agree that we should ignore "physical world" implications

We got hurt by that in side-channel attacks.

Going by that rule, optimizing compilers just shouldn't exist. Optimizations will (or at least are supposed to) decrease computation, which will affect CPU temperatures.

Contrary to popular belief the C++ specification does not require conforming implementations to produce temperature, fan noise or the like.

"Please just add an option to re-enable spacebar heating!" [1]

[1] https://xkcd.com/1172/

Nikita Popov is thanked in the forward for work fixing LLVM bugs.

Before he pivoted to LLVM work, Nikita was one of the key individual contributors to the official PHP project in the last decade. He's an incredible force for good.

Seconding this. Nikita has been a fantastic help in reviewing my LLVM contributions over the past couple of years.

nikic is demigod!

Neat that this thesis was written by a student of ralfj [1][2] (who has done a lot of work to drive forward formal definitions for rust).

[1] https://research.ralfj.de/ [2] https://news.ycombinator.com/user?id=ralfj

I've only got a few pages through this but I just wanted to say how well this is written. It's so clear! If only all academic texts were like this.

> Producing observable and deterministic output

The approach described in this section (just insert a bunch of calls to a dump_var() function which dumps its results into the graph) is really interesting to me. A problem I've had with fuzzing is getting some high-bandwidth error data other than "the program crashed". You can eg instrument pointer reads and writes, but sometimes reordering or deleting them is a legitimate optimization.

It's really cool to see Rust developers pioneer these revolutionary new methods nobody thought of before. </CunninghamsLaw> (But seriously, if someone has a name for this technique, I'm interested.)

As I understand it, the value of this thesis is the design of the fuzzer, which produces sufficiently 'complex' code to exercise uncommon code paths in the compiler, while retaining desirable properties such as reducibility.

Reply on news.ycombinator.com