Computer Science ›› 2019, Vol. 46 ›› Issue (3): 19-29.doi: 10.11896/j.issn.1002-137X.2019.03.003

• Surveys • Previous Articles     Next Articles

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

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

CLC Number: 

  • 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.
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)
[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].
[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.
software with QuickCheck[C]∥IEEE Eighth International Conference on Software Testing,Verification and Validation Workshops.IEEE,2015:1-4.
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] WEN Jin, ZHANG Xing-yu, SHA Chao-feng, LIU Yan-jun. Test Suite Reduction via Submodular Function Maximization [J]. Computer Science, 2021, 48(12): 75-84.
[2] TENG Jun-yuan, GAO Meng, ZHENG Xiao-meng, JIANG Yun-song. Noise Tolerable Feature Selection Method for Software Defect Prediction [J]. Computer Science, 2021, 48(12): 131-139.
[3] SUN Chang-ai, ZHANG Shou-feng, ZHU Wei-zhong. Mutation Based Fault Localization Technique for BPEL Programs [J]. Computer Science, 2021, 48(1): 301-307.
[4] XIA Chun-yan, WANG Xing-ya, ZHANG Yan. Test Case Prioritization Based on Multi-objective Optimization [J]. Computer Science, 2020, 47(6): 38-43.
[5] BO Li-li, JIANG Shu-juan, ZHANG Yan-mei, WANG Xing-ya, YU Qiao. Research Progress on Techniques for Concurrency Bug Detection [J]. Computer Science, 2019, 46(5): 13-20.
[6] BAO Xiao-an, XIONG Zi-jian, ZHANG Wei, WU Biao, ZHANG Na. Approach for Path-oriented Test Cases Generation Based on Improved Genetic Algorithm [J]. Computer Science, 2018, 45(8): 174-178.
[7] ZHANG Xing-long, YU Lei, HOU Xue-mei and HOU Shao-fan. Method of Metamorphic Relations Constructing for Object-oriented Software Testing [J]. Computer Science, 2017, 44(Z11): 485-489.
[8] CHEN Cheng, ZHENG Zheng, WANG Hao-qin and QIAO Yu. Non-deadlock Concurrency Fault Localization Approach Based on Adequate Test Criteria [J]. Computer Science, 2017, 44(11): 195-201.
[9] ZHANG Wei-xiang and LIU Wen-hong. Test Suite Generation Based on Interaction Testing and Fault Tree Analysis [J]. Computer Science, 2014, 41(Z11): 375-378.
[10] WANG Zhi-wen,HUANG Xiao-long,WANG Hai-jun,LIU Ting and YU Le-chen. Program Slicing-guied Test Case Generation System [J]. Computer Science, 2014, 41(9): 71-74.
[11] FU Teng and GAO Jian-hua. Metadata Checking and Testing of Web Application Based on Invariance [J]. Computer Science, 2014, 41(8): 224-228.
[12] WANG Zhen-zhen. Elementary Theoretical Framework for Software Testing [J]. Computer Science, 2014, 41(3): 12-16.
[13] LI Li-ping and LI Xing-sen. Model-based Logic Boundary Coverage Testing Criteria [J]. Computer Science, 2013, 40(Z11): 109-114.
[14] . Quantitative Assessing Method of Software Quality Evaluation Based on Software Testing and KDD [J]. Computer Science, 2012, 39(Z11): 28-30.
[15] . Symbolic Execution Based on Branch Confusion Algorithm [J]. Computer Science, 2012, 39(9): 115-119.
Full text



No Suggested Reading articles found!