How to code debuggers

/ 1评 / 0赞

How to code debuggers reships from taw's blog

Coding low-level infrastructure like kernels, compilers, and linkers can be
very scary, and most programmers stay as far away from them as they can.
And the scariest of all are debuggers, which rip apart warm flesh of innocent
programs, and use the dark side of the force to control them. Every decent
Computer Science course includes coding at least a toy compiler, most also
toy interpretters, virtual machines, and disassemblers, but how many people
wrote even the most toyish debugger ? (by debugger I mean any tool for low-
level analysis of running programs, wheather it single steps, traces execution,
or does something else)

Most debuggers are written in C, so touching their code is pretty much out of
the question. It's hard enough without having to use 30 year old and
about 32 time less productive tools.

Why would anybody want to write a debugger ? Many people work almost exc-
lusively with high-level languages running on virtual machines, and they probably
don't need to - high-level languages provide a lot of reflection and run-time program
modification abilities that writing custom debugging tools won't be necessary.
Many people are satisfied by available debuggers, or at least find them flexible
enough to write custom debugging tools around them. strace plus perl one-liners
certainly saved people years of debugging time.

And then there are people who have to do low-level coding, and find perl scripting
around existing tools insufficient, but because debuggers seem so scary they
simply learned to live with bad tools.

How debuggers work

Debuggers are based on a few simple techniques. I'll talk about Linux and other modern
Unices here like Solaris and FreeBSD. On other systems the details differ, but principles
are similar.

That's about it. Sometimes these techniques are insufficient, for example when debugging
kernel bugs. Then there are fancier tricks like kernel modules and running on a virtual
machine, but it's very rarely needed.

ptrace

1

long ptrace(enum __ptrace_request request, pid_t pid, void *addr, void *data);

Most debugging tools are based on ptrace. ptrace is extremely useful but almost unknown syscall.

To start tracing some process simply include in your C program, and attach with
ptrace(PTRACE_ATTACH, process_pid, 0, 0).

Then you can read and write its registers:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void *get_instruction_pointer(pid_t pid)
{
  return (void *)ptrace(PTRACE_PEEKUSR, pid, 4 * EIP, 0);
}
 
void set_instruction_pointer(pid_t pid, void *addr)
{
  ptrace(PTRACE_POKEUSR, pid, 4 * EIP, (long)addr);
}
 
and data:
 
void *get_stack_pointer(pid_t pid)
{
  return (void *)ptrace(PTRACE_PEEKUSER, pid, 4 * UESP, 0);
}
 
void *get_return_addr(pid_t pid, void *stack_pointer)
{
  return (void *)ptrace(PTRACE_PEEKTEXT, pid, stack_pointer, 0);
}

For "historical reasons" PEEK means read, and POKE means write. Available requests are:

Under Linux code and data are not separated, so PTRACE_PEEKDATA equals PTRACE_PEEKTEXT
and PTRACE_POKEDATA equals PTRACE_POKETEXT. Registers can be read/written either through
PEEKUSR/POKEUSR or through GETREGS/SETREGS, whichever is more convenient.

ptrace is very low level. Reads and writes only do one (probably aligned) machine word at time. It's not
difficult to wrap these routines in some more convenient interface.

So you know how to manipulate programs. The only missing part is breakpoints.
Breakpoints are actually pretty easy:

Disabling breakpoits is even easier - just write back the old instruction.
Running breakpointed code is a little more tricky:

As we can only read and write full words at time, what actually happens is that we read 4 bytes,
modify one of them, and write back 4 bytes (one with breakpoint, and 3 around it).

ptrace in action

There are many ptrace-based tools, like strace for tracing syscalls, ltrace for tracing shared library calls, and gdb uses ptrace too.

ptraceing process can be ptraced, so let's see what happens inside a tracing process. strace -o metastrace strace true traces strace as it traces true and saves the trace to metastrace file.

Here's a fragment:

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

