Defragment

The state of a process's heap depends on the history of allocations and deallocations that have occurred during the process's lifetime. Consequently, the state of the heap for a long running multithreaded process (e.g. a web browser) is unpredictable. Generally, such a heap is fragmented in that it has many holes of free memory. The presence of varying sized holes of free memory means that the addresses of successive allocations of similarly sized buffers are unlikely to have any reliable relationship. Figure 1 shows how an allocation in a fragmented heap might look. Since it is impossible to predict where these holes might occur in a heap that has been in use for some time, it is impossible to predict where the next allocation will occur.

However, if we have some control over the target application, we may be able to force the application to make many allocations of any given size. In particular, we can make many allocations that will essentially fill in all the holes. Once the holes are filled up, i.e. the heap is defragmented, allocations of similar size will, in general, be predictably close to each other, as in Figure 2.

We emphasize that defragmentation is always with respect to a particular buffer size. In preparation for the exploit, we must defragment the heap with respect to the size of the vulnerable buffer. The size of this buffer will vary, but should be known. As shown in [2], arranging for defragmentation is simple in JavaScript. For example,

var bigdummy = new Array(1000);
for(i=0; i<1000; i++){
   bigdummy[i] = new Array(size);
}

In the code snippet above, each call to new Array(size) results in an allocation of 4*size+8 bytes on the heap.¹ This allocation corresponds to an ArrayStorage object consisting of an eight byte header followed by an array of size pointers. Initially, the entire allocation is zeroed out. A value of size should be chosen so that the resulting allocations are as close as in size as possible, and no smaller, than the size of the vulnerable buffer. The value of 1000 used above was determined empirically.