Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Abstract
Keywords
Electronic Supplementary Material
References
Show full outline
Hide outline
Regular Paper

A Reinforcement Learning Based Approach to Partition Testing

School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing 100083, China
Department of Computing Technologies, Swinburne University of Technology, Hawthorn VIC 3122, Australia
Show Author Information

Abstract

Partition testing is one of the most fundamental and popularly used software testing techniques. It first divides the input domain of the program under test into a set of disjoint partitions, and then creates test cases based on these partitions. Motivated by the theory of software cybernetics, some strategies have been proposed to dynamically select partitions based on the feedback information gained during testing. The basic intuition of these strategies is to assign higher probabilities to those partitions with higher fault-detection potentials, which are judged and updated mainly according to the previous test results. Such a feedback-driven mechanism can be considered as a learning process—it makes decisions based on the observations acquired in the test execution. Accordingly, advanced learning techniques could be leveraged to empower the smart partition selection, with the purpose of further improving the effectiveness and efficiency of partition testing. In this paper, we particularly leverage reinforcement learning to enhance the state-of-the-art adaptive partition testing techniques. Two algorithms, namely RLAPT_Q and RLAPT_S, have been developed to implement the proposed approach. Empirical studies have been conducted to evaluate the performance of the proposed approach based on seven object programs with 26 faults. The experimental results show that our approach outperforms the existing partition testing techniques in terms of the fault-detection capability as well as the overall testing time. Our study demonstrates the applicability and effectiveness of reinforcement learning in advancing the performance of software testing.

Keywords

partition testingreinforcement learningtemporal-difference learningintelligent software engineering

Electronic Supplementary Material

Download File(s)
JCST-2210-12900-Highlights.pdf (318.6 KB)

References

[1]

Hamlet D, Taylor R. Partition testing does not inspire confidence (program testing). IEEE Trans. Software Engineering, 1990, 16(12): 1402–1411. DOI: 10.1109/32.62448.

Crossref Google Scholar
[2]

Weyuker E J, Jeng B. Analyzing partition testing strategies. IEEE Trans. Software Engineering, 1991, 17(7): 703–711. DOI: 10.1109/32.83906.

Crossref Google Scholar
[3]

Chen T Y, Yu Y T. On the relationship between partition and random testing. IEEE Trans. Software Engineering, 1994, 20(12): 977–980. DOI: 10.1109/32.368132.

Crossref Google Scholar
[4]
Cai K Y, Jing T, Bai C G. Partition testing with dynamic partitioning. In Proc. the 29th Annual International Computer Software and Applications Conference, Jul. 2005, pp.113–116. DOI: 10.1109/COMPSAC.2005.118.
Crossref
[5]

Cai K Y, Gu B, Hu H, Li Y C. Adaptive software testing with fixed-memory feedback. Journal of Systems and Software, 2007, 80(8): 1328–1348. DOI: 10.1016/j.jss.2006.11.008.

Crossref Google Scholar
[6]
Hamlet R. Random testing. In Encyclopedia of Software Engineering, Marciniak J J (ed.), John Wiley, 2002. DOI: 10.1002/0471028959.sof268.
Crossref
[7]

Ammann P E, Knight J C. Data diversity: An approach to software fault tolerance. IEEE Trans. Computers, 1988, 37(4): 418–425. DOI: 10.1109/12.2185.

Crossref Google Scholar
[8]

Finelli G B. NASA software failure characterization experiments. Reliability Engineering & System Safety, 1991, 32(1/2): 155–169. DOI: 10.1016/0951-8320(91)90052-9.

Crossref Google Scholar
[9]
Cai K Y, Hu H, Jiang C H, Ye F. Random testing with dynamically updated test profile. In Proc. the 20th International Symposium on Software Reliability Engineering, Nov. 2009.
[10]

Pei H, Yin B, Xie M, Cai K Y. Dynamic random testing with test case clustering and distance-based parameter adjustment. Information and Software Technology, 2021, 131:106470. DOI: 10.1016/j.infsof.2020.106470.

