This site presents a code flow visualization and execution tracking tool called StackTrack. An example code flow graph for an execution of the kexec_file_load linux system call is shown below.
When browsing large codebases, it is often unclear how a certain function can be reached. StackTrack tries to solve this problem for the linux kernel by generating call graphs. The graphs are represented as expandable trees. Examples can be found here
For the sake of brevity this page is lacking a lot of implementation details. Should you need more information regarding some of the details, please feel free to drop me an email.
A function call cross reference database table was built by parsing the output of the egypt tool. This mysql database dump can be downloaded from the github repository. It consists of a single table with two columns: caller and callee.
The Graph.py python script creates a "Graph" datastructure based on this table. This graph consists of nodes and edges. The graph information can be exported in json format with the dump_node(s) method. The script can be invoked from the cli to retrieve a callgraph from the xrefs database in json format. The command line options of this script are
usage: Graph.py [-h] [-v VERBOSE] [-r] [-e] [-a] [-d DIRECTORY]
[nodes [nodes ...]]
positional arguments:
nodes
optional arguments:
-h, --help show this help message and exit
-v VERBOSE, --verbose VERBOSE
Logging level (10: debug, 20 : info, etc )
-r, --callers Export caller tree
-e, --callees Export caller tree
-a, --allnodes Dump all nodes
-d DIRECTORY, --directory DIRECTORY
Output directory
The "nodes" cli arguments are function names.
The script is able to lookup codepaths in both caller and callee directions.
The following command for example generates a graph of all callees for the sys_kexec_file_load system call:
$ python Graph.py -e sys_kexec_file_load
INFO:root:dumping callees of Node sys_kexec_file_load to /tmp/sys_kexec_file_load_callees.json
The javascript renders this graph using this json file for the static call graph and this filefor the dynamic call graph (execution trace) coloring .
The json graph output is rendered using the d3js javascript visualization library.
The source code for this project is available in the github repository . To test the execution tracking you will need a linux kernel with debug symbols and a gdb session. gdb must by The graph generating code is written in python and uses a mysql server. Following items are explained in the Readme file in the src directory from the repository:
To track execution we place breakpoints on the functions that are in the codepath of our interest. Every time a breakpoint is hit, we query the cross-reference database to retrieve all functions that can be called next (the callees) and we place breakpoints on these functions as well. This process allows us to track the program flow.
The tracking is implemented in the breakpoint.py python code which is called from within gdb. This trace flow is also saved in a Graph datastructure.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ubuntu pygdb # gdb -q vmlinux
Reading symbols from vmlinux...done.
(gdb) set pagination off
(gdb) target remote u:8864
Remote debugging using u:8864
native_safe_halt () at ./arch/x86/include/asm/irqflags.h:50
self.func_name = func_name
50 }
(gdb) python
>import breakpoint, importlib
>importlib.reload(breakpoint)
>breakpoint.KxrBreakpoint('sys_chdir')
>end
loaded
DEBUG:root:dumping Node hrtimer_cancel to /tmp/hrtimer_cancel.json
DEBUG:root:Ignoring Node hrtimer_cancel
DEBUG:root:dumping Node getname_flags to /tmp/getname_flags.json
DEBUG:root:Ignoring Node getname_flags
DEBUG:root:dumping Node __wake_up to /tmp/__wake_up.json
DEBUG:root:Ignoring Node __wake_up
...
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
class STBreakpoint(gdb.Breakpoint):
>
loaded
Breakpoint 1 at 0xffffffff811f7dc0: file fs/open.c, line 422.
(gdb) c
Continuing.
Breakpoint 2 at 0xffffffff817c0990: file arch/x86/kernel/mcount_64.S, line 151.
Breakpoint 3 at 0xffffffff81209420: file fs/namei.c, line 2327.
Breakpoint 4 at 0xffffffff81203fd0: file fs/namei.c, line 459.
Breakpoint 5 at 0xffffffff81203560: path_put. (36 locations)
Breakpoint 6 at 0xffffffff8122d310: file fs/fs_struct.c, line 33.
Breakpoint 7 at 0xffffffff8107a090: file kernel/panic.c, line 493.
DEBUG:root:Creating Node sys_chdir 0ncel.json
DEBUG:root:Ignoring Node hrtimer_cancel
DEBUG:root:dumping Node getname_flags to /tmp/getname_flags.json
DEBUG:root:Ignoring Node getname_flags
DEBUG:root:dumping Node __wake_up to /tmp/__wake_up.json
DEBUG:root:Ignoring Node __wake_up
# node = self.node = self.graph.add_node(func_name)
# if not node in self.graph.nodes: self.graph.load_node(self.node)
self.parent = parent
STBreakpoint.bplist.add(func_name)
#print('ini %s'%str(func_name))
super(STBreakpoint, self).__init__(
func_name, gdb.BP_BREAKPOINT, internal=False
)
def _stop(self):
comm = get_current()['comm'].string()
if not comm.startswith('trinity'):
return
print(self.func_name)We
def stop(self):
comm = get_current()['comm'].string()
if not comm.startswith('trinity'):
DEBUG:root:Creating Node user_path_at_empty 1
Breakpoint 8 at 0xffffffff81208e60: file fs/namei.c, line 126.
Breakpoint 9 at 0xffffffff81209200: file fs/namei.c, line 2151.
DEBUG:root:Creating Node getname_flags 2
Breakpoint 10 at 0xffffffff811dad30: file mm/slub.c, line 2519.
Breakpoint 11 at 0xffffffff813ee620: file lib/strncpy_from_user.c, line 100.
Breakpoint 12 at 0xffffffff8111e430: file kernel/auditsc.c, line 1701.
Breakpoint 13 at 0xffffffff8111e490: file kernel/auditsc.c, line 1724.
Breakpoint 14 at 0xffffffff811da560: file mm/slub.c, line 2744.
Breakpoint 15 at 0xffffffff811da8e0: file mm/slub.c, line 2531.
...
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
(gdb) python
self.func_name = func_name
>breakpoint.KxrBreakpoint.graph.dump_nodes('/tmp')
>end
DEBUG:root:dumping Node fsnotify to /tmp/fsnotify.json
DEBUG:root:Ignoring Node fsnotify
DEBUG:root:dumping Node hrtimer_cancel to /tmp/hrtimer_cancel.json
DEBUG:root:Ignoring Node hrtimer_cancel
DEBUG:root:dumping Node getname_flags to /tmp/getname_flags.json
DEBUG:root:Ignoring Node getname_flags
DEBUG:root:dumping Node __wake_up to /tmp/__wake_up.json
DEBUG:root:Ignoring Node __wake_up
# node = self.node = self.graph.add_node(func_name)
# if not node in self.graph.nodes: self.graph.load_node(self.node)
self.parent = parent
STBreakpoint.bplist.add(func_name)
#print('ini %s'%str(func_name))
super(STBreakpoint, self).__init__(
func_name, gdb.BP_BREAKPOINT, internal=False
)
def _stop(self):
comm = get_current()['comm'].string()
if not comm.startswith('trinity'):
return
print(self.func_name)We
def stop(self):
comm = get_current()['comm'].string()
if not comm.startswith('trinity'):
return
</div>
...
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
class STBreakpoint(gdb.Breakpoint):
>
bplist = set()
todelete = []
edges = []
graph = Graph()
def __init__(self, func_name, parent=None):
get_bt_start()
self.func_name = func_name
# node = self.node = self.graph.add_node(func_name)
# if not node in self.graph.nodes: self.graph.load_node(self.node)
self.parent = parent
STBreakpoint.bplist.add(func_name)
#print('ini %s'%str(func_name))
super(STBreakpoint, self).__init__(
func_name, gdb.BP_BREAKPOINT, internal=False
)
def _stop(self):
comm = get_current()['comm'].string()
if not comm.startswith('trinity'):
return
print(self.func_name)We
def stop(self):
comm = get_current()['comm'].string()
if not comm.startswith('trinity'):
return
</div>
if self.parent:
STBreakpoint.graph.add_edge(self.parent,self.func_name)
else:
get_bt_start()
for bp in STBreakpoint.todelete:
try:
if bp.func_name != self.func_name:
bp.delete()
except:
pass
for callee in get_callees(self.func_name):
if callee not in STBreakpoint.bplist:
STBreakpoint(callee,self.func_name)
STBreakpoint.todelete += [self]
Following syscall execution traces have been generated with the trinity syscall fuzzer: