Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How Antithesis finds bugs

antithesis.com

Post reply on HN
Print view View original

21–30 of 56 posts

Re: How Antithesis finds bugs

#21

Post by mrkmarron »

wwilson wrote: post #16
mrkmarron wrote: post #12

Earlier quoted context omitted.

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 mak…

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/ As for getting to the newer stuff, yeah, totally, just give us some time. There's a bit of a backlo…

I just rewatched the end of the video to make sure I didn't miss anything. Deterministic execution and replay is very-very well-known and understood. It is possible that your packaging and market fit is right on. Lots of cottage industry in DB testing and bug finding -- but not clear how this generalizes and why something like Coyote [1] (to pick one) wouldn't work as well.

So, fuzzing has been applied to very stateful and very large industrial systems for some time. And yes it is very cool but I feel like I am seeing more "sizzle than steak" so to speak. Great engineering though, hypervisor work is very challenging.

[1] https://www.microsoft.com/en-us/research/blog/coyote-making-...

Re: How Antithesis finds bugs

#22

Post by wwilson »

mrkmarron wrote: post #21
wwilson wrote: post #16

Earlier quoted context omitted.

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/ As for getting to the newer stuff, yeah, totally, just give us some time. There's a bit of a backlo…

I just rewatched the end of the video to make sure I didn't miss anything. Deterministic execution and replay is very-very well-known and understood. It is possible that your packaging and market fit is right on. Lots of cottage industry in DB testing and bug finding -- but not clear how this generalizes and why something like Coyote [1] (to pick one) wouldn't work as well. So, fuzzing has been applied to very statef…

It is absolutely possible to write a large stateful system from the ground up so that autonomous testing techniques can be applied to it. FoundationDB and Tiger Beetle are both examples of this, I think Resonate might be another one, and Toby Bell's talk at Strange Loop last year is a great guide on how to do so.

What's much harder is to take an arbitrary system, written in an arbitrary way, without these techniques in mind, and make it amenable to this sort of testing. From the start of our company, we believed that unless this was possible, the market would be too hard to crack, because most human beings are not very foresightful and not able to justify a bunch of extra work.

Hypervisor-based snapshot fuzzing like Nyx-Net and deterministic userspaces like Facebook's now-discontinued Hermit project are the other ways I know of accomplishing that goal. We believe that both of them have some pretty serious practical limitations which our approach does not share.

EDIT: Maybe the way to get to the crux of the disagreement is for me to turn the question around. Why do you believe that the vast majority of stateful and concurrent systems are not tested with fuzzing?

Re: How Antithesis finds bugs

#23

Post by bbor »

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.

Re: How Antithesis finds bugs

#24

Post by wwilson »

infogulch wrote: post #18
mrkmarron wrote: post #7

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_IJ...

Have any of these methods found clips and speedrunning shortcuts? Examples: Clip the base of the flagpole to skip some animation time. Clip into and walk below the floor to run past obstacles. Etc.

We find a ton of glitches in Mario, and even more in other games. See, e.g.: https://vimeo.com/807601164

Re: How Antithesis finds bugs

#25

Post by wwilson »

wwilson wrote: post #24
infogulch wrote: post #18

Earlier quoted context omitted.

Have any of these methods found clips and speedrunning shortcuts? Examples: Clip the base of the flagpole to skip some animation time. Clip into and walk below the floor to run past obstacles. Etc.

We find a ton of glitches in Mario, and even more in other games. See, e.g.: https://vimeo.com/807601164

Hmm... looks like Vimeo is currently having some kind of outage. If anybody at Vimeo is reading this and wants some help with testing backend systems, email is in bio.

Re: How Antithesis finds bugs

#26

Post by someplaceguy »

wwilson wrote: post #10
cperciva wrote: post #9

Earlier quoted context omitted.

Why is Mario so jumpy?

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, y…

> 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).

Re: How Antithesis finds bugs

#27

Post by vojev »

yanniszark wrote: post #19

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?

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.)

Re: How Antithesis finds bugs

#28

Post by mrkmarron »

wwilson wrote: post #22
mrkmarron wrote: post #21

Earlier quoted context omitted.

I just rewatched the end of the video to make sure I didn't miss anything. Deterministic execution and replay is very-very well-known and understood. It is possible that your packaging and market fit is right on. Lots of cottage industry in DB testing and bug finding -- but not clear how this generalizes and why something like Coyote [1] (to pick one) wouldn't work as well. So, fuzzing has been applied to very statef…

It is absolutely possible to write a large stateful system from the ground up so that autonomous testing techniques can be applied to it. FoundationDB and Tiger Beetle are both examples of this, I think Resonate might be another one, and Toby Bell's talk at Strange Loop last year is a great guide on how to do so. What's much harder is to take an arbitrary system, written in an arbitrary way, without these techniques…

At the end of the day you have 2 problems (1) how to make execution deterministic within some boundary be it a process, hypervisor, or distributed system and (2) how you handle non-determinism when data crosses this boundary. You can move the boundaries and effort around but the problems always exist. So, if you are claiming that you have a sweet spot on this tradeoff then I could certainly believe that, if you claim that you eliminated this boundary issue then I am highly credulous.

I'll agree with you on indeterminate behaviors though, I suspect they will eventually be seen like the "billion dollar" mistake of null pointers.

Re: How Antithesis finds bugs

#29

Post by wwilson »

someplaceguy wrote: post #26
wwilson wrote: post #10

Earlier quoted context omitted.

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, y…

> 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 alte…

Thank you. Comments like this are why I love HN.

Re: How Antithesis finds bugs

#30

Post by mrkmarron »

wwilson wrote: post #22
mrkmarron wrote: post #21

Earlier quoted context omitted.

I just rewatched the end of the video to make sure I didn't miss anything. Deterministic execution and replay is very-very well-known and understood. It is possible that your packaging and market fit is right on. Lots of cottage industry in DB testing and bug finding -- but not clear how this generalizes and why something like Coyote [1] (to pick one) wouldn't work as well. So, fuzzing has been applied to very statef…

It is absolutely possible to write a large stateful system from the ground up so that autonomous testing techniques can be applied to it. FoundationDB and Tiger Beetle are both examples of this, I think Resonate might be another one, and Toby Bell's talk at Strange Loop last year is a great guide on how to do so. What's much harder is to take an arbitrary system, written in an arbitrary way, without these techniques…

Just saw the edit. I have 2 answers:

1) Fuzzing is under-utilized even for simple code. AFL is dead easy to use and, even so, most projects don't have it in CI runs. So, despite how much I like it, in general it seems people do not see value in this type of testing.

2) The effort to handle external state (say a restful call to get stock ticker info) needs to be mocked -- which is deeply unpopular -- or handled by record/replay which works ok-ish but eventually breaks down with divergences. Outside of well-chosen domains it these eventually pop-up and add an additional pain point that builds on item 1.

Post reply on HN