Safe Rust code miscompilation due to a bug in LLVM's Global Value Numbering

[RalfJung]

lib/src.rs in the foo crate:

#[inline(never)]
pub fn test(gp1: &mut *const i32, gp2: &mut *const i32, b1: bool, b2: bool) -> (i32, i32) {
    let mut g = 0;
    let mut b = 0;
    let y = 6666;
    let mut x = 7777;
    let mut p = &mut g as *const _;

    {
        let mut q = &mut g;
        let mut r = &mut 8888;

        if b1 {
            p = (&y as *const _).wrapping_offset(1);
        }

        if b2 {
            q = &mut x;
        }

        *gp1 = p.wrapping_offset(1234);
        if q as *const _ == p {
            b = 1;
            *gp2 = (q as *const _).wrapping_offset(1234);
            r = q;
        }

        *r = 42;
    }

    return (b, x);
}

src/main.rs in the main crate:

use std::ptr;

extern crate foo;

pub fn main() {
    let mut x1 = ptr::null();
    let mut x2 = ptr::null();
    let mut gp1 = &mut x1;
    let mut gp2 = &mut x2;

    let (b, x) = foo::test(&mut gp1, &mut gp2, true, true);
    println!("b = {}, x = {}", b, x);
}

This prints b = 1, x = 7777. That is wrong; if b is 1, it must be the case that the then-branch in the q as *const _ == p conditional was taken, so r is &mut x (since b2 is true), so x cannot still be 7777.

This is a bug in LLVM's GVN, see https://bugs.llvm.org/show_bug.cgi?id=35229 for the upstream report and some further analysis.

Original C test case by Gil Hur.

[bstrie]

Conservatively tagging this as I-unsound, feel free to downgrade to I-wrong if necessary.

[nikomatsakis]

We discussed this in the @rust-lang/compiler team meeting and we are thinking of closing this bug. It doesn't make sense to have a bug for every LLVM bug, and this one hasn't been observed "in the wild" for Rust code, only for artificial examples, so it's probably not adding much value. @RalfJung thanks for bringing it to our attention.

If LLVM decides not to fix, we may want to re-open, though it's unclear if there is much we can practically do to prevent this sort of optimization.

[RalfJung]

Fine for me.

If LLVM decides not to fix, we may want to re-open, though it's unclear if there is much we can practically do to prevent this sort of optimization.

