Algorithmic Game Theory and Cyber SecurityDirector: Dr Mingyu Guo
Application: Defending Active Directory Windows Domain NetworksTechniques: Fixed Parameter Analysis, Stackelberg Game, Graph Neural Network, Reinforcement Learning
Active Directory (AD) is the default security management system for Windows domain networks, which is used by most large organisations world wide including our own university. An AD environment naturally describes a cyber attack graph where nodes represent computers, user accounts, groups, etc. and (directed) edges represent accesses/known exploits. I.e., an edge from node A to computer B represents that an attacker with access of A can gain access to B. There are many open source/commericial tools for generating/analysing/visualizing AD graphs and these tools are used by real attackers for attack planning (i.e., BloodHound is a popular tool for generating "shortest attack paths") and used by real defenders for defence planning (often involves cleanning up unnecessary accesses that are potentially exploitable by the attackers).
We formulate the AD defence problem as Stackelberg games (on graphs) between attackers and defenders. We exploit the structural features of practical AD graphs to design scalable defence algorithms. Example structural features include 1) attack paths tend to be short, which is similar to the observation from the Small World Experiment (i.e., every two individuals in the world are within six social connections); 2) practical AD graphs are similar to trees, where the tree roots are the Domain Admin nodes (i.e., nodes with the highest priviledge). We apply fixed parameter analysis to design scalable algorithms that can handle large graphs with tens of thousands of nodes.
Often, fixed parameter analysis alone is not enough to achieve practical scalability. We combine the strength of theoretical analysis and optimisation techniques like mixed integer programming, evolutionary computation, graph neural networks, reinforcement learning to achieve maximal scalability.
- Mingyu Guo, Max Ward, Aneta Neumann, Frank Neumann, Hung Nguyen. Scalable Edge Blocking Algorithms for Defending Active Directory Style Attack Graphs. The 37th AAAI Conference on Artificial Intelligence (AAAI), Washington DC, USA, 2023, 2023.
- Diksha Goel, Aneta Neumann, Frank Neumann, Hung Nguyen, Mingyu Guo. Evolving Reinforcement Learning Environment to Minimize Learner's Achievable Reward: An Application on Hardening Active Directory Systems. GECCO '23: Genetic and Evolutionary Computation Conference, 2023, 2023.
- (Extended Abstract) Quang Huy Ngo, Mingyu Guo, Hung Nguyen. Near Optimal Strategies for Honeypots Placement in Dynamic and Large Active Directory Networks. The 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2023.
- Mingyu Guo, Jialiang Li, Aneta Neumann, Frank Neumann, Hung Nguyen. Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs. The 36th AAAI Conference on Artificial Intelligence (AAAI), Vancouver, Canada, 2022, 2022.
- Diksha Goel, Max Hector Ward-Graham, Aneta Neumann, Frank Neumann, Hung Nguyen, Mingyu Guo. Defending Active Directory by Combining Neural Network Based Dynamic Program and Evolutionary Diversity Optimisation. GECCO '22: Genetic and Evolutionary Computation Conference, 2022, 2022.
Mechanism Design via Neural Networks
Mechanism design deals with economic systems involving multiple agents. A mechanism is a set of rules that map the agents’ preferences to social decisions. For example, a school allocation mechanism maps the students’ preferences over schools to an assignment of students to schools. Sometimes, the decision also involves payments. For example, an Internet advertisement auction mechanism maps the advertisers’ preferences over different advertising slots to an arrangement of the advertisements, as well as some corresponding payments. Mechanism design studies how to design mechanism rules that optimize certain objective while enforcing certain constraints. Typical objectives include welfare maximization and revenue maximization. A typical constraint is that the mechanism should encourage truthful reporting. It should be noted that the mechanism makes decisions based on the agents’ reported preferences, so a manipulative agent may lie about his preference in order to reach a better social decision for himself, which may be bad for the others. A truthful mechanism ensures that under its rules, no agents can benefit by misreporting.
Traditionally, economists have designed mechanisms manually. Automated mechanism design aims to automate the mechanism design process using computational techniques. The basic idea is to model the design process as a functional optimization problem. Essentially, if we express the agents’ preferences and the possible social decisions using numeric terms, then a mechanism is just a complex function whose domain and range are both multi-dimensional. This view of mechanism design motivates the application of neural networks toward mechanism design.
Neural network based mechanism design imposes unique challenges. For some models, the optimal mechanisms involve iterative binary decisions, which makes gradient computation challenging. One idea we proposed is to "hard code" the analytical commutative density function of the agents' prior distribution into the cost function to derive high-quality gradients. For worst-case design objective, evaluating a neural network's worst-case performance is not scalable, so we are restricted to tiny networks that are often difficult to train. One idea we proposed is to rely on the Lottery Ticket Hypothesis to guide a systematic search process for tiny trainable networks.
- Mingyu Guo. Worst-Case VCG Redistribution Mechanism Design Based on the Lottery Ticket Hypothesis. Working paper, 2023.
- Guanhua Wang, Runqi Guo, Yuko Sakurai, Muhammad Ali Babar, Mingyu Guo. Mechanism Design for Public Projects via Neural Networks. AAMAS '21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021, Pages 1380--1388, 2021.
- Mingyu Guo. An Asymptotically Optimal VCG Redistribution Mechanism for the Public Project Problem. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, Pages 315--321, 2019.