{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T14:57:09Z","timestamp":1776092229008,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"FSE","license":[{"start":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T00:00:00Z","timestamp":1720742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Softw. Eng."],"published-print":{"date-parts":[[2024,7,12]]},"abstract":"<jats:p>\n                    We present\n                    <jats:sc>FeatMaker<\/jats:sc>\n                    , a novel technique that automatically generates state features to enhance the search strategy of symbolic execution. Search strategies, designed to address the well-known state-explosion problem, prioritize which program states to explore. These strategies typically depend on a \u201cstate feature\u201d that describes a specific property of program states, using this feature to score and rank them. Recently, search strategies employing multiple state features have shown superior performance over traditional strategies that use a single, generic feature. However, the process of designing these features remains largely manual. Moreover, manually crafting state features is both time-consuming and prone to yielding unsatisfactory results. The goal of this paper is to fully automate the process of generating state features for search strategies from scratch. The key idea is to leverage path-conditions, which are basic but vital information maintained by symbolic execution, as state features. A challenge arises when employing all path-conditions as state features, as it results in an excessive number of state features. To address this, we present a specialized algorithm that iteratively generates and refines state features based on data accumulated during symbolic execution. Experimental results on 15 open-source C programs show that\n                    <jats:sc>FeatMaker<\/jats:sc>\n                    significantly outperforms existing search strategies that rely on manually-designed features, both in terms of branch coverage and bug detection. Notably,\n                    <jats:sc>FeatMaker<\/jats:sc>\n                    achieved an average of 35.3% higher branch coverage than state-of-the-art strategies and discovered 15 unique bugs. Of these, six were detected exclusively by\n                    <jats:sc>FeatMaker<\/jats:sc>\n                    .\n                  <\/jats:p>","DOI":"10.1145\/3660815","type":"journal-article","created":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T10:22:09Z","timestamp":1720779729000},"page":"2447-2468","source":"Crossref","is-referenced-by-count":3,"title":["FeatMaker: Automated Feature Engineering for Search Strategy of Symbolic Execution"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-5502-7520","authenticated-orcid":false,"given":"Jaehan","family":"Yoon","sequence":"first","affiliation":[{"name":"Sungkyunkwan University, Suwon, South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4697-8536","authenticated-orcid":false,"given":"Sooyoung","family":"Cha","sequence":"additional","affiliation":[{"name":"Sungkyunkwan University, Suwon, South Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,7,12]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2020.2967380"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/2042243.2042252"},{"key":"e_1_3_1_4_2","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1007\/s10664-013-9249-9","article-title":"Parameter tuning or default values? An empirical investigation in search-based software engineering","author":"Arcuri Andrea","year":"2013","unstructured":"AndreaArcuri and GordonFraser. 2013. Parameter tuning or default values? An empirical investigation in search-based software engineering. Empirical Software Engineering 594\u2013623","journal-title":"Empirical Software Engineering"},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","first-page":"3075","DOI":"10.1016\/j.ins.2007.11.024","article-title":"Search based software testing of object-oriented containers","author":"Arcuri Andrea","year":"2008","unstructured":"AndreaArcuri and XinYao. 2008. Search based software testing of object-oriented containers. Information Sciences 3075\u20133095","journal-title":"Information Sciences"},{"key":"e_1_3_1_6_2","first-page":"53","article-title":"Symbolic search-based testing","author":"Baars Arthur","year":"2011","unstructured":"ArthurBaars, MarkHarman, YoussefHassoun, KiranLakhotia, PhilMcMinn, PaoloTonella, and TanjaVos. 2011. Symbolic search-based testing. 2011 26th IEEE\/ACM International Conference on Automated Software Engineering (ASE 2011) (ASE \u201911) 53\u201362","journal-title":"2011 26th IEEE\/ACM International Conference on Automated Software Engineering (ASE 2011) (ASE \u201911)"},{"key":"e_1_3_1_7_2","doi-asserted-by":"crossref","unstructured":"PeterBoonstoppel CristianCadar and DawsonEngler. 2008. RWset: Attacking path explosion in constraint-based test generation. International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS \u201908) 351\u2013366","DOI":"10.1007\/978-3-540-78800-3_27"},{"key":"e_1_3_1_8_2","first-page":"199","article-title":"Redundant State Detection for Dynamic Symbolic Execution","author":"Bugrara Suhabe","year":"2013","unstructured":"SuhabeBugrara and DawsonEngler. 2013. Redundant State Detection for Dynamic Symbolic Execution. Proceedings of the 2013 USENIX Conference on Annual Technical Conference (USENIX ATC'13) 199\u2013212","journal-title":"Proceedings of the 2013 USENIX Conference on Annual Technical Conference (USENIX ATC'13)"},{"key":"e_1_3_1_9_2","first-page":"443","article-title":"Heuristics for Scalable Dynamic Test Generation","author":"Burnim Jacob","year":"2008","unstructured":"JacobBurnim and KoushikSen. 2008. Heuristics for Scalable Dynamic Test Generation. Proceedings of 23rd IEEE\/ACM International Conference on Automated Software Engineering (ASE'08) 443\u2013446","journal-title":"Proceedings of 23rd IEEE\/ACM International Conference on Automated Software Engineering (ASE'08)"},{"key":"e_1_3_1_10_2","first-page":"209","article-title":"KLEE: Unassisted and Automatic Generation of High-coverage Tests for Complex Systems Programs","author":"Cadar Cristian","year":"2008","unstructured":"CristianCadar, DanielDunbar, and DawsonEngler. 2008. KLEE: Unassisted and Automatic Generation of High-coverage Tests for Complex Systems Programs. Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation (OSDI \u201908) 209\u2013224.","journal-title":"Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation (OSDI \u201908)"},{"key":"e_1_3_1_11_2","first-page":"2","article-title":"Execution Generated test-cases: How to Make Systems Code Crash Itself","author":"Cadar Cristian","year":"2005","unstructured":"CristianCadar and DawsonEngler. 2005. Execution Generated test-cases: How to Make Systems Code Crash Itself. Proceedings of the 12th International Conference on Model Checking Software (SPIN'05) 2\u201323","journal-title":"Proceedings of the 12th International Conference on Model Checking Software (SPIN'05)"},{"issue":"2","key":"e_1_3_1_12_2","first-page":"10:1","article-title":"EXE: Automatically Generating Inputs of Death","volume":"12","author":"Cadar Cristian","year":"2008","unstructured":"CristianCadar, VijayGanesh, Peter M.Pawlowski, David L.Dill, and Dawson R.Engler. 2008. EXE: Automatically Generating Inputs of Death. ACM Transactions on Information and System Security 12 2 10:1\u201310:38","journal-title":"ACM Transactions on Information and System Security"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2021.3101870"},{"key":"e_1_3_1_14_2","first-page":"1244","article-title":"Automatically Generating Search Heuristics for Concolic Testing","author":"Cha Sooyoung","year":"2018","unstructured":"SooyoungCha, SeongjoonHong, JunheeLee, and HakjooOh. 2018. Automatically Generating Search Heuristics for Concolic Testing. Proceedings of the 40th International Conference on Software Engineering (ICSE \u201918) 1244\u20131254","journal-title":"Proceedings of the 40th International Conference on Software Engineering (ICSE \u201918)"},{"key":"e_1_3_1_15_2","article-title":"Making Symbolic Execution Promising by Learning Aggressive State-Pruning Strategy","author":"Cha Sooyoung","year":"2020","unstructured":"Sooyoung Cha and HakjooOh. 2020. Making Symbolic Execution Promising by Learning Aggressive State-Pruning Strategy. The 28th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC\/FSE \u201920)","journal-title":"The 28th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC\/FSE \u201920)"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3341180"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2017.61"},{"key":"e_1_3_1_18_2","unstructured":"CREST. 2008. A concolic test generation tool for C. https:\/\/github.com\/jburnim\/crest"},{"key":"e_1_3_1_19_2","first-page":"337","article-title":"Z3: An efficient SMT solver","author":"De Moura Leonardo","year":"2008","unstructured":"LeonardoDe Moura and NikolajBj\u00f8rner. 2008. Z3: An efficient SMT solver. International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS \u201908) 337\u2013340","journal-title":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS \u201908)"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/C-M.1978.218136"},{"key":"e_1_3_1_21_2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1109\/ICST.2012.92","article-title":"The seed is strong: Seeding strategies in search-based software testing","author":"Fraser Gordon","year":"2012","unstructured":"GordonFraser and AndreaArcuri. 2012. The seed is strong: Seeding strategies in search-based software testing. 2012 IEEE Fifth International Conference on Software Testing, Verification and Validation (ICST \u201912) 121\u2013130","journal-title":"2012 IEEE Fifth International Conference on Software Testing, Verification and Validation (ICST \u201912)"},{"key":"e_1_3_1_22_2","first-page":"519","article-title":"A decision procedure for bit-vectors and arrays","author":"Ganesh Vijay","year":"2007","unstructured":"VijayGanesh and David LDill. 2007. A decision procedure for bit-vectors and arrays. International Conference on Computer Aided Verification (CAV \u201907) 519\u2013531","journal-title":"International Conference on Computer Aided Verification (CAV \u201907)"},{"key":"e_1_3_1_23_2","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/1065010.1065036","article-title":"DART: Directed Automated Random Testing","author":"Godefroid Patrice","year":"2005","unstructured":"PatriceGodefroid, NilsKlarlund, and KoushikSen. 2005. DART: Directed Automated Random Testing. Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI \u201905) 213\u2013223","journal-title":"Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI \u201905)"},{"key":"e_1_3_1_24_2","first-page":"151","article-title":"Automated Whitebox Fuzz Testing","author":"Godefroid Patrice","year":"2008","unstructured":"PatriceGodefroid, Michael YLevin, and David AMolnar. 2008. Automated Whitebox Fuzz Testing. Proceedings of the Symposium on Network and Distributed System Security (NDSS \u201908) 151\u2013166","journal-title":"Proceedings of the Symposium on Network and Distributed System Security (NDSS \u201908)"},{"key":"e_1_3_1_25_2","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1109\/TSE.1977.231145","article-title":"Testing Programs with the Aid of a Compiler","author":"Hamlet R.G.","year":"1977","unstructured":"R.G.Hamlet. 1977. Testing Programs with the Aid of a Compiler. IEEE Transactions on Software Engineering 279\u2013290","journal-title":"IEEE Transactions on Software Engineering"},{"key":"e_1_3_1_26_2","doi-asserted-by":"crossref","DOI":"10.1109\/ICST.2015.7102580","article-title":"Achievements, open problems and challenges for search based software testing","author":"Harman Mark","year":"2015","unstructured":"MarkHarman, YueJia, and YuanyuanZhang. 2015. Achievements, open problems and challenges for search based software testing. 2015 IEEE 8th International Conference on Software Testing, Verification and Validation (ICST \u201915)","journal-title":"2015 IEEE 8th International Conference on Software Testing, Verification and Validation (ICST \u201915)"},{"key":"e_1_3_1_27_2","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1016\/S0950-5849(01)00189-6","article-title":"Search-based software engineering","author":"Harman Mark","year":"2001","unstructured":"MarkHarman and Bryan FJones. 2001. Search-based software engineering. Information and Software Technology 833\u2013839","journal-title":"Information and Software Technology"},{"key":"e_1_3_1_28_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2379776.2379787","article-title":"Search-based software engineering: Trends, techniques and applications","author":"Harman Mark","year":"2012","unstructured":"MarkHarman, S AfshinMansouri, and YuanyuanZhang. 2012. Search-based software engineering: Trends, techniques and applications. ACM Computing Surveys (CSUR) 1\u201361","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"e_1_3_1_29_2","first-page":"1","article-title":"Search based software engineering: Techniques, taxonomy, tutorial","author":"Harman Mark","year":"2010","unstructured":"MarkHarman, PhilMcMinn, JerffesonTeixeira De Souza, and ShinYoo. 2010. Search based software engineering: Techniques, taxonomy, tutorial Empirical software engineering and verification 1\u201359","journal-title":"Empirical software engineering and verification"},{"key":"e_1_3_1_30_2","first-page":"2526","article-title":"Learning to Explore Paths for Symbolic Execution","author":"He Jingxuan","year":"2021","unstructured":"JingxuanHe, GishorSivanrupan, PetarTsankov, and MartinVechev. 2021. Learning to Explore Paths for Symbolic Execution. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (CCS \u201921) 2526\u20132540","journal-title":"Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (CCS \u201921)"},{"key":"e_1_3_1_31_2","first-page":"48","article-title":"Boosting Concolic Testing via Interpolation","author":"Jaffar Joxan","year":"2013","unstructured":"JoxanJaffar, VijayaraghavanMurali, and Jorge A.Navas. 2013. Boosting Concolic Testing via Interpolation. Proceedings of the 9th Joint Meeting on Foundations of Software Engineering (ESEC\/FSE \u201913) 48\u201358","journal-title":"Proceedings of the 9th Joint Meeting on Foundations of Software Engineering (ESEC\/FSE \u201913)"},{"key":"e_1_3_1_32_2","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1109\/TSE.2010.62","article-title":"An Analysis and Survey of the Development of Mutation Testing","author":"Jia Yue","year":"2011","unstructured":"YueJia and MarkHarman. 2011. An Analysis and Survey of the Development of Mutation Testing. IEEE Transactions on Software Engineering (TSE) 649-678","journal-title":"IEEE Transactions on Software Engineering (TSE)"},{"key":"e_1_3_1_33_2","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/800125.804034","article-title":"Approximation Algorithms for Combinatorial Problems","author":"Johnson David S.","year":"1973","unstructured":"David S.Johnson. 1973. Approximation Algorithms for Combinatorial Problems. Proceedings of the Fifth Annual ACM Symposium on Theory of Computing 38\u201349","journal-title":"Proceedings of the Fifth Annual ACM Symposium on Theory of Computing"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/3477.764879"},{"key":"e_1_3_1_36_2","first-page":"19","article-title":"Steering Symbolic Execution to Less Traveled Paths","author":"Li You","year":"2013","unstructured":"YouLi, ZhendongSu, LinzhangWang, and XuandongLi. 2013. Steering Symbolic Execution to Less Traveled Paths. Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems, Languages, and Applications (OOPSLA \u201913) 19\u201332","journal-title":"Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems, Languages, and Applications (OOPSLA \u201913)"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177730491"},{"key":"e_1_3_1_38_2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1109\/ICSTW.2011.100","article-title":"Search-based software testing: Past, present and future","author":"McMinn Phil","year":"2011","unstructured":"PhilMcMinn. 2011. Search-based software testing: Past, present and future. 2011 IEEE Fourth International Conference on Software Testing, Verification and Validation Workshops 153\u2013163","journal-title":"2011 IEEE Fourth International Conference on Software Testing, Verification and Validation Workshops"},{"key":"e_1_3_1_39_2","unstructured":"OSDI'08_Coreutil_Experiments2008Coreutils experimentshttps:\/\/klee.github.io\/docs\/coreutils-experiments"},{"key":"e_1_3_1_40_2","first-page":"35:1","article-title":"CarFast: Achieving Higher Statement Coverage Faster","author":"Park Sangmin","year":"2012","unstructured":"SangminPark, B. M.Mainul Hossain, IshtiaqueHussain, ChristophCsallner, MarkGrechanik, KunalTaneja, ChenFu, and QingXie. 2012. CarFast: Achieving Higher Statement Coverage Faster. Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering (FSE \u201912) 35:1\u201335:11","journal-title":"Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering (FSE \u201912)"},{"key":"e_1_3_1_41_2","first-page":"263","article-title":"CUTE: A Concolic Unit Testing Engine for C","author":"Sen Koushik","year":"2005","unstructured":"KoushikSen, DarkoMarinov, and GulAgha. 2005. CUTE: A Concolic Unit Testing Engine for C. Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC\/FSE \u201905) 263\u2013272","journal-title":"Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC\/FSE \u201905)"},{"key":"e_1_3_1_42_2","article-title":"How We Get There: A Context-guided Search Strategy in Concolic Testing","author":"Seo Hyunmin","year":"2014","unstructured":"HyunminSeo and SunghunKim. 2014. How We Get There: A Context-guided Search Strategy in Concolic Testing. Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE \u201914)","journal-title":"Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE \u201914)"},{"key":"e_1_3_1_43_2","unstructured":"ParaDysE2022A tool for automaticallygenerating search strategy of symbolic executionhttps:\/\/github.com\/kupl\/dd-klee\/tree\/master\/paradyse"},{"key":"e_1_3_1_44_2","unstructured":"Gcov2021A tool for measuring coveragehttps:\/\/gcc.gnu.org\/onlinedocs\/gcc\/Gcov.html"},{"key":"e_1_3_1_45_2","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1145\/3180155.3180251","article-title":"Chopped Symbolic Execution","author":"Trabish David","year":"2018","unstructured":"DavidTrabish, AndreaMattavelli, NoamRinetzky, and CristianCadar. 2018. Chopped Symbolic Execution. Proceedings of the 40th International Conference on Software Engineering (ICSE \u201918) 350\u2013360","journal-title":"Proceedings of the 40th International Conference on Software Engineering (ICSE \u201918)"},{"key":"e_1_3_1_46_2","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1145\/3180155.3180177","article-title":"Towards Optimal Concolic Testing","author":"Wang Xinyu","year":"2018","unstructured":"XinyuWang, JunSun, ZhenbangChen, PeixinZhang, JingyiWang, and YunLin. 2018. Towards Optimal Concolic Testing. Proceedings of the 40th International Conference on Software Engineering (ICSE \u201918) 291\u2013302","journal-title":"Proceedings of the 40th International Conference on Software Engineering (ICSE \u201918)"},{"key":"e_1_3_1_47_2","first-page":"359","article-title":"Fitness-guided path exploration in dynamic symbolic execution","author":"Xie Tao","year":"2009","unstructured":"TaoXie, NikolaiTillmann, Jonathande Halleux, and WolframSchulte. 2009. Fitness-guided path exploration in dynamic symbolic execution. 2009 IEEE\/IFIP International Conference on Dependable Systems Networks 359\u2013368","journal-title":"2009 IEEE\/IFIP International Conference on Dependable Systems Networks"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2017.2659751"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2013.6693070"},{"key":"e_1_3_1_50_2","doi-asserted-by":"crossref","unstructured":"LuZhang Shan-ShanHou Jun-JueHu TaoXie and HongMei. 2010. Is operator-based mutant selection superior to random mutant selection?. Proceedings of the 32nd ACM\/IEEE International Conference on Software Engineering - Volume 1 (ICSE \u201910) 435\u2013444","DOI":"10.1145\/1806799.1806863"}],"container-title":["Proceedings of the ACM on Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3660815","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3660815","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T07:55:40Z","timestamp":1770191740000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3660815"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,12]]},"references-count":49,"journal-issue":{"issue":"FSE","published-print":{"date-parts":[[2024,7,12]]}},"alternative-id":["10.1145\/3660815"],"URL":"https:\/\/doi.org\/10.1145\/3660815","relation":{},"ISSN":["2994-970X"],"issn-type":[{"value":"2994-970X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,12]]}}}