Di erent forms of plagiarism make fair assessment of student assignments more di cult. Source code plagiarisms pose a significant challenge especially for automated assessment systems aimed for students' programming solutions. Di erent automated assessment systems employ di erent text or source code similarity detection tools, and all of these tools have their advantages and disadvantages. In this paper we revitalize the idea of similarity detection based on string complexity and compression. We slightly adapt an existing, third party, approach, implement it and evaluate its potential on synthetically generated cases and on a small set of real student solutions. On synthetic cases we showed that average deviation (in absolute values) from the expected similarity is less than 1% (0.94%). On the real life examples of student programming solutions we compare our results with those of two established tools. The average di erence is around 18.1% and 11.6%, while the average di erence between those two tools is 10.8%. However, the results of all three tools follow the same trend. Finally, a deviation in some extent is expected as observed tools apply di erent approaches that are sensitive to other factors of similarities. Gained results additionally demonstrate open challenges in the eld.
12:2 only small superficial adjustments. They often do not change the structure of the code but only rename variables and functions or reorder statements that they know will not change the program correctness.
In this paper we describe an approach to similarity analysis based on string complexity and compression. We have chosen this method because the initial study presented in [Chen et al. 2004] showed promising results and a fresh perspective on settled practices, but the system is not available anymore for use or extension.
Other approaches to measuring similarity and detecting plagiarism were concentrated around feature comparison and program structure matching. Early attempts are usually based on computing different software metrics and comparing the results. More recent tools usually use a form of greedy string tiling to compare two streams of tokens instead a summary indicator. Both types of approaches have their strengths and weaknesses with attribute counting systems performing better in the case of very small changes, and structure comparison systems exhibiting better performance when only a part of the code is copied.
In section 2, we describe the background and motivation for our work, that lays in the previous third-party solution [Chen et al. 2004] that introduced this approach and showed perspective but is not available anymore. Description of our approach and our contribution to the previous results can be found in the section 3. Results of our contribution, demonstrated on both artificial cases and reallife student solutions, are described in the section 4, followed by conclusions and the future work in section 5.
Kolmogorov complexity K(s) of a string s [Zvonkin and Levin 1970] is the length of the shortest computer program that with no given input produces the string s as the output. It can be considered as a measure of the amount of information contained in the string s.
The conditional Kolmogorov complexity K(sjt) of two strings s and t [Zvonkin and Levin 1970] is the length of the shortest computer program that produces the string s as the output with the string t given as an input. It can be viewed as a measure of the amount of information contained in the string s that is not present in the string t.
The chain Kolmogorov complexity K(s; t) of two strings s and t [Zvonkin and Levin 1970] is the length of the shortest computer program that produces the string s followed by the string t with the information on how to separate them.
The chain rule for Kolmogorov complexity [Li et al. 2008] states that K(s; t) K(s) + K(tjs) + O(log(K(s; t))) or K(s; t) K(s) + K(tjs). In other words, the length of the shortest computer program that produces the string s followed by the string t is approximately the same as the length of the shortest computer program that produces the string s plus the length of the shortest computer program that produces the string t having the string s as input.
The algorithmic mutual information for Kolmogorov complexity IK (s; t) is defined as IK (s; t) = K(s) K(sjt) and represents the amount of information about the string s that is contained in the string t. This quantity is symmetric up to a logarithmic factor as shown in [Ga´ cs 1974] which gives us IK (s; t) IK (t; s).
Having all this in mind we get K(s; t) K(s) + K(tjs) K(t) + K(sjt) K(t; s).
If we take the absolute amount of mutual information in the strings s and t and divide it by total amount of information in both strings as in formula 1 we get a normalized measure of similarity between the strings s and t.
sim(s; t) =
IK (s; t) K(s; t) (1)
If the strings s and t are identical, this will be equal to one, if the two string are completely unrelated, the value will be zero. However sim function is not a properly defined metric function. On the other hand, the function dsim(s; t) = 1 sim(s; t) satisfies all the necessary conditions for a metric up to a logarithmic error as shown in [Li et al. 2001].
Unfortunately, Kolmogorov complexity is not computable. It is not possible to compute even the lower bound [Chaitin 1974]. However, a reasonable upper bound can be expressed as the length of the compressed representation of the string as produced by a reasonable compression algorithm. This is the approach taken in a tool called SID [Chen et al. 2004] that employs algorithmic complexity to check for similarities in source code. As approximation for this value, a special compression algorithm called TokenCompress is used. However, this tool is no longer available for usage, which is one of the motivating factors behind our work.
Our tool is also based on measuring Kolmogorov complexity, or more accurately approximating it using compression similarly to the work done in [Chen et al. 2004].
A compressed version of the string can be viewed as a program written in a language executed by the corresponding decompressor. Interpreted by the decompressor, the output of such program is the original string. Also such program tends to be the shortest as the main goal of a compression algorithm is to produce the shortest possible sequence that decompresses into the original input.
As the original compression algorithm described in [Chen et al. 2004] is not available. We have chosen GNU gzip library to approximate K(s). This library uses Lempel-Ziv coding (LZ77) [Ziv and Lempel 1977] and Huffman coding [Huffman 1952], and is considered the industry standard for general compression with a good balance of time and compression ratio. We define jsj as the length in bytes of the compressed form of the string s when compressed using the mentioned library. As stated earlier, the value jsj is a reasonable approximation for K(s). Similarly, K(s; t) is approximated by jstj and K(sjt) is approximated using the formula K(sjt) K(t; s) K(t) based on the chain rule for Kolmogorov complexity.
Having this in mind, the final similarity is calculated using the formula 2.
sim(s; t) = jsj + jtj jtsj
jstj p =
2sim(s; t) 1 + sim(s; t)
In order to calculate the percentage of the common information we have to further interpret this similarity metric, as was done in [Chen et al. 2004]. If we assume that the two strings s and t are approximately the same length as is common among student solutions, then sim(s; t) = 2 p p where p is the percentage of the information common in both strings [Chen et al. 2002]. This gives us the formula 3 to calculate p.
However, when students try to hide similarities, one of the methods they employ is adding redundant or unused code thus increasing the total length of the copy. In such cases, when compared with each other, the copy and the original can have considerable length difference.
To combat this we have proposed two new measures in addition to the one already described in [Chen et al. 2004]. These measures represent the percentage of string s that is present in t and vice versa, and are given with formulas 4 and 5. (2) (3)
sims(s; t) = jsj + jtj jtsj jsj (4) simt(s; t) = jsj + jtj jtsj (5) jtj
These two measures are not always symmetrical. For example, if we have a string s representing the source code form one student solution, and string t generated from s by adding two times more unused code, then sim(s; t) will not give a strong indication about possible plagiarism as the percentage will be around 50%. However, sims(s; t) will give the percentage around 100% immediately stating that one string is present in the other in its entirety. Similar situation can be observed when a part of one solution is copied from the other without adding or modifying it much.
To explore the viability of our proposed approach, we tested the performance of our tool both in isolation and in comparison with two other similarity detection tools.
In the first step we tested our tool using synthetic benchmarks. We have performed 22 separate tests by supplying two randomly generated strings as input to our tool and recording the calculated similarities. Each test was repeated 1000 times and the average similarity was recorded. In each test we generated three sequences of random data of predefined lengths for that test: unique content for the first input string, unique content for the second input string and content common for both strings. The two inputs supplied to the tool were generated by combining the content from the appropriate random sequences.
The results of the tests are given in Table I. The value unq(s) represents the total amount of data unique to the string s, while unq(t) represent the same for the string t. The value cmn(s; t) represents the total amount of data common in both strings. The next two groups of values represent the expected and calculated percentages of similarity, while the last three columns contain percentage of difference between expected and calculated values. The value p represent the percentage of data common to both strings. The value ps represent the percentage of data in the string s that is also present in the string t. The value pt represent the percentage of data in the string t that is also present in the string s.
As can be seen from the data, the similarity calculated by our tool is very close to the real values. More precisely, values of all three functions differ from the expected value within an interval between 0.04% and 2.69%. It can be observed that the calculated values differ from the expected ones on average 0.94% for both strings, 1.1% for the amount of data s has in common with t, and 0.85% for the amount of data t has in common with s, while standard deviation of differences is 0.59%, 0.69% and 0.57% respectively. The retrieved values are consistently slightly lower because of the imperfections of the compression algorithm used to approximate the Kolmogorov complexity. With a compression algorithm closer to the perfect compression these values would probably be closer to the expected.
In the second step we have compared the results from our tool with SIM [Grune 2006] and JPlag [Prechelt et al. 2002]. SIM tests lexical similarity in natural language texts and in programs written in various programming languages. Its main purpose is to detect duplicated code in large software projects and to detect plagiarism between different software projects. JPlag is a system that finds similarities among multiple sets of source code files. It is aimed at detecting software plagiarism and as such was used by expert witnesses in several intellectual property cases.
As sample data, we have selected a few student solutions to practical exercises. All solutions belong to a single group of second year students working independently on the same assignment. The students were not sharing code among them. Along with student solutions one produced by us was added. We have randomly chosen one of the student solutions and changed all variable names without changing the rest of the code. This was done to illustrate a common way students try to mask plagiarism.
The results of this test are illustrated by charts in figures 1 and 2. From the starting 14 solutions, all possible pairs were generated. Figure 1 shows 182 points in total representing each pair twice, once for each component in the pair. For each of these components, the figure shows the percentage of the code that is also present in the other component of the pair, as reported by all three tools. Figure 2 contains the similarity values reported for the pair as a whole. As SIM does not report this measure, it is not included in the graph on this figure.
The results from our tool are comparable with the results from SIM and JPlag. As can be seen from the charts, percentages are roughly consistent within a margin, both for a single solution and for the whole pair.
There are a few instances in which each of the tools give a slightly different result from the others. The discrepancies between our tool and each of the other two are roughly the same as differences between them and all three tools are showing the same trend. Anyhow, in no situation one of the tools gives a strong indication of similarity while the other two are indicating the opposite.
However, our tool usually gives a slightly higher percentage of similarity. This is rooted in two fundamental reasons. Firstly, both SIM and JPlag have a concept of a minimum run length. This parameter dictates how many consecutive matches are needed to consider a part of the program code a potential copy. Our tool does not have such restriction stated explicitly. However, implicitly as a feature of standard compression algorithms, a match that is too small is disregarded on the basis that its compressed representation is longer that the uncompressed.
Secondly, our tool is basing the comparison on the level of characters, while SIM and JPlag are comparing token streams. This results in our tool detecting finer similarities that do not span whole tokens, like for example, between Integer, LongInteger and ShortInteger or by capturing a part of a token in front or behind the group detected by other tools.
This does not mean that either of the approaches is better that the other. It depends on the particular case and warrants further investigation.
In the area of automatic assessment of students’ programming solutions, one of the open challenges is plagiarism detection. While there are numerous tools for source code similarity analysis and for code clone detection, there is still no tool fully suitable to be used for these purposes. Some of the factors that affect the usefulness of these tools are the applied approach and the used similarity algorithm. In this paper we explore possibilities of employing string complexity and compression in source code similarity measurement. We evaluate gained results on synthetic examples in comparison with the expected values based on the background theory, as well as on real-life student solutions in comparison with alternative tools.
In comparison with the expected values, we gain slightly lower similarity values. The cause of this is the imperfection of the chosen compression algorithm, and the fact that it implements lossless compression which considers the equality of string sequences and not actually their similarity. Hence, in the future work we can experiment with alternative algorithms that are lossy and sacrifice a little accuracy to, for example, better capture attempts at renaming variables.
Results obtained from our tool, when compared to the similarity values acquired from competitive tools, show the same general trend, although our calculated similarity values tend to be slightly higher. The differences are caused by different observation unit employed (character- versus token-based observation). Experimentation in this direction may bring higher precision, but also lower detection capabilities.
Also, one of the important features in similarity analysis is the consideration of the base code, as student assignments usually include some predefined elements for the future solution. This is another significant direction for future work.