Re: The Science of Insecurity

On Tue, Jan 10, 2012 at 01:39, Bjoern Hoehrmann <derhoermi@gmx.net> wrote:
> Even if you were lucky and the specific scheme was provided as some ABNF
> grammar that's compatible with the ABNF grammar for the generic URI syn-
> tax, there is no tool that I am aware of, that would, for instance, turn
> all regular productions in an ABNF grammar into a regular expression and
> there is no tool that I am aware of that would take two expressions, and
> tell you whether one is a subset of the other. Nothing easily discover-
> able and usable that I did not write myself anyway. Even though this is
> a very simple problem, you turn the grammars into a NFAs, the NFAs into
> DFAs, toggle the acceptance of all states in one, compute a product au-
> tomaton, minimize it, and look at the result. A 4th semester computer
> science student should be familiar with all the individual steps. But no
> mainstream tool for this exists as far as I am aware.

Sorry for being nitpicky or if I have misunderstood you. The reason
why no such generic tools exist is that such tools are impossible to
create. As far as I can remember, ABNF/BNF/EBNF are used to define
context-free grammars (CFG) and express context-free languages, which
are a superset of regular languages. Therefore, there is no way to
construct a DFA from an arbitrary CFG (however, it is possible to
create a DFA from a CFG which expresses a regular language).
Furthermore, language equality and inclusion are undecidable for
context-free languages (given two CFGs we can't know if they generate
the same language or if one includes the other). Therefore, we can
build the tools you describe, but their applicability is limited to
situations in which regular languages are used. Since regular
languages are used in many situations, I do agree that more tools are
needed (or that awareness of existing tools is poor). I might build
one myself :).

Best,
Ivan

Received on Tuesday, 10 January 2012 20:49:49 UTC