プログラマブルデータプレーンのためのプログラミング言語P4について勉強する

はじめに

SIGCOMMの論文を読んでいてP4というプログラミング言語を知りました。
面白そうだったので勉強しようと思ったのですが、どこまで環境構築すれば動くようになるのかいまいちやり方が分からず、思い立ってはやめを繰り返していました。
2021年は心機一転,そろそろ書き方は知っておきたいと思い本腰を入れて勉強することにしました。
そんな折、日本P4ユーザ会様がP4のハンズオン勉強会をオンラインで開催されていたため、そちらにも参加させていただき、理解を深めることができました。
connpass.com

本記事の内容は以下のチュートリアルを進めていくにあたって,理解した内容を自分なりにまとめたものになります。
誤りがございましたらご指摘いただけますと幸いです。可及的速やかに修正いたします。
github.com

[追記 2021.08.19 細かなtypoや言い回しは特に断らずちょこちょこ直していますが、明らかに誤解を生みそうな文章、認識が完全に誤っていた文章に関しては追記を付して変更・編集しています]

[追記 2021.08.20 本記事はP4の言語仕様ver1.2.1時点のものを参照して作成しました。現在はver1.2.2が策定されており、一部異なる可能性がございます]
https://p4.org/p4-spec/docs/P4-16-v1.2.2.pdf

SDN (Software Defined Network)

データプレーンとは何かを説明するにあたり、まずは簡単にSDNについて紹介します。

SDNとは、Software Defined Networkの略で、ネットワークの設定・構成等を柔軟に動的に制御するための技術です。

SDNでは、従来のネットワークスイッチのルーティングを、ルーティングのルールを決定する機能と、パケット転送などのパケットを処理する機能に分離します。
このそれぞれのモジュールを、コントロールプレーン、データプレーンと呼びます。コントロールプレーンは中央集権的にデータプレーンとなるネットワーク機器を管理することができます。

従来技術では、ネットワーク機器ごとに異なるルーティングルールが設定されているため、統括的な管理には手間がかかります。

データプレーンは各々フローテーブルを持っており,到着したパケットの処理をどうするべきか、フローテーブルを参照して決定します。このフローテーブルはコントロールプレーンが制御しています。
例えば、OpenFlowでは、フローテーブルはヘッダ情報、カウンタ、アクションが定義されています。

SDNでは、コントロールプレーンを介してフローテーブルをデータプレーンに伝えることにより、複数のネットワーク機器に設定を反映することができます。

このようにして、まるでソフトウェア的にネットワークの構成・設定をプログラミングできるように扱えます。

P4について

P4とは、データプレーンがどのようにパケットを処理するかを記述するために開発されたプログラミング言語です。P4という名前は、論文のタイトルにもなっているProgramming Protocol-independent Packet Processorsの略語になっています。

Bosshart, Pat, Dan Daly, Glen Gibb, Martin Izzard, Nick McKeown, Jennifer Rexford, Cole Schlesinger, et al. 2014. “P4: Programming Protocol-Independent Packet Processors.” SIGCOMM Comput. Commun. Rev. 44 (3): 87–95.
https://dl.acm.org/doi/10.1145/2656877.2656890

従来のネットワーク機器のパケット処理に関する機能は、ASICの設計に依存しており、ASICの持つ機能しか利用できないという制約がありました。
この機能を変更しようとなると、ASICから再設計する必要があり、多大なコストがかかります。

P4では、P4に対応している機器であれば、機器の特性に依らずデータプレーンの機能をプログラミングすることができます。

P4の言語仕様にはP4-14とP4-16が存在します。これはオリジナルのP4に改良を加えていったものがP4-16となっており、旧来のP4をP4-14と呼ぶようになったようです。現在はP4-16での開発が主流です。

PISA (Protocol Independent Switching Architecture)

P4では以下のようなパイプライン処理を持つアーキテクチャを想定し、パイプラインの各ブロックの処理をプログラミングしていくことになります。

「Parser」→「Match-Action Unit」→「Deparser」

このアーキテクチャPISA(Protocol Independent Switching Architecture)と呼ばれています。

ブロックの意味は、それぞれ以下の通りです。

  • Parser: ヘッダ情報を解析し、その情報をメタデータとしてパイプラインの各ブロックに渡す。
  • Match-Action Unit: 得られたメタデータを用いてフローテーブルを参照し、対応する処理(アクション)を実行する
  • Deparser: ヘッダを再構成し、パケットを送出する

ターゲットとアーキテクチャモデル

P4でプログラミングするデータプレーン機器のことをターゲットと呼びます。
ターゲットとなるハードウェアに関しては、FPGAやASICなどがあります。また、P4の仕様に完全準拠するBehavioral-Model (BMv2)というP4対応の簡易的なソフトウェアスイッチもあります。これはP4開発の練習やテストのためのターゲットであり、性能は控えめになっています。

P4でPISAをプログラミングするにあたって,「プログラミングが可能なブロック」「各ステージの持つインターフェイス」「各ステージの機能」を定義したものをアーキテクチャと呼びます。

Specifically, arch.p4 defines what P4-programmable blocks are available, the interface for each stage, and the capability for each stage. Who is responsible for writing such an architecture program? The P4 Consortium is one source of such a definition, but different switch vendors have created their own architecture specifications to closely describe the capabilities of their switching chips.

Chapter 4: Bare-Metal Switches — Software-Defined Networks: A Systems Approach Version 2.0-dev documentation

アーキテクチャは基本的にプログラミング対象となるデータプレーン機器のベンダが提供するファイルです。P4でデータプレーンの機能をプログラミングする際は、ターゲットがサポートするアーキテクチャを利用する必要があります。

チュートリアルではBMv2をターゲットとして利用しています。
ちなみにBMv2にはいくつかのバリエーションがあるのですが、チュートリアルなどで利用されているsimple_switch、simple_switch_grpcは、v1model.p4というアーキテクチャを利用できます。
github.com

アーキテクチャモデルは他にPSA (Portable Switch Architecture)があります。
これは、汎用的に利用できることを目的にしたモデルで、現在開発が進められています。
[追記 2021.08.20 曖昧かつ誤解のあった記述であったため文章を再考しました]
ベンダごとにアーキテクチャが異なるとプログラムの書き方が変わってしまうため、汎用性がありません。
PSAでは異なるデバイスに対しても共通の方法でプログラミングできるように、P4 Architecture Working Groupで標準化が進められているものです。
2021年8月現在はver 1.1が策定されています。


https://p4lang.github.io/p4-spec/docs/PSA.pdf

P4言語を書いてみる

定義ファイルのインクルード

P4言語は、コアとなるプログラムをインクルードするところから始まります。
最初の部分を見てみると、以下のようになっています。C言語に似た書き方です。

#include <core.p4>
#include <v1model.p4>

core.p4はコアとなるヘッダファイルであることは推察されますが、v1model.p4は何でしょうか。
これは、アーキテクチャの定義ファイルです。
今回はBMv2をターゲットとするので、対応しているアーキテクチャの1つであるv1model.p4を利用します。
実際には、ネットワーク機器のアーキテクチャに合わせた定義ファイルをインクルードしてくることになります。

変数の定義

変数は一般的なプログラミングと同様の方法で定義することができます。
型もいくつかありますが、そのうちよく利用されるものを以下に列挙します。
また、typedefを用いて変数の型に別名をつけることも可能です。

  • bit<n>: n bitで表現される符号なしinteger
  • int<n>: n bitで表現される符号つきinteger
  • varbit<n>: n bitで表現されるbitstring
  • bool: bool型
  • header: 順序付きのデータコレクション。ヘッダ情報を表現するときに用いる。isValid()というメソッドで検証することができる。
  • struct: 順序なしのデータコレクション。

上の情報を使い、イーサネットヘッダを変数として定義すると、以下のようになります。

typedef bit<32> macAddr 
header ethernet_t {
   macAddr dst;
   macAddr src;
   bit<16> type;
};

パイプラインの実装方法

各ブロックをどのように定義し実装するべきかに関しては、アーキテクチャの定義ファイル(ここではv1model.py)に記載されています。
tutorials/p4-cheat-sheet.pdf at master · p4lang/tutorials · GitHub

v1model.p4ではパイプライン処理は以下のように定義されています。したがって、v1modelアーキテクチャのデータプレーンをプログラミングする際には、以下の構造にしたがってパイプラインの処理を実装していくことになります。

// v1model pipeline elements
parser Parser<H, M>(
    packet_in pkt,
    out H hdr,
    inout M meta,
    inout standard_metadata_t std_meta
);

control VerifyChecksum<H, M>(
    inout H hdr,
    inout M meta
);

control Ingress<H, M>(
    inout H hdr,
    inout M meta,
    inout standard_metadata_t std_meta
);

control Egress<H, M>(
    inout H hdr,
    inout M meta,
    inout standard_metadata_t std_meta
);

control ComputeChecksum<H, M>(
    inout H hdr,
    inout M meta
);

control Deparser<H>(
    packet_out b, in H hdr
);

// v1model switch
package V1Switch<H, M>(
    Parser<H, M> p,
    VerifyChecksum<H, M> vr,
    Ingress<H, M> ig,
    Egress<H, M> eg,
    ComputeChecksum<H, M> ck,
    Deparser<H> d
);

各ブロックの実装方法

それぞれの機能をどのようにP4で実装していくかを見ていきます。
なお、タイトルに*が付いているものは少し細かい話になるので、まずは大まかな流れを知りたいという人は飛ばしていただいて問題ないという意味で付けています。

Parser

Parserは,届いたパケットのヘッダ情報を解析して,のちのMatch-Action Pipelineで利用するための情報を取得します.例えば,MACアドレスIPアドレスなどです.
これらのデータは,パイプラインで利用できるような形式(メタデータ)として抽出され、Match-Action Pipelineに渡されていきます。

parse

Parserをプログラミングする箇所はparserブロックです。

parseブロックでは、startという初期状態と、acceptrejectの2種類の終了状態が定義されたステートマシンを想定しています。
acceptは「パースに成功した」、rejectは「(パケットにエラーがあるなどして)パースに失敗した」を指します*1

parseブロックは、必ずstartから始まってからどちらかの終了状態に到達しなければなりません。ただし、初期状態と終了状態以外の状態は、stateステートメントを用いて自分で定義することができます。

一般的に、パケットの各種ヘッダ(イーサネットヘッダ、IPヘッダなど)を抽出するための状態をそれぞれ定義して、start→各種ヘッダの解析状態→acceptと状態を遷移させていくことで、ヘッダを順番に抽出していきます。

P4では、transitionステートメントで状態を遷移させていきます。以下はtransitionの使い方を示したものです。ここでは単純にstartから直接acceptへと状態を遷移します。
特に処理を記述していないので何も実行されません。

parser MyParser(packet_in packet,
                out headers hdr,
                inout metadata meta,
                inout standard_metadata_t standard_metadata) {

    state start {
        transition accept
    }
}
select

一般的には、selectステートメントを併用して状態遷移を制御し、処理を記述していくことになります。
selectステートメントは一般的なプログラミング言語のswitch-case文の使い方に非常に似ています。

実際に、TutorialsのBasicForwardingのsolutionよりソースコードを引用させていただき、状態遷移制御のやり方を確認します。
(コメントにつきましては著者が追加しております。)
github.com

