An Edit-Distance Algorithm to Detect Correlated Attacks in Distributed Systems
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:64413", author = "Sule Simsek", title = "An Edit-Distance Algorithm to Detect Correlated Attacks in Distributed Systems", 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.", volume = "2", number = "2", pages = "602-7", }
