Simple Linux kernel memory corruption bug can lead to complete system compromise

But here we're talking about the Linux kernel and so we needn't stretch that far. "The buck stops here" so to speak, if you can't trust the OS kernel to do what it promised, you're pretty much screwed.

All you have left are broader physical or mathematical guarantees e.g. even a Linux kernel bug at Let's Encrypt can't leak your TLS server private keys because they don't have your private keys and so mathematically that can't happen - or even if there's a really drastic Linux kernel zero day this Android phone can't travel faster than the speed of light because physics doesn't rely on kernel code.

FWIW most of what you're referring to (reaching a free'd pointer via pointer arithmetic, or going straight to its address) is actually undefined behavior according to the C standard, what you're allowed to do with pointers is more limited than that. There are ways of getting around some of that (obviously, since it's necessary in embedded and other low-level situations), but it requires knowledge about your specific compiler and/or potentially the use of extensions or similar things not part of the standard.

I'm pretty sure you can get similar optimization behavior when you mark functions with special attributes, I'm not 100% sure on that point though. So for the Linux Kernel I'm not sure that kind of optimization would ever be done since obviously it's not using the standard defined functions and the compiler might not be given enough information to know the functions have the same semantics as 'malloc()' and 'free()'.

I personally was able to get the exact behavior described here by compiling the below code using `-O2`. The volatile write just ensures the first constant write and the malloc itself cannot be optimized out (and that does happen! Take out the volatile and there are no calls to malloc in the result), but gcc is still free to do whatever it wants with the other write and for me it's completely gone in the resulting program.

    int main()
    {
        int *p = malloc(sizeof(*p));
        *(volatile int *)p = 20;

        printf("p=%d\n", *p);
        *p = 30; /* this is gone from the -O2 compiled code */
        free(p);
        return 0;
    }

    push   $0x4
    call   460 <malloc@plt>
    movl   $0x14,(%eax) # Assignment of 20
    mov    %eax,%esi
    pop    %eax
    lea    -0x1930(%ebx),%eax
    pop    %edx
    pushl  (%esi) # push the 20
    push   %eax
    call   440 <printf@plt>
    mov    %esi,(%esp) # load address to pass to free(), no assignment between printf() and free()
    call   450 <free@plt>

Here's a piece of code that would go slower if you turned it off:

    for (i = 0; i < 1000; i++) {
        struct foobar *ptr = malloc(sizeof(struct foobar));
        ptr->this = a[i];
        ptr->that = b[i];
        if (ptr->this > 0) {
            do_stuff(ptr);
        }
        free(ptr);
    }

Compilers that don't do this get rejected for compilers that do.

So compiler optimizers get to take advantage of UB for that last mile optimization, which in a language like C always expect the developer to be a ISO C expert, and when they aren't or are too tired trying to meet project deadlines, surprises happen.

"Oh, it was quite a while ago. I kind of stopped when C came out. That was a big blow. We were making so much good progress on optimizations and transformations. We were getting rid of just one nice problem after another. When C came out, at one of the SIGPLAN compiler conferences, there was a debate between Steve Johnson from Bell Labs, who was supporting C, and one of our people, Bill Harrison, who was working on a project that I had at that time supporting automatic optimization...The nubbin of the debate was Steve's defense of not having to build optimizers anymore because the programmer would take care of it. That it was really a programmer's issue.... Seibel: Do you think C is a reasonable language if they had restricted its use to operating-system kernels? Allen: Oh, yeah. That would have been fine. And, in fact, you need to have something like that, something where experts can really fine-tune without big bottlenecks because those are key problems to solve. By 1960, we had a long list of amazing languages: Lisp, APL, Fortran, COBOL, Algol 60. These are higher-level than C. We have seriously regressed, since C developed. C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine. This is one of the reasons compilers are ... basically not taught much anymore in the colleges and universities."

-- Fran Allen interview, Excerpted from: Peter Seibel. Coders at Work: Reflections on the Craft of Programming

So, in general, the idiomatic Rust "twiddle all these doodads" compiles to the same machine code as the idiomatic C++ for that problem, even though Rust bounds checked it and C++ didn't care. Lots of Rust checks are like this, they compile away to nothing, so long as what you did is necessarily correct. The Option<NonZeroU64> stuff a few days ago is another example. Same machine code as a C++ long integer using zero as a signal value, but with type safety.

The bounds check wasn't being elided either. I checked and it was there in the assembly, so I figured that the function is so hot that an unchecked access might help things. Apparently not. The only thing I can think of is that the reduction in code-size for that function had an unintended effect elsewhere, either for the optimizer or that it resulted in a hot bit of code crossing a cache line?