早稲田大学 基幹理工学研究科 5109B084-7 後藤研究室 修士2年 本嶋 悠也

Presentation on theme: "早稲田大学 基幹理工学研究科 5109B084-7 後藤研究室 修士2年 本嶋 悠也"— Presentation transcript:

1 早稲田大学 基幹理工学研究科 5109B084-7 後藤研究室 修士2年 本嶋 悠也
修士論文審査 「IPアドレスの特徴を用いた SVMによるspamメールの判別法」 早稲田大学 基幹理工学研究科 5109B084-7 後藤研究室 修士2年 本嶋 悠也 2011/2/4 修論審査

2 Agenda 研究の背景 研究の目的 既存手法 提案手法 実証実験 実験１ 実験２ まとめ 今後の課題 2011/2/4 修論審査

3 研究の背景 spamメールとは 問題点 受信者の意図に関わらず、自動的に送られてくるメール
不特定多数の相手に送られる、内容として広告・宣伝・誘導・詐欺等の性質が強いメール 問題点 メール整理に伴う時間の浪費・受信者への精神的負担 重要なメールの見落とし ネットワーク資源及びサーバ資源の浪費 サーバ資源の浪費に伴うメール配送遅延 マルウェアへの感染 2011/2/4 修論審査

4 研究の背景 spamメールは長年問題視されている
メールのヘッダや本文に基づく対策手法は 精度の良いものが存在しているが、その計算量によって配送遅延の原因となる メールのヘッダや本文によらない対策手法を提案する 2011/2/4 修論審査

5 研究の目的 メールのヘッダや本文によらず、メール送信者の IPアドレスでspamメール送信者か否かを判別 する手法をSVM (Support Vector Machine)を用いて実現する。 2011/2/4 修論審査

6 既存手法 2008年度 卒業論文 「IPアドレスの特徴を用いたspamメール送信者判別方法」 ナイーブベイズ分類器を利用
各クラスにおける特徴の生起確率を用いる 利用する特徴：BGP Prefix, AS番号, 国番号, PTR, OS 表１：既存手法における判別精度 FNR (％) FPR (％) 0.346 ※FPR: False Positive Ratio = legitをspammerと判別した数 / legit数 　 FNR: False Negative Ratio = spammerをlegitと判別した数 / spammer数 2011/2/4 修論審査

7 例：133.9.81.1 → vox3.goto.info.waseda.ac.jp
既存手法 利用する特徴 BGP Prefix： IPアドレスに対応する、AS番号に関連付けられたネットワーク AS番号： そのIPアドレスが属するネットワークのAS番号 国番号： そのIPアドレスを割り当てられている国 PTRレコードの有無 逆引きドメイン名が設定されているか否か OS IPアドレスから判定された、ホストのOS 例：早稲田大学 /16 例：早稲田大学：AS17956 例：JP, US, CN, … 補足資料：BGP Prefix, AS番号, 国番号, PTRレコード, OS 例： → vox3.goto.info.waseda.ac.jp 例：Windows, Linux, Mac, … 2011/2/4 修論審査

8 提案手法 IPアドレスから求めることのできる特徴を特徴ベクトルとしてSVMに適用し、spamメール送信者を判別する
既存手法を踏まえつつ、新しい特徴を導入する カテゴリカルでない特徴 逆引きドメイン名に着目した特徴 SVM (Support Vector Machine) 教師あり機械学習の一つ カーネル関数により、非線形な問題にも適用可能 ※カテゴリカルな特徴： 　順序性、等間隔性を持たない特徴 2011/2/4 修論審査

9 提案手法 利用する特徴 (既存手法と同じ) BGP Prefix AS番号 国番号 PTRレコードの有無 OS 2011/2/4 修論審査

