Method and apparatus for static taint analysis of computer program code
View Patent ↗A method is provided to infer taintedness in code expressions encoded in a computer readable device comprising: configuring a computer system to, store a representation of a computer program that is to be evaluated in non-transitory storage media; identify within the representation a pointer cast operation; determine whether an identified cast operation involves a cast from a pointer to a raw memory data type to a pointer to a structured data type; determine whether a structured data type casted to is associated with indicia of externalness; designating data addressed by that pointer as tainted; and determine whether data designated as tainted is consumed by an operation in the computer program that acts as a taintedness sink.
1. A method to infer taintedness in code expressions encoded in a computer readable device comprising:
configuring a computer system to,
store a representation of a computer program that is to be evaluated in non-transitory storage media;
identify within the representation a pointer cast operation;
in response to identifying a cast operation, determine whether the identified cast operation involves a cast from a pointer to a raw memory data type to a pointer to a structured data type;
in response to a determination that a raw memory pointer is cast to a pointer to a structured data type, determine whether the structured data type casted to is associated with indicia of externalness;
in response to a determination that the structured data type casted to is associated with indicia of externalness, designate a value addressed by that pointer as tainted; and
determine whether a value designated as tainted is indicated in the representation as consumed by an operation in the computer program that acts as a taintedness sink.
2. The method of claim 1 further including:
configuring a computer system to,
determine whether the representation indicates that the computer program sanitizes the value associated with identified cast operation.
3. The method of claim 1 further including:
configuring a computer system to,
determine whether the representation indicates that the computer program sanitizes the value associated with identified cast operation;
in response to determinations that the value associated with identified cast operation is consumed by an operation in the computer program that acts as a taintedness sink and that the computer program does not sanitize the value associated with identified cast operation, report that an unsanitized value is consumed by the sink.
4. The method of claim 1 further including:
configuring a computer system to,
determine whether the representation indicates that the computer program includes operations to sanitize the value associated with identified cast operation through path termination.
5. The method of claim 1 further including:
determine whether the representation indicates that the computer program includes operations to sanitize the value associated with identified cast operation through value substitution.
6. The method of claim 1 further including:
determine whether the representation indicates that the computer program includes operations to sanitize the value associated with identified cast operation through at least one of path termination and variable substitution.
7. The method of claim 1 ,
wherein the representation includes source code.
8. The method of claim 1 ,
wherein the representation includes an abstract syntax tree.
9. The method of claim 1 ,
wherein the representation includes byte code.
10. The method of claim 1 ,
wherein the transformed representation includes object code that retains sufficient source-level information about types and casting.
11. The method of claim 1 ,
wherein determining whether a structured data type casted to is associated with indicia of externalness includes determining whether any field has a pointer type.
12. The method of claim 1 ,
wherein association of a structured data type casted with a field that has a pointer type indicates internalness.
13. The method of claim 1 ,
wherein determining whether a structured data type casted to is associated with indicia of externalness includes weighing one or more factors from the group including: diversity of field sizes in the casted data type, whether the casted data type has bit fields, whether unsigned fields are present, packing of the data type.
14. The method of claim 13 ,
wherein a large number of fields, many different data sizes, frequent use of bit fields, and the frequent use of unsigned types are indicative of externalness; and
wherein presence of pointer type fields are indicative of not externalness.
15. The method of claim 1 ,
wherein identifying a pointer cast operation includes tracing code expressions within the representation.
16. The method of claim 1 ,
wherein identifying a pointer cast operation includes tracing code expressions within the representation; and
wherein determining whether a value designated as tainted is indicted in the representation as consumed by an operation in the computer program that acts as a taintedness sink includes tracing code expressions within the representation.
17. The method of claim 1 further including:
in response to a determination that the value designated as tainted is consumed by an operation that acts as a taintedness sink, report a taintedness result.
18. The method of claim 1 ,
wherein identify within the representation a pointer cast operation includes identifying an explicit cast operation.
19. The method of claim 1 ,
wherein identify within the representation a pointer cast operation includes identifying an implicit cast operation.
20. The method of claim 1 further including:
traversing the computer program in a direction from the representation a pointer cast operation to the operation in the computer program that acts as a taintedness sink.
21. The method of claim 1 further including:
traversing the computer program in a direction from the operation in the computer program that acts as a taintedness sink to the representation of the pointer cast operation.
22. The method of claim 1 ,
wherein association of a structured data type casted with a field that has a pointer type indicates internalness; and
wherein determining whether a structured data type casted to is associated with indicia of externalness includes weighing one or more factors from the group including: diversity of field sizes in the casted data type, whether the casted data type has bit fields, whether unsigned fields are present, packing of the data type.
23. An article of manufacture that includes a computer readable device encoded with instruction code to cause a computer to perform a process that includes:
configuring a computer system to,
store a representation of a computer program that is to be evaluated in non-transitory storage media;
identify within the representation a pointer cast operation;
in response to identifying a cast operation, determine whether the identified cast operation involves a cast from a pointer to a raw memory data type to a pointer to a structured data type;
in response to a determination that a raw memory pointer is cast to a pointer to a structured data type, determine whether the structured data type casted to is associated with indicia of externalness;
in response to a determination that the structured data type casted to is associated with indicia of externalness, designate a value addressed by that pointer as tainted; and
determine whether a value designated as tainted is indicated in the representation as consumed by an operation in the computer program that acts as a taintedness sink.