Virtual structures and heterogeneous nodes in dependency graphs for detecting metamorphic malware

The traditional way to identify malicious programs is to compare the code body with a set of previously stored code patterns, also known as signatures, extracted from already identified malware code. To nullify this identification process, the malware developers can insert in their creations the ability to modify the malware code when the next contamination process takes place, using obfuscation techniques. One way to deal with this metamorphic malware behavior is the use of dependency graphs, generated by surveying dependency relationships among code elements, creating a model that is resilient to code mutations. Analog to the signature model, a matching procedure that compares these graphs with a reference graph database is used to identify a malware code. Since graph matching is a NP-hard problem, it is necessary to find ways to optimize this process, so this identification technique can be applied. Using dependency graphs extracted from binary code, we present an approach to reduce the size of the reference dependency graphs stored on the graph database, by introducing a node differentiation based on its features. This way, in conjunction with the insertion of virtual paths, it is possible to build a virtual clique used to identify and dispose of less relevant elements of the original graph. The use of dependency graph reduction also produces more stable results in the matching process. To validate these statements, we present a methodology for generating these graphs from binary programs and compare the results achieved with and without the proposed approach in the identification of the Evol and Polip metamorphic malware.