Skip to content

Examples

Jump to bottom
Tavis Ormandy edited this page Mar 17, 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, must 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.

Clone this wiki locally