Academic Source Code Plagiarism Detection by Measuring Program Behavioural Similarity

There exist many Java symbolic execution tools that could have been applied in BPlag. For example, JPF³³ 3 https://babelfish.arc.nasa.gov/trac/jpf/wiki/projects/jpf-symbc, JDart⁴⁴ 4 https://github.com/psycopaths/jdart, and JBSE⁵⁵ 5 http://pietrobraione.github.io/jbse/. However, a custom-built symbolic execution tools is used due to three main quality concerns:

1. 1.

   Computational complexity of existing tools

2. 2.

   Impacts of compilation on execution behaviour

3. 3.

   Quality of student assignments for analysis

Firstly, existing symbolic execution tools are designed for applying symbolic execution to program testing. In particular, they seek to identify the constraints on inputs that result in certain execution paths to aid software quality activities such as software testing or identifying bugs in code [43]. Analysing the constraints placed upon inputs requires the use of a constraint solver that can determine if encountered path conditions are mutually compatible/exclusive. Solving constraints is a computationally intensive process, and is not required by BPlag. Furthermore, existing symbolic execution tools execute all Java bytecode, even that provided as part of system libraries. BPlag is not concerned with the behaviour of system libraries, hence by mocking their interaction it lowers the amount of computation. Hence, a custom built tool that omits constraint solving and library bytecode execution was deemed to provide greater efficiency.

Secondly, during the compilation pipeline, compilers are known to optimise source code. While the standard Java compiler is known not to optimise bytecode, it was observed that it may rewrite and transform conditional code. In order to eliminate any risks associated with using compiled code, it was deemed that a source code interpreter would be appropriate. Furthermore, as BPlag is a SCPDT, it was desirable to record program behaviour as expressed through source code, and not as bytecode.

Thirdly, the quality of student code is known to vary. It is not uncommon to see assignment submissions with syntactic or semantic errors in them. If an existing symbolic execution tool was applied, it would stop BPlag from analysing such submissions; as it would require analysing only compilable assignments. When using a source code interpreter, there is the potential for submissions with syntactic or semantic errors to be partially-evaluated. In a best-case scenario this would result in some execution paths terminating early, while in a worst case scenario this would prohibit assignments from being compared. Furthermore, as most existing SCPDTs only require submissions to be parseable, this was another desired quality of BPlag.

The symbolic executor also makes some assumptions regarding the execution of any program to accommodate for the quality of student code. This is for largely for stability, and to bring assurances that any analysed program will terminate. Firstly, the execution of any loop (i.e. for, enhanced for, while, do-while) is limited to at most $n$ executions (default $n$ = 3). This assures that there are no infinite loops, as not all loops have well-defined exit conditions identifiable through symbolic execution. This avoids repeating the behaviour of the loop when represented as a PIDG under such circumstances. Secondly, any recursive method will execute at most $m$ times (default $m$ = 2). This is to ensure that there is no potential for infinite recursion. This is often seen when calculating a value or searching for a value with a recursive algorithm. Thirdly, no object or field will ever be null, unless null is explicitly assigned. This is to account for cases where fields have an assigned value that is not exposed to the symbolic executor. Subsequently, when a null field is encountered, a symbolic value is created in its place. Finally, array indexes are never out of bounds, and will always contain a value (i.e. will never be null). This is to account for situations where an array index is accessed by a symbolic value. In such situations the return value is ambiguous, and hence a symbolic value is returned.

A single PIDG is created for each execution trace returned from the symbolic executor component. Each PIDG represents the behaviour of a program over a single execution. This is in a ‘flattened’ manner, representing the utilised data and relations, its transformation, and interactions with the execution environment. An individual PIDG does not describe the branching of a program. However, a set of constructed PIDGs represents the execution behaviour of a program over all possible executions.

The PIDG is constructed by mapping runtime events (recorded by the symbolic executor) to graph components. Table III describes the mapping of each event to elements in the constructed graph. The first node created in any graph is the Entry point node. This is followed by the inclusion of any entry point parameters. The recorded runtime events are subsequently mapped to graph elements, representing program behaviour in terms of data and its relations, how it is transformed, and interactions with the execution environment. Object, Array and Symbolic Value nodes appear once per graph (as they are unique). Concrete Value nodes are duplicated on each reference, allowing for the same primitive value to appear multiple times. API method call and Operator nodes are created for each distinct usage.

