Lect06A-测试的理论基础.ppt

1、理论基础,测试用例设计的理论依据,主要内容,简单图论知识 覆盖准则,简单图论知识,无向图 图G=，其中V=n1, n2, , nm为有限非空集合，称为顶点集，ni为顶点，E=e1, e2, , ek为有限集合，E称为边集，ei称为边。 ei=(u,v)为无序顶点对，称ei为无向边，若任意eiE都是无向边，则G称为无向图。,n1,n2,n3,n4,n5,n6,n7,e1,e2,e3,e4,e5,e6,无向图相关定义,节点的度：节点n的度定义为该节点作为顶点的边的数目，记为deg(n) 路径：路径是一系列边的序列，该序列中任何连续的两个边都存在一个公共的顶点。,无向图相关定义,连接性：节点ni、n

2、j是连接的，当且仅当ni、nj在同一条路径上。 组件：图的组件是相连节点的最大集合 图G的圈复杂度V（G)en2p，其中e为G的边数，n为节点数，p为组件数。,有向图,有向图： 图G=，其中V=n1, n2, , nm为有限非空集合，称为顶点集，ni为顶点，E=e1, e2, , ek为有限集合，E称为边集，ei称为边。 ei=为有序顶点对，称ei为有向边，若任意eiE都是有向边，则G称为有向图。,n1,n2,n3,n4,n5,n6,n7,e1,e2,e3,e4,e5,e6,有向图,节点n的入度：有向图G中以n作为终点的边数目 节点n的出度：有向图G中以n作为起点的边数目 路径p是一个有向边的

3、序列：相邻两条边满足前一条边的终点是后一条边的起点。,有向图,环路是一个开始节点与结束节点相同的有向路径 3-连接：有向图的两个节点ni、nj，当且仅当从ni到nj有一条路径，且nj到ni有一条路径。 强组件：有向图的强组件是3-连接节点的最大集合。如n1n3n7 n2 n5 n6n4,n1,n2,n3,n4,n5,n6,n7,e1,e2,e3,e4,e5,e6,n1,s1,n3,n4,n7,e1,e2,e5,覆盖准则,路径覆盖准则 数据流覆盖准则 逻辑覆盖准则 输入空间的划分准则,覆盖准则,测试需求：是软件制品（artifact）的一个特殊元素，测试用例必须要满足或覆盖它。 测试需求通常成套

4、出现，以TR表示一测试需求集合。 如目标是覆盖程序中所有判断，则每个判断导致两个测试需求：判断成真、判断成假。 若目标是每个方法被调用一次，则每个方法对应一个测试需求。,覆盖准则,覆盖准则：将测试需求加在一个测试集上的一个或一组规则。测试准则以一种完整明确的方式描述测试需求。 覆盖：对于覆盖准则C，给定一组测试需求TR，测试集T满足C是指当且仅当对于每一个TR中的测试需求tr，T中至少存在一个测试t，使t满足tr。,T,TRC,覆盖准则就是测试需求的抽象描述,覆盖准则,覆盖率：给定一组测试需求TR和一个测试集T，覆盖率是被T满足的测试需求的数量与TR大小的比率。 有时满足覆盖准则代价昂贵，则满

5、足覆盖率，如所有路径覆盖 有些需求是不能被满足的，如无法到达的代码,测试准则,准则包含性：若每个测试集T在满足覆盖准则C1的同时，也满足覆盖准则C2，则称C1包含C2。 C1的测试需求集是C2测试需求集的一个扩展，或者C1的测试需求与C2的测试需求之间存在一个多对一的映射。 直觉上， 测试准则C1包含C2，C1应该能够揭示更多错误。,图覆盖准则,图G(N,N0,Nf,E)，其中N为节点的非空集合，N0是始节点的非空集合，Nf是终节点的非空集合，E是边的集合，E是NxN的子集。边记为，ni为前驱，nj为后继。 一条路径是节点的序列，其中相邻的节点是图G的一条边。路径长度定义为所包含边的数量。子路

6、径是路径p的子序列。,图覆盖准则,节点可达：如果存在一条从节点ni到n的路径，称节点n为从节点ni开始可达的。 reachG(x)：是从参数x开始可达的。参数可以是一个节点、一条边或节点集合 reachG(n)是G的一个子图。 reachG(N0)是G的一个子图，它是从始节点可达的,图覆盖准则,测试路径：从N0中某节点开始到Nf中某节点结束的一条路径称为一条测试路径。 如果节点n在测试路径p中，则称测试路径p访问节点n；如果边e在测试路径中，则称测试路径p访问边e。如果q是测试路径p的子路径，则称测试路径遍历子路径q。,pathG(t)表示测试用例t所执行的图G的测试路径。 path(T)表示

