[LWN Logo]

Date:	Tue, 27 Oct 1998 16:23:54 +0300
From:	Serge Orlov <sorlov@CON.MCST.RU>
Subject:      Multi-stack allocator: another way to prevent stack smashing
To:	BUGTRAQ@NETSPACE.ORG

  I would like to annouce the first release of multi-stack allocator
for C programs. "Multi-stack" is a technique of allocating local
arrays to prevent exploits for the most of buffer overflows. It's NOT
a complete solution for buffer overflows. See paragraph "Limitations"
for details. The package consists of patch for egcs compiler
version 1.1 (publicly available from http://egcs.cygnus.com) and
run-time library.

How it works.
  It's quite simple.
All local arrays are allocated not in the "ordinary" stack, but
in additional stacks. Each array goes into its own stack and
those stacks grow up. Here is data layout for function that
is written in C as:

int f(void)
{
    char path[20];
    int  flag_i_am_root;
    char floh[100];
.......

***** Means no data.

"Ordinary" stack layout (stack grows down):

------------------------------------------------------------------
** |   floh   |flag_i_am_root| path | return address | Caller data
------------------------------------------------------------------

"Multi-stack" layout:
  now in the "ordinary" stack (stack grows down):
------------------------------------------------------------------
******************* |flag_i_am_root | return address | Caller data
------------------------------------------------------------------

    Unaccessible pages between upper and lower stacks

(stack grows up)
------------------------------------------------------------------
 Caller data or no data | path | *********************************
------------------------------------------------------------------

    Unaccessible pages between upper and lower stacks

(stack grows up)
------------------------------------------------------------------
 Caller data or no data |   floh   | *****************************
------------------------------------------------------------------

  Suppose, function f has big overflow of array "path". In the
case of "ordinary" stack it will overflow its return address.
In the case of multi-stack, it will overwrite "no data" area.
  Suppose, function f has one byte overflow of array "floh". In
the case of "ordinary" stack it will overflow flag_i_am_root.
This can be enough to make it positive. In the case of multi-stack,
it will overwrite "no data" area.

How to use it.
  Install it. Recompile and relink your program with the option
"-fmulti-stack". That's all.

Limitations.
  1. Buffer overflows in the data segment are not prevented.
  2. Arrays in structures are still placed in the "ordinary"
     stack (it's the limitation of current version, in the
     future it is possible to place them in their own stack.
     However, that will only protect scalar variables and
     function return address.)
     I guess buffer overflow of arrays in structures are rare.
  3. If caller and callee have arrays, and callee overflows
     caller's array, then callee's array will be overwritten.
     I guess it is rare, but this issue can be addressed in
     the future.
  4. Program or shared library MUST run with stack top at the
     address which is built into compiler.
  5. No debug information for local arrays.

Performance impact and memory consumption.
  Egcs compiler that was "multi-stacked" runs 0.3-0.8% slower.
Egcs is a good test, since it uses quite a big number of arrays
(up to 25 in one function). I guess average slowdown is about 0.5
percent.
  It's hard to say how much additional memory does it need. In
the worst case it's max_number_of_arrays_in_one_function *
a_little_bit_less_than_max_ordinary_stack_size. The worst case
also means that your program runs for very long time. For my
home workstation max_number_of_arrays_in_one_function is about 2
for daemons and suid programs, sum of max_ordinary_stack_size is
about 250kb. So the total additional memory is 0.5Mb for me.

Portability.
  The technique is portable, but the current version is for
Linux/i386.

Where to get it.
  http://www.ipmce.su/~sorlov/security.html




                                    Serge Orlov <sorlov@con.mcst.ru>.