This is an automated email from the ASF dual-hosted git repository. coheigea pushed a commit to branch coheigea/xmlschema-walker in repository https://gitbox.apache.org/repos/asf/ws-xmlschema.git
commit 83fea1a1c2345e68faf21ef54e77ef1d117b8699 Author: Colm O hEigeartaigh <[email protected]> AuthorDate: Mon Aug 24 14:28:53 2026 +0100 Improve cycle detection in the schema walker --- THREAT-MODEL.md | 40 +++++- .../ws/commons/schema/walker/XmlSchemaScope.java | 38 ++++- .../ws/commons/schema/walker/XmlSchemaWalker.java | 58 ++++++-- .../schema/walker/CyclicSchemaWalkerTest.java | 160 +++++++++++++++++++++ 4 files changed, 278 insertions(+), 18 deletions(-) diff --git a/THREAT-MODEL.md b/THREAT-MODEL.md index 12664adf..4dc3afaa 100644 --- a/THREAT-MODEL.md +++ b/THREAT-MODEL.md @@ -179,7 +179,12 @@ A finding is in-model only if it reaches a row marked **yes**. `DocumentBuilderFactory` decided that. In-model for whatever the schema-model semantics imply about the DOM contents. - **`xmlschema-walker`**: in-model when the visitor walks an - attacker-controlled schema. The walker is purely in-memory. + attacker-controlled schema. The walker is purely in-memory. Before cycle + detection, malformed but parseable schemas could create cycles in type + derivation, substitution groups, model groups, or attribute groups and + recurse until `StackOverflowError`. The walker now tracks these expansion + paths and rejects cyclic re-entry with `XmlSchemaException`; recursion that + crosses an element declaration remains supported. - **`XmlSchemaPathFinder`**: in-model when caller-supplied SAX events are matched against an attacker-controlled schema. Its backtracking work is bounded per document by configurable decision-point and @@ -209,7 +214,9 @@ A finding is in-model only if it reaches a row marked **yes**. *(inferred — §14 Q7)*. - **Memory**: schemas are held in memory; XMLSchema has no built-in ceiling on schema-document size, number of imports, or import-graph - depth *(inferred — §14 Q8)*. + depth *(inferred — §14 Q8)*. The walker has active-path cycle detection + for the schema expansion graphs it traverses, but large acyclic schemas + may still consume substantial memory and CPU. - **System properties**: `org.apache.ws.commons.schema.extension_registry` is consulted at `XmlSchemaCollection` construction time, and the named class is loaded via `Class.forName()` *(documented: @@ -299,6 +306,10 @@ feature is the intended defense and is sufficient) or `MODEL-GAP` - No documented limit on schema-document size *(inferred — §14 Q8)*. - No documented limit on the import-graph depth or breadth *(inferred — §14 Q8)*. +- Walker expansion cycles are rejected for type derivation, substitution + groups, model groups, and attribute groups. This prevents recursive + stack exhaustion for malformed but parseable schemas; it is not a general + limit on the size or cost of an acyclic schema. - No rate limit on URL fetches when following `xs:import` *(inferred — §14 Q12)*. - `XmlSchemaPathFinder` bounds decision points and replayed events per @@ -375,6 +386,19 @@ feature is the intended defense and is sufficient) or `MODEL-GAP` - **Severity**: **correctness-only**. - *(inferred — §14 Q17)* +### P5 — Bounded recursive schema walking + +- **Condition**: an attacker-controlled schema is passed to + `XmlSchemaWalker.walk(XmlSchemaElement)`. +- **Property**: cyclic type derivation, substitution-group, model-group, + and attribute-group expansions terminate with `XmlSchemaException` rather + than recursing indefinitely. Legal recursive content that passes through + an element declaration remains walkable. +- **Violation symptom**: a parseable schema causes the walker to recurse + until `StackOverflowError` or another resource-exhaustion failure. +- **Severity**: **medium** availability impact when the embedding + application accepts untrusted schemas *(inferred — §14 Q23)*. + ## §9 Security properties the project does *not* provide State each plainly so a triager can route an inbound report to the @@ -452,7 +476,8 @@ matching disclaimer. - **Billion-laughs / quadratic blowup** — partially mitigated by `FEATURE_SECURE_PROCESSING=true`, but not universally. - **Schema-amplification DoS** — a deeply nested or heavily-recursive - schema can exhaust memory. + acyclic schema can exhaust memory or CPU; cyclic walker expansion is + rejected as described in §8 P5. - **Confused-deputy fetch via untrusted `baseUri` + relative `schemaLocation`** — the operator-supplied base URI is trusted. @@ -760,6 +785,14 @@ sees recur in inbound reports. *(meta — §11a)* **Q22.** What kind of change to XMLSchema should trigger a revision (proposed list in §12 — confirm or correct)? *(meta — §12)* +**Q23.** `xmlschema-walker` cycle handling: should rejection of cyclic +type derivation, substitution-group, model-group, and attribute-group +expansions be treated as a claimed medium-severity availability property +for attacker-controlled schemas? Proposed: **yes**; malformed but +parseable cycles must terminate with `XmlSchemaException`, while legal +recursive content through element declarations remains supported. *(maps +to §4, §6, §8 P5)* + --- ## Appendix: SECURITY.md / website → §x back-map @@ -781,3 +814,4 @@ source comments. The project website is | `xmlschema-core/src/main/java/.../resolver/URIResolver.java` | Resolver interface — caller-pluggable | §2 caller-roles, §10 item 1 | | `xmlschema-walker/src/main/java/.../docpath/DomBuilderFromSax.java` line 81 | `factory.setFeature(XMLConstants.FEATURE_SECURE_PROCESSING, TRUE)` | §5a, §8 P2 | | `xmlschema-walker/src/main/java/.../docpath/XmlSchemaPathFinder.java` | Configurable per-document limits on decision points and replayed events | §4, §5a, §6, §12 | +| `xmlschema-walker/src/main/java/.../walker/XmlSchemaWalker.java` and `XmlSchemaScope.java` | Active-path cycle detection for schema expansion | §4, §6, §8 P5 | diff --git a/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/walker/XmlSchemaScope.java b/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/walker/XmlSchemaScope.java index 475f5aab..fcd7b674 100644 --- a/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/walker/XmlSchemaScope.java +++ b/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/walker/XmlSchemaScope.java @@ -21,8 +21,10 @@ package org.apache.ws.commons.schema.walker; import java.util.ArrayList; import java.util.Collection; +import java.util.Collections; import java.util.HashMap; import java.util.HashSet; +import java.util.IdentityHashMap; import java.util.List; import java.util.Map; import java.util.Set; @@ -42,6 +44,7 @@ import org.apache.ws.commons.schema.XmlSchemaComplexContentRestriction; import org.apache.ws.commons.schema.XmlSchemaComplexType; import org.apache.ws.commons.schema.XmlSchemaContent; import org.apache.ws.commons.schema.XmlSchemaElement; +import org.apache.ws.commons.schema.XmlSchemaException; import org.apache.ws.commons.schema.XmlSchemaFacet; import org.apache.ws.commons.schema.XmlSchemaParticle; import org.apache.ws.commons.schema.XmlSchemaSequence; @@ -71,6 +74,8 @@ final class XmlSchemaScope { private XmlSchemaParticle child; private XmlSchemaAnyAttribute anyAttr; private Set<QName> userRecognizedTypes; + private Set<XmlSchemaType> typesInProgress; + private final Set<QName> attributeGroupsInProgress = new HashSet<QName>(); /** * Initialization of members to be filled in during the walk. @@ -87,8 +92,9 @@ final class XmlSchemaScope { this.schemasByNamespace = child.schemasByNamespace; this.scopeCache = child.scopeCache; this.userRecognizedTypes = child.userRecognizedTypes; + this.typesInProgress = child.typesInProgress; - walk(type); + walkWithCycleCheck(type); } /** @@ -104,8 +110,22 @@ final class XmlSchemaScope { schemasByNamespace = xmlSchemasByNamespace; this.scopeCache = scopeCache; this.userRecognizedTypes = userRecognizedTypes; + this.typesInProgress = + Collections.newSetFromMap(new IdentityHashMap<XmlSchemaType, Boolean>()); - walk(type); + walkWithCycleCheck(type); + } + + private void walkWithCycleCheck(XmlSchemaType type) { + if (!typesInProgress.add(type)) { + throw new XmlSchemaException("Cyclic type derivation detected involving type " + + getName(type, "{Anonymous}") + '.'); + } + try { + walk(type); + } finally { + typesInProgress.remove(type); + } } /** @@ -494,7 +514,19 @@ final class XmlSchemaScope { if (attrGroup == null) { attrGroup = schemasByNamespace.getAttributeGroupByName(groupRef.getTargetQName()); } - return getAttributesOf(attrGroup); + + final QName groupName = groupRef.getTargetQName(); + if ((groupName != null) && !attributeGroupsInProgress.add(groupName)) { + throw new XmlSchemaException("Cyclic attribute group reference detected involving " + + groupName + '.'); + } + try { + return getAttributesOf(attrGroup); + } finally { + if (groupName != null) { + attributeGroupsInProgress.remove(groupName); + } + } } private ArrayList<XmlSchemaAttrInfo> getAttributesOf(XmlSchemaAttributeGroup attrGroup) { diff --git a/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/walker/XmlSchemaWalker.java b/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/walker/XmlSchemaWalker.java index 4c978502..4a906677 100644 --- a/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/walker/XmlSchemaWalker.java +++ b/xmlschema-walker/src/main/java/org/apache/ws/commons/schema/walker/XmlSchemaWalker.java @@ -22,6 +22,7 @@ package org.apache.ws.commons.schema.walker; import java.util.ArrayList; import java.util.Collection; import java.util.HashMap; +import java.util.HashSet; import java.util.IdentityHashMap; import java.util.List; import java.util.Map; @@ -38,6 +39,7 @@ import org.apache.ws.commons.schema.XmlSchemaChoiceMember; import org.apache.ws.commons.schema.XmlSchemaCollection; import org.apache.ws.commons.schema.XmlSchemaComplexType; import org.apache.ws.commons.schema.XmlSchemaElement; +import org.apache.ws.commons.schema.XmlSchemaException; import org.apache.ws.commons.schema.XmlSchemaGroup; import org.apache.ws.commons.schema.XmlSchemaGroupParticle; import org.apache.ws.commons.schema.XmlSchemaGroupRef; @@ -45,7 +47,6 @@ import org.apache.ws.commons.schema.XmlSchemaParticle; import org.apache.ws.commons.schema.XmlSchemaSequence; import org.apache.ws.commons.schema.XmlSchemaSequenceMember; import org.apache.ws.commons.schema.XmlSchemaType; -import org.apache.ws.commons.schema.utils.XmlSchemaNamed; /** * Walks an {@link XmlSchema} from a starting {@link XmlSchemaElement}, @@ -61,6 +62,8 @@ public final class XmlSchemaWalker { private final SchemasByNamespace schemasByNamespace; private final Map<QName, XmlSchemaScope> scopeCache; private final IdentityHashMap<XmlSchemaType, XmlSchemaType> visitedTypes; + private Set<QName> substGroupsInProgress = new HashSet<QName>(); + private Set<QName> groupsInProgress = new HashSet<QName>(); /** * Initializes the {@link XmlSchemaWalker} with the @@ -147,6 +150,8 @@ public final class XmlSchemaWalker { public void clear() { scopeCache.clear(); visitedTypes.clear(); + substGroupsInProgress.clear(); + groupsInProgress.clear(); } /** @@ -301,7 +306,16 @@ public final class XmlSchemaWalker { // 6. Walk the child groups and elements (if any), depth-first. final XmlSchemaParticle child = scope.getParticle(); if (child != null) { - walk(child); + final Set<QName> outerSubstGroupsInProgress = substGroupsInProgress; + final Set<QName> outerGroupsInProgress = groupsInProgress; + substGroupsInProgress = new HashSet<QName>(); + groupsInProgress = new HashSet<QName>(); + try { + walk(child); + } finally { + substGroupsInProgress = outerSubstGroupsInProgress; + groupsInProgress = outerGroupsInProgress; + } } } @@ -320,12 +334,21 @@ public final class XmlSchemaWalker { // 8. Now handle substitute elements, if any. if (substitutes != null) { - for (XmlSchemaElement substitute : substitutes) { - walk(substitute); + final QName substGroupName = getElementQName(substGroupElem); + if (!substGroupsInProgress.add(substGroupName)) { + throw new XmlSchemaException("Cyclic substitution group detected involving " + + substGroupName + '.'); } + try { + for (XmlSchemaElement substitute : substitutes) { + walk(substitute); + } - for (XmlSchemaVisitor visitor : visitors) { - visitor.onExitSubstitutionGroup(substGroupElem); + for (XmlSchemaVisitor visitor : visitors) { + visitor.onExitSubstitutionGroup(substGroupElem); + } + } finally { + substGroupsInProgress.remove(substGroupName); } } } @@ -333,14 +356,25 @@ public final class XmlSchemaWalker { private void walk(XmlSchemaParticle particle) { if (particle instanceof XmlSchemaGroupRef) { XmlSchemaGroupRef groupRef = (XmlSchemaGroupRef)particle; - XmlSchemaGroupParticle group = groupRef.getParticle(); - if (group == null) { - XmlSchemaGroup g = schemasByNamespace.getGroupByName(groupRef.getRefName()); - if (g != null) { - group = g.getParticle(); + final QName groupName = groupRef.getRefName(); + if ((groupName != null) && !groupsInProgress.add(groupName)) { + throw new XmlSchemaException("Cyclic group reference detected involving group " + + groupName + '.'); + } + try { + XmlSchemaGroupParticle group = groupRef.getParticle(); + if (group == null) { + XmlSchemaGroup g = schemasByNamespace.getGroupByName(groupName); + if (g != null) { + group = g.getParticle(); + } + } + walk(group, groupRef.getMinOccurs(), groupRef.getMaxOccurs()); + } finally { + if (groupName != null) { + groupsInProgress.remove(groupName); } } - walk(group, groupRef.getMinOccurs(), groupRef.getMaxOccurs()); } else if (particle instanceof XmlSchemaGroupParticle) { walk((XmlSchemaGroupParticle)particle, particle.getMinOccurs(), particle.getMaxOccurs()); diff --git a/xmlschema-walker/src/test/java/org/apache/ws/commons/schema/walker/CyclicSchemaWalkerTest.java b/xmlschema-walker/src/test/java/org/apache/ws/commons/schema/walker/CyclicSchemaWalkerTest.java new file mode 100644 index 00000000..c29e0f90 --- /dev/null +++ b/xmlschema-walker/src/test/java/org/apache/ws/commons/schema/walker/CyclicSchemaWalkerTest.java @@ -0,0 +1,160 @@ +/** + * 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.ws.commons.schema.walker; + +import java.io.StringReader; + +import javax.xml.namespace.QName; + +import org.apache.ws.commons.schema.XmlSchemaCollection; +import org.apache.ws.commons.schema.XmlSchemaElement; +import org.apache.ws.commons.schema.XmlSchemaException; + +import org.junit.Assert; +import org.junit.Test; + +public class CyclicSchemaWalkerTest extends Assert { + + private static final String XSD_HEADER = + "<xs:schema xmlns:xs=\"http://www.w3.org/2001/XMLSchema\""; + + " xmlns:tns=\"urn:cyclic\" targetNamespace=\"urn:cyclic\">"; + + private XmlSchemaElement load(String schemaBody, String elementName, + XmlSchemaCollection collection) { + collection.read(new StringReader(XSD_HEADER + schemaBody + "</xs:schema>")); + XmlSchemaElement element = + collection.getElementByQName(new QName("urn:cyclic", elementName)); + assertNotNull(element); + return element; + } + + @Test + public void testRecursiveContentModelThroughElementWalks() { + XmlSchemaCollection collection = new XmlSchemaCollection(); + XmlSchemaElement element = + load("<xs:group name=\"content\"><xs:sequence>" + + "<xs:element ref=\"tns:section\"/>" + + "</xs:sequence></xs:group>" + + "<xs:element name=\"section\"><xs:complexType><xs:sequence>" + + "<xs:group ref=\"tns:content\" minOccurs=\"0\"/>" + + "</xs:sequence></xs:complexType></xs:element>" + + "<xs:element name=\"root\"><xs:complexType><xs:sequence>" + + "<xs:group ref=\"tns:content\"/>" + + "</xs:sequence></xs:complexType></xs:element>", + "root", collection); + + new XmlSchemaWalker(collection).walk(element); + } + + @Test + public void testNestedValidSubstitutionGroupReferenceWalks() { + XmlSchemaCollection collection = new XmlSchemaCollection(); + XmlSchemaElement element = + load("<xs:complexType name=\"HeadType\"><xs:sequence>" + + "<xs:element name=\"leaf\" type=\"xs:string\" minOccurs=\"0\"/>" + + "</xs:sequence></xs:complexType>" + + "<xs:complexType name=\"BranchType\"><xs:complexContent>" + + "<xs:extension base=\"tns:HeadType\"><xs:sequence>" + + "<xs:element ref=\"tns:node\" minOccurs=\"0\"/>" + + "</xs:sequence></xs:extension>" + + "</xs:complexContent></xs:complexType>" + + "<xs:element name=\"node\" type=\"tns:HeadType\"/>" + + "<xs:element name=\"branch\" type=\"tns:BranchType\"" + + " substitutionGroup=\"tns:node\"/>", + "node", collection); + + new XmlSchemaWalker(collection).walk(element); + } + + @Test + public void testSelfSubstitutionGroupIsRejected() { + XmlSchemaCollection collection = new XmlSchemaCollection(); + XmlSchemaElement element = + load("<xs:element name=\"a\" type=\"xs:string\"" + + " substitutionGroup=\"tns:a\"/>", "a", collection); + + assertThrowsXmlSchemaException(element, collection); + } + + @Test + public void testMutualSubstitutionGroupCycleIsRejected() { + XmlSchemaCollection collection = new XmlSchemaCollection(); + XmlSchemaElement element = + load("<xs:element name=\"a\" type=\"xs:string\"" + + " substitutionGroup=\"tns:b\"/>" + + "<xs:element name=\"b\" type=\"xs:string\"" + + " substitutionGroup=\"tns:a\"/>", "a", collection); + + assertThrowsXmlSchemaException(element, collection); + } + + @Test + public void testCyclicGroupReferencesAreRejected() { + XmlSchemaCollection collection = new XmlSchemaCollection(); + XmlSchemaElement element = + load("<xs:group name=\"g1\"><xs:sequence><xs:group ref=\"tns:g2\"/>" + + "</xs:sequence></xs:group>" + + "<xs:group name=\"g2\"><xs:sequence><xs:group ref=\"tns:g1\"/>" + + "</xs:sequence></xs:group>" + + "<xs:element name=\"root\"><xs:complexType><xs:sequence>" + + "<xs:group ref=\"tns:g1\"/>" + + "</xs:sequence></xs:complexType></xs:element>", + "root", collection); + + assertThrowsXmlSchemaException(element, collection); + } + + @Test + public void testCyclicTypeDerivationIsRejected() { + XmlSchemaCollection collection = new XmlSchemaCollection(); + XmlSchemaElement element = + load("<xs:complexType name=\"A\"><xs:complexContent>" + + "<xs:extension base=\"tns:A\"/>" + + "</xs:complexContent></xs:complexType>" + + "<xs:element name=\"e\" type=\"tns:A\"/>", "e", collection); + + assertThrowsXmlSchemaException(element, collection); + } + + @Test + public void testCyclicAttributeGroupReferencesAreRejected() { + XmlSchemaCollection collection = new XmlSchemaCollection(); + XmlSchemaElement element = + load("<xs:attributeGroup name=\"ag1\"><xs:attributeGroup ref=\"tns:ag2\"/>" + + "</xs:attributeGroup>" + + "<xs:attributeGroup name=\"ag2\"><xs:attributeGroup ref=\"tns:ag1\"/>" + + "</xs:attributeGroup>" + + "<xs:complexType name=\"C\"><xs:attributeGroup ref=\"tns:ag1\"/>" + + "</xs:complexType>" + + "<xs:element name=\"e\" type=\"tns:C\"/>", "e", collection); + + assertThrowsXmlSchemaException(element, collection); + } + + private void assertThrowsXmlSchemaException(XmlSchemaElement element, + XmlSchemaCollection collection) { + try { + new XmlSchemaWalker(collection).walk(element); + fail("Expected cyclic schema expansion to be rejected."); + } catch (XmlSchemaException expected) { + // Expected: malformed schema expansion is bounded by the walker. + } + } +}
