Efficient generation of error-inducing floating-point inputs via symbolic execution
Authors:
Open Access
- 27 June 2020
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1261-1272
Abstract
Floating point is widely used in software to emulate arithmetic over reals. Unfortunately, floating point leads to rounding errors that propagate and accumulate during execution. Generating inputs to maximize the numerical error is critical when evaluating the accuracy of floating-point code. In this paper, we formulate the problem of generating high error-inducing floating-point inputs as a code coverage maximization problem solved using symbolic execution. Specifically, we define inaccuracy checks to detect large precision loss and cancellation. We inject these checks at strategic program locations to construct specialized branches that, when covered by a given input, are likely to lead to large errors in the result. We apply symbolic execution to generate inputs that exercise these specialized branches, and describe optimizations that make our approach practical. We implement a tool named FPGen and present an evaluation on 21 numerical programs including matrix computation and statistics libraries. We show that FPGen exposes errors for 20 of these programs and triggers errors that are, on average, over 2 orders of magnitude larger than the state of the art.Keywords
Funding Information
- National Science Foundation (1750983)
This publication has 24 references indexed in Scilit:
- Exploiting community structure for floating-point precision tuning2018
- A comprehensive study of real-world numerical bug characteristics2017
- Achieving high coverage for floating-point code via unconstrained programming2017
- Efficient search for inputs causing high floating-point errors2014
- On-the-fly detection of instability problems in floating-point program execution2013
- Symbolic execution for software testingCommunications of the ACM, 2013
- Automatic detection of floating-point exceptions2013
- A dynamic program analysis to find floating-point accuracy problems2012
- EXEACM Transactions on Information and System Security, 2008
- The Accuracy of Floating Point SummationSIAM Journal on Scientific Computing, 1993