{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T10:21:36Z","timestamp":1758709296856,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T00:00:00Z","timestamp":1644883200000},"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":["Digital Threats"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>As an analytical tool in cyber-security, an attack graph (AG) is capable of discovering multi-stage attack vectors on target computer networks. Cyber-physical systems (CPSs) comprise a special type of network that not only contains computing devices but also integrates components that operate in the continuous domain, such as sensors and actuators. Using AGs on CPSs requires that the system models and exploit patterns capture both token- and real-valued information. In this article, we describe a hybrid AG model for security analysis of CPSs and computer networks. Specifically, we focus on two issues related to applying the model in practice: efficient hybrid AG generation and techniques for information extraction from them. To address the first issue, we present an accelerated hybrid AG generator that employs parallel programming and high performance computing (HPC). We conduct performance tests on CPU and GPU platforms to characterize the efficiency of our parallel algorithms. To address the second issue, we introduce an analytical regimen based on centrality analysis and apply it to a hybrid AG generated for a target CPS system to discover effective vulnerability remediation solutions.<\/jats:p>","DOI":"10.1145\/3491257","type":"journal-article","created":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T18:44:36Z","timestamp":1634323476000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Strategies for Practical Hybrid Attack Graph Generation and Analysis"],"prefix":"10.1145","volume":"3","author":[{"given":"Ming","family":"Li","sequence":"first","affiliation":[{"name":"The University of Tulsa, Tulsa, OK"}]},{"given":"Peter","family":"Hawrylak","sequence":"additional","affiliation":[{"name":"The University of Tulsa, Tulsa, OK"}]},{"given":"John","family":"Hale","sequence":"additional","affiliation":[{"name":"The University of Tulsa, Tulsa, OK"}]}],"member":"320","published-online":{"date-parts":[[2022,2,15]]},"reference":[{"volume-title":"Apache Spark","year":"2020","key":"e_1_3_1_2_2","unstructured":"2020. Apache Spark. Wikipedia. Retrieved from https:\/\/en.wikipedia.org\/wiki\/Apache_Spark."},{"volume-title":"CVE-2019-19290","year":"2019","key":"e_1_3_1_3_2","unstructured":"2019. CVE-2019-19290. National Vulnerability Database. Retrieved from https:\/\/nvd.nist.gov\/vuln\/detail\/CVE-2019-19290."},{"volume-title":"CVE-2020-4785","year":"2020","key":"e_1_3_1_4_2","unstructured":"2020. CVE-2020-4785. National Vulnerability Database. Retrieved from https:\/\/nvd.nist.gov\/vuln\/detail\/CVE-2020-4785."},{"volume-title":"Robotic Operating System (ROS)","year":"2020","key":"e_1_3_1_5_2","unstructured":"2020. Robotic Operating System (ROS). ros.org. Retrieved from https:\/\/www.ros.org\/."},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2012.08.064"},{"key":"e_1_3_1_7_2","first-page":"1","volume-title":"Proceedings of the 1st ACM MobiHoc Workshop on Mobile IoT Sensing, Security, and Privacy","author":"Ghazo Alaa T. Al","year":"2018","unstructured":"Alaa T. Al Ghazo, Mariam Ibrahim, Hao Ren, and Ratnesh Kumar. 2018. A2G2V: Automated attack graph generator and visualizer. In Proceedings of the 1st ACM MobiHoc Workshop on Mobile IoT Sensing, Security, and Privacy. 1\u20136."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/586110.586140"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389013"},{"key":"e_1_3_1_10_2","first-page":"34","volume-title":"Proceedings of the International Conference on Science of Cyber Security","author":"Cao Ningyuan","year":"2018","unstructured":"Ningyuan Cao, Kun Lv, and Changzhen Hu. 2018. An attack graph generation method based on parallel computing. In Proceedings of the International Conference on Science of Cyber Security. Springer, 34\u201348."},{"key":"e_1_3_1_11_2","volume-title":"Proceedings of the 5th International Symposium for ICS & SCADA Cyber Security Research","author":"Depamelaere Wouter","year":"2018","unstructured":"Wouter Depamelaere, Laurens Lemaire, Jan Vossaert, and Vincent Naessens. 2018. CPS security assessment using automatically generated attack trees. In Proceedings of the 5th International Symposium for ICS & SCADA Cyber Security Research. British Computer Society (BCS)."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2017.09.017"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3307681.3326606"},{"key":"e_1_3_1_14_2","first-page":"215","volume-title":"Proceedings of the 4th Global Conference on Artificial Intelligence","author":"Gonda Tom","year":"2018","unstructured":"Tom Gonda, Tal Pascal, Rami Puzis, Guy Shani, and Bracha Shapira. 2018. Analysis of attack graph representations for ranking vulnerability fixes. In Proceedings of the 4th Global Conference on Artificial Intelligence. 215\u2013228."},{"key":"e_1_3_1_15_2","first-page":"1","volume-title":"Proceedings of the 43rd Annual IEEE\/IFIP Conference on Dependable Systems and Networks Workshop (DSN-W)","author":"Hong Jin B.","year":"2013","unstructured":"Jin B. Hong and Dong Seong Kim. 2013. Scalable security analysis in hierarchical attack representation model using centrality measures. In Proceedings of the 43rd Annual IEEE\/IFIP Conference on Dependable Systems and Networks Workshop (DSN-W). IEEE, 1\u20138."},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3297280.3297401"},{"issue":"1","key":"e_1_3_1_17_2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/TDSC.2010.61","article-title":"Extending attack graph-based security metrics and aggregating their application","volume":"9","author":"Idika Nwokedi","year":"2010","unstructured":"Nwokedi Idika and Bharat Bhargava. 2010. Extending attack graph-based security metrics and aggregating their application. IEEE Trans. Depend. Secure Comput. 9, 1 (2010), 75\u201385.","journal-title":"IEEE Trans. Depend. Secure Comput."},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACSAC.2006.39"},{"key":"e_1_3_1_19_2","first-page":"285","volume-title":"Algorithms, Architectures and Information Systems Security","author":"Jajodia Sushil","year":"2009","unstructured":"Sushil Jajodia and Steven Noel. 2009. Topological vulnerability analysis: A powerful new approach for network attack prevention, detection, and response. In Algorithms, Architectures and Information Systems Security. World Scientific, 285\u2013305."},{"issue":"5","key":"e_1_3_1_20_2","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1109\/TDSC.2015.2423682","article-title":"Distributed attack graph generation","volume":"13","author":"Kaynar Kerem","year":"2015","unstructured":"Kerem Kaynar and Fikret Sivrikaya. 2015. Distributed attack graph generation. IEEE Trans. Depend. Secure Comput. 13, 5 (2015), 519\u2013532.","journal-title":"IEEE Trans. Depend. Secure Comput."},{"key":"e_1_3_1_21_2","first-page":"174","volume-title":"Proceedings of the 2nd International Conference on Data Intelligence and Security (ICDIS)","author":"Li Ming","year":"2019","unstructured":"Ming Li, Peter Hawrylak, and John Hale. 2019. Concurrency strategies for attack graph generation. In Proceedings of the 2nd International Conference on Data Intelligence and Security (ICDIS). IEEE, 174\u2013179."},{"key":"e_1_3_1_22_2","first-page":"730","volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)","author":"Li Ming","year":"2020","unstructured":"Ming Li, Peter J. Hawrylak, and John Hale. 2020. Implementing an attack graph generator in CUDA. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 730\u2013738."},{"key":"e_1_3_1_23_2","first-page":"1","volume-title":"Proceedings of the International Conference for High-performance Computing, Networking, Storage and Analysis","author":"Liu Hang","year":"2015","unstructured":"Hang Liu and H. Howie Huang. 2015. Enterprise: Breadth-first graph traversal on GPUs. In Proceedings of the International Conference for High-performance Computing, Networking, Storage and Analysis. 1\u201312."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2602087.2602106"},{"key":"e_1_3_1_25_2","first-page":"2976","volume-title":"Proceedings of the 10th IEEE International Conference on Computer and Information Technology","author":"Ma Junchun","year":"2010","unstructured":"Junchun Ma, Yongjun Wang, Jiyin Sun, and Xiaofeng Hu. 2010. A scalable, bidirectional-based search strategy to generate attack graphs. In Proceedings of the 10th IEEE International Conference on Computer and Information Technology. IEEE, 2976\u20132981."},{"issue":"8","key":"e_1_3_1_26_2","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1145\/2370036.2145832","article-title":"Scalable GPU graph traversal","volume":"47","author":"Merrill Duane","year":"2012","unstructured":"Duane Merrill, Michael Garland, and Andrew Grimshaw. 2012. Scalable GPU graph traversal. ACM SIGPLAN Not. 47, 8 (2012), 117\u2013128.","journal-title":"ACM SIGPLAN Not."},{"key":"e_1_3_1_27_2","article-title":"Efficient attack graph analysis through approximate inference","author":"Munoz-Gonzalez Luis","year":"2016","unstructured":"Luis Munoz-Gonzalez, Daniele Sgandurra, Andrea Paudice, and Emil C. Lupu. 2016. Efficient attack graph analysis through approximate inference. arXiv preprint arXiv:1606.07025. (2016).","journal-title":"arXiv preprint arXiv:1606.07025."},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1180405.1180446"},{"key":"e_1_3_1_29_2","first-page":"71","volume-title":"Proceedings of the Workshop on New Security Paradigms","author":"Phillips Cynthia","year":"1998","unstructured":"Cynthia Phillips and Laura Painton Swiler. 1998. A graph-based system for network-vulnerability analysis. In Proceedings of the Workshop on New Security Paradigms. 71\u201379."},{"key":"e_1_3_1_30_2","first-page":"18","volume-title":"Proceedings of the European Symposium on Research in Computer Security","author":"Sawilla Reginald E.","year":"2008","unstructured":"Reginald E. Sawilla and Xinming Ou. 2008. Identifying critical attack assets in dependency attack graphs. In Proceedings of the European Symposium on Research in Computer Security. Springer, 18\u201334."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/829514.830526"},{"key":"e_1_3_1_32_2","volume-title":"Minimization and Reliability Analysis of Attack Graphs","author":"Sheyner S. Jha, O.","year":"2002","unstructured":"S. Jha, O. Sheyner, and J Wing. 2002. Minimization and Reliability Analysis of Attack Graphs. Technical Report. Technical Report CMU-CS-2-109, Carnegie Mellon University."},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2018.2805690"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851145"}],"container-title":["Digital Threats: Research and Practice"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491257","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3491257","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:19Z","timestamp":1750183759000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,15]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3491257"],"URL":"https:\/\/doi.org\/10.1145\/3491257","relation":{},"ISSN":["2692-1626","2576-5337"],"issn-type":[{"type":"print","value":"2692-1626"},{"type":"electronic","value":"2576-5337"}],"subject":[],"published":{"date-parts":[[2022,2,15]]},"assertion":[{"value":"2020-12-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-07","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}