Software classification using phylogenetic techniques

1. A computer-implemented method, comprising:

obtaining dynamic traces of a representative set of software programs, by a computing system, wherein the dynamic traces comprise time-ordered sequences of execution commands extracted from running software binaries;

developing metrics, by the computing system, using the dynamic traces;

reconstructing, by the computing system, an evolutionary history of the representative set of software programs, generating a reference phylogeny based on the dynamic traces and developed metrics; and

classifying one or more unknown software programs, by the computing system, against the reference phylogeny, wherein

the construction of the reference phylogeny comprises:

identifying, by the computing system, an instruction sequence segment (n-gram) length sufficient to discriminate between programs of the representative set of software programs from different families, and short enough to be present in variants of a same family,

comparing different sequence similarity measures, by the computing system, to convert an n-gram match distribution of a pair of dynamic traces into a phylogenetic distance, and

analyzing, by the computing system, whether removing contiguous repeats influences classification of the dynamic traces.

2. The computer-implemented method of claim 1 , further comprising:

constructing a feature vector, by the computing system, for each software program in the representative set of software programs, wherein

feature values of the feature vector correspond to the occurrence frequencies of each n-gram in the dynamic traces.

3. The computer-implemented method of claim 1 , wherein the classification of the one or more unknown software programs comprises:

identifying, by the computing system, unique identifier signatures including n-grams extracted from the dynamic traces of the reference software programs; and

assigning the identifier signatures, by the computing system, to nodes of the reference phylogeny.

4. The computer-implemented method of claim 1 , further comprising:

classifying the one or more unknown software programs, by the computing system, to a node on the reference phylogeny consistent with a set of n-gram signatures that the one or more unknown software programs contain, wherein

the classification determines whether the one or more unknown software programs are variants of an existing family, hybrids of two or more different software programs, or constitute a new software strain.

5. The computer-implemented method of claim 1 , further comprising:

calculating, by the computing system, a way that a number of random matches varies with n-gram size is characterized by calculating a relative frequency at which each instruction occurs in the set of dynamic traces extracted from a software corpus;

determining, by the computing system, mean and maximum lengths of the instruction sequences; and

calculating, by the computing system, an expected number of n-gram matches in a pair of dynamic traces with arbitrary sequences of instructions, the expected number of n-gram matches in a pair of instruction traces of length L given by:

(

∑

j

=

1

N

⁢

f

j

2

)

n

⁢

L

2

where N is a number of instructions.

6. The computer-implemented method of claim 1 , further comprising:

investigating, by the computing system, a number of random matches as a function of n-gram size when n-grams extracted from a dynamic trace are reduced to a unique set by determining an average and maximum number of unique n-grams in reference software programs for each n-gram size;

constructing, by the computing system, arbitrary unique n-gram sets by sequentially generating n-grams one at a time and removing duplicates until a desired size is reached; and

calculating, by the computing system, a mean number of matching n-grams for a predetermined number of pairs of average and maximum-sized unique n-gram sets.

7. The computer-implemented method of claim 6 , wherein each n-gram is generated by sampling the set of instructions n times with replacement, where a probability of choosing a particular instruction is proportional to a relative frequency of the particular instruction.

8. The computer-implemented method of claim 1 , further comprising:

preprocessing the dynamic traces, by the computing system, removing loops and repeated function calls, wherein

all repeating subsequences of at least a predetermined number of contiguous instructions are removed.

9. The computer-implemented method of claim 1 , further comprising:

evaluating, by the computing system, an extent to which phylogenies generated by different distance functions and n-gram sizes from original and preprocessed instruction traces correspond to a classification produced by analysis software, wherein

the reference phylogeny comprises phylogenetic trees generated by determining a phylogenetic distance between each pair of software programs in a distance matrix and using a resulting distance matrix to build a neighbor-joining phylogenetic tree, and

the distance matrix is constructed by comparing the n-gram feature vectors extracted from the dynamic traces for each pair of software programs.

10. The computer-implemented method of claim 9 , further comprising:

calculating the phylogenetic distance, by the computing system, using a binary proportional (BP) algorithm, a binary proportional-inverse document frequency (BP-IDF) algorithm, a binary cosine similarity-inverse document frequency (BCS-IDF) algorithm, a term frequency cosine similarity-inverse document frequency (TFCS-IDF) algorithm, or any combination thereof.

