Test Case Generation Based on Combination of Schema Using Particle Swarm Optimization
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61502497); Guangxi Key Laboratory of Trusted Software (kx201530); State Key Laboratory for Novel Software Technology at Nanjing University (KFKT2014B19)

  • Article
  • | |
  • Metrics
  • |
  • Reference [30]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    The design of fitness function plays one of most important roles in search based test data generation. While in some special program structures, such as nested structure, unstructured jump statements, and return/break statements, the existing fitness functions can't evaluate all the branches. The currently used approaches are to change the source program so that the branches can be evaluated completely. Changing source program might not only affect the program structure and result in errors, but also be hard to implement automatically. To solve the problem, this paper presents an approach of test case generation based on combination of schema using particle swarm optimization. First, a definition called "schema" is presented for all the branches which are able to improve the fitness value, and the branch function of the schema is obtained, solving the problem of partial evaluation. Then, a crossover is designed to place search on all the individuals which have the minimum value of branch function of the schema. The crossover views each schema as a whole and combines all the schemata into a single individual, as a result the crossover can not only prevent schemata destroyed in the process of evolution, but also improve the fitness value of individuals because of the combination. Furthermore, a local search strategy is used for the best particle in each generation in the process of test case generation. Experiments on some benchmark programs and open source programs are performed. The experimental results show that the proposed approach has obvious advantages in average coverage and generations comparing with other methods.

    Reference
    [1] Harman M, Jones BF. Search based software engineering. Information and SoftwareTechnology, 2001,43(14):833-839.
    [2] McMinn P. An identification of program factors that impact crossover performance in evolutionary test input generation for thebranch coverage of C programs. Information and Software Technology, 2013,55(1):153-172.[doi:10.1016/j.infsof.2012.03. 010]
    [3] McMinn P, Binkley D, Harman M. Empirical evaluation of a nesting testability transformation for evolutionary testing. ACM Trans. on Software Engineering and Methodology, 2009,18(3):824-833.[doi:10.1145/1525880.1525884]
    [4] Holland JH. Adaptation in Natural and Artificial Systems. Ann Arbor:University of Michigan Press, 1992.
    [5] Windisch A, Wappler S, Wegener J. Applying particle swarm optimization to software testing. In:Lipson H, ed. Proc. of the 9th Annual Conf. on Genetic and Evolutionary Computation. New York:ACM Press, 2007. 1121-1128.[doi:10.1145/1276958. 1277178]
    [6] Wang LS, Jiang SJ, Zhang YM, Yu Q. Test case generation based on orthogonal exploration and particle swarm optimization. Acta Electronica Sinica, 2014,42(12):2345-2351(in Chinese with English abstract).
    [7] Korel B. Automated software test data generation. IEEE Trans. on Software Engineering, 1990,16(8):870-879.[doi:10.1109/32. 57624]
    [8] Xiao M, El-Attar M, Reformat M, Miller J. Empirical evaluation of optimization algorithms when used in goal-oriented automated test data generation techniques. Empirical Software Engineering, 2007,12(2):183-239.[doi:10.1007/s10664-006-9026-0]
    [9] Kifetew MF, Panichella A, Lucia AD, Oliveto R, Tonella P. Orthogonal exploration of the search space in evolutionary test case generation. In:Pezzè M, Harman M, eds. Proc. of the 2013 Int'l Symp. on Software Testing and Analysis. Lugano:ACM Press, 2013. 257-267.[doi:10.1145/2483760.2483789]
    [10] Zhu XM, Yang XF. Software test data generation automatically based on improved adaptive particle swarm optimizer. In:Zhang J, ed. Proc. of the 2010 Int'l Conf. on Computational and Information Sciences. Chengdu:IEEE CPS, 2010. 1300-1303.[doi:10. 1109/ICCIS.2010.321]
    [11] Wilcoxon F. Individual comparisons by ranking methods. Biometrics Bulletin, 1945,1(6):80-83.
    [12] Cohen J. Statistical Power Analysis for the Behavioral Sciences. 2nd ed., Lawrence Erlbaum Assoc. Inc., 1988.
    [13] Harman M, Jia Y, Zhang Y. Achievements, open problems and challenges for search based software testing. In:Wotawa F, ed. Proc. of the IEEE Int'l Conf. on Software Testing, Verification & Validation. Graz:GUM Press, 2015. 1-12.[doi:10.1109/ICST.2015. 7102580]
    [14] McMinn P. Search_Based software testing:Past, present and future. In:Schieferdecker I, Pretchner A, eds. Proc. of the 20114th Int'l Conf. on Software Testing, Verification and Validation Workshops. Berlin:CPS Press, 2011. 153-163.[doi:10.1109/ICSTW. 2011.100]
    [15] Sthamer H. The automatic generation of software test data using genetic algorithms[Ph.D. Thesis]. Brirain:University of Glamorgan, 1996.
    [16] Wegener J, Baresel A, Sthamer H. Evolutionary test environment for automatic structural testing. Information and Software Technology, 2001,43(14):841-854.[doi:10.1016/S0950-5849(01)00190-2]
    [17] Fraser G, Arcuri A. EvoSuite:Automatic test suite generation for object-oriented software. In:Gyimóthy T, Zeller A, eds. Proc. of the 19th ACM SIGSOFT Symp. and the 13th European Conf. on Foundations of Software Engineering(FSE). New York:ACM Press, 2011. 416-419.[doi:10.1145/2025113.2025179]
    [18] Fraser G, Arcuri A. Whole test suite generation. IEEE Trans. on Software Engineering, 2013,39(2):276-291.[doi:10.1109/TSE. 2012.14]
    [19] Fraser G, Arcuri A. A large scale evaluation of automated unit test generation using EvoSuite. ACM Trans. on Software Engineering and Methodology(TOSEM), 2014,24(2):8:1-8:42.[doi:10.1145/2685612]
    [20] Fraser G, Arcuri A, Mcminn P. A memetic algorithm for whole test suite generation. Journal of Systems & Software, 2014,103:311-327.[doi:10.1016/j.jss.2014.05.032]
    [21] Michael C, McGraw G, Schatz M. Generating software test data by evolution. IEEE Trans. on Software Engineering, 2001,27(12):1085-1110.[doi:10.1109/32.988709]
    [22] Miller J, Reformat M, Zhang H. Automatic test data generation using genetic algorithm and program dependence graphs. Information and Software Technology, 2006,48:586-605.[doi:10.1016/j.infsof.2005.06.006]
    [23] Watkins A, Hufnagel EM. Evolutionary test data generation:A comparison of fitness functions. Software Practice and Experience, 2006,36(1):95-116.[doi:10.1002/spe.684]
    [24] Hermadi I, Lokan C, Sarker R. Genetic algorithm based path testing:Challenges and key parameters. In:Huang XH, Xu LD, Zhou ZD, eds. Proc. of the 20102nd WRI World Congress on Software Engineering. Wuhan:IEEE Computer Society Press, 2010. 241-244.[doi:10.1109/WCSE.2010.82]
    [25] Mao CY, Yu XX, Xue YZ. Algorithm design and empirical analysis for particle swarm optimization-based test data generation. Journal of Computer Research and Development, 2014,51(4):824-837(in Chinese with English abstract).
    [26] Shi JJ, Jiang SJ, Han H, Wang LS. Adaptive particle swarm optimization algorithm and its application in test data generation. Acta Electronica Sinica, 2013,41(8):1555-1559(in Chinese with English abstract).
    附中文参考文献:
    [6] 王令赛,姜淑娟,张艳梅,于巧.基于正交搜索的粒子群优化测试用例生成方法.电子学报,2014,42(12):2345-2351.
    [25] 毛澄映,喻新欣,薛云志.基于粒子群优化的测试数据生成及其实证分析.计算机研究与发展,2014,51(4):824-837.
    [26] 史娇娇,姜淑娟,韩寒,王令赛.自适应粒子群优化算法及其在测试数据生成中的应用研究.电子学报,2013,41(8):1555-1559.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

姜淑娟,王令赛,薛猛,张艳梅,于巧,姚慧冉.基于模式组合的粒子群优化测试用例生成方法.软件学报,2016,27(4):785-801

Copy
Share
Article Metrics
  • Abstract:4932
  • PDF: 7613
  • HTML: 5675
  • Cited by: 0
History
  • Received:July 26,2015
  • Revised:October 20,2015
  • Online: January 14,2016
You are the first2035265Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063