networknt / networknt/json-schema-validator
Exponential validation cost: (schema node, instance node) pairs re-evaluated once per evaluation path
Nobody has claimed this yet.
- Dominant language
- Java
- Stars
- 1.1k
- Forks
- 352
- Avg merge
- 3d 13h
- Merged PRs (30d)
- 5
Description
A 43-byte instance OOMs validate() on 3.0.6 with -Xmx2g, against a fixed 165-byte schema.
Cost is 2^depth because each (schema node, instance node) pair is re-evaluated once per evaluation
path. At depth 20 that's 2,097,152 errors covering 2 distinct (schemaLocation, instanceLocation)
pairs.
Filing as a perf issue: I checked ~600 real OpenAPI specs and none had a
request-body schema with this shape. I wouldn't rule it out completely.
Reproduce
String schema = "{\"$ref\":\"#/$defs/n\",\"$defs\":{\"n\":{\"anyOf\":["
+ "{\"type\":\"array\",\"items\":{\"$ref\":\"#/$defs/n\"},\"minItems\":0},"
+ "{\"type\":\"array\",\"items\":{\"$ref\":\"#/$defs/n\"},\"maxItems\":99}]}}}";
String instance = "[".repeat(d) + "\"x\"" + "]".repeat(d); // [[[["x"]]]]
SchemaRegistry registry = SchemaRegistry.withDefaultDialect(SpecificationVersion.DRAFT_2020_12);
Schema s = registry.getSchema(schema);
s.validate(instance, InputFormat.JSON);
depth instance validate errors
19 41 B 354 ms 1,048,576
20 43 B 694 ms 2,097,152
21 45 B 5,746 ms 4,194,304
22 47 B OutOfMemoryError
Both anyOf arms accept an array, so both descend into the same child, twice per parent all the way
down. jstack mid-run is just AnyOfValidator / Schema.validate / RefValidator / ItemsValidator
repeating, RUNNABLE. getSchema is flat at 0 ms; it's all in validate.
A level costs 2 bytes, so more heap buys 2 characters per doubling.
Affected versions
Same schema and instance, -Xmx2g:
| version | API | OOM at |
|---|---|---|
| 1.5.4 | JsonSchemaFactory |
depth 19, 41 B |
| 2.0.4 | SchemaRegistry |
depth 22, 47 B |
| 3.0.0 | SchemaRegistry |
depth 22, 47 B |
| 3.0.3 | SchemaRegistry |
depth 22, 47 B |
| 3.0.6 | SchemaRegistry |
depth 22, 47 B |
Existing config options, measured
depth instance DEFAULT BOOLEAN FLAG failFast+BOOLEAN
20 43 B 857 ms 972 ms 615 ms 697 ms
21 45 B 5961 ms 6492 ms 6156 ms 5706 ms
22 47 B OutOfMemoryError (all four)
failFast still returns 2,097,152 errors at depth 20, registry or execution context. Makes sense
given anyOf: a failing arm is a rejected candidate, not an error, so there's no first error to
return on. The output formats bound what's returned, but allocation is per node visited — under
BOOLEAN an Error is still built per failed arm and dropped. cacheRefs bounds compilation, which
isn't where the cost is.
Which schemas are affected
Needs two or more anyOf/oneOf arms that can match the same node, descend into the same child
slot, and sit in a $ref cycle.
Also happens with kestra's published schema
kestra 0.19.0 from SchemaStore, 4.1 MB, 733 definitions.
#/definitions/io.kestra.core.models.conditions.Condition is a oneOf where NotCondition and
OrCondition both declare conditions as {"type":"array","items":{"oneOf":[... Condition ...]}}.
Nested conditions arrays, 17 bytes per level:
depth instance validate errors
14 250 B 365 ms 1,179,613
15 267 B 769 ms 2,359,261
16 284 B OutOfMemoryError
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the supplied Java reproducer and profile the repeated stack through AnyOfValidator, Schema.validate, RefValidator, and ItemsValidator; getSchema is not implicated. Compare validation behavior and allocations at increasing depths, then verify that equivalent recursive paths no longer cause exponential cost or OutOfMemoryError while validation results remain correct.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100