pith. sign in

arxiv: 1906.10943 · v1 · pith:XCFJ3ZHPnew · submitted 2019-06-26 · 💻 cs.CR

Heuristic Approach Towards Countermeasure Selection using Attack Graphs

Orly Stan , Ron Bitton , Michal Ezrets , Moran Dadon , Masaki Inokuchi , Yoshinobu Ohta , Tomohiko Yagyu , Yuval Elovici
show 1 more author
Asaf Shabtai
This is my paper

Pith reviewed 2026-05-25 15:52 UTC · model grok-4.3

classification 💻 cs.CR
keywords attack graphscountermeasure selectionheuristic searchrisk assessmentnetwork securitybudget limitationvulnerability modelinglateral movement
0
0 comments X

The pith

Heuristic search on extended attack graphs selects optimal countermeasures under budget without repeated graph regeneration.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a heuristic approach to choose the best countermeasures to deploy when resources are limited. It uses an extended attack graph to model risks more fully than standard methods, accounting for what an attack needs to succeed, what happens when it does, how attackers can move to other parts of the network, the physical connections, and weaknesses in protocols. Previous methods either rely on simple scores that miss these details or require manual repeated assessments that ignore topology and optimal placement. The new method avoids rebuilding the attack graph every time it evaluates a different set of countermeasures, aiming for a process that is both more accurate and computationally practical for real networks.

Core claim

The proposed heuristic search approach for selecting the optimal countermeasure deployment under a given budget limitation expresses the risk using extended attack graph modeling and provides a more accurate and practical countermeasure deployment planning process without requiring re-generation of the attack graph at each stage.

What carries the argument

Heuristic search applied to an extended attack graph that incorporates prerequisites, consequences, lateral movements, physical network topology, and protocol vulnerabilities.

Load-bearing premise

The extended attack graph model correctly and completely represents the network's vulnerabilities, prerequisites for exploits, consequences, lateral movements, topology, and protocol issues.

What would settle it

Compare the countermeasures chosen by the heuristic against those found by exhaustive search on a small network with known optimal deployment.

Figures

Figures reproduced from arXiv: 1906.10943 by Asaf Shabtai, Masaki Inokuchi, Michal Ezrets, Moran Dadon, Orly Stan, Ron Bitton, Tomohiko Yagyu, Yoshinobu Ohta, Yuval Elovici.

