Premium
Toward efficient and accurate function‐call graph matching of binary codes
Author(s) -
Huang DongXing,
Tang Yong,
Wang Yi,
Wei ShuNing
Publication year - 2018
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.4871
Subject(s) - computer science , matching (statistics) , software , theoretical computer science , binary number , graph , blossom algorithm , code (set theory) , algorithm , node (physics) , function (biology) , mathematics , arithmetic , statistics , programming language , set (abstract data type) , structural engineering , evolutionary biology , engineering , biology
Summary Reverse engineering, software plagiarism detection, and malware analysis have always been important issues in software and security fields. For a binary code, the function‐call graph (FCG) reflects its capability, structure, and intrinsic relations, which motivates us to study FCG matching and its applications in those problems systematically. In this work, we propose an FCG matching algorithm based on Hungarian algorithm that solves the maximum weight matching problem in polynomial time and makes matching between graphs of large scale possible. Also, optimizations including node pairs pruning and forward matching are proposed to improve the efficiency and accuracy of FCG matching algorithm. Finally, a series of experiments are conducted to show that FCG matching is an effective method and has huge application potentiality in software and security analysis.