Abstract
In the present scenario, even well administered networks are susceptible to sophisticated cyber attacks. Such attack combines vulnerabilities existing on different systems/services and are potentially more harmful than single point attacks. One of the methods for analyzing such security vulnerabilities in an enterprise network is the use of attack graph. It is a complete graph which gives a succinct representation of different attack scenarios, depicted by attack paths. An attack path is a logical succession of exploits, where each exploit in the series satisfies the preconditions for subsequent exploits and makes a causal relationship among them. Thus analysis of the attack graph may help in assessing network security from hackers’ perspective. One of the intrinsic problems with the generation and analysis of such a complete attack graph is its scalability. In this work, an approach based on Planner, a special purpose search algorithm from artificial intelligence domain, has been proposed for time-efficient, scalable representation of the attack graphs. Further, customized algorithms have been developed for automatic generation of attack paths (using Planner as a low-level module). The analysis shows that generation of attack graph using the customized algorithms can be done in polynomial time. A case study has also been presented to demonstrate the efficacy of the proposed methodology.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Noel S, Jajodia S, O’Berry B, Jacobs M (2003) Efficient minimum-cost network hardening via exploit dependency graph. In: Proceedings of 19th annual computer security applications conference (ACSAC 2003), Las Vegas, Nevada, pp 86–95
Phillips C, Swiler LP (1998) A graph-based system for network-vulnerability analysis. In: Proceedings of the workshop on new security paradigms (NSPW), Virginia, USA, pp 71–79
Tidwell T, Larson R, Fitch K, Hale J (2001) Modelling internet attacks. In: Proceedings of the second annual IEEE SMC information assurance workshop, United States Military Academy, West Point, New York. IEEE Press, New York, pp 54–59
Dawkins J, Hale J (2004) A systematic approach to multi-stage network attack analysis. In: Proceedings of the second IEEE internation information assurance workshop (IWIA ’04), IEEE Computer Society, Washington, pp 48–56
Ortalo R, Deswarte Y, Kanniche M (1999) Experimenting with quantitative evaluation tools for monitoring operational security. IEEE Trans Soft Eng 25(5):633–650
Ritchey RW, Ammann P (2000) Using model checking to analyze network vulnerabilities. In: Proceedings of the 2000 IEEE symposium on security and privacy, Oakland, CA, pp 156–165
Templeton S, Levitt K (2001) A requires/provides model for computer attacks. In: Proceedings of the 2000 workshop on new security paradigms, Ballycotton, County Cork, Ireland. ACM Press, New York, pp 31–38
Sheynar O, Jha S, Wing JM, Lippmann RP, Haines J (2002) Automated generation and analysis of attack graphs. In: Proceedings of the 2002 IEEE symposium on security and privacy, pp 273–284
Ammann P, Wijesekera D, Kaushik S (2002) Scalable, graph-based network vulnerability analysis. In: Proceedings of CCS 2002: 9th ACM conference on computer and communications security, Washington, DC. ACM Press, New York, pp 217–224
Jajodia S, Noel S, O’Berry B (2005) Topological analysis of network attack vulnerability. In: Managing cyber threats: issues, approaches and challenges, vol V. Springer, New York, pp 247–266
Ammann P, Pamula J, Ritchey R, Street J (2005) A host-based approach to network attack chaining analysis. In: Proceedings of the 21st annual computer security applications conference (ACSAC), pp 72–84
Pamula J, Jajodia S, Ammann P, Swarup V (2006) A weakest-adversary security metric for network configuration security analysis. In: Proceedings of 2nd ACM workshop on quality of protection. ACM Press, New York, pp 31–38
Zhang T, Hu MZ, Li D, Sun L (2005) An effective method to generate attack graph. In: Proceedings of the international conference on machine learning and cybernetics (ICMLC), Guangzhou, China, pp 3926–3931
Ingols K, Lippmann R, Piwowarski K (2006) Practical attack graph generation for network defense. In: Proceedings of the 22nd annual computer security applications conference (ACSAC ’06), pp 121–130
Wang L, Islam T, Long T, Singhal A, Jajodia S (2008) An attack graph-based probabilistic security metric. In: Proceedings of the international federation for information processing (IFIP). LNCS, vol 5094, pp 283–296
Wang L, Noel S, Jajodia S (2006) Minimum cost-network hardening using attack graphs. Comput Commun 29(18):3812–3824
Blum AL, Furst ML (1997) Fast planning through planning graph analysis. J Artif Intell 281–300
Bonet B, Geffner H (2001) Planning and control in artificial intelligence: A unifying perspective. Appl Intell 14:237–252
Fox M, Long D (2003) Pddl 2.1: An extension to pddl for expression temporal planning domains. J Artif Intell Res, 61–124
Martin M, Geffner H (2004) Learning generalized policies from planning examples using concept languages. Appl Intell 20:9–19
Sheynar O (2004) Scenario graphs and attack graphs. PhD thesis, Carnegie Mellon University, USA
Sheynar O, Wing JM (2004) Tools for generating and analyzing attack graphs. In: Proceedings of the workshop on formal methods for components and objects (FMCO), Leiden, The Netherlands, pp 344–371
Chen Y, Hsu C, Wah B (2006) Temporal planning using subgoal partitioning and resolution in sgplan. J Artif Intell Res, 323–369
Ghosh N, Ghosh SK (2009) An intelligent technique for generating minimal attack graph. In: Proceedings of the first workshop on intelligent security (security and artificial intelligence, SecArt 2009), 19th international conference on automated planning and scheduling (ICAPS’09), Thessaloniki, Greece, pp 42–51
Bhattacharya S (2008) Security risk management of local area network. Master’s thesis, School of Information Technology, I.I.T Kharagpur
Ghosh N, Ghosh SK (2010) An intelligent approach for security management of an enterprise network using planner. Studies in computational intelligence, vol 275. Springer, Berlin, pp 187–214
Cuppens F, Ortalo R (2000) Lambda: A language to model a database for detection of attacks. In: Proceedings of the 3rd international workshop on the recent advances in intrusion detection (RAID). LNCS, vol 1907. Springer, Berlin, pp 197–216
Grinstead CM, Snell JL (1997) Introduction to probability. American Mathematical Society, Providence
Lippmann RP, Ingols IW (2005) An annotated review of past papers on attack graphs. Technical Report ESC-TR-2005-054, Lincoln Laboratory, Massachusetts Institute of Technology, USA
Swiler LP, Phillips C, Ellis D, Chakerian S (2001) Computer-attack graph generation tool. In: Proceedings of the 2nd DARPA information survivability conference & exposition (DISCEX II), vol II. IEEE Computer Society, Los Alamitos, pp 307–321
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ghosh, N., Ghosh, S.K. A planner-based approach to generate and analyze minimal attack graph. Appl Intell 36, 369–390 (2012). https://doi.org/10.1007/s10489-010-0266-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-010-0266-8