Skip to content

Examples

Jump to bottom
Tavis Ormandy edited this page Mar 18, 2019 · 10 revisions

Halfempty Cookbook

This wiki page contains a collection of useful example scripts to help you minimize with halfempty.

Minimizing Timeouts / Hangs

You have found a timeout or hang in your application, and want halfempty to find you the minimal version that still hangs.

To achieve this, you can ask halfempty to send you a SIGALRM using the --timeout parameter, and then handle it in your script.

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

trap 'rm -f ${tempfile}; exit ${result:=1}' EXIT TERM
trap 'rm -f ${tempfile}; exit ${result:=0}' ALRM

yourprogram --yourargs ${tempfile}

Now the following command will find the simplest testcase that takes at least 10 seconds to run:

$ halfempty --timeout 10 ./timeout.sh testcase

Minimizing Input to a Graphical Application

You have a graphical application and a record of user interaction you want to replay, and want to find the minimal amount of input to reach the final state.

You can do this by creating a "golden" image of how you want the application to look, and then asking halfempty to find the minimum amount of input to reach that state. A useful set of tools for this is Xvfb, xdotool and ImageMagick.

  • Xvfb is a virtual X server, it doesn't actually display any output but emulates a display for applications.
  • xdotool can automate sending input, keystrokes, mouse clicks, and so on.
  • ImageMagick can automate taking screenshots and comparing images.

Let's look at an example. Imagine we have a large amount of input to gnome-calculator from testing or fuzzing that causes some error state we would like to examine. This would be much easier to debug if we have the minimum amount of input necessary to reproduce the state.

First, replay the input in Xvfb and take a screenshot of how it looks.

For this example, I randomly generated some input like this:

$ tr -dc '0-9()%+/*.\r\033-' < /dev/urandom | head -c 1024 > input.txt

Now start Xvfb, and replay the input using xdotool:

$ Xvfb :1 -screen 0 640x480x24 &
$ DISPLAY=:1 gnome-calculator &
$ DISPLAY=:1 xdotool search --sync --onlyvisible --name "Calculator" windowmove 0 0 windowsize 100% 100% getwindowgeometry
Window 2097159
  Position: 0,0 (screen: 0)
  Geometry: 640x480
$ DISPLAY=:1 xdotool type --delay 100 --file input.txt
$ DISPLAY=:1 import -window 2097159 png:golden.png

This might take a few minutes, but halfempty can run many jobs in parallel.

You can verify the screenshot looks correct by looking at golden.png.

If that looks correct, you can minimize the input using a script like this:

#!/bin/bash
# create a fifo for communication with Xserver
fifoname=$(mktemp -u) && mkfifo ${fifoname}

# cleanup on timeout or error
trap 'rm -f ${fifoname}; kill %Xvfb; exit ${result:=1}' TERM ALRM EXIT

# start a virtual X server
Xvfb -nolisten tcp -displayfd 1 -screen 0 640x480x24 :$$ > ${fifoname} &

# wait for Xvfb to say it's ready for a client
read display < ${fifoname} && export DISPLAY=:${display}

# start application
gnome-calculator &

# wait for calculator to appear and position at 0 0
eval $(xdotool search --sync --onlyvisible --name "Calculator"   \
        windowmove --sync 0 0                                    \
        windowsize --sync 100% 100%                              \
        getwindowgeometry --shell)

# give it a second to initialize
sleep 1

# send it the specified input
xdotool type --delay 100 --file -

# give it a second to finish processing
sleep 1

# compare the window to golden image
result=$(import -windowid $WINDOW png:- \
       | compare -metric AE png:- png:golden.png /dev/null 2>&1)

# send exit command
xdotool key ctrl+q

# wait for it to finish
wait %gnome-calculator

Now use this command to find the minimal input required to make gnome-calculator look the way it does in the golden image.

$ halfempty ./sendinput.sh input.txt 
╭│   │ ── halfempty ───────────────────────────────────────────────── v0.30 ──
╰│  2│ A fast, parallel testcase minimization tool
 ╰───╯ ───────────────────────────────────────────────────────── by @taviso ──

