Log auditing through model-checking

Abstract

Abstract: Log auditing is a basic intrusion detection mechanism, whereby attacks are detected by uncovering matches of sequences of events against signatures. We argue that this is naturally expressed as a model-checking problem against linear Kripke models. A variant of the classic linear time temporal logic of Manna and Pnueli with first-order variables is first investigated in this framework. But this logic is in dire need of refinement, as far as expressiveness and efficiency are concerned. We therefore propose a second, less standard logic consisting of flat, Wolper-style linear-time formulae. We describe an efficient on-line algorithm, making the approach attractive for complex log auditing tasks. We also present a few optimizations that the use of a formal semantics affords us.