Playing with the heap and stack

Discuss how to write good code, break bad code, your current pet projects, or the best way to approach novel problems

Playing with the heap and stack

Post by WallShadow on Thu Aug 09, 2012 10:21 pm
([msg=68671]see Playing with the heap and stack[/msg])

Good afternoon everyone,

I was reading Hacking The Art of Exploitation recently, and in it, it states that the heap grows upwards dynamically toward the stack while the stack grows downward dynamically towards the heap. A bit of experimentation easily confirms this, and that immediately gives me the idea: crash the heap into the stack!

So I write a C program which instantiates an int on the stack and an int on the heap and then prints their addresses. At first it baffles me; about 9 out of 10 times, heap memory starts getting allocated at addresses AFTER the stack, for example:

Code: Select all
[0x0027ff14] my_Int = 32
[0x009a0f28] my_HeapInt = 26112
[0x009a0f48] my_HeapInt = 26112




I decide that, since 1 in 10 times the heap starts getting allocated before the stack, its worth a try. I added a while loop that keeps allocating heap memory until the heap addresses surpass the stack based my_Int address. This is the result:

Code: Select all
[0x0027ff14] my_Int = 32
[0x00030f28] my_HeapInt = 26112
[0x00030f48] my_HeapInt = 26112

Attempting to crash heap...

[0x00030f58] my_HeapInt = 26112
[0x00030f68] my_HeapInt = 26112
[0x00030f78] my_HeapInt = 26112
[0x00030f88] my_HeapInt = 26112
[0x00030f98] my_HeapInt = 26112
[0x00030fa8] my_HeapInt = 26112

( for the sake of brevity, i cut out addresses 0x00030fb8 - 0x000313e0 ... )

[0x000313f0] my_HeapInt = 26112
[0x00031400] my_HeapInt = 26112
[0x00031410] my_HeapInt = 26112
[0x00031420] my_HeapInt = 26112
[0x00031430] my_HeapInt = 26112
[0x008f0be0] my_HeapInt = 26112


Did you see that? I set the program to stop when the address of my_HeapInt exceeded the address of my_Int. Well, I guess you can consider a jump from 0x00031430 to 0x008f0be0 to surpass 0x0027ff14 by a wide margin. Da fuq is in between there that it had to jump so far? And wouldn't it be smarter to just start at such a high address in the first place?

So, I can't crash the heap into the stack :cry: . I know! Crash the stack into the heap!!!!

So I added a recursive function that infinitely calls itself. Results:

Code: Select all

[0x0027ff14] my_Int = 32
[0x00020f28] my_HeapInt = 26112
[0x00020f48] my_HeapInt = 26112

Attempting to crash heap...

[0x00020f58] my_HeapInt = 26112
[0x00020f68] my_HeapInt = 26112
[0x00020f78] my_HeapInt = 26112

( skipping addresses 0x00020f88 - 0x00021400 ... )

[0x00021410] my_HeapInt = 26112
[0x00021420] my_HeapInt = 26112
[0x00021430] my_HeapInt = 26112
[0x00990be0] my_HeapInt = 26112

