slllib1.0: a simple C library for simple linked lists (en,it)

Summing up what we did in the previous posts about simple linked lists, here at c-lessons-online.org we put together the first release of slllib, a small and simple C library for handling simple linked lists in C.
The code is located in the downloads page of this blog. Please note that to download the code you need a gmail account and to wait for the authorization, that will be granted to everybody :). In the .rar file, you'll find a small demo of the library in the main.c file. The demo program is an interpreter of  simple commands for lists manipulation.

Riassumendo quanto fatto nei precedenti post sulle liste semplici collegate, qui a c-lessons-online.org abbiamo messo insieme slllib, una piccola libreria in C per la gestione di liste collegate semplici. Potete scaricare i sorgenti dalla pagina di download di questo blog. Notate che per scaricare la libreria dovete avere un'account gmail e attendere l'autorizzazione che non verrà negata a nessuno :). Nel file .rar troverete anche un piccolo demo della libreria nel file main.c. Il demo è un interprete di semplici comandi per la manipolazione delle liste.

Stack overflow in C: when size matters (part 1 of 2)

As a programmer or analyst-programmer, understanding stack/buffer overflow, and knowing how to find and mitigate it, is useful, at least, in two circumstances:

• when you are debugging a piece of code, dealing with unpredictable run time behaviors. In this case, it is highly probable that, you are facing a buffer overflow problem and you have to find it. Soon!
• when you are working on a software of which buffer overflow flaws  could be eventually exploited in order to damage you, your organizations or your customers.

In this post I'd like to focus on the first topic.

Let start having a look at a simple C program with a simple buffer overflow.

#include
int main(void){
   char c[4] = { 'A', 'B', 'C', 'D' };
   char d[4] = { 'W', 'X', 'Y', 'Z' };
   printf("c[0] is '%c'\n", c[0]);    
d[4] = 'Z';
   printf("c[0] is '%c'\n", c[0]);    
return 0;
}
Most of us, looking at the previous code would think that the output should be:
c[0] is 'A'

c[0] is 'A'

Are we sure? Lets compile, link and execute it! Drum Roll, please. The output is: 

c[0] is 'A'

c[0] is 'Z'

What happened here? After the first printf, the statement d[4] = 'Z'; put the character  'Z' in the fifth position of the char array d. But. wait  a moment, d is a 4 elements array. How is it possible to write beyond the limits of the array and, why didn't the  C compiler  warn us about it? To understand this, I'd suggest to check the following link for a discussion on this topic: Why do compilers not warn about out-of-bounds static array indices?. If you don't have time or you don't want to leave me alone  to go there  :), to make it short, in C there is no strict buffer checking in order to produce lighter and faster code then other programming language. There is another question that need to be answered:
Where the hell  did the statement "d[4] = 'Z';" write the 'Z' character? Well, apparently, it went in the first position of the c array. How is it possible?
When the compiler read the two declaration:

   char c[4] = { 'A', 'B', 'C', 'D' };
   char d[4] = { 'W', 'X', 'Y', 'Z' };
it reserves enough contiguous space in the program stack to store the c and d array.
Compiling the code with gcc -S or using a smart :) IDE like Eclipse, we can have a look at the corresponding assembly code. Here I copied it for you from the Eclipse's disassembly window:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 main: push %ebp mov %esp,%ebp and $0xfffffff0,%esp sub $0x20,%esp call 0x401918 <__main> char c[4] = { 'A', 'B', 'C', 'D' }; movb $0x41,0x1c(%esp) movb $0x42,0x1d(%esp) movb $0x43,0x1e(%esp) movb $0x44,0x1f(%esp) char d[4] = { 'W', 'X', 'Y', 'Z' }; movb $0x57,0x18(%esp) movb $0x58,0x19(%esp) movb $0x59,0x1a(%esp) movb $0x5a,0x1b(%esp) printf("c[0] is '%c'\n", c[0]); mov 0x1c(%esp),%al movsbl %al,%eax mov %eax,0x4(%esp) movl $0x403064,(%esp) call 0x401b50 <printf> d[4] = 'Z'; movb $0x5a,0x1c(%esp) printf("c[0] is '%c'\n", c[0]); In particular, gcc reserves 0x20 (32 in decimal) bytes for the main local data at line 5. You are authorized to ask why 32 bytes and not 4 bytes (one for each char of c) + 4 bytes (one for each char of d) = 8 bytes. You can ask. But, answering it would bring us too far and it is not strictly important to understand this example. If there will be any request about it we play with it and understand why does it happen :).

