JP2003337629A - プログラム難読化方法及び装置 - Google Patents

Abstract

(57)【要約】 【課題】 プログラムが機密データや機密アルゴリズム
を持つとき、前記プログラムを、安価な構成で、関数間
解析を困難にするように難読化する方法であって、構成
によっては難読化された前記プログラムの解析の困難さ
が証明されているような難読化方法及び装置によって前
記プログラムを難読化し、前記プログラムへの不正アク
セスを防ぐ。 【解決手段】 プログラムのソースコードに対して、前
記プログラムの仕様を変更しないように、関数へのポイ
ンタ変数を新たに複数個導入し、前記関数ポインタ変数
のいずれかに関数のアドレスを代入する命令文を複数個
挿入し、前記プログラムにおける関数の呼出しを、前記
関数ポインタ変数の値に応じて関数を呼出すように変換
する。

Description

【発明の詳細な説明】

【０００１】

【発明が属する技術分野】本発明は、機密データや機密
アルゴリズム等を持つプログラムにおいて、前記データ
や前記アルゴリズム等への不正アクセスを防ぐ必要があ
る場合に、前記プログラムに対して、その解析が困難に
なるよう変換する難読化方法及び装置に関するものであ
る。

【０００２】

【従来の技術】近年のコンピュータネットワークの発展
により、プログラムの流通形態が変化している。従来
は、プログラムの流通はバイナリ形式で行うことが一般
的であったが、フリーソフトウェア等に見られるよう
に、ソースコード形式もしくはそれに近い形式でのプロ
グラムの流通が増大している。特に、近年、次世代のコ
ンピューティング基盤として注目を浴びているモバイル
エージェントシステムでは、機種依存性の問題から、モ
バイルエージェントはソースコードもしくはソースコー
ドに近い形で実現され、端末間を移動することが一般的
となっている。

【０００３】このような状況下では、悪意のある第三者
によって機密データや機密アルゴリズムを持つプログラ
ムが解析され、前記データが盗用されたり、前記アルゴ
リズムの知的財産権が侵害されたりする危険性が存在す
る。そこで、プログラムをこのような不正アクセスから
保護する方法が必要であると考えられる。

【０００４】前記保護方法としては、単純にプログラム
を暗号化するだけでは不十分であると考えられる。なぜ
ならば、暗号化されたプログラムは、流通の過程での解
析は非常に困難であるものの、そのままでは計算機は解
釈実行することができないことから、実行時にプログラ
ムを必ず復号化する必要があるため、復号後のプログラ
ムの保護が難しいからである。

【０００５】そこで、前記保護方法として、特開平８−
９５７７７号公報「ソフトウェア利用制御装置」に示さ
れているように、特殊なハードウェアを利用し、様々な
デジタルコンテンツをネットワーク上で流通させ、かつ
課金が可能であるようなシステム（「超流通」として知
られる）が提案されている。さらに、特殊なハードウェ
アを利用しない方法として、難読化によって、プログラ
ムに対して外部からの観測や不当な改変が困難な性質
（耐タンパ性）を持たせる方法が提案されている。難読
化とは、例えば、門田、高田、鳥居、らによる論文「ル
ープを含むプログラムを難読化する方法の提案」電子情
報通信学会論文誌Ｖｏｌ．Ｊ８０−Ｄ−ＩＮｏ．７、に
述べられているように、プログラムの仕様を保ちながら
その解析を困難にするように前記プログラムを変換する
方法のことである。特に、難読化に関しては、Ｗａｎ
ｇ、Ｈｉｌｌ、Ｋｎｉｇｈｔ、Ｄａｖｉｄｓｏｎ、ら
が、その研究「Ｓｏｆｔｗａｒｅ ｔａｍｐｅｒ ｒｅ
ｓｉｓｔａｎｃｅ： Ｏｂｓｔｒｕｃｔｉｎｇ ｓｔａ
ｔｉｃ ａｎａｌｙｓｉｓ ｏｆ ｐｒｏｇｒａｍｓ」
Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ ＣＳ−２０００−
１２、Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｖｉｒｇｉｎｉ
ａ、において、プログラムにおけるポインタ変数の解析
が困難なことに着目し、難読化されたプログラムの解析
の困難さを定量的に示すことができる難読化方法を提案
している。このＷａｎｇらの提案方法は、関数内のみを
難読化の対象とし、難読化されたプログラムに対する関
数内解析の困難さのみ示されている。

【０００６】

【発明が解決しようとする課題】しかしながら、超流通
による解決方法では、コストが大きくなるという問題点
が存在する。また、難読化による方法は、門田らの方法
を始めとして従来の多くの方法においては、難読化され
たプログラムの解析の困難さが定量的に示されておら
ず、その効果が明らかではないという問題点がある。一
方で、Ｗａｎｇらが提案した難読化方法は、難読化され
たプログラムに対する関数内解析の困難さは示されてい
るものの、関数間の呼び出し関係を対象としておらず、
難読化されたプログラムに対する関数間解析の困難さは
示されていないという問題点が存在する。すなわち、Ｗ
ａｎｇらの方法は局所的な難読化方法であり、プログラ
ムを全体として見た場合、Ｗａｎｇらの方法の有効性は
明らかではないと考えられる。

