PhD Thesis: Greybox Automatic Exploit Generation for Heap Overflows in Language Interpreters

Over the summer I defended my PhD thesis. You can find it here.

To give a super quick summary (prior to a rather verbose one ;)):

  • Pre-2016 exploit generation was primarily focused on single-shot, completely automated exploits for stack-based buffer overflows in things like network daemons and file parsers. In my opinion, the architecture of such systems unlikely to enable exploit generation systems for more complex bug classes, different target software, and in the presence of mitigations.
  • Inspired by the success of fuzzing at bug finding, I wanted to bring greybox input generation to bear on exploit generation. As a monolithic problem exploit generation is too complex a task for this to be feasible, so I set about breaking exploit generation down into phases and implementing greybox solutions for each stage. I designed these phases to be composable, and used a template language to enable for communication of solutions between phases.
  • Composable solver solutions and a human-writable template language gives two, new, powerful capabilities for an exploit generation engine: 1) “Human in the loop” means we can automate the things that are currently automatable, while allowing a human to solve the things we don’t have good solvers for, and 2) If solutions are composable, and if a mock solution can be produced for any stage, then we can solve stages out of order. This leads to efficiency gains if a solution to one stage is expensive to produce, but we can mock it out and see if such a solution would even be useful to later stages, and then come back and solve for it if it does turn out to be useful. In practice I leveraged this to assume particular heap layouts, check if an exploit can be created from that point, and only come back and try to achieve that heap layout if it turns out to be exploitable.
  • My belief is that the future of exploit generation systems will be architectures in which fuzzing-esque input generation mechanisms are applied to granular tasks within exploit generation, and the solutions to these problems are composed via template languages that allow for human provided solutions as necessary. Symbolic execution will play a limited, but important role, when precise reasoning is required, and other over-approximate static analysis will likely be used to narrow the search problems that both the input generation and symex engines have to consider.
  • You’ll find a detailed description of the assumptions I’ve made in Chapter 1, as well as an outline of some of the most interesting future work, in my opinion, in the final chapter.


I originally worked on exploit generation in 2009 (MSc thesis here), and the approach I developed was to use concolic execution to build SMT formulas representing path semantics for inputs that cause the program to crash, then conjoin these formulas with a logical condition expressing what a successful exploit would look like, and ask an SMT solver to figure out what inputs are required to produce the desired output. This works in some scenarios where there are limited protection mechanisms (IoT junk, for example), but has a number of limitations that prevent it from being a reasonable path to real-world automatic exploit generation (AEG) solutions. There’s the ever present issue with concolic execution that scaling it up to something like a web browser is a bit of an open problem, but the killer flaw is more conceptual, and it is worth explaining as it is the same flaw found at the heart of every exploit generation system I am aware of, right up to and including everything that participated in the DARPA Cyber Grand Challenge.

This earlier work (mine and others) essentially treats exploit generation as a two phase process. Firstly, they find a path to a location considered to be exploitable using a normal fuzzer or symbolic execution tool. ‘Exploitable’ almost always translates to ‘return address on the stack overwritten’ in this case, and this input is then passed to a second stage to convert it to an exploit. That second stage consists of rewriting the bytes in the original input that corrupt a function pointer or return address, and potentially also rewriting some other bytes to provide a payload that will execute a shell, or something similar. This rewriting is usually done by querying an SMT solver.

The conceptual flaw in this approach is the idea that a crashing input as discovered by a fuzzer will, in one step, be transformable into a functioning exploit. In reality, a crashing input from a fuzzer is usually just the starting point of a journey to produce an exploit, and more often than not the initial input leading to that crash is largely discarded once the bug has been manually triaged. The exploit developer will then begin to use it as part of a larger exploit that may involve multiple stages, and leverage the bug as one component piece.

Open Problems Circa 2016

From 2009 to 2016 I worked on other things, but in 2016 I decided to return to academia to do a PhD and picked up the topic again. Reviewing the systems that had participated in the DARPA CGC [3], as well as prior work, there were a few apparent interesting open problems and opportunities:

  1. All systems I found were focused on entirely automated exploit generation, with no capacity for tandem exploit generation with a human in the loop.
  2. No research I could find had yet to pick up on the notion of an ‘exploitation primitive’, which is fundamental in the manual construction of exploits, and will presumably be fundamental in any automated, or semi-automated approach.
  3. All systems treated AEG as essentially a two step process of 1) Find a path that triggers a bug, 2) Transform that path into an exploit in one shot, rather than a multi-stage ‘programming’ problem [4]. IMO, this is the primary limitation of these systems, as mentioned above, and the reason they are not extendable to more realistic scenarios.
  4. Nobody was really leveraging greybox input generation approaches (fuzzing) extensively, outside of the task of bug finding.
  5. Almost all systems were still focused on stack-based overflows.
  6. Nobody was working on integrating information leaks, or dealing with ASLR, in their exploit generation systems.
  7. Nobody was working on language interpreters/browsers.
  8. Nobody was working on kernels.

It’s likely that points 5-8 are the ‘reason’ for points 1-4. Once you decide to start tackling any of 5-8, by necessity, you must start thinking about multi-stage exploit generation, having human assistance, addressing bug classes other than stack-based overflows, and using greybox approaches in order to avoid the scalability traps in symbolic execution.


With the above in mind (I didn’t touch 6 or 8), the primary goal for my PhD was to see if I could explore and validate some ideas that I think will push forward the state of the art, and form the foundation of AEG tools in the future. Those ideas are:

  1. Real exploits are often relatively complex programs, with multiple distinct phases in which different tasks must be solved. Much like with ‘normal’ program synthesis, it is likely that different tasks will require different solvers. Also, by breaking the problem down we naturally make it easier to solve as long as solutions to distinct phases are composable. Thus, my first goal was to break the exploitation process down into distinct phases, with the intention of implementing different solvers for each. An interesting side effect of breaking the exploit generation task down into multiple, distinct, phases was it allowed me to integrate the idea of ‘lazy’ resolution of these phases, and solve them out of order. In practice, what this meant was that if a solver for an early stage was much more expensive than a later stage then my system allowed one to ‘mock’ out a solution to the early stage, and only come back to solve it for real once it was validated that having a solution for it would actually lead to an exploit.
  2. Once exploit generation is broken down into multiple phases, we have decisions to make about how to solve each. Symbolic execution has powered the core of most exploit generation engines, but it has terrible performance characteristics. OTOH fuzzing has proven itself to be vastly more scalable and applicable to a larger set of programs. Why hadn’t fuzzing previously taken off as a primary component of of exploit generation? Well, if you treat exploit generation as a single, monolithic, problem then the state space is simply too large and there’s no reasonable feedback mechanism to navigate it. Greybox approaches that do input generation using mutation really need some sort of gradient to scale and a scoring mechanism to tell them how they are doing. Once we have broken the problem down into phases it becomes much easier to design feedback mechanisms for each stage, and the scale of the state space at each stage is also drastically reduced. My second goal was therefore to design purely greybox, fuzzing inspired, solutions for each phase of my exploitation pipeline. I purposefully committed to doing everything greybox to see how far I could push the idea, although in reality you would likely integrate an SMT solver for a few surgical tasks.
  3. I knew it would be unlikely I’d hit upon the best solver for each pipeline stage at a first attempt, and it’s even possible that a real solution for a particular pipeline stage might be an entire PhD’s worth of research in itself. Thus it is important to enable one to swap out a particular automated solution for either a human provided solution, or an alternate solver. My third goal was then to figure out a way to enable multiple solvers to interact, be swappable, and to allow for a human in the loop. To enable this I designed a template approach whereby each stage, and a human exploit developer, could write and update exploits in a template language that further stages could understand and process. I wrote about what this looks like in practice here.

