Deviation-Based Obfuscation-Resilient Program Equivalence Checking With Application to Software Plagiarism Detection
The DOI matches its Crossref record; 71 of the 76 references it cites were found in a registry or an index.
Abstract
Software plagiarism, an act of illegally copying others' code, has become a serious concern for honest software companies and the open source community. Considerable research efforts have been dedicated to searching the evidence of software plagiarism. In this paper, we continue this line of research and propose LoPD, a deviation-based program equivalence checking approach, which is an ideal fit for the whole-program plagiarism detection. Instead of directly comparing the similarity between two programs, LoPD searches for any dissimilarity between two programs by finding an input that will cause these two programs to behave differently, either with different output states or with semantically different execution paths. As long as we can find one dissimilarity, the programs are semantically different; but if we cannot find any dissimilarity, it is more likely a plagiarism case. We leverage dynamic symbolic execution to capture the semantics of execution paths and to find path deviations. Compared to the existing detection approaches, LoPD's formal program semantics-based method is more resilient to automatic obfuscation schemes. Our evaluation results indicate that LoPD is effective in detecting whole-program plagiarism. Furthermore, we demonstrate that LoPD can be applied to partial software plagiarism detection as well. The encouraging experiment results show that LoPD is an appealing complement to existing software plagiarism detection approaches.
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
“LoPD identifies the similarity of programs based on their implemented program logic to determine if they are semantically equivalent.”
From Academic Source Code Plagiarism Detection by Measuring Program Behavioral Similarity (2021) · cites this paper as [54]
Citations
Cites
de Moura, L., & Bjørner, N. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78800-3_24 · Cited by 6,595 · cited 1×
“, STP [58] and Z3 [59]) is usually used to generate the input that satisfies the corresponding path constraints.”
Dijkstra, E. W. (1976) · CERN Document Server (European Organization for Nuclear Research) · Cited by 4,733
An axiomatic basis for computer programming
Hoare, C. A. R. (1969) · Communications of the ACM · doi:10.1145/363235.363259 · Cited by 4,002
Symbolic execution and program testing
King, J. C. (1976) · Communications of the ACM · doi:10.1145/360248.360252 · Cited by 3,031
LLVM: A compilation framework for lifelong program analysis & transformation
Lattner, C., & Adve, V. (2004) · International Symposium on Code Generation and Optimization, 2004. CGO 2004. · doi:10.1109/cgo.2004.1281665 · Cited by 2,681
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
CUTE: a concolic unit testing engine for C
Sen, K., Marinov, D., & Agha, G. (2005) · Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering · doi:10.1145/1081706.1081750 · Cited by 1,651
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
An empirical study of the reliability of UNIX utilities
Miller, B. P., Fredriksen, L., & So, B. (1990) · Communications of the ACM · doi:10.1145/96267.96279 · Cited by 1,281
Clone detection using abstract syntax trees
Baxter, I. D., Yahin, A., Moura, L., Sant'Anna, M., & Bier, L. (2002) · Proceedings. International Conference on Software Maintenance (Cat. No. 98CB36272) · doi:10.1109/icsm.1998.738528 · Cited by 1,277
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×
“tection techniques include string-based [30], tree-based [31], [32], token-based [7], [33], [34] and PDG-based [35]–[37].”
Automated Whitebox Fuzz Testing.
Godefroid, P., Levin, M. Y., & Molnar, D. A. (2008) · Cited by 1,095
DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones
Jiang, L., Misherghi, G., Su, Z., & Glondu, S. (2007) · 29th International Conference on Software Engineering (ICSE'07) · doi:10.1109/icse.2007.30 · Cited by 1,039
Automated software test data generation
Korel, B. (1990) · IEEE Transactions on Software Engineering · doi:10.1109/32.57624 · Cited by 971
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
BitBlaze: A New Approach to Computer Security via Binary Analysis
Song, D., Brumley, D., Yin, H., Caballero, J., Jager, I., Kang, M. G., Liang, Z., Newsome, J., Poosankam, P., & Saxena, P. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-89862-7_1 · Cited by 718
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
Identifying similar code with program dependence graphs
Krinke, J. (2002) · Proceedings Eighth Working Conference on Reverse Engineering · doi:10.1109/wcre.2001.957835 · Cited by 616
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
Using Slicing to Identify Duplication in Source Code
Komondoor, R., & Horwitz, S. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-47764-0_3 · Cited by 527
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
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
Differential symbolic execution
Person, S., Dwyer, M. B., Elbaum, S., & Pǎsǎreanu, C. S. (2008) · Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering · doi:10.1145/1453101.1453131 · Cited by 268
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
Obfuscator-LLVM -- Software Protection for the Masses
Junod, P., Rinaldini, J., Wehrli, J., & Michielin, J. (2015) · 2015 IEEE/ACM 1st International Workshop on Software Protection · doi:10.1109/spro.2015.10 · Cited by 238
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
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-citationAutomatic Reverse Engineering of Malware Emulators
Sharif, M., Lanzi, A., Giffin, J., & Lee, W. (2009) · 2009 30th IEEE Symposium on Security and Privacy · doi:10.1109/sp.2009.27 · Cited by 204
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
A Generic Approach to Automatic Deobfuscation of Executable Code
Yadegari, B., Johannesmeyer, B., Whitely, B., & Debray, S. (2015) · 2015 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2015.47 · Cited by 195
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
Semantic Diff: a tool for summarizing the effects of modifications
Jackson, & Ladd (1994) · Proceedings International Conference on Software Maintenance ICSM-94 · doi:10.1109/icsm.1994.336770 · Cited by 185
A Study of the Packer Problem and Its Solutions
Guo, F., Ferrie, P., & Chiueh, T.-C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-87403-4_6 · Cited by 180
Detecting code clones in binary executables
Sæbjørnsen, A., Willcock, J., Panas, T., Quinlan, D., & Su, Z. (2009) · Proceedings of the eighteenth international symposium on Software testing and analysis · doi:10.1145/1572272.1572287 · Cited by 171
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
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-citationPractical, Low-Effort Equivalence Verification of Real Code
Ramos, D. A., & Engler, D. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22110-1_55 · Cited by 126
Binary-code obfuscations in prevalent packer tools
Roundy, K., & Miller, B. P. (2013) · ACM Computing Surveys · doi:10.1145/2522968.2522972 · Cited by 122
Schüler, D., Dallmeier, V., & Lindig, C. (2007) · doi:10.1145/1321631.1321672 · Cited by 117
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
Dynamic Software Birthmarks to Detect the Theft of Windows Applications
Tamada, H., Okamoto, K., Nakamura, M., Monden, A., & Matsumoto, K. (2004) · Cited by 107
Fast location of similar code fragments using semantic 'juice'
Lakhotia, A., Preda, M. D., & Giacobazzi, R. (2013) · doi:10.1145/2430553.2430558 · Cited by 105
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 2×
“[27], [28] introduced system call-based birthmarks.”
BackgroundSelf-citationBrumley, D., Caballero, J., Liang, Z., Newsome, J., & Song, D. X. (2018) · doi:10.1184/r1/6469484 · Cited by 97
Creating Vulnerability Signatures Using Weakest Preconditions
Brumley, D., Wang, H., Jha, S., & Song, D. X. (2007) · IEEE Computer Security Foundations Workshop (CSFW) · doi:10.1109/csf.2007.17 · Cited by 90
A 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-citationSymbolic Execution of Obfuscated Code
Yadegari, B., & Debray, S. (2015) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2810103.2813663 · Cited by 87
Detecting Software Theft via System Call Based Birthmarks
Wang, X., Jhi, Y.-C., Zhu, S., & Liu, P. (2009) · 2009 Annual Computer Security Applications Conference · doi:10.1109/acsac.2009.24 · Cited by 87
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-citationBinClone: Detecting Code Clones in Malware
Farhadi, M. R., Fung, B. C. M., Charland, P., & Debbabi, M. (2014) · IEEE International Conference on Software Security and Reliability Companion · doi:10.1109/sere.2014.21 · Cited by 76
Plagiarizing Smartphone Applications: Attack Strategies and Defense Techniques
Potharaju, R., Newell, A., Nita-Rotaru, C., & Zhang, X. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-28166-2_11 · Cited by 68
Software Plagiarism Detection with Birthmarks Based on Dynamic Key Instruction Sequences
Tian, Z., Zheng, Q., Liu, T., Fan, M. Y., Zhuang, E., & Yang, Z. (2015) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2015.2454508 · Cited by 66
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-citationExpose: Discovering Potential Binary Code Re-use
Ng, B. H., & Prakash, A. (2013) · IEEE Annual International Computer Software and Applications Conference (COMPSAC) · doi:10.1109/compsac.2013.83 · Cited by 58
Program 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×
“3) We have extended our preliminary conference paper [18] in several ways by discussing and evaluating the possible application to partial plagiarism detection, adding more testing cases of whole-program plagiarism detection, testing with the stateof-the-art obfuscators such as Obfuscator-LLVM [4] and Code Virtualizer…”
BackgroundSelf-citationFinding Plagiarisms among a Set of Programs with JPlag
Malpohl, G., Prechelt, L., & Philippsen, M. (2002) · Verlag der Technischen Universität Graz · doi:10.3217/jucs-008-11-1016 · Cited by 56 · cited 1×
“tection techniques include string-based [30], tree-based [31], [32], token-based [7], [33], [34] and PDG-based [35]–[37].”
LOCO: an interactive code (De)obfuscation tool
Madou, M., Put, L. V., & Bosschere, K. D. (2006) · ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM) · doi:10.1145/1111542.1111566 · Cited by 51
DARWIN: An approach to debugging evolving programs
Qi, D., Roychoudhury, A., Liang, Z., & Vaswani, K. (2012) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/2211616.2211622 · Cited by 42
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×
“[5], [25] proposed to use core values as birthmark to detect software 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-citationA Software Birthmark Based on Dynamic Opcode n-gram
Lu, B., Liu, F., Ge, X., Liu, B., & Luo, X. (2007) · IEEE International Conference on Semantic Computing (ICSC) · doi:10.1109/icsc.2007.15 · Cited by 32
(2007) · IEEE International Conference on Semantic Computing (ICSC) · doi:10.1109/icsc.2007.7 · Cited by 27
Plagiarism detection for multithreaded software based on thread-aware software birthmarks
Tian, Z., Zheng, Q., Liu, T., Fan, M. Y., Zhang, X., & Yang, Z. (2014) · International Conference on Program Comprehension · doi:10.1145/2597008.2597143 · Cited by 18
Loco: An Interactive Code (De)Obfuscation tool
Madou, M., Put, L. V., & Bosschere, K. D. (2005) · Ghent University Academic Bibliography (Ghent University) · Cited by 7
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
“, code similarity comparison beyond function pairs, which has been emphasized by previous work [27], [37], [43], [68], [26], [60], [61](, although they can only work for code of the same ISA).”
BackgroundLuo, L., Ming, J., Wu, D., Liu, P., & Zhu, S. (2017) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2017.2655046 · Cited by 144
“[55], [79] presented a program logic based approach which searches for dissimilarity between two programs by finding path deviations.”
BackgroundSelf-citationA blockchain-based code copyright management system
Jing, N., Liu, Q., & Sugumaran, V. (2021) · Information Processing & Management · doi:10.1016/j.ipm.2021.102518 · Cited by 140
Kim, D., Kim, E., Kil, S., Son, S., & Kim, Y. (2022) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2022.3187689 · Cited by 164
“The symbolic constraints could express the output variables or states of a basic block [7], a program slice [16], [59], [63], or a path [8], [79], [80].”
BackgroundAutomatic Grading of Programming Assignments: An Approach Based on Formal Semantics
Liu, X., Wang, S., Wang, P., & Wu, D. (2019) · IEEE/ACM International Conference on Software Engineering: Software Engineering Education and Training (ICSE-SEET) · doi:10.1109/icse-seet.2019.00022 · Cited by 107
“Our idea is to efficiently search for semantic differences between a student’s submission and the reference implementation by detecting Path Deviation [16]–[18].”
MethodSelf-citation
Metadata
- Authors
- Ming, J., Zhang, F., Wu, D., Liu, P., & Zhu, S.
- Affiliations
- Pennsylvania State University (US)
- Venue
- IEEE Transactions on Reliability
- Published
- 2016-12
- Volume
- 65
- Issue
- 4
- Pages
- 1647-1664
- ISSN
- 0018-9529 (ISSN-L)
- 1558-1721
- OpenAlex
- W2432058664
- Semantic Scholar
- cef283e8a74eed398ce164d455d787f1f21b7ed0
- Cited by
- 33
- References
- 76
- Citations by year
- 2025: 1 · 2024: 6 · 2023: 1 · 2022: 3 · 2021: 4 · 2020: 6 · 2019: 3 · 2018: 1 · 2017: 7 · 2016: 1
- FWCI
- 8.90
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Reliability (publishedVersion)
- Funders
- National Science Foundation (CCF-1320605, CNS-1223710, CNS-1422594, CNS-1505664)
- Office of Naval Research (N00014-13-1-0175, N00014-16-1-2265)
- ARO (W911NF-09-1-0525, W911NF-13-1-0421)
- Topics
- Physical Sciences › Computer Science › Information Systems › Software Engineering Research
- Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
- Social Sciences › Education › Academic integrity and plagiarism
- Keywords
- software plagiarism detection, program equivalence checking, obfuscation resilience, dynamic symbolic execution, program semantics
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.