{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T03:06:47Z","timestamp":1769742407762,"version":"3.49.0"},"reference-count":88,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T00:00:00Z","timestamp":1697414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,10,16]]},"abstract":"<jats:p>We present a new algorithm for solving string constraints. The algorithm builds upon a recent method for solving word equations and regular constraints that interprets string variables as languages rather than strings and, consequently, mitigates the combinatorial explosion that plagues other approaches. We extend the approach to handle linear integer arithmetic length constraints by combination with a known principle of equation alignment and splitting, and by extension to other common types of string constraints, yielding a fully-fledged string solver. The ability of the framework to handle unrestricted disequalities even extends one of the largest decidable classes of string constraints, the chain-free fragment. We integrate our algorithm into a DPLL-based SMT solver. The performance of our implementation is competitive and even significantly better than state-of-the-art string solvers on several established benchmarks obtained from applications in verification of string programs.<\/jats:p>","DOI":"10.1145\/3622872","type":"journal-article","created":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T15:41:29Z","timestamp":1697470889000},"page":"2112-2141","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Solving String Constraints with Lengths by Stabilization"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2872-0336","authenticated-orcid":false,"given":"Yu-Fang","family":"Chen","sequence":"first","affiliation":[{"name":"Academia Sinica, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-5614-1592","authenticated-orcid":false,"given":"David","family":"Chocholat\u00fd","sequence":"additional","affiliation":[{"name":"Brno University of Technology, Brno, Czechia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4375-7954","authenticated-orcid":false,"given":"Vojt\u011bch","family":"Havlena","sequence":"additional","affiliation":[{"name":"Brno University of Technology, Brno, Czechia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6957-1651","authenticated-orcid":false,"given":"Luk\u00e1\u0161","family":"Hol\u00edk","sequence":"additional","affiliation":[{"name":"Brno University of Technology, Brno, Czechia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3038-5875","authenticated-orcid":false,"given":"Ond\u0159ej","family":"Leng\u00e1l","sequence":"additional","affiliation":[{"name":"Brno University of Technology, Brno, Czechia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7454-3751","authenticated-orcid":false,"given":"Juraj","family":"S\u00ed\u010d","sequence":"additional","affiliation":[{"name":"Brno University of Technology, Brno, Czechia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,10,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-89051-3_17"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062384"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.23919\/FMCAD.2018.8602997"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_10"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21690-4_29"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-31784-3_16"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-13185-1_16"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66158-2_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21690-4_15"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.23919\/FMCAD.2018.8602994"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.3233\/978-1-61499-495-4-26"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99524-9_24"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3070822"},{"key":"e_1_2_1_15_1","unstructured":"Clark Barrett Pascal Fontaine and Cesare Tinelli. 2016. The Satisfiability Modulo Theories Library (SMT-LIB). www.SMT-LIB.org \t\t\t\t  Clark Barrett Pascal Fontaine and Cesare Tinelli. 2016. The Satisfiability Modulo Theories Library (SMT-LIB). www.SMT-LIB.org"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898375.2898393"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.12.009"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.23919\/FMCAD.2017.8102241"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81688-9_14"},{"key":"e_1_2_1_20_1","unstructured":"Berzish Murphy. 2021.\n  Z3str4: A Solver for Theories over Strings\n  . Ph.D. Dissertation. http:\/\/hdl.handle.net\/10012\/17102 \t\t\t\t  Berzish Murphy. 2021. Z3str4: A Solver for Theories over Strings. Ph.D. Dissertation. http:\/\/hdl.handle.net\/10012\/17102"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00768-2_27"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-27481-7_23"},{"key":"e_1_2_1_23_1","unstructured":"Tevfik Bultan. [n. d.]. ABC string solver. https:\/\/github.com\/vlab-cs-ucsb\/ABC \t\t\t\t  Tevfik Bultan. [n. d.]. ABC string solver. https:\/\/github.com\/vlab-cs-ucsb\/ABC"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/635499.635502"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158091"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498707"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59152-6_18"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290362"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11194-0_12"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64437-6_18"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.8289595"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2023.111673"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44898-5_1"},{"key":"e_1_2_1_34_1","volume-title":"Model Checking Regular Language Constraints. CoRR, abs\/1708.09073","author":"Cox Arlen","year":"2017","unstructured":"Arlen Cox and Jason Leasure . 2017. Model Checking Regular Language Constraints. CoRR, abs\/1708.09073 ( 2017 ), arXiv:1708.09073. arxiv:1708.09073 Arlen Cox and Jason Leasure. 2017. Model Checking Regular Language Constraints. CoRR, abs\/1708.09073 (2017), arXiv:1708.09073. arxiv:1708.09073"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30806-3_8"},{"key":"e_1_2_1_36_1","volume-title":"The Satisfiability of Extended Word Equations: The Boundary Between Decidability and Undecidability. CoRR, abs\/1802.00523","author":"Day Joel D.","year":"2018","unstructured":"Joel D. Day , Vijay Ganesh , Paul He , Florin Manea , and Dirk Nowotka . 2018. The Satisfiability of Extended Word Equations: The Boundary Between Decidability and Undecidability. CoRR, abs\/1802.00523 ( 2018 ), arXiv:1802.00523. arxiv:1802.00523 Joel D. Day, Vijay Ganesh, Paul He, Florin Manea, and Dirk Nowotka. 2018. The Satisfiability of Extended Word Equations: The Boundary Between Decidability and Undecidability. CoRR, abs\/1802.00523 (2018), arXiv:1802.00523. arxiv:1802.00523"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.3233\/FI-1997-3112"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38499-8_17"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.130"},{"key":"e_1_2_1_41_1","volume-title":"Second NASA Formal Methods Symposium - NFM 2010, Washington D.C., USA, April 13-15, 2010. Proceedings, C\u00e9sar A. Mu\u00f1oz (Ed.) (NASA Conference Proceedings","volume":"76","author":"Fu Xiang","year":"2010","unstructured":"Xiang Fu and Chung-Chih Li . 2010 . Modeling regular replacement for string constraint solving . In Second NASA Formal Methods Symposium - NFM 2010, Washington D.C., USA, April 13-15, 2010. Proceedings, C\u00e9sar A. Mu\u00f1oz (Ed.) (NASA Conference Proceedings , Vol. NASA\/CP-2010-216215). 67\u2013 76 . Xiang Fu and Chung-Chih Li. 2010. Modeling regular replacement for string constraint solving. In Second NASA Formal Methods Symposium - NFM 2010, Washington D.C., USA, April 13-15, 2010. Proceedings, C\u00e9sar A. Mu\u00f1oz (Ed.) (NASA Conference Proceedings, Vol. NASA\/CP-2010-216215). 67\u201376."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39611-3_21"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158092"},{"key":"e_1_2_1_44_1","volume-title":"20th USENIX Security Symposium","author":"Hooimeijer Pieter","year":"2011","unstructured":"Pieter Hooimeijer , Benjamin Livshits , David Molnar , Prateek Saxena , and Margus Veanes . 2011 . Fast and precise sanitizer analysis with BEK . In 20th USENIX Security Symposium , San Francisco, CA, USA , August 8-12, 2011, Proceedings. USENIX Association. http:\/\/static.usenix.org\/events\/sec11\/tech\/full_papers\/Hooimeijer.pdf Pieter Hooimeijer, Benjamin Livshits, David Molnar, Prateek Saxena, and Margus Veanes. 2011. Fast and precise sanitizer analysis with BEK. In 20th USENIX Security Symposium, San Francisco, CA, USA, August 8-12, 2011, Proceedings. USENIX Association. http:\/\/static.usenix.org\/events\/sec11\/tech\/full_papers\/Hooimeijer.pdf"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10515-012-0111-x"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2743014"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2377656.2377662"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-02768-1_19"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03077-7_2"},{"key":"e_1_2_1_50_1","unstructured":"Liana Hadarean. 2019. String Solving at Amazon. https:\/\/mosca19.github.io\/program\/index.html Presented at MOSCA\u201919. \t\t\t\t  Liana Hadarean. 2019. String Solving at Amazon. https:\/\/mosca19.github.io\/program\/index.html Presented at MOSCA\u201919."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_43"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-016-0247-6"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24246-0_9"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837641"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-17(4:4)2021"},{"key":"e_1_2_1_56_1","first-page":"147","article-title":"The problem of solvability of equations in a free semigroup","volume":"32","author":"Makanin G. S.","year":"1977","unstructured":"G. S. Makanin . 1977 . The problem of solvability of equations in a free semigroup . Matematicheskii Sbornik , 32 , 2 (1977), 147 \u2013 236 . (in Russian). G. S. Makanin. 1977. The problem of solvability of equations in a free semigroup. Matematicheskii Sbornik, 32, 2 (1977), 147\u2013236. (in Russian).","journal-title":"Matematicheskii Sbornik"},{"key":"e_1_2_1_57_1","unstructured":"Microsoft. 2020. Azure Resource Manager documentation. https:\/\/docs.microsoft.com\/en-us\/azure\/azure-resource-manager\/ \t\t\t\t  Microsoft. 2020. Azure Resource Manager documentation. https:\/\/docs.microsoft.com\/en-us\/azure\/azure-resource-manager\/"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-90870-6_21"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457113"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217859"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-13188-2_11"},{"key":"e_1_2_1_62_1","unstructured":"OWASP. 2013. Top 10. https:\/\/www.owasp.org\/images\/f\/f8\/OWASP_Top_10_-_2013.pdf \t\t\t\t  OWASP. 2013. Top 10. https:\/\/www.owasp.org\/images\/f\/f8\/OWASP_Top_10_-_2013.pdf"},{"key":"e_1_2_1_63_1","unstructured":"OWASP. 2017. Top 10. https:\/\/owasp.org\/www-project-top-ten\/2017\/ \t\t\t\t  OWASP. 2017. Top 10. https:\/\/owasp.org\/www-project-top-ten\/2017\/"},{"key":"e_1_2_1_64_1","unstructured":"OWASP. 2021. Top 10. https:\/\/owasp.org\/Top10\/ \t\t\t\t  OWASP. 2021. Top 10. https:\/\/owasp.org\/Top10\/"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321364"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301443"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25543-5_2"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.34727\/2020\/isbn.978-3-85448-042-6_30"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_24"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-13185-1_1"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2010.38"},{"key":"e_1_2_1_72_1","unstructured":"Prateek Saxena Devdatta Akhawe Steve Hanna Feng Mao Stephen McCamant and Dawn Song. 2023. Kaluza web site. https:\/\/webblaze.cs.berkeley.edu\/2010\/kaluza\/ \t\t\t\t  Prateek Saxena Devdatta Akhawe Steve Hanna Feng Mao Stephen McCamant and Dawn Song. 2023. Kaluza web site. https:\/\/webblaze.cs.berkeley.edu\/2010\/kaluza\/"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59776-8_5"},{"key":"e_1_2_1_74_1","unstructured":"SMT-COMP\u201922. 2022. https:\/\/smt-comp.github.io\/2022\/ \t\t\t\t  SMT-COMP\u201922. 2022. https:\/\/smt-comp.github.io\/2022\/"},{"key":"e_1_2_1_75_1","unstructured":"SMTLib. 2023. https:\/\/clc-gitlab.cs.uiowa.edu:2443\/SMT-LIB-benchmarks\/QF_S \t\t\t\t  SMTLib. 2023. https:\/\/clc-gitlab.cs.uiowa.edu:2443\/SMT-LIB-benchmarks\/QF_S"},{"key":"e_1_2_1_76_1","unstructured":"SMTLib. 2023. https:\/\/clc-gitlab.cs.uiowa.edu:2443\/SMT-LIB-benchmarks\/QF_SLIA \t\t\t\t  SMTLib. 2023. https:\/\/clc-gitlab.cs.uiowa.edu:2443\/SMT-LIB-benchmarks\/QF_SLIA"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454066"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660372"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_12"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/2103656.2103674"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_13"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3238147.3238189"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12002-2_13"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-013-0189-1"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111009112"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21690-4_14"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491411.2491456"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjjip.27.810"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3622872","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3622872","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:57:27Z","timestamp":1750298247000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3622872"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,16]]},"references-count":88,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2023,10,16]]}},"alternative-id":["10.1145\/3622872"],"URL":"https:\/\/doi.org\/10.1145\/3622872","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,16]]},"assertion":[{"value":"2023-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}