[ 
https://issues.apache.org/jira/browse/LUCENE-9981?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17354295#comment-17354295
 ] 

Dawid Weiss commented on LUCENE-9981:
-------------------------------------

Hey. Sorry, guys - I was away and didn't see the thread.  

I see you have it all figured out (thanks for the breakdown, Robert!). Indeed, 
a good catch of a very interesting code angle (and arguably an adversarial 
regexp). Reminds me of the recent flurry of reDoS scans/attacks using github 
scans for potentially vulnerable subgroups [1]. Not the same, but equally 
puzzling at first.

Anyway. Scanned the patch and it looks great to me. Caught one typo 
("Automataon") in CHANGES.txt. I like minor-optimizations like the use of fixed 
bit sets too. One thing that bugs me is the int argument's "defaults". 
Currently it just says:

bq. Set higher to allow more complex queries and lower to prevent memory 
exhaustion.

Maybe we should give some ballpark ranges of what the defaults should be here? 
Or provide constants that would make it slightly easier for folks to refer to/ 
use? 

This comment is interesting:
{code}
+      // TODO: these int sets really do not need to be sorted, and we are 
paying a high (unecessary)
+      // price for that!  really we just need a
+      // low-overhead Map<int,int> that implements equals/hash based only on 
the keys (ignores the
+      // values).  fixing this would be a big
+      // speedup for determinizing complex automata
{code}

I wonder what you had in mind, Robert? I'd have to refresh my memory of the 
original algorithm but I think the key here is that lookup based on a key 
formed of a set of transitions (ints). I see Lucene's code precalculates the 
hash of them; values are sorted to speed up set-set comparisons in equals. I 
think the assumption here is that states have a short list of outgoing 
transitions so sorting is cheap. You could probably go for a tradeoff of a more 
complex hash (long) but set-set equals is still going to be difficult to avoid 
entirely?

[1] https://en.wikipedia.org/wiki/ReDoS

> CompiledAutomaton.getCommonSuffix can be extraordinarily slow, even with 
> default maxDeterminizedStates limit
> ------------------------------------------------------------------------------------------------------------
>
>                 Key: LUCENE-9981
>                 URL: https://issues.apache.org/jira/browse/LUCENE-9981
>             Project: Lucene - Core
>          Issue Type: Task
>            Reporter: Robert Muir
>            Priority: Major
>         Attachments: LUCENE-9981.patch, LUCENE-9981.patch, LUCENE-9981.patch, 
> LUCENE-9981.patch, LUCENE-9981_nfaprefix.patch, LUCENE-9981_test.patch, 
> three-repeats-reverse-det.png, three-repeats.png
>
>
> We have a {{maxDeterminizedStates = 10000}} limit designed to keep 
> regexp-type queries from blowing up. 
> But we have an adversary that will run for 268s on my laptop before hitting 
> exception, first reported here: 
> https://github.com/opensearch-project/OpenSearch/issues/687
> When I run the test and jstack the threads, this what I see:
> {noformat}
> "TEST-TestOpensearch687.testInteresting-seed#[4B9C20A027A9850C]" #15 prio=5 
> os_prio=0 cpu=56960.04ms elapsed=57.49s tid=0x00007fff7006ca80 nid=0x231c8 
> runnable  [0x00007fff8b7f0000]
>    java.lang.Thread.State: RUNNABLE
>       at 
> org.apache.lucene.util.automaton.SortedIntSet.decr(SortedIntSet.java:106)
>       at 
> org.apache.lucene.util.automaton.Operations.determinize(Operations.java:769)
>       at 
> org.apache.lucene.util.automaton.Operations.getCommonSuffixBytesRef(Operations.java:1155)
>       at 
> org.apache.lucene.util.automaton.CompiledAutomaton.<init>(CompiledAutomaton.java:247)
>       at 
> org.apache.lucene.search.AutomatonQuery.<init>(AutomatonQuery.java:104)
>       at 
> org.apache.lucene.search.AutomatonQuery.<init>(AutomatonQuery.java:82)
>       at org.apache.lucene.search.RegexpQuery.<init>(RegexpQuery.java:138)
>       at org.apache.lucene.search.RegexpQuery.<init>(RegexpQuery.java:114)
>       at org.apache.lucene.search.RegexpQuery.<init>(RegexpQuery.java:72)
>       at org.apache.lucene.search.RegexpQuery.<init>(RegexpQuery.java:62)
>       at 
> org.apache.lucene.TestOpensearch687.testInteresting(TestOpensearch687.java:42)
> {noformat}
> This is really sad, as {{getCommonSuffixBytesRef()}} is only supposed to be 
> an "up-front" optimization to make the actual subsequent terms-intensive part 
> of the query faster. But it makes the whole query run for nearly 5 minutes 
> before it does anything.
> So I definitely think we should improve {{getCommonSuffixBytesRef}} to be 
> more "best-effort". For example, it can reduce the lower bound to {{1000}} 
> and catch the exception like such:
> {code}
> try {
>    // this is slow, and just an opto anyway, so don't burn cycles on it for 
> some crazy worst-case.
>    // if we don't set this common suffix, the query will just run a bit 
> slower, that's all.
>    int limit = Math.min(1000, maxDeterminizedStates);
>    BytesRef suffix = Operations.getCommonSuffixBytesRef(binary, limit);
>    ... (setting commonSuffixRef)
> } catch (TooComplexTooDeterminizeException notWorthIt) {
>   commonSuffixRef = null;
> }
> {code}
> Another, maybe simpler option, is to just check that input state/transitions 
> accounts don't exceed some low limit N.
> Basically this opto is geared at stuff like leading wildcard query of "*foo". 
> By computing that the common suffix is "foo" we can spend less CPU in the 
> terms dictionary because we can first do a memcmp before having to run data 
> thru any finite state machine. It's really a microopt and we shouldn't be 
> spending whole seconds of cpu on it, ever.
> But I still don't quite understand how the current limits are giving the 
> behavior today, maybe there is a bigger issue and I don't want to shove 
> something under the rug.



--
This message was sent by Atlassian Jira
(v8.3.4#803005)

---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to