Is this the ultimate stack-smash fix?

Is this the ultimate stack-smash fix?

[Jeremy Jackson]

Greetings.  This is my first post on linux-kernel, I hope this is
appropriate.

The recent CERT IN-2001-01 's massive repercussions and CA-2001-02's
re-releasing
old material in an attempt to coerce admins to update their OS, has led
me to think about
buffer overrun exploits.   I have gained a new appreciation after being
rooted twice this month.

I believe there is a solution that can be implemented in the kernel
(Linux and probably most Unix)
that can prevent this type of exploit, has no effect on userspace code,
and is minimally obtrusive
for the kernel.

Making a few assumptions here - I'm writing to confirm or deny this
idea.

Background:

The virtual address space of a Linux process starts at a low address
(0?) with a block
containing

-the executable's code & constant data mmaped read-only from the
executable.
-the executable's static initialized data mmapped copy-on-write from
same file.
-more of each of the above, but for shared libraries.

each continuous address range from the above is described in a kernel
vm_area_struct,
and is mapped on demand and placed into hardware page-protection perms
(rwx) by the CPU's
PMMU hardware and the kernel's fault-handler's.

Next, there is a variable ammount of un mapped memory, Followed by the
Stack.

The stack's vm_area grows downward, unlike the others ( brk() call) and
begins at the high
address at the top of user space, which varies but is 3GB for a 1GB max
mem kernel.

beyond this there is no vm_area's, and the page tables contain mappings
which are marked
supervisor-only (is this right?), and definitely don't contain user
code.


Next, gcc doesn't generate any code which would be placed in the stack,
nor does it
generate any calls/jumps to the stack area.

Next, buffer overruns are the only source of code whch would execute
from the stack, and
from what I understand, remote (if not all)  buffer overruns depend on
this to "work".

Solution: if the kernel sets up the CPU's memory management unit (PMMU)
so that it won't
execute code in the stack address space, the exploits are foiled.

Problem: on intel, the page tables page permissions are not flexible
enough, so when a page
is marked (for userspace) read-write permissions, execute permission is
implied.

But, intel also has segment descriptors held in the GDT/LDTs, which
configure a base address
and range, and a different one can be selected for each segment register
of a process.   Under the current
Linux the code segment (CS) has a descriptor from the GDT which allows
code to be executed read-only from
base address 0 with a range of 4G (i.e. the entire linear address
space), and the data segment
allows read-write but not execute (can't be loaded into CS register).

SO, if the CS descriptor were changed by the kernel to track the bottom
of the stack (lower in memory),
then any attempt to execute code on the stack would segfault (or another
signal to help track exploit
attempts)  It could get the bottom page address from the vm_area_struct
for the stack (are there more than one GROWS_DOWN
vm areas in a process?)

Currently the CS for all linux programs gets it's descriptor from GDT,
so it would have to be manually
changed at each task-swap, and perhaps there are segment descriptor and
other cache flushing issues,
(maybe just store CS limit in the per-task data structure, and update
GDT then reload CS at each
context change)

I realize that the GDT/LDT must be accessible, and that they are in
kernel space (above 3GB), but I don't
think these go through CS register access controls.  The DS segment can
be left alone.

For other arch's, maybe they have separate read/write/execute perms per
page, or something similar
to segment descriptors.

I would appreciate thoughful comments; anybody who knows why it won't
work, tell me,
I haven't got my hopes up for the Nobel prize yet :)

Cheers,

Jeremy

Re: Is this the ultimate stack-smash fix?

[Alan Cox]

> which are marked
> supervisor-only (is this right?), and definitely don't contain user
> code.

x86 its a fair description. However someone has taken the same theory, 
including handling the exceptions and the x86 segment tricks needed to make
it kind of fly. Its not a perfect cure but it works. Search for Solar Designer
and non executable stack.

Re: Is this the ultimate stack-smash fix?

[James Sutherland]

On Tue, 13 Feb 2001, Jeremy Jackson wrote:

(Long description of how to create a non-executable stack on x86)

I'm afraid you just reinvented the wheel. The idea has been around for a
long time, and it was OK as a quick hack to stop existing exploits
working, but it's possible to modify a buffer overflow exploit to work
around this.

It does sound look like a good idea, but it doesn't really gain you
anything in the long run: the exploits just change a bit.

ISTR there is a patch which does this for Linux, though??


James.

Re: Is this the ultimate stack-smash fix?

[Bruce Harada]

On Tue, 13 Feb 2001 21:22:26 +0000 (GMT)
James Sutherland <jas88@cam.ac.uk> wrote:

> On Tue, 13 Feb 2001, Jeremy Jackson wrote:
> 
> (Long description of how to create a non-executable stack on x86)
>
> ISTR there is a patch which does this for Linux, though??

See:

 http://www.openwall.com/linux/

for Solar Designer's patch, and:

 http://www.insecure.org/sploits/non-executable.stack.problems.html

for the exploit. It was done to death on the linux-security ML a while
ago, so you could search the archives if you want to know more.

--
Bruce Harada
bruce@ask.ne.jp

Re: Is this the ultimate stack-smash fix?

[William T Wilson]

On Tue, 13 Feb 2001, Jeremy Jackson wrote:

> Next, gcc doesn't generate any code which would be placed in the
> stack, nor does it generate any calls/jumps to the stack area.

Unfortunately, you can't count on this.  Objective C, for one, requires an
executable stack.

While there have been "unofficial" patches (Solar Designer) to lock out
executing the stack for a long time, and it does work in most cases, this
isn't really doable as a general solution.

Re: Is this the ultimate stack-smash fix?

[Eric W. Biederman]

Jeremy Jackson <jeremy.jackson@sympatico.ca> writes:

> Greetings.  This is my first post on linux-kernel, I hope this is
> appropriate.
> 
> The recent CERT IN-2001-01 's massive repercussions and CA-2001-02's
> re-releasing
> old material in an attempt to coerce admins to update their OS, has led
> me to think about
> buffer overrun exploits.   I have gained a new appreciation after being
> rooted twice this month.
> 
> I believe there is a solution that can be implemented in the kernel
> (Linux and probably most Unix)
> that can prevent this type of exploit, has no effect on userspace code,
> and is minimally obtrusive
> for the kernel.

There is another much more effective solution in the works.  The C
standard allows bounds checking of arrays.  So it is quite possible
for the compiler itself to check this in a combination of run-time and
compile-time checks.   I haven't followed up but not too long ago
there was an effort to add this as an option to gcc.  If you really
want this fixed that is the direction to go.  Then buffer overflow
exploits become virtually impossible.

Eric

Re: Is this the ultimate stack-smash fix?

[Jeremy Jackson]

"Eric W. Biederman" wrote:

> Jeremy Jackson <jeremy.jackson@sympatico.ca> writes:
> (about non-executable stack)
>
> There is another much more effective solution in the works.  The C
> standard allows bounds checking of arrays.  So it is quite possible
> for the compiler itself to check this in a combination of run-time and
> compile-time checks.   I haven't followed up but not too long ago
> there was an effort to add this as an option to gcc.  If you really
> want this fixed that is the direction to go.  Then buffer overflow
> exploits become virtually impossible.
>

I've thought some more, and yes someone else has already done this.  Problems
are with compilers that
put code on stack (g++ trampolines for local functions i think).  There is
the gcc-mod (Stack-guard?) that checks for
corrupt stack frame using magic number containing zeros before returning...
this will take away some
performance though...

I wonder if the root of the issue is the underlying security architechure ...
anything that needs ANY privilege
gets ALL privileges (ie root).  chown named and such fixes this, but can't
rebind to privileged port, must be restarted
by root to do so.  VMS / NT have more fine grained privileges.

Is there any documentation of the kernel's 'capabilities' functions?  It
would be exceedingly cool if services (named, nfs, etc)
could be updated to use this;  I think crackers would loose some motivation
if instead of "hey I can totally rule this box!"
they have to settle for "hey I can make the ident service report user 'CrAp'
for every port!".

Re: Is this the ultimate stack-smash fix?

[Gerhard Mack]

> Is there any documentation of the kernel's 'capabilities' functions?  It
> would be exceedingly cool if services (named, nfs, etc)
> could be updated to use this;  I think crackers would loose some motivation
> if instead of "hey I can totally rule this box!"
> they have to settle for "hey I can make the ident service report user 'CrAp'
> for every port!".

Named and proftpd are already updated to use this.. check the source
for the best documentation ...

	Gerhard




--
Gerhard Mack

gmack@innerfire.net

<>< As a computer I find your faith in technology amusing.

Re: Is this the ultimate stack-smash fix?

[Eric W. Biederman]

Jeremy Jackson <jeremy.jackson@sympatico.ca> writes:

> "Eric W. Biederman" wrote:
> 
> > Jeremy Jackson <jeremy.jackson@sympatico.ca> writes:
> > (about non-executable stack)
> >
> > There is another much more effective solution in the works.  The C
> > standard allows bounds checking of arrays.  So it is quite possible
> > for the compiler itself to check this in a combination of run-time and
> > compile-time checks.   I haven't followed up but not too long ago
> > there was an effort to add this as an option to gcc.  If you really
> > want this fixed that is the direction to go.  Then buffer overflow
> > exploits become virtually impossible.
> >
> 
> I've thought some more, and yes someone else has already done this.  Problems
> are with compilers that
> put code on stack (g++ trampolines for local functions i think).  There is
> the gcc-mod (Stack-guard?) that checks for
> corrupt stack frame using magic number containing zeros before returning...
> this will take away some
> performance though...

No.  I'm not talking about stack-guard patches.  I'm talking about bounds checking.
The difference here is that if correct code is generated you won't
overflow any buffer at all period.  The compiler will either prove at
compile time that it can't happen (The efficient case).  Or it will
generate pointers as <start,length,offset> tuples into chunks of
memory.  And it will do runtime checks that will that will kill your
program if it overflows the stack.  I think the gcc options is -fcheck
or something like that.  I haven't had a chance to follow up, since I
saw that someone was actually working on it.

Since compilers bugs happen buffer overflow exploits are still
possible but it means two separate programmers must mess up in
complimentary ways.

As for fine grain privileges they can help, but the real fix is to
keep the programs that need raised privileges down to one function.
Letting you look at the program and see if it is obviously correct
with no security bugs. 

But the gcc bounds checking work is the ultimate buffer overflow fix.
You can recompile all of your trusted applications, and libraries with
it and be safe from one source of bugs.

Eric

Re: Is this the ultimate stack-smash fix?

[Manfred Spraul]

"Eric W. Biederman" wrote:
> 
> But the gcc bounds checking work is the ultimate buffer overflow fix.
> You can recompile all of your trusted applications, and libraries with
> it and be safe from one source of bugs.
>

void main(int argc, char **argv[])
{
	char local[128];
	if(argc > 2)
		strcpy(local,argv[1]);
}

Unless you modify the ABI and pass the array bounds around you won't
catch such problems, and I won't even mention unions and

struct dyn_data {
	int len;
	char data[];
}

--
	Manfred

Re: Is this the ultimate stack-smash fix?

[Eric W. Biederman]

Manfred Spraul <manfred@colorfullife.com> writes:

> "Eric W. Biederman" wrote:
> > 
> > But the gcc bounds checking work is the ultimate buffer overflow fix.
> > You can recompile all of your trusted applications, and libraries with
> > it and be safe from one source of bugs.
> >
> 
> void main(int argc, char **argv[])
> {
> 	char local[128];
> 	if(argc > 2)
> 		strcpy(local,argv[1]);
> }
> 
> Unless you modify the ABI and pass the array bounds around you won't
> catch such problems, 

Of course.  But this is linux and you have the source.  And I did mention
you needed to recompile the libraries your trusted applications depended on.


> and I won't even mention unions and
> 
> struct dyn_data {
> 	int len;
> 	char data[];
> }

Yep bounds checking is not an easy fix.  But it is a good fix.

Eric

Re: Is this the ultimate stack-smash fix?

[Peter Samuelson]

  [Manfred Spraul]
> > Unless you modify the ABI and pass the array bounds around you won't
> > catch such problems, 

[Eric W. Biederman]
> Of course.  But this is linux and you have the source.  And I did
> mention you needed to recompile the libraries your trusted
> applications depended on.

So by what ABI do you propose to pass array bounds to a called
function?  It sounds pretty ugly.  It also sounds like you will be
breaking the extremely useful C postulate that, at the ABI level at
least, arrays and pointers are equivalent.  I can't see *how* you plan
to work around that one.

> Yep bounds checking is not an easy fix.

Understatement of the year, if you really want to catch all cases.

Peter

Re: Is this the ultimate stack-smash fix?

[Eric W. Biederman]

Peter Samuelson <peter@cadcamlab.org> writes:

>   [Manfred Spraul]
> > > Unless you modify the ABI and pass the array bounds around you won't
> > > catch such problems, 
> 
> [Eric W. Biederman]
> > Of course.  But this is linux and you have the source.  And I did
> > mention you needed to recompile the libraries your trusted
> > applications depended on.
> 
> So by what ABI do you propose to pass array bounds to a called
> function?  It sounds pretty ugly.  

Not especially.  In cases you can't optimize pointers become tuples
of <pointer to the array, pointer one past the end of the array, real pointer>.

> It also sounds like you will be
> breaking the extremely useful C postulate that, at the ABI level at
> least, arrays and pointers are equivalent.  I can't see *how* you plan
> to work around that one.

Huh?  Pointers and arrays are clearly different at the ABI level.

A pointer is a word that contains an address of something.
An array is an array.

There is an implicit promotion from one to the other at the source level,
but that has little to do with the application binary interface.

> > Yep bounds checking is not an easy fix.
> 
> Understatement of the year, if you really want to catch all cases.

No, it's more of a large mechanical job than truly hard problem.
The real challenge lies in optimizing out the checks so you don't penalize
the inner loops of code.

Eric

Re: Is this the ultimate stack-smash fix?

[Andreas Bombe]

On Sat, Feb 17, 2001 at 09:53:48PM -0700, Eric W. Biederman wrote:
> Peter Samuelson <peter@cadcamlab.org> writes:
> > It also sounds like you will be
> > breaking the extremely useful C postulate that, at the ABI level at
> > least, arrays and pointers are equivalent.  I can't see *how* you plan
> > to work around that one.
> 
> Huh?  Pointers and arrays are clearly different at the ABI level.
> 
> A pointer is a word that contains an address of something.
> An array is an array.

An array is a word that contains the address of the first element.

Exercise 1:  What is the difference between the following two
declarations at the source level and at the ABI level?

a) int main(int argc, char *argv[])
b) int main(int argc, char **argv)


