research-article

Open access

Exploiting input sanitization for regex denial of service

Authors:

James C. DavisAuthors Info & Claims

ICSE '22: Proceedings of the 44th International Conference on Software Engineering

Pages 883 - 895

https://doi.org/10.1145/3510003.3510047

Published: 05 July 2022 Publication History

Abstract

Web services use server-side input sanitization to guard against harmful input. Some web services publish their sanitization logic to make their client interface more usable, e.g., allowing clients to debug invalid requests locally. However, this usability practice poses a security risk. Specifically, services may share the regexes they use to sanitize input strings --- and regex-based denial of service (ReDoS) is an emerging threat. Although prominent service outages caused by ReDoS have spurred interest in this topic, we know little about the degree to which live web services are vulnerable to ReDoS.

In this paper, we conduct the first black-box study measuring the extent of ReDoS vulnerabilities in live web services. We apply the Consistent Sanitization Assumption: that client-side sanitization logic, including regexes, is consistent with the sanitization logic on the server-side. We identify a service's regex-based input sanitization in its HTML forms or its API, find vulnerable regexes among these regexes, craft ReDoS probes, and pinpoint vulnerabilities. We analyzed the HTML forms of 1,000 services and the APIs of 475 services. Of these, 355 services publish regexes; 17 services publish unsafe regexes; and 6 services are vulnerable to ReDoS through their APIs (6 domains; 15 subdomains). Both Microsoft and Amazon Web Services patched their web services as a result of our disclosure. Since these vulnerabilities were from API specifications, not HTML forms, we proposed a ReDoS defense for a popular API validation library, and our patch has been merged. To summarize: in client-visible sanitization logic, some web services advertise ReDoS vulnerabilities in plain sight. Our results motivate short-term patches and long-term fundamental solutions.

"Make measurable what cannot be measured." -Galileo Galilei

References

[1]

2014. Documentation | API Blueprint. https://apiblueprint.org/documentation/

[2]

2015. Support interdependencies between query parameters · Issue #256 · OAI/OpenAPI-Specification. https://github.com/OAI/OpenAPI-Specification/issues/256

[3]

2019. GitHub - davisjam/vuln-regex-detector: Detect vulnerable regexes in your project. https://github.com/davisjam/vuln-regex-detector

[4]

2019. Prism | Open-Source HTTP Mock and Proxy Server. https://stoplight.io/open-source/prism

[5]

2020. About RAML. https://raml.org/about-raml

[6]

2021. Alexa - Top sites. https://www.alexa.com/topsites

[7]

2021. Browse APIs - APIs.guru. https://apis.guru/

[8]

2021. json-schema-faker/json-schema-faker. https://github.com/json-schema-faker/json-schema-faker

[9]

2021. OpenAPI Specification Version 3.0.3. https://swagger.io/specification/.

[10]

2022. https://developer.mozilla.org/en-US/docs/Web/HTML/Element/form

[11]

2022. https://developer.mozilla.org/en-US/docs/Learn/Forms/Form_validation

[12]

2022. https://apify.com/

[13]

2022. Security Through Obscurity. https://en.wikipedia.org/wiki/Security_through_obscurity

[14]

AV Aho, Monica S Lam, R Sethi, and JD Ullman. 2013. Compilers: Pearson New International Edition: Principles, Techniques, and Tools. Pearson.

[15]

Cyril Allauzen, Mehryar Mohri, and Ashish Rastogi. 2008. General Algorithms for Testing the Ambiguity of Finite Automata. In International Conference on Developments in Language Theory.

[16]

Rene Alquezar and A Sanfeliu. 1999. Incremental Grammatical Inference From Positive and Negative Data Using Unbiased Finite State Automata. (1999).

[17]

Dana Angluin. 1978. On the complexity of minimum inference of regular sets. Information and Control 39, 3 (1978), 337--350.

[18]

Vaggelis Atlidakis, Patrice Godefroid, and Marina Polishchuk. 2019. RESTler: Stateful REST API Fuzzing. In International Conf. on Software Engineering (ICSE).

[19]

Vaggelis Atlidakis, Patrice Godefroid, and Marina Polishchuk. 2020. Checking Security Properties of Cloud Service REST APIs. International Conference on Software Testing, Verification and Validation (ICST) (2020), 387--397.