Crossref Google Scholar
[11]
Lv J, Hu H, Cai K Y. A sufficient condition for parameters estimation in dynamic random testing. In Proc. the 35th IEEE Annual Computer Software and Applications Conference Workshops, Jul. 2011, pp.19–24. DOI: 10.1109/COMPSACW.2011.14.
Crossref
[12]
Zhang L, Yin B B, Lv J, Cai K Y, Yau S S, Yu J. A history-based dynamic random software testing. In Proc. the 38th IEEE International Computer Software and Applications Conference Workshops, Jul. 2014, pp.31–36. DOI: 10.1109/COMPSACW.2014.9.
Crossref
[13]
Yang Z, Yin B, Lv J, Cai K, Yau S S, Yu J. Dynamic random testing with parameter adjustment. In Proc. the 38th IEEE International Computer Software and Applications Conference Workshops, Jul. 2014, pp.37–42. DOI: 10.1109/COMPSACW.2014.10.
Crossref
[14]
Li Y, Yin B B, Lv J, Cai K Y. Approach for test profile optimization in dynamic random testing. In Proc. the 39th IEEE Annual Computer Software and Applications Conference, Jul. 2015, pp.466–471. DOI: 10.1109/COMPSAC.2015.257.
Crossref
[15]

Sun C A, Dai H, Liu H, Chen T Y, Cai K Y. Adaptive partition testing. IEEE Trans. Computers, 2019, 68(2): 157–169. DOI: 10.1109/TC.2018.2866040.

Crossref Google Scholar
[16]

Cai K Y. Optimal software testing and adaptive software testing in the context of software cybernetics. Information and Software Technology, 2002, 44(14): 841–855. DOI: 10.1016/S0950-5849(02)00108-8.

Crossref Google Scholar
[17]
Sutton R S, Barto A G. Reinforcement Learning: An Introduction. MIT Press, 1998.
Crossref
[18]
Watkins C J C H. Learning from delayed rewards [Ph.D. Thesis]. University of Cambridge, Cambridge, 1989.
[19]

Watkins C J C H, Dayan P. Q-learning. Machine Learning, 1992, 8(3): 279–292. DOI: 10.1007/BF00992698.

Crossref Google Scholar
[20]
Rummery G A, Niranjan M. On-line Q-learning using connectionist systems. Technical Report TR166, University of Cambridge, 1994. https://www.cs.utexas.edu/~shivaram/readings/b2hd-RummeryNiranjan1994.html.
[21]
Mohri M, Rostamizadeh A, Talwalkar A. Foundations of Machine Learning (2nd edition). MIT Press, 2018.
[22]
Mitchell T M. Machine Learning. McGraw-Hill, Inc., 1997.
[23]

Tesauro G. Temporal difference learning and TD-gammon. Communications of the ACM, 1995, 38(3): 58–68. DOI: 10.1145/203330.203343.

Crossref Google Scholar
[24]

Mnih V, Kavukcuoglu K, Silver D, Rusu A A, Veness J, Bellemare M G, Graves A, Riedmiller M, Fidjeland A K, Ostrovski G, Petersen S, Beattie C, Sadik A, Antonoglou I, King H, Kumaran D, Wierstra D, Legg S, Hassabis D. Human-level control through deep reinforcement learning. Nature, 2015, 518(7540): 529–533. DOI: 10.1038/nature14236.

Crossref Google Scholar
[25]
Schulman J, Levine S, Abbeel P, Jordan M, Moritz P. Trust region policy optimization. In Proc. the 32nd International Conference on Machine Learning, Jul. 2015, pp.1889–1897.
[26]
Mnih V, Badia A P, Mirza M, Graves A, Lillicrap T, Harley T, Silver D, Kavukcuoglu K. Asynchronous methods for deep reinforcement learning. In Proc. the 33rd International Conference on Machine Learning, Jun. 2016, pp.1928–1937.
[27]

Arulkumaran K, Deisenroth M P, Brundage M, Bharath A A. Deep reinforcement learning: A brief survey. IEEE Signal Processing Magazine, 2017, 34(6): 26–38. DOI: 10.1109/MSP.2017.2743240.