Exercise 2:  What would the following in hypothetical C startup code do?

	char *args[10];
	int count = 10;

	...

	exit(main(count - 1, args + 1));

-- 
 Andreas E. Bombe <andreas.bombe@munich.netsurf.de>    DSA key 0x04880A44
http://home.pages.de/~andreas.bombe/    http://linux1394.sourceforge.net/

Re: Is this the ultimate stack-smash fix?

[Xavier Bestel]

Le 20 Feb 2001 02:10:12 +0100, Andreas Bombe a écrit :
> On Sat, Feb 17, 2001 at 09:53:48PM -0700, Eric W. Biederman wrote:
> > Peter Samuelson <peter@cadcamlab.org> writes:
> > > It also sounds like you will be
> > > breaking the extremely useful C postulate that, at the ABI level at
> > > least, arrays and pointers are equivalent.  I can't see *how* you plan
> > > to work around that one.
> > 
> > Huh?  Pointers and arrays are clearly different at the ABI level.
> > 
> > A pointer is a word that contains an address of something.
> > An array is an array.
> 
> An array is a word that contains the address of the first element.


No. Exercise 3: compile and run this:
file a.c:
char array[] = "I'm really an array";

file b.c:
extern char* array;
main() { printf("array = %s\n", array); }

... and watch it biting the dust !
in short: an array is NOT a pointer.


    Xav

Re: Is this the ultimate stack-smash fix?

[Jeremy Jackson]

Xavier Bestel wrote:

> Le 20 Feb 2001 02:10:12 +0100, Andreas Bombe a écrit :
> >
> > An array is a word that contains the address of the first element.
>
> No. Exercise 3: compile and run this:
> file a.c:
> char array[] = "I'm really an array";
>
> file b.c:
> extern char* array;
> main() { printf("array = %s\n", array); }
>

try file b.c
extern char array;
main() { printf("array= %s\n", &array); }

?

>
> ... and watch it biting the dust !
> in short: an array is NOT a pointer.

Re: Is this the ultimate stack-smash fix?

[Xavier Bestel]

Le 20 Feb 2001 11:40:18 -0500, Jeremy Jackson a écrit :
> Xavier Bestel wrote:
> 
> > Le 20 Feb 2001 02:10:12 +0100, Andreas Bombe a écrit :
> > >
> > > An array is a word that contains the address of the first element.
> >
> > No. Exercise 3: compile and run this:
> > file a.c:
> > char array[] = "I'm really an array";
> >
> > file b.c:
> > extern char* array;
> > main() { printf("array = %s\n", array); }
> >
> 
> try file b.c
> extern char array;
> main() { printf("array= %s\n", &array); }

