LWN: Comments on "Fun with NULL pointers, part 2"

Fun with NULL pointers, part 2

bdonlan — 2009-08-11T18:50:24+00:00

BUG_ON doesn't fix a problem - it complains about one. It's a bit like
assert(!condition) in userspace - if you actually hit it, the program's
already doomed. The Linux kernel tries to keep going a bit, just because it's
difficult to get debug information after a panic, but this is _not_ fixing a
problem, and a tripped BUG_ON is _by definition_ a bug.

As such, the only disadvantage to extra BUG_ONs is the run-time overhead from
them.

Suggestion

eparis123 — 2009-07-24T23:29:41+00:00

An older interview with the other half of the Pax team on June:

http://www.phrack.org/issues.html?issue=66&id=2#article

Suggestion

corbet — 2009-07-24T14:37:28+00:00

Cool, that speeds the reading process for some of us. FWIW, here's a direct link to the comment.

Suggestion

spender — 2009-07-24T14:35:15+00:00

The original English version was just posted as a comment to the article:
http://linuxfr.org/2009/07/24/25761.html

-Brad

Suggestion

corbet — 2009-07-24T13:04:47+00:00

You're not the only one to think about such things...I just noticed that LinuxFR.org has posted an interview with Brad. Only possible problem is that it's in French...

Suggestion

Trou.fr — 2009-07-24T08:58:00+00:00

I concur. Some well detailed explanation about the current shortcomings of the kernel, and how to they could possibly fixed. Without ranting ;)

Suggestion

bojan — 2009-07-24T01:31:13+00:00

It would be great if LWN could engage Brad and PaXTeam to write an article in which they lay out what/how the kernel should be changed so that we don't see bugs like this exploited any more.

+1

xoddam — 2009-07-23T14:57:27+00:00

+1, for sanity.

Fun with NULL pointers, part 2

ortalo — 2009-07-23T12:27:16+00:00

Don't you think a static checker could benefit from BUG_ON()-like information (or ASSERT() or whatever you want to name it) by using the given check/assumption for code analysis.
In this case, the additional line is more an annotation (like those many static checkers introduce) than source code.
As a developper you may legitimately want that such annotations be placed elsewhere than in the middle of code, but then where would you like to place them?

Side note: I really do not buy the constant number_of_fault/loc assumption. But well... that's another debate; and anyway IMHO your argument with respect to code readability and maintanability is totally valid.

Are you an idiot or just play one or TV?

epa — 2009-07-23T11:15:14+00:00

Why yes, I was talking about this particular case. Doing a null pointer check earlier (whether with BUG_ON(x==NULL) or some other test) would have avoided a local root exploit in this one case. That suggests that the whole approach is not completely useless, even if in other cases it doesn't help.

I am not arguing for 'defensive programming' as sometimes practised, where you cruft up the code with workarounds to silently return or do something random if a caller is buggy. That tends to hide bugs and thus cause buggier software in the long run. (Although even this kind of defensive programming can occasionally be useful, for example in safety-critical systems where the code must keep running no matter what.)

There were a lot of investigations. Number of bugs per line of code does not change too much when you switch languages, paradigms, etc.

That is quite true but you cannot reason as follows: on average, more lines of code means more bugs, therefore an average 101-line program is buggier than an average 100-line program, therefore adding *this particular line of code* to *this particular* program is likely to cause a bug! Of course it depends on the individual case! Some kinds of code such as assertions (runtime checking) and type annotation (compile-time checking) exist only to catch bugs, and it doesn't make sense to say that adding them will tend to make code buggier just based on a general rule about lines of code.

An incorrect BUG_ON(x==NULL) certainly can introduce a bug into a program, but then an incorrect anything can introduce a bug.

Fun with NULL pointers, part 2

etienne_lorrain@yahoo.fr — 2009-07-23T08:54:21+00:00

Nowadays, if you are not in a tight loop written in assembly, you no more count the number of cycles of instructions but the amount of time it takes to load it into the layer 1 memory cache, and the time to reload the previous cache line after executing your instruction, it is basically proportional to the size of the instruction.
The two cmp solution needs 16 bytes (in protected mode) if the out-of-bound handler is within 256 bytes of the test, and 32 bytes if not: that is a complete cache line.
The bound solution needs 8 bytes, mostly because it does not encode the out-of-bound address handler.
The difference loading the other 24 bytes is a lot more significant than the 4 cycles difference.
Even the failed branch prediction you will probably get is more important - even the fact that you have polluted the branch prediction cache is probably more important.
The default INT5 screen print handler is not accessible under Linux, BIOS is not mapped and the APIC is configured differently, if I remember well you have a SIGBUS exception in user mode and something as easy to trap/abort in kernel mode.

