Customizing k-Gram Based Birthmark through Partial Matching in Detecting Software Thefts

The k-gram based birthmark is a method for comparing binary programs to find similar software, such as software thefts or common modules. The method directly compares opcode sequences, so it is susceptible to program changes, such as optimization or obfuscation. In this paper, we present a method for customizing the k-gram birthmark to allow slight changes of programs by employing partial matching of k-grams. We find the customized k-gram birthmark in Java application environments, and evaluate the customized birthmark in real-world Java applications. In the experimental results, we show that customization of k-gram birthmark improves the credibility and resilience in comparing binary programs.