(57)【特許請求の範囲】
【請求項１】
１以上の正当プログラム命令からなるオリジナルプログラムから、正常系での実行結果が前記オリジナルプログラムの実行結果と同一となる難読化プログラムを生成するプログラム難読化装置であって、
前記オリジナルプログラムを記憶している記憶手段と、
前記正常系での実行結果を得るためには不要な偽装処理命令からなる偽装ブロックを少なくとも１つ生成する偽装ブロック生成手段と、
前記オリジナルプログラムに、前記偽装ブロックと、前記偽装ブロックを迂回するように制御する制御命令とを挿入する偽装ブロック挿入手段とを備え、
前記偽装ブロック挿入手段は、前記偽装ブロック生成手段にて生成される少なくとも１つの偽装ブロックに分岐命令を挿入する
ことを特徴とするプログラム難読化装置。
【請求項２】
前記オリジナルプログラムは、秘匿すべき被秘匿情報を含む秘匿処理命令群を含み、
前記プログラム難読化装置は、さらに、
複数の処理命令であって、定められた処理順序に従った処理が行われると最後の処理により、前記秘匿処理命令群による処理と同一の結果が得られる複数の処理命令を生成する処理命令生成手段と、
前記秘匿処理命令群に代えて、前記オリジナルプログラムの開始から前記秘匿処理命令群が出現するまでの間に、前記複数の処理命令のそれぞれを、前記処理順序で実行されるように挿入する処理命令挿入手段とを備え、
前記偽装ブロック生成手段は、前記複数の処理命令を攪乱する偽装ブロックを少なくとも１つ生成する
ことを特徴とする請求項１に記載のプログラム難読化装置。
【請求項３】
前記偽装ブロック挿入手段は、前記偽装ブロックに、前記正常系にて実行される実行プログラム命令、及び他の偽装ブロックに含まれる偽装処理命令の何れかを分岐先とする分岐命令を挿入する
ことを特徴とする請求項２に記載のプログラム難読化装置。
【請求項４】
前記実行プログラム命令は、
前記正当プログラム命令および前記処理命令の何れかである
ことを特徴とする請求項３に記載のプログラム難読化装置。
【請求項５】
前記秘匿処理命令群は、演算対象として前記被秘匿情報を含む秘匿演算式であり、
前記処理命令は、秘密変数に対して演算結果を代入する演算式であり、
前記偽装処理命令は、前記秘密変数を演算対象とする偽装演算式であり、
前記処理命令生成手段は、定められた処理順序に従った演算が行われると最後の演算により、前記秘匿演算式による演算と同一の値が得られる複数の演算式を生成し、
前記処理命令挿入手段は、
前記オリジナルプログラムが含む被秘匿情報を前記秘密変数へ置換する置換部と、
前記オリジナルプログラムの開始から前記秘匿処理命令群が出現するまでの間に、前記複数の演算式のそれぞれを、前記演算順序で実行されるように挿入する挿入部と
を備えることを特徴とする請求項２に記載のプログラム難読化装置。
【請求項６】
前記オリジナルプログラムは、１以上の前記正当プログラム命令を含む複数のオリジナルブロックが実行順序で並べられており、
前記処理命令挿入手段は、
前記複数の処理命令のそれぞれを、最初に実行されるオリジナルブロックから前記秘匿処理命令群を有するオリジナルブロックまでの何れかに挿入し、
前記偽装ブロック挿入手段は、
前記複数のオリジナルブロック、及び前記偽装ブロックのそれぞれをノードとし、前記オリジナルブロックの実行順序と、前記オリジナルブロックに含まれる分岐命令と、前記偽装ブロックに含まれる分岐命令とに基づいて、グラフを生成する第１生成部と、
生成したグラフの難易度が、所定の条件を満たすか否かを判定する判定部と、
所定の条件を満たすと判定する場合に、前記偽装ブロックと前記制御命令とを前記オリジナルプログラムに挿入し、所定の条件を満たさないと判断する場合には、前記複数のオリジナルブロック、及び他の偽装ブロックのうち１のブロックを分岐先とする条件分岐命令を、１の偽装ブロックに挿入する第２生成部と、
前記所定の条件を満たすまで、前記第１生成部と前記判定部と前記第２生成部による処理を行うように制御する制御部と
を備えることを特徴とする請求項２に記載のプログラム難読化装置。
【請求項７】
前記プログラム難読化装置は、さらに、
難読化の強度の指定を受け付ける受付手段を備え、
前記所定の条件を満たすとは、ノード間を結ぶエッジの数と、ノード数とから算出される値（エッジ数）−（ノード数）が、指定された前記強度に応じたグラフの難易度にて定まる所定数以上であることであり、
前記判定部は、前記第１生成部にて生成されたグラフから、エッジ数とノード数とを取得し、値（エッジ数）−（ノード数）が、前記所定数以上であるか否かを判定する
ことを特徴とする請求項６に記載のプログラム難読化装置。
【請求項８】
前記プログラム難読化装置は、さらに、
難読化の強度の指定を受け付ける受付手段を備え、
前記所定の条件を満たすとは、グラフにおける閉路の数が、指定された前記強度に応じたグラフの難易度にて定まる所定数以上であることであり、
前記判定部は、前記第１生成部にて生成されたグラフから閉路数を取得し、取得した閉路数が、前記所定数以上であるか否かを判定する
ことを特徴とする請求項６に記載のプログラム難読化装置。
【請求項９】
前記所定の条件を満たすとは、グラフが平面グラフでないことであり、
前記判定部は、前記第１生成部にて生成されたグラフが平面グラフであるか否かを判定し、平面グラフでないと判定する場合に、前記所定の条件を満たすとする
ことを特徴とする請求項６に記載のプログラム難読化装置。
【請求項１０】
前記プログラム難読化装置は、さらに、
難読化の強度の指定を受け付ける受付手段を備え、
前記所定の条件を満たすとは、第１の所定数以上のノード数からなる閉路の数が、ユ指定された前記強度に応じたグラフの難易度にて定まる第２の所定数以上であることであり、
前記判定部は、前記第１生成部にて生成されたグラフから、第１の所定数以上のノード数からなる閉路の数を取得し、取得した閉路数が、前記第２所定数以上であるか否かを判定する
ことを特徴とする請求項６に記載のプログラム難読化装置。
【請求項１１】
前記偽装ブロック挿入手段は、
前記オリジナルブロックに対して、前記演算式が前記演算順位で実行された場合に真偽値が一定値となる比較式を含み、前記比較式により真偽値が前記一定値となる場合の分岐先を次に実行する次オリジナルブロックとする条件分岐命令を、前記オリジナルブロックに挿入し、
前記偽装ブロックが、前記オリジナルブロックの直後に挿入された場合には、前記条件分岐命令を前記制御命令とする
ことを特徴とする請求項６に記載のプログラム難読化装置。
【請求項１２】
前記オリジナルプログラムは、１以上の前記正当プログラム命令を含む複数のオリジナルブロックが実行順序で並べられており、
前記処理命令挿入手段は、
前記複数の処理命令のそれぞれを、最初に実行されるオリジナルブロックから前記秘匿処理命令群を有するオリジナルブロックまでの何れかに挿入し、
前記偽装ブロック挿入手段は、
前記複数のオリジナルブロック、及び前記偽装ブロックのそれぞれをノードとし、前記オリジナルブロックの実行順序と、前記オリジナルブロックに含まれる分岐命令と、前記偽装ブロックに含まれる分岐命令とに基づいて、グラフを生成する第１生成部と、
生成したグラフの強度が、所定の条件を満たすか否かを判定する判定部と、
所定の条件を満たすと判定する場合に、前記偽装ブロックと前記制御命令とを前記オリジナルプログラムに挿入し、所定の条件を満たさないと判断する場合には、前記複数のオリジナルブロック、及び他の偽装ブロックのうち１のブロックを分岐先とする条件分岐命令を、１の偽装ブロックに挿入する、又は１のオリジナルブロックに、１の偽装ブロックを分岐先とし、常に前記分岐先には分岐しない条件分岐命令を前記オリジナルブロックに挿入する第２生成部と、
前記所定の条件を満たすまで、前記第１生成部と前記判定部と前記第２生成部を行うように制御する制御部と
を備えることを特徴とする請求項２に記載のプログラム難読化装置。
【請求項１３】
前記処理命令生成手段は、
前記処理順序で実行した場合のみに、前記秘匿処理命令群による処理と同一の結果が得られるように、前記複数の処理命令を生成する
ことを特徴とする請求項２に記載のプログラム難読化装置。
【請求項１４】
前記偽装ブロック挿入手段は、
前記オリジナルプログラムを、１以上の正当プログラム命令からなる複数の分割ブロックに分割する分割部と、
前記オリジナルプログラムにおいて最後に実行される正当プログラム命令を含む分割ブロックを除く１以上の分割ブロックのそれぞれから、分割ブロックに、次に実行する分割ブロックを示す分岐命令を含む被入替ブロックを生成する被入替ブロック生成部と、
前記オリジナルプログラムにおいて最初に実行される正当プログラム命令を含む被入替ブロックを除く他の被入替ブロックのそれぞれと、前記オリジナルプログラムにおいて最後に実行される正当プログラム命令を含む分割ブロックとの配置順序を入れ替えるブロック入替部と、
前記偽装ブロックを前記オリジナルプログラムに挿入する挿入部とを備え、
前記偽装ブロックが挿入された直前に位置する被入替ブロックに含まれる分岐命令を前記制御命令とする
ことを特徴とする請求項１に記載のプログラム難読化装置。
【請求項１５】
前記分割部は、さらに、
前記偽装ブロックを、１以上のプログラム命令からなる複数の偽装分割ブロックに分割し、
前記被入替ブロック生成部は、さらに、
前記偽装分割ブロックのそれぞれから、偽装分割ブロックに、他の偽装分割ブロックを示す分岐命令を含む偽装被入替ブロックを生成し、
前記挿入部は、
前記偽装被入替ブロックのそれぞれを前記オリジナルプログラムに挿入する
ことを特徴とする請求項１４に記載のプログラム難読化装置。
【請求項１６】
前記被入替ブロック生成部は、さらに、
前記偽装ブロックから、前記偽装ブロックに、１の分割ブロック又は他の偽装ブロックを示す分岐命令を含む偽装被入替ブロックを生成し、
前記挿入部は、
前記偽装被入替ブロックのそれぞれを前記オリジナルプログラムに挿入する
ことを特徴とする請求項１４に記載のプログラム難読化装置。
【請求項１７】
前記オリジナルプログラムは、１以上の前記正当プログラム命令を含む複数の分割ブロックに予め分割され、前記複数の分割ブロックが実行順序で並べられており、
前記処理命令挿入手段は、最初に実行される分割ブロックから前記秘匿処理命令群を有する分割ブロックまでの間に、前記複数の処理命令のそれぞれを挿入し、
前記偽装ブロック挿入手段は、
前記オリジナルプログラムにおいて最後に実行される正当プログラム命令を含む分割ブロックを除く１以上の分割ブロックのそれぞれから、分割ブロックに、次に実行する分割ブロックを示す分岐命令を含む被入替ブロックを生成する被入替ブロック生成部と、
前記オリジナルプログラムにおいて最初に実行される正当プログラム命令を含む被入替ブロックを除く他の被入替ブロックのそれぞれと、前記オリジナルプログラムにおいて最後に実行される正当プログラム命令を含む分割ブロックとの配置順序を入れ替えるブロック入替部と、
前記偽装ブロックを前記オリジナルプログラムに挿入する挿入部とを備え、
前記偽装ブロックが挿入された直前に位置する被入替ブロックに含まれる分岐命令を前記制御命令とする
ことを特徴とする請求項２に記載のプログラム難読化装置。
【請求項１８】
前記被入替ブロック生成部は、さらに、
前記偽装ブロックから、前記偽装ブロックに、１の分割ブロック又は他の偽装ブロックを示す分岐命令を含む偽装被入替ブロックを生成し、
前記挿入部は、
前記偽装被入替ブロックのそれぞれを前記オリジナルプログラムに挿入する
ことを特徴とする請求項１７に記載のプログラム難読化装置。
【請求項１９】
１以上の正当プログラム命令からなるオリジナルプログラムから、正常系での実行結果が前記オリジナルプログラムの実行結果と同一となる難読化プログラムを生成するプログラム難読化装置で用いられる難読化方法であって、
前記プログラム難読化装置は、
前記オリジナルプログラムを記憶している記憶手段を備え、
前記難読化方法は、
前記正常系での実行結果を得るためには不要な偽装処理命令からなる偽装ブロックを少なくとも１つ生成する偽装ブロック生成ステップと、
前記オリジナルプログラムに、前記偽装ブロックと、前記偽装ブロックを迂回するように制御する制御命令とを挿入する偽装ブロック挿入ステップとを含み、
前記偽装ブロック挿入ステップは、前記偽装ブロック生成ステップにて生成される少なくとも１つの偽装ブロックに分岐命令を挿入する
ことを特徴とする難読化方法。
【請求項２０】
１以上の正当プログラム命令からなるオリジナルプログラムから、正常系での実行結果が前記オリジナルプログラムの実行結果と同一となる難読化プログラムを生成するプログラム難読化装置で用いられる難読化プログラム生成プログラムであって、
前記プログラム難読化装置は、
前記オリジナルプログラムを記憶している記憶手段を備え、
前記難読化方法は、
前記正常系での実行結果を得るためには不要な偽装処理命令からなる偽装ブロックを少なくとも１つ生成する偽装ブロック生成ステップと、
前記オリジナルプログラムに、前記偽装ブロックと、前記偽装ブロックを迂回するように制御する制御命令とを挿入する偽装ブロック挿入ステップとを含み、
前記偽装ブロック挿入ステップは、前記偽装ブロック生成ステップにて生成される少なくとも１つの偽装ブロックに分岐命令を挿入する
ことを特徴とする難読化プログラム生成プログラム。
【請求項２１】
前記難読化プログラム生成プログラムは、コンピュータ読み取り可能な記録媒体に記録されていることを特徴とする請求項２０に記載の難読化プログラム生成プログラム。
【請求項２２】
１以上の正当プログラム命令からなるオリジナルプログラムから、正常系での実行結果が前記オリジナルプログラムの実行結果と同一となる難読化プログラムを生成するプログラム難読化装置の集積回路であって、
前記オリジナルプログラムを記憶している記憶手段と、
前記正常系での実行結果を得るためには不要な偽装処理命令からなる偽装ブロックを少なくとも１つ生成する偽装ブロック生成手段と、
前記オリジナルプログラムに、前記偽装ブロックと、前記偽装ブロックを迂回するように制御する制御命令とを挿入する偽装ブロック挿入手段とを備え、
前記偽装ブロック挿入手段は、前記偽装ブロック生成手段にて生成される少なくとも１つの偽装ブロックに分岐命令を挿入する
ことを特徴とする集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密情報を保持して実行するプログラムを、秘密情報を不正に解析することを困難にするプログラムに変換する技術に関する。
【背景技術】
【０００２】
従来、暗号鍵などの被秘匿情報を扱うプログラムの不正な解析／改ざんを防止するための方法としてプログラムの制御構造／処理などを元のプログラムとは異なる形式に変換して、解析困難なプログラムにするプログラム難読化の方法が考えられている（例えば非特許文献１参照）。ここで、被秘匿情報とは、第三者には知られたくない情報である。
非特許文献１において、例えば、プログラムの出力結果に影響を与えない複製生成型偽装コードの挿入を行い、難読化プログラムを生成する方法が開示されている。
【０００３】
ここで、擬似分岐命令と偽装ブロックの挿入による難読化プログラムの生成方法について説明する。
難読化前のオリジナルのプログラムは、命令群１、命令群２、及び命令群３から構成されており、３つの命令群を順に実行するものとする。
この難読化方法では、オリジナルプログラムに、オリジナルプログラムの実行とは無関係なダミー変数を追加し、ダミー変数の値を書き換えるようなプログラム命令群を実行コード中にいくつか挿入する。また、ダミー変数の値によって分岐先が決定する擬似分岐命令が、命令群１と命令群２との間に追加される。この際、擬似分岐命令は、プログラム実行時に決定するダミー変数の値によって必ず真偽が一定の値（例えば、常に「真」となる値）となる分岐条件を設定しておく。さらに、分岐の条件が真となる場合の分岐先を命令群２とし、分岐の条件が偽となる場合の分岐先を偽装ブロックとする。
【０００４】
このように難読化されたプログラムは、命令群１、擬似分岐命令、命令群２、命令群３の順に実行される。追加された偽装ブロックは、プログラム中に存在するがデバッガ等を用いてプログラムカウンターを強制的に変更する等の特別な操作を行わない正常系の実行時には実行されることはない。
また、擬似分岐命令の挿入による難読化プログラムの生成方法について説明する。
【０００５】
難読化前のオリジナルのプログラムは、命令群１、命令群２、及び命令群３から構成されており、３つの命令群を順に実行するものとする。
この方法では、オリジナルプログラムにダミー変数を追加する。次に、ダミー変数の値によって分岐先が決定する擬似分岐命令を命令群１と命令群２との間に追加する。この際、擬似分岐命令は、プログラム実行時に決定するダミー変数の値によって必ず真偽が一定の値（例えば、常に「真」となる値）となる分岐条件を設定する。このとき、分岐の条件が真となる場合の分岐先を命令群２とし、分岐の条件が偽となる場合の分岐先を命令群３とする。
【０００６】
このように難読化されたプログラムは、命令群１、擬似分岐命令、命令群２、命令群３の順に実行される。
非特許文献１では、以上に述べたような難読化を行うことで、プログラムからアルゴリズムを推定することが困難になること、特定モジュールの位置の推定が困難になることが開示されている。例えば、暗号アルゴリズムのプログラムから暗号鍵を不正な解析から保護したい場合には、暗号アルゴリズムのモジュール位置の推定を困難にすることができる。
【０００７】
しかし、このような方法を用いてプログラムの制御構造を複雑にした場合でも、プログラム中のどこかには暗号鍵のような被秘匿情報が存在する。よって、プログラム中に存在する定数データを全て収集すれば、その中のいずれかが被秘匿情報となる。
そのため、例えば暗号アルゴリズムの場合では、平文と暗号文の組を入手可能な不正解析者であれば、プログラム中に存在する定数データを暗号鍵と仮定して平文を暗号化して得た暗号文が実際の暗号文と一致するかを調べていけば、いずれ本当の暗号鍵を見つけることができる。
【０００８】
非特許文献１では、さらに、この問題に対し被秘匿情報を含むプログラム命令を、複数のプログラム命令群に置き換えることでプログラムを難読化する方法を述べている。例えば、「ｄ０＝１２３４」というプログラム命令において「１２３４」が被秘匿情報である場合、「ｄ０＝１２３４」というプログラム命令を、「ｄ０＝２３０」、「ｄ０＝ｄ０＋１０００」、「ｄ０＝ｄ０＋４」のようなプログラム命令群に置き換え、これらを分散して配置することが述べられている。このような方法を用いれば、プログラム中に存在する定数データを収集しても、その中から被秘匿情報を見つけることができなくなる。また、被秘匿情報が分割され、生成された複数のプログラム命令を分割秘密と呼ぶ。
【非特許文献１】鴨志田、松本、井上、"耐タンパーソフトウェアの構成手法に関する考察"、ＩＳＥＣ９７−５９
【非特許文献２】Ｊｏｈａｎｎｅｓ  Ｋｏｅｂｌｅｒ，Ｕｗｅ  Ｓｃｈｏｅｎｉｎｇ，Ｊａｃｏｂｏ  Ｔｏｒａｎ，"Ｔｈｅ  Ｇｒａｐｐｈ  Ｉｓｏｍｏｒｐｈｉｓｍ  Ｐｒｏｂｌｅｍ"，  Ｂｉｒｋｈａａｕｓｅｒ，１９９３
【非特許文献３】戸田誠之助、「グラフ同型性判定問題」、日本大学文理学部厳書（２００１年）
【発明の開示】
【発明が解決しようとする課題】
【０００９】
以上に述べたように、従来、被秘匿情報を含む第一のプログラム命令を、これと同等の機能を有する第二のプログラム命令群（ここでは、複数の分割秘密）に置き換える難読化がある。
しかしながら、不正解析者が、分割秘密を用いて難読化されたプログラムから複数の分割秘密を見つけ出すことが考えられる。例えば、第二のプログラム命令群で用いられる変数に着目し、その変数を用いた式を難読化後のプログラムから収集する方法が考えられる。例えば、前述の被秘匿情報「ｄ０＝１２３４」を４つの処理「ｄ０＝２３０」、「ｄ０＝ｄ０＋１０００」、「ｄ０＝ｄ０＋４」に置き換えた場合、不正解析者は、ｄ０と言う変数を用いた処理をプログラム中から収集することで、第二のプログラム命令群を構成する分割秘密を見つけ出し、見つけ出した複数の分割秘密から被秘匿情報「ｄ０＝１２３４」を取得することができる。
【００１０】
そこで、本発明は、不正解析者が容易に被秘匿情報を取得することができない難読化プログラムを生成するプログラム難読化装置及び難読化方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、本発明は、１以上の正当プログラム命令からなり、秘匿すべき被秘匿情報を含む秘匿処理命令群を含むオリジナルプログラムからプログラム解析が困難であるプログラムを生成するプログラム難読化装置であって、前記オリジナルプログラムを記憶している記憶手段と、複数の処理命令であって、定められた処理順序に従った処理が行われると最後の処理により、前記秘匿処理命令群による処理と同一の結果が得られる複数の処理命令を生成する処理命令生成手段と、前記秘匿処理命令群に代えて、前記オリジナルプログラムの開始から前記秘匿処理命令群が出現するまでの間に、前記複数の処理命令のそれぞれを、前記処理順序で実行されるように挿入する処理命令挿入手段と、前記複数の処理命令を攪乱する偽装処理命令を含む偽装ブロックを少なくとも１つ生成する偽装ブロック生成手段と、前記オリジナルプログラムに、前記偽装ブロックと、前記偽装ブロックを迂回するように制御する制御命令とを挿入する偽装ブロック挿入手段とを備えることを特徴とする。
【発明の効果】
【００１２】
上記に示した構成によると、プログラム難読化装置は、偽装処理命令を含む偽装ブロックを、オリジナルプログラムに挿入するので、オリジナルプログラムの不正解析者が複数の処理命令を見つけ出してもその中に偽装処理命令が含まれているため、被秘匿情報を得るために必要な複数の処理命令を取得することは困難となる。つまり、不正解析者が、容易に被秘匿情報を取得することができない。
【００１３】
ここで、前記秘匿処理命令群は、演算対象として前記被秘匿情報を含む秘匿演算式であり、前記処理命令は、秘密変数に対して演算結果を代入する演算式であり、前記偽装処理命令は、前記秘密変数を演算対象とする偽装演算式であり、前記処理命令生成手段は、定められた処理順序に従った演算が行われると最後の演算により、前記秘匿演算式による演算と同一の値が得られる複数の演算式を生成し、前記処理命令挿入手段は、前記オリジナルプログラムが含む被秘匿情報を前記秘密変数へ置換する置換部と、前記オリジナルプログラムの開始から前記秘匿処理命令群が出現するまでの間に、前記複数の演算式のそれぞれを、前記演算順序で実行されるように挿入する挿入部とを備えるとしてもよい。
【００１４】
この構成によると、プログラム難読化装置は、偽装演算式を含む偽装ブロックを、オリジナルプログラムに挿入するので、オリジナルプログラムの不正解析者が複数の演算式を見つけ出してもその中に偽装演算式が含まれているため、被秘匿情報を得るために必要な複数の演算式を取得することは困難となる。つまり、不正解析者が、容易に被秘匿情報を取得することができない。
【００１５】
ここで、前記偽装ブロック挿入手段は、前記偽装ブロック生成手段にて生成される少なくとも１の偽装ブロックに、前記正当プログラム命令、前記処理命令及び他の偽装ブロックの何れかを分岐先とする分岐命令を挿入するとしてもよい。
この構成によると、プログラム難読化装置は、１の偽装ブロックに、前記１の偽装ブロックから、オリジナルプログラムに含まれる正当プログラム命令、及び他の偽装ブロックの何れに分岐する分岐命令を挿入するので、オリジナルプログラムの解析を困難にすることができる。
【００１６】
ここで、前記オリジナルプログラムは、１以上の前記正当プログラム命令を含む複数のオリジナルブロックが実行順序で並べられており、前記処理命令挿入手段は、前記複数の処理命令のそれぞれを、最初に実行されるオリジナルブロックから前記秘匿処理命令群を有するオリジナルブロックまでの何れかに挿入し、前記偽装ブロック挿入手段は、前記複数のオリジナルブロック、及び前記偽装ブロックのそれぞれをノードとし、前記オリジナルブロックの実行順序と、前記オリジナルブロックに含まれる分岐命令と、前記偽装ブロックに含まれる分岐命令とに基づいて、グラフを生成する第１生成部と、生成したグラフの難易度が、所定の条件を満たすか否かを判定する判定部と、所定の条件を満たすと判定する場合に、前記偽装ブロックと前記制御命令とを前記オリジナルプログラムに挿入し、所定の条件を満たさないと判断する場合には、前記複数のオリジナルブロック、及び他の偽装ブロックのうち１のブロックを分岐先とする条件分岐命令を、１の偽装ブロックに挿入する第２生成部と、前記所定の条件を満たすまで、前記第１生成部と前記判定部と前記第２生成部による処理を行うように制御する制御部とを備えるとしてもよい。
【００１７】
この構成によると、プログラム難読化装置は、偽装ブロックが挿入されたオリジナルプログラムからグラフを生成するので、偽装ブロックが挿入されたオリジナルプログラムを部分グラフ同型問題として扱うことができる。部分グラフ同型問題において、与えられた２つのグラフ（部分グラフと全体グラフ）があるとき、全体グラフから部分グラフを見つけ出すことが困難であることが知られている。これにより、偽装ブロックが挿入されたオリジナルプログラムからグラフから、偽装ブロックが挿入されていないオリジナルプログラムを見つけ出すことが困難になる。
【００１８】
ここで、前記プログラム難読化装置は、さらに、難読化の強度の指定を受け付ける受付手段を備え、前記所定の条件を満たすとは、ノード間を結ぶエッジの数と、ノード数とから算出される値（エッジ数）−（ノード数）が、指定された前記強度に応じたグラフの難易度にて定まる所定数以上であることであり、前記判定部は、前記第１生成部にて生成されたグラフから、エッジ数とノード数とを取得し、値（エッジ数）−（ノード数）が、前記所定数以上であるか否かを判定するとしてもよい。
【００１９】
この構成によると、プログラム難読化装置は、グラフの強度の基準として、値（エッジ数）−（ノード数）を用いて、グラフ生成をすることができる。
ここで、前記プログラム難読化装置は、さらに、難読化の強度の指定を受け付ける受付手段を備え、前記所定の条件を満たすとは、グラフにおける閉路の数が、指定された前記強度に応じたグラフの難易度にて定まる所定数以上であることであり、前記判定部は、前記第１生成部にて生成されたグラフから閉路数を取得し、取得した閉路数が、前記所定数以上であるか否かを判定するとしてもよい。
【００２０】
この構成によると、プログラム難読化装置は、グラフの強度の基準として、閉路数を用いて、グラフ生成をすることができる。
ここで、前記所定の条件を満たすとは、グラフが平面グラフでないことであり、前記判定部は、前記第１生成部にて生成されたグラフが平面グラフであるか否かを判定し、平面グラフでないと判定する場合に、前記所定の条件を満たすとするとしてもよい。
【００２１】
この構成によると、プログラム難読化装置は、グラフの強度の基準を、平面グラフでないことを用いて、グラフ生成をすることができる。
ここで、前記プログラム難読化装置は、さらに、難読化の強度の指定を受け付ける受付手段を備え、前記所定の条件を満たすとは、第１の所定数以上のノード数からなる閉路の数が、ユ指定された前記強度に応じたグラフの難易度にて定まる第２の所定数以上であることであり、前記判定部は、前記第１生成部にて生成されたグラフから、第１の所定数以上のノード数からなる閉路の数を取得し、取得した閉路数が、前記第２所定数以上であるか否かを判定するとしてもよい。
【００２２】
この構成によると、プログラム難読化装置は、グラフの強度の基準として、閉路数を用いて、グラフ生成をすることができる。
ここで、前記偽装ブロック挿入手段は、前記オリジナルブロックに対して、前記演算式が前記演算順位で実行された場合に真偽値が一定値となる比較式を含み、前記比較式により真偽値が前記一定値となる場合の分岐先を次に実行する次オリジナルブロックとする条件分岐命令を、前記オリジナルブロックに挿入し、前記偽装ブロックが、前記オリジナルブロックの直後に挿入された場合には、前記条件分岐命令を前記制御命令とするとしてもよい。
【００２３】
この構成によると、プログラム難読化装置は、真偽値が一定値となる条件分岐命令をオリジナルブロックに挿入することにより、オリジナルプログラムの解析を困難にすることができる。
ここで、前記オリジナルプログラムは、１以上の前記正当プログラム命令を含む複数のオリジナルブロックが実行順序で並べられており、前記処理命令挿入手段は、前記複数の処理命令のそれぞれを、最初に実行されるオリジナルブロックから前記秘匿処理命令群を有するオリジナルブロックまでの何れかに挿入し、前記偽装ブロック挿入手段は、前記複数のオリジナルブロック、及び前記偽装ブロックのそれぞれをノードとし、前記オリジナルブロックの実行順序と、前記オリジナルブロックに含まれる分岐命令と、前記偽装ブロックに含まれる分岐命令とに基づいて、グラフを生成する第１生成部と、生成したグラフの強度が、所定の条件を満たすか否かを判定する判定部と、所定の条件を満たすと判定する場合に、前記偽装ブロックと前記制御命令とを前記オリジナルプログラムに挿入し、所定の条件を満たさないと判断する場合には、前記複数のオリジナルブロック、及び他の偽装ブロックのうち１のブロックを分岐先とする条件分岐命令を、１の偽装ブロックに挿入する、又は１のオリジナルブロックに、１の偽装ブロックを分岐先とし、常に前記分岐先には分岐しない条件分岐命令を前記オリジナルブロックに挿入する第２生成部と、前記所定の条件を満たすまで、前記第１生成部と前記判定部と前記第２生成部を行うように制御する制御部とを備えるとしてもよい。
【００２４】
この構成によると、プログラム難読化装置は、偽装ブロックが挿入されたオリジナルプログラムからグラフを生成するので、偽装ブロックが挿入されたオリジナルプログラムを部分グラフ同型問題として扱うことができる。これにより、偽装ブロックが挿入されたオリジナルプログラムからグラフから、偽装ブロックが挿入されていないオリジナルプログラムを見つけ出すことが困難になる。
【００２５】
ここで、処理命令生成手段は、前記処理順序で実行した場合のみに、前記秘匿処理命令群による処理と同一の結果が得られるように、前記複数の処理命令を生成するとしてもよい。
この構成によると、プログラム難読化装置にて生成された前記複数の演算式は、正しい演算順序で実行した場合にのみ前記被秘匿情報を算出するので、不正解析者は、正しい演算順序を得ない限り、被秘匿情報を取得することができない。つまり、プログラム難読化装置は、オリジナルプログラムの解析を困難にすることができる。
【００２６】
ここで、前記偽装ブロック挿入手段は、前記オリジナルプログラムを、１以上の正当プログラム命令からなる複数の分割ブロックに分割する分割部と、前記オリジナルプログラムにおいて最後に実行される正当プログラム命令を含む分割ブロックを除く１以上の分割ブロックのそれぞれから、分割ブロックに、次に実行する分割ブロックを示す分岐命令を含む被入替ブロックを生成する被入替ブロック生成部と、前記オリジナルプログラムにおいて最初に実行される正当プログラム命令を含む被入替ブロックを除く他の被入替ブロックのそれぞれと、前記オリジナルプログラムにおいて最後に実行される正当プログラム命令を含む分割ブロックとの配置順序を入れ替えるブロック入替部と、前記偽装ブロックを前記オリジナルプログラムに挿入する挿入部とを備え、前記偽装ブロックが挿入された直前に位置する被入替ブロックに含まれる分岐命令を前記制御命令とするとしてもよい。
【００２７】
この構成によると、プログラム難読化装置は、オリジナルプログラムの先頭に位置する分割ブロックを除く他の分割ブロックの位置を入れ替えるので、オリジナルプログラムの解析を困難にすることができる。
ここで、前記分割部は、さらに、前記偽装ブロックを、１以上のプログラム命令からなる複数の偽装分割ブロックに分割し、前記被入替ブロック生成部は、さらに、前記偽装分割ブロックのそれぞれから、偽装分割ブロックに、他の偽装分割ブロックを示す分岐命令を含む偽装被入替ブロックを生成し、前記挿入部は、前記偽装被入替ブロックのそれぞれを前記オリジナルプログラムに挿入するとしてもよい。
【００２８】
この構成によると、プログラム難読化装置は、偽装ブロックを構成する１以上の偽装分割ブロックのそれぞれを前記オリジナルプログラムに挿入するので、オリジナルプログラムの解析を困難にすることができる。
ここで、前記被入替ブロック生成部は、さらに、前記偽装ブロックから、前記偽装ブロックに、１の分割ブロック又は他の偽装ブロックを示す分岐命令を含む偽装被入替ブロックを生成し、前記挿入部は、前記偽装被入替ブロックのそれぞれを前記オリジナルプログラムに挿入するとしてもよい。
【００２９】
この構成によると、プログラム難読化装置は、偽装ブロックを前記オリジナルプログラムに挿入するので、オリジナルプログラムの解析を困難にすることができる。
ここで、前記オリジナルプログラムは、１以上の前記正当プログラム命令を含む複数の分割ブロックに予め分割され、前記複数の分割ブロックが実行順序で並べられており、前記処理命令挿入手段は、最初に実行される分割ブロックから前記秘匿処理命令群を有する分割ブロックまでの間に、前記複数の処理命令のそれぞれを挿入し、前記偽装ブロック挿入手段は、前記オリジナルプログラムにおいて最後に実行される正当プログラム命令を含む分割ブロックを除く１以上の分割ブロックのそれぞれから、分割ブロックに、次に実行する分割ブロックを示す分岐命令を含む被入替ブロックを生成する被入替ブロック生成部と、前記オリジナルプログラムにおいて最初に実行される正当プログラム命令を含む被入替ブロックを除く他の被入替ブロックのそれぞれと、前記オリジナルプログラムにおいて最後に実行される正当プログラム命令を含む分割ブロックとの配置順序を入れ替えるブロック入替部と、前記偽装ブロックを前記オリジナルプログラムに挿入する挿入部とを備え、前記偽装ブロックが挿入された直前に位置する被入替ブロックに含まれる分岐命令を前記制御命令とするとしてもよい。
【００３０】
この構成によると、プログラム難読化装置は、オリジナルプログラムの先頭に位置する分割ブロックを除く他の分割ブロックの位置を入れ替えるので、オリジナルプログラムの解析を困難にすることができる。
【発明を実施するための最良の形態】
【００３１】
１．第１の実施の形態
以下、本発明に係る第１の実施の形態としてのプログラム難読化装置１０について、図面を参照して説明する。
１．１  プログラム難読化装置１０の構成
プログラム難読化装置１０は、図１に示すように、記憶部１００、入力部１０１、ブロック分割部１０２、等価プログラム命令生成部１０３、等価プログラム生成部１０４、偽装ブロック挿入後プログラム生成部１０５、擬似分岐命令挿入後プログラム生成部１０６、被入替ブロック群生成部１０７、配置順序入替部１０８から構成される。
【００３２】
以下、各構成要素について説明する。以下の説明では、まず、構成要素の動作を説明し、その後、具体的に難読化対象プログラムの一例に対して各構成要素による処理を施した例を示すことでその構成要素をより明確にしていく。
１．１．１  入力部１０１
入力部１０１は、被秘匿情報を保持する難読化対象プログラムと、難読化対象プログラムにおける被秘匿情報を含むプログラム命令の位置を示す位置情報とを受け付ける。
【００３３】
入力部１０１は、受け付けた難読化対象プログラムと位置情報とを、記憶部１００へ格納する。
入力部１０１は、難読対象プログラムの分割を指示する分割命令をブロック分割部１０２へ出力する。
ここで、難読化対象プログラムは、例えば、被秘匿情報である暗号鍵を使って暗号文の復号化を行うプログラムである。位置情報は、受け付けた難読化対象プログラムにおける秘密情報を保持するプログラム命令の行番号である。
【００３４】
以下に、具体例を示す。
入力部１０１が受け付ける難読化対象プログラムの一例を図２に示す。
図２において難読化対象プログラム２０１は関数ｆｕｎｃから構成されている。関数ｆｕｎｃは、変数宣言部２０２と、処理部２０３から構成されている。処理群Ａは、実際には反復命令（ｆｏｒ文、ｗｈｉｌｅ文、ｄｏ−ｗｈｉｌｅ文）、選択命令（ｉｆ文、ｓｗｉｔｃｈ文）、無条件分岐命令（ｇｏｔｏ文、ｂｒｅａｋ文、ｃｏｎｔｉｎｕｅ文、ｒｅｔｕｒｎ文）以外のプログラム命令からなるプログラム命令群であり、Ｎ個のプログラム命令である命令ａ＿１、命令ａ＿２、・・・、命令ａ＿Ｎから構成されるが図では簡略化している。命令ａ＿１、命令ａ＿２、・・・、命令ａ＿Ｎは、例えば変数に定数を足すプログラム命令である「ｘ＋＝１０；」などのプログラム命令である。処理群Ｂ、処理群Ｄ、処理群Ｆ、処理群Ｇ、処理群Ｈも同様である。処理群Ｈの最後のプログラム命令は、「ｒｅｔｕｒｎ；」であるとする。なお、Ｃ言語の用語については、公知であるので、詳細な説明は省略する。
【００３５】
処理群Ｃ、処理群Ｅは、含まれる命令数が（Ｎ−１）個である以外は、処理群Ａと同種のプログラム命令から構成されるプログラム命令群である。
処理部２０３には、被秘匿情報を保持するプログラム命令２０４が含まれる。プログラム命令２０４は、この難読化対象プログラム２０１の被秘匿情報「５１２」を含むプログラム命令「ａ＝ｂ＋５１２；」である。
【００３６】
入力部１０１は、難読化対象プログラム２０１と、位置情報（ここでは、プログラム命令２０４の行番号）とを受け取り、受け取った難読化対象プログラム２０１と、位置情報とを記憶部１００へ格納する。
入力部１０１は、難読化対象プログラム２０１の分割を指示する分割命令をブロック分割部１０２へ出力する。
【００３７】
以降、具体例を用いて説明する場合には、難読化対象プログラム２０１を用いて説明する。
１．１．２  記憶部１００
記憶部１００は、入力部１０１にて受け付けた難読化対象プログラムと、位置情報とを記憶している。
【００３８】
具体的には、記憶部１００は、入力部１０１にて受け付けた難読化対象プログラム２０１と、この難読化対象プログラム２０１の被秘匿情報「５１２」を含むプログラム命令「ａ＝ｂ＋５１２；」の位置を示す位置情報とを記憶している。
１．１．３  ブロック分割部１０２
ブロック分割部１０２は、入力部１０１から分割命令を受け取ると、記憶部１００に記憶されている難読化対象プログラムを読み出し、読み出した難読化対象プログラムに含まれる処理部を分割して、１以上の分割後ブロックを生成する。
【００３９】
ブロック分割部１０２は、受け取った難読化対象プログラムに含まれる処理部を、１以上の基本ブロックに分割し、その後、分割した基本ブロックのそれぞれを、詳細に分割して、１以上の分割後ブロックを生成する。ここで、基本ブロックは、１以上のプログラム命令からなるプログラム命令群であって、プログラム命令群の先頭以外では他のプログラム命令群とは合流せず、プログラム命令群の最後以外では他のプログラム命令群へ分岐しないプログラム命令群である。なお、コンパイラに関する用語についての詳細な説明は省略する。
【００４０】
（１）基本ブロックの生成
ブロック分割部１０２は、入力部１０１から、難読化対象プログラムを受け取ると、受け取った難読化対象プログラムに含まれる処理部を、１以上の基本ブロックに分割する。ここで、基本ブロックとは、開始位置が、処理部の先頭（難読化対象プログラムの入口のプログラム命令、つまり、難読化対象プログラムの一番最初に実行されるプログラム命令）、処理が合流するプログラム命令、または、分岐となるプログラム命令の次のプログラム命令であり、終了位置が、次に処理が合流するプログラム命令の一つ前のプログラム命令、処理部の最後（プログラムの出口の命令、つまり、難読化対象プログラムの一番最後に実行されるプログラム命令）、または、分岐となるプログラム命令であるブロックである。
【００４１】
なお、基本ブロック生成に関するより詳細については、コンパイラの分野で公知であるためここでの説明は省略する。
これにより、ブロック分割部１０２は、難読化対象プログラムを分割して複数の基本ブロックを生成することができる。また、難読化対象プログラムを構成する全てのプログラム命令は、ブロック分割部１０２により、いずれかの一つの基本ブロックに含まれるようになる。
【００４２】
（２）分割後ブロックの生成
ブロック分割部１０２は、生成した各基本ブロックを、以下のように分割して、１以上の分割後ブロックを生成する。
ブロック分割部１０２は、基本ブロックに含まれるプログラム命令数ｍ、予め与えられた所定数Ｎとを用いて、基本ブロックを（［（ｍ−１）／Ｎ］＋１）個の分割後ブロックに分割する。分割する際には、各ブロックのプログラム命令数が出来るだけ均等になるようにする。ここで、演算［ａ／ｂ］は、除算ａ／ｂを施し、算出結果から小数点以下を切り捨てた整数を取得する演算式である。例えば、［５／２］＝２となる。
【００４３】
（３）具体例
図３は、図２に示す難読化対象プログラムを、基本ブロックに分割した結果を示す。
図３における基本ブロック３０１ａ〜３０１ｃは、図２の関数ｆｕｎｃの処理部２０３を分割して生成した基本ブロックである。
基本ブロック３０１ａは、関数ｆｕｎｃの入口のプログラム命令（関数の中で一番最初に実行されるプログラム命令）を含む処理群Ａからはじまり、それ以降、最初に出現する条件分岐命令（ｆｏｒ文、ｗｈｉｌｅ文、ｄｏ−ｗｈｉｌｅ文、ｉｆ文、ｓｗｉｔｃｈ文）であるプログラム命令「ｉｆ（条件１）ｇｏｔｏ  ｌａｂｅｌＦ；」までのプログラム命令を含む。ここで、この条件分岐命令を基本ブロック３０１ａの最後にしたのは、基本ブロックはブロックの最後以外では分岐しないためである。
【００４４】
基本ブロック３０１ｂは、基本ブロック３０１ａの最後のプログラム命令の次のプログラム命令からはじまり、それ以降、最初に合流する位置である「ｌａｂｅｌＦ」の直前のプログラム命令「ａ＝ｂ＋５１２；」までのプログラム命令までを含む。ここで、合流位置の直前のプログラム命令を基本ブロック３０１ｂの最後にしたのは、基本ブロックはブロックの先頭以外では合流しないためである。なお、「ｌａｂｅｌＦ：」で合流するとしたのは、「ｌａｂｅｌＦ：」の位置に処理が移動する経路が２つ以上ありうるからである。すなわち、一方は基本ブロック３０１ａの実行後に条件分岐により処理が移動する場合であり、もう一方は、基本ブロック３０１ｂの実行後に処理が移動する場合である。
【００４５】
基本ブロック３０１ｃは、基本ブロック３０１ｂの最後のプログラム命令の次のプログラム命令からはじまり、それ以降、関数ｆｕｎｃの出口となるプログラム命令（関数の中で一番最後に実行されるプログラム命令）までを含む。
次に、図４は、図３に示す各基本ブロックを、分割後ブロックに分割した結果を示す。
処理群Ａ、処理群Ｂ、処理群Ｃを含む基本ブロック３０１ａは、含まれるプログラム命令数の合計が３Ｎ個である。なぜなら、ここでは、処理群Ａ、処理群Ｂに含まれるプログラム命令の個数をそれぞれＮ個と、処理群Ｃに含まれるプログラム命令をＮ−１個としており、基本ブロック３０１ａには、プログラム命令「ｉｆ（条件１）ｇｏｔｏ  ｌａｂｅｌＦ；」が含まれているからである。
【００４６】
基本ブロック３０１ａから生成する分割後ブロック数は、式（[（ｍ−１）／Ｎ]＋１）のｍに３Ｎを代入し３である事がわかる。基本ブロック３０１ａを３つに分割して生成したものが分割後ブロック４０１ａ〜４０１ｃである。
以下、同様に２Ｎ個のプログラム命令を含む基本ブロック３０１ｂを分割し生成した分割後ブロックが、分割後ブロック４０１ｄ〜４０１ｅである。さらに、同様に３Ｎ個のプログラム命令を含む基本ブロック３０１ｃを分割し生成した分割後ブロックが、分割後ブロック４０１ｆ〜４０１ｈである。
【００４７】
なお、本実施例では、基本ブロックを更に分割して分割後ブロックを生成する構成を示したが、基本ブロックそのものを分割後ブロックとして扱っても構わない。
１．１．４  等価プログラム命令生成部１０３
等価プログラム命令生成部１０３は、被秘匿情報を含むプログラム命令と同等の機能を有する命令群を生成する。以降の説明では、この命令群を構成する各命令を等価プログラム命令と呼ぶ。
【００４８】
本実施例では、簡単のため被秘匿情報である定数を、複数のプログラム命令から算出するようなプログラム命令群を生成し、生成したプログラム命令群のそれぞれを等価プログラム命令とする場合を示す。
等価プログラム命令生成部１０３は、等価プログラム命令に使用する変数名（秘密情報用変数名）の決定、グラフ作成、等価プログラム命令の挿入対象ブロックの決定、及び等価プログラム命令挿入対象ブロックに挿入する等価プログラム命令の生成を行う。
【００４９】
（１）秘密情報用変数名の決定
等価プログラム命令生成部１０３は、等価プログラム命令に使用する変数の名前を決定する。
まず、等価プログラム命令生成部１０３は、難読化対象プログラムを解析し、このプログラム中で使用されている全ての変数名を調べる。次に、使用されているいずれの変数名とも重複しない変数名を生成し、生成した変数名を秘密情報用変数名として決定する。
【００５０】
（２）グラフ作成
等価プログラム命令生成部１０３は、難読化対象プログラムの構造を示すグラフを作成する。
等価プログラム命令生成部１０３は、ブロック分割部１０２により生成された分割後ブロックのそれぞれをノードと見なし、第一のノードが第二のノードへの分岐命令（ｇｏｔｏ文、ｂｒｅａｋ文、ｃｏｎｔｉｎｕｅ文、ｒｅｔｕｒｎ文による無条件分岐命令、またはｆｏｒ文、ｗｈｉｌｅ文、ｄｏ−ｗｈｉｌｅ文、ｉｆ文、ｓｗｉｔｃｈ文による条件分岐命令）を含む場合、または、第一のノードの最後のプログラム命令が無条件分岐命令以外のプログラム命令であって、前記最後のプログラム命令に対応するプログラム上のプログラム命令の一つ後のプログラム命令が第二のノードに含まれている場合に、第一のノードと第二のノードの間にはエッジが存在すると見なし、ノードとエッジからなるグラフを生成する。なお、グラフに関する用語については公知であるため、ここでの説明は省略する。グラフ生成に関するより詳細については、コンパイラの分野では公知であるため、ここでの説明は省略する。
【００５１】
このようなグラフにおいて、第一のノードは第二のノードの先行ブロック、第二のノードは第一のノードの後続ブロックと呼ぶ。
さらに、ここでは、位置情報にて示される被秘匿情報を含むプログラム命令が含まれるノードを秘密保有ノードと呼ぶ。また、プログラムの入り口となるプログラム命令（プログラムの一番最初に実行されるプログラム命令）を含むノードを開始ノード、プログラムの出口となるプログラム命令（プログラムの一番最後に実行されるプログラム命令）を含むノードを終了ノードと呼ぶこととする。
【００５２】
（３）等価プログラム命令の挿入対象ブロックの決定
等価プログラム命令生成部１０３は、生成したグラフに基づき、等価プログラム命令を挿入する分割後ブロックを決定する。
等価プログラム命令生成部１０３は、まず、秘密保有ノードに対応するブロックを第１の等価プログラム命令挿入対象ブロックとする。次に、第１の等価プログラム命令挿入対象ブロックの先行ブロックが一つだけであった場合、等価プログラム命令生成部１０３は、その先行ブロックを第２の等価プログラム命令挿入対象ブロックとする。以下、同様に第ｎの等価プログラム命令挿入対象ブロックの先行ブロックが一つだけであった場合、等価プログラム命令生成部１０３は、その先行ブロックを第（ｎ＋１）の等価プログラム命令挿入対象ブロックとする。第ｎの等価プログラム命令挿入対象ブロックの先行ブロックが複数ある場合には、等価プログラム命令生成部１０３は処理を中止し、等価プログラム命令数をｎとする。このステップのいずれの操作においても、等価プログラム命令挿入対象ブロックに選ばれなかった分割後ブロックを、以降、等価プログラム非挿入ブロックと呼ぶ。
【００５３】
このような方法で、等価プログラム命令挿入対象ブロックを決定した場合、デバッガ等を用いてプログラムカウンターを強制的に変更する等の特別な操作を行わない正常系で実行された際において、第１の等価プログラム命令挿入対象ブロックが実行される前には必ず第２の等価プログラム命令挿入対象ブロックが実行されることになる。このことは、第１の等価プログラム命令挿入対象ブロックの先行ブロックが第２の等価プログラム命令挿入対象ブロックのみであることより分る。以下同様に、第（ｎ−１）の等価ブロックが実行される前には必ず第ｎの等価プログラム命令挿入対象ブロックが実行される。まとめると、第１の等価プログラム命令挿入対象ブロックが実行される際には、それ以前に必ず第ｎ、第（ｎ−１）、・・・、第２の等価プログラム命令挿入対象ブロックがこの順番で実行されることが分る。なお、実際に等価プログラム命令を挿入する処理は、等価プログラム生成部１０４にて行われ、その詳細な動作は後述する。
【００５４】
（４）等価プログラム命令の生成
等価プログラム命令生成部１０３は、等価プログラム命令挿入対象ブロックに挿入する等価プログラム命令を生成する。等価プログラム命令生成部１０３は、等価プログラム命令数ｎと同数の等価プログラム命令を生成する。ここでは、等価プログラム命令数をＮとし、以下、第１の等価プログラム命令から第Ｎまでの等価プログラム命令の生成手順を述べる。
【００５５】
（Ａ）第１の等価プログラム命令の生成
等価プログラム命令生成部１０３は、整数ＲＡ＿０をランダムに選択し、選択した整数ＲＡ＿０を秘密情報用変数に設定する第１の等価プログラム命令「（秘密情報用変数）＝ＲＡ＿０；」を生成する。
（Ｂ）第ｔ（ｔ＝２、３、・・・Ｎ−１）の等価プログラム命令の生成
等価プログラム命令生成部１０３は、０以外の整数であるＲＡ＿ｔ、ＲＢ＿ｔをランダムに選択し、選択した０以外の整数ＲＡ＿ｔ、ＲＢ＿ｔと、第ｔの演算子とを用いて、第ｔ（ｔ＝２、３、・・・Ｎ−１）の等価プログラム命令「（秘密情報用変数）＝（秘密情報用変数）（第ｔの演算子）ＲＡ＿ｔ＋ＲＢ＿ｔ；」を生成する。ここで、第ｔの演算子は、掛け算を表す「＊」または割り算を表す「／」のどちらかの演算子であり、どちらにするかはランダムに選択する。
【００５６】
（Ｃ）第Ｎの等価プログラム命令の生成
等価プログラム命令生成部１０３は、０以外の整数であるＲＡ＿Ｎをランダムに選択し、選択した０以外の整数ＲＡ＿Ｎと、第一の値と、演算子「＊」とを用いて、第Ｎの等価プログラム命令「（秘密情報用変数）＝（秘密情報用変数）＊ＲＡ＿Ｎ＋（第一の値）」を生成する。  
【００５７】
ここで、第一の値の算出方法を以下に述べる。
等価プログラム命令生成部１０３は、記憶部１００にて記憶されている位置情報を取得し、取得した位置情報にて示されるプログラム命令に含まれる被秘匿情報の値を取得する。
等価プログラム命令生成部１０３は、第１〜第（Ｎ−１）の等価プログラム命令を順番に並べたプログラム命令群
「（秘密情報用変数）＝ＲＡ＿０；
（秘密情報用変数）＝（秘密情報用変数）（第２の演算子）ＲＡ＿２＋ＲＢ＿２；
（秘密情報用変数）＝（秘密情報用変数）（第３の演算子）ＲＡ＿３＋ＲＢ＿３；
・・・
（秘密情報用変数）＝（秘密情報用変数）（第（Ｎ−１）の演算子）ＲＡ＿（Ｎ−１）＋ＲＢ＿（Ｎ−１）；
」
を実行した際に得られる秘密情報用変数の値を、第二の値として算出する。
【００５８】
等価プログラム命令生成部１０３は、
式１：（第一の値）＝（被秘匿情報の値）―  ｛  （第二の値）＊ＲＡ＿Ｎ  ｝
で得られる値を第一の値とする。
このような方法によって、第１から第Ｎまでの等価プログラム命令を生成した場合、
「（秘密情報用変数）＝ＲＡ＿０；
（秘密情報用変数）＝（秘密情報用変数）（第２の演算子）ＲＡ＿２＋ＲＢ＿２；
（秘密情報用変数）＝（秘密情報用変数）（第３の演算子）ＲＡ＿３＋ＲＢ＿３；
・・・
（秘密情報用変数）＝（秘密情報用変数）（第（Ｎ−１）の演算子）ＲＡ＿（Ｎ−１）＋ＲＢ＿（Ｎ−１）；
（秘密情報用変数）＝（秘密情報用変数）＊ＲＡ＿Ｎ＋（第一の値）；」
からなるプログラム命令群を順に処理した場合、処理の最後で秘密情報用変数は被秘匿情報の値になる。
【００５９】
この生成方法によると、例えば、第ｔの等価プログラム命令と、第（ｔ＋１）の等価プログラム命令とを入れ替えて、第１、２、・・・、ｔ−１、ｔ＋１、ｔ、ｔ＋２、・・・、Ｎの順に等価プログラム命令を実行した値と、第１から第Ｎまでの等価プログラム命令を実行した値とは異なることが分かる。
なお、ここでは等価プログラム命令として、掛け算と足し算とを組み合わせた演算とを示したが、これに限定されない。等価プログラム命令数ｎと同数の等価プログラム命令を用いて、被秘匿情報の値が取得される演算であれば、どのような演算を用いても構わない。
【００６０】
（５）具体例
等価プログラム命令生成部１０３は、まず、図２に示す難読化対象プログラム２０１を用いて、難読化対象プログラム２０１の関数ｆｕｎｃで使用されている引数の変数名、およびの変数宣言部２０２で宣言されている変数名を調べ、これらと重複しない変数名を秘密情報用変数名とする。ここでは、秘密情報用変数名を「ｄｋｅｙ」とする。
【００６１】
次に、等価プログラム命令生成部１０３は、図４に示す分割後ブロック４０１ａ〜４０１ｈを用いて、以下のようにしてグラフＧ１００を生成する。ここでは、分割後ブロック４０１ａ〜４０１ｈのそれぞれを、ノード５０１ａ〜５０１ｈとして説明する。
分割後ブロック４０１ａの最後のプログラム命令は無条件分岐命令ではない。また、分割後ブロック４０１ａの次のプログラム命令は分割後ブロック４０１ｂのプログラム命令である。よって、等価プログラム命令生成部１０３は、ノード５０１ａとノード５０１ｂにエッジ５０２ａを設ける。
【００６２】
同様にして、等価プログラム命令生成部１０３は、エッジ５０２ｂ〜エッジ５０２ｇを設ける。
分割後ブロック４０１ｃには分割後ブロック４０１ｆのラベル「ｌａｂｅｌＦ：」に条件分岐する条件分岐命令「ｉｆ（条件１）  ｇｏｔｏ  ｌａｂｅｌＦ；」がある。よって、等価プログラム命令生成部１０３は、ノード５０１ｃとノード５０１ｆにエッジ５０２ｈを設ける。
【００６３】
等価プログラム命令生成部１０３は、上記の動作を行うことにより、難読化対象プログラム２０１の構造を示すグラフＧ１００を生成する。生成したグラフＧ１００を図５にて示す。
なお、このグラフにおいて、ノード５０１ａは開始ノードであり、ノード５０１ｈは終了ノードであり、ノード５０１ｅは秘密保有ノードである。
【００６４】
次に、等価プログラム命令生成部１０３は、図５に示すグラフＧ１００に基づいて、等価プログラム命令を挿入する分割後ブロックを、以下のようにして決定する。
等価プログラム命令生成部１０３は、秘密保有ノードであるノード５０１ｅに対応する分割後ブロック４０１ｅを第１の等価プログラム命令挿入対象ブロックとする。ノード５０１ｅには先行ブロックはノード５０１ｄのみであるので、等価プログラム命令生成部１０３は、ノード５０１ｄに対応する分割後ブロック４０１ｄを第２の等価プログラム命令挿入対象ブロックとする。以下、同様に、等価プログラム命令生成部１０３は、ノード５０１ｃに対応する分割後ブロック４０１ｃを第３の等価プログラム命令挿入対象ブロック、ノード５０１ｂに対応する分割後ブロック４０１ｂを第４の等価プログラム命令挿入対象ブロック、ノード５０１ａに対応する分割後ブロック４０１ａを第５の等価プログラム命令挿入対象ブロックとする。第5の等価プログラム命令挿入対象ブロックには先行ブロックがないので、等価プログラム命令生成部１０３は、等価プログラム命令数を「５」とする。
【００６５】
次に、等価プログラム命令生成部１０３は、等価プログラム命令数「５」と同数の等価プログラム命令を生成する。ここでは、次に、等価プログラム命令生成部１０３は、第１〜第５の等価プログラム命令を生成する。
等価プログラム命令生成部１０３は、整数「１８」を選択し、第１の等価プログラム命令「ｄｋｅｙ＝１８；」を生成する。
【００６６】
等価プログラム命令生成部１０３は、以下、第２〜第４の等価プログラム命令をそれぞれ決定する。
ここでは、等価プログラム命令生成部１０３は、第２の演算子から第４の演算子をそれぞれ順に、「／」、「＊」、「／」とし、ランダムな値ＲＡ＿２〜ＲＡ＿４をそれぞれ値「２」、値「４」、値「５」とし、ランダムな値ＲＢ＿２〜ＲＢ＿４をそれぞれ値「５４」、値「−３２」、値「＋８」とし、第２〜第４の等価プログラム命令をそれぞれ以下のように生成する。
【００６７】
「ｄｋｅｙ＝ｄｋｅｙ／２＋５４；」、
「ｄｋｅｙ＝ｄｋｅｙ＊４―３２；」、
「ｄｋｅｙ＝ｄｋｅｙ／５＋８；」
次に、等価プログラム命令生成部１０３は、第５の等価プログラム命令を生成する。
ここでは、等価プログラム命令生成部１０３は、ランダムな値ＲＡ＿Ｎを値「９」とする。さらに、等価プログラム命令生成部１０３は、以下のプログラム命令群の実行し、第二の値を算出する。
【００６８】
「ｄｋｅｙ＝１８；
ｄｋｅｙ＝ｄｋｅｙ／２＋５４；
ｄｋｅｙ＝ｄｋｅｙ＊４−３２；
ｄｋｅｙ＝ｄｋｅｙ／５＋８；」
このプログラム命令群を順に実行すると、「ｄｋｅｙ」の値は、順に、値「１８」、値「６３」、値「２２０」、値「５２」となり、等価プログラム命令生成部１０３は、値「５２」を第二の値とする。
【００６９】
等価プログラム命令生成部１０３は、
式１：（第一の値）＝（被秘匿情報の値）―  ｛  （第二の値）＊ＲＡ＿Ｎ  ｝
に、被秘匿情報の値「５１２」と、第二の値「５２」、ＲＡ＿Ｎの値「９」を代入することにより、第一の値「４４」を算出する。
等価プログラム命令生成部１０３は、第５の等価プログラム命令「ｄｋｅｙ＝ｄｋｅｙ＊９＋４４；」を生成する。
【００７０】
以上、まとめると、第１から第５の等価プログラム命令は順に
「ｄｋｅｙ＝１８；」、
「ｄｋｅｙ＝ｄｋｅｙ／２＋５４；」、
「ｄｋｅｙ＝ｄｋｅｙ＊４―３２；」、
「ｄｋｅｙ＝ｄｋｅｙ／５＋８；」、
「ｄｋｅｙ＝ｄｋｅｙ＊９＋４４；」
となる。これらのプログラム命令を順に行った場合のｄｋｅｙの値は被秘匿情報の値「５１２」になることを確認することが出来る。
【００７１】
１．１．５  等価プログラム生成部１０４
等価プログラム生成部１０４は、被秘匿情報を秘密情報用変数に置き換え、等価プログラム命令生成部１０３にて生成したそれぞれの等価プログラム命令を、等価プログラム命令挿入対象ブロックに挿入し、等価プログラム挿入後ブロックを生成する。
等価プログラム生成部１０４は、生成した等価プログラム挿入後ブロックと、等価プログラム命令を挿入しなかった分割後ブロックとからなる等価プログラムを生成する。等価プログラムは、被秘匿情報を含む命令が等価プログラム命令群に置き換えられているが、置き換えを行う前のプログラムと同等の機能を有するプログラムである。
【００７２】
なお、以降において、等価プログラム命令を挿入しなかった分割後ブロックのことを、以降の説明では等価プログラム非挿入ブロックと呼ぶ。
等価プログラム生成部１０４は、秘密情報用変数の追加と、被秘匿情報の置き換えと、等価プログラム命令の挿入とを行う。
（１）秘密情報用変数の追加
等価プログラム生成部１０４は、等価プログラム命令生成部１０３にて決定された秘密情報用変数を、難読化対象プログラムの変数宣言部に追加し、新たな変数宣言部を生成する。
【００７３】
（２）被秘匿情報の置き換え
等価プログラム生成部１０４は、記憶部１００にて記憶されている位置情報を取得し、取得した位置情報にて示されるプログラム命令に含まれる被秘匿情報の値を秘密情報用変数に置き換える。ここでは、等価プログラム生成部１０４は、秘密保有ノードに含まれる被秘匿情報の値を秘密情報用変数に置き換える。
【００７４】
（３）等価プログラム命令の挿入
等価プログラム生成部１０４は、等価プログラム命令生成部１０３にて生成した等価プログラム命令それぞれを、等価プログラム命令生成部１０３にて決定したいずれかの等価プログラム命令挿入対象ブロックに挿入する。以下、詳細な動作について説明する。
等価プログラム生成部１０４は、第ｔ（ｔ＝１、２、・・・、Ｎ）の等価プログラム命令を第（Ｎ―ｔ＋１）の等価プログラム命令挿入対象ブロックに挿入し、第（Ｎ―ｔ＋１）の等価プログラム命令挿入後ブロックを生成する。
【００７５】
つまり、等価プログラム生成部１０４は、第1の等価プログラム命令を第Ｎの等価プログラム命令挿入対象ブロックに挿入し、第Ｎの等価プログラム命令挿入後ブロックを生成する。以下、同様に、第ｔ（ｔ＝２、３、・・・、Ｎ）の等価プログラム命令を第（Ｎ−ｔ＋１）の等価プログラム命令挿入対象ブロックに挿入し、第ｔの等価プログラム命令挿入後ブロックを生成する。
【００７６】
ここで、第Ｎの等価プログラム命令は、被秘匿情報を秘密情報用変数に置き換えたプログラム命令よりも前に挿入することとする。これは、秘密情報用変数が被秘匿情報の値になってから、被秘匿情報を秘密情報用変数に置き換えることにより生成したプログラム命令を実行することを確実にするためである。
なお、以降の説明において、等価プログラム命令を挿入しなかった分割後ブロックのことを、等価プログラム非挿入ブロックと呼ぶ。
【００７７】
これにより、等価プログラム生成部１０４は、１以上の等価プログラム挿入後ブロックと、１以上の等価プログラム非挿入ブロックからなる等価プログラムを生成することができる。
また、第１〜第Ｎの等価プログラム挿入後ブロックを実行することにより、秘密情報用変数には被秘匿情報の値が設定されることがわかる。
【００７８】
なぜなら、上述したように、第1の等価プログラム命令挿入対象ブロックは、被秘匿情報を有する分割後ブロックである。さらに、第1の等価プログラム命令挿入対象ブロックが実行される際には、それ以前に必ず第Ｎ、第（Ｎ−１）、・・・、第２の等価プログラム命令挿入対象ブロックがこの順番で実行される。一方で、（１．１．４）で述べたように、第１、第２、・・・、第Ｎの等価プログラム命令をこの順に実行すれば、秘密情報用変数の値は被秘匿情報の値となる。したがって、等価プログラム生成部１０４は、上述したように、第１〜第Ｎの等価プログラム挿入後ブロックを生成することにより、第1の等価プログラム命令挿入後ブロックが実行される際には、それ以前に必ず第Ｎ、第（Ｎ−１）、・・・、第２の等価プログラム命令挿入後ブロックが実行されることとなり、その中に含まれる第１、第２、・・・、第（Ｎ−１）の等価プログラム命令が必ずこの順番で実行されることとなる。よって第１の等価プログラム命令挿入後ブロックにある第Ｎの等価プログラム命令が実行された際には、秘密情報用の変数は被秘匿情報の値となる。
【００７９】
したがって、等価プログラム生成部１０４にて生成された等価プログラムが、デバッガ等を用いてプログラムカウンターを強制的に変更する等の特別な操作を行わない正常系で実行された場合、第１の等価プログラム命令を含む第Ｎの等価プログラム挿入後ブロックが実行された際には、秘密情報用変数の値は第１の等価プログラム命令が実行された際に秘密情報用変数が取る値になる。また、第２の等価プログラム命令を含む第（Ｎ−１）の等価プログラム挿入後ブロックが実行された際には、第１〜第２の等価プログラム命令を順に行った場合の秘密情報用変数の値は、第１の等価プログラム命令と第２の等価プログラム命令を順に行った際に秘密情報用変数が取る値となる。以下、同様に、第ｔ（ｔ＝３、４、・・・Ｎ）の等価プログラム命令を含む第（Ｎ−ｔ＋１）の等価プログラム命令挿入後ブロックが実行された際には、秘密情報用変数が、第１〜第ｔまでの等価プログラム命令を順に実行された際に秘密情報用変数が取る値となる。
【００８０】
（４）具体例
等価プログラム生成部１０４は、等価プログラム命令生成部１０３にて決定された秘密情報用変数「ｄｋｅｙ」を、難読化対象プログラムの変数宣言部に追加し、図６に示すように、新たな変数宣言部６０１を生成する。変数宣言部６０１は、変数宣言部２０２に、秘密情報用変数「ｄｋｅｙ」の宣言文が加わったものである。このとき、等価プログラム生成部１０４は、秘密情報用変数「ｄｋｅｙ」を、難読化対象プログラムの変数宣言部に追加する際に、変数「ｄｋｅｙ」の変数の型を、被秘匿情報である「５１２」を示すことが出来る型にする（例えば、８ビット正整数型を用いると０〜２５５までしか表現できず５１２を示すことができないので、これは避ける。）。ここでは、例えば、変数「ｄｋｅｙ」の変数の型をｉｎｔ型とする。
【００８１】
次に、等価プログラム生成部１０４は、位置情報にて示されるプログラム命令（ここでは、図２にて示すプログラム命令２０４）における被秘匿情報の値「５１２」を秘密情報用変数「ｄｋｅｙ」に置き換えて、図６に示すように、新たなプログラム命令６０３を生成する。
次に、等価プログラム生成部１０４は、第１の等価プログラム命令「ｄｋｅｙ＝１８；」を第５の等価プログラム命令挿入対象ブロックであるノード５０１ａに挿入し、第５の等価プログラム命令挿入後ブロック６０２ａを生成する。同様に第２の等価プログラム命令「ｄｋｅｙ＝ｄｋｅｙ／２＋５４；」を第４の等価プログラム命令挿入対象ブロックであるノード５０１ｂに挿入し、第４の等価プログラム命令挿入後ブロック６０２ｂを生成する。以下、同様に、第３の等価プログラム命令挿入後ブロック６０２ｃ、第２の等価プログラム命令挿入後ブロック６０２ｄ、第１の等価プログラム命令挿入後ブロック６０２ｅを生成する。
【００８２】
ここで、等価プログラム命令を挿入しなかったノード５０１ｆ〜５０１ｈを、以降では、等価プログラム命令非挿入ブロック６０３ｆ〜６０３ｈとする。
図６にて、等価プログラム命令挿入後ブロック６０２ａ〜６０２ｅと、等価プログラム命令非挿入ブロック６０３ｆ〜６０３ｈとを用いたグラフを示す。
１．１．６  偽装ブロック挿入後プログラム生成部１０５
偽装ブロック挿入後プログラム生成部１０５は、正常系での実行結果を得るためには必要なく、また実行されることもないプログラム命令群である偽装ブロックを生成する。偽装ブロックは、より詳細には、プログラム実行中にデバッガ等を用いてプログラムカウンターや変数の値を強制的に変更することを行わない限り、実行されることのないプログラム命令群である。
【００８３】
偽装ブロック挿入後プログラム生成部１０５は、生成した偽装ブロックと、等価プログラム命令挿入後ブロックと、等価プログラム命令非挿入ブロックからなる偽装ブロック挿入後プログラムを生成する。
偽装ブロック挿入後プログラム生成部１０５は、偽装ブロック数の取得と、偽装ブロック本体の生成と、偽装等価プログラム命令挿入後偽装ブロックの生成と、偽装分岐命令付き偽装ブロックの生成とを行う。
【００８４】
（１）偽装ブロック数の取得
偽装ブロック挿入後プログラム生成部１０５は、生成する偽装ブロック数を予め記憶している。
偽装ブロック挿入後プログラム生成部１０５は、記憶している偽装ブロック数を取得する。偽装ブロック数の値は、例えば、「１０００」等である。なお、説明の簡略化のために偽装ブロック数を値「４」とする。
【００８５】
ここで、偽装ブロック数の決定について説明する。ノード数（ここでは、偽装ブロック数）と、難読化の強度との関係は、図７に示すように、ノード数が大きくなるにつれ、まず難読化の強度は指数関数的に増加し（図７に示す関数Ｇ１１０）、ある時点から、ノード数が増大するにつれ、難読化の強度が指数関数的に減少する（図７に示す関数Ｇ１２０）。偽装ブロック数は、例えば、図７に示すｔ１〜ｔ２の区間から選ばれることが望ましい。特に、ｔ１に対応するノード数を偽装ブロック数とすることが望ましい。
【００８６】
（２）偽装ブロック本体の生成
偽装ブロック挿入後プログラム生成部１０５は、取得した偽装ブロック数にて示される個数の偽装ブロック本体を生成する。
偽装ブロック挿入後プログラム生成部１０５は、ブロック分割部１０２で生成した分割後ブロックの中から１以上の分割後ブロックをランダムに選択する。
【００８７】
偽装ブロック挿入後プログラム生成部１０５は、選択した１以上の分割後ブロックそれぞれのプログラム命令群から、分岐命令（無条件分岐命令および条件分岐命令）を取り除いたプログラム命令群と同じプログラム命令群からなるプログラム命令群を偽装ブロック本体として生成する。
（３）偽装等価プログラム命令挿入後偽装ブロックの生成
偽装ブロック挿入後プログラム生成部１０５は、生成した偽装ブロック本体のそれぞれに対して、偽装等価プログラム命令を生成する。偽装ブロック挿入後プログラム生成部１０５は、生成した偽装等価プログラム命令それぞれを、対応する偽装ブロック本体のそれぞれに挿入し、偽装等価プログラム命令挿入後偽装ブロックを生成する。偽装等価プログラム命令は、等価プログラム生成部１０４にて用いた第ｔ（ｔ＝２、３、・・・Ｎ）の等価プログラム命令と同じ変数、演算子を用いたプログラム命令である。
【００８８】
偽装ブロック挿入後プログラム生成部１０５は、以下の動作を、生成した全ての偽装ブロック本体に対して行い、偽装等価プログラム命令挿入後偽装ブロックを生成する。
偽装ブロック挿入後プログラム生成部１０５は、０以外の整数ＲＡ及びＲＢをランダムに選択し、選択したＲＡ及びＲＢを用いて、偽装等価プログラム命令「（秘密情報用変数）＝（秘密情報用変数）（演算子）（ＲＡ）＋（ＲＢ）；」を生成する。ここで、演算子は、掛け算を表す「＊」または割り算を表す「／」のどちらかの演算子であり、どちらにするかはランダムに選択する。偽装ブロック挿入後プログラム生成部１０５は、生成した偽装等価プログラム命令を、対応する偽装ブロック本体の先頭に挿入する。
【００８９】
このように生成した偽装等価プログラム命令は、前述の等価プログラム命令と同じく秘密情報用変数を用いたプログラム命令であり、秘密情報用変数のみに着目した場合、等価プログラム命令と区別できないプログラム命令である。そのため、秘密情報用変数に着目して等価プログラム命令を収集しようとする不正解析者には、偽装等価プログラム命令と等価プログラム命令の区別がつかない。
【００９０】
（４）偽装分岐命令付き偽装ブロックの生成
偽装ブロック挿入後プログラム生成部１０５は、ユーザが所望する難読化の強度に応じて定まる数である所定数を予め記憶している。本実施の形態では、所定数は、例えば、「１３」である。
偽装ブロック挿入後プログラム生成部１０５は、生成した偽装等価プログラム命令挿入後偽装ブロックのそれぞれに、無条件分岐命令及び条件分岐命令のうち少なくとも１の分岐命令を挿入し、偽装分岐命令付き偽装ブロックを生成する。
【００９１】
偽装ブロック挿入後プログラム生成部１０５は、等価プログラム命令非挿入ブロックそれぞれの先頭に異なるラベルを挿入し、ラベル挿入後等価プログラム命令非挿入ブロックを生成する。
偽装ブロック挿入後プログラム生成部１０５は、生成した各々の偽装等価プログラム命令挿入後偽装ブロックの先頭に異なるラベルを追加し、ラベル挿入後偽装等価プログラム命令挿入後偽装ブロックを生成する。
【００９２】
ここで、各ブロックに挿入するラベルのラベル名は、プログラム中で既に使用されているラベル名とは重複しないようにする。また、既に、ラベルが付与されている場合には、新たなラベルの挿入は行わない。
次に、偽装ブロック挿入後プログラム生成部１０５は、ラベル挿入後偽装等価プログラム命令挿入後偽装ブロックの最後に無条件分岐命令を追加する。なお、以降では、ラベル挿入後偽装等価プログラム命令挿入後偽装ブロックの最後に無条件分岐命令が追加されたブロックをＴＭＰブロックと呼ぶ。
【００９３】
また、ＴＭＰブロックを生成する際に、追加する無条件分岐命令の分岐先は、ラベル挿入後偽装等価プログラム命令挿入後偽装ブロックのそれぞれと、ラベル挿入後等価プログラム命令挿入後ブロックのそれぞれと、ラベル挿入後等価プログラム非挿入ブロックのそれぞれの中からランダムに選んだブロックの先頭とする。以下の説明では、この動作により生成した全てのＴＭＰブロックからなるブロックの集合をＴＭＰブロック群と呼ぶ。
【００９４】
次に、偽装ブロック挿入後プログラム生成部１０５は、ＴＭＰブロック群を構成するＴＭＰブロックのそれぞれと、ラベル挿入後等価プログラム挿入後ブロックのそれぞれと、ラベル挿入後等価プログラム命令非挿入ブロックのそれぞれをノードと見なし、第一のノードが第二のノードへの分岐命令を含む場合に第一のノードと第二のノードの間にはエッジが存在すると見なし、また、第一のノードの最後のプログラム命令が無条件分岐命令以外のプログラム命令であって、最後のプログラム命令の一つ後のプログラム命令が対応するノードが第二のノードであった場合に、第一のノードと第二のノードの間にはエッジが存在すると見なし、ノードとエッジからなるグラフを生成する。
【００９５】
次に、偽装ブロック挿入後プログラム生成部１０５は、生成したグラフを用いて、ノード数、及びエッジ数を取得する。偽装ブロック挿入後プログラム生成部１０５は、式「（エッジ数）−（ノード数）」を算出し、算出した値が所定数以上であるか否かを判定する。
算出結果が所定数以上であると判定する場合には、偽装ブロック挿入後プログラム生成部１０５は、処理を中止する。中止した時点での、ＴＭＰブロック群を構成するＴＭＰブロックを、以降、偽装ブロックと呼ぶ。
【００９６】
所定数以上でないと判定する場合には、偽装ブロック挿入後プログラム生成部１０５は、以下の動作を行う。
偽装ブロック挿入後プログラム生成部１０５は、ＴＭＰブロック群を構成するＴＭＰブロックの中から条件分岐命令を挿入するＴＭＰブロックをランダムに選択する。次に、選択したＴＭＰブロックに、条件分岐命令を挿入し、新たなＴＭＰブロックを生成する。ここで、挿入する条件分岐命令の分岐条件は秘密情報用変数とランダムに決定した値とを比較する条件式とし、条件分岐命令の分岐先は、生成したグラフを構成するいずれかのノードに対応するブロックの先頭とする。条件分岐命令を挿入する位置は、挿入対象ブロックが有する一番最初の分岐命令よりも前の位置とする。挿入対象ブロックが分岐命令を有さない場合には、挿入対象ブロックの最後に追加するものとする。
【００９７】
偽装ブロック挿入後プログラム生成部１０５は、条件分岐命令を挿入して生成した新たなＴＭＰブロックと、挿入を行わず変更を加えていないＴＭＰブロックからなるブロック群を新たなＴＭＰブロック群とし、再度、グラフ生成を行い、上記に示す動作を行う。
（５）具体例
偽装ブロック挿入後プログラム生成部１０５は、予め記憶している偽装ブロック数「４」を取得する。
【００９８】
偽装ブロック挿入後プログラム生成部１０５は、図８に示すように、取得した偽装ブロック数にて示される個数の偽装ブロック本体７０１ｉ〜７０１ｌを生成する。
偽装ブロック挿入後プログラム生成部１０５は、ブロック分割部１０２で生成した分割後ブロックの中から１の分割後ブロック４０１ｃを選択し、選択した分割後ブロック４０１ｃから分岐命令である「ｉｆ（条件１）ｇｏｔｏ  ｌａｂｅｌＦ；」を取り除いたプログラム命令群Ｃを用いて、偽装ブロック本体７０１ｉを生成する。
【００９９】
偽装ブロック挿入後プログラム生成部１０５は、ブロック分割部１０２で生成した分割後ブロックの中から１の分割後ブロック４０１ｈを選択し、選択した分割後ブロック４０１ｈを用いて、偽装ブロック本体７０１ｊを生成する。偽装ブロック本体７０１ｋ、７０１ｌについても同様の生成方法であるため、ここでの説明は省略する。
次に、偽装ブロック挿入後プログラム生成部１０５は、生成した偽装ブロック本体７０１ｉ〜７０１ｌのそれぞれに対する偽装等価プログラム命令を生成する。偽装ブロック挿入後プログラム生成部１０５は、生成した偽装等価プログラム命令のそれぞれを偽装ブロック本体７０１ｉ〜７０１ｌに挿入して、図９に示すような偽装等価プログラム命令挿入後偽装ブロック８０１ｉ〜８０１ｌを生成する。
【０１００】
例えば、偽装ブロック挿入後プログラム生成部１０５は、偽装ブロック本体７０１ｉに対する偽装等価プログラム命令「ｄｋｅｙ＝ｄｋｅｙ＊３４＋７；」を生成し、生成した偽装等価プログラム命令を偽装ブロック本体７０１ｉに挿入することにより、偽装等価プログラム命令挿入後偽装ブロック８０１ｉを生成する。
偽装等価プログラム命令挿入後偽装ブロック８０１ｊ〜８０１ｌについても同様の生成方法であるため、ここでの説明は省略する。
【０１０１】
次に、偽装ブロック挿入後プログラム生成部１０５は、等価プログラム命令挿入後ブロック６０２ａ〜６０２ｅ、等価プログラム命令非挿入ブロック６０３ｆ〜６０３ｈ、偽装等価プログラム命令挿入後偽装ブロック８０１ｉ〜８０１ｌのそれぞれの先頭に、ラベルを挿入し、ラベル挿入後等価プログラム命令挿入後ブロック１００１ａ〜１００１ｅ、ラベル挿入後等価プログラム命令非挿入ブロック１００２ｆ〜１００２ｈ、及びラベル挿入後偽装等価プログラム命令挿入後偽装ブロック１００３ｉ〜１００３ｌを生成する。図１０において、生成した各ブロックの一例を示す。ここで、ブロックＢ１０００は、ラベル挿入後等価プログラム命令挿入後ブロック１００１ａ〜１００１ｅと、ラベル挿入後等価プログラム命令非挿入ブロック１００２ｆ〜１００２ｈとからなり、上位から順に実行する、又は、ラベル挿入後等価プログラム命令挿入後ブロック１００１ａ〜１００１ｃの実行後、分岐命令にてラベル挿入後等価プログラム命令非挿入ブロック１００２ｆに分岐し、ラベル挿入後等価プログラム命令非挿入ブロック１００２ｆ〜１００２ｈを実行するものとする。また、ブロックＢ１００１は、ラベル挿入後偽装等価プログラム命令挿入後偽装ブロック１００３ｉ〜１００３ｌからなるものとする。
【０１０２】
図１０において、ラベル挿入後等価プログラム命令挿入後ブロック１００１ａ〜１００１ｅは、等価プログラム命令挿入後ブロック６０２ａ〜６０２ｅの各ブロックの先頭にそれぞれ重複しないラベルを挿入して生成したラベル挿入後等価プログラム命令挿入後ブロックである。
ラベル挿入後等価プログラム命令非挿入ブロック１００２ｆ〜１００２ｈは、等価プログラム命令非挿入ブロック６０３ｆ〜６０３ｈの各ブロックの先頭にそれぞれ重複しないラベルを挿入して生成したラベル挿入後等価プログラム命令非挿入ブロックである。なお、等価プログラム命令非挿入ブロック６０３ｆの先頭には始めからラベル「ｌａｂｅｌＦ：」があったので、ラベルの挿入は行っていない。
【０１０３】
ラベル挿入後偽装等価プログラム命令挿入後偽装ブロック１００３ｉ〜１００３ｌは、偽装等価プログラム命令挿入後偽装ブロック８０１ｉ〜８０１ｌの各ブロックの先頭にそれぞれ重複しないラベルを挿入して生成したラベル挿入後偽装等価プログラム命令挿入後偽装ブロックである。
次に、偽装ブロック挿入後プログラム生成部１０５は、生成したラベル挿入後偽装等価プログラム命令挿入後偽装ブロック１００３ｉ〜１００３ｌからＴＭＰブロック１１０１ｉ〜１１０１ｌを生成する。図１１において、生成したＴＭＰブロック１１０１ｉ〜１１０１ｌの一例を示す。
【０１０４】
例えば、偽装ブロック挿入後プログラム生成部１０５は、ラベル挿入後等価プログラム命令挿入後ブロック１００１ａ〜１００１ｅ、ラベル挿入後等価プログラム命令非挿入ブロック１００２ｆ〜１００２ｈ、及びラベル挿入後偽装等価プログラム命令挿入後偽装ブロック１００３ｉ〜１００３ｌから、ラベル挿入後等価プログラム命令挿入後ブロック１００１ａを選択する。偽装ブロック挿入後プログラム生成部１０５は、選択したラベル挿入後等価プログラム命令挿入後ブロック１００１ａへ無条件に分岐するように、無条件分岐命令「ｇｏｔｏ  ｌａｂｅｌＡ；」を生成し、生成した無条件分岐命令を、ラベル挿入後偽装等価プログラム命令挿入後偽装ブロック１００３ｉの最後に挿入して、ＴＭＰブロック１１０１ｉを生成する。
【０１０５】
ＴＭＰブロック１１０１ｊ〜１１０１ｌについても同様の生成方法であるため、ここでの説明は省略する。
次に、偽装ブロック挿入後プログラム生成部１０５は、以下のようにして図１２にて示すグラフＧ２００を生成する。ここでは、ラベル挿入後等価プログラム命令挿入後ブロック１００１ａ〜１００１ｅのそれぞれを、ノード１２０１ａ〜１２０１ｅとし、ラベル挿入後等価プログラム命令非挿入ブロック１００２ｆ〜１００２ｈのそれぞれを、ノード１２０１ｆ〜１２０１ｈとし、ＴＭＰブロック１１０１ｊ〜１１０１ｌのそれぞれを、ノード１２０１ｉ〜１２０１ｌとして説明する。
【０１０６】
ラベル挿入後等価プログラム命令挿入後ブロック１００１ａの最後のプログラム命令は無条件分岐命令ではない。また、ラベル挿入後等価プログラム命令挿入後ブロック１００１ａの次のプログラム命令はラベル挿入後等価プログラム命令挿入後ブロック１００１ｂのプログラム命令である。よって、偽装ブロック挿入後プログラム生成部１０５は、ノード１２０１ａとノード１２０１ｂにエッジ１２０２ａを設ける。
【０１０７】
同様にして、偽装ブロック挿入後プログラム生成部１０５は、エッジ１２０２ｂ〜エッジ１２０２ｇを設ける。
ラベル挿入後等価プログラム命令挿入後ブロック１００１ｃにはラベル挿入後等価プログラム命令非挿入ブロック１００２ｆのラベル「ｌａｂｅｌＦ：」に条件分岐する条件分岐命令「ｉｆ（条件１）  ｇｏｔｏ  ｌａｂｅｌＦ；」がある。よって、偽装ブロック挿入後プログラム生成部１０５は、ノード１２０１ｃとノード１２０１ｆにエッジ１２０２ｈを設ける。
【０１０８】
ＴＭＰブロック１１０１ｉの最後のプログラム命令は無条件分岐命令であるプログラム命令「ｇｏｔｏ  ｌａｂｅｌＡ；」はラベル挿入後等価プログラム命令挿入後ブロック１００１ａのラベル「ｌａｂｅｌＡ：」に無条件分岐するプログラム命令である。よって、偽装ブロック挿入後プログラム生成部１０５は、ノード１２０１ｉとノード１２０１ａにエッジ１２０２ｉを設ける。
【０１０９】
同様にして、偽装ブロック挿入後プログラム生成部１０５は、エッジ１２０２ｊ〜１２０２ｋを設ける。
偽装ブロック挿入後プログラム生成部１０５は、上記の動作を行うことにより、グラフＧ２００を生成することができる。
次に、偽装ブロック挿入後プログラム生成部１０５は、図１２にて示すグラフＧ２００を用いて、「（エッジ数）−（ノード数）」の値が、所定数「１３」以上であるか否かを判定する。
【０１１０】
ここでは、「（エッジ数）−（ノード数）」の値は０であるので、偽装ブロック挿入後プログラム生成部１０５は、所定数以上でないと判定し、以下の動作を行う。
偽装ブロック挿入後プログラム生成部１０５は、ＴＭＰブロック１１０１ｉ〜１１０１ｌからＴＭＰブロック１１０１ｊをランダムに選択し、選択したＴＭＰブロック１１０１ｊに条件分岐命令を挿入して、図１３にて示す新たなＴＭＰブロック１３０１ｊを生成する。
【０１１１】
偽装ブロック挿入後プログラム生成部１０５は、ＴＭＰブロック１３０１ｊを生成する際に、まず、選択したＴＭＰブロック１１０１ｊに挿入する条件分岐命令を生成する。ここでは、秘密情報用変数を「ｄｋｅｙ」とし、ランダムな値を値「２７３」とし、「ｄｋｅｙ」と値「２７３」との比較を条件式とする。さらに、ノード１２０１ａ〜１２０１ｌまでのノードからノード１２０１ｄを、ランダムにノードを選択する。偽装ブロック挿入後プログラム生成部１０５は、生成する条件分岐命令の条件分岐先を、選択したノード１２０１ｄに対応するブロックであるラベル挿入後等価プログラム命令挿入後ブロック１００１ｄの先頭にする。このようにして生成した条件分岐命令に対応するプログラム命令が、プログラム命令「ｉｆ（ｄｋｅｙ＞２７３）ｇｏｔｏ  ｌａｂｅｌＤ；」である。次に、偽装ブロック挿入後プログラム生成部１０５は、ＴＭＰブロック１１０１ｊの一番最後のプログラム命令であり、無条件分岐命令でもあるプログラム命令「ｇｏｔｏ  ｌａｂｅｌ  Ｂ；」の一つ手前に生成したプログラム命令を挿入して、ＴＭＰブロック１３０１ｊを生成する。
【０１１２】
以上の動作が終了した後、偽装ブロック挿入後プログラム生成部１０５は、生成したＴＭＰブロック１３０１ｊと、変更を行わなかったＴＭＰブロックであるＴＭＰブロック１１０１ｉ、１１０１ｋおよび１１０１ｌからなるブロック群を新たなＴＭＰブロック群とし、グラフの作成を行う。
ここで、新たなＴＭＰブロック群を用いたグラフＧ２１０を図１４に示す。グラフＧ２００との違いは、ノード１２０１ｊがノード１２０５ｊとなり、ノード１２０５ｊとノード１２０１ｂとにエッジ１２０２ｊを設け、ノード１２０５ｊとノード１２０１ｄとにエッジ１３０２ｊを設ける。なお、ＴＭＰブロック１３０１ｊとノード１２０５ｊとが対応している。
【０１１３】
１．１．７  擬似分岐命令挿入後プログラム生成部１０６
擬似分岐命令挿入後プログラム生成部１０６は、偽装ブロック挿入後プログラム生成部１０５にて生成したラベル挿入後等価プログラム命令挿入後ブロックに、擬似分岐命令を挿入して擬似分岐命令挿入後ブロックを生成する。ここで、ラベル挿入後等価プログラム命令挿入後ブロックに挿入される擬似分岐命令は、デバッガ等を用いてプログラムカウンターを強制的に変更する等の特別な操作を行わない正常系のプログラム実行時には必ず真偽が一定の値となる分岐条件分岐命令である。
【０１１４】
擬似分岐命令挿入後プログラム生成部１０６は、生成した擬似分岐命令挿入後ブロックのそれぞれと、ラベル挿入後等価プログラム命令非挿入ブロックのそれぞれと、偽装ブロック挿入後プログラム生成部１０５にて生成した偽装ブロックのそれぞれとからなる擬似分岐命令挿入後プログラムを生成する。
擬似分岐命令挿入後プログラム生成部１０６は、第Ｎのラベル挿入後等価プログラム命令挿入後ブロックから第１のラベル挿入後等価プログラム命令挿入後ブロックに対して、等価命令挿入後ブロック秘密情報用の変数値の決定と、擬似分岐命令の挿入とを行うことにより、擬似分岐命令挿入後プログラムを生成する。
【０１１５】
以下に、擬似分岐命令挿入後プログラム生成部１０６が、第ｔ（ｔ＝１、２、・・・、Ｎ）のラベル挿入後等価プログラム命令挿入後ブロックから擬似分岐命令挿入後ブロックを生成する場合について説明する。
擬似分岐命令挿入後プログラム生成部１０６は、第１の等価プログラム命令から第（Ｎ−ｔ＋１）の等価プログラムまでの等価プログラムを取得する。
【０１１６】
擬似分岐命令挿入後プログラム生成部１０６は、取得した第１〜第（Ｎ−ｔ＋１）の等価プログラムを順次実行して、等価命令挿入後ブロック秘密情報用の変数値を算出する。
次に、擬似分岐命令挿入後プログラム生成部１０６は、定数ｍ及び比較演算子をランダムに選択し、条件式「ｄｋｅｙ  （比較演算子）  ｍ」を生成する。
擬似分岐命令挿入後プログラム生成部１０６は、生成した条件式を用いて、擬似分岐命令「ｉｆ  （ｄｋｅｙ  （比較演算子）  ｍ）  ｔｈｅｎ  第１の分岐先  ｅｌｓｅ  第２の分岐先」を生成する。擬似分岐命令挿入後プログラム生成部１０６は、生成した擬似分岐命令を、第ｔのラベル挿入後等価プログラム命令挿入後ブロックの追加して擬似分岐命令挿入後ブロックを生成する。なお、条件分岐命令を追加する位置はブロックの最後とする。
【０１１７】
ここで、擬似分岐命令の生成方法について、説明する。
擬似分岐命令挿入後プログラム生成部１０６は、変数「ｄｋｅｙ」に、算出した等価命令挿入後ブロック秘密情報用の変数値を代入し、条件式の真偽を判定する。
条件式が真であると判定する場合には、擬似分岐命令挿入後プログラム生成部１０６は、第１の分岐先を次ブロックとし、第２の分岐先をラベル挿入後等価プログラム命令挿入後ブロックのそれぞれと、ラベル挿入後等価プログラム命令非挿入ブロックのそれぞれと、偽装ブロックのそれぞれからランダムに選択した１のブロックとする。
【０１１８】
条件式が偽であると判定する場合には、擬似分岐命令挿入後プログラム生成部１０６は、第１の分岐先をラベル挿入後等価プログラム命令挿入後ブロックのそれぞれと、ラベル挿入後等価プログラム命令非挿入ブロックのそれぞれと、偽装ブロックのそれぞれからランダムに選択した１のブロックとし、第２の分岐先を次ブロックとする。
なお、擬似分岐命令挿入後プログラム生成部１０６は、第１の分岐先と第２の分岐先が、重複しないように、各ブロックを選択する。
【０１１９】
以下に具体例を示す。
ここでは、ラベル挿入後等価プログラム命令挿入後ブロック１００１ａ〜１００１ｅから図１５に示す擬似分岐命令挿入後ブロック１４０１ａ〜１４０１ｅが生成される具体例について説明する。
擬似分岐命令挿入後プログラム生成部１０６は、まず、第Ｎ（ここでは、Ｎ＝５）ラベル挿入後等価プログラム命令挿入後ブロック１００１ａから擬似分岐命令挿入後ブロック１４０１ａを以下のようにして生成する。
【０１２０】
擬似分岐命令挿入後プログラム生成部１０６は、第１の等価プログラム命令「ｄｋｅｙ＝１８；」を取得し、取得した第１の等価プログラム命令を用いて、等価命令挿入後ブロック秘密情報用の変数値「１８」を算出する。
擬似分岐命令挿入後プログラム生成部１０６は、定数ｍ（ここでは、「４６」）及び比較演算子（ここでは、「＜」）をランダムに選択し、条件式「ｄｋｅｙ  ＜  ４６」を生成する。
【０１２１】
擬似分岐命令挿入後プログラム生成部１０６は、変数「ｄｋｅｙ」に、算出した等価命令挿入後ブロック秘密情報用の変数値「１８」を代入し、条件式の真偽を判定する。
この場合、条件式は真となり、擬似分岐命令挿入後プログラム生成部１０６は、第１の分岐先として次ブロック（ここでは、ラベル名が「ｌａｂｅｌＢ」であるブロック）を選択し、第２の分岐先としてラベル名が「ｌａｂｅｌＣ」を選択し、擬似分岐命令であるプログラム命令「ｉｆ（ｄｋｅｙ＜４６）ｇｏｔｏ  ｌａｂｅｌＢ；ｅｌｓｅ  ｇｏｔｏ  ｌａｂｅｌＣ；」を生成する。
【０１２２】
擬似分岐命令挿入後プログラム生成部１０６は、生成した擬似分岐命令を第５のラベル挿入後等価プログラム命令挿入後ブロック１００１ａの最後に挿入して、擬似分岐命令挿入後ブロック１４０１ａを生成する。
擬似分岐命令挿入後ブロック１４０１ｂ〜１４０１ｅについても同様の生成方法であるため、ここでの説明は省略する。
【０１２３】
１．１．８  被入替ブロック群生成部１０７
被入替ブロック群生成部１０７は、ラベル挿入後等価プログラム非挿入ブロックのそれぞれと、偽装ブロックのそれぞれと、偽装分岐命令挿入後ブロックのそれぞれからなるブロック群から、デバッガ等を用いてプログラムカウンターを強制的に変更する等の特別な操作を行わない正常系の実行時に、ｇｏｔｏ文を用いずに他のブロックに移動する経路を有するブロックを１以上抽出する。
【０１２４】
被入替ブロック群生成部１０７は、抽出した１以上のブロックそれぞれに対して、他のブロックへの移動する経路をｇｏｔｏ文を用いた分岐に置き換える。
また、被入替ブロック群生成部１０７は、プログラムの出口となるプログラム命令を含むブロックを抽出し、抽出したブロックの最後の命令がプログラム命令「ｒｅｔｕｒｎ；」、「ｅｘｉｔ（）；」以外のプログラム命令であった場合には、ブロックの最後にプログラム命令「ｒｅｔｕｒｎ；」を追加する。
【０１２５】
被入替ブロック群生成部１０７は、変更を加えたブロックのそれぞれと、置き換えを行わなかったブロックのそれぞれからなる被入替ブロック群を生成する。
なお、以降の説明において、被入替ブロック群に含まれるブロックを被入替ブロックと呼ぶ。
以下に具体例を示す。
【０１２６】
被入替ブロック群生成部１０７が、ラベル挿入後等価プログラム命令非挿入ブロック１００２ｆ〜１００２ｈと、偽装ブロックのそれぞれと、擬似分岐命令挿入後ブロック１４０１ａ〜１４０１ｅとから生成した被入替ブロック群を、図１６に示す。
被入替ブロック群生成部１０７は、ラベル挿入後等価プログラム命令非挿入ブロック１００２ｆ〜１００２ｈと、偽装ブロックのそれぞれと、擬似分岐命令挿入後ブロック１４０１ａ〜１４０１ｅとから、ｇｏｔｏ文を用いずに他のブロックに移動する経路を有するブロック（ここでは、ラベル挿入後等価プログラム命令非挿入ブロック１００２ｆ、及び１００２ｇ）を抽出する。
【０１２７】
被入替ブロック群生成部１０７は、抽出したラベル挿入後等価プログラム命令非挿入ブロック１００２ｆに対して、他のブロック（ここでは、次ブロックである。）へ移動する経路を、無条件分岐命令であるプログラム命令「ｇｏｔｏ  ｌａｂｅｌＧ；」を挿入し、被入替ブロック１５０１ｆを生成する。
抽出したラベル挿入後等価プログラム命令非挿入ブロック１００２ｇに対しても同様に、被入替ブロック群生成部１０７は、無条件分岐命令であるプログラム命令「ｇｏｔｏ  ｌａｂｅｌＨ；」を挿入し、被入替ブロック１５０１ｇを生成する。
【０１２８】
被入替ブロック群生成部１０７は、プログラムの出口となるプログラム命令を含むブロック（ここでは、ラベル挿入後等価プログラム命令非挿入ブロック１００２ｈ）を抽出する。このとき、ラベル挿入後等価プログラム命令非挿入ブロック１００２ｈには処理群Ｈが含まれ、処理群Ｈは命令群Ｈである。その命令群Ｈの最後のプログラム命令は、「ｒｅｔｕｒｎ；」であるため、被入替ブロック群生成部１０７は、ブロックの最後にプログラム命令「ｒｅｔｕｒｎ；」を追加しないで、被入替ブロック１５０１ｈを生成する。つまり、ラベル挿入後等価プログラム命令非挿入ブロック１００２ｈと被入替ブロック１５０１ｈとは同一である。
【０１２９】
また、擬似分岐命令挿入後ブロック１４０１ａ〜１４０１ｅのそれぞれは、他のブロックへの分岐はｇｏｔｏ文を使っているため、被入替ブロック群生成部１０７は、擬似分岐命令挿入後ブロック１４０１ａ〜１４０１ｅのそれぞれに変更を加えることなく、被入替ブロック１５０１ａ〜１５０１ｅを生成する。
偽装ブロックについても同様に偽装ブロックそのものを被入替ブロックとし、被入替ブロック群生成部１０７は、被入替ブロック１５０１ｊ〜１５０１ｌを生成する。
【０１３０】
１．１．９  配置順序入替部１０８
配置順序入替部１０８は、被入替ブロック群生成部１０７で生成した被入替ブロック群に含まれる各被入替ブロックのうち、開始ノードとなる被入替ブロックを除く他の被入替ブロックの配置順序を、ランダムに入れ替える。
配置順序入替部１０８は、等価プログラム生成部１０４にて生成した新たな変数宣言部と、配置順序を入れ替えた被入替ブロック群とからなる難読化プログラムを生成する。
【０１３１】
配置順序入替部１０８は、生成した難読化プログラムを、当該難読化プログラムを実行する外部装置へ配布する。
以下に具体例を示す。
配置順序入替部１０８は、図１６にて示す被入替ブロック１５０１ｂ〜１５０１ｌの入れ替えを行う。ここでは、配置順序入替部１０８は、順に、被入替ブロック１５０１ａ、被入替ブロック１５０１ｇ、被入替ブロック１５０１ｄ、被入替ブロック１５０１ｃ、被入替ブロック１５０１ｅ、被入替ブロック１５０１ｌ、被入替ブロック１５０１ｆ、被入替ブロック１５０１ｂ、被入替ブロック１５０１ｈ、被入替ブロック１５０１ｋ、被入替ブロック１５０１ｉ、被入替ブロック１５０１ｊとなるように、入れ替えを行う。
【０１３２】
配置順序入替部１０８は、入れ替えを行った被入替ブロック群と、等価プログラム生成部１０４にて生成した変数宣言部６０１とから、図１７にて示す難読化プログラム１５００を生成する。
１．２  プログラム難読化装置１０の動作
ここでは、プログラム難読化装置１０の動作について説明する。
【０１３３】
１．２．１  動作概要
ここでは、プログラム難読化装置１０が難読化対象プログラムを難読化する動作概要について、図１８に示す流れ図を用いて説明する。
プログラム難読化装置１０の入力部１０１は、難読化対象プログラム、及び位置情報を受け付ける（ステップＳ５）。
【０１３４】
入力部１０１は、受け付けた難読化対象プログラムと位置情報とを記憶部１００へ格納する。
ブロック分割部１０２は、記憶部１００から難読化対象プログラムを読み出し、読み出した難読化対象プログラムに含まれる処理部を、１以上の基本ブロックに分割する。その後、ブロック分割部１０２は、分割した基本ブロックのそれぞれを、詳細に分割して、１以上の分割後ブロックを生成する（ステップＳ１０）。
【０１３５】
プログラム難読化装置１０は、等価プログラム生成処理を施して、等価プログラムを生成する（ステップＳ１５）。
プログラム難読化装置１０は、偽装ブロック挿入後プログラムの生成処理を施して、偽装ブロック挿入後プログラムを生成する（ステップＳ２０）。
プログラム難読化装置１０の擬似分岐命令挿入後プログラム生成部１０６は、ラベル挿入後等価プログラム命令挿入後ブロックに、擬似分岐命令を挿入して擬似分岐命令挿入後ブロックを生成する。擬似分岐命令挿入後プログラム生成部１０６は、生成した擬似分岐命令挿入後ブロックのそれぞれと、ラベル挿入後等価プログラム命令非挿入ブロックのそれぞれと、偽装ブロック挿入後プログラム生成部１０５にて生成した偽装ブロックのそれぞれとからなる擬似分岐命令挿入後プログラムを生成する（ステップＳ２５）。
【０１３６】
被入替ブロック群生成部１０７は、ラベル挿入後等価プログラム非挿入ブロックのそれぞれと、偽装ブロックのそれぞれと、偽装分岐命令挿入後ブロックのそれぞれからなるブロック群から、正常系の実行時に、ｇｏｔｏ文を用いずに他のブロックに移動する経路を有するブロックを１以上抽出する。被入替ブロック群生成部１０７は、抽出した１以上のブロックそれぞれに対して、他のブロックへの移動する経路をｇｏｔｏ文を用いた分岐に置き換える。また、被入替ブロック群生成部１０７は、プログラムの出口となるプログラム命令を含むブロックを抽出し、抽出したブロックの最後の命令がプログラム命令「ｒｅｔｕｒｎ；」、「ｅｘｉｔ（）；」以外のプログラム命令であった場合には、ブロックの最後にプログラム命令「ｒｅｔｕｒｎ；」を追加する。被入替ブロック群生成部１０７は、変更を加えたブロックのそれぞれと、置き換えを行わなかったブロックのそれぞれからなる被入替ブロック群を生成する（ステップＳ３０）。
【０１３７】
配置順序入替部１０８は、被入替ブロック群生成部１０７で生成した被入替ブロック群に含まれる各被入替ブロックのうち、開始ノードとなる被入替ブロックを除く他の被入替ブロックの配置順序を、ランダムに入れ替える。配置順序入替部１０８は、等価プログラム生成部１０４にて生成した新たな変数宣言部と、配置順序を入れ替えた被入替ブロック群とからなる難読化プログラムを生成する（ステップＳ３５）。
【０１３８】
配置順序入替部１０８は、生成した難読化プログラムを、当該難読化プログラムを実行する外部装置へ配布する（ステップＳ４０）。
１．２．２  等価プログラム生成処理の動作
ここでは、図１８に示す等価プログラム生成処理（ステップＳ１５）の動作について、図１９に示す流れ図を用いて説明する。
【０１３９】
等価プログラム命令生成部１０３は、難読化対象プログラムを解析し、このプログラム中で使用されている全ての変数名を調べる。次に、使用されているいずれの変数名とも重複しない変数名を生成し、生成した変数名を秘密情報用変数名として決定する（ステップＳ１００）。
等価プログラム命令生成部１０３は、ブロック分割部１０２により生成された分割後ブロックのそれぞれをノードと見なし、グラフを生成する。
【０１４０】
等価プログラム命令生成部１０３は、グラフ生成ステップで生成したグラフに基づき、等価プログラム命令を挿入する第１〜第Ｎの等価プログラム命令挿入対象ブロックを取得する（ステップＳ１０５）。ここで、Ｎは１以上の整数である。
等価プログラム命令生成部１０３は、取得した１以上の等価プログラム命令挿入対象ブロックそれぞれに対応する等価プログラム命令を生成する（ステップＳ１１０）。
【０１４１】
等価プログラム生成部１０４は、等価プログラム命令生成部１０３にて決定された秘密情報用変数を、難読化対象プログラムの変数宣言部に追加し、新たな変数宣言部を生成する（ステップＳ１１５）。
等価プログラム生成部１０４は、記憶部１００にて記憶されている位置情報を取得し、取得した位置情報にて示されるプログラム命令に含まれる被秘匿情報の値を秘密情報用変数に置き換える（ステップＳ１２０）。
【０１４２】
等価プログラム生成部１０４は、第ｔ（ｔ＝１、２、・・・、Ｎ）の等価プログラム命令を第（Ｎ―ｔ＋１）の等価プログラム命令挿入対象ブロックに挿入し、第（Ｎ―ｔ＋１）の等価プログラム命令挿入後ブロックを生成する。等価プログラム生成部１０４は、１以上の等価プログラム挿入後ブロックと、１以上の等価プログラム非挿入ブロックからなる等価プログラムを生成する（ステップＳ１２５）。
【０１４３】
１．２．３  偽装ブロック挿入後プログラムの生成処理の動作
ここでは、図１８に示す偽装ブロック挿入後プログラムの生成処理（ステップＳ２０）の動作について、図２０に示す流れ図を用いて説明する。
偽装ブロック挿入後プログラム生成部１０５は、記憶している偽装ブロック数を取得することにより、偽装ブロック数を決定する（ステップＳ２００）。
【０１４４】
偽装ブロック挿入後プログラム生成部１０５は、ブロック分割部１０２で生成した分割後ブロックの中から１以上の分割後ブロックをランダムに選択し、選択した１以上の分割後ブロックそれぞれのプログラム命令群から、分岐命令（無条件分岐命令および条件分岐命令）を取り除いたプログラム命令群と同じプログラム命令群からなるプログラム命令群を偽装ブロック本体として生成する（ステップＳ２０５）。偽装ブロック挿入後プログラム生成部１０５は、このステップを取得した偽装ブロック数分だけ行う。
【０１４５】
偽装ブロック挿入後プログラム生成部１０５は、生成した偽装ブロック本体のそれぞれに対して、偽装等価プログラム命令を生成し、生成した偽装等価プログラム命令を対応する偽装ブロック本体に挿入し、偽装ブロック数にて示される個数分の偽装等価プログラム命令挿入後偽装ブロックを生成する（ステップＳ２１０）。
偽装ブロック挿入後プログラム生成部１０５は、等価プログラム生成部１０４にて生成した等価プログラム命令挿入後ブロックそれぞれの先頭に異なるラベルを挿入し、ラベル挿入後等価プログラム命令挿入後ブロックを生成する。偽装ブロック挿入後プログラム生成部１０５は、プログラム命令非挿入ブロックそれぞれの先頭に異なるラベルを挿入し、ラベル挿入後等価プログラム命令非挿入ブロックを生成する。偽装ブロック挿入後プログラム生成部１０５は、生成した偽装等価プログラム命令挿入後偽装ブロックそれぞれの先頭に異なるラベルを追加し、ラベル挿入後偽装等価プログラム命令挿入後偽装ブロックを生成する（ステップＳ２１５）。
【０１４６】
偽装ブロック挿入後プログラム生成部１０５は、ラベル挿入後偽装等価プログラム命令挿入後偽装ブロックそれぞれの最後に無条件分岐命令を追加して、偽装ブロック数にて示される個数分のＴＭＰブロックを生成する。偽装ブロック挿入後プログラム生成部１０５は、生成した１以上のＴＭＰブロックからなるＴＭＰブロック群を生成する（ステップＳ２２０）。
【０１４７】
偽装ブロック挿入後プログラム生成部１０５は、ＴＭＰブロック群を構成するＴＭＰブロックのそれぞれと、ラベル挿入後等価プログラム挿入後ブロックのそれぞれと、ラベル挿入後等価プログラム命令非挿入ブロックのそれぞれをノードとして、グラフを生成する（ステップＳ２２５）。
偽装ブロック挿入後プログラム生成部１０５は、値「（エッジ数）−（ノード数）」が所定数以上であるか否かを判定する（ステップＳ２３０）。
【０１４８】
算出結果が所定数以上であると判定する場合には（ステップＳ２３０における「ＹＥＳ」）、偽装ブロック挿入後プログラム生成部１０５は、処理を終了する。
所定数以上でないと判定する場合には（ステップＳ２３０における「ＮＯ」）、偽装ブロック挿入後プログラム生成部１０５は、ＴＭＰブロック群を構成するＴＭＰブロックの中から条件分岐命令を挿入するＴＭＰブロックをランダムに選択し、選択したＴＭＰブロックに、条件分岐命令を挿入し、新たなＴＭＰブロックを生成して、新たなＴＭＰブロック群を更新（生成）し（ステップＳ２３５）、ステップＳ２２５へ戻る。
【０１４９】
１．３  第１の実施の形態の効果
このような構成によると、難読化されたプログラムから、秘密情報を見つけ出すことを困難にすることができる。
まず、等価プログラム命令生成部１０３、等価プログラム生成部１０４によって、秘密情報を含む命令を等価プログラム命令に置き換えプログラム上の様々な位置に配置している。このような構成により、不正解析者はプログラム中に含まれる定数値を全て収集したとしても、秘密情報を見つけることができなくなる。また、等価プログラム命令を分割後ブロックをまたがって、難読化後のプログラムの様々な位置に配置したことにより、不正解析者が等価プログラム命令を見つけ出すことを困難にすることが出来る。
【０１５０】
さらに、偽装ブロック挿入後プログラム生成部１０５で、偽装ブロックに等価プログラム命令と同じ変数を用いたプログラム命令である偽装等価プログラム命令を挿入したことで、不正解析者がプログラム中の特定の変数を用いた処理を収集したとしても、その中に等価プログラム命令と、偽装等価プログラム命令が含まれることとなり、等価プログラム命令の収集を困難にすることができる。
【０１５１】
さらに、等価プログラム命令生成部１０３で、複数の演算を組み合わせて等価プログラム命令を生成している。よって、不正解析者がプログラム中に含まれる等価プログラム命令の集合を見つけ出したとしても、見つけ出した集合の等価プログラム命令を正しい順序に並べ替えることが出来なければ、被秘匿情報の値を算出することができない。例えば、等価プログラム命令がプログラム命令「（秘密情報用変数名）＝ＲＡ＿０；」、「（秘密情報用変数名）＋＝ＲＡ＿２；」「（秘密情報用変数名）＋＝ＲＡ＿３；」であれば、２番目と３番目の処理の順番を逆にしても同じ被秘匿情報の値を算出することが出来てしまうが、実施例で述べた方法では、そのような事が起こらない。
【０１５２】
さらに、不正解析者が、難読化対象プログラム（難読化前のプログラム）のアルゴリズム、および、本難読化手法自体を知っている場合、その情報を用いて不正解析を行うことが考えられる。この詳細を説明する。
例えば、ＤＥＳ、ＡＥＳ等の暗号プログラムは広くアルゴリズムが公開されており、不正解析者が難読化対象プログラムのアルゴリズムを知ることは容易である。そのような難読化対象プログラムにおいても、被秘匿情報である暗号鍵を不正解析から保護したいという要求がある。
【０１５３】
さて、難読化対象プログラムのアルゴリズムを知る不正解析者は難読化前のプログラムのグラフを作成することができると考えることが出来る（例えば、図５のグラフ）。また、難読化後のプログラムを解析して、難読化後のプログラムのグラフを作成することができると考えることが出来る（例えば、図１２のグラフ）。
この２つのグラフを知る不正解析者が、難読化後のプログラムのグラフから、難読化前のプログラムのグラフに相当するグラフを見つけ出すことで、難読化後のプログラムから偽装ブロックを取り除いた部分を見つけ出すという不正解析が考えられる。
【０１５４】
本実施の形態では、偽装ブロック挿入後プログラム生成部１０５で、偽装ブロックに偽装分岐命令の挿入を行っていることにより、難読化後のプログラムのグラフの構成を複雑になるので、上記の不正解析が困難になる。
さらに、配置順序入替部１０８により、難読化後のプログラムのグラフの構造を複雑にすることで上記の不正解析を困難にすることができる。
【０１５５】
また、暗号鍵を有する暗号化プログラムにおいて、プログラム難読化装置は、前記暗号鍵を被秘匿情報として、暗号化プログラムを難読化するので、不正解析者は、暗号鍵を解析することが困難になる。これにより、著作権を保護すべきデータを暗号化して暗号化データを生成した場合、暗号鍵を不正に取得することが困難であるので、暗号化データを不正に解析することも困難になる。
【０１５６】
１．４  変形例１
上記第１の実施の形態では、プログラム難読化装置１０は、ＴＭＰブロック群を用いてグラフを生成したが、これに限定されない。
プログラム難読化装置は、偽装ブロック挿入後プログラム生成部１０５と、擬似分岐命令挿入後プログラム生成部１０６とを備える代わりに、偽装ブロック挿入後プログラム生成部１０５と、擬似分岐命令挿入後プログラム生成部１０６とを１つの構成要素とする擬似分岐命令挿入後プログラム生成部１０６ａを備えるとし、擬似分岐命令挿入後プログラムを用いてグラフを生成してもよい。
【０１５７】
１．４．１  擬似分岐命令挿入後プログラム生成部１０６ａ
擬似分岐命令挿入後プログラム生成部１０６ａは、偽装ブロック数の取得と、偽装ブロック本体の生成と、偽装等価プログラム命令挿入後偽装ブロックの生成と、偽装分岐命令付き偽装ブロックの生成と、ＴＭＰブロック群の生成と、擬似分岐命令挿入後プログラムの生成とを行う。
【０１５８】
なお、擬似分岐命令挿入後プログラム生成部１０６ａが行う偽装ブロック数の取得と、偽装ブロック本体の生成と、偽装等価プログラム命令挿入後偽装ブロックの生成に係る動作は、偽装ブロック挿入後プログラム生成部１０５にて示す偽装ブロック数の取得、偽装ブロック本体の生成、及び偽装等価プログラム命令挿入後偽装ブロックの生成に係る動作と同様であるため、ここでの説明は省略する。
【０１５９】
以下において、ＴＭＰブロック群の生成と、擬似分岐命令挿入後プログラムの生成とについて説明する。
（１）ＴＭＰブロック群の生成
擬似分岐命令挿入後プログラム生成部１０６ａは、等価プログラム生成部１０４にて生成した等価プログラム命令挿入後ブロックそれぞれの先頭に異なるラベルを挿入し、ラベル挿入後等価プログラム命令挿入後ブロックを生成する。
【０１６０】
擬似分岐命令挿入後プログラム生成部１０６ａは、等価プログラム命令非挿入ブロックそれぞれの先頭に異なるラベルを挿入し、ラベル挿入後等価プログラム命令非挿入ブロックを生成する。
擬似分岐命令挿入後プログラム生成部１０６ａは、生成した各々の偽装等価プログラム命令挿入後偽装ブロックの先頭に異なるラベルを追加し、ラベル挿入後偽装等価プログラム命令挿入後偽装ブロックを生成する。
【０１６１】
ここで、各ブロックに挿入するラベルのラベル名は、プログラム中で既に使用されているラベル名とは重複しないようにする。また、既に、ラベルが付与されている場合には、新たなラベルの挿入は行わない。
次に、擬似分岐命令挿入後プログラム生成部１０６ａは、ラベル挿入後偽装等価プログラム命令挿入後偽装ブロックの最後に無条件分岐命令を追加して、ＴＭＰブロックを生成する。
【０１６２】
擬似分岐命令挿入後プログラム生成部１０６ａは、ラベル挿入後偽装等価プログラム命令挿入後偽装ブロックのそれぞれに対して、ＴＭＰブロックを生成することにより、ＴＭＰブロック群を生成する。
次に、擬似分岐命令挿入後プログラム生成部１０６ａは、第ｔ（ｔ＝１、２、・・・、Ｎ）のラベル挿入後等価プログラム命令挿入後ブロックから擬似分岐命令挿入後ブロックを生成する。生成方法は、上記第１の実施の形態にて示す擬似分岐命令挿入後プログラム生成部１０６が行う生成方法と同様であるため、説明は省略する。
【０１６３】
次に、擬似分岐命令挿入後プログラム生成部１０６ａは、擬似分岐命令挿入後プログラムに含まれる各ブロックをノードと見なして、グラフを生成する。グラフの生成方法は、上記第１の実施の形態にて示す偽装ブロック挿入後プログラム生成部１０５にて示すグラフの生成方法と同様であるため説明は省略する。
擬似分岐命令挿入後プログラム生成部１０６ａは、生成したグラフに含まれる閉路数を取得し、取得した閉路数が予め定めた所定数以上であるか否かを判定する。ここで、閉路とは、始点となるノードから終点となるノードに至る経路のうち、始点と終点が同じノードである経路である。ここで、所定数とは、ユーザが所望する難読化の強度に応じて定まる数であり、例えば、「１３」である。
【０１６４】
所定数以上でないと判定する場合には、擬似分岐命令挿入後プログラム生成部１０６ａは、ラベル挿入後等価プログラム命令挿入後ブロックのそれぞれ、ラベル挿入後等価プログラム命令非挿入ブロックのそれぞれ、ＴＭＰブロックのそれぞれから、条件分岐命令を挿入する１のブロックをランダムに選択する。擬似分岐命令挿入後プログラム生成部１０６ａは、選択したブロックに、条件分岐命令を挿入し、新たなブロックを生成する。
【０１６５】
ここで、選択されたブロックが、第ｔ（ｔ＝１、２、・・・、Ｎ）のラベル挿入後等価プログラム命令挿入後ブロックである場合には、擬似分岐命令挿入後プログラム生成部１０６ａは、第１〜第（Ｎ−ｔ＋１）の等価プログラムを順次実行して、等価命令挿入後ブロック秘密情報用の変数値を算出する。擬似分岐命令挿入後プログラム生成部１０６ａは、定数ｍをランダムに選択し、秘密情報用変数ｄｋｅｙに算出した値を代入し、条件式「ｄｋｅｙ  （比較演算子）  ｍ」が偽となるように、比較演算子を決定し、決定した比較演算子を用いた擬似分岐命令「ｉｆ  （ｄｋｅｙ  （比較演算子）  ｍ）  ｔｈｅｎ  分岐先」を生成する。ここで、分岐先は、ＴＭＰブロックの先頭とする。また、条件分岐命令の挿入位置は、ブロックの最後とする。
【０１６６】
選択されたブロックが、ラベル挿入後等価プログラム命令非挿入ブロックである場合には、第１〜第Ｎの等価プログラムを順次実行して、等価命令挿入後ブロック秘密情報用の変数値を算出する。以降は、上記と同様の動作であるので、説明は省略する。また、条件分岐命令の挿入位置は、ブロックの最後とする。
選択されたブロックが、ＴＭＰブロックである場合には、上記に示す偽装ブロック挿入後プログラム生成部１０５による新たなＴＭＰブロックの生成と同様であるため、説明は省略する。また、条件分岐命令の挿入位置は、挿入対象ブロックが有する一番最初の分岐命令よりも前の位置とする。挿入対象ブロックが分岐命令を有さない場合には、挿入対象ブロックの最後に追加するものとする。
【０１６７】
擬似分岐命令挿入後プログラム生成部１０６ａは、条件分岐命令を挿入して生成した新たなブロックと、挿入を行わず変更を加えていない各ブロックとを用いて、再度、グラフ生成を行い、上記に示す動作を行う。
所定数以上であると判定する場合には、擬似分岐命令挿入後プログラム生成部１０６ａは、生成したグラフが、平面グラフ（交差を含まないグラフ）であるか否かを判定する。
【０１６８】
平面グラフでないと判定する場合には、擬似分岐命令挿入後プログラム生成部１０６ａは、動作を終了する。
平面グラフであると判定する場合には、擬似分岐命令挿入後プログラム生成部１０６ａは、ラベル挿入後等価プログラム命令挿入後ブロックのそれぞれ、ラベル挿入後等価プログラム命令非挿入ブロックのそれぞれ、ＴＭＰブロックのそれぞれから、条件分岐命令を挿入する１のブロックをランダムに選択する。擬似分岐命令挿入後プログラム生成部１０６ａは、選択したブロックに、条件分岐命令を挿入し、新たなブロックを生成する。擬似分岐命令挿入後プログラム生成部１０６ａは、条件分岐命令を挿入して生成した新たなブロックと、挿入を行わず変更を加えていない各ブロックとを用いて、再度、グラフ生成を行い、上記に示す動作を行う。
【０１６９】
なお、平面グラフに関しては、グラフ理論の分野で公知であるので、ここでの説明は省略する。
また、擬似分岐命令挿入後プログラム生成部１０６ａは、閉路数を取得する代わりに、生成したグラフのエッジ数、ノード数を数え、式「（エッジ数）―（ノード数）＋１」で算出した値を閉路数の近似値として用いてもよい。
【０１７０】
１．４．２  動作概要
ここでは、変形例１におけるプログラム難読化装置が難読化対象プログラムを難読化する動作概要について、図１８に示す流れ図を用いて変更点のみ説明する。
変形例１におけるプログラム難読化装置は、図１８に示すステップＳ５〜１５を実行後、ステップＳ２０における偽装ブロック挿入後プログラムの生成処理を行う代わりに、擬似分岐命令挿入後プログラムの生成処理を行う。
【０１７１】
変形例１におけるプログラム難読化装置は、擬似分岐命令挿入後プログラムの生成処理を実行後、ステップＳ２５を省略し、ステップＳ３０以降を行う。
１．４．３  擬似分岐命令挿入後プログラムの生成処理
ここでは、擬似分岐命令挿入後プログラムの生成処理の動作について、図２１に示す流れ図を用いて説明する。
【０１７２】
擬似分岐命令挿入後プログラム生成部１０６ａは、記憶している偽装ブロック数を取得することにより、偽装ブロック数を決定する（ステップＳ３００）。
擬似分岐命令挿入後プログラム生成部１０６ａは、分割後ブロックの中から１以上の分割後ブロックをランダムに選択し、選択した１以上の分割後ブロックそれぞれのプログラム命令群から、分岐命令（無条件分岐命令および条件分岐命令）を取り除いたプログラム命令群と同じプログラム命令群からなるプログラム命令群を偽装ブロック本体として生成する（ステップＳ３０５）。擬似分岐命令挿入後プログラム生成部１０６ａは、このステップを取得した偽装ブロック数分だけ行う。
【０１７３】
擬似分岐命令挿入後プログラム生成部１０６ａは、生成した偽装ブロック本体のそれぞれに対して、偽装等価プログラム命令を生成し、生成した偽装等価プログラム命令を対応する偽装ブロック本体に挿入し、偽装ブロック数にて示される個数分の偽装等価プログラム命令挿入後偽装ブロックを生成する（ステップＳ３１０）。
擬似分岐命令挿入後プログラム生成部１０６ａは、等価プログラム命令挿入後ブロックそれぞれの先頭に異なるラベルを挿入し、ラベル挿入後等価プログラム命令挿入後ブロックを生成、プログラム命令非挿入ブロックそれぞれの先頭に異なるラベルを挿入し、ラベル挿入後等価プログラム命令非挿入ブロックを生成、及び生成した偽装等価プログラム命令挿入後偽装ブロックそれぞれの先頭に異なるラベルを追加し、ラベル挿入後偽装等価プログラム命令挿入後偽装ブロックを生成する（ステップＳ３１５）。
【０１７４】
擬似分岐命令挿入後プログラム生成部１０６ａは、ラベル挿入後偽装等価プログラム命令挿入後偽装ブロックそれぞれの最後に無条件分岐命令を追加して、偽装ブロック数にて示される個数分のＴＭＰブロックを生成する。擬似分岐命令挿入後プログラム生成部１０６ａは、生成した１以上のＴＭＰブロックからなるＴＭＰブロック群を生成する（ステップＳ３２０）。
【０１７５】
擬似分岐命令挿入後プログラム生成部１０６ａは、第ｔ（ｔ＝１、２、・・・、Ｎ）のラベル挿入後等価プログラム命令挿入後ブロックに対応する等価命令挿入後ブロック秘密情報用の変数値を算出する（ステップＳ３２５）。算出方法は、上記第１の実施の形態にて示す擬似分岐命令挿入後プログラム生成部１０６が行う算出方法と同様であるため、説明は省略する。
【０１７６】
擬似分岐命令挿入後プログラム生成部１０６ａは、算出した変数値のそれぞれから、第ｔ（ｔ＝１、２、・・・、Ｎ）のラベル挿入後等価プログラム命令挿入後ブロックに挿入する擬似分岐命令を生成し、生成した擬似分岐命令を、挿入対象の第ｔ（ｔ＝１、２、・・・、Ｎ）のラベル挿入後等価プログラム命令挿入後ブロックに挿入して擬似分岐命令挿入後ブロックを生成する。擬似分岐命令挿入後プログラム生成部１０６ａは、擬似分岐命令挿入後ブロックのそれぞれと、ラベル挿入後等価プログラム命令非挿入ブロックのそれぞれと、偽装ブロック（ＴＭＰブロック）のそれぞれからなる擬似分岐命令挿入後プログラムを生成する（ステップＳ３３０）。
【０１７７】
擬似分岐命令挿入後プログラム生成部１０６ａは、擬似分岐命令挿入後プログラムに含まれる各ブロックをノードとしてグラフを生成する（ステップＳ３３５）。
擬似分岐命令挿入後プログラム生成部１０６ａは、生成したグラフに含まれる閉路数を取得し、取得した閉路数が予め定めた所定数以上であるか否かを判定する（ステップＳ３４０）。
【０１７８】
所定数以上であると判定する場合には（ステップＳ３４０における「ＹＥＳ」）、擬似分岐命令挿入後プログラム生成部１０６ａは、生成したグラフが、平面グラフ（交差を含まないグラフ）であるか否かを判定する（ステップＳ３４５）。
平面グラフでないと判定する場合には（ステップＳ３４５における「ＮＯ」）、擬似分岐命令挿入後プログラム生成部１０６ａは、動作を終了する。
【０１７９】
閉路数が所定数以上でないと判定する場合（ステップＳ３４０における「ＮＯ」）、及び平面グラフであると判定する場合には（ステップＳ３４５における「ＹＥＳ」）、擬似分岐命令挿入後プログラム生成部１０６ａは、擬似分岐命令挿入後ブロックのそれぞれと、ラベル挿入後等価プログラム命令非挿入ブロックのそれぞれと、偽装ブロック（ＴＭＰブロック）のそれぞれから、条件分岐命令を挿入する１のブロックをランダムに選択する。擬似分岐命令挿入後プログラム生成部１０６ａは、選択したブロックに、条件分岐命令を挿入し、新たなブロックを生成し（ステップＳ３５０）、ステップＳ３３５へ戻る。
【０１８０】
１．４．４  変形例１の効果
グラフ理論の分野では、２つのグラフＧ１、Ｇ２において、Ｇ１がＧ２に含まれるか否かを判定する問題が難しいことが部分グラフ同型判定問題として知られている。このことは非特許文献２に述べられている。
このことから、Ｇ２にＧ１が含まれることが分っていても、Ｇ２のどこにＧ１が含まれるかを判定することが難しいことが言える。また、部分グラフ同型判定問題が難しい条件として、プログラムが木構造ではないこと、プログラムが平面グラフでないことが知られる。
【０１８１】
よって、難読化後のプログラムのグラフから、難読化前のプログラムのグラフを見つけ出す部分グラフ同型判定問題が困難になる指標に基づき、難読化後のプログラムのグラフを構築すれば、先に述べた不正解析を困難にすることができる。
変形例１のプログラム難読化装置は、部分グラフ同型判定問題が困難となる難読化後のプログラムのグラフを構築することができる。
【０１８２】
なお、変形例１のプログラム難読化装置は、全ての閉路数を取得する代わりに、予め与えられた範囲のノード数からなる閉路数を取得する構成としても構わない。
また、変形例１のプログラム難読化装置は、全ての閉路数を取得する代わりに、予め難読化前のプログラムに含まれる閉路を調べ、さらに、それぞれの閉路を構成するノード数を調べ、調べたノード数と同数のノードからなる閉路数のみを数える構成としても構わない。このような構成によれば、変形例１のプログラム難読化装置はグラフの閉路数の傾向を大まかに知ることができ、また閉路数を計算する処理時間を短くすることができる。
【０１８３】
また、閉路数の判定や、平面グラフの判定の他に、非特許文献３（４４〜５０）に示されるグラフ同型判定問題の計算複雑さの指標を判定に用いても構わない。グラフ同型判定問題は、部分グラフ同型判定問題の特別な場合であると考えることが出来るので、このような指標を用いれば、部分グラフ同型判定が困難な難読化後のプログラムのグラフを生成することができる。
【０１８４】
また、ここでは、偽装ブロックを生成し部分グラフ同型判定が困難でない場合は偽装分岐を追加していく場合について述べたが、予め部分グラフ同型判定が困難になる難読化後のグラフを作成し、そのグラフに合うように偽装分岐命令を追加しても構わない。
１．４．５  その他の変形例
擬似分岐命令挿入後プログラム生成部１０６ａは、擬似分岐命令挿入後プログラムの生成において、閉路数の判定や、平面グラフの判定の双方を用いたが、これに限定されない。
【０１８５】
擬似分岐命令挿入後プログラム生成部１０６ａは、閉路数の判定、及び平面グラフの判定のうち１の判定のみを用いて、擬似分岐命令挿入後プログラムを生成してもよい。
１．５  変形例２
変形例１において、図２１に示すステップＳ３３０及びステップＳ３５０の動作を以下のように変更してもよい。
【０１８６】
１．５．１  ステップＳ３３０の変更
擬似分岐命令挿入後プログラム生成部１０６ａは、挿入する分岐命令として、プログラムの終了処理に相当するプログラム命令「ｒｅｔｕｒｎ；」、「ｅｘｉｔ（）；」を挿入する。
１．５．２  ステップＳ３５０の変更
擬似分岐命令挿入後プログラム生成部１０６ａは、挿入する条件分岐命令として、プログラムの終了処理に相当するプログラム命令「ｒｅｔｕｒｎ；」、「ｅｘｉｔ（）；」を挿入する。
【０１８７】
１．５．３  変形例２の効果
難読化前のプログラムのアルゴリズムを知る不正解析者が、難読化後のプログラムのグラフから、難読化前のプログラムのグラフを見つけ出す解析を行う際に、難読化前のプログラムと難読化後のプログラムの終了ノードを対応付けることで解析を進めることが考えられる。例えば、図５に示すグラフのノード５０１ｈと、図１２におけるノード１２０１ｈの対応を見つけることを行えば、難読化後のプログラムのグラフから、難読化前のプログラムを見つける解析が容易になる。
【０１８８】
変形例２によれば、終了ノードの候補が増えるため、難読化後のプログラムから終了ノードを見つけ出すことを困難にすることが出来る。
１．６  変形例３
難読化前のプログラムのアルゴリズムを知る不正解析者が、難読化後のプログラムのグラフから、難読化前のプログラムのグラフを見つけ出す解析を行う際に、難読化前のプログラムと難読化後のプログラムの開始ノードを対応付けることで解析を進めることが考えられる。例えば、図５に示すグラフのノード５０１ａと、図１２におけるノード１２０１ａの対応を見つけることを行えば、そこから解析が進む。変形例３は、プログラムの開始ノードの抽出を困難にするための変形例であり、変形例３のプログラム難読化装置は、上記第１の実施の形態にて示す配置順序入替部１０８を、以下に示す配置順序入替部１０８ａに変更する。
【０１８９】
１．６．１  配置順序入替部１０８ａ
配置順序入替部１０８ａは、難読化対象プログラムにおいて、プログラム中で使用されている変数名、および、引数で使用されている変数名を調べ、これらと重複しない変数名を、難読化対象プログラムに開始ノードを指定するための新たな引数である開始ノード指定用変数として、変数宣言部６０１に追加し、新たな変数宣言部６０１ａを生成する。
【０１９０】
次に、配置順序入替部１０８ａは、プログラムの先頭に、条件分岐命令であるｓｗｉｔｃｈ文を追加する。追加するｓｗｉｔｃｈ文は、開始ノード指定用変数の値によって実行するｃａｓｅ文を選択するプログラム命令とし、各ｃａｓｅ文は、開始ノードを含むノード群に対応するブロックへの先頭への分岐命令を有するようにする。
次に、配置順序入替部１０８ａは、開始ノードに対応するブロックへの先頭に分岐命令を実行する際のノード指定用変数の値を、難読化対象プログラムを呼び出す側のプログラムにおける難読化対象プログラムを呼び出すプログラム命令の引数に追加する。
【０１９１】
次に、開始ノードを含め、全てのブロックの順序をランダムに並び替えて難読化プログラムを生成する。
１．６．２  具体例
配置順序入替部１０８ａは、難読化対象プログラムにおいて、プログラム中で使用されている変数名、および、引数で使用されている変数名を調べ、これと重複しない変数名を開始ノード指定用変数とする。ここでは、開始ノード指定用変数を「ｓｔａｒｔ」とする。
【０１９２】
次に、プログラムの先頭にｓｗｉｔｃｈ文を追加する。
追加するｓｗｉｔｃｈ文にあたるプログラム命令を
「
ｓｗｔｉｃｈ（ｓｔａｒｔ）｛
ｃａｓｅ  １：
ｇｏｔｏ  ｌａｂｅｌＣ；
ｃａｓｅ  ２：
ｇｏｔｏ  ｌａｂｅｌＡ；
ｃａｓｅ  ３：
ｇｏｔｏ  ｌａｂｅｌＬ；
ｄｅｆａｕｌｔ：
｝
」
とする。
【０１９３】
次に、関数宣言および関数名を「ｆｕｎｃ（ｉｎｔ  ａ，ｉｎｔ  ｂ）」から「ｆｕｎｃ（ｉｎｔ  ａ，ｉｎｔ  ｂ，ｉｎｔ  ｓｔａｒｔ）」に置き換える。
また、難読化対象を呼び出すプログラム命令が「ｆｕｎｃ（ａ，ｂ）；」であるならば、これを「ｆｕｎｃ（ａ，ｂ，２）；」に置き換える。ここで、値「２」は、ｓｗｉｔｃｈ文に用いられる開始ノード指定用変数「ｓｔａｒｔ」に格納される数値である。なお、難読化対象プログラムを呼び出す側のプログラムを別途難読化して、開始ノード指定用変数がとる値「２」を隠蔽するなどを行ってもよい。
【０１９４】
１．６．３  変形例３の効果
このような難読化を適用することにより、開始ノード指定用変数ｓｔａｒｔに格納される正しい値が分からなくては開始ノードがどれであるのかが分からなくなる。すなわち、難読化対象プログラムを局所的に解析したのでは、開始ノードがわからなくなり難読化前のプログラムのグラフと難読化後のプログラムのグラフにおいて開始ノードの対応を取ることを困難にすることが出来る。
【０１９５】
１．７  変形例４
上記第１の実施の形態において、難読化後プログラムにおいて秘密情報用変数が右辺にのみ存在するプログラム命令は、被秘匿情報位置のプログラム命令のみである（図１７では、被入替ブロック１５０１ｅ）。そのため、難読化前のプログラムのアルゴリズムを知る不正解析者が難読化前のプログラムのグラフにおいて被秘匿情報位置となるノード（図５では、ノード５０１ｅ）と難読化後のプログラムにおける秘密情報用変数が右辺にのみ存在するブロックとの対応を取って、不正解析を行うことが考えられる。
【０１９６】
そこで、変形例４のプログラム難読化装置は、偽装ブロック本体生成の際に秘密情報用変数が右辺にのみ存在するプログラム命令を追加してもよい。これにより、変形例４のプログラム難読化装置は、上記の不正解析を困難にすることができる。
また、変形例４のプログラム難読化装置は、等価プログラム命令挿入後ブロックにおいて、右辺に定数がある命令における定数を、算出した等価命令挿入後ブロック秘密情報用の変数値を用いて算出するプログラム命令に置き換えてもよい。これにより、右辺に秘密情報用変数を含むプログラム命令の数が増えるので、変形例４のプログラム難読化装置は、上記の不正解析を困難にすることができる。
【０１９７】
１．８  変形例５
難読化前のプログラムに特徴的な演算、特徴的な数値を用いた演算（例えば、暗号プログラムのアルゴリズムにおけるループの回数など）が含まれる場合がある。そのため、難読化前のプログラムのアルゴリズムを知る不正解析者が難読化前のプログラムにおいて、特徴的な演算または数値を見つけ難読化前のグラフと難読化後のグラフにおいて対応が取れるノードを見つける手がかりにすることが考えられる。
【０１９８】
そこで、特徴的な演算を別の処理に置き換えることで、上記の解析を困難にすることを行ってもよい。このような方法については、非特許文献１に述べられている。
また、特徴的な数値も、秘密情報として扱い本手法で述べた難読化方法や他の難読化方法により隠蔽しても構わない。
１．９  その他の変形例
１．９．１  Ｃ言語以外
上記第１の実施の形態では、秘密情報を保持するプログラムがＣ言語の場合を示したが、これに限定されない。Ｊａｖａ（登録商標）バイトコード、Ｊａｖａ（登録商標）言語、アセンブリ言語、機械語などで記述されたプログラムであってもよい。
【０１９９】
Ｊａｖａ（登録商標）バイトコードの場合、Ｃ言語のプログラム命令「ｇｏｔｏ」文を生成する処理では、プログラム命令「ｇｏｔｏ」、「ｇｏｔｏ＿ｗ」を使用する。プログラム命令「ｇｏｔｏ」、「ｇｏｔｏ＿ｗ」の使い分けについては、公知であるため、ここでの説明は省略する。
その他の生成する命令については、Ｊａｖａ（登録商標）バイトコードにおける記述方法にのっとり、同等の命令を生成する。
【０２００】
また、無条件分岐命令を見つける処理では、Ｊａｖａ（登録商標）バイトコードにおける無条件分岐を、条件分岐命令を見つける処理では、Ｊａｖａ（登録商標）バイトコードにおける複合分岐、条件分岐をみつける。
また、Ｊａｖａ（登録商標）言語に適用する際には、Ｊａｖａ（登録商標）言語にプログラム命令「ｇｏｔｏ」に対応する命令がない。よって、各ブロックをメソッドとして生成し、プログラムの出口となるプログラム命令を含むメソッドには例外をスローされるプログラム命令を追加し、プログラムの入口となる命令を含むメソッドにはスローした例外をキャッチするプログラム命令を追加する。メソッド、例外の記述仕方は公知であるため説明は省略する。
【０２０１】
その他の生成する命令については、Ｊａｖａ（登録商標）言語における記述方法にのっとり、同等の命令を生成する。
Ｊａｖａ（登録商標）言語において、無条件分岐命令を見つける処理では、プログラム命令「ｂｒｅａｋ」、「ｃｏｎｔｉｎｕｅ」，「ｒｅｔｕｒｎ」、「ｔｈｒｏｗ」を見つける。
【０２０２】
条件分岐命令を見つける処理では、「ｉｆ−ｅｌｓｅ」「ｓｗｉｔｃｈ」、「ｗｈｉｌｅ」、「ｄｏ−ｗｈｉｌｅ」、「ｆｏｒ」、「ｔｒｙ、ｃａｔｃｈ，ｆｉｎａｌｌｙ」を見つける。なお、これらのプログラム命令については、公知であるため説明は省略する。
アセンブリ言語の場合、用いるアセンブラ言語によって命令セットは異なるが、例えばＧＡＳによるアセンブル言語の場合、Ｃ言語のプログラム命令「ｇｏｔｏ」文を生成する処理では、プログラム命令「ｊｍｐ」を使用する。
【０２０３】
また、無条件分岐命令を見つける処理では、プログラム命令「ｊｍｐ」、「ｃａｌｌ」、「ｒｅｔ」、「ｈｌｔ」を見つける。
条件分岐命令を見つける処理では、「ｊｍｐ」以外のジャンプ命令を見つける。なお、ＧＡＳのアセンブリ言語については、公知であるため説明は省略する。
機械語については、用いる機械語によって命令セットは異なるが、それぞれの記述方法にのっとり記述する。
【０２０４】
なお、機械語を用いる場合、変形例３に述べたｓｗｉｔｃｈ文の生成の代わりに以下の処理を用いた構成としてもよい。すなわち、ｓｗｉｔｃｈ文を生成する代わりに、引数として開始ノード指定用変数を用いた相対ジャンプ命令（引数として指定された変数の値の分だけプログラムカウンタを動かす命令）を生成する。開始ノード指定用変数には、ｓｗｉｔｃｈ文のｃａｓｅ文で使用する値を設定する代わりに、生成した相対ジャンプ命令で開始ノードに対応するアドレスにジャンプできるような値を設定する。
【０２０５】
１．９．２  ブロック分割
上記第１の実施の形態では、ブロック分割の際に基本ブロックに分割した後、さらに分割後ブロックを生成したが、基本ブロックへの分割を行わず、行数のみに基づく分割により分割後ブロックの生成を行っても良い。
このような構成を取る場合には、プログラム難読化装置は、等価プログラム命令を挿入する際に、等価プログラム命令挿入対象ブロックに含まれる一番最初の分岐命令よりも前に、さらに、一番最後の合流位置よりも後に等価プログラム命令を挿入する。
【０２０６】
１．１０  その他の変形例
なお、本発明を上記の実施の形態に基づいて説明してきたが、本発明は、上記の実施の形態に限定されないのはもちろんである。以下のような場合も本発明に含まれる。
（１）上記第１の実施の形態において、プログラム難読化装置１０が受け付ける位置情報は、難読化対象プログラムにおける秘密情報を保持するプログラム命令の行番号であるとしたが、これに限定されない。
【０２０７】
位置情報は、定数のマクロの名前を用いて指定してもよい。すなわち、予め定められた所定の名前のマクロを有するプログラム命令を位置情報として扱う構成としてもよい。
または、位置情報は、ラベルを用いて指定してもよい。すなわち、予め定められた所定の名前のラベルがあるプログラム上の行の次の行を被秘匿情報として扱う構成としてもよい。
【０２０８】
または、ここで述べた所定の名前のマクロ／ラベルの変わりに、予め定められた所定の接頭語、接尾語を有するマクロ／ラベルを用いて位置情報を指定する構成としても構わない。
（２）上記第１の実施の形態において、プログラム難読化装置１０は、偽装ブロック数を予め記憶するとしたが、これに限定されない。
【０２０９】
プログラム難読化装置１０は、難読化対象プログラムの複雑度をｅとし、下式を用いて、偽装ブロック数を取得しても構わない。
（生成する偽装ブロック数）＝（所定数）−ｅ
ここで、複雑度は、プログラムに含まれるプログラム命令数や、ループ数や、プログラムに使用される変数の数、またはそれらの組み合わせ等でプログラムの複雑さを指標化した値であり、バグが発生しやすいプログラムを見つけ出す際などに使用される。
【０２１０】
ここで、所定数とは、ユーザが所望する難読化の強度に応じて定まる数である。
ここで、所定数の決定について説明する。所定数と、難読化の強度との関係は、図２２に示すように、強度が増加すると、所定数は単調に増加する（図２２に示す関数Ｇ３００）。グラフＧ３００は、ｙ＝ａＸ＋ｂにて示される。これにより、ユーザが所望する強度が決定すると、一意的に所定数が決定することになる。プログラム難読化装置は、決定した所定数から難読化対象プログラムの複雑度ｅを減算することにより得られた結果を、偽装ブロック数とする。
【０２１１】
または、決定したノード数から分割後ブロックの個数を減算した結果を偽装ブロック数としてもよい。
（３）上記第１の実施の形態において、プログラム難読化装置１０は、ユーザが所望する難読化の強度に応じて定まる数である所定数を予め記憶しているとしたが、これに限定されない。
【０２１２】
プログラム難読化装置１０は、プログラムを難読化する度に、難読化の強度の指定を、入力部１０１にて受け付け、指定された強度に応じた所定数を用いて難読化を行ってもよい。
または、プログラム難読化装置１０は、プログラムを難読化する度に、難読化の強度に応じた所定数を、入力部１０１にて受け付け、受け付けた所定数を用いて難読化を行ってもよい。
【０２１３】
または、プログラム難読化装置１０は、プログラムを難読化する度に、他のプログラムから難読化の強度の指定を受け付け、指定された強度に応じた所定数を用いて難読化を行ってもよい。
または、プログラム難読化装置１０は、プログラムを難読化する度に、他のプログラムから難読化の強度に応じた所定数を受け付け、受け付けた所定数を用いて難読化を行ってもよい。
【０２１４】
（４）上記第１の実施の形態において、プログラム難読化装置１０は、全ての偽装ブロック本体のそれぞれに対して、偽装等価プログラム命令を挿入して、偽装等価プログラム命令挿入後偽装ブロックを生成したが、これに限定されない。
プログラム難読化装置１０は、生成した複数の偽装ブロック本体のうち１以上の偽装ブロック本体に、偽装等価プログラム命令を挿入して、偽装等価プログラム命令挿入後偽装ブロックを生成してもよい。
【０２１５】
（５）上記第１の実施の形態において、プログラム難読化装置１０は、擬似分岐命令挿入後プログラムから、ブロック分割部を用いて１以上の分割後ブロックを生成し、生成した１以上の分割後ブロックから被入替ブロック群を生成してもよい。
または、擬似分岐命令挿入後プログラムに含まれる正常系の動作により実行される１以上のブロックからなる部分プログラムから、ブロック分割部を用いて１以上の分割後ブロックを生成し、生成した１以上の分割後ブロックと、擬似分岐命令挿入後プログラムに含まれる正常系の動作により実行されない１以上のブロック（偽装ブロックに相当する）とから被入替ブロック群を生成してもよい。
【０２１６】
（６）上記第１の実施の形態及び変形例において、グラフの難易度（強度）を示す指標の例として、「（エッジ数）−（ノード数）」、閉路数、平面グラフを用いたが、これに限定されない。
グラフの難易度を示す指標として、第１の所定数以上のノードからなる閉路の数としてもよい。このとき、プログラム難読化装置１０は、例えば、第１の所定数として「３」、閉路数の最小値を示す第２の所定数として「４」を予め記憶している。
【０２１７】
プログラム難読化装置１０の偽装ブロック挿入後プログラム生成部１０５は、生成したグラフから３個以上のノードからなる閉路を全て取得する。
偽装ブロック挿入後プログラム生成部１０５は、取得した閉路数が、第２の所定数以上であるか否かを判定する。
閉路数が所定数以上であると判定する場合には、偽装ブロック挿入後プログラム生成部１０５は、処理を中止する。
【０２１８】
所定数以上でないと判定する場合には、偽装ブロック挿入後プログラム生成部１０５は、第１の実施の形態と同様に、ＴＭＰブロック群を構成するＴＭＰブロックの中から条件分岐命令を挿入するＴＭＰブロックをランダムに選択し、選択したＴＭＰブロックから新たなＴＭＰブロックを生成する。
（７）上記第１の実施の形態において、被秘匿情報は、定数としたがこれに限定されない。被秘匿情報は、１以上のプログラム命令からなる命令群であってもよい。
【０２１９】
例えば、分岐命令による分岐先を被秘匿情報としてもよい。具体的には、分岐命令「ｇｏｔｏ  ｌａｂｅｌ  Ｄ；」の分岐先「ｌａｂｅｌ  Ｄ」を被秘匿情報とする場合、「ｘ＝０；」、「ｘ＝ｘ＋３」、「ｉｆ  （ｘ＝＝２）  ｔｈｅｎ  ｇｏｔｏ  ｌａｂｅｌ  Ｂ；」、及び「ｉｆ  （ｘ＝＝３）  ｔｈｅｎ  ｇｏｔｏ  ｌａｂｅｌ  Ｄ；」に分解しても良い。このとき、偽装ブロックには、例えば、変数ｘを用いた演算式、ラベルＤへ分岐する命令、及び変数ｘに格納された値に応じて分岐先を変更する命令等のうち少なくとも１のプログラム命令が追加される。追加されるプログラム命令の具体例は、「ｘ＝ｘ＋５；」、「ｉｆ  （ｘ＝＝５）  ｔｈｅｎ  ｇｏｔｏ  ｌａｂｅｌ  Ｄ；」、及び「ｉｆ  （ｘ＝＝４）  ｔｈｅｎ  ｇｏｔｏ  ｌａｂｅｌ  Ａ；」である。ここで、プログラム命令の概念には、演算式も含まれる。また、上記に記載の「ｌａｂｅｌ  Ａ」及び「ｌａｂｅｌ  Ｂ」は、例えば、難読化対象プログラムに記載されているラベル名である。
【０２２０】
また、例えば、２つのプログラム命令「ａ＝ａ＊１０；ａ＝ａ＋５；」を被秘匿情報とし、プログラム難読化装置は、これらから等価プログラム命令として、「ａ＝ａ＊２；」、「ａ＝ａ＋１；」、「ａ＝ａ＊５；」を３つ生成する。このとき、偽装ブロックには、変数ａを用いた演算式が追加される。例えば、「ａ＝ａ＊５＋２；」である。
（８）上記第１の実施の形態において、秘密情報用変数を用いたが、これに限定されない。秘密情報用変数を用いなくてもよい。
【０２２１】
例えば、「ｂ＝ａ＾３」を被秘匿情報とし、これを、「ｂ＝ａ；」、「ｂ＝ｂ＊ａ＋４；」、「ｂ＝（ｂ−４）＊ａ；」と分解してもよい。このとき、偽装ブロックには、例えば、変数ａ、ｂの双方を用いた演算式、若しくはその一方を用いた演算式のうち少なくとも１の演算式が追加される。追加される演算式の具体例は、「ｂ＝ｂ＊ａ−６；」、「ｂ＝ｂ＋２；」、「ａ＝ａ＋１；」である。
【０２２２】
また、例えば、「ｂ＝９；」を、「値８をファイルＡに書き込む命令」、「ファイルＡを読み込む命令」、「読み込んだ値を変数ｂに代入する命令」、「読み込んだ値が代入された変数ｂに１を加算する命令」に分解してもよい。または、「値８をファイルＡに書き込む命令」、「ファイルＡを読み込む命令」、「読み込んだ値を変数ｃに代入する命令」、「読み込んだ値が代入された変数ｃに１を加算する命令」、及び「加算結果を変数ｂに代入する命令」に分解してもよい。このとき、偽装ブロックには、例えば、変数ｂを用いた演算式、ファイルＡの書き込み命令又はファイルＡの読み込み命令、ファイルＡを読み込み、読み込んだ値を変数ｂに代入する命令等のうち少なくとも１のプログラム命令が追加される。追加される演算式の具体例は、「ｂ＝ｂ＊３＋１；」、「値３をファイルＡにｗｒｉｔｅ；」、「ｂ＝ｒｅａｄ関数（ファイルＡの読み込み）；」である。ここで、プログラム命令の概念には、演算式も含まれる。
【０２２３】
（９）上記第１の実施の形態において、プログラム難読化装置は、複数の分割後ブロックと、１以上の偽装等価プログラム命令挿入後偽装ブロックとを用いて、被入替ブロック群を生成してもよい。また、分割後ブロックのそれぞれに、ラベル名を付与してもよい。
または、プログラム難読化装置は、複数の分割後ブロックと、１以上のＴＭＰブロックとを用いて、被入替ブロック群を生成してもよい。また、分割後ブロックのそれぞれに、ラベル名を付与してもよい。
【０２２４】
（１０）上記第１の実施の形態において、配置順序入替部１０８は、開始ノードとなる被入替ブロックを除く他の被入替ブロックの配置順序を、ランダムに入れ替えたが、これに限定されない。
配置順序入替部１０８は、開始ノードとなる被入替ブロックを含めた全ての被入替ブロックの配置順序を、ランダムに入れ替えてもよい。このとき、配置順序入替部１０８は、入替結果により、プログラムに含まれる処理部の先頭位置に、偽装ブロックである被入替ブロックが存在する場合には、その被入替ブロックの先頭に、常に処理群Ａを含む被入替ブロック（開始ノードとなるブロック）に分岐する無条件分岐命令又は条件分岐命令を挿入する。
【０２２５】
これにより、プログラムの開始位置に偽装ブロックが存在する場合でも、難読化プログラムは、常に正しいブロックから実行される。
（１１）上記第１の実施の形態において、プログラム難読化装置１０は、等価プログラム命令の挿入対象ブロックに対して、１の等価プログラム命令を挿入したが、これに限定されない。プログラム難読化装置１０は、挿入対象ブロックに対して、２以上の等価プログラム命令を挿入してもよい。
【０２２６】
（１２）上記第１の実施の形態において、プログラム難読化装置１０は、開始ノードであるブロックから、秘密保有ノードであるブロックまでに存在する各ブロックに、等価プログラム命令を挿入したが、これに限定されない。プログラム難読化装置１０は、開始ノードであるブロックから、秘密保有ノードであるブロックまでに存在する各ブロックのうち１以上のブロックに、等価プログラム命令を順次挿入してもよい。
【０２２７】
（１３）上記第１の実施の形態において、プログラム難読化装置１０は、難読化対象プログラムを、複数の分割後ブロックに分割した後、等価プログラム命令を挿入したが、これに限定されない。プログラム難読化装置１０は、難読化対象プログラムにおいて最初に実行されるプログラム命令から、被秘匿情報を含むプログラム命令までの間に、生成した第１〜第Ｎの等価プログラム命令を挿入してもよい。
【０２２８】
このとき、プログラム難読化装置１０は、第１〜第Ｎの等価プログラム命令を挿入後、複数の分割後ブロックに分割してもよい。または、プログラム難読化装置１０は、第１〜第Ｎの等価プログラム命令を挿入後、さらに、偽装ブロックを挿入し、挿入した偽装ブロックを常に迂回する分岐命令を挿入する。この場合、プログラム難読化装置１０は、例えば、挿入された偽装ブロックの直後に、ラベルを付与し、挿入する分岐命令の分岐先は、付与したラベルを示すようにする。
【０２２９】
ここで、偽装ブロックを迂回する分岐命令とは、偽装ブロックに含まれる全てのプログラム命令を実行しないように、偽装ブロックに含まれない他のプログラム命令へ分岐することを示す命令である。
（１４）上記第１の実施の形態において、プログラム難読化装置１０は、被秘匿情報の値を秘密情報用変数に置き換え、その後、等価プログラム命令挿入対象ブロックのそれぞれに対応する等価プログラム命令を挿入したが、これに限定されない。
【０２３０】
プログラム難読化装置１０は、等価プログラム命令挿入対象ブロックのそれぞれに対応する等価プログラム命令を挿入後、被秘匿情報の値を秘密情報用変数に置き換えてもよい。
（１５）上記第１の実施の形態において、正常系での実行に全ての命令が必要なプログラムを難読化している。そのため、難読化後のプログラムが正常系で適切に動作することを保証するために、各分割後ブロック（以下、単に、「ブロック」という。）の最後に、次に実行すべきブロックの先頭への分岐命令を挿入する必要がある。
【０２３１】
しかし、以下のような場合には、このような分岐命令の挿入の仕方を取る必要はない。
例えば、入力として与えられるプログラムに、正常系では必要のないダミーの命令が既に含まれている場合、プログラムの分割の仕方によっては、ブロックの先頭にダミーの命令が含まれたり、最後にダミーの命令が含まれたりする可能性がある。このような事態は、他の難読化手法により難読化された後のプログラムを、本発明による手法で、さらに難読化を行う場合などが考えられる。
【０２３２】
このようなプログラムが入力として与えられる場合、ダミーの命令については実行を省略しても正常系での動作に影響はないため、正常系で必要な命令が始まる箇所を分岐先とした分岐命令を挿入することで、ブロックの先頭にあるダミーの命令の実行を省略してもよい。
また、正常系で必要な命令が終わる箇所に分岐命令を挿入することで、ブロックの最後にあるダミーの命令の実行を省略してもよい。
【０２３３】
（１６）また、偽装ブロックに挿入する分岐命令や、常に分岐先に分岐しない条件分岐命令の分岐先については、どこに分岐するとして正常系での実行に影響はない。したがって、これらの命令については、ブロックの先頭に分岐する分岐命令とする必要がなく、ブロックの途中に分岐するとしてもよい。
（１７）本発明における命令群とは、１以上の命令からなるものとする。つまり、本発明における命令群は、１の命令からなる場合も含まれる。
【０２３４】
（１８）上記の各装置は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスクユニット、ディスプレィユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記ＲＡＭ又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。ここで、コンピュータプログラムは、所定の機能を達成するために、コンピュータに対する指令を示す命令コードが複数個組み合わされて構成されたものである。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、各装置は、その機能を達成する。つまり、前記マイクロプロセッサは、前記コンピュータプログラムに含まれる各命令を１個ずつ読み出し、読み出した命令を解読し、解読結果に従って動作する。
【０２３５】
（１９）上記の各装置を構成する構成要素の一部又は全部は、１個のシステムＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ：大規模集積回路）から構成されているとしてもよい。システムＬＳＩは、複数の構成部を１個のチップ上に集積して製造された超多機能ＬＳＩであり、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどを含んで構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、システムＬＳＩは、その機能を達成する。
【０２３６】
ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路又は汎用プロセサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用しても良い。
【０２３７】
さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術の適応等が可能性としてありえる。
（２０）上記の各装置を構成する構成要素の一部又は全部は、各装置に脱着可能なＩＣカード又は単体のモジュールから構成されているとしてもよい。前記ＩＣカード又は前記モジュールは、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、などから構成されるコンピュータシステムである。前記ＩＣカード又は前記モジュールは、上記の超多機能ＬＳＩを含むとしてもよい。マイクロプロセッサが、コンピュータプログラムに従って動作することにより、前記ＩＣカード又は前記モジュールは、その機能を達成する。このＩＣカード又はこのモジュールは、耐タンパ性を有するとしてもよい。
【０２３８】
（２１）本発明は、上記に示す方法であるとしてもよい。また、これらの方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるデジタル信号であるとしてもよい。
また、本発明は、前記コンピュータプログラム又は前記デジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フレキシブルディスク、ハードディスク、ＣＤ―ＲＯＭ、ＭＯ、ＤＶＤ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＢＤ（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ）、半導体メモリなど、に記録したものとしてもよい。また、これらの記録媒体に記録されている前記コンピュータプログラム又は前記デジタル信号であるとしてもよい。
【０２３９】
また、本発明は、前記コンピュータプログラム又は前記デジタル信号を、電気通信回線、無線又は有線通信回線、インターネットを代表とするネットワーク、データ放送等を経由して伝送するものとしてもよい。
また、本発明は、マイクロプロセッサとメモリとを備えたコンピュータシステムであって、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムに従って動作するとしてもよい。
【０２４０】
また、前記プログラム又は前記デジタル信号を前記記録媒体に記録して移送することにより、又は前記プログラム又は前記デジタル信号を前記ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実施するとしてもよい。
（２２）上記実施の形態及び上記変形例をそれぞれ組み合わせるとしてもよい。
１．１１  まとめ
（１）本発明は、プログラムを難読化するプログラム難読化装置であって、  第一の入力プログラムにおける被秘匿情報を使用するプログラム命令または被秘匿命令を含む少なくとも一つ以上のプログラム命令からなる第一のプログラム命令群と同等の機能を有する、第二のプログラム命令群を生成する等価プログラム命令群生成手段と、前記第一の入力プログラムから前記第一のプログラム命令群を取り除き、前記第二のプログラム命令群を挿入して第一の出力プログラムを生成する等価プログラム生成手段と、  正常系の実行結果を得るための任意の実行時には、実行されない１以上のプログラム命令からなる偽装ブロックを生成し、第二の入力プログラムに前記偽装ブロックを挿入し第二の出力プログラムを生成する偽装ブロック挿入後プログラム生成手段とを有し、  少なくとも一つの前記偽装ブロックのプログラム命令の少なくとも一つは、前記第二のプログラム命令群を構成するプログラム命令が使用する変数を用いることを特徴とする。
【０２４１】
（２）ここで、上記（１）に示すプログラム難読化装置において、前記偽装ブロックの少なくとも一つは、前記第二の入力プログラムのいずれかのプログラム命令への分岐命令を有するとしてもよい。
（３）ここで、上記（２）に示すプログラム難読化装置は、さらに、第三の入力プログラムを、１以上のプログラム命令から構成される分割後ブロックに分割するプログラム分割手段を有し、前記偽装ブロック挿入後プログラム生成手段は、前記分割後ブロックのそれぞれと前記偽装ブロックのそれぞれをノードと見なし、第一の前記ノードに第二の前記ノードへの分岐命令がある場合に前記第一の前記ノードと前記第二の前記ノードの間にはエッジが存在すると見なし、また、前記第一の前記ノードの最後のプログラム命令が無条件分岐命令以外のプログラム命令であって、前記最後のプログラム命令に対応する前記第二の入力プログラムのプログラム命令の一つ後のプログラム命令が対応する前記ノードが前記第二の前記ノードであった場合に、前記第一の前記ノードと前記第二の前記ノードの間にはエッジが存在すると見なし、前記ノードと前記エッジからなるグラフにおいて、閉路が予め与えられた第一の所定数以上となるように前記偽装ブロックを生成するとしてもよい。
【０２４２】
（４）ここで、上記（３）にて示すプログラム難読化装置は、さらに、前記与えられた第一の所定数を入力する入力手段を有するとしてもよい。
（５）ここで、上記（２）に示すプログラム難読化装置は、さらに、前記第二の入力プログラムを、１以上のプログラム命令から構成されるプログラム命令群である分割後ブロックに分割するプログラム分割手段を有し、前記偽装ブロック挿入後プログラム生成手段は、  前記分割後ブロックのそれぞれと前記偽装ブロックのそれぞれをノードと見なし、第一の前記ノードに第二の前記ノードへの分岐命令がある場合に前記第一の前記ノードと前記第二の前記ノードの間にはエッジが存在すると見なし、また、前記第一の前記ノードの最後のプログラム命令が無条件分岐命令以外のプログラム命令であって、前記最後のプログラム命令に対応する前記第二の入力プログラムのプログラム命令の一つ後のプログラム命令が対応する前記ノードが前記第二の前記ノードであった場合に、前記第一の前記ノードと前記第二の前記ノードの間にはエッジが存在すると見なし、前記ノードと前記エッジからなるグラフにおいて、予め与えられた第一の所定数以上のノード数からなる閉路の数が予め与えられた第二の所定数以上となるように偽装ブロックを生成するとしてもよい。
【０２４３】
（６）ここで、上記（５）に示すプログラム難読化装置は、さらに、前記与えられた第一の所定数を入力する入力手段を有するとしてもよい。
（７）ここで、上記（５）に示すプログラム難読化装置は、さらに、前記与えられた第二の所定数を入力する入力手段を有するとしてもよい。
（８）ここで、上記（２）に示すプログラム難読化装置において、前記偽装ブロック挿入後プログラム生成手段は、さらに、前記第二のプログラムを、１以上のプログラム命令から構成されるプログラム命令群である分割後ブロックに分割するプログラム分割手段を有し、前記偽装ブロック挿入後プログラム生成手段は、前記分割後ブロックのそれぞれをノードと見なし、第一の前記ノードに第二の前記ノードへの分岐命令がある場合、前記第一の前記ノードと前記第二の前記ノードの間にはエッジが存在すると見なし、また、前記第一の前記ノードの最後のプログラム命令が無条件分岐命令以外のプログラム命令であって、前記最後のプログラム命令が対応する前記第二の入力プログラムのプログラム命令の一つ後のプログラム命令が対応する前記ノードブロックが前記第二の前記ノードであった場合に、第一の前記ノードと第二の前記ノードの間にはエッジが存在すると見なし、前記ノードと前記エッジからなる第一のグラフを生成し、前記ノードブロックのそれぞれと前記偽装ブロックのそれぞれをノードと見なし、第一の前記ノードに第二の前記ノードへの分岐命令がある場合、前記第一の前記ノードと前記第二の前記ノードの間にはエッジが存在すると見なし、また、前記第一の前記ノードの最後のプログラム命令が無条件分岐命令以外のプログラム命令であって、前記最後のプログラム命令が対応する前記第二の入力プログラムのプログラム命令の一つ後のプログラム命令が対応する前記ノードブロックが前記第二の前記ノードであった場合に、第一の前記ノードと第二の前記ノードの間にはエッジが存在すると見なし、前記ノードと前記エッジからなる第二のグラフを生成し、前記第二のグラフから前記第一のグラフを見つけ出す部分グラフ同型判定問題の難易度が予め与えられた第一の所定数以上になるように偽装ブロックを生成するとしてもよい。
【０２４４】
（９）ここで、上記（８）に示すプログラム難読化装置は、さらに、前記与えられた第一の所定数を入力する入力手段を有するとしてもよい。
（１０）ここで、上記（１）又は（２）に示すプログラム難読化装置は、さらに、第三の入力プログラムを任意の位置で第一のブロックと第二のブロックに分割し、正常系の実行結果を得るための任意の実行時には、真偽値が一定の第一の値となる分岐条件によって分岐先を決定する条件分岐命令を前記第一のブロックの最後に追加して第三のブロックを生成し、  前記第三のブロックと前記第二のブロックからなる第三の出力プログラムを生成する擬似分岐命令挿入後プログラム生成手段を有し、前記条件分岐命令は、前記分岐条件が前記第一の値を取る場合の分岐先が前記第二のブロックの先頭であるとしてもよい。
【０２４５】
（１１）ここで、上記（１）に示すプログラム難読化装置において、前記等価プログラム命令群生成手段は、前記第一の出力プログラムに含まれる前記第二のプログラム命令群を構成する少なくとも一組の二つのプログラム命令を入れ替えたプログラムが、正常系のいずれかの実行時には前記第一の出力プログラムと機能が異なる前記第二のプログラム命令群を生成するとしてもよい。
【０２４６】
（１２）ここで、上記（１）又は（２）に示すプログラム難読化装置は、さらに、第四の入力プログラムを１以上のプログラム命令から構成される細分化ブロックに分割する細分化ブロック生成手段と、各々の前記細分化ブロックから被入替ブロックを生成する被入替ブロック生成手段と、前記被入替ブロックの配置順序を変えて、第四の出力プログラムを生成する配置順序入替後プログラム生成手段配置順序入替後プログラム生成手段とを有し、前記被入替ブロック生成手段は、第一の前記細分化ブロックの最後のプログラム命令が対応する前記第四の入力プログラムのプログラム命令の、次のプログラム命令が対応する前記第二の前記細分化ブロックへの分岐命令を、前記第一の前記細分化ブロックの最後に追加して被入替ブロックとするとしてもよい。
【０２４７】
（１３）ここで、上記（１２）に示すプログラム難読化装置において、前記被入替ブロック生成手段は、前記第一の前記細分化ブロックの最後のプログラム命令が無条件分岐でない場合に、前記第四の入力プログラムのプログラム命令の、次のプログラム命令が対応する前記第二の前記細分化ブロックへの分岐命令を、前記第一の前記細分化ブロックの最後に追加したものを被入替ブロックとするとしてもよい。
【０２４８】
（１４）ここで、上記（１）又は（２）に示すプログラム難読化装置は、さらに、前記偽装ブロックを含む第四の入力プログラムにおいて、前記偽装ブロック以外に存在するプログラム命令からなるプログラム命令群を１以上のプログラム命令から構成される細分化ブロックに分割して細分化ブロックを生成する細分化ブロック生成手段と、前記細分化ブロックまたは前記偽装ブロックである小ブロックから被入替ブロックを生成する被入替ブロック生成手段と、前記被入替ブロックの配置順序を変えて、第四の出力プログラムを生成する配置順序入替後プログラム生成手段配置順序入替後プログラム生成手段とを有し、前記被入替ブロック生成手段は、第一の前記小ブロックの最後のプログラム命令が対応する前記第四の入力プログラムのプログラム命令の、次のプログラム命令が対応する前記第二の前記小ブロックへの分岐命令を、前記第一の前記小ブロックの最後に追加したものを被入替ブロックとするとしてもよい。
【０２４９】
（１５）ここで、上記（１）又は（２）に示すプログラム難読化装置は、さらに、第四の入力プログラムを構成する偽装ブロックの各々と、分割後ブロックの各々を細分化ブロックとし、各々の前記細分化ブロックから被入れ替えブロックを生成する被入替ブロック生成手段と、前記被入替ブロックの配置順序を変えて、第四の出力プログラムを生成する配置順序入替後プログラム生成手段とを有し、前記被入替ブロック生成手段は、第一の前記細分化ブロックの最後のプログラム命令が対応する前記第二の入力プログラムの次のプログラム命令が対応する第二の細分化ブロックへの分岐命令を、前記第一の細分化ブロックの最後に追加したものを被入替ブロックとするとしてもよい。
【産業上の利用可能性】
【０２５０】
上記にて示したプログラム難読化装置は、電器機器製造産業において、経営的に、また継続的及び反復的に、製造し、販売することができる。また、本発明のプログラム難読化装置は、著作権を有するデータを暗号化して配布するサービス産業において、経営的に、また継続的及び反復的に使用することができる。
【図面の簡単な説明】
【０２５１】
【図１】プログラム難読化装置１０の構成を示すブロック図である。
【図２】難読化対象プログラム２０１の構成の一例を示す図である。
【図３】難読化対象プログラム２０１から生成された複数の基本ブロックの構成の一例を示す図である。
【図４】基本ブロックのそれぞれから生成された複数の分割後ブロックの構成の一例を示す図である。
【図５】各分割後ブロックに基づいて生成されたグラフを示す図である。
【図６】等価プログラム命令挿入後ブロックを示す図である。
【図７】ノード数として取り得る範囲を示す図である。
【図８】偽装ブロック本体の構成の一例を示す図である。
【図９】偽装等価プログラム命令挿入後偽装ブロックの構成の一例を示す図である。
【図１０】ラベル挿入後等価プログラム命令挿入後ブロック、ラベル挿入後等価プログラム命令非挿入ブロック、及びラベル挿入後等価プログラム命令挿入後偽装ブロックの構成の一例を示す図である。
【図１１】ＴＭＰブロックの構成の一例を示す図である。
【図１２】ラベル挿入後等価プログラム命令挿入後ブロック、ラベル挿入後等価プログラム命令非挿入ブロック、及びＴＭＰブロックを用いて生成したグラフである。
【図１３】ＴＭＰブロック１１０１ｊに条件分岐命令が挿入された新たなＴＭＰブロック１３０１ｊの構成の一例を示す図である。
【図１４】新たなＴＭＰブロック１３０１ｊを用いて、再生成したグラフを示す図である。
【図１５】擬似分岐命令挿入後ブロックの構成の一例を示す図である。
【図１６】被入替ブロックの構成の一例を示す図である。
【図１７】難読化対象プログラム２０１から生成した難読化プログラム１５００の構成の一例を示す図である。
【図１８】プログラム難読化装置１０の動作概要を示す流れ図である。
【図１９】等価プログラム生成処理の動作を示す流れ図である。
【図２０】偽装ブロック挿入後プログラムの生成処理の動作を示す流れ図である。
【図２１】擬似分岐命令挿入後プログラムの生成処理の動作を示す流れ図である。
【図２２】所定数とグラフの強度との関係を示す図である。
【符号の説明】
【０２５２】
１０    プログラム難読化装置
１００    記憶部
１０１    入力部
１０２    ブロック分割部
１０３    等価プログラム命令生成部
１０４    等価プログラム生成部
１０５    偽装ブロック挿入後プログラム生成部
１０６    擬似分岐命令挿入後プログラム生成部
１０７    被入替ブロック群生成部
１０８    配置順序入替部
２０１    難読化対象プログラム
２０２    変数宣言部
２０３    処理部
【図１】
0004806402.tif 000002
【図２】
0004806402.tif 000003
【図３】
0004806402.tif 000004
【図４】
0004806402.tif 000005
【図５】
0004806402.tif 000006
【図６】
0004806402.tif 000007
【図７】
0004806402.tif 000008
【図８】
0004806402.tif 000009
【図９】
0004806402.tif 000010
【図１０】
0004806402.tif 000011
【図１１】
0004806402.tif 000012
【図１２】
0004806402.tif 000013
【図１３】
0004806402.tif 000014
【図１４】
0004806402.tif 000015
【図１５】
0004806402.tif 000016
【図１６】
0004806402.tif 000017
【図１７】
0004806402.tif 000018
【図１８】
0004806402.tif 000019
【図１９】
0004806402.tif 000020
【図２０】
0004806402.tif 000021
【図２１】
0004806402.tif 000022
【図２２】
0004806402.tif 000023