【０００７】本発明は、前記課題の少なくとも一つを解
決するためになされたもので、機密データや機密アルゴ
リズム等をもつプログラムへの不正アクセスを防ぐため
に、前記プログラムに対して、安価な構成で、関数間解
析を困難にするように難読化する方法であって、構成に
よっては難読化された前記プログラムの解析の困難さが
証明されているような方法及び装置を提供することにあ
る。

【０００８】

【課題を解決するための手段】本発明に関わる難読化方
法は、関数の記述が可能なプログラミング言語によって
記述されたプログラムのソースコードに対して、前記プ
ログラムの仕様を変更しないように変換する方法であっ
て、関数へのポインタ変数を新たに複数個導入し、前記
関数ポインタ変数のいずれかに関数のアドレスを代入す
る命令文を複数個挿入し、前記プログラムにおける関数
の呼出しを、前記関数を直接呼出すのではなく、前記関
数ポインタ変数の値に応じて関数を呼出すように変換す
ることを特徴とする。

【０００９】本発明に関わる難読化方法は、与えられた
プログラムのソースコードに対して、関数へのポインタ
変数と、関数へのポインタの配列変数と、を新たに複数
個導入し、前記複数個の関数ポインタ変数のいずれかあ
るいは前記複数個の関数ポインタ配列の要素のいずれか
に、前記複数個の関数ポインタ変数のいずれかあるいは
前記複数個の関数ポインタ配列の要素のいずれかあるい
は関数のアドレスを代入し、前記関数ポインタ変数ある
いは前記関数ポインタ配列の要素により関数を呼び出す
ように変換することを特徴とする。

【００１０】本発明に関わる難読化方法は、与えられた
プログラムのソースコードに対して、複数個の関数への
ポインタ変数と、ダミー関数Ｆと、を新たに導入し、前
記関数Ｆの内部において、前記プログラムにおける複数
個の関数呼び出しを前記関数ポインタ変数を介して実行
できるようにし、前記プログラムにおける前記関数呼び
出しのそれぞれを関数Ｆを呼出すように変換することを
特徴とする。

【００１１】本発明に関わる難読化方法は、与えられた
プログラムのソースコードに対して、ある値を返す関数
へのポインタ変数と、ある値を返す関数へのポインタの
配列変数と、を新たに複数個導入し、前記複数個の関数
ポインタ変数のいずれかあるいは前記複数個の関数ポイ
ンタ配列の要素のいずれかに、前記複数個の関数ポイン
タ変数のいずれかあるいは前記複数個の関数ポインタ配
列の要素のいずれかあるいは関数のアドレスを代入し、
前記関数ポインタ変数あるいは前記関数ポインタ配列の
要素により関数を呼び出すように変換する方法であっ
て、その解析の困難さが証明されていることを特徴とす
る。

【００１２】本発明に関わる難読化装置は、関数の記述
が可能なプログラミング言語によって記述されたプログ
ラムのソースコードを入力する入力手段と、難読化に関
する処理全体の制御を行う制御手段と、前記プログラム
のソースコードを解析して難読化の対象となる領域を決
定する手段と、難読化に利用される関数ポインタ変数や
関数ポインタの配列変数やダミー関数等を導入して前記
関数ポインタ変数や前記関数ポインタの配列変数や前記
ダミー関数等を利用して関数を呼出すように変換する難
読化手段と、前記プログラムを難読化して得られたプロ
グラムのソースコードあるいは実行形式プログラムを出
力する手段と、を備えることを特徴とする。

【００１３】本発明に関わる難読化処理用記録媒体は、
プログラムのソースコードを難読化するプログラムを記
録した記録媒体であって、前記プログラムのソースコー
ドを解析して難読化の対象となる領域を決定する第１の
処理と、難読化に利用される関数ポインタ変数や関数ポ
インタの配列変数やダミー関数等を導入して前記関数ポ
インタ変数や前記関数ポインタの配列変数や前記ダミー
関数等を利用して関数を呼出すように変換する第２の処
理と、前記プログラムを難読化して得られたプログラム
のソースコードあるいは実行形式プログラムを出力する
第３の処理と、を含むコンピュータが実行可能な難読化
プログラムが記録されていることを特徴とする。

【００１４】

【発明の実施の形態】以下、図面を参照しながら本発明
の全体構成及び、以下の４つの実施形態 （１）関数ポインタによる難読化実施形態、（２）関数
ポインタ及び関数ポインタの配列による難読化実施形
態、（３）関数ポインタ及び関数呼び出しをまとめたダ
ミー関数による難読化実施形態、（４）値を返す関数へ
のポインタ及び値を返す関数へのポインタの配列による
難読化実施形態で、その解析の困難さが証明されている
もの、の概略を説明し、その後、それぞれの詳細を説明
する。

【００１５】図１に、本発明を適用した難読化装置の全
体構成を難読化装置１１０として示す。

【００１６】難読化装置１１０は、入力部１１１と、中
央処理部１１２と、出力部１１３と、難読化領域決定部
１１４と、難読化処理部１１５と、から構成されてい
る。

