使用伪预言测试随机软件

论文：Matthew Patrick, Andrew P. Craig, Nik J.Cunniffe, Matthew F Parry, Christopher A Gilligan

摘要

由于随机模型的复杂性和随机性，它们很难进行测试，但是它们的预测通常用于做出重要的决策，因此它们需要是正确的。我们引入了一种新的基于搜索的技术，通过最大化实现和伪oracle之间的差异来测试随机模型的实现。我们的技术减少了测试工作，并允许发现可能被忽略的差异。我们显示技术可以识别不同挑战人类观察,并使用它来帮助新用户理解实现差异在实际模型的柑橘类疾病(黄龙病)用于通知政策和研究。

关键字

计算模型;测试;搜索优化

1. 介绍

随机模型被用来为各种主题的关键决策提供信息，超过一半的科学家现在开发的软件比10年前的要多。在最近的一项调查中，70%的生物、数学和物理科学研究人员表示，他们把开发软件作为工作的一部分，80%的人表示，如果没有这些软件，他们就不可能开展工作。科学家需要对他们的模型有信心，因为他们的预测可能会产生深远的影响。

2.使用伪预言测试

自动化的oracle数据库对于彻底有效地测试软件非常重要。伪预言用于测试没有oracle可用的软件，这要么是因为很难确定正确的输出应该是什么，要么是因为oracle不可能生成。伪预言比较多个独立实现的输出，并检查是否有任何差异。

伪预言已应用于各种各样的软件，如编译器、访问控制系统和重构引擎。找到一个合适的伪预言可能并不容易，因为模型通常是为高度专门化的目的而开发的。然而，两种实现不必在预期的功能上完全相同;只要它们能被参数化/限制为表现相同的方式，它们就能被当作彼此的部分。

3.寻找差异

3.1实现输出比较

我们从每个时间序列记录的统计数据是:(i)曲线下的面积(AUC)， (ii)峰值的值和(iii)峰值出现的时间。对于其他类型的模型，例如金融模型，选择不同的统计数据可以提高算法性能。

我们使用汇总统计信息(AUC、峰值时间、峰值)来描述每个实现的时间序列输出。多次运行这些实现将生成这些统计数据集。对于每个汇总统计数据，我们使用Kolmogorov-Smirnov测试比较两个实现的输出，这是一个针对两个概率分布差异的非参数测试。我们使用得到的p值作为差异的度量(注意，我们没有执行假设检验)。与其他测试(例如基于平均值或中值差异的测试)相比，Kolmogorov-Smirnov测试更可取，因为它考虑了分布的形状(程序输出分布可能不同，即使它们具有相同的平均值)。最后，我们取这些产生的p值中最小的一个，并使用这个（表示为f）为两个实现输出之间差异的度量。我们使用f(参见公式1)作为基于搜索的优化的目标函数。

3.2基于搜索优化

4.1 SEIR模型

SEIR模型已被用于预测多种疾病的传播(包括麻疹和埃博拉)。它通过几个单独的隔间来跟踪宿主(例如人)的数量:易感(未受感染)、暴露(受感染但不具传染性)、感染和移除(死亡或恢复)。

在SEIR模型的基本结构中，有许多选择:模型可以是连续的，也可以是离散的(在时间和/或每个隔间中的主机);它可能包含明确的空间/接触异质性或假设质量作用定律。我们实验的版本是非空间的，假设主机之间的接触是均匀的(即，并且具有离散的主机数量和连续时间)。

4.2 SECI模型

除了SEIR模型中的人为差异外，我们还应用我们的技术来探索所使用的理论SECI模型的两个实际实现之间的差异预测的传播黄龙病 (HLB),也称为柑橘绿化。HLB是由该属细菌引起的由木虱传播的自由念珠菌。它的特点是发育不良的树木生长和扭曲的苦果，保持绿色下面。HLB被认为是世界上最具破坏性的柑橘病害，导致产量下降30%至100%。

重要的是要理解这些实现是如何不同的，如果使用不当，它们的预测可能会给出相互冲突的信息。因此，我们将说明如何使用我们的技术来帮助第一次使用这些实现的人理解每个实现的假设和输出，以便他们能够运行所需的模拟并正确解释输出。

5. 研究问题

RQ1：时间序列比较指标能否揭示实现之间的细微差异?

RQ2：基于搜索的技术是否比随机测试更有效地发现差异?

RQ3：基于搜索的技术是否发现模型的实际实现之间存在差异?

6. 实验方法

实验使用两个模型:简单的SEIR模型(人为我们介绍差异)和更高级的SECI HLB模型(我们比较两个真正实现用于通知政策和研究,科学家与包装器代码修改的学习如何使用这两种实现)。对于每个模型，我们应用基于搜索的优化来最小化各种统计数据(AUC、峰值时间、峰值主机和总主机)的Kolmogorov-Smirnov测试的p值。换句话说，我们最大化了每个实现的时间序列分布之间的差异。