Figure 1
Figure 1. Figure 1: Mitigation action definition methodology. [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: MulVAL example: code execution attack graph. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Evaluation environment. (4) Tamper with the organization’s website by executing mali￾cious code on Web Server 1. (5) Deny users from accessing the organization’s Subversion server (Web Server 2) and disrupt their work [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Risk per budget. countermeasure is currently not modeled). The deployment cost of this plan is $2030. We examined the countermeasure plans generated for different budgets ranging from $10 to $2100. The plans for each tested budget are presented in [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Calculating risk using equations vs. regenerating [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
read the original abstract

Selecting the optimal set of countermeasures is a challenging task that involves various considerations and tradeoffs such as prioritizing the risks to mitigate and costs. The vast majority of studies for selecting a countermeasure deployment are based on a limited risk assessment procedure that utilizes the common vulnerability scoring system (CVSS). Such a risk assessment procedure does not necessarily consider the prerequisites and exploitability of a specific asset, cannot distinguish insider from outsider threat actor, and does not express the consequences of exploiting a vulnerability as well as the attacker's lateral movements. Other studies applied a more extensive risk assessment procedure that relies on manual work and repeated assessment. These solutions however, do not consider the network topology and do not specify the optimal position for deploying the countermeasures, and therefore are less practical. In this paper we suggest a heuristic search approach for selecting the optimal countermeasure deployment under a given budget limitation. The proposed method expresses the risk of the system using an extended attack graph modeling, which considers the prerequisites and consequences of exploiting a vulnerability, examines the attacker's potential lateral movements, and express the physical network topology as well as vulnerabilities in network protocols. In addition, unlike previous studies which utilizes attack graph for countermeasure planning, the proposed methods does not require re-generating the attack graph at each stage of the procedure, which is computationally heavy, and therefore it provides a more accurate and practical countermeasure deployment planning process.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes a heuristic search method for selecting an optimal set of countermeasures under a fixed budget. It models system risk via an extended attack graph that incorporates vulnerability prerequisites and consequences, attacker lateral movement, physical network topology, and protocol vulnerabilities. Unlike prior CVSS-based or manually repeated assessments, the method claims to avoid regenerating the attack graph at each planning stage, thereby delivering a more accurate and practical deployment process.

Significance. If the heuristic reliably returns near-optimal deployments and the one-time extended graph correctly encodes the listed risk factors, the approach would supply a computationally lighter alternative to repeated graph regeneration while addressing limitations of CVSS scoring. This could improve practicality for network administrators facing budget constraints, provided the modeling assumptions hold.

major comments (2)
  1. [Abstract] Abstract: the central claim that the method 'provides a more accurate and practical countermeasure deployment planning process' is unsupported; the manuscript contains no experimental results, baseline comparisons, worked example, optimality proof, or complexity analysis demonstrating that the heuristic achieves near-optimality or that the single extended graph improves risk-assessment accuracy over regeneration-based methods.
  2. [Abstract] Abstract: the modeling assumptions that the extended attack graph 'considers the prerequisites and consequences of exploiting a vulnerability, examines the attacker's potential lateral movements, and express[es] the physical network topology as well as vulnerabilities in network protocols' are stated without any formal definition, encoding rules, or illustrative instance showing how these elements are represented or why regeneration is unnecessary.
minor comments (2)
  1. [Abstract] Abstract, last sentence: 'the proposed methods does not' should read 'the proposed method does not'.
  2. [Abstract] Abstract: 'express the physical network topology' should be 'expresses the physical network topology' for subject-verb agreement.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We address each major comment below. We agree that the abstract overstates the method's demonstrated benefits and that the modeling requires more formal detail. Revisions will be made to the abstract and to add clarifying material.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the method 'provides a more accurate and practical countermeasure deployment planning process' is unsupported; the manuscript contains no experimental results, baseline comparisons, worked example, optimality proof, or complexity analysis demonstrating that the heuristic achieves near-optimality or that the single extended graph improves risk-assessment accuracy over regeneration-based methods.

    Authors: We agree that the abstract's claim of providing a 'more accurate and practical' process is not supported by experimental results, comparisons, examples, proofs, or complexity analysis in the manuscript. The work presents a heuristic approach and argues for its design advantages in principle, but does not empirically validate superiority. We will revise the abstract to remove the unsupported claim and instead describe the proposed method without asserting unproven improvements in accuracy or practicality. revision: yes

  2. Referee: [Abstract] Abstract: the modeling assumptions that the extended attack graph 'considers the prerequisites and consequences of exploiting a vulnerability, examines the attacker's potential lateral movements, and express[es] the physical network topology as well as vulnerabilities in network protocols' are stated without any formal definition, encoding rules, or illustrative instance showing how these elements are represented or why regeneration is unnecessary.

    Authors: We agree that the abstract states the modeling capabilities without formal definitions, encoding rules, or an illustrative example. The full manuscript describes the extended attack graph in later sections, but these elements are not formalized or exemplified in sufficient detail to show representation of prerequisites, consequences, lateral movement, topology, and protocol vulnerabilities, nor to explain avoidance of regeneration. We will add a new subsection with formal definitions, encoding rules, and a worked example demonstrating these aspects and the rationale for a single graph. revision: yes

Circularity Check

0 steps flagged

No circularity; algorithmic proposal with no derivation chain

full rationale

The manuscript presents a heuristic algorithm for countermeasure selection on an extended attack graph. No equations, parameter fitting, or closed-form derivations appear in the abstract or described method. The central claim (one-time graph suffices for optimal deployment under budget) is an unproven modeling assertion rather than a result derived from prior inputs. No self-citations, ansatzes, or renamings reduce any step to itself by construction. This matches the reader's 0.0 assessment and qualifies as a normal non-finding for an applied algorithmic paper.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The central claim rests on the modeling power of the extended attack graph and the effectiveness of the heuristic; no independent evidence for either is supplied in the abstract.

free parameters (1)
  • budget limitation
    The method operates under a user-specified budget that constrains the search.
axioms (2)
  • domain assumption An extended attack graph can faithfully represent prerequisites, consequences, lateral movements, physical topology, and protocol vulnerabilities for risk assessment.
    Invoked when the paper states that the proposed method expresses risk using this modeling.
  • domain assumption A heuristic search can identify an optimal or near-optimal countermeasure set without regenerating the attack graph after each candidate change.
    Central to the claimed computational practicality.

pith-pipeline@v0.9.0 · 5806 in / 1382 out tokens · 35583 ms · 2026-05-25T15:52:53.561208+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Stefano Bistarelli, Marco Dall’Aglio, and Pamela Peretti. 2006. Strategic Games on Defense Trees. In Formal Aspects in Security and Trust , Theo Dimitrakos, Fabio Martinelli, Peter Y. A. Ryan, and Steve Schneider (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 1–15

    work page 2006

  2. [2]

    Stefano Bistarelli, Fabio Fioravanti, and Pamela Peretti. 2006. Defense trees for economic evaluation of security investments. In First International Conference on A vailability, Reliability and Security (ARES’06). IEEE, 8–pp

    work page 2006

  3. [3]

    Chun-Jen Chung, Pankaj Khatkar, Tianyi Xing, Jeongkeun Lee, and Dijiang Huang. 2013. NICE: Network intrusion detection and countermeasure selection in virtual network systems. IEEE transactions on dependable and secure computing 10, 4 (2013), 198–211

    work page 2013

  4. [4]

    Frédéric Cuppens, Fabien Autrel, Yacine Bouzida, Joaquin Garcia, Sylvain Gom- bault, and Thierry Sans. 2006. Anti-correlation as a criterion to select appropriate counter-measures in an intrusion detection framework. Annales Des Télécommu- nications 61, 1 (01 Feb 2006), 197–217. https://doi.org/10.1007/BF03219974

    work page doi:10.1007/bf03219974 2006

  5. [5]

    Gustavo Gonzalez-Granadillo, Elena Doynikova, Igor Kotenko, and Joaquin Garcia-Alfaro. 2017. Attack Graph-Based Countermeasure Selection Using a Stateful Return on Investment Metric. In International Symposium on Foundations and Practice of Security . Springer, 293–302

    work page 2017

  6. [6]

    Kyle Ingols, Richard Lippmann, and Keith Piwowarski. 2006. Practical attack graph generation for network defense. In Computer Security Applications Confer- ence, 2006. ACSAC’06. 22nd Annual. IEEE, 121–130

    work page 2006

  7. [7]

    Sushil Jajodia, Steven Noel, and Brian O’Berry. 2005. Topological Analysis of Network Attack Vulnerability. Springer US, 247–266. 13 O. Stan, et al

    work page 2005

  8. [8]

    Kijsanayothin and R

    P. Kijsanayothin and R. Hewett. 2010. Analytical Approach to Attack Graph Analysis for Network Security. In 2010 International Conference on A vailability, Reliability and Security. 25–32. https://doi.org/10.1109/ARES.2010.21

    work page doi:10.1109/ares.2010.21 2010

  9. [9]

    Barbara Kordy, Sjouke Mauw, Saša Radomirović, and Patrick Schweitzer. 2012. Attack–defense trees. Journal of Logic and Computation 24, 1 (06 2012), 55–87. https://doi.org/10.1093/logcom/exs029

    work page doi:10.1093/logcom/exs029 2012

  10. [10]

    Kotenko and E

    I. Kotenko and E. Doynikova. 2016. Dynamical Calculation of Security Metrics for Countermeasure Selection in Computer Networks. In 2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP). 558–565. https://doi.org/10.1109/PDP.2016.96

    work page doi:10.1109/pdp.2016.96 2016

  11. [11]

    Xinming Ou, Wayne F Boyer, and Miles A McQueen. 2006. A scalable approach to attack graph generation. In Proceedings of the 13th ACM conference on Computer and communications security. ACM, 336–345

    work page 2006

  12. [12]

    Xinming Ou, Sudhakar Govindavajhala, and Andrew W Appel. 2005. MulVAL: A Logic-based Network Security Analyzer.. In USENIX Security Symposium, Vol. 8. Baltimore, MD

    work page 2005

  13. [13]

    Cynthia Phillips and Laura Painton Swiler. 1998. A graph-based system for network-vulnerability analysis. In Proceedings of the 1998 workshop on New secu- rity paradigms. ACM, 71–79

    work page 1998

  14. [14]

    Ira Pohl. 1970. Heuristic search viewed as path finding in a graph. Artificial Intelligence 1, 3 (1970), 193 – 204. https://doi.org/10.1016/0004-3702(70)90007-X

    work page doi:10.1016/0004-3702(70)90007-x 1970

  15. [15]

    Arpan Roy, Dong Seong Kim, and Kishor S Trivedi. 2012. Attack countermeasure trees (ACT): towards unifying the constructs of attack and defense trees.Security and Communication Networks 5, 8 (2012), 929–943

    work page 2012

  16. [16]

    Ganesh Ram Santhanam, Zachary J Oster, and Samik Basu. 2013. Identifying a preferred countermeasure strategy for attack graphs. In Proceedings of the Eighth Annual Cyber Security and Information Intelligence Research Workshop . ACM, 11

    work page 2013

  17. [17]

    Oleg Sheyner, Joshua Haines, Somesh Jha, Richard Lippmann, and Jeannette M Wing. 2002. Automated generation and analysis of attack graphs. In Security and privacy, 2002. Proceedings. 2002 IEEE Symposium on . IEEE, 273–284

    work page 2002

  18. [18]

    Valentina Viduto, Carsten Maple, Wei Huang, and David LóPez-PeréZ. 2012. A novel risk assessment and optimisation model for a multi-objective network security countermeasure selection problem. Decision Support Systems 53, 3 (2012), 599–610. A MITIGATION ACTIONS - EXAMPLE For demonstrating the definition of mitigation actions correspond- ing to the vulHost...

    work page 2012