{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T01:32:46Z","timestamp":1762047166839,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":50,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030995263"},{"type":"electronic","value":"9783030995270"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T00:00:00Z","timestamp":1648598400000},"content-version":"vor","delay-in-days":88,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Regression testing is an important activity to check software changes by running the tests in a test suite to inform the developers whether the changes lead to test failures. Regression test prioritization (RTP) aims to inform the developers faster by ordering the test suite so that tests likely to fail are run earlier. Many RTP techniques have been proposed and are often compared with the random RTP baseline by sampling some of the <jats:italic>n<\/jats:italic>! different test-suite orders for a test suite with <jats:italic>n<\/jats:italic> tests. However, there is no theoretical analysis of random RTP. We present such an analysis, deriving probability mass functions and expected values for metrics and scenarios commonly used in RTP research. Using our analysis, we revisit some of the most highly cited RTP papers and find that some presented results may be due to insufficient sampling. Future RTP research can leverage our analysis and need not use random sampling but can use our simple formulas or algorithms to more precisely compare with random RTP.<\/jats:p>","DOI":"10.1007\/978-3-030-99527-0_12","type":"book-chapter","created":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T10:37:21Z","timestamp":1648550241000},"page":"217-235","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Theoretical Analysis of Random Regression Test Prioritization"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6669-6520","authenticated-orcid":false,"given":"Pu","family":"Yi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8480-8167","authenticated-orcid":false,"given":"Hao","family":"Wang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6731-216X","authenticated-orcid":false,"given":"Tao","family":"Xie","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5023-3492","authenticated-orcid":false,"given":"Darko","family":"Marinov","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2243-1218","authenticated-orcid":false,"given":"Wing","family":"Lam","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,30]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"B\u00f6hme, M., Man\u00e8s, V.J.M., Cha, S.K.: Boosting fuzzer efficiency: An information theoretic perspective. In: ESEC\/FSE (2020)","DOI":"10.1145\/3368089.3409748"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"B\u00f6hme, M., Paul, S.: On the efficiency of automated testing. In: FSE (2014)","DOI":"10.1145\/2635868.2635923"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"B\u00f6hme, M., Paul, S.: A probabilistic analysis of the efficiency of automated software testing. TSE (2016)","DOI":"10.1109\/TSE.2015.2487274"},{"key":"12_CR4","unstructured":"Brigham, E.O.: The fast Fourier transform and its applications. Prentice-Hall, Inc. (1988)"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Busjaeger, B., Xie, T.: Learning for test prioritization: An industrial case study. In: FSE (2016)","DOI":"10.1145\/2950290.2983954"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Cheng, R., Zhang, L., Marinov, D., Xu, T.: Test-case prioritization for configuration testing. In: ISSTA (2021)","DOI":"10.1145\/3460319.3464810"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Claessen, K., Hughes, J.: QuickCheck: A lightweight tool for random testing of Haskell programs. In: ICFP (2000)","DOI":"10.1145\/351240.351266"},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Csallner, C., Smaragdakis, Y., Xie, T.: DSD-Crasher: A hybrid analysis tool for bug finding. TOSEM (2008)","DOI":"10.1145\/1348250.1348254"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Duran, J.W., Ntafos, S.C.: An evaluation of random testing. TSE (1984)","DOI":"10.1109\/TSE.1984.5010257"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Elbaum, S., Kallakuri, P., Malishevsky, A., Rothermel, G., Kanduri, S.: Understanding the effects of changes on the cost-effectiveness of regression testing techniques. STVR (2003)","DOI":"10.1002\/stvr.263"},{"key":"12_CR11","unstructured":"Elbaum, S., Malishevsky, A., Rothermel, G.: Incorporating varying test costs and fault severities into test case prioritization. In: ICSE (2001)"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Elbaum, S., Malishevsky, A.G., Rothermel, G.: Prioritizing test cases for regression testing. In: ISSTA (2000)","DOI":"10.1145\/347324.348910"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Elbaum, S., Malishevsky, A.G., Rothermel, G.: Test case prioritization: A family of empirical studies. TSE (2002)","DOI":"10.1109\/32.988497"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Elbaum, S., Rothermel, G., Penix, J.: Techniques for improving regression testing in continuous integration development environments. In: FSE (2014)","DOI":"10.1145\/2635868.2635910"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Elsner, D., Hauer, F., Pretschner, A., Reimer, S.: Empirically evaluating readily available information for regression test optimization in continuous integration. In: ISSTA (2021)","DOI":"10.1145\/3460319.3464834"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Endres, D.M., Schindelin, J.E.: A new metric for probability distributions. Transactions on Information Theory (2003)","DOI":"10.1109\/TIT.2003.813506"},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Fraser, G., Zeller, A.: Generating parameterized unit tests. In: ISSTA (2011)","DOI":"10.1145\/2001420.2001464"},{"key":"12_CR18","unstructured":"Hamlet, R.: Random testing. In: Encyclopedia of Software Engineering (1994)"},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"Jiang, B., Zhang, Z., Chan, W.K., Tse, T.H.: Adaptive random test case prioritization. In: ASE (2009)","DOI":"10.1109\/ASE.2009.77"},{"key":"12_CR20","unstructured":"JUnit (2022), https:\/\/junit.org"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Kim, J.M., Porter, A.: A history-based test prioritization technique for regression testing in resource constrained environments. In: ICSE (2002)","DOI":"10.1145\/581339.581357"},{"key":"12_CR22","doi-asserted-by":"crossref","unstructured":"Kim, J.M., Porter, A., Rothermel, G.: An empirical study of regression test application frequency. STVR (2005)","DOI":"10.1002\/stvr.326"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Liang, J., Elbaum, S., Rothermel, G.: Redefining prioritization: Continuous prioritization for continuous integration. In: ICSE (2018)","DOI":"10.1145\/3180155.3180213"},{"key":"12_CR24","doi-asserted-by":"crossref","unstructured":"Lu, Y., Lou, Y., Cheng, S., Zhang, L., Hao, D., Zhou, Y., Zhang, L.: How does regression test prioritization perform in real-world software evolution? In: ICSE (2016)","DOI":"10.1145\/2884781.2884874"},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Luo, Q., Hariri, F., Eloussi, L., Marinov, D.: An empirical analysis of flaky tests. In: FSE (2014)","DOI":"10.1145\/2635868.2635920"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Majumdar, R., Niksic, F.: Why is random testing effective for partition tolerance bugs? In: POPL (2017)","DOI":"10.1145\/3158134"},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Mattis, T., Rein, P., D\u00fcrsch, F., Hirschfeld, R.: RTPTorrent: An open-source dataset for evaluating regression test prioritization. In: MSR (2020)","DOI":"10.1145\/3379597.3387458"},{"key":"12_CR28","unstructured":"Maven (2022), https:\/\/maven.apache.org"},{"key":"12_CR29","unstructured":"Mirarab, S., Tahvildari, L.: A prioritization approach for software test cases based on Bayesian networks. In: FASE (2007)"},{"key":"12_CR30","doi-asserted-by":"crossref","unstructured":"Mondal, S., Nasre, R.: Summary of Hansie: Hybrid and consensus regression test prioritization. In: ICST (2021)","DOI":"10.1109\/ICST49551.2021.00038"},{"key":"12_CR31","doi-asserted-by":"crossref","unstructured":"Ntafos, S.: On random and partition testing. In: ISSTA (1998)","DOI":"10.1145\/271771.271785"},{"key":"12_CR32","doi-asserted-by":"crossref","unstructured":"Ozkan, B.K., Majumdar, R., Oraee, S.: Trace aware random testing for distributed systems. OOPSLA (2019)","DOI":"10.1145\/3360606"},{"key":"12_CR33","doi-asserted-by":"crossref","unstructured":"Pacheco, C., Lahiri, S.K., Ernst, M.D., Ball, T.: Feedback-directed random test generation. In: ICSE (2007)","DOI":"10.1109\/ICSE.2007.37"},{"key":"12_CR34","doi-asserted-by":"crossref","unstructured":"Peng, Q., Shi, A., Zhang, L.: Empirically revisiting and enhancing IR-based test-case prioritization. In: ISSTA (2020)","DOI":"10.1145\/3395363.3397383"},{"key":"12_CR35","unstructured":"pytest (2022), https:\/\/docs.pytest.org"},{"key":"12_CR36","doi-asserted-by":"crossref","unstructured":"Rothermel, G., Untch, R., Chu, C., Harrold, M.: Test case prioritization: An empirical study. In: ICSM (1999)","DOI":"10.1109\/ICSM.1999.792604"},{"key":"12_CR37","doi-asserted-by":"crossref","unstructured":"Rothermel, G., Elbaum, S., Malishevsky, A., Kallakuri, P., Davia, B.: The impact of test suite granularity on the cost-effectiveness of regression testing. In: ICSE (2002)","DOI":"10.1145\/581356.581358"},{"key":"12_CR38","doi-asserted-by":"crossref","unstructured":"Rothermel, G., Untch, R.H., Chu, C., Harrold, M.J.: Prioritizing test cases for regression testing. TSE (2001)","DOI":"10.1109\/32.962562"},{"key":"12_CR39","doi-asserted-by":"crossref","unstructured":"Rummel, M.J., Kapfhammer, G.M., Thall, A.: Towards the prioritization of regression test suites with data flow information. In: SAC (2005)","DOI":"10.1145\/1066677.1067016"},{"key":"12_CR40","doi-asserted-by":"crossref","unstructured":"Saha, R.K., Zhang, L., Khurshid, S., Perry, D.E.: An information retrieval approach for regression test prioritization based on program changes. In: ICSE (2015)","DOI":"10.1109\/ICSE.2015.47"},{"key":"12_CR41","doi-asserted-by":"crossref","unstructured":"Spieker, H., Gotlieb, A., Marijan, D., Mossige, M.: Reinforcement learning for automatic test case prioritization and selection in continuous integration. In: ISSTA (2017)","DOI":"10.1145\/3092703.3092709"},{"key":"12_CR42","doi-asserted-by":"crossref","unstructured":"Srivastava, A., Thiagarajan, J.: Effectively prioritizing tests in development environment. In: ISSTA (2002)","DOI":"10.1145\/566185.566187"},{"key":"12_CR43","doi-asserted-by":"crossref","unstructured":"Stanley, R.P.: Enumerative Combinatorics, Volume 1, 2nd Edition. Cambridge University Press (2011)","DOI":"10.1017\/CBO9781139058520"},{"key":"12_CR44","unstructured":"A Theoretical Analysis of Regression Test Prioritization website (2022), https:\/\/sites.google.com\/view\/theoretical-analysis-of-rtp"},{"key":"12_CR45","doi-asserted-by":"crossref","unstructured":"Wang, Z., Chen, L.: Improved metrics for non-classic test prioritization problems. In: SEKE (2015)","DOI":"10.18293\/SEKE2015-230"},{"key":"12_CR46","doi-asserted-by":"crossref","unstructured":"Wei, A., Yi, P., Xie, T., Marinov, D., Lam, W.: Probabilistic and systematic coverage of consecutive test-method pairs for detecting order-dependent flaky tests. In: TACAS (2021)","DOI":"10.26226\/morressier.604907f41a80aac83ca25cf5"},{"key":"12_CR47","unstructured":"Wong, W., Horgan, J., London, S., Agrawal, H.: A study of effective regression testing in practice. In: ISSRE (1997)"},{"key":"12_CR48","doi-asserted-by":"crossref","unstructured":"Yoo, S., Harman, M.: Regression testing minimization, selection and prioritization: A survey. STVR (2012)","DOI":"10.1002\/stv.430"},{"key":"12_CR49","unstructured":"Zhai, K., Jiang, B., Chan, W.: Prioritizing test cases for regression testing of location-based services: Metrics, techniques, and case study. IEEE TSC (2012)"},{"key":"12_CR50","doi-asserted-by":"crossref","unstructured":"Zhang, S., Saff, D., Bu, Y., Ernst, M.D.: Combined static and dynamic automated test generation. In: ISSTA (2011)","DOI":"10.1145\/2001420.2001463"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-99527-0_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T12:47:39Z","timestamp":1710247659000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-99527-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783030995263","9783030995270"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-99527-0_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"30 March 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TACAS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Munich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 April 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 April 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2022\/tacas","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"159","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"46","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"29% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"16 tool papers of the affiliated competition SV-Comp and 1 paper consisting of the competition report are also included in the proceedings","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}