あどけない話

Internet technologies

HaskellによるQPACKの実装

Haskell QUIC

いやいや、難産だったよ。

2020年から2021年にかけて、HaskellでHTTP/3ライブラリを作成する過程で、QPACKを実装した。HPACKやQPACKでは、圧縮を担う符号器(encoder)よりも、伸長を担う復号器(decoder)の方が、圧倒的に簡単である。このため、Haskellの復号器は、静的表に加えて動的表も使うように実装できたが、符号器は難し過ぎて静的表しか活用しない状態でライブラリをリリースした。

2021年に執筆した「QUICをゆっくり解説(16)：ヘッダ圧縮」の「おわりに」では、

私の現時点の実装では、圧縮側は動的表を全く利用していません。この記事を書いたことをきっかけに、実装に挑戦してみようかと思います。

と表明してた。

あれから4年。ようやく時間が取れたので、符号器を動的表に対応させる宿題に取り組んだ。

このブログは、QPACKを実装した経験の備忘録である。HPACKは知っているけど、QPACKはよく分からない人の役に立つかもしれない。

用語は、今どきの IETF 用語に合わせる。

  • フィールド名 - 世間で言うヘッダ名
  • フィールド値 - 世間で言うヘッダの値
  • フィールド：フィールド名とフィールド値の組
  • セクション - フィールドの集合。いわゆるヘッダ。

仕様

QPACKの目的は、HPACKの Head-of-Line ブロッキングを「緩和」することである。HPACKでは、セクションが圧縮された順番で、伸長される必要があった。パケットの欠損などにより、途中の伸長が止まれば、たとえ以降のセクションが届いていても、伸長の工程は止まる。

QPACKでは、伸長側(復号器)をできるかぎり並列化できるように設計されている。鍵となるアイディアは、「動的表の更新命令」(encoder instruction)と「フィールド表現」(field representation)を分離することである。

HPACKでは、これらの区別がなかった。そのため、動的表を変更するセクションに次のセクションが依存し、後続のセクションもまた依存しと、依存の連鎖が起きていた。

QPACKでは、動的表の更新命令を一方向ストリームで送る。フィールド表現は、HTTPのリクエスト＆リスポンスをやりとりするための、双方向ストリームで送る。このHTTPのストリームは、更新命令を送るストリームにのみ依存する。

動的表の更新命令

動的表に登録されるエントリは、フィールドである。動的表の更新命令(encoder instruction)は以下の通り：

  • 動的表の大きさの設定
  • 「文字列のフィールド名」(literal)を使ったエントリの挿入
  • 「フィールド名の参照」(index)を使ったエントリの挿入
  • エントリの複製 (duplicate)

HPACKでは、静的表と動的表のインデックスが同じ空間として扱われていた。静的表のエントリ数は61なので、動的表のインデックス62から始まる。動的表は62以降をFIFOとして使う。つまり、新しく挿入したエントリのインデックスは62であり、その挿入によって元々のエントリのインデックスは1増加する。動的表の大きさを超えた古いエントリは、動的表から削除される。明示的な削除命令はない。

QPACKでは、静的表と動的表のインデックスは、別の空間として扱われる。動的表のインデックスは、単調に増加する。単純に大きなインデックスを符号化すると、バイト数が大きくなるので、動的表の更新命令では、「挿入点」(insertion point)からの相対値で表現される。挿入によって動的表の大きさの制限を超えると、必要な分、古いエントリが削除される。明示的な削除命令はない。

ここが重要なのだが、QPACKの動的表に挿入するエントリは、これから追い出されるエントリを参照してもよい。もちろん、追い出された後のエントリは参照してはならない。

フィールド表現

フィールド表現は、以下の3つに大別される。

  • インデックスを使ってフィールドを表現する
  • インデックスを使ってフィールド名を表現し、フィールド値には文字列を使う
  • フィールド名にもフィールド値にも文字列を使う

符号器は、これから圧縮するセクションに対して、現在の挿入点を「基準点」(base point)とて指定する。フィールド表現で使われるインデックスは、バイト数を抑えるために、基準点からの相対値を利用する。圧縮開始までに挿入されているエントリのインデックスは、基準点よりも小さい。圧縮中に挿入されたエントリのインデックスは、基準点の値以上となる(post base-indexing)。

重要なのは、(「動的表の更新命令」の節で説明した「これから追い出されるエントリ」も含めて)動的表にないエントリは、参照してはならないことである。

並列化

圧縮されたセクションには、圧縮されたフィールドと基準点に加えて「必要挿入数」(required insert count)が付与される。復号器の動的表に、少なくとも必要挿入数分のエントリが挿入済みであれば、そのセクションの伸長は「ブロックされない」。不足していれば、「ブロックされる」。

復号器は、動的表に挿入されたエントリの数を以下のACK(decoder instruction)によって通知できる。

  1. 動的表に新たに何個エントリを挿入したかのACK
  2. 圧縮されたセクションを伸長できたことのACK

1)は直感的に分かりやすい。動的表の更新命令に対して、ACKを返すからである。2)は、復号側で動的表を管理しないコードが発するACKなので、少し分かりにくい。

実装モデルとして、スレッド・プログラミングを考えよう。リクエスト＆リスポンスに1スレッドを割り当てるとする。(1HTTPストリーム、1スレッドという意味。)

リクエストは同時に複数発生するかもしれない。実装して分かったのだが、圧縮側には並列性は必要ない。HoLブロッキングは、伸長側の問題なので、圧縮側は直列に実装するのが理にかなっている。

あるスレッドがリクエストのセクションを圧縮する際は、動的表をロックする。そして、動的表の操作命令が発生した場合は、それを専用の一方向ストリームで送る。また、圧縮したセクションを、双方向のHTTPストリームで送信する。

伸長側では、動的表の操作命令を一方向ストリームから読み取り、動的表を操作する専用スレッドが必要である。このスレッドのみが、動的表に書き込む。書き込めたら、「この専用スレッドが1)のACKを返す」。

リクエストが送られてくるHTTPストリームを読み込むスレッドは、動的表を読む。読むだけなので、並列化できる(ロックは必要ない)。動的表に必要なだけエントリが挿入されていれば、このスレッドはブロックされない。そうでなければ、ブロックされる。セクションの伸長が終わったら、「このHTTP用のスレッドが2)のACKを返す」。

圧縮側にも、ACKを読み込んで処理するための専用スレッドが必要である。2)を処理するためには、あるセクションに対する「ストリーム番号」と「必要挿入数」を記録しておく必要がある。2)のACKが返れば、その必要挿入数分、挿入されたと判断できる。

動的表を参照しない場合、符号器は必要挿入数に0を指定する。復号器は、必要挿入数が0の場合、2)のACKは返さない。

ブロックされてもよいストリーム数

動的表の大きさに加えて、もう一つのパラメータとして、「ブロックされてもよいストリーム数」がある。この値が許す限り、送信側は、「ACKが返っていない動的表のエントリを参照したフィールド表現」を含むセクションを送信してもよい。

