どうも、ロバストと愉快な仲間たちのロバストこと、かわしんです。そうです、私がロバストです。
さて、8 月 13 日から 8 月 17 日までの 4 泊 5 日で セキュリティネクストキャンプ に参加してきました。
セキュリティネクストキャンプとは、セキュリティ・キャンプ全国大会 と同時期に開催されるネクストな感じのセキュリティキャンプです。
全国大会は 22 才までの一生に一度しか参加できないのですが、もう一度参加したいという卒業生をターゲットに今年から新しく始まったそうです。このネクストキャンプは 25 才までの学生であれば（詳しくは公式の募集要項を確認してください）卒業生でなくても同等の技術スキルがあれば参加することができます。
応募には審査があり、今年は 13 人の応募から 6 人が選ばれたそうです。
僕はセキュリティキャンプの存在を去年知った時にはすでに 24 才になっており参加できないことを残念に思っていたのですが、今年ネクストキャンプの存在を Twitter で知り参加することにしました。
講義としては、暗号化アルゴリズムの AES を FPGA に実装したり、XSS 文字列の検知するエンジンを機械学習で実装したり、複数の CPU アーキテクチャのエミュレータに実装された特殊命令のアルゴリズムを解析してそれをエミュレータに実装し直したりなど、主に手を動かして演習するタイプの講義が多く非常に勉強になりました。
参考 : セキュリティ・ネクストキャンプ2019 プログラム：IPA 独立行政法人 情報処理推進機構
実習講義が多い分、キャンプ開催前の事前学習やキャンプ中の宿題などタスクが多く眠れない充実した楽しい 5 日間を過ごすことができました。
さて、その授業の中で一番僕が楽しみにしていたのがこの「ロバストなプロトコルを考案せよ」という講義です。
これは、10BASE-T の LAN ケーブルの 4 対のツイストペアの 1 つにノイズを載せ、そのケーブルを使ってなるべく多くのファイル転送ができるようなプロトコルを考えて実装し、最終日にコンテストを行うものでした。僕はこのコンテストで１位をとり、ロバスト賞をいただきました。なので、僕こそがロバストです。
ファイルとしては事前に用意された 1000 個の 100KB 程度のランダムなバイナリファイルを転送し、チェックサムを確認して内容が正しいファイルのみをカウントします。間違ったファイルによるペナルティはありません。また出力するファイル名は元のファイルと異なっていても問題ないというレギュレーションでした。
ノイズはだいたい ping パケットが 50% 失敗する程度のノイズが発生させられます。
イメージとしてはこんな感じです。ノイズインジェクターはブラックボックスになっており、ピンを接続して利用します。
この画像のケーブルは講師の今岡先生が作成してくださったものですが、事前学習で自分でケーブルの被膜を剥ぐのは結構難しかったです。
僕の Robustp
この課題に対して僕は Robustp という独自プロトコルを設計して実装しました。（正確には実装しながら設計を進化させていますが）
github.com
これは、簡単にいうと UDP の上に TCP や QUIC のようなプロトコルを載せている感じです。
設計
Robustp は内部で 2 つのレイヤーに別れています。TCP を参考にしたファイル単位でセグメントの位置やファイルの完成などを管理する ファイル層 と、セグメントを TransID という一意で単調増加する ID で管理して再送やウィンドウ制御を行う トランスポート層 です。
ファイル層 は、各ファイルは一意な Fileno が割り当てられた FileContext 構造体で表現され、ファイルデータを分割したセグメントは Offset が割り当てられた FileSegment 構造体で一意に管理されます。これは TCP を参考にしており、TCP のポート番号が Fileno に対応し、TCP のシーケンス番号が Offset に対応しています。
ファイル層は各ファイルのどのデータが送信済み・受信済みであるのかとファイルのデータが揃っているのかを管理します。ファイル層では TCP と同じように Partial ACK を実現し、受信した全てのパケットの位置を ACK メッセージに詰めて応答し、無駄な再送を防ぎます。
トランスポート層 は FileSegment をラップした TransSegment に TransId を紐づけて管理します。それぞれの TransSegment は WindowManager 内のウィンドウバッファで管理され、WindowManager は、ウィンドウサイズ制御、RTTの計測、再送タイマー、欠損したACKの即時再送 などの機能を提供します。TransId は QUIC での Delivery Order Id の考え方を参考にして実装されており、再送が必要な場合は新しい TransId を割り当てて再送することで RTT 計測のロジックがシンプルになります。
最初は TCP を参考にファイル層のみで実装をして Fileno と Offset （実装当時は Seqno だった）でセグメントを一意に管理して再送を行なっていましたが、再送パケットの RTT 計測ができなくなる課題を抱えていて悩んでいました。
その時にちょうど ぺトロン 君に QUIC の論文 1 を教えてもらい、読んでみると QUIC では再送などを管理する Delivery Order Id とデータの位置を管理する Stream Offset を分離しているという考え方を知りました。それを TransID という形でトランスポート層を分離して実装しました。
Add TransId · kawasin73/robustp@c585c66 · GitHub
ちょうどこのコミットで対応していますが、ファイル層の操作をうまく抽象化していたのでそこまで載せ替えるのは大変ではなかったです。
それぞれのメッセージは、Ethernet の 1 フレームに収まるように 起動時にコマンド引数で渡される MTU（1500 バイト）からセグメントのサイズを調整します。複数のフレームに UDP パケットが分割されると 1 つのフレームが落ちただけでパケット全体をロスしてしまうのを防ぐためです。
ファイル層とトランスポート層の間はシンプルな 4 つのインターフェイスだけが定義されています。
ファイル層からトランスポート層へは Sender の sendThread() メソッド内に定義された sendSegment() マクロを呼び出します。このマクロは、WindowManager.Push() メソッドを呼び出してセグメントをウィンドウに追加してパケットを送信します。
トランスポート層からファイル層へは以下の 3 つのインターフェイスが FileSegment に定義されています。
TransId 付きのデータメッセージを作成する PackMsg()- ACK メッセージを受信した時に呼び出す
Ack()
- セグメントを再送する時に Partial ACK によってファイル層が知っている再送の必要がないかどうかの情報を問い合わせる
IsCompleted()
この辺りの機能の分離とインターフェイス設計は綺麗にできたと自分では満足しています。
ヘッダはこんな感じになっています。
赤い部分がファイル層のためのヘッダで、青い部分がトランスポート層のためのヘッダです。どちらかというと TransId を先頭の方に持ってきたかったのですが、これは歴史的経緯です。変更するのがめんどくさかったのでこのままにしました。
送信側のコンポーネントはこのように設計されて実装されています。
上の FileContext と FileSegment がファイル層、WindowManager と Enqueuer と Receiver がトランスポート層です。FileSegment が WindowManager からのファイル層へのインターフェイスになっています。
WindowManager の導入が一番難しかったです。このコミットで対応していますが、WindowManager にどの機能（タイマーや RTT 収集など）を含めるかを悩みました。
Add WindowManager · kawasin73/robustp@35836c5 · GitHub
CongestionControlAlgorithm による輻輳制御アルゴリズムの抽象化
TCP では様々な輻輳制御アルゴリズムが提案されています。Robustp ではそれを CongestionControlAlgorithm というインターフェイスで抽象化して輻輳制御アルゴリズムを差し替え可能にしています。
それぞれのアルゴリズムは以下の 2 つのメソッドを実装したものであり、最終的には本番では、Vegas という RTT の遅延を元にしたアルゴリズムにデータロスト時のペナルティを加えた独自のアルゴリズムを実装してコンテストに挑みました。
type CongestionControlAlgorithm interface {
Add(status uint8, sendAt time.Time, rtt time.Duration)
WindowSize() int
}
RTOCalclater による RTO 計算の抽象化
また、RTT（Round-Trip Time）から再送タイマーの長さ RTO（Retransmission Time Out）を算出するアルゴリズムも TCP では複数提案されています。
これも RTOCalclater というインターフェイスで抽象化して差し替え可能にしています。本番では実験する時間がなくてシンプルに RTT の倍の時間を RTO とする RTOCalclater を設定しました。
type RTOCalclater interface {
Update(rtt float64, rttTable []float64) time.Duration
}
再送メッセージがウィンドウを溢れた場合の再送バッファ
ウィンドウサイズは RTT やメッセージのロストによって小さくなったり大きくなったりします。そのため、パケットの再送時にはウィンドウサイズが小さくなって再送できない場合があります。その場合は Enqueuer 内の再送バッファに一時的に貯めておいて、ウィンドウサイズを忠実に守るように工夫をしました。
欠損 ACK の即時再送
今回のコンテストの特徴として 1 本のケーブルのみを占有して利用します。送信したメッセージは全て同じ通信路を通るためメッセージの順序の入れ替わりはありえません。
TCP では 3 回同じ ACK を受け取ったらそれ以前のメッセージはロストしたものとして再送する高速再送アルゴリズムが提案されていますが、今回の講義では 1 つでも TransId が飛んだ ACK メッセージが返ってきた場合はそれ以前のメッセージはロストしたものとして即時に再送するナイーブな実装になっています。
もし IP ネットワークの上をメッセージが流れる場合はもうちょっと緩めの判定をする必要があります。
整合性の検査
データペイロードがノイズによって書き換わっていないかの検証は、UDP のチェックサム機能を利用して、Robustp 自体では実装していません。UDP のチェックサムで整合性の検証をサボることができたのは IP ソケットではなく UDP ソケットを選んだ理由の１つです。
ここまでの機能の設計と実装は、DMM でのインターンの時に学んだシンプルな実装を愚直に積み重ねていく経験がなかったらできていなかったと思います。DMM でインターンして身に付けることができたスキルを自分で実感しました。
Go の採用
この Robustp は Go で実装しました。
この一番の理由は クロスプラットフォーム に対応しており OS ごとの違いを抽象化して隠蔽してくれているからです。コンテストは貸与された Windows PC で行うレギュレーションがあったので、開発を macOS で行う僕としてはクロスプラットフォームは必須でした。Go では UDP ソケットは net.UDPConn という構造体で抽象化されています。
クロスプラットフォームでありながら OS に近い機能のインターフェイスを提供してくれているので今回の課題にはぴったりでした。
GC 言語なので ガバガバとメモリを確保できる気楽さ もあります。今回は速さを競い、プログラムのメモリ量などは気にしないので普段のプロダクトよりも気楽にメモリを確保するプログラムを書いていました。
Queue を C などで実現しようとすると、リングバッファや要素のずらしなどをしないといけませんが、Go ではスライスで以下のシンプルな表記で Queue が実装できて新しいバッファの確保などは Go のスライスが行なってくれます。もちろんスライスの拡張時にコピーやメモリの確保・破棄が起こるのでリングバッファほどのパフォーマンスは出ませんが、初期のプロトタイプの実装では素早く Queue を実現できます。
var queue []Item
queue = append(queue, Item{})
item, queue = queue[0], queue[1:]
コンパイルされるため そこそこ速い ということもあります。もちろん C ほどの速度は出ませんが 10BASE-T を使う以上、極上の速さは求められないと考えて Go にしました。
並列・並行処理が簡単 に行えることも Go の便利な点です。1 プロセスでクライアント側の送信スレッド、受信スレッドと、サーバ側の送受信スレッドの 3 並列のプログラムにする必要があったので便利でした。
結果
60 秒間の間に送信する試行をクライアント側ポートとサーバ側ポートを変えて 2 回行いました。
結果は、1回目が 399 ファイルの転送に成功して全てのファイルの中身が壊れておらず、2 回目は 475 ファイルの転送に成功して全てのファイルが壊れていないという結果になり、堂々の 1 位を受賞しました。
3 位は TCP の上に grpc を載せて転送して 65 ファイルと 36 ファイル、4 ~ 6 位の転送ファイル数は 1 桁だったので圧勝と言えます。
僕が特に面白かったのは 2 位の aso 君で、1 回目は 347 ファイルを転送して 163 ファイルが正常なファイルで、2 回目は 799 ファイルを転送して792 ファイルが正常という驚異のパフォーマンスを見せていました。残念ながら 2 回目の試行は制限時間内に終わらなかったため参考記録ですが、驚異の結果です。
彼は、プロトコルなどなく、各ファイルを 50 KB の 2 つのブロックに分割し UDP パケットにして片っ端から送りつけ続け、全ファイルを送り終わったらまた先頭から送り直し、受け側では連続する2つの UDP パケットを結合して保存するだけでレスポンスはしないというシンプルなものでした。
何も考えないでファイルを片っ端から送り続けてそのうちのいくつかが正常ファイルだったらいいねという大胆なこんなんプロトコルじゃねーだろとも言えるシステムですが、不正ファイルが無視されるというレギュレーションを逆手に取ったスマートな方法だったと思います。これには度肝を抜かれました。
今回のケーブルはツイストペアの 1 対にだけノイズを載せます。全二重通信では、上りか下りのどちらかだけにノイズがのるため、ノイズがのらない方が上りになる 2 回目では圧倒的なパフォーマンスが得られたようです。そりゃそうか。
やり残したこと
事前学習で実質プログラムを書いていたのはキャンプが始まる前日の1日で、キャンプ中も他の講義の宿題で忙しく隙間時間で実装していたので実質 2~3 日分くらいしか実装していません。（最終日の夜は朝の5時半まで徹夜して時間を稼ぎました）
なので、もちろん効率の悪い部分だったり、やりきれなかった機能が残っています。ざっと羅列していきます。
- writev によるメモリコピーの削減
- ファイルデータメモリから送信バッファへコピーしているのを writev などによって効率化できれば速くなっていたはず
- Receiver がセグメントサイズを暗黙知に依存している
- プロトコルヘッダーはバイト単位なので任意のセグメント分けができるが、実装を簡単にするためにクライアント・サーバの両方に同じ MTU を渡し、MTU を元に共通のセグメントサイズを持つという実装にしていた
- 実際の世界ではセグメントサイズは一定ではないはずなので任意のセグメントサイズに対応できるように区間木などのデータ構造を導入する
- window をリングバッファにする
- Go のスライスを使った簡易な Queue になっているのでリングバッファに書き換える
- リングバッファによってメモリコピーやメモリアロケーションが減るはず
- TransId のローテーション
- 今回は 60 秒程度しか動かさないので TransId はインクリメントさせるだけだった。32 bit 整数なのでローテーションに対応する必要がある。
- 輻輳制御アルゴリズムをもっと試す
- Cubic とか試してみたかった
- 体力の限界で Vegas アルゴリズムを実装するところで諦めてしまった
- ファイル送信完了の仕組み
- ファイル送信が完了したらサーバ側の FileContext を削除できるようにするとメモリ効率が上がる。コンテストではメモリリークは関係ないので対応していなかった
- 実現するためにはファイル転送の開始と終了をクライアントとサーバ側で同期する必要がある。SYN/ACK, FIN/ACK などの TCP でのコネクション管理をファイルごとにする必要がある
- ファイル名も送る
- プロトコルの中にファイル名も送る仕組みを入れると実用的になる
- リンク層を相手にプロトコル構築
- そもそも IP + UDP の上に乗っかっているので MAC アドレスを直接指定して送信しあう TCP/IP スタックのようなものを実装しても良かった
- プログラムの規模が大きくなるので実装コスト的に UDP で甘えてしまった
- UDP ではチェックサムが異常なファイルは全て捨てていたが、データ訂正の仕組みを入れるなどもできる
最後に
疲れました。とっても。でもとても楽しかったです。
来週の月曜（8/26）からは Klab での TCP/IP プロトコルスタック自作のインターンを受講してきます。奇しくも今回の経験がめちゃめちゃ役に立ちそうです。
また、マスタリング TCP / IP を本屋さんに買いに行った時に出会ったこの本がものすごく役に立ったので共有しておきます。
それでは。
