Breaking PHP’s Garbage Collection and Unserialize

Hey PHP, those variables look like garbage don’t you agree? No? Well look again…

tl;dr:

We have found two use-after-free vulnerabilities in PHP’s garbage collection algorithm:

• One vulnerability affecting all PHP 5 versions >= 5.3 (fixed in PHP 5.6.23).
• One vulnerability affecting all PHP versions >= 5.3 including all PHP 7 versions (fixed in PHP 5.6.23 and PHP 7.0.8).
• Those vulnerabilities could also be remotely exploited over PHP’s unserialize function. In particular, they were used to get RCE on pornhub.com, helped us to earn $20,000 and were each awarded with $1,000 by the Internet Bug Bounty committee at Hackerone.

Credits:

• Many thanks go out to Dario Weißer for writing an unserialize fuzzer and helping to identify initial bugs in unserialize!

In the context of auditing Pornhub we have identified two critical flaws in PHP’s garbage collection algorithm (c.f. How we broke PHP, hacked Pornhub and earned $20,000). In particular, two critical use-after-free vulnerabilities were discovered when PHP’s garbage collection algorithm interacts with other specific PHP objects. Those vulnerabilities have wide reaching effects like allowing the exploitation of unserialize to gain remote code execution on a target system and will be discussed in this article.

After fuzzing unserialize and analyzing interesting issues we could extract two proof of concepts for use-after-free vulnerabilities. Please read Dario’s write-up about fuzzing unserialize to see how we came up with those. One of the examples was:

For this example you would normally expect an output like:

Nevertheless, once executed we can see that the outer array (referenced by $outer_array) is freed and its zval is overwritten by the zval of $filler2 resulting in the output “bbbb” instead. This leaves the following questions:

• Why is the outer array freed at all?
• What is gc_collect_cycles() doing and is a manual call really necessary? This would be very inconvenient for remote exploitation as many scripts and setups don’t invoke this function at all.
• Even if we are able to invoke it during unserialization. Will this example still work in an unserialization context?

All the magic seems to happen in gc_collect_cycles which invokes PHP’s garbage collection. A better understanding of it was required to unlock the mysteries of the given example.

PHP’s Garbage Collection

In early PHP versions there was no way to deal with circular reference memory leaks. Thus, a garbage collection (GC) algorithm was introduced in PHP 5.3.0 (c.f. PHP manual – Collecting Cycles). The garbage collection is active by default and can be triggered by configuring the php.ini setting zend.enable_gc accordingly.

• Please note:
  At this point some basic knowledge about PHP internals, PHP’s memory management and terms like “zval” and “reference counting” is assumed. If any of those terms are unfamiliar to you, you should read the following basics: PHP Internals Book – Basic zval structure and PHP Internals Book – Memory managment first.

Cyclic References

To understand what a circular reference is just consider the following example:

Since $test references itself its reference count is 2. Thus, even if you unset $test its reference count would become 1 resulting in memory that wouldn’t be freed anymore: a memory leak. To tackle this problem the PHP developers implemented a GC algorithm according to the paper “Concurrent Cycle Collection in Reference Counted Systems” by IBM.

Triggering the GC

The main implementation can be found in “Zend/zend_gc.c“. Every time a zval is destructed e.g. when unset is called on this zval the GC algorithm gets involved and checks if it is an array or object. All other (primitive) data types can’t contain circular references. This check is realized by calling the gc_zval_possible_root function. Any such potential zval is called root and is added to a list called gc_root_buffer.

The above steps are then repeated until either

• gc_collect_cycles() is called manually.
• The garbage storage space is about to be exceeded. In particular, this means that 10,000 zvals have been stored in the root buffer and a new root is about to be added. The number 10,000 is the default limit defined by GC_ROOT_BUFFER_MAX_ENTRIES in the head section of “Zend/zend_gc.c“. The 10,001 zval will invoke gc_zval_possible_root again which in turn will execute a call to gc_collect_cycles to process and flush the current buffer so that new elements can be stored again.

Graph Marking Algorithm for Cycle Collection

The GC algorithm is a graph marking algorithm which is applied on the following graph structure. The graph nodes represent actual zvals like arrays, strings or objects. The edges represent connections/references between those zvals.
Further, this algorithm mainly uses the following colors to mark nodes:

