  JSON is a popular data format used pervasively in web APIs, cloud computing,
NoSQL databases, and increasingly also machine learning. JSON Schema is a
language for declaring the structure of valid JSON data. There are validators
that can decide whether a JSON document is valid with respect to a schema.
Unfortunately, like all instance-based testing, these validators can only show
the presence and never the absence of a bug. This paper presents a
complementary technique: JSON subschema checking, which can be used for static
type checking with JSON Schema. Deciding whether one schema is a subschema of
another is non-trivial because of the richness of the JSON Schema specification
language. Given a pair of schemas, our approach first canonicalizes and
simplifies both schemas, then decides the subschema question on the canonical
forms, dispatching simpler subschema queries to type-specific checkers. We
apply an implementation of our subschema checking algorithm to 8,548 pairs of
real-world JSON schemas from different domains, demonstrating that it can
decide the subschema question for most schema pairs and is always correct for
schema pairs that it can decide. We hope that our work will bring more static
guarantees to hard-to-debug domains, such as cloud computing and artificial
intelligence.
