Indistinguishable from Jesse

Fuzz-testing is usually only used to find crashes and assertion failures, but my JavaScript engine fuzzer goes beyond catastrophic failures when it tests the decompiler. It checks the decompiled code for signs of incorrectness in two ways.

First, it checks that the decompiled code compiles without giving syntax errors. This finds fun bugs like bug 346904 where the decompiler screwed up in an understandable way, as well as bugs like bug 351496 where the decompilation is complete nonsense.

Second, it checks that the decompiled code is canonical -- compiling and decompiling again should give the exact same representation as the original decompilation. This helps find bugs like bug 381196 where decompilation changes the meaning of the code without introducing a syntax error.

Some decompilation changes, such as bug 352068, did not change the meaning of the code and simply reflected varying amounts of optimization in the compiler. Early in the fuzzer's life, I was able to convince Brendan that it was worth fixing many of those otherwise harmless "round-trip changes" in order to make it possible to find other bugs with this method.

This pair of checks doesn't find all decompiler bugs, of course, but it finds quite a few of them. jsfunfuzz has a few other correctness checks for things like unnecessary parentheses in decompiled code and bogus results from object uneval.

Can you think of other ways to use fuzz-testing to find "correctness" bugs?

The project for the graduate algorithms class I took in Fall was to compare two algorithms for a problem of our choice. I chose to compare two trust metrics, the Advogato trust metric and Google's PageRank. Trust metrics attempt to solve the following problem: "Given a directed graph where an edge from A to B means 'A trusts B', whom should I trust?".

In the case of Advogato, the nodes are Advogato accounts and the edges are explicit certifications. In the case of Google, the nodes are web pages and the edges are links.

A good trust metric makes it difficult for an attacker to gain a large amount of trust. More specifically, we might want the amount of trust an attacker gains to be at most linear in the cost of the attack. It helps to think in terms of "bad" nodes, which are controlled by the attacker, "confused" nodes, which trust bad nodes, and "good" nodes, which are neither bad nor confused.

Proving a statement about the cost of an attack requires assuming something about the cost of compromising or confusing each node. Advogato assumes that the cost of confusing a node is closely related to the node's capacity, which is a function of the node's distance from the root. PageRank assumes that the cost of confusing a page is closely related to the page's popularity, which is in turn estimated by the page's PageRank score.

I discovered a problem with Advogato's security proof: it bounds the trust by the final capacities of the confused nodes rather than their capacities before the attack. An attacker can confuse a single expensive (high-capacity) node and many cheap (capacity 1) nodes, then tell the expensive node to trust the cheap nodes. Now there are many confused nodes with substantial capacity, and the attacker can get get an amount of trust equal to a constant times the square of the cost of the attack.

PageRank does not have this problem. The PageRank score gained by the attacker is bounded by a small constant times the total PageRank-score-before-attack of the confused pages, no matter where the attacker makes confused or bad nodes link.

For more details, you can read my paper for the algorithms class.

I have trouble completing personal projects that take longer than a weekend. I often lose interest after doing the interesting parts and procrastinate indefinitely on completing the projects since they have no deadline. In August 2004, I set a goal compatible with my attention span: "start and finish one interesting project every weekend". This goal helped me write a bunch of Firefox extensions and one or two Firefox patches, but of course it didn't help me finish longer projects. Now I have several half-finished longer-than-a-weekend projects piled up.

I'm hoping that this "coming soon" post will make me finish at least some of these projects soon. Also, you can tell me which projects you want me to finish first.

• A novel attack against something that was proven secure using a what I think is a poor definition of security.
• A proof that a popular puzzle is NP-complete.
• A list of some of Firefox's weaknesses, design elements that can lead to security holes.
• Security tips for Firefox users (current version). Since this document is already 7 printed pages long without screenshots, it may be more effective at pointing out critical user interface flaws in Firefox and Windows than at educating users.
• Security tips for web application developers (current version).
• Security tips for Firefox developers and extension developers (current version).