A Decision Support System for Placement of Intrusion Detection and Prevention Devices in Large-Scale Networks

Abstract

This article describes an innovative Decision Support System (DSS) for Placement of Intrusion Detection and Prevention Systems (PIDPS) in large-scale communication networks. PIDPS is intended to support network security personnel in optimizing the placement and configuration of malware filtering and monitoring devices within Network Service Providers’ (NSP) infrastructure, and enterprise communication networks. PIDPS meshes innovative and state-of-the-art mechanisms borrowed from the domains of graph theory, epidemic modeling, and network simulation. Scalable network exploitation models enable to define the communication patterns induced by network users (thereby establishing a virtual overlay network), and parallel attack models enable a PIDPS user to define various interdependent network attacks such as: Internet worms, Trojans horses, Denial of Service (DoS) attacks, and others. PIDPS incorporates a set of deployment strategies (employing graph-theoretic centrality measures) in order to facilitate intelligent placement of filtering and monitoring devices; as well as a dedicated network simulator in order to evaluate the various deployments. Experiments with PIDPS indicate that incorporating knowledge on the overlay network (network exploitation patterns) into the placement and configuration of malware filtering and monitoring devices substantially improves the effectiveness of intrusion detection and prevention systems in NSP and enterprise networks.

References

1. Anderson, R. M. and May, R. M. 1992. Infectious Diseases of Humans: Dynamics and Control. Oxford University Press.
2. AOL/NCSA. 2005. Online safety study. http://www.staysafeonline.org/pdf/safety_study_2005.pdf.
3. Barabasi, A.-L. and Albert, R. 1999. Emergence of scaling in random networks. Science, 286, 509--512.
4. Borgatti, S. P. and Everett, M. G. 2006. A graph-theoretic perspective on centrality. Social Netw. 28, 4, 466--484.
5. Brandes, U. 2008. On variants of shortest-path betweenness centrality and their generic computation. Social Netw. 30, 2, 136--145.
6. Bye, R., Schmidt, S., Luther, K., and Albayrak, S. 2008. Application-level simulation for network security. In Proceedings of the 1st International Conference on Simulation Tools and Techniques for Communications, Networks and Systems. 33.
7. Cai, M., Hwang, K., Kwok, Y.-K., Song, S., and Chen, Y. 2005. Collaborative internet worm containment. IEEE Secur. Priv. 1540--7993, 05, 24--33.
8. Chakrabarti, D., Wang, Y., Wang, C., Leskovec, J., and Faloutsos, C. 2008. Epidemic thresholds in real networks. ACM Trans. Inform. Syst. Secur. 10, 4, Art. 13.
9. Chen, S. and Tang, Y. 2004. Slowing down internet worms. In Proceedings of the 24th International Conference on Distributed Computing and Systems. 312--319, Tokyo, Japan.
10. Coelho, F., Cruz, O., and Codec, O-.C. 2008. Epigrass: A tool to study disease spread in complex networks. Source Code Biol. Med. 3, 1, 3.
11. Costa, M., Crowcroft, J., Castro, M., Roowstron, A., Zhou, L., Zhang, L., and Baham, P. 2005. Vigilante: End-to-end containment of internet worms. In Proceedings of the Symposium on Operating System Principles. 133--147.
12. Dolev, S, Elovici, Y., and Puzis, R. 2010. Routing betweenness centrality. J. ACM 57, 4, 25, 1--27.
13. DTLabs@BGU, eDare(II&III) project. 2006. Beta release of PIDPS can be obtained from Deutsche Telekom Laboratories at Ben-Gurion University. http://tlabs.bgu.ac.il/edare23.
14. Ediger, B. 2005. Simulating network worms. http://www.users.qwest.net/eballen1/nws/ (accessed 06/08).
15. Elovici, Y., Shabtai, A., Moskovitch, R., Tahan, G., and Glezer, C. 2007. Applying machine learning techniques for detection of malicious code in network traffic. In Proceedings of the 30th Annual German Conference on Artificial Intelligence. Lecture Notes in Computer Science, vol. 4667. Springer, 44--50.
16. Everett, M. G. and Borgatti, S. P. 1999. The centrality of groups and classes. Math. Sociol. 23, 3, 181--201.
17. Freeman, L. C. 1977. A set of measures of centrality based on betweenness. Sociometry 40, 1, 35--41.
18. Freeman, L. C. 1979. Centrality in social networks conceptual clarification. Social Netwo. 1, 215--239.
19. Gorman, S. P., Schintler, L., Kulkarni, R., and Stough, R. 2004. The revenge of distance: Vulnerability analysis of critical information infrastructure. J. Conting. Crisis Manage. 12, 48--63.
20. Harris Interactive. 2006. Survey reveals the majority of U.S. adult computer users are unprotected from malware. www.harrisinteractive.com/news/newsletters/clientnews/2006_ESET.pdf.
21. Kephart, J. O. and White, S. R. 1991. Directed-graph epidemiological models of computer viruses. In Proceedings of the IEEE Computer Society Symposium on Research in Security and Privacy. IEEE, 343--359.
22. Kotenko, I. and Ulanov, A. 2005. The software environment for multi-agent simulation of defense mechanisms against DDOS attacks. In Proceedings of the 2005 International Conference on Computational Intelligence for Modeling Control and Automation (CIMCA’05). 283--289.
23. Kruegel, C., Valeur, F., Vigna, G., and Kemmerer. R. 2002. Stateful intrusion detection for high-speed networks. In Proceedings of the IEEE Symposium on Security and Privacy. IEEE, 285--294.
24. Liljenstam, M., Nicol, D. M., Berk, V. H., and Gray, R. S. 2003. Simulating realistic network worm traffic for worm warning system design and testing. In Proceedings of the ACM Workshop on Rapid Malcode (WORM). New York, NY.
25. Mcafee-NCSA. 2007. Online safety study. http://staysafeonline.org/pdf/McAfee_NCSA_analysis.pdf.
26. Medina, A., Taft, N., Salamatian, K., Bhattacharyya, S., and Diot, C. 2002. Traffic matrix estimation: Existing techniques and new directions. SIGCOMM Comput. Comm. Rev. 32, 4, 161--174.
27. Moore, D., Shannon, C., and Brown, J. 2002. Code-red: A case study on the spread and victims of an internet worm. In Proceedings of the 2nd Internet Measurement Workshop on Traffic Analysis. 273--284.
28. Moore, D., Shannon, C., Voelker, G., and Savage, S. 2003. Internet quarantine: Requirements for containing self-propagating code. In Proceedings of the 22th IEEE Conference on Computer Communications. IEEE.
29. NCSA. 2008. Overview of NCSA consumer research study.
30. Newman, M. E. J. and Girvan, M. 2004. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113.
31. Papagiannaki, K., Taft, N., and Lakhina, A. 2004. A distributed approach to measure ip traffic matrices. In Proceedings of the 4th ACM SIGCOMM Conference on Internet Measurement (IMC’04). 161--174.
32. Park, K. 2004. Scalable protection against DDoS and worm attacks. DARPA ATO FTN project AFRL contract F30602-01-2-0530, Purdue University, West Lafayette.
33. Pastor-Satorras, R. and Vespignani, A. 2001. Epidemic spreading in scale-free networks. Phys. Rev. Lett. 86, 14, 3200--3203.
34. Pastor-Satorras, R. and Vespignani, A. 2002. Immunization of complex networks. Phys. Rev. E 65, 036104.
35. Puzis, R., Elovici, Y., and Dolev, S. 2007a. Fast algorithm for successive computation of group betweenness centrality. Phys. Rev. E 76, 5, 056709.
36. Puzis, R., Elovici, Y., and Dolev, S. 2007b. Finding the most prominent group in complex networks. AI Comm. 20, 4, 287--296.
37. Puzis, R., Klippel, M. D., Elovici, Y., and Dolev, S. 2007c. Optimization of NIDS placement for protection of intercommunicating critical infrastructures. In Proceedings of EuroISI. 191--203.
38. Riley, G. F., Sharif, M. I., and Lee, W. 2004. Simulating internet worms. In Proceedings of the IEEE 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems(MASCOTS). IEEE Computer Society, 268--274.
39. Schwartz, Y., Shavitt, Y., and Weinsberg, U. 2010. On the diversity, stability and symmetry of end-to-end internet routes. In Global Internet.
40. Shabtai, A., Menahem, E., and Elovici, Y. 2010. F-sign: Automatic, function-based signature generation for malware. IEEE Trans. Syst. Man Cybernet. Part C: Appl. Rev. 99, 1--15
41. Stafford, S., Li, J., Ehrenkranz, T., and Knickerbocker, P. 2006. GLOWS: A high fidelity worm simulator. Tech. rep. CIS-TR-2006-11, University of Oregon.
42. Vojvonic, M. and Ganesh, A. 2008. On the race of worms, alerts an patches. IEEE/ACM Trans. Netw. 16, 5, 1066--1079.
43. Watts, D. J. and Strogatz, S. H. 1998. Collective dynamics of ‘small-world’ networks. Nature 393, 440--442.
44. Weaver, N., Staniford, S., and Paxson V. 2004. Very fast containment of scanning worms. In Proceedings of the 13th USENIX Security Symposium. 29--44.
45. Wei, S., Mirkovic, J., and Swany, M. 2005. Distributed worm simulation with a realistic internet model. In Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation (PADS’05). IEEE Computer Society, Press, 71--79.
46. Yan, G., Eidenbenz, S., Thulasidasan, S., Datta, P., and Ramaswamy, V. 2010. Criticality analysis of internet infrastructure. Comput. Netw. 54, 7, 1169--1182.
47. Zanette, D. H. and Kuperman, M. 2002. Effects of immunization in small-world epidemics. Phys. A 309, 445--452.
48. Zegura, E. W., Calvert, K. L., and Bhattacharjee, S. 1996. How to model an internetwork. In Proceedings of IEEE INFOCOM. 594--602.
49. Zhang, Y., Roughan, M., Duffield, N., and Greenberg, A. 2003. Fast accurate computation of large-scale IP traffic matrices from link loads. SIGMETRICS Perform. Eval. Rev. 31, 1, 206--217.
50. Zhou, T., Liu, J.-G., Bai, W.-J., Chen, G., and Wang, B.-H. 2006. Behaviors of susceptible-infected epidemics on scale-free networks with identical infectivity. Phys. Rev. E 74, 056109.
51. Zou, C. C., Gong, W., and Towsley. D. 2002. Code red worm propagation modeling and analysis. In Proceedings of the 9th ACM Conference on Computer and Communications Security (CCS’02). ACM, New York, 138--147.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Evaluation

    • Metrics

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

      • Network flows

  • Probability and statistics

    • Statistical paradigms

      • Exploratory data analysis

    • Stochastic processes

• Security and privacy

  • Intrusion/anomaly detection and malware mitigation

• Social and professional topics

  • Computing / technology policy

    • Computer crime

  • Professional topics

    • Management of computing and information systems

      • Implementation management

        • Computing equipment management

        • Pricing and resource allocation

      • Information system economics

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows