情報処理装置及び情報処理プログラム
【課題】動的解析に対しても効果のあるプログラムの難読化処理を行う情報処理装置を提供する。
【解決手段】情報処理装置の受付手段は、難読化処理の対象となるプログラムを受け付け、ダミーコード生成手段は、有限群の任意の要素に対して、有限群の位数回の演算を施したものが単位元になる演算を用いてダミーコードを生成し、プログラム合成手段は、前記ダミーコード生成手段によって生成されたダミーコードを、前記受付手段によって受け付けられたプログラムに合成する。
【解決手段】情報処理装置の受付手段は、難読化処理の対象となるプログラムを受け付け、ダミーコード生成手段は、有限群の任意の要素に対して、有限群の位数回の演算を施したものが単位元になる演算を用いてダミーコードを生成し、プログラム合成手段は、前記ダミーコード生成手段によって生成されたダミーコードを、前記受付手段によって受け付けられたプログラムに合成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置及び情報処理プログラムに関する。
【背景技術】
【０００２】
プログラムを悪意あるリバースエンジニアリングから守るために、様々なプログラム難読化技術が提案されている。難読化とは、プログラムを複雑に変換することで、プログラムの解析コストを大きくする技術である。
【０００３】
これに関連する技術として、例えば、特許文献１には、秘密データやアルゴリズムを読み取りにくくするとともに、スタックメモリの覗き見によるプログラムの秘密データの取得も困難にでき、さらには、一般的なプログラムに対して適用することができる難読化手法によりプログラムを難読化することを課題とし、プログラム中のデータを符号化規則を用いて符号化するデータ符号化部と、データ符号化部によって符号化された符号化データを含む演算式の各演算子に、演算子変換規則を適用することにより演算式を符号化演算式に変換する演算式変換部と、符号化演算式を復号化規則を用いて復号化演算式とする復号化処理部とを備えることが開示されている。
【０００４】
また、例えば、特許文献２には、元のプログラムで用いられている変数の個数、ならびに当該変数間の参照・代入関係を秘匿し、かつ、秘密鍵の候補数を多くして耐性の高いプログラムの難読化を実現することを課題とし、プログラム中の変数を演算装置によって線形変換して符号化を施す符号化方法であって、符号化を施すｎ個（ただし、ｎは正整数）の変数を任意に選択するステップと、ｍ×ｎの行列（ただし、ｍは、ｍ≧ｎの正整数）及びｍ次元の任意のベクトルを生成するステップと、生成した行列及びベクトルを変換鍵として前記ｎ個の変数を線形変換して同時にｍ個の整数に符号化するステップとを有することが開示されている。
【０００５】
また、例えば、特許文献３には、プログラムが機密データや機密アルゴリズムを持つとき、前記プログラムを、安価な構成で、関数間解析を困難にするように難読化する方法であって、構成によっては難読化された前記プログラムの解析の困難さが証明されているような難読化方法及び装置によって前記プログラムを難読化し、前記プログラムへの不正アクセスを防ぐことを課題とし、プログラムのソースコードに対して、前記プログラムの仕様を変更しないように、関数へのポインタ変数を新たに複数個導入し、前記関数ポインタ変数のいずれかに関数のアドレスを代入する命令文を複数個挿入し、前記プログラムにおける関数の呼出しを、前記関数ポインタ変数の値に応じて関数を呼出すように変換することが開示されている。
【特許文献１】特開２００５−０４９９２５号公報
【特許文献２】特開２００６−０７９３４７号公報
【特許文献３】特開２００３−３３７６２９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、Opaque Predicatesを用いた難読化技術は、攻撃者がプログラムに対し動的解析を行うことによってプログラムの内容を解析できてしまう場合がある。
本発明は、動的解析による解析に対しても、その解析コストをより大きくするプログラムの難読化処理を行う情報処理装置及び情報処理プログラムを提供することを目的としている。
【課題を解決するための手段】
【０００７】
かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
請求項１の情報処理装置は、難読化処理の対象となるプログラムを受け付ける受付手段と、有限群の任意の要素に対して、有限群の位数回の演算を施したものが単位元になる演算を用いてダミーコードを生成するダミーコード生成手段と、前記ダミーコード生成手段によって生成されたダミーコードを、前記受付手段によって受け付けられたプログラムに合成するプログラム合成手段を具備することを特徴とする。
【０００８】
請求項２の情報処理装置は、請求項１に記載する情報処理装置であって、前記ダミーコード生成手段は、前記受付手段によって受け付けられたプログラム内の変数に対するダミーコードを生成することを特徴とする。
【０００９】
請求項３の情報処理装置は、請求項１又は２に記載する情報処理装置であって、前記ダミーコード生成手段は、互いに逆変換となる式を含むダミーコードを生成することを特徴とする。
【００１０】
請求項４の情報処理プログラムは、コンピュータを、難読化処理の対象となるプログラムを受け付ける受付手段と、有限群の任意の要素に対して、有限群の位数回の演算を施したものが単位元になる演算を用いてダミーコードを生成するダミーコード生成手段と、前記ダミーコード生成手段によって生成されたダミーコードを、前記受付手段によって受け付けられたプログラムに合成するプログラム合成手段として機能させることを特徴とする。
【発明の効果】
【００１１】
請求項１記載の情報処理装置によれば、動的解析による解析に対しても、本構成を有していない場合に比較して、その解析コストをより大きくするプログラムの難読化処理を行うことができるようになる。
【００１２】
請求項２記載の情報処理装置によれば、プログラム内の変数の値を変化させて、より安全性の高い難読化処理を行うことができるようになる。
【００１３】
請求項３記載の情報処理装置によれば、より安全性の高い難読化処理を行うことができるようになる。
【００１４】
請求項４記載の情報処理プログラムによれば、動的解析による解析に対しても、本構成を有していない場合に比較して、その解析コストをより大きくするプログラムの難読化処理を行うことができるようになる。
【発明を実施するための最良の形態】
【００１５】
本実施の形態は、プログラムの不正対策技術、例えば、不正な逆解析・リバースエンジ
ニアリング防止、難読化、耐タンパ（Ａｎｔｉ−Ｔａｍｐｅｒ）技術等に関するものである。
【００１６】
まず、難読化手法の１つとして知られている、不明瞭な条件式（以下、Opaque Predicates ともいう）を用いた難読化処理（［１］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を用いた難読化処理を適用した例を示す。なお、図１０に示すプログラムは、以下、第１の実施の形態、第２の実施の形態の説明においても、難読化処理の対象となるプログラムとして示す。これらのプログラムはＣ言語によるものを例示する。
【００１８】
図１０のプログラムのｐ１２の箇所に、「a*(a-1) mod 2 == 1」という条件式と「++a;」という条件節からなる条件分岐２１を加えることで、図１１のプログラムは生成されている。ここでmodとは、記号modの左にある整数値を右にある整数値で割った時の剰余を返す演算である（（例）7 mod 2 = 1）。
【００１９】
aがどのような整数値であっても、条件分岐２１内の「a*(a-1)」は、２の倍数であるため、「a*(a-1) mod 2」の値は常に０、つまり、「a*(a-1) mod 2 == 1」は恒偽のOpaque Predicateである。そのため、「++a;」という条件節は決して実行されない。
図１０と図１１に示すプログラムの機能・動作は変わらない一方で、図１１のプログラムには冗長な条件分岐２１が含まれている分、図１０のプログラムよりもプログラム全体の長さが長くなり、解析コスト、つまりプログラムの挙動解析に必要となるコストは大きくなる。これにより、解析が困難になり、難読化処理が施されたプログラムは元のプログラムに比較して安全性が向上することになる。
【００２０】
しかし、このようなOpaque Predicatesを用いた難読化処理には、プログラムの入力を変えても、付加したOpaque Predicatesの真偽値が変化しないという点がある。そのため、攻撃者は難読化処理を適用したプログラムに動的解析を行うことで、Opaque Predicatesを用いた難読化処理を無効化できる。ここで動的解析とは、プログラムを実行しつつ、プログラムにランダムに入力を与えたり、プログラム内部を書き換えたりすることで、出力結果や実行フローの違いを観察することでプログラムの挙動を分析することをいう。
【００２１】
攻撃者はプログラムに対し、以下に述べるような動的解析を行うことで、Opaque Predicatesを無効化できる。
通常考えられる条件分岐の場合、プログラムの入力を変えればある割合でその真偽値も変化する。しかし、Opaque Predicatesの真偽値はどのような入力に対しても変化しない。つまり、Opaque Predicatesを用いた条件分岐の条件節は、どのような入力においても必ず実行されるか、必ず実行されないかのいずれかである。
このことを利用して、動的解析において入力を変えて何度も実行フローを観察するうちに、攻撃者は、必ず実行される／必ず実行されない条件節を特定できる。これにより、Opaque Predicatesを利用した難読化処理は無効化されてしまう。
【００２２】
このため、以下に説明する実施の形態では、有限群の任意の要素に対して有限群の位数回の演算を施したものが単位元になる性質を利用することで、動的解析に対しても堅牢なプログラムの難読化処理を行う。このプログラムの難読化処理では、前記の性質を利用して入力によって変換式の出力値は変化するが、プログラムの挙動に変更を与えないような変換式群を与え、この変換式群を用いて任意の長さのダミーコードを生成することができる。前述のようにOpaque Predicatesを用いた難読化処理は動的解析により比較的簡単に無効化されてしまうが、本実施の形態によれば動的解析に対して安全性が高い難読化処理を行うことができる。
【００２３】
以下、図面に基づき本発明を実現するにあたっての好適な各種の実施の形態の例を説明する。
図１は、第１の実施の形態の構成例についての概念的なモジュール構成図を示している。
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア（コンピュータ・プログラム）、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはコンピュータ・プログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、コンピュータ・プログラム、システム及び方法の説明をも兼ねている。ただし、説明の都合上、「記憶する」、「記憶させる」、これらと同等の文言を用いるが、これらの文言は、実施の形態がコンピュータ・プログラムの場合は、記憶装置に記憶させること、又は記憶装置に記憶させるように制御するの意である。また、モジュールは機能にほぼ一対一に対応しているが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、１つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示、データ間の参照関係等）を含む。
また、システム又は装置とは、複数のコンピュータ、ハードウェア、装置等がネットワーク（一対一対応の通信接続を含む）等の通信手段で接続されて構成されるほか、１つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。
【００２４】
難読化装置は、プログラムに対して難読化処理を施すものであって、図１に示すように、プログラム受付モジュール１１０、プログラム合成モジュール１２０、ダミーコード生成モジュール１３０、プログラム送信モジュール１４０を有している。
プログラム受付モジュール１１０は、プログラム合成モジュール１２０と接続されており、難読化処理の対象となるプログラムを受け付け、そのプログラムをプログラム合成モジュール１２０へ渡す。
【００２５】
プログラム合成モジュール１２０は、プログラム受付モジュール１１０、ダミーコード生成モジュール１３０、プログラム送信モジュール１４０と接続されており、ダミーコード生成モジュール１３０によって生成されたダミーコードを、プログラム受付モジュール１１０によって受け付けられたプログラムに合成し、そのプログラム（すなわち、難読化処理されたプログラム）をプログラム送信モジュール１４０へ渡す。
【００２６】
ダミーコード生成モジュール１３０は、プログラム合成モジュール１２０と接続されており、有限群の任意の要素に対して、有限群の位数回の演算を施したものが単位元になる演算を用いてダミーコードを生成し、そのダミーコードをプログラム合成モジュール１２０へ渡す。より具体的には、有限群として剰余環Ｚ／ｎＺ（ｎは整数）上の乗法群を利用するようにしてもよいし、有限群として楕円曲線上の加法群を利用するようにしてもよい。
また、ダミーコード生成モジュール１３０は、プログラム受付モジュール１１０によって受け付けられたプログラム内の変数に対するダミーコードを生成するようにしてもよい。より具体的には、プログラム内の変数を引数として、有限群の性質を利用して関数を生成する。
さらに、ダミーコード生成モジュール１３０は、互いに逆変換となる式を含むダミーコードを生成するようにしてもよい。より具体的には、有限群の性質を利用して互いに逆変換となる２つの関数をダミーコードとして生成し、さらに、その関数によってプログラム内の変数を処理するようにしてもよいし、その２つの関数の対が複数あってもよい。そして、２つの関数の対を複数生成した場合、プログラム合成モジュール１２０は、対となる２つの関数が入れ子の状態になるように、プログラムと合成する。
【００２７】
プログラム送信モジュール１４０は、プログラム合成モジュール１２０と接続されており、プログラム合成モジュール１２０によって合成されたプログラムを、そのプログラムを実行する装置へ送信する。
【００２８】
図２を用いて、第１の実施の形態を実現する場合のシステムの構成例を説明する。
このシステムは、プログラム難読化送信用ＰＣ２１０、プログラム受信実行用ＰＣ２２０を有しており、インターネット２３０がプログラム難読化送信用ＰＣ２１０とプログラム受信実行用ＰＣ２２０を接続している。
プログラム難読化送信用ＰＣ２１０は、第１の実施の形態を含んでおり、難読化処理したプログラムをプログラム受信実行用ＰＣ２２０へ送信する。プログラム受信実行用ＰＣ２２０は、プログラム難読化送信用ＰＣ２１０によって難読化処理されたプログラムを受け取り、そのプログラムを実行するものである。プログラム難読化送信用ＰＣ２１０、プログラム受信実行用ＰＣ２２０は、それぞれ複数あってもよい。
【００２９】
図３をもとに、第１の実施の形態による難読化装置の利用形態を説明する。
まず、図３の表記を説明する。人型の記号は、プログラム開発者３１又はユーザ３３を表し、四角形の記号は難読化装置３２を表す。矢印は、プログラムの交換を表す。つまり、矢印の起点の方から終点の方に、矢印に付記されたプログラムが渡されることを示す。
【００３０】
第１の実施の形態による難読化装置３２は、一般的なプログラム開発者３１によって利用されることを想定している。開発者３１は、ユーザの利用に供されるプログラムを開発する。プログラムの開発完了後、開発者３１はそのプログラムを難読化装置３２に入力として与える（Ｓ３０１）。
難読化装置３２は、受け取ったプログラムに対し、第１の実施の形態による難読化処理を施し、その後、難読化済プログラムを出力する（Ｓ３０２）。難読化装置３２は、入力プログラムと難読化済プログラムの機能及び出力が異ならないように入力プログラムを変換する。ただし、難読化済プログラムにはダミーコードが追加されているので、変換により元のプログラムよりも解析コストは大きくなる。
そして、開発者３１は、物理的に離れたところにいるユーザ３３に対し、難読化済プログラムを渡す（Ｓ３０３）。渡す手段としては、インターネットを介する方法、あるいはＣＤ−ＲＯＭ等のメディアにデータとして格納した後にこれを渡す方法等であってもよい。
【００３１】
難読化済プログラムがユーザに渡された時点での、プログラム開発者４１、ユーザ４２、開発者４１が作成したプログラム（元のプログラム）４３、難読化済プログラム４４の関係を図４に示す。
まず、図４の表記を説明する。人型の記号はプログラム開発者４１又はユーザ４２を表し、丸形の記号はプログラム４３又は難読化済プログラム４４を表す。
図４は、開発者４１が元のプログラム４３と難読化済プログラム４４を所持しており、またユーザ４２が難読化済プログラム４４のみを所持している状態を示す。
元のプログラム４３と難読化済プログラム４４の機能及び出力は同じなので、ユーザ４２は難読化済プログラム４４により元のプログラム４３と同じ機能及び出力を利用できる。さらに、ユーザ４２は元のプログラム４３を所持していないので、元のプログラム４３の持つ機密情報（例えば、ライセンスに関する情報など）を得るためには、難読化済プログラム４４を解析しなければならない。元のプログラム４３の解析コストよりも難読化済プログラム４４の解析コストの方が大きいので、元のプログラム４３をユーザに手渡す状況と比較すると、プログラムの機密情報が流出する機会はより小さい。
【００３２】
次に第１の実施の形態による難読化手法の手順を説明する。
ここでは、長さがnのダミーコードを生成し、これをプログラムに付加して難読化処理を施す場合を述べる。
まず、難読化処理を施すデータをxとした場合の変換式を生成する手順Ａを示す。また、手順Ａのフローチャートを図５に示す。以下において、max_xは難読化処理が施されるデータxの最大値を表すものとする。
【００３３】
＜手順Ａ＞
（ステップＳ５１）
max_x よりも大きな素数p,q1,・・・,qn-1を生成する。
（ステップＳ５２）
ランダムな正の整数kを選択し、k(p-1)+1を素因数分解して素因数s1,s2,・・・,smを算出する。
（ステップＳ５３）
m>=nであるならＳ５４へ進む。そうでなければ、Ｓ５２に戻る。
（ステップＳ５４）
m=nであるならＳ５６へ進む。そうでなければ、Ｓ５５へ進む。
（ステップＳ５５）
sm-n, sm-n-1,・・・,smを掛け合わせてできる合成数をsnとしてＳ５６へ進む。
（ステップＳ５６）
変換式を以下の式（数１）と置く。
【数１】
【００３４】
前記の手順Ａにより生成される変換式群がプログラムの挙動に影響を与えないことを以下に説明する。
まず、数２とすると、数３が成立する。
【数２】
【数３】
次に、数４とすると、数５が成立する。
【数４】
【数５】
ただし、前式で、K 及びK’は適当な正の整数である。このことから、xに変換式x=f1(x),x=f2(x),・・・,x=fn(x)を順次適用して得られる結果は、数６に示す式であることがわかる。
【数６】
【００３５】
pを法とする剰余全体をZ/pZで表記する。pは素数なのZ/pZは乗法に関する群を構成し、その位数はp-1となる。オイラーの定理により、有限群の任意の要素に対して有限群の位数回演算を施したものは単位元となる。よって、任意の整数wに対して、数７に示す式が成立する。
【数７】
このとき、数８に示す式となるため、変換式x=f1(x),x=f2(x),・・・,x=fn(x)を適用した後のxの値と変換を適用しない状態のxの値は同じものとなる。
【数８】
このため、プログラム中の適当な変数xに前記の変換式群x=f1(x),x=f2(x),・・・,x=fn(x)を適用してもプログラムの挙動に影響が出ないことがわかる。
【００３６】
次に、前記変換式を利用したダミーコードの生成手順を説明する。
図６に、このダミーコードの生成手順のフローチャートを示す。
まず、プログラム中の難読化処理を施す変数とダミーコードの長さを選択する（ステップＳ６１）。ここでは、前記同様選択される変数をx、ダミーコードの長さをnとする。ダミーコードは長いほど、攻撃者が解析に用するコストが大きくなるが、一方で難読化処理後のプログラムの実行時間も増加する。このため、nは難読化済プログラムの実行速度に関する要求仕様に見合うような適切なものを選択する。
前述した手順Ａを用いて、x=f1(x),x=f2(x),・・・,x=fn(x)を作成する（ステップＳ６２）。
【００３７】
次に、プログラム中でxの値に関して参照あるいは代入が発生する場所prを決定し（ステップＳ６３）、プログラムのフロー上prの上位にあり、prに最も近いところにあるxの参照あるいは代入が発生する場所psを決定する（ステップＳ６４）。
次に、prとpsに挟まれた領域内のランダムな位置に変換式x=f1(x),x=f2(x),・・・,x=fn(x)を挿入していく（ステップＳ６５）。ただし、プログラムのフロー上においてx=fn(x)が最後になるようにする。
【００３８】
図７に、この実施例によって生成されるプログラムの例を示す。
図７のプログラムは、図１０に示すプログラムである関数funcに難読化処理を適用した例である。図７のプログラムの動作について説明する。
式ｆ７１から式ｆ７４は、前記手順Ａによって生成された変換式である。ただし、ここでn=4、q1=41,q2=31,q3=29,p1=23である。これらの式は前記のprとpsに挟まれた領域内に適当に配置されており、式ｆ７１から式ｆ７４はデータcを順次変換していく。前記に示したとおり、手順Ａによって生成された変換式は、その全ての変換式を適用することでcの値を変化させない。このため、式ｆ７１から式ｆ７４によって構成されるダミーコードは元のプログラムの挙動を変化させない。
【００３９】
前述では、有限群として環Z/nZ上の乗法群を使用したが、有限体上に構成される楕円曲線上の加法群も同様に用いることができる。この際、ランダムな楕円曲線を生成し、その位数をSchoofの方法、あるいはその改良法で求める。楕円曲線上の加法群を用いる場合、上記の環Z/nZ上の乗法群において使用されるべき乗計算、及び乗算はそれぞれ全て乗算、及び加算となる。その他のダミーコードの生成手順は、環Z/nZ上の乗法群の場合と同様で、図６に示されたフローチャートと同様の手順である。
【００４０】
第２の実施の形態の構成例及び実現する場合のシステム構成例は、前述の第１の実施の形態の構成例（図１、図２）と同等である。また、第２の実施の形態における難読化装置の利用形態例は、前述の第１の実施の形態の利用形態例（図３、図４）と同等である。
第２の実施の形態では、可逆な変換式の対を複数個生成し、これらを用いてダミーコードを生成する例を説明する。
ダミーコードの生成手順は以下の手順Ｂで記述される。また、この手順のフローチャートを図８に示す。下記でpr及びpsは、第１の実施の形態の説明で定義されたものと同一である。
【００４１】
＜手順Ｂ＞
（ステップＳ８１）
ダミーコードの長さ2tを決定
（ステップＳ８２）
n=2として手順Ａを用いて、変換式の対（fi(x),fi-1(x)）をt個作成する。
（ステップＳ８３）
prを決定する。
（ステップＳ８４）
psを決定する。
（ステップＳ８５）
prとpsの間に、x=f1(x),x=f2(x),・・・,x=ft(x),x=ft-1(x),・・・,x=f2-1(x),x=f1-1(x)を、この順番に挿入する。
【００４２】
手順Ｂでは、互いに逆変換を与える変換式の対を利用するため、プログラム中の適当な変数xに前記の手順Ｂによって生成されるダミーコードを付加してもプログラムの挙動は変化しない。
ダミーコードの長さは2tで与えられるため、tの値は難読化済プログラムの実行速度に関する要求仕様に見合うような適切なものを選択するとよい。
【００４３】
図９に、第２の実施の形態によって生成されるプログラムの例を示す。
図９のプログラムは、図１０の関数funcに難読化処理を適用した例である。
図９のプログラムの動作について説明する。
式ｆ９０５からより式ｆ９１０は、前記手順Ｂによって生成された変換式である。式ｆ９０５と式ｆ９１０、式ｆ９０６と式ｆ９０９、式ｆ９０７と式ｆ９０８はそれぞれ互いの逆変換になっている。これらの式は前記のprとpsに挟まれた領域内に配置されており、難読化処理前の元のプログラムではこの領域内で変数cの値は変化しない。
手順Ｂによって生成された式ｆ９０５から式ｆ９１０を順次適用していくと、式ｆ９１０適用後のcの値は、式ｆ９０５の適用前の値と同じものになる。このため、難読化処理後もプログラムの挙動は変化しないことがわかる。
【００４４】
前述の実施の形態では、有限群の任意の要素に対して有限群の位数回演算を施したものが単位元になる性質を利用する。これにより、前述の実施の形態は動的解析に対して堅牢なプログラム難読化手法を提供している。このプログラム難読化手法では、前記の性質を利用して入力によって個々の変換式の出力値は変化するが、プログラムの挙動に変更を与えないような変換式群を与える。これを用いて任意の長さのダミーコードを生成する。前述のようにOpaque Predicatesを用いた難読化処理は動的解析により簡単に無効化されてしまうが、前述の実施の形態によるダミーコードはプログラムの入力に関連してその状態（変数の値）が変化するため、動的解析に対して安全性が高い難読化手法を提供している。
【００４５】
なお、第１及び第２の実施の形態としてのプログラムが実行されるコンピュータのハードウェア構成は、図１２に示すように、一般的なコンピュータであり、具体的にはパーソナルコンピュータ、サーバーとなり得るコンピュータ等である。プログラム受付モジュール１１０、プログラム合成モジュール１２０、ダミーコード生成モジュール１３０、プログラム送信モジュール１４０等のプログラムを実行するＣＰＵ１２０１と、そのプログラムやデータを記憶するＲＡＭ１２０２と、本コンピュータを起動するためのプログラム等が格納されているＲＯＭ１２０３と、補助記憶装置であるＨＤ１２０４（例えばハードディスクを用いることができる）と、キーボード、マウス等のデータを入力する入力装置１２０６と、ＣＲＴや液晶ディスプレイ等の出力装置１２０５と、通信ネットワークと接続するための通信回線インタフェース１２０７（例えばネットワークインタフェースカードを用いることができる）、そして、それらをつないでデータのやりとりをするためのバス１２０８により構成されている。これらのコンピュータが複数台互いにネットワークによって接続されていてもよい。
【００４６】
前述の実施の形態のうち、コンピュータ・プログラムによるものについては、本ハードウェア構成のシステムにソフトウェアであるコンピュータ・プログラムを読み込ませ、ソフトウェアとハードウェア資源とが協働して、前述の実施の形態が実現される。
なお、図１２に示すハードウェア構成は、１つの構成例を示すものであり、本実施の形態は、図１２に示す構成に限らず、本実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えばＡＳＩＣ等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図１２に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、特に、パーソナルコンピュータの他、情報家電、複写機、ファックス、スキャナ、プリンタ、複合機（スキャナ、プリンタ、複写機、ファックス等のいずれか２つ以上の機能を有している画像処理装置）などに組み込まれていてもよい。
【００４７】
なお、数式を用いて説明したが、数式には、その数式と同等のものを含めてもよい。同等のものとは、その数式そのものの他に、最終的な結果に影響を及ぼさない程度の数式の変形、又は数式をアルゴリズミックな解法で解くこと等が含まれる。
【００４８】
なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、前記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）等が含まれる。
そして、前記のプログラム又はその一部は、前記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組み合わせ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、前記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。
【図面の簡単な説明】
【００４９】
【図１】第１及び第２の実施の形態の構成例についての概念的なモジュール構成図である。
【図２】第１及び第２の実施の形態を実現する場合のシステムの構成例を示す説明図である。
【図３】第１及び第２の実施の形態における難読化装置の利用形態例を示す説明図である。
【図４】第１及び第２の実施の形態における難読化適用済プログラムをユーザに渡す状態例を示す説明図である。
【図５】第１の実施の形態における変換式を生成する処理例を示すフローチャートである。
【図６】第１の実施の形態におけるダミーコードの生成手順例を示すフローチャートである。
【図７】第１の実施の形態によって関数funcを難読化した例を示す説明図である。
【図８】第２の実施の形態におけるダミーコードの生成手順例を示すフローチャートである。
【図９】第２の実施の形態によって関数funcを難読化した例を示す説明図である。
【図１０】難読化対象の例である関数funcを示す説明図である。
【図１１】関数funcにOpaque Predicatesを用いた難読化処理を適用した例を示す説明図である。
【図１２】第１及び第２の実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。
【符号の説明】
【００５０】
１１０…プログラム受付モジュール
１２０…プログラム合成モジュール
１３０…ダミーコード生成モジュール
１４０…プログラム送信モジュール
２１０…プログラム難読化送信用ＰＣ
２２０…プログラム受信実行用ＰＣ
２３０…インターネット
【技術分野】
【０００１】
本発明は、情報処理装置及び情報処理プログラムに関する。
【背景技術】
【０００２】
プログラムを悪意あるリバースエンジニアリングから守るために、様々なプログラム難読化技術が提案されている。難読化とは、プログラムを複雑に変換することで、プログラムの解析コストを大きくする技術である。
【０００３】
これに関連する技術として、例えば、特許文献１には、秘密データやアルゴリズムを読み取りにくくするとともに、スタックメモリの覗き見によるプログラムの秘密データの取得も困難にでき、さらには、一般的なプログラムに対して適用することができる難読化手法によりプログラムを難読化することを課題とし、プログラム中のデータを符号化規則を用いて符号化するデータ符号化部と、データ符号化部によって符号化された符号化データを含む演算式の各演算子に、演算子変換規則を適用することにより演算式を符号化演算式に変換する演算式変換部と、符号化演算式を復号化規則を用いて復号化演算式とする復号化処理部とを備えることが開示されている。
【０００４】
また、例えば、特許文献２には、元のプログラムで用いられている変数の個数、ならびに当該変数間の参照・代入関係を秘匿し、かつ、秘密鍵の候補数を多くして耐性の高いプログラムの難読化を実現することを課題とし、プログラム中の変数を演算装置によって線形変換して符号化を施す符号化方法であって、符号化を施すｎ個（ただし、ｎは正整数）の変数を任意に選択するステップと、ｍ×ｎの行列（ただし、ｍは、ｍ≧ｎの正整数）及びｍ次元の任意のベクトルを生成するステップと、生成した行列及びベクトルを変換鍵として前記ｎ個の変数を線形変換して同時にｍ個の整数に符号化するステップとを有することが開示されている。
【０００５】
また、例えば、特許文献３には、プログラムが機密データや機密アルゴリズムを持つとき、前記プログラムを、安価な構成で、関数間解析を困難にするように難読化する方法であって、構成によっては難読化された前記プログラムの解析の困難さが証明されているような難読化方法及び装置によって前記プログラムを難読化し、前記プログラムへの不正アクセスを防ぐことを課題とし、プログラムのソースコードに対して、前記プログラムの仕様を変更しないように、関数へのポインタ変数を新たに複数個導入し、前記関数ポインタ変数のいずれかに関数のアドレスを代入する命令文を複数個挿入し、前記プログラムにおける関数の呼出しを、前記関数ポインタ変数の値に応じて関数を呼出すように変換することが開示されている。
【特許文献１】特開２００５−０４９９２５号公報
【特許文献２】特開２００６−０７９３４７号公報
【特許文献３】特開２００３−３３７６２９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、Opaque Predicatesを用いた難読化技術は、攻撃者がプログラムに対し動的解析を行うことによってプログラムの内容を解析できてしまう場合がある。
本発明は、動的解析による解析に対しても、その解析コストをより大きくするプログラムの難読化処理を行う情報処理装置及び情報処理プログラムを提供することを目的としている。
【課題を解決するための手段】
【０００７】
かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
請求項１の情報処理装置は、難読化処理の対象となるプログラムを受け付ける受付手段と、有限群の任意の要素に対して、有限群の位数回の演算を施したものが単位元になる演算を用いてダミーコードを生成するダミーコード生成手段と、前記ダミーコード生成手段によって生成されたダミーコードを、前記受付手段によって受け付けられたプログラムに合成するプログラム合成手段を具備することを特徴とする。
【０００８】
請求項２の情報処理装置は、請求項１に記載する情報処理装置であって、前記ダミーコード生成手段は、前記受付手段によって受け付けられたプログラム内の変数に対するダミーコードを生成することを特徴とする。
【０００９】
請求項３の情報処理装置は、請求項１又は２に記載する情報処理装置であって、前記ダミーコード生成手段は、互いに逆変換となる式を含むダミーコードを生成することを特徴とする。
【００１０】
請求項４の情報処理プログラムは、コンピュータを、難読化処理の対象となるプログラムを受け付ける受付手段と、有限群の任意の要素に対して、有限群の位数回の演算を施したものが単位元になる演算を用いてダミーコードを生成するダミーコード生成手段と、前記ダミーコード生成手段によって生成されたダミーコードを、前記受付手段によって受け付けられたプログラムに合成するプログラム合成手段として機能させることを特徴とする。
【発明の効果】
【００１１】
請求項１記載の情報処理装置によれば、動的解析による解析に対しても、本構成を有していない場合に比較して、その解析コストをより大きくするプログラムの難読化処理を行うことができるようになる。
【００１２】
請求項２記載の情報処理装置によれば、プログラム内の変数の値を変化させて、より安全性の高い難読化処理を行うことができるようになる。
【００１３】
請求項３記載の情報処理装置によれば、より安全性の高い難読化処理を行うことができるようになる。
【００１４】
請求項４記載の情報処理プログラムによれば、動的解析による解析に対しても、本構成を有していない場合に比較して、その解析コストをより大きくするプログラムの難読化処理を行うことができるようになる。
【発明を実施するための最良の形態】
【００１５】
本実施の形態は、プログラムの不正対策技術、例えば、不正な逆解析・リバースエンジ
ニアリング防止、難読化、耐タンパ（Ａｎｔｉ−Ｔａｍｐｅｒ）技術等に関するものである。
【００１６】
まず、難読化手法の１つとして知られている、不明瞭な条件式（以下、Opaque Predicates ともいう）を用いた難読化処理（［１］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を用いた難読化処理を適用した例を示す。なお、図１０に示すプログラムは、以下、第１の実施の形態、第２の実施の形態の説明においても、難読化処理の対象となるプログラムとして示す。これらのプログラムはＣ言語によるものを例示する。
【００１８】
図１０のプログラムのｐ１２の箇所に、「a*(a-1) mod 2 == 1」という条件式と「++a;」という条件節からなる条件分岐２１を加えることで、図１１のプログラムは生成されている。ここでmodとは、記号modの左にある整数値を右にある整数値で割った時の剰余を返す演算である（（例）7 mod 2 = 1）。
【００１９】
aがどのような整数値であっても、条件分岐２１内の「a*(a-1)」は、２の倍数であるため、「a*(a-1) mod 2」の値は常に０、つまり、「a*(a-1) mod 2 == 1」は恒偽のOpaque Predicateである。そのため、「++a;」という条件節は決して実行されない。
図１０と図１１に示すプログラムの機能・動作は変わらない一方で、図１１のプログラムには冗長な条件分岐２１が含まれている分、図１０のプログラムよりもプログラム全体の長さが長くなり、解析コスト、つまりプログラムの挙動解析に必要となるコストは大きくなる。これにより、解析が困難になり、難読化処理が施されたプログラムは元のプログラムに比較して安全性が向上することになる。
【００２０】
しかし、このようなOpaque Predicatesを用いた難読化処理には、プログラムの入力を変えても、付加したOpaque Predicatesの真偽値が変化しないという点がある。そのため、攻撃者は難読化処理を適用したプログラムに動的解析を行うことで、Opaque Predicatesを用いた難読化処理を無効化できる。ここで動的解析とは、プログラムを実行しつつ、プログラムにランダムに入力を与えたり、プログラム内部を書き換えたりすることで、出力結果や実行フローの違いを観察することでプログラムの挙動を分析することをいう。
【００２１】
攻撃者はプログラムに対し、以下に述べるような動的解析を行うことで、Opaque Predicatesを無効化できる。
通常考えられる条件分岐の場合、プログラムの入力を変えればある割合でその真偽値も変化する。しかし、Opaque Predicatesの真偽値はどのような入力に対しても変化しない。つまり、Opaque Predicatesを用いた条件分岐の条件節は、どのような入力においても必ず実行されるか、必ず実行されないかのいずれかである。
このことを利用して、動的解析において入力を変えて何度も実行フローを観察するうちに、攻撃者は、必ず実行される／必ず実行されない条件節を特定できる。これにより、Opaque Predicatesを利用した難読化処理は無効化されてしまう。
【００２２】
このため、以下に説明する実施の形態では、有限群の任意の要素に対して有限群の位数回の演算を施したものが単位元になる性質を利用することで、動的解析に対しても堅牢なプログラムの難読化処理を行う。このプログラムの難読化処理では、前記の性質を利用して入力によって変換式の出力値は変化するが、プログラムの挙動に変更を与えないような変換式群を与え、この変換式群を用いて任意の長さのダミーコードを生成することができる。前述のようにOpaque Predicatesを用いた難読化処理は動的解析により比較的簡単に無効化されてしまうが、本実施の形態によれば動的解析に対して安全性が高い難読化処理を行うことができる。
【００２３】
以下、図面に基づき本発明を実現するにあたっての好適な各種の実施の形態の例を説明する。
図１は、第１の実施の形態の構成例についての概念的なモジュール構成図を示している。
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア（コンピュータ・プログラム）、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはコンピュータ・プログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、コンピュータ・プログラム、システム及び方法の説明をも兼ねている。ただし、説明の都合上、「記憶する」、「記憶させる」、これらと同等の文言を用いるが、これらの文言は、実施の形態がコンピュータ・プログラムの場合は、記憶装置に記憶させること、又は記憶装置に記憶させるように制御するの意である。また、モジュールは機能にほぼ一対一に対応しているが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、１つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示、データ間の参照関係等）を含む。
また、システム又は装置とは、複数のコンピュータ、ハードウェア、装置等がネットワーク（一対一対応の通信接続を含む）等の通信手段で接続されて構成されるほか、１つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。
【００２４】
難読化装置は、プログラムに対して難読化処理を施すものであって、図１に示すように、プログラム受付モジュール１１０、プログラム合成モジュール１２０、ダミーコード生成モジュール１３０、プログラム送信モジュール１４０を有している。
プログラム受付モジュール１１０は、プログラム合成モジュール１２０と接続されており、難読化処理の対象となるプログラムを受け付け、そのプログラムをプログラム合成モジュール１２０へ渡す。
【００２５】
プログラム合成モジュール１２０は、プログラム受付モジュール１１０、ダミーコード生成モジュール１３０、プログラム送信モジュール１４０と接続されており、ダミーコード生成モジュール１３０によって生成されたダミーコードを、プログラム受付モジュール１１０によって受け付けられたプログラムに合成し、そのプログラム（すなわち、難読化処理されたプログラム）をプログラム送信モジュール１４０へ渡す。
【００２６】
ダミーコード生成モジュール１３０は、プログラム合成モジュール１２０と接続されており、有限群の任意の要素に対して、有限群の位数回の演算を施したものが単位元になる演算を用いてダミーコードを生成し、そのダミーコードをプログラム合成モジュール１２０へ渡す。より具体的には、有限群として剰余環Ｚ／ｎＺ（ｎは整数）上の乗法群を利用するようにしてもよいし、有限群として楕円曲線上の加法群を利用するようにしてもよい。
また、ダミーコード生成モジュール１３０は、プログラム受付モジュール１１０によって受け付けられたプログラム内の変数に対するダミーコードを生成するようにしてもよい。より具体的には、プログラム内の変数を引数として、有限群の性質を利用して関数を生成する。
さらに、ダミーコード生成モジュール１３０は、互いに逆変換となる式を含むダミーコードを生成するようにしてもよい。より具体的には、有限群の性質を利用して互いに逆変換となる２つの関数をダミーコードとして生成し、さらに、その関数によってプログラム内の変数を処理するようにしてもよいし、その２つの関数の対が複数あってもよい。そして、２つの関数の対を複数生成した場合、プログラム合成モジュール１２０は、対となる２つの関数が入れ子の状態になるように、プログラムと合成する。
【００２７】
プログラム送信モジュール１４０は、プログラム合成モジュール１２０と接続されており、プログラム合成モジュール１２０によって合成されたプログラムを、そのプログラムを実行する装置へ送信する。
【００２８】
図２を用いて、第１の実施の形態を実現する場合のシステムの構成例を説明する。
このシステムは、プログラム難読化送信用ＰＣ２１０、プログラム受信実行用ＰＣ２２０を有しており、インターネット２３０がプログラム難読化送信用ＰＣ２１０とプログラム受信実行用ＰＣ２２０を接続している。
プログラム難読化送信用ＰＣ２１０は、第１の実施の形態を含んでおり、難読化処理したプログラムをプログラム受信実行用ＰＣ２２０へ送信する。プログラム受信実行用ＰＣ２２０は、プログラム難読化送信用ＰＣ２１０によって難読化処理されたプログラムを受け取り、そのプログラムを実行するものである。プログラム難読化送信用ＰＣ２１０、プログラム受信実行用ＰＣ２２０は、それぞれ複数あってもよい。
【００２９】
図３をもとに、第１の実施の形態による難読化装置の利用形態を説明する。
まず、図３の表記を説明する。人型の記号は、プログラム開発者３１又はユーザ３３を表し、四角形の記号は難読化装置３２を表す。矢印は、プログラムの交換を表す。つまり、矢印の起点の方から終点の方に、矢印に付記されたプログラムが渡されることを示す。
【００３０】
第１の実施の形態による難読化装置３２は、一般的なプログラム開発者３１によって利用されることを想定している。開発者３１は、ユーザの利用に供されるプログラムを開発する。プログラムの開発完了後、開発者３１はそのプログラムを難読化装置３２に入力として与える（Ｓ３０１）。
難読化装置３２は、受け取ったプログラムに対し、第１の実施の形態による難読化処理を施し、その後、難読化済プログラムを出力する（Ｓ３０２）。難読化装置３２は、入力プログラムと難読化済プログラムの機能及び出力が異ならないように入力プログラムを変換する。ただし、難読化済プログラムにはダミーコードが追加されているので、変換により元のプログラムよりも解析コストは大きくなる。
そして、開発者３１は、物理的に離れたところにいるユーザ３３に対し、難読化済プログラムを渡す（Ｓ３０３）。渡す手段としては、インターネットを介する方法、あるいはＣＤ−ＲＯＭ等のメディアにデータとして格納した後にこれを渡す方法等であってもよい。
【００３１】
難読化済プログラムがユーザに渡された時点での、プログラム開発者４１、ユーザ４２、開発者４１が作成したプログラム（元のプログラム）４３、難読化済プログラム４４の関係を図４に示す。
まず、図４の表記を説明する。人型の記号はプログラム開発者４１又はユーザ４２を表し、丸形の記号はプログラム４３又は難読化済プログラム４４を表す。
図４は、開発者４１が元のプログラム４３と難読化済プログラム４４を所持しており、またユーザ４２が難読化済プログラム４４のみを所持している状態を示す。
元のプログラム４３と難読化済プログラム４４の機能及び出力は同じなので、ユーザ４２は難読化済プログラム４４により元のプログラム４３と同じ機能及び出力を利用できる。さらに、ユーザ４２は元のプログラム４３を所持していないので、元のプログラム４３の持つ機密情報（例えば、ライセンスに関する情報など）を得るためには、難読化済プログラム４４を解析しなければならない。元のプログラム４３の解析コストよりも難読化済プログラム４４の解析コストの方が大きいので、元のプログラム４３をユーザに手渡す状況と比較すると、プログラムの機密情報が流出する機会はより小さい。
【００３２】
次に第１の実施の形態による難読化手法の手順を説明する。
ここでは、長さがnのダミーコードを生成し、これをプログラムに付加して難読化処理を施す場合を述べる。
まず、難読化処理を施すデータをxとした場合の変換式を生成する手順Ａを示す。また、手順Ａのフローチャートを図５に示す。以下において、max_xは難読化処理が施されるデータxの最大値を表すものとする。
【００３３】
＜手順Ａ＞
（ステップＳ５１）
max_x よりも大きな素数p,q1,・・・,qn-1を生成する。
（ステップＳ５２）
ランダムな正の整数kを選択し、k(p-1)+1を素因数分解して素因数s1,s2,・・・,smを算出する。
（ステップＳ５３）
m>=nであるならＳ５４へ進む。そうでなければ、Ｓ５２に戻る。
（ステップＳ５４）
m=nであるならＳ５６へ進む。そうでなければ、Ｓ５５へ進む。
（ステップＳ５５）
sm-n, sm-n-1,・・・,smを掛け合わせてできる合成数をsnとしてＳ５６へ進む。
（ステップＳ５６）
変換式を以下の式（数１）と置く。
【数１】
【００３４】
前記の手順Ａにより生成される変換式群がプログラムの挙動に影響を与えないことを以下に説明する。
まず、数２とすると、数３が成立する。
【数２】
【数３】
次に、数４とすると、数５が成立する。
【数４】
【数５】
ただし、前式で、K 及びK’は適当な正の整数である。このことから、xに変換式x=f1(x),x=f2(x),・・・,x=fn(x)を順次適用して得られる結果は、数６に示す式であることがわかる。
【数６】
【００３５】
pを法とする剰余全体をZ/pZで表記する。pは素数なのZ/pZは乗法に関する群を構成し、その位数はp-1となる。オイラーの定理により、有限群の任意の要素に対して有限群の位数回演算を施したものは単位元となる。よって、任意の整数wに対して、数７に示す式が成立する。
【数７】
このとき、数８に示す式となるため、変換式x=f1(x),x=f2(x),・・・,x=fn(x)を適用した後のxの値と変換を適用しない状態のxの値は同じものとなる。
【数８】
このため、プログラム中の適当な変数xに前記の変換式群x=f1(x),x=f2(x),・・・,x=fn(x)を適用してもプログラムの挙動に影響が出ないことがわかる。
【００３６】
次に、前記変換式を利用したダミーコードの生成手順を説明する。
図６に、このダミーコードの生成手順のフローチャートを示す。
まず、プログラム中の難読化処理を施す変数とダミーコードの長さを選択する（ステップＳ６１）。ここでは、前記同様選択される変数をx、ダミーコードの長さをnとする。ダミーコードは長いほど、攻撃者が解析に用するコストが大きくなるが、一方で難読化処理後のプログラムの実行時間も増加する。このため、nは難読化済プログラムの実行速度に関する要求仕様に見合うような適切なものを選択する。
前述した手順Ａを用いて、x=f1(x),x=f2(x),・・・,x=fn(x)を作成する（ステップＳ６２）。
【００３７】
次に、プログラム中でxの値に関して参照あるいは代入が発生する場所prを決定し（ステップＳ６３）、プログラムのフロー上prの上位にあり、prに最も近いところにあるxの参照あるいは代入が発生する場所psを決定する（ステップＳ６４）。
次に、prとpsに挟まれた領域内のランダムな位置に変換式x=f1(x),x=f2(x),・・・,x=fn(x)を挿入していく（ステップＳ６５）。ただし、プログラムのフロー上においてx=fn(x)が最後になるようにする。
【００３８】
図７に、この実施例によって生成されるプログラムの例を示す。
図７のプログラムは、図１０に示すプログラムである関数funcに難読化処理を適用した例である。図７のプログラムの動作について説明する。
式ｆ７１から式ｆ７４は、前記手順Ａによって生成された変換式である。ただし、ここでn=4、q1=41,q2=31,q3=29,p1=23である。これらの式は前記のprとpsに挟まれた領域内に適当に配置されており、式ｆ７１から式ｆ７４はデータcを順次変換していく。前記に示したとおり、手順Ａによって生成された変換式は、その全ての変換式を適用することでcの値を変化させない。このため、式ｆ７１から式ｆ７４によって構成されるダミーコードは元のプログラムの挙動を変化させない。
【００３９】
前述では、有限群として環Z/nZ上の乗法群を使用したが、有限体上に構成される楕円曲線上の加法群も同様に用いることができる。この際、ランダムな楕円曲線を生成し、その位数をSchoofの方法、あるいはその改良法で求める。楕円曲線上の加法群を用いる場合、上記の環Z/nZ上の乗法群において使用されるべき乗計算、及び乗算はそれぞれ全て乗算、及び加算となる。その他のダミーコードの生成手順は、環Z/nZ上の乗法群の場合と同様で、図６に示されたフローチャートと同様の手順である。
【００４０】
第２の実施の形態の構成例及び実現する場合のシステム構成例は、前述の第１の実施の形態の構成例（図１、図２）と同等である。また、第２の実施の形態における難読化装置の利用形態例は、前述の第１の実施の形態の利用形態例（図３、図４）と同等である。
第２の実施の形態では、可逆な変換式の対を複数個生成し、これらを用いてダミーコードを生成する例を説明する。
ダミーコードの生成手順は以下の手順Ｂで記述される。また、この手順のフローチャートを図８に示す。下記でpr及びpsは、第１の実施の形態の説明で定義されたものと同一である。
【００４１】
＜手順Ｂ＞
（ステップＳ８１）
ダミーコードの長さ2tを決定
（ステップＳ８２）
n=2として手順Ａを用いて、変換式の対（fi(x),fi-1(x)）をt個作成する。
（ステップＳ８３）
prを決定する。
（ステップＳ８４）
psを決定する。
（ステップＳ８５）
prとpsの間に、x=f1(x),x=f2(x),・・・,x=ft(x),x=ft-1(x),・・・,x=f2-1(x),x=f1-1(x)を、この順番に挿入する。
【００４２】
手順Ｂでは、互いに逆変換を与える変換式の対を利用するため、プログラム中の適当な変数xに前記の手順Ｂによって生成されるダミーコードを付加してもプログラムの挙動は変化しない。
ダミーコードの長さは2tで与えられるため、tの値は難読化済プログラムの実行速度に関する要求仕様に見合うような適切なものを選択するとよい。
【００４３】
図９に、第２の実施の形態によって生成されるプログラムの例を示す。
図９のプログラムは、図１０の関数funcに難読化処理を適用した例である。
図９のプログラムの動作について説明する。
式ｆ９０５からより式ｆ９１０は、前記手順Ｂによって生成された変換式である。式ｆ９０５と式ｆ９１０、式ｆ９０６と式ｆ９０９、式ｆ９０７と式ｆ９０８はそれぞれ互いの逆変換になっている。これらの式は前記のprとpsに挟まれた領域内に配置されており、難読化処理前の元のプログラムではこの領域内で変数cの値は変化しない。
手順Ｂによって生成された式ｆ９０５から式ｆ９１０を順次適用していくと、式ｆ９１０適用後のcの値は、式ｆ９０５の適用前の値と同じものになる。このため、難読化処理後もプログラムの挙動は変化しないことがわかる。
【００４４】
前述の実施の形態では、有限群の任意の要素に対して有限群の位数回演算を施したものが単位元になる性質を利用する。これにより、前述の実施の形態は動的解析に対して堅牢なプログラム難読化手法を提供している。このプログラム難読化手法では、前記の性質を利用して入力によって個々の変換式の出力値は変化するが、プログラムの挙動に変更を与えないような変換式群を与える。これを用いて任意の長さのダミーコードを生成する。前述のようにOpaque Predicatesを用いた難読化処理は動的解析により簡単に無効化されてしまうが、前述の実施の形態によるダミーコードはプログラムの入力に関連してその状態（変数の値）が変化するため、動的解析に対して安全性が高い難読化手法を提供している。
【００４５】
なお、第１及び第２の実施の形態としてのプログラムが実行されるコンピュータのハードウェア構成は、図１２に示すように、一般的なコンピュータであり、具体的にはパーソナルコンピュータ、サーバーとなり得るコンピュータ等である。プログラム受付モジュール１１０、プログラム合成モジュール１２０、ダミーコード生成モジュール１３０、プログラム送信モジュール１４０等のプログラムを実行するＣＰＵ１２０１と、そのプログラムやデータを記憶するＲＡＭ１２０２と、本コンピュータを起動するためのプログラム等が格納されているＲＯＭ１２０３と、補助記憶装置であるＨＤ１２０４（例えばハードディスクを用いることができる）と、キーボード、マウス等のデータを入力する入力装置１２０６と、ＣＲＴや液晶ディスプレイ等の出力装置１２０５と、通信ネットワークと接続するための通信回線インタフェース１２０７（例えばネットワークインタフェースカードを用いることができる）、そして、それらをつないでデータのやりとりをするためのバス１２０８により構成されている。これらのコンピュータが複数台互いにネットワークによって接続されていてもよい。
【００４６】
前述の実施の形態のうち、コンピュータ・プログラムによるものについては、本ハードウェア構成のシステムにソフトウェアであるコンピュータ・プログラムを読み込ませ、ソフトウェアとハードウェア資源とが協働して、前述の実施の形態が実現される。
なお、図１２に示すハードウェア構成は、１つの構成例を示すものであり、本実施の形態は、図１２に示す構成に限らず、本実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えばＡＳＩＣ等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図１２に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、特に、パーソナルコンピュータの他、情報家電、複写機、ファックス、スキャナ、プリンタ、複合機（スキャナ、プリンタ、複写機、ファックス等のいずれか２つ以上の機能を有している画像処理装置）などに組み込まれていてもよい。
【００４７】
なお、数式を用いて説明したが、数式には、その数式と同等のものを含めてもよい。同等のものとは、その数式そのものの他に、最終的な結果に影響を及ぼさない程度の数式の変形、又は数式をアルゴリズミックな解法で解くこと等が含まれる。
【００４８】
なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、前記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）等が含まれる。
そして、前記のプログラム又はその一部は、前記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組み合わせ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、前記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。
【図面の簡単な説明】
【００４９】
【図１】第１及び第２の実施の形態の構成例についての概念的なモジュール構成図である。
【図２】第１及び第２の実施の形態を実現する場合のシステムの構成例を示す説明図である。
【図３】第１及び第２の実施の形態における難読化装置の利用形態例を示す説明図である。
【図４】第１及び第２の実施の形態における難読化適用済プログラムをユーザに渡す状態例を示す説明図である。
【図５】第１の実施の形態における変換式を生成する処理例を示すフローチャートである。
【図６】第１の実施の形態におけるダミーコードの生成手順例を示すフローチャートである。
【図７】第１の実施の形態によって関数funcを難読化した例を示す説明図である。
【図８】第２の実施の形態におけるダミーコードの生成手順例を示すフローチャートである。
【図９】第２の実施の形態によって関数funcを難読化した例を示す説明図である。
【図１０】難読化対象の例である関数funcを示す説明図である。
【図１１】関数funcにOpaque Predicatesを用いた難読化処理を適用した例を示す説明図である。
【図１２】第１及び第２の実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。
【符号の説明】
【００５０】
１１０…プログラム受付モジュール
１２０…プログラム合成モジュール
１３０…ダミーコード生成モジュール
１４０…プログラム送信モジュール
２１０…プログラム難読化送信用ＰＣ
２２０…プログラム受信実行用ＰＣ
２３０…インターネット
【特許請求の範囲】
【請求項１】
難読化処理の対象となるプログラムを受け付ける受付手段と、
有限群の任意の要素に対して、有限群の位数回の演算を施したものが単位元になる演算を用いてダミーコードを生成するダミーコード生成手段と、
前記ダミーコード生成手段によって生成されたダミーコードを、前記受付手段によって受け付けられたプログラムに合成するプログラム合成手段
を具備することを特徴とする情報処理装置。
【請求項２】
前記ダミーコード生成手段は、前記受付手段によって受け付けられたプログラム内の変数に対するダミーコードを生成する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記ダミーコード生成手段は、互いに逆変換となる式を含むダミーコードを生成する
ことを特徴とする請求項１又は２に記載の情報処理装置。
【請求項４】
コンピュータを、
難読化処理の対象となるプログラムを受け付ける受付手段と、
有限群の任意の要素に対して、有限群の位数回の演算を施したものが単位元になる演算を用いてダミーコードを生成するダミーコード生成手段と、
前記ダミーコード生成手段によって生成されたダミーコードを、前記受付手段によって受け付けられたプログラムに合成するプログラム合成手段
として機能させることを特徴とする情報処理プログラム。
【請求項１】
難読化処理の対象となるプログラムを受け付ける受付手段と、
有限群の任意の要素に対して、有限群の位数回の演算を施したものが単位元になる演算を用いてダミーコードを生成するダミーコード生成手段と、
前記ダミーコード生成手段によって生成されたダミーコードを、前記受付手段によって受け付けられたプログラムに合成するプログラム合成手段
を具備することを特徴とする情報処理装置。
【請求項２】
前記ダミーコード生成手段は、前記受付手段によって受け付けられたプログラム内の変数に対するダミーコードを生成する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記ダミーコード生成手段は、互いに逆変換となる式を含むダミーコードを生成する
ことを特徴とする請求項１又は２に記載の情報処理装置。
【請求項４】
コンピュータを、
難読化処理の対象となるプログラムを受け付ける受付手段と、
有限群の任意の要素に対して、有限群の位数回の演算を施したものが単位元になる演算を用いてダミーコードを生成するダミーコード生成手段と、
前記ダミーコード生成手段によって生成されたダミーコードを、前記受付手段によって受け付けられたプログラムに合成するプログラム合成手段
として機能させることを特徴とする情報処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２００９−８６７４６（Ｐ２００９−８６７４６Ａ）
【公開日】平成２１年４月２３日（２００９．４．２３）
【国際特許分類】
【出願番号】特願２００７−２５２２７６（Ｐ２００７−２５２２７６）
【出願日】平成１９年９月２７日（２００７．９．２７）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
【公開日】平成２１年４月２３日（２００９．４．２３）
【国際特許分類】
【出願日】平成１９年９月２７日（２００７．９．２７）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
[ Back to top ]