More Web Proxy on the site http://driver.im/

research-article

Supervised learning for provenance-similarity of binaries

Authors:

Arie GurfinkelAuthors Info & Claims

KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 15 - 23

https://doi.org/10.1145/2020408.2020419

Published: 21 August 2011 Publication History

Abstract

Understanding, measuring, and leveraging the similarity of binaries (executable code) is a foundational challenge in software engineering. We present a notion of similarity based on provenance -- two binaries are similar if they are compiled from the same (or very similar) source code with the same (or similar) compilers. Empirical evidence suggests that provenance-similarity accounts for a significant portion of variation in existing binaries, particularly in malware. We propose and evaluate the applicability of classification to detect provenance-similarity. We evaluate a variety of classifiers, and different types of attributes and similarity labeling schemes, on two benchmarks derived from open-source software and malware respectively. We present encouraging results indicating that classification is a viable approach for automated provenance-similarity detection, and as an aid for malware analysts in particular.

References

[1]

Aliser worm. http://www.sophos.com/security/analyses/viruses-and-spyware/w32aliserd%am.html.

[2]

M. Apel, C. Bockermann, and M. Meier. Measuring similarity of malware behavior. In Proc. of LCN, 2009.

[3]

M. Braverman, J. Williams, and Z. Mador. Microsoft security intelligence report: January--June 2006, 2006. http://microsoft.com/downloads/details.aspx?FamilyId=1C443104--5B3F-4C3%A-868E-36A553FE2A02.

[4]

L. Breiman. Random Forests. Machine Learning, 45(1):5--32, 2001.

Digital Library

[5]

D. Brumley and J. Newsome. Alias analysis for assembly. Technical report Carnegie Mellon University-CS-06--180{R}, Carnegie Mellon University, Pittsburgh, 2006.

[6]

J. Caballero, N. M. Johnson, S. McCamant, and D. Song. Binary code extraction and interface identification for security applications. Technical report UCB/EECS-2009--133, University of California, Berkeley, Berkeley, CA, October 2009.

[7]

S. Choi, H. Park, H. il Lim, and T. Han. A Static Birthmark of Binary Executables Based on API Call Structure. In Proc. of ASIAN, 2007.

Digital Library

[8]

C. Cohen and J. Havrilla. Function Hashing for Malicious Code Analysis, 2009. www.cert.org/research/2009research-report.pdf.

[9]

T. Dullien and R. Rolles. Graph-based comparison of Executable Objects. In Proc. of SSTIC, 2005.

[10]

H. Flake. Structural Comparison of Executable Objects. In Proc. of DMIVA, 2004.

[11]

D. Gao, M. K. Reiter, and D. X. Song. BinHunt: Automatically Finding Semantic Differences in Binary Programs. In Proc. of ICICS, 2008.

Digital Library

[12]

M. Hayes, A. Walenstein, and A. Lakhotia. Evaluation of malware phylogeny modelling systems using automated variant generation. Journal in Computer Virology (JCV), 5(4):335--343, November 2009.

[13]

X. Hu, T. Chiueh, and K. G. Shin. Large-scale malware indexing using function-call graphs. In Proc. of CCS, 2009.

Digital Library

[14]

IDA Pro. http://www.hex-rays.com/idapro.

[15]

R. Linger, S. Prowell, and K. Sayre. Computing the behavior of malicious code with function extraction technology. In Proc. of CSIIRW, 2009.

Digital Library

[16]

ROSE. http://rosecompiler.org.

[17]

N. E. Rosenblum, B. P. Miller, and X. Zhu. Extracting compiler provenance from program binaries. In Proc. of PASTE, 2010.

Digital Library

[18]

A. Sæbjørnsen, J. Willcock, T. Panas, D. J. Quinlan, and Z. Su. Detecting code clones in binary executables. In Proc. of ISSTA, 2009.

Digital Library

[19]

Symantec. Symantec internet security threat report: Trends for January 06--June 06, 2006. http://www.symantec.com/enterprise/threatreport/index.jsp.

[20]

A. Walenstein and A. Lakhotia. The Software Similarity Problem in Malware Analysis. In Duplication, Redundancy, and Similarity in Software, volume 06301 of Dagstuhl Seminar Proceedings, 2007.

[21]

A. Walenstein, M. Venable, M. Hayes, C. Thompson, and A. Lakhotia. Exploiting Similarity Between Variants to Defeat Malware: "Vilo" Method for Comparing and Searching Binary Programs. In Proc. of BLACKHAT DC, 2007.

[22]

WEKA website. http://www.cs.waikato.ac.nz/ml/weka.

[23]

Y. Ye, T. Li, Y. Chen, and Q. Jiang. Automatic malware categorization using cluster ensemble. In Proc. of KDD, 2010.

Digital Library

Cited By

Ismail MLin YHan DGao D(2023)BinAlign: Alignment Padding Based Compiler Provenance RecoveryInformation Security and Privacy10.1007/978-3-031-35486-1_26(609-629)Online publication date: 15-Jun-2023
https://doi.org/10.1007/978-3-031-35486-1_26
Alrabaee SDebbabi MWang L(2022)A Survey of Binary Code Fingerprinting Approaches: Taxonomy, Methodologies, and FeaturesACM Computing Surveys10.1145/348686055:1(1-41)Online publication date: 17-Jan-2022
https://dl.acm.org/doi/10.1145/3486860
Alrabaee SDebbabi MShirani PWang LYoussef ARahimian ANouh LMouheb DHuang HHanna AAlrabaee SDebbabi MShirani PWang LYoussef ARahimian ANouh LMouheb DHuang HHanna A(2020)Binary Analysis OverviewBinary Code Fingerprinting for Cybersecurity10.1007/978-3-030-34238-8_2(7-44)Online publication date: 1-Mar-2020
https://doi.org/10.1007/978-3-030-34238-8_2
Show More Cited By

