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:

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.)

Reference

^*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.

^*4)S&P
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.