BPF "loop" instruction to help IPv6 filtering

[Paul LeoNerd Evans]

Hi all,

[I tried this suggestion at Linux a while ago, but was met with
complete silence. Trying my luck here instead hoping I can nudge
support from here first]

BPF deliberately avoids being fully Turing-powerful in order to
guarantee that its filter programs definitely terminate, to ensure
timely handling of packet filtering in the kernel. This is good.
However, I find that trying to filter IPv6 packets means that the
program has to take a number of non-ideal steps that make it less
useful to IPv6.

In contrast to IPv4 packets, IPv6 packets do not have a fixed header
with an area for protocol-level options, followed eventually by the
"upper level" protocol like TCP or UDP at an offset easily calculable
in fixed space. Instead, an IPv6 packet contains a "linked list"
structure, where the overall IPv6 header gives the protocol number of
the "next" protocol on the packet. That will either be TCP/UDP/similar,
or it will be some sort of wrapper header, with its own "next" field.
It is further complicated by each header having its own format, there
not being a standard "next" place to look without understanding the
specific protocol. All very messy.

Anyhow, the current way BPF-using programs have to filter for IPv6 is
to unroll the implied "while" loop this would create a fixed number of
times (e.g. tcpdump usually does 5), and expands the entire skip
program in each unrolling, leading to quite a large amount of code.

I would like to propose a new BPF instruction, "LOOP", which can apply
a limited kind of while() loop to the BPF program, making it easier to
filter on IPv6 packets. It would operate in conjunction with the 'X'
register, in the following way:

  LOOP A, label -- add the accumulator to 'X', and jump backwards to
                   the given instruction if the new value of X is still
                   shorter than the overall packet length.

  LOOP k, label -- add the immediate constant k to X, and jump backwards
                   as before.

Statically, the program can be checked to ensure that a constant 'k' is
non-zero, and that no instruction alters the value of 'X' between the
LOOP and its target label -- if these checks fail then the program is
rejected. Dynamically while running, if the LOOP A instruction is run
with the accumulator zero, then the program should "RET 0" (similar to
a divide by zero).

I believe these semantics ensure that the program is still guaranteed
to terminate eventually, as each LOOP instruction must make a non-zero
progress to the index, X; and furthermore it cannot proceed further
than the length of the packet.

How this would be used in practice would involve creating a switch-type
block, inspecting the "next protocol" field of the current IPv6 header,
being at the X index. If the type is the required one (e.g. TCP), then
the packet can be accepted (or further tested). If not, then the
switch-type block can increment X according to the size of the header
it is currently looking at, ensuring it now points at the next header
type. This allows an efficient IPv6-parsing program, because it doesn't
have to be loop-unrolled a static number of times, either consuming too
much program space, or lacking the ability to handle deeply-nested
constructs. 

Does this sound sane?

-- 
Paul "LeoNerd" Evans

leonerd at leonerd.org.uk
ICQ# 4135350       |  Registered Linux# 179460
http://www.leonerd.org.uk/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 230 bytes
Desc: not available
URL: <http://lists.freebsd.org/pipermail/freebsd-hackers/attachments/20131022/0b709ea1/attachment.sig>