伸長側は、2)のACKを返すだけで十分であると考えがちだが、実際は1)のACKも返す必要がある。たとえば、現在のブロックされてもよいストリーム数が0だとしよう。

  • 圧縮側は、将来のために動的表の挿入命令を送る
  • ブロックされてもよいストリーム数が0なので、新たに挿入したエントリは参照できない
  • 動的表をまったく参照しないで圧縮し場合、必要挿入数には0が指定される
  • 伸長側は、そのセクションを伸長する際、必要挿入数が0なので、2)のACKは返さない

これだけだと、将来使うためのエントリには、ACK は返ってこないので、いつまでたっても利用できない事態に陥る。そこで、伸長側は、少なくとも必要挿入数が0の場合、1)のACKを返す必要がある。

そろそろ、嫌になってきたでしょ。

動的表の大きさ

HPACKもQPACKも最初の大きさは0で、初期値を交渉することで、大きさを決定する。HPACKでは、最初のセクションを送信する前に、大きさが決定されることが保証されている。QPACKでは、初期値を交渉を待たずに、セクションを送ることができ、その場合の動的表の大きさは、もちろん0である。この短い期間内では、動的表は使えないので、静的表だけ活用してセクションの圧縮を試みる。

後述のように、この性質をうまく利用したエントリ管理の方法(ニーモニック技法)がある。

エントリの削除

HPACKでは、動的表の末尾から自由にエントリを削除できた。

QPACKでは、動的表の各エントリに対して、どのセクションから参照されているかのリファレンス数を管理しないといけない。参照する際にリファレンス数を増やし、2)のACKが返って来れば、対応するエントリのリファレンス数を減らす。

動的表の末尾のエントリは、リファレンス数が0の場合にのみ削除できる。つまり、エントリを挿入する際は、末尾からリファレンス数が0のエントリが連続しているかを調べ、「それらの合計数」と「未使用の大きさ(使いきれないギャップ)」の合計が、新たに挿入するエントリの大きさ以上の場合に限り、そのエントリを挿入できる。

末尾にリファレンス数が0のエントリが連続するようにする技法として、RFC 9204では「排除点」(draining point)が紹介されている。見付かったエントリが、排除点よりも小さい場合は、利用しない。そうすれば、新たな参照は発生しないので、いずれリファレンス数が0になるという訳である。

Haskellでの実装

Haskellには軽量スレッドがあるので、上記のスレッド・プログラミングを採用している。

初期実装

符号器を動的表に対応させる初期の実装としては、RFC 9204 の内容に従って排除点を利用していた。動的表から見付かったエントリのインデックスが、排除点よりも小さい場合、それは利用しない。可能であれば、そのエントリを複製して、利用しようとする。

この時点でのコードは、見通しが悪かった。なぜなら組み合わせ爆発が起きていたからである。

  • 検索結果の種類
    • 「フィールド」が見付かった
    • 「フィールド名のみ」が見付かった
    • 見付からなかった
  • 表の種類
    • 静的表
    • 動的表
  • 排除点との関係
    • 排除対象
    • 排除対象外

QIFs

QIFsとは、QPACKの相互接続性検証プロジェクトである。ここには、Facebook と netbsd.org でサンプリングされたセクション群と、各QPACK実装での圧縮結果が置かれている。

Haskellの復号器は、これらの圧縮結果を伸長することで、正しさを検証していた。

圧縮するためのパラメータは以下の通り：

  • 動的表の大きさ：0、256、512、4096
  • ブロックされてもよいストリーム数：0、100
  • ACK: ACKはまったく返されない(no)、すぐにACKが返される(yes)

ACKに関しては、解釈の範囲が広い。Haskellのテストプログラムでは、あるセクションに対して、ある圧縮したセクションと動的表の操作命令両方を送信し終えた直後、1)と2)のACKが返ってくるという解釈を採用した。(動的表の操作命令ごとに1)のACKが返るのではなく、セクション単位でまとめて返るという意味。)

長い期間、他の実装と圧縮率の傾向に相違があって、ずいぶんと悩んだ。そうして、ようやく期待される振る舞いを理解した。下2つのパラメータの組み合わせに対して、符号器の期待される振る舞いを記す。

  • (0, no)：動的表は育ててもよいが、ACKは返ってこないので、動的表はまったく参照できない
  • (0, yes)：育てた動的表は、次のセクションから利用できる。
  • (100, no)：100つのセクションまでは、挿入したエントリをすぐに利用できる。101目以降は、動的表は活用できない。
  • (100, yes)：挿入したエントリをすぐに利用できる。

ngtcp2/nghttp3

QIFs のセクションを Haskellの符号器で圧縮した結果は、まず Haskell の復号器で伸長できることを確かめた。

次に、ngtcp2/nghttp3を使って、Haskellで圧縮したセクションを伸長できるか検査した。ngtcp2/nghttp3の実装は、極めて正確であり、安心して信頼できた。また、僕が慣れているC言語で書かれているので、printf debug できるようにコードを変更しやすかったのも助かった。

ニーモニック技法

QIFs に圧縮結果を登録しているLITESPEEDのブログサイトに「Developer’s Corner: QPACK Mnemonic Technique」という記事を発見した。

QPACKに挿入されるエントリは、HPACKよりも追い出しにくいので、挿入するエントリを慎重に選ばないといけない。多くの実装では、フィールド名ごとに挿入するかしないかの情報をアドホックに定義して使っている。

この記事で紹介されている「ニーモニック技法」のアイディアはこうだ。利用されたフィールドの「集合」を管理する。その集合を利用して、2回以上フィールド(あるいはフィールド名)が利用された場合に限り、動的表に挿入する。

最初の出現では動的表には登録しないので、それがよく使われるフィールドであれば、出遅れた分、圧縮率が悪くなるかと思いきや、動的表の大きさの初期値は0なので、ペナルティは発生しないのである。

Haskellでも、ニーモニック技法を採用している。

逆インデックスと排除エントリ

「排除エントリが見付かった場合には複製すべき」という思い込みによって、初期実装では、組合せ爆発が起きていた。あるとき、「複製は一旦あきらめて、排除エントリを検索対象から外せば組み合わせの数が低減されるのでは？」というアイディアを思いついた。

動的表にインデックスでアクセスするとフィールドが得られる。逆にフィールドからインデックスを得るためには、何も工夫がなければ、動的表を端から端まで走査しなければならない。

Haskellの符号器では、高速化のために逆インデックスを持っている。この逆インデックスから排除エントリを排除することにした。検索できるエントリは、排除エントリでないことが保証されたため、コードが簡潔になった。

そもそも、ニーモニック技法を使っているので、排除点が不要なのではないかと思って試したが、排除点は圧縮率に貢献していることが分かった。

フィールド名

圧縮率を比較していて、なかなかLITESPEEDの性能に迫れなかったとき、LITESPEEDの圧縮結果を解析すると、LITESPEEDでは動的表の(フィールドではなく)フィールド名をうまく活用していることが分かった。

動的表のフィールド名は、QPACKの魔境である。

動的表をフィールドのみで利用するのであれば、逆インデックスは「フィールド→インデックス」というデータ構造で済む。フィールド名(のみ)も利用するであれば、「フィールド名→(フィールド値→インデックス)」というデータ構造が必要となる。

あるフィールド名に対して、「フィールド値→インデックス」は複数登録されうるから、どのエントリを利用するかが問題となる。最近のエントリを使うと「要求挿入数が大きくなる」(ブロックされる確率が上がる)し、古いエントリを使うと「リファレンス数が増えて、そのエントリを削除しにくくなる」というジレンマがある。

