Three binary information flow relations are defined for while-programs. &lgr; relates variables to expressions, stating whether the value of variable v, as defined on entry to statement S, may be used in the evaluation of an expression e, where e is contained in S. v may be used in evaluating e even if v is not found directly in e, i.e., an intermediate set of assignments to other variables may transmit the value of v. (S may be a compound statement.) &mgr; relates expressions to variables, stating whether an expression e in statement S may be used in obtaining the value of variable v on exit from S. Again, transitive relationships are included. &rgr; is a composition of &lgr; and &mgr;, relating variables to variables, in the sense of “the value of v on entry to S may be used in obtaining the value of v on exit from S.”

Having defined these relationships, the authors proceed to show how they can be computed for assignment, if, while, empty, and compound statements. They then proceed to show a variety of uses for the information thus computed. Primarily, the information is useful in revealing errors or anomalies in a program. The &rgr; operator can be used to demonstrate, in an avionics system for example, that if the passenger in seat 8A flips the reading light switch there will be no effect on the position of the landing gear. The &lgr;, &mgr;, and &rgr; operators can also be used in computing program slices for use in debugging; that is, the set of only those program statements which may be involved in determining an expression’s value. Other uses are also described.

The operators in this paper may be used to compute many of the information relations that are computed by data flow analysis techniques (as well as many that are not typically done with data flow analysis). However, aside from one exception, the authors do not address the issue that computing must affect information, as opposed to may affect information. Experience with data flow analyzers has demonstrated the importance of the distinction. The authors have also neglected to consider how the relations may be computed for recursive procedures. The formulas they provide for handling procedure calls assume no recursion.

The authors claim that, despite poor worst-case complexity measures for computing the information flow relations (cubic or worse), “in practice” they will be found sufficiently efficient. This claim is accompanied with a reference to experiments they have performed, but the description of the experiment leaves one to believe that substantial further study is necessary to support this claim.

Overall, this paper presents some very interesting ideas for static analysis of programs and is suggested reading for builders of analysis and debugging tools.