{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T12:34:00Z","timestamp":1742387640277},"reference-count":51,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2010,10,28]],"date-time":"2010-10-28T00:00:00Z","timestamp":1288224000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[2011,4,10]]},"abstract":"Abstract<\/jats:title>Grammars are traditionally used to recognize or parse sentences in a language, but they can also be used to generate sentences. In grammar\u2010based test generation (GBTG), context\u2010free grammars are used to generate sentences that are interpreted as test cases. A generator reads a grammar G<\/jats:italic> and generates L<\/jats:italic>(G<\/jats:italic>), the language accepted by the grammar. Often L<\/jats:italic>(G<\/jats:italic>) is so large that it is not practical to execute all of the generated cases. Therefore, GBTG tools support \u2018tags\u2019: extra\u2010grammatical annotations which restrict the generation. Since its introduction in the early 1970s, GBTG has become well established: proven on industrial projects and widely published in academic venues. Despite the demonstrated effectiveness, the tool support is uneven; some tools target specific domains, e.g. compiler testing, while others are proprietary. The tools can be difficult to use and the precise meaning of the tags are sometimes unclear. As a result, while many testing practitioners and researchers are aware of GBTG, few have detailed knowledge or experience. We present YouGen, a new GBTG tool supporting many of the tags provided by previous tools. In addition, YouGen incorporates covering\u2010array tags, which support a generalized form of pairwise testing. These tags add considerable power to GBTG tools and have been available only in limited form in previous GBTG tools. We provide semantics for the YouGen tags using parse trees and a new construct, generation trees. We illustrate YouGen with both simple examples and a number of industrial case studies. Copyright \u00a9 2010 John Wiley & Sons, Ltd.<\/jats:p>","DOI":"10.1002\/spe.1017","type":"journal-article","created":{"date-parts":[[2010,10,28]],"date-time":"2010-10-28T22:27:43Z","timestamp":1288304863000},"page":"427-447","source":"Crossref","is-referenced-by-count":16,"title":["Grammar\u2010based test generation with YouGen"],"prefix":"10.1002","volume":"41","author":[{"given":"Daniel Malcolm","family":"Hoffman","sequence":"first","affiliation":[]},{"given":"David","family":"Ly\u2010Gagnon","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Strooper","sequence":"additional","affiliation":[]},{"given":"Hong\u2010Yi","family":"Wang","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2010,10,28]]},"reference":[{"key":"e_1_2_9_2_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.223.0229"},{"key":"e_1_2_9_3_2","unstructured":"HoffmanD KubeN.Automated testing of SCADA protocols. Proceedings of SCADA Security Scientific Symposium Miami Beach FL U.S.A. 2007;4.1\u20134.13."},{"key":"e_1_2_9_4_2","unstructured":"ZaytsevV.Combinatorial test set generation: Concepts implementation case study. Master's Thesis Universiteit Twente June2004;7\u201313 26\u201344."},{"key":"e_1_2_9_5_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.94.0242"},{"key":"e_1_2_9_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/331960.331965"},{"key":"e_1_2_9_7_2","volume-title":"A Functional Method for Assessing Protocol Implementation Security","author":"Kaksonen R","year":"2001"},{"key":"e_1_2_9_8_2","first-page":"43","volume-title":"Proceedings of TAIC\u2010PART 2009","author":"Hoffman D","year":"2009"},{"key":"e_1_2_9_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.979992"},{"key":"e_1_2_9_10_2","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J","year":"2001"},{"key":"e_1_2_9_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.10059"},{"key":"e_1_2_9_12_2","first-page":"121","article-title":"Combinatorial aspects of covering arrays","volume":"58","author":"Colbourn C","year":"2004","journal-title":"Le Matematiche"},{"key":"e_1_2_9_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.07.050"},{"key":"e_1_2_9_14_2","volume-title":"Practical Model\u2010Based Testing: A Tools Approach","author":"Utting M","year":"2007"},{"key":"e_1_2_9_15_2","unstructured":"AugerR SimaC(eds.). Zero Day Subscriptions: Using RSS and Atom Feeds As Attack Delivery Systems. SPI Dynamics 2006. Available at:http:\/\/www.cgisecurity.com\/papers\/RSS\u2010Security.ppt[21 September2010]."},{"key":"e_1_2_9_16_2","unstructured":"Universal feed parser 2002. Available at:http:\/\/www.feedparser.org\/[21 September2010]."},{"key":"e_1_2_9_17_2","first-page":"105","volume-title":"Proceedings of TAIC\u2010PART 2009","author":"Hoffman D","year":"2009"},{"key":"e_1_2_9_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2010.07.048"},{"key":"e_1_2_9_19_2","unstructured":"The atom syndication format 2005. Available at:http:\/\/www.ietf.org\/rfc\/rfc4287.txt[21 September2010]."},{"key":"e_1_2_9_20_2","unstructured":"RDF site summary (RSS) 1.0 2000. Available at:http:\/\/web.resource.org\/rss\/1.0\/spec[21 September2010]."},{"key":"e_1_2_9_21_2","unstructured":"RSS 2.0 specification 2003. Available at:http:\/\/cyber.law.harvard.edu\/rss\/rss.html[21 September2010]."},{"key":"e_1_2_9_22_2","unstructured":"XML path language (xpath). Available at:http:\/\/www.w3.org\/TR\/xpath[21 September2010]."},{"key":"e_1_2_9_23_2","unstructured":"MacNamaraC.Grammar\u2010based testing of XML and XPath applications. BE Thesis The University of Queensland 2009; 78pp."},{"key":"e_1_2_9_24_2","unstructured":"XimpleWare. VTD\u2010XML: The future of XML processing. Available at:http:\/\/vtd\u2010xml.sourceforge.net[21 September2010]."},{"key":"e_1_2_9_25_2","unstructured":"XMLSoft. The XML C parser and toolkit of Gnome: Introduction. Available at:http:\/\/www.xmlsoft.org\/intro.html[21 September2010]."},{"key":"e_1_2_9_26_2","unstructured":"Xquery 1.0: An XML query language. Available at:http:\/\/www.w3.org\/TR\/xquery\/[21 September2010]."},{"key":"e_1_2_9_27_2","unstructured":"SchmidtAR WaasF KerstenML FlorescuD ManolescuI CareyMJ BusseR.The XML benchmark project. Technical Report Amsterdam the Netherlands 2001;6\u201312."},{"key":"e_1_2_9_28_2","unstructured":"WangH.Grammar\u2010based test generation for XPath queries. MSc Report University of Victoria 2008;25\u201334."},{"key":"e_1_2_9_29_2","unstructured":"PyXML. Available at:http:\/\/sourceforge.net\/projects\/pyxml\/[21 September2010]."},{"key":"e_1_2_9_30_2","unstructured":"SAXON: The XSLT and XQuery processor. Available at:http:\/\/saxon.sourceforge.net\/[21 September2010]."},{"key":"e_1_2_9_31_2","volume-title":"Computer Networks","author":"Tanenbaum AS","year":"2003"},{"key":"e_1_2_9_32_2","unstructured":"SobotkiewiczL.A new tool for grammar\u2010based test case generation. Master's Thesis University of Victoria December2008;45\u201358."},{"key":"e_1_2_9_33_2","volume-title":"The Linux Networking Architecture","author":"Wehrle K","year":"2005"},{"key":"e_1_2_9_34_2","volume-title":"Red Hat Linux Firewalls","author":"McCarty B","year":"2003"},{"key":"e_1_2_9_35_2","doi-asserted-by":"publisher","DOI":"10.1002\/stvr.319"},{"key":"e_1_2_9_36_2","doi-asserted-by":"publisher","DOI":"10.1002\/jcd.20067"},{"key":"e_1_2_9_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-006-0020-8"},{"key":"e_1_2_9_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.605761"},{"key":"e_1_2_9_39_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.113.022"},{"key":"e_1_2_9_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2004.24"},{"key":"e_1_2_9_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2006.8"},{"key":"e_1_2_9_42_2","doi-asserted-by":"crossref","unstructured":"CohenM ColbournC GibbonsP MugridgeW.Constructing test suites for interaction testing. Proceedings of the International Conference on Software Engineering Portland OR U.S.A. 2003;38\u201344.","DOI":"10.1109\/ICSE.2003.1201186"},{"key":"e_1_2_9_43_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380190106"},{"key":"e_1_2_9_44_2","doi-asserted-by":"publisher","DOI":"10.1002\/stvr.4370040204"},{"key":"e_1_2_9_45_2","doi-asserted-by":"crossref","unstructured":"HoffmanD YooK.Blowtorch: A framework for firewall test automation. Proceedings of the 20th IEEE\/ACM International Conference on Automated Software Engineering Long Beach CA U.S.A. 2005;96\u2013103.","DOI":"10.1145\/1101908.1101925"},{"key":"e_1_2_9_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/54.7959"},{"key":"e_1_2_9_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/11754008_2"},{"key":"e_1_2_9_48_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380130911"},{"key":"e_1_2_9_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/953428.953435"},{"key":"e_1_2_9_50_2","first-page":"170","volume-title":"Proceedings of the Fifth International Conference on Software Engineering","author":"Duncan A","year":"1981"},{"key":"e_1_2_9_51_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380101104"},{"key":"e_1_2_9_52_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380220303"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.1017","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.1017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,31]],"date-time":"2023-10-31T04:13:55Z","timestamp":1698725635000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.1017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,28]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,4,10]]}},"alternative-id":["10.1002\/spe.1017"],"URL":"https:\/\/doi.org\/10.1002\/spe.1017","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,28]]}}}