System and method for identifying and comparing code by semantic abstractions
Certain embodiments of the present invention are configured to facilitate analyzing computer code more efficiently. For example, by conducting a first level abstraction (e.g., symbolic interpretation and algebraic simplification) and a second level abstraction (e.g., generalization) of the computer code, the analysis may more accurately account for variations in the code that may occur as a result of register renaming, instruction reordering, choice of instructions, etc. while minimizing the cost of computations required to perform the analysis.
1. A system for analyzing versions or variants of potentially malicious computer code to locate code components that have the same effect on a system's state variable though potentially using different sequences of instructions, comprising:
a processor;
a main memory in communication with the processor via a communication infrastructure and storing the different instructions that, when executed by the processor, cause the processor to:
obtain a first section of computer code in a binary executable file format;
disassemble the first section of code in the binary executable file format to form a section of code in assembly format;
decompose the section of computer code in assembly format into one or more code fragments;
perform a first level of abstraction on at least one of the one or more code fragments to acquire at least one semantics statement, comprising mapping a code fragment to a semantics statement, wherein each semantics statement summarizes changes made by one or more instructions of the code fragment to one or more state variables of the processor, the changes described in a form independent of the instructions of the code fragment;
apply a second level of abstraction on the at least one semantics statement to result in at least one first generalized statement, comprising consistently replacing one or more register names of the semantics statement with one or more logical variables wherein said replacement is consistent if two occurrences of identical register names are always replaced by the same unique logical variable;
computing an index for one or more generalized statements;
storing the index in a database;
repeating the obtain step, disassemble step, decompose step, perform step, and apply step to a second section of computer code, resulting in at least one second generalized statement;
comparing the at least one first generalized statement to the at least one second generalized statement to form a comparison, the comparison showing the similarity between the changes made to one or more state variables of the processor by one or more instructions of the code fragment on the first section of computer code and the changes made to one or more state variables of the processor by one or more instructions of the code fragment of the second section of computer, and producing an output related to the comparison;
wherein the main memory in communication with the processor via communication infrastructure and storing instructions that, when executed by the processor, cause the processor to index the at least one first generalized statement and the at least one second generalized statement, and storing the index in a database, wherein said database is a cloud computing database; and
wherein a result is displayed to a user.
2. The system of claim 1 , wherein the comparison is configured for display with a user interface.
3. The system of claim 1 , wherein the main memory for communication with the processor via a communication infrastructure and storing instructions that, when executed by the processor, cause the processor to search the database for computer code similar to a section of computer code of interest by repeating the disassemble step, decompose step, perform step, apply step and indexing step to the computer code of interest and comparing the indexes for similarity.
4. The system of claim 1 , wherein the symbolic interpretation includes the step of interpreting the one or more code fragments using symbolic values comprising a mathematical expression.
5. The system of claim 4 , wherein the mathematical expression is in canonical form.
6. The system of claim 1 , wherein the one or more state variables comprise registers, flags, memory locations, I/O devices.
7. A method for analyzing two versions or variants of potentially malicious computer programs to locate components that have the same effect on a system's state variables through potentially using different sequences of instructions, comprising:
obtaining a first section of computer code in a binary executable file format;
disassembling the first section of code in the binary executable file format to form a section of code in assembly format;
decomposing the section of computer code in assembly format into one or more code fragments;
performing a first level of abstraction on at least one of the one or more code fragments to acquire at least one semantics statement, comprising mapping a code fragment to a semantics statement, wherein each semantics statement summarizes changes made by one or more instructions of the code fragment to one or more state variables of the processor, the changes described in a form independent of the instructions of the code fragment;
applying a second level of abstraction on the at least one semantics statement to result in at least one first generalized statement, comprising consistently replacing one or more register names of the semantics statement with one or more logical variables wherein said replacement is consistent if two occurrences of identical register names are always replaced by the same unique logical variable;
computing an index for one or more generalized statements;
storing the index in a database;
repeating the obtain step, disassemble step, decompose step, perform step, and apply step to a second section of computer code, resulting in at least one second generalized statement;
comparing the at least one first generalized statement to the at least one second generalized statement to form a comparison, the comparison showing the similarity between the changes made to one or more state variables of the processor by one or more instructions of the code fragment on the first section of computer code and the changes made to one or more state variables of the processor by one or more instructions of the code fragment of the second section of computer, and producing an output related to the comparison;
wherein the main memory in communication with the processor via communication infrastructure and storing instructions that, when executed by the processor, cause the processor to index the at least one first generalized statement and the at least one second generalized statement, and storing the index in a database, wherein said database is a cloud computing database; and
wherein a result is displayed to a user.
8. The method of claim 7 , wherein the comparison is configured for display with a user interface.
9. The method of claim 7 , indexing the at least one first generalized statement and the at least one second generalized statement, and storing the index in a database.
10. The method of claim 9 , searching the database for computer code similar to a section of computer code of interest by repeating the interpret step, the simplify step and indexing step to the computer code of interest and comparing the indexes for similarity.
11. The method of claim 7 , wherein the at least one of the one or more code fragments is symbolically interpreted using symbolic values comprising a mathematical expression.
12. The method of claim 11 , wherein the mathematical expression is in canonical form.
13. The method of claim 7 , wherein the one or more state variables comprise registers, flags, memory locations, I/O devices.
14. A non-transitory computer-readable storage medium for analyzing for similar computer code in a collection of versions and variants of potentially malicious computer programs to locate code that have the same effect on the system's state variables through potentially using different sequences of instructions, comprising:
obtaining a first section of computer code in a binary executable file form at;
disassembling the first section of code in the binary executable file format to form a section of code in assembly format;
decomposing the section of computer code in assembly format into one or more code fragments;
performing a first level of abstraction on at least one of the one or more code fragments to acquire at least one semantics statement, comprising mapping a code fragment to a semantics statement, wherein each semantics statement summarizes changes made by one or more instructions of the code fragment to one or more state variables of the processor, the changes described in a form independent of the instructions of the code fragment;
applying a second level of abstraction on the at least one semantics statement to result in at least one first generalized statement, comprising consistently replacing one or more register names of the semantics statement with one or more logical variables wherein said replacement is consistent if two occurrences of identical register names are always replaced by the same unique logical variable;
computing an index for one or more generalized statements;
storing the index in a database;
repeating the obtain step, disassemble step, decompose step, perform step, and apply step to a second section of computer code, resulting in at least one second generalized statement;
comparing the at least one first generalized statement to the at least one second generalized statement to form a comparison, the comparison showing the similarity between the changes made to one or more state variables of the processor by one or more instructions of the code fragment on the first section of computer code and the changes made to one or more state variables of the processor by one or more instructions of the code fragment of the second section of computer, and producing an output related to the comparison;
wherein the main memory in communication with the processor via communication infrastructure and storing instructions that, when executed by the processor, cause the processor to index the at least one first generalized statement and the at least one second generalized statement, and storing the index in a database, wherein said database is a cloud computing database; and
wherein a result is displayed to a user.
15. The non-transitory computer-readable storage medium of claim 14 , wherein the at least one section of computer code is obtained from at least a first computer program and at least a second computer program.
16. The non-transitory computer-readable storage medium of claim 14 , wherein the first level of abstraction includes symbolic interpretation using symbolic values comprising a mathematical expression in canonical form.
17. The non-transitory computer-readable storage medium of claim 14 , wherein the one or more state variables comprise registers, flags, memory locations, I/O devices.