组合测试中的约束

2023/3/151组合测试中的约束答辩人：曾梦凡指导老师：聂长海教授2023/3/152绪论组合测试和约束问题约束分类约束的处理方法支持约束处理的组合测试工具应用研究总结与展望论文目录组合测试和约束问题2023/3/153OSBrowserNetworkAccessWindowsIEInternetWiredMacChromeLANWIFIOSBrowserNetworkAccessMacIELANWiredWindows

ChromeInternetWiredWindowsIELANWIFIMacIEInternetWIFIMacChromeLANWIFI

研究现状2023/3/1542023/3/155研究现状618intotalConstraints:8%49papers相关工作1994年D.M.Cohen等人提出了组合测试中约束的问题[D.M.Cohenetal.1994]2005年BrahimHnich等人将覆盖表生成问题转化为一个约束求解的问题[B.Hnichetal.2005]2006年MatsGrindal等人提出了抽象参数法，子模型法，约束避免法和替换法[M.Grindaletal.2006]2006年RenéeC.Bryce等人提出硬约束和软约束的概念，并结合DDA算法提出了一种约束避免策略[RenéeC.Bryceetal.2006]2008年MyraB.Cohen等人提出了AETG结合约束求解器的约束处理方法[MyraB.Cohenetal.2008]2012年,LongshuLi等人给出了找出隐含约束的算法[LongshuLietal.2012]2013年LinbinYu等人将约束求解器用在IPOG算法中，以解决约束问题[LinbinYuetal.2012]2015年LinbinYu等人提出了用禁止元组处理约束的方法[LinbinYuetal.2015]2015年，JustynaPetke指出约束是组合测试的未来[JustynaPetke2015]2017年，Akihisa等人结合约束求解器使用替换法处理约束[Akihisaetal.2017]...2023/3/156研究问题约束是否广泛存在？对组合测试有什么影响？约束有哪些表现形式？它们之间有何关系？如何处理约束？哪种处理策略效果最好？存在哪些支持约束的组合测试工具？在含有大量约束的系统中，组合测试效果如何？2023/3/157约束调研2023/3/158系统模型约束BBS3421Apache21583844516123314251Bugzilla24931422431GCC218931023733SpinS21345213SpinV2423241124732CommProtocol21071128Concurrency257NetworkMgmt22415310211120Services23345282102388SystemMgmt25345117Telecom243142516121MobilePhone3322253151CruiseControl41312422SpinSimulator4521324732HotelGuide334123.........文章：49篇软件：7个约束分类2023/3/159

约束转化2023/3/1510禁止约束必须约束数值约束屏蔽约束

约束处理覆盖表生成前抽象参数子模型覆盖表生成时使用求解器直接约束避免法测试用例修正*覆盖表生成后约束后处理*2023/3/1511直接约束避免法2023/3/15121.将约束转化为禁止约束并进行推导，化简2.按照下面过程生成覆盖表validvalidvalidvalidvalidvalidvalid...每次取值都保证当前测试用例不覆盖禁止约束！一种测试用例修正算法*2023/3/15131.将约束转化为禁止约束并进行推导，化简2.按照下面过程生成覆盖表unknownunknownunknownunknownunknown检查并修正validvalidvalidvalid先不管测试用例合法性，待一条测试用例生成结束后再修正！一种约束后处理算法*2023/3/15141.将约束转化为禁止约束并进行推导，化简2.按照下面过程生成覆盖表unknownunknownunknown...validvalidvalid...先不管约束，直接生成覆盖表。后将非法测试用例通过分解，重组的方式进行替换！实验对象2023/3/1515模型名取值约束模型名取值约束Apache21583844516123314251M62763342516324036Bugzilla24931422431M727234416223134GCC218931023733M8225316121332Spin-S21345213M9211032536422534Spin-V2423241124732M102118364252662233341M1286334155622203341M1128731435422834M22863343516221933M122553242516221733M3227422931M13216731642536623136M425134425121532M142134375321933M52155374355642323641M152733343220322维覆盖表大小2023/3/1516

modifyavoidpostminmeanstdminmeanstdminmeanstdApache4246.4312.384043.337.394548.5314.61Bugzilla2325.038.062021.465.422527.3011.50GCC2731.2313.172627.906.534651.1314.95Spin-S3030.534.842729.704.923434.772.32Spin-V7585.1330.914446.879.78895.0317.92M15761.6713.815355.377.546570.5718.85M24246.5713.543841.239.024953.6313.08M32121.0002121.802.192727.172.04M42628.676.532728.737.473034.038.89M57683.6024.316465.977.819299.7023.33M65053.0310.345153.678.525155.8012.44M74045.5311.984145.4715.084550.9718.25M81616.131.861616.861.861919.702.51M96872.6714.025861.8011.617683.4020.96M107884.2317.876568.139.978995.0315.65M114446.8011.174143.537.975862.5012.47M124448.1712.974648.239.975258.8713.98M138892.3716.156870.607.16101107.314.72M144144.238.803740.8711.64858.2020.80M152728.806.842527.637.812934.3314.722维覆盖表生成时间2023/3/1517APBZGCCSSSVM1M2M3M4

modify608723464294233232488166556333

avoid4292140393622344140596740231

post6486202193622153091843599071091057

