Lately I've been working on fuzzing the PHP interpreter. I've explored many tools and techniques (AFL, LibFuzzer, even a custom fuzz engine), but most recently I decided to give Domato a try. For those not aware, Domato is a grammar-based DOM fuzzer, built to tease complex bugs out of complex code-bases. It was originally designed with browsers in mind, but I figured I might be able to re-purpose it for fuzzing the PHP interpreter.
Context-free Grammar
In order to use Domato, one must first describe the language using a context-free grammar. A CFG is simply a set of rules which define how a language is constructed. For instance, if our language was composed of sentences in the form...
[name] has [number] [adjective] [noun]s. [name]'s [noun] is very [adjective]. I want to purchase [number] [adjective] [noun]s.
...and each of those variables could take several forms, such as...
Names: alice, bob, eve Numbers: 1, 10, 100 Adjectives: green, large, expensive Nouns: car, hat, laptop
...then our context free grammar might look like...
<name> = alice <name> = bob <name> = eve <number> = 1 <number> = 10 <number> = 100 <adjective> = green <adjective> = large <adjective> = expensive <noun> = car <noun> = hat <noun> = laptop <sentence> = <name> has <number> <adjective> <noun>s. <sentence> = <name>'s <noun> is very <adjective>. <sentence> = I want to purchase <number> <adjective> <noun>s.
Domato then uses our context free grammar to generate random combinations which conform to the rules of the language. For example...
eve has 1 expensive laptops. alice's hat is very green. I want to purchase 100 expensive cars. I want to purchase 10 large laptops. bob has 100 expensive cars. eve has 100 green laptops. I want to purchase 100 large laptops. bob has 1 large cars. I want to purchase 1 large cars. I want to purchase 1 large hats. bob's laptop is very expensive.
As you can imagine, by breaking each rule down into many more sub-rules, we can begin to define much more complex language, well beyond a simple search/replace. In practice, Domato also provides some built-in functionality for limiting recursion, and generating basic types (int, char, string, etc). For instance, consider the following Domato grammar, which generates pseudo-code...
!max_recursion 10
<varname> = var<int min=0 max=10>
<vardef> = int <varname> = <int>
<vardef> = char <varname> = '<char min=32 max=127>'
<condition> = <varname> == <varname>
<condition> = <varname> == <int>
<condition> = <varname> != <int>
<statement> = <vardef>;
<statement> = if (<condition>) { <statement> } else { <statement> }
<statement> = while (<condition>) { <statement> }
<statement> = <statement>; <statement>;
<examplefuzz> = <statement>
!begin lines
<examplefuzz>
!end lines
Feeding this into Domato produces the following...
if (var0 == var5) { int var5 = 915941154; } else { int var3 = 1848395349; }; if (var3 == -121615885) { int var7 = 1962369640;; int var1 = 196553597;;; int var6 = -263472135;; } else { int var2 == 563276937; };
while (var9 = var8) { while (var0 == -2029947247) { int var7 = 1879609559; } }; char var0 = '';;
char var2 = '/';
char var3 = 'P';
if (var8 == var1) { int var7 = -306701547; } else { while (var3 == 868601407) { while (var0 == -1328592927) { char var10 = '^'; }; char var8 = 'L';;; int var9 = -1345514425;; char var5 = 'b';;; } }
int var8 = 882574440;
if (var8 == var9) { int var7 = 1369926086; } else { if (var9 != -442302103) { if (var3 != 386704757) { while (var4 != -264413007) { char var6 = 'C'; } } else { int var8 = 289431268; } } else { char var10 = '~'; } }
char var5 = '+';
if (var9 == 1521038703) { char var2 = '&'; } else { int var7 = -215672117; }
while (var9 == var0) { char var9 = 'X';; int var7 = -1463788903;; }; if (var8 == var7) { int var10 = 1664850687;; char var6 = 'f';; } else { while (var5 == -187795546) { int var3 = -1287471401; } };
This is perfectly suited for fuzzing an interpreter, because each sample is both unusual, and still guaranteed to be syntactically valid! :)
Enumerating the Attack Surface
The next step then is to describe the PHP language as a CFG. If you're interested in seeing a complete CFG, download the PHP source code, and look in Zend/zend_language_parser.y. However I was more interested in fuzzing specific code-patterns. So, I implemented my CFG such that it only generated calls to built-in functions and class methods using "fuzzy" parameters. For this, we need a list of functions, methods, and their arguments.There are two ways to obtain this data. The simplest is to use PHP's built in Reflection classes to iterate over all defined functions and classes, building a list. The following code demonstrates this for all internal PHP functions...
<?php
foreach (get_defined_functions()["internal"] as $f) {
$r = new ReflectionFunction($f);
$params = array();
foreach ($r->getParameters() as $p) {
$params[] = $p->getName();
}
echo "$f(" . implode(", ", $params) . ");\n";
}
?>
This produces something like...
andrew@thinkpad /tmp % php lang.php zend_version(); func_num_args(); func_get_arg(arg_num); func_get_args(); strlen(str); strcmp(str1, str2); strncmp(str1, str2, len); strcasecmp(str1, str2); strncasecmp(str1, str2, len); each(arr); error_reporting(new_error_level); define(constant_name, value, case_insensitive); defined(constant_name); get_class(object); ... etc ...
The problem with this however, is that this list contains no type information. Yes, the ReflectionParameter class does contain a getType method, however it doesn't seem to work at the moment for the vast majority of functions. :( Maybe this is a bug? Hard to say. Regardless, having type information will make our fuzzing efforts significantly more effective, so it's worth the time investment to find another way to get that data.
The less-elegant way of obtaining this data is to scrape the PHP documentation and parse out what we need. Luckily, PHP's documentation is generally quite good, and can be downloaded as a single gzipped HTML document here. After a few arduous hours writing regular expressions, I was able to parse that into a usable list of functions, methods, and argument types. I'll leave this as an exercise to the reader, but the final product (in CFG form) looked like this...
<functioncall> = abs(<fuzzmixed>) <functioncall> = acos(<fuzzfloat>) <functioncall> = acosh(<fuzzfloat>) <functioncall> = addcslashes(<fuzzstring>, <fuzzstring>) <functioncall> = addslashes(<fuzzstring>) <functioncall> = array_change_key_case(<fuzzarray>, <fuzzint>) <functioncall> = array_chunk(<fuzzarray>, <fuzzint>, <fuzzbool>) ... snip snip snip ... <methodcall> = <obj_DateInterval>->createFromDateString(<fuzzstring>) <methodcall> = <obj_DateInterval>->format(<fuzzstring>) <methodcall> = <obj_DatePeriod>->getDateInterval() <methodcall> = <obj_DatePeriod>->getEndDate() <methodcall> = <obj_DatePeriod>->getRecurrences() <methodcall> = <obj_DatePeriod>->getStartDate() <methodcall> = <obj_DateTime>->add(<fuzzDateInterval>) <methodcall> = <obj_DateTime>->createFromFormat(<fuzzstring>, <fuzzstring>, <fuzzDateTimeZone>) ... snip snip snip ... <obj_DateInterval> = $vars["DateInterval"] <obj_DatePeriod> = $vars["DatePeriod"] <obj_DateTime> = $vars["DateTime"] <obj_DateTimeImmutable> = $vars["DateTimeImmutable"] <obj_DateTimeZone> = $vars["DateTimeZone"] <obj_Directory> = $vars["Directory"] <obj_DOMAttr> = $vars["DOMAttr"] ... etc ...
Setting up Domato
In order for Domato to use our grammar, we'll also need to define some basic components such as <fuzzint>, <fuzzstring>, and <fuzzarray>. We will set them to potentially dangerous values, such as INT_MAX, -1, NULL, "AAA....AAA", array(array(array())), etc. These will be fed into our function and method calls. Additionally, we'll tell Domato to wrap each line in try/catch blocks, so that exceptions and errors won't be fatal. After quite a lot of tweaking and tuning, my configuration ended up looking a bit like this...!lineguard try { try { <line> } catch (Exception $e) { } } catch(Error $e) { }
<fuzzvoid> =
<fuzzbool> = true
<fuzzbool> = false
<fuzzinteger> = <fuzzint>
<fuzzint> = 0
<fuzzint> = 1
<fuzzint> = -1
<fuzzint> = 1000000
<fuzzint> = <largeint>
<fuzzint> = -<largeint>
<largeint> = 2147483647
<largeint> = 2147483648
<largeint> = 4294967295
<largeint> = 4294967296
<fuzzfloat> = 2.2250738585072011e-308
<fuzznumber> = <fuzzint>
<fuzznumber> = <fuzzfloat>
<fuzzstring> = str_repeat("A", 0x100)
<fuzzstring> = implode(array_map(function($c) {return "\\x" . str_pad(dechex($c), 2, "0");}, range(0, 255)))
<fuzzstring> = str_repeat("%s%x%n", 0x100)
<repeatcount> = 257
<repeatcount> = 65537
<array> = range(0, 10)
<array> = array("a" => 1, "b" => "2", "c" => 3.0)
<fuzzarray> = <array>
<fuzzmixed> = <fuzzint>
<fuzzmixed> = <fuzzfloat>
<fuzzmixed> = <fuzzbool>
<fuzzmixed> = <fuzzstring>
<fuzzmixed> = <fuzzarray>
!include php/phplang.txt
<fuzzline> = <methodcall>;
<fuzzline> = <functioncall>;
!begin lines
<fuzzline>
!end lines
We also need to define a template which the grammar will be applied to. The template will set up the environment, instantiate any objects that might later be used, and then run each fuzz line. My template looked a bit like this...
<?php $vars = array( "stdClass" => new stdClass(), "Exception" => new Exception(), "ErrorException" => new ErrorException(), "Error" => new Error(), "CompileError" => new CompileError(), "ParseError" => new ParseError(), "TypeError" => new TypeError(), ... etc ... ); <phpfuzz> ?>
The last step is to copy and modify Domato's generator.py file. I found that simply making the following changes was sufficient...
- Lines 55 and 62: change the root element to '<phpfuzz>'
- Line 78: reference my own 'template.php'
- Line 83: reference my own grammar in 'php.txt'
- Line 134: change the output name and extension to '<uuid>.php'
We should then be able to generate valid fuzz input!
andrew@thinkpad ~/domato/php % python generator.py /dev/stdout
Writing a sample to /dev/stdout
<?php
$vars = array(
"stdClass" => new stdClass(),
"Exception" => new Exception(),
"ErrorException" => new ErrorException(),
"Error" => new Error(),
"CompileError" => new CompileError(),
"ParseError" => new ParseError(),
"TypeError" => new TypeError(),
... etc ...
);
try { try { $vars["SplPriorityQueue"]->insert(false, array("a" => 1, "b" => "2", "c" => 3.0)); } catch (Exception $e) { } } catch(Error $e) { }
try { try { filter_has_var(1000, str_repeat("%s%x%n", 0x100)); } catch (Exception $e) { } } catch(Error $e) { }
try { try { posix_access(implode(array_map(function($c) {return "\\x" . str_pad(dechex($c), 2, "0");}, range(0, 255))), -1); } catch (Exception $e) { } } catch(Error $e) { }
try { try { rand(0, 0); } catch (Exception $e) { } } catch(Error $e) { }
try { try { fputcsv(fopen("/dev/null", "r"), array("a" => 1, "b" => "2", "c" => 3.0), str_repeat(chr(135), 65), str_repeat(chr(193), 17) + str_repeat(chr(21), 65537), str_repeat("A", 0x100)); } catch (Exception $e) { } } catch(Error $e) { }
try { try { $vars["ReflectionMethod"]->isAbstract(); } catch (Exception $e) { } } catch(Error $e) { }
try { try { $vars["DOMProcessingInstruction"]->__construct(str_repeat(chr(122), 17) + str_repeat(chr(49), 65537) + str_repeat(chr(235), 257), str_repeat(chr(138), 65) + str_repeat(chr(45), 4097) + str_repeat(chr(135), 65)); } catch (Exception $e) { } } catch(Error $e) { }
try { try { utf8_encode(str_repeat("A", 0x100)); } catch (Exception $e) { } } catch(Error $e) { }
try { try { $vars["MultipleIterator"]->current(); } catch (Exception $e) { } } catch(Error $e) { }
try { try { dl(str_repeat("A", 0x100)); } catch (Exception $e) { } } catch(Error $e) { }
try { try { ignore_user_abort(true); } catch (Exception $e) { } } catch(Error $e) { }
Preparing to Fuzz
Now that we have data to fuzz with, we need to build PHP in a way that maximizes our chances of detecting any kind of memory corruption. For this, I strongly recommend the LLVM Address Sanitizer (ASAN), which will detect any invalid memory access, even if it would not immediately result in a crash.To build PHP with ASAN, download the latest version of the source code here, and run the following commands...
./configure CFLAGS="-fsanitize=address -ggdb" CXXFLAGS="-fsanitize=address -ggdb" LDFLAGS="-fsanitize=address" make make install
Before leaving a fuzzer to run unattended, it's also a good idea to try to eliminate any conditions that hold up the process unnecessarily. For instance, like most languages PHP has a function called sleep(), which takes an integer argument and simply waits that many seconds before continuing. Calling this function with large fuzz-values such as INT_MAX will quickly tie up even a large fuzz cluster.
There are also functions which could cause the process to "crash" legitimately, such as posix_kill(), or posix_setrlimit(). We may wish to remove these from our test corpus in order to reduce the number of false positives.
Finally, since many of the functions and classes listed in the PHP documentation are not actually available in the core install (rather, from extensions) we may wish to remove some of them from our corpus to avoid wasting time calling non-existent code.
Finally, after some experimentation, I settled on the following list...
$class_blacklist = array( // Can't actually instantiate "Closure", "Generator", "HashContext", "RecursiveIteratorIterator", "IteratorIterator", "FilterIterator", "RecursiveFilterIterator", "CallbackFilterIterator", "RecursiveCallbackFilterIterator", "ParentIterator", "LimitIterator", "CachingIterator", "RecursiveCachingIterator", "NoRewindIterator", "AppendIterator", "InfiniteIterator", "RegexIterator", "RecursiveRegexIterator", "EmptyIterator", "RecursiveTreeIterator", "ArrayObject", "ArrayIterator", "RecursiveArrayIterator", "SplFileInfo", "DirectoryIterator", "FilesystemIterator", "RecursiveDirectoryIterator", "GlobIterator", ); $function_blacklist = array( "exit", // false positives "readline", // pauses "readline_callback_handler_install", // pauses "syslog", // spams syslog "sleep", // pauses "usleep", // pauses "time_sleep_until", // pauses "time_nanosleep", // pauses "pcntl_wait", // pauses "pcntl_waitstatus", // pauses "pcntl_waitpid", // pauses "pcntl_sigwaitinfo", // pauses "pcntl_sigtimedwait", // pauses "stream_socket_recvfrom", // pauses "posix_kill", // ends own process "ereg", // cpu dos "eregi", // cpu dos "eregi_replace", // cpu dos "ereg_replace", // cpu dos "similar_text", // cpu dos "snmpwalk", // cpu dos "snmpwalkoid", // cpu dos "snmpget", // cpu dos "split", // cpu dos "spliti", // cpu dos "snmpgetnext", // cpu dos "mcrypt_create_iv", // cpu dos "gmp_fact", // cpu dos "posix_setrlimit" );
Although one machine could both generate and fuzz the samples alone, I opted for a small cluster of machines to speed up the process. I used Proxmox, running on an Intel NUC, with 10 Debian VM's whose jobs were the following...
- Node 0: Sample generator, hosting an NFS share.
- Nodes 1-8: Fuzz nodes, pulling samples from the NFS share to test.
- Node 9: Triage node: Binning crashing samples based on crash metrics.
I created simple, crude shell scripts to run on each of these to carry out those duties. Those scripts can be found in the github repo linked above.
Finding Crashes
After only a short period of time, my work paid off! Within minutes the fuzzer had generated several crashing samples, and overnight it created more than 2,000.By binning the crashes according to the instruction address they crashed on, I was able to determine that all 2,000 were the result of only 3 unique bugs. Of these, 2 were clearly unexploitable (both OOM errors due to stack exhaustion), however the last appeared to be a use-after-free! Here is the minimized crashing sample...
<?php
$x = array(new XMLWriter());
$x[0]->openUri("/tmp/a");
$x[0]->startComment();
?>
This bug has since been fixed in bug#79029 (this commit), and should be included in the next release. In the next few blog posts I will discuss the process tracing it back to the root cause, abusing it to achieve arbitrary code execution, and a neat little shellcode trick that I discovered along the way.
Stay tuned! :)