7、测试集T测试所执行的测试路径的集合，path(T)=path(t)|tT,图覆盖准则,n0,n1,n3,n2,ab,a=b,ab,t1(a=0,b=1) p1:n0,n1,n3,n2 t2(a=1,b=1) p2:n0,n3,n2 t3(a=2,b=1) p3:n0,n2,图覆盖准则,图覆盖：给定一个关于图G的准则C的测试需求集合TR，测试集合T在图G上满足准则C当且仅当对TR中每个测试需求tr，path(T)中至少存在一条测试路径p满足tr。,结构化覆盖准则,涉及控制流的准则称为结构化覆盖准则 节点覆盖： 节点覆盖准则NC：TR包含图G中每个可达的节点 测试集合T满足图G上的节点覆盖准则当且

8、仅当N中每个语法可达节点n在path(T)存在一条路径p，p访问n。 TR包含图G中长度为零的可达路径,结构化覆盖准则,边覆盖（EC）：TR包含图G中长度不大于1的可达路径。 测试集合T满足图G上的边覆盖准则当且仅当E中每个语法可达边e在path(T)存在一条路径p，p访问e.,n0,n1,n2,xy,xy,path(t1)=n0,n1,n2 path(t2)=n0,n2 T=t1满足节点覆盖 T=t1,t2满足边覆盖,结构化覆盖准则,简单路径：如果从ni到nj的一条路径中，除了始节点和终节点可以相同外，没有任何节点出现次数多于一次，则该路径为简单路径。 简单路径没有内部环，但整个路径本身可以

9、形成一个环。,结构化覆盖准则,主路径：如果从ni到nj是一条简单路径，并且它不作为任何其他简单路径的子路径出现，则称之为主路径。,n0,n1,n2,n4,n3,n0,n1,n2 n0,n1,n3,n4 n1,n3,n4,n1 n3,n4,n1,n3 n4,n3,n1,n4 n3,n4,n1,n2,结构化覆盖准则,主路径覆盖（PPC）准则：TR包含图中每一条主路径。,n0,n1,n2,n4,n3,n0,n1,n2 n0,n1,n3,n4 n1,n3,n4,n1 n3,n4,n1,n3 n4,n3,n1,n4 n3,n4,n1,n2,path(t1)=n0,n1,n2 path(t2)=n0,n1

10、,n3,n4,n1,n3,n4,n1,n2 T=t1,t2满足主路径覆盖,结构化覆盖准则,完全路径覆盖（CPC）：TR包含图中的所有路径。 如果图G中存在循环，则完全路径覆盖无效，因为路径数量无穷多，测试需求也无穷多。,结构化覆盖准则,指定路径覆盖（SPC)：TR包含一个测试路径集S，S为指定参数。,n0,n3,n1,n2,主路径:n0,n1,n3,n0,n2,n3 path(t1)=n0,n1,n3 path(t2)=n0,n2,n3 T=t1,t2满足主路径覆盖 T满足完全路径,n0,n1,n2,n4,n3,path(t1)=n0,n1,n2 path(t2)=n0,n1,n3,n4, n

11、1,n3,n4,n1,n2 T=t1,t2满足主路径覆盖,结构化覆盖准则,遍历：测试路径p遍历子路径q，当且仅当q是p的一个子路径。 边路遍历：测试路径p边路遍历子路径q，当且仅当q中的每一条边以同样的顺序出现在p中。 绕路遍历：测试路径p绕路遍历子路径q，当且仅当q中的每个节点以同样的顺序出现在p中。,结构化覆盖准则,s0,sf,a,b,d,c,设q=a,b,d p=s0,a,b,c,b,d,sf没有遍历q，因为q不是p的子路径 但是p边路覆盖q，因为边,以同样顺序出现在p中,结构化覆盖准则,s0,sf,a,b,d,c,s0,sf,a,b,d,c,s0,a,b,c,b,d,sf边路覆盖q=a

12、,b,d， 从一个节点b离开，经一个环又回到相同的b节点，将环b,c,b压缩为节点b之后就满足了遍历的条件,s0,a,b,c,d,sf绕路覆盖q=a,b,d， 从一个节点b离开，绕过边直接到子路径的下一个节点，所以子路径b,c,d是a,b,d的一个绕路。,结构化覆盖准则,边路覆盖、绕路覆盖是解决由于循环引起的无限路径问题。例如：如果前图中循环b,c,b是do-while循环，一次都不执行不可能，导致a,b,d子路径不可能被遍历。,结构化覆盖准则,寻找主路径算法： 1.长度为0的路径（即可达节点）； 2.扩展出长度为1的路径（即可达边）； 3.逐步扩展，直到不能扩展出新路径为止。扩展过程中不能扩

