[langsec-discuss] Computational Power of Restricted Languages

D J Capelis mail at capelis.dj
Tue Nov 11 22:24:02 UTC 2014

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 <havoc at 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 at mail.langsec.org <javascript:;>
> https://mail.langsec.org/cgi-bin/mailman/listinfo/langsec-discuss
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.langsec.org/pipermail/langsec-discuss/attachments/20141111/b37b5ecf/attachment.html>

More information about the langsec-discuss mailing list