libxml vulnerability and interesting integer issues

A while ago, I was playing with grammar-based XPath fuzzing and I found and fixed an interesting libxml bug. The commit, for the curious, is here:

http://git.gnome.org/browse/libxml2/commit/?id=d7958b21e7f8c447a26bb2436f08402b2c308be4

The trigger for this bug was the XPath expression: //@*/preceding::node()/ancestor::node()/ancestor::foo['foo'] which for some reason I haven't yet analyzed leads to a pathologically large collection of nodes within libxml.

As the nodeset is grown and grown, things get interesting when the system runs out of memory whilst trying to double the size of the nodeset:

        cur->nodeMax *= 2;
        temp = (xmlNodePtr *) xmlRealloc(cur->nodeTab, cur->nodeMax *
                                         sizeof(xmlNodePtr));
        if (temp == NULL) {
            xmlXPathErrMemory(NULL, "growing nodeset\n");
            return;
        }
        cur->nodeTab = temp;

Notice how the max number of allocated nodes in the "cur" structure is doubled before doing, checking and assigning the reallocation. This means that in the event of a realloc() failure, one of two things will happen:

• If you malloc() implementation exits the process upon alloc failure (such as Chromium), lucky you! You dodged a bullet.


• More typically, you'll exit this function with "cur" in an inconsistent state, i.e. it indicates it can hold more data than it really can.

Despite the call to xmlXPathErrMemory(), XPath processing continues with "cur" in an inconsistent state, leading to a heap-based buffer overflow.

The fix is to only update the structure's "max size" member after a successful expansion of the underlying array. libxml already did this in most places, using a paradigm such as:

        temp = (xmlNodePtr *) xmlRealloc(cur->nodeTab, cur->nodeMax * 2 *
                                         sizeof(xmlNodePtr));
        if (temp == NULL) {
            xmlXPathErrMemory(NULL, "growing nodeset\n");
            return;
        }
        cur->nodeMax *= 2;
        cur->nodeTab = temp;

... which leads us nicely into part 2:

Interesting integer issues

Even with the fix applied, there are some really interesting integer issues going on here. The astute will have noticed a possible integer overflow in the argument to xmlRealloc(), which is a general hazard with the common pattern of "double the size of the array if we ran out of room". Digging in to more detail, we see a fascinating difference in behaviour between 32-bit and 64-bit builds and maybe even learn a thing or two about integer promotion rules.

On 32-bit builds

First, let's quickly note that cur->nodeMax is of type int. That's likely the wrong type for a couple of reasons, but we will run with it for our analysis.
On 32-bit, sizeof(int) == sizeof(size_t) so we're looking at a fairly basic possible integer overflow. But can it ever be triggered? Does the 32-bit address space offer enough room?
The case with the least space requirements for the 32-bit address space is the case where we already have a 2GB (2^31) allocation and are attempting to double it -- leading to an integer overflow at 2^32 and an attempt to realloc() to 0 bytes.
But to arrive at the 2^31 allocation, we need to have a 1GB -> 2GB realloc() succeed first.
This is actually unlikely on 32-bit Linux -- which typically has just the lower 3GB of address space usable. 1GB + 2GB + program text etc. won't simultaneously fit, so the only way 1GB -> 2GB realloc() will succeed is if the allocation can be expanded in-place. glibc malloc() will typically use mmap() for large allocations, and put them towards the top of address space in order to reserve room for standard heap expansion. So realloc() on such an mmap()ed chunk typically won't have room to mremap() to a larger size.
All in all, this seems to be a hard-to-exploit bug, unless the attacker has a lot of control over other allocations (to influence the placement of the 1GB mmap() lower down in the address space and then free() whatever chunks were needed to do that, before the realloc()). Further research might be merited for other allocators (e.g. tcmalloc) and 32-bit-process-on-64-bit-host (>3GB address space available).

On 64-bit builds

With 64-bit, we have a much larger address space. This means that we should be able to successfully allocate the growing array -- and the objects contained within it -- right up until the fault condition.

The fault condition is that cur->nodeMax * 2 will eventually become negative. This negative int is then multiplied by sizeof(xmlNodePtr). Remember that sizeof() returns a size_t, so we have an int -> size_t promotion at this point. This will result in sign-extension to a 64-bit size, which will end up massive and the system allocator will not be able to satisfy an allocation of that size. Therefore, a lucky lack of impact on 64-bit.

Finally, note that there's a real subtlety in the ordering of the expression given to xmlMalloc():

cur->nodeMax * 2 * sizeof(xmlNodePtr)

Things would be very different if we had:

cur->nodeMax * sizeof(xmlNodePtr) * 2

Promotions for left-to-right operator sequences are done in strict left-to-right ordering, as opposed to some kind of overall max(precedence) promotion. Therefore, in this latter case, the initial negative-related failure will be avoided; we're looking at:

(int) 2^30 -> (int) -(2^31) -> (size_t) 0xffffffff80000000 * 8 == (size_t) 0xfffffffc00000000
vs.
(int) 2^30 -> (size_t) 2^30 * 8 -> (size_t) 2^30 * 8 * 2 == (size_t) 2^34

Seeing that nodeNr is just an int, we would likely see subsequent memory corruption if nodeNr goes subsequently negative after its increment in a statement such as cur->nodeTab[cur->nodeNr++] = xmlXPathNodeSetDupNs(node, ns);