Applying Code Change Patterns during Analysis of Program Equivalence

The goal of this thesis is to propose a static analysis method for recognition of code change patterns describing recurrent changes between different versions of low-level code. The thesis proposes an encoding method of patterns, which uses the LLVM intermediate representation, and a pattern matching algorithm based on gradual comparison of instructions according to their control flow. The proposed analysis has been implemented as an extension of DiffKemp, a tool for analysing semantic differences between versions of large C projects. Results of experiments conducted on three pairs of past versions of the Linux kernel show that the extension is able to eliminate a substantial amount of false-positive or generally undesirable differences from the output of DiffKemp, which would otherwise require manual inspection.