Incremental Upgrade Checking by Means of Interpolation-based Function Summaries

Abstract:

During its evolution, a typical software/hardware design undergoes a myriad of small changes. However, it is extremely costly to verify each new version from scratch. As a remedy to this problem, we propose to use function summaries to enable incremental verification of the evolving systems. During the evolution, our approach maintains function summaries derived using Craig's interpolation. For each new version, these summaries are used to perform a local incremental check. Benefit of this approach is that the cost of the check depends on the extent of the change between the two versions and can be performed cheaply for incremental changes without resorting to re-verification of the entire system. Our implementation and experimentation in the context of the bounded model checking for C confirms that incremental changes can be verified efficiently for different classes of industrial programs.

Notes:

• BibTex

@inproceedings { Ondrej Sery; Gri,
	title = {Incremental Upgrade Checking by Means of Interpolation-based Function Summaries},
	booktitle = {Twelfth International Conference on Formal Methods in Computer-Aided Design (FMCAD)},
	year = {2012},
	note = {To appear at the conference. The pdf-version is not final.},
	address = {Cambridge, UK},
	URL = {publications/upgrade-checking-fmcad},
	author = {Ondrej Sery and  Grigory Fedyukovich and  Natasha Sharygina}
}