我们使用我们的技术来识别人为引入差异在SEIR的实现中,首先对参数(时间单位T和年代,E,我和R单元[S])β= 0.003 [S]?1 T?1,γ= 1 T?1和μ= 1 T?1,然后通过发展新的参数值在[0,0.006]的经营范围内为β,γ(0,2),为μ(0,2)。在这个实验和SECI HLB实验中，我们允许基于搜索的优化技术在每个试验中进行30代，总共运行了50次试验。之所以选择这样的代数，是因为我们发现，在我们用来进行实验的台式电脑(Intel Core i7.8 GB内存)上，每次试验平均需要大约一个小时的时间。我们认为这是计算建模者等待结果的合理时间。

我们使用类似的方法确定了M1和M2之间的差异，这是SECI HLB模型的两种实现(以及包装器代码)。每个测试用例(输入参数集)运行100次，以处理随机性。测试用例生成合理的范围内(0,20)m为α,[0,0.1]年?1,和[0,1000]m2yr?1β0(我们最初认为是相同的与单位年β?1,但见7.3节)的区别。然后，我们使用测试结果来识别两个实现(M1和M2)的时间序列输出的差异。这些信息被用作指导，帮助我们检查代码，了解输出行为中这些差异背后的原因。

7. 结果

7.1回答RQ1

RQ1评估通过人为差异引入到SEIR实现轻微增加β和γ。目的是了解我们的技术是否能够识别微小的差异，并深入了解可以检测到的差异的大小和类型。

改变β和γ以不同的方式影响到SEIR的实现。增加β提出的感染率,而增加γ提出了主机的速度成为传染性。曲线的变化产生的增加β和γ的值是微妙的,但我们的技术仍然可以检测到它们,因为它使用不同的度量。使用峰值和峰值时间指标发现beta差异，而使用e的AUC只能发现gamma差异。如果只使用一个指标，可能会忽略差异，但是通过结合多个指标，我们的技术可以非常有效。

7.2回答RQ2

我们通过比较进化优化(CMA-ES)和随机搜索的进展来评估RQ2。这两种方法都用于查找输入参数值

使(当γ增加0.1%)产生的差异更加明显,从初始值(β= 0.003,γ= 1和μ= 1)使用在前面的问题。搜索中各参数的下界为0;上界是0.006β,γ和μ2。图8显示了搜索技术在实现低假定值稍快的增加比随机搜索γ。然而，随机搜索和CMA-ES都在相当短的时间内(不到一小时)实现了较低的p值。进化优化方法有可能导致更快、更一致的测试。

使用CMA-ES和随机搜索选择的参数值进行的100次仿真的p值分布。虽然随机搜索产生的p值范围略大于CMA-ES，但与原始参数值的分布相比，差异很小。类似地，图10显示CMA-ES并不总是更快。在对SECI HLB模型的参数值进行优化时，其p值较低，与随机搜索的p值基本相同。这表明这两种方法都适用于我们的技术。

7.3回答RQ3

RQ1是通过将基于搜索的伪预言技术应用于两个实际实现的输出，以及用于为HLB制定策略决策的模型的包装器代码(M1和M2)来评估的，这是学习使用这两个实现的科学家所使用的。再一次,我们强调M1和M2之间的差异没有错误在原始代码,而是差异有关模型设置,输出格式,转换代码写的科学家学习如何使用这两种实现。

图 M1和M2之间存在差异

8. 威胁的有效性

由于被测软件是随机的，每次运行的输出可能是不同的。对于一个给定的样本大小,有机会从错误的输出实现将遵循同样的分布与正确的实现(我们可以找不到错误)或两个正确的输出实现可能有不同的分布(我们可能会错误地认为有错误)。我们通过将搜索算法合并到我们的技术中来解决这个问题，以识别参数值，如果参数值存在，则一致地显示差异。

在SEIR的例子中,我们看到小改变β和γ并不一定产生变化的分布假定值(考虑增加0.5%βγ或增加0.2%)。我们可能担心，当两个实现之间的差异非常小时，这可能会导致错误的安全感。然而，即使在这些情况下，我们的技术也能够使用搜索来查找输入参数，这些参数不断地将p值降低到一个较低的水平，从而使差异更加明显。显然，我们的技术能够检测到的差异大小是有限的，即使使用搜索，因为计算机的精度不是无限的。然而，我们的技术甚至能够检测到人类无法观察到的微小差异。

9. 结论

我们提出了一种新的测试随机软件的技术，使用基于搜索的优化和伪预言。通过优化，可以找到实现的输出分布尽可能不同的输入参数，从而确定这些差异的原因。我们通过将Kolmogorov-Smirnov测试应用于从时间序列输出导出的汇总统计数据集，来识别差异并指导搜索。与容错阈值或均值差测量等简单方法相比，该方法具有更强的鲁棒性，能够识别输出分布中的细微差异。我们在一个简单的非空间模型上演示了我们的技术，并描述了它如何帮助科学家熟悉如何正确使用两种实现来实现一个更复杂的真实疾病的空间模型(HLB)。

致谢