10 提案手法 利用する特徴 （カテゴリカルでない特徴） メール送信回数：そのIPアドレスからメールが送られた回数
spamメール送信回数：そのIPアドレスから送られたメールのうち　spamメールであると判定されたものの件数 hamメール送信回数：そのIPアドレスから送られたメールのうち、hamメール(正常なメール)であると判定されたものの件数 グレイリスト：そのIPアドレスから送られたメールの中で、グレイリストで受信が拒否されたものの件数 SMTPセッション：SMTPセッションを開始したが、メールが送られずにセッションを開始しただけで終わったものの件数 活動期間：1ヶ月の間にメールを送った日が何日間あったか 予め、送られてきたメールの件数等を、IPアドレスごとに集計してあるものとする 補足資料：グレイリスト ナイーブベイズ分類器では特徴の生起確率を用いるため、カテゴリカルでない特徴を導入することが難しい 2011/2/4 修論審査

11 提案手法 利用する特徴 (逆引きドメイン名に着目した特徴) 逆引きドメイン名に含まれる数字の個数 S25Rスパム対策方式のルール1
逆引きドメイン名に含まれる数字の個数が、対応するIPアドレス の数字の個数以上か否か S25Rスパム対策方式のルール1 逆引きドメイン名の最下位の名前が、数字以外の文字列で分断 された二つ以上の数字列を含むか否か 補足資料：逆引きドメイン名 補足資料：IPアドレス形式のドメイン名 補足資料：S25R ※S25Rスパム対策方式 浅見秀雄が考案した手法。逆引きドメイン名の特徴に基づいて作られたルールを用いて、メール送信元がメール中継サーバかエンドユーザかを判断する。エンドユーザと思われるクライアントから送られたメールをspamメールと判断する。 2011/2/4 修論審査

12 提案手法 特徴ベクトル カテゴリカルな特徴 カテゴリカルでない特徴 その特徴を持つか否か(0 or 1)で与える
その特徴の値を[0,1]にスケーリングして与える 2011/2/4 修論審査

13 提案手法 スケーリング 数値の範囲の大きな特徴が数値の範囲の小さい特徴を支配してしまう場合がある 各特徴ごとに、
　　として[0,1]にスケーリングする 2011/2/4 修論審査

14 実証実験 実験１：カテゴリカルでない特徴を導入した場合の 判別率の評価 実験２：逆引きドメイン名に着目した特徴を導入した 場合の判別率の評価
実験１：カテゴリカルでない特徴を導入した場合の　　 　　　　　　 判別率の評価 実験２：逆引きドメイン名に着目した特徴を導入した 　　　　　　 場合の判別率の評価 実験結果の評価 FPR: False Positive Ratio = 　　　　legitをspammerと判別した数 / legit数 FNR: False Negative Ratio = 　　　　spammerをlegitと判別した数 / spammer数 　　　として評価する 交差確認法 (cross validation)を用いる 2011/2/4 修論審査

15 実験に用いるデータ 協力者に提供して頂いた、1ヶ月間のSMTPログ このSMTPログではメールは分類済み
　　(spam / ham / greylisted / session) ログを集計し、spammer,legitらしいIPアドレスを抽出 spammer : spamメール送信者 legit : 正常なメール送信者 IPアドレスごとに特徴を求め、特徴ベクトルを作成する IPアドレスの件数 サンプリング 表２：SMTPログから抽出したIPアドレスの件数 legit spammer 3577 514360 legit spammer 3577 ランダムサンプリング 2011/2/4 修論審査

16 表３：カテゴリカルでない特徴を導入した場合の判別率の変化
実験１の結果 カテゴリカルでない特徴を導入した場合の判別率 表３：カテゴリカルでない特徴を導入した場合の判別率の変化 FPR (%) FNR(%) ① 2.8432 1.1997 ② 1.7412 1.1086 ①カテゴリカルな特徴のみの場合 ②カテゴリカルでない特徴含む場合 FPR, FNRが共に改善された ※FPR: False Positive Ratio = legitをspammerと判別した数 / legit数 　 FNR: False Negative Ratio = spammerをlegitと判別した数 / spammer数 2011/2/4 修論審査