ptrace(PTRACE_SYSCALL, 7973, 0x1, SIG_0) = 0
wait4(-1, [{WIFSTOPPED(s) && WSTOPSIG(s) == SIGTRAP}], __WALL, NULL) = 7973
--- SIGCHLD (Child exited) @ 0 (0) ---
ptrace(PTRACE_PEEKUSER, 7973, 4*ORIG_EAX, [0x5]) = 0
ptrace(PTRACE_PEEKUSER, 7973, 4*EAX, [0xffffffda]) = 0
ptrace(PTRACE_PEEKUSER, 7973, 4*EBX, [0xb7f2ab3c]) = 0
ptrace(PTRACE_PEEKUSER, 7973, 4*ECX, [0]) = 0
ptrace(PTRACE_PEEKUSER, 7973, 4*EDX, [0]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab3c, [0x62696c2f]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab40, [0x736c742f]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab44, [0x3836692f]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab48, [0x6d632f36]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab4c, [0x6c2f766f]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab50, [0x2e636269]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab54, [0x362e6f73]) = 0
ptrace(PTRACE_PEEKDATA, 7973, 0xb7f2ab58, [0x62696c00]) = 0
write(2, "open(\"/lib/tls/i686/cmov/libc.so"..., 45) = 45
ptrace(PTRACE_SYSCALL, 7973, 0x1, SIG_0) = 0
wait4(-1, [{WIFSTOPPED(s) && WSTOPSIG(s) == SIGTRAP}], __WALL, NULL) = 7973
--- SIGCHLD (Child exited) @ 0 (0) ---
ptrace(PTRACE_PEEKUSER, 7973, 4*ORIG_EAX, [0x5]) = 0
ptrace(PTRACE_PEEKUSER, 7973, 4*EAX, [0x3]) = 0
write(2, ") = 3\n", 6)                  = 6
ptrace(PTRACE_SYSCALL, 7973, 0x1, SIG_0) = 0
wait4(-1, [{WIFSTOPPED(s) && WSTOPSIG(s) == SIGTRAP}], __WALL, NULL) = 7973

In highlighted regions:

That wasn't bad, was it ?

ELF format

Binaries on most modern Unices use ELF format (106-page specification). A lot more can be done with ELF
binaries than just executing them. For one we can check which shared library the program uses.

1
2
3
4
5
6
7
8
9

$ ldd /usr/bin/ruby
      linux-gate.so.1 =>  (0xffffe000)
      libruby1.8.so.1.8 => /usr/lib/libruby1.8.so.1.8 (0xb7e3e000)
      libpthread.so.0 => /lib/tls/i686/cmov/libpthread.so.0 (0xb7e27000)
      libdl.so.2 => /lib/tls/i686/cmov/libdl.so.2 (0xb7e23000)
      libcrypt.so.1 => /lib/tls/i686/cmov/libcrypt.so.1 (0xb7df5000)
      libm.so.6 => /lib/tls/i686/cmov/libm.so.6 (0xb7dce000)
      libc.so.6 => /lib/tls/i686/cmov/libc.so.6 (0xb7c8d000)
      /lib/ld-linux.so.2 (0xb7f29000)

/lib/ld-linux.so is dynamic loader, which looks for other libraries in the path. linux-gate is a
pseudolibrary used for communication with kernel. libdl.so is a dynamic library loader and
lets the program load more libraries at runtime. More about that later - what's interesting is
that all this information is contained in the ELF binary in easily accessible format.

Two programs most useful for getting information from binaries are objdump and readelf. To
get default a basic overview simply run readelf -W --all binary or objdump --all-headers binary.

