(57)【要約】  ソースコードコンピュータプログラム１０２をオブジェクトコードコンピュータプログラムに変換するコンパイルデバイス１００である。コンパイルデバイスは、ソースコードコンピュータプログラムを解析（１２０）し、ソースコードコンピュータプログラムの少なくとも一部について、静的単一代入（ＳＳＡ）グラフ１２２を生成し、ＳＳＡグラフの第２の部分グラフＰを探索し、ＳＳＡグラフの第２の部分グラフを、オブジェクトコードコンピュータプログラムに、単一の演算として実装させ、これにより、第１の部分グラフの辺に対応する代入を省略するプロセッサ回路を含む。第１の部分グラフＮは、第２の部分グラフの部分グラフであり（Ｎ⊆Ｐ）、第２の部分グラフの流入辺に関連付けられるビットサイズの合計は、第１のグラフの流入辺に関連付けられるビットサイズの合計よりも小さい。
2020503623.tif 000002
【特許請求の範囲】
【請求項１】
ソースコードコンピュータプログラムをオブジェクトコードコンピュータプログラムに変換するコンパイルデバイスであって、
ソースコードコンピュータプログラムを受信する入力部と、
前記ソースコードコンピュータプログラムを解析し、前記ソースコードコンピュータプログラムの少なくとも一部について、静的単一代入（ＳＳＡ）グラフを生成するプロセッサ回路と、
を含み、
前記ＳＳＡグラフの頂点が、演算に対応し、前記ＳＳＡの辺が、対応するビットサイズを有する代入に対応し、
前記入力部は更に、前記ＳＳＡグラフの空ではない第１の部分グラフの指示を受信し、
前記指示は、前記ソースコードコンピュータプログラムの１つ以上の変数及び／又は代入を含み、
前記プロセッサ回路は更に、
前記ＳＳＡグラフの第２の部分グラフを探索し、
前記ＳＳＡグラフの前記第２の部分グラフを、前記オブジェクトコードコンピュータプログラムに、単一の演算として実装させて、これにより、前記第１の部分グラフの辺に対応する代入を省略し、
前記第１の部分グラフは、前記第２の部分グラフの部分グラフであり、前記第２の部分グラフの流入辺に関連付けられるビットサイズの合計が、前記第１の部分グラフの流入辺に関連付けられるビットサイズの合計よりも小さい、コンパイルデバイス。
【請求項２】
前記ＳＳＡグラフの前記第２の部分グラフは、前記オブジェクトコードコンピュータプログラムに、テーブル又はテーブルネットワークとして実装される、請求項１に記載のコンパイルデバイス。
【請求項３】
前記ＳＳＡグラフの前記第２の部分グラフは、前記オブジェクトコードコンピュータプログラムに、アフィン変換として実装される、請求項１に記載のコンパイルデバイス。
【請求項４】
前記ＳＳＡグラフ内の前記第２の部分グラフは、修正されていないＳＳＡグラフ内の第２の部分グラフによって示されているのと同じ演算を修正されたＳＳＡグラフ内に示す、前記修正されたＳＳＡグラフ内の単一の頂点に置換される、請求項１乃至３の何れか一項に記載のコンパイルデバイス。
【請求項５】
前記ＳＳＡグラフの第１の部分グラフの前記指示は、前記ＳＳＡグラフの１つ以上の辺の指示を含み、前記プロセッサ回路は、前記複数の指示された辺のうちの第１の辺と、指示された辺からなる前記ＳＳＡグラフ内のパスを介して前記第１の辺と連結する前記複数の指示された辺の全ての更なる辺とを選択する、請求項１乃至４の何れか一項に記載のコンパイルデバイス。
【請求項６】
前記ＳＳＡグラフの第１の部分グラフの前記指示は、前記ソースコードコンピュータプログラム内の変数の指示を含み、前記プロセッサ回路は、指示された前記変数への代入を、前記ＳＳＡグラフ内の辺として表し、表された前記辺は、前記ＳＳＡグラフの複数の辺の前記指示に含まれる、請求項５に記載のコンパイルデバイス。
【請求項７】
前記ＳＳＡグラフの第１の部分グラフの前記指示は、前記ソースコードコンピュータプログラムの一部の指示を含み、前記プロセッサ回路は、前記ソースコードコンピュータプログラムの指示された前記一部における代入を、開始辺、中間辺及び終了辺を含むパスとして表し、前記開始辺及び前記終了辺は、前記複数の指示された辺に含まれ、前記中間辺は前記複数の指示された辺に含まれない、請求項６に記載のコンパイルデバイス。
【請求項８】
前記テーブル又は前記テーブルネットワークは、符号化データに作用する、請求項２に従属する請求項７に記載のコンパイルデバイス。
【請求項９】
前記プロセッサ回路は、前記第１の部分グラフの複数のスーパーグラフにわたって反復し、前記複数のスーパーグラフから、前記第２の部分グラフの流入辺に関連付けられるビットサイズの最小合計を有するスーパーグラフを前記第２の部分グラフとして選択するか、又は、前記最小合計が前記第１の部分グラフの流入辺に関連付けられるビットサイズの前記合計よりも大きい場合、前記第１の部分グラフと等しい前記第２の部分グラフを選択する、請求項１乃至８の何れか一項に記載のコンパイルデバイス。
【請求項１０】
前記プロセッサ回路は、前記ＳＳＡグラフ又はその派生物に最小カットアルゴリズムを適用して、前記第２の部分グラフを得る、請求項１乃至９の何れか一項に記載のコンパイルデバイス。
【請求項１１】
前記プロセッサ回路は、
前記ＳＳＡグラフから派生グラフを生成し、
前記派生グラフに最小カットアルゴリズムを適用して、前記派生グラフの２つの部分グラフへの分割を得て、
前記派生グラフは、
前記第１の部分グラフの流入辺を含む有向パスを介して前記第１の部分グラフに連結される前記ＳＳＡグラフ内の前記頂点及び前記辺と、
前記ＳＳＡグラフ内の流入辺を持たない頂点に、無限大のビットサイズの辺で連結されるソース頂点と、
前記第１の部分グラフの前記頂点の少なくとも一部と、
前記第１の部分グラフ内の前記頂点のうちの少なくとも１つの頂点に、無限大のビットサイズの辺で連結されるシンク頂点と、
を含み、
前記２つの部分グラフのうちの第１の部分グラフは、前記ソース頂点を含み、前記２つの部分グラフのうちの第２の部分グラフは、前記シンク頂点を含み、
前記ＳＳＡグラフ内の前記第２の部分グラフを、前記第２の分割内の前記頂点に対応する部分グラフとして得る、請求項１乃至１０の何れか一項に記載のコンパイルデバイス。
【請求項１２】
前記ＳＳＡグラフからの前記派生グラフは、前記第１の部分グラフの辺を含まず、前記シンクは、前記第１の部分グラフの全ての頂点に、無限大のビットサイズの辺で連結されるか、又は、
前記ＳＳＡグラフからの前記派生グラフは、前記第１の部分グラフの辺を含み、前記辺のビットサイズは、無限大に設定されている、請求項１１に記載のコンパイルデバイス。
【請求項１３】
記ＳＳＡグラフの更なる部分グラフの更なる指示を受信し、前記プロセッサ回路は更に、前記第２の部分グラフを探索する前に、前記更なる部分グラフ内の辺のビットサイズを無限大に設定する、請求項１乃至１２の何れか一項に記載のコンパイルデバイス。
【請求項１４】
ソースコードコンピュータプログラムをオブジェクトコードコンピュータプログラムに変換するコンパイル方法であって、
ソースコードコンピュータプログラムを受信するステップと、
前記ソースコードコンピュータを解析するステップと、
前記ソースコードコンピュータプログラムの少なくとも一部について、静的単一代入（ＳＳＡ）グラフを生成するステップと、
前記ＳＳＡグラフの空でない第１の部分グラフの指示を受信するステップと、
前記ＳＳＡグラフの第２の部分グラフを探索するステップと、
前記ＳＳＡグラフの前記第２の部分グラフを、前記オブジェクトコードコンピュータプログラムに、単一の演算として実装させて、前記第１の部分グラフの辺に対応する代入を省略するステップと、
を含み、
前記ＳＳＡグラフの頂点が、演算に対応し、前記ＳＳＡの辺が、対応するビットサイズを有する代入に対応し、
前記指示は、前記ソースコードコンピュータプログラムの１つ以上の変数及び／又は代入を含み、
前記第１の部分グラフは、前記第２の部分グラフの部分グラフであり、前記第２の部分グラフの流入辺に関連付けられるビットサイズの合計が、前記第１の部分グラフの流入辺に関連付けられるビットサイズの合計よりも小さい、方法。
【請求項１５】
プロセッサシステムに請求項１４に記載の方法を行わせる命令を表す一時的又は非一時的データを含む、コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイルデバイス、コンパイル方法及びコンピュータ可読媒体に関する。
【背景技術】
【０００２】
プログラムの実行中に、一部のランタイムデータが見えないようにすることが望ましい場合がある。例えば機密データを処理するコンピュータプログラムでは、機密データがメモリ内でそのままで処理されるのを避けることが好ましい場合がある。例えば機密データは、例えば金融又はマルチメディアアプリケーションで使用される秘密鍵を含む。例えばブロック暗号又はキー付きＭＡＣの実装では、キー値をそのまま使用することは避けようとされるであろう。データを非表示にする他の理由としては、プロプライエタリアルゴリズムの詳細を非表示にすることが挙げられる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
この問題に対して様々な解決策が考案されてきている。１つの手法は、機密情報を含む変数をマスキングすることである。このような手法の１つは、Andreas Hoheiselによる「Side-Channel Analysis Resistant Implementation of AES on Automotive Processors」に詳述されている。しかし、マスキングには欠点がある。例えばマスキングを行っても暗号化形式のデータは依然として利用可能なままである。更に、マスクは、多くの場合、データを計算ユニットに提供する前に、除去されなければならない。これは、例えばマスキングが行われたやり方と互換性がない演算がマスキングデータに行われる場合に必要となる。ブロック暗号の場合では、いわゆるＳボックスがこの点で問題がある。
【０００４】
もう１つの手法は、ホワイトボックス暗号化を使用することである。ホワイトボックス暗号化では、例えば場合によってはソルトを伴った符号化データに全単射関数を適用することによって、全ての演算が符号化データ上で行われる。この場合、コンピュータプログラムは、符号化データに作用するテーブルネットワークとして表される。このような実装例は、S. Chow他による「White-Box Cryptography and an AES Implementation」に記載されている。ホワイトボックス暗号化は、一般に、マスキングよりも高水準の保護を提供するが、この方法にも欠点がある。１つの特有の問題は、ホワイトボックス暗号化が、しばしば、コンピュータプログラムの設計者のかなりの関与を必要とすることである。例えばＡＥＳホワイトボックスの場合、プログラムのどの部分がテーブルによって最もよく表されるかを人間の設計者が慎重に選択している。
【課題を解決するための手段】
【０００５】
これらの懸念に対処するコンパイルデバイスが提示されている。このコンパイルデバイスは、プログラマが、プログラムのどの部分を実行中に非表示にするべきかを簡単に示すことを可能にする。このコンパイルデバイスは、ＳＳＡグラフを使用してプログラムを解析し、所望の部分を非表示にしながら効率的に実装することができる部分を見つける。これは、プログラマ側の労力をかなり必要とせずにホワイトボックス実装を作成するために使用される。本発明者らは、非表示のままであるべきＳＳＡグラフ内の部分グラフの直接置換が、効率的な解決策にならないことが多いことに気が付いた。コンパイルデバイスの用途には、サイドチャネル攻撃、メモリスクレイピングとしても知られるキースクレイピング及びホワイトボックス攻撃に対する保護が含まれる。例えばメモリスクレイピング攻撃では、デジタルデバイスのメモリがスキャンされて、暗号鍵、例えばＤＲＭ保護メディアプレーヤで使用される鍵が探される。
【０００６】
一実施形態では、最小カットアルゴリズムを使用して、入力サイズが小さいＳＳＡグラフの一部が見つけられ、したがって、メモリの効率的な実装につながる。
【０００７】
本発明による方法は、コンピュータ実装方法としてコンピュータ上に、専用ハードウェア又はその両方の組合せで実装することができる。本発明による方法の実行可能コードは、コンピュータプログラムプロダクトに格納することができる。コンピュータプログラムプロダクトの例としては、メモリデバイス、光記憶装置、集積回路、サーバ、オンラインソフトウェア等が挙げられる。好適には、コンピュータプログラムプロダクトは、コンピュータ可読媒体に格納され、当該コンピュータプログラムプロダクトがコンピュータ上で実行されるときに本発明による方法を行う非一時的プログラムコードを含む。
【０００８】
好適な実施形態では、コンピュータプログラムは、当該コンピュータプログラムがコンピュータ上で実行されるときに本発明による方法の全てのステップを行うように適応されたコンピュータプログラムコードを含む。好適には、コンピュータプログラムは、コンピュータ可読媒体上に具現化される。
【０００９】
本発明の別の態様は、コンピュータプログラムをダウンロードのために利用可能にする方法を提供する。この態様は、コンピュータプログラムが、例えばアップル社のＡｐｐ  Ｓｔｏｒｅ、グーグル社のＰｌａｙ  Ｓｔｏｒｅ又はマイクロソフト社のＷｉｎｄｏｗｓ  Ｓｔｏｒｅにアップロードされるとき、及び、コンピュータプログラムがそのようなストアからダウンロードのために利用可能であるときに使用される。
【００１０】
Bayrak Ali Galip他による「Automatic Application of Power Analysis Countermeasures」を参照されたい。Giovanni Agosta他による「The MEET Approach: Securing Cryptographic Embedded Software Against Side Channel Attacks」を参照されたい。
【図面の簡単な説明】
【００１１】
本発明の更なる詳細、態様及び実施形態を、図面を参照して、ほんの一例として説明する。図中の要素は、単純さ及び明確さのために示されており、必ずしも縮尺通りではない。図において、既に説明された要素に対応する要素は、同じ参照符号を有することがある。
【００１２】
【図１ａ】図１ａは、コンパイルデバイスの一実施形態の一例を概略的に示す。
【図１ｂ】図１ｂは、探索ユニットの一実施形態の一例を概略的に示す。
【図２ａ】図２ａは、プログラム断片の一実施形態の一例を概略的に示す。
【図２ｂ】図２ｂは、ＳＳＡグラフの一実施形態の一例を概略的に示す。
【図２ｃ】図２ｃは、ＳＳＡグラフ内の辺を指示する一実施形態の例を概略的に示す。
【図２ｄ】図２ｄは、ＳＳＡグラフ内の辺の一実施形態の一例を概略的に示す。
【図２ｅ】図２ｅは、ＳＳＡグラフ内の修正辺の一実施形態の一例を概略的に示す。
【図３ａ】図３ａは、ＳＳＡグラフの一実施形態の一例を概略的に示す。
【図３ｂ】図３ｂは、修正ＳＳＡグラフの一実施形態の一例を概略的に示す。
【図４ａ】図４ａは、プログラム断片の一実施形態の一例を概略的に示す。
【図４ｂ】図４ｂは、ＳＳＡグラフの一実施形態の一例を概略的に示す。
【図４ｃ】図４ｃは、修正ＳＳＡグラフの一実施形態の一例を概略的に示す。
【図５ａ】図５ａは、ＳＳＡグラフの一実施形態の一例を概略的に示す。
【図５ｂ】図５ｂは、派生グラフの一実施形態の一例を概略的に示す。
【図５ｃ】図５ｃは、派生グラフの一実施形態の一例を概略的に示す。
【図５ｄ】図５ｄは、最小カット解の一実施形態の一例を概略的に示す。
【図５ｅ】図５ｅは、修正ＳＳＡグラフの一実施形態の一例を概略的に示す。
【図６】図６は、コンパイル方法の一実施形態の一例を概略的に示す。
【図７ａ】図７ａは、一実施形態によるコンピュータプログラムを含む書き込み可能部分を有するコンピュータ可読媒体を概略的に示す。
【図７ｂ】図７ｂは、一実施形態によるプロセッサシステムの概略図を概略的に示す。
【発明を実施するための形態】
【００１３】
図１ａ乃至図５ｅにおける参照符号のリスト
１００  コンパイルデバイス
１０２  ソースコードコンピュータプログラム
１０４  ＳＳＡグラフの第１の部分グラフ（Ｎ）の指示
１０６  オブジェクトコードコンピュータプログラム
１１０  入力部
１２０  パーサ
１２２  第１の静的単一代入（ＳＳＡ）グラフ
１３０  探索ユニット
１３２  第２のグラフセレクタ
１３３  ＳＳＡグラフモディファイア
１３４  制御フロー
１３６  第２のＳＳＡグラフ
１３７  置換された第２の部分グラフの実装に関する情報
１４０  コード生成器
２００  探索ユニット
２１０  派生ＳＳＡグラフ生成器
２２０  最小カットソルバー
２３０  ＳＳＡグラフモディファイア
３１０  分配ノード
３２０、３３０  頂点
３２０’、３３０’  頂点
３２２、３２４  頂点
５０１〜５１６  頂点
５２０  ソース
５３０  シンク
５４０  追加された頂点
５７０  最小カット解
【００１４】
本発明は、多くの異なる形態の実施形態が可能であるが、本開示が本発明の原理の例示であると見なされ、本発明を図示され説明される特定の実施形態に限定することを意図していないという理解と共に、１つ以上の特定の実施形態が図面に示され、これらを詳細に説明する。
【００１５】
以下では、理解のために、実施形態の要素を動作中にあるものとして説明する。しかし、各要素は、当該要素によって行われるものとして説明されている機能を行うように構成されていることは明らかであろう。
【００１６】
更に、本発明は、実施形態に限定されず、本発明は、本明細書に説明されている又は相互に異なる従属請求項に記載される個々の新規な特徴又は特徴の任意の組み合わせにある。
【００１７】
上述したように、プログラム内で中間値（中間データとも呼ばれる）を非表示とすることが望ましい場合が多い。本発明は、このような非表示値の明示的な計算を完全に回避することを目的としたコンパイラを提供する。コンパイル方法の実施形態を、コンパイラのパスで実装することができる。データが実行から消えるので、実施形態は、ランタイムデータを自動的に真に非表示にすると言うことができる。
【００１８】
図１ａは、コンパイルデバイス１００の一実施形態の一例を概略的に示す。コンパイルデバイス１００は、ソースコードコンピュータプログラム１０２をオブジェクトコードコンピュータプログラム１０６に変換する。コンパイルデバイス１００は、ソースコードコンピュータプログラム１０２を受信する入力部１１０を含む。図１ａは、コンパイルデバイスの１つの可能なアーキテクチャ及び／又は機能組織を様々なユニットで示す。これらのユニットは、例えば専用回路であるハードウェア実装としてのプロセッサ回路（図１ａには個別に示していない）及び／又はこれらの間のハイブリッドによって実装されてよい。
【００１９】
ソースコード１０２は、Ｃ、Ｃ＃、Ｃ＋＋、Ｏｂｊｅｃｔｉｖｅ−Ｃ、Ｆｏｒｔｒａｎ、Ｐａｓｃａｌ、（コンパイラ型）Ｂａｓｉｃ、Ｊａｖａ（登録商標）等といった高級コンピュータプログラム言語で書かれている。オブジェクトコード１０６は、コンピュータ言語、通常は機械語言語（即ち、バイナリ）、又は、レジスタ転送言語（ＲＴＬ）といった中間言語の一連のステートメント又は命令を含む。次に、オブジェクトファイルをリンクして実行可能ファイル又はライブラリファイルを作成することができる。実行可能ファイル又はライブラリファイル等内でリンクされて配置されている機械語言語のオブジェクトコードは、特定の機械語言語に合わせて構成されたコンピュータによって実行することができる。機械語言語の例としては、８０３８６、ＡＲＭ、Ｍｉｐｓ機械語言語等が挙げられる。
【００２０】
オブジェクトコードは、完成したプログラムの機械語には見られない、様々なオブジェクトコード及び／又はデータを一緒に連結するためにリンカが使用するプレースホルダ又はオフセットを含むことができる。機械語は、ＣＰＵによって直接実行されることができるバイナリコードであるが、オブジェクトコードは、リンカがそれらを埋めることができるように部分的にパラメータ化されたジャンプ等を有することができる。一実施形態では、コンパイルデバイス１００は、実行する準備ができている、例えば既に完全にリンクされているオブジェクトコードを生成する。
【００２１】
コンパイラデバイス１００は、パーサ１２０を含む。パーサ１２０は、ソースコード１０２を受信し、ソースコード１０２が書かれている高次レベルの構文に従ってソースコード１０２を解析する。
【００２２】
パーサ１２０は、入力されたソースコード１０２の構文解析を行う。パーサ１２０は、ソースコードコンピュータプログラムの少なくとも一部について、静的単一代入（ＳＳＡ）グラフ１２２を生成する。
【００２３】
例えばＳＳＡグラフ１２２は、いわゆる基本ブロック、例えば分岐を含まないソースコード１０２の一部について生成される。一実施形態では、基本ブロックは、条件付き代入を有することが許可される。一実施形態では、ソースコード１０２内の１つ以上のループが、コンパイルデバイス１００（例えばパーサ１２０）によってアンロールされて、基本ブロックが拡大される。アンロールするループは、例えば従来のヒューリスティックを使用して、コンパイルデバイス１００によって特定される。或いは、アンロールするループは、例えばアンロールするループを特定するためにソースコード１０２内に特別な識別子を使用して、プログラマによって示されてもよい。例えば一実施形態では、暗号演算におけるメインループがアンロールされてもよい。例えば実行するラウンドを示すループが、例えばＡＥＳ、ＤＥＳ等であるブロック暗号、例えばＨＭＡＣであるＭＡＣ、例えばＲＳＡといった公開−秘密鍵暗号システム用の指数関数といった暗号プリミティブにおいてアンロールされてもよい。これは、ＳＳＡグラフ１２２のサイズ、したがって、最適化の範囲を大幅に拡大するという利点を有する。コンパイルデバイスはまた、非キー付き暗号関数、例えばＳＨＡ‐１といったハッシュ関数にも適用されてよい。
【００２４】
パーサ１２０は、ＳＳＡグラフ１２２の他に、様々な他のデータ構造、例えば解析木、抽象構文木及びソースコード入力の構造表現を示す他の階層構造を作成することができる。このような追加構造は、それ自体が当技術分野で知られているように、コード生成を助けることができる。ＳＳＡグラフ以外の構造及びコード生成の詳細は、従来の技法を使用して行うことができるので、本明細書ではそれほど詳細には説明しない。
【００２５】
ＳＳＡグラフ、特にＳＳＡグラフ１２２は、ソースコード１０２の中間形式を表す一種のデータフローグラフである。ＳＳＡグラフは、有向非巡回グラフである。ＳＳＡグラフの頂点（ノードとも呼ばれる）は演算を表す。ＳＳＡグラフの辺は、レジスタ（例えば仮想レジスタを含む）又はメモリ（例えばメモリの選択された部分）といったデータホルダを表す。特別なノードがデータフローグラフの引数及び結果を表すと仮定する。図２ａは、例示的なプログラム断片を示し、図２ｂは、対応するＳＳＡグラフを示す。図２ｂでは、特別なノードは、正方形のボックスとして示し、通常のノードは、楕円形又は点として示す。
【００２６】
ＳＳＡグラフ内の辺は、多重辺であってよい。多重辺は１つの頂点を１つ以上の頂点に連結する。ＳＳＡグラフは、多重辺の代わりに（又はそれに加えて）、到来値を複数のノードに分配する分配ノードを含んでもよい。図２ｂは、２つのそのような分配ノード３１０を示す。なお、本明細書に図示されるＳＳＡグラフは、コンパイルデバイス１００の電子メモリ内のデータ構造として表すことができる。
【００２７】
ＳＳＡグラフの辺には、対応するデータ値のビットサイズが示されている。これは、このデータに割り当てなければならないビットサイズである。典型的なビットサイズは、ニブル、バイト、ワード及びダブルワードの４、８、１６、３２等である。ビットサイズはまた、例えば２進フラグ又は４つの可能な値を有する小構造をそれぞれ示すために、例えば１又は２であってもよい。図２ｂでは、ビットサイズが辺に示されている。図２ｂにおける辺はまた、それらが対応するプログラム内のデータホルダも示している。一実施形態では、全てのビットサイズは少なくとも１である。
【００２８】
図１ａに戻る。入力部１１０は更に、ＳＳＡグラフ１２２の第１の部分グラフＮの指示１０４を受信する。第１の部分グラフＮは、ＳＳＡグラフ１２２の連結部分グラフである。第１の部分グラフは空グラフではない。例えば第１の部分グラフは、ＳＳＡグラフ１２２の少なくとも１つの頂点を含む。しかし、一実施形態では、第１の部分グラフが少なくとも２つの頂点と当該２つの頂点間に延在する辺とを含むことが必要である。第１の部分グラフは、中間値がプログラム内で明示的に表されない（非表示にされるとも言う）ことが望ましいＳＳＡグラフ１２２の一部を表す。第１の部分グラフだけでなく、複数の部分グラフが指示されてもよい。コンパイルデバイスは、複数の指示された部分グラフから第１の部分グラフ（例えば最初の部分グラフ又はランダムな部分グラフ等）を選択することができる。複数の部分グラフは、それらの複数の辺を指示することによって指示することができる。
【００２９】
第１の部分グラフの指示のやり方は幾つかある。例えば一実施形態では、ＳＳＡグラフ１２２の辺が指示される。コンパイルデバイス１００は、非表示辺のみからなる道を介して連結されている全ての辺を収集する。つまり、コンパイラデバイス１００は、非表示辺だけからなる連結部分グラフを特定する。このような部分グラフは、１つしかない場合も、もっと多くある場合もある。後者の場合、アルゴリズムを各部分グラフに反復することができる。後述する図５ａに、非表示辺が破線の辺として示されているＳＳＡグラフが図示される。３つの辺は共に第１の非表示部分グラフを形成する。指示された辺に連結されている頂点もまた、指示されたと見なすことができる。
【００３０】
例えば一実施形態では、ＳＳＡグラフの第１の部分グラフ（Ｎ）の指示は、ＳＳＡグラフの１つ以上の辺の指示を含む。例えばソースコードでは、例えばプログラマによって、ある代入に、当該代入が非表示であることを示すラベルが付けられてよい。例えばこのような代入は、「ｘ＝＃ｈｉｄｄｅｎ３＊ｙ」のような形式で、演算３＊ｙの結果が非表示に代入されるべきであることが示される。この代入に対応するＳＳＡグラフ１２２内の辺は、非表示とラベルを付けられてよい。例えばＳＳＡグラフを表すデータ構造では、フィールドが、辺は指示されている又は指示されていない（非表示）ことを表してもよい。
【００３１】
第１の部分グラフＮの指示の別のやり方は、ソースコードコンピュータプログラム１０２内の変数を指示することによる。例えば変数が宣言されると、当該変数はラベル付けされる。この場合、ラベル付けはまた、キーワードを、この場合は変数に添付することによって行うことができる。興味深いことに、変数を、例えば宣言後に指示する、例えばラベル付けすることができる。更に、変数の指示後、当該変数は、例えば更なるラベルによって指示解除されてもよい。図２ｃは、変数を非表示にする２つの例を示す。１番目の例では、変数は、非表示と宣言されている。即ち、指示されている。２番目の例では、変数は、正規変数として宣言され、後に、非表示とラベル付けされる。例２では、変数は、後に非表示解除（非表示ではない）として宣言されている。変数の非表示解除はオプションである。プロセッサ回路は、指示された変数への代入をＳＳＡグラフ内の辺として表し、これらの辺に非表示とラベル付けする。例えばこれはパーサ１２０によって行われてもよい。図２ｃの例１では、ｘへの代入全てが、指示された辺をもたらす。例２では、ｘ＝ａ＋ｂにおけるｘへの代入だけが、指示された辺をもたらす。ただし、ＨＩＤＤＥＮステートメントとＵＮＨＩＤＤＥＮステートメントとの間の他の代入は、指示された辺をもたらさない。一実施形態では、セキュリティ支援プログラミング言語が、例えば従来のプログラミング言語の拡張として定義される。この言語では、変数宣言に追加されて、その変数に格納された値が計算中に観測されるべきでないことを示すキーワードＨＩＤＤＥＮがある。セキュリティ支援プログラミング言語で書かれたソースコードプログラムは、コンパイルデバイス１００によってデータフローグラフに変換される。非表示変数は、データフローグラフ内の幾つかの辺に変換される。したがって、ＨＩＤＤＥＮとマーク付けされた変数は、非表示とラベル付けされた複数の辺を生じさせる。図２ｃの例３は、ＳＳＡグラフ内の辺の指示の更に別のやり方を示す。ソースコード１０２の一部が、ＨＩＤＤＥＮステートメント及びＵＮＨＩＤＤＥＮステートメントで示される。一実施形態では、ソースコードのこの部分の全ての代入を非表示とマークすることができる。しかし、これは手に負えないほど大きい第１の部分グラフをもたらす場合がある。図２ｄ及び図２ｅを参照して、改良されたやり方を示す。
【００３２】
図２ｄには、図２ｃの例３に対応するＳＳＡグラフの１つの辺が示されている。例えばノード３２０は、演算ｘ＝ａ＋ｂを表し、これは、変数ｘへのｎビット幅の代入をもたらす。この代入は、指示されているソースコード１０２の一部において行われるので、辺は、図２ｅに示されるように修正される。図２ｄにおける単一の辺は、２つの追加のノード３２２及び３２４を有するパスに置換される。図２ｅのノード３２０’及び３３０’は、ノード３２０及び３３０に対応するが、図２ｄの結合辺が図２ｅのパスと置換されているという点で修正されている。この場合、図２ｅのパスは、３つの辺、即ち、ノード３２０’からノード３２２への第１の辺、ノード３２２からノード３２４への第２の辺及びノード３２４からノード３３０’への第３の辺を含む。この場合、第２の辺が中間辺である。第１の辺及び第３の辺はまた、それぞれ、開始辺及び終了辺とも呼ばれる。
【００３３】
第１の辺（又は開始辺）及び第３の辺（又は終了辺）は、複数の指示された辺に含まれるが、第２の辺（中間辺）は、複数の指示された辺には含まれない。ＳＳＡグラフ用のコードが生成されるとき、非表示辺は、１つ以上の非表示辺を含む第２の部分グラフを表すルックアップテーブルとして実装することができる。パスには非表示ではない辺が含まれているため、ＳＳＡグラフは分割され、ＳＳＡグラフ全体又はその大部分が、単一の非表示部分グラフにならないようにされる。非表示グラフが大きすぎると、テーブルが大きくなりすぎる場合がある。パスは３辺より長くてもよい。例えばパスの方向に沿って見たときに、開始辺、中間辺及び終了辺をこの順序で含む有向パスが使用されてよい。興味深いことに、非表示開始辺及び終了辺が、非表示ではない中間辺と共に使用されるので、変数は、符号化変数として実装することができる。最適化された第２の部分グラフにより、これは、最適化されたサイズの符号化入力を使用する。これは、ソースコード１０２の大部分が非表示とラベル付けされることを可能にし、そうでなければ、大きすぎる第１の部分グラフをもたらしてしまう場合がある。例えば一実施形態では、これは、ＨＭＡＣアルゴリズムをループアンロールする実装全体にうまく適用されている。
【００３４】
例えばノード３２２を符号化演算と考え、ノード３２４を復号化演算と考えることができる。このようにすると、変数は、例えば符号化前の非表示辺（辺３２０’−３２２）若しくは復号化後の非表示辺（辺３２４−３３０’）と表されるか、又は、当該変数は可視であるが符号化される（辺３２２−３２４）。これにより、テーブルベースの算術演算を使用して多数の変数を符号化し、非常に大きいテーブルになることを自動的に回避する洗練されたやり方が可能になる。符号化演算及び復号化演算は、他の演算がＳＳＡグラフ内のノードに関連付けられるのと同様に、辺３２２及び辺３２４に関連付けられてよい。コンパイラデバイスが、非表示部分グラフをテーブルに置換すると、符号化演算及び復号化演算は、テーブルに自動的に組み入れられる。この実施形態の場合、テーブル又はテーブルネットワークは、第２の部分グラフによって表される演算を置換する適切な手段である。
【００３５】
符号化入力は、変数の第２の全単射変換を使用することによって達成することができる。符号化を更に向上させるために、全単射を、変数と、状態とも呼ばれるソルトとに適用することができる。なお、非表示部分グラフを置換するテーブルが符号化変数に作用することは、通常、不要である。非表示辺が、代わりに削除されており、通常、符号化変数に作用する必要はない。場合によっては、例えば符号化変数に作用する図２ｄ及び図２ｅの最適化を、大きすぎるテーブルが作成されないようにするための妥協策として使用することができる。ホワイトボックスコンテキストでの符号化／復号化演算は、暗号化／復号化と呼ばれる場合もある。
【００３６】
図１ａに戻る。コンパイルデバイスは更に、探索ユニット１３０を含む。探索ユニット１３０は、ＳＳＡグラフの第２の部分グラフ（Ｐ）を探索する。第１の部分グラフ（Ｎ）は、第２の部分グラフの部分グラフである（Ｎ⊆Ｐ）。探索ユニット１３０は、第２部分グラフの流入辺に関連付けられるビットサイズの合計が、第１のグラフの流入辺に関連付けられるビットサイズの合計よりも小さい部分グラフを探索する。
【００３７】
例えば探索ユニット１３０は、例えば第２のグラフセレクタ１３２によって、第１の部分グラフＮを拡張する複数の部分グラフを連続的に又は並列に構築する。探索ユニット１３０は、次に、構築された部分グラフの流入辺に関連付けられるビットサイズの合計を計算することができる。要件を満たす部分グラフが見つかると、当該部分グラフを第２の部分グラフと見なすことができる。一実施形態では、探索ユニット１３０は、最初に、第１の部分グラフの祖先グラフ、例えば第１の部分グラフに連結可能である全てのノード及び辺を含み、第１の部分グラフに向かう有向パスを有するグラフを構築する。Ｎよりも大きい部分グラフの構築は、祖先グラフ内のＮの外側のノードを選択することによって行うことができる。
【００３８】
例えば一実施形態では、コンパイルデバイスは、第１の部分グラフの複数のスーパーグラフにわたって反復する。第１の部分グラフのスーパーグラフは、第１の部分グラフを含むＳＳＡグラフの部分グラフである。コンパイルデバイスは、複数のスーパーグラフのうちの、第２の部分グラフの流入辺に関連付けられるビットサイズのより小さい、好適には最小合計を有する１つのスーパーグラフを第２の部分グラフとして選択するか、又は、上記合計が第１のグラフの流入辺に関連付けられるビットサイズの合計よりも大きい場合、第１の部分グラフに等しい第２の部分グラフを選択する。より単純な状況では、この探索ユニット１３０は、すでに有効結果を出していてもよい。しかし、以下に、特に大きなＳＳＡグラフに対して、より良い結果を出す優れたアルゴリズムを説明する。なお、非表示入力辺を有するスーパーグラフは回避される。これは、ハードコード化されるか、又は、当該辺のビットサイズを無限大に設定することによって達成されてよい。
【００３９】
第２の部分グラフＰが見つかると、探索ユニット１３０は、ＳＳＡグラフ内の第２の部分グラフ（Ｐ）を修正ＳＳＡグラフ内の単一の頂点に置換する。この単一頂点は、修正されていないＳＳＡグラフ内の第２の部分グラフ（Ｐ）によって示されるのと同じ演算を修正ＳＳＡグラフ内に示す。つまり、新しい修正ＳＳＡグラフは同じ結果を生成するが、ＳＳＡグラフの一部は単一の演算に置換されている。第１の部分グラフＮ内で非表示と示されていた辺が部分グラフＰに含まれているので、これらの辺は、単一の演算として実行されることにより事実上非表示となる。例えばこの演算は、ＳＳＡグラフモディファイア１３３によって行われてよい。上記単一の頂点は、第２の部分グラフＰと同じ流入辺及び流出辺を有する単一の頂点であってよい。なお、この構築では、辺は縮約してもよい。例えばＰがＰの外側の同じ頂点から２つの異なる流入辺を受け取る場合、これらの２つの流入辺は、Ｐの外側の頂点からＰを置換する単一の頂点までの単一の辺に縮約する。このような辺は、流入辺のビットサイズ合計を計算するために一度しか足されない。
【００４０】
第２の部分グラフＰは、第１の部分グラフＮと同じ出力を生成するが、入力幅は小さい。第２の部分グラフＰは、第１の部分グラフＮが生成した出力よりも多くの出力を生成することも可能である。これは、複数の出力を持つ演算子を分割し、他の出力をグラフの一部に残すことによって常に解決することができる。これは、図３ａ及び図３ｂに示されている。図３ａでは、頂点ｅだけを含むノード集合を、複素演算子、例えばテーブルと置換することが望まれている。この場合、第２の部分グラフが、頂点ｄ及びｅによって形成され、また、わずか６の入力幅を有する。ただし、この集合は、ｄからｆへの追加の出力がある。これは、グラフのｄからｆまでの計算部分を残して、演算子を分割することで解決することができる。図３ｂにこの解決策が示されている。新しい単一演算子、例えば複素演算子Ｔが集合｛ｄ、ｅ｝を置換する一方で、ｄからｆへの計算はグラフに残されている。
【００４１】
この手順を実装する効果的なやり方は、（必要に応じて縮約辺を有する）第２の部分グラフＰと同じ流入辺及び流出辺を有する単一の頂点を追加し、第１の部分グラフの元の流出辺のみを取り除くことによって、例えばＳＳＡグラフ１２２から新しいＳＳＡグラフを作成することである。次に、デッドコード除去アルゴリズムを新しいＳＳＡグラフに実行する。第１の部分グラフＮの流出辺はないので、Ｎの全ての非表示辺が除去される。興味深いことに、第１の部分グラフに関連していない流出辺を回避するためにＰの一部を複製する必要がある場合、これは、したがって、自動的に行われる。Ｎにのみ必要であったＰの部分が除去される。
【００４２】
つまり、データフローグラフは、非表示辺の評価が少なくて済む、意味的に等価なデータフローグラフに変換される。一実施形態では、コンパイルデバイスは、第２の部分グラフＰが見つからない場合、エラーメッセージを生成することができる。
【００４３】
ＳＳＡグラフ内の辺を指示する上記方法は、通常、複数の非連結部分グラフを形成する。１つの部分グラフの中で、全ての辺が非表示辺である。第２の部分グラフを見つけ、それを単一ノードに置換することによって、部分グラフのうちの１つが第１の部分グラフとして置換されると、非表示辺の数が低減される。ただし、１つ以上の非表示部分グラフが残っている場合がある。これは、修正ＳＳＡグラフにわたってアルゴリズムを再開することによって解決することができる。各反復において、非表示辺は、非表示辺がなくなる時点まで、又は、残っている辺について、適切な第２の部分グラフが見つけられなくなるまで、除去することができる。図１ａは、アルゴリズムを修正ＳＳＡグラフに再適用することができる制御フロー１３４を示す。
【００４４】
図１ａでは、探索ユニット１３０は、少なくとも２つの結果、即ち、少なくとも１つの第２の部分グラフ（第１の部分グラフのスーパーグラフ）が単一の頂点に置換されている第２のＳＳＡグラフ１３６と、置換された第２の部分グラフの実装に関する情報１３７とを生成する。例えば一実施形態では、情報１３７は、置換された部分を実装する１つ以上のテーブルである。
【００４５】
第２の部分グラフＰは、第２の部分グラフＰ全体と同じ入力を有する単一の複素演算子に置換される。このような複素演算子を実装するやり方は多くあり、選択された実装に関する情報は、情報１３７に含まれる。例えば一実施形態では、複素演算子は、テーブル（例えばルックアップテーブル）又はテーブルネットワークとして実装される。演算を表すためにテーブルを使用すること自体は、ホワイトボックス暗号化から知られている。しかし、コンパイルデバイスは、テーブル又はテーブルネットワークとしての実装に適した有利な候補を選択するための自動的な方法を与える。テーブルは、１つ以上の入力を受け取り、受け取った入力をテーブル内で調べることによって、１つ以上の出力を生成する。例えばテーブルは、全ての可能な入力についてＰを評価し、結果を表にまとめることによって、Ｐを置換するように生成される。テーブルネットワークは、複数のテーブルを含み、そのうちの幾つかのテーブルは、１つ以上の入力のうちの１つの入力を受け取り、幾つかのテーブルは、１つ以上の出力のうちの１つの出力を生成する。テーブルネットワークのうちの幾つかのテーブルは、代わりに又は追加的に、テーブルネットワークのうちの他のテーブルの出力を受け取ることができ、一方、幾つかのテーブルは、他のテーブルによって出力されないが、使用だけされる中間値を生成することができる。
【００４６】
テーブルの利点は、全ての演算を、テーブルとして理論的に表現できる点である。一方で、テーブルには、このような実装では実用的でないほど大きいテーブルが必要になる可能性があるという欠点がある。第２の部分グラフＰを実装する別の手法は、全部ではないが多くの第２の部分グラフを表すことができる十分に大きいクラスの演算子を選択することである。このようなクラスの一例は、アフィンベクトル変換である。アフィンベクトル変換は入力に適用され、非表示にされることを必要とした同じ中間結果を必要としないやり方で出力を生成することができる。アフィン変換が存在することの検証は、行列Ａ及びベクトルｂについて、式ｘ＝Ａｙ＋ｂを解くことによって行うことができる。ここで、ｘは、第２の部分グラフＰの１つ以上の出力を表し、ｙは、１つ以上の入力を表す。アフィン変換は、同じ演算を表す対応テーブルよりもはるかに小さいという利点がある。アフィン変換の一部が非表示変数と同じであるというリスクを回避するために、これをマスキングすることができる。例えばＡ＝Ａ１＋Ａ２及びｂ＝ｂ１＋ｂ２を選択し、ｘ＝（Ａ１ｙ＋ｂ１）＋（Ａ２ｙ＋ｂ２）を計算することができる。これは、ランダム成分を持つＡ１及びｂ１を選択し、そこからＡ２及びｂ２を計算することによって行うことができる。
【００４７】
したがって、Ｎの内部にある辺がもはや関連性がなくなるように演算が実装され、したがって、これらの辺のデータが事実上非表示となる。残念なことに、ルックアップテーブルは、時に、非常に多くの量のメモリを使用し、また、アフィンベクトル変換が常に存在するとは限らない。これらの場合、コンパイルデバイスは、どの部分グラフを非表示にできなかったかを示すフィードバックを与えることができる。このフィードバックに基づいて、人間のオペレータが、この問題を回避すべくソースコードの対応する部分を書き直すことができる。例えばオペレータは、妥協して、幾つかの代入について、非表示ステートメントを削除するか、又は、幾つかの変数を、完全に非表示にするのではなく、符号化変数に置換することを決定することができる。
【００４８】
コンパイルデバイス１００は、コード生成器１４０を含む。コード生成器１４０は、修正ＳＳＡグラフを実装するためのコードを生成し、オブジェクトコードを生成する。具体的には、ＳＳＡグラフの第２の部分グラフは、単一の演算としてオブジェクトコードコンピュータプログラムに実装されるので、第１の部分グラフの辺に対応する代入が省略される。例えばコード生成器１４０は、パーサ１２０から、修正ＳＳＡグラフ１３６と、第２の部分グラフを置換した特別な頂点がどのように実装されるべきかを詳述する情報１３７とを受け取る。通常、情報１３７は、置換された各部分グラフの１つ以上のテーブルである。
【００４９】
一実施形態では、図２ｄ及び図２ｅの変換が使用される。置換された部分グラフは、符号化データに作用するテーブルとして実装される。各辺は少なくとも非表示開始辺、非表示ではない中間辺及び非表示終了辺を含むパスに置換されているので、全ての変数を符号化変数に置換することが可能である。情報１３７はまた、テーブルの入力又は出力として使用される変数の符号化方法を示す符号化情報を含んでいてよい。必要に応じて、コード生成器は、非表示セクションの始まり又は終わりにおいて、コードを符号化形式に変換したり、コードを符号化形式から戻したりするコードを追加することができる。
【００５０】
図１ｂは、探索ユニット２００の一実施形態の一例を概略的に示す。探索ユニットは、探索ユニット１３０の代わりに、図１ａにおいて使用することができる。第１の部分グラフＮの複数のスーパーグラフにわたって反復するのではなく、探索ユニット２００は、最小カットアルゴリズムを適用して、第２の部分グラフを得る。最小カットアルゴリズムは、いわゆるソース頂点とシンク頂点とを有し、辺が重みを有する有向グラフに適用されるアルゴリズムである。最小カットアルゴリズムは、このようなグラフ内で、ソース頂点をシンク頂点から分離する最小合計重みを有する辺の集合を見つける。当業者は、例えば多項式時間で効率的に実行される様々な最小カットアルゴリズムを利用することができる。例えばJianxiu Haoによる「A Faster Algorithm for Finding the Minimum Cut in a Directed Graph」（Journal of Algorithms１７、４２４−４４６（１９９４）に掲載）を検討されたい。最小カットアルゴリズムを適用して、非表示部分グラフの効率的な置換を見つけることができ、また、どのようにしてこれを行うことができるかは、発明者の洞察であった。最小カットを適用する方法は幾つかあり、そのうちの幾つかを以下に詳述する。
【００５１】
図５ａ乃至図５ｅを参照して、最小カットアルゴリズムの実施形態を説明する。図５ａに、例示的なＳＳＡグラフを示す。例えば図５ａのＳＳＡグラフは、ソースコード１０２の一部を表す。図５ａでは、ボックスを使用して引数（例えば入力）を表し、小さい白丸を使用して出力を表し、小さい黒丸を使用して頂点を表す。辺は、対応する変数のビットサイズがラベル付けされている。図５ａは、ノード５０１〜５１５を示す。図５ａはまた、破線の辺で示されている第１の部分グラフを示す。この例における第１の部分グラフは、頂点５０８、５１５及び５１６によって形成されている。
【００５２】
第１段階において、ＳＳＡグラフから派生グラフ（derivative graph）が生成される。派生グラフ内の頂点は、ＳＳＡグラフ内の頂点に対応するか、又は、ソース若しくはシンクといった追加頂点である。なお、ＳＳＡグラフ内の全ての頂点が、派生グラフ内に表されるとは限らない。派生グラフの作成は、探索ユニット２００内の派生ＳＳＡグラフ生成器２１０によって行われてよい。
【００５３】
ＳＳＡグラフから生成された派生グラフは、第１の部分グラフの流入辺を含む有向パスを介して第１の部分グラフに連結されたＳＳＡグラフ内の頂点及び辺（Ａ）を含む。これは、第１の部分グラフＮの祖先グラフと呼ばれる。第１の部分グラフ（Ｎ）の頂点の少なくとも一部もまた、派生グラフに含まれる。一実施形態では、第１の部分グラフが、派生グラフに完全に含まれる。
【００５４】
Ｎの祖先グラフもまた、Ｎ自体を含んでもよい。なお、第１の部分グラフの祖先グラフを計算することによって、ＳＳＡグラフから多くの頂点及び辺を失う可能性がある。派生グラフの２つの異なる例を示す図５ｂ及び５ｃにおいて、頂点５０４、５０５及び５１１は、Ｎの祖先グラフにはなく、派生グラフにもまたない。このことは、図５ｂ及び５ｃでは、これらのラベルを点線のボックスに入れることによって示されている。派生グラフにはまた、ソース頂点及びシンク頂点も含まれている。これらは追加された頂点である。図５ｂ及び５ｃでは、ソースは、参照符号５２０及び文字Ｓで示され、シンクは、参照符号５３０及び文字Ｔで示されている。
【００５５】
ソース頂点は、ＳＳＡグラフ、具体的には流入辺のない祖先グラフの頂点に、無限ビットサイズの辺で連結される。流入辺のない派生グラフ内の頂点はまた、祖先グラフの最上部とも呼ばれる。シンク頂点は、第１の部分グラフ内の頂点のうちの少なくとも１つの頂点に、無限ビットサイズの辺で連結される。一実施形態では、シンクは、第１の部分グラフＮから出る流出辺を有する第１の部分グラフＮの少なくとも頂点に、無限ビットサイズの辺で連結される。
【００５６】
辺は、通常、対応する代入のビットサイズでラベル付けされている。無限大のビットサイズを代入することによって、この辺が、最小カット解の一部にならないことが確保される。無限大サイズの辺を使用しない任意の他の解が、そのような辺を使用する解よりも優先される。なお、この場合の無限大とは、これらの辺がもはや解に含まれないように十分に大きい数を表す技術用語である。実装では、これらの辺に大きな数を任意に代入することができる。これらの辺が解に依然として選択される場合、値を大きくすることができる。或いは、全ての辺の合計よりも大きい値を無限大として使用することができる。これにより、非無限大の辺の幾つか又は全部を使用する任意の解が、より小さい解を有することが保証される。
【００５７】
図５ｂは、派生グラフを生成する第１のやり方を示す。図５ｂの派生グラフは、第１の部分グラフの全てを含む祖先グラフと、祖先グラフの最上部に連結されたソースと、第１の部分グラフの最下部頂点に連結されたシンクとを含む。第１の部分グラフの最下部頂点は、第１の部分グラフから出ていく辺を有する頂点である。ソース及びシンクへの辺並びにソース及びシンクからの辺と、第１の部分グラフ内の無限大のビットサイズを有する辺とを除き、全ての辺は、元のＳＳＡグラフと同じビットサイズを有する。
【００５８】
図５ｃは、派生グラフを生成する第２のやり方を示す。図５ｃの派生グラフは、第１の部分グラフの全てを含む祖先グラフと、祖先グラフの最上部に連結されたソースと、第１の部分グラフ内の全頂点に連結されたシンクとを含む。無限大のビットサイズを有するソース及びシンクへの辺並びにソース及びシンクからの辺を除いて、全ての辺は、元のＳＳＡグラフと同じビットサイズを有する。第１の部分グラフの内側にある辺は全て除去される。
【００５９】
派生グラフを作成する両方の例において、第１の部分グラフにない任意の非表示辺のビットサイズもまた無限大に設定される。１つの実装では、多くの非連結部分グラフがありうるが、このような追加の非表示辺は、図５ａ乃至図５ｅにはない。例えばＳＳＡグラフの非表示にされるべき更なる部分グラフの更なる指示が受け取られていてもよい。なお、これは、更なる部分グラフが第２の部分グラフに完全に含まれる解を排除しない。これは問題ではない。
【００６０】
最後に、最小カットアルゴリズムが派生グラフに適用されて、派生グラフの２つの部分グラフへの分割（Ｓ、Ｔ）が得られる。２つの部分クラブのうちの一方は、ソース頂点を含み、他方はシンク頂点を含む。ＳとＴとの間の辺が最小カットである。例えば探索ユニット２００は、最小カットソルバー２２０を含んでよい。これで、第２の部分グラフを、ＳＳＡグラフにおいて、シンクを含む第２の分割部内の頂点に対応する部分グラフとして得ることができる。
【００６１】
図５ｄは、図５ａの元のＳＳＡグラフに投影された最小カット解５７０を示す。５７０における曲線の内側の頂点及び辺は、最小カット解の一部である。なお、最小カット解５７０の流入辺のビットサイズの合計は、次の通りである。
辺５０１−５０２：８
辺５０６−５０２：２
辺５１０−５０８：８
辺５１３−５１４：８
合計：２６
これを第１の部分グラフのサイズの合計と比較すると、次の通りになる。
辺５１０−５０８：８
辺５０３−５０８：１６
辺５１４−５１５：８
合計：３２
【００６２】
このように、第１の部分グラフは、３２ビットではなく２６ビットだけの入力サイズを有する単一の複素演算で表すことができる。例えば第２の部分グラフがテーブルによって表されるならば、当該テーブルは、第１の部分グラフの直接のテーブルよりも２６倍（６＝３２−２６）小さい。実際のアルゴリズムの実装に対応するより大きなグラフでは、削減は更に大きくなる。なお、ビットサイズを変更することによって、図５ａから更なる例が得られる。例えば全てのビットサイズが２で除算されるならば、同じ解が見出される。
【００６３】
最後に、ＳＳＡグラフモディファイア２３０が、元のＳＳＡグラフを修正し、第２の部分グラフを単一の新しい複素演算子に置換することができる。これは図５ｅに示されている。この例では、第１の部分グラフによってもともと行われたのと同じ計算を表す新しい頂点５４０が追加される。なお、元の第２の部分グラフの一部は、第１の部分グラフの出力ではない第２の部分グラフの出力、例えば流出辺をカバーするために複製されている。図５ｅでは、ノード５０２’、５０３’及び５０７’は、ノード５０２、５０３及び５０７に対応するが、入力から供給ノード５１０及び５０４にコピーされている。
【００６４】
派生ＳＳＡグラフが作成される前に、他の幾つかの修正が行われてもよい。例えば第１の部分グラフ（Ｎ）の内部頂点を縮約することができる。例えば第１の部分グラフ全体を縮約することができる。例えばデッドコード削除アルゴリズムを最初にＳＳＡグラフ上で実行してデッドコードを削除し、削除されるコードについてのテーブルが作成されることを回避することができる。ＳＳＡグラフの一部を、例えば縮約によって一時的に、又は、例えばデッドコード除去によって永久的に除去すると、メモリ内のＳＳＡグラフのサイズが縮小され、これは、アルゴリズムを実行するのに必要なリソースを低減する。
【００６５】
以下に、特定の実施形態のより数学的な説明を示す。
【００６６】
ＳＳＡグラフＧ内の第１の部分グラフをＮとする。第１の部分グラフＮは、空グラフではなく、特別なノードを含まない。つまり、ＳＳＡグラフＧの引数及び結果は、非表示にされない。集合Ｎの入力及び出力を次のように定義する。
【数１】
2020503623.tif 000003
【００６７】
表記ｐ→ｑは、ｐからｑへの有向辺を示す。Ｎの入力の全幅を＃ｉｎをする。Ｎの出力の全幅を＃ｏｕｔとする。Ｎのテーブル実装は、２＃ｉｎ個のエントリを有するテーブルを必要とし、各エントリは#ｏｕｔビットを必要とする。これは、急速に成長し、部分集合Ｎを実装するための多くのテーブルは、現行のコンピュータアーキテクチャではしばしば実現不可能である。
【００６８】
したがって、次のような部分グラフＰに関心が寄せられている。
Ｐ⊇Ｎ∧ｏｕｔ．Ｎ⊆ｏｕｔ．Ｐ∧＃ｉｎ．Ｐは最小である。
【００６９】
このようなＰは存在しなければならない。以下に、１つを建設的に作成する１つのやり方を説明する。Ｎ自体を含むＮ内のノードの祖先グラフをＡとする。祖先を有さず、Ｎの一部ではないＡ内のノードをＴｏＰ（Ａ）とする。この場合、Ｎは入力を有するので、ＴｏＰ（Ａ）は空ではない。幅が無限大の辺で全てのＴｏＰ（Ａ）ノードに連結する特別なノードであるソースを作成する。ＡからＮの内部にある全ての辺を除去し、Ｎ内の全てのノードが無限大の幅の辺で連結する特別なノードであるシンクを導入する。
【００７０】
Ｎへの入力辺がグラフＡのカットを形成する。これは、Ｎの入力辺の１つを含まないソースからシンクへのパスがないことを意味する。この結果、Ｎの入力引数の幅は、少なくとも祖先グラフの最小カットの幅となることが分かる。データフローグラフが、Ｎの外側に、非表示とマーク付けされている更なる辺を有する場合、これらは、無限大のサイズに変更される。
【００７１】
最小カットアルゴリズムを使用することによって、祖先グラフの最小カットを見つけることができる。更に、Ｓがソースノードを含み、Ｔがシンクノードを含み、ＳからＴへの辺が最小カットを形成するグラフ（Ｓ；Ｔ）の分割を見つけることができる。Ｎからシンクまでの辺が無限大の幅を有し、最小カットの一部ではないため、集合Ｔは、Ｎの全てのノードを含む。したがって、Ｔ⊇Ｎである。Ｔの入力は、Ａにおいて最小であり、また、Ａは祖先グラフなので、Ｔの入力はＧにおいても同じである。集合Ｔの入力は、幅が無限大であるため、非表示の入力はない。したがって、Ｔは、内部の非表示辺を有し、非表示入力辺を有さない。Ｔは、非表示出力辺を有しうるが、例えば図３ａ及び図３ｂに示すように、これらをＳＳＡグラフの一部とする。
【００７２】
非表示とマーク付けされた流出辺を有するノードをｐとする。非表示辺だけからなるパスを通ってｐから到達可能な全てのノードの集合をＨ：ｐとする。集合Ｈ：ｐは、テーブル演算子を作成したいノードの最小集合である。Ｔをテーブル演算に置換すると、グラフから少なくとも１つの非表示辺が除去される。このプロセスは、非表示辺がなくなるまで繰り返される。
【００７３】
なお、このようにして得られたテーブルは、入力幅において最適である。必要なメモリリソースは、入力幅において指数関数的であるため、これは最大の寄与である。それでも、Ｔよりも大きい集合が、その出力はより小さいことにより、メモリが少なくて済む（例えば小さいテーブルで済む）ことが依然として可能である。大きい集合の出力が非常に小さいので、これが入力幅の増加を相殺することが可能である。
【００７４】
このようなことは比較的まれであり、少し優れた解が存在する可能性を受け入れるだけでよい。更に、単純なヒューリスティックが実際にうまくいくことが分かる。これは、より効率的な実装は、存在するならば、ｑの出力を使用すべきではないからである。したがって、ｑの子はノード集合の一部でなければならない。Ｔの入力は最小である。したがって、より効率的な任意の解は、ｑの出力よりも小さいｑの子孫の出力を必要とする。多くの場合、これらの出力は存在しない。更に、それらが存在する場合、これらの子孫は到達可能でなければならず、また、内部ノードが元の集合に追加されなければならない。新しい集合は、等しい出力を有する極小集合に変換されて、入力幅に対する任意の影響が観察される。
【００７５】
したがって、よりメモリ効率の良い実装のために、探索空間を迅速かつ効率的に削減することができる。実際には、ヒューリスティックが十分に機能する。同様に、できるだけテーブルの数を少なくするために、できるだけ多く元のグラフをカバーするテーブルを見つけることが道理にかなっている。なお、例えば図５ｄでは、他の同様に優れた解が可能であるが、これらは、ＳＳＡグラフの小さい部分をカバーする。一実施形態によるアルゴリズムは非常に高速であるので、通常のコンパイルパスで、様々なヒューリスティックを実行することができる。例えば２つの部分グラフを非表示にしたい場合は、２つの部分グラフの和集合に対してアルゴリズムを試すことができる。
【００７６】
この解は、特に解がテーブルを使用する場合に、計算において真に非表示となるデータを提供する。更に、当該解は、少なくとも入力ビット数において最適である。当該解は、複数の可能な連結非表示値の非表示にすることを支援する。
【００７７】
図４ａ乃至図４ｃは、更に別の例を示す。図４ａは、非表示変数を有するソースコードプログラム断片を示す。図４ｂは、点線で非表示プロパティを有する辺を示す。図４ｃは、テーブル挿入後の状態を示す。
【００７８】
実施形態は、従来のコンパイラ技術と容易に統合することができる。プロトタイプが実装され、プロトタイプでは、プログラマが変数に非表示プロパティでラベル付けすることができる。このプロパティは、データフローグラフ内の、後にコンパイルデバイスによってカバーされる多くの非表示辺に変換される。この実施形態は、特にセキュリティアプリケーションにおいて、高速で、プログラマにとって有用であることが分かった。テーブルエントリの数が非常に多くても、テーブル内で非表示にすることが実行不可能でも、これはコンパイラがプログラマに直接報告できる有用な情報である。メモリ使用に関して最適な解決策がすぐには見つからない場合でも、より良い解決策のために、単純なヒューリスティックによって、探索空間をすばやく縮小することができる。
【００７９】
様々な実施形態において、入力１０２及び１０４（例えば入力インターフェース）は、様々な代替案から選択されてもよい。例えば入力インターフェースは、ローカル又はワイドエリアネットワーク（例えばインターネット）へのネットワークインターフェース、内部又は外部のデータストレージへのストレージインターフェース、キーボード等であってよい。
【００８０】
ＳＳＡグラフ１２２、第２のＳＳＡグラフ１３６及び情報１３７といった中間結果は、例えばコンパイルデバイス１００に含まれる、又は、コンパイルデバイス１００によってアクセス可能な電子記憶装置に格納することができる。記憶装置は、電子メモリ（例えばフラッシュメモリ）又は磁気メモリ（例えばハードディスク）等として実装することができる。記憶装置は、当該記憶装置を共に構成する複数の個別メモリを含んでよい。記憶装置は、一時記憶装置（例えばＲＡＭ）であってもよい。
【００８１】
典型的には、デバイス１００は、デバイス１００に格納されている適切なソフトウェアを実行するマイクロプロセッサ（別個には図示せず）を含む。例えば当該ソフトウェアは、ダウンロードされて、及び／又は、対応するメモリ（例えばＲＡＭといった揮発性メモリ又はフラッシュメモリといった不揮発性メモリ）（別個には図示せず）に格納されていてもよい。或いは、デバイス１００は、全体的に又は部分的に、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）としてプログラマブルロジックで実装されてもよい。デバイス１００は、全体的に又は部分的に、いわゆる特定用途向け集積回路（ＡＳＩＣ）、即ち、それらの特定の使用のためにカスタマイズされた集積回路（ＩＣ）として実装されてもよい。例えば回路は、例えばＶｅｒｉｌｏｇ、ＶＨＤＬ等のハードウェア記述言語を使用してＣＭＯＳで実装されてもよい。
【００８２】
一実施形態では、デバイス１００は、入力回路、パーサ回路、探索回路、コード生成回路を含む。デバイス１００は、追加の回路、例えば第２のグラフ選択回路、ＳＳＡグラフ修正回路、派生ＳＳＡグラフ生成回路、最小カット解決回路等を含むことができる。これらの回路は、本明細書に説明される対応するユニットを実装する。これらの回路は、プロセッサ回路及び記憶回路であってよく、プロセッサ回路は、記憶回路において電子的に表される命令を実行する。これらの回路はまた、ＦＰＧＡ、ＡＳＩＣ等でもよい。
【００８３】
プロセッサ回路は、例えば複数のサブプロセッサ回路として分散方式で実装されてもよい。記憶装置は、複数の分散下位記憶装置に分散されてもよい。メモリの一部又は全部が、電子メモリ、磁気メモリ等であってよい。例えば記憶装置は、揮発性部分と不揮発性部分とを有してもよい。記憶装置の一部が読み取り専用になっていてもよい。
【００８４】
図６は、コンパイル方法６００の一実施形態の一例を概略的に示す。コンパイル方法６００は、ソースコードコンピュータプログラム１０２をオブジェクトコードコンピュータプログラム１０６に変換する。コンパイル方法は、
ソースコードコンピュータプログラムを受信するステップ６１０と、
ソースコードコンピュータプログラムを解析するステップ６２０と、
ソースコードコンピュータプログラムの少なくとも一部について、静的単一代入（ＳＳＡ）グラフ１２２を生成するステップ６３０であって、ＳＳＡグラフの頂点は演算に対応し、ＳＳＡグラフの辺は代入に対応し、代入は対応するビットサイズを有する、ステップ６３０と、
ＳＳＡグラフの空ではない第１の部分グラフＮの指示１０４を受信するステップ６４０と、
ＳＳＡグラフの第２の部分グラフＰを探索するステップ６５０であって、第１の部分グラフＮは、第２の部分グラフＰの部分グラフであり（Ｎ⊆Ｐ）、第２の部分グラフの流入辺に関連付けられているビットサイズの合計は、第１の部分グラフの流入辺に関連付けられているビットサイズの合計より小さい、ステップ６５０と、
ＳＳＡグラフの第２の部分グラフを、オブジェクトコードコンピュータプログラム内に、単一の演算として実装し、これにより、第１の部分グラフの辺に対応する代入を省略するステップ６６０とを含む。
【００８５】
当業者には明らかなように、方法を実行するやり方は多く様々に可能である。例えばステップの順序は変更することができ、又は、幾つかのステップは並行して実行することができる。更に、ステップ間に他の方法ステップを挿入することができる。挿入されたステップは、本明細書に説明されているような方法の改良を表しても、又は、上記方法とは無関係でもよい。更に、あるステップが次のステップが開始される前に完全に終了していなくてもよい。
【００８６】
本発明による方法は、プロセッサシステムに方法６００を行わせる命令を含むソフトウェアを使用して実行することができる。ソフトウェアは、システムの特定のサブエンティティによって行われるステップのみを含んでいてよい。ソフトウェアは、ハードディスク、フロッピー（登録商標）、メモリ、光ディスク等の適切な記憶媒体に格納されていてよい。ソフトウェアは、電線に沿った信号として又は無線で、或いは例えばインターネットであるデータネットワークを使用して送信することができる。ソフトウェアは、ダウンロード及び／又はサーバ上での遠隔使用のために利用可能にすることができる。本発明による方法は、方法を行うために、プログラマブルロジック、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）を設定するように構成されたビットストリームを使用して実行されてもよい。
【００８７】
当然のことながら、本発明は、本発明を実施するのに適したコンピュータプログラム、特に担体上又は担体内のコンピュータプログラムにも及ぶ。プログラムは、ソースコード、オブジェクトコード、コード中間ソース及び部分的にコンパイルされた形式等のオブジェクトコードの形式又は本発明による方法の実装における使用に適した他の任意の形式であってよい。コンピュータプログラムプロダクトに関連する実施形態は、説明された方法のうちの少なくとも１つの方法の各処理ステップに対応するコンピュータ実行可能命令を含む。これらの命令は、サブルーチンに細分されても、及び／又は、静的若しくは動的にリンクされている１つ以上のファイルに格納されてもよい。コンピュータプログラムプロダクトに関連する別の実施形態は、説明されたシステム及び／又はプロダクトのうちの少なくとも１つのシステム及び／又はプロダクトの各手段に対応するコンピュータ実行可能命令を含む。
【００８８】
図７ａは、一実施形態による、コンピュータプログラム１０２０を含む書き込み可能部分１０１０を有するコンピュータ可読媒体１０００を示す。コンピュータプログラム１０２０は、プロセッサシステムにコンパイル方法を行わせる命令を含む。コンピュータプログラム１０２０は、物理的なマークとして、又は、コンピュータ可読媒体１０００の磁化によって、コンピュータ可読媒体１０００上に具現化することができる。しかし、任意の他の適切な実施形態も同様に考えられる。更に、当然ながら、コンピュータ可読媒体１０００は、ここでは光ディスクとして示されているが、コンピュータ可読媒体１０００は、ハードディスク、半導体メモリ、フラッシュメモリ等といった任意の適切なコンピュータ可読媒体であってよく、また、記録不可能であっても、記録可能であってもよい。コンピュータプログラム１０２０は、プロセッサシステムに、上記コンパイル方法を行わせる命令を含む。
【００８９】
図７ｂは、一実施形態によるプロセッサシステム１１４０の概略図である。プロセッサシステムは、１つ以上の集積回路１１１０を含む。図７ｂに、１つ以上の集積回路１１１０のアーキテクチャが概略的に示されている。回路１１１０は、一実施形態による方法を実行し及び／又はそのモジュール若しくはユニットを実装するためにコンピュータプログラム構成要素を実行する処理ユニット１１２０（例えばＣＰＵ）を含む。回路１１１０は、プログラミングコード、データ等を格納するメモリ１１２２を含む。メモリ１１２２の一部は、読み取り専用であってよい。回路１１１０は、通信要素１１２６（例えばアンテナ、コネクタ又はその両方等）を含んでよい。回路１１１０は、方法で定義された処理の一部又は全部を行う専用集積回路１１２４を含んでよい。プロセッサ１１２０、メモリ１１２２、専用ＩＣ１１２４及び通信要素１１２６は、相互接続１１３０（例えばバス）を介して互いに接続されてよい。プロセッサシステム１１１０は、それぞれアンテナ及び／又はコネクタを使用して、接触及び／又は非接触通信用に構成することができる。
【００９０】
例えば一実施形態では、コンパイルデバイスは、プロセッサ回路とメモリ回路とを含み、プロセッサは、メモリ回路に格納されているソフトウェアを実行する。例えばプロセッサ回路は、Ｉｎｔｅｌ  Ｃｏｒｅ  ｉ７プロセッサ、ＡＲＭ  Ｃｏｒｔｅｘ−Ｒ８等であってよい。メモリ回路は、ＲＯＭ回路又は不揮発性メモリ（例えばフラッシュメモリ）であってよい。メモリ回路は、揮発性メモリ（例えばＳＲＡＭメモリ）であってもよい。後者の場合、検証デバイスが、ソフトウェアを提供するように構成された不揮発性ソフトウェアインターフェース（例えばハードドライブ、ネットワークインターフェース等）を含んでよい。
【００９１】
次の節は、請求項ではなく、本発明の様々な実施形態に関するものである。出願人は、本願又はそこから派生する任意の更なる出願の審査手続中に、当該節、並びに／又は、当該節及び／若しくは明細書若しくは請求項からの特徴の組み合わせから、新しい請求項を作成することができることをここに記す。特に、この節は、以下に列挙される従属請求項のいずれとも組み合わせることができる。
【００９２】
第１節
ソースコードコンピュータプログラム１０２をオブジェクトコードコンピュータプログラム１０６に変換するコンパイルデバイス１００であって、
ソースコードコンピュータプログラムを受信する入力部１１０と、
ソースコードコンピュータプログラムを解析（１２０）し、ソースコードコンピュータプログラムの少なくとも一部について、静的単一代入（ＳＳＡ）グラフ１２２を生成するプロセッサ回路と、
を含み、
ＳＳＡグラフの頂点は、演算に対応し、ＳＳＡグラフの辺は、代入に対応し、代入は、対応するビットサイズを有し、
入力部１１０は更に、ＳＳＡグラフの空でない第１の部分グラフＮの指示１０４を受信し、
プロセッサ回路は更に、ＳＳＡグラフの第２の部分グラフＰを探索し、
ＳＳＡグラフの第２の部分グラフを、オブジェクトコードコンピュータプログラムに、単一の演算として実装させて、これにより、第１の部分グラフの辺に対応する代入を省略し、
第１の部分グラフＮは、第２部分グラフの部分グラフであり（Ｎ⊆Ｐ）、第２の部分グラフの流入辺に関連付けられるビットサイズの合計は、第１のグラフの流入辺に関連付けられるビットサイズの合計より小さい。
【００９３】
なお、上記実施形態は、本発明を限定するのではなく例示するものであり、当業者であれば多くの代替実施形態を設計することができるであろう。
【００９４】
請求項において、括弧内に配置された任意の参照符号は、請求項を限定するものとして解釈されるべきではない。動詞「含む」及びその活用形の使用は、請求項に記載された要素またはステップ以外の要素又はステップの存在を排除するものではない。要素に先行する冠詞「ａ」又は「ａｎ」は、当該要素が複数存在することを排除するものではない。本発明は、幾つかの異なる要素を含むハードウェアによって、及び、適切にプログラミングされたコンピュータによって実現することができる。幾つかの手段を列挙しているデバイスの請求項において、これらの手段の幾つかは、同一のハードウェアアイテムによって具体化されてもよい。特定の手段が互いに異なる従属請求項に記載されているというだけで、これらの手段の組み合わせが有利に使用することができないことを示すものではない。
【００９５】
請求項において、括弧内の参照は、実施形態を例示する図面中の参照符号又は実施形態の式を指し、したがって、請求項の理解度を高めるものである。これらの参照は、特許請求の範囲を限定するものとして解釈されるべきではない。
【図１ａ】
2020503623.tif 000004
【図１ｂ】
2020503623.tif 000005
【図２ａ】
2020503623.tif 000006
【図２ｂ】
2020503623.tif 000007
【図２ｃ】
2020503623.tif 000008
【図２ｄ】
2020503623.tif 000009
【図２ｅ】
2020503623.tif 000010
【図３ａ】
2020503623.tif 000011
【図３ｂ】
2020503623.tif 000012
【図４ａ】
2020503623.tif 000013
【図４ｂ】
2020503623.tif 000014
【図４ｃ】
2020503623.tif 000015
【図５ａ】
2020503623.tif 000016
【図５ｂ】
2020503623.tif 000017
【図５ｃ】
2020503623.tif 000018
【図５ｄ】
2020503623.tif 000019
【図５ｅ】
2020503623.tif 000020
【図６】
2020503623.tif 000021
【図７ａ】
2020503623.tif 000022
【図７ｂ】
2020503623.tif 000023
【国際調査報告】
2020503623.tif 000024
2020503623.tif 000025
2020503623.tif 000026