{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T17:47:33Z","timestamp":1772041653801,"version":"3.50.1"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,7,31]],"date-time":"2017-07-31T00:00:00Z","timestamp":1501459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/L022729\/1"],"award-info":[{"award-number":["EP\/L022729\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Priv. Secur."],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>Attack graphs provide compact representations of the attack paths an attacker can follow to compromise network resources from the analysis of network vulnerabilities and topology. These representations are a powerful tool for security risk assessment. Bayesian inference on attack graphs enables the estimation of the risk of compromise to the system\u2019s components given their vulnerabilities and interconnections and accounts for multi-step attacks spreading through the system. While static analysis considers the risk posture at rest, dynamic analysis also accounts for evidence of compromise, for example, from Security Information and Event Management software or forensic investigation. However, in this context, exact Bayesian inference techniques do not scale well. In this article, we show how Loopy Belief Propagation\u2014an approximate inference technique\u2014can be applied to attack graphs and that it scales linearly in the number of nodes for both static and dynamic analysis, making such analyses viable for larger networks. We experiment with different topologies and network clustering on synthetic Bayesian attack graphs with thousands of nodes to show that the algorithm\u2019s accuracy is acceptable and that it converges to a stable solution. We compare sequential and parallel versions of Loopy Belief Propagation with exact inference techniques for both static and dynamic analysis, showing the advantages and gains of approximate inference techniques when scaling to larger attack graphs.<\/jats:p>","DOI":"10.1145\/3105760","type":"journal-article","created":{"date-parts":[[2017,8,1]],"date-time":"2017-08-01T19:20:44Z","timestamp":1501615244000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["Efficient Attack Graph Analysis through Approximate Inference"],"prefix":"10.1145","volume":"20","author":[{"given":"Luis","family":"Mu\u00f1oz-Gonz\u00e1lez","sequence":"first","affiliation":[{"name":"Imperial College London, London, UK"}]},{"given":"Daniele","family":"Sgandurra","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, Egham Hill, Egham, UK"}]},{"given":"Andrea","family":"Paudice","sequence":"additional","affiliation":[{"name":"Imperial College London, London, UK"}]},{"given":"Emil C.","family":"Lupu","sequence":"additional","affiliation":[{"name":"Imperial College London, London, UK"}]}],"member":"320","published-online":{"date-parts":[[2017,7,31]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2016. CVE Details. The ultimate security vulnerability datasource. Retrieved from http:\/\/www.cvedetails.com 2016. CVE Details. The ultimate security vulnerability datasource. Retrieved from http:\/\/www.cvedetails.com"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2012.6263942"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23822-2_23"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/586110.586140"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10669-013-9463-4"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382284"},{"key":"e_1_2_2_7_1","volume-title":"Pattern Recognition and Machine Learning","author":"Bishop C. M."},{"key":"e_1_2_2_8_1","unstructured":"Common Vulnerability Scoring System V3. 2016. Development update. Retrieved from https:\/\/www.first.org\/cvss. (2016). Common Vulnerability Scoring System V3. 2016. Development update. Retrieved from https:\/\/www.first.org\/cvss. (2016)."},{"key":"e_1_2_2_9_1","unstructured":"Common Weaknesses Scoring System. 2014. Retrieved from https:\/\/cwe.mitre.org\/cwss\/cwss_v1.0.1.html. (2014). Common Weaknesses Scoring System. 2014. Retrieved from https:\/\/cwe.mitre.org\/cwss\/cwss_v1.0.1.html. (2014)."},{"key":"e_1_2_2_10_1","first-page":"393","article-title":"The computational complexity of probabilistic inference using bayesian belief networks","volume":"42","author":"Cooper G. F.","year":"1990","journal-title":"J. AI"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the International Conference on Uncertainty in AI. 211--219","author":"Dechter R.","year":"1996"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1456362.1456368"},{"key":"e_1_2_2_13_1","unstructured":"Gartner Inc. 2014. Gartner Says Worldwide Information Security Spending Will Grow Almost 8 Percent in 2014 as Organizations Become More Threat-Aware. Retrieved from http:\/\/www.gartner.com\/newsroom\/id\/2828722. Gartner Inc. 2014. Gartner Says Worldwide Information Security Spending Will Grow Almost 8 Percent in 2014 as Organizations Become More Threat-Aware. Retrieved from http:\/\/www.gartner.com\/newsroom\/id\/2828722."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2010.61"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1046920.1088703"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSAC.2009.21"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/MILCOM.2011.6127490"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-24230-9_9"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSFW.2002.1021806"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2015.23268"},{"key":"e_1_2_2_21_1","unstructured":"D. Koller and N. Friedman. 2009. Probabilistic Graphical Models: Principles and Techniques. MIT Press Cambridge MA. D. Koller and N. Friedman. 2009. Probabilistic Graphical Models: Principles and Techniques. MIT Press Cambridge MA."},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the International Symposium on Cluster Computing and the Grid. 1--11","author":"Li W."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/MILCOM.2006.302434"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.604240"},{"key":"e_1_2_2_25_1","unstructured":"N. Lord. 2015. The History of Data Breaches. Retrieved from https:\/\/digitalguardian.com\/blog\/history-data-breaches. N. Lord. 2015. The History of Data Breaches. Retrieved from https:\/\/digitalguardian.com\/blog\/history-data-breaches."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2808691"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the Conference on Uncertainty in AI. 396--403","author":"Mooij J. M."},{"key":"#cr-split#-e_1_2_2_28_1.1","unstructured":"L. Mu\u00f1oz-Gonz\u00e1lez D. Sgandurra M. Barr\u00e8re and E. C. Lupu. 2017. Exact inference techniques for the analysis of Bayesian attack graphs. To appear in IEEE Transactions on Dependable and Secure Computing (DOI:10.1109\/TDSC.2016.2627033) 10.1109\/TDSC.2016.2627033)"},{"key":"#cr-split#-e_1_2_2_28_1.2","unstructured":"L. Mu\u00f1oz-Gonz\u00e1lez D. Sgandurra M. Barr\u00e8re and E. C. Lupu. 2017. Exact inference techniques for the analysis of Bayesian attack graphs. To appear in IEEE Transactions on Dependable and Secure Computing (DOI:10.1109\/TDSC.2016.2627033)"},{"key":"e_1_2_2_29_1","volume-title":"Machine Learning: A Probabilistic Perspective","author":"Murphy K. P."},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the Conference on Uncertainty on AI. 467--475","author":"Murphy K. P."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1029208.1029225"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602087.2602117"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSAC.2003.1254313"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.815323"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180446"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1179494.1179502"},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the National Conference on AI. 133--136","author":"Pearl J.","year":"1982"},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"J. Pearl. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann. J. Pearl. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann.","DOI":"10.1016\/B978-0-08-051489-5.50008-4"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/310889.310919"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2011.34"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/MASSP.1986.1165342"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SPW.2013.12"},{"key":"e_1_2_2_43_1","first-page":"21","article-title":"Attack trees","volume":"24","author":"Schneier B.","year":"1999","journal-title":"Dr. Dobbs J."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01531015"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2011.5958263"},{"key":"e_1_2_2_46_1","volume-title":"Proceedings of the Conference on Uncertainty in AI. 169--198","author":"Shenoy P. P."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/SECPRI.2002.1004377"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30101-1_17"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/DISCEX.2001.932182"},{"key":"e_1_2_2_50_1","volume-title":"Internet Security Threat Report","year":"2015"},{"key":"e_1_2_2_51_1","unstructured":"G. Tan M. Poletto J. Guttag and F. Kaashoek. 2003. Role classification of hosts within enterprise networks based on connection patterns. In USENIX General Track. 15--28. G. Tan M. Poletto J. Guttag and F. Kaashoek. 2003. Role classification of hosts within enterprise networks based on connection patterns. In USENIX General Track. 15--28."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70567-3_22"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2013.24"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73538-0_9"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314257.1314273"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1162\/089976600300015880"},{"key":"e_1_2_2_57_1","doi-asserted-by":"crossref","unstructured":"Y. Weiss. 2001. Comparing the mean field method and belief propagation for approximate inference in MRFs. Adv. Mean Field Methods Theor. Prac. (2001) 229--240. Y. Weiss. 2001. Comparing the mean field method and belief propagation for approximate inference in MRFs. Adv. Mean Field Methods Theor. Prac. (2001) 229--240.","DOI":"10.7551\/mitpress\/1100.003.0019"},{"key":"e_1_2_2_58_1","volume-title":"Proceedings of the Conference on Uncertainty in AI. 554--561","author":"Welling M."},{"key":"e_1_2_2_59_1","volume-title":"Security Risk Management: Building an Information Security Risk Management Program from the Ground Up","author":"Wheeler E."},{"key":"e_1_2_2_60_1","unstructured":"WhiteHat Security. 2015. Website Security Statistics Report. Retrieved from https:\/\/info.whitehatsec.com\/rs\/whitehatsecurity\/images\/2015-Stats-Report.pdf. WhiteHat Security. 2015. Website Security Statistics Report. Retrieved from https:\/\/info.whitehatsec.com\/rs\/whitehatsecurity\/images\/2015-Stats-Report.pdf."},{"key":"e_1_2_2_61_1","volume-title":"Proceedings of the Internationa Conference on Dependable Systems and Networks. 211--220","author":"Xie P."},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1162\/08997660260028674"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2016.2516916"}],"container-title":["ACM Transactions on Privacy and Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105760","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3105760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:03Z","timestamp":1750217403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,31]]},"references-count":64,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3105760"],"URL":"https:\/\/doi.org\/10.1145\/3105760","relation":{},"ISSN":["2471-2566","2471-2574"],"issn-type":[{"value":"2471-2566","type":"print"},{"value":"2471-2574","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,31]]},"assertion":[{"value":"2016-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}