High-Order Graph Models and their Applications in Active Directory Security
Date
2025
Authors
Nguyen, Nhu Long
Editors
Advisors
Nguyen, Hung
Falkner, Nickolas
Falkner, Nickolas
Journal Title
Journal ISSN
Volume Title
Type:
Thesis
Citation
Statement of Responsibility
Conference Name
Abstract
Active Directory (AD) is a directory service for Windows domain networks, managing identity and access control within organizations. Given its widespread adoption— used by 90% of Fortune 500 companies—AD has become a primary target for cyberattacks. Recent studies indicate that over 50% of organizations have experienced AD-related breaches, with 82% of penetration tests successfully exploiting AD vulnerabilities. Despite the increasing frequency of AD attacks, the majority of existing defense solutions remain reactive, addressing threats only after they have been exploited. This reactive approach leaves organizations vulnerable, highlighting the need for defenses that mitigate attack vectors before adversaries exploit them. A major challenge in AD security is its complexity. AD environments can contain hundreds of thousands of users, computers, and groups with intricate permissions. Attack graphs have emerged as a crucial tool for modeling AD vulnerabilities, providing a structured representation of attack paths that adversaries could exploit. By applying security algorithms to these graphs, organizations can identify and eliminate high-risk attack paths to protect critical assets. However, the effectiveness of these defense strategies is inherently limited by the quality of the underlying AD data. Due to the sensitive nature of ADs, few real-world datasets are publicly available, and existing generative tools fail to produce realistic AD attack graphs. As a result, security research often relies on overly simplistic models that do not accurately reflect how AD is constructed in real-world environments, potentially leading to ineffective mitigation strategies. Additionally, conventional attack graph representations follow a node-tonode mapping model, where security relationships are depicted as directed edges, and an edge connects two nodes, representing individual entities. While intuitive, this model does not accurately capture how AD permissions are structured in practice. Real-world access control applies to sets of objects, not individual nodes. Failure to account for this high-order structure involving sets leads to an explosion in graph size with edges connecting individual nodes, dramatically increasing the computational complexity of security algorithms. This inefficiency is particularly problematic in large-scale AD environments, where rapid response to threats is critical and defenders are constrained by a limited number of edges they can remove to minimize the traversability of attackers to high-value assets. To address these limitations, this thesis introduces two key contributions. First, it proposes a generative model for constructing realistic AD attack graphs based on the inherent design principles and security guidelines of realistic AD systems. This generative model enables security researchers to evaluate defense strategies on representative data, bridging the gap between theoretical security measures and real-world applicability. Second, the thesis presents a novel high-order graph model for security permissions, optimizing defense strategies in eliminating attack sources, especially under cyber emergencies. In addition, this thesis proposes the α-Spiral Algorithm, an enhancement on the state-of-the-art Spiral Algorithm in eliminating attack sources in Active Directory. The mathematical proof and extensive experiments show that the proposed graph model, in conjunction with the α-Spiral Algorithm, achieves greater elimination of attack sources while reducing computational overhead compared to the conventional graph model and the original Spiral Algorithm.
School/Discipline
School of Computer and Mathematical Sciences
Dissertation Note
Thesis (MPhil) -- University of Adelaide, School of Computer and Mathematical Sciences, 2025
Provenance
This electronic version is made publicly available by the University of Adelaide in accordance with its open access policy for student theses. Copyright in this thesis remains with the author. This thesis may incorporate third party material which has been used by the author pursuant to Fair Dealing exceptions. If you are the owner of any included third party copyright material you wish to be removed from this electronic version, please complete the take down form located at: http://www.adelaide.edu.au/legals