(defparameter *scanner*
(ppcre:create-scanner
'(:sequence
(:register
(:greedy-repetition 1 nil :whitespace-char-class))
(:register
(:greedy-repetition 0 1 :non-whitespace-char-class)))))
(let ((length 40000))
(defparameter *no-match*
(let ((string (make-string length :initial-element #\space)))
(setf (char string (1- (length string))) #\+)
string))
(defparameter *match* (make-string length :initial-element #\space)))
(defun end-white-match (string)
(ppcre:do-scans (ms me rs re *scanner* string)
(when (and ms
(= (aref re 1) (aref rs 1)))
(return (values ms me)))))
(time (end-white-match *match*))
0, 40000
;; Evaluation took:
;; 0.000 seconds of real time
;; 0.000000 seconds of total run time (0.000000 user, 0.000000 system)
;; 100.00% CPU
;; 25,139,832 processor cycles
;; 0 bytes consed
(time (end-white-match *no-match*))
NIL
;; Evaluation took:
;; 0.000 seconds of real time
;; 0.000000 seconds of total run time (0.000000 user, 0.000000 system)
;; 100.00% CPU
;; 11,105,364 processor cycles
;; 0 bytes consedStack Overflow Outage Postmortem
101–110 of 335 posts
Re: Stack Overflow Outage Postmortem
#102Is this the sort of thing that https://github.com/google/re2 was made to solve?
Re: Stack Overflow Outage Postmortem
#103Ha! 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…
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…
Re: Stack Overflow Outage Postmortem
#104Ha! 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…
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…
At least they keep you warm. Sometimes.
How can it not be a feature that you can heat more space the more spaces you feed it?
Re: Stack Overflow Outage Postmortem
#105> 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…
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.) Assuming the OP was using this type of method, then this difference exactly explains why you can't reproduce it. I can:
>>> import re
>>> haystack = (' ' * 20000) + 'a'
>>> re.match('\s+$', haystack) >> re.search('\s+$', haystack)
indeed, this chugs a bit too: >>> re.match('.*?\s+$', haystack)
So technically, the OP left out this little detail, but it's a pretty common thing to find in regex libraries. In fact, Rust's library treats all searches as if they were re.search and provides no re.match function, instead preferring to require an explicit `^` to remove the implicit `.STAR?` prefix.Re: Stack Overflow Outage Postmortem
#106Earlier 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.
Re: Stack Overflow Outage Postmortem
#107They have limits on everything (comments per second, edits per second, upvotes per day, reputation earned per day, etc), it seems like they should have an upper bound character limit on what they accept too.
Re: Stack Overflow Outage Postmortem
#108Earlier 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…
It's a little unfair to complain that they're slower than 30 year old regex engines when the old regex engines were so feature limited that they were nearly useless.
Re: Stack Overflow Outage Postmortem
#109Nice bug. I tried to replicate this and indeed, the time to notice that no match is found is growing very fast with the length of the input. Using a substring check is a good fix, but I tried to change the regex to fix this and: if instead of an end anchor, you can add an optional non-whitespace character at the end of the pattern, then you only have to check whether the optional part is empty. Testing with very long…
Re: Stack Overflow Outage Postmortem
#110Earlier 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.