infinite loop with Constraint::CHECK_MODE_APPLY_DEFAULTS

[mathroc]

I've found an issue, with some schema, the validator will go into an infinite loop and eventually terminate when the allowed memory is exhausted, you can reproduce the issue with this code :

<?php

include_once __DIR__."/../vendor/autoload.php";

$validator = new \JsonSchema\Validator();

$data = [];
$schema = (object)['$ref' => 'http://json-schema.org/draft-04/schema'];

echo __LINE__, PHP_EOL;

$validator->validate($data, $schema);

echo __LINE__, PHP_EOL;

$validator->validate($data, $schema, \JsonSchema\Constraints\Constraint::CHECK_MODE_APPLY_DEFAULTS);

echo __LINE__, PHP_EOL;

I'm not sure yet what is causing this. I'll guess a infinite recursion has been introduced in UndefinedConstraint::validateCommonProperties. I'll try to make another reproduction of the bug with a smaller schema

[erayd]

Thanks for finding this! Will see if I can get that fixed this morning; infinite recursion is not good!

[erayd]

Have nailed it down to this so far as a minimal test case:

{
    "properties": {
        "propertyOne": {
            "anyOf": [
                { "$ref": "#" }
            ],
            "default": {}
        }
    }
}

[mathroc]

good job finding the small schema reproducing the issue, my attempts failed because when I replaced (object)['$ref' => 'http://json-schema.org/draft-04/schema'] with its content it was not blocking anymore 😕

and then work got in the way ;)

[erayd]

Yeah, there's some bloody weird behavior happening in there. Still haven't found the root cause, although I'm getting there. Working on several things at once, so it's taking a while.

[erayd]

Have located and fixed an unrelated bug with resolving references - @bighappyface, do you want it (and any other bugs I might find along the way to sorting this one) in the same PR, or do you want a separate PR per bug?

[erayd]

OK, this is really nutty. I'm currently buried in the depths of SchemaStorage, and resolveRef() seems to be taking a file URI, converting it to a schema, then converting it back to a URI again. As far as I can tell, this is not how that method is supposed to behave!

[erayd]

@mathroc @shmax @bighappyface Is there any scenario where a $ref to # is ever valid, and does not result in an infinite recursion if fully dereferenced?

[shmax]

Sorry, not an expert on that stuff. If you can provide a minimal code snippet I can help debug.

[erayd]

The minimal schema example I posted above is all I've got at the moment unfortunately. If you can be a bit more specific I can try to isolate bits that might help.

My hope is that if such a reference is never legal, then I can kill the problem when it sees the reference for the first time. If it's legal, then this will be much more complicated to fix.

[shmax]

Fair enough. If you haven't sorted it out by tomorrow evening I'll fire up the debugger and help research.

[erayd]

Thanks! :-)

[mathroc]

@mathroc @shmax @bighappyface Is there any scenario where a $ref to # is ever valid, and does not result in an infinite recursion if fully dereferenced?

not sure what you mean. a recursive schema is valid (eg: any tree structure). It was added in #277 maybe @jojo1981 or @araines can help finding the issue here ?

[erayd]

I know they're valid - I'm not asking about recursive schemas in general; I'm asking very specifically about whether the single case of a schema that infinitely recurses the root is ever valid (and if it is, is it ever something that anybody could actually use).

That PR looks very useful - thank you for that. I have some more reading to do!

[mathroc]

well I would probably represent a binary tree like this:

{
    "type": "object",
    "properties": {
        "value": {
            "type": "integer"
        },
        "left": {
            "$ref": "#"
        },
        "right": {
            "$ref": "#"
        }
    },
    "required": "value"
}

[erayd]

@mathroc Thank you - exactly what I needed :-).

Complicated fix it is then!

[erayd]

Although thinking about this a bit more, lazy dereferencing should be preventing this problem before it becomes one, so I've clearly got some more hunting to do. It's also quite possible that I've done something stupid in my own code and just haven't realised it yet.

[mathroc]

wondering about something, it might be wrong and unrelated but, in case it can help..

validateCommonProperties is iterating over properties and items, is it really needed ? my guess is that each property and item would eventually be checked and their defaults would then be applied in the "leaf" case.

even if that's the case, I don't see what would cause an infinite recursion in validateCommonProperties, just saying what comes to mind

I've now read #349 but cannot understand what is going wrong here, however now that I have taken a look at the code I have another question / suggestion, I added it as code review here : https://github.com/justinrainbow/json-schema/pull/349/files#r103655365 (not sure if you receive notification once a PR is closed)

[mathroc]

