Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Locals aligned to greater than page size can cause unsound behavior #70143

Open
retep998 opened this issue Mar 19, 2020 · 17 comments
Open

Locals aligned to greater than page size can cause unsound behavior #70143

retep998 opened this issue Mar 19, 2020 · 17 comments

Comments

@retep998
Copy link
Member

@retep998 retep998 commented Mar 19, 2020

Forked from #70022

Minimal example

#[repr(align(0x10000))]
struct Aligned(u8);

fn main() {
    let x = Aligned(0);
    println!("{:#x}", &x as *const _ as usize);
}

Aligning the stack is done after the stack probe. Because stacks grow downwards and aligning the stack shifts it downwards, it can cause the end of the stack to extend past the guard page and cause invalid access exceptions or worse when those sections of the stack are touched.

Only confirmed that this occurs on pc-windows-msvc.

@retep998 retep998 changed the title Alignment greater than page size locals can cause invalid access exceptions. Locals aligned to greater than page size can cause unsound behavior Mar 19, 2020
@Amanieu
Copy link
Contributor

@Amanieu Amanieu commented Mar 19, 2020

This is most likely an LLVM bug.

@retep998 retep998 added the A-LLVM label Mar 19, 2020
bors added a commit to rust-lang-ci/rust that referenced this issue Mar 20, 2020
Limit maximum alignment in #[repr(align)] to 4K

Let's try this on crater to see the impact.

cc rust-lang#70022 rust-lang#70143 rust-lang#70144
bors added a commit to rust-lang-ci/rust that referenced this issue Mar 20, 2020
Limit maximum alignment in #[repr(align)] to 4K

Let's try this on crater to see the impact.

cc rust-lang#70022 rust-lang#70143 rust-lang#70144
bors added a commit to rust-lang-ci/rust that referenced this issue Mar 20, 2020
Limit maximum alignment in #[repr(align)] to 4K

Let's try this on crater to see the impact.

cc rust-lang#70022 rust-lang#70143 rust-lang#70144
@RalfJung
Copy link
Member

@RalfJung RalfJung commented Apr 22, 2020

Could someone who knows the technical details here report this bug upstream with LLVM?

@spastorino spastorino added P-high and removed I-prioritize labels Jun 17, 2020
@LeSeulArtichaut
Copy link
Member

@LeSeulArtichaut LeSeulArtichaut commented Jun 17, 2020

@rustbot ping llvm

@rustbot
Copy link
Collaborator

@rustbot rustbot commented Jun 17, 2020

Hey LLVM ICE-breakers! This bug has been identified as a good
"LLVM ICE-breaking candidate". In case it's useful, here are some
instructions for tackling these sorts of bugs. Maybe take a look?
Thanks! <3

cc @camelid @comex @cuviper @DutchGhost @dyncat @hanna-kruppe @hdhoang @heyrutvik @JOE1994 @jryans @mmilenko @nagisa @nikic @Noah-Kennedy @SiavoshZarrasvand @spastorino @vertexclique

@ghost
Copy link

@ghost ghost commented Jul 12, 2020

I think this is platform-specific but it still all happens to varying degrees on x86(-64). This safe code causes a stack overflow on Ubuntu:

#[repr(align(0x800000))]
struct Aligned(usize);

fn main() {
    let x = Aligned(2);
    println!("{}", x.0);
}

This safe code causes a segfault on Ubuntu:

#[repr(align(0x10000000))]
struct Aligned(usize);

fn main() {
    let x = Aligned(2);
    println!("{}", x.0);
}

This isn't specific to Windows, then, and can be used to cause stack overflows and/or segfaults in safe code.

I don't know how this would be done, but maybe doing such alignments should only be allowed if unsafe is used to keep it out of safe code? Embedded might depend on high alignments, so I don't think removing the ability to align with high numbers entirely would be a good solution.

@RalfJung
Copy link
Member

@RalfJung RalfJung commented Jul 12, 2020

Note that we do install a stack guard and associated handler to check for stack overflows. So just getting a stack overflow or segfault does not necessarily demonstrate a problem. Rust cannot statically make sure that your stack is always big enough, so being able to trigger a stack overflow through big locals or deep recursion is entirely expected behavior.

