高信頼性・高安全性を有する
ネットワーク共生環境の構築技術の創出

1

菊野 亨

井上 克郎

大阪大学大学院情報科学研究科

大阪大学大学院情報科学研究科〒 565–0871 吹田市山田丘 1–5
kikuno@ist.osaka-u.ac.jp〒 565–8531 豊中市待兼山町 1–3
inoue@ist.osaka-u.ac.jp

藤原 融

増澤 利光

大阪大学大学院情報科学研究科

大阪大学大学院情報科学研究科〒 565–0871 吹田市山田丘 1–5
fujiwara@ist.osaka-u.ac.jp〒 565–8531 豊中市待兼山町 1–3
masuzawa@ist.osaka-u.ac.jp

はじめに

3. 情報システムにおけるデータの漏洩や攻撃などに対処し，高度なセキュリティを確保する

本テーマでは，ネットワーク共生環境を，安心・ことは，もはや普遍的といってよい課題であ

信頼のおける真に豊かな情報社会の基盤として実る．そこで，これらを実現する系統的な方法

現することを目的とし，その高信頼性・高安全性論としてのセキュリティ工学の確立を目指す．

を達成する技術について研究を行った．従来の研究分野による分類に基づけば，ソフトウェア工学，

さらに本テーマでは，生物共生ネットワークの分散システム工学，ディペンダビリティ工学，セ

生成過程の研究で得られた生物学上の知見の，高キュリティ工学を主軸とする研究である．これら

信頼・高安全な情報システムの基盤技術への適用の研究分野は，情報システムの高信頼化・高安全を模索した．

化に不可欠であり，本テーマは COE プログラムに

以下では，本研究プロジェクトの全期間を通じおける他テーマに対し，基盤となるべき要素技術て，各サブテーマごとに得られた主な研究成果にの提供を目的とする領域横断的なテーマとして位ついて説明する．

置づけることができる．
本テーマでは，主として，以下のサブテーマに取り組んできた．また，それぞれのサブテーマに2

高信頼・高安全ソフトウェアの留まらず，それらの総合分野において多様な研究を推進してきた．

1. 高信頼・高安全な情報システムを実現するた
めには，その基盤たるソフトウェアの安定性・設計・運用・管理
2.1

ソフトウェア分析に基づく高信頼・
高安全化手法信頼性が不可欠である．そこで，ソフトウェ

ソフトウェアの分析や信頼性の向上のための種々

アの効果的な設計・運用・管理を可能とするの技術を検討，評価を行なってきた．主として以

ソフトウェア工学の確立を目指す．

下のテーマに取り組んだ．

2. 情報システムは，通信技術を基盤とした分散システムの形態を取ることになる．そこで，分

• プログラム解析による信頼性，安全性の向上

散環境におけるプロセス協調の実現，あるい• ソフトウェアシステム類似度メトリクス

は，障害や分散環境の動的な変化への自律的• ソフトウェアシステムの自動分類

適応性を実現するために，分散システム工学，• ソフトウェア部品グラフのべき乗則の調査と部品検索への応用

ディペンダビリティ工学を基盤とする効果的な解法の提案を目指す．

図 1: マイコプラズマの遺伝子配列中の同型部分（阪大松田研究室提供）
図 2: 3 種類の Unix 系 OS の中のコードクローン
以下に，各テーマに関して得られた成果について説明する．
「プログラム解析による信頼性，安全性の向上の研究」では，主にコードクローン解析の研究を動などを行なった（詳細は，教育プログラム「ソフトウェア工学工房」を参照）．この活動を通じ，多くの利用者を獲得する事ができた．

行なった．コードクローンとは，プログラム中に「ソフトウェアシステム類似度メトリクスの研現れる同形の部分テキストの対で，プログラムの究」では，すでに開発されたソフトウェアシステム

一部をコピー・ペーストを行なってプログラムの同士の相異点を定量的に比較するためのメトリク作成を行なう場合に生じるものである [7]．一対のスとそれを計測するためのツール SMMT に関する片方のコードクローンにバグがあると，他方も修研究を行った．作成したツールを複数の類似した正が必要になる，など，プログラムの保守性を低

大規模ソフトウェアに適用することによって，ソ下させる大きな要因となっている．

フトウェアがどのように開発されてきたかを視覚本研究では，大規模なプログラム群に対して高的にわかりやすく表示させることが可能となった．

速に含まれるコードクローンを検出するツール「ソフトウェアシステムの自動分類の研究」でCCFinder を作成し，多くの対象に適用した [9]．

は，生物の種の分類作業と同様に，多種多様なソ

このコードクローン検出技術は，生物の遺伝子

フトウェアに対して，それぞれの持つ特徴を解析

配列より，同型部分を検出するアルゴリズム（サし，自動分類する手法について研究を行った．

フィックス木アルゴリズム）を用いており，その結

近年，インターネット上には膨大なソフトウェ

果の表現法も非常に似ている．図 1 はマイコプラ

ア開発プロジェクトが登録されているため，実際ズマ菌の遺伝子配列の中の同型部分をスキャッタプに希望するソフトウェアや類似ソフトウェアを検ロットで表現した物で，点の列が長いほど長い同索するためには，ソフトウェアがうまく分類，整型部分列を持っている事を示している（大阪大学

理されていなければならない．現存するリポジト

大学院情報科学研究科松田研究室提供）．

リサービスでは，プロジェクトを登録する人がそ

図 2 には，3 つの Unix 系 OS(FreeBSD, NetBSD,のプロジェクトの分類を行う．しかし，このようLinux) のカーネル部分の同型部分（コードクローン）を点で示している．この結果は対角線を中心

な手動分類では分類先となるカテゴリ集合を定義に対象なので，下部のみを表示している．

アがどのカテゴリに分類されるのか，分類を行う

我々は，コードクローン分析技術を普及させるためにソフトウェア工学工房においてセミナー活するのに労力がかかる．また，個々のソフトウェ
ソフトウェア登録者に依存するため分類の一貫性に問題がある．

このようにソフトウェアの分析や信頼性の研究に関し，生物界の種々の知見と通じる部分がある
cumulative frequency
100
10000

ことは興味深い．今後は，このような生物界の知見に基づき，ソフトウェアの特性やシステム開発の人間活動の性質を分析し，効率の良い開発作業に結び付く手法を探索する事が必要になろう．

2.2

ホームネットワークシステムにおける機器間でのサービス競合の検出

1

電力線通信等の技術の実用化に伴い，今後急速
1

100
10000
number of incoming links

図 3: ソフトウェア部品集合の部品グラフの入力次数の分布
このような問題を解消するために，自動的にソフトウェアの分類を行う MUDABlue システムの提案を行った．MUDABlue は潜在的意味解析手法(Latent Semantic Analysis: LSA) を用いて，カテゴリ集合の作成とソフトウェアの分類を自動的に行う．MUDABlue はソースコードのみに依存するため，管理者の入力は一切必要としない．LSA は単語間の意味的繋がりを統計的手法を用いることで抽出する．
「ソフトウェア部品グラフのべき乗則の調査と部品検索への応用の研究」においては，ソフトウェ
ア部品群が持つ利用関係が，生物界に良く見られるべき乗則に従うかどうかを調査した．ここでは，大規模なソフトウェア集合のソフトウェア部品グ
ラフ（Java の基礎的なライブラリである，JDK や，

JDK を用いて構築した複数のシステムの集合）に対して調査を行なった．さらに，ソフトウェア部
品検索への応用を考慮し，キーワード検索などにより取得した部品群からなる部分グラフの性質についても調査した．
その結果，図 3 のように，多数のソフトウェア

な普及が予想されるホームネットワークシステム
を対象に，システム中の機器が提供する複数のサービスが互いに干渉することで誤動作を招く可能性を検出し，異種サービスの共生を信頼高く実現す
る方法について研究を行った [13]．
具体的には，まず，ホームネットワーク上の機器の動作を正確に記述できるよう，簡易なモデル化
言語を定義した．この言語を利用することで，各機器の動作を表現したモデルを記述することが可能となる．一旦，形式的な各機器の動作記述が得られれば，計算機を用いてそれらを統合し，シス
テム全体の動作を表現するモデルを生成することができる．このモデルを解析することで，意図しない機器間の干渉や不具合の検出が可能となる．モデルの解析には，モデル検査と呼ばれる，状態探索に基づく自動検証手法を応用している．実験の結果，最新のモデル検査技術を用いることで，極めて短時間（数秒程度）で検証が可能なことが分かった．
この研究は，当初，ホームネットワークを設計する際に行う，静的な検証を念頭に進めてきたものであるが，上記の通り，検証時間が非常に短い
ため，機器がホームネットワークに追加されるのを検知したネットワーク自体が，自律的に検証手続きを起動し検証を行うといった動的な用途への応用も可能である．

を含む集合の入力次数の分布は，べき乗則に従う
ことがわかった [5]．また，キーワード検索によって得られた部分グラフに対しても，比較的少数の部品数で構成されるにもかかわらずべき乗則に従2.3

全ペアテストと生物学的状態探索の応用

うことがわかった．また，その際の係数 a は，ほソフトウェアに潜在する不具合を，テスト工程

ぼ 2 であり，多くの生物界のシステムで現れるべにおいて確実に検出する技術は，信頼性の高いソき乗則の係数とほぼ同じである．

フトウェアの実現において，欠かすことができな

を保持させるレプリケーション技術は，分散システ…

ムの高信頼化の主要な技術であるが，マルチキャス
トはレプリケーションの実現に不可欠な通信サー
ビスであり，その高性能化・高信頼化の重要性は

