Provoke stack underflow in C

Question

I would like to provoke a stack underflow in a C function to test security measures in my system. I could do this using inline assembler. But C would be more portable. However I can not think of a way to provoke a stack underflow using C since stack memory is safely handled by the language in that regard.

So, is there a way to provoke a stack underflow using C (without using inline assembler)?

As stated in the comments: Stack underflow means having the stack pointer to point to an address below the beginning of the stack ("below" for architectures where the stack grows from low to high).

Answer 1

There's a good reason why it's hard to provoke a stack underflow in C.The reason is that standards compliant C does not have a stack.

Have a read of the C11 standard, you'll find out that it talks about scopes but it does not talk about stacks. The reason for this is that the standard tries, as far as possible, to avoid forcing any design decisions on implementations. You may be able to find a way to cause stack underflow in pure C for a particular implementation but it will rely on undefined behaviour or implementation specific extensions and won't be portable.

Answer 2

Regarding already existing answers: I don't think that talking about undefined behaviour in the context of exploitation mitigation techniques is appropriate.

Clearly, if an implementation provides a mitigation against stack underflows, a stack is provided. In practice, void foo(void) { char crap[100]; ... } will end up having the array on the stack.

A note prompted by comments to this answer: undefined behaviour is a thing and in principle any code exercising it can end up being compiled to absolutely anything, including something not resembling the original code in the slightest. However, the subject of exploit mitigation techniques is closely tied to the target environment and what happens in practice. In practice, the code below should "work" just fine. When dealing with this kind of stuff you always have to verify generated assembly to be sure.

Which brings me to what in practice will give an underflow (volatile added to prevent the compiler from optimising it away):

static void
underflow(void)
{
    volatile char crap[8];
    int i;

    for (i = 0; i != -256; i--)
        crap[i] = 'A';
}

int
main(void)
{
    underflow();
}

Valgrind nicely reports the problem.

Answer 3

You can't do this in C, simply because C leaves stack handling to the implementation (compiler). Similarly, you cannot write a bug in C where you push something on the stack but forget to pop it, or vice versa.

Therefore, it is impossible to produce a "stack underflow" in pure C. You cannot pop from the stack in C, nor can you set the stack pointer from C. The concept of a stack is something on an even lower level than the C language. In order to directly access and control the stack pointer, you must write assembler.

---

What you can do in C is to purposely write out of bounds of the stack. Suppose we know that the stack starts at 0x1000 and grows upwards. Then we can do this:

volatile uint8_t* const STACK_BEGIN = (volatile uint8_t*)0x1000;

for(volatile uint8_t* p = STACK_BEGIN; p<STACK_BEGIN+n; p++)
{
  *p = garbage; // write outside the stack area, at whatever memory comes next
}

Why you would need to test this in a pure C program that doesn't use assembler, I have no idea.

---

In case someone incorrectly got the idea that the above code invokes undefined behavior, this is what the C standard actually says, normative text C11 6.5.3.2/4 (emphasis mine):

The unary * operator denotes indirection. If the operand points to a function, the result is a function designator; if it points to an object, the result is an lvalue designating the object. If the operand has type ‘‘pointer to type’’, the result has type ‘‘type’’. If an invalid value has been assigned to the pointer, the behavior of the unary * operator is undefined 102)

The question is then what's the definition of an "invalid value", as this is no formal term defined by the standard. Foot note 102 (informative, not normative) provides some examples:

Among the invalid values for dereferencing a pointer by the unary * operator are a null pointer, an address inappropriately aligned for the type of object pointed to, and the address of an object after the end of its lifetime.

In the above example we are clearly not dealing with a null pointer, nor with an object that has passed the end of its lifetime. The code may indeed cause a misaligned access - whether this is an issue or not is determined by the implementation, not by the C standard.

And the final case of "invalid value" would be an address that is not supported by the specific system. This is obviously not something that the C standard mentions, because memory layouts of specific systems are not coverted by the C standard.

Answer 4

Is it possible to do it reliably in standard compliant C? No

Is it possible to do it on at least one practical C compiler without resorting to inline assembler? Yes

void * foo(char * a) {
   return __builtin_return_address(0);
}

void * bar(void) {
   char a[100000];
   return foo(a);
}

typedef void (*baz)(void);

int main() {
    void * a = bar();
    ((baz)a)();
}

Build that on gcc with "-O2 -fomit-frame-pointer -fno-inline"

https://godbolt.org/g/GSErDA

Basically the flow in this program goes as follows

• main calls bar.
• bar allocates a bunch of space on the stack (thanks to the big array),
• bar calls foo.
• foo takes a copy of the return address (using a gcc extension). This address points into the middle of bar, between the "allocation" and the "cleanup".
• foo returns the address to bar.
• bar cleans up it's stack allocation.
• bar returns the return address captured by foo to main.
• main calls the return address, jumping into the middle of bar.
• the stack cleanup code from bar runs, but bar doesn't currently have a stack frame (because we jumped into the middle of it). So the stack cleanup code underflows the stack.

We need -fno-inline to stop the optimiser inlining stuff and breaking our carefully laid-down strcture. We also need the compiler to free the space on the stack by calculation rather than by use of a frame pointer, -fomit-frame-pointer is the default on most gcc builds nowadays but it doesn't hurt to specify it explicitly.

