Distilling critical attack graph surface iteratively through minimum-cost SAT solving

ABSTRACT

It has long been recognized that it can be tedious and even infeasible for system administrators to figure out critical security problems residing in full attack graphs, even for small-sized enterprise networks. Therefore a trade-off between analysis accuracy and efficiency needs to be made to achieve a reasonable balance between completeness of the attack graph and its usefulness. In this paper, we provide an approach to attack graph distillation, so that the user can control the amount of information presented by sifting out the most critical portion of the full attack graph. The user can choose to see only the k most critical attack paths, based on specified severity metrics, e.g. the likelihood for an attacker to carry out certain exploit on certain machine and the chance of success. We transform an dependency attack graph into a Boolean formula and assign cost metrics to attack variables in the formula, based on the severity metrics. We then apply Minimum-Cost SAT Solving (MCSS) to find the most critical path in terms of the least cost incurred for the attacker to deploy multi-step attacks leading to certain crucial assets in the network. An iterative process inspired by Counter Example Guided Abstraction and Refinement (CEGAR) is designed to efficiently guide the MCSS to render solutions that contain a controlled number of realistic attack paths, forming a critical attack graph surface. Our method can distill critical attack graph surfaces from the full attack graphs generated for moderate-sized enterprise networks in only several minutes. Experiments on various sized network scenarios show that even for a small-sized critical attack graph surface (around 15% the size of the original full attack graph), the calculated risk metrics are good approximation of the values computed with the full attack graph, meaning the distilled critical attack graph surface is able to capture the crucial security problems in an enterprise network for further in-depth analysis.

References

