Control flow graph representation and classification
View Patent ↗A software sample is identified that includes code and a control flow graph is generated for each of a plurality of functions included in the sample. Features are identified in each of the functions that correspond to instances of a set of control flow fragment types. A feature set is generated for the sample from the identified features.
1. At least one non-transitory machine accessible storage medium having instructions stored thereon, the instructions when executed on a machine, cause the machine to:
identify a particular sample comprising code;
generate a structure to represent the particular sample, wherein the structure represents a plurality of functions included in the particular sample;
identify, in each of the functions, respective control flow fragments of the function;
identify a subset of the fragments of the plurality of functions as features of the particular sample based on each of the subset of fragments comprising an instance of a respective one of a predefined set of fragment types;
generate a feature set for the particular sample from the identified features; and
classify the particular sample based on a determination that feature sets of a cluster of other samples overlap with the feature set of the particular sample.
2. The storage medium of claim 1 , wherein the instructions, when executed, are to further cause the machine to combine the features identified for each of the functions to generate a consolidated string for the particular sample, wherein the feature set is generated from the consolidated string.
3. The storage medium of claim 2 , wherein the instructions, when executed, are to further cause the machine to generate, for each of the functions, a string describing the respective features identified for the function.
4. The storage medium of claim 3 , wherein combining the features includes:
identifying a call in a particular one of the plurality of functions to another one of the plurality of functions; and
replacing a portion of the string of the particular function referencing the other function with contents of the string of the other function.
5. The storage medium of claim 3 , wherein identifying the features includes abstracting each of the strings of the functions such that only features of the set of fragment types are described in the strings and fragments of the functions of types outside the set of fragment types are excluded from the feature set.
6. The storage medium of claim 1 , wherein the set of fragment types comprise memory accesses by the function and function calls by the function.
7. The storage medium of claim 5 , wherein identifying the features comprises:
identifying instances of memory accesses by each of the functions; and
identifying instances of function calls by each of the functions.
8. The storage medium of claim 1 , wherein the feature set identifies each of the features identified for each of the functions.
9. The storage medium of claim 1 , wherein the feature set comprises an n-graph.
10. The storage medium of claim 1 , wherein classifying the particular sample includes determining a set of features relevant to a cluster of samples.
11. The storage medium of claim 1 , wherein classifying the particular sample includes determining whether to classify the sample as malware.
12. The storage medium of claim 1 , wherein classifying the particular sample includes determining whether the sample is likely one of one or more families of malware.
13. The storage medium of claim 1 , wherein identifying the features includes abstracting each of the structures such that only features of the set of control flow fragment types are described in the structures.
14. A method comprising:
identifying a particular sample comprising code;
generating, using at least one data processing apparatus, a structure for the particular sample, wherein the structure represents a plurality of functions included in the particular sample;
identifying, using at least one data processing apparatus, in each of the functions, respective fragments of the function;
identify a subset of the fragments of the plurality of functions as features of the particular sample based on each of the subset of fragments comprising an instance of a respective one of a predefined set of fragment types;
generating, using at least one data processing apparatus, a feature set for the particular sample from the identified features; and
classifying the particular sample based on a determination that feature sets of a cluster of other samples overlap with the feature set of the particular sample.
15. The method of claim 14 , further comprising combining the features identified for each of the functions to generate a consolidated string for the particular sample, wherein the feature set is generated from the consolidated string.
16. The method of claim 15 , further comprising generating, for each of the functions, a string describing the respective features identified for the function.
17. The method of claim 16 , wherein combining the features includes:
identifying a call in a particular one of the plurality of functions to another one of the plurality of functions; and
replacing a portion of the string of the particular function referencing the other function with contents of the string of the other function.
18. The method of claim 14 , further comprising receiving a plurality of samples including the particular sample.
19. The method of claim 18 , wherein the plurality of samples are received from a plurality of sources.
20. A system comprising:
at least one processor device;
at least one memory element; and
a feature set builder, when executed by the at least one processor device, to:
identify a particular sample comprising code;
generate a structure for the particular sample, wherein the structure represents a plurality of functions included in the particular sample;
identify, in each of the functions, respective fragments of the function;
identify a subset of the fragments of the plurality of functions as features of the particular sample based on each of the subset of fragments comprising an instance of a respective one of a predefined set of fragment types;
generate a feature set for the particular sample from the identified subset of the fragments; and
classify the particular sample based on a determination that feature sets of a cluster of other samples overlap with the feature set of the particular sample.
21. The system of claim 20 , wherein the cluster comprises a particular one of a plurality of clusters.
22. The system of claim 20 , wherein the feature set identifies a subset of features identified in the structures of the functions of the particular sample.
23. The system of claim 22 , wherein the subset of features corresponds to memory accesses and function calls in the sample code.