41–50 of 56 posts
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.
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.
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
[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
[2]: I introduce the concept of fuzzing in another comment: https://news.ycombinator.com/item?id=40068187#40071972
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.
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?
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?
Fuzzing is a moderately advanced software testing technique popularized in the '90s that operates on a very simple idea: If you feed a program's inputs with arbitrary/random data, this could be used to discover bugs in the program with little human effort.
In the 90s they fed random data into the stdin of unix utilities and found that many programs crashed. [0] In this context printing an error message that says "I can't interpret the input" is a valid state, but reading past the end of a buffer because the input confused the program is a bug. Variants can be designed to test any API layer.
More recently Coverage Guided Fuzzers use information about which code paths are executed for each input as a way to reach a variety of program states more quickly. Also, starting with a prefix known to produce an interesting state can also speed up testing.
I wrote a comment relating this to the article and talk in the OP here: https://news.ycombinator.com/item?id=40068187#40071950
Earlier quoted context omitted.
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 comp…
In your original reply, you started with (transcribing) "Kolmogorov complexity is not technically uncomputable in the practical case of not having an infinite tape", which gave me hope that we would start talking about how there are some reasonable shortcuts in this particular case (as you mention in this answer now).
But then you ended with (literally) "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)", which squashed my hopes, seemed to just have replaced "theoretically uncomputable" with "practically uncomputable", and made me wonder how it changed anything that OP already wrote in practical terms, namely: "Unfortunately, that's uncomputable"
But now it seems we're back to (potentially) discussing how in this particular use case there might be tractable ways to (limited, but useful) computability, which is good again!
Earlier quoted context omitted.
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 comp…
Oh but that was specifically what I was trying to get at, i.e. point #4 of this reply of yours: Are there any shortcuts that make this reasonably computable or not? In your original reply, you started with (transcribing) "Kolmogorov complexity is not technically uncomputable in the practical case of not having an infinite tape", which gave me hope that we would start talking about how there are some reasonable shortc…
I tend to think that an efficient computation of some finite-state version of Kolmogorov complexity would necessarily require an efficient computation of a finite-state version of the halting problem, but I'm not entirely sure of this.
Naively, it seems that this Kolmogorov calculation would require enumerating all programs (in increasing program size) and then running each of them until they either 1) enter an infinite loop, 2) produce the input string and halt, or 3) start producing a different string.
However, I'm not sure this would be the most efficient algorithm. For example, it might be easy to inspect each program and discard almost all that would "obviously" not produce the input string before we even try to run them.
Or better yet, never even enumerate such programs that can be proven not to produce the input string. In other words, cut the search space significantly.
Perhaps there might even be a shortcut to directly construct the smallest program that produces a given string, or at least, a family of small candidate programs that would be a very small subset of all possible programs and yet would be guaranteed to contain the solution.
As you might have noticed, unfortunately I don't know if there are such extraordinarily efficient shortcuts, I'm only speculating that they might exist.
That said, I still suspect that this might be intractable due to having to account for the worst case, i.e. undecipherable random-looking programs. In the case of the halting problem in the context of formal verification, I'm more optimistic since we usually don't need to care about such random-looking programs, only human-constructed ones (usually), which might be far easier to analyze algorithmically. I don't know if that makes sense...
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…
This reminds me a lot of the problem space involving Perlin Noise. I'd hypothesize that by using a fractal noise pattern you can generate inputs with correlated values yet still remain random enough to get to any state. Have you tried using noise generators for random inputs?
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.