QUICをゆっくり解説(16):ヘッダ圧縮

2021年11月17日 水曜日


【この記事を書いた人】
山本 和彦

Haskellコミュニティでは、ネットワーク関連を担当。 4児の父であり、家庭では子供たちと、ジョギング、サッカー、スキー、釣り、クワガタ採集をして過ごす。

「QUICをゆっくり解説(16):ヘッダ圧縮」のイメージ

前回説明したように、HTTP/2用とHTTP/3用のヘッダ圧縮は、それぞれHPACK、QPACKと呼ばれています。HPACKはヘッダ圧縮の基礎を築き、QPACKはHPACKのHoLブロッキングの問題を緩和しました。今回は、HPACKとQPACKについて説明します。

HPACK

ヘッダ全体を通常のテキスト圧縮を使って圧縮すると、CRIMEという攻撃手法の餌食となり、TLSなどで暗号化していてもCookieの値などを攻撃者に盗まれる可能性があります。

たとえば、攻撃者は犠牲者と同じFree Wi-Fiを使っており、パケットの大きさを観察できるとしましょう。そして、犠牲者を悪意のあるサイトに誘導し、要求ヘッダに任意のフィールドを挿入するスクリプトをダウンロードさせたとします。

挿入したフィールドの値が、Cookieの値に使われている文字列に部分的に一致すれば、圧縮率が上がります。パケットを観察して、サイズが小さくなっていれば、Cookieの一部を知り得たことになります。これを繰り返し、Cookieの値全体を盗み出します。

HPACKでは、CRIMEに対抗するため、複数のフィールドを対象とした圧縮ではなく、フィールドごとに圧縮する方法を採用しています。HPACKの圧縮方法の要は、以下の2点です。

  • フィールド名や値が登録された表を共有し、各エントリを「何番目かという数値」(インデックス)で表現して相手に指示する。
  • フィールド名や値を表に挿入するように相手に伝えるときに、文字列をHuffman符号を使って圧縮する。

表は2つあります。変化しない「静的表」と変化する「動的表」です。静的な表の一部を以下に抜粋します。

インデックス フィールド名 フィールド値
1 :authority
2 :method GET
3 :method POST
4 :path /

たとえば、メソッドの値がGETという擬似フィールドを表現するには、2というインデックスを指示すればよいわけです。フィールドの表現として存在するのは以下の3つです。

  1. 1つのインデックスでフィールド名とフィールド値の両方を指示する
  2. インデックスでフィールド名を指示し、フィールド値は文字列で指示する
  3. フィールド名とフィールド値の両方とも文字列で指示する

2)と3)の文字列の部分では、Huffman符号を使って圧縮するか否かを選べます。また、2)と3)には、それぞれ以下3つの版があります。

  • 動的表に登録する
  • 動的表に登録しない
  • 動的表に登録しない。加えてセキュリティのため、中継装置で伸長後、再圧縮される場合も、常に文字列による指示を使用する制約を付ける

動的表には大きさの制限があり、エントリでいっぱいになると、古いエントリが削除されていきます。動的表にはデフォルトの大きさがありますが、復号側が SETTINGS_HEADER_TABLE_SIZE というパラメータを使って圧縮側へ指示することもできます。

QPACK

HPACKでは、圧縮表現が順番に届くという仮定がありました。HTTP/3で望まれるのは、圧縮表現が順番を守らずに届いても伸長できる圧縮方式です。並行化されたHPACKが必要だと言ってもよいでしょう。

HPACKを並行化する際の問題をスレッドプログラミングで考えてみましょう。以下の図は、サーバ側でのスレッドの構成を表しています。長方形がスレッドで、矢印はデータの流れです。

1つのソケットに対して、複数のスレッドが読んだり、複数のスレッドが書いたりすると問題が生じることが知られています。そこで、常套手段としては、ソケットを読むスレッドとソケットに書くスレッドを1つずつ用意します。図の中では、前者が Reader、後者が Senderと呼ばれています。クライアントからの要求を処理して応答を作るのが、Workerです。Workerは、1つの(双方向)ストリームを担当します。Readerは、クライアントからの要求をWorkerに振り分けます。

