【研究概要】


当研究室では形式言語理論、アルゴリズム論、プログラム理論などを使って、現実の問題をモデル化し問題解決を図るというアプローチを大切にしています。研究では、なぜ問題がうまく解けたのか(もしくは、解けなかったのか)を客観的に理解することも重要だと思うからです。理論にしっかり根ざした応用研究にはもう一つ、現実の問題を解く過程で得られた知見を通して、理論自体が進展するという面白さがあります。前置きが長くなってしまいました。具体的なテーマを紹介します。




【ソフトウェア設計検証】


安全性と信頼性の高いソフトウェアを実現するための技術、特にセキュリティ、情報保存といった特性に着目した設計検証法に関する研究を行っています。


(1)無限状態モデル検査法

ネットワークからダウンロードしたプログラムを手元の計算機上で実行するということが日常的に行われていますが、それらの中には悪意あるコードが含まれている可能性があります。JDK 等の実行時環境では、そのようなコードから情報を保護するためのアクセス制御機能が提供されています。しかし、アクセス制御をプログラムのどの部分でどのように行うのかは設計者の直観に委ねられています。そこで私達は、アクセス制御を含むプログラムが本当に安全かを検証する方法や、セキュリティ要求を満たすようにアクセス制御をプログラムに自動挿入する手法を提案し、ツールを実装してその有効性の評価も行ってきました。


(2)木言語理論とXM文書処理・変換への応用

XML文書圧縮、XML文書変換の情報保存性、XMLデータベースへの推論攻撃に対するセキュリティ耐性の研究を行っています。

 これらの研究には、木言語理論を用います。文字列は1次元データですがこれを2次元に拡張したものが木表現です。文字列を扱うオートマトンや変換器を木を扱うように拡張したものが木オートマトンや木変換器です。XML文書はタグによって階層構造をもちますから、木によって自然にモデル化できます。そのことから、階層構造の制約を表すXMLスキーマは木オートマトン、XML文書処理・変換は木変換器で自然にモデル化できます。共同研究者と協力し、これらのモデルを用いて以下のテーマに取り組んでいます。

  • 木文法を用いたXML文書圧縮
  • XML文書変換に対する問合せ保存性の判定法
  • XMLスキーマの推論攻撃に対するk-安全性判定法

 

(3)量的概念に基づくセキュリティ・プライバシー

 最近、k-匿名性、量的情報流、差分プライバシーなど、セキュリティ強度・プライバシー保全の度合を計る新しい概念が提案されています。その背景には、セキュリティやプライバシーの有無だけを調べるのではなく、外部から観測可能から推測できる秘匿データの量を定量化したいという社会的要請が高まっていることが挙げられます。

 これらは大変新しいテーマであり、以下のアプローチでこの問題に挑戦しつつあります。

  • ソフトウェア静的解析、論理式のモデル計数を用いた量的情報流の見積もり

  • プライバシー保全と解析パフォーマンスの高トレードオフ実現手法

  • 構造化データのk-匿名化技法



【形式言語理論とその生物データ解析への応用】


多重文脈自由文法(MCFG)という文法を提案しその諸性質を解明してきました。MCFGの生成能力は文脈自由文法(CFG) よりも大きく文脈規定文法(CSG) よりも小さいこと、多項式時間構文解析可能性や言語演算に対する閉包性など、CFG のよい性質を受け継いでいることがわかっています。

 さて、DNA, RNAといったいわゆる生物配列の機能の解明にはその立体構造を知ることが必須だといわれています。しかし、分子生物学における実験データは膨大で誤差も含まれており、それらから有意な情報を効率よく抽出するには優れたアルゴリズム設計が必要です。今風にいうと典型的なビッグデータ解析の問題です。

 RNA にはシュードノットとよばれる重要な部分構造が含まれますが、これはCFG では表現できないけれどMCFGを使えば自然に表現できることがわかっています。そこで、MCFGの構文解析法を利用して、RNA の2次構造予測アルゴリズムを開発しツールの実装も行いました。


今後も引き続き、シーケンシング(誤りを含む超多重マッチング、アセンブリ)や高次構造予測に関する研究を行う予定です。





【研究室のモットー】


学生さんとの議論を通し、

  • 10年後、20年後の研究潮流のさきがけとなるようなシンプルで独創的な研究
  • 「あたかも誰かに発見されるのをその形で待っていたかのような」美しく、種々応用可能な結果を得たい

と思っています。研究室の最大の財産は若い人たちの頭脳だと考えています。新しいことに興味のある積極的な学生さんをお待ちしています。