スライド 1

プログラム依存グラフを利用した
情報漏洩解析手法の提案と実現
大阪大学大学院
情報科学研究科
○西秀雄横森励士井上克郎
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
1
発表内容
研究の背景
情報漏洩解析とは
MAC方式によるアクセス制御法
情報フロー
情報漏洩解析の例
既存の情報漏洩解析手法の問題点
提案する情報漏洩解析手法
プログラム依存グラフの利用
一般的なセキュリティモデルへの対応
実現した情報漏洩解析システムについて
システムの説明
手法の有効性の検証
まとめと今後の課題
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
2
研究の背景(1/2)
クレジットカード番号等、第三者に知られてはならない情報
を扱うシステムにおいて、不適切な情報漏洩を防ぐことは重
要な課題である
情報漏洩を防ぐ手段として用いられるアクセス制御法
(Mandatory Access Control, MAC方式)¶
アクセス不可
アクセス可能
機密情報
xxxx……..
公開情報
管理者
secret
¶G.Purnul “Database Security“
Advances in Computers (M. Yovits Ed.), Vol.38, pp.1-72, 1994
zzzz……..
システム
一般ユーザ
public
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
3
研究の背景(2/2)
プログラムによって引き起こされる情報漏洩
利用者が本来アクセス不可能な機密度の高い情報を、ユーザプロ
グラムがアクセス可能な記憶領域に書き出してしまうこと
アクセス不可
アクセス可能
(間接)アクセス
機密情報
xxxx……..
プログラム
管理者
secret
…………
readln(x);
writeln(x);
情報漏洩
公開情報
xxxx……..
zzzz……..
一般ユーザ
public
プログラムが引き起こす情報漏洩を検出するために、情報
漏洩解析手法が提案、実現されている
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
4
発表内容
研究の背景
情報漏洩解析とは
MAC方式によるアクセス制御法
情報フロー
情報漏洩解析の例
既存の情報漏洩解析手法の問題点
提案する情報漏洩解析手法
プログラム依存グラフの利用
一般的なセキュリティモデルへの対応
実現した情報漏洩解析システムについて
システムの説明
手法の有効性の検証
まとめと今後の課題
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
5
情報漏洩解析
プログラムを静的に解析することで得られるデータの
推移関係をもとに、入力値の機密度から出力値の
機密度を求める
プログラムが、どのような記憶領域に、どのような機密度の
データを出力するのか解析できる
プログラム実行において、重要な情報が漏洩する可能性
があるかどうか判定するために利用
各データの持つ機密度 : セキュリティクラス
変数間に存在するデータ授受関係 : 情報フロー
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
6
MAC方式によるアクセス制御法
セキュリティクラス(以後SC): データの機密度
セキュリティモデル：システムにおける各SCの強弱
各SCを元とする束を用いて表される
一意な最大元、最小元が存在
任意の2元の最小上界，最大下界が
定義されている
クリアランス：利用者に割り当てられた、
データへのアクセス権限
データの参照
データのSCが利用者のクリアランスより小さいか
等しければ、利用者はそのデータを参照可能
クリアランス3ならば全てのデータを参照可能
クリアランス1ならばSC0、1のデータを参照可能
最大元
3
1
2
0
最小元
セキュリティモデル
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
7
情報フローとは
プログラム中の変数間に存在するデータ授受関係
explicit flow :
変数の定義～参照間に存在
implicit flow :
分岐(繰り返し)命令の条件節と内部の文の間に存在
1:
2:
3:
4:
5:
b := 5;
c := 5;
if ( c > 0 ) then begin
a=b
end;
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
8
情報漏洩解析の例(1/2)
a (SC:1) のデータと b (SC:2) のデータが
c にフローする
3
1
2
0
セキュリティモデル
1: readln(a);
2: readln(b);
3: c = a + b;
explicit flow
3行目の代入後の c は a 、 b 両方の
データに関する情報を持つ
代入後の c のデータを参照できるのは、
a 、b 両方のデータを参照できるクリア
ランスを持つ利用者であるべき
代入後の c のSCは a と b のSCの最小
上界として求められる(この場合SC 3)
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
9
情報漏洩解析の例(2/2)
a (SC:0)のデータと b (SC:2)のデータ
がc にフローする
3
1
2
0
セキュリティモデル
1:
2:
3:
4:
5:
6:
readln(a);
readln(b);
if (b>0) then
begin
c=a
end;
explicit flow
implicit flow
5行目の代入後の c は a 、 b 両方の
データに関する情報を持つ
代入後の c のデータを参照できるのは、
a 、b 両方のデータを参照できるクリア
ランスを持つ利用者であるべき
代入後の c のSCは a と b のSCの最
小上界として求められる(この場合SC
2)
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
10
発表内容
研究の背景
情報漏洩解析とは
MAC方式によるアクセス制御法
情報フロー
情報漏洩解析の例
既存の情報漏洩解析手法の問題点
提案する情報漏洩解析手法
プログラム依存グラフの利用
一般的なセキュリティモデルへの対応
実現した情報漏洩解析システムについて
システムの説明
手法の有効性の検証
まとめと今後の課題
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
11
既存の情報漏洩解析手法の問題点
既存手法およびその実装¶
各文内・文間の情報フローに基づいた、データフロー方程式の繰
り返し計算による手法
問題点
1. 言語ごとに解析アルゴリズムを定義する必要があり、汎用性に欠
ける
2. 入力値のSCの変更のたびに再度繰り返し計算が必要で、効率
が悪い
3. 2値のSCをとるセキュリティモデルにのみ対応しており、
一般的なセキュリティモデルに対応していない
セキュリティモデル
¶横森励士, 大畑文明, 高田義朗, 関浩之, 井上克郎: "セキュリティ解析アルゴリズムの実現とオブジェクト指向言語への適用に関する一考察",
ソフトウェアサイエンス研究会
電子情報通信学会技術研究報告、SS2000-27～30, Vol.100, No.472, pp. 17-24, 2000.
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
12
発表内容
研究の背景
情報漏洩解析とは
MAC方式によるアクセス制御法
情報フロー
情報漏洩解析の例
既存の情報漏洩解析手法の問題点
提案する情報漏洩解析手法
プログラム依存グラフの利用
一般的なセキュリティモデルへの対応
実現した情報漏洩解析システムについて
システムの説明
手法の有効性の検証
まとめと今後の課題
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
13
提案する情報漏洩解析手法
プログラム依存グラフ(PDG)を利用した情報漏洩解析
問題点1. 言語ごとに解析アルゴリズムを定義する必要があり
汎用性に欠ける
PDGの利用による汎用性の向上
問題点2. 入力値のSCの変更のたびに再度繰り返し計算が
必要で、効率が悪い
PDGの再利用性による効率の向上
問題点3. 一般的なセキュリティモデルに対応していない
束上の任意の2元の最小上界を二次元行列で記述することで
一般的なセキュリティモデルに対応
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
14
プログラム依存グラフ
（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
データ依存辺
制御依存辺
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
15
情報フローとPDG
情報フローとPDGが示す依存関係の等価性に着目
explicit flowとデータ依存辺、
implicit flowと制御依存辺を対応させる
情報フロー
explicit flow
implicit flow
PDG
データ依存辺
制御依存辺
PDGが示す依存関係から情報フローが求められる
PDGを利用した情報漏洩解析が可能
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
16
提案手法の言語独立性と再利用性
PDGはプログラム中のデータの推移関係を表す
異なる言語であってもPDGが構築できれば、
提案する情報漏洩解析手法が適用可能
構築したPDGはコード修正を行わない限り、再利用が可能
入力値のSCを変更しても、同一のPDGで
情報漏洩解析が可能
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
17
一般的なセキュリティモデルへの対応
束上の任意の2元の最小上界を二次元行列で記述
二次元行列を参照することで、最小上界が求められる
一般的なセキュリティモデルへの対応
5
3
4
1
2
0
セキュリティモデル
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
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
18
PDGを利用した情報漏洩解析の実現
PDG
起点
起点
PDGを構築
SCの初期化
セキュリティモデルの読み込み
各入力文に対応する頂点に
対しSCの初期値を与える
各入力文を起点としてPDG
を探索し、各頂点のSCを求
める
起点
入力文
すでに高いSCが与えられてい
る頂点への辺はたどらない
探索が合流する頂点ではSC
の最小上界をとる
その他の文
データ依存辺
制御依存辺
セキュリティモデル
結果を出力
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
19
発表内容
研究の背景
情報漏洩解析とは
MAC方式によるアクセス制御法
情報フロー
情報漏洩解析の例
既存の情報漏洩解析手法の問題点
提案する情報漏洩解析手法
プログラム依存グラフの利用
一般的なセキュリティモデルへの対応
実現した情報漏洩解析システムについて
システムの説明
手法の有効性の検証
まとめと今後の課題
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
20
実装(1/2)
既存のスライス抽出システムOsaka Slicing
Systemを拡張
情報漏洩解析
その他の文
前提条件の入力
1. セキュリティモデル
2. 入力文、戻り値で定義されるデータのSC
PDG
PDG
PDG
入力文
構文、意味解析
結果の出力
セキュリティモデル
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
21
実装(2/2)
情報漏洩解析の問題点
情報フローにのみ従い解析を行う
情報を隠蔽可能な暗号化通信路の存在や、情報の復
元や類推が不可能な状況は考慮されていない
現実的には問題がないデータのSCが過度に高くなってし
まう場合がある
関数の戻り値データに対するSC制約機能
重要な情報の復元・類推が不可能であると判断できる
戻り値データに対し、そのSCをユーザが指定できる
データのSCを現実的な値に補正可能
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
22
評価1: 解析効率の向上
解析対象:
約2500行のプログラム
評価方法
既存のシステム、作成したシステム
それぞれで、入力文のSCを同条件
で設定し、繰り返し解析する
既存のシステムと作成したシステム
の実行時間の累計を比較
PDGの再利用性による、効率の
向上
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
23
評価2:複雑なセキュリティモデルを持つ
システムへの適用(1/5)
事例: 学生の成績管理システム(約400行)
ユーザおよびそのクリアランス
学生：4 教養事務 : 3 専門事務 : 5
6
4
3
1
5
2
0
セキュリティモデル
主なデータ
教養科目の成績
専門科目の成績
教養科目の事務の認証番号
学生の認証番号
専門科目の事務の認証番号
各データの
SC
1
2
3
4
5
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
24
評価2:複雑なセキュリティモデルを持つ
システムへの適用(2/5)
学生の成績管理システムの構造
main関数
認証番号
認証関数
入力
・入力によりユーザを識別
・ユーザのクリアランスを
・戻り値として得られたクリアランスを持つユーザが
戻り値として返す
可能な処理を行う関数を呼び出す
return
認証関数の戻り値を条件式として分岐
クリアランス３
クリアランス4
クリアランス5
教養事務の処理関数
学生の処理関数
専門事務の処理関数
・全学生の教養科目の
成績の更新
・自身の両科目の
成績の参照
・全学生の専門科目の
成績の更新
各ユーザのクリアランス
学生：4
教養事務 : 3
専門事務 : 5
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
25
評価2:複雑なセキュリティモデルを持つ
システムへの適用(3/5)
SCが高い出力文が非常に多い
認証番号は隠蔽を行っているの
で、この結果は不自然
戻り値のSCが過度に高くなってい
る?
認証関数の戻り値から認証番号
の類推は不可能
3
0
1
戻り値のSCをlowとして設定
6
26
4
1
5
2
0
0
1
0
5
各SCの右下の数字:
結果そのSCとなった出力文の数
セキュリティモデル
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
26
評価2:複雑なセキュリティモデルを持つ
システムへの適用(4/5)
学生の成績管理システムの構造
main関数
認証番号
認証関数
入力
・入力によりユーザを識別
・ユーザのクリアランスを
・戻り値として得られたクリアランスを持つユーザが
戻り値として返す
可能な処理を行う関数を呼び出す
return
認証関数の戻り値を条件式として分岐
過度に高いSC
クリアランス３
クリアランス4
クリアランス5
教養事務の処理関数
学生の処理関数
専門事務の処理関数
・全学生の教養科目の
成績の更新
・自身の両科目の
成績の参照
・全学生の専門科目の
成績の更新
各ユーザのクリアランス
学生：4
教養事務 : 3
専門事務 : 5
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
27
評価2:複雑なセキュリティモデルを持つ
システムへの適用(5/5)
戻り値のSCをlowとして設定するこ
とでSCの高い出力文が削減された
現実的には情報漏洩の危険性は
微々たるもの
一般的なセキュリティモデルを持つ
システムへの提案手法の適用
SC制約機能の有効性を確認
現実的な情報漏洩の可能性を判断
できた
隠蔽すべきデータを判断する指標に
することも可能
6
3
4
0
1
0
5
1
2
2
0
1
2
27
各SCの右下の数字:
結果そのSCとなった出力文の数
セキュリティモデル
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
28
まとめ
PDGを利用した、一般的なセキュリティモデルを対象
とする情報漏洩解析手法を提案、実現した
情報漏洩解析の効率化と、汎用性の向上
一般的なセキュリティモデルを持つシステムへの対応
実装による手法の有効性を確認
繰り返し解析における解析効率の向上
複雑なセキュリティモデルを持つシステムへの対応
SC制約機能による現実的な利用度の向上
今後の課題
他のプログラム言語に対する提案手法の適用
ソフトウェアサイエンス研究会
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Technology and Science, Osaka University
29

Download Report