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

11–20 of 56 posts

Re: How Antithesis finds bugs

#11

Post by gwern »

cperciva wrote: post #9
wwilson wrote: post #3

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.

Why is Mario so jumpy?

Most RL agents are 'jumpy' or jitter a lot, because it makes no difference to the reward, and where it does make a difference, that tends to only matter close to convergence where slight speedups are all that's left. If you want to reduce that, you have to reward-shape it to penalize excess movement. (Which is relevant in robotics, where 'jitter' can be very bad for the machinery in a way not reflected in the simple tasks' reward functions.)

Re: How Antithesis finds bugs

#12

Post by mrkmarron »

wwilson wrote: post #8
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...

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.

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.

Re: How Antithesis finds bugs

#13

Post by chc4 »

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

A lot of fuzzers use Mario or other simple games as an internal testcase. I'm aware of a hypervisor fuzzer from 2016 that did it, and I'm positive there are others (both before and since). Hell, tom7 has a fuzzer for exploring program states that uses Super Mario Bros as the example from 2013 (https://www.cs.cmu.edu/~tom7/mario/mario.pdf, plus a youtube video https://youtu.be/xOCurBYI_gY), and he's definitely not the first either.

Re: How Antithesis finds bugs

#14

Post by mrkmarron »

chc4 wrote: post #13
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...

A lot of fuzzers use Mario or other simple games as an internal testcase. I'm aware of a hypervisor fuzzer from 2016 that did it, and I'm positive there are others (both before and since). Hell, tom7 has a fuzzer for exploring program states that uses Super Mario Bros as the example from 2013 ( https://www.cs.cmu.edu/~tom7/mario/mario.pdf , plus a youtube video https://youtu.be/xOCurBYI_gY ), and he's definitely not…

Thanks for sharing, I felt like there were earlier but the x,y trick jumped out at me and that was the one I remembered off the top of my head.

Re: How Antithesis finds bugs

#15

Post by wwilson »

chc4 wrote: post #13
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...

A lot of fuzzers use Mario or other simple games as an internal testcase. I'm aware of a hypervisor fuzzer from 2016 that did it, and I'm positive there are others (both before and since). Hell, tom7 has a fuzzer for exploring program states that uses Super Mario Bros as the example from 2013 ( https://www.cs.cmu.edu/~tom7/mario/mario.pdf , plus a youtube video https://youtu.be/xOCurBYI_gY ), and he's definitely not…

We are huge fans of tom7 and that paper was one of our inspirations for using NES as a domain for researching autonomous state space search! I think he does a very good job of explaining why the problem is hard.

Re: How Antithesis finds bugs

#16

Post by wwilson »

mrkmarron wrote: post #12
wwilson wrote: post #8

Earlier quoted context omitted.

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.

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

Re: How Antithesis finds bugs

#17

Post by chc4 »

wwilson wrote: post #15
chc4 wrote: post #13

Earlier quoted context omitted.

A lot of fuzzers use Mario or other simple games as an internal testcase. I'm aware of a hypervisor fuzzer from 2016 that did it, and I'm positive there are others (both before and since). Hell, tom7 has a fuzzer for exploring program states that uses Super Mario Bros as the example from 2013 ( https://www.cs.cmu.edu/~tom7/mario/mario.pdf , plus a youtube video https://youtu.be/xOCurBYI_gY ), and he's definitely not…

We are huge fans of tom7 and that paper was one of our inspirations for using NES as a domain for researching autonomous state space search! I think he does a very good job of explaining why the problem is hard.

Right, in case it wasn't clear to readers this isn't a bad thing. Lots of people use games because they're good analogs for other programs and evocatively show fuzzing exploration progress. Not being the first to point a fuzzer at Mario doesn't matter.

Re: How Antithesis finds bugs

#18

Post by infogulch »

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.

Re: How Antithesis finds bugs

#19

Post by yanniszark »

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?

Re: How Antithesis finds bugs

#20

Post by mustknow2201 »

wwilson wrote: post #3

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.

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?
Post reply on HN