さらに、古いエントリが排除エントリであるかもしれないという問題もあったが、この問題は上記のアイディアで考えなくてもよくなった。排除エントリでない、もっとも古いエントリを発見するために、「フィールド値→インデックス」のデータ構造としては、PSQ(Priority Search Queue)を利用することにした。

  • key はフィールド値
  • value はインデックス
  • priority もインデックス

とすると、

  • key による検索は O(log n)
  • key による削除は O(log n)
  • 最小の priority のエントリを発見するには O(1)

である。

これに加えて、ニーモニック技法の集合にも、フィールド値を空文字列としたフィールドを登録しなければならない。

動的表のフィールド名を参照しながら、動的表に新しいエントリを追加する場合、参照したエントリが動的表から削除される可能性がある。フィールド表現では、この削除されたエントリを参照してはならない。

末尾複製

複製に関して、末尾複製(tail duplicate)というアイディアを思いついた。動的表の操作命令では、これから削除されるエントリを参照してもよい。末尾を複製すれば、先頭に追加されたエントリと末尾のエントリのサイズは同じなので、動的表の大きさを気にせずに削除できる。(ただしリファレンス数が0の場合に限る。)

あとは、いつ末尾複製するかである。いろいろ試したが、動的表がいっぱいでフィールドを挿入できない場合、つまり「フィールド名にもフィールド値にも文字列を使う」フィールド表現を発行した場合に、末尾のエントリのリファレンス数が0であり、これまで一定数(現在は10)使われていたなら、末尾複製するのが一番圧縮率が高かった。

圧縮率

参考までに、現時点での圧縮率の結果を示す。

qifs/encoded/qpack-05/haskell-quic/fb-resp.out.4096.0.0   62.0
    qifs/encoded/qpack-05/ls-qpack/fb-resp.out.4096.0.0   62.0
     qifs/encoded/qpack-05/nghttp3/fb-resp.out.4096.0.0   82.9

qifs/encoded/qpack-05/haskell-quic/fb-resp.out.4096.0.1   18.9
    qifs/encoded/qpack-05/ls-qpack/fb-resp.out.4096.0.1   17.3
     qifs/encoded/qpack-05/nghttp3/fb-resp.out.4096.0.1   37.6

qifs/encoded/qpack-05/haskell-quic/fb-resp.out.4096.100.0 50.4
    qifs/encoded/qpack-05/ls-qpack/fb-resp.out.4096.100.0 50.8
     qifs/encoded/qpack-05/nghttp3/fb-resp.out.4096.100.0 50.6

qifs/encoded/qpack-05/haskell-quic/fb-resp.out.4096.100.1 19.7
    qifs/encoded/qpack-05/ls-qpack/fb-resp.out.4096.100.1 15.2
     qifs/encoded/qpack-05/nghttp3/fb-resp.out.4096.100.1 19.4

これは、あくまでFacebookのサイトのサンプリングに対する結果である。入力データが変われば、結果も変わる。

LITESPEEDの圧縮率に肩を並べるには、複製のアルゴリズムを工夫しなければならないようだが、まだ何もアイディアを思いつかない。

おまけ

HPACKを実装したときとは違って、QPACKの実装過程では、特に目新しいことは発見できなかった。貢献できたことは以下の通り：

謝辞

安定したQPACKの実装を提供しており、またいくつかの質問に答えてくださった Tsujikawa さんに心から感謝します。QPACKに関する素敵なブログを公開してくださった Dmitri Tikhonov さんにお礼を申し上げます。

Encrypted Client Hello の実装

TLS

ECHをHaskell tlsライブラリに実装した話。先に「Encrypted Client Hello の仕様」を参照のこと。Haskellで実装した経験談なので、Haskellの知識を前提に書く。

ライブラリの構成

バックエンド・サーバの設定情報である ECHConfigList は、DNSを通じて提供され、TLSクライアントとTLSサーバで利用される。ECHConfigList の型や、その符号器/復号器をどのライブラリで実装するか決める必要がある。

tls ライブラリをECHに対応させると、ECHConfigList を利用するのは当然である。僕の希望としては、IIJが開発している DNS検索コマンドdug で HTTPS RR を検索したときに、ech パラメータが16進数表記されるのではなく、ECHConfigList を利用してユーザに分かりやすく表示されるようにしたい。

dug は、HTTPS RR を提供する dnsext-svcb ライブラリに依存している。ECHConfigList を tls から提供すると dnsext-svcb が tls に依存するし、逆もまたしかりである。両者は本来独立であるので、この依存関係が発生するのは嬉しくない。そこで、依存するライブラリの数が少ない ech-config というライブラリを新たに作り、そこに格納することにした。

ECHConfigList には HPKE のパラメータに関する情報が含まれている。ech-config が、新たに作成する hpke ライブラリに依存すると、単なる型情報を提供する ech-config が、暗号ライブラリ crypton に依存してしまう。これは避けたい。

という訳で、ECHConfigList を適切な型で表現するのは諦めた。たとえば、hpkeライブラリから提供される AEAD_ID を使いたくなるが、それは我慢して Word16 を使うといった具合だ。

最終的なライブラリの依存関係は、以下の図の通り。

ライブラリの依存関係

HPKEの実装

HPKE用のモジュールは、crypton に収めてもおかしくないが、hpkeという別のライブラリにすることにした。hpkeの作成にあたっては、以下のようにcryptonを拡張する必要があった。

  • ChaCha20Poly1305 が AEAD として利用するには中途半端な状態だったので、これを直した。
  • ECDHEの秘密鍵から公開鍵を作る関数は内部で実装されているものの、公開されていなかったので、型クラス EllipticCurve のメソッドして提供するようにした。

大局的に言うと hpke ライブラリは、HPKEのパラメータと crypton から提供される関数をつなげる役割を果たす。最初はよい構成が発見できず紆余曲折したが、同僚の日比野さんと議論した結果、最終的には以下のように拡張可能な構成となった。

  • HPKE パラメータは、(拡張不可能な直和型ではなく) 拡張可能なように PatternSynonyms を使う
  • HPKE パラメータをキー、呼び出す関数を値とした、連想配列を渡せる内部関数を作り、Internal モジュールから提供して拡張可能とする。
  • デフォルトのAPIでは、この連想配列は渡さなくてよく、簡便に利用できる。
  • crypton の関数は、型クラスで提供されているものが多い。つまり関数名は同一だが、型が異なるので、そのままではリストに格納できない。そこで、存在型を使って同一の型にすることで、連想リストに収める。

RFC 9180の付録にはテストベクターが載っているが、定義されているAPIでは、これらを直接活用することはできない。なぜなら、APIでは、送信側の秘密鍵は内部で動的に生成されるので、秘密鍵を外から指定するのは無理である。そこで、秘密鍵を指定できる内部関数を作って、内部関数をテストの対象とすると共に、API では動的に生成した秘密鍵を内部関数に指定するようにした。

Haskellの型システムは、RFC 9180の仕様にマイナーなバグがあることを教えてくれた。一般的に、鍵を派生させる手続では、共有した鍵を extract して expand する。Export は export_secret を expand するように定義してあるのだが、export_secret はすでに expand した値である。(型の弱いプログラミング言語で考えていると、何でもかんでも文字列で表現するので、よくこういう間違いを犯す。)

