Sound and effective data-flow analysis in the presence of aliasing

Abstract

A method is disclosed that includes, using a data flow model of a program suitable for taint analysis of the program, tracking information from sources of taint to entities in a heap using a model of the heap based on the program. The tracking is performed so that the information is relevant for taint propagation and is performed in a manner that is field-sensitive for the entities in the heap. The method includes, based on output of the tracking, performing data-flow analysis to determine taint flow from the sources of the taint through data flow paths to sinks using the taint.

What is claimed is: 
     
         1 . A method, comprising:
 using a data flow model of a program suitable for taint analysis of the program, tracking information from sources of taint to entities in a heap using a model of the heap based on the program, wherein the tracking is performed so that the information is relevant for taint propagation and is performed in a manner that is field-sensitive for the entities in the heap; and   based on output of the tracking, performing data-flow analysis to determine taint flow from the sources of the taint through data flow paths to sinks using the taint.   
     
     
         2 . The method of  claim 1 , wherein tracking information further comprises performing a field-sensitive analysis using a pointer analysis model to distinguish fields of abstract objects in the heap from each other and fields of different abstract objects in the heap from each other. 
     
     
         3 . The method of  claim 2 , wherein the field-sensitive analysis distinguishes field pointer keys of different abstract objects even when such field pointer keys represent an identically named field. 
     
     
         4 . The method of  claim 2 , wherein the pointer analysis model comprises a points-to graph. 
     
     
         5 . The method of  claim 2 , further comprising determining the data flow model by analyzing the program and determining the pointer analysis model by analyzing the program. 
     
     
         6 . The method of  claim 2 , wherein performing a field-sensitive analysis using a pointer analysis model further comprises creating a heap graph comprising an intersection of a first set of environment and heap pointers in the program intersected with a second set of the abstract objects participating in the pointer analysis model, and further comprising a set of edges connecting elements of the first and second sets. 
     
     
         7 . The method of  claim 6 , wherein first set of environment and heap pointers in the program comprise local variables in the heap and fields that reference objects in the heap. 
     
     
         8 . The method of  claim 6 , wherein the tracking information further comprises:
 determining that taint flows into a given access path, wherein each access path is a pair linking a variable with a set of field identifiers, and wherein an access path can be evaluated to yield a unique object allocated in the heap;   determining all access paths, corresponding to the given access path, that meet a set of conditions, the determining the all access paths using the heap graph; and   outputting the deter mined access paths that meet the set of conditions.   
     
     
         9 . The method of  claim 8 , wherein the evaluation of an access path is performed in a certain concrete state of the program with a particular environment and a given heap to yield the unique object in the given heap. 
     
     
         10 . The method of  claim 8 , wherein determining that taint flows into a given access path further comprises determining, using a relational summary mapping for a function in the program, that taint flows into the given access path. 
     
     
         11 . The method of  claim 10 , wherein determining that taint flows into a given access path further comprises determining, for the function in the program that is analyzed for a first time, a relational summary mapping one or more input parameters of the function to one or more return values of the function. 
     
     
         12 . The method of  claim 8 , wherein the set of conditions comprises:
 the access paths in the all access paths are rooted at local variables;   the local variables belong to a same method; and   all of the access paths alias the given access path.   
     
     
         13 . The method of  claim 12 , wherein the set of conditions further comprises: all of the access paths can be truncated to specific length. 
     
     
         14 . The method of  claim 1 , wherein the tracking information is performed in a manner that is also flow-insensitive with respect to fields, wherein in response to a field f of an object o in the heap being assigned value v and value w at two different program points, the field f is considered to point to the set of values. 
     
     
         15 . The method of  claim 14 , wherein the tracking information further comprises building a call graph and a points-to graph, and wherein flow insensitivity is performed when at least the call graph and points-to graph are built. 
     
     
         16 . The method of  claim 1 , further comprising outputting indications of the data flow paths determined to be tainted by the performing the data-flow analysis. 
     
     
         17 - 33 . (canceled)