(57)【要約】【課題】恒偽（又は恒真）の条件式を追加することでループに対して複数の入り口を設ける方式よりも動的解析に対する耐性が高いプログラム難読化のための装置を提供する。【解決手段】プログラム難読化装置は、難読化対象のプログラムからループA→B1→B2→Aを検出するループ検出部と、前記ループの前に恒偽及び恒真のいずれでもない条件式A'を追加すると共に、条件式A'の論理値が偽の場合には前記ループの先頭の条件式Aに進み、真の場合には前記ループ内の複数の実行文のうちの最初の実行文から途中の実行文までの実行文の組B1と等価な実行文の組B1'を実行した後前記ループ内の前記途中の実行文の次の実行文以降の組B2に進む、というフローを追加する条件分岐追加部と、を備える。【選択図】図５
2010191847.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを、
難読化対象のプログラムからループを検出する検出手段、
前記難読化対象のプログラムに対し、前記ループの前に恒偽及び恒真のいずれでもない条件式を追加すると共に、前記条件式の論理値が偽の場合には前記ループの先頭に進み、真の場合には前記ループ内の複数の実行文のうちの最初の実行文から途中の実行文までの実行文の組と等価な実行文の組を実行した後前記ループ内の前記途中の実行文の次の実行文に進む、というフローを追加する追加手段、
として機能させるためのプログラム難読化プログラム。
【請求項２】
前記追加手段は、前記ループ内に実行文が１つしかない場合には、当該実行文を当該実行文と等価な複数の実行文に置き換えた上で、前記条件式の論理値が真の場合には、当該複数の実行文のうちの最初の実行文から途中の実行文までの実行文の組と等価な実行文の組を実行した後、前記ループ内の前記途中の実行文の次の実行文に進むというフローを前記プログラムに追加する、ことを特徴とする請求項１記載のプログラム難読化プログラム。
【請求項３】
前記追加手段は、前記ループを継続するか否かを判定する判定条件式が前記ループの先頭に位置する場合には、前記恒偽及び恒真のいずれでもない条件式として、前記判定条件式の論理値が偽となる場合には必ず偽となる条件式を前記ループの前に追加する、ことを特徴とする請求項１又は２に記載のプログラム難読化プログラム。
【請求項４】
前記等価な実行文の組は、前記ループ内の複数の実行文のうちの最初の実行文から途中の実行文までの実行文の組と異なる表現を含むことを特徴とする請求項１〜３のいずれか１項に記載のプログラム難読化プログラム。
【請求項５】
難読化対象のプログラムからループを検出する検出手段と、
前記難読化対象のプログラムに対し、前記ループの前に恒偽及び恒真のいずれでもない条件式を追加すると共に、前記条件式の論理値が偽の場合には前記ループの先頭に進み、真の場合には前記ループ内の複数の実行文のうちの最初の実行文から途中の実行文までの実行文の組と等価な実行文の組を実行した後前記ループ内の前記途中の実行文の次の実行文に進む、というフローを追加する追加手段と、
を備えるプログラム難読化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム難読化プログラム及びプログラム難読化装置に関する。
【背景技術】
【０００２】
プログラムを悪意あるリバースエンジニアリングから保護するために、様々なプログラム難読化技術が提案されている。難読化とは、プログラムを複雑に変換することで、プログラムの解析コストを大きくする技術である。
【０００３】
従来の難読化手法の１つに、プログラムの逆コンパイルを阻止する手法がある。この手法を以降、逆コンパイル阻止手法と呼ぶ。逆コンパイル阻止手法は、プログラムを意味的に等価であるが逆コンパイルされにくい（例えば、逆コンパイラの異常終了や、逆コンパイラの誤った出力結果を引き起こす）プログラムに変換する手法である。
【０００４】
非特許文献１では、恒偽（又は恒真）の条件式を用いてループ構造の外から中へのダミーのフロー、つまり実行時には決して辿ることのないフロー、を付け加える難読化手法が言及されている。この手法により、元々制御フローグラフ上で単一の入り口しか持たなかったループ構造が、複数の入り口を持つようになる。なお、恒偽（又は恒真）の条件式とは、プログラム実行時に必ず偽（又は必ず真）と評価される条件式のことである。Ｃ言語やＪａｖａ言語を始めとした一般的なプログラミング言語によるソースコードでは、複数の入り口を持つループ構造を表現できない。そのため、この手法を適用されたバイナリプログラムが入力された逆コンパイラは、入力バイナリプログラムに対応する適切な出力ソースプログラムを出力できず、異常終了したり誤った結果を出力したりするようになる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】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
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、プログラムに対する入力を様々に変えながらプログラムの実行状況を解析する動的解析を行えば、プログラム中に恒偽（又は恒真）の条件式があればそれを判定することができる。そして、恒偽（又は恒真）と判定された条件式を用いた条件分岐をそのプログラムから削除すれば、難読化の効果が消失してしまう。
【０００７】
本発明は、恒偽（又は恒真）の条件式を追加することでループに対して複数の入り口を設ける方式よりも動的解析に対する耐性が高いプログラム難読化のためのプログラム及び装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
請求項１に係る発明は、コンピュータを、難読化対象のプログラムからループを検出する検出手段、前記難読化対象のプログラムに対し、前記ループの前に恒偽及び恒真のいずれでもない条件式を追加すると共に、前記条件式の論理値が偽の場合には前記ループの先頭に進み、真の場合には前記ループ内の複数の実行文のうちの最初の実行文から途中の実行文までの実行文の組と等価な実行文の組を実行した後前記ループ内の前記途中の実行文の次の実行文に進む、というフローを追加する追加手段、として機能させるためのプログラム難読化プログラムである。
【０００９】
請求項２に係る発明は、請求項１に係る発明において、前記追加手段は、前記ループ内に実行文が１つしかない場合には、当該実行文を当該実行文と等価な複数の実行文に置き換えた上で、前記条件式の論理値が真の場合には、当該複数の実行文のうちの最初の実行文から途中の実行文までの実行文の組と等価な実行文の組を実行した後、前記ループ内の前記途中の実行文の次の実行文に進むというフローを前記プログラムに追加する、ことを特徴とする。
【００１０】
請求項３に係る発明は、請求項１又は２に記載の発明において、前記追加手段は、前記ループを継続するか否かを判定する判定条件式が前記ループの先頭に位置する場合には、前記恒偽及び恒真のいずれでもない条件式として、前記判定条件式の論理値が偽となる場合には必ず偽となる条件式を前記ループの前に追加する、ことを特徴とする。
【００１１】
請求項４に係る発明は、請求項１〜３のいずれか１項に記載の発明において、前記等価な実行文の組は、前記ループ内の複数の実行文のうちの最初の実行文から途中の実行文までの実行文の組と異なる表現を含むことを特徴とする。
【００１２】
請求項５に係る発明は、難読化対象のプログラムからループを検出する検出手段と、前記難読化対象のプログラムに対し、前記ループの前に恒偽及び恒真のいずれでもない条件式を追加すると共に、前記条件式の論理値が偽の場合には前記ループの先頭に進み、真の場合には前記ループ内の複数の実行文のうちの最初の実行文から途中の実行文までの実行文の組と等価な実行文の組を実行した後前記ループ内の前記途中の実行文の次の実行文に進む、というフローを追加する追加手段と、を備えるプログラム難読化装置である。
【発明の効果】
【００１３】
請求項１又は５に係る発明によれば、恒偽（又は恒真）の条件式を追加することでループに対して複数の入り口を設ける方式よりも動的解析に対する耐性が高いプログラム難読化が実現できる。
【００１４】
請求項２に係る発明によれば、ループ内の実行文が１つしかない場合でも、請求項１に係る発明の処理を実現することができる。
【００１５】
請求項３に係る発明によれば、ループを継続するか否かを判定する判定条件式が前記ループの先頭に位置する場合でも、請求項１に係る発明の処理を実現することができる。
【００１６】
請求項４に係る発明によれば、ループ内の複数の実行文のうちの最初の実行文から途中の実行文までの実行文の組と全く同じ実行文の組を実行した後、その途中の実行文の次の実行文に進むフローを用いる場合よりも、難読性を高めることができる。
【図面の簡単な説明】
【００１７】
【図１】実施形態のプログラム難読化装置の概略構成を示す図である。
【図２】whileループ構造を難読化する処理の例を示すフローチャートである。
【図３】whileループ構造を表す制御フローグラフを例示する図である。
【図４】whileループ構造中の実行文の組の分割を例示する図である。
【図５】whileループ構造の難読化結果の制御フローグラフを例示する図である。
【図６】whileループ構造を表す制御フローグラフの具体例を示す図である。
【図７】図７のwhileループ構造の難読化結果の例を示す図である。
【図８】do-whileループ構造を難読化する処理の例を示すフローチャートである。
【図９】do-whileループ構造を表す制御フローグラフを例示する図である。
【図１０】do-whileループ構造中の実行文の組の分割を例示する図である。
【図１１】do-whileループ構造の難読化結果の制御フローグラフを例示する図である。
【図１２】do-whileループ構造を表す制御フローグラフの具体例を示す図である。
【図１３】図１２のdo-whileループ構造の難読化結果の例を示す図である。
【図１４】do-whileループ構造を難読化する処理の別の例を示すフローチャートである。
【図１５】do-whileループ構造を表す制御フローグラフを例示する図である。
【図１６】do-whileループ構造中の実行文の組の分割を例示する図である。
【図１７】do-whileループ構造の難読化結果の制御フローグラフを例示する図である。
【図１８】do-whileループ構造を表す制御フローグラフの具体例を示す図である。
【図１９】図１８のdo-whileループ構造の難読化結果の例を示す図である。
【発明を実施するための形態】
【００１８】
図１に、本実施形態のプログラム難読化装置１０の概略構成を示す。プログラム難読化装置１０は、入力された難読化対象プログラム１００に対し難読化処理を施すことで、難読化されたプログラム１１０を生成し出力する。難読化対象プログラム１００及び難読化されたプログラム１１０は例えばバイナリプログラムである。
【００１９】
プログラム難読化装置１０は、ループ検出部１２、条件分岐追加部１４及びルール記憶部１６を備える。ループ検出部１２は、難読化対象プログラム１００からループ構造を検出する。条件分岐追加部１４は、検出されたループ構造に対して、別の入り口を追加するための条件分岐を追加する。追加される条件分岐は、条件式や実行文などが含まれる。ルール記憶部１６は、追加される条件分岐を構成する条件式や実行文を生成するためのルール情報を保持している。条件分岐追加部１４は、それらルール情報を参照して、条件分岐を追加する。
【００２０】
プログラム難読化装置１０が実行する難読化処理の一例を図２に示す。この例は、難読化対象プログラム１００中に含まれるwhileループ構造に対して難読化のための条件分岐を追加する場合の例である。
【００２１】
この処理では、装置１０は、まず難読化対象のバイナリプログラムPを入力として受け取る（Ｓ２１）。次に、ループ検出部１２は、そのバイナリプログラムPから制御フローグラフGを作成する（Ｓ２２）。バイナリプログラムから制御フローグラフを生成する処理は従来から知られており、そのような従来の処理を用いればよい。次に、ループ検出部１２は、制御フローグラフGから、任意にwhileループ構造を特定する（Ｓ２３）。ここで、特定したwhileループ構造の入り口の条件式をA、その条件式の論理値が真の場合に実行される実行文の組をBと呼ぶ（図３参照）。なお、図３以下のフローチャート例では、条件式のブロックから下に延びる矢印は条件式の論理値が真の場合のフローであり、条件式のブロックから左に延びる矢印は条件式の論理値が偽の場合のフローを示す。
【００２２】
次に条件分岐追加部１４が、実行文の組Bを2つの組B1, B2に分割する（図４参照）（Ｓ２４）。各組B1, B2には、それぞれ１以上の実行文が含まれるようにする。次に、条件分岐追加部１４が、恒真及び恒偽のいずれでもなくかつ条件式Aの論理値が偽の時は必ず偽と評価される条件式A'と、B1と等価な文の組B1'を生成する（Ｓ２５）。次に条件分岐追加部１４が、制御フローグラフG に以下の手順(i), (ii)に従って文B1'と条件式A'を追加することで、制御フローグラフG'（図５参照）を作成する（Ｓ２６）。すなわち、(i)制御フローグラフGに実行文の組B1'を追加し、さらに実行文の組B1'の実行後に実行文の組B2に進むという無条件分岐のフローを追加する。(ii) 制御フローグラフGに条件式A'を追加し、さらに条件式A'の論理値が真である場合は実行文の組B1'に進み、偽である場合には条件式Aに進むという条件分岐のフローを追加する。
【００２３】
次に、条件分岐追加部１４が、制御フローグラフG'からバイナリプログラムP'を作成し（Ｓ２７）、生成したバイナリプログラムP'を出力する（Ｓ２８）。
【００２４】
なお、制御フローグラフG内に複数のwhileループが存在する場合には、それらwhileループごとにステップＳ２３〜Ｓ２６の処理が行われる。
【００２５】
次に具体例を用いて、図２の処理手順の処理内容を更に説明する。例えば、難読対象のプログラムPに例えばwhileループ  while(a>0){b=a+1;c=2*b;a=a-1;} が含まれていたとする。
【００２６】
この場合、制御フローグラフG中のそのwhileループを表す部分は図６に示すようなものとなる。このwhileループには、条件式６０１（a>0）の論理値が真の場合に３つの実行文{b=a+1;c=2*b;a=a-1;}からなる実行文の組６０２に進むというフロー６０３と、実行文の組６０２の実行後に条件式６０１に戻るというフロー６０４とが含まれている。ステップＳ２３でこのループ構造が選択され、ステップＳ２４で実行文の組B（６０２）が、B1=｛b=a+1;｝と、B2={c=2*b; a=a-1;}という２つの組に分割されたとする。実行文の組をステップＳ２４でどのように分割するかは、あらかじめルール記憶部１６にルール情報として登録しておけばよい。このようなルール情報としては、例えば、実行文の組Bの最初の１つの文をB1とし、残りの文の組をB2とする、という規則を示すものでもよい。
【００２７】
次に条件分岐追加部１４は、ステップＳ２５において、条件式A'として例えば a > 10 を、追加する実行文の組B1'としてb ={ a + a*(a-1)%2 + 1; }を作成したとする（ここで、%は剰余演算子とする）。この例で作成した条件式A'は、ステップＳ２５中に示した「恒真及び恒偽のいずれでもなくかつ条件式Aの論理値が偽の時は必ず偽と評価される」という条件を満たしている。このような条件を満たす条件式A'は、ルール記憶部１６に登録されたルール情報に基づき自動生成すればよい。例えば、元の条件式Aが不等式の場合には、その不等式における小さい側の辺の値（図６の例では「０」）をより大きな値（例えば「１０」）に変更するというルール、又はその逆に、大きい側の辺の値（図６の例では「ａ」）を、より小さい値（例えば「ａ−１０」）に変更するというルールなどが考えられる。また、別のルールとして、条件式Aの左辺又は右辺に、演算結果が０となる項（例えば「a*(a-1)%2」）を追加するルールも考えられる。このルールは、元の条件式Aと追加する条件式A'とは等価となる。このように元の条件式Aと等価な条件式A'も「恒真及び恒偽のいずれでもなくかつ条件式Aの論理値が偽の時は必ず偽と評価される」という条件を満たす。なお、追加する条件式A'は、元の条件式Aと全く同じものであってもよいが、難読化のためには上に例示したように元の条件式と異なった表現となるものを用いる方がよい。また、この例で作成した文の組B1'についても、変数aはいかなる値でもa*(a-1)%2の値は0になるので、文の組B1と等価となっている。ある実行文に等価な条実行文を生成するルールとしては、表現は異なるが算術的に等価な式を生成するルールを用いることが考えられる。制御フローグラフGに追加する文の組B1'は、元の文の組B1と全く同じものでもよいが、難読性を高めるためには、異なった表現のものとした方がよい。
【００２８】
そして、条件分岐追加部１４は、図７に例示するように、図６のwhileループに対し、条件式A'と実行文の組B1'とを追加する。そして、更に、条件式A'の評価結果が偽の場合に条件式Aに進むというフロー７０１と、条件式A'の評価結果が真の場合には実行文の組B1'に進むというフロー７０２と、その実行文の組B1'の実行後に実行文の組B2（より厳密にはその組内の先頭の文「c=2*b;」）に進むというフロー７０３とを追加する。なお、図７のフローグラフのうち、フロー７０４，７０５及び７０６からなるループ構造は、図６に示したフロー６０３及び６０４からなるループ構造と等価である。
【００２９】
図７に示した難読化結果の制御フローグラフG'では、フロー６０３及び６０４と等価なループ構造（７０４〜７０６）に対し、フロー７０１及び７０３という２つの入り口が存在している。また、条件式A'は恒真及び恒偽のいずれでもないので、aの値によってはフロー７０１及び７０３はどちらも辿られ得る。また、この難読化処理では、元の制御フローグラフGにあったループ構造６０３及び６０４には、新たな文は追加されない。
【００３０】
図６に示した構造を持つプログラム片と、図７に示した難読化後の構造を持つプログラム片の動作は等しい。すなわち、まず図７のプログラム片の実行直前でのaの値が10以下であったとする。この時、a > 10の条件判定は偽となり、制御はフロー７０１を辿って条件式Aに進む。それ以降の制御は、明らかに図６のそれと同じである。一方、実行直前でのaの値が10より大きいとする。この時、a > 10の条件判定は真となり、制御はフロー７０２を辿って実行文の組B1'（すなわち「 b = a + a*(a-1)%2 + 1;」）に進む。その後、制御はループ中の実行文の組B2（すなわち「c=2*b; a=a-1; 」）に進み、B2の実行後に条件式Aに戻る。ここで、実行文の組B1（「b = a + 1; 」）とB1'（「 b = a + a*(a-1)%2 + 1; 」）とは等価なので、実行文の組B1を実行した後実行文の組B2を実行した場合の演算結果と、実行文の組B1'を実行した後実行文の組B2を実行した場合の演算結果とは等しくなる。そして、実行文の組B2の実行後の処理は、条件式Aに進むので、図６のループと同じになる。このように、この図２に例示した処理は、元のプログラムの動作を変更することなく、ループ構造が複数の入り口を持つように変更している。
【００３１】
以上、元のプログラム中のwhileループ構造を難読化する処理の例を説明したが、次にdo-whileループ構造を難読化する処理の例を説明する。図８を参照して、この処理の手順の一例を説明する。
【００３２】
この処理では、装置１０は、まず難読化対象のバイナリプログラムPを入力として受け取る（Ｓ８１）。次に、ループ検出部１２は、そのバイナリプログラムPから制御フローグラフGを作成する（Ｓ８２）。次に、ループ検出部１２は、制御フローグラフGから、任意にdo-whileループ構造を特定する（Ｓ８３）。ここで、特定したdo-whileループ構造中の実行文の組をB、出口の条件式をAと呼ぶ（図９参照）。次に条件分岐追加部１４が、実行文の組Bを2つの組B1, B2に分割する（図１０参照）（Ｓ８４）。
【００３３】
次に、条件分岐追加部１４が、恒真及び恒偽のいずれでもない条件式Cと、B1と等価な文B1'を生成する（Ｓ８５）。次に条件分岐追加部１４が、制御フローグラフG に以下の手順(i), (ii)に従って文B1'と条件式Cを追加することで、制御フローグラフG'（図１１参照）を作成する（Ｓ８６）。すなわち、(i)制御フローグラフGに実行文の組B1'を追加し、さらに実行文の組B1'の実行後に実行文の組B2に進むという無条件分岐のフローを追加する。(ii) 制御フローグラフGに条件式Cを追加し、さらに条件式Cの論理値が真である場合は実行文B1'に進み、偽である場合には実行文の組B1に進むという条件分岐のフローを追加する。次に、条件分岐追加部１４が、制御フローグラフG'からバイナリプログラムP'を作成し（Ｓ８７）、生成したバイナリプログラムP'を出力する（Ｓ８８）。
【００３４】
なお、制御フローグラフG内に複数のdo-whileループが存在する場合には、それらdo-whileループごとにステップＳ８３〜Ｓ８６の処理が行われる。
【００３５】
次に具体例を用いて、図８の処理手順の処理内容を更に説明する。例えば、難読対象のプログラムPに例えばdo-whileループ「do{b=a+1;c=2*b;a=a-1;}while(a>0)」 が含まれていたとする。この場合、制御フローグラフG中のそのdo-whileループを表す部分は図１２に示すようなものとなる。以下では、このようなループが、図１３に示すようなループに変換される処理の流れを説明する。
【００３６】
この場合、そのdo-whileループは、３つの実行文{b=a+1;c=2*b;a=a-1;}からなる実行文の組１２０２を実行した後条件式１２０１（a>0）に進むというフロー１２０３と、条件式１２０１が真の場合に実行文の組１２０２に進むというフロー１２０４とから構成される。ステップＳ８３でこのループ構造が選択され、ステップＳ８４で実行文の組B（１２０２）が、B1=｛b=a+1;｝と、B2={c=2*b; a=a-1;}という２つの組に分割されたとする。実行文の組をステップＳ８４でどのように分割するかは、あらかじめルール記憶部１６にルール情報として登録しておけばよい。
【００３７】
次に条件分岐追加部１４は、ステップＳ８５において、条件式Cとして例えば「 b > c 」を、追加する実行文の組B1'としてb ={ a + a*(a-1)%2 + 1; }を作成したとする。この例で作成した条件式Cは「恒真及び恒偽のいずれでもない」という条件を満たしている。このような条件を満たす条件式Cは、ルール記憶部１６に登録されたルール情報に基づき自動生成すればよい。例えば、難読化対象のプログラム中に含まれる２つの変数を左辺と右辺に持つ不等式を条件式Cとして生成する、というルールが考えられる。難読化対象のプログラム中にdo-whileループが複数含まれる場合、追加する条件式Cをすべてのdo-whileループで同じものとしてもよいが、難読性を高めるためには、ループごとに条件式Cとして異なる式を用いた方がよい。この例で作成した文の組B1'は、図７の例で追加したものと同じであるため、説明を省略する。
【００３８】
そして、条件分岐追加部１４は、図１３に例示するように、図１２のdo-whileループに対し、条件式Cと実行文の組B1'とを追加する。そして、更に、条件式Cの評価結果が偽の場合に条件式B1に進むというフロー１３０１と、条件式Cの評価結果が真の場合には実行文の組B1'に進むというフロー１３０２と、その実行文の組B1'の実行後に実行文の組B2（より厳密にはその組内の先頭の文「c=2*b;」）に進むというフロー１３０３とを追加する。なお、図１３のフローグラフのうち、フロー１３０４，１３０５及び１３０６からなるループ構造は、図１２に示したフロー１２０３及び１２０４からなるループ構造と等価である。
【００３９】
図１３に示した難読化結果の制御フローグラフG'では、フロー１２０３及び１２０４からなるループ構造と等価なループ構造（１３０４〜１３０６）に対し、フロー１３０１及び１３０３という２つの入り口が存在している。また、条件式Cは恒真及び恒偽のいずれでもないので、式内の変数の値によってはフロー１３０１及び１３０３はどちらも辿られ得る。また、元の制御フローグラフGにあったループ構造１２０３及び１２０４には、新たな文は追加されない。
【００４０】
図１２に示した構造を持つプログラム片と、図１３に示した難読化後の構造を持つプログラム片の動作は等しい。すなわち、まず図１３に示すプログラム片の実行直前でbはc以下であったとする。この時、制御はフロー１３０１を辿って実行文の組B1に進む。それ以降の制御は、明らかに図１２のそれと同じである。一方、実行直前でcがb未満であったとする。この時、制御はフロー１３０２を辿って実行文の組B1'（すなわち「 b = a + a*(a-1)%2 + 1;」）に進む。その後、制御はループ中の実行文の組B2（すなわち「c=2*b; a=a-1; 」）に進み、B2の実行後に条件式Aに戻る。ここで、実行文の組B1とB1'とは等価なので、実行文の組B1を実行した後実行文の組B2を実行した場合の演算結果と、実行文の組B1'を実行した後実行文の組B2を実行した場合の演算結果とは等しくなる。そして、実行文の組B2の実行後の処理は、条件式Aに進むので、図１２のループと同じになる。このように、この図８に例示した処理は、元のプログラムの動作を変更することなく、do-whileループ構造が複数の入り口を持つように変更している。
【００４１】
次に、do-whileループ構造を図８に例示した処理よりも更に難読化する処理の例を、図１４〜図１９を参照して説明する。
【００４２】
この処理では、装置１０は、まず難読化対象のバイナリプログラムPを入力として受け取る（Ｓ１４１）。次に、ループ検出部１２は、そのバイナリプログラムPから制御フローグラフGを作成する（Ｓ１４２）。次に、ループ検出部１２は、制御フローグラフGから、任意にdo-whileループ構造を特定する（Ｓ１４３）。ここで、特定したdo-whileループ構造中の実行文の組をB、出口の条件式をAと呼び、条件式Aが偽となった場合に実行文の組Dが実行されるものとする（図１５参照）。次に条件分岐追加部１４が、実行文の組Bを2つの組B1, B2に分割する（図１６参照）（Ｓ１４４）。
【００４３】
次に、条件分岐追加部１４が、恒真及び恒偽のいずれでもない条件式Cと、条件式Cと等価な条件式C'と、実行文の組B1と等価な文の組B1'とを生成する（Ｓ１４５）。また、ステップＳ１４５では、難読化対象のdo-while構造内で用いられていない変数を可逆変換する実行文M1及びM2と、それら実行文M1及びM2の逆変換を表す実行文R1及びR2を生成する。すなわち、実行文M1及びM2は、可逆的な（すなわち逆変換により元の変数と全く同じ変数に戻る）変数変換を表す実行文である。実行文M1で変換された変数は、対応する実行文R1を実行することにより元の変数と同じ値に戻る。M2とR2も同様の関係にある。
【００４４】
次に条件分岐追加部１４が、制御フローグラフG に以下の手順(i)〜(viii)に従って文B1'と条件式Cを追加することで、制御フローグラフG'（図１７参照）を作成する（Ｓ１４６）。すなわち、まず(i)制御フローグラフGに実行文の組B1'を追加し、さらに実行文の組B1'の実行後に実行文の組B2に進むという無条件分岐のフローを追加する。また、(ii)実行文M1を追加し、M1の実行後に実行文の組B1'に進むという無条件分岐のフローを追加する。(iii) 実行文M2を追加し、M2の実行後に実行文の組B1に進むという無条件分岐のフローを追加する。(iv)条件式Cを追加し、更に条件式Cの論理値が真である場合は実行文M1に進み、偽である場合には実行文M2に進むという条件分岐のフローを追加する。(v)条件式Aの論理値が偽である場合に実行文の組Dに進むというフローを削除する。(vi)条件式C'を追加し、さらに条件式Aの論理値が偽である場合に条件式C'に進むというフローを追加する。(vii)実行文R1を追加し、さらに条件式C'の論理値が真である場合にR1に進むというフローと、R1の実行後に条件式の組Dに進むという無条件分岐のフローとを追加する。(viii)実行文R2を追加し、さらに条件式C'の論理値が偽である場合にR2に進むというフローと、R2の実行後に無条件でDに進むというフローを追加する。
【００４５】
次に、条件分岐追加部１４が、以上のようにして生成された制御フローグラフG'からバイナリプログラムP'を作成し（Ｓ１４７）、生成したバイナリプログラムP'を出力する（Ｓ１４８）。
【００４６】
なお、制御フローグラフG内に複数のdo-whileループが存在する場合には、それらdo-whileループごとにステップＳ１４３〜Ｓ１４６の処理が行われる。
【００４７】
次に具体例を用いて、図１４の処理手順の処理内容を更に説明する。例えば、難読対象のプログラムPに例えばdo-whileループを含んだプログラム片「do{b=a+1;c=2*b;a=a-1;}while(a>0); d=b+c+e;」 が含まれていたとする。
【００４８】
この場合、制御フローグラフG中のそのプログラム片を表す部分は図１８に示すようなものとなる。以下では、このようなプログラム片が、図１９に示すようなプログラム片に変換される処理の流れを説明する。
【００４９】
このプログラム片の中のdo-whileループは、３つの実行文{b=a+1;c=2*b;a=a-1;}からなる実行文の組１８０２を実行した後条件式１８０１（a>0）に進むというフロー１８０３と、条件式１８０１が真の場合に実行文の組１８０２に進むというフロー１８０４とから構成される。また、このプログラム片には、条件式１８０２が偽の場合に実行文Ｄ（１８０５）に進むというフローが含まれる。ステップＳ１４３でそのループ構造が選択され、ステップＳ１４４で実行文の組B（１８０２）が、B1=｛b=a+1;｝と、B2={c=2*b; a=a-1;}という２つの組に分割されたとする。実行文の組をステップＳ１４４でどのように分割するかは、あらかじめルール記憶部１６にルール情報として登録しておけばよい。
【００５０】
次に条件分岐追加部１４は、ステップＳ１４５において、条件式Cとして例えば「 e > 10 」を、これと等価な条件式C'として「 e > 0 && e*e > 100」を、追加する実行文の組B1'として「b ={ a + a*(a-1)%2 + 1; }」を、それぞれ作成する。この例で作成した条件式Cは「恒真及び恒偽のいずれでもない」という条件を満たしている。このような条件を満たす条件式Cは、ルール記憶部１６に登録されたルール情報に基づき自動生成すればよい。例えば、難読化対象のプログラム中で用いられていない変数を導入し、その変数があらかじめ定められた定数より大きいという不等式を条件式Cとして生成する、というルールが考えられる。また、条件式C'の生成ルールは、条件式Cの生成ルールと対応して定めることができる。例えば、上述のような不等式を条件式Cとする場合、その不等式に現れる変数を二乗したものがその定数の二乗より大きく、かつその変数は正であるという条件式C'を生成するというルールが考えられる。このように、ある条件式に等価な条件式を生成するルールとしては、表現は異なるが算術的に等価な式を生成するルールを用いることが考えられる。この例で作成した文の組B1'は、図７の例で追加したものと同じであるため、説明を省略する。
【００５１】
また、条件分岐追加部１４は、ステップＳ１４５において、ルール記憶部１６を参照して、変数を可逆変更する文M1, M2としてそれぞれd=2*d + 3, d=4*d - 5を、M1, M2のそれぞれの逆変換R1, R2としてd=(d - 3) / 2, d=(d+5) / 4を作成する。ルール記憶部１６には、例えば可逆的な変換x=2*x + 3とその逆変換x=(x - 3) / 2との組をルール情報として登録しておき、条件分岐追加部１４は難読化対象のループ構造内に含まれない変数を求め、その変数をそのルール情報の変数x に代入することで、具体的な変換M1とR1を生成すればよい。また、ルール記憶部１６には、そのような変換と逆変換の組を複数登録しておき、それら複数の組の中から、M1とM2に用いるものをそれぞれ個別に選択するようにしてもよい。また、難読化対象のプログラム中に複数のdo-whileループが存在する場合、難読性を高めるためには、それらdo-whileループごとに、使用するM1とM2の組合せを変えてもよい。図１９の例では、追加する可逆変換の文で用いる変数として、do-whileループから出た直後の実行文Dで用いられている変数d（この変数dはdo-whileループ内では用いられていない）を用いたが、これに限られるわけではない。例えば、難読化対象のプログラムに含まれていない変数を導入し、その変数を可逆変換する文を生成してもよい。ただし、難読性を増すためには、do-whileループから出た直後の実行文Dに含まれる変数を用いることが考えられる。
【００５２】
そして、条件分岐追加部１４は、図１９に例示するように、図１８のdo-whileループに対し、実行文の組B1'、条件式C及びC'、変数の可逆変換の文M1, M2とその逆変換R1, R2とを追加する。そして、更に、条件式Cの評価結果が偽の場合に文M2に進むというフロー１９０１と、文M2の実行後に文B1に進むというフロー１９０２とを追加し、条件式Cの評価結果が真の場合に文M1に進むというフロー１９０３と、文M1の実行後に実行文の組B1'に進むというフロー１９０４と、その実行文の組B1'の実行後に実行文の組B2（より厳密にはその組内の先頭の文「c=2*b;」）に進むというフロー１９０５とを追加する。
【００５３】
図１９のフローグラフのうち、フロー１９０６，１９０７及び１９０８からなるループ構造は、図１８に示したフロー１８０３及び１８０４からなるループ構造と等価である。
【００５４】
また、条件分岐追加部１４は、条件式Aが偽である場合に文Dに進むというフローを削除し、条件式Aが偽である場合に条件式C'に進むというフロー１９０９を追加する。そして、条件式C'が真である場合に文M1の逆変換R1に進むフロー１９１０と、R1の実行後に文Dに進むというフロー１９１１を追加する。また、条件式C'が偽である場合に文M2の逆変換R2に進むフロー１９１２と、R2の実行後に文Dに進むというフロー１９１３を追加する。
【００５５】
以上のような処理において追加された変数変換の文M1及びM2により変換された変数が実際に使用される実行文Dが実行される直前で、対応する逆変換の文R1及びR2によりそれぞれ元の値に戻される。したがって、図１９が示す制御フローの処理結果は、図１８が示す制御フローの処理結果と等価となる。
【００５６】
以上、本発明の実施形態を説明した。以上に説明したように、本実施形態では、一般的なマシン語が備えている条件分岐命令や無条件分岐命令、算術命令のみを用いることでプログラムを変換している。
【００５７】
以上では、whileループとdo-whileループという２種類のループの難読化処理の例を説明したが、上記実施形態の手法は他の種類のループにも適用できる。例えば、ループの終了判定（すなわち条件式A）をループの処理（すなわちループ内の実行文の組B)を実行する前に行う前判定方式のループ（例えばforループ）は、上述のwhileループと同様の処理を適用すればよい。また、ループの終了判定をループの処理を実行した後に行う後判定方式のループは、上述のdo-whileループと同様の処理を適用すればよい。
【００５８】
難読化対象のプログラム中に複数種類のループが含まれる場合には、個々のループごとに、当該ループの種類に応じて、前判定方式に対する難読化処理、後判定方式に対する難読化処理をそれぞれ適用すればよい。
【００５９】
また、以上の例では、難読化対象のループ中に複数の実行文が含まれていた（図６、図１２、図１８参照）。しかし、難読化対象のループ中に実行文が１つしかない場合にも、上述の実施形態の処理は適用できる。このような場合、条件分岐追加部１４は、ループ中の実行文を、その実行文と等価な処理を表す複数の実行文に変換すればよい。このような変換は、例えば、難読化対象のプログラムに影響を与えないダミーの実行文をループ内に追加することにより行えばよい。また、別の例として、ループ中の実行文Bで用いられる定数cを変数x（この変数xは難読化対象のプログラム中で用いられていないものにする）に代入する処理を表す実行文「x=c」をループ中の実行文Bの前に追加し、実行文B中の定数cを変数xに変更してもよい。
【００６０】
また、上記実施形態では、難読化においてループ構造中に新たに文や条件式を追加しない。従って、難読化に伴って発生する処理オーバーヘッドが予測しやすい。例えば、図２の例の処理によって生じるオーバーヘッドは以下のように見積もることができる。
【００６１】
まず、whileループの繰り返し実行回数をnとおく（ n ≧ 1）。この時、難読化前のプログラム（図６）の実行コストCbeforeは以下のように算出される。
Cbefore = n( c(A) + c(B1) + c(B2) ) + c(A)
ここで、c(X)は、文Xの実行コストを表すとする。
【００６２】
一方で、難読化後のプログラム（図７）の実行コストCafterは以下のように算出される。
Cafter = ( c(A') + c(B1') + c(B2) ) + (n - 1)( c(A) + c(B1) + c(B2) ) + c(A)
となる。
【００６３】
従って、実行オーバーヘッドCafter - Cbeforeは、
Cafter - Cbefore = ( c(A') - c(A) ) + ( c(B1') - c(B1) )
と見積もることができる。このように、本実施形態によって生じる実行オーバーヘッドはループ構造の実行回数に関わらず一定なので、予測しやすい。
【００６４】
以上に説明したプログラム難読化装置１０は、一つの例では、汎用のコンピュータに上述の処理を表すプログラムを実行させることにより実現される。ここで、コンピュータは、例えば、ハードウエアとして、ＣＰＵ等のマイクロプロセッサ、ランダムアクセスメモリ（ＲＡＭ）およびリードオンリメモリ（ＲＯＭ）等のメモリ（一次記憶）、ＨＤＤ（ハードディスクドライブ）コントローラを経由して接続されたＨＤＤ、各種Ｉ／Ｏ（入出力）インタフェース等が、バスを介して接続された回路構成を有する。バスには、ローカルエリアネットワーク等のネットワークに接続するためのネットワークインタフェースが接続されていてもよい。また、そのバスに対し、例えばＩ／Ｏインタフェース経由で、ＣＤやＤＶＤなどの可搬型ディスク記録媒体に対する読み取り及び／又は書き込みのためのディスクドライブ、フラッシュメモリなどの各種規格の可搬型の不揮発性記録媒体に対する読み取り及び／又は書き込みのためのメモリリーダライタなどが接続されてもよい。上に例示した各機能モジュールの処理内容が記述されたプログラムがＣＤやＤＶＤ等の記録媒体を経由して、又はネットワーク等の通信手段経由で、ハードディスクドライブ等の固定記憶装置に保存され、コンピュータにインストールされる。インストールされたプログラムがＲＡＭに読み出されＣＰＵ等のマイクロプロセッサにより実行されることにより、上に例示したプログラム難読化装置１０の機能が実現される。
【符号の説明】
【００６５】
１０  プログラム難読化装置、１２  ループ検出部、１４  条件分岐追加部、１６  ルール記憶部、１００  難読化対象のプログラム、１１０  難読化されたプログラム。
【図１】
2010191847.tif 000003
【図２】
2010191847.tif 000004
【図３】
2010191847.tif 000005
【図４】
2010191847.tif 000006
【図５】
2010191847.tif 000007
【図６】
2010191847.tif 000008
【図７】
2010191847.tif 000009
【図８】
2010191847.tif 000010
【図９】
2010191847.tif 000011
【図１０】
2010191847.tif 000012
【図１１】
2010191847.tif 000013
【図１２】
2010191847.tif 000014
【図１３】
2010191847.tif 000015
【図１４】
2010191847.tif 000016
【図１５】
2010191847.tif 000017
【図１６】
2010191847.tif 000018
【図１７】
2010191847.tif 000019
【図１８】
2010191847.tif 000020
【図１９】
2010191847.tif 000021