CodEX is a source code search engine that allows users to search a repository of source code snippets using source code snippets as the query also. A potential use for such a search engine is to help educators identify cases of plagiarism in students' programming assignments. This paper evaluates CodEX in this context. Abstract Syntax Trees (ASTs) are used to represent source code les on an abstract level. This, combined with node hashing and similarity calculations, allows users to search for source code snippets that match suspected plagiarism cases. A number of commonly-employed techniques to avoid plagiarism detection are identi ed, and the CodEX system is evaluated for its ability to detect plagiarism cases even when these techniques are employed. Evaluation results are promising, with 95% of test cases being identi ed successfully.
CodEX is a general-purpose search engine to allow users to search for source code snippets, developed as part of an undergraduate nal year project. The user interface supports three di erent methods providing queries to the system: { keyword-based search: obtains keywords from the user and returns source les relevant to these keywords from GitHub3. { description-based search: allows users to input questions or descriptions of code, and returns relevant StackOver ow4 answers to similar questions. { source code snippet search: obtains a complete source code structure (code snippet) from the user, and returns source les containing similar code snippets from GitHub.
One potential use for the source code snippet search feature is the detection of plagiarism among programming assignments. Given a repository of existing source code, a suspected case of plagiarism can be used as a search snippet, with CodEX providing a list of similar code snippets. This paper focuses on this use
case, in the context of ve common tactics used by students to avoid detection and a combination of these.
Due to the syntax di erences of variant source code languages, di erent APIs or supporting external classes are needed to implement the source code snippet searching feature. CodEX applies a general algorithm based on Abstract Syntax Trees (ASTs) to solve this problem. Initially, Python and Java code snippets were chosen as examples, since their AST structures vary to some degree. Successfully applying this approach to multiple languages indicates the potential for extending the system to other programming languages in the future.
In Section 2 of this paper, related work is listed and discussed with comparison to CodEX; in Section 3, the implementation approach of the source code snippet search feature is illustrated in detail; evaluation results are displayed in Section 4 with brief analysis; the last section draws conclusions and outlines the future work of this project. 2
Multiple code search engines already exist that support keyword-based
searching in multiple programming languages, such as searchcode5, codas6, unspsc7,
Debian8. etc. CodEX distinguishes itself from these through its code-snippet
searching module and plagiarism detection. Regarding code snippet searching,
there are already several pioneers who have achieved high performance in this
area [
Other variations of ngerprinting are frequently proposed by Information
Retrieval researchers. Among these, Syntax Tree Fingerprinting [
Regarding plagiarism among programming assignments, multiple commonly
used techniques for avoiding plagiarism detection should be considered when
developing source code plagiarism detection tools [
In this section, the idea and advantages of ASTs are discussed in detail initially.
Following this, a number of techniques are identi ed in Section 3.2 that are
frequently used by students to avoid plagiarism detection. The implementation
strategy for code snippet searching is then demonstrated in Section 3.3.
3.1
As an abstract form of source code structure, ASTs capture the structural
features of code snippets and represent them in a hierarchical tree structure.
Compared to Concrete Syntax Trees (CSTs) [
This advantage makes a signi cant di erence for the implementation: AST
node types and attributes are classi ed to declare the component usage and
function, which allows noise to be removed easily. The fact that ASTs translate
the structure of source code into parent-child or sibling relationships among tree
nodes enables the e cient depth- rst top-to-bottom traversal strategy [
generators for Java source les. As Javalang is not a fully-developed AST API, it was necessary to implement additional methods to ful ll necessary analysis for Java source les. 3.2
In developing this module, it was necessary to identify methods that students use
to avoid plagiarism detection. Additionally, certain di erences between source
code submissions would have no e ect on the overall functionality of the code,
but would cause a simple matching algorithm to fail. Six diverse techniques were
initially identi ed for particular focus, as follows:
{ output statement insertion/removal : inserting or removing output
statements (e.g. \print" in Python) are inserted into the original code.
{ comments insertion/removal : inserting or removing comments to the original
code.
{ identi er name modi cation: modifying identi er names (variable names,
method names, class names etc.).
{ change code order : changing the order of some pieces of source code to avoid
plagiarism detection (e.g. changing the order of function declarations).
However, only order changes between sibling nodes are relevant to this technique,
while those between parent-child nodes are not plagiarism techniques as they
have a functional e ect on the source le.
{ combine multiple code blocks from multiple source les : copying multiple
code blocks from di erent source les where each piece of copied code is not
serious enough to be de ned as plagiarism. This technique cannot be easily
detected by traditional source code search engines which simply evaluate the
similarity between the input code and individual source les.
{ meaningless code insertion: this is the trickiest plagiarism technique that
challenges plenty of researchers in the eld [
The implementation of the source code snippet search feature follows the classical information retrieval process: preprocessing, indexing, searching. These are addressed in the following sections.
Source File Pre-processing As is shown in Figure 1, in the pre-processing phase, the source code snippets are rstly parsed into ASTs. Next, some noise (unimportant nodes in green) is removed from these trees. Some plagiarism techniques related to noise are detected during this step. Here, four types of noise are removed: identi er names, inner documents (comments), output statements and unused variables. These unimportant nodes are pruned from Python ASTs and Java ASTs with di erent strategies.
For the cleaning step in Python source les, a \visitor" is implemented to traverse the AST of each code snippet and invoke diverse removal operations on di erent types of noise. This visitor is an instance of a class implementing the abstract NodeTransformer class provided by Python AST API. In this class, multiple methods are de ned and implemented for di erent types of nodes to make modi cations to their attribute values and return the modi ed nodes. These methods are implemented as lters for source les. For each type of noise, there is a speci c lter implemented in the visitor to remove it from the original nodes. When removing the identi er names, only those identi er names de ned within the code snippets are removed but those standard class/method names de ned by external classes are retained as they have a functional e ect on the source les. Next, all the code snippets are serialized as Strings in nested lists to represent the hierarchical structures. However, for Java source le code cleaning, it was necessary to implement additional serialization and noise cleaning strategies as they are not provided or directly supported by Javalang.
Unused variables, the variables that are de ned or initialized but never called in the source le are also detected in this phase, as they are regarded as one category of meaningless elements. However, removing them demands another traversal of the entire tree as the list of unused variables can only be obtained after the rst traversal. Early experimentation indicated that the time required for this process was excessive and so it was removed from the current version of the system in order to improve the response time for users. Including a more e cient implementation is left to future work, which assumes more available computational resources.
In summary, noise cleaning is performed during the preprocessing phases for both Python and Java, after which the output insertion/removal, inner documents (comment) insertion/removal and identi er name modi cations techniques are all addressed. Also, a partial solution to the \meaningless code insertion" problem is also proposed and demonstrated in this phase. Therefore, what has been left to the latter phases are those plagiarism techniques involving structural modi cations.
Indexing In the indexing phase, the cleaned source code is represented by
appropriate data structures for further comparison and calculation. As Figure 1
shows, after the preprocessing phase, the source les have been cleaned and
turned into pruned ASTs. Nevertheless, there are still some steps to execute
before the similarity calculation. To summarise this process: rstly, a ngerprint
is generated for each tree nodes to represent its relevant information. In order to
avoid redundancy, not all nodes need to be analyzed and stored; instead, only
important nodes are stored for further comparison. Therefore, a benchmark
determining what constitutes an \important" node nodes is determined, which also
re ects the granularity of code snippet searching algorithms. Secondly,
following the suggestion in [
These three key tasks in the indexing phase are discussed in detail as follows:
1. Node Hashing Granularity: As mentioned above, in the indexing phase,
the code snippet is decomposed into relatively ne-grained code components
of diverse granularity. Here, \relatively ne-grained" means that the code
structure is decomposed thoroughly enough to expose all matching elements,
while some tiny elements such as constants and parameters are not
decomposed as independent nodes to avoid a cumbersome comparison process. This
does not mean that these tiny elements will be ignored but they are
contained within some bigger nodes. However, now that tiny elements need to
be treated in a di erent way, a speci c benchmark deciding what elements
are \tiny" should be determined in advance. This benchmark is essential
because it also determines the granularity of the indexing phase, which directly
a ects the accuracy and e ciency of the search algorithm. Inspired by the
code clone detection research of Nilsson et al. [
Searching To search for suspected plagiarism cases, the user supplies a program or code snippet. This is passed through two di erent search strategies. Firstly, the query code is compared with all code snippets in the index to obtain a similarity score for each. The output of the search is a ranked list of code snippets from the index based on their similarity to a query code snippet.Secondly, a global similarity score is computed, by comparing the query to the corpus as a whole. Those snippets from the corpus that have contributed to this global score (assuming a suspected plagiarism case has been detected) are made available to the user. Given that plagiarism detection requires a manual judgment (not all similar code is plagiarised), these search outputs are aimed at providing the user with the most likely sources of plagiarised code.
Local Similarity Matching (weight-based depth rst search): Figure 2 shows the mechanism for calculating local similarities. The similarity score is calculated during depth- rst traversal through a nested query ngerprint. This query ngerprint is represented as a tree in this diagram, as it is based on an abstract form of its original AST hierarchy.
The rst step is to search the weight of current query node within the indexed
dictionary of the corpus, in which each di erent weight is a key mapping to
a list of corresponding node ngerprints. The corresponding ngerprint list is
extracted out for comparison. Next, the second step is the comparison between
the hash values of the query nodes and that of all nodes in the list. In this stage,
a matching judgment is made to each node in the ngerprint list, and invokes
two branches A and B for further processing:
{ Branch A: If some node in the ngerprint list has the same hash value as
the this query node, then this judgment goes to the Branch A (the green
branch in the diagram), where the similarity score is increased by the weight
of the matching node. After the similarity score is updated, the subtree
derived from this query node is pruned from the query tree in the third step
(A3). The tree-pruning step aims to avoid further unnecessary comparison
between its subnodes and the corpus, since the matching of current query
node also implies matching of all its subtrees. This is why in the searching
phase the nested indexed structure can achieve higher time e ciency than
plain indexed structure proposed in [
After the traversal is complete, a similarity score is calculated as the total weight of matching code blocks from each source le in the corpus. A threshold is pre-de ned to indicate whether a similarity score is high enough to indicate a suspected plagiarism case. The similarity scores are normalised as the proportion of the matching weight over the total weight of query code snippet to avoid snippet length having an impact. The suspected plagiarism threshold must consequently lie between 0 and 1. Empirical testing resulted in a threshold of 0.6 being identi ed. Although this threshold achieved good accuracy, it still needs to be tuned with more test cases in the future stages for higher accuracy. Global Similarity & Matching Block Threshold: Global similarity is the similarity score between the query code snippet and the whole corpus, which is di erent from the similarity between each single source le in the corpus (local similarity) as there is only one global similarity score for each query. The aim of global similarity is to detect plagiarism queries with multiple copied code blocks from the di erent sources, which cannot be shown by local similarity when each copied code block is not big enough to be de ned as plagiarism. However, this global similarity makes false positives more likely, as a query may have a high global similarity based on matching many small code snippets throughout the corpus. To avoid this issue, only \big" matching code blocks are used in the global similarity calculation. Therefore, another threshold needs to be set for de ning \big" matching blocks (called the \blockThreshold"). This threshold is based on the weight of a code block, and empirical testing indicates that a weight of 50 is suitable. This had the e ect of ltering out scattered small pieces of code blocks while retaining complete code structures such as big loops and methods. In addition, at most one matching block is taken from a source le to calculate the global similarity. This is to avoid de ning normal queries with multiple scattered matching blocks as plagiarism. Therefore, among all matching blocks from each source le, the matching code block with the highest weight is selected to contribute to the global similarity calculation.
After all matching blocks are gathered, the sum of the weight of these code blocks is calculated. Next, the similarity score is normalised as the proportion of this sum over the total weight of query code. Finally, this global similarity score is compared with the pre-de ned plagiarism threshold. If the threshold is exceeded, this query is suspected to have copied blocks from multiple source les, and these component source les are marked in the result list. 4
To evaluate the accuracy of the code-snippet searching function and the reliability of its plagiarism detection functionality, both original code snippets and plagiarism code snippets were input to this searching module as test cases. For each of the techniques to avoid plagiarism detection identi ed in Section 3.2, 10 pairs of original & \plagiarised" code snippets were designed using corresponding techniques. Of these, 5 pairs of test cases are in Python and the other 5 are in Java. Additionally, 10 cases were also created whereby a mixture of all the individual techniques were employed.
Fig. 3. Source Code Plagiarism Detection Searching Evaluation Results.
Firstly, in the context of code searching in general, no false-positive issue was observed in the evaluated results. Despite the abstractions used in searching, only source les containing similar code snippets are returned, in which the matching lines between the input query and source les are highlighted for comparison. For most test cases, the returned results ranked in the top 10 all contain multiple matching lines. For some other tested code snippets, there are only 7 or 8 returned results containing matching lines, and these test cases are all self-designed structures that are not commonly used. In general, the code-usage searching function achieves precision of 0.84 and is proved to be helpful to nd the relative usage of query code snippets.
Regarding the plagiarism detection function, as Figure 3 shows, all similarity scores assigned to plagiarism test cases purely applying identi er name modi cations, output insertions and sibling-code-order changes are 1. which suggests that these techniques are unlikely to succeed in avoiding plagiarism detection in the CodEX system. For the \combining multiple code blocks" technique, each case consists of four code snippets, and contains at least one original block and three copied source code blocks. These copied source code blocks vary in both size and distribution patterns. According to the evaluation results, 90% of these plagiarism cases can be detected by CodEX and are assigned high global similarities (in excess of the similarity threshold), and the only one plagiarism case that was not detected as the plagiarism case is found to contain small scattered copied code blocks.
Apart from test cases about one single plagiarism technique, the 10 mixed test cases applying all the plagiarism techniques are also designed to test the overall plagiarism detection accuracy of CodEX. 80% of these mixed-plagiarism source les are judged as plagiarism cases by the system and 20% of them are not detected as plagiarism cases as their copied code blocks are scattered and relatively small.
In summary, CodEX achieves accuracy of 84% for the source code snippet search, and achieves high performance on detecting all the ve plagiarism techniques introduced before as well as the mixed plagiarism cases based on them, with a 95% success rate overall. 5
As a source code search engine, CodEX supports code snippet search and source code plagiarism detection, distinguishing itself from most traditional code search engines. As is demonstrated by the evaluation results, ve commonly-used plagiarism techniques can be detected accurately. Additionally, a partial solution to the \meaningless code insertion" issue is proposed. Therefore, CodEX brings convenience to both programmers and education sta , and its high accuracy proves the feasibility of several innovated code searching algorithms. For the future work, all the thresholds should be tuned further with larger quantities of test cases to achieve higher performance. Additionally, removing unused variables and code was not implemented in this version due to speed constraints; an e cient mechanism for this can be added in future. Finally, CodEX should be extended for more programming languages other than Java and Python.