(57)【特許請求の範囲】
【請求項１】
第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムを第２のコンピュータプログラムにコンパイルするためのコンパイラであって、
当該コンパイラは、テーブル及びマシン言語コードを生成することにより前記第２のコンピュータプログラムを生成するためのコードジェネレータを有し、生成されたテーブル及び生成されたマシン言語コードは、前記第２のコンピュータプログラムを一緒に形成し、生成されたマシン言語コードは、テーブルを参照し、
当該コンパイラは、前記第１のコンピュータプログラムにおける算術表現又は論理表現を識別するように構成され、前記の表現は、少なくとも１つの変数に依存し、前記コードジェネレータは、前記変数の複数の値のための識別された表現の予め計算された結果を表す１又はそれ以上のテーブルを生成し、予め計算された結果を表す生成された１又はそれ以上のテーブルにアクセスすることにより前記第２のコンピュータプログラムにおいて前記識別された表現を実装するためのマシン言語コードを生成するように構成され、
前記識別された表現を実装するために生成される前記マシン言語コードは、算術若しくは論理マシン命令を含まない、及び／又は、条件文のマシン命令を含まない、マシン言語コードであり、
前記識別された表現を実装するために生成されるマシン言語コードは、演算子のないものであり、当該演算子のないマシン言語コードは、レジスタとメモリとの間のデータを転送するためのロード及びストア演算と、ジャンプ演算とのみを有する、コンパイラ。
【請求項２】
前記コードジェネレータは、条件文の複数の値のための識別された表現のための１又はそれ以上の予め計算された分岐テーブルを生成し、生成された１又はそれ以上の分岐テーブルにアクセスすることにより前記第２のコンピュータプログラムにおいて前記識別された表現を実装するためのマシン言語コードを生成するように構成される、請求項１に記載のコンパイラ。
【請求項３】
前記ロード演算は、定数、メモリアドレスに格納された値及び他のレジスタのうちの１つによりレジスタをロードするためのものであり、
前記メモリアドレスは、１又はそれ以上のレジスタ及び／又は定数により示される、請求項１に記載のコンパイラ。
【請求項４】
前記ストア演算は、１又はそれ以上のレジスタ及び／又は定数を１又はそれ以上のメモリアドレスにストアするためのものであり、
前記メモリアドレスは、１又はそれ以上のレジスタ及び／又は定数により示される、請求項１−３のうちいずれか一項に記載のコンパイラ。
【請求項５】
前記ジャンプ演算は、メモリアドレスへジャンプするためのものであり、
前記メモリアドレスは、１又はそれ以上のレジスタ及び／又は定数により示されるか、又は、メモリアドレスは、更なるメモリアドレスからの取り出される、請求項１−４のうちいずれか一項に記載のコンパイラ。
【請求項６】
前記マシン言語は、レジスタに作用し、
前記レジスタのサブセットは、メモリアドレスを含めるためのアドレスレジスタを形成する、請求項１−５のうちいずれか一項に記載のコンパイラ。
【請求項７】
当該コンパイラは、前記第１のコンピュータプログラムにおいて、１又はそれ以上のデータアイテムに作用する表現を識別するように構成され、
前記コードジェネレータは、同じアドレスレジスタのそれぞれのレジスタにおけるデータアイテムの各一つをロードし、前記アドレスレジスタがテーブル入力を示すように前記アドレスレジスタの他のレジスタにおけるデータをロードし、前記データアイテムに作用する演算子の、前記アドレスレジスタにより示されたメモリアドレスからレジスタへの結果をロードするためのマシン言語コードを生成するように構成される、請求項１−６のうちいずれか一項に記載のコンパイラ。
【請求項８】
当該コンパイラは、前記第１のコンピュータプログラムにおいて、条件付きのジャンプを識別するように構成され、
前記コードジェネレータは、アドレスレジスタのレジスタにおいて条件文を示す値を保持するレジスタをロードし、前記アドレスレジスタがテーブル入力を示すように前記アドレスレジスタの他のレジスタにおけるデータをロードし、前記アドレスレジスタにより示されたメモリアドレスにある前記メモリにストアされた前記メモリアドレスまでジャンプするためのマシンコードを生成するように構成される、請求項１−７のうちいずれか一項に記載のコンパイラ。
【請求項９】
請求項１−８のうちいずれか一項に記載のコンパイラを有する、コンピュータ。
【請求項１０】
第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムを第２のコンピュータプログラムにコンパイルするためのコンパイル方法であって、
テーブル及びマシン言語コードを生成することにより前記第２のコンピュータプログラムを生成するステップであって、生成されたテーブル及び生成されたマシン言語コードは、前記第２のコンピュータプログラムを一緒に形成し、生成されたマシン言語コードは、テーブルを参照する、ステップと、
前記第１のコンピュータプログラムにおける算術表現又は論理表現を識別するステップであって、前記表現は、少なくとも１つの変数に依存する、ステップと、
前記変数の複数の値のための識別された表現の予め計算された結果を表す１又はそれ以上のテーブルを生成し、予め計算された結果を表す生成された１又はそれ以上のテーブルにアクセスすることにより前記第２のコンピュータプログラムにおいて前記識別された表現を実装するためにマシン言語コードを生成するステップとを有し、
前記識別された表現を実装するために生成される前記マシン言語コードは、算術又は論理マシン命令を含まない、及び／又は、条件文のマシン命令を含まない、マシン言語コードであり、
前記識別された表現を実装するために生成されるマシン言語コードは、演算子のないものであり、当該演算子のないマシン言語コードは、レジスタとメモリとの間のデータを転送するためのロード及びストア演算と、ジャンプ演算とのみを有する、コンパイル方法。
【請求項１１】
前記第１のコンピュータプログラムは、第４のコンピュータプログラムを解釈するためのバーチャルマシンプログラムであり、
当該方法は、
更なるテーブル及び第４のプログラミング言語コードを生成することにより前記第４のコンピュータプログラムを生成することにより、第３のコンピュータプログラミング言語において記述される第３のコンピュータプログラムを第４のコンピュータプログラミング言語において記述される前記第４のコンピュータプログラムにコンパイルするステップであって、前記更なるテーブル及び前記第４のプログラミング言語コードは、前記第４のコンピュータプログラムを一緒に形成し、生成された第４のプログラミング言語コードは、更なるテーブルを参照する、ステップと、
前記第３のコンピュータプログラムにおける算術表現又は論理表現を識別するステップであって、前記表現は、少なくとも１つの変数に依存する、ステップと、
前記変数の複数の値のための識別された表現の予め計算された結果を表す１又はそれ以上のテーブルを生成し、予め計算された結果を表す生成された１又はそれ以上のテーブルにアクセスすることにより前記第３のコンピュータプログラムにおいて前記識別された表現を実装するための第４のプログラミング言語コードを生成するステップとを有する、請求項１０に記載のコンパイル方法。
【請求項１２】
第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムを第２のコンピュータプログラムにコンパイルするためのコンパイラにより、第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムを第２のコンピュータプログラミング言語において記述される第２のコンピュータプログラムにコンパイルすることにより生成される第１のテーブル及び第２のプログラミング言語コードを有するコンピュータプログラムであって、
前記コンパイラは、テーブル及び第２のプログラミング言語コードを生成することにより前記第２のコンピュータプログラムを生成するためのコードジェネレータを有し、
生成されたテーブル及び生成された第２のプログラミング言語コードは、前記第２のコンピュータプログラムを一緒に形成し、
生成された第２のプログラミング言語コードは、テーブルを参照し、
前記コンパイラは、前記第１のコンピュータプログラムにおける算術表現又は論理表現を識別するように構成され、
前記表現は、少なくとも１つの変数に依存し、
前記コードジェネレータは、前記変数の複数の値のための識別された表現の予め計算された結果を表す１又はそれ以上のテーブルを生成し、予め計算された結果を表す生成された１又はそれ以上のテーブルにアクセスすることにより前記第２のコンピュータプログラムにおいて前記識別された表現を実装するための第２のプログラム言語コードを生成するように構成され、
当該コンピュータプログラムは、請求項１−８のうちいずれか一項に記載のコンパイラにより前記第２のコンピュータプログラムをマシン言語に翻訳するためにバーチャルマシンプログラムをコンパイルすることにより生成される第２のテーブル及びマシン言語コードを更に有し、
前記識別された表現を実装するために生成される前記マシン言語コードは、算術又は論理マシン命令を含まない、及び／又は、条件文のマシン命令を含まない、コンピュータプログラム。
【請求項１３】
コンピュータ上で実行されたときに請求項１０又は請求項１１の全てのステップを前記コンピュータに実行させる、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムを第２のコンピュータプログラムにコンパイルするためのコンパイラに関する。コンパイラは、マシン言語コードを生成することにより第２のコンピュータプログラムを生成するためにコードジェネレータを有する。
【０００２】
本発明は、更に、コンパイラ及びコンパイル方法として構成されるコンピュータに関する。
【背景技術】
【０００３】
コンピュータシステムがいわゆるサイドチャネルを介して一部の情報を漏らすことは長い間知られている。コンピュータシステムの入出力動作を観察することは、コンピュータシステムにより使用される秘密鍵のような機密情報に関する何らかの有益な情報を供給しないかもしれない。しかし、コンピュータシステムは、観察され得る他のチャネル、例えばその電力消費又は電磁放射を有し、これらのチャネルは、サイドチャネルと呼ばれる。例えば、異なる命令により消費される電力の小さな変動及び命令を実行している間に消費される電力の変動が測定され得る。測定された変動は、機密情報（例えば、暗号鍵）に相関され得る。観察可能な及び意図された入出力動作の背後にある機密情報に関するこの追加の情報は、サイドチャネルと称される。
【０００４】
サイドチャネルを介して、コンピュータシステムは、その使用の間、機密情報を"漏らす"かもしれない。サイドチャネルを観察及び解析することは、入出力動作のみの暗号解析から取得され得るよりも良好な情報へのアクセスを攻撃者に与え得る。サイドチャネル攻撃の１つの既知のタイプは、いわゆる差動電力分析（ＤＰＡ；differential power analysis）である。
【０００５】
コンピュータハードウェア及びコンピュータソフトウェアの機能の双方の実装は、サイドチャネル攻撃に対して弱い。しかしながら、問題は、ソフトウェアにおいて最も厳しい。ハードウェア実装と比較して、ソフトウェアは、比較的遅く、電力の比較的大きな量を消費する。双方のファクタは、サイドチャネル攻撃を支持する。
【０００６】
試みは、これらのコンパイルを変えることによりサイドチャネル攻撃に対するコンピュータプログラムの抵抗を増大させるよう行われている。
【０００７】
米国特許７９９６６７１号は、向上したコンパイルによりサイドチャネル攻撃に対するコンピュータプログラムの抵抗を増大させることを提案している。電力分析攻撃が測定された電力消費に依存するので、抵抗は、電力消費を低減させるようにコンパイルすることにより増大される。コンパイラは、最も効率的なエネルギになるコンパイルを予測し、これを選択する。エネルギ消費削減は、電力ノイズ／変動を増大させ、サイドチャネル抵抗を向上させることが観察される。
【０００８】
エネルギ削減アプローチが、単独で十分な電力ノイズ／バリエーションを取り込むのに十分でない場合、その後、エネルギ最適化のために用いられるコンパイラアプローチが、コード（例えば、暗号アルゴリズム）の重要な部分における電力コストをランダム化するために用いられ得る。これは、異なる電力要件によりコードを故意に生成により、コンパイル時に達成される。
【０００９】
計算にランダム性を取り込むサイドチャネル問題に対する現在のアプローチは、満足なものには満たないと判明した。隠されるにもかかわらず、電力消費と機密計算との間の一部の関係は残る。充分な電力測定及び統計解析が与えられた場合、ランダム性に基づく対策は効果がないかもしれない。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
これら及び他のセキュリティ関心事に対処するために向上したコンパイラを有することが有利であるだろう。
【課題を解決するための手段】
【００１１】
発明者らは、秘密データ（例えば、暗号鍵）に関する情報の漏出が、秘密のデータに基づき動作するマシンコード命令の演算及び論理回路の使用により第一にもたらされることを観測した。第一に斯様な命令を回避することが可能であった場合、サイドチャネル漏出の根本的原因のうち１つは対処されるだろう。
【００１２】
本発明の態様は、独立請求項において規定される。従属請求項は、有利な実施形態を規定する。
【００１３】
第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムを第２のコンピュータプログラムにコンパイルするためのコンパイラが提供される。第２のコンピュータプログラムは、マシンプログラミング言語であってもよいが、より一般に任意のコンピュータプログラミング言語であってもよい。コンパイラは、テーブル及びマシン言語コードを生成することにより前記第２のコンピュータプログラムを生成するためのコードジェネレータを有し、生成されたテーブル及び生成されたマシン言語コードは、前記第２のコンピュータプログラムを一緒に形成し、生成されたマシン言語コードは、テーブルを参照し、当該コンパイラは、前記第１のコンピュータプログラムにおける演算又は論理表現を識別するように構成され、前記の表現は、少なくとも１つの変数又はデータアイテムに依存し、前記コードジェネレータは、前記変数の複数の値のための識別された表現の予め計算された結果を表す１又はそれ以上のテーブルを生成し、予め計算された結果を表す生成された１又はそれ以上のテーブルにアクセスすることにより前記第２のコンピュータプログラムにおいて前記識別された表現を実装するためのマシン言語コードを生成するように構成される。
【００１４】
少ない演算又は論理演算しか含まないので、第２のコンピュータプログラムのサイドチャネル漏出はより低くなる。理想的には、全ての演算及び論理表現及び下位表現がテーブルアクセスに置換される。演算又は論理表現又は下位表現を構成するこれらの命令がないので、これらは如何なる情報も漏らし得ない。テーブルは事前計算される。即ち、テーブルに囲まれる演算又は論理的動作を実行するために消費される電力は、プログラムの実行中に可視ではない。
【００１５】
更に、命令セットが削減されるので、実行されるプログラムを非常によりしっかりと復元する。実際に、サイドチャネル情報は、過去において、埋め込まれたプロセッサ上で実行されるプログラムの大部分を回復するために用いられていた。例えば、Thomas Eisenbarth, Christof Paar, and Bjorn Weghenkelによる"Building a Side channel Based Disassembler", Springer Transactions on Computational Science, Special Issue on "Security in Computing", 2010を参照。サイドチャネルに基づく分解は、典型的には、オペランドではなく命令のタイプを示す。その理由は、オペランドが（言わばＤＰＡを用いた）よりきめ細かい統計分析を必要とするためである。したがって、使用される命令のタイプの数を低減することにより、命令のタイプを知ることからはあまり情報は示されない。極端には、演算子のないコンパイルが用いられるときには、その分解は、ロード及びストア動作が用いられるよりも、分解の前に明瞭である何かが始まることをほとんど示さないだろう。従って、例えば、所有者の暗号アルゴリズムがより少ない命令を用いて実装される場合、サイドチャネル情報から暗号アルゴリズムをリバースエンジニアリングするのがより難しくなるだろう。
【００１６】
コンパイラは、第１のプログラムと少なくとも意味的に等価である第２のプログラムを生成する。但し、第２のプログラムは、第１のプログラムより多くのことを行い得る。
【００１７】
第１のコンピュータプログラムは、より大きなコンピュータプログラムの部分であってもよい。その場合、コンパイラは、より大きなコンピュータプログラムの部分のみをコンパイルする。これは、演算子のないコンパイルが典型的には大きな量のメモリを必要とするので、利点である。それ故、演算子のないコンパイルをより大きなプログラムのより重要な部分に限定することが有利である。同様に、第２のコンピュータプログラムは、より大きな第２のコンピュータプログラムの部分であってもよい。より大きな第２のコンピュータプログラムは、全体として演算子のない状態でコンパイルされる必要はない。
【００１８】
通常、コンパイラは、１つを超える表現（例えば、演算又は論理表現）を識別するだろう。予め計算された結果は、識別された表現に関連していてもよい。表現が依存する１つを超える変数があってもよい。この場合、テーブルは、変数の複数の値のための予め計算された結果を表してもよい。コンパイラは、複数の変数に依存して、表現を、より少ない変数に依存するより小さな表現の組み合わせに分割することを決めるための決定論理を有してもよい。
【００１９】
一実施形態において、表現が依存する変数は、セキュリティに関連したデータ（例えば、暗号鍵）と相関される。
【００２０】
一実施形態において、第２のコンピュータプログラムは、マシン言語において記述される。
【００２１】
一実施形態において、識別された表現を実装するために生成されるマシン言語コードは、演算又は論理マシン命令を含まない。
【００２２】
一実施形態において、識別された表現を実装するために生成されるマシン言語コードは、演算又は論理を含まない、及び、条件文のマシン命令を含まない。演算又は論理マシン命令も条件文の命令も回避することが有利であることに注意されたい。一実施形態において、第２のコンピュータプログラムは、演算又は論理を含まない、及び／又は、条件文のマシン命令を含まない。好ましくは、暗号鍵の少なくとも部分に依存するか又はこれと相関される入力を有する少なくとも表現は、演算を伴わない第２のコンピュータプログラム又は論理マシン命令及び／又は条件文の命令において実装される。
【００２３】
コンパイラは、計算機読み取り可能媒体上に格納されてもよい。即ち、マシン読み取り可読格納デバイスにおいて明白に具現化される。コンパイラは、例えばネットワーク（例えば、ワイヤレスネットワーク又はインターネット等）を介して受信されるデジタル信号としてダウンロードされてもよい。コンパイラは、コンパイルするためのコンピュータ制御の方法として表されてもよい。
【００２４】
マシン言語は、場合により更なる関連付けステップを必要とする、コンピュータプロセッサ上で実行可能な言語である。第２のコンピュータプログラムは、異なるコンパイラによってコンパイルされた他のコンピュータプログラムに関連付けられてもよいことに留意されたい。第２のプログラムは、例えば、１又はそれ以上のメモリ及びプロセッサを有するコンピュータ上で実行されてもよく。プロセッサは、レジスタを有する。プロセッサは、マシン命令セットを解釈するように構成される。一部のマシン命令は、メモリとレジスタとの間でデータを転送する。マシン命令がデータ（典型的にはレジスタ）に影響する命令をサポートする場合であっても、コンパイラはそれらを用いる必要はない。例えば、コンパイラは、演算及び論理命令をサポートするプロセッサのためのコードを生成するために用いられてもよい。しかしながら、コンパイラは、それらを用いることを回避する。また、コンパイラは、演算及び論理命令をサポートしないプロセッサの使用を可能にする。コードジェネレータは、マシンコード命令のストリームを生成してもよい。
【００２５】
コンパイラは、第１のコンピュータプログラミング言語において記述されたプログラムを受信するための入力部を有してもよい。コンパイラは、第１のコンピュータプログラミング言語を構文解析するように構成されるパーサを有してもよく、コードジェネレータは、パーサの制御下でマシン言語コードを生成するように構成されてもよい。構文解析は、文法に従うものであってもよい。例えば、パーサは、パーサにより検出される言語要素に対応するコードを生成するためのコードジェネレータルーチンを呼び出し得る。パーサは、例えば構文解析ツリーを生成することにより、第１のプログラムの内部表現を生成し有る。
【００２６】
コンパイラは、第１のプログラムの一連の文字を第１のコンピュータプログラミング言語の一連のトークンに変換することを有する、語彙解析のための語彙スキャナを有し得る。語彙スキャナは、パーサの前で実行されてもよく、又は、パーサの部分であってもよい。
【００２７】
一実施形態において、生成されたマシン言語コードは、条件文のマシン命令を含まない。条件文のマシン命令は、条件文が特定の値を有する場合、及び、そうでない場合に、或る動作を実行する命令である。条件文の命令は、以下のものを含む；或るレジスタが或る値を有する場合にのみジャンプする条件付きのジャンプ命令、条件付きの代入、及び、レジスタが或る値を有する場合に繰り上げビットをセット又はリセットするいわゆる比較命令。コンパイラは、予め計算された分岐テーブルを用いて条件文の命令を回避してもよい。分岐テーブルは、好ましくは、必要とされるジャンプアドレスが取り出されるポインタのテーブルとして実装される。取り出されるアドレスは、条件文に依存する。分岐テーブルは、条件文に依存するオフセットを用いて分岐される無条件の分岐命令のシリアルのリストとして実装されてもよい。オフセットは、テーブルを用いることにより、又は、必要とされた加算を実現するために１又はそれ以上のテーブルを用いるルーチンによりベースアドレスに追加される。３２ビットオフセット加算が小さな加算テーブルの繰り返された使用により実装され得ることに留意されたい。
【００２８】
また、条件文の命令は、これらの電力消費が特定の条件が真か否かに関連付けられるので、サイドチャネル情報の重要なソースであり、それ故、条件に関する情報を直接漏らす。
【００２９】
好ましい実施形態において、第２のコンピュータプログラムコードは、いわゆる"演算子のない"ものである。演算子のないコードは、移動（即ち、ロード、演算、レジスタとメモリとの間でデータを転送するためのストア演算、ジャンプ演算）のみを有する。演算及び論理命令のような命令を漏らす演算子のないコード情報の使用は回避される。移動、ロード及びストア演算は、例えば使用されるテーブルをエンコードすることにより、エンコーディングに非常に従うことに留意されたい。それ故、任意の残りの電力漏出は、テーブルをエンコードすることにより低減され得る。演算子のないコードは、以下を含んでもよい：定数を伴うロードレジスタ、他のレジスタを伴うロードレジスタ、メモリアドレスで格納される値を伴うロードレジスタ、１又はそれ以上のレジスタにより示される１又はそれ以上のメモリアドレスに１又はそれ以上のレジスタの格納、レジスタ（又は直接アドレス）により示されたメモリアドレスまでのジャンプ。
【００３０】
プロセッサが、好ましくは移動、又はストア演算を介して、プログラムカウンタの操作の一部のタイプを可能にする場合、ジャンプ命令は回避されてもよいことに留意されたい。例えば、このアドレスレジスタの全ての下位レジスタが、並列にロードされるか、又は、少なくとも次の命令のロードが効力を有する前にロードされる、プログラムカウンタに対するロードが可能である場合、ジャンプがもたらされてもよい。好ましい実施形態において、命令セットは、アドレスレジスタにストアされるメモリアドレスまでのジャンプを有する。これは、条件付きのジャンプが、レジスタ又はその部分へのロード及びストアを介して実装されるのを可能にする。
【００３１】
一実施形態において、ロード演算は、以下のうちの１つを伴うレジスタをロードするためのものである：定数、メモリアドレスにストアされた値及び他のレジスタ。メモリアドレスは、１又はそれ以上の定数及び／又はレジスタにより示される。一実施形態において、ストア演算は、１又はそれ以上のメモリアドレスにおける１又はそれ以上の定数及び／又はレジスタをストアするためのものである。メモリアドレスは、１又はそれ以上のレジスタ値、及び／又は、定数により示される。一実施形態において、ジャンプ演算は、メモリアドレスまでジャンプするためのものである。メモリアドレスは、１又はそれ以上の定数及び／又はレジスタにより示されるか、又は、メモリアドレスは、更なるメモリアドレスから取り出される。
【００３２】
一実施形態において、マシン言語はレジスタに作用し、レジスタのサブセットが、メモリアドレスを含めるためのアドレスレジスタを形成する。例えば、各レジスタは、多数のビット（即ち、８ビット）を含む。及び、各アドレスレジスタは、多数のレジスタ（即ち、４）を含む。これは、アドレス計算を必要とすることなくテーブルアクセスを可能にし、レジスタに依存するテーブルアクセスは、アドレスレジスタのレジスタをロードすることにより実装され得る。これは、アドレス算出ユニットの加算（演算）を除去するので、重要である。また、この加算は、情報を明らかにすることができる。
【００３３】
一実施形態において、幾つかのテーブルは、２の累乗の倍数であるメモリアドレスに格納される。テーブルの開始は、レジスタにビットがあるので、ゼロ最下位ビットの同じ数を有するアドレスに格納される。一実施形態において、テーブルの幾つかの開始は、レジスタにビットがあるので、ゼロ最下位ビットの数の２倍を有するアドレスに格納される。それ故、定数及びレジスタを効果的に連結することにより、テーブルにおける索引を可能にし、それ故計算が回避される。複数のオペランドを用いたオペランドは、複数のゼロビットを有するアドレスにテーブルを配置することによりサポートされてもよい。
【００３４】
例えば加算及び乗算のテーブルが２の累乗の境界に格納される一実施形態においては、２の累乗の境界に他のテーブルも置く必要がない。テーブル化された加算及び乗算を用いて、我々は、プロセッサによりサポートされた演算又は論理の使用を伴うことなく、テーブル化された加算又は乗算の使用を介して、任意の基数+タイプサイズ（typesize）*オフセットを計算する。従って、プログラム１のテーブルアクセスの他のテーブルアクセス、又は、少なくとも意味論的に等価なプログラム２の取り込まれたテーブルは、演算子のないコード加算、及び／又は、テーブル駆動される乗算の使用を介して生成され得る。
【００３５】
一実施形態において、コンパイラは、第１のコンピュータプログラムにおいて、１又はそれ以上のデータアイテムに影響する算術又は論理マシン演算のような演算子を識別するように構成され、コードジェネレータは、同じアドレスレジスタのそれぞれのレジスタにおけるデータアイテムのそれぞれをロードするためのマシン言語コードを生成するように構成され、アドレスレジスタがテーブル入力を示すようにアドレスレジスタの他のレジスタにおけるデータをロードし、アドレスレジスタにより示されたメモリアドレスからレジスタへのデータアイテムに影響する演算子の結果をロードする。第１のプログラムが演算を明示的に含むという点で、第１のコンピュータプログラムにおける演算子を識別することは、直接識別することであり得る。しかし、識別することは、黙示的であってもよく、コンパイラが、マシン言語コードを生成する前に第１のコンピュータプログラムを中間の表現に変換したことを意味する。斯様な中間言語は、レジスタ伝達言語であってもよい。
【００３６】
一実施形態において、コンパイラは、第１のコンピュータプログラムにおいて条件付きのジャンプを識別するように構成され、コードジェネレータは、アドレスレジスタのレジスタにおいて条件を示す値を保持するレジスタをロードするためのマシンコードを生成するように構成され、アドレスレジスタがテーブル入力を示すようにアドレスレジスタの他のレジスタにおけるデータをロードし、アドレスレジスタにより示されたメモリアドレスにおけるメモリに格納されたメモリアドレスまでジャンプする。
【００３７】
本発明の一態様は、第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムを、算術及び／又は論理命令を伴わない及び／又は条件付きの命令を伴わない形式に、オプションとして演算子のない形式で、コンパイルするためのコンパイラとして構成されるコンピュータに関する。
【００３８】
本発明の態様は、第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムを第２のコンピュータプログラミング言語において記述される第２のコンピュータプログラムにコンパイルするためのコンパイラに関する。コンパイラは、テーブル及び第２のプログラミング言語コードを生成することにより第２のコンピュータプログラムを生成するためのコードジェネレータを有し、生成されたテーブル及び生成された第２のプログラミング言語コードは、第２のコンピュータプログラムを一緒に形成し、生成された第２のプログラミング言語コードは、前記テーブルを参照し、生成された第２のプログラミング言語コードは、算術又は論理マシン命令を含まず、前記テーブルは、算術及び／又は論理マシン命令の予め計算された結果を有する。第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムを第２のコンピュータプログラミング言語において記述される第２のコンピュータプログラムにコンパイルするためのコンパイラは、マシン言語命令のために第２のプログラミング言語からの等価物が選択されなければならないことを除き、第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムをマシン言語において記述される第２のコンピュータプログラムにコンパイルするためのコンパイラと同じ技術を用いることができる。
【００３９】
一実施形態において、コンパイラは、例えば、中央処理ユニット（ＣＰＵ）と、第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムをマシン言語において記述される第２のコンピュータプログラムにコンパイルするために前記ＣＰＵに結合されたメモリとを有する、電子装置である。装置は、第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムを受信するための入力部と、テーブル及びマシン言語コードを生成することにより第２のコンピュータプログラムを生成するためのコードジェネレータとを有し、生成されたテーブル及び生成されたマシン言語コードは、第２のコンピュータプログラムを一緒に形成する。生成されたマシン言語コードは、テーブルを参照し、生成されたマシン言語コードは、算術又は論理マシン命令を含まず、テーブルは、算術及び／又は論理マシン命令の予め計算された結果を有する。
【００４０】
本発明の態様は、第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムをマシン言語において記述される第２のコンピュータプログラムにコンパイルするための方法に関し、当該方法は、テーブル及びマシン言語コードを生成することにより前記第２のコンピュータプログラムを生成するステップを有し、生成されたテーブル及び生成されたマシン言語コードは、前記第２のコンピュータプログラムを一緒に形成し、生成されたマシン言語コードは、テーブルを参照し、生成されたマシン言語コードは、算術又は論理マシン命令を含まず、前記テーブルは、算術及び／又は論理マシン命令の予め計算された結果を有する。
【００４１】
本発明の一態様は、第１のコンピュータプログラムをコンパイルするためのコンパイル方法に関し、当該方法は、第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムを、算術又は論理マシン命令を含まない第２のコンピュータプログラミング言語において記述される第２のコンピュータプログラムにコンパイルするステップであって、前記テーブルは、算術及び／又は論理マシン命令の予め計算された結果を有する、ステップと、第１のテーブル及び第２のプログラミング言語コードを取得するステップと、前記第２のコンピュータプログラムを解釈するためにバーチャルマシンプログラムを算術又は論理マシン命令を含まないマシン言語にコンパイルするステップであって、前記バーチャルマシンプログラムは、更なる第１のコンピュータプログラミング言語において書き込まれる、ステップと、生成されたマシン言語コード及び第２のテーブルを取得するステップとを有し、前記テーブルは、算術及び／又は論理マシン命令の予め計算された結果を有する。
【００４２】
コンピュータプログラムがバーチャルマシン上での実行に適している（及び、バーチャルマシンのためのインタプリタのコンパイルと組み合わせる）第２のコンピュータプログラムにコンパイルされるこの構造、好ましくは演算子のないコンパイラは、"von Munchhausen"コンパイルと呼ばれる。これは、演算子のないプログラムにより与えられる保護を提供するが、例えばsandboxingのようなバーチャルマシン実行により与えられる保護も提供する。ＶＭ及びプログラムは、スタンドアロンであってもよい。また、ＶＭのフィーチャは、それ故、組み合わせられた結果、例えば実行の間のコード確認、難読化等に対して与えられてもよい。
【００４３】
von Munchhausen構造に従ってコンパイルされたプログラムは、特別な形式を有する。即ち、これらは、２セットのテーブル、各コンパイルから１つ、及び、１つの実行ファイルを有する。本発明の態様は、コンパイラにより、第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラムを第２のコンピュータプログラミング言語において記述される第２のコンピュータプログラムにコンパイルすることにより生成される第１のテーブル及び第２のプログラミング言語コードと、コンパイラにより、前記第２のコンピュータプログラムを解釈するためにバーチャルマシンプログラムをマシン言語にコンパイルすることにより生成される第２のテーブル及びマシン言語コードとを有し、前記バーチャルマシンプログラムは、更なる第１のコンピュータプログラミング言語において記述される、コンピュータプログラムに関する。１つは、プログラムとＶＭとの間でテーブルを共有するかしないかの選択を有する。そうでもあっても、分岐テーブルは、典型的には、プログラム及びＶＭの専用である。
【００４４】
本発明の方法は、コンピュータに実装された方法としてのコンピュータ上で、若しくは、専用のハードウェアにおいて、又は、これらの組み合わせにおいて、実装されてもよい。本発明の方法のための実行可能なコードは、コンピュータプログラム製品上に格納されてもよい。コンピュータプログラム製品の例としては、メモリデバイス、光学格納デバイス、集積回路、サーバ、オンラインソフト等が挙げられる。好ましくは、コンピュータプログラム製品は、前記プログラム製品がコンピュータ上で実行されたときに本発明の方法を実行するためにコンピュータ読み取り可能な媒体上に格納される非一時的プログラムコード手段を有する。
【００４５】
好ましい実施形態において、コンピュータプログラムは、コンピュータプログラムがコンピュータ上で実行されたときに本発明の方法の全てのステップを実行するように適合されたコンピュータプログラムコード手段を有する。好ましくは、コンピュータプログラムは、コンピュータ読み取り可能な媒体上に具現化される。
【００４６】
一実施形態において、生成されたテーブルは、明細書において示されるように、難読化される。例えば、Oが難読化しているエンコーディングを表す場合、テーブルは、表現又は演算子fに対して以下のように構成され得る：O (f( O-1(x), O-1(y)))。
【００４７】
一実施形態において、難読化は、鍵により制御され、これは、コンパイラに入力される。例えば、鍵は、疑似ランダムストリームを生成するために用いられてもよく、これは、難読化するエンコーディングを選択するために用いられる。面白いことに、これは、特定のコンパイルを鍵に関連付ける。関連付けは、例えば、特定のユーザが特定のソフトウェアのコンパイルに含まれたことを証明するために、ソフトウェアから指紋をとるために後に用いられてもよい。鍵は、場合によりホワイトボックスの実装において、コンパイラに埋め込まれてもよい。例えば、破壊工作ソフトの製作者は、コンパイルされた製品において使用されるエンコーディングを介して追跡され得る。
【００４８】
本発明のこれらの及び他の態様は、以下で述べられる実施形態から明らかになり、これらを参照して説明されるだろう。
【図面の簡単な説明】
【００４９】
【図１】コンパイルシステムを示すブロック図である。
【図２】コンパイルシステムを示すブロック図である。
【図３】テーブルを示すブロック図である。
【図４】コンピュータを示すブロック図である。
【図５】コンパイルを示すフローチャートである。
【図６】コンパイルを示すフローチャートである。
【発明を実施するための形態】
【００５０】
異なる図面において同一の参照番号を有するアイテムは、同じ構造的なフィーチャ及び同じ機能を有するか、又は、同じ信号であることに留意されるべきである。斯様なアイテムの機能及び／又は構造が説明された場合、詳細な説明においてその反復説明の必要がない。
【００５１】
本発明は、多くの異なる形式における実施形態を可能とする一方で、これらは、図面において示され、本開示が、本発明の原理の例示的なものであるとみなされ、本発明を示され述べられた特定の実施形態に限定することを意図しないという理解のもとで、１又はそれ以上の特定の実施形態がここで詳細に述べられるだろう。
【００５２】
図１は、コンパイルシステム１００を示している。システム１００は、コンパイラ１３４を有する。また、第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラム１１０が示される。コンパイラ１３４は、第１のコンピュータプログラミング言語において記述されるコンピュータプログラムをマシン言語にコンパイルするように構成される。好ましくは、第１のコンパイラは、オペランドのない形式にコンパイルするが、この制限は、例えば、条件文演算を可能にすることにより、緩和されてもよい。コンパイラ１３４は、テーブル１４２及び第２のコンピュータプログラム１４４を生成し、第２のコンピュータプログラム１４４は、テーブル１４２との使用のために、マシン言語にコンパイルされる第１のコンピュータプログラム１１０のオペランドのない形式である。
【００５３】
コンピュータプログラム１４４及びテーブル１４２は、コンピュータ１６０上で一緒に実行され得る。コンピュータ１６０は、マシン言語を実行し、実行するための入力オペランドのないプログラム１４４及びテーブル１４２を受信するように構成される。
【００５４】
図４は、演算子のないマシン言語コードの実行に適しているコンピュータ４００を示している。
【００５５】
図４は、バス４３０を介してメモリ４４０に接続されたコンピュータプロセッサ４１０を示している。この特定の実施形態において、メモリ４４０は、２つのより小さなメモリ（不揮発性メモリ４４２及び揮発性メモリ４４４）を有する。
【００５６】
プロセッサ４１０は、汎用レジスタ４２２及びアドレスレジスタ４２４を有する。また、プログラムカウンタＰＣが示される。アドレスレジスタは、複数の汎用レジスタ（この場合、４つのレジスタ）で作られることに留意されたい。ＰＣは、アドレスレジスタのように実装されてもよいが、全体としてアドレス指定可能であってもよい。
【００５７】
図４は、ＵＬ（unlink）及びＳＰとしてマークされる２つのアドレスレジスタを示している。ＵＬレジスタは、自身でサブルーチンを呼び出さないサブルーチンへのジャンプのために、ＰＣの値を保存するために用いられてもよい。この最適化は、一部のアドレス計算を回避し、これは、とりわけ、演算子のないものである場合に有益である。unlinkレジスタとしてのアドレスレジスタ６の使用はオプショナルである。図４は、更に、オプショナルなスタックポインタ（ＳＰ）を示す。スタックポインタは、スタックの最上位の値を指す。スタックは、パラメータを渡すため又は入れ子になったサブルーチンのために用いられてもよい。
【００５８】
メモリ４４０が２つのメモリ（より多くてもより少なくてもよい）で作られるにも関わらず、説明の容易さのために、我々は、メモリ４４０が平坦なアドレス空間においてアドレス指定可能であることを前提とするだろう。また、我々は、メモリ４４０が実行ユニット４２０及び対応するテーブルによる実行のための実行可能マシンコードを有することを前提とするだろう。リニアメモリモデルとも呼ばれる平坦なアドレス空間において、ＣＰＵは、メモリ分割又はページングに頼る必要なく利用可能なメモリ位置の全てに直接的に及びリニアにアドレスすることができる。しかしながら、これは必要ではなく、より小さなアドレス空間がサポートされてもよく、例えば平坦ではないアドレス空間が、例えばテーブルにおいてアドレス空間を考慮することによりサポートされてもよい。
【００５９】
この実施形態において、汎用レジスタは、全て同一のサイズ（即ち、双方が汎用レジスタ）を有する。レジスタのサイズがそれほど大きくない場合に、大きなテーブルをもたらすので、有利である。レジスタのための良好なサイズは８ビットである。４ビットも可能であるが、より長い実行時間をもたらすだろう。１６ビットも可能であるが、これはより大きなテーブルをもたらすだろう。より大きなレジスタも考えられるが、その場合においては、使っていないレジスタ（例えば、ゼロ）の部分を残すことが好ましいかもしれない。図４は、３２の汎用レジスタ（Ｒ０−Ｒ３１）を示している。アドレスレジスタは、複数の汎用レジスタから作られる。
【００６０】
プロセッサ４１０は、マシン言語をサポートする。即ち、マシン言語コードを実行することができる。プロセッサ４１０は、レジスタ（少なくとも汎用レジスタ並びにロード及びストアアドレスレジスタ）とメモリ４４０との間でデータを転送するための少なくともロード及びストア演算をサポートする。一例の実施形態において、プロセッサ４１０は、以下の代入をサポートする：Ri :=#定数（示された場合においては0..255）、Ri := Rj; ARi := ARj; PC := ARi; ARi := PC。ＰＣへのアドレスレジスタの代入は、ジャンプ命令と解釈されてもよい。命令は、別々のジャンプ命令としてラベル付けされてもよいが、移動演算として記録されてもよい。
【００６１】
また、プロセッサ４１０は、例えばアドレスレジスタによりアドレスされる、メモリに対する書込レジスタをサポートする。例えば、@ARi := Riは、アドレスレジスタAriを介したストアを表す。一部の他の非演算命令がサポートされてもよい（例えば、NOP、又は、データに影響しない、例えば割り込みを開始及び停止する幾つかの制御命令）。
【００６２】
幾つかの従来のプロセッサが上記の命令をサポートすることに注意されたい。しかしながら、斯様なプロセッサは、演算子のないプログラムにおいて用いられない多くの命令もサポートする（第１にはそれらの中の算術及び論理命令、第２には条件文の命令）。しかしながら、多くのアドレス指定モードは、演算子のないプログラムにおいては用いられない。例えば、インデックス付けされたアドレス指定モードは、算術演算である加算をもたらす。それにもかかわらず、斯様なプロセッサは、問題のある命令を用いないことにより、用いられてもよい。有利なプロセッサは、前記の命令のみをサポートする。
【００６３】
以下のテーブルは、幾つかの共通の演算が演算子のない態様においてどのように実装され得るかを示す。
【表１】
0006429785.tif 000002
0006429785.tif 000003
サブルーチンの使用はオプショナルであることに注意されたい。
【００６４】
上で与えられた値（即ち、特定の値の加算又は減算）は、とりわけワードサイズ及びコンピュータアーキテクチャに合わせるために、所望の実装に適合されてもよい。
【００６５】
図５は、コンパイル方法５００としてのフローチャートを示している。ステップ５１０において、第１のコンピュータプログラムが受信される。ステップ５２０において、例えばトークンを識別するために、語彙の分析が実行される。場合によりマクロ展開のような処理も行われる。ステップ５３０において、プログラムが解析される。例えば、パーサは、第１のプログラムのプログラミング言語の形式文法に従って構文解析ツリーを生成する。パーサは、プログラムにおける異なる言語構造を識別し、適切なコード生成ルーチンを呼び出す。ステップ５４０においてコード生成が行われる。コード生成の間、一部のコード及び必要に応じて付随するテーブルが生成される。ステップ５５５において、生成されたテーブルは、テーブルベースに統合される。幾つかのテーブルが複数回生成されることが生じ得るので、この場合、これらを複数回ストアすることは必要ではない。例えば、加算テーブルが必要とされてもよく、一度だけ生成されてもよい。ステップ５６０において、コードが生成される。ステップ５６５において、コードと統合することが実行される。全てのコードが統合され、全てのテーブルが統合されたときに、コンパイルは終了する。オプションとして、最適化ステップがあってもよい。
【００６６】
図６は、コンパイラを生成するための興味深い手段であるコンパイル方法６００としてのフローチャートを示している。ステップ５３５において、中間コンパイルが行われる。これは、中間言語（例えば、レジスタ伝達言語等）であってもよいが、マシン言語コードコンパイルであってもよい。これは、図６のステップ５１０−５３５に関して、演算子のないものではない従来のコンパイラが用いられ得ることを意味する。しかしながら、ステップ５４０において、コード生成は、中間コンパイルに基づいて行われる。例えば、マシン言語コードが用いられた場合、各命令は、その命令の対応する演算子のない実装と置換される。これは、コンパイラを生成するための特定の直接的な手段を表す。図５及び６は、マシン言語ではなく第２のプログラミング言語を生成するコンパイラを生成するために用いられてもよい。
【００６７】
図３は、テーブルを有するメモリ３１０を示している。複数の単項テーブル３２０が示される（テーブル３２１，３２２及び３２３）。単項テーブルは、単一の入力に適用される演算の全ての結果をリストアップする。リストは、自然な（即ち、経時的な）順序であってもよいが、例えばサイドチャネル及びリバースエンジニアリング攻撃に対する抵抗を増大させるランダム化及び／又は難読化を増大させるために、エンコーディングが適用されてもよいことに留意されたい。
【００６８】
また、複数の２個一組のテーブル３３０が示される（２個一組のテーブル３３１，３３２，３３３）。テーブルは、仕上げられ、オペランドを固定して他のものを変化させることにより取得される複数の単項テーブルを有する。例えば、２個一組のテーブル３３１は、テーブル３３１１−３３１３（一の各々の考えられる値のための１つのテーブル、即ち、第１のオペランド）を含む。
【００６９】
"ｎ"がレジスタのビットサイズであることを前提とする。単項テーブル３２１−３２３は、少なくともnゼロで終わる開始アドレスを有する。例えば、テーブル３２１−３２３は、aa, bb及びccの幾つかの値に関してそれぞれ0xaa 0xbb 0xcc 0x00のような開始アドレスを有する。２個一組のテーブルは、少なくとも2nゼロで終わる開始アドレスを有する。例えば、テーブル３３１１，３３２１及び３３３１は、aa, bbの幾つかの値に関してそれぞれ0xaa 0xbb 0x00 0x00のような開始アドレスを有する。これは、２個一組のテーブルにおけるテーブル検索が定数及び／又はレジスタのアドレス計算のみの連結を必要としないという利点を有する。最下位端の代わりに、ゼロビットが、他の場所に配置されてもよく、これは、メモリを介してテーブルを広げる効果を有し、難読化を増大させる。
【００７０】
図２は、コンパイルシステム２００を示している。図２において、いわゆるMunchhausen構造が用いられる。
【００７１】
システム２００は、第２のコンピュータプログラミング言語において記述されるコンピュータプログラムをマシン言語にコンパイルするように構成される第２のコンパイラ２３４を有し、第２のコンパイラは、オペランドのない形式にコンパイルするように構成される。コンパイラ２３４は、コンパイラ１３４と同じタイプでもよい。
【００７２】
システム２００は、第１のコンピュータプログラミング言語において記述されるコンピュータプログラムをバーチャルマシンプログラム言語にコンパイルするように構成される第１のコンパイラ２３２を有し、第１のコンパイラは、オペランドのない形式にコンパイルするように構成される。例えば、バーチャルマシンプログラム言語は、ジャババイトコードであってもよい。コンパイラ２３２を構成することは、コード生成がバーチャルマシンプログラム言語において表されるコードを用いることを除いて、コンパイラ１３４及び２３４を構成することと非常に類似している。
【００７３】
システム２００は、第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラム２１０を示している。第１のコンピュータプログラミング言語は、コンパイラ２３２によりテーブル２４２及びコンピュータプログラム２４４にコンパイルされる。コンピュータプログラム２４４は、テーブル２４２との使用のために、バーチャルマシンプログラム言語にコンパイルされた第１のコンピュータプログラム２１０のオペランドのない形式である。
【００７４】
また、システム２００は、バーチャルマシンプログラミング言語を解釈するように構成されるバーチャルマシンコンピュータプログラム２２０を示し、バーチャルマシンコンピュータプログラムは、第２のコンピュータプログラミング言語において記述される。
【００７５】
バーチャルマシンコンピュータプログラム２２０は、テーブル２５２及びコンピュータプログラム２５４にコンパイルされ、コンピュータプログラム２５４は、テーブル２５２との使用のために、マシン言語にコンパイルされたバーチャルマシンコンピュータプログラム２２０のオペランドのない形式である。
【００７６】
プログラム２５４は、マシン言語を実行するように構成されるコンピュータ２６０により実行可能である。プログラム２５４は、テーブル２４２及び２５２と一緒に実行し、プログラム２４４を解釈する。
【００７７】
面白いことに、テーブル２４２及び２５２は統合されてもよく、その結果、バーチャルマシンは、実行するプログラムとテーブルを共有する。典型的には、仮想マシン（ＶＭ；virtual machine）、インタプリタ又はエミュレータは、命令に関して明確に定義されたインタフェースを与えるプログラムである。
【００７８】
典型的に、コンパイラは、デバイスで格納される適切なソフトウェアを実行するマイクロプロセッサ（図示省略）を有するデバイスとして実装される。例えば、ソフトウェアは、ダウンロードされてもよく、対応するメモリ（例えば、ＲＡＭ（図示省略））に格納されてもよい。
【００７９】
以下の詳細は、図２に示された実施形態を更に改良する実施形態である。制御フロー命令から離れて、ＶＭの最も一般的な命令は、演算を実行し、その結果をストアする。これらの演算は、加算（+）、減算（-）、乗算（*）等のような良く知られた演算を含む。コンパイラは、これらの命令を対象とする。即ち、これは、一部の高いレベルの言語において記述される表現をこれらの既知の演算に分解する。
【００８０】
テーブルは、全ての含まれた演算（プログラムにおける演算及びプログラムが実行されるＶＭの演算）のために用いられ得る。セキュリティは、これらのテーブルに独自の特徴又は特性を与えることにより更に向上され得る。
【００８１】
あらゆる演算に関して、テーブルが用いられてもよい。テーブルは、演算に従って規定される。例えば、単項演算子に関して、Opm tableOpm [x] == Opm(x)、又は、２個一組の演算子に関して、Opd tableOpd [x][y] == Opd(x,y)。非単項演算のために、コンパイラがテーブルへのアクセスを複数のアクセスとして実装することができることに注意されたい（Ｃｕｒｒｙとして知られる処理）。それは、X[y]に続くX = tableOpd[x]である。注：記憶方法は、８ビットのデータ経路、１４の２個一組の演算子に関して、１メガバイトに等しいメモリ使用量を必要とするだろう。これは許容可能であるとみなされる。揮発性又は不揮発性に関わらず、幾つか又は全てのテーブルがＲＯＭにストアされてもよく、幾つか又は全てのテーブルが他のメモリにストアされてもよい点に留意されたい。
【００８２】
コンパイラ／リンカー及びＶＭの結合体は、演算使用を演算のテーブルアクセスに置換することにより維持される。根本的なプラットフォームは、ジャンプ命令並びにレジスタ及び記憶から／へ読み取り／書き込みのためにのみ用いられる必要がある。
【００８３】
より高度な実施形態において、コンパイラは、完全な表現をテーブルとして実装することができる。例えば、表現：Ｘ２＋Ｙ２は、２つの乗算及び１つの加算を介して実装され、少なくとも３つの（又はＣｕｒｒｉｅｄである場合にはより多くの）演算をもたらす。
しかしながら、これは、Ｘ２＋Ｙ２のテーブルとして実装され、このテーブルのアクセスに対してコンパイルされてもよい。これは、１つの（Ｃｕｒｒｉｅｄの場合には２つの）テーブルアクセスをもたらすだろう。コンパイラ／リンカー及びＶＭの間の結合体は、テーブルをＶＭに渡すことにより維持され得る。ラベル付けされたテーブルは、コンパイラの出力及びＶＭへの入力になる。コンパイラにより供給されるコードにおいて、その後、これらのラベルが参照される。これは、使っていない演算のテーブルが省略され得るので、改善記憶方法であり得る。一実施形態において、コンパイラは、第１のプログラムにおいて、値を１、２又は複数の数字の入力に割り当てる表現を識別するための表現ユニットを有し、コードジェネレータは、数字の入力の全ての値のための表現の結果を表すテーブルを生成するように構成される。面白いことに、表現は、既存のマシンコード命令に等しい必要はない。
【００８４】
ＶＭは、プログラムでもあり、それ故、これらのプログラムは、例えばテーブル化された演算に向かって、演算子のない形式においてコンパイルされ得ることに再び留意されたい。ＶＭ上で実行されるべきプログラムＰのためにそれを行うこと、及び、ＶＭ自体は、図２に示される４つの結果を与えるだろう。
１．ＶＭ（プログラム２４４）により解釈されようとするＰコード
２．Ｐのテーブル２４２
３．根本的なプラットフォーム上で実際に実行するコードである、演算子のないＶＭコード２５４
４．ＶＭテーブル２５２（これらのＶＭテーブルは、演算子のないＶＭコードに関連付けられる）
【００８５】
テーブル２４２は、そのコンパイルの前であっても、ＶＭプログラム２２０に含まれてもよいことに注意されたい。ＶＭのデコーダは、これらのラベル付けされたテーブルを、解釈されたコードにおけるラベルに連結する。生ずるコードは、テーブルアクセス及び場合により制御命令を行う命令のみを含める必要がある。プログラム及びＶＭのためのコンパイラによりそれぞれ出力されるテーブルは、ＶＭのフレームへの設定方法及びリスト方法として加えられ得る。テーブルの設定方法の追加は、少ないテーブルしか必要としないという利点を有し、従って、格納資源が削減される。設定方法の追加は、このリストの追加が用いられる（Ｐ及びＶＭが共有されない自己のテーブルを有する）のを回避するために、ＶＭ及びＰがテーブルに対して同じエンコーディングを用いることを必要とするという欠点を有する。
【００８６】
非実際的に巨大であるテーブルが必要な場合において、これらは、取り込まれた特性又は機能に関するマイクロ命令として機能する、より小さなテーブルに関してプログラムされ得る。
【００８７】
このセクションにおいて、我々は、高いレベルで、図２の構造のために用いられ得るＶＭについて述べる。ＶＭを介して、追加の特性又は機能がプログラムに付けられてもよい。簡潔さの理由のために、我々は、加算にフォーカスする。他の演算は、同様に処理される。ＶＭの説明の後、我々は、命令を介して特性を取り込み、特性がどのように伝播されるかについて述べるだろう。例として、我々は、難読化の特性を利用した。
【００８８】
簡潔さの理由のために、我々は、ＶＭの主なコンポーネントのみを述べる。これらの主なコンポーネントは、メインループ、デコーダ及び根本的なプラットフォームのメモリ及びレジスタの使用である。
【００８９】
メインループは以下のように規定される。
register pc = start;
while(true)
do
{
Instruction x = fetch ( pc, memory );
Decode_and_evaluate( x );
pc = add[ pc,1];
// through the use of brackets we try to indicated that the compiler did his work and changed the operation into a table access
}
【００９０】
ループが始まる前に、我々は、評価されるべき第１の命令のアドレスを含むレジスタｐｃを参照する。
【００９１】
ループにおいて、我々は、以下のものを観察する。
１．ｐｃの値によりラベル付けされた位置に配置された命令の記憶からのフェッチ
２．命令のデコード及び評価
３．レジスタ（ｐｃ）に次の命令を参照させる、レジスタｐｃに含まれる値のインクリメント
【００９２】
更に、我々は、一部のレジスタｘ及びｙと、開始アドレスにおいて加算命令が配置されるメモリとを有する。
Registers
register x:
register y:
Memory:
...
address start add_instruction
address start+1 jmp_relative_8
...
【００９３】
フェッチ演算は
x = memory[ pc ];
である。
【００９４】
示された単純なＶＭの評価及びデコードのうち、我々は、演算子である加算により行われた評価及び（Ｃのようなスイッチによる）デコードのみを与える。
Decode_and_execute (instruction)
{
switch(instruction)
{ ...
case add_instruction: x := add[ x, y ];
...
}
}
【００９５】
加算は、
Add[ x, y ] == x + y;
である命令を表す。
【００９６】
上記のものは、用いられ得る一例のＶＭであり、他方で、既存のＶＭが述べられた態様において用いられてもよい。
【００９７】
面白いことに、Munchhausen ＶＭに、難読化が与えられてもよい。命令を分かり難くするために、第１のステップは、難読化の特性を命令の既存の機能に追加することであってもよい。提示された場合においては加算命令。我々が１つの難読化関数Ｏを用いると仮定する。関数Ｏの目的は、入出力値の順序付けにより演算のセマンティックスを隠すことである。Ｏは、入力及び出力のセットの入替えであり得る。（addとして示される）分かり難くされた加算は、以下のように見ることができる。
add( x, y ) == O( add[O-1( x ) , O-1( y )] )
【００９８】
add()の入力及び出力は、分かり難くされた領域にあることに留意されたい。これは、命令自体のための結果を有する。元のセマンティックスを保つために、我々は、正しい時点で難読化及び脱難読化を行う必要があるだろう。
case add_instruction: x := O-1 ( add[O(x), O(y)] );
【００９９】
しかしながら、レジスタにおいて難読化された値を保つことにより、我々は、脱難読化及び難読化を省略することができ、その場合、add_instruction: x := add[ x, y ];をもたらす。
【０１００】
ＶＭは、難読化された命令に関して再定義されてもよい。例えば、１つは、ＶＭ自体のメインループを実装するためにバーチャルマシンの命令を用いてもよい。再び、我々は、難読化された追加命令の使用に限定する。他命令は同様に対処される。
【０１０１】
１つは、ＶＭのメインループにおいて"add"があることを識別してもよい（即ち、pc := add[ pc,1];）。
【０１０２】
同等に、難読化されたaddを用いて、我々は、pc := O-1( add[ O(pc), O(1)] );を有する。
【０１０３】
レジスタにおいて難読化された値を保つことにより、PC = O(pc)。置換は、PC := add[ PC, O(1) ];になり得る。
【０１０４】
注：定数は、難読化された領域に向かって上昇されなければならない。
【０１０５】
（この単純な例におけるような）ｐｃの他の発生は、以下のようになるだろう。
１．x = memory[ pc ];
２．pc = start;
第１のケース
x = memory[ pc ];
これは、x = memory[ O-1 ( O(pc) ) ];に等しい。
前と同じように、置換は以下のようになるだろう。
x = memory[ O-1 ( PC ) ];
memory[] over O-1を再構成することにより、我々は、x = MEMORY[ ( PC ) ];を得る。ここで、全てのx に関して、MEMORY[x] == memory[O-1(x)]。
Memory:
...
address O(start+1) ...
...
address O(start) add_instruction
...
をもたらす。
【０１０６】
O(start+1)がO(start)の前に示されるという事実は、まさに入れ換えることを示すものである。これは、選ばれた難読化入替えに依存する。addを用いることにより互いの後に連続的に並べられた命令は、メモリにおいてランダムに分配されることに留意されたい。我々は、Oの領域及び範囲が記憶インデックスと一致するとここで暗に想定する。
【０１０７】
第２のケースは、まさに当然の結果である。同等の命令文は、O( pc ) = O( start )になるだろう。置換することは、PC = O( start );を与える。
【０１０８】
従って、startは、難読化された領域に上昇される（及び、メモリは、前のステップにおいて適宜入れ換えられる）。ｐｃの全ての発生が扱われたあと、好ましくは、我々は、memory[ ]の全ての発生も扱うべきであることは明瞭であるべきである。それは、memory[ ] をMEMORY[ ]に置換することである。これは、前と同じように幾つかの他の命令のための結果を有し得る。これらの結果は、有限の数の命令しかないので、終了まで及ぶ。
【０１０９】
我々は、命令の元の位置の間の距離及びaddを暗示的に用いるジャンプに関する命令のような命令があることを述べる。この距離は、減算により計算される。
【０１１０】
１つは、以下のような命令を特定することができる。
jmp_relative(distance) { pc = add[ pc, distance ] }
難読化方式を適用することは、jmp_relative(y) { PC = add[ PC, y ]; }をもたらすだろう。ここで、ＰＣは、難読化されたｐｃである。
【０１１１】
しかしながら、引数ｙにおける問題が依然として存在する。この引数は、O (元のジャンプ命令のアドレス) - O (ターゲット==元のジャンプ命令のアドレス+距離))を介した連結で再計算されるべきである。プロセスは、根本的なプラットフォームに関する命令をテーブルに変換することにより完了される。
【０１１２】
一部のワードは、命令及びそのデコーダの表現である。命令の表現が難読化され得ることは明らかである。これは、任意の入替えによって難読化され得る。命令及びデコーディングの表現は結合されるが、これらは、ＶＭの他のコンポーネントへのリンクを有しない。それ故、独立した難読化であっても、命令表現とデコーダとの間で用いられ得る。
【０１１３】
当業者にとって明らかなように、方法を実行する多くの異なる手段が考えられることに注意されたい。例えば、ステップの順序は変えられてもよく、又は、一部のステップが並列に実行されてもよい。更に、ステップの間において、他の方法ステップが挿入されてもよい。挿入されたステップは、ここで述べられたような方法の改良を表してもよく、又は、方法に無関係であってもよい。例えば、ステップ５４０、５５０及び５６０は、少なくとも部分的に、並列に実行されてもよい。更に、所与のステップは、次のステップが始まる前に、完全に終了していなくてもよい。
【０１１４】
本発明による方法は、プロセッサシステムに方法５００及び６００を実行させることをもたらすための命令を有するソフトウェアを用いて実行されてもよい。ソフトウェアは、システムの特定のサブエンティティにより利用されるそれらのステップのみを含んでもよい。ソフトウェアは、適切な格納媒体（例えば、ハードディスク、フロッピー、メモリ等）に格納されてもよい。ソフトウェアは、有線若しくは無線に沿った信号として送られてもよく、又は、データネットワーク（例えば、インターネット）を用いてもよい。ソフトウェアは、ダウンロードに対して及び／又はサーバに対する遠隔使用に対して利用可能に行われてもよい。
【０１１５】
本発明は、本発明を実現するために適合される、コンピュータプログラム、とりわけ担体上の又はそれにおけるコンピュータプログラムにも拡張することはいうまでもないだろう。プログラムは、部分的にコンパイルされた形式のような、ソースコード、オブジェクトコード、コード中間ソース及びオブジェクトコードの形式、又は、本発明の方法の実装における使用に適した任意の他の形式であってもよい。コンピュータプログラム製品に関する一実施形態は、記載された方法のうちの少なくとも１つの処理ステップのそれぞれに対応するコンピュータ実行可能な命令を有する。これらの命令は、サブルーチンに再分割されてもよく、及び／又は、静的又は動的に連結され得る１又はそれ以上のファイルに格納されてもよい。コンピュータプログラム製品に関する他の実施形態は、製品及び／又はシステムのうちの少なくとも１つの手段のそれぞれに対応するコンピュータ実行可能な命令を有する。
【０１１６】
上述の実施形態は、本発明を限定するよりはむしろ例示であり、当業者は、多くの代替実施形態を設計することが可能であることが留意されるべきである。
【０１１７】
請求項において、括弧間に配置された任意の参照符号は、請求項を限定するものとして考慮されるべきではない。"有する"という動詞の使用及びその活用は、請求項に記載されたもの以外の要素又はステップの存在を除外するものではない。要素の単数標記は、斯様な要素の複数の存在を除外するものではない。本発明は、幾つかの異なる要素を有するハードウェアによって、及び、適切にプログラムされたコンピュータによって実装されてもよい。幾つかの手段を列挙している装置に係る請求項において、これらの手段の幾つかは、ハードウェアの全く同一のアイテムにより具現化されてもよい。特定の手段が相互に異なる従属請求項に記載されるという単なる事実は、これらの手段の組み合わせが有効に用いられ得ないことを示すものではない。
【０１１８】
【符号の説明】
【０１１９】
１００  コンパイルシステム
１１０  第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラム
１３４  第１のコンピュータプログラミング言語において記述されるコンピュータプログラムをマシン言語にコンパイルするように構成された第１のコンパイラ
１４２  テーブル
１４４  テーブル用としての第２のコンピュータプログラムのマシン言語コード
１６０  入力マシンコード１４４及びテーブル１４２として受信する、マシン語を実行するように構成されたコンピュータ
２００  コンパイルシステム
２１０  第１のコンピュータプログラミング言語において記述される第１のコンピュータプログラム
２２０  バーチャルマシンプログラミング言語を解釈するように構成されたバーチャルマシンコンピュータプログラム（バーチャルマシンコンピュータプログラムは、第２のコンピュータプログラミング言語において記述される）
２３２  第１のコンピュータプログラミング言語において記述されるコンピュータプログラムをバーチャルマシンプログラム言語にコンパイルするように構成された第１のコンパイラ
２３４  第２のコンピュータプログラミング言語において記述されるコンピュータプログラムをマシン言語にコンパイルするように構成された第２のコンパイラ
２４２  テーブル
２４４  テーブル２４２用としてのバーチャルマシンプログラム言語コード
２５２  テーブル
２５４  テーブル２５２用としてのバーチャルマシンコンピュータプログラム２２０のマシン言語コード
２６０  実行するための入力されたオペランドのないプログラム２５４として受信する、マシン語、テーブル２４２、２５２及びプログラム２４４を実行するように構成されたコンピュータ
３１０  メモリ
３２０  複数の単項テーブル
３２１−３２３  単項テーブル
３３０  複数の２個一組のテーブル
３３１−３３３  ２個一組のテーブル
３３１１−３３３３  単項テーブル
４００  コンピュータ
４１０  コンピュータプロセッサ
４２０  実行ユニット
４２２  汎用レジスタ
４２４  アドレスレジスタ
４３０  バス
４４０  メモリ
４４２  不揮発性メモリ
４４４  揮発性メモリ
【図１】
0006429785.tif 000004
【図２】
0006429785.tif 000005
【図３】
0006429785.tif 000006
【図４】
0006429785.tif 000007
【図５】
0006429785.tif 000008
【図６】
0006429785.tif 000009