• Purple:
  Potential garbage cycle root. This node could be the root of a circular reference cycle. All nodes that are initially added to the garbage buffer are marked purple.
• Grey:
  Potential member of a garbage cycle. This node could be part of a circular reference cycle.
• White:
  Member of a garbage cycle. This node should be freed once the algorithm terminates.
• Black:
  In use or already freed. This node shouldn’t be freed under any circumstance.

To see what this algorithm does in detail we will now take a look at its implementation. The overall garbage collection is executed in gc_collect_cycles:

This function takes care of the following four simplified steps:

1. gc_mark_roots(TSRMLS_C):
   Apply zval_mark_grey to all purple marked elements in gc_root_buffer. Where zval_mark_grey does the following things with a given zval:
   1. Return if the given zval is already marked grey.
   2. Mark this zval grey.
   3. Retrieve all childrens’ zvals (only if the given zval is an array or object).
   4. Decrement the reference count of every child’s zval by 1 and call zval_mark_grey on it.

   Overall, this step marks all from a root zval reachable other zvals grey and decrements the reference counters for any such encountered zval.

2. gc_scan_roots(TSRMLS_C):
   Apply zval_scan (unfortunately it isn’t called zval_mark_white) to all elements in gc_root_buffer. Where zval_scan does the following things with a given zval:
   1. Return if the given zval has another color than grey.
   2. If its reference count is greater than zero call zval_scan_black (unfortunately it isn’t called zval_mark_black) on it. Where zval_scan_black basically reverts all effects on reference counters done by zval_mark_grey before and marks all reachable zvals black.
   3. Else mark the given zval white, retrieve all childrens’ zvals (only if the given zval is an array or object) and call zval_scan on them.

   Overall, this step determines which grey marked zvals should now be marked black or white.

3. gc_collect_roots(TSRMLS_C):
   This step collects all white marked zvals and restores their reference counters. In addition, they are added to the list gc_zval_to_free which is the equivalent of gc_free_list.
4. Finally, free all elements contained in gc_free_list i.e. free all elements that have been marked white.

Applying this algorithm will hence identify and free all parts of circular references by marking them white, collecting them later on and finally freeing them. A closer analysis of the implementation shows the following conflict potential:

• In step 1.4 zval_mark_grey decrements the reference counters of all children before actually checking if they were already marked grey before.
• Since the zvals’ reference counters are temporarily decremented, any side effects like checks against those weakened reference counters or other manipulations can have disastrous consequences.

Analyzing the POC

With our now obtained knowledge regarding the GC implementation we can analyze the found vulnerability example again. We recall the following serialized string:

While using gdb we can use a standard PHP 5.6 .gdbinit and an additional custom routine to dump the GC buffer’s content.

Further, we can now set a breakpoint on gc_mark_roots and gc_scan_roots to see the state of all relevant reference counters.

Our goal is to find an answer to the following question: why is the outer array freed at all? We will load the php process into gdb, set all breakpoints as discussed and execute our example script.

Here we can see that once unserialize has finished both arrays (inner_array and outer_array) have been added to the GC buffer. If we continue and break at gc_scan_roots we will get the following reference counters:

At this point we can see that gc_mark_roots did indeed decrement all reference counters to zero. Consequently, those nodes can be marked white in the following steps and be freed later on. However, this leaves the question: why did the reference counters become zero in the first place?

Debugging unexpected behavior

Let’s go step by step through gc_mark_roots or zval_mark_grey respectively to see what happens in detail.

1. zval_mark_grey will be called on outer_array (recall that outer_array was added to the GC buffer).
2. This will mark outer_array grey and retrieve all its children. In this case outer_array has only one child:
   “object(ArrayObject) #1” (refcount=1).
3. The reference count of this child or ArrayObject respectively will be decremented resulting in:
   “object(ArrayObject) #1” (refcount=0).
4. zval_mark_grey will be called on this ArrayObject.
5. This object will be marked grey and all its children will be retrieved. The children are: a reference to inner_array and a reference to outer_array.
6. The reference counter of both children i.e. both referenced zvals will be decremented resulting in:
   “outer_array” (refcount=1) and “inner_array” (refcount=1).