17 表４：逆引きドメイン名に着目した特徴を導入した場合の判別率の変化
実験２の結果 逆引きドメイン名に着目した特徴を導入した場合の判別率 表４：逆引きドメイン名に着目した特徴を導入した場合の判別率の変化 FPR (%) FNR(%) ② 1.7412 1.1086 ③ 1.2327 0.7426 ②逆引きドメイン名に着目した特徴を含まない場合　　　※実験１の②と同条件 ③逆引きドメイン名に着目した特徴を含む場合 FPR, FNRがさらに改善された ※FPR: False Positive Ratio = legitをspammerと判別した数 / legit数 　 FNR: False Negative Ratio = spammerをlegitと判別した数 / spammer数 2011/2/4 修論審査

18 まとめ IPアドレスから求めることのできる特徴をSVMに 適用し、メール送信者がspamメール送信者か否かを判別する手法を提案した
カテゴリカルでない特徴、逆引きドメイン名に着目した特徴の導入により判別率を向上させることができた 2011/2/4 修論審査

19 今後の課題 判別に有効な新しい特徴の検討 訓練量による判別率への影響 提案手法で用いた特徴の他にも、判別に有効な特徴が存在する可能性がある
訓練データの量が増えた場合にどうなるか spammerと同等の件数のlegitを用意する 新しい特徴： カテゴリカルでない特徴も扱えることから、統計的なデータ？ スパマーのドメイン名の特徴を探る：時折スラッシュを含むドメインがある 2011/2/4 修論審査

20 ご清聴ありがとうございました 2011/2/4 修論審査

21 2011/2/4 修論審査

22 補足資料 2011/2/4 修論審査

23 spamメール spamメールとは 問題点 受信者の意図に関わらず、自動的に送られてくるメール
不特定多数の相手に送られる、内容として広告・宣伝・誘導・詐欺等の性質が強いメール 問題点 メール整理に伴う時間の浪費・受信者への精神的負担 重要なメールの見落とし ネットワーク資源及びサーバ資源の浪費 サーバ資源の浪費に伴うメール配送遅延 マルウェアへの感染 2011/2/4 修論審査

24 BGP Prefix BGP PrefixとAS番号の対応表は、「Route Views Archive Project」のものを整形して使用 アメリカ、オレゴン大学が公開しているBGP経路情報。フルルートデータが公開されている。 2011/2/4 修論審査

25 AS番号 BGP Prefix同様、対応表はRoute Views Archive Projectのものを使用
AS番号はBGPで経路制御を行うASに割り当てられる 2011/2/4 修論審査

26 AS (Autonomous System)
大規模なTCP/IPネットワークにおいて、各組織が保有・運用する自律したネットワーク インターネットはマクロに見ると、ASを相互に接続した形態となっている AS間の経路制御に使われるプロトコルがBGP (Border Gateway Protocol) AS間の境界にあるルータは経路情報を交換する 2011/2/4 修論審査

27 国番号 MaxMind社のGeoIPというデータベースを使用。GeoIPはIPアドレスを地理情報にマッピングした データベースである。
2011/2/4 修論審査

28 OS passive fingerprintingの実装の一つであるp0fというツールを用いてOSを判定
passive fingerprintingは、OSによってTCPパケットに記載するヘッダのデフォルト値の組み合わせが異なるという性質を利用し、TCPパケットに記録されたヘッダの各属性値の組み合わせから、そのパケットを送出したホストのOSを判定する技術 p0fでは、事前に集めた各OSと属性値の組み合わせから構成されるテーブルを用意し、パッシブ測定によって得たTCPヘッダの属性とテーブルを比較することにより、OSを判定する 2011/2/4 修論審査

