Announcing cross_fuzz, a potential 0-day in circulation, and more

I am happy to announce the availability of cross_fuzz - a surprisingly effective but notoriously annoying cross-document DOM binding fuzzer that helped identify about one hundred bugs in all browsers on the market - many of said bugs exploitable - and is still finding more.

The fuzzer owes much of its efficiency to dynamically generating extremely long-winding sequences of DOM operations across multiple documents, inspecting returned objects, recursing into them, and creating circular node references that stress-test garbage collection mechanisms.

Detailed cross_fuzz fuzzing algorithm:

1. Open two windows with documents of any (DOM-enabled) type. Simple HTML, XHTML, and SVG documents are randomly selected as targets by default - although any other, possibly plugin-supported formats could be targeted instead.

2. Crawl DOM hierarchy of the first document, collecting encountered object references for later reuse. Visited objects and collected references are tagged using an injected property to avoid infinite recursion; a secondary blacklist is used to prevent navigating away or descending into the master window. Critically, random shuffling and recursion fanout control are used to ensure good coverage.

3. Repeat DOM crawl, randomly tweaking encountered object properties by setting them to a one of the previously recorded references (or, with some probability, to one of a handful of hardcoded "interesting" values).

4. Repeat DOM crawl, randomly calling encountered object methods. Call parameters are synthesized using collected references and "interesting" values, as noted above. If a method returns an object, its output is subsequently crawled and tweaked in a similar manner.

5. Randomly destroy first document using one of the several possible methods, toggle garbage collection.

6. Perform the same set of crawl & tweak operations for the second document, but use references collected from the first document for overwriting properties and calling methods in the second one.

7. Randomly destroy document windows, carry over a percentage of collected references to the next fuzzing cycle.

This design can make it unexpectedly difficult to get clean, deterministic repros; to that effect, in the current versions of all the affected browsers, we are still seeing a collection of elusive problems when running the tool - and some not-so-elusive ones. I believe that at this point, a broader community involvement may be instrumental to tracking down and resolving these bugs.

I also believe that at least one of the vulnerabilities discovered by cross_fuzz may be known to third parties - which makes getting this tool out a priority.

The following summarizes notification and patch status for all the affected vendors:

• Internet Explorer: MSRC notified in July 2010. Fuzzer known to trigger several clearly exploitable crashes (example stack trace for CVE-2011-0346) and security-relevant GUI corruption issues (XP-only, example, CVE-2011-0347). >Reproducible, exploitable faults still present in current versions of the browser. I have reasons to believe that one of these vulnerabilities is known to third parties.

  Comment: Vendor has acknowledged receiving the report in July (case 10205jr), but has not contacted me again until my final ping in December. Following that contact attempt, they were able to quickly reproduce multiple exploitable crashes, and asked for the release of this tool to be postponed indefinitely. Since they have not provided a compelling explanation as to why these issues could not have been investigated earlier, I refused; see this timeline for more.

• All WebKit browsers: WebKit project notified in July 2010. About two dozen crashes identified and addressed in bug 42959 and related efforts by several volunteers. Relevant patches generally released with attribution in security bulletins. Some extremely hard-to-debug memory corruption problems still occurring on trunk.

• Firefox: Mozilla notified in July 2010. Around 10 crashes addressed in bug 581539, with attribution in security bulletins where appropriate. Fuzzing approach subsequently rolled into Jesse Ruderman's fuzzing infrastructure under bug 594645 in September; from that point on, 50 additional bugs identified (generally with no specific attribution at patch time). Several elusive crashes still occurring on trunk. Bad read / write offset crashes in npswf32.dll can also be observed if the plugin is installed.

• Opera: vendor notified in July 2010. Update provided in December states that Opera 11 fixed all the frequent crashes, and that a proper security advisory will be released at a later date (release notes list a placeholder statement: "fixed a high severity issue"). Several tricky crashes reportedly still waiting to be resolved.

  Note that with Opera, the fuzzer needs to be restarted frequently.

Well, that's it. To download the tool or see it in action, you can follow this link. The fuzzer may be trivially extended to work with any other DOM-compliant documents, plugin bindings, and so forth.