这是indexloc提供的服务，不要输入任何密码
Skip to main content
Springer Nature Link
Log in

A Reinforcement Learning Based Approach to Partition Testing

  • Regular Paper
  • Published:
Journal of Computer Science and Technology Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MATH  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: https://doi.org/10.1109/32.368132.

    Article  MATH  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: https://doi.org/10.1109/COMPSAC.2005.118.

    MATH  Google Scholar 

  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: https://doi.org/10.1016/j.jss.2006.11.008.

    Article  MATH  Google Scholar 

  6. Hamlet R. Random testing. In Encyclopedia of Software Engineering, Marciniak J J (ed.), John Wiley, 2002. DOI: https://doi.org/10.1002/0471028959.sof268.

    MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  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.

    MATH  Google Scholar 

  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: https://doi.org/10.1016/j.infsof.2020.106470.

    Article  MATH  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: https://doi.org/10.1109/COMPSACW.2011.14.

    MATH  Google Scholar 

  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: https://doi.org/10.1109/COMPSACW.2014.9.

    Google Scholar 

  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: https://doi.org/10.1109/COMPSACW.2014.10.

    Google Scholar 

  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: https://doi.org/10.1109/COMPSAC.2015.257.

    MATH  Google Scholar 

  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: https://doi.org/10.1109/TC.2018.2866040.

    Article  MathSciNet  MATH  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: https://doi.org/10.1016/S0950-5849(02)00108-8.

    Article  MATH  Google Scholar 

  17. Sutton R S, Barto A G. Reinforcement Learning: An Introduction. MIT Press, 1998.

    MATH  Google Scholar 

  18. Watkins C J C H. Learning from delayed rewards [Ph.D. Thesis]. University of Cambridge, Cambridge, 1989.

    MATH  Google Scholar 

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

    Article  MATH  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/∼shiv-aram/readings/b2hd-RummeryNiranjan1994.html.

    MATH  Google Scholar 

  21. Mohri M, Rostamizadeh A, Talwalkar A. Foundations of Machine Learning (2nd edition). MIT Press, 2018.

    MATH  Google Scholar 

  22. Mitchell T M. Machine Learning. McGraw-Hill, Inc., 1997.

    MATH  Google Scholar 

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

    Article  MATH  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: https://doi.org/10.1038/nature14236.

    Article  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.

    Google Scholar 

  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.

    Google Scholar 

  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: https://doi.org/10.1109/MSP.2017.2743240.

    Article  Google Scholar 

  28. Lattimore T, Szepesvári C. Bandit Algorithms. Cambridge University Press, 2020. DOI: https://doi.org/10.1017/9781108571401.

    Book  MATH  Google Scholar 

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

    Article  MATH  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.

    MATH  Google Scholar 

  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: https://doi.org/10.1145/62959.62964.

    Article  MATH  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: https://doi.org/10.1145/800027.808473.

    Chapter  MATH  Google Scholar 

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

    Article  MATH  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: https://doi.org/10.1007/s10664-005-3861-2.

    Article  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: https://doi.org/10.1109/TSC.2019.2960496.

    Article  MATH  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: https://doi.org/10.1002/stvr.308.

    Article  MATH  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: https://doi.org/10.1145/1985793.1985795.

    MATH  Google Scholar 

  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: https://doi.org/10.1145/3533314.

  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.

    MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  41. Hedges L V, Olkin I. Statistical Methods for Meta-Analysis. Academic Press, 2014.

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  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: https://doi.org/10.1109/TSMC.2014.2318019.

    Article  MATH  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: https://doi.org/10.1109/TSE.2014.2310194.

    Article  MATH  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: https://doi.org/10.1016/j.jss.2009.02.022.

    Article  MATH  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: https://doi.org/10.23919/CISTI49556.2020.9141124.

    MATH  Google Scholar 

  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: https://doi.org/10.1145/3395363.3397354.

    Chapter  MATH  Google Scholar 

  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: https://doi.org/10.1109/icst.2018.00020.

    Google Scholar 

  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: https://doi.org/10.1145/3502868.

  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: https://doi.org/10.1145/3278186.3278191.

    MATH  Google Scholar 

  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: https://doi.org/10.1145/3278186.3278187.

    Google Scholar 

  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: https://doi.org/10.1145/3194718.3194720.

    Chapter  MATH  Google Scholar 

  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: https://doi.org/10.1613/jair.1.12190.

    Article  MathSciNet  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: https://doi.org/10.1007/11940197_16.

    Chapter  MATH  Google Scholar 

  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: https://doi.org/10.1109/ase.2019.00077.

    MATH  Google Scholar 

  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: https://doi.org/10.1109/cog47356.2020.9231552.

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing, 100083, China

    Chang-Ai Sun  (孙昌爱), Ming-Jun Xiao  (肖明俊) & He-Peng Dai  (代贺鹏)

  2. Department of Computing Technologies, Swinburne University of Technology, Hawthorn, VIC, 3122, Australia

    Huai Liu  (刘 淮)

