You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "cfournie (via GitHub)" <gi...@apache.org> on 2023/04/27 17:03:38 UTC

[GitHub] [lucene] cfournie opened a new pull request, #12249: Fix lucene 10181

cfournie opened a new pull request, #12249:
URL: https://github.com/apache/lucene/pull/12249

   ### Description
   This PR fixes https://github.com/apache/lucene/issues/11218, where `GraphTokenStreamFiniteStrings#articulationPointsRecurse` can result in a `StackOverflowError` for very long query strings. Errors are avoided by adding an arbitrary maximum recursion depth during `articulationPointsRecurse`.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] cfournie commented on a diff in pull request #12249: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth

Posted by "cfournie (via GitHub)" <gi...@apache.org>.
cfournie commented on code in PR #12249:
URL: https://github.com/apache/lucene/pull/12249#discussion_r1226824178


##########
lucene/CHANGES.txt:
##########
@@ -80,6 +80,8 @@ Bug Fixes
 
 * GITHUB#12220: Hunspell: disallow hidden title-case entries from compound middle/end
 
+* LUCENE-10181: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth. (Chris Fournier)

Review Comment:
   Done; also rebased to pick up the latest changes in this file



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] cfournie commented on a diff in pull request #12249: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth

Posted by "cfournie (via GitHub)" <gi...@apache.org>.
cfournie commented on code in PR #12249:
URL: https://github.com/apache/lucene/pull/12249#discussion_r1179529497


##########
lucene/core/src/test/org/apache/lucene/util/graph/TestGraphTokenStreamFiniteStrings.java:
##########
@@ -660,4 +661,27 @@ public void testMultipleSidePathsWithGaps() throws Exception {
         it.next(), new String[] {"king", "alfred", "saxons", "ruled"}, new int[] {1, 1, 3, 1});
     assertFalse(it.hasNext());
   }
+
+  public void testLongTokenStreamStackOverflowError() throws Exception {
+    ArrayList<Token> tokens =
+        new ArrayList<Token>() {
+          {
+            add(token("turbo", 1, 1));
+            add(token("fast", 0, 2));
+            add(token("charged", 1, 1));
+            add(token("wi", 1, 1));
+            add(token("wifi", 0, 2));
+            add(token("fi", 1, 1));
+          }
+        };
+
+    // Add in too many tokens to get a high depth graph
+    for (int i = 0; i < 1024 * 10; i++) {

Review Comment:
   On my machine values above 8k trigger a `StackOverflowError`, but unfortunately this is JVM implementation and JVM setting dependent; if you set a higher [`-Xss`](https://docs.oracle.com/en/java/javase/11/tools/java.html#GUID-3B1CE181-CD30-4178-9602-230B800D4FAE) you could stave off this `StackOverflowError` for more tokens.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] romseygeek commented on pull request #12249: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth

Posted by "romseygeek (via GitHub)" <gi...@apache.org>.
romseygeek commented on PR #12249:
URL: https://github.com/apache/lucene/pull/12249#issuecomment-1527632254

   Thanks for opening @cfournie!  I think I'd prefer we threw a better error rather than silently dropping possible paths here?  ie, rather than `continue` throw an exception with an informative message.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] cfournie commented on pull request #12249: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth

Posted by "cfournie (via GitHub)" <gi...@apache.org>.
cfournie commented on PR #12249:
URL: https://github.com/apache/lucene/pull/12249#issuecomment-1529143322

   @romseygeek good idea 😄  I added a version where we throw a new `GraphException`; it's re-thrown as an unchecked `RuntimeException`, which I'd like to avoid. Where's a good place to catch and fail a query when this happens without a `RuntimeException`? I'll try to take a look 
   
   If this approach looks good I'll tidy it up and add in the missing javadoc, etc.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] romseygeek commented on pull request #12249: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth

Posted by "romseygeek (via GitHub)" <gi...@apache.org>.
romseygeek commented on PR #12249:
URL: https://github.com/apache/lucene/pull/12249#issuecomment-1531164211

   I think an unchecked `IllegalArgumentException` here is fine - it's a problem with the input, and that's what we throw elsewhere on bad inputs.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] cfournie commented on a diff in pull request #12249: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth

Posted by "cfournie (via GitHub)" <gi...@apache.org>.
cfournie commented on code in PR #12249:
URL: https://github.com/apache/lucene/pull/12249#discussion_r1226823890


##########
lucene/core/src/test/org/apache/lucene/util/graph/TestGraphTokenStreamFiniteStrings.java:
##########
@@ -16,6 +16,9 @@
  */
 package org.apache.lucene.util.graph;
 
+import static org.apache.lucene.util.automaton.Operations.MAX_RECURSION_LEVEL;

Review Comment:
   Removed, thanks!



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] jpountz commented on a diff in pull request #12249: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #12249:
URL: https://github.com/apache/lucene/pull/12249#discussion_r1218211772


##########
lucene/core/src/test/org/apache/lucene/util/graph/TestGraphTokenStreamFiniteStrings.java:
##########
@@ -660,4 +663,27 @@ public void testMultipleSidePathsWithGaps() throws Exception {
         it.next(), new String[] {"king", "alfred", "saxons", "ruled"}, new int[] {1, 1, 3, 1});
     assertFalse(it.hasNext());
   }
+
+  public void testLongTokenStreamStackOverflowError() throws Exception {
+
+    ArrayList<Token> tokens =
+        new ArrayList<Token>() {
+          {
+            add(token("fast", 1, 1));
+            add(token("wi", 1, 1));
+            add(token("wifi", 0, 2));
+            add(token("fi", 1, 1));
+          }
+        };
+
+    // Add in too many tokens to get a high depth graph
+    for (int i = 0; i < 1024 * 10; i++) {
+      tokens.add(token("network", 1, 1));
+    }
+
+    TokenStream ts = new CannedTokenStream(tokens.toArray(new Token[0]));
+    GraphTokenStreamFiniteStrings graph = new GraphTokenStreamFiniteStrings(ts);
+
+    assertThrows(IllegalArgumentException.class, () -> graph.articulationPoints());

Review Comment:
   nit: we prefer method refs to lambdas whenever possible
   
   ```suggestion
       assertThrows(IllegalArgumentException.class, graph::articulationPoints);
   ```



##########
lucene/core/src/test/org/apache/lucene/util/graph/TestGraphTokenStreamFiniteStrings.java:
##########
@@ -660,4 +661,27 @@ public void testMultipleSidePathsWithGaps() throws Exception {
         it.next(), new String[] {"king", "alfred", "saxons", "ruled"}, new int[] {1, 1, 3, 1});
     assertFalse(it.hasNext());
   }
+
+  public void testLongTokenStreamStackOverflowError() throws Exception {
+    ArrayList<Token> tokens =
+        new ArrayList<Token>() {
+          {
+            add(token("turbo", 1, 1));
+            add(token("fast", 0, 2));
+            add(token("charged", 1, 1));
+            add(token("wi", 1, 1));
+            add(token("wifi", 0, 2));
+            add(token("fi", 1, 1));
+          }
+        };
+
+    // Add in too many tokens to get a high depth graph
+    for (int i = 0; i < 1024 * 10; i++) {

Review Comment:
   @cfournie I think that Erik's point is that your test would not catch an issue where the exception only gets thrown with a depth of 4000 or more, so changing the number of iterations to 1024+1 would help make sure that the exception gets thrown as early as we expect. I would prefer changing the number of iterations to 1024+1 as well.



##########
lucene/CHANGES.txt:
##########
@@ -80,6 +80,8 @@ Bug Fixes
 
 * GITHUB#12220: Hunspell: disallow hidden title-case entries from compound middle/end
 
+* LUCENE-10181: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth. (Chris Fournier)

Review Comment:
   Can you move it to the 9.7 section instead of 10.0? This feels like a change that could go in a minor.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth [lucene]

Posted by "dlavant (via GitHub)" <gi...@apache.org>.
dlavant commented on PR #12249:
URL: https://github.com/apache/lucene/pull/12249#issuecomment-2008538507

   I think I ran into this issue with (Elastic 7.17 + Lucene 8.11.1).    I am aware that this version of Lucene does not have the fix.
   
   To confirm this, I tried to reproduce the StackOverflowError on-demand by feeding Elastic an absurdly long query.    But strangely, I cannot reproduce it consistently.     To be specific, I am running queries that are ~200,000 characters long, with a single word repeated over and over (i.e. "cat,cat,cat,cat....cat,cat,cat,cat").     I would expect that a query like this would trigger the StackOverflowError every time, but it doesn't.      
   
   I suspect there some fact about Lucene tokenization that I am overlooking.        Could anyone provide an example of a query *string* that would be likely to cause the StackOverflowError?     
   
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] jpountz commented on a diff in pull request #12249: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #12249:
URL: https://github.com/apache/lucene/pull/12249#discussion_r1218216466


##########
lucene/core/src/test/org/apache/lucene/util/graph/TestGraphTokenStreamFiniteStrings.java:
##########
@@ -16,6 +16,9 @@
  */
 package org.apache.lucene.util.graph;
 
+import static org.apache.lucene.util.automaton.Operations.MAX_RECURSION_LEVEL;

Review Comment:
   FYI the build complains that this import is never used.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] jpountz commented on a diff in pull request #12249: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #12249:
URL: https://github.com/apache/lucene/pull/12249#discussion_r1226846973


##########
lucene/core/src/java/org/apache/lucene/util/graph/GraphTokenStreamFiniteStrings.java:
##########
@@ -45,6 +45,8 @@
  * different paths of the {@link Automaton}.
  */
 public final class GraphTokenStreamFiniteStrings {
+  /** Maximum level of recursion allowed in recursive operations. */
+  public static final int MAX_RECURSION_LEVEL = 1000;

Review Comment:
   let's make it private?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] jpountz merged pull request #12249: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz merged PR #12249:
URL: https://github.com/apache/lucene/pull/12249


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] erikhatcher commented on a diff in pull request #12249: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth

Posted by "erikhatcher (via GitHub)" <gi...@apache.org>.
erikhatcher commented on code in PR #12249:
URL: https://github.com/apache/lucene/pull/12249#discussion_r1179514851


##########
lucene/core/src/test/org/apache/lucene/util/graph/TestGraphTokenStreamFiniteStrings.java:
##########
@@ -660,4 +661,27 @@ public void testMultipleSidePathsWithGaps() throws Exception {
         it.next(), new String[] {"king", "alfred", "saxons", "ruled"}, new int[] {1, 1, 3, 1});
     assertFalse(it.hasNext());
   }
+
+  public void testLongTokenStreamStackOverflowError() throws Exception {
+    ArrayList<Token> tokens =
+        new ArrayList<Token>() {
+          {
+            add(token("turbo", 1, 1));
+            add(token("fast", 0, 2));
+            add(token("charged", 1, 1));
+            add(token("wi", 1, 1));
+            add(token("wifi", 0, 2));
+            add(token("fi", 1, 1));
+          }
+        };
+
+    // Add in too many tokens to get a high depth graph
+    for (int i = 0; i < 1024 * 10; i++) {

Review Comment:
   would 1024 + 1 work instead of `* 10`?   Or rather, what's the minimum here needed to trigger the cutoff limit?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] erikhatcher commented on pull request #12249: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth

Posted by "erikhatcher (via GitHub)" <gi...@apache.org>.
erikhatcher commented on PR #12249:
URL: https://github.com/apache/lucene/pull/12249#issuecomment-1526104798

   Looks nice and simple and effective to me!  +1


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


[GitHub] [lucene] softwaredoug commented on pull request #12249: Restrict GraphTokenStreamFiniteStrings#articulationPointsRecurse recursion depth

Posted by "softwaredoug (via GitHub)" <gi...@apache.org>.
softwaredoug commented on PR #12249:
URL: https://github.com/apache/lucene/pull/12249#issuecomment-1526564209

   +1 if my vote counts! 
   
   I would vote for merging this to prevent crashing clusters, then if there's some galaxy brain fix, doing that later.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org