计算机科学 ›› 2019, Vol. 46 ›› Issue (3): 19-29.doi: 10.11896/j.issn.1002-137X.2019.03.003

• 综述 • 上一篇    下一篇

基于划分的自适应随机测试综述

李志博,李清宝,于磊,侯雪梅   

  1. (中国人民解放军战略支援部队信息工程大学 郑州 450001)(数学工程与先进计算国家重点实验室 郑州 450001)
  • 收稿日期:2018-01-14 修回日期:2018-03-10 出版日期:2019-03-15 发布日期:2019-03-22
  • 作者简介:李志博(1982-),女,博士生,讲师,主要研究方向为软件测试、测试结果正确性验证,E-mail:lizhibo1019@163.com;李清宝(1967-),男,博士,教授,主要研究方向为信息安全、软件测试,E-mail:qingbao_li@163.com(通信作者);于磊(1973-),男,博士,副教授,主要研究方向为软件测试;侯雪梅(1981-),女,副教授,主要研究方向为软件测试。
  • 基金资助:
    本文受国家自然科学基金(61402525),国家社会科学基金(15AJG012),国家“核高基”科技重大专项(2013JH00103)资助

Survey on Adaptive Random Testing by Partitioning

LI Zhi-bo, LI Qing-bao, YU Lei, HOU Xue-mei   

  1. (PLA Strategic Support Force Information Engineering University,Zhengzhou 450001,China)
    (State Key Laboratory of Mathematical Engineering and Advanced Computing,Zhengzhou 450001,China)
  • Received:2018-01-14 Revised:2018-03-10 Online:2019-03-15 Published:2019-03-22

摘要: 随机测试是一种广泛应用于实践的基础测试方法。自适应随机测试(ART)是对随机测试的改进,其检错有效性优于随机测试。首先,分析了具有较高检错有效性但时间开销较大的经典ART算法;其次,重点综述了能降低时间开销的基于划分的ART算法,并对各种划分策略和测试用例生成算法进行了分析和对比;同时,分析了影响ART算法有效性的关键因素以及高维输入域空间中算法有效性低下的问题,梳理了算法有效性度量指标以及测试用例分布度量指标;最后,论述了ART算法中存在的问题及面临的挑战。

关键词: 基于划分的自适应随机测试, 软件测试, 随机测试, 自适应随机测试

Abstract: As a fundamental software testing technique,random testing (RT) has been widely used in practice.Adaptive random testing (ART),an enhancement of RT,performs better than original RT in terms of fault detection capability.Firstly,this paper analyzed the classical ART algorithm with high detection effectiveness and large time overhead.Se-condly,it summarizedthe ART algorithms by partitioning to reduce the time cost,analyzed and compared various partition strategies and test case generation algorithms.Meanwhile,this paper analyzed the problems of the key factors affecting the effectiveness of ART algorithm and leading to low efficiency of algorithm in high dimensional input domain.Finally,it discussed the problems and challenges in the ART algorithm.

Key words: Adaptive random testing by partitioning, Adaptive random testing(ART), Random testing(RT), Software testing

中图分类号: 

  • TP311.5