テスト 要素１
ケース
1

要素2

…

2

3

言を待たない．
1

2

エピデミック通信では，各ノードが隣接ノード
をランダムに選びメッセージを転送することで，マ

図 4: アントコロニーアルゴリズムによるテスト

ルチキャストを行う [3]．したがって，単一故障点

ケースの生成となるノードが存在せず，また，同じメッセージが冗長に転送されるため，ノードや通信の障害にい．全ペアテストは，そのような技術として，近年対し高い耐性が実現できる．これは，一旦流行が特に注目を集めているテスト手法である [1]．これ広まった疫病の伝染や噂の拡散の阻止が極めて難

は，ソフトウェアへの入力空間をすべてテストすしいという現象に対応している．

るのではなく，二つの次元（パラメータ）の値のペ

本研究では，エピデミック通信の信頼性を更にアすべてを，少なくとも一度テストするという手高めるため，幾つかの最適化手法を開発した．ま法であり，全数テストと比べ大幅にテストケース

ず，メッセージ伝搬状況が思わしくない場合，各数が減らせ，かつ，高い不具合検出能力を有すもノードが自律的にメッセージの再送を行うというのと認識されている．しかしながら，そのような適応的手法を導入した [25]．この判断の基準につテストを少ないテストケース数で完了するためにいても，隣接ノードの状況を観測することで，適は，テストケースを適切に選択することが必要で切に行う手法を考案した．様々なトポロジーのネッあり，これには計算機による支援が不可欠である．

トワークを対象にシミュレーション実験を行った

そこで，Java プログラムに対する標準的なテス

結果，殆どの場合で，これらの提案手法によって，トフレームワークである JUnit を用いて，全ペア

メッセージ受信に失敗するノード数を大幅に減少

テストを容易に実施することが可能なツールを開できることが分かった [17]．

発した．このツールでは，テストケースを生成する際，遺伝アルゴリズム，あるいは，アントコロ
ニーアルゴリズムという生物学的状態探索手法を用いることで，全ペアテストに必要なテストケー

3.2

生態系の単一個体群モデルに基づく
資源数制御

ス数の削減を行っている [20] （図 4）．今後は，広大規模なネットワーク環境で，メモリや通信帯く用いられている統合開発環境である Eclipse に，域などのネットワーク資源を有効に利用してタス開発したツールをプラグインとして組み入れるこクを効率的に実行するには，モバイルエージェンとを予定している．

トやファイル・レプリカの数を，ネットワークの規模に応じて適切に設定することが重要である．例
えば，モバイルエージェントを利用した分散シス

3

高信頼・高安全分散システム

3.1

エピデミック通信による高信頼マル
チキャスト

テムでは，ネットワーク中のエージェント数が多いほど処理に要する時間が減少するが，システム
資源（計算資源，通信帯域など）の消費は増加する．一方，ネットワーク環境は本質的にダイナミ

疫病の伝染過程を模倣することで，高信頼なマクスを有するものであり，このエージェントやファ

ルチキャストを実現するエピデミック通信についイル・レプリカ数制御には，ネットワーク規模の変て，更なる信頼性向上のための手法の開発を行っ化に対する適応性を有することが要求されている．

た．マルチキャストは，ネットワーク上の特定の生態系では，環境における単一種個体群の個体

ノード集合に対し，同一メッセージを配信する通数が，環境から供給される食物量に応じて安定す

信サービスである．複数のノードにデータの複製るという単一種個体群モデルが知られている [4]．

本研究では，この単一種個体群モデルを適用する# Initial Agents

ことによって，ネットワーク中のモバイルエージェ

500
0

γ=0.8

ントやファイル・レプリカの数を，ネットワークのノード数に対して一定の割合に保つ手法を提案

γ=0.5

した [21, 22]．また，提案手法が，ノード数に対してレプリカ数を所定の比に保つことを，ランダム

γ=0.2

ネットワークやスケールフリーネットワークなどのさまざまな種類のネットワークに対するシミュ
レーション実験によって確認した（図 5(a)）．さらに，ネットワークの規模が動的に変化する環境に(a) 静的ネットワーク

おいて，ネットワーク規模の変化に応じて，レプリカの数を適応的に制御できることをシミュレー# Nodes# Agents
Difference ratio

ション実験によって示した（図 5(b)）．

3.3

ノードの自律動作によるオーバーレ
イネットワークのトポロジーマッチ
ング

Peer-To-Peer (P2P) システムによって用いられるオーバーレイネットワークでは，下部の物理ネッ
トワークの構造と独立して自由なトポロジーを設(b) 動的ネットワーク

定することができる．このことは，P2P システムに高い柔軟性をもたらすと同時に，物理ネットワー

図 5: スケールフリーネットワークにおけるモバイ

クとオーバレイネットワークとのトポロジー間にルエージェント数制御

大きな不一致が生じた場合に，過度の通信負荷や，信頼性の低下といった問題を引き起こす原因となても確認することができた．

る [18]．
そこで本研究では，この不一致を解消し，効率的なオーバーレイネットワークを動的に構築するための手法を開発した [6]．提案手法では，各ノードは物理ネットワーク上の距離を反映した隣接ノー

3.4

高度な適応性を有する P2P 情報検索方式

ド間の通信コストを基準に，局所的なリンクの繋Peer-To-Peer (P2P) システムでは，ネットワー
ク中に分散しているファイル等の資源から，必要ぎ換えを繰り返し行う．このような各ノードの局とする資源をいかにして探索するかは重要な問題

所的な動作の結果，オーバーレイネットワークのの一つである．これまでフラッディングに基づくトポロジーを，物理ネットワークのそれに近づけ，手法や分散ハッシュ表に基づく手法など，さまざネットワーク全体の負荷を軽減することが可能とまな手法が研究されているが，それら手法にはスなる．同時に提案手法は，各ノードが保持するリン

ケーラビリティの欠如や，計算機の参加離脱といっク数も配慮し，ネットワーク全体のリンクの総数

た P2P ネットワークの動的変化に弱いなどいったは一定に保ちながら，各ノードが最終的にできる問題が存在する．これらの問題を解決する手法とだけ同程度のリンクを有すように動作する．この

してランダム性に基づいた手法がいくつか提案さため，得られるオーバーレイネットワークは，ノー

れており，たとえば文献 [14] などが知られている．

ド故障の際にネットワーク分割を起こす確率が極膨大な端末群で構成される P2P ネットワークでめて低くなる．負荷の軽減と高信頼化という提案の情報検索において，端末の参加離脱が激しい場法のこれらの利点は，シミュレーション実験によっ合においても正常に動作し，しかも時々刻々変化

する情報の検索頻度などに対し，パフォーマンス

そこで本研究では，自己安定分散システムの故の最適化を自動的に行う自己適応型の手法の確立

障や動的変化に対する高度な頑健性として，安全が本研究の目的である．

収束という新たな概念を提案した [8]．これは，故文献 [14] で提案されている方式は激しく端末の障や動的変化が生じたときに，迅速に安全な状況

参加離脱に頑強ではあるが，自己適応性を有してに復帰し，その後は安全性を保ちながら自己最適

いない事が知られている．そこで本研究では，参化を行うというものである．また文献 [8] では，ア

加離脱への頑強さを保ったまま，情報の検索頻度

ドホックネットワークのクラスタリングに重要なに応じた通信メッセージ量を自動的に最適化する役割を果たす支配集合の選出に，この概念を適用手法を提案し，シミュレーション実験によりそのすることに成功した．

有効性を示した [26]．

また，間欠的な故障や動的変化が頻繁に発生す

また，ランダムウォークに基づいた検索手法にる分散システムにおいて，故障や動的変化がシス

対しブルームフィルタ (bloom filter) を適応的にテムに与える影響を定量化することにより，自己使用する手法を提案し，検索効率の大幅な向上を

安定システムが正常な状況に復帰するのに要する行った [23]．提案手法では各端末が所有する情報

時間と故障や動的変化の頻度の関係を解明する手

オブジェクト（のハッシュ値）の集合をブルーム

法を提案した [10, 15]．さらに，永久故障として，フィルタにより圧縮表現し，それを周囲の端末に

ビザンチン故障が存在する分散システムにおける配布することで所有情報オブジェクトを通知する．

自己安定システムの実現法について考察し，永久ブルームフィルタはその性質上，オブジェクトのビザンチン故障に対する故障耐性を有する自己安有無の検索を誤る場合がある．ブルームフィルタ

定分散システムを設計した [11, 12, 19]．

の作成方法を，ブルームフィルタを配布する距離と情報検索頻度に関連づけて選択することにより，誤り確率を大幅に下げるとともに，通信量も大き4高信頼性・高安全性を実現する

く削減可能であることをシミュレーション実験に通信技術より示した．

ディジタルコンテンツ流通のための高信頼・高3.5

安全な通信システムの実現やそれに関連する基礎

自己安定分散システム

自己安定分散システム [2] は，計算機の一時的な故障や動的変化のためにネットワークがどのような状況に陥っても，十分に長い間新たな故障や動的変化が発生しなければ，自動的に正常動作に復帰することを保証する．つまり，自己安定分散シ
ステムは，一時的な故障や動的変化に対する高度研究として，様々なコンテンツ配信サービスのためのプロトコルやその要素技術，インデックス付
きで管理されているデータのアクセス方式，推論による情報漏えいへの対策，誤り訂正符号に関する研究を行ってきた．
以下では，これらのうちで代表的な成果について報告する．