Fun with NULL pointers, part 2

dgm — 2009-07-23T08:09:04+00:00

Except that the kernel is not designed, it evolves. Linus has pointed it out several times. At most, some features are initially designed, but from there on, it's all evolution.

Maybe you write perfectly designed code that works wonderfully and will never need an update, fix or improvement. I centainly don't. I make mistakes, that's why my code is full of assertions, and I try to manage impossible situations in a sane way, just in case.

With regards to fat and slow... Any check can be made optional, by simply putting it between a pair of #ifdefs. Maybe somebody will apreciate a more rugged, even if slower kernel for certain servers that are exposed to the outside World. An important point would be to measure how much slower that kernel would be.

Are you an idiot or just play one or TV?

khim — 2009-07-23T05:35:07+00:00

It's not even funny: you are discussing one particular function in it's current incarnation where Eric discusses the whole approach.

Adding the null pointer check does not cause the first bug you mention, although it may help to reveal it.

But it can crash the perfectly working system tomorrow after some kind of refactoring.

The second item is a coding style issue, not a bug (and your logic is circular; you try to show that adding the BUG_ON is a bad idea, so you cannot assume that in your argument).

Today human mistakes are promoted to "code style issue"? News to me...

The third assertion needs some evidence, and even if true cannot be used to show that adding any particular line of code introduces a bug

There were a lot of investigations. Number of bugs per line of code does not change too much when you switch languages, paradigms, etc. It reduces if you do a lot of rafactoring (like kernel developers do) and srinks when you are using different autodetection tools (which are they using too), this change is pretty limited. It'll be somewhat strange to see that BUG_ON is somehow 100 times less buggy then the rest of the code.

any more than you could use it to justify removing one particular line of code from the middle of your program.

Yup. Justification is the same as for the rest of code: if you function will continue to work - why have this line in first place? Redundant comments can be kept around, but actual line of code? Please - a lot of stuff kernel developers are doing is this exact "removal lines of code from the middle of your program".

(It is sometimes the case that adding overzealous error checking introduces a bug, but that needs to be shown in each individual case, and you haven't shown it here.)

And now sound almost adequately. If sometimes overzealous error checking introduces a bug then it's good idea to keep it out of program: asserts, coverity, etc. These things can detect bug but they can not introduce new bug (false positive is not a bug as it's not compiled in actual kernel).

Defensive programming makes sense when you suspect other code has lower quality (userspace, drivers for obscure devices, etc), but to try to protect code from code of equal quality with so-called "defensive programming" is to increase number of bugs!

Incorrect statements:

spender — 2009-07-23T02:45:32+00:00

We have a word for those "dumb things" that grant more privilege than the system normally would: "vulnerability." So where's the CVE?

-Brad

Fun with NULL pointers, part 2

spender — 2009-07-23T02:36:17+00:00

The videos require being a USENIX member.

-Brad

Fun with NULL pointers, part 2

quotemstr — 2009-07-23T02:20:50+00:00

Not really all that nice:

Intel's designers added the bound instruction to allow a quick check of the range of a value in a register. This is useful in Pascal, for example, which checking array bounds validity and when checking to see if a subrange integer is within an allowable range. There are two problems with this instruction, however. On 80486 and Pentium/586 processors, the bound instruction is generally slower than the sequence of instructions it would replace:
     cmp     reg, LowerBound
     jl      OutOfBounds
     cmp     reg, UpperBound
     jg      OutOfBounds
On the 80486 and Pentium/586 chips, the sequence above only requires four clock cycles assuming you can use the immediate addressing mode and the branches are not taken; the bound instruction requires 7-8 clock cycles under similar circumstances and also assuming the memory operands are in the cache. A second problem with the bound instruction is that it executes an int 5 if the specified register is out of range. IBM, in their infinite wisdom, decided to use the int 5 interrupt handler routine to print the screen. Therefore, if you execute a bound instruction and the value is out of range, the system will, by default, print a copy of the screen to the printer. If you replace the default int 5 handler with one of your own, pressing the PrtSc key will transfer control to your bound instruction handler. Although there are ways around this problem, most people don't bother since the bound instruction is so slow.

NKX-bit

i3839 — 2009-07-22T23:37:46+00:00

