This is an automated email from the ASF dual-hosted git repository. coheigea pushed a commit to branch coheigea/policy-comparator-budget in repository https://gitbox.apache.org/repos/asf/ws-neethi.git
commit a577368ac7c626e5fea21314b019e074b4f1e68c Author: Colm O hEigeartaigh <[email protected]> AuthorDate: Thu Aug 20 09:33:37 2026 +0100 Adding a policy comparator budget --- README.txt | 9 +++ THREAT-MODEL.md | 19 ++++- .../org/apache/neethi/util/PolicyComparator.java | 53 +++++++++++--- .../neethi/util/PolicyComparatorDoSTest.java | 83 ++++++++++++++++++++++ 4 files changed, 155 insertions(+), 9 deletions(-) diff --git a/README.txt b/README.txt index 7e732b7..85b2335 100644 --- a/README.txt +++ b/README.txt @@ -52,3 +52,12 @@ Policy normalization also enforces several hard caps: MAX_ALTERNATIVES can still materialize hundreds of millions of references (alternatives × parent widths). This cap ensures a fast RuntimeException instead of OutOfMemoryError. + +`PolicyComparator` also enforces a comparison budget: + +- `MAX_COMPARISONS` - maximum number of pairwise component comparisons a + single top-level `compare(...)` call may perform. + Default: `10000000`. `PolicyComparator`'s list matching is unordered and + unmemoized, so mismatched operand orderings cost O(n1 * n2) comparisons. + This cap turns an engineered quadratic comparison into a fast, predictable + RuntimeException instead of pinned CPU. diff --git a/THREAT-MODEL.md b/THREAT-MODEL.md index 8225d56..9e29d45 100644 --- a/THREAT-MODEL.md +++ b/THREAT-MODEL.md @@ -432,6 +432,22 @@ overload disables both. The pre-parsed-`Element` / `XMLStreamReader` / divergence is security-meaningful downstream. - *(inferred — §14 Q10)* +### P12 — `PolicyComparator` pairwise-comparison budget is enforced + +- **Condition**: `PolicyComparator.compare(...)` (directly, or + transitively via `Policy.equals` / `AbstractPolicyOperator.equal` / + `PolicyContainingPrimitiveAssertion.equal`) is invoked on two + well-formed `PolicyComponent` trees. +- **Violation symptom**: the unordered, unmemoized list-matching in + `compare(List, List)` completes more than `MAX_COMPARISONS` pairwise + component comparisons without rejection — an adversarial operand + ordering costs O(n1 * n2) comparisons with no cap, up to minutes of + pinned CPU at the parser budgets. +- **Severity**: **availability-relevant** (quadratic, not exponential — + bounded even unpatched), `VALID` per §13. +- *(documented: `README.txt` — `MAX_COMPARISONS`, default `10000000`; + `src/main/java/org/apache/neethi/util/PolicyComparator.java`)* + ## §9 Security properties the project does *not* provide State each plainly so a triager can route an inbound report to the @@ -796,6 +812,7 @@ source comments. The project website is | --- | --- | --- | | `README.txt` | "implementation of WS-Policy Specification (September, 2007)"; "It provides a convenient model and an API to process policy information at runtime and an extension model for serialization and de-serialization of domain-specific Assertions" | §1, §2 intended use | | `README.txt` | documented security budgets: `org.apache.neethi.parser.maxDepth=256`, `org.apache.neethi.parser.maxElements=100000`, `org.apache.neethi.parser.maxAttributes=10000`, `org.apache.neethi.remote.maxPolicyBytes=67108864`, and normalization/intersection cap `10000` alternatives; invalid/unset values fall back to defaults | §5a, §6, §8 P2-P6, §10 item 4 | +| `README.txt` | `PolicyComparator` comparison budget: `MAX_COMPARISONS=10000000` pairwise component comparisons per top-level `compare(...)` call; throws `RuntimeException` on exhaustion | §8 P12 | | `src/main/java/org/apache/neethi/PolicyBuilder.java` lines 99-100 (`getPolicy(InputStream)`) | `xif.setProperty(IS_SUPPORTING_EXTERNAL_ENTITIES, FALSE); xif.setProperty(SUPPORT_DTD, FALSE)` | §8 P1, §11a | | `PolicyBuilder.java` lines 140-141 (`getPolicyReference(InputStream)`) | same XXE/DTD hardening on the PolicyReference parse path | §8 P1, §11a | | `PolicyReference.java` lines 141-190 (`getRemoteReferencedPolicy(String u)`) | the remote-policy fetcher | §1 (deployment shape), §4 B5, §5 network, §5a, §8 P7-P10, §9 first three bullets, §10 items 2-3, §11 | @@ -806,5 +823,5 @@ source comments. The project website is | `PolicyEngine.java` lines 45-52 | "static synchronized PolicyBuilder" facade | §9 false-friend, §11 | | `AssertionBuilderFactoryImpl.java`, `util.Service` | ServiceLoader-style discovery of `AssertionBuilder` via `META-INF/services/` | §5, §10 item 6 | | `Policy.java`, `All.java`, `ExactlyOne.java`, `AbstractPolicyOperator.java` | `normalize(reg, deep)` resolves references via registry/local `#id` only and throws on a miss; remote fetch requires a direct embedder call to `PolicyReference.normalize(reg, deep)` or `getRemoteReferencedPolicy(...)` | §4 B4-B5, §11 | -| `util.PolicyIntersector`, `util.PolicyComparator` | policy-algebra utilities | §8 P11, §14 Q10 | +| `util.PolicyIntersector`, `util.PolicyComparator` | policy-algebra utilities | §8 P11-P12, §14 Q10 | | `RELEASE-NOTE.txt` | release notes per version | §1 supported branches | diff --git a/src/main/java/org/apache/neethi/util/PolicyComparator.java b/src/main/java/org/apache/neethi/util/PolicyComparator.java index 0c173f6..4411b49 100644 --- a/src/main/java/org/apache/neethi/util/PolicyComparator.java +++ b/src/main/java/org/apache/neethi/util/PolicyComparator.java @@ -37,6 +37,25 @@ public final class PolicyComparator { //utility class } + /** + * Maximum number of pairwise component comparisons a single top-level + * compare call may perform. The list comparison is unordered nested + * matching with no memoization, so mismatched operand orderings cost + * O(n1 * n2) comparisons, converting an engineered quadratic comparison + * into a fast, predictable RuntimeException instead of pinned CPU. + */ + private static final long MAX_COMPARISONS = 10_000_000L; + + private static void chargeComparison(long[] budget) { + if (++budget[0] > MAX_COMPARISONS) { + throw new RuntimeException( + "Policy comparison exceeded the maximum number of component" + + " comparisons (" + MAX_COMPARISONS + "). The operands may be" + + " crafted to cause Algorithmic Complexity DoS via unordered" + + " matching."); + } + } + /** * Returns {@code true} if the two policies have the same semantics * @@ -47,6 +66,10 @@ public final class PolicyComparator { * @return {@code true} if both policies have the same semantics */ public static boolean compare(Policy arg1, Policy arg2) { + return compare(arg1, arg2, new long[1]); + } + + private static boolean compare(Policy arg1, Policy arg2, long[] budget) { // check Name attributes of each policies if (arg1.getName() != null) { @@ -79,7 +102,7 @@ public final class PolicyComparator { } } - return compare(arg1.getPolicyComponents(), arg2.getPolicyComponents()); + return compare(arg1.getPolicyComponents(), arg2.getPolicyComponents(), budget); } /** @@ -93,18 +116,23 @@ public final class PolicyComparator { * @return {@code true} if both PolicyComponents have the same semantics */ public static boolean compare(PolicyComponent arg1, PolicyComponent arg2) { + return compare(arg1, arg2, new long[1]); + } + + private static boolean compare(PolicyComponent arg1, PolicyComponent arg2, long[] budget) { + chargeComparison(budget); if (!arg1.getClass().equals(arg2.getClass())) { return false; } if (arg1 instanceof Policy) { - return compare((Policy) arg1, (Policy) arg2); + return compare((Policy) arg1, (Policy) arg2, budget); } else if (arg1 instanceof All) { - return compare((All) arg1, (All) arg2); + return compare((All) arg1, (All) arg2, budget); } else if (arg1 instanceof ExactlyOne) { - return compare((ExactlyOne) arg1, (ExactlyOne) arg2); + return compare((ExactlyOne) arg1, (ExactlyOne) arg2, budget); } else if (arg1 instanceof Assertion) { return compare((Assertion) arg1, (Assertion) arg2); @@ -117,11 +145,19 @@ public final class PolicyComparator { } public static boolean compare(All arg1, All arg2) { - return compare(arg1.getPolicyComponents(), arg2.getPolicyComponents()); + return compare(arg1, arg2, new long[1]); + } + + private static boolean compare(All arg1, All arg2, long[] budget) { + return compare(arg1.getPolicyComponents(), arg2.getPolicyComponents(), budget); } public static boolean compare(ExactlyOne arg1, ExactlyOne arg2) { - return compare(arg1.getPolicyComponents(), arg2.getPolicyComponents()); + return compare(arg1, arg2, new long[1]); + } + + private static boolean compare(ExactlyOne arg1, ExactlyOne arg2, long[] budget) { + return compare(arg1.getPolicyComponents(), arg2.getPolicyComponents(), budget); } public static boolean compare(Assertion arg1, Assertion arg2) { @@ -131,7 +167,8 @@ public final class PolicyComparator { return true; } - private static boolean compare(List<PolicyComponent> arg1, List<PolicyComponent> arg2) { + private static boolean compare(List<PolicyComponent> arg1, List<PolicyComponent> arg2, + long[] budget) { if (arg1.size() != arg2.size()) { return false; } @@ -140,7 +177,7 @@ public final class PolicyComparator { for (PolicyComponent assertion1 : arg1) { boolean match = false; for (PolicyComponent assertion2 : arg2) { - if (compare(assertion1, assertion2)) { + if (compare(assertion1, assertion2, budget)) { match = true; break; } diff --git a/src/test/java/org/apache/neethi/util/PolicyComparatorDoSTest.java b/src/test/java/org/apache/neethi/util/PolicyComparatorDoSTest.java new file mode 100644 index 0000000..aa07730 --- /dev/null +++ b/src/test/java/org/apache/neethi/util/PolicyComparatorDoSTest.java @@ -0,0 +1,83 @@ +/** + * 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.util; + +import javax.xml.namespace.QName; + +import org.apache.neethi.All; +import org.apache.neethi.ExactlyOne; +import org.apache.neethi.Policy; +import org.apache.neethi.PolicyTestCase; +import org.apache.neethi.builders.PrimitiveAssertion; + +import org.junit.Test; + +/** + * PolicyComparator's list comparison is unordered nested matching with no + * memoization: each component of one list scans the other list for a match, + * so operand orderings engineered to match late cost O(n1 * n2) comparisons + * — minutes of pinned CPU at the parse budgets. The comparison budget must + * turn that into a fast, predictable RuntimeException. + */ +public class PolicyComparatorDoSTest extends PolicyTestCase { + + private static final int LARGE = 6000; + private static final int SMALL = 200; + + @Test + public void testQuadraticUnorderedMatchingIsRejectedByComparisonBudget() { + Policy p1 = buildAlternativesPolicy(LARGE, false); + Policy p2 = buildAlternativesPolicy(LARGE, true); + + try { + PolicyComparator.compare(p1, p2); + fail("Expected RuntimeException due to comparison budget"); + } catch (RuntimeException ex) { + assertTrue(ex.getMessage().contains("component comparisons")); + } + } + + @Test + public void testModerateUnorderedComparisonStillWorks() { + Policy p1 = buildAlternativesPolicy(SMALL, false); + Policy p2 = buildAlternativesPolicy(SMALL, true); + + assertTrue(PolicyComparator.compare(p1, p2)); + } + + /** + * Builds a Policy holding one ExactlyOne of {@code n} single-assertion + * alternatives. With {@code reversed} set, the alternatives appear in + * reverse order, so the unordered matcher finds each partner only at the + * far end of its scan — the quadratic worst case for equal operands. + */ + private static Policy buildAlternativesPolicy(int n, boolean reversed) { + Policy policy = new Policy(); + ExactlyOne eo = new ExactlyOne(); + for (int i = 0; i < n; i++) { + int idx = reversed ? n - 1 - i : i; + All all = new All(); + all.addPolicyComponent(new PrimitiveAssertion(new QName("urn:test", "a" + idx))); + eo.addPolicyComponent(all); + } + policy.addPolicyComponent(eo); + return policy; + } +}
