Microsoft ends support for Internet Explorer on June 16, 2022.
We recommend using one of the browsers listed below.

  • Microsoft Edge(Latest version) 
  • Mozilla Firefox(Latest version) 
  • Google Chrome(Latest version) 
  • Apple Safari(Latest version) 

Please contact your browser provider for download and installation instructions.

Open search panel Close search panel Open menu Close menu

March 23, 2022

NTT Corporation
Waseda University

NTT and Waseda University develop novel technology for automatically repairing vulnerability of pattern matching function

NIPPON TELEGRAPH AND TELEPHONE CORPORATION (Head Office: Chiyoda-ku, Tokyo; Jun Sawada, President & CEO;"NTT ") and Waseda University (Headquarters: Shinjuku-ku, Tokyo, President: Aiji Tanaka) have developed practical novel technology for automatically repairing a vulnerability that makes web applications slow down or crash, in the worst case, by exploiting the behavior of pattern matching engines. Regular expressions (*1) are patterns used to match character combinations in strings and used for a wide variety of web services to sanitize user inputs, extract data, etc. Regular expression denialofservice vulnerability has become a major global threat in recent years. This technology allows developers to repair these vulnerabilities without the expertise of regular expressions and helps to provide secure services.

1. Background

There is no end to cyber attacks that exploit software vulnerabilities, and large damages are reported all over the world. A vulnerability is a security flaw caused by a program flaw or design error. In particular, ReDoS vulnerability (*2) is a vulnerability that consumes computational resources and causes a denial of service by providing input that increases processing time to a function that performs pattern matching on strings using regular expressions.
 Regular expressions are provided as a standard library in many modern programming languages for providing a functionality of string manipulations and are widely used in a variety of software and services. For example, regular expressions are used for validating the format of email addresses and phone numbers. Commercial service outages due to the ReDoS vulnerability have occurred frequently over the past few years and have gained global attention as a major threat.

2. Achievement

Regular expressions have their origins in formal language theory. However, regular expressions used in real-world software are different from the original one since they are extended by adding new operators for handling real-world issues. Such extended regular expressions are distinguished from the original one as real-world regular expressions (*3). Until now, there has been no technology that automatically repairs the ReDoS vulnerability of real-world regular expressions.
 In this project, we achieved the world's first technology for automatically repairing the ReDoS vulnerability by giving the first formal definition of the ReDoS vulnerability, sufficient condition for ensuring the ReDoS invulnerability, the repair problem, and the algorithm for solving the repair problem.
 NTT developed the method for repairing the ReDoS vulnerability of real-world regular expressions, and Professor Tachio Terauchi (Faculty of Science and Engineering, Waseda University) verified the theoretical correctness of the method developed by NTT.
 The paper that introduces this achievement has been accepted to the IEEE S&P 2022 (43rd IEEE Symposium on Security and Privacy) (*4), the most challenging international conference in the field of security and privacy. Since 1980, IEEE S&P has been a top-level international conference in the field of security and privacy, with the low acceptance rate of about 12%.

3. Technology

The key points of this technology are as follows:

(1) The formal definition of ReDoS vulnerability of real-world regular expressions, the repair problem, and its algorithm. Our repair algorithm uses the "Programming by Example (PBE)" method (*5) to repair ReDoS vulnerability. PBE method automatically generates a program that satisfies the condition represented by input and output examples of the program that the user wants. In our case, it enables the users to repair the ReDoS vulnerability by only providing examples of strings that the regular expression user wants and should accept (positive examples) and reject (negative examples).
(2) The condition for ensuring ReDoS invulnerability based on the formal definition (1). The condition requires to disambiguate a regular expression and remove backtrackings, which cause the ReDoS vulnerability, from the pattern matching of the regular expression. Our repair algorithm guarantees that the repaired regular expression is invulnerable to ReDoS vulnerability by enforcing that the regular expression satisfies the condition.
 This method verifies whether a program satisfies a formal specification and proves the correctness of the program by the specification. Such a method is called "formal verification (*6)". While the correctness shown by the conventional verification by test cases is limited, the formal verification is comprehensive. It will help the users to develop secure software.

About the announcement

This result will be presented at IEEE S&P 2022 (43rd IEEE Symposium on Security and Privacy), one of the most prestigious international conferences in the field of security and privacy, to be held from May 22 to 26, 2022, with the following titles and authors. (* The author's affiliation is currently NTT Social Informatics Laboratories.)

Title: Repairing DoS Vulnerability of Real-World Regexes
Authors: Nariyoshi Chida (NTT Secure Platform Laboratories *), Tachio Terauchi (Waseda University)

<Inquiries regarding this press release>

Nippon Telegraph and Telephone Corporation
Service Innovation Laboratory Group
Public Relations

Waseda University
Office of Information & Public Relations


*1)Regular expressions
Method used to match character combinations in strings.

*2)ReDoS Vulnerability
ReDoS stands for Regular Expression Denial of Service, and refers to vulnerabilities in regular expressions that make the running time of regular expression engines slow down by consuming computational resources and cause service outages.

*3)Real-world regular expressions
Extended regular expressions used in real-world software. Their theoretical properties are different from pure regular expressions that are well known in formal language theory since they have non-regular operators such as backreferences.

IEEE Symposium on Security and Privacy; a 1st-tier conference in the field of security and privacywhere the most advanced security countermeasure technology is presented.

*5)Programming by Examples (PBE) method
The method that enables the users who do not have programming knowledge to write programs. This method automatically generates programs that satisfy the condition represented by input/output examples.

*6)Formal Verification
The method that verifies the correctness of a program by a formal specification and helps the users to develop reliable software.

Information is current as of the date of issue of the individual press release.
Please be advised that information may be outdated after that point.