Seems like the execute (and perhaps some other) memory permissions should be split up into user and kernel versions, that would solve this particular problem at least. That said, if they just got used to a separate no-execute bit, it may take a really long time before they introduce a no-kernel-execute bit (or ring0, whatever).

Fun with NULL pointers, part 2

i3839 — 2009-07-22T23:26:21+00:00

> This bug happened because the author wrote patently idiotic code, using a pointer and THEN checking it.

My understanding was that two people worked on the same code and that this was a result of a bad merge, though I could be confusing this with another case.

Fun with NULL pointers, part 2

dlang — 2009-07-22T21:04:21+00:00

this is actually a very interesting presentation. videos are available at
http://www.usenix.org/events/usenix09/tech/ (I believe they are available to everyone, not just usenix members, please let me know if that is not the case)

there are a number of trends (not very surprising in retrospect)

if you have a false positive, the chances of anyone paying attention to further reports in that section of the code drop drasticly.

if you have a maintainer who looks at one report, the chances of them dealing with all of them in that area go up significantly

if a fix is produced as a result of a report, the chances of all the reports for a given area being looked at and fixed go up drasticly

if there is not an active maintainer of that section of code the chances of the reports being looked at go down drasticly.

a large percentage of real bugs and vunerabilities have had reports on that section of the code (note that this is _not_ the same thing as saying that a large percentage of reports have been found to cause real bugs and vunerabilities)

there is a significant push from kernel developers to avoid rushing to clean up the code to silence the warnings, there is a large enough correlation between these reports and more significant bugs that many of them want the entire section where reports are found to be examined, there is a significant chance that there is a more significant and subtle bug lurking in that area.

Fun with NULL pointers, part 2

hmh — 2009-07-22T20:52:20+00:00

Is the information that the checker produces actually getting to the developers that can do something about it?

That seems to be a valid question...

Yes, you are overly naive...

PaXTeam — 2009-07-22T18:53:33+00:00

well, the actual page table manipulation would not be that expensive, with some tradeoffs you can reduce it to changing a few top-level page table entries and a single TLB flush, which would be a few hundred cycles or so.

however there's more cost to this: TLB repopulation which would inevitably occur after returning to userland. that is the real expense as we're talking about up to hundreds of TLB entries on modern CPU cores, each potentially missing in the data cache and incurring hundreds of cycles.

Yes, you are overly naive...

dlang — 2009-07-22T17:25:39+00:00

this would be _very_ expensive. changing the page tables is relativly expensive (especially if you have to do a lot of them)

Fun with NULL pointers, part 2

brianomahoney — 2009-07-22T16:03:51+00:00

Add more checks of all types, we all make mistakes is pure nonsense, it will make the kernel slow and fat, with no real improvement in reliability. it is the mark of a confused and poor programmer who has no sense of design and debugging kernel code.

This bug happened because the author wrote patently idiotic code, using a pointer and THEN checking it. This code, and all others like it need to be fixed so it actually does what it is intended to do. We do not need the kernel full of ah, well, but checks and other kruft.

The secondary, and very worrying thing is GCC silently dropping the check, we do not need optimizations like that without a STRONG warning, but I guess the motivations of the GCC developers are different here, and they really cannot win, there is constant pressure to improve compiled code and not to introduce more baby-minding warnings.

Perhaps COVERTY can help here, but we need more and better analysis, and focused bug-fixing bu good developers not the injection of confused well meaning tests.

Fun with NULL pointers, part 2

error27 — 2009-07-22T14:57:45+00:00

One thing that is delaying smatch is that I'm cycling through Africa right now :P. The smatch web page is out of date. I gave up trying to ssh in and fix it from internet cafes, but now I'm in South Africa maybe it's possible.

The new link for smatch is: http://repo.or.cz/w/smatch.git/

One issue with printing an error after a dereference is that some macros do needless checking.

But it's easy enough to write a script for that. I don't have electric tonight but hopefully I will be able to post a script in a two or three days. I wrote a first draft of the script yesterday and it did find a bug.

Fun with NULL pointers, part 2

dgm — 2009-07-22T13:25:38+00:00

