BPFプログラムの作成方法、BPFの検証器、JITコンパイル機能：Berkeley Packet Filter（BPF）入門（3）（2/3 ページ）

[味曽野雅史，OSSセキュリティ技術の会]

検証器

　カーネルはBPFのプログラムをアタッチする前に、そのBPFプログラムを実行しても安全かどうかを、検証器を用いて検証します。チェック項目としては以下のようなものがあります。

• ループがないこと
• 未初期化のレジスタを利用しないこと
• コンテキストの許可範囲のみアクセスしていること
• 境界を超えたメモリアクセスをしないこと
• メモリアクセスのアラインメントが正しいこと

　また、検証器は必要に応じて一部の命令の書き換えを行います。

　cBPFにはcBPFの検証器が、eBPFにはeBPFの検証器が存在します。また、eBPFではプログラムタイプごとに検証する内容に差異が存在します。

　以下では主にeBPFの検証器について簡単に説明します。

eBPFの検証器

　eBPFの検証器はkernel/bpf/verifier.cにあります。また、tools/testing/selftests/bpf/test_verifier.cにBPF検証器のテストコードがあります。

・第1段階

　検証器のエントリポイントは「bpf_check()」です。検証器では、初めに「check_cfg()」で深さ優先探索によりプログラムを探索し、以下をチェックします。

• ループが存在しないこと
• プログラム外へのジャンプを行わないこと
• 到達不可能な命令が存在しないこと

　なお、BPFプログラムが一定サイズ以下であることは、検証器前にBPFシステムコールの段階でチェックします。

・第2段階

　この後、検証器は「do_check()」でプログラムの開始から到達可能なパスを全てたどり、「不正な命令実行がないか」を検証します。このために検証器は各レジスタの状態を追跡しています。

　各レジスタの状態は「struct bpf_reg_state」で管理されます。「bpf_reg_state」は以下のような情報を保持します。

• レジスタの型（「enum bpf_reg_type」）
• レジスタが保持し得る最小値／最大値（smin_value、smax_value、umin_value、umax_value)
• レジスタが保持している値（「struct tnum」、valueとmaskのペア）
• オフセット（ポインタ型のみ、オフセットは固定（即値）の場合と、変数の場合が存在する）

　bpf_reg_typeとして以下が定義されています。

bpf_reg_type	意味
NOT_INIT	未初期化状態
SCALAR_VALUE	スカラ値（ポインタとして不正な値）
PTR_TO_CTX	「bpf_context」へのポインタ
CONST_PTR_TO_MAP	「struct bpf_map」へのポインタ。ポインタ演算不可
PTR_TO_MAP_VALUEBPF	map要素へのポインタ
PTR_TO_MAP_VALUE_OR_NULL	BPF map要素あるいはNULLへのポインタ。ポインタ演算不可
PTR_TO_STACK	スタックへのポインタ
PTR_TO_PACKET_META	skb->data - meta_len
PTR_TO_PACKET	skb->data
PTR_TO_PACKET_END	skb->data + headlen。ポインタ演算不可

　プログラムの初期状態では、R1の型がPTR_TO_CTX、R10の型がPTR_TO_STACKであり、それ以外のレジスタの型はNOT_INITになります。命令の実行によって、レジスタの状態は変化します。

　以下に幾つか例を挙げます。

• 「R2 = R1」ならR2の型はPTR_TO_CTX
• 「R2 = R1 + R1」ならR2の型はSCALAR_VALUE
• 「if R2 > 8 ; then {} ; else {}」の場合、true blockの中ではR2のumin_valueは9に、false blockの中ではR2のumax_valueは8
• 関数呼び出し後、R1-R5のレジスタの型はNOT_INIT

　これらの状態を元に、「do_check()」の中では一つ一つの命令に対して、その命令が実行可能か確認し、実行可能であればレジスタ状態を更新します。

　例えば、ALU命令の場合、「check_alu_op()」でレジスタのオペランドが正しいかや、予約フィールドが0であるかなどを確認しています。

　ロードやストア命令の場合は、「check_mem_access()」で正しいメモリアクセスが行われるかをチェックします。

　特に、アクセス先がPTR_TO_CTXのとき、「check_ctx_access()」において「env->ops->is_valid_access()」コールバック関数が呼ばれます。

