プログラム依存グラフを利用した 情報漏洩解析手法の提案と実現 大阪大学大学院 情報科学研究科 ○西 秀雄 横森 励士 井上 克郎 ソフトウェアサイエンス研究会

発表内容 研究の背景 情報漏洩解析とは 既存の情報漏洩解析手法の問題点 提案する情報漏洩解析手法 実現した情報漏洩解析システムについて MAC方式によるアクセス制御法 情報フロー 情報漏洩解析の例 既存の情報漏洩解析手法の問題点 提案する情報漏洩解析手法 プログラム依存グラフの利用 一般的なセキュリティモデルへの対応 実現した情報漏洩解析システムについて システムの説明 手法の有効性の検証 まとめと今後の課題 ソフトウェアサイエンス研究会

研究の背景(1/2) クレジットカード番号等、第三者に知られてはならない情報を扱うシステムにおいて、不適切な情報漏洩を防ぐことは重要な課題である 情報漏洩を防ぐ手段として用いられるアクセス制御法(Mandatory Access Control, MAC方式)¶ アクセス可能 アクセス不可 機密情報　 xxxx…….. まず，研究の背景について述べます． 近年，ネットワーク上における商用取引が盛んになっています．それに伴い，例えばクレジットカード番号など，第三者にしられてはならない重要な情報を処理する機会も多くなっています． その処理を行うシステムでは，不適切な情報の漏洩を防ぐことが重要な課題です． 情報漏洩を防ぐ手段として用いられるアクセス制御法として以下の図に示すようなものがあります． システム中に，それぞれ機密情報を格納したファイル，公開情報を格納したファイルがあります． 機密情報に対してアクセスする権限を持つ管理者は，機密情報ファイル，公開情報ファイルどちらにもアクセス可能ですが， 一般ユーザは公開情報にのみアクセス可能であるとします． 一般ユーザが機密情報ファイルにアクセスしようとすると，システムがアクセスを拒否します． このような形で，情報に対してその機密度，各ユーザに対してアクセス権限を与えることで，一般ユーザが機密情報に対してアクセスすることを防ぎます． 公開情報 zzzz…….. 管理者 一般ユーザ secret public システム ¶G.Purnul “Database Security“ Advances in Computers (M. Yovits Ed.), Vol.38, pp.1-72, 1994 ソフトウェアサイエンス研究会

研究の背景(2/2) プログラムによって引き起こされる情報漏洩 利用者が本来アクセス不可能な機密度の高い情報を、ユーザプログラムがアクセス可能な記憶領域に書き出してしまうこと プログラムが引き起こす情報漏洩を検出するために、情報漏洩解析手法が提案、実現されている アクセス可能 アクセス不可 (間接)アクセス 機密情報　 xxxx…….. プログラム ………… readln(x); writeln(x); 公開情報 zzzz…….. 管理者 xxxx…….. 一般ユーザ しかしながら，先ほどのシステムでは次のようにプログラムによって引き起こされる情報漏洩の可能性があります． あるプログラム実行が機密情報を読み取り，それを一般ユーザが参照できるような公開情報ファイルに書き出してしまったとき，一般ユーザは機密情報への直接アクセスはできませんが，公開情報ファイルにアクセスすることで，先ほど書きだされた機密情報のデータを間接的にアクセス可能となります． このときプログラムが情報漏洩を引き起こしたことになります． このように，プログラムによって引き起こされる情報漏洩を検出するため，プログラムを静的に解析しその情報漏洩の可能性を判断する，情報漏洩解析手法が提案，実現されています． 情報漏洩 secret public ソフトウェアサイエンス研究会

発表内容 研究の背景 情報漏洩解析とは 既存の情報漏洩解析手法の問題点 提案する情報漏洩解析手法 実現した情報漏洩解析システムについて MAC方式によるアクセス制御法 情報フロー 情報漏洩解析の例 既存の情報漏洩解析手法の問題点 提案する情報漏洩解析手法 プログラム依存グラフの利用 一般的なセキュリティモデルへの対応 実現した情報漏洩解析システムについて システムの説明 手法の有効性の検証 まとめと今後の課題 ソフトウェアサイエンス研究会

情報漏洩解析 プログラムを静的に解析することで得られるデータの推移関係をもとに、入力値の機密度から出力値の機密度を求める プログラムが、どのような記憶領域に、どのような機密度のデータを出力するのか解析できる プログラム実行において、重要な情報が漏洩する可能性があるかどうか判定するために利用 各データの持つ機密度 : セキュリティクラス 変数間に存在するデータ授受関係 : 情報フロー ソフトウェアサイエンス研究会

MAC方式によるアクセス制御法 セキュリティクラス(以後SC): データの機密度 セキュリティモデル： システムにおける各SCの強弱 一意な最大元、最小元が存在 任意の2元の最小上界，最大下界が 定義されている クリアランス： 利用者に割り当てられた、 　 データへのアクセス権限 データの参照 データのSCが利用者のクリアランスより小さいか 等しければ、利用者はそのデータを参照可能 クリアランス3ならば全てのデータを参照可能 クリアランス1ならばSC0、1のデータを参照可能 最大元 3 1 2 最小元 セキュリティモデル ソフトウェアサイエンス研究会

情報フローとは プログラム中の変数間に存在するデータ授受関係 explicit flow : 変数の定義～参照間に存在 implicit flow : 分岐(繰り返し)命令の条件節と内部の文の間に存在 1: b := 5; 2: c := 5; 3: if ( c > 0 ) then begin 4: a = b 5: end; ソフトウェアサイエンス研究会

情報漏洩解析の例(1/2) a (SC:1) のデータと b (SC:2) のデータが c にフローする 3行目の代入後の c は a 、 b 両方のデータに関する情報を持つ 代入後の c のSCは a と b のSCの最小上界として求められる(この場合SC 3) 3 1 2 セキュリティモデル 代入後の c のデータを参照できるのは、 a 、b 両方のデータを参照できるクリア ランスを持つ利用者であるべき 1: readln(a); 2: readln(b); 3: c = a + b; explicit flow ソフトウェアサイエンス研究会

情報漏洩解析の例(2/2) a (SC:0)のデータと b (SC:2)のデータがc にフローする 5行目の代入後の c は a 、 b 両方のデータに関する情報を持つ 代入後の c のSCは a と b のSCの最小上界として求められる(この場合SC 2) 3 1 2 セキュリティモデル 代入後の c のデータを参照できるのは、 a 、b 両方のデータを参照できるクリア ランスを持つ利用者であるべき 1: readln(a); 2: readln(b); 3: if (b>0) then 4: begin 5: c = a 6: end; explicit flow implicit flow ソフトウェアサイエンス研究会

発表内容 研究の背景 情報漏洩解析とは 既存の情報漏洩解析手法の問題点 提案する情報漏洩解析手法 実現した情報漏洩解析システムについて MAC方式によるアクセス制御法 情報フロー 情報漏洩解析の例 既存の情報漏洩解析手法の問題点 提案する情報漏洩解析手法 プログラム依存グラフの利用 一般的なセキュリティモデルへの対応 実現した情報漏洩解析システムについて システムの説明 手法の有効性の検証 まとめと今後の課題 ソフトウェアサイエンス研究会

既存の情報漏洩解析手法の問題点 既存手法およびその実装¶ 問題点 各文内・文間の情報フローに基づいた、データフロー方程式の繰り返し計算による手法 問題点 言語ごとに解析アルゴリズムを定義する必要があり、汎用性に欠ける 入力値のSCの変更のたびに再度繰り返し計算が必要で、効率が悪い 2値のSCをとるセキュリティモデルにのみ対応しており、 一般的なセキュリティモデルに対応していない セキュリティモデル ¶横森励士, 大畑文明, 高田義朗, 関浩之, 井上克郎: "セキュリティ解析アルゴリズムの実現とオブジェクト指向言語への適用に関する一考察", 電子情報通信学会技術研究報告、SS2000-27～30, Vol.100, No.472, pp. 17-24, 2000. ソフトウェアサイエンス研究会