【００１７】入力部１１１は、難読化したいプログラム
のソースコードを入力するためのものである。中央処理
部１１２は、難読化する対象を決定する処理や、変数や
ダミー関数の導入処理や、難読化処理などを制御する。
出力部１１３は、難読化されたソースコードや実行形式
プログラムを出力するためのものである。難読化領域決
定部１１４は、ソースコードを解析した後、ソースコー
ドにおける難読化する部分を決定する。難読化処理部１
１５は、難読化に利用される関数ポインタ変数や関数ポ
インタの配列変数やダミー関数等を新たに導入し、それ
らを利用してプログラムのソースコードを難読化する。

【００１８】上述した難読化装置１１０は、以下の２つ
の処理を特徴として持つ。

【００１９】（１）難読化領域決定処理 （２）難読化処理 難読化対象決定処理は、中央処理部１１２から与えられ
たプログラムのソースコードを解析し、難読化する対象
部分を決定する。難読化処理は、難読化の処理に用いら
れる関数ポインタ変数や関数ポインタの配列変数やダミ
ー関数等を導入し、それらを利用してプログラムのソー
スコードを難読化する。以下、これら２つの処理につい
て詳しく説明する。

【００２０】最初に、図２の難読化領域決定フロー図を
用いて、難読化領域決定部１１４が行う処理について説
明する。まずはじめに、難読化したいプログラムのソー
スコードを、入力部１１１から入力する（ステップ２
１）。中央処理部１１２は、このソースコードを難読化
領域決定部１１４に送る。難読化領域決定部１１４は、
送られてきたソースコードを解析する（ステップ２
２）。このとき、一般的には、難読化領域決定部１１４
は、フローグラフ等を作成し、それを用いて、関数呼び
出しを含めた実行順序の解析、関数内や関数間の変数の
利用状況やデータの流れ、等の解析を行う。難読化領域
決定部１１４は、ステップ２２の処理によって得られた
情報を利用して、難読化する対象部分を決定する（ステ
ップ２３）。難読化領域決定部１１４は、難読化領域を
決定すると、プログラムの解析情報を含む難読化領域情
報を中央処理部１１２へ送る。中央処理部１１２は、送
られてきたプログラム解析情報を含む難読化領域情報を
難読化処理部１１５に送り（ステップ２４）、難読化領
域決定処理は終了する。

【００２１】次に、難読化処理について、図３の難読化
処理フロー図を用いて説明する。難読化処理部１１５
は、中央処理部１１２から送られてきた、プログラム解
析情報を含む難読化領域情報を入力する（ステップ３
１）。この情報を参照しながら、難読化処理部１１５
が、与えられたプログラムのソースコードを難読化す
る。このとき、難読化処理部１１５は、プログラムの仕
様を変更しないように、複数個の関数ポインタ変数や関
数ポインタの配列変数やダミー関数等を新たに導入する
（ステップ３２）。その処理後、難読化処理部１１５
は、前記関数ポインタ変数や前記関数ポインタの配列変
数や前記ダミー関数等を利用して複数の関数の中から関
数を選んで呼び出すような命令文の列を作成する（ステ
ップ３３）。難読化処理部１１５は、難読化領域決定部
１１４によって決定された難読化領域の一部の関数呼び
出しに関する命令文を取り除き、プログラムの仕様が変
更されないように、ステップ３３によって作成された命
令文の列を挿入する（ステップ３４）。ここで挿入され
る命令文の列は、プログラムの仕様が変更されなけれ
ば、必ずしも連続して挿入しなくてもよい。その後、ス
テップ３５において、さらに難読化処理が必要であれ
ば、ステップ３２からの処理を繰り返す。もし必要なけ
れば、難読化処理を終了する。

【００２２】以上の全体構成のもとで、本発明は、与え
られたプログラムのソースコードを難読化する。ここ
で、難読化装置１１０においては、入力部１１１と、中
央処理部１１２と、出力部１１３と、は実施形態によら
ず共通であるが、難読化領域決定部１１４と、難読化処
理部１１５と、は実施形態により内容が異なることがあ
る。上述したように、これらの実施形態は、関数ポイン
タによる難読化実施形態、関数ポインタ及び関数ポイン
タの配列による難読化実施形態、関数ポインタ及び関数
呼び出しをまとめたダミー関数による難読化実施形態、
値を返す関数へのポインタ及び値を返す関数へのポイン
タの配列による難読化実施形態でその解析の困難さが証
明されているもの、である。以下で、これらのそれぞれ
について詳しく説明する。

【００２３】まず始めに、説明を分かりやすくするため
に、関数ポインタによる難読化実施形態、関数ポインタ
及び関数ポインタの配列による難読化実施形態、関数ポ
インタ及び関数呼び出しをまとめたダミー関数による難
読化実施形態、の３つの実施形態における、元となるプ
ログラムのソースコードを共通のものであるものと仮定
し、その一実施例を図４に示す。図４は、ステップ２３
における、難読化領域決定処理の説明図である。

