Optimizing our way through Metroid

Antithesis sells an advanced and rather expensive software testing service that customers use to test software like databases in an isolated, simulated environment. It uses fuzzing to find bugs. (More here).

Apparently they’ve been running it on 8-bit video games to see how good it is at exploring all possible states of a program being tested.

So they tried it on Metroid. From the article:

[T]he problem is that we don’t have any more missiles. Getting through one of those red doors in Metroid requires firing 5 missiles at it. But that’s just a single example of us standing in front of the door. In order to prove that this is the problem, what we really want to ask our database is: “do we ever get close to the red door with 5 or more missiles in our inventory?”

Questions like this are pretty important when trying to determine why your test system is or isn’t finding some bug, so we have a whole product feature to help you ask it.

…

Metroid was the most taxing Nintendo game beaten by Antithesis so far, and forced us to invent multiple new state-space exploration techniques, chief among them the capability to fuzz a program while dragging along an orthogonal optimization objective. But if you think about it, this capability is core to what a fuzzer needs to do. Want to look for memory leaks while fuzzing an API? That’s optimization! Looking for hangs or other performance anomalies in a distributed system? Fuzz with optimization! Trying to find an input that causes some buffer to overflow? Optimization may do the trick!

They also solved Zelda and other games.