Path-oriented random testing through iterative partitioning (IP-PRT)

Path-oriented random testing aims at generating a uniformly distributed sequence of test data from a programinput domain space to traverse a desired execution path of the program. To this aim, this article proposes a new algorithmto refine a program inputs domain space from invalid subdomains not covering the path. The validity of the subdomainsis checked by a constraint propagation method against the path constraints (PCs). The proposed algorithm uses a divideand-conquer technique to iteratively split the inputs domain into subdomains and each time refutes those subdomainsthat are inconsistent with the PCs. The remaining shrunken subdomains provide all possible test data covering thedesired path. Obviously, the more accurate the input domain is, the more effective test data will result. Experimentsshow the proposed method outperformed other related methods on a set of classical benchmark programs.

PDF

___

[1] Swain S, Mohapatra DP. Genetic algorithm-based approach for adequate test data generation. In: Mohapatra D, Patnaik S (editors). Intelligent Computing, Networking, and Informatics. New Delhi, India: Springer, 2014, pp. 453-462.
[2] Sahin O, Akay B. Comparisons of metaheuristic algorithms and fitness functions on software test data generation. Applied Soft Computing 2016; 49 (1): 1202-1214. doi: 10.1016/j.asoc.2016.09.045
[3] Hamlet D. When only random testing will do. In: Proceedings of the First International Workshop on Random Testing; Portland, ME, USA; 2006. pp. 1-9.
[4] Liu H, Chen TY. Randomized quasi-random testing. IEEE Transactions on Computers 2016; 65 (6): 1896-1909. doi: 10.1109/TC.2015.2455981
[5] Groce A, Holzmann G, Joshi R. Randomized differential testing as a prelude to formal verification. In: 29th International Conference on Software Engineering; Minneapolis, MN, USA; 2007. pp. 621-631.
[6] Arcuri A, Iqbal MZ, Briand L. Formal analysis of the effectiveness and predictability of random testing. In: Proceedings of the 19th International Symposium on Software Testing and Analysis; Torento, Italy; 2010. pp. 219-230.
[7] Chen TY, Kuo FC, Merkel RG, Tse TH. Adaptive random testing: the art of test case diversity. Journal of Systems and Software 2010; 83 (1): 60-66.
[8] Godefroid P, Klarlund N, Sen K. DART: directed automated random testing. In: Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation; Chicago, IL, USA; 2005. pp. 213-223.
[9] Gotlieb A, Petit M. A uniform random test data generator for path testing. Journal of Systems and Software 2010; 83 (12): 2618-2626. doi: 10.1016/j.jss.2010.08.021
[10] Dinges P, Agha G. Targeted test input generation using symbolic-concrete backward execution. In: Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering, Västerås, Sweden; 2014. pp. 31-36.
[11] McMinn P. Search-based software test data generation: a survey. Software Testing, Verification and Reliability 2004; 14 (2): 105-156. doi: 10.1002/stvr.294
[12] Harman M, McMinn P. A theoretical & empirical analysis of evolutionary testing and hill climbing for structural test data generation. In: Proceedings of the 2007 International Symposium on Software Testing and Analysis; Washington, DC, USA; 2007. pp. 73-83.
[13] Şahin O, Akay B. Comparisons of metaheuristic algorithms and fitness functions on software test data generation. Applied Soft Computing 2016; 49 (1): 1202-1214. doi: 10.1016/j.asoc.2016.09.045
[14] Feyzi F, Parsa S. Bayes-TDG: Effective test data generation using Bayesian belief network: towards failure-detection effectiveness and maximum coverage. IET Software 2018; 12: 225-235. doi: 10.1049/iet-sen.2017.0112
[15] Chow C, Chen TY, Tse TH. The art of divide and conquer: an innovative approach to improving the efficiency of adaptive random testing. In: Proceedings of 13th International Conference on Quality Software; Nanjing, China; 2013. pp. 268-275.
[16] Chen TY, Huang DH, Zhou ZQ. On adaptive random testing through iterative partitioning. Journal of Information Science and Engineering 2011; 27 (4): 1449-1472.
[17] Chan KP, Chen TY, Towey D. Normalized restricted random testing. In: International Conference on Reliable Software Technologies; Berlin, Germany; 2003. pp. 368-381.
[18] Chen TY, Kuo FC, Merkel RG, Ng SP. Mirror adaptive random testing. Information and Software Technology 2004; 6 (15): 1001-1010. doi: 10.1016/j.infsof.2004.07.004
[19] Chen TY, Merkel R, Wong PK, Eddy G. Adaptive random testing through dynamic partitioning. In: Proceedings of Fourth International Conference on Quality Software; Braunschweig, Germany; 2004. pp. 79-86.
[20] Nikravan E, Feyzi F, Parsa S. Enhancing path-oriented test data generation using adaptive random testing techniques. In: Proceedings of 2nd International Conference on Knowledge-Based Engineering and Innovation; Tehran, Iran; 2015. pp. 1-14.
[21] Sabor KK, Thiel S. Adaptive random testing by static partitioning. In: Proceedings of the 10th International Workshop on Automation of Software Test; Florence, Italy; 2015. pp. 28-32.
[22] Baldoni R, Coppa E, D’Elia DC, Demetrescu C, Finocchi I. A survey of symbolic execution techniques. ACM Computing Surveys 2018; 51 (3): 50. doi: 10.1145/3182657
[23] Braione P, Denaro G, Mattavelli A, Pezzè M. Combining symbolic execution and search-based testing for programs with complex heap inputs. In: Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis; Santa Barbara, CA, USA; 2017. pp. 90-101
[24] Qiu R, Păsăreanu CS, Khurshid S. Certified symbolic execution. In: International Symposium on Automated Technology for Verification and Analysis; Chiba, Japan; 2016. pp. 495-511.
[25] Gotlieb A, Petit M. Path-oriented random testing. In: Proceedings of the 1st International Workshop on Random Testing; Portland, ME, USA; 2006. pp. 28-35.
[26] Offutt AJ, Jin Z, Pan J. The dynamic domain reduction procedure for test data generation. Software Practice and Experience 1999; 29 (2): 167-193.