7. zval_mark_grey will now be called on outer_array with no effect since outer_array is already marked grey (it was already visited in step 2).
8. zval_mark_grey will now be called on inner_array. It will be marked grey and all its children will be retrieved. The children are the same as in step 5.
9. The reference counter of both children will be decremented again resulting in:
   “outer_array” (refcount=0) and “inner_array” (refcount=0).
10. Finally, there are no more zvals to visit and zval_mark_grey will terminate.

After all, the references contained in inner_array or ArrayObject respectively got decremented twice! This is definitively unexpected behavior since each reference should be decremented exactly once. In particular, step 8 shouldn’t be executed at all since those elements have already been visited by the marking algorithm in step 6.

• Please note:
  The marking algorithm makes the assumption that each element can only have exactly one parent element. Apparently, this assumption seems to be violated at this point.

So why is it that an element can be returned as a child of two different parents in our example?

One child two different parents?

To find an answer we need to take a look at how children zvals are retrieved from object parents:

As can be seen, in case the passed zval is an object the function will call the object specific get_gc handler. This handler is supposed to return a hash table with all children. After further debugging I found out that this will lead to a call to spl_array_get_properties:

Altogether, this will return the hash table of the internal ArrayObject array. The mistake here, however, is that this hash table is used in two different contexts:

1. When the algorithm tries to access the children of our ArrayObject zval.
2. When the algorithm tries to access the children of inner_array.

As you might have guessed, something is missing in the first step: since returning the hash table of inner_array is pretty much the same as visiting inner_array it should also be marked grey in the first step so that it can’t be visited in step 2 again!

Thus, the next question was: why is inner_array not marked grey in step 1? Once again we can take a closer look on how zval_mark_grey retrieves the children of an object parent:

This method is supposed to call the object’s garbage collection function. A garbage collection function is supposed to look similar to this example:

As you can see the returned hash table is supposed to contain only the object’s own properties. There is also the table zval parameter which is passed by reference and used as a second “return parameter”. This zval is supposed to contain all zvals that are referenced in other contexts by the object. One example could be all objects/zvals that can be stored in a SplObjectStorage.

For our specific ArrayObject scenario we would expect this table zval to contain a reference to inner_array. So why is spl_array_get_properties called instead of spl_array_get_gc?

A missing GC function and its consequences

The answer is relatively simple: spl_array_get_gc does simply not exist!

The PHP developers forgot to implement a garbage collection function for ArrayObjects. Nevertheless, this still doesn’t explain why spl_array_get_properties is called at all. To answer this circumstance we can take a look at how objects are initialized in general:

The standard behavior of dealing with a missing garbage collection function is to rely on the object’s own get_properties method if defined.

Puh, we have finally found an answer to our first question. The main reason for this vulnerability is a missing garbage collection function for ArrayObjects.

Strangely enough this function was introduced in PHP 7.1.0 alpha2 almost right from the start. Hence, only all versions of PHP >= 5.3 and PHP < 7 were affected. Unfortunately, as we will see in the next sections this bug can’t be triggered during unserialization without adjustments. Thus, further effort was necessary to come up with tricks to pave the way for remote exploitation. As of now we will refer to this vulnerability simply as “double decrement bug“. This vulnerability was reported here: PHP Bug – ID 72433 – CVE-2016-5771

Resolving Remote Exploitation Issues

At this point we still need to answer two of our three initial questions. Let’s start with: is a manual call to gc_collect_cycles really necessary?

Triggering the GC during Unserialization

I was very doubtful if we can trigger the garbage collection in the first place. However, as discussed before there is a way to automatically invoke the garbage collection process which is to exceed the garbage collection buffer with potential root elements. In particular, I found the following simple trick.

Once you inspect the above in gdb you can see that gc_collect_cycles is indeed called. This trick works only because unserialize allows to pass the same index over and over again (in this example index 0). Once you are reusing an index of an array, the reference counter of the old element has to be decremented. In particular, the unserialization process will call zend_hash_update which will in turn call the destructor of the old element.

Every time a zval is destructed […] the GC algorithm gets involved […].

This means that all of the created arrays will start to fill up the garbage buffer until its space is exceeded resulting in a call to gc_collect_cycles.

Those are awesome news! The target system is not required to manually invoke the garbage collection procedure. Unfortunately, new problems arose and things got even tougher.

