Crushing Castlevania with Antithesis | Antithesis Bug Bash, the conference for quality-obsessed builders, is coming to Copenhagen this fall!See announcement

September 20, 2024 | David Edelstein , Senior Engineer<br>Crushing Castlevania with Antithesis

David Edelstein Senior Engineer

In this post

Snouty’s quest<br>Curse of squashedness<br>Dracula, X, Y, stage<br>Legacy of debugging

The latest from antithesis

The latest

Monthly reliability and distributed systems news, curated for teams<br>building critical software.

Please enable JavaScript in your browser to load and submit this form.

Thanks — you're subscribed.

Something went wrong. Please try again.

What’s the hardest part of the original NES Castlevania?

Death? Antithesis one-shots him.

Dracula? He was easy once we had a ROM-map to tell which phase he was in (byte $007A, by the way).

That stupid corridor with all the gorgon heads? Didn’t even register.

No, for us the hardest part is Stage 6’s stompers. Three alternating crushers a 5-year old could intuitively understand and probably get through.

There isn’t, as far as I can tell, any more widely accepted term for these objects, though I feel like there really should be.

Pathetically pancaked protagonists persistently produced

We spent an unbelievable amount of exploration time trying to find a way past the trio of stompers, but the same configuration that had blitzed through the first five stages was utterly stuck here. What could be going wrong? Read on to learn the answer, and for broader lessons on how to get good test coverage for any software system, even ones that aren’t about battling the undead.

This, by the way, is the third installment in a series of posts showing how Antithesis explores classic 8-bit NES games, each of which holds an extraordinarily complex state space. When Antithesis isn’t playing NES games, it’s helping developers track down hard-to-find bugs in distributed systems. (But if you just want to see it playing NES games, skip to near the end for a video of our full victorious playthrough of Castlevania.)

Snouty’s quest

A quick refresher on Castlevania:

Castlevania is a 1986 platformer for the Nintendo Entertainment System (NES), in which the player guides Simon Belmont, a whip-cracking vampire hunter who takes his fashion cues from Conan the Barbarian, through Dracula’s castle. The game is less open than Zelda, but more complex than Mario, and rivals those masterworks in influence.

So called because it is a Metroidvania game set in a Castle.

Specifically, Simon Belmont is re-vanquishing Dracula, who has returned after Simon Belmont’s ancestor, also Simon Belmont, killed him a century ago.

Besides the platforming, Castlevania features health and inventory management. We actually ended up ignoring these complications. The gameplay was better when it preserved every single point of health, and sensible use of pickups was unnecessary to victory.

And a quick refresher on Antithesis:

The heart of Antithesis is a deterministic hypervisor, which lets any program be run in a controllable, rewindable way so all bugs are reproducible. There’s also a guidance component that intelligently seeks out and explores system states that seem likely to lead to interesting behavior.

How does this work for Castlevania? In this case, we’re searching that vast space for an exceedingly rare yet possible state of the system: “You win!”. Just like for Zelda, we can make use of SOMETIMES_EACH assertions to explore Castlevania. Here, we’re interested in traversing all the stages of the game, so our guiding assertion will be SOMETIMES_EACH({SimonX/32, SimonY/32, stageID}). In effect, we’re bucketing the game’s map into a 32-pixel square grid and turning the platform loose to discover it all.

As a reminder, SOMETIMES_EACH takes a set of parameters that assume possibly-unknown values and directs our system to focus particularly on less-explored values of those parameters. We can explore any slice of the values Castlevania’s memory can assume with the appropriate set of parameters.

But as we explore the game, we will likely find a tremendous number of system states that all get lumped together into a single bucket, so many that it’s impractical to save them all. This is analogous to how a traditional, coverage-guided fuzzer may find many input sequences that lead to a particular line of code running, but can’t save all of them in its corpus. When Antithesis encounters the same assertion many times, it will score the various states that hit that assertion and then only use a few of them as a basis for future exploration.

You can let Antithesis decide what makes a particular input “good”, or you can override it. For our work on Castlevania we optimized for time remaining (each level has a countdown clock) and Belmont being at full health.

Our SOMETIMES_EACH assertion guides Antithesis by providing a system state to start from, choosing an exemplar from an underexplored bucket to ensure that our...