Fig. 4 exemplifies representing a program as a PIDG. This example exemplifies the hashing of a password and with an appended salt value. A User object (User@0) and HashFunction object (HashFunction@1) are passed to the method call ‘hashPassword’ as entry point parameters. The fields ‘password’ (String@2) and ‘salt’ (String@3) are implicitly retrieved from the ‘user’ object (User@0). Note, it is assumed the User class is defined in source code, and hence the getter methods are followed upon invocation. The salt password and salt values are then string concatenated (i.e. the ‘+’ operator) into the variable ‘input’ (String@4). This value is then passed to the ‘hash’ function (hash(String)), resulting in the hashed representation stored in variable ‘hash’ (String@5). Note, in this example all values are symbolic, and the program contains only 1 execution path as there are no branching statements. If the program contained branching statements, it would be represented by multiple PIDGs.

A common method to evaluate graph similarity is to identify isomorphic sub-graphs. While accurate, sub-graph isomorphism is suffers from high computational complexity and does not scale to large graph sizes [44, 26]. As the PIDG has the potential to contain a large number of elements, sub-graph isomorphism is not an applicable method for evaluating the similarity of PIDGs. To compare the PIDGs efficiently, an approach was developed that takes advantage of the semantics between two programs. The graph comparison approach maps data nodes between two graphs by their local usage. It starts by mapping points-of-reference between two graphs (i.e. API method calls and primary operations) and incrementally expands out, mapping nodes and edges with similar local usages between two graphs.

This approach effectively identifies common sub-graphs between two PIDGs. It is reminiscent of token-tiling (as commonly used in SCPDTs [11]). However, applies this concept to the tiling of graph nodes and edges. The similarity of two execution traces is then measured by the size of overlapping sub-graphs. This is considered to represent the quantity of behaviour in common between the programs in a single execution trace. Subsequently, the similarity of two programs can be evaluated by the overall similarity between all extracted PIDGs.

PIDGs are compared in a two-step iterative manner. Firstly, points of reference are mapped between two graphs, indicating areas that may be semantic matches. Secondly, the mapping between two graphs is iteratively expanded by exploring the graph outwards from the set of mapped nodes and subsequently expanding the mapped nodes and edges until no more nodes can be mapped.

The usage of primary operators and API method calls are considered as points of reference between two programs. This as in any two sufficiently complex programs, it can be guaranteed there will be some usage of primary operators and API method calls. By iterating out from these points of reference, two graphs can be mapped with greater efficiency than using sub-graph isomorphism. In all comparisons, two nodes are considered potential matches if:

• •

  They have the same node type, semantic attributes (excluding runtime type if the type is defined in source code), and flags; and

• •

  They are connected by the same type of edge to the last mapped node they are connected to.

Firstly, the initial mappings between the two graphs are identified. Let $A$, $B$ be the set of all operator and API call nodes in graphs $X$ and $Y$. The elements $a\in A$ and $b\in B$ are compared pairwise if they are considered a valid match. The similarity of $a$ and $b$ is then calculated by the percentage of immediate neighbours that may also constitute valid matches. This set of candidates is then mapped by the optimal assignment of their evaluated similarity scores. This results in the initial set of all mapped primary operator and API call nodes, and their immediate neighbours.

Secondly, the mappings between the two graphs are iteratively expanded. Each node $a\in M_{a}$ and $b\in M_{b}$ (where $M_{a}$ and $M_{b}$ are the sets of last mapped nodes in $X$ and $Y$ respectively) are compared pairwise for similarity. The similarity of the nodes is once again calculated by the percentage of valid mappings of immediate neighbours to the current node, that are then mapped pairwise. This process is continued at increasing depths from the initial mapped points of reference until the sets of last mapped nodes are empty (i.e. there are no more nodes that can be mapped).

