The Center for Education and Research in Information Assurance and Security (CERIAS)

The Center for Education and Research in
Information Assurance and Security (CERIAS)

Eliminating Regex-based Denial of Service

Principal Investigator: Jamie Davis

Regexes are implemented with exponential worst-case time complexity. When used for input processing, slow regexes comprise a denial of service vector. Researchers have reported that thousands of major websites are vulnerable. This project is investigating how best to discover and eliminate these vulnerabilities. We conduct empirical work to measure vulnerability incidence in practice. We propose novel algorithms with provable security guarantees. We are exploring their adoption in production-grade regex engines.

Personnel

Other PIs: Dongyoon Lee (Stony Brook University)

Students: Dharun Anandayuvaraj (PhD student) Charles Sale (Undergraduate)

Representative Publications

Keywords: application-level vulnerabilities, denial of service, regular expressions, Web security