parser MyParser(packet_in packet,
                out headers hdr,
                inout metadata meta,
                inout standard_metadata_t standard_metadata) {

    state start {
        transition parse_ethernet;  //1. 
    }

    state parse_ethernet {
        packet.extract(hdr.ethernet); //2. 
        transition select(hdr.ethernet.etherType) { //3. 
            TYPE_IPV4: parse_ipv4;  //4. 
            default: accept; //5. 
        }
    }

    state parse_ipv4 { 
        packet.extract(hdr.ipv4); //6. 
        transition accept; //7. 
    }

}
  1. stateステートメントで定義した「parse_ethernet」に状態を遷移させる
  2. parse_ethernet状態に遷移し、まずイーサネットヘッダを抽出する
  3. selectステートメントイーサネットヘッダのイーサネットタイプを確認する
  4. もしもイーサネットタイプがTYPE_IPV4(プログラム上部で0x800と定義されています)であれば、parse_ipv4に遷移
  5. TYPE_IPv4でなければ、これ以上抽出したいヘッダ情報はないので、accept状態に遷移してパース終了
  6. parse_ipv4状態に遷移し、IPヘッダを抽出する。
  7. これ以上抽出したいヘッダ情報は無いので、accept状態に遷移してパース終了

ちなみにこちらはIPヘッダのみを利用するという前提に立っています。それ以外のヘッダを抽出したい場合は適宜状態を定義して遷移させていくことになります。

Match-Action Unit

Parserでヘッダ情報を取り出しました。このヘッダ情報にはフローエントリのkeyとなりうる情報が含まれています。keyというのは送信元IPアドレスなどのことです。

次にやりたいことは、そのkeyに対応するactionを実行することです。すなわち、送信元IPアドレスがこうだったら転送、違っていれば廃棄、というようなことをしたいわけです。

P4では、keyとactionを定義していくことになります。

control

Match-Action Unitはマルチステージ型で構成されており、各ステージに固有のメモリとALUが搭載されているのですが、各ステージはcontrolブロックを用いて定義することができます。parserブロックで抽出されたメタデータは、controlブロックに渡されています。

control MyIngress(inout headers hdr,
                  inout metadata meta,
                  inout standard_metadata_t standard_metadata) {
 ...
}
方向*

controlに渡されている引数には、inoutというものが付けられています。これはデータの方向を示す型です。

controlや後述のactionでは、DirectionalなものとDirectionlessなものの2種類の変数を利用可能です。Directionalなものはデータプレーンから(すなわちパイプライン上から)送られて来るデータ、Directionlessなものはコントロールプレーンから来るデータです。

Directionlessなものは特に問題無いのですが、Directionalなデータに関しては別途in, out, inoutの3種類の方向を付与されます。
inはread-onlyで変更不可能なデータ、outは変更される予定のあるデータ*2につけられます。
すなわち基本的には、inとなっているデータは代入式の右側、outとなっているデータは代入式の左側で出てくることになります。

inoutはinputとしてもoutputとしても利用されるデータであり、上の例と照らし合わせれば、代入式の右側にも左側にも来ることができます。例えば、値を入れ替えるswap処理や、インクリメント、デクリメント処理をする時などに利用されます。

Directionlessなデータに関しては後述のactionにて説明します。

action

acitionの処理を記述するには、actionステートメントを利用します。

構文としては、以下のとおりです(Parserと同じくbasic.p4より引用)。一般的なプログラミング言語で言う関数定義と類似しています。

control MyIngress(inout headers hdr,
                  inout metadata meta,
                  inout standard_metadata_t standard_metadata) {

    action drop() { //1.
        ...
    }
    
    action ipv4_forward(macAddr_t dstAddr, egressSpec_t port) {  //2.
        standard_metadata.egress_spec = port;
        hdr.ethernet.srcAddr = hdr.ethernet.dstAddr;
        hdr.ethernet.dstAddr = dstAddr;
        hdr.ipv4.ttl = hdr.ipv4.ttl - 1;
    }
 ...
}

1. drop()というactionを定義します。
2. ipv4_forward()というactionを定義します。データプレーンのどのポートからパケットを送出するかを決定したあと、送信元MACアドレスhdr.ethernet.dstAddr(データプレーン自身)に、宛先MACアドレスをフローテーブルに従って決定された転送先dstAddr、そしてttlを1つ減らします(つまりL2での通常のルーティングの実装です)。

standard_metadata_tは、アーキテクチャ(v1model.p4)で定義されているデータで、以下があります。
egressSpec_tは、データプレーンの持つポート(ネットワークスイッチの文脈でのポート)です。

struct standard_metadata_t {
    bit<9> ingress_port;
    bit<9> egress_spec;
    bit<9> egress_port;
    bit<32> clone_spec;
    bit<32> instance_type;
    bit<1> drop;
    bit<16> recirculate_port;
    bit<32> packet_length;
    bit<32> enq_timestamp;
    bit<19> enq_qdepth;
    bit<32> deq_timedelta;
    bit<19> deq_qdepth;
    bit<48> ingress_global_timestamp;
    bit<48> egress_global_timestamp;
    bit<32> lf_field_list;
    bit<16> mcast_grp;
    bit<32> resubmit_flag;
    bit<16> egress_rid;
    bit<1> checksum_error;
    bit<32> recirculate_flag;
}
Directionlessな変数*

actionに渡している引数には今回は方向型が付けられていません。

方向型が付けられない、Directionlessなデータとしては次のような場合があります。

  1. コンパイル時に決定するデータ
  2. actionに渡されるパラメータのうち、コントロールプレーンからのみセットできるデータ
  3. actionに渡されるパラメータのうち、他のアクションによってセットされるデータ(inとして扱われる)

今回のmacAddr_t dstAddr、egressSpec_t portに渡される具体的な値は、pod-topo/s*-runtime.jsonで指定されています。
つまりこれは2.の「コントロールプレーンからセットされるデータ」であるため方向型が付けられていないということになります。
コントロールプレーンに関しては後述のP4Runtimeにて説明させていただきます。

table

keyとactionを定義するために、tableステートメントを利用します。

以下が、Parserと同じbasic.p4より引用したソースコードです。

control MyIngress(inout headers hdr,
                  inout metadata meta,
                  inout standard_metadata_t standard_metadata) {

    action drop() {
        ...
    }
    
    action ipv4_forward(macAddr_t dstAddr, egressSpec_t port) {
        ...
    }
    
    table ipv4_lpm {  //3.
        key = { //4.
            hdr.ipv4.dstAddr: lpm;
        }
        actions = {  //5. 
            ipv4_forward;
            drop;
            NoAction;
        }
        size = 1024;
        default_action = drop();
    }
 ...
}

3. tableステートメントを用いてテーブル情報を定義します。
4. keyとして、IPv4の宛先IPアドレスを利用します。lpmとは、logest prefix matchの略であり、マッチングのルールとして、IPアドレスのビット列の一致する長さが最長の経路を選択するという意味です。core.p4で定義されています。*3
5. actionsとして、ipv4_forward, dropを登録します。

applyブロック

tableで定義した情報を実際に適用するため、applyブロックを利用します。
controlブロックには、applyブロックがなければいけません。*4
[追記 2021.08.19 まるでその根拠があると断定しているような書き方になっていたので、大幅に編集しました]

tableで定義した情報を実際に適用するには、tableが持つapply()メソッドを呼び出します。
tableの持つapply()メソッドを呼び出すと、そのtableに格納されているフローテーブルエントリから、キーにヒットするものを検索し、対応するactionを実行します(言語仕様の13.2.3参照)。

control MyIngress(inout headers hdr,
                  inout metadata meta,
                  inout standard_metadata_t standard_metadata) {

    action drop() {
        ...
    }
    
    action ipv4_forward(macAddr_t dstAddr, egressSpec_t port) {
        ...
    }
    
    table ipv4_lpm {
        ...
    }
    
    apply {
        if (hdr.ipv4.isValid()) { //6
            ipv4_lpm.apply();
        }
    }
}

6. applyブロック内でテーブル情報を適用します。isValid()によってヘッダを検証し、もし有効なものであればテーブルの持つapply()メソッドで実際にテーブル情報を適用します。

apply()メソッドを呼び出しているのは、applyブロック内です。このapplyブロックは何者でしょうか。

controlブロックには、applyブロックがなければいけないと書かれている文献もありましたが、言語仕様にはそのような内容は明示的に書かれていません。

そのため、もう少し突っ込んで調べました。

言語仕様のApplendix Fを見ると、

Actions may be called directly from a control apply block.

とあります。
また、その下の表を見ると、control apply block内では、「control」、「extern」、「table」、「action」、「function」を呼び出すことが可能と書いており、さらに「table」を呼び出せるのは、control内のapplyブロックのみということが書かれています。
そして、その少し前に、

Calling a parser, control, or table means invoking its apply() method.

とあります。
上記を踏まえると、定義したtableをapply()メソッドで呼び出すためには、controlブロック内でapplyブロックを用意してそこに記述しなくてはならない、という認識のほうが正しいかもしれません。
(controlブロックにapplyブロックがなければならない、というのは、tableを用意してわざわざそれを利用しないことはない、というような意味かもしれません。もう少し調査します。)


ところで、宛先IPアドレスがどうだったらipv4_forwardを実行し、dropを実行するのかが分かりません。実際の対応付けはどこでやっているのでしょうか。

対応付けに関しては、コントロールプレーンが定義しており、データプレーンは単にそのコントロールプレーンから渡された情報をもとに処理を行います。
コントロールプレーンがgRPCを介してデータプレーンの持つフローテーブルのエントリを更新している形です(詳しくは実験・P4Runtimeの章)。

P4で記述するのは、あくまでデータプレーンで実行される処理であり、その他のことに関してはタッチしません*5

Deparser

Deparserではヘッダを再構成してパケットを作成し、それを宛先に対して送信します。
もしもヘッダデータを書き換えているのであれば、その内容が反映されます。

以下がDeparserの例です。

control MyDeparser(packet_out packet, in headers hdr) {
    apply { //1.
        packet.emit(hdr.ethernet); //2. 
        packet.emit(hdr.ipv4); //3. 
    }
}

1. applyステートメントで実行する内容を記述します。
2. イーサネットヘッダをセットします。
3. IPヘッダをセットします。

packet_out packetはcore.p4に記述されています。packet.emtiによりヘッダ情報をシリアライズします。これでパケットのヘッダを、順番にセットしていっていることになります。

PISAブロックの適用

PISAの主要ブロックを適切に定義したあとは、これを実際に適用します。構文は下記のとおりです。*6

V1Switch(
    MyParser(),
    MyVerifyChecksum(),
    MyIngress(),
    MyEgress(),
    MyComputeChecksum(),
    MyDeparser()
) main;

これでデータプレーンのプログラミングが完成しました。

P4を実行する

実行環境の構築

P4ファイルを書き終えたので、今度はコンパイルのための実行環境を準備します。
まずは、P4をコンパイルするp4lang-p4cを以下のページにしたがってインストールします。
github.com

なお、今回は以下の環境で実験をします。
カーネルのバージョン [追記 2021.08.19 誤りがあったため修正しました。NetFliterの記事のものをコピーしたまま修正するのを忘れていました。]

<s>5.4.0-47-generic</s>
5.11.0-25-generic

OSのバージョン

Ubuntu 20.04 LTS

嬉しいことに、Ubuntu20.04であれば、リポジトリが用意されているのでここからインストールしてきます。

$ sudo add-apt-repository ppa:dreibh/ppa
$ sudo apt update
$ sudo apt install p4lang-p4c

自分の場合、元々の環境が悪かったのか、依存関係の問題でclangのインストールができず、p4lang-p4cがインストールできませんでした。
aptitudeコマンドを使うといくつか解決方法を教えてくれるのですが、libc6のバージョンを2.31-0ubuntu9.3から2.31-0ubuntu9.2にダウングレード(3を選択)したところ、うまくインストールできました。
unix.stackexchange.com