【００２４】本発明は、関数を直接呼び出すのではな
く、関数ポインタ変数等の値に応じて複数個の関数から
一つの関数を呼び出すように変換する難読化方法を特徴
としているため、関数を直接呼び出す命令文あるいは関
数を（変数の値に依存するなどして）間接的に呼び出す
命令文等が難読化の対象となる。図４においては、難読
化領域として、関数呼び出しである命令文４１と命令文
４２とが選ばれている。

【００２５】ここから、各実施形態の詳細の説明を始め
る。始めに、関数ポインタによる難読化実施形態を、図
５に従い、順を追って説明する。

【００２６】図５は、関数ポインタによる難読化実施形
態の図面である。図５においては、図４に示されたプロ
グラムのソースコードが、関数ポインタを利用すること
によって難読化されている。図５においては、図４と同
一の部分については同一符号を付している。前述したよ
うに、難読化領域決定部１１４によって、命令文４１お
よび４２が難読化領域として決定されており、プログラ
ム解析情報を含む難読化領域の情報が、中央処理部１１
２から難読化処理部１１５に送られてきている。

【００２７】ステップ３２では、与えられたプログラム
の仕様を変更しないように、命令文（変数宣言文）５１
によって整数変数ｉが導入されており、かつ、命令文５
２において関数へのポインタ変数ｆが導入されている。
このとき、呼び出す関数を決定する際に用いられる変数
の数が多いほど、呼び出される関数を決定することを困
難にできるため、ステップ３２において導入される、関
数へのポインタ変数等の数は多いことが望ましい。

【００２８】ステップ３３においては、難読化処理部１
１５は、プログラムの仕様を変更しないように、変数の
値に依存して異なる関数を呼び出すような命令文の列を
作成する。この実施例の一つは、命令文５３および命令
文５６である。命令文５３は、式「ｉ＊（ｉ＋１）％２
＝＝０」を条件式として持ち、この条件式が成立する場
合には、関数ポインタｆに関数のアドレスｆｕｎｃ１を
代入し（命令文５４）、その条件式が成立しない場合に
は、関数ポインタｆに関数のアドレスｆｕｎｃ２を代入
する（命令文５５）ようなｉｆ文である。また、命令文
５６は、関数ポインタｆに格納されているアドレスを持
つ関数を呼び出して実行する命令文である。

【００２９】次に、ステップ３４において、難読化領域
として決定された部分のうち任意に命令文４１を選び、
前記命令文の列（命令文５３および５６）を置き換え
る。命令文５３および命令文５６は、プログラムの仕様
を変更しないのであれば、連続して挿入する必要はな
い。

【００３０】ここで、命令文５３のｉｆ文の条件式の左
辺の計算式「ｉ＊（ｉ＋１）％２」はｉの如何なる（整
数）値においても恒等的に０となるので、常に命令文５
４が実行されることになり、プログラムの仕様は変更さ
れないことがいえる。さらに、通常ｉｆ文における条件
式を計算することは困難であるため、その分岐先を決定
することは困難である。より一般的に言えば、条件分岐
があるときプログラムにおける命令文の実行順序を決定
する問題は決定不能であることが知られている。この点
は、例えば、Ｌａｎｄｉによる「Ｕｎｄｅｃｉｄａｂｉ
ｌｉｔｙ ｏｆＳｔａｔｉｃ Ａｎａｌｙｓｉｓ」、
ＡＣＭ Ｌｅｔｔｅｒｓ ｏｎ Ｐｒｏｇｒａｍｍｉｎ
ｇ Ｌａｎｇｕａｇｅｓ ａｎｄ Ｓｙｓｔｅｍｓ、Ｖ
ｏｌ．１、Ｎｏ．４、１９９２、などの論文で言及され
ている。

【００３１】上述の理由により、通常は命令文５３を実
行後にｆの値を決定することは困難となり、その結果命
令文５６においてｆによってどの関数が呼び出されるか
を決定することが困難となる。したがって、本発明の実
施により、関数間の解析を困難にする難読化がなされて
いるといえる。

【００３２】次に、関数ポインタ及び関数ポインタの配
列による難読化実施形態を、図６に従い、順を追って説
明する。

【００３３】図６は、関数ポインタ及び関数ポインタの
配列による難読化実施形態の図面である。図６において
は、図６に示されたプログラムのソースコードを、関数
ポインタ及び関数ポインタの配列を利用することによっ
て難読化している。図６においては、図４と同一の部分
については同一符号を付して、左端に配置している。前
述したように、難読化領域決定部１１４によって、命令
文４１および４２が難読化領域として決定されており、
プログラム解析情報を含む難読化領域の情報が、中央処
理部１１２から難読化処理部１１５に送られてきてい
る。

【００３４】図６における難読化実施例においては、難
読化処理部１１５は、難読化領域決定部１１４によって
選ばれた命令文のうち、命令文４１をまず関数ポインタ
を用いて難読化し、さらに、関数ポインタの配列を用い
て難読化している。図６における実施例では、上述の処
理のうち、関数ポインタを用いて難読化する処理は関数
ポインタによる難読化実施例と同一であり、図６の中央
に配置されている図によって示されている。図６の中央
の図は、図５と同一の部分については同一符号を付して
いる。この段階で、難読化処理はステップ３５が実行さ
れる。

