DEIM Forum 2017 A4-3

外れ構造検知：大規模離散値データの圧縮による集団アノマリの発見
丸橋 弘治†

齊藤 聡美†

悟†

鳥居

武仲

正彦†

† 株式会社富士通研究所 〒 211–8588 神奈川県川崎市上小田中 4-1-1
E-mail: †{maruhashi.koji,sa.satomi,torii.satoru,ma}@jp.fujitsu.com
あらまし

大規模な離散値データに基づき異常行動を効率的に発見することが求められている。従来の異常検知手法

は稀な値やパタンを持つデータを抽出するが、離散値のとりうる値が数万以上の大規模データになると、大半の値やパタンが稀なものになる。その場合、単一のデータを抽出するのではなく、値の関連の仕方に注目し、データの集団としてのアノマリを検知することが必要となる。本研究では、従来の異常検知手法にデータ集団の考え方を取り入れた、
新たなアノマリ検知手法を提案する。また、アノマリの候補となる小規模なデータ集団を大量に生成するための、新たなクラスタリング手法を提案する。さらに、実際の侵入検知ログを用いた実験により、本手法の効果を実証する。
外れ値検知, 最小記述長原理, 侵入検知

1. は じ め に
人やモノの挙動が反映された大規模データから、異常な行動

60,00040,00020,000
1
4,000
2,000

Port

キーワード

を発見することが強く求められている。例えば、ネットワーク

dstIP

システムへの不正な侵入を知らせるアラート（侵入検知ログ）
は、送信元 IP、送信先 IP、ポート番号といった数万種類の離

図1

1

1

100,000
50,000

srcIP

srcIP

dstIP

Port

a.a.a.ax.x.x.x

p1

a.a.a.ay.y.y.yp2

b.b.b.bx.x.x.xp2

b.b.b.by.y.y.yp1

侵入検知ログの数百万件以上のアラートのプロット（左）。ほと

散値を含むデータである（図 1）。企業のセキュリティ担当者

んどの送信元 IP(srcIP)、送信先 IP(dstIP)、ポート番号 (Port)は、大半を占める日常的なアラートの中から、従来知られていは稀な値であるが、稀な値を共有しあうデータの集団（右）は、ない類の攻撃を発見し、早急に対策を行う必要がある。そのた何らかの意味のある挙動を反映している可能性がある。

め、大規模な離散値データの中から、他と異なる異常なデータ（アノマリ）を抽出するだけでなく、対策を検討するため、異タ集団内での値の共有の度合いも考慮に入れて、データ集団と常の理由が容易に分析可能な技術が求められる。このような技

してのアノマリを抽出する。

術として、データ圧縮を利用したアノマリ検知手法が提案されまた、離散値データの従来のクラスタリング手法 [1] は、数ている [2], [13]。これらの手法は、値やパタンにコードを与え

万種類の離散値を含む大規模データに対し、アノマリの候補とるコード表を生成する。このとき、データ全体を効率的に圧縮なる数千個以上の小規模なデータ集団を効率的に生成することできるよう、頻出する値・パタンほど短いコードを与える。こはできない。さらに、ほとんどの従来手法ではデータ集団の数

れにより、頻出パタンで記述できないために記述長が長いデーを指定する必要があるが、数千個以上のデータ集団の数を予め

タをアノマリとして抽出すると共に、異常の理由となるパタン

知ることは困難である。本研究では、離散値データの新たなクを容易に分析することが可能となる。

ラスタリング手法も提案する。

しかし、数百万件以上のデータを含む大規模離散値データ
では、ほとんどの値・パタンが稀になってしまう。このような本研究の貢献は、以下のとおりである。

•

データ圧縮を利用した、新たなアノマリ検知手法を提案

データにおいては、稀な値・パタンを含む単一のデータを抽出する。提案手法は、データ集団別のコード表を用いて、頻出パするのではなく、互いに何らかの意味を持って関連しあっていタンで記述できないだけでなく、データ集団内での値の共有のる、もしくは互いの関連の仕方が他と異なるデータの集団を、度合いも考慮に入れて、アノマリであるデータ集団を抽出する。

アノマリとして検知することが必要となる。例えば、図 1 右に•

大規模離散値データから大量の小規模なデータ集団を効示したデータの集団は、それぞれの IP アドレスやポート番号

率的に生成する、新たなクラスタリング手法 DescCat を提案

は 1 回か 2 回しか使われない稀な値であるが、データ間で値をする。DescCat は、最小記述長原理 (MDL) に基づき、データ共有し互いに関連しあっていることから、単なるノイズではな

集団別のコード表の記述長と、データ全体の記述長の合計を最く、何らかの注目すべき挙動と関連している可能性がある。

小化する。また、予めデータ集団の数を与える必要はない。

本研究では、データ圧縮を利用したアノマリ検知手法に、デー•

実際の侵入検知ログを用い、多くのタイプの攻撃を従タ集団の考え方を取り入れた新たな手法を提案する。提案手法

来手法より高精度に検知できることを示す。さらに、DescCat

では、データ集団内での値の共有のされ方を反映した、データ

は、従来手法よりも大規模データセットを効率的に圧縮できる

集団別のコード表を導入する。そして、従来手法を拡張し、頻ことを示す。

出パタンで記述できないために記述長が長いだけでなく、デー2. 関 連 研 究
2. 1 離散値データからのアノマリ検知
セキュリティやリスク管理、不正監視などの様々な分野にお表 1 コード表 CT の例
データ集団

f1

f2

v code(v|C) v code(v|C) v code(v|C)

C1 101

a1 0

いて、アノマリ検知は重要である [8]。連続値データに対しては多くの手法が提案されているが [5], [11], [14]、離散値データに対する手法は比較的少ない。Das ら [9] は、ルールベースのア

f3

C code(C)

C2

10

a1 0

b1

0

c1

1

b2

1

c2

10

c3

11

b1

0

a2 1

c1

1

c3

10

ノマリ検知 [15] に基づき、ノイズの多い離散値データからのア
ノマリ検知手法を提案した。また、CompreX [2] は、データ圧L(M ) + L(D|M ),縮に基づく、高精度かつ説明力の高いアノマリ検知手法 [13] を発展させた手法である。しかし、いずれも、稀な値・パタンをが最小となるモデル M を最良のモデルとして選択する。言い含む単一のデータの抽出は可能だが、データ集団としてのアノ換えれば、MDL は、データセットとモデルそのものの両方を

マリを検知することはできない。

同時に簡潔に表現できるモデルを選択する。本研究では、MDL

2. 2 離散値データのクラスタリングに基づき、データセット D を最も簡潔に表現できるモデル M 、

離散値データのクラスタリング手法は多数提案されている [1]。

すなわちコード表を効率的に選択するアルゴリズムを提案する。

COOLCAT [4] や LIMBO [3] は、我々の提案手法と似た目的関4. 提 案 手 法

数の最小化を利用する。いずれも、クラスタ数 k に比例した計算量を必要とするため、数百万件以上のデータを含む離散値

本章では、コード表とデータの記述方法、およびアノマリス

データから、数千個のデータ集団を、現実的な計算量で生成すコアについて説明する。その後、新規のクラスタリングアルゴ

ることはできない。DHCC [16] は階層的にクラスタを生成する

リズム、およびデータ集団の可視化方法について述べる。

アルゴリズムであり、最も良いケースで log2 k に比例した計算

4. 1 コード表とデータの記述方法

量で計算可能である。しかし、アノマリ検知のために、小規模

まず、コード表を定義する。その後、コード表に基づくデー

なデータ集団を補正することは考慮に入っていない。
上記の手法は k を指定する必要があるが、k が数千以上になタの記述方法、および MDL に基づくクラスタリングに必要なコード表そのものの記述方法について説明する。

る場合、k を予め知ることは困難である。MDL に基づき k を

4. 1. 1 コ ー ド 表

自動的に決定する手法が、グラフ分割の文脈からいくつか提案

表 1 は、コード表の例である。コード表 CT は、データ集されている [6], [7]。また、ROCAT [10] は、MDL に基づく評団に対応した k 個の表のセットであり、それぞれの表は m + 1

価指標を用いる部分空間クラスタリングの手法である。しかし、個に区分されている。最初の区分にはデータ集団そのもののいずれも、k がデータ数より遥かに少ないことを前提とする。

コードが記述され、残りの区分にはデータ集団内の値のコードが記述される。各区分は２列の表であり、１列目にはデータ集

3. 準

備

団 C または値 v が記述され、２列目にはデータ集団のコード

3. 1 記法

code(C) または値のコード code(v|C) が記述される。なお、従データセット D に含まれるデータ数を N とする。個々の来手法 [2], [13] と違い、変数間の値の組み合わせに対するコー

データ r ∈ D は m 個の離散値変数 F = {f1 , . . . , fm } を

ドは用いない。これは、第 4. 3 章で説明するクラスタリング手

持ち、各変数 f ∈ F が取り得る値の集合 {v1 , v2 , . . .} をド法において、変数間の値の組み合わせを考慮したデータ集団のメイン dom(f ) とする。ドメインは変数間で背反、すなわち補正が困難なためである。

dom(fi ) ∩ dom(fj ) = ∅, ∀i =| j とする。
クラスタリング C は、互いに共通要素がないデータ集団群

C = {C1 , . . . , Ck } により、データセット D を分割する。すな
わち、C1 ∪ . . . ∪ Ck = D であり、Cp ∩ Cq = ∅, ∀p =| q である。データ集団 C における、値 v を持つデータ数を、n(v|C)とする。また、データ集団 C に含まれる第 i 番目の変数の値の集合を、fi (C) とする。

4. 1. 2 データの記述長
コード表 CT を使うことにより、各データ集団 C 中のデータ

r = (v1 , . . . , vm ) を、code(C) に code(v1 |C), . . . , code(vm |C)を加えたものとして記述できる。本研究では、code(v|C) を op-

timal prefix code [12] により記述する。このとき、code(v|C)の記述長は、Shannon エントロピーを用いてL(code(v|C)|CT ) = − log

本論文では、全ての対数の底を 2 とし、0 log 0 = 0 とする。

n(v|C)|C|

3. 2 最小記述長原理で算出される。直観的には、データ集団中で高頻度で出現する

最小記述長原理（MDL） [12] に基づき、与えられたモデル

値のコード長を短くすることにより、データ全体をより圧縮での集合 M に対し、最良のモデル M ∈ M を選択することができる。すなわち、L(M ) をモデル M の記述長、L(D|M ) をモ
デル M を用いたときのデータセット D の記述長としたとき、トータルの記述長

きる。同様に、code(C) の記述長は、L(code(C)|CT ) = − log|C|Nで算出される。直観的には、データセット中で多くのデータを

占めるデータ集団のコード長を短くすることにより、データ全

データ集団に与える、２種類のアノマリスコアを提案する。

体をより圧縮できる。
以上より、データ集団 C 中のデータ r = (v1 , . . . , vm ) の記述

L(r|CT ) = L(code(C)|CT ) +m∑

圧縮アノマリスコアは、従来のデータ圧縮に基づくアノマリ

L(code(vi |C)|CT )スコアを、データ集団の記述長を用いて拡張したスコアである。

i=1

圧縮アノマリスコア SCcomp (C) を、データを集団化しない場となる。さらに、データセット全体の記述長は、∑∑

いずれも、スコアが閾値より大きい集団をアノマリとみなす。

4. 2. 1 圧縮アノマリスコア

長は、C の記述長と r の記述長の合計

L(D|CT ) =4. 2 アノマリスコア

合のコード表 CT1 を用いて、L(r|CT )SCcomp (C) =C∈C r∈Cとなる。

と定義する。第 1 項は、従来のデータ圧縮に基づくアノマリス

4. 1. 3 コード表の記述長

コアに相当するものであり、稀な値を持つデータ集団ほど高い

次に、コード表 CT そのものの記述長について説明する。コード表の各区分の２列目の記述長は、単純に code(C) と code(v|C)の合計である。コード表の各区分の１列目、値 v の記述には、
再び optimal prefix code を用いる。すなわち、各値の記述長を、Shannon エントロピーを用いて、CT における各値の出現頻度に基づき算出する。具体的には、コード表 CT における第i 変数の値 v の記述長は、CT における v の出現数 rv 、および∑出現数の合計 ci = vi ∈dom(fi ) rvi を用いて、− log rcvi により算出する。以上より、コード表 CT の記述長は、L(CT ) =1 ∑1 ∑L(r|CT1 ) −L(r|CT )|C| r∈C|C| r∈C∑

L(code(C)|CT )∑4. 2. 2 エントロピーアノマリスコア
圧縮アノマリスコアは、各変数の値の共有のされ方の違いが考慮できない。例えば、送信元 IP が多く共有されているデー
タ集団が多くを占める場合に、ポート番号が多く共有されているデータ集団をアノマリとして検知することができない。そこ∑v∈fi (C)

m
∑∑
∑

m
∑

値が多く共有されている場合に、大きい値となる。

H(fi (C)) =L(code(v|C)|CT )−rv log

i=1 v∈dom(fi )−n(v|C)
n(v|C)log|C||C|

に対し、(H(f1 (C)), . . . , H(fm (C))) が外れ値となるデータ集団

C∈C i=1 v∈fi (C)+組み合わせは考慮していない。第 2 項は、集団内のデータ間でで、データ集団 C の第 i 変数の記述長の平均値（エントロピー）

C∈C+値となる。ただし、従来手法 [2], [13] のように、変数間の値のを検知することを考える。このとき、値の共有のされ方はデータ

rv
ci

集団のサイズにも依存するため、L(C|CT ) も重要な特徴量である。これらのことから、データ集団 C の値の共有のされ方の特徴を、ベクトル xC = (L(C|CT ), H(f1 (C)), . . . , H(fm (C)))Tとなる。
なお、CT の第１区分の１列目にあたるデータ集団 C の番号は、記述する必要がない。これは、情報の損失なくデータセット

により表現する。そして、データ集団 C のエントロピーアノマ
リスコア SCent (C) を、マハラノビス距離を圧縮するためには、C の番号を用いる必要がないためである。
すなわち、データが (code(C), code(v1 |C), . . . , code(vm |C)) で記述されれば、コード表 CT において C が特定でき、さらに

v1 , . . . , vm を特定することができる。

− log

+

m
∑

∑

∑

−|C| logC∈C+C ′ ∈C xC′

であり、S はベラスタリングを探索したい。しかし、全ての可能性のある CT

m
∑∑

|C|
+
N
C∈C i=1i=1 v∈dom(fi )+∑我々は、MDL に基づき、L(CT, D) (式 1) を最小にするク

L(CT, D) = L(CT ) + L(D|CT )C∈C

により定義する。このとき、µ = k1

4. 3 クラスタリングアルゴリズム

データセット D とコード表 CT の記述長の合計は、∑√(xC − µ)T S −1 (xC − µ)クトルの集合 xC1 , . . . , xCk に関する分散共分散行列である。

4. 1. 4 記述長の合計=

SCent (C) =

∑

− log

v∈fi (C)n(v|C)|C|のため、ヒューリスティクスによる手法 DescCat を提案する。

rv−rv log
ci

DescCat は、L(CT, D) を小さくするように、データ集団の分割と統合を繰り返す。

|C|
N

m
∑∑
∑
C∈C i=1 v∈fi (C)−n(v|C) logに対して L(CT, D) を算出することは現実的ではなく、また全探索のための有効な枝狩り手法を考えることも困難である。そ4. 3. 1 メインアルゴリズム
アルゴリズム 1 は、DescCat の疑似コードである。データがn(v|C)|C|(1)となる。後述するクラスタリング手法は、MDL に基づき、L(M, D) すなわち L(CT, D) を最小とする CT を選択する。

集団化されていない状態から開始し、L(CT, D) が減少しなくなるまで、データ集団の分割と統合を繰り返す。
データ集団を統合する最も単純な方法は、全てのデータ集団の組み合わせに対し、統合したときの L(CT, D) を算出するこAlgorithm 1: DescCat

Algorithm 2: split

Input: D = {r1 , . . . , rN }, ϵ1 , ϵ2 , maxiter

Input: D, C, コード表 CT , 記述長 L, G, ϵ

ただし rs = (vs1 , . . . , vsm ), vsi ∈ dom(fi )Output: C, コード表 CT , 記述長 L

Output: C = {C1 , . . . , Ck }, コード表 CT , 記述長 L

1

Q←C ;

1

(C, CT, L) ← initialize(D) ;2while Q =| ∅ do2

for iter ← 1 to maxiter do

3▷C を 1 つの集団に初期化

3

Q から集団 Cp を選択;

C0 ← C, CT0 ← CT, L0 ← L;

4

Q ← Q\{Cp };▷データ集団の分割

5(C 0 , C 1 , CT r , Lr ) ← ランダム分割 (Cp , CT, G);

6(C 0 , C 1 , CT u , Lu ) ← 補正 (C 0 , C 1 , CT r , G);
if Lr − ϵ|Cp |(Lr − Lu ) < L then4G ← {{r1 }, . . . , {rN }} ;5

(C, CT, L) ← split (D, C, CT, L, G, ϵ1 );7▷データ集団の統合
6

G←C ;

7

(C, CT, L) ← initialize(D) ;▷データがユニット

8

C ← C\{Cp } ∪ {C 0 , C 1 }, CT ← CT u , L ← Lu ;▷データ集団がユニット

9Q ← Q ∪ {C 0 , C 1 };▷C を 1 つの集団に初期化

109(C, CT, L) ←split (D, C, CT, L, G, ϵ2 );if L >= L0 then10

C ← C0 , CT ← CT0 , L ← L0 ;11

break;

8

12

end

13

end

14

return C, CT, L;▷初期化とである。しかし、集団数 k に対し少なくとも k 2 に比例する計算量となるため、集団数が数千個以上になる場合には現実的ではない。そこで、DescCat は、データセット全体を、データ集団を単位として分割する。これは、データ集団の分割と同じアルゴリズムで実現できる（アルゴリズム 1 の split()）。その結果生成された「データ集団の集団」は、データ集団を統合したものとみなせる。そして、データ集団の分割前に比べてL(CT, D) が減少しないのであれば、それ以上統合は不可能と判断し、終了する。

4. 3. 2 split アルゴリズム
アルゴリズム 2 は、データ集合の分割と統合の両方に用いられる split アルゴリズムの疑似コードである。このアルゴリズ
ムは、データ集団のランダム分割とその補正を繰り返す。デー
タは、「ユニット」と呼ぶ単位によりデータ集団に割り当てる。
ユニットは、集団の分割では 1 つのデータであり、集団の統合
では、1 つのデータ集団である。
補正のアルゴリズムは、基本的には、L(CT, D) が減少しなくなるまで、個々のユニットの交換を繰り返すものである（本論文では詳細は省略する）。しかし、データ集団に数万以上のデータが含まれる場合、L(CT, D) を減少させられるよう補正することは容易ではない。そのため、将来の分割における最終的な L(CT, D) の減少の期待値を導入する。すなわち、(1) 集団が大きいほど、また、(2) ランダム分割に比べて L(CT, D)が大きく減少するほど、将来的にも分割しやすいと仮定する。

end

11

end

12

return C, CT, L;に ϵ = 0.01 を用いて、充分に良い結果を得ることができた。

4. 3. 3 計 算 量
全体の記述長 (式 1) を全て計算しなおす場合、計算量は、∑O(N + mi=1 |dom(fi )|) である。しかし、１つのデータが別のクラスタに再配置されるごとに、記述長は O(1) で更新することができる。従って、DescCat の全体の計算量は、I をアルゴ
リズム 1 の繰り返し回数（上限は maxiter）、S をアルゴリズ
ム 1 の 1 回の繰り返しの中で各データが再配置を受ける平均回数とすると、O(IN S) となる。これは、アルゴリズム 2 において毎回バランスよく分割される場合に、最も良い結果となる。この場合には、S は log2 k に近くなり、全体の計算量はO(IN log2 k) となる。これは、データ集団数が数千個以上の場
合でも、現実的な計算量である。なお、階層的な分割アルゴリ
ズムである DHCC [16] も類似の計算量であるが、DHCC は分
割後に統合するプロセスを持たない。最も悪い場合は、ほとん
ど毎回の分割において、生じるデータ集団の一方がそれ以上分割されない場合である。このような場合には、S は最終的な集
団数 k に近くなり、全体の計算量は O(IN k) になる。

4. 4 データ集団の可視化
データ集団をグラフ表現を用いて可視化することにより、分析が容易になる。図 2 は、クラウド侵入検知ログ（第 5. 1
章で説明）で発見されたデータ集団の可視化の例である。ここで、分析をより容易にするため、情報量の少ない値を省略して表示している。例えば、集団内での値 v の情報量の合計−n(v|C) log n(v|C)
が閾値より小さい場合には、v を省略する。
|C|
さらに、集団内で情報量の多いデータを、赤いノードで強調している。その他、データの性質に合わせ、グラフ表現に様々な工夫を施すことが考えられる。なお、このデータ集団の詳細は、この仮定に基づき、L(CT, D) の減少の期待値を ϵ|C|(Lr − Lu )第 5. 1 章で説明する。

により算出する。ここで、Lr はランダム分割後の L(CT, D)、

5. 評 価 実 験Lu は補正後の L(CT, D) である。そして、Lu − ϵ|C|(Lr − Lu )が分割前の L(CT, D) より小さいのなら、将来的に良い分割となる可能性が高いとみなし、分割を実行する。なお、ϵ は、デー
タ集団の分割と統合で異なる値でもよい。今回の実験では、共アノマリ検知の精度評価結果、および DescCat の計算量と圧縮効率の評価結果を報告する。提案手法は、Python で実装した。全ての実験は、2.8GHz の 6 コアの CPU と 48GB のメ

[FTP*** u*d/p*l][FTP*** a*m/a*l]*.*.248.88[FTP*** u*9/t*l][FTP*** w*r/p*l][FTP*** c*y/3*l][FTP*** w*1/p*l]*.*.177.228[FTP*** w*m/t*l]*.*.12.2****.*.252.222[FTP*** u*d/t*l][FTP*** w*4/s*l][FTP*** w*3/q*l]**.*.247.239[FTP*** w*r/t*l]

Detection precision

1[FTP*** r*t/s*l]CompreX
SC_compSC_ent

0.8
0.6
0.4
0.2
0
0

0.5
Detection rate / Recall1

図 3 再現率-適合率プロットの例（第 6 週）。横軸に再現率、縦軸

図 2 クラウド侵入検知ログで発見されたデータ集団の可視化。全ての変数の値が一致するデータを１つの楕円のノードでまとめてに適合率を示す。黒色の点線は CompreX、赤色の太い実線はSCcomp 、青色の太い点線は SCent である。

示し、ノードの大きさはデータ数を表す。値は長方形のノードで示し、変数により色分けしている。集団内での情報量の合計が小さい値は省略している。データと、そのデータに含まれる値（Sig）の、４つの変数を持つ。シグネチャには、侵入検知シス

をエッジで接続する。情報量の多いデータは赤いノードで示し、テムが推定した攻撃タイプが示されている。約 2,000,000 件のさらにアスタリスクで強調する。

データが含まれる、６週間分のデータを実験に用いた。クラウ
ド侵入検知ログの概要を、表 5 に示す。

表 2 DARPA 侵入検知ログの攻撃のタイプ分類。
タイプ

攻撃

DOS

back, land, neptune, smurf, teardrop, syslog

R2L
U2R

probing

dict, dict simple, ftp-write, guest, imap, phf, mul-

5. 2 DARPA 侵入検知ログからのアノマリ検知
表 3 に、DescCat により生成されたデータ集団数、およびデータ集団のデータ数の最小値、最大値、平均値を示す。デー

tihop, spy, warez, warezclient, warezmaster

タ集団数は、どの週でもおよそ 1, 000 個から 2, 000 個であっeject, eject-fail, ﬀb, ﬀb clear, format, format clear,

た。比較手法として、CompreX [2] のプログラムをダウンロー

format-fail, loadmodule, load clear, perl clear,

ドして用いた。なお、CompreX を大規模データに適用するた

perlmagic, rootkit

め、主要アルゴリズムには影響しない微小な改変を加えた。

ipsweep, nmap, satan, portsweep

5. 2. 1 評 価 指 標anomaly anomaly

精度評価の指標として、 [2] と同様の平均適合率を用いた。これは、再現率に対する適合率の平均値のことである。適合率とモリを持つ、64 ビット Windows 7 の計算機を用いて行った。

は、アノマリとしたデータのうち、正しく攻撃であったデータ

5. 1 データセットが占める割合である。また、再現率とは、全攻撃のうち、検知性質の異なる２つの侵入検知ログを用いて実験を行った。

できた攻撃が占める割合である。具体的には、まず、アノマリ

5. 1. 1 DARPA 侵入検知ログ

スコアの様々な閾値に対する再現率と適合率を算出する。そし（注 1）

は、意図的に行て、再現率を横軸に、適合率を縦軸としたプロットを作成し、われた攻撃が含まれた侵入検知ログであり、侵入検知の精度

プロットの下部の面積を、平均適合率とする。図 3 は、再現率-

DARPA Intrusion Detection Data Sets

評価が可能である。今回は、1998 年の 7 週間分の学習データ

適合率プロットの例である（第 6 週目）。下部の面積が大きいほを用いた。なお、著名な KDD Cup 99 データセットは、このど、手法として性能が良いことを意味する。この場合、SCcomp

データセットを専門家が人手で加工したものである。我々は、はほとんどの再現率に対して従来手法より高い適合率を示す一

専門家の知識に頼らないアノマリ検知を評価するため、送信元

方、SCent は従来手法の適合率より低い。

IP（sIP）、送信先 IP（dIP）、送信元ポート番号（sPort）、送

5. 2. 2 精 度 評 価

