Recovering source code structure from program binaries
Recovering structure from binaries is disclosed. A binary file having components including a plurality of linker objects is received. A cross reference map of linker objects is created. The linker objects are associated based on calls. An address space distance for each call is determined. Boundaries are defined in the cross reference map based on the address space distance. Subsets are defined as portions of the file that are separated by the boundaries.
1. A system for detecting unauthorized linker objects by performing a similarity search on a binary file, wherein the similarity search includes determining whether a plurality of linker objects included in the binary file are derived from a common linker object, the system comprising:
at least one processor; and
at least one memory storing instructions that, when executed by the at least one processor, cause the system to:
in response to receiving the binary file including the plurality of linker objects:
categorize one or more linker object subsets from the plurality of linker objects of the binary file that is to be stored at a database, wherein each of the one or more linker object subsets includes multiple linker objects of the plurality of linker objects;
generate a cross reference map of the plurality of linker objects by defining an edge between a respective caller and callee that are included in each of the one or more linker object subsets;
calculate an address space distance between the respective caller and callee that are included in each of the one or more linker object subsets;
define respective boundaries that separate the multiple linker objects of each of the one or more linker object subsets by labeling the edge with the address space distance;
establish first and second boundary threshold values;
compare the respective boundaries associated with each of the one or more linker object subsets to the first boundary threshold value;
in response to determining that at least one subset of the one or more linker object subsets includes the respective boundaries that satisfies the first boundary threshold value:
output a listing with the at least one subset that satisfies the first boundary threshold value, wherein the listing indicates that the multiple linker objects of the at least one subset are derived from the common linker object and that the multiple linker objects are unauthorized, and
preventing the binary file including the multiple linker objects from being stored at the database; and
in response to determining that the at least one subset does not satisfy the first boundary threshold value:
associate the at least one subset with the second boundary threshold value.
2. The system of claim 1 , wherein the cross reference map includes a function call graph.
3. The system of claim 1 , wherein associating the at least one subset with the second boundary threshold value indicates that the multiple linker objects of the at least one subset are non-derivatives of the common linker object.
4. The system of claim 1 , wherein the respective boundaries are defined by links that are based on the address space distance associated with the respective caller and callee.
5. The system of claim 1 , wherein each linker object of the plurality of linker objects includes at least one function and at least one variable generated from source code.
6. The system of claim 1 , wherein the first and second boundary threshold values are adjustable.
7. The system of claim 1 , wherein the at least one subset that satisfies the first boundary threshold value is ordered within the listing according to the address space distance.
8. The system of claim 1 , wherein the respective boundaries include linker object boundaries.
9. The system of claim 1 , wherein the respective boundaries include a static library function boundary.
10. The system of claim 1 , wherein the at least one processor further causes the system to:
recover data boundaries for the plurality of linker objects.
11. The system of claim 1 , wherein the at least one processor further causes the system to:
recover data boundaries for static libraries.
12. The system of claim 1 , wherein the at least one processor further causes the system to:
recover source code layout.
13. The system of claim 1 , wherein the at least one processor further causes the system to:
recover the respective boundaries by identifying articulation nodes in a graph.
14. The system of claim 1 , wherein the at least one processor further causes the system to:
recover the respective boundaries by computing a minimum cut in a graph.
15. A computer-implemented method for detecting unauthorized linker objects by performing a similarity search on a binary file, wherein the similarity search includes determining whether a plurality of linker objects included in the binary file are derived from a common linker object, comprising, at a computing device:
in response to the computing device receiving the binary file that includes the plurality of linker objects:
categorizing, at the computing device, one or more linker object subsets from the plurality of linker objects of the binary file that is to be stored at a database, wherein each of the one or more linker object subsets includes multiple linker objects of the plurality of linker objects;
generating, at the computing device, a cross reference map of the plurality of linker objects by defining an edge between a respective caller and callee that are included in each of the one or more linker object subsets
calculating, at the computing device, an address space distance between the respective caller and callee that are included in each of the one or more linker object subsets:
defining, at the computing device, respective boundaries that separate the multiple linker objects of each of the one or more linker object subsets by labeling the edge with the address space distance;
establishing, at the computing device, first and second boundary threshold values;
comparing, at the computing device, the respective boundaries associated with each of the one or more linker object subsets to the first boundary threshold value; and
in response to determining that at least one subset of the one or more linker object subsets includes the respective boundaries that satisfies the first boundary threshold value:
outputting, at the computing device, a listing with the at least one subset that satisfies the first boundary threshold value, wherein the listing indicates that the multiple linker objects of the at least one subset are derived from the common linker object and that the multiple linker objects are unauthorized, and
preventing the multiple linker objects from being stored at the database, and
in response to determining that the at least one subset does not satisfy the first boundary threshold value:
associating, at the computing device, the at least one subset with second boundary threshold value.
16. The computer-implemented method of claim 15 , wherein the at least one subset that satisfies the first boundary threshold value is ordered within the listing according to the address space distance.
17. The computer-implemented method of claim 15 , wherein the respective boundaries are defined by links that are based on the address space distance associated with the respective caller and callee.
18. At least one non-transitory computer readable storage medium storing instructions for detecting unauthorized linker objects by determining whether a plurality of linker objects included in a binary file are derived from a common linker object that, when executed by at least one processor included in a computing device, cause the computing device to:
in response to receiving the binary file that includes the plurality of linker objects:
categorize one or more linker object subsets from the plurality of linker objects of the binary file that is to be stored at a database, wherein each of the one or more linker object subsets includes multiple linker objects of the plurality of linker objects:
generate a cross reference map of the plurality of linker objects by defining an edge between a respective caller and callee that are included in each of the one or more linker object subsets;
calculate an address space distance between the respective caller and callee that are included in each of the one or more linker object subsets;
define respective boundaries that separate the multiple linker objects of each of the one or more linker object subsets by labeling the edge with the address space distance;
establish first and second boundary threshold values;
compare the respective boundaries associated with each of the one or more linker object subsets to the first boundary threshold value; and
in response to determining that at least one subset of the one or more linker object subsets includes the respective boundaries that satisfies the first boundary threshold value:
output a listing with the at least one subset that satisfies the first boundary threshold value, wherein the listing indicates that the multiple linker objects of the at least one subset are derived from the common linker object and that the multiple linker objects are unauthorized, and
preventing the multiple linker objects from being stored at the database, and
in response to determining that the at least one subset does not satisfy the first boundary threshold value:
associate the at least one subset with the second boundary threshold value.
19. The at least one non-transitory computer readable storage medium of claim 18 , wherein the at least one subset that satisfies the first boundary threshold value is ordered within the listing according to the address space distance.
20. The at least one non-transitory computer readable storage medium of claim 18 , wherein the respective boundaries are defined by links that are based on the address space distance associated with the respective caller and callee.