Shariful Haque; Travis Atkison

An Evolutionary Approach of Attack Graph to Attack Tree Conversion

Full Text (PDF, 734KB), PP.1-16

Views: 0 Downloads: 0

Author(s)

Shariful Haque ^1,* Travis Atkison ¹

1. Department of Computer Science, University of Alabama, Tuscaloosa, AL 35478, USA

* Corresponding author.

DOI: https://doi.org/10.5815/ijcnis.2017.11.01

Received: 4 Jul. 2017 / Revised: 23 Jul. 2017 / Accepted: 7 Aug. 2017 / Published: 8 Nov. 2017

Index Terms

Attack graph, Attack tree, Intrusion detection, Attack modeling, Survey

Abstract

The advancement of modern day computing has led to an increase of threats and intrusions. As a result, advanced security measurements and threat analysis models are necessary to detect these threats and identify protective measures needed to secure a system. Attack graphs and attack trees are the most popular form of attack modeling today. While both of these approaches represent the possible attack steps followed by an attacker, attack trees are architecturally more rigorous than attack graphs and provide more insights regarding attack scenarios. The goal of this research is to identify the possible direction to construct attack trees from attack graphs analyzing a large volume of data, alerts or logs generated through different intrusion detection systems or network configurations. This literature summarizes the different approaches through an extensive survey of the relevant papers and identifies the current challenges, requirements and limitations of an efficient attack modeling approach with attack graphs and attack trees. A discussion of the current state of the art is presented in the later part of the paper, followed by the future direction of research.

Cite This Paper

Md. Shariful Haque, Travis Atkison, "An Evolutionary Approach of Attack Graph to Attack Tree Conversion", International Journal of Computer Network and Information Security(IJCNIS), Vol.9, No.11, pp.1-16, 2017. DOI:10.5815/ijcnis.2017.11.01

Reference

