メモリ効率の良いトラフィック監視を可能にするSketch技術をまとめる（1/？）

はじめに

本記事は効率的なインターネットトラフィック情報監視技術であるSketch技術について，論文を読んで勉強したものです．実際のトラフィック監視業務や理論的背景となる諸定理の厳密な定義に明るくないため，誤ったことを書いている場合にはご指摘いただけますと幸いです．勉強しなおし，可及的速やかに対処いたします．
本記事では，ネットワークトラフィック監視に特化した手法ではなく，Sketch手法として有名なCount-min Sketch[1]を追い，Sketchの基本的事項についてまとめます．

ネットワークトラフィックの監視

統計量

ネットワークトラフィック監視の文脈では，トラフィックの統計情報を用いて異常や攻撃の検知を行います．インターネットが普及している昨今，ネットワークトラフィックは非常に大規模なデータストリームであるため，1パケットずつ監視を行うのは現実的ではありません．
そこでトラフィックを統計情報という縮約された情報に落とし込んで監視することが一般的となっています．
また到着する全てのパケットを対象に計算するのではなく，NetFlowやsFlow，一度サンプリングされたデータを以降の監視対象としそれ以外は無視するSample & Hold[2]，サンプリングに優先順位を付けるPriority Sampling[3]などを用いて計算対象となるパケットを減らすことなども行われています．

ここで統計情報というのは，例えば，パケットレートや，データレート，エントロピー（平均情報量）などです．

パケットレートやデータレートが，パケット量やデータ量の異常度を測るのに用いられることは容易に想像できると思うのですが，エントロピーは聞きなれない言葉ではないでしょうか．

エントロピーは主にDDoS攻撃やポートスキャンなどの攻撃を検知するためによく用いられます．

エントロピーは次の計算式で算出される値で，情報源の出現頻度の偏りを測るのに用いられます．ここで， $N$ は情報源の総数， $p(x_{i})$ は情報源 $x_{i}$ の出現確率です．

$E = - \sum_{i}^{N}p(x_{i}) \log p(x_{i})$

しかし当然全てのIPアドレスの真の出現確率は分からないので，実際には，ある単位時間（ウィンドウサイズ）に観測・サンプリングされたデータを使って以下のように計算します．ここで， $M$ はウィンドウサイズ内に観測されたパケットの総数， $X$ はウィンドウサイズ内で観測された情報源の集合， $m_{j}$ は，情報源 $j$ の出現回数です．

$E = - \sum_{j \in X}\frac{m_{j}}{M} \log \frac{m_{j}}{M}$

エントロピー値には，出現頻度がある情報源に偏っていると値が小さくなり，逆に分散されていると値が大きくなるという特徴を持っています．
例えば，DDoS攻撃が行われると，一般的には大量の異なるホストからの攻撃トラフィックが流入するのですが，情報源を送信元IPアドレスや宛先IPアドレスに設定したエントロピー値を監視することで，送信元IPアドレスが異常に分散していないか，または宛先IPアドレスが異常に集中していないかが分かります．

問題点

ネットワークトラフィックから統計量を計算する時に問題となるのは，メモリ効率です．

例えば，エントロピー値は情報源の確率密度分布（ここでは単にヒストグラムを仮定）を用いて計算されますが，これを実現するにはIPアドレスをキーにしてそのIPアドレスの出現数をデータとして保持しておく必要があります．

しかしIPv4アドレスは全部で $2^{32}$ 種類あり，かつ，大量のデータが到着することが予想されます．

そのため，全てのIPアドレスに対応可能な形式を単純に実装してしまうと，メモリ効率が悪くなってしまいます．

そこで考えられたのが，Sketchデータ構造の導入です．Sketchというデータ構造を用いると，メモリの使用量を抑えられ，次の章で示すように利用するメモリ量を事前に把握できます．これによって多くの場合はKB（キロバイト），多くてもMB（メガバイト）のデータ量でトラフィックを監視することが可能となります．

Sketch技術はネットワークトラフィック用に提案されたものではありませんが，今後，Sketch技術とは，ネットワークトラフィック監視にSketchデータ構造を用いている技術全般を指すことにします．

Sketchデータ構造

基本形式

Sketchデータ構造は，キーの候補数（カテゴリ数）が多い場合に使われるデータ構造[4]で，データストリームを計算対象とする，Streaming Alorithmの一種です．

Sketchは以下に示すように $H \times K$ 個の二次元カウンタで構成されたデータ構造です． $H$ はハッシュ関数の個数で， $K$ はハッシュ関数の値域の最大値です．

Sketchの配列を $S$ で表すとすると， $S[i][j]$ のカウンタは「 $i$ 番目のハッシュ関数を用いてハッシュ値 $j$ が出力される $key$ が何個観測されるか数えるためのカウンタ」となります．

Sketchはカウンタ（たいていはintを利用）を利用するので，カウンタ変数の型とSketchのサイズから，使用するメモリ量が事前に分かります．
理論的な空間計算量はSketchの設計によって異なります．例えば以下で説明しているCount-min SketchはPoint Query（あるキー値のカウンタ値がどのくらいあるか知るための操作）をするためだけでは，空間計算量は $O(\frac{1}{\epsilon^{2}} \log \frac{1}{\delta})$ となります．

（追記：2020/07/26 『メモリ効率の良い』と言いつつ空間計算量の話が明示的に書かれていなかったので追記いたしました）

f:id:madomadox:20200411194140p:plain — Sketchデータ構造

Update操作

データ構造に $(key, val)$ の組のデータを挿入することを考えます（以降この操作をUpdate操作と呼ぶことにします）．
ここで $key$ はIPアドレス， $val$ はIPアドレスの出現回数です．（ところで $val$ を計算するのにSketchが新たに必要となり堂々巡りになりそうな気がしますが，運用上，出現回数を数えることはせずに， $val$ を1に設定して，新たにパケットが到着するごとに更新しているのだと思います）．
updateは， $i = 0, 1, 2, ..., H$ について，次に示す手順で行われます．

入力となる $key$ を，ハッシュ関数 $h_{i}$ でハッシュ化し， $j = h_{i}(key)$ を取得
得られたデータ $j$ に対応するカウンタ $S[i][j]$ を $val$ だけカウントアップ

f:id:madomadox:20200411192738p:plain — Update操作

この更新方法により，管理しておくべきカテゴリの数が高々 $K$ 個に圧縮されます．
また，レアなカテゴリは基本的に寄与が少ない割にヒストグラムを無駄に大きくしてしまいがちなのでどこかに混ぜ込んでしまったりするのですが，Sketchだとそれが自然に行われるので，そういった点でも都合が良いと言えます[4]．
ここで，ハッシュ関数としてどのようなものを用いるかという話ですが，基本的には以下の式を用います．

$h_{i}(key) = a_{i} \times key + b_{i} \mod K$

ここで， $a_{i}$ と $b_{i}$ は整数であり，値域は素数 $p$ を使い， $[1,p]$ です．（ハッシュ関数やパラメータの選び方は手法によって異なります．）

Query操作

次にこのSketchを利用して， $key$ に対応する $val$ を取得します（以降この処理をQueryと呼びます）．ハッシュ値が，値域 $K$ によっては衝突する可能性があるため，どのような操作で取り出せばより推定値として適切かを考える必要があります．

今回は，Count-min SketchのQueryを考えてみます．Count-min SketchのQueryは以下の式で表現される操作を行います．

$\displaystyle Q(key) = \hat{v}_{key} = \min_{i} S[i][h_{i}(key)]$

