Paper Appeared at Oakland 2004
Posted 19 May 2004
The paper Formalizing Sensitivity in Static Analysis for
Intrusion Detection appeared at the IEEE Symposium on
Security and Privacy in Oakland, California, on May 11,
2004. Jonathon Giffin, Somesh Jha, and Barton Miller were
co-authors of the paper with Henry Feng and Yong Huang of the
University of Massachusetts, Amherst, and Wenke Lee of the Georgia
Institute of Technology. Henry and Jonathon presented the paper at
the conference.
Model-based intrusion detection systems compare program execution against a model of expected behavior. Prior work has demonstrated a trade-off between the efficiency of operation and the precision of statically-generated models. In particular, accurate pushdown automaton (PDA) models are inefficient to operate due to non-determinism in stack activity. This paper formalizes the PDA models used for intrusion detection and introduces a new concept: the stack-deterministic PDA. Investigating these formalisms drives the discovery of why certain program models do or do not exhibit reasonable performance.
We present two techniques to determinize a PDA. The observational technique, used by our new VPStatic model, extracts information about the stack activity of the program to fully determinize the PDA. The Dyck model uses the instrumentation technique to insert new code into the program that exposes information about call stack changes in the program, producing a stack-deterministic PDA. Our tests of the two models demonstrate that efficiency needs not be sacrificed for model precision.
