(57)【要約】  デバイス上において実行されるプログラムを、予期せぬメモリ領域へプログラム実行をジャンプさせるデバイス不具合および電圧スパイクなどの物理的妨害によって生じる実行フローエラーから、少なくともある程度保護する。実行される上記プログラムは、複数の領域（B’[m]、B’[f]）を通る実行パスに従う。第１の検査値（wisb）は、ランダムにアクセス可能なメモリ領域に提供される。少なくとも一度（例えばTERM[m]において）は、少なくとも１つの領域（B’[m]）において、上記第１の検査値（wisb）が上記領域（B’[m]）に対する予想値（s[m]）を有しているかが判別される。上記第１の検査値（wisb）は、第１の領域（B’[m]）から、上記のような判別が成される第２の領域（B’[f]）へと実行が進むときに、上記第２の領域（B’[f])において予想される値（s[f]）を有するように更新される。エラー処理手順は、上記判別が否定的であった場合に行われる。【選択図】図１
2009525509.tif 000002
【特許請求の範囲】
【請求項１】
複数の領域を介して進む実行パスに従ってデバイス上において実行されるプログラムを、予期しないメモリ領域へプログラム実行をジャンプさせるデバイス不具合および電圧スパイクのような物理的妨害によって生じる実行フローエラーから、少なくともある程度は保護する方法であって、
ランダムにアクセス可能なメモリ領域に第１の検査値を設ける工程と、
少なくとも１つの領域において少なくとも一回は、上記第１の検査値が当該領域に対する予想値を有しているか否か否かを判別する工程と、
第１の領域から、上記のような判別が成される第２の領域へと実行が進むときに、上記第１の検査値を、上記第２の領域において予想される値を有するように更新する工程と、
上記のような判別が否定的であった場合にエラー処理手順を行う工程とを含んでいる方法。
【請求項２】
上記の判別工程を、クリティカルな性質（critical nature）を有する上記プログラムの少なくとも一部の演算の前に行う工程を含んでいる請求項１に記載の方法。
【請求項３】
上記の判別工程を、上記検査値更新工程の少なくとも一部の前に行う工程を含んでいる請求項１に記載の方法。
【請求項４】
上記の判別工程を、上記デバイスの持続ストレージを更新する上記プログラムの少なくとも一部の演算の前に行う工程を含んでいる請求項１、２または請求項３に記載の方法。
【請求項５】
上記の判別工程を、上記デバイスの外部または上記デバイスの保護領域の外部にデータを送信させる少なくとも一部の演算の前に行う工程を含んでいる請求項１、２または請求項３に記載の方法。
【請求項６】
ランダムにアクセス可能なメモリ領域に第２の検査値を設ける工程と、
領域が、コール領域からコールされるコードの機能ユニットを有している場合は、リターン領域に実行を戻す工程と、
実行が上記機能ユニット外に進む前に、上記機能ユニットに対して予想される最終値を有するように、第２の検査値を更新する工程と、
実行が上記機能ユニット外に進んだ後および実行が上記リターン領域に戻る前に、上記第２の検査値が上記予想される最終値を有しているか否かを判別する工程とを含んでいる請求項１、２または３に記載の方法。
【請求項７】
上記リターン領域は上記コール領域と同一である請求項６に記載の方法。
【請求項８】
上記第２の検査値は、同一のランダムにアクセス可能なメモリ領域を用いて、上記第１の検査値と同一であり、
上記第２の領域において予想される上記値を有するように上記第１の検査値が更新される前に、上記第２の検査値が、上記予想される最終値を有しているか否か否かを判別する工程を含んでいる請求項６に記載の方法。
【請求項９】
上記第２の領域に実行が進む前に上記更新工程が行われる上記第１の領域に実行が進むときに、上記第１の領域において予想される値を有するように上記第１の検査値を更新する工程を含んでいる請求項１、２または３に記載の方法。
【請求項１０】
上記検査値が予想外の値を一旦推定すると、後の上記更新においても予想外の値を保持する可能性を有するように、上記検査値を更新する工程を含んでいる請求項１、２または３に記載の方法。
【請求項１１】
上記更新された検査値が上記更新前に上記第１の領域に対する上記予想値を有している場合に限り、上記更新された検査値が上記第２の領域に対する上記予想値を有するように、上記検査値を、上記第２の領域に対するその予想値および上記第１の領域に対するその予想値に基づいて更新する工程を含んでいる請求項１、２または３に記載の方法。
【請求項１２】
上記第１の領域に対する上記予想値から導き出される第１の調整、および上記第２の領域に対する上記予想値から導き出される第２の調整を効果的に適用することによって上記検査値を更新する工程を含んでおり、
上記第１の調整は、上記第２の調整に対して用いられる演算子に対して反比例関係（inverse relationship）にある演算子を用いる請求項１１に記載の方法。
【請求項１３】
上記第１の領域に対する上記予想値および上記第２の領域に対する上記予想値から導き出される中間値を演算することによって、上記第１の調整および第２の調整を共に適用する工程と、
演算された上記中間値から導き出される上記検査値に対して、単一の調整を適用する工程とを含んでいる請求項１２に記載の方法。
【請求項１４】
上記中間値は事前に演算される請求項１３に記載の方法。
【請求項１５】
上記第１の調整および第２の調整を上記検査値に別々に適用する工程を含んでいる請求項１２に記載の方法。
【請求項１６】
上記第２の調整は上記第１の調整の前に適用される請求項１５に記載の方法。
【請求項１７】
上記第１の調整のための上記演算子は減算演算であり、上記第２の調整のための上記演算子は加算演算である請求項１２に記載の方法。
【請求項１８】
上記第１の調整のための上記演算子は排他的論理和演算であり、上記第２の調整のための上記演算子は排他的論理和演算である請求項１２に記載の方法。
【請求項１９】
少なくとも一部の領域あるいは機能ユニットに対する上記各予想値は、上記プログラムコードから直接取り出される請求項１、２または３に記載の方法。
【請求項２０】
少なくとも一部の領域あるいは機能ユニットに対する上記各予想値を、異なるメモリ領域に記憶する工程と、
領域あるいは機能ユニットに対する上記予想値を、適切な上記メモリ領域から必要時に取り出す工程とを含んでいる請求項１、２または３に記載の方法。
【請求項２１】
少なくとも一部の予想値は乱数または擬似乱数である請求項１、２または３に記載の方法。
【請求項２２】
少なくとも一部の予想値は、各領域または機能ユニットのそれぞれに対応する上記メモリ領域の入力点から導き出される請求項１、２または３に記載の方法。
【請求項２３】
上記少なくとも一部の予想値をハッシュ技術を用いて導き出す工程を含んでいる請求項２２に記載の方法。
【請求項２４】
ランダムにアクセス可能なメモリ領域に第３の検査値を設ける工程と、
領域が、コール領域からコールされるコードの機能ユニットを有している場合は、上記コール領域に実行を戻す工程と、
実行が上記機能ユニットに進む前に、上記第３の検査値を、上記コールに関連する値を有するように更新する工程と、
少なくとも１つの上記機能ユニットから実行が戻った後に、上記第３の検査値が上記コールに関連する上記値を有しているか否か否かを判別する工程とを含んでいる請求項１、２または３に記載の方法。
【請求項２５】
上記第３の検査値判別工程を、実行が上記コール領域に戻る前に行う工程を含んでいる請求項２４に記載の方法。
【請求項２６】
上記コールに関連する量の調整を与えることによって、上記第３の検査値を更新する工程と、
上記調整を上記と同量だけ逆にすることによって上記第３の検査値が上記コール前調整が行われる前の値に戻るか否か否かを判別することによって、上記第３の検査値が上記コールに関連する上記値を保持しているか否かを、実行が戻った後に判別する工程とを含んでいる請求項２４に記載の方法。
【請求項２７】
上記第３の検査値を、上記コール前調整が行われる前の値に戻すために更新する工程を含んでいる請求項２４に記載の方法。
【請求項２８】
上記工程は、実行前に上記プログラム内に含まれていた命令によって行われる請求項１、２または３に記載の方法。
【請求項２９】
プログラム実行はプログラムカウンタによって制御される請求項１、２または３に記載の方法。
【請求項３０】
上記デバイスはセキュリティデバイスを含んでいる請求項１、２または３に記載の方法。
【請求項３１】
上記デバイスはスマートカードを含んでいる請求項１、２または３に記載の方法。
【請求項３２】
複数の領域を介して進む実行パスに従ってデバイス上において実行されるプログラムを、予期しないメモリ領域へプログラム実行をジャンプさせるデバイス不具合および電圧スパイクのような物理的妨害によって生じる実行フローエラーから、少なくともある程度は保護する方法であって、
ランダムにアクセス可能なメモリ領域に第１の検査値を提供する工程と、
少なくとも１つの領域において少なくとも一回は、上記第１の検査値が当該領域に対する予想値を有しているか否かを判別する工程と、
第１の領域から、上記の判別が成される第２の領域へと実行が進むときに、上記第１の検査値を、上記第２の領域において予想される値を有するように更新する工程と、
上記の判別が否定的であった場合にエラー処理手順を行う工程とを含むように、上記プログラムを変換する工程を含んでいる方法。
【請求項３３】
上記プログラムは、Ｃプログラミング言語のような高級プログラミング言語において特定される請求項３２に記載の方法。
【請求項３４】
上記プログラムをコンパイルして、実行のための機械コードを上記デバイスによって直接生成する工程を含んでいる請求項３２または３３に記載の方法。
【請求項３５】
予期しないメモリ領域へプログラム実行をジャンプさせるデバイス不具合および電圧スパイクのような物理的妨害によって生じる実行フローエラーから少なくともある程度は保護されるプログラムであって、複数の領域を介して進む実行パスに従って実行されるプログラムがロードされたデバイスであって、
ランダムにアクセス可能なメモリ領域に第１の検査値を提供する手段と、
少なくとも１つの領域において少なくとも一回は、上記第１の検査値が当該領域に対する予想値を有しているか否かを判別する手段と、
第１の領域から、上記のような判別が成される第２の領域へと実行が通過するときに、上記第１の検査値を、上記第２の領域において予想される値を有するように更新する手段と、
上記のような判別が否定的であった場合にエラー処理手順を行う手段とを含んでいるデバイス。
【請求項３６】
請求項１または３２に記載の方法を当該デバイスに実施させるために、上記デバイス上において実行されるプログラム。
【請求項３７】
請求項３５に記載の上記デバイスにロードされるプログラム。
【請求項３８】
キャリア媒体上において実行される請求項３６に記載のプログラム。
【請求項３９】
キャリア媒体上において実行される請求項３７に記載のプログラム。
【請求項４０】
上記キャリア媒体は伝送媒体または記憶媒体である請求項３８に記載のプログラム。
【請求項４１】
上記キャリア媒体は伝送媒体または記憶媒体である請求項３９に記載のプログラム。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
〔技術分野〕
本発明は、演算装置のための制御フロー保護機構に関する。
【０００２】
〔背景技術〕
ＣＰＵベースのデバイスは、記憶されたプログラムおよび記憶されたデータを用いて、その入力において動作し、出力を生成する。プログラムは、個別の命令から構成されている。これら個別の命令は、プログラマーが設計したプログラムロジックによって決定される順序で、ＣＰＵによって実行される。ＣＰＵは、フェッチまたは実行される次の命令が記憶されているアドレスを示す、プログラムカウンタ（ＰＣ）の概念を有している。プログラムカウンタは、ハードウェアレジスタと同一であると見なされる場合があるが、他の態様も存在する。命令が実行されると、プログラムカウンタは、次の命令を示すようにＣＰＵによって更新される。次の命令は、通常、（単純な命令または「非分岐」命令の場合は、)記憶されている前の命令の真上のメモリ領域に位置しており、あるいは、「分岐」ジャンプまたはコール型の命令の場合は専ら、別の場所に位置している。このモデルでは、割り込みは無視される。
【０００３】
セキュリティデバイス上で実行されるソフトウェアは、様々な種類の攻撃から保護されなければならない。このような攻撃の種類の１つとして、「故障利用」攻撃が挙げられる。故障利用攻撃は、通常ではない方法でデバイスを操作して誤動作させ、その誤動作によって、攻撃者の意図する影響をデバイスに及ぼさせるものである。故障利用攻撃の種類の１つとして、攻撃者は、電源またはＩ／Ｏポートに一時的な電圧スパイク（すなわち「グリッチ」）を生じさせ、あるいはＣＰＵ  ＩＣに明るい閃光を与える。これによって、（他の効果の中でもとりわけ、）プログラムカウンタが予期しないアドレスへ変更され、コード実行はそのアドレスから続けられる。従って、プログラマーの予期せぬ順序でプログラムが実行される。攻撃者は、デバイスに機密情報を露呈させるために適したグリッチを見つけ出す、あるいは、セキュリティ検査を巧みに回避するなどを辛抱強く行う。これらが機能するとは考えにくいが、事実上の現実的な攻撃技術である。
【０００４】
例えば、プログラマーは、関数“make＿credit()”を与える。これは、セキュリティ検査（例えば、ＰＩＮ検査およびパラメータ検査）を通過した後にのみコールされる関数である。攻撃者は、プログラムカウンタをコード内の別の場所からmake＿credit(）へジャンプさせることができた場合、ＰＩＮ検査を受けることなくcreditを加えることができる。同様の別の攻撃では、機密内部データが、デバイスの出力チャネルに誤ってコピーされる場合がある。このように一旦デバイス情報が漏洩すると、その攻撃パラメータを用いて他の同様のデバイス（あるいは、別の機会に同一のデバイス)への攻撃を複製することも可能となる。
【０００５】
同様の考えは、例えば宇宙線あるいは他の偶発的な事象（デバイス部品の不具合など）によってもたらされる、不注意によるプログラムカウンタの一時的変更にも当てはまる。セキュリティシステムだけではなく、セーフティクリティカルおよびミッションクリティカルなシステムもまた危険に曝されている。
【０００６】
予期せぬメモリ領域にプログラム実行をジャンプさせる、上述した全ての種類のグリッチ、およびデバイスに影響を及ぼす他の物理的要因（例えばデバイス不具合）を、ここでは一般的に「物理的妨害」と称する。
【０００７】
ＵＳ５，２７４，８１７（キャタピラー社）は、サブルーチンコールを実行する方法を開示している。当該方法では、サブルーチンコールに、検査アドレスがスタックに記憶される。サブルーチンコールは、サブルーチンが、コールしたルーチンに戻る前に確認される。これによって、プログラムカウンタ値に誤りを生じさせる偶発的な妨害に対して、ある程度の保護を加えることができる。しかし、開示されている当該方法は、不正確な関数のコールを防止していない場合がある。例えば、保護されたコールを意図する関数にセットアップするスタックプッシュ演算（stack push operation）の直前から、保護されたコールを意図せぬ関数にセットアップするスタックプッシュ演算の直前に実行がジャンプした場合、呼び出された（意図せぬ）関数において誤りが認識されない。
【０００８】
ＪＰ４１１１１３８（富士通）は、ハードウェア検出システムに依存して、プログラムカウンタにおいてどのような遷移が許容されるのかを示す、世界モデルの使用を開示している。
【０００９】
ＥＰ０５９０８６６（ＡＴ＆Ｔ）は、故障検出ではなく、フォールトトレランスを提供する演算技術を開示している。
【００１０】
ＵＳ５，７５８，０６０（ダラスセミコンダクタ）は、ソフトウェアが所定量のコードを省略していないことを実証するための、ハードウェアを開示している。当該技術は、ハードウェアタイマーを検査して、所定のデータ演算がほぼ適切なタイミングで行われるかどうか否かを判別する工程を含んでいる。
【００１１】
ＧＢ１４２２６０３（エリクソン）は、故障を検出するためにコードの各セクションを実行するのに要した時間を検査する技術を開示している。
【００１２】
ＵＳ６，０４４，４５８（モトローラ）は、オペコード（opcodes）に順番に記憶された固定語（fixwords）を用いてプログラムフローを監視するハードウェア技術を開示している。
【００１３】
ＵＳ５，７１７，８４９（ＩＢＭ）は、連鎖的な一連の制御ブロックにおいて故障を早期検出するシステムおよび手順を開示している。プログラム実行における各作業の単位（すなわち「ブロック」）が、適切なプログラムに正確に関連付けられているかを検査する（これによって、関係のないブロックが実行されることがない)方法が開示されている。これは、ブロックが、オペレーティングシステムによって（例えばリモート記憶装置から)、プログラム実行の一部としてではなく負荷されたときに、（ブロック内にデータとして埋め込まれている）タグを比較することによって行われる。当該方法による保護は、本発明に係る保護に対して相補的である。
【００１４】
従来技術では、「ウォオッチドッグ」タイマーの使用は周知である。ウォッチドッグは、プログラムによって間隔を置いてリセットされるハードウェアデバイスである。ウォッチドッグは、（例えば攻撃中に)プログラムが不具合を起こして、タイマーを迅速にリセットしない場合にタイムアウトするため、適切な処置を講じることができる。しかし、特殊なハードウェアが必要であり、また検出がやや粗雑であるため、いかなるリセットポイントに達するソフトウェアによっても、ウォッチドッグの機能が弱められる。
【００１５】
プログラムは、グリッチが生じたか否かをＣＰＵクロック（サイクルカウンタ）を用いて判別することができると考えられている。グリッチ後、グリッチ前に期待されたよりも速く（または遅く）動作が完了する場合がある。しかしこのような方法は、一般的には、完了するまでの長さがデータ依存的または環境依存的であるコードの検査には不適当である。
【００１６】
今日まで考えられた別の方法では、プログラム実行状態の可能な進展の実行可能モデルが提供される。プログラムは、実行時に、その状態に関する情報をモデル部品に与える。達するべきではない状態にプログラムが達したことをモデルが判別すると、攻撃が行われていると見なされて、処置を講じることができる。しかし、このようなモデルは、開発コストが高い場合があり、また不正確である（許容度が過度に高い)か、あるいは大型で非効率である可能性がある。
【００１７】
〔発明の開示〕
本発明の第１の形態によると、複数の領域を通る実行パスに従ってデバイス上において実行されるプログラムを、予期しないメモリ領域へプログラム実行をジャンプさせるデバイス不具合および電圧スパイクなどの物理的妨害によって生じる実行フローエラーから、少なくともある程度は保護する方法であって、ランダムにアクセス可能なメモリ領域に第１の検査値を提供する工程と、少なくとも１つの領域において少なくとも一回は、上記第１の検査値が当該領域に対する予想値を有しているか否かを判別する工程と、第１の領域から、上記のような判別が成される第２の領域へと実行が通過するときに、上記第１の検査値を、上記第２の領域において予想される値を有するように更新する工程と、上記のような判別が否定的であった場合にエラー処理手順を行う工程とを含んでいる、方法が提供される。
【００１８】
上記方法は、上記のような判別工程を、クリティカルな性質（critical nature）を有する上記プログラムの少なくとも一部の演算の前に行う工程を含んでいてもよい。
【００１９】
上記方法は、上記のような判別工程を、上記検査値更新工程の少なくとも一部の前に行う工程を含んでいてもよい。
【００２０】
上記方法は、上記のような判別工程を、上記デバイスの持続ストレージを更新する上記プログラムの少なくとも一部の演算の前に行う工程を含んでいてもよい。
【００２１】
上記方法は、上記のような判別工程を、上記デバイスの外側または上記デバイスの保護領域の外側にデータを送信させる少なくとも一部の演算の前に行う工程を含んでいてもよい。
【００２２】
上記方法は、ランダムにアクセス可能なメモリ領域に第２の検査値を設ける工程と、領域が、コール領域からコールされるコードの機能ユニットを有している場合は、リターン領域に実行を戻す工程と、実行が上記機能ユニット外に進む前に、上記機能ユニットに対して予想される最終値を有するように、第２の検査値を更新する工程と、実行が上記機能ユニット外に進んだ後および実行が上記リターン領域に戻る前に、上記第２の検査値が上記予想された最終値を有しているか否かを判別する工程とを含んでいてもよい。
【００２３】
上記リターン領域は、上記コール領域と同一であってもよい。
【００２４】
上記第２の検査値は、同一のランダムにアクセス可能なメモリ領域を用いて、上記第１の検査値と同一であってよく、上記第２の領域において予想される上記値を有するように上記第１の検査値が更新される前に、上記第２の検査値が、上記予想される最終値を有しているか否かを判別する工程を含んでいてもよい。
【００２５】
上記方法は、上記第２の領域に実行が進む前に、上記更新工程が行われる上記第１の領域に実行が入るときに、上記第１の領域において予想される値を有するように上記第１の検査値を更新する工程を含んでいてもよい。
【００２６】
上記方法は、上記検査値が予想外の値を一旦推定すると、後に行われる上記のような更新においても期待外の値を保持する可能性を有するように、上記検査値を更新する工程を含んでいてもよい。
【００２７】
上記方法は、上記更新された検査値が上記更新前に上記第１の領域に対する上記予想値を有している場合に限り、上記更新された検査値が上記第２の領域に対する上記予想値を有するように、上記検査値を、上記第２の領域に対するその予想値および上記第１の領域に対するその予想値に基づいて更新する工程を含んでいてもよい。
【００２８】
上記方法は、上記第１の領域に対する上記予想値から導き出される第１の調整、および上記第２の領域に対する上記予想値から導き出される第２の調整を効果的に適用することによって上記検査値を更新する工程を含んでいてもよく、上記第１の調整は、上記第２の調整に対して用いられる演算子に対して反比例関係（inverse relationship）にある演算子を用いる。
【００２９】
上記方法は、上記第１の領域に対する上記予想値および上記第２の領域に対する上記予想値から導き出される中間値を演算することによって、上記第１の調整および第２の調整を共に適用する工程と、演算された上記中間値から導き出される上記検査値に対して、単一の調整を適用する工程とを含んでいてもよい。
【００３０】
上記中間値は、コンパイル中に事前に演算されてもよい。
【００３１】
上記方法は、上記第１の調整および第２の調整を、上記検査値に別々に適用する工程を含んでいてもよい。
【００３２】
上記第１の調整のための上記演算子は減算演算であってもよく、上記第２の調整のための上記演算子は加算演算であってよい。
【００３３】
上記第１の調整のための上記演算子は排他的論理和演算であってよく、上記第２の調整のための上記演算子は排他的論理和演算であってもよい。
【００３４】
少なくとも一部の領域あるいは機能ユニットに対する上記各予想値は、上記プログラムコードから直接取り出すことができる。
【００３５】
上記方法は、少なくとも一部の領域あるいは機能ユニットに対する上記各予想値を、異なるメモリ領域に記憶する工程と、領域あるいは機能ユニットに対する上記予想値を、適切な上記メモリ領域から必要時に取り出す工程とを含んでいてもよい。
【００３６】
少なくとも一部の予想値は、乱数または擬似乱数であってもよい。
【００３７】
少なくとも一部の予想値は、その対応する各領域または機能ユニットのメモリ領域の入力点から導き出すことができる。
【００３８】
上記方法は、上記少なくとも一部の予想値をハッシュ技術を用いて導き出す工程を含んでいてもよい。
【００３９】
上記方法は、ランダムにアクセス可能なメモリ領域に第３の検査値を提供する工程と、領域が、コール領域からコールされるコードの機能ユニットを有している場合は、上記コール領域に実行を戻す工程と、実行が上記機能ユニットに入る前に、上記第３の検査値を、上記コールに関連する値を有するように更新する工程と、少なくとも１つの上記のような機能ユニットから実行が戻った後に、上記第３の検査値が上記コールに関連する上記値を有しているか否かを判別する工程とを含んでいてもよい。
【００４０】
上記方法は、上記第３の検査値判別工程を、実行が上記コール領域に戻る前に行う工程を含んでいてもよい。
【００４１】
上記方法は、上記コールに関連する量の調整を与えることによって、上記第３の検査値を更新する工程と、上記調整を上記と同量だけ逆にすることによって上記第３の検査値が上記コール前調整が行われる前の値に戻るか否かを判別することによって、上記第３の検査値が上記コールに関連する上記値を保持しているかを、実行が戻った後に判別する工程とを含んでいてもよい。
【００４２】
上記方法は、上記第３の検査値を、上記コール前調整が行われる前の値に戻すために更新する工程を含んでいてもよい。
【００４３】
上記工程は、実行前に上記プログラム内に含まれていた命令によって行うことができる。
【００４４】
プログラム実行は、プログラムカウンタによって制御することができる。
【００４５】
上記デバイスは、セキュリティデバイスを含んでいてもよい。
【００４６】
上記デバイスは、スマートカードを含んでいてもよい。
【００４７】
本発明の第２の形態によると、複数の領域を介して進む実行パスに従ってデバイス上において実行されるプログラムを、予期せぬメモリ領域へプログラム実行をジャンプさせるデバイス不具合および電圧スパイクなどの物理的妨害によって生じる実行フローエラーから、少なくともある程度は保護する方法であって、ランダムにアクセス可能なメモリ領域に第１の検査値を提供する工程と、少なくとも１つの領域において少なくとも一回は、上記第１の検査値が当該領域に対する予想値を有しているか否かを判別する工程と、第１の領域から、上記のような判別が成される第２の領域へと実行が通過するときに、上記第１の検査値を、上記第２の領域において予想される値を有するように更新する工程と、上記のような判別が否定的であった場合にエラー処理手順を行う工程とを含むように、上記プログラムを変換する工程を含んでいる方法が提供される。
【００４８】
上記プログラムは、Ｃプログラミング言語などの高級プログラミング言語において特定することができる。
【００４９】
上記方法は、上記プログラムをコンパイルして、実行のための機械コードを上記デバイスによって直接生成する工程を含んでいてもよい。
【００５０】
本発明の第３の形態によると、予期せぬメモリ領域へプログラム実行をジャンプさせるデバイス不具合および電圧スパイクなどの物理的妨害によって生じる実行フローエラーから少なくともある程度は保護されるプログラムであって、複数の領域を介した実行パスに従って実行されるプログラムがロードされたデバイスであって、ランダムにアクセス可能なメモリ領域に第１の検査値を提供する手段と、少なくとも１つの領域において少なくとも一回は、上記第１の検査値が当該領域に対する予想値を有しているか否か否かを判別する手段と、第１の領域から、上記判別が成される第２の領域へと実行が通過するときに、上記第１の検査値を、上記第２の領域において予想される値を有するように更新する手段と、上記判別が否定的であった場合にエラー処理手順を行う手段とを含んでいるデバイスが提供される。
【００５１】
本発明の第４の形態によると、デバイス上において実行されるときに、当該デバイスに、本発明の上記第１の形態または上記第２の形態に係る方法を実施させるプログラムが提供される。
【００５２】
本発明の第５の形態によると、デバイスにロードされるときに、上記デバイスを、本発明の上記第３の形態に係るデバイスにするプログラムが提供される。
【００５３】
上記プログラムは、キャリア媒体上において実行することができる。当該キャリア媒体は、伝送媒体であってよい。当該キャリア媒体は、記憶媒体であってよい。
【００５４】
〔図面の簡単な説明〕
例として、添付図面を参照されたい。添付図面は、以下の通りである。
【００５５】
図１は、本発明の第１の実施形態の動作を示す図である。
【００５６】
図２は、本発明の第２の実施形態の動作を示す図である。
【００５７】
図３は、本発明の一実施形態を用いて実施可能な一スキーム（scheme）における様々な段階を示すブロック図である。
【００５８】
図４は、本発明の一実施形態に係る保護されたプログラムを実行するようにプログラムされたデバイスと、そのようなデバイスにおける様々な攻撃ポイントを示すブロック図である。
【００５９】
〔発明の最良の実施形態〕
本発明の一実施形態は、上述した従来の方法を考慮に入れながら、プログラムカウンタがプログラマーの予期せぬルートでコード内の特定のポイントに達した場合、ＣＰＵがこれを検出して保護処置（例えば、デバイスの終了または他のタイプのエラー処理ルーチンの実行)を講じることができるようにするための補助をする、ソフトウェアフロー制御検査を提案する。
【００６０】
以下では、本発明の実施形態について、Ｃ言語で書かれたソースコード、あるいはその簡略されたサブセットを参照しながら説明する。
【００６１】
具体的には、通常のＣ言語構文によると、“=”は代入を示し、“+=”はインクリメント代入（incrementing assignment）を示し、そして“==”は等価試験を示すために用いられている。
【００６２】
「関数」という用語は、単位として存在する１つのコードを示すために用いられている。関数は、通常のソフトウェア工学の実施においては、名前および明確な動作を有している。これは、Ｃ言語では実際に関数と称される。しかし、一部のコンピュータ言語では、同一の概念に対して、「サブルーチン」、「手順」、あるいは「方法」という用語が用いられている。
【００６３】
「故障」および「誤り」という用語は、一般的には置き換え可能に用いられており、意図的および偶発的に引き起こされたシステムの誤動作を示している。
【００６４】
構文“[]”は、例えばr[c]、s[c]、e[c]などの添字を示すために用いられている。
【００６５】
本発明の一形態を実施する方法は、プログラムカウンタを変更する攻撃に対して安全性を高めるために、ソースコードを変換する工程を含んでいる。
【００６６】
このような方法では、プログラムコードを複数の領域に分割して、ランダムだが固定した値r[c]を各領域ｃに与えると考えることができる。グローバル変数wisbは、プログラムカウンタが領域ｃ内のコードを示すときは常に、wisb==r[c]であることを意図して定義されている。プログラムカウンタが領域cから新しい領域c’へと正確に移動できるときは常に、この変換によって、wisbの以前の値を新しい値r[c’]に変換するためのステートメントが挿入される。領域内のコードは、wisbの値が正しいかを確認するために（および、正しくない場合は適切な処置を講じるために）、必要に応じて変換させることができる。これによって、wisbへの代入によって合致しない、領域間におけるあらゆる制御フローが潜在的に検出される。
【００６７】
wisbを、wisb=r[c’]と単純代入するのではなく、以前の値およびr[c’]-r[c]の値に設定することが好ましい。これによって、また古い値がr[c]であったと仮定することによって、新しい値はr[c]+（r[c’]-r[c])となる。この値は、r[c’]と等しい。しかし、何らかの故障によって古い値が不正確であった場合（すなわちr[c]と等しくなかった場合)、新しい値もまた同量分、不正確となり、実行の残りの部分においても不正確のままとなる（偶然を除く）。従って上記値は、早急に検査されない場合であっても、後に検査されることになる。
【００６８】
このようにwisbは、一旦不正確となると、（高い確率で）不正確であり続けるという、「エラー伝搬」特性を有していると考えられる。これは、セキュリティおよびエラー検出において通常の特性である。
【００６９】
〔第１の実施形態〕
本発明の第１の実施形態について、図１を参照しながら説明する。図１は、保護される関数ｆを呼び出す、保護される関数ｍを示している。
【００７０】
保護されるべきプログラム（あるいはサブプログラム）Ｐがあると仮定する。
【００７１】
Ｐのいずれの部分が保護されるべきなのかが決定される。本実施形態では、全関数のみを保護するものと決定する。これによって、C={c1, c2, ...cn}が、保護されるＰにおいて決定される全ての関数名をとるのに好都合となる。変換ユーティリティは、保護プロトコルに適切に従うために、コールする側とコールされる側との両方の保護状態を知っていなければならない。少なくとも１つの関数が保護され、保護されない関数は、保護される関数を呼び出さないものと仮定する。
【００７２】
入力ｘを受け付けるfunction＿assert(x)が与えられ、ｘが真である場合、単純に、呼び出す側に戻るものと仮定する。ｘが偽である場合、何らかの故障警告が機能するか、あるいはエラー処理ルーチン（例えばデバイスのリセット）が動作する。上記function＿assert()は、一般的に、本発明の一実施形態において保護される関数のうちの１つではなく、多くの場合、プラットフォームによって提供される低レベルコールである。
【００７３】
Ｃにおける各ｃに対して、２つの値s[c]およびe[c]が定義される。“s”および“e”は、それぞれ“開始（start）”および“終了（end）”を示している。s[c]およびe[c]は、セキュリティのために、その（整数）データ型に対して可能な全集合に及ぶ範囲の中から無作為に選択されることが望ましい。s[c]およびe[c]は、攻撃の複製を防止するために、デバイスが起動される度に無作為に生成されることが好ましい。しかし、本実施形態では、これらの値は定数であるものと仮定する。
【００７４】
グローバル変数wisbは、s[c]およびe[c]の値と同一のデータ型によって宣言され、また初期値s[main]を与える。「main」は、Ｐにおいて定義される最も外側の関数（Ｐに対して意図される唯一の開始点)である。この関数は、Ｃプログラミング言語では実際に「main」と称される。既述した条件により、本実施形態では、mainは、保護される関数であると保証される。
【００７５】
Ｃにおける各cに対して、関数cは、そのボディーコードB[c]を、変更されたコードB’[c]と置換することによって変更される。B’[c]は、以下の様に定義される。
【００７６】
B’[c]の実行前に、当該構造は、何らの故障も引き起こされていない場合は、wisb==s[c]が真であることを保証する。B’[c]は、終了すると、故障がない場合はwisb==e[c]が真であることを保証する。
【００７７】
INIT[c]を、ステートメント“＿assert(wisb==s[c]);”となる様に定義する。
【００７８】
TERM[c]を、ステートメント“wisb += e[c] - s[c];”となる様に定義する。
【００７９】
まずB[c]を書き換えて、各内部コールを、保護される関数に変更する。可能な限りこれを分かり易くするために、まず、保護される各関数コールが、“X = F(Y);”というステートメントとして独自に書き込まれるものとする。上記Ｘは、（任意の）仮引数Ｙを有する関数Ｆの（任意の）結果を記憶するために用いられる（任意の）変数である。既にこのような状態になっていない場合でも、このような状態にするのは簡単である。
【００８０】
各“X = F(Y)”を以下のステートメントによって置換する。
{wisb += s[F] - s[c];
X = F(Y);
＿assert(wisb == e[F]); 
wisb += s[c] - e[F];}
あらゆる“return X;"ステートメント（Ｘは任意の戻り値）もまた、“{TERM[c]; return X;}”によって置換される。これは、B[c]が意図的に早く終了した場合を対処する。別の方法としては、“return”ステートメントを用いずにB[c]を書き換えるという方法もあるが、これはより複雑である。
【００８１】
変更された部分（すなわち、全ての関数コール、および上述したように置換された戻りステートメントを有するB[c]）は、BB[c]と称される。
【００８２】
次に、B’[c]を、“INIT[c]; BB[c]; TERM[c];”となる様に定義する。
【００８３】
(BB[c]を通過する全ての可能な実行パスが戻りステートメントを終了した場合、最終的なTERM[c]は省略可能である。)。
【００８４】
故障がない状態において、wisbは、B’[c]が実行を開始したときにs[c]と等しい場合、終了時（および、もし終了する場合）には、e[c]と等しくなる。さらに、B’[c]が（保護される）関数ｆを呼び出す場合は常に、wisbの値は、ｆの開始時にはs[f]となり、ｆの戻り時にはe[f]となる。図１では、二重括弧{{}}内の式は、故障がない状態において真であるように意図された値を示している。これらの式は、図１の理解を補助するために挿入されたものであり、コードの一部としては考えられない。
【００８５】
エラー伝搬特性に鑑みて、（故障のため）一旦wisbが不正確となると、如何なるコマンドによってもこれが自動的に訂正されることはないため、不正確のままである可能性が高い限りは、アサーションの検査は任意であってよいことに留意されたい。従って、エラーの検査は時折行えばよい。例えば、セキュリティ中心のアプリケーション（security-centred application）に対しては、セキュリティクリティカルな各動作の直前、永続ストレージを更新する各動作の直前、および外部へデータを送信する各Ｉ／Ｏ動作の直前に、最少集合の検査を行う。挿入するアサーションは、特定のアプリケーションによる必要性に応じて増減することができる。
【００８６】
次に、単純なプログラムに適用される変換の実施例を挙げる。
【００８７】
本実施例では、関数“main”が関数“docredit”を呼び出すものとする。関数“print”は、汎用関数であり、システムによって定義される。従ってここでは、関数“print”は、保護されるべきものとは考えられない。
【００８８】
保護されないコードは:
main(pin、amount）{
if（pin != test）return;
print(docredit(x));
}
int docredit(int x）{
balance = balance + x;
return balance;
}
となる。
【００８９】
上記コードはまず、“docredit()”のコールが“print()”のコール内部から出るように、以下に変換することができる。
【００９０】
main(pin、amount）{
int y;
if（pin != test）return;
y = docredit(x);
print(y);
}
int docredit(int x）{
balance = balance + x;
return balance;
}
次に、残りの変換が適用される。説明する目的のために、プリプロセッサ定数は、sMAINを読み出してs[main]を実施し、eMAINを読み出してe[main]を実施する等として定義される。なお、使用時には、代わりに乱数を補間することも可能であるが、これはリーダにとっては従うのがより困難である。
// constants for each function
// name（randomly generated)
#define sMAIN 56769
#define eMAIN 15637
#define sDOCREDIT 9493
#define eDOCREDIT 41322
int wisb = sMAIN;
main(pin、amount）{
int y;
＿assert(wisb==sMAIN);    // INIT[MAIN]
if（pin != test）
{wisb += eMAIN - sMAIN; return;}    // handling
// return
// handling function call:
{wisb += sDOCREDIT - sMAIN; 
y = docredit(amount); 
＿assert(wisb == eDOCREDIT);
wisb += sMAIN - eDOCREDIT;}
＿assert(wisb==sMAIN);    // added check
print(y);
wisb += eMAIN - sMAIN;    // TERM[MAIN]
}
docredit(int amount){
＿assert(wisb==sDOCREDIT]);   // INIT[DOCREDIT]
balance = balance + amount;
{wisb += eDOCREDIT - sDOCREDIT; return;}
// no TERM required（return is always used)
}
多くのコンパイラは、実行をより効率的にするために、定数式（「定数畳み込み」）を単純化する点について留意されたい。例えば、“wisb += eMAIN - sMAIN;”を“wisb += -41132;”に低減することができる。これによってセキュリティに影響が及ぼされることはない。
【００９１】
また、機密データを偶発的に印刷しようという試みを捕捉するために、印刷直前にさらなるアサーションが追加された点についても留意されたい。
【００９２】
〔第２の実施形態〕
次に、本発明の第２の実施形態について、図２を参照しながら説明する。
【００９３】
第１の実施形態では、関数ｆが戻るときは常に、wisbの値はe[f]でなければならないという制限がある可能性がある。しかしｆは、ソースコード内の２つ以上のポイントからコールされる場合もある（ｆは「多重コール側（multi-caller）」関数と言われる）ため、上記スキームは、ｆを誤ったコール側に戻すグリッチに対して保護を行わない。例えば、ｍ１およびｍ２が双方ともｆを呼び出すように設計されている場合、グリッチによって、ｆが、例えｍ１から呼び出された場合であってもｍ２に戻される可能性がある。wisbの値は、いずれの場合にも同じe[f]であるため、第１の実施形態のプロトコルでは故障を検出することができない。
【００９４】
第２の実施形態では、第２の保護層を追加するために、グローバル状態に余剰変数パス（extra variable path）が導入および初期化される。これは、第２の実施形態では、無作為な値に導入されることが好ましい。
【００９５】
前述同様、cがコールされると、{{wisb == s[c]}}であることが保証され、cが終了すると、{{wisb == e[c]}}であることが保証される（図１と同様、図２では、二重括弧{{}}内の式は、故障がない状態において真であるように意図された値を示している。これらの式は、図２の理解を補助するために挿入されたものであり、コードの一部としては考えられない）。さらに、関数ｆがコールされる前（および、wisbが更新される前）に、ローカルコピー（local copy）ｐにパスの値が記憶される。次に、公知の方法を用いて、（一定の）無作為な値Rを加算することによってパスが変更される。当該Ｒは、特定の関数コールに固有の値である。上記関数が戻り、wisbが更新された後、パスｐの値がＲと等しいかどうかが決定される。そして、Ｒを再び減算することによって、パスがリストアされる。
【００９６】
この方法の保護領域は、wisbがs[f]と等しい領域の上位集合である。なお、fが多重コール側関数である場合、wisbの構造では、そのような領域を区別することができない点について思い出されたい。従って、コードにおける上記のような各領域には、異なる値（R）のパスｐが与えられる。関数が何らかの理由で不正確な領域に戻った場合、wisbが不正確となるか、あるいはパスｐが不正確となるかのいずれかとなる。パスの調整前に＿assert(path - p == R)を得る代わりとして、＿assert(path == p）ステートメント前に-= Rであるパスを調整することができる。
【００９７】
INIT[c]およびTERM[c]を前述同様に定義する。ここでもまた、前述同様に、関数コールを正準形Y = F(X)に変換する。このような各関数コールに対して、一定の乱数Rを生成し、そして関数コールを以下の様に置換する。
{int p = path; path += R;
wisb += s[F] - s[c];
Y = F(X);
＿assert(wisb == e[F]);
wisb += s[c] - e[F];
＿assert(path - p == R); 
path -= R;}
なお、全ての関数コールに対して上記方法を用いる必要はないことに留意されたい。変更される必要がある関数は、（例えば多重コール側関数を呼び出すため）「危険がある」と考えられるもののみである。他の関数は、第１の実施形態による上記方法を用いることができる（あるいは、完全に保護されていない状態としておくことができる）。
【００９８】
上記方法に必要なのは、第１に、上記方法を用いる各関数に対する１つの余剰グローバル変数、パス、および多くとも１つのローカルストレージ場所ｐである。ローカルストレージｐは、スタック上に保持することができる。これによって、それが保護する関数がアクティブである（あるいは、それに戻るためのコールを待っている）ときのみにストレージを使用するという利点がある。保護される各pは、p[c]としてグローバルストレージに保持することができる。
【００９９】
上記方法の代わりとしては、多重コール側関数ｆへの各コールポイント1, 2... kは、（必要に応じて、）s[f]およびe[f]、例えばs[f][1]、s[f][2]、...s[f][k]およびe[f][1]、e[f][2]、...e[f][k]に対して異なる値を用いることができる点を除いては、第１の実施形態による方法が用いられる。関数ｆは、wisbがs[f][i]のいずれか１つと等しいことを検査し、最終的には適合しているe[f][i]に戻る。Ｆによって読み出される、保護されるあらゆる関数はまた、複数の関連付けを有している可能性がある。このため上記のような方法は、管理不可かつ非効率となる場合がある。
【０１００】
〔第３の実施形態〕
本発明の第３の実施形態について説明する。
【０１０１】
２つの第１の実施形態は、関数ユニット全体のみを保護する。これらの実施形態では、関数ｍ内におけるwisbの値は、INIT[m]の後かつTERM[m]の前における任意のソース位置s[m]であるが、関数コール付近のセットアップまたはクリア中は、そうではない。(この領域は、図１において点描で示されている)。第２の実施形態では、ｍ本体の内部において関数ｆが複数回コールされる場合、保護は行われなかった。従って、ｆの一方のコールからｆの異なるコールへの誤った戻りは検出されない。
【０１０２】
第３の実施形態では、関数本体は、複数の小さい領域へとセグメント化されると考えられる。各領域は、関数全体を保護する方法と同様の方法によって保護される。
【０１０３】
本実施形態を、関数に分割されない「モノリシック」コードに適用することができる。この場合、関数は１つのみであり、当該関数はコード全体を含んでいるものと考えられる。（プログラムが開始する）開始点は１つのみであり、終了点はない可能性がある（プログラムが非終端である場合)。
【０１０４】
説明のため、および、一般的にあらゆる状況において適用可能な方法を提供するために、以下の要素から成る、再帰的に定義された簡易言語を用いて考察する：
「コードセグメント」Sは、以下のいずれかである。
A
（保護されない）関数の代入あるいはコールなどのアトミックステートメント、あるいは空のステートメント（“{}”で示される）。
F
アトミックステートメントのようなステートメント。しかし、保護される関数のコールは厳密に１つであり、また関数名はFUNC(F)という標記を用いて検索される。例えば、FUNC(“a = 3 + f(x*g(y))”)は、“ｆ”（ｆは保護され、ｇは保護されないものと仮定する）と等しい。
D: S
一部のローカル変数Dが宣言されるセグメントS。範囲はS。
S1; S2
順次実行される２つのセグメント、S1とS2との複合。最初に実行されるのはS1。
while(E）S1
式Eが真である場合にセグメントS1が置換されるループ構造。Eは、保護される関数のコールを含んでいてはならない。
if E S1 S2
Eを評価し、Eが真である場合にS1を行い、Eが偽である場合にS2を行う条件付き構造。Eは、保護される関数のコールを含んでいてはならない。
return E
現在の関数から出てコール側に戻る、戻りステートメント。戻り値Eは任意。Eは、保護される関数のコールを含んでいてはならない。
【０１０５】
括弧{...}は、曖昧にならないように項をグループ分けするために用いられている。
【０１０６】
「プログラム」であるＰは、グローバル変数および関数の定義の集合である。各関数ｆは、コードセグメントである本体、B(f)を有している。「メイン」関数であるMAIN(P)があり、これはＰの開始点である。
【０１０７】
また、単純な理由により、Ｐは変数名「wisb」は述べないものとする。Ｐが変数名「wisb」を述べると、その名前は新しい名前によって完全に置換されることになる。当業者であれば、現実世界のプログラムは、この形式で機械的に１つに簡略化できることを容易に理解できるであろう。この簡略形式（reduced from）によって得られる簡素化は必須ではないが、変換の既述をより簡素にすることができる。
【０１０８】
さらに重要な点としては、本願に記載の教示内容を用いることによって、中間物（intermediate）として簡略形式を明示的に用いることなく、元のプログラムに変換をいかに適用するかが当業者には明らかとなるであろう。
【０１０９】
ａ，ｂ，ｃ，ｄを、整数定数を表すメタ変数とする。
【０１１０】
#aを、任意のステートメント“＿assert(wisb == a)”であると定義する。当該ステートメントは、変換によって与えられた通りに挿入することができ、あるいは挿入しなくてもよいという意味で任意である。いずれの場合も、全てのアサーションが除外された場合は保護が行われないという前述の条件において、許容可能な変換のインスタンス化であると考えられる。
【０１１１】
T(a,b)を、ａがｂと等しくない場合はセグメント“#a; wisb += b - a; #b;”であると定義し、ａがｂと等しい場合は“#a”であると定義する。
【０１１２】
ａおよびｂを定数であると仮定すると、変換a<<S>>bは、Sの構造における再帰によって、セグメントSにおいて以下の様に定義される。
【０１１３】
一部の新しい無作為な値cに対して、
a<<A>>b = #a; A; T(a,b);
a<<F>>b = #a; T(a,s[FUNC(F)]); F; T(e[FUNC(F)]、b）
a<<D: S>>b = D: {#a; a<<S2>>b}
a<<S1;S2>>b = #a; a<<S１>>c; c<<S2>>b
一部の新しい無作為な値cに対して、
a<<while(E）S>>b = #a; while(E）{T(a,c); c<<S>>a}; T(a,b)
一部の新しい一対の無作為な値c、dに対して、
a<<if(E）S1 S2>>b
= #a; if(E）{T(a,c); c<<S1>>b} {T(a,d); d<<S2>>b}
a<<return E>>b = T(a、e[f]); return E
ここでfは、囲んでいる関数である。
B(f、S)を定義する、すなわち関数ｆの本体Sの変換は、
一部の新しい一対の無作為な値s[f]、e[f]に対して、
B(f,S)= s[f]<<S>>e[f]
となる。
【０１１４】
プログラムＰの変換Ｐ’は、次の様に定義される。まずＰから開始し、Ｐにおいて定義される保護される各関数ｆに対して、ランダム定数（random constant）s[f]およびe[f]の定義を加える。値s[MAIN(P)]に初期化された、wisbのグローバル定義（global definition）を加える。Ｐにおいて保護される各関数ｆに対して、fの本体SをB(S)によって置換する。Ｐにおいて保護されない各関数gに対して、gが保護される関数ｆを呼び出すときは常に、fのコール直前にステートメントwisb=s[f]を挿入する。結果Ｐ’を呼び出す。
【０１１５】
上記定義には、テスト#aの挿入決定、および定数の選択において、大幅な選択の自由が含まれている。もし#aが強制的なアサーションとして扱われ、全ての定数が新しものとなるように選択された場合、変換されるプログラムはやや大きくなるが、非常によく保護されたプログラムとなる。
【０１１６】
連続ステートメント“T(a,b); T(b,c)”を単一のT(a,c）によって変換して、プログラムサイズを縮小することができる（また、セキュリティを強化できる場合もある)。
【０１１７】
必要に応じて、（aがbと等しいときのTの定義に従って)ランダム定数cおよびdを他のランダム定数と同じになるように選択して、多くのT(a,b）ステートメントがゼロになるようにすることができる。
【０１１８】
以下に一例を示す。この例は、保護されないコードであるものとする：
main(）{
x = １;
y = ２;
return;
}
これは、まず以下の様に変換される。
【０１１９】
int wisb = s[main]; // global
const A=84756387、B=48976230; // random constants
const sMain=45732576、eMain=2098573; 
main（）{
＿assert(wisb == sMain); //optional
x = 1; 
＿assert(wisb == sMain); //optional
wisb += A - sMain;
＿assert(wisb == A); //optional
y = 2; 
＿assert(wisb == A); //optional
wisb += B - A;
＿assert(wisb == B); //optional
wisb += eMain - B;
＿assert(wisb == eMain); //optional
return;
＿assert(wisb == B);   // optional:
// note: cannot reach here
}
一部の任意の＿assertsが削除されると、以下のようになる。
【０１２０】
int wisb = s[main]; // global
const A=84756387, B=48976230; // random constants
const sMain=45732576, eMain=2098573;
main（）{
＿assert(wisb == sMain); //optional
x = 1;
wisb += A - sMain;
＿assert(wisb == A); //optional
y = 2;
wisb += B - A;
wisb += eMain - B;
＿assert(wisb == eMain); //optional
return;
}
wisbインクリメントを組み合わせることによって、以下の様になる。
【０１２１】
int wisb = s[main]; // global
const A=84756387;   // random constants
const sMain=45732576、eMain=2098573; 
main（）{
＿assert(wisb == sMain); //optional
x = １;
wisb += A - sMain;
＿assert(wisb == A); //optional
y = 2;
wisb += eMain - A;
＿assert(wisb == eMain); //optional
return;
}
Aがs[main]と同じになるように選択されている場合は、以下の様になる。
【０１２２】
int wisb = s[main]; // global
const sMain=45732576、eMain=2098573; 
main（）{
＿assert(wisb == sMain); //optional
x = １; 
y = ２; 
wisb += eMain - sMain;
＿assert(wisb == eMain); //optional
return;
}
定数sMainおよびeMainは、メモリ内に記憶されて実行中に読み出されるのではなく、コンパイラによってコード内に構築されることが好ましい。
【０１２３】
〔第４の実施形態〕
本発明の第４の実施形態では、多重コール側関数が故障によって不正確なコール側に戻らないように保護が行われる。第３の実施形態では、関数ｆの各コール側は、wisbが戻り時にe[f]に設定されて、wisb自体がこの種のエラーを検出できないようになることを期待している。
【０１２４】
第３の実施形態の変換は、第２の実施形態が第１の実施形態から導かれた方法と同様の方法によって変更される。これは以下の通りである。
【０１２５】
余剰グローバル変数パスを加算する。保護される関数コールの節を置換することによって、＿<<＿>>＿の定義を変更する。
a<<F>>b =
#a;
declare p: 
{
p = path; path+=R; 
T(a,s[FUNC(F)]); F; T(e[FUNC(F)]、b);
＿assert(path - p == R); path-=R;
}
ここでｐは、Ｆでは用いられていない新しい変数名である。
【０１２６】
パスが、wisbのようなエラー伝搬特性を有していることを考慮すると、上記＿assertステートメントは、パスがその時点において正確な値を有していることを保証するために少なくともプログラム内のどこかに＿assertステートメントが含まれているのであれば、任意として処置することができ、またこれと共にローカル変数ｐを使用することもできる。これによって、より効率的（用いるストレージを減らして、速く）実行を行うことできる。これらを任意として扱うことによって、以下の様になる:
a<<F>>b =
#a;
{
path+=R;
T(a,s[FUNC(F)]); F; T(e[FUNC(F)]、b);
path-=R;
}
〔第５の実施形態〕
あるいは、関数本体において保護される全ての関数コールは、１つのローカル変数ｐを共有することができる。これを、本発明の第５の実施形態として考えることができる。
a<<F>>b =
#a; path+=R;
T(a,s[FUNC(F)]); F; T(e[FUNC(F)]、b);
＿assert(path - p == R); path-=R;
関数本体変換Bもまた、以下の様に変更される。
B(f、S)= declare p: {p=path; s[f]<<S>>e[f]}
ここでｐは、Sにおいて表されない新しい変数名である。
【０１２７】
〔第６の実施形態〕
MAINが保護される関数ではない場合であっても、本発明の一実施形態を用いることができる。この制限を緩和することによって、保護されない関数ｕが、保護される関数ｐを呼び出すことも可能となる。これを、本発明の第６の実施形態として考えることができる。
【０１２８】
uの本体が、ステートメントx = p()を含んでいるものとする。これは、以下によって置換することができる。
【０１２９】
declare tmp:
{tmp = wisb:
wisb = s[p];
x = p();
#(e[p]);
wisb = tmp;}
保護される関数が、（他のコールを介して直接的または間接的に）ｕを呼び出すことができない場合、wisbの古い値を記憶する必要はなく、あるいはこれを、ｐをコールた後にリストアする必要はない。
【０１３０】
〔一般例〕
図３は、本発明の一実施形態を用いたスキームの一形態の様々な段階を示すブロック図である。第１の段階Ｓ１では、上述のセキュリティ変換手順を用いて、保護されないソースコード２が保護されるソースコード４に変換される。第２の段階Ｓ２では、保護される当該ソースコードがコンパイルされて、標的デバイス６内にロードされる。第３の段階Ｓ３では、コンパイルされた保護される上記コードが、標的デバイス６において実行される。第３の段階Ｓ３中において、一時的エラーまたはグリッチ攻撃が生じる。これは、上述のコンパイルされた保護されるコードに含まれている工程によって検出される。この結果、ハードウェアがリセットされるか、あるいはその他のエラー処理ルーチンＳ４が行われる。図４は、本発明の一実施形態に従って保護されるプログラムを実行するようにプログラムされたデバイス１０のブロック図を示している。デバイス１０は、記憶部１２、中央演算処理装置（ＣＰＵ）１４、プログラムカウンタ（ＰＣ）１６、入力／出力装置１８、および電源装置２０を備えている。図４は、このようなデバイスにおける様々な種類の攻撃ポイントの例を示している。
【０１３１】
本発明の実施形態について、Ｃ（の簡略化された部分集合）で書かれたソースコードを参照しながら説明した。しかし本発明の一実施形態は、幅広い種類の任意の手続き型コンピュータ言語（例えば、C++、Java（登録商標）、Pascal、Fortran、Basic、C#、Perl等)を用いて実施できることについて理解されたい。通常の能力を有するソフトウェアエンジニアであれば、本願に記載されている教示内容を、他の言語に容易に適用することができるであろう。本発明の一実施形態はまた、アセンブリ言語または機械コードなど、コンパイラによって生成可能な低級言語を用いることができ、あるいはこのような言語に適用することができる。
【０１３２】
元の（保護されていない）プログラムを系統的に変換することによって、ソフトウェア全体において検査を行うことができる。これによって、物理的なグリッチ型攻撃からの保護など、本願に記載の技術的利点を実現する、保護されたプログラムを得ることができる。この意味においては、ソフトウェア変換工程のみによって、実際的かつ重要な技術的利点がもたらされる。変換は、手入力、自動によって行うことができ、または、ある程度はこれら両極端の手段の中間を用いて行うことができる（例えば微調整時)。
【０１３３】
検査自体はソフトウェア処理であるため、保護しているプログラムと同類の攻撃に対する抵抗を示すことが望ましい。
【０１３４】
本発明の一実施形態を効果的に実施するために、Ｃコンパイラが上記スキームを過剰最適化してセキュリティが完全に消失しないようにする必要がある。wisbおよびパスを「揮発性の」変数として定義し、直接代入後であってもコンパイラがその値について何も仮定しないようにする必要がある場合がある。
【０１３５】
定数s[]およびe[]は、インクリメント（例えばe[main] - e[f]）の分布が適切に拡散されるように、無作為に選択されることが好ましい。しかし、s[f]およびe[f]を、例えばfのコード開始点のアドレスから、一種のハッシュ技術（SHA-１などの暗号学的ハッシュはここでは不要である)を用いて導き出すことができる。例えば、s[f] =（int)(f)/3; e[f]=(int)(f)。
【０１３６】
個々の検査ステートメントは、任意ではあるが、上記技術を効果的にするためには少なくとも一部は必要であることを理解されたい。検査ステートメントが多いほど、より早く攻撃が検出される。クリティカルな演算（例えばフラッシュ更新またはＩ／Ｏ）の直前の検査を任意だとは考えないという方針にしてもよい。
【０１３７】
なお、上記変換に対して、提供される保護の種類を変化させることのない変更を加えることができることについて理解されたい。また、これらの変更は、特許請求の範囲に明記されている本発明の範囲内であると考えられる。
【０１３８】
例えば、必ずしも加算および減算を用いてwisbを更新する必要はなく、同様の性質を有する他の算術演算を代わりに用いることもできる。一形態としては、加算と減算との両方を排他的論理和演算と置き換えて、更新が“wisb ^= b ^ a”の形式になるようにすることができ、またこのようにして「パス」変数を操作することもできる。
【０１３９】
この種の変数更新を機能させるために必要な代数的性質は、以下の通りである。
【０１４０】
A +（B - A）== B
上記は、機能しているデータ型の値ＡおよびＢのためのものである。これは、通常は整数の部分集合であるが、必ずしもそうでなくてもよい。このような更新は、まず中間値“B - A”を演算して、その中間値に基づいて検査値wisbを調整するか、あるいは、wisbを“+B”および“-A”とは別々に調整するかのいずれかによって行うことができる。後者の場合、まず“+B”の調整を先に行うことが好ましい。なぜなら、“-A”の調整を先に行うことによって、通常は、これら調整の対の間にwisbが一定値（ゼロ）を帯びるからである。これはつまり、このような調整の対の一方の間から、このような調整の対の他方の間への予期せぬジャンプは検出されない可能性があることを意味している。また、負の値の加算は、正の値の減算と同じであるため、加算演算と減算とは本質的に等化であることに留意されたい。
【０１４１】
記号“+”および“-”は、この特性を有する任意の演算によって置換可能である。例えば、
A -（B $ A）== B
(“+”を“-”によって置換し、“-”を“$”によって置換し、B $ A == A - B（オペランドの順序をスワップ）と定義する)
となる。
あるいは、
A ^（B ^ A）== B
(“+”と“-”との両方を“^”によって置換（排他的論理和）)
となる。
【０１４２】
言い換えると、ある種の逆の関係において有効となるためには、これら２つの演算が必要とされる。なお、排他的論理和自身は、この意味において逆の関係（inverse）である。
【０１４３】
前述したように、一実施形態では、制御フローが割り込みされていないＲＡＭ変数を検査として１つ用いる。これは、コード内の異なるポイントにおいて、様々な量でインクリメントされる。いずれかのインクリメントが行われなかった場合、その時点から値は不正確となる。ＲＡＭ変数は、高速検出のために頻繁に検証することができ、あるいは必要に応じて、効率のためにより低い頻度で検証することができる。
【０１４４】
本発明の一実施形態は、以下のいずれか１つまたは１つ以上の利点を有している。
・コンパクト:ＲＡＭ要件が非常に小さい。これは、一実施形態では、ネスト化された各関数コールに対して例えばスタックの１ワード（one word of stack）を用いる代わりに、符号化を行うために１つの変数が用いられるためである。
・簡素:変換が簡素であるため、マクロあるいはその他の自動ツールによって支援可能であり、あるいは完全自動化することができる。
・利便性:上記方法は、何らの構造的変化を加えることなく既存のコードに加えることができる。当該スキームはまた、グローバルプログラムフロー状態機械を演算することなく、コードの小部分に適用可能である。
・柔軟性:カバレージ（coverage）の質は、リソースの許す範囲で低くすることができ、あるいは高くすることができる。
・効率性:挿入される行が短く、実行が早い。
・有効性: スキップされた区域を検出する。制御フローに対する全体的変化を検出する。一旦エラーがセットされると、後のあらゆる時点において検出可能である（複合故障によって１つ以上の検査ステートメントがスキップされた場合であっても）。(例えば、ＵＳ５，２７４，８１７はエラー伝搬特性を有していない。)
本発明の一実施形態を適用できる例としては、パスポートのチップ、スマートカードデバイス、他のハードウェアセキュリティデバイス、および一般的にあらゆるセーフティクリティカルおよびミッションクリティカルなセキュリティデバイスが含まれる。
【０１４５】
提示されている本方法は、プログラムカウンタへの全てのグリッチ攻撃を防止する訳ではない。本方法は、例えば、条件付き分岐命令を不正確に受けさせる（あるいは受けさせないようにする)攻撃の大部分を検出しないであろう。本方法は、わずか一部の命令をスキップさせる故障を検出しない可能性がある。従って、本発明を実施する者は、さらに（例えば）複数のＰＩＮ検査および冗長な計算を追加して、クリティカルな結果を検査しなければならない。
【０１４６】
本発明を実施するプログラムは、コンピュータ可読媒体に記憶させることができ、あるいは、例えば、インターネットウェブページによって供給されるダウンロード可能なデータ信号などの信号に組み込むことができることを理解されたい。特許請求の範囲は、プログラムそのものを網羅するものとして、あるいは担体上の記録として、あるいは信号として、あるいは他の任意の形式にあるものとして解釈される。
【図面の簡単な説明】
【０１４７】
【図１】本発明の第１の実施形態の動作を示す図である。
【図２】本発明の第２の実施形態の動作を示す図である。
【図３】本発明の一実施形態を用いて実施可能な一スキーム（scheme）における様々な段階を示すブロック図である。
【図４】本発明の一実施形態に係る保護されたプログラムを実行するようにプログラムされたデバイスと、そのようなデバイスにおける様々な攻撃ポイントを示すブロック図である。
【図１】
2009525509.tif 000003
【図２】
2009525509.tif 000004
【図３】
2009525509.tif 000005
【図４】
2009525509.tif 000006
【国際調査報告】
2009525509.tif 000007