Here's a fragrent of readelf -W --all /usr/bin/perl's output, listing functions which Perl interpretter gets from shared libraries.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Relocation section '.rel.plt' at offset 0x1688c contains 231 entries:
Offset     Info    Type            Sym.Value  Sym. Name
08142114  00001d07 R_386_JUMP_SLOT   00000000   readlink
08142118  00003907 R_386_JUMP_SLOT   00000000   nl_langinfo
0814211c  00003a07 R_386_JUMP_SLOT   00000000   mkdir
08142120  00004507 R_386_JUMP_SLOT   00000000   pthread_getspecific
08142124  00004807 R_386_JUMP_SLOT   00000000   cos
08142128  00005807 R_386_JUMP_SLOT   00000000   fgetc
0814212c  00006007 R_386_JUMP_SLOT   00000000   chown
08142130  00006907 R_386_JUMP_SLOT   00000000   getgrnam_r
08142134  00006e07 R_386_JUMP_SLOT   00000000   __strtod_internal
08142138  00007107 R_386_JUMP_SLOT   00000000   setservent
0814213c  00007a07 R_386_JUMP_SLOT   00000000   rename
08142140  00008b07 R_386_JUMP_SLOT   00000000   ferror
08142144  00009207 R_386_JUMP_SLOT   00000000   sigaction
08142148  00009b07 R_386_JUMP_SLOT   00000000   getgrent_r
0814214c  00009d07 R_386_JUMP_SLOT   00000000   execl
08142150  0000a207 R_386_JUMP_SLOT   00000000   vsprintf
08142154  0000a307 R_386_JUMP_SLOT   00000000   strchr
08142158  0000b607 R_386_JUMP_SLOT   00000000   fdopen

Here's a partial list of functions provided by libjpeg, found by readelf -all /usr/lib/libjpeg.so:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Symbol table '.dynsym' contains 141 entries:
 Num:    Value  Size Type    Bind   Vis      Ndx Name
  12: 00008581   664 FUNC    GLOBAL DEFAULT   10 jpeg_gen_optimal_table
  13: 00002e6b   652 FUNC    GLOBAL DEFAULT   10 jpeg_copy_critical_parame
  14: 00005ba0   537 FUNC    GLOBAL DEFAULT   10 jinit_c_prep_controller
  16: 0000d1be   115 FUNC    GLOBAL DEFAULT   10 jinit_input_controller
  17: 0000c150   159 FUNC    GLOBAL DEFAULT   10 jpeg_read_scanlines
  18: 0001b414    35 FUNC    GLOBAL DEFAULT   10 jpeg_get_small
  19: 000146b4  1343 FUNC    GLOBAL DEFAULT   10 jpeg_idct_float
  20: 000032c1   969 FUNC    GLOBAL DEFAULT   10 jpeg_set_colorspace
  21: 00003280    65 FUNC    GLOBAL DEFAULT   10 jpeg_quality_scaling
  22: 000037fd   760 FUNC    GLOBAL DEFAULT   10 jpeg_simple_progression
  23: 0000b280   655 FUNC    GLOBAL DEFAULT   10 jpeg_fdct_ifast
  24: 00010487  1045 FUNC    GLOBAL DEFAULT   10 jpeg_make_d_derived_tbl
  25: 000160e3    59 FUNC    GLOBAL DEFAULT   10 jpeg_idct_1x1
  26: 0000fd59   309 FUNC    GLOBAL DEFAULT   10 jpeg_huff_decode
  27: 00014bf4  2667 FUNC    GLOBAL DEFAULT   10 jpeg_idct_islow
  28: 0000cd9e   919 FUNC    GLOBAL DEFAULT   10 jinit_master_decompress
  29: 0000cab6   744 FUNC    GLOBAL DEFAULT   10 jpeg_calc_output_dimensio
  30: 00003cbe   108 FUNC    GLOBAL DEFAULT   10 jpeg_set_linear_quality

Using it on C++ libraries is more difficult, as C++ "mangles" identifiers. Because in C++
multiple functions with the same name are allowed, as long as they use arguments of
different types, the compiler "mangles" identifiers to include type information, and it ends
up like this:
_ZN13nsCOMPtr_base18assign_with_AddRefEP11nsISupports. readelf doesn't seem to
provide any demangling, but objdump -C -R /usr/bin/firefox will tell us that the needed
function is nsCOMPtr_base::assign_with_AddRef(nsISupports*).

objdump also includes a disassembler, so you can find implementation of geteuid by looking at output of objdump -d /lib/libc.so.6:

1
2
3
4
5
6
7

0008c750 <geteuid>:
 8c750:       55                      push   %ebp
 8c751:       89 e5                   mov    %esp,%ebp
 8c753:       b8 c9 00 00 00          mov    $0xc9,%eax
 8c758:       cd 80                   int    $0x80
 8c75a:       5d                      pop    %ebp
 8c75b:       c3                      ret

