スライド 1

プログラム依存グラフを利用した
情報漏洩解析手法の提案と実装
～一般的な束構造を持つセキュリティクラスを対象として～
大阪大学基礎工学部
情報科学科
井上研究室
西秀雄
情報漏洩解析
情報フローに基づき、入力値のセキュリティクラス
(以下SC)から出力値のSCを求める
プログラム実行において、重要な情報が漏洩する可能
性があるかを判定するために利用
SC: データの機密度
束を用いて構造を表現
SC
high(最大元)
3
1
2
0
low(最小元)
1
特別研究報告会
2015/10/1
情報フロー
プログラム中の変数間に存在するデータ授受関係
explicit flow: 定義～参照間に存在
implicit flow: 分岐(繰り返し)命令の
条件節とその内部の文の間に存在
SC
high
low
c := a + b;
1:
2:
3:
4:
5:
b = 5;
c = 5;
if ( c > 0 ) {
a = b;
}
aのデータとbのデータがcにフローする
cはa,b両方のデータに関する情報を持つ
cのSCはaとbのSCの最小上界
2
特別研究報告会
2015/10/1
既存手法の問題点
既存手法およびその実装¶
データフロー方程式の繰り返し計算に基づく
問題点
入力値のSCの変更のたびに繰り返し計算が必要で、
効率が悪い
言語ごとに解析アルゴリズムを定義する必要があり、
汎用性に欠ける
2値(high, low)のSCのみを実現しており、一般的な
束に対応していない
3
¶横森励士, 大畑文明, 高田義朗, 関浩之, 井上克郎: "セキュリティ解析アルゴリズムの実現とオブジェクト指向言語への適用に関する一考察",
2015/10/1
電子情報通信学会技術研究報告、SS2000-27～30,特別研究報告会
Vol.100, No.472, pp. 17-24, 2000.
提案する手法
プログラム依存グラフ(PDG)を利用した情報漏洩解析
PDGの持つ情報と情報漏洩解析で必要な情報の類似性に着目
PDGの再利用性による、効率の向上
PDGの言語独立性による、汎用性の向上
束上の任意の2元の最小上界を二次元行列で記述
一般的な束構造を持つSCへの対応
4
特別研究報告会
2015/10/1
プログラム依存グラフ
（Program Dependence Graph, PDG）
プログラムの各文を頂点とし、文間の依存関係を
有向辺で表現したグラフで、スライス計算などに利
用される
implicit flow
情報フロー explicit flow
PDG
PDG
データ依存関係制御依存関係
PDGが示す依存関係から情報フローが求められる
データ依存関係辺
制御依存関係辺
5
PDGを利用した情報漏洩解析が可能
特別研究報告会
2015/10/1
PDGを利用した情報漏洩解析の実現
PDG
PDGを構築
SCの初期化
起点
起点
起点
入力文
その他の文
束構造の読み込み
各入力文に対応する頂点に
対しSCの初期値を与える
各入力文を起点としてPDGを
探索し、各頂点のSCを求める
SC
すでに高いSCが与えられて
いる頂点への辺はたどらない
探索が合流する頂点ではSC
の最小上界をとる
high
データ依存関係
制御依存関係
6
low
結果を出力
特別研究報告会
2015/10/1
実装(1/2)
既存のスライス抽出システムOsaka Slicing
Systemのスライス抽出部を拡張
入力文
その他の文
PDG
構文、意味解析
前提条件の入力
1. SCの束構造
2. 入力文、戻り値で定義される値のSC
情報漏洩解析
PDG
PDG
SC
high
結果の出力
low
7
特別研究報告会
2015/10/1
実装(2/2)
情報漏洩解析の問題点
情報フローにのみ従い解析を行う
情報を隠蔽可能な暗号化通信路の存在や、(SCの高い)情報の
復元が不可能な状況は考慮されていない
過度に高いSCが設定されてしまう
SC制約機能
プログラム中に存在するデータに対し、そのSCをユーザが指定
できる
8
特別研究報告会
2015/10/1
評価(解析効率の向上)
約2500行のプログラムに
対し同条件でSCを設定し、
解析を繰り返し行い、実行
時間の累計を比較
提案手法の有効性を確認
PDGの持つ情報を繰り返し
利用できるため
9
特別研究報告会
2015/10/1
評価(システムの有効性) (1/2)
事例: 学生の成績管理システム(約400行)
認証番号
認証
教養事務
データ
SC
教養科目の成績
1
専門科目の成績
2
2
教養科目の事務の認証番
号
3
5
low
専門科目の事務の認証番
号
学生の認証番号
4
SC
学生
6
専門事務
3
high
5
4
1
両科目の成績の参照
0
教養科目の成績の更新
専門科目の成績の更新
10
特別研究報告会
2015/10/1
評価(システムの有効性) (2/2)
SCが高い出力文が多い
認証の結果を受けてモジュー
ルが実行されるため
認証を行う関数の戻り値から
認証番号の類推は不可能
そのSCをlowとして設定するこ
とでSCの高い出力文が削減
された
SC
SC制約機能の有効性を確認
3
0
1
6
0
26
4
1
2
20
0
11
特別研究報告会
5
1
2
0
27
5
2015/10/1
まとめ
PDGを利用した、一般的な束構造を持つSCに
基づく情報漏洩解析手法を提案、実現した
情報漏洩解析の効率化と、汎用性の向上
実装による手法の有効性を確認
今後の課題
情報フローの定義の拡張
他のプログラム言語に対する提案手法の適用
12
特別研究報告会
2015/10/1

Download Report