な適応性を有する．
しかし，自己安定分散システムが正常な状況に復帰するためには，十分に長い間新たな故障や動的変化が発生せず，すべての計算機が正しく動作

4.1

ポリシーの自己更新が可能なアクセス制御システムすることが必要である．しかし，大規模分散シス

本研究において，アクセス制御の対象となるコ

テムにおいては，故障や動的変化が頻繁に発生すンテンツは，XML コンテンツ（コンテンツ本体とる状況は避け難く，十分に長い間，すべての計算機

その作者等の属性情報を含む XML 文書）である．

が正しく動作するという仮定は受け容れ難い．そコンテンツの配信環境としては，XML コンテンツ

こで，間欠的に生じる故障や動的変化，あるいは，に対するアクセス制御ポリシーを保有するブラウ

永久的な故障にかかわらず，正常な状況に復帰できザが存在し，各ユーザが自由に XML コンテンツ

る自己安定システムを実現することが重要である．

を作成・配信できる P2P 型ネットワークを想定す

ユーザ

ストレージ

アクセス制御アクセス制御
システム
システム
コンテンツ
ポリシー更新情報
つき
ポリシー
コンテンツ

攻撃者

TS(D)

アプリケーション・
アプリケーション・ミドルウェアミドルウェアTS(D)TS 機密情報を求める

ブラウザ

問合せ

エディタ

自己更新
ポリシー更新情報

機密情報の候補

機密情報

DのスキーマD

元のデータベース

ネットワーク

推論

G

T1 ,

KT
,

n

実行が許可されている問合せ

T1 (D)T1 ,

Tn (D )K T の実行結果,n

図 6: ポリシーの自己更新が可能なアクセス制御シ
図 7: 対象とする推論攻撃の概要

ステムる．ただし，違法コンテンツの氾濫などの無秩序評価した．また，実現したそれぞれのシステムが，状態を避けるため，ネットワークの監視機関が存

この XML コンテンツを読み込むことにより，ポ在し，各ユーザに対してアクセス制御ポリシーをリシーの自己更新を行い，更新後のアクセス制御

配布するものとする．このような配信環境においポリシーが意図した通りのアクセス判定を行うこて，将来起こり得るあらゆる状況を想定し，アクとを確認した．これらの成果の一部は，Bio-ADIT

セス制御ポリシーをあらかじめ記述しておくこと

2006 のポスターセッションで発表した．

は現実的ではない．
そこで本研究では，監視機関によりポリシーの更新情報が XML コンテンツに埋め込まれ，そのXML コンテンツをブラウザに読み込むときにポリ

4.2

XML データベースへの推論攻撃に対する安全性の定式化と検証シーが更新されるシステムを提案した．ただし，更機密情報が格納されているデータベースシステ

新情報と既存のポリシーの安全性は確保されていムにおいて，セキュリティ面での管理が必ずしも正るものとする．これにより，各ユーザが保有する確に行われていないことが問題となっている．特アクセス制御ポリシーの管理を自動化することがに，機密情報への直接のアクセスを禁止していてでき，ポリシー管理の煩雑さを解消することがでも，アクセスを許可されている情報や実行を許可

きる．次に，提案システムの実現を行った．XML

された問合せの結果，ドメイン知識などを基に，本文書に対するポリシー記述言語として OASIS で標来権限の無いユーザがその機密情報を推論できて準化された XACML を採用し，標準的な XACML

しまう場合がある．そのような推論を行うことをプロセッサのひとつを搭載した PC 上に提案シス

推論攻撃と呼ぶ．推論攻撃によりどのような情報テムを実現した．また，アクセスを読み出しだけが得られるかは，一般に自明ではない．したがっに制限した提案システムを，XSLT プロセッサのて，高安全性をもつデータベースシステムを構築・みを搭載した PC 上に実現した．自己更新処理に運用するために，データベース管理者は，機密情あたっては，更新情報に含まれる更新ポリシーと，報に対して推論攻撃が成功する可能性をあらかじ

既存の XACML ポリシーをどのように結合すべきめ把握できることが重要である．

かを検討した．

本研究では，推論攻撃に対する安全性の 1 つの上述の配信環境において，監視機関が違法 XML定式化として，「推論攻撃により機密情報の値の候

コンテンツを発見し，そのコンテンツへのアクセ

補が 1 つに絞り込まれる可能性 (特定可能性) がな

ス否認ポリシーを埋め込んだ XML コンテンツをいこと」を採用した．そして，ある前提条件のもネットワーク上へと流している状況を考える．ことで，特定可能性を検証する決定性多項式時間アのような状況において，ポリシー更新情報がネット

ルゴリズムを提案した．このアルゴリズムは，まワーク上に広まる速度をシミュレーションによりず，問い合わせとその結果から，逆型推論を用い

てもとのデータベースの候補集合を求める．さら

