PHP Fuzzer

This library implements a fuzzer for PHP, which can be used to find bugs in libraries (particularly parsing libraries) by feeding them “random” inputs. Feedback from edge coverage instrumentation is used to guide the choice of “random” inputs, such that new code paths are visited.

Bug types

The fuzzer by default detects three kinds of bugs:

• Error exceptions are thrown by the fuzzing target. While Exception exceptions are considered a normal result for malformed input, uncaught Error exceptions always indicate a programming error. They are most commonly produced by PHP itself, for example when calling a method on null .
• Thrown notices and warnings (unless they are suppressed). The fuzzer registers an error handler that converts these to Error exceptions.
• Timeouts. If the target runs longer than the specified timeout (default: 3s), it is assumed that the target has gone into an infinite loop. This is realized using pcntl_alarm() and an async signal handler that throws an Error on timeout.

Notably, none of these checks whether the output of the target is correct, they only determine that the target does not misbehave egregiously. One way to check output correctness is to compare two different implementations that are supposed to produce identical results:

$fuzzer->setTarget(function(string $input) use($parser1, $parser2) {

    $result1 = $parser1->parse($input);

    $result2 = $parser2->parse($input);

    if ($result1 != $result2) {

        throw new Error('Results do not match!');

    }

});

Technical

Many of the technical details of this fuzzer are based on libFuzzer from the LLVM project. The following describes some of the implementation details.

Instrumentation

To work efficiently, fuzzing requires feedback regarding the code-paths that were executed while testing a particular fuzzing input. This coverage feedback is collected by “instrumenting” the fuzzing target. The interceptor library is used to transform the code of all included files on the fly. The PHP-Parser library is used to parse the code and find all the places where additional instrumentation code needs to be inserted.

Inside every basic block, the following code is inserted, where BLOCK_INDEX is a unique, per-block integer:

This assumes that the block index is at most 28-bit large and counts the number of (prev_block, cur_block) pairs that are observed during execution. The generated code is unfortunately fairly expensive, due to the need to deal with uninitialized edge counts, and the use of static properties. In the future, it would be possible to create a PHP extension that can collect the coverage feedback much more efficiently.

In some cases, basic blocks are part of expressions, in which case we cannot easily insert additional code. In these cases we instead insert a call to a method that contains the above code:

In the future, it would be beneficial to also instrument comparisons, such that we can automatically determine dictionary entries from comparisons like $foo == “SOME_STRING”.

Features

Fuzzing inputs are considered “interesting” if they contain new features that have not been observed with other inputs that are already part of the corpus. This library uses course-grained edge hit counts as features:

ft = (approx_hits << 56) | (prev_block << 28) | cur_block

The approximate hit count reduces the actual hit count to 8 categories (based on AFL):

0: 0 hits
1: 1 hit
2: 2 hits
3: 3 hits
4: 4-7 hits
5: 8-15 hits
6: 16-127 hits
7: >=128 hits

As such, each input is associated with a set of integers representing features. Additionally, it has a set of “unique features”, which are features not seen in any other corpus inputs at the time the input was tested.

If an input has unique features, then it is added to the corpus (NEW). If an input B was created by mutating an input A, but input B is shorter and has all the unique features of input A, then A is replaced by B in the corpus (REDUCE).

Mutation

On each iteration, a random input from the current corpus is chosen and then mutated using a sequence of mutators. The following mutators (taken from libFuzzer) are currently implemented:

• EraseBytes: Remove a number of bytes.
• InsertByte: Insert a new random byte.
• InsertRepeatedBytes: Insert a random byte repeated multiple times.
• ChangeByte: Replace a byte with a random byte.
• ChangeBit: Flip a single bit.
• ShuffleBytes: Shuffle a small substring.
• ChangeASCIIInt: Change an ASCII integer by incrementing/decrementing/doubling/halving.
• ChangeBinInt: Change a binary integer by adding a small random amount.
• CopyPart: Copy part of the string into another part, either by overwriting or inserting.
• CrossOver: Cross over with another corpus entry with multiple strategies.
• AddWordFromManualDictionary: Insert or overwrite with a word from the dictionary (if any).

A mutation is subject to a maximum length constrained. While an overall maximum length can be specified by the target (setMaxLength()), the fuzzer also performs automatic length control (–len-control-factor). The maximum length is initially set to a very low value and then increased by log(maxlen) whenever no action (NEW or REDUCE) has been taken for the last len_control_factor * log(maxlen) runs.

The higher the length control factor, the more aggressively the fuzzer will explore short inputs before allowing longer inputs. This significantly reduces the size of the generated corpus but makes initial exploration slower.

Changelog v0.0.7 releases

• Print correct entry during crash minimization
• Support mutation depth during minimization

Download && Use