13、展的路径为可能的主路径。 4.按照主路径的定义进行筛选即可。,结构化覆盖准则,1,2,4,6,3,5,7,1.长度为0的路径：1,2,3,4,5,6,7# 由于节点7是终节点，不能扩展。 2.扩展出长度为1的路径： 1,2,1,7#,2,3,2,4,3,2 4,5,4,6,5,6,6,1 3.扩展出长度为2的路径：1,2,3 1,2,4 2,3,2* 2,4,5 2,4,6 3,2,3* 3,2,4 4,5,6,4,6,1,5,6,16,1,2 6,1,7# *标注路径是环，不能进一步扩展,结构化覆盖准则,4.找长度为3的路径：1,2,3扩展为1,2,3,2是不合适的扩展，因为2出现两次，且不

14、是始点、终点，不是简单路径 1,2,4,5 1,2,4,6, 2,4,5,6 2,4,6,1 3,2,4,5 3,2,4,6 4,5,6,1 4,6,1,2 4,6,1,7# 5,6,1,2 5,6,1,7# 6,1,2,3 6,1,2,4,结构化覆盖准则,5.找长度为4的路径：1,2,4,5,6 1,2,4,6,1* 2,4,5,6,1 2,4,6,1,2* 2,4,6,1,7# 3,2,4,5,6 3,2,4,6,1 4,5,6,1,2 4,5,6,1,7# 4,6,1,2,3 4,6,1,2,4* 5,6,1,2,3 5,6,1,2,4 6,1,2,4,5 6,1,2,4,6*,结构化覆

15、盖准则,6.找长度为5的路径：124561* 245612* 245617# 324561 324617# 456123 456124* 561245* 612456* 7.找长度为6的路径：3245617#,结构化覆盖准则,8.扩展结束，过程中所有、*的路径是可能的主路径，然后删除非主路径即可。 232 323 12461 24612 46124 61246 124561 245612 324617 456124 561245 612456 3245617 进一步得出测试路径：12323245617 124561245617 12324617 1246124617,数据流覆盖准则,为充分测试

16、程序，应该关注数据值的流动，以数据定义（def变量值被写入内存）、使用（use变量的值被访问）来描述数据值从定义位置传递到使用位置，称为du路径。 假设涉及判断的变量在关联的边上使用。,n0,n1,n2,n3,ab,a=b,ab,def(n0)=a,b,use(n2)=a,b,use(n0,n1)=a,b,数据流覆盖准则,定义清除路径：从位置li到lj的路径是关于变量v定义清楚路径是指，如果对于路径上每个节点nk和每条边ek，ki且kj，v不在集合def（nk）和def（ek）中。 定义清除路径表明从li到lj变量v没有改变，称为在li定义的变量到达了lj的使用。,数据流覆盖准则,du遍历：如

17、果测试路径p遍历关于v的子路径q，并且p与q相对应的部分是关于v的定义清除路径，则称测试路径p为du遍历v的子路径q。,数据流覆盖准则,关于变量v的du路径是一条简单路径，该路径是关于变量v从节点ni到节点nj定义清除的，其中v在集合def(ni)和use(nj)中。 定义路径集du(n,v)是从节点n开始的关于变量v的du路径集合。 全定义覆盖（ADC）：对于每一个“定义路径”集合Sdu（n，v），TR至少包含S中的一条路径,n,vdef(n),n1,n2,nk,vuse(ni),数据流覆盖准则,“定义对”集du(ni，nj，v)作为关于从节点ni开始到节点nj结束的变量v的du路径集合。

18、全使用覆盖（AUC)：对于每一个“定义对”集合S=du(ni,nj,v)，TR至少包含S中的一条路径。,n,vdef(n),n1,n2,nk,vuse(nm),nm,数据流覆盖准则,全du路径覆盖（ADUPC)：对于每一个“定义对”集合Sdu(ni,nj,v),TR包含S中的每一条路径。,n,vdef(n),n1,n2,nk,vuse(nm),nm,数据流覆盖准则,0,1,2,3,4,5,6,def(0)=x,use(5)=x,use(4)=x,全定义ADC：0,1,3,4 全使用AUC：0,1,3,4 0,1,3,5 全du路径ADUPC：0,1,3,4 0,1,3,5 0,2,3,4 0,

