スマートフォン解析 top

TOP > タイガーチームセキュリティレポート > Berkeley Packet Filterの基礎と応用 - Part 2

タイガーチームセキュリティレポート

Berkeley Packet Filterの基礎と応用 - Part 2

今回もBPFの基礎というテーマでLinux KernelのBPF実装を見ていきます。


-LinuxとBPF-

前回のコラムでBPFが一種のvirtual machineとして設計されていることを書きましたが、
BPF virtual machineの命令で記述されたフィルタを"実行"するにはBPFの命令をCPUのnative codeに対応づける必要があります。

Linux KernelではBPFを2通りの方法で実装しています。

ひとつはinterpreterとして命令を順に解釈しながらvirtual machineの動作をエミュレートする方法です。
もうひとつはフィルタをJIT compilerでnative codeにcompileし、そのコードを直接実行する方法です。

JITはLinux Kernel 3.0から実装された機能で/proc/sys/net/core/bpf_jit_enableに1を設定することで有効化します。

単純なフィルタを使ったベンチマークではJITでフィルタを実行した場合interpreterと比較してパケットあたり50ns程度有利になるという結果があり、通信量が多い場合にJITによるpacket filterは性能上の大きなメリットになります。[4]


-System Call-

user spaceからBPFを利用するためにはAPIとしてsetsockopt()というsystem callを呼び出します。
man 2 setsockoptを見ると、setsockopt()のprototypeは以下のようになっています。

SYNOPSIS
       #include <sys/types.h>          /* See NOTES */
       #include <sys/socket.h>
       int getsockopt(int sockfd, int level, int optname,
                      void *optval, socklen_t *optlen);
       int setsockopt(int sockfd, int level, int optname,
                      const void *optval, socklen_t optlen);

optnameにSO_ATTACH_FILTER, SO_DETACH_FILTER, SO_LOCK_FILTERを指定することで
フィルタのattach, detach, lock(変更の禁止)ができます。これらはsys/socket.hに定義されています。
フィルタをattachする場合にはoptvalを使ってユーザが指定したフィルタをKernelに渡します。

以下はそれぞれのオプションを付けたsetsockopt()の呼び出し方の例です。[2]

setsockopt(sockfd, SOL_SOCKET, SO_ATTACH_FILTER, &Filter, sizeof(Filter));
setsockopt(sockfd, SOL_SOCKET, SO_DETACH_FILTER, &value, sizeof(value));
setsockopt(sockfd, SOL_SOCKET, SO_LOCK_FILTER, &value, sizeof(value));

つぎに、Debian Wheezy上でsetsockopt()を呼び出した後のKernel側の処理を追いかけていきます。
Kernelは3.2です。setsockopt()はnet/socket.cに定義されています。

1788 SYSCALL_DEFINE5(setsockopt, int, fd, int, level, int, optname,
1789                 char __user *, optval, int, optlen)
1790 {
1791         int err, fput_needed;
1792         struct socket *sock;
1793
1794         if (optlen < 0)
1795                 return -EINVAL;
1796
1797         sock = sockfd_lookup_light(fd, &err, &fput_needed);
1798         if (sock != NULL) {
1799                 err = security_socket_setsockopt(sock, level, optname);
1800                 if (err)
1801                         goto out_put;
1802
1803                 if (level == SOL_SOCKET)
1804                         err =
1805                             sock_setsockopt(sock, level, optname, optval,
1806                                             optlen);
1807                 else
1808                         err =
1809                             sock->ops->setsockopt(sock, level, optname, optval,
1810                                                   optlen);
1811 out_put:
1812                 fput_light(sock->file, fput_needed);
1813         }
1814         return err;
1815 }
net/socket.c

levelにSOL_SOCKETを指定した場合には1805行目のsock_setsockopt()が呼び出されます。
sock_setsockopt()の中を見ていくとoptnameの値でswitchしていますが、
optnameの値がSO_ATTACH_FILTERの場合の処理だけを抜き出したものが以下です。

