what should the security policy of this crate be?

[BurntSushi]

On occasion, someone files a bug against this crate by following the Rust Security Policy. This is great and I am appreciative of folks being so conscientious about following our security policies.

However, treating bugs as security problems tends to be heavyweight. And some bugs reported are not obviously security problems. For example, if there's a bug in the regex crate that can result in a panic while compiling a regex or running a search, is that a security problem that should go through responsible disclosure because it could in theory cause a denial-of-service attack? What if compiling a regex could use an "unexpected" amount of resources (CPU or memory or both)? What if regex search produces a match when it shouldn't, or does not match when it should? Are these security problems?

I'll stop there. I'd like to hear thoughts from others. (I have my own opinions but want to wait for others to chime in.)

[joshtriplett]

I think it'd be reasonable for the regex crate to declare which of its guarantees are considered "security" guarantees. For instance, regex could say "using unexpectedly excessive CPU or memory is a security bug, but safely panicking is not". (I'm not proposing this as the policy, just an example.)

[BurntSushi]

Yeah, we are within our rights to choose which things are security bugs or not. But I suppose what I'm looking for is feedback on what things should be security bugs.

The "unexpectedly excessive CPU or memory" thing is tricky. Because what does "unexpected" mean? But maybe/hopefully those reports are few enough that we can have a broad policy and then make judgment calls for each one?

Unicode honestly kind of throws a wrench in things here. If you build a regex that is just within the default size limits, you can wind up with pretty slow-in-practice searches. Here's an example:

use std::time::Instant;

use regex::Regex;

fn main() {
    let hay = std::fs::read_to_string("all-codepoints-utf8").unwrap();

    let start = Instant::now();
    let re = Regex::new(r"\w{20}|\w{19}|\w{18}|\w{17}").unwrap();
    let compile_time = Instant::now().duration_since(start);

    let start = Instant::now();
    let count = re.find_iter(&hay).count();
    let search_time = Instant::now().duration_since(start);

    println!(
        "count: {count:?}, compile: {compile_time:?}, search: {search_time:?}"
    );
}

Where all-codepoints-utf8 is a file containing the UTF-8 encoding of every codepoint in sequence. (Such a strange haystack isn't necessary to get slow times, but we turn the dial up to 11 here for demonstration purposes.) On my machine, the output of the above program is:

$ time ./target/release/d994
count: 6765, compile: 18.215903ms, search: 5.388586051s

real    5.418
user    5.398
sys     0.017
maxmem  39 MB
faults  0

So that's 18ms to compile the regex and several seconds to search a <5MB corpus. And the memory used is quite big (around 20MB, right in line with the default limit). Someone might reasonably call that "unexpected" even though it doesn't violate any of the stated time complexity guarantees.

(It's possible this is an argument in favor of lowering the default limit, but that risks causing regexes to fail to compile that used to compile. So we're limited in what we can do there.)

[workingjubilee]

My experience is...

it is common for security researchers to operate by a fairly arbitrary definition of "security" that does not necessarily involve e.g. the ability to actually exploit the bug, or for the security bug to actually be a security flaw in context.

Rust programs, in general, tend to not consider "denial of service" to be a "security bug" because it is part of the language's design to, in fact, deny service instead of e.g. following another codepath that can be exploited to subvert the program and acquire the coveted "remote code execution" vuln: a true, devastating exploit if actually obtained, as it usually allows subverting all other defenses and obtaining access to all available information.

Obviously, this may be unacceptable in some situations. You do not want "denial of service" if you are the software running a pacemaker. In that context, it is not unfair to label a "denial of service" attack as a major security concern. However, this reveals the essential problem with a generic, context-free approach to security: what is acceptable and even preferred behavior in some cases is completely unacceptable in others.

Even RCEs are often only obtained in certain situations. A computer is fundamentally an engine for "remote code execution", and it is very often that the computer's actual human user wishes to cause an "RCE" vulnerability to happen, such as by double-clicking on a program to launch it... which may seem absurd as an example, but it is not uncommon for a user to then be stopped by pre-installed security measures, only to then deliberately circumvent those.

Which brings me to the last detail: some bugs, sometimes capable of causing actually horrifying vulnerabilities, have been dismissed with a simple "working as intended" due to the circumstances required being the equivalent of violating an unsafe fn's safety contract. For example, many functions in glibc could be safer to use, but instead the onus is placed on the user to correctly use them.

---

As far as I know, this crate is immune to typical "ReDoS" attacks, and that is a well-known trait of it, so I think that property should be maintained and any flaw revealing a problem in that should be considered as a serious bug ("security" or not). However, I think that otherwise any panics reached during execution should simply be documented as part of the API. If you wanted to not hit a DoS ever, you wouldn't use a crate that has panic! anywhere.

[BurntSushi]

However, I think that otherwise any panics reached during execution should simply be documented as part of the API.

Can you elaborate on this point? There are oodles of panicking branches in the regex crate, but outside of a few niche APIs that can panic for invalid offsets (like Regex::find_at), it's always a bug if any of those branches are taken. So what should the documentation say, "This routine may panic if there is a bug in the implementation"? That seems a little weird, so perhaps I am misunderstanding what you're saying here.

When one of those panics occurs, is it a security bug because it could result in a DoS?

If you wanted to not hit a DoS ever, you wouldn't use a crate that has panic! anywhere.

I think this means that your answer to my above question is "no."

A perhaps analogous example: if slice::sort() in the standard library was found to panic for a particular input, would we treat that as a security bug? The sort implementation has plenty of panicking branches, so it's possible this could happen. But there's nothing in the docs of the sort routine that suggests it can panic for any input.

As far as I know, this crate is immune to typical "ReDoS" attacks, and that is a well-known trait of it, so I think that property should be maintained and any flaw revealing a problem in that should be considered as a serious bug ("security" or not).

I think my understanding of ReDoS has evolved over the years. I would say this crate is resistant to ReDoS attacks, but possibly not immune. What this crate guarantees is a time complexity bound. But there's a lot of wiggle room there to create regexes that use a fair bit of memory and/or CPU time. It's never going to be as bad as catastrophic backtracking, but whether a regex compile/search is slow enough to cause a DoS is very context dependent.

Rust programs, in general, tend to not consider "denial of service" to be a "security bug" because it is part of the language's design to, in fact, deny service instead of e.g. following another codepath that can be exploited to subvert the program and acquire the coveted "remote code execution" vuln: a true, devastating exploit if actually obtained, as it usually allows subverting all other defenses and obtaining access to all available information.

Yes, I think this perspective is important to keep in mind.

[workingjubilee]

I would simply write code without bugs, and then I wouldn't have to worry about bugs in the implementation causing undocumented panics in the API. 😌

[BurntSushi]

So tempted to just click "mark as answer" haha.

I am doubling (or tripling) down on fuzzing. I am trying to go this route as much as I feasibly can.

[ChrisJefferson]

My personal viewpoint is the only major security issue should be incorrect matches (either positive or negative).

If someone is sanitizing data using regex (yes, that might not be the best idea, but people often do), then missed matches is a serious problem. Similarly, extra matches might be usable to corrupt data.

Undocumented panics I wouldn't personally consider a security issue, but I can understand how some people would. They are certainly (to my mind) much more minor. Seeing as it's very hard to write panic-free Rust code anyway (because memory allocation can panic), I tend to assume any code can panic.

Personally, I hate the "slow is a security problem", because there isn't a clear standard for "slow", so we end up with lots of ad-hoc attempts at defining slow.

[BurntSushi]

No, you're absolutely right 👍🏻. If we're on the bleeding edge here... we must be about 20 years away from comprehensive proofs about it. I was asking in case we weren't ^^.

I'm not aware of any literature on the correctness of any kind of regex engine. And they are quite old. So you might be waiting quite some time!

Maybe just... document it?

The time complexity is documented...

It sounds like you're saying, "anything with the time complexity bound is fair." Which is fine. I guess what I'm asking here is whether anything inside those bounds should be treated as a security bug.

[felix91gr]

So you might be waiting quite some time!

I might indeed, then 😆. I'm hyped to see what people come up with though nonetheless :)

I guess what I'm asking here is whether anything inside those bounds should be treated as a security bug.

I don't think so. From what I've studied of security at least (which is mainly cryptography), performance is only an issue for security whenever it breaks through a complexity bound.

The security concern is mostly about how the opponent scales against your own scaling.

I don't believe it's an issue whenever the haystack or the regex are provided by the user of the crate.

For the case when both come from an untrusted party, sadly, an opponent has leverage since they can force a quadratic cost by paying only linearly themselves. But that's going to be the case even for the most optimal regex engine, isn't it?

And in the sense of scaling against an attacker, as long as the crate's performance stays inside of that bound, the wall the attacker will see against their scaling is identical.

So I think it's absolutely fine. There isn't much you can do about the bound, but as long as you stay inside of it, the challenge an attacker poses will stay the same as it did before.

[BurntSushi]

From what I've studied of security at least (which is mainly cryptography), performance is only an issue for security whenever it breaks through a complexity bound.

I think this as stated would imply that ReDoS isn't ever a security problem, because backtrackers are known to have worst case exponential time complexity. I suspect you need to add more from your adversarial analysis below.

But that's going to be the case even for the most optimal regex engine, isn't it?

Probably, as far as I know. There are a lot of levers to push. For example, you can guarantee O(n) search time by building out a full DFA, but building such a DFA takes exponential time in the size of the pattern. (This is where a lot of the complexity of the regex crate comes from: giving average case O(n) search time while maintaining O(m) compile time. And of course, maintaining the worst case O(m * n) bound

[felix91gr]

I think this as stated would imply that ReDoS isn't ever a security problem, because backtrackers are known to have worst case exponential time complexity. I suspect you need to add more from your adversarial analysis below.

Ah, I think I get what you mean here. My words were ambiguous there, I apologize. There is nuance that I failed to articulate on.

I meant it this way:

• Say there is a complexity bound one wishes to achieve, that would provide secure enough scaling against an attacker.
• Say there is an algorithm which can seemingly stay within that bound in all executions. The bound is assumed to hold, and the algorithm deployed.
• Let's say now that an issue is found later in that algorithm, that provides a way to break through that bound and give it worse performance under a given set of conditions.
• Such breakage of an assumed, secure-otherwise bound, is a security issue.

A backtracker isn't secure against ReDoS there, because a polynomial bound is never assumed – we know for a fact that their bound is actually exponential.

In the case of this crate, if we can assume the time complexity is bound by n x m, and we consider that bound to be secure (or in this case, "the best known bound in the state-of-the-art" at least), only a breakage of that bound would be considered a security issue. Staying within it would be fine.

[BurntSushi]

Aye, I get what you're saying. I'm just not sure if I buy it entirely. I think the problem is that it comes down to expectations. Something like \w{100} for example has a very different space/time profile when Unicode mode is enabled (the default) versus when it is disabled. It all stays within the time bound, but the size of m in \w{100} when Unicode mode is enabled is probably about two orders of magnitude bigger than when Unicode mode is disabled.

There's nothing here that's undocumented. The crate docs talk about Unicode mode and its impact on performance. The point here is really just the unexpected cliff that Unicode mode can push you over.

I don't know if I really have a point to be honest other than to try to see this from all angles. I guess I just don't see it as simple as "here's this nice time complexity bound and that's that." Whether it rises to the level of a security bug is hard to say.

With that said, I think the time complexity bound is a decent line in the sand to draw. At least for now. And we can always revisit it later if practice demands it.

[felix91gr]

To add my two cents to this conversation:

The "unexpectedly excessive CPU or memory" thing is tricky. Because what does "unexpected" mean?

Well, the crate's description explicitly says:

This implementation uses finite automata and guarantees linear time matching on all inputs.

So I'd start by stating that any non-linear time is "unexpected".

And similarly, since the crate is using finite automata, I'd consider anything larger than constant memory (constant with regards to the text being matched) to be unexpected as well.

Does that make sense? I hope that makes sense.

[BurntSushi]

It makes sense. The problem is that this is a conservative interpretation. There is a lot that fits within those time complexity guarantees that might be unexpectedly slow.

[dfoxfranke]

I would advocate for a fairly expansive definition of what's a vulnerability, but a fairly lightweight way of dealing with them when they're reported.

For non-pathological regexes (anything someone would reasonably write), it's a vulnerability if an attacker who controls only the input can:

• Cause a crash, panic, or memory corruption.
• Cause superlinear CPU or memory usage.
• Match something that shouldn't match or not match something that should.

If the attacker controls both the regex and the input (but not anything else), it's a vulnerability if the attacker can:

• Cause a crash, panic, or memory corruption.
• Circumvent the limits passed to RegexBuilder.
• Cause CPU or memory usage in excess of O(mn).

Most of the time, though, I would recommend against any lengthy coordinated disclosure process. Just fix the bug as soon as possible and then publish the fix, stamp a release, and issue a RUSTSEC advisory all at once.

[BurntSushi]

I think the actual process is more or less dictated by the Rust project itself. I'm not sure how much say I have there. (Or, to be honest, how much say I want to have.)

[BurntSushi]

I think that "cause a panic" is probably not sufficient to rise to level of a vulnerability in any context. But I think it's also fair to add something to the docs to this crate that "this crate can have a bug that results in a panic."

[BurntSushi]

I am going to add this to the top-level crate documentation as part of the regex 1.9 release:

## Panics

Outside of clearly documented cases, most APIs in this crate are intended to
never panic regardless of the inputs given to them. For example, `Regex::new`,
`Regex::is_match`, `Regex::find` and `Regex::captures` should never panic. That
is, it is an API promise that those APIs will never panic no matter what inputs
are given to them. With that said, regex engines are complicated beasts, and
providing a rock solid guarantee that these APIs literally never panic is
essentially equivalent to saying, "there are no bugs in this library." That is
a bold claim, and not really one that can be feasibly made with a straight
face.

Don't get the wrong impression here. This crate is extensively tested, not just
with unit and integration tests, but also via fuzz testing. For example, this
crate is part of the [OSS-fuzz project]. Panics should be incredibly rare, but
it is possible for bugs to exist, and thus possible for a panic to occur. If
you need a rock solid guarantee against panics, then you should wrap calls into
this library with [`std::panic::catch_unwind`].

It's also worth pointing out that this library will generally panic when other
regex engines would commit undefined behavior. When undefined behavior occurs,
your program might continue as if nothing bad has happened, but it also might
mean your program is open to the worst kinds of exploits. In contrast, the
worst thing a panic can do is a denial of service.

[OSS-fuzz project]: https://android.googlesource.com/platform/external/oss-fuzz/+/refs/tags/android-t-preview-1/projects/rust-regex/
[`std::panic::catch_unwind`]: https://doc.rust-lang.org/std/panic/fn.catch_unwind.html

I think that's probably good enough for now. It doesn't quite answer questions about performance on its, but there will be clarifying docs on that in the top-level crate docs as well.