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>.