そこで，これらの安全性に関する要求を全て満に，型推論を用いて機密情報の値の候補集合を求たし，データ検索時及びデータベース更新時の通信

める．最後に，その候補集合が 1 要素からなるか

量が共にデータベースのサイズに比例しないデーどうかを判定する．この成果を論文 [24] としてまタ検索方式を提案した [16]．提案方式では，暗号技とめた．

術として Merkle 木と呼ばれるハッシュ木，コミッ

本研究ではさらに，特定可能性による定式化でトメント方式，紛失通信を利用している．Merkleは区別できない以下のような実用上両極端な状況木を利用することで，データベース更新時の通信を区別できるよう，新たな定式化を行った．

量を O(1) とすることができた．また，データ検• 機密情報の値の候補が数個にしかならず，特定されないまでも推論攻撃の効果が非常に高い．

索時の通信量である問い合わせと返答の大きさは，
データベースのサイズ N に対して O((log N )2 ) である．このように，提案方式はデータベースの更• 機密情報の値の候補の個数が非常に多く，攻新が頻繁に起こる場合に特に効率が良い．利用す撃の効果がない，あるいは非常に低い．

る暗号技術が安全であるという仮定のもとで，提また，より実用的な検証アルゴリズム開発を目指して，対象とする問合せクラスの拡張を行ってい案方式が安全性に関する要求を全て満たすことを証明した．この成果を論文 [16] としてまとめた．

る．今年度内にこれらの成果についての学会発表を行う予定である．

4.3

誤り訂正符号の厳密な性能評価

誤り訂正符号の正確な性能評価を行うことは，高秘匿性と一貫性を保証する通信効率の良いデータアクセス方式

インデックス付きでデータが管理されているデー
タベースを考える．データベースサーバに対して，得たいデータのインデックスを送り，それに対する返答から所望のデータを計算する状況を考える．
安全性に関する要求として，検索インデックスの秘匿，データベースの秘匿，結果の一貫性検証の三つがある．検索インデックスの秘匿とは，アクセスしようとするデータのインデックスをサーバから秘匿できることである．データベースの秘匿とは，サーバがもつデータベースに関して返答から分かることが所望のデータだけであることである．結果の一貫性検証とは，得られた結果がインデックスに対応したものであることを検索者が検証できることである．すなわち，データベースが更新されない限り，同じ問い合わせ（インデックス）について同じデータが得られ，そのことを検証できることを意味する．
これまでに，これらの安全性に関する要求を全て満たすデータアクセス方式が提案されている．しかし，従来方式ではデータ検索時の通信効率は非常に良いが，データベース更新時の通信量がデー
タベースのサイズに比例してしまい，通信効率が
悪い．

4.4

信頼なシステムを構成する技術として重要な課題である．そのため，記号位置置換やトレリス構造を活用して，局所重み分布の計算法の計算量削減を行った．局所重み分布とは，零語に隣接する符号語に関する重み分布である．記号位置置換不変性を用いて，局所重み分布を計算する方法や局所
重み分布の計算に有用な性質等を導出した．これ
らの成果は，論文としてまとめ，IEEE の論文誌に掲載された [27]．
さらに，トレリス構造，及びバイナリーシフトと呼ばれるアフィン変換の部分クラスを用いること
により局所重み分布の計算法の改良を図った．これにより，符号長 256，3 次のリード・マラー符号について計算時間を，従来法（我々が提案している方法）の 1/256 に削減することに成功し，その局所重み分布を求めた．この成果を論文 [28] としてまとめた．
また，局所重み分布を用いることにより，復号誤り率の下界，上界の改善を行った．復号誤り率について，単純な和集合下界，和集合上界においては，重み分布を局所重み分布に置き換えることによって，より精度の高い結果が得られることが知られている．しかし，単純な和集合下界，和集合上界は，もともとあまりよい下界・上界ではない．
そこで，同じ考え方に基づくが，より精度の高い

下界，上界が最近提案されている．例えば，加法的ウェアプロダクトラインの考えを導入し，よ

白色ガウス雑音 (AWGN) 通信路における復号誤りり効率なソフトウェア群の開発を行なう技術

率の Seguin 下界，Poltyrev 上界等である． これ開発が必須となる．

らの下界，上界に対しても局所重み分布を用いる

2. 稠密な分散環境におけるプロセス協調の実現，ことが可能であることを示し，実際に局所重み分

あるいは，障害や分散環境の動的な変化への布を用いた下界や上界の評価をいくつかの線形ブ

自律的適応性を実現することは，アンビエン

ロック符号を対象に行った．その結果，BCH 符号，

ト情報社会を実現するためには必須のものでリード・マラー符号，ゴーレイ符号等で復号誤り率

ある．アンビエント情報社会では，多数の端の下界，上界が改善されることを確認した．例え

末やネットワーク機器が有機的に連携して動ば，AWGN 通信路の SN 比が 0dB のとき，(31, 26)

作するが，高信頼・高安全な情報システムをハミング符号の復号誤り率の上界は 3.4 × 10−1 であり，下界は 9.4 × 10−4 から 1.1 × 10−2 へ改善された．

構築するための連携動作について，その基盤技術を構築することが重要な課題である．

3. 情報システムにおけるデータの漏洩や攻撃などに対処し，高度なセキュリティを確保する

5

おわりに

ことアンビエント情報社会を実現するためには必須のものである．これまでの安全性（セ本研究テーマでは，ネットワーク共生環境を，安キュリティ）に関する研究では，匿名性など，

心・信頼のおける真に豊かな情報社会の基盤とし個人情報をなるべく出さずにサービスを実現て実現することを目的とし，その高信頼化・高安することが重要な目標の一つであったが，ア全化のための技術について研究を行った．本研究

ンビエントネットワーク社会では必然的に個

プロジェクトの全期間を通じて，各サブテーマに人に関する情報を出さざるを得ず，それをい関してさまざまな基幹技術の開発を進めることがかに守るかが重要な課題となる．

でき，高信頼性・高安全性を有するネットワーク
共生環境の構築技術の創出に貢献できたものと考えている．
本研究テーマの今後の展望として，ポストユビ
キタス時代のアンビエント情報社会の実現に向けて，高信頼性・高安全性を有する情報システム構
築のための研究に取り組むことが重要である．本
研究の各サブテーマでは，具体的には，以下の展望が考えられる．

1. ソフトウェアの分析や信頼性の研究を推進する事は，アンビエント情報社会を実現するためには必須のものである．アンビエント情報
社会では，多数の端末やネットワーク機器が有機的に連携し，その機能を発揮するが，個々の機器のソフトウェアの信頼性を確保する事は重要なテーマである．個々のソフトウェア
システムが，予定通りであるかどうか，静的，
動的に検証する必要がある．また，アンビエ
ント情報社会を実現するためには，非常に多種の機器のソフトウェア開発が必須であるが，個別にソフトウェア開発を行なう事は，手間の増大を招き，経済的に困難である．ソフト

参考文献[1] Copeland, L., “A Practitioner’s Guide to Software Test Design,” Artech House (Dec. 2003).
[2] Dolev, S., “Self-Stabilization,” The MIT Press(2000).
[3] Eugster, P. T., Guerraoui, R., Kermarrec, A.M., Massoulié, L., “Epidemic Information Dissemination in Distributed Systems,” IEEE Computer, Vol. 37, No. 5, pp. 60–67 (May 2004).
[4] Haberman, R., “Mathematical Model: Population Dynamics,” Prentice Hall (1977).
[5] 市井 誠, 松下 誠, 井上克郎, “ソフトウェア部品グ
ラフの次数分布におけるべき乗則の調査,” ソフト
ウェア信頼性研究会第 3 回ワークショップ論文集,
pp. 87–96 (2006 年 7 月).
[6] Ikeda, S., Tsuchiya, T., and Kikuno, T., “A
Decentralized Scheme for Network-Aware Reliable Overlay Construction,” Proc. of Int’l Conf.
on Information Networking 2006 (ICOIN 2006),
pp. 955–964 (Jan. 2006).
[7] 井上克郎, 神谷年洋, 楠本真二, “コードクローン検出法,” コンピュータソフトウェア, Vol. 18, No. 5,
pp. 529–536 (2001 年 9 月).