Alongside these goals I had to decide on a bug class and target software type to work with. Stack-based overflows had been done to death, so I decided to go with heap-based overflows which had received no attention. I also decided to target language interpreters (PHP and Python, in practice), as they’re ubiquitous and no exploit generation research had focused on them up to that point.

In the end the research was a lot of fun, and hopefully useful to others. I think the ideas of breaking down exploitation into multiple phases, using greybox solutions as much as possible, and using template-driven exploitation to integrate various solvers, or optionally a human, have real legs and are likely to be found in practical AEG engines of the future.

P.S. Thanks to my colleagues and friends that allowed me to bounce ideas off them, that read drafts, and that were generally awesome. Thanks as well to the anonymous reviewers of CCS, USENIX Security, and IEEE S&P. A lot of words have been written about the problems of the academic review process for both authors and reviewers, but on an individual and personal level I can’t but appreciate the fact that total strangers took their time to work through my papers and provide feedback.

Further Reading

Thesis – Contains all of my research, along with a lot of introductory and background material, as well as ideas for future work. One of the things I wanted to be quite clear about in my work was the limitations, and in those limitations it’s clear there’s plenty of scope for multiple more PhDs from this topic. In Section 1.2 I outline my assumptions, and by thinking about how to alleviate these you’ll find multiple interesting problems. In Section 6.1 I explicitly outline a bunch of open problems that are interesting to me. (Btw, if you do end up working on research in the area and would like feedback on anything feel free to drop me a mail).

Automatic Heap Layout Manipulation for Exploitation (USENIX Security 2018) – A paper on the heap layout problem, and a greybox solution for it. Also discusses exploit templates.

Gollum: Modular and Greybox Exploit Generation for Heap Overflows in Interpreters (ACM CCS 2019) – A paper on an end-to-end architecture for exploit generation using entirely greybox components.

Gollum: Modular and Greybox Exploit Generation for Heap Overflows in Interpreters

At the upcoming ACM Conference on Computer and Communications Security (CCS) I’ll be presenting a paper on Automatic Exploit Generation (AEG), with the same title as this blog post. You can find the paper here. In the paper I discuss a system for automatically discovering primitives and constructing exploits using heap overflows in interpreters. The approach taken in the paper is a bit different from most other AEG solutions in that it is entirely greybox, relying on lightweight instrumentation and various kinds of fuzzing-esque input generation. The following diagram shows the stages of the system, and each is explained in detail in the paper. 

Workflow diagram for Gollum
Workflow diagram showing how Gollum produces exploits and primitives

In terms of evaluation, I used 10 vulnerabilities in the PHP and Python interpreters as tests, and provided these as input to Gollum for it to use in its search for primitives and to build exploits.

Exploit generation and primitive search results
Exploit generation and primitive search results

There are three main takeaways from the paper that I think worth highlighting (see paper for details!):

1. AEG is a multi-stage process, and by breaking the problem into distinct phases it becomes reasonable to attack a number of those phases using a fuzzing-esque combination of lightweight instrumentation and relatively dumb input generation. Traditionally, AEG systems used symbolic execution as their main driver and, while there are some positives to this, it also encounters all of the scalability issues that one expects with symbolic execution. In a paper last year at USENIX Security, I showed how with lightweight instrumentation one could use the existing tests of an application, combined with a fuzzer, to discover language fragments that could be used to perform heap layout manipulation, as well as to allocate interesting objects to corrupt. In the upcoming CCS paper, I show how one can use a similar approach to also discover exploitation primitives, and in certain situations to even build exploits. It’s worth noting that in their paper on FUZE, Wu et al. take a similar approach, and you should check out their paper for another example system. My guess is that in the next couple of years fuzzing-driven exploit generation is likely to be the predominant flavour, with symbolic execution being leveraged in scenarios where its bit-precise reasoning is required and state-space explosion can be limited.

2. When automatically constructing exploits for heap overflows one needs a solution for achieving the desired heap layout and then another solution for building the rest of the exploit. In the CCS paper I introduce the idea of lazy resolution of tasks in exploit generation. Essentially, this is an approach for solving the problems of heap layout manipulation and the rest of the exploit generation in the reverse order. The reason one might want to do this is simple: in an engine where the process for achieving the heap layout can potentially take much longer than the one to create the rest of the exploit (as is the case in Gollum), it makes sense to check if it is feasible to produce an exploit under the assumption that the more difficult problem is solvable, and then only bother to solve it if it enables an exploit. Specifically, in the case of Gollum, I constructed a heap allocator that allows you to request a particular layout, then you can attempt to generate the exploit under the assumption the layout holds, and only later figure out how to achieve it once you know it enables the exploit.

I think this sort of idea might be more generally useful in exploit generation for other vulnerability types as well, e.g. in an exploit generation system for race conditions, one could have a solution that allows one to request a particular scheduling, check if that scheduling enables an exploit, and only then search for the input required to provide the scheduling. Such an approach also allows for a hybrid of manual and automatic components. For example, in our case we assume a heap layout holds, then generate an exploit from it, and finally try and automatically solve the heap layout problem. Our solution for the heap layout problem has a number of preconditions though, so in cases where those conditions are not met we can still automatically generate the rest of the exploit under the assumption that the layout problem is solved, and eventually the exploit developer can manually solve it themselves.

3. In last year’s USENIX Security paper I discussed a random search algorithm for doing heap layout manipulation. As you might expect, a genetic algorithm, optimising for distance between the two chunks you want to place adjacent to each other, can perform this task far better, albeit at the cost of a more complicated and time consuming implementation.

Random search versus GA graph
% of heap layout benchmarks solved by random search (rand) versus the genetic algorithm (evo)


Automation in Exploit Generation with Exploit Templates

At last year’s USENIX Security conference I presented a paper titled “Automatic Heap Layout Manipulation for Exploitation” [paper][talk][code]. The main idea of the paper is that we can isolate heap layout manipulation from much of the rest of the work involved in producing an exploit, and solve it automatically using blackbox search. There’s another idea in the paper though which I wanted to draw attention to, as I think it might be generally useful in scaling automatic exploit generation systems to more real world problems. That idea is exploit templates.

An exploit template is a simply a partially completed exploit where the incomplete parts are to be filled in by some sort of automated reasoning engine. In the case of the above paper, the parts filled in automatically are the inputs required to place the heap into a particular layout. Here’s an example template, showing part of an exploit for the PHP interpreter. The exploit developer wants to position an allocation made by imagecreate adjacent to an allocation made by quoted_printable_encode.

$quote_str = str_repeat("\xf4", 123);

$image = imagecreate(1, 2); 