発表内容 研究の背景 情報漏洩解析とは 既存の情報漏洩解析手法の問題点 提案する情報漏洩解析手法 実現した情報漏洩解析システムについて MAC方式によるアクセス制御法 情報フロー 情報漏洩解析の例 既存の情報漏洩解析手法の問題点 提案する情報漏洩解析手法 プログラム依存グラフの利用 一般的なセキュリティモデルへの対応 実現した情報漏洩解析システムについて システムの説明 手法の有効性の検証 まとめと今後の課題 ソフトウェアサイエンス研究会

束上の任意の2元の最小上界を二次元行列で記述することで 一般的なセキュリティモデルに対応 提案する情報漏洩解析手法 プログラム依存グラフ(PDG)を利用した情報漏洩解析 問題点1. 言語ごとに解析アルゴリズムを定義する必要があり 汎用性に欠ける PDGの利用による汎用性の向上 問題点2. 入力値のSCの変更のたびに再度繰り返し計算が 必要で、効率が悪い PDGの再利用性による効率の向上 問題点3. 一般的なセキュリティモデルに対応していない 束上の任意の2元の最小上界を二次元行列で記述することで 一般的なセキュリティモデルに対応 ソフトウェアサイエンス研究会

プログラム依存グラフ （Program Dependence Graph, PDG） プログラムの各文を頂点、 文間に存在する依存関係を有向辺としたグラフ プログラムの文間の依存関係 データ依存関係 変数の定義～参照 制御依存関係 条件節～述部 1: a=5; 2: b=3; 3: if (b>0) { 4: c=a; 5: }else{ 6: d=b; 7: } データ依存関係 制御依存関係 PDG 1 2 3 6 4 データ依存辺 制御依存辺 ソフトウェアサイエンス研究会

情報フローとPDG 情報フローとPDGが示す依存関係の等価性に着目 explicit flowとデータ依存辺、 implicit flowと制御依存辺を対応させる PDGが示す依存関係から情報フローが求められる PDGを利用した情報漏洩解析が可能 情報フロー explicit flow implicit flow PDG データ依存辺 制御依存辺 ソフトウェアサイエンス研究会

提案手法の言語独立性と再利用性 PDGはプログラム中のデータの推移関係を表す 入力値のSCを変更しても、同一のPDGで 情報漏洩解析が可能 ソフトウェアサイエンス研究会

一般的なセキュリティモデルへの対応 束上の任意の2元の最小上界を二次元行列で記述 一般的なセキュリティモデルへの対応 5 3 4 1 2 二次元行列を参照することで、最小上界が求められる 一般的なセキュリティモデルへの対応 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 1 3 3 5 5 2 2 3 2 3 4 5 3 3 3 3 3 5 5 4 4 5 4 5 4 5 5 5 5 5 5 5 5 5 3 4 1 2 セキュリティモデル ソフトウェアサイエンス研究会

PDGを利用した情報漏洩解析の実現 PDGを構築 SCの初期化 各入力文を起点としてPDGを探索し、各頂点のSCを求める 結果を出力 セキュリティモデルの読み込み 各入力文に対応する頂点に対しSCの初期値を与える 各入力文を起点としてPDGを探索し、各頂点のSCを求める すでに高いSCが与えられている頂点への辺はたどらない 探索が合流する頂点ではSCの最小上界をとる 結果を出力 起点 起点 起点 データ依存辺 入力文 その他の文 制御依存辺 また、一度目の解析においてはPDGを構築する必要がありますが、二度目以降の解析においては構築したPDGを探索することで 情報漏洩解析を行うことができるので、必要な処理は以上のようになります。 例えばこのように各入力文のSCの初期値を変更したとき、PDGを構築する必要はなく、探索のみで解析が行えます。 セキュリティモデル ソフトウェアサイエンス研究会

