16.2 Nonlattice Information Flow Policies

Denning [267] identifies two requirements for information flow policies. Both are intuitive. Information should be able to flow freely among members of a single class, providing reflexivity. If members of one class can read information from a second class, they can save the information in objects belonging to the first class. Then, if members of a third class can read information from the first class, they can read the contents of those objects and, effectively, read information from the second class. This produces transitivity. The Bell-LaPadula Model exhibits both characteristics. For example, Cathy dom Betty, and Betty dom Anne, then Cathy dom Anne.

However, in some circumstances, transitivity is undesirable.

EXAMPLE: Betty is a confidante of Anne, and Cathy is a confidante of Betty. Hence, information can flow from Anne to Betty, and from Betty to Cathy. Anne confides to Betty that she is having an affair with Cathy's significant other. Needless to say, it is not desirable that this information flow directly from Anne to Cathy.

If information flow throughout a system is not transitive, then Denning's lattice model of information flow cannot represent the system. But such systems exist, as pointed out above. Lattices may not even model transitive systems.

EXAMPLE: Two faculty members are co-principle investigators of a grant. Graduate students report to both faculty members, and graduate students supervise undergraduate students on the project. The faculty members have equal power, neither being able to overrule the other. Clearly, information flows from the undergraduates to the graduates, and then on to the faculty members, so the system is transitive. But the graduate students have no single least upper bound, because both faculty members dominate them and there is no entity that dominates both faculty members. Hence, the information flow relations in this system do not form a lattice.

We generalize the notion of a confidentiality policy. An information flow policy I is a triple I = (SC_I, _I, join_I), where SC_I is a set of security classes, _I is an ordering relation on the elements of SC_I, and join_I combines two elements of SC_I.

EXAMPLE: Denning's lattice model for the Bell-LaPadula Model has SCI as the set of security compartments, I as the relation dom, and joinI as the relation least upper bound.

We now present a model of information flow that does not require transitivity and apply it to two cases in which the information flow relations do not form a lattice. In the first case, the relations are transitive; in the second, they are not.

16.2.1 Confinement Flow Model

Foley [362] presented a model of confinement flow. Assume that an object can change security classes; for example, a variable may take on the security classification of its data. Associate with each object x a security class x.

Definition 16–3. [362] The confinement flow model is a 4-tuple (I, O, confine, ) in which I = (SC_I, _I, join_I) is a lattice-based information flow policy; O is a set of entities; : O x O is a relation with (a, b) if and only if information can flow from a to b; and, for each a O, confine(a) is a pair (a_L, a_U) SC_I x SC_I, with a_{L I}a_U, and the interpretation that for a O, if x a_U, information can flow from x to a, and if a_L x, information can flow from a to x.

This means that a_L is the lowest classification of information allowed to flow out of a, and a_U is the highest classification of information allowed to flow into a.

The security requirement for an information flow model requires that if information can flow from a to b, then b dominates a under the ordering relation of the lattice. For the confinement flow model, this becomes

( a, b O)[ a b a_{L I} b_U ]

EXAMPLE: Let a, b, and c O. Define confine(a) = [ CONFIDENTIAL, CONFIDENTIAL ] confine(b) = [ SECRET, SECRET ] confine(c) = [ TOPSECRET, TOPSECRET ] The possible information flows are a b, a c, b a, b c, c a, and c b. If only secure flows (those meeting the security requirement of the confinement flow model) are allowed, then a b, a c, and b c are the legal flows (because aL IbU, aL IcU, and bL I cU). Thus, transitivity holds. Now consider x, y, and z. These three variables can assume values of different classifications: confine(x) = [ CONFIDENTIAL, CONFIDENTIAL ] confine(y) = [ SECRET, SECRET ] confine(z) = [ CONFIDENTIAL, TOPSECRET ] The possible information flows are x y, x z, y x, y z, z x, and z y. If only secure flows are allowed, then x y, x z, y z, and z x are the legal flows. But information cannot legally flow from y to x, because yL IxU is false. Hence, transitivity fails.

This model exhibits weak tranquility. It also binds intervals of security classes, rather than a single security class (as in the Bell-LaPadula Model). The lattice of security classes induces a second lattice on these intervals (see Exercise 2).

16.2.2 Transitive Nonlattice Information Flow Policies

Consider a company in which line managers report income to two different superiors—a business manager and an auditor. The auditor and the business manager are independent. Thus, information flows from the workers to the line managers, and from the line managers to the business manager and the auditor. This model is reflexive (because information can flow freely among entities in the same class) and transitive (because information can flow from the workers to the business manager and auditor). However, there is no way to combine the auditor and the business manager, because there is no "superior" in this system. Hence, the information flow relations do not form a lattice. Figure 16-1 captures this situation.

Definition 16–4. A quasi-ordered set Q = (S_Q, _Q) is a set S_Q and a relation _Q defined on S_Q such that the relation is both reflexive and transitive.

The company described above forms a quasi-ordered set. Handling the information flow now becomes a matter of defining a lattice that includes the quasi-ordered set. For all x S_Q, let f(x) = { y | y S_Q y _Q x }. Define the set S_QP = { f(x) | x S_Q } and the relation _QP = { (x, y) | x, y S_QP x y }. Then S_QP is a partially ordered set under _QP. f preserves ordering, so x _Q y if and only if f(x) _QP f(y).

