メモ: The Velocity of Censorship: High-Fidelity Detection of Microblog Post Deletions

USENIX Security 2013の論文メモ2つ目

The Velocity of Censorship: High-Fidelity Detection of Microblog Post Deletions

Tao Zhu, Independent Researcher; David Phipps, Bowdoin College; Adam Pridgen, Rice University; Jedidiah R. Crandall, University of New Mexico; Dan S. Wallach, Rice University

第一著者の方は中国人のようなのだが、こんな論文を書いて中国に戻ったら当局に捕まるとか消されたりしないんだろうかというドキドキが止まらない論文。Independent Researcherというのが、またいろいろと妄想をかきたてる。

一部界隈では有名な話だが、中国のインターネットは言論統制や不穏分子発見のためとても厳しいネットワーク上の活動監視やデータ送受信のブロックが実施されている。そのため、海外のSNSではなく中国国内のSNSを使う人が多いそうだが、そこはさすが中国というべきか、多くのサービスが表向き普通に運営しているものの、当局の監視が厳しく行われている。そのなかの中国国産Micro blog(≒Twitter)であるWeibo(読み:ウェイボー)をとりあげ、どのような取り締まりが実施されているのかについて分析したのが本発表である。

筆者らはユーザ視点で当局がどのような活動をしているかを推定している。基本的な戦略は以下のとおり。

  1. 当局に目をつけられそうな人たち(sensitive user group)を見つける
  2. 彼らの投稿を監視する
  3. 彼らの投稿の削除を発見する

「削除するくらいなら、そもそも投稿させないのでは?」と思ったが、これはWeiboの挙動を見る限りデータそのものが消え去っている通常の削除と、Permission Deniedによって「見えなく」なっている削除の2通りがあるらしい。これは監視の目的からすると「きわどい発言」をしたデータというのを残しておいて、あとから検証や捜査につかうという可能性があるのではないかと考えられる。(このあたりは推測しかできないので、筆者も厳密には言及していない)またあとから削除するというのも、すぐにはNGキーワードだということが分からずあとから発覚して消すなど、いろいろな状況が予想される。筆者らの観測によると10%ほどの書き込みは1日以上たったあとに削除されていたらしい。したがって、筆者らは単純なキーワードマッチ以外に、怪しい人物を事前に特定してその人物らの投稿を注意深く監視したり、削除対象となる投稿を見つけた場合に関連する他の投稿を探しだして詳しく検査したり、人気のトピックを注意深く監視するなど、まさにあの手この手で対応しているのではないかという仮説を主張している。

この論文、Weiboに特化した話なので、おそらく一般性・普遍性についてそこまで優れているというわけではないとみられる。しかし近年、日本を含む中国以外の国でも政府・公安機関による監視を強化する流れが顕著になってきているため、(良くも悪くも)先進的な事例になっている中国で、政府による介入がどのように実施されるかという観測や考察については多くの人に対して価値があると判断されたのではないかと思う。理論より実践よりなUSENIXらしいなぁ、という印象。

メモ: ZMap: Fast Internet-wide Scanning and Its Security Applications

USENIX Security 2013のメモ

情報セキュリティの分野において世界的に有名な学会の1つであるUSENIX Securityの2013年開催のものから、気になった論文にざーっと目を通したので、その内容をメモも兼ねてまとめておきます。論文をしっかり読み込む暇は無かったので、おおまかなまとめになっていたり、間違いが含まれる可能性もあります。論文、発表資料、講演のビデオも公開されているので、詳しくはそちらを御覧ください。この内容をあてにして何か間違えたり恥かいたりしても、一切責任はとりません。(一度に載せようと思ったんですが、なんかダルくなったんで、順次アップロードしていきます)

ZMap: Fast Internet-wide Scanning and Its Security Applications

Zakir Durumeric, Eric Wustrow, and J. Alex Halderman, University of Michigan

インターネットでサービスを提供しているソフトウェアやプロトコルの脆弱性が発見された時、「ではそのソフトウェアやプロトコルを使っているホストは世界に何台ぐらいあって、それは全体の何%か?」というような調査がここ何年かのメジャーなセキュリティ系の学会で発表されてきた。その際の調査方法は基本的に総当り方式で、インターネットの2の32乗(約42億)個のアドレス全てにアクセスして調査していた。通常のOSが提供しているプロトコルスタックを使って調査をしようとすると膨大な時間(長いと数ヶ月単位)の時間がかかってしまうが、これを秒間数万台規模で調査できるようにしたのが著者らが提案したツール ZMap である。

