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.

The paper is available online: [Abstract] [PDF] [PS]

<< Back to index

This page updated October 18, 2005.