Crossref Google Scholar
[28]
Lattimore T, Szepesvári C. Bandit Algorithms. Cambridge University Press, 2020. DOI: 10.1017/9781108571401.
Crossref
[29]

Spieker H, Gotlieb A. Adaptive metamorphic testing with contextual bandits. Journal of Systems and Software, 2020, 165:110574. DOI: 10.1016/j.jss.2020.110574.

Crossref Google Scholar
[30]
Baskiotis N, Sebag M, Gaudel M C, Gouraud S D. EXIST: Exploitation/exploration inference for statistical software testing. In Proc. the On-line Trading of Exploration and Exploitation, NIPS 2006 Workshop, Dec. 2006.
[31]

Ostrand T J, Balcer M J. The category-partition method for specifying and generating fuctional tests. Communications of the ACM, 1988, 31(6): 676–686. DOI: 10.1145/62959.62964.

Crossref Google Scholar
[32]
Goodenough J B, Gerhart S L. Toward a theory of test data selection. In Proc. the 1975 International Conference on Reliable Software, Apr. 1975, pp.493–510. DOI: 10.1145/800027.808473.
Crossref
[33]

Grochtmann M, Grimm K. Classification trees for partition testing. Software Testing, Verification and Reliability, 1993, 3(2): 63–82. DOI: 10.1002/stvr.4370030203.

Crossref Google Scholar
[34]

Do H, Elbaum S, Rothermel G. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Empirical Software Engineering, 2005, 10(4): 405–435. DOI: 10.1007/s10664-005-3861-2.

Crossref Google Scholar
[35]

Sun C A, Dai H P, Wang G, Towey D, Chen T Y, Cai K Y. Dynamic random testing of web services: A methodology and evaluation. IEEE Trans. Services Computing, 2022, 15(2): 736–751. DOI: 10.1109/TSC.2019.2960496.

Crossref Google Scholar
[36]

Ma Y S, Offutt J, Kwon Y R. MuJava: An automated class mutation system. Software Testing, Verification and Reliability, 2005, 15(2): 97–133. DOI: 10.1002/stvr.308.

Crossref Google Scholar
[37]
Arcuri A, Briand L. A practical guide for using statistical tests to assess randomized algorithms in software engineering. In Proc. the 33rd International Conference on Software Engineering, May 2011, pp.1–10. DOI: 10.1145/1985793.1985795.
Crossref
[38]

Sun C A, Dai H P, Liu H, Chen T Y. Feedback-directed metamorphic testing. ACM Trans. Software Engineering and Methodology, 2023, 32(1): Article No. 20. DOI: 10.1145/3533314.

Crossref Google Scholar
[39]
Szepesvári C. The asymptotic convergence-rate of Q-learning. In Proc. the 10th International Conference on Neural Information Processing Systems, Dec. 1997, pp.1064–1070.
[40]

Even-Dar E, Mansour Y. Learning Rates for Q-learning. Journal of Machine Learning Research, 2003, 5:1–25.

Google Scholar
[41]
Hedges L V, Olkin I. Statistical Methods for Meta-Analysis. Academic Press, 2014.
[42]

Sawilowsky S S. New effect size rules of thumb. Journal of Modern Applied Statistical Methods, 2009, 8(2): 597–599. DOI: 10.22237/jmasm/1257035100.

Crossref Google Scholar
[43]

Lv J, Hu H, Cai K Y, Chen T Y. Adaptive and random partition software testing. IEEE Trans. Systems, Man, and Cybernetics: Systems, 2014, 44(12): 1649–1664. DOI: 10.1109/TSMC.2014.2318019.

Crossref Google Scholar
[44]

Lv J, Yin B B, Cai K Y. On the asymptotic behavior of adaptive testing strategy for software reliability assessment. IEEE Trans. Software Engineering, 2014, 40(4): 396–412. DOI: 10.1109/TSE.2014.2310194.

Crossref Google Scholar
[45]

Chen T Y, Kuo F C, Merkel R G, Tse T H. Adaptive random testing: The art of test case diversity. Journal of Systems and Software, 2010, 83(1): 60–66. DOI: 10.1016/j.jss.2009.02.022.