Index Terms

Supervised learning for provenance-similarity of binaries
1. Software and its engineering
  1. Software creation and management
    1. Software post-development issues
      1. Software reverse engineering

Recommendations

On Binary Similarity Measures for Handwritten Character Recognition
ICDAR '05: Proceedings of the Eighth International Conference on Document Analysis and Recognition

Similarity and dissimilarity measures play an important role in pattern classification and clustering. For a century, researchers have searched for a good measure. Here, we review, categorize, and evaluate various binary vector similarity/dissimilarity ...
A Comparative Study of Supervised Learning Algorithms for Re-opened Bug Prediction
CSMR '13: Proceedings of the 2013 17th European Conference on Software Maintenance and Reengineering

Bug fixing is a time-consuming and costly job which is performed in the whole life cycle of software development and maintenance. For many systems, bugs are managed in bug management systems such as Bugzilla. Generally, the status of a typical bug report ...
Similarity of binaries through re-optimization
PLDI 2017: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation

We present a scalable approach for establishing similarity between stripped binaries (with no debug information). The main challenge in binary similarity, is to establish similarity even when the code has been compiled using different compilers, with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2011

1446 pages

ISBN:9781450308137

DOI:10.1145/2020408

General Chair:
Chid Apte
IBM Research
,
Program Chairs:
Joydeep Ghosh
UT Austin
,
Padhraic Smyth
UC Irvine

Copyright © 2011 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 ACM 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: 21 August 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

KDD '11

Sponsor:

KDD '11: The 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 21 - 24, 2011

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
744
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ismail MLin YHan DGao D(2023)BinAlign: Alignment Padding Based Compiler Provenance RecoveryInformation Security and Privacy10.1007/978-3-031-35486-1_26(609-629)Online publication date: 15-Jun-2023
https://doi.org/10.1007/978-3-031-35486-1_26
Alrabaee SDebbabi MWang L(2022)A Survey of Binary Code Fingerprinting Approaches: Taxonomy, Methodologies, and FeaturesACM Computing Surveys10.1145/348686055:1(1-41)Online publication date: 17-Jan-2022
https://dl.acm.org/doi/10.1145/3486860
Alrabaee SDebbabi MShirani PWang LYoussef ARahimian ANouh LMouheb DHuang HHanna AAlrabaee SDebbabi MShirani PWang LYoussef ARahimian ANouh LMouheb DHuang HHanna A(2020)Binary Analysis OverviewBinary Code Fingerprinting for Cybersecurity10.1007/978-3-030-34238-8_2(7-44)Online publication date: 1-Mar-2020
https://doi.org/10.1007/978-3-030-34238-8_2
Nazir SShahzad SMukhtar N(2019)Software Birthmark Design and Estimation: A Systematic Literature ReviewArabian Journal for Science and Engineering10.1007/s13369-019-03718-944:4(3905-3927)Online publication date: 16-Jan-2019
https://doi.org/10.1007/s13369-019-03718-9
Pagani FDell'Amico MBalzarotti DZhao ZAhn GKrishnan RGhinita G(2018)Beyond Precision and RecallProceedings of the Eighth ACM Conference on Data and Application Security and Privacy10.1145/3176258.3176306(354-365)Online publication date: 13-Mar-2018
https://dl.acm.org/doi/10.1145/3176258.3176306
Tian ZLiu TZheng QZhuang EFan MYang Z(2018)Reviving Sequential Program Birthmarking for Multithreaded Software Plagiarism DetectionIEEE Transactions on Software Engineering10.1109/TSE.2017.268838344:5(491-511)Online publication date: 1-May-2018
https://doi.org/10.1109/TSE.2017.2688383
Oikonomopoulos AVermeulen RGiuffrida CBos H(2018)On the Effectiveness of Code Normalization for Function Identification2018 IEEE 23rd Pacific Rim International Symposium on Dependable Computing (PRDC)10.1109/PRDC.2018.00045(241-251)Online publication date: Dec-2018
https://doi.org/10.1109/PRDC.2018.00045
Lakhotia ANotani VLeDoux C(2018)Malware Economics and its Implication to Anti-Malware Situational Awareness2018 International Conference On Cyber Situational Awareness, Data Analytics And Assessment (Cyber SA)10.1109/CyberSA.2018.8551388(1-8)Online publication date: Jun-2018
https://doi.org/10.1109/CyberSA.2018.8551388
Nouh LRahimian AMouheb DDebbabi MHanna A(2017)BinSign: Fingerprinting Binary Functions to Support Automated Analysis of Code ExecutablesICT Systems Security and Privacy Protection10.1007/978-3-319-58469-0_23(341-355)Online publication date: 4-May-2017
https://doi.org/10.1007/978-3-319-58469-0_23
Tian ZZheng QLiu TFan MZhuang EYang Z(2015)Software Plagiarism Detection with Birthmarks Based on Dynamic Key Instruction SequencesIEEE Transactions on Software Engineering10.1109/TSE.2015.245450841:12(1217-1235)Online publication date: 1-Dec-2015
https://doi.org/10.1109/TSE.2015.2454508
Show More Cited By

View Options

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