We now define precisely the notion of information flow. Intuitively, information flows from an object x to an object y if the application of a sequence of commands c causes the information initially in x to affect the information in y. We use the notion of entropy, or uncertainty (see Chapter 32, “Entropy and Uncertainty”), to formalize this concept.

Let c be a sequence of commands taking a system from state s to another state t. Let x and y be objects in the system. We assume that x exists when the system is in state s and has the value x_s. We require that y exist in state t and have the value y_t. If y exists in state s, it has value y_s.

This definition states that information flows from the variable x to the variable y if the value of y after the commands allows one to deduce information about the value of x before the commands were run.

This definition views information flow in terms of the information that the value of y allows one to deduce about the value in x. For example, the statement

y := x;

reveals the value of x in the initial state, so H(x_s | y_t) = 0 (because given the value y_t, there is no uncertainty in the value of x_s). The statement

y := x / z;

reveals some information about x, but not as much as the first statement.

The final result of the sequence c must reveal information about the initial value of x for information to flow. The sequence

tmp := x;
y := tmp;

has information flowing from x to y because the (unknown) value of x at the beginning of the sequence is revealed when the value of y is determined at the end of the sequence. However, no information flow occurs from tmp to x, because the initial value of tmp cannot be determined at the end of the sequence.

x := y + z;

if x = 1 then y := 0;
else y := 1;

The flow of information occurs, not because of an assignment of the value of x, but because of a flow of control based on the value of x. This demonstrates that analyzing programs for assignments to detect information flows is not enough. To detect all flows of information, implicit flows must be examined.

An information flow policy is a security policy that describes the authorized paths along which that information can flow. Part 3, “Policy,” discussed several models of information flow, including the Bell-LaPadula Model, nonlattice and nontransitive models of information flow, and nondeducibility and noninterference. Each model associates a label, representing a security class, with information and with entities containing that information. Each model has rules about the conditions under which information can move throughout the system.

In this chapter, we use the notation x ≤ y to mean that information can flow from an element of class x to an element of class y. Equivalently, this says that information with a label placing it in class x can flow into class y.

Earlier chapters usually assumed that the models of information flow policies were lattices. We first consider nonlattice information flow policies and how their structures affect the analysis of information flow. We then turn to compiler-based information flow mechanisms and runtime mechanisms. We conclude with a look at flow controls in practice.

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.

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 ]

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

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.

Figure 16-1. An example of a nonlattice information flow policy. Because the business manager and the auditor are independent, they have no least upper bound. Hence, the structure is not a lattice.

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.

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.

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:

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

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.

For our discussion, we assume that the allowed flows are supplied to the checking mechanisms through some external means, such as from a file. The specifications of allowed flows involve security classes of language constructs. The program involves variables, so some language construct must relate variables to security classes. One way is to assign each variable to exactly one security class. We opt for a more liberal approach, in which the language constructs specify the set of classes from which information may flow into the variable. For example,

x: integer class { A, B }

states that x is an integer variable and that data from security classes A and B may flow into x. Note that the classes are statically, not dynamically, assigned. Viewing the security classes as a lattice, this means that x's class must be at least the least upper bound of classes A and B—that is, lub{A, B} ≤ x.

Two distinguished classes, Low and High, represent the greatest lower bound and least upper bound, respectively, of the lattice. All constants are of class Low.

Information can be passed into or out of a procedure through parameters. We classify parameters as input parameters (through which data is passed into the procedure), output parameters (through which data is passed out of the procedure), and input/output parameters (through which data is passed into and out of the procedure).

(* input parameters are named is; output parameters, os; *)
(* and input/output parameters, ios, with s a subscript *)
proc something(i1, ..., ik; var o1, ..., om, io1, ..., ion);
var l1, ..., lj;                  (* local variables *)
begin
         S;                       (* body of procedure *)
end;

The class of an input parameter is simply the class of the actual argument:

Because information can flow from any input parameter to any output parameter, the declaration must capture this:

(We implicitly assume that any output-only parameter is initialized in the procedure.) The input/output parameters are like output parameters, except that the initial value (as input) affects the allowed security classes:

