LinuxのBPF : (1) パケットフィルタ

はじめに

BPFはBerkeley Packet Filterの略で，1993年に効率的なパケットフィルタリング手法として提案されました[1] *1． BPFの構成要素は大きく2つあって，一つがネットワークからパケットをキャプチャする部分，そしてもう一つがキャプチャした パケットをフィルタリングする部分です．BPFといった場合，後者のフィルタリング機構だけを指すことも多いです． FreeBSDなどのBSD系のOSでは/dev/bpf*という特別なデバイスがあって，このBPFを利用することができます．また， Linuxでもパケットフィルタリング（Linux Sokcet Filtering; LSF）にBPFのフィルタリングをサポートしています*2．

そんなBPFですが，Linuxではここ数年で進化を遂げ，パケットフィルタリング以外の用途にも使われるようになりました． 例えば，プロセスのサンドボックス化のために発行できるシステムコールを制限するseccomp[2]はシステムコールをフィルタリングするためにBPFを利用しています．さらに，Linux 3.15からkprobe[3]とBPFを合わせて利用することが可能となり，カーネル内での様々なイベントに対してユーザが定義した処理をおこなうことができます*3．例えば， iovisorが作成しているbccはBPFを活用したダイナミックトレースツール群で， ディスクI/Oのレイテンシの測定，新しいプロセスの実行の監視，TCPコネクション情報 の取得，スタックプロファイリング機能等々，さまざまなことができます．

BPFは元々パケットフィルタリング機構だったはずなのにいったいどういうことやねん...ということでLinuxにおけるBPFについて ここではその機構と何故そのようなことが可能なのかを説明しようと思います．そのためにまずオリジナルのBPFとLinuxでBPF を利用したフィルタリングについて説明したあと，seccompでのBPFの使われ方を説明し，最後に最近のBPFを利用したトレースについて説明します．

まず始めはBPFでのパケットフィルタリングについて見ていきます．

BPFの基礎

まずはじめにオリジナルのBPF論文について説明します．

BPFの構造

BPFの構造は以下のようになっています．

(論文より引用)

BPFの基本的な使い方は以下の通りです．

1. ユーザのプロセスが/dev/bpf*を開く．図に示したようにネットワークデバイスとプロセスがBPFを挟んで接続される．
2. ユーザプロセスはプロセスごとにフィルタリングプログラム（次で説明）を設定する．
3. デバイスがパケットを受信すると，それがBPFの機構に送られ，フィルタリングされた結果がバッファにたまる．
4. ユーザはデバイスをreadすることでパケットを受信する．

カーネル内でフィルタリングされるため，無駄なコピーが発生せず効率的です． さらに，フィルタリング手法も次に説明するように効率的なものになっています．

BPFでのフィルタリング

BPF以前のパケットフィルタリング手法として，代表的なものにCMU/Stanford PacketFilter(CSPF)[4]がありました．CSPFではフィルタリングは論理演算（木構造）で表現します．一方BPFではフィルタリングをCFG（Control Flow Graph）として表現します．以下にCSPFとBPFでのフィルタの表現例を示します．

(論文より引用)

CSPFのような木構造の表現は一般にスタックマシンで評価することができます．しかし，一般にスタックはメモリ上に置かれるため評価のために必要なメモリアクセスが増えることや（速度低下の原因），非効率的なパケットのパースが何度も発生するなどといった問題がありました．また，CSPFには固定オフセット位置の要素にしかアクセスできないといった問題もありました．

BPFはこれらの問題を解決し，汎用的かつ効率的なフィルタリングをおこなうために，仮想的なレジスタマシンを提案しました．

レジスタマシン

BPFで利用するレジスタマシンの命令セットは64bit固定で，フォーマットは以下の通りです．

   opcode:16 jt:8 jf:8 k:32

jtが分岐命令において条件が真のときの分岐先，jfが偽の時の分岐先です．kは命令ごとにしようする目的が変わります．

このマシンは32bitのレジスタ2つ(AとX)と作業用のメモリおよび処理対象のパケットのデータにアクセスすることが可能です．Aがアキュムレータ，Xはインデックスレジスタとして利用します． 命令セットは 1) ストア，2) ロード，3) 算術演算，4) 分岐，5) return，6) その他 の6種類22命令からなります．

(論文より引用)

