Software Fingerprinting

A new cross-compression metric, based on Lempel-Ziv-Welch compression, is suggested as a method for detecting programming style. In essence, the process of compression of one program is used to build a a string table which is then used to compress the text of another program. The resulting compression ratio defines a measure of coherency between the two programs. In using the metric, we define the stylistic separation condition, and show how it can be used to automatically assign a code fragment to the program it belongs. This condition is demonstrated to hold in an ensemble of 21 large programs, spanning over a million lines of code. We also develop a new linear-time compression algorithm which compresses programs based on their syntactical structure. This algorithm is insensitive to superficial similarities, such as in identifier names, and is competitive with standard compressors. Other than its applications in achieving better compression rates of program source, we use this new algorithm to measure similarity between programs. The stylistic separation condition holds for this algorithm as well.