705         case SO_ATTACH_FILTER:
706                 ret = -EINVAL;
707                 if (optlen == sizeof(struct sock_fprog)) {
708                         struct sock_fprog fprog;
709
710                         ret = -EFAULT;
711                         if (copy_from_user(&fprog, optval, sizeof(fprog)))
712                                 break;
713
714                         ret = sk_attach_filter(&fprog, sk);
715                 }
716                 break;
net/socket.c

copy_from_user()でユーザがsetsockopt()の引数で指定したoptvalをkernel spaceにコピーし、
sk_attach_filter()でフィルタをsocketにattachします。sk_attach_filter()の処理は以下です。

600 int sk_attach_filter(struct sock_fprog *fprog, struct sock *sk)
601 {
602         struct sk_filter *fp, *old_fp;
603         unsigned int fsize = sizeof(struct sock_filter) * fprog->len;
604         int err;
605
606         /* Make sure new filter is there and in the right amounts. */
607         if (fprog->filter == NULL)
608                 return -EINVAL;
609
610         fp = sock_kmalloc(sk, fsize+sizeof(*fp), GFP_KERNEL);
611         if (!fp)
612                 return -ENOMEM;
613         if (copy_from_user(fp->insns, fprog->filter, fsize)) {
614                 sock_kfree_s(sk, fp, fsize+sizeof(*fp));
615                 return -EFAULT;
616         }
617
618         atomic_set(&fp->refcnt, 1);
619         fp->len = fprog->len;
620         fp->bpf_func = sk_run_filter;
621
622         err = sk_chk_filter(fp->insns, fp->len);
623         if (err) {
624                 sk_filter_uncharge(sk, fp);
625                 return err;
626         }
627
628         bpf_jit_compile(fp);
629
630         old_fp = rcu_dereference_protected(sk->sk_filter,
631                                            sock_owned_by_user(sk));
632         rcu_assign_pointer(sk->sk_filter, fp);
633
634         if (old_fp)
635                 sk_filter_uncharge(sk, old_fp);
636         return 0;
637 }
net/core/filter.c

613行目でBPF virtual machineの命令列をuser spaceからkernel spaceにコピーしています。

この命令列は通信をフィルタする際にstruct sk_filterのbpf_funcで指定した関数によって実行されます。
bpf_funcはsk_attach_filter()の620行目と628行目で設定されています。

620行目で設定しているsk_run_filter()は、フィルタをinterpreterとして実行するための関数です。
628行目でcallしているbpf_jit_compileはbpf_jit_enableが非零にセットされているかどうかをチェックして、
セットされている場合は命令列をnative codeの関数にcompileし、bpf_funcにその関数を設定します。

以上から、bfp_jit_enableに0(デフォルト値)を設定しているか1を設定しているかで
通信をフィルタする際にinterpterとJITのどちらの実装が呼び出されるかが分かれるようになっています。

以上が、user spaceのプログラムからsetsockopt()でフィルタをattachするまでの大まかな処理の流れです。


-sk_run_filterの実装-

すでに見たように、sk_run_filter()はフィルタをinterpreterとして実行する処理にあたる関数です。
sk_run_filter()の実装を覗いてみます。以下は関数の冒頭部分です。