基本的な戦略は、OSの標準スタックを使うのではなく自前でプロトコルに従ったパケットを生成し、libpcapのようなパケットキャプチャによって受信した内容をこれまた自前で解釈するというもの。これによって最小限のやりとりのみで必要となる情報を引き出し、時間あたりの調査数を大幅に高めている。また、実際に調査を実施して既存手法との比較をしたり、送信間隔を短く(最終的には1.4M packet/sec 程度で送信)しても応答が減るようなことは無いということを示している。ソースコードも公開されているので、他の研究でも応用範囲は広そうである。

Pthread_mutex_lock/unlockの処理コスト

pthread_mutex_lock/unlockの処理コスト

スレッドプログラミングをするにあたって適切なセマフォの操作は必須の課題です。よく問題になるのは双方でロックをかけようとしてロック待ちの状態が発生することで遅延が発生し、全体の処理が遅くなってしまうというケースです。ですが一方で、2つスレッドがあった時に一方のスレッドは頻繁に資源を触るけど、他方のスレッドはほとんど資源を触らないという状況もあります。この場合、資源のつかみ合いはほとんど発生しないと考えられますが、そうなると「そもそもロックをかけること自体にどれくらいコストがあるのか?」ということが気になります。とくに秒間数百万回の処理で毎回そんなことやっていいのか、というのが気になります。ということで、ちょっと調べてみました。

今回対象としたのはpthread (Posix thread) です。pthread_mutex_lockとunlockを特にオプションなど指定せず、素直に使ってみました。単純な足し算を228回繰り返すさい、mutex_lock無しで実行した場合(普通のシングルスレッドで書かれたプログラム)と、mutex_lock, unlockを毎回の計算の前後で実行した場合の比較をしました。時刻はgettimeofdayで見ているやら、試行回数は2,3回やらなので、その程度の精度だと思ってください。

計測に使ったコードはgithubにおいてあります。実験は以下の環境でそれぞれやってみました。

  • OSX 10.8.5 1.6GHz Core i5
  • OSX 10.8.5 2.53GHz Core 2 Duo
  • Linux 3.8.0-31 Pentium G640 2.80GHz
  • Linux 3.2.0-39 Xeon® E5645 2.4GHz (@Sakura VPS)

で、結果は以下のとおり。

詳細な数値は省きますが、(lock/unlock有り時間 - lock/unlock無し時間) / 繰り返し回数 という計算をしてみると、 Core i5のOSXで約51ナノ秒、Pentium G640のLinuxで約25ナノ秒が、lockとunlockの処理に平均して必要ということがおおよそ推測されます。一回一回は非常に短い処理時間ですが、一秒に数百万回呼び出すようなときはちょっと考えたほうがいいかもしれません。

Msgpack in C++で自由なデータ型のmap形式を抽出する

前説

msgpackはJSONのように自由なデータ形式を使えつつ、直接の可読性を捨てることでデータ容量を節約し、実装的にもserialize, deserializeを高速化している今どきな感じのシリアライズフォーマットです。KVSに構造化データをがしがし入れていくためデータのシリアライズが必要でしたが、ありきたりなJSONよりはmsgpackも使ってみるか、ぐらいの気持ちで使い始めてみました。

やりたいこと

JSONで例えると、こういうデータを扱いたいと思いました。

{
    "ts": 13345133.43,
    "src": "10.0.0.1",
    "domain": {
        "example.com": 1,
        "example.org": 2,
        "example.net": 3,           
    }
}

特徴としては、

  1. マップ形式だが、バリュー部分に数値や文字列などのデータ形式が入り交じっている
  2. 出現するキーがメッセージごとにまちまちで統一されない

となります。1だけ解決したいならユーザ定義Classへのバインド機能 (MSGPACK_DEFINE) を使う、2だけならmapではなくarray形式をうまく使うようにする、で概ね解決できます。実際、1と2を組み合わせてやればある程度は解決できる可能性もあるのですが、実装上の制約によって本来あるべきと考えるデータ構造の形式をねじまげるのはなんか癪な気持ちになったので、いろいろ調べてみました。ちなみに上記のようなデータをシリアライズする方法はQuickStartガイドに示されています。しかし、デシリアライズする方法が無い…。

解決方法

調べ方の問題かもしれませんが、見つかったのは構造体内のデータに直接触るやり方でした。参考にしたデータは本家のソースコードの object.cpp の64-76行目で、表示可能な文字列に変換してostreamに流し込んでいるところ。

case type::MAP: // map形式のオブジェクトだったら
    s << "{";  // まずはカッコを表示
    if(o.via.map.size != 0) { // マップ内のサイズが0じゃなかったら、
        object_kv* p(o.via.map.ptr); // object_kv構造体をobject構造体の .via.map.ptr から作成
        s << p->key << "=>" << p->val; // 最初のキー+バリューを表示、
        ++p; // 一つずらす
        for(object_kv* const pend(o.via.map.ptr + o.via.map.size);
                p < pend; ++p) { // 終点を設定して、そのままポインタをずらしつづける
            s << ", " << p->key << "=>" << p->val; // キーとバリューを表示
        }
    }
    s << "}"; // 締め
    break;

これを参考にunpackするコードを書こうとすると、こんな感じ。dataがシリアライズされたデータへのポインタ、lenがデータ長とし、nameというキーの文字列データがバリューで入っているものとします。

msgpack::unpacked msg;
msgpack::unpack(&msg, data, len);  // デシリアライズ
msgpack::object obj = msg.get ();

if(obj.via.map.size != 0) {
  msgpack::object_kv* p(obj.via.map.ptr);
  for(msgpack::object_kv* const pend(obj.via.map.ptr + obj.via.map.size);
      p < pend; ++p) {
    std::string key, name;
    p->key.convert (&key);

    if (k == "name") {
      p->val.convert (&name);
      std::cout << k << "=>" << name << std::endl;
    }
  }
}

p->keyp->valueはそれぞれmsgpack::object型で数値、真偽値、文字列をラップするような形式になっており、適宜別のデータ型に変換できるようです。

一応、これでやりたいことはできたのですが、なんか外法を使っているような気になります。オブジェクト指向なのに構造体の内部データに直接触ってしまうだけでいろいろと罪悪感がつきません。なんかもっといい方法を知っている人がいたら、ぜひご教授ください。

参考ページ

Bro IDSを使ってみる

Bro IDS

Bro IDS http://www.bro.org/ はgatewayに流れるようなネットワークトラフィックを監視し、セキュリティに関連したイベントを発見するオープンソースの侵入検知システム(Intrusion Detection System, IDS)です。オープンソースのIDSで最も有名なのがSnort http://snort.org/ ですが、2000年後半あたりからこのBroを使ったネットワークセキュリティ系の論文が散見されるようになりました。なのでそこそこ業界的には有名なはずなんですが、あまり日本語の記事もなかったので書いてみました。

Broの特徴は、多くのIDSで実装されているシグネチャベースのパターンマッチ(特定の文字列などが出現したらアラートを報告する)だけでなく、トラフィックのプロトコルを解読した結果を用いて簡単なスクリプトを記述できる点です。これによって、研究者がネットワーク監視から得られたデータから自分の目的にあわせたデータの抽出が容易になり、様々な研究が捗るようになりました。

インストール

詳しくはQuick Start Guideを参照してください。ここでは自分の環境でインストールした時のメモだけ。

環境はUbuntu Linux 12.04、さくらVPS上のホストに入れました。パッケージから入れる方法もありますが、昔大学の先輩に教わった「自分にとって大切なパッケージはソースをとってきてちゃんとコンパイルすべし」という薫陶を守り、手作業で導入。

下準備として、とりあえず以下のパッケージを導入。

% sudo aptitude install flex bison libmagic1 libmagic-dev swig libpcap0.8 libpcap-dev openssl build-essential zlibc zlib1g-dev libssl-dev python-dev

ソースはgitレポジトリが公開されているので、そこからcloneしてくる。あとは普通にconfigure + make。プレフィックス指定は趣味なので、ご参考までに。

% git clone --recursive git://git.bro-ids.org/bro
% cd bro
% ./configure --prefix=$HOME/local
% make
% make install

特にハマることもなく完了。ほらね、簡単でしょう?

とりあえず使ってみる

このあたりから適当なサンプルのpcapファイルをとってきてテストしてみる

% wget "http://wiki.wireshark.org/SampleCaptures?action=AttachFile&do=get&target=http.cap" -O http.pcap 

% bro -v
bro version 2.1-1377

