121–130 of 335 posts
It seems like there should be a way to determine whether a regex can be compiled using the classic O(n) DFA algorithm or with whatever madness PCREs use to support backtracking and so on. Anybody know if any regex engines attempt this? Obviously you can still shoot yourself in the foot, but it's somewhat more difficult to do so in a situation like this where the regex in question "looks" cheap.
Ha! The same bug happened internally at my company. In that case it was a regex matching a URL taking so much CPU as to cause a DOS of a proxy server. I won't be surprised if it's happened to someone here too. This is very timely, because minutes ago, I made a link to Russ Cox's articles in my Kernighan awk repo: https://github.com/andychu/bwk https://swtch.com/~rsc/regexp/regexp1.html If you are not familiar with th…
/* lasciate ogne speranza, voi ch'intrate. */
("Abandon all hope, you who enter here.")
Is this the sort of thing that https://github.com/google/re2 was made to solve?
Also implemented in the go stdlib https://golang.org/pkg/regexp
Earlier quoted context omitted.
The key quote here is: "Regular expressions are one of computer science's shining examples of how using good theory leads to good programs ..." "Today, regular expressions have also become a shining example of how ignoring good theory leads to bad programs. The regular expression implementations used by today's popular tools are significantly slower than the ones used in many of those thirty-year-old Unix tools." The…
FWIW, the conversion from NFA (non-deterministic, i.e. backtracking) to DFA (deterministic, linear time) can take exponential space. So there's another avenue for DDOS; it's a lot harder to exploit, though, because it requires the attacker to control the input (i.e. regular expression) to the NFA->DFA transformation, rather than merely provide a string that takes a long time for an NFA to recognize.
The problem is that the friedl O'Reilly book uses the terms NFA and DFA in a completely wrong and boneheaded way. I was confused by that book for awhile.
Earlier quoted context omitted.
Well in this case a post contained 20K whitespaces, so I wouldn't jump to the conclusion that it was a mistake rather than intentional.
I think it'd be possible to inject this kind of thing into your code if you're just starting out with vim, aren't cognisant of all commands you invoke, and then copy/paste all code straight into a browser.
Earlier quoted context omitted.
System not responsive. Look at the CPU load. Look at the process peaking at 100%. Force dump the stack track of the process couple times. Hmm. All of them stuck in the regex engine. Look back up the stack track to see who calls it. Oh, it's on the home page's text cleansing code. Something like that.
This is exactly what we did to diagnose (source: I was on the call). The only tricky part was figuring out which post it was, since it wasn't in the stacktrace. To do that, we grabbed the 3000 most recent posts and ran the regex against them. By that point we already had the code fix (another dev working on it in parallel), but if we hadn't we also could have gotten back up by just deleting the post.
If time pressure is not a factor and the production server has the VStudio or WinDbg installed, attaching the debugger to the process can see the data related to the post. But the symbol file and source files might be needed; it's just more hassle to set up. For stressful situation, simple steps and simple tools are more useful. Whatever works.
> If the string to be matched against contains 20,000 space characters in a row, but not at the end, then the Regex engine will start at the first space, check that it belongs to the \s character class, move to the second space, make the same check, etc. After the 20,000th space, there is a different character, but the Regex engine expected a space or the end of the string. Realizing it cannot match like this it back…
> If the string to be matched against contains 20,000 space characters in a row, but not at the end, then the Regex engine will start at the first space, check that it belongs to the \s character class, move to the second space, make the same check, etc. After the 20,000th space, there is a different character, but the Regex engine expected a space or the end of the string. Realizing it cannot match like this it back…
> I mean, if the engine tried matching from the second space, what would be matching the first space? Something has to. Some regex engines provide an API call that puts an implicit `.STAR?` at the beginning of the regex so that the semantics of the match are "match anywhere" as opposed to "match only from the start of the string." (This is in fact the difference between Python's `match` and `search` methods.) Assumin…
python3 -m timeit -n 1 -r 3 -s "import re ; haystack = (' ' * 20000) + 'a'" -c "re.match('\s+$', haystack)"
python3 -m timeit -n 1 -r 3 -s "import re ; haystack = (' ' * 20000) + 'a'" -c "re.search('\s+$', haystack)"
Options
-n how many times to execute statement
-r how many times to repeat the timer
-s setup code (run once)
-c command to run n times* "Audit our regular expressions and post validation workflow for any similar issues"
* ==> "Not even people who've worked for years on the guts of regex engines can easily predict the runtime of a given regex, but somehow our engineers will be expected to do that".
* "Add controls to our load balancer to disable the healthcheck – as we believe everything but the home page would have been accessible if it wasn’t for the the health check"
* ==> "Our lb check was checking /index, that failed because /index was slow: Lesson learned, let's not lb check anything at all"
Earlier quoted context omitted.
Yeah, I'm trying to figure out how you even get 20,000 spaces into a Stack Exchange post, and how it would render in your browser.
Browsers typically collapse whitespace, so it probably would render as a single space.
[0] eBay insists on something being entered and when it was a routine transaction with a vendor I seldom have anything useful to say.