{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T17:19:08Z","timestamp":1791393548486,"version":"4.3.3"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"FSE","license":[{"start":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:00:00Z","timestamp":1750291200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["214989"],"award-info":[{"award-number":["214989"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Softw. Eng."],"published-print":{"date-parts":[[2025,6,19]]},"abstract":"<jats:p>Adaptive Random Testing (ART) has faced criticism, particularly for its computational inefficiency, as highlighted by Arcuri and Briand. Their analysis clarified how ART requires a quadratic number of distance computations as the number of test executions increases, which limits its scalability in scenarios requiring extensive testing to uncover faults. Simulation results support this, showing that the computational overhead of these distance calculations often outweighs ART\u2019s benefits. While various ART variants have attempted to reduce these costs, they frequently do so at the expense of fault detection, lack complexity guarantees, or are restricted to specific input types, such as numerical or discrete data.<\/jats:p>\n                  <jats:p>\n                    In this paper, we introduce a novel framework for adaptive random testing that replaces pairwise distance computations with a compact aggregation of past executions, such as counting the\n                    <jats:sc>q-grams<\/jats:sc>\n                    observed in previous runs. Test case selection then leverages this aggregated data to measure diversity (e.g., entropy of\n                    <jats:sc>q-grams<\/jats:sc>\n                    ), allowing us to reduce the computational complexity from quadratic to linear.\n                  <\/jats:p>\n                  <jats:p>\n                    Experiments with a benchmark of six web applications, show that ART with\n                    <jats:sc>q-grams<\/jats:sc>\n                    covers, on average, 4\u00d7 more unique targets than random testing, and 3.5\u00d7 more than ART using traditional distance-based methods.\n                  <\/jats:p>","DOI":"10.1145\/3715740","type":"journal-article","created":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T11:16:02Z","timestamp":1750331762000},"page":"533-553","source":"Crossref","is-referenced-by-count":1,"title":["Adaptive Random Testing with Q-grams: The Illusion Comes True"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7825-3409","authenticated-orcid":false,"given":"Matteo","family":"Biagiola","sequence":"first","affiliation":[{"name":"Universit\u00e0 della Svizzera italiana, Software Institute, Lugano, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5179-4205","authenticated-orcid":false,"given":"Robert","family":"Feldt","sequence":"additional","affiliation":[{"name":"Chalmers University of Technology, Gothenburg, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3088-0339","authenticated-orcid":false,"given":"Paolo","family":"Tonella","sequence":"additional","affiliation":[{"name":"Universit\u00e0 della Svizzera italiana, Software Institute, Lugano, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,19]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TR.2019.2907577"},{"key":"e_1_3_1_3_2","first-page":"265","volume-title":"Proceedings of the 20th International Symposium on Software Testing and Analysis ISSTA","author":"Arcuri Andrea","year":"2011","unstructured":"Andrea Arcuri and Lionel C. Briand. 2011. Adaptive random testing: an illusion of effectiveness?. In Proceedings of the 20th International Symposium on Software Testing and Analysis ISSTA, Toronto, ON, Canada, July 17-21, 2011. 265\u2013275."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/STVR.1486"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2016.2547380"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66299-2_2"},{"key":"e_1_3_1_8_2","first-page":"142","volume-title":"Proceedings of the ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering","author":"Biagiola Matteo","year":"2019","unstructured":"Matteo Biagiola, Andrea Stocco, Filippo Ricca, and Paolo Tonella. 2019. Diversity-based web test generation. In Proceedings of the ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC\/SIGSOFT FSE, Tallinn, Estonia. 142\u2013153."},{"key":"e_1_3_1_9_2","volume-title":"Classification and Regression Trees","author":"Breiman Leo","year":"1984","unstructured":"Leo Breiman, J. H. Friedman, Richard A. Olshen, and C. J. Stone. 1984. Classification and Regression Trees. Wadsworth."},{"key":"e_1_3_1_10_2","first-page":"485","volume-title":"30th Annual International Computer Software and Applications Conference (COMPSAC\u201906)","author":"Chan Kwok Ping","year":"2006","unstructured":"Kwok Ping Chan, TY Chen, and Dave Towey. 2006. Forgetting test cases. In 30th Annual International Computer Software and Applications Conference (COMPSAC\u201906), Vol. 1. IEEE, 485\u2013494."},{"key":"e_1_3_1_11_2","first-page":"320","volume-title":"Advances in Computer Science - ASIAN 2004","author":"Yueh Chen Tsong","year":"2004","unstructured":"Tsong Yueh Chen, Hing Leung, and I. K. Mak. 2004. Adaptive Random Testing. In Advances in Computer Science - ASIAN 2004, Chiang Mai, Thailand, December 8-10, 2004. 320\u2013329."},{"key":"e_1_3_1_12_2","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1109\/QSIC.2004.1357947","volume-title":"Fourth International Conference on Quality Software, 2004. QSIC 2004. Proceedings","author":"Chen Tsong Yueh","year":"2004","unstructured":"Tsong Yueh Chen, R Merkel, PK Wong, and G Eddy. 2004. Adaptive random testing through dynamic partitioning. In Fourth International Conference on Quality Software, 2004. QSIC 2004. Proceedings. IEEE, 79\u201386."},{"key":"e_1_3_1_13_2","unstructured":"Software Freedom Conservancy. 2024. Page object models. https:\/\/www.selenium.dev\/documentation\/test_practices\/encouraged\/page_object_models\/. Accessed: 2024-09-01."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.7717\/peerj-cs.1625"},{"key":"e_1_3_1_15_2","doi-asserted-by":"crossref","unstructured":"Islam Elgendy Robert Hierons and Phil McMinn. 2024. Evaluating String Distance Metrics for Reducing Automatically Generated Test Suites. In Proceedings of the 5th ACM\/IEEE International Conference on Automation of Software Test (AST 2024). 171\u2013181.","DOI":"10.1145\/3644032.3644455"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1002\/stvr.1914"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2016.33"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSTW.2008.36"},{"key":"e_1_3_1_19_2","unstructured":"Martin Fowler. 2013. PageObject. http:\/\/martinfowler.com\/bliki\/PageObject.html. Accessed: 2024-09-01."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2017.8115667"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICST46399.2020.00035"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSTW.2013.19"},{"issue":"5","key":"e_1_3_1_23_2","doi-asserted-by":"crossref","first-page":"e1827","DOI":"10.1002\/stvr.1827","article-title":"Fostering the diversity of exploratory testing in web applications","volume":"32","author":"Leveau Julien","year":"2022","unstructured":"Julien Leveau, Xavier Blanc, Laurent R\u00e9veill\u00e8re, Jean-R\u00e9my Falleri, and Romain Rouvoy. 2022. Fostering the diversity of exploratory testing in web applications. Software Testing, Verification and Reliability 32, 5 (2022), e1827.","journal-title":"Software Testing, Verification and Reliability"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TR.2019.2892230"},{"key":"e_1_3_1_25_2","first-page":"547","volume-title":"Proceedings of the fourth Berkeley symposium on mathematical statistics and probability, volume 1: contributions to the theory of statistics","author":"R\u00e9nyi Alfr\u00e9d","year":"1961","unstructured":"Alfr\u00e9d R\u00e9nyi. 1961. On measures of entropy and information. In Proceedings of the fourth Berkeley symposium on mathematical statistics and probability, volume 1: contributions to the theory of statistics, Vol. 4. University of California Press, 547\u2013562."},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCC.2004.843247"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.53"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2012.18"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.3390\/e12071765"},{"issue":"1","key":"e_1_3_1_31_2","first-page":"19","article-title":"Measuring the diversity of a test set with distance entropy","volume":"65","author":"Shi Qingkai","year":"2015","unstructured":"Qingkai Shi, Zhenyu Chen, Chunrong Fang, Yang Feng, and Baowen Xu. 2015. Measuring the diversity of a test set with distance entropy. IEEE transactions on reliability 65, 1 (2015), 19\u201327.","journal-title":"IEEE transactions on reliability"},{"key":"e_1_3_1_32_2","unstructured":"testingautomated usi. 2024. https:\/\/github.com\/testingautomated-usi\/adaptive-tg-qgrams"},{"issue":"2","key":"e_1_3_1_33_2","first-page":"101","article-title":"A Critique and Improvement of the \u201cCL\u201d Common Language Effect Size Statistics of McGraw and Wong","volume":"25","author":"Vargha Andr\u00e1s","year":"2000","unstructured":"Andr\u00e1s Vargha and Harold D. Delaney. 2000. A Critique and Improvement of the \u201cCL\u201d Common Language Effect Size Statistics of McGraw and Wong. Journal of Educational and Behavioral Statistics 25, 2 (2000), 101\u2013132. http:\/\/www.jstor.org\/stable\/1165329","journal-title":"Journal of Educational and Behavioral Statistics"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.2307\/3001968"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2022.3171295"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/QRS.2016.49"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE43902.2021.00048"}],"container-title":["Proceedings of the ACM on Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3715740","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T11:06:04Z","timestamp":1787483164000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3715740"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,19]]},"references-count":36,"journal-issue":{"issue":"FSE","published-print":{"date-parts":[[2025,6,19]]}},"alternative-id":["10.1145\/3715740"],"URL":"https:\/\/doi.org\/10.1145\/3715740","relation":{},"ISSN":["2994-970X"],"issn-type":[{"value":"2994-970X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,19]]}}}