keeping just this part of the code still trigger the issue :

        // Apply default values from schema
        if ($this->factory->getConfig(self::CHECK_MODE_APPLY_DEFAULTS)) {
            if ($this->getTypeCheck()->isObject($value) && isset($schema->properties)) {
                // $value is an object, so apply default properties if defined
                // foreach ($schema->properties as $i => $propertyDefinition) {
                //     if (!$this->getTypeCheck()->propertyExists($value, $i) && isset($propertyDefinition->default)) {
                //         if (is_object($propertyDefinition->default)) {
                //             $this->getTypeCheck()->propertySet($value, $i, clone $propertyDefinition->default);
                //         } else {
                //             $this->getTypeCheck()->propertySet($value, $i, $propertyDefinition->default);
                //         }
                //     }
                // }
            } elseif ($this->getTypeCheck()->isArray($value)) {
                // if (isset($schema->properties)) {
                //     // $value is an array, but default properties are defined, so treat as assoc
                //     foreach ($schema->properties as $i => $propertyDefinition) {
                //         if (!isset($value[$i]) && isset($propertyDefinition->default)) {
                //             if (is_object($propertyDefinition->default)) {
                //                 $value[$i] = clone $propertyDefinition->default;
                //             } else {
                //                 $value[$i] = $propertyDefinition->default;
                //             }
                //         }
                //     }
                // } elseif (isset($schema->items)) {
                //     // $value is an array, and default items are defined - treat as plain array
                //     foreach ($schema->items as $i => $itemDefinition) {
                //         if (!isset($value[$i]) && isset($itemDefinition->default)) {
                //             if (is_object($itemDefinition->default)) {
                //                 $value[$i] = clone $itemDefinition->default;
                //             } else {
                //                 $value[$i] = $itemDefinition->default;
                //             }
                //         }
                //     }
                // }
            } elseif (($value instanceof self || $value === null) && isset($schema->default)) {
                // $value is a leaf, not a container - apply the default directly
                $value = is_object($schema->default) ? clone $schema->default : $schema->default;
            }
        }

and commenting the last $value = is_object($schema->default) ? clone $schema->default : $schema->default; prevent it