[1]R. W. Shirey, “Internet security glossary, version 2,” 2007.
[2]S. Cheung, U. Lindqvist, and M. W. Fong, “Modeling multistep cyber attacks for scenario recognition,” in DARPA information survivability conference and exposition, 2003. Proceedings, vol. 1. IEEE, 2003, pp. 284–292.
[3]O. Sheyner, J. Haines, S. Jha, R. Lippmann, and J. M. Wing, “Automated generation and analysis of attack graphs,” in Security and privacy, 2002. Proceedings. 2002 IEEE Symposium on. IEEE, 2002, pp. 273–284.
[4]B. Schneier, “Attack trees,” Dr. Dobbs journal, vol. 24, no. 12, pp. 21–29, 1999.
[5]S. Mauw and M. Oostdijk, “Foundations of attack trees,” in International Conference on Information Security and Cryptology. Springer, 2005, pp. 186–198.
[6]X. Qin and W. Lee, “Statistical causality analysis of infosec alert data,” in International Workshop on Recent Advances in Intrusion Detection. Springer, 2003, pp. 73–93.
[7]A. Valdes and K. Skinner, “Probabilistic alert correlation,” in International Workshop on Recent Advances in Intrusion Detection. Springer, 2001, pp. 54–68.
[8]P. A. Porras, M. W. Fong, and A. Valdes, “A mission- impact-based approach to infosec alarm correlation,” in International Workshop on Recent Advances in Intrusion Detection. Springer, 2002, pp. 95–114.
[9]I. D. W. Group et al., “Intrusion detection message exchange format data model and extensible markup language (xml) document type definition,” Internet-Draft, pp. 21–26, 2003.
[10]K. Julisch and M. Dacier, “Mining intrusion detection alarms for actionable knowledge,” in Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2002, pp. 366–375.
[11]C. Granger, “Investigating causal relations by econometric,” Rational Expectations and Econometric Practice, vol. 1, p. 371, 1981.
[12]G. M. Ljung and G. E. Box, “On a measure of lack of fit in time series models,” Biometrika, vol. 65, no. 2, pp. 297–303, 1978.
[13]A. J. Hayer, Probability and Statistics for Engineers and Scientists. Duxbury Press, 2002.
[14]X. Ou, W. F. Boyer, and M. A. McQueen, “A scalable approach to attack graph generation,” in Proceedings of the 13th ACM conference on Computer and communications security. ACM, 2006, pp. 336–345.
[15]C. Phillips and L. P. Swiler, “A graph-based system for network vulnerability analysis,” in Proceedings of the 1998 workshop on New security paradigms. ACM, 1998, pp. 71–79.
[16]X. Ou, S. Govindavajhala, and A. W. Appel, “Mulval: A logic-based network security analyzer.” in USENIX security, 2005.
[17]P. Rao, K. Sagonas, T. Swift, D. S. Warren, and J. Freire, “Xsb: A system for efficiently computing well-founded semantics,” in International Conference on Logic Programming and Non-monotonic Reasoning. Springer, 1997, pp. 430–440.
[18]B. Zhu and A. A. Ghorbani, “Alert correlation for extracting attack strategies,” IJ Network Security, vol. 3, no. 3, pp. 244–258, 2006.
[19]F. Cuppens and A. Miege, “Alert correlation in a cooperative intrusion detection framework,” in Security and privacy, 2002. proceedings. 2002 ieee symposium on. IEEE, 2002, pp. 202– 215.
[20]F. Cuppens and R. Ortalo, “Lambda: A language to model a database for detection of attacks,” in International Workshop on Recent Advances in Intrusion Detection. Springer, 2000, pp. 197–216.
[21]O. Dain and R. K. Cunningham, “Fusing a heterogeneous alert stream into scenarios,” in Proceedings of the 2001 ACM workshop on Data Mining for Security Applications, vol. 13. Citeseer, 2001.
[22]S. T. Eckmann, G. Vigna, and R. A. Kemmerer, “Statl: An attack language for state-based intrusion detection,” Journal of computer security, vol. 10, no. 1, 2, pp. 71–103, 2002.
[23]P. Ning, Y. Cui, and D. S. Reeves, “Constructing attack scenarios through correlation of intrusion alerts,” in Proceedings of the 9th ACM conference on Computer and communications security. ACM, 2002, pp. 245–254.
[24]S. J. Templeton and K. Levitt, “A requires/provides model for computer attacks,” in Proceedings of the 2000 workshop on New security paradigms. ACM, 2001, pp. 31–38.
[25]J. B. Hong, D. S. Kim, and T. Takaoka, “Scalable attack representation model using logic reduction techniques,” in 2013 12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications. IEEE, 2013, pp. 404–411.
[26]B. Schneier, Secrets and lies: digital security in a networked world. John Wiley & Sons, 2011.
[27]L. Munoz-Gonzalez, D. Sgandurra, M. Barrere, and E. C. Lupu, “Exact inference techniques for the analysis of bayesian attack graphs,” arXiv preprint arXiv: 1510.02427, 2015.
[28]N. Poolsappasit, R. Dewri, and I. Ray, “Dynamic security risk management using bayesian attack graphs,” IEEE Transactions on Dependable and Secure Computing, vol. 9, no. 1, pp. 61–74, 2012.
[29]M. Albanese, S. Jajodia, and S. Noel, “Time-efficient and cost- effective network hardening using attack graphs,” in IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2012). IEEE, 2012, pp. 1–12.
[30]K. Ingols, M. Chu, R. Lippmann, S. Webster, and S. Boyer, “Modeling modern network attacks and countermeasures using attack graphs,” in Computer Security Applications Conference, 2009. ACSAC’09. Annual. IEEE, 2009, pp. 117–126.
[31]L. Wang, T. Islam, T. Long, A. Singhal, and S. Jajodia, “An attack graph-based probabilistic security metric,” in IFIP Annual Conference on Data and Applications Security and Privacy. Springer, 2008, pp. 283–296.
[32]Forum of Incident Response and Security Teams, “Common vulnerability scoring system, v3 development update,” https://www.first.org/cvss, [Accessed: 12-21-2016].
[33]J. Pearl, “Reverend bayes on inference engines: A distributed hierarchical approach,” in AAAI, 1982, pp. 133–136.
[34]C. M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics). Secaucus, NJ, USA: Springer-Verlag New York, Inc., 2006.
[35]Y. Weiss, “Correctness of local probability propagation in graphical models with loops,” Neural computation, vol. 12, no. 1, pp. 1–41, 2000.
[36]V. Saini, Q. Duan, and V. Paruchuri, “Threat modeling using attack trees,” Journal of Computing Sciences in Colleges, vol. 23, no. 4, pp. 124–131, 2008.
[37]K. S. Edge, “A framework for analyzing and mitigating the vulnerabilities of complex systems via attack and protection trees,” DTIC Document, Tech. Rep., 2007.
[38]K. Edge, R. Raines, M. Grimaila, R. Baldwin, R. Bennington, and C. Reuter, “The use of attack and protection trees to analyze security for an online banking system,” in System Sciences, 2007. HICSS 2007. 40th Annual Hawaii International Conference on. IEEE, 2007, p. 144b.
[39]I. Inc, “Attacktree+,” https://www.isograph.com/software/ attacktree/, [Accessed: 12-31-2016].
[40]A. T. Ltd., “Securitree,” http://www.amenaza.com/, [Accessed: 12-31-2016].
[41]R. Lippmann, K. Ingols, C. Scott, K. Piwowarski, K. Kratkiewicz, M. Artz, and R. Cunningham, “Validating and restoring defense in depth using attack graphs,” in MILCOM 2006-2006 IEEE Military Communications conference. IEEE, 2006, pp. 1–10.
[42]J. Pamula, S. Jajodia, P. Ammann, and V. Swarup, “A weakest- adversary security metric for network configuration security analysis,” in Proceedings of the 2nd ACM workshop on Quality of protection. ACM, 2006, pp. 31–38.
[43]N. Idika and B. Bhargava, “Extending attack graph-based security metrics and aggregating their application,” IEEE Trans- actions on dependable and secure computing, vol. 9, no. 1, pp. 75–85, 2012.
[44]R. Ortalo, Y. Deswarte, and M. Kaaniche, “Experimenting with quantitative evaluation tools for monitoring operational security,” IEEE Transactions on Software Engineering, vol. 25, no. 5, pp. 633–650, 1999.
[45]L. Munoz-Gonzalez, D. Sgandurra, A. Paudice, and E. C. Lupu, “Efficient attack graph analysis through approximate inference,” arXiv preprint arXiv: 1606.07025, 2016.
[46]K. S. Edge, G. C. Dalton, R. A. Raines, and R. F. Mills, “Using attack and protection trees to analyze threats and defenses to homeland security,” in MILCOM 2006-2006
IEEE Military Communications conference. IEEE, 2006, pp. 1–7.
[47]B. Kordy, S. Mauw, S. Radomirovic ?, and P. Schweitzer, “Foundations of attack–defense trees,” in International Workshop on Formal Aspects in Security and Trust. Springer, 2010, pp. 80–95.
[48]S. Bistarelli, F. Fioravanti, and P. Peretti, “Defense trees for economic evaluation of security investments,” in First International Conference on Availability, Reliability and Security (ARES’06). IEEE, 2006, pp. 8–pp.
[49]Y. Luo, F. Szidarovszky, Y. Al-Nashif, and S. Hariri, “Game theory based network security,” Journal of Information Security, vol. 1, no. 1, p. 41, 2010.
[50]B. Kordy, S. Mauw, M. Melissen, and P. Schweitzer, “Attack–defense trees and two-player binary zero-sum extensive form games are equivalent,” in International Conference on Decision and Game Theory for Security. Springer, 2010, pp. 245–256.
[51]A. Buldas, P. Laud, J. Priisalu, M. Saarepera, and J. Willemson, “Rational choice of security measures via multi-parameter attack trees,” in International Workshop on Critical Information Infrastructures Security. Springer, 2006, pp. 235–248.
[52]A. Jurgenson and J. Willemson, “Computing exact outcomes of multi-parameter attack trees,” in OTM Confederated International Conferences” On the Move to Meaningful Internet Systems”. Springer, 2008, pp. 1036–1051.
[53]M. GhasemiGol, A. Ghaemi-Bafghi, and H. Takabi, “A comprehensive approach for network attack forecasting,” Computers and Security, vol. 58, pp. 83-105, 2016.
[54]S. Nagaraju and L. Parthiban, “Analyzing configurations of authentication access points in cloud using attack graph,” in 2015 IEEE International Conference on Computer Graphics, Vision and Information Security (CGVIS). IEEE, 2015, pp. 72–76.
[55]M. Ficco, L. Tasquier, and R. Aversa, “Intrusion detection in cloud computing,” in P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC), 2013 Eighth International Conference on. IEEE, 2013, pp. 276–283.
[56]C. J. Chung, P. Khatkar, T. Xing, J. Lee, and D. Huang, “Nice: Network intrusion detection and countermeasure selection in virtual network systems,” IEEE transactions on dependable and secure computing, vol. 10, no. 4, pp. 198–211, 2013.
[57]Z. Hu, S. Gnatyuk, O. Koval, V. Gnatyuk, and S. Bondarovets, “Anomaly Detection System in Secure Cloud Computing Environment,” International Journal of Computer Network and Information Security, vol. 9, no. 4, pp 10-21, 2017.
[58]S. Hashemi and P. Hesarlo, “Security, privacy and trust challenges in cloud computing and solutions,” International Journal of Computer Network and Information Security, vol. 6, no. 8, pp 34-40, 2014.
[59]P. Wang, W. Lin, P. Kuo, H. Lin, and T. Wang, “Threat risk analysis for cloud security based on Attack-Defense Trees,” in 2012 8th International Conference on Computing Technology and Information Management (ICCM), IEEE, 2012, pp. 106-111.
[60]N. Alhebaishi, L. Wang, S. Jajodia, and A. Singhal, “Threat Modeling for Cloud Data Center Infrastructures,” in International Symposium on Foundations and Practice of Security, Springer, 2016, pp. 302-319.
[61]B. Kordy, S. Mauw, S. Radomirovic, and P. Schweitzer, “Attack–defense trees,” Journal of Logic and Computation, p. 29, 2012.
[62]R. Vigo, F. Nielson, and H. R. Nielson, “Automated generation of attack trees,” in 2014 IEEE 27th Computer Security Foundations Symposium. IEEE, 2014, pp. 337–350.
[63]M. G. Ivanova, C. W. Probst, R. R. Hansen, and F. Kammuller, “Attack tree generation by policy invalidation,” in IFIP International Conference on Information Security Theory and Practice. Springer, 2015, pp. 249–259.
[64]S. Pinchinat, M. Acher, and D. Vojtisek, “Towards synthesis of attack trees for supporting computer-aided risk analysis,” in International Conference on Software Engineering and Formal Methods. Springer, 2014, pp. 363–375.
[65]J. Dawkins and J. Hale, “A systematic approach to multi-stage network attack analysis,” in Information Assurance Workshop, 2004. Proceedings. Second IEEE International. IEEE, 2004, pp. 48–56.
[66]M. Bruglieri, F. Maffioli, and M. Ehrgott, “Cardinality con- strained minimum cut problems: complexity and algorithms,” Discrete Applied Mathematics, vol. 137, no. 3, pp. 311–341, 2004.
[67]S. Roschke, F. Cheng, and C. Meinel, “Intrusion detection in the cloud,” in Dependable, Autonomic and Secure Computing, 2009. DASC’09. Eighth IEEE International Conference on. IEEE, 2009, pp. 729–734.
[68]D. Yu and D. Frincke, “A novel framework for alert correlation and understanding,” in International Conference on Applied Cryptography and Network Security. Springer, 2004, pp. 452–466.
[69]T. F. Lunt et al., “Real-time intrusion detection,” COMPCOM Spring, vol. 89, pp. 348–353, 1989.
[70]K. Haslum, M. E. Moe, and S. J. Knapskog, “Real-time intrusion prevention and security analysis of networks using hmms,” in 2008 33rd IEEE Conference on Local Computer Networks (LCN). IEEE, 2008, pp. 927–934.
[71]A. K. Ghosh, C. Michael, and M. Schatz, “A real-time intrusion detection system based on learning program behavior,” in International Workshop on Recent Advances in Intrusion Detection. Springer, 2000, pp. 93–109.

International Journal of Computer Network and Information Security (IJCNIS)