Friday, May 27, 2011

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:

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 *
if (temp == NULL) {
xmlXPathErrMemory(NULL, "growing nodeset\n");
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 *
if (temp == NULL) {
xmlXPathErrMemory(NULL, "growing nodeset\n");
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
(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);

Wednesday, May 25, 2011

Bug bounties vs. black (& grey) markets

I'm just back from the fun that was HiTB Amsterdam 2011. (Plug: you should check out one of the HiTB series if you haven't yet; Dhillon and crew invariably put a good, intimate conf together).

I sat on the day 2 keynote panel on "The economics of vulnerabilities". As usual, talking about this topic was great fun and the audience asked some great questions. Predictably, the topic strayed on to black market sales as an interesting sub-discussion. With 6 people on the panel, it was hard to cover this in the detail it deserves, and I think a few important subtleties were missed. I'll try to cover some of them here.

Vulnerability reward programs do not "buy" bugs, nor do they aim to compete with the black market
Remember that the black (or grey) markets buy exploits, not vulnerabilities. The latter are just the first step towards exploits, which are hard to write on modern software. Also remember that reward programs are not buying even vulnerabilities. Typically, they are a "thank you" mechanism for talented researchers who used their skills to make things better.
Also, there's often a separation of which researchers participate where, along ethics lines; see below.

A vulnerability reward program will indirectly compete with black market sales
It's interesting to note that a reward program doesn't have to outbid dubious markets in order to have a benefit in this area. These days, there's a lot of independent rediscovery of the same vulnerabilities -- ZDI quoted 22 "collisions" for the most recent year.
So any motivation you can provide for white hats to discover vulnerabilities will inevitably kill the occasional black market vulnerability.
A quick story in support: the WebKit vulnerability used by VUPEN to pwn Safari at this years' pwn2own competition was independently reported to the Chromium project by researcher Martin Barbella. Thanks to Inferno's lightning quick fix, Chrome entered pwn2own without that bug. Martin, of course, received a $1000 Chromium Security Reward (on top of all his others).

Black / grey market sales are a dangerous alternative to consider
Each researcher has to set their own ethics, of course. Hopefully, most of us get into this industry to make users safer and software more secure. Aside from reward programs and ZDI, there's also a large number of well-paid security jobs sponsored by corporations, so no need to start selling exploits to feed the family.
If you sell an exploit to someone, it's basically going to be used to exploit end users of the software. This could harm a lot of people if the target is mass malware for financial gain. Or it could seriously harm some targeted individuals if a government of dubious human rights commitment gets their hands on it.

"Credit", whilst important, is not a full replacement for a monetary reward
To be clear about it: if you launch a vulnerability reward program, you will receive more vulnerability reports from a wider range of researchers. The power of credit and prestige is often cited as an argument to not launch a reward program, but the fact remains that you will get more reports if you have a program in place. And as long as you have a culture of fixing security bugs promptly, your users will be safer thanks to having a reward program.