Automatic Inference Of Whitelist-Based Validation As Part Of Static Analysis For Security

• US 20120266247A1
• Filed: 04/18/2011
• Published: 10/18/2012
• Est. Priority Date: 04/18/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Pistoia, Marco, Tateishi, Takaaki, Tripp, Omer, Guy, Lotem
• Granted Patent: US 8,627,465 B2
• Time in Patent Office: Days
• US Class Current: 726/25
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589
• CPC Class Codes: G06F 21/577 Assessing vulnerabilities and evaluating computer system security
• CPC Class Codes: G06F 2221/033 Test or assess software

Abstract

A method includes performing taint analysis of a computer program and determining an original set of paths from sources to sinks. Each path corresponds to a vulnerability. The method includes determining for each variable whose type is a collection and is accessed in one of the paths in the original set of paths whether the variable points to a concrete value whose internal state is not tainted according to the taint analysis. The method further includes, for each of the variables whose type is a collection found not to be tainted according to the taint analysis, determining all points in the computer program where a membership check against the collection is performed. The method also includes, for each of the points, determining corresponding paths and removing those paths from the original set of paths to create a reduced set of paths. Apparatus and computer readable program products are also disclosed.

Claims

1. A method, comprising:

performing taint analysis of a computer program and determining an original set of paths from sources to sinks, wherein each path corresponds to a vulnerability because taint flows from a source in the path to a sink in the path;

determining for each variable whose type is a collection and is accessed in one of the paths in the original set of paths whether the variable points to a concrete value whose internal state is not tainted according to the taint analysis;

for each of the variables whose type is a collection found not to be tainted according to the taint analysis, determining all points in the computer program where a membership check against the collection is performed; and

for each of the points, determining corresponding paths and removing those paths from the original set of paths to create a reduced set of paths.

2. The method of claim 1, further comprising displaying the reduced set of paths to a user.

3. The method of claim 1, wherein an output of the performed taint analysis includes a map from program points to taint facts holding at these points, and wherein determining whether the variable points to a concrete value whose internal state is not tainted according to the taint analysis further comprises:

determining at a program point by static types whether a variable is a collection and, if so, adding the collection to a list;

determining, using the map, if taint facts at the program point indicate the variable points to a concrete value whose internal state may be tainted and, if so, removing the collection from the list; and

performing the determining at a program point and determining if taint facts at the program point for all points in the computer program, wherein the list indicates each variable whose type is a collection points to a concrete value whose internal state is not tainted according to the taint analysis.

4. The method of claim 3, wherein determining at a program point by static types whether a variable is a collection is performed at least in part by using known types for collections indicating which variables are collections.

5. The method of claim 3, wherein determining at a program point by static types whether a variable is a collection is performed at least in part by using a user-supplied specification of types for collections indicating which variables are collections.

6. The method of claim 1, wherein determining all the points in the computer program where a membership check against the collection is performed further comprises determining a membership check is performed at least in part by using known types for collections indicating which collections perform membership checks.

7. The method of claim 1, wherein determining all the points in the computer program where a membership check against the collection is performed further comprises determining a membership check is performed at least in part by using known types for collections indicating which collections perform membership checks.

8. The method of claim 1, wherein a membership check against a collection comprises a whitelist-based validator.

9. An apparatus, comprising:

one or more memories comprising computer readable program code;

one or more processors configured, in response to execution of the computer readable program code, to cause the apparatus to perform at least the following;

performing taint analysis of a computer program and determining an original set of paths from sources to sinks, wherein each path corresponds to a vulnerability because taint flows from a source in the path to a sink in the path;

determining for each variable whose type is a collection and is accessed in one of the paths in the original set of paths whether the variable points to a concrete value whose internal state is not tainted according to the taint analysis;

for each of the variables whose type is a collection found not to be tainted according to the taint analysis, determining all points in the computer program where a membership check against the collection is performed; and

for each of the points, determining corresponding paths and removing those paths from the original set of paths to create a reduced set of paths.

10. The apparatus of claim 9, further comprising displaying the reduced set of paths to a user.

11. The apparatus of claim 9, wherein an output of the performed taint analysis includes a map from program points to taint facts holding at these points, and wherein determining whether the variable points to a concrete value whose internal state is not tainted according to the taint analysis further comprises:

determining at a program point by static types whether a variable is a collection and, if so, adding the collection to a list;

determining, using the map, if taint facts at the program point indicate the variable points to a concrete value whose internal state may be tainted and, if so, removing the collection from the list; and

performing the determining at a program point and determining if taint facts at the program point for all points in the computer program, wherein the list indicates each variable whose type is a collection points to a concrete value whose internal state is not tainted according to the taint analysis.

12. The apparatus of claim 11, wherein determining at a program point by static types whether a variable is a collection is performed at least in part by using known types for collections indicating which variables are collections.

13. The apparatus of claim 11, wherein determining at a program point by static types whether a variable is a collection is performed at least in part by using a user-supplied specification of types for collections indicating which variables are collections.

14. The apparatus of claim 9, wherein determining all the points in the computer program where a membership check against the collection is performed further comprises determining a membership check is performed at least in part by using known types for collections indicating which collections perform membership checks.

15. The apparatus of claim 9, wherein determining all the points in the computer program where a membership check against the collection is performed further comprises determining a membership check is performed at least in part by using known types for collections indicating which collections perform membership checks.

16. The apparatus of claim 9, wherein a membership check against a collection comprises a whitelist-based validator.

17. A computer program product, comprising:

a computer readable storage medium having computer readable program code embodied thereon, the computer readable program code comprising;

code for performing taint analysis of a computer program and determining an original set of paths from sources to sinks, wherein each path corresponds to a vulnerability because taint flows from a source in the path to a sink in the path;

code for determining for each variable whose type is a collection and is accessed in one of the paths in the original set of paths whether the variable points to a concrete value whose internal state is not tainted according to the taint analysis;

code for, for each of the variables whose type is a collection found not to be tainted according to the taint analysis, determining all points in the computer program where a membership check against the collection is performed; and

code for, for each of the points, determining corresponding paths and removing those paths from the original set of paths to create a reduced set of paths.

18. The computer program product of claim 17, further comprising displaying the reduced set of paths to a user.

19. The computer program product of claim 17, wherein an output of the performed taint analysis includes a map from program points to taint facts holding at these points, and wherein determining whether the variable points to a concrete value whose internal state is not tainted according to the taint analysis further comprises:

determining at a program point by static types whether a variable is a collection and, if so, adding the collection to a list;

determining, using the map, if taint facts at the program point indicate the variable points to a concrete value whose internal state may be tainted and, if so, removing the collection from the list; and

performing the determining at a program point and determining if taint facts at the program point for all points in the computer program, wherein the list indicates each variable whose type is a collection points to a concrete value whose internal state is not tainted according to the taint analysis.

20. The computer program product of claim 19, wherein determining at a program point by static types whether a variable is a collection is performed at least in part by using known types for collections indicating which variables are collections.

21. The computer program product of claim 19, wherein determining at a program point by static types whether a variable is a collection is performed at least in part by using a user-supplied specification of types for collections indicating which variables are collections.

22. The computer program product of claim 17, wherein determining all the points in the computer program where a membership check against the collection is performed further comprises determining a membership check is performed at least in part by using known types for collections indicating which collections perform membership checks.

23. The computer program product of claim 17, wherein determining all the points in the computer program where a membership check against the collection is performed further comprises determining a membership check is performed at least in part by using known types for collections indicating which collections perform membership checks.

24. The computer program product of claim 17, wherein a membership check against a collection comprises a whitelist-based validator.