[20]

Gina R. Bai, Brian Clee, Nischal Shrestha, Carl Chapman, Cimone Wright, and Kathryn T. Stolee. 2019. Exploring tools and strategies used during regular expression composition tasks. In IEEE International Conference on Program Comprehension (ICPC). IEEE.

[21]

Zhihao Bai, Ke Wang, Hang Zhu, Yinzhi Cao, and Xin Jin. 2021. Runtime Recovery of Web Applications under Zero-Day ReDoS Attacks. In IEEE Symposium on Security and Privacy (SP).

[22]

Alberto Bartoli, Giorgio Davanzo, Andrea De Lorenzo, Marco Mauri, Eric Medvet, and Enrico Sorio. 2012. Automatic generation of regular expressions from examples with genetic programming. In International Conference on Genetic and Evolutionary Computation Companion (GECCO). 1477--1478.

Digital Library

[23]

Alberto Bartoli, Andrea De Lorenzo, Eric Medvet, and Fabiano Tarlao. 2016. Inference of Regular Expressions for Text Extraction from Examples. IEEE Transactions on Knowledge and Data Engineering 28, 5 (2016), 1217--1230.

Digital Library

[24]

Daniel Bates, Adam Barth, and Collin Jackson. 2010. Regular expressions considered harmful in client-side XSS filters. In The Web Conference (WWW).

Digital Library

[25]

Jason Bau, Elie Bursztein, Divij Gupta, and John Mitchell. 2010. State of the art: Automated black-box web application vulnerability testing. In IEEE Symposium on Security and Privacy. 332--345.

Digital Library

[26]

Fabian Beck, Stefan Gulan, Benjamin Biegel, Sebastian Baltes, and Daniel Weiskopf. 2014. RegViz: Visual Debugging of Regular Expressions. In Companion Proceedings of the 36th International Conference on Software Engineering (ICSE).

Digital Library

[27]

Martin Berglund, Frank Drewes, and Brink Van Der Merwe. 2014. Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching. EPTCS: Automata and Formal Languages 2014 151 (2014), 109--123.

[28]

Martin Bidlingmaier. 2021. An Additional Non-Backtracking RegExp Engine. https://v8.dev/blog/non-backtracking-regexp

[29]

Hudson Borges and Marco Tulio Valente. 2018. What's in a GitHub Star? Understanding Repository Starring Practices in a Social Coding Platform. Journal of Systems and Software 146 (2018), 112--129. https://linkinghub.elsevier.com/retrieve/pii/S0164121218301961

[30]

Claus Brabrand and Jakob G. Thomsen. 2010. Typed and unambiguous pattern matching on strings using regular expressions. Symposium on Principles and Practice of Declarative Programming (PPDP) (2010).

[31]

Alan Cha, Erik Wittern, Guillaume Baudart, James C. Davis, Louis Mandel, and Jim A. Laredo. 2020. A Principled Approach to GraphQL Query Cost Analysis. In European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE).

[32]

Carl Chapman and Kathryn T Stolee. 2016. Exploring regular expression usage and context in Python. In International Symposium on Software Testing and Analysis (ISSTA).

Digital Library

[33]

Carl Chapman, Peipei Wang, and Kathryn T Stolee. 2017. Exploring Regular Expression Comprehension. In Automated Software Engineering (ASE).

[34]

Qiaochu Chen, Xinyu Wang, Xi Ye, Greg Durrett, and Isil Dillig. 2020. Multi-modal synthesis of regular expressions. In Programming Language Design and Implementation (PLDI). 487--502.

Digital Library

[35]

Nariyoshi Chida and Tachio Terauchi. 2020. Automatic Repair of Vulnerable Regular Expressions. (2020). http://arxiv.org/abs/2010.12450

[36]

Robert A. Cochran, Loris D'Antoni, Benjamin Livshits, David Molnar, and Margus Veanes. 2015. Program boosting: Program synthesis via crowd-sourcing. In Principles of Programming Languages (POPL), Vol. 50. 677--688.

[37]

Brendan Cody-Kenny, Michael Fenton, Adrian Ronayne, Eoghan Considine, Thomas McGuire, and Michael O'Neill. 2017. A search for improved performance in regular expressions. In Proceedings of the Genetic and Evolutionary Computation Conference. 1280--1287.

