Affiliations: [a] Faculty of Computer Science, University of New Brunswick, P.O. Box 4400, Fredericton, N.B., Canada E3B 5A3, E-mail: [email protected] | [b] Communications Security Establishment, Canadian System Security Centre, P.O. Box 9703, Terminal, Ottawa, Ontario, Canada K1G 3Z4, E-mail: [email protected] | [c] Martin Marietta Canada Ltd., 50 O'Connor Street, Suite 1450, Ottawa, Ontario, Canada K1P 6L2, Fax: (613) 232-6698
Abstract: A network of computers is vulnerable to the cascading problem when data of a security level d can be passed to a user with a lower security clearance u elsewhere on the network, without having to defeat any single component of the system that has an accreditation range great enough to allow users of level u and data of level d on a single system. An algorithm of time complexity order O(an3) and space complexity O(an2) is given to solve the cascade detection problem, where a is the number of security levels for data, and n is the number of nodes in the network. Also, the cascade correction problem, to remove all cascading paths from a network for a given cost, under restrictive conditions is shown to be NP-complete.
