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 ./get.sh && ./build.sh && ./fuzz.sh 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 build.sh 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 fuzz.sh 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 vertex.re/training 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 contact@vertex.re to book a place, or check out vertex.re/training 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/ld-linux-x86-64.so.2
(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/ld-linux-x86-64.so.2
(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/libphp7.so"
[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 contact@vertex.re 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 contact@vertex.re.

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_ vertex.re). 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 contact@vertex.re 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 contact@vertex.re 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 contact@vertex.re:

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


Public Edition of “Advanced Tool Development with SMT Solvers” Coming Soon!

SMT solvers are an interesting, and powerful, technology and can be leveraged as a reasoning engine in a variety of solutions. The most popular uses being symbolic execution systems, like KLEE and angr, and concolic execution/whitebox fuzzing systems, such as SAGE. Due to the nature of the technology, and the overwhelming number of academic publications on the topic, it can take a while for people to get to grips with the underlying theory, and even longer to figure out the strengths and limitations of such tools in practice.

For the above reasons, since 2013 I have taught the “Advanced Tool Development with SMT Solvers” course to students from a variety of backgrounds (you can see a high level syllabus here). It’s a fun course to teach as it’s a bit different from your usual info-sec training, and the material is constantly evolving as program analysis research progresses. While the material regularly changes, my goals for the class have remained the same: after the class students should be able to perform informed cost-benefit analysis when considering integrating SMT-backed technologies into their workflow, to use and to extend publicly available SMT-based tools, to begin to develop their own SMT-based systems, and to keep up with the published state of the art.

On to the point of this post: Bar one public version in Iceland in 2013, I have exclusively hosted private versions of this class. To do so requires organisations to have at least 6 individuals interested in the course and obviously that isn’t always possible. As a result I’ve had a number of requests for a public edition, which until now I haven’t got around to following up on! Over the summer/early fall I intend to host one or more public editions and I’m currently soliciting feedback as to where they will be. If you are interested, there is a poll here where you can let me know your location of choice (at the moment London and New York seem to be the most popular).

I’ll make a decision on the location in the next few weeks and if you’d like to be sent the details email contact@vertex.re or follow me on Twitter (@seanhn).

(If you do happen to have 6 or more people from your organisation interested in taking the course it is likely to be significantly more cost effective to organise a private, on-site training at your location. To do so email contact@vertex.re.)