SHRIKE (the engine that parses the template and searches for solutions to heap layout problems) takes as input a .php file containing a partially completed exploit, and searches for problems it should solve automatically. Directives used to communicate with the engine begin with the string X-SHRIKE. They are explained in full in the above paper, but are fairly straightforward: HEAP-MANIP tells the engine it can insert heap manipulating code at this location, RECORD-ALLOC tells the engine it should record the nth allocation that takes place from this point onwards, and REQUIRE-DISTANCE tells the engine that at this point in the execution of the PHP program the allocations associated with the specified IDs must be at the specified distance from each other. The engine takes this input and then starts searching for ways to put the heap into the desired layout. The above snippet is from an exploit for CVE-2013-2110 and this video shows SHRIKE solving it, and the resulting exploit running with the heap layout problem solved. For a more detailed description of what is going on in the video, view its description on YouTube.

So, what are the benefits of this approach? The search is black-box, doesn’t require the exploit developer to analyse the target application or the allocator, and, if successful, outputs a new PHP file that achieves the desired layout and can then be worked on to complete the exploit. This has the knock-on effect of making it easier for the exploit developer to explore different exploitation strategies for a particular heap overflow. In ‘normal’ software development it is accepted that things like long build cycles are bad, while REPLs are generally good. The reason is that the latter supports a tight loop of forming a hypothesis, testing it, refining and repeating, while the former breaks this process. Exploit writing has a similar hypothesis refinement loop and any technology that can make this loop tighter will make the process more efficient.

There’s lots of interesting work to be done still on how exploit templates can be leveraged to add automation to exploit development. In automatic exploit generation research there has been a trend to focus exclusively on full automation and, because that is hard for almost all problems, we haven’t explored in any depth what aspects can be partially automated. As such, there’s a lot of ground still to be broken. The sooner we start investigating these problems the better, because if the more general program synthesis field is anything to go by, the future of automatic exploit generation is going to look more like template-based approaches than end-to-end solutions.

Some Cool Projects from a Dagstuhl Seminar on SAT, SMT and CP

I was lucky enough to attend a Dagstuhl seminar titled “Bringing CP, SAT & SMT Together” earlier this week, and learned about some really cool work I hadn’t previously heard of, especially in the realm of constraint satisfaction and optimization. There were plenty of other of great talks and discussions, but below are the projects I made a note to play around with.


MiniZinc is a free and open-source constraint modeling language.

You can use MiniZinc to model constraint satisfaction and optimization problems in a high-level, solver-independent way, taking advantage of a large library of pre-defined constraints. Your model is then compiled into FlatZinc, a solver input language that is understood by a wide range of solvers.

There are even a couple of Coursera courses on the topic.


Unison is a simple, flexible, and potentially optimal tool that performs integrated register allocation and instruction scheduling using constraint programming as a modern method for combinatorial optimization.

Approximate Model Counting

Blog post by Mate Soos (author of cryptominisat), with code:

Approximate model counting allows to count the number of solutions (or “models”) to propositional satisfiability problems. This problem seems trivial at first given a propositional solver that can find a single solution: find one solution, ban it, ask for another one, ban it, etc. until all solutions are counted. The issue is that sometimes, the number of solutions is 2^50 and so counting this way is too slow. There are about 2^266 atoms in the universe, so counting anywhere near that is impossible using this method.


Slightly chilled attendees




Fuzzing PHP’s unserialize Function

Recently, the PHP development team have decided that they will no longer consider bugs in the implementation of the unserialize function to be security relevant. In this post I’d like to outline why I think this is a bad idea, and provide an easy set up for fuzzing/ongoing QA of unserialize, as the fact that it is a bottomless pit of bugs seems to be part of the motivation for this move.

The argument for the change in categorisation is twofold. Firstly, they state that unserialize is inherently an unsafe function to use on data from an untrusted source. Essentially, they are saying that there is no point in treating bugs in the implementation of unserialize as security-relevant, because the mere fact that an application passes untrusted data to it means that the security of that application has already been compromised. Secondly, they argue that treating unserialize bugs as security relevant encourages developers to use it on untrusted data. In my opinion this is quite a weak point. It is prominently documented that unserialize is unsafe, and if that warning doesn’t get the message across then I very much doubt that a change in categorisation in the PHP bug tracker will.

Lets briefly discuss the first point in a little more detail, as the reality is a bit more nuanced. Often, it is relatively easy to leverage an unserialize of untrusted data without resorting to attacking the unserialize implementation itself. There are some requirements for this though. In particular, the attacker must be able to find a class containing a PHP magic method in the target application or one of the libraries that it makes use of, e.g. a __destruct function. Also, if the allowed_classes argument to unserialize is provided then the class containing the magic method must be included in this list. These conditions don’t always hold. If the application is closed source then the attacker will have no direct way to figure out the name of such classes, and if allowed_classes is the empty list then they won’t be able to make use of them anyway.

The above are not merely hypothetical scenarios.  This rather nice write-up documents the exploitation of a vulnerability in PornHub which required the attackers to target the unserialize implementation. As mentioned in the write-up, the fact that the application was closed source prevented them from discovering a class which could be used for object injection.

I think most people will agree with the PHP development team that if an application contains a call to unserialize with untrusted data then it is a bad idea and should be fixed. However, it is also true that treating unserialize bugs like normal bugs unnecessarily exposes PHP application developers, and the users of their applications, to further risk.

The Fun Part

One reason the PHP development team are drowning in unserialize bugs appears to be that they either don’t fuzz the function at all after making changes, or that their mechanism for fuzzing it is ineffective. I fully recognize that the functionality that unserialize implements is complex and that adding to it, or modifying the existing code, is always going to come with the risk of introducing bugs. However, I also believe that with a small of effort it should be possible to significantly decrease the number of low hanging fruit that make it to release builds.

Anyway, in the interests of putting my shell scripts where my mouth is, I’ve uploaded a repository of scripts and auxiliary files for building PHP and fuzzing unserialize via AFL. There’s no secret sauce. If anything that’s kind of the point; ongoing sanity checking of the existing unserialize implementation and changes to it could be trivially automated.

The README file explains how to get everything up and running, but in short it should just be a matter of running ./ && ./ && ./ output N.  A GNU screen session will be running in the background containing the output of an AFL master instance and N slaves. which you can attach to via screen -r fuzz.

The scripts are straightforward, but there are a few things worth noting for the curious:

  • The driver PHP script loads a string representing the data to be unserialized from a file and passes it directly to unserialize. This should be sufficient to find a significant portion of the bugs that I know of that have previously been fixed in unserialize, e.g. things like this. However, if some extra PHP code is required to trigger the bug then it will not be found. e.g. things like this. It should be relatively easy to extend the fuzzing setup with ideas from other blog posts on the topic, e.g. there are some good ideas in this post by the people who wrote the PornHub exploit mentioned above.
  • One can either build all of PHP with AFL’s instrumentation, or just the components that one thinks will be relevant to the unserialize functionality. The advantage of the former is you’re guaranteed that AFL can intelligently explore all functionality which may be triggered via unserialize, with the disadvantage that it is slower. The script currently compiles everything with AFL’s instrumentation. If you would like a faster binary you can compile PHP without AFL/ASAN, delete the object files that relate to unserialize, reconfigure the build to use AFL/ASAN and then recompile those object files. I’ve used this is the past and it works quite well but you need to make sure you recompile all the object files which relate to code that unserialize might trigger, otherwise AFL won’t be able to track coverage there.
  • AFL can be provided with a dictionary of tokens which it will use when fuzzing. The dictionary in the repository contains tokens pulled from the unserialize parser and I think it is fairly complete, but if I’ve missed anything let me know and I’ll be sure to include it.
  • The seed files one provides to AFL for fuzzing can have a significant impact on it’s ability to find bugs, and how quickly one finds a particular bug. The seed files I have provided have been constructed from examples of valid unserialize usage I’ve found in the PHP documentation and triggers for previous vulnerabilities. Feel free to let me know if you find a seed file which would be useful to add.
  • I have created this repository by pulling files and configurations from my fuzzing machines as I write this blog post. The goal is to give a faithful representation of the setup I’ve used in the past to find multitudes of unserialize bugs. However, I may have forgotten something, or broken something in the process of pulling it all together for release. As I’m writing this I have started up the script to ensure everything works, but it’s possible I’ve messed something up and won’t notice. If that does turn out to be the case, let me know! If you’d like to confirm everything is functional then compile PHP version 5.6.11 and you should find this bug within 40 million executions or so.

