[langsec-discuss] Basic results?

Paul Burchard paulburchard at gmail.com
Tue May 27 14:05:58 UTC 2014

Peter, that is definitely an interesting example.  The computational model
there is the acyclic finite state machine, which is weaker than regular
languages (general finite state machine).  The lack of looping avoids the
exponential blowup that makes security analysis of regular languages

The most interesting part is that at least in this application, such a
computational model has been found to be sufficiently useful over decades
of use.  I wonder if other security-sensitive applications have used DAG
 On May 27, 2014 3:17 AM, "Peter Bex" <Peter.Bex at xs4all.nl> wrote:

> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.langsec.org/pipermail/langsec-discuss/attachments/20140527/050f9e9e/attachment.html>

More information about the langsec-discuss mailing list