and not setting the defaults (when they're objects) prevent the issue too, so this "wworks (does not end up crashing):

        // Apply default values from schema
        if ($this->factory->getConfig(self::CHECK_MODE_APPLY_DEFAULTS)) {
            if ($this->getTypeCheck()->isObject($value) && isset($schema->properties)) {
                // $value is an object, so apply default properties if defined
                foreach ($schema->properties as $i => $propertyDefinition) {
                    if (!$this->getTypeCheck()->propertyExists($value, $i) && isset($propertyDefinition->default)) {
                        if (is_object($propertyDefinition->default)) {
                            // $this->getTypeCheck()->propertySet($value, $i, clone $propertyDefinition->default);
                        } else {
                            $this->getTypeCheck()->propertySet($value, $i, $propertyDefinition->default);
                        }
                    }
                }
            } elseif ($this->getTypeCheck()->isArray($value)) {
                if (isset($schema->properties)) {
                    // $value is an array, but default properties are defined, so treat as assoc
                    foreach ($schema->properties as $i => $propertyDefinition) {
                        if (!isset($value[$i]) && isset($propertyDefinition->default)) {
                            if (is_object($propertyDefinition->default)) {
                                // $value[$i] = clone $propertyDefinition->default;
                            } else {
                                $value[$i] = $propertyDefinition->default;
                            }
                        }
                    }
                } elseif (isset($schema->items)) {
                    // $value is an array, and default items are defined - treat as plain array
                    foreach ($schema->items as $i => $itemDefinition) {
                        if (!isset($value[$i]) && isset($itemDefinition->default)) {
                            if (is_object($itemDefinition->default)) {
                                // $value[$i] = clone $itemDefinition->default;
                            } else {
                                $value[$i] = $itemDefinition->default;
                            }
                        }
                    }
                }
            } elseif (($value instanceof self || $value === null) && isset($schema->default)) {
                // $value is a leaf, not a container - apply the default directly
                // $value = is_object($schema->default) ? clone $schema->default : $schema->default;
            }
        }

[erayd]

@mathroc It's needed; attempting to apply everything at the leaf stage will result in a lot of failed tests, unless you have a better idea for how to do the leaf sets. In addition, there are precedence rules, which are the reason for the current code layout:

1. If it's an object, then we don't need to care about anything else and can just apply the defaults
2. If it's an array, but there is a properties attribute on the schema, then the schema wants us to treat this like an object - so do that.
3. If it's an array, but properties is not set, then treat it like an array, and fill from items.
4. If it's neither an object nor an array, then it must be a leaf, so fill it directly as a fallback case.

Yes, I do receive emails for closed PR stuff. I did have it using LooseTypeCheck at one point, then put it back while I was writing test. Suspect I just forgot to put it back; there's no good reason to not use it, so I've done that. Thanks for spotting it.

[erayd]

I've already done the steps you posted the code for above; that was one of the first things I tried. Am well beyond that now. I appreciate you tackling it though; a fresh pair of eyes never hurts, and you may well spot something that I've missed.

[erayd]

@mathroc Have opened #365 to aid collaboration on this, so we're at least looking at the same code.

[erayd]

OK, so I've gotten to the bottom of this, and I'm gonna say it... I don't think that this is a bug.

After spending hours combing the code and bashing my head against a metaphorical brick wall when tracing stuff yielded no problematic code that could cause this, I went back to the minimal schema example and ran it in my head. Then I compared it to where the problem occurred in the original schema the bug was reported against. And as it turns out, assuming I'm understanding the spec correctly, the problem has been the schema all along.

{
    "properties": {
        "propertyOne": {
            "anyOf": [
                { "$ref": "#" }
            ],
            "default": {}
        }
    }
}

When this is dereferenced, it yields infinitely nested instances of the root object. Which is legal, and this library does lazy-dereferencing, so it's theoretically not a problem.

EXCEPT: The way anyOf (and allOf / oneOf) works, is that it takes each sub-item and validates $value against it. When combined with setting defaults, the result is essentially this:

1. We are checking the validation of an empty object against the schema root.
2. propertyOne is not set, so create it and set the value to {}.
3. Validate propertyOne (an empty object) against the schema root (i.e. goto (1)).

The result is an infinitely nested set of propertyOne objects, which is exactly what the schema mandates should occur. This is the cause of the infinite recursion. The same behavior can be seen when trying to validate using the draft schema as per the original bug report, as it contains a similar structure.

So... while clearly both legal and desired behavior according to the schema, obeying an instruction to create an infinitely nested set of objects is clearly not a good outcome for anyone who actually wants their validation to finish.

@mathroc @shmax @bighappyface Is this something that should be left caveat emptor, and it's the user's responsibility not to try and set defaults with a schema that deliberately pulls this kind of stunt, or is it better to come up with some kind of detection mechanism to notice and abort infinitely recursive situations?

[mathroc]

ok! I think I understand what you mean.
I was wondering how the we could validate against such a schema and not be able to apply the defaults. I believe it's because the properties are not required but the lib is applying its default value anyway. Is that intended ? could we turn that off ? (with a flag ?)

actually I think it should default to not create properties that are not required because it's doing more than "APPLY_DEFAULTS" and I'm not sure a flag to force creation of not required properties is needed. that way schema that are "validatable" are always safe

what do you think?

[erayd]

It's intended, because the spec doesn't say anything about only-apply-defaults-if-required, so assuming it seems dangerous.

My current thoughts are to implement some kind of mechanism that makes setting defaults-on-defaults a noop (maybe by remembering the path somewhere?), but I haven't finished considering the ramifications of doing this and whether it's a good idea.

[erayd]

I've filed an issue against the spec - in there, I've asked if there's a recommended way of dealing with this situation. If there is I think we should follow that - if not, then I guess we'll need to roll our own solution, whatever form that ends up taking.

[mathroc]

good point asking on json-schema-org/json-schema-spec. I was thinking that this CHECK_MODE_APPLY_DEFAULTS was an extension of the validation but not defined by the spec.

are you aware of other validation libraries doing this ?

In my mind default was only here for things like json-schema-form/angular-schema-form not for validation. but I have no clue if that's the case or not

[erayd]

I'm not particularly familiar with validation libraries other than this one, so I really can't say. I did search for previous issues on the spec repository regarding this and found nothing.

The schema recommends validating defaults, so unless I'm badly misunderstanding something this is actually the intended behavior... and if so, then the intended behavior violates the spec.

[bighappyface]

Here is how some of this was addressed in the past:

#184

https://github.com/edisonthk/json-schema/blob/0e895e7e6b7be3e53d7038a36161fa9f5be5cbe6/src/JsonSchema/RefResolver.php#L31

Interesting stuff...

[mathroc]

@bighappyface it would prevent exhausting the memory (or reaching the nested call limit) but it would also build a partial recursive structure on the first "recursive default" found and might not apply defaults found afterward

My current thoughts are to implement some kind of mechanism that makes setting defaults-on-defaults a noop (maybe by remembering the path somewhere?), but I haven't finished considering the ramifications of doing this and whether it's a good idea.

@erayd not sure what would the resulting data look like but this might work !

@erayd is there anything wrong with only applying defaults for required properties ? I can't think of a use case where I could not make the properties required I need it. the only downside I can think of is that the tool generating the documentation (eg: interagent/prmd) will have to understand that required properties with default should not appear as required for the user (but that's quite easy to do, at least for prmd)