Unserialize is a tough opponent

The remaining question at this point was: even if we are able to invoke the GC during unserialize. Will the double decrement bug still work in an unserialization context?

After testing it quickly turned out that the answer was no. This is due to the circumstance that the reference counters of all elements are higher during unserialization than after it has finished.

In particular, unserialize keeps track of all unserialized elements to allow setting references. All of those entries are stored in the list var_hash. Once unserialize is about to finish it will destruct those entries in the function var_destroy.

To see the problem of high reference counters you can just consider the following example:

The reference counter of the 1337 integer zval is 2 after unserialize has finished. Once we set a breakpoint right before unserialize terminates (e.g. at a call to var_destroy which is called before returning) and dump the contents of var_hash we will see the following reference counts:

The double decrement bug that we analyzed before allows us to decrement the reference count of any selected element twice. However, as we can see according to these numbers we have to “pay” a reference count increase of 2 for every additional reference we set on any element.

Lying sleepless in my bed at 4 a.m. and thinking about all these problems I finally remembered one important thing: the unserialization function of ArrayObject accepts a reference to another array for initialization purposes. This means that once you unserialize an ArrayObject you can just refer to any array that was already unserialized before. Further, this allows you to decrement all entries of a whole specific hash table twice. Consider the following setup:

• We are given a target zval X that is supposed to be freed.
• We create an array Y that will contain several references to the zval X:
  array(ref_to_X, ref_to_X, […], ref_to_X)
• We create an ArrayObject that will be initialized with the contents of array Y. Thus, it will return all children of array Y once visited by the GC marking algorithm.

By using this setup we can manipulate the marking algorithm to visit all references in the array Y twice. However, as stated before, creating a reference will lead to a reference counter increase of 2 during the unserialization process. Visiting such a reference twice will thus have the same effect as leaving out the reference in the first place. The real trick occurs once we add the following ingredient to our setup:

• We create an additional ArrayObject with the same setup as the last one.

Once the marking algorithm will visit this second ArrayObject it will begin to decrement all references in array Y for the third time. We now have a way to create a negative reference counter delta and especially to null the reference count of any target zval!

Since those ArrayObjects are used to decrement target reference counters I will simply refer to them as DecrementorObjects as of now.

Unfortunately, even after being able to null the reference counter of any target zval the GC algorithm still didn’t free those…

Destroying Reference Counter Decrementation Evidence

After a lot of debugging I have found the core issue with the previous setup. I assumed that once a node is marked white it will be definitively freed. However, it turned out that even once a node was marked white it could be later on marked black again.
Consider what happens to our setup in detail:

• Once gc_mark_roots and zval_mark_grey have finished the reference count of our target zval is 0.
• Next, the GC will execute gc_scan_roots to determine which zvals can be marked white and which ones should be marked black.
  In this step our target zval will be marked white (since its reference count is 0).
• Once this function visits our DecrementorObjects it will detect that their own reference count is greater than 0 and mark them including all their children black. Unfortunately, our target zval is also a child of our DecremtorObjects. Thus, our target zval will be marked black again.

Altogether, we somehow have to get rid of the decrementation “evidence” here. In particular, we have to ensure that the reference counters of our DecremtorObjects become 0 after zval_mark_grey is done, too. After further thought the most simple solution I could come up with was to adjust our setup to:

The advantage of adjusting our setup like this is that the DecrementorObjects will now also decrement their own reference count. This will help us to achieve a state where the target array and all its children will have reference counts of zero after gc_mark_roots has visited all zvals. By using this core idea and some more adjustments you can come up with an example like:

As you can see no manual invocation of gc_collect_roots is necessary anymore :)! The result shows that our target array ($free_me in the example) is freed and some other rather strange things have happened to it so that we end up with a heap address.

The reason why this is happening is:

1. The GC is triggered and the target array is freed. Then the GC terminates and gives back control to unserialize.
2. The freed space will be overwritten by the next zval that is going to be defined.
   Keep in mind that we have triggered the GC by using many consecutive ‘i:0;a:0:{}’ structures. Thus, once one specific element triggers the GC the next zval that is going to be created after that is ‘i:0;’ which is the index integer of the next array that is going to be defined. In other words we have a string like ‘ […]i:0;a:0:{} X i:0;a:0:{} X i:0;a:0:{}[…]’ where the GC is triggered at an arbitrary X after which unserialize will continue to unserialize data that will fill the previously freed space.