　このコールバック関数は、コンテキストごとに設定される関数で、これによりコンテキストに応じた検証を行います。

　例えば、パケットフィルタリングで使用される「BPF_PROG_TYPE_SOCKET_FILTER」の場合、対応するコンテキストの検証器は「sk_filter_verifier_ops」になります（「verifier_ops」のプロトタイプ宣言はbpf.hにあります）。

　「sk_filter_is_valid_access()」でオフセットが正しいかどうか（読み出し禁止領域にアクセスしないか）、書き込みは許可されたフィールドに対してかどうかなどを調べています。

　関数呼び出しに関しても、プログラムタイプごとに使用できる関数は異なるため、コールバック関数を利用します。

　「check_helper_call()」で外部関数呼び出し命令のチェックをします。ここで、「env->ops->get_func_proto()」コールバック関数で関数のプロトタイプを得るための関数を取得します。

　「BPF_PROG_TYPE_SOCKET_FILTER」の場合、この関数は「sk_filter_func_proto()」です。関数のプロトタイプは戻り値や引数を定義しており（例）、検証器はこれに基づいて検証を行います。

・命令の書き換え

　「do_check()」後、検証器では一部命令を書き換えます。

　「convert_ctx_access()」では、eBPFプログラムの引数として渡されるコンテキストを書き換えます。

　例えば、ネットワークに関連するeBPFプログラムを作成する際はinclude/uapi/linux/bpf.hで定義される「struct __sk_buff」が渡されるものとしてプログラムを作成しますが、「convert_ctx_access()」ではこの「__sk_buff」のアクセスを実際のカーネル内のデータ構造で利用される「sk_buff」の対応したフィールドに対するアクセスとなるように変換します。

　このような構成になっている理由は以下の通りです。「struct sk_buff」はカーネル内データ構造であり、カーネルの更新ごとに変更される可能性があります。

　つまり、「struct sk_buff」を利用するプログラムは「sk_buff」の変更に伴って修正する必要があります。パケットフィルタリングのような、よく使用されるアプリケーションでいちいちカーネルごとに対応するのは面倒です。そこで、代わりに「__sk_buff」の使用が提案されました。

　検証器で「__sk_buff」のアクセスを変換することで、「sk_buff」のデータ構造が変更されてもBPFのプログラムを修正する必要はなくなります。また、このような構成にすることで、BPFプログラム側に見せるデータフィールドを制限することもできます。「__sk_buff」は「uapi」としてエクスポートされており、後方互換性を持って更新されることが保証されています。

　なお、コンテキスト変換もコールバック関数で定義されています。実際、「sk_buff」の変換は「bpf_convert_ctx_access()」で行われています。

　また、「fixup_bpf_calls()」では幾つか関数呼び出し命令を修正しています。

　「BPF_LD BPF_ABS」「BPF_LD BPF_IND」命令はこのタイミングで書き換えられます。この書き換えもコールバック関数経由で行われており、実際の書き換え関数は「bpf_gen_ld_abs()」です。

　「BPF_LD BPF_ABS」「BPF_LD BPF_IND」は以下のような命令に書き換えられています（抜粋）。

    switch (BPF_SIZE(orig->code)) {
    case BPF_B:
        *insn++ = BPF_EMIT_CALL(bpf_skb_load_helper_8_no_cache);
        break;
    case BPF_H:
        *insn++ = BPF_EMIT_CALL(bpf_skb_load_helper_16_no_cache);
        break;
    case BPF_W:
        *insn++ = BPF_EMIT_CALL(bpf_skb_load_helper_32_no_cache);
        break;
    }
 
    *insn++ = BPF_JMP_IMM(BPF_JSGE, BPF_REG_0, 0, 2);
    *insn++ = BPF_ALU32_REG(BPF_XOR, BPF_REG_0, BPF_REG_0);
    *insn++ = BPF_EXIT_INSN();

　BPF_CALLで呼ばれる関数では境界値チェックを行い、範囲外であれば「-EFAULT」という値を返します。