ECH Config の実装

下位の符号/復号ライブラリとして、最初は tls で利用されている cereal を利用したが、dnsext-scvb から ech-config を利用してみると、dnsext-scvb が依存している network-byte-order の方がよいことが分かり、そちらに移行した。

ech-config には、設定情報や秘密鍵を生成するためのコマンド ech-gen を収めた。設定情報や秘密鍵をサーバに渡す書式は標準化されていないので、ECH の各実装は独自の書式を採用している。ech-gen は僕が調べた限りの書式を生成する。

また Haskell tls のクライアント・コマンドで、オープンサーバと通信するには、対象サーバの HTTPS RR を引き、echパラメータを抽出するコマンドが必要である。dug に機能追加するという案も検討したが、大掛かりなプログラムなので改造するのは諦め、ech-lookup というコマンドを作成した。ech-lookup は dnsext-svcb に依存するが、dnsext-svcb は ech-config に依存している。このため、ech-lookup は、ech-config 内でビルドすることは諦め、単にリポジトリにソースを追加している状態になっている。

ECH サーバの実装

TLSに対する相互接続性の検証で、僕が一番使っているのは picotls である。これは kazuho さんが作ったライブラリで、クライアントにもサーバにもなれるコマンド cli も提供されている。ビルドが簡単であることに加えて、kazuho さん作だけに信頼性が高い。kazuho さんは ECH 仕様の著者の一人であり、当然のように picotls は ECH を実装している。

調べてみると、ECH に対して cli クライアントを利用する方法が明快だったので、Haskell tls ではサーバ側から作り始めることにした。サーバは ECH 拡張を復号する側である。

「Encrypted Client Hello の仕様」では、便宜上「クラアントに面したサーバ」と「バックエンド・サーバ」を分けて説明したが、これらは同一のサーバとして実装してもよい。Haskell tls の利用方法では、今のところ同一サーバ方式が適していると思われる。理屈の上では、同一サーバ方式では、ECH拡張を復号できたら、取り出せた内部 ClientHello を使い、復号に失敗したら外側の ClientHello を使えばよい。

復号するには、ECDHEの秘密鍵に加えて、「追加データ」として外側のClientHelloを加工する必要がある。面倒であるが時間をかけて実装すると、一番簡単なハンドシェーク・モードである full handshake で pictls と、内側の ClientHello を使って通信できるようになった。

次のモードは HRR(Hello Retry Request) であるが、この実装は困難を極めた。Haskell サーバが HRR を返すと、picotls は最初と同じ EHC 拡張を返してきた。正しいケースでは、暗号化し直した別の ECH 拡張を送ってこなければならない。picotls の ECH は、HRR に未対応なのかもと思い、boringssl を試したがまったく同じ挙動を示した。

ここで行き詰まってしまったが、IETF の TLS メーリングリストに ECH の相互接続性検証レポートが投稿されているのを発見し、著者の Stephen さんにメールを出してみた。彼が進めている DEfO プロジェクトで作成された OpenSSL フォークは HRR に完全対応していると言う。そこで、そのフォークを使ってみたら、2回目の ECH は再び暗号化しているものの、ハンドシェークで同一の鍵を共有できなかった。

最後の希望である NSS を試すと、2回目の ECH は再び暗号化していて、しかも alert を送ってきた。この alert を生成しているソースの場所を特定したことで、謎が解けた。HRRでは、サーバがECHの受理情報を2回クライアントへ返す。両者が異なる、つまり一方が受理で、他方が拒否の場合、この alert が生成されていた。

分かった、分かった。ようやく分かった。すべての事象をうまく説明できる仮説は、HRRに埋め込む一回目の受理データの計算が間違っていることだ。仕様をよく読み返すと、HRRでECHが拒否された場合、2回目のECH拡張は、1回目と同じものを使うと定義されていた。picotlsや boringssl の挙動の解釈に頭を抱えていたが、正しい振る舞いをしていたのだ。

受理データを正しく生成できなかった理由は、一連のハンドシェイク・メッセージのハッシュ値 (Transcript Hash) の計算が間違っていたからだった。これが契機となり、以前から作りたかったが手をつけてなかった、Transcript Hash のモニター機能を作成した。このおかげで、Transcript Hash に関する大胆なリファクタリングが可能となり、コードの見通しが劇的によくなった。

ECH クライアントの実装

次はクライアントである。もちろん最初は full handshake モードを実装する。当初の印象には反して、サーバよりもクライアントの方がロジックが難しかった。というのは、サーバでは内部と外部のどちらの ClientHello を使うかは、自分で決定できるので、採用しなかった方を忘れることができる。一方で、クライアントは、サーバが受理するか拒否するかは分からないので、内側のClientHello を保持しておく必要がある。

Haskell tls クライアントと pictls サーバは、早い段階で full handshake をできるようになった。

boringssl に関しては、公開サーバの存在も教えてもらったので、そちらを試したがうまくいかなかった。しかし、ローカルでビルドしたサーバとは、通信できた。これは一体どういうことだろう？ 公開サーバに使われているコードは、リポジトリから入手できるものとは違うのだろうか？

公開サーバの設定情報を ech-config で復号し表示してみると、違和感があった。たとえば、Cloudflare で公開されている設定情報は、設定が1つしか入っていないのだが、boringsslの公開サーバの設定情報には、設定が複数個含まれていた。AEAD-128-GCM よりも、ChaCha20Poly1305が優先されているのも「そう言う趣味なのかな」という感じであったが、ech-config が逆順に返していることを気づいた。このバグを直したところ、公開サーバとも通信できるようになった。

すなわち、ECHの暗号化にAEAD-128-GCMを利用すると通信できるが、ChaCha20Poly1305だと失敗するのである。hpke では ChaCha20Poly1305 に対しテストベクターでテストしているので、間違いはないように思える。また、TLS自体の暗号スイートに ChaCha20Poly1305 が選ばれても、問題なく通信できる。今のところ、boringssl には、ECH 拡張をChaCha20Poly1305 で復号するコードにバグがあるのではないかと疑っている。

DEfO OpenSSLサーバは、設定情報と秘密鍵を PEM 形式で指定する必要があるとこが苦労した。NSSサーバは、書式が複雑過ぎるので、ech-gen で生成するのは諦めた。別のモードでは、NSSサーバは、これらを自動生成し、設定情報を表示する。相互接続性の検証には、そのモードを利用した。

Cloudflareは、すでに ECH をサービスインしている。適当なドメイン名のリストに対して、HTTPS RR の ech パラメータを検索させると、2.4% が対応済みであり、クライアントに面したサーバは、すべてcloudflare-ech.com であった。これらのドメインに対して、Haskell tls クライアントは ECH でコネクションを張ることができた。

開発者によく知られた Cloudflare の実験サーバは、crypto.cloudflare.com である。しかし、このドメインは HTTPS RR を公開しておらず、サイトにも ECH の設定情報は書かれていない。頭を抱えていたが、試しに上記で得た設定情報を使ってみると、うまく通信できた。なお、cloudflare-ech.com に対して HTTPS RR を検索すると、答えが返ってくる。なんだかなぁ。