So ?

Re: Is this the ultimate stack-smash fix?

[Andreas Bombe]

On Tue, Feb 20, 2001 at 10:09:55AM +0100, Xavier Bestel wrote:
> Le 20 Feb 2001 02:10:12 +0100, Andreas Bombe a écrit :
> > On Sat, Feb 17, 2001 at 09:53:48PM -0700, Eric W. Biederman wrote:
> > > Peter Samuelson <peter@cadcamlab.org> writes:
> > > > It also sounds like you will be
> > > > breaking the extremely useful C postulate that, at the ABI level at
> > > > least, arrays and pointers are equivalent.  I can't see *how* you plan
> > > > to work around that one.
> > > 
> > > Huh?  Pointers and arrays are clearly different at the ABI level.
> > > 
> > > A pointer is a word that contains an address of something.
> > > An array is an array.
> > 
> > An array is a word that contains the address of the first element.
> 
> 
> No. Exercise 3: compile and run this:
> file a.c:
> char array[] = "I'm really an array";
> 
> file b.c:
> extern char* array;
>
> main() { printf("array = %s\n", array); }
> 
> ... and watch it biting the dust !

Deliberately linking to the wrong symbol is not a point.  Might as well
replace file a.c with "int array = 0;".  That'll also bite the dust.  So?

> in short: an array is NOT a pointer.

In this context we were talking *function calls*, not confusing the
linker.  And whether you say "char array[];" or "char *const array;",
array is a pointer.  Even more so at the ABI = function call interface.

Another try:  Assume that
	#include "secret.h"
	int main() { printf("array = %s\n", array); return 0; }
is correct code.

Is the variable array a pointer to a char or an array of chars?

Oh well, who cares.

-- 
 Andreas E. Bombe <andreas.bombe@munich.netsurf.de>    DSA key 0x04880A44
http://home.pages.de/~andreas.bombe/    http://linux1394.sourceforge.net/

Re: Is this the ultimate stack-smash fix?

[Xavier Bestel]

