Detecting Cascade Vulnerability in Linear Time
Loading...
Files
Date
2000
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The cascade vulnerability detection problem asks whether an opponent can use interconnections to pass data improperly across a network of individually accredited systems without having to defeat any single system that is rated high enough to be judged safe for the particular data flow. In the most general setting, an algorithm is given of time complexity O(CD2U2 + LDU), where C is the number of computers, D is the number of different classes of data, U is the number of different classes of user, and L is the number of links in the network. In the case with a linear data classification, the time complexity reduces to O(CD2 + LD), which improves on the previous best complexity of O(C3D). The case with parallel linear data classes is also solved in O(CD2 + LD) time.
Keywords: algorithm, network security, cascade vulnerability, detection problem