例えば，リンクレイヤーでEthernetを使っているデバイスでARPパケットのみを受理するフィルタプログラムは以下のようになります．

ldh [12]           // パケット先頭12byte目から2byteロード
jne #0x806, drop   // 読み込んだ値が0x806でなければdropへジャンプ
ret #-1
drop: ret #0

イーサネットフレームはpreambleを除くと先頭から12byteから2byteがtype/lengthフィールドで，その値が0x806のときパケットがARPであることを示します[5]．戻り値が0の場合そのパケットは棄却されます．

BPFでフィルタリングする際は，このようにユーザがBPFのプログラムを作成し設定するわけですが，BPFのプログラムはカーネル内で実行 されるため，プログラムは安全である必要があります．そこで， 安全性確保のために例えば負の方向に対するジャンプは禁止されています（無限ループを防止するため）．カーネルにはBPFプログラムを実行して安全かどうかを事前に静的に解析して検証する機能が入っています．

以下，BPFといった場合BPFのフィルタリング機構について指すことにします．

LinuxでのBPF

Linuxには/dev/bpf*は存在せず， Linuxでパケットキャプチャをする場合はソケットのプロトコルファミリにPF_PACKETを指定することでおこないますが[6]， カーネル内でパケットのフィルタリングするためにLinux Socket Filtering (LSF) という仕組みが用意されています[7]． このLSFのフィルタリングアルゴリズムは実はBPF（を拡張したもの）です．

LinuxのBPFに関してはカーネルのドキュメント Documentation/networking/filter.txt [7]にまとまっていますので， 一読を勧めます． またBPFプログラムの仕様はBSDのものを引き継いでいるので，FreeBSDのbpf(4)のmanページ[8]も参考になります．

BPFを利用したパケットフィルタリング

LinuxでLSF（BPF）を利用したパケットフィルタリングの例を見てみましょう．以下のプログラムはパケットをキャプチャしてそれが IPパケットかARPパケットかそれ以外かを出力するだけのプログラムです*4．

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/socket.h>
#include <sys/ioctl.h>
#include <arpa/inet.h>
#include <linux/if_ether.h>
#include <linux/filter.h>
#include <netpacket/packet.h>
#include <net/if.h>

int main(){
    int soc;
    struct ifreq ifr;
    struct sockaddr_ll sll;
    unsigned char buf[4096];

    memset(&ifr, 0, sizeof(ifr));
    memset(&sll, 0, sizeof(sll));

    soc = socket(AF_PACKET, SOCK_RAW, htons(ETH_P_ALL));

    strncpy(ifr.ifr_name, "br0", IFNAMSIZ);
    ioctl(soc, SIOCGIFINDEX, &ifr);

    sll.sll_family = AF_PACKET;
    sll.sll_protocol = htons(ETH_P_ALL);
    sll.sll_ifindex = ifr.ifr_ifindex;
    bind(soc, (struct sockaddr *)&sll, sizeof(sll));

    while(1){
        ssize_t len = recv(soc, buf, sizeof(buf), 0);
        struct ethhdr* ethhdr = (struct ethhdr*)buf;
        int proto = ntohs(ethhdr->h_proto);
        if(len <= 0) break;
        printf("%3ld %0x %s\n", len, proto,
                proto==ETH_P_ARP ? "arp" : proto==ETH_P_IP ? "ip" : "other");
    }
    return 0;
}

ここで，BPFプログラムを使ってARPパケットのみを受理するようにしてみましょう．そのためには，setsockopt(2)システムコール[8]を 以下のように利用して，ソケットのfdに対してBPFプログラムをアタッチします．

setsockopt(sockfd, SOL_SOCKET, SO_ATTACH_FILTER, &bpf, sizeof(bpf));

ここで，bpfは<linux/filter.h> の中で定義されているsock_fprog構造体です．

struct sock_fprog { /* Required for SO_ATTACH_FILTER. */
    unsigned short      len;    /* Number of filter blocks */
    struct sock_filter *filter;
};

struct sock_filter {    /* Filter block */
    __u16   code;   /* Actual filter code */
    __u8    jt; /* Jump true */
    __u8    jf; /* Jump false */
    __u32   k;      /* Generic multiuse field */
};

このように，BPFプログラムの実体はsock_filter構造体の配列です． BPF命令のコードは<linux/bpf_common.h>でdefineされています． また，BPF命令列はマクロを使って定義することができます（もちろんハンドアセンブルしたい人はすればいいですが..）．

