Subject: [Cbor] CDDL: avoiding bad regex patterns in validation

From: Kaoru Maeda <[email-masked]>
Date: Wed, 22 Nov 2017 13:51:48 +0900

This is what I texted at IETF100.

When building a generic CDDL validator, a bad regex may result in a poor
performance.
Document may want to clarify this wrt description vs validation.

Example: suppose you want to ensure double quotes are paired.  You wrote a
regex "([^\\"]+|\\.)*".  It works to find correctly closed pairs.  However,
it takes 2^n computation time against a long string with an unclosed quote
if you use a standard PCRE engine. (This example can be easily fixed by
removing an excessive + "([^\\"]|\\.)*".)

A CDDL validator/editor that accepts user-written regex may take care of
this. If a bad regex and a PCRE engine are embedded in a product, a DoS
attack might be possible with a crafted input. (I don't know whether PCRE
with extended expressions can be compiled into DFA.)

Kaoru Maeda