Indistinguishable from Jesse

Last week, I asked Luke Wagner to explain some security bugs that he fixed in the past. I hoped to learn from each bug at multiple levels, in ways that could help prevent future security bugs from arising and persisting.

Luke is one of the developers working on Firefox's JavaScript engine, which is currently our largest source of critical security bugs.

Method

I imagined we would recurse in exhaustive breadth and exhausting depth. Instead, we recursed only on the most interesting items, and refined a checklist of starting points:

• What was the bug?
• What went wrong in the developer's thinking that caused the bug to be introduced?
• What made the bug exploitable?
• What caused us to use especially dangerous features of C++?
• Could a new abstraction make it possible to do this both fast and safe?
• What caused the bug to persist? Could we have caught this earlier with improved regression tests, fuzz testing, dynamic analysis, or static analysis?

Luke and I made trees for all ten bugs, at first on paper and later using EtherPad. Then I extracted and categorized what I thought were the most useful lessons and recommendations.

Recommendations for introducing fewer bugs

Casts

• Create centralized, type-restricted cast functions. This protects you when you change the representation of one of the types. It also protects against mistakes that cause the input type to be incorrect.

Sentinel values

• Use tagged unions instead.
• Use a typed wrapper (a struct containing a single value). When assigning from the underlying numeric type, convert using one of two functions: one that checks for special values, and one that explicitly does not.
• Audit existing code paths to ensure they cannot generate the special value.

Clarity of invariants

• Increase use of methods named AssertInvariants
• Create an alias for JS_ASSERTION called JS_INVARIANT.

Interacting with other developers

• If you're about to do something gross because someone else doesn't expose the right API/helper, maybe you should get it exposed.

JS Engine specific

• Any patch that touches rooting should be reviewed by Igor.
• Interpreter could have better abstraction and encapsulation for its stack.

Recommendations for catching bugs earlier

Static analysis

• Find all casts (C-style casts, the reinterpret_cast keyword, and casts through unions) for a given type. Could be used to enforce centralization or to find things that should be centralized.
• Be suspicious of a function with multiple return statements, all of which return the same primitive value.
• Be suspicious of a function returning true/success in an OOM path.

Dynamic analysis

• Ask Valgrind developers what they think of providing (in valgrind.h) a way to tie the addressability of "stacklike memory" to a variable that represents the end of the stack.

Fuzzing

• We should fuzz worker threads somehow.
  • In browser (slow and messy, but it's what users are running).
  • In thread-safe shell (--enable-threadsafe?), which has "toy workers".
• We should fuzz compartments better.
  • I should ask Blake and Andreas for help with testing compartments and wrappers.
  • I should ask Gary to run jsfunfuzz in xpcshell, where I can test both same-origin and different-origin compartments, and thus get more interesting wrappers.
• We should give JS OOM fuzzing another shot.

Next steps

I'm curious if others have additional ideas for what could have prevented the ten bugs we looked at. For example, someone like Jeff Walden, who loves to write exhaustive regression tests, might have ideas that Luke and I did not consider.

I'd also like to do this kind of analysis with a other developers on bugs they have fixed.

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:

<script>
function quit()
{
  var evt = document.createEvent("Events");
  evt.initEvent("please-quit", true, false);
  document.dispatchEvent(evt);
}
window.addEventListener("load", function() { 
  setTimeout(quit, 1000);
}, false);
window.onerror = quit;
</script>
<!-- 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"); 
  document._write(s);
};

__noSuchMethod__

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 "this.foo()" rather than "foo()".

Pretty-printing JavaScript

You can use jsbeautifier.org 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.

I gave my new fuzzer a break from testing TraceMonkey by asking it to look for differences between SpiderMonkey and JavaScriptCore. I have listed them below, with SpiderMonkey output above JavaScriptCore output.

I have no idea how many of these are bugs (in SpiderMonkey or JavaScriptCore) and how many are ambiguous in the spec (intentionally or unintentionally).

Early error reporting

SpiderMonkey reports some errors at compile time that JavaScriptCore only reports at run time, if the code is actually hit. The difference is most obvious (and most likely to cause compatibility problems) if the code is skipped.

> if (false) { --1; }
S: SyntaxError: invalid decrement operand
J: (no error)

> if (false) { return; }
S: SyntaxError: return not in function
J: (no error)