proc sum(x: int class { x };
              var out: int class { x, out });
begin
         out := out + x;
end;

The declarations presented so far deal only with basic types, such as integers, characters, floating point numbers, and so forth. Nonscalar types, such as arrays, records (structures), and variant records (unions) also contain information. The rules for information flow classes for these data types are built on the scalar types.

Consider the array

a: array 1 .. 100 of int;

First, look at information flows out of an element a[i] of the array. In this case, information flows from a[i] and from i, the latter by virtue of the index indicating which element of the array to use. Information flows into a[i] affect only the value in a[i], and so do not affect the information in i. Thus, for information flows from a[i], the class involved is lub{ a[i], i }; for information flows into a[i], the class involved is a[i].

A program consists of several types of statements. Typically, they are

We consider each of these types of statements separately, with two exceptions. Function calls can be modeled as procedure calls by treating the return value of the function as an output parameter of the procedure. Input/output statements can be modeled as assignment statements in which the value is assigned to (or assigned from) a file. Hence, we do not consider function calls and input/output statements separately.

y := f(x1, ..., xn)

x := y + z;

begin
     S1;
     ...
     Sn;
end;

begin
     x := y + z;
     a := b * c - x;
end;

if f(x1, ..., xn) then
     S1;
else
     S2;
end;

if x + y < z then
     a := b;
else
     d := b * c - x;
end;

while f(x1, ..., xn) do
      S;

while i < n do
begin
     a[i] := b[i];
     i := i + 1;
end;

Goto Statements

A goto statement contains no assignments, so no explicit flows of information occur. Implicit flows may occur; analysis detects these flows.

• Definition 16–7. A basic block is a sequence of statements in a program that has one entry point and one exit point.

EXAMPLE: Consider the following code fragment.

proc transmatrix(x: array [1..10][1..10] of int class { x };
             var y: array [1..10][1..10] of int class { y } );
var i, j, tmp: int class { tmp };
begin
         i := 1;                     (* b1 *)
_________________________________________________________________
l2:      if i > 10 goto l7;          (* b2 *)
_________________________________________________________________
         j := 1;                     (* b3 *)
_________________________________________________________________
l4:      if j > 10 then goto l6;     (* b4 *)
_________________________________________________________________
         y[j][i] := x[i][j];         (* b5 *)
         j := j + 1;
         goto l4;
_________________________________________________________________
l6:      i := i + 1;                 (* b6 *)
         goto l2;
_________________________________________________________________
l7:                                  (* b7 *)
end;

There are seven basic blocks, labeled b₁ through b₇ and separated by lines. The second and fourth blocks have two ways to arrive at the entry—either from a jump to the label or from the previous line. They also have two ways to exit—either by the branch or by falling through to the next line. The fifth block has three lines and always ends with a branch. The sixth block has two lines and can be entered either from a jump to the label or from the previous line. The last block is always entered by a jump.

Control within a basic block flows from the first line to the last. Analyzing the flow of control within a program is therefore equivalent to analyzing the flow of control among the program's basic blocks. Figure 16-3 shows the flow of control among the basic blocks of the body of the procedure transmatrix.

Figure 16-3. The control flow graph of the procedure transmatrix. The basic blocks are labeled b₁ through b₇.The conditions under which branches are taken are shown over the edges corresponding to the branches.

When a basic block has two exit paths, the block reveals information implicitly by the path along which control flows. When these paths converge later in the program, the (implicit) information flow derived from the exit path from the basic block becomes either explicit (through an assignment) or irrelevant. Hence, the class of the expression that causes a particular execution path to be selected affects the required classes of the blocks along the path up to the block at which the divergent paths converge.

• Definition 16–8. An immediate forward dominator of a basic block b (written IFD(b)) is the first block that lies on all paths of execution that pass through b.

EXAMPLE: In the procedure transmatrix, the immediate forward dominators of each block are IFD(b₁) = b₂, IFD(b₂) = b₇, IFD(b₃) = b₄, IFD(b₄) = b₆, IFD(b₅) = b₄, and IFD(b₆) = b₂.