If this prints, then the program has failed at crashing the heap :(

Attempting to crash stack :D

[0x0027fee8] my_Int = 32
[0x0027feb8] my_Int = 32
[0x0027fe88] my_Int = 32
[0x0027fe58] my_Int = 32
[0x0027fe28] my_Int = 32
[0x0027fdf8] my_Int = 32
[0x0027fdc8] my_Int = 32

( skipping 1100 KB worth of my_Int = 32 lines ... )

[0x00084768] my_Int = 32
[0x00084738] my_Int = 32
[0x00084708] my_Int = 32
[0x000846d8] my_Int = 32
[0x000846a8] my_Int = 32



At that point, the program crashed with a "a.exe has stopped responding..." error. I printed all of this to a txt file anticipating the crash. So whats the result? There is still a decent bit of memory between 0x000846a8 ( the address of the last successfully allocated Int variable ) and 0x00021430 (the address of the last Int allocated on the heap before it pole vaults over the stack) . What the fuck is in between them? Am I missing something here? Or is Windows just screwing with me?

Can anyone please help me out with this? I'm as confuzzled by this as a someone is on their first day on /b/.



Source code for anyone who wants to judge my crappy C skills:

Code: Select all
#include <stdio.h>


void recurse()
{
   
   int my_Int = 32;
   
   int * my_Int_Pointer = &my_Int;
   
   printf("[0x%08x] my_Int = %d\n", my_Int_Pointer, my_Int);
   
   recurse();
   
}


int main()
{
   
   int my_Int = 32;
   
   int * my_Int_Pointer = &my_Int;
   
   
   printf("[0x%08x] my_Int = %d\n", my_Int_Pointer, my_Int);
   
   
   int * my_HeapInt_Pointer = (int *) malloc(4);
   
   *my_HeapInt_Pointer = 26112;
   
   
   printf("[0x%08x] my_HeapInt = %d\n", my_HeapInt_Pointer, *my_HeapInt_Pointer);
   
   
   my_HeapInt_Pointer = (int *) malloc(4);
   
   *my_HeapInt_Pointer = 26112;
   
   
   printf("[0x%08x] my_HeapInt = %d\n", my_HeapInt_Pointer, *my_HeapInt_Pointer);
   
   
   
   if(my_HeapInt_Pointer < my_Int_Pointer)
   {
      
      printf("\nAttempting to crash heap...\n\n");
      
      while(my_HeapInt_Pointer < my_Int_Pointer)
      {
         
         my_HeapInt_Pointer = (int *) malloc(4);
         
         *my_HeapInt_Pointer = 26112;
         
         printf("[0x%08x] my_HeapInt = %d\n", my_HeapInt_Pointer, *my_HeapInt_Pointer);
         
      }
      
      printf("\nIf this prints, then the program has failed at crashing the heap :(\n\n");
      
      printf("Attempting to crash stack :D\n\n");
      
      recurse();
      
   }
   
}






-WallShadow <3
User avatar
WallShadow
Contributor
Contributor
 
Posts: 630
Joined: Tue Mar 06, 2012 9:37 pm
Blog: View Blog (0)


Re: Playing with the heap and stack

Post by LoGiCaL__ on Fri Aug 10, 2012 6:23 am
([msg=68676]see Re: Playing with the heap and stack[/msg])

I'm not 100% sure of this it's just a theory, but there may be something built in the system to prevent the crash and just handle it when the addresses come within a certain range of each other. I do admire your willingness to experiment though. Keep it up.

You should try making the program so that when it assigns the address it keeps the assignment and doesn't just move to the next address and assign that. This way when they do come close to each other there is nowhere to jump to because all the addresses are taken up.
User avatar
LoGiCaL__
Addict
Addict
 
Posts: 1063
Joined: Sun May 30, 2010 12:33 pm
Blog: View Blog (0)


Re: Playing with the heap and stack

Post by WallShadow on Fri Aug 10, 2012 9:49 am
([msg=68686]see Re: Playing with the heap and stack[/msg])

LoGiCaL__ wrote:You should try making the program so that when it assigns the address it keeps the assignment and doesn't just move to the next address and assign that. This way when they do come close to each other there is nowhere to jump to because all the addresses are taken up.


Sorry, I don't quite understand what you mean by this. Keep what assignments? All the variables that I assign are kept until the program dies. And I can't take up the memory that the heap jumps to because it is way past the stack.
User avatar
WallShadow
Contributor
Contributor
 
Posts: 630
Joined: Tue Mar 06, 2012 9:37 pm
Blog: View Blog (0)


Re: Playing with the heap and stack

Post by centip3de on Fri Aug 10, 2012 2:27 pm
([msg=68694]see Re: Playing with the heap and stack[/msg])

I love your spunk, kid. +1

This seems, to me at least, to be your compiler's version of compensating for an impending crash (it could go either way, your compiler could be blocking out a certain space in memory per variable, and throwing in a "je" (jump if equal) in the outputted ASM, comparing the two addresses, in hopes that if a newbie accidentally did this, they wouldn't really be in that big of a shit hole.).

Logically, how could Window's save itself from an impending crash in a variable it can't control? The OS can only control processes as a whole, the programs that are in said process space have to be able to control themselves. If it were the other way around, we wouldn't have BSOD's, would we? (Note, I do not know the Window's OS internals at all, so this could be completely wrong.).

Also, when compiling under a different compiler (GCC) and different OS (Ubuntu), nothing happened on my end. All it did was cycle through a bunch of addresses continuously. However, I did tell GCC to output all warnings to me, and it came up with this:

Code: Select all
centip3de@ubuntu:~/Desktop$ gcc -Wall Crash.c -o Crashes
Crash.c: In function ‘recurse’:
Crash.c:11:4: warning: format ‘%x’ expects argument of type ‘unsigned int’, but argument 2 has type ‘int *’ [-Wformat]
Crash.c: In function ‘main’:
Crash.c:26:4: warning: format ‘%x’ expects argument of type ‘unsigned int’, but argument 2 has type ‘int *’ [-Wformat]
Crash.c:29:4: warning: implicit declaration of function ‘malloc’ [-Wimplicit-function-declaration]
Crash.c:29:39: warning: incompatible implicit declaration of built-in function ‘malloc’ [enabled by default]
Crash.c:34:4: warning: format ‘%x’ expects argument of type ‘unsigned int’, but argument 2 has type ‘int *’ [-Wformat]
Crash.c:42:4: warning: format ‘%x’ expects argument of type ‘unsigned int’, but argument 2 has type ‘int *’ [-Wformat]
Crash.c:58:10: warning: format ‘%x’ expects argument of type ‘unsigned int’, but argument 2 has type ‘int *’ [-Wformat]
Crash.c:70:1: warning: control reaches end of non-void function [-Wreturn-type]
centip3de@ubuntu:~/Desktop$


My best advice would be to try it under a different compiler and see what happens. If you get what I got, then it must have just been your compiler being extra-careful (don't worry, you can probably disable that). If it wasn't your compiler, then it must be something with Window's being over protective (don't worry, you can install Linux).

Side note: It seems as though I get stack crashing errors in Linux when programming on a weekly basis... the only difference is that I wasn't trying to cause them. ;)
Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning. -Rick Cook
User avatar
centip3de
Moderator
Moderator
 
Posts: 1467
Joined: Fri Aug 20, 2010 5:46 pm
Blog: View Blog (0)


Re: Playing with the heap and stack

Post by LoGiCaL__ on Fri Aug 10, 2012 6:04 pm
([msg=68699]see Re: Playing with the heap and stack[/msg])

Ironically enough from stackoverflow lol : http://stackoverflow.com/questions/1334055/what-happens-when-stack-and-heap-collide

Googling stack heap collision brings up some good info.
User avatar
LoGiCaL__
Addict
Addict
 
Posts: 1063
Joined: Sun May 30, 2010 12:33 pm
Blog: View Blog (0)



Return to Programming

Who is online

Users browsing this forum: No registered users and 0 guests