Cost minimization of the attack graph for thwarting network attacks

An Attack Graph is a graphical representation of possible ways that an intruder can attack a network system through atomic attacks. Based on such graphs, Jha, Sheyner and Wing have formulated a problem of adopting a minimum set M' of measures to ensure that the network system won't be attacked. They decompose the problem into two subproblems and solve each one by a Greedy Approximation Algorithm. In this paper, we extend their works in two directions. First, we extend their problem to find a minimum-cost set M' when each measure is assigned a cost according to the utilities used. We directly formulate the minimum-cost problem by a set of Integer Programming Equations (without decomposing the problem into subproblems.) A Branch and Bound Algorithm can optimally solve these equations for small cases. For larger cases, the algorithm uses the solution of the Greedy Algorithm as the initial solution, iteratively improving that solution until that the software program is terminated. In the second extension, we assume that each measure can delay the occurrence of certain atomic attacks by given values of time. Our objective is to find a minimum-cost set M' of measures so that adopting M' can ensure that the network won't be attacked before a required time T'. Again, we use the Integer Programming Method to solve this problem.