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

research-article

Patch based vulnerability matching for binary programs

Authors:

Ting LiuAuthors Info & Claims

ISSTA 2020: Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis

Pages 376 - 387

https://doi.org/10.1145/3395363.3397361

Published: 18 July 2020 Publication History

Abstract

The binary-level function matching has been widely used to detect whether there are 1-day vulnerabilities in released programs. However, the high false positive is a challenge for current function matching solutions, since the vulnerable function is highly similar to its corresponding patched version. In this paper, the Binary X-Ray (BinXray), a patch based vulnerability matching approach, is proposed to identify the specific 1-day vulnerabilities in target programs accurately and effectively. In the preparing step, a basic block mapping algorithm is designed to extract the signature of a patch, by comparing the given vulnerable and patched programs. The signature is represented as a set of basic block traces. In the detection step, the patching semantics is applied to reduce irrelevant basic block traces to speed up the signature searching. The trace similarity is also designed to identify whether a target program is patched. In experiments, 12 real software projects related to 479 CVEs are collected. BinXray achieves 93.31% accuracy and the analysis time cost is only 296.17ms per function, outperforming the state-of-the-art works.

References

[1]

2014. CVE-2014-0160. https://cve.mitre.org/cgi-bin/cvename.cgi?name= cve2014-0160.

[2]

2015. CVE-2015-1791. https://cve.mitre.org/cgi-bin/cvename.cgi?name= cve2015-1791.

[3]

2020. CVE Details. https://www.cvedetails.com/.

[4]

2020. CVE List. https://cve.mitre.org/index.html.

[5]

2020. Diaphora. https://github.com/joxeankoret/diaphora.

[6]

2020. IDA Pro. https://www.hex-rays.com/products/ida/.

[7]

2020. NVD. https://nvd.nist.gov/.

[8]

2020. Open Source Data and Results for the Paper. https://sites.google.com/view/ submission-for-issta-2020.

[9]

2020. OpenSSL Vulnerabilities. https://www.openssl.org/news/vulnerabilities. html.

[10]

Martial Bourquin, Andy King, and Edward Robbins. 2013. Binslayer: accurate comparison of binary executables. In Proceedings of the 2nd ACM SIGPLAN Program Protection and Reverse Engineering Workshop. ACM, 4.

Digital Library

[11]

Mahinthan Chandramohan, Yinxing Xue, Zhengzi Xu, Yang Liu, Chia Yuan Cho, and Hee Beng Kuan Tan. 2016. BinGo: Cross-architecture cross-os binary search. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, 678-689.

Digital Library

[12]

Christopher S Corley, Nicholas A Kraft, Letha H Etzkorn, and Stacy K Lukins. 2011. Recovering traceability links between source code and fixed bugs via patch analysis. In Proceedings of the 6th International Workshop on Traceability in Emerging Forms of Software Engineering. ACM, 31-37.

Digital Library

[13]

Yaniv David, Nimrod Partush, and Eran Yahav. 2016. Statistical similarity of binaries. ACM SIGPLAN Notices 51, 6 ( 2016 ), 266-280.

[14]

Yaniv David, Nimrod Partush, and Eran Yahav. 2018. Firmup: Precise static detection of common vulnerabilities in firmware. In ACM SIGPLAN Notices, Vol. 53. ACM, 392-404.

Digital Library

[15]

Yaniv David and Eran Yahav. 2014. Tracelet-based code search in executables. Acm Sigplan Notices 49, 6 ( 2014 ), 349-360.

[16]

Ruian Duan, Ashish Bijlani, Meng Xu, Taesoo Kim, and Wenke Lee. 2017. Identifying open-source license violation and 1-day security risk at large scale. In Proceedings of the 2017 ACM SIGSAC Conference on computer and communications security. ACM, 2169-2185.

Digital Library

[17]

Manuel Egele, Maverick Woo, Peter Chapman, and David Brumley. 2014. Blanket execution: Dynamic similarity testing for program binaries and components. USENIX.

[18]

Sebastian Eschweiler, Khaled Yakdan, and Elmar Gerhards-Padilla. 2016. discovRE: Eficient Cross-Architecture Identification of Bugs in Binary Code. In NDSS.

[19]

Mohammad Reza Farhadi, Benjamin C. M. Fung, Philippe Charland, and Mourad Debbabi. 2014. BinClone: Detecting Code Clones in Malware. In Proceedings of the 8th International Conference on Software Security and Reliability. 78-87.

Digital Library

[20]

Qian Feng, Rundong Zhou, Chengcheng Xu, Yao Cheng, Brian Testa, and Heng Yin. 2016. Scalable graph-based bug search for firmware images. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 480-491.

Digital Library

[21]

Halvar Flake. 2004. Structural comparison of executable objects. In Proc. of the International GI Workshop on Detection of Intrusions and Malware & Vulnerability Assessment, number P-46 in Lecture Notes in Informatics. Citeseer, 161-174.

[22]

Debin Gao, Michael K Reiter, and Dawn Song. 2008. Binhunt: Automatically ifnding semantic diferences in binary programs. In International Conference on Information and Communications Security. Springer, 238-255.

Digital Library

[23]

Yikun Hu, Yuanyuan Zhang, Juanru Li, and Dawu Gu. 2017. Binary code clone detection across architectures and compiling configurations. In Proceedings of the 25th International Conference on Program Comprehension. IEEE Press, 88-98.

Digital Library

[24]

Yikun Hu, Yuanyuan Zhang, Juanru Li, Hui Wang, Bodong Li, and Dawu Gu. 2018. BinMatch: A Semantics-based Hybrid Approach on Binary Code Clone Analysis. In 2018 IEEE International Conference on Software Maintenance and Evolution (ICSME). IEEE, 104-114.

[25]

Jiyong Jang, David Brumley, and Shobha Venkataraman. 2011. BitShred: feature hashing malware for scalable triage and semantic analysis. In Proceedings of the 18th ACM Conference on Computer and Communications Security. 309-320.

Digital Library

[26]

Lingxiao Jiang and Zhendong Su. 2009. Automatic mining of functionally equivalent code fragments via random testing. In Proceedings of the eighteenth international symposium on Software testing and analysis. ACM, 81-92.

Digital Library

[27]

Miryung Kim and David Notkin. 2009. Discovering and representing systematic code changes. In 2009 IEEE 31st International Conference on Software Engineering. IEEE, 309-319.

Digital Library

[28]

Seulbae Kim, Seunghoon Woo, Heejo Lee, and Hakjoo Oh. 2017. VUDDY: a scalable approach for vulnerable code clone discovery. In Security and Privacy (SP), 2017 IEEE Symposium on. IEEE, 595-614.

[29]

Frank Li and Vern Paxson. 2017. A large-scale empirical study of security patches. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2201-2215.

Digital Library

[30]

Hong Lin, Dongdong Zhao, Linjun Ran, Mushuai Han, Jing Tian, Jianwen Xiang, Xian Ma, and Yingshou Zhong. 2017. CVSSA: Cross-Architecture Vulnerability Search in Firmware Based on Support Vector Machine and Attributed Control Flow Graph. In Dependable Systems and Their Applications (DSA), 2017 International Conference on. IEEE, 35-41.

[31]

Bingchang Liu, Wei Huo, Chao Zhang, Wenchao Li, Feng Li, Aihua Piao, and Wei Zou. 2018. Dif: cross-version binary code similarity detection with DNN. In Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering. ACM, 667-678.

Digital Library

[32]

Danjun Liu, Yao Li, Yong Tang, Baosheng Wang, and Wei Xie. 2018. VMPBL: Identifying Vulnerable Functions Based on Machine Learning Combining Patched Information and Binary Comparison Technique by LCS. In 2018 17th IEEE International Conference On Trust, Security And Privacy In Computing And Communications/12th IEEE International Conference On Big Data Science And Engineering (TrustCom/BigDataSE). IEEE, 800-807.

[33]

Lannan Luo, Jiang Ming, Dinghao Wu, Peng Liu, and Sencun Zhu. 2014. Semantics-based obfuscation-resilient binary code similarity comparison with applications to software plagiarism detection. In Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, 389-400.

Digital Library

[34]

Xiaozhu Meng and Barton P Miller. 2016. Binary code is not easy. In Proceedings of the 25th International Symposium on Software Testing and Analysis. ACM, 24-35.

Digital Library

[35]

Jiang Ming, Meng Pan, and Debin Gao. 2012. iBinHunt: Binary hunting with inter-procedural control flow. In International Conference on Information Security and Cryptology. Springer, 92-109.

[36]

Jiang Ming, Dongpeng Xu, Yufei Jiang, and Dinghao Wu. 2017. BinSim: Tracebased semantic binary difing via system call sliced segment equivalence checking. In Proceedings of the 26th USENIX Security Symposium.

[37]

Hoan Anh Nguyen, Anh Tuan Nguyen, Tung Thanh Nguyen, Tien N Nguyen, and Hridesh Rajan. 2013. A study of repetitiveness of code changes in software evolution. In Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering. IEEE Press, 180-190.

Digital Library

[38]

Jannik Pewny, Behrad Garmany, Robert Gawlik, Christian Rossow, and Thorsten Holz. 2015. Cross-architecture bug search in binary executables. In Security and Privacy (SP), 2015 IEEE Symposium on. IEEE, 709-724.

Digital Library

[39]

Jannik Pewny, Felix Schuster, Lukas Bernhard, Thorsten Holz, and Christian Rossow. 2014. Leveraging semantic signatures for bug search in binary programs. In Proceedings of the 30th Annual Computer Security Applications Conference. ACM, 406-415.

Digital Library

[40]

Andreas Saebjørnsen, Jeremiah Willcock, Thomas Panas, Daniel Quinlan, and Zhendong Su. 2009. Detecting code clones in binary executables. In Proceedings of the eighteenth international symposium on Software testing and analysis. ACM, 117-128.

Digital Library

[41]

Mauricio Soto, Ferdian Thung, Chu-Pan Wong, Claire Le Goues, and David Lo. 2016. A deeper look into bug fixes: patterns, replacements, deletions, and additions. In Proceedings of the 13th International Conference on Mining Software Repositories. ACM, 512-515.

Digital Library

[42]

Yuan Tian, Julia Lawall, and David Lo. 2012. Identifying linux bug fixing patches. In Proceedings of the 34th International Conference on Software Engineering. IEEE Press, 386-396.

Digital Library

[43]

Zhenzhou Tian, Ting Liu, Qinghua Zheng, Eryue Zhuang, Ming Fan, and Zijiang Yang. 2017. Reviving sequential program birthmarking for multithreaded software plagiarism detection. IEEE Transactions on Software Engineering 44, 5 ( 2017 ), 491-511.

[44]

Haijun Wang, Xiaofei Xie, Shang-Wei Lin, Yun Lin, Yuekang Li, Shengchao Qin, Yang Liu, and Ting Liu. 2019. Locating vulnerabilities in binaries via memory layout recovering. In Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 718-728.

Digital Library

[45]

Cheng Wen, Haijun Wang, Yuekang Li, Shengchao Qin, Yang Liu, Zhiwu Xu, Hongxu Chen, Xiaofei Xie, Geguang Pu, and Ting Liu. 2020. Memlock: Memory usage guided fuzzing. In Proceedings of the 42nd International Conference on Software Engineering. IEEE.

Digital Library

[46]

Xiaojun Xu, Chang Liu, Qian Feng, Heng Yin, Le Song, and Dawn Song. 2017. Neural network-based graph embedding for cross-platform binary code similarity detection. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, 363-376.

Digital Library

[47]

Zhengzi Xu, Bihuan Chen, Mahinthan Chandramohan, Yang Liu, and Fu Song. 2017. SPAIN: security patch analysis for binaries towards understanding the pain and pills. In Proceedings of the 39th International Conference on Software Engineering. IEEE Press, 462-472.

Digital Library

[48]

Yinxing Xue, Zhengzi Xu, Mahinthan Chandramohan, and Yang Liu. 2018. Accurate and Scalable Cross-Architecture Cross-OS Binary Code Search with Emulation. IEEE Transactions on Software Engineering ( 2018 ).

[49]

Hang Zhang and Zhiyun Qian. 2018. Precise and accurate patch presence test for binaries. In 27th {USENIX} Security Symposium ({USENIX} Security 18). 887-902.

[50]

Hao Zhong and Zhendong Su. 2015. An empirical study on real bug fixes. In Proceedings of the 37th International Conference on Software Engineering-Volume 1. IEEE Press, 913-923.

Digital Library

Cited By