文字に書き下すと，1行目から $H$ 行目まで $h_{i}(key)$ を計算した時の，対応するカウンタ値 $S[i][h_{i}(key)]$ の最小値を， $key$ に対応する $val$ の推定値として出力します．
この操作の意味を直感的に考えると「カウント数が最小値よりも大きい場合は確実に衝突しているので，より衝突の可能性の少ない最小値を推定値として採用する」となります．
この推定値がどのくらい良いかというのは，次の定理で示されています[1]．ここで， $\|x\|_{1}$ は $x$ のL1ノルムを指します．

$key$ の真の $val$ となる値を $v_{key}$ ，Queryによる推定値を $\hat{v}_{key}$ とすると， $v_{key} \leqq \hat{v}_{key}$ かつ $(1-\delta)$ の確率で $\hat{v}_{key} \leqq v_{key} + \epsilon \|v\|_{1}$ を満たす．

Count-min Sketchは $\epsilon$ と $\delta$ の2つのパラメータを持っており，Sketchのサイズは $w \times d = \frac{e}{\epsilon} \times \ln(\frac{1}{\delta})$ で決まります．なお， $e$ はネイピア数です．
定理から， $\delta$ と $\epsilon$ を小さくしていけば，比較的高い確率で真の値に近づいていくことが分かります．しかしその分Sketchのサイズが大きくなってしまうのでバランスを調整する必要があります．

実際に簡単にプログラムを作成して確認してみます．以下はSketchに $(10,1), (150,2), (132,3), (140, 4), (13, 5), (2, 6)$ の6つの $(key, val)$ の組を挿入し， $key=2$ の， $val=6$ を取得できたか試してみたものです．
cmsketch.cpp

#include <iostream>
#include "cmsketch.hpp"

int main()
{
    CMSketch cm_sketch(0.05,0.01);
    cm_sketch.setHash(173);
    
    cm_sketch.update(10,1);
    cm_sketch.update(150,2);
    cm_sketch.update(132,3);
    cm_sketch.update(140,4);
    cm_sketch.update(13,5);
    cm_sketch.update(2,6);
    
    cm_sketch.printSketch();
    int q = cm_sketch.query(2);
    std::cout << q << std::endl;
}

cmsketch.hpp

#ifndef _CMSKETCH_H
#define _CMSKETCH_H

#include <iostream>
#include <vector>
#include <random>
#include <limits>
#include <algorithm>
#include <cmath>

class CMSketch
{
    public:
        CMSketch(float epsilon, float delta);
        void setHash(int prime);
        void update(int key, int value);
        int query(int key);
        void printSketch();

    private:
        int prime;
        int h;
        int d;
        std::vector<std::vector<int>> counter;
        std::vector<int> hash_coef;
        std::vector<int> hash_intercept;
};

CMSketch::CMSketch(float epsilon, float delta)
{
    h = ceil(log(1.0/delta));
    d = ceil(exp(1.0)/epsilon);

    counter.resize(h);
    for(int i = 0; i < h; i++)
    {
        std::vector<int> tmp(d,0);
        counter[i] = tmp;
    }

    hash_coef.resize(h);
    hash_intercept.resize(h);
}

void CMSketch::printSketch()
{

    for(int i = 0; i < h; i++)
    {
        for(int j = 0; j < d; j++)
            std::cout << counter[i][j] << "," ;

        std::cout << std::endl;
    }
}

void CMSketch::setHash(int prime)
{

    std::random_device seed_gen;
    std::default_random_engine engine(seed_gen());

    std::uniform_int_distribution<> dist(0,prime);
    int row_size = counter.size();
    
    for(int i = 0; i < h; i++)
    {
        hash_coef[i] = dist(engine);
        hash_intercept[i] = dist(engine);
    }
}

void CMSketch::update(int key,int value)
{
    
    for(int i = 0; i < h; i++)
    {
        int hash = (hash_coef[i] * key + hash_intercept[i]) % d;
        counter[i][hash] += value;
    }
}