[8] Kakugawa, H., and Masuzawa, T., “A Selfstabilizing Minimal Dominating Set Algorithmwith Safe Convergence,” Proc. of Int’l Workshop
on Advances in Parallel and Distributed Computational Models (APDCM 2006), 103, 8 pages(Apr. 2006).
[9] Kamiya, T., Kusumoto, S., and Inoue, K.,“CCFinder: A Multilinguistic Token-Based CodeClone Detection System for Large Scale Source
Code,” IEEE Transaction on Software Engineering, Vol. 28, No. 7, pp. 654–670 (July 2002).
[10] Masuzawa, T., and Kakugawa, H., “Selfstabilization in spite of Frequent Changes of
Networks: Case Study of Mutual Exclusion on
Dynamic Rings,” Proc. of Int’l Symposium on
Self Stabilizing Systems (SSS 2005), pp. 183–197(Oct. 2005).
[11] Masuzawa, T., and Tixeuil. S., “A SelfStabilizing Link-Coloring Protocol Resilient to
Unbounded Byzantine Faults in Arbitrary Networks,” Proc. of Int’l Conf. on Principles of Distributed Systems (OPODIS 2005), pp. 283–298(Dec. 2005).
[12] Masuzawa, T., and Tixeuil, S., “Bounding the
Impact of Unbounded Attacks in Stabilization,”
Proc. of Int’l Symposium on Stabilization, Safety
and Security of Distributed Systems (SSS 2006),
pp. 440–453 (Nov. 2006).
[13] 松尾尚文, 土屋達弘, 菊野 亨, “Detecting Injected
Safety Errors in the Chandra-Toueg Algorithmwith Model Checking,” 第 3 回システム検証の科
学技術シンポジウム (Oct. 2006).
[14] Miura, K., Tagawa, T., and Kakugawa, H., “A
Quorum-Based Protocol for Searching Objects inPeer-to-peer Networks,” IEEE Transactions on
Parallel and Distributed Systems, Vol. 17, No. 1,
pp. 25–37, (Jan. 2006).
[15] Nakaminami, Y., Kakugawa, H., and Masuzawa
T., “An Advanced Performance Analysis of Selfstabilizing Protocols: Stabilization Time withTransient Faults during Convergence,” Proc. ofInt’l Workshop on Advances in Parallel andDistributed Computational Models (APDCM
2006), 106, 8 pages (Apr. 2006).
[16] Nakayama, S., Yoshida, M., Okamura, S., andFujiwara, T., “A Private and Consistent Data
Retrieval Scheme with Log-Squared Communication,” IEICE Transactions on Fundamentals
of Electronics, Communications and Computer
Sciences, Vol. E90-A, No. 1 (Jan. 2007, to appear).
[17] 奥山拓矢, 土屋達弘, 菊野 亨, “ゴシップ型ブロードキャストの高信頼化のための適応的再送手法の提案,” 電子情報通信学会技術研究報告, Vol. 106,
No. 198 (2006 年 8 月).
[18] Ren, S., Guo, L., Jiang, S., and Zhang, X.,“SAT-Match: A Self-Adaptive Topology Matching Method to Achieve Low Lookup Latency

in Structured P2P Overlay Networks,” Proc. of
18th Int’l Parallel and Distributed Processing
Symposium (IPDPS 2004), pp. 83–91, 2004.
[19] Sakurai, Y., Ooshita, F., and Masuzawa, T., “A
Self-stabilizing Link-coloring Protocol in Tree
Networks with Permanent Byzantine Faults,”
Journal of Aerospace Computing, Information,
and Communication, Vol. 3, No. 8, pp.420–436(Aug. 2006).
[20] Shiba, T., Tsuchiya, T., and Kikuno, T., “Using
Artificial Life Techniques to Generate Test Cases
for Combinatorial Testing,” Proc. of Annual
Int’l Computer Software and Applications Conf.
(COMPSAC 2004), pp. 72–77 (Sept. 2004).
[21] Suzuki, T., Izumi, T., Ooshita, F., Kakugawa,H., and Masuzawa, T., “Bio-inspired Replica
Density Control in Dynamic Networks,” Proc.
of Int’l Workshop on Biologically Inspired Approaches to Advanced Information Technology(Bio-ADIT 2006), pp. 281–293 (Jan. 2006).
[22] Suzuki, T., Izumi, T., Ooshita, F., and Masuzawa, T., “Self-adaptive Mobile Agent Population Control in Dynamic Networks Based on theSingle Species Population Model,” IEICE Transactions on Information and Systems, Vol. E90-D,
No. 1 (Jan. 2007, to appear).
[23] 高橋佑典, 泉 泰介, 増澤利光, “P2P ネットワーク
における決定性減衰型ブルームフィルタの提案と検索効率の評価,” 電子情報通信学会技術研究報
告 (NS2006-133), 奨励講演, Vol. 106, No. 355,
pp. 55–60 (2006 年 11 月).
[24] 高須賀史和, 橋本健二, 石原靖哲, 藤原 融, “XML
データベースへの推論攻撃による機密情報特定可能性の形式化とある前提条件のもとでの特定可能性検証法の提案,” 日本データベース学会 Letters,Vol. 5, No. 2, pp. 21–24 (2006 年 9 月)．
[25] Tsuchiya, T., Ikeda, S., and Kikuno, T.,“Counter-Based Reliability Optimization for
Gossip-Based Broadcasting,” Computer Communications, Vol. 29, No. 9, pp. 1516–1521 (May2006).
[26] Wu, Y., Izumi, T., Ooshita, F., Kakugawa, H.,
and Masuzawa, T., “An Adaptive Randomized
Searching Protocol in Peer-to-peer Systems,”
Proc. of ACM Symposium on Applied Computing (SAC 2007), (Mar. 2007, to appear).
[27] Yasunaga, K., and Fujiwara, T., “Determinationof the Local Weight Distribution of Binary Linear Block Codes,” IEEE Transactions on Information Theory, Vol. 52, No. 10, pp. 4444–4454(Oct. 2006).
[28] Yasunaga, K., Fujiwara, T., and Kasami, T.,“Local Weight Distribution of the (256, 93)
Third- Order Binary Reed-Muller Code,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,Vol. E90-A, (2007, to appear).