Digital Library

[38]

Melvin E Conway. 1968. How do committees invent. Datamation 14, 4 (1968).

[39]

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2009. Introduction to algorithms. MIT press.

[40]

Russ Cox. 2007. Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...).

[41]

Russ Cox. 2010. Regular Expression Matching in the Wild. https://swtch.com/~rsc/regexp/regexp3.html

[42]

Scott Crosby. 2003. Denial of service through regular expressions. In USENIX Security work in progress report.

[43]

Scott A Crosby and Dan S Wallach. 2003. Denial of Service via Algorithmic Complexity Attacks. In USENIX Security.

[44]

James C. Davis. 2020. On the Impact and Defeat of Regular Expression Denial of Service. Ph.D. Dissertation. Virginia Tech.

[45]

James C Davis, Christy A Coghlan, Francisco Servant, and Dongyoon Lee. 2018. The Impact of Regular Expression Denial of Service (ReDoS) in Practice: an Empirical Study at the Ecosystem Scale. In European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE).

Digital Library

[46]

James C. Davis, Louis G. Michael IV, Christy A. Coghlan, Francisco Servant, and Dongyoon Lee. 2019. Why aren't regular expressions a lingua franca? an empirical study on the re-use and portability of regular expressions. In The ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE).

Digital Library

[47]

James C Davis, Daniel Moyer, Ayaan M Kazerouni, and Dongyoon Lee. 2019. Testing Regex Generalizability And Its Implications: A Large-Scale Many-Language Measurement Study. In Automated Software Engineering (ASE).

[48]

James C. Davis, Francisco Servant, and Dongyoon Lee. 2021. Using Selective Memoization to Defeat Regular Expression Denial of Service (ReDoS). In IEEE Security and Privacy (S&P).

[49]

James C Davis, Eric R Williamson, and Dongyoon Lee. 2018. A Sense of Time for JavaScript and Node.js: First-Class Timeouts as a Cure for Event Handler Poisoning. In USENIX Security Symposium (USENIX Security).

Digital Library

[50]

Leonardo De Moura and Nikolaj Bjørner. 2008. Z3: An efficient SMT solver. In International conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, 337--340.

Digital Library

[51]

François Denis. 2001. Learning regular languages from simple positive examples. Machine Learning 44, 1--2 (2001), 37--66.

Digital Library

[52]

Adam Doupé, Ludovico Cavedon, Christopher Kruegel, and Giovanni Vigna. 2012. Enemy of the State: A State-Aware Black-Box Web Vulnerability Scanner. In USENIX Security. 523--538.

Digital Library

[53]

Serdar Doǧan, Aysu Betin-Can, and Vahid Garousi. 2014. Web application testing: A systematic literature review. Journal of Systems and Software 91, 1 (2014), 174--201.

Digital Library

[54]

Ian Drosos, Titus Barik, Philip J. Guo, Robert DeLine, and Sumit Gulwani. 2020. Wrex: A Unified Programming-by-Example Interaction for Synthesizing Readable Code for Data Scientists. In Computer-Human Interaction (CHI).

[55]

Fabien Duchene, Sanjay Rawat, Jean-Luc Richier, and Roland Groz. 2014. KameleonFuzz: Evolutionary Fuzzing for Black-Box XSS Detection. In ACM conference on Data and application security and privacy (CODASPY).

Digital Library

[56]

Aryaz Eghbali and Michael Pradel. 2020. No Strings Attached : An Empirical Study of String-related Software Bugs. In Automated Software Engineering (ASE).

[57]

Stack Exchange. 2016. Outage Postmortem. http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016.

[58]

Christopher Ferris and Joel Farrell. 2003. What are web services? Commun. ACM 46, 6 (2003), 31.

Digital Library

[59]

Roy T Fielding and Richard N Taylor. 2000. Principled design of the modern Web architecture. In International Conference on Software Engineering (ICSE).

Digital Library

[60]

Jeffrey EF Friedl. 2002. Mastering regular expressions. O'Reilly Media, Inc.

Digital Library

[61]

Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides, and Design Patterns. 1995. Elements of reusable object-oriented software. Addison-Wesley Reading, Massachusetts.

[62]

Patrice Godefroid, Bo Yuan Huang, and Marina Polishchuk. 2020. Intelligent REST API data fuzzing. European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) (2020).