For those that want to know - int 0x80 enters the kernel, and %eax contains syscall number (0xc9 is obviously one for geteuid).
At least that's how it used to work. The "real" libc in /lib/tls/i686/cmov/libc.so.6 uses call *%gs:0x10 instead of int $0x80. (that's
related to linux-gate.so.1 pseudolibrary)

Shared libraries

Let's get back to ldd:

1
2
3
4
5
6
7
8
9

$ ldd /usr/bin/ruby
      linux-gate.so.1 =>  (0xffffe000)
      libruby1.8.so.1.8 => /usr/lib/libruby1.8.so.1.8 (0xb7e3e000)
      libpthread.so.0 => /lib/tls/i686/cmov/libpthread.so.0 (0xb7e27000)
      libdl.so.2 => /lib/tls/i686/cmov/libdl.so.2 (0xb7e23000)
      libcrypt.so.1 => /lib/tls/i686/cmov/libcrypt.so.1 (0xb7df5000)
      libm.so.6 => /lib/tls/i686/cmov/libm.so.6 (0xb7dce000)
      libc.so.6 => /lib/tls/i686/cmov/libc.so.6 (0xb7c8d000)
      /lib/ld-linux.so.2 (0xb7f29000)

Only the dynamic linker is specified by full path. Everything else is resolved at runtime.
Like binaries are looked for in PATH, libraries are searched in directories in LD_LIBRARY_PATH.
So we can trivially make program use our libraries by changing LD_LIBRARY_PATH (like most
techniques presented here, it doesn't work with setuid programs, so don't bother).

Even more effective is LD_PRELOAD, which simply lets us preload another library before the
program runs. It can be any shared library, but usually we want to

Let's fool /bin/date into thinking it's noon (UTC) of July 21, 1995.

The library to do so it truly trivial:

1
2
3
4
5
6
7
8

#include <time.h>
 
int clock_gettime(clockid_t clk_id, struct timespec *tp)
{
  tp->tv_sec  = 806328000;
  tp->tv_nsec = 0;
  return 0;
}

We need to tell compiler we're compiling shared library, not a standalone binary by -fPIC -shared flags:

gcc -Wall -W -g -fPIC -shared magic_clock.c -o magic_clock.so

And:

1
2
3
4

$ date
Thu Mar 22 08:12:36 CET 2007
$ LD_PRELOAD=./magic_clock.so date
Fri Jul 21 14:00:00 CEST 1995

It even remembered to change to summer time.

Usually we want to have the original functionality available. I think it's enough hello worlds for this post,
so let's do something useful, like getting statistics for hash lookups in Ruby.

Hash lookups in Ruby go through st_lookup function. We're interested in distribution of sizes of hash
tables used. This kind of data is useful for profiling - maybe it will provide hints wheather replacing
Ruby hashes by Judy is worthwhile. Or maybe we just want to know. Anyway, here's the debugging tool:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#define _GNU_SOURCE 1
#include <stdio.h>
#include <dlfcn.h>
 
/* Copied from ruby's st.h - it's the easiest way */
typedef unsigned long st_data_t;
struct st_table {
  struct st_hash_type *type;
  int num_bins;
  int num_entries;
  struct st_table_entry **bins;
};
 
int statistics[128];
 
int (*real_st_lookup) (struct st_table *, st_data_t, st_data_t *);
 
int st_lookup(struct st_table *table, st_data_t key, st_data_t *value)
{
  int size = table-&gtnum_entries;
  if(size > 15)
      size = 15 + (size / 16);
  if(size > 127)
      size = 127;
  statistics[size]++;
 
  return real_st_lookup(table, key, value);
}
 
void st_lookup_stats_init() __attribute__ ((constructor));
void st_lookup_stats_init()
{
  int i;
  for(i=0; i<128; i++)
      statistics[i] = 0;
 
  real_st_lookup = dlsym(RTLD_NEXT, "st_lookup");
}
 