発表内容 研究の背景 情報漏洩解析とは 既存の情報漏洩解析手法の問題点 提案する情報漏洩解析手法 実現した情報漏洩解析システムについて MAC方式によるアクセス制御法 情報フロー 情報漏洩解析の例 既存の情報漏洩解析手法の問題点 提案する情報漏洩解析手法 プログラム依存グラフの利用 一般的なセキュリティモデルへの対応 実現した情報漏洩解析システムについて システムの説明 手法の有効性の検証 まとめと今後の課題 ソフトウェアサイエンス研究会

実装(1/2) 既存のスライス抽出システムOsaka Slicing Systemを拡張 入力文 その他の文 情報漏洩解析 PDG PDG 前提条件の入力 1. セキュリティモデル 2. 入力文、戻り値で定義されるデータのSC 入力文 情報漏洩解析 その他の文 PDG PDG PDG 構文、意味解析 結果の出力 セキュリティモデル ソフトウェアサイエンス研究会

実装(2/2) 情報漏洩解析の問題点 関数の戻り値データに対するSC制約機能 情報フローにのみ従い解析を行う 情報を隠蔽可能な暗号化通信路の存在や、情報の復元や類推が不可能な状況は考慮されていない 現実的には問題がないデータのSCが過度に高くなってしまう場合がある 関数の戻り値データに対するSC制約機能 重要な情報の復元・類推が不可能であると判断できる戻り値データに対し、そのSCをユーザが指定できる データのSCを現実的な値に補正可能 ソフトウェアサイエンス研究会

評価1: 解析効率の向上 解析対象: 約2500行のプログラム 評価方法 PDGの再利用性による、効率の向上 解析対象: 約2500行のプログラム 評価方法 既存のシステム、作成したシステムそれぞれで、入力文のSCを同条件で設定し、繰り返し解析する 既存のシステムと作成したシステムの実行時間の累計を比較 PDGの再利用性による、効率の向上 約２５００行のプログラムに対し同条件でSCを設定し解析を繰り返し行い、実行時間の累計を比較しました。 結果は右の表のようになりました。１度目の解析には同程度の時間がかかっていますが、解析を重ねるにしたがって 実行時間に開きがでています。 これにより作成したシステムの有効性が確認できました。 これはPDGのもつ情報を繰り返し利用できるためです ソフトウェアサイエンス研究会

評価2:複雑なセキュリティモデルを持つ システムへの適用(1/5) 事例: 学生の成績管理システム(約400行) ユーザおよびそのクリアランス 学生 ：4 教養事務 : 3 専門事務 : 5 6 3 4 5 主なデータ 各データのSC 教養科目の成績 1 専門科目の成績 2 教養科目の事務の認証番号 3 学生の認証番号 4 専門科目の事務の認証番号 5 1 2 各ユーザの認証番号はSCが高く、重要な情報である セキュリティモデル ソフトウェアサイエンス研究会

評価2:複雑なセキュリティモデルを持つ システムへの適用(2/5) 学生の成績管理システムの構造 認証関数 入力 認証番号 main関数 ・入力によりユーザを識別 ・ユーザのクリアランスを 戻り値として返す ・戻り値として得られたクリアランスを持つユーザが 可能な処理を行う関数を呼び出す return 認証関数の戻り値を条件式として分岐 クリアランス３ クリアランス4 クリアランス5 束構造のSCを持つシステムへの適用事例として、学生の成績管理システムに対し今回作成したツールを適用しました。 このシステムでは、認証部分で認証番号が読み込まれ、その認証番号により、ユーザが何者であるか判断されます。 ユーザの種類は認証部分の関数の戻り値として返されます。 そしてその戻り値によりユーザが行うことのできる処理が可能となります。 このシステムのSCはこのようになっております。 また、主なデータとそのSCを右の表に示します。 例えば学生はSC4までのデータを参照する権限を持ち、教養科目の成績、専門科目の成績、自身の認証番号を知る ことができます。 教養事務の処理関数 学生の処理関数 専門事務の処理関数 ・全学生の教養科目の 成績の更新 ・自身の両科目の 成績の参照 ・全学生の専門科目の 成績の更新 各ユーザのクリアランス 学生 ：4 教養事務 : 3 専門事務 : 5 ソフトウェアサイエンス研究会

