(57)【要約】実行トレースプリントを検証することによってプログラム実行の整合性を制御する進歩的な方法は、プログラム実行に用いられた実行経路及び／またはデータの典型的なプリントを更新すること、所定のプログラムポイントにおいて（動的に計算された）実際のプリント値を期待値（静的に固定され、プログラム実行が妨げられない場合にプリントの値に等しい）に比較すること、及び実際のプリントが期待値と異なる場合にプログラムによって特定の処理を実行すること、に存する。【特許請求の範囲】
【請求項１】
実行トレースプリントを検証することによってプログラム実行の整合性を制御する方法であって、
・プログラム実行に関する実行経路及び／または処理されたデータを示すトレースプリントを更新するステップと、
・前記プログラムの決定されたポイントにおいて前記トレースプリント（動的に算出された現在値）を（静的に固定されていて、プログラム実行が妨げられない場合にトレースプリントが有するべき値に等しい）期待値と比較するステップと、
・前記現在のトレースプリントが前記期待値とは異なる場合に特別な処理を実行するステップと、
を含むことを特徴とする方法。
【請求項２】
前記現在のトレースプリントが前記期待値と異なる場合に、前記プログラムの前記特別な処理が、決定的であろうとなかろうと、特定のデータを保護するステップ、及び／またはうまく機能していないユーザに音または視覚の信号によって警告するステップ、及び／または前記プログラムの実行を中断するステップから成ることを特徴とする請求項１記載の方法。
【請求項３】
前記トレースプリントは、重要であるとみなされる前記プログラム及び／またはプログラム状態の重要なコード部分にだけ関係することを特徴とする請求項１記載の方法。
【請求項４】
前記トレースプリントが、その１つの引数が前記現在のトレースプリント値でありもう１つの引数がトレースプリント更新の前記ポイント及び時期（プログラム状態及び／またはプログラム実行ポイント及び／または処理されたデータ）における特定の観察データである関数の連続した組成物で、前記プログラムの前記実行経路に沿って、増分的に算出されることを特徴とする請求項１記載の方法。
【請求項５】
前記関数が、≪チェックサム（checksum）≫、線形一致、周期的冗長検査（CRC）、暗号のトレーシングプリント（≪ダイジェスト（digest）≫）若しくは、加算、減算、定数または前記観察データ項目を有する≪or≫排他的論理（≪xor≫）、または固定ビット数の交代、奇数定数による乗算といった演算の組合せの関数の１つから成ることを特徴とする請求項４記載の方法。
【請求項６】
前記トレースプリントが、前記チェックフローのある収束ポイントに到る前に前記実行経路に沿って調整されて、前記収束経路の前記トレースプリントが等しくされることを特徴とする請求項１記載の方法。
【請求項７】
前記調整演算が、定数値へのアサインメント、定数の加算、定数値との≪or≫排他的論理（≪xor≫）といった関数の組合せから成ることを特徴とする請求項６記載の方法。
【請求項８】
前記プログラムのあるポイントにおいて、前記トレースプリントが、前記先行するトレースプリント値から差し引かれるというよりむしろある値に割り当てられることを特徴とする請求項１記載の方法。
【請求項９】
前記プログラムポイントが、その数がある閾値より大きい実行分岐が収束するポイント並びに／または、サブルーチン及び／または例外ハンドラの前記エントリポイントであるポイントであり、前記アサインされた値が所定の値及び／またはランダムな抽出によって決定された何らかの値、並びに／または考慮中に前記プログラムポイントにおいて不変式と前の分析によって決定されたプログラム式であることを特徴とする請求項８記載の方法。
【請求項１０】
前記トレースプリント値が、プログラムポイントにおいて前記期待値と比較され、前記プログラムポイントは前記プログラムの前記チェックフローグラフ中のプログラムポイントの特定の特徴によってかつ／または前記プログラムポイントで実行される演算のタイプによって決定されることを特徴とする請求項１記載の方法。
【請求項１１】
前記プログラムポイントが、前記チェックフローの各々の分岐の後及び／または各々の結合の前、並びに／または不揮発性メモリで書き込む各々の演算の前、並びに／または特定の暗号演算の前、並びに／または特定のライブラリプログラムルーチンに対する呼び出しの前及び／または特定のライブラリプログラムルーチンに対する呼び出しの後、に位置することを特徴とする請求項１０記載の方法。
【請求項１２】
トレースプリント設定（算出及び／または更新及び／または調整及び／またはアサインメント）及び／または制御が、
・前記プログラムコードの装備によって明示的に、かつ／または
・トレースプリント設定及び／または制御演算が（複合の演算から生じている値を含むこと）どのプログラムポイントでかつ／またはどの値を用いてなされるかを前記実行マシンに指示する補完的なプログラム・データに基づいて前記実行マシン（前記実行プラットフォームのバーチャルマシン及び／またはプロセッサ）によって明示的に、かつ／または
・実行された命令の特定の観察に基づいて、前記実行マシン（バーチャルマシン及び／または前記実行プラットフォームのプロセッサ）によって陰的に、
なされることを特徴とする請求項１乃至１１のいずれかに記載の方法、
【請求項１３】
前記プログラムコードの前記装備は、前記トレースプリントを示す変数またはレジスタの明示的な処理、及び／または専用のプログラムルーチンに対する呼び出し、及び／または前記実行マシンの専用の命令の使用、に基づいていることを特徴とする請求項１２記載の方法。
【請求項１４】
前記補完的なプログラム・データは、実行されるべき前記演算を定義しているコードとプログラムポイントを関連させかつ特定の命令を実行する場合に前記実行マシンによって参考にだけされるテーブルにおいてコード化されることを特徴とする請求項１２記載の方法。
【請求項１５】
前記特定の命令が、分岐及び／または不揮発性メモリにおける書き込み及び／またはあるプログラムルーチンへの呼び出し及び／または特定の暗号演算であることを特徴とする請求項１４記載の方法。
【請求項１６】
所定のプログラムポイントにおける前記期待されるトレースプリント値及びトレースプリント調整値が、前記プログラムコード（ソースまたはオブジェクト）の静的分析によって決定され、前記プログラムコードが、いくつかのループ及び再帰をほどくことをシミュレーションすることができ、さらにプログラムコードを修正して前記トレースプリント値を予測可能にしかつ／またはこれらの値を点検することができることを特徴とする請求項１記載の方法。
【請求項１７】
前記分析の目的で、トレースプリント更新（プログラムポイント及びこのプログラムポイントでの実行観察のタイプ）及び／またはトレースプリント調整（トレースプリントが特定の値に調整されなければならないプログラムポイント）及び／またはトレースプリントアサインメント（前記トレースプリントがある値に強制的になされなければならないプログラムポイント）及び／またはトレースプリント制御（前記トレースプリントがチェックされなければならないプログラムポイント）に関する情報が提供され、この情報が、
・請求項６乃至１１のいずれかにおけるような前記方法に従って自動的に決定され、かつ／または
・前記プログラムコードに配置される命令から成っていて、（引数としていかなる整数をとるか否かによらず、プログラムルーチン呼び出しなどの）前記トレースプリントに上で演算をする指令の形で与えられ、かつ／または前記プログラムに補完的なテーブルの形で与えられ、かつ、
・前記分析によって算出される前記値に従って完了され、かつ／または修正されることが可能である、
ことを特徴とする請求項４乃至１６のいずれかに記載の方法。
【請求項１８】
各々のプログラムルーチンに対して、前記期待されるトレースプリント値が、以下の演算手順、即ち、
・調査されるべき全てのプログラムポイントを、第１のプログラムルーチン命令の形をなす別物（singleton）を用いて初期化するステップと、
・前記プログラムルーチン・エントリポイントで、前記所定の初期トレースプリント値に等しいトレースプリント値を記憶するステップと、
・調査されるべき前記一組のプログラムポイントが無効でない限り、
・調査されるべき前記一組のプログラムポイントから１つのプログラムポイント（起点）を抽出するステップと、
・前記命令の実行後に結果として生じる可能なプログラムポイント（目標ポイント）の各々に対して：
*前記目標ポイントがトレースプリントアサインメントを含み、かつ、この目標ポイントがまだ調査されていない場合に、前記目標ポイントにおいて、前記アサインメントによって画定される前記トレースポイント値を記憶するステップと、
*前記目標ポイントがトレースプリントアサインメントを含まず、かつ、この目標ポイントがすでに調査されている場合に、前記起点におけるトレースプリント値を前記目標ポイントにおいて記憶された前記トレースポイント値上へと送出するトレースプリント調整を、前記起点における前記命令と前記目標ポイントにおける前記命令との間に、挿入するステップと、
*前記目標ポイントがトレースプリントアサインメントを含まず、かつ、この目標ポイントがまだ調査されていない場合、前記起点と前記目標ポイントとの間に１つがある場合にトレースプリント更新によって任意に変更される、前記起点における前記トレースプリント値を前記目標ポイントにおいて記憶するステップと、
*前記目標ポイントがまだ調査されていない場合、調査されるべき前記一組のプログラムポイント中の前記目標ポイントを追加するステップと、
によって決定されることを特徴とする請求項１７記載の方法。
【請求項１９】
第１に、前記トレースプリントがそのエントリポイントから（プログラムルーチン呼び出しを含め）前記プログラムの完全な実行に関係し、第２に、請求項１７におけるような前記方法が、前記呼び出されたプログラムルーチンの第１の命令に関する無条件の分岐としての静的プログラムルーチン呼び出しの命令、前記対応する呼び出されたプログラムルーチンの前記第１の命令に関する条件分岐としての前記ダイナミックプログラムルーチン呼び出しの命令、及び前記対応する呼び出しの直後に続く命令の方への分岐としての復帰呼び出しの命令、を処理することによって一組のプログラムルーチンに適用されることを特徴とする請求項１２乃至１８のいずれかに記載の方法。
【請求項２０】
前記プログラム及び／または前記実行マシンが装備されて、前記トレースプリントがプログラムルーチン（例えばプログラムの一部でないかまたは分析されることができないようなプログラムルーチン）に対する特定の呼び出しで保存されて、リターン呼び出しで復帰することを特徴とする請求項１２記載の方法。
【請求項２１】
前記プログラム及び／または前記実行マシンが装備されて、前記トレースプリントが特定のプログラムルーチン（呼び出しの時点で動的に決定されるプログラムルーチンを含む）からの呼び出し及び復帰で調整され、前記トレースプリントが：
・呼び出されたプログラムルーチンのエントリ上で、前記呼び出されたプログラムルーチンの名前及び／または符号定数に依存する値（例えば前記名前及び／または符号定数の暗号トレーシングプリントによって得られる値など）、
・前記呼び出し中のプログラムルーチンにおけるリターン後に、前記呼び出されたプログラムルーチンの前記名前及び／または前記符号定数に同様に依存する値であって、前記プログラムルーチン呼び出しによって関係している各々の例外ハンドラ（即ち、例外が前記呼び出されたプログラムルーチンにおいて持ち上げられる時に影響を及ぼされるかもしれない）が決定された値に前記トレースプリントをアサインしなければいけない、
に等しいように装備されることを特徴とする請求項１２記載の方法。
【請求項２２】
前記トレースプリントが実行マシンによって陰的に更新される場合に、
・前記プログラムの重要でないコード部分を実行する場合、及び／またはプログラム状態が重要であるとみなされない場合に不必要な計算、及び／または特定のプログラムの実行中にトレースプリントチェックを実行していないルーチン、を避けるためにトレースプリント設定が一時的に停止され、
・それが停止されていない場合、トレースプリント設定は各々の実行された命令に関係し、
*その直接の引数のいくつか及び／またはこの命令（例えば前記オペランド・スタックの高さまたは前記オペランド・スタックにおける価値の特定のタイプの存在など）に対するいくつかのプログラム不変式及び／または前記命令が分岐である場合になされた分岐の選択を含み、
* しかし、前記実行された命令が観察されるべき命令の所定のクラスに属するように設けられているので、前記クラスは前記実行マシンに対して固定されるか、さもなくば前記命令が観察されるべきかどうかを命令するあらゆる命令コードをブールに関係付けるテーブルによって与えられ、さらに前記テーブルは様々なプログラムルーチン及び／または様々なプログラムに特有である、
ことを特徴とする請求項３乃至１２のいずれかに記載の方法。
【請求項２３】
・前記トレースプリントに関するいくつかの演算（例えば、トレースプリントアサインメント及び制御など）は、前記プログラムコードに明示的に挿入され、
・前記トレースプリントに関するいくつかの演算（例えば、トレースプリント調整など）は、補完的なプログラム情報に関して前記実行マシンによって明示的に実行され、
・前記トレースプリントに関するいくつかの演算（例えば、トレースプリント更新など）は、前記実行マシンによって陰的に実行される、
ことを特徴とする請求項１２記載の方法。
【請求項２４】
・トレースプリントセット及び／またはチェック演算がプログラムルーチン呼び出しによってなされる場合、前記プログラムはこれらのプログラムルーチンを実行するライブラリによって付随され、実行プラットフォームにロードする場合に、前記ライブラリが特別な実行によっておそらく置換され、
・前記トレースプリントセット及びチェック演算が、補完的なプログラム情報によって表現され、かつ、前記実行プラットフォームが、この情報を用いることを知らず、かつ／または用いることができず、かつ／または用いたくない場合に、前記情報は無視されて整合性制御を用いることなく実行を可能にする、
ことを特徴とする請求項１２記載の方法。
【請求項２５】
前記プログラムの前記実行マシンは、トレースプリント算出及び／またはトレースプリント更新及び／またはトレースプリント調整及び／またはトレースプリントアサインメント及び／またはトレースプリント制御及び／またはプログラムルーチンへの呼び出しに関するトレースプリント保存、及びプログラムルーチンからの復帰に関するトレースプリント回復、に対する専用の命令を有し、これらの命令がプログラムコードにおいて明示的に現れ、かつ／または前記実行マシンを実行するために用いられることを特徴とする請求項１２及び２０のいずれかに記載の方法。
【請求項２６】
実行整合性の制御を可能にする実行システムであって、前記システムが、請求項１乃至２５のいずれかにおいてのような方法に従って、トレースプリント算出及び／またはトレースプリント更新及び／またはトレースプリント調整及び／またはトレースプリントアサインメント及び／またはトレースプリント制御及び／またはプログラムルーチンへの呼び出しに関するトレースプリント保存及びプログラムルーチンからの復帰に関するトレースプリント回復に対する専門化された命令を有するマイクロプロセッサを含むことを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の主題は、実行トレースプリントを検証することによってプログラム実行整合性を制御する方法である。
【０００２】
本発明の主題は、プログラムの実行の整合性を制御することに特に当てはまる。プログラム実行は、実行経路及び／または処理されたデータを表しているトレースプリントを更新し、プログラムの決定されたポイントで現在のトレースプリント値が期待値と比較されることを念頭におく。
【背景技術】
【０００３】
例えばスマートカードなどの小さな埋め込まれたシステムには、システムが含むデータ及びプログラムを保護するように設計されているものがある。特に、これらのシステムの材料基板は、プログラム実行時を含めて、記憶されたデータを観察して修正することを非常に難しくする。
【０００４】
しかしながら、保護は全体的でない。これらのシステムは、システム及びプログラムの正常化を低下させるかまたは秘密の情報を明らかにすることを目的とした、(≪攻撃(attack)≫とも称される)悪意のある行為にさらされているかもしれない。（物質的攻撃とも称される）物理的攻撃は、例えば放射線照射や論理ゲートの破壊などの電力供給妨害である。
【０００５】
攻撃は、カード上で実行されるプログラムの不安定な働きの原因となるかもしれない。メモリから読み込まれる命令及びデータが間違っているかもしれない。さらに、プロセッサがいくつかの命令を不正確に実行するかもしれない。妨害によって、特定の機密に関わる処置を実行する前にセキュリティ状況を点検するコードが無効になるかもしれない。
【０００６】
Ｃ言語で記述されたコードについての以下の簡略化された例を想定する。
【０００７】
if(！condition 1())goto error;
if(！condition 2())goto error;
do_sensitive_action();
２つの条件≪条件1()(condition1())≫及び≪条件2()(condition2())≫が満足する場合に、機密に関わる処置≪機密に関わる処置を実行せよ()(do-sensitive-action())≫が正常に実行されるだけである。それでもなお、物理的妨害は、２つの≪イフ(ifs)≫というコードを直接飛び越すかまたは２つの≪イフ(ifs)≫というコードの一連の様々な命令をメモリから読むことをプロセッサに引き起こすかもしれない。この場合、テスト≪条件1()(condition1())≫及び≪条件2()(condition2())≫が満足されなかったとしても、プロセッサは、≪機密に関わる処置を実行せよ()(do-sensitive-action()≫を実行するかもしれない。
【０００８】
この種の攻撃に対するプログラムを≪強固にする（harden）≫ために周知の１つの技術は、プログラムチェックフローと特定の補助変数の値との間の冗長性を導くことから成る。換言すれば、実行がセキュリティ条件のすべてのチェックを実際に通過した、という事実のトレースを維持するために補助変数が用いられる。上記の例の場合には、それは次のように記述されてもよい：
trace=0;
if(condition1()trace|=1;else goto error;
if(condition2()trace|=2;else goto error;
if(trace= = 3)do_sensitive_action();
従って、最初の２つの≪イフ(ifs)≫が正しく実行されない場合、≪トレース(trace)≫変数が最後に３に等しくなく、その結果、演算≪機密に関わる処置を実行せよ()(do_sensitive_action())≫が実行されないという見通しがある。
【０００９】
この場合でさえ、妨害によって、テスト≪トレース==3(trace==3)≫がいつでも真であるかまたは同様に無視されるということを引き起こされるだろう。概して、本願明細書において開示される本発明の関連性に対して、物理的攻撃によって生じる妨害が比較的洗練されていないと考えられている。それらはプログラムの一部の実行を機能させなくなることができるかまたはメモリの一部の見た目に明らかな内容を変えることができるが、この一部の範囲は攻撃者によって細かく制御されていない。
【００１０】
この方法は、以下のように一般化され得る。プログラムは、その実行が通過する重要なコントロールポイントを表している値を更新する。この値は、例えばこれらの重要なコントロールポイントを特徴づける整数で計算されたチェックサムなどであるトレースプリントであってもよい。この機密に関わる演算を実行する前に、実行の間に更新されるこの値が、プログラムの制御構造からプログラマによって手作業で事前に計算されたその通常の（期待される）値と比較されてもよい。例えば、
trace= 42：
for(i = 0;i<4;i++)｛
if(provided_pin[i]！=actual_pin[i]goto error;
trace= h(trace,i);
]
if(trace== 2346)do_sensitive_action();
しかしながら、ＰＩＮコードはこのような方法で通常チェックされないことが注目されるべきである。これは、トレースプリント計算の使用法を説明するための単なる例である。
【００１１】
ここで用いられるトレースプリント演算子は、線形合同≪h(t,x) =（（33*t）mod(2^16)）xor x≫であり、そこで
・≪a * b≫は≪a≫に≪b≫を掛けた積を表す
・≪a mod b≫は≪a≫を≪b≫で除算した余りを表す（即ちモジュロである）
・≪a^b≫は≪a≫を≪b≫累乗することを表す
・≪a xor b≫は、≪a≫及び≪b≫を表すビット上で≪or排他的論理≫演算である
値２３４６は、≪h(h(h(h(42,0),1),2),3)≫、即ち、ループ（０から３の変数≪i≫毎に４ターン）の正常実行のトレースプリント以外でない。ループが、実行されないかまたは４ターンをする前に異常終了する場合、≪機密に関わる処置を実行せよ()(do_sensitive_action())≫呼び出しの前に≪トレース(trace)≫変数の値は２３４６とほとんど異なっているだろう。
【００１２】
このトレーシングプリント演算子「ｈ」は、重要な制御ポイントを特徴づける一連の整数を演算するトレーシングプリント関数「Ｈ」の増分演算を可能にする演算子と判断され得る。観察手順に関するこのトレーシングプリント関数は、≪H(T0,i1,i2、…、in)=h(…h(h(T0,i1)、i2)…、in)≫によって定義される。
【００１３】
それが低い演算能力を有する小さな埋め込みシステムで用いられてもよいように、≪h≫トレーシングプリント演算子は計算するのに速くなければならない。また、結果として生じる≪H≫トレーシングプリント関数は、事前イメージ耐久性でなければならない。ランダムシーケンス≪(T0,i1,…,in) ≫のトレースプリント≪H(T0、i1,…in) ≫が所定の値と等しいという蓋然性が、（Ｂがトレースポイント値をコード化するためのビット数である、２-Bという次数において）低くなければならない。
【００１４】
以下に説明するいくつかの場合において、その第１の引数において可逆的であるトレーシングプリント演算子≪h≫を有することも役に立つかもしれない。全ての値≪t'≫及び≪x≫に対して、≪t≫が≪t'=h(t,x)≫であるように存在する。
【００１５】
上記にあげた例における場合のように、例えば、≪h≫に対する線形合同を用いることが可能である。この線形合同も可逆的であるという特性を有する。より一般的には、以下の演算を結合するいかなる関数が用いられてもよい。即ち、加算、減算または、定数または≪x≫を用いる排他的論理（xor）、固定数ビットの循環、奇数定数による乗算、である。
【００１６】
また、例えばＣＲＣ−１６などの周期的冗長検査（ＣＲＣ）を用いることが可能である。関数は、事前に演算されたテーブルを用いて効率的に計算されてもよい。
【００１７】
その一方、整合引数を有する整数の合計として定義されるチェックサムが、速算、事前イメージ抵抗及び変換性という良い特性を有しているとしても、チェックサムはほとんど満足でない。なんとなれば、得られるトレーシングプリント関数が引数の順序に無関心だからである。
【００１８】
その対極に、非常に安全であるが算出するのに非常に高価でもある、暗号法トレーシングプリント関数（例えばＳＨＡ−１、ＭＤ−５などの適用）がある。
【００１９】
トレースプリント設定は、トレースプリントアサインメント及びトレースプリント更新という２つの主演算によってなされ得る。≪セットトレース(T)(setTrace(T))≫は≪T≫（通常いかなる値でも）においてトレースプリントの初期値を固定する。そして、「アッドトレース(N)(addTrace(N))」は整数「Ｎ」をプログラム実行の観察の特徴を示すトレースに加える。上記の例では、≪セットトレース(T)(setTrace(T))≫は、アサインメント≪トレース=T（trace=T）≫に対応する。さらに、≪アッドトレース(N)((addTrace(N))≫は≪トレース=h（トレース,n）（trace=h(trace,N))≫によってトレースプリントの更新に対応する。
【００２０】
演算≪アッドトレース(N)((addTrace(N))≫の間に供給される値「Ｎ」は、それ自体がトレーシングプリント関数の結果であってもよい。整数≪N≫がプログラムの局部的実行を表現すればするほど、即ち、起こり得る実行妨害の出現において≪N≫が変化すればするほど、攻撃の検出力がより高くなる。
【００２１】
トレースプリント制御は、単一の演算を用いてなされてもよい。≪チェックトレース(T)(checkTrace(T))≫は、トレースプリントの現在値が実際に≪T≫であることを確認する。そうでない場合には、それはプログラムが攻撃を受けたということを示すものである。厳密に言えば、スマートカードなどのシステムが使い古して、トレースプリントの相違も、材料の不良の表われであるかもしれない。
【００２２】
いずれにしても、プログラムは、プログラムがそのために設計されたサービスをもはや提供することができない。重要なシステムにおいて、かかる状況下でとられる手段は、決定的であろうとなかろうと、通常、いくつかのプログラムデータを保護することとプログラム実行を中断することとから成る。具体的に可能なときに、音または視覚の信号によって、うまく機能していないことをユーザに警告してもよい。
【００２３】
上記の実行例に照らして、この技術を実行することは、第１にトレースプリントの算出ステップを挿入するために、そして、第２にチェックされるべきポイントにおいて期待されるトレースプリント値を算出するために、プログラマの一部に多くの努力を要求することは明らかである。
【発明の開示】
【発明が解決しようとする課題】
【００２４】
上記に提示した問題を考慮して、本発明の目的は、とりわけ、この技術の一般化及びその自動化である。
【課題を解決するための手段】
【００２５】
この目的のために、以下によって実行トレースのトレースプリントを検証することによりプログラム実行の整合性を制御する方法が提案される。即ち、
・プログラム実行の間に、実行経路及び／または処理されたデータを示すトレースプリント更新するステップと、
・プログラムの所定のポイントで、該トレースプリント（動的に算出される現在値）を期待値（静的に固定されていて、プログラム実行が妨げられない場合にトレースプリントが有しなければならない値に等しい）と比較するステップと、
・現在のトレースプリントが期待値とは異なる場合に、特別な処理を実行するステップと、
によってである。
【００２６】
この方法は、以下を考慮に入れてもよい。
・トレースプリントは、プログラムの重要なコード部分に関係するだけである。
・プログラムの所定のポイントにおいて、トレースプリントの期待値が、トレースプリント値が予測可能であるように、プログラムコードを任意に修正してもよい静的プログラム分析によって決定される。
【発明を実施するための形態】
【００２７】
この方法及びその改良は、制限的でない例として以下により詳細に記載されている。
【００２８】
期待されるトレースプリント値を決定するプログラム分析は、いくつかのステップに分割され得る。先ず、プログラムのプログラムルーチン（方法、サブプログラム、その他）が考慮される。
【００２９】
トレースプリント制御ポイントからプログラムルーチンのスタートを切り離す全ての命令が線形である場合、即ち、いかなる分岐も含まない場合、トレースプリントの期待値は単に≪h(…h(h(T0,i1),i2)…,in)≫である。ここで、≪T0≫はトレースプリントの初期値であり、≪i1,…,i2≫は実行経路上のさまざまな観察ポイントにおける実行を示す整数である。
【００３０】
より一般的に、トレースプリントの値が１つの基本的ブロックの開始時に静的に周知の場合、プログラムルーチンがいくつかの基本的ブロックに分けられた時から、その値はブロックのあらゆるポイントで同様に周知である。
【００３１】
異なるいくつかの実行経路が１つの同じプログラムポイントに至る場合、このプログラムポイントでの≪該(the)≫期待されるトレースプリント値を予測することはできない。なんとなれば、そのうちのいくつかがあるからである。この場合においては、トレースプリント値は、チェックフロー中の結合ポイントにおいて≪等しくなされて（equalized）≫いる。（おそらく分岐のうちの１つを除いては）結合ポイントに至る各分岐において、定数値が現在のトレースプリントに加えられて、その結果生じるトレースプリントが各々の分岐に対して同じものである。この加算は、例えばトレースプリント値に関する直接の演算または専用のプログラムルーチンに対する呼び出しなどのコードにおいて明示的になされ得る。プログラムを例えば以下にしてみよう。
【００３２】
if(cond)｛
addTrace(1);
…
addTrace(2);
｝elese｛
addTrace(3);
…
addTrace(4);
]
トレースプリントが≪イフ(if)≫の前に値≪T0≫を有する場合、この≪イフ(if)≫の２つの分岐の各々の終わりにおいて、値≪h(h(T0,1),2) ≫及び ≪h(h(T0,3),4)≫をそれぞれ有する。
この≪イフ(if)≫の後にトレースプリント制御ポイントを定めるために、次のように分岐を等しくすることが可能である。即ち、
if(cond)｛
addTrace(1);
…
addTrace(2);
｝else｛
addTrace(3);
…
addTrace(4);
adjustTrace(X);
｝
checkTrace(Y);
であって、以下の定義を有する。
・≪アジャストトレース(N)(adjustTrace(N))≫は、トレースプリントの現在値に整数≪N≫を加える
・≪X≫は、≪h(h(T0,1),2)−h(h(T0,3),4)≫,
・≪Y≫は、≪h(h(T0,1),2)≫
従って、取られる実行経路にかかわりなく、トレースプリントは、常に≪イフ(if)≫の後、≪Y≫に等しい。トレースプリントの現在値に値≪X≫を加える事実は、偽造するのが困難であるという事実を維持すると同時に、このトレースプリントを予測可能にする。調整が、≪イフ(if)≫の２番目の分岐上よりむしろ１番目の分岐上で対称の形でなされるかもしれない。
【００３３】
この図式は、繰り返しの数が未定であるループの場合にもあてはまる。各々の繰り返しに関して、トレースプリントが、同じ初期値に戻るように調整される。
【００３４】
トレースプリント調整演算≪アジャストトレース(adjustTrace)≫は、演算（≪アッドトレース(addTrace)）を更新するトレースプリント及びトレースプリントアサインメント演算（≪セットトレース(setTrace)≫）に加えられて、一組の≪トレースプリントセット(trace print set)≫演算を形成する。
【００３５】
トレースプリント調整演算≪アジャストトレース(N)(adjustTrace(N))≫は、必ずしも≪トレース=トレース+N;（trace =trace+N;）≫のタイプの加算演算に基づく演算である必要はない。それは、より一般的には、≪トレース=アジャスト（トレース,N）;trace=adjust(trace,N); ≫として定義され得る。そこで、≪アジャストトレース(T,N) ((adjust(T,N)))がその第１の引数において可逆的な関数である。いかなる始点≪T≫のトレースプリント及びいかなる目標トレースプリント≪T'≫に対しても、知ることが必要とされる全ては、≪アジャストトレース(T,N) = T'( adjust(T,N) = T')≫であるようにどのように≪N = デルタ(T,T')(N = delta(T,T'))≫を決定するかである。
【００３６】
このように、加算：≪アジャスト(T,N) = T + N (adjust(T,N) = T + N)≫及び≪delta(T,T')=T'−T≫が見つけられる。しかし、例えば≪or排他的論理≫、≪アジャスト(T,N) = T xor N (adjust(T,N) = T xor N) ≫及び≪デルタ(T,T')=T xor T'(delta(T,T')=T xor T')≫を用いることも可能である。トレースプリント調整≪アジャストトレース(デルタ(T,T')); (adjustTrace(delta(T,T'));) ≫は、難しい偽証を保持する間に、トレースプリント≪T’≫上へトレースプリント≪T≫を送出する。
【００３７】
プログラムの例外ハンドラは、静的にトレースプリント値を決定することを難しくする。実行は、このハンドラによってカバーされるいかなる命令からも、ハンドラコードの開始上へとそれ自体を接続することができる。よって、ハンドラコードの開始時にトレースプリント値は、静的に予測できない。上記の通りの例外ハンドラによってカバーされる全ての命令のトレースプリント調整の挿入は、理論的にはハンドラの開始時に周知のトレースプリント値を確実にすることを可能にする。しかしながら、必要な調整の数が多いので、特に調整が≪アジャストトレース(N)(adjustTrace(N))≫タイプのプログラムルーチン呼び出しによって明示的にコード化される場合、これはコードサイズに関して高価であるかもしれない。加えて、調整は、例外ハンドラによってカバーされるコードの全区間にわたってトレースプリントを一定にする悪影響を有するだろう。そのときトレースプリントは、実行妨害を検出することにおいて効果がない。
【００３８】
実行が例外ハンドラに入るときに、この問題に対する１つの解決はトレースプリントを静的に周知の値に強制的にすることである。このことは、例外回復を処理するときに、バーチャルマシンのインタプリタによってなされてもよい。他の可能性は、≪T≫が任意に選ばれた値であるそれぞれの例外ハンドラの開始時に、プログラムルーチン≪セットトレース(T)(setTrace(T))≫に呼び出しを挿入することである。
【００３９】
この解決法を用いると、実行整合性制御の特性は、分岐に先んじる実行部分とそれに続く部分との間で局部的に失われる。しかし、実行整合性制御の特性は、プログラム実行全体にわたって全体的に保持されたままである。
【００４０】
この方法は、より一般的には、プログラムルーチンチェックフローの全ての強い収束ポイントに適用されてもよい。
【００４１】
≪ジャバ(Java)（登録商標）≫バーチャルマシン（JVM）または≪ジャバカード(Java Card)（登録商標）≫（JCVM）（サンマイクロシステムズ(Sun Mycrosystems)によって登録されている商標）の言語などの言語において、サブルーチンは例えば同様の問題を提起する。サブルーチンは、トレースプリントに対して異なる値を有するコードのいくつかのポイントから呼び出されてもよい。サブルーチンは、サブルーチンに入る場合に、トレースプリント値を強制することによって、例外ハンドラと同じ方法で処理されてもよい。サブルーチン呼び出しポイントがうまく区切られ、（例えばJVM及びJCVMの≪jsr≫命令）、概して数がほとんどないので、それらは、サブルーチン呼び出しの前の≪アジャストトレース(adjustTrace)≫への呼び出しの挿入を用いて通常の分岐として処理されて、１つの同じサブルーチンの全ての呼び出しポイントで１つの同じトレースを保証することができる。
【００４２】
同様に、トレースプリント算出及びその制御は、常にプログラムの重要コード部分に限られていてもよい。トレースプリント上で演算によって表されるような冗長を導くときに、このことがコードのサイズ増加を減少させることを可能にする。このことは、同様に、プログラムの追加の演算による低速化を減少させる。
【００４３】
トレースプリント上の演算は、プログラム演算（妨害がない場合）を修正しない。（≪アッドトレース(addTrace)≫タイプの）演算を更新するトレースプリント及び（≪アジャストトレース(adjustTrace)≫タイプの）トレースプリント調整演算は、プログラム実行ポイントとリンクしているチェックフローグラフのアーク上に概念的に配置される。このような方法で、トレースプリント更新及び調整が、実行の間カバーされるプログラムポイントだけでなく、いくつかの分岐が２つの同じポイントをリンクする場合を含むことに続く特定の分岐にも依存する。実際問題として、トレースプリント更新及び調整演算が効果的に実行可能プログラムコードに挿入されるときに、それらは、それらが配置されるアークの２つのプログラムポイントの間で、順番に実行されるように配置される。この挿入は、付加的な分岐の追加などのプログラムの軽微な局部的な変更を要求してもよい。
【００４４】
その一方、（≪セットトレース(setTrace)≫タイプの）アサインメント演算及び（≪チェックトレース(checkTrace)≫タイプの）トレースポイント制御演算は、プログラムポイント上に概念的に配置されるか、これらのポイントの間でアーク以外の上に配置される。トレースプリント値は、プログラムポイントの特性である。所定のプログラムポイントに至る実行経路にかかわりなく、（動的に算出した）トレースプリントの現在値は、（静的に周知の）期待される固定値に等しくなければならない。さらに、この期待値は、トレースプリントアサインメント演算によって強制されてもよい。
【００４５】
プログラムルーチンの各々の実行ポイントにおけるトレースプリント値及びトレースプリントを予測可能にするために挿入されるべき調整が、静的プログラム分析によって自動的に決定されてもよい。静的プログラム分析はトレースプリントを予測可能にしそれらを制御するために任意にプログラムコードを修正する。
【００４６】
この目的のために、使用は、プログラムルーチン、並びに、トレースプリント更新（プログラムポイント及びこのプログラムポイントでの実行観察の種類）に関するデータ、トレースプリントアサインメント（トレースプリントが特定の値に強制されなければならないプログラムポイント）に関するデータ、及び任意でトレースプリント制御（トレースプリントが点検されなければならないプログラムポイント）に関するデータでできている。
【００４７】
トレースプリント更新、アサインメント及び制御に関する情報は、例えば、プログラムコードにおける命令（コメント、プラグマ、効果的に実行されたコード、その他）の明示的な挿入によって与えられてもよい。かかる指令は、プログラム・チェックフローに関する所定の中立な考慮として与えられる。≪アッドトレース(addTrace)≫タイプのトレースプリント更新指令は、プログラムの（指令を除外する）２つの効果的実行位置の間に位置する。従って、概念的にプログラムを結びつけるアークに関して、トレースプリントアサインメント指令（≪セットトレース(setTrace)≫）及びトレースプリントチェック指令（≪チェックトレース(checkTrace)≫）はあとに続いている実行位置に関連する。同じことは、プログラム変換によって任意に挿入される指令にあてはまる。≪アジャストトレース(adjustTrace)≫タイプの調整指令は、同様に、（プログラムポイントに着く前にトレースプリント値を訂正するために）アーク上に、即ち、２つの実行位置の間に位置する。
【００４８】
トレースプリントアサインメント指令は、従来のプログラム変換によって適当に導入されてもよい。実行分岐の数が所定の閾値より多い多くの実行分岐が集中するプログラムポイント毎に、この変換はたとえば組織的に≪セットトレース(setTrace)≫タイプの指令を配置してもよい。指令は、同様に、サブルーチン及び／または例外ハンドラ毎のエントリポイントにおいて組織的に配置されてもよい。
【００４９】
同様に、トレースプリント更新指令によって処理される値は、従来のプログラム変換によって前もって決定されていてもよい。この更新に用いられる値（≪アッドトレース(addTrace)≫引数）は、一般に任意の定数である。従って、いかなる値（例えばランダム値など）が、指令の各々の出現に自動的に割り当てられてもよい。場合によっては、プログラムの不変式を用いることが望まれるかもしれない。この場合に、プログラムの静的分析が行われて、例えば、２つの変数の合計が一定であるという事実、変数が特定の閾値未満であるという事実、ループ繰り返しの数が周知であるという事実などといったあるプログラムポイントにおける不変式、を決定するために実行される。続いて、定数に関してトレースプリントを更新する代わりに、式がダイナミックプログラムに関連していたとしても、一定の値を有していなければならない式が用いられる。
【００５０】
期待されるトレースプリント値を自動的に決定する方法は、そのとき、以下の演算手順によって定義される。即ち、
・第１のプログラムルーチンの命令の形をなす別物（singleton）によって、調査されるべき全てのプログラムポイントを初期化するステップと、
・プログラムルーチンエントリポイントで、得られた最初のトレースプリント値に等しいトレースプリント値を記憶するステップと、
・調査されるべき一組のプログラムポイントが無効でない限り、
・調査されるべき一組のプログラムポイントから１つのプログラムポイント（起点）を抽出するステップと、
・命令の実行後に生じる可能なプログラムポイント（目標ポイント）の各々に対して、
目標ポイントがトレースプリントアサインメントを含み、かつ、この目標ポイントがまだ調査されていない場合、アサインメントによって定義されるトレースプリント値を目標ポイントで記憶するステップと、
目標ポイントがトレースプリントアサインメントを含まず、かつ、この目標ポイントがすでに調査されている場合、起点における命令と目標ポイントにおける命令との間に、目標ポイントにおいて記憶されたトレースにプリント値上へと起点におけるトレースプリント値を送出するトレースプリント調整を挿入するステップと、
目標ポイントがトレースプリントアサインメントを含まず、かつ、この目標ポイントがまだ調査されていない場合、起点と目標ポイントとの間に１つが存在する場合にトレースプリント更新によって任意に変更される起点におけるトレースプリント値を、目標ポイントで記憶するステップと、
目標ポイントがまだ調査されていない場合、調査されるべき一組のプログラムポイントにおいて目標ポイントを加えるステップと、
によってである。
【００５１】
いくつかの言語は、上記に説明したようなタイプトレースプリントセット及びトレースプリントチェックの中立の指令の簡単な取り扱いを許容しない。この場合、実際の命令を用いてプログラムコードを装備することから成る技術が用いられてもよい。
【００５２】
例えば、明示的なプログラムルーチン呼び出しが、トレースプリント更新及びアサインメントとトレースプリント制御との両方に対して、プログラムコードの中に挿入されてもよい。例えば≪ジャバ(Java)（登録商標）≫では、それは以下のように書かれる。即ち、
｛
…
if（cond）｛
a[i+j] = b[i];
addTrace();
｝
checkTrace();
｝
catch(Exception e)｛
setTrace();
…
｝
このプログラム部分は、更新演算及びアサインメント演算に対して任意のトレースプリント値を割り当てるために一度目を変更してもよい。
｛
…
（if（cond）｛
a[i+j] = b[i];
addTrace(28935);
｝
checkTrace();
｝
catch(Exception e)｛
setTrace(9056);
…
｝
次に、プログラムは、制御ポイントでのトレースプリント値を決定しかつ必要な調整を挿入するために、上記の方法を用いて二度目を変換してもよい。この変換によってアサインされる値は、用いられるトレーシングプリント演算子に依存する。上記に例として与えられたプログラム部分は、次のように変換されてもよい。
【００５３】
｛
…
if（cond）｛
a[i+j] = b[i];
addTrace(28935);
adjustTrace(16220);
｝
checkTrace(13991);
｝
catch（Exception e）｛
setTrace(9056);
…
｝
例えばデバッグすることなどの、変換前のプログラムをコンパイルしかつ実行する可能性を有することが望ましい場合、ソースプログラムを適応させることが要求されてもよい。トレースプリントセット及びチェックライブラリが、引数に対して整数を用いるプログラムルーチンを含むだけの場合、≪チェックトレース()(checkTrace())≫を記述することは不正である。この場合、以下の仕様が用いられてもよい。（例えば）値≪0≫は、未だ決定されない値を示す。次に、≪チェックトレース()(checkTrace())≫が、最初のソースコードに記述される。変換後、プログラムルーチン呼び出しは、例えば≪チェックトレース(13991)(checkTrace(13991))≫になるだろう。
【００５４】
この技術は、プログラムコンパイリングと互換性を持つ。プログラム変換が、ソースコードに関してとオブジェクトコードに関してとの両方になされてもよい。例えば、≪ジャバカード(JavaCard)（登録商標）≫において、以下のように記述されてもよい。
【００５５】
checkTrace();
JCVMの実行フォーマットへコンパイルして変換した後、オブジェクトコードは、
sconst_0
invokestatic checkTrace
の形式で得られる。
【００５６】
≪インヴォークスタティック（invokestatic）≫上の期待されるトレースプリント値を自動的に判定する方法は、JCVMオブジェクトコードに用いられて、以下のコードを生成してもよい。
【００５７】
sspush 13991
invokestatic checkTrace
自動的にトレースプリント値決定するこの方法は、プログラムループ及び再帰の巻き戻しを場合によっては実行するプログラム分析と組み合わされてもよい。そのとき、自動算出は、≪トレース=h(トレース,i)(trace=h(trace,i))≫がインデックス≪i≫のループ内にある上記の例においてのように、プログラム変数に関するトレースプリントで可能である。
【００５８】
トレースプリントは、プログラムコード中に明示的に挿入される所定の観察ポイントから、上記に示したように算出されてもよい。トレースプリントは、また、バーチャルマシンのインタプリタによって自動的にかつ陰的に算出されてもよい。
【００５９】
特に、トレースプリントが、バーチャルマシンによって実行される命令コードに関係してもよい。このような方法で、プログラム命令の連続的な実行が妨げられないことが確認されてもよい。
【００６０】
バーチャルマシンのインタプリタの主ループは、一般に以下の形式を有する。即ち、
while(1)｛
//Reading of instruction code at pc address
opcode = *pc++
switch(opcode)｛
case INSTR：
//Instruction semantics≪instr≫
…
｝
｝
である。
【００６１】
このコードは、次のように装備されてもよい。即ち、
while(1)｛
opcode = *pc++;
addTrace(opcode);
switch(opcode)｛
…
｝
｝
である。
【００６２】
差し当たっては、演算≪アッドトレース(addTrace)≫と関連する≪トレース(trace)≫変数が、各々のプログラムルーチン呼び出しにおいて、呼び出し側プログラムルーチンの起動ブロックにおいて保存され、かつ周知の値≪T0≫で再初期化されるということ、さらに、各々のプログラムルーチン復帰上の呼び出し側の起動ブロックから対称的に回復するということが考えられる。従って、プログラムのいかなるポイントでも、≪トレース(trace)≫の値は、呼び出された方法の命令を無視して、現在のプログラムルーチンにおけるエントリ後に実行される命令の演算コード≪i1、…、i2≫のトレースプリントである≪Tn = h(…h(h(T0、i1)、i2),…,in) ≫である。
【００６３】
この間接的なトレースプリント更新は、期待されるトレースプリント値の自動決定について上記で説明した方法によって、明示的にかつ自動的に考慮に入れられてもよい。バーチャルマシンで見えるプログラムの不変式が、トレースプリント更新のために用いられてもよい。即ち、オペランドスタックの高さ、（スタックがタイプされる場合、または、データがそれらのタイプの識別を可能にする場合に）オペランドスタックにおけるある種の値の出現、である。
【００６４】
バーチャルマシンによる間接的なトレースプリント算出用モデルは、ネイティブコードを実行しているマイクロプロセッサの場合に直接置き換えられてもよい。そうするために、マイクロプロセッサは、各々の実行された命令に対してトレースプリントを更新されるように設計されていなければならない。この方法で、≪トレース（trace）≫変数は、（入退出手順に関するトレース値を保存しかつ復帰するための）≪ロード(load)≫及び≪ストア(store)≫タイプ、（トレース値を修正しかつ初期化するための）≪addi≫及び≪movi≫の命令を介してアクセスされる、プロセッサの特別なレジスタになる。
【００６５】
実際的な視点から、トレースプリント設定は、プロセッサの重要な経路がわずかに低速化されるようになされなければならない。それはまた、重要なコードセクションでトレースプリント算出を実行することだけを可能にする、プロセッサの開放可能な機能モードであってもよい。この種の動的開放は、また、バーチャルマシンによる間接的なトレースプリント算出のために用いられてもよい。
【００６６】
トレースプリント算出を加速するための他の可能性は、プロセッサがハードウェアにおいて更新演算≪トレース= h(トレース（x）;)(trace= h(trace（x）;))≫を実行する命令を有することである。このマシン命令が、バーチャルマシンの解釈ループにおいてとネイティブコードにおいてとの両方で用いられてもよい。それはマシンコードの変換によって自動的に挿入されてもよい。プロセッサは、また、専用の命令を含み、トレースプリント調整演算、アサインメント演算及び制御演算を実行してもよい。
【００６７】
専用の命令は、また、バーチャルマシンの一組の命令に明示的に含まれてもよい。≪トレース(trace)≫変数に関して明示的に演算するかまたは≪アッドトレース(N) (addTrace(N))≫、≪セットトレース(T)(setTrace(T))≫、≪アジャストトレース(N))(adjustTrace(N))≫、及び≪チェックトレース(T)(checkTrace(T))≫といったタイプのプログラムルーチン呼び出しを生成する代わりに、これらの演算が、バーチャルマシンの専用の命令によって実行されてもよい。この場合、トレースプリント算出は陰的でない。それは、明示的であり、（任意に自動の）プログラムの装備を必要とする。
【００６８】
この方法の有利な点は、速度の増加だけでだけでなくメモリサイズの増加でもある。例えば、JCVMオブジェクトコードにおいて呼び出し≪チェックトレース(42)(checkTrace(42))≫によって必要とされる６オクテットの代わりに、３オクテット（命令のための１及び短い整数引数に対する２）だけ必要になるだろう。トレースプリントが、実行マシン（バーチャルマシンまたはプロセッサ）によって自動的にかつ陰的に更新される場合、いくつかの改良が意図されてもよい。
【００６９】
第１に、トレースプリント設定による実行時間に関する余分の費用を減らすために、命令のいくつかのクラスに対するトレースプリントを変更しないことが考慮されてもよい。これは、命令がトレースされるべきかどうかを指示するあらゆる命令コードをブールに関係付けるテーブルを用いてなされてもよい。インタプリタの主ループは、そのとき次のように記述される：
while(1)｛
opcode = *pc++;
if（update_trace[opcode]
trace= h(trace、opcode);
switch（opcode）｛
…
｝
｝
効率的にトレースされるべき命令に関する情報が（ここではテーブル≪アップデートトレース(update_trace)≫）、情報がロードされて実行プラットフォームで実行される間、プログラムを伴ってもよい。この情報は、プログラムに従って、さらに、様々なプログラムの様々なプログラムルーチンによっても変化することができる。
【００７０】
また、様々な命令コードに対応する場合のインタプリタにおいてこの情報を≪強固に(hard)≫コード化することは可能である。例えば、これは、
while(1)｛
opcode = *pc++;
switch（opcode）｛
case INSTRI：//trace
trace= h(trace、opcode);
…
case INSTR2：//no torace
…
｝
｝
命令の直接の引数の値に関するなんらかの妨害も検出するために、トレースプリント算出において直接の引数を統合することも可能である。例えば、JCVMにおいて、（それは、オペランドスタック上への整数の定数≪n）をプッシュする）命令≪bspush n≫に対して、インタプリタが、単に≪トレース= h(トレース,BSPUSH)(trace = h(trace,BSPUSH))≫の代わりに≪トレース= h(h(トレース、BSPUSH,n)(trace= h(h(trace、BSPUSH,n)) ≫を実行することができる。
【００７１】
トレースプリント値の静的算出の可能性を維持するために、この図式は、その直接の引数がローディング時に変更されない命令にだけリンク時に適用され得る。そうでない場合には、リンク編集後にプログラム上で演算することができることが可能でなければならない。このことは、例えば、プログラムがスマートカードのマスク内のリードオンリーメモリ（ROM）に含まれる場合に可能である。
【００７２】
プログラムルーチンのコード内で効果的に続くチェックフローに対してトレースプリント値をより敏感にするために、条件つきの分岐命令（例えばJCVMの≪イフゼロ(ifzero) ≫）及び多数分岐命令（例えばJCVMの≪ステーブルスイッチ(stableswitch)≫）が、条件つきの分岐がされるか否かに依存して、または選択されたジャンプテーブルのエントリに依存して、異なってトレースを更新することができる。例えば、これは、
switch（opcode）｛
case IFZERO：
if(top_of_stack == 0)｛
trace= h(trace,BRANCH_TAKEN);
pc+=pc[0];
｝else｛
trace= h(trace,BRANCH_NOT_TAKEN);
pc+=1;
]
…
を与える。
【００７３】
この改良は、また、命令≪イフゼロ(ifzero)≫の分岐の各々において、即ち、≪真(true)≫及び≪偽(false)≫のそれぞれにおいて、式≪スタックの頂部 == 0(top_of_stack == 0)≫の周知の値を考慮に入れるとみられてもよい。
【００７４】
全ての上記の説明において、トレースプリントは、プログラムルーチンによる算出されたプログラムルーチンである。目的がなく、この変数の値を調べない、即ち≪チェックトレース(checkTrace)≫のタイプ演算を含まないプログラムルーチンをインタプリティングする場合に変数≪トレース(trace)≫を更新することにおいて、実行時間に関して潜在的に高価である。プログラムルーチンが≪チェックトレース(checkTrace)≫演算を含むかどうか指示する情報が、プログラムルーチンコードの簡単な審査によって容易に決定されてもよい。
【００７５】
バーチャルマシンのインタプリタは、次のように変更されてもよい。
【００７６】
while(1)｛
opcode = *pc++;
if(method_flags & NEEDS_TRACE)
trace = h(trace, opcode)
switch（opcode）｛
…
｝
｝
JCVMの特定の場合において、例えば、この情報が、（例えばプログラムローディングに関して）きっぱりと算出され、構造≪メソッドインフォ(method_info)≫の≪フラッグス(flags)≫フィールドにおいてビット形式で保存されてもよい。
【００７７】
現在まで、実行トレースプリントは各々の方法に対して局部的であるとみなされてきた。変数≪トレース（trace）≫がプログラムルーチン呼び出し上で保存され、その値は、呼び出されたプログラムルーチンを除いて、現在のプログラムルーチンの範囲内で実行観察ポイントのトレースプリントを表す。変数≪トレース(trace)≫が全体的になされてもよく、従って、≪トレース(trace)≫が周知の値で初期化された周知のエントリポイント（例えば、≪ジャバカード(Javacard)（登録商法）≫アプレットの≪プロセス(process)≫及び≪インストール(install)≫方法）から、プログラムルーチン呼び出しを介すること含む、全ての実行命令の全てのトレースプリントを含んでもよい。
【００７８】
理由は二重である。先ず、単一の≪チェックトレース(checkTrace)≫演算において、プログラムの完全な実行における、かつ、ちょうど≪チェックトレース(checkTrace)≫があるプログラムルーチンの実行においてでなく、妨害の欠如を制御する可能性であり、次に、トレースプリントが実行マシンによって陰的にセットされる場合に対して、このマシンの簡略化（各々の呼び出し上の≪トレース(trace)≫）を保存して元に戻すことはもはや必要ない）である。
【００７９】
この方法での主な問題点は、プログラムポイント毎のトレースプリント値の静的算出である。この算出は、可能なままであるが、完全なプログラム（相互手続き的な）の分析かまたは各々のプログラムルーチンの開始時及び終了時においてトレースプリント値に関する不変式を決めることのいずれかを必要とする。
【００８０】
全体的分析の方法では、静的分析の時点で、特にライブラリのプログラムにおいて他のプログラムに属しているプログラムルーチンを含む、プログラムエントリポイントから直接または間接に呼び出されてもよい全てのプログラムルーチンとしてコードが周知であると考えられる。
【００８１】
この仮定の下で、トレースプリントの静的判定のための上記の方法は、次のように進む：各々のプログラムルーチンを個々に分析して変換する代わりに、呼び出されたプログラムルーチンの第１の命令に関する無条件の分岐としてのプログラムルーチン呼び出し命令（≪インヴォーク(invoke)≫, ≪コール(call)≫,その他）、及び、対応する呼び出しの直後に続いている命令の方への分岐としての復帰呼び出し命令（≪リターン(return)≫,その他）、を処理することによって、同時にすべて変換される。
【００８２】
換言すれば、手順は、もはやプログラムルーチンのチェックフローグラフに関してではないが、プログラムルーチン呼び出し及び復帰命令に対応する追加のアークを含む相互手続き的チェックフローグラフに関してである。効果的に呼び出されるべきプログラムルーチンを動的に決定する命令（例えば、仮想方法またはインタフェース方法への呼び出しなど）に対して、呼び出しが動的に解決され得る全てのプログラムルーチンから／へ、アークが加えられるという点が注目される。例えば、JVMにおいて、≪インヴォークバーチャルC.m (invokevirtual C.m)≫の全ての目標方法の単純な近似が、クラス≪C≫またはそのサブクラスのうちの１つにおいて定義される方法≪m≫のグループである。（このグループのより良い近似は、静的チェックフロー分析を用いて得られてもよい）。
【００８３】
この相互手続き的グラフに適用される、プログラムルーチンに対して上記に説明された方法は、必要なトレースプリント調整を挿入して、トレースプリント値がある同じプログラムルーチンの全ての呼び出しサイトにおいて、かつ同じ呼び出しサイトから呼び出されそうな全てのプログラムルーチンの終わりにおいて同じである。
【００８４】
上記の全体的方法での問題は、全てのプログラムルーチンのコードが周知であるという仮定が時々強いためであるということである。コードは、変換の間、パッケージ方法として知られているが、必ずしも、ライブラリプログラムルーチンのコードまたは他のプログラムと共有されるコードである必要はない。
【００８５】
１つの最初の解決は、例えばこれらの呼び出しのまわりの≪トレース(trace)≫変数を保存して元に戻すことによって、プログラムの一部でないプログラムルーチンへの呼び出しを介してトレースプリント値を保存することである。
【００８６】
相互手続き的チェック分析も軽減する別の解決法は、全てのプログラムルーチンの間で次の≪コントラクト(contract)≫を決めることから成る。名前≪r≫の各々のプログラムルーチンに対して、トレースプリント値がプログラムルーチンへのエントリで≪E(r)≫である場合、そのとき、トレースプリント値はプログラムルーチンを去るときに≪S(r)≫である。ここで、≪E≫及び≪S≫は、例えば暗号追跡プリントによって算出されるといった、プログラムルーチン名を任意のトレースプリント値に関連付ける関数である。特にそれがお互いに無関係なプログラムルーチンを区別することが可能である場合に、プログラムルーチン符号定数（その引数及び戻り値のタイプ）が同様に名前と関連付けられてもよい。
【００８７】
上記の≪コントラクト(contract)≫は、確実にするのが容易である。プログラムルーチン≪r≫に対する呼び出しのための各々の命令の前に、トレースプリント調整は、値≪E(r)≫にそれをもたらすために挿入される。そして、各々の復帰呼び出し命令に対して、トレースプリント調整は、同様に≪S(r)≫にその値をもたらすために挿入される。
【００８８】
この原則は、呼び出しの時点で動的に決定される方法に及ぶ。例えば≪ジャバ(Java)（登録商標）≫または≪ジャバカード(JavaCard)（登録商標）≫において、≪m≫が方法名であり≪s≫が方法符号定数である≪（m、s）≫の対が用いられてもよい。この一組のトレースプリントは、≪E(m、s)≫及び≪S(m（s）)の定義を可能にする。仮想方法が他の方法を再定義する場合、これらの２つの方法が同じ名前及び同じ符号定数、よって、同じ値≪E≫及び≪S≫を有するということが注目されてもよい。方法呼び出し及び復帰に対するトレースプリントに関する≪コントラクト(contract)≫は、従って、同様の方法で適用される。
【００８９】
プログラムルーチンの名前だけ（そして、任意にそれらの符号定数）が考慮に入れられる限り、トレースプリント値の決定は、プログラムルーチンによってプログラムの全部を知ることなくプログラムルーチンでなされてもよい。非回復の例外を介してプログラムルーチンから早期に出ることは、例外が引き起こされるときに、バーチャルマシン（陰的に）または例外ハンドラ（明示的に）が周知の定数値までトレースプリントを常に再初期化するという仮定上のいかなる追加の問題をも提起しない。
【００９０】
トレースプリント検証をどの場所でなされなければならないかをソースにおいて（例えば≪チェックトレース()(checkTrace())≫への明示的な呼び出しで）プログラマに明示的に命令することを要求する代わりに、これらのチェックも、コード変換ツールを用いて自動的に挿入されてもよい。
【００９１】
例えば、JCVMにおいて、
・不揮発性メモリ（EEPROM）を書き込む各々の命令の前に、クラスフィールド（≪プットスタティック(putstatic)≫）またはインスタンスフィールド（≪プットフィールド(putfield)≫）に記述して、またはテーブル（≪x-アストア(x-astore)≫）に記述して、
・各々の処理の開始時及び終了時に、
・特定のライブラリ方法などへの呼び出しの前に、
チェックが実行されてもよい。
【００９２】
このことは、プログラムが不揮発性データの値を変更して入退出を実行しようとしない限り、場合によっては妨げられるいかなる演算をプログラムが実行することができると考える実行性整合性制御のポリシーを設定することを特に可能にする。
【００９３】
トレースプリント検証の自動挿入の戦略は変更するのが簡単である。なんとなれば、それは単にコードの変換フェーズに影響を及ぼすだけであるからである。実際には、それが確認の頻度とコードサイズ及び≪checkTrace≫演算による実行時間の増加との間で見出されるべき妥協から生じる。
【００９４】
コード（例えば、≪アッドトレース(addTrace)）、≪チェックトレース(checkTrace)≫、≪アジャストトレース(adjustTrace)≫及び≪セットトレース(setTrace)≫タイプのプログラムルーチンに対する呼び出しなど）において命令を挿入することによって明確にプログラムを修正するよりはむしろ、トレースプリントセット及びチェック・データがプログラムの実行可能なコードから独立しているテーブルに記憶されてもよい。これらのデータ項目は、トレースプリント演算が実行されるプログラムポイント及び関連する値（これらの演算の引数）を含んでもよい。それは、そのとき、現在のプログラムポイントがテーブルに記憶されたプログラムポイントを通過する時に、これらの演算を担当して実行する実行マシン（例えばバーチャルマシン）である。
【００９５】
トレースプリント演算の効果的引数よりむしろ、テーブルは、どのダイナミックデータが演算において考慮されるべきかを示す値も記憶することができる。例えば、≪アッドトレース(addTrace)≫に対応する複雑なエントリが、そうすることができる実行例が、トレースプリントがマシンの変数またはレジスタの現在値を用いて更新されるべきであるということを示してもよい（なんとなれば、その値が静的に周知であるからである）。
【００９６】
この方法の１つの有利な点は、トレースプリント算出とチェックデータとでより少ないメモリ・スペースを使いつくすということである。その一方、それはテーブル検索のために実行時間に関して高価であるかもしれない。性能問題がある場合、混合型の方法が用いられてもよい。いくつかの演算は、実行マシンによって自動的に算出される。他の演算は、明示的にプログラムコードに挿入される。そして、他の演算はテーブルに記憶される。例えば、演算≪アッドトレース(addTrace)≫は、バーチャルマシンによって算出されてもよい。≪チェックトレース(checkTrace)≫及び≪セットトレース(setTrace)≫演算は明示的なプログラムルーチン呼び出しによって表現されてもよい。≪アッドトレース(addTrace)≫は、テーブル検索によって実行されてもよい。さらに、有効性の理由で、≪アジャストトレース(adjustTrace)≫に対するテーブル検索が、分岐がとられた場合にだけ実行されてもよい（効果的調整がそのような場合だけ実行されると仮定する）。
【００９７】
トレースプリント算出及びチェック演算が標準化されない限り、上記に記載したような実行の整合性を制御するための装備されたプログラムが、適合されない実行プラットフォーム上で機能しないかもしれない。
【００９８】
コードが、（タイプ≪アッドトレース(addTrace)）、≪チェックトレース(checkTrace)≫、≪アジャストトレース(adjustTrace)≫及び≪セットトレース(setTrace)≫）のトレースプリントに関するプログラムルーチン呼び出しを明示的に示す場合、プログラムは、これらのプログラムルーチンを実行するライブラリによって付随されてもよい。そのとき、それは、全ての実行プラットフォーム上で可搬である。しかしながら、プラットフォームにより効果的な実行がある場合、それはプログラムを供給されるものの代わりに、後者を置換してもよい。
【００９９】
トレースプリント設定及び制御演算がテーブルにおいてコード化される場合に、プログラムは更に可搬的でさえある。例えば、JCVMに対して、テーブルは付加的な個別の構成要素の形で提供されてもよい。機械がこれらのテーブルを認識するかまたは使用する。若しくは、それはそれらを認識しないかまたはそれらを無視する（そして、この場合、実行整合性を制御することを実行しない）。
【国際調査報告】
2007517299.tif 000002
2007517299.tif 000003
2007517299.tif 000004
2007517299.tif 000005
2007517299.tif 000006
2007517299.tif 000007