Happy hunting!

(Unrelated side note: I’ll be teaching a 4 day version of ‘Advanced Tool Development with SMT Solvers’ in London in early November. See here for details if you’re interested!)


Upcoming Public Training: 4 Days of Advanced Tool Development with SMT Solvers (London, Nov ’17)

TL;DR: I’ll be running a new version of the Advanced Tool Development with SMT Solvers training course in London, starting November 6th 2017. The most significant change is the addition of an extra day covering some diverse real world analysis platforms. See for details. Read on for more info on the new content.

For almost 5 years I’ve been running training courses on SMT-based program analysis technology. The contents have evolved continuously over the this time, keeping up with new advances in the space, but I’ve stuck with the 3 day format as it has allowed for the best balance between catering for complete newbies and those with prior experience.

For much of this time, the number of real world symbolic execution tools that are 1) publicly available, 2) still being actively maintained and 3) amenable to extension, improvement and re-purposing, has been quite limited. Due to this, most of the training has focused on fundamentals of SMT-based analysis, under the assumption that there’s a significant chance the students would have to develop their own systems from scratch. In the early days I did include introductions to S2E and KLEE, but both are rather large C++-based projects which students seemed to struggle with in the compressed time frame of a training course.

Recently, partially due to the DARPA Cyber Grand Challenge, and partially due to an uptick in industry interest in the technology, the number of public frameworks and architectures made available has increased significantly.  Due to this, I’ve decided to add a 4th day which will focus entirely on introducing, comparing and contrasting some publicly available systems. While the exact contents may change between now and November, the preliminary list looks as follows: angr, CBMC, KLEE and manticore. These four tools occupy different points in the design space of symbolic execution platforms and show interesting takes on the fundamental concepts. There are lots of different ways to achieve the same end with symbolic execution tools and I think these four implementations should well prepare students to develop their own tech, as well as enabling them to build on public code if they so wish.

If the above sounds interesting, drop a mail to to book a place, or check out for more details.


Tracking Down Heap Overflows with rr

Anyone who’s spent time doing vulnerability analysis on C/C++ has had the experience of floundering around in a debugger for hours on end trying to figure out the source of a mysterious crash.

The reason this can be an incredibly time consuming and frustrating process is simple: memory corruption is often quite subtle in its effect. The fact that corruption has occurred may not actually become apparent until far later in the program’s execution, when all trace of the buggy function is gone from the call-stack. Along with that, due to randomisation of various things, such as memory layout and allocation patterns, the same root cause can manifest in a variety of different ways across multiple runs.

For example, lets say we’re analysing an interpreter, e.g. php, and the following occurs: an API call triggers a function containing a bug, and a write to buffer X overflows into the memory occupied by object Y, smashing some pointers internal to Y.  The API call returns, the interpreted program eventually ends and the interpreter begins to shutdown. During the shutdown process it notifies Y, which tries to use its (now corrupted) internal pointers and crashes. By the time the crash occurs, there is no trace of the buggy API call on the call-stack, nor is there any apparent link in the source code between the contents of buffer X and the corrupted internal pointer of object Y.

The above scenario isn’t limited to buffer overflows on the heap. Use-after-frees and other memory life-time management issues can have similar effects. At a high level the question we want to answer when debugging such situations is straightforward ‘Where did the data that corrupted this location get written?’. Taint tracking solutions attempt to solve this problem by tracking data forwards from a taint source. For various reasons, all existing implementations tend to be limited to two of  fast, accurate or detailed, and all three are often required for a trace of tainted data to be useful.

This brings me to rr, a tool developed by Robert O’Callahan of Mozilla. The project page is here, and this video is a good introduction to the tool. rr can do really fast record and replay, but on top of that it can also do really fast reverse execution. During replay, the user interface provided is gdb‘s, and thus you effectively get your standard debugger interface but with a guarantee that repeated runs will be identical, as well as the ability to execute in reverse. The key to solving our heap overflow problem is that not only can you execute in reverse, but that, during reverse execution, watch points (and normal breakpoints) still function. In other words, if we want to know where some data in memory came from, we can set a watch point on it, execute reverse-continue and the program will execute in reverse until the point where the data was written [1].

I hope the following example highlights how useful this capability can be.

The php interpreter  recently had a potentially remotely exploitable issue due to a flaw in the libgd library, which it bundles. The libgd issue was assigned CVE-2016-3074 and the PHP bug tracker entry is here. The reporter rather helpfully included a PoC exploit, which you can find at the previous link, that is intended to spawn a reverse shell. This PoC is a useful starting point for a ‘real’ exploit, but is pretty much ‘hit and hope’ in terms of reliability: it sprays data after a overflowed buffer, seemingly in the hope of corrupting a function pointer called before the corruption causes the process to die for some other reason [2]. For fun I decided to build a more reliable exploit around the primitives offered by the bug, and the first step of this was figuring out exactly why the existing PoC was failing.

When I first ran the PoC, mod_php died in a strlen function call due to being passed a pointer to an unmapped region of memory. The backtrace at that point (in normal gdb) looked as follows:

[root@localhost ~]# gdb --pid=1963
GNU gdb (GDB) Fedora 7.10.1-31.fc23
0x00007f7ca5dc6a68 in accept4 (fd=4, addr=addr@entry=..., addr_len=addr_len@entry=0x7ffe3580e2e0, flags=flags@entry=524288) at ../sysdeps/unix/sysv/linux/accept4.c:40
40      return SYSCALL_CANCEL (accept4, fd, addr.__sockaddr__, addr_len, flags);
(gdb) c

Program received signal SIGSEGV, Segmentation fault.
strlen () at ../sysdeps/x86_64/strlen.S:106
106        movdqu    (%rax), %xmm12
(gdb) bt
#0  strlen () at ../sysdeps/x86_64/strlen.S:106
#1  0x00007f7ca312aad9 in format_converter (odp=0x7ffe3580bff0, fmt=0x7f7ca37dca49 "s(%d) :  Freeing 0x%.8lX (%zu bytes), script=%s\n", ap=0x7ffe3580c040)
    at php-7.0.5-debug/main/snprintf.c:993