Taking into account that 0x41 is the ASCII code for 'A', we can easily recognize the assembly statements that initialize the arrays c (line 8 to 11) and d (line 13 to 16).

As for up to line 16, the stack content can be represented as in the figure on the right.
Then, the instruction d[4] = 'Z'; is executed and, without any warning, the code smashes the d array and put 'Z' ASCII code in the memory location +0x1C, that is the memory location where c[1] is stored.
So the following printf correctly print the content of c[1], that is 'Z' and not 'A' as expected.

What should we do to avoid buffer overflow? Add code to check array boundary! And, when you are debugging programs with an apparent unpredictable behavior, check all the statements assigning value to arrays elements.
In the second part of this post we'll try to understand together how buffer overflow can be a potential security vulnerability.

Assembly programming using gcc (part 2)

In the previous post we saw the inline assembly programming features of gcc. It is now time to have a look at how to interface C programs with assembly code file (.S file containing only assembly instructions, assembled and linked like another C file).
To do this we need to understand how the C compiler realize the two well known mechanisms: parameter passing by value and parameter passing by reference.
High-level languages have standard ways to pass data known as calling conventions. For high-level code to interface with assembly language, the assembly language code must use the same conventions as the high-level language. These conventions allow one to create subprograms that are re-entrant. A re-entrant subprogram may be called at any point of a program safely (even inside the subprogram itself). The major concern of these conventions is the description of the rules governing the use of the system stack. Before to call the function the caller program must "push" the parameters  onto the stack in case of parameter passing by value or the parameter's address in case of passage by reference.
Let examine together the following C code example:

void f(char a, char b, char c)
{
   char buffer1[6];
   int d;
}
void main() {
  function(1,2,3);
}

If we want to see how the C compiler implementthe function's parameter passing mechanisms  in assembly language,  there are two possibilities:

1. Feed gcc with this code and the -S option, i.e. gcc -S example.c;
2. Disassemble the executable produced by the compiler:

Because in Eclipse is so straightforward to see the disassembled code, just look at the dissambly windows of the debugger perspective :), I've hard-copied this qindow in the figure on the left where we can see the assembly translation in AT&T  syntax of the previous C code.
Here we can see that the caller program before to invoke the function f , pushes onto the stack the values of the three parameters:

20 f(1,2,3);
004013b4: movl $0x3,0x8(%esp)
004013bc: movl $0x2,0x4(%esp)
004013c4: movl $0x1,(%esp)
004013cb: call 0x40138c <f>

Note that gcc, to speed up the things, prefers to use the movl instructions instead of the push ones to implement the push mechanism.

Anyway, what it really does is:

push 3;
push 2;
push 1;
call f;

So, the stack before the call of the function f, together with the memory layout of the executing process, is as depicted in the following figure:

Note that, depending on the implementation, the stack will either grow downward (towards lower memory addresses), or upward. In the case of the Intel, Motorola, SPARC and MIPS processors the stack grows downward. The stack pointer (SP) is also implementation dependent. It may point to the last address on the stack, or to the next free available address after the stack. In the case of Intel processors it points to the last address on the stack.

When the call instruction is executed to invoke the f function, the microprocessor save the 

At the beginning of the f function, the EBP register is saved onto the stack and is used to save the current address of the top of the stack (ESP). Why? Because the C calling convention requires the value of EBX to be unmodified by the function call. If this is not done, it is very likely that the program will not work correctly. So the next two assembly instruction will surely be the standar  prologue of our assembly routines skeleton linkable with C programs.

