This is an automated email from the ASF dual-hosted git repository.

quantranhong1999 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/james-jsieve.git


The following commit(s) were added to refs/heads/master by this push:
     new 4bf3a6b  [FIX] SieveFactory: bound the comparisons of an evaluation
4bf3a6b is described below

commit 4bf3a6bd2cc2e24b38470242dcadcac4da45d9a9
Author: Benoit TELLIER <[email protected]>
AuthorDate: Thu Nov 12 08:44:43 2026 +0100

    [FIX] SieveFactory: bound the comparisons of an evaluation
    
    :matches and :contains are O(text length x key length), and nothing
    capped the number nor the size of the comparisons of an evaluation: a
    script with long keys against a large mail kept the evaluating thread
    busy for minutes to hours.
    
    Each comparison now charges the evaluation with the characters it
    compares, and an evaluation beyond the budget fails with a
    SieveException. :is and :contains are charged the length of their
    values: :contains now searches with Knuth-Morris-Pratt, linear whatever
    the values, instead of String#indexOf, quadratic at worst. :matches is
    charged the steps its matcher really takes, as it runs, so that an
    ordinary glob on a large header costs about its length while a
    pathological one stops once the budget is spent. A comparator outside
    jSieve, whose cost is unknown, is charged the product of the lengths
    before running, unless it overrides Contains#contains or
    Matches#matches taking a SieveContext.
    
    The budget is SieveFactory.DEFAULT_COMPARISON_BUDGET (10^10, seconds of
    work) and can be set with ConfigurationManager::setComparisonBudget. A
    SieveContext built without budget is not limited.
---
 .../java/org/apache/jsieve/BaseSieveContext.java   |  31 ++++
 .../org/apache/jsieve/ConfigurationManager.java    |  18 ++-
 .../main/java/org/apache/jsieve/SieveContext.java  |  13 ++
 .../main/java/org/apache/jsieve/SieveFactory.java  |  31 +++-
 .../apache/jsieve/comparators/AsciiCasemap.java    |  24 +++
 .../apache/jsieve/comparators/ComparatorUtils.java | 126 +++++++++++++--
 .../org/apache/jsieve/comparators/Contains.java    |  22 +++
 .../org/apache/jsieve/comparators/Matches.java     |  21 +++
 .../java/org/apache/jsieve/comparators/Octet.java  |  23 +++
 .../org/apache/jsieve/EvaluationBudgetTest.java    | 180 +++++++++++++++++++++
 .../jsieve/comparator/ComparatorUtilsTest.java     |  30 ++++
 11 files changed, 506 insertions(+), 13 deletions(-)

diff --git a/core/src/main/java/org/apache/jsieve/BaseSieveContext.java 
b/core/src/main/java/org/apache/jsieve/BaseSieveContext.java
index e66afb7..566ac2c 100644
--- a/core/src/main/java/org/apache/jsieve/BaseSieveContext.java
+++ b/core/src/main/java/org/apache/jsieve/BaseSieveContext.java
@@ -19,6 +19,8 @@
 
 package org.apache.jsieve;
 
+import org.apache.jsieve.exception.SieveException;
+
 /**
  * Bean based implementation of context.
  */
@@ -36,9 +38,26 @@ public class BaseSieveContext extends SieveContext {
 
     private final TestManager testManager;
 
+    private long remainingComparisonBudget;
+
     public BaseSieveContext(final CommandManager commandManager,
                             final ComparatorManager comparatorManager,
                             final TestManager testManager) {
+        this(commandManager, comparatorManager, testManager, Long.MAX_VALUE);
+    }
+
+    /**
+     * @param comparisonBudget the number of characters the comparisons of an
+     * evaluation may compare, see {@link #chargeComparison(long)}
+     */
+    public BaseSieveContext(final CommandManager commandManager,
+                            final ComparatorManager comparatorManager,
+                            final TestManager testManager,
+                            final long comparisonBudget) {
+        if (comparisonBudget < 0) {
+            throw new IllegalArgumentException("The comparison budget cannot 
be negative");
+        }
+        this.remainingComparisonBudget = comparisonBudget;
         this.commandStateManager = new CommandStateManager();
         this.conditionManager = new ConditionManager();
         this.testManager = testManager;
@@ -113,4 +132,16 @@ public class BaseSieveContext extends SieveContext {
     public TestManager getTestManager() {
         return testManager;
     }
+
+    /**
+     * @see SieveContext#chargeComparison(long)
+     */
+    @Override
+    public void chargeComparison(long cost) throws SieveException {
+        if (cost > remainingComparisonBudget) {
+            remainingComparisonBudget = 0;
+            throw new SieveException("Evaluation budget exceeded: the script 
compares too much content");
+        }
+        remainingComparisonBudget -= cost;
+    }
 }
diff --git a/core/src/main/java/org/apache/jsieve/ConfigurationManager.java 
b/core/src/main/java/org/apache/jsieve/ConfigurationManager.java
index a4031eb..3389c1b 100644
--- a/core/src/main/java/org/apache/jsieve/ConfigurationManager.java
+++ b/core/src/main/java/org/apache/jsieve/ConfigurationManager.java
@@ -97,6 +97,8 @@ public class ConfigurationManager {
      */
     private int initialConcurrencyLevel = DEFAULT_INITIAL_CONCURRENCY_LEVEL;
 
+    private long comparisonBudget = SieveFactory.DEFAULT_COMPARISON_BUDGET;
+
     private static final Logger LOGGER = 
LoggerFactory.getLogger(ConfigurationManager.class);
 
     /**
@@ -280,8 +282,22 @@ public class ConfigurationManager {
         return new TestManagerImpl(fieldTestMap);
     }
 
+    /**
+     * Sets the number of characters the comparisons of a single evaluation
+     * may compare, {@link SieveFactory#DEFAULT_COMPARISON_BUDGET}
+     * by default.
+     *
+     * @param comparisonBudget not negative
+     */
+    public void setComparisonBudget(long comparisonBudget) {
+        if (comparisonBudget < 0) {
+            throw new IllegalArgumentException("The comparison budget cannot 
be negative");
+        }
+        this.comparisonBudget = comparisonBudget;
+    }
+
     public SieveFactory build() {
         return new SieveFactory(getCommandManager(), getComparatorManager(),
-                getTestManager());
+                getTestManager(), comparisonBudget);
     }
 }
diff --git a/core/src/main/java/org/apache/jsieve/SieveContext.java 
b/core/src/main/java/org/apache/jsieve/SieveContext.java
index 4e8afdd..3d4ffe1 100644
--- a/core/src/main/java/org/apache/jsieve/SieveContext.java
+++ b/core/src/main/java/org/apache/jsieve/SieveContext.java
@@ -19,6 +19,8 @@
 
 package org.apache.jsieve;
 
+import org.apache.jsieve.exception.SieveException;
+
 /**
  * Context for sieve operations.
  * 
@@ -75,4 +77,15 @@ public abstract class SieveContext {
      * @return test manager, not null
      */
     public abstract TestManager getTestManager();
+
+    /**
+     * Charges the evaluation budget with a comparison of the given cost,
+     * in characters compared.
+     * By default, evaluation is not limited.
+     *
+     * @param cost not negative
+     * @throws SieveException when the budget is exhausted
+     */
+    public void chargeComparison(long cost) throws SieveException {
+    }
 }
diff --git a/core/src/main/java/org/apache/jsieve/SieveFactory.java 
b/core/src/main/java/org/apache/jsieve/SieveFactory.java
index f16adee..f38e07f 100644
--- a/core/src/main/java/org/apache/jsieve/SieveFactory.java
+++ b/core/src/main/java/org/apache/jsieve/SieveFactory.java
@@ -76,15 +76,42 @@ public class SieveFactory {
     private final TestManager testManager;
 
     /**
-     * Constructor for SieveFactory.
+     * Default number of characters the comparisons of a single evaluation may
+     * compare: seconds of work.
+     */
+    public static final long DEFAULT_COMPARISON_BUDGET = 10_000_000_000L;
+
+    private final long comparisonBudget;
+
+    /**
+     * Constructor for SieveFactory, using the
+     * {@link #DEFAULT_COMPARISON_BUDGET}.
      */
     public SieveFactory(final CommandManager commandManager,
             final ComparatorManager comparatorManager,
             final TestManager testManager) {
+        this(commandManager, comparatorManager, testManager, 
DEFAULT_COMPARISON_BUDGET);
+    }
+
+    /**
+     * Constructor for SieveFactory.
+     *
+     * @param comparisonBudget the number of characters the comparisons of a
+     * single evaluation may compare. An evaluation going beyond fails
+     * with a {@link SieveException}.
+     */
+    public SieveFactory(final CommandManager commandManager,
+            final ComparatorManager comparatorManager,
+            final TestManager testManager,
+            final long comparisonBudget) {
         super();
+        if (comparisonBudget < 0) {
+            throw new IllegalArgumentException("The comparison budget cannot 
be negative");
+        }
         this.commandManager = commandManager;
         this.comparatorManager = comparatorManager;
         this.testManager = testManager;
+        this.comparisonBudget = comparisonBudget;
     }
 
     /**
@@ -147,7 +174,7 @@ public class SieveFactory {
     public void evaluate(MailAdapter mail, Node startNode)
             throws SieveException {
         final SieveContext context = new BaseSieveContext(commandManager,
-                comparatorManager, testManager);
+                comparatorManager, testManager, comparisonBudget);
         try {
             // Ensure that the context is set on the mail
             mail.setContext(context);
diff --git a/core/src/main/java/org/apache/jsieve/comparators/AsciiCasemap.java 
b/core/src/main/java/org/apache/jsieve/comparators/AsciiCasemap.java
index 81d4825..18dc36b 100644
--- a/core/src/main/java/org/apache/jsieve/comparators/AsciiCasemap.java
+++ b/core/src/main/java/org/apache/jsieve/comparators/AsciiCasemap.java
@@ -19,6 +19,8 @@
 
 package org.apache.jsieve.comparators;
 
+import org.apache.jsieve.SieveContext;
+import org.apache.jsieve.exception.SieveException;
 import org.apache.jsieve.exception.SievePatternException;
 
 /**
@@ -61,6 +63,28 @@ public class AsciiCasemap implements Comparator {
                 toAsciiUpperCase(glob));
     }
 
+    /**
+     * The search being linear, charges the lengths.
+     * @see org.apache.jsieve.comparators.Contains#contains(String, String, 
SieveContext)
+     */
+    @Override
+    public boolean contains(String container, String content, SieveContext 
context)
+            throws SieveException {
+        context.chargeComparison(ComparatorUtils.linearCost(container, 
content));
+        return contains(container, content);
+    }
+
+    /**
+     * Charges the steps the matcher takes.
+     * @see org.apache.jsieve.comparators.Matches#matches(String, String, 
SieveContext)
+     */
+    @Override
+    public boolean matches(String string, String glob, SieveContext context)
+            throws SieveException {
+        return ComparatorUtils.matches(toAsciiUpperCase(string),
+                toAsciiUpperCase(glob), context);
+    }
+
     /**
      * Maps a-z onto A-Z and leaves every other character untouched, as
      * defined by RFC 4790 section 9.2. Unlike {@link String#toUpperCase()},
diff --git 
a/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java 
b/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java
index da41127..77759f4 100644
--- a/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java
+++ b/core/src/main/java/org/apache/jsieve/comparators/ComparatorUtils.java
@@ -75,8 +75,10 @@ public class ComparatorUtils {
             String matchTarget, String matchArgument, SieveContext context)
             throws SieveException {
         boolean isMatched = false;
-        if (matchType.equals(IS_TAG))
+        if (matchType.equals(IS_TAG)) {
+            context.chargeComparison(linearCost(matchTarget, matchArgument));
             isMatched = is(comparatorName, matchTarget, matchArgument, 
context);
+        }
         else if (matchType.equals(CONTAINS_TAG))
             isMatched = contains(comparatorName, matchTarget, matchArgument,
                     context);
@@ -86,6 +88,31 @@ public class ComparatorUtils {
         return isMatched;
     }
 
+    /**
+     * Cost, in characters compared, of a comparison linear in the length of
+     * its values, such as <code>:is</code> or {@link #contains(String, 
String)}.
+     */
+    static long linearCost(String first, String second) {
+        return first.length() + 1L + second.length() + 1L;
+    }
+
+    /**
+     * Cost, in characters compared, of a comparison quadratic in the length
+     * of its values: the worst case of a naive substring search or of a glob
+     * matcher.
+     */
+    static long quadraticCost(String first, String second) {
+        // Lengths are below 2^31: the product cannot overflow
+        return (first.length() + 1L) * (second.length() + 1L);
+    }
+
+    /**
+     * Number of steps of the glob matcher charged to the evaluation budget at
+     * once: the budget is checked as the matcher runs, without charging it
+     * at each step.
+     */
+    private static final int STEPS_CHARGED_AT_ONCE = 1 << 16;
+
     /**
      * <p>
      * Method <code>matches</code> answers a boolean indicating if the
@@ -107,6 +134,31 @@ public class ComparatorUtils {
      */
     static public boolean matches(String string, String glob)
             throws SievePatternException {
+        try {
+            return matches(string, glob, null);
+        } catch (SieveException e) {
+            // Not reached: nothing is charged without context
+            throw new IllegalStateException(e);
+        }
+    }
+
+    /**
+     * Same as {@link #matches(String, String)}, charging the evaluation
+     * budget of the context with the steps the matcher really takes, so that
+     * a pathological glob fails once the budget is exhausted while an
+     * ordinary one on a large value is charged little more than its length.
+     *
+     * @param string not null
+     * @param glob not null
+     * @param context charged with the steps taken, nothing charged when null
+     * @return boolean
+     * @throws SieveException when the budget is exhausted
+     */
+    static public boolean matches(String string, String glob, SieveContext 
context)
+            throws SieveException {
+        if (context != null) {
+            context.chargeComparison(linearCost(string, glob));
+        }
         final int[] pattern = compileGlob(glob);
         final int[] target = string.codePoints().toArray();
 
@@ -116,7 +168,14 @@ public class ComparatorUtils {
         int afterStar = -1;
         // Position in the target the last star is currently matched up to
         int starMatchEnd = 0;
+        // Steps taken and not charged yet
+        int uncharged = 0;
+        boolean mismatch = false;
         while (t < target.length) {
+            if (context != null && ++uncharged == STEPS_CHARGED_AT_ONCE) {
+                context.chargeComparison(uncharged);
+                uncharged = 0;
+            }
             if (p < pattern.length && pattern[p] == GLOB_STAR) {
                 afterStar = ++p;
                 starMatchEnd = t;
@@ -130,9 +189,16 @@ public class ComparatorUtils {
                 p = afterStar;
                 t = ++starMatchEnd;
             } else {
-                return false;
+                mismatch = true;
+                break;
             }
         }
+        if (context != null) {
+            context.chargeComparison(uncharged);
+        }
+        if (mismatch) {
+            return false;
+        }
         while (p < pattern.length && pattern[p] == GLOB_STAR) {
             p++;
         }
@@ -181,23 +247,63 @@ public class ComparatorUtils {
      * Like <code>:matches</code>, it compares characters (RFC 5228 section
      * 2.7.1): a match never starts or ends inside a surrogate pair.
      * </p>
+     * <p>
+     * The search is linear (Knuth-Morris-Pratt): it compares at most
+     * <code>2 * container length + contents length</code> characters,
+     * whatever the values.
+     * </p>
      *
      * @param container
      * @param contents
      * @return boolean
      */
     static public boolean contains(String container, String contents) {
-        int index = container.indexOf(contents);
-        while (index >= 0) {
-            if (!splitsSurrogatePair(container, index)
-                    && !splitsSurrogatePair(container, index + 
contents.length())) {
-                return true;
+        final int length = contents.length();
+        if (length == 0) {
+            return true;
+        }
+        final int[] border = borders(contents);
+        // Number of characters of contents matched so far
+        int matched = 0;
+        for (int i = 0; i < container.length(); i++) {
+            final char c = container.charAt(i);
+            while (matched > 0 && contents.charAt(matched) != c) {
+                matched = border[matched - 1];
+            }
+            if (contents.charAt(matched) == c) {
+                matched++;
+            }
+            if (matched == length) {
+                final int end = i + 1;
+                if (!splitsSurrogatePair(container, end - length)
+                        && !splitsSurrogatePair(container, end)) {
+                    return true;
+                }
+                matched = border[matched - 1];
             }
-            index = container.indexOf(contents, index + 1);
         }
         return false;
     }
 
+    /**
+     * Knuth-Morris-Pratt failure function: for each prefix of the string,
+     * the length of its longest proper prefix that is also a suffix.
+     */
+    private static int[] borders(String string) {
+        final int[] border = new int[string.length()];
+        int length = 0;
+        for (int i = 1; i < string.length(); i++) {
+            while (length > 0 && string.charAt(i) != string.charAt(length)) {
+                length = border[length - 1];
+            }
+            if (string.charAt(i) == string.charAt(length)) {
+                length++;
+            }
+            border[i] = length;
+        }
+        return border;
+    }
+
     private static boolean splitsSurrogatePair(String string, int index) {
         return index > 0 && index < string.length()
                 && Character.isHighSurrogate(string.charAt(index - 1))
@@ -232,7 +338,7 @@ public class ComparatorUtils {
     public static boolean contains(String comparatorName, String container,
             String contents, SieveContext context) throws SieveException {
         Contains comparatorObj = 
context.getComparatorManager().getComparator(comparatorName);
-        return comparatorObj.contains(container, contents);
+        return comparatorObj.contains(container, contents, context);
     }
 
     /**
@@ -265,7 +371,7 @@ public class ComparatorUtils {
     public static boolean matches(String comparatorName, String string,
             String glob, SieveContext context) throws SieveException {
         Matches comparatorObj = 
context.getComparatorManager().getComparator(comparatorName);
-        return comparatorObj.matches(string, glob);
+        return comparatorObj.matches(string, glob, context);
     }
 
 }
diff --git a/core/src/main/java/org/apache/jsieve/comparators/Contains.java 
b/core/src/main/java/org/apache/jsieve/comparators/Contains.java
index 7d82728..f4a126a 100644
--- a/core/src/main/java/org/apache/jsieve/comparators/Contains.java
+++ b/core/src/main/java/org/apache/jsieve/comparators/Contains.java
@@ -19,7 +19,9 @@
 
 package org.apache.jsieve.comparators;
 
+import org.apache.jsieve.SieveContext;
 import org.apache.jsieve.exception.FeatureException;
+import org.apache.jsieve.exception.SieveException;
 
 
 /**
@@ -39,4 +41,24 @@ public interface Contains {
      */
     public boolean contains(String container, String content) throws 
FeatureException;
 
+    /**
+     * Same as {@link #contains(String, String)}, charging the evaluation
+     * budget of the context with the characters compared. Its cost being
+     * unknown, an implementation that does not override this method is
+     * charged the worst case of a naive search before running: the product of
+     * the lengths.
+     *
+     * @param container not null
+     * @param content not null
+     * @param context not null
+     * @return boolean
+     * @throws SieveException when substring is unsupported or the budget is
+     * exhausted
+     */
+    default boolean contains(String container, String content, SieveContext 
context)
+            throws SieveException {
+        context.chargeComparison(ComparatorUtils.quadraticCost(container, 
content));
+        return contains(container, content);
+    }
+
 }
diff --git a/core/src/main/java/org/apache/jsieve/comparators/Matches.java 
b/core/src/main/java/org/apache/jsieve/comparators/Matches.java
index 63cd6fa..fd9eb23 100644
--- a/core/src/main/java/org/apache/jsieve/comparators/Matches.java
+++ b/core/src/main/java/org/apache/jsieve/comparators/Matches.java
@@ -19,6 +19,7 @@
 
 package org.apache.jsieve.comparators;
 
+import org.apache.jsieve.SieveContext;
 import org.apache.jsieve.exception.SieveException;
 
 /**
@@ -36,4 +37,24 @@ public interface Matches {
      */
     public boolean matches(String string, String glob) throws SieveException;
 
+    /**
+     * Same as {@link #matches(String, String)}, charging the evaluation
+     * budget of the context with the characters compared. Its cost being
+     * unknown, an implementation that does not override this method is
+     * charged the worst case of a glob matcher before running: the product of
+     * the lengths.
+     *
+     * @param string not null
+     * @param glob not null
+     * @param context not null
+     * @return boolean
+     * @throws SieveException when the glob is invalid or the budget is
+     * exhausted
+     */
+    default boolean matches(String string, String glob, SieveContext context)
+            throws SieveException {
+        context.chargeComparison(ComparatorUtils.quadraticCost(string, glob));
+        return matches(string, glob);
+    }
+
 }
diff --git a/core/src/main/java/org/apache/jsieve/comparators/Octet.java 
b/core/src/main/java/org/apache/jsieve/comparators/Octet.java
index 2b6f7a9..be795a6 100644
--- a/core/src/main/java/org/apache/jsieve/comparators/Octet.java
+++ b/core/src/main/java/org/apache/jsieve/comparators/Octet.java
@@ -19,6 +19,8 @@
 
 package org.apache.jsieve.comparators;
 
+import org.apache.jsieve.SieveContext;
+import org.apache.jsieve.exception.SieveException;
 import org.apache.jsieve.exception.SievePatternException;
 
 /**
@@ -58,4 +60,25 @@ public class Octet implements Comparator {
         return ComparatorUtils.matches(string, glob);
     }
 
+    /**
+     * The search being linear, charges the lengths.
+     * @see org.apache.jsieve.comparators.Contains#contains(String, String, 
SieveContext)
+     */
+    @Override
+    public boolean contains(String container, String content, SieveContext 
context)
+            throws SieveException {
+        context.chargeComparison(ComparatorUtils.linearCost(container, 
content));
+        return contains(container, content);
+    }
+
+    /**
+     * Charges the steps the matcher takes.
+     * @see org.apache.jsieve.comparators.Matches#matches(String, String, 
SieveContext)
+     */
+    @Override
+    public boolean matches(String string, String glob, SieveContext context)
+            throws SieveException {
+        return ComparatorUtils.matches(string, glob, context);
+    }
+
 }
diff --git a/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java 
b/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java
new file mode 100644
index 0000000..7460333
--- /dev/null
+++ b/core/src/test/java/org/apache/jsieve/EvaluationBudgetTest.java
@@ -0,0 +1,180 @@
+/****************************************************************
+ * Licensed to the Apache Software Foundation (ASF) under one   *
+ * or more contributor license agreements.  See the NOTICE file *
+ * distributed with this work for additional information        *
+ * regarding copyright ownership.  The ASF licenses this file   *
+ * to you under the Apache License, Version 2.0 (the            *
+ * "License"); you may not use this file except in compliance   *
+ * with the License.  You may obtain a copy of the License at   *
+ *                                                              *
+ *   http://www.apache.org/licenses/LICENSE-2.0                 *
+ *                                                              *
+ * Unless required by applicable law or agreed to in writing,   *
+ * software distributed under the License is distributed on an  *
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY       *
+ * KIND, either express or implied.  See the License for the    *
+ * specific language governing permissions and limitations      *
+ * under the License.                                           *
+ ****************************************************************/
+
+package org.apache.jsieve;
+
+import static org.assertj.core.api.Assertions.assertThat;
+import static org.assertj.core.api.Assertions.assertThatCode;
+import static org.assertj.core.api.Assertions.assertThatThrownBy;
+
+import java.io.ByteArrayInputStream;
+import java.nio.charset.StandardCharsets;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+
+import org.apache.jsieve.comparators.Contains;
+import org.apache.jsieve.comparators.Matches;
+import org.apache.jsieve.exception.SieveException;
+import org.apache.jsieve.mail.ActionDiscard;
+import org.apache.jsieve.mail.ActionKeep;
+import org.apache.jsieve.utils.JUnitUtils;
+import org.apache.jsieve.utils.SieveMailAdapter;
+import org.junit.Test;
+
+/**
+ * The comparisons of an evaluation are bounded: a script cannot keep the
+ * evaluating thread busy for hours on a large mail.
+ */
+public class EvaluationBudgetTest {
+
+    private static final String CONTAINS_SCRIPT = "if header :contains 
\"Subject\" \"holidays\" { discard; }";
+
+    @Test(timeout = 10_000)
+    public void 
aPathologicalMatchOnALargeHeaderShouldFailOnceTheBudgetIsSpent() throws 
Exception {
+        SieveMailAdapter mail = mailWithSubject("a".repeat(2_000_000));
+        String script = "if header :matches \"Subject\" \"*" + 
"a".repeat(10_000) + "b\" { discard; }";
+
+        assertThatThrownBy(() -> 
factoryWithBudget(100_000_000).interpret(mail, script(script)))
+            .isInstanceOf(SieveException.class)
+            .hasMessageContaining("budget");
+        assertThat(mail.getActions()).isEmpty();
+    }
+
+    @Test(timeout = 10_000)
+    public void 
aPathologicalContainsOnALargeHeaderShouldBeEvaluatedInLinearTime() throws 
Exception {
+        SieveMailAdapter mail = mailWithSubject("a".repeat(2_000_000));
+        String script = "if header :contains \"Subject\" \"" + 
"a".repeat(10_000) + "b\" { discard; }";
+
+        JUnitUtils.interpret(mail, script);
+
+        
assertThat(mail.getActions()).singleElement().isInstanceOf(ActionKeep.class);
+    }
+
+    @Test(timeout = 30_000)
+    public void manyContainsKeysOnAMultiMegabyteHeaderShouldBeEvaluated() 
throws Exception {
+        SieveMailAdapter mail = mailWithSubject("lorem ipsum dolor sit amet 
".repeat(170_000) + "holidays");
+        String script = "if header :contains \"Subject\" [" + keys(100) + ", 
\"holidays\"] { discard; }";
+
+        JUnitUtils.interpret(mail, script);
+
+        
assertThat(mail.getActions()).singleElement().isInstanceOf(ActionDiscard.class);
+    }
+
+    @Test(timeout = 30_000)
+    public void manyMatchesKeysOnAMultiMegabyteHeaderShouldBeEvaluated() 
throws Exception {
+        SieveMailAdapter mail = mailWithSubject("lorem ipsum dolor sit amet 
".repeat(170_000) + "holidays");
+        String script = "if header :matches \"Subject\" [" + 
keys(100).replace("\"key", "\"*key") + ", \"*holidays\"] { discard; }";
+
+        JUnitUtils.interpret(mail, script);
+
+        
assertThat(mail.getActions()).singleElement().isInstanceOf(ActionDiscard.class);
+    }
+
+    @Test
+    public void aComparatorWithoutCostShouldBeChargedTheWorstCase() throws 
Exception {
+        ConfigurationManager configurationManager = new ConfigurationManager();
+        SieveContext context = new 
BaseSieveContext(configurationManager.getCommandManager(),
+            configurationManager.getComparatorManager(), 
configurationManager.getTestManager(), 1_000);
+        Contains naiveContains = String::contains;
+        Matches naiveMatches = (string, glob) -> string.equals(glob);
+
+        assertThatThrownBy(() -> naiveContains.contains("a".repeat(100), 
"b".repeat(10), context))
+            .isInstanceOf(SieveException.class)
+            .hasMessageContaining("budget");
+        assertThatThrownBy(() -> naiveMatches.matches("a".repeat(100), 
"b".repeat(10), context))
+            .isInstanceOf(SieveException.class)
+            .hasMessageContaining("budget");
+    }
+
+    @Test
+    public void comparisonsWithinTheBudgetShouldBeEvaluated() throws Exception 
{
+        SieveMailAdapter mail = mailWithSubject("Gone for holidays");
+
+        factoryWithBudget(40).interpret(mail, script(CONTAINS_SCRIPT));
+
+        
assertThat(mail.getActions()).singleElement().isInstanceOf(ActionDiscard.class);
+    }
+
+    @Test
+    public void comparisonsBeyondTheBudgetShouldFail() throws Exception {
+        SieveMailAdapter mail = mailWithSubject("Gone for holidays");
+
+        assertThatThrownBy(() -> factoryWithBudget(20).interpret(mail, 
script(CONTAINS_SCRIPT)))
+            .isInstanceOf(SieveException.class)
+            .hasMessageContaining("budget");
+    }
+
+    @Test
+    public void theBudgetShouldBeSpentAcrossTheTestsOfAnEvaluation() throws 
Exception {
+        SieveMailAdapter mail = mailWithSubject("Gone for holidays");
+        String script = CONTAINS_SCRIPT + CONTAINS_SCRIPT;
+
+        assertThatThrownBy(() -> factoryWithBudget(40).interpret(mail, 
script(script)))
+            .isInstanceOf(SieveException.class)
+            .hasMessageContaining("budget");
+    }
+
+    @Test
+    public void theBudgetShouldBeRenewedForEachEvaluation() throws Exception {
+        SieveFactory factory = factoryWithBudget(40);
+
+        for (int i = 0; i < 3; i++) {
+            SieveMailAdapter mail = mailWithSubject("Gone for holidays");
+            factory.interpret(mail, script(CONTAINS_SCRIPT));
+            
assertThat(mail.getActions()).singleElement().isInstanceOf(ActionDiscard.class);
+        }
+    }
+
+    @Test
+    public void aNegativeBudgetShouldBeRejected() {
+        assertThatThrownBy(() -> new 
ConfigurationManager().setComparisonBudget(-1))
+            .isInstanceOf(IllegalArgumentException.class);
+    }
+
+    @Test
+    public void aContextBuiltWithoutBudgetShouldNotLimitEvaluation() throws 
Exception {
+        ConfigurationManager configurationManager = new ConfigurationManager();
+        SieveContext context = new 
BaseSieveContext(configurationManager.getCommandManager(),
+            configurationManager.getComparatorManager(), 
configurationManager.getTestManager());
+
+        assertThatCode(() -> 
context.chargeComparison(Long.MAX_VALUE)).doesNotThrowAnyException();
+    }
+
+    private static SieveFactory factoryWithBudget(long budget) throws 
Exception {
+        ConfigurationManager configurationManager = new ConfigurationManager();
+        configurationManager.setComparisonBudget(budget);
+        return configurationManager.build();
+    }
+
+    private static String keys(int count) {
+        return IntStream.range(0, count)
+            .mapToObj(i -> "\"key" + i + "\"")
+            .collect(Collectors.joining(", "));
+    }
+
+    private static ByteArrayInputStream script(String script) {
+        return new 
ByteArrayInputStream(script.getBytes(StandardCharsets.UTF_8));
+    }
+
+    private static SieveMailAdapter mailWithSubject(String subject) throws 
Exception {
+        SieveMailAdapter mail = (SieveMailAdapter) JUnitUtils.createMail();
+        mail.getMessage().setHeader("Subject", subject);
+        return mail;
+    }
+}
diff --git 
a/core/src/test/java/org/apache/jsieve/comparator/ComparatorUtilsTest.java 
b/core/src/test/java/org/apache/jsieve/comparator/ComparatorUtilsTest.java
index f6ba4e3..8f4676a 100644
--- a/core/src/test/java/org/apache/jsieve/comparator/ComparatorUtilsTest.java
+++ b/core/src/test/java/org/apache/jsieve/comparator/ComparatorUtilsTest.java
@@ -121,6 +121,36 @@ public class ComparatorUtilsTest {
         Assert.assertTrue(ComparatorUtils.contains("\uD83D\uDE20\uDE20", 
"\uDE20"));
     }
 
+    @Test
+    public void containsShouldFindContentsOverlappingAPartialMatch() throws 
Exception {
+        Assert.assertTrue(ComparatorUtils.contains("aabaabaaab", "aaab"));
+        Assert.assertTrue(ComparatorUtils.contains("abababc", "ababc"));
+        Assert.assertTrue(ComparatorUtils.contains("abcabd", "abd"));
+        Assert.assertTrue(ComparatorUtils.contains("", ""));
+        Assert.assertTrue(ComparatorUtils.contains("abc", ""));
+        Assert.assertFalse(ComparatorUtils.contains("aaa", "aaaa"));
+        Assert.assertFalse(ComparatorUtils.contains("", "a"));
+    }
+
+    @Test
+    public void containsShouldAgreeWithIndexOfOnRandomStrings() throws 
Exception {
+        Random random = new Random(42);
+        for (int i = 0; i < 20_000; i++) {
+            String container = randomAbc(random, random.nextInt(12));
+            String contents = randomAbc(random, random.nextInt(5));
+            Assert.assertEquals("container=" + container + " contents=" + 
contents,
+                container.contains(contents), 
ComparatorUtils.contains(container, contents));
+        }
+    }
+
+    private static String randomAbc(Random random, int length) {
+        StringBuilder builder = new StringBuilder();
+        for (int i = 0; i < length; i++) {
+            builder.append((char) ('a' + random.nextInt(3)));
+        }
+        return builder.toString();
+    }
+
     @Test
     public void supplementaryCharacterShouldNotBeAWildcard() throws Exception {
         // U+1002A must not be truncated into '*'


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

Reply via email to