Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Regex: badly needs fuzzing

svn.boost.org

Post reply on HN
Print view View original

31–40 of 180 posts

Re: Regex: badly needs fuzzing

#31

Post by kuschku »

AgentME wrote: post #18
revelation wrote: post #11

They seem to be fuzzing the regex, not just the input it is applied to. This may or may not change the results, but if you're allowing users to input arbitrary regex patterns you have a whole lot of other problems.

I've seen plenty of places that you may want to accept an arbitrary regex from the user. An app could allow the user to set up a filter for messages or usernames by putting in a regex. Or an interpreter for a sandboxed language could provide regex support.

Or the ignore rule in an IRC client. The input pattern of a log filter. Etc.

Re: Regex: badly needs fuzzing

#32

Post by kbenson »

revelation wrote: post #29
AgentME wrote: post #18

Earlier quoted context omitted.

I've seen plenty of places that you may want to accept an arbitrary regex from the user. An app could allow the user to set up a filter for messages or usernames by putting in a regex. Or an interpreter for a sandboxed language could provide regex support.

All manner of problems in the programmers mind become trivial if only we allow users to input essentially code to express exactly what they want. Of course this is basically never a good solution. The issue with allowing arbitrary regex patterns is DoS through exponential blowup. But if you allow running code anyway you might not very much care for that.

Assuming untrue things about the mathematical properties of your regular expression engine which are not supported by the documentation and allowing that to be exploited by user input is a different beast entirely than a bug in that library. The first, with careful examination of the properties may be preventable through sanitation of the input to exclude certain edge cases. You can't assume you'll be able to sanitize input ahead of time for bugs nobody knows about yet, which might be hidden in normally safe features.

Re: Regex: badly needs fuzzing

#35

Post by nix0n »

zao wrote: post #15
nix0n wrote: post #6

Google's cache of this bug (loads quite slowly for some reason): https://webcache.googleusercontent.com/search?q=cache:mVrrFL...

The trac instance (and legacy SVN server) isn't really designed for slashdot (well, HN) effect traffic, runs on some jiggly piece of rust at some uni somewhere.

I was commenting on the loadtime of the cached page (amalag found the solution).

Re: Regex: badly needs fuzzing

#36

Post by Houshalter »

gcp wrote: post #17
revelation wrote: post #11

They seem to be fuzzing the regex, not just the input it is applied to. This may or may not change the results, but if you're allowing users to input arbitrary regex patterns you have a whole lot of other problems.

Huh? It would be perfectly valid to have it power the regex part of the scripting engine in a browser, for example. If that would then lead to memory safety errors, you just got yourself a 0-day. Regex engines used in browsers are both fast and hardened against these attacks.

Finding vulnerabilities in existing regexes would be significantly more dangerous/interesting though. Like say if an exploit was found that could be triggered with a carefully crafted input to an email validator. Half of the servers on the web would be vulnerable! See e.g. https://en.wikipedia.org/wiki/ReDoS

If you have to be able to run an arbitrary regex on the victim's machine, that makes it much more limited. You shouldn't be letting users access regex any more than you should let them execute arbitrary code. Sure browsers do both of those things. But only through monumental effort that shouldn't be expected everywhere else.

Re: Regex: badly needs fuzzing

#37

Post by Someone1234 »

revelation wrote: post #11

They seem to be fuzzing the regex, not just the input it is applied to. This may or may not change the results, but if you're allowing users to input arbitrary regex patterns you have a whole lot of other problems.

> if you're allowing users to input arbitrary regex patterns you have a whole lot of other problems.

Why? I am legitimately asking, you say that like it is meant to be obvious or common knowledge. But many regular expression engines are self contained entities that can crash but cannot expose information or poison other parts of the program.

A DoS-like attack might be an argument against unfettered user inputed regular expressions. But that off the top of my head is the only BIG risk. Particularly in secure-by-design languages like Java, C#, and Rust.

Re: Regex: badly needs fuzzing

#39

Post by slavik81 »

stuckagain wrote: post #10
CJefferson wrote: post #7

Any rust lovers out there: Could I ask you do a benchmark comparison and a fuzz comparison. I'd be genuinely interested in the result and if (as you might hope) the Rust::regex is as fast as boost:regex, and never crashes, that would persuade at least me to finally learn some Rust!

If you were interested in performance you probably would not have been using boost::regex to begin with. RE2 is often an order of magnitude faster. You might choose boost if you require backtracking, but that's crazy anyway due to exponential time.

Is there a quick and easy way to check if a particular regex could take exponential time?

Re: Regex: badly needs fuzzing

#40

Post by carussell »

0xFFC wrote: post #20
stuckagain wrote: post #10

Earlier quoted context omitted.

If you were interested in performance you probably would not have been using boost::regex to begin with. RE2 is often an order of magnitude faster. You might choose boost if you require backtracking, but that's crazy anyway due to exponential time.

What is backtracking?

Looks like there's (a lot of) confusion in these comments about the difference between backtracking and backreferences.

The `\2` in Phritzy's snippet is a backreference.

Backtracking is an implementation strategy for writing a regular expression engine.

I don't know why anyone choosing an engine would "require backtracking". It's an implementation detail, not a feature. (Although the fact that Thompson NFAs avoid exponential time complexity inherent to backtracking is something that I suppose could be considered a feature.)

Here's a link to some real literature:

https://swtch.com/~rsc/regexp/regexp1.html

Post reply on HN