暗号化XML文書の安全な検索方法に関する研究

暗号化XML文書の安全な検索
方法に関する研究
信州大学大学院
工学系研究科情報工学専攻
07TA561J
中村伸一
1
目次
•
•
•
•
•
•
•
•
•
背景・提案
周辺技術
先行研究
暗号化XML文書検索システムの概要
提案手法
実験・結果
考察
今後の課題
まとめ
2
背景
• インターネットを経由してデータベースを提供
するサービス(Amazon Simple DB等)が始まって
いる。
専用施設
（iDC）
インターネット
利用者
データベース
サーバ
SELECT name, address FROM ...
Yamada Taro, Japan...
データベース
データベース
3
管理者
背景
• セキュリティに関する問題の一つに、保存され
たデータベースを構成するファイルの持ち出し
による情報漏えいがある。
専用施設
（iDC）
インターネット
利用者
データベース
サーバ
SELECT name, address FROM ...
ファイル
持ち出し
Yamada Taro, Japan...
データベース
データベース
管理者
4
背景
• ファイルを暗号化しても、メモリ上でファイル
を復号しているため、管理者の権限や、不正プ
ログラムでメモリの内容の持ち出しは可能。
専用施設
（iDC）
不正プログラム
による盗聴
インターネット
利用者
SELECT name, address FROM ...
データベース
管理者特権
サーバ
による持ち出し
Yamada Taro, Japan...
データベース
（暗号化）
データベース
管理者
5
提案
• データを暗号化したままで安全に検索する手法
を提案する
– 提案する手法で取り扱うデータはExtensible Markup
Language（以下 XML）
• T をターゲットXML 文書、Q をクエリXML文書
と呼ぶ２つの XML文書T、Q に対し、Tを保存
する側でT、QのXML構造を知られないまま、T
に出現するQ をすべて検索する。
6
周辺技術(Extensible Markup Language)
• Extensible Markup Language(XML) は、テキストをタグと
呼ばれる文字列（開始タグ（<要素名>）と終了タグ（</
要素名>））で挟むことで、属性（段落や文字の種類
等）を付ける表現形式
<?xml version="1.0" encoding="utf-8"?>
<site>
<open_auctions>
<open_auction>
<bidder>
<date>10/22/1999</date>
<time>15:48:27</time>
<personref person="person3"/>
<increase>16.50</increase>
</bidder>
</open_auction>
</open_auctions>
</site>
7
周辺技術(XPath)
• XPathとはXML文書の特定の部分を指定するための言語
• XPathは“/”で表現される直下の要素、“//”で表現される
先祖子孫の要素、“*”で表現される全ての要素等を指
定することが出来る。
<?xml version="1.0" encoding="utf-8"?>
<site>
<open_auctions>
<open_auction>
<bidder>
<date>10/22/1999</date>
<time>15:48:27</time>
<personref person="person3"/>
<increase>16.50</increase>
</bidder>
</open_auction>
</open_auctions>
</site>
XPath
/site
/site/open_auctions
/site/open_auctions/bidder/*
//bidder
意味
ルートsiteを選択する。
site以下の全てのopen_auctionsを選択する。
bidder以下の全ての要素を選択する。
全てのbidder要素を選択する。
8
先行研究
• 暗号化XML文書の検索に関して以下の先行研究がある
• Dawn Xiaodong Songらの手法
暗号化文字列の検索
• R. Brinkman らの手法
Dawn Xiaodong Songらの手法をもとにXML文書検索に拡
張
• Hui (Wendy) Wangらの手法
XML文書中の要素名を暗号化したものと出現位置、出現
位置と暗号化した要素の情報から検索
9
先行研究(Dawn Xiaodong Songらの手法)
• 暗号化の前に平文を暗号化（暗号文字列１）
• 暗号文字列１とランダム列とランダム列のハッシュでXOR
する（暗号文字列２）
• 暗号文字列１とハッシュを用意し、暗号文字列１と暗号文
字列２をXORして、ハッシュが同じであれば同じ文字列
暗号化
検索
文字列
暗号文字列２
暗号化
XOR
暗号文字列１
暗号文字列１
A,Bに分割
暗号文字列A
暗号
文字列B
ランダム列
ランダム列
のハッシュ
XOR
ランダム列
ランダム列
のハッシュ
暗号文字列２
この値が同じか比較する
10
先行研究(R. Brinkmanらの手法)
• Dawn Xiaodong Songらの手法で暗号化したXML文書中の
要素名と出現位置をRDBに登録
• XPathの各要素の位置関係が同じ要素をRDBから検索し、
要素名がXPathと同じかDawn Xiaodong Songらの手法で
確認する
クライアント
検索XPath
XPathの要素名
を変換
（暗号化）
変換した要素名とXPathの
関係を満たす要素を検索
RDB
要素名が同じ
でXPathの関係
を満たす要素
を検索
要素を返す
結果の要素名が
XPathの要素名と
合致するか確認
暗号化した要素名と
出現する位置を保存
出現位置は深さ優先 11
探索順で表現
先行研究(Hui (Wendy) Wangらの手法)
• RDBに暗号化した要素名と出現位置（0-1の実数で包含
関係を利用して出現位置を表現する）、出現位置と要素
の情報を登録
• XPathの暗号化した要素名と位置を検索しクライアント
側で復号して確認
クライアント
検索XPath
XPathの要素名
を変換
（暗号化）
変換した要素名とXPathの
関係を満たす要素を検索
要素を返す
要素名と位置関
係がXPathと同
じか確認
RDB
要素名が同じ
でXPathの関係
を満たす要素
を検索
要素を
復号する
暗号化した要素名と出現する
12
位置を保存。出現位置は0-1の
実数で包含関係で表現
先行研究（提案する手法の改善点）
• サーバ側にターゲット・クエリXML文書の構造
を知られる事なく検索を行うことを可能とした
– クエリXML文書の要素と同じ位置関係となっている
ターゲットXML文書の部分をクライアント側で特定
するため
• クエリXML文書の一部の情報からターゲット
XML検索すべき部分を絞り込むことで検索の効
率化を行った
– 一般的なXML文書の検索はXML文書が比較的簡単な
構造であることに注目した
13
暗号化XML文書検索システムの概要
• ターゲットXML文書を保存するためのRDBとク
ライアントで構成
• RDBにインデックステーブルとデータテーブル
を設置
XML文書
データ登録
XML送信
結果送信
利用者
検索
クライアント
インデックス
テーブル
SQL送信
ネットワーク
データ送信
RDBサーバ
データ 14
テーブル
提案手法(XML文書の系列化)
• ターゲットXML文書、クエリXML文書を深さ優
先探索順（以下プリオーダ）で系列化する
myDocument
1
Data
2
myDocument
1
Data
5
first
Name
6
first
Name
3
Data
2
second
Name
4
first
Name
6
second
Name
7
Data
5
first
Name
3
second
Name
4
second
Name
7
15
提案手法(データの定義)
• ターゲットXML文書、クエリXML文書の定義
TITEM i Ed (TITEM ) Lv(TITEM ) Path(TITEM ) Len(TITEM )
i
i
Br(Q) Lf k ( Br (Q))
i
i
ターゲットXML文書
TITEM
TITEM
クエリXML文書
QITEM
1
1
2
QITEM 2
TITEM N 1
Br Q 
1
Lv(TITEM )
TITEM N
2
QITEM N
1
Ed TITEM
2
Lf1 Br Q 

2
Lf N Br Q 
3
Path (TITEM )  (TITEM , TITEM
N1
N1
N11
, TITEM )
1
16
提案手法(テーブル定義)
• インデックステーブル
要素名、出現位置、木の範囲、文字列長
ITbll1  H (TNAMEl1 ), E(H (K ), il2 , Ed(TITEMl 2 ), Len(TITEM l2 ) l2 ) 
(l1  1,...,M1 ),(l2  1,...,M 2 )
• データテーブル
出現位置、要素名、木の範囲、深さ、根までのパス
DTbli  i, E(H (K , i),TITEM i ), E(H (K , i), Ed(TITEM i )),
E(H (K , i), Lv(TITEMi ), E(H (K , i), Path(TITEMi ))  (i  1,...,M3 )
17
提案手法(テーブル定義)
• インデックステーブル、データテーブルの例
• 木の範囲は最も深く、右の要素
ターゲットXML文書
(要素名,位置,範囲,深さ)
a,1,9,1
b,2,7,2
c,3,4,3
b,8,9,1
c,5,7,2
c,9,9,2
インデックステーブル（暗号化していない）
"|"はデータの区切り文字
要素名: 出現位置|木の範囲|文字列長
a: 1|9|1
b: 2|7|1,8|9|1
c: 3|4|1,5|7|1,9|9|1
d: 4|4|1,6|6|1,7|7|1
データテーブル（暗号化していない）
d,4,4,4
d,6,6,4
d,7,7,4
出現位置: 要素名|木の範囲|深さ|根までのパス
1: a|9|1|1
2: b|7|2|2,1
3: c|4|3|3,2,1
..
18
提案手法
クライアント
クエリXML
文書
①分岐点、分岐点
からの葉を抽出
②分岐点、分岐点からの葉
の出現位置を検索
③分岐点、葉の出現位置を
取得
④葉の要素が全
部含む分岐点を
抽出
RDB
インデックス
テーブル
⑤抽出した分岐点からの葉の
情報を検索
⑥葉の情報を取得
⑦葉から根までの
経路の要素を取得
経路の要素を重ね
合わせ
⑩クエリXML文
書が含まれるか
判定する
⑧重ね合わせた経路の要素の
情報を検索
データ
テーブル
⑨要素の情報を取得
19
提案手法
• ターゲットXML文書中のクエリXML文書中の分
岐点と分岐点以下の葉の要素名が同じ要素を探
す
ターゲットXML文書
クエリXML文書
a
a
b
d
g
f
e
h
b
c
i
c
クエリXML文書の
分岐点の要素名
が同じものを探す
クエリXML文書の分岐点
以下の葉の要素名が全て
含まれるか調べる
h
i
20
提案手法
• 葉の要素の根までのパスを重ね合わせ、クエリ
XML文書が含まれるか調べる
ターゲットXML文書
a
a
b
d
g
c
f
e
h
b
i
葉の要素の根までの
要素を得る
a
a
b
b
c
c
c
h
i
重ね合わせ
h
i
クエリXML文書
21
が含まれるか調べる
提案手法(④分岐点抽出)
• Stack-Joinと呼ばれる手法を利用
• XML文書（各要素の左はプリオーダ、右は要素の範囲（最も深
く、右の要素））を、中央の対象リストに変換する
• 子孫対象リストの①から④を走査する間、先祖対象に子孫対象が
含まれる場合、その先祖対象をスタックに積む
• スタックにある間、含まれる子孫対象を追加する
1,7
2,6
3,3
7,7
先祖対象
リスト
(1,7),(2,6),(4,6)
4,6
5,5
6,6
子孫対象
リスト
(4,6)
(5,5),(6,6)
(2,6)
(3,3),(5,5),(6,6)
(1,7)
(7,7),(3,3),(5,5),(6,6)
(3,3),(5,5),(6,6),(7,7)
①
②
③
④
スタック
先祖対象に属する子孫対象
22
提案手法(⑦重ね合わせ)
• 重ね合わせるパスで同じ要素がある場合は１つ
にまとめ、重ねた要素をプリオーダの順で並び
替える手順を行っている。
myDocument
1,8
Data
2,7
first
Name
3,6
Data
5,4
second
Name
4,5
first
Name
6,3
second
Name
7,2
first
Name
3,6
myDocument
1,8
Data
2,7
重ね合わせ
重ね合わせ
myDocument
1,8
Data
2,7
second
Name
4,5
myDocument
1,8
Data
2,7
first
Name
3,6
second
Name
4,5 23
提案手法(⑩判定)
• 取得したデータとクエリXML文書の要素につい
て、要素名と根からの深さをペアにしてプリ
オーダ順で系列化を行う
a
b
c
d
a
j
f
e g
h
i
取得したデータ
k
(a,0),(b,1),(c,2),(d,2),(e,2),
(f,1),(g,2),(h,2),(i,2),(j,1),
(k,2)
j
f
g
(a,0),(f,1),(g,2),(i,2),(j,1)
i
クエリXML文書
24
提案手法(⑩判定)
• クエリXML文書の最初の要素（根）を取得した
データの先頭から検索する
クエリXML文書：(a,0),(f,1),(g,2),(i,2),(j,1)
合致
取得したデータ：(a,0),(b,1),(c,2),(d,2),(e,2),(f,1),(g,2),(h,2),(i,2),(j,1),(k,2)
25
提案手法(⑩判定)
• クエリXML文書の次の要素を検索する。ただし、
取得したデータの次の要素と同じレベルの要素
しか検索しない
クエリXML文書：(a,0),(f,1),(g,2),(i,2),(j,1)
スキップ
合致
取得したデータ：(a,0),(b,1),(c,2),(d,2),(e,2),(f,1),(g,2),(h,2),(i,2),(j,1),(k,2)
26
提案手法(⑩判定)
• fの次に深さが大きい要素がある場合(fが子を持つ場合)、fの
位置をスタックに積み、fの次(子)に対して要素を検索する
• クエリXML文書の要素の深さより小さい要素が出現したら
終了し、スタックに記憶した位置 (f) の要素と同じ深さの次
の要素 (j) から検索を続ける
次の要素
クエリXML文書：(a,0),(f,1),(g,2),(i,2),(j,1)
合致
合致
取得したデータ：(a,0),(b,1),(c,2),(d,2),(e,2),(f,1),(g,2),(h,2),(i,2),(j,1),(k,2)
27
提案手法(⑩判定)
• 全てのクエリXML文書の要素が合致したため、
取得したデータにクエリXML文書が含まれるこ
とがわかる
クエリXML文書：(a,0),(f,1),(g,2),(i,2),(j,1)
合致
取得したデータ：(a,0),(b,1),(c,2),(d,2),(e,2),(f,1),(g,2),(h,2),(i,2),(j,1),(k,2)
28
提案手法(検索クライアント)
• 標準入力でクエリXML文書を入力し、標準出力でター
ゲットXML文書中に出現するクエリXML文書の根の位
置を返す
• 検索速度の高速化のため、復号したデータのキャッシュ、
文字列長の比較を組み込んでいる
検索クライアント
Stream
クエリXML文書
HashQueryNode
GetQueryLoc
MakeNodeList
MakeBindList
GetNodeData
Matching
出現位置
29
実験・結果
• サーバPC１台、クライアントPC１台を100Mbpsのネットワー
クで接続して実験を実施
種別
CPU
メモリ
HDD容量
使用OS
サーバ
Intel Xeon 3.2GHz×2
4GB
200GB
CentOS 4.1
クライアント
AMD Athron X2 5400×1
2GB
120GB
Windows XP SP3
• ターゲットXML文書は、1M、5M、10MbyteのXML文書を用
意。XML文書の要素数は、1MByteで24405個、5MByteで
121944個、10MByteで243435個
• RDBサーバはMySQL を使用、インデックステーブルのテー
ブル数を1MByteのXML文書の場合は10000、5MByteは50000、
10MByte場合は100000に設定
• データテーブルの位置について、RDBの機能であるイン
デックスを有効にした
30
実験・結果
•
•
•
•
クエリXML文書（XPathで表現）は以下のものを使用した
Q1-Q6は枝のないXML文書
Q7-Q10は枝のあるXML文書
Q11-Q12はターゲットXML文書の根からではない一部
クエリ
Q1
Q2
Q3
Q4
Q5
Q6
Q7
Q8
Q9
Q10
Q11
Q12
XPath
/site
/site/regions
/site/regions/asia
/site/regions/asia/item
/site/regions/europe/item/description
/site/regions/namerica/item/description
/site[regions][catgraph][open_auctions]
/site/people/person[name][emailaddress]
/site/open_auctions/open_auction/bidder[date][increase]
/site/closed_auctions/closed_auction/annotation[author][description]
//item
//description/text
31
実験・結果
•
•
•
•
Q1-Q3、Q7は、検索時間は１秒未満と短い
Q4-Q6は、分岐数に従って検索時間が長い
Q8-Q10は、分岐数、葉数に従って検索時間は長い
Q11-Q12は、分岐数に従って検索時間が長い
クエリ検索時間検索時間検索時間分岐数葉数
分岐数葉数
分岐数葉数
マッチ数マッチ数マッチ数
1MB
1MB
5MB
5MB
10MB 10MB 1MB
5MB
(ms）
(ms）
(ms）
10MB
1MB
5MB
10MB
Q1
119
81
119
1
1
1
1
1
1
1
1
1
Q2
143
82
120
1
1
1
1
1
1
1
1
1
Q3
127
93
120
1
1
1
1
1
1
1
1
1
Q4
1,394
2,057
4,253
183
1
923
1 1,848
1
17
85
170
Q5
3,596
10,036
22,712
374
1 1,888
1 3,782
1
51
255
510
Q6
3,606
10,117
22,498
374
1 1,888
1 3,782
1
85
425
850
Q7
171
235
398
1
3
1
3
1
3
1
1
1
Q8
2,581
7,380
15,602
216
623 1,084 3,131 2,168 6,268
216
1,083
2,167
Q9
7,604
29,240
73,186
527 1,841 2,628 9,222 5,190 18,219
527
2,628
5,190
Q10
1,574
8,138
17,573
183
557
923 2,811 1,848 5,630
81
413
828
32
Q11
419
2,004
4,173
183
1
923
1 1,848
1
183
923
1,848
Q12
5,980
37,267
107,901
908
1 4,479
1 9,051
1
257
1,332
2,652
実験・結果
• 実際にRDBにデータテーブルの情報を要求した
数と検索時間の関係は比例していた
120000
時間（ms）
100000
80000
1MB
60000
5MB
10MB
40000
20000
0
0
5,000
10,000
15,000
実要求数
20,000
25,000
30,000
33
実験・結果
• Q4、Q11はMakeBindList、Q5-Q6、Q8-Q10、Q12は
GetNodeData、MakeBindListが多くの処理時間を占めて
いる。
120000
時間（ ms）
90000
Matching
GetNodeData
MakeBindList
MakeNodeList
GetQueryLoc
HashQueryNode
Stream
60000
30000
0
Q1
Q2
Q3
Q4
Q5
Q6
Q7
クエリ
Q8
Q9
Q10
Q11
Q12
34
実験・結果
• Q1-Q3、Q7はGetQueryLocが多くの処理時間を占めてい
る。
1000
750
Matching
時間（ ms）
GetNodeData
MakeBindList
500
MakeNodeList
GetQueryLoc
HashQueryNode
Stream
250
0
Q1
Q2
Q3
クエリ
Q7
35
考察
• 枝がない場合の検索は、その要素がターゲットXML文書中に多
く存在するほど検索時間は長い
– クエリXML文書の根からもっとも深い要素名をターゲットXML文書
から検索して、根までのパスの要素を取得している
• 枝がある場合の検索は、葉の要素がターゲットXML文書中に多
く存在するほど検索時間は長い
– クエリXML文書から子が２つ以上に分岐している分岐点と分岐点を
根とする木の葉の要素を取得し、根までのパスの要素を取得してい
る
• 検索クライアント中の処理時間について、MakeBindList 、
GetNodeDataが多くの時間を占めている
– MakeBindListは、クエリXML文書の分岐点と葉の位置関係と同じ関
係を持つ部分の要素をRDBから取得・復号し、ターゲットXML文書
の根までのパスの要素を重ね合わせる処理
– GetNodeDataは、MakeBindList で重ね合わせた要素をRDBから取得
する処理
36
今後の課題
• 検索時間の高速化が課題
• 実験結果から検索時間の高速化はRDBへの要素の要求に関
する時間を短縮することが効果的
• 検索に必要な要素をできるだけ少ない数でインデックス
テーブルから得ることが出来れば、検索時間を高速化する
ことが出来る
• インデックステーブルのキーに要素名とXML文書の構造を
含めることで、同じ要素名でも別のインデックステーブル
に分散して位置の情報を配置し、１テーブルあたりの登録
数を少なくすることが考えられる
37
まとめ
• XML文書を暗号化したままで安全に検索する手法を提案
を行った
• XML Benchmark Projectで公開されているXML文書作成ソ
フトウエアで作成したXML文書で検索時間等の評価を
行った
• 今回提案した手法は、検索時間がRDBからの要素の取得
数に大きく依存していた
• RDBから取得する要素をできるだけ少なくなるように、
インデックステーブルのキーを改善することが今後の課
題である
38
ご清聴ありがとうございました
39

Download Report