% bro -C -r http.pcap

-Cはチェックサムの検証を無視、-rは読み込み対象のtcpdump形式ファイル指定のオプションになります。実行すると以下の様なログがそれぞれ吐き出されます。

  • conn.log : TCP,UDP,ICMPでのフロー情報をまとめたもの。転送データ量、接続時間、プロトコルなどが記録されている
  • dns.log : DNSによる名前解決のレコードが記録されている
  • files.log : HTTPなどでどのようなファイルが取得されたかを表示している。HTTPをパースした上でのファイルのサイズ、mime typeなどが見える。オプションによっては、ファイルそのものを復元できる模様
  • http.log : HTTP request/responseの情報。URL、ホスト名、User agentなどの情報が参照できる。
  • packet_filter.log : tcpdump形式のフィルタの情報が記録されている

各ファイルはだいたいTABで各フィールドが区切られた形式になっているので、他のスクリプトなどで処理するのは比較的簡単そうです。これらはデフォルトのルールやスクリプトによってはき出されているものであり、それの変更次第で出力内容や監視対象を変更できるようです。

とりあえずここまで。

2013.10.8 追記

インストールするパッケージのリストを新更o

Octopress + github.ioの設定

ブログ的なものをまた少しやってみようかといろいろあさってみた結果、なんとなくgithub.ioを使ってみようと思い、Octopressも含めてセットアップしてみました。 github.io + Octopressを使ってみようと思った理由は、

  • ローカルにデータを持てるので可搬性が高そう(な気がする)
  • Markdown記法で記述でき、編集に自分の好きなエディタを使うことができる
  • ソースをいじろうと思えばいじれるので、いざというときの自由度は高そう
  • なんか意識高い人っぽい

以下、Hello world的にgithub.ioとOctopressを使ってblog的なページを作成する手順をまとめてみました。

事前にやっておくこと

おそらく日頃からRubyをヘビーに使っている人には不要な作業なのだが、結構ほかのサイトだとしれっと書かれていたりするので、一応メモ。

インストール

  1. <user-name>.github.io という名前でレポジトリを作る
  2. Octopressを自分のローカル環境にcloneする

     % git clone git@github.com:m-mizutani/octopress.git octopress
     % cd octopress
     % bundle install
     % rake install
    

これで終わり。とりあえずローカルでプレビューを立ち上げるには、

% rake preview

と実行すると、ローカルでポート4000でサーバが立ち上がる。 http://localhost:4000/ で確認できる。

編集

_config.yml をいじる

タイトルなど、ページ全体に関連するメタ情報の設定。とりあえず先頭10行程度をいじれば動く。以下設定例。

# ----------------------- #
#      Main Configs       #
# ----------------------- #

url: http://m-mizutani.github.io
title: ある研究者の手記
subtitle: Notebook Found in a Deserted Field
author: Masayoshi Mizutani
simple_search: http://google.com/search
description:

ページを作成する

静的なページを作成するには以下のコマンド。

% rake new_page['hoge']

zshで作業している場合、[] はパス名解決に使おうとしてしまうので、

zsh: no matches found: new_page[hoge]

のようなエラーになってしまう。その場合は、

% rake new_page\['hoge'\]

のようにして、エスケープする。

ページは source + 指定したページ名が作成されるので、この場合は source/hoge/index.markdown を編集することで、ページに反映される。アクセスは http://localhost:4000/hoge/ で参照できる。

テーマ変更

% git clone https://github.com/macjasp/cleanpress.git .themes/cleanpress
% rake install['cleanpress']
A theme is already installed, proceeding will overwrite existing files. Are you sure? [y/n] y

デプロイする

% rake setup_github_pages

repositoryのURLを入れろと言ってくるので、git@github... のURLを入力

Repository url: git@github.com:m-mizutani/m-mizutani.github.io.git

そのあと

% rake gen_deploy

とすると、コンテンツ作成&デプロイを一括してやってくれる

To git@github.com:m-mizutani/m-mizutani.github.io.git
 ! [rejected]        master -> master (non-fast-forward)

と怒られる場合があるので、Rakefile 内の、

system "git push origin #{deploy_branch}"

system "git push origin +#{deploy_branch}"    

に変更する。このあと、数秒〜数分後に自分のgithub.ioサイト(自分の場合は http://m-mizutani.github.io/ )に変更が適用されるはずなので、プレビューと同じ内容が見えていたら成功。