[libFuzzer] Extend ChangeBinaryInteger mutator to support overwriting selected input with predefined integers.

[dokyungs]

Summary

(Experimental - Uploading this to get early feedback before a large-scale experiment.)

This patch extends the ChangeBinaryInteger mutator to support overwriting the selected input with predefined integers. The rationale for this heuristic is that certain byte (word, qword, or qword) overwrite at a specific location (with "magic" integers) in a large input may make an invalid input valid, potentially triggering new neighbor code paths.

Currently, triggering such an overwrite is costly in libFuzzer. ChangeBinaryInteger mutator may do the same, but only with a low probability, because the chosen byte (word, dword, or qword) must already be an integer ranging from -10 to 10.

CopyPart/CrossOver mutator may also effectively do the same, but only if these predefined integers are found in any of the corpus inputs; even if the corpus inputs do contain the predefined integers, the chances are much narrower because a specific location and a specific width have to be selected.

InsertRepeatedBytes combined with EraseBytes mutators (or other combinations of existing mutators) may eventually trigger the desired change, but still the probability is low, as the probabilities of different mutators multiply.

This patch allows to find the desired input in a single mutation (as tested by the accompanying test - overwrite-bytes.test), effectively increasing the probability of finding the desired input given a corpus input.

[morehouse]

compiler-rt/lib/fuzzer/FuzzerMutate.cpp

454

I think we should add more. What does honggfuzz use?

compiler-rt/test/fuzzer/OverwriteBytesTest.cpp

26

Probably the large input defeats our memcmp hook, but we should be careful that it isn't the reason we can pass this test.

compiler-rt/test/fuzzer/OverwriteBytesTest.h

2

Why do we need such a large sequence of bytes, and how did you generate it?

compiler-rt/test/fuzzer/overwrite-bytes.test

3

Can we hard code the magics in the C++?

7

100M runs seems high. How long does it take if we hit that limit?

[dokyungs]

compiler-rt/lib/fuzzer/FuzzerMutate.cpp

454

afl uses the following magic values.

#define INTERESTING_8 \
  -128,          /* Overflow signed 8-bit when decremented  */ \
  -1,            /*                                         */ \
   0,            /*                                         */ \
   1,            /*                                         */ \
   16,           /* One-off with common buffer size         */ \
   32,           /* One-off with common buffer size         */ \
   64,           /* One-off with common buffer size         */ \
   100,          /* One-off with common buffer size         */ \
   127           /* Overflow signed 8-bit when incremented  */

#define INTERESTING_16 \
  -32768,        /* Overflow signed 16-bit when decremented */ \
  -129,          /* Overflow signed 8-bit                   */ \
   128,          /* Overflow signed 8-bit                   */ \
   255,          /* Overflow unsig 8-bit when incremented   */ \
   256,          /* Overflow unsig 8-bit                    */ \
   512,          /* One-off with common buffer size         */ \
   1000,         /* One-off with common buffer size         */ \
   1024,         /* One-off with common buffer size         */ \
   4096,         /* One-off with common buffer size         */ \
   32767         /* Overflow signed 16-bit when incremented */

#define INTERESTING_32 \
  -2147483648LL, /* Overflow signed 32-bit when decremented */ \
  -100663046,    /* Large negative number (endian-agnostic) */ \
  -32769,        /* Overflow signed 16-bit                  */ \
   32768,        /* Overflow signed 16-bit                  */ \
   65535,        /* Overflow unsig 16-bit when incremented  */ \
   65536,        /* Overflow unsig 16 bit                   */ \
   100663045,    /* Large positive number (endian-agnostic) */ \
   2147483647    /* Overflow signed 32-bit when incremented */

honggfuzz uses the following values for 8B as well as similar values for 1, 2, 4B too:

