Cl-GBI法によるふるまいのグラフの類似に基づく群れのモデルの提案 200902799 安竹有輝背景、問題人の行為（＝ふるまい）によって生じる、情報漏えいが止まらない。スマホ、PC/ クライアント Xはファイル1を読めない。ファイル2は読める。データサーバ X データセンタ/サーバ X Y ファイル1 φ Read ファイル2 Read Write データサーバファイル1をR、ファイル2にW The Internet Y 後にX,Y=subject ファイル1,2=object として用いる． The Internet Xがファイル2をR 情報漏えい X Y クラウドファイルシステムの構想群を守るモデル。セキュリティ面から群から離れないような仕組みを作る小泉 ACOやBoidなど群知能を使った”集まる”という基礎的な仕組みを作る鈴木エージェント管理動き任意のファイル任意のファイル要素任意のファイル・フレンドシップモデル・クラスメートモデル・Ant Colony Optimization ・ファイルのタグ、色・群集合（ふるまいの履歴）任意のファイル・リンゴ・赤色・甘くて、美味しいです。アクセスの順番、ふるまいの履歴などファイルの持つ”形”から情報をセパレートする安竹安竹キーワードやファイルの中身から、含用率から重要度や竹村群の中心を判断する「動き」と「要素」の橋渡しとして家族的類似（パラメータ）が用いられる。クラウドファイルシステムの様々な仕組みを統括しての、総合的な実装を目的とする目的 • アクセス行列からグラフの類似度を探し出す数式を書き、似ているふるまいが群れを成すようにする． Mason上に生成された群れを使ってcovert channelをセパレートするのが最終目的。（アクセス行列からCovert Channelをセパレートすることによって、群れ全体を護ることになる．） S1 O1 O2 S2 Read Read Write 情報漏えいふるまい，アクセス行列，類似度の説明クラウドファイルシステムに人がRead,Writeする行為を``ふるまい’’と呼ぶ． Read,Write（ふるまい）の連鎖＝アクセス行列である．アクセス行列の一部を抜き出し、類似度の高いものを集める．類似度の高い物＝形の似ているもの S 1 O 1 S 2 S 1 O 1 O 4 類似度の似ているグラフアクセス行列の例 S 2 O 4 Cl-GBI法について求めたいノードを入力するとそれを含む似ているペアを作る．そこからさらに似ているグラフを作りだす．（後にこれを抽出グラフとして使用する） S=Subject,O=Object Masonについて • MasonはMulti agent simulatorである。 • 従来のMulti agent simulatorに比べて高速。 • シミュレーションの様子を、客観的に第三者的（例えるなら神様のような）視点から観察することができる。 Masonのシュミレーション例(ball) 提案モデルの流れ 1.アクセス行列からCl-GBI法を用いて，複数の似ているパターンのグラフを抜き出す． 2.抜き出したグラフの類似度を``構造類似性’’を用いて求め，それをMason上のAgentに引力斥力として与える． 3.Agentで群れを作る． 4.Covert Channel分析をし，セパレートする．グラフの類似度を求めるところまでを手掛けた． 5.以上を行って，群れが保っていることを確かめる．提案モデルにおける研究の現段階 O 4 アクセス行列の例 S 1 O 1 S 2 Cl-GBI法を用いて、グラフを抜き出す ① S 1 O 4 S=subject O=object ② 構造類似性を用いて、グラフ同士の類似度を求める O 1 S 2 S 1 O 1 S 2 O 4 制限を付けたグラフ間の類似度を計算するアルゴリズムグラフ S 1 O 4 O 1 S 2 S 1 O 1 S 3 S 2 O 5 S 1 O 1 S 2 S 2 P1: S 1 O 1 P2: O 1 S 2 P3: O 4 S 1 O 1 P4: S 1 O 1 S 3 設ける制限１．対象となるグラフは木構造である．２．抽出パターンは単純パス．３．各ノードは2種類に分類できる．抽出パターン参考にした文献をもとにアルゴリズムを組んだ S 1 O 4 O 1 S 2 グラフ1 S 1 O 1 グラフ2 S 3 S 2 O 5 S 1 O 1 S 2 + 抽出パターングラフ3 ①P1のノードの両端の始点、終点を定める．グラフ1の中に始点と種類が同じノードを選択する．グラフ１を木構造とみなし、スタックを用い、P1と一致する箇所をカウントする．（P2,3…に関しても行い、その後グラフ2，3に関しても同様に①を行う．) ②カウントした数値を用い、一致度、不一致度を求める．類似度の計算方法対象とするグラフ集合から抽出された部分グラフ集合を P ，抽出された部分グラフ数を J ， k k k ノード nik を含む部分グラフp j  P, j  1,2,，, J , の数を mij  m (ni , p j ) とおくと，任意のグラフ Gk は以下に示す行列 M k で表現することができる． Mk  m11k m12k  m1kJ k m21 k m22    m k Ik 1      m k Ik J 対象となるグラフ集合全体から抽出されている部分グラフの数を J それぞれの構造分布行列を M 1 ,M 2 部分グラフ p j を構成するノード数をsize( p j ) ノードペアの個数 I グラフG1のノードxとグラフ2のノードｙのノード間類似度 r 12 およびノード間相異値 d 12 xy xy を以下のように定義する． J rxy12   α・j min(m1xj , myj2 ) 1 αj  size( p ) j j 1 J d xy  βj mxj  myj 12 j 1 1 2 1 βj αj m  m (n , p j )  M1 i  1,2,, I1 m  m (ni , p j )  M 2 i  1,2,, I 2 I 2  I1 1 ij 2 ij 1 2 1 i 2 12 これらを用いて、ノード間類似度 sxy を以下のように定義する． s 12 xy  12 xy r 12 xy r d 12 xy グラフ間類似値 S 12 グラフ間相異値 R12 グラフ間類似度 D 12 12 R S  12 R  D12 12 Mason上のAgentの引力，斥力となる． I2 R  r 12 i 1 I2 D  d 12 i 1 12 xi y i 12 xi y i グラフ１とグラフ２を用いて求めた結果 C:一致度 E:不一致度類似度=0.739130 似ている形のグラフを集めるための数式の値として使える．まとめ • プログラミングにより，一致度の算出に成功した． • MasonでAgentが動くプログラミングを書いた． • クラウドファイルシステムのCovert Channel分析において，アクセス行列の``形’’に着目したものは今までなく，本研究はこの分野の新しいモデルを提案できた． • グラフの形の類似度をMasonの引力斥力を設定するのと，Covert Channel分析をするのに新しいアルゴリズムが作るのが今後の課題である．制限を付けたグラフ間の類似度を計算するアルゴリズム設ける制限１．対象となるグラフは木構造である．２．抽出パターンは単純パス．３．各ノードは2種類に分類できる．参考にした文献をもとにアルゴリズムを組んだ C 3 O 4 C 2 C 1 C 3 C 2 C 1 C 4 グラフ1 グラフ２ C 4 C 3 C 2 グラフ３ C 1 + ①P1のノードの両端の始点、終点を定める．グラフ1の中に始点と種類が同じノードを選択する．グラフ１を木構造とみなし、スタックを用い、P1と一致する箇所をカウントする．（P２，３に関しても行い、その後グラフ2，3に関しても同様に①を行う．) ②カウントした数値を用い、一致度、不一致度を求める．