f:0040138c: push %ebp
0040138d: mov %esp,%ebp

Note that it is mandatory, at the end of the procedure, to restore the original value of EBP and deallocate the local variables restoring the initial stack pointer ESP. This is done with the following two assembly statements that will be the standard epilogue of our function skeleton: 

mov %ebp,%esp; deallocate locals
pop %ebp; restore original EBP value

Goinge back to our disassembly listing, we can see that the next instruction written by the compiler is:

0040138f:   sub $0x1c,%esp

Here the compiler is making room in the stack for the function f local variables. This is done decreasing the stack pointer ESP of 0x1c (decimal 28). Remember that the stack grows toward low memory addresses. But. Hey, wait a moment! Why does the compiler reserve 28 bytes to make room for the two variables buffer1 and d that needs only: size(buffer1)+size(d)=6+4=10 bytes?
The answer is composed by several pieces:

• First of all, we must remember that memory can only be addressed in multiples of the word size. A word in our case is 4 bytes, or 32 bits. So our 6 byte buffer needs two words to be stored, that is 8 bytes instead of 6!
• Then, we have to reserve room for d, that is one word or 4 bytes.
• Then, the compiler want to reserve rooms to make a copy of the function parameters. There are three char parameters, but for each char variables we have to use 1 word. So we have 12 bytes for the parameters.
• Finally, we must take into account that we pushed onto the stack the 4 bytes EBP register and this account for 4 bytes more .

Summing up all the previous quantities, we have 8+4+12+4=28 bytes. In this way, the compiler create a safe 28 bytes long stack frame to isolate the current contest of the function from the eventual new frame that , eventually, could be necessary to be implemented, for example, in case of calls to other function inside f o recursive calls of f. Puff... Puff...Puff.
This was a little boring! Wasn't it?
Anyway, lets try to summarize what we learned so far. The skeleton of our assembly routine callable from C program should be:

subprogram_label:
  push %ebp
  mov %esp,%ebp
  sub SZ,%esp ; SZ=# bytes needed by local variables
  ; subprogram code
  mov %ebp,%esp
  push %ebp
  ret

Note that the prologue and epilogue of a subprogram can be simplified by using two special instructions that are designed specifically for this purpose. The ENTER instruction performs the prologue code and the LEAVE performs the epilogue. The ENTER instruction takes two immediate operands. For the C calling convention, the second operand is always 0. The first operand is the number bytes needed by local variables. The LEAVE instruction has no operands.

To understand how to access to the passed parameters we can look at how the compiler did it in our simple program:

mov 0x8(%ebp),%ecx   ; move the value of a in ecx
mov 0xc(%ebp),%edx   ; move the value of b in edx
mov 0x10(%ebp),%eax  ; move the value of a in eax

It means that in our stack frame we have:

Location   : data 

EBP + 0x10 : content of c

EBP + 0xc  : content of b

EBP + 0x8  : content of a

EBP + 4    : Return address

EBP        : saved EBP

In case of parameters passed by reference, the caller program pushes the address of the variable instead of its content and the called routine access the address of the variable and can read and, eventually, modifies the content of the passed variables.

So far we saw how to deal with a void function, but what does it happen when we need to write a non void function? 

The C calling conventions specify how this is done. Return values are passed via registers. All integral
types (char, int, enum, etc.) are returned in the EAX register. If they are smaller than 32-bits, they are extended to 32-bits when stored in EAX. (How they are extended depends on if they are signed or unsigned types.) 64-bit values are returned in the EDX:EAX register pair. Pointer values are also stored in EAX. Floating point values are stored in the ST0 register of the math co-processor.

The C calling conventions specify also that after the subprogram is over, the parameters that were pushed on the stack must be removed by the caller program.  Other conventions are different. For example, the Pascal calling convention specifies that the subprogram must remove the parameters before returning to the caller program.