#2  0x00007f7ca312b40c in strx_printv (ccp=0x7ffe3580c05c, buf=0x7ffe3580c380 "[Thu May 26 12:32:29 2016]  Script:  '/var/www/html/upload.php'\n", len=512, format=0x7f7ca37dca48 "%s(%d) :  Freeing 0x%.8lX (%zu bytes), script=%s\n", 
    ap=0x7ffe3580c040) at php-7.0.5-debug/main/snprintf.c:1248
#3  0x00007f7ca312b645 in ap_php_snprintf (buf=0x7ffe3580c380 "[Thu May 26 12:32:29 2016]  Script:  '/var/www/html/upload.php'\n", len=512, format=0x7f7ca37dca48 "%s(%d) :  Freeing 0x%.8lX (%zu bytes), script=%s\n")
    at php-7.0.5-debug/main/snprintf.c:1293
#4  0x00007f7ca3126483 in php_message_handler_for_zend (message=4, data=0x7ffe3580d410) at php-7.0.5-debug/main/main.c:1444
#5  0x00007f7ca31b5523 in zend_message_dispatcher (message=4, data=0x7ffe3580d410) at php-7.0.5-debug/Zend/zend.c:998
#6  0x00007f7ca3182bef in zend_mm_check_leaks (heap=0x7f7c96a00040) at php-7.0.5-debug/Zend/zend_alloc.c:2129
#7  0x00007f7ca3182f2e in zend_mm_shutdown (heap=0x7f7c96a00040, full=0, silent=0) at php-7.0.5-debug/Zend/zend_alloc.c:2201
#8  0x00007f7ca3183d1b in shutdown_memory_manager (silent=0, full_shutdown=0) at php-7.0.5-debug/Zend/zend_alloc.c:2637
#9  0x00007f7ca3127255 in php_request_shutdown (dummy=0x0) at php-7.0.5-debug/main/main.c:1849
#10 0x00007f7ca3274e8a in php_apache_request_dtor (r=0x55a587a49780) at php-7.0.5-debug/sapi/apache2handler/sapi_apache2.c:518

Again using normal gdb we can quickly figure out that the issue is that strlen is passed a pointer to unmapped memory, and that the source of that pointer is the php_message_handler_for_zend function (frame 4 above). e.g.:

(gdb) f 1
#1 0x00007f7ca312aad9 in format_converter (odp=0x7ffe3580bff0, fmt=0x7f7ca37dca49 "s(%d) : Freeing 0x%.8lX (%zu bytes), script=%s\n", ap=0x7ffe3580c040)
 at php-7.0.5-debug/main/snprintf.c:993
993 s_len = strlen(s);
(gdb) l
989 case 's':
990 case 'v':
991 s = va_arg(ap, char *);
992 if (s != NULL) {
993     s_len = strlen(s);
994     if (adjust_precision && precision < s_len) {
995         s_len = precision;
996     }
997 } else {
(gdb) p/x s
$1 = 0xa8bc37
(gdb) x/x s
0xa8bc37: Cannot access memory at address 0xa8bc37

This tells us that the argument to strlen is a vararg. We can figure out where that came from easily enough:

(gdb) f 2
#2 0x00007f7ca312b40c in strx_printv (ccp=0x7ffe3580c05c, buf=0x7ffe3580c380 "[Thu May 26 12:32:29 2016] Script: '/var/www/html/upload.php'\n", len=512, format=0x7f7ca37dca48 "%s(%d) : Freeing 0x%.8lX (%zu bytes), script=%s\n", 
 ap=0x7ffe3580c040) at php-7.0.5-debug/main/snprintf.c:1248
1248 cc = format_converter(&od, format, ap);
(gdb) f 3
#3 0x00007f7ca312b645 in ap_php_snprintf (buf=0x7ffe3580c380 "[Thu May 26 12:32:29 2016] Script: '/var/www/html/upload.php'\n", len=512, format=0x7f7ca37dca48 "%s(%d) : Freeing 0x%.8lX (%zu bytes), script=%s\n")
 at php-7.0.5-debug/main/snprintf.c:1293
1293 strx_printv(&cc, buf, len, format, ap);
(gdb) f 4
#4 0x00007f7ca3126483 in php_message_handler_for_zend (message=4, data=0x7ffe3580d410) at php-7.0.5-debug/main/main.c:1444
1444 snprintf(memory_leak_buf, 512, "%s(%d) : Freeing 0x%.8lX (%zu bytes), script=%s\n", t->filename, t->lineno, (zend_uintptr_t)t->addr, t->size, SAFE_FILENAME(SG(request_info).path_translated));
(gdb) p/x t->filename
$2 = 0xa8bc37

From the above code we can see that php_message_handler_for_zend is where the corrupted pointer is read and utilised as an argument to snprintf, while ap_php_snprintf and strx_printv just pass through the ap variable, from which the invalid pointer is eventually extracted and used in format_converter.

We are now back at the problem I stated in the beginning: We have a corrupted memory location, &(t->filename),and we want to know the source of that corruption. In a ‘normal’ dataflow tracking scenario we could read the source code and find locations that write to &(t->filename) and work from there. When a variable is influenced due to a heap overflow of an unrelated memory buffer that is no longer an option. Once corruption has occurred we’ve traversed from the state-space which is apparent by inspecting the source to the state-space of a ‘weird machine’ which, among other things, is dependent on memory layout.

Fortunately, ‘What is the source of data at memory location x?‘ is exactly the kind of question that rr can help us answer. We begin by starting the target (apache in this case) under rr, and triggering the crash. This is simply achieved via rr httpd -X. We can then replay the session up until the crash point as follows:

[root@localhost tmp]# rr replay
GNU gdb (GDB) Fedora 7.10.1-31.fc23
0x00007f8710739c80 in _start () from /lib64/
(rr) c
AH00558: httpd: Could not reliably determine the server's fully qualified domain name, using localhost.localdomain. Set the 'ServerName' directive globally to suppress this message
[New Thread 57236.57239]

Program received signal SIGSEGV, Segmentation fault.
strlen () at ../sysdeps/x86_64/strlen.S:106
106        movdqu    (%rax), %xmm12

From our previous analysis we know the data which we wish to know the source of is the memory backing t->filename in frame 4, so we can switch to that frame and add a watch point:

(rr) f 4
#4  0x00007f870c079483 in php_message_handler_for_zend (message=4, data=0x7ffd14c702c0) at php-7.0.5-debug/main/main.c:1444
1444                        snprintf(memory_leak_buf, 512, "%s(%d) :  Freeing 0x%.8lX (%zu bytes), script=%s\n", t->filename, t->lineno, (zend_uintptr_t)t->addr, t->size, SAFE_FILENAME(SG(request_info).path_translated));
(rr) p &(t->filename)
$1 = (const char **) 0x7ffd14c702d0
(rr) watch -l t->filename
Hardware watchpoint 1: -location t->filename
(rr) reverse-continue 

Program received signal SIGSEGV, Segmentation fault.
strlen () at ../sysdeps/x86_64/strlen.S:106
106        movdqu    (%rax), %xmm12
(rr) reverse-continue 
Hardware watchpoint 1: -location t->filename

