Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs
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 a small tree width. 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.
Code (0)
등록된 구현이 없습니다.
Tasks
ManagementTree DecompositionSimilar Papers 제목 키워드 기반
ShieldNets: Defending Against Adversarial Attacks Using Probabilistic Adversarial Robustness
Defending adversarial attack is a critical step towards reliable deployment of deep learning empowered solutions for industrial applications. Probabilistic adversarial robustness (PAR), as a theoretical framework, is int…
Adversarial AttackAdversarial RobustnessDefending against Adversarial Attack towards Deep Neural Networks via Collaborative Multi-task Training
Deep neural networks (DNNs) are known to be vulnerable to adversarial examples which contain human-imperceptible perturbations. A series of defending methods, either proactive defence or reactive defence, have been propo…
Adversarial AttackContinuous Time Analysis of Momentum Methods
Gradient descent-based optimization methods underpin the parameter training of neural networks, and hence comprise a significant component in the impressive test results found in a number of applications. Introducing sto…
Does Differential Privacy Prevent Backdoor Attacks in Practice?
Differential Privacy (DP) was originally developed to protect privacy. However, it has recently been utilized to secure machine learning (ML) models from poisoning attacks, with DP-SGD receiving substantial attention. Ne…
Defending with Shared Resources on a Network
In this paper we consider a defending problem on a network. In the model, the defender holds a total defending resource of R, which can be distributed to the nodes of the network. The defending resource allocated to a no…