BinSim: Trace-based Semantic Binary Diffing via System Call Sliced Segment Equivalence Checking

Authors: 

Jiang Ming, University of Texas at Arlington; Dongpeng Xu, Yufei Jiang, and Dinghao Wu, Pennsylvania State University

Abstract: 

Detecting differences between two binary executables (binary diffing), first derived from patch analysis, have been widely employed in various software security analysis tasks, such as software plagiarism detection and malware lineage inference. Especially when analyzing malware variants, pervasive code obfuscation techniques have driven recent work towards determining semantic similarity in spite of ostensible difference in syntax. Existing ways rely on either comparing runtime behaviors or modeling code snippet semantics with symbolic execution. However, neither approach delivers the expected precision. In this paper, we propose system call sliced segment equivalence checking, a hybrid method to identify fine-grained semantic similarities or differences between two execution traces. We perform enhanced dynamic slicing and symbolic execution to compare the logic of instructions that impact on the observable behaviors. Our approach improves existing semantics-based binary diffing by 1) inferring whether two executable binaries’ behaviors are conditionally equivalent; 2) detecting the similarities or differences, whose effects spread across multiple basic blocks. We have developed a prototype, called BinSim, and performed empirical evaluations against sophisticated obfuscation combinations and more than 1;000 recent malware samples, including now-infamous crypto ransomware. Our experimental results show that BinSim can successfully identify fine-grained relations between obfuscated binaries, and outperform existing binary diffing tools in terms of better resilience and accuracy.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {203720,
author = {Jiang Ming and Dongpeng Xu and Yufei Jiang and Dinghao Wu},
title = {{BinSim}: Trace-based Semantic Binary Diffing via System Call Sliced Segment Equivalence Checking},
booktitle = {26th USENIX Security Symposium (USENIX Security 17)},
year = {2017},
isbn = {978-1-931971-40-9},
address = {Vancouver, BC},
pages = {253--270},
url = {https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/ming},
publisher = {USENIX Association},
month = aug
}

Presentation Video