The Complexity and Composability of Secure Interoperation^{∗}

Li Gong and Xiaolei Qian

SRI International Computer Science Laboratory

333 Ravenswood Avenue Menlo Park, California 94025 U.S.A.

{gong,qian}@csl.sri.com

Abstract

Advances in distributed systems and networking technology have made interoperation not only feasible but also increasingly popular. We define the interoperation of secure systems and its security, and prove complexity and composability results on obtaining optimal and secure interoperation. Most problems are NP-complete even for systems with very simple access control structures. Nevertheless, composability reduces complexity in that secure global interoperation can be obtained incrementally by composing secure local interoperation. We illustrate, through an application, how these theoretical results can help system designers in practice.

1 Introduction

Recent advances in distributed systems and networking technology have made interoperation not only feasible but also increasingly popular. For example, heterogeneous databases can be linked by highspeed networks that consist of heterogeneous networks connected by gateways. In such an application environment, heterogeneity (such as in data semantics, data representation, and communication protocol) among system components must be reconciled properly. Some research efforts are under way to deal with these problems [SL90].

One attribute of interoperation that needs reconciliation but has not been closely studied is security with regard to access control. Consider an application involving multiple systems dealing with commerce (e.g., national credit databases), finance (e.g., stock market information systems), medicine (e.g., patient records), and defense, each having a distinct access control structure. To facilitate information exchange among such systems, some mapping between the heterogeneous security attributes must be introduced, for example, by the system administrators. Current practices show that these mappings, even if chosen carefully, can result in security breaches that previously did not exist in any individual system (e.g., [U.S87, U.S90]).

Secure interoperation is a serious concern for military systems^{1} as well as commercial ones. For example, consider the information system of a major research organization where Alice, being a project supervisor, is allowed access to Bob’s files, but not vice versa. Suppose that this organization has just been purchased by a corporation where Charles is Vice President for research and Diana, being his secretary, has access to his files. After the merger, it seems natural to permit Charles to access Alice’s project papers. But if Bob should be allowed access to Diana’s file cabinet, there would be a security violation because now Bob would potentially have access (indirectly via Diana and Charles) to Alice’s files to which he should be denied access.

Although the security violation in this example may not be too difficult to remove, a real-world system could have hundreds or thousands of entries in its access control list so that choosing a secure yet satisfactory (e.g., with maximum data sharing) mapping between many such access control lists is a daunting task. In other words, interoperation of systems with heterogeneous access control structures poses the following new challenges: what is the definition of secure interoperation? How can security violations be detected? And how can these violations be removed while a maximum amount of information exchange is still facilitated? This paper attempts to answer some of these questions. First we turn to what we think are the fundamental requirements in secure interoperation.

∗This work was supported in part by the U.S. Department of Defense Advanced Research Projects Agency and U.S. Air Force Rome Laboratory under Contract F30602-92-C-0140.

1It is estimated in the Defense Information Systems Agency’s Defense Information System Network Technology Requirements Document, version 0 (August 3, 1993) that the U.S. DoD enterprise has more than 10,000 networks worldwide, most of which are not interoperable with each other and do not adequately support information sharing.

2 Principles of Secure Interoperation

One essential feature in federated systems is the autonomy of an individual system – each system may be administrated independently [BGS92, SL90]. To preserve this feature in secure interoperation, autonomy in security must be guaranteed.

Principle of Autonomy. Any access permitted within an individual system must also be permitted under secure interoperation.

On the other hand, interoperation should not violate the security of an individual system.

Principle of Security. Any access not permitted within an individual system must be also denied under secure interoperation.

All other new access introduced by interoperation should be permitted unless explicitly denied by the specification of secure interoperation. Note that, unless specified otherwise, by access we mean direct or indirect access.

It is conceivable that under some circumstances a system may be willing to sacrifice some of its autonomy.

3 System Model and Terminology

In our discussion, the security attributes of a system are expressed with an access control list (ACL) [Lam71]. We view a system as a collection of users, machines, data objects, and others, each being a distinct unit with regard to security.

The task we are facing is the following: given a set of access control lists that are individually secure, define what secure interoperation is, and investigate the complexity of detecting security violations in the global system and that of removing security violations while maintaining a reasonable level of interoperation.

It has been previously shown that the security of any given access control list is in general undecidable [HRU76], and some variations of the decision problem are at best NP-complete [San92]. Therefore, we also expect to obtain NP-completeness results and thus follow the general proof method for NP-completeness to investigate only a restricted problem where in each ACL: (1) each subject owns exactly one file, with read and write access; (2) a subject can have only read access to a file owned by someone else; (3) if a subject can read another’s file, the latter cannot read the former’s file; (4) an ACL is static in that read and write are the only types of access specified.