struct sock_filter code[] = {
    BPF_STMT(BPF_LD | BPF_H | BPF_ABS, 12),  // ldh [12]
    BPF_JUMP(BPF_JMP | BPF_JEQ | BPF_K, 0x806, 0, 1), // jeq #0x806 jt 0 jf 1
    BPF_STMT(BPF_RET | BPF_K, -1), // ret #-1
    BPF_STMT(BPF_RET | BPF_K, 0) // ret #0
};

struct sock_fprog bpf = {
    .len = sizeof(code)/sizeof(code[0]),
    .filter = code,
};

マクロについては前述のドキュメント[7]，[8]に詳しくは書いてあります．

以上をまとめると，フィルタリングプログラム全体は以下のようになります．

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/socket.h>
#include <sys/ioctl.h>
#include <arpa/inet.h>
#include <linux/if_ether.h>
#include <linux/filter.h>
#include <linux/kernel.h>
#include <netpacket/packet.h>
#include <net/if.h>

struct sock_filter code[] = {
    BPF_STMT(BPF_LD | BPF_H | BPF_ABS, 12),  // ldh [12]
    BPF_JUMP(BPF_JMP | BPF_JEQ | BPF_K, 0x806, 0, 1), // jeq #0x06 jt 2 jf 3
    BPF_STMT(BPF_RET | BPF_K, -1), // ret #-1
    BPF_STMT(BPF_RET | BPF_K, 0) // ret #0
};

struct sock_fprog bpf = {
    .len = sizeof(code)/sizeof(code[0]),
    .filter = code,
};

int main(){
    int soc;
    struct ifreq ifr;
    struct sockaddr_ll sll;
    unsigned char buf[4096];

    memset(&ifr, 0, sizeof(ifr));
    memset(&sll, 0, sizeof(sll));

    soc = socket(AF_PACKET, SOCK_RAW, htons(ETH_P_ALL));

    strncpy(ifr.ifr_name, "br0", IFNAMSIZ);
    ioctl(soc, SIOCGIFINDEX, &ifr);

    sll.sll_family = AF_PACKET;
    sll.sll_protocol = htons(ETH_P_ALL);
    sll.sll_ifindex = ifr.ifr_ifindex;
    bind(soc, (struct sockaddr *)&sll, sizeof(sll));

    setsockopt(soc, SOL_SOCKET, SO_ATTACH_FILTER, &bpf, sizeof(bpf));

    while(1){
        ssize_t len = recv(soc, buf, sizeof(buf), 0);
        struct ethhdr* ethhdr = (struct ethhdr*)buf;
        int proto = ntohs(ethhdr->h_proto);
        if(len <= 0) break;
        printf("%3ld %0x %s\n", len, proto,
                proto==ETH_P_ARP ? "arp" : proto==ETH_P_IP ? "ip" : "other");
    }
    return 0;
}

このプログラムを実行すると，ARPのパケットを受信したことしか出力されないはずです． ここで重要なことは，フィルタリングがカーネル空間で行われていること，またユーザが定義したプログラムがカーネル内で動作していることです．

libpcapとBPF

先ほどはフィルタプログラムはマクロを使って定義しましたが，パケットキャプチャライブラリとして有名なlibpcapはパケットのフィルタリングに BPFを利用しており，実はtcpdumpを使うとフィルタ式をBPFのプログラムにコンパイルすることができます（というかそもそもtcpdumpがBPFを最初に使ったプログラムだったぽい） *5．

% sudo tcpdump  -d arp
(000) ldh      [12]
(001) jeq      #0x806           jt 2    jf 3
(002) ret      #262144
(003) ret      #0

% sudo tcpdump  -dd arp
{ 0x28, 0, 0, 0x0000000c },
{ 0x15, 0, 1, 0x00000806 },
{ 0x6, 0, 0, 0x00040000 },
{ 0x6, 0, 0, 0x00000000 },

% sudo tcpdump  -ddd arp
4
40 0 0 12
21 0 1 2054
6 0 0 262144
6 0 0 0