instanceof

The two engines disagree about what objects are reasonable operands for the 'instanceof' operator.

> ({} instanceof {a:2})
S: typein:3: TypeError: invalid 'instanceof' operand ({a:2})
J: false

> ({} instanceof eval)
S: false
J: Exception: TypeError: instanceof called on an object with an invalid prototype property.

new with native functions

SpiderMonkey allows the "new" operator to be used with some native functions that JavaScriptCore considers non-constructors.

> new Math.sqrt(16)
S: 4
J: Exception: TypeError: Result of expression 'Math.sqrt' ... is not a constructor.

> new ({}.toString)
S: [object Object]
J: Exception: TypeError: Result of expression '({}.toString)' ... is not a constructor.

> new eval
S: typein:9: EvalError: function eval must be called directly, and not by way of a function of another name
J: Exception: TypeError: Result of expression 'eval' ... is not a constructor.

Converting between numbers and strings

> print(+'\00000027')
S: NaN
J: 0

> (1e-10).toString(16)
S: 0.000000006df37f675ef6ec
J: 0

const

There are subtle differences in handling of this new keyword.

> const d; const d;
S: TypeError: redeclaration of const d
J: (no error)

> const c = 0; print(++c);
S: 0
J: 1

Other differences

> print((function(){return arguments;})());
S: [object Object]
J: [object Arguments]

> typeof /x/
S: object
J: function

See Mozilla bug 61911, which changed this in SpiderMonkey in 2007.

Making JavaScript faster is important for the future of computer security. Faster scripts will allow computationally intensive applications to move to the Web. As messy as the Web's security model is, it beats the most popular alternative, which is to give hundreds of native applications access to your files. Faster scripts will also allow large parts of Firefox to be written in JavaScript, a memory-safe programming language, rather than C++, a dangerous footgun.

Mozilla's ambitious TraceMonkey project adds a just-in-time compiler to Firefox's JavaScript engine, making many scripts 3 to 30 times faster. TraceMonkey takes a non-traditional approach to JIT compilation: instead of compiling a function at a time, it compiles only a path (such as the body of a loop) at a time. This makes it possible to optimize the native code based on the actual type of each variable, which is important for dynamic languages like JavaScript.

My existing JavaScript fuzzer, jsfunfuzz, found a decent number of crash and assertion bugs in early versions of TraceMonkey. I made several changes to jsfunfuzz to help it generate code to test the JIT infrastructure heavily. For example, it now generates mixed-type arrays in order to test how the JIT deals with unexpected type changes.

Andreas Gal commented that each fuzz-generated testcase saved him nearly a day of debugging: otherwise, he'd probably have to tease a testcase out of a misbehaving complex web page. Encouraged by his comment, I looked for additional ways to help the TraceMonkey team.

JIT correctness

Differential testing is designed to find correctness bugs. It runs a randomly-generated script twice (with and without the JIT) and complains if the output is different.

It quickly found 13 bugs where the JIT caused JavaScript code to produce incorrect results. These bugs range from obvious to obscure to evil.

It even found at least one security bug that jsfunfuzz had missed. An uninitialized-memory-read bug caused output to be random when it should have been consistent. jsfunfuzz missed the bug because it ignores most output, but the differential testing caught it just like it would catch a JIT vs interpreter difference.

JIT speed

I set up the new fuzzer to compare the time needed to execute scripts and complain whenever enabling the JIT made a script run more slowly. It measures speed by letting the script run for 500ms and reporting the number of loop iterations completed in that time.

So far, it has found 4 serious bugs where the JIT makes scripts several times slower. Two of these have already been fixed, but the other two may be difficult to fix.

It has also found 10 cases where the JIT makes scripts about 10% slower. Most of these minor slowdowns are due to "trace aborts", where a piece of JavaScript is not converted to native code and stays in the interpreter. Some trace aborts are due to bugs, while others are design decisions or cases for which conversion to native code simply hasn't been implemented yet.

There is some disagreement over which trace aborts are most likely to affect real web pages. I asked members of Mozilla's QA team to scan the web in a way that can answer this question.

Interpreter speed

Mostly for fun, I also looked to see which code the JIT speeds up the most. Here's a simplified version of its answer:

for (var i = 0; i < 0x02000000; ++i) {
  d = 0x55555555;
  d++; d++; d++; d++; d++;
}

