Microsoft Active Directory is the default security management system for Windows domain network. Both real cyber attacke

[answerhappygod]

Microsoft Active Directory is the default security management
system for Windows domain network. Both real cyber attackers and
defenders interpret the Active Directory environment as a directed
graph. The nodes are computers/accounts/security groups/etc. A
directed edge from node u to v means an attacker can gain
access from u to v via existing accesses or known exploits. We
use a directed graph G = (V,E) to describe an Active Directory
environment. We assume that there is an attacker, who has access to
a set of entry nodes in G (for example, the attacker mass spammed
the organisation using phishing emails and gained 5 accounts
already). We assume the goal of the attacker is to reach a
destination node called the Domain Admin (DA). The attacker attacks
by going through the edges in order to move from one of the entry
nodes to the destination.
We assign two probabilities to an edge. Edge e has:
A detection rate D(e): if an attacker uses e (attempts to access
it), then the probability of being detected is D(e). Once detected,
the attack ends.
A failure rate F (e): if an attacker uses e, then the
probability of failing to pass through e is F (e). Failure is
different from being detected. Failing an edge only means this edge
is not usable. The attacker can try some other edges or restart
from some other nodes to continue the attack. We assume that once
an attacker reaches a node. The attacker will forever have access
to this node. An attack essentially “grows” the set of nodes the
attacker has access to, until the set contains DA.
With probability 1 − D(e) − F (e), the attacker can pass through
e successfully.
Given a graph G with arbitrary splitting and non-splitting
nodes, given the detection/failure rates D(e) and F(e) for all e,
how can we derive the attacker’s optimal policy? The optimal policy
is the attacking plan that maximizes the attacker’s chance for
reaching DA before getting detected. We define a node to be a
non-splitting node if it has one out-going edges. We define a node
to be a splitting node if it has multiple out-going edges, we also
assume a splitting node’s out-degree is exactly 2. Let t be the
number of splitting nodes in the graph. If the attacker initially
has access to s entry nodes. Can you derive a fixed
parameter tractable algorithm for computing the attacker’s optimal
policy that is fixed parameter tractable with respect to s +
t? Again, for simplicity, you could assume that a
splitting node’s out-degree is exactly 2.