« 2006年8月 | トップページ | 2006年10月 »

2006年9月の8件の投稿

2006.09.30

[Mixi]つながりを表す指標「笠原数」の提案

□はじめに
Mixiを使ったことのある人は自分または他の人マイミクの数を気にした事があるかもしれない。Mixiの興味深さは「ある人」と「ある人」が繋がっている事が「マイミク」というつながりで可視化できることである。これは非常に重要である。というのは、リアルな世界では、ある人とある人が知人かどうかは、その周囲の人に聞いてみるしかないからだ。Mixiはそのつながりを自動的に表示してくれる。

□つながりの科学~ミクロの場合
この「つながり」ということを数学的に言うとどうなるだろうか?「つながり」は数学的に言うところの「グラフ理論」で表される。例えばマイミクの数は辺、あるいはリンクの数となる。Mixiに参加している人は頂点で表される。

もう少しつっこんでみよう。AさんのマイミクBが、AさんのマイミクCとマイミク同士であることも良くある。この「良くある」頻度をクラスター密度呼ぶ。これによって、Aさんの周囲でどのようなマイミクが形成されているか、ある程度の指標を教えてくれる。

□つながりの科学~マクロの場合
ここでよりマクロ問題を考えてみよう。Mixiの参加者であるAさんとBさんをランダムに選ぶ。AさんとBさんは何人のマイミクを介して繋がっているのだろうか?(問題A)そして、どんなAさんでもBさんでも平均どのくらいのマイミクを挟めばつながっているだろうか?(問題B)これは非常に興味深い問題だ。

この手の最初の実験をしたのはミルグラムらの実験である。彼は、アメリカ人におけるまったく他人同士において、何人を介して手紙が届くか実験をした。答えは大抵6次のつながりだったという。
今、1次とはマイミク同士、2次とはマイミクのマイミク同士と考えてもらって構わない。

□Mixiとつながりの科学
この問題をMixiで研究することは有意義なことである。というのは、マイミクという情報が既にサーバにあり、問題AにしろBにしろ計算可能だからである。しかし直感的にわかるように、問題Bは答えがわかるまでに相当大きな計算が必要であることがわかる。

もう少し単純なことを考えよう。
Mixiの参加者である、特定の人を決めておく。この人とAさんがどのくらいのマイミクを挟めば繋がっているだろうか?(問題C)

問題Cは既に特定の人という基準があるので、問題Bに比べると計算が楽である。問題Aと計算量はほぼ同じだが、どんなMixiの参加者からも共通のものさしを与えられる事が違う。

ではこの特定の人を誰にすべきか?という事が挙げられる。重要なことは
・有名人であること
・Mixiに永続的に参加していること
の2つであろう。特に後者を考えるとMixi社長の笠原氏が望ましいと考える。

今、笠原氏とMixiの参加者での繋がりの数(ホップ数)を「笠原数」と定義する。
笠原氏のマイミクは笠原数=1、笠原氏のマイミクのマイミクは笠原数=2である。
ちなみに私は笠原数が2である。(ちなみに笠原氏自身は笠原数は0である)

この手の話は、私がオリジナルではない。グラフ理論の権威であるエルデシュ氏を称えたエルデシュ数を参考にしている。皆様も是非笠原数を計算して欲しい。

□Mixiと笠原数
実はこれからが本題である。
笠原数が3以上についてはMixiで計算する事は面倒である。というのは笠原数が2以下の場合にはMixiが自動的に表示するが、3以上は手計算で調べないといけないからである。

では、笠原数が3以上の人はどのような計算をすればよいだろうか?一番確実なのは、マイミク経由で総当りに調べる事である。しかしこれはとても大変である。

そこで、次のようなアルゴリズムが考えられる。
[アルゴリズム1]マイミクが多い人を優先的に計算する
[アルゴリズム2]ITあるいはベンチャー系に関心がある人を優先的に計算する

