Kernel Fuzzing in Userspace

Twitter is not just flames and drama, sometimes it inspires you:

I was as surprised as everybody else, five ASN.1 parsers inside the Linux kernel? Wow! But surely somebody would already have audited them, right? CVE-2016-0758 should be the result of that. Since I already had parts of the required glue around to make these parsers run in user space with a little beating, I decided that a quick fuzzing run might not hurt.
For a proper audit the time was simply missing. :(

So what did I do? The first step was an AFL based fuzzer, which quickly identified some out-of-bound reads in two different parsers. The next step included modifying the code to get more out of the different parsers and to actually get all five running (this did not happen in the first iteration due to some bugs). After this went on successfully for a while, I weeded out all the generated test cases (input and queue) with afl-cmin and reduced them with afl-tmin. This was passed on to radamsa, since we have gotten some nice results out of it in the past, where the radamsa mutators uncovered test cases afl and libfuzzer have had a harder time finding. The resulting corpus was reduced again and passed to an additional libfuzzer test case, since libfuzzer greatly improves on the speed in comparison to AFL.

Fortunately (heh, we use Linux as well…) this only triggered some out of bound
reads and nothing
more serious.

One of the parsers is generic and needs to be fed with additional data generated with the help of the scripts/asn1_compiler tool. Users include the x509, pkcs7 and mscode parsers. In order to get a proper coverage of this parser, the x509 parser was fuzzed as well and it triggered a more interesting bug, an out of bounds write. What was the culprit? Responsible was an integer underflow in the sprint_oid() function.

int sprint_oid(const void *data, size_t datasize, char *buffer, size_t bufsize)
{
        const unsigned char *v = data, *end = v + datasize;
        unsigned long num;
        unsigned char n;
        size_t ret;
        int count;

        if (v >= end)
                return -1;

        n = *v++;
        ret = count = snprintf(buffer, bufsize, "%u.%u", n / 40, n % 40);
        buffer += count;
        bufsize -= count;
        if (bufsize == 0)
                return -1;

        while (v < end) {
                num = 0;
                n = *v++;
                if (!(n & 0x80)) {
                        num = n;
                } else {
                        num = n & 0x7f;
                        do {
                                if (v >= end)
                                        return -2;
                                n = *v++;
                                num <<= 7;
                                num |= n & 0x7f;
                        } while (n & 0x80);
                }
                ret += count = snprintf(buffer, bufsize, ".%lu", num);
                buffer += count;
                bufsize -= count;
                if (bufsize == 0)
                        return -1;
        }

        return ret;
}

The culprit is the second snprintf() call. Lets see what the manpage says regarding return values:

“return value of size or more means that the output was truncated”

That means, if the buffer does not fit, bufsize might get decreased to a value < 0, and we write past the end of buffer in the next iteration of the while loop. A quick PoC in user space shows that this is happening and we can write as much as we want. The somewhat uninuitive behaviour of sprintf seems not to be known widely. The next step wass to test this in kernel space, but to my surprise, a kernel module which send the right data to sprint_oid() did not trigger a bug, but a warning.

int vsnprintf(char *buf, size_t size, const char *fmt, va_list args)
{
	unsigned long long num;
	char *str, *end;
	struct printf_spec spec = {0};

	/* Reject out-of-range values early.  Large positive sizes are
	   used for unknown buffer sizes. */
	if (WARN_ON_ONCE(size > INT_MAX))
		return 0;

The reason lied in vsnprintf(), which checked if the size of the buffer into which it writes is bigger than INT_MAX. When checking the current -git, we see that the issue was also fixed in commit afdb05e9d61905220f09268535235288e6ba3a16.

Nevertheless, this is an interesting pattern. A small cocinelle script from Markus helped to find other users of this pattern in the kernel, which we patched and submitted to LKML.

Unfortunately, this is when we ran out of spare time to look into this topic. But we hope we will gain further opportunities in the future to look deeper into the security of the Linux kernel. If you are interested in sponsoring such research in order to get bugs in the kernel fixed (and not exploited), please let us know