cross_fuzz is an amazingly 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 it 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.
The cross_fuzz fuzzing Algorithm
- 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.
- 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.
- 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).
- 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.
- Randomly destroy first document using one of the several possible methods, toggle garbage collection.
- 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.
- 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.
You can download cross_fuzz here:
http://lcamtuf.coredump.cx/cross_fuzz
Or read more here.
