Thread by @mboehme_

For my new followers, my research group is interested in techniques that make machines attack other machines with maximal efficiency. All our tools are open-source, so people can use them to identify security bugs before they are exploited.

This is how it all started.

My first technical paper introduced a technique that could, in principle, *prove* that no bug was introduced by a new code commit [ICSE'13]. This was also the first of several symbolic execution-based whitebox fuzzers [FSE'13, ASE'16, ICSE'20].

mboehme.github.io/paper/ICSE13.p…

Yet, something was amiss. Even a simple random input generator could outperform my most effective whitebox fuzzer if it generated inputs fast enough. To understand why, we modelled fuzzing as a sampling process and proved some bounds [FSE'14, TSE'15].

mboehme.github.io/paper/TSE15.pdf

How can we use this insight? How to make our fuzzer explore more "behaviors" per minute (like a whitebox fuzzer)? We maximally bias the input generation towards rare behaviors. To understand how, we model our fuzzer as Markov chain [CCS'16, TSE'18].

mboehme.github.io/paper/TSE18.pdf

Did someone say Markov chain? Many search strategies are defined as traversals of Markov chains. Let's search something. We used Simulated Annealing search to reduce the distance to a given set of target locations in the other machine's code [CCS'17]

mboehme.github.io/paper/CCS17.pdf

Now, some machines process inputs only if they adhere to a certain structure, such as a file format. Instead of low-level mutations of an input, we suggest a high-level mutation of the structural representation of an input (partial parse tree) [TSE'19].

mboehme.github.io/paper/TSE19.pdf

Other machines require inputs to follow a certain *order*. For instance, servers implement protocols to communicate with a client, and phones are controlled by a sequence of user events. Knowing the required order, the problem might be easier [ICST'20].

mboehme.github.io/paper/ICST20.A…

If we don't know the required order, we can start with generating a random sequence. Along the way, we identify interesting states and take snapshots, like before a boss fight in a game. Once we are stuck, we restore the most progressive state [ICSE'20].

mboehme.github.io/paper/ICSE20.T…

Meanwhile, we wanted to stand fuzzing on some formal foundations, so we can investigate fundamental limitations of various approaches. Turns out, ecological biostatistics provides a nice statistical framework and some interesting estimators [TOSEM'18].

mboehme.github.io/paper/TOSEM18.…

Using and extending the STADS statistical model, we introduced information theory to fuzzing. Each new input reveals some information about the machine's behaviors. Entropy measures this information. Maximize entropy, you maximize efficiency [FSE'20].

mboehme.github.io/paper/FSE20.En…

We also used the STADS model to explain an empirical observation that seems like a contradiction. You increase # machines exponentially, you find *all* bugs exponentially faster, but given a fixed time budget, you only find linearly more bugs [FSE'20].

mboehme.github.io/paper/FSE20.Em…

After finding bugs, they need to be debugged & fixed [ISSTA'14, FSE'17, ICST'20]; e.g., our human-in-the-loop automated repair has the machine negotiate with the bug-reporting user the condition under which the program fails, before it repairs the bug.

mboehme.github.io/paper/ICST20.p…

Finally, none of this would be possible without our group's students, colleagues, and collaborators. Kudos!