Evolving similarity functions for code plagiarism detection

ABSTRACT

Detecting whether computer program code is a student's original work or has been copied from another student or some other source is a major problem for many universities. Detection methods based on the information retrieval concepts of indexing and similarity matching scale well to large collections of files, but require appropriate similarity functions for good performance. We have used particle swarm optimization and genetic programming to evolve similarity functions that are suited to computer program code. Using a training set of plagiarised and non-plagiarised programs we have evolved better parameter values for the previously published Okapi BM25 similarity function. We have then used genetic programming to evolve completely new similarity functions that do not conform to any predetermined structure. We found that the evolved similarity functions outperformed the human developed Okapi BM25 function. We also found that a detection system using the evolved functions was more accurate than the the best code plagiarism detection system in use today, and scales much better to large collections of files. The evolutionary computing techniques have been extremely useful in finding similarity functions that advance the state of the art in code plagiarism detection.

REFERENCES

• 1: K. Bowyer and L. Hall. Experience Using 'MOSS' to Detect Cheating On Programming Assignments. In Proceedings of the Frontiers in Education Conference, volume 3, pages 18--22, 1999.
• 2: Steven Burrows , S. M. M. Tahaghoghi , Justin Zobel, Efficient plagiarism detection for large code repositories, Software—Practice & Experience, v.37 n.2, p.151-175, February 2007 [doi>10.1002/spe.v37:2]
• 3: M. Clerc and J. Kennedy. The Particle Swarm: Explosion, Stability, and Convergence in a Multi-Dimensional Complex Space. IEEE Transactions on Evolutionary Computation, 6(1):58--73, 2002.
• 4: Weiguo Fan , Michael D. Gordon , Praveen Pathak, A generic ranking function discovery framework by genetic programming for information retrieval, Information Processing and Management: an International Journal, v.40 n.4, p.587-602, May 2004 [doi>10.1016/j.ipm.2003.08.001]
• 5: David Gitchell , Nicholas Tran, Sim: a utility for detecting similarity in computer programs, The proceedings of the thirtieth SIGCSE technical symposium on Computer science education, p.266-270, March 24-28, 1999, New Orleans, Louisiana, United States
• 6: John R. Koza, Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers, Norwell, MA, 2003
• 7: K. Sparck Jones , S. Walker , S. E. Robertson, A probabilistic model of information retrieval: development and comparative experiments Part 2, Information Processing and Management: an International Journal, v.36 n.6, p.809-840, Nov.06.2000 [doi>10.1016/S0306-4573(00)00016-9]
• 8: M. Joy and M. Luck. Plagiarism in Programming Assignments. IEEE Transactions on Education, 42(2):129--133, 1999.
• 9: J. Kennedy and R. Eberhart. Particle Swarm Optimization. In Proceedings of the IEEE International Conference on Neural Networks, volume 4, pages 1942--1948, 1995.
• 10: Chao Liu , Chen Chen , Jiawei Han , Philip S. Yu, GPLAG: detection of software plagiarism by program dependence graph analysis, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150522]
• 11: Trent McConaghy , Georges Gielen, Canonical form functions as a simple means for genetic programming to evolve human-interpretable functions, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144147]
• 12: L. Prechelt, G. Malpohl, and M. Philippsen. Finding Plagiarisms among a Set of Programs with JPlag. Journal of Universal Computer Science, 8(11):1016--1038, 2002.
• 13: S. Robertson and S. Walker. Okapi/Keenbow at TREC-8. Overview of the Eighth Text REtrieval Conference (TREC-8), pages 151--162, 1999.
• 14: S. E. Robertson , S. Walker , M. Beaulieu, Experimentation as a way of life: Okapi at TREC, Information Processing and Management: an International Journal, v.36 n.1, p.95-108, Jan. 2000 [doi>10.1016/S0306-4573(99)00046-1]
• 15: Judy Sheard , Martin Dick , Selby Markham , Ian Macdonald , Meaghan Walsh, Cheating and plagiarism: perceptions and practices of first year IT students, Proceedings of the 7th annual conference on Innovation and technology in computer science education, June 24-28, 2002, Aarhus, Denmark
• 16: G. Whale, Identification of program similarity in large populations, The Computer Journal, v.33 n.2, p.140-146, April 1990 [doi>10.1093/comjnl/33.2.140]
• 17: N. Wu. Evolving Similarity Functions for Code Plagiarism Detection. Honours Thesis, RMIT, School of Computer Science and Information Technology, 2007.
• 18: Justin Zobel, "Uni cheats racket": a case study in plagiarism investigation, Proceedings of the sixth conference on Australasian computing education, p.357-365, January 01, 2004, Dunedin, New Zealand
• 19: Justin Zobel , Alistair Moffat, Exploring the similarity space, ACM SIGIR Forum, v.32 n.1, p.18-34, Spring 1998 [doi>10.1145/281250.281256]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Parameter learning

General Terms:
Algorithms, Experimentation

Keywords:
evolutionary computing, genetic programming, okapi bm25, particle swarm optimization, similarity function