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).

Inflation

Maybe this will help #6552641 – Strappado

Is stack underflow a problem? Would that not, (almost certainly), segfault/AV the thread running it at the next function return? – Sine

@Martin: That is exactly what I want to test. – Inflation

Also: 'test security measures in my system'....But C would be more portable'. Why would it matter if the mechanism is non-portable? – Sine

What exactly is a stack underflow here? Performing a "ret" instruction while there is no valid return address under the stack pointer? Or the stack pointer pointing to unmapped memory? For both scenarios I do not see much gain in testing these, the situation is quite clear: Either the program segfaults when trying to access unmapped memory or it tries to execute opcodes at an arbitrary location in process memory. – Anglaangle

@Ctx: 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). – Inflation

Does allocating a stack and that freeing portion of it counts? You can do it via pthread_attr_setstackaddr on Posix (or directly via clone) and allocating/freeing via map/unmap. – Quirt

Well, on x86, you could call a __stdcall function through a pointer to a __cdecl function, but that's not "portable". – Hailee

I think @Hailee 's comment may actually be the closet to the exact answer Silicomancer is looking for, based on Silicomancer's last comment precisely defining what a stack underflow is in this context. – Ec

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.

Hyps

But scopes-within-scopes-within-scopes behaves as a stack. A stack is often a hardware supported feature but is primarily a data structure. – Godless

@PaulOgilvie There are for example (micro-)platforms, which only support nesting 3 scopes or so on three fixed locations. Is that already considered a stack? If not, how many scopes are needed? This gets philosophical... ;) – Anglaangle

@Ctx: a stack in always finite on real computers. But 3 slots is really a small one :-). – Salisbarry

@PaulOgilvie Calling one function from another is not a scope within a scope. In any case, the question is clearly talking about a traditional computer stack. – Hyps

A scope probably has meaning in different contexts: during translation there is the scope of names; during the execution there is the scope of variable values (e.g. recursion). The first behaves a bit like a stack but is not; the second behaves a stack and could be implemented as a stack. – Godless

@PaulOgilvie "could be implemented as a stack". But not necessarily the stack. You are right that there are different forms of scoping. There's static scoping, which refers to the way scopes are nested within the source code and dynamic scoping which is about how they are organised in memory during execution. Logically they are stacked, but you do not have to use a traditional computer stack to organise them. A linked list would work, for example. – Hyps

So the linked list would behave as a stack? Then you have a stack, though not a hardware supported stack (unless the implementation would have hardware supported linked lists) – Godless

@PaulOgilvie Do you know of such an architecture? – Hyps

Is writing to a register-indexed memory location with post-increment/pre-decrement already a hardware stack? Is it a hardware stack if you increment/decrement the register manually after the memory access? It is hard to differentiate exactly here in any case. – Anglaangle

Alternative scenario: There is more than one stack. For instance cc65, a C compiler for 6502 based systems which uses the 256 byte hardware stack of a 6502 processor for return addresses and a separate software stack for argument passing. – Callow

