（计算机应用技术专业论文）kn软件系统测试集生成方法设计与研究.pdf

摘要 参数的配对组合测试是适用于各种软件系统的一种实用而且有效的测试方法。目 前，应用于软件系统生成测试案例集合的方法主要有：正交矩阵方法、覆盖矩阵方法、 川巳t g 、i p o 组合策略等。 论文首先介绍了正交矩阵方法、覆盖矩阵方法、a e t g 、i p o 等四种方法的主要思 想，总结和比较了它们各自的应用范围和优缺点。然后分析了运用正交矩阵方法和覆 盖矩阵方法构造测试集的过程及其在参数组合配对测试中的应用。通过分析它们在软 件系统中生成测试集时存在的问题，包括软件系统与测试集生成方法之间的不适应性、 构造测试集的算法复杂、测试集偏大等问题，论文提出了改进方法。 为了有效解决这些方法中存在的诸多问题，本文把k - n 软件系统，即参数个数k 和参数取值个数n 的系统划分成四类。对于n = 2 的k 2 二值软件系统，本文设计一种 基于纵向二进制字符串集合和控制变量法的测试集生成方法。对于n 2 ，n 是素数或 素数幂的k n 软件系统，设计一种基于正交矩阵及其派生矩阵、两个有用判别条件的 测试集覆盖矩阵方法。对于k 个参数的取值个数n 不尽相同的软件系统，提出一种经 验算法。 论文最后用实验验证这三种方法的有效性。实验表明，用这三种方法得到的测试 案例集合的大小都优于正交矩阵方法、覆盖矩阵方法、口o 、a e t g ，而且软件系统与 测试集生成方法之间的适应性也大大提高。 关键词：k - n 软件系统，测试案例集合，测试集覆盖矩阵，参数配对组合 a b s t r a c t p a i r w i s et e s t i n gi sap r a c t i c a la n de f f e c t i v et e s t i n gf o rv a r i o u st y p e s0 f s o f t w a r es y s t e m s a tp r e s e n t ，t h e r ea r em a i n l yf o u rm e t h o d st oc o n s t m c tt e s tc a s es e ts u c ha so a m ( 0 n h o g o n a l a a ym e t h o d ) 、c f 气m ( c o v e r i n ga h a ym e t h o d ) 、i p 0 、a e t g a n ds oo n i nt h i st h e s i s ，f i r s to fa uw ei n t f o d u c et h em a i nt h o u g h t so ft h e s ef o u rk i n d s0 fm e t h o d s w ea l s 0s u m m 撕z e d 锄dc 0 m p a r e dt h e i r0 w nr a n g e s0 fa p p l i c a t i o na i l db o t ht h e i ra d v a n t a g e s a i l ds h o r t c o m i n g s t l l e nw ea n a l y z et h ec o u r s eo fc o n s t m c t i n gt e s tc a s es e tb yo n h o g o n a l a r r a ym e t h o da l l dc o v e r i n ga a ym e t h o d ，a n dt h e i ra p p l i c a t i o nt ot h ep a i r - w i s et e s t i n g w e 锄a l y z et h ep r o b l e m sw h e nw eu s et h e s em e t h o d si nt h es o f t w a r et e s t i n gt 0g e n e r a t et e s tc a s e s e t ，i n d u d i n gn oa d a p t a b i l i t yb e 俩e e nt h es o f t w a r et e s t i n ga i l dt h em e t h o dt og e n e r a t et e s t c a s es e t ，c o m p l i c a t e da l g o r i t h mt 0c o n s t m c tt e s tc a s es e ta i l dm u c hm o r et e s tc a s e sa i l ds o0 n ， s ow ep u tf 6 n a r dt h ei m p r 0 v e dm e t h o d s h lo r d e rt os o l v ea 铲e a td e a lo fp r o b l e m se x i s t i n gi nt h e s em e t h o d se f f e c t i v e l y ，w e 西v ea k ns o 胁a r et e s t i n g ，w h i c hm e a i l sw ed i v i d et e s ts y s t e m si n t 0f o u rt y p e sa c c o r d i n gt 0 n u m b e r so fp a r a m e t e rk 柚dn u m b e r so ft h e i rv a l u e sn a sf o rt w 0 - v a l u es o f 细a r es y s t 眦，t h i s p a p e rd e s i g i l s 孤a l g o r i t h mt oc o n s t m c tt e s tc a s e s ，b a s e d0 nt h el o n g i t u d i n a lb i n a r ys t r i n gs e t 锄dm e t h o do fc o n t r o l l i n gv a r i a b l e s a sf o r k - ns o f t w a r es y s t e i l l w h i c hni sl a r g e r t h a l l2 a l l dn i sp r i m e0 rp o w e r0 fp r i m e ，w ed e s i g nam e t h o d0 fc o v e r i n ga r r a y0 ft e s ts e tt oc o n s t m c tt e s t s e tb yt a l 【i n g0 n h o g o n a la 1 1 r a ya l l dd e r i v i n ga r r a y sf r o mo r t h 0 9 0 n a la r r a ya i l d 咐0u s e f i l l c o n d i t i o n s a sf o ras o f t w a r es y s t e mw i t hkp a r 锄e t e r sw h o s en - v a l u ei sn o ta ne q u a l ，w e d e s i g na ne x p e r i e n c ea l g o r i t h m t l l l et h e s i sv e r i f i e st h ev a l i d i t yo ft h e s et h r e ek i n d s0 fm e t h o d sw i t ht h ee x p e r i m e n t s f i n a l l y t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h es i z eo ft e s ts e t sf 如mt h em e t h o d sw eg i v ei n t h i sp a p e ri ss u p e r i o r t ot h es i z ef r o mo a m 、q 蝴、i p o ，伽玎g a n dt h ea d a p t a b i l i t yb e m e e n t h es o f t 、7 ，a r et e s t i n g 卸dt h em e t h o dt og e n e r a t et e s tc a s es e th a sb e e ni m p r o v e d 伊e a t l y k e y w o i i d s ：k ns o f t w a r es y s t e m ，t e s tc a s es e t ，c o v e r i n ga 盯a yo ft e s ts e t ，p a r a m e t e r p a i r w i s ec o m b i n a t i o n i l 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了特别 加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究成果。其他同 志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表示了谢意。 作者签名：红导日期：沙移矽 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权保留送 交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以 采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此规定。 刈心燧名：翘卜彬加 上海师范大学硕士学位论文第一章绪论 1 1 论文研究的背景 第一章绪论 测试是软件工程中一个重要且代价昂贵的部分，在测试过程中，由于资金、时间、 人力资源等条件制约，选取一种能覆盖所有参数配对组合的方法是比较困难的。当然， 要覆盖全部配对组合，可用穷尽测试方法测试全部测试案例，但这样会造成效率低下、 耗时过多、人力资源浪费等缺点。 经验及实践表明，参数的配对组合测试【1 】是对各种软件系统测试的一个实际而有效 的方法【2 】1 3 】【4 】，因为多数软件系统的故障是参数相互作用引起的。测试配对要求，对于 系统任何一对输入参数，它们每一个有效值组合必须被至少一个测试案例所覆盖，于是 问题转化为寻找一个尽可能小的测试案例集合，使所有的参数配对组合都能被这个集合 所覆盖。然而，要求得这样一个最优集合是一个n p c 问趔5 1 。 “ 为了简要说明它的概念，我们考察这样一个系统，该系统中有三个参数a ( a 。，a 2 ) 、 b ( b 1 ，b 2 ) 、c ( c l ，c 2 ，c 3 ) ，括号内是每个参数的取值。若采用穷尽测试方法需2 2 3 = 1 2 个案例，即t 1 = ( a 1 ，b 1 ，c 1 ) ，( a 1 ，b 1 ，c 2 ) ，( a 1 ，b 1 ，c 3 ) ，( a 1 ，b 2 ，c 1 ) ，( a 1 ，b 2 ， c 2 ) ，( a 1 ，b 2 ，c 3 ) ，( a 2 ，b l ，c 1 ) ，( a 2 ，b 1 ，c 2 ) ，( a 2 ，b 1 ，c 3 ) ，( a 2 ，b 2 ，c 1 ) ，( a 2 ， b 2 ，c 2 ) ，( a 2 ，b 2 ，c 3 ) ) 。若采用文献【5 】中逐个加入参数直至覆盖所有参数配对组合的 方法，则有t 2 = ( a 1 ，b 1 ，c 1 ) ，( a 1 ，b 2 ，c 1 ) ，( a 2 ，b 1 ，c 2 ) ，( a 2 ，b 2 ，c 3 ) ，( a 2 ，b 1 ， c 1 ) ，( a 1 ，b 2 ，c 1 2 ) ，( a 1 ，b 1 ，c 3 ) ) ；t 3 = ( a 1 ，b 1 ，c 1 ) ，( a 1 ，b 2 ，c 1 ) ，( a 2 ，b 1 ，c 2 ) ， p 乜，b 2 ，c 2 ) ，p 也，b 1 ，c 1 ) ，( a 1 ，b 1 ，c 2 ) ，( a l ，b 1 ，c 3 ) ，p 垃，b 2 ，c 3 ) ) ，t 1 、t 2 和t 3 都覆盖了a 、b 、c 的所有参数组合，但t 1 的个数为1 2 ，t 2 的个数为7 ，t 3 的个 数为8 。显然，测试集越小越好。 国外有关组合参数的测试技术研究以及测试工具的开发已有一些成果和经验，可 以分为启发式方法和代数方法两大类，比较著名的有正交矩阵方法、覆盖矩阵方法、 a e t g 、i p o 组合策略。启发式方法主要有i p o 、a e t g 组合策略等。 l p o 【5 1 【6 】阴：其主要思想是，首先对两个参数组合，得到它们全部的测试案例集合t ， 然后每次加入一个参数，生成一个临时集合，该临时集合包含所有原有参数与新进入参 数所有的配对组合，通过对t 的水平扩展和垂直扩展算法使t 中的测试案例能覆盖所有 临时集合内的配对组合。 1 上海师范人学硕士学位论文第一章绪论 a e t g 【8 】【9 】【1 0 】：a e t g 测试集自动生成系统，初始时是一个空的测试案例集合，每次 往集合中加入一个测试案例，在得到这个测试案例前该系统先产生一组侯选测试案例， 利用贪心法选择其中一个能覆盖最多未覆盖到的参数配对组合。 a e t g 、i p o 属于启发式方法，它们应用于某些软件系统生成测试集时存在以下缺 点：测试集偏大，测试数据规模不好确定。 代数方法主要有正交矩阵方法( o a m ：o n h o g o n a la 玎a ym e t h o d ) 和覆盖矩阵方法 ( c a m ：c o v e 咖ga r r a ym e t h o d ) 。 正交矩阵方法【1 1 】【1 2 】【1 3 1 主要是以拉丁方、正交拉丁方、g a l o i s 域等为基础构造的。它 的优点在于：它在一定程度上改进了穷尽测试方法而能生成较优测试集，大大缩短了测 试时间。它的不足在于：正交矩阵的定义非常严格，它要求每个配对组合在测试案例集 合中出现的次数相同，从而导致构造过程非常复杂。另外，由于其本身构造算法的局限 性使其应用范围受到一定限制，结果会产生相对较多的测试案例。在实际系统中，为了 满足构造算法的要求以及软件系统和测试集生成方法之间的适应性，常常需要添加“无 关值 ，因此也会导致增加额外的测试案例，从而使测试集偏大。 覆盖矩阵方法【1 4 】【1 5 】是以正交矩阵及其派生矩阵为基础构造的。它的优点在于：该方 法能在一定范围内解决正交矩阵中存在的问题，扩大应用范围。它的不足在于：当它应 用于k 2 二值软件系统、k - n 软件系统时的结果却不一定是最优的，软件系统和测试集 生成方法之间的适应性还有待进一步提高。 为了有效解决这些问题，本文首先提出k n 软件系统的概念。所谓k - n 软件系统是 指根据参数个数k 和参数取值个数n 的异同把k n 软件系统分成四类，第一类：k 2 软 件系统即n = 2 的二值软件系统；第二类：k - n 软件系统，n 2 ，n 是素数或素数幂；第 三类：k n 软件系统，n 2 ，n 不是素数或素数幂；第四类：k 个参数且每个参数的取值 个数n 不尽相同的软件系统。对于上述第一类、第二类、第四类软件系统，运用穷尽测 试方法、正交矩阵方法、覆盖矩阵方法、口o 、a e l g 所得测试集都偏大【5 】【8 】1 1 0 】1 1 1 j 【1 5 j 。 本文针对这三类软件系统，提出三种方法来优化测试集，这三种方法是基于正交矩阵方 法和覆盖矩阵方法而提出的。 1 2 课题来源 国家自然科学基金项目“软件参数配对覆盖测试集生成的若干问题研究 ， 2 0 0 7 1 1 2 0 0 9 1 2 3 0 ( 项目编号：6 0 6 7 3 0 6 7 ) 。 2 上海师范大学硕士学位论文第一章绪论 1 3 论文的主要工作 本文在研究正交矩阵方法和覆盖矩阵方法应用于软件系统生成测试集的基础上，总 结了它们在参数配对组合测试应用中存在的问题，并提出了改进方法。 本文对于第一类软件系统引入纵向二进制字符串集合的概念和控制变量法生成测 试集。对于第二类软件系统，设计一种测试集覆盖矩阵方法，它以正交矩阵及其派生矩 阵为基础，并根据本文的两个条件为依据，据此选择不同构造方法来实现。对于第四类 软件系统，设计一种经验算法，主要利用分块设计测试集覆盖矩阵的思想得到完整测试 集。这三种方法能克服正交矩阵方法、覆盖矩阵方法生成测试集时算法的复杂性，简化 构造过程；且这三种方法都能有效减少案例数，得到的结果比口o 、a e t g 、正交矩阵 方法、覆盖矩阵方法更优；并大大提高了软件系统和测试集生成方法之间的适应性。 1 4 论文创新点 本文从理论联系到实际，深入分析了生成测试集的四种策略，通过分析正交矩阵方 法( o 蝴) 、覆盖矩阵方法( 洲) 、口o 、a e t g 的不足方面，提出方法加以改进。 本文的主要创新点如下； ( 1 ) 对于第一类：k 2 软件系统即n = 2 的二值软件系统，提出纵向二进制字符串集合 的概念和控制变量法生成测试集，得到的测试集大小总是小于用o a m 、洲、p o 和 a e t g 得到的。 ( 2 ) 对于第二类：k _ n 软件系统，n 2 ，n 是素数或素数幂设计了一种方法，它以正 交矩阵及其派生矩阵为基础，并根据本文的两个条件为依据，据此选择不同构造方法来 实现，且得到的测试集大小总是小于用0 蝴、洲、口o 和伽玎g 得到的。 ( 3 ) 对于第四类：k 个参数且每个参数的取值个数n 不尽相同的软件系统，主要利用 分块设计测试集覆盖矩阵的思想得到完整测试集，且得到的测试集大小总是小于用 o a m 、渊、口o 和a e t g 得到的。 ( 4 ) 用n e t 工具实现了基于覆盖矩阵方法的测试集自动生成工具。 ( 5 ) 用数学方法证明利用覆盖矩阵方法构造测试集的步骤数确实为s2 1 0 9 棚忙) 1 。 ( 6 ) 给出了基于覆盖矩阵方法的测试集大小的估计范围。 ( 7 ) 用数学方法证明了用覆盖矩阵方法得到的测试集总是小于用正交矩阵方法得到 的。 3 上海师范大学硕十学位论文第一章绪论 ( 8 ) 对于第一类、第二类、第四类系统，给出了直观、有效的计算测试集大小的公 式。并通过实验验证了这些公式的实用性。 1 5 论文结构 本论文共分七个章节，各个章节的安排如下： 第一章是全文的概述，介绍了本论文的背景、意义、主要工作和创新点。 第二章从理论上介绍参数配对覆盖的相关概念。其次通过实验数据说明参数个数k 和参数取值个数n 与测试集生成方法之间存在适应性关系，且提高这种适应性有助于生 成最优测试集。 第三章主要介绍了正交矩阵的定义和性质、三种构造正交矩阵的方法、以及正交矩 阵方法在参数组合测试中的应用。通过分析正交矩阵方法构造测试集的特点和局限性， 提出改进意见，并提出用覆盖矩阵方法加以解决其不足方面。 第四章主要介绍了覆盖矩阵的定义和性质、覆盖矩阵的构造过程和算法及其在参数 组合测试中的应用，给出了覆盖矩阵方法生成测试集的预计范围，同时用数学方法证明 覆盖矩阵方法得到的测试集大小恒定小于正交矩阵方法得到的。最后总结了覆盖矩阵方 法的有效性和不确定性，一方面该方法对正交矩阵方法的三个方面作了改进；另一方面， 通过分析覆盖矩阵方法三个方面的不足，提出进一步的改进意见，优化测试集生成方法。 第五章根据第一类、第二类、第四类，分别提出改进方法用以解决正交矩阵方法、 覆盖矩阵方法、a e t g 、i p 0 等中存在的问题，包括软件系统与测试集生成方法之间 的不适应性、构造测试集的算法复杂、测试集偏大等问题。最后通过实验验证，这三 种方法的有效性。 第六章通过实验，运用本文提出的三种方法和o a m 、洲、a e t g 、口o 进行比 较，并得出结论：用本文三种方法得到的测试案例集合的大小都优于正交矩阵方法、 覆盖矩阵方法、i p o 、a e t g ，而且软件系统与测试集生成方法之间的适应性也大大提 高，并进一步分析了不同软件系统和测试集生成方法之间的适应性对应法则、不同软 件系统和计算测试集大小的公式之间的相互依赖关系。 第七章对论文进行了总结和展望。在强调本文的几项主要工作的同时，还总结了本 文将来的研究方向。 4 第二章软件系统与测试集生成方法之间的适应性关系研究 本章首先从理论上介绍参数配对覆盖的相关概念，给出在含有k 个测试参数的软件 系统中，测试集大小的理论估计范围【1 6 1 。其次通过一组实验数据说明参数个数k 和参数 取值个数n 与测试集生成方法之间存在适应性关系，也就是说对于不同的k - n 软件系统， 我们必须灵活选择适当的测试集生成方法来生成测试集，且提高这种适应性有助于生成 最优测试集。 2 1 基本概念 测试集生成方法，包含两层意思：一是该测试集能覆盖软件系统中的所有参数配对 组合。二是要能生成一个测试集，且该测试集越小越好，这就需要研究测试集的取值范 围。 考察一个含有k 个参数的系统s ( k 2 ) ，对于参数a ，它有n 种取值a o ，a 1 ，a 2 ， a n - l ，则d ( a ) = a o ，a 1 ，a n 1 ) 叫作参数a 的值域。系统s 的两个参数a 和b 的一对取 值a i 、b j 则标记为( a i ，b j ) ( 我们认为( a i ，b j ) 和 ，a i ) 是相等的，0 i ，j n 一1 ) 。系统s 的一个测试案例记作t ，它含有k 个取值，每一个取值属于系统s 的一个参数。若t 在 参数a 位置的取值为a i ，在b 处的取值为b j ，则称t 覆盖了配对组合“，b j ) 。显然对于 系统s 中任意一个测试案例，它能覆盖到k ( k 1 ) 2 对组合。 从配对组合测试的目的出发，将系统s 表示为( t ，p ) ，其中t 是所有可能的测试案 例集合，p 是所有参数值的配对组合的集合。一个满足配对覆盖的测试集t 是t 的一个 子集，且对于任意一对组合( a i ，b i ) p ，t t 中至少存在一个测试案例t 将其覆盖，我们用 i t t l 表示t 中含有的测试案例总数。配对覆盖问题就是：对于一个给定系统，找到一个满 足配对覆盖要求且i t l i 为最小的测试集t 。 文献【5 】中已经指出配对覆盖是一个n p c 问题，且文献同时表明虽然要求一个最优 的配对覆盖测试集是一个n p c 问题，但仍然可以估计配对覆盖测试集的大小是在一定 范围之内，并得出以下结论： 给定一个带有k 个测试参数的系统，假设每个参数有n 种取值，则必定在一个满足 配对覆盖的测试集t ，且t 在区间为【n 2 ，l l o g ( ) l o g ( 1 1 刀2 ) + 1 l 】的范围之内，其中 n = k ( k 1 ) 2 n 2 。 。 s 上海师范人学硕十学位论文第二章软件系统与测试集生成方法之间的适应性关系研究 但在实际情况下，往往每个参数的取值个数不都相同，根据上述结论可得到用于实 际系统的，估计其配对覆盖测试集大小的结论： 在一个实际含有k 个测试参数的软件系统中，各参数的取值个数可以不同，令测试 参数按其取值个数从大到小排列为1 1 0 ，n 1 ，n k 1 ，则在范围 d ( i l o ) d ( n 1 ) ， i l o g ( ) l o g 【1 1 d ( ，l 。) 2 ) + 11 内一定存在满足配对覆盖的测试集t ，其中n = k ( k 一1 ) 2 d ( n o ) z 。 关于这两个结论的证明可参见文献 8 和 1 6 ，这里不在赘述。测试案例集合范围 大小的理论估计意义在于：当测试计划制定时，具体实施之前，就可预计出测试可能花 费的代价，从而使测试管理人员能预先进行控制和调整；同时也易于我们评价算法的有 效性。但是这个测试集大小的取值范围过于笼统，没有可针对性，当其应用于所有k n 软件系统时并不具备实用性，存在准确性较低、误差偏大等问题。 2 2 软件系统与测试集生成方法之间的关系研究 目前存在的测试集生成方法主要有0 a m 、洲、a e t g 、口o 组合策略等。当某 一种生成方法应用于某一类软件系统时结果是较优的，而应用于另一类软件系统时结 果却很不理想。例如，蝴、洲、a e t g 、i p o 分别应用于四个样本软件系统时 【5 】【1 吵5 】【1 7 1 ，可以看出： ( 1 ) o 舢v i 较适合软件系统s 1 ，q 蝴较适合软件系统s 1 、s 2 、s 5 ，a e t g 较适合 软件系统s 5 ，i p o 较适合软件系统s 1 。 ( 2 ) 对于不同的软件系统，选取一种适合的测试集生成方法生成测试集会得到理想 的结果；否则，会造成测试集偏大等问题。 ( 3 ) 有必要对软件系统进行分类，并为每一类软件系统设计一种最合适的测试集生 成方法，提高软件系统与测试集生成方法之间的适应性。 ( 4 ) 在2 1 节中我们给出了测试集大小的一个取值范围，但遗憾的是这个取值范围 没有针对性，也就是说它虽能应用于所有的软件系统，但对于大部分软件系统来说取值 范围太大，没有准确性，存在较大误差，从而导致这个取值范围在实际软件系统中的应 用性不强。 6 1 a b l e2 1a p p l yf o u rn l e t h o d si n c l u d i n go a m 、( a m 、a e l g 、口0t of o l l fs a m p l es o f 耐a 陀s y s t e m s 表2 1o a m 、c a m 、削巳1 g 、i p o 分别应用于四个样本软件系统 一 s 1s 2s 3s 4s 5 _ 懿 o a m9 1 84 84 81 6 c a m91 54 03 0l l a e t g1 11 54 1 2 8 1 2 i p 0 92 03 42 71 5 s 1 ：4 - 3 软件系统； s 2 ：1 3 3 软件系统； s 3 ：6 1 个参数，其中1 5 个4 值参数，1 7 个3 值参数，2 9 个2 值参数； s 4 ：7 5 个参数，其中1 个4 个参数，3 9 个3 值参数，3 5 个2 值参数； s 5 ：3 1 2 软件系统。 2 3 软件系统与测试集生成方法之间的适应性原则 通过分析洲、洲、a e t g 、i p o 在软件系统中生成测试集时存在的问题，包 括软件系统与测试集生成方法之间的不适应性、构造测试集的算法复杂、计算测试集大 小的公式以及取值范围应用性不强、测试集偏大等问题，我们发现，不能单一地把洲 或者q 气m 或者一个测试集生成方法应用于所有k n 软件系统，这样就忽视了软件系统 与测试集生成方法之间的适应性关系，继而会造成测试集偏大。 本文首先根据k 和n 的特点提出了k - n 软件系统这一概念对软件系统进行分类，且 k n 软件系统是研究测试集生成方法的重要基础和依据。然后提出软件系统与测试集生 成方法之间的适应性关系原则： ( 1 ) 软件系统与测试集生成方法之间的生成方法要有适应性，以便优化测试集。 ( 2 ) 软件系统与测试集生成方法之间计算测试集大小的公式要有适应性，测试集大 小的取值范围要有较强的应用性，以便提高计算公式的准确性和取值范围的实用性，减 少误差。 在k - n 软件系统的基础上，根据软件系统与测试集生成方法之间的适应性关系原则， 我们提出了针对三类软件系统的测试集生成方法。并通过论文第六章的实验及分析来深 入说明k n 软件系统的提出对于研究测试案例集合的生成方法有重大意义。 为此，本文根据实际软件系统的特点，主要提出以下三条改进建议： ( 1 ) 根据k n 软件系统的分类原则，针对三类软件系统设计了三种测试集生成方法， 并给出相应算法，以及实验结果分析。 7 上海师范人学硕士学位论文第二章软件系统与测试集生成方法之间的适应性关系研究 ( 2 ) 对于不同的k n 软件系统，给出计算测试集大小的公式和取值范围，使其能较 准确的估计测试集大小的范围。 ( 3 ) 对于不同的k n 软件系统提出不同的测试集生成方法，可以方便测试人员灵活 选择生成方法，减少测试案例数，提高软件系统与测试集生成方法之间的适应性。 我们研究软件系统与测试集生成方法之间的适应性关系，其最终目的就是为了构造 最优测试集，这就必须首先分析目前几种生成方法的的构造过程、应用范围、局限性等， 并对各种不同方法进行比较和分析，然后找出不同软件系统与测试集生成方法之间的最 佳匹配关系。下一章首先介绍一种有效的参数配对覆盖测试集生成策略正交矩阵方 法，研究它的构造方法及其在参数组合测试中的应用。 8 第三章正交矩阵及其在参数组合测试中的应用 本章首先介绍了正交矩阵的定义和性质，与正交矩阵相关的数学理论知识，如拉丁 方、正交拉丁方、有限域等概念。其次，介绍了三种构造正交矩阵的方法、以及正交矩 阵方法在参数组合测试中的应用。最后，通过分析正交矩阵方法构造测试集的特点和局 限性，提出改进意见，并提出用覆盖矩阵方法加以解决其不足方面。 3 1 正交矩阵的定义和性质 正交矩阵【1 5 】【1 8 】方法构造测试集可以大大减少案例数，其特点非常适用于软件系统测 试。下面首先给出正交矩阵的定义。 3 1 1 正交矩阵的定义 定义3 - 1 正交矩阵记作o ( p ，k ，n ，t ) 表示，它要求矩阵中每个t 维组合出现次数相同。其中： p 表示矩阵的行数，也就是测试案例的数目。 k 表示矩阵的列数，也就是参数个数。 n 表示每个参数的取值个数。矩阵中每个参数的n 个值通常用逻辑值0 ，1 ，n 1 表示。 t 表示维数，如果t = 2 ，表示构造的矩阵可以覆盖所有配对组合。本文重点研究强度 t = 2 的情形。在正交矩阵中，矩阵中每个参数的n 个值通常用逻辑值0 ，l ，n 1 表示。 例如，在一个远程通信网络中有4 个参数，分别是c a l l i n gp h o n e ，c a ut y p e ，s w i t c h m a r k e t ，s t a t u s ( 逻辑上，可分别用o ，1 ，2 ，3 表示这4 种参数) ，每个参数都有3 种 取值，各参数的取值见表3 1 。 t 曲l e 3 - 1t h et e s t i n gp a r a m e t e r so ft h el o n g - r 孤g et e l e c 0 姗u n i c a t i o n 北t 、) l r o r k 表3 1 远程通信网络测试参数 0 = c a l l i n gp h o n e l = c a nt y p e2 = s w i t c hm a r k e t3 = c a l l e dp h o n e 0 = r e g u l 缸 0 = l o c a lo = c a n a d a o r e g u l a r 1 = w i r e l e s s 1 = l o n gd i s t a n c e 1 = u s1 = w b r e l e s s 2 = p u b l i c 2 = i n t e m a t i o n a l2 = m e x i c 0 2 = p a g e r 如果用穷尽测试的方法，需要测试8 1 个测试案例，该实例说明了一个实际问题： 当待测系统有很多参数，且每一个参数有很多可能的取值，则生成和测试全部测试案例 是不太可能做到的。所以，我们需要一种有效的方法来选择一个较小的测试案例集合。 9 上海师范人学硕士学位论文 第三章上e 交矩阵及其在参数组合测试中的应用 若我们采用正交矩阵方法来构造测试集，则测试案例集合如表3 2 所示。 t a b l e 3 - 2n e o n h o g o n a la m yo ( 9 ，4 ，3 ，2 ) w i t hf o u rp a r a i i l e t e r sa n dt h r e ev a l u e sf o re a c h 表3 - 24 个3 值参数的止交矩阵0 ( 9 ，4 ，3 ，2 ) 测试案例编号参数0参数1参数2参数3 00000 101 1 1 20222 3 1 0 12 411 2 o 51201 6 2 0 21 7 2 1 0 2 8221o 观察上表发现，正交矩阵中的每一行代表一个测试案例，每一列代表一个参数。仅 用9 个测试案例就覆盖了全部配对组合。可见，正交矩阵方法在软件系统中具有一定的 应用价值。 3 1 2 正交矩阵的性质 由正交矩阵的定义和上述实例可知，正交矩阵的特点非常适合于参数组合测试，下 面就来介绍它的一些重要性质f 1 5 】【1 9 】【2 0 】【2 1 l 。 性质3 1 均匀分散性质 正交矩阵的每一列中，不同的参数值出现次数相同；任意t 列的各种不同参数值组合 出现的次数也相同。也就是说，如果在矩阵中任取一个p x t 的子矩阵，得到的n 1 个t 维参 数值组合出现的次数必须相同，我们把这个性质叫做正交矩阵的“均匀分散性质。 例如在表3 2 中，每一列都有3 个不同的逻辑值，在每列中它们各出现3 次。 性质3 2 参数独立性 在一个正交矩阵o q ，k ，n ，t ) 中，通常用逻辑值 0 ，1 ，k - 1 ) 表示k 个参数，由于 参数是相互独立的，我们可用 0 ，1 ，k 1 ) 的任意排序表示这k 个参数，而不影响 正交矩阵的其他性质。 例如，在正交矩阵o ( 9 ，4 ，3 ，2 ) 中，我们用 0 ，1 ，2 ，3 】分别表示 c a l l i n g p h o n e ，c a l l t y p e ，s w i t c hm a r k e t ，c a l l e dp h o n e ) 这4 个参数，我们同样也可以用 2 ，3 ，0 ，1 ) 表示这 4 个参数，得到的矩阵仍然是一个正交矩阵。 性质3 3 行列独立性 在一个正交矩阵o q ，k ，n ，t ) 中，任意互换其中的两行或两列，它仍然是一个正交矩阵。 1 0 上海师范大学硕士学位论文第三章正交矩阵及其在参数组合测试中的应用 这是由“均匀分散 的性质决定的，因为在互换其中的两行或者两列后，任选一个 p t 的子矩阵，得到的n t 个t 维组合中的每一个组合出现的次数相同。因此，它仍然是 一个正交矩阵。 例如在正交矩阵o ( 9 ，4 ，3 ，2 ) 中，把第1 行和第2 行互换，或者把第1 列和第2 列 互换，我们发现它仍满足正交矩阵的定义，它还是一个正交矩阵。 性质3 4 子矩阵不变性 移除正交矩阵中的一列后的新的子矩阵仍是一个正交矩阵，结果仅仅是少了几个t 维组合。 例如，在正交矩阵o ( 9 ，4 ，3 ，2 ) 中，移除第1 列后的矩阵为9 3 ，当t = 2 时，有c 。2 3 2 = 2 7 个配对组合，比没有移除前的c 4 2 x3 2 = 5 4 个配对组合少了2 7 个，但它仍然是一个 正交矩阵。换句话说，系统有k 个参数，构造的正交矩阵至少有k 列，而不是恰好有k 列。而移除一列不会影响测试案例数。但是在实际测试过程中，对于一个已生成韵正交 矩阵，有时需要增加一个新参数即增加列数，此时很可能需要添加新的测试案例即增加 行数来满足配对覆盖要求是显然的。 一个正交矩阵对应一个测试案例集合。正交矩阵是以若干个相互正交的拉丁方为基 础构造的，当n 是素数或素数幂时总存在o ( n 2 ，n + 1 ，n ，2 ) 。 “ 为了构造正交矩阵，首先要介绍关于正交矩阵的数学理论基础拉丁方、正交拉 丁方、有限域等概念。 3 2 相关的数学理论知识 定义3 2 拉丁方【2 2 】【2 3 】【2 4 j 由0 ，l ，n 1 构成的n n 方阵( a i j ) n n ，要求每行及每列0 ， a - 旺三刁b - g 量习c - 匡丢兰 对组合的测试集【冽【矧。单独一个n n 的拉丁方可以构造由3 个参数组成，每个参数带 上海师范人学硕士学位论文第三章正交矩阵及其在参数组合测试中的应用 一个测试案例，而整个方阵就组成了覆盖所有参数两两配对的测试集。例如上述3 阶的 拉丁方a ，阴影处所示的测试案例为( 2 ，l ，0 ) ：其中行号为2 ( 表示参数o 取值为2 ) ， 列号为1 ( 表示参数1 取值为1 ) ，元素值0 ( 表示参数2 取值为0 ) 。 当一个系统有3 个以上参数时，需用一组正交拉丁方来构造测试集。 定义3 3 正交拉丁方f 2 2 】【2 3 】【2 4 】设a = ( a i j ) n 。n ，b = ( b i j ) 。是两个n n 的拉丁方，若矩阵 ( ( a i j ，b i j ) ) 。n 中的n 2 个数偶互不相同，i ，j = o ，1 ，n 1 ，则称a 和b 正交，或a 和b 是互 相正交的拉丁方。 例如，将a 、b 叠合在一起，得到复合矩阵d ： f ( o ，o ) ( 1 ，1 ) ( 2 ，2 ) 1 d = i ( 1 ，2 ) ( 2 ，o ) ( o ，1 ) l l ( 2 ，1 ) ，2 ) ( 1 ，o ) 图3 2 两个3 阶拉丁方a 、b 构成复合矩阵d 的实例 f i g l l r e 3 - 2t h ei n s t a i l c eo fc o m p o u n da r r a yd6 f o m 船ol a t i ns q u a r e sa 、b w i t h3s t e p s 9 个配对组合( 0 ，0 ) 、( 0 ，1 ) 、( 0 ，2 ) 、( 1 ，0 ) 、( 1 ，1 ) 、( 1 ，2 ) 、( 2 ，0 ) 、( 2 ，1 ) 、( 2 ， 2 ) ，正好各出现在上面复合方阵中一次。符合定义3 3 ，故a 、b 是一对3 阶的正交拉丁方。 将b 、c 叠合在一起，也得到一个复合矩阵e ： f 固，磅 ( 1 ，2 ) ( 2 ，o ) 1 e = l ( 2 ，o ) ( o 1 ) ( 1 ，2 ) i l ( 1 ，2 ) ( 2 ，o ) 固，l 圳 图3 3 两个3 阶拉丁方b 、c 不能构成正交拉丁方的实例e f i g l l r e 3 31 1 1 ei i l s t a i l c eo fc o m p o u n da r r a ye 丘o mt 、) l ，0l a t i ns q u a r e sb 、cw i t h3s t e p s 该方阵中9 个组合不是都正好出现一次，例如( 0 ，0 ) 就没有出现，而( o ，1 ) 却出现三次， 故b 、c 不正交。 根据文献【2 2 】可知，对于参数取值个数n 为素数或素数幂，且参数个数恰好为k = n + 1 的软件系统，总有k 2 = n 1 个正交拉丁方可用于构造该系统的测试集，且测试集大小为n 2 。 由此构成的方阵中每个元组代表k 2 = n 1 个参数的取值，另两个参数的取值为该元组的所 处复合方阵中的行列值，从而构成了覆盖这k 个参数两两配对组合的测试集。例如若待 测系统有4 个参数，每个参数带有3 种取值( 用0 ，1 ，2 表示) ，则需要2 个正交拉丁方叠 合在一起得到复合矩阵。 例如，拉丁方a 和b ，经复合后得到拉丁方d ，如图3 2 所示。复合方阵d 中阴影的元 组代表测试案例( 2 ，1 ，0 ，2 ) ，其中行号为2 ( 表示参数0 取值为2 ) ，列号为1 ( 表示参数1 取值为1 ) ，二维元组为( o ，2 ) ( 表示参数2 、参数3 取值分别为0 、2 ) ，表3 2 为此待测系 统覆盖所有配对组合的测试集。 表3 2 中的每个元素、每个配对组合出现次数均相同，符合正交矩阵定义和形式， 1 2 上海师范大学硕士堂鱼鲨塞蔓三童垂銮堑堕壁基垄叁墼丝全型堕生箜查旦 - _ - _ - _ _ _ _ _ _ - - - - _ _ - _ _ - _ - _ _ - _ - - 。o 。o 。一 故表3 2 实质上是一个正交矩阵，并可记作o ( 9 ，4 ，3 ，2 ) 。正交矩阵是以正交拉丁方为基础 构造的，下一节将通过一个具体实例来介绍正交拉丁方及其构造过程。 3 3 利用g a l o i s 域构造正交矩阵 3 3 1 利用同余类方法构造g a l o i s 域 为了构造正交拉丁方，需引入有限域的概念，并给出构造g a l o i s 域的两种方法。第 一种方法叫做同余类法，第二种叫做系数组合法。 设p 是一素数，f = g f ) = 0 ，1 ，p - 1 ) 在m o dp 的意义下关于“+ ”，“，运算构 成有限域，用g f ( p ) 表示。 多项式：p ( x ) = a o + a l x + + a k x k ，a i f ，i = o ，1 ，k 。如果f 的元素个数为p ，则 不同的多项式p ( x ) 的个数为p k + 1 ，即p ( x ) 和k + 1 位p 进制数a k a k - l a 2 a l a 0 一一对应。 例如f = g f ( 2 ) = 0 ，1 ) ，二次以下的多项式集合g f 【2 ，x 】包括： p 0 0 0 ( x ) = o ， p 1 ( x ) = l ， p o l o ( x ) = x ， p o l l ( x ) = x + l ， p 1 0 0 ( x ) = x 2 ， p 1 0 1 ( x ) = x 2 + 1 ， p 1 1 0 ( x ) = x 2 + x ， p 1 1 1 ( x ) = x 2 + x + 1 。 若p 是素数，系数在g f ( p ) 中的多项式集合用g f 【p ，x 】表示。若p ( x ) 和q ( x ) 都是属于 g f 【p ，x