![](https://csdnimg.cn/release/download_crawler_static/9132331/bg3.jpg)
from memory traversal). In addition to checking
if some code section is modified, MAS detects two
kinds of violations: (1) a function pointer points to
a memory region outside of a list of known good
modules; (2) a data object is hidden from a system
program. The list of identified integrity violations
is the final output of MAS. Such information can be
used to detect if a system is infected by a rootkit or
analyze a rootkit’s behavior.
Next we describe these three steps in detail.
3 Static Analysis
In this section, we present our demand-driven pointer
analysis algorithm. After that, we describe how we use
this algorithm to identify candidate types for generic
pointers and data types associated with pool tags.
3.1 Demand-Driven Pointer Analysis
We use demand-driven pointer analysis because we do
not need the alias information for all the variables in a
program, which traditional pointer analyses compute. In-
stead, we only compute the alias sets of generic pointers,
a small portion of all the variables in a program.
Our demand-driven pointer analysis follows largely
the approach of Zheng and Rugina [27]. Since our goal
is to precisely identify candidate types for generic point-
ers, we extend Zheng and Rugina’s pointer analysis to
be field-sensitive, context-sensitive and partially flow-
sensitive. We achieve partial flow-sensitivity by convert-
ing a program to the Static Single Assignment (SSA)
form conservatively. We enforce context-sensitivity in
a way similar to [23]. We handle indirect calls in our
analysis as well.
Next we will summarize the approach of [27] and pro-
vide a detailed description of our extension to field sen-
sitivity.
3.1.1 Program Expression Graph
The algorithm of [27] operates on a Program Expression
Graph (PEG), a graph representation of all expressions
and assignments in a C-like program. In this paper, we
represent an expression as a C variable with ∗ (for the
dereference operation), & (for the take-address opera-
tion) and → (for the field operation). In a PEG, the nodes
are program expressions, and the edges are of two kinds:
Assignment Edge (A): For each assignment e
1
= e
2
,
there is an A-edge from e
2
to e
1
.
Dereference Edge (D): For each dereference ∗e, there
is a D-edge from e to ∗e; for each address &e, there
is a D-edge from &e to e.
!"
!"
#"$"%&'"
(#"$"%)'"
(&"$"*'"
!")"$"*"
%&" &" (&"
#" (#" )"%)"
*"
+"
+"
+"
!"
!"
!"
!"
!"
!"
!"
+"
+"
+"
+"
+"
+"
!"
!"
!"
Figure 1: Sample program and its PEG
For each A and D edge, there is also a corresponding
inverse edge in the opposite direction, denoted by A and
D. The edges can also be treated as relations between the
corresponding nodes; so relations A and D are the inverse
relations of A and D. Figure 1 shows a sample program
and its PEG.
3.1.2 CFL-Reachability
In addition to the A and D relations (edges), we further
define two relations between expressions (nodes):
Value Alias (V ): If a and b may evaluate to the same
value, we say they are value aliases, represented as
aV b.
Memory Alias (M): If the addresses of a and b may de-
note to the same location, we say they are memory
aliases, represented as aMb.
Given an interesting expression p, our pointer analy-
sis searches for the set of expressions q such that pV q.
We call this set thevalue alias set of p. Similar to [27],
we formulate the computation of the V relation as a
Context-Free Language (CFL) reachability problem [21]
over the program expression graph. Specifically, a rela-
tion R over the nodes of a PEG can be formulated as a
CFL-reachability problem by constructing a grammar G
such that a node pair (a, b) has the relation R if and only
if there is a path from a to b such that the sequence of
labels along the path belongs to the language L(G). The
context-free grammar G
V
for value and memory alias re-
lations is:
Value Aliases: V ::= M | MAV | VAM
Memory Aliases: M ::= ε | DV D
The grammar G
V
has non-terminals V and M, and ter-
minals A, A, D, and D. Readers can verify that the sample
PEG in Figure 1 contains a path from b to c with label se-
quence DADADDA that can be produced by the V non-
terminal in G
V
. So the grammar successfully deducts
that b and c are value aliases. The intuition behind each
production rule is:
M ::= ε a is a memory alias of itself.
3