Rust Patches ReDoS Vulnerability

Security team from Rust has patched a bug in the regex crate that left applications open to Denial of Service attacks.

Attackers take advantage of this characteristic of a regular expression complexity to stage Regex Denial of Service (ReDoS) attacks through application features such as search pages and APIs.

Most computer languages, including Rust, have defensive measures to limit the complexity of regex strings and prevent ReDoS attacks. But the newly found bug in Rust’s regex library exhausted the server resources in ways that were not provisioned in the default defense methods.

The empty regex subexpressions with large repetitions avoided triggering any of the existing mitigations, which were oriented towards memory usage, not compilation time. Therefore, carefully crafted regexes could cause the regex compiler to attempt to generate an exponentially increasing number of empty subexpressions.

According to the Git history of the affected library, the bug existed at least since 2018, when the regex-syntax was rewritten, the severity of this vulnerability is ‘high’ when the ‘regex’ crate is used to parse untrusted regexes.

Researchers discovered the ReDoS bug while experimenting with fuzzing the cargo-fuzz crate.By generating the valid regexes by using Arbitrary to generate structured inputs, then turning it back into its string form before executing it against regex. This approach is a break from traditional fuzzing methods that generate a lot of random outputs, much of which is useless noise.

Rust developers need to use structure-aware fuzzing to discover potential memory corruption and logic bugs in their code.