HPACKの伸長は、読み込む順番が大切ですのでReaderで実行されます。これを並行化するには、伸長の実行をWorkerに移せばよいでしょう。しかし、HPACKを単純に並行化すると、複数のWorkerが順番を守って動的表を操作することになります。可変領域を複数のスレッドが操作する点、そしてスレッド間に数珠つなぎの依存関係が発生する点を考えると、設計としてよくないと言えるでしょう。

この問題は、HPACKの「圧縮表現」に「動的表の制御」も含まれていることから発生しています。そこで、QPACKでは「圧縮表現」と「動的表の制御」を分離しました。圧縮表現はHPACKと同等ですが、それらは動的表を変化させません。動的表の制御は、専用のコマンドを使い、伸長側から挿入の確認が返ってくるようになっています。これらは、一方向のストリームを2つ使ってやり取りします。(圧縮表現は、これまでどおり双方向のストリームで運搬されます。) このアイディアで、以下の2つが実現できます。

  • あるエントリの挿入に対して確認が返れば、そのエントリへのインデックスは伸長側にも必ず存在します
  • 依存関係は数珠つなぎにはならず、各ストリームの圧縮表現が依存するのは、制御のストリームのみです

必ず確認を待つよう設計してもよいのですが、それだと圧縮率が犠牲になります。HTTP/3では、要求を一度にたくさん出せます。しかし、その時点では確認が返ってきてないので、圧縮効率の悪い文字列を使わなければならないからです。

そこで、QPACKは確認を待たなくても動的表へのインデックスを利用できるように設計されています。

  • ヘッダの圧縮表現には、必要となる「動的表の最低限のエントリ番号」が付加されます。伸長側で、動的表がこの条件を満たさない場合は、そのヘッダの圧縮表現はブロックされます
  • 伸長側は SETTINGS_QPACK_BLOCKED_STREAMS というパラメータを使って、ブロックされてもよいヘッダの数を圧縮側へ指示できます(初期値は0)

挿入の確認を待たずに動的表へのインデックスを使えばブロックされ得るヘッダの数は増え、確認が届けば減ります。圧縮側はこの制限に達した場合は、以下の動作を選択します。

  • 動的表を使わない圧縮表現にして送信を続ける
  • 制限が解除されるまで待つ

HPACKと同様、動的表には大きさの制約があるので、古いエントリは削除しないといけません。HPACKと違い、QPACKでは参照がなくなったことを保証しなければならず、エントリの削除は手強い問題です。なお、QPACKで動的表の大きさを制御するのは、SETTINGS_QPACK_MAX_TABLE_CAPACITY です。動的表のデフォルトの大きさは0なので、動的表を使う場合、伸長側はまずこのパラメータを圧縮側へ指示する必要があります。

おわりに

QPACKの伸長側は、圧縮側の指示どおりに動作するだけなので、実装はそれほど難しくはありません。一方で、圧縮側は圧縮方法の戦略に幅があり、考慮すべきことが多いと言えます。私の現時点の実装では、圧縮側は動的表を全く利用していません。この記事を書いたことをきっかけに、実装に挑戦してみようかと思います。

これまでの16回の連載で、QUICに関しては全体を網羅できたと思います。この記事をもちまして、「QUICをゆっくり解説」は一区切りとします。今後は、気が向いたときに落ち穂拾いのような内容をお届けできればよいなと考えています。

最後に、3歳になった娘の寝付きは、全然よくなっていないことを申し添えておきます。

山本 和彦

2021年11月17日 水曜日

Haskellコミュニティでは、ネットワーク関連を担当。 4児の父であり、家庭では子供たちと、ジョギング、サッカー、スキー、釣り、クワガタ採集をして過ごす。

Related
関連記事