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.
_______________________________________________ langsec-discuss mailing list langsec-discuss@mail.langsec.org https://mail.langsec.org/cgi-bin/mailman/listinfo/langsec-discuss
