This is an HTML rendering of a working paper draft that led to a publication. The publication should always be cited in preference to this draft using the following reference:
The Cascade Vulnerability
for Distributed Systems:
Department of Informatics University of Athens TYPA Buildings, Athens GR-15771, Greece tel.: +30-1-7291885, fax: +30-1-7219561
Department of Informatics
Institute (T.E.I.) of Athens
Aegaleo GR-12210, Greece
tel.: +30-1- 5910974,
Sokratis K. Katsikas
Department of Mathematics
University of the
Samos GR-83200, Greece
Department of Mathematics University of the Aegean Samos GR-83200, Greece tel.: +30-273-33919, fax: +30-273-35483 email: email@example.com
The Cascade Vulnerability Problem
is a potential problem which must be faced when using the interconnected
accredited system approach of the Trusted Network Interpretation.
In this paper, the general Cascade vulnerability problem is presented,
the basic properties of the most important detection algorithms
are described, and a brief comparative analysis is conducted.
Cascade Vulnerability Problem,
Network & Open Distributed Systems Security, Risk Analysis.
The Cascade Vulnerability problem was discussed in the Trusted Network Interpretation (NCSC, 1987) of the Trusted Computer System Evaluation Criteria (TCSEC, 1985). According to (NCSC, 1987), the Cascade Vulnerability problem exists when a penetrator 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 s/he must defeat to do so.
In a distributed system with
many nodes and interconnections, the existence of a Cascade Vulnerability
problem may not be obvious and can cause serious security problems.
In this paper we will present the most effective algorithms -in
the open literature- for the detection of the existence of the
Cascade vulnerability problem and the identification of the paths
along which the problem exists. Then, we will present the basic
semantics of an algorithm for the restricted Cascade correction
problem, which proposes network modifications for reducing the
risk of Cascade vulnerability. Finally, a brief comparative analysis
of the presented algorithms will be presented.
2 THE CASCADE VULNERABILITY
The Cascade vulnerability problem
belongs to a subspace of the problem set that address the issue
of whether the interconnection of secure systems via a secure
channel results in a secure distributed system.
The term "secure system"
is taken here to mean a system that has undergone not only a risk
analysis evaluation that results an acceptable risk of operating
the system, but a system security evaluation as well.
The assets of the system and
the threats against each one of them are considered during the
risk analysis review, in order to identify the level of the security
required. System security can be modelled as a function of many
parameters, such as computer security, communications security,
administrative security, personnel security and physical security
(Madron, 1990). For implementation reasons all these parameters
must be categorised into classes of countermeasures that reduce
the system risks. Therefore a system security evaluation assesses
the effectiveness of the countermeasures which were finally selected
for this certain system, at this specific time.
The Cascade vulnerability problem
holds for the subset of networks that cannot be treated as a single
system. There are different reasons why networks cannot be viewed
as a single system. The main reasons can be:
In any case, it is necessary
that the administrators of any two systems that are to be interconnected
mutually agree that both systems are secure as stand-alone systems;
that is, both administrators need to accept the risk assessment
and the security evaluation methods which are used for both systems.
In summary, one can argue that
(Fitch, 1991) (Fitch, 1993) the Cascade vulnerability problem
appears when independent mutually recognised secure systems, are
interconnected by secure channels to create a distributed system
which, potentially, is not secure. In other words (Millen, 1988)
the Cascade vulnerability problem appears when an adversary can
take advantage of network connections to compromise information
across a range of sensitivity levels that is greater than the
accreditation range of any of the component systems s/he must
defeat to do so.
As a typical example of the
Cascade vulnerability problem (NCSC, 1987), let us consider two
systems, as shown in Figure 1. Host A is accredited for TS-Top
Secret and S-Secret information and all users are cleared to at
least the Secret level. Host B is accredited for S and C-Confidential
and all users are cleared to at least the Confidential level;
finally, there is a link at level S between the two systems.
The generic Cascade vulnerability problem.
While the risk of compromise
in each of these systems is small enough to justify their use
with two levels of information, the system as a whole has three
levels of information. This increases the potential harm that
an adversary could cause, since s/he could downgrade the TS-level
information in system A to S-level, send it to system B, and further
downgrade the information to C-level therein.
The adversary has to defeat
the protection mechanisms of both systems A and B, but that is
an easier job than defeating the protection mechanisms of a single
system trusted to protect the whole range from TS-level to C-level.
The network connection has, in essence, created a Trusted Computing
Base (TCB) with users cleared to at least the C-level with data
on it at the TS-level.
In this way (Millen, 1988)
the network connection has invalidated the risk analysis that
accredited the two systems, because such a networked system must
have a more secure architecture, a TCB rating of B3, than either
rating of the original individual sub-systems TCB (i.e. B1 or
B2, Figure 2).
Security Index Matrix for Open Environments (NCSC, 1985).
Let Rj(t) be the probability that both TCBs can be penetrated if the joint combination of two TCBs is subject to a total threat of t units or less. Changing variables and taking into account that the probability of two independent events occurring together is the product of their separate probabilities (Freund, 1962), the value of Rj can be then computed as the convolution integral:
whose precise value in relation
to the original RB2(x)
is not intuitively obvious.
In Figure 3a and 3b the probability density functions for RB2(t) and of the Cascade Rj(t) are shown.
It has been proven (Lee, 1989)
that Rj is approximately
equal to R2B2 for the Cascade of two B2 systems. This means that
the resistance to threat of a Cascade of two B2 systems is approximately
the same as, or even better than, that of a B3 system.
3 ALGORITHMS FOR CASCADE VULNERABILITY
3.1 The Nesting and
The Nesting condition
The simplest approach for recognising
a potential Cascade Vulnerability problem is to test whether a
network can or cannot face such a problem. This simple test is
calling the nesting condition (NCSC, 1987).
The nesting condition is true
if the accreditation range of each of the interconnected systems
Fulfilment of the nesting condition
implies that there can be no Cascade Vulnerability problem in
the network at hand. However, there are many cases in the literature
(Millen, 1988) where the nesting condition is not fulfilled, yet
there is actually no Cascade Vulnerability problem.
A possible solution when the
problem may exist is to eliminate certain network connections,
either physically or by means of end-to-end encryption. The latest
solution allows hosts that need to communicate to do so, while
eliminating additional unnecessary Cascading risk on the path
from one host to another.
The Cascading condition
An attempt for a formal description
of the Cascading condition, which is more precise than
the one described in (NCSC, 1987), is presented in (Millen, 1988).
According to that, when we use a network, we know that it consists
of some nodes h, and every node has its accreditation range
A(h). This A(h) consists of a set of sensitivity
levels which, as a whole, form a lattice. Consequently, an accreditation
range is a convex sublattice, which is the formal notion corresponding
to a range.
The protection regions are
the pairs (h,s), for each sensitivity level sA(h).
A step is an ordered pair of protection regions (h1,
s1), (h2, s2)
such that either
In the second case, if also
then the information transfer is permitted by the enforced security
policy in this specific node. A downgrade is a flow such that
A downgrade from s1
is always associated with a risk index R(s1,s2).
The risk index of any convex sublattice can be defined as the
least upper bound of all R(si,sj).
Two accreditation ranges -
convex sublattices are:
For a certain path (h1,s1),
its net downgrade is R(s1,sn),
and its difficulty is max(R(A(hi))),
such that si>si+1.
According to the above formalism,
we can argue that a path is a Cascading path, if its difficulty
is at least as great as its net downgrade. Therefore, a network
satisfies the Cascade condition, if it has no Cascading paths
In (Millen, 1988) one can find
a program, written in Edinburgh Prolog, that can identify all
Cascading paths based on the previous formalism.
3.2 A heuristic procedure
The heuristic condition is
a less conservative but much more complex heuristic that takes
into account the connectivity of the network and the evaluation
classes of the components. Given the goal of not allowing a risk
greater than is recommended by the Environmental Guidelines, the
heuristic procedure (NCSC, 1987) has been developed to
examine systems and determine whether they fall within the bounds
prescribed by these Guidelines.
In formal terms, the heuristic
procedure is an approximate test for the Cascade condition, described
in the previous section. It should be noted that this procedure
is not intended to be prescriptive: it is merely one way of examining
It is obvious that the heuristic
procedure, as every heuristic, has been derived through trial
and error, it produces reasonable results and provides useful
guidance to the prudence of interconnecting various systems.
In (NCSC, 1987) an algorithm
is described for determining whether or not a given network, composed
of evaluated components, meets the risk categories of the Environmental
Guidelines. The algorithm is based on the idea of dividing a network
into groups. The risk presented by any given group can be compared
to the maximum allowed risk as defined by the Yellow Book for
a system at the given evaluation class, to determine if any community
presents an unacceptable risk.
The steps for the heuristic
procedure are (NCSC, 1987):
The reader can find an analytical
application of the heuristic procedure in an example in (NCSC,
3.3 Shortest path
network security model
The formulation of the Cascade
Vulnerability problem as a Resource-Constrained Shortest Path
Problem (Fitch, 1991) (Fitch, 1993) leads to an efficient algorithm
for determining whether a network has a Cascade Vulnerability
The resource-constrained shortest
path is based on three phases: Preprocessing, Shortest path calculation
In this approach, the algorithm
is flexible in two ways:
The time-complexity of the
algorithm is at most O(n'3)=O(a3n3),
where n' is the number of nodes in the expanded graph. The space-complexity
of the algorithm is O(n'2)=O(a2n2).
3.4 The Horton algorithm
An efficient algorithm for
the detection of Cascading Vulnerability paths is presented in
(Horton, 1993). In this algorithm, the interconnection network
of trusted computer systems is modelled as a directed graph with
n nodes and m edges. The nodes have a TCB rating
associated with each other and represent the trusted subsystems.
The edges represent the interconnection on which data can flow.
The information needed to be associated with a node is the lowest
user security level for which some user on the node is cleared,
as well as the highest security level of labelled data at the
A new data structure is needed
to represent the paths that data can follow. Each data path is
represented by a directed edge or arc from the starting to the
ending node of the path. With each arc a pair (d,u) is
associated, where d is the security level of the data
at the beginning of the path, and u the security level
of the user at the end of the path. In a Cascading Vulnerability
path the proposition u<d holds true.
The algorithm (Horton, 1993)
begins by creating arcs for each edge in the graph in which u
and d are equal. In the sequel, the algorithm consists
of two main phases. In the first phase, all possible legal paths
through the network are found. A legal path is one for which du.
In the sequel, the use of the
Floyd-Warshall shortest path algorithm (Aho, 1974) is proposed.
In the second phase the new arcs represent illegal data paths
as well as legal data paths. The new step in this phase, is the
answer of the question whether the TCB rating of node i
allows the accreditation range of the arc(j, k). If it
does, then the path corresponding to the new arc is not a Cascading
Vulnerability path. If it does not, then the path from which this
arc is constructed is a Cascading Vulnerability path.
A Cascade Vulnerability correction
algorithm should include suggestions for these network modifications
which eliminate or reduce the risk of Cascade vulnerability. (Horton,
1993) supports the idea that an algorithm that solves the Cascade
Vulnerability correction problem would also solve the vertex cover
problem for planar graphs (which is known to be intractable).
Based on the above, the Cascade Vulnerability correction problem
appears to be NP-hard. The detection algorithm shows that the
correction problem is in NP, and hence the problem is NP-complete.
Thus, an efficient algorithm that would give the optimal solution
is not expected to be found.
It is only possible that by
using generalised techniques (e.g. ILP-Integer Linear Programming)
a reasonable initial network could be defined, with all known
constraints incorporated; this network could then be modified
as unfullfilled requirements are identified.
Although solving integer linear
programs problems is also NP-complete, there are efficient techniques
which give acceptable solutions. The multiple-path problem can
be stated as an ILP as follows:
p is a Cascading path in the network
n is a node in the network
s is the TCB rating for a system
cn,s is the cost of upgrading node n to rating s
n,s p means that upgrading node n to TCB rating s would correct path p
is a variable that is either 1 (node n is to be upgraded
to TCB rating s) or 0 (node n is not to be upgraded to
TCB rating s).
Minimise cn,s xn,s , subject to xn,s1, p
The basic disadvantage of Horton's
algorithm is that not all pairs of nodes connected by Cascading
Vulnerability paths are found. However, if all the pairs of nodes
connected by Cascading Vulnerability paths that are found are
corrected, then all the Cascading Vulnerability paths are corrected.
Any unreported Cascading Vulnerability path will contain all of
some reported Cascading Vulnerability path.
3.5 Algorithms comparative
As stated above, the Horton
algorithm has reduced time-complexity O(an3)
as compared to O(a3n3) for the (Fitch, 1991) algorithm. The space-complexity
for the (Horton, 1993) algorithm is O(an2) as compared to O(a2n2)
for the (Fitch, 1991) (Fitch, 1993) algorithm. In (Millen, 1990)
the resistance of all paths in the network is calculated by a
matrix computation which requires O(N3log2N) steps.
A common problem to (Fitch,
1991) (Fitch, 1993) (Horton, 1993) is the following: if there
are multiple Cascading Vulnerability paths between a pair of nodes,
then only one of the paths will be detected in the straightforward
version of the algorithm.
However, the (Horton, 1993)
algorithm does not handle partially-ordered security levels, as
the (Fitch, 1991) (Fitch, 1993) (Millen, 1990) algorithms do.
A network of computers is exposed
to the Cascade Vulnerability 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.
Many efficient algorithms have
been proposed in the literature to deal with the Cascade Vulnerability
detection. In the previous sections, the basic properties of the
most important algorithms were reviewed. A brief comparative analysis
of them followed, and the Cascade Vulnerability correction problem
(e.g. to remove all Cascading Vulnerability paths from a network
for a given cost, under restrictive conditions) was shown to be
Possible future work could
focus on finding reasonable approximation heuristic procedures
for the Cascade Vulnerability correction problem.
Aho. A., Hopcroft J., Ullman
J., (1974) The Design and Analysis of Computer Algorithms,
Addison-Wesley, Reading, MA.
Department of Defence (1985)
Trusted Computer System Evaluation Criteria, DOD 5200.28-STD.
Fitch J.A. III, Hoffman L.J.,
(1991) The Cascade problem: Graph Theory can help, Proceedings
of the 14th National Computer Security Conference, pp. 88-100.
Fitch J.A. III, Hoffman L.J.,
(1993) A shortest path network security model, Computers and
Security, Vol. 12, pp. 169-189.
Freund J. E., (1962) Mathematical
Statistics, Prentice Hall, Englewood Cliffs, N.J.
Lee T. M. P., (1989) Statistical
models of trust: TCBs vs. People, Proceedings of the IEEE Symposium
on Security and Privacy, pp. 10-19.
Madron T., (1990) Network
Security in the 90's: Issues and Solutions for Managers, J.
Wiley & Sons, Inc.
Millen J. K., (1988) Interconnection of Accredited Systems, The MITRE Corporation, M88-8, February 1988.
Millen J. K., Schwartz M.W.,
(1988) The Cascading problem for interconnected networks, Proceedings
of the Fourth Aerospace Computer Security Applications Conference,
Millen J. K., (1990) Algorithm
for the Cascading problem, in J.P.Anderson ed., Internet IEEE
Cipher News Group, June 25 IEEE Cipher Forum on dockmaster.ncsc.mil.
National Computer Security
Center, (1985) Technical Rationale Behind CSC-STD-003-85: Computer
Security Requirements, CSC-STD-004-85, National Computer Security
National Computer Security
Center, (1987) Trusted Network Interpretation of the Trusted
Computer System Evaluation Criteria, Red Book NCSC-TG-005,
Library No. S228, 526, Version 1, National Computer Security Center,