Cost-effective learning-based strategies for test case prioritization in continuous integration of highly-configurable software | Empirical Software Engineering Skip to main content

Advertisement

Springer Nature Link
Log in

Cost-effective learning-based strategies for test case prioritization in continuous integration of highly-configurable software

  • Published:
Empirical Software Engineering Aims and scope Submit manuscript

Abstract

Highly-Configurable Software (HCSs) testing is usually costly, as a significant number of variants need to be tested. This becomes more problematic when Continuous Integration (CI) practices are adopted. CI leads the software to be integrated and tested multiple times a day, subject to time constraints (budgets). To address CI challenges, a learning-based test case prioritization approach named COLEMAN has been successfully applied. COLEMAN deals with test case volatility, in which some test cases can be included/removed over the CI cycles. Nevertheless, such an approach does not consider HCS particularities such as, by analogy, the volatility of variants. Given such a context, this work introduces two strategies for applying COLEMAN in the CI of HCS: the Variant Test Set Strategy (VTS) that relies on the test set specific for each variant; and the Whole Test Set Strategy (WST) that prioritizes the test set composed by the union of the test cases of all variants. Both strategies are applied to two real-world HCSs, considering three test budgets. Independently of the time budget, the proposed strategies using COLEMAN have the best performance in comparison with solutions generated randomly and by another learning approach from the literature. Moreover, COLEMAN produces, in more than 92% of the cases, reasonable solutions that are near to the optimal solutions obtained by a deterministic approach. Both strategies spend less than one second to execute. WTS provides better results in the less restrictive budgets, and VTS the opposite. WTS seems to better mitigate the problem of beginning without knowledge, and is more suitable when a new variant to be tested is added.

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+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. https://gitlab.com/libssh/libssh-mirror/-/commit/17b518a677c92d943cf016b81272ec10ee1ca368

  2. https://gitlab.com/libssh/libssh-mirror/pipelines/116809311/builds

  3. https://gitlab.com/libssh/libssh-mirror/-/jobs/432862254

  4. The implementation of COLEMAN for HCS is available at: https://github.com/jacksonpradolima/coleman4hcs.

  5. The systems and data collected, as well as the values found for each metric with statistical test results and plots, are available in our supplementary material (Prado Lima et al. 2021).

  6. LIBSSH at https://gitlab.com/libssh/libssh-mirror and DUNE at https://gitlab.dune-project.org

  7. https://gitlab.com/libssh/libssh-mirror/-/jobs/432862254#L837

  8. https://github.com/jacksonpradolima/gitlabci-torrent

  9. https://www.libssh.org/

  10. https://www.dune-project.org/

  11. The implementation of the deterministic approach is available at: https://github.com/jacksonpradolima/deterministic-optimal-tcpci.

  12. See supplementary material about characteristics of this variant. Available in Prado Lima et al. (2021).

