Formalizing Sensitivity in Static Analysis for Intrusion Detection
A key function of a host-based intrusion detection system is to
monitor program execution. Models constructed using static analysis
have the highly desirable feature that they do not produce false
alarms; however, they may still miss attacks. Prior work has shown a
trade-off between efficiency and precision. In particular, the more
accurate models based upon pushdown automata (PDA) are very
inefficient to operate due to non-determinism in stack activity. In
this paper, we present techniques for determinizing PDA models. We
first provide a formal analysis framework of PDA models and introduce
the concepts of determinism and stack-determinism. We then present the
VPStatic model, which achieves determinism by extracting information
about stack activity of the program, and the Dyck model, which
achieves stack-determinism by transforming the program and inserting
code to expose program state. Our results show that in run-time
monitoring, our models slow execution of our test programs by 1% to
135%. This shows that reasonable efficiency needs not be sacrificed
for model precision. We also compare the two models and discover that
deterministic PDA are more efficient, although stack-deterministic PDA
require less memory.
Download:[PS,PDF]
Somesh Jha
Last modified: Fri May 14 15:44:39 CDT 2004