アルゴリズム1はMixiのマイミク数がべき乗に分布していることを利用している。つまり、ハブとなる人を経由すれば、おのずと笠原氏とつながるだろうということである。
アルゴリズム2は「笠原氏」と繋がるであろうマイミクを「推定する」している。つまり、たんなる数学的な情報だけでなく、意味的な情報を含めて最短パスを計算する。

今まで、コミュニティの最短パスの計算等は単に数学的な研究結果を考慮してアルゴリズムを計算した場合が多かった。しかし、参加者の特性(特にアルゴリズム2)を利用したコミュニティのつながりに関する研究がもっと盛んに行うべきだと私は思う。つまり今までグラフ理論にプラスした「何か」の情報を加えた研究がこの手の分析には有効だと思うのだ。それはグラフ理論の有向グラフ、重み付けグラフ等に結局は帰するかもしれないが。

もしかすると、「意味のつながり」の近さ(日記やプロフィール、趣味など)を数学的に記述できるようになれば、アルゴリズム2のようなことは自動的に計算できるのかもしれない。

□終わりに
Mixiのようなコミュニティは一見ランダムなつながりだと思われるが、実は最近の研究では色々と特徴があることがわかっている。しかし、どうしてそのような特徴が現れるのかはまだ良くわかってない。
まずは自分の笠原数を計算してみて、グラフ理論そして複雑ネットワークの奥深さを実感して欲しい。

なお、参考書籍として増田 直紀氏らの「複雑ネットワークの科学」をお勧めしておく。

| | コメント (5) | トラックバック (1)

2006.09.23

[はてブ]SBMにおけるブックマーク「サゲ」攻撃の可能性

ビジネスやプライベートにおいてはてブを愛用している。使い方として、自分の興味のあるWebページをクリッピングをするのはもちろんこと、他の人のブックマークやホットエントリーを参考にして閲覧する事が多い。最近では特に後者の使い方の方がウェイトが高く、SBMを「インテリジェンスな」RSSリーダーライクに使っているのが実情である。(RSSリーダーとはてブとの比較は後日行いたい。)

□はてブとタグの関係

さて、はてブを使っていると気になる事がある。それは、各タグのページはブックマーク数が多い順(あるいはブックマークされた時間順)に表示できるということである。もちろん、それはありがたい機能だが問題なのは被ブックマークページに該当「タグ」(これをタグAとしよう)を一つでも付けた人がいれば、タグAのページに表示されてしまうことである。

もう少し具体的に書いてみよう。今、1000個ブックマークされているページPがあるとする。このとき例えば「セキュリティ」というタグを一人だけがつけたとしよう。すると、「セキュリティ」というタグにページPが表示されてしまう。

□はてブに対する「サゲ」攻撃

ここまで書くとわかってしまった人もいるかもしれない。つまり、ホットエントリーのようなブックマーク数の多い被ブックマークページに「全然関係ないタグ」を1個でも付けたらどうなるか?

例えば、セキュリティのページのはずなのに「モーニング娘。」というタグをつけると、「モーニング娘。」のタグの上位に全然関係ないセキュリティのページが表示されてしまう。すると、本来モーニング娘。に関するWebページがタグの画面においては表示される「はず」だが、上記攻撃によって意味のないページによって埋もうれてしまう。つまり2chでいうところの、「強制的に」意味のあるブックマークがサゲ進行にされてしまう事になる。

もう少し応用しよう。例えば気に入らないタグAがあったとする。(このようなタグの例として、嫌いなタレント、番組等が挙げられる)そこに、はてブの情報を抽出して自動的にホットエントリーにタグAを自動的につけてしまう。すると、タグAは無関係なページで埋まっていくということである。
つまり、SBMならではの「意味のあるページ」の表示ができなくなり、SBMの機能が停止してしまう。

□「サゲ」攻撃の対策は?

これはかなり難しい。先ほど書いた、自動的に「タグA」をつけるような攻撃は時間内にどれだけタグAとなるブックマークをするかどうかをチェックするというのが考えられるが、どこまで攻撃を回避できるかあるいは副作用がないのかが微妙である。

意味解析をしてタグとWebページとの相関を考える事も考えらるが、そもそもタグの内容自体はユーザ任せなのでこれも難しいだろう。

もし、良いアイデアがあれば教えてください。

*追記1:「sage」攻撃よりも「ageアラシ」という表現の方が良いとの指摘がありました。
*追記2:del.icio,usでは、既にこのような攻撃が起こっておりdel.icio.us側でも対策がされているようです。
参考:しっぽのさきっちょ「注目泥棒」
http://www.baldanders.info/spiegel/log/200609.html#d23_t4

| | コメント (3) | トラックバック (0)

2006.09.21

[Winny]Winnyネットワークをダウンさせる方法の提案

第2回DHT勉強会の講師として、DHT(分散ハッシュテーブル)のセキュリティ対策についてレクチャーを行ったが、オーバーレイなシステムについては、セキュリティの研究をもっと積極的に行うべきだと思った。意外にこの分野で研究をしている人が日本では少なかったりする。

ところで、DHTのセキュリティ対策を考えている際にWinnyのネットワークをダウンさせる効率のよい方法も考えたので、皆様の意見を聞きたいと思う。

□悪意のノードの混入でシステムダウンは可能か?

そもそもの考察の発端はDHTにおいてどの程度悪意のノードが混入した場合、システムがダウンするかを検討したことである。実は相当数の悪意ノードが混入しない限りシステムはダウンしない。この結論に従うと、たとえWinnyに悪意のノードを混入しても相当数の悪意のノードがない限りシステムはダウンしないことになる。

上流のノードを選択的に悪意のノードに置き換える攻撃方法を検討している人がいる。しかしながら上流ノードにおける隣接ノード数を考えてみると、ネットワーク全体レベルでのダウンを実際に実行しようとすれば、相当のリソースが必要となるだろう。このようなリソースが確保できるのは現状国家レベルの機関しかないだろう。

□P2Pならではの特徴を利用したアタック

ところが、P2Pならではの特徴を利用すると、一人のスーパークラッカーがいればオーバーレイ系、例えばWinnyのネットワークをダウンできる可能性がある。
ヒントはeEye社の鵜飼氏によるWinnyのプロトコル、脆弱性に関する講演である。
Winnyの解析とそのセキュリティ脅威分析セミナー概要
http://toremoro.tea-nifty.com/tomos_hotline/2006/05/winnywinny_21c2.html
鵜飼氏は上記講演にてWinnyにおける脆弱性について説明するとともに、近い将来P2Pネットワークを使ったワームが発生した場合、きわめて短時間でワームがP2Pネットワーク全体に蔓延するだろうと予測している。

Winnyのシステムをダウンさせるには、このようなP2Pワームを利用することとなる。
具体的にはスーパークラッカーが次のようなワームを作成すればよい。

☆ワームの機能
ワームの機能として
・特定時間以降はWinnyにおいてすべてのノードと接続しない機能
・アプリを常駐させ特定時間以降はWinnyのプロセス立ち上がりを妨害するorプロセスをダウンさせる機能
・P2Pシステムのメッセージ機能を利用してワームをP2Pシステムに拡散する機能
等が挙げられる。

この「特定時間」の設定が大切である。特定時間の設定の狙いはワームをP2Pシステム全体に可能な限り蔓延させ、ある時間に「一気に」P2Pシステムが崩壊させることが狙いである。このようにすれば、ある特定時間以降はWinnyの各ノードは、他のノードと接続できる可能性が極端に低下する。つまり、Winnyネットワークは1から立ち上がる必要があり、そのネットワーク成長は非常に遅いと考えられる。Winnyネットワークが現状のような規模に復活するには時間がかかるだろうし、それまでにワームの亜種が発生すれば、現在のようなネットワークサイズまで回復しないかもしれない。