【００３５】次に、ステップ３５からステップ３２に処
理が移り、関数ポインタの配列を利用して、命令文４１
に相当する部分の難読化が行われる。このために、まず
始めにステップ３２により、命令文６１において新たに
整数変数ｊが導入され、さらに、命令文６２において関
数ポインタの配列Ａを導入している。その後、関数ポイ
ンタｆへの代入を関数ポインタ配列Ａを介して行うよう
に変換する。このため、ステップ３３により、命令文５
３のｉｆ文に対応するｉｆ文であって、命令文５４にお
ける関数ポインタｆへの代入を、命令文６４においてま
ず関数ポインタの配列の一要素Ａ［３３］に代入するも
のとし、また、命令文５５における関数ポインタｆへの
代入を、命令文６５においてまず関数ポインタの配列の
一要素Ａ［７１］に代入するものとするような、命令文
６３のｉｆ文を作成している。さらに、二つ目のｉｆ文
として、その条件式が「（ｊ−１）＊ｊ％２＝＝０」で
あるような命令文６６を作成し、その命令文６７におい
て、関数ポインタの配列の一要素Ａ［３３］を関数ポイ
ンタｆに代入するものとし、命令文６８において、関数
ポインタの配列の一要素Ａ［７１］を関数ポインタｆに
代入するものとするようなｉｆ文を作成している。次
に、ステップ３４において、上述のように作成した文お
よび、関数ポインタｆに格納されているアドレスを持つ
関数を呼び出して実行する命令文６９とを、命令文４１
に相当する部分に置き換えている。これらの置き換えの
際に挿入される命令文は、プログラムの仕様を変えない
ものであれば、連続して挿入する必要はない。

【００３６】関数ポインタの配列の要素Ａ［３３］およ
びＡ［７１］における添字３３および７１については、
プログラムの仕様を変えないものであれば、任意に選ん
でよい。その際、難読化の効果を高めるため、複雑な計
算式などを利用して計算することも考えられる。

【００３７】このとき、命令文６６のｉｆ文の条件式の
左辺「（ｊ−１）＊ｊ％２」はｊの如何なる（整数）値
においても恒等的に０となるので、常に命令文６７が実
行されることになり、プログラムの仕様は変更されな
い。さらに、Ａｈｏ、Ｓｅｔｈｉ、Ｕｌｌｍａｎ、らに
よる「Ｃｏｍｐｉｌｅｒｓ： Ｐｒｉｎｃｉｐｌｅｓ、
Ｔｅｃｈｎｉｑｕｅｓ ａｎｄ Ｔｏｏｌｓ」、Ａｄｄ
ｉｓｏｎ−Ｗｅｓｌｅｙ、１９８６、などの文献に示さ
れているように、一般的に言って配列の要素の計算は困
難であることが知られており、また上述したようにｉｆ
文における実行の流れを計算することが困難であること
がいえるため、通常は命令文６３および６６の二つのｉ
ｆ文の実行後にｆの値を決定することは困難となり、そ
の結果命令文６９においてｆによってどの関数が呼び出
されるかを決定することがより困難となり、関数間の解
析を困難にする難読化がなされているといえる。

【００３８】なお、今まで述べてきた関数ポインタ及び
関数ポインタの配列による難読化実施形態においては、
関数ポインタによる難読化を実施した後に関数ポインタ
の配列による難読化を行うといった順で行う必要はな
く、逆に関数ポインタの配列に関数のアドレスを代入し
て行う難読化を実施した後、関数のアドレスを関数ポイ
ンタによって難読化するといった順で行ってもよい。も
ちろん、前記の二つの難読化を同時に実施してもよい。

【００３９】次に、関数ポインタ及び関数呼び出しをま
とめたダミー関数による難読化実施形態を、図７に従
い、順を追って説明する。

【００４０】図７は、関数ポインタ及び関数呼び出しを
まとめたダミー関数による難読化実施形態の図面であ
る。図７においては、図４に示されたプログラムのソー
スコードを、関数ポインタ及び関数呼び出しをまとめた
ダミー関数を利用することで難読化している。図７にお
いては、図４と同一の部分については同一符号を付し
て、左端に配置している。前述したように、難読化領域
決定部１１４によって、命令文４１および４２が難読化
領域として決定されており、プログラム解析情報を含む
難読化領域の情報が、中央処理部１１２から難読化処理
部１１５に送られてきている。

【００４１】図７における難読化実施例においては、難
読化処理部１１５は、難読化領域決定部１１４によって
選ばれた命令文４１および４２を関数ポインタを用いて
難読化し、さらに、関数呼び出しをまとめたダミー関数
を利用することで難読化している。このために、まずス
テップ３２により、命令文７０１において新たに整数変
数ｉを導入し、命令文７０２において関数へのポインタ
ｆを導入している。その後、関数呼び出しをまとめたダ
ミー関数を利用して難読化するために、ステップ３３に
より、命令文７０３（関数宣言文）においてダミー関数
Ｆを導入している。関数Ｆの内部において、難読化領域
決定部１１４によって選択された命令文４１および４２
の関数呼び出しをまとめて呼び出すことができるように
するために、命令文７０４のｉｆ文において、変数ｉの
値に応じて、ｉが０のときは命令文７０５において関数
のアドレスｆｕｎｃ１をｆに代入し、ｉが１のときは命
令文７０６において関数のアドレスｆｕｎｃ２をｆに代
入するものを作成する。命令文７０７は、関数ポインタ
ｆに格納されているアドレスをもつ関数を呼び出すため
のものである。