The evaluated similarity of two graphs is reduced to being the intersection between the graphs. This is the number of elements that can be mapped between the graphs as a percentage of the total size of the two graphs. For example, given two graphs $X$ and $Y$ with a mapped sub-graph $X\cap Y$, the similarity of $X$ and $Y$ is evaluated as:

The utilised algorithm is designed for speed as opposed to accuracy. Hence, it is a heuristic. If the initial points of reference are not mapped correctly in the first step, there is the potential that sections of the graph will not be mapped correctly. Furthermore, if there are dis-connected components of the graphs that do not contain primary operators or API calls, they will not be mapped. However, in pilot evaluations this has minimal impact on the evaluation of similarity.

BPlag is compared against 5 commonly utilised SCPDTs. Ideally, the approach would be evaluated against as many SCPDTs as possible to ensure a thorough comparison. However, as identified in prior works [9, 12], not all SCPDTs are made available by their authors after publication. For this evaluation, only 6 SCPDTs were identified as accessible for reuse: MOSS [18], JPlag [11], Plaggie [19], Sim [20], Sherlock-Warwick [7], Sherlock-Sydney [15].

From these 6 tools, only 5 could be consistently used for the evaluation of similarity. Unfortunately, MOSS proved to be unreliable in its use, as it cannot be run locally (MOSS is only made available as a web service). In initial evaluations, large data sets would cause MOSS to perform unreliably when evaluating the pairwise similarity of all submissions in the data sets. It was found that MOSS would hang for large intervals, and subsequently fail to respond. Hence, it could not be included in this evaluation. However, in a prior study [12], MOSS performed with poorer results than JPlag, but greater results than Sim; hence similar results can be assumed in its absence.

JPlag [11] operates by applying a token tiling algorithm to cover one source code file with tokens extracted from another. If two source files have a large degree of coverage, they can be considered similar and hence a candidate for plagiarism. First, source code files are converted into a stream of tokens. JPlag uses its own set of tokens that abstract standard language tokens to avoid matching the same token with different meanings. Second, extracted tokens are compared between files to determine similarity by the Running-Karp-Rabin Greedy-String-Tiling algorithm [45] where tokens from one file are covered over another within a tolerance of mismatch. Program similarity is evaluated as the percentage of tokens from one program that can be tiled over another program.

Plaggie [19] is a tool that is claimed to operate similarly to JPlag. However, it is an entirely local application, compared to JPlag that was originally provided as a web service. No known publication describes the operation of Plaggie; however, from examining its source code, it operates upon tokenised representations of code evaluating similarity by token tiling.

Sim [20] analyses programs for structural similarity through the use of string alignment. For two programs, Sim will first parse the source code creating a parse tree. The tool will then represent the parse trees as strings and align them by inserting spaces to obtain a maximal common subsequence of their contained tokens. The similarity of programs is then evaluated as the number of matches.

Sherlock-Warwick [7] (Sherlock-W) implements both text and tokenised comparison methods. In the tool, a pair of programs are compared for similarity 5 times: in their original form, whitespace removed, comments removed, whitespace and comments removed, and as a tokenised source file. In all cases, the comparisons measure similarity through the identification of ‘runs’ - a sequence of lines common to two files that may be interrupted by anomalies (e.g. extra lines).

Sherlock-Sydney [15] (Sherlock-S) analyses programs for lexical similarity. Digital signatures of source code are generated by hashing string token sequences (not lexical tokens) extracted from text files. The digital signatures are then compared, with the similarity of files being evaluated as the number of digital signatures in common.

Accessibility of test data is a known problem in SCPDT evaluations [9, 12]. The only authentic data sets for evaluating SCPDTs are collections of undergraduate programming assignments. However, such data sets are inherently unreliable as there is no ground truth and there is no guarantee for a diverse range of plagiarism-hiding transformations to be present.

To accommodate for these issues, BPlag will be evaluated upon generated test data sets. This will allow for a comprehensive evaluation of the presented approach against a diverse range of plagiarism-hiding transformations. Cheers, Lin and Smith [46] developed the plagiarism detection data set generation tool SPPlagiarise that applies a randomly selected set of source code transformations a random number of times at randomly selected locations in a body of source code to simulate plagiarism. All implemented transformations (listed in table IV) are representative of undergraduate programmers, and conform to the first 5 levels of Faidhi and Robinson’s [10] transformation taxonomy.

