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]