论文：Enyi Tang , Xiangyu Zhang, Norbert Th. Mu€ller, Zhenyu Chen, and Xuandong Lihttps://ieeexplore.ieee.org/document/7792694
摘要：数值不稳定性是一个众所周知的，可能导致严重的软件运行时故障的问题。我们探索了在软件开发过程中不稳定的原因，并开发集成了一套工具链，不仅能检测数值软件中潜在的不稳定，也能诊断这种不稳定的原因。我们把不稳定的原因分为两类。当它被软件需求引入时，我们称之为问题引起的不稳定性。在这种情况下，它不能通过改进软件开发环节来避免，但需要检查需求，特别是底层的数学性质。否则，我们称之为实践引起的不稳定性。我们设计了一套工具链---四个松散耦合的工具，它把随机算法与无限精度测试相结合。在我们的工具中，根据待分析软件的性质，每个工具可以配置不同的策略。我们在业界有名的项目上评估我们的工具。结果表明，它能有效地检测和找出由问题引起的不稳定性。我们还在最新版本的GNU科学库上评估了，并找到了一些真正的错误，这些都是维护的很好，并且广泛部署的数值库。在我们的工具的帮助下，我们把细节和修复的建议报告给了GSL的bug列表。
技术介绍：技术的迅速发展使得现代个人计算机和设备在计算方面具有强大的功能。因此，复杂的数值算法变得不是那么的无法承受，并被广泛应用于我们的日常软件中。保证数值计算的正确性对软件可靠性具有重要意义。但是另一方面，它也很有挑战性，特别是，在数值计算中独特和复杂的计算逻辑常常给软件测试和验证带来新的挑战。此外，由于有限的表示精度引起的截断误差在数值计算中一直存在，因此数值误差不可避免地在数值运算的传播过程中积累。因此，对于现代数值软件，我们不仅需要数值分析的方法，而且需要帮助我们测试和构建更优秀的数值程序的工具，特别是在存在数值误差的情况下测试它们的稳定性。
本文提出了一种全新的数值测试的工具链，它是根据软件开发过程中的模块化原理设计的。与现有的工具不同，我们的工具链不仅能够自动地检测数值程序中的潜在不稳定性，而且还可以确定不稳定性发生的原因。
软件开发过程通常包括几个不同的阶段，如需求分析、软件设计、实现、软件测试、部署和维护。在软件测试之前，任何阶段都可能引入数值不稳定性。在这里，我们把数值不稳定性定义为问题，该问题是由内部错误引起的截断或外部输入误差引起的，外部错误是指由于精度限制在原始数据收集阶段就会引入误差，从而导致大的输出误差。在存在数值不稳定性的情况下，人们往往难以信任数据处理的结果。我们的工具链主要用于测试数值程序不稳定性，图1给出了导致不稳定性的数值计算的各个方面原因。
图 1. 在软件中引起数值不稳定性的原因类别
我们的工具链结合了数值程序的随机测试和无限精度测试的技术。随机测试技术用来估计在软件数值传播过程中累积的数值误差。当我们在数值计算中随机引入小的输入变化时，程序输出的波动范围可以帮助我们估计在计算过程中累积的数值误差的大小。然后利用无穷精度算法（IPA）生成数值计算的精确输出，以展示数学问题的性质，并诊断问题的不稳定性来源，来自需求问题还是开发实践。无限精度算法不断增加精度，迭代计算过程，以确保每一个数值输出足够精确。与传统的具有固定位数的浮点运算不同，无穷精度运算按需求动态增加存储器分配的位数，以获得需要的精度。它有一个迭代模块来确保程序中的每一个数值都有足够的内存。
图2给出了工具链的主要工作流程：
图2.数值程序测试工具链的主要工作流程
为了灵活性，将工具链设计为四个松散耦合的工具依次工作：ipatrans, fpstoc, ipstoc和ediagno。
1、ipatrans: 无限精度程序转换工具
包含固定精度浮点运算的待测程序的源代*会码**提供给ipatrans。该工具将程序中的固定精度浮点运算算法自动转换为无穷精度算法。虽然传输的无限精度程序比原来的慢得多，但它是精确的，并且在以后的不稳定性诊断步骤中可以作为测试Oracle。
算法1和2展示了我们在无限精度算法中迭代的实现，算法3描述了转换过程。
算法1
算法2
算法3
2、fpstoc & ipstoc: 针对固定精度和无限精度算法的随机化转换工具
我们提供两个随机变换工具：fpstoc和ipstoc。工具fpstoc用随机方法扩展固定精度浮点运算，而ipstoc在无限精度程序上执行类似的变换。在这个步骤中可以应用一些不同的策略，例如CESTAC方法。为了一般化，我们在实现中选择了简单的策略，这种策略系统地把每个输入和中间值改变成均匀分布的随机数，在一个小但可控的范围内。
虽然CESTAC方法更有效，但这种简单普通的策略能直接改变值，并在一般情况下提供精确的统计的结果。因为fpstoc和ipstoc的变换，变换后的程序会输出在执行期间进行过随机数值扰动的结果，因此我们称之为随机化的程序。无限精度随机程序在每个算法步骤中引入随机值，但在不含有舍入误差的情况下精确地对每一步进行运算。因此，它的结果显示了该问题的基本数学性质。然而，固定精度随机程序在每个步骤中引入含有舍入误差的随机值，这表明了程序的性质。
图3给出了在固定精度浮点值上使用CESTAC策略的随机化函数，图4给出了无限精度数值的随机的舍入模式切换。
图3. 使用CESTAC策略的固定精度算法的随机化函数
图4. 使用CESTAC策略的无限精度的随机化函数
4、ediagno:评估和诊断
工具ediagno驱动测试程序，并根据转换后的随机程序的执行结果生成统计结果。如果固定精度的随机化程序的输出与原始结果相差很大，则数值软件是不稳定的。在这种情况下，ediagno检查无限精度的随机程序的相应输出。
本文主要贡献：
- 我们设计了一个与软件开发过程紧密耦合的数值测试工具链。该工具链能够检测软件中的数值不稳定性，并诊断导致这种不稳定性的原因。
- 我们结合随机和无限精度测试技术，用四个松散耦合的工具来实现工具链。该实现灵活，易于采用不同的策略进行更新。
- 我们使用业界有名的测试对象和GNU科学库对本文提出的方法进行评估。我们的工具链能成功地检测和诊断测试对象程序的不稳定性。新识别的bug被报告给测试对象所在项目的问题列表。