The Cascade Vulnerability Problem for Distributed Systems: A Review

Stefanos Gritzalis
Department of Informatics University of Athens TYPA Buildings, Athens GR-15771, Greece tel.: +30-1-7291885, fax: +30-1-7219561

Department of Informatics Technological Educational Institute (T.E.I.) of Athens Ag.Spiridonos St. Aegaleo GR-12210, Greece tel.: +30-1- 5910974, fax.: +30-1-5910975 email: sgritz@teia.ariadne-t.gr

Sokratis K. Katsikas Department of Mathematics University of the Aegean Samos GR-83200, Greece tel.: +30-273-33919, fax: +30-273-35483 email: ska@aegean.gr

Diomidis Spinellis
Department of Mathematics University of the Aegean Samos GR-83200, Greece tel.: +30-273-33919, fax: +30-273-35483 email: dspin@aegean.gr

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.

1 INTRODUCTION

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 PROBLEM

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:

• the large size of the network
• different administrative entities, which may lead to different risk assessment methods.

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.

System A

TS		System B
S		S
		C

Figure 1. 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).

	Maximum Data Sensitivity
Minimum		U	N	C	S	TS	1C	MC
Clearance	U	C1	B1	B2	B3	*	*	*
or	N	C1	C2	B2	B2	A1	*	*
authorisation	C	C1	C2	C2	B1	B3	A1	*
of	S	C1	C2	C2	C2	B2	B3	A1
System	TS(BI)	C1	C2	C2	C2	C2	B2	B3
Users	TS(SBI)	C1	C2	C2	C2	C2	B1	B2
	1C	C1	C2	C2	C2	C2	C2	B1
	MC	C1	C2	C2	C2	C2	C2	C2

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

DETECTION

3.1 The Nesting and Cascade condition

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 are either:

• nested - one range is included in the other
• disjoint - have no common level.

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

• s1=s2 and h1 sends information to h2 at level s1 - a network link
• h1=h2 - an information flow within a component.

In the second case, if also s1s2, then the information transfer is permitted by the enforced security policy in this specific node. A downgrade is a flow such that s1>s2.

A downgrade from s1 to s2 is always associated with a risk index R(s1,s2). If s1s2, then R(s1,s2)=0, otherwise R(s1,s2)>0. 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:

• nested, if either AB or BA.
• strictly ordered, if (for every aA and bB) then a<b
• incomparable, if for every (aA and bB) neither ab nor ba

For a certain path (h1,s1), (h2,s2),..., (hn,sn), 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 at all.

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 the problem.

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):

1. Create a Network Table listing all components within the network. This table should include the following information for every component: Component ID, Evaluation Class, Range of security classifications at which the component sends data to the network, List of security classifications at which the component receives data from the network, Maximum of (highest level of data received from network, highest level of data processed by component), Minimum of (clearance of the user with the lowest clearance of the users with direct access to the component, lowest level of data sent to the network from the component).

2. Produce three tables: a Network Table Evaluation Class, a Network Table Maximum and a Network Table Minimum. The Network Table Evaluation Class will be the highest evaluation class of any component listed in the table. The Network Table Maximum will be the maximum of the Maximum associated with all the components listed in the table which send data to the network. The Network Table Minimum will be the minimum of the Minimum's associated with all the components listed in the table which receive data from the network.

3. If the Network Table Evaluation Class is greater than B1, then tables for each evaluation class lower than the Class of the Network Table, must be produced, down to tables for the C1 class. These tables will be produced for each evaluation class by first listing any one component whose evaluation class is less than or equal to the evaluation class for the table. Then add to the table all components that meet all of the following conditions:
   • - They have an evaluation class less than or equal to the class of the table
   • - They receive data from the network at a level that is being sent by a component who is already in the table
   • - They send data to the network at a level that is equal to or less than any node already in the table.
     
4. After all the tables have been constructed, then the Network Table Evaluation Class of each table is compared to the Maximum and Minimum for the Table with regard to the rules specified by the Environmental Guidelines.

5. If all Tables satisfy the assurance requirements for the Environmental Guidelines then the Network passes the assurance requirements. If any of the Tables provide a greater risk index than is permitted by the Environmental Guidelines then the Network provides a high level of risk, and should not be connected as currently designed.

The reader can find an analytical application of the heuristic procedure in an example in (NCSC, 1987).

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 problem.

The resource-constrained shortest path is based on three phases: Preprocessing, Shortest path calculation and Postprocessing.

1. The Preprocessing step consists of the following actions:
   • Defining the Cascade Vulnerability problem as a graph by identifying nodes, edges, and weights.
   • Viewing the problem from the penetrator's perspective by allocating the penetrator a set of resources
   • Defining the resource consumption function that determines how the network consumes the penetrator's resources.

2. The Shortest path calculation step determines the paths through the graph that minimise the cost to the penetrator under the consumption function. The Shortest path calculation step may require careful selection of the algorithm or algorithms used so that the path calculation is computationally efficient. The appropriate selection may be based on the size of the network problem, the user-defined consumption function, and whether the penetrator's resources are scalar (e.g. money), or vector (e.g. (money, time))

3. The Postprocessing step analyses the shortest path results to determine the network security metric. For some applications, determining that the network is not secure may require rearchitecting the network connectivity and reiterating the model steps.

In this approach, the algorithm is flexible in two ways:

• There is a wide choice of what is meant by cost. In the standard Cascade Vulnerability problem the cost of a path is defined by the maximum TCB rating of a machine on the path at which the security level of the data is compromised by illegally downgrading it to a lower security level. This makes the conservative assumption that once one machine of a given TCB rating is penetrated, then all others of equal or lower rating can be penetrated easily. However, the cost could also be defined as the sum of the costs of defeating the security protection mechanisms of all computers on the path independently.

• There is a flexibility for the choice of which shortest path algorithm to use. In (Fitch, 1991) (Fitch, 1993) it is apparent that the Floyd-Warshall all-pairs algorithm (Aho, 1974) was intended to be used. This algorithm has a very good worst-case complexity to solve the all-pairs shortest path problem. However the Dijkstra single-source algorithm (Aho, 1974) could also be used. This algorithm is generally faster for sparse graphs, like the computer network, so it is possible to implement the current algorithm using a somewhat faster algorithm than which is suggested in (Fitch, 1991) (Fitch, 1993).

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 node.

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

xn,s 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).

Then

Minimise cn,s xn,s , subject to xn,s1, p

n,s n,sp

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 effectiveness analysis

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.

4 CONCLUSIONS

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 NP-complete.

Possible future work could focus on finding reasonable approximation heuristic procedures for the Cascade Vulnerability correction problem.

5 REFERENCES

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, pp. 269-273.

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 Center, USA.

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, USA.