【００４２】さらに、変数ｉの値を適切なものにするた
めに、命令文７０８を作成し、その命令文７０８の以降
の部分に関数Ｆの呼び出しである命令文７０９を作成す
る。同様に、命令文７１０を作成し、その命令文７１０
の以降の部分に関数Ｆの呼び出しである命令文７１１を
作成する。命令文７０８の右辺の式「ｉ＊（ｉ＋１）％
２」においては、ｉが如何なる（整数）値を持とうと恒
等的に０となるため、命令文７０８の実行後にはｉの値
は０となる。同様に、命令文７１０の右辺の式「（ｉ−
１）＊ｉ％２＋１」においては、ｉが如何なる（整数）
値を持とうと恒等的に１となるため、命令文７１０の実
行後にはｉの値は１となる。以上より、元のプログラム
の仕様に変更がないことがいえる。

【００４３】ステップ３４において、前記作成された関
数Ｆおよび命令文７０８から７１１を、難読化領域決定
部１１４によって選択された命令文４１および４２に対
応して置き換える。これらの置き換えの際に挿入される
命令文は、プログラムの仕様を変えないものであれば、
連続して挿入する必要はない。

【００４４】ここで、図７における難読化実施例の内容
について説明する。プログラムを実行する際には、関数
呼び出しから復帰したときは、プログラムの実行は呼び
出した命令文の次の命令文に移らなければならない。た
とえば、図７の命令文７０９において関数Ｆが呼び出さ
れ、その内部の命令文７０７において関数ポインタｆが
ｆｕｎｃ１のアドレスを持っておりｆｕｎｃ１が呼び出
されたとすると、プログラムの実行がｆｕｎｃ１から復
帰し、次に関数Ｆから復帰した直後に実行される命令文
は、命令文７０９の次の実行文でなければならない。同
様に、命令文７１１において関数Ｆが呼び出され、その
内部の命令文７０７において関数ポインタｆがｆｕｎｃ
１のアドレスを持っておりｆｕｎｃ１が呼び出されたと
すると、プログラムの実行がｆｕｎｃ１から復帰し、次
に関数Ｆから復帰した直後に実行される命令文は、命令
文７１１の次の実行文でなければならない。これを関数
ｆｕｎｃ１に注目して考えてみると、関数ｆｕｎｃ１の
復帰後の実行は、ｆｕｎｃ１の呼び出し位置によって復
帰されるべき点が変わってくるということになる。一般
的に言って、ｉｆ文における分岐先を決める問題が難し
いのと同様の理由で、上述のような正しい呼び出し復帰
の実行順序を決定することは、困難であることがいえる
ため、図７による難読化実施例によって、関数間解析の
困難さが増したことがいえる。

【００４５】次に、値を返す関数へのポインタ及び値を
返す関数へのポインタの配列による難読化実施形態でそ
の解析の困難さが証明されているもの、を、図８に従っ
て説明する。

【００４６】しかしながら、図８は、関数が値を返すも
のであるという点以外は、ほぼ図６と同様であるので、
説明は必要最小限にとどめる。

【００４７】図８の実施形態において、難読化の対象と
なるプログラムのソースコードは、図８の左端の図面に
与えられている。図６のプログラムとの違いは、図８で
は関数ｆｕｎｃ１（命令文８２１によって宣言される）
および関数ｆｕｎｃ２（命令文８２２によって宣言され
る）は、いずれも整数値を返す関数であり、命令文８２
３において変数ｍにｆｕｎｃ１の返り値が代入され、命
令文８２４においてｆｕｎｃ２の返り値が変数ｎに代入
されているという点である。

【００４８】図８の実施形態においては、難読化領域決
定部１１４は命令文８２３および８２４を対象部分とし
て選択している。

【００４９】図８の実施形態においては、難読処理部１
１５は関数ポインタを導入して難読化している。この処
理の実施形態は、図８の中心の図面に示されている。こ
の実施形態と、図６の実施形態との違いは、図８では命
令文８３２によって、（整数）値を返す関数へのポイン
タｆが導入されているという点と、命令文８３６におい
て、ｆを介して呼ばれる関数の返り値がｍに代入されて
いるという点である。

【００５０】上記処理の後、図８の実施形態において
は、難読処理部１１５は（整数）値を返す関数へのポイ
ンタの配列を導入し、それを介して関数呼び出しを行う
ように難読化している。図６の実施例との違いは、図８
では命令文８４２によって、（整数）値を返す関数への
ポインタの配列Ａが導入されているという点と、命令文
８４９において、ｆを介して呼ばれる関数の返り値がｍ
に代入されているという点である。