This code runs 250 times faster when the JIT is enabled. The JIT is able to achieve this gigantic speedup due to the interpreter being inefficient in dealing with undeclared variables and numbers that can't be represented as 30-bit ints.

Assertions

The JavaScript engine team has documented many of their assumptions as assertions in the code. Many of these assertions make it easier to spot dangerous bugs, because the script generated by the fuzzer doesn't have to be clever enough to actually cause a crash, only strange enough to violate an assumption. This is similar to my experience with other parts of Gecko that use assertions well.

Other JavaScript engine assertions make it easier to find severe performance bugs. Without these assertions, I'd only find these bugs when I measure speed directly, which requires drastically slowing down the tests.

More ideas

One testcase generated by my fuzzer demonstrated a combination of a JIT performance bug with a minor bytecode generation bug. I might be able to search for similar bytecode generation bugs the same way I searched for decompiler bugs: by ensuring that a function does not change when round-tripping through the decompiler. In order to do that, I'll need a new patch for making dis() return the disassembly instead of printing it.

I should be able to find some performance bugs by looking at which aborts and side exits are taken. This strategy would make some performance bugs (such as repeatedly taking a side exit) easier to spot.

DOM 2 does not allow nodes to be moved between documents -- in fact, it requires that implementations throw an error when code tries to do so. But for years, Gecko has not enforced this rule.

It's a bit embarrassing that Internet Explorer gets this right and we get it wrong. Someone might think Gecko is trying to embrace and extend the DOM.

Soon, Gecko will start enforcing the rule on trunk. But bringing Gecko in line with this aspect of the DOM spec risks breaking Gecko-specific code, such as code in extensions and bookmarklets written for Firefox. For example, my Search Keys extension used to create some nodes in the chrome document, and some in the foreground tab, before putting them in the tab that that just loaded. Search Keys 0.8 creates all elements in the correct document.

I also updated the following bookmarklets to create nodes in the correct document and/or use importNode when copying nodes between documents:

• Validation bookmarklets: list alts
• Web development bookmarklets: partial source, view style sheets, view scripts
• Text and data bookmarklets: view selection
• Bookmarklets for testing browsers: clone document

These bookmarklets previously only worked in browsers that violated the DOM spec by allowing nodes to be moved between documents without a call to importNode or adoptNode. Maybe some of them work in IE now.

If you use those bookmarklets, you should grab the new versions so they won't break when you update to next week's trunk build or to Firefox 3.

A desperate web developer emailed me asking how make a bookmarklet that does something with the selected text, where the selected text is usually in a textarea.

He had tried using window.getSelection.toString(), but that doesn't work, because window.getSelection() is implemented in terms of DOM Ranges and it doesn't make much sense to have a DOM Range inside a textarea.

Here are some of the methods I tried:

• Determine focus using by tracking with onfocus or onblur events. Works for web pages, but doesn't work for bookmarklets.
• Determine focus using window.getSelection().getRangeAt(...) and commonAncestorContainer. Doesn't work (bug 336936).
• Determine focus using a XUL document in an iframe and commandDispatcher.focusedElement. Ugly Firefox-only hack, but it works.
• Determine focus using WhatWG's document.currentFocus. Only a working draft, not implemented in Firefox yet (bug 337631).
• Use selectionStart / selectionEnd in all textareas. This can return nonempty selections from multiple textareas.

Am I missing a sane solution that works in current versions of Firefox?

SVG support

SVG is W3C specification providing resolution-independent scalable vector graphics, along with a DOM. Firefox 1.5 supports a subset of SVG 1.1. For more information, see SVG in DevMo.

Canvas Support

<canvas> is a scriptable bitmap drawing surface. It is suitable for many uses, such as drawing dynamic graphs and game graphics. For more information, see Drawing Graphics with Canvas or the Canvas tutorial.

Hidden referrer column for history

Extensions can now access the referrer information for pages stored in the browser history. This feature can be used to provide alternate history views and other useful functionality. For example, my How'd I Get Here? extension uses this feature.

API for prioritizing HTTP connections

The Mozilla networking library now supports the prioritization of connections to a specific server. (See nsISupportsPriority.)

API for configuring proxies

It is now possible for extensions to easily override the proxy configuration without affecting user-visible preferences. (See nsIProtocolProxyService, nsIProtocolProxyFilter, and nsIProtocolProxyCallback.)

