netdev - RFC: New BGF 'LOOP' instruction

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <20100802110334.GK11110@cel.leo>
Date:	Mon, 2 Aug 2010 12:03:34 +0100
From:	Paul LeoNerd Evans <leonerd@...nerd.org.uk>
To:	netdev@...r.kernel.org
Subject: RFC: New BGF 'LOOP' instruction

---
 Proposal: Create a new BPF instruction, "LOOP", which can implement a
   specific time-bounded kind of while() loop over packet contents
---

IPv6 packets contain a linked-list of headers. Some other network
protocols may also contain linked-list structure.

BPF cannot implement loops.

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.

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. By banning further
nested LOOP instructions, we can ensure at worst a linear running time.

I believe this addition should have minimal impact on existing users of
the filter layer, as it simply adds a new instruction and does not
otherwise change the semantics of any existing code. I also believe it
to be useful in writing filters that process IPv6 packets. I also
believe that the semantics and static checks are sufficient to preserve
the termination guarantee of BPF filter programs, ensuring each packet's
fate is decided in a timely fashion to avoid locking up the kernel.

Any comments on this, while I proceed? Barring any major complaints,
I'll have a hack at some code and present a patch in due course...

-- 
Paul "LeoNerd" Evans

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

Download attachment "signature.asc" of type "application/pgp-signature" (191 bytes)