It’s been a busy few days.. I was truely struggling for a while making no progress, but it all seems to have resolved itself.
I have a working memcheck tool for the Linux Kernel that checks for out of bounds memory access in both the page and slub allocator. It honours the original size requests for kmalloc etc, so the tool may find bugs which may go unnoticed due to the fact that allocations are often rounded up to confer to the slub’s internal workings.
I tried booting Fedora 8 with a modified 2.6.26 kernel with my tool running, and there were no reports of out of bounds access. However, my code only actives once the memory subsystem is initialized, which results in a reasonable amount of code not being covered.
For better results, a kernel stress test should be performed using public testing tools for kernel developers. This is something I plan on doing next.
I am likely to release this tool as a QEMU fork and set of kernel patches at the Ruxcon http://www.ruxcon.org.au security conference later this year. I will be disappointed if I don’t find any real bugs with it, but I think there is still value in the code I’ve written as a validation and testing tool.
— how it works
I’ve explained this really in earlier posts, but I’ll say it again since its really working now. The operation of it is quite simple.
QEMU is modified such that it tracks execution of the Linux Kernel running as a guest. Heap operations that allocate and free memory are intercepted (really they are dynamically instrumented). In Linux, this is the page allocator (which uses a buddy system), the slub allocator, and the bootmem allocator.
A small set of kernel patches is used in the guest to enable easier intercepting of these functions.
A representation of the heap is constructed using the information returned from the intercepted heap functions. This representation is held by the QEMU host.
All memory operations performed by the Linux Kernel guest are intercepted/instrumented. The memory access, if in the range of being on the kernel heap is checked against the heap representation. If the address is not present as part of prior allocation, a report containing the stack trace of the kernel at that point is generated.
Stack traces are symbolic, and the System.map of the guest Kernel must be provided to the QEMU host.
Free’ing non allocated memory, and use after free (really an out of bounds access) is also detected with accompanying reports.
The implementation is fairly straight forward, and has a small footprint nearing about 1000 lines for the QEMU changes, and less than 400 additional lines of for the Linux Kernel which mostly consists of instrumenting and wrapping preexisting code.