Re: RFC: New BGF 'LOOP' instruction

[Hagen Paul Pfeifer <hagen@jauu.net>]

* Paul LeoNerd Evans | 2010-08-02 12:03:34 [+0100]:

Hello Paul,

>Currently therefore, it is impossible to efficiently parse IPv6 packets
>without resorting to such annoying tricks as statically unrolling a loop
>into a long list of instructions. In IPv6's case this gets very large
>very quickly, as different header types have different lengths, or
>structure layouts.
>
>I propose to add a new instruction, "LOOP", with the following
>semantics:
>
> BPF_JMP|BPF_LOOP, jt
>
>    If A == 0, fallthrough to the next instruction.
>      (TODO: Or perhaps this should be considered a hard error which
>       immediately aborts the filter, similar to divide by zero?)
>    Otherwise:
>       X += A.
>       If X < len, jump backwards jt instructions.
>       Otherwise, fallthrough to the next instruction
>
>The following static checks would be enforced:
>
> None of the 'jt' preceeding instructions before the LOOP instruction
> (i.e. the body of the loop) may themselves be LOOP instructions, nor may
> they be STX.

[..]

in principle I had no objectives against any BPF loop construct. But as said
this I question the significant advantages.

In general: BPF was constructed to address filters rules in a generic manner
and BPF does not contain any special protocol specific optimization - nor any
sophisticated connection tracking functionality. In general you should
pre-filter unneeded packets and shift the real high level filtering to some
post-processing step. tcpdump filter capabilities are limited and where never
designed to filter _any_ traffic. For example: you are lost if you want to match
transport layer fields like port number where the underlying IPv{4,6} packet
is fragmented.

Currently tcpdump/libpcap does not generate any IPv4 options or IPv6 
extension header code. The following byte code is generated by applying a 
"tcp" filter:

(000) ldh      [12]
(001) jeq      #0x86dd          jt 2    jf 4
(002) ldb      [20]
(003) jeq      #0x6             jt 7    jf 8
(004) jeq      #0x800           jt 5    jf 8
(005) ldb      [23]
(006) jeq      #0x6             jt 7    jf 8
(007) ret      #96
(008) ret      #0

Furthermore, I doubt that the loop provides any significant advantages. 
IPv6 extension header parsing is not that straight forward. For example 
check  the IPSec AH Extension header where the extension header length 
must interpreted differently because of a IPSec AH protcol defect. I assume
that a straight forward pcap encoded BPF opcode (composed of jump and load
instructions) is more efficient as an highly flexible loop construct. 

Last but not least I am interested in a RFC patch as well as a pcap patch (see
pcap-opt.c). You should not underrate the effort to generate an generic IPv6
extension header opcode optimizer - without this the newly introduced opcode
is pointless.

Hagen

PS: the LOOP opcode must be secure against any ressource attack -> the loop
must be break after n iterations.

-- 
Hagen Paul Pfeifer <hagen@jauu.net>  ||  http://jauu.net/
Telephone: +49 174 5455209           ||  Key Id: 0x98350C22
Key Fingerprint: 490F 557B 6C48 6D7E 5706 2EA2 4A22 8D45 9835 0C22