API for managing user and UA stylesheets

Extensions can now register stylesheet URIs as additional user and UA stylesheets. This means extensions no longer have to try to edit userContent.css to add styling (say for XBL binding attachment) to web pages. This makes it easier to implement extensions like Flashblock. For details on using this API, see Using the Stylesheet Service.

Site-specific user style sheet rules

Firefox now supports site-specific user style sheet rules. While advanced users can edit userContent.css to use this feature directly, an extension could also take advantage of this feature using the API for managing user style sheets above.

Dynamic Overlays

Loading of XUL overlays after the document has been displayed is now supported. (See nsIDOMXULDocument.)

Translucent Windows (Windows/Linux)

On Windows and Linux, XUL windows with a transparent background are now supported. This allows whatever is below the window to shine through the window background.

New Preferences Bindings

These new bindings make it easier to create preferences windows for extensions. The new preferences windows support instant-apply behavior, which is enabled by default on Mac and Linux.

API for implementing new command-line switches

An extensible API has been introduced so that extensions can easily handle complex command-line flags. (See nsICommandLine and nsICommandLineHandler.)

XTF Support

The eXtensible Tag Framework allows adding support for new namespaces using XPCOM components to Mozilla (written in JavaScript or C++). For example, the Mozilla XForms Project uses XTF to add support for the XForms namespace. See the XTF Home Page.

Cryptographic hash API

Extensions now have access to several cryptographic hash functions, including MD5, SHA-1, and several flavors of SHA-2. (See nsICryptoHash.)

Rich list box

<xul:richlistbox> is a new widget that Firefox's Download Manager and Extension/Theme manager now use. For more information, see XULPlanet: richlistbox or DevMo: richlistbox.

Access to nsIEditor of textboxes

Firefox now has a supported method for getting the nsIEditor of textboxes and textareas, making it easier to implement features such as spell checking for web forms. For more information, see bug 303727 or nsIDOMNSEditableElement.

Access to nsIPipe

See bug 300423 or nsIPipe.

Other improvements

This post emphasizes new features since Firefox 1.0.7 over things that have changed since Firefox 1.0.7, but here are a few important things that have changed:

• Improvements to evalInSandbox make it easier for extensions like Greasemonkey to inject scripts into web pages safely.
• Improvements to designMode (WYSIWYG HTML editing) make it more suitable for use in extensions.
• Extensions can now include search plugins, plugin DLLs, and platform-specific XPCOM components.
• Extensions can now add to the user-agent string in a safe way.
• There are now extra ways to install and uninstall extensions, especially Firefox extensions that are shipped with Windows programs.
• New JavaScript language features allow extension developers (and web developers who only target Firefox) to manipulate arrays and XML concisely.
• There have been many changes in XUL, especially to the XUL tree widget.
• Extensions written using JavaScript now use XPCNativeWrappers by default, making it easier to write extensions that manipulate web content without introducing security holes.
• Extensions can now specify that they are compatible only with specific versions of Firefox (e.g. Firefox 1.5.0.2). Most extensions that work with Firefox 1.5 should set their maxVersion as 1.5.0.*, indicating that they will work with future security releases (unless some of those releases contain API changes, which is unlikely and will cause them to be numbered e.g. Firefox 1.5.1). See this page for more information.

Parts of this post were taken from this page, which was based on a wiki page, which was based on an early version of my changelog for Deer Park Alpha 1. It might be merged with this wiki page in the future.

AutoLink turns plain text URLs, email addresses, bug numbers, ISBNs, and US phone numbers into links. For example, it turns all of these into links:

• http://www.squarefree.com/userscripts/
• jruderman@gmail.com
• Bug 162020
• Bug 162020 comment 0
• ISBN 0-340-82899-4
• (555) 555-5555

You can add new filters if you know how to use JavaScript regular expressions. Here is an example filter, rewrapped to fit in my blog:

  {
    name: "Bug number",
    regexp: /bug \#?(\d+)/ig,
    href: function(match) {
      return
        "https://bugzilla.mozilla.org/show_bug.cgi?id=" + 
          match[1];
    }
  }

To install a user script into Firefox, install Greasemonkey, restart Firefox, open the user script, and select "Install User Script..." from the Tools menu.