29 グレイリスト spamメール対策手法の一つ
メール受信の際に送信元の情報をデータベースに登録し、メールは受信せずに一時的エラーを示すステータスコードを返す。その後、一定時間以上経ってから同じサーバからメールが再送された場合に受信する spamメールを送信するサーバは、大量のメールを短時間に送信することを重視して、一時的エラーに対して再送を行わないという特徴を利用している 2011/2/4 修論審査

30 逆引きドメイン名 DNSを用いてIPアドレスからドメイン名に変換する ことを逆引きという 逆引きによって得られるドメイン名が逆引きドメイン名
ISPによって自動的に付加されているIPアドレスも存在する ドメイン名がIPアドレス形式のものはその可能性が高い　例： example.com 2011/2/4 修論審査

31 S25Rスパム対策方式 浅見秀雄が考案したspamメール対策手法 ルール 0:逆引き失敗
1:逆引きFQDNの最下位の名前が、数字以外の文字列で分断された二つ以上の文字列を含む 2:逆引きFQDNの最下位の名前が、5個以上連続する数字を含む 3:逆引きFQDNの上位3階層を除き、最下位または下位から2番目の名前が数字で始まる 4:逆引きFQDNの最下位の名前が数字で終わり、かつ下位から2番目の名前が、1個のハイフンで分断された二つ以上の数字列を含む 5:逆引きFQDNが5階層以上で、下位2階層の名前がともに数字で終わる 6:逆引きFQDNの最下位の名前が「dhcp」、「dialup」、「ppp」、またはDSL系の名前で始まり、かつ数字を含む 2011/2/4 修論審査

32 カテゴリカルでない特徴の導入 スケーリング 数値の範囲の大きな特徴が数値の範囲の小さい特徴を支配してしまう場合がある 各特徴ごとに、
　　として[0,1]にスケーリングする 2011/2/4 修論審査

33 訓練データの偏りに対する対策 サンプリング 正例、負例の数に偏りがある場合、予測精度が低下する
spammerの件数をlegitと同じ数に減らす ランダムサンプリング 表：サンプリング前後の判別率の変化 legit数 spammer数 FPR (%) FNR(%) サンプリング前 3577 514360 サンプリング後 ※FPR: False Positive Ratio = legitをspammerと判別した数 / legit数 　 FNR: False Negative Ratio = spammerをlegitと判別した数 / spammer数 2011/2/4 修論審査

34 SVMの分類結果を確率値に近似 SVMの出力をシグモイド関数に当てはめることで確率値へのよい近似が得られることは実験的に示されている
John Platt. “Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods” In Advances in Large Margin Classifiers. MIT Press, 1999. 2011/2/4 修論審査 34

35 交差確認法 10-fold cross validation(10分割交差確認法) データを10個に分ける
分けたうちの一つを除外した、9個のデータを使ってパラメータを推定 除外するデータを毎回変えて、推定を10回繰り返す 10回の推定の平均値で評価する 統計学において、仮説検定に用いられる手法 2011/2/4 修論審査

36 各属性の生起確率の例 (BGP) spammer legit BGP Prefix 生起確率 1 83.0.0.0/11
/20 2 /13 /21 3 /14 /20 4 /16 /17 5 /16 /24 6 /16 /16 7 /10 /21 8 /16 /16 9 /11 /13 10 /16 /16 2011/2/4 修論審査

37 各属性の生起確率の例 (AS番号) spammer legit AS番号 生起確率 1 9121 0.092810483 7506
2 4837 4713 3 4134 2514 4 6147 23820 5 7470 2497 6 19262 4694 7 3269 15169 8 22927 9370 9 7738 714 10 5617 4732 2011/2/4 修論審査

38 各属性の生起確率の例 (国情報) spammer legit 国情報 生起確率 1 CN 0.098390233 JP
2 TR US 3 GB 4 RU CA 5 ES FR 6 DE 7 BR 8 CO KR 9 AR NL 10 PE IT 2011/2/4 修論審査

