DNS DNS...

2015

年度 修士論文

User-Agent

毎の

DNS

キャッシュの効果分析

提出日：2016

年

2

月

1

日

指導：後藤滋樹教授

早稲田大学大学院 基幹理工学研究科 情報理工・情報通信専攻

学籍番号：5114F058-7

高橋 一基

目次

1 序論 3 1.1 研究の背景 . . . 3 1.2 研究の目的 . . . 4 1.3 本論文の構成 . . . 4 2 DNS 5 2.1 DNSとは . . . 5 2.1.1 DNSの目的 . . . 5 2.1.2 DNSによる名前解決の仕組み . . . 5 2.2 DNSキャッシュ . . . 6 2.2.1 DNSキャッシュの概要 . . . 6 2.2.2 DNSキャッシュの挙動に関する事前調査 . . . 6 3 提案手法 11 3.1 既存研究 . . . 11 3.1.1 下田らのモデル式 . . . 11 3.1.2 TTL補正式 . . . 14 3.2 提案手法の概要 . . . 15 4 実験 18 4.1 実験に用いたデータ . . . 18 4.2 対象としたドメインと User-Agent . . . 18 4.3 結果のグラフ . . . 20 4.4 結果の考察 . . . 33 4.4.1 立ち上がりがないグラフ . . . 33 4.4.2 立ち上がりが遅れるグラフ . . . 34 4.4.3 正規分布的なカウント増加が見られるグラフ . . . 34

目次 4.5 IPアドレス毎のカウント数測定の追加実験 . . . 35 5 結論 38 5.1 まとめ . . . 38 5.2 今後の課題 . . . 38 5.2.1 より多くのデータを用いた実験 . . . 38 5.2.2 別地域で収集されたデータへの適用 . . . 38 謝辞 40 参考文献 41

図一覧

2.1 Windowsに同一内容が 2 つキャッシュされる例 . . . 7 2.2 名前解決要求が送信されない例 . . . 8 2.3 シーケンス番号が 1 の www.apple.com, HTTP のパケット . . . 9 2.4 www.goto.info.waseda.ac.jpを名前解決する DNS パケット . . . 9 2.5 シーケンス番号が 1 の www.goto.info.waseda.ac.jp, HTTP のパケット . . . 10 3.1 DNSキャッシュの TTL 切れの性質 . . . 12 3.2 シミュレーションによるモデル式の例 . . . 13 3.3 TTL補正式の具体例 . . . 15 3.4 提案手法のフローチャート . . . 16 4.1 www.yahoo.co.jp,すべての User-Agent のグラフ . . . 21 4.2 www.yahoo.co.jp, Windowsのグラフ . . . 21 4.3 www.yahoo.co.jp, Mac OSのグラフ . . . 22 4.4 www.yahoo.co.jp, iOSのグラフ . . . 22 4.5 www.yahoo.co.jp, Androidのグラフ . . . 23

4.6 www.yahoo.co.jp, Internet Explorerのグラフ . . . 23

4.7 www.yahoo.co.jp, Google Chromeのグラフ . . . 24

4.8 www.yahoo.co.jp, Firefoxのグラフ . . . 24 4.9 www.facebook.com, すべての User-Agent のグラフ . . . 25 4.10 www.facebook.com, Windowsのグラフ . . . 25 4.11 www.facebook.com, Mac OSのグラフ . . . 26 4.12 www.facebook.com, Androidのグラフ . . . 26 4.13 www.facebook.com, iOSのグラフ . . . 27

4.14 www.facebook.com, Internet Explorerのグラフ . . . 27

4.15 www.facebook.com, Google Chromeのグラフ . . . 28

4.16 www.facebook.com, Firefoxのグラフ . . . 28

図一覧

4.18 platform.twitter.com, Windowsのグラフ . . . 29

4.19 platform.twitter.com, Mac OSのグラフ . . . 30

4.20 platform.twitter.com, iOSのグラフ . . . 30

4.21 platform.twitter.com, Internet Explorerのグラフ . . . 31

4.22 platform.twitter.com, Google Chromeのグラフ . . . 31

4.23 platform.twitter.com, Firefoxのグラフ . . . 32

4.24 platform.twitter.com, Safariのグラフ . . . 32

4.25 www.google.co.jp, すべての User-Agent のグラフ . . . 35

4.26 カウント数全体に対する上位 100 ユーザの割合 . . . 36

第

1

章

序論

1.1

研究の背景

DNS (Domain Name System) は IP アドレスとドメイン名を対応付けるためのプロトコル で、今日のインターネットを利用する上で欠かすことの出来ないものである。DNS の実装は 最適化、効率化を目的として発展しているが、このため挙動が複雑なものになっている。DNS キャッシュサーバの実装の不可解な点を指摘した論文として藤原らによるもの [1] がある。こ の論文では DNS キャッシュサーバの実装の 1 つである BIND 9 [2] がルート DNS サーバ向けに 無駄なクエリを生成することや存在しない TLD (Top Level Domain) へのクエリが多いことな どが報告されている。本研究ではユーザ側での DNS クエリや DNS キャッシュの挙動を調べる ため事前調査を行った。この詳細は第 2.2.2 節にて述べる。この結果、同一 Web ブラウザであ るにもかかわらずアクセスするドメインによって DNS キャッシュの扱い方が変化する例など が見つかり、ユーザ側の DNS の挙動も複雑なものであることがわかった。  またユーザ側の DNS キャッシュに着目した研究として下田らによるもの [3] がある。この研 究ではユーザ側での DNS キャッシュ切れの性質を元に、サービスへのアクセス数を推定する 手法を提案している。この研究の背景に HTTPS による通信の暗号化が世界的に進んでいると いう状況がある。例として Google 検索は 2013 年 9 月に [4]、Yahoo 検索は 2015 年 8 月に [5]、 HTTPSによる通信が必須となった。通信が暗号化されるとパケットを盗聴されても被害を防 ぐことができる。しかし通信事業者にとってはこの通信の暗号化と、CDN (Contents Delivery Network) によるコンテンツの所在地のブラックボックス化が組み合わさると、自分たちの管 理するネットワークに流れているトラフィックが何のサービスのものなのかがわからなくなっ てしまうという問題が起こる。DNS パケットは暗号化されていないため、この手法は HTTPS によりサービスが行われるドメインについてもトラフィック量を推定することができる。    