Computing the information flow requirement for the set of blocks along the path is now simply applying the logic for the conditional statement. Each block along the path is taken because of the value of an expression. Information flows from the variables of the expression into the set of variables assigned in the blocks. Let B_i be the set of blocks along an execution path from b_i to IFD(b_i), but excluding these endpoints. (See Exercise 6.) Let x_i1, ..., x_in be the set of variables in the expression that selects the execution path containing the blocks in B_i. The requirements for the program's information flows to be secure are

• All statements in each basic block secure

• lub{x_i1, ..., x_in} ≤ glb{ y | y is the target of an assignment in B_i }

EXAMPLE: Consider the body of the procedure transmatrix. We first state requirements for information flow within each basic block:

• b₁: Low ≤ i ⇒ secure

• b₃: Low ≤ j ⇒ secure

• b₅: lub{ x[i][j], i, j } ≤ y[j][i]; j ≤ j ⇒ lub{ x[i][j], i, j } ≤ y[j][i]

• b₆: lub{ Low, i } ≤ i ⇒ secure

The requirement for the statements in each basic block to be secure is, for i = 1, ..., n and j = 1, ..., n, lub{ x[i][j], i, j } ≤ y[j][i]. By the declarations, this is true when lub{x, tmp} ≤ y.

In this procedure, B₂ = { b₃, b₄, b₅, b₆ } and B₄ = { b₅ }. Thus, in B₂, statements assign values to i, j, and y[j][i]. In B₄, statements assign values to j and y[j][i]. The expression controlling which basic blocks in B₂ are executed is i ≤ 10; the expression controlling which basic blocks in B₄ are executed is j ≤ 10. Secure information flow requires that i ≤ glb{ i, j, y[j][i]} and j ≤ glb{ j, y[j][i] }. In other words, tmp ≤ glb{ tmp, y } and tmp ≤ glb{ tmp, y }, or tmp ≤ y.

Combining these requirements, the requirement for the body of the procedure to be secure with respect to information flow is lub{x, tmp} ≤ y.

proc procname(i1, ..., im : int; var o1, ..., on : int);
begin
     S;
end;

transmatrix(a, b)

Exceptions can cause information to flow.

proc copy(x: int class { x }; var y: int class Low);
var  sum: int class { x };
     z: int class Low;
begin
     z := 0;
     sum := 0;
     y := 0;
     while z = 0 do begin
           sum := sum + x;
           y := y + 1;
     end
end

If exceptions are handled explicitly, the compiler can detect problems such as this. Denning again supplies such a solution.

on overflowexception sum do z := 1;

Denning also notes that infinite loops can cause information to flow in unexpected ways.

proc copy(x: int 0..1 class { x };
            var y: int 0..1 class Low);
begin
     y := 0;
     while x = 0 do
           (* nothing *);
     y := 1;
end.

Of the many concurrency control mechanisms that are available, we choose to study information flow using semaphores [298]. Their operation is simple, and they can be used to express many higher-level constructs [148, 805]. The specific semaphore constructs are

wait(x): if x = 0 then block until x > 0; x := x - 1;
signal(x): x := x + 1;

where x is a semaphore. As usual, the wait and the signal are indivisible; once either one has started, no other instruction will execute until the wait or signal finishes.

Reitman and his colleagues [34, 836] point out that concurrent mechanisms add information flows when values common to multiple processes cause specific actions. For example, in the block

begin
     wait(sem);
     x := x + 1;
end;

the program blocks at the wait if sem is 0, and executes the next statement when sem is nonzero. The earlier certification requirement for compound statements is not sufficient because of the implied flow between sem and x. The certification requirements must take flows among local and shared variables (semaphores) into account.

Let the block be

begin
     S1;
     ...
     Sn;
end;

Assume that each of the statements S₁, ..., S_n is certified. Semaphores in the signal do not affect information flow in the program in which the signal occurs, because the signal statement does not block. But following a wait statement, which may block, information implicitly flows from the semaphore in the wait to the targets of successive assignments.

