Moving and reallocating the stack

[dethboy]

I am almost done builing a system that dectects stack overflow and then moves the stack to a larger free memory space etc.
Through all my research i didn't really come across any mention of doing this.
Is what i am doing a fools errand and i am missing something on a basic level?
just looking for opinions here.

[dchapiesky]

could you clarify...

does your system work at the application level (ring 3) or at the OS level (ring 0) or a mixture therein...?

it sounds promising to me but not because of stack protection - rather in terms of security....

a periodic moving of the stack of a running process would play merry hell with such things a return oriented programming etc....

also in terms of debugging....

moving the stack of an application and then marking the old stack as a page fault would allow you to detect when an application accesses stale data or attempts to write to stale data...

I say keep at it and good work so far...

cheers

[BrightLight]

Personally, I have no system for reallocating a stack. I provide each application with 64 KB of stack space, and when it overflows, it just page-faults and so the faulting application is terminated by the kernel. If you want though, you'd reallocate the stack by allocating memory, copying the current stack content to the end of the allocated memory, and setting the task's ESP to the end of that memory.

For example, consider a sample 64 KB stack from 0x00000 to 0x10000 has overflowed, and you want to resize it to 128 KB. You'd allocate memory, using malloc or whatever, let's assume malloc returns 128 KB at 0x10000 to 0x30000. You'd copy the content of the memory range 0x00000-0x10000 to the memory range of 0x10000-0x30000. And then you need to set the task's ESP, which would be the same offset into the stack, but using the new stack as a base.

I don't guarantee this to work though, as for example, consider the following routine.

Code: Select all

routine:
	push ebp
	mov ebp, esp
	add ebp, 8

	push ebx
	push ecx
	push edx

	; read parameters using i386 ABI from the stack
	mov eax, [ebp]		; first parameter
	mov ebx, [ebp+4]	; second parameter

	; do some useful function here

Let's assume the stack overflows at the PUSH EBX instruction. The kernel transparently allocates a new stack and the application is not aware of it. It then pushes ECX and EDX and then tries to read function parameters from the stack using EBP, which in turn points to the old stack, which may or may not be valid. Thus, this as well may page fault and is an issue for you to figure out on your own.

[Brendan]

Hi,

I am almost done builing a system that dectects stack overflow and then moves the stack to a larger free memory space etc.
Through all my research i didn't really come across any mention of doing this.
Is what i am doing a fools errand and i am missing something on a basic level?
just looking for opinions here.

My primary concern would be pointers to local variables. You can't relocate a stack without finding all of these pointers and updating them; and that makes it "extremely impractical" to relocate a stack without full language support (e.g. a managed language). For example:

Code: Select all

void foo(void) {
    int myArray[1234];

    foo(&myArray[33]);
}

