1、基于数据挖掘的软件测试技术研究摘要 软件的可靠性对社会，经济，国防等都有着巨大的意义，而要提高软件的可靠性，必须对软件进行大量的测试。但是由于条件的限制，必须在资源耗费和测试效果之间达到平衡。如何以最小的代价进行尽量高效的测试，是一个值得研究的问题。因此，数据挖掘技术作为一种处理海量数据的有效方法被引入到软件测试中，也产生了许多成果。软件测试中有两个典型的“数据过量”问题：一个是测试用例的选择：由于软件输入空间十分巨大，将所有这些输入全部检验是不现实的，因此必须用某种方法将输入空间分成若干“等效的”类，在每个类中选择少量元素作为测试用例，从而减少测试用例的数量。另一个是与Bug报告的分析：由于
2、越来越多的软件 采用了自动报告Bug的方式以便可以准确地获得软件Bug信息，这种方法对于Bug数据的收集是非常有效的，但软件开发人员往往无法对过多的Bug数据进行处理，造成了信息浪费。因此必须找到一种自动化的方法对这些数据进行分析。本文针对以上两个问题，介绍和提出了使用数据挖掘技术的解决方案，即：1缩减测试用例：在复杂软件的测试中，其输入空间几乎是无限的，因此不可能将全部的测试用例都输入到待测软件中执行。解决的方法就是通过某种方式选择其中最有代表性的一部分对待测软件进行测试，称作测试用例的缩减。数据挖掘技术可以作为缩减测试用例的一种有效方法。2对Bug报告的分析：由于许多当代的软件可以自动监测
3、异常运行状态并将相关数据发送给软件开发者，软件开发者往往要面临大量的Bug数据，如果对这些数据逐一分析是十分费时费力的，利用数据挖掘方法，自动对这些数据进行处理，缩小问题空间。数据挖掘 数据挖掘 是通过分析，从大量数据中寻找其规律的技术，主要有数据准备、规律寻找和规律表示三个步骤：1.数据准备是从相关的数据源中选取所需的数据并整合成用于数据挖掘的数据集；2.规律寻找是用某种方法将数据集所含的规律找出来；3.规律表示是尽可能以用户可理解的方式（如可视化）将找出的规律表示出来 数据挖掘的技术基础是人工智能，仅利用了人工智能中一些己经成熟的算法和技术，例如：人工神经网络(Artificial Neu
4、ral Networks)遗传算法(Genetic Algorithms)决策树(Decision Trees)邻近搜索方法(Nearest Neighbor Method)规则推理(Rule Induction)模糊逻辑(Fuzzy Logic)等等.遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法 由三个基本算子(或过程)组成：1.繁殖(选择)，即从一个旧种群(父代)选出生命 力强的个体，产生新的种群(后 代)的过程。2.交叉(重组)，即选择两个不同的个体(染色体)的部分(基因)进行交换，形成 新个体的过程。3.变异(
5、突变)，即对某些个体的某些基因进行 变异(0变19或l变0)，形成 新个体的过程。数据挖掘的主要分析方法 1关联分析(Associations)，关联分析的目的就是为了挖掘出隐藏在数据间的相互关系。2序列模式分析(Sequential Patterns)序列模式分析和关联分析法相似，其目的也是为了挖掘出数据之间的联系，但序列模式分析的侧重点在于分析数据间的前后或因果关系。3分类分析(Classifiers)假定记录集会和一组标记(TAG)，所谓标记是指一组具有不同特征的类别。分类分析时首先为每一个记录赋予一个标记，按标记分类记录。4聚类分析(Clustering)与分类分析法不同，聚类分析法的
6、输入集是一组未标定的记录，也就是说此时输入的记录还没有被进行任何分类。其目的是根据一定的规则，合理地划分记录集合。信息-模糊网 简介 信息-模糊网(Info-FuzzyNetwork，以下简称IFN)是由以色列Bcn-Gurion大学的Mark Last提出的一种基于信息论的分类方法，与传统基于信息论的分类方法相比，在保证分类精度的同时可以得到比较简约的分类规则。信息-模糊网的结构与决策树不同，IFN具有网状的，类似神经网络的分层结构IFN由一个根节点，若干个中间层，和一个目标层构成。IFN的每个中间层只对应一个待分类的属性，第L中间层的一个节点表示前L个输入属性值的并。如果某个属性为连续变量
7、，需要将其离散化。目标层的每个节点表示目标属性的一个值，如果目标属性是连续量，则目标层表示若干不相交的区间。其中，直接与目标层节点相连的中间层节点称为终结点(final nodes)，终结点与目标层节点间的连接表示一组输入属性可以被划分一个特定类；例如有五个终结点：(1，1)，(1，2)，(3，1)，(3，2)。假如把图看作是根据某个可执行程序的输入、输出所建立的IFN，则连接(1，1)-1的意义为：对于具有两个输入值都为1的测试用例，程序将输出结果1。信息-模糊网的构建算法 输入为一个训练数据集，目标属性集合和节点分裂所需的最小熵压缩阈值sign，首先定义目标层，每个节点表示一个类别；由一个
8、表示空集的根节点开始，计算每个属性分裂后引起的熵压缩，对于取离散值得属性可直接计算，对于连续值的属性首先进行离散化再计算；选择引起熵压缩最大的属性进行分裂，形成下一个中间层；重复以上步骤迭代地建立网络，直到没有候选属性接点分裂起的熵压缩大于sign时，网络的建立过程结束。计算某个结点分裂引起的熵压缩使用如下的算法：设S是s个数据样本的集合，假定有m个互不相同的目标属性，定义m个不同类 。设Si是类Ci中的样本数。对一个给定的样本分类所需的期望信息(熵)可以由以下公式计算：Pi是任意样本属于Ci的估算概率).2,1(Cimi)(log),.,(1221imiimppSSSIsspii设候选属性A
9、有v个不同值(al，a2 av)。可以用属性A将S划分为v个子集S1，S2，Sv)；其中，sj包含S中在A上值为aj的样本。设sij是子集sj中类属于Ci的样本数。则将样本按A划分后，对一个给定样本分类所需的期望信息(熵)由下式给出：其中，对于给定的子集Sj，pij是sj中的样本属于类Ci的概率，表示为vmjjjmjjjsssIssssAE1j2121),.,(.)(miijijmjjjppsss1221)(log-),.,(Ijijijssp 分裂属性A所造成的熵压缩为：然后选择引起熵压缩最大的属性进行分裂。.)(),.,()(21AEsssIAGainm使用信息-模糊网划分等价类 使用IF
10、N划分测试用例等价类的系统结构见图 系统组成模块及功能如下：被测试模块：这部分可以是一个程序，组件或完整的系统，并且它在以后的使用中将不断的更新版本。要注意的是，它应该是“数据驱动”的，即它的输入和输出都是一组了格式和类型的数据。系统输入输出说明：对待测试模块输入和输出数据的说明，可以包括变量数量，名称，类型，取值范围等。测试用例产生器：根据系统输入输出说明提供的信息自动地，随机地产生测 试用例，产生的数量由用户指定。产生的测试用例输入数据交给测试驱动程序和 IFN构建算法。测试驱动程序：它将用例产 生器产生的测试用例送给被测试模块执行，并接收每个测试用例的输出。然后交给IFN构建算法。IFN
11、构建算法：算法的训练数据集是接收自测试用例产生器的测试用例输入数据和来自测试驱动程序的测试用例输出数据。算法根据某组输入所对应得输出将随机产生的大量测试用例划分成若干等价类。系统运行时，首先由测试用例产生器根据输入输出说明中的描述产生一组输入数据，这组输入数据被交给测试驱动程序；测试驱动程序将数据输入被测模块并得到被测模块的输出；随后，这组输入和它相应得输出被作为一条训练数据交给IFN的构建算法。构建算法迭代的运行，以输出作为目标层，将大量的输入划分成少量等价类。然后便可以从每个等价类中选择少量的数据作为测试用例。使用序列模式挖掘技术分析BugBug报告 什么是BUG报告在软件测试和使用过程中
12、，当测试人员或用户发现一个缺陷时，需要把它告 诉给开发人员，Bug报告就是将Bug的详细信息传递给开发人员的方式。有效的 Bug描述，会更加容易帮助开发解决问题。因此，在Bug报告中需要尽量给出足够多的指引，以便开发人员能够根据报告中的描述重现错误。BUGBUG报告的内容 一般来说，高质量的Bug报告，应该包括以下内容：1、Bug标题：简明扼要地对Bug进行一个概述。2、Bug的属性。Bug的属性应该包括：(1)产品名称：测试产品的名称。(2)产品子系统：测试产品的子系统，如果产品比较小，该项可以忽略。(3)产品模块：测试产品发现问题的模块的名称。(4)测试版本：当前的测试版本。(5)测试平台
13、：Bug的产生很可能跟平台有关。(6)测试阶段：模块测试、内部集成测试、外部集成测试。(7)问题级别：紧急、严重、一般、建议，级别高的问题应优先处理。(8)问题来源：测试、工程故障、升级、其他(9)问题类型：功能问题、版本问题、遗留问题、新需求、低级错误、改进建 议、移植修改、割接问题、配置错误、编译问题、性能问题、设计问题、兼容问 题、新功能增强、偶发性出错自动BugBug报告 自动记录并发送Bug信息的技术是软件开发技术的一项重要进步，使软件的开发人员能 够获得足够的数据来确认和定位Bug，提高软件质量。但是，这种技术给开发人员带来了一个新的问题：接收到的自动Bug报告往往数量巨大，根本无
14、法逐个进行分析，那又如何从用户实际使用时的事件序列中定位缺陷位置呢?为解决这个问题提出：从若干个这些事件序列中的发现出现的较为频繁的共同的子序列，则这个子序列就可能是导致错误发生的事件序列。软件的开发人员可以使用这个子序列重现错误，继而定位错误，从而避免了对大量的错误报告逐一分析，大大提高了效率。下面给出一个形式化的描述：设 是软件可能发生的事件集合，O中的每个元素代表一个事件；设 是若干事件序列组成的集合，S中的每个元素是一个可以导致软件产生错误的事件序列：如果S中有一个子集 ，满足 c(c是人为选定的正整数)，并且 中任意一个元素序列 ，都有子序列P,则P就可能是导致错误发生的事件序列。需
15、要注意的是，这里“序列”的意义与集合不同，序列中元素的出现是有次序的。,.o,o,o321O,.,321SSSS ONjNissssSsssSsssSij),(.,.,.,.,33,3231323,2221213,12111SSS)0(SSiSi序列模式挖掘技术 序列模式挖掘由 Agrawal和Srikant最早提出：给定一个由不同序列组成的集合，其中每个序列由不同的元素按顺序有序排列、每个元素由不同项目组成，同时给定一个用户指 定的最小支持度阈值，序列模式挖掘的任务就是找出所有频繁子序列，即出现频率不低于最小支持度阈值的子序列。定义：序列：序列(sequence)是项集的有序表，。其中S是
16、项集(也是S的元素)。序列包含的项集的个数称为序列的长度，长度为k的序列记为k-序列。子序列：，使得 ，则称序列A为序列B的子序列。支持度:序列A在序列数据库S中的支持度为序列数据库S中包含序列A的序列个数，记为Support(A)。模式给定支持度阈值c:如果序列A在序列数据库中的支持数不低于c，则称序列A为序列模式，长度为k的序列模式记为k-模式。可见，前一节提出的问题，可以部分的转化为从序列数据库中发现序列模式的问题。,.,321SSSS mjjjBBBBAAAAnnn.1,.,.,212121如果存在整数jnnjjBABABA,.,2211IPMIPM算法 基本概念 1.所有事件序列的集
17、合。集合中的每个序列S是软件发生错误之前用户事件序列(可以取最近若干个事件)。2.候选模式：等待算法判断是否是模式的一个子序列。3.下标运算符i：一个序列的第i项。4.插入错误：当序列SS包含序列P时，对区间(0，length(p)中的每一个正整数i,取J=i+1,记满足条件 时的正整数li与ki之差为Ci，则Max(C)称为插入错误。5.判定标准c：用户定义的三元组(minLen，minSupp，maxError)，表示模式P成为频繁模式需要满足的最小长度，最小支持度，最大允许插入错误。,.,321SSSS PiiikSjPlS 6.模式描述表：用来描述一个模式，记为localist(P)，
18、表中的每个项是描 述模式P的三元组(seqnum，startloc，endloc)表示包含该模式的序列在S 中的编号，该模式在包含它的序列中起始和终止的位置。显然，每 个 模 式 的 描 述 表 长 度 等 于 它 的 支 持 度，localist(P)Jength=Support(P)。7.模式的前缀：记做prefw(P)，表示模式P的前length(P)一1项组成的序 列。8.模式的后缀：记做suffix(P)，表示模式P移除第一个项后的序列。算法执行过程 IPM算法的基本过程与各种经典序列挖掘算法相同，首先找到较短的频繁序列，然后将其扩展以得到长序列。算法接受一个输入序列集合S和判定标准
19、c，找出S中符合c的所有频繁模式。主要由两个阶段构成，首先：算法搜索输入串，穷举所有的长度为2，插入错误小于c.m a x E r r o r 的 候 选 模 式，并 将 所 有 候 选 模 式 存 储 在 一 个length(A)*length(A)的矩阵ptList中。ptList的行、列编号对应A中事件的编号，矩阵的每个单元ptListi，j包含了所有P2=i，P1ength(P)=j的候选模式，例如：候选模式1，4，7，5)被存储在ptList4，5中。算法的第二个阶段是通过迭代扩展序列，直到所有的模式被发现。每次迭代进行如下的过程：对矩阵中已存储的每个长度为L(L随每次迭代递增)的候
20、选模式P1 P2，如果prefix(Pi)=suffix(P2)，生成一个新候选模式P3=P2+P1L，并存 储在矩阵单元ptListP11，P1L中。对于新候选模式P3，如果 Support(P3)c.rainSupp，则被剪枝，否则保留；当不能生成新的更长的候选模式时，算法终止。示例 以两个较短的序列S1=1，3，2，3，4，3，S2=2，3，2，4，1，3)为例演示算法的执行过程。对于这两个序列，A=l，2，3，4)，S=S1,S2，S1=l，3，2，3，4，3)，S2=2，3，2，4，1，3)，取c=(minLen，minSupp，maxError)=(2，2，1)，算法执行过程如下所示：阶段预处理：第一次迭代:第二次迭代：迭代结束，最终发现模式3，2，4，3)，2，3，4，3)，1,3，3，3。继而定位了错误，重点排查。谢 谢