39 各属性の生起確率の例 (RDNS) spammer legit DNS逆引き 生起確率 1 0.677844311 0.952194576
2011/2/4 修論審査

40 各属性の生起確率の例 (OS) spammer legit OS 生起確率 1 Windows 0.630855821 Linux
2 Bob FreeBSD 3 UNKNOWN 4 Paul Solaris 5 6 Oscar 7 HP-UX 8 MacOS OpenBSD 9 BSD/OS 10 NetBSD NetCache 2011/2/4 修論審査

41 実験データの作成 特徴を番号に対応付ける表を作成 BGP Prefix～OSについては カテゴリカルデータとして扱い、個別に番号を振る
順序性・等間隔性を持たない valueは 0 or 1 [対応表] 1:messages 2:spam 3:ham 4:greylisted 5:session 6:active days 7:bgp prefix /24 8:bgp prefix /20 9:bgp prefix /20 ～中略～ 59305:asn 8434 59306:asn 5006 59307:asn 42517 67951:country code DJ 67952:country code JM 67953:country code PG 68160:rdns 68161:os SymbianOS 68162:os OpenBSD ～後略～ 2011/2/4 修論審査 41

42 実験データの作成 先の表に基づいてフォーマットを変更 42 2011/2/4 修論審査 [変更前] [変更後]
IP, messages, spam, ham, greylisted, session, active days, bgp prefix, asn, country code, rdns, os ,11,0,11,60,0,2, /9,3356,US,0,Windows ,10,0,10,34,0,3, /9,3356,US,1,Windows ,10,0,10,26,0,3, /24,14267,US,1,Oscar [変更後] 1 1:11 2:0 3:11 4:60 5:0 6:2 3938: : : : :1 # 1 1:10 2:0 3:10 4:34 5:0 6: : : : : :1 # 1 1:10 2:0 3:10 4:26 5:0 6: : : : : :1 # 2011/2/4 修論審査 42

43 SVMの出力 実験結果 浮動小数点数で得られる 0以上ならlegit, 0未満ならspammer 43 2011/2/4 修論審査
[実験結果の一部] ～中略～ ～後略～ ※legit:正常なメール送信者 　 spammer: spamメール送信者 2011/2/4 修論審査 43

44 SVM (Support Vector Machine)
教師あり機械学習 マージン最大化 非線形な問題でも分類可能 ソフトマージン カーネルトリック w・x+b=0 y=1 マージン y=-1 2011/2/4 2010/11/30 第一回修論進捗発表 修論審査 44

45 2011/2/4 修論審査

46 2011/2/4 修論審査

47 訓練データの偏りに対する対策 アンダーサンプリング 訓練データ中のspammerの数を減らしてlegitの数に合わせる
表３：サンプリング前後の判別率の変化 legit数 spammer数 判別精度 (%) FPR (%) FNR(%) サンプリング前 3577 514360 サンプリング後 ※FPR: False Positive Ratio = legitをspammerと判別した数 / legit数 　 FNR: False Negative Ratio = spammerをlegitと判別した数 / spammer数 FPRがかなり改善された 2011/2/4 修論審査

48 カテゴリカルでないデータも含めた学習 カテゴリカルなデータ カテゴリカルでないデータ
BGP Prefix, AS番号, 国番号, OS, PTRレコードの有無 カテゴリカルでないデータ messages, spam, ham, greylisted, session, active days 値の大きさに引きずられてまともな結果がでなかったので、使用しないでいた 数値の範囲の大きな特徴が数値の範囲の小さい特徴を支配してしまうので、そのような特徴を用いる場合は　　スケーリングしないと使い物にならないとの指摘 2011/2/4 修論審査

