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, the authors present techniques for determinizing PDA models. They first provide a formal analysis framework of PDA models and introduce the concepts of determinism and stack-determinism.