Verifying Relative Safety, Accuracy, and Termination for Program Approximations

2016_OOPSLA_sdbgr screenshot

Abstract

Approximate computing is an emerging area for trading off the accuracy of an application for improved performance, lower energy costs, and tolerance to unreliable hardware. However, developers must ensure that the leveraged approximations do not introduce significant, intolerable divergence from the reference implementation, as specified by several established robustness criteria. In this work, we show the application of automated differential verification towards verifying relative safety, accuracy, and termination criteria for a class of program approximations. We use mutual summaries to express relative specifications for approximations, and SMT-based invariant inference to automate the verification of such specifications. We perform a detailed feasibility study showing promise of applying automated verification to the domain of approximate computing in a cost-effective manner.

Citation

Shaobo He, Shuvendu K. Lahiri, Zvonimir Rakamaric
Verifying Relative Safety, Accuracy, and Termination for Program Approximations
Proceedings of the 8th NASA Formal Methods Symposium (NFM), 9690: 237--254, 2016.

BibTeX

@inproceedings{2016_NFM_hlr,
  title = {Verifying Relative Safety, Accuracy, and Termination for Program Approximations},
  author = {Shaobo He and Shuvendu K. Lahiri and Zvonimir Rakamaric},
  booktitle = {Proceedings of the 8th NASA Formal Methods Symposium (NFM)},
  editor = {Sanjai Rayadurgam and Oksana Tkachuk},
  publisher = {Springer},
  volume = {9690},
  pages = {237--254},
  year = {2016}
}