We address the problem of computing semantic differences between a program and a patched version of the program. Our goal is to obtain a precise characterization of the difference between program versions, or establish their equivalence. We focus on infinite-state numerical programs, and use abstract interpretation to compute an over-approximation of program differences.
Computing differences and establishing equivalence under abstraction requires abstracting relationships between variables in the two programs. Towards that end, we use a correlating abstract domain to compute a sound approximation of these relationships which captures semantic difference. This approximation can be computed over any interleaving of the two programs. However, the choice of interleaving can significantly affect precision. We present a speculative search algorithm that aims to find an interleaving of the two programs with minimal abstract semantic difference. This method is unique as it allows the analysis to dynamically alternate between several interleavings.
We have implemented our approach and applied it to real-world examples including patches from Git, GNU Coreutils, as well as a few handpicked patches from the Linux kernel and the Mozilla Firefox web browser. Our evaluation shows that we compute precise approximations of semantic differences, and report few false differences.
Fri 24 Oct
|13:30 - 13:52|
Henrique Nazaré SantosUFMG, Izabela Karennina Travizani MaffraUFMG, Willer Fernandes SantosUFMG, Leonardo Barbosa OliveiraUFMG, Laure GonnordUniversity of Lyon & LIP, France, Fernando Magno Quintão PereiraUFMGLink to publication
|13:52 - 14:15|
|Link to publication|
|14:15 - 14:37|
Qirun ZhangThe Hong Kong University of Science and Technology, Xiao XiaoThe Hong Kong University of Science and Technology, Charles ZhangHong Kong University of Science and Technology, Hao YuanBOPU Technologies, Zhendong SuUniversity of California, DavisLink to publication
|14:37 - 15:00|
Lucas BrutschyETH Zurich, Pietro FerraraIBM Thomas J. Watson Research Center, Peter MüllerETH ZurichLink to publication