(57)【要約】【課題】攻撃耐性の高いサーバを構築する。【解決手段】情報処理装置は、外部から入力されて追跡情報が付加されたデータを記憶する記憶手段と、記憶手段からの追跡情報が付加された第１のデータの第１の読み出しを検出する第１の読み出し検出手段と、第１の読み出しの実行後に、記憶手段に対する文字列データの一部に対する第１の書き込みを検出する第１の書き込み検出手段と、第１の書き込みの実行後に、記憶手段からの追跡情報が付加された第２のデータの第２の読み出しを検出する第２の読み出し検出手段と、第２の読み出しの実行後に、記憶手段に対する前記文字列データの一部に対する第２の書き込みを検出する第２の書き込み検出手段と、第１及び第２の読み出し検出手段、第１及び第２の書き込み検出手段によって、第１及び第２の読み出し、第１及び第２の書き込みが検出された場合に、第１及び第２の書き込みによって記憶手段に書き込まれるデータに、追跡情報を付加する付加手段とを具備する。【選択図】      図３
2010102679.tif 000002
【特許請求の範囲】
【請求項１】
外部から入力されて追跡情報が付加されたデータを記憶する記憶手段と、
前記記憶手段からの前記追跡情報が付加された第１のデータの第１の読み出しを検出する第１の読み出し検出手段と、
前記第１の読み出しの実行後に、前記記憶手段に対する文字列データの一部に対する第１の書き込みを検出する第１の書き込み検出手段と、
前記第１の書き込みの実行後に、前記記憶手段からの前記追跡情報が付加された第２のデータの第２の読み出しを検出する第２の読み出し検出手段と、
前記第２の読み出しの実行後に、前記記憶手段に対する前記文字列データの一部に対する第２の書き込みを検出する第２の書き込み検出手段と、
前記第１の読み出し検出手段、前記第１の書き込み検出手段、前記第２の読み出し検出手段及び前記第２の書き込み検出手段によって、前記第１の読み出し、前記第１の書き込み、前記第２の読み出し及び前記第２の書き込みが検出された場合に、前記第１の書き込み及び前記第２の書き込みによって前記記憶手段に書き込まれるデータに、前記追跡情報を付加する付加手段と、
を具備することを特徴とする情報処理装置。
【請求項２】
前記第１及び第２の書き込みが前記文字列に対するものであることを検出する文字列検出手段をさらに具備することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
注入攻撃の検出を目的としてテイント情報の伝搬を行う情報処理装置であって、
プログラムの実行における読み出しと書き込みとからなる時系列の部分系列が第１の条件と第２の条件とを満たすか否かを判断する判断手段と、
前記判断手段によって前記部分系列が前記第１の条件と前記第２の条件とを満たすと判断された場合に、前記第１の条件を満たす書き込み対象のデータに対して前記テイント情報の伝播を行う伝搬手段と、
を具備し、
前記第１の条件は、１つの文字列に対する書き込みをすべて含むことであり、
前記第２の条件は、第１の部分系列と前記第１の部分系列に引き継ぐ第２の部分系列とからなる部分系列群の２つ以上の連続からなることであり、
前記第１の部分系列は、テイントであるデータの読み出しを１つ以上含み、かつ、前記第１の条件の書き込みを含まず、
前記第２の部分系列は、前記第１の条件の書き込みを１つ以上含み、かつ、テイントであるデータの読み出しを含まない、
ことを特徴とする情報処理装置。
【請求項４】
前記テイントでないデータの読み出しをｒ、前記テイントであるデータの読み出しをＲ、前記第１の条件の文字列に対するものではない書き込みをｗ、前記第１の条件の文字列の一部に対する書き込みをＷと表した場合、前記第２の条件は、（［＾Ｗ］＊Ｒ［＾Ｗ］＊［＾Ｒ］＊Ｗ［＾Ｒ］＊）（［＾Ｗ］＊Ｒ［＾Ｗ］＊［＾Ｒ］＊Ｗ［＾Ｒ］＊）＋の正規表現を満たすことを特徴とする請求項３に記載の情報処理装置。
【請求項５】
記憶手段から追跡情報の付加された第１の文字列データを読み出すための複数の読み出しイベントを含む読み出し系列と、前記複数の読み出しイベントの発生タイミングとを検出する読み出し系列検出手段と、
前記記憶手段に対して第２の文字列データを記憶するための複数の書き込みイベントを含む書き込み系列と、前記複数の書き込みイベントの発生タイミングとを検出する書き込み系列検出手段と、
前記読み出し系列検出手段によって検出された前記読み出し系列、前記複数の読み出しイベントの発生タイミング、前記書き込み系列検出手段によって検出された前記書き込み系列、前記複数の書き込みイベントの発生タイミングに基づいて、「前記読み出し系列に含まれており１つ又は連続する複数の読み出しイベントを含む複数の読み出しイベントグループ」と、「前記書き込み系列に含まれており１つ又は連続する複数の書き込みイベントを含む複数の書き込みイベントグループ」との間で、互い違いの関係を満たすか否か判断するインタリービング判断手段と、
前記インタリービング判断手段によって前記互い違いの関係を満たすと判断された前記書き込みイベントグループに含まれている前記書き込みイベントによって書き込まれる文字列データに、前記追跡情報を付加する追跡情報付加手段と
を具備する情報処理装置。
【請求項６】
請求項５記載の情報処理装置において、
前記インタリービング判断手段は、前記読み出し系列における第１の読み出しイベントグループの後に、前記書き込み系列における第１の書き込みイベントグループが発生し、その後さらに、前記読み出し系列における第２の読み出しイベントグループの後に、前記書き込み系列における第２の書き込みイベントグループが発生している場合に、前記互い違いの関係を満たすと判断する
ことを特徴とする情報処理装置。
【請求項７】
請求項６記載の情報処理装置において、
前記追跡情報付加手段は、前記追跡情報を付与する書き込みイベントが複数の読み出しイベントに基づいて発生している場合に、これら複数の読み出しイベントのうち最後に発生した読み出しイベントにおける前記追跡情報を、前記書き込まれる文字列データに付与することを特徴とする情報処理装置。
【請求項８】
請求項５乃至請求項７のいずれか１項に記載の情報処理装置において、
ｔはｔ≧２のしきい値であり、
k≧１であり、
mk1，mk2，…，mkt≧１であり、
n1，n2，…，nt≧１であり、
前記書き込み系列検出手段は、前記書き込み系列を検出し、
前記読み出し系列検出手段は、前記読み出し系列を検出し、
前記読み出し系列を
（ｗ_1_1，ｗ_1_2，…，ｗ_1_n1，
ｗ_2_1，ｗ_2_2，…，ｗ_2_n2，
…
ｗ_t_1，ｗ_t_2，…，ｗ_t_nt，
…）
とし、
前記読み出し系列を
（rk_1_1，rk_1_2，…，rk_1_mk1，
rk_2_1，rk_2_2，…，rk_2_mk2，
…
rk_t_1，rk_t_2，…，rk_t_mkt，
…）
とすると、
前記インタリービング判断手段は、前記書き込み系列と前記読み出し系列との時系列が、
（rk_1_1，rk_1_2，…，rk_1_mk1），
（ｗ_1_1，ｗ_1_2，…，ｗ_1_n1），
（rk_2_1，rk_2_2，…，rk_2_mk2），
（ｗ_2_1，ｗ_2_2，…，ｗ_2_n2），
…
（rk_t_1，rk_t_2，…，rk_t_mkt），
（ｗ_t_1，ｗ_t_2，…，ｗ_t_n2）
…
の互い違いの関係を満たすか判断し、
前記追跡情報付加手段は、前記互い違いの関係を満たす場合に、
i（i≧１）とし、
（r1_i_m1i，r2_i_m2i，…）
の中で、最後に現れた読み出しイベントにおける読み出し元のテイント情報を
（ｗ_i_1，ｗ_i_2，…，ｗ_i_ni）
の書き込みに対して付加する
ことを特徴とする情報処理装置。
【請求項９】
コンピュータが、外部から入力されて追跡情報が付加されたデータを記憶し、
前記コンピュータが、前記記憶手段からの前記追跡情報が付加された第１のデータの第１の読み出しを検出し、
前記コンピュータが、前記第１の読み出しの実行後に、前記記憶手段に対する文字列データの一部に対する第１の書き込みを検出し、
前記コンピュータが、前記第１の書き込みの実行後に、前記記憶手段からの前記追跡情報が付加された第２のデータの第２の読み出しを検出し、
前記コンピュータが、前記第２の読み出しの実行後に、前記記憶手段に対する前記文字列データの一部に対する第２の書き込みを検出し、
前記コンピュータが、前記第１の読み出し、前記第１の書き込み、前記第２の読み出し及び前記第２の書き込みが検出された場合に、前記第１の書き込み及び前記第２の書き込みによって前記記憶手段に書き込まれるデータに、前記追跡情報を付加する
ことを特徴とする情報処理方法。
【請求項１０】
コンピュータ・システムに対する注入攻撃の検出を目的とするテイント情報の伝搬方法であって、
プログラムの実行における読み出しと書き込みとからなる時系列の部分系列が第１の条件と第２の条件とを満たす場合、前記第１の条件を満たす書き込み対象のデータに対して前記テイント情報の伝播を行い、
前記第１の条件は、１つの文字列に対する書き込みをすべて含むことであり、
前記第２の条件は、第１の部分系列と前記第１の部分系列に引き継ぐ第２の部分系列とからなる部分系列群の２つ以上の連続からなることであり、
前記第１の部分系列は、テイントであるデータの読み出しを１つ以上含み、かつ、前記第１の条件の書き込みを含まず、
前記第２の部分系列は、前記第１の条件の書き込みを１つ以上含み、かつ、テイントであるデータの読み出しを含まない、
ことを特徴とする情報処理方法。
【請求項１１】
前記テイントでないデータの読み出しをｒ、前記テイントであるデータの読み出しをＲ、前記第１の条件の文字列に対するものではない書き込みをｗ、前記第１の条件の文字列の一部に対する書き込みをＷと表した場合、前記第２の条件は、（［＾Ｗ］＊Ｒ［＾Ｗ］＊［＾Ｒ］＊Ｗ［＾Ｒ］＊）（［＾Ｗ］＊Ｒ［＾Ｗ］＊［＾Ｒ］＊Ｗ［＾Ｒ］＊）＋の正規表現を満たすことを特徴とする請求項６に記載の情報処理方法。
【請求項１２】
コンピュータが、記憶手段から追跡情報の付加された第１の文字列データを読み出すための複数の読み出しイベントを含む読み出し系列と、前記複数の読み出しイベントの発生タイミングとを検出するとともに、前記記憶手段に対して第２の文字列データを記憶するための複数の書き込みイベントを含む書き込み系列と、前記複数の書き込みイベントの発生タイミングとを検出し、
前記コンピュータが、前記読み出し系列、前記複数の読み出しイベントの発生タイミング、前記書き込み系列、前記複数の書き込みイベントの発生タイミングに基づいて、「前記読み出し系列に含まれており１つ又は連続する複数の読み出しイベントを含む複数の読み出しイベントグループ」と、「前記書き込み系列に含まれており１つ又は連続する複数の書き込みイベントを含む複数の書き込みイベントグループ」との間で、互い違いの関係を満たすか否か判断し、前記互い違いの関係を満たすと判断された前記書き込みイベントグループに含まれている前記書き込みイベントによって書き込まれる文字列データに、前記追跡情報を付加する
ことを特徴とする情報処理方法。
【請求項１３】
コンピュータに、
外部から入力されて追跡情報が付加されたデータを記憶する機能と、
前記記憶手段からの前記追跡情報が付加された第１のデータの第１の読み出しを検出する機能と、
前記第１の読み出しの実行後に、前記記憶手段に対する文字列データの一部に対する第１の書き込みを検出する機能と、
前記第１の書き込みの実行後に、前記記憶手段からの前記追跡情報が付加された第２のデータの第２の読み出しを検出する機能と、
前記第２の読み出しの実行後に、前記記憶手段に対する前記文字列データの一部に対する第２の書き込みを検出する機能と、
前記第１の読み出し、前記第１の書き込み、前記第２の読み出し及び前記第２の書き込みがそれぞれ検出された場合に、前記第１の書き込み及び前記第２の書き込みによって前記記憶手段に書き込まれるデータに、前記追跡情報を付加する機能と、
を実現させるためのプログラム。
【請求項１４】
コンピュータに対する注入攻撃の検出を目的とするテイント情報の伝搬を前記コンピュータに実行させるプログラムであって、
前記コンピュータに、
注入攻撃検出の対象となるプログラムの実行における読み出しと書き込みとからなる時系列の部分系列が第１の条件と第２の条件とを満たすか否かを判断する機能と、
前記判断する機能によって前記部分系列が前記第1の条件と前記第２の条件とを満たすと判断されるときに、前記第１の条件を満たす書き込み対象のデータに対して前記テイント情報の伝播を行う機能と、
を実行させるためのプログラムであり、
前記第１の条件は、１つの文字列に対する書き込みをすべて含むことであり、
前記第２の条件は、第１の部分系列と前記第１の部分系列に引き継ぐ第２の部分系列とからなる部分系列群の２つ以上の連続からなることであり、
前記第１の部分系列は、テイントであるデータの読み出しを１つ以上含み、かつ、前記第１の条件の書き込みを含まず、
前記第２の部分系列は、前記第１の条件の書き込みを１つ以上含み、かつ、テイントであるデータの読み出しを含まない、
ことを特徴とするプログラム。
【請求項１５】
前記テイントでないデータの読み出しをｒ、前記テイントであるデータの読み出しをＲ、前記第１の条件の文字列に対するものではない書き込みをｗ、前記第１の条件の文字列の一部に対する書き込みをＷと表した場合、前記第２の条件は、（［＾Ｗ］＊Ｒ［＾Ｗ］＊［＾Ｒ］＊Ｗ［＾Ｒ］＊）（［＾Ｗ］＊Ｒ［＾Ｗ］＊［＾Ｒ］＊Ｗ［＾Ｒ］＊）＋の正規表現を満たすことを特徴とする請求項９に記載のプログラム。
【請求項１６】
コンピュータを、
記憶手段から追跡情報の付加された第１の文字列データを読み出すための複数の読み出しイベントを含む読み出し系列と、前記複数の読み出しイベントの発生タイミングとを検出する読み出し系列検出手段、
前記記憶手段に対して第２の文字列データを記憶するための複数の書き込みイベントを含む書き込み系列と、前記複数の書き込みイベントの発生タイミングとを検出する書き込み系列検出手段、
前記読み出し系列検出手段によって検出された前記読み出し系列、前記複数の読み出しイベントの発生タイミング、前記書き込み系列検出手段によって検出された前記書き込み系列、前記複数の書き込みイベントの発生タイミングに基づいて、「前記読み出し系列に含まれており１つ又は連続する複数の読み出しイベントを含む複数の読み出しイベントグループ」と、「前記書き込み系列に含まれており１つ又は連続する複数の書き込みイベントを含む複数の書き込みイベントグループ」との間で、互い違いの関係を満たすか否か判断するインタリービング判断手段、
前記インタリービング判断手段によって前記互い違いの関係を満たすと判断された前記書き込みイベントグループに含まれている前記書き込みイベントによって書き込まれる文字列データに、前記追跡情報を付加する追跡情報付加手段
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ・システムに対する注入攻撃（injection attack）の検出等を目的とする情報処理装置、情報処理方法及びこれを実現させるためのプログラムに関する。
【背景技術】
【０００２】
コンピュータ・システムに対する注入攻撃とは、コンピュータ・システムの脆弱性を利用して、外部からこのコンピュータ・システムに注入（inject）した攻撃コードや攻撃コマンドなどを、このコンピュータ・システムに実行させる攻撃をいう。
【０００３】
当初は、バッファ・オーバフローをはじめとして、通常クライアント上で動作するネイティブ・コードのプログラムに対する攻撃が主であった。しかし、最近では、クロス・サイト・スクリプティング（ＸＳＳ）やＳＱＬインジェクションなど、Ｐｅｒｌ、ＰＨＰ、Ｊａｖａ（登録商標）などのスクリプト言語で記述されたサーバ・プログラムに対する攻撃が深刻になっている。ここで、前者のように、ネイティブ・コードの構造に依存する攻撃を低次（low-level）の攻撃といい、後者のように、ネイティブ・コードの構造に依存しない攻撃を高次（high-level）の攻撃という。
【０００４】
このような注入攻撃を検出する方法として、ＤＴＰ（Dynamic Taint Propagation）、ＤＩＦＴ（Dynamic Information Flow Tracking）と呼ばれる技術群がある。ＤＴＰ／ＤＩＦＴでは、プログラムが扱う各データには、外部からの入力に依存するかどうかを表す追跡情報（以下、テイント情報と称す。）が付加される。そして、ＤＴＰ／ＤＩＦＴでは、このテイント情報を用いて、動的（Dynamic）に、すなわち、プログラム実行時に、外部から入力されたデータに依存するデータを追跡することによって、注入攻撃を検出する。
【０００５】
テイント情報は、最も基本的な方法では、１ビットのテイント・ビットによって表現される。以下、その場合を基に説明するが、実質的に相当する場合も包含される。注入攻撃を検出するより具体的な方法は、以下の（１−１）から（１−３）による３つの処理を行う。なお、テイント・ビットがセットされたデータをテイント・データという。
【０００６】
（１−１）外部からデータが入力されたとき、そのデータに対してテイント・ビットをセットする。
【０００７】
（１−２）データの依存関係にしたがって、依存元から依存先へとテイント・ビットの内容を伝搬させる。
【０００８】
（１−３）プログラムからデータが出力されるとき、そのデータのテイント・ビットを検査する。テイント・ビットがセットされていれば、攻撃の可能性があると判定する。
【０００９】
ＤＴＰ／ＤＩＦＴには、以下で述べるように、処理の実行主体に関して、様々な実装方法が考えられる。
【００１０】
ＤＴＰでは、Ｐｅｒｌのテイント・モードをはじめとする言語レベルのものでは、テイント・ビットの扱いが言語仕様の一部として追加定義される。したがって、テイント・ビットの扱いは、文などの言語構造に対して定義される。典型的には、代入文の実行に際して、右辺を構成する各データに付加されたテイント・ビットの内容を左辺が示すデータのテイント・ビットへと伝搬させることになる。実際の処理は、インタープリタによって行われるか、コンパイラによって埋め込まれたネイティブ・コードをプロセッサなどが実行することなどによって行われる。
【００１１】
ＤＩＦＴは、低次の注入攻撃を検出することを目的に、Ｐｅｒｌのテイント・モードをプロセッサに応用したものであり、上記（１−２）の処理の実行主体はプロセッサになる。すなわち、テイント・ビットの扱いは、プロセッサが実行する命令に対して定義される。典型的には、プロセッサが命令を実行する際に、ソース・オペランドに付加されたテイント・ビットの内容をデスティネーション・オペランドのテイント・ビットへと伝搬させることになる。
【００１２】
このようなＤＩＦＴは、もともと低次の注入攻撃を検出するために考案されたものではあるが、高次の注入攻撃も検出することが可能である。ＤＩＦＴでは、上記（１−１）、（１−３）の処理はプロセッサ単体では実行することができないため、以下のように、コンピュータ・システムのプロセッサ以外の部分との連携が見られる。
【００１３】
（２−１）（プログラムの外部からではなく）ネットワークなどを介して、コンピュータ・システムの外部から入力されたデータに対して、テイント・ビットをセットする。
【００１４】
（２−２）データの依存関係にしたがって、依存元から依存先へとテイント・ビットの情報を伝搬させる。
【００１５】
（２−３）プログラムからデータが出力されるとき、単にデータのテイント・ビットがセットされているか否かだけではなく、どの部分のテイント・ビットがセットされているか否かを検査する。例えば、システム・コールやデータベース・システムに対するＳＱＬ文であれば、出力された文字列の構文解析を行い、コマンド名やファイル名など、コンピュータ・システムの外部から直接指定されてはならない部分のテイント・ビットがセットされていないか否かを検査する。
【００１６】
ＤＴＰ／ＤＩＦＴには、上述以外にも、Ｊａｖａ（登録商標）  ＶＭをはじめとする中間言語の実行系に対するものや、プロセッサ・エミュレータに対するものなど、様々なレベルの実装方法が考えられる。
【００１７】
なお、これらのうち、ＤＩＦＴなど、特定の言語に依存しないものは、包括的であるというメリットがある。言語レベルの技術は、当然のことながら、特定の言語によって記述されたプログラムにしか適用できない。これに対し、言語非依存なものは、その上で実行されるあらゆるプログラムに適用することができる。
【００１８】
ところで、意味のあるサービスを提供するプログラムでは、その出力は入力に依存する。出力が入力に依存しないということは、常に同じ値を出力することを意味することになる。そのようなプログラムは、実際上、役に立たない。
【００１９】
したがって、意味のあるプログラムに対してＤＴＰ／ＤＩＦＴを完全に厳密に実行すると、その出力は入力に依存するのであるから、あらゆる出力データのテイント・ビットがセットされることになり、意味がない。結局、ＤＴＰ／ＤＩＦＴを意味のあるものにするには、何らかの条件を満たした時にはテイント・ビットの伝搬を行わないという非伝搬の規則が重要である。
【００２０】
非伝搬規則の設定にあたっては、データ依存によって生じる直接的依存には工夫の余地がないが、条件分岐や間接参照などによって生じる間接的依存の取り扱いが難しい。実際、従来のＤＴＰ／ＤＩＦＴは、間接依存に関する非伝搬規則が機械的に定められているため、誤検出や検出漏れが多く発生していた。
【００２１】
特に、プロセッサで伝搬を行うＤＩＦＴでは、条件分岐における分岐条件の依存先の範囲を特定すること自体がそもそも困難である。
【００２２】
言語レベルのＤＴＰにおいても、言語の文法規則の上で、非伝搬規則は機械的に定められている。例えばＰｅｒｌでは、正規表現マッチで一致した部分を出力するとき、出力にはテイント・ビットは伝搬しない。例えばプラス記号を空白文字に置き換えるような、注入攻撃に関しては無意味なマッチの場合であっても、伝搬は行われない。
【００２３】
尚、この出願の発明に関連する先行技術文献情報としては、次のようなものがある。
【先行技術文献】
【非特許文献】
【００２４】
【非特許文献１】マイケル・ダルトン（Michael Dalton）、外２名、「Ｒａｋｓｈａ：ソフトウェア・セキュリティのための柔軟な情報フロー・アーキテクチャ（Raksha: A Flexible Information Flow Architecture for Software Security）」、インターナショナル・シンポジウム・オン・コンピュータ・アーキテクチャ（International Symposium on Computer Architecture）、２００７年、ｐｐ．２２７-２３２
【発明の概要】
【発明が解決しようとする課題】
【００２５】
本発明は、攻撃耐性の高いサーバを構築することが可能な情報処理装置、情報処理方法及びこれを実現させるためのプログラムを提供する。
【課題を解決するための手段】
【００２６】
本発明の第１の態様による情報処理装置は、外部から入力されて追跡情報が付加されたデータを記憶する記憶手段と、前記記憶手段からの前記追跡情報が付加された第１のデータの第１の読み出しを検出する第１の読み出し検出手段と、前記第１の読み出しの実行後に、前記記憶手段に対する文字列データの一部に対する第１の書き込みを検出する第１の書き込み検出手段と、前記第１の書き込みの実行後に、前記記憶手段からの前記追跡情報が付加された第２のデータの第２の読み出しを検出する第２の読み出し検出手段と、前記第２の読み出しの実行後に、前記記憶手段に対する前記文字列データの一部に対する第２の書き込みを検出する第２の書き込み検出手段と、前記第１の読み出し検出手段、前記第１の書き込み検出手段、前記第２の読み出し検出手段及び前記第２の書き込み検出手段によって、前記第１の読み出し、前記第１の書き込み、前記第２の読み出し及び前記第２の書き込みが検出された場合に、前記第１の書き込み及び前記第２の書き込みによって前記記憶手段に書き込まれるデータに、前記追跡情報を付加する付加手段と、を具備する。
【００２７】
本発明の第２の態様による情報処理装置は、注入攻撃の検出を目的としてテイント情報の伝搬を行う情報処理装置であって、プログラムの実行における読み出しと書き込みとからなる時系列の部分系列が第１の条件と第２の条件とを満たすか否かを判断する判断手段と、前記判断手段により前記部分系列が前記第1の条件と前記第２の条件とを満たすと判断された場合に、前記第１の条件を満たす書き込み対象のデータに対して前記テイント情報の伝播を行う伝搬手段と、を具備し、前記第１の条件は、１つの文字列に対する書き込みをすべて含むことであり、前記第２の条件は、第１の部分系列と前記第１の部分系列に引き継ぐ第２の部分系列とからなる部分系列群の２つ以上の連続からなることであり、前記第１の部分系列は、テイントであるデータの読み出しを１つ以上含み、かつ、前記第１の条件の書き込みを含まず、前記第２の部分系列は、前記第１の条件の書き込みを１つ以上含み、かつ、テイントであるデータの読み出しを含まない。
【００２８】
本発明の第３の態様による情報処理装置は、記憶手段から追跡情報の付加された第１の文字列データを読み出すための複数の読み出しイベントを含む読み出し系列と、前記複数の読み出しイベントの発生タイミングとを検出する読み出し系列検出手段と、前記記憶手段に対して第２の文字列データを記憶するための複数の書き込みイベントを含む書き込み系列と、前記複数の書き込みイベントの発生タイミングとを検出する書き込み系列検出手段と、前記読み出し系列検出手段によって検出された前記読み出し系列、前記複数の読み出しイベントの発生タイミング、前記書き込み系列検出手段によって検出された前記書き込み系列、前記複数の書き込みイベントの発生タイミングに基づいて、「前記読み出し系列に含まれており１つ又は連続する複数の読み出しイベントを含む複数の読み出しイベントグループ」と、「前記書き込み系列に含まれており１つ又は連続する複数の書き込みイベントを含む複数の書き込みイベントグループ」との間で、互い違いの関係を満たすか否か判断するインタリービング判断手段と、前記インタリービング判断手段によって前記互い違いの関係を満たすと判断された前記書き込みイベントグループに含まれている前記書き込みイベントによって書き込まれる文字列データに、前記追跡情報を付加する追跡情報付加手段とを具備する。
【００２９】
本発明の第４の態様による情報処理方法は、コンピュータが、外部から入力されて追跡情報が付加されたデータを記憶し、前記コンピュータが、前記記憶手段からの前記追跡情報が付加された第１のデータの第１の読み出しを検出し、前記コンピュータが、前記第１の読み出しの実行後に、前記記憶手段に対する文字列データの一部に対する第１の書き込みを検出し、前記コンピュータが、前記第１の書き込みの実行後に、前記記憶手段からの前記追跡情報が付加された第２のデータの第２の読み出しを検出し、前記コンピュータが、前記第２の読み出しの実行後に、前記記憶手段に対する前記文字列の一部に対する第２の書き込みを検出し、前記コンピュータが、前記第１の読み出し、前記第１の書き込み、前記第２の読み出し及び前記第２の書き込みが検出された場合に、前記第１の書き込み及び前記第２の書き込みによって前記記憶手段に書き込まれるデータに、前記追跡情報を付加する。
【００３０】
本発明の第５の態様による情報処理方法は、コンピュータ・システムに対する注入攻撃の検出を目的とするテイント情報の伝搬方法であって、プログラムの実行における読み出しと書き込みとからなる時系列の部分系列が第１の条件と第２の条件とを満たす場合、前記第１の条件を満たす書き込み対象のデータに対して前記テイント情報の伝播を行い、前記第１の条件は、１つの文字列に対する書き込みをすべて含むことであり、前記第２の条件は、第１の部分系列と前記第１の部分系列に引き継ぐ第２の部分系列とからなる部分系列群の２つ以上の連続からなることであり、前記第１の部分系列は、テイントであるデータの読み出しを１つ以上含み、かつ、前記第１の条件の書き込みを含まず、前記第２の部分系列は、前記第１の条件の書き込みを１つ以上含み、かつ、テイントであるデータの読み出しを含まない。
【００３１】
本発明の第６の態様による情報処理方法では、コンピュータが、記憶手段から追跡情報の付加された第１の文字列データを読み出すための複数の読み出しイベントを含む読み出し系列と、前記複数の読み出しイベントの発生タイミングとを検出するとともに、前記記憶手段に対して第２の文字列データを記憶するための複数の書き込みイベントを含む書き込み系列と、前記複数の書き込みイベントの発生タイミングとを検出し、前記コンピュータが、前記読み出し系列、前記複数の読み出しイベントの発生タイミング、前記書き込み系列、前記複数の書き込みイベントの発生タイミングに基づいて、「前記読み出し系列に含まれており１つ又は連続する複数の読み出しイベントを含む複数の読み出しイベントグループ」と、「前記書き込み系列に含まれており１つ又は連続する複数の書き込みイベントを含む複数の書き込みイベントグループ」との間で、互い違いの関係を満たすか否か判断し、前記互い違いの関係を満たすと判断された前記書き込みイベントグループに含まれている前記書き込みイベントによって書き込まれる文字列データに、前記追跡情報を付加する。
【００３２】
本発明の第７の態様によるプログラムは、コンピュータに、外部から入力されて追跡情報が付加されたデータを記憶する機能と、前記記憶手段からの前記追跡情報が付加された第１のデータの第１の読み出しを検出する機能と、前記第１の読み出しの実行後に、前記記憶手段に対する文字列データの一部に対する第１の書き込みを検出する機能と、前記第１の書き込みの実行後に、前記記憶手段からの前記追跡情報が付加された第２のデータの第２の読み出しを検出する機能と、前記第２の読み出しの実行後に、前記記憶手段に対する前記文字列データの一部に対する第２の書き込みを検出する機能と、前記第１の読み出し、前記第１の書き込み、前記第２の読み出し及び前記第２の書き込みがそれぞれ検出された場合に、前記第１の書き込み及び前記第２の書き込みによって前記記憶手段に書き込まれるデータに、前記追跡情報を付加する機能と、を実現させる。
【００３３】
本発明の第８の態様によるプログラムは、コンピュータに対する注入攻撃の検出を目的とするテイント情報の伝搬を前記コンピュータに実行させるプログラムであって、前記コンピュータに、注入攻撃の検出の対象となるプログラムの実行における読み出しと書き込みとからなる時系列の部分系列が第１の条件と第２の条件とを満たすか否かを判断する機能と、前記判断する機能によって前記部分系列が前記第1の条件と前記第２の条件とを満たすと判断される場合に、前記第１の条件を満たす書き込み対象のデータに対して前記テイント情報の伝播を行う機能と、を実行させるためのプログラムであり、前記第１の条件は、１つの文字列に対する書き込みをすべて含むことであり、前記第２の条件は、第１の部分系列と前記第１の部分系列に引き継ぐ第２の部分系列とからなる部分系列群の２つ以上の連続からなることであり、前記第１の部分系列は、テイントであるデータの読み出しを１つ以上含み、かつ、前記第１の条件の書き込みを含まず、前記第２の部分系列は、前記第１の条件の書き込みを１つ以上含み、かつ、テイントであるデータの読み出しを含まない。
【００３４】
本発明の第９の態様によるプログラムは、コンピュータを、記憶手段から追跡情報の付加された第１の文字列データを読み出すための複数の読み出しイベントを含む読み出し系列と、前記複数の読み出しイベントの発生タイミングとを検出する読み出し系列検出手段、前記記憶手段に対して第２の文字列データを記憶するための複数の書き込みイベントを含む書き込み系列と、前記複数の書き込みイベントの発生タイミングとを検出する書き込み系列検出手段、前記読み出し系列検出手段によって検出された前記読み出し系列、前記複数の読み出しイベントの発生タイミング、前記書き込み系列検出手段によって検出された前記書き込み系列、前記複数の書き込みイベントの発生タイミングに基づいて、「前記読み出し系列に含まれており１つ又は連続する複数の読み出しイベントを含む複数の読み出しイベントグループ」と、「前記書き込み系列に含まれており１つ又は連続する複数の書き込みイベントを含む複数の書き込みイベントグループ」との間で、互い違いの関係を満たすか否か判断するインタリービング判断手段、前記インタリービング判断手段によって前記互い違いの関係を満たすと判断された前記書き込みイベントグループに含まれている前記書き込みイベントによって書き込まれる文字列データに、前記追跡情報を付加する追跡情報付加手段として機能させる。
【発明の効果】
【００３５】
本発明によれば、攻撃耐性の高いサーバを構築することが可能な情報処理装置、情報処理方法及びこれを実現させるためのプログラムを提供できる。
【図面の簡単な説明】
【００３６】
【図１】本発明の第１の実施形態に係わるテイント・ビットの伝搬方法を示す状態遷移図。
【図２】本発明の第１の実施形態に係わるテイント・ビットの伝搬方法の具体例を示す図。
【図３】本発明の第１の実施形態に係わる情報処理装置を示すブロック図。
【図４】本発明の第１の実施形態に係わる情報処理装置を示すブロック図。
【図５】本発明の第１の実施形態に係わる他の情報処理装置を示すブロック図。
【図６】図５の情報処理装置が実行する情報処理のフロー図。
【図７】本発明の第２の実施形態に係わる情報処理装置の構成の一例を示すブロック図。
【図８】第２の実施形態に係わるアルゴリズムによってテイント情報が伝搬される状態の第１の例を示す図。
【図９】第２の実施形態に係わるアルゴリズムによってテイント情報が伝搬される状態の第２の例を示す図。
【図１０】第２の実施形態に係わるアルゴリズムによってテイント情報が伝搬される状態の第３の例を示す図。
【図１１】第２の実施形態に係わるアルゴリズムによってテイント情報が伝搬される状態の第４の例を示す図。
【図１２】本発明の第３の実施形態に係わる文字列検出テーブルの一例を示す図。
【図１３】第３の実施形態に係わる文字列検出テーブルのエントリ毎に行う文字列検出動作の一例を示すフローチャート。
【図１４】第３の実施形態に係わるアクセスを通知された側の動作の一例を示すフローチャート。
【図１５】第３の実施形態に係わるロード命令が実行された場合の動作の一例を示すフローチャート。
【図１６】第３の実施形態に係わるストア命令が実行された場合の動作の一例を示すフローチャート。
【発明を実施するための形態】
【００３７】
本発明の実施の形態を以下に図面を参照して説明する。尚、以下の各実施の形態では、入力データとこの入力データに依存するデータであることを示す追跡情報の一例として、テイント・ビットを用いる場合を例に挙げて説明するが、他の情報を用いる場合でもよい。以下の各図において、同一の構成要素については同一の符号を付して説明を省略する。
【００３８】
（第１の実施形態）
［１］テイント情報の伝搬の規則
本発明者は、テイント・ビットの伝搬を行う場合の規則について、次のような考察を行った。
【００３９】
プログラムには、入力から出力に至る依存の経路が１つ以上存在する。コンピュータ・システムに対する注入攻撃に関しては、これらの経路のうち、入力も出力も文字列であるもののみを考えればよい。この経路は、１つ以上の部分処理からなる。個々の部分処理は、出力される文字列を用意した主体が当該プログラムかそうでないかによって、以下の２種に分けられる。
【００４０】
第１は、ｎ択的処理である。この処理は、プログラムが用意したｎ個の文字列群のうちから、入力によって１つが選択され、出力されるものである。
【００４１】
第２は、フリーフォーム的処理である。この処理は、入力された文字列が、そのまま、あるいは文字列変換を経て、出力されるものである。ここでいう文字列変換とは、大文字と小文字、半角文字と全角文字との変換、異なる文字コード間の変換、ＵＲＬエンコード／デコードなど、文字の表現方法が変換されるだけで、その表す内容は実質的に変化しないものを指す。
【００４２】
この２つの処理は、注入攻撃に対して、ｎ択的処理は安全であり、フリーフォーム的処理は危険である。したがって、入力文字列から出力文字列へのテイント・ビットの情報の伝搬は、フリーフォーム的処理に関しては行い、ｎ択的処理に関しては行わなければよい。
【００４３】
［２］テイント情報の伝搬
［２−１］概要
本実施形態では、コンピュータ・システムの外部からデータが入力された場合、このデータに対してテイント・ビットをセットする。プログラムの依存関係にしたがって、プロセッサによって、依存元から依存先へとテイント・ビットの情報を伝搬させる。データを出力するときは、このデータのテイント・ビットがセットされている（テイントである）か否かを検査する。
【００４４】
ここで、テイント・ビットの伝搬においては、プログラムの実行における読み出しと書き込みとからなる時系列を検査し、フリーフォーム的処理であるとみなす場合（例えば、文字列への出力をなす個々の書き込みの間にテイントであるデータを読み出していた場合）はテイント・ビットの伝搬を行う。
【００４５】
フリーフォーム的処理であるとみなす場合とは、以下の第１の条件と第２の条件とを満たす部分系列を指す。この場合、第１の条件の書き込み対象の文字列データに対してテイント・ビットの伝播を行う。
【００４６】
第１の条件：１つの文字列に対する書き込みをすべて含む。但し、文字列検出器によって１つの文字列に対するものと検出される場合を含む。
【００４７】
第２の条件：第１の部分系列とこの第１の部分系列に引き継ぐ第２の部分系列とからなる部分系列群の２つ以上の連続からなる。
【００４８】
第１の部分系列：テイントであるデータの読み出しを１つ以上含み、かつ、前記第１の条件の書き込みを含まない。
【００４９】
第２の部分系列：前記第１の条件の書き込みを１つ以上含み、かつ、テイントであるデータの読み出しを含まない。
【００５０】
このようなテイント情報の伝搬において、テイントでないデータの読み出しをｒ、テイントであるデータの読み出しをＲ、上記第１の条件の文字列に対するものではない書き込みをｗ、上記第１の条件の文字列の一部に対する書き込みをＷと表すと、上記第２の条件を満たす部分系列は、以下の式（１）の正規表現で表すことができる。
【００５１】
（［＾Ｗ］＊Ｒ［＾Ｗ］＊［＾Ｒ］＊Ｗ［＾Ｒ］＊）（［＾Ｗ］＊Ｒ［＾Ｗ］＊［＾Ｒ］＊Ｗ［＾Ｒ］＊）＋…（１）
［２−２］状態遷移図
図１は、式（１）の正規表現と同じ系列を受理するオートマトンの状態遷移図である。同図中、丸は状態を、矢印は状態遷移を、それぞれ表す。矢印に隣接して書かれたシンボルが入力されたとき、矢印の元の状態から先の状態へと遷移する。
【００５２】
オートマトンは、最初、初期状態Ｓ０にあり、順に入力される系列のシンボルにしたがって状態遷移を繰り返す。系列の最後のシンボルを入力した後に、オートマトンが受理状態Ｓ４にあれば、その系列は受理される。
【００５３】
具体的には、初期状態Ｓ０において、テイントでないデータの読み出しｒ及び上記第１の条件の文字列に対するものではない書き込みｗが入力された場合は再び状態Ｓ０に遷移し、テイントであるデータの読み出しＲが入力された場合は状態Ｓ１に遷移する。
【００５４】
状態Ｓ１において、テイントでないデータの読み出しｒ、テイントであるデータの読み出しＲ及び上記第１の条件の文字列に対するものではない書き込みｗが入力された場合は再び状態Ｓ１に遷移し、上記第１の条件の文字列の出力の一部に対する書き込みＷが入力された場合は状態Ｓ２に遷移する。
【００５５】
状態Ｓ２において、テイントでないデータの読み出しｒ、上記第１の条件の文字列に対するものではない書き込みｗ及び上記第１の条件の文字列の一部に対する書き込みＷが入力された場合は再び状態Ｓ２に遷移し、テイントであるデータの読み出しＲが入力された場合は状態Ｓ３に遷移する。
【００５６】
状態Ｓ３において、テイントでないデータの読み出しｒ、テイントであるデータの読み出しＲ及び上記第１の条件の文字列に対するものではない書き込みｗが入力された場合は再び状態Ｓ３に遷移し、上記第１の条件の文字列の一部に対する書き込みＷが入力された場合は状態Ｓ４に遷移する。
【００５７】
状態Ｓ４において、テイントでないデータの読み出しｒ、上記第１の条件の文字列の出力に対するものではない書き込みｗ及び上記第１の条件の文字列の一部に対する書き込みＷが入力された場合は再び状態Ｓ４に遷移し、テイントであるデータの読み出しＲが入力された場合は状態Ｓ５に遷移する。
【００５８】
状態Ｓ５において、テイントでないデータの読み出しｒ、テイントであるデータの読み出しＲ及び上記第１の条件の文字列に対するものではない書き込みｗが入力された場合は再び状態Ｓ５に遷移し、上記第１の条件の文字列の一部に対する書き込みＷが入力された場合は状態Ｓ４に遷移する。
【００５９】
以上のように、本実施形態によれば、式（１）の正規表現が表すシンボルの系列、図１の状態遷移図によって表わされるオートマトンが受理するシンボルの系列に対して、上記第１の条件の文字列の一部に対する書き込みＷの対象となる文字列データに対してテイント情報の伝搬を行う。
【００６０】
［２−３］具体例
図２は、テイント情報の伝搬を行う部分系列の具体例（例１−ａ〜ｃ）とテイント情報の伝搬を行わない部分系列の具体例（例２−ａ〜ｂ）をそれぞれ示す。各例において、テイントであるデータの読み出しをＲで示し、上記第１の条件の文字列の一部に対する書き込みをＷと示す。また、本図における（１）及び（２）は、上述した第２の条件の第１の部分系列及び第２の部分系列にそれぞれ相当する。なお、本図では、簡単のため、ＲとＷについてのみ示すが、ｒ（テイントでないデータの読み出し）、ｗ（上記第１の条件の文字列に対するものではない書き込み）は任意の位置にいくらでも現れてよい。
【００６１】
例１−ａは、テイント情報の伝搬を行う最も簡単な例である。１つのＲからなる第１の部分系列（１）と１つのＷからなる第２の部分系列（２）とを有する部分系列群が２回連続している。これにより、例１−ａは、上述した第２の条件を満たす。
【００６２】
例１−ｂは、例１−ａと同様、１つのＲからなる第１の部分系列（１）と１つのＷからなる第２の部分系列（２）とを有する部分系列群が存在している。そして、例１−ｂでは、この部分系列群が４回連続している。これにより、例１−ｂは、上述した第２の条件を満たす。この例１−ｂは、フリーフォーム的処理の典型例となっている。
【００６３】
例１−ｃは、それぞれの部分系列に含まれるＲ、Ｗの個数がそれぞれ異なっている例である。１番目の部分系列群は、１つのＲからなる第１の部分系列（１）と１つのＷからなる第２の部分系列（２）とを有する。２番目の部分系列群は、２つのＲからなる第１の部分系列（１）と１つのＷからなる第２の部分系列（２）とを有する。３番目の部分系列群は、１つのＲからなる第１の部分系列（１）と３つのＷからなる第２の部分系列（２）とを有する。このように、各部分系列に含まれるＲ、Ｗの個数がそれぞれ異なっている例１−ｃのような場合も、上述した第２の条件を満たす。
【００６４】
一方、例２−ａと例２−ｂは、部分系列群が２回以上連続していない例である。例２−ａは、１つのＲからなる第１の部分系列（１）と１つのＷからなる第２の部分系列（２）とを有する部分系列群が存在しているだけで、この部分系列群が連続しない。したがって、第２の条件の後半の「部分系列群の２つ以上の連続からなる」という条件を満たさないため、テイント・ビットの伝搬が行われない。同様に、例２−ｂは、１つのＲからなる第１の部分系列（１）と４つのＷからなる第２の部分系列（２）とを有する部分系列群が存在しているだけで、この部分系列群が連続しない。したがって、第２の条件の後半の「部分系列群の２つ以上の連続からなる」という条件を満たさないため、テイント・ビットの伝搬が行われない。この例２−ｂは、ｎ択的処理の典型例となっている。
【００６５】
［３］情報処理装置
図３及び図４は、本実施形態のテイント情報の伝搬を実現するための情報処理装置のブロック図を示す。図３及び図４に示す情報処理装置１は、プロセッサ１０、メモリ（記憶部）２０、入力部３０、出力部４０を具備している。プロセッサ１０は、読み出し検出手段１１、書き込み検出手段１２、テイント・ビット付加手段１３、検査手段１４を具備する。メモリ２０は、外部から入力されたテイント情報が付加された文字列データが記憶される第１の記憶部２１、処理が実行された後の文字列データが記憶される第２の記憶部２２を備えている。なお、第１の記憶部２１、第２の記憶部２２は、分離されているメモリにそれぞれ記憶されていてもよい。
【００６６】
本実施形態の情報処理装置１では、次のような情報処理を行う。
【００６７】
まず、情報処理装置１の外部から入力部３０にデータが入力される。このデータはプロセッサ１０に入力され、テイント・ビット付加手段１３によりデータに含まれる各データに対してテイント・ビットがそれぞれ付加された（セットされた）状態で、第１の記憶部２１に記憶される。
【００６８】
プログラムが実行される際、プロセッサ１０は第1の記憶部２１から読み出しを行い、第２の記憶部２２に書き込みを行う。この際、読み出し検出手段１１により、テイント・ビットがセットされたデータ（テイント・データ）に対する読み出しＲが検出され、書き込み検出手段１２により、文字列データＤに含まれるデータｄ’の書き込みＷが検出される。
【００６９】
ここで、テイント・データｄ１に対する第１の読み出しＲ１、上記文字列データＤに含まれるデータｄ１’の第１の書き込みＷ１、テイント・データｄ２に対する第２の読み出しＲ２、上記文字列データＤに含まれるデータｄ２’の第２の書き込みＷ２が順に検出された場合、上記第１の書き込みＷ１のデータｄ１’及び上記第２の書き込みＷ２のデータｄ２’に対してテイント・ビット付加手段によりテイント・ビットを付加して（セットして）第２の記憶部２２に記憶する。
【００７０】
そして、第２の記憶部２２に記憶されたデータを出力部４０から読み出す場合、プロセッサ１０の検査手段１４によって、出力データがテイント・データか否かの検査が行われる。
【００７１】
なお、上述した情報処理において、第１の書き込みＷ１におけるデータｄ１’は、第１の読み出しＲ１におけるテイント・データｄ１でもよいし、テイント・データｄ１以外でもよい。同様に、第２の書き込みＷ２におけるデータｄ２’は、第２の読み出しＲ２におけるテイント・データｄ２でもよいし、テイント・データｄ２以外でもよい。第１及び第２の書き込みＷ１、Ｗ２におけるデータｄ１’、ｄ２’は、上記文字列データＤの任意の２つの部分に対するものであり、このデータｄ１’、ｄ２’は、文字列データＤの任意の連続する部分であっても連続しない部分であってもよい。
【００７２】
また、第１及び第２の読み出しＲ１、Ｒ２のデータは、文字列データに限定されない。第１及び第２の読み出しＲ１、Ｒ２のデータは、同じものであっても異なるものであってもよい。
【００７３】
また、本実施形態の情報処理装置１は、図５に示すように、文字列アクセス検出部５０をさらに具備してもよい。この文字列アクセス検出部５０は、プロセッサ１０が実行する読み出し／書き込み（ロード／ストア）命令の時系列からなるアドレス・トレースを入力として、そこから文字列アクセスを成す部分系列を検出するものである。
【００７４】
具体的には、図６に示すように、文字列アクセス検出部５０によって、文字列データであるか否かが判断される（ＳＴ１）。この結果、文字列データである場合は、テイント情報の伝搬を行う対象か否かが判断され（ＳＴ２）、対象に該当すればテイント情報の伝搬が行われる（ＳＴ３）。一方、文字列データでない場合、テイント情報の伝搬を行う対象でない場合には、テイント情報の伝搬は行われない（ＳＴ４）。なお、テイント情報の伝搬を行う対象か否かの判断は、上述したように、プロセッサ１０によって判断される。
【００７５】
このような文字列アクセス検出部５０を利用すれば、プロセッサ１０やＶＭなどのプラットフォームに、本実施形態を実装可能である。なお、スクリプト言語処理系など、文字列アクセスが容易に識別可能である場合には、この文字列アクセス検出器を用いる必要はない。ここで、文字列アクセス検出部５０の機能をプロセッサ１０により実施させるとしてもよい。
【００７６】
なお、上述した本実施形態のテイント情報の伝搬などの情報処理は、情報処理装置１のプロセッサ１０によって実現したり、例えばコンピュータに実現させることのできるプログラム６１としても適用可能である（図３及び図５参照）。このプログラム６１は、例えば、磁気ディスク、光ディスク、半導体メモリなどの記録媒体６０に書き込んで各種装置に適用したり、通信媒体により伝送したりして各種装置に適用することも可能である。記録媒体６０に記録されたプログラム６１を読み込み、このプログラム６１によって動作が制御されることにより、上述した本実施形態の情報処理を実行する。
【００７７】
［４］効果
以上のように、本実施形態によれば、文や命令などのミクロな処理を単位として伝搬していた従来と異なり、プロセッサによる文字列操作毎にテイント情報を伝搬する。したがって、テイント情報の高精度な伝搬が実現でき、注入攻撃の検出漏れや誤検出を抑制することができるため、攻撃耐性の高いサーバ構築が可能となる。
【００７８】
また、本実施形態は、ＤＩＦＴのように言語非依存性であるため、プロセッサやＶＭなどのプラットフォーム側に実装可能である。したがって、プラットフォームがアタック耐性を有するため、アプリケーション開発時にはセキュリティ・ホールなどについて考慮する必要がなくなる。
【００７９】
（第２の実施形態）
本実施形態に係る情報処理装置は、上記１の実施形態に係る情報処理装置と異なるアルゴリズムを用いてテイント情報の伝搬を行う。
【００８０】
図７は、本実施の形態に係る情報処理装置の構成の一例を示すブロック図である。
【００８１】
本実施の形態に係るアルゴリズムでは、プロセッサ１０は、第１の記憶部２１に記憶されているテイント情報の付されている文字列データの読み出しイベントと、第２の記憶部２２に対する文字列データの書き込みイベントとの間に互い違い（インタリービング）の関係が発生しているか否か判断する。
【００８２】
そして、プロセッサ１０は、テイント情報付き文字列データの読み出しイベントに対して互い違いに発生している書き込みイベントによって第２の記憶部２２に記憶される文字列データに、テイント情報を付す。
【００８３】
具体的なアルゴリズムを以下で説明する。
【００８４】
本実施の形態に係るアルゴリズムにおいて、
ｔはｔ≧２のしきい値、
k≧１、
mk1，mk2，…，mkt≧１、
n1，n2，…，nt≧１、
である。
【００８５】
文字列Ｗに対する書き込みの系列に対して文字列Ｒkに対する読み出しの系列があって、
文字列Ｗに対する書き込みの系列を
ｗ_1_1，ｗ_1_2，…，ｗ_1_n1，
ｗ_2_1，ｗ_2_2，…，ｗ_2_n2，
…
ｗ_t_1，ｗ_t_2，…，ｗ_t_nt，
…
とし、
文字列Ｒkに対する読み出しの系列を
rk_1_1，rk_1_2，…，rk_1_mk1，
rk_2_1，rk_2_2，…，rk_2_mk2，
…
rk_t_1，rk_t_2，…，rk_t_mkt，
…
とすると、
これらの書き込みの系列及び読み出しの系列が、
rk_1_1，rk_1_2，…，rk_1_mk1，
ｗ_1_1，ｗ_1_2，…，ｗ_1_n1，
rk_2_1，rk_2_2，…，rk_2_mk2，
ｗ_2_1，ｗ_2_2，…，ｗ_2_n2，
…
rk_t_1，rk_t_2，…，rk_t_mkt，
ｗ_t_1，ｗ_t_2，…，ｗ_t_n2
…
となる互い違いの関係を持つ場合、
i（i≧１）に対して、
r1_i_m1i，r2_i_m2i，…
の中で最後に現れた読み出しイベントに対応するテイント情報を
ｗ_i_1，ｗ_i_2，…，ｗ_i_ni
の書き込みイベントに対して伝搬させる。
【００８６】
情報処理装置７０に備えられているプロセッサ１０は、上記のようなアルゴリズムを実現するためのプログラム６２を記録媒体６０から読み出して実行する。
【００８７】
これにより、プロセッサ１０は、テイント情報判断部７１、読み出し系列検出部７２、書き込み系列検出部７３、インタリービング判断部７４、テイント情報付加部７５として機能する。
【００８８】
テイント情報判断部７１は、第１の記憶部２１に記憶されている読み出し対象の文字列データに、テイント情報が付与されているか否か判断する。
【００８９】
読み出し系列検出部７２は、テイント情報判断部７１の判断結果に基づいて、第１の記憶部２１から、テイント情報が付加されている文字列データの読み出し系列を検出する。読み出し系列は、第１の記憶部２１に記憶されておりテイント情報が付加されている文字列データに対する複数の読み出しイベントを含む。また、読み出し系列検出部７２は、テイント情報が付加されている文字列データに対する複数の読み出しイベントの発生タイミングを検出、記録、管理する。
【００９０】
書き込み系列検出部７３は、第２の記憶部２２に対して書き込み対象のデータを記憶するための書き込み系列を検出する。書き込み系列は、第２の記憶部２２に書き込まれるデータに対する複数の書き込みイベントを含む。また、書き込み系列検出部７３は、第２の記憶部２２に書き込まれるデータに対する複数の書き込みイベントの発生タイミングを検出、記録、管理する。
【００９１】
インタリービング判断部７４は、読み出し系列検出部７２によって検出された読み出し系列とその発生タイミングと、書き込み系列検出部７３によって検出された書き込み系列とその発生タイミングとに基づいて、それぞれが読み出し系列に含まれており１つ又は連続する複数の読み出しイベントを含む複数の読み出しイベントグループと、それぞれが書き込み系列に含まれており１つ又は連続する複数の書き込みイベントを含む複数の読み出しイベントグループとの間で、互い違いの関係を満たすか否か判断する。
【００９２】
例えば、テイント情報が付加されていると判断された文字列データに関する読み出し系列は、１つ又は連続する複数の読み出しイベントを含む第１の読み出しイベントグループを含み、その後に、１つ又は連続する複数の読み出しイベントを含む第２の読み出しイベントグループを含み、同様の状態が繰り返されているとする。
【００９３】
また、例えば、書き込み系列は、１つ又は連続する複数の書き込みイベントを含む第１の書き込みイベントグループを含み、その後に、１つ又は連続する複数の書き込みイベントを含む第２の書き込みイベントグループを含み、同様の状態が繰り返されているとする。
【００９４】
この場合、インタリービング判断部７４は、第１の読み出しイベントグループの後に、第１の書き込みイベントグループが発生し、この第１の書き込みイベントグループの後において、さらに第２の読み出しイベントグループの後に、第２の書き込みイベントグループが発生する状態を、前記互い違いの関係が発生している状態と判断する。その後も、インタリービング判断部７４は、処理対象の読み出しイベントグループと処理対象の書き込みイベントグループとをずらしながら同様の判断処理を繰り返す。
【００９５】
上記の読み出し系列検出部７２の検出処理、書き込み系列検出部７３の検出処理、インタリービング判断部７４の判断処理は、例えば、各種の判断文などの制御文を組み合わせることで実現されるとしてもよく、各種のパターン認識技術、パターンの分類手法などを用いるとしてもよい。
【００９６】
テイント情報付加部７５は、インタリービング判断部７４によってテイント情報が付加されている文字列データに関する互い違いの読み出し及び書き込みが発生していると判断された場合に、書き込み対象の文字列データにテイント情報を付加する。
【００９７】
例えば、テイント情報付加部７５は、第１の書き込みイベントグループと第２の書き込みイベントグループとに対して互い違いが発生していると判断された場合に、この第１の書き込みイベントグループに含まれている書き込みイベントによって書き込まれる文字列データのすべてと、第２の書き込みイベントグループに含まれている書き込みイベントによって書き込まれる文字列データのすべてに対して、テイント情報を付加する。
【００９８】
例えば、テイント情報付加部７５は、テイント情報を付与する書き込みイベントが複数の読み出しイベントに基づいて発生している場合に、これら複数の読み出しイベントのうち最後に発生した読み出しイベントに対する追跡情報を、書き込み対象の文字列データに付与する。
【００９９】
図８は、本実施の形態に係るアルゴリズムによってテイント情報が伝搬される状態の第１の例を示す図である。
【０１００】
この図８においては、横方向は、読み出しイベント及び書き込みイベントの発生する時間を表す。縦方向は、読み出し文字列データ及び書き込み文字列データの種別を表す。この図８において、矢印は、テイント情報の伝搬を表している。
【０１０１】
この図８では、読み出し文字列データＲに対して、読み出しイベントr1_1_1，…，r1_5_1を含む読み出し系列が発生している。
【０１０２】
この図８において、複数の読み出しイベントグループ（r1_1_1），…，（r1_5_1）は、それぞれが一つの読み出しイベントr1_1_1，…，r1_5_1を含むとする。
【０１０３】
図８では、書き込み文字列データＷに対して、書き込みイベントw_1_1，…，w_5_1を含む書き込み系列が発生している。
【０１０４】
この図８において、複数の書き込みイベントグループ（w_1_1），…，（w_5_1）は、それぞれが一つの書き込みイベントw_1_1，…，w_5_1を含むとする。
【０１０５】
それぞれの発生タイミングから、各読み出しイベントグループ（r1_1_1），…，（r1_5_1）と各書き込みイベントグループ（w_1_1），…，（w_5_1）とは、互い違いの関係を満たしている。すなわち、読み出しイベントグループ（r1_1_1），…，（r1_5_1）と書き込みイベントグループ（w_1_1），…，（w_5_1）とは、交互のタイミングで発生する関係を満たしている。
【０１０６】
そこで、書き込み文字列データＷに対する書き込みイベントグループ（w_1_1），…，（w_5_1）内の書き込みイベントに対しては、それぞれの書き込みイベントグループにとって互い違いの関係にある直前の読み出しイベントグループに属する最終（最新）の読み出しイベントに対応するテイント情報が、書き込み文字列データに対して付与される。
【０１０７】
図９は、本実施の形態に係るアルゴリズムによってテイント情報が伝搬される状態の第２の例を示す図である。
【０１０８】
この図９では、読み出し文字列データＲに対して、読み出しイベントr1_1_1，r1_2_1，r1_2_2，…，r1_4_1を含む読み出し系列が発生している。
【０１０９】
この図９において、複数の読み出しイベントグループは、それぞれ（r1_1_1），（r1_2_1，r1_2_2），（r1_3_1，r1_3_2，r1_3_3），（r1_4_1）である。
【０１１０】
図９では、書き込み文字列データＷに対して、書き込みイベントw_1_1，w_2_1，w_2_2，…，w_4_3を含む書き込み系列が発生している。
【０１１１】
この図９において、複数の書き込みイベントグループは、それぞれ（w_1_1），（w_2_1，w_2_2），（w_3_1，w_3_2），（w_4_1，w_4_2，w_4_3）である。
【０１１２】
それぞれの発生タイミングから、各読み出しイベントグループ（r1_1_1），（r1_2_1，r1_2_2），（r1_3_1，r1_3_2，r1_3_3），（r1_4_1）と各書き込みイベントグループ（w_1_1），（w_2_1，w_2_2），（w_3_1，w_3_2），（w_4_1，w_4_2，w_4_3）とは、互い違いの関係を満たしている。すなわち、読み出しイベントグループ（r1_1_1），（r1_2_1，r1_2_2），（r1_3_1，r1_3_2，r1_3_3），（r1_4_1）と書き込みイベントグループ（w_1_1），（w_2_1，w_2_2），（w_3_1，w_3_2），（w_4_1，w_4_2，w_4_3）とは、交互のタイミングで発生する関係を満たしている。
【０１１３】
そこで、書き込みイベントグループ（w_1_1），（w_2_1，w_2_2），（w_3_1，w_3_2），（w_4_1，w_4_2，w_4_3）内の書き込みイベントに対しては、それぞれの書き込みイベントグループにとって互い違いの関係にある直前の読み出しイベントグループに属する最終（最新）の読み出しイベントに対応するテイント情報が、書き込み文字列データに対して付与される。
【０１１４】
図１０は、本実施の形態に係るアルゴリズムによってテイント情報が伝搬される状態の第３の例を示す図である。
【０１１５】
読み出し文字列データＲ１に対して、読み出しイベントr1_1_1，r1_2_1，r1_3_1，r1_3_2，r1_4_1を含む読み出し系列が発生している。
【０１１６】
読み出し文字列データＲ１の読み出し系列における複数の読み出しイベントグループは、それぞれ（r1_1_1），（r1_2_1），（r1_3_1，r1_3_2），（r1_4_1）である。
【０１１７】
読み出し文字列データＲ２に対して、読み出しイベントr2_1_1，r2_2_1，r2_3_1，r2_4_1を含む読み出し系列が発生している。
【０１１８】
読み出し文字列データＲ２の読み出し系列における複数の読み出しイベントグループは、それぞれ（r2_1_1），（r2_2_1），（r2_3_1），（r2_4_1）である。
【０１１９】
書き込み文字列データＷに対して、書き込みイベントw_1_1，w_2_1，w_3_1，w_4_1，w_4_2を含む書き込み系列が発生している。
【０１２０】
複数の書き込みイベントグループは、それぞれ（w_1_1），（w_2_1），（w_3_1），（w_4_1，w_4_2）である。
【０１２１】
それぞれの発生タイミングから、読み出し文字列データＲ１についての各読み出しイベントグループ（r1_1_1），（r1_2_1），（r1_3_1，r1_3_2），（r1_4_1）と書き込み文字列データＷについての各書き込みイベントグループ（w_1_1），（w_2_1），（w_3_1），（w_4_1，w_4_2）とは、互い違いの関係を満たしている。
【０１２２】
さらに、読み出し文字列データＲ２についての各読み出しイベントグループ（r2_1_1），（r2_2_1），（r2_3_1），（r2_4_1）と書き込み文字列データＷについての各書き込みイベントグループ（w_1_1），（w_2_1），（w_3_1），（w_4_1，w_4_2）とについても、互い違いの関係を満たしている。
【０１２３】
そこで、書き込みイベントグループ（w_1_1），（w_2_1），（w_3_1），（w_4_1，w_4_2）内の書き込みイベントに対しては、読み出し文字列データＲ１，Ｒ２の読み出しイベントグループのうち、書き込みイベントグループとの間で互い違いの関係にある直前の読み出しイベントグループに属する最終（最新）の読み出しイベントに対応するテイント情報が、書き込み文字列データに対して付与される。
【０１２４】
この図１０の例では、読み出しイベントr2_1_1に対するテイント情報が、書き込みイベントw_1_1に対する文字列データに付与される。読み出しイベントr1_2_1に対するテイント情報が、書き込みイベントw_2_1に対する文字列データに付与される。読み出しイベントr1_3_2に対するテイント情報が、書き込みイベントw_3_1に対する文字列データに付与される。読み出しイベントr2_4_1に対するテイント情報が、書き込みイベントw_4_1，w_4_2に対する文字列データに付与される。
【０１２５】
図１１は、本実施の形態に係るアルゴリズムによってテイント情報が伝搬される状態の第４の例を示す図である。
【０１２６】
読み出し文字列データＲ１に対して、読み出しイベントr1_1_1，r1_2_1を含む読み出し系列が発生している。
【０１２７】
読み出し文字列データＲ１の読み出し系列における複数の読み出しイベントグループは、それぞれ（r1_1_1），（r1_2_1）である。
【０１２８】
読み出し文字列データＲ２に対して、読み出しイベントr2_1_1，r2_1_2，r2_1_3，r2_1_4を含む読み出し系列が発生している。
【０１２９】
書き込み文字列データＷに対して、書き込みイベントw_1_1，w_2_1を含む書き込み系列が発生している。
【０１３０】
複数の書き込みイベントグループは、それぞれ（w_1_1），（w_2_1）である。
【０１３１】
それぞれの発生タイミングから、読み出し文字列データＲ１についての各読み出しイベントグループ（r1_1_1），（r1_2_1）と書き込み文字列データＷについての各書き込みイベントグループ（w_1_1），（w_2_1）とは、互い違いの関係を満たしている。
【０１３２】
しかしながら、読み出し文字列データＲ２に対する読み出し系列と、書き込み文字列データＷに対する書き込み系列とでは、互い違いの関係を満たしていない。
【０１３３】
そこで、書き込みイベントグループ（w_1_1），（w_2_1）内の書き込みイベントに対しては、読み出し文字列データＲ１の読み出しイベントグループのうち、書き込みイベントグループとの間で互い違いの関係にある直前の読み出しイベントグループに属する最終（最新）の読み出しイベントに対応するテイント情報が、書き込み文字列データに対して付与される。
【０１３４】
この図１１の例では、読み出しイベントr1_1_1に対するテイント情報が、書き込みイベントw_1_1に対する文字列データに付与される。読み出しイベントr1_2_1に対するテイント情報が、書き込みイベントw_1_2に対する文字列データに付与される。
【０１３５】
上記のように、本実施形態では、テイント情報を付加されている文字列データに対する少なくとも一回の読み出しイベントの発生後に少なくとも１回の書き込みイベントが発生し、さらにその後に、このテイント情報を付加されている文字列データに対する少なくとも一回の読み出しイベントの発生後に少なくとも１回の書き込みイベントが発生した場合に、互い違いが発生していると判断される。そして、同様の判断が繰り返される。
【０１３６】
テイント情報を伝搬させる場合には、その書き込みの直前の少なくとも1回の読み出しにおける最終の読み出しに基づいてテイント情報が伝搬される。
【０１３７】
以上説明した本実施形態においては、外部から入力された文字列データに基づいて情報処理装置７１内で生成された文字列データについても、精度よくテイント情報を伝搬させることができる。これにより、攻撃耐性の高い情報処理装置７１を構築することができる。
【０１３８】
（第３の実施の形態）
本実施形態においては、テイント情報の伝搬を実現する具体的なアルゴリズムについて、文字列アクセスの検出と、この文字列アクセスの検出を用いた伝播とに分けて説明する。
【０１３９】
［文字列アクセスの検出］
ここでは、文字列アクセスを検出するための文字列検出器の動作について説明する。この文字列検出器は、与えられたアドレスに対して、以下の２つの情報を出力する。なお、この文字列検出器は、プロセッサによって実現されるとしてもよい。
【０１４０】
１．該当アクセスが文字列であるか否か
２．バックトラック（後に説明）が必要であるか否か
文字列検出器は、文字列に対するロードとストアをそれぞれ検出するために２つ備えられている。２つの文字列検出器は、それぞれが共通したアルゴリズムにより文字列アクセスを検出する。
【０１４１】
それぞれの文字列検出器は、文字列検出テーブルを用いて文字列の検出を行う。図１２に、この文字列検出テーブル内の各エントリの要素を示す。文字列検出テーブル内の各エントリは、それぞれが一つの文字列アクセスに関わる情報を保持する。
【０１４２】
［エントリの更新と検出］
文字列アクセスの検出は、ロード命令、及びストア命令が実行された際、以下で説明する動作を、それぞれの文字列検出器に備えられている文字列検出テーブル内の全エントリに対して行うことによって実現される。
【０１４３】
図１３は、本実施の形態に係る文字列検出動作の一例を示すフローチャートである。この図１３の文字列検出動作は、文字列検出テーブルのエントリ毎に行われる。
【０１４４】
まず、ステップＳ１−０において、アクセスが行われた際のアドレスと予測アドレス（next_adr）の比較が行われる。これらのアドレスが一致しなかった場合，該当エントリに対する処理は終了する。
【０１４５】
ステップＳ１−０でアドレスが一致した場合、ステップＳ１−１において、アクセスのインクリメント・フラグ（paired_inc）が１に更新され、ステップＳ１−２において、アクセス回数（cnt）と予測アドレス（next_adr）がインクリメントされる。
【０１４６】
次に，ステップＳ１−３において、アクセス回数（cnt）が一定のしきい値CNを超えているか否かの判定が行われる。アクセ回数cntがしきい値CNを超えていた場合には、ステップＳ１−４において、アクセスがロードであった場合はストアを検出する検出器にアクセスの通知が行われ、アクセスがストアであった場合はロードを検出する検出器にアクセスの通知が行われる。通知を行われた側の動作については後述する。
【０１４７】
続いて，ステップＳ１−５において、アクセス回数（cnt）が一定のしきい値CSを超えているか否かの判定が実行される。ここで、アクセス回数cntがしきい値CSを超えていない場合は、該当エントリに対する処理は終了する。アクセス回数cntがしきい値CSを超えていた場合、ステップＳ１−６において、さらに対となる文字列のアクセス回数（paired_cnt）が一定の閾値CPを超えているか否かの判定が行われる。アクセス回数paired_cntが閾値CPを超えていない場合、該当エントリに対する処理は終了する。
【０１４８】
上記のステップＳ１−６において、アクセス回数paired_cntが閾値CPを超えていた場合、続いて、ステップＳ１−７において、文字列フラグ（string）が１か否かの判定が行われる。ここで，stringが０の場合、ステップＳ１−８において、バックトラック要求が出力される。
【０１４９】
その後、ステップＳ１−９において、該当アクセスを文字列として検出した旨が出力され，文字列フラグ（string）が１に更新される。
【０１５０】
［エントリの追加］
上記ステップＳ１−０において、メモリ・アクセスにおけるアドレスと一致する予測アドレス（next_adr）を持つエントリがテーブル内に1つも存在しなかった場合、テーブルへ新しいエントリが追加される。この場合、追加されるエントリ内の各要素は，以下の様に初期化される．
base_adr：該当アクセスのアドレスに初期化される
next_adr：base_adr+1に初期化される
cnt     ：１に初期化される
他の全ての要素：０に初期化される
なお，テ−ブルの大きさは有限であるため、もしエントリが不足した場合には、ＬＲＵアルゴリズムに基づいた置き換えが行われる。
【０１５１】
［対となる文字列検出器からの通知］
上記のステップＳ１−４で行われるアクセスの通知について、この通知を受けた側の動作の一例を図１４に示す。この動作は、通知を受けた側の検出器内にある文字列検出テーブルのエントリ全てに対して行われる。この図１４の動作は、例えばプロセッサによって実行される。
【０１５２】
まず、ステップＳ２−０において、対となるアクセスのインクリメント・フラグ（paired_inc）が１であるか否かの判定が行われる。インクリメント・フラグpaired_incが０の場合、該当エントリに対する処理は終了する。
【０１５３】
ステップＳ２−０において、インクリメント・フラグpaired_incが１であった場合、ステップＳ２−１において、対となるアクセスのインクリメント・フラグ（paired_inc）が０に更新され、ステップＳ２−２において、対となる文字列のアクセス回数（paired_cnt）がインクリメントされる。
【０１５４】
［伝搬］
テイント情報の伝搬は、ロード命令およびストア命令が実行された際の動作によって実現される。これらの動作は，先に説明したロード用およびストア用の文字列検出器からの出力に基づいて、例えばプロセッサなどによって行われる。ロード用およびストア用の文字列検出器は、例えばプロセッサに含まれていてもよく、プロセッサとは別構成でもよい。
【０１５５】
［ロード命令が実行された際の動作］
図１５は、ロード命令が実行された場合の動作の一例を示すフローチャートである。
【０１５６】
まず、ステップＳ３−０において、文字列検出器は、該当アクセスが文字列かどうか判定する。該当アクセスが文字列ではない場合、ここで処理は終了する。
【０１５７】
該当アクセスが文字列の場合、ステップＳ３−１において、そのアドレスに対応するテイント情報がロードされ、保存される。
【０１５８】
なお、上記ステップＳ３−１は、例えばプロセッサによって実行される。
【０１５９】
［ストア命令が実行された際の動作］
図１６は、ストア命令が実行された場合の動作の一例を示すフローチャートである。
【０１６０】
まず、ステップＳ４−０において、文字列検出器は、該当アクセスが文字列に対するものであるか否か判定する。該当アクセスが文字列ではない場合、ここで処理は終了する。
【０１６１】
該当アクセスが文字列の場合、テイント情報のストアが行われる。すなわち、ステップＳ４−１において、文字列データへのロード時（図１５のステップＳ３−１）に保存されたテイント情報が、対応するアドレスに対してストアされる。次に、ステップＳ４−２において、文字列検出器から出力されるバックトラック要求の判定が行われ、要求が存在した場合には、ステップＳ４−３において、後述するバックトラックによる伝搬が行われる。
【０１６２】
なお、上記ステップＳ４−１からステップＳ４−３は、例えばプロセッサによって実行される。
【０１６３】
［バックトラックによる伝搬］
上記図１６のステップＳ４−２において、文字列検出器よってバックトラック要求が出力された場合、以下に示す「2．入力アドレス」から「3．出力アドレス」に対し，「1．伝搬を行うサイズ」で指定されたサイズの伝搬が行われる。なお、この伝搬は、例えばプロセッサによって実行される。
【０１６４】
1．伝搬を行うサイズ：ステップＳ４−０において検出された文字列に対応するエントリ内のアクセス回数（cnt）
2．入力アドレス：直前に検出された文字列へのロードにおける先頭アドレス（base_adr）
3．出力アドレス：ストア時のアドレスから，上記「1．伝搬を行うサイズ」を引いたアドレス
その他、本発明は、上記各実施形態に限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で、種々に変形することが可能である。さらに、上記実施形態には種々の段階の発明が含まれており、開示される複数の構成要件における適宜な組み合わせにより種々の発明が抽出され得る。例えば、上記各実施形態に示される全構成要件から幾つかの構成要件が削除されても、発明が解決しようとする課題の欄で述べた課題が解決でき、発明の効果の欄で述べられている効果が得られる場合には、この構成要件が削除された構成が発明として抽出され得る。
【０１６５】
本発明は、言語処理系などのソフトウェアから、ＶＭ、プロセッサなどのプラットフォームまで、あらゆるレベルのテイント情報の伝搬方法として利用可能である。
【符号の説明】
【０１６６】
１，７０…情報処理装置、１０…プロセッサ、１１…読み出し検出手段、１２…書き込み検出手段、１３…テイント・ビット付加手段、１４…検査手段、２０…メモリ、２１…第１の記憶部、２２…第２の記憶部、３０…入力部、４０…出力部、５０…文字列アクセス検出部、６０…記録媒体、６１，６２…プログラム、７１…テイント情報判断部、７２…読み出し系列検出部、７３…書き込み系列検出部、７４…インタリービング判断部、７５…テイント情報付加部。
【図１】
2010102679.tif 000003
【図２】
2010102679.tif 000004
【図３】
2010102679.tif 000005
【図４】
2010102679.tif 000006
【図５】
2010102679.tif 000007
【図６】
2010102679.tif 000008
【図７】
2010102679.tif 000009
【図８】
2010102679.tif 000010
【図９】
2010102679.tif 000011
【図１０】
2010102679.tif 000012
【図１１】
2010102679.tif 000013
【図１２】
2010102679.tif 000014
【図１３】
2010102679.tif 000015
【図１４】
2010102679.tif 000016
【図１５】
2010102679.tif 000017
【図１６】
2010102679.tif 000018