信先ポート番号 (dPort）の 4 変数を加工せずに用いた。また、

表 4 には、平均適合率の全ての週の平均値を示している（注 1）を参考に、攻撃を５つに分類した（表 2）。

(“All”)。全体として、SCcomp は従来手法より平均適合率が

ただし、本来 DOS 攻撃に分類される neptune は、正常なデー

高く、SCent は従来手法より低い。攻撃タイプ別に見ると、

タとした。なぜなら、neptune 攻撃が発生するときは、明らか

SCcomp は、DOS タイプと R2L タイプを、従来手法より良いにそれとわかるデータが、全てのデータの半分以上を埋め尽く精度で検知している（表 4）。以下、SCcomp と SCent の違いにすからである。表 3 に、各攻撃タイプのデータ数を示す。

ついて、詳細に分析する。

Attack Database

5. 1. 2 クラウド侵入検知ログ

図 4 に、週別の平均適合率を示す。第 3 週と第 4 週、および

我々は、ある企業が提供するクラウド環境の侵入検知ログへ

第 6 週において、SCcomp は従来手法より良い結果を示していの適用実験も行った。このデータセットは、送信元 IP（sIP）、る。また、SCent は、第 3 週においては、どの手法よりも高い

送信先 IP（dIP）、送信先ポート番号（dPort）、シグネチャ

平均適合率を示している。図 5 は、週別の平均適合率を、さら（注 1）：http://www.ll.mit.edu/ideval/data/に攻撃タイプ別に示したものである。ただし、anomaly タイプ

表 3 DescCat が DARPA 侵入検知ログで生成したデータ集団の概要。

sIP

dIP

sPort

dPort

DOS

1

177,487

40 1,040 12,795

9

1

1

4

0

2

187,986

40 2,265 15,819

108

1,002

55

0

3

360,225 1,096 4,987 35,379

7,098 76,638

40

4

116,881

93 2,133 17,307 11,444

201 1,770

5592,61164 2,022 45,501

8,485

1,174

0

6

939,247

67 1,978 53,143 12,740

717

7

431,578

54 2,265 36,603 10,141

390

988

2

104,239

179.6

1,043

0 1,4102

106,970

133.3

1

7,236

0 2,0942

159,742172.0

3111,7930 2,0732

25,118

56.4

23

7,519

0 2,1622

201,323

274.1

883

14

14,166

9 1,1353

199,325

827.5

2

4

9,341

0 1,0012

200,794431.1

表 4 DARPA 侵入検知ログにおける平均精度。

R2L

CompreX

0.17

0.04

0.02 0.05

0.19

0.00

SCcomp0.24

0.09 0.08

0.01

0.18

0.00

SCent

0.09

0.07

0.00

0.02

0.00

0.00

U2R Probing Anomaly

1CompreX
SC_compSC_ent

0.8
0.6
0.4
0.2
0

1
0.8

w2

w3

w4

w5

w6

0.2
0
w2

w3

w4

w5

w6

w7

図 4 DARPA 侵入検知ログにおける各手法の平均適合率。横軸に週、縦軸に平均適合率を示す。

0.2(a) DOS

w2

w3

w4

w5

w6

w7

(b) R2L
1
CompreX
SC_compSC_ent

0.8
0.6
0.4
0.2
0

w1

0.4

w1

Average precision

0.4

0.6

w7

1

0.6

CompreX
SC_compSC_ent0.8

0w1CompreX
SC_compSC_entAverage precision

Average precision0

1

All DOS

Average precision

Method|C| min|C| max|C| ave|C|

R2L U2R probing anomaly

Average precision

|D|

Week

CompreX
SC_compSC_ent

0.8
0.6
0.4
0.2
0

w1

w2

w3

w4

w5

w6

w7

w1

(c) U2R

w2

w3

w4

w5

w6

w7

(d) Probing

図 5 DARPA 侵入検知ログの、攻撃タイプ別の平均適合率。横軸に週、縦軸に平均適合率を示す。(a) は DOS タイプ、(b) は R2Lの攻撃は、どの手法でも平均適合率が著しく低いため、示してタイプ、(c) は U2R タイプ、(d) は probing タイプである。

いない。第 3 週における SCent の高い平均適合率は、DOS タ
イプの検知によるものであった（図 5(a)）。具体的には、SCentの結果は、各データ集団により、攻撃に関連するデータをうまは、smurf 攻撃をほぼ正確に検知していた。すなわち、75, 630

く切り出せていることを示唆している。

件の全ての smurf 攻撃は、併せて 75, 636 個のデータを含む

5. 3 クラウド侵入検知ログからのアノマリ検知

SCent が高い上位 2 つのデータ集団に含まれていた。その他、続いて、クラウド侵入検知ログの実験結果を報告する。約

SCcomp は、第 4 週において、R2L タイプの攻撃を特に精度良2, 000, 000 個のデータが、10, 000 個以上のデータ集団に分割さく検知していた（図 5(b)）。この週で最も多い R2L タイプのれた。表 5 は、DescCat によるクラスタリングの結果の概要

攻撃は warezclient 攻撃であり（1, 766 件）、これらのほぼ半数である。クラウド侵入検知ログについては、定量的な評価のたが、SCcomp の上位 100 データ集団（1, 474 件）に含まれていめの正解データが無いため、定性的な結果のみ示す。

た。このように、SCcomp と SCent は、それぞれ異なるタイプ

5. 3. 1 圧縮アノマリスコアの攻撃パタンを的確に捉えられることが示唆された。

表 6 に、SCcomp の上位 5 個のデータ集団の概要を示す。こさらに、SCcomp と SCent の上位のデータ集団において、各のクラウド環境の侵入検知システムをよく知る専門家による、攻撃がどのように含まれているかを、具体的に示す。図 6(a)各データ集団の解釈も示す。例えば、SCcomp が最も高いデー

は、第 6 週における、SCcomp の上位 20 データ集団である。

タ集団には、3 種類の送信元 IP と 2 種類の送信先 IP と 2 種類

多くのデータ集団は probing タイプの攻撃を含み、それらは全の送信先ポート番号、および 1 種類のシグネチャを持つ 4 つのて satan 攻撃であった。第 18 位のデータ集団（図 6(a) 矢印）

データが含まれる。いずれも、データセット中で稀な値を含み、は DOS タイプの land 攻撃であり、第 6 週の 17 個の land 攻

かつ互いに値を共有しあうデータ集団であるが、大量の稀な値

撃のうち 6 個を含んでいた。また、同じ週における、SCent のを含むデータセットの中から、このような小規模のデータ集団

上位 20 個のデータ集団を図 6(b)（(c) は拡大図）に示す。第に注目し分析することは容易ではない。

15,16,17 位のデータ集団の全てのデータは DOS 攻撃であった

5. 3. 2 エントロピーアノマリスコア（図 6(b)(c) 矢印）。これらは teardrop 攻撃であり、600 個の全SCent が高いデータ集団を専門家が分析した結果、いくつかての teardrop 攻撃がこれらのデータ集団に含まれていた。以上の注目すべき攻撃パタンが発見された。その 1 つは、可能性の

50

0
0

5

10
Rank

15

anomaly
probing
U2R
R2L
DOS
normal150000100000

Number of records

100

2000

200000anomaly
probing
U2R
R2L
DOS
normalNumber of records

Number of records

150

50000

0
0

20

(a) SCcomp

5

10
Rank

15

anomaly
probing
U2R
R2L
DOS
normal

1500

1000

500

0
0

20

5

(b) SCent

10
Rank

15

20

(c) SCent (zoom)

図 6 第 6 週におけるアノマリスコアの上位 20 個のデータ集団。(a) は、SCcomp の上位デー
タ集団である。１つのデータ集団には、DOS タイプの攻撃が多く含まれていた（矢印）。

(b) は、SCent の上位データ集団である（(c) は拡大図）。いくつかのデータ集団には、(a)とは別の DOS タイプの攻撃が多く含まれていた（矢印）。
表 5 クラウド侵入検知ログから DescCat により生成されたデータ集団の概要。

|D|

sIP

dIP

dPort

|C| min|C| max|C| ave|C|Sig

1,942,041 123,156 3,935 50,217 3,640 13,565
表6SCcomp2

114,952

143.2

クラウド侵入検知ログの、SCcomp 上位 5 個のデータ集団。

|C| sIP

dIP

Sig

説明

[TCP***]

RST パケットの大量送信

5900[VNC***]VNC(Virtual Network

1198, 1226,[Internet***],

悪意あるスクリプト挿入と1164, 1249

[Malware***]マルウェアのダウンロード

0[Invalid***]

不正な IP バージョン番号10649, 2808,[Malicious***] 悪意ある JavaScript 挿入

dPort

34.9

4 *.*.46.146, *.*.182.175, *.*.241.196, *.*.248.150 764, 847

31.9

4 *.*.65.129*.*.240.19, *.*.240.15

31.0

4 *.*.200.65, *.*.97.66*.*.248.165

30.2

2 *.*.0.0*.*.0.0

29.7

6 *.*.227.13, *.*.9.196,*.*.247.211*.*.2.189
Computing) に対する攻撃*.*.153.106, *.*.57.142,

33909, 31389,*.*.227.13, *.*.18.234

37446, 5712*.*.146.211

ある ID/PASS の組合せを手当たり次第に試行する総当たり攻*.*.71.62*.*.199.239

撃であった（図 2）。すなわち、2 つの攻撃元（“*.*.177.228”*.*.200.186*.*.28.68*.*.181.43*.*.172.161と “*.*.12.2”）が、2 つの標的（“*.*.248.88” と “*.*.252.222”）*.*.166.203*.*.185.203*.*.253.243*.*.67.37

に対し、総当たり攻撃を行っていた。さらに、そのうち 1 つの*.*.3.19*.*.0.91*.*.252.178*.*.224.220*.*.240.70*.*.241.55*.*.219.179*.*.245.135*.*.151.69*.*.107.172*.*.252.29*.*.247.121*.*.221.117*.*.152.90

攻撃元は、別の標的（“*.*.247.239”）に対しても類似の攻撃を*.*.63.254*.*.118.12*.*.246.5

行っていた（図 2 の赤色のノード）。なお、これは、SCent の*.*.253.237

上位約 1.0% にあたる、第 140 位のデータ集団であった。

*.*.253.206

**
** *

また、稀なタイプの Secure Shell(SSH) 総当たり攻撃も発見*.*.35.3[Host***]*.*.138.202*.*.143.25*.*.11.112[Secure***]*.*.13.170*.*.207.138*.*.188.85*.*.175.3*.*.241.168*.*.145.55*.*.246.24*.*.80.193*.*.247.107*.*.247.139*.*.245.169*.*.216.90*.*.247.191*.*.245.225*.*.81.7*.*.0.41*.*.6.85*.*.113.204*.*.91.17*.*.5.48*.*.155.91*.*.247.123*.*.222.104*.*.253.255

された（図 7）。すなわち、ある 1 組の標的群に対し、多数の使*.*.46.119*.*.253.210*.*.194.98*.*.125.35*.*.81.37*.*.253.204

い捨て IP アドレスを用いて、可能性のある SSH プロトコルの*.*.253.36*.*.48.94*.*.240.121*.*.83.218*.*.248.54*.*.253.65*.*.240.139

パスワードを試行していた（図 7 の “[Secure***]” に接続するデータ）。さらに、図 7 で強調された赤色のノードにより、こ

図7

クラウド侵入検知ログで発見されたデータ集団の可視化。

の攻撃にいくつかのホスト探索が関与していることに、分析者は容易に気づくことができた。さらなる分析により、このホスト探索は、この攻撃の前触れとして行われていることが明らかになった。なお、これは、SCent の上位約 0.9% にあたる、第118 位のデータ集団であった。
5. 4 計算量と圧縮効率の評価実験
DARPA 侵入検知ログを 1 日単位で分割し、計算量と圧縮効
果を評価した。1 日あたりおよそ 1, 000 個から 500, 000 個のデータが含まれ、DescCat により 500 個から 1, 300 個のデー
タ集団が生成された。
比較対象として、類似のコスト関数を最小化する COOL-CAT [4] を用いた。ただし、コスト関数は L(D, CT ) とした。
以降、この比較手法を DescCat-CC とよぶ。DescCat-CC は、
データを 1 つずつ含む初期データ集団を生成した後、残りのデータを追加していく。全てのデータの追加後、各データ集

Computing time (sec.)

6. 結

50000
DescCat-CC
DescCat論

40000

データ集団別のコード表を用いた、新たなアノマリ検知手法

30000を提案した。提案手法は、大規模な侵入検知ログに対し、従来手法より高い検知精度を示した。また、大量の小規模なデータ

20000

集団を効率的に生成する DescCat を提案した。DescCat は、

10000

大規模データに対し、計算量と圧縮効率の両面で、従来手法より良い性能を示した。今後、データ集団別のコード表に、変数

0
0

100k

200k

300k

Number of records

間の値の組み合わせを考慮することを検討する。

(a) Computing time

文

1.1
1.0

< 30,000>= 30,000

DescCat

0.9

0.8

0.7

0.6
0.6

0.7

0.8

0.9

1.0

1.1

DescCat-CC(b) Compression ratio

図 8 (a) 1 日単位の DARPA 侵入検知ログに対する計算時間。Desc-

Cat の回帰直線は赤色の実線、DescCat-CC の回帰直線は青色の点線で示す。横軸にデータセットのサイズ、縦軸に計算時間を示す。(b) クラスタリング前の記述長に対する、クラスタリング
後の記述長の比（圧縮率）。データ数が 30, 000 より少ないデー
タセットは三角、30, 000 以上のデータセットは丸で示す。横軸に DescCat-CC の圧縮率、縦軸に DescCat の圧縮率を示す。

団で稀な値を持つデータを、適切なデータ集団に再配置する。

DescCat-CC のパラメータは、データ集団の最小サイズ m を100、確信度 δ を 0.5、再配置するデータの割合を 10% とした（詳細は [4] 参照）。また、DescCat-CC は予めデータ集団数 kを与える必要があるが、今回は DescCat で生成されたデータ
集団数と同じ数を与えた。DescCat のパラメータ maxiter は2 とすることで、今回の実験では充分な性能が得られた。
5. 4. 1 計算量の評価
図 8(a) に、DescCat と DescCat-CC の計算時間を示す。共に、計算時間は全データ数にほぼ比例して増加するが、DescCat
は DescCat-CC に比べて傾きが小さい。これは、DescCat-CCの計算量はデータ集団数 k に比例するのに対し、DescCat の計
算量は最善の場合に log2 k に比例するためと考えられる。

5. 4. 2 圧縮効率の評価
図 8(b) は、DescCat と DescCat-CC の圧縮率の比較である。ここで、圧縮率とは、クラスタリング前後の記述長の比である。圧縮率が小さいほど、良く圧縮されたことを意味する。

DescCat は、データ数が 30, 000 個より大きいデータセットに対し、DescCat-CC より良く圧縮することができた。総じて、

DescCat は、大規模なデータセットにおいては、計算量と圧縮効率の両面で従来手法よりも良い性能を示すことがわかった。

献[1] Charu C. Aggarwal and Chandan K. Reddy, editors. Data
Clustering: Algorithms and Applications. CRC Press, 2014.
[2] Leman Akoglu, Hanghang Tong, Jilles Vreeken, and Christos Faloutsos. Fast and reliable anomaly detection in categorical data. In CIKM, pages 415–424, 2012.
[3] Periklis Andritsos, Panayiotis Tsaparas, Renée J. Miller,
and Kenneth C. Sevcik. LIMBO: scalable clustering of categorical data. In EDBT, pages 123–146, 2004.
[4] Daniel Barbará, Yi Li, and Julia Couto. COOLCAT:an entropy-based algorithm for categorical clustering. In
CIKM, pages 582–589, 2002.
[5] Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng,
and Jörg Sander. LOF: identifying density-based local outliers. SIGMOD Record, 29:93–104, May 2000.
[6] Deepayan Chakrabarti. Autopart: Parameter-free graphpartitioning and outlier detection. In PKDD, pages 112–
124, 2004.
[7] Deepayan Chakrabarti, Spiros Papadimitrou, Dharmendra
Modha, and Christos Faloutsos. Fully automatic crossassociations. In KDD, pages 79–88, 2004.
[8] Varun Chandola, Arindam Banerjee, and Vipin Kumar.
Anomaly detection: A survey. ACM Comput. Surv., 41(3),2009.
[9] Kaustav Das, Jeﬀ G. Schneider, and Daniel B. Neill.
Anomaly pattern detection in categorical datasets. In KDD,
pages 169–176, 2008.
[10] Xiao He, Jing Feng, Bettina Konte, Son T. Mai, and Claudia
Plant. Relevant overlapping subspace clusters on categorical
data. In KDD, pages 213–222, 2014.
[11] Spiros Papadimitriou, Hiroyuki Kitagawa, Phillip B. Gibbons, and Christos Faloutsos. Loci: Fast outlier detection
using the local correlation integral. In ICDE, pages 315–326,
2003.
[12] J. Rissanen. Modeling by shortest data description. Automatica, 14(5):465 – 471, 1978.
[13] Koen Smets and Jilles Vreeken. The odd one out: Identifying and characterising anomalies. In SDM, pages 804–815,
2011.
[14] Ye Wang, Srinivasan Parthasarathy, and Shirish Tatikonda.
Locality sensitive outlier detection: A ranking driven approach. In ICDE, pages 410–421, 2011.
[15] Weng-Keen Wong, Andrew W. Moore, Gregory F. Cooper,
and Michael M. Wagner. Rule-based anomaly pattern detection for detecting disease outbreaks. In AAAI/IAAI, pages
217–223, 2002.
[16] Tengke Xiong, Shengrui Wang, André Mayers, and Ernest
Monga. A new mca-based divisive hierarchical algorithm
for clustering categorical data. In ICDM, pages 1058–1063,
2009.