References

  • Al-Hajjaji M, Lity S, Lachmann R, Thüm T, Schaefer I, Saake G (2017) Delta-oriented product prioritization for similarity-based product-line testing. In: 2017 IEEE/ACM 2nd International Workshop on Variability and Complexity in Software Design (VACE). IEEE, pp 34–40

  • Arcuri A, Briand L (2011) A practical guide for using statistical tests to assess randomized algorithms in software engineering. In: 33rd International Conference on Software Engineering, ICSE’11. ACM, New York, pp 1–10. https://doi.org/10.1145/1985793.1985795

  • Bertolino A, Guerriero A, Miranda B, Pietrantuono R, Russo S (2020) Learning-to-rank vs ranking-to-learn: Strategies for regression testing in continuous integration. In: 42nd International Conference on Software Engineering, ICSE’20. ACM, New York

  • Capilla R, Bosch J, Kang KC (2013) Systems and software variability management: Concepts, tools and experiences. Springer

  • Cho Y, Kim J, Lee E (2016) History-Based Test Case Prioritization for Failure Information. In: 2016 23rd Asia-Pacific Software Engineering Conference (APSEC), pp 385–388

  • Colanzi TE, Assunção WKG, Farah PR, Vergilio SR, Guizzo G (2019) A review of ten years of the symposium on search-based software engineering. In: Symposium on Search-Based Software Engineering. Springer, Cham, pp 42–57

  • Dayhoff J E (1990) Neural network architectures: an introduction. Van Nostrand Reinhold Co.

  • Do H, Mirarab S, Tahvildari L, Rothermel G (2008) An empirical study of the effect of time constraints on the cost-benefits of regression testing. In: 16th ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, New York, pp 71–82

  • Duvall P M, Matyas S, Glover A (2007) Continuous integration: improving software quality and reducing risk. Pearson Education

  • Elbaum S, Rothermel G, Penix J (2014) Techniques for improving regression testing in continuous integration development environments. In: 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, New York, pp 235–245

  • Engström E (2010) Regression test selection and product line system testing. In: 3rd International Conference on Software Testing, Verification and Validation. IEEE, pp 512–515

  • Ensan A, Bagheri E, Asadi M, Gasevic D, Biletskiy Y (2011) Goal-oriented test case selection and prioritization for product line feature models. In: 8th International Conference on Information Technology: New Generations. IEEE, pp 291–298. https://doi.org/10.1109/ITNG.2011.58

  • Gargantini A, Petke J, Radavelli M, Vavassori P (2016) Validation of constraints among configuration parameters using search-based combinatorial interaction testing. In: 8th International Symposium on Search Based Software Engineering. Springer, Cham, pp 49–63

  • Haghighatkhah A, Mäntylä M, Oivo M, Kuvaja P (2018) Test prioritization in continuous integration environments. J Syst Softw 146:80–98. https://doi.org/10.1016/j.jss.2018.08.061

    Article  Google Scholar 

  • Hajri I, Goknil A, Pastore F, Briand L C (2020) Automating system test case classification and prioritization for use case-driven testing in product lines. Empir Softw Eng 25(5):3711–3769

    Article  Google Scholar 

  • Jung P, Kang S, Lee J (2019) Automated code-based test selection for software product line regression testing. J Syst Softw 158:110419. https://doi.org/10.1016/j.jss.2019.110419

  • Kumar S (2016) Rajkumar: Test case prioritization techniques for software product line: A survey. In: International Conference on Computing, Communication and Automation (ICCCA). IEEE, pp 884–889

  • Lachmann R, Beddig S, Lity S, Schulze S, Schaefer I (2017) Risk-based integration testing of software product lines. In: 11th International Workshop on Variability Modelling of Software-intensive Systems, pp 52–59

  • Lachmann R, Lity S, Lischke S, Beddig S, Schulze S, Schaefer I (2015) Delta-oriented test case prioritization for integration testing of software product lines. In: 19th International Conference on Software Product Line, pp 81–90

  • Li K, Fialho A, Kwong S, Zhang Q (2014) Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 18(1):114–130

    Article  Google Scholar 

  • Lity S, Nieke M, Thöm T, Schaefer I (2019) Retest test selection for product-line regression testing of variants and versions of variants. J Syst Softw 147:46–63

  • Lochau M, Schaefer I, Kamischke J, Lity S (2012) Incremental model-based testing of delta-oriented software product lines. In: Tests and Proofs. Springer, Berlin, pp 67–82

  • Mann H B, Whitney D R (1947) On a test of whether one of two random variables is stochastically larger than the other. Ann Math Stat 18:50–60

    Article  MathSciNet  Google Scholar 

  • Marijan D (2015) Multi-perspective regression test prioritization for time-constrained environments. In: Proceedings of the IEEE International Conference on Software Quality, Reliability and Security, QRS. IEEE Computer Society, pp 157–162

  • Marijan D, Gotlieb A, Liaaen M (2019) A learning algorithm for optimizing continuous integration development and testing practice. Softw Practice Exper 49(2):192–213

    Article  Google Scholar 

  • Marijan D, Gotlieb A, Liaaen M (2019) A learning algorithm for optimizing continuous integration development and testing practice. Softw Practice Exper 49(2):192–213. https://doi.org/10.1002/spe.2661

  • Marijan D, Gotlieb A, Sen S (2013) Test case prioritization for continuous regression testing: An industrial case study. In: IEEE International Conference on Software Maintenance, ICMS. IEEE, pp 540–543

  • Marijan D, Liaaen M (2017) Test prioritization with optimally balanced configuration coverage. In: IEEE 18th International Symposium on High Assurance Systems Engineering, HASE. IEEE, pp 100–103

  • Marijan D, Liaaen M, Gotlieb A, Sen S, Ieva C (2017) Titan: Test suite optimization for highly configurable software. In: IEEE International Conference on Software Testing, Verification and Validation, ICST. IEEE, pp 524–531

  • Medeiros F, Kstner C, Ribeiro M, Gheyi R, Apel S (2016) A comparison of 10 sampling algorithms for configurable systems. In: 38th International Conference on Software Engineering, ICSE’16. ACM, New York, pp 643–54

  • Medeiros F, Ribeiro M, Gheyi R, Apel S, Kstner C, Ferreira B, Carvalho L, Fonseca B (2018) Discipline matters: Refactoring of preprocessor directives in the #ifdef hell. IEEE Trans Softw Eng 44(5):453–469

    Article  Google Scholar 

  • Mukelabai M, Nešiundefined D, Maro S, Berger T, Steghöfer J-P (2018) Tackling combinatorial explosion: A study of industrial needs and practices for analyzing highly configurable systems. In: 33rd ACM/IEEE International Conference on Automated Software Engineering. ACM, New York, pp 155–166

  • Oliveira R, Cafeo B, Hora A (2019) On the evolution of feature dependencies: An exploratory study of preprocessor-based systems. In: 13th International Workshop on Variability Modelling of Software-Intensive Systems. ACM, New York, pp 1–9

  • Pett T, Krieter S, Runge T, Thüm T, Lochau M, Schaefer I (2021) Stability of Product-Line Sampling in Continuous Integration. In: 15th international Conference on Variability Modelling of Software-Intensive Systems, VaMoS’21. Association for Computing Machinery. https://doi.org/10.1145/3442391.3442410

  • Prado Lima J A, Mendonça W D F, Assunção W K G, Vergilio S R (2021) Supplementary material - cost-effective learning-based strategies for test case prioritization in continuous integration of highly-configurable software. Open Science Framework. https://doi.org/10.17605/OSF.IO/Z3R2E

  • Prado Lima J A, Mendonça WDF, Vergilio S R, Assunção WKG (2020) Learning-based prioritization of test cases in continuous integration of highly-configurable software. In: Proceedings of the 24th ACM Conference on Systems and Software Product Line: Volume A-Volume A, pp 1–11

  • Prado Lima J A, Vergilio S R (2020) A multi-armed bandit approach for test case prioritization in continuous integration environments. IEEE Trans Softw Eng:12. https://doi.org/10.1109/TSE.2020.2992428

  • Prado Lima J A, Vergilio S R (2020) Multi-armed bandit test case prioritization in continuous integration environments: A trade-off analysis. In: 5th Brazilian Symposium on Systematic and Automated Software Testing. SAST’20. ACM

  • Prado Lima J A, Vergilio S R (2020) Test case prioritization in continuous integration environments: A systematic mapping study. Inf Softw Technol 121:106268. https://doi.org/10.1016/j.infsof.2020.106268

    Article  Google Scholar 

  • Qu X, Cohen M B, Woolf K M (2007) Combinatorial interaction regression testing: A study of test case generation and prioritization. In: IEEE International Conference on Software Maintenance. IEEE, pp 255–264

  • Remmel H, Paech B, Bastian P, Engwer C (2011) System testing a scientific framework using a regression-test environment. Comput Sci Eng 14(2):38–45

    Article  Google Scholar 

  • Remmel H, Paech B, Engwer C, Bastian P (2013) Design and rationale of a quality assurance process for a scientific framework. In: 2013 5th International Workshop on Software Engineering for Computational Science and Engineering (SE-CSE), IEEE, pp 58–67

  • Robbins H (1985) Some aspects of the sequential design of experiments, Springer

  • Rothermel G (2018) Improving regression testing in continuous integration development environments (keynote). In: 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation, A-TEST 2018. ACM, New York, p 1

  • Rothermel G, Untch R H, Chu C, Harrold M J (1999) Test case prioritization: An empirical study. In: IEEE International Conference on Software Maintenance, ICSM ’99. IEEE Computer Society, p 179

  • Runeson P, Engström E (2012) Chapter 7 - regression testing in software product line engineering. In: Hurson A, Memon A (eds) Advances in Computers. https://doi.org/10.1016/B978-0-12-396535-6.00007-7, vol 86. Elsevier, pp 223–263

  • Shahin M, Babar M A, Zhu L (2017) Continuous integration, delivery and deployment: A systematic review on approaches, tools, challenges and practices. IEEE Access 5:3909–3943

    Article  Google Scholar 

  • Spieker H, Gotlieb A, Marijan D, Mossige M (2017) Reinforcement Learning for Automatic Test Case Prioritization and Selection in Continuous Integration. In: 26th ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2017. ACM, New York, pp 12–22

  • Vargha A, Delaney H D (2000) A critique and improvement of the cl common language effect size statistics of mcgraw and wong. J Educ Behav Stat 25 (2):101–132

    Google Scholar 

  • Črepinšek M, Liu S-H, Mernik M (2013) Exploration and exploitation in evolutionary algorithms: A survey. ACM Comput Surv 45(3). https://doi.org/10.1145/2480741.2480752

  • von Rhein A, Grebhahn A, Apel S, Siegmund N, Beyer D, Berger T (2015) Presence-condition simplification in highly configurable systems. In: 37th International Conference on Software Engineering - Volume 1, ICSE 2015. IEEE, New York, pp 178–188

  • Wang S, Ali S, Gotlieb A (2015) Cost-effective test suite minimization in product lines using search techniques. J Syst Softw 103:370–391. https://doi.org/10.1016/j.jss.2014.08.024

  • Wang S, Ali S, Gotlieb A, Liaaen M (2016) A systematic test case selection methodology for product lines: results and insights from an industrial case study. Empir Softw Eng 21:1586–1622

    Article  Google Scholar 

  • Wang T, Yu T (2018) A study of regression test selection in continuous integration environments. In: 2018 IEEE 29th International Symposium on Software Reliability Engineering (ISSRE), pp 135–143

  • Wohlin C, Runeson P, Höst M, Ohlsson MC, Regnell B, Wesslén A (2000) Experimentation in Software Engineering: An Introduction. Kluwer Academic Publishers, USA. https://doi.org/10.1007/978-1-4615-4625-2

  • Xu Z, Cohen M.B, Motycka W, Rothermel G (2013) Continuous test suite augmentation in software product lines. In: 17th International Software Product Line Conference, SPLC ’13. Association for Computing Machinery, New York, pp 52–61. https://doi.org/10.1145/2491627.2491650

  • Yoo S, Harman M (2012) Regression testing minimization, selection and prioritization: A survey. Softw Test Verif Reliab 22(2):67–120. https://doi.org/10.1002/stvr.430

  • Zhou Z Q, Liu C, Chen T Y, Tse T H, Susilo W (2021) Beating random test case prioritization. IEEE Trans Reliab 70(2):654–675. https://doi.org/10.1109/TR.2020.2979815

    Article  Google Scholar 