Let statement S_i be a wait statement, and let shared(S_i) be the set of shared variables that are read (so information flows from them). Let g(S_i) be the greatest lower bound of the targets of assignments following S_i. A requirement that the block be secure is that shared(S_i) ≤ g(S_i). Thus, the requirements for certification of a compound statement with concurrent constructs are

begin
     x := y + z;
     wait(sem);
     a := b * c - x;
end;

Loops are handled similarly. The only difference is in the last requirement, because after completion of one iteration of the loop, control may return to the beginning of the loop. Hence, a semaphore may affect assignments that precede the wait statement in which the semaphore is used. This simplifies the last condition in the compound statement requirement considerably. Information must be able to flow from all shared variables named in the loop to the targets of all assignments. Let shared(S_i) be the set of shared variables read, and let t₁, ..., t_m be the targets of assignments in the loop. Then the certification conditions for the iterative statement

while f(x1, ..., xn) do
     S;

are

while i < n do
begin
     a[i] := item;
     wait(sem);
     i := i + 1;
end;

Finally, concurrent statements have no information flow among them per se. Any such flows occur because of semaphores and involve compound statements (discussed above). The certification conditions for the concurrent statement

cobegin
     S1;
     ...
     Sn;
coend;

are

cobegin
     x := y + z;
     a := b * c - y;
coend;

Denning and Denning [274], Andrews and Reitman [34], and others build their argument for security on the intuition that combining secure information flows produces a secure information flow, for some security policy. However, they never formally prove this intuition. Volpano, Irvine, and Smith [1023] express the semantics of the above-mentioned information on flow analysis as a set of types, and equate certification that a certain flow can occur to the correct use of types. In this context, checking for valid information flows is equivalent to checking that variable and expression types conform to the semantics imposed by the security policy.

Let x and y be two variables in the program. Let x's label dominate y's label. A set of information flow rules is sound if the value in x cannot affect the value in y during the execution of the program. (The astute reader will note that this is a form of noninterference; see Chapter 8.) Volpano, Irvine, and Smith use language-based techniques to prove that, given a type system equivalent to the certification rules discussed above, all programs without type errors have the noninterference property described above. Hence, the information flow certification rules of Denning and of Andrews and Reitman are sound.

Fenton [345] created an abstract machine called the Data Mark Machine to study handling of implicit flows at execution time. Each variable in this machine had an associated security class, or tag. Fenton also included a tag for the program counter (PC).

The inclusion of the PC allowed Fenton to treat implicit flows as explicit flows, because branches are merely assignments to the PC. He defined the semantics of the Data Mark Machine. In the following discussion, skip means that the instruction is not executed, push(x, x) means to push the variable x and its security class x onto the program stack, and pop(x, x) means to pop the top value and security class off the program stack and assign them to x and x, respectively.

Fenton defined five instructions. The relationships between execution of the instructions and the classes of the variables are as follows.

1. if x = 0 then goto 4 else x := x – 1
2. if z = 0 then goto 6 else z := z – 1
3. halt
4. z := z + 1
5. return
6. y := y + 1
7. return

Fenton's machine handles errors by ignoring them. Suppose that, in the program above, y ≤ x. Then at the fifth step, the certification check fails (because PC = x). So, the assignment is skipped, and at the end y = 0 regardless of the value of x. But if the machine reports errors, the error message informing the user of the failure of the certification check means that the program has attempted to execute step 6. It could do so only if it had taken the branch in step 2, meaning that z = 0. If z = 0, then the else branch of statement 1 could not have been taken, meaning that x = 0 initially.

To prevent this type of deduction, Fenton's machine continues executing in the face of errors, but ignores the statement that would cause the violation. This satisfies the requirements. Aborting the program, or creating an exception visible to the user, would also cause information to flow against policy.

The problem with reporting of errors is that a user with lower clearance than the information causing the error can deduce the information from knowing that there has been an error. If the error is logged in such a way that the entries in the log, and the action of logging, are visible only to those who have adequate clearance, then no violation of policy occurs. But if the clearance of the user is sufficiently high, then the user can see the error without a violation of policy. Thus, the error can be logged for the system administrator (or other appropriate user), even if it cannot be displayed to the user who is running the program. Similar comments apply to any exception action, such as abnormal termination.

