{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T05:04:57Z","timestamp":1769749497550,"version":"3.49.0"},"publisher-location":"Cham","reference-count":48,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030720155","type":"print"},{"value":"9783030720162","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T00:00:00Z","timestamp":1616198400000},"content-version":"vor","delay-in-days":78,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Software developers frequently check their code changes by running a <jats:italic>set<\/jats:italic> of tests against their code. Tests that can nondeterministically pass or fail when run on the same code version are called <jats:italic>flaky tests<\/jats:italic>. These tests are a major problem because they can mislead developers to debug their recent code changes when the failures are unrelated to these changes. One prominent category of flaky tests is order-dependent (OD) tests, which can deterministically pass or fail depending on the <jats:italic>order<\/jats:italic> in which the set of tests are run. By detecting OD tests in advance, developers can fix these tests before they change their code. Due to the high cost required to explore all possible orders (<jats:italic>n<\/jats:italic>! permutations for <jats:italic>n<\/jats:italic> tests), prior work has developed tools that randomize orders to detect OD tests. Experiments have shown that randomization can detect many OD tests, and that most OD tests depend on just one other test to fail. However, there was no analysis of the probability that randomized orders detect OD tests. In this paper, we present the first such analysis and also present a simple change for sampling random test orders to increase the probability. We finally present a novel algorithm to systematically explore all consecutive pairs of tests, guaranteeing to detect all OD tests that depend on one other test, while running substantially fewer orders and tests than simply running all test pairs.<\/jats:p>","DOI":"10.1007\/978-3-030-72016-2_15","type":"book-chapter","created":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T22:03:37Z","timestamp":1616191417000},"page":"270-287","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Probabilistic and Systematic Coverage of Consecutive Test-Method Pairs for Detecting Order-Dependent Flaky Tests"],"prefix":"10.1007","author":[{"given":"Anjiang","family":"Wei","sequence":"first","affiliation":[]},{"given":"Pu","family":"Yi","sequence":"additional","affiliation":[]},{"given":"Tao","family":"Xie","sequence":"additional","affiliation":[]},{"given":"Darko","family":"Marinov","sequence":"additional","affiliation":[]},{"given":"Wing","family":"Lam","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,20]]},"reference":[{"key":"15_CR1","unstructured":"Apache Hadoop (2020), https:\/\/github.com\/apache\/hadoop"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Bell, J., Kaiser, G., Melski, E., Dattatreya, M.: Efficient dependency detection for safe Java test acceleration. In: ESEC\/FSE (2015)","DOI":"10.1145\/2786805.2786823"},{"key":"15_CR3","unstructured":"Coefficient of variation (2020), https:\/\/en.wikipedia.org\/wiki\/Coefficient_of_variation"},{"key":"15_CR4","unstructured":"Cucumber (2020), https:\/\/cucumber.io\/docs\/cucumber"},{"key":"15_CR5","unstructured":"Facebook testing and verification request for proposals (2019), https:\/\/research.fb.com\/programs\/research-awards\/proposals\/facebook-testing-and-verification-request-for-proposals-2019"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Gambi, A., Bell, J., Zeller, A.: Practical test dependency detection. In: ICST (2018)","DOI":"10.1109\/ICST.2018.00011"},{"key":"15_CR7","unstructured":"Golomb, S.W., Taylor, H.: Tuscan squares \u2013 A new family of combinatorialdesigns. Ars Combinatoria (1985)"},{"key":"15_CR8","unstructured":"Google: Avoiding flakey tests (2008), http:\/\/googletesting.blogspot.com\/2008\/04\/tott-avoiding-flakey-tests.html"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Gyori, A., Shi, A., Hariri, F., Marinov, D.: Reliable testing: Detecting state-polluting tests to prevent test dependency. In: ISSTA (2015)","DOI":"10.1145\/2771783.2771793"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Harman, M., O\u2019Hearn, P.: From start-ups to scale-ups: Opportunities and open problems for static and dynamic program analysis. In: SCAM (2018)","DOI":"10.1109\/SCAM.2018.00009"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Herzig, K., Greiler, M., Czerwonka, J., Murphy, B.: The art of testing less without sacrificing quality. In: ICSE (2015)","DOI":"10.1109\/ICSE.2015.66"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Herzig, K., Nagappan, N.: Empirically detecting false test alarms using association rules. In: ICSE (2015)","DOI":"10.1109\/ICSE.2015.133"},{"key":"15_CR13","unstructured":"Houston, R.: Tackling the minimal superpermutation problem (2014), arXiv"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Huo, C., Clause, J.: Improving oracle quality by detecting brittle assertions and unused inputs in tests. In: FSE (2014)","DOI":"10.1145\/2635868.2635917"},{"key":"15_CR15","unstructured":"iDFlakies: Flaky test dataset (2020), https:\/\/sites.google.com\/view\/flakytestdataset"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Jiang, H., Li, X., Yang, Z., Xuan, J.: What causes my test alarm? Automatic cause analysis for test alarms in system and integration testing. In: ICSE (2017)","DOI":"10.1109\/ICSE.2017.71"},{"key":"15_CR17","unstructured":"JUnit (2020), https:\/\/junit.org"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Kowalczyk, E., Nair, K., Gao, Z., Silberstein, L., Long, T., Memon, A.: Modeling and ranking flaky tests at Apple. In: ICSE SEIP (2020)","DOI":"10.1145\/3377813.3381370"},{"key":"15_CR19","unstructured":"Lam, W.: Illinois Dataset of Flaky Tests (IDoFT) (2020), http:\/\/mir.cs.illinois.edu\/flakytests"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"Lam, W., Godefroid, P., Nath, S., Santhiar, A., Thummalapenta, S.: Root causing flaky tests in a large-scale industrial setting. In: ISSTA (2019)","DOI":"10.1145\/3293882.3330570"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"Lam, W., Mu\u015flu, K., Sajnani, H., Thummalapenta, S.: A study on the lifecycle of flaky tests. In: ICSE (2020)","DOI":"10.1145\/3377811.3381749"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Lam, W., Oei, R., Shi, A., Marinov, D., Xie, T.: iDFlakies: A framework for detecting and partially classifying flaky tests. In: ICST (2019)","DOI":"10.1109\/ICST.2019.00038"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"Lam, W., Shi, A., Oei, R., Zhang, S., Ernst, M.D., Xie, T.: Dependent-test-aware regression testing techniques. In: ISSTA (2020)","DOI":"10.1145\/3395363.3397364"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"Lam, W., Winter, S., Astorga, A., Stodden, V., Marinov, D.: Understanding reproducibility and characteristics of flaky tests through test reruns in Java projects. In: ISSRE (2020)","DOI":"10.1109\/ISSRE5003.2020.00045"},{"key":"15_CR25","doi-asserted-by":"crossref","unstructured":"Lam, W., Winter, S., Wei, A., Xie, T., Marinov, D., Bell, J.: A large-scale longitudinal study of flaky tests. In: OOPSLA (2020)","DOI":"10.1145\/3428270"},{"key":"15_CR26","unstructured":"Lucas, E.: R\u00e9cr\u00e9ations math\u00e9matiques (1894)"},{"key":"15_CR27","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":"15_CR28","unstructured":"Maven (2020), https:\/\/maven.apache.org"},{"key":"15_CR29","unstructured":"Maven Surefire plugin (2020), https:\/\/maven.apache.org\/surefire\/maven-surefire-plugin"},{"key":"15_CR30","doi-asserted-by":"crossref","unstructured":"Memon, A., Gao, Z., Nguyen, B., Dhanda, S., Nickell, E., Siemborski, R., Micco, J.: Taming Google-scale continuous testing. In: ICSE SEIP (2017)","DOI":"10.1109\/ICSE-SEIP.2017.16"},{"key":"15_CR31","unstructured":"Micco, J.: The state of continuous integration testing at Google. In: ICST (2017)"},{"key":"15_CR32","doi-asserted-by":"crossref","unstructured":"Mu\u015flu, K., Soran, B., Wuttke, J.: Finding bugs by isolating unit tests. In: ESEC\/FSE (2011)","DOI":"10.1145\/2025113.2025202"},{"key":"15_CR33","doi-asserted-by":"crossref","unstructured":"Nie, C., Leung, H.: A survey of combinatorial testing. ACM Comput. Surv. (2011)","DOI":"10.1145\/1883612.1883618"},{"key":"15_CR34","doi-asserted-by":"crossref","unstructured":"Ollis, M.: Sequenceable groups and related topics. Electronic Journal of Combinatorics (2013)","DOI":"10.37236\/30"},{"key":"15_CR35","unstructured":"pytest (2020), https:\/\/docs.pytest.org"},{"key":"15_CR36","unstructured":"RSpec (2020), https:\/\/rspec.info"},{"key":"15_CR37","doi-asserted-by":"crossref","unstructured":"Shi, A., Lam, W., Oei, R., Xie, T., Marinov, D.: iFixFlakies: A framework for automatically fixing order-dependent flaky tests. In: ESEC\/FSE (2019)","DOI":"10.1145\/3338906.3338925"},{"key":"15_CR38","unstructured":"Spock (2019), http:\/\/docs.spockframework.org"},{"key":"15_CR39","unstructured":"StackExchange \u2013 Covering pairs with permutations (2020),https:\/\/math.stackexchange.com\/questions\/1769877\/covering-pairs-with-permutations"},{"key":"15_CR40","unstructured":"Test Verification (2019), https:\/\/developer.mozilla.org\/en-US\/docs\/Mozilla\/QA\/Test_Verification"},{"key":"15_CR41","unstructured":"TestNG (2019), https:\/\/testng.org\/doc\/documentation-main.html"},{"key":"15_CR42","doi-asserted-by":"crossref","unstructured":"Tillson, T.W.: A Hamiltonian decomposition of $$K_{2m}^{*}$$, $$2m\\ge 8$$. Journal of Combinatorial Theory, Series B (1980)","DOI":"10.1016\/0095-8956(80)90044-1"},{"key":"15_CR43","unstructured":"TotT: Avoiding flakey tests (2019), http:\/\/goo.gl\/vHE47r"},{"key":"15_CR44","unstructured":"TuscanSquare (2020), https:\/\/github.com\/Anjiang-Wei\/TuscanSquare"},{"key":"15_CR45","doi-asserted-by":"publisher","DOI":"10.1002\/stv.430","volume-title":"Regression testing minimization, selection and prioritization: A survey","author":"S Yoo","year":"2012","unstructured":"Yoo, S., Harman, M.: Regression testing minimization, selection and prioritization: A survey. Software Testing, Verification & Reliability (2012)"},{"key":"15_CR46","doi-asserted-by":"crossref","unstructured":"Zeller, A., Hildebrandt, R.: Simplifying and isolating failure-inducing input. TSE (2002)","DOI":"10.1109\/32.988498"},{"key":"15_CR47","doi-asserted-by":"crossref","unstructured":"Zhang, S., Jalali, D., Wuttke, J., Mu\u015flu, K., Lam, W., Ernst, M.D., Notkin, D.: Empirically revisiting the test independence assumption. In: ISSTA (2014)","DOI":"10.1145\/2610384.2610404"},{"key":"15_CR48","doi-asserted-by":"crossref","unstructured":"Ziftci, C., Reardon, J.: Who broke the build?: Automatically identifying changes that induce test failures in continuous integration at Google scale. In: ICSE (2017)","DOI":"10.1109\/ICSE-SEIP.2017.13"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-72016-2_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T00:08:43Z","timestamp":1616371723000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-72016-2_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030720155","9783030720162"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-72016-2_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 March 2021","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":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 March 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 April 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2021\/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":"141","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":"41","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":"21","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":"12","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":"The conference changed to an online format due to the COVID-19 pandemic","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)"}}]}}