Dynamic Program Slicing and Information Flow Tracking

Given a variable at an execution point, dynamic slicing (DS) identifies the set of executed instructions (called dynamic slice) that had directly or transitively contributed to the value of the variable. DS is achieved by tracking program dependences on the fly. The challenges of DS lie in the cost and the large size of the produced slices.

Dynamic information flow tracking (DIFT) tracks if confidential information such as user password is leaked during program execution, or if untrusted information from external sources contaminates critical part of program execution. Technically, DIFT shares a lot of similarity with DS as it also relies on tracking program dependences, and hence faces similar challenges.

We aim to improve the effectiveness and efficiency of program dependence tracking in this project. In the efficiency aspect, some of our contributions are highlighted as follows.

• We have developed a highly efficient dynamic slicing technique. It identifies and removes redundancy in traditional slicing techniques and improves the efficiency by an order of magnitude [PLDI'04].
• DS algorithms often operate on traces. We have designed a technique that can efficiently trace and represent control flow, program dependences, and variable values in a unified and compressed format [MICRO'04]. It achieves the space efficiency of 4 bits per executed instruction for real world programs.

• Traditional slices are large because all dependences are considered. We proposed to associate weights to dependence edges based on their semantics and their relations to the correct part of the output. We are able to reduce the size of dynamic slices by orders of magnitude, to less than one hundred statements in many cases [PLDI'06].
• A great challenge in DIFT is to properly handle control dependence. Considering all control dependences causes a lot of false positives, e.g. bogus information leaks are reported, whereas not considering control dependence at all causes a lot of false negatives, e.g. real information leaks are missed. We identified a specific kind of dependence called strict control dependence that denotes significant information flow, and proposed an efficient online detection algorithm. Considering only strict control dependences reduces false positives and negatives in DIFT by a factor of 3-10 [ISSTA'10-1].

Recently, we have also developed a novel dual slicing algorithm for concurrent programs. It slices two executions simultaneously, one passing and the other failing due to schedule differences, in an alternative and iterative way. The algorithm produces very small slices and naturely overcomes the inherent limitation of DS due to execution omission [ISSTA'10-2].

Traditional DS is code centric. Hence, the upper bound size of a slice is the length of the execution, which could be infinite. We proposed a memory centric technique called memory slicing. It computes the set of live variables that a given variable is dependent on at an execution point. The upper bound of a memory slice is the live memory, which is finite. We showed that memory slicing is effective in debugging [ISSTA'09].

Funding

	Secure End-to-end Service Oriented Architecture, Air Force Research Lab, 2010-2011.
	Scalable and Efficient Dynamic Information Flow Tracking in Multithreaded Programs, NSF-CSR-AES-RCS-0720516, 2007-2009.
	An Advanced Infrastructure for Generation, Storage, and Analysis of Program Execution Traces, NSF-CRI-0708464, 2007-2008.

Awards

• 2006 ACM SIGPLAN Dissertation Award for thesis `` Fault Localization via Precise Dynamic Slicing''.
• 2003 ICSE Distingushied Paper Award for paper ``Precise Dynamic Slicing Algorithms''.

Students

• Bin Xin (Google)
  
• Tao Bao
  
• William N. Sumner
  

Publications