Published: 2021-11-27

Writing a Fuzzer for Nes Games

My project this weekend was a fuzzer for nes games based on seeded input from TAS movies.

Tool assisted speedruns


A screenshot of the tiled windows. Each window showing a different fuzzing run.

Basic Setup

nesfuzz built on top of the nestur emulator by spieglt.

I looked into a number of different possibilities for a base, but my main requirements were something written in rust and something not too embedded to the idea of “an app”.

I made the following big changes to nestur:

This functionality is still very incomplete.

To begin fuzzing the tool needs a rom file, and a sample input file. For sample inputs see TasVids.

nessfuzz <rom> <tas file> nessfuzz smb.rom happylee-supermariobros,warped.fm2

nesfuzz uses the seed input to find novel RAM configurations and search the possible input space. It will also tile 28 (by default), windows to allow you to see the fuzzing happen (this dramatically slows down fuzzing, but makes the whole thing much more visually interesting).

Parameters

There are a number of different parameters than impact how a fuzzing run turns out, a few big ones are:

Results

The biggest win of the weekend was when the fuzzer was given happylee-supermariobros,warped.fm2as input and found a path to the World 5 warp glitch in World 1-2:


A fuzzing run showing a few runs making it to world 5 from world 1-2

I ws then able to modify the fuzzer to detect when Mario had reached World-5 and generate a set of inputs that could be played back on an emulator.

Overall this exceeded my expectations for this weekend. It demonstrated that, at a minimum the fuzzer can find glitches not in the original input, and can generate a new set of inputs that can be given to an external emulator to replicate the glitch!

As such the main challenge facing this fuzzer going forward are around optimizing mutation and selection to pick interesting runs.

Known Issues

The only game that really works as expected is Super Mario Bros. with the happylee-supermariobros,warped.fm2 input. This is probably because of issues in the underlying emulator / differences in the expected behaviour of the system the tas inputs are produced for v.s. the emulator.


The fuzzer playing final fantasy.

Other games like Legend of Zelda, Megaman, Super Mario Bros. 3, Final Fantasy II etc. will run, but tas inputs from them quickly become out of sync with the actual gameplay. Further research is needed to as to why that is. Any help in tracking these emulator bugs down is appreciated!

As noted above, many speed runs, and some of the more interesting bugs require exploiting input from a second controller. I didn’t have time to dive into exactly how player 2 controllers work on the NES this weekend and so my first attempt at this implementation is buggy. It seems to work fine for Legend of Zelda, but causes issues if the feature is enabled in other games.

Note from future Sarah: This now works.

Finally, there is an issue with the cpu clock / soft reset which causes a one frame difference in behaviour between emulated runs and fuzzed runs. This means a tiny modification needs to be made to runs exported from nesfuzz before they can be run in an emulator. This might also be related to the issue described above.

Future Extensions

Right now novelty is driven by the hamming distance of the ram of the cpu compared to observed values. Better performance can be achieved by changing the novelty function to focus on specific RAM values / be more game specific.

There are also a number of possible extensions in the replacement algorithm. Right now the fuzzer makes no attempt to “lock-in” good paths and so the engine is likely to reconsider all past values. This leads to the queue of inputs growing without bound (eventually causing the application itself to be refused memory from the kernel).

Source Code

You can find the source code for nesfuzz at https://git.openprivacy.ca/sarah/nesfuzz/




About This Site

This is a site where I dump essays, ideas, thoughts, math and anything else that doesn’t fit into another format, or isn’t yet ready for a longer paper. Beware: Ideas may be half thought through and/or full of errors. Hic sunt dracones.


Recent Articles

2023-03-30Retrospective: Winter of Pipelines
2022-12-31Change, Control, Habits, and Productivity
2022-10-05Exploit Disclosure: Turning Thunderbird into a Decryption Oracle
2022-06-03An Extended Reply Regarding Auditing Anonymity Networks
2022-05-14Ideas for a better IDE
2022-04-25Federation is still the Worst of All Worlds
2022-03-21A brief introduction to insecurity buttons
2022-02-28A Queer Kind of Hope
2022-01-16Private and Decentralized Human Readable Names with Fuzzy Message Detection and Delay Towers
2021-11-27Writing a Fuzzer for Nes Games
2021-11-08Defining (De)Centralization in a Useful Way (The thing you are supposed to be decentralizing is power)
2021-11-02Extending Fuzzy Message Detection to Groups
2021-09-09Rough Cut: Oblivious Transfer
2021-08-30Building a Home-made Hydrogen Line Telescope
2021-08-19NeuralHash, Semantics, Collisions and You (or When is a Cat a Dog?)
2021-08-16Revisiting First Impressions: Apple, Parameters and Fuzzy Threshold PSI
2021-08-12A Closer Look at Fuzzy Threshold PSI (ftPSI-AD)
2021-08-10Obfuscated Apples