評価2:複雑なセキュリティモデルを持つ システムへの適用(3/5) SCが高い出力文が非常に多い 認証番号は隠蔽を行っているので、この結果は不自然 戻り値のSCが過度に高くなっている? 認証関数の戻り値から認証番号の類推は不可能 戻り値のSCをlowとして設定 1 26 5 6 3 4 5 右上の図がシステムの実行結果です。 システム中には33個の出力文があります。 右下の図の各SCの右の値は、解析の結果、各SCとなった出力文の数です。 SCの高い出力文が多いほど情報漏洩の可能性が高くなります。 過度に高いSCが設定されてしまうという、情報フローの問題点を解決できます。 これを用いると、例えば隠蔽を施すべきデータ(関数)を推測する手助けとなります。 1 2 各SCの右下の数字: 結果そのSCとなった出力文の数 セキュリティモデル ソフトウェアサイエンス研究会

評価2:複雑なセキュリティモデルを持つ システムへの適用(4/5) 学生の成績管理システムの構造 認証関数 入力 認証番号 main関数 ・入力によりユーザを識別 ・ユーザのクリアランスを 戻り値として返す ・戻り値として得られたクリアランスを持つユーザが 可能な処理を行う関数を呼び出す return 認証関数の戻り値を条件式として分岐 過度に高いSC クリアランス３ クリアランス4 クリアランス5 束構造のSCを持つシステムへの適用事例として、学生の成績管理システムに対し今回作成したツールを適用しました。 このシステムでは、認証部分で認証番号が読み込まれ、その認証番号により、ユーザが何者であるか判断されます。 ユーザの種類は認証部分の関数の戻り値として返されます。 そしてその戻り値によりユーザが行うことのできる処理が可能となります。 このシステムのSCはこのようになっております。 また、主なデータとそのSCを右の表に示します。 例えば学生はSC4までのデータを参照する権限を持ち、教養科目の成績、専門科目の成績、自身の認証番号を知る ことができます。 教養事務の処理関数 学生の処理関数 専門事務の処理関数 ・全学生の教養科目の 成績の更新 ・自身の両科目の 成績の参照 ・全学生の専門科目の 成績の更新 各ユーザのクリアランス 学生 ：4 教養事務 : 3 専門事務 : 5 ソフトウェアサイエンス研究会

評価2:複雑なセキュリティモデルを持つ システムへの適用(5/5) 戻り値のSCをlowとして設定することでSCの高い出力文が削減された 現実的には情報漏洩の危険性は微々たるもの 一般的なセキュリティモデルを持つシステムへの提案手法の適用 SC制約機能の有効性を確認 現実的な情報漏洩の可能性を判断できた 隠蔽すべきデータを判断する指標にすることも可能 2 1 27 6 3 4 5 右上の図がシステムの実行結果です。 システム中には33個の出力文があります。 右下の図の各SCの右の値は、解析の結果、各SCとなった出力文の数です。 SCの高い出力文が多いほど情報漏洩の可能性が高くなります。 過度に高いSCが設定されてしまうという、情報フローの問題点を解決できます。 これを用いると、例えば隠蔽を施すべきデータ(関数)を推測する手助けとなります。 1 2 各SCの右下の数字: 結果そのSCとなった出力文の数 セキュリティモデル ソフトウェアサイエンス研究会

まとめ PDGを利用した、一般的なセキュリティモデルを対象とする情報漏洩解析手法を提案、実現した 今後の課題 情報漏洩解析の効率化と、汎用性の向上 一般的なセキュリティモデルを持つシステムへの対応 実装による手法の有効性を確認 繰り返し解析における解析効率の向上 複雑なセキュリティモデルを持つシステムへの対応 SC制約機能による現実的な利用度の向上 今後の課題 他のプログラム言語に対する提案手法の適用 ソフトウェアサイエンス研究会