Skip to Main content Skip to Navigation
Conference papers

Memoized Semantics-Based Binary Diffing with Application to Malware Lineage Inference

Abstract : Identifying differences between two executable binaries (binary diffing) has compelling security applications, such as software vulnerability exploration, “1-day” exploit generation and software plagiarism detection. Recently, binary diffing based on symbolic execution and constraint solver has been proposed to look for the code pairs with the same semantics, even though they are ostensibly different in syntactics. Such logical-based method captures intrinsic differences of binary code, making it a natural choice to analyze highly-obfuscated malicious program. However, semantics-based binary diffing suffers from significant performance slowdown, hindering it from analyzing large-scale malware samples. In this paper, we attempt to mitigate the high overhead of semantics-based binary diffing with application to malware lineage inference. We first study the key obstacles that contribute to the performance bottleneck. Then we propose basic blocks fast matching to speed up semantics-based binary diffing. We introduce an union-find set structure that records semantically equivalent basic blocks. Managing the union-find structure during successive comparisons allows direct reuse of previously computed results. Moreover, we purpose to concretize symbolic formulas and cache equivalence queries to further cut down the invocation times of constraint solver. We have implemented our technique on top of iBinHunt and evaluated it on 12 malware families with respect to the performance improvement when performing intra-family comparisons. Our experimental results show that our methods can accelerate symbolic execution from 2.8 x to 5.3 x (with an average 4.0 x), and reduce constraint solver invocation by a factor of 3.0 x to 6.0 x (with an average 4.3 x).
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Wednesday, July 13, 2016 - 11:09:43 AM
Last modification on : Thursday, August 22, 2019 - 12:04:03 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Jiang Ming, Dongpeng Xu, Dinghao Wu. Memoized Semantics-Based Binary Diffing with Application to Malware Lineage Inference. 30th IFIP International Information Security Conference (SEC), May 2015, Hamburg, Germany. pp.416-430, ⟨10.1007/978-3-319-18467-8_28⟩. ⟨hal-01345132⟩



Record views


Files downloads