Live data from Hacker News

Stack Overflow Outage Postmortem

stackstatus.net

101–110 of 335 posts

Re: Stack Overflow Outage Postmortem

#101
Nice 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 strings which respectively match and don't match shows that the result is immediate in both cases.

    (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 consed

Re: Stack Overflow Outage Postmortem

#103
post #78
post #9

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…

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

#104
post #78
post #9

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…

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…

So you have the classic NFA and DFA engines, and these more modern NSH (non-deterministic space heater) engines.

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
post #70

> 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.) 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

#106
post #78

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.

I'm actually not aware of any popular DFA based engines that suffer from this vulnerability. grep and RE2, for example, build the DFA lazily and cap the size of the DFA such that matching is still linear time even if generating the full DFA would take exponential space. (This is because at most one DFA state is generated for each byte in the input, so technically, you only ever need space for one or two states. In practice, you give a little more room to avoid constantly recomputing states, but it's still bounded.)

Re: Stack Overflow Outage Postmortem

#107
post #64

They 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.

There are some very long Stack Overflow answers that contain a wealth of information. If there were a limit, it would likely need to be far greater than 20k characters anyway (the number of whitespace characters that caused the outage).

Re: Stack Overflow Outage Postmortem

#108
post #78

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…

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.

[deleted]

Re: Stack Overflow Outage Postmortem

#109
post #101

Nice 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…

So, you're saying that if you enjoy tricky gotchas and puzzle-solving over reliability, then the perl-aping regex implementations have your back?

Re: Stack Overflow Outage Postmortem

#110
post #78

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.

[deleted]
Post reply on HN