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).
Type de document :
Communication dans un congrès
Hannes Federrath; Dieter Gollmann. 30th IFIP International Information Security Conference (SEC), May 2015, Hamburg, Germany. IFIP Advances in Information and Communication Technology, AICT-455, pp.416-430, 2015, ICT Systems Security and Privacy Protection. 〈10.1007/978-3-319-18467-8_28〉
Domaine :

Littérature citée [22 références]

https://hal.inria.fr/hal-01345132
Contributeur : Hal Ifip <>
Soumis le : mercredi 13 juillet 2016 - 11:09:43
Dernière modification le : lundi 2 octobre 2017 - 13:52:03

Fichier

337885_1_En_28_Chapter.pdf
Fichiers produits par l'(les) auteur(s)

Citation

Jiang Ming, Dongpeng Xu, Dinghao Wu. Memoized Semantics-Based Binary Diffing with Application to Malware Lineage Inference. Hannes Federrath; Dieter Gollmann. 30th IFIP International Information Security Conference (SEC), May 2015, Hamburg, Germany. IFIP Advances in Information and Communication Technology, AICT-455, pp.416-430, 2015, ICT Systems Security and Privacy Protection. 〈10.1007/978-3-319-18467-8_28〉. 〈hal-01345132〉

Métriques

Consultations de la notice

99

Téléchargements de fichiers