×

Computer-assisted verification of four interval arithmetic operators. (English) Zbl 1434.65063

Summary: Interval arithmetic libraries provide the four elementary arithmetic operators for operand intervals bounded by floating-point numbers. Actual implementations need to make a large case analysis that considers, e.g., magnitude relations between all pairs of argument bounds, positional relations between the arguments and zero, and handling of the special values, \( \pm \infty\) and NaN. Their correctness is not obvious as they are implemented by human hands, which comes to be critical for the reliability. This work provides a mechanically-verified interval arithmetic library. For this purpose, we utilize the Why3 platform equipped with a specification language for annotated programs and back-end theorem provers. We conduct several proof tasks for each of three properties of the target code: validity, soundness, and tightness; zero division exception handling is also verified for the division code. To accomplish the proof, we propose several techniques for specification/verification. First, we specify additional lemmas that support deductions made by back-end SMT solvers, which enable to discharge proof obligations in floating-point arithmetic containing nonlinear terms. Second, we examine the annotation of tightness, which requires to assume that a computation may result in NaN; we propose specific extremum operators for this purpose. In the experiments, applying the techniques in conjunction with the Alt-Ergo SMT solver and the Coq proof assistant proved the entire code.

MSC:

65G30 Interval and finite arithmetic
68Q60 Specification and verification (program logics, model checking, etc.)
68V15 Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.)

Software:

Alt-Ergo; Coq; CRlibm; kv; Flocq; Why3

References:

[1] Moore, R. E., Interval Analysis (1966), Prentice-Hall · Zbl 0176.13301
[2] Neumaier, A., Interval Methods for Systems of Equations (1990), Cambridge University Press · Zbl 0706.15009
[3] Kashiwagi, M., The kv interval arithmetic library (version 0.4.43) (2017), URL http://verifiedby.me/kv/index-e.html
[4] Bobot, F.; Filliâtre, J.-C.; Marché, C.; Melquiond, G.; Paskevich, A., The why3 platform (version 1.1.0) (2017), URL http://why3.lri.fr/
[5] F. Bobot, J.-C. Filliâtre, C. Marché, A. Paskevich, Why3: Shepherd your herd of provers, in: International Workshop on Intermediate Verification Languages, BOOGIE, 2011, pp. 53-64.
[6] Boldo, S.; Clément, F.; Filliâtre, J.-C.; Mayero, M.; Melquiond, G.; Weis, P., Wave equation numerical resolution: a comprehensive mechanized proof of a c program, J. Automat. Reason., 50, 4, 423-456 (2013) · Zbl 1267.68208
[7] Bobot, F.; Conchon, S.; Contejean, E.; Iguernelala, M.; Lescuyer, S.; Mebsout, A., The Alt-Ergo theorem prover (version 2.2.0) (2017), URL https://alt-ergo.ocamlpro.com/
[8] IEEE, F., 1788-2015 - IEEE Standard for Interval Arithmetic (2015)
[9] IEEE, F., 754-2008 - IEEE Standard for Floating-Point Arithmetic (2008)
[10] Brain, M.; Tinelli, C.; Ruemmer, P.; Wahl, T., An automatable formal semantics for IEEE-754 floating-point arithmetic, IEEE 22nd Symposium on Computer Arithmetic, ARITH, 160-167 (2015)
[11] Pryce, J. D.; Corliss, G. F., Interval arithmetic with containment sets, Computing, 78, 3, 251-276 (2006) · Zbl 1108.65043
[12] Rump, S. M.; Ogita, T.; Morikura, Y.; Oishi, S., Interval arithmetic with fixed rounding mode, Nonlinear Theory Appl., 7, 3, 362-373 (2016), URL https://www.jstage.jst.go.jp/article/nolta/7/3/7_362/_article
[13] F. Goualard, Fast and correct SIMD algorithms for interval arithmetic, in: 9th International Workshop on State-of-the-Art in Scientific and Parallel Computing, PARA, 2008, pp. 6126-6127.
[14] Ayad, A.; Marché, C., Multi-prover verification of floating-point programs, (International Joint Conference on Automated Reasoning, IJCAR. International Joint Conference on Automated Reasoning, IJCAR, LNAI, vol. 6173 (2010)), 127-141 · Zbl 1291.68321
[15] Daramy-Loirat, C.; Defour, D.; De Dinechin, F.; Gallet, M.; Gast, N.; Quirin Lauter, C.; Muller, J.-M., CRlibm - A library of correctly rounded elementary functions in double-precision (version 1.0beta4) (2016)
[16] Daumas, M.; Melquiond, G., Certification of bounds on expressions involving rounded operators, ACM Trans. Math. Software, 37, 1, 1-20 (2010), URL http://gappa.gforge.inria.fr/ · Zbl 1364.68328
[17] Boldo, S.; Marché, C., Formal verification of numerical programs: From C annotated programs to mechanical proofs, Math. Comput. Sci., 5, 4, 377-393 (2011) · Zbl 1264.68054
[18] Roux, P., Formal proofs of rounding error bounds, J. Automat. Reason., 57, 2, 135-156 (2016) · Zbl 1409.68263
[19] Boldo, S.; Melquiond, G., Flocq: A unified library for proving floating-point algorithms in Coq, IEEE 20th Symposium on Computer Arithmetic, ARITH, 243-252 (2011), URL http://flocq.gforge.inria.fr/
[20] Conchon, S.; Iguernlala, M.; Ji, K.; Melquiond, G.; Fumex, A., A three-tier strategy for reasoning about floating-point numbers in SMT, (International Conference on Computer-Aided Verification, CAV. International Conference on Computer-Aided Verification, CAV, LNCS, vol. 10427 (2017)), 419-435 · Zbl 1494.68282
[21] Kashiwagi, M., Tanten ni mugendai wo motsu kukan enzan matome A summary of interval arithmetic with infinity bounds (2015), URL http://verifiedby.me/kv/interval/table3.pdf (in Japanese)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.