6 ms·

How Antithesis finds bugs

160 points by wwilson 2y ago

Olesya000 2y ago
[dead]
wwilson 2y ago
This is Will (I gave the talk linked in the post). Happy to answer any questions about this work, or how it generalizes to testing things that aren't Nintendo games.
- thsksbd 2y ago
  How does this distinguish between a bug and a "feature"? Edit: i mean this is the spirit of Knuth's quip that when he dies all the bugs in tex will become features
  - wwilson 2y ago
    There was a LOT of discussion of this in the Q&A after the talk. Currently we have 4 main approaches: (1) There's some stuff that's pretty much a bug for every program. If it segfaults, exits with a nonzero code, OOMs, triggers a TSAN error, fills the disk with fatal error messages, etc., etc., that's pretty easy to qualify. (2) You can use our SDK to define additional custom test properties. Think like a normal assertions library, but you can also do existential quantification ("this code is reachable/this situation can happen") and soon temporal assertions ("this should never happen without this other thing happening first, possibly on a different node"). (3) We store all the output of your system in every timeline in a giant analytic database and support ad-hoc querying against it. Think "pre-observability", observability but for mirror universes. You can then do all the spelunking and analysis you would do with your production traces, but before your real customers are exposed to any issue. (4) We have some very cool ML approaches in the pipeline that I can't talk about quite yet.
    - ajb 2y ago
      Can you define equivalence classes (mutations that shouldn't change the result) eg timing, order of events, idempotence, etc? So that you can use (3) to define the correct result for all members of the class (Sorry if this is explained in the talk - I'll watch it but it's now too late in the day in my timezone)
- cperciva 2y ago
  Why is Mario so jumpy?
  - wwilson 2y ago
    This is actually an incredibly deep and difficult question to answer. I would expect no less from cperciva. :-) As I mention in the talk, you get very bad tactical performance from taking a uniform random distribution and piping it into the emulator. The fuzzer is exponentially unlikely to hold the jump button for many successive frames without a break. In the fully general case, I think instead of maximum entropy, you want something more like Marcus Hutter's AIXI where you spend energy on inputs inversely proportional to their Kolmogorov complexity. Unfortunately, that's uncomputable, but it turns out that just switching to toggling bits with low probability does a lot better than pure randomness. The approach is analogous to swarm testing (https://users.cs.utah.edu/~regehr/papers/swarm12.pdf https://users.cs.utah.edu/~regehr/papers/swarm12.pdf). All of which is to say, the result that we show here is vastly less jumpy than our first tries. The reason it's still more jumpy than a human player is that our platform has no idea where it is in the game, or even that it's playing a game. So if a jump doesn't harm it in the exploration process, there's some chance the first input getting somewhere new will involve a jump, and that will then get locked in. We do have the capability to do optimization on inputs (what conventional PBT calls "shrinking"), and indeed if you apply this to Mario you can get it to jump a lot less and complete levels a lot faster. That capability didn't exist yet when this video was recorded. We should totally do a another post on this topic!
    - someplaceguy 2y ago
      > Unfortunately, that's uncomputable Minor nitpick, but while Kolmogorov complexity as typically defined is uncomputable, I would argue that this result is only a theoretical curiosity and mostly irrelevant. That is, the "uncomputable" Kolmogorov complexity computation presupposes that you have a Turing machine, i.e. a machine with literally infinite memory, which is not possible to construct in our universe. Or alternatively, it presupposes that "computable function" is one that can be computed by a machine with an infinite amount of storage, which amounts to the same thing as having a Turing machine. You could probably define some version of Kolmogorov complexity that is parametrized by the memory size (e.g. of a linear bounded automaton or similar model that better represents a computer with finite resources), which should make it computable. That said, in practice it would probably take an unreasonable amount of time to perform this computation (but that is orthogonal to whether it's computable or not).
- mustknow2201 2y ago
  How close is or isn't this to a genetic algorithm in practice? It seems like as soon as you start scaling out to multiple threads/nodes you'd benefit from crossover, selection techniques and so on?
- iamcreasy 2y ago
  Very cool presentation. Thanks for doing this. Choosing next input based on present sounds a lot like a Markov chain - is that something you guys use when simulating user interaction with distributed system?
