Verifying Relative Safety, Accuracy, and Termination for Program Approximations

JAR 2018 screenshot


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.



  title = {Verifying Relative Safety, Accuracy, and Termination for Program Approximations},
  author = {Shaobo He and Shuvendu K. Lahiri and Zvonimir Rakamaric},
  journal = {Journal of Automated Reasoning (JAR)},
  volume = {60},
  publisher = {Springer},
  pages = {23--42},
  doi = {10.1007/s10817-017-9421-9},
  number = {1},
  month = {jan},
  year = {2018}


We thank Adrian Sampson for his feedback and for helping out with benchmark selection, and Akash Lal for assisting with Houdini. This work was supported in part by NSF awards 1255776 and 1552975, and SRC contract 2013-TJ-2426.