Buffer Overflow Attacks

Buffer Overflow Attacks

[Frank Pilhofer]

   Hi,

 beware, the following text contains an idea on a topic that I am not
an expert on and which I have not extensively researched, so it's one
of the usual cases where someone comes along with dangerous half know-
ledge. So ignore me if the following does not make any sense at all.

 A few days ago, I have once again read an article about attacking
systems on the Internet using various kinds of exploits. Seems to me
that apart from braindead administrators, the usual entry into a sys-
tem is by exploiting a buffer overflow error.

 Despite extensive peer review and linkers that warn us about gets(),
new buffer overflow errors in popular software are discovered again
and again.

 If my limited comprehension of this topic is correct, buffer over-
flow exploits are based on the fact that you can overwrite vital parts
like processor registers and a function's return address, which are
stored on the stack just as local variables are.

 So I had the idea whether it would be possible to avoid buffer over-
flow vulnerabilities by using two separate stacks, one for data and
the other for registers and addresses. This is work that could be done
with the compiler and the linker.

 This idea would not work if it is not possible to have two stack seg-
ments. You could place the two parts into different address ranges of
the stack segment, though. If the registers/addresses parts is on a
smaller virtual address, your program would likely run out of real
memory whilst the attacker sends data before the wrap-around occurs
(or fail upon hitting a read-only address).

 Another alternative would be to introduce some randomness in the
usage of stack data. Exploits only work well because we have large
OS distributions that put the same executable onto hundreds of
thousands of machines. But even compiling the same program with
different compiler options makes a difference, e.g. compiling with
or without debugging, invalidating the exploit, doesn't it?

 Some ideas that come to my mind for this topic are e.g. random
padding on the stack (e.g. upon a function call, you add a couple
of bytes more or less), or maybe xor'ing the register values on
the stack with a per-process random number.

 So basically, I am wondering if the compiler could do something to
blunt buffer overflow attacks. I know, that is not the prime purpose
of the compiler but rather the responsibility of the programmer, but
still I find it an attractive idea as a one-step fix for all such
exploits.

 Okay, that's enough for now. If you've read so far, it's either because
there is some sense in my ideas, or because you were getting a good laugh
out of it.

 Any comments?

	Frank



-- 
Frank Pilhofer  ...........................................  fp@fpx.de
A family vacation is when you go away with people you need to get
away from. - Alfred E. Neuman

Re: Buffer Overflow Attacks

[Carlo Wood]

On Sun, Oct 14, 2001 at 02:09:20PM +0200, Frank Pilhofer wrote:
>  So basically, I am wondering if the compiler could do something to
> blunt buffer overflow attacks. I know, that is not the prime purpose
> of the compiler but rather the responsibility of the programmer, but
> still I find it an attractive idea as a one-step fix for all such
> exploits.

Because of this, complete new languages have been designed (Java and C#),
which - as a result of that - are considerably slower.  I don't think that
a C/C++ compiler should sacrifice memory and/or cpu time to this.  And as
you said yourself, it wouldn't make much sense unless the large
distributions make use of it; so a compile option is not an option - we're
talking about a change to the default here.

-- 
Carlo Wood <carlo@alinoe.com>

Re: Buffer Overflow Attacks

[Florian Weimer]

520065607613-0001@t-online.de (Frank Pilhofer) writes:

>  If my limited comprehension of this topic is correct, buffer over-
> flow exploits are based on the fact that you can overwrite vital parts
> like processor registers and a function's return address, which are
> stored on the stack just as local variables are.

Nowadays, Buffer overflow exploits sometimes involve overwriting
function pointers on the heap.  Since buffers and function pointers
are sometimes part of the same data structure, it is difficult to
separate them in the address space.

Sometimes, buffer overflow bugs are not just related to buffer
overflows, but they give you complete control what you can write
*anywhere* (one of the recent fetchmail problems was of this type).

> This idea would not work if it is not possible to have two stack seg-
> ments. You could place the two parts into different address ranges of
> the stack segment, though. If the registers/addresses parts is on a
> smaller virtual address, your program would likely run out of real
> memory whilst the attacker sends data before the wrap-around occurs
> (or fail upon hitting a read-only address).

You could unmap a page between these to memory areas.

> So basically, I am wondering if the compiler could do something to
> blunt buffer overflow attacks. I know, that is not the prime purpose
> of the compiler but rather the responsibility of the programmer, but
> still I find it an attractive idea as a one-step fix for all such
> exploits.

There isn't one.  Suppose you have an object of this type
("func_ptr_t" is some function pointer):

        struct s {
          char buffer[32];
          func_ptr_t ptr;
        };

Then a statement like

        s.buffer[32] = 1;

is completely legal.  It is equivalent to:

        *((s.buffer) + 32) = 1;

"(s.buffer) + 32" is a valid pointer to a character because every
object can be read and written as sequence of characters.  From the
point of view of the C language, no buffer overflow occurs, but this
clearly unsatisfactory from a safety point of view because quite a few
buffer overflow bugs are of this type.

Re: Buffer Overflow Attacks

[dewar]

<<Because of this, complete new languages have been designed (Java and C#),
which - as a result of that - are considerably slower.  I don't think that
>>

This is misleading, Ada has shown for a long time that bounds checking need
not be that expensive. The performance of Java is not substantially due to
this feature at all. The obvious approach in a compiler to prevent this
kind of error is to generate appropriate runtime checks, and it is by
no means impossible to do this kind of code generation for C (indeed
it can be done already by some C translators). Yes there is overhead, but
probably not significantly more than would occur for the schemes discussed
here (e.g. separated data and control stacks).

Re: Buffer Overflow Attacks

[Florian Weimer]

dewar@gnat.com writes:

> and it is by no means impossible to do this kind of code generation
> for C

According to the language standard, buffer overflow detection for
character pointer types is possible only for buffers which are not
nested in other objects (in struct or union objects).  Overflowing
character buffers has a well-defined effect if the buffer is contained
in an object (and other objects follow the buffer inside this object),
so a C implementation is not free to detect such errors (which is only
possible if the buffer overflow triggers undefined behavior). ;-)

Re: Buffer Overflow Attacks

[Joseph S. Myers]

On Sun, 14 Oct 2001, Florian Weimer wrote:

> According to the language standard, buffer overflow detection for
> character pointer types is possible only for buffers which are not
> nested in other objects (in struct or union objects).  Overflowing
> character buffers has a well-defined effect if the buffer is contained
> in an object (and other objects follow the buffer inside this object),
> so a C implementation is not free to detect such errors (which is only
> possible if the buffer overflow triggers undefined behavior). ;-)