Authors
  1. Chang-Ai Sun  (孙昌爱)
    View author publications

    Search author on:PubMed Google Scholar

  2. Ming-Jun Xiao  (肖明俊)
    View author publications

    Search author on:PubMed Google Scholar

  3. He-Peng Dai  (代贺鹏)
    View author publications

    Search author on:PubMed Google Scholar

  4. Huai Liu  (刘 淮)
    View author publications

    Search author on:PubMed Google Scholar

Corresponding authors

Correspondence to Chang-Ai Sun  (孙昌爱), Ming-Jun Xiao  (肖明俊), He-Peng Dai  (代贺鹏) or Huai Liu  (刘 淮).

Ethics declarations

Conflict of Interest The authors declare that they have no conflict of interest.

Additional information

This work was supported by the National Natural Science Foundation of China under Grant Nos. 62272037 and 61872039, the Beijing Natural Science Foundation under Grant No. 4162040, the Aeronautical Science Foundation of China under Grant No. 2016ZD74004, the Fundamental Research Funds for the Central Universities of China under Grant No. FRF-GF-19-B19, and the Australian Research Council Discovery Project under Grant No. DP210102447.

Chang-Ai Sun received his B.S. degree in computer science from the University of Science and Technology Beijing, Beijing, in 1997, and his Ph.D. degree in computer science from Beihang University, Beijing, in 2002. He is a professor with the School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing. His research interests include software testing, program analysis, and service-oriented computing.

Ming-Jun Xiao received his B.S. degree in information and computing sciences from the University of Science and Technology Beijing, Beijing, in 2020. He is working toward his M.S. degree in the School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing. His current research interests include software testing and debugging.

He-Peng Dai received his B.S. degree in information and computing sciences from China University of Mining and Technology, Beijing, in 2016, and his M.S. degree in software engineering from the University of Science and Technology Beijing, Beijing, in 2018. He is working toward his Ph.D. degree in the School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing. His current research interests include software testing and debugging.

Huai Liu received his B.S. degree in physioelectronic technology and M.S. degree in communications and information systems, from Nankai University, Tianjin, in 1998 and 2003, respectively, and his Ph.D. degree in software engineering from Swinburne University of Technology, Melbourne, in 2008. He is a senior lecturer at the Department of Computing Technologies, Swinburne University of Technology, Melbourne. His research interests include software testing, cloud computing, and end-user software engineering.

Electronic supplementary material

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sun, CA., Xiao, MJ., Dai, HP. et al. A Reinforcement Learning Based Approach to Partition Testing. J. Comput. Sci. Technol. 40, 99–118 (2025). https://doi.org/10.1007/s11390-024-2900-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Version of record:

  • Issue date:

  • DOI: https://doi.org/10.1007/s11390-024-2900-7

Keywords