For this evaluation, the tool has been extended to afford the configuration of how pervasively source code transformations are applied to the generated data sets. This is to replace the random number of times transformations are applied, allowing a semi-fixed number of time search transformation is applied. The pervasiveness is represented as a transformation chance, a percentage value indicating how likely a transformation will be applied at any valid location in code. This allows for the evaluation of SCPDTs with different intensities of plagiarism-hiding transformations.

Two groups of programs are used to evaluate robustness. Group 1 consists of 5 undergraduate assignment submissions implemented in Java that have been collected from GitHub (previously used in [12]). Group 2 consists of a collection of 24 samples of 4 families of algorithms implemented in Java. These algorithm implementations consist of: 6 change-making (2 dynamic programming, 2 iterative, 2 recursive); 6 string search (2 Boyer-Moore, 2 Knuth-Morris-Pratt, 2 Rabin-Karp); 6 sorting (2 bubble sort, 2 merge sort, 2 quick sort); and 6 Minimum Spanning Tree (2 Kruskal’s, 2 Prim’s, 2 reverse delete).

Firstly, test data is generated using SPPlagiarise. The 29 test programs (from data sets 1 and 2) are used as ‘base’ programs for the generation of simulated plagiarised ‘variant’ programs. Variant programs are generated with varying configuration parameters, changing the levels of applied transformations, and pervasiveness of applied transformations. For each base program, 3 sets of 150 simulated plagiarised variants are generated, consisting of: 10 L1 variants, 20 L2 variants, 30 L3 variants, 40 L4 variants, and 50 L5 variants. Each set of variants is generated with a transformation chance of: 20%, 40% and 60%. This results in 450 variant programs for each base program (13,050 variants in total), enabling the measurement of SCPDT robustness to various source code transformations with varying pervasiveness.

The number of variants generated at each transformation level is increased to offset an increasing number of potential transformations to be selected at each level. A large number of variants are generated to minimise the impact of the randomness in the data set generation method. This reduces the impact of any outliers (i.e. inconsistent decreases in similarity caused by specific transformations) and allows for the evaluation of tool robustness to transformation on average. Higher transformation chances could be applied for generated test data, however, the 3 utilised values are sufficient for this experiment.

Secondly, robustness is evaluated by measuring the average decrease in similarity of each variant compared to its base program. The average decrease in similarity is considered to represent the vulnerability of a SCPDT to transformation. Hence, a SCPDT that shows a lesser decrease in similarity is more robust than a SCPDT with a greater decrease in similarity. An initial reading of similarity is first measured for each base program by comparing it against itself with each SCPDT. The similarity of each variant against its base program is then measured. Subsequently, the decrease in similarity of each variant from the initial similarity reading is calculated. All decreases are then summed and averaged based on the combination of transformation level and transformation chance the variant was generated with. This average decrease in similarity is then considered to represent the vulnerability of a tool to the applied plagiarism-hiding transformations.

The initial similarity value is considered to be the highest possible similarity value each SCPDT can measure for a base program compared to its variants. However, most SCPDTs (BPlag included) utilise heuristics to afford fast comparison and hence may not measure a 100% initial similarity. A SCPDT will not always evaluate a program as being 100% similar to itself, hence this value offsets any errors

Fig. 5 compares the average drop in similarity as evaluated by each SCPDT for variants generated with the 5 levels of transformation. Lower average drops in similarity are considered to represent greater robustness to source code transformation. Over the three transformation chances, two trends can be observed. Firstly, as the chance of transformation increases, the average drop in similarity increases for each level of transformation. Secondly, all tools begin to show a sudden increase in the average drop in similarity for variants constructed with L3 transformations. For all tools but BPlag, this drop continues with the L4 and L5 transformations.

At the 20% transformation chance, most tools show high robustness to transformation. All but Sherlock-W and Sherlock-S fall within a tight range below 10% across all 5 levels of transformation. It can be seen that the average drop in similarity slowly increases at higher levels of transformation. However, this is not significant, attributed to the low transformation chance. At this transformation chance, there is a negligible decrease in similarity, however, BPlag is slightly more robust than all other tools.

At the 40% transformation chance, the tools begin to show greater vulnerability to the plagiarism-hiding transformations. For variants created with the L1 & L2 transformations, all tools (excluding Sherlock-S and Sherlock-W) demonstrate negligible decreases in similarity. However, starting with the application of L3 transformations, the tools suffer from a sharp and noticeable decrease in measured similarity. For the five compared SCPDTs, this decrease continues at the L4 & L5 transformations. However, for BPlag, this decrease in similarity begins to stabilise. This implies at L3, certain transformations have a large impact on the similarity of the variants as evaluated by BPlag. However, the transformations applied to the L4 & L5 variants do not impact upon BPlag.

The 60% transformation chance provides clear evidence that BPlag has greater robustness to transformation. Initially, for variants created with L1 & L2 transformations, all tools (excluding Sherlock-S and Sherlock-W) again show negligible decreases in similarity. However, for variants created with the L3 transformations, a much larger average drop in similarity is recorded for all tools. However, the greater robustness of BPlag is demonstrated against L4 & L5 transformations. Where the compared tools see a progressively greater decrease in average similarity, BPlag maintains a near-constant average drop in similarity. Technically, BPlag shows slightly greater robustness to L4 & L5 transformations, however, this can largely be explained by the sample size and is not significant.

In summary of these results, BPlag is shown to be more robust to plagiarism-hiding transformations. The five compared tools show greater vulnerability to transformation at all levels of transformation, with all transformation chances. This is opposed to BPlag that consistently ranks lowest in terms of the average drop in similarity. However, BPlag shows a sharp decrease in robustness to L3 transformations. The lack of decrease in robustness to L4 & L5 transformations implies that BPlag is robust to such transformations. This is expected, as L4 & L5 transformations do not modify the behaviour of a program. However, from the results, BPlag is vulnerable to specific L3 transformations. On further analysis, this is a result of ‘value-injecting transformations’: transformations that result in new values represented on PIDGs. Hence, a supplementary experiment is performed to investigate their impact.

The drop in similarity against L3 transformations is largely caused by two specific source transformations: ‘declare redundant constants’, and ‘assign default value to variable declaration’. Both of these transformations result in the addition of new values represented in PIDGs. As a result of this, it introduces new data nodes to the graphs that cannot be matched to the base program. Hence, it results in a decrease in similarity. To demonstrate the impact of value-injecting transformations, the results of BPlag are analysed in further depth. This is namely to identify the average drop in similarity experienced by BPlag when analysing variants created with value-injection transformations, and those without value-injecting transformations.

Table V compares the average drop in similarity of variants created with and without value-injecting transformations. It can be seen that there is a much larger average drop in similarity for variants created with value-injecting transformations, compared to those that do not contain value-injecting transformations. In all cases, for L3+ variants there is a substantial reduction in the drop of similarity for variants created without value-injecting transformations. Hence, it can be concluded that BPlag is much more robust to transformation compared to the SCPDTs; however, it does have a vulnerability to value-injecting transformations.

It should be noted that value injection is a vulnerability of all SCPDTs, and not just BPlag. Value-injection is analogous to the addition of source code to a plagiarised program. When a conventional SCPDT attempts to evaluate similarity in such a case, it cannot match the injected source code and hence results in a drop in similarity. In BPlag, value injection changes the representation used to compare programs for similarity (i.e. PIDGs). And hence, it results in a reduction of similarity.

From the results in Fig. 5, BPlag demonstrates greater robustness to plagiarism-hiding transformations. As the chance of transformation increases, BPlag demonstrates progressively greater robustness to transformation, indicated by the lower average drop in similarity. However, as identified, BPlag is vulnerable to value-injecting transformations. Without value-injecting transformations, BPlag demonstrates much greater robustness to transformation.

The simplest method of accommodating for value-injecting transformations is to simply ignore the addition of these values. They could easily be identified in the PIDG as nodes with degree 0. This effectively means the data has no relation to any other data in the program and is otherwise unused. However, this does not consider if any arbitrary node with degree 0 is placed intentionally or maliciously. Therefore, any such improvement requires further investigation.

Accuracy is a difficult aspect of a SCPDT to measure. Contrary to as the name suggests, a SCPDT does not detect plagiarism. Instead, a SCPDT identifies indications of plagiarism [7]. If two programs have a high similarity, it can be considered an indication that plagiarism may be present. However, there is no consensus as to what is considered a high similarity. Hence, this has resulted in different interpretations of what is considered an indication of plagiarism for use in SCPDT evaluations, and how to evaluate SCPDTs in general [9].

In this evaluation, the accuracy of SCPDTs is compared by the number of errors made when analysing a set of assignments. A SCPDT makes an error when it evaluates a plagiarised pair of programs as having a lower similarity score than an innocent pair of programs. Subsequently, if all similarity scores for a data set are plotted on a number line, this results in it being impossible to linearly separate those that are plagiarised and innocent into homogeneous groups. An example of this is demonstrated in Fig. 6. On top, innocent scores (labelled i) can be cleanly separated from the plagiarised scores (p). However, on bottom, the innocent scores cannot be cleanly separated from the plagiarised scores as an innocent score is more similar than a plagiarised score. Hence, an error has occurred by measuring an innocent pair with a higher similarity than a plagiarised pair.

Using this evaluation method allows for measuring accuracy by the relative value of plagiarised and innocent similarity scores. This affords for comparing SCPDTs in terms of the number of errors they make when evaluating program similarity. A SCPDT that commits many errors is considered to be less accurate than a tool that commits few errors. Hence, the purpose of this experiment will be to show that BPlag is more accurate than other SCPDTs by committing fewer errors when detecting plagiarism.

A collection of 12 sets of undergraduate assignment submissions are used to evaluate SCPDT accuracy. Each set of submissions are for an individual programming assignment for first and second-year programming courses. All assignment sets differ in code size, complexity, and the number of submissions. Table VI provides an overview of this data set.

Firstly, test data is generated with SPPlagiarise. Using generated test data allows for the construction of a data set with known plagiarised programs pairs that can be injected into an existing data set of innocent assignment submissions. Hence, this affords the accurate evaluation of SCPDT accuracy with a ground-truth data set with known types of plagiarism-hiding transformations applied. This experiment will be performed with different combinations of transformations and pervasiveness of transformation. Simulated plagiarised variants will be generated with the 5 levels of transformation, as well as with 4 increasing levels of transformation pervasiveness: 40%, 60%, 80% and 100%. Higher transformation chances are used in this experiment, as experiment 1 demonstrated that BPlag is largely robust to the 20% and 40% transformation chances. From each of the assignment collections, 5 assignment submissions are randomly selected as base programs for the generation of simulated plagiarised variant programs. For each base program: 10 L1, 10 L2, 10 L3, 10 L4 and 10 L5 variants are created for each of the 4 chances of transformation (40%, 60%, 80%, 100%). This results in the generation of 200 variants for each selected base program, totalling 12,000 variants across the 12 data sets. This will enable a comprehensive and large scale evaluation of SCPDT accuracy.

Secondly, the SCPDTs are used to evaluate the pairwise similarity scores of all programs in the base data sets, as well as the similarity of the variants to their respective base programs. This results in 12 sets of pairwise similarity scores (one for each collection of assignments), as well as 12,000 similarity scores to be injected into these data sets. Amongst the 12 collections of assignments, there are known cases of academic misconduct present. To maintain the integrity of the experiment (in that only generated variants are considered plagiarised), all scores representing the known cases of academic misconduct are removed from the data sets. This was through manual review of the similarity scores reported by each SCPDT.

Thirdly, the error counts of the SCPDTs are evaluated. The scores of the simulated plagiarised variants (for each transformation level and chance combination) are placed into their respective base data sets. The scores are then sorted, and the error count is evaluated. The error count is evaluated by identifying the best possible separation between the plagiarised and innocent scores (i.e. when the lowest number of errors occur). This results in a worst-case of 600 errors for each transformation level and transformation chance combination (i.e. the number of variants generated). Subsequently, any innocent pairs above and the score separation point, and any plagiarised scores below this point are considered errors.