[erayd]

@mathroc

not sure what would the resulting data look like but this might work !

Unless you have nested defaults, it would look normal, just as you'd expect with all defaults applied. If you defined nested defaults, then it would become noncompliant in order to break the recursion situations - but unfortunately would also catch non-recursive situations with nested defaults, which isn't ideal. I'd like to come up with a better approach that actually detects the recursion if I can think of a sane way to do it (I haven't thought of one yet; currently considering how to utilise analysis of the path for this).

Is there anything wrong with only applying defaults for required properties ? I can't think of a use case where I could not make the properties required I need it. the only downside I can think of is that the tool generating the documentation (eg: interagent/prmd) will have to understand that required properties with default should not appear as required for the user (but that's quite easy to do, at least for prmd)

Yes - behaving like this is risky, because it assumes that the schema author knows we only apply required defaults, or that the user can modify the schema (which if the schema URI isn't under their control may not be easily possible). Ignoring non-required defaults breaks any situation where a schema author (or a user of this library) expects it to be applied but isn't aware of the situation.

An example is a webservice which consumes a user message and uses a schema to clamp it to ensure legitimacy and completeness before processing. In such a case, the webapp isn't necessarily doing any further checks on the user data, because it assumes the schema has done the work, including filling in missing elements. That was my primary motivation for adding the defaults feature in the first place - a simple way of ensuring data completeness prior to processing by the ingesting service, given that I'm already validating it against a schema anyway.

[mathroc]

An example is a webservice which consumes a user message and uses a schema to clamp it to ensure legitimacy and completeness before processing. In such a case, the webapp isn't necessarily doing any further checks on the user data, because it assumes the schema has done the work, including filling in missing elements. That was my primary motivation for adding the defaults feature in the first place - a simple way of ensuring data completeness prior to processing by the ingesting service, given that I'm already validating it against a schema anyway.

that's exactly how I'm planning to use it :) we just make different assumptions, as said in json-schema-org/json-schema-spec/issues/263 it's because default is not well defined and it that it should probably be split into different keywords.

Ignoring non-required defaults breaks any situation where a schema author (or a user of this library) expects it to be applied but isn't aware of the situation.

just to be clear, that's where I have a different opinion, in the app I believe I should only rely on properties being present if they are required.

I'm now thinking that the behavior of CHECK_MODE_APPLY_DEFAULTS is correct, that crashing when there is recursion is not that bad (an exception might be better if we can detect it) but silently stopping at a defined limit seems risky.

what do you think about having multiple modes for multiple interpretations of the default keyword ? I might work on PR to add CHECK_MODE_APPLY_REQUIRED_DEFAULTS

[erayd]

Having multiple modes for applying defaults seems like a good idea. Draft-06 will obviate it, but older schemas will still be around for a long time, so it's a feature that makes a lot of sense.

I've added CHECK_MODE_REQUIRE_DEFAULTS to #365, as I already have refactored defaults code in there - @mathroc, is this the kind of thing you meant?

[erayd]

Following discussion on #263, I think that for now, not setting defaults-on-defaults is a good idea. Does anyone object to this? If not, then I will go ahead and implement this restriction.

[mathroc]

Hy @erayd , it's exactly what I meant, I just tested and it works great, thx !

[awwright]

As has been noted, the problem is that "defaults" doesn't necessarially mean "the value to assume if unspecified" but usually, merely "a suitable initial value when creating an instance" (usually for user interfaces).

Mutating defaults, I think, is somewhat outside the scope of JSON Schema, but it's still a useful feature that implementations can adopt, that applications may frequently may decide to make use of.

For these cases where you do want to mutate the instance and apply defaults, yeah, I think it makes sense that you don't recursively mutate the default, just assume defaults are already fully expanded.

If there's any suggestions for better names for these two behaviors, I'm interested in knowing. Normally the distinction is unambiguous, but here, where it's being used in the context of both user interfaces and application configuration, different people see "default" and think different things.

[erayd]

@awwright What about something like this?

• default: If the value is missing, use this in its place when validating. This is the value that should be used by any implementation that mutates input data. Satisfies required.
• hint: Used for placeholder data in e.g. user interfaces, but never touched directly by the validator, and never used for mutation.

Using default to mean "use this as the value if a value is not defined" is consistent with how XML does it, and IMO consistency here is a good thing, and will help avoid confusion.

Using hint for "here is a useful value, but the validator won't touch it" also seems like an obvious attribute name to choose. A hint suggests, but does not compel, and does not assume how or if it will be used.

[bighappyface]

See #365 - Will be official in 6.0.0