void st_lookup_stats_fini() __attribute__ ((destructor));
void st_lookup_stats_fini()
{
  int i, total=0;
 
  for(i=0; i<128; i++)
      total += statistics[i];
 
  printf("Hash lookup statistics by hash size:\n");
  for(i=0; i<16; i++)
      printf("%d-element hashes: %d (%.1f%%)\n", i, statistics[i], 100.0 * statistics[i] / total);
  for(i=16; i<127; i++)
      printf("%d..%d-element hashes: %d (%.1f%%)\n", (i-15)*16, (i-15)*16+15, statistics[i], 100.0 * statistics[i] / total);
  printf("1792+-element hashes: %d (%.1f%%)\n", statistics[127], 100.0 * statistics[127] / total);
}

Compile it with:

gcc -Wall -W -g -fPIC -shared -ldl -lruby1.8 st_lookup_stats.c -o st_lookup_stats.so

and run with:

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
26
27
28
29
30
31
32
33
34
35

$ LD_PRELOAD=./st_lookup_stats.so ruby -e 'p 42'
42
Hash lookup statistics by hash size:
0-element hashes: 164 (2.2%)
1-element hashes: 1059 (14.3%)
2-element hashes: 20 (0.3%)
3-element hashes: 18 (0.2%)
4-element hashes: 17 (0.2%)
5-element hashes: 13 (0.2%)
6-element hashes: 17 (0.2%)
7-element hashes: 12 (0.2%)
8-element hashes: 19 (0.3%)
9-element hashes: 192 (2.6%)
10-element hashes: 10 (0.1%)
11-element hashes: 14 (0.2%)
12-element hashes: 10 (0.1%)
13-element hashes: 12 (0.2%)
14-element hashes: 12 (0.2%)
15-element hashes: 12 (0.2%)
16..31-element hashes: 185 (2.5%)
32..47-element hashes: 158 (2.1%)
48..63-element hashes: 171 (2.3%)
64..79-element hashes: 171 (2.3%)
80..95-element hashes: 126 (1.7%)
96..111-element hashes: 171 (2.3%)
112..127-element hashes: 92 (1.2%)
128..143-element hashes: 48 (0.7%)
144..159-element hashes: 103 (1.4%)
160..175-element hashes: 49 (0.7%)
176..191-element hashes: 95 (1.3%)
192..207-element hashes: 60 (0.8%)
[...]
1760..1775-element hashes: 0 (0.0%)
1776..1791-element hashes: 0 (0.0%)
1792+-element hashes: 0 (0.0%)

OK, now the explanations. int statistics[128]; keeps our statistics and st_lookup_stats_fini() function prints them out.

In ELF it's possible to mark some functions as constructors and destructors.

1
2
3
4
5

void st_lookup_stats_init() __attribute__ ((constructor)); tells gcc to mark st_lookup_stats_init as constructor, so it runs when the library gets loaded.
 
void st_lookup_stats_fini() __attribute__ ((destructor)); tells gcc to mark st_lookup_stats_fini as destructor, so it runs when the program exits.
 
void st_lookup_stats_init() zeroes statistics and find out location of the real st_lookup: real_st_lookup = dlsym(RTLD_NEXT, "st_lookup");

Our fake st_lookup records hash size and calls the genuine st_lookup.

st_data_t and struct st_table are copied from Ruby sources because i was too lazy to do it the "right way", and it doesn't matter anyway.

Debug information

gdb can control program by ptrace, but it still needs to know about its internals somehow. When gcc is run with -g flag,
it saves debug information in DWARF format (117-page specification of DWARF-2).

Unfortunately most programs are distributed without this information, so we need to recompile with -g to get it.
For all ELF files (programs, shared libraries, .o object files etc.) that contain debugging information, we can
get it with readelf -W -w binary. Some of the useful data not available in other ways are types of function
arguments, structure members and their offsets, and file/line information for everything.

Unfortunately parsing either binary DWARF or output of readelf is rather complicated. I haven't tried it out yet, but
there seems to be a program for converting DWARF-2 information to XML. The XML it produces seems rather low-level, but it's XML, so it won't be hard to get useful information out of it.

/proc

/proc filesystem contains a lot of information about running processes. Most of this information can be extracted by ptrace, but /proc interface is far more convenient.

Some files useful for debugging:

That's pretty much all you need to know to start. Happy debugger coding.

一条回应：“How to code debuggers”

  1. Kgdb说道：
    2011年01月10日 8:44 上午

    Kgdb…

    […] something about kgdb[…]…