JSON 스키마 검사기를이 스키마로 종료 할 수 있습니까?

일부 JSON 스키마 유효성 검사기를 사용하여이 기능을 테스트했지만 일부 기능은 실패하지만 문제는 유효성 검사기가 사용하는 메모리가 얼마나 많은지 확인하여이를 중단시키고 종료시키는 것입니다.JSON 스키마 검사기를이 스키마로 종료 할 수 있습니까?

우리는 JSON 스키마에서 유한 상태 기계를 구현할 수 있음이 밝혀졌습니다. 그렇게하기 위해 FSM 노드는 객체 스키마이고 FSM 모서리는 anyOf에 싸여있는 JSON 포인터 집합입니다. 모든 일은 비교적 간단하지만 이렇게 할 수있는 것은 몇 가지 결과를 낳습니다. 즉, JSON 스키마가 주어진 2^N 시간 또는 메모리 (각각 깊이 우선 검색 또는 폭 넓은 첫 번째 검색)가 필요한 FSM을 만들면 어떻게 될까요? N 정의와 유효성을 검사 할 입력이 있습니까?

은 그럼 두 심볼 a 및 b의 알파벳을 통해 비 결정적 유한 상태 기계 (NFA)를 구현하는 N 정의와 JSON 스키마를 만들 수 있습니다. 정규식을 (a{N}|a(a|b+){0,N-1}b)*x으로 인코딩하면됩니다. 여기서 x은 끝을 나타냅니다. 최악의 경우,이 정규 표현식의 NFA는 텍스트를 일치시키는 데 2 ^ 시간이 걸리며 (예 : 결정 성 유한 상태 시스템으로 변환 될 때) 2^N 메모리가 소요됩니다. 이제 단어 abbx은 JSON 포인터 a/b/b/x으로 표현할 수 있으며 JSON에서는 {"a":{"b":{"b":{"x":true}}}}과 같습니다.

우리가 먼저 "0"상태에 대한 정의를 추가 스키마로이 NFA를 인코딩 :

가

{ 
    "$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> 열거 된 스키마 각 상태 <DEF>위한 N -1 정의를 추가 "1", "2", "3"... "N -1"

" <DEF> +1"이 때,769을 "0"으로 다시 랩

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

은 N -1과 같습니다.

두 글자 알파벳에있는이 "NFA"는 N 주, 단 하나의 초기 및 최종 상태를가집니다. 해당 최소 DFA는 2^N (2에서 거듭 제곱 수 : N)입니다.

이것은 최악의 경우,이 스키마를 사용하거나 2^N 시간 또는 2^N 메모리 "셀"을 사용 복용해야하는 검증의 입력을 확인하는 것을 의미한다.

유효성 검사기가 유효성 검사에 근접한 바로 가기를 사용하지 않는 한이 논리가 잘못 될 수있는 부분이 없습니다.

내가 발견 this here.

출처

2016-11-27 Dr. Alex RE

실제 예 : https://runkit.com/esp/583ca4c49f00610014777a8b. 문제는 스택 크기가 될 것입니다. 일부는 내부적으로 재귀를 구현하지 않는 한 모든 유효성 검사기에 대해 가능성이 매우 낮습니다. 그래도 조금 이론적 인 문제가 있습니다. – esp

나는 원칙적으로 당신이 옳다고 생각합니다. 나는 당신이 묘사 한 스키마 구조에 대해 100 % 확신하지는 못했지만, 이론적으로 당신이 설명하는 이유 때문에 정확하게^N 시간이나 공간을 필요로하는 스키마를 구성 할 수 있어야합니다.

실제로 대부분의 스키마 프로세서는 아마도 anyOf의 재귀 적 유효성 검사를 시도 할 것입니다.그래서, 그것은 기하 급수적 인 시간입니다.

출처

2016-11-27 21:30:10 lexicore

JSON 스키마 검사기를이 스키마로 종료 할 수 있습니까?

답변

관련 문제