112 unsigned int sk_run_filter(const struct sk_buff *skb,
113                            const struct sock_filter *fentry)
114 {
115         void *ptr;
116         u32 A = 0;                      /* Accumulator */
117         u32 X = 0;                      /* Index Register */
118         u32 mem[BPF_MEMWORDS];          /* Scratch Memory Store */
119         u32 tmp;
120         int k;
121
122         /*
123          * Process array of filter instructions.
124          */
125         for (;; fentry++) {
126 #if defined(CONFIG_X86_32)
127 #define K (fentry->k)
128 #else
129                 const u32 K = fentry->k;
130 #endif
131
132                 switch (fentry->code) {
133                 case BPF_S_ALU_ADD_X:
134                         A += X;
135                         continue;
136                 case BPF_S_ALU_ADD_K:
137                         A += K;
138                         continue;
139                 case BPF_S_ALU_SUB_X:
140                         A -= X;
141                         continue;
142                 case BPF_S_ALU_SUB_K:
net/core/filter.c

コメントからも明らかなようにBPF virtual macheのレジスタがそれぞれ変数A, Xでエミュレートされます。
また、最大BPF_MEMWORDS * 4バイトの一時的なメモリ領域memと
sk_run_filter()への引数として渡される処理対象のデータへの参照skbを持っています。
125行目以降が命令列を一つづつ読み込むループで、132行目から命令の種類に応じた分岐がはじまります。

以降も処理としてはほとんどそれだけなので実装は比較的単純に見えます。

フィルタの実行速度について考えてみます。

まず、virtual machineのレジスタをローカル変数A, Xつまりスタック上のメモリ領域でエミュレートしているため、物理CPUのレジスタを使うよりデータアクセスがずっと遅くなります。また、ひとつの命令を読み込むたびにswitchで分岐する処理が入っており、実行速度の面では不利な要素になります。

ただし、switch文の場合if文と違って分岐の数が多くなっても比較の回数は増えることはないので、命令の種類の数によって実行速度が影響を受けることはなさそうです。


-bpf_jit_compileの実装-

bpf_jit_compile()はフィルタの命令列をcompileしてnative codeの関数を構築するJIT comilerです。
compileされた関数は、EAX, EBXレジスタをそれぞれvirtual machineのA, Xレジスタとして使用します。
その他、以下のようなルールにしたがってcompileされます。

15 /*
16  * Conventions :
17  *  EAX : BPF A accumulator
18  *  EBX : BPF X accumulator
19  *  RDI : pointer to skb   (first argument given to JIT function)
20  *  RBP : frame pointer (even if CONFIG_FRAME_POINTER=n)
21  *  ECX,EDX,ESI : scratch registers
22  *  r9d : skb->len - skb->data_len (headlen)
23  *  r8  : skb->data
24  * -8(RBP) : saved RBX value
25  * -16(RBP)..-80(RBP) : BPF_MEMWORDS values
26  */
arch/x86/net/bpf_jit_comp.c

コンパイルされた関数はkmalloc()で確保されたメモリ領域に格納され、detachの際に開放されます。
compileの詳細な処理を知りたい場合はarch/x86/net/bpf_jit_comp.cを読んでみると面白いかもしれません。

ここではフィルタがどのようなnative codeにcompileされるかを実例から見てみます。
bpf_jit_compile()の末尾あたりを見てみると、以下のようなdebug用コードがあるのが発見できます。

622                 oldproglen = proglen;
623         }
624         if (bpf_jit_enable > 1)
625                 pr_err("flen=%d proglen=%u pass=%d image=%p\n",
626                        flen, proglen, pass, image);
627
628         if (image) {
629                 if (bpf_jit_enable > 1)
630                         print_hex_dump(KERN_ERR, "JIT code: ", DUMP_PREFIX_ADDRESS,
631                                        16, 1, image, proglen, false);
632
633                 bpf_flush_icache(image, image + proglen);
634
635                 fp->bpf_func = (void *)image;
636         }
637 out:
638         kfree(addrs);
639         return;
640 }
arch/x86/net/bpf_jit_comp.c

どうやら、bpf_jit_enableに1よりも大きな値をセットしていた場合にはcompileした後のJIT codeを
Kernelのログに出力してくれるようになっているようですね。:-)
試してみます。rootのterminal上で以下のコマンドを実行し、kern.logに出力されるログを監視します。

root@debian:~# echo 2 > /proc/sys/net/core/bpf_jit_enable
root@debian:~# tail -f /var/log/kern.log

つぎに、X Window上でWiresharkを起動してNetwork Interfaceのひとつにフィルタを設定してみます。
ここでは前回と同じく"Edit Interface Settings"からeth0に"src port 80"というフィルタを設定しました。