Digital Library

[63]

E. Mark Gold. 1978. Complexity of automaton identification from given data. Information and Control 37, 3 (1978), 302--320.

[64]

Jan Goyvaerts. 2016. A list of popular tools, utilities and programming languages that provide support for regular expressions, and tips for using them. https://www.regular-expressions.info/tools.html

[65]

Graham-Cumming, John. [n.d.]. Details of the Cloudflare outage on July 2, 2019. https://web.archive.org/web/20190712160002/htttps://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/.

[66]

Renáta Hodován, Zoltán Herczeg, and Ákos Kiss. 2010. Regular expressions on the web. In International Symposium on Web Systems Evolution (WSE).

[67]

John E Hopcroft, Rajeev Motwani, and Jeffrey D Ullman. 2006. Automata theory, languages, and computation. Vol. 24. 19 pages.

[68]

John C. Knight and Nancy G. Leveson. [n.d.]. An Experimental Evaluation of the Assumption of Independence in Multiversion Programming. SE-12, 1 ([n.d.]), 96--109.

Digital Library

[69]

Eric Larson. 2018. Automatic Checking of Regular Expressions. In Source Code Analysis and Manipulation (SCAM).

[70]

Eric Larson and Anna Kirk. 2016. Generating Evil Test Strings for Regular Expressions. In International Conference on Software Testing, Verification and Validation (ICST).

[71]

Nuo Li, Tao Xie, Maozhong Jin, and Chao Liu. 2010. Perturbation-based user-input-validation testing of web applications. Journal of Systems and Software 83, 11 (2010), 2263--2274.

Digital Library

[72]

Pengui Li, Yinxi Liu, and Wei Meng. 2021. Understanding and Detecting Performance Bugs in Markdown Compilers. In IEEE/ACM International Conference on Automated Software Engineering (ASE).

[73]

Xiaowei Li and Yuan Xue. 2014. A Survey on Server-Side Approaches to Securing Web Applications. ACM Comput. Surv. 46, 4, Article 54 (March 2014), 29 pages.

Digital Library

[74]

Yunyao Li, Rajasekar Krishnamurthy, Sriram Raghavan, Shivakumar Vaithyanathan, and H. V. Jagadish. 2008. Regular expression learning for information extraction. In Conference on Empirical Methods in Natural Language Processing (EMNLP). 21--30.

[75]

Yeting Li, Shuaimin Li, Zhiwu Xu, Jialun Cao, Zixuan Chen, Yun Hu, Haiming Chen, and Shing-Chi Cheung. 2020. TransRegex: Multi-modal Regular Expression Synthesis by Generate-and-Repair. (2020). http://arxiv.org/abs/2012.15489

[76]

Yeting Li, Zhiwu Xu, Jialun Cao, Haiming Chen, Tingjian Ge, Shing-Chi Cheung, and Haoren Zhao. 2020. FlashRegex: Deducing Anti-ReDoS Regexes from Examples. In Automated Software Engineering (ASE). 659--671.

[77]

Yinxi Liu, Mingxue Zhang, and Wei Meng. [n.d.]. Revealer: Detecting and Exploiting Regular Expression Denial-of-Service Vulnerabilities. In 2021 IEEE Symposium on Security and Privacy (SP) (2021-05). IEEE.

[78]

Michael Martin and Monica S Lam. 2008. Automatic Generation of XSS and SQL Injection Attacks with Goal-Directed Model Checking. In USENIX Security.

[79]

Louis G Michael IV, James Donohue, James C Davis, Dongyoon Lee, and Francisco Servant. 2019. Regexes are Hard : Decision-making, Difficulties, and Risks in Programming Regular Expressions. In IEEE/ACM International Conference on Automated Software Engineering (ASE).

[80]

Mozilla. 2021. https://github.com/mozilla/OpenWPM

[81]

Microsoft Developer Network. 2021. HTML: HyperText Markup Language. https://developer.mozilla.org/en-US/docs/Web/HTML

[82]

Microsoft Developer Network. 2021. SPA (Single-page application). https://developer.mozilla.org/en-US/docs/Glossary/SPA

[83]

Michael Nieles, Kelley Dempsey, and Victoria Yan Pillitteri. 2017. An Introduction to Information Security. Number NIST SP 800-12r1.