Input file "input.txt" is now 1024 bytes, starting strategy "bisect"...
Verifying the original input executes successfully... (skip with --noverify)
The original input file succeeded after 57.0 seconds.
New finalized size: 1024 (depth=2) real=0.0s, user=0.0s, speedup=~-0.0s
New finalized size: 768 (depth=6) real=43.1s, user=105.4s, speedup=~62.3s
New finalized size: 640 (depth=10) real=109.2s, user=230.8s, speedup=~121.5s
New finalized size: 576 (depth=16) real=172.2s, user=412.7s, speedup=~240.5s
New finalized size: 512 (depth=18) real=231.6s, user=472.0s, speedup=~240.4s
New finalized size: 448 (depth=21) real=287.7s, user=551.0s, speedup=~263.3s
New finalized size: 416 (depth=27) real=344.3s, user=703.8s, speedup=~359.6s
New finalized size: 384 (depth=37) real=441.8s, user=943.4s, speedup=~501.5s
New finalized size: 352 (depth=38) real=463.1s, user=964.6s, speedup=~501.5s
New finalized size: 336 (depth=40) real=486.1s, user=1004.8s, speedup=~518.7s
New finalized size: 320 (depth=42) real=525.4s, user=1044.0s, speedup=~518.6s
...
Reached the end of our path through tree, all nodes were finalized
597 nodes failed, 130 worked, 18 discarded, 1 collapsed
7026.639 seconds of compute was required for final path

Strategy "bisect" complete, output 85 bytes
All work complete, generating output halfempty.out (size: 85)

Halfempty reduced the testcase to just 85 inputs, much more manageable to debug.

Let's verify it worked by taking a new screenshot and comparing them:

$ Xvfb :1 -screen 0 640x480x24 &
$ DISPLAY=:1 gnome-calculator &
$ DISPLAY=:1 xdotool search --sync --onlyvisible --name "Calculator" windowmove 0 0 windowsize 100% 100% getwindowgeometry
Window 2097159
  Position: 0,0 (screen: 0)
  Geometry: 640x480
$ DISPLAY=:1 xdotool type --delay 100 --file halfempty.out
$ DISPLAY=:1 import -window 2097159 png:output.png

Golden Image Minimized Image

Looks Identical! You can use Xnest instead of Xvfb if you want to see and interact with the application, note that some of the parameters are different (For example, Xnest uses -geometry instead of -screen).

Minimizing Rendered Output of a Graphical Application

Using the Xvfb method as above, we could minimize the amount of html required to produce the same output in a browser.

First, I saved a website to an html file, and took a screenshot of it when rendered:

$ Xvfb :1 -screen 0 1024x768x24 &
$ DISPLAY=:1 firefox --no-remote ./Hacker\ News.html &
$ DISPLAY=:1 xdotool search --sync --onlyvisible --name "Mozilla Firefox" windowmove 0 0 windowsize 100% 100% getwindowgeometry
Window 4194320
  Position: 0,0 (screen: 0)
  Geometry: 1024x768
$ DISPLAY=:1 import -window 4194320 png:golden.png

Note that firefox actually has a --screenshot option, but this example can be applied to other applications.

Minimizing Memory Leaks

Using LSAN, Valgrind or other tools it's possible to minimize an input that causes memory leaks or other errors in your program.

For this example, I've used the following simple C program that leaks memory if the input contains the string "leaky".

$ cat leaky.c 
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main(int argc, char **argv)
{
    char *lineptr = NULL;
    size_t size;

    while (getline(&lineptr, &size, stdin) > 0) {
        if (strstr(lineptr, "leaky"))
            return 0;
    }

    free(lineptr);
    return 0;
}

Valgrind

A minimal example using valgrind.

#!/bin/sh
# In this example, the test application reads stdin, see the halfempty wiki if
# you need an example of creating temporary files.
#
# choose an exitcode your application wont use, like 42 in this example
valgrind --error-exitcode=42   \
         --quiet               \
         --leak-check=full     \
         leaky