3. Hence, our freed space will temporarily contain this integer zval. Finally, when unserialize is about to terminate it will call var_destroy which will in turn free this integer element. The memory manager will overwrite the first bytes of this freed space with an address to the last freed space. However, the type of the previous zval i.e. integer type will remain.

Consequently, we are seeing a heap address. That might be quite complicated to understand, however, the only important take away at this point is to understand where the GC is triggered and where new values are generated to fill the newly created freed space.

Now that we have gained this knowledge we can take care of controlling the freed space.

Controlling the freed space

The normal procedure of controlling a freed space is to fill it with a fake zval. By using the dangling pointer you can then do things like leaking memory or controlling the CPU’s instruction pointer.

To utilize the freed space in our given example we have to make several adjustments first:

• More than one variable has to be freed so that we can fill one of those freed spaces with our fake zval string’s content instead of filling a freed space with the fake zval string’s zval.
• We have to “stabilize” the freed space which gets filled with our fake zval string’s zval. If we skip this step unserialize will just free our fake zval string i.e. it will corrupt our fake zval.
• We have to ensure a proper alignment of freed spaces and our created fake zval strings. Further, we have to ensure that once the GC has finished the freed spaces are immediately filled with our fake zval strings. To achieve this I have come up with a “sandwich” technique.

I won’t go into more detail at this point and leave you with the following POC:

Finally, in this example you can see that after all the effort we now can create an artificial integer variable.

At this point the payload was ready to be used for remote exploitation purposes. Please note that there is some optimization potential regarding this payload. For example, one can further minimize the overall payload size by applying the sandwich technique only for the last 20% of the consecutive ‘i:0;a:0:{}’ elements.

ZipArchive Class Use-After-Free Vulnerability

Another vulnerability that has been reported in this context is:

PHP Bug – ID 72434 – CVE-2016-5773

It is based upon a similar mistake: a forgotten GC function inside its ZipArchive class. However, its exploitation is quite different from the vulnerability which we discussed before.

Since the zvals’ reference counters are temporarily decremented, any side effects like checks against those weakened reference counters or other manipulations can have disastrous consequences.

This is exactly the circumstance that can be abused for this vulnerability. By first letting the marking algorithm weaken the reference counters and then calling php_zip_get_properties instead of a valid GC function we can free one specific element. Please consider the following POC:

It is worth mentioning that setting references to zvals that haven’t been unserialized yet is impossible under normal circumstances. This payload utilizes a small trick which allows to bypass this limitation:

In particular, the payload first creates a NULL entry with the index 1 and later on overwrites this entry with a reference to filename. The GC will then only see “i:1;REF_TO_FILENAME; […] s:8:”filename”;i:1337; […]”. This trick is necessary as we need to ensure that the reference counter of the “filename” integer zval has been weakened before any side effects occur.

Conclusion

Preparing those bugs for remote exploitation was a very daunting task. Every time I had solved one problem a new problem arose. However, in this write-up we have seen one approach to tackle issues with a relatively high complexity. By iteratively asking well-prepared questions, by focusing to solve each question step-by-step and with enough determination we were finally able to tame the complexity and win this case.

Further, it was quite interesting to see the interplay of two completely unrelated PHP components: unserialize and the GC. Here, I personally had a lot of fun and learned a lot while analyzing the behavior of those components and would advise you to recreate the discussed matter for learning purposes. The latter can be especially important when considering that even in this relatively long article I have left out/black boxed several details.

Please consider that in our scenario we have exploited unserialize. However, the use of unserialize is, at least for local exploitation, optional. This distinguishes the discussed vulnerabilities from the usual low-hanging fruits one was used to encounter when auditing unserialize in earlier PHP versions. Nevertheless, as stated in our other articles: you should never use unserialize with user input and rather rely on less complex serialization methods like JSON.

In conclusion, the proof of concepts in this article and the fact that we could utilize one of the discussed vulnerabilities to get remote code execution on pornhub.com highlights PHP’s garbage collector as an interesting attack surface.

On a side note I’ve heard rumors about the GC being not really amused about this situation: