修士論文審査 「IPアドレスの特徴を用いた SVMによるspamメールの判別法」 早稲田大学 基幹理工学研究科 5109B084-7 後藤研究室 修士2年 本嶋 悠也 2011/2/4 修論審査 1 Agenda 1. 2. 3. 4. 5. 研究の背景 研究の目的 既存手法 提案手法 実証実験 a. 実験１ b. 実験２ 6. まとめ 7. 今後の課題 2011/2/4 修論審査 2 研究の背景 spamメールとは 受信者の意図に関わらず、自動的に送られてくるメール 不特定多数の相手に送られる、内容として広告・宣伝・誘導・詐 欺等の性質が強いメール 問題点 メール整理に伴う時間の浪費・受信者への精神的負担 重要なメールの見落とし ネットワーク資源及びサーバ資源の浪費 サーバ資源の浪費に伴うメール配送遅延 マルウェアへの感染 2011/2/4 修論審査 3 研究の背景 spamメールは長年問題視されている メールのヘッダや本文に基づく対策手法は 精度の良いものが存在しているが、その計算量 によって配送遅延の原因となる メールのヘッダや本文によらない対策手法を提案する 2011/2/4 修論審査 4 研究の目的 メールのヘッダや本文によらず、メール送信者の IPアドレスでspamメール送信者か否かを判別 する手法をSVM (Support Vector Machine) を用いて実現する。 2011/2/4 修論審査 5 既存手法 2008年度 卒業論文 「IPアドレスの特徴を用い たspamメール送信者判別方法」 ナイーブベイズ分類器を利用 IPベースでspamメール送信者か否か判別 各クラスにおける特徴の生起確率を用いる 利用する特徴：BGP Prefix, AS番号, 国番号, PTR, OS 表１：既存手法における判別精度 FNR (％) 2008-04 0.346 FPR (％) 5.903926 ※FPR: False Positive Ratio = legitをspammerと判別した数 / legit数 FNR: False Negative Ratio = spammerをlegitと判別した数 / spammer数 2011/2/4 修論審査 6 既存手法 利用する特徴 例：早稲田大学 133.9.0.0/16 BGP Prefix： IPアドレスに対応する、AS番号に関連付けられたネットワーク AS番号： 例：早稲田大学：AS17956 そのIPアドレスが属するネットワークのAS番号 国番号： 例：JP, US, CN, … そのIPアドレスを割り当てられている国 PTRレコードの有無 例：133.9.81.1 → vox3.goto.info.waseda.ac.jp 逆引きドメイン名が設定されているか否か OS 例：Windows, Linux, Mac, … IPアドレスから判定された、ホストのOS 2011/2/4 修論審査 7 提案手法 IPアドレスから求めることのできる特徴を特徴ベクトル としてSVMに適用し、spamメール送信者を判別する IPアドレスベースで判別 既存手法を踏まえつつ、新しい特徴を導入する カテゴリカルでない特徴 逆引きドメイン名に着目した特徴 ※カテゴリカルな特徴： 順序性、等間隔性を持たない特徴 SVM (Support Vector Machine) 教師あり機械学習の一つ カーネル関数により、非線形な問題にも適用可能 2011/2/4 修論審査 8 提案手法 利用する特徴 (既存手法と同じ) BGP Prefix AS番号 国番号 PTRレコードの有無 OS 2011/2/4 修論審査 9 提案手法 利用する特徴 （カテゴリカルでない特徴） メール送信回数：そのIPアドレスからメールが送られた回数 spamメール送信回数：そのIPアドレスから送られたメールのうち spamメールであると判定されたものの件数 hamメール送信回数：そのIPアドレスから送られたメールのうち、 hamメール(正常なメール)であると判定されたものの件数 グレイリスト：そのIPアドレスから送られたメールの中で、グレイリ ストで受信が拒否されたものの件数 SMTPセッション：SMTPセッションを開始したが、メールが送られ ずにセッションを開始しただけで終わったものの件数 活動期間：1ヶ月の間にメールを送った日が何日間あったか ナイーブベイズ分類器では特徴の生起確率を用いるため、カテゴリ カルでない特徴を導入することが難しい 2011/2/4 修論審査 10 提案手法 利用する特徴 (逆引きドメイン名に着目した特徴) 逆引きドメイン名に含まれる数字の個数 逆引きドメイン名に含まれる数字の個数が、対応するIPアドレス の数字の個数以上か否か S25Rスパム対策方式のルール1 逆引きドメイン名の最下位の名前が、数字以外の文字列で分断 された二つ以上の数字列を含むか否か ※S25Rスパム対策方式 浅見秀雄が考案した手法。逆引きドメイン名の特徴に基づいて作られた ルールを用いて、メール送信元がメール中継サーバかエンドユーザかを 判断する。エンドユーザと思われるクライアントから送られたメールを spamメールと判断する。 2011/2/4 修論審査 11 提案手法 特徴ベクトル カテゴリカルな特徴 その特徴を持つか否か(0 or 1)で与える カテゴリカルでない特徴 その特徴の値を[0,1]にスケーリングして与える 2011/2/4 修論審査 12 提案手法 スケーリング 数値の範囲の大きな特徴が数値の範囲の小さい特徴 を支配してしまう場合がある 各特徴ごとに、 ((その特徴の特徴量)－(特徴量の最小値)) ((特徴量の最大値) －(特徴量の最小値)) として[0,1]にスケーリングする 2011/2/4 修論審査 13 実証実験 実験１：カテゴリカルでない特徴を導入した場合の 判別率の評価 実験２：逆引きドメイン名に着目した特徴を導入した 場合の判別率の評価 実験結果の評価 FPR: False Positive Ratio = legitをspammerと判別した数 / legit数 FNR: False Negative Ratio = spammerをlegitと判別した数 / spammer数 として評価する 交差確認法 (cross validation)を用いる 2011/2/4 修論審査 14 実験に用いるデータ 協力者に提供して頂いた、1ヶ月間のSMTPログ このSMTPログではメールは分類済み (spam / ham / greylisted / session) ログを集計し、spammer,legitらしいIPアドレスを抽出 spammer : spamメール送信者 legit : 正常なメール送信者 IPアドレスごとに特徴を求め、特徴ベクトルを作成する 表２：SMTPログから抽出したIPアドレスの件数 legit 3577 2011/2/4 legit spammer 514360 3577 spammer 3577 ランダムサンプリング 修論審査 15 実験１の結果 カテゴリカルでない特徴を導入した場合の判別率 表３：カテゴリカルでない特徴を導入した場合の判別率の変化 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 修論審査 16 実験２の結果 逆引きドメイン名に着目した特徴を導入した場合の判別率 表４：逆引きドメイン名に着目した特徴を導入した場合の判別率の変化 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 修論審査 17 まとめ IPアドレスから求めることのできる特徴をSVMに 適用 し、メール送信者がspamメール送信者か否かを判別 する手法を提案した ベイズ分類器と違い、SVMではカテゴリカルでない 特徴の導入が容易である カテゴリカルでない特徴、逆引きドメイン名に着目した 特徴の導入により判別率を向上させることができた 2011/2/4 修論審査 18 今後の課題 判別に有効な新しい特徴の検討 提案手法で用いた特徴の他にも、判別に有効な特徴 が存在する可能性がある 訓練量による判別率への影響 訓練データの量が増えた場合にどうなるか spammerと同等の件数のlegitを用意する 2011/2/4 修論審査 19 ご清聴ありがとうございました 2011/2/4 修論審査 20 2011/2/4 修論審査 21 補足資料 2011/2/4 修論審査 22 spamメール spamメールとは 受信者の意図に関わらず、自動的に送られてくるメール 不特定多数の相手に送られる、内容として広告・宣伝・誘導・詐 欺等の性質が強いメール 問題点 メール整理に伴う時間の浪費・受信者への精神的負担 重要なメールの見落とし ネットワーク資源及びサーバ資源の浪費 サーバ資源の浪費に伴うメール配送遅延 マルウェアへの感染 2011/2/4 修論審査 23 BGP Prefix BGP PrefixとAS番号の対応表は、「Route Views Archive Project」のものを整形して 使用 2011/2/4 修論審査 24 AS番号 BGP Prefix同様、対応表はRoute Views Archive Projectのものを使用 AS番号はBGPで経路制御を行うASに割り当 てられる 2011/2/4 修論審査 25 AS (Autonomous System) 大規模なTCP/IPネットワークにおいて、各組織 が保有・運用する自律したネットワーク インターネットはマクロに見ると、ASを相互に接続した 形態となっている AS間の経路制御に使われるプロトコルがBGP (Border Gateway Protocol) AS間の境界にあるルータは経路情報を交換する 2011/2/4 修論審査 26 国番号 MaxMind社のGeoIPというデータベースを使用。 GeoIPはIPアドレスを地理情報にマッピングした データベースである。 2011/2/4 修論審査 27 OS passive fingerprintingの実装の一つであるp0fと いうツールを用いてOSを判定 passive fingerprintingは、OSによってTCPパケットに記 載するヘッダのデフォルト値の組み合わせが異なるという 性質を利用し、TCPパケットに記録されたヘッダの各属性 値の組み合わせから、そのパケットを送出したホストのOS を判定する技術 p0fでは、事前に集めた各OSと属性値の組み合わせから 構成されるテーブルを用意し、パッシブ測定によって得た TCPヘッダの属性とテーブルを比較することにより、OSを 判定する 2011/2/4 修論審査 28 グレイリスト spamメール対策手法の一つ メール受信の際に送信元の情報をデータベースに 登録し、メールは受信せずに一時的エラーを示す ステータスコードを返す。その後、一定時間以上 経ってから同じサーバからメールが再送された場 合に受信する spamメールを送信するサーバは、大量のメール を短時間に送信することを重視して、一時的エラ ーに対して再送を行わないという特徴を利用して いる 2011/2/4 修論審査 29 逆引きドメイン名 DNSを用いてIPアドレスからドメイン名に変換する ことを逆引きという 逆引きによって得られるドメイン名が逆引きドメイン名 逆引きを設定していないIPアドレスも存在する ISPによって自動的に付加されているIPアドレスも存在する ドメイン名がIPアドレス形式のものはその可能性が高い 例：192.168.0.1.example.com 2011/2/4 修論審査 30 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 修論審査 31 カテゴリカルでない特徴の導入 スケーリング 数値の範囲の大きな特徴が数値の範囲の小さい特徴 を支配してしまう場合がある 各特徴ごとに、 ((その特徴の特徴量)－(特徴量の最小値)) ((特徴量の最大値) －(特徴量の最小値)) として[0,1]にスケーリングする 2011/2/4 修論審査 32 訓練データの偏りに対する対策 サンプリング 正例、負例の数に偏りがある場合、予測精度が低下する spammerの件数をlegitと同じ数に減らす ランダムサンプリング 表：サンプリング前後の判別率の変化 legit数 spammer数 FPR (%) FNR(%) サンプリング前 3577 514360 12.57241799 0.05365505 サンプリング後 3577 3577 2.843188521 1.199672872 ※FPR: False Positive Ratio = legitをspammerと判別した数 / legit数 FNR: False Negative Ratio = spammerをlegitと判別した数 / spammer数 2011/2/4 修論審査 33 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 交差確認法 10-fold cross validation(10分割交差確認法) 1. データを10個に分ける 2. 分けたうちの一つを除外した、9個のデータを使って パラメータを推定 3. 除外するデータを毎回変えて、推定を10回繰り返す 4. 10回の推定の平均値で評価する 2011/2/4 修論審査 35 各属性の生起確率の例 (BGP) spammer BGP Prefix legit 生起確率 BGP Prefix 生起確率 1 83.0.0.0/11 0.012366825 210.157.16.0/20 0.045848476 2 60.16.0.0/13 0.009378645 202.72.48.0/21 0.025719877 3 221.200.0.0/14 0.009291158 211.125.80.0/20 0.024042494 4 190.42.0.0/16 0.005385333 59.106.0.0/17 0.023483366 5 190.40.0.0/16 0.005150089 17.254.6.0/24 0.017892088 6 201.240.0.0/16 0.004932343 210.150.0.0/16 0.013139502 7 86.128.0.0/10 0.004638774 66.163.168.0/21 0.012300811 8 201.230.0.0/16 0.004391866 202.218.0.0/16 0.011182555 9 90.192.0.0/11 0.003830002 125.200.0.0/13 0.009225608 10 190.43.0.0/16 0.003769733 202.248.0.0/16 0.008946044 2011/2/4 修論審査 36 各属性の生起確率の例 (AS番号) spammer AS番号 legit 生起確率 AS番号 生起確率 1 9121 0.092810483 7506 0.072407045 2 4837 0.042635508 4713 0.071009226 3 4134 0.03673886 2514 0.042773274 4 6147 0.032210903 23820 0.034386357 5 7470 0.020983358 2497 0.033547666 6 19262 0.020178474 4694 0.033268102 7 3269 0.017063924 15169 0.033268102 8 22927 0.017011432 9370 0.032708974 9 7738 0.016595381 714 0.023483366 10 5617 0.015596081 4732 0.021805983 2011/2/4 修論審査 37 各属性の生起確率の例 (国情報) spammer 国情報 legit 生起確率 国情報 生起確率 1 CN 0.098390233 JP 0.668157674 2 TR 0.093220701 US 0.241543193 3 US 0.075291625 GB 0.011462119 4 RU 0.052846256 CA 0.010902991 5 ES 0.05135897 FR 0.00866648 6 GB 0.048143324 DE 0.007268661 7 BR 0.047472587 CN 0.004473022 8 CO 0.045133758 KR 0.004193458 9 AR 0.035484874 NL 0.00363433 10 PE 0.032759157 IT 0.003354767 2011/2/4 修論審査 38 各属性の生起確率の例 (RDNS) spammer DNS逆引き legit 生起確率 DNS逆引き 生起確率 1 1 0.677844311 1 0.952194576 2 0 0.322155689 0 0.047805424 2011/2/4 修論審査 39 各属性の生起確率の例 (OS) spammer OS legit 生起確率 OS 生起確率 1 Windows 0.630855821 Linux 0.457366508 2 Bob 0.302910413 FreeBSD 0.14984624 3 0.028491718 UNKNOWN 0.138384121 4 Paul 0.018195427 Solaris 0.109868605 5 UNKNOWN 0.012392099 Windows 0.070170534 6 Linux 0.003365347 Oscar 0.041655018 7 FreeBSD 0.002130803 HP-UX 0.021246855 8 MacOS 9 Solaris 0.000367447 BSD/OS 0.001956947 10 NetBSD 0.000202193 NetCache 0.001677383 2011/2/4 0.00092931 OpenBSD 修論審査 0.002516075 40 実験データの作成 特徴を番号に対応付ける表を作成 BGP Prefix～OSについては カテゴリカルデータとして扱い、個別に 番号を振る 順序性・等間隔性を持たない valueは 0 or 1 2011/2/4 修論審査 [対応表] 1:messages 2:spam 3:ham 4:greylisted 5:session 6:active days 7:bgp prefix 201.221.197.0/24 8:bgp prefix 119.235.0.0/20 9:bgp prefix 71.13.80.0/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 ～後略～ 41 実験データの作成 先の表に基づいてフォーマットを変更 [変更前] IP, messages, spam, ham, greylisted, session, active days, bgp prefix, asn, country code, rdns, os 4.21.175.95,11,0,11,60,0,2,4.0.0.0/9,3356,US,0,Windows 8.7.218.53,10,0,10,34,0,3,8.0.0.0/9,3356,US,1,Windows 12.11.148.84,10,0,10,26,0,3,12.11.148.0/24,14267,US,1,Oscar [変更後] 1 1:11 2:0 3:11 4:60 5:0 6:2 3938:1 61094:1 68135:1 68160:0 68173:1 #4.21.175.95 1 1:10 2:0 3:10 4:34 5:0 6:3 37815:1 61094:1 68135:1 68160:1 68173:1 #8.7.218.53 1 1:10 2:0 3:10 4:26 5:0 6:3 49865:1 63130:1 68135:1 68160:1 68167:1 #12.11.148.84 2011/2/4 修論審査 42 SVMの出力 実験結果 [実験結果の一部] 浮動小数点数で得られる 0以上ならlegit, 0未満ならspammer ※legit:正常なメール送信者 spammer: spamメール送信者 2011/2/4 修論審査 28.208991 3.5107295 1.1482799 ～中略～ -1.000785 -2.0499438 -1.0010235 ～後略～ 43 SVM (Support Vector Machine) 教師あり機械学習 マージン最大化 非線形な問題でも分類可能 ソフトマージン カーネルトリック w・x+b=0 y=1 マージン y=-1 2011/2/4 2010/11/30 第一回修論進捗発表 修論審査 44 2011/2/4 修論審査 45 2011/2/4 修論審査 46 訓練データの偏りに対する対策 アンダーサンプリング 訓練データ中のspammerの数を減らしてlegitの数 に合わせる 表３：サンプリング前後の判別率の変化 legit数 判別精度 (%) spammer数 FPR (%) FNR(%) サンプリング前 3577 514360 99.85984 12.57241799 0.05365505 サンプリング後 3577 3577 97.97855 2.843188521 1.199672872 FPRがかなり改善された 2011/2/4 ※FPR: False Positive Ratio = legitをspammerと判別した数 / legit数 FNR: False Negative Ratio = spammerをlegitと判別した数 / spammer数 修論審査 47 カテゴリカルでないデータも含めた学習 カテゴリカルなデータ BGP Prefix, AS番号, 国番号, OS, PTRレコードの有無 カテゴリカルでないデータ messages, spam, ham, greylisted, session, active days 値の大きさに引きずられてまともな結果がでなかったので、 使用しないでいた 数値の範囲の大きな特徴が数値の範囲の小さい特徴を 支配してしまうので、そのような特徴を用いる場合は スケーリングしないと使い物にならないとの指摘 2011/2/4 修論審査 48 カテゴリカルでないデータも含めた学習 1 1:10 2:0 3:10 4:34 5:0 6:3 25509:1 42636:1 46637:1 46660:1 46669:1 1 1:25 2:0 3:25 4:33 5:0 6:11 19636:1 41855:1 46637:1 46660:0 46668:1 1 1:21 2:0 3:21 4:19 5:0 6:11 20500:1 42125:1 46637:1 46660:1 46671:1 1 1:0.000965903602820438 2:0 3:0.000977708251857646 4:0.000913192952299097 5:0 6:0.125 25509:1 42636:1 46637:1 46660:1 46669:1 1 1:0.0024147590070511 2:0 3:0.00244427062964411 4:0.000886334336055006 5:0 6:0.458333333333333 19636:1 41855:1 46637:1 46660:0 46668:1 1 1:0.00202839756592292 2:0 3:0.00205318732890106 4:0.000510313708637731 5:0 6:0.458333333333333 20500:1 42125:1 46637:1 46660:1 46671:1 2011/2/4 修論審査 49 カテゴリカルでないデータも含めた学習 カテゴリカルでないデータ 表４：カテゴリカルでないデータを含めた場合の判別率の変化 判別精度 (%) FPR (%) FNR(%) ① 99.85984 12.57241799 0.05365505 ② 99.92588 6.412015997 0.03014346 ③ 97.97855 2.843188521 1.199672872 ④ 98.57506 1.741230534 1.108640811 ①カテゴリカルなデータのみ、サンプリングなし ②カテゴリカルでないデータ有り、サンプリングなし ③カテゴリカルなデータのみ、サンプリング有り ④カテゴリカルでないデータ有り、スケーリング有り 2011/2/4 修論審査 50 2011/2/4 修論審査 51 （再掲）実験2 内容と結果 使用する特徴を限定してSVMを適用、様子を見る messages～active daysの特徴を省く 表１：適用したカーネル関数とその判別率 カーネル関数 線形分離 (default) 判別精度(%) FPR (%) FNR (%) 99.8405325 13.96507444 0.063570403 多項式カーネル 99.85723952 12.54191507 0.056228169 RBFカーネル 99.82759111 20.08528623 0.033825298 99.4721702 44.51718041 0.223138722 シグモイドカーネル FPRが高く、 FNRが非常に 低い 訓練データの 偏りによるもの ※FPR: False Positive Ratio = legitをspammerと判別した数 / legit数 FNR: False Negative Ratio = spammerをlegitと判別した数 / spammer数 2011/2/4 修論審査 spammer数は legit数の約150倍 52 パラメータチューニング SVMではカーネルパラメータの選択が重要 特にRBFカーネルでは顕著 LIBSVMでも推奨されている 上手くパラメータを設定できればかなり有効 LIBSVM付属のツールによるパラメータ探索 grid.py 表２：パラメータ適用前の判別率 カーネル関数 RBFカーネル 判別精度(%) 99.82759111 FPR (%) 20.08528623 FNR (%) 0.033825298 ※FPR: False Positive Ratio = legitをspammerと判別した数 / legit数 FNR: False Negative Ratio = spammerをlegitと判別した数 / spammer数 表３：パラメータ適用後の判別率 カーネル関数 RBFカーネル 2011/2/4 2010/11/30 判別精度(%) 99.890825 FPR (%) 10.36694932 第一回修論進捗発表 修論審査 FNR (%) 0.047188214 53 確率値に近似した結果 確率値での出力も可能 度合いで判断することができる legitらしさ、spammerらしさ 閾値を設定してフィルタリング オプション未使用 label 1 -1 1 1 1 1 1 1 1 2011/2/4 2010/11/30 -w オプションで 重みづけした結果の 分析に利用 オプション使用 label 1 -1 1 0.961098 0.0389017 -1 0.244081 0.755919 1 0.96111 0.0388897 1 0.96111 0.0388897 1 0.961967 0.0380331 1 0.999864 0.00013586 1 0.966642 0.0333579 1 0.961014 0.0389856 1 0.962324 0.0376763 第一回修論進捗発表 修論審査 54 2011/2/4 2010/11/30 第一回修論進捗発表 修論審査 55 実験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＞ クラス 特徴量のインデックス 特徴量 featureは整数で表されるので、各特徴に番号を割り当てる必要がある 2011/2/4 2010/11/30 第一回修論進捗発表 修論審査 56
© Copyright 2024 ExpyDoc
