Research On Automated Repair Techniques Of Floating-Point Programs

In modern computer systems,floating-point numbers are one of the most widely used approximations of real numbers.Floating-point programs that integrate a large number of floating-point operations often as basic arithmetic modules provide computational support for upper-layer software systems.However,floating-point operations,as an approximation of real-number operations,are nature inexact,and floating-point operations are also not closed,resulting in accuracy bugs and floating-point exceptions in floating-point programs.Due to the huge input space of floating-point programs and the input distribution of triggering accuracy bugs and floating-point exceptions has no specific rules,making accuracy bugs and floating-point exceptions difficult to be detected.It is also very difficult to manually fix the accuracy bugs and floating-point exceptions in floating-point programs,which requires proficiency in floating-point arithmetic and expert knowledge in the field of numerical analysis.At the same time,the complex structure of floatingpoint programs also makes existing research techniques often limited to the analysis and optimization of floating-point expressions instead of the entire floating-point programs.In addition,the ill-conditioned problems that exist in the corresponding mathematical functions of floating-point programs also limit the repair ability of current techniques.Therefore,this paper focuses on the accuracy bugs and floating-point exception problems of floating-point programs,and conducts research work in three aspects: basic theory of the problem of repairing accuracy bugs,automated repair techniques of accuracy bugs and floating-point exceptions.The main contributions of this article are summarized as follows:(1)To address the problem of repairing accuracy bugs in floating-point programs,we propose a reduction theory for the problem of repairing accuracy bugs in floatingpoint programs—ATR reduction theory.The core idea of ATR reduction theory is that floating-point programs are essentially numerical approximations of mathematical functions in floating-point space.Based on the core idea,we propose a reduction algorithm that constructs a numerical approximation to repair accuracy bugs and the ATR reduction theory that guarantees the reduction algorithm can generate patches that meet any given accuracy requirement.(2)To repair accuracy bugs in single-input floating-point programs,we propose an automated repair method of accuracy bugs based on piecewise linear approximation,Auto RNP,which is the first method in the world that can automated repair of accuracy bugs in floating-point programs.Theoretically,the method can 100% fix accuracy bugs in singleinput floating-point programs.This method addresses the challenge of ill-conditioned problems of mathematical functions,uses the approximate values of condition numbers of mathematical fun as a guide to search and locate the problem space,and implements automated repair of accuracy bugs with any given accuracy requirements by piecewise linear approximation.In the GNU Scientific Library,Auto RNP can automatically repair all 20 single-input floating-point programs that have detected accuracy bugs.(3)To repair accuracy bugs in multi-input input floating-point programs,we propose an automated repair method of accuracy bugs based on Taylor approximation,NPTaylor,which is the first method that can the automated repair of accuracy bugs in multi-input floating-point programs?This method aims at the problem that automated repair of accuracy bugs in multi-input floating-point program,based on the ATR reduction theory,through Taylor approximation to achieve automated repair of accuracy bugs in multi-input floating-point program under any given accuracy requirements,and through error-free transformation and Horner algorithm to implement the precision optimization and performance optimization for generated patches.In the GNU Scientific Library,NPTaylor can automatically repair 20 of the 27 multi-input floating-point programs that have detected accuracy bugs.(4)To repair floating-point exceptions in floating-point programs,we propose an automated repair method for floating-point exceptions in floating-point programs,ARFPE,which is the first method that can the automated repair of floating-point exceptions in floating-point programs.Based on the core idea of the ATR reduction theory,we propose a localization method of floating-point exceptions that combines the static and dynamic analysis techniques.The advantages of soundness of static techniques and the accuracy of dynamic techniques are combined to achieve an accuracy and fast localzation of the input sud-domains that triggers floating-point exceptions.After localization,to analysis the impact of floating-point exceptions on the functionality of floating-point programs,this method classifies those input sub-domains that can trigger floating-point exceptions based on the outputs of corresponding mathematical functions of floating-point programs.and combines numerical approximation methods and floating-point exception handling methods to realize automated repair of floating-point exceptions.For the 107 single-input floating-point programs in the GNU scientific computing library GSL,ARFPE successfully detected 30 floating-point programs that contained a large number of floating-point exceptions,and successfully fixed floating-point exceptions in 14 of those 30 floatingpoint programs.