$ sudo aptitude install clang
...
 libc6-i386 : 依存: libc6 (= 2.31-0ubuntu9.2) 2.31-0ubuntu9.3 がインストール済みです
...

以下のアクションでこれらの依存関係の問題は解決されます:

     以下のパッケージを削除する:                                            
1)     libc-dev-bin [2.31-0ubuntu9.3 (now)]                                 

     以下のパッケージをインストールする:                                    
2)     libc-dev-bin:i386 [2.31-0ubuntu9.2 (focal-updates)]                  

     以下のパッケージをダウングレードする:                                  
3)     libc6 [2.31-0ubuntu9.3 (now) -> 2.31-0ubuntu9.2 (focal-updates)]     
4)     libc6:i386 [2.31-0ubuntu9.3 (now) -> 2.31-0ubuntu9.2 (focal-updates)]
5)     libc6-dbg [2.31-0ubuntu9.3 (now) -> 2.31-0ubuntu9.2 (focal-updates)] 
6)     libc6-dev [2.31-0ubuntu9.3 (now) -> 2.31-0ubuntu9.2 (focal-updates)] 



この解決方法を受け入れますか? [Y/n/q/?]y

さて、次はターゲットとなるBMv2をインストールします。
github.com

依存するパッケージが、すでにp4lang-p4cを入れた時に入っているような?と思いそのまま作業を進めたところうまく./configure -> makeができました。
パスを通すほどでもないなと思ったら、make installは行わずとも大丈夫です。

$ git clone https://github.com/p4lang/behavioral-model.git
$ cd behavioral-model

$  ./autogen.sh
$ ./configure
$ make
$ sudo make install

実際に実行する

実験用ネットワークの構築

コンパイラとターゲットをインストールできたので、実際に実験用のネットワーク環境を構築していきます。
なお、この構築方法については、下記記事を参考に書かせていただきました。
opennetworking.org

www.slideshare.net

P4環境の整ったVMなどを用意しても良いのですが、簡単に試す際にはNetwork Namespaceが利用されています。Network Namespaceとは、カーネル名前空間機能の一種であり、ネットワーク関連の機能を分離させて動作させることのできる技術です。コンテナ技術にも利用されています。

ホストマシンにBmv2をインストールしているので、今回は以下のような環境を想定しました。

まずは、host0とhost1というネットワーク名前空間を作ります。

$ sudo ip netns add host0
$ sudo ip netns add host1

続いて、ホストマシンとhost0、ホストマシンとhost1をつなぐvethペア(それぞれveth0とveth0-host、veth1とveth1-hostという名前にします)を作ります。

$ sudo ip link add veth0 type veth peer name veth0-host
$ sudo ip link add veth1 type veth peer name veth1-host

今度は、作ったvethをそれぞれのネットワーク名前空間に移します。veth0をhost0に、veth1をhost1に移します。

$ sudo ip link set veth0 netns host0
$ sudo ip link set veth1 netns host1

ここまでくれば、あとは必要なインターフェースにIPアドレスを付与して、up状態にします。

$ sudo ip netns exec host0 ip addr add 10.0.0.1/24 dev veth0
$ sudo ip netns exec host1 ip addr add 10.0.1.1/24 dev veth1

$ sudo ip netns exec host0 ip link set veth0 up
$ sudo ip netns exec host1 ip link set veth1 up

$ sudo ip link set dev veth0-host up
$ sudo ip link set dev veth1-host up
P4プログラムのコンパイル

次に、P4プログラムをコンパイルします。
コンパイルするプログラムは以下です。
github.com

p4cコマンドでコンパイルし、コンパイルに成功すると、basic.p4iファイルと、basic.jsonファイルが生成されます。

p4c basic.p4
ソフトウェアスイッチの起動とテーブル情報の書き込み

次に、P4プログラムの書き込みのターゲットとなるソフトウェアスイッチを起動します。
これは、simple_switchプログラムを使います(場所はbehavioral-model/targets/simple_switch)
iオプションで、スイッチのポートがどのネットワークインタフェースに紐づくかを指定できます。
ホストとhost0の通信路であるveth0-hostをポート0に、ホストとhost1の通信路であるveth1-hostをポート1に設定します。
log-consoleオプションをつけることで、ログが端末に表示されるようになります。

$ sudo ./simple_switch -i 0@veth0-host -i 1@veth1-host --log-console <p4cで生成されたjsonファイルのパス>

今度は、CLIプログラムでソフトウェアスイッチにテーブル情報を書き込みます。
プログラムは/behavioral-model/targets/simple_switchにあります。

コマンド名はhelpで確認でき、またコマンドの使い方は help <コマンド名> で確認できます。

./runtimeCLI

     :
     :

RuntimeCmd: help

Documented commands (type help <topic>):
========================================
act_prof_add_member_to_group       set_crc16_parameters
     :
     :

RuntimeCmd: show_tables
MyIngress.ipv4_lpm             [implementation=None, mk=ipv4.dstAddr(lpm, 32)]

RuntimeCmd: show_actions
MyIngress.drop                 []
MyIngress.ipv4_forward         [dstAddr(48),	port(9)]
NoAction                       []

早速、ソフトウェアスイッチにテーブル情報を書き込みます。
スイッチに「宛先IPアドレスが10.0.0.1宛てのパケットが来たら、host0のMACアドレスに転送」、
「10.0.1.1宛のパケットが来たらhost1のMACアドレスに転送」というルールを書き込むことにします。

このような場合にはtable_addコマンドを使います。
help table_addとすることで、コマンドの書式を確認することが出来ます。

table_add <table name> <action name> <match fields> => <action parameters> [priority]

今回の例では、どのように書けば良いでしょうか。P4プログラムのMyIngressの箇所を見てみます。
ここでは、コメントに書いたとおりの対応関係になります。

  • table name : ipv4_lpm
  • action name : ipv4_forward
  • match fileds : ホスト0 or ホスト1のIPアドレス(宛先として)
  • action parameters : ホスト0 or ホスト1のMACアドレス(宛先として)、ソフトウェアの出力ポート
control MyIngress(inout headers hdr,
                  inout metadata meta,
                  inout standard_metadata_t standard_metadata) {

    action drop() {
        ...
    }
    
    action ipv4_forward(macAddr_t dstAddr, egressSpec_t port) { // action parameters (dstAddrとport)
        ...
    }
    
    table ipv4_lpm {  // table name
        key = {
            hdr.ipv4.dstAddr: lpm;  // match fields(host0あるいはhost1のIPアドレス/プレフィックス)
        }
        actions = {
            ipv4_forward;  // action name
            drop;
            NoAction;
        }
        size = 1024;
        default_action = drop();
    }
 ...
}

それでは早速、ルールを追加していきます。
10.0.0.1のときはパケットの宛先MACアドレスをhost0のものにし、その出力ポートをveth0-hostのポートである0(スイッチ起動時に指定したもの)にします。
10.0.1.1のときはパケットの宛先MACアドレスをhost1のものにし、その出力ポートをveth1-hostのポートである1にします。

RuntimeCmd: table_add MyIngress.ipv4_lpm MyIngress.ipv4_forward 10.0.0.1/24 => host0のMACアドレス 0
Adding entry to lpm match table MyIngress.ipv4_lpm
match key:           LPM-0a:00:00:01/24
action:              MyIngress.ipv4_forward
runtime data:        host0のMACアドレス	00:00
Entry has been added with handle 0
RuntimeCmd: table_add MyIngress.ipv4_lpm MyIngress.ipv4_forward 10.0.1.1/24 => host1のMACアドレス 1
Adding entry to lpm match table MyIngress.ipv4_lpm
match key:           LPM-0a:00:01:01/24
action:              MyIngress.ipv4_forward
runtime data:        3a:e3:c5:6e:85:19	00:01
Entry has been added with handle 1

table_dumpコマンドでテーブル内容を確認してみると、以下のようになっています。

RuntimeCmd: table_dump MyIngress.ipv4_lpm
==========
TABLE ENTRIES
**********
Dumping entry 0x0
Match key:
* ipv4.dstAddr        : LPM       0a000001/24
Action entry: MyIngress.ipv4_forward - a230e2b741d3, 00
**********
Dumping entry 0x1
Match key:
* ipv4.dstAddr        : LPM       0a000101/24
Action entry: MyIngress.ipv4_forward - 3ae3c56e8519, 01
==========
Dumping default entry
Action entry: MyIngress.drop -
パケットを実際に送ってみる

さて、ここから実験を行います。
簡単にScapyで下記のようなプログラムを書きました。
host0からhost1に対して、あるいはhost1からhost0に対してパケットを1つ送信します。

from scapy.all import *
import sys

switch_veth0_mac = "52:0b:93:d7:52:51"
switch_veth1_mac = "36:86:0a:a1:c7:e5"

host0_mac = "a2:30:e2:b7:41:d3"
host1_mac = "3a:e3:c5:6e:85:19"

host0_ip = "10.0.0.1"
host1_ip = "10.0.1.1"

if len(sys.argv) < 2:
    print(f"Usage {sys.argv[0]} <mode | 0=host0, 1=host1>")
    exit()

mode = sys.argv[1]
print(mode)

if mode == "0":
    ether = Ether(dst=switch_veth0_mac, type=0x0800)
    ip = IP(dst=host1_ip)
    request = (ether/ip)
    sendp(request, iface="veth0")
else:
    ether = Ether(dst=switch_veth1_mac, type=0x0800)
    ip = IP(dst=host0_ip)
    request = (ether/ip)
    sendp(request, iface="veth1")

では、host0からhost1に向かってパケットを送信します。

$ sudo ip netns exec host0 sudo python3 test.py 0

simple_switchを起動した画面を確認すると、キー(宛先IPアドレス)がテーブルエントリにマッチしていることがわかります。

Match key:
* hdr.ipv4.dstAddr    : LPM       0a000101/24
Action entry: MyIngress.ipv4_forward - host1のMACアドレス,1,

host1上でtcpdumpを使って確認しておくと、パケットが届いていることがわかります。

$ sudo ip netns exec host1 sudo tcpdump -i veth1
IP 0.0.0.0 > 10.0.1.1:  hopopt 0

host1からhost0に向かってパケットを送信してみても同様です。

$ sudo ip netns exec host1 sudo python3 test.py 1
Match key:
* hdr.ipv4.dstAddr    : LPM       0a000001/24
Action entry: MyIngress.ipv4_forward - host0のMACアドレス,0,
$ sudo ip netns exec host0 sudo tcpdump -i veth0
IP 0.0.0.0 > 10.0.0.1:  hopopt 0

P4Runtime

P4言語のコンパイルから実行まで確認してみました。

流れをまとめると、次のようになります。

  1. P4でプログラムを記述
  2. P4プログラムをコンパイルしてデータプレーンのターゲットに合わせたバイナリデータを生成(ベンダーの提供しているアーキテクチャモデルの定義ファイルも含まれる)
  3. バイナリデータをデータプレーンにロード
  4. データプレーンのテーブル情報を作成・更新・削除

肝となるのは、4番目の操作です。これはどのようにすれば良いでしょうか。例えば、P4コンパイラコンパイルすると、データプレーンにアクセスするためのAPIが自動生成されます。このAPIを使ってコントロールプレーンの機能を実装すれば実行可能です。しかし、このAPIは、作成したP4プログラムに依存しています。そのため、P4プログラムを書き換えてしまうとAPIが変わってしまい、再度コントロールプレーンを実装し直さなければなりません。

