(57)【特許請求の範囲】
【請求項１】
プログラムに含まれる変数の参照関係を用い、演算装置によってプログラムの評価を行うプログラム評価方法であって、
前記変数をグラフの節点に割付け、ある節点に割り付けられた変数を参照して計算される値が他の節点に割り付けられる変数に代入されたときに、前記ある節点から他の節点に向かう枝を加えた変数の依存関係グラフを生成するステップと、
初期値が代入されている変数に対応する前記節点にある初期評価値を設定し、初期値が代入されていない変数に対応する前記節点に他の初期評価値を設定するステップと、
前記ある初期評価値が設定され、かつ、評価値の加算が終了したことを示すフラグが設定されていない前記節点のそれぞれについて、互いに隣接する節点の評価値を加算して自身の評価値を更新して、評価値の加算が終了したことを示すフラグを設定するステップと、
すべての節点の更新された評価値の総和を算出して前記プログラムの評価値を生成出力するステップと、
を有することを特徴とするプログラム評価方法。
【請求項２】
プログラムに含まれる変数をグラフの節点に割付け、ある節点に割り付けられた変数を参照して計算される値が他の節点に割り付けられる変数に代入されたときに、前記ある節点から他の節点に向かう枝を加えた変数の依存関係グラフを生成する依存関係グラフ生成手段と、
初期値が代入されている変数に対応する前記節点にある初期評価値を設定し、初期値が代入されていない変数に対応する前記節点に他の初期評価値を設定する初期評価値設定手段と、
前記ある初期評価値が設定され、かつ、評価値の加算が終了したことを示すフラグが設定されていない前記節点のそれぞれについて、互いに隣接する節点の評価値を加算して自身の評価値を更新して、評価値の加算が終了したことを示すフラグを設定する評価値更新手段と、
すべての節点の更新された評価値の総和を算出して前記プログラムの評価値を生成出力する評価値生成出力手段と、
を備えたことを特徴とするプログラム評価装置。
【請求項３】
プログラムに含まれる変数の参照関係を用い演算装置によってプログラムの評価を行うプログラム評価装置に用いられる評価プログラムであって、
前記変数をグラフの節点に割付け、ある節点に割り付けられた変数を参照して計算される値が他の節点に割り付けられる変数に代入されたときに、前記ある節点から他の節点に向かう枝を加えた変数の依存関係グラフを生成する処理と、
初期値が代入されている変数に対応する前記節点にある初期評価値を設定し、初期値が代入されていない変数に対応する前記節点に他の初期評価値を設定する処理と、
前記ある初期評価値が設定され、かつ、評価値の加算が終了したことを示すフラグが設定されていない前記節点のそれぞれについて、互いに隣接する節点の評価値を加算して自身の評価値を更新して、評価値の加算が終了したことを示すフラグを設定する処理と、
すべての節点の更新された評価値の総和を算出して前記プログラムの評価値を生成出力する処理と、
をコンピュータに実行させる評価プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラムに含まれる変数の参照関係に着目してプログラムの評価を行う、プログラム評価方法および装置ならびに評価プログラムに関する。
【背景技術】
【０００２】
プログラムには、価値のあるアルゴリズムや利用者に対して秘密にすべき情報が含まれる場合がある。近年、プログラムを解析するための技術が数多く開発されており、これらの技術を用いてプログラムが解析されると、不正者が秘密情報を入手する脅威が考えられる。この脅威に対し、プログラムの仕様を保ったままプログラムの解析を困難にする難読化という技術がある。
【０００３】
難読化の定量的な評価方法として、従来、［Ｇｏｔｏ００］［Ｇｏｔｏ０１］が知られている（それぞれ、非特許文献１、２参照）。例えば、［Ｇｏｔｏ００］は、ソースコードの構造の複雑さに着目した難読化の評価方法であり、また、［Ｇｏｔｏ０１］は、ソースコードの構造の複雑さおよびモジュール間の呼び出し関係の複雑に基づいた評価方法である。また、対象物の参照関係を利用した評価方法として、［Ｐａｇｅ９８］（非特許文献３参照）がある。この方法は、Ｗｅｂページの重要度をページ間のリンク構造を用いて決定するＰａｇｅらによる方法であり、検索サイトＧｏｏｇｌｅ（非特許文献４参照）におけるＷｅｂページのランキングに利用されている。
【非特許文献１】Hideaki Goto, Masahiro Mambo, Kenjiro Matsumura, and Hiroki Shizuya. An approach to the objective and quantitative evaluation of tamper-resistant software. In the third International Workshop on Information Security,ISW '00, Lecture Notes in Computer Science 773, pages 82-96, 2000.
【非特許文献２】Hideaki Goto, Masahiro Mambo, Hiroki Shizuya, and Yasuyoshi Watanabe. Evaluation of temper-resident software deviating from structured programming rules. In the 6th Australasian Conference on Information Security and Privacy, ACISP 01, Lecture Notes in Computer Science 2119, pages 145-158, 2001.
【非特許文献３】Lawrence Page and Sergey Brin. The pagerank citation ranking: Bringing order to the web. In Stanford University, 1998. http://citeser. Ist. Psu. Edu/page98pagerank. html
【非特許文献４】検索サイトGoogle. http://google.com
【発明の開示】
【発明が解決しようとする課題】
【０００４】
上記した非特許文献１および２は、プログラムの制御の流れの複雑さを評価することに適した方式であるが、データの複雑さの評価には適していない。また、非特許文献３は、ランダムサーファーモデルに基づいたものであり、Ｗｅｂページの重要度の相対的評価には適しているが、絶対的評価には適していない。
このように、従来、多くの難読化方法が提案されてきたが、これらの方法は安全性に対する定量的な評価は十分に与えられていないのが現状である。
【０００５】
本発明は上記事情に基づいてなされたものであり、プログラムに含まれる変数の参照関係に着目して、例えば難読化されたプログラムの評価を行うことで、安全性に対する定量的な評価を与えることのできる、プログラム評価方法および装置ならびに評価プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記した課題を解決するために本発明は、プログラムに含まれる変数の参照関係を用い、演算装置によってプログラムの評価を行うプログラム評価方法であって、前記変数をグラフの節点に割付け、ある節点に割り付けられた変数を参照して計算される値が他の節点に割り付けられる変数に代入されたときに、前記ある節点から他の節点に向かう枝を加えた変数の依存関係グラフを生成するステップと、初期値が代入されている変数に対応する前記節点にある初期評価値を設定し、初期値が代入されていない変数に対応する前記節点に他の初期評価値を設定するステップと、前記ある初期評価値が設定され、かつ、評価値の加算が終了したことを示すフラグが設定されていない前記節点のそれぞれについて、互いに隣接する節点の評価値を加算して自身の評価値を更新して、評価値の加算が終了したことを示すフラグを設定するステップと、すべての節点の更新された評価値の総和を算出して前記プログラムの評価値を生成出力するステップと、を有することを特徴とする。
【０００７】
また、本発明のプログラム評価装置は、プログラムに含まれる変数をグラフの節点に割付け、ある節点に割り付けられた変数を参照して計算される値が他の節点に割り付けられる変数に代入されたときに、前記ある節点から他の節点に向かう枝を加えた変数の依存関係グラフを生成する依存関係グラフ生成手段と、初期値が代入されている変数に対応する前記節点にある初期評価値を設定し、初期値が代入されていない変数に対応する前記節点に他の初期評価値を設定する初期評価値設定手段と、前記ある初期評価値が設定され、かつ、評価値の加算が終了したことを示すフラグが設定されていない前記節点のそれぞれについて、互いに隣接する節点の評価値を加算して自身の評価値を更新して、評価値の加算が終了したことを示すフラグを設定する評価値更新手段と、すべての節点の更新された評価値の総和を算出して前記プログラムの評価値を生成出力する評価値生成出力手段と、を備えたことを特徴とする。
【０００８】
また、本発明は、プログラムに含まれる変数の参照関係を用い演算装置によってプログラムの評価を行うプログラム評価装置に用いられる評価プログラムであって、前記変数をグラフの節点に割付け、ある節点に割り付けられた変数を参照して計算される値が他の節点に割り付けられる変数に代入されたときに、前記ある節点から他の節点に向かう枝を加えた変数の依存関係グラフを生成する処理と、初期値が代入されている変数に対応する前記節点にある初期評価値を設定し、初期値が代入されていない変数に対応する前記節点に他の初期評価値を設定する処理と、前記ある初期評価値が設定され、かつ、評価値の加算が終了したことを示すフラグが設定されていない前記節点のそれぞれについて、互いに隣接する節点の評価値を加算して自身の評価値を更新して、評価値の加算が終了したことを示すフラグを設定する処理と、すべての節点の更新された評価値の総和を算出して前記プログラムの評価値を生成出力する処理と、をコンピュータに実行させることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、プログラムに含まれる変数の参照関係に着目してプログラムの評価を行うことで、プログラム解析の困難さを定量的に評価することができる。また、相対的な評価方法は非特許文献３により実現されているが、本発明によれば、絶対的に定義された初期条件（初期値が代入されている変数の評価値を1とする）に基づく評価を行うことで絶対的な評価方法も提供することができる。
【発明を実施するための最良の形態】
【００１０】
図１は、本発明の実施形態に係るプログラム評価装置の内部構成を機能展開して示した図である。
図１に示すプログラム評価装置１０は、プログラムインタフェース部１１と、依存関係グラフ生成部１２と、依存関係グラフ１３と、初期評価値設定部１４と、評価値更新部１５と、評価値算出部１６とで構成される。
【００１１】
プログラムインタフェース部１１は、外部から入力されるプログラム、例えばある難読化アルゴリズムによって符号化されたプログラムを取込み、依存関係グラフ生成部１２へ供給する。また、依存関係グラフ生成部１２は、与えられるプログラムに含まれる変数をグラフの節点に割付け、ある節点に割り付けられた変数を参照して計算される値が他の節点に割り付けられる変数に代入されたときに、ある節点から他の節点に向かう枝を加えた変数の依存関係グラフ１３を生成する依存関係グラフ生成手段として機能する。
一方、初期評価値設定部１４は、初期値が代入されている変数に対応する節点にある初期評価値（例えば、“１”）を設定し、それ以外の変数に対応する節点に他の初期評価値（例えば、“０”）を設定する初期評価値設手段として機能する。
【００１２】
評価値更新部１５は、初期評価値“０”が設定されており、かつ、評価が終了したことを示すフラグが設定されていない節点のそれぞれについて、互いに隣接する節点の評価値を加算して自身の評価値を更新する評価値更新手段として機能する。また、評価値生成出力部１６は、すべての節点の更新された評価値の総和を算出してプログラムの評価値を生成出力する評価値生成出力手段として機能する。
【００１３】
図２は、本発明の実施形態に係るプログラム評価方法の手順を説明するために引用したフローチャートである。
以下、図２に示すフローチャートを参照しながら本発明の実施形態に係るプログラム評価方法について詳細に説明する。
【００１４】
ここでは、以下の２つの条件を満たす評価尺度を用いることとする。一つは、多くの変数の値を参照している変数の評価値は高く（その変数の解析は難しい）、他の一つは、評価値の高い変数の値を参照している変数の評価値は高いということである。
この条件を満たす相対的な評価方法は、従来の非特許文献３で実現されているが、上記した通り、絶対的な評価には適していない。そこで、本発明においては、初期値が代入されている変数の評価値を“１”と定義することにより、上記の条件を満たす絶対的な評価を与えるものである。以下にその詳細について説明する。
【００１５】
まず、プログラム評価装置１０は、変数の依存関係グラフを生成する（ステップＳ２１）。ここでは、プログラム中で用いられているすべての変数ｘ1，ｘ２，…，ｘnを、ここで生成するグラフの節点に割付ける。次に、変数間の依存関係に応じて節点間に枝を加える、例えば、変数ｘｉを参照して計算された値が、変数ｘｉに代入されている場合には、節点ｘｉへの枝を加える。この依存関係グラフは、プログラムインタフェース部１１を介して供給されるプログラムを取り込んだ依存関係グラフ生成部１２によって生成される。
【００１６】
次に、プログラム評価装置１０は、初期評価値の設定を行う（ステップＳ２２）。ここで、初期評価値設定部１４は、依存関係グラフ生成部１２により生成された依存関係グラフ１３を参照し、初期値が代入されている変数に対応する節点には、初期評価値として“１”を、それ以外の変数に対応する節点には、初期評価値として“０”を設定する。
続いて、プログラム評価装置１０は、評価値更新部１５を起動して各節点の評価値の算出を行う（ステップＳ２３）。ここでは、はじめに、“０”以外の評価値が設定されており、なおかつフラグが未設定の節点を列挙する。そして、列挙されたそれぞれの節点に対し、以下の操作を行う。
【００１７】
すなわち、評価値更新部１５は、列挙された節点ｘｉに隣接する節点ｘｉ1，ｘｉ2，…，ｘｊｋの評価値Ｅ(ｘj1），Ｅ(ｘｊ２），…，Ｅ(ｘjｋ)に、それぞれｘｉの評価値Ｅvalｖ(ｘｉ)を加算する。このとき、ｘｉの評価値Ｅ(ｘｉ)自身にも、他の節点の評価値が加算され、更新される可能性がある。このため、ここでは、更新前の値を他の節点の評価値に加算するものとする。当該頂点に自己ループが存在する場合にも同等に、更新前の自身の評価値を加算する。
次に、評価が終了した節点ｘｉにフラグを設定する。以上の処理は、すべての節点にフラグが設定されるまで繰り返し行われる（ステップＳ２４）。
【００１８】
プログラム評価装置１０は、続いて評価値算出部１６を起動してプログラム全体の評価値の算出を行う（ステップＳ２５）。すなわち、評価値算出部１６は、すべて節点の評価値の総和を求める。
【００１９】
上記したプログラムの評価方法についてソースコードに適用した具体例を図４に示す。図４に示すソースコードは、ある難読化アルゴリズムによって図３に示す難読化前のソースコードを難読化したものである。
ここで、ある難読化手法とは、福島和英、清本晋作、田中俊昭著、コンピュータセキュリティシンポジュウム２００４（ＣＳＳ２００４）予稿集、「多変数の符号化による難読化方式の提案」、頁２４７−頁２５２に記載されたものに従う。
【００２０】
まず、変数間の依存関係グラフを作成する。入力されたプログラムからは図５に示される変数の依存関係グラフが得られる。ここでは、変数の一例として、Ｘ、Ｙ、Ｚ、Ｘｔｍｐ、Ｙｔｍｐ、Ｚｔｅｍｐが示され、それらの依存関係が枝（矢印実線）で示されている。
次に、初期評価値の設定を行う。ここで、節点Ｘ、ＹおよびＺには初期値が代入されているので、初期評価値として“１”を設定する。初期値が代入されていない節点Ｘｔｍｐ、ＸｔｍｐおよびＺｔｍｐには、初期評価値として“０”を設定する。このことにより更新される依存関係グラフは、図６に示されている。
図６において、節点Ｘ、ＹおよびＺには、評価値“１”が設定されており、また、フラグは設定されていない。このため、これらの節点に対してステップＳ２３に示す「各節点の評価値の算出処理」を実行する。すなわち、節点Ｘ、ＹおよびＺには、それぞれ、節点Ｘｔｍｐ、ＸｔｍｐおよびＺｔｍｐが隣接している。このため、節点Ｘｔｍｐ、ＸｔｍｐおよびＺｔｍｐの評価値にそれぞれ“１”を加算し、節点Ｘ、ＹおよびＺにフラグを設定する。ここで生成され、依存関係グラフに反映されるフラグは、図７に示されている。
【００２１】
次に、節点Ｘｔｍｐ、ＸｔｍｐおよびＺｔｍｐには評価値“１”が設定されており、また、フラグは設定されていない。このため、これらの節点に対してＳ２３に示す「各節点の評価値の算出処理」を実行する。すなわち、節点Ｘｔｍｐ、ＸｔｍｐおよびＺｔｍｐには３つの節点Ｘ、ＹおよびＺが全て隣接している。このため、節点Ｘ、ＹおよびＺの評価値にそれぞれ“３”を加算し、節点Ｘｔｍｐ、ＸｔｍｐおよびＺｔｍｐにフラグを設定する。このようにして得られる最終的な依存関係グラフを図８に示す。
以上の処理により、すべての節点にフラグが設定される。ここで、すべての節点における評価値の総和は“１５”になるため、図４に示すソースコードの評価値は“１５”になる。また、同様に、図３に示す難読化前のソースコードに、本発明のプログラム評価方法を適用すると図９に示す依存関係グラフが得られる。これによれば、難読化前のソースコードの評価値は“５”となり、難読化処理によって評価値が“１０”だけ増加していることが分かる。
【００２２】
以上説明のように本発明は、プログラムに含まれる変数の参照関係に着目してプログラムの評価を行うものであり、このことにより、プログラム解析の困難さを定量的に評価することができる。また、相対的な評価方法は非特許文献３により実現されているが、本発明によれば、絶対的に定義された初期条件（初期値が代入されている変数の評価値を1とする）に基づく評価を行うことで絶対的な評価方法も提供することができる。
【００２３】
なお、図１に示すプログラムインタフェース部１１と、依存関係グラフ生成部１２と、依存関係グラフ１３と、初期評価値設定部１４と、評価値更新部１５と、評価値算出部１６のそれぞれで実行される手順をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって本発明のプログラム評価装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００２４】
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００２５】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００２６】
【図１】本発明の実施形態に係るプログラム評価装置の内部構成を機能展開して示したブロック図である。
【図２】本発明の実施形態に係るプログラム評価方法の手順を説明するたに引用したフローチャートである。
【図３】本発明の実施形態の動作を説明するために引用した、難読化前のプログラムにおけるソースリストの一例を示す図である。
【図４】本発明の実施形態の動作を説明するために引用した、難読化後のプログラムにおけるソースリストの一例を示す図である。
【図５】本発明の実施形態の動作を説明するために引用した、変数の依存関係グラフの生成過程を示す図である。
【図６】本発明の実施形態の動作を説明するために引用した、変数の依存関係グラフの生成過程を示す図である。
【図７】本発明の実施形態の動作を説明するために引用した、変数の依存関係グラフの生成過程を示す図である。
【図８】本発明の実施形態の動作を説明するために引用した、変数の依存関係グラフの生成過程を示す図である。
【図９】本発明の実施形態の動作を説明するために引用した、変数の依存関係グラフの生成過程を示す図である。
【符号の説明】
【００２７】
１０…プログラム評価装置、１１…プログラムインタフェース部、１２…依存関係グラフ生成部、１３…依存関係グラフ、１４…初期評価値設定部、１５…評価値更新部、１６…評価値算出部
【図１】
0004732093.tif 000002
【図２】
0004732093.tif 000003
【図３】
0004732093.tif 000004
【図４】
0004732093.tif 000005
【図５】
0004732093.tif 000006
【図６】
0004732093.tif 000007
【図７】
0004732093.tif 000008
【図８】
0004732093.tif 000009
【図９】
0004732093.tif 000010