Easily and Permanently prevent all stack buffer overflows

xi4oyu wrote:
> On 11 14 , 12 31 , Wayne <nos... DeleteThis @all4me.invalid> wrote:
>> I've often wondered why Linux (or any OS) puts up with
>> stack buffer overflows. They only happen because
>> the stack grows in one direction and buffers grow
>> in the other:
>>
>> +----------------------------------------------------+
>> | unused stack space | buf | ... | return_addr | ... |
>> +----------------------------------------------------+
>> Lower memory address ----> Higher memory address
>>
>> where buf is some local char array. A buffer
>> overflow (in the case, there are heap attacks too)
>> is only possible if a user over-writes the return
>> address or some other part of the "lower" stack
>> contents.
>>
>> So why doesn't any OS define the stack growth in the
>> other direction:
>>
>> +----------------------------------------------------+
>> | ... | return_addr | ... | buf | unused stack space |
>> +----------------------------------------------------+
>> Lower memory address ----> Higher memory address
>>
>> The worst that can happen if a user overflows "buf"
>> is to over-write other local variables in the current
>> stack frame (not shown in the ASCII art), or write
>> to unused stack space.
>>
>> I do realize both the OS and all apps would need to be
>> re-compiled to run on the new system, but that sort of
>> flash-cutover happened before. (IIRC early SunOS was
>> little-endian in one version and big-endian in the next.
>> Or maybe it's the other way around.)
>>
>> But I've never seen this idea mentioned in ANY discussion
>> of buffer overflows. I can't be the first to think of
>> this simple idea, it seems obvious. So why isn't
>> this done? What am I (clearly a non-expert) missing?
>> Does anyone have any ideas?
>>
>> -Wayne
>
> Stack and Heap are orgnized in this ways cos we wanna save space for
> the process
>

Thanks for the reply. But I don't understand how the direction
of stack growth affects the amount of memory consumed by a
process (actually a thread). The stack is fixed in size
at process creation time, and unlike the heap, doesn't grow
over time. "Stack growth" is really just "stack use", right?
So how does the direction affect total memory usage?

-Wayne

Wayne wrote:


> Please, could you explain why reversing the stack growth
> direction would not solve this security problem? I grant
> such a drastic change to the memory system would cause
> other problems, but maybe those are not unsurmountable?
>
> I appreciate your patience with my ignorance, and your
> replies. Thanks!

Wouldn't you then have an "underflow" problem, allowing programs to
"underflow" into other regions of allocated memory? There's nothing
magic about it: if you have access to pointers, you can decrement them
as well as increment them. It might be easier to bounds-check them, I
admit.

Wayne wrote:
> xi4oyu wrote:
>
>>On 11 14 , 12 31 , Wayne <nos... DeleteThis @all4me.invalid> wrote:
>>
>>>I've often wondered why Linux (or any OS) puts up with
>>>stack buffer overflows. They only happen because
>>>the stack grows in one direction and buffers grow
>>>in the other:
>>>
>>> +----------------------------------------------------+
>>> | unused stack space | buf | ... | return_addr | ... |
>>> +----------------------------------------------------+
>>> Lower memory address ----> Higher memory address
>>>
>>>where buf is some local char array. A buffer
>>>overflow (in the case, there are heap attacks too)
>>>is only possible if a user over-writes the return
>>>address or some other part of the "lower" stack
>>>contents.
>>>
>>>So why doesn't any OS define the stack growth in the
>>>other direction:
>>>
>>> +----------------------------------------------------+
>>> | ... | return_addr | ... | buf | unused stack space |
>>> +----------------------------------------------------+
>>> Lower memory address ----> Higher memory address
>>>
>>>The worst that can happen if a user overflows "buf"
>>>is to over-write other local variables in the current
>>>stack frame (not shown in the ASCII art), or write
>>>to unused stack space.
>>>
>>>I do realize both the OS and all apps would need to be
>>>re-compiled to run on the new system, but that sort of
>>>flash-cutover happened before. (IIRC early SunOS was
>>>little-endian in one version and big-endian in the next.
>>>Or maybe it's the other way around.)
>>>
>>>But I've never seen this idea mentioned in ANY discussion
>>>of buffer overflows. I can't be the first to think of
>>>this simple idea, it seems obvious. So why isn't
>>>this done? What am I (clearly a non-expert) missing?
>>>Does anyone have any ideas?
>>>
>>>-Wayne
>>
>>Stack and Heap are orgnized in this ways cos we wanna save space for
>>the process
>>
>
>
> Thanks for the reply. But I don't understand how the direction
> of stack growth affects the amount of memory consumed by a
> process (actually a thread). The stack is fixed in size
> at process creation time, and unlike the heap, doesn't grow
> over time. "Stack growth" is really just "stack use", right?
> So how does the direction affect total memory usage?
>
> -Wayne


Please get a book on Linux memory management, and read it.

My suggestion is 'Understanding the Linux Kernel'. You can
Google for it.

The demand-paged virtual memory system of Linux will detect
an overflow of a memory section. It also uses only the active
pages of the memory sections in real memory.

Most of the overflow attacks are using buffers allocated
*in the stack*, so the memory management cannot detect an
overflow. This is simply sloppy programming.

--

Tauno Voipio
tauno voipio (at) iki fi

Tauno Voipio wrote:
> Wayne wrote:
>> xi4oyu wrote:
>>
>>> On 11 14 , 12 31 , Wayne <nos....TakeThisOut@all4me.invalid> wrote:
>>>
>>>> I've often wondered why Linux (or any OS) puts up with
>>>> stack buffer overflows. They only happen because
>>>> the stack grows in one direction and buffers grow
>>>> in the other:
>>>>
>>>> +----------------------------------------------------+
>>>> | unused stack space | buf | ... | return_addr | ... |
>>>> +----------------------------------------------------+
>>>> Lower memory address ----> Higher memory address
>>>>
>>>> where buf is some local char array. A buffer
>>>> overflow (in the case, there are heap attacks too)
>>>> is only possible if a user over-writes the return
>>>> address or some other part of the "lower" stack
>>>> contents.
>>>>
>>>> So why doesn't any OS define the stack growth in the
>>>> other direction:
>>>>
>>>> +----------------------------------------------------+
>>>> | ... | return_addr | ... | buf | unused stack space |
>>>> +----------------------------------------------------+
>>>> Lower memory address ----> Higher memory address
>>>>
>>>> The worst that can happen if a user overflows "buf"
>>>> is to over-write other local variables in the current
>>>> stack frame (not shown in the ASCII art), or write
>>>> to unused stack space.
>>>>
>>>> I do realize both the OS and all apps would need to be
>>>> re-compiled to run on the new system, but that sort of
>>>> flash-cutover happened before. (IIRC early SunOS was
>>>> little-endian in one version and big-endian in the next.
>>>> Or maybe it's the other way around.)
>>>>
>>>> But I've never seen this idea mentioned in ANY discussion
>>>> of buffer overflows. I can't be the first to think of
>>>> this simple idea, it seems obvious. So why isn't
>>>> this done? What am I (clearly a non-expert) missing?
>>>> Does anyone have any ideas?
>>>>
>>>> -Wayne
>>>
>>> Stack and Heap are orgnized in this ways cos we wanna save space for
>>> the process
>>>
>>
>>
>> Thanks for the reply. But I don't understand how the direction
>> of stack growth affects the amount of memory consumed by a
>> process (actually a thread). The stack is fixed in size
>> at process creation time, and unlike the heap, doesn't grow
>> over time. "Stack growth" is really just "stack use", right?
>> So how does the direction affect total memory usage?
>>
>> -Wayne
>
>
> Please get a book on Linux memory management, and read it.
>
> My suggestion is 'Understanding the Linux Kernel'. You can
> Google for it.
>
> The demand-paged virtual memory system of Linux will detect
> an overflow of a memory section. It also uses only the active
> pages of the memory sections in real memory.
>
> Most of the overflow attacks are using buffers allocated
> *in the stack*, so the memory management cannot detect an
> overflow. This is simply sloppy programming.
>

I will do that. But while I agree buffer overflows are
the result of sloppy programming, none the less, changing
the stack push/pop from --/++ to ++/-- prevents the problem
even if sloppy programing is used. This doesn't seem to
have anything to do with paging or overflow of a memory
section, just the direction of the stack growth,
whether the stack is one or more pages.

Please, could you explain why reversing the stack growth
direction would not solve this security problem? I grant
such a drastic change to the memory system would cause
other problems, but maybe those are not unsurmountable?

I appreciate your patience with my ignorance, and your
replies. Thanks!

-Wayne

Stack and heap grow in different directions, because you have two data
structures, which can be dynamically increased. What would happen,
heap and stack will grow in the same direction? Assume, the heap lies
above the stack in memory (it also works the other way). How far
should the start of stack be away from the start of the heap? In some
cases, you the distance will be too less, so you limit heap size or
the heap will overwrite parts of the stack. In the other case, the
distance will be too large, so the size of memory will limit your
stack size. As you can see, you will also have the problem of buffer
overflows. You could say "Why not moving stack / heap, so heap / stack
will get more space?", but this is very time expensive.

I hope, I could give you a short explanation, why linux (and other OS)
organize their memory in this way.

Greetings from Bavaria,

Markus

Nico wrote:
>
> Wayne wrote:
>
>
>> Please, could you explain why reversing the stack growth
>> direction would not solve this security problem? I grant
>> such a drastic change to the memory system would cause
>> other problems, but maybe those are not unsurmountable?
>>
>> I appreciate your patience with my ignorance, and your
>> replies. Thanks!
>
> Wouldn't you then have an "underflow" problem, allowing programs to
> "underflow" into other regions of allocated memory? There's nothing
> magic about it: if you have access to pointers, you can decrement them
> as well as increment them. It might be easier to bounds-check them, I
> admit.

Obviously in my ignorance I have not explained my idea well.
Sorry! How about this as an illustration:

crackme.c:

#include <string.h>
int main (int argc, char* argv[]) {
char buf[20];
strcpy( buf, argv[1]); // A bad idea!
return 0;
}

Now if crackme.c is compiled into crackme, and then run as:

crackme "A buffer overflow is an easy mistake to make but hard to find"

AFAIK, this causes a classic stack-based buffer overflow.
By crafting the string passed in you can over-write
the return address on the stack, causing a return into libc
and/or other nastiness.

Now, if the stack grew in the other direction, the over-flowing
text (" an easy mistake to make but hard to find\0") will
harmlessly over-write the unused stack space. An attacker armed
with "crackme" can't do anything about it. The programming error
is rendered harmless. (Well mostly harmless since the string may
over-write other local variables in that function.)

(And Nico, an attacker can't pass in a "negative length" string
to cause an "under-flow".

Hopefully my idea is clearer now, and some knowledgeable
security folks here will explain why this isn't a good idea.

(I don't think it is; someone would have been done it long
ago if it were a good idea. I just want to know why it's
a bad idea since I clearly don't "get it".
Then again, maybe I'm a security genius and just ahead
of my time with a brilliant idea?

-Wayne

cipher wrote:
> Stack and heap grow in different directions, because you have two data
> structures, which can be dynamically increased. What would happen,
> heap and stack will grow in the same direction? Assume, the heap lies
> above the stack in memory (it also works the other way). How far
> should the start of stack be away from the start of the heap? In some
> cases, you the distance will be too less, so you limit heap size or
> the heap will overwrite parts of the stack. In the other case, the
> distance will be too large, so the size of memory will limit your
> stack size. As you can see, you will also have the problem of buffer
> overflows. You could say "Why not moving stack / heap, so heap / stack
> will get more space?", but this is very time expensive.
>
> I hope, I could give you a short explanation, why linux (and other OS)
> organize their memory in this way.
>
> Greetings from Bavaria,
>
> Markus

I appreciate the response. I was unaware that on Linux the execution
stack was a dynamic structure now. (It didn't use to be, you
had to specify a desired stack size during the link-edit.)

But I finally found an explanation on Wikipedia, at
http://en.wikipedia.org/wiki/Stack_buffer_overflow#Stacks_that_grow_up:

<quote>
Within the topic of stack buffer overflows an often discussed but rarely
seen architecture is one in which the stack grows in the opposite
direction. This change in architecture is frequently suggested as a
solution to the stack buffer overflow problem because any overflow
of a stack buffer that occurs within the same stack frame can not
overwrite the return pointer. Further investigation of this
claimed protection finds it to be a naïve solution at best. Any
overflow that occurs in a buffer from a previous stack frame will
still overwrite a return pointer and allow for malicious
exploitation of the bug.[10] For instance, in the example above,
the return pointer for foo will not be overwritten because the
overflow actually occurs within the stack frame for strcpy.
However, because the buffer that overflows during the call to
strcpy resides in a previous stack frame, the return pointer
for strcpy will have a numerically higher memory address than
the buffer. This means that instead of the return pointer for
foo being overwritten, the return pointer for strcpy will be
overwritten. At most this means that growing the stack in the
opposite direction will change some details of how stack buffer
overflows are exploitable, but it will not reduce significantly
in the number of exploitable bugs.
</quote>

Now this makes sense to me.

Thanks again for all the replies.

-Wayne

Wayne wrote:
> Tauno Voipio wrote:
>
>>Wayne wrote:
>>
>>>xi4oyu wrote:
>>>
>>>
>>>>On 11 14 , 12 31 , Wayne <nos... DeleteThis @all4me.invalid> wrote:
>>>>
>>>>
>>>>>I've often wondered why Linux (or any OS) puts up with
>>>>>stack buffer overflows. They only happen because
>>>>>the stack grows in one direction and buffers grow
>>>>>in the other:
>>>>>
>>>>>+----------------------------------------------------+
>>>>>| unused stack space | buf | ... | return_addr | ... |
>>>>>+----------------------------------------------------+
>>>>>Lower memory address ----> Higher memory address
>>>>>
>>>>>where buf is some local char array. A buffer
>>>>>overflow (in the case, there are heap attacks too)
>>>>>is only possible if a user over-writes the return
>>>>>address or some other part of the "lower" stack
>>>>>contents.
>>>>>
>>>>>So why doesn't any OS define the stack growth in the
>>>>>other direction:
>>>>>
>>>>>+----------------------------------------------------+
>>>>>| ... | return_addr | ... | buf | unused stack space |
>>>>>+----------------------------------------------------+
>>>>>Lower memory address ----> Higher memory address
>>>>>
>>>>>The worst that can happen if a user overflows "buf"
>>>>>is to over-write other local variables in the current
>>>>>stack frame (not shown in the ASCII art), or write
>>>>>to unused stack space.
>>>>>
>>>>>I do realize both the OS and all apps would need to be
>>>>>re-compiled to run on the new system, but that sort of
>>>>>flash-cutover happened before. (IIRC early SunOS was
>>>>>little-endian in one version and big-endian in the next.
>>>>>Or maybe it's the other way around.)
>>>>>
>>>>>But I've never seen this idea mentioned in ANY discussion
>>>>>of buffer overflows. I can't be the first to think of
>>>>>this simple idea, it seems obvious. So why isn't
>>>>>this done? What am I (clearly a non-expert) missing?
>>>>>Does anyone have any ideas?
>>>>>
>>>>>-Wayne
>>>>
>>>>Stack and Heap are orgnized in this ways cos we wanna save space for
>>>>the process
>>>>
>>>
>>>
>>>Thanks for the reply. But I don't understand how the direction
>>>of stack growth affects the amount of memory consumed by a
>>>process (actually a thread). The stack is fixed in size
>>>at process creation time, and unlike the heap, doesn't grow
>>>over time. "Stack growth" is really just "stack use", right?
>>>So how does the direction affect total memory usage?
>>>
>>>-Wayne
>>
>>
>>Please get a book on Linux memory management, and read it.
>>
>>My suggestion is 'Understanding the Linux Kernel'. You can
>>Google for it.
>>
>>The demand-paged virtual memory system of Linux will detect
>>an overflow of a memory section. It also uses only the active
>>pages of the memory sections in real memory.
>>
>>Most of the overflow attacks are using buffers allocated
>>*in the stack*, so the memory management cannot detect an
>>overflow. This is simply sloppy programming.
>>
>
>
> I will do that. But while I agree buffer overflows are
> the result of sloppy programming, none the less, changing
> the stack push/pop from --/++ to ++/-- prevents the problem
> even if sloppy programing is used. This doesn't seem to
> have anything to do with paging or overflow of a memory
> section, just the direction of the stack growth,
> whether the stack is one or more pages.
>
> Please, could you explain why reversing the stack growth
> direction would not solve this security problem? I grant
> such a drastic change to the memory system would cause
> other problems, but maybe those are not unsurmountable?
>
> I appreciate your patience with my ignorance, and your
> replies. Thanks!
>
> -Wayne


Stack and heap are in different sections, and
there is plenty of unallocated address space
in between for the memory management hardware
to catch.

For a variable allocated in stack, the buffer
overflow can always clobber unintended data:
the allocated buffer is not always allocated
last in the stack frame.

--

Tauno Voipio
tauno voipio (at) iki fi

On 2007-11-14, Wayne <nospam DeleteThis @all4me.invalid> wrote:
> I've often wondered why Linux (or any OS) puts up with
> stack buffer overflows.

Isn't this the kind of thing "libsafe" is supposed to deal with?

http://directory.fsf.org/project/libsafe/


--

John (john@os2.dhs.org)

I forgot something:

A "buffer overflow" does not necessarily mean, that the stack will be
corrupted. Buffer overflow means, that a piece of code writes to a
region in memory, where it shouldn't, when everything would be o. k.
(command line parameters, data from file / database / network
packets, ...). In those cases the program overwrites some other
variables / buffers in memory, so the behaviour of your program (or
some other program) changes.

In my eyes, the only way to avoid buffer overflows is in using a
programming language, that provides built-in techniques that will
check things like array indices, like Java. Java reports an so called
ArrayIndexOutOfBoundsException exception if your array index leaves
the valid range. Some older languages like Pascal or Modula-2 also
checks these ranges by default. In C, this will be rather difficult.

Greetings from Bavaria,

Markus

On Nov 14, 4:31 am, Wayne <nos... RemoveThis @all4me.invalid> wrote:
> I've often wondered why Linux (or any OS) puts up with
> stack buffer overflows. They only happen because
> the stack grows in one direction and buffers grow
> in the other:
>
> +----------------------------------------------------+
> | unused stack space | buf | ... | return_addr | ... |
> +----------------------------------------------------+
> Lower memory address ----> Higher memory address
>
> where buf is some local char array. A buffer
> overflow (in the case, there are heap attacks too)
> is only possible if a user over-writes the return
> address or some other part of the "lower" stack
> contents.
>
> So why doesn't any OS define the stack growth in the
> other direction:
>
> +----------------------------------------------------+
> | ... | return_addr | ... | buf | unused stack space |
> +----------------------------------------------------+
> Lower memory address ----> Higher memory address
>

> -Wayne

Surely this is a function of the x86 architecture? PUSH is defined to
write the PUSHed register to the address pointed to by the stack
pointer, and then to *decrement* the stack pointer. POP reads from the
pointed-to address, and *increments* the stack pointer.
I don't see how any OS could realistically do it any differently on
that architecture - but perhaps I am missing something?

MT

On Fri, 16 Nov 2007 04:12:53 -0800, Abut wrote:

> On Nov 14, 4:31 am, Wayne <nos... RemoveThis @all4me.invalid> wrote:
>> I've often wondered why Linux (or any OS) puts up with
>> stack buffer overflows. They only happen because
>> the stack grows in one direction and buffers grow
>> in the other:
>>
>> +----------------------------------------------------+
>> | unused stack space | buf | ... | return_addr | ... |
>> +----------------------------------------------------+
>> Lower memory address ----> Higher memory address
>>
>> where buf is some local char array. A buffer
>> overflow (in the case, there are heap attacks too)
>> is only possible if a user over-writes the return
>> address or some other part of the "lower" stack
>> contents.
>>
>> So why doesn't any OS define the stack growth in the
>> other direction:
>>
>> +----------------------------------------------------+
>> | ... | return_addr | ... | buf | unused stack space |
>> +----------------------------------------------------+
>> Lower memory address ----> Higher memory address
>>
>
>> -Wayne
>
> Surely this is a function of the x86 architecture? PUSH is defined to
> write the PUSHed register to the address pointed to by the stack
> pointer, and then to *decrement* the stack pointer. POP reads from the
> pointed-to address, and *increments* the stack pointer.
> I don't see how any OS could realistically do it any differently on
> that architecture - but perhaps I am missing something?
>
You're not missing something -- you're right. The entity that defines the
instruction set architecture specifies the calling conventions for
subroutines, including use of the stack for local variables, parameter
passing and return address. The compiler developer must follow the
specification (if not, different compilers won't interoperate). The OS
comes along well after (esp. Linux) and has no say. (In the distant past,
compiler and OS and ISA were co-developed by the same entity, as in the
case of the DEC VAX. I don't know of a recent example. Actually, there
haven't been too many new ISA's coming along lately.)