[84]

Jeff Offutt, Ye Wu, Xiaochen Du, and Hong Huang. 2004. Bypass testing of web applications. Proceedings - International Symposium on Software Reliability Engineering, ISSRE (2004), 187--197.

Digital Library

[85]

Andres Ojamaa and Karl Duuna. 2012. Assessing the security of Node.js platform. In International Conference for Internet Technology and Secured Transactions.

[86]

Rong Pan, Qinheping Hu, Gaowei Xu, and Loris D'Antoni. 2019. Automatic repair of regular expressions. In Object-Oriented Programming Systems, Languages, and Applications (OOPSLA).

Digital Library

[87]

Theoolos Petsios, Jason Zhao, Angelos D Keromytis, and Suman Jana. 2017. SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities. In Computer and Communications Security (CCS).

[88]

Victor Le Pochat, Tom Van Goethem, Samaneh Tajalizadehkhoob, Maciej Korczyński, and Wouter Joosen. 2019. Tranco: A Research-Oriented Top Sites Ranking Hardened Against Manipulation. Network and Distributed System Security Symposium (NDS)) (2019). arXiv: 1806.01156.

[89]

Asiri Rathnayake and Hayo Thielecke. 2014. Static Analysis for Regular Expression Exponential Runtime via Substructural Logics. Technical Report.

[90]

Eric S. Raymond. 2000. The Cathedral and the Bazaar. Number July 1997. 1--35 pages.

[91]

Thomas Rebele, Katerina Tzompanaki, and Fabian M. Suchanek. 2018. Adding missing words to regular expressions. In Pacific-Asia Conference on Knowledge Discovery and Data Mining.

[92]

Kenneth Reitz. 2020. requests: Python HTTP for Humans. https://requests.readthedocs.io

[93]

Olli Saarikivi, Margus Veanes, Tiki Wan, and Eric Xu. 2019. Symbolic regex matcher. In Tools and Algorithms for the Construction and Analysis of Systems (TACAS).

[94]

Yuju Shen, Yanyan Jiang, Chang Xu, Ping Yu, Xiaoxing Ma, and Jian Lu. 2018. ReScue: Crafting Regular Expression DoS Attacks. In Automated Software Engineering (ASE).

[95]

Mor Sides, Anat Bremler-Barr, and Elisha Rosensweig. 2015. Yo-Yo Attack: vulnerability in auto-scaling mechanism. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. 103--104.

Digital Library

[96]

Gaurav Somani, Manoj Singh Gaur, Dheeraj Sanghi, Mauro Conti, Muttukrishnan Rajarajan, and Rajkumar Buyya. 2017. Combating DDoS attacks in the cloud: requirements, trends, and future directions. IEEE Cloud Computing (2017).

[97]

Henry Spencer. 1994. A regular-expression matcher. In Software solutions in C. 35--71.

[98]

Eric Spishak, Werner Dietl, and Michael D. Ernst. 2012. A type system for regular expressions. In Workshop on Formal Techniques for Java-like Programs.

[99]

Cristian-Alexandru Staicu and Michael Pradel. 2018. Freezing the Web: A Study of ReDoS Vulnerabilities in JavaScript-based Web Servers. In USENIX Security Symposium (USENIX Security).

Digital Library

[100]

Satoshi Sugiyama and Yasuhiko Minamide. 2014. Checking Time Linearity of Regular Expression Matching Based on Backtracking. Information and Media Technologies 9, 3 (2014), 222--232.

[101]

Martin Sulzmann and Kenny Zhuo Ming Lu. 2017. Derivative-Based Diagnosis of Regular Expression Ambiguity. International Journal of Foundations of Computer Science 28, 5 (4 2017), 543--561.

[102]

Ken Thompson. 1968. Regular Expression Search Algorithm. Communications of the ACM (CACM) (1968).

[103]

Omer Tripp, Omri Weisman, and Lotem Guy. 2013. Finding your way in the testing jungle: a learning approach to web security testing. In International Symposium on Software Testing and Analysis (ISSTA).

Digital Library

[104]

Lenka Turoňová, Lukáš Holík, Ondřej Lengál, Olli Saarikivi, Margus Veanes, and Tomáš Vojnar. 2020. Regex matching with counting-set automata. Proceedings of the ACM on Programming Languages 4, OOPSLA (2020), 1--30.