【００５１】図８の実施形態の特徴は、図６に述べたも
のと同様であるが、図８の特徴は、その解析の困難さが
証明できるということにある。より具体的には、値を返
す関数へのポインタに対して、関数ポインタの配列を利
用した代入があり、値を返す関数へのポインタによる関
数への呼び出しがあるようなプログラムにおいて、関数
ポインタの指し示すアドレスを決定する問題はＮＰ困難
であることことが示される。以下にこの証明を示す。

【００５２】証明任意の３−ＳＡＴ問題が与えられたと
き、前記の問題はその３−ＳＡＴ問題から多項式時間で
帰着可能であることを以下に示す。３−ＳＡＴ問題はＮ
Ｐ完全であることが知られているため、これにより証明
されたことになる。以下に具体的に証明を述べる。この
証明では、すべての実行経路を実行可能であるとみなし
て解析が行われると仮定している。これは、解析に関し
て通常行われる仮定で、「ｍｅｅｔ ｏｖｅｒ ａｌｌ
ｐａｔｈｓ」仮定としばしば呼ばれる。命題変数ｖ_ｉ
（ｉ＝１，２，．．．，ｍ）について、ｎ個の節の論
理積の充足可能性を調べる３−ＳＡＴ問題が与えられた
と仮定する。ここで、節とは、３つのリテラルｌ_ｉ１，
ｌ_ｉ２，ｌ_ｉ３ （ｉ＝１，．．．，ｎ）の論理和であ
る。リテラルとは、あるｋ （１≦ｋ≦ｍ）について、
ｖ_ｋもしくはその論理否定¬ｖ_ｋである。このような３
−ＳＡＴ問題が与えられたとき、図９に示すような、関
数ポインタを含むプログラムを構成する。このプログラ
ムのサイズは、明らかに命題変数と論理式の多項式オー
ダで押さえられる。また、ｉｆ文のすべての実行経路は
実行可能であると仮定するので、条件式を省略し「−」
と記述している。このプログラムにおいて、Ｌ１では、
関数ポインタｃおよび元の３−ＳＡＴ問題の命題変数ｖ
_ｉに対応する関数ポインタｖ_ｉ （ｉ＝１，
２，．．．，ｍ）が宣言されている。同様に、命題変数
ｖ_ｉの論理否定に対応する、関数ポインタｎｅｇ＿ｖ_ｉ
が宣言される。さらに、ｌ_ｉｊ （ｉ＝１，
２，．．．，ｎ，ｊ＝１，２，３）は、ｉ番目の節のｊ
番目のリテラルに対応するもので、あるｋ （１≦ｋ≦
ｍ）について、ｖ_ｋもしくはｎｅｇ＿ｖ_ｋである。そし
て、Ｌ２では関数ｆａｌｓｅ（）および関数ｔｒｕ
ｅ（）のアドレスを、それぞれ関数ポインタの配列Ａ
［０］およびＡ［１］に代入している。プログラム中の
Ｌ３における任意の実行経路は、３−ＳＡＴ問題におけ
る真理値の割り当てに相当する。すなわち、もし３−Ｓ
ＡＴ問題に解が存在するならば、すべての節について少
なくとも一つはｔｒｕｅとなるリテラルが存在し、プロ
グラムにおける対応する関数ポインタｌ_ｉｊ は関数ｔ
ｒｕｅ（）のアドレスを指し示す。したがって、対応す
る実行経路をたどると、Ｌ５において、関数ポインタｃ
は関数ｔｒｕｅ（）を指し示すことが分かる。また、３
−ＳＡＴ問題に解が存在しないときは、３つのリテラル
すべてがｆａｌｓｅとなる節が少なくとも１つ存在す
る。そのとき、プログラムのＬ５において、関数ポイン
タｃは関数ｆａｌｓｅ（）を指し示し、ｔｒｕｅ（）を
指し示すような実行経路は存在しない。逆に、プログラ
ムのＬ５において関数ポインタｃが関数ｔｒｕｅ（）を
指し示しでいるとき、与えられた３−ＳＡＴ問題は実行
経路に対応する真理値の割り当てを持つ。すなわち、３
−ＳＡＴ問題は解を持つ。（証明終わり）

【００５３】上述したように、値を返す関数へのポイン
タ及び値を返す関数へのポインタの配列による難読化実
施形態では、その解析の困難さが証明されることが分か
る。より具体的には、関数ポインタの指し示すアドレス
を決定することが困難であることが証明された。これに
より、関数間解析などで関数ポインタを指し示すアドレ
スを決定しようとしたとき、正確に決定することは困難
になり、プログラムを難読化できることが分かる。

【００５４】このように本実施形態によれば、元のプロ
グラムの仕様を変更することなしに、安価な構成で、呼
び出される関数の特定を困難することができ、結果とし
てプログラムの仕様やアルゴリズムの解析を困難にする
ことができる。また、構成によっては、解析の困難さを
証明することができることが本発明の大きな特徴であ
る。以上により、プログラムが機密データや機密アルゴ
リズムを持つとき、前記プログラムに対する不正アクセ
スを、安価な構成で防ぐことができるようになる。

【００５５】

