networknt / networknt/json-schema-validator

Exponential validation cost: (schema node, instance node) pairs re-evaluated once per evaluation path

Open
#1,276 0 comments 0 reactions 0 assignees View on GitHub

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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.