SPLASH 2014
Mon 20 - Fri 24 October 2014 Portland, Oregon, United States
Fri 24 Oct 2014 13:52 - 14:15 at Salon E - Static Analysis Chair(s): Anders Møller

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

oopsla2014
13:30 - 15:00: OOPSLA - Static Analysis at Salon E
Chair(s): Anders MøllerAarhus University
oopsla2014141415020000013:30 - 13:52
Talk
Link to publication
oopsla2014141415155000013:52 - 14:15
Talk
Nimrod PartushTechnion, Eran YahavTechnion
Link to publication
oopsla2014141415290000014:15 - 14:37
Talk
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, Davis
Link to publication
oopsla2014141415425000014:37 - 15:00
Talk
Lucas BrutschyETH Zurich, Pietro FerraraIBM Thomas J. Watson Research Center, Peter MüllerETH Zurich
Link to publication