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
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:
- Replaced sdl2 dependencies with minifb (as I just wanted a window and pixel buffer)
- Rewrote the main function to allow spinning up of many, different cpu instances and states easily
- Added a
FuzzInputstruct that can load in seed tas files and mutate them around given frame points - Modified the Cpu run loop to use FuzzInput instead of user input.
- Hacked in the ability to use a second controller (necessary for some speed run inputs like Legend of Zelda)
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:
- Mutation Rate - the rate at which inputs are changed each run
- Frames To Consider - how far the fuzzer looks ahead before evaluating the input and making a decision about which inputs to try next
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:
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.
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/