|=---------------------=[ Introduction to the x86 Stack ]=--------------------=| |=----------------------------------------------------------------------------=| |=-------------------------=[ lhall@telegenetic.net ]=------------------------=| ---[ Introduction to the almighty Stack. The first and most important instructions to understand the stack are push and pop. The `pushl %eax` instruction in C looks like: esp = esp - (sizeof(int)); memory[esp] = eax; and in asm: subl $4, %esp movl %eax, (%esp) While the `popl %eax` in C looks like: eax = memory[esp]; esp = esp + (sizeof(int)); and in asm: movl (%esp), %eax addl $4, %esp The stack is a data structure that works on the principle of last in first out (LIFO). LIFO means that the last item put on the stack is the first item that can be taken off, althought with the stack you cannot remove any item execpt for the last one put in although you can access the value of any area of the stack you have permission too. A stack-based computer system is one that is based on the use of stacks, rather than being register based. The stack starts at high memory and grows down, so if the stack top starts at the address 0xbfffffff and we add something thats four bytes to it we have 0xbfffffff-4 which is 0xbffffffb. We can use gdb to do all our hex math for us (assuming you understand C's printf and format strings). entropy@phalaris asm $ gdb GNU gdb 6.3 Copyright 2004 Free Software Foundation, Inc. GDB is free software, covered by the GNU General Public License, and you are welcome to change it and/or distribute copies of it under certain conditions. Type "show copying" to see the conditions. There is absolutely no warranty for GDB. Type "show warranty" for details. This GDB was configured as "i386-pc-linux-gnu". (gdb) printf "0x%x\n", 0xbfffffff - 4 0xbffffffb (gdb) quit This is usually quicker then using a hex calculator as we are usually in gdb when we need to do this. So lets see this in action, assemble and link this simple program. entropy@phalaris asm $ cat stack.s .section .text .globl _start _start: nop pushl $100 pushl $200 pushl $300 popl %eax popl %eax popl %eax movl $1, %eax movl $0, %ebx int $0x80 entropy@phalaris asm $ as -g stack.s -o stack.o entropy@phalaris asm $ ld stack.o -o stack All this program does is push three longs (4 bytes each) onto the stack, then it pops them off the stack into the register eax. We can pop them off the stack into and of the general purpose registers, for now it dosent matter which we use. The next part should be familiar from the last tutorial, its the exit syscall (move 1 into eax, one is the syscall number for exit, then move 0 into ebx which is the return value for exit). What we are expecting to see is this, the stack will start at some address we will call X for now, the first push should make the stack address X-4 (stack grows downward toward lower memory remember), then next push should make it X-8, and the third one X-12. Then the pops should reverse that so when were dont the third pop the stack address should be back to our original X. entropy@phalaris asm $ gdb stack GNU gdb 6.3 Copyright 2004 Free Software Foundation, Inc. GDB is free software, covered by the GNU General Public License, and you are welcome to change it and/or distribute copies of it under certain conditions. Type "show copying" to see the conditions. There is absolutely no warranty for GDB. Type "show warranty" for details. This GDB was configured as "i386-pc-linux-gnu"...Using host libthread_db library "/lib/libthread_db.so.1". Ok set our breakpoint at the address of the _start label plus one. (gdb) break *_start+1 Breakpoint 1 at 0x8048095: file stack.s, line 5. List our source code our. (gdb) list _start 1 .section .text 2 .globl _start 3 _start: 4 nop 5 pushl $100 6 pushl $200 7 pushl $300 8 popl %eax 9 popl %eax 10 popl %eax (gdb) 11 movl $1, %eax 12 movl $0, %ebx 13 int $0x80 And start the program running. (gdb) run Starting program: /home/entropy/asm/stack Breakpoint 1, _start () at stack.s:5 5 pushl $100 Current language: auto; currently asm Ok we hit our breakpoint, and are now paused at the first instruction which is the pushl $100, or push long value 100 onto the stack. Lets first find what the current value of esp is, esp points to where we currently are in the stack, hence its name extended stack pointer or esp. (gdb) x $esp 0xbfae91d0: 0x00000001 So esp points to the address 0xbfae91d0 and the value at that address is 0x00000001, the value dosent matter for now. This means that the top of our stack for this program starts at 0xbfae91d0 when we hit our break point. All elf binaries actually have their stack start at 0xbfffffff which is a virtual address mapped to a physical one. When we do this push long we are expecting the address to be 0xbfae91d0 - 4 because, again, longs are four bytes and the stack grows downward to lower memory addresses. Use gdb to find out what our expected address will be. (gdb) printf "0x%x\n", 0xbfae91d0 - 4 0xbfae91cc It appears that after we do this push long esp will point to 0xbfae91cc. Execute the pushl $100 instruction. (gdb) step _start () at stack.s:6 6 pushl $200 Now examine what esp points to. (gdb) x $esp 0xbfae91cc: 0x00000064 It does indeed point to our 0xbfae91cc address, but what is 0x00000064? Print it in decimal with another printf. (gdb) printf "%d\n", 0x00000064 100 Its the 100 that was pushed onto the stack, but represented in hex not decimal (6*16 + 4 = 100). Where is esp going to point after the next push long? The current address of esp which is 0xbfae91cc minus another 4. (gdb) printf "0x%x\n", 0xbfae91cc - 4 0xbfae91c8 Which is 0xbfae91c8, so step again. (gdb) step _start () at stack.s:7 7 pushl $300 Examine what esp points to. (gdb) x $esp 0xbfae91c8: 0x000000c8 Its the address we knew it would go to, and the value 0x000000c8 is our 200 in hex. (gdb) printf "%d\n", 0x000000c8 200 So our last push long will be at 0xbfae91c8 - 4, let see where thats at. (gdb) printf "0x%x\n", 0xbfae91c8 - 4 0xbfae91c4 Next address should be 0xbfae91c4. (gdb) step _start () at stack.s:8 8 popl %eax (gdb) x $esp 0xbfae91c4: 0x0000012c It is, and the value at 0xbfae91c4, 0x0000012c is easily guessable. (gdb) printf "%d\n", 0x0000012c 300 We are now done out pushes and are going onto the popl's. pop longs pop values off the stack and into a register, so its going to pop the value off and move up the stack the size of what was popped. (gdb) x $esp 0xbfae91c4: 0x0000012c The stack value is at 0xbfae91c4, so the first pop will make it 0xbfae91c4 + 4 because we are now going up the stack be removing things. (gdb) printf "0x%x\n", 0xbfae91c4 + 4 0xbfae91c8 First pop long will make it 0xbfae91c8, let see. (gdb) step _start () at stack.s:9 9 popl %eax (gdb) x $esp 0xbfae91c8: 0x000000c8 We calculated the address correct, and the pop long has popped the value that was at 0xbfae91c4 into eax, so lets check out eax. (gdb) print $eax $1 = 300 And its the 300 that was the last thing pushed onto the stack. Next pop long is another 4 up the stack. (gdb) printf "0x%x\n", 0xbfae91c8 + 4 0xbfae91cc (gdb) step _start () at stack.s:10 10 popl %eax (gdb) x $esp 0xbfae91cc: 0x00000064 And the value in eax now. (gdb) print $eax $2 = 200 Another 4 up. (gdb) printf "0x%x\n", 0xbfae91cc + 4 0xbfae91d0 (gdb) step _start () at stack.s:11 11 movl $1, %eax (gdb) x $esp 0xbfae91d0: 0x00000001 Final value popped into eax, also notice the value of esp is 0xbfae91d0, exactly what we started with. (gdb) print $eax $1 = 100 (gdb) step _start () at stack.s:12 12 movl $0, %ebx (gdb) step _start () at stack.s:13 13 int $0x80 (gdb) step Program exited normally. (gdb) quit entropy@phalaris asm $ At the start of the program: Stack top is 0xbfae91d0 (I show the values on the stack as 0x00000000 when they will usually have the old values left on the stack from previous stack frames). Address Value -------------- 0xbfae91d0: | 0x00000001 | <--- esp points here -------------- 0xbfae91cc: | 0x00000000 | -------------- 0xbfae91c8: | 0x00000000 | -------------- 0xbfae91c4: | 0x00000000 | -------------- pushl $100, add 4 bytes to esp then push long value 100 into where esp is pointing. Address Value -------------- 0xbfae91d0: | 0x00000001 | -------------- 0xbfae91cc: | 0x00000064 | <--- esp points here now -------------- 0xbfae91c8: | 0x00000000 | -------------- 0xbfae91c4: | 0x00000000 | -------------- pushl $200, add 4 bytes to esp then push long value 200 into where esp is pointing. Address Value -------------- 0xbfae91d0: | 0x00000001 | -------------- 0xbfae91cc: | 0x00000064 | -------------- 0xbfae91c8: | 0x000000c8 | <--- esp points here now -------------- 0xbfae91c4: | 0x00000000 | -------------- pushl $300, add 4 bytes to esp then push long value 300 into where esp is pointing. Address Value -------------- 0xbfae91d0: | 0x00000001 | -------------- 0xbfae91cc: | 0x00000064 | -------------- 0xbfae91c8: | 0x000000c8 | -------------- 0xbfae91c4: | 0x0000012c | <--- esp points here now -------------- Now were done the pushes start doing to pop's. popl %eax, pop the value esp points to into eax then add 4 bytes to esp. Address Value -------------- 0xbfae91d0: | 0x00000001 | -------------- 0xbfae91cc: | 0x00000064 | -------------- 0xbfae91c8: | 0x000000c8 | <--- esp points here now -------------- eax is 0x0000012c (300) 0xbfae91c4: | 0x0000012c | -------------- popl %eax, pop the value esp points to into eax then add 4 bytes to esp. Address Value -------------- 0xbfae91d0: | 0x00000001 | -------------- 0xbfae91cc: | 0x00000064 | <--- esp points here now -------------- eax is 0x000000c8 (200) 0xbfae91c8: | 0x000000c8 | -------------- 0xbfae91c4: | 0x0000012c | -------------- popl %eax, pop the value esp points to into eax then add 4 bytes to esp. Address Value -------------- 0xbfae91d0: | 0x00000001 | <--- esp points here now -------------- eax is 0x00000064 (100) 0xbfae91cc: | 0x00000064 | -------------- 0xbfae91c8: | 0x000000c8 | -------------- 0xbfae91c4: | 0x0000012c | -------------- All that is left is to do exit syscall. The stack is pretty easy to understand and work with, after you have stepped through it a bunch. # milw0rm.com [2006-04-08]