Bennouk KAit Aali NEl Bouzekri El Idrissi YSebai BFaroukhi AMahouachi D(2024)A Comprehensive Review and Assessment of Cybersecurity Vulnerability Detection MethodologiesJournal of Cybersecurity and Privacy10.3390/jcp40400404:4(853-908)Online publication date: 7-Oct-2024
https://doi.org/10.3390/jcp4040040
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
Lin RFu YYi WYang JCao JDong ZXie FLi H(2024)Vulnerabilities and Security Patches Detection in OSS: A SurveyACM Computing Surveys10.1145/369478257:1(1-37)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3694782
Show More Cited By

Index Terms

Patch based vulnerability matching for binary programs
1. Security and privacy
  1. Software and application security
    1. Software reverse engineering
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program analysis

Recommendations

Towards Practical Binary Code Similarity Detection: Vulnerability Verification via Patch Semantic Analysis
Vulnerability is a major threat to software security. It has been proven that binary code similarity detection approaches are efficient to search for recurring vulnerabilities introduced by code sharing in binary software. However, these approaches suffer ...
Function matching-based binary-level software similarity calculation
RACS '13: Proceedings of the 2013 Research in Adaptive and Convergent Systems

This paper proposes a method to calculate similarities of software without any source code information. The proposed method can be used for various applications such as detecting the source code theft and copyright infringement, as well as locating ...
Vulnerability of CNNs against Multi-Patch Attacks
SaT-CPS '23: Proceedings of the 2023 ACM Workshop on Secure and Trustworthy Cyber-Physical Systems

Convolutional Neural Networks have become an integral part of anomaly detection in Cyber-Physical Systems (CPS). Although highly accurate, the advent of adversarial patches exposed the vulnerability of CNNs, posing a security concern for safety-critical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA 2020: Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis

July 2020

591 pages

ISBN:9781450380089

DOI:10.1145/3395363

General Chair:
Sarfraz Khurshid
University of Texas at Austin, USA
,
Program Chair:
Corina S. Păsăreanu
Carnegie Mellon University Silicon Valley / NASA Ames Research Center, USA

Copyright © 2020 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

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 July 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSTA '20

Sponsor:

SIGSOFT

ISSTA '20: 29th ACM SIGSOFT International Symposium on Software Testing and Analysis

July 18 - 22, 2020

Virtual Event, USA

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
1,033
Total Downloads

Downloads (Last 12 months)260
Downloads (Last 6 weeks)23

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bennouk KAit Aali NEl Bouzekri El Idrissi YSebai BFaroukhi AMahouachi D(2024)A Comprehensive Review and Assessment of Cybersecurity Vulnerability Detection MethodologiesJournal of Cybersecurity and Privacy10.3390/jcp40400404:4(853-908)Online publication date: 7-Oct-2024
https://doi.org/10.3390/jcp4040040
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
Lin RFu YYi WYang JCao JDong ZXie FLi H(2024)Vulnerabilities and Security Patches Detection in OSS: A SurveyACM Computing Surveys10.1145/369478257:1(1-37)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3694782
Xie ZWen MWei ZJin HFilkov VRay BZhou M(2024)Unveiling the Characteristics and Impact of Security Patch EvolutionProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695488(1094-1106)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695488
Zhan QHu XXia XLi SFilkov VRay BZhou M(2024)REACT: IR-Level Patch Presence Test for BinaryProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695012(381-392)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695012
Xiao HZhang YShen MLin CZhang CLiu SYang MLuo BLiao XXu JKirda ELie D(2024)Accurate and Efficient Recurring Vulnerability Detection for IoT FirmwareProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670275(3317-3331)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670275
Gong YNie JYou WShi WHuang JLiang BZhang JBaysal OLinares-Vasquez MMoran KSteinmacher I(2024)SICode: Embedding-Based Subgraph Isomorphism Identification for Bug DetectionProceedings of the 32nd IEEE/ACM International Conference on Program Comprehension10.1145/3643916.3646556(304-315)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1145/3643916.3646556
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
Zhan QHu XLi ZXia XLo DLi SRoychoudhury APaiva AAbreu RStorey M(2024)PS3: Precise Patch Presence Test based on Semantic Symbolic SignatureProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639134(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639134
Jia AFan MXu XJin WWang HLiu TRoychoudhury APaiva AAbreu RStorey M(2024)Cross-Inlining Binary Function Similarity DetectionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639080(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639080
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