This is a gross over-simplification of the problem of exactly when an
object can be accessed through a given pointer.  For details see Nick
Maclaren's "What is an object when it is at home?" paper, except that I
don't think he's published it beyond the UK and WG14 reflectors.  For
examples where the committee has ruled that bounds of sub-objects can't be
exceeded, see DR#017 question 16, and DRs #051 and #178 relating to the
"struct hack".

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: Buffer Overflow Attacks

[Florian Weimer]

"Joseph S. Myers" <jsm28@cam.ac.uk> writes:

> On Sun, 14 Oct 2001, Florian Weimer wrote:
>
>> According to the language standard, buffer overflow detection for
>> character pointer types is possible only for buffers which are not
>> nested in other objects (in struct or union objects).  Overflowing
>> character buffers has a well-defined effect if the buffer is contained
>> in an object (and other objects follow the buffer inside this object),
>> so a C implementation is not free to detect such errors (which is only
>> possible if the buffer overflow triggers undefined behavior). ;-)
>
> This is a gross over-simplification of the problem of exactly when an
> object can be accessed through a given pointer.  For details see Nick
> Maclaren's "What is an object when it is at home?" paper, except that I
> don't think he's published it beyond the UK and WG14 reflectors.  For
> examples where the committee has ruled that bounds of sub-objects can't be
> exceeded, see DR#017 question 16, and DRs #051 and #178 relating to the
> "struct hack".

The struct hack for character arrays results in strictly conforming
programs because arithmetic on pointers to a character type is not
restricted in any way, as long the enclosing object is not left.  This
is a consequence of 6.3.2.3(7).

However, this only applies to pointers to a character type, and not to
other pointer types.  Of course, it's clearly not desirable that types
which are used to implement the frequently used string idiom have this
property, but that's the way the language is defined.

Re: Buffer Overflow Attacks

[Joseph S. Myers]

On Sun, 14 Oct 2001, Florian Weimer wrote:

> The struct hack for character arrays results in strictly conforming
> programs because arithmetic on pointers to a character type is not
> restricted in any way, as long the enclosing object is not left.  This
> is a consequence of 6.3.2.3(7).

6.3.2.3#7:

       [#7]  A  pointer  to  an  object  or  incomplete type may be
       converted to a pointer to a different object  or  incomplete
       type.   If the resulting pointer is not correctly aligned57)
       for  the  pointed-to  type,  the  behavior   is   undefined.
       Otherwise,  when  converted  back  again,  the  result shall
       compare equal to the original pointer.  When a pointer to an
       object  is  converted  to a pointer to a character type, the
       result points to the lowest addressed byte  of  the  object.
       Successive  increments  of the result, up to the size of the
       object, yield pointers to the remaining bytes of the object.

The problem is, what is "the object"?  In the struct hack, it is quite
arguably an array of size 1 within the structure - not the larger area
within which the structure was allocated.

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: Buffer Overflow Attacks

[Michael Eager]

Florian Weimer wrote:
> 
> "Joseph S. Myers" <jsm28@cam.ac.uk> writes:
> 
> > On Sun, 14 Oct 2001, Florian Weimer wrote:
> >
> >> According to the language standard, buffer overflow detection for
> >> character pointer types is possible only for buffers which are not
> >> nested in other objects (in struct or union objects).  Overflowing
> >> character buffers has a well-defined effect if the buffer is contained
> >> in an object (and other objects follow the buffer inside this object),
> >> so a C implementation is not free to detect such errors (which is only
> >> possible if the buffer overflow triggers undefined behavior). ;-)
> >
> > This is a gross over-simplification of the problem of exactly when an
> > object can be accessed through a given pointer.  For details see Nick
> > Maclaren's "What is an object when it is at home?" paper, except that I
> > don't think he's published it beyond the UK and WG14 reflectors.  For
> > examples where the committee has ruled that bounds of sub-objects can't be
> > exceeded, see DR#017 question 16, and DRs #051 and #178 relating to the
> > "struct hack".
> 
> The struct hack for character arrays results in strictly conforming
> programs because arithmetic on pointers to a character type is not
> restricted in any way, as long the enclosing object is not left.  This
> is a consequence of 6.3.2.3(7).