[105]

Lenka Turoňová, Lukáš Holík, Ondřej Lengál, Olli Saarikivi, Margus Veanes, and Tomáš Vojnar. 2020. Regex Matching with Counting-Set Automata. In Object-Oriented Programming Systems, Languages, and Applications (OOPSLA).

[106]

Brink van der Merwe, Jacobie Mouton, Steyn van Litsenborgh, and Martin Berglund. 2021. Memoized Regular Expressions. In International Conference on Implementation and Application of Automata. Springer, 39--52.

[107]

W3C. 2017. Accessible Rich Internet Applications (WAI-ARIA) 1.1. https://www.w3.org/TR/wai-aria

[108]

Peipei Wang, Chris Brown, Jamie A Jennings, and Kathryn T Stolee. 2020. An Empirical Study on Regular Expression Bugs. In Mining Software Repositories (MSR).

[109]

Peipei Wang and Kathryn T Stolee. 2018. How well are regular expressions tested in the wild?. In Foundations of Software Engineering (FSE).

[110]

Xiang Wang, Yang Hong, Harry Chang, KyoungSoo Park, Geoff Langdale, Jiayu Hu, and Heqing Zhu. 2019. Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs. In Networked Systems Design and Implementation (NSDI).

[111]

Nicolaas Weideman, Brink van der Merwe, Martin Berglund, and Bruce Watson. 2016. Analyzing matching time behavior of backtracking regular expression matchers by using ambiguity of NFA. In International Conference on Implementation and Application of Automata. Springer, 322--334.

[112]

Erik Wittern, Alan Cha, James C. Davis, Guillaume Baudart, and Louis Mandel. 2019. An Empirical Study of GraphQL Schemas. In International Conference on Service-Oriented Computing (ICSOC).

[113]

Erik Wittern, Philippe Suter, and Shriram Rajagopalan. 2016. A look at the dynamics of the JavaScript package ecosystem. In International Conference on Mining Software Repositories (MSR).

Digital Library

[114]

Valentin Wüstholz, Oswaldo Olivo, Marijn J H Heule, and Isil Dillig. 2017. Static Detection of DoS Vulnerabilities in Programs that use Regular Expressions. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS).

Digital Library

[115]

Tianyi Zhang, London Lowmanstone, Xinyu Wang, and Elena L Glassman. 2020. Interactive Program Synthesis by Augmented Examples. In ACM Symposium on User Interface Software and Technology (UIST).

Digital Library

Cited By

Wang ZBu DTian WCui B(2024)Analyzing and Discovering Spatial Algorithm Complexity Vulnerabilities in RecursionApplied Sciences10.3390/app1405185514:5(1855)Online publication date: 23-Feb-2024
https://doi.org/10.3390/app14051855
Siddiq MZhang JSantos JBaysal OLinares-Vasquez MMoran KSteinmacher I(2024)Understanding Regular Expression Denial of Service (ReDoS): Insights from LLM-Generated Regexes and Developer ForumsProceedings of the 32nd IEEE/ACM International Conference on Program Comprehension10.1145/3643916.3644424(190-201)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1145/3643916.3644424
Doss P LGunasekaran M(2024)Attacks and Defenses Against Poison and Evasion Attacks on COVID-19 Detection Models2024 Second International Conference on Emerging Trends in Information Technology and Engineering (ICETITE)10.1109/ic-ETITE58242.2024.10493292(1-6)Online publication date: 22-Feb-2024
https://doi.org/10.1109/ic-ETITE58242.2024.10493292
Show More Cited By

Index Terms

Exploiting input sanitization for regex denial of service
1. General and reference
  1. Cross-computing tools and techniques
2. Security and privacy
  1. Network security
    1. Denial-of-service attacks
  2. Software and application security
    1. Web application security

Recommendations

The impact of regular expression denial of service (ReDoS) in practice: an empirical study at the ecosystem scale
ESEC/FSE 2018: Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering

Regular expressions (regexes) are a popular and powerful means of automatically manipulating text. Regexes are also an understudied denial of service vector (ReDoS). If a regex has super-linear worst-case complexity, an attacker may be able to trigger ...
Mitigating denial of service attacks: a tutorial

