JSON 模式验证器可以用这个模式杀死吗？

Question

我用一些 JSON 模式验证器尝试了这个，但有些失败了，但问题是要弄清楚验证器使用了多少内存导致它阻塞和被杀死。

事实证明，我们可以在 JSON 模式中实现有限状态机。为此，FSM 节点是对象模式，FSM 边是一组 JSON 指针，包裹在 anyOf 中。整个事情做起来相当简单，但能够做到这一点会产生一些后果：如果我们创建一个 FSM 需要 2^N 时间或内存（深度优先搜索或广度优先分别搜索）给定一个 JSON 模式，其中包含 N 定义和一些要验证的输入？

因此，让我们创建一个 JSON 具有 N 定义的模式，以在两个符号的字母表上实现非确定性有限状态机 (NFA) a 和 b。我们需要做的就是对正则表达式进行编码 (a{N}|a(a|b+){0,N-1}b)*x，其中x表示结束。在最坏的情况下，此正则表达式的 NFA 需要 2^N 时间来匹配文本或 2^N 内存（例如，当转换为确定性有限状态机）。现在注意单词 abbx 可以用 JSON 指针 a/b/b/x 表示，在 JSON 中等同于 {"a":{"b":{"b":{"x":true}}}}.

要将此 NFA 编码为模式，我们首先添加状态“0”的定义：

{
  "$schema": "http://json-schema.org/draft-04/schema#",
  "$ref": "#/definitions/0",
  "definitions": {
    "0": {
      "type": "object",
      "properties": {
        "a": { "$ref": "#/definitions/1" },
        "x": { "type": "boolean" }
      },
      "additionalProperties": false
    },

然后我们将每个状态<DEF>的N-1个定义添加到模式中，其中<DEF>被枚举为“1”、“2”、“ 3", ... "N-1":

    "<DEF>": {
      "type": "object",
      "properties": {
        "a": { "$ref": "#/definitions/<DEF>+1" },
        "b": {
          "anyOf": [
            { "$ref": "#/definitions/0" },
            { "$ref": "#/definitions/<DEF>" }
          ]
        }
      },
      "additionalProperties": false
    },

当 <DEF> 等于 N-1 时，“<DEF>+1”返回“0”。

这个"NFA"在一个双字母表上有N个状态，只有一个首字母和一个最终状态。等效的最小 DFA 有 2^N（2 的 N 次方）状态。

这意味着在最坏的情况下，使用此模式的验证器要么必须花费 2^N 时间，要么使用 2^N 内存 "cells" 来验证输入。

我看不出这个逻辑哪里会出错，除非验证者采取捷径来近似有效性检查。

我找到了 this here。

Answer 1

我认为原则上你是对的。我不是 100% 确定您所描述的模式构造，但理论上应该可以构造一个需要 ^N 时间或 space 的模式，正是出于您描述的原因。

实际上大多数模式处理器可能只会尝试递归验证 anyOf。所以，那将是指数时间。

JSON 模式验证器可以用这个模式杀死吗？

Can a JSON schema validator be killed with this schema?

jsonschema