eBPF Deep Dive: Architecture and Safety Mechanisms

Cloud Native Days Winter 2024で発表した eBPF の技術解説の発表です。
https://event.cloudnativedays.jp/cndw2024/talks/2398

Transcript

1. eBPF Deep Dive: Architecture and Safety Mechanisms 2024/11/28 Takeru Hayasaka <t-hayasaka@bbsakura.net> CloudNativeDaysWinter 2024
2. 本発表の趣旨 - eBPFの基礎の説明を通じて仕組みとユースケースを押さえる - 根幹となる仕組みを理解することで、eBPFを採用するクラウドネイティブ 関連プロジェクトの本質を理解できる素養を取得する 2
3. Agenda • eBPFの概要と歴史 • eBPFのライフサイクル • eBPFのアーキテクチャ • まとめ 3
4. 自己紹介 • 早坂 彪流 (Hayasaka Takeru|@takemioIO) • さくらインターネット に所属 現在は BBSakura Networksへ出向中 ◦ 社会人4年目 ◦ 前職はゲーム会社でゲーム機のファームを書いていた ◦ モバイルコアの研究開発・運用に従事 ▪ パケット処理にeBPF を使った開発を業務でやってます ▪ 本業はパケット処理屋さん ◦ 今年から（自腹で）社会人大学院生をやってる。ピカピカの一年生。 100分授業つらい...😇 • 好きなeBPF Helper Function は bpf_fib_lookup ◦ 雑にやっても使える感じが良い • 一言: めっちゃ緊張しております...! 4
5. PR: eBPF Japan Meetup 第二回やります - 正式名:Cloud Native Community Japan - eBPF Japan Meetup #2 - eBPF ユーザー会みたいなものを CNCFでやってたりしてます - 次回第二回が12/6(金)1900~から さくらインターネット東京支社で 開催予定です - eBPFに興味が出てきました！ みたいな人がいたらぜひご参加ください cf. https://ebpf.connpass.com/ 5
6. eBPFの概要と歴史 6
7. eBPF(extended Berkeley Packet Filter)とは？ - Linuxカーネルに対する拡張を楽に書いて、動的にロードさせる仕組み - つまりカーネル空間で動作する拡張プログラムを用意できる仕組み - 言語仕様としてはRISC型仮想マシンとして表現される - 主に以下の用途で利用される - セキュリティ: seccomp, LSM… - オブザーバビリティ: kprobe, uprobe, retprobe, tracepoint, fentry… - ネットワーク: XDP, TC, TCP-BPF, cgroup_skb… - その他: CPUスケジューラー … cf. https://ebpf.io/what-is-ebpf/ 誤解を恐れずにいうと, eBPFを使えば • 手軽にkernelの拡張ができる • Kernel内部で実行された関数の結果を ほぼ何でも取れる • 100GbEを超える速度のパケット処理 が手軽にできるようになる と言ったことが出来る嬉しさがある 7
8. - Linuxにはカーネルモジュールと呼ばれる機能がある - これを使えばカーネル空間で動く独自の拡張を書くことができる - eBPFで実装できる機能は基本的はカーネルモジュールで作れる機能と同じ - しかし以下の点が異なる - 1. 安全性: Verifier による検証でプログラマのミスを未然に防ぐ - メモリアクセス違反でカーネルがハングすることを防いだり、 メモリリークや無限ループに対する事前検証をVerifierが行ってくれる - 2. 後方互換性: カーネルモジュールが後方互換性を保証しないのに対し、 eBPFはAPI Interface経由で動作するため（原則）後方互換性が保証される - 更に仮想マシンなのでCPUアーキテクチャに依存しない、ポータビリティもある - なので頑張ってLinuxのアップストリームに入れる必要もない - カーネルメンテナと議論する必要もなくなり、開発アジリティも改善する KernelModule（従来の仕組み）と何が違う？ 8
9. つまりKernelModule（従来の仕組み）と比べると - 別にeBPFで技術的にできることが増えた訳では無い󰢄 - eBPFを使って実装すると、カーネル開発へのアクセスが良くなる󰢐 - システム上でセキュリティ的にも担保され、後方互換も担保されてる - 開発者もユーザーも（ある程度）保証されたプロダクトが手に入る - アップストリームに入れなくていいので早く機能が手に入る󰢐 9
10. eBPFを利用することは開発の効率化にも繋がる - “A full sweep through the fleet can easily take months.” - 「フリート全体の徹底的な調査には、簡単に数か月かかることがあります。」 - Subject: Re: [PATCHSET RFC] sched: Implement BPF extensible scheduler class - metaのエンジニアがコア機能をLinuxに入れるために、LKMLに投稿した文章 - （※フリート: 本番環境） - 大規模なサービスにおいては、テスト環境では再現できない負荷や トラフィックの影響を把握し、リスクを最小限に抑えるために本番環境での検 証が不可欠。つまり本番でのイテレーションが必要になる - eBPFなら、安全性が担保され、再起動不要で動く実装になるため、本番環境で テストがしやすい→つまり、eBPFなら価値を素早く届けることにつながる 10
11. eBPFの採用事例が成熟しつつある - Cloud Native 方面だと、IsovalentのCiliumを中心に成熟している - CiliumはKubernetes に次いで 2 番目にアクティブな CNCF Graduatedプロジェクト - 11/24現在の12ヶ月以内のコミット数で33129, これは3位 Argoの11180と比べて 3倍程度のコミット数:) - cf.https://www.cncf.io/announcements/2023/10/11/cloud-native-computing-foundation-announces-cilium-graduation/ - Isovalent が Cilium以外にもTetragon やHubbleなども実装している - 子供向けにeBPFを説明する謎の本まである力の入れ具合はすごい https://isovalent.com/books/children-guide-to-ebpf/ Isovalentのサイト見ると all explained so that your kids or colleagues can follow along too と書いているので、多分 これを読むとebpf 完全理解したができると思われます....(?)→ 11
12. プロダクトユースケース - セキュリティ - Isovalent, Cisco / Tetragon(Podセキュリティイベント監視、ContainerRuntimeポリシー...) - Sysdig / Falco(Teragonと同様にセキュリティ監視) - オブザーバビリティ - Isovalent, Cisco / Hubble(Metrics, Service map, flow log…) - Aqua Security / Tracee (Metrics, Forensics…) - ネットワーク - Isovalent, Cisco / Cilium(KubernetesのCNIやセキュリティ) - Meta / Katran(L4Loadbrancer) - Cloudflare / Gatebot(DDoS Mitigation), Unimog(L4Loadbrancer) - LINEヤフー / L4LB, SRv6 - MIXI / StaticNAT, PayloadCutterなど - さくらインターネット&BBSakura Networks /パケット交換機(PGW-U) - 弊社でも使ってます:) 12
13. 歴史：最初期 - 1992: 「The BSD Packet Filter: A New Architecture for User-level Packet Capture」のパケットキャプチャを効率化するアイディアが始まり - classic BPF (cBPF)と呼ばれ、LinuxにおいてLinuxSocketFilter(LSF)という 名前になって入れられている。libpcap(tcpdump)での利用が知られている。 $ sudo tcpdump -d "ip proto \tcp" (000) ldh [12] ; read EtherType (001) jeq #0x800 jt 2 jf 5 ; if (is_ipv4){goto 2}else{goto 5} (002) ldb [23] ; read IPv4Proto (003) jeq #0x6 jt 4 jf 5 ; if(is_tcp){goto 4}else{goto 5} (004) ret #262144 ; パケットキャプチャするようにして exit (005) ret #0 ; 何もせず exit tcpdumpで利用される、cBPFアセンブリの例 IPv4で尚且つTCPのパケットをフィルタできるバイトコードを示している 13
14. - 2013: 「[PATCH net-next] extended BPF」をAlexei StarovoitovがLKML に投稿してBPFの拡張を提案する - この段階でパケット処理やSeccompなど汎用的な仕組みを目指していたことがMLから読める - Alexei自身は、IOVisorの元となってるPLUMgridの開発者で、 後にXDPの初期パッチを投稿していたりしてる - cf. PLUMgridによるLinuxへの開発の様子（主にeBPFとNetwork関連に力を入れてる） - cf. 最初期のXDPのパッチ(Jul 2016) - 2024現在、約32年の時を経て、BPFは拡張されまくった結果 パケットフィルタに留まらない、いろいろ便利な機能として育った 歴史：約20年後、eBPFが生まれる 14
15. eBPFのライフサイクル 15
16. eBPFのライフサイクル cf. https://ebpf.io/what-is-ebpf/ 16
17. eBPFのライフサイクル cf. https://ebpf.io/what-is-ebpf/ つまりELFファイル 17
18. - eBPFのプログラムは右のような スタイルのC言語で書くことになる - clangのバックエンドにeBPFバイト コードを吐き出す仕組みがあり、 このプログラムを食わせることで eBPFバイトコード(ELFファイル) を取得できる - 最近だとgccでコンパイルしたり、 Rustでもかけたりするらしい... eBPFプログラミング #include <linux/bpf.h> #include <bpf/bpf_helpers.h> #include <linux/if_ether.h> #include <arpa/inet.h> SEC("xdp_drop") int xdp_drop_prog(struct xdp_md *ctx) { void *data_end = (void *)(long)ctx->data_end; void *data = (void *)(long)ctx->data; struct ethhdr *eth = data; __u16 h_proto; if (data + sizeof(struct ethhdr) > data_end) return XDP_DROP; h_proto = eth->h_proto; if (h_proto == htons(ETH_P_IPV6)) return XDP_DROP; return XDP_PASS; } char _license[] SEC("license") = "GPL"; cf. Get started with XDP/Task 2: Drop specific packets with XDP 18
19. eBPFプログラミング - 右図はIPv6パケットをDropするコード例 - 1. SECマクロをつけることで エントリポイントを指定する - Cのmainに相当するものを自分で指定する - どこにhookを設定するかによって、 SECマクロと関数の引数の中身が変更される - XDPのProgramTypeを指定するとxdp_mdになる - 2. 安全性を保つためにデータを読むたびに 境界値チェックをしている #include <linux/bpf.h> #include <bpf/bpf_helpers.h> #include <linux/if_ether.h> #include <arpa/inet.h> SEC("xdp_drop") int xdp_drop_prog(struct xdp_md *ctx) { void *data_end = (void *)(long)ctx->data_end; void *data = (void *)(long)ctx->data; struct ethhdr *eth = data; __u16 h_proto; if (data + sizeof(struct ethhdr) > data_end) return XDP_DROP; h_proto = eth->h_proto; if (h_proto == htons(ETH_P_IPV6)) return XDP_DROP; return XDP_PASS; } char _license[] SEC("license") = "GPL"; cf. Get started with XDP/Task 2: Drop specific packets with XDP 1 2 19
20. 余談: ProgramTypeはKernelとeBPFのInterface - 以下は実際のXDPのプログラム定義とそれを構成するmacro - prog_ctx_type, kern_ctx_type は それぞれeBPFから, kernelから見た 引数である。つまりKernelからeBPFを呼び出す時のプログラム引数の型の 対応をここで定義している - このように分離してるのは、カーネルバージョン依存を回避するためである // progtypeのmacro #define BPF_PROG_TYPE(_id, _name, prog_ctx_type, kern_ctx_type) \(略) // xdp progtypeの定義 BPF_PROG_TYPE(BPF_PROG_TYPE_XDP, xdp, struct xdp_md, struct xdp_buff) cf.https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/include/linux/bpf_types.h#L11 cf.https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/include/linux/bpf.h#L2263 20
21. eBPFのライフサイクル cf. https://ebpf.io/what-is-ebpf/ 21
22. eBPF Loader - Loaderはカーネルとユーザー空間のインターフェースの役割を持つ - ELFバイナリをパースして、実行に必要な情報を取り出して、 bpf(2) syscall経由でLoad, Mapとの読み書きをする - BTFやeBPF Mapをロードした後にリロケーションで後続のプログラムやeBPF Mapに対して FD(File Descriptor)を埋め込む。 - これはロードした実体のポインターを実行時にプログラムたちに渡すことで、 カーネル内部で必要なデータとの読み書きを実現するので必要となる 22
23. eBPF Loaderで知られてるモノ - libbpf(C): 本家大元、これが一番実装されてる。 - cilium/ebpf(Go)：pure-goで頑張っててえらい。libbpfと比べると機能不足 だが、ciliumやcloudflareで使われてるので大変枯れてる - Aya(Rust): pure-rustで頑張っててえらい - BCC(C,Python,Go,lua): 初めて勉強する時はこれがわかりやすいかも - Sys::Ebpf(perl): 拙作のライブラリ、Perlから実行できる。 Pure-Perlで頑張ってる！ cf. https://speakerdeck.com/takehaya/getting-started-with-ebpf-in-perl-how-to-create-your-own-loader Loaderの作り方とか知りたい人 はこちらの資料をどうぞ💁 23
24. eBPFのライフサイクル cf. https://ebpf.io/what-is-ebpf/ 24
25. - bpf syscallでロードされたプログラムはVerifierにより二段階でチェック - 一段階目は全ての分岐をトレースした大雑把なもの - CFGを探索することで無限ループの回避 - 最大命令長(100万命令）を超えてしまわないかのチェック - 不正なジャンプがないかの確認 - 内部的にはcheck_cfgで深さ優先探索して実現してる - 二段階目は制約の上でレジスタの演算ができるなどの細かい確認 - 例えばスカラー値をポインタとしてメモリに対して読み書きできたら、 任意のアドレス空間の読み書きができてしまい大変危ない。 - バッファオーバーフローしないかのチェックもここでやっている - 型や定数の追跡をすることでこれらを実現している - 具体的にはbpf_reg_typeやbpf_reg_stateに定義してある eBPF Verifier 25
26. eBPFのライフサイクル cf. https://ebpf.io/what-is-ebpf/ 26
27. - Verifierを通過したBPFプログラムは安全と仮定し、パフォーマンスのために ネイティブマシンコードに変換される - ここでeBPFバイトコードからArchごとのネイティブコードに変換されるため、 eBPFはアーキテクチャ非依存で展開することができる - そもそもネイティブで動いてくれないと、実行速度に難があるので・・・ - 実際にはdo_jitというカーネル内部の関数でJITコンパイルされる - バイトコードからの変換なので結構愚直で素朴な実装で書かれてる JIT Compiler case BPF_ALU | BPF_ADD | BPF_X: case (色々なcase条件を中略...): case BPF_ALU64 | BPF_XOR | BPF_X: maybe_emit_mod(&prog, dst_reg, src_reg, BPF_CLASS(insn->code) == BPF_ALU64); b2 = simple_alu_opcodes[BPF_OP(insn->code)]; EMIT2(b2, add_2reg(0xC0, dst_reg, src_reg)); break; cf. https://elixir.bootlin.com/linux/v6.11/source/arch/x86/net/bpf_jit_comp.c#L1379 dst_reg ^= src_reg 相当のコード 27
28. eBPFのライフサイクル cf. https://ebpf.io/what-is-ebpf/ 28
29. eBPF Attach & Hook - カーネルにロードしたら、実行したい場所にアタッチする必要がある - 何かのイベントをトリガーにeBPFのプログラムが実行される - Hookの例 - Socket: socketに対してのIOをhookしてフィルタ - kprobe, kretprobe: カーネルの関数呼び出し・返り値をトレース - TC, XDP: NICに対してのIOをhookして読み書き - アタッチ可能なタイプがbpf_attach_typeに定義されている - Linux v6.11現在で58のattach pointがある 29
30. eBPFのライフサイクル cf. https://ebpf.io/what-is-ebpf/ 30
31. eBPF Map - eBPFプログラムとユーザー空間から読み書きできるKVストア - 様々なMap Typeが存在している - Hash, Array - Trie(IPアドレスのプレフィックスマッチなどに使う) - Per-CPU (Hash|Array): RWでロックしないように割り込みCPU毎でデータを持ちたい時に使う - LRU, CPUMAP, QUEUE etc… - 例えば、IPアドレスのブラックリストをeBPF Mapで持っていれば、 それを参照することでカーネルレベルでパケットを落とせる。 このDenylistはユーザー空間から更新可能である 31
32. eBPFのライフサイクルのまとめ - Cなどのコードを書いてeBPFプログラムを実装し、カーネルにロードできる - eBPFプログラムはVerifierにかけられ、最後はネイティブコードにJITされる - eBPF Mapを使ってユーザー空間とデータのやり取りができる cf. https://ebpf.io/what-is-ebpf/ 32
33. eBPFのアーキテクチャ 33
34. eBPFはRISC型の仮想マシンとして表現される - 固定長のStack(512byte) - 固定長で64bit命令 - 汎用レジスタ10本+フレームポインタ1本 - 算術もLD/ST、JMPとか大体ある - Call命令(HelperFuncを呼べる） - 非推奨になってるパケット操作用レジスタもある...(レガシー😇) R0 汎用レジスタ（戻り値を格納） R1～R5 汎用レジスタ（引数レジスタ） R6～R9 汎用レジスタ R10 フレームポインタ（読み出し専 用） msb 32 48 52 56 lsb +------------------------+----------------+----+----+--------+ |immediate |offset |src |dst |opcode | +------------------------+----------------+----+----+--------+ BPFの命令をアスキーアートで書いた図（基本命令エンコーディング） cf. https://github.com/iovisor/bpf-docs/blob/master/eBPF.md#instruction-encoding 34
35. e.g. 適当なレジスタ演算をするeBPF バイトコード例 - 実際にバイトコード上で計算するとこんな雰囲気になる - 最終的に1+5 をするだけのBPFバイトコードの例 - Sys::Ebpf(拙作のPerl eBPF Loader)での動作例 my @program = ( Sys::Ebpf::Asm::BPF_ALU64_IMM( Sys::Ebpf::Asm::BPF_MOV, 6, 1 ), # r6 = 1 Sys::Ebpf::Asm::BPF_ALU64_REG( Sys::Ebpf::Asm::BPF_MOV, 1, 6 ), # r1 = r6 Sys::Ebpf::Asm::BPF_ALU64_IMM( Sys::Ebpf::Asm::BPF_ADD, 1, 5 ), # r1 += 5 Sys::Ebpf::Asm::BPF_ALU64_REG( Sys::Ebpf::Asm::BPF_MOV, 0, 1 ), # r0 = r1 Sys::Ebpf::Asm::BPF_JMP_IMM( Sys::Ebpf::Asm::BPF_EXIT, 0, 0, 0 ), # exit ); cf. https://github.com/takehaya/Sys-Ebpf/blob/9b8565188f0d391128af13941e8b009e0f7e6581/t/04_ebpf_load_prog.t#L17 35
36. ワイド命令エンコーディングもサポートしてる - 64bitの命令だと64bitの変数を一発で渡すことができない... - そうだ2命令を1命令として見做せばええやん！(128bitで表現) - imm64 = (next_imm << 32) | imm として、32bitずつに分けるイメージ ワイド命令エンコーディングを書いた図 cf. https://kernel.org/doc/html/v6.12/bpf/standardization/instruction-set.html +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | opcode | regs | offset | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | imm | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | next_imm | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 36
37. e.g. ワイド命令エンコーディングの例 - 前述したLoaderが実施することがあり、eBPF MapのFDをリロケーションするのに使う - eBPF Mapのロード結果をバイナリに埋め込んで、初めてプログラムはMapを利用できる - 仮にFDが305419896(0x12345678)で、Sys::Ebpf上でバイトコードの表現するとこうなる my $High = Sys::Ebpf::Asm->new( code => 0x18, # opcode(lddw) dst_reg => 0x1, # destination register (r1) src_reg => 0x1, # source register(Pseudo map fd) off => 0, # offset imm => 0x1234 # immediate value (map fd)upper ); my $Low = Sys::Ebpf::Asm->new( code => 0,dst_reg => 0,src_reg => 0, off => 0,imm => 0x5678);# lower eBPF Mapのリロケーションをする図 37
38. CPUアーキごとのレジスタ割当を工夫してる - eBPFはLoad時にJITコンパイルを行い、結果ネイティブに近い性能を実現 - （もちろんJITコンパイルをしないケースもあり、インタープリタもある） - そのときにはx86_64やARM64などのABIとのコンパチビリティを意識し、 eBPFレジスタ (R0-R9) を、ハードウェアレジスタに1対1対応させることで ネイティブに近い性能を実現してる - e.g. R0 → rax (x86_64の場合) - cf. https://docs.kernel.org/bpf/classic_vs_extended.html 38
39. static const int reg2hex[] = { [BPF_REG_0] = 0, /* RAX */ [BPF_REG_1] = 7, /* RDI */ [BPF_REG_2] = 6, /* RSI */ [BPF_REG_3] = 2, /* RDX */ [BPF_REG_4] = 1, /* RCX */ [BPF_REG_5] = 0, /* R8 */ [BPF_REG_6] = 3, /* RBX callee saved */ [BPF_REG_7] = 5, /* R13 callee saved */ [BPF_REG_8] = 6, /* R14 callee saved */ [BPF_REG_9] = 7, /* R15 callee saved */ [BPF_REG_FP] = 5, /* RBP readonly */ [BPF_REG_AX] = 2, /* R10 temp register */ [AUX_REG] = 3, /* R11 temp register */ [X86_REG_R9] = 1, /* R9 register, 6th function argument */ [X86_REG_R12] = 4, /* R12 callee saved */ }; x86のレジスタのマッピング例 呼び出し規約との対応が読み取れる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://elixir.bootlin.com/linux/v6.12/source/arch/x86/net/bpf_jit_comp.c#L178 39
40. eBPF ProgramはKernel内でどのように実行されるのか - フローをざっくりと列挙する - 1.Loaderが bpf(2)をコールして、プログラム（やMapの）ロードを実施する - 2.eBPF VerifierがeBPFプログラムを検査する - 3.JITコンパイラがeBPFプログラムをネイティブコードに変換する - 4.HookpointでロードしたeBPFプログラムをAttachして実行する 40
41. eBPF ProgramはKernel内でどのように実行されるのか - フローをざっくりと列挙する - 1.Loaderが bpf(2)をコールして、プログラム（やMapの）ロードを実施する - 2.eBPF VerifierがeBPFプログラムを検査する - 3.JITコンパイラがeBPFプログラムをネイティブコードに変換する - 4.HookpointでロードしたeBPFプログラムをAttachして実行する 今回は時間の関係で省略 41
42. eBPF ProgramはKernel内でどのように実行されるのか - 1.Loaderが bpf(2)をコールして、プログラム（やMapの）ロードを実施する - 2.eBPF VerifierがeBPFプログラムを検査する 42
43. bpf(2) syscallでprogram/mapを生成・ロードする - bpf(2) syscallを実行することでELFから取り出したプログラムとeBPF Map を生成およびロードできる - これを行うeBPFLoaderが内部で実行する順番は（BTFを除くと） ELFパース->Map Create->リロケーション->ProgramLoad - eBPF Map生成はbpf(2)サブコマンドでBPF_MAP_CREATEを実行 - 既存のeBPF Mapをロードするときはbpf(2)サブコマンドBPF_OBJ_GETを実行 - eBPF Programのロードはbpf(2)サブコマンドでBPF_PROG_LOADを実行 - これらの引数は union bpf_attr で表現される - 詳しくはLinux KernelのeBPF Syscallを参照 int bpf(int command, union bpf_attr *attr, u32 size) cf. https://man7.org/linux/man-pages/man2/bpf.2.html より、改変及び抜粋 43
44. Loaderのお仕事を図にしてみるとこんな感じ #include <linux/bpf.h> #include <bpf/bpf_helpers.h> #include <linux/if_ether.h> #include <arpa/inet.h> SEC("xdp_drop") int xdp_drop_prog(struct xdp_md *ctx) { void *data_end = (void *)(long)ctx->data_end; void *data = (void *)(long)ctx->data; struct ethhdr *eth = data; __u16 h_proto; if (data + sizeof(struct ethhdr) > data_end) return XDP_DROP; h_proto = eth->h_proto; if (h_proto == htons(ETH_P_IPV6)) return XDP_DROP; return XDP_PASS; } char _license[] SEC("license") = "GPL"; Cプログラム ELF Object LLVM compile User Kernel bpf(2) Create Map Get map FD ELF リロケーション ELF Section (prog & rel) Map bpf(2) Load Prog 44 Program
45. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 union bpf_attr { struct { /* Used by BPF_PROG_LOAD */ __u32 prog_type; __u32 insn_cnt; __aligned_u64 insns; /* 'const struct bpf_insn *' */ __aligned_u64 license; /* 'const char *' */ __u32 log_level; __u32 log_size; /* size of user buffer */ __aligned_u64 log_buf; /* user supplied 'char *' buffer */ __u32 kern_version; }; } __attribute__((aligned(8))); cf. https://man7.org/linux/man-pages/man2/bpf.2.htmlより、改変及び抜粋 eBPFプログラムをロード時に bpf(2)に渡せるアトリビュート 定義（一部簡略) 45
46. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 union bpf_attr { struct { /* Used by BPF_PROG_LOAD */ __u32 prog_type; __u32 insn_cnt; __aligned_u64 insns; /* 'const struct bpf_insn *' */ __aligned_u64 license; /* 'const char *' */ __u32 log_level; __u32 log_size; /* size of user buffer */ __aligned_u64 log_buf; /* user supplied 'char *' buffer */ __u32 kern_version; }; } __attribute__((aligned(8))); cf. https://man7.org/linux/man-pages/man2/bpf.2.htmlより、改変及び抜粋 ロードするプログラムタイプ e.g. BPF_PROG_TYPE_XDP… プログラムの命令数と プログラム命令の配列ポインタ Verifierとかで失敗した時のログを保存 できるバッファ変数 46
47. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 int fd; union bpf_attr attr = { .prog_type = BPF_PROG_TYPE_XDP, .insn_cnt = 10, .insns = 0x1000,// 仮の命令配列アドレス .license = (unsigned long)"GPL", .log_level = BPF_LOG_LEVEL_DEBUG, .log_size = 1024, .log_buf = (unsigned long)malloc(1024), }; int fd = bpf(BPF_PROG_LOAD, &attr, sizeof(attr)); eBPFプログラムをロード時に bpf(2)に渡す例 XDPのプログラムをこのように するとロードできる 47
48. eBPF ProgramはKernel内でどのように実行されるのか - 1.Loaderが bpf(2)をコールして、プログラム（やMapの）ロードを実施する - 2.eBPF VerifierがeBPFプログラムを検査する 48
49. - bpf syscallでロードされたプログラムはVerifierにより二段階でチェック - 一段階目は全ての分岐をトレースした大雑把なもの - CFGを探索することで無限ループの回避 - 最大命令長(100万命令）を超えてしまわないかのチェック - 不正なジャンプがないかの確認 - 内部的にはcheck_cfgで深さ優先探索して実現してる - 二段階目は制約の上でレジスタの演算ができるなどの細かい確認 - 例えばスカラー値をポインタとしてメモリに対して読み書きできたら、 任意のアドレス空間の読み書きができてしまい大変危ない。 - バッファオーバーフローしないかのチェックもここでやっている - 型や定数の追跡をすることでこれらを実現している - 具体的にはbpf_reg_typeやbpf_reg_stateに定義してある eBPF Verifier 再掲 49
50. eBPF Verifier: 一段階目チェック - 一段階目は全ての分岐をトレースした大雑把なもの - 基本的な処理構造 - CFG(Control Flow Graph)として各命令をノード（点）として表現し、制御フローをエッジ （辺）として表現する - 条件分岐(JUMP, CALL等)での分岐やフォールスルー（順番に命令が遷移）をエッジと評価 - 深さ優先探索で、DAG(Directed Acyclic Graph) であることを検証する - ※DAGを検証する: ループを持たない有向グラフであることを検証する - 検証ポイント - ループを検出 - 到達不能命令を検出 - 範囲外へのジャンプを検出 - プログラムが必ず終了ことを検出(EXIT or JUMP で終わる） 50
51. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 // 到達不能な命令 mov r0, 2 ; r0 に 2 を代入 exit ; プログラム終了 mov r0, 42 ; 到達不能な命令 exit ; 到達不能な命令 // 領域外へのジャンプ(命令のアドレス番地が 1-3までしかない） jmp +5 ; goto 5 (アドレス番地5に飛ぼうとして不正なジャンプ ) mov r0, 1 ; r0 に 1 を代入 exit ; プログラム終了 // ループの存在 mov r0, 2 ; r0 = 2(アドレス番地1を持つ) jeq r0, 2, 1 ; if 2==2 goto 1(アドレス番地1に常に飛ぶ) exit ; 到達不能な命令 一段階目で弾かれるプログラムの例 51
52. パスの探索最適化 - 実装では高速化のために探索パスの枝刈りをしている - プログラムのなかで特定の命令(e.g. 比較に関する命令)に到達した時の 検証状態を保存しておく（メモ化） - 再度同じポイントに到達した時、以前保存された状態と比較して同等と判断 された場合は、これ以上探索を行わずSkipしている - これによって次の探索では、今後使われない変数などを無視すること が可能になって、効率を上げることができる 52
53. eBPF Verifier: 二段階目チェック - 二段階目は制約の上でレジスタの演算ができるなどの細かい確認 - 基本的な処理構造 - レジスタに対するシンボリック実行を行う - 誤解を恐れずに噛み砕くと命令の状態ごとに意味を割り当て、 動作のシミュレーションをするイメージ - 計算可能な型の整合性と実現可能な値の整合性を見てる - 検証ポイント - 算術演算: スカラ or ポインタ型を見て、値の範囲やオフセットを見る - ロード/ストア: アクセス可能なメモリポインタなのかを確認 - ジャンプ（条件付き/無条件）: 分岐した上でトレースし、比較可能なのかとか - 関数呼び出し: 呼び出し可能な関数かどうか - ProgramType由来のレジスタタイプ: パケットのバッファー等 53
54. レジスタに対する型の追跡 - レジスタが有効なメモリ領域を指していることを保証してることを理解する ために以下のようなポインタ型レジスタに対してポインタを足してみる - Verifierが型の観点で気にするのは以下のようなこと - スタックの初期化状態が行われてるか？ - 計算可能な型で実施されているか？ r0 = r10 - 8; // r0 は PTR_TO_STACK 型 r1 = r10 - 16; // r1 も PTR_TO_STACK 型 r2 = r0 + r1; // ポインタ同士の加算は不正 🙅 ポインタとポインタの足し算で失敗する図 54
55. - レジスタが有効なメモリ領域を指すように保証するのを理解するために 以下のような演算を考える - Verifierが値の観点で気にするのは以下のようなこと - Stackの有効範囲、eBPFはStackに512byte制限がある - 変数型のサイズ(e.g. uint32)に沿ってるか？ レジスタに対する値の追跡 // r0 はスタックポインタ（ `PTR_TO_STACK` 型）だが有効範囲外 ... 🙅 r0 = r10 - 520; *(r0) = 42; // スタックに値を書き込むところまでいけない 🙅 –-- r0 = 0xFFFFFFFE; // 最大値に近い値を代入 r0 += 2; // r0 の値は 0x1_0000_0000 になり、範囲外 🙅 stack上の変数に代入できなくて失敗してる図 55
56. - bpf syscallでロードされたプログラムはVerifierにより二段階でチェック - 一段階目は全ての分岐をトレースした大雑把なもの - CFGを探索することで無限ループの回避 - 最大命令長(100万命令）を超えてしまわないかのチェック - 不正なジャンプがないかの確認 - 内部的にはcheck_cfgで深さ優先探索して実現してる - 二段階目は制約の上でレジスタの演算ができるなどの細かい確認 - 例えばスカラー値をポインタとしてメモリに対して読み書きできたら、 任意のアドレス空間の読み書きができてしまい大変危ない。 - バッファオーバーフローしないかのチェックもここでやっている - 型や定数の追跡をすることでこれらを実現している - 具体的にはbpf_reg_typeやbpf_reg_stateに定義してある eBPF Verifier 再掲 56
57. - bpf syscallでロードされたプログラムはVerifierにより二段階でチェック - 一段階目は全ての分岐をトレースした大雑把なもの - DAGをみることで無限ループの回避 - 最大命令長(100万命令）を超えてしまわないかのチェック - 不正なジャンプがないかの確認 - 内部的にはcheck_cfgで深さ優先探索して実現してる - 二段階目は制約の上でレジスタの演算ができるなどの細かい確認 - 例えばスカラー値をポインタとしてメモリに対して読み書きできたら、 任意のアドレス空間の読み書きができてしまい大変危ない。 - バッファオーバーフローしないかのチェックもここでやっている - 型や定数の追跡をすることでこれらを実現している - 具体的にはbpf_reg_typeやbpf_reg_stateに定義してある eBPF Verifier 再掲 一,二段階だけではなくて、 実は三段階目が存在する 57
58. - 実は三段階目が存在しており、eBPFプログラムの最適化がされてる - DeadCode除去 - JUMP命令の分岐が実施されない、探索しなくて良いとされる実質的に到達不可能なコードを プログラムから削除することができる - 移植性の観点から実行時に定数を書き換えて切り替えてロードしたいことがある。その場 合、ロード時に不要なコードが判明するため、DeadCode除去をカーネルに任せるしかない - なので、コンパイル時にあらかじめ最適化することが難しい - これによりランタイムのCPUサイクルを節約し高速化に貢献している - 命令のインライン化と書き換え - eBPFヘルパーに対する間接的な関数呼び出しはAPIとしての一面もあり、これを呼ぶことで 安全にカーネルへのアクセスを担保できている側面がある。一方で関数呼び出しのオーバー ヘッド影響が大きいケースがある(e.g. bpf_jiffies64のような時間に関する値)そこで、間接 呼び出し命令を透過的にinline化して直接呼び出しに変更することで高速化に貢献している eBPF Verifier Optimize 58
59. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u32 uattr_size) { u64 start_time = ktime_get_ns(); struct bpf_verifier_env *env; (中略) //　bpf_verifier_env という検証環境を表す構造体を初期化します env = kvzalloc(sizeof(struct bpf_verifier_env), GFP_KERNEL); if (!env) return -ENOMEM; //　各命令に関する補助情報を格納するための領域を確保します env->bt.env = env; len = (*prog)->len; env->insn_aux_data = vzalloc(array_size(sizeof(struct bpf_insn_aux_data), len)); (中略) cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16494 eBPFのプログラムを検証する エントリポイント関数の部分 59
60. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u32 uattr_size) {(以下中略および重要なコードを抜粋 ) //　検証ターゲットのプログラム設定と、 ProgramTypeの種類ごとに行うべき検証ルールの設定する env->prog = *prog; env->ops = bpf_verifier_ops[env->prog->type]; env->fd_array = make_bpfptr(attr->fd_array, uattr.is_kernel); //　生ポインタを出すのはセキュリティリスクがあるので、オプションやケイパビリティや特定の判断で有効 化されたり、Spectre対策での分岐予測緩和を有効にするかなどの検証オプションがここで渡される env->allow_ptr_leaks = bpf_allow_ptr_leaks(env->prog->aux->token); env->allow_uninit_stack = bpf_allow_uninit_stack(env->prog->aux->token); env->bypass_spec_v1 = bpf_bypass_spec_v1(env->prog->aux->token); env->bypass_spec_v4 = bpf_bypass_spec_v4(env->prog->aux->token); env->bpf_capable = is_priv = bpf_token_capable(env->prog->aux->token, CAP_BPF); (中略) cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16494 プログラム検証するための 基本的な情報の設定をします 60
61. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u32 uattr_size) { (以下中略および重要なコードを抜粋 ) // ジャンプ命令が同じサブプログラム内で完結するか (つまり境界はtailcallで渡すのが前提) ret = check_subprogs(env); // MapFD の実際のポインタへの置き換え解決 ret = resolve_pseudo_ldimm64(env); // step1: CFGを検証する(DFSでループ分岐を見てる) ret = check_cfg(env); // 関数呼び出しの最適化実施（直接レジスタにアクセスすることで低いオーバーヘッドにする） ret = mark_fastcall_patterns(env); // step2: プログラム・サブプログラム全体の整合性の検証 ret = do_check_main(env); ret = ret ?: do_check_subprogs(env); (中略) cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16494 実際にプログラム検証を行います 61
62. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u32 uattr_size) { (以下中略および重要なコードを抜粋 ) // ジャンプ命令が同じサブプログラム内で完結するか (つまり境界はtailcallで渡すのが前提) ret = check_subprogs(env); // MapFD の実際のポインタへの置き換え解決 ret = resolve_pseudo_ldimm64(env); // step1: CFGを検証する(DFSでループ分岐を見てる) ret = check_cfg(env); // 関数呼び出しの最適化実施（直接レジスタにアクセスすることで低いオーバーヘッドにする） ret = mark_fastcall_patterns(env); // step2: プログラム・サブプログラム全体の整合性の検証 ret = do_check_main(env); ret = ret ?: do_check_subprogs(env); (中略) cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16494 実際にプログラム検証を行います step1, step2とコメントした関数 を起点に解説します 62
63. CFGの検証（一段階目検証） - check_cfg で深さ優先探索を行ってる - visit_insnで現在見ている命令（ノード）に対しての処理する - 分岐先をStackにPushしたり、枝刈りを行う - 非分岐命令, 関数呼び出し,無条件ジャンプ,条件付きジャンプの4つをケアしている - push_insnで現在の命令から、次の命令に遷移する制御エッジ（辺）を処理 - ついでに定義外ジャンプの検出やループ検出をする - ここでも枝刈りの情報を保持したりしてる 63
64. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる static int check_cfg(struct bpf_verifier_env *env) {(以下中略および重要なコードを抜粋 ) while (env->cfg.cur_stack > 0) { int t = insn_stack[env->cfg.cur_stack - 1]; ret = visit_insn(t, env); switch (ret) { case DONE_EXPLORING: insn_state[t] = EXPLORED; env->cfg.cur_stack--; break; case KEEP_EXPLORING: break; default:(中略) goto err_free; } } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16494 一段階目のCFGの検証は この関数で実施している 64
65. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる static int check_cfg(struct bpf_verifier_env *env) {(以下重要なコードを抜粋) while (env->cfg.cur_stack > 0) { int t = insn_stack[env->cfg.cur_stack - 1]; ret = visit_insn(t, env); switch (ret) { case DONE_EXPLORING: insn_state[t] = EXPLORED; env->cfg.cur_stack--; break; case KEEP_EXPLORING: break; default:(中略) goto err_free; } } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16516 深さ優先探索をStackを使って 行なってる Stackが空になるまで命令列を探索 命令を訪問してDONE or KEEP or errを返す （探索終了 or 次の命令探索) 探索完了フラグをつけている 65
66. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる static int visit_insn(int t, struct bpf_verifier_env *env) {(以下中略および重要なコードを抜粋 ) // Exitの時は探索を終了する switch (BPF_OP(insn->code)) { (中略) default: /* conditional jump with two edges */ mark_prune_point(env, t); if (is_may_goto_insn(insn)) mark_force_checkpoint(env, t); ret = push_insn(t, t + 1, FALLTHROUGH, env); if (ret) return ret; return push_insn(t, t + insn->off + 1, BRANCH, env); (以下中略) } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16516 CFGでどのように命令の条件を 判断してるのかがわかる関数 非分岐命令, 関数呼び出し,無条件ジャンプ, 条件付きジャンプの4つをケアしてる 66
67. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる static int visit_insn(int t, struct bpf_verifier_env *env) {(以下中略および重要なコードを抜粋 ) // Exitの時は探索を終了する switch (BPF_OP(insn->code)) { (中略) default: /* conditional jump with two edges */ mark_prune_point(env, t); if (is_may_goto_insn(insn)) mark_force_checkpoint(env, t); ret = push_insn(t, t + 1, FALLTHROUGH, env); if (ret) return ret; return push_insn(t, t + insn->off + 1, BRANCH, env); } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16516 条件付きジャンプ命令のケアの例 67
68. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる static int visit_insn(int t, struct bpf_verifier_env *env) {(以下中略および重要なコードを抜粋 ) // Exitの時は探索を終了する switch (BPF_OP(insn->code)) { (中略) default: /* conditional jump with two edges */ mark_prune_point(env, t); if (is_may_goto_insn(insn)) mark_force_checkpoint(env, t); ret = push_insn(t, t + 1, FALLTHROUGH, env); if (ret) return ret; return push_insn(t, t + insn->off + 1, BRANCH, env); } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16516 枝刈りのために状態の保存を実施 68
69. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる static int visit_insn(int t, struct bpf_verifier_env *env) {(以下中略および重要なコードを抜粋 ) // Exitの時は探索を終了する switch (BPF_OP(insn->code)) { (中略) default: /* conditional jump with two edges */ mark_prune_point(env, t); if (is_may_goto_insn(insn)) mark_force_checkpoint(env, t); ret = push_insn(t, t + 1, FALLTHROUGH, env); if (ret) return ret; return push_insn(t, t + insn->off + 1, BRANCH, env); } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16516 条件が成立しない場合の経路をstackにpush 次の命令に進むように指定(FALLTHROUGH) 69
70. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる static int visit_insn(int t, struct bpf_verifier_env *env) {(以下中略および重要なコードを抜粋 ) // Exitの時は探索を終了する switch (BPF_OP(insn->code)) { (中略) default: /* conditional jump with two edges */ mark_prune_point(env, t); if (is_may_goto_insn(insn)) mark_force_checkpoint(env, t); ret = push_insn(t, t + 1, FALLTHROUGH, env); if (ret) return ret; return push_insn(t, t + insn->off + 1, BRANCH, env); } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16516 条件が成立する場合の経路をstackにpush ジャンプ先命令に進むように指定(BRANCH) 70
71. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる static int push_insn(int t, int w, int e, struct bpf_verifier_env *env) {(以下中略および重要なコードを抜粋 ) if (w < 0 || w >= env->prog->len) { verbose_linfo(env, t, "%d: ", t); verbose(env, "jump out of range from insn %d to %d\n", t, w); return -EINVAL; } if (e == BRANCH) { /* mark branch target for state pruning */ mark_prune_point(env, w); mark_jmp_point(env, w); } (以下中略) } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16051 CFGでエッジ（辺）に関してケアしつつ、 どのようにpushするかを判断してる 71
72. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる static int push_insn(int t, int w, int e, struct bpf_verifier_env *env) {(以下中略および重要なコードを抜粋 ) if (w < 0 || w >= env->prog->len) { verbose_linfo(env, t, "%d: ", t); verbose(env, "jump out of range from insn %d to %d\n", t, w); return -EINVAL; } if (e == BRANCH) { /* mark branch target for state pruning */ mark_prune_point(env, w); mark_jmp_point(env, w); } (以下中略) } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16051 命令のindexを見て定義外ジャンプ していないかをチェック 条件付き分岐が発生する場合は、 ジャンプ先でも枝刈りのためのポイントを 作る（visit_insnでは現在の命令につけてた） 72
73. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる static int push_insn(int t, int w, int e, struct bpf_verifier_env *env) {(以下中略および重要なコードを抜粋 ) } else if ((insn_state[w] & 0xF0) == DISCOVERED) { if (env->bpf_capable) return DONE_EXPLORING; verbose_linfo(env, t, "%d: ", t); verbose_linfo(env, w, "%d: ", w); verbose(env, "back-edge from insn %d to %d\n", t, w); return -EINVAL; } (以下中略) } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16051 DISCOVEREDのマーカーであれば、 再度訪れたことになる命令とわかるので ループであることを検出できる(back-edge) 73
74. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる static int push_insn(int t, int w, int e, struct bpf_verifier_env *env) {(以下中略および重要なコードを抜粋 ) } else if ((insn_state[w] & 0xF0) == DISCOVERED) { if (env->bpf_capable) return DONE_EXPLORING; verbose_linfo(env, t, "%d: ", t); verbose_linfo(env, w, "%d: ", w); verbose(env, "back-edge from insn %d to %d\n", t, w); return -EINVAL; } (以下中略) } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16051 面白い点として、CAP_BPFがついてる時は privilege(特権)としてループ自体は許可されて いたりします （今回は説明しませんが、特権がついてる場合 はその場合有界な範囲でループしているかを 二段階目チェックでケアされてたりします） 74
75. CFGの検証の具体的な手順まとめ 1. 深さ優先探索でノードとエッジを探索するためにCFGを初期化する 2. Stackの要素をpopして、ノードの各エッジをスキャンする 3. ループの場合や定義外ジャンプとかはCFGを拒否 a. BackEdgeの存在チェックでDAGかどうかがわかる 4. すべてのノードを探索したら、CFGが有効かどうかを判定 - 判定結果 - 有効なCFG（Valid CFG） - 到達不能命令が存在するCFG（Unreachable Instructions） - ループを含むCFGは拒否 75
76. 値と型の追跡（二段階目検証） - do_check_common で値と型の追跡に必要な初期化を実施 - レジスタに対しての割り当て型bpf_reg_typeをうまく当てはめたりする - 引数用の割り当て型bpf_arg_type、戻り値用の割り当てbpf_return_typeもある - do_check で具体的なチェック - 有効な命令かの確認 - 命令数上限の確認 - 命令種別ごとの処理チェック - 命令種別のチェックの中で、値の追跡を行う - 命令種別としてはALU/ALU64, LDX, STX, JMP, EXITのケアがされてる 76
77. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u32 uattr_size) { (以下中略および重要なコードを抜粋 ) // ジャンプ命令が同じサブプログラム内で完結するか (つまり境界はtailcallで渡すのが前提) ret = check_subprogs(env); // MapFD の実際のポインタへの置き換え解決 ret = resolve_pseudo_ldimm64(env); // step1: CFGを検証する(DFSでループ分岐を見てる) ret = check_cfg(env); // 関数呼び出しの最適化実施（直接レジスタにアクセスすることで低いオーバーヘッドにする） ret = mark_fastcall_patterns(env); // step2: プログラム・サブプログラム全体の整合性の検証 ret = do_check_main(env); ret = ret ?: do_check_subprogs(env); (中略) cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16494 実際にプログラム検証を行います 再掲 step1, step2とコメントした関数 を起点に解説します 77
78. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int do_check_common(struct bpf_verifier_env *env, int subprog) {(以下中略および重要なコードを抜粋 ) 　　if (subprog || env->prog->type == BPF_PROG_TYPE_EXT) { 　　... 　　for (i = BPF_REG_1; i <= sub->arg_cnt; i++) { 　　 arg = &sub->args[i - BPF_REG_1]; 　　 reg = &regs[i]; 　　 ... 　　 } 　　} /* 1st arg to a function */ regs[BPF_REG_1].type = PTR_TO_CTX; mark_reg_known_zero(env, regs, BPF_REG_1); ret = do_check(env); （中略） cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L21504 割り当てチェックの事前 準備を行う関数 78
79. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int do_check_common(struct bpf_verifier_env *env, int subprog) { 　　if (subprog || env->prog->type == BPF_PROG_TYPE_EXT) { 　　... 　　for (i = BPF_REG_1; i <= sub->arg_cnt; i++) { 　　 arg = &sub->args[i - BPF_REG_1]; 　　 reg = &regs[i]; 　　 ... 　　 } 　　} /* 1st arg to a function */ regs[BPF_REG_1].type = PTR_TO_CTX; mark_reg_known_zero(env, regs, BPF_REG_1); ret = do_check(env); （中略） サブプログラムやレジスタ の初期化割り当てを行う メインプログラムの引数の 初期化を行う （第一引数は通常はbpf ctxを受け取る） 型と値のチェックを行う cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L21504 79
80. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 enum bpf_reg_type { NOT_INIT = 0, /* nothing was written into register */ SCALAR_VALUE, /* reg doesn't contain a valid pointer */ PTR_TO_CTX, /* reg points to bpf_context */ CONST_PTR_TO_MAP, /* reg points to struct bpf_map */ PTR_TO_MAP_VALUE, /* reg points to map element value */ PTR_TO_MAP_KEY, /* reg points to a map element key */ PTR_TO_STACK, /* reg == frame_pointer + offset */ PTR_TO_PACKET_META, /* skb->data - meta_len */ PTR_TO_PACKET, /* reg points to skb->data */ PTR_TO_PACKET_END, /* skb->data + headlen */ （中略） cf. https://elixir.bootlin.com/linux/v6.12/source/include/linux/bpf.h#L882 実際に定義されている レジスタの型の抜粋 （一部中略） 80
81. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 enum bpf_reg_type { NOT_INIT = 0, /* nothing was written into register */ SCALAR_VALUE, /* reg doesn't contain a valid pointer */ PTR_TO_CTX, /* reg points to bpf_context */ CONST_PTR_TO_MAP, /* reg points to struct bpf_map */ PTR_TO_MAP_VALUE, /* reg points to map element value */ PTR_TO_MAP_KEY, /* reg points to a map element key */ PTR_TO_STACK, /* reg == frame_pointer + offset */ PTR_TO_PACKET_META, /* skb->data - meta_len */ PTR_TO_PACKET, /* reg points to skb->data */ PTR_TO_PACKET_END, /* skb->data + headlen */ （中略） cf. https://elixir.bootlin.com/linux/v6.12/source/include/linux/bpf.h#L882 スカラー値（つまり普通の変数の値) eBPFプログラムの呼び出し引数ポインタ （つまりbpf_contextオブジェクトを指してる 未初期化の値 81
82. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 enum bpf_reg_type { NOT_INIT = 0, /* nothing was written into register */ SCALAR_VALUE, /* reg doesn't contain a valid pointer */ PTR_TO_CTX, /* reg points to bpf_context */ CONST_PTR_TO_MAP, /* reg points to struct bpf_map */ PTR_TO_MAP_VALUE, /* reg points to map element value */ PTR_TO_MAP_KEY, /* reg points to a map element key */ PTR_TO_STACK, /* reg == frame_pointer + offset */ PTR_TO_PACKET_META, /* skb->data - meta_len */ PTR_TO_PACKET, /* reg points to skb->data */ PTR_TO_PACKET_END, /* skb->data + headlen */ （中略） cf. https://elixir.bootlin.com/linux/v6.12/source/include/linux/bpf.h#L882 eBPFMap自体へのポインタ eBPFMapのValueへのポインタ eBPFMapのKeyへのポインタ 82
83. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 enum bpf_reg_type { NOT_INIT = 0, /* nothing was written into register */ SCALAR_VALUE, /* reg doesn't contain a valid pointer */ PTR_TO_CTX, /* reg points to bpf_context */ CONST_PTR_TO_MAP, /* reg points to struct bpf_map */ PTR_TO_MAP_VALUE, /* reg points to map element value */ PTR_TO_MAP_KEY, /* reg points to a map element key */ PTR_TO_STACK, /* reg == frame_pointer + offset */ PTR_TO_PACKET_META, /* skb->data - meta_len */ PTR_TO_PACKET, /* reg points to skb->data */ PTR_TO_PACKET_END, /* skb->data + headlen */ （中略） cf. https://elixir.bootlin.com/linux/v6.12/source/include/linux/bpf.h#L882 eBPFプログラムで実行されているスタック 領域へのポインタ型 83
84. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 enum bpf_reg_type { NOT_INIT = 0, /* nothing was written into register */ SCALAR_VALUE, /* reg doesn't contain a valid pointer */ PTR_TO_CTX, /* reg points to bpf_context */ CONST_PTR_TO_MAP, /* reg points to struct bpf_map */ PTR_TO_MAP_VALUE, /* reg points to map element value */ PTR_TO_MAP_KEY, /* reg points to a map element key */ PTR_TO_STACK, /* reg == frame_pointer + offset */ PTR_TO_PACKET_META, /* skb->data - meta_len */ PTR_TO_PACKET, /* reg points to skb->data */ PTR_TO_PACKET_END, /* skb->data + headlen */ （中略） cf. https://elixir.bootlin.com/linux/v6.12/source/include/linux/bpf.h#L882 パケット処理をするときのメタデータ領域 （uint32のサイズで領域にあるやつ） レジスタが skb->data （パケットデータの先頭）を指している レジスタが skb->data + headlen （パケットデータの終端）を指している 84
85. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int do_check(struct bpf_verifier_env *env) {(以下中略および重要なコードを抜粋 ) for (;;) { if (env->insn_idx >= insn_cnt) { verbose(env, "invalid insn idx %d insn_cnt %d\n", env->insn_idx, insn_cnt); return -EFAULT; } insn = &insns[env->insn_idx]; class = BPF_CLASS(insn->code); if (++env->insn_processed > BPF_COMPLEXITY_LIMIT_INSNS) { verbose(env, "BPF program is too large. Processed %d insn\n", env->insn_processed); return -E2BIG; } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L18291 レジスタの値と型の追跡 を行う関数 85
86. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int do_check(struct bpf_verifier_env *env) {(以下中略および重要なコードを抜粋 ) for (;;) { if (env->insn_idx >= insn_cnt) { verbose(env, "invalid insn idx %d insn_cnt %d\n", env->insn_idx, insn_cnt); return -EFAULT; } insn = &insns[env->insn_idx]; class = BPF_CLASS(insn->code); if (++env->insn_processed > BPF_COMPLEXITY_LIMIT_INSNS) { verbose(env, "BPF program is too large. Processed %d insn\n", env->insn_processed); return -E2BIG; } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L18291 命令インデックスが命令列の範囲外ではない事 をチェック 命令数の上限チェック (特権だと)100万命令が上限になってる 無限ループにして命令ごとに検証を実行 （以降はループの中で動作していることに して省略する） 86
87. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int do_check(struct bpf_verifier_env *env) {(以下中略および重要なコードを抜粋 ) if (is_prune_point(env, env->insn_idx)) { err = is_state_visited(env, env->insn_idx); if (err == 1) { goto process_bpf_exit; } } ・・・ if (class == BPF_ALU || class == BPF_ALU64) { err = check_alu_op(env, insn); if (err) return err; } else if (class == BPF_LDX) { ・・・ 　　　} else if (class == BPF_STX) { cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L18291 以前の検証済みのポイント があれば、枝刈りをする ALU/ALU64, LDX,STX,JMP, EXIT命令 に対して検証を実行している ここではALU/ALU64命令に対して検証 を実行している 87
88. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) {(以下中略および重要なコードを抜粋 ) u8 opcode = BPF_OP(insn->code); 　　　　if (opcode == BPF_END || opcode == BPF_NEG) { 　　　　} else if (opcode == BPF_MOV) {... 　　　　} else if (opcode > BPF_END) {... 　　　　} else { /* all other ALU ops: and, sub, xor, add, ... */ err = check_reg_arg(env, insn->dst_reg, SRC_OP); if ((opcode == BPF_MOD || opcode == BPF_DIV) && BPF_SRC(insn->code) == BPF_K && insn->imm == 0) { verbose(env, "div by zero\n"); return -EINVAL; } /* check dest operand */ err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); err = err ?: adjust_reg_min_max_vals(env, insn); cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14292 ALU（算術関連)の実装 を取り上げてみる 88
89. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) {(以下中略および重要なコードを抜粋 ) u8 opcode = BPF_OP(insn->code); 　　　　if (opcode == BPF_END || opcode == BPF_NEG) { 　　　　} else if (opcode == BPF_MOV) {... 　　　　} else if (opcode > BPF_END) {... 　　　　} else { /* all other ALU ops: and, sub, xor, add, ... */ err = check_reg_arg(env, insn->dst_reg, SRC_OP); if ((opcode == BPF_MOD || opcode == BPF_DIV) && BPF_SRC(insn->code) == BPF_K && insn->imm == 0) { verbose(env, "div by zero\n"); return -EINVAL; } /* check dest operand */ err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); err = err ?: adjust_reg_min_max_vals(env, insn); cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14292 基本的にはこのelseの中が算術系 でよく使われる操作（他は少し 変わったオペコードのケア） 89
90. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) {(以下中略および重要なコードを抜粋 ) 　　　　err = check_reg_arg(env, insn->dst_reg, SRC_OP); if ((opcode == BPF_MOD || opcode == BPF_DIV) && BPF_SRC(insn->code) == BPF_K && insn->imm == 0) { return -EINVAL; } if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) { int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32; if (insn->imm < 0 || insn->imm >= size) { return -EINVAL; } } err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); err = err ?: adjust_reg_min_max_vals(env, insn); cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14292 説明のためにelse節の 中身を抜き出す 90
91. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) {(以下中略および重要なコードを抜粋 ) 　　　　err = check_reg_arg(env, insn->dst_reg, SRC_OP); if ((opcode == BPF_MOD || opcode == BPF_DIV) && BPF_SRC(insn->code) == BPF_K && insn->imm == 0) { return -EINVAL; } if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) { int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32; if (insn->imm < 0 || insn->imm >= size) { return -EINVAL; } } err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); err = err ?: adjust_reg_min_max_vals(env, insn); cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14292 有効なレジスタかどうかの確認 （つまり初期化されていて 読み出せるということ) 91
92. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) {(以下中略および重要なコードを抜粋 ) 　　　　err = check_reg_arg(env, insn->dst_reg, SRC_OP); if ((opcode == BPF_MOD || opcode == BPF_DIV) && BPF_SRC(insn->code) == BPF_K && insn->imm == 0) { return -EINVAL; } if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) { int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32; if (insn->imm < 0 || insn->imm >= size) { return -EINVAL; } } err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); err = err ?: adjust_reg_min_max_vals(env, insn); cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14292 除算演算 or 剰余演算で 即値が0の場合エラーを返す つまりゼロで割ってしまうこ とを防ぐ シフト演算の範囲が 0~31,0~63以内かどうか でエラーを返す 92
93. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) {(以下中略および重要なコードを抜粋 ) 　　　　err = check_reg_arg(env, insn->dst_reg, SRC_OP); if ((opcode == BPF_MOD || opcode == BPF_DIV) && BPF_SRC(insn->code) == BPF_K && insn->imm == 0) { return -EINVAL; } if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) { int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32; if (insn->imm < 0 || insn->imm >= size) { return -EINVAL; } } err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); err = err ?: adjust_reg_min_max_vals(env, insn); cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14292 有効なレジスタかどうかの確認 （これはDSTなので、書き込み 可能かどうかを見ている） 93
94. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) {(以下中略および重要なコードを抜粋 ) 　　　　err = check_reg_arg(env, insn->dst_reg, SRC_OP); if ((opcode == BPF_MOD || opcode == BPF_DIV) && BPF_SRC(insn->code) == BPF_K && insn->imm == 0) { return -EINVAL; } if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) { int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32; if (insn->imm < 0 || insn->imm >= size) { return -EINVAL; } } err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK); err = err ?: adjust_reg_min_max_vals(env, insn); cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14292 レジスタ同士の計算可能な型をチェックもする レジスタの取りうる最大値/最小値を更新 or 確認 94
95. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, struct bpf_insn *insn) {(以下中略および重要なコードを抜粋 ) if (BPF_SRC(insn->code) == BPF_X) { src_reg = &regs[insn->src_reg]; if (src_reg->type != SCALAR_VALUE) { if (dst_reg->type != SCALAR_VALUE) {/* ポインタ += ポインタ の演算を禁止 */ } else {/* スカラー += ポインタの演算を処理 */} } else if (ptr_reg) {/* ポインタ += スカラーの演算を処理 */ } else if (dst_reg->precise) {/* Precise なスカラー値演算（今回はskip） */ } } else {/* 即値（imm）の処理 */ off_reg.type = SCALAR_VALUE; __mark_reg_known(&off_reg, insn->imm); src_reg = &off_reg; if (ptr_reg) /* ポインタ + 即値の演算を処理 */ return adjust_ptr_min_max_vals(env, insn, ptr_reg, src_reg); } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14157 adjust_reg_min_max_vals を掘り下げてみる 95
96. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, struct bpf_insn *insn) {(以下中略および重要なコードを抜粋 ) if (BPF_SRC(insn->code) == BPF_X) { src_reg = &regs[insn->src_reg]; if (src_reg->type != SCALAR_VALUE) { if (dst_reg->type != SCALAR_VALUE) {/* ポインタ += ポインタ の演算を禁止 */ } else {/* スカラー += ポインタの演算を処理 */} } else if (ptr_reg) {/* ポインタ += スカラーの演算を処理 */ } else if (dst_reg->precise) {/* Precise なスカラー値演算（今回はskip） */ } } else {/* 即値（imm）の処理 */ off_reg.type = SCALAR_VALUE; __mark_reg_known(&off_reg, insn->imm); src_reg = &off_reg; if (ptr_reg) /* ポインタ + 即値の演算を処理 */ return adjust_ptr_min_max_vals(env, insn, ptr_reg, src_reg); } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14157 ポインタ型のレジスタを含んで計算する場合 - ポインタ += ポインタ ->許可されない - ポインタ += スカラ -> 許可されて、ポインタの範囲と整合性を検証 （前述した拒否されるケースの例だ！） 96
97. レジスタに対する型の追跡 - レジスタが有効なメモリ領域を指していることを保証してることを理解する ために以下のようなポインタ型レジスタに対してポインタを足してみる - Verifierが型の観点で気にするのは以下のようなこと - スタックの初期化状態が行われてるか？ - 計算可能な型で実施されているか？ r0 = r10 - 8; // r0 は PTR_TO_STACK 型 r1 = r10 - 16; // r1 も PTR_TO_STACK 型 r2 = r0 + r1; // ポインタ同士の加算は不正 🙅 ポインタとポインタの足し算で失敗する図 97 再掲 これを検査してるところ がわかった！
98. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, struct bpf_insn *insn) {(以下中略および重要なコードを抜粋 ) if (BPF_SRC(insn->code) == BPF_X) { src_reg = &regs[insn->src_reg]; if (src_reg->type != SCALAR_VALUE) { if (dst_reg->type != SCALAR_VALUE) {/* pointer + pointer の演算を禁止 */ } else {/* スカラー値 + ポインタの演算を処理 */} } else if (ptr_reg) {/* ポインタ + スカラー値の演算を処理 */ } else if (dst_reg->precise) {/* Precise なスカラー値演算（今回はskip） */ } } else {/* 即値（imm）の処理 */ off_reg.type = SCALAR_VALUE; __mark_reg_known(&off_reg, insn->imm); src_reg = &off_reg; if (ptr_reg) /* ポインタ + 即値の演算を処理 */ return adjust_ptr_min_max_vals(env, insn, ptr_reg, src_reg); } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14157 即値（imm）を操作する場合は一時的にスカラー型レジスタとして 処理される （つまり、先ほどのはr1+=r2みたいなので、今回はr1+=1みたいな やつを意図しているということです 98
99. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, struct bpf_insn *insn) {(以下中略および重要なコードを抜粋 ) } else {/* スカラー値 + ポインタの演算を処理 */ return adjust_ptr_min_max_vals(env, insn, src_reg, dst_reg); } } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14157 レジスタの取りうる最大値/最小値を更新or確認 をしている 99
100. - レジスタの取りうる最大値/最小値を更新or確認するとは...? - Verifierはレジスタの取りうる値の区間を持って値の抽象化を実施している - 例えば R1 += R2 を考えた時にそれらのレジスタが演算前に取りうる値を [max, min]で考慮してみる - R1:[30, 10], R2:[10, -10] だとする - そうすると演算後にR1が取りうる値は[40, 0] となる - Verifierは [umax_value, umin_value] のような値を各レジスタごとに保持 して処理を実施している - 符号なし、符号あり、bit数でこの範囲の名前は変わる - これは具体的な値で評価することができないので抽象化している 値の抽象解釈 100
101. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int adjust_ptr_min_max_vals(省略){(以下中略および重要なコードを抜粋 ) if ((known && (smin_val != smax_val || umin_val != umax_val)) || smin_val > smax_val || umin_val > umax_val) { __mark_reg_unknown(env, dst_reg); return 0; } switch (opcode) { case BPF_ADD: if (known && (ptr_reg->off + smin_val ==(s64)(s32)(ptr_reg->off + smin_val))) { dst_reg->smin_value = smin_ptr; dst_reg->smax_value = smax_ptr; dst_reg->umin_value = umin_ptr; dst_reg->umax_value = umax_ptr; dst_reg->var_off = ptr_reg->var_off; dst_reg->off = ptr_reg->off + smin_val; dst_reg->raw = ptr_reg->raw; break; } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14157 adjust_ptr_min_max_vals を掘り下げてみる 101
102. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int adjust_ptr_min_max_vals(省略){(以下中略および重要なコードを抜粋 ) if ((known && (smin_val != smax_val || umin_val != umax_val)) || smin_val > smax_val || umin_val > umax_val) { __mark_reg_unknown(env, dst_reg); return 0; } switch (opcode) { case BPF_ADD: if (known && (ptr_reg->off + smin_val ==(s64)(s32)(ptr_reg->off + smin_val))) { dst_reg->smin_value = smin_ptr; dst_reg->smax_value = smax_ptr; dst_reg->umin_value = umin_ptr; dst_reg->umax_value = umax_ptr; dst_reg->var_off = ptr_reg->var_off; dst_reg->off = ptr_reg->off + smin_val; dst_reg->raw = ptr_reg->raw; break; } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14157 更新しようとしているレジスタの 最大最小の範囲に矛盾がないかを確認 （例えば最小のはずが最大より大きいと かだと困る 102
103. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる cf. https://github.com/torvalds/linux/blob/9f16d5e6f220661f73b36a4be1b21575651d8833/arch/x86/net/bpf_jit_comp.c#L178 static int adjust_ptr_min_max_vals(省略){(以下中略および重要なコードを抜粋 ) if ((known && (smin_val != smax_val || umin_val != umax_val)) || smin_val > smax_val || umin_val > umax_val) { __mark_reg_unknown(env, dst_reg); return 0; } switch (opcode) { case BPF_ADD: if (known && (ptr_reg->off + smin_val ==(s64)(s32)(ptr_reg->off + smin_val))) { dst_reg->smin_value = smin_ptr; dst_reg->smax_value = smax_ptr; dst_reg->umin_value = umin_ptr; dst_reg->umax_value = umax_ptr; dst_reg->var_off = ptr_reg->var_off; dst_reg->off = ptr_reg->off + smin_val; dst_reg->raw = ptr_reg->raw; break; } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L14157 32bitの整数範囲に含んでいるかを確認している 32bit castして値を切り飛ばした後、64bit cast して、比較するみたいなことをしている... 新しいポインタと符号なし整数 の最大最小の値を引き継ぐ 103
104. - 実は三段階目が存在しており、eBPFプログラムの最適化がされてる - DeadCode除去 - JUMP命令の分岐が実施されないよう、探索しなくて良いとされる到達不可能なコードを プログラムから削除することができる。 - あらかじめ最適化をすれば良いと考えるかもだが、移植性の観点から実行時に定数を 書き換えて切り替えてロードする前提だと異なるコードパスをロード時に拾う可能性がある - これによりランタイムのCPUサイクルを節約し高速化に貢献している - 命令のインライン化と書き換え - eBPFヘルパーに対する関数呼び出しはAPIとしての一面もあり、これを呼ぶことで安全に カーネルへのアクセスを担保できている側面がある。一方で関数呼び出しのオーバヘッド影 響が大きいケースがある(e.g. bpf_jiffies64のような時間に関する値)そこで、間接呼び出し 命令を透過的にinline化して直接呼び出しに変更することで高速化に貢献している eBPF Verifier Optimize 再掲 104
105. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u32 uattr_size) {(以下中略および重要なコードを抜粋 ) if (ret == 0) ret = optimize_bpf_loop(env); if (is_priv) { if (ret == 0) opt_hard_wire_dead_code_branches(env); if (ret == 0) ret = opt_remove_dead_code(env); if (ret == 0) ret = opt_remove_nops(env); } else { if (ret == 0) sanitize_dead_code(env); } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16494 以下のような最適化コードが動作 105
106. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u32 uattr_size) {(以下中略および重要なコードを抜粋 ) if (ret == 0) ret = optimize_bpf_loop(env); if (is_priv) { if (ret == 0) opt_hard_wire_dead_code_branches(env); if (ret == 0) ret = opt_remove_dead_code(env); if (ret == 0) ret = opt_remove_nops(env); } else { if (ret == 0) sanitize_dead_code(env); } cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16494 以下のような最適化コードが動作 実はCAP_BPFがついてる時は privilege(特権)として解釈され 最適化の内容が変わる 106
107. x86のレジスタのマッピング例 呼び出し規約に合致していることがわかる 戻り値,第1~5引数,呼び出し元保存 1~4…と対応してる int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u32 uattr_size) {(以下中略および重要なコードを抜粋 ) // loopの最適化、定数ループやネストしてないループ等の時にインライン化する（ +スタックが足りること ret = optimize_bpf_loop(env); // 条件式が常に真または偽である場合、その分岐を「ハードワイヤー化」する（結果を直接残す） opt_hard_wire_dead_code_branches(env); // CFG的に到達不可能な部分を削除する ret = opt_remove_dead_code(env); // nop と呼ばれる何もやらない命令を除去する ret = opt_remove_nops(env); cf. https://elixir.bootlin.com/linux/v6.12/source/kernel/bpf/verifier.c#L16494 動作コードの説明をしつつ抜粋 107
108. e.g. ハードワイヤー化の例（DeadCode除去） - 例えばコンパイラ時最適化されない定数評価できるモノの場合で、 尚且つvolatileがついているような定数に効果的 - 実行時にa=1と定数書き換えする場合でのケースの例を載せる volatile int a; int example() { if (a > 0) { return 1; } else { return 0; } } volatile int a; int example() { return 1; } 不要な分岐の削除 108
109. 落ち穂拾いとまとめ 109
110. - 時間や分量の関係で説明できないものを紹介するコーナーです - BTF方面について - BTFはeBPFプログラムの型情報が書いてるメタデータ（DWARFと似ている） - StructOpsと呼ばれるBPFでTCPの輻輳制御や、CPUスケジューラーを各機能を作るのに 使われてるフレームワークやオブザーバービリティで使われるbpf trampolineを理解する には必要な知識ではあるが、今回は省略しました...(正直、これだけでセッションになる😇） - eBPFの具体的な利用方法や実装テクニックなど - CloudNative関連でユースケースが多い、コンテナ間通信のあれこれや オブザーバービリティ方面の解説とかはeBPF本体ではないので諦めた - パケット処理方面は以前eBPF Meetupとかで話した話が参考になるかも... - cf.https://speakerdeck.com/takehaya/exploring-xdp-fundamentals-and-real-wo rld-implementations-in-mobile-network-data-plane 落ち穂拾い 110
111. - KFunc方面などのさらなるeBPFの拡張に関する話 - eBPF Linkのような、柔軟なアタッチ方法の話とか - JITコンパイルにおいて実行時の無効なアクセスによるページフォールトを例外 テーブルを用意してカーネルがクラッシュしないようにケアしてる話とか - eBPF Verifierがより頑張ってるところ or 諦めてるところの話 - 頑張ってる - ALU sanitationという領域外参照の緩和機構で攻撃対策してる話とか... - PREVALという形式検証で生まれたverifierがWindowsのeBPFに導入されてる話とか... - 諦めてる - ループの中で複雑なことをしてると、指数関数的に状態が増えてパス爆発を起こしてしまうの で命令数の制限が存在してる - あとは実際にはバグってたり想定外の挙動で脆弱性PoCとして選ばれがちというのを見て わかる通り、必ずしも安全性が100%保たれているとは限らないというのを頭の片隅に 置いてもらえると何かの時に役立つかも。eBPFプログラムは安全でも、カーネル内部利用する 先が安全ではないことがあるとか...etc 落ち穂拾い（説明ができてないところの紹介） 111
112. まとめ - eBPFのライフサイクルから、内部アーキテクチャまで説明しました - eBPFの仕組みを知ったことで、eBPFという技術がどのようにしたら使える のか？何故こんなにもCloudNaitve関連のプロダクトで使われるのか理解 できる素養を得ることができたと思ってます - 是非、カーネルの中でなんか動かしたくなった時はeBPFのことを思い出して 見てください :) 112
113. Thank you !!😻 @takemioIO @takehaya @takehaya 113
114. Enabling a Connected Future. 114
115. 参考資料 - https://github.com/torvalds/linux - https://docs.kernel.org/userspace-api/ebpf/syscall.html - https://man7.org/linux/man-pages/man2/bpf.2.html - https://speakerdeck.com/yutarohayakawa/ebpfhahe-gaxi-siinoka - https://mechpen.github.io/posts/2019-08-03-bpf-map/index.html - https://blog.yuuk.io/entry/2021/ebpf-tracing - https://atmarkit.itmedia.co.jp/ait/articles/1910/07/news008.html - https://arxiv.org/html/2410.00026v2 - https://lwn.net/Articles/982077/ - https://lwn.net/Articles/977815/ 115