I think that this is stretching reading of this paragraph.  Creating
a valid pointer address does not mean that deferencing the pointer is
defined.

If you have the following:

	struct foo {
	   char c[31];
  	   int  i;
	} f;

	char *p1;

You can create a pointer which points beyond the end of the array f.c:

	p1 = &f.c[32];

The effect of dereferencing this pointer is undefined.  There are few
restrictions on the layout of structures.  Commonly there would be 
padding bytes placed between c and i.  Referencing these padding bytes
is undefined.  

Indeed, in a hypothetical processor with very fine grained memory 
protection, any padding bytes placed between c and i in the struct may
be both unreadable and/or unwritable.  (We won't consider the havoc
this might cause to memcopy.)



--
Michael Eager     eager@mvista.com	408-328-8426	
MontaVista Software, Inc. 1237 E. Arques Ave., Sunnyvale, CA  94085

Re: Buffer Overflow Attacks

[dewar]

<<According to the language standard, buffer overflow detection for
character pointer types is possible only for buffers which are not
nested in other objects (in struct or union objects).  Overflowing
character buffers has a well-defined effect if the buffer is contained
in an object (and other objects follow the buffer inside this object),
so a C implementation is not free to detect such errors (which is only
possible if the buffer overflow triggers undefined behavior). ;-)
>>

Well there is room for argument on the above analysis (since the standard
does not fully specify how composite types are layed out), but in any case,
it is always just fine to have a switch that requires sensible restrictions
on behavior, regardless of the standard, subsetting is always allowed, and
it is also just fine to compile sensitive code with such a switch and insist
that it conforms to some safe subset.

Re: Buffer Overflow Attacks

[mike stump]

> Date: Thu, 18 Oct 2001 15:02:24 -0700
> From: Michael Eager <eager@mvista.com>
> To: Florian Weimer <fw@deneb.enyo.de>
> CC: "Joseph S. Myers" <jsm28@cam.ac.uk>, gcc@gcc.gnu.org

> I think that this is stretching reading of this paragraph.  Creating
> a valid pointer address does not mean that deferencing the pointer is
> defined.

Well, I can't comment on the exact code you gave, but I can comment on
C++ and code like this:

struct foo {
  char c[31];
  int i;
} f;

  *(((char*)&f)+32) and *(((char*)&f)+33) are allowed.

C must have the same rules for this case.  If they don't they got it wrong.

> Referencing these padding bytes is undefined.

Nope.  See above.  Let's suppose that there are 16 bytes of padding in
there.  The two expressions about, must work.

> Indeed, in a hypothetical processor with very fine grained memory
> protection, any padding bytes placed between c and i in the struct
> may be both unreadable and/or unwritable.

Nope.  Cannot be done in C++.  If C doesn't say this, it is wrong.

Re: Buffer Overflow Attacks

[Florian Weimer]

mike stump <mrs@windriver.com> writes:

> Well, I can't comment on the exact code you gave, but I can comment on
> C++ and code like this:
> 
> struct foo {
>   char c[31];
>   int i;
    int j;

(Otherwise the argument below is wrong, especially if sizeof(int)
equals sizeof(char).)

> } f;
> 
>   *(((char*)&f)+32) and *(((char*)&f)+33) are allowed.

Yes, that's right even for C.  But this doesn't help in the case I
originally presented.  While we certainly have (&(f.c[30])) equal to
(((char *)&f) + 30) (they both refer to the same object), it occured
to me that &(f.c[32]) is indeed undefined, but (((char *)&f) + 32) is
defined.  It's a bit funny that if two objects which compare equal
show such different behavior, but I think that's way it's specified in
the standard.

So I have to retract my original claim that it was impossible to do
buffer overflow checks in such cases.  After all, a pointer in C-speak
(or "address", as in "address-of operator") is not very similar to a
machine address.

Re: Buffer Overflow Attacks

[mike stump]

> To: mike stump <mrs@windriver.com>
> Cc: eager@mvista.com, gcc@gcc.gnu.org, jsm28@cam.ac.uk
> From: Florian Weimer <fw@deneb.enyo.de>
> Date: Wed, 31 Oct 2001 19:23:54 +0100

> So I have to retract my original claim that it was impossible to do
> buffer overflow checks in such cases.  After all, a pointer in
> C-speak (or "address", as in "address-of operator") is not very
> similar to a machine address.

Off Topic: A pointer in C speak is exactly like a machine address.
Please show us C code that shows a difference.  comp.lang.c is a
better place for these types of comments.