The bug here is about the locals not having the alignment that was requested via repr. As far as I can see, your tests do not demonstrate that this happens here.

@retep998
Copy link
Member Author

@retep998 retep998 commented Jul 12, 2020

The bug here is about the locals not having the alignment that was requested via repr.

The locals do absolutely have the required alignment. The issue is with the stack aligning prologue which can cause the function's frame to exist entirely past the guard page so unrelated memory can be stomped on.

@cuviper
Copy link
Member

@cuviper cuviper commented Jul 13, 2020

I just tried this on godbolt: https://rust.godbolt.org/z/8xfn4v

#[repr(align(0x10000000))]
struct Aligned(usize);

pub fn foo() -> usize {
    Aligned(2).0
}

The output for x86_64-pc-windows-msvc:

example::foo:
        push    rbp
        mov     eax, 536870896    # 0x1ffffff0
        call    __chkstk
        sub     rsp, rax
        lea     rbp, [rsp + 128]
        and     rsp, -268435456    # 0xfffffffff0000000
        mov     qword ptr [rsp], 2
        mov     rax, qword ptr [rsp]
        lea     rsp, [rbp + 536870768]    # 0x1fffff70
        pop     rbp
        ret

In the worst case, the sub could move rsp to the very top of an aligned block, or anywhere more than a page size away from the aligned base. Then the large and will round this down, which might jump over the stack guard page, and this wasn't tested by __chkstk.

The output for x86_64-unknown-linux-gnu:

example::foo:
        push    rbp
        mov     rbp, rsp
        and     rsp, -268435456    # 0xfffffffff0000000
        mov     eax, 536870912    # 0x20000000
        call    __rust_probestack
        sub     rsp, rax
        mov     qword ptr [rsp], 2
        mov     rax, qword ptr [rsp]
        mov     rsp, rbp
        pop     rbp
        ret

Here the alignment is done first, but it's still bad. We might start with rsp more than a page size unaligned, and then again the large and can jump over the guard page. Then __rust_probestack could be probing non-stack memory and think everything is fine.

Here's one more Linux test I ran locally, using LLVM 11's "probe-stack"="inline-asm":

example::foo:
        pushq   %rbp
        movq    %rsp, %rbp
        andq    $-268435456, %rsp    # 0xfffffffff0000000
        movq    %rsp, %r11
        subq    $536870912, %r11    # 0x20000000
.LBB0_1:
        subq    $4096, %rsp
        movq    $0, (%rsp)
        cmpq    %r11, %rsp
        jne     .LBB0_1
        movq    $2, (%rsp)
        movq    (%rsp), %rax
        movq    %rbp, %rsp
        popq    %rbp
        retq

Again, the initial alignment could jump the guard page, then the probe loop may be clobbering non-stack memory.
(cc @serge-sans-paille)

@cuviper cuviper added the O-linux label Jul 13, 2020
@Amanieu
Copy link
Contributor

@Amanieu Amanieu commented Jul 13, 2020

It seems that the ideal behavior here would be to add the alignment to the size passed to __chkstk/__rust_probestack and perform the stack alignment masking after the stack probing.

@cuviper
Copy link
Member

@cuviper cuviper commented Jul 13, 2020

Yeah, I've been talking privately with Serge, and he's going to try implementing something like that.

@RalfJung
Copy link
Member

@RalfJung RalfJung commented Jul 14, 2020

I thought this is what already happens?

Aligning the stack is done after the stack probe.

And the fix would be to align first and then run the stack probe?

@retep998
Copy link
Member Author

@retep998 retep998 commented Jul 14, 2020

I thought this is what already happens?

Aligning the stack is done after the stack probe.

And the fix would be to align first and then run the stack probe?

The fix is to first probe the stack for the frame size plus the alignment, and then align the stack. Currently stack probes only check the frame size without adding the alignment to that size.

@cuviper
Copy link
Member

@cuviper cuviper commented Jul 14, 2020

Note that the size of the alignment adjustment is a dynamic value -- the offset from whatever incoming stack pointer we get to an aligned pointer below that. Then the actual frame size is allocated after we have known alignment. If the stack guard page is anywhere in that total range, we need to fault, which is what the probing does.