BPFでフィルタリングしたいのなら普通はこのコンパイル結果を埋め込めばいいでしょう．最適化もしてくれます． また，libpcapのpcap_compileという関数でプログラム内でコンパイルすることもできます．

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/socket.h>
#include <sys/ioctl.h>
#include <arpa/inet.h>
#include <linux/if_ether.h>
#include <linux/filter.h>
#include <netpacket/packet.h>
#include <net/if.h>

#include <pcap/pcap.h>
#include <pcap/bpf.h>

int main(){
    int soc;
    struct ifreq ifr;
    struct sockaddr_ll sll;
    unsigned char buf[4096];

    memset(&ifr, 0, sizeof(ifr));
    memset(&sll, 0, sizeof(sll));

    soc = socket(AF_PACKET, SOCK_RAW, htons(ETH_P_ALL));

    strncpy(ifr.ifr_name, "br0", IFNAMSIZ);
    ioctl(soc, SIOCGIFINDEX, &ifr);

    sll.sll_family = AF_PACKET;
    sll.sll_protocol = htons(ETH_P_ALL);
    sll.sll_ifindex = ifr.ifr_ifindex;
    bind(soc, (struct sockaddr *)&sll, sizeof(sll));

    struct bpf_program bpf;
    pcap_t *handle;
    handle = pcap_open_live("br0", 4096, 1, 1000, buf);
    pcap_compile(handle,&bpf,"arp",1,PCAP_NETMASK_UNKNOWN);
    setsockopt(soc, SOL_SOCKET, SO_ATTACH_FILTER, (struct sock_fprog*)&bpf, sizeof(bpf));

    while(1){
        ssize_t len = recv(soc, buf, sizeof(buf), 0);
        struct ethhdr* ethhdr = (struct ethhdr*)buf;
        int proto = ntohs(ethhdr->h_proto);
        if(len <= 0) break;
        printf("%3ld %0x %s\n", len, proto,
                proto==ETH_P_ARP ? "arp" : proto==ETH_P_IP ? "ip" : "other");
    }
    return 0;
}

...まぁそもそもlibpcap使うのならキャプチャ用に便利な関数がいろいろあるのでそれを使った方がいいと思いますが． libpcapにはBPFプログラムのインタプリタも付属していて，ユーザ空間でパケットのフィルタリングをしたい場合に使えます．

また，Linuxのソースのtools/net以下にもbpfのアセンブラなどのツールがあります．これらの使い方は ドキュメント[7]に書いてあります．

ここまでのまとめ

1. BPFというパケットフィルタリング機構がある．
2. BPFはパケットキャプチャ部分とフィルタリング部分に分けられ，フィルタリングは仮想的なレジスタマシンを使用する．
3. LinuxのLinux Socket FilterはBPFでフィルタリングをおこなう．
4. Linuxではsetsockopt(2)でソケットに対してフィルタリングをするBPFプログラムを設定できる．
5. tcpdump(libpcap)を使ってBPFプログラムはコンパイルできる．

次回はseccompがBPFをどのように利用しているかについて書こうと思います．

---

参考文献

• [1]Steven McCanne and Van Jacobson. 1993. The BSD packet filter: a new architecture for user-level packet capture. In Proceedings of the USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993 Conference Proceedings (USENIX'93). USENIX Association, Berkeley, CA, USA, 2-2
• [2]seccomp(2) - Linux manual page
• [3]Kprobe-based Event Tracing
• [4]MOGUL, J.C., RASHID, R.F., AND ACCETTA, M.J. The packet filter: An efficient mechanism for user-level network code. In Proceedings of 11th Symposium on Operating Systems Principles (Austin, TX, Nov. 1987), ACM, pp. 39–51
• [5]Ethernet - The Wireshark Wiki
• [6]packet(7) - Linux manual page
• [7]Linux Socket Filtering aka Berkeley Packet Filter (BPF)
• [8]bpf(4)
• [9]getsockopt(2) - Linux manual page

その他参考URL

• Berkeley Packet Filterの基礎と応用 - Part 1
• Net bsd advent calendar 2015 BPF Programming basic

*1:論文が出たのが93年で実際にはその2年ぐらい前から存在していたようです

*2:ここでBPFはBPFのフィルタリング機構のことを指しています

*3:Linux 4.7からperfのeventもサポートされました

*4:良い子はエラーハンドリングしましょう

*5:BPFプログラムのコードについて，統一的な仕様は私は知りませんが，LinuxもBSDも同じものを利用しているようです