Algorithms and tool support for dynamic information flow analysis

A new approach to dynamic information flow analysis (DIFA) is presented, and its applications to intrusion detection, software testing and program debugging are discussed. The approach is based on a new forward-computing algorithm that enables online analysis when fast response is not critical. A new forward-computing algorithm for dynamic slicing is also presented, which is more precise than previous forward-computing algorithms and is not restricted to programs with structured control flow. The DIFA and slicing algorithms both rely on a new, precise direct dynamic control dependence algorithm, which requires only constant time per program action. The correctness of this algorithm depends on special, graph-theoretic properties of control dependence, which are established here. A tool called DynFlow is described that implements the proposed approach in order to support analysis of Java byte code programs, and two case studies are presented to illustrate how DynFlow can be used to detect and debug insecure flows. Finally, since dynamic analysis alone is inherently unable to detect implicit information flows, an extension to our approach is described that enables it to detect most implicit information flows at runtime.