次は HRR である。これまでの大胆なリファクタリングおかげで、クライアントを HRR に対応させるのは、そんなに難しくなかった。

おわりに

相互接続性の検証に利用したクライアント・サーバの使い方は、ここにまとめてある。

メールでいろいろ教えてくれた Stephen さんに感謝します。

Encrypted Client Hello の仕様

TLS

ECH(Encrypted Client Hello) とは何か

TLS 1.3のハンドシェイクは、EncryptedExtensionsから暗号化されるが、それより前のClientHello と ServerHelloは平文のままで交換される。ClientHelloに含まれるSNI(Server Name Indication、サーバ名)は、特にプライバシ性が高い。単にこのSNIを暗号化する方法として、初期はESNI(Encrypted Server Name Indication)が提案されていた。しかし、その後ClientHello自体を暗号化するECH(Encrypted Client Hello) となった。

ECHには2つのサーバが登場する。「クライアントに面したサーバ」と「バックエンド・サーバ」だ。保護したいのはバックエンド・サーバのSNIである。前提として ECHでは、バックエンド・サーバの「設定情報」をDNSのHTTPS RRに登録する。このプライバシ性の高いSNIに対する HTTPS RRを検索すると、バックエンド・サーバの設定情報が得られる。設定情報には、「クラアントに面したサーバの公開鍵」や「クラアントに面したサーバのSNI」が入ってる。これらの検索には、DoH (DNS over HTTPS)などを利用することで、バックエンド・サーバのSNIが観察されることを防ぐ。

設定情報を得ると、ECHを利用できるようになる。まず、バックエンド・サーバのSNIを含むClientHelloを作成して暗号化する。そしてクライアントに面したサーバのSNIを含む別のClientHelloを作成し、その中にECH拡張として暗号文を挿入する。

たとえば、バックエンドのSNIが private.example.jp で、クライアントに面したサーバのSNIが public.example.jpの場合、内側のClientHelloに private.example.jpが、外側のClientHelloにpublic.example.jpが入る。ClientHello全体を暗号化するため、将来定義されるさまざまな拡張を必要に応じて暗号化できる。柔軟な設計であるが、それ故に、仕様は目眩がするほど大きい。

僕は1月の終わりに実装を開始して、リリースできたのは3月の半ばであった。ようやく時間ができたので、仕様の解説と実装の体験記を記そうと思う。

HPKE

内側のClientHelloの暗号化には、RFC 9180で定められているHPKE(Hybrid Public Key Encryption)を使う。TLSが「通信の暗号化」であるのに対して、HPKEは「オブジェクトの暗号化」である。ClientHello自体は、オブジェクトだからね。

オブジェクトの暗号化と言えば、PGPやS/MIMEが有名だ。「乱数的に生成した鍵」と共通鍵暗号でオブジェクトを暗号化し、鍵を公開鍵暗号で暗号化する。大雑把に言えば、HPKEはこの方式をモダンにしたものであると言える。しかし細かい点は異なる：

  • 以前は鍵を共有するためにRSAが主に使われていたが、現在の鍵交換の主役といえば ECDHEである。HPKEでも、ECDHEが使われる。
  • 共有した鍵は、「標準化された鍵派生関数」(KDF)により加工される
  • OpenPGPが標準された時代とは違って、共通鍵暗号に許されるのはAEADモードのみである

TLSとHPKEを比較すると、以下のような点が決定的に違う：

  • TLSには前方秘匿性がある。HPKEでも ECDHEが使われているので、前方秘匿性を期待したくなるが、前方秘匿性はない。なぜなら、クラアントに面したサーバが公開する公開鍵は静的だからだ。
  • TLSでは初手のClientHelloを暗号化できない。暗号化を始められるのはサーバ側である。一方で、HPKEではクライアントが初手から暗号化を使える。(ClientHelloを暗号化するのが目的だからね。)

HPKEは、前方秘匿性を諦める代わりに、初手からの暗号化という機能を手に入れているとも言える。

HPKEでは、APIが定義されている。以下に暗号化関数Sealの例を示す。

def Seal<MODE>(pkR, info, aad, pt, ...):
  enc, ctx = Setup<MODE>S(pkR, info, ...)
  ct = ctx.Seal(aad, pt)
  return enc, ct

大雑把に言うと、「受信者の公開鍵」(pkR)と「文字列」(info)でAEADを初期化し、「追加データ」(aad)と「平文」(pt)をAEADに入力して、「暗号文」(ct)を得る。encは、送信者の公開鍵である。

ECHクライアント

クライアントは、ECH拡張を含む ClientHello を以下のように作成する。

  • バックエンド・サーバの設定情報から、クライアントに面したサーバのSNIや公開鍵を得る
  • バックエンドサーバのSNIを含んだ内側のClientHelloを作成する。(このClientHelloがバックエンドサーバに平文で届けば、TLSコネクションが張れる。)
  • クライアント向けサーバのSNIを含んだ外側のClientHelloを作成する。
  • 内側と外側の ClientHello の拡張リストを走査しながら、必要であれば参照を使って、内側の拡張リストを圧縮する (※1)
  • 内側の ClientHello の大きさから、暗号文の大きさを予想し、外側の ClientHelloに「本体を0で埋めた ECH 拡張」を挿入する (※2)
  • ※2を追加データとして、※1の平文を暗号化する (※3)
  • ※3の0 で埋めらた部分を暗号文で置き換える

外側のClientHelloを追加データとして使うのは、外側のClientHelloに対する改ざんを検知するためである。

一般的に、暗号が絡んだプログラミングでは、すべてが正しくなければ、まったく正常に動作しない。ECHの場合、追加データの作成も難しく、実装をより困難にしている。

ECHサーバ

クライアントに面したサーバが、ECH拡張を含んだClientHelloを受け取ると、上記の逆の操作を施して、内側のClientHelloの復元を試みる。

復元に失敗した場合、外側の ClientHello を使って、クライアントと TLS のハンドシェイクを実行する。後述の検知方法により、クライアントはバックエンドサーバとハンドシェイクしてないことが分かるので、ハンドシェイクが終わった時点で、alert を送ってコネクションを終了させる。

復元できた場合、クライアントに面したサーバは、平文の ClientHello をバックエンドサーバに送る。この後、クライアントに面したサーバは、単なるリレー役となる。内側の ClientHello を受け取ったバックエンドサーバは、クライアントとハンドシェイクを開始する。

バックエンドサーバは、内側の ClientHello を受け取ったことを示すために、8バイトの特殊な値を生成し、ServerHello の Server Random に埋め込む。この値の生成には、ClientHello ＋該当8バイトを0で埋めた ServerHello のハッシュ値が使われるので、これまたややこしい。

さらに HelloRetryRequest のケースでは、最初の ClientHello はハッシュ値のハッシュ値になるというルールがあるので、正しい値を導くのは大変である。

以上は、あくまでECHの概要である。実際の仕様には、ここで説明した以外にも面倒な部分があり、実装の進捗具合は亀の歩みよりも遅い。

TLS レコード・サイズ制限拡張

TLS

tlsfuzzer

僕が tlsfuzzer を知ったのは、知人からのメールがきっかけだった。tlsfuzzerは、fuzzer という名前には反して、対象であるTLSの中身を高度に理解して実装されている強力なテストツールである。各テスト項目が、それぞれのPythonスクリプトとして提供されいる。インストールは簡単で、Python初心者の僕でも気軽に利用できた。

