An Edit-Distance Algorithm to Detect Correlated Attacks in Distributed Systems

Authors: Sule Simsek

Abstract:

Intrusion detection systems (IDS)are crucial components of the security mechanisms of today-s computer systems. Existing research on intrusion detection has focused on sequential intrusions. However, intrusions can also be formed by concurrent interactions of multiple processes. Some of the intrusions caused by these interactions cannot be detected using sequential intrusion detection methods. Therefore, there is a need for a mechanism that views the distributed system as a whole. L-BIDS (Lattice-Based Intrusion Detection System) is proposed to address this problem. In the L-BIDS framework, a library of intrusions and distributed traces are represented as lattices. Then these lattices are compared in order to detect intrusions in the distributed traces.

Keywords: Attack graph, distributed, edit-distance, misuse detection.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1085002

References:

[1] G. Birkhoff, Lattice Theory, 3rd ed., ser. American Mathematical Societ Colloquium Publications. NY, USA: American Mathematical Society, 1967, vol. 25.
[2] P. Chandra and A. D. Kshemkalyani, "Distributed algorithm to detect strong conjunctive predicates," Inf. Process. Lett., vol. 87, no. 5, pp. 243-249, 2003.
[3] R. Cooper and K. Marzullo, "Consistent detection of global predicates," in Proceedings of the 1991 ACM Workshop on Parallel and distributed debugging. New York, NY, USA: ACM Press, 1991, pp. 167-174.
[4] D. E. Denning and P. G. Neumann, "Requirements and model for IDES - a real-time intrusion expert system," SRI International, Computer Science Lab, Tech. Rep., August 1985.
[5] J. Ellson, E. Gansner, L. Koutsofios, S. C. North, and G. Woodhull, "Graphviz - open source graph drawing tools," Lecture Notes in Computer Science, vol. 2265, 2002.
[6] C. Fidge, "Timestamps in message-passing systems that preserve the partial ordering," in Proc. 11th Australian Computer Science Conference, 1988.
[7] D. Gao, M. Reiter, and D. Song, "Gray-box extraction of execution graphs for anomaly detection," in Proceedings of the 11th ACM Conf. on Computer and Communications Security. New York, NY, USA: ACM, 2004, pp. 318-329.
[8] V. Garg and C. Chase, "Distributed algorithms for detecting conjunctive predicates." in ICDCS, 1995, pp. 423-430.
[9] L. Guoyuan, H. Hao, and C. Tianjie, "Issue of event sequence in time of distributed intrusion detection system," in Proceedings of the 2007 Network and Parallel Computing Workshops. Dalian, China: IEEE Computer Society, 2007, pp. 215-222.
[10] S. A. Hofmeyr and S. A. Forrest, "Architecture for an artificial immune system," Evol. Comput., vol. 8, no. 4, pp. 443-473, 2000.
[11] I. V. Kotenko and M. Stepashkin, "Attack graph based evaluation of network security," in Comm. and Multimedia Security, ser. Lecture Notes in Computer Science, vol. 4237. Springer, 2006, pp. 216-227.
[12] L. Lamport, "Time, clocks, and the ordering of events in a distributed system," Commun. ACM, vol. 21, no. 7, pp. 558-565, 1978.
[13] T. Lane and C. E. Brodley, "An empirical study of two approaches to sequence learning for anomaly detection," Mach. Learn., vol. 51, no. 1, pp. 73-107, 2003.
[14] W. Lee and S. J. Stolfo, "A framework for constructing features and models for intrusion detection systems," ACM Trans. Inf. Syst. Secur., vol. 3, no. 4, pp. 227-261, 2000.
[15] V. I. Levenshtein, "Binary codes capable of correcting deletions, insertions, and reversals," Soviet Physics - Doklady, vol. 10, no. 8, pp. 707-710, February 1966.
[16] F. Mattern, "Virtual time and global states of distributed systems," in Proceedings of the International Workshop on Parallel and Distributed Algorithms. Elsevier Science Publishers B.V., 1989.
[17] N. Mittal and V. Garg, "Techniques and Applications of Computation Slicing," Distributed Computing, vol. 17, no. 3, pp. 251-277, 2005.
[18] S. Shivashankaraiah, "Latgenu - lattice generator for unix," Computer Science Department, Missouri University of Science and Technology, Tech. Rep., 2003.
[19] M. Tupper and A. N. Zincir-Heywood, "Vea-bility security metric: A network security analysis tool," in ARES, 2008, pp. 950-957.
[20] S. M. Varghese and K. Jacob, "Anomaly detection using system call sequence sets," Journal of Software, vol. 2, no. 6, pp. 14-21, 2007.
[21] S. Vongpradhip and W. Plaimart, "Survival architecture for distributed intrusion detection system (dids) using mobile agent," in NCA, 2007, pp. 332-338.
[22] L. Williams, R. Lippmann, and K. Ingols, "An interactive attack graph cascade and reachability display," in Proceedings of the Workshop on Visualization for Computer Security, 2007, pp. 97-104.
[23] J. Wu, C. Wang, J. Wang, and S. fu Chen, "Dynamic hierarchical distributed intrusion detection system based on multi-agent system," in WI-IATW -06: Proceedings of the 2006 International Conference on Web Intelligence and Intelligent Agent Technology. Washington, DC, USA: IEEE Computer Society, 2006, pp. 89-93.
[24] Y.-F. Zhang, Z.-Y. Xiong, and X.-Q. Wang, "Distributed intrusion detection based on clustering," in Proceedings of 2005 International Conference on Machine Learning and Cybernetics, vol. 4, 2005, pp. 2379-2383.