Table VII lists the error counts for each SCPDT for detecting the simulated plagiarism. This is broken down into error counts at each level of transformation and chance of transformation combination, and are aggregated for all data sets for ease of review. From the results, BPlag is much more accurate in the presence of pervasive plagiarism-hiding transformations. For example, at the 40% transformation chance, BPlag has cumulatively 17 errors over the 5 levels of transformation. This is compared to the next closest tool, Sim, that has cumulatively 46 errors recorded. At the 60%, 80% and 100% transformation chances, the error counts of all tools, including BPlag, continue to increase. However, BPlag experiences the least increase in errors out of all the tools. Hence, it commits the fewest errors when detecting the simulated plagiarised variants.

All errors in this experiment result from submission pairs being incorrectly identified as plagiarised (for programs originally contained in the 12 data sets) or innocent (for the generated variants). This is caused by the similarity scores of some variant programs dropping to a point where correctly innocent scores are ranked higher. This effectively results in the similarity scores of the plagiarised and innocent program pairs becoming no longer linearly separable. Hence, there are unavoidable errors that occur when identifying the plagiarised programs. Note, the L3+ variants in this experiment were generated with value-injecting transformations. Hence, it was expected errors would occur as this is a known vulnerability of BPlag.

From the results in table VII, BPlag is shown to be the most accurate in detecting the simulated cases of plagiarism across the six compared SCPDTs. By analysing program behaviour, it is capable of consistently measuring a higher similarity between the simulated plagiarised programs, as compared to the five compared SCPDTs. Overall, this has resulted in a lower error count at all level of transformation and transformation chance combinations. While BPlag does suffer a decrease in accuracy when detecting the L3+ variants (in theory BPlag should be not affected by such transformations), this is explained by the value-injecting transformations identified in experiment 1. For L3+ transformations applied with higher transformation chances (i.e. are more pervasively applied), this appears to have a profound impact on accuracy. However, the results of BPlag at the 100% transformation chance, are more similar to the five compared tools results at the 40% or 60% transformation chances. Hence, even in the presence of such transformations, BPlag remains the most accurate tool in this experiment.

The results roughly correspond to the robustness evaluation in Fig. 5. The SCPDTs will generally see a small decrease in similarity against L1 and L2 transformations. This is reflected in this experiment by a low error rate against L1 and L2 transformations (that are largely consistent across the 4 transformation levels, excluding Sherlock-S and Sherlock-W). Furthermore, the compared tools started seeing progressively larger decreases of accuracy against the L3+ transformations. This correlates with the large average drop in similarity when exposed to L3+ transformations in Fig. 5. Hence, these results are largely consistent with experiment 1. Comparatively, BPlag is subject to a progressively smaller decrease in accuracy when exposed to L3+ transformations.

The accuracy of the compared SCPDTs can be also be compared in general from the results. If the tools are ranked by lowest cumulative errors, BPlag is consistently first. This is followed by Sim, JPlag, and Sherlock-W that shuffle between second, third and fourth place. Plaggie and Sherlock-S are consistently ranked fifth and sixth, both having significantly higher error counts than the other tools.

This experiment is controlled by two scripts written in Kotlin (a Java-like programming language). Both scripts handle the invocation of the SCPDTs on a pair of programs and monitor the time each SCPDT spends executing on each data set. This experiment utilises the data set of experiment 2 (i.e. the collection of 12 sets of undergraduate assignment submissions) while evaluating all pairwise similarity scores of the assignment collections.

The first script manages the execution of the five compared tools. Each of these tools is exposed through a Java binding (i.e. a Java class exposing the tool) that affords procedural invocation of the tool from Java code. The script enforces that at any one time: only one data set can be analysed by a single tool, and each tool can be executed at most 32 times in parallel. Subsequently, this script records the runtime of each tool invocation and calculates the average execution time per program pair.