Taikonerd 2y ago
Super Mario is such a fun example. Well chosen.
mrkmarron 2y ago
FYI playing Super Mario with fuzzing (AFL) was done in a fun 2020 S&P paper. Also finds bugs and security issues. "IJON: Exploring Deep State Spaces via Fuzzing" https://casa.rub.de/fileadmin/img/Publikationen_PDFs/2020_IJON_Exploring_Deep_State_Spaces_via_Fuzzing_Publication_ClusterofExcellence_CASA_Bochum.pdf https://casa.rub.de/fileadmin/img/Publikationen_PDFs/2020_IJ...
- wwilson 2y ago
  Thanks for flagging this! The work we're announcing today was completed in 2018, and we have since moved on to much more challenging problems both in the Nintendo domain and elsewhere. Totally not looking to pick a fight over priority though. This is such a hilariously understudied and under-explored area, we really value anybody else who's trying to work on these problems.
  - mrkmarron 2y ago
    I think you underestimate the level to which this area has been studied. And I wish you would talk about these new results then instead of announcing 5+ year old results then. It would be great to see progress in this area (not my primary area of work BTW) but I am not seeing anything here, technically, that is going to make that happen -- maybe it is just getting all the parts in place and magic happens. It just makes me scratch my head a bit.
    - wwilson 2y ago
      It's possible you did not make it to the end of the talk where I explain this, but the thing that excites me is that we can now apply fuzzing and related techniques to things which are neither Nintendo games nor tiny stateless libraries and parsers, because of this: https://antithesis.com/blog/deterministic_hypervisor/ https://antithesis.com/blog/deterministic_hypervisor/ As for getting to the newer stuff, yeah, totally, just give us some time. There's a bit of a backlog. :-)
      - mrkmarron 2y ago
