Distilling Critical Attack Graph Surface iteratively through Minimum-Cost SAT Solving

It has long been recognized that rendering a full complicated attack
graph to a system administrator (SA) has limited utility. It could be
tedious and even infeasible for the SA to figure out critical security
problems residing in the attack graph, even for small-sized enterprise
networks. Therefore a trade-off between analysis accuracy
and efficiency needs to be made to achieve a reasonable balance
between completeness and usefulness of the information. In this
paper, we provide an approach to attack graph distillation, so that
the user can control the amount of information presented by sifting
out the most critical portion of the full attack graph. The user
can choose to see only the first k most critical attack paths, based
on pre-defined metrics of severity and user-specified security concern,
e.g. the crucial assets in the enterprise network, critical attack
paths related to given vulnerabilities, etc. We transform the dependency
attack graph into a Boolean formula and assign cost metrics
to attack variables in the formula, based on the severity metrics,
e.g. the likelihood of success for an attacker to carry out the exploit.
We then apply Minimum-Cost SAT Solving (MCSS) to find
the most critical path in terms of the least cost incurred for the attacker
to deploy multi-step attacks leading to certain crucial assets
in the network. An iterative process inspired by Counter Example
Guided Abstraction and Refinement (CEGAR) is designed to efficiently
guide the MCSS to render solutions that contain realistic attack
paths, and also allow a controlled number of paths to be output,
forming a critical attack graph surface. Our method can distill critical
attack graph surfaces from the full attack graphs generated for
moderate-sized enterprise networks in only several minutes. With
the critical attack graph surface, several flexible visualization and
analysis approaches for attack graphs can be applied, e.g. calculating
quantitative security risk metrics on the most critical surface.
Experiments on various sized network scenarios show that even for
a very small-sized critical attack graph surface (around 15% the
size of the original full attack graph), the calculated risk metrics
are good approximation of the values computed with the full attack
graph, meaning the distilled critical attack graph surface is able to
capture the crucial security problems in an enterprise network for
further in-depth analysis.

Author(s):

Heqing Huang    
Kansas State University
United States

Su Zhang    
Kansas State University
United States

Xinming Ou    
Kansas State University
United States

Atul Prakash    
University of Michigan
United States

Karem Sakallah    
University of Michigan
United States