{"id":"e95f9181-da48-4c84-a3b6-7631db822110","arxiv_id":"2505.01028","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"The paper introduces the Adaptive Path Removal problem for Active Directory attack graphs, claims #P-hardness, and shows a restricted dynamic programming heuristic outperforms the approximation algorithm on synthetic and real graphs.","lead":"This paper models Active Directory security hardening as an interactive game where a wizard proposes attack paths and an IT administrator deletes one connection per round. It proves the optimization problem is hard, and offers exact, approximate, and heuristic methods, with a heuristic called DPR winning the experiments.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The #P-hardness reduction in Appendix 6.1 assumes each gadget is queried in isolation; proposed s-t paths span multiple gadgets, so the admin's 50/50 per-segment choice is not valid and the equivalence to network reliability is unsupported.","rationale":"The reader's verdict is REJECT with moderate confidence, and I agree that the weakest point is the #P-hardness proof in Appendix 6.1. The reduction's per-gadget 50/50 step is not a harmless simplification: it is the only mechanism that connects each original edge's independent reliability failure to an APR query outcome. In the constructed graph, a query is an s-t path, not a gadget; when the path spans multiple original edges, the Bradley-Terry choice is spread over all low-confidence edges on that path, so the probability of removing a particular ml edge drops from 1/2 to 1/(2k). No argument in the appendix shows the optimal policy can restrict attention to one-segment paths; indeed, for a generic route of length k>1 it cannot. The notation reversal around s-t connectivity in Eq. (9) strengthens the impression that the reliability calculation is not derived carefully. The paper itself flags a second unsupported step: in Section 3.3 the authors state they 'admit' the pointwise submodularity needed for strong adaptive submodularity and defer it, but Appendix 6.2 only restates the condition rather than proving it, so Theorem 4's approximation guarantee is also not established. These theoretical gaps are load-bearing because the abstract and contributions present #P-hardness and the approximation guarantee as the justification for the heuristic approach. The empirical comparison may still be useful, but without a valid reduction the paper's central claims are not supported as written. I would keep the reader's REJECT verdict; the concern does not change it, but it confirms it.","tokens_in":17137,"tokens_out":8318,"duration_ms":91992,"concrete_test":"Instantiate the reduction on the smallest graph where the flaw is visible: G' with two serial edges s->a and a->t, so the reduced graph has two gadgets and a unique all-low s-t path of length 4 (ml, nl, ml, nl), with B=3 and high edges having confidence so large that any path containing one is never chosen for an ml/nl outcome. Solve the APR MDP exactly using Eq. (3); the state space is small enough for exhaustive dynamic programming. Compute the optimal expected query count. Independently compute the quantity predicted by the proof's Eq. (9) from the reliability of the two-edge serial graph, Rel(G')=1/4. If Eq. (9) holds for this instance, the proof's coupling assumption survives; if the numbers differ, the 50/50 isolation step fails and the reduction as written is invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central theoretical claim is Theorem 1/5: APR is #P-hard, reduced from (s,t)-network reliability in Appendix 6.1. The construction replaces each edge (u,v) of the reliability graph with a segment u -> uv -> v containing one ml edge (u->uv), one nl edge (uv->v), and B parallel nh edges (uv->v). The proof's key step says that under the optimal policy, a segment is presented alone, and the admin removes the ml edge with probability 1/2 and the nl edge with probability 1/2. This is where the argument breaks. In the constructed graph, any s-t path follows a route in the original graph and therefore traverses k segments, k>=1. If the path contains any nh edge, the admin, by the 'infinite confidence' assumption, chooses among the nh edges and no ml/nl information is gained; to get a chance of removing an ml edge, the path must consist of nl edges in every segment, giving 2k low-confidence edges on the path. Under Eq. (1), the probability that a particular ml edge is removed is 1/(2k), not 1/2. Consequently, the gadget outcomes are not independent 50/50 Bernoulli trials, and the identification of APR's expected query count with the reliability polynomial via Eq. (9) does not follow. The appendix also reverses its own notation: it sets the success event equal to the event that (s,t) 'remains connected,' and Eq. (9) attaches B*Rel(G) to the wrong event. A corrected reduction or a different argument would be needed to establish #P-hardness; as written, the theorem that motivates the approximate algorithms is unproven.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17503,"tokens_out":6793,"duration_ms":67567,"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":[{"comment":"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":"Appendix 6.1, Theorem 5, Eq. (9)"},{"comment":"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":"Section 3.3 and Appendix 6.2, Theorem 6"},{"comment":"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.","section":"Section 4, Tables 1-3"}],"minor_comments":[{"comment":"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":"Section 2.1"},{"comment":"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.","section":"Section 4.1"},{"comment":"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":"Appendix 6.2"},{"comment":"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.","section":"Section 3.3"}],"recommendation":"reject","confidential_remarks":"The manuscript itself signals the missing proof of strong adaptive submodularity by deferring it and then providing only a restatement in the appendix. Combined with the invalid #P-hardness reduction and the weak experimental evidence, the paper's central claims are not established. This is not a matter of presentation polish; the theoretical and empirical cores would need to be reworked and re-verified. I also note that the LQGCT comparison in Table 3 is between different problem models, which may mislead readers about the relative quality of the algorithms."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper introduces the Adaptive Path Removal (APR) problem: a wizard proposes an s-t attack path, and the IT admin selects one edge to remove according to a Bradley-Terry model. That is a real contribution. It extends the LQGCT edge-binary model to path-based multiple-choice queries, gives a cut guarantee by construction, and is clearly motivated by the security-team/IT-ops workflow. The DPR heuristic—bounded lookahead DP with path sampling—is a sensible practical recipe, and the evaluation on synthetic AD graphs plus a real 125k-node AD graph is more than many papers in this area do.\n\nBut the load-bearing theory does not hold up. The #P-hardness reduction in Appendix 6.1 assumes that under the optimal policy a single gadget segment is presented in isolation, so the admin removes the ml-type edge with probability 1/2. In the constructed graph, every s-t path traverses several segments. If it contains any high-confidence (nh) edge, the admin never touches the low-confidence edges; if it contains only low-confidence edges, there are 2k of them, and a given ml edge is selected with probability 1/(2k), not 1/2. The gadget outcomes are not independent 50/50 trials, so the link to network reliability in Eq. (9) is unsupported. The theorem that motivates all the approximations is therefore unproven as written.\n\nThe strong adaptive submodularity needed for the APP approximation guarantee is also asserted, not demonstrated. The appendix defines pointwise submodularity and then hand-waves that g satisfies it. That is a second gap in the theory. There are also smaller issues: the appendix says DPR results on ORG were not obtained while Table 2 reports them; the LQGCT RL comparison in Table 3 compares two different query models, so the 'successful cuts' numbers are not commensurable; no error bars or code/data are provided, which matters because the DPR gains over APP are small (a few hundredths of a query).\n\nDo I think the paper is worthless? No. The APR problem is worth stating and studying, and the DPR heuristic may well be useful in practice. But the current manuscript's central theoretical claims need either a corrected reduction or a different hardness argument, and the submodularity proof needs to be written out. As is, I would not accept it, but I would send it to reviewers: they should see the problem statement and the experimental setup, and the authors deserve a chance to fix the theory.\n\nRecommendation: send to peer review, expect major revision. This is a paper for the AI/security community, not a general journal.","headline":"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.","tokens_in":18050,"tokens_out":4230,"would_cite":false,"duration_ms":39794,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Active Directory hardening","attack graph","adaptive path removal","Bradley-Terry model","network reliability","adaptive submodularity","dynamic programming heuristic"],"falsifier":"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.","tokens_in":16874,"feed_emoji":"🛡️","tokens_out":8350,"duration_ms":80178,"temperature":0.7,"pith_summary":"The paper introduces a human-in-the-loop model for removing attack paths in Windows Active Directory: a wizard proposes an s-t path, and an IT administrator removes exactly one edge of that path, chosen with probability proportional to the edge's confidence score. The goal is to minimize the expected number of these proposals before the target becomes unreachable or the query budget is spent. The paper proves that this Adaptive Path Removal problem is #P-hard, then offers an exact dynamic program, an adaptive-submodularity approximation, and a scalable heuristic (DPR) that restricts lookahead and candidate paths. On synthetic tier-based graphs and a real 125,444-node AD graph, DPR matches the exact optimum on small instances and outperforms the approximation and reinforcement-learning baselines on every larger graph. If the model holds, path-based proposals give a cut guarantee that single-edge binary queries lack, at the price of a harder optimization problem.","feed_headline":"Attack-path wizard cuts AD cleanup to fewer human steps","feed_subtitle":"Model proves the path-removal problem is #P-hard; a bounded-lookahead heuristic beats exact and approximation solvers on real AD graphs.","key_machinery":"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'}}$).","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the (s,t)-network reliability problem and its #P-hardness, which Theorem 5's reduction builds on.","marker":"Ball (1986)"},{"why":"Provides the adaptive-submodularity framework and greedy approximation bound behind Algorithm 1 and Theorem 4.","marker":"Golovin and Krause (2011)"},{"why":"Introduces AD attack-graph hardening and the iterative edge-removal workflow that APR extends with path proposals.","marker":"Dunagan et al. (2009)"},{"why":"Proposes active learning of which edges admins remove, the basis for assigning confidence scores in the Bradley-Terry model.","marker":"Zheng et al. (2011)"},{"why":"Defines LQGCT, the binary edge-query adaptive model that path proposals are designed to improve upon and are compared against.","marker":"Guo et al. (2024)"},{"why":"Supplies ADSynth, the synthetic AD attack-graph generator used to create the tier-based evaluation graphs.","marker":"Nguyen et al. (2024)"},{"why":"Provides SharpHound, the data-collection tool used to obtain the real 125,444-node ORG Active Directory graph.","marker":"Vazarkar (2019)"},{"why":"Gives the O(|V|^k) path-enumeration complexity used in the exact and DPR algorithms' complexity analysis.","marker":"Peng et al. (2019)"}],"fun_headline_variants":["Adaptive wizard trims AD cleanup to fewest admin decisions","Heuristic beats exact solver on real AD graphs, scales to 100k","Wizard cuts human effort in AD attack-path removal via smart queries","AD wizard minimizes admin steps, proving problem #P-hard","Bounded-lookahead wizard outperforms exact and approx AD solvers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive wizard trims AD cleanup to fewest admin decisions","Heuristic beats exact solver on real AD graphs, scales to 100k","Wizard cuts human effort in AD attack-path removal via smart queries","AD wizard minimizes admin steps, proving problem #P-hard","Bounded-lookahead wizard outperforms exact and approx AD solvers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000308,"raw_usage":{"total_tokens":1767,"prompt_tokens":957,"completion_tokens":810,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":573,"completion_tokens_details":{"reasoning_tokens":718}},"tokens_in":573,"tokens_out":810,"duration_ms":8894,"temperature":1.0,"reasoning_tokens":718,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:29:58.771045+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}