【発明の効果】以上述べたように本発明によれば、プロ
グラムが機密データや機密アルゴリズムを持つとき、前
記プログラムを、安価な構成で、関数間解析を困難にす
るように難読化する方法であって、構成によっては難読
化された前記プログラムの解析の困難さが証明されてい
るような難読化方法及び装置によって前記プログラムを
難読化し、前記プログラムへの不正アクセスを防ぐこと
ができるようになる。

【図面の簡単な説明】

【図１】本発明の実施形態を示す装置構成図である。

【図２】難読化領域決定処理のフローチャートである。

【図３】難読化処理のフローチャートである。

【図４】難読化領域決定処理の説明図である。

【図５】関数ポインタによる難読化実施形態の説明図で
ある。

【図６】関数ポインタ及び関数ポインタの配列による難
読化実施形態の説明図である。

【図７】関数ポインタ及び関数呼び出しをまとめたダミ
ー関数による難読化実施形態の説明図である。

【図８】値を返す関数へのポインタ及び値を返す関数へ
のポインタの配列による難読化実施形態で、その解析の
困難さが証明されているものの説明図である。

【図９】関数ポインタのアドレスを決定する問題の証明
図である。

【符号の説明】

１１０ 難読化装置、１１１ 入力部、１１２ 中央処
理部、１１３ 出力部、１１４ 難読化領域決定部、１
１５ 難読化処理部。

Claims (6)

【特許請求の範囲】
1. 【請求項１】 関数の記述が可能なプログラミング言語
   によって記述されたプログラムのソースコードに対し
   て、前記プログラムの仕様を変更しないように変換する
   方法であって、関数へのポインタ変数を新たに複数個導
   入し、前記関数ポインタ変数のいずれかに関数のアドレ
   スを代入する命令文を複数個挿入し、前記プログラムに
   おける関数の呼出しを、前記関数を直接呼出すのではな
   く、前記関数ポインタ変数の値に応じて関数を呼出すよ
   うに変換することを特徴とする難読化方法。
2. 【請求項２】 与えられたプログラムのソースコードに
   対して、関数へのポインタ変数と、関数へのポインタの
   配列変数と、を新たに複数個導入し、前記複数個の関数
   ポインタ変数のいずれかあるいは前記複数個の関数ポイ
   ンタ配列の要素のいずれかに、前記複数個の関数ポイン
   タ変数のいずれかあるいは前記複数個の関数ポインタ配
   列のいずれかあるいは関数のアドレスを代入し、前記関
   数ポインタ変数あるいは前記関数ポインタ配列の要素に
   より関数を呼び出すように変換することを特徴とする請
   求項１記載の難読化方法。
3. 【請求項３】 与えられたプログラムのソースコードに
   対して、複数個の関数へのポインタ変数と、ダミー関数
   Ｆと、を新たに導入し、前記関数Ｆの内部において、前
   記プログラムにおける複数個の関数呼び出しを前記関数
   ポインタ変数を介して実行できるようにし、前記プログ
   ラムにおける前記関数呼び出しのそれぞれを関数Ｆを呼
   出すように変換することを特徴とする請求項１記載の難
   読化方法。
4. 【請求項４】 与えられたプログラムのソースコードに
   対して、ある値を返す関数へのポインタ変数と、ある値
   を返す関数へのポインタの配列変数と、を新たに複数個
   導入し、前記複数個の関数ポインタ変数のいずれかある
   いは前記複数個の関数ポインタ配列の要素のいずれか
   に、前記複数個の関数ポインタ変数のいずれかあるいは
   前記複数個の関数ポインタ配列の要素のいずれかあるい
   は関数のアドレスを代入し、前記関数ポインタ変数ある
   いは前記関数ポインタ配列の要素により関数を呼び出す
   ように変換する方法であって、その解析の困難さが証明
   されていることを特徴とする請求項１あるいは２のいず
   れかに記載の難読化方法。
5. 【請求項５】 関数の記述が可能なプログラミング言語
   によって記述されたプログラムのソースコードを入力す
   る入力手段と、難読化に関する処理全体の制御を行う制
   御手段と、前記プログラムのソースコードを解析して難
   読化の対象となる領域を決定する手段と、難読化に利用
   される関数ポインタ変数や関数ポインタの配列変数やダ
   ミー関数等を導入して前記関数ポインタ変数や前記関数
   ポインタの配列変数や前記ダミー関数等を利用して関数
   を呼出すように変換する難読化手段と、前記プログラム
   を難読化して得られたプログラムのソースコードあるい
   は実行形式プログラムを出力する手段と、を備えること
   を特徴とする難読化装置。
6. 【請求項６】 プログラムのソースコードを難読化する
   プログラムを記録した記録媒体であって、前記プログラ
   ムのソースコードを解析して難読化の対象となる領域を
   決定する第１の処理と、難読化に利用される関数ポイン
   タ変数や関数ポインタの配列変数やダミー関数等を導入
   して前記関数ポインタ変数や前記関数ポインタの配列変
   数や前記ダミー関数等を利用して関数を呼出すように変
   換する第２の処理と、前記プログラムを難読化して得ら
   れたプログラムのソースコードあるいは実行形式プログ
   ラムを出力する第３の処理と、を含むコンピュータが実
   行可能な難読化プログラムが記録されていることを特徴
   とする難読化処理用記録媒体。