1. P. Ammann, D. Wijesekera, and S. Kaushik. Scalable, graph-based network vulnerability analysis. In Proceedings of 9th ACM Conference on Computer and Communications Security, Washington, DC, November 2002.
2. Z. S. Andraus, M. H. Liffiton, and K. A. Sakallah. Refinement strategies for verification methods based on datapath abstraction. In Proceedings of the 2006 Asia and South Pacific Design Automation Conference(ASP-DAC), 2006.
3. E. Clarke, O. Grumberg, S. Jha, Y. Lu, and H. Veith. Counterexample-guided abstraction refinement. In Proceedings of Computer Aided Verification (CAV), volume 1855, pages 154--169, 2000.
4. O. Coudert. On solving covering problems. In 33rd Design Automation Conference (DAC'96), pages 197--202, 1996.
5. M. Dacier, Y. Deswarte, and M. Kaâniche. Models and tools for quantitative assessment of operational security. In IFIP SEC, 1996.
6. L. de Moura and N. Bjørner. Z3: An efficient SMT solver. In Tools and Algorithms for the Construction and Analysis of System (TACAS), pages 337--340, 2008.
7. R. Dewri, N. Poolsappasit, I. Ray, and D. Whitley. Optimal security hardening using multi-objective optimization on attack tree models of networks. In 14th ACM Conference on Computer and Communications Security (CCS), 2007.
8. M. Frigault and L. Wang. Measuring network security using Bayesian network-based attack graphs. In Proceedings of the 3rd IEEE International Workshop on Security, Trust, and Privacy for Software Applications (STPSA'08), 2008.
9. Z. Fu and S. Malik. Solving the minimum-cost satisfiability problem using sat based branch and bound search. In Proceedings of the International Conference on Computer-Aided Design (ICCAD'06), San Jose, CA, USA, 2006.
10. J. Homer and X. Ou. SAT-solving approaches to context-aware enterprise network security management. IEEE J SAC Special Issue on Network Infrastructure Configuration, 27(3), April 2009.
11. J. Homer, X. Ou, and D. Schmidt. A sound and practical approach to quantifying security risk in enterprise networks. Technical report, Kansas State University, 2009.
12. J. Homer, A. Varikuti, X. Ou, and M. A. McQueen. Improving attack graph visualization through data reduction and attack grouping. In The 5th International Workshop on Visualization for Cyber Security (VizSEC), 2008.
13. M. Howard, J. Pincus, and J. Wing. Measuring relative attack surfaces. In Proceedings of Workshop on Advanced Developments in Software and Systems Security, 2003.
14. K. Ingols, R. Lippmann, and K. Piwowarski. Practical attack graph generation for network defense. In 22nd Annual Computer Security Applications Conference (ACSAC), Miami Beach, Florida, December 2006.
15. S. Jajodia, S. Noel, and B. O'Berry. Topological analysis of network attack vulnerability. In V. Kumar, J. Srivastava, and A. Lazarevic, editors, Managing Cyber Threats: Issues, Approaches and Challanges, chapter 5. Kluwer Academic Publisher, 2003.
16. S. Jha, O. Sheyner, and J. M. Wing. Two formal analyses of attack graphs. In Proceedings of the 15th IEEE Computer Security Foundations Workshop, pages 49--63, Nova Scotia, Canada, June 2002.
17. X. Y. Li. Optimization Algorithms for the Minimum-Cost Satisfiability Problem. PhD thesis, North Carolina State University, Raleigh, North Carolina, 2004.
18. R. P. Lippmann, K. W. Ingols, C. Scott, K. Piwowarski, K. Kratkiewicz, M. Artz, and R. Cunningham. Evaluating and strengthening enterprise network security using attack graphs. Technical Report ESC-TR-2005-064, MIT Lincoln Laboratory, October 2005.
19. Y. S. Mahajan, Z. Fu, and S. Malik. Zchaff2004: An efficient SAT solver. In Lecture Notes in Computer Science SAT 2004 Special Volume, pages 360--375. LNCS 3542, 2004
20. P. Manadhata and J. Wing. An attack surface metric. IEEE Transactions on Software Engineering, 2010.
21. P. Manadhata, J. Wing, M. Flynn, and M. McQueen. Measuring the attack surfaces of two FTP daemons. In Proceedings of the 2nd ACM workshop on Quality of Protection, 2006.
22. V. M. Manquinho and J. ao P. Marques-Silva. Search pruning techniques in SAT-based branch-and-bound algorithmsfor the binate covering problem. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 21:505--516, 2002.
23. V. Mehta, C. Bartzis, H. Zhu, E. Clarke, and J. Wing. Ranking attack graphs. In Proceedings of Recent Advances in Intrusion Detection (RAID), September 2006.
24. P. Mell, K. Scarfone, and S. Romanosky. A Complete Guide to the Common Vulnerability Scoring System Version 2.0. Forum of Incident Response and Security Teams (FIRST), June 2007.
25. S. Narain, G. Levin, S. Malik, and V. Kaul. Declarative infrastructure configuration synthesis and debugging. Journal of Network and Systems Management, 2008.
26. L. R. Nielsena, K. A. Andersenb, and D. Pretolani. Finding the k shortest hyperpaths. Computers & Operations Research, 32:1477--1497, 2005.
27. S. Noel and S. Jajodia. Managing attack graph complexity through visual hierarchical aggregation. In VizSEC/DMSEC '04: Proceedings of the 2004 ACM workshop on Visualization and data mining for computer security, pages 109--118, New York, NY, USA, 2004. ACM Press.
28. S. Noel, S. Jajodia, B. O'Berry, and M. Jacobs. Efficient minimum-cost network hardening via exploit dependency graphs. In 19th Annual Computer Security Applications Conference (ACSAC), December 2003.
29. X. Ou, W. F. Boyer, and M. A. McQueen. A scalable approach to attack graph generation. In 13th ACM Conference on Computer and Communications Security (CCS), pages 336--345, 2006.
30. X. Ou and A. Singhal. Quantitative security risk assessment of enterprise networks. Information Security. SpringerBrief, 2011.
31. C. Phillips and L. P. Swiler. A graph-based system for network-vulnerability analysis. In NSPW '98: Proceedings of the 1998 workshop on New security paradigms, pages 71--79. ACM Press, 1998.
32. D. Saha. Extending logical attack graphs for efficient vulnerability analysis. In Proceedings of the 15th ACM conference on Computer and Communications Security (CCS), 2008.
33. R. Sawilla and X. Ou. Identifying critical attack assets in dependency attack graphs. In 13th European Symposium on Research in Computer Security (ESORICS), Malaga, Spain, October 2008.
34. M. Schiffman, G. Eschelbeck, D. Ahmad, A. Wright, and S. Romanosky. CVSS: A Common Vulnerability Scoring System. National Infrastructure Advisory Council (NIAC), 2004.
35. O. Sheyner, J. Haines, S. Jha, R. Lippmann, and J. M. Wing. Automated generation and analysis of attack graphs. In Proceedings of the 2002 IEEE Symposium on Security and Privacy, pages 254--265, 2002.
36. L. Wang, T. Islam, T. Long, A. Singhal, and S. Jajodia. An attack graph-based probabilistic security metric. In Proceedings of The 22nd Annual IFIP WG 11.3 Working Conference on Data and Applications Security (DBSEC '08), 2008.
37. L. Wang, S. Noel, and S. Jajodia. Minimum-cost network hardening using attack graphs. Computer Communications, 29:3812--3824, November 2006.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Information systems

  • Information systems applications

• Security and privacy

  • Cryptography

    • Cryptanalysis and other attacks

  • Intrusion/anomaly detection and malware mitigation

• Social and professional topics

  • Computing / technology policy

    • Computer crime

  • Professional topics

    • Management of computing and information systems

      • Software management

        • Software selection and adaptation

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Empirical software validation

  • Software organization and properties

    • Extra-functional properties

      • Software performance

    • Software functional properties

      • Formal methods