Witness Generation for JSON Schema Patterns

Abstract

JSON Schema is a schema language for the popular data exchange format JSON. This paper introduces an approach to convert regular expressions, which appear in ECMA-262 syntax in JSON Schema, into an alternative syntax such that they may be compiled to finite-state automata.This is a step towards generating witnesses, i.e., JSON instances which are valid w.r.t. the given JSON Schema specification. Specifically, we address the challenge that the ECMA-262 pattern syntax uses anchor symbols to mark the beginning and end of a word, which is not compatible with available libraries for automata manipulation. We implement an algorithm proposed by Dominik Freydenberger to convert regular expressions into brics syntax. We show that we successfully address over 97% of the patterns found in a collection of thousands of JSON Schema specifications collected from GitHub.