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 OctDisplayed time zone: Tijuana, Baja California change
13:30 - 15:00
|Validation of Memory Accesses Through Symbolic Analyses|
Henrique Nazaré Santos UFMG, Izabela Karennina Travizani Maffra UFMG, Willer Fernandes Santos UFMG, Leonardo Barbosa Oliveira UFMG, Laure Gonnord University of Lyon & LIP, France, Fernando Magno Quintão Pereira UFMGLink to publication
|Abstract Semantic Differencing via Speculative Correlation|
OOPSLALink to publication
|Efficient Subcubic Alias Analysis for C|
Qirun Zhang The Hong Kong University of Science and Technology, A: Xiao Xiao The Hong Kong University of Science and Technology, A: Charles Zhang Hong Kong University of Science and Technology, A: Hao Yuan BOPU Technologies, A: Zhendong Su University of California, DavisLink to publication
|Static Analysis for Independent App Developers|
Lucas Brutschy ETH Zurich, Pietro Ferrara IBM Thomas J. Watson Research Center, Peter Müller ETH ZurichLink to publication