Checking for idempotency: a bodgey formatter fuzzer
My good friend was telling me about this new testing technique he was researching and exploring called “fuzzing” where you squint and pretend that throwing lots of different inputs at a program is equivalent to proving there are no bugs. Similar to how machine learning will replace all programs as we know today 🙂
I wanted to try my hand at writing a fuzzer but I had little reason to fuzz a rust program, though I love my little collection of RIIR cli tools, I turned my eye towards the prettier code formatter. Precisely, the golang html/template plugin.
Someone took that “language” and wrote an AST parser for it, then wrapped a prettier printer around that output. It worked great! Except when it didn’t. And it was hard to reduce what the actual cause of the bug was, to find the root cause.
I ended up exploring tools like jsfuzz bought by Gitlab, but ended up abandoning them because I couldn’t get around OOM presumably from prettier have too many globals hang around.
I used radamsa, a cli fuzzer to produce files for prettier to format, then format again. I eventually ended up with a script that found a bug if either the output of the first and seocnd format was different, or if the first format succeeded and the second format errored.
the problem was that the generated crash cases were often enormous in size
I researched a method to reduce these failure cases and ended up finding delta (8) which is a very dumb “give me a script that tests for the behavior and i’ll binary search the lines of code to find the bug”
it works great!
this also was helped by the existing thorough unit test fixtures that I could use to feed radamsa as seeds, so that it could alter the seeds for its purposes, like a GMO corn seed 🙂
I found about 7 different idempotency bugs that imo greatly improved the reliability of the formatter, especially since i can now continually run the fuzzer without immediately running into a crash.
the important thing is that fuzzers don’t prove the non-existence of bugs, they just sniff out the ones they can find. but fuzzing uses computers for what they’re solid at: churning through god-forseen numbers of data and producing value that would otherwise be discovered by the people that use them. build a funny lil fuzzer! test the tools you use day-to-day
https://discord.gg/fpSMc9FGb
golang and rust have great language support for fuzzing as a first class testing setup, and you can get ok dx with fast-check for Typescript. It’s technically property testing, which uses the same principles but with less time running, so they’ll slowly maybe explore the space.
having good invariants you test for is important too to make the crashes recognizable and useful.
thx for listening lol interests: