Semantics-Based Obfuscation-Resilient Binary Code Similarity Comparison with Applications to Software and Algorithm Plagiarism Detection
The DOI matches its Crossref record; 69 of the 69 references it cites were found in a registry or an index.
Abstract
Existing code similarity comparison methods, whether source or binary code based, are mostly not resilient to obfuscations. Identifying similar or identical code fragments among programs is very important in some applications. For example, one application is to detect illegal code reuse. In the code theft cases, emerging obfuscation techniques have made automated detection increasingly difficult. Another application is to identify cryptographic algorithms which are widely employed by modern malware to circumvent detection, hide network communications, and protect payloads among other purposes. Due to diverse coding styles and high programming flexibility, different implementation of the same algorithm may appear very distinct, causing automatic detection to be very hard, let alone code obfuscations are sometimes applied. In this paper, we propose a binary-oriented, obfuscation-resilient binary code similarity comparison method based on a new concept, longest common subsequence of semantically equivalent basic blocks , which combines rigorous program semantics with longest common subsequence based fuzzy matching. We model the semantics of a basic block by a set of symbolic formulas representing the input-output relations of the block. This way, the semantic equivalence (and similarity) of two blocks can be checked by a theorem prover. We then model the semantic similarity of two paths using the longest common subsequence with basic blocks as elements. This novel combination has resulted in strong resiliency to code obfuscation. We have developed a prototype. The experimental results show that our method can be applied to software plagiarism and algorithm detection, and is effective and practical to analyze real-world software.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Cop identifies similar components between two programs by analysing semantics (behaviour) through symbolic execution.”
From Academic Source Code Plagiarism Detection by Measuring Program Behavioral Similarity (2021) · cites this paper as [35]
Citations
Cites
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
Grossman, P. (2009) · Discrete Mathematics for Computing · doi:10.1007/978-0-230-37405-8_1 · Cited by 8,834
KLEE: unassisted and automatic generation of high-coverage tests for complex systems programs
Cadar, C., Dunbar, D., & Engler, D. (2008) · doi:10.5555/1855741.1855756 · Cited by 2,620
DART: directed automated random testing
Godefroid, P., Klarlund, N., & Sen, K. (2005) · ACM SIGPLAN Notices · doi:10.1145/1064978.1065036 · Cited by 2,067
CCFinder: a multilinguistic token-based code clone detection system for large scale source code
Kamiya, T., Kusumoto, S., & Inoue, K. (2002) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2002.1019480 · Cited by 1,711
DART: directed automated random testing
Godefroid, P., Klarlund, N., & Sen, K. (2005) · Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation · doi:10.1145/1065010.1065036 · Cited by 1,570
Kleinberg, J. M., & Eva Tardos, D. (2005) · Cited by 1,400
Schleimer, S., S, W. D., & Aiken, A. (2003) · Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data · doi:10.1145/872757.872770 · Cited by 1,099 · cited 1×
“Moss is a system for determining the similarity of programs based on the winnowing algorithm [63] for document fingerprinting.”
MethodAutomated Whitebox Fuzz Testing.
Godefroid, P., Levin, M. Y., & Molnar, D. A. (2008) · Cited by 1,095
A Taxonomy of Obfuscating Transformations
Collberg, C. S., Thomborson, C. D., & Low, D. (1997) · ResearchSpace (University of Auckland) · Cited by 1,090
CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs
Necula, G. C., McPeak, S., Rahul, S. P., & Weimer, W. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45937-5_16 · Cited by 977
The art of computer virus research and defense
(2005) · Choice Reviews Online · doi:10.5860/choice.43-1613 · Cited by 836
EXE: automatically generating inputs of death
Cadar, C., Ganesh, V., Pawlowski, P. M., Dill, D. L., & Engler, D. R. (2006) · Proceedings of the 13th ACM conference on Computer and communications security · doi:10.1145/1180405.1180445 · Cited by 788
Toward Automated Dynamic Malware Analysis Using CWSandbox
Willems, C., Holz, T., & Freiling, F. (2007) · IEEE Security and Privacy Magazine · doi:10.1109/msp.2007.45 · Cited by 739
On finding duplication and near-duplication in large software systems
Baker, B. S. (2002) · Proceedings of 2nd Working Conference on Reverse Engineering · doi:10.1109/wcre.1995.514697 · Cited by 717
Obfuscation of executable code to improve resistance to static disassembly
Linn, C., & Debray, S. (2003) · Proceedings of the 10th ACM conference on Computer and communications security · doi:10.1145/948109.948149 · Cited by 602
Detecting repackaged smartphone applications in third-party android marketplaces
Zhou, W., Zhou, Y., Jiang, X., & Ning, P. (2012) · Proceedings of the second ACM conference on Data and Application Security and Privacy · doi:10.1145/2133601.2133640 · Cited by 590
A Decision Procedure for Bit-Vectors and Arrays
Ganesh, V., & Dill, D. L. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-73368-3_52 · Cited by 585
Manufacturing cheap, resilient, and stealthy opaque constructs
Collberg, C., Thomborson, C., & Low, D. (1998) · Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '98 · doi:10.1145/268946.268962 · Cited by 535
GPLAG: detection of software plagiarism by program dependence graph analysis
Liu, C., Chen, C., Han, J., & Yu, P. S. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150522 · Cited by 422
Identifying syntactic differences between two programs
Yang, W. (1991) · Software: Practice and Experience · doi:10.1002/spe.4380210706 · Cited by 346
Scalable detection of semantic clones
Gabel, M., Jiang, L., & Su, Z. (2008) · Proceedings of the 13th international conference on Software engineering - ICSE '08 · doi:10.1145/1368088.1368132 · Cited by 328
Structured testing: a testing methodology using the cyclomatic complexity metric
Wallace, D. R., Watson, A. H., & McCabe, T. J. (1996) · doi:10.6028/nist.sp.500-235 · Cited by 312
Dynamic Analysis of Malicious Code
Bayer, U., Moser, A., Kruegel, C., & Kirda, E. (2006) · Journal in Computer Virology · doi:10.1007/s11416-006-0012-2 · Cited by 295
PolyUnpack: Automating the Hidden-Code Extraction of Unpack-Executing Malware
Royal, P., Halpin, M., Dagon, D., Edmonds, R., & Lee, W. (2006) · 2006 22nd Annual Computer Security Applications Conference (ACSAC'06) · doi:10.1109/acsac.2006.38 · Cited by 293
Achieving accuracy and scalability simultaneously in detecting application clones on Android markets
Chen, K., Liu, P., & Zhang, Y. (2014) · Proceedings of the 36th International Conference on Software Engineering · doi:10.1145/2568225.2568286 · Cited by 287
Self-citationWYSINWYX: What you see is not what you eXecute
Balakrishnan, G., & Reps, T. (2010) · ACM Transactions on Programming Languages and Systems · doi:10.1145/1749608.1749612 · Cited by 286
Impeding Malware Analysis Using Conditional Code Obfuscation
Sharif, M. I., Lanzi, A., Giffin, J. T., & Lee, W. (2008) · Network and Distributed System Security Symposium · Cited by 284
Renovo: a hidden code extractor for packed executables
Kang, M. G., Poosankam, P., & Yin, H. (2007) · Proceedings of the 2007 ACM workshop on Recurring malcode · doi:10.1145/1314389.1314399 · Cited by 272
Attack of the Clones: Detecting Cloned Applications on Android Markets
Crussell, J., Gibler, C., & Chen, H. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-33167-1_3 · Cited by 270
BinHunt: Automatically Finding Semantic Differences in Binary Programs
Gao, D., Reiter, M. K., & Song, D. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88625-9_16 · Cited by 255
Execution Generated Test Cases: How to Make Systems Code Crash Itself
Cadar, C., & Engler, D. (2005) · Lecture Notes in Computer Science · doi:10.1007/11537328_2 · Cited by 254
Fast, scalable detection of "Piggybacked" mobile applications
Zhou, W., Zhou, Y., Grace, M., Jiang, X., & Zou, S. (2013) · Proceedings of the third ACM conference on Data and application security and privacy · doi:10.1145/2435349.2435377 · Cited by 229
Juxtapp: A Scalable System for Detecting Code Reuse among Android Applications
Hanna, S., Huang, L., Wu, E., Li, S., Chen, C., & Song, D. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-37300-8_4 · Cited by 221
Obfuscation of executable code to improve resistance to static disassembly
Linn, C., & Debray, S. (2003) · Proceedings of the 10th ACM conference on Computer and communication security - CCS '03 · doi:10.1145/948148.948149 · Cited by 221
Luo, L., Ming, J., Wu, D., Liu, P., & Zhu, S. (2014) · Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering · doi:10.1145/2635868.2635900 · Cited by 220
Self-citationDispatcher: enabling active botnet infiltration using automatic protocol reverse-engineering
Caballero, J., Poosankam, P., Kreibich, C., & Song, D. (2009) · Proceedings of the 16th ACM conference on Computer and communications security · doi:10.1145/1653662.1653737 · Cited by 213
OmniUnpack: Fast, Generic, and Safe Unpacking of Malware
Martignoni, L., Christodorescu, M., & Jha, S. (2007) · Twenty-Third Annual Computer Security Applications Conference (ACSAC 2007) · doi:10.1109/acsac.2007.15 · Cited by 208
Lagarias, J. C. (2010) · American Mathematical Society eBooks · doi:10.1090/mbk/078 · Cited by 203
SYMDIFF: A Language-Agnostic Semantic Diff Tool for Imperative Programs
Lahiri, S. K., Hawblitzel, C., Kawaguchi, M., & Rebêlo, H. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-31424-7_54 · Cited by 197
K-gram based software birthmarks
Myles, G., & Collberg, C. (2005) · Proceedings of the 2005 ACM symposium on Applied computing · doi:10.1145/1066677.1066753 · Cited by 187
Structural Comparison of Executable Objects
Flake, H. (2004) · Technische Universität Dortmund Eldorado (Technische Universität Dortmund) · doi:10.17877/de290r-2007 · Cited by 182
ViewDroid: towards obfuscation-resilient mobile application repackaging detection
Zhang, F., Huang, H., Zhu, S., Wu, D., & Liu, P. (2014) · Proceedings of the 2014 ACM conference on Security and privacy in wireless & mobile networks · doi:10.1145/2627393.2627395 · Cited by 167
Self-citationDetecting Software Theft via Whole Program Path Birthmarks
Myles, G., & Collberg, C. S. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30144-8_34 · Cited by 144
JPlag: finding plagiarisms among a set of programs
Prechelt, L., Malpohl, G., & Philippsen, M. (2000) · Karlsruhe · doi:10.5445/ir/542000 · Cited by 144 · cited 4×
“We compared the detection results of CoP with those of four state-of-the-art plagiarism detection systems including MOSS [28], JPLag [61], DarunGrim2 [24] and Bdiff [9].”
MethodResultInfluentialMOSS : A system for detecting software plagiarism
Aiken, A. (2004) · Medical Entomology and Zoology · Cited by 141
ReFormat: Automatic Reverse Engineering of Encrypted Messages
Wang, Z., Jiang, X., Cui, W., Wang, X., & Grace, M. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-04444-1_13 · Cited by 139
iBinHunt: Binary Hunting with Inter-procedural Control Flow
Ming, J., Pan, M., & Gao, D. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-37682-5_8 · Cited by 133
Self-citationDesign and evaluation of birthmarks for detecting theft of Java programs
Tamada, H., Nakamura, M., & Monden, A. (2004) · Cited by 129
Automated Identification of Cryptographic Primitives in Binary Programs
Gröbert, F., Willems, C., & Holz, T. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-23644-0_3 · Cited by 116
Binary obfuscation using signals
Попов, И. В., Debray, S., & Andrews, G. R. (2007) · Cited by 114
Schuler, D., Dallmeier, V., & Lindig, C. (2007) · Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering · doi:10.1145/1321631.1321672 · Cited by 108
Dynamic Software Birthmarks to Detect the Theft of Windows Applications
Tamada, H., Okamoto, K., Nakamura, M., Monden, A., & Matsumoto, K. (2004) · Cited by 107
The Ultimate Challenge: The 3x+1 Problem
Lagarias, J. C. (2011) · Medical Entomology and Zoology · Cited by 103
Behavior based software theft detection
Wang, X., Jhi, Y.-C., Zhu, S., & Liu, P. (2009) · Proceedings of the 16th ACM conference on Computer and communications security · doi:10.1145/1653662.1653696 · Cited by 101 · cited 3×
“[72] introduced two system call based birthmarks, which are suitable for programs invoking many different system calls.”
BackgroundInfluentialSelf-citationA Framework for Evaluating Mobile App Repackaging Detection Algorithms
Huang, H., Zhu, S., Liu, P., & Wu, D. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38908-5_13 · Cited by 89
Self-citationValue-based program characterization and its application to software plagiarism detection
Jhi, Y.-C., Wang, X., Jia, X., Zhu, S., Liu, P., & Wu, D. (2011) · Proceedings of the 33rd International Conference on Software Engineering · doi:10.1145/1985793.1985899 · Cited by 83
Self-citationCalvet, J., Fernandez, J. M., & Marion, J.-Y. (2012) · Proceedings of the ACM Conference on Computer and Communications Security · doi:10.1145/2382196.2382217 · Cited by 74
A first step towards algorithm plagiarism detection
Zhang, F., Jhi, Y.-C., Wu, D., Liu, P., & Zhu, S. (2012) · Proceedings of the 2012 International Symposium on Software Testing and Analysis · doi:10.1145/2338965.2336767 · Cited by 63
Self-citationProgram Logic Based Software Plagiarism Detection
Zhang, F., Wu, D., Liu, P., & Zhu, S. (2014) · 2014 IEEE 25th International Symposium on Software Reliability Engineering · doi:10.1109/issre.2014.18 · Cited by 57 · cited 1×
“[55], [79] presented a program logic based approach which searches for dissimilarity between two programs by finding path deviations.”
BackgroundSelf-citationSemantics-aware trace analysis
Hoffman, K. J., Eugster, P., & Jagannathan, S. (2009) · Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1542476.1542527 · Cited by 45
LOCO: an interactive code (De)obfuscation tool
Madou, M., Van Put, L., & De Bosschere, K. (2006) · Proceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation · doi:10.1145/1111542.1111566 · Cited by 43
Program Characterization Using Runtime Values and Its Application to Software Plagiarism Detection
Jhi, Y.-C., Jia, X., Wang, X., Zhu, S., Liu, P., & Wu, D. (2015) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2015.2418777 · Cited by 35 · cited 1×
“[39], [40] proposed a corevalue based birthmark for detecting plagiarism.”
BackgroundSelf-citationRepackage-Proofing Android Apps
Luo, L., Fu, Y., Wu, D., Zhu, S., & Liu, P. (2016) · International Conference on Dependable Systems & Networks/Proceedings · doi:10.1109/dsn.2016.56 · Cited by 34
Self-citationMing, J., Zhang, F., Wu, D., Liu, P., & Zhu, S. (2016) · IEEE Transactions on Reliability · doi:10.1109/tr.2016.2570554 · Cited by 33 · cited 1×
“[55], [79] presented a program logic based approach which searches for dissimilarity between two programs by finding path deviations.”
BackgroundSelf-citationMcCabe, T. J. (1982) · doi:10.6028/nbs.sp.500-99 · Cited by 30
The Superdiversifier: Peephole Individualization for Software Protection
Jacob, M., Jakubowski, M. H., Naldurg, P., Saw, C. W., & Venkatesan, R. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-89598-5_7 · Cited by 29
Replacement Attacks on Behavior Based Software Birthmark
Xin, Z., Chen, H., Wang, X., Liu, P., Zhu, S., Mao, B., & Li, X. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-24861-0_1 · Cited by 12
Self-citationLoco: An Interactive Code (De)Obfuscation tool
Madou, M., Put, L. V., & Bosschere, K. D. (2005) · Ghent University Academic Bibliography (Ghent University) · Cited by 7
Research works printed but not linked: 4
- conway, 1972, Unpredictable iterations, Proc Number Theory Conf, 49
- crussell, 2013, Scalable semantics-based detection of similar Android applications, Proc 18th Eur Symp Res Comput Secur, 182
- desnos, 2011, Android: From reversing to decompilation, Black Hat Abu Dhabi United Arab Emirates
- lutz, 2008, Towards revealing attackers’ intent by automatically decrypting network traffic, Master’s thesis Institut für Technische Informatik und Kommunikationsnetze ETH Zürich Zürich Switzerland
Cited by
Neural Machine Translation Inspired Binary Code Similarity Comparison beyond Function Pairs
Zuo, F., Li, X., Young, P., Luo, L., Zeng, Q., & Zhang, Z. (2019) · Proceedings 2019 Network and Distributed System Security Symposium · doi:10.14722/ndss.2019.23492 · Cited by 175
Self-citationαDiff: cross-version binary code similarity detection with DNN
Liu, B., Huo, W., Zhang, C., Li, W., Li, F., Piao, A., & Zou, W. (2018) · Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering · doi:10.1145/3238147.3238199 · Cited by 192
jTrans: jump-aware transformer for binary code similarity detection
Wang, H., Qu, W., Katz, G., Zhu, W., Gao, Z., Qiu, H., Zhuge, J., & Zhang, C. (2022) · Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis · doi:10.1145/3533767.3534367 · Cited by 169
A Survey of Binary Code Similarity
Haq, I. U., & Caballero, J. (2021) · ACM Computing Surveys · doi:10.1145/3446371 · Cited by 244
Identifying Open-Source License Violation and 1-day Security Risk at Large Scale
Duan, R., Bijlani, A., Xu, M., Kim, T., & Lee, W. (2017) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3133956.3134048 · Cited by 174
Metadata
- Authors
- Luo, L., Ming, J., Wu, D., Liu, P., & Zhu, S.
- Affiliations
- Pennsylvania State University (US)
- The University of Texas at Arlington (US)
- Venue
- IEEE Transactions on Software Engineering
- Published
- 2017-12-01
- Volume
- 43
- Issue
- 12
- Pages
- 1157-1177
- ISSN
- 0098-5589 (ISSN-L)
- 1939-3520
- OpenAlex
- W2579698096
- Semantic Scholar
- d86129473ebc932af4cdcf143a196e60e24fad9b
- Cited by
- 144
- References
- 69
- Citations by year
- 2026: 12 · 2025: 25 · 2024: 19 · 2023: 19 · 2022: 17 · 2021: 15 · 2020: 12 · 2019: 13 · 2018: 8 · 2017: 4
- FWCI
- 18.84
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- Locations
- IEEE Transactions on Software Engineering (publishedVersion)
- Funders
- US National Science Foundation (CCF-1320605)
- Topics
- Physical Sciences › Computer Science › Information Systems › Software Engineering Research
- Physical Sciences › Computer Science › Hardware and Architecture › Security and Verification in Computing
- Physical Sciences › Computer Science › Hardware and Architecture › Physical Unclonable Functions (PUFs) and Hardware Security
- Keywords
- code obfuscation, obfuscation resilience, software plagiarism detection, longest common subsequence, approximate string matching, theorem proving
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.