Old value = 0xa8bc37 <error: Cannot access memory at address 0xa8bc37>
New value = 0xff15e8fef2615642 <error: Cannot access memory at address 0xff15e8fef2615642>
0x00007f870c0d5bab in zend_mm_check_leaks (heap=0x7f86ffa00040) at php-7.0.5-debug/Zend/zend_alloc.c:2123
2123                                leak.filename = dbg->filename;
(rr) p &(leak.filename)
$2 = (const char **) 0x7ffd14c702d0
(rr) p/x dbg->filename
$3 = 0xa8bc37

From the above we discover that the write to t->filename (address 0x7ffd14c702d0) was line 2123, in the zend_mm_check_leaks function. The value was sourced from dbg->filename, which already contains the invalid pointer, so we repeat the process to discover the source of that variable.

(rr) delete 1
(rr) watch -l dbg->filename
Hardware watchpoint 2: -location dbg->filename
(rr) reverse-continue 
Hardware watchpoint 2: -location dbg->filename

Old value = 0xa8bc37 <error: Cannot access memory at address 0xa8bc37>
New value = 0x0
__mempcpy_sse2 () at ../sysdeps/x86_64/memcpy.S:219
219        movq     %r8,  8(%rdi)
(rr) bt
#0  __mempcpy_sse2 () at ../sysdeps/x86_64/memcpy.S:219
#1  0x00007f870ec8f55e in __GI__IO_file_xsgetn (fp=0x56128d40a9a0, data=<optimized out>, n=18446744073709551615) at fileops.c:1392
#2  0x00007f870ec848b6 in __GI__IO_fread (buf=<optimized out>, size=1, count=18446744073709551615, fp=0x56128d40a9a0) at iofread.c:42
#3  0x00007f870be6ed79 in fileGetbuf (ctx=0x7f86ffa5a0e0, buf=0x7f86ffa5e0a0, size=-1) at php-7.0.5-debug/ext/gd/libgd/gd_io_file.c:91
#4  0x00007f870be6e47e in php_gd_gdGetBuf (buf=0x7f86ffa5e0a0, size=-1, ctx=0x7f86ffa5a0e0) at php-7.0.5-debug/ext/gd/libgd/gd_io.c:131
#5  0x00007f870be6c79c in _gd2ReadChunk (offset=1176, compBuf=0x7f86ffa5e0a0 '\220' <repeats 40 times>, "\242", <incomplete sequence \354\266>, compSize=-1, chunkBuf=0x7f86ffa70000 'A' <repeats 100 times>, chunkLen=0x7ffd14c6e898, 
    in=0x7f86ffa5a0e0) at php-7.0.5-debug/ext/gd/libgd/gd_gd2.c:213
#6  0x00007f870be6cad8 in php_gd_gdImageCreateFromGd2Ctx (in=0x7f86ffa5a0e0) at php-7.0.5-debug/ext/gd/libgd/gd_gd2.c:311
#7  0x00007f870be6c801 in php_gd_gdImageCreateFromGd2 (inFile=0x56128d40a9a0) at php-7.0.5-debug/ext/gd/libgd/gd_gd2.c:232
#8  0x00007f870be5d337 in _php_image_create_from (execute_data=0x7f86ffa130d0, return_value=0x7f86ffa130c0, image_type=9, tn=0x7f870c5b4e77 "GD2", func_p=0x7f870be6c7d9 <php_gd_gdImageCreateFromGd2>, 
    ioctx_func_p=0x7f870be6c86c <php_gd_gdImageCreateFromGd2Ctx>) at php-7.0.5-debug/ext/gd/gd.c:2385
#9  0x00007f870be5d572 in zif_imagecreatefromgd2 (execute_data=0x7f86ffa130d0, return_value=0x7f86ffa130c0) at php-7.0.5-debug/ext/gd/gd.c:2483
#28 0x000056128c671437 in main (argc=2, argv=0x7ffd14c71688) at main.c:777

Executing in reverse we discover the corruption was caused by a call to __GI__IO_freadwith a count of -1, which is the overflow leveraged by the PoC. At this point we might like to know a few other things, such as how much data was actually read in, as well as how big the destination buffer is.

The first value is trivial to find, in the same way as you normally would with gdb, as it is the return value of the fread function.

(rr) f 3
#3 0x00007f7958587d79 in fileGetbuf (ctx=0x7f794c05a0e0, buf=0x7f794c05e0a0, size=-1) at php-7.0.5-debug/ext/gd/libgd/gd_io_file.c:91
91 return fread(buf, 1, size, fctx->f);
(rr) finish
Run till exit from #3 0x00007f7958587d79 in fileGetbuf (ctx=0x7f794c05a0e0, buf=0x7f794c05e0a0, size=-1) at php-7.0.5-debug/ext/gd/libgd/gd_io_file.c:91
php_gd_gdGetBuf (buf=0x7f794c05e0a0, size=-1, ctx=0x7f794c05a0e0) at php-7.0.5-debug/ext/gd/libgd/gd_io.c:132
132 }
Value returned is $2 = 612

To find the size of the destination buffer (which is at address 0x7f86ffa5e0a0) we can look over the backtrace to see the first function that doesn’t take it as an argument (php_gd_gdImageCreateFromGd2Ctx), set a breakpoint where it calls the first function in the backtrace that does take the buffer as an argument and replay the execution again:

(rr) f 6
#6  0x00007f870be6cad8 in php_gd_gdImageCreateFromGd2Ctx (in=0x7f86ffa5a0e0) at php-7.0.5-debug/ext/gd/libgd/gd_gd2.c:311
311                    if (!_gd2ReadChunk(chunkIdx[chunkNum].offset, compBuf, chunkIdx[chunkNum].size, (char *) chunkBuf, &chunkLen, in)) {
(rr) b 311
Breakpoint 6 at 0x7f870be6ca88: file php-7.0.5-debug/ext/gd/libgd/gd_gd2.c, line 311.
(rr) r
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: /usr/sbin/httpd 

[Thread 57236.57236] #1 stopped.
0x00007f8710739c80 in _start () from /lib64/
(rr) c
AH00558: httpd: Could not reliably determine the server's fully qualified domain name, using localhost.localdomain. Set the 'ServerName' directive globally to suppress this message
warning: Temporarily disabling breakpoints for unloaded shared library "/usr/lib64/httpd/modules/"
[New Thread 57236.57239]

Breakpoint 6, php_gd_gdImageCreateFromGd2Ctx (in=0x7f86ffa5a0e0) at php-7.0.5-debug/ext/gd/libgd/gd_gd2.c:311
311                    if (!_gd2ReadChunk(chunkIdx[chunkNum].offset, compBuf, chunkIdx[chunkNum].size, (char *) chunkBuf, &chunkLen, in)) {
(rr) p compBuf
$13 = 0x7f86ffa5e0a0 ""

Now we’re back to the familiar problem of having a variable (compBuf) and wanting to know where its value came from, so we set a watchpoint and switch from forwards execution to reverse execution to find the allocation site of the buffer, and its size.

(rr) watch -l compBuf
Hardware watchpoint 7: -location compBuf
(rr) reverse-continue 
Hardware watchpoint 7: -location compBuf

Old value = 0x7f86ffa5e0a0 ""
New value = 0x0
0x00007f870be6ca1d in php_gd_gdImageCreateFromGd2Ctx (in=0x7f86ffa5a0e0) at php-7.0.5-debug/ext/gd/libgd/gd_gd2.c:292
292            compBuf = gdCalloc(compMax, 1);
(rr) p compMax
$14 = 112

Finally, for the sake of completeness, it might be useful to know what the data represented before it was corrupted, which will tell us what the key difference between crashing and non-crashing runs is. Since the data flows straight from the overflow location to its first use in zend_mm_check_leaks, which is a function internal to the allocator and which operates on heap metadata, a reasonable assumption is that the overflow corrupts something other than dbg->filename, which tricks the allocator into thinking that dbg->filename is a valid pointer to a string. If we look at zend_mm_check_leaks we can confirm this may be the case:

(rr) l
2118 j = 0;
2119 while (j < bin_elements[bin_num]) {
2120     if (dbg->size != 0) {
2121         leak.addr = (zend_mm_debug_info*)((char*)p + ZEND_MM_PAGE_SIZE * i + bin_data_size[bin_num] * j);
2122         leak.size = dbg->size;
2123         leak.filename = dbg->filename;
2124         leak.orig_filename = dbg->orig_filename;
2125         leak.lineno = dbg->lineno;
2126         leak.orig_lineno = dbg->orig_lineno;

We can assume based on the above that the entire dbg object has been corrupted, and because dbg->size has been changed to a non-zero value we have ended up at the crash location that we have. This can be confirmed by tracing the value to its source in the same way as before:

(rr) awatch -l dbg->size
Hardware access (read/write) watchpoint 4: -location dbg->size
(rr) reverse-continue 
Hardware access (read/write) watchpoint 4: -location dbg->size

Value = 4665427
0x00007f7db1825b9c in zend_mm_check_leaks (heap=0x7f7da5200040) at /home/sean/Documents/Git/EntomologyPrivate/PHP/CVE-2016-3074/php-7.0.5-debug/Zend/zend_alloc.c:2122
2122 leak.size = dbg->size;
Hardware access (read/write) watchpoint 4: -location dbg->size

Value = 4665427
0x00007f7db1825b56 in zend_mm_check_leaks (heap=0x7f7da5200040) at /home/sean/Documents/Git/EntomologyPrivate/PHP/CVE-2016-3074/php-7.0.5-debug/Zend/zend_alloc.c:2120
2120 if (dbg->size != 0) {
Hardware access (read/write) watchpoint 4: -location dbg->size

Old value = 4665427
New value = 0
__mempcpy_sse2 () at ../sysdeps/x86_64/memcpy.S:218
218 movq %rax, (%rdi)
(rr) bt
#0 __mempcpy_sse2 () at ../sysdeps/x86_64/memcpy.S:218
#1 0x00007f7db43df55e in __GI__IO_file_xsgetn (fp=0x563db9fbb9a0, data=<optimized out>, n=18446744073709551615) at fileops.c:1392
#2 0x00007f7db43d48b6 in __GI__IO_fread (buf=<optimized out>, size=1, count=18446744073709551615, fp=0x563db9fbb9a0) at iofread.c:42
#3 0x00007f7db15bed79 in fileGetbuf (ctx=0x7f7da525a0e0, buf=0x7f7da525e0a0, size=-1) at php-7.0.5-debug/ext/gd/libgd/gd_io_file.c:91
#4 0x00007f7db15be47e in php_gd_gdGetBuf (buf=0x7f7da525e0a0, size=-1, ctx=0x7f7da525a0e0) at php-7.0.5-debug/ext/gd/libgd/gd_io.c:131
#5 0x00007f7db15bc79c in _gd2ReadChunk (offset=1176, compBuf=0x7f7da525e0a0 '\220' <repeats 40 times>, "\242", <incomplete sequence \354\266>, compSize=-1, chunkBuf=0x7f7da5270000 'A' <repeats 100 times>, chunkLen=0x7fff6af192a8, 
 in=0x7f7da525a0e0) at php-7.0.5-debug/ext/gd/libgd/gd_gd2.c:213
#6 0x00007f7db15bcad8 in php_gd_gdImageCreateFromGd2Ctx (in=0x7f7da525a0e0) at php-7.0.5-debug/ext/gd/libgd/gd_gd2.c:311
#7 0x00007f7db15bc801 in php_gd_gdImageCreateFromGd2 (inFile=0x563db9fbb9a0) at php-7.0.5-debug/ext/gd/libgd/gd_gd2.c:232

Above we can see that it was, as we presumed, the overflow that corrupted dbg->size. To figure out what its value was before it was corrupted, and what code set that value, we just reverse-continue again.

(rr) reverse-continue 
Hardware watchpoint 2: -location dbg->size

Old value = 0
New value = <unreadable>
_raw_syscall () at /home/sean/Documents/Git/rr/rr/src/preload/raw_syscall.S:120
120 callq *32(%rsp)
(rr) bt
#0 _raw_syscall () at /home/sean/Documents/Git/rr/rr/src/preload/raw_syscall.S:120
#1 0x00007f795cc261ab in traced_raw_syscall (call=<optimized out>) at /home/sean/Documents/Git/rr/rr/src/preload/preload.c:282
#2 sys_readlink (call=<optimized out>) at /home/sean/Documents/Git/rr/rr/src/preload/preload.c:1914
#3 syscall_hook_internal (call=0x7fff28911668) at /home/sean/Documents/Git/rr/rr/src/preload/preload.c:2345
#4 0x00007f795cc25b81 in syscall_hook (call=0x7fff28911668) at /home/sean/Documents/Git/rr/rr/src/preload/preload.c:2396
#5 0x00007f795cc29cea in _syscall_hook_trampoline () at /home/sean/Documents/Git/rr/rr/src/preload/syscall_hook.S:170
#6 0x00007f795cc29cfb in _syscall_hook_trampoline_48_3d_01_f0_ff_ff () at /home/sean/Documents/Git/rr/rr/src/preload/syscall_hook.S:221
#7 0x00007f795b42b960 in mmap64 () at ../sysdeps/unix/syscall-template.S:84
#8 0x00007f79587eb2dd in zend_mm_mmap (size=4190208) at /home/sean/Documents/Git/EntomologyPrivate/PHP/CVE-2016-3074/php-7.0.5-debug/Zend/zend_alloc.c:477
#9 0x00007f79587eba73 in zend_mm_chunk_alloc_int (size=2097152, alignment=2097152) at /home/sean/Documents/Git/EntomologyPrivate/PHP/CVE-2016-3074/php-7.0.5-debug/Zend/zend_alloc.c:767
#10 0x00007f79587ede46 in zend_mm_init () at /home/sean/Documents/Git/EntomologyPrivate/PHP/CVE-2016-3074/php-7.0.5-debug/Zend/zend_alloc.c:1828

(rr) f 8
#8 0x00007f79587eb2dd in zend_mm_mmap (size=4190208) at /home/sean/Documents/Git/EntomologyPrivate/PHP/CVE-2016-3074/php-7.0.5-debug/Zend/zend_alloc.c:477
477 ptr = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);

We can see that our hypothesis is correct and that prior to the overflow dbg->size was zero, having being allocated during the initialisation of the memory manager and not used after that. At this point we have a fairly good idea of why the PoC is triggering the crash we’re seeing, and for the purposes of this post we’re done!

All of the above takes a few minutes in total, as reverse execution has a barely noticeable overhead and thus can be integrated into your normal workflow. Higher overhead tools, such as taint trackers, have their place and can offer more automated or more complete answers, but rr finds a sweet-spot between performance and capability that makes it a very interesting tool.

Entirely Unrelated Training Update

There are still seats available for the London/NYC editions of Advanced Tool Development with SMT Solvers, scheduled for this August. These are likely to be the only public editions in the near future, so if you’d like to attend send an email to ASAP.

[1] It doesn’t actually execute in reverse in the sense of walking backwards through the instruction stream. The video linked to above provides some detail on what actually happens.

[2] I can only guess this is the intended operation of the PoC as I never got it to work in its original form.

Fuzzing Language Interpreters Using Regression Tests

At INFILTRATE ’14 I gave a talk on the topic of fuzzing language interpreters. The slides are now available here. The results generated by the system presented and, subsequent, related work, were sufficiently good that my bottleneck quite soon moved from bug discovery to crash triage, which ended up forming the basis for my talk at INFILTRATE ’16.

The question addressed in the talk is ‘How can we fuzz stateful APIs in an efficient manner?’, where ‘efficient’ in this case means we want to reduce the number of wasted tests. For a stateful API, it’s probable that a given API call requires a preceding set of API calls to have set the environment into a particular state before it does anything ‘interesting’. If we don’t make an attempt to set up the environment correctly then we will likely end up with a lot of our tests discarded without exercising new functionality.

As you’ve probably guessed, and as I would assume many other people have concluded before me: a good source of such information is existing code written using the API. In particular, regression tests (and other test types) often provide self-contained examples of how to exercise a particular API call.

The talk itself is in two parts: firstly, a minimal system which works versus ‘easy’ targets, such as PHP and Ruby, and secondly, a more complex system which works versus more difficult targets, such as the JS interpreters found in web browsers.

Given that this talk was two years ago, the ideas in it have evolved somewhat and if you are interested in fuzzing either category of software mentioned above I would offer the following advice:

  1. For the easier targets, compile them with ASAN, extract the tests as mentioned and mutate them using something like radamsa. ASAN plus some batch scripts to automate execution and crash detection is sufficient to reproduce the results mentioned and also to find bugs in the latest versions of these interpreters. The system mentioned in the slides ended up being overkill for these targets.
  2. For the harder targets, a reimplementation of Langfuzz by Holler et al is probably a good first port of call. Also, rather than going down the somewhat insane route of hand-coding Javascript parsing and AST traversal in Go, the esprima and estraverse libraries make the process a lot less painful. My only excuse for not doing this to begin with is along the lines of ‘I’ve just learned Go and I must use it for everything!’. I have too much free time.

On the topic of program analysis: if you are interested in learning about SMT-based analysis engines the early-bird rate for the public editions of ‘Advanced Tool Development with SMT Solvers’ is available for another week. The details, including a syllabus, are here, and if you are interested drop me an email via

Some Early-Stage Work on Statistical Crash Triage

Last week at Infiltrate I presented some early-stage work on crash triage under the title “Automated Root Cause Identification for Crashing Executions“. The slides can be found here, and the presentation notes contain further details in draft form.

A better title for this work would probably have been “Statistical Crash Triage” or possibly something involving the term “predicate synthesis“, as really those things are at the core of what was presented. The main algorithm can be summarised fairly quickly as follows:

  1. Run the target application on all the good inputs and all the bad inputs. Record coverage information.
  2. Use the coverage information to predict what functions are likely relevant to the crash.
  3. Rewrite those functions to insert instrumentation which will record all computed values and other properties.
  4. Rerun the instrumented version of the target application on all the good and bad inputs.
  5. From the recorded state, and predicate templates, synthesise and evaluate predicates over the program’s variables.
  6. Apply a lightweight statistical analysis to the evaluations of these predicates to shake out those relevant to the crash from those that are not.

The actual details are in the slides so I won’t go into that any further. The advantages of this approach are that it isn’t tuned towards one bug type, or class of applications, and simply relies on large amounts of input data and lightweight analyses to discover ‘interesting’ things. Alongside that, the analyses at each stage are parallelisable and so it’s quite simple to scale up. On a reasonably sized target (PHP) the approach is fast enough to fit into a normal workflow.

The most significant downside is that the generality means that if a bug is best described by a very complicated/precise predicate it may not be discovered (although more simple predicates may be, which can help a user manually discover the precise predicate more easily). In terms of the work as a whole there is also a weakness in the limited evaluation so far, but this is something I’m currently in the process of alleviating. In particular I’m working on testing with a wider variety of memory management issues as those pose some unique challenges for the algorithm above.

Besides the analysis algorithm itself, I also want to quickly mention CrashCorpus*. This is a corpus I’m currently working on for the evaluation of crash triage (and related) tools. A significant issue with the academic literature is that the algorithms tend to be tested almost exclusively on toy programs or synthetic bugs. The goal of CrashCorpus is to eliminate that by providing easy to build, easy to run, real-world targets. I’ll have more info on this once I get closer to a public release.

* I’m still building towards a public release of the corpus as it needs more targets before it is truly useful, but if you’d like to contribute drop me an email (sean _at_ All I require is a set of crashing inputs, a set of non-crashing inputs and the source code for the target. I’ll take care of the rest.


Training Dates Confirmed (Plus a Contest for Students)

Good news everyone! The location and dates for the public edition of “Advanced Tool Development with SMT Solvers” have been settled and are as follows:

New York, August 15th-17th
London, August, 22nd-24th

The full details, including pricing can be found here, while the syllabus is here. I’ve been teaching this class since early 2013 to private groups so I’m quite looking forward to a public edition. If you’re interested in bug finding, RE, exploit dev or more general automated program analysis, and want an exercise-driven introduction to SMT-based analyses, then send an email to to reserve your place now. There’s an early-bird discount available until April 29th (UPDATE: deadline extended until May 13th!), and further discounts available for groups, so drop me an email for a quote!

Now, for the other part of this post: there will be a seat at each training* up for grabs for full-time students** who are not otherwise employed. I considered a few different options for ‘challenges’ but, realistically, I would much rather see what fun things people have come up with on their own, than go over responses to a contrived challenge I have come up with. So, we’re going to go with something simple (and hassle-free for everyone involved!): published something awesome in the past 6 months? Great! Send an email with a link to and whomever makes me go “Well that’s f**king awesome!” with the greatest degree of enthusiasm wins. Simple.

Ideally, your entry will have something to do with program analysis, bug finding, exploit dev, RE and such things, but use your imagination here. GitHub repos, blog posts, bug reports, exploits, academic papers, CTF write-ups, and so on, are all fair game.

To enter, send the following to

  • A link to a write-up, paper or code, which has been published in the past 6 months
  • Your name
  • The university/college at which you are enrolled, and the title of the programme***
  • Which location (NYC or London) you can make it to

The contest will run until April 29th (UPDATE: deadline extended until May 13th) and I’ll notify the winners shortly thereafter.

* Just so it’s clear: students will still be responsible for their own travel, accommodation and all other costs except for the cost of the training.

** In order to take the most from the course you will still need to meet the minimum requirements set out in the syllabus. In short: you’ll need a solid grasp of Python, and be comfortable reading plenty of x86 assembly.

*** If you win we’ll also need some proof that you are in fact enrolled in this programme full-time.