Skip to main content
SpringerLink
Log in

A planner-based approach to generate and analyze minimal attack graph

  • Published:
Applied Intelligence Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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

    Chapter  Google Scholar 

  2. 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

    Google Scholar 

  3. 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

    Google Scholar 

  4. 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

    Chapter  Google Scholar 

  5. Ortalo R, Deswarte Y, Kanniche M (1999) Experimenting with quantitative evaluation tools for monitoring operational security. IEEE Trans Soft Eng 25(5):633–650

    Article  Google Scholar 

  6. 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

    Google Scholar 

  7. 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

    Google Scholar 

  8. 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

    Chapter  Google Scholar 

  9. 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

    Chapter  Google Scholar 

  10. 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

    Google Scholar 

  11. 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

    Chapter  Google Scholar 

  12. 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

    Chapter  Google Scholar 

  13. 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

    Chapter  Google Scholar 

  14. 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

    Chapter  Google Scholar 

  15. 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

    Google Scholar 

  16. Wang L, Noel S, Jajodia S (2006) Minimum cost-network hardening using attack graphs. Comput Commun 29(18):3812–3824

    Article  Google Scholar 

  17. Blum AL, Furst ML (1997) Fast planning through planning graph analysis. J Artif Intell 281–300

  18. Bonet B, Geffner H (2001) Planning and control in artificial intelligence: A unifying perspective. Appl Intell 14:237–252

    Article  MATH  Google Scholar 

  19. Fox M, Long D (2003) Pddl 2.1: An extension to pddl for expression temporal planning domains. J Artif Intell Res, 61–124

  20. Martin M, Geffner H (2004) Learning generalized policies from planning examples using concept languages. Appl Intell 20:9–19

    Article  MATH  Google Scholar 

  21. Sheynar O (2004) Scenario graphs and attack graphs. PhD thesis, Carnegie Mellon University, USA

  22. 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

    Chapter  Google Scholar 

  23. Chen Y, Hsu C, Wah B (2006) Temporal planning using subgoal partitioning and resolution in sgplan. J Artif Intell Res, 323–369

  24. 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

    Google Scholar 

  25. Bhattacharya S (2008) Security risk management of local area network. Master’s thesis, School of Information Technology, I.I.T Kharagpur

  26. 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

    Google Scholar 

  27. 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

    Chapter  Google Scholar 

  28. Grinstead CM, Snell JL (1997) Introduction to probability. American Mathematical Society, Providence

    MATH  Google Scholar 

  29. 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

  30. 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

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Information Technology, Indian Institute of Technology, Kharagpur, 721302, India

    Nirnay Ghosh & S. K. Ghosh

Authors
  1. Nirnay Ghosh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. K. Ghosh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. K. Ghosh.

Rights and permissions

Reprints 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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-010-0266-8

Keywords

Search

Navigation