The classes of the variables in the examples above are fixed. Fenton's machine alters the class of the PC as the program runs. This suggests a notion of dynamic classes, wherein a variable can change its class. For explicit assignments, the change is straightforward. When the assignment

y := f(x1, ..., xn)

occurs, y's class is changed to lub(x₁, …, x_n). Again, implicit flows complicate matters.

proc copy(x : integer class { x };
               var y : integer class { y });
var z : integer class variable { Low };
begin
       y := 0;
       z := 0;
       if x = 0 then z := 1;
       if z = 0 then y := 1;
end;

Fenton's Data Mark Machine would detect the violation (see Exercise 7).

Denning [266] suggests an alternative approach. She raises the class of the targets of assignments in the conditionals and verifies the information flow requirements, even when the branch is not taken. Her method would raise z to x in the third statement (even when the conditional is false). The certification check at the fourth statement then would fail, because lub(Low, z) = x ≤ y is false.

Denning ([269], p. 285) credits Lampson with another mechanism. Lampson suggested changing classes only when explicit flows occur. But all flows force certification checks. For example, when x = 0, the third statement sets z to Low and then verifies x ≤ z (which is true if and only if x = Low).

Hoffman and Davis [477] propose adding a processor, called a security pipeline interface (SPI), between a host and a destination. Data that the host writes to the destination first goes through the SPI, which can analyze the data, alter it, or delete it. But the SPI does not have access to the host's internal memory; it can only operate on the data being output. Furthermore, the host has no control over the SPI. Hoffman and Davis note that SPIs could be linked into a series of SPIs, or be run in parallel.

They suggest that the SPI could check for corrupted programs. A host requests a file from the main disk. An SPI lies on the path between the disk and the host (see Figure 16-4.) Associated with each file is a cryptographic checksum that is stored on a second disk connected to the first SPI. When the file reaches the first SPI, it computes the cryptographic checksum of the file and compares it with the checksum stored on the second disk. If the two match, it assumes that the file is uncorrupted. If not, the SPI requests a clean copy from the second disk, records the corruption in a log, and notifies the user, who can update the main disk.

Figure 16-4. Use of an SPI to check for corrupted files.

The information flow being restricted here is an integrity flow, rather than the confidentiality flow of the other examples. The inhibition is not to prevent the corrupt data from being seen, but to prevent the system from trusting it. This emphasizes that, although information flow is usually seen as a mechanism for maintaining confidentiality, its application in maintaining integrity is equally important.

Consider two networks, one of which has data classified SECRET^[4] and the other of which is a public network. The authorities controlling the SECRET network need to allow electronic mail to go to the unclassified network. They do not want SECRET information to transit the unclassified network, of course. The Secure Network Server Mail Guard (SNSMG) [937] is a computer that sits between the two networks. It analyzes messages and, when needed, sanitizes or blocks them.

The SNSMG accepts messages from either network to be forwarded to the other. It then applies several filters to the message; the specific filters may depend on the source address, destination address, sender, recipient, and/or contents of the message. Examples of the functions of such filters are as follows.

The SNSMG is a computer that runs two different message transfer agents (MTAs), one for the SECRET network and one for the unclassified network (see Figure 16-5). It uses an assured pipeline [785] to move messages from the MTA to the filter, and vice versa. In this pipeline, messages output from the SECRET network's MTA have type a, and messages output from the filters have a different type, type b. The unclassified network's MTA will accept as input only messages of type b. If a message somehow goes from the SECRET network's MTA to the unclassified network's MTA, the unclassified network's MTA will reject the message as being of the wrong type.

Figure 16-5. Secure Network Server Mail Guard. The SNSMG is processing a message from the SECRET network. The filters are part of a highly trusted system and perform checking and sanitizing of messages.

The SNSMG is an information flow enforcement mechanism. It ensures that information cannot flow from a higher security level to a lower one. It can perform other functions, such as restricting the flow of untrusted information from the unclassified network to the trusted, SECRET network. In this sense, the information flow is an integrity issue, not a confidentiality issue.