A Heuristic Approach to Minimum-Cost Network Hardening Using Attack Graph

Network hardening answers the following critical question in defending against multi-step intrusions: Which vulnerabilities must be removed in order to prevent any attacker from reaching the given goal conditions. Existing approaches usually derive a logic proposition to represent the negation of the goal conditions in terms of initially satisfied conditions. In the disjunctive normal form (DNF) of the logic proposition, each disjunction then provides a viable solution to network hardening. However, such solutions suffer from an exponential time complexity. In this work, we study heuristic methods for solving this important problem with a reasonable complexity. We evaluate our proposed solution through comprehensive experiments. The results show that our solution can achieve comparable costs of network hardening in much less time than the optimal solution.