In every day, Anti-virus Corporations receive large number of potentially harmful executables. Many of the malicious samples among these executables are variations of their early versions that created by their authors to evade the detection. Consequently, robust detection approaches are required, capable of recognizing similar samples automatically. In this paper, malware detection through call graph was studied, the call graph functions of a binary executable are represented as vertices, and the calls between those functions as edges. By representing malware samples as call graphs, it is possible to derive and detect structural similarities between multiple samples. The present paper provides a new malware detection algorithm based on the analysis of graphs introduced from instructions of the executable objects, the graph is constructed through the graph extractor, and the maximum common sub-graph similarity measures is approximated, then the graphs are sent to support vector machine to perfectly approximate the similarity value. © 2012 IEEE.