第 1 章 序論

1.2

研究の目的

下田らの研究で提案されたあるサービスへのアクセス数を推定するモデル式は、詳しくは第 3.1.1節にて紹介するが、ユーザを TTL に従うユーザと TTL に従わないユーザの 2 つに区別 している。ただしアクセスを行う際に使用している OS (Operating System) や Web ブラウザ などといった要素は考慮されていない。実際にはこれら OS や Web ブラウザなどのアプリケー ションには様々な種類がある。またこれらの組み合わせも考えると、その数はさらに増加する。 しかし事前調査を行った通り、DNS キャッシュの扱い方に関してこれらがすべて同じ挙動をす るとは限らない。また下田らの研究ではモデル式では識別できない例も報告されており、改善 の余地が残されている。  そこで本研究ではこの下田らの手法を拡張し、User-Agent 毎にグラフ化を行う。そして得ら れた従来とは異なる特徴のあるグラフについて検討を行い、下田らの手法の精度向上のための 第一歩とすることを目的とする。

1.3

本論文の構成

本論文は以下の章により構成される。 第 1 章 序論 本論文の概要を述べる。 第 2 章 DNS DNSの概要と事前調査の内容について述べる。 第 3 章 提案手法 本論文の提案手法について説明する。 第 4 章 実験 提案手法に対する実験の結果、および考察を述べる。 第 5 章 結論 本論文の結論を述べ、今後の課題を示す。

第

2

章

DNS

2.1

DNS

とは

ここでは DNS の概要とその仕組みについて説明する。 2.1.1 DNSの目的 DNSはドメイン名を対応する IP アドレスに変換する (名前解決を行う) ためのプロトコル である [6]。インターネットにおける通信相手の識別には IP アドレスが用いられる。しかし IP アドレスは数字の羅列であり人間が覚えるには不便であるため、これを覚えやすくするために ドメイン名が用いられる。 2.1.2 DNSによる名前解決の仕組み DNSによる名前解決はユーザが意識することなく行われるのが一般的である。ここでは DNS による名前解決の仕組みを、あるユーザが “www.exmaple.com” というドメイン名の名前解決 要求を行う場合を例として説明する。  はじめにユーザが “www.exmaple.com” へアクセスを試みると、ユーザの使用する端末の DNSの検索を行うプログラムである「スタブリゾルバ」が「DNS キャッシュサーバ」に名前解 決要求を送信する。すると DNS キャッシュサーバはまず検索の起点となる「ルートサーバ」に “www.exmaple.com”の IP アドレスを問い合わせる。ルートサーバは “com” ドメインを管理す る「権威サーバ」の IP アドレスを DNS キャッシュサーバに返す。次に DNS キャッシュサーバ は “com” ゾーンを管理する権威サーバに “www.exmaple.com” について問い合わせる。この権 威サーバは “example.com” ドメインを管理する権威サーバの IP アドレスを返す。そして DNS キャッシュサーバが “example.com” ゾーンを管理する権威サーバに “www.exmaple.com” につ いて問い合わせると、この権威サーバは “www.exmaple.com” の IP アドレスを返す。最後に DNSキャッシュサーバはスタブリゾルバに “www.exmaple.com” に対応する IP アドレスを返

第 2 章 DNS 答し、これにより名前解決が完了する。  このように DNS による名前解決は、DNS キャッシュサーバと各ドメインを管理する権威サー バとの反復的な通信によって行われる。しかしスタブリゾルバからの名前解決要求があるたび に毎回これらの通信を行うのは非効率的である。そのため DNS にはキャッシュの仕組みが存 在する。DNS キャッシュについては第 2.2.1 節で説明する。

2.2

DNS

キャッシュ

ここでは DNS キャッシュの概要と、DNS キャッシュの挙動に関する事前調査について説明 する。 2.2.1 DNSキャッシュの概要 DNSにより対応付けられたドメイン名と IP アドレスの情報は、ドメイン名ごとに定められ た TTL 値の時間だけキャッシュされる。あるドメイン名と IP アドレスについてのキャッシュが 存在する場合は、名前解決はこのキャッシュの情報により行われ、DNS キャッシュサーバと権 威サーバ間での反復的な名前解決は行われない。TTL 値が 0 になるとキャッシュは破棄され、 この後は再び反復的な名前解決が行われる。また DNS には名前解決の対象が存在しなかった 事をキャッシュする「ネガティブキャッシュ」も存在するが、本論文で扱う DNS のキャッシュ という言葉はすべて名前解決に成功した際のキャッシュを指す。   DNS キャッシュが保存されるのは DNS キャッシュサーバだけではない。ユーザの使用する Webブラウザなどのアプリケーションや OS のスタブリゾルバ、家庭用ルータにも保存される ことがある。 2.2.2 DNSキャッシュの挙動に関する事前調査 DNSキャッシュは第 2.2.1 節で示したように、キャッシュが存在すればこれを利用し、キャッ シュが存在しなければ新たに名前解決の通信を行いこれをキャッシュとして保存する、という 単純な仕組みである。しかし以下に示す例のように、単純には説明できない場合もある。この 事前調査と第 4 節で説明する実験で使用した OS と Web ブラウザに関する簡単な紹介は第 4.2 節で行う。この調査は 2015 年 8 月に行った。またこの調査に際し、「ユーザが Web ページの リンクをクリックする前にそのドメインの名前解決をあらかじめ行う機能」である DNS プリ フェッチは無効にしてある。プリフェッチは DNS の複雑な挙動を生み出す要因の 1 つである。  図 2.1 は Windows 7 [7] の DNS キャッシュに同一内容が 2 つ保存されている例である。これは早 稲田大学基幹理工学部後藤滋樹研究室の Web ページ HTTP://www.goto.info.waseda.ac.jp/ に、Internet Explorer [8] (バージョン 11.0.9600.17959) を用いてアクセスした直後に Google

第 2 章 DNS

Chrome [9] (バージョン 44.0.2403.155 m 64-bit) を用いてアクセスした際のキャッシュの様子 である。

図 2.1: Windows に同一内容が 2 つキャッシュされる例

Internet Explorerと Google Chrome はどちらも Windows 上で動作している Web ブラウザで あるが、これら 2 つのアプリケーションは OS に保存されている DNS キャッシュを共有してい ないことがわかる。また Internet Explorer と Fire Fox [10] (バージョン 40.0.2) を用いて同様の 実験を行ったところ、この場合は OS に保存された DNS キャッシュは 1 つだけであった。よって この 2 つは OS に保存されている DNS キャッシュを共有している。一般的にはこのように 2 種 類の Web ブラウザを同時に使用する状況はあまりないが、メールクライアントや Twitter [11] クライアントのように Web ブラウザではないアプリケーションを Web ブラウザと同時に使用 する状況はよくある。これらのクライアントも DNS の機能を用いる。

 図 2.2 は Google Chrome を使用して HTTP://www.apple.com/ へアクセスし、10 分間 10 秒ご とにリロードを行った際の pcap データの様子である。Wireshark [12] のディスプレイフィルタ を用い、HTTP://www.apple.com/ の名前解決を行う DNS パケットと HTTP://www.apple.com/ を宛先とする HTTP パケットのみを表示している。この実験と次の実験において、DNS パケッ トの宛先アドレスがローカルのものになっているが、これは家庭用ルータが代理で DNS の応

第 2 章 DNS 答を返しているためである。実際には外部の DNS サーバに名前解決要求を送信している。  図 2.2: 名前解決要求が送信されない例 この図では、はじめに名前解決が一度行われた以降、DNS の通信が行われていないことが わかる。HTTP://www.apple.com/ の TTL 値は実験を行った時点では最大で 30 秒程度であっ た。そのため 10 分間リロードを続けている間に TTL 値は 0 になっている。  図 2.3 は同じ pcap データについて、HTTP のうちシーケンス番号が 1 のパケットのみを表 示したものである。

第 2 章 DNS 図 2.3: シーケンス番号が 1 の www.apple.com, HTTP のパケット すると該当する HTTP のパケットは DNS の直後に送信された 1 つしか存在しないことがわ かる。これは実験中に行われた HTTP の通信は、はじめに確立された TCP のコネクションの 上で 10 分間ずっと行われていたことを示す。このことから、たとえ DNS のキャッシュが切れ ていても、TCP のコネクションが確立されていれば通信相手を識別できているため、その相 手に対する DNS による名前解決要求は送信されないことがわかる。  同様の実験を HTTP://www.goto.info.waseda.ac.jp/ ついて行った。このドメインについ てキャッシュされた TTL は数万秒程度であったため、60 秒毎に “ipconfig /flushdns” のコマン ドで Windows に保存された DNS キャッシュを消去した。このときキャプチャされた www.goto. info.waseda.ac.jpを名前解決する DNS パケットを図 2.4 に示す。 図 2.4: www.goto.info.waseda.ac.jp を名前解決する DNS パケット 10秒ごとにリロードを行っているが DNS パケットの送信は 10 秒毎ではなく、OS の DNS

第 2 章 DNS キャッシュが消去された次のリロードで再度 www.goto.info.waseda.ac.jp を名前解決する DNS パケットが送信されていることがわかる。また同じ pcap データについて、HTTP のうちシー ケンス番号が 1 であり index.html を取得しているパケットを抜き出したものを図 2.5 に示す。 図 2.5: シーケンス番号が 1 の www.goto.info.waseda.ac.jp, HTTP のパケット こちらは図 2.3 とは異なり、シーケンス番号が 1 のパケットは 1 つだけではない。すなわち TCPのコネクションが一度確立され続けていた HTTP://www.apple.com/ へのアクセスとは異 なり、TCP のコネクションが何度か切れていることがわかる。10 秒毎にリロードするという 方法は同じでも、アクセスするドメインによって DNS また HTTP のパケットのやりとりは異 なる挙動を示している。これらの例から DNS キャッシュは、第 2.2.1 節で述べたような、すな わち DNS の教科書に書かれているような、単純な仕組みだけではなく、より多くの要素が関 係し複雑な挙動を見せることがわかる。

第

3

章

提案手法

3.1

既存研究

本論文は下田らの研究を拡張した手法で実験を行っている。まず下田らの研究の手法を紹介 する。 3.1.1 下田らのモデル式 下田らの提案するモデル式は、ユーザのスタブリゾルバでの DNS キャッシュの TTL 切れの 性質を元に、ドメインへのアクセス数を推定するものである。「ユーザのスタブリゾルバでの DNSキャッシュの TTL 切れの性質」を以下の図 3.1 を用いて説明する。

第 3 章 提案手法 䝴䞊䝄ϯ 䝴䞊䝄Ϯ 䝴䞊䝄ϭ E^䜻䝱䝑䝅䝳䝃䞊䝞 dd>䠖ϰϬ ;ƐͿ䜢グ㘓 dd>䠖ϯϬ ;ƐͿ䜢グ㘓 ϭϬ;ƐͿ dd>䠖ϮϬ ;ƐͿ䜢グ㘓 ඲ ඲ ඲ ඲䝴䝴䝴䞊䝴䞊䞊䞊䝄䝄䝄䝄䛾䛾䛾䛾dd>䛿䛿䛿䛿 ྠ ྠ ྠ ྠ᫬᫬᫬䛻᫬䛻䛻䛻Ϭ䛻䛻䛻䛺䛻䛺䛺䛺䜛䜛䜛䜛 ϭϬ;ƐͿ 䛭䛾᫬Ⅼ䛷䛾dd>䜢㏉䛩 図 3.1: DNS キャッシュの TTL 切れの性質 3人のユーザが同じドメインを名前解決するために一台の DNS キャッシュサーバを使用する 場合を考える。ユーザ 1 が名前解決を行うと、ユーザ 1 のスタブリゾルバにはドメインと IP ア ドレスの対応と TTL：40 秒という情報が記録される。その 10 秒後、ユーザ 2 が名前解決を行 う。すると DNS キャッシュサーバ内でのこのドメインの TTL も 10 減少しているため、TTL： 30秒が返りこれが記録される。このときユーザ 1 が保持しているキャッシュついても 10 秒が 経過しているため TTL：30 秒となっている。ユーザ 3 についても同様で、ユーザ 3 が TTL： 20秒を DNS キャッシュサーバから受け取ると、その時点でユーザ 1、ユーザ 2 の TTL も 20 秒 となる。すなわち全ユーザの TTL の値は揃い、これによりすべてのユーザは DNS キャッシュ が同時に切れる。これはユーザが何人存在しても同じである。  またユーザのあるドメインへのアクセスはポアソン分布に従うと仮定する。するとキャッシュ が同時に切れたユーザによる新たな名前解決要求はこれに従って発生するためモデル化ができ る。この考え方をモデル化した式を以下に示す。 q(t) = N re−r×mod(t,TTL)+ ϵ (3.1) ただし各変数と関数の意味は以下の通りである。 q(t) :名前解決要求数 N : TTL切れが有効なランダムにアクセスするユーザ数

第 3 章 提案手法 r :正常ユーザの単位時間あたりの名前解決要求数 [1/s] t :時間 [s] TTL : そのドメインの権威サーバで設定された TTL の最大値 ϵ : TTLを無視し一定レートでアクセスするユーザ数 mod(t, TTL) :時間 t を TTL で割った余り このモデル式中における TTL は、上記の説明の通り TTL の最大値を表す定数であるが、変 数 N と変数 ϵ の説明文中で用いている TTL はユーザの DNS キャッシュが切れるまでの時間を 表す変数という意味である。右辺の左の項が TTL に従うユーザを表し、右の項が TTL を無視 するユーザを表す。  以下に各変数に値を入れシミュレーションを行ったグラフの例を示す。 図 3.2: シミュレーションによるモデル式の例 この例では各変数は以下のように設定している。 N = 4000

第 3 章 提案手法 r = 0.1 ϵ = 100 TTL = 60 DNSキャッシュが切れるとユーザはポアソン分布に従い再度名前解決要求のクエリを送信す るため、次の時刻において q(t) の値が立ち上がる。その後は指数関数的に減少していき、再度 TTLが 0 になったところで最小となり、次の時刻でまた立ち上がる。これを TTL の値の周期 で繰り返す。ϵ の項が存在するため指数関数的に減少は 0 には収束しない。実際には N, r, ϵ の 3つの変数は未知である。これらを求めるために回帰分析を行う。 3.1.2 TTL補正式 前節では DNS キャッシュサーバが一台の場合を考えた。しかし実際には負荷分散などを目 的として複数台の DNS キャッシュサーバが設置されていることがあり、この場合ユーザはアク セスするたびに異なる DNS サーバにアクセスすることになる。これらの DNS キャッシュサー バ間で、あるドメインについてのキャッシュの TTL 値が揃っているという保証はない。その ため前節の手法をそのまま DNS キャッシュサーバが複数台ある場合には適用できない。そこ で TTL 補正式を用いる。   TTL 補正式は「あるユーザについて、TTL が切れてから次の名前解決要求の送信までに要 した時間」を計算する式である。これは次のように表される。 Tc = T2− (T1+ TTL) (3.2) T1 : n回目の DNS 応答を受け取った時刻 T2 : n+1回目の DNS 要求を送信した時刻 TTL : n回目の DNS 応答で受け取った TTL の値 これを図解したものが図 3.3 である。

第 3 章 提案手法 䛒䜛䝴䞊䝄 E^䝃䞊䝞;」ᩘͿ ǁǁǁ͘ĞdžĂŵƉůĞ͘ĐŽŵ 䜢ྡ๓ゎỴ䛧䛯E^ᛂ⟅ dd>䠖ϯϬ;ƐͿ ϭϮ͗ϬϬ͗ϬϬ ϭϮ͗ϬϬ͗ϯϬ dd>ษ䜜 ϭϮ͗Ϭϭ͗ϭϬ ǁǁǁ͘ĞdžĂŵƉůĞ͘ĐŽŵ 䜢ྡ๓ゎỴ䛩䜛䛯䜑䛾 E^䜽䜶䝸㏦ಙ ϰϬ;ƐͿ

;ϭϮ͗Ϭϭ͗ϭϬͿͲ ΂;ϭϮ͗ϬϬ͗ϬϬͿн;ϯϬͿ΃сϰϬ;ƐͿ

䛣 䛣 䛣 䛣䛾䛾ồ䛾䛾ồ䜎ồồ䜎䜎䜎䛳䛳䛯䛳䛳䛯䛯䛯ϰϬ;ƐͿ䛜䛜䛂䛜䛜䛂䛂䛂dd>ษษ䜜ษษ䜜䜜䜜䛛䛛䜙䛛䛛䜙䜙䜙ḟḟḟ䛾ḟ䛾䛾䛾ྡྡ๓ྡྡ๓๓๓ゎゎゎゎỴỴỴỴせせồせせồồồ㏦㏦㏦ಙ㏦ಙಙ䜎ಙ䜎䛷䜎䜎䛷䛷䛷䛾䛾䛾䛾⤒⤒⤒⤒㐣㐣᫬㐣㐣᫬᫬㛫᫬㛫㛫䛃㛫䛃䛃䛃 図 3.3: TTL 補正式の具体例 あるユーザが www.example.com のを名前解決した DNS 応答を 12:00:00 に受け取ったとする。 そのときの TTL は 30 秒である。するとこの DNS キャッシュは 30 秒後の 12:00:30 に切れる。そし て次にこのユーザが同じ www.example.com を名前解決するための DNS クエリを送信した時刻 が 12:01:10 とする。すると図中の式のように T1 = (12 : 00 : 00), T2 = (12 : 01 : 00), TTL = 30 となり、TTL の補正値 Tc = 40(s) が求まる。  この TTL 補正値を求める際、DNS 応答を受けた DNS キャッシュサーバと、次の DNS 要求を 送信した DNS キャッシュサーバが同一のものである必要がない。そのため複数台の DNS キャッ シュサーバがある場合にも適用できる。この補正値を横軸 (時間) の値とし、積み上げていく ことで式 3.1 の 1 周期分のグラフを作成することができる。

3.2

提案手法の概要

本論文では第 3.1 節で紹介した手法を拡張し、すべてのユーザをまとめた 1 つのグラフだけ ではなく、User-Agent 毎にもグラフを作成する。提案手法の概要を示したフローチャートを以 下に示す。

第 3 章 提案手法 図 3.4: 提案手法のフローチャート 入力は DNS と HTTP のパケットを含む pcap データである。本手法では、あるユーザの DNS 要求・DNS 応答・HTTP 要求の 3 つを 1 つの単位と考え、これを紐付けする。つまり、ある ユーザについて以下の一連の 3 項目が発見できれば紐付け成功とする。 1. あるドメインへの名前解決要求がある 2. その名前解決要求の応答がある 3. 名前解決したドメインへの HTTP アクセスがある

第 3 章 提案手法 1つ目の条件はユーザが DNS キャッシュサーバへ送信した名前解決要求が存在することである。 2つ目の条件はこの名前解決要求に対する応答パケットが存在することである。そして 3 つ目 の条件は、1 つ目と 2 つ目で名前解決されたドメインに対する HTTP アクセスが存在するこ とである。既存手法では DNS パケットのみを用いていたが、本手法では User-Agent の情報の 取得のために HTTP ヘッダを調べる。そのため User-Agent が暗号化され情報が取得できない HTTPSは本手法では扱うことができない。ここでユーザの区別は IP アドレスと User-Agent の両方で行う。また 2 つ目と 3 つ目の条件はプロトコルが異なるためユーザ側のポート番号も 異なる。そのためポート番号を用いた対応付けが出来ない。実際には連続して発生していない、 時間が大きく空いた別タイミングの HTTP アクセスと紐付けされることを防ぐため、これら 3つの条件に当てはまるパケットは近いタイムスタンプを持つ必要がある。今回は 3 項目のタ イムスタンプが 2 秒以内の場合を紐付け成功とする。紐付けが成功したら紐付け成功数を 1 増 やす。  同ユーザかつ同ドメインについて上の 3 項目の紐付けが成功し、それが 2 回目以降の場合に は第 3.1.2 節で述べた TTL 補正式を適用する。一度目の紐付け成功の際は、前回の DNS キャッ シュの TTL 値とこのキャッシュがいつ切れたかがわからないため、TTL 補正式は適用できな い。この計算結果の補正値をグラフの横軸 (経過時間) の位置として、その位置のカウントを 1増やす。これをすべてのパケットの走査が完了するまで繰り返し、カウントを積み上げてい く。走査の終了後、横軸を経過時間、縦軸を積み上げたカウントとして User-Agent 毎にグラ フを描く。

第

4

章

実験

4.1

実験に用いたデータ

 今回の実験にはあるゲートウェイで取得した数千人規模の利用者による DNS と HTTP の トラヒック、2013 年 8 月のある 4 日分のデータセットを用いた。このため各ドメインの TTL 値と、サービスに使用されているプロトコルが HTTP かもしくは HTTPS か、という設定は 当時のものである。  データセットは 4 日分あるが、これを時間で区切ることなく 1 つのグラフにすると横軸 (経 過時間) が非常に長くなり、グラフの形状がわかりづらくなる。また例えば 1 回目のアクセス から 2 回目のアクセスまでの経過時間が 4 時間だった場合を考える。このときユーザの使用形 態について、 • Web ブラウザを 4 時間連続で使用していた • 途中で Web ブラウザの使用を中断しブラウザの再起動などを挟んだ この 2 つのパターンが挙げられるが、直感的には前者のように長時間連続で使用を続けるユー ザはごく少数であると考えられる。だが本手法をこの場合に適用すると、前者の「ユーザは Webブラウザを 4 時間連続で使用していた」という結果でカウントされる。これを防ぐため、 データは 1 時間ごとに区切って集計し、最後にこれを 96 時間分足し合わせてグラフ化すると いう方法をとる。

4.2

対象としたドメインと

User-Agent

今回対象としたドメインは、HTTP でサービスが行われており、かつ人気がありグラフ化の ためのデータが多く取得できるものの中から選んだ。今回は以下の 3 つのドメインについて実 験結果を示す。

第 4 章 実験

• www.yahoo.co.jp • www.facebook.com • platform.twitter.com

www.yahoo.co.jpは Yahoo! JAPAN [13] のポータルサイトのドメインである。検索エンジン サービスでの国内シェア率は Yahoo! JAPAN と Google [14] の 2 つで 9 割程度を占めている [15]。www.facebook.com はソーシャルネットワークサービスである Facebook [16] のドメイン である。公式の発表 [17] によると 2015 年 9 月の世界でのアクティブ利用者は 1 日で 10 億人に も上るという。platform.twitter.com は Twitter のシェア率ボタンに使用されるドメインで ある。  次に今回対象とした User-Agent、すなわち OS と Web ブラウザについて説明する。まず OS について、今回は以下の 4 つの OS を対象とした。 • Windows • Mac OS • Android • iOS

Windows (Microsoft Windows) は Microsoft 社の開発する OS である [7]。Mac OS は Apple 社 の開発する OS である [18]。NetMarketShare の調査 [19] によると 2013 年時点では Windows の シェア率が 9 割以上である。そのため取得できるデータの量には大きく差が生じる。LinuxOS についてもグラフを作成したが、データ量が少なくグラフに特徴が現れなかったため今回は報 告しない。Android は Google 社が開発するモバイル端末向けの OS である [20]。iOS は Apple 社開発するモバイル端末向けの OS で、Apple 社製品の iPhone や iPad などに搭載されている [21]。  続いて今回対象とした Web ブラウザを説明する。以下の 4 つを対象とした。 • Internet Explorer • Google Chrome • Firefox • Safari

第 4 章 実験

Internet Explorerは Microsoft 社が開発する Windows 用の Web ブラウザである。今回使用 したデータセットは 2013 年のものであり、同じく Microsoft 社が開発している Web ブラウザ Edge [22]についてのデータはこの時点で存在しないため取り扱わない。Google Chrome は Google社が開発する Web ブラウザである。Firefox (Mozilla Firefox) は Mozilla 財団が開発し ている Web ブラウザである。Safari は Apple 社が開発する Web ブラウザで、Apple 社性の OS である Mac OS と iOS に搭載されている [23]。  これらの OS と Web ブラウザ、またその組み合わせの中からデータ量が少なくグラフの特徴 が見られなかったものを除き、特徴が見られたものを次節にて報告する。また今回の実験では 説明した各 OS と Web ブラウザについてバージョンごとの区別は行っていない。

4.3

結果のグラフ

実験結果のグラフを以下に示す。グラフは 3 つのドメインについて特徴が現れているものを 8枚ずつ、計 24 枚載せる。すべてのグラフは縦軸がカウント数、横軸は単位が秒の経過時間 である。グラフタイトルが All のものは名前の通り User-Agent を区別せずに集計したもの、す なわち既存手法と同じである。グラフタイトルが OS 名のものは、Web ブラウザによらずその OSと判別されたものすべてを集計したグラフである。同様にグラフタイトルが Web ブラウザ のものは、OS によらずその Web ブラウザと判別されたものすべてを集計したグラフである。

第 4 章 実験

図 4.1: www.yahoo.co.jp, すべての User-Agent のグラフ

第 4 章 実験

図 4.3: www.yahoo.co.jp, Mac OS のグラフ

第 4 章 実験

図 4.5: www.yahoo.co.jp, Android のグラフ

第 4 章 実験

図 4.7: www.yahoo.co.jp, Google Chrome のグラフ

第 4 章 実験

図 4.9: www.facebook.com, すべての User-Agent のグラフ

第 4 章 実験

図 4.11: www.facebook.com, Mac OS のグラフ

第 4 章 実験

図 4.13: www.facebook.com, iOS のグラフ

第 4 章 実験

図 4.15: www.facebook.com, Google Chrome のグラフ

第 4 章 実験

図 4.17: platform.twitter.com, すべての User-Agent のグラフ

第 4 章 実験

図 4.19: platform.twitter.com, Mac OS のグラフ

第 4 章 実験

図 4.21: platform.twitter.com, Internet Explorer のグラフ

第 4 章 実験

図 4.23: platform.twitter.com, Firefox のグラフ

第 4 章 実験

4.4

結果の考察

はじめにすべてのグラフについて、横軸 (結果時間) の値が負の位置にカウントが存在する。 このグラフにおける経過時間とは DNS キャッシュの TTL が切れてから、次の名前解決要求送 信までの時間である。そのため経過時間が負になるのは「TTL が切れていないにも関わらず、 次の名前解決要求が送信された」ということを表す。この挙動はどのグラフでも一定数存在し ていることがわかる。次にすべてのグラフは左端、すなわち横軸が最小の位置でカウントが 増えている。これはダブルクリックなどの原因で 2 連続で送信された DNS パケットをどちら も集計してしまい、時間差 0 秒で 2 回の紐付けに成功したとしてカウントをしたプログラムの ミスである。また今回扱った 3 つのドメインについて TTL の最大値は、www.yahoo.co.jp と www.facebook.comが 60 秒、platform.twitter.com が 3600 秒である。そして各グラフの横 軸の最小値の絶対値は、各ドメインの TTL の最大値もしくはそれに近い値となっている。こ れは図 3.3 を見ると分かる通り、そのドメインの TTL の値が大きいほど、その DNS キャッシュ が切れるまでの時間、言い換えると横軸が 0 の位置までの距離が長くなるためである。  多くのグラフは図 3.2 の 1 周期分のグラフと似た形状、つまり「TTL が切れた直後にグラフ が立ち上がり、指数関数的に減衰し、いつまでも 0 に収束しない」という特徴が現れている。 これは既存手法と同様の結果である。一方で既存手法では見られなかった特徴として次の 3 つ のものが見つかった。 4.4.1 立ち上がりがないグラフ 図 4.13 は www.facebook.com に iOS からアクセスしたユーザの結果をまとめたグラフであ る。このグラフは他のグラフとは異なり、横軸が 0 の位置、すなわち DNS キャッシュが切れた 直後の立ち上がりとその後の指数関数的な減衰が見られない。同じく iOS によるアクセスの図 4.20ではこの DNS キャッシュが切れた直後の立ち上がりとその後の指数関数的な減衰が見ら れるため、iOS はすべてこのような結果になるというわけではないことがわかる。  横軸が 0 の位置で立ち上がりがないということは、「DNS キャッシュを使用していない」と言 える。3.1 式で言えば右辺の N re−r×mod(t,TTL)の項が表す TTL に従うユーザが存在しないため グラフが時間で変化せず、ϵ の項のみが存在している状況である。このような現象が起こる原 因の仮説として「iOS の Facebook のアプリケーションは起動時に名前解決要求を送信し、起 動中にキャッシュが切れても次の名前解決要求を送信しない。そして次回起動時に再び名前解 決要求が送信される。これにより、生成されるグラフは DNS キャッシュの TTL 切れに従うの ではなく、ユーザが Facebook のアプリケーションを起動する間隔に従うことになる。よって DNSキャッシュ切れの性質とポアソン分布を仮定とした 3.1 式 N re−r×mod(t,TTL)の項ではなく、 ランダムアクセスの同式 ϵ の項に従ったグラフが得られた」が考えられる。

第 4 章 実験

4.4.2 立ち上がりが遅れるグラフ

図 4.7 と図 4.15 はそれぞれ www.yahoo.co.jp と www.facebook.com に Google Chrome から アクセスしたユーザのグラフである。また図 4.12 は www.facebook.com に Android からアク セスしたユーザのグラフである。これらのグラフには「グラフの立ち上がりが DNS キャッシュ が切れた直後ではなく、少し遅れた位置で起こる」という特徴が見られる。例として、図 4.15 の立ち上がりがピークに達したときの横軸の値は 120 であった。  立ち上がりが遅れるということは、「DNS キャッシュを使用しているが、TTL の値をデフォ ルトのまま扱っていない」と言える。これは立ち上がりのないグラフの例と DNS キャッシュに 素直に従っていないという点では同じだが、性質は異なる。よって原因も別にあると考えられ る。

  Google Chrome と Android はどちらも Google 社が開発する Web ブラウザと OS である。 Google Chromeには、デフォルトでは無効になっているが、ブラウザが DNS キャッシングの 機能を OS の代わりに行う機能が存在する。また古いバージョンの Google Chrome では、DNS キャッシュの TTL が 60 秒以下の場合とそれ以上の場合で挙動が変わる仕組みが存在するとい う情報が見つかった [24]。また第 2.2.2 節の事前調査において報告した通り、最新バージョン の Google Chrome であっても TTL が最大 30 秒程度のドメインと TTL が数万秒あるドメイン とでは挙動の変化が見られた。これらの機能が影響し、本来の TTL の設定値よりも長い時間 DNSキャッシュを保持し、結果次の名前解決要求が遅れるのではないかと考えられる。 4.4.3 正規分布的なカウント増加が見られるグラフ www.yahoo.co.jpと www.facebook.com の多くのグラフについて、横軸が 3000 秒から 3500 秒の位置でカウントが正規分布のような形で増えていることがわかる。この現象は下田らの 研究では報告されていない。より綺麗な正規分布の形が出現したグラフの例として、以下に www.google.co.jpにアクセスしたすべての User-Agent のグラフを示す。

第 4 章 実験 図 4.25: www.google.co.jp, すべての User-Agent のグラフ しかしすべてのグラフについてこの現象が見られるわけではなく、www.facebook.com に Androidからアクセスしたユーザのグラフである図 4.12 にはこれが出現していない。また platform.twitter.comについては一見するとこの現象が現れていないように見える。だが 図 4.17 は横軸が−600 の付近からカウントが増加しており、このドメインの TTL の最大値は 3600秒であったため、グラフの左端から 3000 秒経過した位置ということになる。すなわちこ れは「DNS キャッシュが切れた直後、横軸が 0 の位置から 3000 秒程度経過した後にカウントが 正規分布的に増加する」という現象ではなく、「DNS 応答を受け取った時点、横軸の最小値の 位置から 3000 秒程度経過した後にカウントが正規分布的に増加する」という現象だといえる。 この原因としてプログラムのミスということも考えられるが、その場合はすべてのグラフにつ いてこの特徴が現れるはずであり、出現するものとしないものがあるためこの可能性は低い。

4.5

IP

アドレス毎のカウント数測定の追加実験

第 4.3 節にて結果を示した本手法において、アクセスを頻繁に行っているユーザは DNS キャッ シュが切れるとすぐ次のアクセスを行うため、横軸が 0 に近い正の位置にカウントされること になる。一方でアクセスの頻度が低い場合、DNS キャッシュが切れてから時間が空いて次の アクセスを行うため、横軸の 0 の位置から離れた正の位置にカウントされる。またユーザの割

第 4 章 実験 合は、高頻度アクセスのユーザが少数存在し低頻度アクセスのユーザが多数存在すると仮定す る。するとグラフの立ち上がり付近では高頻度アクセスのユーザが何度もカウントされ、少数 ユーザのカウントが全体に占める割合が高くなり、逆にグラフのテールの部分では低頻度アク セスのユーザが多く、この割合が下がると予想できる。これを検証するために、グラフの立ち 上がりの付近と、指数関数的な減衰が収まったテールの部分についてそれぞれ IP アドレス毎 のカウント数を測定する実験を行う。この追加実験には第 4.3 節で扱ったものと同じデータ、 www.facebook.comのある 24 時間分を用いる。取得するデータはデータ A とデータ B の 2 種 類を用意する。データ A は立ち上がりの付近、横軸が 0 の位置から 120 秒間のものとし、デー タ B はテールの部分、横軸が 1000 の位置から 900 秒間のものとする。  以下の図 4.26 はデータ A とデータ B それぞれのカウント数上位 100 ユーザの、カウント数全 体に対する割合を表したものである。どちらのデータもユニークユーザ数は 1600 程度である。   図 4.26: カウント数全体に対する上位 100 ユーザの割合 データ B に比べデータ A は、カウント数全体に対する上位のユーザの割合が高く推移して いることがわかる。特に上位の数ユーザについては顕著で、データ A のカウント数が最も多 かったユーザは全体の 2.78%を一人で占めていた。そして 100 位付近ではどちらのデータも全 体に対する割合が同程度になっている。次に測定結果をカウント数の多い順に並べ、これを累 積度数分布で表したグラフを図 4.27 に示す。横軸はユニークな IP アドレスの数、すなわちユ

