research-article

Tracelet-based code search in executables

Authors:

Eran YahavAuthors Info & Claims

PLDI '14: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 349 - 360

https://doi.org/10.1145/2594291.2594343

Published: 09 June 2014 Publication History

Abstract

We address the problem of code search in executables. Given a function in binary form and a large code base, our goal is to statically find similar functions in the code base. Towards this end, we present a novel technique for computing similarity between functions. Our notion of similarity is based on decomposition of functions into tracelets: continuous, short, partial traces of an execution. To establish tracelet similarity in the face of low-level compiler transformations, we employ a simple rewriting engine. This engine uses constraint solving over alignment constraints and data dependencies to match registers and memory addresses between tracelets, bridging the gap between tracelets that are otherwise similar. We have implemented our approach and applied it to find matches in over a million binary functions. We compare tracelet matching to approaches based on n-grams and graphlets and show that tracelet matching obtains dramatically better precision and recall.

References

[1]

A heap based vulnerability in gnu's rtapelib.c. http://www.cvedetails.com/cve/CVE-2010-0624/.

[2]

Hex-rays IDAPRO. http://www.hex-rays.com.

[3]

Yard-plot. http://pypi.python.org/pypi/yard.

[4]

Balakrishnan, G., and Reps, T. Divine: discovering variables in executables. In VMCAI'07 (2007), pp. 1--28.

Digital Library

[5]

Ball, T., and Larus, J. R. Efficient path profiling. In Proceedings of the 29th Int. Symp. on Microarchitecture (1996), MICRO 29.

Digital Library

[6]

Bansal, S., and Aiken, A. Automatic generation of peephole superoptimizers. In ASPLOS XII (2006).

Digital Library

[7]

Bellon, S., Koschke, R., Antoniol, G., Krinke, J., and Merlo, E. Comparison and evaluation of clone detection tools. IEEE TSE 33, 9 (2007), 577--591.

Digital Library

[8]

Bruschi, D., Martignoni, L., and Monga, M. Detecting self-mutating malware using control-flow graph matching. In DIMVA'06.

Digital Library

[9]

Comparetti, P., Salvaneschi, G., Kirda, E., Kolbitsch, C., Kruegel, C., and Zanero, S. Identifying dormant functionality in malware programs. In IEEE Symp. on Security and Privacy (2010).

Digital Library

[10]

Horwitz, S. Identifying the semantic and textual differences between two versions of a program. In PLDI '90.

Digital Library

[11]

Horwitz, S., Reps, T., and Binkley, D. Interprocedural slicing using dependence graphs. In PLDI '88 (1988).

Digital Library

[12]

Jang, J., Woo, M., and Brumley, D. Towards automatic software lineage inference. In USENIX Security (2013).

Digital Library

[13]

Khoo, W. M., Mycroft, A., and Anderson, R. Rendezvous: a search engine for binary code. In MSR '13.

Digital Library

[14]

Kruegel, C., Kirda, E., Mutz, D., Robertson, W., and Vigna, G. Polymorphic worm detection using structural information of executables. In Proc. of int. conf. on Recent Advances in Intrusion Detection, RAID'05.

Digital Library

[15]

Myles, G., and Collberg, C. K-gram based software birthmarks. In Proceedings of the 2005 ACM symposium on Applied computing, SAC '05, pp. 314--318.

Digital Library

[16]

Partush, N., and Yahav, E. Abstract semantic differencing for numerical programs. In SAS (2013).

[17]

Reps, T., Ball, T., Das, M., and Larus, J. The use of program profiling for software maintenance with applications to the year 2000 problem. In ESEC '97/FSE-5.

Digital Library

[18]

Rosenblum, N., Zhu, X., and Miller, B. P. Who wrote this code? identifying the authors of program binaries. In ESORICS'11.

Digital Library

[19]

Rosenblum, N. E., Miller, B. P., and Zhu, X. Extracting compiler provenance from program binaries. In PASTE'10.

Digital Library

[20]

Saebjornsen, A., Willcock, J., Panas, T., Quinlan, D., and Su, Z. Detecting code clones in binary executables. In ISSTA '09.

Digital Library

[21]

Schkufza, E., Sharma, R., and Aiken, A. Stochastic superoptimization. In ASPLOS '13.

Digital Library

[22]

Sharma, R., Schkufza, E., Churchill, B., and Aiken, A. Data-driven equivalence checking. In OOPSLA'13.

Digital Library

[23]

Singh, R., Gulwani, S., and Solar-Lezama, A. Automated feedback generation for introductory programming assignments. In PLDI '13, pp. 15--26.

Digital Library

[24]

Swamidass, S. J., Azencott, C.-A., Daily, K., and Baldi, P. A CROC stronger than ROC. Bioinformatics 26, 10 (May 2010).

Digital Library

[25]

Wagner, R. A., and Fischer, M. J. The string-to-string correction problem. J. ACM 21, 1 (Jan. 1974), 168--173.

Digital Library

Cited By

Avitan MRavve EVolkovich Z(2024)Assembly Function Recognition in Embedded Systems as an Optimization ProblemMathematics10.3390/math1205065812:5(658)Online publication date: 23-Feb-2024
https://doi.org/10.3390/math12050658
Ruan LXu QZhu SHuang XLin X(2024)A Survey of Binary Code Similarity Detection TechniquesElectronics10.3390/electronics1309171513:9(1715)Online publication date: 29-Apr-2024
https://doi.org/10.3390/electronics13091715
Zhang PWu CHu HJia LPeng MXu JXie MLai YKang YWang Z(2024)Shining Light on the Inter-procedural Code Obfuscation: Keep Pace with Progress in Binary DiffingACM Transactions on Architecture and Code Optimization10.1145/3701992Online publication date: 28-Oct-2024
https://doi.org/10.1145/3701992
Show More Cited By

Index Terms

Tracelet-based code search in executables
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Source code generation
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program analysis
    2. Program semantics

Recommendations

Tracelet-based code search in executables
PLDI '14

We address the problem of code search in executables. Given a function in binary form and a large code base, our goal is to statically find similar functions in the code base. Towards this end, we present a novel technique for computing similarity ...
Stochastic superoptimization
ASPLOS '13

We formulate the loop-free binary superoptimization task as a stochastic search problem. The competing constraints of transformation correctness and performance improvement are encoded as terms in a cost function, and a Markov Chain Monte Carlo sampler ...
Checking Compliance to Coding Standards for x86 Executables
UIC-ATC '10: Proceedings of the 2010 Symposia and Workshops on Ubiquitous, Autonomic and Trusted Computing

COTS component evaluation is one of the most important steps in component-based development. Enforcing the coding standard within the coding phase is one important aspect for the quality of safety-critical software. This paper addresses the problem of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '14: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2014

619 pages

ISBN:9781450327848

DOI:10.1145/2594291

General Chair:
Michael O'Boyle
University of Edinburgh
,
Program Chair:
Keshav Pingali
University of Texas, Austin

ACM SIGPLAN Notices Volume 49, Issue 6
PLDI '14
June 2014
598 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2666356
Editor:
Andy Gill
University of Kansas, Lawrence, KS
Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Seventh Framework Programme

Conference

PLDI '14

Sponsor:

PLDI '14: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 9 - 11, 2014

Edinburgh, United Kingdom

Acceptance Rates

PLDI '14 Paper Acceptance Rate 52 of 287 submissions, 18%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

172
Total Citations
View Citations
832
Total Downloads

Downloads (Last 12 months)68
Downloads (Last 6 weeks)9

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Avitan MRavve EVolkovich Z(2024)Assembly Function Recognition in Embedded Systems as an Optimization ProblemMathematics10.3390/math1205065812:5(658)Online publication date: 23-Feb-2024
https://doi.org/10.3390/math12050658
Ruan LXu QZhu SHuang XLin X(2024)A Survey of Binary Code Similarity Detection TechniquesElectronics10.3390/electronics1309171513:9(1715)Online publication date: 29-Apr-2024
https://doi.org/10.3390/electronics13091715
Zhang PWu CHu HJia LPeng MXu JXie MLai YKang YWang Z(2024)Shining Light on the Inter-procedural Code Obfuscation: Keep Pace with Progress in Binary DiffingACM Transactions on Architecture and Code Optimization10.1145/3701992Online publication date: 28-Oct-2024
https://doi.org/10.1145/3701992
Zhou AHu YXu XZhang C(2024) ARCTURUS: Full Coverage Binary Similarity Analysis with Reachability-guided EmulationACM Transactions on Software Engineering and Methodology10.1145/364033733:4(1-31)Online publication date: 11-Jan-2024
https://dl.acm.org/doi/10.1145/3640337
Pan ZHu XXia XZhan XLo DYang XRoychoudhury APaiva AAbreu RStorey M(2024)PPT4J: Patch Presence Test for Java BinariesProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639231(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639231
Dong CLi SYang SXiao YWang YLi HLi ZSun LRoychoudhury APaiva AAbreu RStorey M(2024)LibvDiff: Library Version Difference Guided OSS Version Identification in BinariesProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3623336(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3623336
Wong WWang HLi ZWang SRoychoudhury APaiva AAbreu RStorey M(2024)BinAug: Enhancing Binary Similarity Analysis with Low-Cost Input RepairingProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3623328(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3623328
Liu LWang SJiang X(2024)UniBin: Assembly Semantic-enhanced Binary Vulnerability Detection without DisassemblyInformation Sciences10.1016/j.ins.2024.121605(121605)Online publication date: Oct-2024
https://doi.org/10.1016/j.ins.2024.121605
Console FD’Aquanno GDi Luna GQuerzoni L(2023)BinBench: a benchmark for x64 portable operating system interface binary function representationsPeerJ Computer Science10.7717/peerj-cs.12869(e1286)Online publication date: 1-Jun-2023
https://doi.org/10.7717/peerj-cs.1286
Lai YZeng X(2023)A POI Recommendation Model for Intelligent Systems Using AT-LSTM in Location-Based Social Network Big DataInternational Journal on Semantic Web & Information Systems10.4018/IJSWIS.33024619:1(1-15)Online publication date: 12-Sep-2023
https://dl.acm.org/doi/10.4018/IJSWIS.330246
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents