「ZMap: Fast Internet-Wide Scanning and its Security Applications」(PDF) という USENIX Security Symposium (2013) で発表された論文を読んだので、そのメモ書きです。

免責 内容が間違っていたり、偏っていたりする可能性があります。正確な情報が欲しい方は必ず論文を読んでください。誤りの指摘や補足、議論などは GitHub Issue へお願いします。

読んだ動機

先日参加したシステム系輪講会で ZMap というスキャンツールを使ったインターネットの調査研究がよく行われているという話を聞きました。曰く、ZMap を使うとパブリックな IPv4 アドレス空間を数十分でスキャンできるとのこと。その仕組みが気になってこの論文を読んでみました。

まとめ・雑感

  • 実装を工夫することで、拡張性があり高速なネットワークスキャナーを実現した。
    • probe パケットの送信部と受信部を別のスレッドで並列動作させている。
    • 状態をなるべく持たないようにし、状態共有にかかるコストを抑えている。
    • probe パケットをイーサネットレイヤーから送ることでカーネル空間でのオーバヘッドを削減している。
    • 送信先アドレスの選択アルゴリズムを工夫することで、送信先ネットワークが過負荷にならないようにしている。これにより送信レートを制限せずに probe パケットを送れる。
  • Nmap が汎用的なネットワークスキャナーを目指しているのに対し、ZMap はパブリックな IPv4 アドレス空間の全ホストに対してパケットを一つだけ送ることに特化している。
  • 実装上の工夫点については詳細な記述がなく、個別の評価も行われていないため、どれが一番性能に寄与しているのかがよく分からなかった。
  • ZMap を用いた様々な調査を長期間に渡って行っており、それをもとに ZMap の全体性能や有用性を丁寧に論じていて、興味深い内容だった。

読んだメモ

注：翻訳ではないです。

1. Introduction and Roadmap

インターネット規模のネットワークスキャンはボットネットやワームといった悪意のある行為と関連付けられがちだが、セキュリティリサーチにとっても重要なツールである。ネットワークをスキャンするメジャーなツールに Nmap がある。Nmap では IPv4 アドレス空間を探索するのに数週間もしくは多くのマシンを必要とする。

本論文では、インターネット規模のネットワークスキャンに特化した高速なネットワークスキャナー ZMap を提案している。ZMap は一台のミッドレンジのマシンを使って、特別なハードウェアやカーネルモジュールなどを使わずに、パブリックな IPv4 アドレス空間を 45 分以下でスキャンすることができる。これはギガビットイーサネットの速度の理論値の 97% を超えている。最もアグレッシブなデフォルト設定を用いた Nmap と比較して、ZMap はパブリック IPv4 アドレス空間を 1300 倍以上高速にスキャンすることができた。

