This is an automated email from the ASF dual-hosted git repository. coheigea pushed a commit to branch coheigea/alternative-cap in repository https://gitbox.apache.org/repos/asf/ws-neethi.git
commit d63930bee2244cfca5c09f58f9c056393e550b2f Author: Colm O hEigeartaigh <[email protected]> AuthorDate: Wed Aug 19 11:26:55 2026 +0100 Add a cap on max normalized components --- README.txt | 25 ++++++- .../org/apache/neethi/AbstractPolicyOperator.java | 36 ++++++++- .../neethi/PolicyNormalizationMemoryDoSTest.java | 86 ++++++++++++++++++++++ 3 files changed, 139 insertions(+), 8 deletions(-) diff --git a/README.txt b/README.txt index fbe66f8..7e732b7 100644 --- a/README.txt +++ b/README.txt @@ -31,7 +31,24 @@ back to the default shown below. referenced policy document fetched through `PolicyReference`. Default: `67108864` bytes (`64 MiB`). -Policy normalization also enforces a hard cap of `10000` policy alternatives. -This limit applies to the number of normalized alternatives produced by policy -normalization and intersection, and helps prevent crafted policies from -triggering exponential expansion. +Policy normalization also enforces several hard caps: + +- `MAX_ALTERNATIVES` - maximum number of normalized policy alternatives + produced by policy normalization and intersection. + Default: `10000`. Helps prevent crafted policies from triggering exponential + expansion through Cartesian cross-products. + +- `MAX_REFERENCE_EXPANSIONS` - maximum number of PolicyReference expansions a + single normalization pass may perform. + Default: `100000`. Prevents exponential work from reference-DAG re-expansion: + a DAG with sibling references can materialize 2^d work from O(d) parsed + elements when the on-path cycle token is removed and siblings re-expand. + +- `MAX_NORMALIZED_COMPONENTS` - maximum total number of component references + normalization may materialize while building cross-product alternatives. + Default: `5000000`. The alternative-count cap alone cannot bound memory + consumption: every cross-product alternative copies the component lists of + both parents, so a policy staying under all parse budgets and under + MAX_ALTERNATIVES can still materialize hundreds of millions of references + (alternatives × parent widths). This cap ensures a fast RuntimeException + instead of OutOfMemoryError. diff --git a/src/main/java/org/apache/neethi/AbstractPolicyOperator.java b/src/main/java/org/apache/neethi/AbstractPolicyOperator.java index e4e4555..949e2b2 100644 --- a/src/main/java/org/apache/neethi/AbstractPolicyOperator.java +++ b/src/main/java/org/apache/neethi/AbstractPolicyOperator.java @@ -54,6 +54,18 @@ public abstract class AbstractPolicyOperator implements PolicyOperator { * work into a fast, predictable RuntimeException. */ private static final int MAX_REFERENCE_EXPANSIONS = 100_000; + + /** + * Maximum total number of component references normalization may + * materialize while building cross-product alternatives. The + * alternative-count cap bounds how many alternatives exist but not their + * width: every produced alternative copies the component lists of both + * parents, so a policy that stays under every parse budget and under the + * 10000-alternatives cap can still materialize hundreds of millions of + * references (alternatives x parent widths). This cap keeps the promise + * of a fast, predictable RuntimeException instead of an OutOfMemoryError. + */ + private static final long MAX_NORMALIZED_COMPONENTS = 5_000_000L; public AbstractPolicyOperator() { @@ -193,11 +205,12 @@ public abstract class AbstractPolicyOperator implements PolicyOperator { } } - return computeResultantComponent(childComponentsList, type); + return computeResultantComponent(childComponentsList, type, budget); } private static PolicyComponent computeResultantComponent(List<PolicyComponent> normalizedInnerComponets, - short componentType) { + short componentType, + NormalizeBudget budget) { ExactlyOne exactlyOne = new ExactlyOne(); @@ -230,7 +243,7 @@ public abstract class AbstractPolicyOperator implements PolicyOperator { exactlyOne = currentExactlyOne; break; } else { - exactlyOne = getCrossProduct(exactlyOne, currentExactlyOne); + exactlyOne = getCrossProduct(exactlyOne, currentExactlyOne, budget); } } @@ -248,7 +261,8 @@ public abstract class AbstractPolicyOperator implements PolicyOperator { return exactlyOne; } - private static ExactlyOne getCrossProduct(ExactlyOne exactlyOne1, ExactlyOne exactlyOne2) { + private static ExactlyOne getCrossProduct(ExactlyOne exactlyOne1, ExactlyOne exactlyOne2, + NormalizeBudget budget) { ExactlyOne crossProduct = new ExactlyOne(); All crossProductAll; @@ -263,6 +277,8 @@ public abstract class AbstractPolicyOperator implements PolicyOperator { checkAlternativeBudget(nextSize); currentAll2 = (All)pc2; + budget.chargeComponents(currentAll1.getPolicyComponents().size() + + (long)currentAll2.getPolicyComponents().size()); crossProductAll = new All(); crossProductAll.addPolicyComponents(currentAll1.getPolicyComponents()); crossProductAll.addPolicyComponents(currentAll2.getPolicyComponents()); @@ -280,6 +296,7 @@ public abstract class AbstractPolicyOperator implements PolicyOperator { private static final class NormalizeBudget { private final Set<String> resolving = new HashSet<String>(); private long referenceExpansions; + private long materializedComponents; void enterReference(String token) { if (!resolving.add(token)) { @@ -299,6 +316,17 @@ public abstract class AbstractPolicyOperator implements PolicyOperator { void exitReference(String token) { resolving.remove(token); } + + void chargeComponents(long count) { + materializedComponents += count; + if (materializedComponents > MAX_NORMALIZED_COMPONENTS) { + throw new RuntimeException( + "Policy normalization exceeded the maximum number of materialized" + + " components (" + MAX_NORMALIZED_COMPONENTS + "). The policy may" + + " be crafted to cause memory-exhaustion DoS via wide" + + " cross-product alternatives."); + } + } } public static void checkMaximumAlternativeCount(long alternativesCount, String operation) { diff --git a/src/test/java/org/apache/neethi/PolicyNormalizationMemoryDoSTest.java b/src/test/java/org/apache/neethi/PolicyNormalizationMemoryDoSTest.java new file mode 100644 index 0000000..5408b14 --- /dev/null +++ b/src/test/java/org/apache/neethi/PolicyNormalizationMemoryDoSTest.java @@ -0,0 +1,86 @@ +/** + * 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.neethi; + +import javax.xml.namespace.QName; + +import org.apache.neethi.builders.PrimitiveAssertion; + +import org.junit.Test; + +/** + * The 10000-alternatives cap bounds the alternative COUNT of the normalized + * form, not its memory: every cross-product alternative copies the component + * lists of both parents, so an ExactlyOne of a few thousand alternatives + * crossed against a wide All materializes alternatives x width references + * (hundreds of millions at the parse budgets) while every count check stays + * green. The materialized-component budget must turn that into a fast, + * predictable RuntimeException instead of an OutOfMemoryError. + */ +public class PolicyNormalizationMemoryDoSTest extends PolicyTestCase { + + private static final int ALTERNATIVES = 3000; + private static final int WIDE_ALL_WIDTH = 2000; + + @Test + public void testWideCrossProductIsRejectedByComponentBudget() { + Policy policy = buildWideCrossProductPolicy(ALTERNATIVES, WIDE_ALL_WIDTH); + + try { + policy.normalize(registry, true); + fail("Expected RuntimeException due to materialized-component budget"); + } catch (RuntimeException ex) { + assertTrue(ex.getMessage().contains("materialized components")); + } + } + + @Test + public void testModerateCrossProductStillNormalizes() { + Policy policy = buildWideCrossProductPolicy(20, 30); + + assertNotNull(policy.normalize(registry, true)); + } + + /** + * Policy (= All) containing an ExactlyOne of {@code alternatives} + * single-assertion Alls and one All of {@code width} assertions. + * Normalization crosses them into {@code alternatives} alternatives of + * width {@code width + 1} each — count under the cap, memory unbounded. + */ + private static Policy buildWideCrossProductPolicy(int alternatives, int width) { + Policy policy = new Policy(); + + ExactlyOne eo = new ExactlyOne(); + for (int i = 0; i < alternatives; i++) { + All alt = new All(); + alt.addPolicyComponent(new PrimitiveAssertion(new QName("urn:test", "a" + i))); + eo.addPolicyComponent(alt); + } + policy.addPolicyComponent(eo); + + All wide = new All(); + for (int i = 0; i < width; i++) { + wide.addPolicyComponent(new PrimitiveAssertion(new QName("urn:test", "w" + i))); + } + policy.addPolicyComponent(wide); + + return policy; + } +}
