liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Program Dependence Graph Generation and Analysis for Source Code Plagiarism Detection
Linköping University, Department of Computer and Information Science. Linköping University, The Institute of Technology.
2012 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Generering och analys av programberoendegrafer för detektering av plagiat i källkod (Swedish)
Abstract [en]

Systems and tools that finds similarities among essays and reports are widely used by todays universities and schools to detect plagiarism. Such tools are however insufficient when used for source code comparisons since they are fragile to the most simplest forms of diguises. Other methods that analyses intermediate forms such as token strings, syntax trees and graph representations have shown to be more effective than using simple textual matching methods. In this master thesis report we discuss how program dependence graphs, an abstract representation of a programs semantics, can be used to find similar procedures. We also present an implementation of a system that constructs approximated program dependence graphs from the abstract syntax tree representation of a program. Matching procedures are found by testing graph pairs for either sub-graph isomorphism or graph monomorphism depending on whether structured transfer of control has been used. Under a scenario based evaluation our system is compared to Moss, a popular plagiarism detection tool. The result shows that our system is more or least as effective than Moss in finding plagiarized procedured independently on the type of modifications used.

Abstract [sv]

System och verktyg som hittar likheter mellan uppsatser och rapporter används i stor omfattning av dagens universitet och skolor för att hitta plagiat bland studenters inlämningar. Sådana verktyg är dock otillräckliga när de används för att jämföra programkod eftersom de är svaga mot de enklaste formerna av modifikationer. Andra metoder som analyserar mellanstegsformer såsom tokensträngar, syntaxträd och grafrepresentationer har visat sig vara mer effektiva än att använda sig av enkla textuella metoder. I denna examensuppsats diskuterar vi hur programberoendegrafer, en abstrakt representation av en programs semantik, kan användas för att hitta jämförelsevis liknande procedurer. Vi presenterar också ett system som konstruerar approximerade programberoendegrafer från det abstrakta syntaxträdet av ett program. Matchande procedurer hittas genom att testa grafpar för antingen sub-graf isomorfism eller monomorfism beroende på om strukturerad byte av kontrolflöde har använts. I en scenariobaserad utvärdering jämför vi vårt system mot Moss, ett populärt verktyg för att detektera plagiat. Resultaten visar att vårt system är lika eller mer effektivt som Moss att detektera plagierade procedurer oberoende av de typer av modifikationer som använts.

Place, publisher, year, edition, pages
2012. , 103 p.
Keyword [en]
plagiarism, program dependence graph
National Category
Computer Science
URN: urn:nbn:se:liu:diva-87446ISRN: LIU-IDA/LITH-EX-A--12/065—SEOAI: diva2:589347
Subject / course
Computer and information science at the Institute of Technology
2012-11-27, Donald Knuth, Linköpings Universitet, Linköping, 15:00 (Swedish)
Available from: 2013-01-21 Created: 2013-01-17 Last updated: 2013-01-29Bibliographically approved

Open Access in DiVA

Program Dependence Graph Generation and Analysis for Source Code Plagiarism Detection(2329 kB)1485 downloads
File information
File name FULLTEXT02.pdfFile size 2329 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Holma, Niklas
By organisation
Department of Computer and Information ScienceThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 1493 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 611 hits
ReferencesLink to record
Permanent link

Direct link