This tutorial describes what Denial of Service (DOS) attacks are. how they can be carried out in IP networks, and how one can defend against them. Distributed DoS (DDoS) attacks are included here as a subset of DoS attacks. A DoS attack has two phases: ...
Sound static analysis of regular expressions for vulnerabilities to denial of service attacks
Abstract
Modern programming languages often provide functions to manipulate regular expressions in standard libraries. If they offer support for advanced features, the matching algorithm has an exponential worst-case time complexity: for some ...
Highlights
- A novel semantics that formalizes the behavior of regular expression matching engines.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICSE '22: Proceedings of the 44th International Conference on Software Engineering

May 2022

2508 pages

ISBN:9781450392211

DOI:10.1145/3510003

General Chair:
Matthew B Dwyer
University of Virginia
,
Program Chairs:
Daniela Damian
University of Victoria, Canada
,
Andreas Zeller
CISPA, Germany

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

In-Cooperation

IEEE CS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 July 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Conference

ICSE '22

Sponsor:

SIGSOFT

ICSE '22: 44th International Conference on Software Engineering

May 21 - 29, 2022

Pennsylvania, Pittsburgh

Acceptance Rates

Overall Acceptance Rate 276 of 1,856 submissions, 15%

Upcoming Conference

ICSE 2025

2025 IEEE/ACM 46th International Conference on Software Engineering

April 26 - May 3, 2025

Ottawa , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
442
Total Downloads

Downloads (Last 12 months)231
Downloads (Last 6 weeks)32

Reflects downloads up to 14 Aug 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang ZBu DTian WCui B(2024)Analyzing and Discovering Spatial Algorithm Complexity Vulnerabilities in RecursionApplied Sciences10.3390/app1405185514:5(1855)Online publication date: 23-Feb-2024
https://doi.org/10.3390/app14051855
Siddiq MZhang JSantos JBaysal OLinares-Vasquez MMoran KSteinmacher I(2024)Understanding Regular Expression Denial of Service (ReDoS): Insights from LLM-Generated Regexes and Developer ForumsProceedings of the 32nd IEEE/ACM International Conference on Program Comprehension10.1145/3643916.3644424(190-201)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1145/3643916.3644424
Doss P LGunasekaran M(2024)Attacks and Defenses Against Poison and Evasion Attacks on COVID-19 Detection Models2024 Second International Conference on Emerging Trends in Information Technology and Engineering (ICETITE)10.1109/ic-ETITE58242.2024.10493292(1-6)Online publication date: 22-Feb-2024
https://doi.org/10.1109/ic-ETITE58242.2024.10493292
Golmohammadi AZhang MArcuri A(2023)Testing RESTful APIs: A SurveyACM Transactions on Software Engineering and Methodology10.1145/361717533:1(1-41)Online publication date: 21-Aug-2023
https://dl.acm.org/doi/10.1145/3617175
Tandon RWang HWeideman NArakelyan SBartlett GHauser CMirkovic J(2023)Leader: Defense Against Exploit-Based Denial-of-Service Attacks on Web ApplicationsProceedings of the 26th International Symposium on Research in Attacks, Intrusions and Defenses10.1145/3607199.3607238(744-758)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3607199.3607238
Alonso JSegura SRuiz-Cortés AJust RFraser G(2023)AGORA: Automated Generation of Test Oracles for REST APIsProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598114(1018-1030)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598114
Eriksson BStjerna ADe Masellis RRüemmer PSabelfeld AMeng WJensen CCremers CKirda E(2023)Black Ostrich: Web Application Scanning with String SolversProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3616582(549-563)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3616582
Hassan SAamir ZLee DDavis JServant F(2023)Improving Developers’ Understanding of Regex Denial of Service Tools through Anti-Patterns and Fix Strategies2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179442(1238-1255)Online publication date: May-2023
https://doi.org/10.1109/SP46215.2023.10179442
Pașca EErdei RDelinschi DMatei O(2023)Overview of Machine Learning Processes Used in Improving Security in API-Based Web ApplicationsArtificial Intelligence Application in Networks and Systems10.1007/978-3-031-35314-7_33(367-381)Online publication date: 9-Jul-2023
https://doi.org/10.1007/978-3-031-35314-7_33

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents