This is an automated email from the ASF dual-hosted git repository. coheigea pushed a commit to branch coheigea/intersection in repository https://gitbox.apache.org/repos/asf/ws-neethi.git
commit 3b18e15499544dfa3551b16fabbbf3767ab1f732 Author: Colm O hEigeartaigh <[email protected]> AuthorDate: Thu Aug 20 10:29:56 2026 +0100 Adding policy intersection budget --- README.txt | 12 ++++ THREAT-MODEL.md | 22 +++++- .../org/apache/neethi/util/PolicyIntersector.java | 83 ++++++++++++++++++---- .../apache/neethi/PolicyIntersectionDoSTest.java | 44 ++++++++++++ 4 files changed, 147 insertions(+), 14 deletions(-) diff --git a/README.txt b/README.txt index 85b2335..99c9300 100644 --- a/README.txt +++ b/README.txt @@ -61,3 +61,15 @@ Policy normalization also enforces several hard caps: 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. + +`PolicyIntersector` also enforces an intersection work budget: + +- `MAX_INTERSECT_STEPS` - maximum number of assertion-pair intersection + attempts a single top-level `intersect(...)` or `compatiblePolicies(...)` + call may perform, including recursion into nested policies of + `PolicyContainingAssertion` values. + Default: `1000000`. The alternatives-output cap bounds what is emitted, but + not all candidate-search work; recursive same-QName fan-out can otherwise + trigger algorithmic-complexity DoS through exponential search effort. + This cap turns that engineered search into a fast, predictable + RuntimeException instead of pinned CPU. diff --git a/THREAT-MODEL.md b/THREAT-MODEL.md index 9e29d45..eb3dd23 100644 --- a/THREAT-MODEL.md +++ b/THREAT-MODEL.md @@ -237,6 +237,7 @@ feature toggles**. The runtime security envelope is shaped by: | `org.apache.neethi.parser.maxAttributes` | `10000` *(documented: `README.txt`)* | hardened-by-default | bounds maximum number of parsed attributes | | `org.apache.neethi.remote.maxPolicyBytes` | `67108864` bytes (`64 MiB`) *(documented: `README.txt`)* | hardened-by-default | bounds bytes read for remotely dereferenced policies | | Policy normalization alternatives cap | `10000` alternatives *(documented: `README.txt`)* | hardened-by-default | blocks exponential policy-alternative expansion during normalization/intersection | +| `PolicyIntersector` work budget (`MAX_INTERSECT_STEPS`) | `1000000` assertion-pair intersection attempts per top-level `intersect(...)` / `compatiblePolicies(...)` call *(documented: `README.txt`)* | hardened-by-default | bounds recursive candidate-search work in intersection (including nested `PolicyContainingAssertion` recursion) | | `META-INF/services/.../AssertionBuilder` | classpath-discovered | classpath is the trust gate | adds domain-specific assertion vocabularies | ### The insecure-default case @@ -289,6 +290,10 @@ overload disables both. The pre-parsed-`Element` / `XMLStreamReader` / *(documented: `README.txt`)*. - Documented hard cap of `10000` normalized policy alternatives during normalization/intersection *(documented: `README.txt`)*. +- Documented hard cap of `1000000` assertion-pair intersection attempts + per top-level `PolicyIntersector.intersect(...)` / + `PolicyIntersector.compatiblePolicies(...)` call *(documented: + `README.txt`)*. - No documented bound on the number of `PolicyReference` URIs in a single policy *(inferred — §14 Q7)*. Transitive fetch chains cannot occur inside one normalization call: a fetched policy is @@ -448,6 +453,19 @@ overload disables both. The pre-parsed-`Element` / `XMLStreamReader` / - *(documented: `README.txt` — `MAX_COMPARISONS`, default `10000000`; `src/main/java/org/apache/neethi/util/PolicyComparator.java`)* +### P13 — `PolicyIntersector` recursive candidate-search work budget is enforced + +- **Condition**: `PolicyIntersector.intersect(...)` and/or + `PolicyIntersector.compatiblePolicies(...)` is invoked on well-formed + policy trees. +- **Violation symptom**: a top-level call performs more than + `MAX_INTERSECT_STEPS` assertion-pair intersection attempts (including + recursion into nested `PolicyContainingAssertion` policies) without + rejection. +- **Severity**: **availability-relevant**, `VALID` per §13. +- *(documented: `README.txt` — `MAX_INTERSECT_STEPS`, default + `1000000`)* + ## §9 Security properties the project does *not* provide State each plainly so a triager can route an inbound report to the @@ -811,7 +829,7 @@ source comments. The project website is | Source | Claim | Lands in | | --- | --- | --- | | `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` | 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`, normalization/intersection output cap `10000` alternatives, and `PolicyIntersector` work budget `MAX_INTERSECT_STEPS=1000000`; invalid/unset values fall back to defaults | §5a, §6, §8 P2-P6/P13, §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 | @@ -823,5 +841,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-P12, §14 Q10 | +| `util.PolicyIntersector`, `util.PolicyComparator` | policy-algebra utilities | §8 P11-P13, §14 Q10 | | `RELEASE-NOTE.txt` | release notes per version | §1 supported branches | diff --git a/src/main/java/org/apache/neethi/util/PolicyIntersector.java b/src/main/java/org/apache/neethi/util/PolicyIntersector.java index 926aa86..4cb1865 100644 --- a/src/main/java/org/apache/neethi/util/PolicyIntersector.java +++ b/src/main/java/org/apache/neethi/util/PolicyIntersector.java @@ -40,6 +40,33 @@ import org.apache.neethi.PolicyContainingAssertion; * See Section 4.5 in http://www.w3.org/TR/2006/WD-ws-policy-20061117. */ public class PolicyIntersector { + + /** + * Maximum number of assertion-pair intersection attempts a single + * top-level intersect/compatiblePolicies call may perform, including the + * recursion into nested policies of PolicyContainingAssertions. The + * output-alternative cap bounds what is emitted but not the search work, + * which otherwise grows with the product of the alternative sizes at + * every nesting level. The budget converts an engineered exponential + * search into a fast, predictable RuntimeException. + */ + private static final long MAX_INTERSECT_STEPS = 1_000_000L; + + /** Work accounting shared across one top-level intersection. */ + private static final class WorkBudget { + private long steps; + + void step() { + steps++; + if (steps > MAX_INTERSECT_STEPS) { + throw new RuntimeException( + "Policy intersection exceeded the maximum number of assertion" + + " intersection steps (" + MAX_INTERSECT_STEPS + "). The policies" + + " may be crafted to cause Algorithmic Complexity DoS via" + + " recursive candidate search."); + } + } + } private boolean strict; @@ -58,7 +85,8 @@ public class PolicyIntersector { strict = s; } - private Assertion intersect(Assertion a1, Assertion a2) { + private Assertion intersect(Assertion a1, Assertion a2, WorkBudget budget) { + budget.step(); if (a1 instanceof IntersectableAssertion) { if (!((IntersectableAssertion)a1).isCompatible(a2, strict)) { return null; @@ -74,8 +102,7 @@ public class PolicyIntersector { PolicyContainingAssertion pc2 = (PolicyContainingAssertion)a2; Policy p1 = pc1.getPolicy(); Policy p2 = pc2.getPolicy(); - PolicyIntersector pi = new PolicyIntersector(strict); - if (pi.compatiblePolicies(p1, p2)) { + if (compatiblePolicies(p1, p2, budget)) { return a1; } } else { @@ -86,12 +113,13 @@ public class PolicyIntersector { } private Assertion findCompatibleAssertion(Assertion assertion, Collection<? extends PolicyComponent> alt, - boolean remove) { + boolean remove, + WorkBudget budget) { Iterator<? extends PolicyComponent> iterator = alt.iterator(); while (iterator.hasNext()) { PolicyComponent a = iterator.next(); if (a instanceof Assertion) { - Assertion compatible = intersect(assertion, (Assertion)a); + Assertion compatible = intersect(assertion, (Assertion)a, budget); if (null != compatible) { if (remove) { iterator.remove(); @@ -106,11 +134,17 @@ public class PolicyIntersector { boolean compatibleAlternatives(Collection<? extends PolicyComponent> alt1, Collection<? extends PolicyComponent> alt2) { + return compatibleAlternatives(alt1, alt2, new WorkBudget()); + } + + private boolean compatibleAlternatives(Collection<? extends PolicyComponent> alt1, + Collection<? extends PolicyComponent> alt2, + WorkBudget budget) { if (alt1.isEmpty() && alt2.isEmpty()) { return true; } - All all = createCompatibleAlternatives(alt1, alt2, true); + All all = createCompatibleAlternatives(alt1, alt2, true, budget); if (all == null) { return false; } @@ -120,6 +154,13 @@ public class PolicyIntersector { All createCompatibleAlternatives(Collection<? extends PolicyComponent> alt1, Collection<? extends PolicyComponent> alt2, boolean remove) { + return createCompatibleAlternatives(alt1, alt2, remove, new WorkBudget()); + } + + private All createCompatibleAlternatives(Collection<? extends PolicyComponent> alt1, + Collection<? extends PolicyComponent> alt2, + boolean remove, + WorkBudget budget) { All all = new All(); if (alt1.isEmpty() && alt2.isEmpty()) { return all; @@ -132,7 +173,7 @@ public class PolicyIntersector { while (iterator.hasNext()) { PolicyComponent a1 = iterator.next(); if (a1 instanceof Assertion) { - Assertion assertion = findCompatibleAssertion((Assertion)a1, alt2, remove); + Assertion assertion = findCompatibleAssertion((Assertion)a1, alt2, remove, budget); if (assertion != null) { if (remove) { iterator.remove(); @@ -149,7 +190,7 @@ public class PolicyIntersector { while (iterator.hasNext()) { PolicyComponent a2 = iterator.next(); if (a2 instanceof Assertion) { - Assertion assertion = findCompatibleAssertion((Assertion)a2, alt1, remove); + Assertion assertion = findCompatibleAssertion((Assertion)a2, alt1, remove, budget); if (assertion != null) { all.addPolicyComponent(assertion); } else if (!strict && ((Assertion)a2).isIgnorable()) { @@ -163,16 +204,23 @@ public class PolicyIntersector { } public boolean compatiblePolicies(Policy p1, Policy p2) { + return compatiblePolicies(p1, p2, new WorkBudget()); + } + + private boolean compatiblePolicies(Policy p1, Policy p2, WorkBudget budget) { + // normalize p2 exactly once: Policy.getAlternatives() re-runs a full + // normalization on every call, so it must not sit inside the p1 loop + List<List<Assertion>> alternatives2 = materializeAlternatives(p2); Iterator<List<Assertion>> i1 = p1.getAlternatives(); while (i1.hasNext()) { List<Assertion> alt1 = i1.next(); - Iterator<List<Assertion>> i2 = p2.getAlternatives(); + Iterator<List<Assertion>> i2 = alternatives2.iterator(); if (!i2.hasNext() && alt1.isEmpty()) { return true; } while (i2.hasNext()) { List<Assertion> alt2 = i2.next(); - if (compatibleAlternatives(alt1, alt2)) { + if (compatibleAlternatives(alt1, alt2, budget)) { return true; } } @@ -184,15 +232,18 @@ public class PolicyIntersector { return intersect(p1, p2, false); } public Policy intersect(Policy p1, Policy p2, boolean allowDups) { + WorkBudget budget = new WorkBudget(); Policy compatible = new Policy(p1.getPolicyRegistry(), p1.getNamespace()); ExactlyOne eo = new ExactlyOne(compatible); + // normalize p2 exactly once (see compatiblePolicies) + List<List<Assertion>> alternatives2 = materializeAlternatives(p2); Iterator<List<Assertion>> i1 = p1.getAlternatives(); while (i1.hasNext()) { List<Assertion> alt1 = i1.next(); - Iterator<List<Assertion>> i2 = p2.getAlternatives(); + Iterator<List<Assertion>> i2 = alternatives2.iterator(); while (i2.hasNext()) { List<Assertion> alt2 = i2.next(); - All all = createCompatibleAlternatives(alt1, alt2, !allowDups); + All all = createCompatibleAlternatives(alt1, alt2, !allowDups, budget); if (all != null) { long nextSize = (long)eo.getPolicyComponents().size() + 1; AbstractPolicyOperator.checkMaximumAlternativeCount(nextSize, "intersection"); @@ -203,5 +254,13 @@ public class PolicyIntersector { return compatible; } + + private static List<List<Assertion>> materializeAlternatives(Policy policy) { + List<List<Assertion>> alternatives = new ArrayList<List<Assertion>>(); + for (Iterator<List<Assertion>> it = policy.getAlternatives(); it.hasNext();) { + alternatives.add(it.next()); + } + return alternatives; + } } diff --git a/src/test/java/org/apache/neethi/PolicyIntersectionDoSTest.java b/src/test/java/org/apache/neethi/PolicyIntersectionDoSTest.java index 7469496..07c21d4 100644 --- a/src/test/java/org/apache/neethi/PolicyIntersectionDoSTest.java +++ b/src/test/java/org/apache/neethi/PolicyIntersectionDoSTest.java @@ -21,13 +21,16 @@ package org.apache.neethi; import javax.xml.namespace.QName; +import org.apache.neethi.builders.PolicyContainingPrimitiveAssertion; import org.apache.neethi.builders.PrimitiveAssertion; +import org.apache.neethi.util.PolicyIntersector; import org.junit.Test; public class PolicyIntersectionDoSTest extends PolicyTestCase { private static final int ALTERNATIVES_PER_POLICY = 101; private static final int SAFE_ALTERNATIVES_PER_POLICY = 100; + private static final int LARGE_CANDIDATE_SET = 1500; @Test public void testIntersectionRejectsCartesianProductBeyondAlternativeBudget() { @@ -68,6 +71,19 @@ public class PolicyIntersectionDoSTest extends PolicyTestCase { assertTrue(((ExactlyOne)intersection.getFirstPolicyComponent()).getPolicyComponents().isEmpty()); } + @Test + public void testRecursiveCandidateSearchRequiresIntersectionStepBudget() { + Policy left = buildLateMatchNestedPolicy(LARGE_CANDIDATE_SET, false); + Policy right = buildLateMatchNestedPolicy(LARGE_CANDIDATE_SET, true); + + try { + new PolicyIntersector(true).intersect(left, right, true); + fail("Expected RuntimeException due to intersection step budget"); + } catch (RuntimeException ex) { + assertTrue(ex.getMessage().contains("intersection steps")); + } + } + private static Policy buildPolicyWithEmptyAlternatives(int alternatives) { Policy policy = new Policy(); ExactlyOne exactlyOne = new ExactlyOne(); @@ -91,4 +107,32 @@ public class PolicyIntersectionDoSTest extends PolicyTestCase { return policy; } + + /** + * Builds one policy alternative containing many same-QName + * policy-containing assertions. The nested policy leaf names are unique; + * reversing order on the second operand forces late unordered matches and + * maximizes recursive candidate search work. + */ + private static Policy buildLateMatchNestedPolicy(int size, boolean reversed) { + Policy policy = new Policy(); + ExactlyOne exactlyOne = new ExactlyOne(); + All all = new All(); + + for (int i = 0; i < size; i++) { + int idx = reversed ? size - 1 - i : i; + Policy nested = new Policy(); + nested.addPolicyComponent(new PrimitiveAssertion(new QName("urn:test", "leaf" + idx))); + + all.addPolicyComponent(new PolicyContainingPrimitiveAssertion( + new QName("urn:test", "n"), + false, + false, + nested)); + } + + exactlyOne.addPolicyComponent(all); + policy.addPolicyComponent(exactlyOne); + return policy; + } } \ No newline at end of file