Download references

Acknowledgements

This research was partially funded by the Brazilian research agencies: CNPq (grants 408356/2018-9 and 305968/2018-1), Fundação Araucária – FAPPR (grant no. 51435), FAPERJ PDR-10 program (grant no. 202073/2020), and CAPES.

Author information

Authors and Affiliations

  1. DINF, Federal University of Paraná (UFPR), Curitiba, Brazil

    Jackson A. Prado Lima, Willian D. F. Mendonça & Silvia R. Vergilio

  2. Pontifical Catholic University of Rio de Janeiro (PUC-Rio), Rio de Janeiro, Brazil

    Wesley K. G. Assunção

Authors
  1. Jackson A. Prado Lima
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Willian D. F. Mendonça
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Silvia R. Vergilio
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Wesley K. G. Assunção
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Jackson A. Prado Lima.

Ethics declarations

Conflict of Interests

The authors declare that they have no conflict of interest.

Additional information

Communicated by: Philippe Collet, Sarah Nadi, and Christoph Seidl

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article belongs to the Topical Collection: Software Product Lines and Variability-rich Systems (SPLC)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Prado Lima, J.A., Mendonça, W.D.F., Vergilio, S.R. et al. Cost-effective learning-based strategies for test case prioritization in continuous integration of highly-configurable software. Empir Software Eng 27, 133 (2022). https://doi.org/10.1007/s10664-021-10093-3

Download citation

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10664-021-10093-3

Keywords