可以使用此模式来终止JSON模式验证程序吗？

我尝试了一些JSON模式验证器和一些失败，但问题是要弄清楚验证程序使用多少内存导致它窒息并被杀死。可以使用此模式来终止JSON模式验证程序吗？

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

因此，让我们创建一个JSON模式与ň定义了两个符号a和b的字母来实现非确定性有限状态机（NFA）。我们所需要做的就是编码正则表达式 (a{N}|a(a|b+){0,N-1}b)*x，其中x表示结束。在最坏的情况下，这个正则表达式的NFA需要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>添加Ñ -1定义到<DEF>枚举架构“1”， “2”， “3”，... “ñ -1”：

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

其中 “<DEF> +1” 绕回 “0” 时<DEF>等于N -1。

这个双字母字母表中的“NFA”有N的状态，只有一个初始值和一个最终状态。等效的最小DFA具有2^N（2的功率N）状态。

这意味着在最坏的情况下，使用该模式要么必须服用2^Ñ时间或使用2^Ñ存储器“单元”一个验证来验证所述输入。

我不明白这个逻辑可能出错，除非验证者采用捷径来近似有效性检查。

我找到了this here。

来源

2016-11-27 Dr. Alex RE

工作示例：https：//runkit.com/esp/583ca4c49f00610014777a8b。对于我认为的所有验证器，问题将会是堆栈大小，除非它们中的一些在内部实现递归，这是极不可能的。虽然看起来有点理论上的问题。 – esp