彼女は、Haskell tls ライブラリが、テストの1つに失敗することを指摘してくれた。TLS 1.3では Finished は暗号化されているが、平文の Finished を送っても、ハンドシェイクが受理されるというバグが存在したのだ。

issueを登録するようにお願いしたにも関わらず、忙しくて放置してしまった。約2年後、心にひっかかっていたバグをようやく修正して、ついでに tlsfuzzer が提供する他のテストも試し始めた。

tlsfuzzerのテストを通すには、Pythonスクリプトに適切な引数を渡さなければならない場合がある。この作業では、その引数を記録することを怠ったため、テストの成功を再現するのが困難になってしまった。他のプロジェクトが忙しくなったこともあり、tlsfuzzerによるテストをこの時もまた放置してしまった。

時は経ち Haskell tlsライブラリの保守を単独で引き継いだ僕は、ライブラリを自由に修正できるようになった。そこで、IETFにより「廃止」された SSL 3、TLS 1.0、TLS 1.1、そしてストリーム暗号やCBCモードのブロック暗号のコードを削除した。後方互換性を意図的に破壊することで、ビルドで失敗するようになった Haskeller に「モダンで安全なTLSに移行しましょう」というメッセージを送ったのだ。ただし、凝った設定をしていなければビルドは成功するので、自動的に安全性が高まる。

昨年の12月に余裕ができたので、tlsfuzzerへ再び取り組んでみることにした。tlsfuzzer のスクリプトの多くは、脆弱な暗号方式や非推奨のパラメータを要求しており、以前通ったはずのテストも通らなくなっていた。そこで、専用ブランチを作って、それらを復活させた。

前回の反省を活かし、通ったテストに関してはコマンド引数をシェルスリプトとして保存し、回帰(regression)テストとして利用できるようにした。このシェルスリプトは強力な武器となり、これ以降、何度救われたか分からない。Haskell内のテストでは、クライアントとサーバが同じロジックを共有しているので、お互いが同じように間違って、テストが成功してしまう可能性がある。この回帰テストのおかげで、大胆な変更に対しても自信を持てるようになった。

レコード・サイズ制限拡張

tlsfuzzerには、Haskell tls がまだ実装していない署名圧縮拡張やレコード・サイズ制限拡張を対象としているスクリプトもあった。モチベーションが高まったので、これらを実装してみた。人が書いたテストを活用できるのは、本当にありがたい。

署名圧縮拡張に関しては特に書くことはないが、レコード・サイズ制限拡張の仕様は少し複雑なので、理解している内に記録に残しておこうと思う。

基本的なレコード・サイズとは：

  • TLS 1.2において、平文の最大レコード・サイズは214(16,384)である。暗号文の場合は、暗号文のオーバーヘッドに従って、これより大きなサイズを格納してよい。
  • TLS 1.3においても、平文の最大レコード・サイズは214(16,384)である。暗号文のオーバヘッドには、暗号自体に加えて、平文に加えられるContent-Typeやパディングもある。Content-Typeのサイズは1で、パディング長は0でもよい。

レコード・サイズ制限拡張で提案するレコード・サイズとは：

  • 基本的な利用方法は、レコード・サイズの上限を引き下げることである。
  • TLS 1.2 に対し提案するレコード・サイズは、平文の大きさの上限である。
  • TLS 1.3 に対し提案するレコード・サイズは、平文の大きさの上限 - 1 である。これは、Content-Typeも含むと定義されているからである。
  • クライアントが TLS 1.2 と TLS 1.3 の両方を提案する場合、サーバがどちらを選ぶかはあらかじめ分からない。TLS 1.3 が選ばれた場合、値が -1 されることに注意しないといけない。(ここがダサい。)

合意形成：

  • レコード・サイズ制限拡張に対応したクライアントは、ClientHelloに拡張を入れて送る。
  • レコード・サイズ制限拡張に対応したサーバは、クライアントからレコード・サイズ制限拡張が送られてきた場合に限り、レコード・サイズ制限拡張を返す。
  • 双方がレコード・サイズ制限拡張を送った場合に限り、レコード・サイズ制限拡張で指定されている上限が有効になる。
  • 両者が送るレコード・サイズは異なってよい。クライアントが送った上限は、サーバがレコードを送信する際に利用される。逆もまた然り。

提案するレコード・サイズの最小値：

  • 提案してよいレコード・サイズの最小値は64である。これより小さい値を受け取った場合は、alert を返す。

提案するレコード・サイズの最大値：

  • 提案してよいレコード・サイズの最大値は、他の拡張で許されない限り、プロトコルで定義されている最大値である。つまり、TLS 1.2 では 214、TLS 1.3 では 214 + 1 である。TLS 1.2も提案する場合、実質的に 214が最大値となる。(以下で説明するように 214 + 1 を提案する裏技もある。)
  • サーバが、プロトコルで定義されている上限よりも大きな値を受け取った場合、受理するが、送信時にはプロトコルで定義されている上限を利用する。alert を返してはならない。なぜなら、クライアントが未知の拡張を使って上限が引き上げようとしているかもしれないからである。(ここがすごい)

当初、僕の仕様に対する理解が不完全であったが、tlsfuzzerがエラーを発して間違った理解を指摘してくれた。感謝！

Channel Bindings 備忘録

TLS

RFC 5056 や RFC 9266で定められている TLS Channel Bindings の備忘録。

Channel bindings とは何か

Channel bindingsは、本質的に TLS の Finished の値である。Finishedは、一連のハンドシェイク・メッセージに対するハッシュ値である。この値は、TLSセッションの名前(ID)だと考え得る。

目的

Channel bindingsの目的は、MITM(Man in the Middle)攻撃を検知すること。

クライアントとサーバは、事前にユーザのパスワードを加工した形で共有する。Channel bindingsに対応したパスワード認証 SCRAM(Salted Challenge Response Authentication Mechanism)では、パスワードによるユーザ認証に加えて、channel bindingsを使って同じTLSセッションを使っているか確認できる。

同じTLSセッションを使っていれば、中間の攻撃者は存在しない。異なるTLSセッションを使っていれば、中間の攻撃者が存在することになる。

前提

中間の攻撃者が、TLSのサーバ認証をかいくぐる方法を持っているとする。中間の攻撃者は、クライアントを偽のサーバに対してTLSセッションを張るように誘導する。クライアントのTLSセッションが確立されたら、本物のサーバに対して別のTLSセッションを張る。

この状態では、中間の攻撃者は、暗号文を平文に戻せる。平文をそのまま再暗号化してリレーしたり、改竄してから暗号化し送信できる。

動作原理

MITM攻撃を検知するために、アプリケーションでSCRAMを使って、ユーザとTLSコネクションを認証する。

認証のやりとりに対する改竄は検知できる。なぜなら、認証のやり取り全体は、事前に共有した鍵(パスワード)を使った形でチェックサムが取られる。中間の攻撃者は、事前共有した鍵を知らないので、チェックサムが作れない。