if test $? -eq 42; then
    exit 0  # leak occurred, keep this input
else
    exit 1  # no leak, discard this input
fi

Use this command to find the leak.

$ halfempty ./leakcheck.sh /usr/share/dict/words 
╭│   │ ── halfempty ───────────────────────────────────────────────── v0.30 ──
╰│  2│ A fast, parallel testcase minimization tool
 ╰───╯ ───────────────────────────────────────────────────────── by @taviso ──

Input file "/usr/share/dict/words" is now 4953680 bytes, starting strategy "bisect"...
Verifying the original input executes successfully... (skip with --noverify)
The original input file succeeded after 0.3 seconds.
New finalized size: 4953680 (depth=2) real=0.0s, user=0.0s, speedup=~-0.0s
New finalized size: 2476840 (depth=4) real=0.9s, user=1.5s, speedup=~0.6s
New finalized size: 1238420 (depth=6) real=1.8s, user=2.4s, speedup=~0.6s
New finalized size: 619210 (depth=8) real=2.8s, user=3.4s, speedup=~0.6s
New finalized size: 309605 (depth=11) real=3.5s, user=4.9s, speedup=~1.4s
New finalized size: 154803 (depth=12) real=4.0s, user=5.4s, speedup=~1.4s
New finalized size: 77402 (depth=14) real=4.8s, user=6.4s, speedup=~1.6s
New finalized size: 38702 (depth=17) real=5.9s, user=7.8s, speedup=~1.9s
New finalized size: 19352 (depth=18) real=6.3s, user=8.3s, speedup=~2.0s
New finalized size: 9677 (depth=20) real=6.9s, user=9.5s, speedup=~2.6s
New finalized size: 4840 (depth=23) real=7.7s, user=10.8s, speedup=~3.1s
New finalized size: 2422 (depth=25) real=8.6s, user=11.8s, speedup=~3.2s
New finalized size: 1213 (depth=27) real=9.7s, user=12.6s, speedup=~2.9s
New finalized size: 609 (depth=28) real=10.1s, user=13.1s, speedup=~2.9s
New finalized size: 307 (depth=31) real=10.8s, user=14.2s, speedup=~3.5s
New finalized size: 156 (depth=33) real=11.6s, user=15.3s, speedup=~3.7s
New finalized size: 81 (depth=34) real=12.2s, user=15.9s, speedup=~3.7s
New finalized size: 44 (depth=36) real=13.0s, user=16.5s, speedup=~3.5s
New finalized size: 26 (depth=39) real=14.2s, user=17.8s, speedup=~3.6s
New finalized size: 17 (depth=41) real=14.8s, user=18.8s, speedup=~3.9s
New finalized size: 13 (depth=44) real=15.5s, user=20.2s, speedup=~4.7s
New finalized size: 9 (depth=45) real=15.7s, user=20.5s, speedup=~4.8s
New finalized size: 7 (depth=49) real=17.2s, user=22.7s, speedup=~5.5s
New finalized size: 6 (depth=55) real=18.9s, user=25.2s, speedup=~6.3s
Reached the end of our path through tree, all nodes were finalized
87 nodes failed, 54 worked, 26 discarded, 1 collapsed
56.959 seconds of compute was required for final path

Strategy "bisect" complete, output 6 bytes
All work complete, generating output halfempty.out (size: 6)
$ cat halfempty.out 
leaky
$

LSAN

By default, LeakSanitizer uses exit code 23 when a leak is detected, so a minimal example would be

#!/bin/sh
# In this example, the test application reads stdin, see the halfempty wiki if
# you need an example of creating temporary files.
leaky

if test $? -eq 23; then
    exit 0  # leak occurred, keep this input
else
    exit 1  # no leak, discard this input
fi

Controlling Resource Limits

You're trying to minimize a testcase in an application that can consume significant resources when given malformed input, such as allocating lots of memory or creating large files.

Halfempty can limit the resources available to the application so that is harmlessly terminated. The full list of resources you can control is described in the setrlimit manual, but let's examine some common scenarios.