Crossref Google Scholar
[46]
Lima R, da Cruz A M R, Ribeiro J. Artificial intelligence applied to software testing: A literature review. In Proc. the 15th Iberian Conference on Information Systems and Technologies, Jun. 2020. DOI: 10.23919/CISTI49556.2020.9141124.
Crossref
[47]
Pan M, Huang A, Wang G, Zhang T, Li X. Reinforcement learning based curiosity-driven testing of Android applications. In Proc. the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis, Jul. 2020, pp.153–164. DOI: 10.1145/3395363.3397354.
Crossref
[48]
Koroglu Y, Sen A, Muslu O, Mete Y, Ulker C, Tanriverdi T, Donmez Y. QBE: QLearning-based exploration of android applications. In Proc. the 11th IEEE International Conference on Software Testing, Verification and Validation, Apr. 2018, pp.105–115. DOI: 10.1109/icst.2018.00020.
Crossref
[49]

Romdhana A, Merlo A, Ceccato M, Tonella P. Deep reinforcement learning for black-box testing of android apps. ACM Trans. Software Engineering and Methodology (TOSEM), 2022, 31(4): Article No. 65. DOI: 10.1145/3502868.

Crossref Google Scholar
[50]
Vuong T A, Takada S. A reinforcement learning based approach to automated testing of Android applications. In Proc. the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation, Nov. 2018, pp.31–37. DOI: 10.1145/3278186.3278191.
Crossref
[51]
Adamo D, Khan M K, Koppula S, Bryce R. Reinforcement learning for android GUI testing. In Proc. the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation, Nov. 2018, pp.2–8. DOI: 10.1145/3278186.3278187.
Crossref
[52]
Kim J, Kwon M, Yoo S. Generating test input with deep reinforcement learning. In Proc. the 11th International Workshop on Search-Based Software Testing, May 2018, pp.51–58. DOI: 10.1145/3194718.3194720.
Crossref
[53]

Lee R, Mengshoel O J, Saksena A, Gardner R W, Genin D, Silbermann J, Owen M, Kochenderfer M J. Adaptive stress testing: Finding likely failure events with reinforcement learning. Journal of Artificial Intelligence Research, 2020, 69:1165–1201. DOI: 10.1613/jair.1.12190.

Crossref Google Scholar
[54]
Veanes M, Roy P, Campbell C. Online testing with reinforcement learning. In Proc. the 1st Combined International Workshops on Formal Approaches to Software Testing and Runtime Verification, Aug. 2006, pp.240–253. DOI: 10.1007/11940197_16.
Crossref
[55]
Harries L, Clarke R S, Chapman T, Nallamalli S V P L N, Ozgur L, Jain S, Leung A, Lim S, Dietrich A, Hernández-Lobato J M, Ellis T, Zhang C, Ciosek K. DRIFT: Deep reinforcement learning for functional software testing. arXiv: 2007.08220, 2020. https://arxiv.org/abs/2007.08220, Dec. 2024.
[56]
Zheng Y, Xie X, Su T, Ma L, Hao J, Meng Z, Liu Y, Shen R, Chen Y, Fan C. Wuji: Automatic online combat game testing using evolutionary deep reinforcement learning. In Proc. the 34th IEEE/ACM International Conference on Automated Software Engineering, Nov. 2019, pp.772–784. DOI: 10.1109/ase.2019.00077.
Crossref
[57]
Bergdahl J, Gordillo C, Tollmar K, Gisslén L. Augmenting automated game testing with deep reinforcement learning. In Proc. the 2020 IEEE Conference on Games, Aug. 2020, pp.600–603. DOI: 10.1109/cog47356.2020.9231552.
Crossref
Journal of Computer Science and Technology
Volume 40 Issue 1,
February 2025
Pages 99-118
DOI: 10.1007/s11390-024-2900-7
Cite this article:
Sun C-A, Xiao M-J, Dai H-P, et al. A Reinforcement Learning Based Approach to Partition Testing. Journal of Computer Science and Technology, 2025, 40(1): 99-118. https://doi.org/10.1007/s11390-024-2900-7
Metrics & Citations  
Article History
Copyright
Return