M5M6M7M8M9M10M11M12M13M14M15124511533109744435067391748747181774705767668410167192925563701105645693932911493167025357231196326498596031752241843624873553926203维覆盖表尺寸和生成时间2023/3/1518modifyavoidpostminmeanstdminmeanstdminmeanstdM37377.9312.166871.138.918287.3314.45M4113118.5713.09113117.9710.72133145.4025.56M84951.677.394850.807.806163.9711.09Bugzilla8188.2719.347479.1010.2391100.4321.62Spin-S128136.5316.90118124.8715.15140146.3019.60M3M4M8BugzillaSpin-Smodify2511363311368189961307avoid15082408483210591528post23457784914996426397覆盖表尺寸分布2023/3/15192维3维支持约束处理的组合测试工具改进AETG算法（组合测试经典算法）简化第一个元组的选取采用新的tiebreaking策略候选集大小非固定约束统一处理将其他约束全部转化为禁止约束带约束约简使用灵活位置合并测试用例移动灵活位置2023/3/1520CTCH工具表单输入真实模型文件输入4种约束形式隐含约束处理覆盖表约简结果下载2023/3/1521相关工具2023/3/1522工具名开发者类型表达处理免费TestcoverBellLabs网页划分模型子模型30天PICTMicroSoft命令行禁止约束避免开源Jenny[Jenkins]命令行禁止约束避免开源AllPairsMetaCommunicationspython库数值约束避免免费ACTSNIST图形界面禁止约束避免免费CombTestWeb[MacarioPoloUsaola]网页禁止约束避免免费PairwiserInductiveAS网页数值约束避免免费tcases[Kimbrough]命令行数值约束避免免费Pro-TestSigmaZone图形界面禁止约束未知10天工具2维实验对比2023/3/1523工具jennyAETG-SATPICTACTSCTCHApache4242.8403339(41.9)Bugzilla2124.9201921(21.5)GCC2924.8302323(24.6)Spin-S2627.1262625(26.8)Spin-V4642.5634543(44.3)M15654.7534852(52.8)M24240.1403235(38.6)M32121231920(20)M43028.7292227(27.7)M57064.1655461(63.4)M65555483946(49.3)M74750.4393741(45.4)M81815.7181414(14)M96159.9574858(59.9)M106866.2655264(66.4)M114843.3423439(41)M124749.8443744(46.1)M137268.4725767(68.9)M144141.2342936(38.6)M152928.7252224(25.7)工具3维实验对比2023/3/1524工具jennyAETG-SATPICTACTSCTCHApache205206.9202173209(211)Bugzilla7371.7706868(70.9)GCC103106.5134108110(111.3Spin-S117117.511398111(114.3)Spin-V251242.3345286251(255.7)应用研究2023/3/1525参数提取2023/3/1526参数名称取值开始时间2016.9.1,2016.11.1,2017.1.1,2017.3.12结束时间2016.10.1,2016.11.30,2017.2.28,2017.4.23统计维度1探针MAC,终端MAC,位置信息,采集时间统计粒度1月,日,时统计维度2无,探针MAC,终端MAC,位置信息,采集时间统计粒度2无,月,日,时同比环比否,同比,环比统计图形折线图,同比图,柱状图,饼图约束分析“结束时间”>“开始时间”“统计维度”只有取“采集时间”时，“统计粒度”才生效“统计维度2”取“无”和“统计粒度2”取“无”或者同时出现，或者同时不出现“同比环比”取“同比”时，“统计图形”必须取“同比图“同比环比”取“环比”时，“统计图形”必须取“柱状图”2023/3/1527测试结果共生成51条测试用例25条测试不通过分析出4个bug:折线图横坐标乱序同比环比不为否时第二个维度无效统计图形为饼图时第二个维度无效统计维度2取值超过12会出错2023/3/1528总结与展望总结约束分析与调研约束分类及转化各种约束处理策略支持约束处理的组合测试工具应用组合测试展望约束类型可能遗漏算法优化工具优化2023/3/1529部分参考文献D.M.Cohen,S.R.Dalal,A.Kajla,andG.C.Patton.Theautomaticefficienttestsgenerator(aetg)system[C].InternationalConferenceonSoftwareReliabilityEngineering,1994,pp.303–309.HnichB,PrestwichS,SelenskyE.Constraint-BasedApproachestotheCoveringTestProblem[M].RecentAdvancesinConstraints.SpringerBerlinHeidelberg,2005.GrindalM,OffuttJ,MellinJ.ManagingConflictsWhenUsingCombinationStrategiestoTestSoftware[C].SoftwareEngineeringConference,2007.Aswec2007.Australian.IEEE,2007:255-264.BryceRC,ColbournCJ.Prioritizedinteractiontestingforpair-wisecoveragewithseedingandconstraints[J].Information&SoftwareTechnology,2006,48(10):960-970.CohenMB,DwyerMB,ShiJ.ConstructingInteractionTestSuitesforHighly-ConfigurableSystemsinthePresenceofConstraints:AGreedyApproach[J].IEEETransactionsonSoftwareEngineering,2008,34(5):633-650.ChenB,YanJ,ZhangJ.CombinatorialTestingwithShieldingParameters[C].SoftwareEngineeringConference.IEEE,2011:280-289.2023/3/1530部分参考文献LiL,CuiY,YangY.Combinatorialtestcaseswithconstraintsinsoftwaresystems[C].IEEE,InternationalConferenceonComputerSupportedCooperativeWorkinDesign.IEEE,2012:195-199.KrusePM,BauerJ,WegenerJ.NumericalConst