The second script manages the invocation of and monitors the execution time of BPlag. BPlag is not implemented as a single ‘tool’, but as three separate programs as part of a pipeline (i.e. execution trace generation, PIDG construction and PIDG comparison, as per Fig. 1). In this setup, the outputs of the first stage (i.e. execution traces) and second stage (i.e. PIDGs) are serialised and stored on disk before being passed to the next stage. This script manages the execution of each stage and the intermediate storing of data. Like the compared tools, BPlag is executed in parallel, however, execution traces are extracted at most 32 times in parallel, PIDGs constructed at most 8 times in parallel, and PIDGs compared at most 8 times in parallel.

Many SCPDTs (e.g. JPlag) support the evaluation of all submissions in a data set simultaneously (i.e. comparing all submissions in a single execution of a tool). While other tools (e.g. Sherlock-S), only support evaluating a single pair of submissions. To ensure a consistent comparison, this experiment evaluates the efficiency of the SCPDTs in evaluating similarity on a per-submission-pair basis, i.e. the SCPDTs are executed once per submission pair in each data set. The total execution time for each tool is then summed, normalised and averaged to identify the average execution time per program pair. As multi-processing is utilised, it can distort the perceived efficiency of the tools. Hence, the execution times are subsequently normalised by the maximum number of parallel invocations. Therefore, the time taken by the compared tools is multiplied by 32, and the time taken by BPlag is multiplied by 32, 8, and 8 for its three stages (respectively); with both being averaged on a per-submission basis. This results in the normalised average execution times for each tool to evaluate the similarity of a single pair of programs.

The construction and comparison of PIDGs can consume large amounts of memory, hence the parallelism of the last 2 phases of BPlag is limited for stability and reliability. If the three stages are amalgamated into a single program, it can result in poor efficiency. This is caused by the JVM garbage collector constantly churning to free up heap space (as the current implementation used large quantities of memory). By implementing the three stages as separate programs, it effectively allows the approach to run without any garbage collection overhead. Hence, it avoids this garbage collection churning. However, this is at the added cost of serialising and storing data between the three stages on disk. The five compared SCPDTs do not incur a garbage collection overhead, hence this does not provide an unfair advantage for BPlag.

Table VIII presents the average execution times per program pair in each of the 12 collections of assignment submissions, normalised for concurrent execution. It can be seen that Sherlock-S is by far the most efficient tool on average. This is followed by Sim, Plaggie, JPlag, Sherlock-W, and finally, BPlag. BPlag is approximately 38 times slower than Sherlock-S and almost 2 times slower than JPlag. This is expected, as BPlag is considerably more computationally complex.

From these results, BPlag is not the most efficient SCPDT. The poorer efficiency is attributed to the comparatively more complex implementation of the approach. Being largely graph-based, it is expected that BPlag will require greater run time. The impact of greater complexity is minimised with the presented graph-matching heuristic that is designed to operate in approximately $O(n^{2})$ time. This is the same complexity of the algorithms used by JPlag and Plaggie. However, BPlag still has a much greater run time due to the sheer number of graphs extracted to represent a single program that all require pairwise comparison. Hence, BPlag is inherently more complex, requiring a greater run time.

The greater runtime does not mean BPlag is impractical to use. If only a pair of programs are analysed, the runtime would not cause a human reviewer to wait an unreasonable amount of time. If BPlag was running on the largest data set (collection 1, 170 programs), it would take approximately 24 hrs to run single-threaded. While this is, of course, a long time for the analysis of a single (large) data set, modern CPUs are multi-cored, and as such BPlag takes advantage of this. On a modern 8-core machine, BPlag would take approximately 3 hrs to execute on collection 1. Furthermore, if a more reasonably sized data set was analysed, (e.g. 100 submissions) it would take approximately 45 mins on an 8-core machine.

It must also be considered that there is greater benefit in a SCPDT being more accurate than efficient. A SCPDT is typically used once per assessment task to identify indications of plagiarism. In this single execution, a SCPDT needs to accurately identify any indications of plagiarism, especially in the presence of plagiarism-hiding transformations. This is afforded by BPlag.