This is an automated email from the ASF dual-hosted git repository. coheigea pushed a commit to branch coheigea/reference-expansions in repository https://gitbox.apache.org/repos/asf/ws-neethi.git
commit dfcbf599f7a5fa63a9dbb71f84bcf6ba67a369f0 Author: Colm O hEigeartaigh <[email protected]> AuthorDate: Wed Aug 19 09:28:11 2026 +0100 Put limit on reference expansions --- .../org/apache/neethi/AbstractPolicyOperator.java | 56 +++++++++-- .../neethi/PolicyReferenceExpansionDoSTest.java | 102 +++++++++++++++++++++ 2 files changed, 149 insertions(+), 9 deletions(-) diff --git a/src/main/java/org/apache/neethi/AbstractPolicyOperator.java b/src/main/java/org/apache/neethi/AbstractPolicyOperator.java index f55acbb..e4e4555 100644 --- a/src/main/java/org/apache/neethi/AbstractPolicyOperator.java +++ b/src/main/java/org/apache/neethi/AbstractPolicyOperator.java @@ -42,6 +42,18 @@ public abstract class AbstractPolicyOperator implements PolicyOperator { * fast, predictable RuntimeException. */ private static final int MAX_ALTERNATIVES = 10_000; + + /** + * Maximum number of PolicyReference expansions a single normalization + * pass may perform. The alternative-count cap alone cannot see reference + * re-expansion: a reference DAG in which every level holds two sibling + * references to the next level normalizes to a single alternative at each + * step while the expansion work doubles per level (2^d work from O(d) + * parsed elements, because the on-path cycle token is removed once each + * expansion completes). Budgeting expansions converts that unbounded + * work into a fast, predictable RuntimeException. + */ + private static final int MAX_REFERENCE_EXPANSIONS = 100_000; public AbstractPolicyOperator() { @@ -95,7 +107,7 @@ public abstract class AbstractPolicyOperator implements PolicyOperator { } - result.addPolicyComponent(normalizeOperator(policy, policy, reg, deep, new HashSet<String>())); + result.addPolicyComponent(normalizeOperator(policy, policy, reg, deep, new NormalizeBudget())); return result; } @@ -103,7 +115,7 @@ public abstract class AbstractPolicyOperator implements PolicyOperator { PolicyOperator operator, PolicyRegistry reg, boolean deep, - Set<String> resolving) { + NormalizeBudget budget) { short type = operator.getType(); @@ -160,26 +172,24 @@ public abstract class AbstractPolicyOperator implements PolicyOperator { String resolvedId = ((Policy) policyComponent).getId(); String resolvingToken = resolvedId != null && resolvedId.length() > 0 ? "id:" + resolvedId : "uri:" + uri; - if (!resolving.add(resolvingToken)) { - throw new RuntimeException("Circular PolicyReference detected: " + resolvingToken); - } + budget.enterReference(resolvingToken); try { All all = new All(); all.addPolicyComponents(((Policy) policyComponent).getPolicyComponents()); - childComponentsList.add(AbstractPolicyOperator.normalizeOperator(policy, all, reg, deep, resolving)); + childComponentsList.add(AbstractPolicyOperator.normalizeOperator(policy, all, reg, deep, budget)); } finally { - resolving.remove(resolvingToken); + budget.exitReference(resolvingToken); } } else if (policyComponent.getType() == Constants.TYPE_POLICY) { All all = new All(); all.addPolicyComponents(((Policy) policyComponent).getPolicyComponents()); - childComponentsList.add(AbstractPolicyOperator.normalizeOperator(policy, all, reg, deep, resolving)); + childComponentsList.add(AbstractPolicyOperator.normalizeOperator(policy, all, reg, deep, budget)); } else { childComponentsList.add(AbstractPolicyOperator .normalizeOperator(policy, - (PolicyOperator)policyComponent, reg, deep, resolving)); + (PolicyOperator)policyComponent, reg, deep, budget)); } } @@ -263,6 +273,34 @@ public abstract class AbstractPolicyOperator implements PolicyOperator { return crossProduct; } + /** + * Per-normalization-pass accounting: the on-path cycle set plus the + * budget that bounds total reference-expansion work. + */ + private static final class NormalizeBudget { + private final Set<String> resolving = new HashSet<String>(); + private long referenceExpansions; + + void enterReference(String token) { + if (!resolving.add(token)) { + throw new RuntimeException("Circular PolicyReference detected: " + token); + } + referenceExpansions++; + if (referenceExpansions > MAX_REFERENCE_EXPANSIONS) { + resolving.remove(token); + throw new RuntimeException( + "Policy normalization exceeded the maximum number of PolicyReference" + + " expansions (" + MAX_REFERENCE_EXPANSIONS + "). The policy may be" + + " crafted to cause Algorithmic Complexity DoS via reference" + + " re-expansion."); + } + } + + void exitReference(String token) { + resolving.remove(token); + } + } + public static void checkMaximumAlternativeCount(long alternativesCount, String operation) { if (alternativesCount > MAX_ALTERNATIVES) { throw new RuntimeException( diff --git a/src/test/java/org/apache/neethi/PolicyReferenceExpansionDoSTest.java b/src/test/java/org/apache/neethi/PolicyReferenceExpansionDoSTest.java new file mode 100644 index 0000000..9c00cb8 --- /dev/null +++ b/src/test/java/org/apache/neethi/PolicyReferenceExpansionDoSTest.java @@ -0,0 +1,102 @@ +/** + * 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 java.io.ByteArrayInputStream; +import java.io.InputStream; +import java.nio.charset.StandardCharsets; + +import org.junit.Test; + +/** + * A reference DAG in which every level holds two sibling references to the + * next level normalizes to a single alternative at every step (so the + * 10000-alternatives cap never trips) while the expansion work doubles per + * level: 2^d normalizeOperator invocations from O(d) parsed elements, because + * the cycle token is removed once each expansion completes and sibling + * references then re-expand the same policy in full. The expansion budget + * converts that into a fast, predictable RuntimeException. + */ +public class PolicyReferenceExpansionDoSTest extends PolicyTestCase { + + private static final int DAG_DEPTH = 30; + + private static final String WSU_NS = + "http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd";; + + @Test + public void testDoublingReferenceDagIsRejectedByExpansionBudget() { + Policy policy = policyEngine.getPolicy(xmlStream(buildDoublingReferenceDagXml(DAG_DEPTH))); + + try { + policy.normalize(registry, true); + fail("Expected RuntimeException due to reference-expansion budget"); + } catch (RuntimeException ex) { + assertTrue(ex.getMessage().contains("PolicyReference expansions")); + } + } + + @Test + public void testSiblingReferencesToSamePolicyStillNormalize() { + Policy policy = policyEngine.getPolicy(xmlStream(buildSiblingReferencePolicyXml())); + + assertNotNull(policy.normalize(registry, true)); + } + + private static InputStream xmlStream(String xml) { + return new ByteArrayInputStream(xml.getBytes(StandardCharsets.UTF_8)); + } + + private static String buildDoublingReferenceDagXml(int depth) { + StringBuilder xml = new StringBuilder(1024 + depth * 160); + xml.append("<wsp:Policy xmlns:wsp=\"http://www.w3.org/ns/ws-policy\"";) + .append(" xmlns:wsu=\"").append(WSU_NS).append("\"") + .append(" xmlns:x=\"urn:x\">"); + + xml.append("<wsp:PolicyReference URI=\"#B1\"/>") + .append("<wsp:PolicyReference URI=\"#B1\"/>"); + + for (int i = 1; i < depth; i++) { + xml.append("<wsp:Policy wsu:Id=\"B").append(i).append("\">") + .append("<wsp:PolicyReference URI=\"#B").append(i + 1).append("\"/>") + .append("<wsp:PolicyReference URI=\"#B").append(i + 1).append("\"/>") + .append("</wsp:Policy>"); + } + + xml.append("<wsp:Policy wsu:Id=\"B").append(depth).append("\">") + .append("<x:Leaf/>") + .append("</wsp:Policy>"); + + xml.append("</wsp:Policy>"); + return xml.toString(); + } + + private static String buildSiblingReferencePolicyXml() { + StringBuilder xml = new StringBuilder(512); + xml.append("<wsp:Policy xmlns:wsp=\"http://www.w3.org/ns/ws-policy\"";) + .append(" xmlns:wsu=\"").append(WSU_NS).append("\"") + .append(" xmlns:x=\"urn:x\">") + .append("<wsp:PolicyReference URI=\"#P\"/>") + .append("<wsp:PolicyReference URI=\"#P\"/>") + .append("<wsp:Policy wsu:Id=\"P\"><x:Leaf/></wsp:Policy>") + .append("</wsp:Policy>"); + return xml.toString(); + } +}
