Doesn’t explain how it finds bugs it’s just had the AI play Mario bros
How Antithesis finds bugs
31–40 of 56 posts
Re: How Antithesis finds bugs
#32Earlier 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…
While reading your comment, I kept having the vague feeling that your idea of "theoretically computable" (within the given memory bounds) will still leave some exponential time and/or space complexity, and so effectively will still be "practically not computable".
Your last paragraph then seemed to confirm that, i.e. there was no particular shortcut for this specific case that would make it any different from general Kolmogorov complexity.
In that sense, isn't your comment itself also "only a theoretical curiosity"? As we went to from "uncomputable", to "theoretically computable under the given constraints", to "practically uncomputable"?
While suffering from lack of rigor, I think a lot of times--probably even the majority of times outside purely cs-theoretical treatments--when we colloquially speak of "uncomputable", we are always talking about practical computers without an infinite touring tape, and so actually mean "practically uncomputable".
Because, yes, while everyone immediately understands that actual computers don't have infinite memory, at the same time everyone understands that "exponential time" is still "never" in practical terms.
Re: How Antithesis finds bugs
#33Earlier quoted context omitted.
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…
Case in point: Watch an actual Mario speed running world record video, and the human players there are jumping around a lot while running around flat sections with no obstacles.
As I understand, the jumping (at least in this case) does nothing to Mario's horizontal speed at all, so they basically just do it for "fun".
The difference is that the human players know that they're doing something inconsequential for variety, while the fuzzer has no "idea" (i.e. no concept) that the jumping does not matter, or even that it is "jumping". More generally, it does not know nor care that this particular part of the input is irrelevant. It just found an input that works, and sometimes that happens to include a useless jump.
Re: How Antithesis finds bugs
#34Earlier quoted context omitted.
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
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 asse…
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)
Re: How Antithesis finds bugs
#35Doesn’t explain how it finds bugs it’s just had the AI play Mario bros
I think everyone in the target audience of this blog post is immediately able to make the connection.
Re: How Antithesis finds bugs
#36Have 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.
Re: How Antithesis finds bugs
#37Earlier quoted context omitted.
> 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…
While reading your comment, I kept having the vague feeling that your idea of "theoretically computable" (within the given memory bounds) will still leave some exponential time and/or space complexity, and so effectively will still be "practically not computable". Your last paragraph then seemed to confirm that, i.e. there was no particular shortcut for this specific case that would make it any different from general…
I would somewhat agree with your comment, but I think you're missing some important points:
> everyone understands that "exponential time" is still "never" in practical terms.
It's important to note that this is not necessarily true:
1. "exponential time" is somewhat ambiguous. An algorithm might be exponential time yet have a very low exponential base (e.g. 1.0001), so in practical terms it might be practically computable for reasonable sizes.
2. Even if the exponential base is high, it still doesn't say anything about whether an algorithm can be used practically or not. The algorithm might still be very efficient for reasonable problem sizes even though it has a high exponential base (important question: exponential in terms of what, exactly?).
3. Exponential time algorithms might only be so in the worst case but might not necessarily be exponential in the average case, or even the vast majority of interesting cases. As an example, it might be easy (or at least doable) to solve the halting problem for normal computer programs. Humans do this all the time with real-world programs when performing formal verification (as these programming languages, logics and tools force you to prove that loops and recursive functions always terminate, even when assuming a model equivalent to a Turing machine), and AFAIK there's no proof that computers can't efficiently do the same for the vast majority of real-world programs (cryptographic algorithms being the usual exception).
4. Whenever someone mentions that the halting problem and Kolmogorov complexity are uncomputable, the discussion ends there. But notice that when I pointed out that it's in fact computable, the discussion turned into one about how efficient the computation might be (which I argue, is how all such discussions should be).
5. As a side note, every single time I argued this point in the past, usually in the context of the halting problem, someone always argued that such an algorithm would necessarily have a time complexity of 2^N, where N=nr. of bits of the machine. This is not true. It would only be true for the simplest and most naive solution to the halting problem, which is inevitably what that person has in mind. In fact, there's already a family of algorithms that solve the halting problem with less complexity for almost all programs: "Floyd's tortoise and hare" and similar ones (see [1]). Note that these algorithms don't even inspect the program, they just run it step by step. This leads me to think that there are undiscovered algorithms that are far more efficient by virtue of exploiting knowledge about the program being analyzed.
Re: How Antithesis finds bugs
#38Earlier 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…
What if you optimized inputs based on the strategy? E.g when you're in the air pressing down has no effect, or more measurably, the code paths between runs where you do or don't press down are very similar or completely converge. Similarly, jumping while running on a flat floor at full speed doesn't affect the game much, so prune it.
Maybe call it "strategy-informed tactics"
Re: How Antithesis finds bugs
#39Earlier 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…
Deterministic execution might be well understood by its proponents, but it's a completely niche technique that practically no one uses in practice. You have this jaded tone like this is something that everyone is doing, and everyone knows that this isn't true, so we're curious... why are you writing these things?
Re: How Antithesis finds bugs
#40Have 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]