またターゲットとなるハードウェアによってはCLIが用意されており、これを用いてアクセスすることも可能です。先程の例では、BMv2で提供されている「runtimeCLI」というプログラムを利用したと思います。これでP4プログラムに依存せずにアクセスが可能となりますが、これはターゲットとなるハードウェアに依存してしまいます。

汎用的に制御できるように、P4ではP4Runtimeと呼ばれるフレームワークでP4の実行基盤を制御することができるようになっています。P4Runtimeでは、コントロールプレーンとデータプレーンの間をgRPCでやり取りさせています。これにより、プログラムやハードウェアに依存しないAPIの提供を実現しています。

ワークフロー

P4プログラムをコンパイルすると、P4Infoと呼ばれる形式のファイルが生成されます。これには、P4プログラムで定義したテーブルやアクション、パラメータなどのIDや、その構造に関する情報が含まれています。このP4infoファイルはgRPCで使えるようにProtobufという書式で書かれています。P4infoファイルがコントロールプレーンとデータプレーンでロードされることで、両者でP4に関する各種情報を参照することができるようになります。

今回のチュートリアルでは、P4Runtimeというページにて演習することが可能です。
github.com


ここでは、mycontroller.pyというPythonプログラムによってコントロールプレーンが実装されています。
github.com


なお、このコントロールプレーンのプログラムは、今まで見てきたbasic.p4ではなく、下記のbasic_tunnel.p4に対応するものであるため、一部違う点があります。
(basic_tunnel.p4に関しては、https://github.com/p4lang/tutorials/blob/master/exercises/basic_tunnel/basic_tunnel.p4を参照)

(以下既存のコメントを削除、新規のコメントに関しては著者が追加)

mycontroller.py
...
import p4runtime_lib.helper #1.
...
def main(p4info_file_path, bmv2_file_path):
    p4info_helper = p4runtime_lib.helper.P4InfoHelper(p4info_file_path) #2. 

    try:
        #3. 
        s1 = p4runtime_lib.bmv2.Bmv2SwitchConnection(
            name='s1',
            address='127.0.0.1:50051',
            device_id=0,
            proto_dump_file='logs/s1-p4runtime-requests.txt')
        s2 = p4runtime_lib.bmv2.Bmv2SwitchConnection(
            name='s2',
            address='127.0.0.1:50052',
            device_id=1,
            proto_dump_file='logs/s2-p4runtime-requests.txt')

        ...

        # 4. 
        s1.SetForwardingPipelineConfig(p4info=p4info_helper.p4info,
                                       bmv2_json_file_path=bmv2_file_path)
        print "Installed P4 Program using SetForwardingPipelineConfig on s1"

        s2.SetForwardingPipelineConfig(p4info=p4info_helper.p4info,
                                       bmv2_json_file_path=bmv2_file_path)

        print "Installed P4 Program using SetForwardingPipelineConfig on s2"

        # 5. 
        writeTunnelRules(p4info_helper, ingress_sw=s1, egress_sw=s2, tunnel_id=100,
                         dst_eth_addr="08:00:00:00:02:22", dst_ip_addr="10.0.2.2")
  1. P4Runtimeを利用するためのライブラリをインポートします。
  2. P4Infoに関するヘルパーを定義(コンパイラに生成されたP4Infoファイルをロードし、その設定に基づいてデータがセットされる)
  3. Bmv2SwitchConnection()により、データプレーンとの接続試行(gRPCコネクション)
  4. SetForwardingPipelineConfig()によってパイプラインの設定をデータプレーンにインストール
  5. データプレーンに対して新規のルールを書き込み

SetForwardingPipelineConfig()は、後述のWriteTableEntry()と同様、P4RuntimeのProtobuf定義に基づくものです。

writeTunnelRulesは上部に定義されています。

def writeTunnelRules(p4info_helper, ingress_sw, egress_sw, tunnel_id,
                     dst_eth_addr, dst_ip_addr):
    ...
    # 1) Tunnel Ingress Rule
    table_entry = p4info_helper.buildTableEntry(
        table_name="MyIngress.ipv4_lpm",  # 1.
        match_fields={
            "hdr.ipv4.dstAddr": (dst_ip_addr, 32)   # 2.
        },
        action_name="MyIngress.myTunnel_ingress", # 3.
        action_params={
            "dst_id": tunnel_id,   # 4.
        })
    ingress_sw.WriteTableEntry(table_entry) # 5.
    print "Installed ingress tunnel rule on %s" % ingress_sw.name
    ...
  1. テーブル名として、P4プログラムで定義したMyIngressのipv4_lpmテーブルを指定
  2. マッチフィールド(key)となる箇所に"10.0.2.2/32"を指定
  3. 対応するアクションとして、MyIngressのmyTunnel_ingressを指定
  4. アクションの持つパラメータ"dst_id"として、tunnel_idの持つ値を指定
  5. WriteTableEntry()によってデータプレーンにルールをインストール

なお、これは今回のチュートリアルで用意されているソースコードにしたがったものであり、これが汎用的な書き方というわけではありません(WriteTableEntry()など、P4RuntimeのProtobuf定義に基づくものを除く)。

gRPCの使い方がいまいちわかっていないので今後調査しようと思います。

まとめ

P4はSDN環境においてデータプレーンの処理を記述するためのプログラミング言語です。
P4ではPISAと呼ばれるパイプライン処理が想定されており、この各種ブロックの処理を実装していくことになります。
また、P4Runtimeと呼ばれるP4のランタイムフレームワークにより、コントロールプレーンとデータプレーンの汎用的な制御を行うことができます。

最後に、簡単な実験によって、P4プログラムが動作することを確認しました。
今後はgRPCの調査を深め、P4Runtimeに関する記事を書いていきます。

*1: acceptとrejectに到達した場合の処理はアーキテクチャ側(BMv2)で定義されます。rejectになった場合は色々と方策を取れます。例えば、これ以上処理をしないようにしたり、エラーログだけ吐いてパースに成功した分だけ後続に渡したりなどです。言語仕様の12.3の"An architecture must specify the behavior when the accept and reject states are reached. "以降参照。

*2:P4ではL値と呼ばれます

*3:match_kind型。他にexact, ternaryがあります。

*4:言語仕様には明示的に書かれていないのですが、リンク先にはそう書かれています。、下記リンクでは "Every control block must contain an 'apply' block." とあります。https://github.com/jafingerhut/p4-guide/blob/master/demo1/demo1-heavily-commented.p4_16.p4

*5:ここがずっと不可解で、勉強会に参加してようやく腑に落ちました

*6:チェックサムの計算や検証など、今回定義していないものもあります。

2020年に読んだ本を振り返る

はじめに

2020年の12月には書いていたのだけど、完全に書いたのを忘れていた。

2020年はひと月に一冊は本に触れようという目標を立てていた。

備忘録として今年触れた作品について簡単な所感を並べていく。

こうしてみると、ひと月で読むには無理のある分量の本を買いすぎな気がする。

小説

ロリータ(ウラジーミル・ナボコフ、訳 若島正

ロリータという少女を取りつかれたように愛してしまった中年男性ハンバート・ハンバートの物語。

「恋愛小説であると同時に、ミステリでもありロード・ノヴェルであり、…」という書評のままの内容で、たとえ内容を紹介してみてくださいと言われたとしても答えに窮する感じだった。色んなネタを仕込んでいるのであろう、註釈の量がえげつなかった。

ロリータとの出会いを書いた第一部、いろいろあってロリータと旅をしに出る第二部との二つに大きく分かれるが、個人的に第二部が好きだった。車を走らせながらロリータと古びたラブホテルを点々としていく旅は、始終不穏な終わりしか感じられない。

驟雨・原色の街(吉行淳之介

吉行淳之介の短編集。表題作はいずれも娼婦が関わる作品。ロリータに続けて読んだので倫理観が終わってしまった。

倫理観がどうという話は実際はこの小説を語るのに無粋な問題で、人間の複雑な感情を性を通して異常なほどつぶさに描写しているという印象があった。

「原色の街」という題に似つかわしくない澱んだ色彩と、閉塞感が好きだった。

恐るべき子供たちジャン・コクトー、訳 東郷青児

第一次大戦後のパリが舞台。ポールとその姉エリザベート、友人のジェラール、アガートの4人が織りなす愛憎の物語。

ニンフの視座を持ち合わせていて、現世の人間とはどうあっても交差できない人間が好きで、その例に漏れずこの小説も好きだった。

子供時代にあるコントロールできない暴力性と人生に投げやりな態度がなんとなく好きで、「部屋」を作り出してそこで社会から抜けて退廃的に生きている子供たちの様子が最高だった。

花・死人に口なし 他7編(シュニッツラー、訳 番匠谷栄一・山本有三

死や罪、愛についての感情の機微が丁寧に書かれていて、分かる〜となることが多かった。バカの感想。特に「死人に口なし」の狼狽具合は自分も同じ状況であればそうなるであろうことは想像に難くない。文春砲にあった時の気持ちを味わえた。

「花」「死人に口なし」「わかれ」などで描写される、死人となった方がむしろ生きている人間に多弁に語り掛けてくるような感覚は分かる。

技術書

時系列解析 自己回帰型モデル・状態空間モデル・異常検知【Advanced Python 1】(島田 直希)

ARIMAなどの時系列解析を実装してみたかったので購入。個人的にこういう題だとフルスクラッチで実装するのかと期待してしまったが、ライブラリでの実装だった。マッチングがうまくいかなかった。

数多くの時系列解析の教科書で挫折した初心者の自分にとって、読むにはちょうど良い内容だった。この本のおかげで難易度高めの本もある程度読めるようになった。

時系列解析入門 [第2版]: 線形システムから非線形システムへ (SGCライブラリ 160)(宮野 尚哉, 後藤田 浩)

第1版を図書館で読んだことがあったが、新たに第2版でエントロピーの箇所などが加筆されたと聞いて購入。AR,MA,ARIMAなどについて丁寧に導出されていて非常によく理解できた。カオス理論の箇所はSF小説を読んでいるような気持ちになった。

エントロピーとカオス理論にここまで関連があったのかと驚いた。

個人的にサンプルエントロピーの話が面白かった。

ベイズ深層学習(須山敦志)

ベイズ推定とニューラルネットワークの基礎と、分布サンプリング法、ベイズニューラルネットワークと盛り沢山な内容で非常に勉強になる内容だった。

レビューで初心者でも分かりやすく丁寧と言われていたが、流石にそれは嘘だと思う難易度だった。少なくともベイズニューラルネットワークそれぞれの基礎が無いと理解は進まないと思う。

しかし丁寧であることは紛れもなく真実だった。後半部で出てくる式変形は基本的に全て本書の前半部の内容でカバーされているため、非常に分かりやすかった。いまいち理解が進まない箇所があるが、単に自分に数学的素養がないのが原因で本書の問題ではありません。

個人的に確率分布の式変形をしてカルバックライブラーダイバージェンスと期待値をあっちこっちする部分の数式がパズルのようで面白かった。

ハッカーの学校 IoTハッキングの教科書(黒林檎、村島 正浩)

ハードウェアハッキングの知識が全くなく、勉強したかったため購入した。

インターネットで公開されていたセキュリティキャンプの資料を参考に、たぶんこれじゃないかと推測しながら道具を揃えて、持っていたラズパイでSPIのところまではできた。ケチ臭い性分が発揮されている。念の為、本で得た知識は断じて悪用していませんし、今後決してすることはありません。

テスターなど高価で手が出なかった道具は揃えられなかったのでそこらへんはまた機会があればやりたい。

RFCの読み方―インターネット技術の公式仕様書(瓜生 聖, 秋月 昭彦)

下記記事を書くために図書館で借りた。

RFCに苦手意識があったのだけど、この本のおかげですらすら読めるようになった。

簡単な例から初めて少しずつ複雑なRFCにシフトしていく内容で無理なく知識を身に着けることができた。

2004年の本であるが内容は全く色褪せていないと感じた。

madomadox.hatenablog.com

Distributed Denial of Service Attacks: Real-world Detection and Mitigation (İlker Oezçelik, Richard Brooks)

自分の研究分野に近い内容だったので即ポチした。9千円近くとえらい値段が高かった。この手の値段とフォーマットの英書をよく見かけるけれどある程度こうしたアカデミックな本を発刊する機会があるのだろうか。

DDoSの歴史、ツールの種類、検知方法、緩和方法、実験環境の構築方法など有益な情報があって助かった。これを研究を始めたばかりで無駄サーベイ・開発に費やしてしまった頃の自分に読ませたい。

Deflectという技術があるのを知らなかった。調べてみたがいったん公開停止されているような気がする。

 

積んでしまった本

マシンリソースの不足、興味が持続できなかったという理由でほんの一部だけ読んだだけの本。

コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方(Noam Nisan, Shimon Schocken 訳 斎藤 康毅)

低レイヤーに対する苦手意識を克服するべく購入したが途中で苦手意識が肥大化して興味が薄れてしまった。来年できるといいなぁ。

つくりながら学ぶ!PyTorchによる発展ディープラーニング(小川雄太郎)

最新のディープラーニング技術を勉強したくて購入。

マシンリソースが足りず学習ができなかったため1章だけ読んで放置してしまった。

 

プログラミング言語C++ 第4版(ビャーネ・ストラウストラップ、訳 柴田 望洋)

目を通してSTLなどがそういうことだったのか~とはなったが全部は読めなかった。この手の本はリファレンスとして必要に応じて読まないとモチベーションが続かない感がある。プログラミング言語の本は何か一冊持っておくべきということだったので購入したが、本当にその通りだなぁと感じた。言語の特徴などを分からずにぐちゃぐちゃに書いてしまうため。

Effective PythonPythonプログラムを改良する90項目~ (Brett Slatkin、訳 石本 敦夫・黒川 利明)

2章まで読んだけれど、上と同じように感じて持続できなかった。とはいえ目が鱗の情報が多くて買って良かった。

コンピュータネットワーク 第5版(アンドリュー・S・タネンバウム,デイビッド・J・ウエザロール,訳 水野忠則・相田仁・東野輝夫・太田賢・西垣正勝・渡辺尚)

興味のあった輻輳制御アルゴリズムQoSだけ読んで放置してしまった。他の部分も必要に応じて読んだけれども、業務などに利用するには少し古かったりする箇所があるなぁという印象。

トラフィック測定のためのサンプリング技術についてまとめる(Sample and Hold法)

はじめに

ネットワークトラフィック測定技術、ストリーミングアルゴリズムに興味があり色々と調べているのですが、今回はサンプリング技術についてまとめようと思います。
その中でも、2002年に発表されたSample and Hold法を提案している論文[1]を読んだので手法部分にフォーカスしてまとめます。
一部数式の記号を変更している箇所がございます。また、認識に誤りがある箇所がございましたらご指摘いただけますと幸いです。可及的速やかに訂正いたします。

[1] Cristian Estan and George Varghese, (2002). “New Directions in Traffic Measurement and Accounting.” In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM, pp. 323–336, New York, NY, USA: Association for Computing Machinery.

論文のURLはこちらになります(フリーアクセスです)。
https://dl.acm.org/doi/10.1145/633025.633056

トラフィック測定とサンプリング技術

単純なトラフィック測定方法

ネットワークトラフィックの様態を知るためその特徴量を正確に把握することが求められます。その際、監視対象をフロー単位でまとめることが一般的です。

フローとは、通信の同一性を区別するために用いられる情報です。一般的には「送信元IPアドレス」「宛先IPアドレス」「送信元ポート番号」「宛先ポート番号」「プロトコル(IPヘッダ)」の5つの組で表現されます。

フロー情報で通信の同一性を区別できるので、フロー単位でトラフィックを監視して、単位時間ごとにその出現回数をカウントすれば、ネットワークトラフィックのパケットレートやエントロピー値などの特徴量を計算することができるようになります。なお、次のインターバルに移った時にはカウンタの値はクリアします。

単純な方法での問題点

しかしながら、ネットワークトラフィックの流量は大規模かつ高速であるため、単純な方法で実装してしまうと次のような問題点が発生します。

  • メモリ消費量の問題:出現回数を数えるということはメモリにフロー用のカウンタ(連想配列が主)を用意する必要があります。IPアドレスは理論的に2^{32}種類あることを考えればフローの種類数は膨大であり、出現回数も非常に多いことが予想されるので、メモリを大量に消費する可能性があります。
  • スケーラビティの問題: 1パケット到着するたびにフローの出現回数を更新していくという方法では、単位時間あたりのメモリアクセス回数が膨大に増加してしまい、大量にトラフィックが到着したときに対応できなくなる可能性があります。

サンプリング法

メモリアクセス回数増加とメモリ消費量という課題に対して、サンプリング法が利用されています。サンプリング法を利用したものとしては、NetFlowなどが有名です。

サンプリング法では、サンプリングしたパケットのみを利用してフローの出現回数をカウントします。これにより処理対象となるフロー数が制限されることになりメモリ消費量を小さくできる可能性があります。また、サンプリングされたフローに関してだけメモリ中のカウンタを更新するため、通常の方法に比べてメモリアクセス数も少なくなります。

サンプリング法では単位時間(あるいはバイト数)ごとに、所与の確率p(=サンプリングレート)で、その間に到着したパケットそれぞれについてサンプリングするかどうか決めます。パケットのサンプリングに成功した場合は、パケットのフロー情報を取り出しそのフローに対応するカウンタ(以降フローカウンタ)を作ります。すでにフローカウンタが作られている場合は、出現回数を加算します。サンプリング処理を繰り返していって、フローカウンタを更新していくことで、フローごとの出現回数を算出します。

しかし、当然ながらサンプリングされたパケットのみを監視対象としてカウントしていくので、出現回数の推定値の誤差が大きくなることが予想されます。

Sample and Hold法

Sample and Hold法はサンプリング法の長所はある程度残しつつ、推定精度を向上させるために考案されました。
それでも推定精度にはまだ難はあり、同論文で別の手法も提案されていますが、実装が単純でリソースの消費量も少ないという点が利点です。

Sample and Hold法はサンプリング法と同じく所与のサンプリングレートpでパケットを取得するのですが、その前にエントリが存在しているかどうかを確認します。
そして、フローカウンタが存在する場合は、サンプリングレートに関係なくパケット情報を取得し、対応するエントリを更新します。
フローカウンタが存在しない場合は、通常のサンプリング法と同様の処理を行います。

その違いについて直感的に捉えてみると、単純サンプリング法はすべてをサンプリングするので、真の出現回数との差が大きくなってしまう可能性があります。
一方、Sample and Hold法は一度サンプリングされたフローに関してはそれ以降取りこぼすことがないため、正確性が増します。ただしメモリアクセス回数はサンプリング法に比べて増加することがあります。

Sample and Hold法の理論的エラー率

論文では、その精度についても分析をしています。まずはフロー数の推定精度、そしてフローの観測成功確率をご紹介します。

フロー数についての推定精度

まずはフローの出現回数についての推定精度です。あるフローの実際の出現回数をs、Sample and Hold法による推定出現回数をcとして、その推定誤差を\sqrt{E[(s-c)^{2}}]という式で評価することにします。

このSample and Hold法では一度でもサンプリングされれば情報をずっと保持します。つまり、推定出現回数cであるということは、本来s回観測されるはずだったがそれまでに(s-c)回サンプリングに失敗したということになります。

成功するまでにx = (s-c)回サンプリングを失敗した場合を考えると、このときの確率を(1-p)^{x}pという式で表すことができます。

このときxは幾何分布(Geometric Probability Distribution)に従い、それぞれ期待値 E[x] = \frac{1}{p}、分散はVar[x] = \frac{1-p}{p^{2}}標準偏差SD[x] = \frac{\sqrt{1-p}}{p}となります。

ここで一般的な分散の定義式を変形すれば、二乗誤差の期待値E[x^{2}] = V[x] + E[x]^{2}となるので、

E[x^{2}] = V[x] + E[x]^{2} = \frac{1-p}{p^{2}} + \frac{1}{p^{2}} = \frac{2-p}{p^{2}}

したがって、

\sqrt{E[(s-c)^{2}}] = \frac{\sqrt{2-p}}{p} となります。

観測成功率

メモリ容量的にフローテーブルを持てる数に限りがある場合を考えます。限りがあるということは、フロー数が多すぎると新規にフローテーブルを作れなくなるため、出現回数を全くカウントできないフローが存在する可能性があります。

ここからは、論文に示されている例示を紹介します。

ある測定期間中に、メモリ許容量を1%超える数のフローで構成されたトラフィック流入してきたとし、その1%のフロー数は最大で100あるとします。
この時確保されるであろうフローカウンタは、100%のフロー数が10,000だとすれば、直感的には10,100必要になるはずです。
しかしここでは、フローメモリの限界が10,000だとします。トラフィックがメモリ許容量を超えている時のフローの観測成功率を考えます。

フローカウンタ数は10,000に抑えたいため、もしトラフィックのデータ量がBバイト到着するときは、サンプリングレートp=10,000/Bに設定します(この例、というより論文全体では単位バイト数ごとにパケットのサンプリングを行います)。これで多くの場合は10,000種類のフローだけが取得されるようになります。

この時、メモリ許容量を1%超えるフローをFとして、その観測成功率を求めます。サンプリングレートが10,000/Bであることを考えると、
FB/100バイト以上は送信されていることになります。(Bの1%)。

このFが全くサンプリングされない確率を考えると、 (1-10000/B)^{B/100}となります。
この値は、 B/100 = B^{\prime}とおけば、 (1-10000/B)^{B/100} = (1-100/B^{\prime})^{B^{\prime}} と変形できます。

これを \displaystyle \lim_{x \to \infty} \left( 1+\frac{x}{n} \right)^{n} = e^{x}と照らし合わせてみると、

 (1-100/B^{\prime})^{B^{\prime}} \approx e^{-100}となります。この100は、先程から考えている、メモリの許容量を1%超えたフロー数Fと一致します。

つまり、メモリ許容量を超えたたために全くサンプリングされない確率は、そのはみ出ているフロー数をfとすると、 e^{-f}で近似することができます。
すなわち、メモリの許容量を超えているトラフィックが到着した際に、許容量を超えているフロー数fについてフローカウンタが存在する確率は 1-e^{-f}で近似できます。

では、Fの5%のフロー数(5つ)が送信された時、それに対応するフローカウンタが存在する確率を確認します。

全くサンプリングされない確率はe^{-5}で近似できるということなので、 1-e^{-5}となり、フローカウンタが存在する確率は99%を超えることになります。

(自分の)TODO

※この章は論文著者が示した今後の課題ではなく自分のやり残したことを書いています。

単純な方法では色々と不都合があるので、同論文ではSample and Hold法以外にもMultistage Filter法という手法を考案しています。
また、これらの2つの手法をさらに改善する方法として、3つの工夫にも言及しています。

この記事はSample and Hold法単体に目を向けたものですので、これらについては別の記事でまとめようと思います。

まとめ

ネットワークトラフィックの様態を知るためその特徴量を正確に把握することが求められます。その際、監視対象をフロー単位でまとめることが一般的です。

単純に実装してしまうとメモリ消費量とメモリアクセス回数が膨大になり処理効率が悪くなってしまいます。これを解決するためサンプリング法によって計算対象となるパケット数を減少させる方法が利用されています。

一方、サンプリング手法も推定精度に難があります。そこで推定精度を改善するため、一度サンプリングされたフローはその後常にカウント対象とするSample and Hold法が考案されました。

理論的な推定誤差・メモリ許容量を超えた時にフローカウンタが存在する確率については、論文に詳細に書かれた例示と数式をもとに自分なりにまとめました。

実証実験などの詳細については論文をご覧ください。
(ブログで詳細に正確に書こうとするともはや翻訳のようになり、著作権的にまずいのではないか…というのと、正直しんどいというのとがあります)。

勉強に利用した文献

T. H. Cormen, C. E. Leiserson, R. L. Rivest, (1992). Introduction To Algorithms 1st Edition, MIT PRESS, (T.H. コルメン,C. E. ライザーソン,R. L. リベスト 浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一 (共訳) (1995). 『アルゴリズムイントロダクション [第1巻] 数学的構造とデータ構造 』 近代科学社 初版)
※図書館で借りたんですが丁寧に書いてあってめちゃくちゃわかりやすかったです。

NetFilterを利用したパケットフィルタリングプログラミング

はじめに

iptablesについて調べていると,どうやらNetFilterの仕組みを自分でも利用できるということを知りました.
実際にそれを用いてパケットフィルタリングのプログラムを作成します.

作成プログラム

8.8.8.8に対するICMPトラフィックをフィルタリングするプログラム

関連知識

LKM (Loadable Kernel Module)

LinuxのNetFilterの仕組みを用いて自分なりの機能を作成するには,NetFilterに関するLKM(Loadable Kernel Module)を新たに作成してカーネルにロードする必要があります.

これにより,ネットワークスタック関連の機能をフック(プログラムのある特定の箇所に独自の機能を追加・挿入)できるため,マシンにパケットが到着したり,出ていったりする時に動作させたいコールバック関数を実装してフィルタリングすることができます.

LKMはカーネルの機能を拡張するための追加モジュールです.

Linuxシステムプログラムに新たに機能を追加・変更しようとすると,カーネルのプログラム全体をリビルドすることになり,効率が悪くなってしまいます.

そこで,変更頻度が少ない基本的なモジュールは元々カーネルに組み込んでおいて,変更頻度の高いモジュールはLKMを用いて導入することにします.LKMでは動的にモジュールを追加できるため,カーネルのプログラム全体をリビルドする必要が無くなります.

LKMをロードすることで,ロードされたモジュールは特権モードで実行され,システムのハードウェアを利用することができます.アンロードも同様に可能なので,必要なくなったら削除することもできます.

LKMについては下記が詳しいです.
www.atmarkit.co.jp

NetFilter

NetFilterはネットワークスタック関連の機能をフックできるLinuxカーネルフレームワークで,主にパケットフィルタリングに利用されます.

Linux関連でのファイアウォールのツールとして一般にiptablesが利用されていますが,それはNetFilterの機能を利用して実装されています.

NetFilterと,フック可能なタイミングについては下記が詳しいです.
qiita.com
wiki.bit-hive.com

実装

プログラムがカーネルに組み込まれるため,あんまり変なフィルタリングの設定をしてしまうと普段使いの際に悪影響を及ぼします.
また,できる限り自前で持っているプログラムを用いて動作確認できる方が望ましいと考えました.
そのため,自システムから8.8.8.8に対して送信されるICMPトラフィックをフィルタリングするようにして,pingコマンドを用いてそれを確認します.

環境

カーネルのバージョン

5.4.0-47-generic

OSのバージョン

Ubuntu 20.04 LTS

ソースコード

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/ip.h>
#include <linux/inet.h>
#include <linux/netdevice.h>
#include <linux/netfilter_ipv4.h>
#include <linux/skbuff.h>

MODULE_LICENSE("GPL");

//登録するコールバック関数の定義
//sk_buff型の変数skbが引数として渡される。
static unsigned int handle_hook(void *priv, struct sk_buff *skb, const struct nf_hook_state *state)
{
        // skbからネットワークヘッダを取得
        struct iphdr *iph = (struct iphdr *)skb_network_header(skb);

        // パケットの宛先IPアドレスが8.8.8.8であり、IPヘッダのプロコトル情報が0x01(ICMP)の場合
        if((be32_to_cpu(iph->daddr) & 0xffffffff) == 0x08080808 && iph->protocol == 0x01){
                return NF_DROP //パケットをDROP(破棄);
        }

        return NF_ACCEPT; //パケットをACCEPT(送信)
}

// 登録するフックのルール
static struct nf_hook_ops hook_ops = {
        .hook   = handle_hook, //コールバック関数
        .pf     = PF_INET, //IPV4
        .hooknum = NF_INET_LOCAL_OUT, //フックのタイミングはローカスシステムから外部にパケットが送信されるとき
        .priority = NF_IP_PRI_FILTER, //フィルタのフック処理
};

//モジュールのロード時の処理
//モジュールのロード時にnf_register_net_hook関数でフックを登録
int init_module(){
        int err;
        err = nf_register_net_hook(&init_net, &hook_ops); //フックを登録

        if(err < 0){
                return err;
        }

        return 0;
}

//モジュールのアンロード時の処理
void cleanup_module(){
        nf_unregister_net_hook(&init_net,&hook_ops); //フックの登録を解除
}
        

実験

pingコマンドを用いて作成したLKMがきちんと動作しているか確認することにします.
mymodule.cというファイル名でコードを作成したことを想定します.

コンパイル方法

1. LKMのためのMakefileの作成

obj-m := mymodule.o

LKMを作成するための最小限の内容にしています。
2. makeによるコンパイル

$ make -C /lib/modules/$(uname -r)/build M=$(pwd) modules

コンパイルに成功すると、mymodule.koファイルが作成されます。
3. モジュールをロード

 $ sudo insmod mymodule.ko

4. モジュールがロードされたか確認

$ lsmod
Module                  Size  Used by
mymodule               16384  0
:
:
:

5. モジュールをアンロードする場合

$ sudo rmmod mymodule

pingコマンドによる動作確認

$ ping 8.8.8.8
PING 8.8.8.8 (8.8.8.8) 56(84) バイトのデータ
ping: sendmsg: 許可されていない操作です
ping: sendmsg: 許可されていない操作です
ping: sendmsg: 許可されていない操作です
$ ping 192.168.10.1
PING 192.168.10.1 (192.168.10.1) 56(84) バイトのデータ
64 バイト応答 送信元 192.168.10.1: icmp_seq=1 ttl=63 時間=21.2ミリ秒
64 バイト応答 送信元 192.168.10.1: icmp_seq=2 ttl=63 時間=10.8ミリ秒
64 バイト応答 送信元 192.168.10.1: icmp_seq=3 ttl=63 時間=9.37ミリ秒

8.8.8.8に対してのICMPトラフィックは送信されず、その他のIPアドレスに対してのものは送信していることがわかります。

まとめ

NetFilterを用いたパケットフィルタリングプログラムの実装方法を調べました。

NetFilterの機能を利用するには、NetFilterに関するLKMを作成してフック処理を登録する必要があります。

実験用のプログラムとして、8.8.8.8に対するICMPトラフィックをフィルタリングするプログラムを作成し、pingコマンドによる簡単な実験を行いました。

百合小説をサーバクライアントプログラムとして実装したい

1. Introduction

経緯

ある梅雨の深夜,じんわりと汗を感じながら寝苦しさに唸っていると,次のような発想がお告げのように降ってきました.

「百合小説をRFC形式で記述しなさい」

私は百合作品に造詣が深いわけでもないため,まったく自分とは違った存在から接続されたような気がして,古代の巫女の畏れを感じました.
そんな突拍子の無さを感じつつも,その試みは自分にとっても興味深く映り,非常に興が乗ったのでさっそく翌日から取り掛かることにしました.

方針

RFC形式で小説を書く」としてしまうと,原稿ファイルをRFCのレイアウトにして文章を書いても達成できてしまうので,少し面白みが欠けているかもしれません.

そこで,お互いの恋愛関係とそのやり取りを記述できるような通信方式を考えてみることにしました.そのプロトコルでは散文でもやり取りを行えるような設計にしておきます.最終的にそのプロトコルに則ったサーバクライアントプログラムを作り,手動か自動でやり取りさせます.これにより,ちょうど往復書簡のような塩梅で,小説に近い形式で物語を作成できるのではないかと考えました.

設計したプロトコル

百合小説の実装のため,オリジナルの通信プロトコルSAPPを設計し,その仕様をRFC形式でまとめていくことにしました.
SAPP(Simple Affection Protection Protocol)は非常に簡単なプロトコルで,主に以下のルールで通信を行います.

  1. SAPPクライアントが魅力的で付き合いたいと思う相手(SAPPサーバ)に告白
  2. 告白方法は,「普通に告白」「曖昧に告白」「脅迫的に告白」の3種類から選択
  3. SAPPサーバはその告白に対し,受諾 / 保留 / 拒絶することができる
  4. 受諾された場合,SAPPクライアントがSAPPサーバとメッセージをやり取りできるようになる
  5. 保留された場合は通信を切断される
  6. 拒絶された場合は通信を切断されたのち,しばらくSAPPサーバと連絡を取れなくなる

以下に,作成したRFC風文書を公開します.なお,クオリティがクオリティなので影響力は微塵も無いと思いますが,少しでも本家にご迷惑をおかけするわけにはいかないので,数字は割り当てずに???としました.
RFCは技術文書ですので基本的に晦渋な言い回しを避ける方針を取りましたが,小説を書くというゴールを考えて,遊び心としてある程度小説的な表現も入れようとしています.

drive.google.com

記事の構成

2章ではRFC風文書を書くために勉強した,RFCについての基本的な事項について説明し,3章で設計したプロトコルの設計思想を紹介します.その後,4章でRFCに則って実装したプログラムを紹介し,5章で動作実験を行い,簡単に物語を創作できるかどうか確認します.

2. RFC(Request For Comment)

概要

RFC(Request For Comment)とは,IETF(Internet Engineering Task Force)という機関から発行される,インターネットに関する様々な技術・事柄をまとめた文書群のことです.再配布が可能という特徴があり,非常に容易に入手可能な文書です.

主に通信プロトコルの仕様を定義し標準化するための文書として利用されることが多いですが様々な種類があります.文書は表題もありますが,特に通し番号で区別されます.

ところで,Request For Commentという名前は,ARPANETの研究グループが様々なアイディアを出して公開したものの,論文として出せるようなものではなかったため,あくまでコメントを求むという意味合いで発表した時の名残のようです[RFC-HOWTO].

種類

RFC文書には複数のタイプがあります.そのうち,インターネット技術として標準化されたStandards Trackとそれ以外のNon-Standards Trackがあります.
Standards Trackの文書は以下の流れで
Internet Draft ==> Proposed Standard ==> Draft Standard ==> Standard
まずIETFなどで議論された後に,その文書はInternet Draftという状態になります.
その後ある期限内にIESGに承認されると,Proposed Standardとなり,この段階からRFC番号が振られるようになります.
その6か月後,IESGに承認されると,Draft Standardとなり,さらに4カ月以上が経過して承認を得ると,Standardという文書になり,新たにSTD番号が振られるようになります.

Non Standards Trackには以下の3つがあります.

  • Informational

業界において,有益な情報として認められた仕様

  • Experimental

研究機関や企業などが実現した仕様

  • Historic

代替技術などの登場により現在は使用されていない仕様

自分の文書をどこに置こうかと考えたのですが,後述のジョークRFCもExperimentalで発表されているのでこちらを採用します.

ジョークRFC

自分のような初学者にはRFCは固い技術文書というイメージがありますが,実態はそういう面ばかりではありません.例えば4月1日には,ジョークRFCという形でユーモアたっぷりなRFCのパロディ文書が発表されます.

この中で有名なのが,RFC 1149「鳥類伝送によるIPデータグラムの転送」[RFC1149]です.これは通信に鳩を用いた時の通信プロトコルを書いた文書です.初めて読んだときに,ユーモアが巧みで非常に感動しました.実際に鳩を使って実装してみようとした人もいるらしいです.

自分の設計したいプロトコルは実用性が皆無であるため,ゴールとしてジョークRFCのようなものを目指すことにしました.

ちなみにRFCで文芸作品を表現しているものは無いのかなと探してみたところ何件かありました.RFC 527[RFC527]では,ARPAWOCKYという詩が書かれています.また,RFC 1121[RFC1121]ではARPANETの20周年記念を祝したシンポジウムACT ONEにて,一部のスピーカーが発表した詩をまとめています.英語の詩の楽しみ方がまだ分からないのでクオリティは判断できませんが,韻の踏み方が好きでした.
他にもご存知の方がいらっしゃれば教えていただけますと幸いです.

RFCの読み方

RFCは再配布可能なので検索すればすぐに情報が出てきますが,公式には以下のRFC Editorが使われます.Referecesとして引用する際にはこちらのURLが使われています.
www.rfc-editor.org

ところで,RFCは公開された後に修正されることはなく,技術仕様に修正が必要な時は,また新たなRFC文書が作成されます.
この時に重要となるキーワードがUpdateとObsoleteです.例えば数字の若いRFCを探してみると,上部にUpdated ByやObsoleted Byという文字の後ろにRFC番号が書かれていることが分かります.
ここで,Updated By〇〇〇となっている場合は,現在参照しているRFC文書への追加情報が書かれたRFC番号が〇〇〇に入ります.
また,Obsoleted By〇〇〇となっている場合は,現在参照しているRFC文書を廃止させたRFC番号が〇〇〇に入ります.
つまり,もし最新情報を得ようと思うのならば,以下のような読み方になります.
Updated By:現在読んでいるRFCと合わせて,Updated Byに続くRFC番号の文書を読む
Obsoleted By:現在読んでいるRFCではなく,Obsoleted Byに続くRFC番号の文書を読む

RFCの書き方

RFCの書き方もまたRFC 7322[RFC7322]などで定義されています.今回は,RFC 7322とそれをUpdateするRFC 7997[RFC7997]を参考にして書き進めることにしました.
ところでこれら二つの文書には,ObsolteしているRFC 2223[RFC2223]に記載されていた,Post Scriptで作成する際のページレイアウトやフォントの情報などが盛り込まれていませんでした.
そのため,ページデザインはRFC 2223を参考にしました.

RFC 7322では,RFCに盛り込まなければならない章・節とその書き方の指針,また参考文献などの体裁についての情報が記載されています.
RFCは英語で書かれなければならないことが示されていますが,正直自分の英文は目も当てられない出来だと思うので,ここは日本語で書くことにしました.

拡張バッカスナウア記法

RFCではある規則を表現するため,拡張バッカスナウア記法(Augmented BNF:ABNF)が使われることがあります.この記法自体もRFC 5234[RFC5234]で定義されています.
自分の勉強のためRFC風文書にこちらを盛り込んだので,簡単に触れようと思います.不慣れなのでおかしいぞという箇所がありましたらご指摘いただければ幸いです.

ABNFでは,基本的なルールを<規則> = <仕様>という形式で定義していきます.
そうやって定義した規則を組み合わせて,多様な規則を表現することができます.

ここからは,実際にSAPPプロトコルのREQUESTコマンドをABNF形式で表現していくことにします.
以下にREQUESTコマンドの一例を示します.これは,ハグによってSAPPサーバに対して告白することを意味します.

REQUEST DECLARE HUG

このコマンドは以下のように構成されています.

<req_cmd_name><スペース><req_type><スペース><situation><改行>

ここで,req_cmd_nameに該当する文字列は"REQUEST"のみです.

一方,req_typeは候補の文字列が3種類あります.DECLARE,PRAY,FORCEです.DECLAREが普通の告白であれば,PRAYは踏ん切りのつかない,あるいは自覚のない迂遠な告白,FORCEは壁ドンなどで強引に迫ったり,はては監禁・拷問などで相手の心をへし折り服従させたりするような告白を意味します.

そしてsituationでは,相手にどのように好意を伝えたのかを,0~400文字のUTF-8の文字列によって表現できます.

しかしこうした規則は上述の構成を眺めるだけでは伝わりません.

そのため,それを表現するためにABNF形式に直していきます.

まず,req_cmd_nameを定義します.文字列の候補はREQUESTのみであるため,素直に次のように書きます.これは「req_cmd_nameは"REQUEST"という文字列である」という意味になります.

req_cmd_name = "REQUEST"

続いて,req_typeです.DECLARE,PRAY,FORCEの3種類がありました.このような時,ABNFでは「/」をつかって「選択」という操作を使えます.

req_type = "DECLARE / "PRAY" / "FORCE"

これは,「req_typeはDECLARE,PRAY,FORCEの3つのうちのどれかである」という意味になります.

最後に,situationです.situationは0~400のUTF-8文字から表現されますが,それをABNF形式で書き直すと以下のようになります.

situation = *400 ( UTF8-char )

これは「situationは0~400回,UTF8-charが繰り返された文字列である」という意味になります.UTF8-charはUTF-8の文字を意味します(RFC 3629[RFC3629]で規則が定義されています).ちなみに,カッコの中の規則は数式と同じで先に評価されます.

他にも,スペースと改行が必要でした.スペースはSPですが,改行はCRLFで表現できます.

これらを踏まえ,REQUESTコマンドを表現する規則req_commandは以下のようになります.下と同じようにすっきりしている上,記法に慣れれば想定している規則もきちんと伝わります.

req_cmd_name = "REQUEST"
req_type = "DECLARE / "PRAY" / "FORCE"
situation = * 400 (UTF8-char  /  SP)
req_command = req_cmd_name  SP  req_type  SP  situation  CRLF
<req_cmd_name><スペース><req_type><スペース><situation><改行>

3. Protocol

概要

ここからは設計したSAPPの詳細をまとめていきます.

SAPPの簡単なルールは冒頭で述べましたが,以下により詳細にルールを示します.なお,通信内容は全てSSL/TLS通信により暗号化されます.

  1. SAPPクライアントが魅力的で付き合いたいと思う相手(SAPPサーバ)に対してREQUESTプロトコルコマンドを用いて告白
  2. SAPPサーバに受け入れられると,SAPPクライアントとサーバ間でメッセージをやり取りできる状態に遷移
  3. メッセージをやりとりできる状態のみMESSAGEプロトコルコマンドを用いてメッセージを送信
  4. もしリクエストがSAPPサーバに拒絶 or 保留された場合は通信が終了
  5. 拒絶したSAPPサーバはDENYテーブルにIPアドレスを登録し通信をしばらく受け付けないようにする

ちなみにプロトコルの名前は,Sapphism(女性同性愛)などの単語の元になった古代ギリシャの女性詩人サッポーから取っています.
TwitterInstagramで検索してみたところ侮辱的な言葉ではなさそうだったので採用しましたが,もしも侮辱的な言葉であれば早急に取り下げます.

設計思想

プロトコルの最終目的は,自分たちの関係を秘密にしておきたい人が周囲の目を気にせずに安心してやりとりできることを実現することです.
ただし,あくまで秘密にしておきたいと思う人のためのものであり,その関係は大っぴらに見せるべきではないと主張するものではありません.

記事タイトルでは「百合」と標榜していますが,特に一般的な関係と差別化を図ったり,対象となる人物像を制限したりしないようにしました.恋愛はどんなものも恋愛であり,その形式に当人たちの属性は関係ないためです.
また,別れなどの悲しい出来事や,浮気や二股など醜い部分も表現できるものを目指し,より細かく関係性を表現できるようにします.

4. プロトコル実装

作ったRFCを基に,実際にプロトコルを実装しました.
プログラミング言語はGoを選択しました.自分はGoは触ったことがなかったのですが,ゴルーチンという非同期処理により,サーバプログラムを作成するのが非常に容易だと聞いたので利用することにしました.
以下が実装したプログラムになります.
gitlab.com


プログラムにおいて,SAPPクライアントからの告白に対して,SAPPサーバの対応を決めるところは,request_func関数とmessage_func関数の箇所になります.
例えば,以下のように実装することができます.
素直に告白されたら受け入れ,あいまいであれば保留,強権的であれば拒否するようにしています.
シチュエーション情報は何でも良いのですが,便宜的にオウム返ししています.
柔軟に対応を変えるには,相手から届いたシチュエーション情報を解析して対応を変えるような実装に変更する必要があります.
このプログラムを書き換えることで,サーバとクライアントの関係を記述し,小説の展開で通信できるのではないかと考えました.

func request_func(connInfo *ConnInfo, mtype string, situation string) int {
	
	resp_situation := situation
	if mtype == "DECLARE"{ //普通に告白されたら...
		response := fmt.Sprintf("+OK %d ACCEPT %s",OK_CODE, resp_situation) //告白を受け入れる(ACCEPT)
		sendCommands(connInfo.conn, response)
		if recvAck(connInfo) {
			sendCommands(connInfo.conn, "ACK")
			connInfo.status = MESSAGE
		}else {
			r := fmt.Sprintf("-ERR %d",ER_CODE4)
			sendCommands(connInfo.conn, r)
		}

	}else if mtype == "PRAY"{ //曖昧に告白されたら...
		response := fmt.Sprintf("+OK %d SUSTAIN %s",OK_CODE, resp_situation) //返事を保留(SUSTAIN)
		sendCommands(connInfo.conn, response)
		if recvAck(connInfo) {
			sendCommands(connInfo.conn, "ACK")
			return -1
		}else {
			r := fmt.Sprintf("-ERR %d",ER_CODE4)
			sendCommands(connInfo.conn, r)
		}

	} else if mtype == "FORCE" { //脅迫的に告白されたら...
		ip := paser_IP_from_conn(connInfo.conn)
		DENY_TABLE.AddTable(ip,time.Now()) //相手をブラックリストに入れて,
		DENY_TABLE.ShowTable()
		response := fmt.Sprintf("+OK %d DECLINE %s",OK_CODE, resp_situation) //相手を拒否する(DECLINE)
		sendCommands(connInfo.conn, response)
		if recvAck(connInfo){
			sendCommands(connInfo.conn, "ACK")
			return -1
		}else {
			r := fmt.Sprintf("-ERR %d",ER_CODE4)
			sendCommands(connInfo.conn, r)
		}
	} else {
		r := fmt.Sprintf("-ERR %d",ER_CODE1)
		sendCommands(connInfo.conn, r)
	}
	return 0
}

5. 実験

ここでは,実際にSAPPサーバとSAPPクライアントの間で通信を行い,百合小説のようなものを作れるかどうかを確認します.
物語を創作する技術は乏しいので,その利用用途でも使えるよね,ということを単に確認するだけにとどめようと思います.

設定ファイルの環境

SAPPサーバのsapp.confファイルを下記のように設定しました.Timeout系は全て単位は秒になります.

#コネクションのタイムアウト時間
ConnectionTimeout       60

#ACK待機のタイムアウト時間
AckTimeout              60

#bindするIPアドレス
IPAdress                127.0.0.1

#ポート番号
Port                    10000

#同時に通信可能な人数(何股までするか)
ListenLimit             3

#サーバにアクセス可能なアドレス
AllowAddresses          "127.0.0.1", "192.168.0.1/24"

#DENYテーブルの数
TableSize               10

#DENYテーブルから排除されるまでの時間(タイプではない相手から告白された時にどのくらいの間連絡を取らないようにするか)
TableTimeout            3600

SAPPサーバ・クライアントの背景

SAPPサーバとクライアントの設定を決めることにします.

SAPPサーバはあまり分かりやすく好意をぶつけられることが苦手です.
まじめな性格で,自分の好意と誠実に向き合っては,これは果たして好意なのだろうかと考え込む面倒臭い面があります.
また,自分の気持ちを認めることに気恥ずかしさを覚えており,素直じゃない言い方しかできません.
しかしSAPPクライアントとともにいる時間は気持ちが穏やかになり,ずっとこの時間が続けば良いのにと願うこともあります.

SAPPクライアントは普段明朗な性格ですが,告白するにあたっていざ本人を目の前にすると,茶化してしまう癖があります.
SAPPサーバに好意を抱いているものの,その気持ちを押し殺して,SAPPサーバとは友人関係のまま行くことにしようと密かに考えていました.
そう思っていたのに,ふとしたきっかけで,公園で二人きり,ベンチに座って話すことになりました.
SAPPクライアントは,月明りに照らされたSAPPサーバの横顔を見て,押し殺していた気持ちがあふれ出し,たどたどしく告白をしてしまいます.

そうした背景を踏まえ,以下のような実装を行いました.

func request_func(connInfo *ConnInfo, mtype string, situation string) int {
        resp_situation := situation
        if mtype != "DECLARE" && mtype != "PRAY" && mtype != "FORCE" {
                r := fmt.Sprintf("-ERR %d",ER_CODE1)
                sendCommands(connInfo.conn, r)
                return 0
        }

        if mtype == "PRAY" && strings.Contains(situation, "手を繋いだ") {
                resp_situation = "私は躊躇いながら手を握り返した"

                response := fmt.Sprintf("+OK %d ACCEPT %s",OK_CODE, resp_situation)
                sendCommands(connInfo.conn, response)
                if recvAck(connInfo) {
                        sendCommands(connInfo.conn, "ACK")
                        connInfo.status = MESSAGE
                }else {
                        r := fmt.Sprintf("-ERR %d",ER_CODE4)
                        sendCommands(connInfo.conn, r)
                }
                return 0
        }

        if strings.Contains(situation, "キスをした"){
                ip := paser_IP_from_conn(connInfo.conn)
                DENY_TABLE.AddTable(ip,time.Now())
                DENY_TABLE.ShowTable()
                resp_situation = "「ごめん、そういうのじゃないから」私はぐいと押し返した。"
                response := fmt.Sprintf("+OK %d DECLINE %s",OK_CODE, resp_situation)
                sendCommands(connInfo.conn, response)
                if recvAck(connInfo){
                        sendCommands(connInfo.conn, "ACK")
                        return -1
                }else {
                        r := fmt.Sprintf("-ERR %d",ER_CODE4)
                        sendCommands(connInfo.conn, r)
                }

        }
        resp_situation = "「じゃあ、また今度ね」と私はそそくさとその場を後にした"

        response := fmt.Sprintf("+OK %d SUSTAIN %s",OK_CODE, resp_situation)
        sendCommands(connInfo.conn, response)
        if recvAck(connInfo) {
                sendCommands(connInfo.conn, "ACK")
                return -1
        }else {
                r := fmt.Sprintf("-ERR %d",ER_CODE4)
                sendCommands(connInfo.conn, r)
        }
        return 0
}

func message_func(connInfo *ConnInfo, message string) int {
        var response string
        resp_message := message

        if strings.Contains(message,"もう少しこのままでも"){
                resp_message = "「いいよ」なんでもないように答えたつもりで、うまく声が出なかった。"
        }else{
                resp_message = "..."
        }
        if connInfo.status == MESSAGE {
                response = fmt.Sprintf("ACK")
        } else {
                response = fmt.Sprintf("-ERR %d",ER_CODE4)
        }
        sendCommands(connInfo.conn, response + " " + resp_message)
        return 0
}

実験結果

まずは成功パターンを見ます.

REQUEST PRAY 私はおずおずと手を繋いだ
[RECV] ==> +OK 0 ACCEPT 私は躊躇いながら手を握り返した
ACK
[RECV] ==> ACK
message 「もう少しこのままでもいいですか」
[RECV] ==> ACK 「いいよ」なんでもないように答えたつもりで、うまく声が出なかった。
ACK

次が断られるパターンです.SAPPクライアントは枕を濡らして眠ることでしょう.

REQUEST FORCE 「ねぇ」私は彼女に呼びかけ、キスをした
[RECV] ==> +OK 0 DECLINE 「ごめん、そういうのじゃないから」私はぐいと押し返した。
ACK
[RECV] ==> ACK
REQUEST PRAY 私は彼女の肩に頭を傾けた。「今日は帰りたくないなぁ」
[RECV] ==> +OK 0 SUSTAIN 「じゃあ、また今度ね」と私はそそくさとその場を後にした
ACK
[RECV] ==> ACK

それっぽく設計をすることができました.とはいえ,単純な解析なのでいくらでも悪戯は可能だと思いますが…

6. まとめ

非常に単純なプロトコルですが,自分のやりたかったことを実現することができました.
幾度となく,自分は何をやっているんだ?と我に返ってしまったので細かい部分で誤りがあると思いますがご容赦ください.
効率が悪い,セキュリティ的にまずい実装があると思うので細々と修正を加えていきます.

RFC風文書にも書いたように,ポート番号が広く知られている場合には,通信内容は分からなくとも,SAPPを利用していることがわかります.
このサービスは利用していることもセンシティブな情報となりうるので,個人的にはSAPP over HTTPSを実装してHTTPS通信に紛れさせようとしたのですが,モチベーションがいったん枯れてしまったのであきらめました.今後気が向いたら実装しようと思います.

ご意見・ご指摘等がありましたらよろしくお願いいたします.

7. 参考文献

[RFC-HOWTO] 瓜生聖,秋月昭彦(2004),『RFCの読み方 インターネット技術の公式仕様書』,株式会社すばる舎
[RFC1149] Waitzman, D., "Standard for the transmission of IP datagrams on avian carriers", RFC 1149, DOI 10.17487/RFC1149, April 1 1990, https://www.rfc-editor.org/info/rfc1149.
[RFC527] Merryman, R., "ARPAWOCKY", RFC 527, DOI 10.17487/RFC0527, May 1973, https://www.rfc-editor.org/info/rfc527.
[RFC1121] Postel, J., Kleinrock, L., Cerf, V., and B. Boehm, "Act one - the poems", RFC 1121, DOI 10.17487/RFC1121, September 1989, https://www.rfc-editor.org/info/rfc1121.
[RFC2234] Crocker, D., Ed., and P. Overell, "Augmented BNF for Syntax Specifications: ABNF", RFC 2234, DOI 10.17487/RFC2234, November 1997, https://www.rfc-editor.org/info/rfc2234.
[RFC7322] Flanagan, H. and S. Ginoza, "RFC Style Guide", RFC 7322, DOI 10.17487/RFC7322, September 2014, https://www.rfc-editor.org/info/rfc7322.
[RFC7997] Flanagan, H., Ed., "The Use of Non-ASCII Characters in RFCs", RFC 7997, DOI 10.17487/RFC7997, December 2016, https://www.rfc-editor.org/info/rfc7997.
[RFC2223] Postel, J. and J. Reynolds, "Instructions to RFC Authors", RFC 2223, DOI 10.17487/RFC2223, October 1997, https://www.rfc-editor.org/info/rfc2223.
https://www.rfc-editor.org/info/rfc5234
[RFC5234] Crocker, D., Ed., and P. Overell, "Augmented BNF for Syntax Specifications: ABNF", STD 68, RFC 5234, DOI 10.17487/RFC5234, January 2008, https://www.rfc-editor.org/info/rfc5234.
[RFC3629] Yergeau, F., "UTF-8, a transformation format of ISO 10646", STD 63, RFC 3629, DOI 10.17487/RFC3629, November 2003, https://www.rfc-editor.org/info/rfc3629.

「Miraiのソースコードを理解する」という記事に関して

Miraiのソースコードを理解する、という題で一連の記事を書いていたのですが、非公開にすることにしました。

ずっとどうなのだろうと考えていたのですが、以下の懸念事項が大きな理由です

GitHubで一般公開されているとはいえ、ソースコードを一部引用して紹介しているので、自分としてはそのような意図は一切なく、悪用禁止の文言を書いてはいたものの悪用を助長するリスクが高いと考えられるため

ソースコードをもとにした記事であるため攻撃に関する情報しか記載されておらず、特徴をまとめる意義はあるものの対策法が書かれていないため

・自分の理解に誤りがある可能性は捨てきれず、間違いを流布するおそれがあるため

 

このような理由があるにも関わらず公開をしていたのは(自分の思い上がりの面もありますが)次の通りです。

・英語ではまとまった文献はあるが、日本語ではなかなか見つからず、自分自身理解に苦労した経験があったので、日本語でそうした記事を提供できないかと考えたため

・アクセス数が実際多く、おそらく需要があるのではないかと考えたため

 

ただ探していくと、日本語で書かれた有用な資料を見つけることができてきたため、自分の中の葛藤を解決するには、記事は全て非公開にし、自分が理解するのに参考にさせていただいた有用な参考文献をまとめていくだけの方が良いと感じました。

 

以下に参考文献を示します。

 

個人的にソースコードを理解していく上で、日本語文献の中で最も参考になった記事です。

https://www.atmarkit.co.jp/ait/articles/1611/08/news028.html

 

Miraiが踏み台機器への不正ログインに利用したIDとパスワードの組などが記載されています。

https://www.ipa.go.jp/files/000062277.pdf

 

ボットネットアーキテクチャなどが詳細に記載されています。

G. Kambourakis, C. Kolias and A. Stavrou, "The Mirai botnet and the IoT Zombie Armies," MILCOM 2017 - 2017 IEEE Military Communications Conference (MILCOM), Baltimore, MD, 2017, pp. 267-272. doi: 10.1109/MILCOM.2017.8170867

 

Miraiで使われているコマンド類など詳しく記載されています

https://www.iij.ad.jp/dev/report/iir/pdf/iir_vol33.pdf

 

HajimeやMiraiについて詳細に書かれている文献(自分自身購入してはいないのですが、試し読みできる範囲ではかなり詳細に書かれていると感じます。めちゃくちゃ高いですが…)

https://www.amazon.co.jp/Botnets-Architectures-Countermeasures-Challenges-Security/dp/0367191547

メモリ効率の良いトラフィック監視を可能にする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操作と呼ぶことにします).
ここでkeyIPアドレスvalIPアドレスの出現回数です.(ところでvalを計算するのにSketchが新たに必要となり堂々巡りになりそうな気がしますが,運用上,出現回数を数えることはせずに,valを1に設定して,新たにパケットが到着するごとに更新しているのだと思います).
updateは, i = 0, 1, 2, ..., Hについて,次に示す手順で行われます.

  1. 入力となるkeyを,ハッシュ関数h_{i}でハッシュ化し, j = h_{i}(key)を取得
  2. 得られたデータ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行目に「11」という文字が見えます.これは,2と13のハッシュ値が衝突してしまっていることが原因です(key=2val=6key=13val=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.