Rust patches sneaky ReDoS bug

Ben Dickson 21 March 2022 at 13:12 UTC

Regex defenses restored to thwart resource consumption trap

The Rust security team has patched a bug in the regex crate that left applications open to Denial of Service (DoS) attacks.

If a regular expression string is too complex to parse, it consumes resources and slows down application servers. Attackers take advantage of this characteristic to stage Regex Denial of Service (ReDoS) attacks through application features such as search pages and APIs.

Regex compilation complexity

ReDoS attacks are well-known and -documented.

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.

“Most ReDoS is when an attacker gets control of a regex input and is able to load regexes which [will] either fill memory or take a long time to execute/compile,” Addison Crump, the security researcher who reported the bug, told The Daily Swig. “rust-lang/regex has mitigations so developers can allow for untrusted regexes and guarantee linear time complexity to prevent DoS and a maximum memory overhead.”

Crump continued: ”The inputs I discovered allowed for an exponential time complexity in the regex compilation process, which violated the safety assurances of the crate.”

According to the patch commit, 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 amount 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, according to Crump.

“The severity of this vulnerability is ‘high’ when the ‘regex’ crate is used to parse untrusted regexes,” an advisory by the Rust Security Response Workgroup states.

Structure-aware fuzzing

Crump discovered the ReDoS bug while experimenting with fuzzing the cargo-fuzz crate.

“What I did was generate only valid regexes (or, at least, only valid regex ASTs) by using Arbitrary to generate structured inputs, then turning it back into its string form before executing it against regex,” Crump explained.

This approach is a break from traditional fuzzing methods that generate a lot of random outputs, much of which is useless noise.

Catch up with the latest secure development news

“I ran the fuzzer for about 20 seconds before I started noticing odd discrepancies in execution time. I put a timeout on the fuzzer for each test case and out popped one of the regex variants which could be used to perform the DoS,” Crump said.

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

“Just because you use a language which is memory-safe, out-of-the-box doesn't mean that crashes or even corruption of data won't be introduced by not thinking through all possible cases, and fuzzing is a great way to find those cases,” Crump concluded. “Structure-aware fuzzing in particular will allow you to identify deep issues in code so that you can find extreme cases that you, as a human, would never think of.”

YOU MAY ALSO LIKE Workaround offered for unpatched HTML-to-PDF rendering vulnerability