This is an automated email from the ASF dual-hosted git repository.
coheigea pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/ws-xmlschema.git
The following commit(s) were added to refs/heads/master by this push:
new be55147f Improve cycle detection in the schema walker (#127)
be55147f is described below
commit be55147fac5cae647c7894f913edbbc83c36e4c8
Author: Colm O hEigeartaigh <[email protected]>
AuthorDate: Mon Aug 24 14:32:53 2026 +0100
Improve cycle detection in the schema walker (#127)
---
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.
+ }
+ }
+}
