Protecting from stack overflow in recursive functions.

[vi]

Suppose you have some recursive function:

fn recursee(n: i64) -> Result<i64, ()> {
    if n > 0 {
        Ok(1+ try!(recursee(n-1)))
    } else {
        Ok(0)
    }
}

fn main() {    
    println!("{:?}", recursee(3));
    println!("{:?}", recursee(100));
    println!("{:?}", recursee(999999999));
    println!("{:?}", recursee(5000));
}

It works for small values (that you need). But attacker can supply special unbalanced bad data that cause stack overflow. Getting rid of recursion requires big redesign and regretting about committing the "Let's use clever recursion here" idea. What if we can just add a direct protection against stack overlow?

#![feature(asm)]

fn sp() -> usize {
    let sp : usize;
    unsafe {
        asm!("":"={esp}"(sp):::"volatile");
    }
    sp
}


static mut near_stack_top : usize = 0;

fn get_stack_gauge() -> f64 {

    let stack_size = if cfg!(target_env="musl") { 0x18000 } else { 0x800000 };

    let (s, st, ss) = (sp() as f64, unsafe { near_stack_top } as f64, stack_size as f64);

    (st - s) / ss
}


fn recursee(n: i64) -> Result<i64, ()> {
    if get_stack_gauge() > 0.95 {
        // stack overflow is nearing
        return Err(());
    }

    if n > 0 {
        Ok(1+ try!(recursee(n-1)))
    } else {
        Ok(0)
    }
}

fn main() {
    unsafe { near_stack_top = sp(); }

    println!("{:?}", recursee(3));
    println!("{:?}", recursee(100));
    println!("{:?}", recursee(999999999));
    println!("{:?}", recursee(5000));
}

Ok(3)
Ok(100)
Err(())
Ok(5000)

Maybe functions for being aware of how much stack is still available should be a bit closer to language, so there can be

fn get_stack_gauge() -> f64 {
    (::std::stack:remaining() as f64) / (::std::stack::size() as f64)
}

?

Alternative ideas:

• Special macro like try_recurse!(recursee(n)) that tries to check if there enough stack for calling and throws othewise;

[jonas-schievink]

https://crates.io/crates/stacker/ looks like something similar to what you're describing

[vi]

Shall I move the issue to stacker? Maybe it can provide more than one function to allow checking for stack without growing it.

[alexcrichton]

Yeah I agree with @jonas-schievink in that I think this should probably grow outside the standard library (perhaps on crates.io), and I think that the stacker crate provides a good way in for now!

[byronmejia]

Late bloomer here.
Is this an issue when you write a tail call optimised function?

[tupshin]

Neither rustc nor llvm currently guarantee any tail optimization, so writing a function that you think should be TCO often isn't
See #271
To answer your question, though, this should not happen if the function is tail call optimized

[byronmejia]

Thank you, @tupshin

[darakian]

Another late bloomer here. Is stacker the advised solution for now? Is TCO coming at some point?

[hasufell]

Not sure a separate crate is what you want here, because you could argue rust is memory unsafe if this is not protected against.

[nagisa]

Stack probes ensure that stack overflows do not ensure in memory safety holes.

…

On Mon, Oct 29, 2018, 06:40 Julian Ospald ***@***.***> wrote: Not sure a separate crate is what you want here, because you could argue rust is memory unsafe if this is not protected against. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1488 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AApc0svArTGXoELtv9P6Uel2t94RcLuBks5upobagaJpZM4HShTE> .

[redengin]

For most functions, the stack depth can be structurally determined and therefore the Rust compiler could assert correctness. When the compiler can not know the stack depth required, a warning could be emitted. Additionally a decorator could be optionally added to a method to describe the expected stack depth max, and a runtime check be instrumented.

[mimoo]

I found several DoS attacks due to recursive functions in the past, so that's something I'm really interested in