/* 8B - LE */
{"\x00\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x01\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x02\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x03\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x04\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x05\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x06\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x07\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x08\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x09\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x0A\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x0B\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x0C\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x0D\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x0E\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x0F\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x10\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x20\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x40\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x7E\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x7F\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x80\x00\x00\x00\x00\x00\x00\x00", 8},
{"\x81\x00\x00\x00\x00\x00\x00\x00", 8},
{"\xC0\x00\x00\x00\x00\x00\x00\x00", 8},
{"\xFE\x00\x00\x00\x00\x00\x00\x00", 8},
{"\xFF\x00\x00\x00\x00\x00\x00\x00", 8},
{"\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x7E", 8},
{"\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x7F", 8},
{"\x00\x00\x00\x00\x00\x00\x00\x80", 8},
{"\x01\x00\x00\x00\x00\x00\x00\x80", 8},
{"\xFE\xFF\xFF\xFF\xFF\xFF\xFF\xFF", 8},

We can probably start with well-described magic values in afl?

compiler-rt/test/fuzzer/OverwriteBytesTest.cpp

26

Right, we need to make sure that. I attempted to do that by using FileCheck that looks for the mutation sequence printed when the test aborts.

compiler-rt/test/fuzzer/OverwriteBytesTest.h

2

This input is the base input used for magic byte mutation that lead to a big subtree that libFuzzer missed in my short experiment. The file was generated by xxd -i.

We do not need this large sequence of bytes for testing purposes. I will trim it down to a lot more compact version in the next upload.

compiler-rt/test/fuzzer/overwrite-bytes.test

3

Will do in the next upload.

7

I will adjust this value after trimming down the base input.

[dokyungs]

Add magic values used in AFL.

[dokyungs]

Addressed comments.

[dokyungs]

compiler-rt/test/fuzzer/OverwriteBytesTest.cpp

26

I now use memmem here and invoke fuzzing with -use_memmem=0 to eliminate that possibility.

compiler-rt/test/fuzzer/OverwriteBytesTest.h

2

Reduced to 36 bytes.

compiler-rt/test/fuzzer/overwrite-bytes.test

3

Done.

7

Reduced to 10M.

[dokyungs]

clang-format

[morehouse]

compiler-rt/lib/fuzzer/FuzzerMutate.cpp

382

Please add a comment saying these are borrowed from AFL.

413

The indentation seems weird. Can we fix it?

441

The templates here seem like overkill. I'd rather have a runtime check if it simplifies the code.

For example, a simple function should suffice:

template<typename T>
static T GetRandomMagic(Random &Rand) {
  switch (sizeof(T)) {
    case 1: {
      constexpr T Magics[] = {INTERESTING_8};
      return Magics[Rand(sizeof(Magics) / sizeof(T))];
    }
    case 2:
      ...
  }

Actually, this probably gets optimized to similar code since sizeof(T) is a compile-time constant.

compiler-rt/test/fuzzer/OverwriteBytesTest.h

2

Now it's probably small enough to be included in the test itself instead of a header.

compiler-rt/test/fuzzer/overwrite-bytes.test

7

How many runs does it take with and without this mutation?

[dokyungs]

Addressed comments.

[dokyungs]

compiler-rt/lib/fuzzer/FuzzerMutate.cpp

413

This is actually what clang-format gives us. Is it better to manually fix the indentation?

441

It's been simplified now as you suggested. Yes, it's more concise!

compiler-rt/test/fuzzer/overwrite-bytes.test

7

Without this mutation it takes 172,094,572 execs to find it the crash. With this mutation, it takes 531,941 execs.

[morehouse]

compiler-rt/lib/fuzzer/FuzzerMutate.cpp

413

Yes, I would prefer manual formatting.

423

Can we avoid the memcpy by just returning SignedVal, possibly with a cast?

429

There's no breaks, so all of these are fallthroughs...

[dokyungs]

Addressed comments.

[dokyungs]

compiler-rt/lib/fuzzer/FuzzerMutate.cpp

423

I am not sure what cast to use - static_cast or repinterpret_cast? To figure this out I should probably go read the C++ standard.

I thought that we want the exact machine representation of signed magic values here. Based on this thought, I thought memcpy could be better here.

429

Thanks. I still make this mistake :(

[dokyungs]

New data with switch breakthrough fix.

compiler-rt/test/fuzzer/overwrite-bytes.test

7

-mutate_depth=1:
With magic mutation: 34,024
Without magic mutation: more than 134,217,728

-mutate_depth=5:
With magic mutation: 537,111
Without magic mutation: more than 67,108,864

[morehouse]

compiler-rt/lib/fuzzer/FuzzerMutate.cpp

423

static_cast should work as long as T isn't some kind of pointer. In that case we would need reinterpret_cast.

Assuming T is some kind of integer, casting is equivalent to memcpy. So if the compiler lets you, I'd prefer to just assume integer types.

We can add a static_assert(std::is_integral<T>::value) to ensure this isn't abused in the future.

[dokyungs]

Addressed comment - use static_cast instead of memcpy.

[morehouse]

LGTM for an experiment.

compiler-rt/lib/fuzzer/FuzzerMutate.cpp

446

Nit: we can save some lines of code by directly returning instead of assigning to Val. That also lets us remove the breaks.

compiler-rt/lib/fuzzer/FuzzerMutate.cpp

for (size_t i = B; i < E; i++) {
     size_t Idx = E + B - i - 1;
     assert(Idx >= B && Idx < E);
     Data[Idx] = (Val % 10) + '0';
     Val /= 10;
   }
   return Size;
 }
 
+#define INTERESTING_8                                                          \
+  -128,    /* Overflow signed 8-bit when decremented  */                       \
+      -1,  /*                                         */                       \
+      0,   /*                                         */                       \
+      1,   /*                                         */                       \
+      16,  /* One-off with common buffer size         */                       \
+      32,  /* One-off with common buffer size         */                       \
+      64,  /* One-off with common buffer size         */                       \
+      100, /* One-off with common buffer size         */                       \
+      127  /* Overflow signed 8-bit when incremented  */
+
+#define INTERESTING_16                                                         \
+  -32768,   /* Overflow signed 16-bit when decremented */                      \
+      -129, /* Overflow signed 8-bit                   */                      \
+      128,  /* Overflow signed 8-bit                   */                      \
+      255,  /* Overflow unsig 8-bit when incremented   */                      \
+      256,  /* Overflow unsig 8-bit                    */                      \
+      512,  /* One-off with common buffer size         */                      \
+      1000, /* One-off with common buffer size         */                      \
+      1024, /* One-off with common buffer size         */                      \
+      4096, /* One-off with common buffer size         */                      \
+      32767 /* Overflow signed 16-bit when incremented */
+
+#define INTERESTING_32                                                         \
+  -2147483648LL,  /* Overflow signed 32-bit when decremented */                \
+      -100663046, /* Large negative number (endian-agnostic) */                \
+      -32769,     /* Overflow signed 16-bit                  */                \
+      32768,      /* Overflow signed 16-bit                  */                \
+      65535,      /* Overflow unsig 16-bit when incremented  */                \
+      65536,      /* Overflow unsig 16 bit                   */                \
+      100663045,  /* Large positive number (endian-agnostic) */                \
+      2147483647  /* Overflow signed 32-bit when incremented */
+
+template <class T> class MagicInt8 {
+public:
+  static constexpr T Values[] = {INTERESTING_8};
+};
+
+template <class T> class MagicInt16 {
+public:
+  static constexpr T Values[] = {INTERESTING_8, INTERESTING_16};
+};
+
+template <class T> class MagicInt32 {
+public:
+  static constexpr T Values[] = {INTERESTING_8, INTERESTING_16, INTERESTING_32};
+};
+
+// Definitions
+template <class T> constexpr T MagicInt8<T>::Values[];
+template <class T> constexpr T MagicInt16<T>::Values[];
+template <class T> constexpr T MagicInt32<T>::Values[];
+
+template <class T>
+using MagicInt = typename std::conditional<
+    sizeof(T) == 1, MagicInt8<int8_t>,
+    typename std::conditional<
+        sizeof(T) == 2, MagicInt16<int16_t>,
+        typename std::conditional<sizeof(T) == 4, MagicInt32<int32_t>,
+                                  MagicInt32<int64_t>>::type>::type>::type;
+
 template<class T>
 size_t ChangeBinaryInteger(uint8_t *Data, size_t Size, Random &Rand) {
   if (Size < sizeof(T)) return 0;
   size_t Off = Rand(Size - sizeof(T) + 1);
   assert(Off + sizeof(T) <= Size);
   T Val;
   if (Off < 64 && !Rand(4)) {
     Val = Size;
     if (Rand.RandBool())
       Val = Bswap(Val);
+  } else if (Rand.RandBool()) {
+    auto SignedVal =
+        MagicInt<T>::Values[Rand(sizeof(MagicInt<T>::Values) / sizeof(T))];
+    memcpy(&Val, &SignedVal, sizeof(SignedVal));
+    if (Rand.RandBool()) {
+      Val = Bswap(Val);
+    }
   } else {
     memcpy(&Val, Data + Off, sizeof(Val));
     T Add = Rand(21);
     Add -= 10;
     if (Rand.RandBool())
       Val = Bswap(T(Bswap(Val) + Add)); // Add assuming different endiannes.
     else
       Val = Val + Add;               // Add assuming current endiannes.

compiler-rt/test/fuzzer/OverwriteBytesMain.cpp

+#include <cstdint>
+#include <cstdio>
+
+#include "OverwriteBytesTest.h"
+
+int main(int argc, char **argv) {
+  fwrite(SeedInput, sizeof(SeedInput[0]), sizeof(SeedInput), stdout);
+  return 0;
+}

compiler-rt/test/fuzzer/OverwriteBytesTest.h

+uint8_t SeedInput[] = {
+    0xba, 0xe3, 0x92, 0x7c, 0x80, 0x86, 0x73, 0x0f, 0xf2, 0x83, 0x23, 0x0f,
+    0xf5, 0x17, 0x4c, 0x08, 0xf2, 0x83, 0x23, 0x0f, 0xd8, 0x71, 0x58, 0x1c,
+    0xb9, 0x8d, 0xf1, 0x0e, 0x80, 0x86, 0x73, 0x0f, 0xf0, 0x83, 0x23, 0x0f,
+};

compiler-rt/test/fuzzer/OverwriteBytesTest.cpp

+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+
+#include <cassert>
+#include <cstdint>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+
+#include <algorithm>
+#include <vector>
+
+#include "OverwriteBytesTest.h"
+
+#define MAGIC_BYTE_VALUE 0x1
+#define MAGIC_BYTE_OFFSET 0xf
+
+static volatile int *Nil = nullptr;
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
+  if (Size != sizeof(SeedInput)) {
+    return 0;
+  }
+
+  *(uint64_t *)(SeedInput + MAGIC_BYTE_OFFSET) = MAGIC_BYTE_VALUE;
+
+  if (memmem(Data, Size, SeedInput, Size) == Data) {
+    *Nil = 42; // crash.
+  }
+
+  return 0;
+}

compiler-rt/test/fuzzer/overwrite-bytes.test

+REQUIRES: linux, x86_64
+RUN: %cpp_compiler %S/OverwriteBytesTest.cpp -o %t-OverwriteBytesTest
+RUN: %cpp_compiler -fno-sanitize=fuzzer %S/OverwriteBytesMain.cpp -o %t-OverwriteBytesPrintSeed
+RUN: %t-OverwriteBytesPrintSeed > %t-OverwriteBytesTest.seed
+
+RUN: not %run %t-OverwriteBytesTest -seed=1 -use_memmem=0 -mutate_depth=1 -reduce_inputs=0 -runs=10000000 -seed_inputs=%t-OverwriteBytesTest.seed 2>&1 | FileCheck %s
+
+CHECK: ABORTING
+CHECK-NEXT: MS: 1 ChangeBinInt-;