@RalfJung
Copy link
Member

@RalfJung RalfJung commented Jul 15, 2020

I guess I am wondering why we can't first align and then probe for the already computed new stack size, that sounds like it avoids doing the aligning twice. But it probably doesn't work for other reasons I cannot see.

@retep998
Copy link
Member Author

@retep998 retep998 commented Jul 17, 2020

@RalfJung Because after aligning the current stack pointer can be past the guard page in a completely unrelated section of memory, that could be completely valid memory for the full size of the stack frame that the stack probe could succeed on, but it's not our stack and we'd be trampling that unrelated memory!

We don't need to do the aligning twice as we can do a simple conservative stack probe of frame size + alignment, which is always sound, but it can trigger stack overflows when there is still a bit of space left. A smarter combination of stack probing + aligning can also avoid computing the aligned address twice, but might involve more implementation effort. Regardless of what technique we use, this only matters for functions with locals that are aligned to a page size or greater.

@RalfJung
Copy link
Member

@RalfJung RalfJung commented Jul 17, 2020

Ah I see, I somehow assumed stack probing would still have access to the old top-of-stack and could thus probe all the way from there to the aligned stack with the new frame.

@cuviper
Copy link
Member

@cuviper cuviper commented Jul 17, 2020

The examples I gave do have the old pointer in rbp. However, once we've moved rsp, a signal could be delivered and run its handler from that stack location, before we've probed that it's safe. For that matter, __chkstk and __rust_probestack need to have a valid stack to be called at all.

serge-sans-paille pushed a commit to llvm/llvm-project that referenced this issue Oct 2, 2020
…otection

As reported in rust-lang/rust#70143 alignment is not
taken into account when doing the probing. Fix that by adjusting the first probe
if the stack align is small, or by extending the dynamic probing if the
alignment is large.

Differential Revision: https://reviews.llvm.org/D84419
JohnHolmesII pushed a commit to JohnHolmesII/llvm-project that referenced this issue Oct 12, 2020
…otection

As reported in rust-lang/rust#70143 alignment is not
taken into account when doing the probing. Fix that by adjusting the first probe
if the stack align is small, or by extending the dynamic probing if the
alignment is large.

Differential Revision: https://reviews.llvm.org/D84419
serge-sans-paille pushed a commit to serge-sans-paille/llvm-project that referenced this issue Nov 5, 2020
…otection

As reported in rust-lang/rust#70143 alignment is not
taken into account when doing the probing. Fix that by adjusting the first probe
if the stack align is small, or by extending the dynamic probing if the
alignment is large.

Differential Revision: https://reviews.llvm.org/D84419
tstellar added a commit to tstellar/llvm-project that referenced this issue Nov 21, 2020
…otection

As reported in rust-lang/rust#70143 alignment is not
taken into account when doing the probing. Fix that by adjusting the first probe
if the stack align is small, or by extending the dynamic probing if the
alignment is large.

Differential Revision: https://reviews.llvm.org/D84419

(cherry picked from commit f2c6bfa)
tstellar added a commit to tstellar/llvm-project that referenced this issue Nov 25, 2020
…otection

As reported in rust-lang/rust#70143 alignment is not
taken into account when doing the probing. Fix that by adjusting the first probe
if the stack align is small, or by extending the dynamic probing if the
alignment is large.

Differential Revision: https://reviews.llvm.org/D84419

(cherry picked from commit f2c6bfa)
serge-sans-paille pushed a commit to serge-sans-paille/llvm-project that referenced this issue Dec 3, 2020
…otection

As reported in rust-lang/rust#70143 alignment is not
taken into account when doing the probing. Fix that by adjusting the first probe
if the stack align is small, or by extending the dynamic probing if the
alignment is large.

Differential Revision: https://reviews.llvm.org/D84419

(cherry picked from commit f2c6bfa)
arichardson added a commit to arichardson/llvm-project that referenced this issue Mar 24, 2021
…otection

As reported in rust-lang/rust#70143 alignment is not
taken into account when doing the probing. Fix that by adjusting the first probe
if the stack align is small, or by extending the dynamic probing if the
alignment is large.

Differential Revision: https://reviews.llvm.org/D84419
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
9 participants