Looks like a variation of the "end to end principle" (http://en.wikipedia.org/wiki/End-to-end_principle). No matter that callers check for NULL, the callee has still to check it, again.

Also, as someone has pointed out, NULL is just *one* invalid pointer value (even if a common one). The kernel should better be testing to prevent pointers to user space, except when needed.

I don't know enough Linux internals. Should it be possible to make those tests with some memory protection trickery?

Fun with NULL pointers, part 2

spender — 2009-07-22T12:51:55+00:00

Now that the blog was posted, I can mention that the tun.c bug was found by Coverity months ago and reported, but it went unfixed.

Couple that with the information from this study:
http://www.usenix.org/events/usenix09/tech/full_papers/gu...

that 40% of the issues reported by the static checkers aren't being triaged.

-Brad

Fun with NULL pointers, part 2

nick.lowe — 2009-07-22T12:13:55+00:00

http://blog.coverity.com/posts/general/would-you-like-to-...

Fun with NULL pointers, part 2

MisterIO — 2009-07-22T12:08:03+00:00

A check for a situation where a pointer dereference is followed by a check for NULL on that pointer will be present in the next release of cppcheck(1.35).

Fun with NULL pointers, part 2

etienne_lorrain@yahoo.fr — 2009-07-22T11:50:39+00:00

And the i386 has a very nice assembly instruction for that, which perfectly fits: "bound".
The nice thing is that it is very short, and never mess with the jump instruction prediction subsystem because if not inside boundaries, an exception is generated.
I just know one single software using that assembly instruction, and it works as intended.

Fun with NULL pointers, part 2

johill — 2009-07-22T11:23:01+00:00

Really? I thought the out_of_line_bug() in my example would have that attribute, but not the BUG() itself. But powerpc for example is different though, it just inserts a trap (twi or such).

Fun with NULL pointers, part 2

epa — 2009-07-22T11:14:26+00:00

Making sure that a pointer is never NULL is easy when it is passed to a static function. For public functions it is harder and more checks are needed, but if all callers are limited to one directory it's still not hard.

It's not hard, but I know that I am able to make mistakes on even the simplest tasks. I also know that I am not quite the world's worst programmer or the most careless, so if I can screw up, others can too. That's why even after you have carefully gone through the code and made sure that 'obviously', NULL can never be passed, it is still a good idea to include a check just in case, to stop a minor oversight becoming a major bug (such as the root exploit discussed in the article).

The best option is for the compiler to statically ensure non-null pointers; tools like Splint let you be certain that getting null is impossible.

If it's unclear if something can be NULL or not then in the long term it's much better to clean up the code.

Absolutely agreed. If it's unclear whether NULL is allowed, then BUG_ON(x==NULL) is not the right way, except as a temporary debugging aid. You need to check the code and make a decision - can NULL ever legally be passed here? If the answer is no, then you should make sure all the callers are behaving properly - but then when you've finished put in the BUG_ON check anyway, because even Linus makes mistakes.

Yes, you are overly naive...

ajb — 2009-07-22T11:13:12+00:00

According to wikipedia newer cpus have an 'address space' tag which can be used to avoid flushing the TLB on VM switches. Could also be used for kernel vs user mode? It would require cooperating with the VM monitor though. (I wish VMs could be nested - it would be nice to be able to run untrusted code on EC2 without using QEMU. ).

Although that doesn't obviously help for the cases where the kernel needs to access user mode memory; one would still have to change the permissions to access it and then change them back.

Fun with NULL pointers, part 2

i3839 — 2009-07-22T10:19:07+00:00

Making sure that a pointer is never NULL is easy when it is passed to a static function. For public functions it is harder and more checks are needed, but if all callers are limited to one directory it's still not hard.

If you pass along a pointer and say "hey, do something with this", in general that code did something with it before, otherwise the second function could be called directly.

For pointers within structures it's much harder though, then it helps to have clean code with clear lifetime rules. If it's messy enough you can make things more messy by adding NULL checks everywhere. If this adds more unexpected error paths then it's not a good way forwards though. If it's unclear if something can be NULL or not then in the long term it's much better to clean up the code. Like assertions BUG_ON is good while developing a new piece of code to make sure all assumptions hold. When the code gets more into shape and becomes more stable there should be not much need for such checks anymore.

An exception is low level library like code which can be used by many users and which wants to prevent them making the same bloody mistakes. It's also a good way to prevent corruptions from spreading around.

The further away the code giving the input is from the code using it the more checking is necessary.

Not NULL assertions

iq-0 — 2009-07-22T10:14:25+00:00

It is argued that adding assertions to your code helps you describe and optionally enforce your contract (design/programming by contract).

I agree that the default BUG_ON(..) is the wrong way to go, but removing it removes a piece of information, namely that we assume the pointer to be not null. I think that a better solution would be to introduce:

ASSERT(expr) and possibly ASSERT_NOT_NULL(ptr) or ASSERT_VALID_PTR(ptr) which also checks for error pointers. They perfectly describe what we expect from our input parameters and you with a DEBUG_ASSERTIONS configuration option you would activate these additional checks (which for production systems would not be enabled by default).

The other thing I personally encountered during some kernel programming was that it's often not clear if a pointer could be NULL at a given point. Idealistically one would always write input and output documentation for functions, but I don't think that would be realistic and it would get outdated soon (or people make the wrong assumptions because the documentation said so, but forgot to mention the out of memory error pointer).
Most tricky bits however ware the hooks one writes in the device drivers, which are called by some other parts of the kernel. There are far fewer of those and changes there are always done very carefully for there are many users of those callbacks (both calling and providing). So a changes any changes here are much more well thought through and given the care that must be taken the updating (and given the symantics change, any resulting code that has to be modified to handle the new symantics) would make the documentation update pretty minor. Idealisticly you should also be able to introduce (preferably with one simple config option) a way that a debug proxy function would be inserted or a debug hook be called before calling the actual hook function. This would probably mean that calling a hook or registering a hook should be made more explicit, which would be a good thing (especially calling a hook, registering is very frequent, but calls are much more sporadic).

This of course assumes that some people would be willing to run test-kernels which are easily 5% slower than the production versions, though they should be more secure and at least as stable as soon as the first wrinkles are ironed out.

Fun with NULL pointers, part 2

mb — 2009-07-22T09:53:20+00:00

Well, for most architectures the BUG() functions are __attribute__((noreturn)) or something equivalent. So the compiler cannot assume that the execution flow reaches to after the if (!ptr) check at all, if ptr is NULL. So it should not optimize it out in that case.

Fun with NULL pointers, part 2

epa — 2009-07-22T09:15:19+00:00

Either make sure that all callers don't pass in a NULL pointer, or if that isn't possible, add a check and return with an error.

Suppose you take the first option; you check all the code that could call your routine and make sure NULL is never passed. Then there is no need for a runtime check, right? In theory this is true but I know I make mistakes, so even after checking all the code I would still put in the check for this 'impossible condition' to stop a small oversight causing a big problem.

It's the same argument for any assertion you put in your code: since they are checking for something that can never ever happen, why bother with them at all? All programmers make mistakes, but the better ones are aware of this fact and take appropriate measures.

(This is not an argument for sloppy 'defensive programming' as sometimes practised, where you insert code to silently return the wrong answer or do something random if the inputs aren't as you expect. You want a macro like BUG_ON or assert() which loudly announces the problem, not hides it.)

Fun with NULL pointers, part 2

epa — 2009-07-22T09:10:03+00:00

You have the wrong input should never have been generated in the first place.
You have the wrong BUG_ON in the function.
Bugs per line of code are roughly constant. Therefore you want a design that uses fewer lines of code.

Adding the null pointer check does not cause the first bug you mention, although it may help to reveal it. The second item is a coding style issue, not a bug (and your logic is circular; you try to show that adding the BUG_ON is a bad idea, so you cannot assume that in your argument). The third assertion needs some evidence, and even if true cannot be used to show that adding any particular line of code introduces a bug, any more than you could use it to justify removing one particular line of code from the middle of your program. (It is sometimes the case that adding overzealous error checking introduces a bug, but that needs to be shown in each individual case, and you haven't shown it here.)

Fun with NULL pointers, part 2

msmeissn — 2009-07-22T08:47:23+00:00

Well, Coverity scans the kernel.

They issued a press release that they found the issue (REVERSE_INULL I
would guess).

Just someone needs to read and investigate all the reports, and
its quite an amount and not so funny work.

Ciao, Marcus

Yes, you are overly naive...

gmaxwell — 2009-07-22T08:02:54+00:00

How terrible for performance would it be to make all userspace accessible memory no-execute on kernel entrance? (or otherwise achieve the same result, like making it unreachable and then faulting it back in with NX-set).

Fun with NULL pointers, part 2

PaXTeam — 2009-07-22T07:01:56+00:00

> What made all of this interesting is the fact someone found a way around the defensive measure of mmap_min_addr.

It's not at all interesting because any feature which is *designed* to be circumventible will be, well, circumvented. From day one it was obvious and publicly discussed that exploit writers would go after the needed capability (that assuming they don't have better bugs to exploit not needing it ;).