11. The computer-implemented method of claim 1 , further comprising:

assigning signatures, by the computing system, to nodes in the reference phylogeny by extracting features of interest from an instruction sequence of each software program in the representative set of software programs;

building, by the computing system, a binary character matrix from all signatures that are shared by at least two software programs;

finding, by the computing system, a set of descendant leaves for each internal node on the reference phylogeny; and

assigning each signature, by the computing system, to an internal node that is a lowest common ancestor of all leaves that contain the internal node.

12. The computer-implemented method of claim 1 , further comprising:

classifying the one or more unknown software programs, by the computing system, to a node on the reference phylogeny by extracting a set of all signatures from the dynamic trace of the one or more unknown software programs;

matching, by the computing system, the signatures of the one or more unknown software programs against signatures on the reference phylogeny; and

identifying, by the computing system, a set of internal nodes that the signatures of the one or more unknown software programs belong to, wherein

when there are no signature matches, a given unknown software program is classified to a root of the tree and considered a potentially novel software program, the reference phylogeny is updated to reflect this increased diversity, and the signatures at the internal nodes of the set of internal nodes are reassigned,

when a set of signature-containing nodes is a subset of internal nodes of the set of internal nodes along a single path from a leaf to the root of the tree, the given unknown software program is classified to a node that is farthest from the root, and

when the set of signature-containing nodes are associated to multiple lineages, the given unknown software program is classified to a lowest common ancestor of nodes that are farthest from the root.

13. The computer-implemented method of claim 1 , further comprising:

generating artificially mutated variants of the representative set of software programs, by the computing system, to determine whether they are classified in correct families.

14. A computer-implemented malware classification method, comprising:

constructing a reference phylogeny, by a computing system, based on finding matches of similar instruction sequences in dynamic traces of a representative set of software programs by comparing different sequence similarity measures to convert an n-gram match distribution of a pair of dynamic traces into a phylogenetic distance;

developing metrics, by the computing system, using the dynamic traces; and

classifying one or more unknown software programs, by the computing system, against the reference phylogeny using the metrics developed using the dynamic traces of the representative set of software programs, wherein

the construction of the reference phylogeny comprises:

identifying, by the computing system, an instruction sequence segment (n-gram) length sufficient to discriminate between programs from different families, and short enough to be present in variants of a same family, and

analyzing, by the computing system, whether removing contiguous repeats influences classification of the dynamic traces.

15. A non-transitory computer-readable medium storing a computer program, the computer program configured to cause at least one processor to:

construct a reference phylogeny of a representative set of software programs; and

classify one or more unknown software programs to a node on the reference phylogeny consistent with a set of n-gram signatures that the one or more unknown software programs contain, wherein

the classification determines whether the one or more unknown software programs are variants of an existing family, hybrids of two or more different software programs, or constitute a new software strain, and

the construction of the reference phylogeny further comprises:

identifying, by the computing system, an instruction sequence segment (n-gram) length sufficient to discriminate between programs from different families, and short enough to be present in variants of a same family, and

analyzing, by the computing system, whether removing contiguous repeats influences classification of the dynamic traces.

16. The non-transitory computer-readable medium of claim 15 , wherein the computer program is further configured to cause the at least one processor to:

classify the one or more unknown software programs to the most specific node on the reference phylogeny consistent with a set of n-gram signatures that the one or more unknown software programs contain by extracting a set of all signatures from the dynamic trace of the unknown software program;

match the signatures of the one or more unknown software programs against signatures on the reference phylogeny; and

identify a set of internal nodes that the signatures of the one or more unknown software programs belong to, wherein

when there are no signature matches, a given unknown software program is classified to a root of the tree and considered a potentially novel software program, the reference phylogeny is updated to reflect this increased diversity, and the signatures at the internal nodes of the set of internal nodes are reassigned,

when a set of signature-containing nodes is a subset of internal nodes of the set of internal nodes along a single path from a leaf to the root of the tree, the given unknown software program is classified to a node that is farthest from the root, and

when the set of signature-containing nodes are associated to multiple lineages, the given unknown software program is classified to a lowest common ancestor of nodes that are farthest from the root.