A call stack (whether it's accessed through the official “stack pointer” register, or elsewhere) is only necessary if you have (non-tail) recursive or mutually-recursive function calls. If you don't, then there's nothing in the C standard that would prevent the compiler from just making all your variables static. – Hailee

@Hailee True, but nothing in the C standard prevents a program from having recursive function calls. Any data structure used to track the currently active scopes in a C program must have the logical properties of a stack i.e. last in first out semantics. However, everything else about that data structure is left to the implementation. This means there is no portble way to induce stack underflow. – Hyps

@Hyps It's stronger than "nothing prevents": there is an explicit requirement to support recursion (§6.5.2.2p11) and to create new copies of variables with automatic storage duration for each recursive invocation (6.2.4p6). (Links are to N1570, but these requirements existed in C89, possibly in slightly different locations.) Even in C11 with threads, though, the word "stack" appears nowhere in the text. – Suborder

Answer 2

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.

Innes

The second part is misleading. What you can do in [standard] C is to trigger undefined behavior and make assumptions what happens on your implementation. – Goosy

@Goosy What are you on about? Undefined behavior is a C language term and there's no undefined behavior anywhere in this code. What will happen when you write to a different memory region than the stack is by no means covered by the C standard. On some systems you may get a hardware exception. On other systems you may overwrite other RAM memory. On yet some other system, absolutely nothing will happen since there is no valid RAM at that location. And so on. This has everything to do with the specific system and absolutely nothing to do with the C standard. – Innes

Oh, yes, there's UB in the code: The moment you dereference p, which is a pointer to a memory region that you didn't allocate with malloc() and which is not the address of an automatic variable, etc. – Wort

@cmaster That's nonsense. If that was true, then we wouldn't be able to access memory mapped registers of hardware peripherals in C. Which we obviously can, and which is done on billions of microcontrollers every day. – Innes

That's implementation defined behavior at best. C does not know anything about memory mapped hardware. Of course, a lot that is done to create the illusion of the C machine is implementation defined behavior at its roots. This includes stuff like syscalls: You simply cannot perform a syscall in C, you absolutely need tricks like inline assembler for that. And unless your implementation defines that there is indeed a uint8_t stored at 0x1000, accessing *p is undefined. – Wort

@cmaster This is what I'm saying, it is beyond the scope of the C standard. Just as the C standard does not label me having a cup of coffee right now as "undefined behavior", because that's no business of a programming language standard. Now what the C standard actually says is (C11 6.5.6) that we cannot do pointer arithmetic on a pointer which does not point at an array, where the array can have any form of storage duration (not specified). Don't mix this up with simple access of any memory location. – Innes

Added some additional information about what the standard actually says, before someone else decides to post subjective speculations, without actual proof or quotes from the standard. – Innes

@Lundin: Accessing a memory-mapped register very much is Undefined Behavior. And unlike the proverbial nasal deamones, the effect of memory-mapped register writes (and even reads) has been considered by the C and C++ committees. It is understood that there is no realistic bound on how hardware can behave if you do that, including causing irreversible damage. For that reason, the Standard does not even require the implementation to define what will happen with an out-of-bounds memory access. – Gallantry

But note that leaving the Behavior Undefined has the convenient side-effect of actually allowing any behavior when writing to a memory-mapped register. C would constrain microcontrolllers unnecessarily if it had required a signal when writing out of bounds. – Gallantry

@Innes "Among" means precisely that the list is not exhaustive. – Crossbeam

"What you can do in C is to purposely write out of bounds of the stack" doesn't make sense. You can write C code with undefined behaviour that some implementation might happen to write out of bounds of the stack but that depends on the implementation. You can "Suppose we know that the stack starts at 0x1000 and grows upwards" but the standard tells you nothing about that. How is it you think that "by no means covered by the C standard" is different from "undefined behaviour"? (Rhetorical.) You really don't understand the way the standard defines and abstract machine. – Bricabrac

@Bricabrac Again, the standard tells nothing about it because it is out of scope of a programming language standard. I can have a cup of coffee just fine, even though the C standard does not mention coffee at all. What you don't understand is the difference between chapter 1 of the C standard "scope", and chapter 3, that specifies terms of things that are in scope. If something is not covered by chapter 1 of the standard, then the standard does not apply. Period. – Innes

@Lundin: I believe you are wrong. A simpler example ((int *)3) = 0;. The C standard does not define how a program with such a statement should behave - it is undefined behaviour. On quite a lot of systems it will trap either for access violation or unaligned access; on others it will rewrite a couple of interupt vectors. It is definitely not implementation specified or implementation dependant. – Built

@MartinBonner The standard does specify that the code you just posted is a constraint violation of the rules of simple assignment, C11 6.5.16.1. Assuming that you actually meant *((int *)3) = 0;, then the C standard does explicitly specify what will happen, C11 6.3.2.3/5. It is explicitly implementation-defined behavior and not undefined behavior. – Innes

Now kindly stop wasting my time with these factually incorrect comments that completely lack references. – Innes

@Lundin: (I did indeed mean the version with pointer). The section you referenced says "An integer may be converted to any pointer type. Except as previously specified, the result is implementation-defined, ...." So yes, the mapping of integers to pointers is implementation defined. The result of assigning through such pointers is undefined. I can't quote a reference for that, because it is not explicitly called out as undefined, it is just isn't ... defined. – Built

@MartinBonner That's because it is covered in chapter 1 of the C standard, specifically: "This International Standard does not specify — the mechanism by which C programs are transformed for use by a data-processing system;". Similarly, you won't find the act of drinking coffee in-scope either. This means that you should stop reading, the thing you are looking for is not covered by this standard. Whereas the term undefined behavior is a term used inside the standard for: "nonportable or erroneous program construct or of erroneous data" in a context that is within scope of the standard. – Innes

@Lundin: You really don't get it, do you? *((int*)3) = 0; is "a nonportable construct for which the C standard imposes no requirements". It is undefined behaviour. That's fine, it may be perfectly useful, but it is undefined. – Built

@MartinBonner Actually I start to think that Lundin is right, because the part you qoute (Except as previously specified, the result is implementation-defined) means that a perfectly valid pointer is an option, too... – Goosy

@Goosy No he isn't. You are right that a perfectly valid pointer is an option - but "working just as the programmmer hoped" is one of the possible manifestations of UB. UB doesn't mean "does not work", it means "is not required to work by the standard". – Built

Answer 3

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.

Signac

Answer 4

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.

Futrell

Note there is a risk here, in that this level of transparent undefined behavior may result in interesting "optimizations" by the compiler, including not calling underflow at all. – Lindblad

If volatile was not present the entire thing could be reduced to just return 0. However, the keyword forces the compiler to generate all the accesses. The most it can do is inline underflow and convert the loop to memset, which has a very similar result (depth of stack corruption changes relative to the beginning of the stack). – Futrell

No, undefined behavior is undefined behavior even if you add volatile. Accessing outside the bounds of the array is undefined behavior. Your compiler may be nice and do what you think you are asking it to do, but that is not mandated by the standard. Heck, creating the pointer pointing outside of the array is undefined behavior, let alone accessing it! And undefined behavior can time-travel or do anything. I'm not saying it doesn't work, I'm saying there is a real risk (which is basically unavoidable). – Lindblad

Well of course in principle it can do absolutely anything, including deleting all the porn. But that's not something which is going to happen. I don't see how realistically it can end up not producing the underflow. – Futrell

@Yakk Normally I'd be the one insisting that you can't make any assumptions about undefined behavior, but in this case, there's no way to do this without invoking undefined behavior, so the best option you have is to write the code in such a way that the compiler is unlikely to optimize anything (and including a volatile and compiling with -O0 is a good start), then manually check the generated assembly to see if it does what you want it to. The UB means you can't guarantee that the generated assembly will contain that loop, but if it does, this will probably work. – Smriti

@Smriti Agreed. I'm just saying that this answer, while the most reasonable and correct one here, doesn't say any of that. It just presents it as something that will work. There is a danger here, an unavoidable one, and the machine code output of compiling this code has to be validated every time you build it. Some innocuous compiler upgrade, or a myraid of other things, could make it do something completely different, because it relies on undefined behavior acting exactly like you want. – Lindblad

@Yakk Sounds like we're in complete agreement, then. employeeofthemonth, it'd be a good idea to mention those caveats in the answer. – Smriti

If you make the i counter volatile too, then there'll be no way for the compiler to know that subscripting will go out of bounds, thus no way to optimize this to something strange. – Not

@Ruslan: Actually, there are a few compilers that in non-optimized "debug" builds will include array bound checks. This code is relying on a compiler that neither optimizes aggressively nor uses run-time checks. – Gallantry

"In practice" is a poor and misleading way to say "for a certain implementation". – Bricabrac

All of this criticism seems to miss the point, to me: This program doesn't cause stack underflow. It overwrites data on the stack next to an automatic variable, perhaps including the return address for underflow and causing the program counter jump into the weeds, but it does nothing that would move the actual stack pointer past either end of the stack area. – Suborder

Answer 5

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])