I'd say this depends on their reasoning. If they somehow introduce a rule that this ought to be UB, we have a problem -- I don't see any good way to rule out such safe code. I would also be surprised if it was not possible to expand this miscompilation to trigger actual UB in safe Rust (notwithstanding the fact that miscompilations giving the wrong results in safe code aren't really less bad than UB in safe code). OTOH, adapting my proposal in #45719 to not use GEP in wrapping_offset would fix all known ways to exploit this bug.

[cristicbz]

FWIW, we could fix this by replacing the wrapping_offset implementation with ((self as isize).wrapping_add(offset * (size_of::<T>() as isize)) as *const T), but I see perf regressions on simple things like:

#[bench]
fn current(b: &mut Bencher) {
    let mut v = Vec::with_capacity(512);
    let mut r = 0u32;
    v.clear();
    for _ in 0..512 {
        r = r.wrapping_mul(1664525).wrapping_add(1013904223);
        v.push(r);
    }

    b.iter(|| {
        let v = black_box(&v);
        let mut p = v.as_ptr();
        let end = v.as_ptr().wrapping_offset(v.len() as isize);
        let mut sum = 0;
        while p != end {
            sum += unsafe { *p };
            p = p.wrapping_offset(1);
        }
        black_box(sum)
    });
}

goes from 23ns/iter up to 187ns/iter . Investigating the asm (playground), it looks like it inhibits auto-vectorisation on:

pub trait WrappingOffsetExt {
    fn wrapping_offset_ext(self, offset: isize) -> Self;
}

impl<T> WrappingOffsetExt for *const T {
    fn wrapping_offset_ext(self, offset: isize) -> Self {
       ((self as isize).wrapping_add(offset * (::std::mem::size_of::<T>() as isize)) as *const T)
    }
}

#[no_mangle]
pub fn via_wrapping_offset(v: &[u32]) -> u32 {
    let mut p = v.as_ptr();
    let end = v.as_ptr().wrapping_offset(v.len() as isize);
    let mut sum = 0;
    while p != end {
        sum += unsafe { *p };
        p = p.wrapping_offset(1);
    }
    sum
}

#[no_mangle]
pub fn via_integer(v: &[u32]) -> u32 {
    let mut p = v.as_ptr();
    let end = v.as_ptr().wrapping_offset_ext(v.len() as isize);
    let mut sum = 0;
    while p != end {
        sum += unsafe { *p };
        p = p.wrapping_offset_ext(1);
    }
    sum
}

fn main() {}

Edit: Fixed lack of size_of::<T>.

[RalfJung]

FWIW, we could fix this by replacing the wrapping_offset implementation with ((self as isize).wrapping_add(offset) as *const T),

That's what I mentioned in my previous commit; however, your patch is slightly wrong: You need to multiply offset by mem::size_of::<T>.

[eddyb]

The only reason wrapping_offset was added was to avoid roundtripping through an integer. cc @dotdash who added the intrinsic (arith_offset) back in #25434.

[cristicbz]

@RalfJung

what I mentioned in my previous commit

Not sure which commit that, I must have missed it, sorry.

You need to multiply

D'oh, sorry. Numbers and conclusions stay exactly the same.

@eddyb Right, makes sense. Figured it would be good to know if in this particular case roundtripping would fix the issue or not. @RalfJung mentioned on reddit that due to LLVM 34548 casting to integers before comparing doesn't help. Wanted to check if casting before the arithmetic does work.

[RalfJung]

@eddyb thanks for the pointer to #25434. It seems that wrapping_offset deliberately does not round-trip through integers, enabling more optimizations. In this case, however, I think there should be a big fat warning in that method's documentation that also the operational effect of this is very different from doing the same thing on integers! The fact that LLVM optimizes more is not because LLVM does not see the potential for optimization when using integers; it is that the optimization would be illegal.

[regehr]

Can I ask if you (Rust compiler) folks have looked over the emitted IR for this one super carefully to make sure it doesn't contain anything that gives LLVM an easy excuse to invoke UB?

[arielb1]

@regehr

Obviously, the entire reason there is UB here is because LLVM's semantics are not clear enough.

However, the 2 "known" exploits of this bug rely either on out-of-bounds getelementptr or on dereferencing pointers cast from integers, so it might be that avoiding these two can banish the bug away. That needs more investigation before we disable something that might just be the messenger.

[regehr]

@arielb1 I was trying to politely ask if y'all are completely sure the Rust compiler isn't doing something stupid.

[sunfishcode]

@regehr Yes; I've looked over the IR. Also, there is a C version of the same bug reported here which doesn't appear to invoke any undefined behavior either.

The underlying problem appears to replacing p by q within the body of an if like this:

   if (p == q) {
       *p = 42;
   }

In LLVM, icmp is a numeric test, not an LLVM pointer-semantics-equivalence test. Even when p is dereferenceable and q is numerically equal to p, q can still be non-dereferenceable.

In C terms, the equality comparison may succeed when "one [operand] is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space" (6.5.9p6), but the dereference of the one-past-the-end pointer isn't valid despite being equal to a pointer which would have a valid dereference, because "If the result [of pointer arithmetic] points one past the last element of the array object, it shall not be used as the operand of a unary * operator that is evaluated." (6.5.6p8).

[regehr]

Thanks @sunfishcode! This stuff is super difficult and I wanted some reassurance this is a hard bug and not an easy bug :)

[RalfJung]

Another interesting question is if we can use this LVLM bug to trigger UB in safe Rust code. So far it seems we have a gadget to "replace" one value of a given type by another; if we could apply that selectively so that the during bounds checks, the index is replaced when checking but not when accessing, we would get UB. Not sure if that is possible though, because the Rust compiler is emitting both of these together.

[ahmedcharles]

The LLVM bug seems to shows a program which has UB in C. In (int)p+1 it computes what is a pointer outside of the bounds of an allocation, due to p = &y+1; when foo() returns true. (Computing 2 past the beginning of the last object in an allocation is undefined).

In Rust, wrapping_offset can't be safe while being implemented in terms of IR which was intended to have C UB characteristics. I.e. if wrapping offset is safe, then it has to treat pointers as integers which wrapping behavior, but LLVM doesn't compile a language with those semantics, which means that wrapping offset should be unsafe or implemented with different IR (though, I can't imagine that would be efficient).

I.e. why is wrapping_offset safe on pointers when it's potentially undefined in every other systems language?

[regehr]

@ahmedcharles the result of (int)p has type int and it obeys integer rules, not pointer rules. adding 1 would only be UB if (int)p had evaluated to INT_MAX

[RalfJung]

@ahmedcharles

In Rust, wrapping_offset can't be safe while being implemented in terms of IR which was intended to have C UB characteristics. I.e. if wrapping offset is safe, then it has to treat pointers as integers which wrapping behavior, but LLVM doesn't compile a language with those semantics, which means that wrapping offset should be unsafe or implemented with different IR (though, I can't imagine that would be efficient).

That's not correct. wrapping_offset uses getelementptr without inbounds. That operation always returns a "good" value in the sense that the output is neither undef nor poison.

Whether the resulting pointer may be used to access memory is a different question, also see the updated documentation for this method.

[ahmedcharles]

@regehr Indeed. I missed that.

@RalfJung Interesting. Thanks for the pointer.