In this paper we describe a new general plagiarism detection method, that we used in our winning entry to the 1st International Competition on Plagiarism Detection, the external plagiarism detection task, which assumes the source documents are available. In the first phase of our method, a matrix of kernel values is computed, which gives a similarity value based on n-grams between each source and each suspicious document. In the second phase, each promising pair is further investigated, in order to extract the precise positions and lengths of the subtexts that have been copied and maybe obfuscated - using encoplot, a novel linear time pairwise sequence matching technique. We solved the significant computational challenges arising from having to compare millions of document pairs by using a library developed by our group mainly for use in network security tools. The performance achieved is comparing more than 49 million pairs of documents in 12 hours on a single computer. The results in the challenge were very good, we outperformed all other methods.
Many methods have been developed for
plagiarism detection, especially for the
external plagiarism analysis, which consists in
finding passages in the suspicious documents
which have been plagiarized and the
corresponding text passages in the source
documents. Almost all these methods handle
the text at word level. Various
comparison units have been employed in
plagiarism detection methods. Entire documents
are compared in
Using words is natural in text analysis
tasks like text categorization (by topic),
authorship identification and plagiarism
detection. Perharps surprisingly, recent results
proved that methods that handle the text at
character level can also be very effective in
text analysis tasks. In
For plagiarism detection, the only
approach that handles the text at character
level that we are aware of is in
There is a strong connection between the
research in NLP and the research in computer
network security. In recent years, network
security research started to approach the
problem of detecting automatically unknown
attacks as soon as they reach the targeted
system. These attacks may follow the syntax
but try to exploit the semantics of the
network communication between the client and
the server applications, in order to gain
access over the attacked computer or at least
to prevent it from working normally. The
communication process defined by the
application layer protocols – e.g. HTTP, FTP,
RPC or IMAP – can also be considered as a
text-based communication in an artificial
language. The idea of payload analysis, which
treats the data as sequences of bytes has
been explored in detail
Graphics methods in comparing sequences
have been used in many fields, mostly
under the name dotplot – see
In what follows, the dataset specifics and
the time performance figures refer to the
dataset of the 1st International
Competition on Plagiarism Detection, external
plagiarism detection task
Our approach consists of two main phases. In the first phase, a matrix of string kernel values is computed, which gives a similarity value between each source and each suspicious document. Then, for each source, the possible “destinations” (suspicious documents) are ranked based on their similarity level with the current source, in decreasing order. In the second phase, each promising pair is further investigated, in order to extract the precise positions and lengths of the subtexts that have been copied and maybe obfuscated by the random plagiarist. In the end we do a supplementary filtering that increases the precision with the price of decreasing the recall.
Based on the work of
|φng(x)−φng(y)| ng∈An φng(x)+φng(y) kernel function k(x, y) linear kernel RBF kernel exp(− ng∈An φng(x) · φng(y) ng∈An ||φng(x)−φng(y)||2 ) 2σ2 work security research group. It has been developed mainly for being used in building real-time network analysis tools at packet level, as part of network intrusion detection and prevention systems. It can map byte sequences to a vectorial n-gram representation, such that the similarity between two byte sequences can be expressed in terms of distance and kernel functions on those representations. The n-gram extraction set of feasible byte sequences is given by An = Σn, where Σ is the alphabet (in our case the whole ASCII–8 set). The n-gram embedding function φ for a byte sequence x is then defined as φ(x) = (φng(x))ng∈An with φng(x) = emb(x, ng), where the dimension of the vector φ(x) is |An|. The function emb(x, ng) returns either the frequency, the count or the presence bit for a n-gram ng in x. With the embedding function φ fixed, one can compute a pairwise similarity value for the vectorial representations of two byte sequences. Table 1 presents a selection of the implemented distances and similarity measures that we could have used (where x and y are arbitrary byte sequences).
Experiments with a very small subset of
only 5 documents and our previous
experience in string kernels led us to use the linear
kernel over a representation where every
ngram present is marked by 1 and every other
is marked by 0 (ignoring thus the frequencies
of the n-grams). The kernel was normalized,
such as K(x, x) = 1 for any string x. For the
length of the n-grams we used 16 characters.
Although in our estimations 18 should have
been better (closer to three times the average
word length plus two separators), the
speedup of the software used can only be obtained
up to n-grams of length 16, see below and
Appendix 1 for details. Using windows of two
to three words in plagiarism detection was
found to be the best choice by
The computation of a matrix of kernel values with sizes as large as 7000 is computationally intensive. There are more than 49 million pairs of documents for which the kernel value has to be computed, in each of the two datasets, the development and the competition corpus, accounting for a total of more than 98 million pairs to consider. libmindy has had already a tool for building a (symmetric) kernel matrix for a set of documents. We extended this tool for being able to handle asymmetric matrices of kernel values, where the kernel values are computed for each x ∈ X and y ∈ Y , where X and Y are two independent finite sets of files, not necessarily having the same cardinal. While the new tool could in principle perform the task fast enough, it would have needed an amount of RAM of about 400 GB for a kernel based on length 16 n-grams. To avoid this issue, we partitioned the matrix of kernel values in blocks of sizes up to 1000x1000 (1 million pairs in most blocks), which required only 8 to 10 GB of RAM for processing. Those 64 blocks per dataset we processed one after the other, but the processing of each block was fully parallelized on the 8 cores of the machine, as a result of internally distributing the tasks by the means of OpenMP programming. Processing a full dataset took 12 hours on the machine we used (Dell Precision T7400). Although we had access to a cluster, it offered only a 32-bit environment. This would have slowed the whole processing by a factor that would almost completely eliminated the advantage of having 8 to 12 times more computing cores, and this is why we decided to use a single multi-core computer. 2.2
If the total processing for one pair of documents (up to book length level) would only take one second, this would lead to a total computation time of more than three years! Even by successfully parallelizing this task and dividing the time by hopefully 8 (the number of computing cores), the time needed would have been more than 4 months. It was obvious that even with the matrix of kernel values computed, there is too much work in comparing the documents in each pair. Pruning was seen from the start as a requirement, the question was what effect will it have on limiting the performance that can be achieved. We have considered ranking the pairs such that the ones with most chances of corresponding to plagiarism come first. Ranking on the absolute values of the kernel proved to work worst. Ranking for each source the suspicious documents proved to provide a consistent 10% advantage over ranking for each suspicious document the sources. Therefore, given also the values that can be seen in the Figure 1, we decided to limit our effort to the first 51 most promising suspicious documents for each given source. 2.3
With the maximum effort down to an estimate of about 100 hours, assuming spending in average a second per exhaustive document comparison (with the hope of reducing it to 12 hours by multicore parallelism), we proceeded to search for a way to identify what the documents have in common, if anything. Essential to this was the visualization of the coincidence pattern of n-grams between two documents. This is a scatter plot of a sublist of the positions where both texts have the same n-gram. We call this plot encoplot. Plots computed for pairs in the development corpus can be seen in Figures 2 and 3. All these plots use documents in the development dataset.
Related ideas (the “dotplot” graphs) exist about visualizing the n-grams that two texts (or sequences) share. The problem with those
2 3 4 5 6 Source Document Position 7 is that the number of pairs can be quadratic in the size of the documents. For megabytes long texts, this can easily become computationally intractable. We solve this issue by limiting ourselves to a sublist that is guaranteed to be no longer than the shortest of the documents, and can be computed in linear time. The precise procedure we employed starts by sorting virtually the sets of n-grams for both documents to be compared. Then these ordered sets of n-grams are compared with a procedure that is derived from the procedure from merging two sorted lists. Every time the smallest elements of the two lists differ, the smallest of them is dropped, without producing any output. Every time the smallest elements of the lists are equal, the pair of positions on which this identical n-gram occurs is being collected by outputting it to the standard output. Code for this core procedure is given in Appendix 1. Please note that encoplot pairs the first instance of an n-gram in one document with the first instance of the same in the other document, the second one with the second one and so on – as opposed to the dotplot, wich pairs each instance with each instance. 2.4
Once the encoplot data (the list of pairs of indexes) is obtained, it is sorted by the value of the first index in each pair, which corresponds to the position in source of the common n-gram. From this list a local “contiguity” score is derived by computing whether there is simultaneously a small jump on both indexes (sum of absolute jumps less than 4) when going from a pair to the next pair, followed by a smoothing by a convolution with a constant vector of length 16. The contiguity score for an encoplot is displayed in red in Figures 2 and 2. Then a Monte Carlo optimization procedure is called, not more than 30 times for each document pair, which in 10 attempts tries to find the largest group from the current encoplot data. The start of the group is decided randomly with uniform distribution over the list of available pairs, then the group is extended to left and right such that the average contiguity score stays above 0.5 and there are no jumps (skipped portions) longer than 512 in any 16 steps. After a group is obtained, it is checked to have an average contiguity score of over 0.75 and a length of at least 256 characters. If not, it is rejected as insignificant. If kept, it is projected to the dimension of the indexes that correspond to the suspicious document, and only the compact core of it is preserved. The compact core is obtained by sorting on the suspicious document axis and eliminating the outliers by starting from the group center and extending it to left and right while the skips are less than 256 positions. What remains is projected back onto the source document axis, obtaining thus an estimate of the indexes whose convex hull define the two subtexts corresponding to each other. This candidate of a plagiarism instance is checked once again, this time for a final length of at least 256, for not having shrinked to less than half with respect to the initial group length and for the two subtexts not having sizes too different (the absolute difference more than half of the mean of the two lengths). This subset of the encoplot data is removed, the plagiarism instance is outputted if all tests succeeded, and the procedure is repeated in the search for more groups. If the group found fails to satisfy the checks, it is deemed as a failure. At three consecutive failures the search is abandoned and the treatment of the pair of documents is considered completed. This decision may be risky, but accelerates substantially this phase, as on very complicated document pairs it can take minutes to completely examine an involved pair. On the other hand, for the actually unrelated documents this ends the investigation rapidly. Technically, we have accelerated this processing phase even more by running simultaneously up to 10 detailed examinations of document pairs at a time, trying to balance the processing power required and the disk latency. 3
We combined the best F-measure – the harmonic mean of precision and recall – 0.6976 (the next competitor had 0.6192) with the best granularity – lack of fragmentation in detection of the plagiated passages – 1.0027 (the next best value was 1.0164), winning thus the competition. 4
The first question is whether our choice to
compare the documents in pairs was optimal.
Indexing based methods could be faster, by
eliminating the need for exhaustive pairwise
comparison of documents in a large corpus.
They function by first indexing the collection
of source documents and then searching for
parts of the suspicious documents in the
index, as the system MOSS
A second question of interest is whether our values for the hyperparameters of the method are optimal for this dataset. The answer is probably no, but maybe not far from that. They have been chosen by educated guess guided by the exploratory data analysis, as opposed to blindly optimizing a crossvalidation towards the best (over)fitting.
The third interesting issue is the claim
of some experts that only the humans can
have very good results at spotting plagiarism
Given the very good results obtained by our method it is worth asking – and further investigating – whether using character n-grams offers any advantage over using word n-grams. First, let us note that our method uses n-grams of 16 characters which in average2 correspond to word trigrams (the standard approach in plagiarism detection). It may seem that (on average) the same information is brought by 16 characters n-grams and word trigrams. What differentiates the two types of n-grams is in our opinion the fact that character n-grams favor long words over short ones, and when people copy text they do that for the content words of the copied text that tend to be longer than the functional words (stop words) which are short. For example: a common syntagmatic expression3 like ”as far as” will contribute with one word trigram, but with none character 16gram. On the other hand, a sequence of content words (worth being copied) like ”educated guess guided” will contribute again with only one word trigram, but with 6 character 16-grams.
Another item to discuss is how to balance precision and recall in automatic plagiarism detection systems. Given that a human is in many cases the final link in the chain that leads to the proof of plagiarism, the effort of that human must be spared as much as possible. The accuse of plagiarism is so strong, that it needs strong evidence. Both these aspects recommend to balance the precision and recall towards a high precision, even at 2The average word length in the corpus is 5.2 3Frequently and systematically co-occurring lexical items. the expense of lowering the recall. This is how we tuned our system’s parameters, including but not limited to the last checking phase. Of course, accurate comparison of systems should take into account the entire precision-recall curve. By plotting on the same graph these curves for more systems, one could easily see where is the best performance region for each system and whether or not one of the systems is overall better than another system.
Related to the maximum achievable precision while keeping a fair recall is the issue of the documents independence and of the automatic plagiarism. The dataset contains plagiarism built automatically and randomly and only these borrowings between the source documents and the suspicious documents had to be found. But the documents were not independent enough: there are pairs of documents with the same or almost the same content, such as independent translations of “One Thousand and One Night” or several Bible editions, authors doing heavy reuse from their previous works (the so-called self-plagiarism). These are interesting in two ways: they are better examples of what the human plagiarism is, so spotting those as related is very good. On the other hand, this can be seen as unintended (by the organizers) plagiarism, so any such pair reported will actually lower the precision score.
A very interesting issue is the asymmetry of the ranking quality. Why is it 10% better to rank all suspicious documents for any fixed source instead of ranking all possible sources for every fixed suspicious document, as clearly seen in Figure 1? A possible source of this asymmetry is that while it was guaranteed for each suspicious document that the areas plagiated do not overlap, this was not the case for the source documents, where the areas plagiated could overlap. This asymmetry deserves more investigation, being one of the few glints of hope so far to tackling what could be the biggest open problem in automatic plagiarism detection, that is determining the direction of plagiarism in a pair of documents – being able to indicate with confidence which is the copy and which is the original.
To conclude, by combining advanced software engineering and effort-sparing heuristics tuned using the novel visualization technique encoplot, we have been able to achieve the top placement in the final results, proving that the interaction of NLP researchers with networks security researchers can lead to highperformance NLP systems.
We thank Dr. Andreas Ziehe and the anonymous reviewers for the thorough review of our paper and for the useful suggestions.
This appendix provides the listing of the implementation of the encoplot algorithm. At its core is a very fast implementation of the radix sort algorithm for virtually sorting the n-grams in a text without swapping any memory blocks. It is a specialization of the general radix sort algorithm. The key part is avoiding to recompute the frequencies at each step in the radix sort algorithm, and relying instead on updating those incrementally. Another key technical aspect is the use of the 128 bit unsigned integer type uint128 t, possible with the gcc compiler on certain platforms, which allows for very good speeds up to n-grams of length 16, on 64bit architectures, such as the common x86-64. The main code uses this virtual sorting of the n-grams sets to compute the encoplot data of two given files, a central part of our plagiarism detection method, as explained above. // computes the encoplot data of a p a i r of f i l e s #i n c l u d e ” s t d i o . h” #i n c l u d e ” s t d l i b . h” #i n c l u d e ” s t r i n g . h” #i n c l u d e <sys / types . h> #i n c l u d e <sys / s t a t . h> #i n c l u d e <unistd . h> typedef u i n t 1 2 8 t tngram ; //CrG r s o r t #d e f i n e f r (x , y ) f o r ( i n t x=0;x<y ; x++) i n t ∗ index rsort ngrams (
unsigned char ∗x , i n t l , i n t DEPTH){ i n t NN=l−DEPTH+1; i f (NN>0){ unsigned char ∗ pin=x+NN; unsigned char ∗pout=x ; i n t ∗ ix =( i n t ∗) malloc (NN∗ s i z e o f ( i n t ) ) ; i n t ∗ox=( i n t ∗) malloc (NN∗ s i z e o f ( i n t ) ) ; const i n t RANGE=256; i n t counters [RANGE] ; i n t s t a r t p o s [RANGE] ; f r ( i ,NN) ix [ i ]= i ; // radix sort , the input i s x , // the output rank i s ix f r (k ,RANGE) counters [ k ]=0; f r ( i ,NN) counters [ ∗ ( x+i )]++; f r ( j ,DEPTH){ i n t o f s=j ;// low endian i n t sp =0; f r (k ,RANGE){ s t a r t p o s [ k]= sp ;
sp+=counters [ k ] ; } f r ( i ,NN){ unsigned char c=x [ o f s+ix [ i ] ] ;
ox [ s t a r t p o s [ c]++]= ix [ i ] ; } memcpy( ix , ox ,NN∗ s i z e o f ( ix [ 0 ] ) ) ; // update counters counters [i∗f p(jo<uDt+EP+T]−H−−1;c){ounters [ ∗ pin++]++;}} #f rdeeef i(noex ) M;rAeXtBuUrFnSIZix 8;}0}00123 unsigned char f i l e 1 [MAXBUFSIZ ] ; unsigned char f i l e 2 [MAXBUFSIZ ] ; i n t l1 , l 2 ; i n l i n e tngram readat ( const unsigned char ∗buf , i n t poz ){ return ∗( tngram ∗)( buf+poz ) ; } i n t main ( i n t argc , char ∗∗ argv ){ i n t depth=s i z e o f ( tngram ) ; FILE ∗ f1=fopen ( argv [ 1 ] , ” rb ” ) ; l 1=f r e a d ( f i l e 1 , 1 ,MAXBUFSIZ, f1 ) ; f c l o s e ( f1 ) ; FILE ∗ f2=fopen ( argv [ 2 ] , ” rb ” ) ; l 2=f r e a d ( f i l e 2 , 1 ,MAXBUFSIZ, f2 ) ; f c l o s e ( f2 ) ; // index the ngrams i n t ∗ ix1=in dex rsort ngr ams ( f i l e 1 , l1 , depth ) ; i n t ∗ ix2=in dex rsort ngr ams ( f i l e 2 , l2 , depth ) ; i n t i 1 =0; i n t i 2 =0;// merge tngram s1=readat ( f i l e 1 , ix1 [ i 1 ] ) ; tngram s2=readat ( f i l e 2 , ix2 [ i 2 ] ) ; l1 −=(depth −1); l2 −=(depth −1); while ( i1<l 1 && i2<l 2 ){ i f ( s1==s2 ){ p r i n t f (”%d %d\n” , ix1 [ i 1 ] , ix2 [ i 2 ] ) ; i 1 ++; i f ( i1<l 1 ) s1=readat ( f i l e 1 , ix1 [ i 1 ] ) ; i 2 ++; i f ( i2<l 2 ) s2=readat ( f i l e 2 , ix2 [ i 2 ] ) ; } e l s e i f ( s1<s2 ){
i 1 ++; i f ( i1<l 1 ) s1=readat ( f i l e 1 , ix1 [ i 1 ] ) ; } e l s e i f ( s2<s1 ){
i 2 ++; i f ( i2<l 2 ) s2=readat ( f i l e 2 , ix2 [ i 2 ] ) ; } } f r e e ( ix2 ) ; f r e e ( ix1 ) ; return 0;}