Ranking Vulnerability Fixes Using Planning Graph Analysis

Tom Gonda, Rami Puzis, Bracha Shapira, Guy Shani

International Workshop on Artificial Intelligence and Security (2017)

During the past years logical attack graphs were
used to find the most critical vulnerabilities and
devise efficient hardening strategies for organizational
networks. Most techniques for ranking vulnerabilities
either do not scale well, e.g. brute-force
attack plan enumeration, or are not well suited for
the analysis of logical attack graphs, e.g. centrality
In this paper we suggest an analysis of the planning
graph (from classical planning) derived from
the logical attack graph to improve the accuracy
of centrality-based vulnerability ranking metrics.
The planning graph also allows efficient enumeration
of the set of possible attack plans that use a
given vulnerability on a specific machine. We suggest
a set of centrality based heuristics for reducing
the number of attack plans and compare with
previously suggested vulnerability ranking metrics.
Results show that metrics computed over the planning
graph are superior to metrics computed over
the logical attack graph or the network connectivity