void foo(int *myPointer) {
    /* Stack gets relocated here, but what does "myPointer" point to? */

More practical would be extending the stack but not relocating it (and not causing problems for pre-existing pointers).

Even more practical would be to reserve a large enough area of the virtual address space (that isn't so large that it fails to protect against problems like "infinite recursion") and then allocate pages in this area if/when needed. This can be done with some page fault handler trickery such that the program itself doesn't need to know or care if/when more RAM is allocated for its stack. This is the method that most OSs use.


Cheers,

Brendan

[dethboy]

Thanks brendan, pointers to local vars is something i had overlooked i will have to look into that

To answer questions from above:
the system is currently on the kernel level, but i have plans to use it (if i can deal with the problem mentioned above)

[iansjack]

How do you use malloc() if your stack has overflowed?

The answer given above - extend the stack by page-faulting and allocating another page to it - is the way to go. If you are using long mode there is plenty of logical address space to set aside for the stack so that it can be extended as far as you would reasonably want; and each process can use the same address space. This also means that your initial stack can be fairly small - you don't need to allocate a large stack area in physical memory for each process.

Note that you should allocate a separate, small stack for the page-fault handler to use so that you can always be sure that it has a valid stack to work with. You can easily calculate exactly how much stack space your page-fault handler needs.

[dethboy]

okay, i have discovered that passing the address to a local variable doesn't work even with no relocation

to explain this let me describe what i am doing:

upon getting control from the boot loader the kernel constructs a map of all the free areas in memory (from the map left by the GRUB bootloader)
this is used for deciding where to place various things in the memory and how to size them
so in this table i allocate 1k for the stack and then i set the stack segment to just this 1k area
when the stack overflows a stack segment fault (0xc) is issued
this causes a task switch to a TSS i have set up to handle the stack reallocation

so the stack is set up to be at 0x1000 to 0x1400

now in the complied c code when i pass the address of a local var it passes the address relative to the SS, tet's say 0x3c0 in stead of 0x13c0
when you try to dereference the pointer in the second function it is relative to the DS so you come up with the wrong value.

now i am pondering if that is something i should worry about, while passing the address is legal for the discussions i am reading some people feel that it is a highly discouraged practice

[Brendan]

okay, i have discovered that passing the address to a local variable doesn't work even with no relocation

to explain this let me describe what i am doing:

upon getting control from the boot loader the kernel constructs a map of all the free areas in memory (from the map left by the GRUB bootloader)
this is used for deciding where to place various things in the memory and how to size them
so in this table i allocate 1k for the stack and then i set the stack segment to just this 1k area
when the stack overflows a stack segment fault (0xc) is issued
this causes a task switch to a TSS i have set up to handle the stack reallocation

so the stack is set up to be at 0x1000 to 0x1400

now in the complied c code when i pass the address of a local var it passes the address relative to the SS, tet's say 0x3c0 in stead of 0x13c0
when you try to dereference the pointer in the second function it is relative to the DS so you come up with the wrong value.

now i am pondering if that is something i should worry about, while passing the address is legal for the discussions i am reading some people feel that it is a highly discouraged practice

This problem (which is unrelated to stack relocation) is that GCC doesn't support for segmentation, expects that "DS.base == ES.base == SS.base" and that segment limits can be ignored, and ends up using whatever the default segment happens to be for various instructions (e.g. SS for "mov eax,[ebp], DS for "mov eax,[edx]" and ES for the destination of "rep movsd") without caring what that default segment might be for an instruction.

To fix this problem you'll probably have to ensure "DS.base == ES.base == SS.base" and that the limits for these segments are all higher than any offset ("pointer"). The simplest way is to create a "base = 0, limit = 4 GiB" descriptor and load that into DS, ES and SS; effectively disabling segmentation for normal data accesses.

The alternatives (if you really want to use segmentation) is to find an old compiler that supports it, use assembly language exclusively, or write a compiler. Modern compilers (and the operating systems they're designed for) use "flat paging" (and don't use segmentation, except for a few special cases - FS and GS for things like thread local storage).


Cheers,

Brendan

[dethboy]

hah, i knew there was a flaw in my thinking, no loss learned a lot by doing it

[LtG]

Why would the OS ever want to reallocate the stack of some app? And if we don't reallocate, why would we need to move the stack?

Using demand paging for the stack (like the rest of the memory) is a useful trick, but no reallocation is needed for it.

The only thing I can think of is to give apps a kind of "infinite" stack, but is that actually a good thing? I'd rather have it bounded and cause app crash when out of bounds access is attempted, same as heap. Or are you creating kind of "infinite" heap also, where any user space memory reference is accepted and automatically mapped? Doing so has some benefits but you lose program "correctness" in that you can't enforce valid memory references.

I'd have the binary file format specify needed stack size and/or allowing apps to do it themselves (ie. app allocates extra heap somewhere and just changes stack to it), thus no kernel support needed, and managed languages can then also do "pointer rebasing" like Brendan mentioned.

Note also that if you absolutely want to do this, then why not put heap at beginning of user address space and stack at the end and allow stack to be resized? When the two collide I doubt you'd ever find large enough free address space somewhere in the middle of the heap due to fragmentation. Also I'd much rather leave all of this to the userspace which means simpler kernel and more flexibility to any potential language runtime to do whatever it wants.

[mallard]

You might find this interesting...

There is a feature in new-ish versions of GCC* (and LLVM) called "split stacks" that allows the stack to be non-contiguous. That means that when you run out of stack space, you can allocate additional space anywhere in memory and have the stack pointer "jump" seamlessly between the different "stacklets".

*Despite the above article being written as a proposal and other documentation being fairly sparse, the feature exists in GCC from version 4.6.

[Boris]

The good thing i see with that is , you can have virtual stack pages allowed in upward direction, by 4kb chunks, but the stack sarts at the top of each page.

[samiam95124]

Don't relocate your stack. It has all kinds of addresses embedded in it that won't appreciate your moving it.

You can allocate pages below the stack as they are read/written in a virtual page system, but be aware that programs can leap any page allocation you have. If a C function or whatever allocates a local of 64kb, you have leapt over 16 4kb pages without touching them.

Opinion: if you are in a demand page virtual environment, stop trying to manage your users stacks. Yea I know it is popular, but leave that to the C compiler (or whatever). Just allocate sparse pages and leave it to the program how to use it. This stuff about asking the OS permission to create a stack makes no sense at all.

Scott Franco
San Jose, CA