Re: RFC: New BPF 'LOOP' instruction

[Paul LeoNerd Evans <leonerd@leonerd.org.uk>]

[-- Attachment #1: Type: text/plain, Size: 5159 bytes --]

On Mon, Aug 02, 2010 at 10:16:29PM +0200, Hagen Paul Pfeifer wrote:
> 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.

Oh, I am quite aware of the futility in trying to, for example, match up
IPv4 fragments.

There's nothing about my suggestion that is in any way IPv6-specific. I
used IPv6 simply as an example to motivate the suggestion. It could
quite easily apply to any other sort of protocol that uses a linked-list
of headers.

> 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. 

I'm not sure I follow your logic here.

By my understanding, pcap's IPv6 header parsing filter is a 6-times
statically-unrolled loop, where each loop body has to parse some
headers. I'm already aware that various headers are hard to parse.

Allow me some pseudocode... Currently, pcap has to do the equivalent of:

X = 0
Look at header at [X]; if it's what we want goto 'got'; else load A with
its length.
X += A
Look at header at [X]; if it's what we want goto 'got'; else load A with
its length.
X += A
Look at header at [X]; if it's what we want goto 'got'; else load A with
its length.
X += A
Look at header at [X]; if it's what we want goto 'got'; else load A with
its length.
X += A
Look at header at [X]; if it's what we want goto 'got'; else load A with
its length.
X += A
Look at header at [X]; if it's what we want goto 'got'; else load A with
its length.
X += A
got:
  ... continue with filter.

That "load A with its length" is the IPv6-specific part; I'm not
suggesting that my LOOP suggestion in any way helps that. It's a
difficult problem, sure. What I _am_ suggesting is that this static
unrolling can be avoided, instead becoming:

X = 0
start:
Look at header at [X]; if it's what we want goto 'got'; else load A with
its length.
LOOP to start
got:
  ... continue with filter.

This results also in a shorter program, because there is a hard limit on
the total number of instructions in a filter.

> 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.

As above; I was under the impression that pcap already -does- contain
code to have a reasonable attempt to hunt down the requested IPv6
header, which is what implements "ipv6 protochain". I'll quote from
pcap-filter(7):

       ip6 protochain protocol
              True  if the packet is IPv6 packet, and contains protocol header
              with type protocol in its protocol header chain.  For example,
                   ip6 protochain 6
              matches any IPv6 packet with TCP protocol header in the protocol
              header  chain.  The packet may contain, for example, authentica‐
              tion  header,  routing  header,  or  hop-by-hop  option  header,
              between  IPv6  header  and  TCP header.  The BPF code emitted by
              this primitive is complex and cannot be  optimized  by  the  BPF
              optimizer code, so this can be somewhat slow.


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

Which is -exactly- what it does. I'll quote my original:

       X += A.
       If X < len, jump backwards jt instructions.
       Otherwise, fallthrough to the next instruction
  ...
  The intention of this instruction is to be able to implement a loop in
  which successive iterations advance the index register along the packet
  buffer. By comparing X to the packet length, we can bound the running
  time of the loop instruction, avoiding it locking up the kernel. By
  banning STX instructions within the body of the loop, we can ensure that
  X must be a strictly monotonically increasing sequence. At absolute
  worst, X is increased by 1 each time, meaning at worst the body of the
  loop must execute for every byte in the packet.

Is this sufficiently secure, or do you suggest a further limit is
required?

-- 
Paul "LeoNerd" Evans

leonerd@leonerd.org.uk
ICQ# 4135350       |  Registered Linux# 179460
http://www.leonerd.org.uk/

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 190 bytes --]