Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Clocksin, W., Mellish, C.: Programming in Prolog. Springer, Heidelberg (1981)
Manna, Z., Pnueli, A.: The Temporal Logic of Reactive and Concurrent Systems. Springer, Heidelberg (1991)
McDonald, J., A.L. Digital Ltd., The Bunker: OpenSSL SSLv2 malformed client key remote buffer overflow vulnerability (July 2002), http://www.securityfocus.com/bid/5363
Morin, B., Debar, H.: Correlation of intrusion symptoms: An application of chronicles. In: Vigna, G., Krügel, C., Jonsson, E. (eds.) RAID 2003. LNCS, vol. 2820, pp. 94–112. Springer, Heidelberg (2003)
Morin, B., Mé, L., Debar, H., Ducassé, M.: M2D2: A formal data model for IDS alert correlation. In: Wespi, A., Vigna, G., Deri, L. (eds.) RAID 2002. LNCS, vol. 2516. Springer, Heidelberg (2002)
Olivain, J.: ORCHIDS—real-time event analysis and temporal correlation for intrusion detection in information systems (2004), http://www.lsv.ens-cachan.fr/orchids/
Olivain, J., Goubault-Larrecq, J.: The Orchids intrusion detection tool. In: Etessami, K., Rajamani, S.K. (eds.) CAV 2005. LNCS, vol. 3576, pp. 286–290. Springer, Heidelberg (2005)
Olivain, J., Goubault-Larrecq, J.: Detecting subverted cryptographic protocols by entropy checking. Research Report LSV-06-13, Laboratoire Spécification et Vérification, ENS Cachan, France, 19. pages (June 2006)
Pouzol, J.-P., Ducassé, M.: Formal specification of intrusion signatures and detection rules. In: Cervesato, I. (ed.) 15th IEEE Computer Security Foundations Workshop (CSFW 2002), pp. 64–76. IEEE Comp.Soc.Press, Los Alamitos (2002)
Purczyński, W.: Linux ptrace/execve race condition vulnerability. BugTraq Id 2529 (March 2001), http://www.securityfocus.com/bid/2529
Purczyński, W.: Linux kernel privileged process hijacking vulnerability. BugTraq Id 7112 (March 2003), http://www.securityfocus.com/bid/7112
Purczyński, W., qaaz.: Linux kernel prior to 2.6.24.2 ‘vmsplice_to_pipe()’ local privilege escalation vulnerability (February 2008), http://www.securityfocus.com/bid/27801
Roger, M., Goubault-Larrecq, J.: Log auditing through model checking. In: 14th IEEE Computer Security Foundations Workshop (CSFW 2001), pp. 220–236. IEEE Computer Society Press, Los Alamitos (2001)
Starzetz, P.: Linux kernel 2.4.22 do_brk() privilege escalation vulnerability, K-Otik ID 0446, CVE CAN-2003-0961 (December 2003), http://www.k-otik.net/bugtraq/12.02.kernel.2422.php
Totel, E., Vivinis, B., Mé, L.: A language driven IDS for event and alert correlation. In: Deswarte, Y., Cuppens, F., Jajodia, S., Wang, L. (eds.) Security and Protection in Information Processing Systems, IFIP 18th World Computer Congress, TC11 19th International Information Security Conference, pp. 209–224. Kluwer, Dordrecht (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goubault-Larrecq, J., Olivain, J. (2008). A Smell of Orchids . In: Leucker, M. (eds) Runtime Verification. RV 2008. Lecture Notes in Computer Science, vol 5289. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-89247-2_1
Download citation
DOI: https://doi.org/10.1007/978-3-540-89247-2_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-89246-5
Online ISBN: 978-3-540-89247-2
eBook Packages: Computer ScienceComputer Science (R0)