Near Optimal Network Defense Resource Allocation Policies for Maximization of Network Survivability

Due to the decreasing cost of computer hardware and the increasing capacity of computer software, most critical networks are being progressively computerized. If one of these systems were to fail, it would not only cause extreme inconvenience in our daily lives, but could even have catastrophic or fatal consequences. Thus, how to assess and evaluate the survivability of a system effectively is a crucial issue in the field of information security.
In this thesis, we propose a simple and novel metric of network survivability, called Degree of Separation (DOS). DOS is a survivability metric used to measure the average damage level of a system; naturally, the larger the DOS value, the more serious the network damage will be. If the DOS value is larger than a pre-established threshold, we say that the network has been compromised.
We express the scenario of network attack-defense as a mathematical linear programming model to near-optimize the resource allocation policies. In the process of problem solving, we adopt the concept of DOS to assess the network survivability and use the Lagrangean Relaxation method and the subgradient method to approach the optimal solution.
Finally, based on the experiment results, not only can the 3-stage selection (3SS) attack algorithm we proposed evaluate the attack cost effectively, but are the results of different defense budget allocation policies to different network topologies quite significant.