BPF_CALL_4(bpf_skb_load_helper_8, const struct sk_buff *, skb, const void *,
       data, int, headlen, int, offset)
{
    u8 tmp, *ptr;
    const int len = sizeof(tmp);
 
    if (offset >= 0) {
        if (headlen ・offset >= len)
            return *(u8 *)(data + offset);
        if (!skb_copy_bits(skb, offset, &tmp, sizeof(tmp)))
            return tmp;
    } else {
        ptr = bpf_internal_load_pointer_neg_helper(skb, offset, len);
        if (likely(ptr))
            return *(u8 *)ptr;
    }
 
    return -EFAULT;
}

　上記の書き換え後の命令では、BPF_CALLの戻り値をチェックし、もしそれが負の値であれば「BFP_EXIT_INSN()」でプログラム実行を終了しています。

・Direct Packet Access

　先ほど示したように「BPF_LD BPF_ABS」「BPF_LD BPF_IND」命令は関数呼び出しとして実行され、アクセス範囲がチェックされます。これはeBPFプログラムからパケットにアクセスする唯一の方法でしたが、XDPなど高速パケット処理が求められる場面では、実行のオーバーヘッドが大きいことが判明しました。

　そこで、BPFプログラムから直接パケットのデータにアクセスできるDirect Packet Accessが導入されました。

　以下に、Direct Packet Accessを利用するBPFプログラムを示します（コミットメッセージから抜粋）。

int bpf_prog(struct __sk_buff *skb)
{
  struct iphdr *ip;
 
  if (skb->data + sizeof(struct iphdr) + ETH_HLEN > skb->data_end)
      /* packet too small */
      return 0;
 
  ip = skb->data + ETH_HLEN;
 
  /* access IP header fields with direct loads */
  if (ip->version != 4 |ip->saddr == 0x7f000001)
      return 1;
  ...
}

　このプログラムでは、「struct iphdr *ip」を利用して、sk_buffのデータに直接アクセスしています。このプログラムの実行を検証器が許可するからくりは、bpf_reg_typeの「TR_TO_PACKET」「PTR_TO_PACKET_END」型にあります。

　まず、「skb->data」の値をレジスタにロードするとき、「is_valid_access()」関数によって、その型は「PTR_TO_PACKET」になります。

　同様に「skb->data_end」をロードすると、その型は「PTR_TO_PACKET_END」になります。「skb->data」から「skb->data_end」までが、プログラムがアクセスできる範囲です。

　この後、「skb->data + sizeof(struct iphdr) + ETH_HLEN > skb->data_end」の比較を行う際、「dst_reg->type == PTR_TO_PACKET_END && src_reg->type == PTR_TO_PACKET」が成立し、検証器では「find_good_pkt_pionters()」が呼ばれます。

　この関数で、「if (skb->data + sizeof(struct iphdr) + ETH_HLEN > skb->data_end)」の条件が成り立たない分岐では、「skb->data」から「skb->data + ETH_HLEN + sizeof(sturct iphdr)」の範囲に関してはアクセス許可するように、「bpf_reg_state」の「range」が更新されます。

　このように、Direct Packet Accessでは検証器でアクセスの安全性が保証された上で直接パケットにアクセスします。

　なお、skbuffのデータは内部的にフラグメントしている場合があります。パケットの全データに対してdirect accessができるように、フラグメントしているskbuffを1つにまとめるヘルパー関数が存在します。

　ちなみに、Direct Packet Accessが利用できるBPFプログラムタイプは下記のようになります。

• BPF_PROG_TYPE_XDP
• BPF_PROG_TYPE_SCHED*
• BPF_PROG_TYPE_SK*
• BPF_PROG_TYPE_LWT*

　BPF_PROG_TYPE_SOCKET_FILTERではDirect Packet Accessはできません。

cBPFの検証器

　cBPFの検証器はnet/core/filter.cの「check_classic()」です。cBPFはeBPFと比べシンプルなアーキテクチャであるため、検証器自体もeBPFよりもずっと単純です。

　またcBPFはeBPFへ変換されて実行されますが、eBPFへの変換の前に、この検証器が実行されます。変換後にeBPFの検証器が呼ばれることはありません。

　seccompは通常のcBPFの検証器に加え、seccomp用の検証器を用いてプログラムを検証します。これに関してはseccompを説明する際に再び触れます。