[langsec-discuss] Basic results?

Paul Burchard paulburchard at gmail.com
Tue May 27 03:55:59 UTC 2014

What are known results mitigating the basic computer science problem that
it's normally expensive or impossible to answer the fundamental language
security question: what might some code do with the powers it's given?
(These are known as decision problems.)

For example, in terms of language restrictions, are there any practical
limitations on Turing completeness that make decision problems easier?  The
Chomsky hierarchy doesn't buy us much practically (even regular languages,
with little power, require exponential cost to answer decision problems),
but what about other limitations like stack or recursion depth, etc., that
effectively already exist?

Or to take on one popular approach, if we think of a sandbox as an "oracle"
that answers specific decision problems about the script, can the
"relative" decision problem (given the oracle) be any less costly?

Another theme on this forum has been use of strong typing.  How can we
characterize the decision problems that strong typing helps to answer?  Is
this a usefully larger class of decision problems than are solvable with
unrestricted code?

If anyone can point me to a review of relevant research I'd be grateful.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.langsec.org/pipermail/langsec-discuss/attachments/20140526/72fc0f0b/attachment.html>

More information about the langsec-discuss mailing list