第 4 章 実験 ニークユーザ数であり、縦軸は正規化したカウント数の累積度数である。 図 4.27: カウントの累積度数分布 図 4.26 で示した結果の通り、データ A はデータ B に比べ、カウント数上位の少数ユーザが全 体に対して占める割合が高いことがわかる。このことから本節の始めに予想した通り、第 4.3 節にて結果を示した本手法において、グラフのテールの部分よりも DNS キャッシュが切れた 直後の立ち上がりの付近に高頻度アクセスのユーザは多いという傾向がわかる。

第

5

章

結論

5.1

まとめ

スタブリゾルバでの DNS キャッシュ切れの性質から、あるサービスへのアクセス数を推定 する手法が下田らによって提案されている。本研究ではこの手法を拡張して、User-Agent 毎 にグラフ化を行った。その結果、多くの場合従来の手法と同様の特徴が確認できたが、一部の User-Agentとドメインの組み合わせにおいて従来とは異なる特徴が現れた。

5.2

今後の課題

5.2.1 より多くのデータを用いた実験 第 4.3 節で紹介したグラフは OS もしくは Web ブラウザ毎に集計したものであり、これらの 組み合わせについては紹介できなかった。実験では OS と Web ブラウザの組み合わせについて のグラフも作成したが、データ量が少なく、シェア率の高い一部の組み合わせについてしか特 徴のあるグラフが得られなかった。そのため今回はこれを紹介していない。また第 4.2 節でも 述べたが、LinuxOS についてもデータ量が少なくいい結果が得られなかった。下田らの手法の 精度向上を目的とするならば、これらのようなシェア率の低い User-Agent については考慮に 入れる必要はないかもしれないが、User-Agent 毎の特徴を明らかにするという観点において、 これは今後の課題である。 5.2.2 別地域で収集されたデータへの適用 第 4.1 節でも述べた通り、今回の実験ではあるゲートウェイで取得した数千人規模の利用者に よる DNS と HTTP のトラヒック、2013 年 8 月のある 4 日分のデータセットを用いた。このデー タは Windows と Internet Explorer のシェア率が圧倒的に高い地域のものであったため、All の グラフはこの 2 つの User-Agent の結果に大きな影響を受けている。そのためここからアクセ

第 5 章 結論

ス数の推定を行う場合、この Windows と Internet Explorer 以外の Web ブラウザや OS の挙動 は無視出来てしまう。しかし地域やパケット収集地点によって、OS や Web ブラウザのシェア 率は変化すると考えられる。今回は All のグラフに影響の少なかった User-Agent も、シェア率 が異なれば All のグラフに大きく影響を与える可能性がある。そのような場合に、User-Agent 毎の特徴に着目した本手法を更に活かすことができると考えている。

謝辞

本修士論文を作成するにあたり、日頃よりご指導いただいた早稲田大学基幹理工学部の後藤 滋樹教授に深く感謝いたします。本研究を進めるにあたり NTT ネットワーク基盤技術研究所 の下田晃弘氏には、研究テーマや解析手法に関する助言やデータセットを用いてのプログラム の実行など多大なるご協力をいただきました。深くお礼申し上げます。最後に、後藤研究室の 皆様に感謝いたします。

参考文献

[1] 藤原 和典, 佐藤 聡, 吉田 健一, “ルート DNS サーバへのクエリ数の削減”, 電子情報通信 学会論文誌 B Vol.J98-B No.6, pp.497-508, June, 2013.

[2] BIND — Internet System Consortium https://www.isc.org/downloads/bind/

[3] A. Shimoda, K. Ishibashi, K. Sato, M. Tsujino, T. Inoue, M. Shimura, T. Takebe, K. Taka-hashi, T. Mori, and S. Goto,“Inferring Popularity of Domain Names with DNS Traffic: Exploiting Cache Timeout Heuristics” IEEE Global Communications Conference, Decem-ber 2015, San Diego CA, US.

[4] Post-PRISM, Google Confirms Quietly Moving To Make All Searches Secure, Except For Ad Clicks

http://searchengineland.com/post-prism-google-secure-searches-172487 [5] 「Yahoo!検索」SSL 化のお知らせ

http://docs.yahoo.co.jp/info/notice/150812.html

[6] Paul Albitz, Cricket Liu,高田 広章, 小島 育夫, 小舘 光正, “DNS&BIND (第 4 版)”, オラ イリー・ジャパン, Feb. 2002.

[7] Windowsと Windows 10 - マイクロソフト http://www.microsoft.com/ja-jp/windows

[8] Internet Explorerのダウンロード - Microsoft Windows

http://windows.microsoft.com/ja-jp/internet-explorer/download-ie [9] Chrome - Google

https://www.google.co.jp/chrome/browser/desktop/index.html [10] Firefox browser - Mozilla

参考文献 [11] Twitter https://twitter.com/ [12] Wireshark https://www.wireshark.org/ [13] Yahoo! JAPAN http://www.yahoo.co.jp/ [14] Google https://www.google.co.jp/ [15] サーチエンジン シェア (検索エンジンシェア) http://find.accessup.org/kensaku/access_history.html [16] Facebook https://www.facebook.com/ [17] 会社情報 — Facebook ニュースルーム http://ja.newsroom.fb.com/company-info/ [18] OS X - OS X とは? - Apple http://www.apple.com/jp/osx/ [19] NetMarketShare https://www.netmarketshare.com/ [20] Android — Googleのモバイル OS https://www.android.com/ [21] iOS 9 - Apple http://www.apple.com/ios/ [22] Microsoft Edge - マイクロソフト https://www.microsoft.com/ja-jp/windows/microsoft-edge [23] OS X - Safari - Apple http://www.apple.com/safari/ [24] 1 min TTL in DNS cache https://code.google.com/p/chromium/issues/detail?id=164026

参考文献

[25] Chrome Networking: DNS Prefetch & TCP Preconnect

https://www.igvita.com/2012/06/04/chrome-networking-dns-prefetch-and-tcp-preconnect/