{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T15:40:02Z","timestamp":1756482002453,"version":"3.44.0"},"reference-count":81,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>Active Directory (AD) is the default security management system for Windows domain networks. An AD environment can be described as a cyber-attack graph, with nodes representing computers, accounts, and so forth, and edges indicating existing accesses or known exploits that enable attackers to move from one node to another. This article explores a Stackelberg game model between one attacker and one defender on an AD attack graph. The attacker\u2019s goal is to maximize their chances of successfully reaching the destination before getting detected. The defender\u2019s aim is to block a constant number of edges to minimize the attacker\u2019s chance of success. The article shows that the problem is #P-hard and, therefore, intractable to solve exactly. To defend the AD graph from cyberattackers, this article proposes two defensive approaches. In the first approach, we convert the attacker\u2019s problem to an exponential-sized Dynamic Program that is approximated by a neural network (NN). Once trained, the NN serves as an efficient fitness function for defender\u2019s Evolutionary Diversity Optimization-based defensive policy. The diversity emphasis on the defender\u2019s solution provides a diverse set of training samples, improving the training accuracy of our NN for modeling the attacker. In the second approach, we propose a RL-based policy to solve the attacker\u2019s problem and Critic network-assisted Evolutionary Diversity Optimization-based defensive policy to solve defender\u2019s problem. Experimental results on synthetic AD graphs show that the proposed defensive policies are scalable, highly effective, approximate attacker\u2019s problem accurately and generate good defensive plans.<\/jats:p>","DOI":"10.1145\/3688401","type":"journal-article","created":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T09:39:50Z","timestamp":1723455590000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Hardening Active Directory Graphs via Evolutionary Diversity Optimization-based Policies"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8212-8793","authenticated-orcid":false,"given":"Diksha","family":"Goel","sequence":"first","affiliation":[{"name":"CSIRO\u2019s Data61, Clayton, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9114-7339","authenticated-orcid":false,"given":"Max","family":"Ward","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Software Engineering, University of Western Australia, Perth, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0036-4782","authenticated-orcid":false,"given":"Aneta","family":"Neumann","sequence":"additional","affiliation":[{"name":"School of Computer and Mathematical Sciences, University of Adelaide, Adelaide, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2721-3618","authenticated-orcid":false,"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[{"name":"School of Computer and Mathematical Sciences, University of Adelaide, Adelaide, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1028-920X","authenticated-orcid":false,"given":"Hung","family":"Nguyen","sequence":"additional","affiliation":[{"name":"School of Computer and Mathematical Sciences, University of Adelaide, Adelaide, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3478-9201","authenticated-orcid":false,"given":"Mingyu","family":"Guo","sequence":"additional","affiliation":[{"name":"School of Computer and Mathematical Sciences, University of Adelaide, Adelaide, Australia"}]}],"member":"320","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"crossref","unstructured":"Majid Abdulsatar Hussain Ahmad Diksha Goel and Faheem Ullah. 2024. Towards deep learning enabled cybersecurity risk assessment for microservice architectures. arXiv:2403.15169. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.2403.15169","DOI":"10.1007\/s10586-024-05092-0"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3558001"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.3390\/s21041292"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.3390\/computers11030041"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2020.3031843"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCCEEE46830.2019.9070826"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.153.3731.34"},{"key":"e_1_3_2_9_1","volume":"2050","author":"Bellman Richard E.","year":"2015","unstructured":"Richard E. Bellman and Stuart E. Dreyfus. 2015. Applied Dynamic Programming, Vol. 2050. Princeton University Press.","journal-title":"Applied Dynamic Programming"},{"key":"e_1_3_2_10_1","first-page":"1","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Bello Irwan","year":"2017","unstructured":"Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. 2017. Neural combinatorial optimization with reinforcement learning. In Proceedings of the International Conference on Learning Representations, 1\u20135."},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449639.3459363"},{"key":"e_1_3_2_12_1","unstructured":"Greg Brockman Vicki Cheung Ludwig Pettersson Jonas Schneider John Schulman Jie Tang and Wojciech Zaremba. 2016. Openai gym. arXiv:1606.01540. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.1606.01540"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-control-042920-020211"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2972320"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2021.3073911"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2704781"},{"key":"e_1_3_2_17_1","volume-title":"A guide to microsoft active directory (ad) design","author":"Dias John","year":"2002","unstructured":"John Dias. 2002. A guide to microsoft active directory (ad) design. Technical Report. Lawrence Livermore National Lab. (LLNL), Livermore, CA."},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-15-4095-0_2"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3561974"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377930.3389844"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629605"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSCI.2017.8285298"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-023-10562-9"},{"key":"e_1_3_2_24_1","unstructured":"Diksha Goel. 2023. Enhancing network resilience through machine learning-powered graph combinatorial optimization: Applications in cyber defense and information diffusion. arXiv:2310.10667. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.2310.10667"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-70879-4_17"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3583131.3590436"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3512290.3528729"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i9.21167"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i5.25701"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.23919\/CNSM50824.2020.9269092"},{"key":"e_1_3_2_31_1","unstructured":"Long He Geng Sun Dusit Niyato Hongyang Du Fang Mei Jiawen Kang M\u00e9rouane Debbah and Zhu Han. 2024. Generative AI for game theory-based mobile networking. arXiv:2404.09699. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.2404.09699"},{"key":"e_1_3_2_32_1","first-page":"372","volume-title":"Proceedings of the AAAI","volume":"5","author":"Hebrard Emmanuel","year":"2005","unstructured":"Emmanuel Hebrard, Brahim Hnich, Barry O\u2019Sullivan, and Toby Walsh. 2005. Finding diverse and similar solutions in constraint programming. In Proceedings of the AAAI, Vol. 5, 372\u2013377."},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3205651.3208287"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SHPCC.1994.296728"},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2020.2995713"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2022.11.019"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622737.1622748"},{"issue":"2","key":"e_1_3_2_38_1","first-page":"37","article-title":"A comparative study of medical imaging techniques","volume":"4","author":"Kasban Hany","year":"2015","unstructured":"Hany Kasban, M. A. M. El-Bendary, and D. H. Salama. 2015. A comparative study of medical imaging techniques. International Journal of Information Science and Intelligent System 4, 2 (2015), 37\u201358.","journal-title":"International Journal of Information Science and Intelligent System"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90054-3"},{"key":"e_1_3_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.inffus.2022.03.003"},{"key":"e_1_3_2_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2019.100219"},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0062186"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11424-019-7420-0"},{"key":"e_1_3_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2021.3084827"},{"key":"e_1_3_2_45_1","unstructured":"Yen-Chen Lin Zhang-Wei Hong Yuan-Hong Liao Meng-Li Shih Ming-Yu Liu and Min Sun. 2017. Tactics of adversarial attack on deep reinforcement learning agents. arXiv:1703.06748. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.1703.06748"},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2023.101410"},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2022.03.037"},{"key":"e_1_3_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.2022.3143657"},{"key":"e_1_3_2_49_1","first-page":"780","article-title":"Evolutionary algorithms and neural networks","author":"Mirjalili Seyedali","year":"2019","unstructured":"Seyedali Mirjalili. 2019. Evolutionary algorithms and neural networks. Studies in Computational Intelligence 780 (2019), 43\u201353.","journal-title":"Studies in Computational Intelligence"},{"key":"e_1_3_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3512290.3528755"},{"key":"e_1_3_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3205455.3205532"},{"key":"e_1_3_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3321707.3321796"},{"key":"e_1_3_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3583131.3590405"},{"key":"e_1_3_2_54_1","first-page":"2517","volume-title":"Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS \u201923)","author":"Ngo Quang Huy","year":"2023","unstructured":"Quang Huy Ngo, Mingyu Guo, and Hung Nguyen. 2023. Near optimal strategies for honeypots placement in dynamic and large active directory networks. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS \u201923). Extended Abstract, 2517\u20132519."},{"key":"e_1_3_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3583131.3590517"},{"key":"e_1_3_2_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICMLA55696.2022.00213"},{"key":"e_1_3_2_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2021.3060483"},{"key":"e_1_3_2_58_1","doi-asserted-by":"crossref","unstructured":"Jeffrey R. Sampson. 1976. Adaptation in natural and artificial systems (John H. Holland).","DOI":"10.1137\/1018105"},{"key":"e_1_3_2_59_1","unstructured":"John Schulman Filip Wolski Prafulla Dhariwal Alec Radford and Oleg Klimov. 2017. Proximal policy optimization algorithms. arXiv:1707.06347. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.1707.06347"},{"key":"e_1_3_2_60_1","unstructured":"Shorya Sharma. 2021. Game theory for adversarial attacks and defenses. arXiv:2110.06166. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.2110.06166"},{"key":"e_1_3_2_61_1","first-page":"40","volume-title":"Proceedings of the 2020 IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC \u201920)","author":"Simoes David","year":"2020","unstructured":"David Simoes, Simao Reis, Nuno Lau, and Luis Paulo Reis. 2020. Competitive deep reinforcement learning over a pok\u00e9mon battling simulator. In Proceedings of the 2020 IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC \u201920). IEEE, 40\u201345."},{"key":"e_1_3_2_62_1","first-page":"2","volume-title":"Proceedings of the Machine Learning for Healthcare Conference.","author":"Tang Shengpu","year":"2021","unstructured":"Shengpu Tang and Jenna Wiens. 2021. Model selection for offline reinforcement learning: Practical considerations for healthcare settings. In Proceedings of the Machine Learning for Healthcare Conference. PMLR, 2\u201335."},{"key":"e_1_3_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/1830483.1830569"},{"key":"e_1_3_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2001576.2001665"},{"key":"e_1_3_2_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_3_2_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICGTSPICC.2016.7955308"},{"key":"e_1_3_2_67_1","volume-title":"Proceedings of the 2012 AAAI Spring Symposium Series","author":"Vorobeychik Yevgeniy","year":"2012","unstructured":"Yevgeniy Vorobeychik, Bo An, and Milind Tambe. 2012. Adversarial patrolling games. In Proceedings of the 2012 AAAI Spring Symposium Series."},{"key":"e_1_3_2_68_1","doi-asserted-by":"publisher","DOI":"10.1631\/FITEE.1900533"},{"key":"e_1_3_2_69_1","first-page":"16020","article-title":"Adversarial attack generation empowered by min-max optimization","volume":"34","author":"Wang Jingkang","year":"2021","unstructured":"Jingkang Wang, Tianyun Zhang, Sijia Liu, Pin-Yu Chen, Jiacen Xu, Makan Fardad, and Bo Li. 2021. Adversarial attack generation empowered by min-max optimization. Advances in Neural Information Processing Systems 34 (2021), 16020\u201316033.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_70_1","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Wang Yutong","year":"2021","unstructured":"Yutong Wang, Ke Xue, and Chao Qian. 2021. Evolutionary diversity optimization with clustering-based selection for reinforcement learning. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_71_1","doi-asserted-by":"publisher","DOI":"10.5555\/3586589.3586856"},{"key":"e_1_3_2_72_1","first-page":"1","article-title":"Adaptive attacker strategy development against moving target cyber defenses","author":"Winterrose Michael L.","year":"2020","unstructured":"Michael L. Winterrose, Kevin M. Carter, Neal Wagner, and William W. Streilein. 2020. Adaptive attacker strategy development against moving target cyber defenses. Advances in Cyber Security Analytics and Decision Systems (2020), 1\u201314.","journal-title":"Advances in Cyber Security Analytics and Decision Systems"},{"key":"e_1_3_2_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-90370-1_6"},{"key":"e_1_3_2_74_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i02.5531"},{"key":"e_1_3_2_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2015.2504420"},{"key":"e_1_3_2_76_1","first-page":"726","volume-title":"Proceedings of the Asian Conference on Machine Learning.","author":"Yang Feidiao","year":"2018","unstructured":"Feidiao Yang, Tiancheng Jin, Tie-Yan Liu, Xiaoming Sun, and Jialin Zhang. 2018. Boosting dynamic programming with neural networks for solving np-hard problems. In Proceedings of the Asian Conference on Machine Learning. PMLR, 726\u2013739."},{"key":"e_1_3_2_77_1","unstructured":"Yaodong Yang and Jun Wang. 2020. An overview of multi-agent reinforcement learning from game theoretical perspective. arXiv:2011.00583. Retrieved from https:\/\/doi.org\/10.48550\/arXiv.2011.00583"},{"key":"e_1_3_2_78_1","first-page":"6","volume-title":"Proceedings of the AAMAS","volume":"10","author":"Yin Zhengyu","year":"2010","unstructured":"Zhengyu Yin, Dmytro Korzhyk, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe. 2010. Stackelberg vs. Nash in security games: interchangeability, equivalence, and uniqueness. In Proceedings of the AAMAS, Vol. 10, 6."},{"key":"e_1_3_2_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477600"},{"issue":"1","key":"e_1_3_2_80_1","first-page":"301","article-title":"Genetic algorithms in search, optimization and machine learning","volume":"3","author":"Zames G.","year":"1981","unstructured":"G. Zames. 1981. Genetic algorithms in search, optimization and machine learning. Information Technology Journal 3, 1 (1981), 301.","journal-title":"Information Technology Journal"},{"key":"e_1_3_2_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319619.3326851"},{"key":"e_1_3_2_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3579856.3590343"}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3688401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T15:23:09Z","timestamp":1756480989000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3688401"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,29]]},"references-count":81,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1145\/3688401"],"URL":"https:\/\/doi.org\/10.1145\/3688401","relation":{},"ISSN":["2688-3007"],"issn-type":[{"type":"electronic","value":"2688-3007"}],"subject":[],"published":{"date-parts":[[2025,8,29]]},"assertion":[{"value":"2024-01-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-14","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}