Efficient heuristic algorithms for correcting the Cascade Vulnerability Problem for interconnected networks

The Cascade Vulnerability Problem for interconnected networks is a potential problem faced when the interconnected accredited system approach of the Trusted Network Interpretation is used. It belongs to a subset of the problem set that addresses the issue of whether the composition of secure systems via a secure channel results in a secure network. The Cascade Vulnerability Problem appears when an attacker can take advantage of network connections to compromise information across a range of security levels that is greater than the accreditation range of any of the component systems she must defeat to do so.In this paper, the general Cascade Vulnerability Problem is presented, and the basic properties of the most important detection and correction algorithms are briefly described. Two new efficient heuristic algorithms are proposed for correcting the Cascade Vulnerability Problem: (a) a conceptually simple and computationally fast Combinatorial Algorithm based on a reduction of the Cascade Vulnerability Correction Problem to Weighted Vertex Cover, and (b) a simple and easy to implement Genetic Algorithm based on the Combinatorial Algorithm. The new algorithms are experimentally evaluated on a collection of randomly generated instances consisting of networks of various characteristics. The experiments demonstrate that the Combinatorial Algorithm is extremely fast but sometimes fails to produce low-cost solutions. On the other hand, the Genetic Algorithm is significantly slower but consistently computes much better solutions.