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

rootKit detection Via
automated inVariant
inference

a separate virtual machine (Garfinkel, 2003). In
our architecture, Gibraltar executes on a separate
machine (the observer ) and monitors the execu-
tion of the target machine (the target ) as shown
in Figure 7. Both the observer and the target are
interconnected via a secure back-end network
using the Myrinet PCI intelligent network cards
(Myricom, n.d.) 1. The back end network allows
Gibraltar to remotely access the target kernel's
physical memory. Gibraltar is built to infer data
structure invariants when supplied with raw
kernel memory as input. Since coprocessor and
VMM based external monitors use a similar
asynchronous monitoring technique to read the
target memory, Gibraltar can be easily adapted
to work with these infrastructures.
Figure 8 presents the architecture of Gibraltar.
It operates in two modes, namely, a training mode
and an enforcement mode. In the training mode,
Gibraltar infers invariants on data structures of the
target's kernel. Training happens in a controlled
environment on an uncompromised target (e.g.
a fresh installation of the kernel on the target
machine). In the enforcement mode, Gibraltar
ensures that the data structures on the target's
kernel satisfy the invariants inferred during the
training mode.
As shown in Figure 8, Gibraltar consists of four
key components (shown in the boxes with solid
lines). The page fetcher responds to requests by
the data structure extractor to fetch kernel
memory pages from the target. The data
structure extractor, in turn, extracts values of data
structures on the target's kernel by analyzing raw
physical memory pages. The data structure extrac-
tor also accepts as input the data type definitions
of the kernel running on the target machine and
a set of root symbols that it uses to traverse the
target's kernel memory pages. Both these inputs
are obtained via an off line analysis of the source
code of the kernel version executing on the target
machine. The output of the data structure extractor
is the set of kernel data structures on the target. The
invariant generator processes these data structures

To automatically detect stealth attacks on the
kernel such as the ones discussed in the last sec-
tion, we propose a novel approach based upon
automatic inference of data structure invariants .
This approach is based on the hypothesis that
kernel data structures exhibit invariants during its
normal operation. A kernel rootkit that alters the
behavior of the kernel algorithms violates some
of these invariants and therefore can be detected.
This approach can uniformly detect rootkits that
modify both control and non-control data. To
evaluate this hypothesis, we built a prototype
Gibraltar, whose design and implementation, we
discuss below.
The key idea is to monitor the values of
kernel data structures during a training phase,
and hypothesize invariants that are satisfied by
these data structures. These invariants serve as
specifications of data structure integrity. For ex-
ample, an invariant could state that the values of
elements of the system call table are a constant
(an example of a control data invariant). Similarly,
an invariant could state that all the elements of
the running-tasks linked list (used by the kernel
for process scheduling) are also elements of the
all-tasks linked list that is used by the kernel for
process accounting (an example of a non-control
data invariant) (Butler, 2005),
(Petroni, 2006). These invariants are then
checked during an enforcement phase; violation
of an invariant indicates the presence of a rootkit.
Because invariants are inferred automatically and
uniformly across both control and non-control
data structures , the approach presented in this
section, overcomes the shortcomings of prior
rootkit detection techniques.
Because Gibraltar aims to detect rootkits,
it must execute on an entity that is outside the
control of the monitored kernel, such as a copro-
cessor (Petroni, 2004), (Zhang, 2002) or inside