2008 | OriginalPaper | Buchkapitel
A Smell of Orchids
verfasst von : Jean Goubault-Larrecq, Julien Olivain
Erschienen in: Runtime Verification
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Orchids
is an intrusion detection tool based on techniques for fast, on-line model-checking.
Orchids
detects complex, correlated strands of events with very low overhead in practice, although its detection algorithm has worst-case exponential time complexity.
The purpose of this paper is twofold. First, we explain the salient features of the basic model-checking algorithm in an intuitive way, as a form of dynamically-spawned monitors. One distinctive feature of the
Orchids
algorithm is that fresh monitors need to be spawned at a possibly alarming rate.
The second goal of this paper is therefore to explain how we tame the complexity of the procedure, using abstract interpretation techniques to safely kill useless monitors. This includes monitors which will provably detect nothing, but also monitors that are subsumed by others, in the sense that they will definitely fail the so-called shortest run criterion. We take the opportunity to show how the
Orchids
algorithm maintains its monitors sorted in such a way that the subsumption operation is effected with no overhead, and we correct a small, but definitely annoying bug in its core algorithm, as it was published in 2001.