もちろん、このようなワームが本当に現在のWinnyで作成可能かどうかは注意深い検討が必要だろう。

□終わりに

オーバーレイのネットワークにおいては、非常に短期間でワームが蔓延する恐れがある。特にDHTのようなホップ数が低いシステムではそのような特徴が顕著になる。
P2Pアプリを作成する際には、脆弱性について細心の注意が払う必要があると考えられる。

| | コメント (0) | トラックバック (2)

2006.09.18

[DHT]第2回DHT勉強会お疲れ様でした!

今日は第2回DHT勉強会でした。悪天候にも関わらず60人強もの参加者が集まり、熱心にDHTに関してディスカッションを行いました。

こんなニッチな勉強会にも関わらず、多くの人が集まるとは正直思っていませんでした。DHTへの関心の高さが伺えます。また講演の質の高さも素晴らしかったです。

私が特に関心を持ったのは吉田さんのSkipGraphの話題です。吉田さん曰く、DHTよりSkipGragphの方が長所が多いとのことです。ところで吉田さんのシステムはSkipGraphの上でDHTをまわしているのですが、もし吉田さんの主張が正しいなら、なぜSkipGraphで系全体を作らないのか疑問を感じました。(質問するのを忘れてしまいましたが。)またDHTよりSkipGraphのほうがどの点で優位なのか、私もきっちり考察してみたいと思います。

もう一つは加藤さんのDe Bruijn Graphの話。なるほどな!とうなづけるグラフ理論の興味深い応用です。この手法を使うとDHTとしてコンパクトなルーティングテーブルを持ち且つホップ数を抑えることができるようです。こちらも調べてあとでBlogに書きたいな。

なおプレゼン資料は順次以下のサイトにアップします。
http://homepage3.nifty.com/toremoro/study/study.html

また議事メモは無印吉澤さんが作成するとの事です。

次は第3回P2P勉強会 or VoIP Conferenceですね。こちらも是非注目してください。
その前にP2P新年会 or 忘年会かな?

| | コメント (6) | トラックバック (4)

2006.09.16

[P2P]UNIX MagazineにDHT入門記事を執筆しました!

本日(9/16[土])発売のUNIX Magazineは、なんとP2P特集です!
私もDHT入門ということで執筆させて頂きました。(夏休みは専らこの執筆作業をしていました。)
UNIX Magazineの目次については下記のリンクを参考して下さいね。
http://www.ascii.co.jp/books/magazines/unix.shtml

★総力特集 P2Pアーキテクチャ
・P2P技術の再考 浜辺将太
・分散ハッシュテーブル入門 西谷智広
・アプリケーション層マルチキャスト:基本と応用 首藤一幸
・地産地消P2Pネットワーク 斉藤賢爾
・P2Pと2つの「アーキテクチャ」 土井裕介
・【インタビュー】問題点の抽出と整理 山口 英
・P2P今後のアーキテクチャ 覆面座談会

(P2P関連部分のみ抜粋)

是非ともDHT勉強会の予習・復習用に活用してください。

| | コメント (0) | トラックバック (0)

2006.09.12

[DHT]第2回DHT勉強会懇親会

第2回DHT勉強会の後に懇親会を開きます。
基本的にはDHT勉強会参加者のための懇親会ですが、懇親会のみの参加もOKです。
DHT勉強会の講師と直で話せるチャンスですので是非とも参加して下さい。

□日時:9/18(月・祝)18:30~20:30
□場所:北海道 渋谷駅前店
http://r.gnavi.co.jp/g086283/
(個室を確保しました!)
□会費:出来高制ですが、4000円前後を想定
□定員:25名程度

参加申し込みはMixi経由です。
http://mixi.jp/view_event.pl?id=10188468&comm_id=128733

