可以使用此模式來終止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