[1]BERTOLINO A.Software testing research:Achievements,challenges,dreams[C]∥Proceedings of Future of Software Engineering.2007:85-103.
[2]HUANG R,XIE X,CHEN T Y,et al.Adaptive Random Test
Case Generation for Combinatorial Testing[C]∥Proceedings of Computer Software and Applications Conference (COMPSAC).IEEE,2012:52-61.
[3]GRIESMAYER A,AICHERNIG B,JOHNSEN E B,et al.Dynamic Symbolic Execution for Testing Distributed Objects[C]∥International Conference on Tests and Proofs.2009:105-120.
[4]CHOW T S.Testing software design modeled by finite-state
machines[M]∥Conformance testing methodologies and architectures for OSI protocols.IEEE Computer Society Press,1995:391-400.
[5]FUJIWARA S,BOCHMANN G V,KHENDEK F,et al.Test
selection based on finite state models[J].IEEE Transactions on Software Engineering,1991,17(6):591-603.
[6]WHITTAKER J A,THOMASON M G.A markov chain model for statistical software testing[J].IEEE Transactions on Software Engineering,1994,20(10):812-824.
[7]ARIFIANI S,ROCHIMAH S.Generating test data using ant
Colony Optimization (ACO) algorithm and UML state machine diagram in gray box testing approach[C]∥Proceedings of Technology of Information & Communication.2017:217-222.
[8]WHITE L J,COHEN E I.A Domain Strategy for Computer
Program Testing[J].IEEE Transactions on Software Enginee-ring,1980,6(3):247-257.
[9]MYERS G J,SANDIER C,BADGETT T.The art of software testing[M].Wiley,2011.
[10]ORSO A,ROTHERMEL G.Software Testing:a Research
Travelogue (2000-2014)[C]∥Proceedings of 14th Future of Software Engineering(FOSE).2014:117-132.
[11]GIRARD E,RAULT J C.A programming technique for soft-
ware reliability[C]∥Proceedings of the IEEE Symposium on Computer Software Reliability.1973:44-50.
[12]CHEN T Y,KUO F C,ZHOU Z Q.On Favourable Conditions for Adaptive Random Testing[J].International Journal of Software Engineering and Knowledge Engineering,2007,17(6):805-825.
[13]LOO P S,TSAI W K.Random Testing Revisited[J].Information and Software Technology,1988,30(7):402-417.
[14]ZHOU Z Q.Using Coverage Information to Guide Test Case Selection in Adaptive Random Testing[C]∥Proceedings of 34th Annual IEEE Computer Software and Applications Conference Workshops.2010:208-213.
[15]XIONG N.Random Testing with varied probability[D].Hefei:University of Science and Technology of China,2013.(in Chinese)
熊能.变概率的随机测试[D].合肥:中国科学技术大学,2013.
[16]AMMANN P E,KNIGHT J C.Data diversity:An approach to software falut tolerance [J].IEEE Transactions on Computers,1998,37(4):418-425.
[17]FINELLI G B.Nasa sofware failure characterization experi-
ments [J].Reliability Engineering and System Safety,1991,32(1-2):155-169.
[18]CHEN T Y,LEUNG H,MAK K.Adaptive Random Testing[C]∥
Proceedings of the IEEE International Conference on Quality Software(QSIC).IEEE,2008.
[19]CHEN T Y,LEUNG H,MAK I K.Adaptive Random Testing[M]∥Advances in Computer Science-ASIAN 2004.Higher-Level Decision Making.Springer Berlin Heidelberg,2004:57-76.
[20]CHAN K P,CHEN T Y,TOWEY D P.Restricted Random Tes-
ting[C]∥Proceedings of 7th Events in Care Screening Questionnaire(ECSQ).Berlin,Germany,2002:321-330.
[21]GUTJAHR W J.Partition testing vs. random testing:The in-
fluence of uncertainty[J].IEEE Transactions on Software Engineering,1999,25(5):661-674.
[22]CHEN T Y,MERKEL R G,EDDY G,et al.Adaptive RANDOM TESTING THROugh Dynamic Partitioning[C]∥Proceedings of the Forth IEEE International Conference on Quality Software.Washington,2004:79-86.
[23]CHAN F T,CHEN T Y,MAK I K,et al.Proportional Sampling Strategy:Guidelines for Software Testing Practitioners[J].Information and Software Technology,1996,38(12):775-782.
[24]BISHOP P G.The variation of software survival times for different operational input profiles[C]∥Proceedings of the 23rd International Symposium on Fault-Tolerant Computing(FTCS-23).IEEE Computer Society Press,1993:98-107.
[25]CHEN T Y,KUO F C,MERKEL R.On the statistical properties of the F-measure[C]∥Proceeding of the Fourth International Conference on Quality SOFTWARE(QSIC 2004).2004:146-153.
[26]CHEN T Y,KUO F C,MERKEL R.On the statistical properties of testing effectiveness measures[J].Journal of Systems & Software,2006,79(5):591-601.
[27]CHAN K P,CHEN T Y,TOWEY D.Normalized Restricted
Random Testing[M]// Reliable Software Technologies.DBLP,2003:368-381.
[28]CHAN K P,CHEN T Y,TOWEY D P.Restricted Random Testing:Adaptive Random Testing by Exclusion[J].International Journal of Software Engineering and Knowledge Engineering,World Scientific Publishing Company,2006,16(4):553-584.
[29]MAYER J,SCHNECKENBURGER C.An Empirical Analysis
and Comparison of Random Testing Techniques[C]∥Procee-dings of the 2006 ACM/IEEE International Symposium on Empirical Software Engineering (ISESE’06).2006:105-114.
[30]CHEN T Y,KUO F C,LIU H.Enhancing Adaptive Random Testing Through Partitioning by Edge and Centre[C]∥Proceedings of the Australian Software Engineering Conference.Washington,2007:265-273.
[31]MAYER J.Adaptive random testing by bisection with restriction[C]∥International Conference on Formal Methods and Software Engineering.Springer-Verlag,2005:251-263.
[32]CHEN T Y,HUANG D H.Adaptive random testing by localization[C]∥Proceedings of the Software Engineering Confe-rence,2004.IEEE,2004:292-298.
[33]MAYER J,SCHNECKENBURGER C.Adaptive random testing with enlarged input domain[C]∥Proceedings of the Sixth international conference on quality software (QSIC’06).IEEE.2006:251-258.
[34]SABOR K K.MOHSENZADEH M.Adaptive Random Testing Through Dynamic Partitioning By Localization with Distance and Enlarged Input Domain[J].International Journal of Innovative Technology & Exploring Engineering,2012,1(6):147-155.
[35]CHEN T Y,HUANG D H,ZHOU Z Q.Adaptive Random Testing Through Iterative Partitioning[C]∥Proceedings of the Eleventh Conference on Software Technologics.Berlin,2006:155-166.
[36]MAYER J,CHEN T Y,HUANG D H.Adaptive Random Testing through Iterative Partitioning Revisited [J].Journal of Information Science and Engineering,2011,27(15):22-29.
[37]CHEN T Y,HAO D H,KUO F C.Adaptive Random Testing by Balancing[C]∥Proceedings of the Second International Workshop on Random Testing,Colocated With the Twenty-second IEEE/ACM International Conference on Automated Software Engineering.New York,USA,2007:2-9.
[38]KOROSH K S,STUART T.Adaptive Random Testing by Sta-
tic Partitioning[C]∥Proceedings of the 2015 IEEE/ACM 10th International Workshop on Automation of Software Test.2015:28-32.
[39]CHEN T Y,KUO F C,ZHOU Z Q.On the Relationships Between the Distribution of Failure-causing Inputs and Effectiveness of Adaptive Random Testing[C]∥Proceedings of the 2005 Software Engineering and Knowledge Engineering(SEKE).2005:306-311.
[40]KUO F C.On adaptive random testing[D].Swinburne Universi-
ty of Technology,2006.
[41]T.R.D.of the Texas Legislative Council.Data for 2001 Redistricting in Texas.the Texas Legislative Council,Austin,Texas,2001[OL].http://www.tlc.state.tx.us/pubspol/red2001data.pdf.
[42]VARACHIU C M,VARACHIU N.A fuzzy paradigm approach for the cognitive process of categorization[C]∥Proceedings of the 1st IEEE International Conference on Cognitive Informatics(ICCI’02).IEEE Computer Society Press,2002:229-232.
[43]YOUNG H P.Measuring the compactness of legislative districts[J].Legislative Studies Quarterly,1988,13(1):105-115.
[44]CHEN T Y,MERKEL R G.An Upper Bound on Software Testing Effectiveness[J].ACM Transactions on Software Enginee-ring and Methodology,2008,17(3):1-27.
[45]CHEN T Y,YU Y T.On the relationship between partition and random testing [J].IEEE Transactions on Software Enginee-ring,1994,20(12):977-980.
[46]WEYUKER E J,JENG B.Analysing partition testing strategies[J].IEEE Transactions on Software Engineering,1991,17(7):703-711.
[47]MERKEL R.Analysis and enhancements of adaptive random
testing[D].Swinburn University of Technology,2005.
[48]LIU H,XIE X D,YANG J,et al.Adaptive Random Testing by Exclusion through Test Profile[C]∥Proceedings of the 10th International Conference on Quality Software.2010:92-101.
[49]MAYER J.Adaptive Random Testing with Randomly Transla-
ted Failure Region [C]∥Proceedings of the First International Workshop on Random Testing.2006:70-77.
[50]ARCURI A,BRIAND L.Adaptive Random Testing:An Illusion of Effectiveness? [C]∥Proceedings of the International Symposium on Software Testing & Analysis.ACM,2011:265-275.
[51]KUO F C,An indepth study of mirror adaptive random testing [C]∥Proceedings of the 9th International Conference on Quality Software (QSIC’09).2009:51-58.
[52]CHEN T Y,KUO F C,MERKEL R,et al.Mirror adaptive random testing [J].Information and Software Technology,2004,46(15):1001-1010.
[53]HOU S F,YU L,LI Z B,et al.Based on the Random Vector
Mirror Method Improve the ART Algorithm[J].Journal of Computer-Aided Design & Computer Graphics,2017,29(9):1750-1759.(in Chinese)
侯韶凡,于磊,李志博,等.基于随机向量镜像策略改进 ART 算法[J].计算机辅助设计与图形学学报.2017,29(9):1750-1759.
[54]BARUS A C,CHEN T Y,KUO F C,et al.A Cost-Effective Random Testing Method for Programs with Non-Numeric Inputs[J].IEEE Transactions on Computers,2016,65(12):3509-3523.
[55]CIUPA I,LEITNER A,ORIOL M,et al.Object distance and its
application to adaptive random testing of object-oriented programs[C]∥Proceedings of the 1st Int.Workshop Random Testing.2006:55-63.
[56]CIUPA I,LEITNER A,ORIOL M,et al.ARTOO:adaptive random testing for object-oriented software[C]∥International Conference on Software Engineering.DBLP,2008:71-80.
[57]LIN Y,TANG X,CHEN Y,et al.A Divergence-Oriented Approach to Adaptive Random Testing of Java Programs[C]∥Ieee/acm International Conference on Automated Software Engineering.IEEE,2009:221-232.
[58]CHEN J F,KUO F C,CHEN T Y,et al.A Similarity Metric for the Inputs of OO Programs and Its Application in Adaptive Random Testing[J].IEEE Transactions on Reliability,2017,66(2):373-402.
[59]VISHAWJYOTI,GANDHID P.A survey on prospects of auto-
mated software test case generation methods[C]∥International Conference on Computing for Sustainable Global Development.IEEE,2016:3867-3871.
[60]PACHECO C,ERNST M D.Randoop:Feedback-Directed Random Testing for Java[C]∥Companion to the Acm Sigplan Conference on Object—oriented Programming System & Application Companion.2007:815-816.
[61]CLAESSEN K,HUGHES J.QuickCheck:a lightweight tool for random testing of Haskell programs[C]∥Acm Sigplan International Conference on Functional Programming.ACM,2000:268-279.
[62]ARTS T,HUGHES J,NORELL U,et al.Testing AUTOSAR
software with QuickCheck[C]∥IEEE Eighth International Conference on Software Testing,Verification and Validation Workshops.IEEE,2015:1-4.
[63]HUGHES J,NORELL U,SMALLBONE N,et al.Find More
Bugs with QuickCheck![C]∥Proceedings of the 2016 11th IEEE/ACM International Workshop in Automation of Software Test.IEEE,2016:71-77.
[64]BARUS A C,CHEN T Y,KUO F C.The Impact of Source Test Case Selection on the Effectiveness of Metamorphic Testing [C]∥Proceedings of the 2016 1st International Workshop on Metamorphic Testing.IEEE,2016:5-11.
[65]HUI Z W,HUANG S.MD-ART:a test case generation method without test oracle problem[C]∥International Workshop on Specification,Comprehension,Testing,and Debugging of Concurrent Programs.ACM,2016:27-34.
[66]LIU H,CHEN T Y.Randomized Quasi-Random Testing[J].IEEE Transactions on Computers,2016,65(6):1896-1909.
[67]MAYER J.Lattice-based Adaptive Random Testing [C]∥Proceedings of the Twenty IEEE/ACM International Conference on Automated Software Engineering.2005:333-336.
[68]CHEN T Y,HUANG D H,KUO F C,et al.Enhance Lattice-based Adaptive Random Testing[C]∥Proceeding of the Software Automated Conference(SAC).Honolulu,Hawaii,2009:422-429.
[69]MAYER J.Towards Effective Adaptive Random Testing for
Higher-Dimensional Input Domains[C]∥Proceedings of the Conference on Genetic & Evolutionary Computation.2006:1955-1956.
[1] 文进, 张星宇, 沙朝锋, 刘艳君.
基于次模函数最大化的测试用例集约简
Test Suite Reduction via Submodular Function Maximization
计算机科学, 2021, 48(12): 75-84. https://doi.org/10.11896/jsjkx.210300086
[2] 滕俊元, 高猛, 郑小萌, 江云松.
噪声可容忍的软件缺陷预测特征选择方法
Noise Tolerable Feature Selection Method for Software Defect Prediction
计算机科学, 2021, 48(12): 131-139. https://doi.org/10.11896/jsjkx.201000168
[3] 孙昌爱, 张守峰, 朱维忠.
一种基于变异分析的BPEL程序故障定位技术
Mutation Based Fault Localization Technique for BPEL Programs
计算机科学, 2021, 48(1): 301-307. https://doi.org/10.11896/jsjkx.200900051
[4] 夏春艳, 王兴亚, 张岩.
基于多目标优化的测试用例优先级排序方法
Test Case Prioritization Based on Multi-objective Optimization
计算机科学, 2020, 47(6): 38-43. https://doi.org/10.11896/jsjkx.191100113
[5] 薄莉莉, 姜淑娟, 张艳梅, 王兴亚, 于巧.
并发缺陷检测技术研究进展
Research Progress on Techniques for Concurrency Bug Detection
计算机科学, 2019, 46(5): 13-20. https://doi.org/10.11896/j.issn.1002-137X.2019.05.002
[6] 王蓁蓁, 刘嘉.
基于校正因子的随机TBFL方法
Stochastic TBFL Approach Based on Calibration Factor
计算机科学, 2019, 46(11): 161-167. https://doi.org/10.11896/jsjkx.191100503C
[7] 包晓安, 熊子健, 张唯, 吴彪, 张娜.
一种基于改进遗传算法的路径测试用例生成方法
Approach for Path-oriented Test Cases Generation Based on Improved Genetic Algorithm
计算机科学, 2018, 45(8): 174-178. https://doi.org/10.11896/j.issn.1002-137X.2018.08.031
[8] 张兴隆,于磊,侯雪梅,侯韶凡.
面向对象程序蜕变关系构造方法
Method of Metamorphic Relations Constructing for Object-oriented Software Testing
计算机科学, 2017, 44(Z11): 485-489. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.103
[9] 高雪笛,周丽娟,张树东,柳昊明.
基于改进遗传算法的测试数据自动生成的研究
Research on Test Data Automatic Generation Based on Improved Genetic Algorithm
计算机科学, 2017, 44(3): 209-214. https://doi.org/10.11896/j.issn.1002-137X.2017.03.044
[10] 陈诚,郑征,王皓钦,乔禹.
基于测试充分性准则的非死锁并发缺陷定位方法
Non-deadlock Concurrency Fault Localization Approach Based on Adequate Test Criteria
计算机科学, 2017, 44(11): 195-201. https://doi.org/10.11896/j.issn.1002-137X.2017.11.030
[11] 张卫祥,刘文红.
基于故障树分析与组合测试的测试用例生成方法
Test Suite Generation Based on Interaction Testing and Fault Tree Analysis
计算机科学, 2014, 41(Z11): 375-378.
[12] 王志文,黄小龙,王海军,刘烃,俞乐晨.
基于程序切片的测试用例生成系统研究与实现
Program Slicing-guied Test Case Generation System
计算机科学, 2014, 41(9): 71-74. https://doi.org/10.11896/j.issn.1002-137X.2014.09.012
[13] 傅腾,高建华.
Web工程中基于不变性的元数据检查和测试
Metadata Checking and Testing of Web Application Based on Invariance
计算机科学, 2014, 41(8): 224-228. https://doi.org/10.11896/j.issn.1002-137X.2014.08.048
[14] 邬晟峰, 吴悦, 徐拾义.
准完全最大距离伪随机测试研究
Study on Quasi-perfect Maximum Distance Pseudo Random Testing
计算机科学, 2014, 41(5): 50-54. https://doi.org/10.11896/j.issn.1002-137X.2014.05.011
[15] 王蓁蓁.
软件测试理论初步框架
Elementary Theoretical Framework for Software Testing
计算机科学, 2014, 41(3): 12-16.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!