朴素贝叶斯应用于自动化测试用例生成

李欣 张聪 罗宪

（重庆交通大学，重庆 400074）

朴素贝叶斯应用于自动化测试用例生成

李欣 张聪 罗宪

（重庆交通大学，重庆 400074）

提出使用朴素贝叶斯作为核心算法来产生自动化测试用例的方法，将分类的思想引入到自动化测试用例的生成中。通过实验验证此生成测试用例方法的可行性。

朴素贝叶斯；自动化测试；测试用例生成

在软件测试过程中，测试用例的设计和生成是软件测试的重点和难点。根据统计，软件测试用例设计的开销约占整个软件测试开销的40%。传统的软件测试方法——手工测试存在测试用例集合庞大、成本高等缺点。为了解决这些问题，测试趋势整体朝着自动化发展，而软件测试用例的自动化生成是软件测试自动化的关键技术。本文将分类的思想引入到自动化测试用例的生成中,利用朴素贝叶斯［1］的策略来对随机生成的测试用例进行分类得到最后的有效测试用例。

1 测试用例的自动生成技术

测试用例自动生成［2］是软件测试自动化的关键技术之一，目的在于减少测试人员手工生成测试用例的工作量，降低测试成本，提高测试效率。目前，软件测试用例自动生成技术一般可以分为面向功能的测试用例自动生成技术和面向路径的测试用例自动生成技术两大类。本文提出的自动化测试用例生成算法将应用于面向路径的测试用例技术。

2 朴素贝叶斯算法

贝叶斯推理提供了用于推理的一种概率手段。它基于待考查的量遵循某概率分布，且可根据这些概率以及观察到的数据进行推理，以作出最优的分类。而贝叶斯学习方法中实用性很高的一种为朴素贝叶斯学习器，常被称为朴素贝叶斯分类器。

将朴素贝叶斯分类器［3］应用到任务中，每个实例x是由属性值的合取描述，而目标函数f(x)从某有限集合V中取值。学习器被提供一系列关于目标函数的训练样例以及新实例，然后对新实例分类。

贝叶斯方法的新实例分类目标是在给定描述实例的属性值＜a1，a2，…，an＞下，得到最可能的目标值 vMAP。

可使用贝叶斯公式将表达式改写为：

由式（1）、（2）可知，估计每个 P(vj)很容易，只要计算每个目标值vj出现在训练数据中的频率就可以。但除非有一个非常大的训练集合，否则用这种方法估计不同的 P(a1，a2，…，an|vj)项不太可行。然而，朴素贝叶斯分类器基于一个简单的假设：在给定目标值时属性之间相互条件独立。因而可以将上式转换为：

其中，vNB表示朴素贝叶斯分类器输出的目标值。

3 基于朴素贝叶斯的路径测试用例生成设计

在应用朴素贝叶斯分类器时的两个主要问题是，首先要决定怎样将任意一组测试用例表示为属性值的形式，其次要决定如何估计朴素贝叶斯分类器所需的概率。这里表示任意测试用例的形式特别简单，给定一个测试用例，可以把每个参数定义为一个属性。而对测试用例的分类可以分为cover和uncover这两大类。

本文使用判断三角形类别的程序［4］作为被测程序，进行路径测试数据生成的算法设计。此程序将3个整数作为输入，判断这3个整数能否构成一个三角形。若能，则输出等腰三角形、等边三角形和普通三角形；若不能，则输出非三角形。由于该程序包含清晰的逻辑，而且即使将一个较大范围的整数作为输入，也只有少量的输入组合能满足代码的某些特定分支，因而有利于对于自动生成算法的分析。由python编写的被测程序如下：程序流程如图1所示：

图1 被测程序的流程图

程序共有4条路径：路径1得到等边三角形，路径2得到等腰三角形，路径3得到普通三角形，路径4得到非三角形。路径1和路径2是2条最长的路径，均要执行3个嵌套的IF语句分支，且若用随机法产生测试用例，路径2和路径1的执行概率比其他2条更低。因此，为更好地突出朴素贝叶斯算法的效果，本文选择其中的路径1作为示例测试路径，其他路径的测试工作就不再重述。

实验中，人为创建数目为80的数据样本作为已分类的测试用例集合。并随机创建基于图1的新的待分类的数目为100的预测测试用例集合，并对其中一个进行分类作为例子。若从预测数据集合中读出如下数据（4，4，2），其中 4、4 和 2 分别对应于参数a、b 和 c。

朴素贝叶斯分类算法［5］的步骤如下：

首先分别计算训练数据中符合路径覆盖和不符合路径覆盖的类型所占的比例。由于80个训练集合中符合的数据数目为50，不符合的数目为30。因此有：

其次，对于要被预测的测试用例，分别计算每个属性在训练集合中的条件概率：

然后，使用这些概率估计以及对剩余属性的相似估计，可按照式（3）计算vNB如下：

基于从训练数据中学习到的概率估计，朴素贝叶斯分类器将此实例赋以目标值uncover。进一步地，通过将上述量化归一，可计算出给定观察值下的目标值为uncover的条件概率。对于此例，概率为：

4 结 语

测试用例的自动生成是实现软件测试自动化的基本前提，因此，如何自动生成测试用例就成为解决自动化测试问题的关键。本文以实现自动化测试为目标，引入了朴素贝叶斯对产生的随机测试用例分类这一思想，通过实验论证这种方法是可行的。

[1]Tom M Mitchell.机器学习[M].曾华军,张银奎，译.北京：机械工业出版社，2003.

[2]陈雨.基于遗传算法的测试用例生成[D].上海：东华大学,2009.

[3]Stuart J.Russell,Peter Norving,et al.人工智能——一种现代的方法：第二版[M].北京：清华大学出版社，2006.

[4]梅尔斯.软件测试的艺术：第二版本[M].王峰,陈杰译.北京：机械工业出版社，2006.

[5]西格兰.集体智慧编程[M].南京：东南大学出版社，2009.

Naive Bayesian Applied in Automatic Test Cases Generation

LI Xin ZHANG Cong LUO Xian
(Chongqing Jiaotong University,Chongqing 400074)

Automatic testing cases are generated by Bayesian methods as the core algorithm.And the thoughts of classification is introduced in test case generate.The results shows the method presented in this paper is an feasible method to generate test cases.

Bayesian;automatic testing;test case generate

TP311

A

1673-1980（2012）02-0150-03

2011-11-29

重庆科技攻关项目(CSTC,2010AC2077)

李欣(1984-)，男，湖北襄樊人，重庆交通大学在读硕士研究生，研究方向为软件工程。