木下研究室鈴木遼  従来の主な情報漏えい対策の目的は, 個人情報や企業機密のような秘密情報がそのまま丸ごと漏えいをしないようにすることだった．  しかし, 一つ一つの情報それ自体は秘密情報でなかったとしても，それらが複数集まり何らかの推論を施すことによって, 秘密情報を抽出できてしまうこともある.   通常のcovertchannel解析では困難だった推論をグラフを用いて表現する.ハイパーグラフを用いることで同じオブジェクトに適用する複数の推論を表現可能にする. 推論を考慮した情報漏えいの解析が可能となる. S0 S1 S2 O1 R O2 R O4 R O5 S4 S5 R R O3 S3 R R R R O2 (S0,S1) O1 R R (S1,S2,S4) R O5 R R R (S1,S3,S4) O3 (S0,S3,S4,S5) O4 (S0,S2,S5)    twitter利用者のアカウント,プロフィール,登録リストなどからmixiのアカウントが発見された. mixiのコミュニティから大学名,入学年度が発見.それからの類推により,所属サークルも割り出された. facebookのアカウントも発見,顔写真も漏えい.そして過去のtwitterからの「○階から見る景色」「そんなに○○が食べたいか」といった発言からアルバイト先の情報も割り出された. twitter つぶやきつぶやき１登録リストアカウントプロフィール mixi つぶやき2 facebook アカウント大学名入学年度サークルアカウント顔写真アルバイト先目次      ACLとcovert channel（従来の情報漏えい対策） ACL :誰がどの情報にアクセスできるかをまとめたリスト covert channel:ACL上で意図しない情報漏えいを起こす可能性がある経路推論を考慮した依存関係のリスト化有向グラフのリスト着色としてのモデル化ハイパーグラフでの拡張不自由なACLを判別するアルゴリズム   Subject(利用者)をS1,S2.Object(情報)O1,O2とする S1はO1 に対してread 可能でO2 に対してread とwrite 可能であり, S2 はO1 に対してはread もwrite も不可能でO2 に対してread 可能であることを意味している．  しかし,S1がO1の内容をO2 にwrite することにより本来S2が読めないO1の情報をO2を中継して読むことが可能となる.    R：Read,情報の読み込み W：write,情報の書き込み Φ：読み書き不可 ACL ACLの情報の流れをグラフ化 S1 S2 O1 O2  グラフ上での実線は read, 破線はwrite , 矢印の向きは情報の流れを意味する． S1 S2 O1 O2 従来のcovert channel対策では殆どがφになってしまい,使い物にならないACLとなってしまう.    covert channel があるからといって実際に情報漏えいが起きるわけではない. 実際にアクセスしたかどうかを考慮して監視する必要性がある. Object間に何らかの推論規則が存在する場合,これも考慮しないといけない. この二つの問題を同時に考慮できるモデルを提案する.  推論を考慮した依存関係のリスト化 ACL 依存関係のリスト S1 推論元オブジェクト推論導出オブジェクト O1 Ｒ O2 O1,O2,O3 ⇒ O4 Ｒ O3 Ｒ O4,O6 ⇒ O5 O4 Φ O3,O6 ⇒ O8 O5 Ｒ O6,O8 ⇒ O7 O6 Ｒ O4 ⇒ O6 O7 Φ O8 Ｒ有向グラフのリスト着色としてのモデル化色集合(C)={C0,C1,C2,C3,C4,….…Cn} (C0,C2) (C0,C1,C3)  (C3,C4)  (C1,C2,C4) 各ノードに塗ってもよい色のリストが与えられている. リストに従って塗ることをリスト着色という.  オブジェクト間の依存関係をグラフ化する．推論元オブジェクト推論導出オブジェクト O1,O2,O3 ⇒ O4 O4,O6 ⇒ O5 O3,O6 ⇒ O8 O6,O8 ⇒ O7 O4 ⇒ O6 O3 O1 O4 O2 O5 O6 O7 O8  オブジェクト間の依存関係をグラフ化する． S0 S1 S2 S3 O1 Ｒ S4 色集合(S)={S0,S1,S2,S3,S4} (S1,S3) Ｒ O2 ＲＲ O3 ＲＲ O4 Ｒ O5 Ｒ O6 ＲＲＲ O7 ＲＲＲ O8 ＲＲＲ O1 ＲＲ (S0,S2) ＲＲＲ O3 (S0, S1,S4) (S0,S2,S3) (S0,S2,S3) Ｒ O4 Ｒ O6 O2 (S0,S1,S2,S3,S4) O5 (S0,S3,S4) O7 O8 (S0,S1,S4) 色集合(S)={S0,S1,S2,S3,S4}    色を塗るということは情報を読んだとする. (S1,S3) O1 (S0,S2) リスト着色ならば情報漏えいが起きていない．リスト着色でなければ情報漏えいが起きている. O3 (S1,S0,S4) O4 (S0,S2,S3) (S0,S2,S3) O6 O2 (S0,S1,S2,S3,S4) O5 (S0,S3,S4) O7 O8 (S0,S1,S4) オブジェクト間の依存関係をグラフ化する．  推論元オブジェクト推論導出オブジェクト O1,O2,O3 ⇒ O4 O4,O6 ⇒ O5 O3,O6 ⇒ O8 O6,O8 ⇒ O7 O4 ⇒ O6 色集合をサブジェクト(S), ノードをオブジェクト(O) として扱う. 色集合(S)={S0, S1,S2,S3,S4} (S1,S3) O3 (S1,S0,S4) O1 (S0,S2)  O4 (S0,S2,S3) (S0,S2,S3) O6 O2 (S0,S1,S2,S3,S4) O5 (S0,S3,S4) O7 O8 (S0, S1,S4)  P =「任意の頂点v に対して, v を終点とする全ての有向辺(u1,v),・・・,(uk,v) の始点ui が同一色で塗られているならば, v とuiも同じ色でなければならない．」とした時に推論による情報漏えいの安全性を以下のように定義できる.  定義：条件Pを満たす着色がリスト着色ならばその着色は推論に対して安全である． u１ V u３ u２ (S1,S2,S4) 推論元オブジェクト推論導出オブジェクト O1,O2 ⇒ O4 (S0,S1) O1,O3 ⇒ O4 O1,O2,O4 ⇒ O5 O1 O1,O3,O5 ⇒ O2  通常の有向グラフでは表現できなかった依存関係のリストもハイパーグラフで表現することができる. O2 O5 (S1,S3,S4) O4 O3 (S0,S3,S4,S5) (S0,S2,S5)  P = 「任意の頂点v に対して, v を終点とする全ての有向辺A, B の始点集合A が同一色で塗られているならば,B の頂点も同じ色で塗られなければならない．」としたときに推論による情報漏えいに対する安全性を以下のように定義することができる.  定義：ある条件P がリスト着色ならばその着色は推論に対して安全であるという．   ACLと推論リストを合わせた時にどうやってもリスト着色ができない推論に対して不自由なACLが存在する. 実際に情報を読み込む前に与えられたグラフが不自由な ACLであるかを判別するアルゴリズムを次に提案する. 色集合(S)={S0,S1,S2,S3,S4,…Sn} (S1,S3) O3 (S1,S0,S4) O1 (S0,S2) O4 (S2,S3) O6 O2 (S0,S1,S2,S3,S4) O5 (S0,S3,S4) (S0,S2,S3) O7 O8 (S0,S1,S4)     Step1.グラフ全体のノードの中からリストの数が1であるものから色を塗っていく. Step2.その次にL≧2のノードにも色を塗って全てのノードの色を塗る. Step3.塗り終わったら,グラフの中から推論によりノードの色が決まるものが存在すればその色に変更する. 推論を全て行い、リスト着色の条件を満たせば少なくても安全なサブジェクトの色分けが存在するからACLに問題がないと判別することができる. 色集合(S)={S0,S1,S2,S3,S4,…Sn} (S0,S3)  また,右の図のような場合の時にO5が推論によりS0,S3 のどちらかに塗らなければならない場合は両方のパターンを記述しておく. (S0,S1,S4) O2 O1 (S0,S2) O7 (S0,S2,S3) O3 (S3,S4) O5 O6 O4 (S0,S3,S4) (S1,S3,S4)     ACLのアクセスタイミングと推論問題を両方表現可能なモデルを提案した. 推論的依存関係をハイパーグラフでモデル化した. ACLのアクセスタイミングをハイパーグラフの頂点着色で表現した. ACLと推論リストを合わせた時にどうやってもリスト着色ができないグラフを判別するアルゴリズムを提案した.  提案モデル上でどのような問題設定をすれば良いか.  推論による情報漏えいの可能性が検出された場合, どのようにACLを修正すれば良いか.  アルゴリズムを用いてACLの安全性をどのように評価するか.    鈴木遼,鈴木一弘,森住哲也,木下宏揚,“推論による情報漏えい防止のためのハイパーグラフによる依存関係のモデル化” 電子情報通信学会情報セキュリティ研究専門委員会（ISEC研）, 2011年暗号と情報セキュリティシンポジウム（SCIS2011）,2F3-1,2011年1月鈴木一弘, 鈴木遼, 森住哲也, 木下宏揚,“ 推論による情報漏えい防止のためのハイパーグラフモデル”信学論D(載録決定) 鈴木遼, 鈴木一弘, 森住哲也, 木下宏揚, “ 推論による情報漏えい防止のためのハイパーグラフによる依存関係のモデル化の改良”技術と社会・倫理研究会(SITE),2012 年3 月 (予定)