Identifying Systemic Threats to Kernel Data - Advanced Operating Systems and Kernel Applications - page 58

Figure 9. Algorithm used by the data structure extractor

the original firmware. Our enhancement ensures
that when the card receives a request from the
page fetcher, the request is directly interpreted
by the firmware and serviced.

The data structure extractor uses the roots
and type definitions to recursively identify data
structures in physical memory using a standard
worklist algorithm as shown in Figure 9. The
extractor first adds the addresses of the roots to a
worklist; it then issues a request to the page fetcher
for memory pages containing the roots. It extracts
the values of the roots from these pages, and uses
their type definitions to identify pointers to more
(previously-unseen) data structures. For example,
if a root is a C struct , the data structure extrac-
tor adds all pointer-valued fields of this struct to
the worklist to locate more data structures in the
kernel's physical memory. This process continues
in a recursive fashion until all the data structures
in the target kernel's memory (reachable from
the roots) have been identified. A complete set of
data structures reachable from the roots is called a
snapshot . The data structure extractor periodically
probes the target and outputs snapshots.
When the data structure extractor finds a
pointer-valued field, it may require assistance in
the form of code annotations to clarify the seman-
tics of the pointer. In particular, the data structure
extractor requires assistance when it encounters

the data Structure extractor

This component reconstructs snapshots of the
target kernel's data structures from raw physi-
cal memory pages. The data structure extractor
processes raw physical memory pages using two
inputs to locate data structures within these pages.
First, it uses a set of root symbols , which denote
kernel data structures whose physical memory
locations are fixed, and from which all data struc-
tures on the target's heap are reachable. In our
implementation, we use the symbols in the System.
map file of the target's kernel as the set of roots.
Second, it uses a set of type definitions of the data
structures in the target's kernel. Type definitions
are used as described below to recursively identify
all reachable data structures. We automatically
extracted 1292 type definitions by analyzing the
source code of the target Linux-2.4.20 kernel us-
ing a CIL module (Necula, 2002).