(57)【要約】いくつかの実施形態は、コンピュータプログラムを難読化するコンパイラデバイス４００に関する。コンパイラデバイスは、コンピュータプログラム表現に生存変数解析を行い、コンピュータプログラム表現を修正して、少なくとも第２の変数を符号化パラメータとして使用して第１の変数を符号化する。
2021530057.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータプログラム表現を受け取る通信インターフェースと、プロセッサとを含む、コンピュータプログラムを難読化するためのコンパイラデバイスであって、
前記プロセッサは、前記コンピュータプログラム表現に生存変数解析を行い、前記生存変数解析によって、前記コンピュータプログラム表現内に割り当てられている変数の集合に関連付けられている生存区間領域、変数が書き込まれている場所を示す定義情報、及び、変数が読み取られる場所を示す使用情報が取得され、
前記プロセッサはさらに、前記変数の集合から、第１の変数及び第２の変数を選択し、ここで、前記第２の変数は、前記第２の変数に関連付けられている前記定義情報に従って前記第１の変数に関連付けられている前記生存区間領域において定義されておらず、
前記プロセッサはさらに、前記定義情報によって、かつ、前記第１の変数に関連付けられている前記使用情報によって定義された場所において、少なくとも前記第２の変数を符号化パラメータとして使用して前記第１の変数を符号化する符号化コードを用いて前記コンピュータプログラム表現を修正する、
コンパイラデバイス。
【請求項２】
前記コンピュータプログラム表現は、制御フローグラフを含み、前記生存区間領域、前記定義情報、及び前記使用情報は、前記制御フローグラフ内のノードを構成する、請求項１に記載のコンパイラデバイス。
【請求項３】
前記プロセッサは、
前記変数の集合からランダムに第１の変数を選択するか、又は、
前記変数の集合から順に第１の変数を選択する、
請求項１又は２に記載のコンパイラデバイス。
【請求項４】
前記プロセッサは、
前記コンピュータプログラム表現内のコンパイラディレクティブに従って第１の変数を選択し、
第２の変数が存在するかどうかを決定し、存在しない場合は、警告信号を生成する、
請求項１から３のいずれか一項に記載のコンパイラデバイス。
【請求項５】
前記プロセッサは、
所与の第１の変数について複数の第２の変数を決定し、
前記決定された複数の第２の変数から、第２の変数をランダムに選択するか、又は、
前記第１の変数の前記生存区間領域により近い使用を有する第２の変数を選択する、
請求項１から４のいずれか一項に記載のコンパイラデバイス。
【請求項６】
前記符号化コードは、
前記第１の変数を前記第２の変数でマスクするか、又は、
前記第１の変数に符号化テーブルを適用し、前記符号化テーブルは、前記第２の変数を、キーとしての入力として受け取る、
請求項１から５のいずれか一項に記載のコンパイラデバイス。
【請求項７】
前記符号化コードは、前記第１の変数を剰余数系において符号化し、前記剰余数系のモジュライは、前記第２の変数から少なくとも部分的に導出される、
請求項１から６のいずれか一項に記載のコンパイラデバイス。
【請求項８】
前記コンピュータプログラム表現を修正することは、符号化された第１の変数に対する演算を符号化された演算に置き換えることを含む、請求項１から７のいずれか一項に記載のコンパイラデバイス。
【請求項９】
前記符号化された演算は、前記第２の変数を修正しない、請求項８に記載のコンパイラデバイス。
【請求項１０】
前記プロセッサは、前記修正されたコンピュータプログラムをコンパイルする、請求項１から９のいずれか一項に記載のコンパイラデバイス。
【請求項１１】
前記プロセッサは、構文解析、中間コード生成、コード最適化、割り当て、ターゲットコード生成のうちの１つ以上を行う、請求項１から１０のいずれか一項に記載のコンパイラデバイス。
【請求項１２】
コンピュータプログラムを難読化するためのコンパイラ方法であって、
コンピュータプログラム表現を受け取るステップと、
前記コンピュータプログラム表現に生存変数解析を行うステップであって、前記生存変数解析によって、前記コンピュータプログラム表現内に割り当てられている変数の集合に関連付けられている生存区間領域、変数が書き込まれている場所を示す定義情報、及び、変数が読み取られる場所を示す使用情報が取得される、ステップと、
前記変数の集合から、第１の変数及び第２の変数を選択するステップであって、前記第２の変数は、前記第２の変数に関連付けられている前記定義情報に従って前記第１の変数に関連付けられている前記生存区間領域において定義されていない、ステップと、
前記定義情報によって、かつ、前記第１の変数に関連付けられている前記使用情報によって定義された場所において、少なくとも前記第２の変数を符号化パラメータとして使用して前記第１の変数を符号化する符号化コードを用いて前記コンピュータプログラム表現を修正するステップと、
を含む、方法。
【請求項１３】
プロセッサシステムに、請求項１２に記載の方法を行わせるための命令を表す一時的又は非一時的データを含む、コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイラデバイス、コンパイラ方法、及びコンピュータ可読媒体に関する。
【背景技術】
【０００２】
コンピュータプログラムは、クラウド、パーソナルコンピュータ、又は組み込みデバイスなど、まったく異なる環境においてデータを処理する。プログラムによって使用又は処理されるデータは、高い値を有する可能性がある。例えば、所与の機能を実施する機械学習アルゴリズムは、機械学習プロセス中に学習された非常に特殊な重みを使用し得る。プログラムのリバースエンジニアリングによって、これらの重みを明らかにすることができるので、機械学習アルゴリズムを訓練するために使用されたデータへのアクセス、又は訓練プロセスを実現するために必要とされる計算能力へのアクセスを必要とせずに、攻撃者がアルゴリズム機能を容易に複製又は改善できる。同様に、他の攻撃を適用して、プログラムの機能を修正し、その可用性に影響を与え得る。例えば、攻撃者がタイミング若しくは消費電力を観察するか、又はグレーボックスファジャーを使用してバグを検出するグレーボックス攻撃である。
【０００３】
過去数年の間に、データの機密性のための様々なタイプの保護（完全準同型スキーム及び符号化スキーム）が大幅に進歩した。また、プログラムの完全性（例えば、異なる難易度の完全性チェック）やプログラムの可用性のために、異なるタイプの保護がある。
【０００４】
参照により本明細書に組み込まれる米国特許８７５２０３２号「Ｓｙｓｔｅｍ  ａｎｄ  ｍｅｔｈｏｄ  ｏｆ  ｉｎｔｅｒｌｏｃｋｉｎｇ  ｔｏ  ｐｒｏｔｅｃｔ  ｓｏｆｔｗａｒｅ−ｍｅｄｉａｔｅｄ  ｐｒｏｇｒａｍ  ａｎｄ  ｄｅｖｉｃｅ  ｂｅｈａｖｉｏｕｒｓ」に、最新のコンパイルデバイスの一例が説明されている。
【０００５】
既知のコンパイラは、ソフトウェアのソースコードを受け取り、ソースコードをロジックの様々な基本ブロックに細分化する。これらの基本ブロックは、それらの内容及びプログラムのロジック及び制御フローにおけるそれらの位置に基づいて、様々な基本ブロック間の依存性を増大又は生成するように修正される。基本ブロックに対する修正は、いくつかの基本ブロックの出力を拡張する一方で、他の対応する基本ブロックの入力を同様に拡張して、それらの間にインターロックを提供するという効果を有する。インターロックは、システムの一部Ｙの動作が、他の一部Ｘの挙動を改ざんすることによって高い確率で一部Ｙの誤動作又は故障を引き起こすように、他の一部Ｘの動作によって影響を受けるようにする。
【０００６】
プログラムは、制御フローグラフ（ＣＦＧ）として表され得る。コンパイラでは、プログラムを介する可能な制御フローは、制御フローグラフ（ＣＦＧ）によって表され得る。制御フローグラフ（ＣＦＧ）では、実行可能コード（単一の始点、単一の終点を有し、その始点からその終点まで順番に実行される「直線」コードシーケンス）の基本ブロック（ＢＢ）がグラフノードによって表され、アークがＢＢ  Ｕに対応するノードをＢＢ  Ｖに対応するノードに、含まれるプログラムの実行中に、制御は常に、又は可能であれば、ＢＢ  Ｕの終わりからＢＢ  Ｖの始まりまで流れる場合に接続する。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
標準的な難読化技法は、メモリのどこかに格納された固定パラメータによる値の難読化に依存する。しかしながら、値は、プログラムの動的解析によって容易に明らかにされる。符号化を使用して、アルゴリズムを保護できる。しかしながら、プログラム全体に対して多くの符号化を使用することは、パフォーマンスのペナルティにつながる可能性があり、また、単一の符号化を使用することは、リバースエンジニアリングをより容易にする。
【０００８】
コンピュータプログラムを難読化するためのコンパイラデバイスが提供される。
【課題を解決するための手段】
【０００９】
コンパイラデバイスは、
コンピュータプログラム表現を受け取る通信インターフェースと、
プロセッサと、
を含み、
プロセッサは、コンピュータプログラム表現に生存変数解析を行い、生存変数解析によって、コンピュータプログラム表現内に割り当てられている変数の集合に関連付けられている生存区間領域（liveness region）、定義情報、及び使用情報が取得され、
プロセッサはさらに、変数の集合から第１の変数及び第２の変数を選択し、第２の変数は、第２の変数に関連付けられている定義情報に従って第１の変数に関連付けられている生存区間領域において定義されておらず、
プロセッサはさらに、定義情報によって、かつ、第１の変数に関連付けられている使用情報によって定義された場所において、少なくとも第２の変数を符号化パラメータとして使用して第１の変数を符号化する符号化コードを用いてコンピュータプログラム表現を修正する。
【００１０】
コンパイラデバイスは、値の動的保護を導入する。プログラムの一部で値が静的である第２の変数を使用して、プログラムのその部分で第１の変数を保護する。第１の変数は、特定の実行に依存する値で保護され、これにより、保護を覆すことを困難にする。特に、例えば、マスキングだけに使用された変数を特定し、除去するホワイトボックスの自動解析は、コンパイラデバイスによって導入される難読化には難点がある。難読化変数は、プログラム内で自然に発生し、プログラムの通常の機能で関数を行う通常の変数であってよい。このような変数の除去は、プログラムの関数に影響を与える。さらに、そのような変数を見つけることは、マスキング又は符号化などに加えて有用な機能を果たすため、困難である。
【００１１】
保護された第１の変数は、自動的に選択できる。例えば、それらはランダムに選択されても、又は、変数のすべて若しくは一部が、例えば、適切な第２の変数が利用可能であるかどうかを決定するために、順番に検査されてもよい。特に重要な変数は、例えばコンパイラディレクティブによって、プログラマによって示されてもよい。コンパイラデバイスの自動適用により、このやり方で多くの変数を難読化できることが分かった。特に、実施形態は、局所変数、例えば、小さい生存区間領域を有する変数を難読化する際に有利である。例えば、一実施形態では、第１の変数は、小さい生存区間領域、例えば、最大で閾値数のブロックを有する変数の集合から選択される。閾値は、例えば、２、４などである。
【００１２】
一実施形態では、第１の変数は、関数に従って、例えば、関数によって計算された順位付けに従って順番に、変数の集合から選択される。関数はランダムであっても、ランダム成分を有していてもよい。関数は、ヒューリスティックスを含んでもよい。
【００１３】
実施形態は、例えば、ソースコードプログラムで定義される変数、中間表現で定義される変数、又はさらには疑似レジスタに適用され得る。疑似レジスタはまた、シンボリックレジスタの仮想とも呼ばれる。
【００１４】
保護はマスキングに基づき得る。例えば、ＸＯＲマスキング、加算及び減算、例えば、モジュロ又はモジュラスなどである。固定された符号化パラメータに対して可逆的である他の関数を使用してもよい。保護は、秘密パラメータが第１の変数に依存するＲＮＳなどの符号化に基づき得る。符号化はまた、ルックアップテーブル又は多項式を介して実施してもよい。例えば、一実施形態では、第１の変数は第２の変数でマスクされる。例えば、一実施形態では、第１の変数は、符号化テーブルを第１の変数に適用することによって符号化され、テーブルは、第２の変数を符号化パラメータ（例えばキー）としての入力として受け取る。
【００１５】
一実施形態では、符号化コードは、第１の変数を剰余数系で符号化し得、剰余数系のモジュライは、第２の変数から少なくとも部分的に導出される。剰余数系は、各々が同じ第２の変数に関して符号化されている複数の第１の変数に適用され得る。
【００１６】
一実施形態では、コンピュータプログラム表現を修正することは、符号化された第１の変数に対する演算を符号化された演算に置き換えることを含む。例えば、複数の第１の変数は、同じ第２の変数で符号化される。符号化された変数に対する計算は、符号化された領域において完全に行われ得る。
【００１７】
コンパイラデバイスは、電子デバイスである。これは、コンピュータ、例えば、デスクトップ、ラップトップ、サーバなどであり得る。本明細書に説明されるコンパイラ方法は、広範囲の実用的な用途に適用され得る。このような実用的な用途には、独自のアルゴリズム、暗号コード、鍵の保護、金融ソフトウェアの保護などを含むソフトウェアの保護が含まれる。
【００１８】
本方法の一実施形態は、コンピュータで実施される方法として、専用ハードウェアで、又は両方の組合せで、コンピュータ上で実施され得る。本方法の一実施形態の実行可能コードは、コンピュータプログラム製品上に格納され得る。コンピュータプログラム製品の例としては、メモリデバイス、光記憶デバイス、集積回路、サーバ、オンラインソフトウェアなどが挙げられる。好ましくは、コンピュータプログラム製品は、コンピュータプログラム製品がコンピュータ上で実行されると、本方法の一実施形態を行うためのコンピュータ可読媒体上に格納された非一時的プログラムコードを含む。
【００１９】
一実施形態では、コンピュータプログラムは、コンピュータプログラムがコンピュータ上で実行されると、本方法の一実施形態のステップのすべて又は一部を行うように適応されたコンピュータプログラムコードを含む。好ましくは、コンピュータプログラムがコンピュータ可読媒体上に具現化される。
【００２０】
本発明の別の態様は、コンピュータプログラムをダウンロード用に利用可能にする方法を提供する。この態様は、コンピュータプログラムが、例えばＡｐｐｌｅ（登録商標）のＡｐｐＳｔｏｒｅ（登録商標）、Ｇｏｏｇｌｅ（登録商標）のＰｌａｙＳｔｏｒｅ（登録商標）又はＭｉｃｒｏｓｏｆｔ（登録商標）のＷｉｎｄｏｗｓＳｔｏｒｅ（登録商標）にアップロードされて、コンピュータプログラムがこのようなストアからダウンロードできるときに使用される。
【図面の簡単な説明】
【００２１】
本発明のさらなる詳細、態様、及び実施形態は、単なる例として、図面を参照して説明される。図中の要素は、簡潔さかつ明瞭さのために示されており、必ずしも縮尺通りに描かれていない。図面において、既に説明された要素に対応する要素は、同じ参照番号を有する。
【００２２】
【図１】図１は、符号化の一実施形態の一例を概略的に示す。
【図２】図２は、符号化の一実施形態の一例を概略的に示す。
【図３ａ】図３ａは、コンピュータプログラム表現の一実施形態の一例を概略的に示す。
【図３ｂ】図３ｂは、コンピュータプログラム表現の一実施形態の一例を概略的に示す。
【図４ａ】図４ａは、コンパイラデバイスの一実施形態の一例を概略的に示す。
【図４ｂ】図４ｂは、コンパイラデバイスの一実施形態の一例を概略的に示す。
【図５】図５は、コンパイラ方法の一実施形態の一例を概略的に示す。
【図６ａ】図６ａは、一実施形態によるコンピュータプログラムを含む書き込み可能部分を有するコンピュータ可読媒体を概略的に示す。
【図６ｂ】図６ｂは、一実施形態によるプロセッサシステムの表現を概略的に示す。
【００２３】
図１〜図４ｂ、図６ａ、図６ｂの参照番号一覧
２１０  プログラム実行フロー
２１２  第１の変数の集合
２１４  第２の変数の集合
３１０  コンピュータプログラム
３２０ａ  制御フローグラフ
３２１〜３２３  基本ブロック
４００  コンパイラデバイス
４１０  メモリ
４２０  プロセッサ
４３１  通信インターフェース
４３２  第１のコンパイラ部
４３３  第２のコンパイラ部
４４０  コンピュータプログラム表現
４４２  変数の集合
４４４  関連する生存区間領域
４５０ａ  生存区間解析器
４６０  変数セレクタ
４６２  コード修正器
１０００  コンピュータ可読媒体
１０１０  書き込み可能部分
１０２０  コンピュータプログラム
１１１０  集積回路
１１２０ａ  処理ユニット
１１２２  メモリ
１１２４  専用集積回路
１１２６ａ  通信要素
１１３０  相互接続部
１１４０  プロセッサシステム
【発明を実施するための形態】
【００２４】
本発明は、多くの異なる形態の実施形態が可能であるが、図面に示されており、本明細書では１つ以上の特定の実施形態を詳細に説明するが、本開示は、本発明の原理の例示と見なされるべきであり、示され説明される特定の実施形態に本発明を限定することを意図するものではないことを理解されたい。
【００２５】
以下では、理解のために、実施形態の要素が動作中に説明される。しかしながら、それぞれの要素は、それらによって実行されるように説明されている機能を実行することは明らかであろう。さらに、本発明は実施形態に限定されず、本発明は本明細書に記載された、又は相互に異なる従属請求項に列挙された、すべての新規の特徴又は特徴の組合せにある。
【００２６】
プログラムで使用される変数の値を難読化する多くの方法がある。例えば、難読化は、混乱を生成することによってプログラムを保護する。変数の値を隠す技法は、プログラムに格納された静的値を使用して変数の値を隠すことを含む。例えば、次のプログラムフラグメントを考える。このプログラムフラグメントは、生存区間解析（liveness analysis）又は第１及び第２の変数の選択を使用せずに難読化された。その代わりに、機密変数の後の発生をマスクする目的で、変数「ｍａｓｋ」が追加される。
Ｍａｓｋ＝０ｘ１８ＡＥ７６２Ｃ９
Ｖａｒｉａｂｌｅ＝ｃｏｎｆｉｄｅｎｔｉａｌ＿ｖａｌｕｅ  ＸＯＲ  Ｍａｓｋ
．．．［ｐｒｏｇｒａｍ］．．．
Ｖａｒｉａｂｌｅ＝Ｖａｒｉａｂｌｅ  ＸＯＲ  Ｍａｓｋ
Ｖａｒｉａｂｌｅ＝Ｆｕｎｃｔｉｏｎ（ｖａｒｉａｂｌｅ）  ＸＯＲ  Ｍａｓｋ
．．．［ｐｒｏｇｒａｍ］．．．
【００２７】
この場合、マスクは、プログラムに格納された静的値又は固定値である。プログラム内の秘密値は、マスクされる、例えば、マスクでＸＯＲされる。その結果、コンパイル後、２行目の秘密値は、もはやコンパイル済みプログラムに明示的に格納されなくなる。値が後に使用されるとき、それはマスクでマスク解除されて、例えば、再びＸＯＲされて、プレーン値が利用可能になるが、実行中にのみ生成される計算値としてのみ利用可能になる。
【００２８】
このタイプの難読化をさらに複雑にするために、難読化に使用される値が静的値の代わりに関数によって返される動的マスクが使用される。しかしながら、このようなアプローチは、関数が例えば、常に「０」を返すように修正され得るので、依然として容易に攻撃可能である。
【００２９】
図１は、符号化の一実施形態の一例を概略的に示す。例えば、ホワイトボックス暗号技術の分野から生じる符号化方式は、アルゴリズム及びそのデータのリバースエンジニアリングをより困難にするために設計されてきている。符号化は、例えば、（ｉ）ニブル、（ｉｉ）剰余数系、又は（ｉｉｉ）代数変換に基づく。図１は、符号化された領域で実現される演算の抽象表現を示す。整数（Ｒ，＋，＊）の環上の評価関数ｆ（）の代わりに、Ｒにおける要素は、Ａ及び代替演算
【数１】
2021530057.tif 000003
において表現される要素に基づいて同じ関数ｆ（）を実装できるように、変換Ｔ（）によって異なる領域Ａに変換される。この実装は、Ｆ（）と示される。このような方式は、Ｔ（）がデータを暗号化するための公開鍵の使用を表現でき、Ｆ（）で実現される演算には、符号化された演算及びある種の評価鍵が含まれ、逆変換は秘密鍵の使用と等価であるという意味で、（完全）準同型暗号化（（Ｆ）ＨＥ）方式とある程度類似している。しかし、依然として大きな違いがある。例えば、変換Ｔ（）及びＴ−１（）の使用法は、通常、コード自体内にマージされ、抽出の難しさは、それらを実装する大きなテーブルをリバースエンジニアリングする難しさに依存する。
【００３０】
標準的な難読化技法は、メモリのどこかに格納された固定パラメータによる値の難読化に依存する。しかしながら、値は、プログラムの動的解析によって、例えば、プログラムが実行されるときに値がどのように発展するかを解析することによって容易に明らかにされるが、これは、ある時点で、演算を行うために難読化を除去する必要があるからである。符号化を使用して、アルゴリズムを保護できる。しかしながら、プログラム全体に対して多くの符号化を使用することは、パフォーマンスのペナルティにつながる可能性がある。したがって、場合によっては、いくつかの、さらには単一の符号化を使用することが好ましい。この場合、攻撃者は、特定の符号化を知るだけで済むため、プログラムのリバースエンジニアリングが容易になる。
【００３１】
一実施形態では、異なるアプローチが使用される。第１の変数の集合が、例えば、難読化又は符号化を使用して保護される。保護は、プログラムで使用される第２の変数の集合から導出される値を使用することによって達成される。第２の変数の集合は、第１の変数の集合を保護するために使用される間、静的であると決定される変数を含む。変数の難読化は、別の変数を使用することによって行われるので、提案する難読化技法は、最新技術で知られているものよりも、動的解析に対してよりレジリエントである。
【００３２】
図２にこの考え方を示す。プログラム実行フロー２１０を示す。保護されるべき第１の変数の集合２１２が選択される。図２の左側に、第１の変数の集合２１２が生存している領域、例えば、それらの値が定義又は使用され得る領域を示す。第１の集合を保護するために、第２の変数の集合２１４が特定される。変数の集合２１４は、集合２１２の生存区間領域（liveness region）に定義をたまたま持たない変数である。図２の右側に、第２の変数の集合が静的なままである領域を示す。さもなければ、集合２１４は、保護に関係のない理由、例えば、プログラムの関数を実行するために、プログラム内で定義及び使用される通常の変数であってもよい。
【００３３】
変数の集合２１２は、少なくとも集合２１２の保護範囲の間、静的なままである変数の集合２１４から導出される値Ｖによって、保護される（例えば、マスクされる、符号化される）。保護は、難読化に基づくことができ、例えば、変数の値がクリアに格納されないように、Ｖを使用して集合２１２内の変数をＸＯＲする。保護は、符号化に基づくこともでき、符号化はＶに依存する。例えば、Ｖを使用して、ＲＮＳ符号化で使用される秘密モジュライを取得する。
【００３４】
図４ａは、コンパイラデバイス４００の一実施形態の一例を概略的に示す。例えば、コンパイラデバイス４００は、コンピュータ（例えば、デスクトップコンピュータ、サーバ、ラップトップ、ネットブックなど）である。コンパイラデバイス４００は、モバイルデバイス（例えば、携帯電話、ＰＤＡなど）でもよい。コンパイラデバイス４００は、スマートカード、セットトップボックス、テレビなどでもよい。
【００３５】
コンパイラデバイス４００は、メモリ４１０を含む。メモリ４００は、コンピュータプログラム表現、コンパイラソフトウェア、コンピュータプログラムコンパイルのうちの１つ以上を格納する揮発性メモリである。例えば、メモリ４１０はＲＡＭメモリである。コンパイラデバイス４００は、追加のメモリ、例えば不揮発性メモリ、例えばＲＯＭメモリ、及び／又は、揮発性メモリなどを有する。
【００３６】
コンパイラデバイス４００は、一実施形態による方法を実施するプロセッサ４２０を含む。例えば、メモリ４１０は、プロセッサによる実行のために構成されたコンピュータ命令を格納する。これは必須ではないが、例えば、コンパイラデバイス４００は、コンピュータコード（例えばコンパイラコード）にアクセスするためのストレージインターフェースを含む。プロセッサは、ストレージインターフェースを介してオペレーティングシステムコード及び／又はコンパイラコードにアクセスし、当該コードを実行する。ストレージインターフェースは、ローカルストレージ（例えばローカルメモリ、ハードディスクなど）、又は非ローカルストレージ（例えばクラウドストレージ）へのインターフェースであってもよい。メモリ４１０は、プロセッサが作用するデータを含み得る。
【００３７】
様々な実施形態における計算デバイスの動作は、プロセッサ（例えばプロセッサ回路）において実装されてもよく、その例を本明細書に示す。以下の図のいくつかは、プロセッサの機能ユニットであり得る機能ユニットを示す。例えば、図４ｂは、プロセッサの可能な機能構成の設計図として使用される。図４ｂでは、プロセッサ回路はユニットとは別個に示されていない。例えば、図に示される機能ユニットは、デバイスのメモリ（例えばデバイスの電子メモリ）に格納され、デバイスのマイクロプロセッサによって実行可能なコンピュータ命令において、全体的に又は部分的に実装される。ハイブリッド実施形態では、機能ユニットは、部分的にハードウェアで（例えばコプロセッサとして）実装され、部分的にデバイス上に格納され実行されるソフトウェアで実装される。プロセッサは、まとめられることでプロセッサを形成する複数のサブプロセッサを含み得る。例えば、プロセッサは、複数のプロセッサ回路を含む。
【００３８】
コンパイラデバイス４００は、コンパイラデバイス４００の用途に応じて、追加のハードウェア及び／又はソフトウェア要素を含み得る。例えば、コンパイラデバイス４００は、コンピュータネットワークを介する通信のための通信インターフェース、又はコンパイラデバイス４００に接続可能なディスプレイ上での計算結果を表示のためのディスプレイインターフェースを含む。
【００３９】
例えば、コンパイラデバイス４００は、コンピュータネットワークを介して通信する。コンピュータネットワークは、インターネット、イントラネット、ＬＡＮ、ＷＬＡＮなどである。コンピュータネットワークは、インターネットでもよい。コンピュータネットワークは、全体若しくは一部が有線、及び／又は全体若しくは一部が無線であってもよい。例えば、コンピュータネットワークは、イーサネット（登録商標）接続を含む。例えば、コンピュータネットワークは、Ｗｉ−Ｆｉ（登録商標）、ＺｉｇＢｅｅ（登録商標）などの無線接続を含む。デバイスは、必要に応じて他の電子デバイス（例えば他のコンピューティングデバイス及び／又はコンパイルデバイス）と通信するための接続インターフェースを含んでもよい。例えば、接続インターフェースは、コネクタ（例えば有線コネクタ、例えばイーサネット（登録商標）コネクタ、又は無線コネクタ、例えばアンテナ、例えばＷｉ−Ｆｉ（登録商標）、４Ｇ又は５Ｇアンテナ）を含む。例えば、デバイス４００は、通信インターフェース４３１を含む。
【００４０】
図４ｂは、コンパイラデバイス４００の一実施形態の一例を概略的に示す。コンパイラデバイス４００は、コンピュータプログラム表現を受信する通信インターフェース４３１を含む。例えば、コンピュータプログラム表現は、コンピュータネットワーク、又はコンピュータストレージなどから受信される。例えば、通信インターフェース４３１は、コンピュータネットワークインターフェース又はコンピュータストレージインターフェースである。例えば、コンピュータプログラム表現は、コンピュータ言語（例えばいわゆるソースコード）で書かれる。例えば、コンピュータプログラム表現は、ソースコードファイルである。例えば、ソースコードは、Ｃ、Ｃ＃、Ｃ＋＋、Ｓｗｉｆｔ、Ｊａｖａ（登録商標）、Ｆ＃などの高レベルのコンピュータプログラム言語で書かれる。例えば、コンピュータプログラム表現は、例えばテキストで書かれたステートメントの線形シーケンスを含む。
【００４１】
コンピュータ言語表現は、中間コンパイラ言語で書かれてもよい。例えば、中間コンパイラ言語には、レジスタ転送言語（ＲＴＬ）、中の中間言語表現（ＭＩＲ）、低の中間言語表現（ＬＩＲ）などの言語が含まれる。後者の２つの言語は、Ｓ．Ｍｕｃｈｎｉｃｋによる「Ａｄｖａｎｃｅｄ  Ｃｏｍｐｉｌｅｒ  ｄｅｓｉｇｎ  ＆  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」に説明されている。これらの中間言語は、例えばステートメント（例えば言語要素）のシーケンス（例えば配列など）として、線形に編成されるか、又はフラットである。中間言語では、ループ制御構造のようなものがもはや利用できなくなり、配列アクセスは、ポインタオフセットの観点から表現され、変数はすでに（シンボリック）レジスタに割り当てられている場合がある。
【００４２】
コンピュータ言語表現はまた、有向グラフの形態であってもよく、例えば、線形に順序付けられていなくてもよい。例えば、コンピュータ言語表現は、いわゆる制御フローグラフである。制御フローグラフ（ＣＦＧ）は、基本ブロックＢ１、…、Ｂｎをノードとする有向グラフである。制御がＢ１からＢ２に流れることができる場合、有向エッジＢ１→Ｂ２が存在する。コンピュータ言語表現は、静的単一代入（ＳＳＡ）形式にすることができるが、これは必須ではない。制御フローグラフは、中間表現、すなわち、ソースとターゲット機械語との間の途中にあるプログラムの表現である。ＣＦＧは、基本ブロックの代わりに、ノードとしてより小さなプログラム部分（例えば、基本ブロックとしての個々のステートメント）、又はより大きなプログラム部分（例えば、拡張基本ブロック）を有することができる。
【００４３】
ＣＦＧは、例えば、各プロシージャの中間コードを基本ブロックに分割することによって構築される。基本ブロックは一片の直線コードであり、例えば、ブロックの中央への又はそこからのジャンプがない。ＣＦＧは、グラフのソース及びシンクであるＥＮＴＥＲやＥＸＩＴなど、１つ以上の特殊なノードを有する。各基本ブロックの内部には、任意の既知の中間表現（例えばタプル、樹、ＤＡＧなど）があり得る。
【００４４】
コンピュータプログラムの様々な可能な表現は、互いに変換される。例えば、制御フローグラフは、コンピュータプログラム言語（例えばソースコード言語）及び／又はコンパイラ中間言語の表現から生成されてもよいし、又はその反対も可能である。
【００４５】
一実施形態では、デバイス４００は、第１のコンパイラ部４３２を含む。例えば、第１のコンパイラ部４３２は、第１のコンピュータプログラム表現を受け取り、第２のコンピュータプログラム表現を生成する。例えば、第１及び第２の表現は、異なる言語である。例えば、第１のコンピュータプログラム表現は、線形言語であり、第２のコンピュータプログラム表現は、樹（例えば制御フローグラフ）である。例えば、第１のコンピュータプログラム表現は、ソースコード言語（例えば高レベル言語）であり、第２のコンピュータプログラム表現はコンパイラ中間言語である。
【００４６】
例えば、一実施形態において、第１のコンパイラ部４３２は、パーサ、意味解析器、及びコード生成器を含む。コード発生器は、例えば、ＬＩＲ発生器、ＣＦＧ発生器などである。第１のコンパイラ部４３２は、オプティマイザ、レジスタアロケータなどを含んでもよい。
【００４７】
第１のコンパイラ部４３２は、変数の数を変更できる。例えば、変数は、例えば、デッドコード除去、強度低減などによって除去される。例えば、いくつかの変数が導入されてもよく、例えば、単一の変数が複数の変数に分割されてもよく、一時的な変数が導入されてもよい。
【００４８】
一実施形態では、通信インターフェース４３１は、内部インターフェース（例えばアプリケーションプログラミングインターフェース）である。例えば、通信インターフェース４３１は、例えば、既にコンパイラ中間言語であるコンピュータプログラムの中間形式か、又はＣＦＧ及び／若しくはＳＳＡなどの樹形式を受け取る。例えば、コンパイラデバイスは、さらなるコンパイラデバイスの一部（例えばサブルーチン）として使用される。
【００４９】
一実施形態では、コンピュータプログラム表現は、制御フローグラフである。ＣＦＧは、通信インターフェース４３１で受信されてもよいし、第１コンパイラ部４３２によって生成されてもよい。例えば、図３ａは、フラット表現と呼ばれることもある線形言語のコンピュータプログラム３１０のフラグメントの一例を示す。言語は、高レベルソースコード言語でもコンパイラ中間言語でもよい。プログラム３１０の最終行は「ｒｅｔｕｒｎ」とマークされて、例えば、サブルーチンからのリターンを示す。代わりに、プログラムフラグメントは、例えば、追加のプログラムステートメントなどを用いて継続することもできる。
【００５０】
図３ｂは、プログラム表現３１０から生成された制御フローグラフ３２０を示す。コンピュータプログラム表現は、より大きなコンピュータプログラム（例えば、ルーチン、プロシージャ、ユニット、ライブラリなど）の一部であり得る。基本ブロックの代わりに、コンピュータプログラムの部分への別の分割（例えば拡張基本ブロック）を使用してもよい。図３ｂのＣＦＧは、基本ブロックを含むノードを有する。例えば、ＣＦＧ３２０は６つの基本ブロックを含み、そのうちの３つは、基本ブロック３２１、３２２、及び３２３とマークされている。
【００５１】
コンパイラデバイス４００は、生存区間解析器４５０を含む。生存区間解析器４５０は、例えば、第１のコンパイラ部分４３２から、又は通信インターフェース４３１から、コンピュータプログラム表現４４０を受け取る。生存区間解析器４５０は、コンピュータプログラム表現４４０に対して生存変数（live variable）解析を行う。生存変数解析によって、コンピュータプログラム表現４４０に割り当てられた変数の集合４４２に関連付けられた生存区間領域４４４が生成される。変数の集合４４２は、生存区間解析器４５０によって生成されても、又は別のエンティティによって生成されてもよい。変数の集合４４２はまた、明示的に（例えば、割り当ての集合としてなど）、又は暗黙的に（例えば、それらの使用によって定義されるように）、コンピュータプログラム表現４４０の一部であり得る。
【００５２】
生存区間解析器４５０は、変数の集合のための定義情報（ｄｅｆｉｎｅ−ｉｎｆｏｒｍａｔｉｏｎ）及び使用情報（ｕｓｅ−ｉｎｆｏｒｍａｔｉｏｎ）を生成し得る。例えば、定義情報は、変数の書き込み場所を示し、使用情報は、変数の読み取り場所を示す。例えば、定義情報は変数が定義された（例えば宣言及び／又は変更された）ときを含む。
【００５３】
変数の集合４４２は、例えば、すべて変数で、例えば、未決定の順序にある。変数の集合４４２は、任意選択的に、変数の範囲又は生存区間範囲などのヒューリスティックスに従った順序にある、すべての変数の部分集合であり得る。
【００５４】
例えば、コンピュータプログラム表現４４０（例えば制御フローグラフ）は、基本ブロック（例えば基本ブロックノード）の集合を含む。生存区間領域及び定義／使用情報は、基本ブロック（例えば、ＣＦＧ内のノード）に関連付けられ得る。あるいは、生存区間情報は、ＣＦＧ内のエッジに関連付けられてもよい。
【００５５】
コンパイラ理論では、生存変数解析（生存区間解析とも呼ばれる）は、各プログラムポイントについて、次の書き込みの前に読み出される可能性がある変数（例えば、各プログラムポイントからの出口で生存している変数）を計算するためにコンパイラによって実行されるデータフロー解析である。変数は、将来必要とされ得る値を保持する場合、生存していると見なされ得る。
【００５６】
生存区間解析は、好ましくはステートメントごとに行われる。例えば、１つ以上の変数を書き込むか読み取るステートメントごとに、そのポイントにおいてどの変数が生存しているかが決定される。生存区間解析は、コンピュータプログラム表現が基本ブロックに分割されるときに行われてもよく、生存区間解析は、基本ブロック内の各ステートメントについて行われてもよい。例えば、基本ブロックはＣＦＧのノードである。生存区間解析にＣＦＧを使用するのではなく、フラットプログラムコード（例えばフラグメント３１０）に直接解析を行うこともできる。
【００５７】
生存区間解析は、生存変数の数を過大評価することが可能である。これにより、考慮からいくつかの可能なマスキングが外されるが、修正されたプログラムの正しさには影響しない。生存区間解析は、結果の生存集合が大きすぎることで、各ステートメントにわたる非生存集合が小さすぎる限り、不正確であり得る。
【００５８】
例えば、生存区間解析は、ブロック又はステートメントごとに、例えば行ごとに行われる。後者は、より細粒の生存区間領域が得られるので有利であり得る。生存区間解析はまた、ブロックごとに行うこともできるが、ブロック境界のみでの生存又は非生存情報では十分ではない場合がある。例えば、ブロック境界での生存区間解析は、各基本ブロックＢに、変数が書き込まれる前にＢで使用される変数の集合ｕｓｅ（Ｂ）、Ｂで書き込まれた変数の集合ｄｅｆ（Ｂ）、Ｂの始まりにおいて生存している変数の集合ｉｎ（Ｂ）、及びＢの終わりにおいて生存している変数の集合ｏｕｔ（Ｂ）を割り当てることができる。集合ｉｎ（）及びｏｕｔ（）は、再帰方程式：ｉｎ（Ｂ）＝ｕｓｅ（Ｂ）∪（ｏｕｔ（Ｂ）−ｄｅｆ（Ｂ））及びｏｕｔ（Ｂ）＝Ｕｓ∈ｓｕｃｃ（Ｂ）ｉｎ（Ｓ）を使用して定義される。Ｓｕｃｃ（Ｂ）は、Ｂのサクセサノードである。これらの方程式は、基本ブロックにわたって反復し、すべてのブロックについて方程式が満たされるまで、ｉｎ（Ｂ）及びｏｕｔ（Ｂ）を更新することによって満たすことができる。生存区間解析は、例えば、Ｍｕｃｈｎｉｃｋのセクション１４．１．３「Ｌｉｖｅ  ｖａｒｉａｂｌｅｓ  ａｎａｌｙｓｉｓ」のアルゴリズム、又はＡｎｄｒｅｗ  Ｗ．Ａｐｐｅｌ、Ｍａｊａ  Ｇｒｉｎｂｕｒｇによる「Ｍｏｄｅｒｎ  Ｃｏｍｐｌｉｅｒ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｉｎ  Ｃ」の第１０章（「ｌｉｖｅｎｓｓ  ａｎａｌｙｓｉｓ」）の生存区間アルゴリズムを使用する。
【００５９】
ブロックレベルでの生存区間解析の後、ステートメントレベルでの生存区間を得ることができる。例えば、ブロックの後方トラバーサルを行うことができ、ブロックのライブアウト（live-out）集合で初期化され、各ステートメントにわたる生存変数を決定するために使用される。例えば、ブロック境界に不正確な情報（生存が多すぎる）を格納できるが、非生存集合は好ましくは命令レベル粒度で決定される。変数は、ブロック境界では非生存であり、ブロック内では生存していることに留意されたい。例えば、所与の変数ｘの生存区間を推定するために、それは、ｘがｉｎ（Ｂ）、ｏｕｔ（Ｂ）又はｕｓｅ（Ｂ）のいずれかで発生するブロックＢで生存しているとみなされる。
【００６０】
例えば、生存区間解析は後退解析で行われる。解析は逆順に行われ、データフロー合流演算子は和集合に設定される。つまり、関数内の特定の数の論理枝を持つ関数に生存区間解析を適用する場合、解析は、関数の終わりから開始して始まりに向かって実行され、関数内で前方に移動する枝のいずれかが変数の現在値を必要とする可能性がある場合、変数は生存していると見なされる。
【００６１】
例えば、ＣＦＧ３２０の生存区間解析は、変数ｃがｏｕｔ（Ｂｌｏｃｋ  ３２２）、ｉｎ（Ｂｌｏｃｋ  ３２３）にあることを見つける。変数ｃの生存区間領域は、ブロック３２２及びブロック３２３であると結論付けられる。しかしながら、例えば、個々のステートメントのレベルでのより綿密な解析が、生存区間領域を変更する場合がある。例えば、変数ｃは、基本ブロック３２３の２行目では使用されないので、変数ｃの生存区間領域は、ブロック３２２とブロック３２３の１行目として定義される。ｉｎ（Ｂｌｏｃｋ  ３２１）は、変数ｂ、ｄ、ｘ、ｔ、ｆ、ｅであり、これらの変数は、推定されるように、コンピュータプログラム３１０の別のフラグメントで定義されていることに留意されたい。
【００６２】
例えば、ＣＦＧ３２０を考慮すると、変数の集合４４２は｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ，ｘ｝である。例えば、変数ｃはｏｕｔ（Ｂｌｏｃｋ  ３２２）であり、ｉｎ（Ｂｌｏｃｋ  ３２３）内であるので、変数ｃの生存区間領域はブロック３２２及び３２３である。集合４４２は、ヒューリスティック規則に従って制限され得る。例えば、変数（例えば変数ｘ）は、変数が異なるプログラムユニット（例えばライブラリなど）においてのみ定義される場合、例えば、システムライブラリにおいて定義される、例えば、決して又はほとんど変更されない、本質的に一定であるグローバル変数である場合、集合４４２から省略されてもよい。
【００６３】
生存区間領域は、暗黙的に格納されてもよい。例えば、一実施形態では、解析アルゴリズムの後に、プログラム内の特定のポイントで生存しているすべての変数が決定される。したがって、変数の生存区間領域に属するコード内の点が既知となる。例えば、コンピュータプログラム表現４４０は、生存区間情報で拡張される。例えば、コンピュータプログラム表現４４０のノード、線、又は要素は、そのポイントで生存している変数を示す情報に関連付けられる（例えばタグ付けされる）。関連情報には、定義情報及び使用情報も含まれてよい。あるいは、生存区間領域、定義情報及び使用情報のうちの１つ以上又はすべてがコンピュータプログラム表現４４０から外部に格納されてもよい。例えば、変数の集合４４２は、生存区間、定義、及び使用に関する関連情報を有する。例えば、変数の集合４４２、ならびに、生存区間、定義及び使用に関する変数に関連付けられる情報は、リスト、データベースなどに格納される。
【００６４】
コンピュータプログラム表現が、例えばテキストファイルのように、線形（例えばフラット）である場合、変数ｘの生存区間は、変数ｘが定義される最初のプログラムポイントｐ１、及び変数ｘが使用される最後のプログラムポイントｐ２として決定される。この表現の結果は、多すぎる変数がステートメントにわたって生存していると示され、したがって、非生存集合が小さすぎる。しかし、これはマスキングの可能性は少なくするが、正しさは妨害しない。
【００６５】
変数が複数の場所で定義されている場合、変数の生存期間を分割して、これらの生存期間のそれぞれを個別にマスクすることができる。しかしながら、このようなアプローチは、最初にＳＳＡ変換を適用し、次いで、生存区間解析を適用し、続いてマスキングアルゴリズムを適用することと同等である。
【００６６】
コンパイラデバイス４００は、セレクタ４６０を有する。セレクタ４６０は、変数の集合４４２から、第１の変数及び第２の変数を選択する。第２の変数は、第２の変数に関連付けられた定義情報に従って第１の変数に関連付けられた生存区間領域において定義されていない。
【００６７】
例えば、変数ｃを第１の変数と考える。基本ブロックレベル（例えば基本ブロック３２２及び３２３）で生存区間をとると、セレクタ４６０は、変数ａ、ｂ、ｄ、ｇ、ｈ、ｘのいずれか１つを第２の変数として選択する。これは、これらの変数のいずれもブロック３２２及び３２３において定義されていないからである。例えば、変数ｂを第２の変数とすると、ブロック３２２及び３２３（フラグメント３１０の３から６行目）は、次のように書き換えられる：
ｃ：＝ＥＮＣ（ｂ／ｄ，ｂ）
ｉｆ  ＤＥＣ（ｃ，ｂ）＜ｘ  ｇｏｔｏ  Ｌ２
ｅ：＝ｂ／ＤＥＣ（ｃ，ｂ）
ｆ：＝ｅ＋１
【００６８】
上記の場合、第１の変数ｃは、変数ｂを符号化パラメータとして使用して符号化され、同じ変数ｂを使用して復号される。この場合、第１の変数ｃが符号化される符号化演算が使用され、ｃが使用される復号演算が使用される。
【００６９】
書き換えは、デバイス４００のコード修正器４６２によって行われ得る。コード修正器４６２は、定義情報によって定義された場所において、かつ、少なくとも第２の変数を符号化パラメータとして使用して第１の変数を符号化する符号化コードを用いて、第１の変数に関連付けられた使用情報によって、コンピュータプログラム表現を修正し得る。ＥＮＣ及びＤＥＣの最初のパラメータの後のパラメータは、ここでは符号化パラメータとして使用される。これらは、ＤＥＣ（ＥＮＣ（ｘ，ｙ１，…，ｙｎ）ｙ１，…，ｙｎ）＝ｘという特性がある。
【００７０】
例えば、コード修正器４６２は、変数ｃがブロック３２２の１及び２行目ならびにブロック３２３の１行目で定義及び／又は使用されることを、定義情報及び使用情報から得る。あるいは、定義情報は、フラグメント３１０の３から５行目を指してもよい。この場合、コード修正器４６２は、第１の変数が定義されている符号化ルーチンと、第１の変数が使用されている復号ルーチンとを挿入する。
【００７１】
生存区間解析は、結果の生存集合が大きすぎることで、各ステートメントにわたる非生存集合が小さすぎる限り、不正確であり得る。生存区間解析がより小さい粒度で、例えばプログラム３１０において、例えばステートメントのレベルで行われる場合、変数ｅ及びｆは、ブロック３２３において定義されているが、変数ｃを符号化するために依然として使用され得ることが分かり得る。これは、後者の生存区間領域はブロック３２３の最終ステートメントに拡張されないからである。従って、フラグメントは以下のように修正され得る：
ｃ：＝ＥＮＣ（ｂ／ｄ，ｅ＋ｆ）
ｉｆ  ＤＥＣ（ｃ，ｅ＋ｆ）＜ｘ  ｇｏｔｏ  Ｌ２
ｅ：＝ｂ／ＤＥＣ（ｃ，ｅ＋ｆ）
ｆ：＝ｅ＋１
【００７２】
上記の例では、複数の第２の変数から導出された値、すなわち、この場合、第２の変数ｅ及びｆから導出された値ｅ＋ｆが符号化パラメータとして使用される。
【００７３】
第２の変数は、ランダムに選択されてもよい。例えば、セレクタ４６０は、複数の第２の変数を決定し、そこから変数がランダムに選択される。例えば、この場合、セレクタ４６０は、変数ａ、ｂ、ｄ、ｇ、ｈ、ｘからランダム変数を選択する。
【００７４】
一実施形態では、セレクタ４６０は、ヒューリスティックスを適用して、１つ以上の第２の変数を選択することができる。例えば、一実施形態では、セレクタ４６０は、第１の変数の生存区間領域により近い使用を有する第２の変数を選択する。例えば、変数ｄ及びｘは、変数ｃの生存区間領域におけるブロックの集合から距離１にあるブロックにおいて使用される変数ａ、ｂ、ｇ、ｈよりも近い変数ｃの生存区間領域において使用される。
【００７５】
同様に、セレクタ４６０は、第１の変数の生存区間領域により近い定義、より好ましくは一定ではない定義を有する第２の変数を選択し得る。例えば、変数ａ、ｂ、ｇ、ｈは、距離１のブロックにおいて定義され、変数ｄ、ｘは、このプログラムフラグメントでは定義されない。
【００７６】
例えば、セレクタ４６０は、異なるヒューリスティックスに従って異なる重み付けを割り当て、重み付けの合計に従って、集合４４２内の変数をランク付けする。１つ以上の変数は、高いランク、例えば、最も高いランク又は閾値を上回るランクなどを有する第２の変数として選択され得る。
【００７７】
一実施形態では、セレクタ４６０は、複数の第２の変数を選択し、コード修正器４６２は、複数の第２の変数を符号化パラメータとして使用する。例えば、同じプログラムコード行は、次のように書き換えられる：
ｃ：＝ＥＮＣ（ｂ／ｄ，ｂ，ｄ）
ｉｆ  ＤＥＣ（ｃ，ｂ，ｄ）＜ｘ  ｇｏｔｏ  Ｌ２
ｅ：＝ｂ／ＤＥＣ（ｃ，ｂ，ｄ）
ｆ：＝ｅ＋１
【００７８】
上記の場合、複数の符号化及び復号パラメータを取る符号化及び復号関数を使用する。あるいは、コードを次のように書き換えられる：
Ｉ：
Ｖ１：＝ＥＮＣ＿ＰＡＲＡＭ（ｂ，ｄ）
ｃ：＝ＥＮＣ（ｂ／ｄ，Ｖ１）
Ｖ２：＝：＝ＥＮＣ＿ＰＡＲＡＭ（ｂ、ｄ）
ｉｆ  ＤＥＣ（ｃ，Ｖ２）＜ｘ  ｇｏｔｏ  Ｌ２
Ｖ３：＝ＥＮＣ＿ＰＡＲＡＭ（ｂ，ｄ）
ｅ：＝ｂ／ＤＥＣ（ｃ，Ｖ３）
ｆ：＝ｅ＋１
又は、
ＩＩ：
Ｖ：＝ＥＮＣ＿ＰＡＲＡＭ（ｂ，ｄ）
ｃ：＝ＥＮＣ（ｂ／ｄ，Ｖ）
ｉｆ  ＤＥＣ（ｃ，Ｖ）＜ｘ  ｇｏｔｏ  Ｌ２
ｅ：＝ｂ／ＤＥＣ（ｃ，Ｖ）
ｆ：＝ｅ＋１
【００７９】
上記の場合Ｉ及びＩＩでは、符号化パラメータは、複数の第２の変数から計算され、第１の変数の符号化又は復号パラメータとして使用される。第１のオプションＩでは、符号化パラメータは、例えばそれが必要とされるたびに、又は少なくとも複数回計算される。第２のオプションＩＩでは、符号化パラメータは、例えば第１の符号化演算の前に、１回計算される。符号化及び復号演算は、有利には、入力として第１及び第２の変数を取るルックアップテーブル又は多項式関数を使用して行うことができる。例えば、第１の変数ｃを第２の変数ｙで符号化するには、Ｅｎｃ（ｃ，ｙ）＝ｔａｂｌｅ［ｃ］［ｙ］を使用する。
【００８０】
一実施形態では、符号化／復号は、マスキング演算であり得る。例えば、コードは次のように書き換えられる：
ｃ：＝（ｂ／ｄ）＋ｂ
ｉｆ  ｃ−ｂ＜ｘ  ｇｏｔｏ  Ｌ２
ｅ：＝ｂ／（ｃ−ｂ）
ｆ：＝ｅ＋１
【００８１】
上記の場合、マスキングは、算術マスキングであり、代わりにＸＯＲ演算を使用してもよい。
【００８２】
一実施形態では、セレクタ４６０は、第１の変数の生存区間領域の前に定義される、例えば、第１の変数の生存区間領域に生存する第２の変数のみを選択する。この選択の利点は、第２のコンパイラ部に通常のコンパイラを使用できることである。例えば、コード修正器４６２は、フラットプログラムコード（場合によっては中間、場合によっては高レベル）を修正することができ、デバイス４００は、従来のコンパイラを使用して、例えば、第２のコンパイラ部４３３でコンパイルを終了する。一実施形態では、変数が第１の変数の生存区間領域中に一定である限り、変数が定義される前に変数を使用することが可能である。しかしながら、変数が定義される前に変数を使用することは、従来のコンパイラを混乱させ、例えば、警告又はエラーにつながる。
【００８３】
一実施形態では、セレクタ４６０は、複数の第１の変数を選択し得る。例えば、選択された第１の変数は、同じ生存区間領域、重なり合う生存区間領域、又は閾値内にある（例えば２つの基本ブロック内にある）生存区間領域を有する。変数セレクタ４６０によって選択される１つ以上の第２の変数は、いずれの第１の変数の生存区間領域にも定義されない。
【００８４】
一実施形態では、コード修正器４６２は、第１の変数を剰余数系で符号化し、剰余数系のモジュライは、第２の変数から少なくとも部分的に導出される。剰余数系を使用することは、複数の第１の変数には特に有利である。例えば、プログラムコードは、次のように書き換えられる：
Ｖ１：＝ＲＮＳ＿ＭＯＤＵＬＵＳ（ｂ）
Ｖ２：＝ＲＮＳ＿ＭＯＤＵＬＵＳ（ｄ）
ｃ：＝ＲＮＳ＿ＥＮＣ（ｂ／ｄ，Ｖ１，Ｖ２）
ｉｆ  ＲＮＳ＿ＤＥＣ（ｃ，Ｖ１，Ｖ２）＜ｘ  ｇｏｔｏ  Ｌ２
ｅ：＝ｂ／ＲＮＳ＿ＤＥＣ（ｃ，Ｖ１，Ｖ２）
ｆ：＝ｅ＋１
あるいは、
Ｖ：＝ＲＮＳ＿ＭＯＤＵＬＩ（ｂ，ｄ）
ｃ：＝ＲＮＳ＿ＥＮＣ（ｂ／ｄ，Ｖ）
ｉｆ  ＲＮＳ＿ＤＥＣ（ｃ，Ｖ）＜ｘ  ｇｏｔｏ  Ｌ２
ｅ：＝ｂ／ＲＮＳ＿ＤＥＣ（ｃ，Ｖ）
ｆ：＝ｅ＋１
あるいは
Ｖ：＝ＲＮＳ＿ＭＯＤＵＬＩ（ｂ，ｄ）
ｃ：＝ＲＮＳ＿ＥＮＣ（ｂ／ｄ，Ｖ）
ｘ１：＝ＲＮＳ＿ＥＮＣ（ｘ，Ｖ）
ｉｆ  ＲＮＳ＿ＣＭＰ（ｃ，ｘ１）  ｇｏｔｏ  Ｌ２
ｅ：＝ｂ／ＲＮＳ＿ＤＥＣ（ｃ，Ｖ）
ｆ：＝ｅ＋１
【００８５】
第２のオプションでは、符号化パラメータＶは、複数の符号化パラメータ（ここでは、複数のＲＮＳパラメータ）の集合である。第３のオプションでは、変数ｘは、例えば生存区間領域が大きすぎることから、第１の変数として使用されないが、符号化された第１の変数と共に符号化された入力として使用できるように、一時的に符号化される。例えば、一実施形態では、コンパイラデバイス、例えばセレクタ４６０は、第１の変数の生存区間領域で使用されるが定義されない１つ以上のさらなる変数を選択する。１つ以上のさらなる変数は、第２の変数で符号化され得る。例えば、符号化されたさらなる変数は、第１の変数の生存区間領域の外側でもはや使用されない。例えば、デッドコード削除最適化が、符号化されたさらなる変数を除去する。符号化されたさらなる変数はこの領域において静的であるため、さらなる変数を、使用後に、例えば、復号することなく、廃棄しても差し支えない。
【００８６】
ＲＮＳモジュライを明示的に計算することが回避され得る。ＲＮＳモジュライの計算は、符号化／復号又は計算関数に統合され得る。例えば、コードは以下のように書き換えられる：
ｃ：＝ＲＮＳ＿ＥＮＣ（ｂ／ｄ，ｂ，ｄ）
ｘ１：＝ＲＮＳ＿ＥＮＣ（ｘ，ｂ，ｄ）
ｉｆ  ＲＮＳ＿ＣＭＰ（ｃ，ｘ１，ｂ，ｄ）  ｇｏｔｏ  Ｌ２
ｅ：＝ｂ／ＲＮＳ＿ＤＥＣ（ｃ，ｂ，ｄ）
ｆ：＝ｅ＋１
【００８７】
上記のコードでは、ＲＮＳ符号化及び復号演算は、１つ以上の符号化パラメータ（この場合、２：ｂ及びｄ）を取る。復号なしの比較演算などのＲＮＳ演算も、符号化パラメータ（複数可）を入力としても取り得る。例えば、符号化コード、復号コード、及び／又は演算コードは、符号化パラメータを入力として取り、そこから、例えば符号化パラメータをシードとして取ってＲＮＳモジュライを計算する。このアプローチの利点は、モジュライは、ＲＮＳ演算の外部に格納する必要がないことである。ＲＮＳでは、いくつかの演算を復号なしで行うことができる。例えば、ＲＮＳ＿ＡＤＤは復号を必要としない。
【００８８】
例えば、コード修正器４６２は、変数が定義された１つ以上の場所を取得し、符号化又はマスキングコードを追加する。例えば、定義ｃ：＝ｆ（ｘ１，…，ｘｎ）では、符号化は、第１の変数ｃが符号化されるように外部レベルで追加される。例えば、ｃ：＝ＥＮＣ（ｆ（ｘ１，…，ｘｎ），ｅｎｃｏｄｉｎｇ  ｖａｒｉａｂｌｅ（ｓ）。例えば、コード修正器４６２は、変数が使用される１つ以上の場所を取得し、復号又はデマスキングコードを追加する。例えば、使用ｙ：＝ｇ（ｃ，…）では、復号が第１の変数に追加される。例えば、ｙ：＝ｇ（ＤＥＣ（ｃ，ｅｎｃｏｄｉｎｇ  ｖａｒｉａｂｌｅ（ｓ），…）。
【００８９】
一実施形態では、コード修正器４６２は、符号化された第１の変数に対する演算を符号化された演算で置き換え得る。例えば、一実施形態では、同じ第２の変数で保護される複数の異なる第１の変数が特定される。例えば、変数ｃ１、ｃ２、及びｃ３はすべて、同じ１つ以上の変数ｖで符号化される。
【００９０】
符号化されていない第１の変数に対する演算ｃ１＝ｆ（ｃ１，ｃ２）を、ｃ１＝Ｆ（ｃ１，ｃ２）又はｃ１＝ｆ（ｃ１，ｃ２，ｖ）に置き換え得る。ここで、関数Ｆは、符号化された変数を入力として取り、符号化された変数を出力として生成する。関数が符号化されていない変数に出力する場合、符号化された変数を入力として取り、符号化されていない出力、例えばｄ＝Ｆ（ｃ１，ｃ２，ｖ）を生成する関数を使用し得、ここで、ｄは符号化されていない。例えば、マスキングを例にとると、ｃ１、ｃ２、ｃ３、ｃ４を第１の変数とし、ｖを１つ以上の第２の変数とし、ｄを符号化されていない変数として、次のプログラムフラグメント：
ｃ１：＝ａ
ｃ２：＝ｂ
ｃ３：＝ＡＤＤ（ｃ１，ｃ２）
ｄ：＝ＡＤＤ（ｃ３，ｃ２）
ｃ４：＝ＡＤＤ（ｃ１，ｄ）
は、（Ｉ）のように符号化され得る。
ｃ１：＝ＡＤＤ（ａ，ｖ）
ｃ２：＝ＡＤＤ（ｂ，ｖ）
ｃ３：＝ＡＤＤ（ＳＵＢ（ｃ１，ｖ），ＳＵＢ（ｃ２，ｖ），ｖ）
ｄ：＝ＡＤＤ（ＳＵＢ（ｃ３，ｖ），ＳＵＢ（ｃ２，ｖ））
ｃ４：＝ＡＤＤ（ＳＵＢ（ｃ１，ｖ），ｄ）
しかし、（ＩＩ）としても符号化され得る。
ｃ１：＝ＡＤＤ（ａ，ｖ）
ｃ２：＝ＡＤＤ（ｂ，ｖ）
ｃ３：＝ＡＤＤ＿１（ｃ１，ｃ２，ｖ）
ｄ：＝ＡＤＤ＿２（ｃ３，ｃ２，ｖ）
ｃ４：＝ＡＤＤ＿３（ｃ１，ｄ）
【００９１】
実施例（Ｉ）では、符号化演算が第１の変数の各定義に追加され（この場合、符号化は算術マスキング）、復号演算が第１の変数の各使用に追加される（この場合、復号は算術デマスキング）。
【００９２】
実施例（ＩＩ）では、第１の変数を定義する演算ｃ３：＝ＡＤＤ（ｃ１，ｃ２）が第１の変数で特定される。演算ＡＤＤは、演算ＡＤＤ＿１に置き換えられる。演算ＡＤＤ＿１は、符号化された変数を入力とし、符号化された変数を出力として生成する。この場合、ＡＤＤ＿１はｃ１＋ｃ２−ｖとして定義できる。
【００９３】
さらに、符号化されていない変数を定義する演算ｄ：＝ＡＤＤ（ｃ３，ｃ２）が第１の変数で特定される。演算ＡＤＤは、演算ＡＤＤ＿２に置き換えられる。演算ＡＤＤ＿２は、符号化された変数を入力として取り、符号化されていない変数を出力として生成する。この場合、ＡＤＤ＿２はｃ１＋ｃ２−２ｖとして定義できる。
【００９４】
符号化及び／若しくは非符号化入力、並びに／又は、符号化及び／若しくは非符号化出力の他の組合せも可能である。例えば、演算ｃ４：＝ＡＤＤ（ｃ１，ｄ）は、混合された符号化入力及び符号化出力を有する。演算ＡＤＤは、符号化された変数と符号化されていない変数の組合せを入力として取り、符号化された変数を出力として生成する演算ＡＤＤ＿３に置き換えられ得る。この場合、ＡＤＤ＿３はｃ１＋ｄとして定義できる。
【００９５】
なお、これらの例では、置換された演算は、第２の変数を入力として取る場合もあれば、取らない場合もある。演算の置換は、演算が符号化された領域で行われ得る準同型符号化に特に有利である。例えば、符号化は、ある数を、１つ以上の第２のモジュライに依存するモジュライを有するＲＮＳ数系に変換する。ＲＮＳ符号化数に対する演算はＲＮＳ演算で置き換えることができる。例えば、加算又は乗算を、ＲＮＳ加算又は乗算などで置き換えることができる。
【００９６】
例として、以下の典型的なＣプログラムフラグメントを考える：
（．．．）
ｆｏｒ（ｉｎｔ  ｉ＝０；ｉ＜＝１０；ｉ＋＋）
｛
ｆｏｒ（ｉｎｔ  ｊ＝０；ｊ＜＝１０；ｊ＋＋）
｛
ｄａｔａ［ｉ，ｊ］＝０；
}
}
（．．．）
【００９７】
生存区間解析器は、変数ｉ及びｊがほぼ同じ生存区間領域、例えば、それらの生存区間領域が重なり合い、それらの差が閾値内にあることを見出し得る。したがって、変数ｉ及びｊは、第２の変数（必ずしも上記に示されていない）に依存するモジュライを有するＲＮＳ数系において符号化され得る。ループインデックスのすべての計算は、符号化された変数に対して行われてよい。しかしながら、変数は、例えば、配列へのポインタを計算するために復号されてもよい。なお、中間コードへの変換は、例えば、適切なインデックスにおける配列へのポインタを計算するために、追加の一時変数を導入し得る。
【００９８】
一実施形態では、コンパイラデバイスは、複数の第１の変数を選択する。第１の変数は、重複する生存区間領域と、１つ以上の第２の変数とを有する。複数の第１の変数の各々は、１つ以上の第２の変数で符号化され得る。追加の制約を第１の変数に課してもよい。例えば、第１の変数は、それらの生存区間領域が近い、例えば、２つの第１の変数の２つの生存区間領域間の距離が小さい、例えば、せいぜい閾値であるものが決定される。距離は、生存区間領域のうちの１つのみにある基本ブロックの数であり得る。さらに、例えば、使用ステートメントにおいて一緒に発生する対話（例えば、上記の例における配列割り当て）を共有する第１の変数を選択することができる。
【００９９】
一実施形態では、セレクタは、例えばプロシージャ内でループに対してローカルに定義される１つ以上の第１の変数を選択する。
【０１００】
一実施形態では、集合４４２に複数の変数があり得る。潜在的な第１の変数が、集合４４２から、例えば、ランダムに、又は集合４４２内の変数を順番に考慮することによって、選択される。潜在的な第１の変数について、第２の変数が存在するかどうか、例えば、第１の変数の生存区間領域中に静的である集合４４２内の第２の変数が存在するかどうかが決定され得る。そのような第２の変数が存在しない場合、潜在的な第１の変数は破棄され、次の潜在的な第１の変数が、例えば、適切な１つ以上の第１の変数及び１つ以上の第２の変数が見つかるまで、選択され、試行され得る。
【０１０１】
第１の変数の選択は、プログラマの影響を受ける場合もある。例えば、コンパイラディレクティブがコンピュータプログラム表現、例えば、高レベルソースコード表現に挿入される。例えば、ディレクティブは、＃ｐｒｏｔｅｃｔである。セレクタ４６０は、まず、ディレクティブを有する変数について１つ以上の第２の変数を見つける。このような第２の変数が見つからない場合には、警告信号が生成され得る。警告信号はディスプレイに表示され得る。別のコンパイラディレクティブは、＃ｃｏｎｆｉｄｅｎｔｉａｌであり得る。このディレクティブが使用される場合、このディレクティブでマークされた変数は、パスワードなどである可能性があるため、第２の変数として使用すべきではない。
【０１０２】
コンパイラ４００は、コンピュータプログラムコード表現４４０上で複数の反復を実行し得る。例えば、第１及び第２の変数を選択し、コードを修正する複数回の反復である。反復を通じて、コンピュータプログラムはますます難読化される。一実施形態による難読化は、従来の難読化と組み合わされ得る。例えば、難読化ユニットが、ダミー変数、ダミーコードを導入し、変数を符号化し、関数をテーブルに置換し、制御フローを複雑化する。特に、一実施形態による難読化は、専用マスキング変数を有する従来のマスキングと組み合わされ得る。例えば、一実施形態では、生存区間解析を使用して、第１及び第２の変数が選択される。第１の変数は、第２の変数及び固定マスキング定数を使用して符号化され得る。
【０１０３】
実施形態は、自動化された難読化解除及びスクレーピング攻撃から保護する。スクレーピング攻撃は、プログラムを解釈しようとすることなく、プログラム内のすべての値を潜在的なキーとして試みることによって、キーを回収することを目的とする。
【０１０４】
コンピュータプログラム表現４４０の修正後、コンパイルは、例えば、第２のコンパイラ部４３３によって完了され得る。例えば、第２のコンパイラ部４３３は、コード生成、例えば、コンピュータプログラム表現４４０のターゲット言語（例えば機械語）へのマッピングを行う。しかしながら、第２のコンパイラ部４３３は、追加のコンパイルステップ（例えば、最適化、レジスタ割当てなど）を行ってもよい。なお、生存区間解析は、コンパイラデバイス４００（例えば、第１のコンパイラ部４３２、第２のコンパイラ部４３３）において、例えば、他の目的（例えば、最適化、レジスタ割り当てなど）のために、複数回行われてもよい。
【０１０５】
レジスタ割り当てとは、ＩＲ内の変数に（物理）レジスタを割り当てるプロセスを指す。これは、ＩＲにおいて、同時に生きている多くの変数があるが、コンピュータのレジスタの数は限られているので、重要である。レジスタ割り当ては、変数の生存区間解析（例えば、生存期間の解析）によって実現される。
【０１０６】
例えば、一実施形態では、第１のコンパイラ部４３２は、構文解析及び中間コード生成のために構成される。構文解析後、コンパイラデバイスは、ソースコードの中間コードを生成し得る。これは、何かの抽象機械又はターゲットデバイス用のプログラムを表し得る。これは、典型的には高レベル言語と機械語との間にある。中間コードは、ＳＳＡ形式であってもよい。
【０１０７】
第２のコンパイラ部４３３は、コード生成のために構成され得る。例えば、コード生成器が中間コードの表現を取り、それをターゲット機械語にマッピングする。コード生成器は、中間コードを機械コードのシーケンスに翻訳する。機械コードは、再配置可能であってよい。
【０１０８】
第１及び第２のコンパイラ部のいずれか１つ（例えば第１及び第２のコンパイラ部のうちの１つ、いずれでもない、又は両方）が、追加のコンパイラタスクを行い得る。追加のコンパイラタスクは、コード最適化、及び割り当てを含み得る。コードの最適化により、不要なコードが削除され、一連のステートメントがある順序に配置されて、プログラムの実行が高速化され得る。割り当て中に、レジスタ、メモリなどが変数に割り当てられ得る。
【０１０９】
コンパイルデバイスは、コンパイラプログラムの形式であってもよい。コンパイラは、プログラム、例えば、その変数及び／又はその処理されたデータを保護し得る。有利には、コンパイラは、少なくとも部分的に、符号化された領域で実行されるプログラムＰを自動的に作成し得る。プログラマが、プログラムをプレーン領域でコード化し、後になって、プログラマがそのプログラムを暗号化された領域で実行することに関心がある場合にのみ、プログラムＰを暗号化された領域に向けてコンパイルすることができる。
【０１１０】
コンパイラでは、例えば、第１のコンパイラ部４３２による部分コンパイルの後に、グラフ表現、又はプログラムの中間表現（ＩＲ）が得られる。一実施形態では、ＩＲプログラムは、右辺が最大２つのオペランドを含むように、一連のステートメントとして表される。プログラムのＩＲ表現は、ＳＳＡ特性を有するように変換できる。
【０１１１】
コンパイル及びＳＳＡ変換の後、結果のデータフローグラフには、ｐｈｉ命令及びコピー命令を使用するブロックのサブネットワークが含まれ得る。このようなネットワークの境界は、異なるタイプのステートメント、例えば、算術演算、メモリ演算などをもつノードによって表される。
【０１１２】
一実施形態では、第１のステップは、入力プログラムをＳＳＡ特性を有する中間表現に変換することであり得る。このステップは必須ではないが、次のステップを容易にする。静的単一代入（ＳＳＡ）特性：各変数が１回だけ割り当てられ、すべての変数は使用前に定義される。このグラフでは、エッジは（時間的）変数で、ノードは演算（＋、−、＊、…）、メモリアクセス（＊ｐ＝…）などである。ｐｈｉ演算を使用して、グラフ内のデータ選択を実施する。例えば、ｚ＝ｐｈｉ（ａ，ｂ）は、ａへの最後の割り当てがｂへの最後の割り当てよりも最近であるとき、ａがｚに割り当てられるべきであり、又はその逆も同様であることを意味する。
【０１１３】
次のステップは、生存区間解析を実行することであり、例えば、プログラム実行の後の時点で依然として使用される変数を含むリストが取得される。単一の変数Ｂがあるとする。この情報があると、変数Ａ１、Ａ２、Ａ３、及び関連する演算を保護できる。例えば、以下の演算を考える：
Ａ３＝Ａ１＊Ａ２＋Ａ２
【０１１４】
このような演算及び変数は、Ｂ（又は変数Ｂの集合）によって、異なるやり方で保護できる。
【０１１５】
難読化を適用する場合、変数ＢをＸＯＲマスクとして使用できる：
Ａ１＝Ａ１  ＸＯＲ  Ｂ
Ａ２＝Ａ２  ＸＯＲ  Ｂ
．．．
Ａ３＝（（（Ａ１  ＸＯＲ  Ｂ）＊（Ａ２  ＸＯＲ  Ｂ））＋（Ａ２  ＸＯＲ  Ｂ））ＸＯＲ  Ｂ
【０１１６】
これは、メモリにＡ１、Ａ２、及びＡ３に保持する代わりに、Ｂを用いてＸＯＲされた値を保持することを意味する。Ｂは、上記の保護範囲において生きており、静的であることを想起されたい。Ｂは、プログラム内の任意の通常の変数であってもよく、それ自体がプログラムの何らかの機能を果たす。
【０１１７】
符号化を適用する場合、変数Ａ１、Ａ２、及びＡ３を使用する演算を同様のやり方で保護できる。剰余数系（ＲＮＳ）の使用を考える。モジュライＮ及びモジュライｑ０，…，ｑ｛Ｎ−１｝の数を返す関数ＲＮＳ＿ｐａｒａｍ（ｘ）があると仮定する。
Ａ１＿ｒｎｓ＝ＲＮＳ＿ｒｅｐ（Ａ１，ＲＮＳ＿ｐａｒａｍ（Ｂ））
Ａ２＿ｒｎｓ＝ＲＮＳ＿ｒｅｐ（Ａ２，ＲＮＳ＿ｐａｒａｍ（Ｂ））
．．．
Ａ３＿ｒｎｓ＝ＲＮＳ＋（ＲＮＳ＊（Ａ１＿ｒｎｓ，Ａ２＿ｒｎｓ），Ａ２＿ｒｎｓ）
【０１１８】
２つの関数ＲＮＳ＋及びＲＮＳ＊について。上記の行では、ＲＮＳ＿ｒｅｐ（ｘ，ｙ）が、モジュライｑ０，…，ｑ｛Ｎ−１｝の数Ｎを所与として、ｘのＲＮＳ表現を返す。ＲＮＳ＊（ｘ，ｙ）が、ｘとｙとのＲＮＳ表現間の乗算を行う。ＲＮＳ＋（ｘ，ｙ）が、ｘとｙとのＲＮＳ表現間の加算を行う。
【０１１９】
なお、保護は、変数Ａ１、Ａ２、Ａ３、…、Ａｘを保護するために、変数Ｂ１、Ｂ２、…、ＢＭの集合（上記の例のようにＢだけでなく）を使用することによっても実現できる。これは、関数ＣＯＭＢＩＮＥ（Ｂ１，Ｂ２，…，ＢＭ）を使用してＸＯＲマスク（難読化の場合）として又はＲＮＳ＿ｐａｒａｍ（）への入力として使用される値を導出することで行われる。一実施形態では、難読化及び／又は符号化は、集合Ｂ内の変数の生存期間が終了する前に逆転される必要がある。また、複数の変数集合を有するネストされたスコープを使用することも可能であることに留意されたい。例えば、ＢがＡに対して静的であり、ＣがＢに対して静的であり、ＤがＣに対して静的であると仮定する。この場合、例えば、ＤはＣを符号化するために使用され、ＣはＢを符号化するために使用され、ＢはＡを符号化するために使用される。
【０１２０】
生存集合対非生存集合の重要性に留意されたい。大きすぎる「生存」へのあらゆるアプローチは、小さすぎる非生存をもたらすが、これは、マスキングの正しさには影響しない。しかし、推定は可能であるが、ステートメントレベルで特定の変数に対してこの非生存特性を確立する必要がある。
【０１２１】
「変数の生存集合」を考慮するプログラム内のポイントは、ステートメントの直前及び直後である。この集合を計算するために、すべての可能な将来の実行を考慮できる。効率を改善するために、例えば、上述のような既知のアルゴリズムを使用して、各基本ブロックの始まり及び終わりにおいて完全な最終生存集合を計算する。次に、ブロックのライブアウト（live-out）集合で初期化されたブロックの後方トラバーサルを使用して、各ステートメントにわたる生存変数を決定する。
【０１２２】
アウトマスキングアルゴリズムについては、「変数「ａ」は、変数「ｘ」の生存期間中に変更しないか」という問題に関心がある。これは、変数「ａ」を変更する各ステートメントＳについて、変数「ｘ」は、「Ｓ」の実行中に非生存が保証されているか、と言い換えられる。（また、「「Ｓ」の実行中」とは、「Ｓの直前及び直後」を意味する）。
【０１２３】
したがって、特定の潜在的なマスク変更ステートメントにわたって、非生存集合に関心があり、したがって、完全な生存区間解析を行う必要がない。変数「ｘ」が、特定のステートメント全体にわたって非生存が保証されていることを示すだけで十分である。以下の例では、これを、時に、大域解析を行わずに推定する方法を示す。しかしながら、大域解析は非常に安価であるため、通常、それを使用しない説得力のある理由はない。さらに、大域生存区間解析では、生存していないことが保証される変数の集合が最大（生存集合の逆数）であり、これは、可能なマスクの集合を増加させる。
【０１２４】
実施例：以下のブロックを考える：
ｘ＝１０；
ｙ＝ｓ；
ｚ＝ｙ＋ｘ；
．．．
ｔ＝ｆ（ｚ）
【０１２５】
ローカルでは、変数ｚは、ステートメントｙ＝ｓの前又は後では非生存であると結論付けることができる。「ｙ＝ｓ」が「ｙ」を変更する唯一のステートメントである場合、「ｙ」を使用して「ｚ」をマスクできる。
ｘ＝１０；
ｙ＝ｓ；
ｚ＝ｍａｓｋ（ｙ＋ｘ，ｙ）；
．．．
ｔ＝ｆ（ｕｎｍａｓｋ（ｚ，ｙ））
ｚは、ｙへの割り当て中は非生存であるため、ｚの使用は、それがプログラムのどこにあろうとも、「ｙ＝ｓ」の影響を受けない。
【０１２６】
例えば線形プログラムテキストのプロパティに基づく他のアプローチも、保護したい変数が保護変数を変更するステートメントで非生存であると決定できれば、うまくいく。したがって、ステートメント全体で多すぎる変数を生存とマークするあらゆる種類の解析が、関数的に正しい結果につながる。
【０１２７】
コンパイラデバイス４００の様々な実施形態では、通信インターフェースを、様々な代替形態から選択できる。例えば、インターフェースは、ローカルエリアネットワーク又はワイドエリアネットワーク（例えばインターネット）へのネットワークインターフェース、内部又は外部データストレージへのストレージインターフェース、キーボード、アプリケーションインターフェース（ＡＰＩ）などである。
【０１２８】
コンパイラデバイス４００は、１つ以上のボタン、キーボード、ディスプレイ、タッチスクリーンなどのよく知られている要素を含むユーザインターフェースを有し得る。ユーザインターフェースは、コンパイル動作を行うためのユーザとの対話に対応する。
【０１２９】
コンパイラデバイス４００用のストレージは、電子メモリ（例えばフラッシュメモリ）、又は磁気メモリ（例えばハードディスク）などとして実装され得る。ストレージは、全体でストレージを構成する複数のディスクリートメモリを含んでもよい。ストレージはまた、一時的なメモリ、例えばＲＡＭでもよい。
【０１３０】
典型的には、デバイス４００は、デバイス４００に格納されている適切なソフトウェアを実行するマイクロプロセッサを含む。例えば、そのソフトウェアは、ダウンロードされて、対応するメモリ（例えばＲＡＭといった揮発性メモリ又はフラッシュといった不揮発性メモリ）に格納されていてよい。あるいは、デバイス４００は、プログラマブルロジック、例えば、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）として、全体的に又は部分的に実装されてもよい。デバイス４００は、いわゆる特定用途向け集積回路（ＡＳＩＣ）、例えば、特定使用のためにカスタマイズされた集積回路（ＩＣ）として、全体的に又は部分的に実装されてもよい。例えば、回路は、例えば、Ｖｅｒｉｌｏｇ、ＶＨＤＬなどのハードウェア記述言語を使用して、ＣＭＯＳで実装されてもよい。
【０１３１】
一実施形態では、コンパイラデバイス４００は、第１のコンパイラ部回路、第２のコンパイラ部回路、生存区間解析回路、変数セレクタ回路、及びコード修正子回路のうちの１つ以上を含む。回路は、本明細書に説明した対応するユニットを実現する。回路は、プロセッサ回路及びストレージ回路であってよく、プロセッサ回路は、ストレージ回路において電子的に表現されている命令を実行する。
【０１３２】
プロセッサ回路は、分散方式で、例えば、複数のサブプロセッサ回路として実装されてもよい。ストレージは、複数の分散サブストレージにわたって分散されてもよい。メモリの一部又は全部は、電子メモリ、磁気メモリなどであってもよい。例えば、ストレージは揮発性部分と不揮発性部分とを有する。ストレージの一部は、読み取り専用であってもよい。
【０１３３】
図５は、コンパイラ方法５００の一実施形態の一例を概略的に示す。コンパイラ方法５００は、コンピュータプログラムを難読化する。コンパイラ方法は、コンピュータプログラム表現を受け取るステップ（５１０）と、コンピュータプログラム表現に生存変数解析を行うステップ（５２０）であって、生存変数解析によって、コンピュータプログラム表現において割り当てられている変数の集合（４４２）に関連付けられた生存区間領域（４４４）、定義情報、及び使用情報が取得される、ステップと、変数の集合から第１の変数及び第２の変数を選択するステップ（５３０）であって、第２の変数は、第２の変数に関連付けられている定義情報に従って第１の変数に関連付けられている生存区間領域において定義されていない、ステップと、定義情報によって、かつ、第１の変数に関連付けられている使用情報によって定義された場所において、少なくとも第２の変数を符号化パラメータとして使用して第１の変数を符号化する符号化コードを用いて、コンピュータプログラム表現を修正するステップ（５４０）とを含む。
【０１３４】
当業者には明らかなように、本方法を実行する多くの異なる方法が可能である。例えば、ステップは、示された順序で行うことができるが、ステップの順序を変更しても、いくつかのステップを並列に行ってもよい。さらに、ステップ間に、他の方法ステップを挿入してもよい。挿入されたステップは、本明細書で説明される方法の改良を表しても、本方法とは無関係であってもよい。さらに、所与のステップは、次のステップが開始される前に完全に終了していなくてもよい。
【０１３５】
本方法の実施形態は、プロセッサシステムに方法５００を行わせるための命令を含むソフトウェアを使用して実行され得る。ソフトウェアは、システムの特定のサブエンティティによって行われるステップのみを含み得る。ソフトウェアは、ハードディスク、フロッピー（登録商標）、メモリ、光ディスクなどの適切な記憶媒体に記憶され得る。ソフトウェアは、有線、無線、又はデータネットワーク（例えば、インターネット）を使用して、信号として送信され得る。ソフトウェアは、サーバ上でのダウンロード及び／又はリモート使用のために利用可能にされ得る。本方法の実施形態は、本方法を行うように、プログラマブルロジック、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）を構成するビットストリームを使用して実行され得る。
【０１３６】
以下の番号付けされた節は、企図され、限定されない実施形態を含む。第１節：コンピュータプログラムを難読化するためのコンパイラデバイス（４００）であって、コンピュータプログラム表現を受け取る通信インターフェース（４３１）と、プロセッサと、を含み、プロセッサは、コンピュータプログラム表現に生存変数解析を行い、生存変数解析によって、コンピュータプログラム表現内で割り当てられている変数の集合（４４２）に関連付けられている生存区間領域（４４４）、定義情報、及び使用情報が取得される。プロセッサはさらに、変数の集合から第１の変数及び第２の変数を選択し、第２の変数は、第２の変数に関連付けられた定義情報に従って第１の変数に関連付けられた生存区間領域内で定義されていない。プロセッサはさらに、定義情報によって、かつ、第１の変数に関連付けられた使用情報によって定義された場所において、少なくとも第２の変数を符号化パラメータとして使用して第１の変数を符号化する符号化コードを用いてコンピュータプログラム表現を修正する。第２節：コンピュータプログラムを難読化するためのコンパイラ方法（５００）であって、コンピュータプログラム表現を受け取るステップ（５１０）と、コンピュータプログラム表現に生存変数解析を行うステップ（５２０）であって、生存変数解析によって、コンピュータプログラム表現内で割り当てられている変数の集合（４４２）に関連付けられている生存区間領域（４４４）、定義情報、及び使用情報が取得される、ステップと、変数の集合から第１の変数及び第２の変数を選択するステップ（５３０）であって、第２の変数は、第２の変数に関連付けられた定義情報に従って第１の変数に関連付けられた生存区間領域内で定義されていない、ステップと、定義情報によって、かつ、第１の変数に関連付けられた使用情報によって定義された場所において、少なくとも第２の変数を符号化パラメータとして使用して第１の変数を符号化する符号化コードを用いてコンピュータプログラム表現を修正するステップ（５４０）とを含む。
【０１３７】
本発明はまた、本発明を実施するように適合されたコンピュータプログラム、特に担体上又は担体内のコンピュータプログラムに拡張されることが理解されるのであろう。プログラムは、ソースコード、オブジェクトコード、コード中間ソース、及び部分的にコンパイルされた形態などのオブジェクトコードの形態であっても、又は本方法の実施形態の実装で使用するのに適した任意の他の形態であってもよい。コンピュータプログラム製品に関する一実施形態は、記載された方法のうちの少なくとも１つの方法の処理ステップのそれぞれに対応するコンピュータ実行可能命令を含む。これらの命令は、サブルーチンに分割されても、静的又は動的にリンクされる１つ以上のファイルに格納されてもよい。コンピュータプログラム製品に関する別の実施形態は、記載されたシステム及び／又は製品のうちの少なくとも１つのシステム及び／又は製品の手段のそれぞれに対応するコンピュータ実行可能命令を含む。
【０１３８】
図６ａは、コンピュータプログラム１０２０を含む書き込み可能部分１０１０を有するコンピュータ可読媒体１０００を示す。コンピュータプログラム１０２０は、プロセッサシステムに、一実施形態によるコンパイラ方法を行わせる命令を含む。コンピュータプログラム１０２０は、物理マークとして、又はコンピュータ可読媒体１０００の磁気化によって、コンピュータ可読媒体１０００上で具現化され得る。しかしながら、任意の他の適切な実施形態も考えられる。さらに、ここでは光ディスクとして示されているが、コンピュータ可読媒体１０００は、ハードディスク、ソリッドステートメモリ、フラッシュメモリなどの任意の適切なコンピュータ可読媒体であってもよく、記録不可能又は記録可能であってもよいことが理解されるであろう。コンピュータプログラム１０２０は、プロセッサシステムに、コンパイラ方法を行わせる命令を含む。
【０１３９】
図６ｂは、コンパイラデバイスの一実施形態によるプロセッサシステム１１４０の概略図を示す。プロセッサシステムは、１つ以上の集積回路１１１０を含む。図６ｂでは、１つ以上の集積回路１１１０のアーキテクチャを概略的に示す。回路１１１０は、一実施形態による方法を実行する、及び／又はそのモジュール若しくはユニットを実現するためにコンピュータプログラムコンポーネントを実行させるための処理ユニット１１２０（例えばＣＰＵ）を含む。回路１１１０は、プログラミングコード、データなどを格納するためのメモリ１１２２を含む。メモリ１１２２の一部は読み出し専用であってもよい。回路１１１０は、通信要素１１２６、例えば、アンテナ、コネクタ又はその両方などを含んでもよい。回路１１１０は、方法で定義された処理の一部又は全部を行うための専用集積回路１１２４を含んでもよい。プロセッサ１１２０、メモリ１１２２、専用ＩＣ１１２４、及び通信要素１１２６は、相互接続部１１３０（例えばバス）を介して互いに接続され得る。プロセッサシステム１１１０は、アンテナ及び／又はコネクタをそれぞれ使用して、接触及び／又は非接触通信用に構成されてもよい。
【０１４０】
例えば、一実施形態では、プロセッサシステム１１４０（例えば、コンパイラデバイス）は、プロセッサ回路及びメモリ回路を含み、プロセッサ回路は、メモリ回路に格納されているソフトウェアを実行する。例えば、プロセッサ回路は、ＩｎｔｅｌＣｏｒｅ  ｉ７（登録商標）プロセッサ、ＡＲＭＣｏｒｔｅｘ−Ｒ８（登録商標）などである。一実施形態では、プロセッサ回路は、ＡＲＭＣｏｒｔｅｘ  Ｍ０（登録商標）とすることができる。メモリ回路は、ＲＯＭ回路であってもよいし、フラッシュメモリなどの不揮発性メモリであってもよい。メモリ回路は、揮発性メモリ、例えばＳＲＡＭメモリであってもよい。後者の場合、デバイスは、ソフトウェアを提供するように構成された不揮発性ソフトウェアインターフェース、例えばハードドライブ、ネットワークインターフェースなどを含み得る。
【０１４１】
上述の実施形態は、本発明を限定するものではなく、例示するものであり、当業者は、多くの代替実施形態を設計することができることに留意されたい。
【０１４２】
請求項において、括弧内に付された参照記号は、請求項を限定するものと解釈してはならない。動詞「有する」及びその活用形の使用は、請求項に記載されたもの以外の要素又はステップの存在を排除するものではない。単数形は、複数のそのような要素の存在を排除するものではない。本発明は、いくつかの別個の要素を含むハードウェアによって、及び適切にプログラムされたコンピュータによって実施され得る。いくつかの手段を列挙する装置請求項において、これらの手段のいくつかは、ハードウェアの１つの同じアイテムによって具現化され得る。特定の手段が相互に異なる従属請求項に記載されているという単なる事実は、これらの手段の組合せを有利に使用することができないことを示すものではない。
【０１４３】
特許請求の範囲では、括弧内の参照が例示的な実施形態の図面又は実施形態の式における参照符号を指し、したがって、特許請求の範囲の理解度を高める。これらの参照は、請求項を限定するものと解釈してはならない。
【図１】
2021530057.tif 000004
【図２】
2021530057.tif 000005
【図３ａ】
2021530057.tif 000006
【図３ｂ】
2021530057.tif 000007
【図４ａ】
2021530057.tif 000008
【図４ｂ】
2021530057.tif 000009
【図５】
2021530057.tif 000010
【図６ａ】
2021530057.tif 000011
【図６ｂ】
2021530057.tif 000012
【国際調査報告】
2021530057.tif 000013
2021530057.tif 000014