また ZMap はモジュラリティのあるアーキテクチャを採用しており、様々なタイプのシングルパケット probe (TCP SYN スキャン、ICMP echo request スキャン、アプリ特有の UDP スキャン、など) を送信可能で、かつ発見したホストに対してフォローアップアクションを行えるフックポイントを提供している。ZMap はオープンソースで公開されている (https://zmap.io/)。

Optimized probing : Nmap が送信元もしくは送信先ネットワークのトラフィックを飽和させるのを防ぐために送信レートを制限しているのに対し、ZMap は送信元ネットワークが十分な容量を持っていると仮定し、かつ送信先のネットワークをランダムな順番で選択することで、ネットワークトラフィックの飽和を回避している。これにより送信元の NIC がサポートしている速度で probe を送ることができる。また、イーサネットフレームを直接生成することで高速化を実現しており、ZMap はギガビットイーサネットのスピードで probe を送信できる。

No per-connection state : Nmap がタイムアウト処理や再送処理のためにスキャン中のホストを保持しておくのに対し、ZMap はコネクション毎の状態を持たないようになっている。また、ZMap では送信先ホストの選択方法を工夫することで、送信済みホストを保持しておかなくてももれなくパケットを送ることができる。

No retransmission : Nmap はタイムアウトやパケットロスを検知すると適応的にパケットを再送するのに対し、ZMap は状態を持つのを避けるために常に決まった数のパケット (デフォルトでは一つだけ) を送信し、再送処理は行わない。シングルパケットだと一時的なパケットロスなどによってカバレッジが下がる恐れがあるが、著者らの推計によるとシングルパケットでも 98% のカバレッジを達成でき、この程度のロスであれば典型的なリサーチアプリケーションでは問題にならないとのこと。

高速なスキャナーはセキュリティ研究者にとって有用なツールとなるが、ネットワークをオーバーロードさせたりネットワーク管理者の仕事を増やすようなことには気をつけなければならない。

2. ZMap: The Scanner

本章では ZMap のアーキテクチャや実装について解説している。次のアーキテクチャ図は論文からの引用です。

ZMap Architecture

ZMap はモジュール機構を持っている。図において青枠 (Packet Generation と Response Interpretation) が probe の送受信や解釈を行う部分で、モジュールを追加することで様々な probe に対応することができる。赤枠 (Output Handler) は probe の結果を出力する部分で、モジュールを追加することで出力先を変更したり、アプリケーション固有の処理を行ったりできる。

この他に、パケットの送信部と受信部が別々のスレッドで動作する点も重要な特徴である。可能な限り状態を共有しない工夫を施していて、これにより各処理が独立して絶え間なくスキャンすることができる。

2.1. Addressing Probes

IP アドレスを順番にスキャンしていくと、特定のネットワークに負荷をかけてしまったり、ネットワークの一時的なエラーで連続的にロスが発生する可能性があるので、ランダムな順番で送るようになっている。この順番を決めるアルゴリズムは、保持すべき状態が少なく済み、かつ IPv4 アドレス空間全体にもれなくリーチすることができるものを提案している（アルゴリズムについては論文で数式付きで解説されているのでそちらを参照）。

特定のアドレス範囲を除外する機能もある。これは IANA が予約済みの範囲や、ネットワーク管理者からの除外リクエストに対応するために必要である。この情報は内部では基数木 (Radix Tree) で管理されていて、設定ファイル経由で指定することができる。

2.2. Packet Transmission and Receipt

パケットの内容をキャッシュしたり、カーネル空間でのオーバヘッドを減らすために、パケットは Raw ソケットを使ってイーサネットレイヤーで送っている。これにより、例えばイーサネットヘッダーのチェックサム以外は変わらないという前提で最適化できる。他にもルーティングや ARP cache のルックアップ、Netfilter のチェックなどをバイパスできる。

イーサネットレイヤーで TCP SYN パケットを送っているので、カーネル側では TCP コネクションを確立しようとしていることを認識していない。これにより、もしサーバ側から ACK＋SYN パケットが返送されてきたとしても、自動的に RST パケットを送り返してコネクションをクローズしてくれる。

応答パケットの受信部は libpcap というライブラリを使っており、これによってネットワークトラフィックをキャプチャしたり、パケットをフィルタリングしたりしている。libpcap がボトルネックになる可能性があるが、多くのホストは probe パケットに対して応答を返さないので、libpcap で十分に処理することができる。

(nhiroki の疑問点・調べたこと)

  • Netfilter はパケット処理のフレームワークで、例えばパケットフィルタリングや、ネットワークアドレスとポートの変換（NAPT）などが行える。iptables はこれの設定操作をするプログラム。
  • ルーティングや ARP cache のルックアップをバイパスできるのは、外部ネットワークに向けて毎回宛先の違うリクエストを投げるので、デフォルトゲートウェイに決め打ちで送信している、ってことかな？

2.3. Probe Modules

前述の通り、probe の送受信や解釈を行う部分はモジュールを追加することで様々な probe に対応することができる。

ZMap では TCP ポートスキャニングを行うために SYN scanning (half-open scanning) と呼ばれるテクニックを使ってやり取りするパケットの数を減らしている。

TCP ポートスキャニングでは次の三通りのケースが想定されるが、最も頻発するケース 1 は 1 パケットのやり取りで済む (図は nhiroki が作成)。

  • ケース 1: unreachable もしくは unresponsive のときは SYN パケット 1 つ。
  • ケース 2: closed port の場合は SYN と RST パケットの 2 つ。
  • ケース 3: open port の場合は SYN, ACK+SYN と RST パケットの 3 つ。

TCP 3-Way Handshake Cases

(nhiroki の疑問点・調べたこと)

SYN scanning (half-open scanning) を知らなかったので調べたところ、Nmap のドキュメントに説明があるのを見つけました。

This technique is often referred to as half-open scanning, because you don’t open a full TCP connection. You send a SYN packet, as if you are going to open a real connection and then wait for a response. A SYN/ACK indicates the port is listening (open), while a RST (reset) is indicative of a non-listener. If no response is received after several retransmissions, the port is marked as filtered. The port is also marked filtered if an ICMP unreachable error (type 3, code 0, 1, 2, 3, 9, 10, or 13) is received. The port is also considered open if a SYN packet (without the ACK flag) is received in response.

(引用元：Port Scanning Techniques - NMAP.ORG)

通常の TCP 3-Way ハンドシェイクでは、まず (1) クライアントがサーバに対して SYN パケットを送って TCP コネクションの確立要求をし、(2) サーバはそれに対して ACK+SYN パケットを返送し、(3) それを受け取ったクライアントは ACK パケットを送ってコネクションを確立します。

コネクションを切断するときも同様に、(4) クライアントがサーバに対して FIN パケットを送って TCP コネクションの切断要求をし、(5) サーバはそれに対して ACK+FIN パケットを返送し、(6) それを受け取ったクライアントは ACK パケットを送ってコネクションを切断します。

TCP 3-Way Handshake

SYN scanning は最初の SYN パケットに対する応答を見ることでポートの状況を知るテクニックで、ACK+SYN パケットが返ってきたときは open port だと判断し、RST パケットを使ってコネクション確立要求をリセットします (前述のケース 3 を参照)。このようにコネクションの確立を最後まで行わないことが half-open という名前の由来のようです。これにより、コネクションの切断処理 (FIN, ACK+FIN, ACK の 3 パケット) をやり取りせずに済みます。

この他のポートスキャン手法に TCP スキャン (ハンドシェイクを最後まで行う)、FIN スキャン、NULL スキャンなどがあるようです (参考：1.5.2 ポートスキャンの各種方法 - IPA ISEC)

Checking Response Integrity 受け取ったレスポンスが probe パケットに対するものか、それとも他のバックグラウンドトラフィックに対するものかを判断するために、probe モジュールは probe パケットにスキャン固有のデータを埋め込む (SYN cookies と似た手法)。ZMap は scan-specific secret を鍵とした宛先アドレスの MAC (Message Authentication Code) 値を計算し、これを埋め込んでいる。性能保証の観点から、MAC の計算には UMAC を用いている。このようなデザインによって、probe パケットの受信部は scan secret と初期設定だけをパケット送信部と共有すれば良くなる。

2.4. Output Modules

ZMap の出力部分はモジュール機構になっており、アプリケーションは様々な通知を受け取って、それに基づいて処理をすることができる。プレーンテキストで出力するものや、Redis DB 向けにキューイングするものが、ビルトインのアウトプットモジュールとして提供されている。

forge_socket ZMap の SYN スキャンは前述の通りイーサネットレイヤーで行われるため、カーネルは TCP コネクションの確立処理を関知しない。そのため、スキャン後にアプリケーションがスキャン先サーバとデータのやり取りをしたい場合は新たに TCP コネクションを張り直す必要がある。このオーバヘッドを減らすため、forge_socket という、ZMap initiated なコネクションを Kernel-aware にしてアプリケーション側に引き継げる仕組みを実装している。

3. Validation and Measurement

ギガビットイーサネットのコネクションを持つエントリーレベルのサーバーで、パブリックな IPv4 アドレス空間を約 44 分でスキャンすることができた。98% のリスニングホストを検知し、同様のカバレッジのスキャンを Nmap で行ったときに比べて 1300 倍の性能向上が得られた。

3.1. Scan Rate: How Fast is Too Fast

  • Scan rate : probe パケットの送信レート
  • Hit rate : ACK+SYN パケットを返してきたホストの割合

もし libpcap や upstream provider (これは何を指しているんだろう？) がボトルネックとなる場合、scan rate が高くなるとパケットの破棄が増え、hit rate が下がる可能性がある。これを検証するため、scan rate を変えてスキャンする実験を行ったところ、scan rate と hit rate の間には統計学的に有意な相関は見られなかった。これは scan rate を抑えたとしても、検知可能なホストの数は変わらないことを意味する。またスキャナーがフルスピードで probe を送っても libpcap は十分処理可能であり、ギガビットスピードのネットワークのスキャンにおいて PF_RING のようなカーネルモジュールは不要であることが分かった。

3.2. Coverage: Is One SYN Enough?

本手法では SYN パケットを一度だけ送ることで高速化を図っているが、一度だけだと一時的なネットワークエラーなどによってホストが検知できない可能性がある。このため、SYN パケットを一回送るだけでどの程度のホストを検知することができるのかが重要になる。そしてその割合を算出するためには、全体でどれだけのホストが存在しているのかを知る必要がある。

SYN パケットを複数回送ることによってどれだけホストの検知数が増えるかを確認し、その増加の割合が変わらなくなった時点での検知数をベースラインとして、これの検証を行った。実際の測定によると、1 パケットで 97.9%、2 パケットで 98.8%、3 パケットで 99.4% のホストを検出できた。97.9% は典型的なリサーチアプリケーションでは十分なカバレッジで、もし更にカバレッジが必要な調査の場合は設定でパケット送信のリトライ回数を増やすこともできる。

3.3. Variation by Time of Day

既存手法ではインターネット全体のスキャンに数日から数ヶ月かかっていたが、ZMap ではこれを一時間以下で行えるようになった。では、一日の中でいつスキャンを行うのが効率的か？

これを調べるため、著者らはインターネット上のランダムな 1% のホストに対して TCP 443 番ポートのスキャンを 24 時間に渡って行った。その結果、時間帯によって +/-3.1% のヒットレートの変化が観測された。最も応答率が高かったのが 7:00 AM EST 頃で、最も応答率が低かったのが 7:45 PM EST 頃であった。おそらくネットワークの輻輳やパケットのドロップレート、日中に断続的に接続されるホストによって変化が生じていると推測している。なお、インフォーマルなテストによると曜日や月内の日にちによる変化は確認できなかったとのこと。

3.4. Comparison with Nmap

Nmap と ZMap は異なる用途に最適化されている。Nmap は少数のホスト上の多数のポートをスキャンする多目的なツールとして作られている。それに対し、ZMap は多数のホスト上の一つのポートをスキャンするツールとして作られている。

(Nmap の設定を色々変えて性能評価している。読み飛ばした)

3.5. Comparison with Previous Studies

(SSL 証明書のスキャンを行った既存研究と比較している。読み飛ばした)

4. Applications and Security Implications

本章では ZMap を用いた様々な調査の結果を報告し、それを通してZMap の性能や有用性を論じている。各調査のショートサマリーが第 1 章の終わりにもあるのでそちらも参照。

4.1. Visibility into Distributed Systems

CA 証明書のスキャン。二つの誤発行を発見した。

4.2. Tracking Protocol Adoption

一年以上の間、ネットワークスキャンを頻繁に実行し、HTTPS の普及率の変化を調べた。

4.3. Enumerating Vulnerable Hosts

UPnP (Universal Plug and Play) の既知の脆弱性修正が行われていないホストのスキャン、など

4.4. Discovering Unadvertised Services

Tor ブリッジのスキャン。ブリッジは定期的に変更されるため従来の手法では有効なブリッジのリストを作成するのは困難だった。ZMap は高速にスキャンすることができるため、宣伝されていない有効なブリッジを見つけることができた。

4.5. Monitoring Service Availability

ZMap はサービスの死活監視にも有用。ハリケーン Sandy がアメリカ東海岸に上陸した際の停電によってホストに到達できなくなった様子が観測できた。

4.6. Privacy and Anonymous Communication

高速にネットワークをスキャンできるので、特定のデバイスのトラッキングに使える可能性がある。また、シングルパケットを高速に送信できることを利用して、暗号化したデータを全アドレスに対して送ることで送信先を秘匿したコミュニケーションを実現できるかもしれない。

5. Scanning and Good Internet Citizenship

高速なスキャンがネットワークやサービスの負荷にならないように注意しなければならない。負荷を下げるような手法として、ZMap はランダムな順番でスキャンする機能を実装している。

スキャンされる側からするとそれが特定のサービスを狙った攻撃であるかのように感じたり、純粋にスキャンされることを快く思わないかもしれない。そこで probe を受け取った人が、その目的を理解し、希望に応じてスキャンから除外できるように、著者らは下記のことを行った。

  • ソースアドレスの 80 番ポートにアクセスすると、スキャンの目的が表示されるようになっている。また、今後スキャンするのをやめてもらうための連絡先を記載した。
  • ソースアドレスの DNS を逆引きすると大学のドメインが得られるように設定した。これにより、トラフィックが学術研究の一環によって生じているものだと分かるようにした。
  • 大学の IT 部門とあらかじめ調整し、問い合わせが行く可能性がある旨を伝えた。

また、著者らは他の研究者のためにネットワークスキャンを行う際のガイドラインを提示している (詳しくは論文参照)。

5.1. User Responses

一年間で約 200 回のインターネット全体のスキャンを行ったところ、前述の問い合わせ窓口などに対してトラフィックの受信者から 145 通のメールを受け取った。これらに対してスキャンの目的を伝え、リクエストに応じて直ちにスキャンリストから除外する処理を行った。合計で 3,753,899 アドレス (パブリックな IPv4 アドレス空間の 0.11%) を除外した。また 15 件の敵対的な返答を受け取った（下記引用参照）。

We received 15 actively hostile responses that threatened to retaliate against our institution legally or to conduct a denial-of-service (DOS) attack against our network. In two cases, we received retaliatory DOS traffic, which was blacklisted by our upstream provider.

既存のネットワークスキャニングツールは小規模なネットワークセグメントを対象としている。また、最もポピュラーな Nmap は様々な probing technique をサポートした多目的なツールとして作られている。それに対し、ZMap はインターネット規模のスキャンに特化することで、その用途においてより高い性能を実現している。

既存のインターネット規模向けのスキャナーとして IRLscanner がある。これは IPv4 アドレス空間をおよそ 24 時間で探索することができる（24,421 packets per second）。これは IRLstack と呼ばれるカスタムな Windows ネットワークドライバを利用したり、各スキャンに対して完全なルーティングテーブルを必要とする。これに対し、ZMap は self-contained なネットワークスキャナーでカスタムドライバを必要としない。また IRLscanner がリサーチコミュニティに公開されていないのに対し、ZMap はオープンソースライセンスのもとで公開されている。ZMap は 1.37 million packets per second でスキャン可能で、これは IRLscanner の 56 倍速い。

PF_RING, PacketShader そして netmap などは Linux カーネルのネットワークスタックを入れ替えることで高速化を実現しているが、ZMap ではそのような変更を行わずにギガビットイーサネットのスピードで probe パケットを送ることができる。ZMap は libpcap を使用しているが、probe に対して応答するホストの数は少ないため、libpcap でもパケットをドロップせずにレスポンスを処理することが可能だと分かった。現在のツールのボトルネックはネットワークスタックよりもスキャンの方法にある。

過去にたくさんのインターネット規模のネットワークサーベイが行われたが、時間がかかったり、複数台のマシンが必要だった。ZMap を使うことでそれらよりも高速で、かつ少ない台数で調査を行うことができる。

7. Future Work

IPv6 アドレスへの対応、10 ギガビットイーサネットでの調査、SSL/TLS の拡張である Server Name Indication (SNI) への対応、サーバ管理者がスキャン除外の設定をするためのスタンダード作り (robots.txt のようなもの)。

8. Conclusion

(以上の内容のまとめのため省略)