Example does not find panicking input since nightly-2021-12-18

[Badel2]

While taking a look at #89, I noticed that even with the proposed workaround, the ci script fails because the first example doesn't find the panicking input. I guess this is an issue caused by llvm, but I am filing it here because I am not sure.

You can use my fork to reproduce the issue. This was working with an old version of rustc, so I was able to bisect the error. 2021-12-17 is good, 2021-12-18 is bad. This is the failing example:

// example/src/main.rs
fuzz_target!(|data: &[u8]| {
    if data == b"banana!" {
        panic!("success!");
    }
});

Bad output

rustup override set nightly-2021-12-18
./ci/script.sh
# Fails to find panicking input

INFO: A corpus is not provided, starting from an empty corpus
#2	INITED ft: 15 corp: 1/1b exec/s: 0 rss: 33Mb
#418	NEW    ft: 24 corp: 2/8b lim: 8 exec/s: 0 rss: 34Mb L: 7/7 MS: 1 InsertRepeatedBytes-
#100000	DONE   ft: 24 corp: 2/8b lim: 994 exec/s: 0 rss: 42Mb
Done 100000 runs in 0 second(s)

Good output

rustup override set nightly-2021-12-17
./ci/script.sh
# Everything works as expected

INFO: -max_len is not provided; libFuzzer will not generate inputs larger than 4096 bytes
INFO: A corpus is not provided, starting from an empty corpus
#2	INITED ft: 15 corp: 1/1b exec/s: 0 rss: 30Mb
#469	NEW    ft: 18 corp: 2/8b lim: 8 exec/s: 0 rss: 30Mb L: 7/7 MS: 2 InsertByte-InsertRepeatedBytes-
thread '<unnamed>' panicked at 'success!', example/src/main.rs:7:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
==5118== ERROR: libFuzzer: deadly signal

Cause

I bisected the cause to this PR: rust-lang/rust#91838 which optimizes comparison of slice and array. But note that this is just a library change, so the actual bug was probably already present before. The PR changes the PartialEq implementation from this one, which forwards the implementation to slice-slice comparison:

    #[inline]
    fn eq(&self, other: &[B]) -> bool {
        self[..] == other[..]
    }

to this one, which uses array-array comparison:

    #[inline]
    fn eq(&self, other: &[B]) -> bool {
        let b: Result<&[B; N], _> = other.try_into();
        match b {
            Ok(b) => *self == *b,
            Err(_) => false,
        }
    }

So a quick workaround would be to force slice-slice comparison, like this:

if data == &b"banana!"[..] {
    panic!("success!");
}

And that does fix the issue. Another workaround is to use a longer string, which somehow prevents the optimization from happening:

if data == b"a very long banana!" {
    panic!("success!");
}

And this also fixes the issue. But obviously it would be better to fix this in the compiler, otherwise there will be many bugs that could have been found by fuzzing but they were not.

I also tried changing the compilation flags, but I did not find any combination that fixed the issue. Also I tried other versions such as the latest nightly 2022-02-28 and the issue is not fixed yet.

Assembly

I tried comparing the assembly code of the good version and the bad version, and I think the main difference is that in the bad version the banana! string is stored inside a register as the constant 0x21616e616e6162, while in the old version it must be stored somewhere else because I did not find that constant.

Also I see that most of the calls to cmp and test are preceded by a call to __sanitizer_cov_trace_const_cmp1, which I assume is the coverage code, while the cmp with 0x21616e616e6162 from the new version does not have such a call, as you can see in this snippet:

movzbl 0x7fff8000(%rax),%r13d
xor    %edi,%edi
mov    %r13d,%esi
call   0xf6950 <__sanitizer_cov_trace_const_cmp1>
test   %r13d,%r13d
jne    0xe0c80 <rust_fuzzer_test_input+3136>
addb   $0x1,0x845f2(%rip)        # 0x164f8a
addb   $0x1,0x845ef(%rip)        # 0x164f8e
movzwl 0x4(%r14),%eax
movzbl 0x6(%r14),%ecx
shl    $0x10,%ecx
or     %eax,%ecx
shl    $0x20,%rcx
mov    (%r14),%eax
or     %rcx,%rax
movabs $0x21616e616e6162,%rcx
cmp    %rcx,%rax
je     0xe0d52 <rust_fuzzer_test_input+3346>
addb   $0x1,0x845bd(%rip)        # 0x164f8f
jmp    0xe0a93 <rust_fuzzer_test_input+2643>
addb   $0x1,0x845a3(%rip)        # 0x164f81

Here is the full disassembly of the rust_fuzzer_test_input function, so you can compare the differences: fuzz_main_dissasembly.zip

Conclusion

I hope this report was useful, and if someone knows what is going on then let me know. If I have time I will try to check if the new slice comparison code has ever compiled correctly in older versions of rust, and also I may try to reproduce the bug in C++ and open an issue directly in the llvm repo.

[fitzgen]

I think letting upstream LLVM know about the seemingly missing sancov tracing calls is good, and I think your intuition of reproducing in C++ is the correct one to make it most actionable for them.

In the meantime, I think we can just update the example program to something like

if data.len() == 6 &&
    data[0] == b'b' &&
    data[1] == b'a' &&
    data[2] == b'n' &&
    data[3] == b'a' &&
    data[4] == b'n' &&
    data[5] == b'a'
{
    panic!("sucess!");
}

which, IIUC, should rely a bit less on the specific Rust comparators call sequence and subsequent lowering to LLVM IR.

[scottmcm]

The root cause here is actually rust-lang/rust#85828

That tries to do comparisons via integer comparison instead of always calling memcmp, for short arrays.

So a == b for 4-element arrays, for example, ends up being done essentially as u32::from_ne_bytes(a) == u32::from_ne_bytes(b), rather than as memcmp(a.as_ptr(), b.as_ptr(), 4) == 0.

[Badel2]

Thanks for you input @scottmcm, but that shouldn't matter because with the default compilation flags cmp instructions are also instrumented, so this should work. I tried to reproduce the bug in C++ but it finds the crashing input instantly:

#include <stdint.h>
#include <stddef.h>
#include <assert.h>

void FuzzMe(const uint8_t *Data, size_t DataSize) {
  if (DataSize != 8) return;

  const uint64_t ban = *(const uint64_t *)Data;
  if (ban == 0x21616e616e6162LL) {
        assert(false);
  }

  return;
}

extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
  FuzzMe(Data, Size);
  return 0;
}

I am compiling that as

clang++ -g -fsanitize=fuzzer bananas.cc 

Following this tutorial if you want to reproduce.

[scottmcm]

I know nothing about the fuzzer, just wanted to give some context on when it happened (since, as the OP mentions, rust-lang/rust#91838 is mostly uninteresting) and what's special about array-to-array comparisons in the codegen right now.