yanniszark 2y ago
This is fascinating! I thought only Reinforcement Learning was doing things like this but you're saying you can do this via fuzzying? What does this mean exactly? How is it able to learn to advance through all these levels? Is there an underlying learning mechanism at play?
- vojev 2y ago
  There's no learning exactly, as the post explains the fuzzer is aware of various RAM addresses (as well as having a tactic for how it "presses" buttons in the game). It's just trying to explore the space of Mario's level + his x and y coordinates. (I'm an Antithesis employee.)
  - nextaccountic 2y ago
    This means that, without a learning procedure to direct Mario towards the end of the level, it can only reach the end by itself because the levels (and Mario's in-memory data structures in general) are pretty small, right? Or rather, if there were tons of irrelevant state, it could always end up trapped somewhere and never actually complete a level even after centuries of fuzzing. Something similar was tested in the Twitch Plays Pokemon [0] gaming experiment, but there the inputs appeared random but weren't actually random: there were "factions" that either tried to sabotage the run, or that tried to make it progress. Ultimately the majority of the players were cooperating to complete the game and this was a deciding factor to make the run succeed. Maybe fuzzing Pokemon can't complete the game, the way that TPP could (or reinforcement learning could). [0] https://en.wikipedia.org/wiki/Twitch_Plays_Pok%C3%A9mon https://en.wikipedia.org/wiki/Twitch_Plays_Pok%C3%A9mon
    - vojev 2y ago
      The space is large, it just turns out if you direct Mario to explore with a bit of bias (so, in general, there's some favoring of exploring from states where Mario's x coordinate is to the right, e.g.) it completes the levels. I think Pokemon could be beaten with our techniques. Final Fantasy on NES poses similar problems to Pokemon, and that is a game at which some progress has been made in the past, here.
bbor 2y ago
At what point can we start suing companies on behalf of the commons for taking words from the lexicon? I miss the days when this would be called “Wilson & Co.’s automated testing solution” instead of such a beautiful, philosophically meaningful word. Same thoughts on that Devin.AI scam taking the name “Cognition” and Vercel somehow bribing their way into claiming the “ai” name on NPM. Technically awesome post tho! Love the heatmap esp. Maybe bring up changing your name to investors because some rando online doesn’t like it though, please.
m3kw9 2y ago
Doesn’t explain how it finds bugs it’s just had the AI play Mario bros
- anyfoo 2y ago
  I think everyone in the target audience of this blog post is immediately able to make the connection.
  - m3kw9 2y ago
    The big question is how does it find bugs without knowing if it is intended behaviour or not?
infogulch 2y ago
Have you tried to 'rediscover' classic (in)famous bugs? E.g. take an old version of OpenSSL vulnerable to heartbleed and run Antethesis on it to 'discover' heartbleed via fuzzing. It would be interesting to see how much fine tuning would be needed to discover it.
- deleted 2y ago
  [deleted]
- nlavezzo 2y ago
  This is a cool idea. I’ll ask the team about it. Would make for a very interesting blog post or talk!
- klysm 2y ago
  Excellent idea and it would be a great way to pitch it. What about collaborations with Jepsen?
- eichin 2y ago
  Heh, yeah, "being able to predict the present" is an important benchmarking technique
infogulch 2y ago
In Will's talk he defines two terms related to optimizing fuzzers [2]: Strategy and Tactics. Strategy is the datum you choose to optimize for as the fuzzer randomly walks the states of the system. E.g. optimize to maximize Mario's X value, or optimize for reaching all tile positions etc. This generalizes the concept of "coverage guided" to include domain-specific details about your target program (e.g. that the program has the concept of a grid of possible positions). Tactics is the choice of input distribution. Sometimes the frequency of the randomness should be tuned for the application. For example, randomly changing the state of the A button every frame is not a good frequency to properly test long jumps, maybe a normal distribution with average hold/not hold time of 1s would be better. Also, encoding the randomness within the program's valid domain can help avoid over-testing parsing/validation code at the expense of more interesting code further in the program. [1][2] [0]: Barton P. Miller, Lars Fredriksen, and Bryan So. 1990. An empirical study of the reliability of UNIX utilities. Commun. ACM 33, 12 (Dec. 1990), 32–44. https://doi.org/10.1145/96267.96279 https://doi.org/10.1145/96267.96279 [1]: This reference appears to be related: Rohan Padhye, Caroline Lemieux, Koushik Sen, Laurent Simon, and Hayawardh Vijayakumar. 2019. FuzzFactory: domain-specific fuzzing with waypoints. Proc. ACM Program. Lang. 3, OOPSLA, Article 174 (October 2019), 29 pages. https://doi.org/10.1145/3360600 https://doi.org/10.1145/3360600 [2]: I introduce the concept of fuzzing in another comment: https://news.ycombinator.com/item?id=40068187#40071972 https://news.ycombinator.com/item?id=40068187#40071972
t4ng0pwn3d 2y ago
I see a lot of fuzzing tools for CLI apps, but are there any good alternatives for web applications/APIs? I've used Hypothesis for generating random datas in requests but maybe there's something better out there.
suprfnk 2y ago
@wwilson How do you define the X/Y "distance" of a non-Mario application? I.e. any (distributed or not) system that doesn't have a relatively trivial "higher x/y is better" fitness function?
m3kw9 2y ago
If you just read it it sounds like a scam to some. Going thru all states does not find you bugs magically. You need to know what a bug is first or if it’s an actual intended feature. This article fails to explain it

160 points by wwilson 2y ago

[dead]

This is Will (I gave the talk linked in the post). Happy to answer any questions about this work, or how it generalizes to testing things that aren't Nintendo games.

thsksbd 2y ago
How does this distinguish between a bug and a "feature"? Edit: i mean this is the spirit of Knuth's quip that when he dies all the bugs in tex will become features
- wwilson 2y ago
  There was a LOT of discussion of this in the Q&A after the talk. Currently we have 4 main approaches: (1) There's some stuff that's pretty much a bug for every program. If it segfaults, exits with a nonzero code, OOMs, triggers a TSAN error, fills the disk with fatal error messages, etc., etc., that's pretty easy to qualify. (2) You can use our SDK to define additional custom test properties. Think like a normal assertions library, but you can also do existential quantification ("this code is reachable/this situation can happen") and soon temporal assertions ("this should never happen without this other thing happening first, possibly on a different node"). (3) We store all the output of your system in every timeline in a giant analytic database and support ad-hoc querying against it. Think "pre-observability", observability but for mirror universes. You can then do all the spelunking and analysis you would do with your production traces, but before your real customers are exposed to any issue. (4) We have some very cool ML approaches in the pipeline that I can't talk about quite yet.
  - ajb 2y ago
    Can you define equivalence classes (mutations that shouldn't change the result) eg timing, order of events, idempotence, etc? So that you can use (3) to define the correct result for all members of the class (Sorry if this is explained in the talk - I'll watch it but it's now too late in the day in my timezone)
cperciva 2y ago
Why is Mario so jumpy?
- wwilson 2y ago
  This is actually an incredibly deep and difficult question to answer. I would expect no less from cperciva. :-) As I mention in the talk, you get very bad tactical performance from taking a uniform random distribution and piping it into the emulator. The fuzzer is exponentially unlikely to hold the jump button for many successive frames without a break. In the fully general case, I think instead of maximum entropy, you want something more like Marcus Hutter's AIXI where you spend energy on inputs inversely proportional to their Kolmogorov complexity. Unfortunately, that's uncomputable, but it turns out that just switching to toggling bits with low probability does a lot better than pure randomness. The approach is analogous to swarm testing (https://users.cs.utah.edu/~regehr/papers/swarm12.pdf https://users.cs.utah.edu/~regehr/papers/swarm12.pdf). All of which is to say, the result that we show here is vastly less jumpy than our first tries. The reason it's still more jumpy than a human player is that our platform has no idea where it is in the game, or even that it's playing a game. So if a jump doesn't harm it in the exploration process, there's some chance the first input getting somewhere new will involve a jump, and that will then get locked in. We do have the capability to do optimization on inputs (what conventional PBT calls "shrinking"), and indeed if you apply this to Mario you can get it to jump a lot less and complete levels a lot faster. That capability didn't exist yet when this video was recorded. We should totally do a another post on this topic!
  - someplaceguy 2y ago
    > Unfortunately, that's uncomputable Minor nitpick, but while Kolmogorov complexity as typically defined is uncomputable, I would argue that this result is only a theoretical curiosity and mostly irrelevant. That is, the "uncomputable" Kolmogorov complexity computation presupposes that you have a Turing machine, i.e. a machine with literally infinite memory, which is not possible to construct in our universe. Or alternatively, it presupposes that "computable function" is one that can be computed by a machine with an infinite amount of storage, which amounts to the same thing as having a Turing machine. You could probably define some version of Kolmogorov complexity that is parametrized by the memory size (e.g. of a linear bounded automaton or similar model that better represents a computer with finite resources), which should make it computable. That said, in practice it would probably take an unreasonable amount of time to perform this computation (but that is orthogonal to whether it's computable or not).
mustknow2201 2y ago
How close is or isn't this to a genetic algorithm in practice? It seems like as soon as you start scaling out to multiple threads/nodes you'd benefit from crossover, selection techniques and so on?
iamcreasy 2y ago
Very cool presentation. Thanks for doing this. Choosing next input based on present sounds a lot like a Markov chain - is that something you guys use when simulating user interaction with distributed system?

Taikonerd 2y ago

Super Mario is such a fun example. Well chosen.

mrkmarron 2y ago

FYI playing Super Mario with fuzzing (AFL) was done in a fun 2020 S&P paper. Also finds bugs and security issues. "IJON: Exploring Deep State Spaces via Fuzzing" https://casa.rub.de/fileadmin/img/Publikationen_PDFs/2020_IJON_Exploring_Deep_State_Spaces_via_Fuzzing_Publication_ClusterofExcellence_CASA_Bochum.pdf https://casa.rub.de/fileadmin/img/Publikationen_PDFs/2020_IJ...

wwilson 2y ago
Thanks for flagging this! The work we're announcing today was completed in 2018, and we have since moved on to much more challenging problems both in the Nintendo domain and elsewhere. Totally not looking to pick a fight over priority though. This is such a hilariously understudied and under-explored area, we really value anybody else who's trying to work on these problems.
- mrkmarron 2y ago
  I think you underestimate the level to which this area has been studied. And I wish you would talk about these new results then instead of announcing 5+ year old results then. It would be great to see progress in this area (not my primary area of work BTW) but I am not seeing anything here, technically, that is going to make that happen -- maybe it is just getting all the parts in place and magic happens. It just makes me scratch my head a bit.
  - wwilson 2y ago
    It's possible you did not make it to the end of the talk where I explain this, but the thing that excites me is that we can now apply fuzzing and related techniques to things which are neither Nintendo games nor tiny stateless libraries and parsers, because of this: https://antithesis.com/blog/deterministic_hypervisor/ https://antithesis.com/blog/deterministic_hypervisor/ As for getting to the newer stuff, yeah, totally, just give us some time. There's a bit of a backlog. :-)
    - mrkmarron 2y ago

yanniszark 2y ago

This is fascinating! I thought only Reinforcement Learning was doing things like this but you're saying you can do this via fuzzying? What does this mean exactly? How is it able to learn to advance through all these levels? Is there an underlying learning mechanism at play?

vojev 2y ago
There's no learning exactly, as the post explains the fuzzer is aware of various RAM addresses (as well as having a tactic for how it "presses" buttons in the game). It's just trying to explore the space of Mario's level + his x and y coordinates. (I'm an Antithesis employee.)
- nextaccountic 2y ago
  This means that, without a learning procedure to direct Mario towards the end of the level, it can only reach the end by itself because the levels (and Mario's in-memory data structures in general) are pretty small, right? Or rather, if there were tons of irrelevant state, it could always end up trapped somewhere and never actually complete a level even after centuries of fuzzing. Something similar was tested in the Twitch Plays Pokemon [0] gaming experiment, but there the inputs appeared random but weren't actually random: there were "factions" that either tried to sabotage the run, or that tried to make it progress. Ultimately the majority of the players were cooperating to complete the game and this was a deciding factor to make the run succeed. Maybe fuzzing Pokemon can't complete the game, the way that TPP could (or reinforcement learning could). [0] https://en.wikipedia.org/wiki/Twitch_Plays_Pok%C3%A9mon https://en.wikipedia.org/wiki/Twitch_Plays_Pok%C3%A9mon
  - vojev 2y ago
    The space is large, it just turns out if you direct Mario to explore with a bit of bias (so, in general, there's some favoring of exploring from states where Mario's x coordinate is to the right, e.g.) it completes the levels. I think Pokemon could be beaten with our techniques. Final Fantasy on NES poses similar problems to Pokemon, and that is a game at which some progress has been made in the past, here.

bbor 2y ago

At what point can we start suing companies on behalf of the commons for taking words from the lexicon? I miss the days when this would be called “Wilson & Co.’s automated testing solution” instead of such a beautiful, philosophically meaningful word. Same thoughts on that Devin.AI scam taking the name “Cognition” and Vercel somehow bribing their way into claiming the “ai” name on NPM. Technically awesome post tho! Love the heatmap esp. Maybe bring up changing your name to investors because some rando online doesn’t like it though, please.

m3kw9 2y ago

Doesn’t explain how it finds bugs it’s just had the AI play Mario bros

anyfoo 2y ago
I think everyone in the target audience of this blog post is immediately able to make the connection.
- m3kw9 2y ago
  The big question is how does it find bugs without knowing if it is intended behaviour or not?

infogulch 2y ago

Have you tried to 'rediscover' classic (in)famous bugs? E.g. take an old version of OpenSSL vulnerable to heartbleed and run Antethesis on it to 'discover' heartbleed via fuzzing. It would be interesting to see how much fine tuning would be needed to discover it.

deleted 2y ago
[deleted]
nlavezzo 2y ago
This is a cool idea. I’ll ask the team about it. Would make for a very interesting blog post or talk!
klysm 2y ago
Excellent idea and it would be a great way to pitch it. What about collaborations with Jepsen?
eichin 2y ago
Heh, yeah, "being able to predict the present" is an important benchmarking technique

infogulch 2y ago

In Will's talk he defines two terms related to optimizing fuzzers [2]: Strategy and Tactics. Strategy is the datum you choose to optimize for as the fuzzer randomly walks the states of the system. E.g. optimize to maximize Mario's X value, or optimize for reaching all tile positions etc. This generalizes the concept of "coverage guided" to include domain-specific details about your target program (e.g. that the program has the concept of a grid of possible positions). Tactics is the choice of input distribution. Sometimes the frequency of the randomness should be tuned for the application. For example, randomly changing the state of the A button every frame is not a good frequency to properly test long jumps, maybe a normal distribution with average hold/not hold time of 1s would be better. Also, encoding the randomness within the program's valid domain can help avoid over-testing parsing/validation code at the expense of more interesting code further in the program. [1][2] [0]: Barton P. Miller, Lars Fredriksen, and Bryan So. 1990. An empirical study of the reliability of UNIX utilities. Commun. ACM 33, 12 (Dec. 1990), 32–44. https://doi.org/10.1145/96267.96279 https://doi.org/10.1145/96267.96279 [1]: This reference appears to be related: Rohan Padhye, Caroline Lemieux, Koushik Sen, Laurent Simon, and Hayawardh Vijayakumar. 2019. FuzzFactory: domain-specific fuzzing with waypoints. Proc. ACM Program. Lang. 3, OOPSLA, Article 174 (October 2019), 29 pages. https://doi.org/10.1145/3360600 https://doi.org/10.1145/3360600 [2]: I introduce the concept of fuzzing in another comment: https://news.ycombinator.com/item?id=40068187#40071972 https://news.ycombinator.com/item?id=40068187#40071972

t4ng0pwn3d 2y ago

I see a lot of fuzzing tools for CLI apps, but are there any good alternatives for web applications/APIs? I've used Hypothesis for generating random datas in requests but maybe there's something better out there.

suprfnk 2y ago

@wwilson How do you define the X/Y "distance" of a non-Mario application? I.e. any (distributed or not) system that doesn't have a relatively trivial "higher x/y is better" fitness function?

m3kw9 2y ago

If you just read it it sounds like a scam to some. Going thru all states does not find you bugs magically. You need to know what a bug is first or if it’s an actual intended feature. This article fails to explain it