面向类集成测试序列生成的强化学习研究
作者:
通讯作者:

张艳梅,E-mail:ymzhang@cumt.edu.cn;姜淑娟,E-mail:shjjiang@cumt.edu.cn

中图分类号:

TP311

基金项目:

国家自然科学基金(61673384, 71774159, 62162004, 51874292); 广西可信软件重点实验室开放课题(kx201608); 广西自然科学基金重点项目(2018GXNSFDA138003)


Generation Method of Class Integration Test Order Based on Reinforcement Learning
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [67]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    集成测试是软件测试过程中不可缺少的步骤, 针对在集成测试中如何对系统中的类合理排序的问题, 国内外研究者提出了多种生成类集成测试序列的方法, 然而他们大多没有将测试桩复杂度作为评估测试代价的指标. 针对该问题, 提出面向类集成测试序列生成的强化学习研究方法, 以总体测试桩复杂度为评价测试代价的指标, 生成测试代价尽可能低的类集成测试序列. 首先, 定义强化学习任务, 根据任务设定算法的追求目标; 其次, 进行程序的静态分析, 根据分析得到的结果计算测试桩复杂度; 然后, 将测试桩复杂度的计算融入奖励函数的设计中, 为选择下一步动作提供信息和依据; 最后, 通过奖励函数反馈值函数, 通过值函数的设定保证累计奖励最大化. 当智能体完成规定训练次数, 系统会选择获得最大累计奖励值的类集成测试序列进行输出, 即为我们追求的测试代价尽可能低的结果. 实验结果表明, 与现有方法相比, 在以总体测试桩复杂度为评价指标时, 提出的方法结果更优.

    Abstract:

    Integration testing is an indispensable step in the software testing process. In response to the problem of how to rationally sort the classes in the system in integration testing, researchers worldwide have proposed a variety of methods to generate class integration test orders. However, most of them didn’t take the stubbing complexity as the indicator, which is an important factor in evaluating the test cost. In order to solve this problem, this study proposes a method of generating a class integration test order based on reinforcement learning, using the overall stubbing complexity as the indicator to evaluate the test cost, and generating a class integration test order with the stubbing complexity as low as possible. First, the reinforcement learning task is defined, and the pursuit goal of the algorithm is set according to the task. Second, the static analysis of the program is performed and the stubbing complexity is calculated according to the results of the analysis. Then, the calculation of the stubbing complexity is integrated into the design of the reward function to provide information and basis for choosing the next action. Finally, the value function is fed back through the reward function, and the value function is set to ensure that the cumulative reward is maximized. When the agent completes the specified number of training times, the system will select the class integration test order that obtains the largest cumulative reward value for output, which costs the lowest stubbing complexity pursued. The experimental results show that the results obtained by this method are better than those obtained by other existing methods in terms of the overall stubbing complexity as the evaluation indicator.

    参考文献
    [1] Jiang SJ, Zhang M, Zhang YM, Wang RC, Yu Q, Keung JW. An integration test order strategy to consider control coupling. IEEE Transactions on Software Engineering, 2021, 47(7): 1350–1367. [doi: 10.1109/TSE.2019.2921965]
    [2] 周志华. 机器学习. 北京: 清华大学出版社, 2016. 371–397.
    Zhou ZH. Machine Learning. Beijing: Tsinghua University Press, 2016. 371–397 (in Chinese).
    [3] 何柳柳, 杨羊, 李征, 赵瑞莲. 面向持续集成测试优化的强化学习奖励机制. 软件学报, 2019, 30(5): 1438–1449. http://www.jos.org.cn/1000-9825/5714.htm
    He LL, Yang Y, Li Z, Zhao RL. Reward of reinforcement learning of test optimization for continuous integration. Ruan Jian Xue Bao/Journal of Software, 2019, 30(5): 1438-1449 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5714.htm
    [4] Czibula G, Czibula IG, Marian Z. An effective approach for determining the class integration test order using reinforcement learning. Applied Soft Computing, 2018, 65: 517–530. [doi: 10.1016/j.asoc.2018.01.042]
    [5] Mathur AP. Foundations of Software Testing. 2nd ed., Boston: Addison-Wesley, 2014. 40–41.
    [6] 张艳梅, 姜淑娟, 张妙, 鞠小林. 集成测试中的类测试顺序生成技术述评. 计算机学报, 2018, 41(3): 670–694. [doi: 10.11897/SP.J.1016.2018.00670]
    Zhang YM, Jiang SJ, Zhang M, Ju XL. Survey of class test order generation techniques for integration test. Chinese Journal of Computers, 2018, 41(3): 670–694 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2018.00670]
    [7] Briand LC, Labiche Y, Wang YH. An investigation of graph-based class integration test order strategies. IEEE Transactions on Software Engineering, 2003, 29(7): 594–607. [doi: 10.1109/TSE.2003.1214324]
    [8] Kung DC, Gao J, Hsia P, Lin J, Toyoshima Y. Class firewall, test order, and regression testing of object-oriented programs. Journal of Object Oriented Programming, 1995, 8(2): 51–65.
    [9] Briand LC, Labiche Y, Wang YH. Revisiting strategies for ordering class integration testing in the presence of dependency cycles. In: Proc. of the 12th Int’l Symp. on Software Reliability Engineering. Hong Kong: IEEE, 2001. 287–296.
    [10] Briand LC, Feng J, Labiche Y. Using genetic algorithms and coupling measures to devise optimal integration test orders. In: Proc. of the 14th Int’l Conf. on Software Engineering and Knowledge Engineering. Ischia: ACM, 2002. 43–50.
    [11] 姜淑娟, 张艳梅, 李海洋, 王庆坛. 一种基于耦合度量的类间集成测试序的确定方法. 计算机学报, 2011, 34(6): 1062–1074. [doi: 10.3724/SP.J.1016.2011.01062]
    Jiang SJ, Zhang YM, Li HY, Wang QT. An approach for inter-class integration test order determination based on coupling measures. Chinese Journal of Computers, 2011, 34(6): 1062–1074 (in Chinese with English abstract). [doi: 10.3724/SP.J.1016.2011.01062]
    [12] He DY, Xu JQ, Chen XL. Information-theoretic-entropy based weight aggregation method in multiple-attribute group decision-making. Entropy, 2016, 18(6): 171. [doi: 10.3390/e18060171]
    [13] 胡晓辉. 一种基于动态参数调整的强化学习动作选择机制. 计算机工程与应用, 2008, 44(28): 29–31, 48. [doi: 10.3778/j.issn.1002-8331.2008.28.009]
    Hu XH. Action choice mechanism of reinforcement learning based on adjusted dynamic parameters. Computer Engineering and Applications, 2008, 44(28): 29–31, 48 (in Chinese with English abstract). [doi: 10.3778/j.issn.1002-8331.2008.28.009]
    [14] SIR. A repository of software-related artifacts meant to support rigorous controlled experimentation. https://sir.csc.ncsu.edu/portal/index.php
    [15] Traon YL, Jéron T, Jezequel JM, Morel P. Efficient object-oriented integration and regression testing. IEEE Transactions on Reliability, 2000, 49(1): 12–25. [doi: 10.1109/24.855533]
    [16] Tai KC, Daniels FJ. Test order for inter-class integration testing of object-oriented software. In: Proc. of the 21st Annual Int’l Computer Software and Applications Conf. Washington: UEEE, 1997. 602–607.
    [17] Wang ZS, Li BX, Wang LL, Meng W, Gong XF. Using coupling measure technique and random iterative algorithm for inter-class integration test order problem. In: Proc. of the 34th Annual Computer Software and Applications Conf. Workshops. Seoul: IEEE, 2010. 329–334.
    [18] 张艳梅, 姜淑娟, 陈若玉, 王兴亚, 张妙. 基于粒子群优化算法的类集成测试序列确定方法. 计算机学报, 2018, 41(4): 931–945. [doi: 10.11897/SP.J.1016.2018.00931]
    Zhang YM, Jiang SJ, Chen RY, Wang XY, Zhang M. Class integration testing order determination method based on particle swarm optimization algorithm. Chinese Journal of Computers, 2018, 41(4): 931–945 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2018.00931]
    [19] Zhang M, Jiang SJ, Zhang YM, Wang XY, Yu Q. A multi-level feedback approach for the class integration and test order problem. The Journal of Systems and Software, 2017, 133: 54–67. [doi: 10.1016/j.jss.2017.08.026]
    [20] Kung D, Gao J, Pei H, Toyoshima Y, Chen C. A test strategy for object-oriented programs. In: Proc. of the 19th Annual Int’l Computer Software and Applications Conf. Dallas: IEEE, 1995. 239–244.
    [21] Kung DC, Gao J, Hsia P, Toyoshima Y, Chen C. On regression testing of object-oriented programs. Journal of Systems and Software, 1996, 32(1): 21–40. [doi: 10.1016/0164-1212(95)00047-X]
    [22] Tarjan R. Depth-first search and linear graph algorithms. SIMA Journal on Computing, 1971, 1(2): 146–160.
    [23] 高海昌, 冯博琴, 李远杰, 曾明. 基于扩展ORD图的类间集成测试顺序改进算法. 小型微型计算机系统, 2007, 28(4): 725–728. [doi: 10.3969/j.issn.1000-1220.2007.04.032]
    Gao HC, Feng BQ, Li YJ, Zeng M. Improved inter-class integration testing sequence algorithm based on extended ORD. Journal of Chinese Computer Systems, 2007, 28(4): 725–728 (in Chinese with English abstract). [doi: 10.3969/j.issn.1000-1220.2007.04.032]
    [24] 李远杰, 周国征, 刘凤晨. 一种类间测试顺序改进算法. 计算机工程, 2010, 36(8): 74–75, 82. [doi: 10.3969/j.issn.1000-3428.2010.08.026]
    Li YJ, Zhou GZ, Liu FC. Improved inter-class test sequence algorithm. Computer Engineering, 2010, 36(8): 74–75, 82 (in Chinese with English abstract). [doi: 10.3969/j.issn.1000-3428.2010.08.026]
    [25] 高建华, 齐丽娜. 基于对象模式关系图的测试顺序生成方法. 上海师范大学学报(自然科学版), 2008, 37(4): 369–376. [doi: 10.3969/j.issn.1000-5137.2008.04.006]
    Gao JH, Qi LN. Research of the test order generation based on OMRD. Journal of Shanghai Normal University (Natural Sciences), 2008, 37(4): 369–376 (in Chinese with English abstract). [doi: 10.3969/j.issn.1000-5137.2008.04.006]
    [26] Hashim NL, Schmidt HW, Ramakrishnan S. Test order for class-based integration testing of Java applications. In: Proc. of the 5th Int’l Conf. on Quality Software. Melbourne: IEEE, 2005. 11–18.
    [27] Abdurazik A, Offutt J. Coupling-based class integration and test order. In: Proc. of the 2006 Int’l Workshop on Automation of Software Test. Shanghai: ACM, 2006. 50–56.
    [28] Abdurazik A, Offutt J. Using coupling-based weights for the class integration and test order problem. Computer Journal, 2009, 52(5): 557–570. [doi: 10.1093/comjnl/bxm054]
    [29] Bansal P, Sabharwal S, Sidhu P. An investigation of strategies for finding test order during integration testing of object oriented applications. In: Proc. of the Int’l Conf. on Methods and Models in Computer Science. New Delhi: IEEE, 2009. 1–8.
    [30] Steindl M, Mottok J. Optimizing software integration by considering integration test complexity and test effort. In: Proc. of the 10th Int’l Workshop on Intelligent Solutions in Embedded Systems, 2012. 63–68.
    [31] 卢炎生, 毛澄映. 面向对象簇级测试中类间测试序确定方法研究. 小型微型计算机系统, 2005, 26(6): 995–999. [doi: 10.3969/j.issn.1000-1220.2005.06.028]
    Lu YS, Mao CY. Method of inter-class test order determination for object-oriented cluster level testing. Mini-Micro Systems, 2005, 26(6): 995–999 (in Chinese with English abstract). [doi: 10.3969/j.issn.1000-1220.2005.06.028]
    [32] Mao CY, Lu YS. Aicto: An improved algorithm for planning inter-class test order. In: Proc. of the 5th Int’l Conf. on Computer and Information Technology. Shanghai: IEEE, 2005. 927–931.
    [33] Hewett R, Kijsanayothin P. Automated test order generation for software component integration testing. In: Proc. of the 2009 IEEE/ACM Int’l Conf. on Automated Software Engineering. Auckland: IEEE, 2009. 211–220.
    [34] 赵玉丽, 王莹, 于海, 朱志良. 基于复杂网络的类间集成测试序列生成方法. 东北大学学报(自然科学版), 2015, 36(12): 1696–1700. [doi: 10.3969/j.issn.1005-3026.2015.12.006]
    Zhao YL, Wang Y, Yu H, Zhu ZL. An inter-class integration test order generation method based on complex networks. Journal of Northeastern University (Natural Science), 2015, 36(12): 1696–1700 (in Chinese with English abstract). [doi: 10.3969/j.issn.1005-3026.2015.12.006]
    [35] 王莹, 于海, 朱志良. 基于软件节点重要性的集成测试序列生成方法. 计算机研究与发展, 2016, 53(3): 517–530. [doi: 10.7544/issn1000-1239.2016.20148318]
    Wang Y, Yu H, Zhu ZL. A class integration test order method based on the node importance of software. Journal of Computer Research and Development, 2016, 53(3): 517–530 (in Chinese with English abstract). [doi: 10.7544/issn1000-1239.2016.20148318]
    [36] Zhang M, Keung JW, Xiao Y, Kabir MA. Evaluating the effects of similar-class combination on class integration test order generation. Information and Software Technology, 2021, 129: 106438. [doi: 10.1016/j.infsof.2020.106438]
    [37] 张妙, 姜淑娟, 张艳梅. 多目标优化类集成测试序列确定问题研究进展. 小型微型计算机系统, 2017, 38(8): 1772–1777. [doi: 10.3969/j.issn.1000-1220.2017.08.022]
    Zhang M, Jiang SJ, Zhang YM. Research on multi-objective optimization in class integration test order. Journal of Chinese Computer Systems, 2017, 38(8): 1772–1777 (in Chinese with English abstract). [doi: 10.3969/j.issn.1000-1220.2017.08.022]
    [38] Briand LC, Feng J, Labiche Y. Experimenting with genetic algorithms to devise optimal integration test orders. In: Khoshgoftaar TM, ed. Software Engineering with Computational Intelligence. The Springer Int’l Series in Engineering and Computer Science. Boston: Springer, 2003. 204–234.
    [39] Le Hanh V, Akif K, Le Traon Y, Jézéque JM. Selecting an efficient OO integration testing strategy: An experimental comparison of actual strategies. In: Proc. of the 15th European Conf. on Object-oriented Programming. Budapest: Springer, 2001. 381–401.
    [40] Borner L, Paech B. Integration test order strategies to consider test focus and simulation effort. In: Proc. of the 1st Int’l Conf. on Advances in System Testing and Validation Lifecycle. Porto: IEEE, 2009. 80–85.
    [41] Wang ZS, Li BX, Wang LL, and Qiao L. A brief survey on automatic integration test order generation. In: Proc. of the 23rd Int’l Conf. on Software Engineering and Knowledge Engineering. Eden Roc Renaissance, 2011. 254–257.
    [42] Wang ZS, Li BX, Wang LL, Li Q. An effective approach for automatic generation of class integration test order. In: Proc. of the 35th Annual Computer Software and Applications Conf. . Munich: IEEE, 2011. 680–681.
    [43] 张悦宁, 姜淑娟, 张艳梅. 基于梦境粒子群优化的类集成测试序列生成方法. 计算机科学, 2019, 46(2): 159–165. [doi: 10.11896/j.issn.1002-137X.2019.02.025]
    Zhang YN, Jiang SJ, Zhang YM. Approach for generating class integration test sequence based on dream particle swarm optimization algorithm. Computer Science, 2019, 46(2): 159–165 (in Chinese with English abstract). [doi: 10.11896/j.issn.1002-137X.2019.02.025]
    [44] da Veiga Cabral R, Pozo A, Vergilio SR. A pareto ant colony algorithm applied to the class integration and test order problem. In: Proc. of the 22nd IFIP WG 6.1 Int’l Conf. on Testing Software and Systems. Natal: Springer, 2010. 16–29.
    [45] Vergilio SR, Pozo A, Árias JCG, Da Veiga Cabral R, Nobre T. Multi-objective optimization algorithms applied to the class integration and test order problem. International Journal on Software Tools for Technology Transfer, 2012, 14(4): 461–475. [doi: 10.1007/s10009-012-0226-1]
    [46] Assunção WKG, Colanzi TE, Pozo ATR, Vergilio SR. Establishing integration test orders of classes with several coupling measures. In: Proc. of the 13th Annual Conf. on Genetic and Evolutionary Computation. Dublin: ACM, 2011. 1867–1874.
    [47] Assunção WKG, Colanzi TE, Vergilio SR, Pozo A. A multi-objective optimization approach for the integration and test order problem. Information Sciences, 2014, 267: 119–139. [doi: 10.1016/j.ins.2013.12.040]
    [48] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182–197. [doi: 10.1109/4235.996017]
    [49] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength pareto evolutionary algorithm. In: Proc. of the Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems, 2001. 95–100.
    [50] Knowles JD, Corne DW. Approximating the nondominated front using the Pareto archived evolution strategy. Evolutionary Computation, 2000, 8(2): 149–172. [doi: 10.1162/106365600568167]
    [51] Zhang M, Keung J, Xiao Y, Kabir MA, Feng S. A heuristic approach to break cycles for the class integration test order generation. In: Proc. of the 43rd Annual Computer Software and Applications Conf. Milwaukee: IEEE, 2019. 47–52.
    [52] Guizzo G, Fritsche GM, Vergilio SR, Pozo ATR. A hyper-heuristic for the multi-objective integration and test order problem. In: Proc. of the 2015 Annual Conf. on Genetic and Evolutionary Computation. Madrid: ACM, 2015. 1343–1350.
    [53] Mariani T, Guizzo G, Vergilio SR, Pozo ATR. Grammatical evolution for the multi-objective integration and test order problem. In: Proc. of the Genetic and Evolutionary Computation Conf. Denver: ACM, 2016. 1069–1076.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

丁艳茹,张艳梅,姜淑娟,袁冠,王荣存,钱俊彦.面向类集成测试序列生成的强化学习研究.软件学报,2022,33(5):1674-1698

复制
分享
文章指标
  • 点击次数:1303
  • 下载次数: 4493
  • HTML阅读次数: 3799
  • 引用次数: 0
历史
  • 收稿日期:2021-08-10
  • 最后修改日期:2021-10-09
  • 在线发布日期: 2022-01-28
  • 出版日期: 2022-05-06
文章二维码
您是第19710078位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号