Our NP-completeness results should imply similar NP-completeness results for formations of the problem using more general access control lists. In addition, given the particular restrictions on ACL, our results should also imply NP-completeness results for the interoperation of Bell-LaPadula (e.g., [Lan81]) type multilevel secure systems, although our study is not specially aimed at multilevel security either in the sense of Bell-LaPadula or that of noninterference (e.g., [GM82]).

In our discussion, we use the following terminology, notations, and definitions. Because one subject owns exactly one file, there is no need to distinguish between a subject and its file. For example, instead of saying that Alice has access to Bob’s file, we can simply say that Alice has access to Bob. We call this combination of a subject and its file an entity. Moreover, it is obvious that one entity has access to oneself (i.e., one’s own file), and if Alice can access Bob, and Bob can access Charles, then Alice can access Charles indirectly. Recall that one restriction on the ACL is that if Alice can access Bob then Bob cannot access Alice, we arrive at the following definition of a secure system as specified with a restricted ACL.

Definition 1 (Secure System) A secure system is an ACL in the form of G =< V, A > where V is a set of entities and A is a binary relation “access” on V that is reflexive, transitive, and antisymmetric.

Graphically, we can view a system as an acyclic directed graph. V is the set of vertices and A is the set of arcs – there is an arc leading from vertex u to v, denoted by (u, v), if and only if A contains the binary relation “u access v”. The direction of the arc is then the direction of the permitted “access”.

Thus, for the merger example, we have Res =< {Alice, Bob, Eve}, {(Alice, Bob), (Eve, Alice)} >, and Com =< {Charles, Diana, F red}, {(Charles, F red), (Diana, Charles)}. The graphical representation of both systems is in Figure 1.

D C F A E B

Figure 1: Two Separate Systems

For convenience, we sometimes do not distinguish between an ACL and its graphical representation if no confusion can arise.

We say that an access (u, v) is legal in G (or in A) if and only if there is a directed path in (the graphical representation of) G leading from u to v. We denote this with (u, v) ∝ G.

Suppose we have n secure systems, G_{i} =< V_{i}, A_{i} >, i = 1, 2, …, n, and for simplicity, we assume that all entities are distinctly named – that is, V_{i} ∩ V_{j} = ∅, i ≠ j. To facilitate interoperation, mappings between entities of different systems must be introduced to reflect the desired data sharing through interoperation. Such mappings can be represented by a set of cross-system “access” relations F, which is chosen possibly by an administrator with global security responsibility or by a select committee in charge of the individual systems.

Definition 2 (Permitted Access) Permitted access is a binary relation F on ∪_{i=1}^{n}V_{i} where ∀(u, v) ∈ F, u ∈ V_{i}, v ∈ V_{j}, and i ≠ j.

The fact that (u, v) ∈ F indicates that it is thought that entity u (in system G_{i}) should be allowed to access entity v (in system G_{j}). Note that it is possible to have both (u, v) ∈ F and (v, u) ∈ F.

In our example, suppose that it is decided that interoperation should allow Bob to access Fred (i.e., his file) and Charles to access Alice. Then the global system is in Figure 2 where arcs belonging to F are represented as dotted lines.

The interoperation may also mandate a set of restricted access R, as follows.

Definition 3 (Restricted Access) Restricted access is a binary relation R on ∪_{i=1}^{n}V_{i} such that ∀(u, v) ∈ R, u ∈ V_{i}, v ∈ V_{j}, and i ≠ j.

D C F B A E

Figure 2: Interoperation of Two Systems

This is similar to a negative entry in an access control list [Sat89]. The purpose is to explicitly safeguard certain parts of the system when the potential implications of introducing F are unclear. In our example, we may forbid access (Diana, Eve). R takes precedence over F.

To give the definition of secure interoperation for a federated system Q =< W, B >, recall that the autonomy principle requires that a legal access in A_{i} remain legal in B, i.e., if (u, v) ∝ A_{i} then (u, v) ∝ B. On the other hand, the security principle requires that an illegal access in A_{i} remain illegal in the interoperation, i.e., if (u, v) ∝̸ A_{i} then (u, v) ∝̸ B. In addition, all access in R should be explicitly restricted – that is, B ∩ R = ∅ (the empty set).

Definition 4 (Secure Interoperation) Q is a secure interoperation if B ∩ R = ∅, and ∀u, v ∈ V_{i}, (u, v) ∝ A_{i} if and only if (u, v) ∝ B.

F and R may contradict each other, and other security violations can also occur as a result of interoperation. As illustrated in Figure 3, Bob can access Alice indirectly through Diana, which is illegal within the research organization.

In situations like this, F may need to be changed or reduced to remove security violations (recall that R takes precedence over F). Thus, given G_{i}, i = 1, …, n, F, and R, our aim is to find a federated system Q =< W, B >, where W = ∪_{i=1}^{n}V_{i} and B ⊆ (∪_{i=1}^{n}A_{i}∪F)−R, such that Q is a secure interoperation.

D C E B A  F a b c d

Figure 3: Security Violation Caused by Interoperation

4 Complexity

For convenient discussion, we mark all arcs belonging to G_{i}, i = 1, …, n, green, mark all arcs in the permitted access set F purple, and mark all arcs in the restricted access set R red.

The first problem we encounter is to decide if a given interoperation is secure.

Problem 1 (Security Evaluation) Given G_{i} =< V_{i}, A_{i} >, i = 1, …, n, permitted access F, and restricted access R. Is < ∪_{i=1}^{n}V_{i}, (∪_{i=1}^{n}A_{i} ∪ F) − R > a secure interoperation?

Theorem 1 Security evaluation is in P.

Proof. We prove the theorem by giving a polynomial-time algorithm to detect security violations. Let A_{i}^{+} denote the transitive closure of A_{i}, and B^{+} denote the transitive closure of B = (∪_{i=1}^{n}A_{i} ∪ F) − R. The algorithm is as follows.

First, check that B ∩ R is an empty set. Then, compute B^{+} and A_{i}^{+}, i = 1, …, n, and check that B^{+} induced by V_{i} is a subset of A_{i}^{+}. If any checking fails, report security violation; otherwise, report secure. The correctness of the algorithm is obvious, noting that the definition of B automatically satisfies the autonomy requirement.

The complexity of the algorithm is the complexity of calculating the transitive closures O(| ∪_{i=1}^{n}V_{i} |^{3}) plus the complexity of the comparisons O(| ∪_{i=1}^{n}V_{i} |^{3}), so an upper bound is O(| ∪_{i=1}^{n}V_{i} |^{3}). □

If B = (∪_{i=1}^{n}A_{i} ∪ F) − R is insecure, we can remove the security violations by reducing F until the resulting interoperation is secure. In other words, find S ⊆ F such that C = (∪_{i=1}^{n}A_{i} ∪S)−R is secure. This is trivial because S = ∅ is definitely a secure solution. To find nontrivial secure solutions, one choice is to find a secure solution that includes all other secure solutions. In other words, find S ⊆ F such that C = (∪_{i=1}^{n}A_{i} ∪S)−R is secure and, for any secure solution T, T ⊆ S. Unfortunately, such solutions do not always exist, as is shown by the following counterexample.

Consider the interoperation of systems G_{1} =< {a1, a2, a3}, {(a1, a2), (a2, a3)} > and G_{2} =< {b1, b2, b3}, {(b1, b2), (b2, b3)} >, as illustrated by Figure 4. Suppose F = {(b3, a2), (a3, b2)}, which obviously causes a security violation because access (a3, a2) is legal in the federated system but illegal in G_{1}. One secure solution is S_{1} = {(a3, b2)}. Another secure solution is S_{2} = {(b3, a2)}. But any solution containing both S_{1} and S_{2} contains F, which causes a security violation.

a3 a2 a1  b3 b2 b1

Figure 4: All-Inclusive Solutions May Not Exist

An alternative in finding nontrivial secure solutions is to look for solutions that cannot be expanded any further. In other words, find a secure solution S ⊆ F such that, for any secure solution T, S ⊈ T. This problem is in P, as the following polynomial-time algorithm demonstrates: start with an empty solution S; add elements in F to S one by one, and only if the addition will not cause a security violation (recall that security evaluation is in P); repeat this process until no more elements can be added. The correctness of this algorithm is obvious.

The three choices described so far do not give natural optimality measures. For example, a solution may turn out to contain just one arc from F although the exclusion of this single arc would allow the addition of two other arcs, with the latter intuitively facilitating more information exchange.

Therefore, we propose two definitions that are more natural. From now on, we stipulate that F ≠ ∅ because the secure interoperation problem disappears when F = ∅ (and thus R = ∅).

One natural optimality measure is to maximize direct information sharing. Take the interoperation represented in Figure 3, for example. Arcs a and d (or c and d) cause a security violation. To reduce a minimum number of arcs from F, it is better to remove d so that both a and c can be preserved.

Problem 2 (Maximum Secure Interoperation) For any positive integer K ≤| F |, is there a secure solution S such that S ⊆ F and | S |≥ K?

Theorem 2 Maximum secure interoperation is NPcomplete.

Proof. The problem belongs to NP because a nondeterministic machine can guess a solution at random and verify its autonomy and security properties in polynomial time (refer to Theorem 1 on security evaluation).

The rest of the proof is to reduce a known NPcomplete problem, the Feedback Arc Set problem [GJ79, p.192], to a restricted case of our problem at hand. We first review the Feedback Arc Set problem:

Given a directed graph G =< V, A >, positive integer K ≤| A |. Is there a subset A′ ⊆ A with | A′ |≤ K such that A′ contains at least one arc from every directed cycle in G?

The restricted case of Problem 2 is when all individual systems are of the form G_{i} =< {u_{i}, v_{i}}, {(u_{i}, v_{i})} >, F contains no direct cycles, and R = ∅. Here, the only type of security violation is a directed cycle (in the federated system) containing a green arc (u_{i}, v_{i}), because access from v_{i} to u_{i} would become possible. Moreover, any cycle must contain at least a green arc because there are no red arcs and no all-purple cycles.

Our reduction, shown in Figure 5, is as follows. Given any G =< V, A >, we define G′ =< V′, A′ > as follows. V′ is formed by splitting every vertex u in V into a pair of vertices u_{1} and u_{2}. We add an arc (u_{1}, u_{2}), and let C denote the set of all such arcs. Let < {u_{1}, u_{2}}, {(u_{1}, u_{2})} > denote an individual system. For every arc in A that ends at u, there is a corresponding arc in A′ that ends at u_{1}, and for every arc in A that departs from u, there is a corresponding arc in A′ that departs from u_{2}. Let F = A′. Clearly F does not contain any cycle.

G a b c  d e G’ u1 a b c  u2 u  d e

Figure 5: Reduction

Next we need to show that this reduction is a oneto-one mapping between the two problems in that A′′ is a solution for the Feedback Arc Set problem in G, with | A′′ |≤ K, if and only if S = (A′ − A′′) is a solution of maximum secure interoperation in G′, with | S |≥| A′ | −K.

Suppose A′′ is a solution for the Feedback Arc Set problem in G, then A′′ ⊆ A′ and | A′′ |≤ K. Let S = (A′ − A′′). S does not contain directed cycles in G, thus S ∪ C does not contain directed cycles in G′ either, because of the way arcs in C are added to G′. Therefore S does not cause a security violation. Moreover, since A′′ ⊆ A′, we have | S |=| (A′−A′′) |=| A′ | − | A′′ |≥| A′ | −K. Thus, S is a solution to maximum secure interoperation in G′.

On the other hand, suppose S is a solution to maximum secure interoperation in G′. Since S does not contain directed cycles, A′′ = A′ − S must contain at least one arc from each directed cycle in A′. Because S ⊆ A′ and | S |≥| A′ | −K, | A′′ |=| A′ − S |=| A′ | − | S |≤| A′ | −(| A′ | −K) = K. Therefore, A′′ is a solution to the Feedback Arc Set problem in G. □ For an NP-complete problem, one naturally seeks good approximation algorithms. We now prove that finding certain approximate solutions is also NPcomplete. Given a federated system G, we use A(G) to denote a solution obtained by an approximation algorithm, of size | A(G) |, and OP T (G) to denote the optimal solution, of size | OP T (G) |.

Corollary 1 If P ≠ NP, then no polynomial-time algorithm for the maximum secure interoperation problem can guarantee | A(G) | − | OP T (G) |≤ K for a fixed constant K.

Proof. Suppose to the contrary that X is indeed such an approximation algorithm. We show that X can be used to construct a polynomial-time algorithm Y that solves the maximum secure interoperation problem, which contradicts the assumption that P ≠ NP.

Given G and a positive integer K, our algorithm Y constructs G′ that consists of K + 1 isomorphic copies of G. It is easy to see that | OP T (G′) |= (K + 1)× | OP T (G) |. Furthermore, we can construct a solution for G with a size of at least | X(G′) | /(K + 1) merely by taking the isomorphic copy of G that has the largest solution among the (K + 1) copies. Thus, (K + 1)× | Y (G) |≥| X(G′) |.

Since X guarantees that | X(G′) | − | OP T (G′) |≤ K, we have | X(G′) | −(K + 1)× | OP T (G) |≤ K. Because (K + 1)× | Y (G) |≥| X(G′) |, we have (K + 1)× | Y (G) | −(K + 1)× | OP T (G) |≤ K, or | Y (G) | − | OP T (G) |≤ K/(K + 1). This means that | Y (G) |=| OP T (G) | and thus Y is a polynomialtime algorithm for the maximum secure interoperation problem, a contradiction. □

So far we have been working to find maximum subsets of F that result in secure interoperation, and Theorem 2 and its corollary suggest that this is hard.

Another natural measure of optimality is to maximize direct and indirect information sharing by working on the whole federated system. The aim is to find a secure interoperation with a maximum number of legal access, instead of looking for a secure solution F of a maximum size. That is, we can now change F as long as the new F does not introduce an access that is illegal under the initial set F.

Take the interoperation represented in Figure 3 again, for example. Arcs a and d (or c and d) cause a security violation. Previously, for a solution with maximum size, it was better to remove d so that both a and c could be preserved. Now to obtain maximum access, it is actually better to remove both a and c to preserve d because the latter facilitates more (albeit indirect) information sharing.

Problem 3 (Maximum-Access Secure Interoperation) For any positive integer K ≤| (∪_{i=1}^{n}A_{i} ∪ F)^{+} − R |, is there a secure interoperation < ∪_{i=1}^{n}V_{i}, B > such that B ⊆ (∪_{i=1}^{n}A_{i} ∪ F)^{+} − R and | B |≥ K?

Theorem 3 Maximum-access secure interoperation is NP-complete.

Proof. The problem obviously belongs to NP because a nondeterministic machine can guess a solution at random and verify its suitability in polynomial time (recall Theorem 1 that security evaluation is in P). Again, we reduce the Feedback Arc Set problem to a subproblem when each individual system is of the form G_{i} =< {u_{i}, v_{i}}, {(u_{i}, v_{i})} >. Our reduction is identical to that in the proof of Theorem 2, as shown in Figure 5, where | C |=| V |. We then compute the transitive closure of G′ and call it G′′ =< V′, (A′)^{+} >. We aim to prove that A′′ is a solution to the Feedback Arc Set problem in G if and only if B = (A′ − A′′) ∪ C forms a secure interoperation in G′′, with | B |≥| A′ | −K+ | V |.

In the set of arcs introduced by computing the transitive closure, namely ((A′)^{+} − A′ − C), if an arc is within one single system, then it must be of the form (u_{2}, u_{1}), which causes a security violation and thus cannot be present in any secure interoperation. Define R to be the subset of ((A′)^{+} − A′ − C) containing arcs that connect two different systems. This definition of R effectively removes from any secure interoperation all arcs added when computing the transitive closure, thus the rest of this proof is essentially the same as that of Theorem 2. □

Corollary 2 If P ≠ NP, then no polynomial-time algorithm for the maximum-access secure interoperation problem can guarantee | A(G) | − | OP T (G) |≤ K for a fixed constant K.

Proof. Similar to the proof of Corollary 1. □ The above results show that the problems we are investigating are NP-complete in general. Nevertheless, we have found a special case where finding an optimal solution takes only polynomial time.

Problem 4 (Simplified Maximum-Access Secure Interoperation) Suppose that every G_{i} is a total order, and graph < ∪_{i=1}^{n}V_{i}, F > is acyclic. For any positive integer K ≤| (∪_{i=1}^{n}A_{i} ∪ F)^{+} |, is there a secure interoperation < ∪_{i=1}^{n}V_{i}, B > such that B ∈ (∪_{i=1}^{n}A_{i} ∪ F)^{+} and | B |≥ K?

Theorem 4 Simplified maximum-access secure interoperation is in P.

Proof. We prove by constructing a polynomialtime algorithm to find the optimal solution. As before, we mark arcs in A_{i} green and arcs in F purple. We mark all the other arcs in (∪_{i=1}^{n}A_{i} ∪F)^{+} yellow. Since G_{i} is a total order and F does not contain directed cycles, a security violation occurs if and only if there is a directed cycle in the transitive closure G^{+} =< ∪_{i=1}^{n}V_{i}, (∪_{i=1}^{n}A_{i} ∪ F)^{+} >. Thus, our objective is to find the maximum acyclic subgraph of G^{+} that also contains all the green arcs (to preserve autonomy). In other words, we want to remove a minimum number of arcs in order to remove all cycles.

Note that in a transitive closure, the subgraph induced by all vertices on a cycle is a complete graph – where each pair of vertices is connected by arcs in both directions – so G^{+} can be viewed as a collection of complete graphs plus arcs between them. These “inbetween” arcs do not introduce cycles, thus any maximum interoperation must include them. Therefore, our task is reduced to finding in a complete graph the maximum subgraph that does not have cycles (since the number of such complete graphs in G^{+} is polynomial).

By induction, we can easily prove a lemma that for a complete graph of m vertices, the maximum acyclic subgraph (denoted as G(k)) contains exactly m(m − 1)/2 arcs. This is obviously true when m = 2 since m(m − 1)/2 = 1. Suppose the lemma is true for m = k. For m = k + 1, we argue that, after adding one more vertex to G(k), we can add exactly k arcs to form G(k + 1) without introducing cycles. First, we can add k arcs without introducing cycles: each new arc departs from an existing vertex and arrives at the new vertex. Second, if we add k + 1 arcs, then since G(k) contains only k vertices, there are at least two arcs connecting the new vertex and an existing vertex. These two arcs are necessarily in opposite directions and therefore form a cycle. Therefore, | G(k + 1) |=| G(k) | +k = k(k − 1)/2 + k = (k + 1)k/2.

Given the above lemma, we can arrange the vertices in a left-to-right line such that vertices in V_{1} are grouped together first, from left to right in descending order, so that a vertex can always “access” the one on its right side. Then vertices in V_{2} are similarly lined up, and so on. Under such an arrangement, all green arcs are in the direction of left to right. Therefore, we only need to delete all arcs pointing from right to left, which are either purple or yellow, and we have found a maximum acyclic subgraph that contains all the green arcs. The whole process is clearly in polynomial time. □

The above theorem is very encouraging and more polynomial-time solvable subcases would be desirable.

Next we turn to another related problem. Suppose that the initial interoperation is already secure, or that an approximate or optimal solution has been found.

Here the set F may contain some arcs that are redundant in the sense that data sharing provided by them is already provided by other permitted access. Therefore, it is quite natural to consider reducing the size of F as much as possible.

Problem 5 (Minimum Representation) For any positive integer K ≤| F |, is there a subset F′ ⊆ F such that | F′ |≤ K and that the set of legal access remains unchanged when F is replaced by F′?

Theorem 5 Minimum  representation  is

NP-complete.

Proof. The subproblem when all A_{i}, i = 1, …, n, and R are empty sets is identical to the known NP-complete problem, Minimum Equivalent Digraph [GJ79, p.198]. □ This result implies that, unless P=NP, any polynomial-time algorithm for finding a secure interoperation cannot guarantee to result in a minimum representation

Nevertheless, if we remove the constraint that reduction can take place only within F – that is, we ask if there is a F′ ⊆ ∪_{i=1,j=1,i≠j}^{n}V_{i} × V_{j} such that | F′ |≤ K and that the set of legal access remains unchanged when F is replaced by F′ – then the problem is equivalent to Transitive Reduction [GJ79, p.198], which is solvable in polynomial time. This type of reduction may be useful in a preprocessing step to reduce the problem space of any algorithm used subsequently. However, such a measure means that the setup of individual systems may be changed, which may not be desirable for other reasons.

5 Composability

To reduce the total complexity of finding maximum secure interoperation, one area for exploration is the topology of system interoperation. In some federated systems, for example, interoperation is accomplished by having a master system interacting with other systems in local interoperation [SL90]. We now prove that in such a configuration, the global interoperation is secure if and only if each local interoperation is secure.

Given systems G_{i} =< V_{i}, A_{i} >, i = 0, 1, …, n, where G_{0} is the master system, let G_{0,i} =< G_{0}, G_{i}, F_{i} > denote the local interoperation between G_{0} and G_{i} with permitted access set F_{i}, i = 1, …, n. The global system is thus G′ =< ∪_{i=0}^{n}V_{i}, (∪_{i=0}^{n}A_{i}) ∪ (∪_{i=1}^{n}F_{i}).

Problem 6 (Federated Secure Interoperation) Given secure G_{0,i}, i = 1, …, n. Is G′ secure?

Theorem 6 G′ is secure if and only if G_{0,i} is secure, i = 1, …, n.

Proof. Any local interoperation of a secure global interoperation is automatically secure. Thus we need only to show that the security of all the local interoperation guarantees the security of the global federated system. By two case studies, we show that, in the federated system, there cannot be a legal access that is illegal in either the master system G_{0} or a satellite system G_{i}.

Suppose there is an access (a, b) that is legal in the federation but is illegal in the master system G_{0}. Because any local interoperation is secure, the chain of access from a to b involves G_{0} and at least two other systems. As depicted in Figure 6, there must be an access chain from a in G_{0} to outside, which reenters G_{0} at some vertex c, goes out to G_{i}, and reenters G_{0} again leading to b.

ac?  Go bGi

Figure 6: Security Violation in G_{0}

Clearly access (a, c) must be illegal in G_{0} because otherwise access (a, b) would be legal in G_{0,i}, which contradicts the assumption that G_{0,i} is a secure local interoperation. But apparently (a, c) is legal in the federated system excluding G_{i}, thus after excluding G_{i}, the rest of the federation must still be insecure. By induction we can see that this implies that there exists an insecure local interoperation G_{0,j}, a contradiction. Similarly, suppose there is a access (a, b) that is legal in the federation but is illegal in some satellite system G_{i}, i ≠ 0. Again, the chain of access from a to b involves G_{0}, G_{i}, and at least another system. As depicted in Figure 7, there must be an access chain from a in G_{i} to c in G_{0}, which eventually leaves G_{0} at some vertex d to enter G_{i} at vertex b.

Gi  Go c ?  b a d

Figure 7: Security Violation outside G_{0}

Clearly access (c, d) must be illegal in G_{0} because otherwise access (a, b) would be legal in G_{0,i}, which contradicts the assumption that G_{0,i} is a secure local interoperation. But apparently (c, d) is legal in the federated system excluding G_{i}, thus after excluding G_{i}, the rest of the federation must still be insecure. By induction we can see that this implies that there exists an insecure G_{0,j}, a contradiction. □ This theorem implies that local secure interoperation, and thus local maximization, can be computed independently and in parallel.

Corollary 3 (Maximum Federated Secure Interoperation) G′ is a maximum secure interoperation if and only if G_{0,i} is a maximum secure interoperation, i = 1, …, n.

The two very positive results above indicate that in a star-like configuration, global (maximum) secure interoperation can be achieved in a distributed fashion, locally, and incrementally as more systems join the interoperation. We can thus say that (maximum) secure interoperation is composable. Note that these results do not necessarily imply that maximum-access secure interoperation is composable.

The proofs in Theorem 6 clearly extend to any configuration of a tree structure in that if all local interoperation between neighboring systems are secure or maximum, then the global interoperation is also secure or maximum.

Corollary 4 (General Federated Secure Interoperation) Secure interoperation and maximum secure interoperation are composable in any treestructure configuration.

In a ring-structure configuration (or any configuration containing a ring), the composability theorem does not always hold. A simple counterexample is when each F_{i} contains only one arc; thus, each local interoperation is secure, but the collection of these plus a green arc forms a cycle and permits an illegal access. The implication is that secure interoperation can be joined together as long as no ring is formed.

From the proof details, we expect that the above composability results generalize beyond the simple access control structure we have assumed in our current discussion.

6 An Application in Databases

An obvious application area is the interoperation of heterogeneous databases. As more secure databases are built and connected through computer networks, a wide variety of secure data sources is becoming accessible. One of the biggest challenges presented by this technology is the secure interoperation of databases containing data with mismatched access control structures [Per92]. Providing secure interoperation not only makes it possible to reliably share data in isolated military and civilian databases, but also increases users’ confidence and willingness in such sharing.

A key requirement in the interoperation of heterogeneous and especially legacy databases is autonomy [SL90]. Since these databases were often independently designed to each serve the needs of a single organization, and significant investment has already been made into them, the interoperation must respect their autonomy. Our definition of secure interoperation properly captures the autonomy requirement in security.

The interoperation of secure databases presents new requirements. While the concern in the interoperation of databases with homogeneous access control structures is how to maximize data sharing between databases, such maximization in the interoperation of databases with heterogeneous access control structures has to be tempered by security considerations. In other words, the data sharing caused by database interoperation should not compromise the security of individual databases. This requirement is also properly captured by our definition of secure interoperation.

Applying our complexity analysis to the autonomous and secure interoperation of heterogeneous databases with mismatched access control structures, we can see that the detection of security breaches in interoperation is easy, and the hard problem is the elimination of security breaches while maximizing data sharing. Although the general problem is not tractable, our results provide useful guidelines in solving this problem in practice. Some example guidelines are

• Although the general problem is NP-complete, the most common case in multilevel military databases, where access control structures form total orders, is polynomial-time solvable, as is shown by Theorem 4.

• Although solving the general problem involves examining globally all the interoperating databases and links between them, for the widely adopted case of federated database systems [SL90], in which all data sharing is carried out through the federated schema, the problem can be solved in a pairwise manner, as is shown by Theorem 6. This implies that the problem can be solved incrementally as new databases join the federation.

In addition, the interoperation of secure databases suggests other natural optimality measures, whose computational complexity we are studying now. For example, we might want to maximize the number of databases interoperable, thus an optimal solution might link as many databases as possible, even if the amount of data sharing is not necessarily maximized.

7 Related Work

Secure interoperation can in some sense also be viewed as composing secure systems. A number of composition methods have been proposed for building a large system out of secure components (e.g., [McC90]). These previous results are mostly focused on composing systems with identical or compatible security attributes or policies, and tend to fall in the category of multilevel security where the avoidance of covert channels is of paramount importance. We deal with secure interoperation of systems with heterogeneous security attributes, and the composition method we examine is a very natural one that has been used frequently in practice.

Another related work is a study of interoperation of multilevel secure databases [JW94], where the problem is security label translation. Like us, these researchers recognize that naive interoperation may cause security violations. They define a notion called relation consistency and propose a label insertion algorithm to achieve that. But unlike us, they do not provide any complexity or composability result.

In [Per92] a canonical security model was proposed for federated databases. The main concern was the integration of heterogeneous security policies and the specification of security constraints in a federated schema. However, the problem of detecting and eliminating security breaches in a federated schema was not considered.

8 Summary and Future Work

We have studied the problem of secure interoperation of systems with heterogeneous access control structures. We formed the definition of secure interoperation on the following basic notions: autonomy, which dictates that legal access in one system should remain legal in the global system, and security, which says that illegal access within one system should remain illegal in the global system. We proved that even for a very simple type of access control list, finding a secure solution with some optimality is NP-complete. Thus, finding similar optimal solutions for general access control lists can only be harder. These results, as shown by the application discussed, can help direct system design effort to searching for approximation algorithms and partial optimization, for example, by using heuristic algorithms.

For future work, one direction is to improve the theoretical results. This includes obtaining results on the hardness of obtaining percentage-wise approximation solutions, where some recent work [ALM^{+}92] may be helpful, and investigating other optimality measurements that are applicable to particular environments. We have so far assumed that R represents direct access that are undesirable, such as a negative entry in an access control list. This means that an indirect access may still be possible, as in the case of a typical discretionary access control scheme. If we interpret restricted access as banning both direct and indirect access, then similar theorems might be obtained. For example, Theorem 1 trivially holds. Theorem 2 (and its corollary) should also hold because its proof is about the subcase when R = ∅. Developing near-optimal algorithms, possibly probabilistic algorithms, to obtain good average-case performance is also desirable.

Another direction is to examine ways to distribute the process of removing security violations from a central control point to individual systems, for example, by defining interfaces that preserve security. This is analogous to the development of distributed concurrency control. We can also explore various topologies of system interoperation, as in Theorem 6. Another possibility is to divide the overall task of finding maximum secure interoperation into preprocessing and run-time processing, because the latter on average probably does not involve a large number of separate systems. This idea of delaying the decision to run time can have other benefits. For example, given two permitted access that together will violate security, instead of deciding somewhat arbitrarily to remove one, we can decide to keep the one that is first used during run time. This is similar to the Chinese Wall policy (e.g., [BN89]) where one access will automatically prohibit future access of another kind, but which access to prohibit is not decided in advance.

Acknowledgment

Our colleagues at SRI, Pat Lincoln, Teresa Lunt, and Peter Neumann provided valuable comments on drafts of this paper.

References

[ALM^{+}92] S. Arora, G. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof Verification and Hardness of Approximation Problems. In Proceedings of the IEEE 33rd Annual Symposium on Foundations of Computer Science, pages 14–23, Pittsburgh, Pennsylvania, October 1992.

[BGS92] J.A. Bull, L. Gong, and K.R. Sollins. Towards Security in an Open Systems Federation. In Proceedings of European Symposium on Research in Computer Security, volume 648 of Lecture Notes in Computer Science, pages 3–20, Toulouse, France, November 1992. Springer-Verlag.

[BN89] D.F.C. Brewer and M.J. Nash. The Chinese Wall Security Policy. In Proceedings of the IEEE Symposium on Security and Privacy, pages 206–214, Oakland, California, April 1989.

[GJ79] M.R. Garey and D.S. Johnson. Computers and Intractability. W.H. Freeman and Co., San Francisco, 1979.

[GM82] J.A. Goguen and J. Meseguer. Security Polices and Security Models. In Proceedings of the IEEE Symposium on Security and Privacy, pages 11–20, Oakland, California, April 1982.

[HRU76] M.A. Harrison, W.L. Ruzzo, and J.D. Ullman. Protection in Operating Systems. Communications of the ACM, 19(8):461– 471, August 1976.

[JW94] V.E. Jones and M. Winslett. Secure Database Interoperation via Role Translation. In B. Thuraisingham, R. Sandhu, and T. C. Ting, editors, Security for Object-Oriented Systems. Springer-Verlag, London, 1994.

[Lam71] B.W. Lampson. Protection. In Proceedings of the 5th Princeton Symposium on Information Sciences and Systems, Princeton University, March 1971. Reprinted in ACM Operating Systems Review, 8(1):18– 24, January, 1974.

[Lan81] C.E. Landwehr. Formal Models for Computer Security. ACM Computing Survey, 13(3):247–278, September 1981.

[McC90] D. McCullough. A Hookup Theorem for Multilevel Security. IEEE Transactions on Software Engineering, 16(6):563–568, June 1990.

[Per92] G. Pernul. Canonical Security Modeling for Federated Databases. In Proceedings of the IFIP TC2/WG2.6 Conference on Semantics of Interoperable Database Systems, November 1992.

[San92] R.S. Sandhu. The Typed Access Matrix Model. In Proceedings of the IEEE Symposium on Research in Security and Privacy, pages 122–136, Oakland, California, May 1992.

[Sat89]  M. Satyanarayanan.  Integrating Se-

curity in a Large Distributed System. ACM Transactions on Computer System, 7(3):247–280, August 1989.

[SL90] A. Sheth and J. Larson. Federated Database Systems for Managing Distributed, Heterogeneous, and Autonomous Databases. ACM Computing Surveys, 22(3):183–236, September 1990.

[U.S87] Trusted Network Interpretation. U.S. National Computer Security Center, July 1987. NCSC-TG-005 version-1.

[U.S90] Trusted Network Interpretation Environments Guideline. U.S. National Computer Security Center, August 1990. NCSC-TG-011 version-1.