Denning [267] describes how to turn a partially ordered set into a lattice. Add the sets S_Q and Ø to the set S_QP. Define ub(x, y) = { z | z S_QP x z y z } (here, ub stands for "upper bound," which contains all sets containing all elements of both x and y). Then define lub(x, y) = ub(x, y). Define the lower bound lb(x, y), and the greatest lower bound glb(x, y) similarly. The structure (S_QP {S_Q, Ø}, _QP) is now a lattice.

At this point, the information flow policy simply emulates that of the containing lattice.

16.2.3 Nontransitive Information Flow Policies

Foley [362] has considered the problem of modeling nontransitive systems. He defines a procedure for building lattices from such systems. His procedure adds entities and relations to the model, but the procedure keeps the nontransitive relationships of the original entities and relations intact.

EXAMPLE: A government agency has the policy shown in Figure 16-2. It involves three types of entities: public relations officers (PRO), who need to know more than they can say publicly; analysts (A); and spymasters (S). The accesses of the three types of entities are confined to certain types of data, as follows. confine(PRO) = [public, analysis] confine(A) = [analysis, top-level] confine(S) = [covert, top-level] Figure 16-2. An example of a government agency information flow policy. Public information is available to all. All other types of information are restricted, with analysis data and covert data (about secret missions) being distinct types of data. Top-level data is synthesized from both covert and analysis data. According to the confinement flow model, PRO A, A PRO, PRO S, A S, and S A. But covert data cannot flow to the public relations officers; S A and A PRO do not imply S PRO. The system is not transitive. Government (and private) agencies often use procedures to insulate public relations officers from data that is not to be leaked. Although the agency may trust the public relations officers, people make mistakes, and what the officers don't know, they cannot accidentally blurt out. So the example is realistic.

Definition 16–5. Let R = (SC_R, _R, join_R) represent a reflexive information flow policy. A dual mapping (l_R(x), h_R(x)) maps R to an ordered set P = (S_P , _P):

l_R: SC_R S_P with l_R(x) = { x }

h_R: SC_R S_P with h_R(x) = { y | y S_P y _R x }

The relation _P indicates "subset," and the elements in S_P are the set of subsets of SC_R. The dual mapping is called order preserving if and only if

(a, b SC_R) [a _R b l_R(a) _P h_R(b) ]

The set S_P formed by the dual mapping of a reflexive information flow policy is a (possibly improper) subset of the power set of SC_R. It is a partially ordered set. Denning's procedure, discussed above, can transform this into a lattice. Hence, without loss of generality, we can assume that the set P = (S_P , _P) is a lattice.

An order-preserving dual mapping preserves the ordering relation under the transformation. It also preserves nonorderings and hence nontransitivity. We now have:

Theorem 16–1. A dual mapping from a reflexive information flow policy R to an ordered set P is order-preserving.

Proof Let R = (SC_R, _R, join_R) be an information flow policy and let P = (S_P , _P) be an ordered set. Let (l_R(x), h_R(x)) be the dual mapping from R to S_P . Let a, b SC_R.

() Let a _R b. By Definition 16–5, a l_R(a) and a h_R(b). Thus, l_R(a) h_R(b), or l_R(a) _P h_R(b), as claimed.

() Let l_R(a) _P h_R(b). By Definition 16–5, l_R(a) h_R(b). Because l_R(a) = { a }, this means that a h_R(b). Thus, a S_P and a _R b, as claimed.

We can now interpret the information flow policy requirements. Let

confine(x) = [ x_L, x_U ]

and consider class y. Then information can flow from x to an element of y if and only if x_{L R} y, or l_R(x_L) h_R(y). Information can flow from an element of y to x if and only if y _Rx_U, or l_R(y) h_R(x_U).

EXAMPLE: Return to the government agency with the policy shown in Figure 16-2 and the entity types discussed in the preceding example. Call this policy R. We have the following flow relationships among the security classes. public R public   public R analysis analysis R analysis public R covert covert R covert public R top-level covert R top-level analysis R top-level top-level R top-level The dual mapping elements lR and hR are lR(public) = { public } hR(public) = { public } lR(analysis) = { analysis } hR(analysis) = { public, analysis} lR(covert) = { covert } hR(covert) = { public, covert} lR(top-level) = { top-level } hR(top-level) = { public, analysis, covert, top-level } Let p, a, and s be entities of the types PRO, A, and S, respectively. In terms of P, they are confined as follows. confine(p) = [ { public } , { public, analysis} ] confine(a) = [ { analysis }, { public, analysis, covert, top-level } ] confine(s) = [ { covert }, { public, analysis, covert, top-level } ] Thus, p a because { public } { public, analysis, covert, top-level } a p because { analysis } { public, analysis } p s because { public } { public, analysis, covert, top-level } a s because { analysis } { public, analysis, covert, top-level } s a because { covert } { public, analysis, covert, top-level } However, because { covert } { public, analysis }, information cannot flow from s to p, reflecting the lack of transitivity of the system.

Nonlattice policies can be embedded into lattices. Hence, analysis of information flows may proceed without loss of generality under the assumption that the information flow model is a lattice.