[5/5]
And as a bonus, here is a DOS attack on irregex. The (+) branch of sre->procedure is:
((+)
(cond
((sre-empty? (sre-sequence (cdr sre)))
(error "invalid sre: empty +" sre))
(else
(letrec
((body
(lp (sre-sequence (cdr sre))
n
flags
(lambda (cnk init src str i end matches fail)
(body cnk init src str i end matches
(lambda ()
(next cnk init src str i end matches fail)
))))))
body))))It unconditionally loops its subexpression and only concedes when that fails. It does not even give one neutrino that the input might be exhausted. Protection from being passed a null matcher is provided by the sre-empty? test. Sre-empty? looks like this:
;; returns #t if the sre can ever be empty
(define (sre-empty? sre)
(if (pair? sre)
(case (car sre)
((* ? look-ahead look-behind neg-look-ahead neg-look-behind) #t)
((**) (or (not (number? (cadr sre))) (zero? (cadr sre))))
((or) (any sre-empty? (cdr sre)))
((: seq $ submatch => submatch-named + atomic)
(every sre-empty? (cdr sre)))
(else #f))
(memq sre '(epsilon bos eos bol eol bow eow commit))))It handles pairs and symbols. Irregex represents string atoms with raw strings, so that we can write '(or "a" "b") instead of having to write something like '(or (s "a") (s "b")). This means that strings can be SREs and they have their own branch in sre->procedure, it is the (string? sre) branch that we patched above for debug prints. But sre-empty? returns #f for everything it doesn't care about, and it doesn't care about strings. Naturally, this is an invitation to pass the empty string to (+) via SREs, e.g.:
scheme@(guile-user)> (sre-empty? '(or "aa" ""))
$1 = #f
scheme@(guile-user)> (imsis '(** 1 1 (+ (or "aa" ""))) "aaaa")This will keep one of your CPU cores on 100% for a while. According to git blame, this sre-empty? is from the same commit by ashinn as the backtracking. In light of the comment above the procedure, "can ever be empty", here is how complicated the fix is: you have to consider the possibility that the empty string might sometimes be empty. Until you do, this is an easy DOS where SREs are directly accepted. The PCRE equivalent is:
scheme@(guile-user)> (imsis "(aa|){1,}" "aaaa")which will also spin up your fans, and uses the fact that the author thought it was perfectly reasonable to add null matcher protection to * and + but not to upper unbounded ranges, neither in string->sre nor in sre->procedure. As I have already asked in >>91 perhaps somebody could bring the shinnoid up to speed.
And now you can have your thread back. I'm done with this irregex thing.