REVIEW 3 major objections 4 minor 38 references
SPEAR: Security Posture Evaluation using AI Planner-Reasoning on Attack-Connectivity Hypergraphs
T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper claims that an attack-connectivity hypergraph and its compiled planning model are exactly equivalent—same attack paths, same connectivity paths—so hardening advice can be computed by planning and then re-checked against the graph.
desk verdict Theorem 1 has a real soundness/completeness gap that is load-bearing for the whole framework, but SPEAR's ACG hypergraph and diverse-hardening search are novel enough to warrant a serious revision. 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 carrying object is the Attack-Connectivity Graph (ACG), a hypergraph whose nodes are all pairs (host, attribute set) and whose edges are either connectivity edges between hosts or attack hyperedges from a set of source nodes to a destination node; it is non-monotonic (attacks may delete attributes) and may contain cycles. Its companion is the representative planning model M_G in PDDL/STRIPS, built by mapping every host-attribute pair to a fluent and every edge to an action, with the precondition of an action equal to the union of the fluents of its source nodes. Theorem 1's soundness and completeness equivalence is what licenses every downstream step: finding plans instead of graph paths, the PSPACE-completeness result for attack paths, the polynomial connectivity result via delete-free actions, the A*-search over constraining changes (limited to κ(M), the initial-state and add-effect parameters), and the compiled model M_α that computes attack difficulty as the cost of an optimal plan.
What would settle it
Build a two-host ACG where one host starts with attributes {p, q} and an attack hyperedge has a source node carrying only {p}, preconditions {p}, and a destination adding attribute r. In the planning model the initial state contains both p and q, so the attack action is applicable and produces a plan leading to r, while in the ACG the transition function requires the exact source node (host, {p}) to be present and therefore no valid attack path to r exists. Running SPEAR on this instance and observing a suggested attack plan (or a hardening edit based on it) would falsify Theorem 1 as stated.
Extended reading notes
Core claim
The central claim is Theorem 1: for a given ACG G, initial node set S0_N, and target node n_t, the representative planning model M_G is sound and complete—a valid plan exists in M_G if and only if a valid connectivity or attack path exists in G. Nodes of the ACG are host-attribute-set pairs; connectivity edges and attack hyperedges become actions whose preconditions are the unions of the source nodes' attribute fluents, whose add and delete effects are the postconditions of the attack, and whose initial and goal states encode the given attacker start and target. The paper claims this planning formulation is lossless, which makes the follow-on results possible: attack-path existence is PSPACE-complete, connectivity-path existence is polynomial, hardening reduces to constraining away all attack plans while keeping a connectivity plan, and the minimum-cost-of-attack metric can be computed by a small compiled model that lets the planner choose the initial state and the target. The practical translation is that what-if analysis over an attack graph can be performed by editing the planning model and re-solving it.
Load-bearing premise
The equivalence in Theorem 1 assumes that an action's preconditions can be represented simply as the union of the attribute fluents of its source nodes, so the planner may apply an attack whenever those fluents are present even if the affected host's attribute set is a proper superset of the source node's attribute set, whereas the ACG transition requires the exact source node set to be present.
Editorial extensions
If this is right
- If Theorem 1 holds, every valid plan produced by the planner in M_G corresponds to a genuine attack or connectivity path, so any hardening suggestion derived from blocking plans is grounded in actual graph paths.
- Hardening to the impenetrability metric means making the attack-plan set empty while preserving a connectivity plan; the A* search with the proposed admissible heuristic guarantees an optimal set of model updates when costs are uniform.
- The attack-difficulty metric equals the optimal plan cost of the compiled model M_α, so raising the required threshold forces the attacker's shortest path cost up by at least the chosen amount.
- The non-overlapping solution set produced by the modified A* search lets an administrator choose among qualitatively different hardening strategies when modification costs are partially or wholly unspecified.
- Relaxing the monotonicity assumption allows the framework to model lateral movement, revisits, and attribute loss, which earlier monotonic attack-graph frameworks cannot express.
Reading between the lines
- Editorial inference: the soundness-completeness equivalence is only as tight as the state-tracking discipline; unless each host is constrained to hold exactly one node's attribute set, the planner can apply an attack whose preconditions are a proper subset of a host's current attributes while the ACG transition requires the exact source node, potentially creating phantom plans.
- Editorial inference: the framework's central promise could be tested end-to-end by comparing planner-derived hardening suggestions against a ground-truth penetration test on the same network, a validation the paper does not report.
- Editorial inference: the constraining-changes insight (only initial-state and add-effect removals can invalidate previous plans) may carry over to other security analyses, such as k-zero-day safety, where the goal is to block newly introduced attacker capabilities.
- Editorial inference: because the ACG treats connectivity as a replaceable relation, the same machinery could be adapted to quantitative service-availability or latency targets rather than the indicator connectivity function used here.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the Attack-Connectivity Graph (ACG), a hypergraph model combining attack dependencies with network connectivity, and proposes SPEAR, a framework that compiles an ACG into a classical planning model in PDDL. On this compiled model, the paper defines robustness metrics (impenetrability and attack difficulty), an A*-based search for diverse hardening updates, an admissible heuristic based on top-K attack plans, and an empirical evaluation on a testbed and synthetic networks. The main formal claims are soundness and completeness of the planning compilation (Theorem 1), complexity results for attack/connectivity path existence (Theorem 2), and guarantees for the model-update search (Propositions 1–4).
Significance. The paper addresses a real gap in network hardening: jointly reasoning about attack reachability and connectivity while supporting human-in-the-loop what-if analysis. The hypergraph-plus-planning framing is promising and the authors provide a tool and a concrete case study. If the central equivalence were correct, the complexity results and the compositional treatment of connectivity would be useful contributions. However, the main theorem is currently unproven and false under the stated definitions, so the framework's formal guarantees do not transfer from the planning model to the ACG. The paper needs substantial revision before its central claims are credible.
major comments (3)
- [Section 3, Definition 5 / Theorem 1]
- [Section 4.2, Definition 11]
- [Section 7, Table 1]
minor comments (4)
- [Section 3, Definition 7] The monotonicity condition 'FA(E1)≥FA(E2), if and only if, E1⊆E2' is a biconditional and would force FA to be injective; it should be an implication ('if E1⊆E2 then FA(E1)≥FA(E2)').
- [Section 4.2, Algorithm 2] The condition 'if {f}∪C has no subset in C' is unclear and appears to use C for both the current node and the closed list; based on the surrounding text it should check that the new update set is not a superset of an already discovered solution.
- [Section 4.2, Proposition 3] The proof claims solutions are tested 'in order of increasing cardinality,' but this is not guaranteed when the heuristic equals 1: a size k+1 goal and a size k goal can then have equal f-cost, and tie-breaking may pop the larger first. The non-overlap guarantee needs a tie-breaking rule or a stricter bound on the heuristic.
- [Theorem 2, proof sketch] Even if Theorem 1 is repaired, the membership argument for attack-path existence should be made precise: the reference to positive-precondition STRIPS must account for the unrestricted delete effects in the compiled actions, and the reduction must be shown to preserve both directions of plan/path existence.
Circularity Check
No meaningful circularity: the ACG-to-PDDL compilation, metrics, and search are defined in-paper; self-citations are non-load-bearing and the flagged Theorem 1 issue is a correctness gap, not circularity.
full rationale
SPEAR's derivation chain is: formalize an Attack-Connectivity Graph (Defs. 1-4), compile it into a planning model (Def. 5), assert an equivalence theorem (Thm. 1), define robustness metrics (Defs. 6-9), and search over constrained models to improve them (Sec. 4.2). Each of these steps is stated with its own definitions and equations; none is fitted to data and none derives its conclusion from the authors' prior work in a load-bearing way. The delta parameterization cites the authors' model-reconciliation papers [34,35], but Definition 10 fully defines delta in the text, so the citation is a convention pointer rather than a premise; the Resiliency Graphs paper [2] appears as related work, not as the basis for Theorem 1. The Theorem 1 proof sketch is very brief, and the reviewer's counterexample identifies a real completeness gap (host-wide delete effects vs node-specific lambda), but that is a soundness/encoding defect, not circular reasoning: the theorem's conclusion is not assumed as an input. Theorem 2's complexity bounds rest on external references (Bylander [7]; Hoffmann and Nebel [16]). Metrics and heuristic values are computed directly from path sets and are not fitted predictions. Thus the circularity score is low.
Assumptions & free parameters
free parameters (1)
- K (number of top attack plans used in heuristic) =
3
assumptions (4)
- standard math STRIPS plan existence is PSPACE-complete for positive-precondition actions with delete effects, and delete-free plan existence is polynomial.
- domain assumption The NLP-based extractor can reliably convert CVE descriptions and network configurations into correct PDDL domain and problem files.
- ad hoc to paper All model updates are constrained to removals of initial fluents or add effects, with unit costs unless otherwise specified.
- domain assumption The relevant attacker model is deterministic, unit-cost, and measured by shortest attack path length.
Cite this review
Pith. "Pith review of SPEAR: Security Posture Evaluation using AI Planner-Reasoning on Attack-Connectivity Hypergraphs." pith.science (2026). https://pith.science/paper/MDDTRF3A
@misc{pith2026250601227,
author = {Pith},
title = {Pith review of: SPEAR: Security Posture Evaluation using AI Planner-Reasoning on Attack-Connectivity Hypergraphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/MDDTRF3A}},
note = {Machine review of arXiv:2506.01227}
}
read the original abstract
Graph-based frameworks are often used in network hardening to help a cyber defender understand how a network can be attacked and how the best defenses can be deployed. However, incorporating network connectivity parameters in the attack graph, reasoning about the attack graph when we do not have access to complete information, providing system administrator suggestions in an understandable format, and allowing them to do what-if analysis on various scenarios and attacker motives is still missing. We fill this gap by presenting SPEAR, a formal framework with tool support for security posture evaluation and analysis that keeps human-in-the-loop. SPEAR uses the causal formalism of AI planning to model vulnerabilities and configurations in a networked system. It automatically converts network configurations and vulnerability descriptions into planning models expressed in the Planning Domain Definition Language (PDDL). SPEAR identifies a set of diverse security hardening strategies that can be presented in a manner understandable to the domain expert. These allow the administrator to explore the network hardening solution space in a systematic fashion and help evaluate the impact and compare the different solutions.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
Massimiliano Albanese, Sushil Jajodia, Anoop Singhal, and Lingyu Wang. 2013. An Efficient Approach to Assessing the Risk of Zero-Day Vulnerabilities. In Pro- ceedings of 2013 International Conference on Security and Cryptography (SECRYPT), Pierangela Samarati (Ed.). Reykjavik, Iceland, 1–12
work page 2013
-
[2]
Shadaab Kawnain Bashir, Rakesh Podder, Sarath Sreedharan, Indrakshi Ray, and Indrajit Ray. 2024. Resiliency Graphs: Modelling the Interplay between Cyber Attacks and System Failures through AI Planning. In 2024 IEEE 6th International Conference on Trust, Privacy and Security in Intelligent Systems, and Applications (TPS-ISA). IEEE, 292–302
work page 2024
-
[3]
Kristian Beckers, Maritta Heisel, Leanid Krautsevich, Fabio Martinelli, Rene Meis, and Artsiom Yautsiukhin. 2014. Determining the Probability of Smart Grid Attacks by Combining Attack Tree and Attack Graph Analysis. In Proceedings of Smart Grid Security: Second International Workshop, SmartGridSec 2014 (Lec- ture Notes in Computer Science, Vol. 8448) , Jo...
work page 2014
-
[4]
Kristian Beckers, Leanid Krautsevich, and Artsiom Yautsiukhin. 2015. Analysis of Social Engineering Threats with Attack Graphs. In Proceedings of Data Privacy Management, Autonomous Spontaneous Security, and Security Assurance: 9th In- ternational Workshop, DPM 2014, 7th International Workshop, SETOP 2014, and 3rd International Workshop, QASA 2014 (Lectur...
work page 2015
-
[5]
Bruhadeshwar Bezawada, Indrajit Ray, and Kushagra Tiwary. 2019. AGBuilder: An AI Tool for Automated Attack Graph Building, Analysis, and Refinement. In Data and Applications Security and Privacy XXXIII: 33rd Annual IFIP WG 11.3 Conference, DBSec 2019, Charleston, SC, USA, July 15–17, 2019, Proceedings 33 . Springer, 23–42
work page 2019
-
[6]
Serena Booth, W Bradley Knox, Julie Shah, Scott Niekum, Peter Stone, and Alessandro Allievi. 2023. The Perils of Trial-and-Error Reward Design: Misdesign through Overfitting and Invalid Task Specifications. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37. 5920–5929
work page 2023
-
[7]
Tom Bylander. 1994. The Computational Complexity of Propositional STRIPS Planning. Artificial Intelligence 69, 1-2 (1994), 165–204
work page 1994
-
[8]
Turgay Caglar, Sirine Belhaj, Tathagata Chakraborty, Michael Katz, and Sarath Sreedharan. 2024. Can LLMs Fix Issues with Reasoning Models? Towards More Likely Models for AI Planning. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38. 20061–20069
work page 2024
Show all 38 references
-
[9]
Rinku Dewri, Nayot Poolsappasit, Indrajit Ray, and Darrell Whitley. 2007. Op- timal Security Hardening using Multi-Objective Optimization on Attack Tree Models of Networks. In Proceedings of the 14th ACM Conference on Computer and Communications Security. 204–213
2007
-
[10]
Rinku Dewri, Indrajit Ray, Nayot Poolsappasit, and Darrell Whitley. 2012. Optimal Security Hardening on Attack Tree Models of Networks: A Cost-Benefit Analysis. International Journal of Information Security 11, 3 (June 2012), 167–188. doi:10. 1007/s10207-012-0160-y
2012
-
[11]
Karel Durkota, Viliam Lis`y, Branislav Bošansk`y, Christopher Kiekintveld, and Michal Pěchouček. 2019. Hardening Networks Against Strategic Attackers using Attack Graph Games. Computers & Security 87 (2019), 101578
2019
-
[12]
Erella Eisenstadt and Amiram Moshaiov. 2016. Novel solution approach for multi- objective attack-defense cyber games with unknown utilities of the opponent. IEEE Transactions on Emerging Topics in Computational Intelligence 1, 1 (2016), 16–26
2016
-
[13]
Mahsa Ghasemi, Evan Scope Crafts, Bo Zhao, and Ufuk Topcu. 2021. Multiple Plans are Better than One: Diverse Stochastic Planning. In Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 31. 140–148
2021
-
[14]
Nirnay Ghosh and Soumya K Ghosh. 2012. A Planner-Based Approach to Gener- ate and Analyze Minimal attack Graph. Applied Intelligence 36 (2012), 369–390
2012
-
[15]
Dijkstra
Jörg Hoffmann. 2015. Simulated Penetration Testing: From" Dijkstra" to" Turing Test++". In Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 25. 364–372
2015
-
[16]
Jörg Hoffmann and Bernhard Nebel. 2001. The FF Planning System: Fast Plan Generation through Heuristic Search. Journal of Artificial Intelligence Research 14 (2001), 253–302
2001
-
[17]
Mariam Ibrahim, Qays Al-Hindawi, Ruba Elhafiz, Ahmad Alsheikh, and Omar Alquq. 2019. Attack Graph Implementation and Visualization for Cyber Physical Systems. Processes 8, 1 (2019), 12
2019
-
[18]
Kerem Kaynar and Fikret Sivrikaya. 2015. Distributed Attack Graph Generation. IEEE Transactions on Dependable and Secure Computing 13, 5 (2015), 519–532
2015
-
[19]
Sarah Keren, Avigdor Gal, and Erez Karpas. 2019. Goal Recognition Design in Deterministic Environments. Journal of Artificial Intelligence Research 65 (2019), 209–269
2019
-
[20]
Bertram F Malle. 2006. How the Mind Explains Behavior: Folk Explanations, Meaning, and Social Interaction . MIT press
2006
-
[21]
Stephanie Milani, Weiran Shen, Kevin S Chan, Sridhar Venkatesan, Nandi O Leslie, Charles Kamhoua, and Fei Fang. 2020. Harnessing the Power of Deception in Attack Graph-Based Security Games. InDecision and Game Theory for Security: 11th International Conference, GameSec 2020, C...
2020
-
[22]
Zohair Shafi Miller, A Benjamin, Ayan Chatterjee, Tina Eliassi-Rad, and Raj- monda S Caceres. 2023. GRASP: Accelerating Shortest Path Attacks via Graph Attention. arXiv preprint arXiv:2310.07980 (2023)
2023 arXiv
-
[23]
Thanh H Nguyen, Mason Wright, Michael P Wellman, and Satinder Baveja. 2017. Multi-Stage Attack Graph Security Games: Heuristic Strategies, with Empirical Game-Theoretic Analysis. In Proceedings of the 2017 Workshop on Moving Target Defense. 87–97
2017
-
[24]
Steven Noel and Sushil Jajodia. 2009. Advanced Vulnerability Analysis and Intrusion Detection through Predictive Attack Graphs. Critical Issues in C4I, Armed Forces Communications and Electronics Association (AFCEA) Solutions Series. International Journal of Command and Control (2009)
2009
-
[25]
Steven Noel and Sushil Jajodia. 2014. Metrics Suite for Network Attack Graph Analytics. In Proceedings of the 9th Annual Cyber and Information Security Research Conference. 5–8
2014
-
[26]
Noel, Sushil Jajodia, B
S. Noel, Sushil Jajodia, B. O’Berry, and M. Jacobs. 2003. Efficient Minimum- Cost Network Hardening via Exploit Dependency Graphs. In Proceedings of 19th Annual Computer Security Applications Conference, Frances Titsworth (Ed.). IEEE, Las Vegas, NV, USA, 86–95. doi:10.1109/CSA...
2003 arXiv
-
[27]
Xinming Ou, Sudhakar Govindavajhala, and Andrew W. Appel. 2005. MulVAL: A Logic-Based Network Security Analyzer. In Proceedings of the 14th Confer- ence on USENIX Security Symposium (Baltimore, MD) (SSYM’05, Vol. 8). USENIX Association, Baltimore, MD, USA, 113–128
2005
-
[28]
Cynthia Phillips and Laura Painton Swiler. 1998. A Graph-Based System for Network-Vulnerability Analysis. In Proceedings of the 1998 Workshop on New Security Paradigms (Charlottesville, Virginia, USA) (NSPW ’98). Association for Computing Machinery, New York, NY, USA, 71–79. d...
1998
-
[29]
Nayot Poolsappasit, Rinku Dewri, and Indrajit Ray. 2011. Dynamic Security Risk Management Using Bayesian Attack Graphs. IEEE Transactions on Dependable and Secure Computing 9, 1 (2011), 61–74
2011
-
[30]
Indrajit Ray and Nayot Poolsapassit. 2005. Using Attack Trees to Identify Ma- licious Attacks from Authorized Insiders. In Proceedings of Computer Security – ESORICS 2005 , Sabrina de Capitani di Vimercati, Paul Syverson, and Dieter Gollmann (Eds.). Springer Berlin Heidelberg,...
2005
-
[31]
Indrajit Ray, Sarath Sreedharan, Rakesh Podder, Shadaab Kawnain Bashir, and Indrakshi Ray. 2023. Explainable AI for Prioritizing and Deploying Defenses for Cyber-Physical System Resiliency. In 2023 5th IEEE International Conference on Trust, Privacy and Security in Intelligent...
2023
-
[32]
Mark Roberts, Adele E Howe, Indrajit Ray, and Malgorzata Urbanska. 2012. Using Planning for a Personalized Security Agent. InProceedings of Workshop on Problem Solving using Classical Planners at 26th AAAI Conf. on Artificial Intelligence . Toronto, Ontario, Canada
2012
-
[33]
Schneier
B. Schneier. 1999. Attack Trees: Modeling Security Threats. Dr. Dobb’s Journal of Software Tools 24 12 (1999), 21–29
1999
-
[34]
Sarath Sreedharan, Pascal Bercher, and Subbarao Kambhampati. 2022. On the Computational Complexity of Model Reconciliations. In Proceedings of the 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence, IJCAI-...
2022
-
[35]
Sarath Sreedharan, Tathagata Chakraborti, and Subbarao Kambhampati. 2021. Foundations of Explanations as Model Reconciliation. Artificial Intelligence 301, 103558 (2021)
2021
-
[36]
Kushagra Tiwary, Sachini Weerawardhana, Indrajit Ray, and Adele Howe. 2017. PDDLAssistant: A Tool for Assisting Construction and Maintenance of Attack Graphs Using PDDL. In in Proceedings of the ACM Conference on Computer and Communications Security 2017 (CCS 2017) . Dallas, USA
2017
-
[37]
Simon Unger, Ektor Arzoglou, Markus Heinrich, Dirk Scheuermann, and Stefan Katzenbeisser. 2023. Risk Assessment Graphs: Utilizing Attack Graphs for Risk Assessment. arXiv preprint arXiv:2307.14114 (2023)
2023 arXiv
-
[38]
Kaifa Zhao, Hao Zhou, Yulin Zhu, Xian Zhan, Kai Zhou, Jianfeng Li, Le Yu, Wei Yuan, and Xiapu Luo. 2021. Structural Attack Against Graph Based Android Mal- ware Detection. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 3218–3235. Appe...
2021
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.