REVIEW 3 major objections 4 minor 19 references
Adaptive Wizard for Removing Cross-Tier Misconfigurations in Active Directory
T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read The Adaptive Path Removal problem—a wizard proposing attack paths for an IT admin to trim—is #P-hard, yet a restricted dynamic-programming heuristic beats exact and approximation solvers on large Active Directory graphs.
desk verdict A novel, practically motivated problem formulation whose central theoretical claims—#P-hardness and the approximation guarantee—are not supported as written; the empirical work is solid but secondary. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the attack graph G=(V,E) with a confidence score conf(e) on each edge; when a simple s-t path p is proposed, the administrator removes edge e in p with probability conf(e) divided by the sum of confidences along p, the Bradley-Terry model. The argument runs through an MDP whose states are the histories of removed edges, whose actions are simple paths, and whose transitions are the Bradley-Terry probabilities. The exact algorithm OPT solves the Bellman equation u(s)=min_p{1+sum_e Phi(e|s,p)u(s\e)}; the approximation APP uses the adaptive-submodular utility g(s) that counts the number of root paths eliminated by removed edges and greedily maximizes expected marginal gain, yielding a (ln|P_sr|+1)^2 guarantee. DPR, the paper's main practical contribution, is OPT with a bounded lookahead B' and a tau-path sampling per state, cutting the subproblem count from O(|E|^B) to O($tau^{{B'}}$).
What would settle it
On a small graph built exactly as in Appendix 6.1, compute the optimal policy by exhaustive dynamic programming and check whether it ever proposes a path containing one of the B parallel high-confidence edges before the budget is exhausted, or whether the expected number of queries conditional on disconnecting s from t obeys Eq. (9). If either fails, the reduction's 50/50 gadget step does not hold and the equivalence to network reliability—and with it the #P-hardness proof—collapses.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that minimizing the expected number of human-admin interactions in adaptive path removal is computationally intractable: the optimization is #P-hard via a reduction from (s,t)-network reliability. Despite that hardness, the same adaptive structure that makes the problem hard can be exploited by a restricted dynamic program. The paper's DPR heuristic keeps the Bellman backup but limits the lookahead to B' rounds and samples τ candidate paths per state, and in experiments it achieves the same expected queries as the optimal policy on graphs where OPT can run, while scaling to graphs with over a hundred thousand nodes where OPT cannot. The paper also positions path proposals against binary edge queries: because a queried path forces the admin to remove at least one of its edges, a successful cut is guaranteed whenever the budget is large enough, which the binary-decision baseline does not offer.
Load-bearing premise
The hardness reduction assumes that at each step the wizard can isolate a single segment of the constructed graph so that the administrator picks the segment-disconnecting edge with probability one-half; if proposed paths must carry edges from several segments at once, the choice probability is split across them and the step-structure that makes the problem equivalent to network reliability falls apart.
Editorial extensions
If this is right
- The #P-hardness result means that no exact polynomial-time optimizer can be expected for APR, so deployments will rely on approximations or heuristics with guarantees like the (ln|P_sr|+1)^2 bound.
- Path-based proposals guarantee that, given a large enough budget, the process always terminates in a successful cut, which the binary edge-query baseline does not guarantee when admins retain too many edges.
- DPR's two restrictions—lookahead B'=4 and tau=16 sampled paths—allow it to run on graphs with 125,444 nodes and 1,195,432 edges, a scale the exact dynamic program cannot reach.
- On small graphs where the exact algorithm is runnable, DPR's expected query counts coincide with the optimal values, indicating the restrictions do not hurt in those cases.
Reading between the lines
- If the network-reliability reduction is sound, APR inherits not just hardness but a toolkit: Monte Carlo reliability estimators could seed DPR's candidate-path sampler and may reduce expected queries further than the fixed samplers the paper uses.
- The confidence scores are the organization's control knob; a classifier that predicts which misconfigurations are safe to remove would change the Bradley-Terry distribution, and DPR's advantage suggests even modest score improvements could translate into fewer admin interactions.
- DPR's performance with only 16 candidate paths suggests that path diversity, not exhaustive enumeration, drives its success; a natural test is a sensitivity sweep over tau and over the mix of sampling heuristics, which the paper fixes rather than tunes.
- The comparison with the binary edge-query baseline implies that the format of the question itself may change admin behavior; a behavioral study with real IT operators would put the Bradley-Terry assumption on firmer empirical ground.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the Adaptive Path Removal (APR) problem, in which an adaptive wizard iteratively proposes an s-t attack path and an IT administrator removes exactly one edge from the proposed path according to a Bradley-Terry choice model (Eq. 1), until s and t are disconnected or a query budget B is exhausted. The goal is to minimize the expected number of proposals. The authors claim APR is #P-hard (Theorem 1 / Theorem 5), propose an exact dynamic program (OPT), an adaptive-submodular greedy approximation (APP) with a claimed (ln|P_sr|+1)^2 guarantee (Theorem 4 / Theorem 6), and a scalable heuristic DPR, and they evaluate these on synthetic AD graphs and one real AD graph, reporting that DPR consistently outperforms all baselines.
Significance. If all claims were established, the paper would make a valuable contribution to human-in-the-loop Active Directory hardening: the path-proposal formulation is novel and practically motivated, the cut-guarantee property of path queries is a useful design choice, and the DPR heuristic appears to scale to large graphs. The paper also provides a breadth of experiments, including a real-world AD dataset. However, the central theoretical pillars are not supported: the #P-hardness proof in Appendix 6.1 is invalid, the strong adaptive submodularity proof required for the approximation guarantee is missing, and the empirical claims lack statistical support. As written, the paper does not establish its main results, so its significance remains potential rather than demonstrated.
major comments (3)
- [Appendix 6.1, Theorem 5, Eq. (9)] The #P-hardness reduction from (s,t)-network reliability is invalid. The proof claims that under the optimal policy a single gadget segment is presented alone and that the admin removes the ml-type edge with probability 1/2. However, every s-t path in the constructed graph must traverse at least one segment per original edge on an s-t route, so a path that contains no nh-type edge contains 2k low-confidence edges (one ml-type and one nl-type per segment). By Eq. (1), the probability that a particular ml-type edge is removed is 1/(2k), not 1/2, and outcomes across segments are not independent 50/50 trials. Consequently the identification of the expected query count with Rel(G) in Eq. (9) does not follow. Additionally, the text preceding Eq. (9) defines ψ_{I,π,s↔t} as the set of realizations where (s,t) 'remains connected,' but Eq. (9) multiplies this event by (1−Rel(G)) and treats it as the disconnected case; the notation is reversed. A new reduction or a substantially different argument would be required to establish #P-hardness.
- [Section 3.3 and Appendix 6.2, Theorem 6] The proof of Lemma 3 establishes only adaptive monotonicity and adaptive submodularity, not the strong adaptive monotonicity and strong adaptive submodularity required by Theorem 17 of Golovin and Krause (2011), which underlies Theorem 6. The manuscript explicitly states 'we admit the second property' for pointwise submodularity and defers the proof; Appendix 6.2 then asserts 'The utility function g is pointwise submodular' with no derivation. The claimed (ln|P_sr|+1)^2 approximation ratio for APP is therefore unsupported. This is a load-bearing gap because the approximation guarantee is a central contribution of the paper.
- [Section 4, Tables 1-3] The empirical claim that 'DPR consistently outperforms' baselines is not supported by the reported evidence. Table 2 reports only mean query counts over 16,000 trials without error bars, confidence intervals, or significance tests; many differences are extremely small (e.g., G1: APP 3.821 vs DPR 3.816; G2: APP 3.762 vs DPR 3.755). Table 3 compares LQGCT's RL model, which queries single edges with binary feedback, against DPR, which proposes paths with multiple-choice feedback; these are different interaction models, so the comparison does not isolate algorithm quality. The practical superiority claim therefore needs stronger statistical and methodological support.
minor comments (4)
- [Section 2.1] The definition of a simple path only forbids repeated edges, whereas a standard simple path also forbids repeated vertices; the intended definition should be clarified.
- [Section 4.1] The sentences 'We reserve a higher budget of 20 and 30 queries due to the size of this graph' and 'For the DPR algorithm, we set τ = 16 actions and a lookahead budget of B′ = 4 step' are duplicated in the text.
- [Appendix 6.2] The phrase 'we admit the proof' is likely a typo for 'we omit the proof,' and Definition 5 is labeled 'Strong Adaptive Monotonicity' but the displayed condition is identical to Definition 2; the definitions should be corrected.
- [Section 3.3] The sentence 'Although we have proven the former, we admit the second property for g' is unclear: 'admit' should probably be 'assert' or 'assume,' and the sentence should specify whether a proof appears in the appendix.
Circularity Check
No circularity: the #P-hardness reduction, APP approximation guarantee, and DPR heuristic comparisons are self-contained; noted issues are proof-correctness and model-evaluation concerns, not circular reasoning.
full rationale
The paper's three central claims (Theorem 1/5: APR is #P-hard; Theorem 4/6: APP is a (ln|Psr|+1)^2-approximation; DPR scalability and performance) do not reduce to their own inputs by construction. The #P-hardness proof constructs an APR instance from an (s,t)-network-reliability instance and attempts to read off Rel(G) from the optimal expected query count. The reduction has a nontrivial technical gap: the 'single segment is presented alone' step gives a 1/2 removal probability for the ml-type edge, but any s-t path in the constructed graph spans multiple gadget segments, so Eq. (1) spreads the removal probability over all low-confidence edges on the path. This is a proof-correctness risk, not a circularity: APR is not defined in terms of reliability, and Rel(G) is not used to define the APR parameters. The APP approximation guarantee is imported from the external adaptive-submodularity theorem of Golovin and Krause (2011); the utility g simply counts removed paths, and the monotonicity/submodularity verification is a direct check rather than a reuse of the target theorem. DPR is a restricted-lookahead dynamic program over a tau-path candidate set; its advantage over APP is reported as an empirical benchmark under the same Bradley-Terry simulator, and no parameter is fitted to the benchmark results to manufacture the prediction. Self-citations (e.g., Guo et al. 2024 LQGCT; Ngo et al. 2024) supply background and baselines and are not load-bearing for the main derivation. The evaluation is model-based in that Eq. (1) is both the planner's model and the simulator, which limits external validity but is not a circular derivation of the paper's claims. No exhibited circular step meets the quoted-evidence standard.
Assumptions & free parameters
free parameters (5)
- DPR lookahead budget B' =
4
- DPR candidate path count τ =
16
- Sampling top-k for DPR and RL =
k=4 for DPR, k=16 for RL
- Budget exhaustion penalty α =
not specified, constant > 0
- Edge confidence scores conf(e) =
not reported
assumptions (6)
- domain assumption IT admin choices follow the Bradley-Terry model with known confidence scores
- domain assumption AD attack graphs can be reduced to a single-source single-target graph by merging tier nodes
- ad hoc to paper In the #P-hardness construction, the optimal policy avoids high-confidence nh edges and each segment can be considered independently with 50/50 outcomes
- ad hoc to paper Strong adaptive submodularity of the coverage utility g, including pointwise submodularity
- standard math (s,t)-network reliability is #P-hard
- domain assumption ADSynth-generated graphs approximately match real AD structures
Cite this review
Pith. "Pith review of Adaptive Wizard for Removing Cross-Tier Misconfigurations in Active Directory." pith.science (2026). https://pith.science/paper/DZ4D4IKH
@misc{pith2026250501028,
author = {Pith},
title = {Pith review of: Adaptive Wizard for Removing Cross-Tier Misconfigurations in Active Directory},
year = {2026},
howpublished = {\url{https://pith.science/paper/DZ4D4IKH}},
note = {Machine review of arXiv:2505.01028}
}
abstract
Security vulnerabilities in Windows Active Directory (AD) systems are typically modeled using an attack graph and hardening AD systems involves an iterative workflow: security teams propose an edge to remove, and IT operations teams manually review these fixes before implementing the removal. As verification requires significant manual effort, we formulate an Adaptive Path Removal Problem to minimize the number of steps in this iterative removal process. In our model, a wizard proposes an attack path in each step and presents it as a set of multiple-choice options to the IT admin. The IT admin then selects one edge from the proposed set to remove. This process continues until the target $t$ is disconnected from source $s$ or the number of proposed paths reaches $B$. The model aims to optimize the human effort by minimizing the expected number of interactions between the IT admin and the security wizard. We first prove that the problem is $\mathcal{\#P}$-hard. We then propose a set of solutions including an exact algorithm, an approximate algorithm, and several scalable heuristics. Our best heuristic, called DPR, can operate effectively on larger-scale graphs compared to the exact algorithm and consistently outperforms the approximate algorithm across all graphs. We verify the effectiveness of our algorithms on several synthetic AD graphs and an AD attack graph collected from a real organization.
Figures
Reference graph
Works this paper leans on
-
[1]
Therefore, the following approximation ratio holds for Algorithm 1: q(π)≤q(π∗) (ln|Psr| + 1)2 (11) 6.8 Other Algorithm 6.8.1 Reinforcement Learning In this approach, we adopt a strategy similar to the DPR algorithm by limiting the action space to make the problem more manageable. However, instead of solving the problem optimally using Dynamic Programming,...
work page 2017
-
[2]
Huy Ngo, Mingyu Guo, and Hung Nguyen
https://www.microsoft.com/en-au/download/details.aspx?id=36036. Huy Ngo, Mingyu Guo, and Hung Nguyen. 2024a. Optimizing Cyber Response Time on Tempo- ral Active Directory Networks Using Decoys. In Proceedings of the Genetic and Evolutionary Computation Conference. 1309–1317. Huy Q Ngo, Mingyu Guo, and Hung Nguyen. 2024b. Catch Me if You Can: Effective Hon...
work page 2024
-
[5]
The APR problem is #P-hard. Proof. The proof is based on a reduction from the (s,t )- network reliability problem Ball (1986) which is #P-hard. PROBLEM: (s,t )-Network Reliability Problem • Input: A graphG = (V,E ), source nodes and destination nodet, probabilitype∈ [0, 1] associated with the present of each edge. • Question: What is the probability that ...
work page 1986
-
[6]
Algorithm 1 achieves a (ln|Psr| + 1)2-approximation for the APR problem withB = |Psr|. Proof. Applying Theorem 17 from Golovin and Krause (2011), the approximation ratio for the greedy algorithm, which maximizes marginal gain, is bounded by: c(π)≤αc(π∗) lnQ η + 1 2 (10) wherec(π) is the average cost of the greedy policy which isα-approximate w.r.t items c...
work page 2011
-
[7]
(Pointwise Submodular) A utility function g : S 7→ R≥0 A function g say to be pointwise submodular if g is submodular in every state for any realization ψ. Formally, function g is pointwise submodular if for all temporary state s and s′ such that ϕs ⊆ ϕs′ and for all e∈{e|e∈a,a∈As}, we haveg(s\e)−g(s)≥g(s′\e)−g(s′) As our definition of adaptive monotonici...
work page 2019
-
[8]
Hop-constrained st Simple Path Enumeration: Towards Bridging Theory and Practice. Proc. VLDB Endow.13, 4 (2019), 463–476. Andy Robbins
work page 2019
-
[9]
https://github.com/ BloodHoundAD/BloodHound
“Bloodhound: Six Degrees of domain admin. https://github.com/ BloodHoundAD/BloodHound. Accessed: 2022-08-02. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov
work page 2022
-
[10]
arXiv preprint arXiv:1707.06347 (2017)
Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017). Matthew W Short and Jason E Domagalski
arXiv 2017
Show all 19 references
-
[13]
arXiv preprint arXiv:2302.10261 (2023)
Deep reinforcement learning for cost-effective medical diagnosis. arXiv preprint arXiv:2302.10261 (2023). Yumeng Zhang, Max Ward, Mingyu Guo, and Hung Nguyen
2023 arXiv
-
[14]
The 18th ACM ASIA Conference on Computer and Communications Security (ACM ASIACCS) (2023)
A Scalable Double Oracle Algorithm for Hardening Large Active Directory Systems. The 18th ACM ASIA Conference on Computer and Communications Security (ACM ASIACCS) (2023). Yumeng Zhang, Max Ward, and Hung Nguyen
2023
-
[16]
adminaccount
In the experiment, for each of algorithm, we will report the result of the sampling scheme that yield the highest performance for each algorithm. 6.10 Data collection and preprocessing for the ORG graph The data was collected from an anonymous organization using SharpHound Vaz...
2019
-
[1986]
Ieee transactions on reliability 35, 3 (1986), 230–239
Computational complexity of network reliability analysis: An overview. Ieee transactions on reliability 35, 3 (1986), 230–239. Petros Christodoulou
1986
-
[2004]
Discrete Applied Mathe- matics 142, 1-3 (2004), 189–205
Sequential testing of complex systems: a review. Discrete Applied Mathe- matics 142, 1-3 (2004), 189–205. Rohan Vazarkar
2004
-
[2011]
Journal of Artificial Intelligence Research 42 (2011), 427–486
Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research 42 (2011), 427–486. Mingyu Guo, Jialiang Li, Aneta Neumann, Frank Neumann, and Hung Nguyen
2011
-
[2013]
American family physician 87, 2 (2013), 98–104
Iron deficiency anemia: evaluation and manage- ment. American family physician 87, 2 (2013), 98–104. Xiaorong Sun, Steve Y Chiu, and Louis Anthony Cox
2013
-
[2017]
Algorithmica 77 (2017), 661–685
Evaluation of monotone DNF formulas. Algorithmica 77 (2017), 661–685. Michael O Ball
2017
-
[2019]
arXiv preprint arXiv:1910.07207 (2019)
Soft actor-critic for discrete action settings. arXiv preprint arXiv:1910.07207 (2019). Amol Deshpande, Lisa Hellerstein, and Devorah Kletenik
2019 arXiv
-
[2023]
GECCO ’23: Genetic and Evolutionary Computation Conference, 2023, 2023 (2023)
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 (2023). Diksha Goel, Max Hector Ward-Graham, Aneta Neumann, Frank N...
2023
-
[2024]
(2024), 66–74
ADSynth: Synthesizing Realistic Active Directory Attack Graphs. (2024), 66–74. You Peng, Ying Zhang, Xuemin Lin, Wenjie Zhang, Lu Qin, and Jingren Zhou
2024
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.