I like Alan’s closing remarks:
“Some day someone will write something that supercedes the Linux kernel. Probably before that someone should either fix or replace C so that it has an inbuilt ability to describe locking and statically enforce some of the locking rules at compile time. I’m sure my generation of programmers will despise the resulting language but in time we will all thank whoever does it.”
Originally shared by Alan Cox
A little digression on security stuff
Today’s victim is the Android pmem.c driver – and yes I told Google about this a month ago and they’ve been looking at it.
It’s an interesting example of two things, both of which are real problems with the C language and to an extent with the kernel verification and validation tools.
pmem.c is on the whole reasonably well thought out. The majority of the code clearly documents its locking model. It handles types and values very carefully. Two things however are a bit of a problem
Firstly there is a small unchecked overflow
static unsigned long pmem_order(unsigned long len)
{
int i;
len = (len + PMEM_MIN_ALLOC – 1)/PMEM_MIN_ALLOC;
and the code then checks the order is valid. By this time however it is too late, a passed length of 0xFFFFFFFF will overflow and we get the wrong order.
The damage here is actually fairly small on the whole because the code is consistent about what it uses afterwards. It checks the order, and it uses the order for everything else. So I can ask for lots but get a little and it stays enforced as a little.
That shows three things always worth remembering
1. Overflow is evil. It’s a pity C and processors were not defined that overflow trapped as they often were in mainframe days. Actually it’s less evil here than some others because unsigned overflow is at least defined behaviour. Signed overflow is not so well defined and the compiler can use that creatively for “optimisation”
2. Check your inputs. Checking the output of something which processes untrusted input data is too late
3. Always check what you use. Google got this right and it saved their bacon. The resulting order may be wrong but it’s used consistently and there is no mix of length/order elsewhere in the code which would have been catastrophic
The second problem is worse though. It’s hard to tell how it happened as I don’t have the entire history. It shows why code review is important and that stuff hidden in other trees may not get enough review. It also to an extent shows up a C and tool weakness.
My guess (and it is but a guess) is that the original pmem.c didn’t have ioctl support and someone wrote it, someone who wasn’t so experienced with multithreading and locking. The rest of the driver clearly documents and uses its locking rules. The ioctl paths just assume that there is locking lower down. In most cases there is. In a couple of cases there aren’t. In one case this is a bit of a disaster
The PMEM_ALLOCATE ioctl checks if an allocation already exists, and allocates a new chunk. As far as I can see there are no locks taken. This allows the caller to do parallel allocations corrupting the allocation pool, and also to do parallel allocations and mapping functions whose results to say the least are going to be exciting. On uniprocessor and on older kernels with the BKL applies to ioctl it’s probably not going to be hittable but you can keep trying very easily.
It’s not btw been used on a Google device since the Nexus One (according to Google) so it’s one of those ‘near miss’ cases, unless some third party is using it on a much newer or SMP device.
It would be easy to question the quality of the author of the code for such a mistake but more importantly the real question ought to be
– Why is it possible to make such a mistake ?
This is another area where C cannot enforce locking as the locking is outside of the language scope and while you could have added runtime assertions they all have a cost.
– Why wasn’t it caught
Two possible answers come straight to mind – no peer review and because the tools can’t catch it. I’m not entirely sure casual peer review would have caught it.
It does suggest we could do with a virtual machine environment where you can associate memory ranges with read/write access violations if a given lock is not held. It’s hard to do this with page tables because you need a page an object unless you do clever fault handling, and because objects often contain their own lock, which itself is accessing/changing the object memory region legitimately.
A bigger style question is why pmem_allocate is different. The other helpers mostly take the locks. A clear interface where locks are taken close to the code that most hold them can really help. Sometimes it means having ‘internal’ versions of functions to call without the lock to avoid lock recursion but that at least can make clear the special cases.
Some day someone will write something that supercedes the Linux kernel. Probably before that someone should either fix or replace C so that it has an inbuilt ability to describe locking and statically enforce some of the locking rules at compile time. I’m sure my generation of programmers will despise the resulting language but in time we will all thank whoever does it.