19、2,3,5,图覆盖之间的包含关系,完全路径覆盖 CPC,主路径覆盖 PPC,双边覆盖 EPC,边覆盖 EC,完全回路覆盖 CRTC,简单回路覆盖 SRTC,全使用覆盖 AUC,全定义覆盖 ADC,节点覆盖 NC,全du路径覆盖 ADUPC,逻辑覆盖准则,逻辑谓词和子句 谓词：由布尔变量、比较运算、逻辑运算构成的表达式。 等价 异或 子句：不包含任何逻辑操作符的谓词，如 谓词(a=b)Cp(x)包含三个子句：关系表达式(a=b)，布尔变量C和函数引用p(x),逻辑覆盖准则,P为谓词集合，C为P的子句集合，每个谓词pP，Cp为p的子句集合。 谓词覆盖（PC)：每个谓词pP，TR包含两个需求条件：p

20、成真、p成假。 谓词覆盖对应图覆盖的边/分支覆盖。 (a=b)Cp(x) a:4 b:4 C:true p(x):true a:x b:x C:false p(x):false,逻辑覆盖准则,子句覆盖(CC)：对于每个cC，TR包含两个需求条件：c取真值、c取假值。 (a=b)Cp(x) a:5 b:5 C:true p(x):true a:5 b:6 C:false p(x):false 子句覆盖并不意味着谓词覆盖，反之亦然 （CC）ab a:T b:F a:F b:T 谓词T （PC) ab a:T b:F a:F b:F,逻辑覆盖准则,组合覆盖（CoC)：对于每个pP，TR要求Cp中的每

21、个子句均可取得真值组合中的每种可能情况。,逻辑覆盖准则,子句判定谓词：在某些条件下，如果改变子句的取值，谓词取值也随之改变，则称该子句判定谓词。即子句决定谓词 当前关注的子句称为谓词的主子句，其他子句称为次子句。 p=ab 如果b为假，那么a判定p，因为p的取值取决于a的取值。,逻辑覆盖准则,活动子句覆盖（ACC)：对于每个pP及每个主子句ciCp，选择次子句cjCp (ij)使得ci判定p。TR对每个ci要求：取真值、取假值。 如p=ab，a判定p（此时b:F），同样b判定p（此时a:F），据此，三组取值（ a:T b:F a:F b:F a:F b:T）满足ACC要求。,逻辑覆盖准则,一般

22、活动子句覆盖（GACC)：对于每个pP及每个主子句ciCp，选择次子句cjCp (ij)使得ci判定p。TR对每个ci要求：取真值、取假值。当ci取真值、假值时，次子句cj的取值不必相同。 GACC不一定包含谓词覆盖，如p=ab，对于b的任意取值，a判定p，当a:T时，取b:T，当a:F时取b:F(GACC不要求不取相同值)，对于b也同样取值，得到两组TT，FF，而p均为T，没有满足覆盖谓词。,逻辑覆盖准则,相关活动子句覆盖（CACC)：对于每个pP及每个主子句ciCp，选择次子句cjCp (ij)使得ci判定p。TR对每个ci要求：取真值、取假值。当ci取真值、假值时，次子句cj的取值满足：

23、主子句ci取某个值时p为真，取另一值时p为假。 p=ab，对于b的任意取值，a判定p，当a:T时，取b:T，谓词为真，当a:F时要求p取假值，即b:T。最终CACC测试集TT,FT+TT,TF,练习：p=a(bc),逻辑覆盖准则,受限活动子句覆盖（RACC）：对于每个pP及每个主子句ciCp，选择次子句cjCp (ij)使得ci判定p。TR对每个ci要求：取真值、取假值。当ci取真值、假值时，次子句cj的取值必须相同。 p=ab，a为主子句（假定b:T)得到a:T b:T; a:F b:T；b为主子句（假定a:T)得到a:T b:T; a:T b:F p=a(bc)，a为主子句（假定b:T c

24、:F）得到TTF, FTF，此时假定还有两种取值TT、FT，都可以满足a为主子句时RACC覆盖。,逻辑覆盖准则,非活动子句覆盖（ICC）：对于每个pP及每个主子句ciCp，选择次子句cjCp (ij)使得ci不判定p。TR对每个ci要求：ci取真值P为真、ci取假值P为真、ci取真值P为假、ci取假值P为真假。,逻辑覆盖准则,一般非活动子句覆盖（GICC）：对于每个pP及每个主子句ciCp，选择次子句cjCp (ij)使得ci不判定p。TR对每个ci要求：ci取真值P为真、ci取假值P为真、ci取真值P为假、ci取假值P为真假。次子句cj的取值四种情况下可以不同。,逻辑覆盖准则,受限非活动子句

