Tuesday, June 27, 2017

Looking at Memory Layout

The programming language C allows you to look at memory layout.

Why would you want to do this?

To get a look at how dangerous a stack crash or smash might be.

In the C run time environment, there is usually a region of memory for statically allocated variables, another for variables allocated through the library by calling malloc() and friends, and another for variables allocated dynamically on the stack. And, of course, there is a region for the runnable object code, can't forget that.

Early on, in the old world of sixteen-bit computing, the allocations often looked something like this:

  stack (dynamic variables, stack frames, return pointers)
0xFxxx ← SP
  heap (malloc()ed variables, etc.)
  statically allocated variables
  application code
  operating system code, variables, etc.

There were many variations, of course. An M6800 memory map might look something like this:

  reset vectors
  I/O ports and monitor code
  operating system code
  stack (dynamic variables, stack frames, return pointers)
0x8xxx ← SP
  heap (malloc()ed variables, etc.)
  statically allocated variables
  application code
  operating system variables

Either way, the problem is easy to see. In this kind of a map, the stack grows downward, and the malloc()ed variables in heap fill memory upward. There is a convenience of sorts, in that an application can be designed to use more of one and less of the other.

But they share the same space.

If a user pushes an application beyond its design limits the two regions can overlap. Since physical memory doesn't magically multiply and increase when the two overlap, writing to one overwrites what is in the other.

Imagine a chalkboard. You and a friend are working on a math problem at the chalkboard. You're doing the math on the left, and your friend is writing down the results that you get on the right.

Things go okay, until the two of you have about 20 results, and she starts erasing your work so she can write down your results.

You're trying to cooperate, but you just don't have enough room.

And after she erases your work to right down your results, if you have to go back, you don't know where to go back to. Your work is gone.

Or, say, you erase the results she has been so kind as to write down for you, to continue your work. That's just as bad, because you still end up not knowing where you are and how to go back so you can move ahead.

Larger address space and more memory doesn't make the problem go away, just gives you more room before things go boom. (There is a way to mitigate these problems, which I will talk about in another blog post on CPU design.)

That's the basic reason you want to know about the layout of your memory.

Now, I'm not going to do all of your homework for you, but this little bit of code can get you started:

/* stkreveal.c
// A Q&D tool to structure of C runtime address space.
// by Joel Matthew Rees, Amagasaki, Japan, 28 June 2017.
// Copyright 2017 Joel Matthew Rees, claimed to the extent possible.
// This source is very much derivative of so many other sources
// that claiming copyright should be meaningless.
// But lawyers are known to quibble for money,
// so I assert all such copyright as I can.
// Permission to use:
// Author extends permission to use the source
// and the object it produces when compiled freely
// for any and all purposes except to assert intellectual property claims.
// Author makes no claims about the safety or reliability of the code.

#include <stdlib.h>
#include <limits.h>
#include <stdio.h>

/* #define AUTOBLOCKSIZE */

#  if INT_MAX > 0x7fff
#     define BLOCKSIZE 0x10000000L
#  else
#     define BLOCKSIZE 0x4000
#  endif
#  define BLOCKSIZE 0x1000

void reportaddress( char * label, char * addr )
   printf( "%32s: %20p (%22lu)\n", label, addr, (unsigned long) addr );

char globalvariable[ BLOCKSIZE ];

int findandshow( int * argc, char * argv[] )
   char * mallocedblock = malloc( BLOCKSIZE );
   int flag = mallocedblock != NULL;

   reportaddress( "program parameters", (char *) argv );
   reportaddress( "main() parameters", (char *) argc );
   reportaddress( "findandshow() parameters", (char *) &argc );
   reportaddress( "mallocedblock", mallocedblock );
   reportaddress( "globalvariable", globalvariable );
   reportaddress( "reportaddress() function", (char *) reportaddress );
   if ( flag )
      free( mallocedblock );
   return flag;

int main( int argc, char * argv[] )
   return findandshow( &argc, argv ) ? EXIT_SUCCESS : EXIT_FAILURE;  

(If you copy and paste, remember to make sure the brackets and ampersands, etc., survived. I explain where to get a compiler in several places, here, for instance.)

On one of my computers, I get the following:

me@mycomputer:~/games$ cc -Wall -o stkreveal stkreveal.c
me@mycomputer:~/games$ ./stkreveal
              program parameters:       0x7ffc1411c938 (       140720645196088)
               main() parameters:       0x7ffc1411c84c (       140720645195852)
        findandshow() parameters:       0x7ffc1411c818 (       140720645195800)
                   mallocedblock:            0x24d3010 (              38613008)
                  globalvariable:             0x600b60 (               6294368)
        reportaddress() function:             0x40059c (               4195740)

The actual numbers change from run to run, because of something called memory randomization, that is used to slow down attackers who want to make use of this little game we are playing.

The remainder of this project is how to figure out what address is showing you what, where.

And to figure out how to protect yourself in a world where Intel doesn't protect you.

And you might be interested in the blog post that started this one, which is still in progress half done now. It will come in two three four parts:
  1. Explaining the currently published issues,
  2. outlining a better approach at addressed regions
  3. describing how CPU manufacturers could completely protect the return address stack,
  4. and describing my perfect ideal processor that probably shall never be.

Maybe it won't be giving away too many clues to mention a few useful tools if you are running a *nix workstation or something similar. Fellow blogspot denizen gallier2 reminded me on my main blog (#1 in the list of rants above) of the pmap utility. Reading the man page on that will point you to some other useful things, as well.

(mmap() and brk() may be of particular interest.)

To use pmap on a particular process, say an instance of bc or gforth or ruby, you would use ps to find out the process id:
ps wwaux | grep "gforth" $ ps wwaux | grep gforth
me       3281  0.0  0.1  22856  1412 pts/2    S+   11:00   0:00 gforth
me       3593  0.0  0.0   7412   884 pts/1    S+   11:01   0:00 grep gforth

The line of interest is the one in which the command is "gforth", not "grep gforth". If that output is confusing, you can use pgrep, to help figure out which is which:

$ pgrep -l gforth
3281 gforth
Now you know the process id, you can use pmap:
$ pmap 3281
3281:   gforth
0000000000400000    100K r-x--  /usr/bin/gforth-0.7.0
ffffffffff600000      4K r-x--    [ anon ]
 total            22860K
If you want to use pmap on the little program I showed you here, add a little wait-for-user-input loop at the end:

int main( int argc, char * argv[] )
   int ch = 0;
   int rval = findandshow( &argc, argv );
   while ( ( ( ch = fgetc( stdin ) ) != 'q' )
            && ( ch != EOF ) )
      /* do nothing. */
   return rval ? EXIT_SUCCESS : EXIT_FAILURE;  

 Typing 'q' and hitting enter will stop the program. While it's running, you can open another terminal window, find the process id with "pgrep stkreveal", and take a pmap of it.

Beyond that is your homework. Have fun.

But be careful with the knowledge you get from this sort of homework. Don't fall into the trap of thinking, "It's just a computer."