Limiting Memory Allocation

You want to minimize a crash testcase, but the application is badly behaved and might allocate significant memory if given incorrect input.

Here is an example written in C, every letter 'M' in the input causes a 64k memory allocation!

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main(int argc, char **argv)
{
    char *lineptr = NULL;
    size_t size;

    while (getline(&lineptr, &size, stdin) > 0) {
        if (strchr(lineptr, 'm')) {
            if (malloc(64 * 1024) == NULL) {
                fprintf(stderr, "memory allocation failure\n");
                return 1;
            }
        }

        if (strstr(lineptr, "crash"))
            *(char *)(0) = 'C';
    }

    return 0;
}

Let's try it with a 1GB virtual memory size limit, here's the test script:

#!/bin/sh
./eatmemory

if test $? -eq 139; then
    exit 0  # Segmentation Fault, keep this input
else
    exit 1  # discard this input
fi

And we run it with an address space limit of 0x40000000 (That's 1GB, 1 * 1024 * 1024 * 1024 bytes)

$ halfempty --limit=RLIMIT_AS=0x40000000 ./testcase.sh /usr/share/dict/words
╭│   │ ── halfempty ───────────────────────────────────────────────── v0.30 ──
╰│  2│ A fast, parallel testcase minimization tool
 ╰───╯ ───────────────────────────────────────────────────────── by @taviso ──

Input file "/usr/share/dict/words" is now 4953680 bytes, starting strategy "bisect"...
Verifying the original input executes successfully... (skip with --noverify)
** Message: 15:29:41.591: This program expected `./testcase.sh` to return successfully
** Message: 15:29:41.591: for the original input (i.e. exitcode zero).
** Message: 15:29:41.591: Try it yourself to verify it's working.
** Message: 15:29:41.591: Use a command like: `cat /usr/share/dict/words | ./testcase.sh || echo failed`

Oops, I guess we were too aggressive, let's try 2GB instead:

$ halfempty --limit=RLIMIT_AS=0x80000000 ./testcase.sh /usr/share/dict/words
╭│   │ ── halfempty ───────────────────────────────────────────────── v0.30 ──
╰│  2│ A fast, parallel testcase minimization tool
 ╰───╯ ───────────────────────────────────────────────────────── by @taviso ──

Input file "/usr/share/dict/words" is now 4953680 bytes, starting strategy "bisect"...
Verifying the original input executes successfully... (skip with --noverify)
The original input file succeeded after 2.3 seconds.
New finalized size: 4953680 (depth=2) real=0.0s, user=0.0s, speedup=~-0.0s
New finalized size: 2476840 (depth=4) real=0.2s, user=0.2s, speedup=~0.0s
New finalized size: 1238420 (depth=7) real=0.4s, user=0.5s, speedup=~0.1s
New finalized size: 619210 (depth=8) real=0.5s, user=0.6s, speedup=~0.1s
New finalized size: 309605 (depth=11) real=0.6s, user=0.7s, speedup=~0.1s
New finalized size: 154803 (depth=13) real=0.6s, user=0.8s, speedup=~0.1s
New finalized size: 77402 (depth=14) real=0.7s, user=0.8s, speedup=~0.1s
New finalized size: 38702 (depth=16) real=0.7s, user=0.9s, speedup=~0.1s
New finalized size: 19352 (depth=19) real=0.8s, user=0.9s, speedup=~0.1s
New finalized size: 9677 (depth=21) real=0.9s, user=1.0s, speedup=~0.1s
New finalized size: 4840 (depth=23) real=1.0s, user=1.1s, speedup=~0.1s
New finalized size: 2422 (depth=25) real=1.1s, user=1.2s, speedup=~0.1s
New finalized size: 1213 (depth=27) real=1.2s, user=1.3s, speedup=~0.1s
New finalized size: 609 (depth=28) real=1.3s, user=1.3s, speedup=~0.1s
New finalized size: 307 (depth=31) real=1.4s, user=1.5s, speedup=~0.1s
New finalized size: 156 (depth=32) real=1.4s, user=1.5s, speedup=~0.1s
New finalized size: 81 (depth=35) real=1.5s, user=1.7s, speedup=~0.1s
New finalized size: 44 (depth=36) real=1.6s, user=1.7s, speedup=~0.1s
New finalized size: 26 (depth=38) real=1.7s, user=1.8s, speedup=~0.1s
New finalized size: 22 (depth=42) real=1.7s, user=1.9s, speedup=~0.1s
New finalized size: 18 (depth=45) real=1.8s, user=1.9s, speedup=~0.1s
New finalized size: 14 (depth=46) real=1.8s, user=2.0s, speedup=~0.1s
New finalized size: 10 (depth=47) real=1.9s, user=2.0s, speedup=~0.1s
New finalized size: 8 (depth=48) real=1.9s, user=2.0s, speedup=~0.1s
New finalized size: 6 (depth=52) real=2.0s, user=2.1s, speedup=~0.1s
New finalized size: 5 (depth=53) real=2.0s, user=2.1s, speedup=~0.1s
Reached the end of our path through tree, all nodes were finalized
117 nodes failed, 66 worked, 51 discarded, 1 collapsed
8.263 seconds of compute was required for final path

Strategy "bisect" complete, output 5 bytes
Input file "/usr/share/dict/words" is now 5 bytes, starting strategy "zero"...
Verifying the original input executes successfully... (skip with --noverify)
The original input file succeeded after 0.0 seconds.
New finalized size: 5 (depth=2) real=0.0s, user=0.0s, speedup=~-0.0s
Reached the end of our path through tree, all nodes were finalized
8 nodes failed, 1 worked, 0 discarded, 1 collapsed
0.083 seconds of compute was required for final path

Strategy "zero" complete, output 5 bytes
All work complete, generating output halfempty.out (size: 5)
$ cat halfempty.out 
crash

It works perfectly!

Note: When an application reaches the RLIMIT_AS limit, allocations will start to fail, no signal is sent.

Limiting CPU Time

You're trying to minimize a crash, but some inputs can cause your program to enter an infinite loop. One way to handle this would be using --timeout

$ halfempty --timeout 30 ./yourscript.sh yourinput

This sends a SIGALRM after 30 seconds, and your application can clean up. However, if your application is very badly behaved, it might catch SIGALRM and try to continue. You can enforce a hard limit that cannot be caught using RLIMIT_CPU, once the limit is reached your application will be sent a SIGKILL.

$ halfempty --limit=RLIMIT_CPU=30 ./yourscript.sh yourinput

Note: If you need to create temporary files, please read this FAQ question, you can't trap a SIGKILL and clean up so you need to be careful!

Limiting File Size

You need to prevent an application from creating huge files on error.

You can use RLIMIT_FSIZE to limit the size of files an application can create.

Understanding Return Codes

If your application doesn't handle any signals, then by default signals that cause termination will cause your exit code to be 128 + signo. Here is a table of the most common signals that cause crashes for easy reference.

Signal Name Signal Number Exit Code
SIGILL 4 132
SIGTRAP 5 133
SIGABRT 6 134
SIGBUS 7 135
SIGFPE 8 136
SIGSEGV 11 139

In your test script, the shell puts the return code of the last application in the variable $?, so you would do something like this:

#!/bin/sh

yourprogram --yourargs

if test $? -eq 132; then
    exit 0 # SIGILL, save this input!
else
    exit 1 # Not interested, discard
fi

You can do anything you like in your script, simply exit 0 if the input was interesting (e.g. causes a crash) and exit 1 if it was not interesting.

Halfempty isn't just for minimizing crashes, you can minimize an input that succeeds when it shouldn't, or when output doesn't match the expected output, and so on.

Interacting with GDB

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

#!/bin/sh
exec 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), fault address ($_siginfo._sifields._sigfault.si_addr), and many more. If you want to see more things you can test, try the command show conv in gdb.

Clone this wiki locally