On Mon, May 26, 2014 at 08:55:59PM -0700, Paul Burchard wrote: > 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?
I don't know if this is at all what you're looking for, but recently I was reminded of one effective, practical way that such things have been dealt with in the past: the Berkeley Packet Filter. It is basically a bytecode for programs which decide whether to accept a network packet and how much data of the packet should be captured. This is run within the kernel context, and arbitrary code in this bytecode can be uploaded. It reins in power by allowing only a fixed length for the program and by allowing only jumps to forward addresses, which precludes loop, making it effectively non-Turing complete. Both things taken together ensure a program terminates within an acceptable predictable maximum amount of time. However, BPF programs are very powerful because otherwise it is a pretty complete (and reasonably elegant) assembly language, which is exactly powerful enough for the problem. It has solved the problem so thoroughly that to this day we still rely on it for tcpdump or Wireshark. Uploading arbitrary bytecode for execution in the kernel sounds scary, but AFAIK there have been no security issues with it in its entire history which were a pure result of this design. I think these kinds of well-designed approaches to the security problem deserve more attention. I wouldn't want to know what ugly things people would've come up with if they'd have to solve the problem today, without access to the BPF design! If you're looking for papers, it was originally presentated at USENIX, at http://www.tcpdump.org/papers/bpf-usenix93.pdf I guess you could say there was already langsec research in 1993 ;) The manpages are pretty decent as well, and there's plenty of extra info at the tcpdump/libpcap website: http://www.tcpdump.org/#documentation Cheers, Peter -- http://www.more-magic.net _______________________________________________ langsec-discuss mailing list langsec-discuss@mail.langsec.org https://mail.langsec.org/cgi-bin/mailman/listinfo/langsec-discuss