I belive this tehcnique should work for gcc on pretty much any CPU architecture.

Answer 5

There is a way to underflow the stack, but it is very complicated. The only way that I can think of is define a pointer to the bottom element then decrement its address value. I.e. *(ptr)--. My parentheses may be off, but you want to decrement the value of the pointer, then dereference the pointer.

Generally the OS is just going to see the error and crash. I am not sure what you are testing. I hope this helps. C allows you to do bad things, but it tries to look after the programmer. Most ways to get around this protection is through manipulation of pointers.

Answer 6

This assumption:

C would be more portable

is not true. C doesn't tell anything about a stack and how it is used by the implementation. On your typical x86 platform, the following (horribly invalid) code would access the stack outside of the valid stack frame (until it is stopped by the OS), but it would not actually "pop" from it:

#include <stdarg.h>
#include <stdio.h>

int underflow(int dummy, ...)
{
    va_list ap;
    va_start(ap, dummy);
    int sum = 0;
    for(;;)
    {
        int x = va_arg(ap, int);
        fprintf(stderr, "%d\n", x);
        sum += x;
    }
    return sum;
}

int main(void)
{
    return underflow(42);
}

So, depending on what exactly you mean with "stack underflow", this code does what you want on some platform. But as from a C point of view, this just exposes undefined behavior, I wouldn't suggest to use it. It's not "portable" at all.

Answer 7

By definition, a stack underflow is a type of undefined behaviour, and thus any code which triggers such a condition must be UB. Therefore, you can't reliably cause a stack underflow.

That said, the following abuse of variable-length arrays (VLAs) will cause a controllable stack underflow in many environments (tested with x86, x86-64, ARM and AArch64 with Clang and GCC), actually setting the stack pointer to point above its initial value:

#include <stdint.h>
#include <stdio.h>
#include <string.h>
int main(int argc, char **argv) {
    uintptr_t size = -((argc+1) * 0x10000);
    char oops[size];
    strcpy(oops, argv[0]);
    printf("oops: %s\n", oops);
}

This allocates a VLA with a "negative" (very very large) size, which will wrap the stack pointer around and result in the stack pointer moving upwards. argc and argv are used to prevent optimizations from taking out the array. Assuming that the stack grows down (default on the listed architectures), this will be a stack underflow.

strcpy will either trigger a write to an underflowed address when the call is made, or when the string is written if strcpy is inlined. The final printf should not be reachable.

---

Of course, this all assumes a compiler which doesn't just make the VLA some kind of temporary heap allocation - which a compiler is completely free to do. You should check the generated assembly to verify that the above code does what you actually expect it to do. For example, on ARM (gcc -O):

8428:   e92d4800    push    {fp, lr}
842c:   e28db004    add fp, sp, #4, 0
8430:   e1e00000    mvn r0, r0 ; -argc
8434:   e1a0300d    mov r3, sp
8438:   e0433800    sub r3, r3, r0, lsl #16 ; r3 = sp - (-argc) * 0x10000
843c:   e1a0d003    mov sp, r3 ; sp = r3
8440:   e1a0000d    mov r0, sp
8444:   e5911004    ldr r1, [r1]
8448:   ebffffc6    bl  8368 <strcpy@plt> ; strcpy(sp, argv[0])

Answer 8

Do you mean stack overflow? Putting more things into the stack than the stack can accomodate? If so, recursion is the easiest way to accomplish that.

void foo();
   {foo();};

If you mean attempting to remove things from an empty stack, then please post your question to the stackunderflow web site, and let me know where you've found that! :-)

Answer 9

It is not possible to provoke stack underflow in C. In order to provoke underflow the generated code should have more pop instructions than push instructions, and this would mean the compiler/interpreter is not sound.

In the 1980s there were implementations of C that ran C by interpretation, not by compilation. Really some of them used dynamic vectors instead of the stack provided by the architecture.

stack memory is safely handled by by the language

Stack memory is not handled by the language, but by the implementation. It is possible to run C code and not to use stack at all.

Neither the ISO 9899 nor K&R specifies anything about the existence of a stack in the language.

It is possible to make tricks and smash the stack, but it will not work on any implementation, only on some implementations. The return address is kept on the stack and you have write-permissions to modify it, but this is neither underflow nor portable.

Answer 10

So there are older library functions in C which are not protected. strcpy is a good example of this. It copies one string to another until it reaches a null terminator. One funny thing to do is pass a program that uses this a string with the null terminator removed. It will run amuck until it reaches a null terminator somewhere. Or have a string copy to itself. So back to what I was saying before is C supports pointers to just about anything. You can make a pointer to an element in the stack at the last element. Then you can use the pointer iterator built into C to decrement the value of the address, change the address value to a location preceding the last element in the stack. Then pass that element to the pop. Now if you are doing this to the Operating system process stack that would get very dependent on the compiler and operating system implementation. In most cases a function pointer to the main and a decrement should work to underflow the stack. I have not tried this in C. I have only done this in Assembly Language, great care has to be taken in working like this. Most operating systems have gotten good at stopping this since it was for a long time an attack vector.