GPLAG: detection of software plagiarism by program dependence graph analysis
The DOI matches its Crossref record; 24 of the 28 references it cites were found in a registry or an index.
Abstract
Along with the blossom of open source projects comes the convenience for software plagiarism. A company, if less self-disciplined, may be tempted to plagiarize some open source projects for its own products. Although current plagiarism detection tools appear sufficient for academic use, they are nevertheless short for fighting against serious plagiarists. For example, disguises like statement reordering and code insertion can effectively confuse these tools. In this paper, we develop a new plagiarism detection tool, called GPLAG, which detects plagiarism by mining program dependence graphs (PDGs). A PDG is a graphic representation of the data and control dependencies within a procedure. Because PDGs are nearly invariant during plagiarism, GPLAG is more effective than state-of-the-art tools for plagiarism detection. In order to make GPLAG scalable to large programs, a statistical lossy filter is proposed to prune the plagiarism search space. Experiment study shows that GPLAG is both effective and efficient: It detects plagiarism that easily slips over existing tools, and it usually takes a few seconds to find (simulated) plagiarism in programs having thousands of lines of code.
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
“Although there are graph-based approaches that are potentially less vulnerable to such attacks, they are not feasible in practice [24] due to the NP nature of determining subgraph isomorphism [25,29,45].”
From Detecting Automatic Software Plagiarism via Token Sequence Normalization (2024) · cites this paper as [24]
In the citing paper
“Compared to formal languages (i.e.programs) plagiarism in natural language is relatively more difficult to identify because of the flexibility of morphology and syntax [8].”
From 2L-APD: A Two-Level Plagiarism Detection System for Arabic Documents (2018) · doi:10.2478/cait-2018-0011 · cites this paper as [8]
Citations
Cites
(1979) · Cited by 43,841
Biometry: The Principles and Practice of Statistics in Biological Research
Sokal, R. R., & Rohlf, F. J. (1969) · Cited by 20,963
Biometry. The Principles and Practice of Statistics in Biological Research
Fienberg, S. E., Sokal, R. R., Rohlf, F. J., Rohlf, F. J., & Sokal, R. R. (1970) · Biometrics · doi:10.2307/2529087 · Cited by 9,364
Testing Statistical Hypotheses
(2021) · Wiley Series in Probability and Statistics · doi:10.1002/9781119243830.ch12 · Cited by 5,106
Biometry: The Principles and Practice of Statistics in Biological Research (2nd ed.).
Bailey, K., Sokal, R. R., & Rohlf, F. J. (1982) · Journal of the American Statistical Association · doi:10.2307/2287349 · Cited by 3,728
The program dependence graph and its use in optimization
Ferrante, J., Ottenstein, K. J., & Warren, J. D. (1987) · ACM Transactions on Programming Languages and Systems · doi:10.1145/24039.24041 · Cited by 2,755
An Algorithm for Subgraph Isomorphism
Ullmann, J. R. (1976) · Journal of the ACM · doi:10.1145/321921.321925 · Cited by 2,277 · cited 1×
“, Ullmann’s algorithm [20] and VF [8] are comfortable with graphs of hundreds or thousands of vertices.”
MethodCCFinder: 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 · cited 2×
“2, we provided an overview of existing techniques based on different representations of programs [1, 2, 9, 11, 17, 18].”
BackgroundMethodClone 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 · cited 2×
“Then duplicate subtrees are searched between two programs, and code corresponding to duplicate subtrees are labelled as plagiarism [2, 11].”
BackgroundMethodSchleimer, 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 11×
“We spent two hours plagiarizing it such that both Moss and JPlag were confused.”
BackgroundMethodInfluentialOn 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 · cited 2×
“Two programs are compared to find sequences of same strings [1].”
BackgroundMethodCloseGraph: mining closed frequent graph patterns
Yan, X., & Han, J. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956784 · Cited by 635 · cited 3×
“CloseGraph: mining closed frequent graph patterns.”
MethodInfluentialSelf-citationIdentifying 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 · cited 2×
“Moreover, for both effectiveness and efficiency, a statistical lossy filter is developed, which has not been seen in previous studies [10, 12].”
MethodResultUsing 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 · cited 2×
“Moreover, for both effectiveness and efficiency, a statistical lossy filter is developed, which has not been seen in previous studies [10, 12].”
MethodResultLinear time algorithm for isomorphism of planar graphs (Preliminary Report)
Hopcroft, J. E., & Wong, J. K. (1974) · Proceedings of the sixth annual ACM symposium on Theory of computing - STOC '74 · doi:10.1145/800119.803896 · Cited by 344
DynaMine: finding common error patterns by mining software revision histories
Livshits, B., & Zimmermann, T. (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.1081754 · Cited by 330 · cited 1×
“apply frequent itemset mining algorithms to software revision history, which uncovers programming rules that developers are expected to conform to [16].”
MethodPerformance evaluation of the VF graph matching algorithm
Cordella, L. P., Foggia, P., Sansone, C., & Vento, M. (2003) · Proceedings 10th International Conference on Image Analysis and Processing · doi:10.1109/iciap.1999.797762 · Cited by 226
Linear time algorithm for isomorphism of planar graphs.
Hopcroft, J. E., & Wong, J. K. (1974) · Cited by 224
Group-Theoretic Algorithms and Graph Isomorphism
(1982) · Lecture Notes in Computer Science · doi:10.1007/3-540-11493-9 · Cited by 196 · cited 1×
“Although subgraph isomorphism is NP-complete in general [5], research in the past three decades has shown that some algorithms are reasonably fast on average and become computationally intractable only in a few cases [6] [7].”
BackgroundTesting Statistical Hypotheses
Ziegel, E. (1987) · Technometrics · doi:10.1080/00401706.1987.10488294 · Cited by 183
Mining Behavior Graphs for “Backtrace” of Noncrashing Bugs
Liu, C., Yan, X., Yu, H., Han, J., & Yu, P. S. (2005) · Proceedings of the 2005 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972757.26 · Cited by 129 · cited 1×
“show that mining program control flow graphs can help developers find logic errors [14,15].”
BackgroundSelf-citationFinding interesting associations without support pruning
Cohen, E., Datar, M., Fujiwara, S., Gionis, A., Indyk, P., Motwani, R., Ullman, J. D., & Yang, C. (2002) · Proceedings of 16th International Conference on Data Engineering (Cat. No.00CB37073) · doi:10.1109/icde.2000.839448 · Cited by 116 · cited 1×
“There are studies on detection of other kinds of plagiarism, such as plagiarized research papers, homework answers, and Web pages [3].”
BackgroundFinding 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 11×
“We spent two hours plagiarizing it such that both Moss and JPlag were confused.”
BackgroundMethodInfluentialMining Control Flow Abnormality for Logic Error Isolation
Liu, C., Yan, X., & Han, J. (2006) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972764.10 · Cited by 33 · cited 1×
“show that mining program control flow graphs can help developers find logic errors [14,15].”
BackgroundSelf-citation
Research works printed but not linked: 6
- 10.5555/832303.836911 · doi:10.5555/832303.836911
- 10.5555/850947.853341 · doi:10.5555/850947.853341
- 10.5555/846219.847313 · doi:10.5555/846219.847313
- 10.5555/647170.718283 · doi:10.5555/647170.718283
- K. Kontogiannis , M. Galler , and R. DeMori . Detecting code similarity using patterns . In Working Notes of 3rd Workshop on AI and Software Engineering , 1995 .]] K. Kontogiannis, M. Galler, and R. DeMori. Detecting code similarity using patterns. In Working Notes of 3rd Workshop on AI and Software Engineering, 1995.]]
- 10.5555/832308.837142 · doi:10.5555/832308.837142
Cited by
Comparison and evaluation of code clone detection techniques and tools: A qualitative approach
Roy, C. K., Cordy, J. R., & Koschke, R. (2009) · Science of Computer Programming · doi:10.1016/j.scico.2009.02.007 · Cited by 1,001
“Approximative search for similar subgraphs in PDGs Duplix [75], GPLAG [81] Searching similar subgraphs in PDGs with slicing Komondoor [65] Mapping PDG subgraphs to structured syntax and reuse Deckard Gabel [46] more memory-efficient suffix-array in place of suffix trees and allows the user to tailor…”
BackgroundMethodInfluentialA Survey on Software Clone Detection Research
Roy, C. K., & Cordy, J. R. (2007) · QSpace (Queen's University Library) · Cited by 962
Deep learning code fragments for code clone detection
White, M., Tufano, M., Vendome, C., & Poshyvanyk, D. (2016) · Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering · doi:10.1145/2970276.2970326 · Cited by 558
DeepWukong: Statically Detecting Software Vulnerabilities Using Deep Graph Neural Network
Cheng, X., Wang, H., Hua, J., Xu, G., & Sui, Y. (2021) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/3436877 · Cited by 335
Structural detection of android malware using embedded call graphs
Gascon, H., Yamaguchi, F., Arp, D., & Rieck, K. (2013) · Proceedings of the 2013 ACM workshop on Artificial intelligence and security · doi:10.1145/2517312.2517315 · Cited by 329
“Determining similar program code is an important problem encountered in several areas of security research, including the detection of malware [1, 21, 27, 36], software plagiarism [28, 30] and vulnerabilities [9, 40].”
Background
Metadata
- Authors
- Liu, C., Chen, C., Han, J., & Yu, P. S.
- Affiliations
- University of Illinois Urbana-Champaign (US)
- IBM (United States) (US)
- Venue
- Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2006-08-20
- Pages
- 872-881
- OpenAlex
- W2107697055
- Semantic Scholar
- 9ca919b9f78ae38917202875298d2bf450a322a2
- Cited by
- 422
- References
- 28
- Citations by year
- 2026: 2 · 2025: 9 · 2024: 13 · 2023: 15 · 2022: 15 · 2021: 30 · 2020: 32 · 2019: 26 · 2018: 42 · 2017: 19 · 2016: 26 · 2015: 31 · 2014: 37 · 2013: 30 · 2012: 29
- FWCI
- 9.47
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Information Systems › Software Engineering Research
- Social Sciences › Education › Academic integrity and plagiarism
- Physical Sciences › Computer Science › Hardware and Architecture › Physical Unclonable Functions (PUFs) and Hardware Security
- Keywords
- software plagiarism detection, program dependence graph, open source software, source code plagiarism, lossy filters, search space pruning
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.