Repository files navigation

Halfempty is a new testcase minimization tool, designed with parallelization inmind. Halfempty was built to use strategies and techniques that dramaticallyspeed up the minimization process.

Fuzzers find inputs that trigger bugs, but understanding those bugs is easierwhen you remove as much extraneous data as possible. This is calledtestcaseminimization ordelta debugging.

Minimization tools use various techniques to simplify the testcase, but thecore algorithm is simply bisection. Bisection is an inherently serial process,you can't advance through the algorithm without knowing the result of eachstep. This data dependency problem can make minimization very slow, sometimestaking hours to complete while cpu cores sit idle.

In this diagram you can see we progressively remove parts of the file to determine which section is interesting.

halfempty solves this problem usingpessimistic speculative execution. Webuild a binary tree of all the possible bisection steps and then idle cores canspeculatively test future steps ahead of our position in the algorithm. In manycases, the test results are already known by the time we need them.

We call itpessimistic, because real workloads are characterized by longseries of consecutive failures. We simply assume that tests are going to fail,and speculatively follow the failure path until proven wrong.

In this diagram, you can see we generated a binary tree of all possible outcomes, and now idle cores can speculatively work ahead of the main thread.

If you're fuzzing a target that takes more than a few seconds to run thenparallelizing the minimization can dramatically speedup your workflow. Realfuzzing inputs that take several seconds to reproduce can take many hours tocomplete using serial bisection, but halfempty can produce the same output inminutes.

In real tests, the author often finds speedup exceeding hours.

This is a real minimization path from a fuzzer generated crash.

Halfempty generates a binary tree, and this graph shows the path through thetree from the root to the final leaf (discarded paths are hidden on the leftto simplify the diagram).

The green nodes were successful and the red nodes were failures. The greynodes in the right were explored but discarded. Because all consecutive rednodes are executed in parallel, the actual wall clock time required tominimize the input was minimal.

Each crash took ~11 seconds to reproduce, requiring about  34 minutes ofcompute time - but halfempty completed in just6 minutes!

The original input was 240K, the final output was just 75 bytes.

The only dependency islibglib2.0-dev, used for some useful data structures, likeN-ary trees.

On RedHat systems, tryglib2-devel.

Just typemake to build the main binary.

The--monitor mode feature requires thegraphviz package and a web browser.

The author has tested the following distributions:

• CentOS 6 amd64
• Ubuntu 14 amd64

Halfempty has preliminary macOS support usinghomebrew.

Please usebrew install pkg-config glib to install necessary dependencies, thenmake to buildthe main binary.

First, create a shell script that when given your input on stdin, returns zero.

A simple example might look like this if you wanted to test agzip crash:

#!/bin/shgzip -dc# Check if we were killed with SIGSEGViftest$? -eq 139;then    exit 0# We want this inputelse    exit 1# We don't want this inputfi

Make the file executable and verify it works:

$ chmod +x testgzip.sh$ ./testgzip.sh < crashinput.gz && echo success || echo failuresuccess

Now simply run halfempty with your input and it will find the smallest version that still returns zero.

Note: If you need to create temporary files, see some advanced examples in the documentation.

$ halfempty testgzip.sh crashinput.gz

If everything worked, there should be a minimal output file inhalfempty.out.

If you want to monitor what halfempty is doing, you can use--monitor mode,which will generate graphs you can watch in realtime. halfempty will generate aURL you can open, and you can view the data in your web browser.

Note:--monitor mode requires the graphviz package to be installed.

Halfempty includes many options to fine tune the execution environment for thechild processes, and tweak performance options. The full documentation can beshown with--help-all, but here are the most commonly useful parameters.

There are more examples available in the wiki.

Note: Are you sure you need temporary files? Many programs will accept/dev/stdin.

If you need to create temporary files to give to your target program, you can simply do something like this.

#!/bin/shtempfile=`mktemp`&& cat>${tempfile}yourprogram${tempfile}

Remember to clean it up when you're done, you can do this if you like:

#!/bin/shtempfile=`mktemp`&& cat>${tempfile}result=1trap'rm -f ${tempfile}; exit ${result}' EXIT TERM ALRMyourprogram${tempfile}iftest$? -eq 139;then    result=0fi

Sometimes your target program might crash with a different crash accidentallyfound during minimization. One solution might be to use gdb to verify the crashsite.

#!/bin/shexec gdb -q                                                                 \         -ex'r'                                                            \         -ex'q !($_siginfo.si_signo == 11 && $pc == 0x00007ffff763f2e7)'   \         -ex'q 1'                                                          \         --args yourprogram --yourparams

This will exit 0 if the signal number and crash address match, or 1 otherwise.

You can test various things such as registers ($rip,$eax, etc), faultaddress ($_siginfo._sifields._sigfault.si_addr), and many more. If you wantto see more things you can test, try the commandshow conv in gdb.

Q.What does finalized mean in halfempty output?

A. Halfempty works by guessing what the results of tests will be before thereal result is known. If the path through the bisection tree from the root nodeto the final leaf was entirely through nodes where we knew the result, then thepath isfinalized (as opposed topending).

Q.Where does the name come from?

A. We usepessimistic speculative execution, so the glass is always halfempty? ....? Sorry. 🥛

Q.How can I kill processes that take too long?

A. Use--timeout 10 to send a signal that can be caught after 10 seconds,or--limit RLIMIT_CPU=10 to enforce a hard limit.

Q.Halfempty wastes a lot of CPU time exploring paths, so is it really faster?

A. It's significantly faster in real time (i.e. wall clock time), that's what counts!

Q.I have a very large input, what do I need to know?

A. Halfempty is less thorough by default on very large inputs that don'tseem to minimize well. Removing each byte from multi-gigabyte inputs just takestoo long, even when run in parallel.

If you reallywant halfempty to be thorough, you can do this:

$ halfempty --bisect-skip-multiplier=0 --zero-skip-multiplier=0 --stable --gen-intermediate harness.sh input.bin

• --bisect-skip-multiplier=0 and--zero-skip-multiplier=0 means to try removing every single byte.
• --stable means to keep retrying minimization until it no further removals work.
• --gen-intermediate means to save the best result as it's found, so youwon't lose your work if you change your mind.

On the other hand, if you just want halfempty to be faster and don't care ifit's not very thorough, you can do the opposite. Something like this:

$ halfempty --bisect-skip-multiplier=0.01 --zero-skip-multiplier=0.01 harness.sh input.bin

The reasonable range for the multiplier is0 to0.1.

• If your program intercepts signals or creates process groups, it might be difficult to cleanup.
• For very long trees, we keep an fd open for each successful node. It's possible we might exhaust fds.

Please report more bugs or unexpected results totaviso@google.com. Theauthor intends to maintain this tool and make it a stable and reliablecomponent of your fuzzing workflow.

Better quality bug reports require simpler reproducers, and that requires goodquality tools.

• The next version will allow the level of pessimism to be controlled at runtime.

Tavis Ormandytaviso@google.com

Apache 2.0, See LICENSE file for details.

This is not an officially supported Google product.