よろしくお願い致します。

| | コメント (0) | トラックバック (0)

2006.09.10

[DHT]DHTとホップ数の関係[その2]~Chordの平均ホップ数を考えよう

前回は直感的な方法でDHTのホップ数について推定した。今度はChordに絞ってホップ数を調べる事でより理解を深める事にしよう。

□Chordのリンク数からホップ数を推定

まず、Chordのノード参加数をN=2^xとしよう。2^xとは2のx乗を表す事とする。ここで1ノード当たりのリンク数はlog(N)=xである事に注意。

平均ホップ数を計算するときに発想を転換しよう。今1ノードxあたりのリンクがある。すると、P回ホップ数すると、ホップ可能な総ノード数LはだいたいL=x^Pとなる。x^P=Nであれば、P回ですべてのノードにアクセスできると大体考えられる事ができる。つまり、平均ホップ数P=log(N)/log(x)=log(N)/log(log(N))~O(log(N))となる。
最後の近似はやや荒っぽい。計算がlog(N)より小さく出たのはホップ時に到達するノード数の仮定が甘いからである。

□もう少し解析的にホップ数求める方法

今度は違った見方をしてみよう。この手法によるホップ数算定はこのBlogが初発表になるはずだ。

今ノード0からのリンクを考えると、総ノード数を2^xとして距離2^0、2^1・・・2^{x-1}のノードとリンクを張るはずだ。
ところで、ハッシュ空間にすべてノードが埋まっている場合、あるノードへ到達する際に次ホップする距離はホップ毎に単調減少するはずだ。(この証明は読者にお任せする。)
つまり、次ホップまでの距離をR、ホップ数をtとするとR(t+1)<R(t)である。
ところが、R(t)として取れる数は、{2^0、2^1・・・・2^{x-1}}というlog(N)個しかない。つまり、最大ホップ数はO(log(N))より超える事がないはずである。

ここで問題なのは、O(log(N))というステップ数で本当に2^xの空間のすべてのノードに到達できるかということである。

そのために補題を作る。
補題:
2^{x-1}+1≦P<2^x となる整数Pは、集合S{2^0、2^1、・・・2^{x-1}}の和で表される。ただし、この和において、集合Sの各元は高々1回しか現れないとする。

証明:帰納法により証明可能。

この補題により、O(log(N))のステップ数以内に、任意のノードに必ず到達できることが証明できた。
今はハッシュ空間にすべてのノードが参加していることを仮定した。ノードが部分的に参加してない場合の証明については読者にお任せする。

| | コメント (0) | トラックバック (0)

2006.09.08

[VoIP]VoIP Conference開催のお知らせ

昨年、P2Pイベントの一環としてSkype Conference 2005 を開催し、大好評を博しました。
Skype Conference 2005 公式HP

そこで今回は講演内容を拡大し、イベントタイトルも「VoIP Conference」と改めることにしました。
講演内容としては
・Asterisk
・Skype
・NGN
・FMC
・SIP最新動向
・VoIP 最新動向

に焦点を当てる予定です。
既にAsterisk関連の著作を書いている人と講演を調整しています。

そのほかの情報ですが、
□日時:2007年前半
□場所:未定(200人以上収容できる会場がベター。会場提供者求む!)
□主催者:VoIP Conference事務局(有志による開催、非営利)

となっています。

なお、本講演の講師について募集しています。自薦・他薦は問いません。
推薦いただける方はMixi経由またはメール(tnishita@yahoo.co.jp)でご連絡をお願い致します。

また本講演に興味のある方は、Mixiトピックを見てください。VoIP Conferenceの最新動向をチェックできます。

VoIP Conference 準備トピック
http://mixi.jp/view_bbs.pl?id=9787327&comm_id=43848

| | コメント (0) | トラックバック (1)

« 2006年8月 | トップページ | 2006年10月 »