49 カテゴリカルでないデータも含めた学習 2011/2/4 修論審査
1 1:10 2:0 3:10 4:34 5:0 6: : : : : :1 1 1:25 2:0 3:25 4:33 5:0 6: : : : : :1 1 1:21 2:0 3:21 4:19 5:0 6: : : : : :1 1 1: :0 3: : :0 6: : : : : :1 1 1: :0 3: : :0 6: : : : : :1 1 1: :0 3: : :0 6: : : : : :1 2011/2/4 修論審査

50 カテゴリカルでないデータも含めた学習 カテゴリカルでないデータ 判別精度 (%) FPR (%) FNR(%) ① 99.85984
表４：カテゴリカルでないデータを含めた場合の判別率の変化 判別精度 (%) FPR (%) FNR(%) ① ② ③ ④ ①カテゴリカルなデータのみ、サンプリングなし ②カテゴリカルでないデータ有り、サンプリングなし ③カテゴリカルなデータのみ、サンプリング有り ④カテゴリカルでないデータ有り、スケーリング有り 2011/2/4 修論審査

51 2011/2/4 修論審査

52 （再掲）実験2 内容と結果 使用する特徴を限定してSVMを適用、様子を見る messages～active daysの特徴を省く
FPRが高く、FNRが非常に低い 表１：適用したカーネル関数とその判別率 カーネル関数 判別精度(%) FPR (%) FNR (%) 線形分離 (default) 多項式カーネル RBFカーネル シグモイドカーネル 訓練データの偏りによるもの ※FPR: False Positive Ratio = legitをspammerと判別した数 / legit数 　 FNR: False Negative Ratio = spammerをlegitと判別した数 / spammer数 spammer数は legit数の約150倍 2011/2/4 修論審査 52

53 パラメータチューニング SVMではカーネルパラメータの選択が重要 LIBSVM付属のツールによるパラメータ探索 特にRBFカーネルでは顕著
上手くパラメータを設定できればかなり有効 LIBSVM付属のツールによるパラメータ探索 grid.py LIBSVMでも推奨されている 表２：パラメータ適用前の判別率 カーネル関数 判別精度(%) FPR (%) FNR (%) RBFカーネル ※FPR: False Positive Ratio = legitをspammerと判別した数 / legit数 　 FNR: False Negative Ratio = spammerをlegitと判別した数 / spammer数 表３：パラメータ適用後の判別率 カーネル関数 判別精度(%) FPR (%) FNR (%) RBFカーネル 2010/11/30 2011/2/4 第一回修論進捗発表 修論審査 53

54 確率値に近似した結果 確率値での出力も可能 度合いで判断することができる legitらしさ、spammerらしさ
閾値を設定してフィルタリング -w オプションで 重みづけした結果の 分析に利用 オプション未使用 オプション使用 label 1 -1 label 1 -1 2011/2/4 2010/11/30 修論審査 第一回修論進捗発表 54

55 2011/2/4 2010/11/30 修論審査 第一回修論進捗発表 55

56 featureは整数で表されるので、各特徴に番号を割り当てる必要がある
実験1 内容 (1/3) 卒論のときに利用していたデータをSVMに適用 森さんに提供して頂いたSMTPログ (2008年4月～7月) SVM-lightというモジュールを利用 SVM-lightで利用できるようにフォーマットを変更 10-fold cross validation [SVM-lightの学習データ・テストデータのフォーマット] ＜line＞ .=. ＜target＞ ＜feature＞:＜value＞ ＜feature＞:＜value＞ ...＜feature＞:＜value＞ ＜target＞ .=. +1 | -1 | 0 | ＜float＞ ＜feature＞ .=. ＜integer＞ | 'qid ' ＜value＞ .=. ＜float＞ SVM-lightはアメリカのコーネル大学の准教授、Thorsten Joachims により作成された ・大きなデータセットを高速に処理可能 ・kernel.hで新規のカーネルを定義可能 クラス 特徴量のインデックス 特徴量 featureは整数で表されるので、各特徴に番号を割り当てる必要がある 2010/11/30 2011/2/4 第一回修論進捗発表 修論審査 56