(57)【要約】【課題】  頻度分析攻撃に対して耐性が高い難読化をプログラムに適用することを可能にする。【解決手段】  難読化対象のプログラム中の第１の変数ａの値を場合分けする条件式及び場合分けされた当該第１の変数ａの値毎に当該プログラム中の第２の変数ｂの値を変換する条件節を含む第１の条件分岐Ｓと、第１の条件分岐Ｓにおける第１の変数ａの取り得る値の全範囲で第１の変数ａの値を場合分けする条件式及び場合分けされた第１の変数ａの値毎に変換された第２の変数ｂの値を元の値に逆変換する条件節を含む第２の条件分岐Ｔとを、前記プログラム中の第１及び第２の変数ａ、ｂが存在する以降の部分に挿入し、当該プログラムを冗長化して難読化する。【選択図】  図５
2008269398.tif 000002
【特許請求の範囲】
【請求項１】
難読化対象のプログラムを入力する入力手段と、
前記プログラム中の第１の変数の値を場合分けする条件式及び場合分けされた当該第１の変数の値毎に当該プログラム中の第２の変数の値を変換する条件節を含む第１の条件分岐と、当該第１の条件分岐における前記第１の変数の取り得る値の全範囲で当該第１の変数の値を場合分けする条件式及び場合分けされた当該第１の変数の値毎に前記変換された第２の変数の値を元の値に逆変換する条件節を含む第２の条件分岐と、を生成する生成手段と、
前記プログラム中の前記第１及び第２の変数が存在する以降の部分で前記第１の条件分岐と第２の条件分岐を挿入する位置を決定する決定手段と、
前記プログラム中の決定された位置に前記第１の条件分岐と第２の条件分岐を挿入する挿入手段と、
を有することを特徴とするプログラム難読化装置。
【請求項２】
前記第１の条件分岐は複数の条件式からなる第１の条件式和集合を含み、前記第２の条件分岐は複数の条件式からなる第２の条件式和集合を含み、
当該第1の条件式和集合と当該第２の条件式和集合とは同値であり、かつ、異なる集合であることを特徴とする請求項１に記載のプログラム難読化装置。
【請求項３】
前記決定手段は、前記第１の条件分岐を挿入する位置以降で前記第１及び第２の変数が操作されないプログラム部分を隔てた位置を前記第２の条件分岐を挿入する位置に決定することを特徴とする請求項１又は請求項２に記載のプログラム難読化装置。
【請求項４】
前記難読化対象のプログラム中に既存の複数の条件分岐の相関度を算出する算出手段を有し、
前記生成手段は、算出した相関度に近い相関度となるように前記第１及び第２の条件分岐を生成することを特徴とする請求項１乃至請求項３のいずれか１項に記載のプログラム難読化装置。
【請求項５】
前記決定手段は、前記第１の条件分岐が含む条件式を、前記難読化対象のプログラム中における前記第１の変数の取り得る値の全範囲で当該第１の変数の値を場合分けする条件式とすることを特徴とする請求項１乃至請求項４のいずれか１項に記載のプログラム難読化装置。
【請求項６】
前記決定手段は、前記第１の条件分岐が含む条件式を、前記難読化対象のプログラム中における前記第１の変数の取り得る値の部分的な範囲で当該第１の変数の値を場合分けする条件式とすることを特徴とする請求項１乃至請求項４のいずれか１項に記載のプログラム難読化装置。
【請求項７】
前記生成手段は、前記難読化対象のプログラムへの入力変数を、前記第１及び第２の変数として前記第１及び第２の条件分岐を生成することを特徴とする請求項１乃至請求項６のいずれか１項に記載のプログラム難読化装置。
【請求項８】
前記生成手段は、前記第１の変数を余剰計算による場合分けして、前記第１及び第２の条件分岐を生成することを特徴とする請求項１乃至請求項７のいずれか１項に記載のプログラム難読化装置。
【請求項９】
前記生成手段は、前記第１の変数をハッシュ関数による場合分けして、前記第１及び第２の条件分岐を生成することを特徴とする請求項１乃至請求項７のいずれか１項に記載のプログラム難読化装置。
【請求項１０】
前記第１の条件分岐と第２の条件分岐を挿入されたプログラムを出力する手段を有することを特徴とする請求項１乃至請求項９のいずれか１項に記載のプログラム難読化装置。
【請求項１１】
難読化対象のプログラムを入力する入力手段と、
前記プログラム中の第１の変数の値を場合分けする条件式及び場合分けされた当該第１の変数の値毎に当該プログラム中の第２の変数の値を変換する条件節を含む第１の条件分岐と、当該第１の条件分岐における前記第１の変数の取り得る値の全範囲で当該第１の変数の値を場合分けする条件式及び場合分けされた当該第１の変数の値毎に前記変換された第２の変数の値を元の値に逆変換する条件節を含む第２の条件分岐と、を生成する生成手段と、
前記プログラム中の前記第１及び第２の変数が存在する以降の部分で前記第１の条件分岐と第２の条件分岐を挿入する位置を決定する決定手段と、
前記プログラム中の決定された位置に前記第１の条件分岐と第２の条件分岐を挿入する挿入手段と、
をコンピュータに実現することを特徴とする難読化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラムを冗長化することで難読化する技術に関する。
【背景技術】
【０００２】
プログラムを悪意あるリバースエンジニアリングから守るために、様々なプログラム難読化技術が提案されている。
難読化とは、プログラムを冗長化して複雑に変換することで、プログラムの解析コストを大きくする技術である。
【０００３】
難読化手法の１つに、不明瞭な条件式（Opaque Predicates）を用いた難読化方法がある（非特許文献１、２参照。）。Opaque Predicatesとは、実行時に恒真／恒偽であることが分かっている、難読化のために用いる条件式のことをいう。
不明瞭な条件式（Opaque Predicates）を用いた難読化とは、Opaque Predicatesを条件式として用いて恒真／恒偽な条件分岐を難読化対象のプログラムに付加することで、当該プログラムを冗長化して難読化する手法である。つまり、プログラムが実現する処理としては意味を持たない恒真／恒偽な条件分岐を付加することで当該プログラムを冗長化してプログラムの解析コストを大きくする。
【０００４】
図２１には難読化の対象とするプログラムの一例を示し、図２２には当該難読化対象プログラムにOpaque Predicatesを用いた難読化を適用した一例を示してある。
図２２に示す難読化を施したプログラムは、図２１に示す元のプログラム中の位置ｐ２１にａ＊（ａ―１）ｍｏｄ２＝＝１と言う条件式と、＋＋ａ；という条件節とからなる条件分岐２２を加えることで生成されている。
ここでｍｏｄとは、例えば７ｍｏｄ２＝１といったように、左の整数値を右の整数値で割った時の余りを返す余剰計算による演算である。また、＋＋ａはａの値に１加える演算、＊は２つの値の積を取る演算である。
【０００５】
条件分岐２２では、ａがどのような整数値であっても、ａ＊（ａ―１）は２の倍数であるため、ａ＊（ａ―１）ｍｏｄ２の値は常に０、つまり、a＊(a ―１)ｍｏｄ２＝＝１は恒偽のOpaque Predicateである。そのため、＋＋ａ；と言う条件節は決して実行されない。
このため、図２１と図２２のプログラムの意味は変わらない一方で、図２２のプログラムには冗長な条件分岐２２が含まれている分、図２１のプログラムよりも解析コスト、つまりプログラムの意味を理解するコストが大きくなる。
【非特許文献１】C. Collberg, C. Thomborson, and D. Low, ``Manufacturing Cheap, Resilient, and Stealthy Opaque Constructs,'' Proceedings of the 25th ACM Symposium on Principles of Programming Languages, pp.184--196, 1998
【非特許文献２】T. Ogiso, Y. Sakabe, M. Soshi and A. Miyaji,``Software obfuscation on a theoretical basis and its implementation,''IEEE Trans. Fundamentals, vol.E86-A, no.1, pp.176--186, January, 2003.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従来のOpaque Predicatesを用いた難読化には、プログラムへの入力を変えても、付加したOpaque Predicatesの真偽値が変化しないという問題があった。
そのため、プログラムを悪意をもって解析しようとする攻撃者は、難読化を適用したプログラムに頻度分析を行うことで、Opaque Predicatesを用いた難読化を無効化することができる。
ここで、頻度分析とは、プログラムにランダムに入力を与えたり、また、プログラム内部を書き換えたりした上で実行させることで、出力結果や実行フローの違いを観察する分析方法を言う。
【０００７】
通常考えられる条件分岐の条件式の場合、プログラムへの入力値を変えればある割合でその真偽値も変化する。しかしながら、Opaque Predicatesの真偽値はどのような入力を与えても変化しない。つまり、Opaque Predicatesを用いた条件分岐の条件節は、どのような入力においても必ず実行されるか、どのような入力においても必ず実行されないかのいずれかである。
したがって、頻度分析において入力値を変えて何度も実行フローを観察するうちに、攻撃者は、必ず実行される／必ず実行されない条件節を特定できる。これにより、Opaque Predicatesを用いた難読化は無効化されてしまう。
【０００８】
本発明は、上記従来の事情に鑑みなされたのもであり、従来に比して、頻度分析攻撃に対して耐性が高い難読化をプログラムに適用することを目的としている。
【課題を解決するための手段】
【０００９】
請求項１のプログラム難読化装置は、難読化対象のプログラムを入力する入力手段と、前記プログラム中の第１の変数の値を場合分けする条件式及び場合分けされた当該第１の変数の値毎に当該プログラム中の第２の変数の値を変換する条件節を含む第１の条件分岐と、当該第１の条件分岐における前記第１の変数の取り得る値の全範囲で当該第１の変数の値を場合分けする条件式及び場合分けされた当該第１の変数の値毎に前記変換された第２の変数の値を元の値に逆変換する条件節を含む第２の条件分岐と、を生成する生成手段と、前記プログラム中の前記第１及び第２の変数が存在する以降の部分で前記第１の条件分岐と第２の条件分岐を挿入する位置を決定する決定手段と、前記プログラム中の決定された位置に前記第１の条件分岐と第２の条件分岐を挿入する挿入手段と、を有することを特徴とする。
【００１０】
請求項２のプログラム難読化装置は、請求項１において、前記第１の条件分岐は複数の条件式からなる第１の条件式和集合を含み、前記第２の条件分岐は複数の条件式からなる第２の条件式和集合を含み、当該第1の条件式和集合と当該第２の条件式和集合とは同値であり、かつ、異なる集合であることを特徴とする。
【００１１】
請求項３のプログラム難読化装置は、請求項１又は請求項２において、前記決定手段は、前記第１の条件分岐を挿入する位置以降で前記第１及び第２の変数が操作されないプログラム部分を隔てた位置を前記第２の条件分岐を挿入する位置に決定することを特徴とする。
【００１２】
請求項４のプログラム難読化装置は、請求項１乃至請求項３のいずれかにおいて、前記難読化対象のプログラム中に既存の複数の条件分岐の相関度を算出する算出手段を有し、前記生成手段は、算出した相関度に近い相関度となるように前記第１及び第２の条件分岐を生成することを特徴とする。
【００１３】
請求項５のプログラム難読化装置は、請求項１乃至請求項４のいずれかにおいて、前記決定手段は、前記第１の条件分岐が含む条件式を、前記難読化対象のプログラム中における前記第１の変数の取り得る値の全範囲で当該第１の変数の値を場合分けする条件式とすることを特徴とする。
【００１４】
請求項６のプログラム難読化装置は、請求項１乃至請求項４のいずれかにおいて、前記決定手段は、前記第１の条件分岐が含む条件式を、前記難読化対象のプログラム中における前記第１の変数の取り得る値の部分的な範囲で当該第１の変数の値を場合分けする条件式とすることを特徴とする。
【００１５】
請求項７のプログラム難読化装置は、請求項１乃至請求項６のいずれかにおいて、前記生成手段は、前記難読化対象のプログラムへの入力変数を、前記第１の及び第２の変数として前記第１及び第２の条件分岐を生成することを特徴とする。
【００１６】
請求項８のプログラム難読化装置は、請求項１乃至請求項７のいずれかにおいて、前記生成手段は、前記第１の変数を余剰計算による場合分けして、前記第１及び第２の条件分岐を生成することを特徴とする。
【００１７】
請求項９のプログラム難読化装置は、請求項１乃至請求項７のいずれかにおいて、前記生成手段は、前記第１の変数をハッシュ関数による場合分けして、前記第１及び第２の条件分岐を生成することを特徴とする。
【００１８】
請求項１０のプログラム難読化装置は、請求項１乃至請求項９のいずれかにおいて、前記第１の条件分岐と第２の条件分岐を挿入されたプログラムを出力する手段を有することを特徴とする。
【００１９】
請求項１１の難読化プログラムは、難読化対象のプログラムを入力する入力手段と、前記プログラム中の第１の変数の値を場合分けする条件式及び場合分けされた当該第１の変数の値毎に当該プログラム中の第２の変数の値を変換する条件節を含む第１の条件分岐と、当該第１の条件分岐における前記第１の変数の取り得る値の全範囲で当該第１の変数の値を場合分けする条件式及び場合分けされた当該第１の変数の値毎に前記変換された第２の変数の値を元の値に逆変換する条件節を含む第２の条件分岐と、を生成する生成手段と、前記プログラム中の前記第１及び第２の変数が存在する以降の部分で前記第１の条件分岐と第２の条件分岐を挿入する位置を決定する決定手段と、前記プログラム中の決定された位置に前記第１の条件分岐と第２の条件分岐を挿入する挿入手段と、をコンピュータに実現することを特徴とする。
【発明の効果】
【００２０】
請求項１のプログラム難読化装置によると、第１の条件分岐と第２の条件分岐とを難読化対象のプログラムに挿入するようにしたため、従来に比して、頻度分析攻撃に対して耐性が高い難読化をプログラムに適用することができる。
【００２１】
請求項２のプログラム難読化装置によると、第１の条件分岐と第２の条件分岐との条件式を和集合として難読化対象のプログラム中に挿入するようにしたため、頻度分析攻撃に対して耐性がより高い難読化をプログラムに適用することができる。
【００２２】
請求項３のプログラム難読化装置によると、第１の条件分岐と第２の条件分岐とを難読化対象のプログラム中の離間した位置に挿入するようにしたため、頻度分析攻撃に対して耐性がより高い難読化をプログラムに適用することができる。
【００２３】
請求項４のプログラム難読化装置によると、第１及び第２の条件分岐を難読化対象のプログラム中に既存の複数の条件分岐に近い相関度となるようにしたため、頻度分析攻撃に対して耐性がより高い難読化をプログラムに適用することができる。
【００２４】
請求項５のプログラム難読化装置によると、第１の条件分岐が含む条件式を難読化対象のプログラム中における第１の変数の取り得る値の全範囲で場合分けするようにしたため、第１及び第２の条件分岐がプログラムを実行すると必ず実行され、第１の変数の値にかかわらずプログラムが冗長となって、耐性がより高い難読化をプログラムに適用することができる。
【００２５】
請求項６のプログラム難読化装置によると、第１の条件分岐が含む条件式を難読化対象のプログラム中における第１の変数の取り得る値の部分的な範囲で当該第１の変数の値を場合分けするようにしたため、第１の変数の値によっては第１及び第２の条件分岐がプログラムを実行しても実行されない場合が生じ、第１及び第２の条件分岐の挿入意図をかえって隠すことができ、頻度分析攻撃に対して耐性がより高い難読化をプログラムに適用することができる。
【００２６】
請求項７のプログラム難読化装置によると、難読化対象のプログラムへの入力変数を第１及び第２の変数として第１及び第２の条件分岐を生成するようにしたため、従来に比して、頻度分析攻撃に対して耐性が高い難読化をプログラムに適用することができる。
【００２７】
請求項８のプログラム難読化装置によると、第１の変数を余剰計算による場合分けして第１及び第２の条件分岐を生成するようにしたため、従来に比して、頻度分析攻撃に対して耐性が高い難読化をプログラムに適用することができる。
【００２８】
請求項９のプログラム難読化装置によると、第１の変数をハッシュ関数による場合分して第１及び第２の条件分岐を生成するようにしたため、従来に比して、頻度分析攻撃に対して耐性が高い難読化をプログラムに適用することができる。
【００２９】
請求項１０のプログラム難読化装置によると、第１の条件分岐と第２の条件分岐を挿入された頻度分析攻撃に対して耐性が高いプログラムプログラムを出力することができる。
【００３０】
請求項１１の難読化プログラムによると、コンピュータハードウエアを利用して、従来に比して頻度分析攻撃に対して耐性が高い難読化をプログラムに適用することができるプログラム難読化装置を実現することができる。
【発明を実施するための最良の形態】
【００３１】
まず、本発明に係るプログラム難読化装置の利用形態の一例を、図３及び図４を参照して説明する。
図３に示すように、本発明に係る難読化装置１はプログラムの開発者によって利用され、開発者は、開発したプログラムを難読化装置に入力として与える。難読化装置１は、入力されたプログラムに対して本発明に係る難読化処理を施して、難読化済プログラムを出力する。
【００３２】
難読化装置は入力された元のプログラムを難読化する際にプログラム自体の意味を変えないので、入力された元のプログラムと難読化済プログラムの動作は同じである。
ただし、難読化済プログラムには冗長な条件分岐が追加されているので、元のプログラムよりも解析コストが大きい。
開発者は、物理的に離れたところにいるユーザに対して、難読化済プログラムを渡す。この渡す手段としては、インターネットを介して提供する方法が考えられ、また別の方法として、ＣＤ−ＲＯＭ等の記憶メディアにデータとして格納して渡す方法も考えられる。
【００３３】
図４に示すように、難読化済プログラムがユーザに渡された後、開発者は元のプログラムと難読化済プログラムとを所持しており、ユーザは難読化済プログラムのみを所持している。
元のプログラムと難読化済プログラムの機能は同じなので、ユーザは難読化済プログラムにより元のプログラムと同じ機能を利用できる。
一方、ユーザは元のプログラムを所持していないので、元のプログラムの持つ機密情報（例えば、ライセンスに関する情報など）を得るためには、難読化済プログラムを解析しなければならない。しかしながら、 難読化済プログラムの解析コストは元のプログラムの解析コストよりも大きいので、元のプログラムをユーザに手渡す状況と比較すると、プログラムの機密情報が暴かれる機会はより小さい。
【００３４】
図１には、本発明の一実施例に係るプログラム難読化装置１の構成を示してある。
本例の難読化装置１は、難読化対象のプログラムを入力する入力手段２と、入力したプログラムを難読化するための処理を行う難読化処理手段３と、難読化されたプログラムを出力する出力手段４と、を有している。更に、難読化処理手段３は、入力したプログラムを難読化するための解析を行う解析手段５と、入力したプログラムを難読化するための条件分岐を生成する条件分岐生成手段６と、入力したプログラムに条件分岐を挿入して難読化する挿入手段７と、を有している。
【００３５】
入力手段２は、例えば、ＣＤＲＯＭ等のメディア記憶媒体に記憶された難読化対象のプログラムを読取る手段、通信回線を介して難読化対象のプログラムを受信する手段など難読化対象のプログラムを難読化装置１に取り込むことができる種々な手段を用いることができる。
なお、開発者が操作するコンピュータに本発明に係る難読化プログラムをインストールして難読化装置を構成することもでき、この場合には、入力手段２は作成したプログラムをコンピュータ内部でプログラム作成部から難読化装置部へ受け渡す手段であってもよい。
【００３６】
出力手段４は、例えば、ＣＤＲＯＭ等のメディア記憶媒体に難読化したプログラムを書き込む手段、通信回線を介して難読化したプログラムを送信する手段など難読化したプログラムを難読化装置１から出力することができる種々な手段を用いることができる。
解析手段５は、難読化対象のプログラムを解析して、難読化のための条件分岐を挿入するプログラム中の位置を決定する。具体的には、解析手段５は、難読化対象プログラム中の、条件分岐に用いられる第１の変数（以下の例では、ａ）と第２の変数（以下の例では、ｂ）が存在する以降の部分で条件分岐を挿入する位置を決定する。
【００３７】
ここで、以下の例では、第１と第２の条件分岐（それぞれ条件分岐の集合）を生成して難読化対象プログラムに挿入するが、第１の条件分岐を挿入する位置以降で第１及び第２の変数が操作されないプログラム部分を隔てた位置を第２の条件分岐を挿入する位置に決定するのが好ましい。すなわち、攻撃者による解析を困難化するために、第１の条件分岐と第２の条件分岐とを、第１及び第２の変数が操作されないプログラム部分を挟んで振り分けてプログラム中に位置させるのが好ましい。
なお、本発明では、このように振り分け配置せずとも、第１の条件分岐と第２の条件分岐とをプログラム中に並べて位置させるようにしてもよく、これによっても、プログラム中に条件分岐を挿入することによる冗長化（難読化）の目的は達成される。
【００３８】
条件分岐生成手段６は、難読化対象プログラム中の第１の変数（以下の例では、ａ）の値を場合分けする条件式及び場合分けされた当該第１の変数の値毎に当該難読化対象プログラム中の第２の変数（以下の例では、ｂ）の値を変換する条件節を含む第１の条件分岐と、当該第１の条件分岐における第１の変数の取り得る値の全範囲で当該第１の変数の値を場合分けする条件式及び場合分けされた当該第１の変数の値毎に前記変換された第２の変数の値を元の値に逆変換する条件節を含む第２の条件分岐と、を生成する。
すなわち、第１の条件分岐は、第１の変数のとり得る値を場合分けして、場合分け毎に第２の変数の値を変換するものであり、難読化対象プログラム中の第１の条件分岐より後部に挿入される第２の条件分岐は、第１の条件分岐で場合分けした第１の変数値の全範囲で当該第１の変数（ａ）の値を場合分けして、場合分け毎に第１の条件分岐で変換された第２の変数値を元の値に逆変換するものである。
【００３９】
ここで、第１の条件分岐における場合分けは、第１の変数が取り得る値の全範囲であっても、又は、第１の変数が取り得る値の部分範囲であってもよい。例えば、第１の変数が取り得る値が１〜１２である場合、この１〜１２の値の範囲を４分する場合分けであっても、又は、第１の変数が取り得る値の範囲の内の３〜１０の値の範囲を４分する場合分けであってもよい。
このように、第１の条件分岐における第１の変数をその取り得る値の部分範囲で場合分けすると、プログラムの実行において、第１の変数値が場合分けした範囲外のときは、第１の条件分岐及びその後の第２の条件分岐は実行されずにパスされることとなるが、このように第１の変数値によって条件分岐が実行されない場合が生じても、プログラム中に条件分岐を挿入することによる冗長化（難読化）の目的は達成される。
【００４０】
なお、第２の条件分岐における場合分けは、第１の条件分岐における第１の変数の取り得る値の全範囲である必要がある。すなわち、この場合分けが部分範囲であると、第１の条件分岐において場合分け毎に変換された第２の変数を元に戻すことができなくなる場合が生じてしまい、条件分岐の挿入によって難読化したプログラムの意味を変更してしまう場合が生じてしまう。
【００４１】
ここで、以下の例では、第１の変数及び第２の変数を難読化対象プログラムへの入力変数としているが、本発明では、第１の条件分岐より前にプログラム中に存在するいずれの変数を用いて第１及び第２の条件分岐を生成してもよい。
また、本例の解析手段５は、難読化対象プログラム中に既存の複数の条件分岐の相関度を算出する機能を有しており、本例の生成手段６は算出した相関度に近い相関度となるようにプログラムに挿入する第１及び第２の条件分岐を生成する。
【００４２】
本例の難読化装置１は、図２に示すように、プロセッサ（ＣＰＵ）１１、基本的な制御プログラムを記憶したＲＯＭ１２、本発明に係るプログラムを処理する作業領域となるＲＡＭ１３、外部との入出力を行うためのインタフェース（Ｉ／Ｏ）１４等を有するコンピュータで構成されており、当該コンピュータによって本発明に係る難読化プログラムを実行することで、上記各機能手段２〜７が実現されている。
なお、本発明では、各機能手段２〜７を専用のハードウエアモジュールで実現してもよい。
【００４３】
図５には、図２１に示したプログラムを難読化対象として、本発明に係る難読化装置１で難読化した例を示してある。
この例では、生成手段６が、第１と第２の変数を難読化対象プログラムの入力変数ａとｂとして、第１の条件分岐Ｓと第２の条件分岐Ｔとを生成し、挿入手段７が、第１の条件分岐Ｓと第２の条件分岐Ｔとを、図２１に示すように、難読化対象プログラム中の変数ａ、ｂを操作しないプログラム部分ｐｐを隔てた位置にｐ２０、ｐ２１に挿入している。
【００４４】
この第１の条件分岐Ｓは、変数ａを余剰計算により場合分けする条件式ｉｆ（ａ ｍｏｄ ２ ＝＝０）と、変数ｂの可逆変換関数である条件節（ｂ＝２＊ｂ＋３）を含んでいる。また、第２の条件分岐は、変数ａを余剰計算により場合分けする２つの条件式ｉｆ（ａ ｍｏｄ ４＝＝０）とｉｆ（ａ ｍｏｄ  ４＝＝２）と、これら場合毎に変数ｂを元の値に戻す逆変換関数である２つの条件節（ｂ＝（ｂ―３）／２）と（ｂ＝（ｂ―３）／２）とを含んでいる。
ここで、この例では、第１の条件分岐における条件式は変数ａを１つに場合分けしていることに相当する。なお、変数ａを複数に場合分けする時には、図５に示す第２の条件分岐Ｔのように、条件分岐は、複数の条件式からなる和集合と、それぞれの条件式に対応する条件節とを含むものとなる。
【００４５】
図５に示す難読化したプログラムでは、明らかに、第１の条件分岐による条件節（ｂ＝２＊ｂ＋３）が実行されれば、必ず、変数ｂを操作しないプログラム部分ｐｐを隔てた第２の条件分岐における条件節（ｂ＝（ｂ―３）／２）も実行される。
したがって、第１と第２の条件分岐を挿入しても、変数ｂの値は元のプログラムにおいて使用される元の値に戻され、これら第１と第２の条件分岐はプログラムの意味を変更しない。
【００４６】
図６及び図７を参照して、図２１に示すプログラムを難読化対象として、本例の難読化装置１で実施される処理の第１実施例を説明する。
本実施例の特徴は、条件分岐生成手段６が、第１の条件分岐Ｓと第２の条件分岐Ｔにそれぞれ含まれる条件式を生成するために、剰余演算を用いた条件式から成る、互いに和集合として同値であり、かつ、集合としては異なる条件式の和集合Ｓ’、Ｔ’を生成することである。
この実施例での難読化装置１は、図６に示すような手順Ｓ６１〜Ｓ６６に従って処理を行う。 
【００４７】
入力手段２２で難読化対象のプログラムを入力として受け取り、解析手段５及び条件分岐生成手段６が難読化対象関数を決める（Ｓ６１）。
具体的には、条件分岐生成手段６が、難読化対象関数の入力変数ａを適当に選び、更に、２以上の整数ｎを適当に選び、このａとｎを用いて、次の定める条件式の和集合Ｓ’、Ｔ’を生成する（Ｓ６２）。
Ｓ’＝｛ａ ｍｏｄ ２＝＝０、ａ ｍｏｄ ２＝＝１｝。
Ｔ’＝｛ａ ｍｏｄ ２＊ｎ＝＝０、ａ ｍｏｄ ２＊ｎ＝＝１、・・ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―２、ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―１ ｝。
【００４８】
そして、条件分岐生成手段６が、２つの可逆関数ｇ１、ｇ２を生成する（Ｓ６３）。具体的には、難読化対象関数中から、ｇ１、ｇ２による操作対象の変数ｂを適当に選び、更に、解析手段５が、難読化対象プログラム中の挿入位置（図２１のｐ２０、ｐ２１参照）を決定する。ただし、ｐ２０とｐ２１の間で変数ｂは使われないとする（Ｓ６４）。
【００４９】
そして、挿入手段７が、位置ｐ２０とｐ２１に次のように条件分岐を挿入する（Ｓ６５）。
第１の条件分岐の集合Ｓとして、（ａ ｍｏｄ ２＝＝ ０）を条件式、変数ｂを関数ｇ１によって変更する文を条件節とした条件分岐｛ｉｆ（ ａ ｍｏｄ ２ ＝＝０）  ｂ＝ｇ１（ｂ）｝と、（ａ ｍｏｄ ２ ＝＝ １）を条件式、変数ｂを関数ｇ２によって変更する文を条件節とした条件分岐｛ｉｆ（ａ ｍｏｄ ２＝＝１）  ｂ＝ｇ２（ｂ）｝とを位置ｐ１に挿入する。
【００５０】
また、第２の条件分岐の集合Ｔとして、（ａ ｍｏｄ２＊ｎ＝＝０）、（ａ ｍｏｄ ２＊ｎ＝＝２）、 …、（ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ ―２）を条件式、変数ｂをｇ１の逆関数ｇ１‘によって変更する文を条件節としたｎ個の条件分岐｛ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝０）    ｂ ＝ ｇ１’（ｂ）｝、｛ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝２ ）  ｂ＝ｇ１‘（ｂ）｝、…、｛ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―２）  ｂ＝ｇ１’（ｂ）｝と、（ａ ｍｏｄ ２＊ｎ＝＝１）、（ａ ｍｏｄ ２＊ｎ＝＝３）、…、（ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―１）を条件式、変数ｂをｇ２の逆関数ｇ２‘によって変更する文を条件節としたｎ個の条件分岐｛ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝１）  ｂ＝ｇ２’（ｂ）｝、｛ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝３ ）  ｂ＝ｇ２‘（ｂ）｝、… 、｛ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―１）  ｂ＝ｇ２’（ｂ）｝を位置ｐ２に挿入して、出力手段４が難読化したプログラムを出力する（Ｓ６６）。
【００５１】
図７には、本実施例によって難読化されたプログラムを例示してある。
図７のプログラムは、図２１の関数ｆ00に難読化を適用した例であり、上の手順Ｓ６１〜Ｓ６６を行う際に、手順Ｓ６２、Ｓ６３、Ｓ６４でそれぞれ次のようにパラメーターを定めている。
手順Ｓ６２において、難読化対象関数の入力変数ａとしてf00の入力変数ａを、２以上の整数ｎとして２を選ぶ。
手順Ｓ６３において、可逆関数ｇ１、ｇ２としてｇ１（ｘ）＝２＊ｘ＋３、ｇ２（ｘ）＝４＊ｘ―５を生成する。
手順Ｓ６４において、ｇ１、ｇ２による操作対象として、f00の変数ｂを選び、難読化対象関数（プログラム）中の位置として、f00中のｐ２０、ｐ２１を選ぶ。
【００５２】
図７の難読化されたプログラムの動作について説明する。
変数ａの値は２の倍数であるか否かによって、第１の条件分岐集合Ｓの２つの条件節（ｂ＝２＊ｂ＋３）、（ｂ＝４＊ｂ―５）のいずれか一方が実行される。
変数ａが２の倍数であったと仮定すると、この時、１つ目の条件節が実行されるので、変数ｂの値は２＊ｂ＋３に変化する。
そして、実行が第２の条件分岐集合Ｔに進むと、変数ａは２の倍数だと仮定しているので、 条件式（ａ ｍｏｄ ４＝＝０）、（ａ ｍｏｄ ４＝＝１）、（ａ ｍｏｄ ４＝＝２）、（ａ ｍｏｄ ４＝＝３）のうち、（ａ ｍｏｄ ４＝＝０）、（ａ ｍｏｄ ４＝＝２）のいずれか一方が必ず真になり、（ａ ｍｏｄ ４＝＝１）、（ａ ｍｏｄ ４＝＝３）はいずれも偽になる。
【００５３】
（ａ ｍｏｄ ４＝＝０）と（ａ ｍｏｄ ４＝＝２）のいずれが真になった場合も、条件節として（ｂ＝（ｂ―３）／２）が実行されるので、変数ｂの値は（ｂ―３）／２に変化し、変数ｂの値は元に戻る。
実行は｛ｒｅｔｕｒｎ ａ ＋ ｂ；｝文に到達するが、変数ｂの値は元に戻っているので、このときに返す値は図２１の難読化前のプログラムのケースと同一である。
なお、変数ａが２の倍数でない場合も、同様に、変数ｂの値は元に戻るので、返す値は図２１の難読化前のプログラムのケースと同一である。
【００５４】
なお、手順Ｓ６２において条件分岐を生成する際に、難読化対象のプログラムに元々含まれる任意の２つの条件節間の相関度に基づいてもよい。具体的には、後に示す手順１、２に従ってnを選んでもよい。
ここで、手順１、２を示す前に、条件節間の相関度について説明する。プログラムにおいて、同じブロック構造に２つの条件分岐 ｛ｉｆ（s１）ｈ１｝と｛ｉｆ（s２）ｈ２｝があるとする（図１２、図１３参照）。この時、２つの条件節ｈ１、ｈ２が同時に実行される度合いを、ｈ１、ｈ２の相関度と定める。頻度分析において、十分な回数、プログラムに適当な入力を与えて実行をトレースすることで、ｈ１、ｈ２間の相関度を計算できる。例えば、図１４のプログラムの条件分岐｛if（０＜a＜＝１００）ｈ１｝と｛if（０＜a＜＝５０）ｈ２｝に関して、頻度分析において変数ａをランダムに変えて実行トレースを何度もとることで、ｈ１とｈ２１の相関度として０．５に十分近い値が得られる。
【００５５】
手順１、２を次に示す。
手順１：プログラムに元々含まれる任意の２つの条件節について相関度を求め、相関度の平均値Ｑを計算する。プログラムの実行時間と実行トレースを取る回数をともに定数とすると、この操作の計算量オーダーは高々Ｏ（ｋ＾２）である（ｋは難読化対象関数に含まれる条件節の数）。
手順２：そして、１／ｎ＜＝Ｑを満たすｎを選ぶ。
【００５６】
図８〜図１４を参照して、本例の難読化装置１で実施される処理の第２実施例を説明する。
本実施例の特徴は、条件分岐生成手段６が、第１の条件分岐Ｓと第２の条件分岐Ｔにそれぞれ含まれる条件式を生成するために、ハッシュ関数を用いた条件式から成る、互いに和集合として同値であり、かつ、集合として異なる条件式の和集合Ｓ’、Ｔ’を生成することである。
本実施例での難読化装置１は、図８に示すように手順Ｓ８１〜Ｓ８６に従って処理を行う。なお、実施例1と異なる手順はＳ８２とＳ８５である。
【００５７】
本実施例では、ハッシュ関数ｈａｓｈを用いており、ｈａｓｈの返り値は１２０ｂｉｔとしている。
入力手段２で難読化対象のプログラムを入力として受け取り、解析手段５及び条件分岐生成手段６で難読化対象関数を決める（Ｓ８１）。具体的には、難読化対象関数の入力変数ａを適当に選び、更に、２以上の整数ｎを適当に選び、このａとｎを用いて、次の定める条件式の和集合Ｓ’、Ｔ’を生成する（Ｓ８２）。ただし、以下では、Ｎ＝２＾（１２０―ｎ）とする。
【００５８】
Ｓ’＝｛０＜＝ｈａｓｈ（ａ）＜（２＾１２０）／２、（２＾１２０）／２＜＝ｈａｓｈ（ａ）＜２＾１２０｝。
Ｔ’＝{０＜＝ｈａｓｈ（ａ）＜１＊Ｎ、１＊Ｎ＜＝ｈａｓｈ（ａ）＜２＊Ｎ、…、（２＾ｎ―２）＊Ｎ＜＝ｈａｓｈ（ａ）＜（２＾ｎ―１）＊Ｎ、（２＾ｎ―１）＊Ｎ ＜＝ｈａｓｈ（ａ）＜２＾ｎ＊Ｎ}。
【００５９】
そして、２つの可逆関数ｇ１、ｇ２を生成する（Ｓ８３）。難読化対象関数中から、ｇ１、ｇ２による操作対象の変数ｂを適当に選び、更に、難読化対象関数中の位置ｐ１、ｐ２を決定する。ただし、位置ｐ１とｐ２の間のプログラム部分ｐｐでは変数ｂは使われないとする（Ｓ８４）。
そして、挿入手段７が、位置ｐ１、ｐ２に、次のような条件分岐Ｓ、Ｔをそれぞれ挿入し（Ｓ８５）、難読化したプログラムを出力手段４が出力する（Ｓ８６）。
【００６０】
条件分岐Ｓとして、条件式和集合Ｓ’の０＜＝ｈａｓｈ（ａ）＜（２＾１２０）／２を条件式、 ｂをg１によって変更する文を条件節とした条件分岐ｉｆ（０＜＝ｈａｓｈ（ａ）＜（２＾１２０）／２＝ｇ１（ｂ）＝ｇ１（ｂ）をｐ１に挿入する。
また、条件分岐Ｓとして、条件式和集合Ｓ’の（２＾１２０）／２＜＝ｈａｓｈ（ａ）＜２＾１２０を条件式、ｂをｇ２によって変更する文を条件節とした条件分岐ｉｆ（（２＾１２０）／２＜＝ｈａｓｈ（ａ）＜（２＾１２０）ｂ＝ｇ２（ｂ）をｐ１に挿入する。
【００６１】
条件分岐Ｔとして、条件式和集合Ｔ’の０＜＝ｈａｓｈ（ａ）＜１＊Ｎ、１＊Ｎ＜＝ｈａｓｈ（ａ）＜２＊Ｎ、…、（２＾（ｎ―１））＊Ｎ＜＝ｈａｓｈ（ａ）＜（２＾（ｎ―１）＋１）＊Ｎを条件式、ｂをｇ１の逆関数ｇ１‘によって変更する文を条件節としたｎ個の条件分岐ｉｆ（０＜＝ｈａｓｈ（ａ）＜１＊Ｎ）ｂ＝ｇ１’（ｂ）、ｉｆ（１＊Ｎ＜＝ｈａｓｈ（ａ）＜２＊Ｎ）ｂ＝ｇ１‘（ｂ）、…、ｉｆ（（２＾（ｎ―１））＊Ｎ＜＝ｈａｓｈ（ａ）＜（２＾（ｎ―１）＋ １）＊Ｎ ）ｂ＝ｇ１’（ｂ）をｐ２に挿入する。
条件式Ｔとして、条件式和集合Ｔ’の（２＾（ｎ―１）＋１）＊Ｎ＜＝ｈａｓｈ（ａ）＜（２＾（ｎ―１）＋２）＊Ｎ、（２＾（ｎ―１）＋２）＊Ｎ＜＝ｈａｓｈ（ａ）＜（２＾（ｎ―１）＋ ３）＊Ｎ、…、（２＾ｎ ― １）＊Ｎ＜＝ｈａｓｈ（ａ）＜（２＾ｎ）＊Ｎを条件式、ｂをｇ２の逆関数ｇ２‘によって変更する文を条件節としたｎ個の条件分岐ｉｆ（（２＾（ｎ―１）＋１）＊Ｎ＜＝ｈａｓｈ（ａ）＜（２＾（ｎ―１）＋ ２）＊Ｎ）ｂ＝ｇ２’（ｂ）、ｉｆ（（２＾（ｎ―１）＋２）＊Ｎ＜＝ｈａｓｈ（ａ）＜（２＾（ｎ―１）＋３）＊Ｎ）ｂ＝ｇ２‘（ｂ）、… 、ｉｆ（（２＾ｎ ― １）＊Ｎ＜＝ｈａｓｈ（ａ）＜（２＾ｎ）＊Ｎ）ｂ＝ｇ２’（ｂ）をｐ２に挿入する。
【００６２】
図９には、本実施例によって難読化されたプログラムの例を示してある。図９のプログラムは、図２１の関数f00に難読化を適用した例である。
なお、図１２〜図１４には、２つの条件分岐を挿入した他の例を示してある。
【００６３】
上記の手順Ｓ８１〜Ｓ８６を行う際に、手順Ｓ８２、Ｓ８３、Ｓ８４でそれぞれ次のようにパラメーターを定めている。
手順Ｓ８２において、難読化対象関数の入力変数ａとしてf00の入力変数ａを、２以上の整数ｎとして２を選ぶ。
手順Ｓ８３において、可逆関数ｇ１、ｇ２としてｇ１（ｘ）＝２＊ｘ＋３、ｇ２（ｘ）＝４＊ｘ―５を生成する。
手順Ｓ８４において、ｇ１、ｇ２による操作対象として、f00の変数ｂを選び、難読化対象関数中の位置ｐ１、ｐ２として、f00中のｐ２０、ｐ２１を選ぶ。
このプログラムも図7のプログラムと同様、図２１と同じ動作をする。
【００６４】
第２実施例でも、第１実施例と同様に、手順Ｓ８２においてｎを選ぶ際に、次の手順１、２に従ってもよい。なお、この手順は、第１実施例で示した手順１、２と同じである。
手順１：プログラムに元々含まれる任意の２つの条件節について相関度を求め、相関度の平均値Ｑを計算する。プログラムの実行時間と実行トレースを取る回数をともに定数とすると、この操作の計算量オーダーは高々Ｏ（ｋ^２）である（ｋは難読化対象関数に含まれる条件節の数）。
手順２：１／ｎ＜＝Ｑを満たすｎを選ぶ。
【００６５】
ここで、上記の第１及び第２実施例では第１の条件分岐Ｓが含む条件式を難読化対象のプログラム中における第１の変数ａの取り得る値の全範囲で当該第１の変数ａの値を場合分けする条件式としているが、本発明では、第１の変数ａの取り得る値の部分的な範囲で当該第１の変数ａの値を場合分けする条件式としてもよい。
【００６６】
具体的には、第２実施例では、第１の条件分岐Ｓで図１０（ａ）に示すように変数ａの取り得る値の範囲２＾１２０を２等分したＡの範囲とＢの範囲とに場合分けし、第２の条件分岐Ｔで図１０（ｂ）に示すように変数ａの取り得る値の範囲２＾１２０を４等分したＣ〜Ｆの範囲に場合分けしている。
これとは異なり、本発明では、第１の条件分岐Ｓで図１１に示すように変数ａの取り得る値の範囲の一部（ＸとＹを除いた部分）場合分けし、この場合分けした範囲の変数ａの値を第２の条件分岐Ｔで場合分けしてもよい。この場合、プログラムの実行において変数ａの値が第１の条件分岐による場合分けから外れた範囲（Ｘの範囲とＹの範囲）であるときには、挿入した第１と第２の条件分岐をパスすることとなるが、これによっても、プログラムの冗長化による難読化効果が得られる。
【００６７】
図１５、図１６を参照して、本例の難読化装置１で実施される処理の第３実施例を説明する。
本実施例での難読化装置１は、図１５に示すように手順Ｓ１５１〜Ｓ１５６に従って処理を行う。
本実施例の特徴は、手順Ｓ１５２において入力変数ａを用いて生成する条件式の和集合Ｓ’、Ｔ’が変数ａの取り得る全ての条件を網羅していない点と、手順Ｓ１５５において関数ｇ１の逆関数ｇ１‘によって変数ｂのｇ１による変更を戻す文を挿入する際に、ｂ＝ｇ１’（ｂ）と構文は異なるが意味的には等価な文を挿入する点である。
【００６８】
入力手段２で難読化対象のプログラムを入力として受け取り、解析手段５及び条件分岐生成手段６で、難読化対象関数を決め（Ｓ１５１）、難読化対象関数の入力変数ａを適当に選び、更に、２以上の整数ｎを適当に選び、このａとｎを用いて、次の定める条件式の和集合Ｓ’、Ｔ’を生成する（Ｓ１５２）。
Ｓ’＝［ａ ｍｏｄ ２＝＝０］
Ｔ’＝ ［ａ ｍｏｄ ２＊ｎ＝＝０、…、ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ ― ２］
【００６９】
そして、解析手段５及び条件分岐生成手段６で、可逆関数ｇ１を生成する（Ｓ１５３）。難読化対象関数中から、ｇ１による操作対象の変数ｂを適当に選び、更に、難読化対象関数中の位置ｐ１、ｐ２を決定する。ただし、ｐ１とｐ２の間でａ、ｂは使われないとする（Ｓ１５４）。
そして、挿入手段７が位置ｐ１、ｐ２に、次のような条件分岐を挿入し（Ｓ１５５）、出力手段４が難読化したプログラムを出力する（Ｓ１５６）。
【００７０】
具体的には、第１の条件分岐集合Ｓとして、条件式和集合Ｓ’のａ ｍｏｄ ２＝＝０を条件式、ｂを関数ｇ１によって変更する文を条件節とした条件分岐ｉｆ（ａ ｍｏｄ ２＝＝０）、ｂ＝ｇ１（ｂ）をｐ１に挿入する。
第２の条件分岐集合Ｔとして、条件式和集合Ｔ’のａ ｍｏｄ ２＊ｎ＝＝０、ａ ｍｏｄ ２＊ｎ＝＝２、…、ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―２を条件式、ｂをｇ１の逆関数ｇ１‘によって変更する文と等価な文ｚ１、 …、ｚｎを条件節としたｎ個の条件分岐ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝０）ｚ１、ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝２）ｚ２、…、ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―２）ｚｎをｐ２に挿入する。
【００７１】
図１６に、本実施例によって難読化されたプログラムの例を示してある。なお、図１６のプログラムは、図２１の関数f00に難読化を適用した例である。
上記の手順Ｓ１５１〜Ｓ１５６を行う際に、手順Ｓ１５２、Ｓ１５３、Ｓ１５４、Ｓ１５５でそれぞれ次のようにパラメーターを定めている。
手順Ｓ１５２において、難読化対象関数の入力変数ａとしてf00の入力変数ａを、２以上の整数ｎとして２を選ぶ。
手順Ｓ１５３において、可逆関数ｇ１としてｇ１（ｘ）＝８＊ｘ＋２を生成する。
【００７２】
手順Ｓ１５４において、ｇ１による操作対象として、f00の変数ｂを選び、難読化対象関数中の位置ｐ１、ｐ２としてf00中のｐ２０２０ｐ２１を選ぶ。
手順Ｓ１５５５において、ｂをｇ１の逆関数ｇ１‘によって変更する文と等価な文ｚ１、ｚ２を以下のように選ぶ。
ｚ１＝｛ｂ＝ｂ―２；ｂ＝ｂ／８；｝
ｚ２＝｛ｂ＝ｂ―３；ｂ＝ｂ＋１；ｂ＝ｂ／８；｝
【００７３】
図１６のプログラムも図７のプログラムと同様、図２１と同じ動作をする。
また、本実施例でも、第１実施例と同様に、手順Ｓ１５２においてｎを選ぶ際に次の手順１、２に従ってもよい。この手順は、第１実施例で示した手順１、２と同じである。
手順１：プログラムに元々含まれる任意の２つの条件節について相関度を求め、相関度の平均値Ｑを計算する。プログラムの実行時間と実行トレースを取る回数をともに定数とすると、この操作の計算量オーダーは高々Ｏ（ｋ＾２）である（ｋは難読化対象関数に含まれる条件節の数）。
手順２：１／ｎ ＜＝Ｑを満たすｎを選ぶ。
【００７４】
図１７、図１８を参照して、本例の難読化装置１で実施される処理の第４実施例を説明する。
本実施例での難読化装置１は、図１７に示すように手順Ｓ１７１〜Ｓ１７６に従って処理を行う。
本実施例の特徴は、挿入する条件節において複数の変数を操作する点である。具体的には、手順Ｓ１７３において生成する可逆変数ｇ１、ｇ２はそれぞれ２つの入力と出力を持ち、更に、手順Ｓ１７４においては操作対象の変数を２つ（ｂ、ｃ）選ぶ。
【００７５】
入力手段２でプログラムを入力として受け取り、解析手段５及び条件分岐生成手段６で難読化対象関数の入力変数ａ適当に選び、２上の整数ｎ適当に選び、このａとｎを用いて、次の定める条件式の和集合Ｓ’、Ｔ’を生成する（Ｓ１７２）。
Ｓ’＝［ａ ｍｏｄ ２＝＝０、ａ ｍｏｄ ２＝＝１］。
Ｔ’＝［ａ ｍｏｄ ２＊ｎ＝＝０、ａ ｍｏｄ ２＊ｎ＝＝１、…、ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―２、ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ ― １］。
【００７６】
そして、解析手段５及び条件分岐生成手段６で、２つの入力をもつ可逆関数ｇ１、ｇ２を生成し（Ｓ１７３）、難読化対象関数中からｇ１、ｇ２による操作対象の変数ｂ、ｃを適当に選び、更に、難読化対象関数中の位置ｐ１、ｐ２を決定する。ただし、ｐ１とｐ２の間でａ、ｂ、ｃは使われないとする（Ｓ１７４）。
そして、挿入手段７が位置ｐ１、ｐ２に、次のような条件分岐を挿入して（Ｓ１７５）、出力手段４が難読化したプログラムを出力する（Ｓ１７６）。
【００７７】
第１の条件分岐集合Ｓとして、条件式和集合Ｓ’のａ ｍｏｄ ２＝＝０を条件式、ｂ、ｃを関数ｇ１によって変更する文を条件節とした条件分岐ｉｆ（ａ ｍｏｄ ２＝＝０）（ｂ、ｃ）＝ｇ１（ｂ、ｃ）；をｐ１に挿入する。
また、第１の条件分岐集合Ｓとして、条件式和集合Ｓ’のａ ｍｏｄ ２＝＝１を条件式、ｂ、ｃをｇ２によって変更する文を条件節とした条件分岐 ｉｆ（ａ ｍｏｄ ２＝＝０）（ｂ、ｃ）＝ｇ２（ｂ、ｃ）；をｐ１に挿入する。
【００７８】
更に、第２の条件分岐集合Ｔとして、条件式和集合Ｔ’のａ ｍｏｄ ２＊ｎ＝＝０、ａ ｍｏｄ ２＊ｎ＝＝２、 …、 ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―２を条件式、ｂ、ｃをｇ１の逆関数ｇ１‘によって変更する文を条件節としたｎ個の条件分岐ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝０）（ｂ、ｃ）＝ｇ１’（ｂ、ｃ）；、ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝２ ）（ｂ、ｃ）＝ｇ１‘（ｂ、ｃ）；、…、ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―２）（ｂ、ｃ）＝ｇ１’（ｂ、ｃ）；をｐ２に挿入する。
また、第２の条件分岐集合Ｔとして、条件式和集合Ｔ’のａ ｍｏｄ ２＊ｎ＝＝１、ａ ｍｏｄ ２＊ｎ＝＝３、…、ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―１を条件式、ｂ、ｃをｇ２の逆関数ｇ２‘によって変更する文を条件節としたｎ個の条件分岐ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝１ ）（ｂ、ｃ）＝ｇ２‘（ｂ、ｃ）；、ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝３）（ｂ、ｃ）＝ｇ２‘（ｂ、ｃ）；、…、ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―１）（ｂ、ｃ）＝ｇ２‘（ｂ、ｃ）；をｐ２に挿入する。
【００７９】
図１８に、本実施例によって難読化されたプログラムの例を示す。図１８のプログラムは、図２１の関数f00に難読化を適用した例である。
上記の手順Ｓ１７１〜Ｓ１７６を行う際に、手順Ｓ１７２、Ｓ１７３、Ｓ１７４でそれぞれ次のようにパラメーターを定めている。
手順Ｓ１７２において、難読化対象関数の入力変数ａとしてf00の入力変数ａを、２以上の整数ｎとして２を選ぶ。
手順Ｓ１７３において、複数の入力を持つ可逆関数ｇ１、ｇ２としてｇ１（ｘ、ｙ）＝（２＊ｘ＋３、５＊ｙ＋４）、ｇ２（ｘ、ｙ）＝（４＊ｘ―５、６＊ｙ＋７）を生成する。
手順Ｓ１７４において、ｇ１、ｇ２による操作対象として、f00の変数ｂ、ｃを選び、難読化対象関数中の位置ｐ１、ｐ２として、f00中のｐ２０、ｐ２１を選ぶ。
【００８０】
図１８のプログラムも図７のプログラムと同様、図２１と同じ動作をする。
本実施例でも、第１実施例と同様に、手順Ｓ１７２においてｎを選ぶ際に次の手順１，２に従ってもよい。この手順は、第１実施例で示した手順１、２と同じである。
手順１：プログラムに元々含まれる任意の２つの条件節について相関度を求め、相関度の平均値Ｑを計算する。プログラムの実行時間と実行トレースを取る回数をともに定数とすると、この操作の計算量オーダーは高々Ｏ（ｋ＾２）である（ｋは難読化対象関数に含まれる条件節の数)。
手順２：１／ｎ＜＝Ｑを満たすｎを選ぶ。
【００８１】
図１９、図２０を参照して、本例の難読化装置１で実施される処理の第５実施例を説明する。
本実施例での難読化装置１は、図１９に示すように手順Ｓ１９１〜Ｓ１９６に従って処理を行う。
上記の各実施例では、複数の条件式からなる条件式和集合Ｓ’と、条件式和集合Ｓ’に同値であるが条件式和集合Ｓ’に含まれる条件式とは異なる条件式の条件式和集合Ｔ’と、複数の可逆な関数と、を用いているが、本実施例の特徴は、これに加えて条件式和集合Ｓ’（と条件式和集合Ｔ’）に同値であるが条件式和集合Ｓ’に含まれる条件式とも条件式和集合Ｔ’に含まれる条件式とも異なる条件式の条件式和集合Ｕ’を用いる点である。
本実施例での難読化装置１は、図１９に示すような手順Ｓ１９１〜Ｓ１９６に従って処理を行う。
【００８２】
入力手段２でプログラムを入力として受け取り、解析手段５及び条件分岐生成手段６で、難読化対象関数を決め（Ｓ１９１）、難読化対象関数の入力変数ａを適当に選び、２以上の整数ｋ、ｎを適当に選び、このａとｋ、ｎを用いて、次の定める条件式の和集合Ｓ’、Ｔ’、Ｕ’を生成する（Ｓ１９２）。
Ｓ’＝［ａ ｍｏｄ ２ ＝＝０、ａ ｍｏｄ ２＝＝１］。
Ｔ’＝［ａ ｍｏｄ ２＊ｋ＝＝０、ａ ｍｏｄ ２＊ｋ＝＝１、…、ａ ｍｏｄ ２＊ｋ＝＝２＊ｋ―２、ａ ｍｏｄ ２＊ｋ＝＝２＊ｋ―１］。
Ｕ’＝［ａ ｍｏｄ ２＊ｎ＝＝０、ａ ｍｏｄ ２＊ｎ＝＝１、…、ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―２、ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―１］。
【００８３】
そして、解析手段５及び条件分岐生成手段６で、可逆関数ｇ１、ｇ２を生成し（Ｓ１９３）、難読化対象関数中からｇ１、ｇ２による操作対象の変数ｂを適当に選び、難読化対象関数中の位置ｐ１、ｐ２、ｐ３を決定する（Ｓ１９４）。ただし、位置ｐ１、ｐ２、ｐ３の３つの位置のいずれの間でも変数ａ、ｂは使われないとする。
そして、挿入手段７が次のような条件分岐集合Ｓ、Ｔ、Ｕを位置ｐ１、ｐ２、ｐ３に挿入し（Ｓ１９５）、出力手段４が難読化されたプログラムを出力する（Ｓ１９６）。
【００８４】
なお、以下の説明で、ｇ１１‘、ｇ１２’は、ｇ１‘（ｘ）＝ｇ１２’（ｇ１１‘（ｘ））を満たす関数とする（ｇ１’はｇ１の逆関数）。また、ｇ２１‘、ｇ２２’は、ｇ２‘（ｘ）＝ｇ２２’（ｇ２１‘（ｘ））を満たす関数とする（ｇ２’はｇ２の逆関数）。
【００８５】
第１の条件分岐集合Ｓとして、条件式和集合Ｓ’のａ ｍｏｄ ２＝＝０を条件式、ｂをｇ１によって変更する文を条件節とした条件分岐ｉｆ（ａ ｍｏｄ ２＝＝０）、ｂ＝ｇ１（ｂ）；を位置ｐ１に挿入する。
第１の条件分岐集合Ｓとして、条件式和集合Ｓ’のａ ｍｏｄ ２＝＝１を条件式、ｂをｇ２によって変更する文を条件節とした条件分岐ｉｆ（ａ ｍｏｄ ２＝＝０）、ｂ＝ｇ２（ｂ）；を位置ｐ１に挿入する。
【００８６】
第２の条件分岐集合Ｔとして、条件式和集合Ｔ’のａ ｍｏｄ ２＊ｋ＝＝０、ａ ｍｏｄ ２＊ｋ＝＝２、…、ａ ｍｏｄ ２＊ｋ＝＝２＊ｋ―２を条件式、ｂを関数ｇ１１‘によって変更する文を条件節としたｋ個の条件分岐ｉｆ（ａ ｍｏｄ ２＊ｋ＝＝０）、ｂ＝ｇ１１’（ｂ）； ｉｆ（ａ ｍｏｄ ２＊ｋ＝＝２）、ｂ＝ｇ１１‘（ｂ）；、…、ｉｆ（ａ ｍｏｄ ２＊ｋ＝＝２＊ｋ―２）、ｂ＝ｇ１１’（ｂ）；  を位置ｐ２に挿入する。
第２の条件分岐集合Ｔとして、条件式和集合Ｔ’のａ ｍｏｄ ２＊ｋ＝＝１、ａ ｍｏｄ ２＊ｋ＝＝３、…、ａ ｍｏｄ ２＊ｋ＝＝２＊ｋ―１を条件式、ｂを関数ｇ２１‘によって変更する文を条件節としたｋ個の条件分岐ｉｆ（ａ ｍｏｄ ２＊ｋ＝＝１）、ｂ＝ｇ２１’（ｂ）；ｉｆ（ａ ｍｏｄ ２＊ｋ＝＝ ３）、ｂ＝ｇ２１‘（ｂ）；、…、ｉｆ（ａ ｍｏｄ ２＊ｋ＝＝２＊ｋ―１）、ｂ＝ｇ２１’（ｂ）；を位置ｐ２に挿入する。
【００８７】
第３の条件分岐集合Ｕとして、条件式和集合Ｕ’のａ ｍｏｄ ２＊ｎ＝＝０、ａ ｍｏｄ ２＊ｎ＝＝２、…、ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―２を条件式、ｂを関数ｇ１１‘によって変更する文を条件節としたｎ個の条件分岐ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝０ ）、ｂ＝ｇ１２’（ｂ）；、ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝２）、ｂ＝ｇ１２‘（ｂ）；、…、ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―２）、ｂ＝ｇ１２’（ｂ）；を位置ｐ３に挿入する。
第３の条件分岐集合Ｕとして、条件式和集合Ｕ’のａ ｍｏｄ ２＊ｎ＝＝１、ａ ｍｏｄ ２＊ｎ＝＝３、…、ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―１を条件式、ｂを関数ｇ２２‘によって変更する文を条件節としたｎ個の条件分岐ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝１）、ｂ＝ｇ２２’（ｂ）；、ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝３）、ｂ＝ｇ２２‘（ｂ）；、…、ｉｆ（ａ ｍｏｄ ２＊ｎ＝＝２＊ｎ―１）、ｂ＝ｇ２２’（ｂ）；を位置ｐ３に挿入する。
【００８８】
図２０に、本実施例によって難読化されたプログラムの例を示す。図２０のプログラムは、図２１の関数f00に難読化を適用した例である。
上記の手順Ｓ１９１〜Ｓ１９６を行う際に、手順Ｓ１９２、Ｓ１９３、Ｓ１９４、Ｓ１９５でそれぞれ次のようにパラメーターを定めている。
【００８９】
手順Ｓ１９２において、難読化対象関数の入力変数ａとしてf00の入力変数ａを、２以上の以上の整数ｋ、ｎとしてｋ＝２、ｎ＝３を選ぶ。
手順Ｓ１９３において、可逆関数ｇ１、ｇ２としてｇ１（ｘ）＝２＊ｘ＋３、ｇ２（ｘ）＝４＊ｘ―５を生成する。
手順Ｓ１９４において、ｇ１、ｇ２による操作対象として、ｆ00の変数ｂを選ぶ。難読化対象関数中の位置Ｐｐ１、ｐ２、ｐ３として、図２１に示すf00中のｐ２０、ｐ２１を選ぶ（なお、本例では、ｐ２とｐ３は同じ位置ｐ２１として、条件分岐和集合Ｔ、Ｕを順に並べて挿入している）。
手順Ｓ１９５において、ｇ１１‘、ｇ１２’、ｇ２１‘、ｇ２２’を以下のように取る。 
ｇ１１‘（ｘ）＝ｘ―３、ｇ１２’（ｘ）＝ｘ／２、ｇ２１‘（ｘ）＝ｘ＋５、ｇ２２’（ｘ）＝ｘ／４、（但し、ｇ１１‘、ｇ１２’、ｇ２１‘、ｇ２２’は、ｇ１‘（ｘ）＝ｇ１２’（ｇ１１‘（ｘ））とｇ２’（ｘ）＝ｇ２２‘（ｇ２１’（ｘ））を満たす）
【００９０】
本発明に係る難読化は、頻度分析攻撃に対して理論的に安全である。この理由として、第１実施例において、難読化のために加えた条件分岐を頻度分析により特定するのは困難であることを以下に説明する。
【００９１】
まず、難読化対象プログラム（実施例では関数ｆ00）に挿入するｇ１（ｇ２）によって変数を変換する条件節（ｅとおく）とｇ１‘（ｇ２’）によって元に戻す条件節（ｎ個の条件節をそれぞれｄ１、…、ｄｎとおく）の間の相関度を考える。ｅが実行されれば、ｄ１、…、ｄｎのいずれかが必ず実行され、更に、そのときｄ１、…、ｄｎの実行される確率はそれぞれ１／ｎである。このことから頻度分析において、ｅとｄ１、…、ｄｎの間の相関度はそれぞれ１／ｎと計算される。
【００９２】
ところで、上記のように手順１、２に従うことで、１／ｎ＜＝Ｑなるｎを選択することができる（Ｑは、プログラムに元々含まれる任意の２つの条件節間の相関度の平均）。つまり、手順１、２に従うと、挿入する条件節ｅ,ｄｉ間の相関度（ｉは集合［１、…、ｎ］に含まれる）は、プログラムに元々含まれていた条件分岐の間の相関度Ｑと比べて大きくならない。このことは、ｅとｄｉが（変数の可逆操作のペアであるという意味で）関連を持っていることを識別するのは、頻度分析では困難であることを意味する。
このように、本発明によると、頻度分析攻撃に対して理論的に安全な難読化を実施することが可能である。
【００９３】
更に説明すると、手順１、２に対する攻撃手法として、条件節の集合間の相関度を計算する方法が考えられる。ここで、２つの条件節の集合Ｈ＝（ｈ１、…、ｈｍ）、Ｇ＝（ｇ１、…、ｇｎ）の間の相関度を、Ｈ中のいずれかの条件節とＧ中のいずれかの条件節が同時に実行される度合いとして定める。
例えば、｛ｅ｝と｛ｄ１、…、ｄｎ｝の間の相関度としては、頻度分析により何度も実行トレースを取ることで、１に近い値が得られる。なぜなら、ｅが実行されたときは必ずｄ１、…、ｄｎのいずれかが実行されるからである。このように、相関度の高い２つの条件節集合を発見することで、難読化対象プログラム中に追加した条件分岐を特定するという攻撃が想定される。
【００９４】
しかしながら、上記のような条件節の集合間の相関度を計算する方法は、計算量的に困難である。今、条件節がｓ個含まれているプログラムに、上記の本発明に係るいずれかの実施例によって難読化を適用したとする。この時、２＋２ｎ個の条件節が挿入されるので、難読化適用済プログラムにはｓ＋２＋２ｎ個の条件節が含まれることになる。この難読化済プログラムの難読化を無効化するには｛ｅ｝と｛ｄ１、…、ｄｎ｝の間の相関度が高いことを特定する必要がある。
ところが、ｓ＋２＋２ｎ個の条件節から要素数が１、ｎの集合のペアを抽出する場合の数は、ｓ＞＞ｎのとき、ｓ＾ｎ＝ｅｘｐ（ｎ＊ｌｏｇｓ）に比例する。つまり、条件式集合のペアの場合の数は、ｎに関して指数関数的に増加する。このため、ｎが十分大きい場合、｛ｅ｝と｛ｄ１、…、ｄｎ｝が相関度の高い相関度を持つと特定することは計算量的に困難である。
【図面の簡単な説明】
【００９５】
【図１】本発明の一実施例に係るプログラム難読化装置の構成図である。
【図２】本発明の一実施例に係るプログラム難読化装置のハードウエア構成図である。
【図３】本発明の一実施例に係るプログラム難読化装置の利用形態の一例を説明する図である。
【図４】本発明の一実施例に係るプログラム難読化装置の利用形態の一例を説明する図である。
【図５】本発明により難読化したプログラムの一例を説明する図である。
【図６】本発明の第１実施例に係る処理手順を説明する図である。
【図７】本発明の第１実施例により難読化したプログラム例を説明する図である。
【図８】本発明の第２実施例に係る処理手順を説明する図である。
【図９】本発明の第２実施例により難読化したプログラム例を説明する図である。
【図１０】場合分けの範囲を説明する図である。
【図１１】場合分けの範囲を説明する図である。
【図１２】本発明により難読化したプログラム例を説明する図である。
【図１３】本発明により難読化したプログラム例を説明する図である。
【図１４】本発明により難読化したプログラム例を説明する図である。
【図１５】本発明の第３実施例に係る処理手順を説明する図である。
【図１６】本発明の第３実施例により難読化したプログラム例を説明する図である。
【図１７】本発明の第４実施例に係る処理手順を説明する図である。
【図１８】本発明の第４実施例により難読化したプログラム例を説明する図である。
【図１９】本発明の第５実施例に係る処理手順を説明する図である。
【図２０】本発明の第５実施例により難読化したプログラム例を説明する図である。
【図２１】プログラムの一例を説明する図である。
【図２２】難読化したプログラムの従来例を説明する図である。
【符号の説明】
【００９６】
１：プログラム難読化装置、  ２：入力手段、
３：難読化処理手段、  ４：出力手段、
５：解析手段（位置決定手段、相関度算出手段）、  ６：条件分岐生成手段、
７：挿入手段、  Ｓ：第１の条件分岐和集合、
Ｔ：第２の条件分岐和集合、  ｐｐ：プログラム部分、
ｐ１、ｐ２、ｐ２０、ｐ２１：挿入位置、  ａ：第１の変数、
ｂ：第２の変数、
【図１】
2008269398.tif 000003
【図２】
2008269398.tif 000004
【図３】
2008269398.tif 000005
【図４】
2008269398.tif 000006
【図５】
2008269398.tif 000007
【図６】
2008269398.tif 000008
【図７】
2008269398.tif 000009
【図８】
2008269398.tif 000010
【図９】
2008269398.tif 000011
【図１０】
2008269398.tif 000012
【図１１】
2008269398.tif 000013
【図１２】
2008269398.tif 000014
【図１３】
2008269398.tif 000015
【図１４】
2008269398.tif 000016
【図１５】
2008269398.tif 000017
【図１６】
2008269398.tif 000018
【図１７】
2008269398.tif 000019
【図１８】
2008269398.tif 000020
【図１９】
2008269398.tif 000021
【図２０】
2008269398.tif 000022
【図２１】
2008269398.tif 000023
【図２２】
2008269398.tif 000024