{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T16:10:00Z","timestamp":1783008600240,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662545799","type":"print"},{"value":"9783662545805","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-662-54580-5_1","type":"book-chapter","created":{"date-parts":[[2017,3,30]],"date-time":"2017-03-30T06:50:09Z","timestamp":1490856609000},"page":"3-20","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["Static Detection of DoS Vulnerabilities in Programs that Use Regular Expressions"],"prefix":"10.1007","author":[{"given":"Valentin","family":"W\u00fcstholz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oswaldo","family":"Olivo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marijn J. H.","family":"Heule","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Isil","family":"Dillig","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,3,31]]},"reference":[{"key":"1_CR1","unstructured":"CVE-2013-2009. cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2013-2099"},{"key":"1_CR2","unstructured":"CVE-2015-2525. cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2015-2526"},{"key":"1_CR3","unstructured":"CVE-2015-2525. cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2009-3275"},{"key":"1_CR4","unstructured":"CVE-2016-2515. cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2016-2515"},{"key":"1_CR5","unstructured":"CVE-2016-2537. cve.mitre.org\/cgi-bin\/cvename.cgi?name=CVE-2016-2537"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Arzt, S., Rasthofer, S., Fritz, C., Bodden, E., Bartel, A., Klein, J., Traon, Y.L., Octeau, D., McDaniel, P.: Flowdroid: precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for Android apps. In: PLDI, pp. 259\u2013269. ACM (2014)","DOI":"10.1145\/2666356.2594299"},{"key":"1_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/3-540-45319-9_19","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"T Ball","year":"2001","unstructured":"Ball, T., Podelski, A., Rajamani, S.K.: Boolean and cartesian abstraction for model checking C programs. In: Margaria, T., Yi, W. (eds.) TACAS 2001. LNCS, vol. 2031, pp. 268\u2013283. Springer, Heidelberg (2001). doi:10.1007\/3-540-45319-9_19"},{"issue":"9","key":"1_CR8","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/1995376.1995398","volume":"54","author":"S Bandhakavi","year":"2011","unstructured":"Bandhakavi, S., Tiku, N., Pittman, W., King, S.T., Madhusudan, P., Winslett, M.: Vetting browser extensions for security vulnerabilities with VEX. Commun. ACM 54(9), 91\u201399 (2011)","journal-title":"Commun. ACM"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Berglund, M., Drewes, F., van der Merwe, B.: Analyzing catastrophic backtracking behavior in practical regular expression matching. In: AFL. EPTCS, vol. 151, pp. 109\u2013123 (2014)","DOI":"10.4204\/EPTCS.151.7"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Chang, R.M., Jiang, G., Ivancic, F., Sankaranarayanan, S., Shmatikov, V.: Inputs of coma: static detection of denial-of-service vulnerabilities. In: CSF, pp. 186\u2013199. IEEE Computer Society (2009)","DOI":"10.1109\/CSF.2009.13"},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"Chaudhuri, A., Foster, J.S.: Symbolic security analysis of ruby-on-rails web applications. In: CCS, pp. 585\u2013594. ACM (2010)","DOI":"10.1145\/1866307.1866373"},{"key":"1_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44898-5_1","volume-title":"Static Analysis","author":"AS Christensen","year":"2003","unstructured":"Christensen, A.S., M\u00f8ller, A., Schwartzbach, M.I.: Precise analysis of string expressions. In: Cousot, R. (ed.) SAS 2003. LNCS, vol. 2694, pp. 1\u201318. Springer, Heidelberg (2003). doi:10.1007\/3-540-44898-5_1"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: POPL, pp. 238\u2013252. ACM (1977)","DOI":"10.1145\/512950.512973"},{"key":"1_CR14","unstructured":"Crosby, S.A., Wallach, D.S.: Denial of service via algorithmic complexity attacks. In: USENIX Security Symposium. USENIX Association (2003)"},{"key":"1_CR15","unstructured":"Dahse, J., Holz, T.: Static detection of second-order vulnerabilities in web applications. In: USENIX Security Symposium, pp. 989\u20131003. USENIX Association (2014)"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Huang, H., Zhu, S., Chen, K., Liu, P.: From system services freezing to system server shutdown in Android: all you need is a loop in an app. In: CCS, pp. 1236\u20131247. ACM (2015)","DOI":"10.1145\/2810103.2813606"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Kiezun, A., Guo, P.J., Jayaraman, K., Ernst, M.D.: Automatic creation of SQL injection and cross-site scripting attacks. In: ICSE, pp. 199\u2013209. IEEE (2009)","DOI":"10.1109\/ICSE.2009.5070521"},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-38631-2_11","volume-title":"Network and System Security","author":"J Kirrage","year":"2013","unstructured":"Kirrage, J., Rathnayake, A., Thielecke, H.: Static analysis for regular expression denial-of-service attacks. In: Lopez, J., Huang, X., Sandhu, R. (eds.) NSS 2013. LNCS, vol. 7873, pp. 135\u2013148. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-38631-2_11"},{"key":"1_CR19","unstructured":"Livshits, V.B., Lam, M.S.: Finding security vulnerabilities in Java applications with static analysis. In: USENIX Security Symposium. USENIX Association (2005)"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"Martin, M.C., Livshits, V.B., Lam, M.S.: Finding application errors and security flaws using PQL: a program query language. In: OOPSLA, pp. 365\u2013383. ACM (2005)","DOI":"10.1145\/1103845.1094840"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Olivo, O., Dillig, I., Lin, C.: Detecting and exploiting second order denial-of-service vulnerabilities in web applications. In: CCS, pp. 616\u2013628. ACM (2015)","DOI":"10.1145\/2810103.2813680"},{"key":"1_CR22","unstructured":"Rathnayake, A., Thielecke, H.: Static analysis for regular expression exponential runtime via substructural logics. CoRR abs\/1405.7058 (2014)"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"Su, Z., Wassermann, G.: The essence of command injection attacks in web applications. In: POPL, pp. 372\u2013382. ACM (2006)","DOI":"10.1145\/1111320.1111070"},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"82","DOI":"10.2197\/ipsjtrans.7.82","volume":"7","author":"S Sugiyama","year":"2014","unstructured":"Sugiyama, S., Minamide, Y.: Checking time linearity of regular expression matching based on backtracking. IPSJ Online Trans. 7, 82\u201392 (2014)","journal-title":"IPSJ Online Trans."},{"issue":"6","key":"1_CR25","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1145\/363347.363387","volume":"11","author":"K Thompson","year":"1968","unstructured":"Thompson, K.: Programming techniques: regular expression search algorithm. Commun. ACM 11(6), 419\u2013422 (1968)","journal-title":"Commun. ACM"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"Tripp, O., Pistoia, M., Fink, S.J., Sridharan, M., Weisman, O.: TAJ: effective taint analysis of web applications. In: PLDI, pp. 87\u201397. ACM (2009)","DOI":"10.1145\/1543135.1542486"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Wassermann, G., Su, Z.: Sound and precise analysis of web applications for injection vulnerabilities. In: PLDI, pp. 32\u201341. ACM (2007)","DOI":"10.1145\/1273442.1250739"},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"Wassermann, G., Su, Z.: Static detection of cross-site scripting vulnerabilities. In: ICSE, pp. 171\u2013180. ACM (2008)","DOI":"10.1145\/1368088.1368112"},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"Wassermann, G., Yu, D., Chander, A., Dhurjati, D., Inamura, H., Su, Z.: Dynamic test input generation for web applications. In: ISSTA, pp. 249\u2013260. ACM (2008)","DOI":"10.1145\/1390630.1390661"},{"key":"1_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/978-3-319-40946-7_27","volume-title":"Implementation and Application of Automata","author":"N Weideman","year":"2016","unstructured":"Weideman, N., Merwe, B., Berglund, M., Watson, B.: Analyzing matching time behavior of backtracking regular expression matchers by using ambiguity of NFA. In: Han, Y.-S., Salomaa, K. (eds.) CIAA 2016. LNCS, vol. 9705, pp. 322\u2013334. Springer, Cham (2016). doi:10.1007\/978-3-319-40946-7_27"},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"W\u00fcstholz, V., Olivo, O., Heule, M.J.H., Dillig, I.: Static detection of DoS vulnerabilities in programs that use regular expressions (extended version). CoRR abs\/1701.04045 (2017)","DOI":"10.1007\/978-3-662-54580-5_1"},{"key":"1_CR32","unstructured":"Xie, Y., Aiken, A.: Static detection of security vulnerabilities in scripting languages. In: USENIX Security Symposium. USENIX Association (2006)"},{"key":"1_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-642-12002-2_13","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"F Yu","year":"2010","unstructured":"Yu, F., Alkhalaf, M., Bultan, T.: Stranger: an automata-based string analysis tool for PHP. In: Esparza, J., Majumdar, R. (eds.) TACAS 2010. LNCS, vol. 6015, pp. 154\u2013157. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-12002-2_13"},{"issue":"1","key":"1_CR34","first-page":"44","volume":"44","author":"F Yu","year":"2014","unstructured":"Yu, F., Alkhalaf, M., Bultan, T., Ibarra, O.H.: Automata-based symbolic string analysis for vulnerability detection. FMSD 44(1), 44\u201370 (2014)","journal-title":"FMSD"},{"key":"1_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/978-3-642-22306-8_3","volume-title":"Model Checking Software","author":"F Yu","year":"2011","unstructured":"Yu, F., Bultan, T., Hardekopf, B.: String abstractions for string verification. In: Groce, A., Musuvathi, M. (eds.) SPIN 2011. LNCS, vol. 6823, pp. 20\u201337. Springer, Heidelberg (2011). doi:10.1007\/978-3-642-22306-8_3"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-54580-5_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,21]],"date-time":"2021-04-21T02:45:08Z","timestamp":1618973108000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-54580-5_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783662545799","9783662545805"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-54580-5_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"31 March 2017","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":"Uppsala","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sweden","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 April 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 April 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.etaps.org\/index.php\/2017\/tacas","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}