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

Figure 15. Invariants inferred on the formats list; the attack modifies the length of the list

lists are also classified as invariants over collec-
tions). Table 6 reports the number of invariants
inferred by Gibraltar on individual objects as well
as on collections of objects. Table 6 also presents
a classification of invariants by templates; the
length and subset invariants apply only to linked
lists. As this table shows, Gibraltar automatically
infers several thousand invariants on kernel data
structures.
False Positives. To evaluate the false positive
rate of Gibraltar, we designed a test suite consist-
ing of several benign applications, that performed
the following tasks: (a) copying the Linux kernel
source code from one directory to another; (b)
editing a text document (an interactive task); (c)
compiling the Linux kernel; (d) downloading
eight video files from the Internet; and (e) perform
file system read/write and meta data operations
using the IOZone benchmark (Norcott, 2001).
This test suite ran for 42 minutes on the target.
We enforced the invariants inferred using the

workload described in 4.1.
The false positive rate is measured as the ratio
of the number of invariants for which violations are
reported and the total number of invariants inferred
by Gibraltar. Table 6 presents the false positive rate,
further classified by the type of invariant (object/
collection) that was erroneously violated by the
benign workload, and the template that classifies
the invariant. As this table shows, the overall false
positive rate of Gibraltar was 0.65%.

performance

We measured three aspects of Gibraltar's perfor-
mance: (a) training time, i.e. the time taken by
Gibraltar to observe the target and infer invariants;
(b) detection time, i.e. the time taken for an alert
to be raised after the rootkit has been installed;
and (c) performance overhead, i.e. the overhead
on the target system as a result of periodic page
fetches via DMA.
Training time. The training time is calculated
as the cumulative time taken by Gibraltar to
gather kernel data structure snapshots and infer
invariants when executing in training mode.
Overall, the process of gathering 15 snapshots
of the target kernel's memory requires approxi-
mately 25 minutes, followed by 31 minutes to
infer invariants, resulting in a total of 56 minutes
for training.
Training is currently a time-consuming process
because our current prototype invokes Daikon to
infer invariants after collecting all the kernel snap-
shots. Training time can potentially be reduced by
adapting Daikon to use an incremental approach
to infer invariants. In this approach, Daikon would
hypothesize invariants using the first snapshot,

Table 6. Invariants and false positives classified
by the type of invariant and the template used
to mine the invariant. Gibraltar infers a total of
718,940 invariants. Average false positive rate:
0.65%.

Invariants False Positives

Templates Object Collection Object Collection

Member-
ship

643,622 422 0.71% 1.18%

Non-zero 49,058 266 0.17% 2.25%

Bounds 16,696 600 0% 0%

Length NA 4,696 NA 0.66%

Subset NA 3,580 NA 0%