リレーも検知できる。サーバが使うTLSセッション名とクライアントが使うTLSセッション名は異なる。ClientHelloには乱数が入っていることを思い出そう。クライアントから見ると、TLSの確立時に偽サーバとのTLSセッション名を得ている。リレーされた認証データには、本物のサーバが利用しているTLSセッション名が入っており、(改竄されようがされまいが)不一致が分かる。

Myth and truth in Haskell asynchronous exceptions

Haskell

This article explains my best current practice on asynchronous exceptions in Haskell using the standard library - Control.Exception. Other libraries for safe exceptions are out of scope. The followings are the definitions of two kinds of exceptions.

  • Synchronous exceptions are ones raised by your actions. You can throw a synchronous exception to yourself via throwIO.
  • Asynchronous exception are ones thrown by other threads. You can re-throw them to yourself via throwIO when you catch them.

Before talking about asynchronous exceptions, let's start with synchronous exceptions.

Synchronous exceptions

You can catch synchronous exceptions by catch, handle and try:

catch :: Exception e => IO a -> (e -> IO a) -> IO a
handle :: Exception e => (e -> IO a) -> IO a -> IO a
try :: Exception e => IO a -> IO (Either e a)

As you can see from this signature, the handler can take only one type. Here is an example:

import Control.Exception
import GHC.IO.Exception
import System.IO.Error

handled_action :: IO ()
handled_action = your_action `catch` handler
  where
    handler :: IOException -> IO ()
    handler e
        -- Bad file descriptor
        | ioeGetErrorType e == InvalidArgument = return ()
        -- Connection refused
        | ioeGetErrorType e == NoSuchThing = return ()
        -- Print it for debugging
        | otherwise = print e

You can define your own exception as follows:

import Control.Exception

data EarlyReturn = EarlyReturn deriving (Eq, Show)
instance Exception EarlyReturn

The important methods of the Exception class are as follows:

class (Typeable e, Show e) => Exception e where
    toException   :: e -> SomeException
    fromException :: SomeException -> Maybe e

instance Exception EarlyReturn derives the methods properly.

The following code implements early return like other languages:

import Control.Monad (when)

early_return :: IO ()
early_return = handle ignore $ do
    when condition1 $ throwIO EarlyReturn
    when concition2 $ throwIO EarlyReturn

    action1
    action2
    action3
    ...
  where
    ignore EarlyReturn = return ()

If you want to catch two or more types, you can use catches:

catches :: IO a -> [Handler a] -> IO a

In my opinion, catches is a little bit hard to use. Rather, I usually use PatternGuard. The following example defines the Break exception as well as EarlyReturn:

{-# LANGUAGE PatternGuards #-}

data Break = Break deriving (Eq, Show)
instance Exception Break

handled_action2 :: IO ()
handled_action2 = your_action `catch` handler
  where
    handler :: SomeException -> IO ()
    handler se
        | Just Break <- fromException se = return ()
        | Just EarlyReturn <- fromException se = return ()
        -- Print it for debugging
        | otherwise = print se

The super data type, SomeException is defined as follows:

{-# LANGUAGE ExistentialQuantification #-}

data SomeException = forall e . Exception e => SomeException e

The constructor SomeException is a kind of container which can contain several types and provides a single type, SomeException. The following example converts IOError and ErrorCall to SomeException:

ghci> import Control.Exception

ghci> :type userError "foo"
userError "foo" :: IOError
ghci> :type SomeException (userError "foo")
SomeException (userError "foo") :: SomeException

ghci> :type ErrorCall "bar"
ErrorCall "bar" :: ErrorCall
ghci> :type SomeException (ErrorCall "bar")
SomeException (ErrorCall "bar") :: SomeException

fromException returns Just if SomeException contains an expected exception type. Otherwise, it returns Nothing:

ghci> let se = SomeException $ ErrorCall "bar"
ghci> fromException se :: Maybe ErrorCall
Just bar
ghci> fromException se :: Maybe IOError 
Nothing

A downside of SomeException is that asynchronous exceptions are caught as well as synchronous exceptions. This could introduce nasty bugs. We will resolve this issue according to rule 3 later.

Asynchronous exceptions

If your code acquires a resource, it must be released after your job. The following is an example of unsafe code to obtain a resource:

unsafe_action_with_resource = do
   x <- acquire_resource
   use x
   release_resource x

If use receives an asynchronous exception, x is not released, thus leaked. To prevent this resource leak, you should use bracket:

bracket :: IO a -> (a -> IO b) -> (a -> IO c) -> IO c

The example can be convert into asynchronous-exception-safe code with bracket:

safe_action_with_resource = bracket acquire_resource release_resource use

Some people (including me) misunderstand/misunderstood that asynchronous exceptions are not delivered into the resource release clause. But this is not quit right.

Consider the following situation:

  • You run a program in Haskell in a terminal
  • Your program is blocked in the resource release clause of bracket.
  • You type Control-C to stop the program on the terminal.

Control-C is an asynchronous exception (in particular UserInterrupt :: AsyncException). If this asynchronous exception is not delivered to the resource release clause, you cannot stop your program.

But Control.Exception is well-defined. Blocking actions such as takeMVar is interruptible by asynchronous exceptions. In other words, non blocking code cannot be interrupted by asynchronous exceptions in the clause. As you will see later, timeout is defined with an asynchronous exception. You can use even timeout in the resource release clause. This is a crucial point to implement graceful-closing of network connections as it is used in the resource release clause typically.

As you understood, the semantics of Control.Exception is clear and well-defined. That's why this article is stick to it.

As described above, if you catch asynchronous exceptions which others define via SomeException, nasty bugs happens. For instance, the async package uses an asynchronous exception, AsyncCanceled. If you run two threads which ignore AsyncCanceled via concurrently, these threads would be leaked.

So, you should obey the following three rules:

Rule 1

If you define an asynchronous exception, you must explicitly define the methods of the Exception class:

import Control.Exception

data Timeout = Timeout deriving (Eq, Show)

instance Exception Timeout where
    toException = asyncExceptionToException
    fromException = asyncExceptionFromException

If we follow this rule, asynchronous exceptions can be distinguished from synchronous exceptions with the following function:

isAsyncException :: Exception e => e -> Bool
isAsyncException e =
    case fromException (toException e) of
        Just (SomeAsyncException _) -> True
        Nothing -> False

Rule2: catch the asynchronous exception which you are using

If you don't catch, the exceptions are leaked from your threads. GHC RTS catches them and displays them to stdout.

The following is an example to define naive timeout:

import Control.Concurrent
import Control.Exception

data Timeout = Timeout deriving (Eq, Show)

instance Exception Timeout where
    toException = asyncExceptionToException
    fromException = asyncExceptionFromException

timeout :: Int -> IO a -> IO (Maybe a)
timeout t action = do
    pid <- myThreadId
    handle handler $ bracket (spawn pid) kill $ \_ -> Just <$> action
  where
    spawn pid = forkIO $ do
        threadDelay t
        throwTo pid Timeout
    kill tid = throwTo tid ThreadKilled
    handler Timeout = return Nothing

In this example, an asynchronous exception, ThreadKilled, is defined and caught by handler.

Rule 3: don't eat up asynchronous exceptions of others

Exceptions of others have their own semantics. If you eat up them, your code does not work well.

If you use SomeException for catch, handle or try, check if the caught exception is asynchronous. And re-throw it via throwIO if asynchronous. You can use the following pattern for this purpose:

{-# LANGUAGE PatternGuards #-}

handled_action3 :: IO ()
handled_action3 = your_action `catch` handler
  where
    handler :: SomeException -> IO ()
    handler se
        | isAsyncException se = throwIO se -- HERE HERE HERE
        | Just Break <- fromException se = return ()
        | Just EarlyReturn <- fromException se = return ()
        -- Print it for debugging
        | otherwise = print se

Event-poll programming

Recently, Kei Hibino, my colleage, spoke eloquently to me about the dangers of asynchronous exceptions. Asynchronous exceptions are thrown to us even when we are not expected them. Rather, he suggested event-poll programming.

Let's consider the recv function of the network library with timeout. This is an essential part of the graceful-closing function (read Implementing graceful-close in Haskell network library in detail):

import Data.ByteString
import Network.Socket
import Network.Socket.ByteString
import System.Timeout

timeoutRecv :: Socket -> Int -> IO (Maybe ByteString)
timeoutRecv sock usec = timeout usec $ recv sock 1024

As I explained, timeout uses an asynchronous exception. How can we implement this function without asynchronous exceptions?

The idea is as follows:

  • Prepare one STM action and ask the system TimerManager to wake up me via the action on timeout.
  • Prepare another STM action and ask the system IOManager to wake up me via the action when the socket is ready for read.
  • Race two managers and check if which one is a winner via the composition of these STM actions. If TimerManager wins, return Nothing from IO. Otherwise, the winner is IOManager. This means that data is available for the socket. So, call recv.

The following code implements this idea. I don't explain this code in detail but please read carefully if you are interested.

import Control.Concurrent.STM (
    atomically,
    newEmptyTMVarIO,
    orElse,
    putTMVar,
    takeTMVar,
 )
import Control.Exception (bracket)
import Data.ByteString (ByteString)
import GHC.Event (getSystemTimerManager, registerTimeout, unregisterTimeout)
import Network.Socket (Socket, waitAndCancelReadSocketSTM)
import Network.Socket.ByteString (recv)

data Wait = MoreData | TimeoutTripped

recvEOFevent :: Socket -> Int -> IO (Maybe ByteString)
recvEOFevent sock usec = do
    tmmgr <- getSystemTimerManager
    tmvar <- newEmptyTMVarIO
    bracket (setupTimeout tmmgr tmvar) (cancelTimeout tmmgr) $ \_ -> do
        bracket (setupRead sock) cancelRead $ \(rxWait', _) -> do
            let toWait = do
                    takeTMVar tmvar
                    return TimeoutTripped
                rxWait = do
                    rxWait'
                    return MoreData
            waitRes <- atomically (toWait `orElse` rxWait)
            case waitRes of
                TimeoutTripped -> return Nothing
                MoreData -> Just <$> recv sock 1024
  where
    setupTimeout tmmgr tmvar =
        registerTimeout tmmgr usec $ atomically $ putTMVar tmvar ()
    cancelTimeout = unregisterTimeout
    setupRead = waitAndCancelReadSocketSTM
    cancelRead (_, cancel) = cancel

I'm trying to get rid of asynchronous exceptions as much as possible from my network libraries by introducing the event-poll programming.

Labeling threads in Haskell

Haskell

GHC 9.6 provides a function to list up the current threads finally. The function is listThreads exported from the GHC.Conc.Sync module. listThreads is a killer debug method for thread leaks.

If you have Haskell programs which run for a long time, it's quite nice to provide feature to monitor threads with the following functions:

import Data.List (sort)
import Data.Maybe (fromMaybe)
import GHC.Conc.Sync (ThreadStatus, listThreads, threadLabel, threadStatus)

printThreads :: IO ()
printThreads = threadSummary >>= mapM_ (putStrLn . showT)
  where
    showT (i, l, s) = i ++ " " ++ l ++ ": " ++ show s

threadSummary :: IO [(String, String, ThreadStatus)]
threadSummary = (sort <$> listThreads) >>= mapM summary
  where
    summary t = do
        let idstr = drop 9 $ show t
        l <- fromMaybe "(no name)" <$> threadLabel t
        s <- threadStatus t
        return (idstr, l, s)

The following is an example of how printThreads displays a list of thread status:

1 (no name): ThreadFinished
2 IOManager on cap 0: ThreadRunning
3 TimerManager: ThreadBlocked BlockedOnForeignCall
4 main: ThreadRunning
5 accepting: ThreadBlocked BlockedOnMVar
6 server:recv: ThreadBlocked BlockedOnForeignCall
7 server:gracefulClose: ThreadRunning

Let's label threads

Threads spawned via forkIO or others do not have its label by default. Threads without label displayed "(no name)" in the example above. If there are a lot of threads without label, debugging is hard. So, I have already asked GHC developers to label threads created in the libraries shipped with GHC.

I would also like to ask all library maintainers to label threads if forked. You can use the following code to label your threads:

import Control.Concurrent (myThreadId)
import GHC.Conc.Sync (labelThread)

labelMe :: String -> IO ()
labelMe lbl = do
    tid <- myThreadId
    labelThread tid lbl

labelThread is a very old function. So, you can use it without worrying about GHC versions.

labelThread override the current label if exists. If you don't want to override it, use the following function:

{-# LANGUAGE CPP #-}

import Control.Concurrent (myThreadId)
import GHC.Conc.Sync (labelThread, threadLabel)

labelMe :: String -> IO ()
#if MIN_VERSION_base(4,18,0)
labelMe name = do
    tid <- myThreadId
    mlabel <- threadLabel tid
    case mlabel of
        Nothing -> labelThread tid name
        Just _ -> return ()
#else
labelMe name = do
    tid <- myThreadId
    labelThread tid name
#endif

Unfortunately, the first appear of threadLabel is GHC 9.6. So, #if is necessary.

ThreadFinished

Threads in the ThreadFinished status should be GCed quickly. If you see a long-lived threads in this status, their ThreadIds are held somewhere. Surprisingly, ThreadId is not integer but reference! The following is an example that a WAI timeout manger holds ThreadIds, resulting in thread leaks.

10150 WAI timeout manager (Reaper): ThreadBlocked BlockedOnMVar
10190 Warp HTTP/1.1 192.0.2.1:43390: ThreadFinished
10191 Warp HTTP/1.1 192.0.2.1:43392: ThreadFinished
10193 Warp HTTP/1.1 192.0.2.1:43404: ThreadFinished
10202 Warp HTTP/1.1 192.0.2.1:43406: ThreadFinished
10204 Warp HTTP/1.1 192.0.2.1:41256: ThreadFinished

To prevent this thread leaks, hold Weak ThreadId instead. This can be created via mkWeakThreadId provided by Control.Concurrent. To convert Weak ThreadId to ThreadId, use deDefWeak exported from GHC.Weak.

More labels

The ThreadBlocked constructor of the ThreadStatus type contains BlockReason. It has the following constructors:

  • BlockedOnMVar
  • BlockedOnBlackHole
  • BlockedOnException
  • BlockedOnSTM
  • BlockedOnForeignCall
  • BlockedOnOther

It's nice if we can label MVar via labelMVar and BlockedOnMVar contains its label. STM data types should follow this way, too.