Le 21 Feb 2001 01:13:03 +0100, Andreas Bombe a écrit :
> On Tue, Feb 20, 2001 at 10:09:55AM +0100, Xavier Bestel wrote:
> > Le 20 Feb 2001 02:10:12 +0100, Andreas Bombe a écrit :
> > > On Sat, Feb 17, 2001 at 09:53:48PM -0700, Eric W. Biederman wrote:
> > > > Peter Samuelson <peter@cadcamlab.org> writes:
> > > > > It also sounds like you will be
> > > > > breaking the extremely useful C postulate that, at the ABI level at
> > > > > least, arrays and pointers are equivalent.  I can't see *how* you plan
> > > > > to work around that one.
> > > > 
> > > > Huh?  Pointers and arrays are clearly different at the ABI level.
> > > > 
> > > > A pointer is a word that contains an address of something.
> > > > An array is an array.
> > > 
> > > An array is a word that contains the address of the first element.
> > 
> > 
> > No. Exercise 3: compile and run this:
> > file a.c:
> > char array[] = "I'm really an array";
> > 
> > file b.c:
> > extern char* array;
> >
> > main() { printf("array = %s\n", array); }
> > 
> > ... and watch it biting the dust !
> 
> Deliberately linking to the wrong symbol is not a point.  Might as well
> replace file a.c with "int array = 0;".  That'll also bite the dust.  So?
> 
> > in short: an array is NOT a pointer.
> 
> In this context we were talking *function calls*, not confusing the
> linker.  And whether you say "char array[];" or "char *const array;",
> array is a pointer.  Even more so at the ABI = function call interface.

OK, I missed this. There are no arrays in the function call interface,
they are promoted to pointers.

Xav

Re: Is this the ultimate stack-smash fix?

[Jeremy Jackson]

"Eric W. Biederman" wrote:

> Jeremy Jackson <jeremy.jackson@sympatico.ca> writes:
>
> > "Eric W. Biederman" wrote

> No.  I'm not talking about stack-guard patches.  I'm talking about bounds checking.

Sorry, I was quite incoherent.  Many others have pointed out that there exist
patches for non-executatble stack, and the problems with it. That's what I meant to
comment on.  But I'm glad to find out about bounds checking as an option.

> But the gcc bounds checking work is the ultimate buffer overflow fix.
> You can recompile all of your trusted applications, and libraries with
> it and be safe from one source of bugs.

That's why I was wondering of limiting privileged addresses security at a more
fundamental level... as you say above,
this fixes *ONE* source of bugs(security threats)... but itn't it inevitable that
there will be others?  But if services are each put
in a separate box, that doesn't have a door leading to the inner sanctum, things would
be more secure in spite of "bugs".

Well I thank everyone for their responses in this thread, I think It's been beaten
into the ground (my original idea),
and I'm left with some food for thought.

Re: Is this the ultimate stack-smash fix?

[Florian Weimer]

ebiederm@xmission.com (Eric W. Biederman) writes:

> There is another much more effective solution in the works.  The C
> standard allows bounds checking of arrays.

The C standard does not allow reliable bounds checking on {signed,
unsigned, vanilla} char arrays, because the corresponding pointers can
address the individual bytes in each object, even the object which
follows the array.  To implement things in an efficient manner, you
need fat pointers, which would make sizeof (long) /= sizeof (void *),
which would break quite some software, I think.

IMHO, C is a hopeless case in this area.  Fortunately, there is a
number of other programming languages out there which do permit proper
bounds checking on arrays (and have strong, static typing and other
gizmos which make shooting yourself into the foot unintentionally a
bit more difficult).

-- 
Florian Weimer 	                  Florian.Weimer@RUS.Uni-Stuttgart.DE
University of Stuttgart           http://cert.uni-stuttgart.de/
RUS-CERT                          +49-711-685-5973/fax +49-711-685-5898

Re: Is this the ultimate stack-smash fix?

[Alan Cox]

> need fat pointers, which would make sizeof (long) /= sizeof (void *),
> which would break quite some software, I think.

There are plenty of architectures where sizeof long != sizeof (void *). If your
code makes bad assumptions and a bounds checking cc breaks it then its progress.