25、覆盖（RICC）：对于每个pP及每个主子句ciCp，选择次子句cjCp (ij)使得ci不判定p。TR对每个ci要求：ci取真值P为真、ci取假值P为真、ci取真值P为假、ci取假值P为真假。次子句cj的取值前两种情况下必须相同，在后两种情况下也必须相同。,逻辑覆盖准则,组合覆盖 CoC,子句覆盖 CC,受限非活动子句覆盖 RICC,一般非活动子句覆盖 GICC,相关活动子句覆盖 CACC,一般活动子句覆盖 ADC,谓词覆盖 PC,受限活动子句覆盖 RACC,输入空间的划分准则,输入域D为输入参数的可能取值集合。 考虑域D的一个抽象划分q，q定义了一系列等价类，简称为块集Bq，满足：不相交性、

26、完全性,输入域建模,输入域建模步骤： 识别可测试功能：例如依据UML用例图确定被测对象的可测试功能； 识别会影响给定可测功能行为的所有参数，包括内部状态； 输入域建模：利用输入特征描述输入域的结构，为每种特征都产生一个划分。一个划分是一个块集，从每种特征的角度来看，每块的值都是等价的。 应用测试覆盖准则选择值的组合。 将块的组合精化为测试输入。,输入域建模,基于接口的输入域建模：单独考虑每个特殊的参数，每个参数都被作为一个特征。由于单独考虑每一个特征/参数，因此，可能某些重要的组合被遗漏。 例如：Triangle（int a, int b, int c) a作为一个单独的特征，整数： 0 ,输

27、入域建模,基于功能的输入域建模：明确被测对象想要实现的功能所对应的特征，将某些语义或领域知识结合到输入域模型。 例如，三角形问题：输入的是三角形，而不是三个整数 可以依据输入规约/需求进行设计，不必等到软件设计完成之后才能开始。,输入域建模,Public Boolean findElement(List list, Object element) /Function: if list or element is null throw NullPointer Exception /else return true if element is in the list, and false othe

28、rwise.,输入域建模,使用基于接口的方法，有两个特征list、element。如list特征 list是0/null b1：listnull true b2：listnull false List是空/empty b1：list=empty true b2：list=empty false,b1: list=null,b2:listnull list=empty,b3:listnull listempty,输入域建模,利用基于功能的方法 list中element出现的次数 b1：0 b2：1 b3：多于1次 Element第一个出现在list中 b1：true b2：false,输入域建模

29、,识别块中值的策略： 有效值：至少包含一组有效值； 子划分：可以将一个划分按照另一特征进行进一步划分； 边界：边界或距边界很近的值常引起错误； 无效值：至少包含一组无效值； 平衡：各特征尽可能划分出数量基本一致的块； 遗漏划分：检查块的并集是否完全覆盖该特征的输入域； 重叠划分：检查是否有值属于超过一个块。,输入域建模,例如：三角形问题的划分如下（a、b、c为整数）： 注意：本例中，分别在三个划分的某个块中取一个值才能构成一组输入。,输入域建模,当然也可以选择其他形式的划分，如： 注意：如果边为浮点数，上表中不是一个有效的划分，因为没有一个块包含（0，1）。,输入域建模,三角形问题的基于功能特

30、性的划分：,上述划分不能构成一个有效划分，因为b2与b3存在重叠，修正如下：,输入域建模,使用多种输入域模型：使用多个小的模型比一个大的模型还要好。 注意多个模型的输入域划分块可以重叠,输入域建模,检查输入域模型 检查是否有关该功能的某些信息没有合并到特征中 根据完整性、不相交性检查每个特征/划分,组合策略准则,所有组合策略（ACoC）：从所有特征得到的所有块的组合必须被覆盖。 如：三个划分得到的块A,B,1,2,3,x,y, ACoC需要12种测试：（A,1,x), ,(B,3,y),组合策略准则,每个选择覆盖（ECC）：对于来自每个特征的每个块的一个值，必须至少在一个测试用例中使用过。 如：三个划分得到的块A,B,1,2,3,x,y,（A,1,x）,(B,2,y),(A,3,x)满足ECC准则。,组合策略准则,成对覆盖（PWC）：每种特征的每个块的一个值必须与其他特征的每个块的一个值进行组合 如：三个划分得到的块A,B,1,2,3,x,y, (A,1),(A,2),(A,3),(A,x),(A,y) (B,1),(B,2),(B,3),(B,x),(B,y) (1,x),(1,y),(2,x),(2,y),(3,x),(3,y) 最