int CMSketch::query(int key)
{
    int query = std::numeric_limits<int>::max();

    for(int i = 0; i < h; i++)
    {
        int hash = (hash_coef[i] * key + hash_intercept[i]) % d;
        query = std::min(query,counter[i][hash]);
    }

    return query;
}
#endif //_CMSKETCH_H

Count-min Sketchのパラメータ $\epsilon$ と $\delta$ は，それぞれ $0.05, 0.01$ ，そして $p=173$ として試してみました．
実行結果の一例を以下に示します．

f:id:madomadox:20200516204342p:plain — 実行結果

上の二次元に羅列されている数値がSketchのカウント数を表示したもので，一番下の数字が推定値として出力された値です．
Sketchを見てみると，2行目に「１１」という文字が見えます．これは，2と13のハッシュ値が衝突してしまっていることが原因です（ $key=2$ は $val=6$ ， $key=13$ は $val=5$ のため）．しかし衝突が発生していない行があるので，各行について $key$ のハッシュ値が示すカウンタ値（6,11,6,6,6）の最小値を取ると， $key=2$ の出現回数として，正しい結果の6が出力されています．

課題

しかし，Sketchデータ構造を用いたネットワークトラフィックの統計量の計算には，次の課題があります．

1つ目は統計量の精度が低くなることです．ハッシュを用いて確率的に処理を行う関係でどうしても実際の統計量との誤差が生じてしまいます．

2つ目はホストの特定ができないことです．異常検知ではその異常の原因となるホストのIPアドレスを特定する必要があるのですが，Sketchではそれができません．なぜならハッシュ関数を用いてIPアドレスをハッシュ化したものを用いるためです．~~ハッシュ関数は一方向関数なので，ハッシュ値からIPアドレスへの逆変換ができません．~~（追記：2020/07/26 ハッシュ関数の概念はあくまで「データ構造とアルゴリズム」で出てくるものであり，暗号学的ハッシュ関数に必要となる一方向性という性質にはそぐわないと考えたため訂正いたします．ただしハッシュ値からIPアドレスに変換するのはそのままでは困難であることは変わらないため，工夫が必要となります）

この二つの課題を解決するため，研究者はより精度の高い統計量を計算したり，ホストの特定が可能となるような手法を研究しています．

まとめ

大量にデータが観測されるネットワークトラフィック監視において，パケット単位で監視するのではなく，統計量を計算してトラフィック情報を縮約する必要があります．
しかし，IPアドレスという，考えられるキーの数が非常に多いデータを対象にした計算を行うとなると，単純な実装ではメモリ効率が悪くなります．
そこで，Streaming Algorithmの一種であるSketchデータ構造を利用し，メモリ効率の良いネットワークトラフィック監視手法が提案されています．
今回は有名な手法，Count-Min Sketchを実装して，Sketchの基本を確認しました．
次回以降は，実際にネットワークトラフィック監視に特化したSketch技術をまとめていきます．
どこかで，今回引用させていただいたサンプリング手法についても紹介していこうと思います．

（2021/04/11 追記）
1個書きました。
madomadox.hatenablog.com

参考文献

[1] Cormode, Graham, and S. Muthukrishnan. “An Improved Data Stream Summary: The Count-Min Sketch and Its Applications,” Journal of Algorithms & Computational Technology Vol. 55, No.1, pp. 58–75, 2005.
[2] Estan, Cristian, and George Varghese. “New Directions in Traffic Measurement and Accounting,” In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM ’02. New York, NY, USA, pp. 323–36, 2002.
[3] Noga Alon, Nick Duffield, Carsten Lund, and Mikkel Thorup. "Estimating arbitrary subset sums with few probes," In Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (PODS ’05). Association for Computing Machinery, New York, NY, USA, 317–325, 2005.
[4]機械学習のための特徴量エンジニアリング著 Alice Zheng, Amanda Casari，訳株式会社ホクソエム，株式会社オライラー・ジャパン，2019.