"Start"を押してキャプチャを開始するとkern.logを監視中のterminalに以下のようなdebugメッセージが表示されました。

Nov 22 13:17:41 debian kernel: [72386.095316] device eth0 entered promiscuous mode
Nov 22 13:17:41 debian kernel: [72386.095964] flen=1 proglen=3 pass=3 image=ffffffffa01b7000
Nov 22 13:17:41 debian kernel: [72386.096799] JIT code: ffffffffa01b7000: 31 c0 c3
Nov 22 13:17:41 debian kernel: [72386.097938] flen=20 proglen=180 pass=3 image=ffffffffa01ce000
Nov 22 13:17:41 debian kernel: [72386.097941] JIT code: ffffffffa01ce000: 55 48 89 e5 48 83 ec 60 48 89 5d f8 31 db 44 8b
Nov 22 13:17:41 debian kernel: [72386.097942] JIT code: ffffffffa01ce010: 4f 68 44 2b 4f 6c 4c 8b 87 e0 00 00 00 be 0c 00
Nov 22 13:17:41 debian kernel: [72386.097943] JIT code: ffffffffa01ce020: 00 00 e8 62 6d e6 e0 3d dd 86 00 00 75 2c be 14
Nov 22 13:17:41 debian kernel: [72386.097945] JIT code: ffffffffa01ce030: 00 00 00 e8 69 6d e6 e0 3d 84 00 00 00 74 0a 83
Nov 22 13:17:41 debian kernel: [72386.097946] JIT code: ffffffffa01ce040: f8 06 74 05 83 f8 11 75 63 be 36 00 00 00 e8 36
Nov 22 13:17:41 debian kernel: [72386.097947] JIT code: ffffffffa01ce050: 6d e6 e0 83 f8 50 74 4d eb 52 3d 00 08 00 00 75
Nov 22 13:17:41 debian kernel: [72386.097948] JIT code: ffffffffa01ce060: 4b be 17 00 00 00 e8 36 6d e6 e0 3d 84 00 00 00
Nov 22 13:17:41 debian kernel: [72386.097950] JIT code: ffffffffa01ce070: 74 0a 83 f8 06 74 05 83 f8 11 75 30 be 14 00 00
Nov 22 13:17:41 debian kernel: [72386.097951] JIT code: ffffffffa01ce080: 00 e8 03 6d e6 e0 66 a9 ff 1f 75 20 be 0e 00 00
Nov 22 13:17:41 debian kernel: [72386.097952] JIT code: ffffffffa01ce090: 00 e8 1a 6d e6 e0 be 0e 00 00 00 e8 e5 6c e6 e0
Nov 22 13:17:41 debian kernel: [72386.097954] JIT code: ffffffffa01ce0a0: 83 f8 50 75 07 b8 ff ff 00 00 eb 02 31 c0 48 8b
Nov 22 13:17:41 debian kernel: [72386.097955] JIT code: ffffffffa01ce0b0: 5d f8 c9 c3
/var/log/kern.log

成功です。上手くいったようですねっ!:-)
ただしhexのままでは(筆者を含め)普通の人は読めないので、興味があればIDAなどで解析してみてください。


-まとめ-

今回はBPFまわりのLinux Kernelのコードを追いかけてみました。
具体的に実装を見ることでBPFのフィルタがどのように実行されているのか、イメージが湧くと思います。


参考情報:
[1] Linux 3.0 - Linux Kernel Newbies
http://kernelnewbies.org/Linux_3.0
[2] filter.txt: Linux Socket Filtering
https://www.kernel.org/doc/Documentation/networking/filter.txt
[3] A JIT for packet filters [LWN.net]
https://lwn.net/Articles/437981/
[4] Re: [PATCH v1] net: filter: Just In Time compiler [LWN.net]
https://lwn.net/Articles/437986/


次回は、BPFの応用としてseccomp sandboxの実装をみてみたいと思います


タイガーチームメンバー 塚本 泰三