Method and system for fast static taint analysis
A method for detecting user input dependence in software code. The method including representing the software code with a reachability graph having: a plurality of nodes, where a root node of the plurality of nodes represents an input controlled by a user; a first directed edge connecting a first node of the plurality of nodes and a second node of the plurality of nodes, where the first directed edge represents a data dependency; and a second directed edge connecting a third node of the plurality of nodes and a fourth node of the plurality of nodes, wherein the second directed edge represents a data dependency. The method also includes identifying a fifth node of the plurality of nodes as a reachable node from the root node by traversing the reachability graph from the root node to the reachable node; and marking a portion of the software code represented by the reachable node as user input dependant.
1. A method for detecting user input dependence in software code, comprising:
generating, by a static analysis engine executing on a processor, an Augmented Static Single Assignment (aSSA) form of the software code comprising:
an augmented phi-node comprising:
a control dependency to a predicate;
a first data dependency to a first variable assignment, and
a second data dependency to a second variable assignment, wherein the first variable assignment and second variable assignment are dependent on the predicate;
generating, by the static analysis engine, a reachability data structure using the aSSA form of the software code, wherein the reachability data structure comprises:
a root node representing an input controlled by a user;
a first node representing the augmented phi-node;
a second node representing the variable assignment;
a third node representing the predicate;
a first directed edge connecting the first node and the second node, wherein the first directed edge represents the data dependency; and
a second directed edge connecting the first node and the third node, wherein the second directed edge represents the control dependency;
determining that the first node is reachable by a path from the root node, wherein the path represents a portion of the software code; and
marking, by a source code modifier executing on the processor, the portion of the software code corresponding to the path as code to modify.
2. The method of claim 1 ,
wherein the control dependency selects between execution of a first statement and execution of a second statement,
wherein execution of the first statement results in an assignment of a first value to a variable, and
wherein execution of the second statement results in an assignment of a second value to the variable.
3. The method of claim 1 , wherein determining that the fifth node is reachable by the path comprises traversing the reachability data structure through the first directed edge.
4. The method of claim 1 , wherein the control dependency in an explicit format, the control dependency being associated with a gating function in the software code.
5. The method of claim 4 , wherein a confluence point associated with the gating function in the software code is represented by the augmented phi-node in the aSSA form.
6. The method of claim 5 ,
wherein the augmented phi-node is denoted as x:=Φ′(y 1 , . . . ,y k ;p 1 , . . . ,p j );
wherein x represents a single assignment variable in the software code;
wherein y 1 , . . . ,y k represent a plurality of values assignable to x; and
wherein p 1 , . . . ,p j represent a portion of a plurality of nodes in the reachability graph associated with selecting a value from y 1 , . . . ,y k to assign to x.
7. The method of claim 1 , wherein at least one of a plurality of nodes in the reachability graph represents one from a group consisting of an instruction, a function, a function argument, and a variable in the software code.
8. The method of claim 1 , further comprising:
modifying the portion of the software code represented by the first node.
9. A system for detecting user input dependence in software code, comprising:
a processor
a static analysis engine, executing on the processor, comprising functionality to:
generate an Augmented Static Single Assignment (aSSA) form of the software code comprising:
an augmented phi-node comprising:
a control dependency to a predicate;
a first data dependency to a first variable assignment, and
a second data dependency to a second variable assignment, wherein the first variable assignment and second variable assignment are dependent on the predicate;
generate a reachability data structure using the aSSA form of the software code, wherein the reachability data structure comprises:
a root node representing an input controlled by a user;
a first node representing the augmented phi-node;
a second node representing the variable assignment;
a third node representing the predicate;
a first directed edge connecting the first node and the second node, wherein the first directed edge represents the data dependency; and
a second directed edge connecting the first node and the third node, wherein the second directed edge represents the control dependency;
determine that the first node is reachable by a path from the root node, wherein the path represents a portion of the software code; and
a source code modifier, executing on the processor, configured to mark the portion of the software code corresponding to the path.
10. The system of claim 9 ,
wherein the control dependency selects between execution of a first statement and execution of a second statement,
wherein execution of the first statement results in an assignment of a first value to a variable, and
wherein execution of the second statement results in an assignment of a second value to the variable.
11. The system of claim 9 , wherein the aSSA form comprises the control dependency in an explicit format, the control dependency being associated with a gating function in the software code.
12. The system of claim 11 , wherein a confluence point associated with the gating function in the software code is represented by the augmented phi-node in the aSSA form.
13. A non-transitory computer readable medium comprising instructions for detecting user input dependence in software code in software code, the instructions comprising functionality for:
generating, by a static analysis engine executing on a processor, an Augmented Static Single Assignment (aSSA) form of the software code comprising:
an augmented phi-node comprising:
a control dependency to a predicate;
a first data dependency to a first variable assignment, and
a second data dependency to a second variable assignment, wherein the first variable assignment and second variable assignment are dependent on the predicate;
generating, by the static analysis engine, a reachability data structure using the aSSA form of the software code, wherein the reachability data structure comprises:
a root node representing an input controlled by a user;
a first node representing the augmented phi-node;
a second node representing the variable assignment;
a third node representing the predicate;
a first directed edge connecting the first node and the second node, wherein the first directed edge represents the data dependency; and
a second directed edge connecting the first node and the third node, wherein the second directed edge represents the control dependency;
determining that the first node is reachable by a path from the root node, wherein the path represents a portion of the software code; and
marking, by a source code modifier executing on the processor, the portion of the software code corresponding to the path as code to modify.
14. The non-transitory computer readable medium of claim 13 ,
wherein the control dependency selects between execution of a first statement and execution of a second statement,
wherein execution of the first statement results in an assignment of a first value to a variable, and
wherein execution of the second statement results in an assignment of a second value to the variable.