{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T18:36:00Z","timestamp":1783362960103,"version":"3.54.6"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,3,9]],"date-time":"2015-03-09T00:00:00Z","timestamp":1425859200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2015,3,27]]},"abstract":"<jats:p>The National Vulnerability Database (NVD) maintained by the US National Institute of Standards and Technology provides valuable information about vulnerabilities in popular software, as well as any patches available to address these vulnerabilities. Most enterprise security managers today simply patch the most dangerous vulnerabilities\u2014an adversary can thus easily compromise an enterprise by using less important vulnerabilities to penetrate an enterprise. In this article, we capture the vulnerabilities in an enterprise as a Vulnerability Dependency Graph (VDG) and show that attacks graphs can be expressed in them. We first ask the question: What set of vulnerabilities should an attacker exploit in order to maximize his expected impact? We show that this problem can be solved as an integer linear program. The defender would obviously like to minimize the impact of the worst-case attack mounted by the attacker\u2014but the defender also has an obligation to ensure a high productivity within his enterprise. We propose an algorithm that finds a Pareto-optimal solution for the defender that allows him to simultaneously maximize productivity and minimize the cost of patching products on the enterprise network. We have implemented this framework and show that runtimes of our computations are all within acceptable time bounds even for large VDGs containing 30K edges and that the balance between productivity and impact of attacks is also acceptable.<\/jats:p>","DOI":"10.1145\/2699907","type":"journal-article","created":{"date-parts":[[2015,3,9]],"date-time":"2015-03-09T19:03:01Z","timestamp":1425927781000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":39,"title":["Pareto-Optimal Adversarial Defense of Enterprise Systems"],"prefix":"10.1145","volume":"17","author":[{"given":"Edoardo","family":"Serra","sequence":"first","affiliation":[{"name":"University of Maryland, College Park,MD20742, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sushil","family":"Jajodia","sequence":"additional","affiliation":[{"name":"George Mason University, Fairfax, VA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrea","family":"Pugliese","sequence":"additional","affiliation":[{"name":"University of Calabria, Italia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antonino","family":"Rullo","sequence":"additional","affiliation":[{"name":"University of Calabria, Italia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"V. S.","family":"Subrahmanian","sequence":"additional","affiliation":[{"name":"University of Maryland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,3,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 10th International Conference on Security and Cryptpgraphy (SECRYPT)","author":"Albanese Massimiliano","year":"2013","unstructured":"Massimiliano Albanese , Sushil Jajodia , Anoop Singhal , and Lingyu Wang . 2013 . An efficient approach to assessing the risk of zero-day vulnerabilities . In Proceedings of the 10th International Conference on Security and Cryptpgraphy (SECRYPT) . Reykjavik, Iceland. Massimiliano Albanese, Sushil Jajodia, Anoop Singhal, and Lingyu Wang. 2013. An efficient approach to assessing the risk of zero-day vulnerabilities. In Proceedings of the 10th International Conference on Security and Cryptpgraphy (SECRYPT). Reykjavik, Iceland."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2010.146"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1689499.1689572"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/586110.586140"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.46.3.316"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056602"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1315245.1315272"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10207-012-0160-y"},{"key":"e_1_2_1_10_1","volume-title":"How to create and deploy a successful patch management policy and program","author":"Foret Felix","year":"2004","unstructured":"Felix Foret . 2004. How to create and deploy a successful patch management policy and program . SANS Institute ( 2004 ). Felix Foret. 2004. How to create and deploy a successful patch management policy and program. SANS Institute (2004)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1689499.1689536"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/MILCOM.2011.6127490"},{"key":"e_1_2_1_13_1","volume-title":"Managing Cyber Threats: Issues, Approaches, and Challenges. Massive Computing","author":"Jajodia Sushil","unstructured":"Sushil Jajodia , Steven Noel , and Brian O\u2019Berry . 2005. Managing Cyber Threats: Issues, Approaches, and Challenges. Massive Computing , Vol. 5 . Springer , Chapter Topological Analysis of Network Attack Vulnerability, 247--266. Sushil Jajodia, Steven Noel, and Brian O\u2019Berry. 2005. Managing Cyber Threats: Issues, Approaches, and Challenges. Massive Computing, Vol. 5. Springer, Chapter Topological Analysis of Network Attack Vulnerability, 247--266."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/794201.795177"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90065-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.833358"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209042"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2480741.2480742"},{"key":"e_1_2_1_19_1","volume-title":"Version 2.0","author":"Mell Peter","year":"2005","unstructured":"Peter Mell , Tiffany Bergeron , and David Henning . 2005. Creating a patch and vulnerability management program. NIST Special Publication 800-40 , Version 2.0 ( 2005 ). Peter Mell, Tiffany Bergeron, and David Henning. 2005. Creating a patch and vulnerability management program. NIST Special Publication 800-40, Version 2.0 (2005)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2006.145"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00158-002-0276-1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0561-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSAC.2004.11"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.815323"},{"key":"e_1_2_1_25_1","volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","unstructured":"Christos H. Papadimitriou . 1994. Computational Complexity . Addison-Wesley . I--XV, 1--523 pages. Christos H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley. I--XV, 1--523 pages."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/310889.310919"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2011.34"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/597917.597926"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/4236.978369"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 2000 IEEE Symposium on Research on Security and Privacy (S&P","author":"Ronald","year":"2000","unstructured":"Ronald W. Ritchey and Paul Ammann. 2000. Using model checking to analyze network vulnerabilities . In Proceedings of the 2000 IEEE Symposium on Research on Security and Privacy (S&P 2000 ). Berkeley, CA, USA, 156--165. Ronald W. Ritchey and Paul Ammann. 2000. Using model checking to analyze network vulnerabilities. In Proceedings of the 2000 IEEE Symposium on Research on Security and Privacy (S&P 2000). Berkeley, CA, USA, 156--165."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/829514.830526"},{"key":"e_1_2_1_32_1","volume-title":"Gnutella peer to peer network from","author":"Network Dataset Collection Stanford Large","year":"2002","unstructured":"Stanford Large Network Dataset Collection . 2014. Gnutella peer to peer network from August 4, 2002 . http:\/\/snap.stanford.edu\/data\/p2p-Gnutella04.html. (2014). Stanford Large Network Dataset Collection. 2014. Gnutella peer to peer network from August 4, 2002. http:\/\/snap.stanford.edu\/data\/p2p-Gnutella04.html. (2014)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/DISCEX.2001.932182"},{"key":"e_1_2_1_34_1","unstructured":"Tenable Network Security\u00ae. 2014. The Nessus\u00ae vulnerability scanner. http:\/\/www.tenable.com\/products\/nessus. (2014).  Tenable Network Security\u00ae. 2014. The Nessus\u00ae vulnerability scanner. http:\/\/www.tenable.com\/products\/nessus. (2014)."},{"key":"e_1_2_1_35_1","unstructured":"The MITRE Corporation. 2011. Common Weakness Scoring System (CWSS\u2122). http:\/\/cwe.mitre.org\/cwss\/. (June 2011). Version 0.8.  The MITRE Corporation. 2011. Common Weakness Scoring System (CWSS\u2122). http:\/\/cwe.mitre.org\/cwss\/. (June 2011). Version 0.8."},{"key":"e_1_2_1_36_1","volume-title":"Market Structure and Equilibrium","author":"von Stackelberg Heinrich","unstructured":"Heinrich von Stackelberg , Damien Bazin , Rowland Hill , and Lynn Urch . 2010. Market Structure and Equilibrium . Springer . Heinrich von Stackelberg, Damien Bazin, Rowland Hill, and Lynn Urch. 2010. Market Structure and Equilibrium. Springer."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2006.04.001"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2006.06.018"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 6th USENIX Security Symposium","author":"Zerkle Dan","year":"1996","unstructured":"Dan Zerkle and Karl Levitt . 1996 . NetKuang - A multi-host configuration vulnerability checker . In Proceedings of the 6th USENIX Security Symposium . San Jose, CA, USA. Dan Zerkle and Karl Levitt. 1996. NetKuang - A multi-host configuration vulnerability checker. In Proceedings of the 6th USENIX Security Symposium. San Jose, CA, USA."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2009.5399894"},{"key":"e_1_2_1_41_1","volume-title":"Game-theoretic analysis of node capture and cloning attack with multiple attackers in wireless sensor networks","author":"Zhu Quanyan","unstructured":"Quanyan Zhu , Linda Bushnell , and Tamer Basar . 2012a. Game-theoretic analysis of node capture and cloning attack with multiple attackers in wireless sensor networks . In CDC. IEEE , 3404--3411. Quanyan Zhu, Linda Bushnell, and Tamer Basar. 2012a. Game-theoretic analysis of node capture and cloning attack with multiple attackers in wireless sensor networks. In CDC. IEEE, 3404--3411."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2012.121214"},{"key":"e_1_2_1_43_1","volume-title":"A stochastic game model for jamming in multi-channel cognitive radio systems","author":"Zhu Quanyan","unstructured":"Quanyan Zhu , Husheng Li , Zhu Han , and Tamer Basar . 2010. A stochastic game model for jamming in multi-channel cognitive radio systems . In ICC. IEEE , 1--6. Quanyan Zhu, Husheng Li, Zhu Han, and Tamer Basar. 2010. A stochastic game model for jamming in multi-channel cognitive radio systems. In ICC. IEEE, 1--6."}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699907","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2699907","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:59Z","timestamp":1750227419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699907"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,9]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,3,27]]}},"alternative-id":["10.1145\/2699907"],"URL":"https:\/\/doi.org\/10.1145\/2699907","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"value":"1094-9224","type":"print"},{"value":"1557-7406","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,9]]},"assertion":[{"value":"2014-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}