Memoized Semantics-Based Binary Diffing with Application to Malware Lineage Inference - ICT Systems Security and Privacy Protection Access content directly
Conference Papers Year : 2015

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

Jiang Ming
  • Function : Author
  • PersonId : 986176
Dongpeng Xu
  • Function : Author
  • PersonId : 986177
Dinghao Wu
  • Function : Author
  • PersonId : 986178


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).
Fichier principal
Vignette du fichier
337885_1_En_28_Chapter.pdf (4 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01345132 , version 1 (13-07-2016)





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⟩
82 View
114 Download



Gmail Facebook X LinkedIn More