329066 - (lithium) Lithium, a testcase reduction tool (delta debugger)

Status: RESOLVED FIXED

(Core Graveyard :: Tracking, enhancement)

Description

[Jesse Ruderman]

I wrote a testcase reduction tool that I'm calling Lithium.  I'm about to attach an alpha version to this bug.

I've already used it to reduce two Stir DOM assertions, bug 328944 and bug 328946.  This alpha should also work with other line-based fuzzers such as Random Styles, Random JS, and CSSGen.  A future version will work with other fuzzers whose output has more fragile structure (e.g. xangle, stirdom-during-mutation-events).

It's extensible to types of bugs other than assertions, hangs, and crashes.  If you want to reduce a testcase that leaks, triggers valgrind warnings, makes Firefox stop painting, or even creates a different DOM two versions of Firefox, you just have to create a program or script whose return value indicates whether the bug was triggered.

Bob Clary expressed concern that releasing this tool would make it easier for blackhats with fuzz-testing tools to create reliable exploits.  Fuzz testing is certainly not unknown outside of the Mozilla security group (see e.g. bug 328937 comment 7 and bug 264944).  On the other hand, releasing it would have some benefits: easier reductions for bug reporters and Gecko hackers outside of the security group (automated testcase reduction is useful even with non-fuzz testcases), and feedback on the tool itself.

I'm making Lithium live in this security-sensitive bug for now.  Even if we released Lithium before we release our fuzzers, this bug would remain security-sensitive because it mentions our fuzzers.

Comment 1

[Jesse Ruderman]

Attachment: lithium 0.1

Comment 2

[Jesse Ruderman]

Attachment: Lithium 0.2

Now lets you choose whether to treat the testcase as consisting of characters, lines, or a tree of open-close pairs whose structure is guessed from indentation.

I've used this to reduce bugs found with Stir DOM, Random JS, and Xangle.  These have included assertions, leaks, and a crash.  Other than the horrible UI, it works pretty well: it seems to reduce testcases a bit faster than I can by hand. (I usually reduce the testcase further by hand, but I'd have to do that anyway.)

Comment 3

[Jesse Ruderman]

Attachment: Lithium 0.3

Much more user-friendly than the previous version.

Example invocation:

./lithium L myhang.html firefox hangs 10

Comment 4

[Jesse Ruderman]

Attachment: Lithium 0.4

Now works on Windows (in addition to Mac).  Several minor bug fixes.

Comment 5

[Jesse Ruderman]

Attachment: Lithium 0.5

* You can now put e.g. "-c 2" before the other arguments to make Lithium only do a single run through the file, with a given chunk size.

* Visual round summaries, e.g. "SS -S" means the first, second, and fourth chunks survived and the third chunk was removed.  There are spaces between each pair of characters to indicate which chunks were grouped together in the previous round.  If you see "--" in a round summary, that means something weird is happening.

Comment 6

[Jesse Ruderman]

The session restore feature in Firefox trunk nightlies can interfere with Lithium.  To turn it off, use:

user_pref("browser.sessionstore.resume_from_crash", false);

Comment 7

[Jesse Ruderman]

Martijn says this doesn't work with mingw gcc -- it says something about not finding sys/wait.h.  I don't know how to fix that in Lithium, so the workaround for now is to use cygwin gcc.

Comment 8

[Jesse Ruderman]

Attachment: Lithium 0.6

* Progress and summary information is now put in lith.log in addition to being output to the console.  This is useful if you're running debug builds and their spew drowns out Lithium's information.  Use tail -f lith.log if you want to keep an eye on lith.log, I guess.

* Made it write a file called most-reduced-testcase every time it successfully takes out a chunk.  This usually happens more frequently than end-of-round, so it can be useful if you want to break in the middle of a round.

* Fixed a bug Martijn found: in C mode, Lithium can remove the line break just before e.g. "<!-- DDEND -->", causing a subsequent run of Lithium to think some more stuff is part of the DDEND line.  (The fix was a bit of a hack: always add an extra line break when in C mode.)

Comment 9

[Jesse Ruderman]

[e-mail], you might find this useful for reducing some of your fuzz testcases, such as the one in bug 377741.

Comment 10

[Jesse Ruderman]

Attachment: Lithium 0.9 (rewritten in Python)

* Rewritten in Python.
* New command-line structure.
* More options for tweaking the algorithm and for using different algorithms (e.g. "try to remove a pair of lines from the file").
* No more "guessing tree structure based on indentation".

Comment 11

[Jesse Ruderman]

Attachment: Lithium 0.9.1

This version has improved documentation.

Comment 12

[Jesse Ruderman]

Colin suggested changing the 'interestingness tests' API to be less of a hack.  Currently, an 'interestingness test' is a program that takes command-line arguments and uses return codes.  Maybe they should be Python files instead.  (I'm guessing Lithium would use __import__ or execfile to load a file that would supply a function or a class with a method.)

Comment 13

[Jesse Ruderman]

http://www.squarefree.com/2007/09/15/introducing-lithium-a-testcase-reduction-tool/

Comment 14

[Daniel Veditz [:dveditz]]

Jesse: can we unhide this bug? Lithium is long public, and people know we fuzz test so the mere names of our fuzzers shouldn't be sensitive