[langsec-discuss] Basic results?

Peter Bex Peter.Bex at xs4all.nl
Tue May 27 07:17:03 UTC 2014

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


More information about the langsec-discuss mailing list