Fuzzbombing: abort() calls for great justice!

The Colossal Cave Adventure restoration is pretty much done now. One thing we’re still working on is getting test coverage of the last few corners in the code. Because when you’re up to 99.7% the temptation to push for that last 0.3% is really strong even if the attempt is objectively fairly pointless.

What’s more interesting is the technique one of our guys came up with for getting us above about 85% coverage. After that point it started to get quite difficult to hand-craft test logs to go to the places in the code that still hadn’t been exercised.

But NHorus, aka Petr Vorpaev, is expert at fuzz testing; we’ve been using American Fuzzy Lop, a well-designed, well-documented, and tasteful tool that I highly recommend. And he had an idea.

Want to get a test log that hits a particular line? Insert an abort() call right after it and rebuild. Then unleash the fuzzer. If you’ve fed it a good test corpus that gets somewhere near your target, it will probably not take long for the fuzzer to random-walk into your abort() call and record that log.

Then watch your termination times. For a while we’d generally get a result within hours, but we eventually hit a break after which the fuzzer would run for days without result. That knee in the curve is your clue that the fuzzer has done everything it can.

I dub this technique “fuzzbombing”. I think it will generalize well.

12 comments

  1. The really clever thing about coverage-guided fuzzers like American Fuzzy Lop is that their random walk isn’t quite as random as all that. They watch your program’s execution, record the path taken through the code, and randomly permute things until they find some interesting new behavior. “Oho!” they say. “That’s new! I’ll generate a bunch of variations on that particular input and see what happens!”. So, for example, AFL managed to create valid JPEG files from nothing just by watching the parser try to load them. When it was able to make the parser get a little further along before rejecting the file as malformed, the fuzzer saw that it had found exciting new territory to explore. Six hours later, boom, valid images conjured up from the ether.

    I also recommend LLVM’s libFuzzer, which works on functions rather than whole executables, which sometimes makes it feasible to use in contexts that would be very awkward with AFL.

  2. Another tool you might want to look into for this sort of thing is Klee. It’s basically an SMT solver that understands the semantics of LLVM bitcode, and can solve for inputs that will trigger a particular code assertion. It’s a bit more researchware than AFL, but I found it usable.

  3. ESR,

    As you et al fuzzbombed along, what sort of weirdness/interestingness did pushing beyond 85% coverage show up?

    1. >As you et al fuzzbombed along, what sort of weirdness/interestingness did pushing beyond 85% coverage show up?

      Nothing in particular. By the time we started fuzzbombing we had already characterized all but one or two of the few minor bugs we found.

  4. Two notes: I’m no expert in fuzzing, AFL is a nifty tool that I itched to use for years and Adventure is interesting place to use it and to learn as I go. Let’s call that intermediate in fuzzing.
    Instrumenting fuzzer is delightfully abusable when you have source code – conditional aborts and few new globals temporarily introduced would guide it to produce logs of walking into certain states or speaking certain phrases.
    Secondly, I’m NHO or NHOrus. Capitalized part is (silly) acronym, normal part is (optional) quantifier. Not a Horus wasn’t intended meaning.

    And of weirdness… Non-fuzz-related: Bugs that we fix accidentally or trying to fix, like not killing dragon taking more time than killing it. Eat grate. Code paths that were there from the start, but that couldn’t be reached at all. Weird consequences of removing as many global variables as possible and following swearing from angry static/dynamic analyzers. Lcov lying about coverage being greater than it is with most honest face possible. Urn extinguishing to dry.

  5. NHO’s fuzzing also uncovered more low-level bugs due to our own coding, most notably me committing the same off-by-one error *twice*.

    valgrind and ubsan also did good work along those lines.

    1. Don’t forget asan (for it is faster for leaks than valgrind) and me smashing into the logic of get_input() for a few days to understand where the leak actually happens.
      ubsan warned about only one error and it was logical problem, easy fixed by putting else in right place.

      1. Yes, asan, and now also _FORTIFY_SOURCE.

        Just now, I caught another bug by using clang instead of gcc. I’m in the process of upgrading our CI pipeline.

        1. if it’s -Wvarargs, then noticed long ago, but still no idea how to fix that.

          Oh, and noticed just now:
          If you try to take grate first thing, well…
          vcarry (verb=1, obj=63)
          (gdb) p objects[obj].inventory
          $10 = 0x438e6a “Rare spices”

          No idea yet WHYYYYYY????

        2. Oh, and no less noticed:
          If you try to take grate first thing, well…
          vcarry (verb=1, obj=63)
          (gdb) p objects[obj].inventory
          $10 = 0x438e6a “Rare spices”

          No idea yet WHYYYYYY????

Leave a comment

Your email address will not be published. Required fields are marked *