Since I am currently working on software for the automated testing of competitive programming problems in C#, I had the idea of building a module that checks two C# files for identical code, so that I can catch the people who copy each other's work while using my system. Of course, to catch them, every submission has to be compared with every other submission. That is the easy part. The hard part is the comparison itself. Here I will try to describe the approaches I found and how I arrived at a solution. ;)
The hard solution
The most reliable way to compare algorithms and code for sameness is to analyse the program's code-flow graph and look for matches using graph isomorphism algorithms. Put simply, this means looking at which instructions every possible execution of the program passes through, and checking whether those possible instruction sequences are the same for the two programs. Analysing the code flow of a program is, however, a complex task and takes a fair amount of time. There are easier options that take less effort and still give reasonably good results.
The easy solution
The first and easiest approach is simply to compare the text of the code for some degree of sameness. That means that if there are several lines with identical code, the program will notice them and consider the code identical. This sounds easy and convenient, but people who copy are clever. Most often they will rename variables, or change the order in which the code executes, change constants and literals, swap the order of operators and so on. So a plain text comparison will not catch them in the large majority of cases.
The Simian tool
I dug around on the internet and found several small programs - some built to check text for sameness, others to check code. Unfortunately most of the good ones are paid. Of the free programs, the one that impressed me most is Simian. It is free for the purposes of free and open-source software. It does a good job of checking for identical C# code, but it has some quite serious gaps, such as ignoring variable names in C# code. Simian can also compare plain text.
My solution
The best way of catching cheaters that occurred to me, and the one that looks considerably more reliable, is to analyse the code of the application after it has been through the compiler. To do that, each of the files being checked is first compiled with the C# compiler (csc.exe). Once the compiler has produced an executable, that file is decompiled to IL code. This is done with ILDASM (ildasm.exe), which is part of the C# SDK. This program turns any compiled .NET assembly from an executable into MSIL code. During compilation and the subsequent decompilation, the names of private variables are lost. On top of that, some of the tricks lose their effect - swapping the order of certain operators, replacing a for loop with a while loop, adding preprocessor directives, adding pointless comments and so on. Once we have the MSIL code, we can count on a far greater chance of catching the copies when we compare it with other MSIL code. This is where Simian comes into play again, only run against the IL files rather than the C# code. Here is what the result looks like:
Conclusion
From the tests I ran, the last approach - the one based on analysing the IL code - turned out to be quite good. On identical code (with renamed variables, a while loop swapped for its for equivalent, one or two operators moved around, added comments and pointless preprocessor directives) Simian found 142 identical lines out of 176 analysed, which is very good considering the effort I put into making the code look different. Of course, a combination of C# analysis and IL analysis can be used, but it seems to me that analysing the IL gives good enough results on its own. The analysis takes 0.227 seconds on a good processor, and the compilation plus decompilation also takes some time. It is not very fast, but it is worth it.
If you have any questions, Google them with Bing :)