Myronmyrrh

This won't wrap the pointer around on 64 bit platforms with 32 bits unsigned long. Even size_t might not be large enough, although it is a better bet. Also, the compiler may know an upper bound for argc so it might prove the VLA allocation will fail unconditionally. – Gallantry

@msalters True. I had intended to swap the long to a uintptr_t before publishing but I forgot to do so while testing the solution. I haven’t seen a compiler figure out whether a VLA allocation will fail or not - in principle, there’s nothing stopping me from having an execution environment with a 2^64 GB “stack”. – Myronmyrrh

Note that I'm only assuming here that uintptr_t has sufficient range to underflow a pointer, which is true on most sane platforms. If your platform is sufficiently strange that the stack pointer has a different size than uintptr_t, well, I did say this hack was UB by definition ;) – Myronmyrrh

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.

Goober

Answer 7

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.

Intramundane

The -x c option will tell g++ to compile as C. – Grethel

Thanks, updated the godbolt link, other than the symbol names I couldn't see any difference between C and C++ output. – Intramundane

This does not appear to be "underflow" as defined by the OP: "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)". The address in a is somewhere after the base of the stack, not before it. – Slattern

The "a" in foo/bar is not actually used for anything, it's just there to force the compiler to allocate a bunch of space on the stack. The "a" in main is a code address not a data address. – Intramundane

The point of the array is to make "foo" have a large stack frame, so that when we jump into it we deallocate a large stack frame that was never allocated causing the underflow. – Intramundane

Answer 8

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.

Jeepers

This doesn't underflow the stack, which as I understand is actually popping more elements than where pushed before. And of course there has to be a stack in the first place, which is not guaranteed by the language specs. See the other answers. – Callow

Answer 9

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! :-)

Scientific

He - obviously - is looking for a stack underflow, as stated. :) – Lonee

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.

Jeepers