The Homologous Analysis Of Malware Based On Function-call Graph

Malware analysis is the important foundation of malware detection and protection. Besides analyzing malware’s different kinds of external behave, people actually also focus on the internal characteristics of malware about homology and evolution, which include where they come from, how they evelop and change, and what the relationships of them are, and so on.Resently there are only few research about the homologous and evolutional analysis of malware, but they all exist some disadvantage and deficiency. As a result, this paper presents a malware homologous analysis method based on function-call graphs of malware, the main work of this paper include:Firstly, it presents a metric called SDMFG (the Similar Distance of Malware’s Function-call Graphs)that aims to measure the function-call graphs’similarity between malware, then proves that it is a mathematical metric on graph space. The feature of the SDMFG is that it uses two aspects of informations of malware’s function-call graphs: the similarity of instructions sequences of malware’s functions that each come from a malware and the similarity of the function-call sequences of malware’s functions that each come from a malware.Secondly, it designs an algorithm of the similarity of malware’s function-call graphs based on the metric SDMFG. The algorithm first constructs a complete bipartite graph with two function-call graphs of malware, then calculate the weights of each edge in the bipartite graph using the the similarity of instructions sequences of functions that each come from a malware and the similarity of the function-call sequences of malware’s functions that each come from a malware, and then use the Kuhn-Munkres algorithm calculate the max-weight matching of the bipartite graph with the weights of edges in the bipartite graph, lastly calculate the value of SDMFG between the two function-call graphs of malware. This algorithm reduces the time cost for calculating the similarity of two function-call graphs, enlarges the applicative range of the methed of graph similar matching, and ensures the accuracy of the methed of graph similar matching in a certain extent.Finally, using for reference on the methods that construct the phylogenetic tree among genes or speces in bioinformatics, this paper presents a method that constructs the phylogenetic tree of malware based on function-call graphs of malware, and do some experiments using value of SDMFG. The experiment results test and verify the effectiveness, efficiency and scalability of the method.The malware homologous analysis method based on function-call graphs have important academic and practical value on malware protection and computer crime forensic s.