Home Events AI-based Optimisation Seminar Series 16 Mar 2022


Mar 16 2022


4:00 pm - 5:00 pm



AI-based Optimisation Seminar Series 16 Mar 2022

Speaker: Dr Mingyu Guo

Title: Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs

Synopsis: Active Directory is the default security management system for Windows domain networks. We study the shortest path edge interdiction problem for defending Active Directory style attack graphs. The problem is formulated as a Stackelberg game between one defender and one attacker. The attack graph contains one destination node and multiple entry nodes. The attacker’s entry node is chosen by nature. The defender chooses to block a set of edges limited by his budget. The attacker then picks the shortest unblocked attack path. The defender aims to maximize the expected shortest path length for the attacker, where the expectation is taken over entry nodes.

We observe that practical Active Directory attack graphs have small maximum attack path lengths and are structurally close to trees. We first show that even if the maximum attack path length is a constant, the problem is still W[1]-hard with respect to the defender’s budget. Having a small maximum attack path length and a small budget is not enough to design fixed-parameter algorithms. If we further assume that the number of entry nodes is small, then we derive a fixed-parameter tractable algorithm.

We then propose two other fixed-parameter algorithms by exploiting the tree-like features. One is based on tree decomposition and requires small treewidth. The other assumes a small number of splitting nodes (nodes with multiple out-going edges). Finally, the last algorithm is converted into a graph convolutional neural network-based heuristic, which scales to larger graphs with more splitting nodes.

Bio: Dr Mingyu Guo is a Lecturer in the School of Computer Science, University of Adelaide, Australia. Guo’s research interests include algorithmic game theory, multiagent systems and cyber security applications. Prior to joining the University of Adelaide, Guo was a Lecturer at the University of Liverpool, UK. Guo received his PhD in Computer Science from Duke University, USA.


ZOOM Meeting ID: 873 1557 5255; Password: 778635

More Info

Zoom Link

The event is finished.


Mar 16 2022

Advancing an industry-ready optimisation toolkit, while training a new generation of industry practitioners and over 120 young researchers, who will vanguard a highly skilled workforce of change agents for industrial transformation.

Monash University
Clayton, Victoria, 3080

University of Melbourne
Parkville, Victoria, 3010

© 2021 ARC Industrial Transformation Training Centre in Optimisation Technologies, Integrated Methodologies and Applications (OPTIMA)