Hmm, I work away from the formal side, but I'm fairly certain by your definition almost nothing is undecidable since I can transform most language inputs into a brainfuck representation. :) (I might have to write a web browser or a C compiler in brainfuck to do it, but it's all possible.)
I think any sensible definition of decidability, especially in a langsec context, includes more than a language's representation. C++ being a notable exception as merely parsing it is a clusterfuck. On Tuesday, November 11, 2014, Taylor Hornby <ha...@defuse.ca> wrote: > Hi, > > I'm doing a LangSec binge and noticing a frequent error in LangSec > material (papers, talks). I'm not sure if it's just an "abuse of > notation" or an actual error, so hopefully someone on this list can > explain what is actually meant. I'm new to LangSec, so please forgive me > if I'm missing something obvious. > > Here's one example. Quoting the footnote on page 5 of "Security > Applications of Formal Language Theory"... > > "...HTML5+CSS3 (shown to be UNDECIDABLE by virtue of its ability to > implement Rule 110)..." > > The fact that HTML5+CSS3 can specify computation that is as powerful as > a Turing machine does not mean the language itself is undecidable or > even requires a Turing machine to decide. > > For example, the Turing-complete language "brainfuck" is as powerful as > a Turing machine, but the language specifying a brainfuck program is > context-free. > > Brainfuck -> OPS > OP -> > | < | + | - | . | , > OPS -> OPS OP | OPS Loop > Loop -> '[' OPS ']' > > Similarly, any reasonable encoding of a Turing machine is context-free. > Most generally, the set of all strings is a regular language, and > clearly you can encode Turing machines with that language! The fact that > a language is, say, regular, does not guarantee that its semantics are > not Turing-complete. > > So: What is meant by this? Is it abuse of notation for "Not only should > your syntax be regular or context-free, but your semantics should be as > well?" > > Another claim I'm skeptical of (for the same reason) is that having > a correct parser will make it less likely for input to trigger bugs that > are "behind" the parser. That's not true, because if you have a bug that > is not related to parsing, that bug can be exploited without assuming > anything about the parser, so changing the parser won't affect the > exploitability of that bug. Given that, LangSec seems to boil down to > "Don't write code when you can have it generated for you." > > Thanks, > -- > Taylor Hornby > Disclaimer: I'm wrong a lot of the time > _______________________________________________ > langsec-discuss mailing list > langsec-discuss@mail.langsec.org <javascript:;> > https://mail.langsec.org/cgi-bin/mailman/listinfo/langsec-discuss >
_______________________________________________ langsec-discuss mailing list langsec-discuss@mail.langsec.org https://mail.langsec.org/cgi-bin/mailman/listinfo/langsec-discuss
