Thanks for sharing this, Steven. It’s excellent and quite engaging. 

Patterson suggests that regular or deterministic context-free languages are the only securable input languages. iXML therefore already fails to satisfy her requirements, since it’s non-deterministic. 

I think (and better minds may correct me) that implementers might therefore improve the security of iXML if they could provide a “reject ambiguity” mode. This would mean that parsing an input with a grammar would fail if the parse is ambiguous, instead of returning one of the possible parses. 

This wouldn’t be enough to make iXML deterministic, of course, since there’s still no guaranteed way to decide whether a given grammar is ambiguous. But it would, at least, prevent the use of ambiguous grammars if and when their ambiguity is exposed by the processor. 

Regarding pragmas, I think Patterson’s work suggests we should give users a guardrail, so that they can ensure that pragmas aren’t going to affect their use of iXML in unexpected ways. This would, I think, involve simply requiring in the spec that all iXML processors permit users to disable pragmas. Users could then permit the use of arbitrary iXML grammars as inputs, and know that they will be treated as though they contained no pragmas at all. 

If anyone’s interested in Patterson’s work, but isn’t a fan of videos, this paper covers some of the same content: https://digitalcommons.dartmouth.edu/cgi/viewcontent.cgi?article=1337&context=cs_tr

BTW


****************************************************

Dr. Bethan Tovey-Walsh

linguacelta.com

Golygydd | Editor geirfan.cymru

Croeso i chi ysgrifennu ataf yn y Gymraeg


On 15 Jan 2025, at 11:48, Steven Pemberton <steven.pemberton@cwi.nl> wrote:

I was recommended this talk, and I think it exposes some of the issues on pragmas.

The talk is 38 minutes long.

https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurity

Steven