Archive for the 'Reduction' Category

Reducing real-world scripts

Sunday, January 11th, 2009

Lithium is great at reducing testcases with simple structures, such as scripts generated by jsfunfuzz. Scripts from web pages are harder to reduce, since removing a line frequently introduces a syntax error. But with a few extra tricks, Lithium can be effective against real-world scripts. For example, when Google Maps triggered a JavaScript Engine assertion, I was able to reduce the 40 KB of Google Maps code to five lines.

I've reduced three other JavaScript engine bugs using these methods, but there are many more that could use help.

Start by saving the page using wget -E -H -k -K -p or one of the other methods on DevMo: Reducing Testcases.

Making Firefox exit quickly

For Lithium to reduce a web page quickly, Firefox needs to exit quickly. To make normal exits fast, install Quitter and make the testcase send a special event to Quitter after onload:

function quit()
  var evt = document.createEvent("Events");
  evt.initEvent("please-quit", true, false);
window.addEventListener("load", function() { 
  setTimeout(quit, 1000);
}, false);
window.onerror = quit;
<!-- DDBEGIN -->

Making Firefox crash quickly

On Mac OS X, crashes are surprisingly slow: it takes the OS crash reporter about 40 seconds to generate a crash log for Firefox. I don't know a general way to bypass the OS crash reporter, but there are two easy cases. First, for crashes that are easy to anticipate at the code level, such as null dereferences, adding a conditional exit(3) should do the trick.

Second, as of Mac OS X 10.5, fatal assertions are treated as crashes. To make the OS treat fatal assertions as exits rather than crashes, edit the relevant assertion-failure function (JS_Assert or NanoAssertFail) to call "exit(3);" rather than "abort();". To make your debug build pick up this change, run "make -C js/src" from the objdir.

Finding the scripts

An initial run of Lithium should make it clear which external <script> tags are involved in triggering the bug. Convert them to inline scripts so they're no longer loaded over the Web.

You may find that one script calls document.write to include another script. Add this code to the script at the top to see what additional scripts are being included:

document._write = document.write;
document.write = function(s) { 
  dump("document.write(" + uneval(s) + ");\n"); 


You can use SpiderMonkey's nonstandard __noSuchMethod__ feature to turn "no such method" errors into no-ops. This helps Lithium reduce object-oriented scripts by allowing it to remove entire methods even before their callers have been removed.

Object.prototype.__noSuchMethod__ = function(id, args) {
  dump("Missing method called: " + id + "\n");

Note that __noSuchMethod__ does not work for top-level functions unless they are explicitly called as "" rather than "foo()".

Pretty-printing JavaScript

You can use or the decompiler built into SpiderMonkey to transform the script into a form that is friendlier to Lithium.

To trigger SpiderMonkey's decompiler, wrap the entire script in an anonymous function and use dump (in the browser) or print (in the shell).

The decompiler has two modes: toString creates one line per statement, while uneval creates one line per function declaration. You'll probably want to run Lithium at least once for each mode, since toString makes it easy to eliminate unnecessary expression-statements while uneval makes it easy to eliminate unnecessary function declarations.

Moving to the shell

As soon as the script seems like it isn't too entangled with the browser DOM, try to eliminate the remaining references to the browser-specific "window" and "document" objects. This should allow you to reproduce the bug in the standalone SpiderMonkey shell, which starts much faster than Firefox (milliseconds rather than seconds).

Note that to reproduce JIT bugs in the shell, you need to use the "-j" switch.

Finishing touches

Lithium may have left empty "if" or "for" blocks, which can almost always be removed. To make the remaining code as simple as possible, try replacing variables with their values and inlining functions. If the code is object-oriented or uses call/apply, this might require a little thinking, but it's usually straightforward.

This post was revised 2009-07-06.

Introducing Lithium, a testcase reduction tool

Saturday, September 15th, 2007

I wrote a tool called Lithium that automatically reduces large testcases, such as real-world web pages or testcases produced by jsfunfuzz. It can usually reduce a 3000-line jsfunfuzz crash testcase to 3-10 lines in several minutes, considerably faster than I can reduce by hand. Perhaps more importantly, I can do something else while it reduces the testcase.

There are two (related) reasons I'm not calling it "Lithium 1.0" yet. First, I'm hoping to improve the way "interestingness tests" are written. Currently, they're separate programs that communicate to Lithium using their exit code, which limits error handling and might slow Lithium down. I'd like to make the interestingness tests be Python files, but I'm not sure what the best way to do that is. (Should Lithium __import__ the interestingness test? Or should the interestingness test import Lithium and be renamed to e.g. ""?)

Second, it would be useful to be able to pass extra arguments to the program being tested. For example, it would be useful to be able to pass a profile name to Firefox, or to pass a Firefox path to Valgrind. One possibility is to put the program being tested last on the command line, so extra positional arguments become options to that program. This solution would only work for interestingness tests that launch a single program (so it wouldn't work for a "renders differently in these two Firefox builds" test, for example), but maybe that's okay. Another possibility is to require the use of a config file for passing arguments to programs being tested (so you don't end up typing all of ".../firefox-bin -P foo" on Lithium's command line).

I'll probably use the MIT license for Lithium (but not for, which was mostly written by Chris Cooper and Bob Clary).