针对函数式编程语言的基于属性的测试方法研究

一、概论

如何提高软件质量是软件工程致力解决的关键问题之一。软件测试和验证是保证软件正确性和提高可靠性的最基本和最重要的手段，也是工业界使用的主流技术。软件测试有不同的方法，基本可以划分为基于程序的测试和基于规范的测试两大范畴。基于程序的测试根据程序特征代码（如：语句、分支、路径）产生测试样例，并以相应程序代码特征是否得到充分测试作为测试终止的判定标准，即测试充分性准则。基于规范的测试要求根据功能规范和设计规范产生测试用例，针对相应的功能和设计属性进行测试，并以相关属性是否得到充分测试作为测试充分性准则。

到目前为止，工业界在软件开发过程中采用的测试技术大多是非系统化的，具有可靠性高、实时性强等要求，通常的完整的软件测试工作需要耗费大量的人力物力，基本上会占据软件开发周期50%甚至更多的时间。特别地，对于一些特殊的软件，比如：安全攸关实时软件（火箭控制等），他们的高复杂性和高安全需求使得传统的基于程序代码的测试在技术上难以实现，开销上难以接受。

对于特定目的，采用某些特定结构的程序可以采用一类称为随机测试的方法。随机测试是一种有效的测试策略，该策略简单易行、成本低，不需要过多了解软件的内部结构的信息，只是按照一定的规则在整个输入域中随机产生测试用例，因而被广泛地用于软件测试和可靠性评估中。同时，高昂的测试代价不断促进研究人员考虑能否有自动化测试的方法，不管是全部自动化还是部分自动化。自动化的测试工具可以帮助编程人员在很短的时间内完成测试，并且很容易在每次程序修改过之后重复测试。目前为止，有一类QuickCheck的工具，可以用于测试Haskell程序。

二、 研究方法

一个属性为基础的测试框架通常会一遍又一遍地运行相同的生成测试数据，这个设置和当前基于样例的测试架构不太一样，在基于样例的测试中，每个单元测试都设置了一个输入的情况，然后运行测试的代码，最后检查输出（以及然后代码应该有的其他的影响）。相反的是，一个属性为基础的测试通常会运行数百次不同的输入，这个测试的框架通常会考虑一些比较边缘的情况，比如：传递空列表、负值、所有可能的边缘情况，来使测试发生失败，以达到学习的目的。

基于属性的测试人员必须非常仔细地考虑各种各样的规范和细节。比如：支持什么样的输入？输入如何产生？可以对输入做哪些申明？这些考虑都是非常必要的。

基于属性的测试主要分为以下八个步骤：

属性选择（selecting a property）。它需要从一堆属性池子中根据一些准则选择一个属性来进行测试。

静态分析（Static analysis and slicing），它主要做的工作是为源代码生成一个基于数据流的图，这个图通常在基于属性的其他步骤中有很多作用。

程序导入（Program instrumentation），它的主要工作是：导入以及定位到与第一步中选择的属性有关的代码片段，然后编译这段代码片段。

初步测试（Initial test execution），它的主要工作是：使用之前产生的各种各样的测试数据进行初步测试。

范围测试（Coverage evaluation），它的主要工作是：根据第四部测试执行过程中产生的代码片段执行的历史记录来分析哪些路径是被执行的，以此来得到一个所谓的范围。

额外测试（Additional test case），它的主要任务是：根据第五步返回的结果进行进一步的测试。

正确性评估（Correctness evaluation），它的主要任务是：将之前的测试结果与期望结果进行比较，依次来判断基于该属性的测试是否成功。

三、实验评估

为了验证基于属性的测试的有效性，我们设计了如下实验对其进行验证，选择二项堆（Binomial Heap）作为测试对象对其进行基于属性的测试。

二项堆是一种支持快速合并的堆数据结构，采用二项树（Binomial Tree）的集合进行实现。二项树递归定义如下：

阶为k的二项树是由阶为k-1， k-2， ， 2， 1， 0的二项树的根节点作为k阶二项树的节点构成的。

二项堆是有二项树的集合构成的，满足如下二项堆性质：

堆中的每一棵二项都树满足最小堆性质，即结点的值大于其父节点的值；

堆中具有某阶的二阶树具有唯一性。

我们采用Scala实现了中的二项堆，并且设计实现了5种具有缺陷的二项堆，对这6种二项堆进行了属性测试。具有缺陷的二项堆对原二项堆的实现进行了变种，使其在某些特定情况下会不满足二项堆的性质。

我们还设计了6个属性，采用基于属性的测试方法对这6种堆实现进行测试，这些属性都是根据二项堆的性质进行设计的，所以正确的二项堆实现会全部满足这些属性，而我们设计实现的具有缺陷的二项堆将会违背某个属性。

这是因为第二种变种实现改变了链接二项树的操作，会影响到堆的插入、删除等各项操作，对产生的堆的结构产生了影响；而第一种变种实现仅会影响到findMin操作，不会对堆的结构产生影响。

四、结论

本文对基于属性的测试进行了研究，实验中采用Scala编程语言对纯函数式二项堆进行了实现，并设计实验了五种具有缺陷的二项堆，并定义了六种满足二项堆性质的属性，采用基于属性的测试对二项堆进行测试，通过实验结果证明了基于属性的测试的有效性。