(57)【要約】  幾つかの実施態様は、エンコードされていると印された１以上の出力ノード及びエンコードされていないと印された１以上の出力ノードを有するデータフローグラフにおける部分グラフ２１０を識別すると共に、該部分グラフをエンコードされた第１部分グラフ２１０．１及びエンコードされていない第２部分グラフ２１０．２により置換するように構成されたコンパイラ装置１００に関するもので、前記第１部分グラフはエンコードされた出力ノードのみを有する一方、前記第２部分グラフはエンコードされていない出力ノードのみを有する。
2021507391.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータプログラム表現を受信する入力インターフェースと、
プロセッサ回路と、
を有するコンパイラ装置であって、該プロセッサ回路が、
前記コンピュータプログラム表現からデータフローグラフの表現を得ることであって、ここで、該データフローグラフにおけるノードの少なくとも一部はエンコードされたものとして又はエンコードされていないものとしてマーキングされるものとし、エンコードされたノードはエンコードされたデータに対する演算を表し、エンコードされていないノードはエンコードされていないデータに対する演算を表す、得ることと、
前記データフローグラフを補正することであって、
前記データフローグラフにおいてエンコードされているとマーキングされた１以上の出力ノード及びエンコードされていないとマーキングされた１以上の出力ノードを有する部分グラフを識別し、
前記部分グラフをエンコードされた第１部分グラフ及びエンコードされていない第２部分グラフにより置換し、ここで、前記第１部分グラフはエンコードされた出力ノードのみを有し、前記第２部分グラフはエンコードされていない出力ノードのみを有し、これら第１部分グラフ及び第２部分グラフは前記部分グラフから更なる部分グラフとして選択されるものとし、
前記第１部分グラフの前にエンコードする演算を表す１以上のノードを挿入して該第１部分グラフがエンコードされたデータに対してのみ作用するようにし、及び／又は前記第２部分グラフの前にデコードする演算を表す１以上のノードを挿入して該第２部分グラフがエンコードされていないデータに対してのみ作用するようにする、
ことにより補正することと、
少なくとも前記補正されたデータフローグラフから前記コンピュータプログラム表現のコンパイルを得ることとを行う、
コンパイラ装置。
【請求項２】
前記部分グラフにおける少なくとも入力ノードが前記第１及び第２部分グラフにおいて複製される、請求項１に記載のコンパイラ装置。
【請求項３】
前記第１及び第２部分グラフが前記部分グラフの複製である、請求項１又は請求項２に記載のコンパイラ装置。
【請求項４】
前記補正された部分グラフに対してデッドコード除去最適化を実行する、請求項３に記載のコンパイラ装置。
【請求項５】
前記第１部分グラフにおけるノードはエンコードされているとマーキングされ、前記第２部分グラフにおけるノードがエンコードされていないとマーキングされる、請求項１から４の何れか一項に記載のコンパイラ装置。
【請求項６】
前記データフローグラフが静的単一代入グラフである、請求項１から５の何れか一項に記載のコンパイラ装置。
【請求項７】
前記部分グラフがファイノード及びコピーノードからなる、請求項１から６の何れか一項に記載のコンパイラ装置。
【請求項８】
前記エンコードが準同型暗号化である、請求項１から７の何れか一項に記載のコンパイラ装置。
【請求項９】
前記コンピュータプログラム表現が前記データフローグラフにおける１以上のノードをエンコードされた又はエンコードされていないものとして識別し、及び／又は
前記プロセッサ回路が、幾つかのノードをエンコードされていないものとしてマーキングすると共に残りのノードをエンコードされているものとしてマーキングするエンコーディング規則を適用する、
請求項１から８の何れか一項に記載のコンパイラ装置。
【請求項１０】
前記部分グラフが複数のソース及び複数の目標を持つデータを示す、請求項１から９の何れか一項に記載のコンパイラ装置。
【請求項１１】
前記データフローグラフにおける前記部分グラフが、エンコードされているものとしてマーキングされた１以上の入力ノード及びエンコードされていないものとしてマーキングされた１以上の入力ノードを有する、請求項１から１０の何れか一項に記載のコンパイラ装置。
【請求項１２】
前記プロセッサ回路が、
前記補正された又は補正されていないデータフローグラフにおいて、フローノード、該フローノードの前のエンコードする又はデコードする演算及び該フローノードの後の演算ノードを識別し、ここで、前記フローノードはファイノード又はコピーノードであり、
前記演算ノードを前記フローノードの後から削除すると共に該フローノードの前に１以上の演算ノードを挿入し、
挿入された演算ノードを前記エンコードする又はデコードする演算と併合する、
請求項１から１１の何れか一項に記載のコンパイラ装置。
【請求項１３】
コンピュータプログラム表現を受信する入力インターフェースと、
プロセッサ回路と、
を有するコンパイラ装置であって、該プロセッサ回路が、
前記コンピュータプログラム表現からデータフローグラフの表現を得ることであって、ここで、該データフローグラフにおけるノードの少なくとも一部はエンコードされたものとして又はエンコードされていないものとしてマーキングされる、得ることと、
補正された又は補正されていないデータフローグラフにおいてフローノード、該フローノードの前のエンコードする又はデコードする演算及び該フローノードの後の演算ノードを識別することであって、ここで、前記フローノードはコピーノード又はファイノードであり、コピーノードは到来する値を１以上の他のノードに分配する、識別することと、
前記データフローグラフを補正することであって、
前記演算ノードを前記フローノードの後から削除すると共に前記フローノードの前に１以上の演算ノードを挿入し、
挿入された演算ノードにより表される演算を前記エンコードする又はデコードする演算と併合する、
ことにより補正することと、
少なくとも前記補正されたデータフローグラフから前記コンピュータプログラム表現のコンパイルを得ることとを行う、
コンパイラ装置。
【請求項１４】
コンピュータプログラム表現を受信するステップと、
前記コンピュータプログラム表現からデータフローグラフの表現を得るステップであって、該データフローグラフにおけるノードの少なくとも一部がエンコードされたものとして又はエンコードされていないものとしてマーキングされる、得るステップと、
前記データフローグラフを補正するステップであって、
前記データフローグラフにおいてエンコードされているとマーキングされた１以上の出力ノード及びエンコードされていないとマーキングされた１以上の出力ノードを有する部分グラフを識別し、ここで、エンコードされたノードはエンコードされたデータに対する演算を表し、エンコードされていないノードはエンコードされていないデータに対する演算を表し、
前記部分グラフをエンコードされた第１部分グラフ及びエンコードされていない第２部分グラフにより置換し、ここで、前記第１部分グラフはエンコードされた出力ノードのみを有し、前記第２部分グラフはエンコードされていない出力ノードのみを有し、これら第１部分グラフ及び第２部分グラフは前記部分グラフから更なる部分グラフとして選択され、
前記第１部分グラフの前にエンコードする演算を表す１以上のノードを挿入して該第１部分グラフがエンコードされたデータに対してのみ作用するようにし、及び／又は前記第２部分グラフの前にデコードする演算を表す１以上のノードを挿入して該第２部分グラフがエンコードされていないデータに対してのみ作用するようにする、
ことにより補正するステップと、
少なくとも前記補正されたデータフローグラフから前記コンピュータプログラム表現のコンパイルを得るステップと、
を有する、コンパイラ方法。
【請求項１５】
コンピュータプログラム表現を受信するステップと、
前記コンピュータプログラム表現からデータフローグラフの表現を得るステップであって、該データフローグラフにおけるノードの少なくとも一部がエンコードされたものとして又はエンコードされていないものとしてマーキングされる、得るステップと、
前記データフローグラフを補正するステップであって、
補正された又は補正されていないデータフローグラフにおいてフローノード、該フローノードの前のエンコードする又はデコードする演算及び該フローノードの後の演算ノードを識別し、ここで、前記フローノードはコピーノード又はファイノードであり、コピーノードは到来する値を１以上の他のノードに分配し、
前記演算ノードを前記フローノードの後から削除すると共に該フローノードの前に１以上の演算ノードを挿入し、
挿入された演算ノードにより表される演算を前記エンコードする又はデコードする演算と併合する、
ことにより補正するステップと、
少なくとも前記補正されたデータフローグラフから前記コンピュータプログラム表現のコンパイルを得るステップと、
を有する、コンパイラ方法。
【請求項１６】
プロセッサシステムに請求項１４又は請求項１５に記載の方法を実行させる命令を表わした一時的又は非一時的データを有する、コンピュータ読取可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイル（コンパイラ）装置、コンパイラ方法及びコンピュータ読取可能な媒体に関する。
【背景技術】
【０００２】
プログラムにより使用され又は処理されるデータは高い価値を有し得る。例えば、所与の機能を実施することを可能にする機械学習アルゴリズムは、機械学習過程の間に学習される非常に固有な重み（例えば、機械学習モデルの）を使用する。プログラムのリバースエンジニアリングは、攻撃者が訓練過程を実現すべく当該機械学習アルゴリズム又は計算能力を訓練するために使用されるデータに対するアクセスを要せずにアルゴリズム機能を容易に複製し又は改善することができるように、これらの重みを明らかにする（暴露させる）ことができる。同様に、幾つかのアプリケーションは秘密暗号キー等の秘密データにより計算する。これらのキーを権限のない使用から保護することが重要である。
【０００３】
秘密情報を暴露し得るリバースエンジニアリングからコンピュータプログラムを保護するための種々のやり方が存在する。例えば、種々の既知の難読化方法は、コンピュータプログラムにおけるデータフローを辿ることを困難にさせる。
【０００４】
更に、コンピュータプログラムが作用するデータ（例えば、変数）にエンコーディングを適用することもできる。このような保護されたプログラムをリバースエンジニアリングしようと試みる攻撃者は、当該プログラムが何のデータに作用するかが分からない。例えば、種々のホワイトボックスエンコーディングを用いることができる。例えば、当該アルゴリズムを保護するために、完全準同型暗号化（fully homomorphic encryption）を用いることができる。しかしながら、これらのエンコーディング技術のプログラムに対する自動化された適用は危険性を有する。コンパイラは、攻撃者により利用され得る状況を、知らぬうちに形成し得る。これらは攻撃者が当該エンコーディングを打ち破る助けとなり得る。エンコーディング及びデコーディング処理が手動で挿入されたとしても、セキュリティ問題が不注意に挿入される危険性が存在する。
【０００５】
既知のコンパイラが、米国特許出願第2003221121号に記載されている。該既知のコンパイラは、ソフトウェアを改竄及びリバースエンジニアリングから保護する。当該プログラムのデータフローは、見える処理がオリジナルのソフトウェアコードの意図から無関係とされるように変換される。その意図は、攻撃者が当該コードの実行を観察することによりデータフローを理解及びデコードすることが困難であると分かるようにすることである。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
既知のコンパイラは、既存のソフトウェアにエンコーディング及びデコーディング処理を挿入することが危険な状況を生じ得るという欠点を有する。
【課題を解決するための手段】
【０００７】
上記課題は、請求項に記載のコンパイラ装置及び方法において対処される。
【０００８】
例えば、データフローのグラフにおいて、混合された出力（例えば、エンコードされた及びエンコードされていない出力）を有する部分グラフを識別することができる。このような非同種的部分グラフ（副グラフ）は、コンパイルされたコードにおいてエンコーディング及びデコーディング演算が互いに即座に続くような経路につながり、より容易に分析可能な状況につながり得る。このような問題は、当該部分グラフが所謂コピー／ファイ（copy-phi）ネットワーク（例えば、当該プログラムにおけるデータの流れにのみ関係する部分）である場合に特に重大となる。
【０００９】
例えば、エンコードする演算が、演算的ノードというよりファイ処理又はコピー処理により後続されるような部分グラフを識別することができる。このことは、上記のエンコードする演算が後続の演算的ノードと併合することができないという欠点を有する。当該演算をファイ処理又はコピー処理を経て後方（逆方向）伝搬させることにより、併合する機会が形成される。
【００１０】
データフローグラフに対してなされる当該改善は、データフローグラフを補正するための他の既知の技術と組み合わせることができる。例えば、コンパイラ設計から既知の最適化技術を、当該データフローグラフに適用することができる。例えば、当該データ又はデータフローを不明瞭にさせる難読化技術を適用することもできる。
【００１１】
当該コンパイル装置は電子装置であり、例えば、該コンパイル装置はコンピュータ、サーバ、デスクトップコンピュータ、ラップトップ等とすることができる。該コンパイル装置は、他のプログラミングツール又は更なるコンパイル装置（例えば、リンカ等）と組み合わせることができる。
【００１２】
本明細書に記載されるコンパイラ（コンパイル）方法は、広範囲の実用的用途に適用することができる。このような実用的用途は、例えば、デジタルメッセージの暗号化、解読及び認証等の暗号アプリケーションの難読化を含む。例えば、当該コンパイル方法は私有アルゴリズム、例えば学習アルゴリズム、画像処理、オーディオ処理等の難読化に適用することができる。
【００１３】
本発明による方法は、コンピュータ上でコンピュータ実施化方法として、専用のハードウェアで、又は両者の組合せで実施することができる。本発明による方法のための実行可能なコードは、コンピュータプログラム製品に記憶することができる。コンピュータプログラム製品の例は、メモリ装置、光記憶装置、集積回路、サーバ、オンラインソフトウェア等を含む。好ましくは、コンピュータプログラム製品は、該プログラム製品がコンピュータ上で実行された場合に本発明による方法を実行するためのコンピュータ読取可能な媒体に記憶された非一時的プログラムコードを有する。
【００１４】
好ましい実施態様において、当該コンピュータプログラムは、該コンピュータプログラムがコンピュータ上で実行された場合に本発明による方法の全てのステップを実行するように構成されたコンピュータプログラムコードを有する。好ましくは、該コンピュータプログラムはコンピュータ読取可能な媒体上で具現化される。
【００１５】
本発明の他の態様は、前記コンピュータプログラムをダウンロードのために利用可能にする方法を提供する。この態様は、当該コンピュータプログラムが例えばアップル社のアップルストア、グーグル社のプレイストア又はマイクロソフト社のウインドウズストアにアップロードされ、該コンピュータプログラムが斯様なストアからダウンロードのために利用可能にされた場合に用いられる。
【００１６】
本発明の更なる詳細、態様及び実施態様は図面を参照して例示のみとして後述されるであろう。尚、各図における要素は簡略化及び明瞭化のために図示されており、必ずしも実寸では描かれていない。また、各図において、既に記載された要素に対応する要素は同一の符号を有し得る。
【図面の簡単な説明】
【００１７】
【図１】図１は、コンパイル装置の実施態様の一例を概略的に示す。
【図２ａ−２ｅ】図２ａから図２ｅは、データフローグラフの実施態様の一例を概略的に示す。
【図３ａ−３ｂ】図３ａ及び図３ｂは、データフローグラフの実施態様の一例を概略的に示す。
【図４】図４は、データ暗号化及び解読システムの実施態様の一例を概略的に示す。
【図５】図５は、エンコードされたソフトウェアの実施態様の一例を概略的に示す。
【図６ａ−６ｃ】図６ａから図６ｃは、コンパイル方法の実施態様の一例を概略的に示す。
【図７ａ】図７ａは、一実施態様によるコンピュータプログラムを有する書込可能部分を備えたコンピュータ読取可能な媒体を概略的に示す。
【図７ｂ】図７ｂは、一実施態様によるプロセッサシステムの図を概略的に示す。
【発明を実施するための形態】
【００１８】
本発明は多数の異なる形態の実施態様が可能であるが、本開示は本発明の原理の例示として見なされるべきであり、本発明を図示及び記載される特定の実施態様に限定することを意図するものではないとの理解の下で、１以上の特定の実施態様が図面に示されると共に明細書に詳細に記載される。
【００１９】
以下では、理解のために、実施態様の要素は動作時において説明される。しかしながら、各要素は、これら要素により実行されると記載されている機能を果たすように構成されていることは明らかであろう。
【００２０】
更に、本発明は実施態様に限定されるものではなく、本発明は本明細書に記載され又は互いに異なる従属請求項に記載された各及び全ての新規なフィーチャ又はフィーチャの組み合わせに存するものである。
【００２１】
先に指摘したように、コンピュータプログラムを権限のないリバースエンジニアリングから保護する多くの理由が存在する。例えば、ソフトウェアは、暗号処理、例えば暗号化／解読処理又は署名処理を表し得る。暗号処理のために必要とされる秘密情報を秘密に維持したいという要望が存在する。ソフトウェアは、私有アルゴリズム、例えば（訓練された）ニューラルネットワーク、画像処理アルゴリズム等も有し得る。ソフトウェアに埋め込まれたノウハウを秘密に維持したという要望も存在し得る。これを行うための１つの方法は、当該ソフトウェアに使用されるデータをエンコード（例えば、暗号化）することである。斯かるエンコードされたデータは、適切に適合化されたソフトウェア演算部により処理され得る。例えば、論理又は算術処理（演算）は、エンコードされたデータに対して作用することができるように、テーブルとして又は有限体上の多項式等としてエンコードすることができる。このような処理は、ホワイトボックス暗号法の分野から知られている。しかしながら、これらの技術は、暗号法の外部でも適用することができる。データをエンコードし、該エンコードされたデータに対して作用するテーブルを用いる一例は、Chow他による文献“White-box Cryptography and an AES Implementation”に示されている。
【００２２】
データのエンコーディングを種々のタイプのソフトウェアに適用する大きな可能性が存在するので、データのエンコーディングを自動化する要望が存在する。しかしながら、このことは余り容易ではないことが分かった。本発明の実施態様は、エンコードされるべき変数及び計算を自動的に決定するシステム及び方法を説明する。
【００２３】
近年、完全準同型方式及びエンコード方式に大きな進展があった。準同型方式を使用することは、エンコードされたデータに対する演算を容易にさせる。最初の完全準同型暗号化（Fully Homomorphic Encryption）方式は、２００９年にGentryにより提案された。このようなＦＨＥ方式は、両基本代数演算、即ち、加算及び乗算を尊重する。それ以降、多くの他の方式が提案されている。SEL（Simple Encrypted Arithmetic Library）は、専門家により及び暗号的背景の少ない又は無い非専門家の両方により使用するのが容易な、外部依存性のない、良く設計され且つ文書化された準同型暗号ライブラリを提供することを目指した実用的ライブラリである。SEAL自体は、RLWE問題に依拠するＦＶ準同型暗号化方式を使用する。いずれの（完全）準同型暗号化方式においても、３つのキー：
−  平文を暗号文に暗号化するために使用される公開キー；
−  暗号化ドメインで演算（例えば、乗算）を実行するために使用される評価キー；及び
−  ユーザが出力を解読することを可能にする秘密キー；
が含まれる。
【００２４】
可能性のある使用例が図４に示されている。図４は、ノード４１０（例えば、コンピュータ）、並びにエンコーディング／デコーディング、暗号化／解読関数及び秘密／公開／評価キーの別のソフトウェア／ハードウェアブロックへの分配を示している。ノード４１０は、データ発生器４２０（例えば、センサ）を有している。該データ発生器はデータを公開キーpubKにより暗号化する。ソフトウェア４３０は、暗号化されたドメインにおけるソフトウェアに対し評価キー（evalk）を用いて演算を実行する。該計算の結果は、クラウド４５０において動作するソフトウェア４６０に送信することができる。例えば、ソフトウェア４６０はセキュアな環境で動作することが信用され得るものである。ソフトウェア４６０は、解読アルゴリズム４６２を適用することにより上記計算結果を解読する。例えば、該解読は、何らかのセキュアな要素４７２に記憶された秘密キーを使用することができる。このように、ソフトウェア４３０は少なくとも部分的に暗号化されたデータに対して動作する。
【００２５】
他の応用例が図５に示されている。図５は、エンコードされたドメインにおける演算の図を示す。ホワイトボックス暗号法の分野から派生するエンコーディング方式は、アルゴリズム及びそのデータのリバースエンジニアリングを一層困難にするように設計されている。エンコーディングは、例えば、（ｉ）ニブル、（ii）剰余数システム、又は（iii）代数変換等に基づくものとすることができる。図５は、エンコードされたドメインで実現される演算の抽象的表現を示す。整数の環(R,+,*)上での評価関数f()に代えて、Ｒにおける要素は変換T()により別のドメインＡに変換され、かくして、同じ関数f()をＡにおいて表される要素及び代替演算
【数１】
2021507391.tif 000003
に基づいて実施することができるようにする。この実施はF()として示されている。このような方式は、T()がデータを暗号化するための公開キーの使用を表すことができ、F()で実現される演算がエンコードされた演算及び何らかのタイプの評価キーを伴い、逆変換が秘密キーの使用と等価であるという点で、幾らか(F)HEに類似している。しかしながら、ホワイトボックス暗号法においては、変換T()及びT-1()の使用をコード自体に併合することが通常である。抽出の困難性は、例えば、これらを実施化する大きなテーブル等をリバースエンジニアリングすることの困難性に依存する。
【００２６】
図１は、コンパイル（コンパイラ）装置１００の実施態様の一例を概略的に示す。
【００２７】
コンパイラ装置１００は、コンピュータプログラム表現を受信するように構成された入力インターフェース１１０を有する。例えば、当該コンピュータプログラム表現は、高レベルコンピュータプログラムで（例えば、Ｃ、パスカル、Ｃ＃等で）書かれたものであり得る。例えば、該コンピュータプログラム表現はソースコードであり得る。該コンピュータプログラム表現は、例えばマクロを実行することにより又はコンピュータコードを構文解析することによりコンピュータプログラムコードを前処理するように構成することができる他のコンパイラ装置の出力とすることもできる。例えば、該コンピュータプログラムコード表現は、高レベルコンピュータコードのデータフローグラフの表現とすることができる。該コンピュータプログラム表現は、コンパイラ中間言語によるものとすることができる。
【００２８】
入力インターフェース１１０は、通信インターフェースであり得る。コンパイラ装置１００は、コンピュータネットワーク（図１には示されていない）を介して他のコンピュータ装置と通信することができる。該コンピュータネットワークは、インターネット、イントラネット、ＬＡＮ、ＷＬＡＮ等とすることができる。該コンピュータネットワークはインターネットであり得る。該コンピュータネットワークは、全体として若しくは部分的に有線とすることができ、及び／又は全体として若しくは部分的に無線とすることができる。例えば、該コンピュータネットワークはイーサネット接続を有し得る。例えば、該コンピュータネットワークは、Wi-Fi及びジグビ等の無線接続を有することができる。当該コンパイラ装置は、必要に応じて他の装置と通信する（例えば、当該コンピュータプログラム表現を受信する）ように構成された接続インターフェースを有することができる。例えば、該接続インターフェースは、例えば有線コネクタ（例えば、イーサネットコネクタ）又は無線コネクタ（例えば、アンテナ（例えば、Wi-Fi、４Ｇ又は５Ｇアンテナ））等のコネクタを有することができる。該コンピュータプログラム表現は、電子形態で受信することができる。
【００２９】
当該コンパイラ装置の実行は、その例が本明細書に示されるプロセッサ回路において実施される。図１は、斯かるプロセッサ回路の機能ユニットであり得る複数の機能ユニットを示す。例えば、図１は当該プロセッサ回路の可能な機能的編成の青写真として用いることができる。当該プロセッサ回路は、図１では斯かるユニットから別途に示されてはいない。例えば、図１に示される機能ユニットは、装置１００に（例えば、該装置１００の電子メモリに）記憶されると共に、該装置１００のマイクロプロセッサにより実行可能なコンピュータ命令で全体として又は部分的に実施化することができる。混成実施態様において、機能ユニットは、部分的にハードウェアで（例えば、コプロセッサとして）実施化されると共に、部分的に装置１００において記憶及び実行されるソフトウェアで実施化される。
【００３０】
コンパイラ装置１００は、コンピュータプログラム表現（例えば、入力インターフェース１１０から受信されたままの）を記憶するための記憶部１２０を有する。記憶部１２０は、中間表現（例えば、データフローグラフ等）を記憶するために使用することもできる。
【００３１】
コンパイラ装置１００は、解析部１３０、修正部１４０及びコンパイルユニット１５０を有する。解析部１３０は、データフロー解析器１３２及びエンコード分析器１３４を有する。解析部１３０及びエンコード分析器１３４は、一緒に、前記コンピュータプログラム表現からデータフローグラフ表現を取得し、該データフローグラフにおけるノードの少なくとも一部はエンコードされたもの又はエンコードされていないものとして印される。
【００３２】
例えば、上記データフローグラフは静的単一代入（ＳＳＡ）形式のものであり得る。これは、ソフトウェアコンパイラにより分析及び最適化を実行するためのコード表現として使用される良く知られた、一般的で効率的なフロー暴露（flow-exposed）形式である。静的単一代入に基づく効率的なアルゴリズムが、定数伝搬、冗長計算検出、デッドコード（不要コード）除去、機能変数（induction variable）除去及び他の要件に対処するために開発されている。
【００３３】
データフローグラフを（特に、ＳＳＡ形式で）得ると共に、コンピュータプログラムをデータフローグラフに基づいて最適化及び／又はコンパイルするための効率的なアルゴリズムが知られている。本発明の好ましい実施態様は、静的単一代入に関して説明される。標準的コンパイラ設計のための背景を提供することができる標準的参考文献は、Steven Muchnickによる１９９７年の文献“Advanced Compiler Design & Implementation”(ISBN 1-55860-320-4)である。
【００３４】
このようにして、部分的コンパイルの後に、各変数が正確に一度だけ代入され且つ各変数が使用される前に定義される静的単一代入（ＳＳＡ）特性を持つデータフローグラフ表現を得る。このグラフにおいて、エッジは（一時的）変数であり、ノードは演算（＋，−，＊，…）、メモリアクセス（＊ｐ＝…）等である。ＳＳＡ形式のデータフローグラフの一例が図２ａに示されている。実際には、データフローグラフは大幅に大きくなり得、その場合、図２ａは一層大きなデータフローグラフの細部と考えることができる。該データフローグラフは、全体のプログラムのデータフローグラフである必要はなく、一部、例えば、ライブラリ、ルーチン、基本ブロック等のデータフローグラフとすることができる。
【００３５】
ＳＳＡグラフ、特にＳＳＡグラフ２００は、コンピュータプログラムコードの（例えば、ソースコードの）中間形態を表す一種のデータフローグラフである。ＳＳＡグラフは方向性且つ非環的である。ＳＳＡグラフの頂点（ノードとも称される）は、演算を表す。ＳＳＡグラフのエッジ（辺）は、レジスタ（例えば、仮想レジスタを含む）又はメモリ（例えば、メモリの選択された部分）等のデータホルダを表す。図２ａは、コンピュータプログラム（断片）に対応する例示的ＳＳＡグラフを示す。ここに図式的に示されるＳＳＡグラフは、コンパイラ装置１００の電子メモリにおけるデータ構造として表すことができることに注意されたい。
【００３６】
当該ＳＳＡグラフにおける２つのタイプのノード、即ち、コピーノード（copy nodes）及びファイノード（phi-nodes）は特別なものである。ＳＳＡグラフは、入力値を１以上のノードに分配するコピーノードを含み得る。図２ｂは、１つの斯様なコピーノード（即ち、コピーノード２１４）を示している。ファイ演算は、当該グラフにおける制御フローにより生じるデータ選択を実施するために使用される。例えば、ｚ＝Φ(a,b)は、ａに対する最後の代入がｂに対する最後の代入より最近である場合、ｚにはａが代入されるべきであることを意味する。ｂに関して、逆も同様である。例示的グラフ２００は２つのファイノード（即ち、ファイノード２１２及びファイノード２１６）を有する。
【００３７】
構文解析及びＳＳＡ変換（もし、必要なら）の後、結果的データフローグラフは、ファイノード及びコピーノードのみからなる部分グラフ又は部分ネットワークを含み得る。このような部分グラフの境界は、例えば算術演算、メモリ演算等の異なるタイプの記述を伴うノードにより表される。後者は演算ノードと称することができる。
【００３８】
実行の間に生きており且つ複数のソース及び複数の目標を持つデータは、ＳＳＡデータフローグラフにおいてコピー／ファイネットワークとして見えるであろう。このように、当該データフローがＳＳＡ形式である場合、複数のソース及び複数の目標を伴うデータをコピー／ファイネットワークとして識別することができる。しかしながら、これは必要ではない。例えば、別のタイプのデータフローグラフは、複数のソース及び複数の目標を持つデータを識別する別の方法を有する。ここに記載される好ましい実施態様はＳＳＡ型データフローグラフを用いるので、続けてコピー／ファイネットワーク又はコピー／ファイ部分グラフと称する。
【００３９】
データフローグラフ２００は、３つのノードを有するコピー／ファイネットワーク２１０を示している。図２ａにおける他のノードは、他の演算を表し得る。例えば、ノード２２２及び２３４は増加（インクリメント）演算、例えば“i:=j+1”を表し得る。例えば、ノード２２４はメモリからの読出演算を表し得る。例えば、ノード２２６は、パラメータ入力、例えばパラメータからルーチンへの入力を表し得る。例えば、ノード２３６は算術演算を表し得る。当該コピー／ファイネットワークにおけるノードは、図２ａ〜図３ｂでは斑点パターンにより印される。
【００４０】
エンコード分析器１３４は、当該データフローグラフにおけるノードをエンコードされたものとして又はエンコードされていないものとして印す。例えば、このことは、例えば当該データフローグラフに関する解析と一緒に、コンパイル過程において実行することができる。コピー又はファイノード等のフロー制御ノード演算は、印されることを要さない。ノードのエンコードされたもの又はエンコードされていないものとしての印し付け（マーキング）は、後にコンパイルユニット１５０により使用することができる。例えば、コンパイルユニット１５０はエンコードされていないノードに対して作用するために本来の演算を使用することができる。例えば、インクリメント演算はコンパイルユニット１５０により、例えばマシン“ＩＮＣ”命令により実施することができる。エンコードされた演算の場合、コンパイルユニット１５０はエンコードされた演算を使用することができる。例えば、当該演算を実行するためにライブラリを呼び出すことができる。例えば、コンパイルユニットは、エンコードされたインクリメントを実行するために“ENC_INC()”演算を呼び出すことができる。エンコードされた関数は、エンコードされたデータを受信し、エンコードされたデータを出力する。例えば、エンコードされた演算は、テーブルとして又は有限体上の多項式として実施することができる。
【００４１】
プログラム、該プログラムの変数及び／又は処理されたデータを保護するために、暗号化ドメインで実行されるプログラムＰを自動的に生成する処理を有することが望ましい。例えば、プログラマはプログラムを平文ドメインで書き得、後になってのみ、該プログラマは斯かるプログラムを暗号化されたドメインで実行することに興味を有するであろう。ノードを自動的に、手動で又は一部手動／一部自動でマーキングすることにより、コンパイラユニット１５０は正しいエンコードされた又はエンコードされていない機能を呼び出すために要する情報を有する。それでも、プログラムの開発は、これらの事項に多く注意を払うことなく行われ得る。
【００４２】
ノードをエンコードされたものとして又はエンコードされていないものとして印すことは、エンコーディング規則に従って実行することができる。例えば、規則の基礎は、幾つかのノードがエンコードされていないもの（非エンコード）であることを必要とし得る。例えば、メモリアクセス、外部関数コール及びパラメータに対応するノードは非エンコードと印され得る。例えば、一実施態様において、幾つかのノードは当該規則に従って非エンコードと印され得、残された全てのノードはエンコードされたものと印され得る。
【００４３】
例えば、一実施態様において、エンコーディングに対する制限はインターフェースに由来し得る。例えば、コンピュータコードは、使用されるエンコーディングと互換性のない装置、メモリ又は他のソフトウェアとインターフェースしなければならない。エンコーディングに対する制限は、当該コンパイルユニット又は使用されるライブラリにおける制限に由来することもあり得る。例えば、幾つかの演算、例えば浮動小数点数に対する演算等は、エンコードされた形態ではサポートされない。
【００４４】
例えば、一実施態様においては、２段階方法を用いることができる。幾つかのノード（例えば、メモリアクセス、外部関数コール等に対応するノード）は規則により非エンコードでなければならない。全ての他のノードは初期的にグリーンと印すことができる。更なる規則（例えば、経験則）に従い、幾つかのノードは、初期的にエンコードされたものであったとしても、エンコードされていないものとしてマーキングすることができる。例えば、構文解析の後、幾つかの演算は暗号化された形態で実行することができないことが分かり得る。例えば、ライブラリは、これら演算をサポートしない。例えば、幾つかのノードは、浮動小数点数に対する演算に対応し得るが、エンコードされた浮動小数点演算は利用可能でないであろう。当該コンパイルユニットは警告又は出力ログ等を出力することができ、かくして、プログラマが、何の演算がエンコードされた形態で実行され、どの演算が実行されないかを検証することができるようにする。一実施態様において、プログラマは当該コンピュータプログラム表現にコンパイラ指示文を挿入することができる。例えば、ソースコードにおいて、プログラマは何の変数がエンコードされるべきであり、又は何の変数がエンコードされるべきでないかを示すことができる。一実施態様においては、コピー／ファイノードを除く全ノードがエンコードされているか又はエンコードされていないか印される。
【００４５】
ノードをエンコードされたもの又はエンコードされていないものとしてマーキングすることが、図２ｂに示されている。図２ｂは、コピー／ファイネットワーク２１０が示されている。コピー／ファイネットワーク２１０に入力を供給するノード、即ち入力ノード２２０；及びコピー／ファイネットワーク２１０から入力を受ける又はコピー／ファイネットワーク２１０が出力するノード、即ち出力ノード２３０も示されている。エンコードされていないノード（本例では、ノード２２４、２２６及び２３２）は、暗いグレイでマーキングされている。エンコードされているノード（本例では、ノード２２２、２３４及び２３６）は、明るいグレイでマーキングされている。
【００４６】
コンパイラ装置１００は修正部１４０を有する。修正部１４０は、特定のセキュリティ問題を回避するためにデータフローグラフを修正（例えば、補正）するように構成される。好ましくは、データフローグラフは機能を変化させないものとするが、当該修正後に演算が実行される態様は特定のセキュリティ上の危険性を低減する。一実施態様において、修正部１４０はデータフロー分析器１４２及びデータフロー補正ユニット１４４を有し得る。データフロー分析器１４２は当該部分グラフにおける潜在的問題を識別するように構成される。データフロー補正ユニット１４４は、当該データフローグラフをデータフロー分析器１４２により発見された問題を軽減すべく修正するように構成される。
【００４７】
何のノードがエンコードされ、何のノードがエンコードされていないかを決定した後、当該データフローグラフに変換を挿入することができる。斯かる変換を挿入することは、当該データフローグラフが有効なままになるという利点を有する。即ち、エンコードされた及び／又はエンコードされていない演算を伴うデータフローグラフにおいて、変換無しでは当該プログラムは適切に動作しないことがあり得る。
【００４８】
図２ｃは、ノードがエンコードされている又はエンコードされていないものとしてマーキングされた図２ｂのデータフローグラフ２０１を示す。図２ｃは、コンパイルユニットが図２ｂのエンコーディング／非エンコーディングのマーキングを単純な態様で実施すべきであったなら生じ得る問題を示している。
【００４９】
コピー／ファイネットワークの単純実施は、変数が間に僅かなコピー／ファイステップのみを伴って（時には、単一のステップのみの後に）エンコードされ及びデコードされるようなプログラムのエンコードされた実現につながり得る。図２ｃにおいては、データをエンコードドメインから非エンコードドメインに又はその逆に変換するために変換ノード２２１及び２３１が挿入される。１つの斯様な挿入された変換が図２ｃでは符号２２３により印されている。例えば、ファイノード２１２は両データをエンコードされたもの又はエンコードされていないものとして必要とする。従って、ノード２２４の出力を暗号化するためにファイノード２１２とノード２２４との間に変換ノードが挿入される。一方、ノード２３２は自身の入力をエンコードされていないものとして必要とするので、エンコードされたものからエンコードされていないものに変換するためにファイノード２１４と２３２との間に変換ノードが挿入される。ファイノード２１６と入力ノード２２６との間にも変換が挿入されることを要する。何故なら、さもなければ、ファイノード２１６はエンコードされた及びエンコードされていない両方のデータを受け得るからである。ファイノード２１６の後には変換は挿入されない。該ファイノード２１６の出力の全てのユーザはエンコードされたデータを期待しているからである。変換は必要とされる箇所に挿入することができる。例えば、一般的に、非エンコード／エンコードノードに対して入力を受け又は出力を生成するエンコード／非エンコードノードは変換が挿入されることを要し得る。例えば、複数の非同種入力ノードからデータを受け、又は複数の非同種出力ノードに対して出力を生成するファイ関数又はコピー関数は、変換ノードの挿入を必要とし得る。
【００５０】
ノード２２４からノード２３２までの経路において、データは変換ノード２２１及び２３１においてエンコードされ、その直後にデコードされることに注意されたい。単一の値がエンコードされ、続いてデコードされるような状況は望ましくない。何故なら、その場合、暗号化／解読関数（例えば、テーブル）が見え、容易に突き止められ得るからである。更に、エンコードされた値は当該プログラムを介して更なる修正無しで伝搬され得、かくして、該値は“追跡され”得るからである。
【００５１】
何れの場合においても、解読は望ましくはなく、解読を回避することは改善となる。例えば、(F)HEが使用される場合、秘密キー（当該情報を解読するために必要とされる）の使用はセキュリティのリスクとなり得る。秘密キーは、利用可能でないことさえあり得る。
【００５２】
保護されたプログラムが図２ｃから生成された場合、攻撃者は当該値の暗号化された表現を容易に学ぶことができる。何故なら、該攻撃者は暗号化されようとしている値をいずれの計算も実行することなく見付け、暗号化された値を観測することしか要さないからである。該値が与えられれば、攻撃者は全ての他の値の暗号化された表現を導出することができる。
【００５３】
幾つかの完全準同型暗号化方式及びエンコーディング方式の場合、状況は更に悪くなり得る。例えば、暗号化された値E(Y)及び暗号化された値の間の除算演算を実施するルーチンが分かる場合、暗号化された／エンコードされた値を自身で除算することにより、１の暗号化された表現（即ち、E(1)=E(Y)/E(Y)）を得ることができる。この値から、秘密キー又は当該エンコーディングが分からなくても、例えば暗号化された加算関数を呼び出すことにより、全ての値を得ることができる。
【００５４】
一実施態様において、データフロー分析器１４２は当該データフローグラフにおいてエンコードされているとして印された出力ノード及びエンコードされていないとして印された出力ノードを有する部分グラフを識別するように構成される。言い換えると、エンコードされたデータ及びエンコードされていないデータの両方を生成する部分グラフである。一実施態様において、該部分グラフはコピー／ファイネットワークに限定される。例えば、データフロー分析器１４２は、エンコードされたデータ及びエンコードされていないデータの両方を生成する、例えばエンコードされていると印された少なくとも１つのノード及びエンコードされていないと印された少なくとも１つのノードにデータを送る（例えば、エンコードされている及びエンコードされていないノードの両方のノードに向かう出力エッジを備えた）コピー／ファイネットワークを識別するように構成される。同様のことを、非ＳＳＡ型データフローグラフにおいても実行することができる。例えば、実行の間に生きていると共に、複数のソース及び複数の目標（該複数の目標はエンコードされた及びエンコードされていない両方の演算を含む）を有するデータを識別することができる。一実施態様において、データフロー分析器１４２は、両入力が混合されており（例えば、エンコードされた及びエンコードされていない入力を有する）、且つ、出力が混合されている（例えば、エンコードされた及びエンコードされていない両出力を有する）部分グラフを識別するように構成される。
【００５５】
このようなコピー／ファイネットワークは、前述した一種の非安全な状況につながり得る。これら状況は、変数及び／又はデータのエンコーディング及び即座のデコーディングを防止するために該コピー／ファイネットワークを重複させ及び／又は分割することにより回避することができる。例えば、当該グラフにおける入力及び出力がエンコード及び非エンコードの両方であるコピー／ファイネットワークを、結果としてのネットワークがエンコードされた又はエンコードされていない（平文の）出力のみを有するように（即ち、出力が同種となるように）、分割させ及び／又は重複させることができる。
【００５６】
データフロー補正ユニット１４４は、識別された部分グラフをエンコードされた第１部分グラフ及びエンコードされていない第２部分グラフにより置換するように構成することができる。上記第１部分グラフはエンコードされた出力ノードのみを有する一方、上記第２部分グラフはエンコードされていない出力ノードのみを有する。該第１部分グラフ及び第２部分グラフは、前記部分グラフの更なる部分グラフとして得ることができる。例えば、図２ｅを考察しよう。図２ｅにおいて、コピー／ファイネットワーク２１０は第１部分グラフ210.1及び第２部分グラフ210.2により置換されている。第１部分グラフ210.1はエンコードされたデータのみを生成する。第２部分グラフ210.2はエンコードされていないデータのみを生成する。両部分グラフは、補正されていない部分グラフから更なる部分グラフを取り出すことにより発生することができる。例えば、第１部分グラフ210.1は、ノード２１２及び２１６により形成される図２ｂの部分グラフに対応する。例えば、第２部分グラフ210.2は、ノード２１２及び２１４により形成される図２ｂの部分グラフに対応する。これらの更なる部分グラフは重なり合わないものであることを要しないことに注意されたい。例えば、ノード２１２は両方において図２ｂの更なる部分グラフとなっている。
【００５７】
第１部分グラフはエンコードされた出力のみを生成するので、エンコードされた入力のみを用いて動作することができる。例えば、第１部分グラフは、該第１部分グラフに対するエンコードされていない入力は変換されることを要することをコンパイルユニットに示すために、エンコードされているとマーキングすることができる。同様に、第２部分グラフはエンコードされていない出力のみを生成するので、エンコードされていない入力のみを用いて動作することができる。例えば、第２部分グラフは、該第２部分グラフに対するエンコードされている入力は変換されることを要することをコンパイルユニットに示すために、エンコードされていないとマーキングすることができる。図２ｅは、このことを、第１及び第２部分グラフの前後に変換ユニットを挿入することにより示している。部分グラフ210.2はエンコードされていない入力のみを受ける一方、部分グラフ210.1はエンコードされた入力のみを受けることに注意されたい。
【００５８】
例えば、ネットワークの分割は、先ずネットワークを複製し（例えば、クローンを作り）、次いで、これらネットワークの一方をエンコードされたものとして、他方をエンコードされていないものとして割り当てることにより実現することができる。このステップの後に、ネットワークにおけるエンコードされていない変数を伴う入力／出力経路とインターフェースする複製ノードは、中間ノードがエンコードされるべきでない安全でない経路としてマーキングすることができ、ネットワークにおけるエンコードされた変数を伴う入力／出力経路とインターフェースする複製ノードは、中間ノードがエンコードされなければならない安全な経路としてマーキングされるであろう。
【００５９】
図２ｅのグラフを生成する特に効率的な方法が、図２ｄに示されている。図２ｄにおいて、コピー／ファイネットワーク２１０全体が、第１のエンコードされた部分グラフ210.1及び第２のエンコードされていない部分グラフ210.2において複製される。これら部分グラフにおけるノードは、オリジナルのコピー／ファイネットワーク２１０が受信したのと同一のノードから入力を受信することに注意されたい。入力ノード２２０と第１及び第２コピー／ファイネットワーク210.1及び210.2との間に変換２２１が挿入され、第１コピー／ファイネットワーク210.1はエンコードされた入力のみを受信し、第２コピー／ファイネットワーク210.2はエンコードされていない入力のみを受信するようにする。即ち、図２ｄにおける入力ノード２２０は、複製のために、２倍の数のノードに出力を送出する。即ち、当該コピー／ファイネットワークの入力側エッジ（例えば、入力ノードの直後のエッジ）も、複製された各コピー／ファイネットワーク毎に複製される。しかしながら、出力側においては斯かる複製は実行されず、エンコードされた出力はエンコードされたコピー／ファイネットワーク210.1に対してのみ接続されたままとなり、エンコードされていない出力はエンコードされていないコピー／ファイネットワーク210.2に対してのみ接続されたままとなる。即ち、当該コピー／ファイネットワークの出力側のエッジは複製されない。
【００６０】
興味深いことに、図２ｄの補正された部分グラフに対して標準的な不要コード除去最適化を実行することにより、必要とされないノードは除去される。特に、ノード216.2及び214.1は死んでおり、除去されるであろう。このことが、図２ｅのグラフを生成する。
【００６１】
最後に、コンパイルユニット１５０は、図２ｅの補正されたデータフローグラフを使用してコンピュータプログラム表現をコンパイルすることができる。コンパイルの分野で一般的であるように、該データフローグラフに対して更なる最適化等を実行することができる。更に、該データフローグラフに対してセキュリティ問題の発見及び解決を反復することができる。
【００６２】
このように、一実施態様を、エンコードされるべき（例えば、プログラムにおいて準同型に暗号化される）変数及び計算を自動的に決定するために使用することができる。このことは、例えばＳＳＡ特性を持つプログラムの中間表現において、本明細書に記載されたもののような危険な状況を探すことにより実施することができる。
【００６３】
一実施態様において、データフロー分析器１４２は異なる潜在的問題を発見するように構成され、データフロー補正ユニット１４４は、これらを解決するように構成される。例えば、一実施態様において、データフロー分析器１４２は、フローノード、該フローノードの前に動作するエンコーディング又はデコーディング、及び該フローノードの後の演算ノードを識別するように構成される。該フローノードは、ファイノード又はコピーノードとすることができる。以下では、当該フローノードはファイノードであると仮定する。その分析はコピーノードに対するものと同様である。
【００６４】
この識別は、図２ａ〜図２ｅにより解説された分析を実行する前及び後の両方で実行することができる。
【００６５】
図３ａは、このような状況の一例を示す。図３ａは、ファイノード３１２並びに３つの演算ノード３２２、３２４及び３３２を有するＳＳＡデータフローグラフを示す。例えば、後者は非フロー演算、例えば非ファイ又は非コピーノードを表すことができる。ここでも、これら演算の幾つか（例えば、ノード３２４）はエンコードされていないとマーキングすることができ、幾つか（例えば、ノード３２２及び３３２）はエンコードされているとマーキングすることができる。非エンコード入力ノード３２４とファイノード３１２との間には変換３２１が挿入される。この状況は望ましくない。このような単独の暗号化関数はいずれの入力パラメータにも適用することができ、エンコードされた値は追跡することができる等となる。
【００６６】
このような状況は、ＳＳＡプログラムフローグラフにおけるノードの後方（逆方向）伝搬（例えば、演算をファイノードより上方に移動させる）により対処することができる。これを実行する際の目標は、エンコード関数を、エンコードされた演算と併合することにより隠蔽することである。
【００６７】
このことが図３ａに示されており、この場合において、図３ａにおけるファイ演算の後に位置される演算３３２は、図３ｂにおけるファイ演算の前に移動され、入力パラメータのエンコーディングが対応するルックアップテーブルの作成により＋１ステートメントにより併合され得るようにする。演算ノード３３２が削除された位置には、コピーノード３１４を挿入することができる。
【００６８】
例えば、データフロー補正ユニット１４４は、データフロー分析器１４２により識別された演算ノードをファイ演算３１２の後から削除すると共に該ファイ演算の前に１以上の演算ノードを挿入するように構成することができる。この場合、当該演算ノードは当該ファイノードが入力を有する分だけ多くの回数で複製される。これが図３ｂに複製された演算332.1及び332.2として示されている。上に移動させることの結果は、複製された演算３３２のうちの少なくとも１つ（この場合では、演算332.2）及び変換３２１が当該データフローグラフにおいて隣接することになることである。結果として、変換３２１は、単一の併合された演算により置換することができる。実際の場合、このことは、当該変換を実施するテーブル又は多項式等を演算332.2と組み合わせることにより実行することができる。例えば、演算332.2はエンコードされた関数F()を実施することができる。当該変換が暗号化Enc()である場合、新たな併合された演算はF(Enc())であり得る。同様に、関数F()が平文関数f()のエンコーディングである場合、併合された演算はEnc(f())であり得る。
【００６９】
図３ｂにおいて、上記２つの関数は楕円３２５により示されている。このように、楕円３２５は、組み合わされたエンコーディングし及び演算するノードにより置換することができる。勿論、変換演算が、後方伝搬が必要とされることなしに、演算ノードと隣接している場合、併合を同様に適用することができる。例えば、データフローグラフが変換ノード３２１及び演算332.2を有する部分グラフを有する場合、併合を直接適用することができる。
【００７０】
例えば、図２ｅにおいて、併合はコピーノード214.2を介して及びファイノード212.2を介してノード２３２を後方伝搬させることにより適用することができる。当該演算は後方伝搬させることはできるが、ここでは、これは必要ではないことに注意されたい。何故なら、変換は先行する命令（該変換に先行する暗号化された演算）と併合することができるからである。このことは、当該先行する命令がエンコードされたものでなかったら不可能であったであろうことに注意されたい（分散を必要とする筋書きが最も有利となるものである）。
【００７１】
隣接する演算がエンコードされている演算である場合、通常のように併合することができる。隣接する演算の何れもエンコードされていない場合、問題が生じる。（例えば、先行者がエンコードされていない演算であり、後続者がファイ／コピー演算である場合）。
【００７２】
後方伝搬は、ノード３１２等のファイノードが複数の演算する出力ノードを有する場合にも使用することができる。このことは、先ず該ファイノード及び該ノードの入力エッジを複製することにより解決することができる。この場合、上記演算する出力ノードの各々は、当該ファイノードの複製のうちの単一のものの出力を受信する。複製ステップの後、後方伝搬を必要に応じて用いることができる。当該フローノードが複数の出力を持つコピーノードである場合にも同様のことが成り立つ。この場合においても、複数の出力はコピーノードを複製することにより減じることができる。
【００７３】
エンコーディングベースの方法において、当該プログラムフローグラフにおいて逆方向に移動された計算的演算を実施するテーブル及びエンコーディングテーブルを併合することは、当該プログラムのリバースエンジニアリングを大幅に困難にさせることに注意されたい。攻撃者は先ず実施された機能を推測することを要し、そこから、該機能を用いて当該エンコーディングをリバースエンジニアリングしなければならないからである。
【００７４】
このように、ＳＳＡデータフローグラフが与えられた場合、該グラフを危険な状況に関して調べることにより当該データフローグラフを改善することができる。例えば、危険な状況は、エンコードされた及びエンコードされていない両方の出力を持つネットワークとして定義される。次に、識別された危険な状況を軽減するために、利用可能な技術の何れかを適用することができるかがチェックされる。例えば、コードを複製し、分割することができ、演算を後方伝搬させることができる。もしそうなら、解決策が適用される。何の技術も利用可能でないなら、当該ネットワークは保護されず且つ問題であると印され、このことは、プログラマが当該コードの該部分に特別な注意を払うことができるという利点を有する。最後に、エンコーディング（例えば、暗号化）を、暗号化を要する各ネットワークに割り当てることができ、この場合、各ネットワークは同一の暗号化で保護される複数の変数を有する。最後に、エンコーディング／デコーディング関数の暴露が減じられた保護されたプログラムが得られる。
【００７５】
一実施態様において、当該コンパイラ装置は特に、補正された又は補正されていないデータフローグラフにおいてファイノード（３１２）、該ファイノードの前で動作するエンコーディング又はデコーディング（３２１）、及び該ファイノードの後の演算ノード（３３２）を識別することにより部分グラフを識別し；本問題を、前記演算ノードをファイノードの後から削除すると共に該ファイノードの前に１以上の演算ノードを挿入し、且つ、挿入される演算ノードを前記エンコーディング又はデコーディング演算と併合することにより軽減するように構成される。例えば、このことは、図２ａ〜図２ｅに示されるように部分グラフを一層同質にすることとは独立に実行することができる。しかしながら、一実施態様においては、両機能が実行される。例えば、コンパイル装置は問題を識別し、必要に応じて適切な解決策を選択することができる。例えば、コンパイル装置は先ず非同種のコピー／ファイネットワークを識別することができ、これらを解決した後、後方伝搬を必要に応じて適用することができる。
【００７６】
コンパイル装置１００の種々の実施態様において、入力インターフェース１１０は種々の代替案から選択することができる。例えば、該インターフェースは、ローカル又は広域ネットワーク（例えば、インターネット）に対するネットワークインターフェース、内部又は外部データ記憶部に対する記憶部インターフェース、キーボード、アプリケーションインターフェース（ＡＰＩ）等とすることができる。例えば、コンピュータプログラム表現は内部又は外部コンピュータプログラム表現記憶部から受信することができる。例えば、コンピュータプログラム表現はキーボード等から受信することができる。
【００７７】
当該コンパイル装置はユーザインターフェースを有することができ、該ユーザインターフェースは１以上の釦、キーボード、ディスプレイ、タッチスクリーン等の良く知られた要素を含むことができる。該ユーザインターフェースは、コンピュータプログラム表現を入力する、コンパイルを実行する等のためのユーザ対話に対応するように構成することができる。
【００７８】
記憶部１２０は、例えばフラッシュメモリ等の電子メモリ、又は例えばハードディスク等の磁気メモリとして実施化することができる。記憶部１２０は、一緒になって該記憶部１２０を形成する複数の別個のメモリを有することができる。記憶部１２０は、例えばＲＡＭ等の一時的メモリとすることもできる。
【００７９】
典型的に、コンパイル装置１００は、該装置１００に記憶された適切なソフトウェアを実行するマイクロプロセッサ（図１には別途図示されてはいない）を有する。例えば、上記ソフトウェアは、ダウンロードされたもの、及び／又はＲＡＭ等の揮発性メモリ若しくはフラッシュ等の不揮発性メモリ等の対応するメモリ（別途図示されてはいない）に記憶されたものとすることができる。代わりに、コンパイル装置１００は、全体として又は部分的に、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）等のプログラマブルロジックで実施化することもできる。装置１００は、全体として又は部分的に、所謂特定用途向け集積回路（ＡＳＩＣ）、即ち特定の用途のためにカスタマイズされた集積回路（ＩＣ）として実施化することもできる。例えば、当該回路は、例えばVerilog、ＶＨＤＬ等のハードウェア記述言語を用いてＣＭＯＳで実施化することができる。
【００８０】
一実施態様において、当該コンパイル装置は、通信インターフェース回路、記憶回路、データフロー解析回路、エンコーディング分析回路、データフロー分析回路、データフロー補正ユニット回路及びコンパイルユニット回路を有する。該コンパイル装置は、追加の回路を有することもできる。これら回路は、本明細書に記載された対応するユニットを構成する。これら回路はプロセッサ回路及び記憶回路とすることができ、該プロセッサ回路は該記憶回路内で電子的に表される命令を実行する。
【００８１】
プロセッサ回路は、分散された態様で（例えば、複数の副プロセッサ回路として）実施化することができる。記憶部は、複数の分散された副記憶部にわたって分散させることができる。当該メモリの一部又は全ては、電子メモリ、磁気メモリ等とすることができる。例えば、当該記憶部は揮発性及び不揮発性部分を有することができる。該記憶部の一部は読み出し専用とすることができる。
【００８２】
図６ａは、コンパイラ方法６００の実施態様の一例を概略的に示す。該方法６００は、
−  コンピュータプログラム表現を受信するステップ６１０と、
−  前記コンピュータプログラム表現からデータフローグラフ２０１の表現を得るステップ６２０であって、該データフローグラフにおけるノードの少なくとも一部がエンコードされたものとして又はエンコードされていないものとしてマーキングされるステップ６２０と、
−  前記データフローグラフを、
−  前記データフローグラフにおいてエンコードされているとマーキングされた１以上の出力ノード及びエンコードされていないとマーキングされた１以上の出力ノードを有する部分グラフ２１０を識別し（６３１）、
−  前記部分グラフをエンコードされた第１部分グラフ210.1及びエンコードされていない第２部分グラフ210.2により置換し（６３２）、ここで、前記第１部分グラフはエンコードされた出力ノードのみを有し、前記第２部分グラフはエンコードされていない出力ノードのみを有し、これら第１及び第２部分グラフは前記部分グラフの更なる部分グラフとして得られるものとし、
−  前記第１部分グラフの前にエンコードする演算を表す１以上のノード２２１を挿入して（６３３）該第１部分グラフがエンコードされたデータに対してのみ動作するようにし、及び／又は前記第２部分グラフの前にデコードする演算を表す１以上のノードを挿入して該第２部分グラフがエンコードされていないデータに対してのみ動作するようにする、
ことにより補正するステップ（６３０）と、
−  少なくとも前記補正されたデータフローグラフから前記コンピュータプログラム表現のコンパイルを得るステップ（６４０）と、
を有する。
【００８３】
図６ｂは、コンパイラ方法６５０の実施態様の一例を概略的に示す。該方法６５０は、
−  コンピュータプログラム表現を受信するステップ６６０と、
−  前記コンピュータプログラム表現からデータフローグラフ２０１の表現を得るステップ６７０であって、該データフローグラフにおけるノードの少なくとも一部がエンコードされたものとして又はエンコードされていないものとしてマーキングされるステップ６７０と、
−  前記データフローグラフを、
−  補正された又は補正されていないデータフローグラフにおいてファイノード３１２、該ファイノードの前のエンコードする又はデコードする演算３２１、及び該ファイノードの後の演算ノード３３２を識別し（６８１）、
−  前記演算ノードをファイ演算の後から削除すると共に前記ファイ演算の前に１以上の演算ノードを挿入し（６８２）、
−  前記挿入された演算ノードを前記エンコードする又はデコードする演算と併合する（６８３）、
ことにより補正するステップ（６８０）と、
−  少なくとも前記補正されたデータフローグラフから前記コンピュータプログラム表現のコンパイルを得るステップ（６９０）と、
を有する。
【００８４】
両方法は、例えばコンパイル（コンパイラ）方法の下記の実施態様に含めることができる。図６ｃは、コンパイラ方法６０１の実施態様の一例を概略的に示す。該コンパイラ方法６０１は、
−  コンピュータプログラム表現を受信するステップ６１０，６６０と、
−  前記コンピュータプログラム表現からデータフローグラフ２０１の表現を得るステップ６２０，６７０であって、該データフローグラフにおけるノードの少なくとも一部がエンコードされたものとして又はエンコードされていないものとしてマーキングされるステップ６２０，６７０と、
−  前記データフローグラフを、
−  前記データフローグラフにおいてエンコードされているとマーキングされた１以上の出力ノード及びエンコードされていないとマーキングされた１以上の出力ノードを有する部分グラフ２１０を識別するか（６３１）、又は補正された若しくは補正されていないデータフローグラフにおいてファイノード３１２、該ファイノードの前のエンコードする又はデコードする演算３２１、及び該ファイノードの後の演算ノード３３２を識別し（６８１）、
−  第１のケースにおいては、
−  前記部分グラフをエンコードされた第１部分グラフ210.1及びエンコードされていない第２部分グラフ210.2により置換し（６３２）、ここで、前記第１部分グラフはエンコードされた出力ノードのみを有し、前記第２部分グラフはエンコードされていない出力ノードのみを有し、これら第１部分グラフ及び第２部分グラフは前記部分グラフの更なる部分グラフとして得られるものとし、
−  前記第１部分グラフの前にエンコードする演算を表す１以上のノード２２１を挿入して（６３３）該第１部分グラフがエンコードされたデータに対してのみ動作するようにし、及び／又は前記第２部分グラフの前にデコードする演算を表す１以上のノードを挿入して該第２部分グラフがエンコードされていないデータに対してのみ動作するようにし、
−  第２のケースにおいては、
−  前記演算ノードをファイ演算の後から削除すると共に前記ファイ演算の前に１以上の演算ノードを挿入し（６８２）、
−  前記挿入された演算ノードを前記エンコードする又はデコードする演算と併合する（６８３）、
ことにより補正するステップ（６３０，６８０）と、
−  少なくとも前記補正されたデータフローグラフから前記コンピュータプログラム表現のコンパイルを得るステップ（６４０，６９０）と、
を有する。
【００８５】
前記補正するステップ６３０は、複数回（例えば、更なる部分グラフが識別されなくなるまで）繰り返すことができる。
【００８６】
当業者にとり明らかなように、当該方法を実行するための多数の異なる態様が可能である。例えば、前記ステップの順序は変更することができ、又は幾つかのステップは並行して実行することができる。更に、ステップの間に他の方法ステップを挿入することもできる。斯かる挿入されるステップは、本明細書に記載されるような当該方法の改良を表すことができ、又は当該方法とは無関係とすることができる。更に、所与のステップは、次のステップが開始される前に完全に完了していなくてもよい。
【００８７】
本発明による方法は、プロセッサシステムに方法６００、６０１又は６５０を実行させるための命令を有するソフトウェアを用いて実行することができる。ソフトウェアは、当該システムの特定の副部分によりなされるステップのみを含むことができる。該ソフトウェアは、ハードディスク、フロッピーディスク、メモリ、光ディスク等の適切な記憶媒体に記憶することができる。該ソフトウェアは、有線に沿い若しくは無線で、又は例えばインターネット等のデータネットワークを使用して信号として伝送することができる。該ソフトウェアは、ダウンロードのために及び／又はサーバ上での遠隔使用のために利用可能にすることができる。本発明による方法は、該方法を実行するために例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）等のプログラマブルロジックを構成するように配されたビットストリームを用いて実行することができる。
【００８８】
以下の番号の節は、想定される限定するものでない実施態様を含む。
１．コンパイラ装置であって、
−  コンピュータプログラム表現を受信するように構成された入力インターフェース１１０と、
−  プロセッサ回路と、
を有し、該プロセッサ回路は、
−  前記コンピュータプログラム表現からデータフローグラフ２０１の表現を得、ここで、該データフローグラフにおけるノードの少なくとも一部はエンコードされたものとして又はエンコードされていないものとしてマーキングされるものとし、
−  前記データフローグラフを、
−  前記データフローグラフにおいてエンコードされているとマーキングされた１以上の出力ノード及びエンコードされていないとマーキングされた１以上の出力ノードを有する部分グラフ２１０を識別し、
−  前記部分グラフをエンコードされた第１部分グラフ210.1及びエンコードされていない第２部分グラフ210.2により置換し、ここで、前記第１部分グラフはエンコードされた出力ノードのみを有し、前記第２部分グラフはエンコードされていない出力ノードのみを有し、これら第１部分グラフ及び第２部分グラフは前記部分グラフの更なる部分グラフとして得られるものとし、
−  前記第１部分グラフの前にエンコードする演算を表す１以上のノード２２１を挿入して該第１部分グラフがエンコードされたデータに対してのみ動作するようにし、及び／又は前記第２部分グラフの前にデコードする演算を表す１以上のノードを挿入して該第２部分グラフがエンコードされていないデータに対してのみ動作するようにする、
ことにより補正し、
−  少なくとも前記補正されたデータフローグラフから前記コンピュータプログラム表現のコンパイルを得る、
ように構成される。
２．コンパイラ装置であって、
−  コンピュータプログラム表現を受信するように構成された入力インターフェース１１０と、
−  プロセッサ回路と、
を有し、該プロセッサ回路は、
−  前記コンピュータプログラム表現からデータフローグラフ２０１の表現を得、ここで、該データフローグラフにおけるノードの少なくとも一部がエンコードされたものとして又はエンコードされていないものとしてマーキングされるようにし、
−  補正された又は補正されていないデータフローグラフにおいてフローノード３１２、該フローノードの前のエンコードする又はデコードする演算３２１、及び該フローノードの後の演算ノード３３２を識別し、ここで、前記フローノードはコピーノード又はファイノードとし、
−  前記データフローグラフを、
−  前記演算ノードを前記フローノードの後から削除すると共に前記フローノードの前に１以上の演算ノードを挿入し、
−  挿入された演算ノードを前記エンコードする又はデコードする演算と併合する、
ことにより補正し、
−  少なくとも前記補正されたデータフローグラフから前記コンピュータプログラム表現のコンパイルを得る、
ように構成される。
３．コンパイラ方法６００であって、
−  コンピュータプログラム表現を受信するステップ６１０と、
−  前記コンピュータプログラム表現からデータフローグラフ２０１の表現を得るステップ６２０であって、該データフローグラフにおけるノードの少なくとも一部がエンコードされたものとして又はエンコードされていないものとしてマーキングされるステップ６２０と、
−  前記データフローグラフを、
−  前記データフローグラフにおいてエンコードされているとマーキングされた１以上の出力ノード及びエンコードされていないとマーキングされた１以上の出力ノードを有する部分グラフ２１０を識別し（６３１）、
−  前記部分グラフをエンコードされた第１部分グラフ210.1及びエンコードされていない第２部分グラフ210.2により置換し（６３２）、ここで、前記第１部分グラフはエンコードされた出力ノードのみを有し、前記第２部分グラフはエンコードされていない出力ノードのみを有し、これら第１部分グラフ及び第２部分グラフは前記部分グラフの更なる部分グラフとして得られるものとし、
−  前記第１部分グラフの前にエンコードする演算を表す１以上のノード２２１を挿入して（６３３）該第１部分グラフがエンコードされたデータに対してのみ動作するようにし、及び／又は前記第２部分グラフの前にデコードする演算を表す１以上のノードを挿入して該第２部分グラフがエンコードされていないデータに対してのみ動作するようにする、
ことにより補正するステップ（６３０）と、
−  少なくとも前記補正されたデータフローグラフから前記コンピュータプログラム表現のコンパイルを得るステップ（６４０）と、
を有する。
４．コンパイラ方法６５０であって、
−  コンピュータプログラム表現を受信するステップ６６０と、
−  前記コンピュータプログラム表現からデータフローグラフ２０１の表現を得るステップ６７０であって、該データフローグラフにおけるノードの少なくとも一部がエンコードされたものとして又はエンコードされていないものとしてマーキングされるステップ６７０と、
−  前記データフローグラフを、
−  補正された又は補正されていないデータフローグラフにおいてフローノード３１２、該フローノードの前のエンコードする又はデコードする演算３２１、及び該フローノードの後の演算ノード３３２を識別し（６８１）、ここで、前記フローノードはコピーノード又はファイノードとし、
−  前記演算ノードを前記フローノードの後から削除すると共に該フローノードの前に１以上の演算ノードを挿入し（６８２）、
−  前記挿入された演算ノードを前記エンコードする又はデコードする演算と併合する（６８３）、
ことにより補正するステップ（６８０）と、
−  少なくとも前記補正されたデータフローグラフから前記コンピュータプログラム表現のコンパイルを得るステップ（６９０）と、
を有する。
【００８９】
本発明はコンピュータプログラムに、特に本発明を実施するように適合化された担体上又は担体内のコンピュータプログラムにも拡張することが理解されるであろう。該プログラムは、ソースコード、オブジェクトコード、中間ソースコード及び部分的にコンパイルされた形態等のオブジェクトコードの形態、又は本発明による方法の実施に使用するのに適した何らかの他の形態とすることができる。コンピュータプログラム製品に関する実施態様は、上述した方法のうちの少なくとも１つの処理ステップの各々に対するコンピュータ実行可能な命令を有する。これらの命令は、サブルーチンに分割することができ、及び／又は静的に又は動的にリンクすることができる１以上のファイルに記憶することができる。コンピュータプログラム製品に関する他の実施態様は、前述したシステム及び／又は製品のうちの少なくとも１つにおける手段の各々に対応するコンピュータ実行可能な命令を有する。
【００９０】
図７ａは、コンピュータプログラム１０２０を含む書込可能部分１０１０を備えたコンピュータ読取可能な媒体１０００を示し、該コンピュータプログラム１０２０はプロセッサシステムに一実施態様によるコンパイル方法を実行させるための命令を有する。コンピュータプログラム１０２０は、コンピュータ読取可能な媒体１０００上に、該コンピュータ読取可能な媒体１０００の物理的マークとして又は磁化により具現化することができる。しかしながら、いずれの他の好適な具現化も同様に考えられる。更に、ここではコンピュータ読取可能な媒体１０００は光ディスクとして示されているが、該コンピュータ読取可能な媒体１０００は、ハードディスク、固体メモリ、フラッシュメモリ等のいずれの好適なコンピュータ読取可能な媒体とすることもでき、記録不可能な又は記録可能なものとすることもできる。コンピュータプログラム１０２０は、プロセッサシステムに前記コンパイル方法を実行させる命令を有する。
【００９１】
図７ｂは、コンパイラ装置の一実施態様によるプロセッサシステム１１４０の概略図を示す。該プロセッサシステムは、１以上の集積回路１１１０を有する。該１以上の集積回路１１１０のアーキテクチャは、図７ｂに概略的に示されている。回路１１１０は、一実施態様による方法を実行する及び／又はそのモジュール若しくはユニットを実施化するためのコンピュータプログラム要素を実行する処理ユニット１１２０（例えば、ＣＰＵ）を有する。回路１１１０はプログラムコード、データ等を記憶するためのメモリ１１２２を有する。メモリ１１２２の一部は読取専用とすることができる。回路１１１０は、例えば、アンテナ、コネクタ又は両方等の通信要素１１２６を有することができる。回路１１１０は、当該方法において定義された処理の一部又は全てを実行するための専用の集積回路１１２４を有することができる。プロセッサ１１２０、メモリ１１２２、専用のＩＣ１１２４及び通信要素１１２６は、相互接続部１１３０（例えば、バス）を介して相互に接続することができる。プロセッサシステム１１１０は、アンテナ及び／又はコネクタを各々用いて接触型及び／又は無接触型通信を行うように構成することができる。
【００９２】
例えば、一実施態様において、当該コンパイラ装置は、プロセッサ回路及びメモリ回路を有することができ、プロセッサ回路はメモリ回路に記憶されたソフトウェアを実行するように構成される。例えば、該プロセッサ回路は、インテルのCore i7プロセッサ、ARM Cortex-R8等とすることができる。一実施態様において、該プロセッサ回路はARM Cortex M0とすることができる。当該メモリ回路は、ＲＯＭ回路又は不揮発性メモリ（例えば、フラッシュメモリ）とすることができる。該メモリ回路は、揮発性メモリ、例えばＳＲＡＭメモリとすることができる。後者の場合、当該装置は当該ソフトウェアを供給するように構成された不揮発性ソフトウェアインターフェース、例えばハードドライブ、ネットワークインターフェース等を有することができる。
【００９３】
上述した実施態様は本発明を限定するというより解説するものであり、当業者であれば多くの代替実施態様を設計することができることに注意すべきである。
【００９４】
尚、請求項において括弧内に示されるいずれの符号も当該請求項を限定するものと見なしてはならない。動詞“有する”及びその活用形の使用は、請求項に記載されたもの以外の要素又はステップの存在を排除するものではない。単数形の要素は、複数の斯様な要素の存在を排除するものではない。本発明は、幾つかの別個の要素を有するハードウェアにより、及び適切にプログラムされたコンピュータにより実施化することができる。幾つかの手段を列挙する装置の請求項において、これら手段の幾つかは１つの同一品目のハードウェアにより具現化することができる。特定の手段が互いに異なる従属請求項に記載されているという単なる事実は、これら手段の組合せを有利に使用することができないということを示すものではない。
【００９５】
請求項において、括弧内の符号は例示的実施態様の図面における符号又は実施態様の式を示し、かくして、当該請求項の理解容易性を高める。これらの符号は当該請求項を限定するものと見なしてはならない。
【符号の説明】
【００９６】
１００    コンパイラ（コンパイル）装置
１１０    入力インターフェース
１２０    記憶部
１３０    構文解析（解析）部
１３２    データフロー解析器
１３４    エンコード分析器
１４０    修正部
１４２    データフロー分析器
１４４    データフロー補正ユニット
１５０    コンパイルユニット
２００〜２０４    データフローグラフ
２１０    コピー／ファイ部分グラフ
210.1    コピー／ファイ部分グラフ
210.2    コピー／ファイ部分グラフ
２１２〜２１６    コピー又はファイノード
212.1〜216.1    コピー又はファイノード
212.2〜216.2    コピー又はファイノード
２２０    入力ノード
２２１    変換ノード
２２２〜２２６    入力ノード
２２３    変換ノード
２３０    出力ノード
２３１    変換ノード
２３２〜２３６    出力ノード
３００    データフローグラフ
３０１    データフローグラフ
３１０    コピー／ファイ部分グラフ
３１２    ファイノード
３１４    コピーノード
３２０    入力ノード
３２１    変換ノード
３２２，３２４  入力ノード
３２３    ノード
３２５    併合されたノード
３３０    出力ノード
３３２    出力ノード
332.1，332.3    ノード
４１０    ノード
４２０    データ発生器（例えば、センサ）
４２２    エンコード及び暗号化（公開キー：pubK）
４３０    ソフトウェア
４３２    アルゴリズム（evalk）
４４０    ハードウェア
４５０    クラウド
４６０    ソフトウェア（セキュアな環境）
４６２    解読及びデコード
４７０    ハードウェア
４７２    セキュアな要素（秘密キー：pk）
１０００  コンピュータ読取可能な媒体
１０１０  書込可能部分
１０２０  コンピュータプログラム
１１１０  集積回路
１１２０  処理ユニット
１１２２  メモリ
１１２４  専用の集積回路
１１２６  通信要素
１１３０  相互接続部
１１４０  プロセッサシステム
【図１】
2021507391.tif 000004
【図２ａ】
2021507391.tif 000005
【図２ｂ】
2021507391.tif 000006
【図２ｃ】
2021507391.tif 000007
【図２ｄ】
2021507391.tif 000008
【図２ｅ】
2021507391.tif 000009
【図３ａ】
2021507391.tif 000010
【図３ｂ】
2021507391.tif 000011
【図４】
2021507391.tif 000012
【図５】
2021507391.tif 000013
【図６ａ】
2021507391.tif 000014
【図６ｂ】
2021507391.tif 000015
【図６ｃ】
2021507391.tif 000016
【図７ａ】
2021507391.tif 000017
【図７ｂ】
2021507391.tif 000018
【国際調査報告】
2021507391.tif 000019
2021507391.tif 000020