JP4945296B2 - コード検出装置及びコード検出方法 - Google Patents

Description

本発明は、複数のコードを含むプログラムコードを解析することで検出対象コードを検出するコード検出装置及びコード検出方法に関する。

複数のコード（命令）を含むプログラムコードの解析をプログラム実行中に行う動的解析技術が知られている。動的解析技術は、プログラムコード中の少なくとも１つのコードからなるブロック単位で各コードを変換及び実行するインタプリンタ実行を利用することで実現される。また、プログラムコード中の特定のコードを実行させるか否かを制御するプログラム実行制御技術が知られている。

さらに、インタプリンタ実行を用いるプログラム実行制御技術が提案されている（非特許文献１及び２参照）。インタプリンタ実行を用いるプログラム実行制御技術では、図１に示すように、プログラムコードをブロック単位で解析することで検出対象コードが検出される。

検出された検出対象コードには、プログラム実行制御用のコードであるフックコードが追加される。フックコードの追加されたコードは、プログラム実行時に、当該コードを実行するか否かを制御する実行制御コードへ分岐させられる。フックコードは検出対象コードの直前に追加されるため、フックコードをバイパスすることは不可能であり、検出対象コードの実行を確実に制御することができる。

なお、インタプリンタ実行の実行単位であるブロックとしては、例えば、プログラムコード中の２つの分岐命令に挟まれた領域が用いられる。分岐が発生するまでは、メモリのアドレス降順でプログラムコードが実行されるので、通常の動作から逸脱することはない。また、分岐命令まで実行されれば、分岐先のアドレスが判明し、次に読み込むブロックが特定される。このため、プログラムコードをブロック単位で順次解析及び実行可能となる。

非特許文献１は、インタプリンタ実行を用いるプログラム実行制御技術を利用したmobile code実行の安全化方法を開示している。ここでmobile codeとは、ネットワーク経由で取得したプログラムコードである。

非特許文献１の方法は、信頼されたプログラムコードの実行中に、当該プログラムコードのメモリ領域に非信頼mobile codeを展開して実行するシステムに適用される。また、非特許文献１の方法は、mobile codeから不正な分岐命令が発行され、本来のリターンアドレスとは異なるコードへ実行制御が移動し、意図しないコードが実行されることを脅威として想定している。

非特許文献１の方法は、上記の脅威を防止するために、mobile codeから分岐命令を検出する。検出された分岐命令の直前には、当該分岐分岐命令の実行可否を判定するためのフックコードが追加される。これにより、mobile codeの解析及び変換後にmobile codeを実行する際、不正な分岐命令が実行されることが防止される。

一方、非特許文献２は、インタプリンタ実行を用いるプログラム実行制御技術を利用したリソースアクセス制御方法を開示している。当該リソースアクセス制御手法では、プログラムが呼ぶシステムコールに対してアクセス制御が実行される。例えば、特定のファイルの読み出しは許可するが、書き込みは禁止するといったリソースアクセス制御の用途が考えられる。

非特許文献２の方法は、プログラムバイナリをブロック毎に読み込み、読み込まれたブロックをＳｔｒａｔａと呼ばれるＶＭ（Virtual Machine）上でインタプリンタ実行する。その際、特定のシステムコールを呼ぶコードが検出された場合、当該コードの直前に、Ｓｔｒａｔａが予め備えるアクセス制御コードを呼出すフックコードが追加される。これにより、プログラムコードにアクセス制御対象のシステムコールが含まれる場合には、当該システムコールの実行を許可するか否かを判定可能となる。

上記のように、非特許文献１及び２の手法は、プログラムコード内での関数呼出等、プログラムコード外部からの監視が不可能なコードについても制御可能である点で、他のプログラム制御技術やアクセス制御技術よりも優れている。

さらにStrataは、インタプリンタ実行のオーバヘッドを削減する技術として、一度インタプリンタ実行を行ったブロックをメモリ上にキャッシュとして保持する機能を備えている。キャッシュは、ブロックのアドレスと、解析済み（コンパイル済み）コードとの組で蓄積される。Strataでは、図２に示すように、実行中のプログラムコードのアドレスをカウントするプログラムカウンタを参照することで、現時点でのプログラムコードのアドレスが特定され、現時点でのプログラムコードのアドレスをキーとしてキャッシュが検索される。

キャッシュされている場合、現時点でのプログラムコードのアドレスに対応する解析済みコードが実行される。一方、キャッシュされていない場合、通常のインタプリンタ実行が行われる。これにより、同一のプログラムコードを複数回インタプリンタ実行する場合に、２回目以降のインタプリンタ実行に要するオーバヘッドが削減される。
Robert Wahbe et.al., "Efficient software-based fault isolation", In Proc. of the fourteenth ACM Symposium on Operating Systems Principals, 1994. Kevin Scott et.al., "Safe virtual execution using software dynamic translation", In Proc. of 18th Annual Computer Security Applications Conference, 2002.

上述した非特許文献１及び、Strataのキャッシュ機能を利用しない場合の非特許文献２の手法では、次の（１）〜（５）のプロセスが実行される。

（１）プログラムコードからあるブロックが読み込まれる。

（２）当該ブロックを構成するコードが解析される。

（３）解析により検出対象コードが検出された場合には、当該検出対象コードにフックコードが追加される。

（４）ブロック内のコード解析後、当該ブロックが実行される。

（５）当該ブロックの実行中にフックコードが検出されると、実行制御コードが呼出される。

しかしながら、プロセス（２）、（３）及び（５）は、通常のプログラム実行では発生しないプロセスであり、オーバヘッド増加の要因となり得る。特に、プロセス（２）において各ブロック内のコードを解析する処理や、プロセス（３）においてフックコードを追加する処理にコストを要する。

一方、非特許文献2においてStrataのキャッシュ機能を利用した場合でも、キャッシュミスの発生時には、上記と同等のオーバヘッドが発生する。 キャッシュミスは、あるブロックが最初に実行される際には必ず発生する。あるいは、搭載メモリ容量の少ない計算機（例えば、携帯型デバイス）では、キャッシュ領域に割り当て可能なメモリ容量が限られるので、キャッシュミスの発生を避けることは困難である。

以上のように、複数のコードを含むプログラムコードを解析することで検出対象コードを検出するプログラム解析システムでは、オーバヘッドを削減することが困難であった。

上記問題点に鑑み、本発明は、複数のコードを含むプログラムコードを解析することで検出対象コードを検出するプログラム解析システムにおいて、オーバヘッドを削減可能なコード検出装置及びコード検出方法を提供することを目的とする。

上記目的を達成するために、本発明の第１の特徴は、複数のコードを含むプログラムコードを解析することで検出対象コードを検出するコード検出装置であって、前記プログラムコードを解析する第１解析部と、前記第１解析部による解析結果を用いて前記プログラムコードを解析する第２解析部とを備え、前記第１解析部は、前記プログラムコードから前記検出対象コードを検出する第１検出部と、前記第１検出部による検出結果に基づき、前記プログラムコードのうち前記第２解析部が解析対象とする領域である解析対象領域を特定するための解析情報を生成する解析情報生成部とを備え、前記第２解析部は、前記解析情報を参照することで前記プログラムコード中の前記解析対象領域を特定する特定部と、前記特定部によって特定された前記解析対象領域から前記検出対象コードを検出する第２検出部とを備えることを要旨とする。

このような特徴によれば、特定部は、解析情報を参照することでプログラムコード中の解析対象領域を特定する。第２検出部は、特定部によって特定された解析対象領域から検出対象コードを検出する。第２検出部は、プログラムコードの一部に対して検出対象コードの検出処理を行うので、第２解析部の処理負荷が削減され、オーバヘッドが削減する。

本発明の第２の特徴は、本発明の第１の特徴に係り、前記第１解析部は、前記プログラムコードの実行前に前記プログラムコードを解析し、前記第２解析部は、前記プログラムコードの実行中に前記プログラムコードを解析することを要旨とする。

このような特徴によれば、第１解析部がプログラムコードの実行前にプログラムコードを解析し（静的解析）、第２解析部がプログラムコードの実行中にプログラムコードを解析する（動的解析）。第２検出部は、プログラムコードの一部に対して検出対象コードの検出処理を行うので、動的解析の処理負荷が削減される。

本発明の第３の特徴は、本発明の第１の特徴に係り、前記検出対象コードの実行を制御するためのコードであるフックコードを含むプログラム制御情報を記憶する制御情報記憶部をさらに備え、前記第２解析部は、前記解析対象領域から検出された前記検出対象コードに前記フックコードを追加することを要旨とする。

このような特徴によれば、第２解析部は、解析対象領域から検出された検出対象コードに、検出対象コードの実行を制御するためのコードであるフックコードを追加する。第２検出部は、プログラムコードの一部に対して検出対象コードの検出処理を行うので、フックコード追加処理の処理負荷が削減される。

本発明の第４の特徴は、本発明の第１の特徴に係り、前記検出対象コードの実行を制御するためのコードであるフックコードを含むプログラム制御情報を記憶する制御情報記憶部をさらに備え、前記第１解析部は、前記プログラムコードから検出された前記検出対象コードに前記フックコードを追加し、前記特定部は、前記第１解析部により前記フックコードの追加されていない領域を前記解析対象領域として特定することを要旨とする。

このような特徴によれば、第１解析部は、検出対象コードにフックコードを追加する。第２解析部の特定部は、フックコードの追加されていない領域を解析対象領域として特定するので、フックコードの追加されている領域は解析対象外とすることができ、第２解析部におけるフックコード追加処理の処理負荷が削減される。

本発明の第５の特徴は、本発明の第４の特徴に係り、前記第１解析部は、所定の条件に応じて、前記プログラムコードから検出された前記検出対象コードに前記フックコードを追加するか否かを判定することを要旨とする。

このような特徴によれば、第１解析部は、所定の条件（例えば、プログラムコードのサイズ、処理負荷）に応じて、プログラムコードから検出された検出対象コードにフックコードを追加するか否かを判定する。このため、第１解析部においてフックコードを追加するか否かを適応的に決定できる。

本発明の第６の特徴は、本発明の第４の特徴に係り、前記第１解析部は、前記フックコードを含むフック専用関数へ分岐する分岐命令を、前記フックコードとして前記検出対象コードに追加することを要旨とする。

このような特徴によれば、第１解析部は、フックコードを直接追加するのではなく、フック専用関数によりフックコードを検出対象コードへ間接的に追加する。これにより、フックコードを直接追加するよりもコードサイズを削減できる。

本発明の第７の特徴は、本発明の第１の特徴に係り、前記検出対象コードを特定する情報を含むプログラム制御情報を記憶する制御情報記憶部をさらに備え、前記第１検出部は、前記プログラム制御情報が更新された場合、更新後の検出対象コードを特定する情報に基づいて前記プログラムコードから前記更新後の検出対象コードを検出し、前記解析情報生成部は、前記第１検出部による前記更新後の検出対象コードの検出結果に基づき、前記解析情報を更新することを要旨とする。

このような特徴によれば、検出対象コードが更新された場合に、第１検出部が更新後の検出対象コードを検出し、解析情報生成部が第１検出部による更新後の検出対象コードの検出結果に基づいて解析情報を更新する。これにより、検出対象コードが更新された場合にも対応可能となる。

本発明の第８の特徴は、本発明の第１の特徴に係り、前記検出対象コードを特定する情報と、前記検出対象コードの変更先候補のコードである候補コードを特定する情報を含むプログラム制御情報を記憶する制御情報記憶部をさらに備え、前記第１検出部は、前記プログラム制御情報に基づき、前記プログラムコードから前記検出対象コード及び前記候補コードを検出し、前記解析情報生成部は、前記第１検出部による検出結果に基づき、前記プログラムコードのうち前記候補コードを含む領域を特定する再生成情報を生成し、前記第１検出部は、前記プログラム制御情報中の前記検出対象コードを特定する情報が変更された場合、前記再生成情報によって特定される領域から、変更された検出対象コードを検出することを要旨とする。

このような特徴によれば、第１検出部は、検出対象コードだけでなく、候補コードも検出する。解析情報生成部は、候補コードを含む領域を特定する再生成情報を生成する。そして、第１検出部は、検出対象コードがいずれかの候補コードに変更された場合に、再生成情報によって特定されるプログラムコードの領域から変更された検出対象コードを検出する。これにより、検出対象コードが変更された場合でも直ちに対応可能となる。

本発明の第９の特徴は、本発明の第１の特徴に係り、前記検出対象コードは、前記プログラムコード中の特定のコードを呼出す制御移動命令であり、前記第１検出部及び前記第２検出部は、前記プログラムコードから制御移動命令を検出した場合、検出された制御移動命令の呼出先コードが前記特定のコードであるか否かを判定し、前記検出された制御移動命令の呼出先コードが前記特定のコードである場合、前記検出された制御移動命令が前記検出対象コードであると判定することを要旨とする。

このような特徴によれば、検出対象コードがプログラムコード中の特定のコードを呼出す制御移動命令である場合に、当該制御移動命令が確実に検出される。

本発明の第１０の特徴は、本発明の第１の特徴に係り、前記第２解析部は、解析済みのコードである解析済みコードを記憶するキャッシュ記憶部をさらに備え、前記第２検出部は、前記解析対象領域から前記検出対象コードが検出された場合、前記検出対象コードを含む前記解析対象領域に対応する解析済みコードを前記キャッシュ記憶部から取得することを要旨とする。

このような特徴によれば、検出対象コードを含む検出対象領域に対応する解析済コードを再利用することで、第２解析部の処理負荷が削減される。

本発明の第１１の特徴は、本発明の第１の特徴に係り、前記第１解析部は、前記プログラムコードのうち前記検出対象コードを含まない領域を非解析対象領域として検出し、前記解析情報は、前記非解析対象領域を特定する情報を含み、前記第２解析部の前記特定部は、前記非解析対象領域を特定する情報が示す領域を除いた前記プログラムコードの領域を前記解析対象領域として特定することを要旨とする。

本発明の第１２の特徴は、本発明の第１１の特徴に係り、前記非解析対象領域を特定する情報は、前記非解析対象領域の開始アドレスを含むことを要旨とする。

本発明の第１３の特徴は、本発明の第１１の特徴に係り、前記第１解析部は、前記プログラムコードを２つの分岐命令で挟まれた領域毎に分割し、分割された領域毎に前記検出対象コードの検出処理を行うことで前記非解析対象領域を検出することを要旨とする。

このような特徴によれば、２つの分岐命令で挟まれた領域毎に検出対象コードの検出処理を行うので、プログラムコード内で重複する領域が発生することなく、１つの検出対象コードが複数の領域で検出されることが回避される。

本発明の第１４の特徴は、本発明の第１１の特徴に係り、前記第１解析部は、前記非解析対象領域を特定する情報を含む前記解析情報を記憶する解析情報記憶部をさらに備え、前記第２解析部は、前記非解析対象領域を特定する情報と、前記非解析対象領域が実行された回数とを対応付けた履歴情報を記憶する履歴情報記憶部をさらに備え、前記解析情報生成部は、前記履歴情報記憶部に記憶されている前記履歴情報に基づき、前記解析情報記憶部に記憶されている前記解析情報を更新することを要旨とする。

このような特徴によれば、実行された非解析対象領域が履歴情報として記録されるので、解析情報生成部は、実際に実行された非解析対象領域を優先的に解析情報に含めるなど、解析情報をより効率的に生成することが可能となる。

本発明の第１５の特徴は、本発明の第１４の特徴に係り、前記履歴情報記憶部に記憶される前記非解析対象領域を特定する情報は、少なくとも前記非解析対象領域の開始アドレスを含むことを要旨とする。

このような特徴によれば、履歴情報として、非解析対象領域の開始アドレスが記録されるため、非解析対象領域が一意に特定される。

本発明の第１６の特徴は、本発明の第１４の特徴に係り、前記特定部は、前記解析情報記憶部中の上位から下位へ前記非解析対象領域を特定する情報を参照することで、前記次に実行されるプログラムコードの領域が前記非解析対象領域であるか否かを特定し、前記解析情報生成部は、前記履歴情報において一定回数以上に対応する前記非解析対象領域を特定する情報を、前記解析情報記憶部中の上位に設定し、前記履歴情報において一定回数未満に対応する前記非解析対象領域を特定する情報を、前記解析情報記憶部中の下位に設定することを要旨とする。

このような特徴によれば、解析情報生成部は、履歴情報を利用して、過去に実行された非解析対象領域を（線形）検索順序の上位に配置することで、特定部が非解析対象領域を参照（検索）する時間が短縮される。

本発明の第１７の特徴は、本発明の第１の特徴に係り、前記検出対象コードは、分岐命令であり、前記第２解析部は、解析済みコードに所定の分岐命令が含まれる場合に、前記所定の分岐命令を特定する情報、及び前記所定の分岐命令の分岐先を分岐先情報として記憶する分岐先情報記憶部をさらに備え、前記第１検出部は、前記分岐先情報記憶部に記憶される前記分岐先情報に基づき、前記検出対象コードを検出することを要旨とする。

このような特徴によれば、第１検出部は、分岐先情報を利用することで、分岐先の特定が困難であることにより検出漏れが生じていたプログラムコードまで解析可能となり、検出対象コードの検出漏れが削減される。

本発明の第１８の特徴は、本発明の第１７の特徴に係り、前記所定の分岐命令は、他の命令の実行結果に応じて分岐先が定まる間接分岐命令であり、前記分岐先情報記憶部は、前記解析済みコードが実行される際に前記分岐先情報を記憶することを要旨とする。

このような特徴によれば、間接分岐命令についての分岐先を検出することが可能となる。

本発明の第１９の特徴は、複数のコードを含むプログラムコードを解析することで検出対象コードを検出するコード検出方法であって、前記プログラムコードを解析する第１ステップと、前記第１ステップによる解析結果を用いて前記プログラムコードを解析する第２ステップとを備え、前記第１ステップは、前記プログラムコードから前記検出対象コードを検出するステップと、前記検出対象コードの検出結果に基づき、前記プログラムコードのうち前記第２ステップが解析対象とする領域である解析対象領域を特定するための解析情報を生成するステップとを備え、前記第２ステップは、前記解析情報を参照することで前記プログラムコード中の前記解析対象領域を特定するステップと、前記特定部によって特定された前記解析対象領域から前記検出対象コードを検出するステップとを備えることを要旨とする。

本発明によれば、複数のコードを含むプログラムコードを解析することで検出対象コードを検出するプログラム解析システムにおいて、オーバヘッドを削減可能なコード検出装置及びコード検出方法を提供できる。

次に、図面を参照して、本発明の第１〜第６実施形態を説明する。以下の第１〜第６実施形態における図面の記載において、同一又は類似の部分には同一又は類似の符号を付している。

＜第１実施形態＞
（プログラム解析システムの構成）
先ず、本実施形態に係るプログラム解析システムの構成について説明する。図３は、本実施形態に係るプログラム解析システムの機能ブロック図である。

図３に示すように、プログラム解析システムは、コード検出装置１００、コード実行装置２００、プログラムコード記憶部３００、動的解析済みコード記憶部３２０及び制御情報記憶部４００を備える。

プログラムコード記憶部３００は、複数のコードを含むプログラムコードを記憶する。本実施形態では、プログラムコードを構成する各コードが、命令、当該命令のアドレス、及び当該命令の引数で構成されるアセンブリ言語で記述されている場合を例に説明する。

（コード検出装置の構成）
コード検出装置１００は、プログラムコードを解析することで検出対象コードを検出する。コード検出装置１００は、第１解析部１１０及び第２解析部１２０を備える。

第１解析部１１０は、プログラム実行前にプログラムコードを解析する「静的解析」を実行する。第２解析部１２０は、プログラム実行中にプログラムコードを解析する「動的解析」を実行する。本実施形態では、第２解析部１２０は、インタプリンタ実行のように、プログラムコードをブロック単位で読み込んで解析する。

第１解析部１１０は、ブロック生成部１１１、第１検出部１１２、解析情報生成部１１３及び解析情報記憶部１１４を備える。

ブロック生成部１１１は、プログラムコード記憶部３００に記憶されたプログラムコードからブロックを順次生成する。

第１検出部１１２は、ブロック生成部１１１によって生成されたブロックに対してブロック解析処理を行う。具体的には、第１検出部１１２は、ブロック生成部１１１によって生成されたブロック内に検出対象コードが含まれているか否かを判定する。

なお、制御情報記憶部４００は、検出対象コードを特定する情報と、当該検出対象コードに追加すべきフックコードを特定する情報とを記憶する。第１検出部１１２は、制御情報記憶部４００を参照することでブロック内の検出対象コードを検出する。

解析情報生成部１１３は、第１検出部１１２による検出結果に基づき、第２解析部１２０が解析対象とするブロック（領域）である解析対象ブロックを特定するための解析情報を生成する。解析情報生成部１１３によって生成された解析情報は、解析情報記憶部１１４内に記憶される。

第２解析部１２０は、特定部１２１、第２検出部１２２、コード出力部１２３、コンパイル部１２４、フックコード追加部１２５及びキャッシュ記憶部１２６を備える。

特定部１２１は、解析情報記憶部１１４に記憶された解析情報を参照することで、プログラムコードから解析対象ブロックを特定する。

第２検出部１２２は、特定部１２１によって特定された解析対象ブロックから検出対象コードを検出する。解析対象ブロックから検出対象コードが検出されると、第２検出部１２２は、当該解析対象ブロックの動的解析済みコードがキャッシュ記憶部１２６に存在するか否かを判定する。

当該解析対象ブロックの動的解析済みコードがキャッシュ記憶部１２６に存在する場合、第２検出部１２２は、キャッシュされている動的解析済みコードを取得する。キャッシュ記憶部１２６から取得された動的解析済みコードは、コード出力部１２３によって動的解析済みコード記憶部３２０に格納される。当該解析対象ブロックの動的解析済みコードがキャッシュ記憶部１２６に存在しない場合、第２検出部１２２は、当該解析対象ブロックを、コード出力部１２３を介してコンパイル部１２４に出力する。

コンパイル部１２４及びフックコード追加部１２５は、検出対象コードの直前にフックコードを追加すると共に、解析対象ブロックをコンパイル処理する。コンパイル処理後の解析対象ブロックは、キャッシュ記憶部１２６内に記憶される。

コード出力部１２３は、コンパイル処理後の解析対象ブロックを動的解析済みコードとして出力する。コード出力部１２３によって出力された動的解析済みコードは、動的解析済みコード記憶部３２０内に記憶される。

（コード実行装置の構成）
コード実行装置２００は、動的解析済みコード記憶部３２０に記憶された動的解析済みコードを実行する。コード実行装置２００は、コード実行部２１０、コード制御部２２０及び制御ポリシー記憶部８００を備える。

コード実行部２１０は、動的解析済みコードをブロック単位で実行する。また、コード実行部２１０は、各ブロックの実行によって、次に実行されるべきプログラムコードのアドレスを特定し、当該アドレスを解析対象ブロックアドレスとして特定部１２１に出力する。このプロセスを繰り返すことで、第２解析部１２０による解析を伴うインタプリンタ実行を行うことが可能となる。

コード実行部２１０は、動的解析済みコードからフックコードが検出された場合には、その旨をコード制御部２２０に通知する。コード制御部２２０は、フックコードが検出された旨の通知を受けると、制御ポリシー記憶部８００に記憶されている制御ポリシーに従って、フックコードが追加されている検出対象コードを実行するか否か判定する。

（解析情報の構成）
次に、解析情報記憶部１１４に記憶される解析情報について説明する。解析情報は、プログラムコードを記憶するメモリ領域のうち検出対象コードを含まない部分のメモリ領域を特定する情報である。

図４は、解析情報の一例を示す図である。図４に示すように、解析情報は、検出対象コードを含まないブロックのブロックＩＤと、当該ブロックの開始アドレスと、当該ブロックの終了アドレスとを対応付けた構成を有している。「ブロック」とは、開始アドレスと終了アドレスとにより表現されるプログラムコードの一部である。以下においては、解析情報記憶部１１４に登録されたブロックを「登録ブロック」と呼ぶ。

（解析情報生成処理）
次に、図５〜図７を参照して、解析情報の生成処理について説明する。

図５に示すように、ブロックは、開始命令から始まり、無条件分岐命令で終了する。無条件分岐命令は、無条件に特定のコードへ分岐する命令であり、例えば次のような命令が該当する。

Ｂ ＰＣ＋ｘｘｘｘ ；アドレスＰＣ＋ｘｘｘｘへの分岐
ＢＬ ＰＣ＋ｙｙｙｙ ；アドレスＰＣ＋ｙｙｙｙへの分岐
ＭＯＶ ＰＣ，ｌｒ ；ｌｒレジスタに格納されたアドレスへの分岐
逆に、条件付き分岐命令とは、次に示すように、条件フィールドを伴い、条件が満たされる場合に特定の分岐先へ制御を移すような命令である。

ＣＭＰ ｌｒ，ｒ１ ；ｌｒレジスタの値とｒ１レジスタの値とを比較
ＢＥＱ ＰＣ＋ｙｙｙｙ ；比較結果に応じて指定アドレスへ分岐
一方、開始命令とは、ｍａｉｎや＿Ｓｔａｒｔといったシンボルで特定される関数の先頭コードである。ｍａｉｎや＿Ｓｔａｒｔを含むブロックを「ブロック１」と呼び、以降Ｎ番目に生成されるブロックを「ブロックＮ」と呼ぶ。ブロック１以外のブロックの開始地点は、あるブロックからの分岐先コードに等しい。

図６は、複数のブロック間の関係を示す図である。図６では、ブロック１に含まれる分岐命令の分岐先はブロック２及びブロック３である。さらに、ブロック３に含まれる分岐命令の分岐先はブロック４である。

（解析情報生成処理の処理フロー）
次に、解析情報生成処理の処理フローについて説明する。図７は、解析情報生成処理の処理フローを示すフローチャートである。

ステップＳ１０００において、第１解析部１１０は、プログラムコードの先頭ブロック（ブロック１）の開始アドレスを取得する。

ステップＳ１００１において、第１解析部１１０は、ステップＳ１０００で取得した開始アドレスからブロック解析処理を実行する。ブロック解析処理の詳細については後述する。

ステップＳ１００２において、第１解析部１１０は、ステップＳ１００１で解析したブロックを解析済みブロックリストへ登録する。解析済みブロックリストは、解析済みのブロックのブロックＩＤ、開始アドレス及び終了アドレスを含む。一度でもブロック解析処理が実行されたブロックは、解析済みブロックリストに登録される。

ステップＳ１００３において、第１解析部１１０は、ステップＳ１００１で解析したブロックの分岐先アドレスをすべて取得する。取得される分岐先アドレスとしては、以下の４つのパターンが考えられる。

（１）分岐先アドレスが特定され、分岐先のブロックが存在し、当該アドレスがいずれの解析済みブロックにも含まれない。

（２）分岐先アドレスが特定され、分岐先のブロックが存在しない。

（３）分岐先アドレスが不特定（分岐がないか分岐先が不明）。

（４）分岐先アドレスが特定され、分岐先のブロックが存在し、当該アドレスがいずれかの解析済みブロックに含まれる。

パターン（１）及び（４）は、通常の分岐である。パターン（２）としては、例えば動的リンクライブラリ関数への分岐が該当する。パターン（３）としては、例えば、プログラム実行時の外部入力により分岐先が決定するような場合が該当する。あるいは、当該ブロックでプログラムが終了するような場合もパターン（３）に含まれる。

パターン（１）及び（４）では、分岐先のブロックを取得可能であるが、パターン（２）及び（３）では、分岐先のブロックを取得できず、その後の解析は不可能である。

パターン（１）及び（４）の違いは、分岐先アドレスを開始アドレスとするブロックが解析済みであるか否かである。これは、当該分岐先アドレスがいずれかの解析済みブロックに含まれるか否かにより判定される。

ステップＳ１００４において、第１解析部１１０は、分岐先のブロックを取得可能であるか否かを判定する。具体的には、取得したすべての分岐先アドレスがパターン（１）又は（４）であった場合、ステップＳ１００５に進む。一方、取得したすべての分岐先アドレスがパターン（２）又は（３）であった場合、ステップＳ１００８に進む。

ステップＳ１００５において、第１解析部１１０は、パターン（１）とパターン（４）との判別を行う。すなわち、取得したすべての分岐先アドレスがいずれかの解析済みブロックに含まれていれば、パターン（４）であり、ステップＳ１００８へ進む。一方、取得したすべての分岐先アドレスがいずれの析済みブロックにも含まれていなければ、分岐先アドレスを開始アドレスとするブロックは未解析であり、ステップＳ１００６へ進む。

ここで、パターン（４）の条件は、分岐先アドレスと解析済みブロックの開始アドレスとが一致する必要はなく、開始アドレスと終了アドレスとに挟まれていればよい。一例として、図８において、矢印を各ブロックの分岐元と分岐先とし、ブロック１からブロック２に分岐し、ブロック２を解析しているものとする。ブロック２の開始アドレスはｘ、かつ終了アドレスはｙであり、解析済みブロックリストに登録されている。その後、ブロック３から、ブロック２のｘとｙに挟まれるアドレスｚに分岐した場合、ｚから始まるブロックの終了アドレスはｙであり、当該ブロックはブロック２に含まれるため、既に解析済みであると判定される。

ステップＳ１００６において、第１解析部１１０は、すべての未解析ブロックの開始（先頭）アドレスを解析候補スタックに積む。解析候補スタックは、次回の解析対象となるブロックの開始アドレスを格納するＦＩＦＯのスタックである。

ステップＳ１００７において、第１解析部１１０は、解析候補スタックから解析対象開始アドレスを１つ取り出す。その後、解析対象開始アドレスから始まるブロックに対して、再びステップＳ１００１が適用されることとなる。

一方、ステップＳ１００８において、第１解析部１１０は、解析候補スタックを検査する。解析候補スタックが空であれば、ステップＳ１０９９へ進み、プログラムコードに対する静的解析を終了する。一方、解析候補スタックが積まれていれば、ステップＳ１００９へ進む。

ステップＳ１００９において、第１解析部１１０は、当該アドレスを１つ取り出す。

ステップＳ１０１０において、第１解析部１１０は、当該アドレスがいずれかの解析済みブロックに含まれるか否かを判定する。

なお、解析対象開始アドレスとして解析候補スタックに積まれた時点では、当該アドレスから始まるブロックは静的解析済みではないが、スタックで解析待ちとなっている間に別のブロックからの分岐により当該ブロックが解析される可能性があるため、ステップＳ１０１０が必要となる。

例えば、図９の例で、ブロック１を解析後、ブロック２，４の開始アドレスｙ、ｗが解析候補として解析候補スタックに積まれる。しかし、ブロック２が先に解析された場合、ブロック３，４へ解析が進み、ブロック３の分岐先として再びｗが解析候補スタックに積まれる。

このように、解析候補スタックに同じ解析対象開始アドレスが複数積まれる可能性があるため、ステップＳ１０１０における解析済みブロックリストによる重複検査は必要である。ステップＳ１０１０において当該アドレスが解析済みでなければ、ステップＳ１００１により実際に解析が実行される。

（ブロック解析処理の処理フロー）
次に、ブロック解析処理の処理フローについて説明する。ブロック解析処理では、与えられたアドレスから始まるブロックに検出対象コードが含まれない場合に、当該ブロックを解析情報記憶部１１４に登録する。検出対象コードの具体例や検出方法については後述する。

図１０は、ブロック解析処理の処理フローを示すフローチャートである。

ステップＳ２０００において、第１解析部１１０は、解析対象ブロックの開始アドレスを取得する。

ステップＳ２００１において、第１解析部１１０は、終了アドレスを特定することで解析対象ブロックを生成する。

ここで、終了アドレスとは、基本的には最後に検出された無条件分岐命令のアドレスであるが、例外がある。例外が発生する例について、図１１を用いて説明する。図１１において、現在解析対象となっているブロックの開始アドレスをｘとし、当該開始アドレスから検索して最初に検出された無条件分岐命令のアドレスがｙであるとする。また、開始アドレスｚ、かつ終了アドレスｙのブロック２は、既に解析済みブロックリストに登録されているものとする。この場合、ｘで開始し、ｙで終了するブロックは、ブロック２と一部重複してしまう。

この状況を防ぐため、ステップＳ２００１において無条件分岐命令を検出することで、取得した終了アドレスが、生成済みブロックの開始アドレス（ここではｗ）を当該ブロックの終了アドレスとする。したがって、この例では、開始アドレスｘのブロック４の終了アドレスはｗとなる。当然、当該ブロックの終了アドレスは無条件分岐命令ではない。

ステップＳ２００２において、第１解析部１１０は、当該ブロックからコードを読み込む。

ステップＳ２００３において、第１解析部１１０は、ステップＳ２００２で読み込んだコードが、検出対象コードに該当するか否かを判定する。ステップＳ２００２で読み込んだコードが検出対象コードに該当する場合、当該ブロックは登録ブロックとして解析情報記憶部１１４に登録されず、処理が終了する。一方、ステップＳ２００２で読み込んだコードが検出対象コードに該当する場合、ステップＳ２００４に進む。

ステップＳ２００４において、第１解析部１１０は、ブロックに存在するコードをすべて読み込んだか否かを判定する。ブロック内に未読み込み（未解析）のコードが存在する場合、ステップＳ２００２に処理が戻る。ブロック内に未読み込みのコードが存在しない場合、ステップＳ２００５に進み、当該ブロックが解析情報記憶部１１４に登録される。

（ブロック解析処理の具体例）
次に、図１２及び図１３を参照して、ブロック解析処理の具体例について説明する。

図１２において、各ブロック内のアルファベットは開始アドレス及び終了アドレスを表し、矢印はブロック間の関係を表している。ハッチングの付されている各ブロックは、解析情報記憶部１１４に登録すべきブロックであるものとする。また、ブロック６の分岐先ブロックは、上述したパターン（２）又はパターン（３）の分岐先であるものとしている。

図１２では、解析可能なブロックは７個であり、解析の重複は起こり得ないため、図７のステップＳ１００１から始まる過程が必ず７回発生する。各過程終了時の解析情報、解析候補スタック及び解析済みブロックリストを図１３に示す。図１３では、解析情報、解析済みブロックリストは、ブロックＩＤで示し、アドレスは省略している。

ブロック１に対する１回目のステップＳ１００１〜ステップＳ１００７を適用後、解析候補スタックには、アドレスｍとアドレスｃが積まれ、解析済みブロックリストにはブロック１が登録される。

次に、解析候補スタックからアドレスｃが取り出され、アドレスｃを開始アドレスとするブロック２に対して、２回目の解析が行われる。ブロック２は、解析情報記憶部１１４に登録すべきブロックであるため、登録ブロックはブロック２となり、解析候補スタックにはブロック２の分岐先アドレスｍ，ｉ，ｅが登録され、解析済みブロックリストにはブロック１，２が登録される。

同様に、ｅを開始アドレスとするブロック３の解析後は、解析候補スタックにｍ，ｉ，ｇが積まれる。ブロック４の解析後は、分岐先のアドレスは既に解析済みブロックリストに存在するブロック３に含まれるため、解析候補スタックには積まれない。同様の手順を繰り返すことで、図１３に示す解析情報が生成される。

（動的解析処理の処理フロー）
次に、動的解析処理、つまり第２解析部１２０の動作について説明する。上述したように、第２解析部１２０は、コード実行部２１０から提示される解析対象ブロックアドレスを元に、プログラムコードから解析すべきプログラムコードを特定し、解析情報を元に当該プログラムコードが検出対象であるか否かを判定する。

さらに、第２解析部１２０は、検出対象コードを検出すると共に、検出された検出対象コードに対してフックコードを追加する。以下では、第２解析部１２０が一回毎に出力する動的解析済みコードを、第１解析部１１０の動作説明時と同様にブロックと呼ぶ。

図１４は、第２解析部１２０の動作を示すフローチャートである。

ステップＳ３０００において、第２解析部１２０は、プログラムコードの先頭ブロックの開始アドレス（ｍａｉｎ関数の先頭ブロックの開始アドレス）を取得する。なお、解析開始時にはプログラムコードの先頭ブロックの開始アドレスが取得されるが、その後の処理ではコード実行部２１０によって解析対象ブロックの開始アドレスが与えられる。

ステップＳ３００１において、第２解析部１２０は、ステップＳ３０００で取得された開始アドレスが、解析情報に登録されたいずれかの登録ブロックに含まれるか否かを判定する。開始アドレスが登録ブロックに含まれる場合、ステップＳ３０９９に進む。一方、開始アドレスが登録ブロックに含まれない場合、ステップＳ３００２に進む。

ステップＳ３０９９において、第２解析部１２０は、当該解析対象ブロックの動的解析が不要であると判断し、当該解析対象ブロックを動的解析済みコードとしてそのまま出力する。

ステップＳ３００２において、第２解析部１２０は、当該解析対象ブロックがキャッシュに存在するか否かを判定する。当該解析対象ブロックがキャッシュに存在する場合、ステップＳ３１９９に進む。当該解析対象ブロックがキャッシュに存在しない場合、ステップＳ３００３に進む。

なお、キャッシュの検索方法は、キャッシュの構成方法により異なる。キャッシュが開始アドレス及び終了アドレスを含む場合、解析情報に対する検索と同様に、解析対象ブロックの開始アドレス及び終了アドレスで検索すればよい。

ステップＳ３１９９において、第２解析部１２０は、キャッシュに存在する動的解析済みコードを解析対象ブロックの動的解析済みコードとして出力する。

ステップＳ３００３において、第２解析部１２０は、解析対象ブロックの終了アドレスを特定し、解析対象ブロックをプログラムコード記憶部から読み込む。なお、ステップＳ３００３では、図１０のステップＳ２００１と同様に、当該ブロックから検出された無条件分岐命令のアドレスが、解析情報の終了アドレスに一致するか再び検査する。一致する場合には、当該ブロックの終了アドレスは一致したブロックの開始アドレスの１つ前となる。一致しない場合には、当該無条件分岐命令のアドレスが当該ブロックの終了アドレスとなる。

ステップＳ３００４において、第２解析部１２０は、ステップＳ３００３で読み込んだ解析対象ブロックをコンパイル処理する。ステップＳ３００４では、当該ブロックから検出された検出対象コードへフックコードが追加される。

（動的解析処理の具体例）
図１４のステップＳ３０９９、ステップＳ３１９９及びステップＳ３２９９で停止した場合の動作概要図を図１５〜図１７に示す。図１５〜図１７では、上段にプログラムコードのメモリ空間を示し、中段にコード検出装置１００（第２解析部１２０）の実行メモリ空間を示し、下段にコード実行装置２００の実行メモリ空間を示している。

図１５では、第２解析部１２０は、ブロックを読み込み、解析情報を元に当該ブロックが非解析対象のブロックであると判定し、当該ブロックをそのまま出力する（ステップＳ３００１、ステップＳ３０９９）。この場合、当該ブロックにはフックコードが追加されないため、コード制御部２２０が呼出されることはない。

図１６では、第２解析部１２０は、ブロックを読み込み、解析情報を元に当該ブロックが解析対象ブロックであると判定する（ステップＳ３００１）。第２解析部１２０は、キャッシュ記憶部１２６を検索し（ステップＳ３００２）、キャッシュ記憶部１２６から動的解析済みブロックを出力する（ステップＳ３１９９）。当該ブロックにフックコードが追加されている場合には、当該ブロックの実行時にコード制御部２２０が呼出される。

図１７では、第２解析部１２０は、各ブロックを読み込み、解析情報を元に当該ブロックが解析対象ブロックであると判定する（ステップＳ３００１）。第２解析部１２０は、キャッシュ記憶部１２６を検索する（ステップＳ３００２）。しかし、当該ブロックがキャッシュ記憶部１２６に存在しないために、プログラムコードからブロックを読み込み（ステップＳ３００３）、読み込んだブロックをコンパイル処理し（ステップＳ３００４）、コンパイル済みのブロックを出力する（ステップＳ３２９９）。

最後に、プログラム実行時には確実に分岐先を特定可能であるため、コード実行装置２００は、図１５〜図１７のいずれの場合においても、次に実行される解析対象ブロックアドレスを第２解析部１２０に通知する。

（作用・効果）
本実施形態によれば、第１解析部１１０は、静的解析によって、第２解析部１２０が解析すべきメモリ領域を指定する。プログラムコードの動的解析を行う第２解析部１２０は、静的解析の結果に応じて、プログラムコードの一部に対して検出対象コードの検出処理を行う。このため、プログラムコードの動的解析を行う第２解析部１２０の処理負荷が削減され、システム全体の処理速度が向上する。

また、本実施形態に係るコード検出方法と、キャッシュ記憶部１２６を用いた手法とを併用することで、動的解析処理に要するコストを大幅に削減可能となる。また、解析対象ブロックが解析情報に存在した場合とキャッシュに存在した場合の両方において、フックコードを追加するためのコンパイル処理を省略可能である。このため、両方式を用いたインタプリンタ実行は、既存技術と比較して、動的解析処理コストの削減効果が大きい。さらに、キャッシュ記憶部１２６には、解析済みの解析対象ブロックのみが記憶されるので、携帯型デバイス等のメモリ容量が小さい場合に好適である。

＜第２実施形態＞
本実施形態では、第１解析部１１０及び第２解析部１２０が検出する検出対象コードが、特定のコードへの制御移動命令（分岐命令）である場合について説明する。

ここで、検出対象コードが特定のコードへの制御移動命令（分岐命令）である場合としては、例えば特定の関数の呼出しが該当する。すなわち、検出対象コードがプログラムコード中の特定のアドレスへ分岐する分岐命令であり、分岐先が予め定められた特定の関数ということになる。特定の関数とは、例えば、プログラムコードからの呼出が許可されない関数である。

本実施形態では、制御情報記憶部４００は、検出対象コードを特定する情報及びフックコードを特定する情報に加えて、特定の関数のシンボル名を記憶する。具体的には、制御情報記憶部４００は、検出対象コードと特定の関数のシンボル名とを対応付けて記憶する。

なお、分岐命令には、分岐先のアドレスが直接指定される分岐命令と、分岐先のアドレスがレジスタで指定される分岐命令とがある。分岐先のアドレスが直接指定される分岐命令では、分岐先のアドレスが、プログラムコードが有するシンボルテーブルと比較される。

また、分岐先のアドレスがレジスタで指定される場合、プログラムコードを解析することで、レジスタへアドレスがコピーされるコードが検出され、当該アドレスがシンボルテーブルと比較される。分岐先のアドレスがレジスタで指定される場合の例としては、例えば次のような分岐命令が該当する。

ＭＯＶ ０ｘ１２ ｌｒ
Ｂ ｌｒ
この分岐命令では、分岐命令（Ｂ）の分岐先であるｌｒレジスタの値が、ＭＯＶ命令から導出される。この場合、ｌｒレジスタの値は、アドレス０ｘ１２である。

（検出対象コードの検出処理フロー）
次に、検出対象コードの検出処理フロー、具体的には、図１０のステップＳ２００３の詳細について説明する。図１８は、検出対象コードの検出処理フローを示すフローチャートである。

ステップＳ４００１において、第１解析部１１０は、読み込んだコードが分岐命令であるか否かを判定する。読み込んだコードが分岐命令である場合、ステップＳ４００２に進む。一方、読み込んだコードが分岐命令でない場合、ステップＳ４０９９に進む。

ステップＳ４０９９において、第１解析部１１０は、読み込んだコードが検出対象コードではないと判定する。

ステップＳ４００２において、第１解析部１１０は、分岐命令の分岐先アドレスから呼出し対象の関数のシンボル名を取得する。

ステップＳ４００３において、第１解析部１１０は、ステップＳ４００２で取得されたシンボル名が、制御情報記憶部４００に記憶されているシンボル名と一致するか否かを判定する。一致する場合はステップＳ４１９９に進み、一致しない場合はステップＳ４０９９に進む。

ステップＳ４１９９において、第１解析部１１０は、読み込んだコードが検出対象コードであると判定する。

なお、図１８で説明した検出対象コード検出処理は、第１解析部１１０だけでなく、第２解析部１２０においても実行される。

（作用・効果）
本実施形態によれば、検出対象コードがプログラムコード中の呼出が許可されない関数を呼出す分岐命令である場合に、当該制御移動命令が確実に検出される。したがって、プログラム実行時に、呼出が許可されない関数を呼出す分岐命令が実行されないように制御することで、特定の関数や共有ライブラリが呼出されないようにすることができる。

＜第３実施形態＞
（プログラム解析システムの構成）
本実施形態では、第１解析部１１０が、検出対象コードにフックコードを追加する構成について説明する。図１９は、本実施形態に係るプログラム解析システムの構成を示す機能ブロック図である。

図１９に示すように、第１解析部１１０は、フックコード追加部１１５及び静的解析済みコード記憶部１１６を備える点で、図３とは異なる。

フックコード追加部１１５は、プログラムコード中の検出対象コードに対してフックコードを追加する。

解析情報記憶部１１４には、検出対象コードを含まないブロックに加えて、フックコードが追加されたブロックを登録ブロックとして登録する。

静的解析済みコード記憶部１１６は、フックコードの追加された静的解析済みコードを記憶する。

特定部１２１は、解析情報記憶部１１４に記憶された解析情報に基づき、静的解析済みコード記憶部１１６に記憶された静的解析済みコードから解析対象ブロックを特定する。その他の構成については、上述した第１実施形態と同様である。

なお、プログラムコードが組込み機器向けに開発されたものである場合、プログラムコードのサイズがシステムの許容する最大サイズ程度であることが多い。このため、プログラムコードのサイズがシステムの許容する最大のサイズ程度である場合には、静的解析時にフックコードを追加しないようにしてもよい。

また、プログラムコードのサイズがシステムの許容する最大サイズ程度である場合には、静的解析時にフックコードを追加しないことにより、静的解析済みコードのサイズがシステムの許容する最大のサイズを超えることが防止される。

（ブロック解析処理の処理フロー）
次に、本実施形態に係るブロック解析処理の処理フローについて説明する。図２０は、本実施形態に係るブロック解析処理の処理フローを示すフローチャートである。図２０に示すように、ステップＳ２００６が追加されている点で、図１０とは異なる。

ステップＳ２００６では、当該コードが検出対象コードである場合に、第１解析部１１０は、プログラム制御情報を参照することでフックコードを追加する。

また、ステップＳ２００５では、当該ブロックに検出対象コードが検出された場合、及び当該ブロックに検出対象コードが検出されなかった場合の両方で、当該ブロックは解析情報に登録される。

（作用・効果）
本実施形態によれば、解析情報記憶部１１４は、検出対象コードを含まないブロックに加えて、フックコードが追加されたブロックを登録する。特定部１２１は、解析情報記憶部１１４に記憶された解析情報に基づき、静的解析済みコード記憶部１１６に記憶された静的解析済みコードから解析対象領域を特定する。

したがって、静的解析時にフックコードの追加されたブロックについては動的解析（コンパイル）の対象外とすることで、動的解析時におけるコンパイル処理回数が削減される。

＜第３実施形態の変更例＞
上述した第３実施形態では、プログラムコードのサイズがシステムの許容する最大のサイズ程度である場合には、静的解析時にフックコードを追加しない一例について説明した。静的解析済みコードにフックコードを追加する場合、コードサイズが増加する。

そこで、本変更例では、検出対象コードが分岐命令である場合に、フックコードを含むフック専用関数を使用する構成について説明する。フック専用関数は、例えば動的ライブラリ関数として、プログラム実行時にプログラムコードと連結される。

第１解析部１１０は、ブロックから検出対象コードを検出する。その際、プログラムコードのサイズ制限が発生していた場合、第１解析部１１０は、検出対象コードの分岐先を書き換える。つまり、検出対象コードが分岐命令である場合に、当該分岐命令の分岐先をフック専用関数へ書き換えることとなる。

一方で、フック専用関数は、図２１に示すように、フックコード及び分岐命令を含む。これにより、検出対象コード（分岐命令）から呼出されたフック専用関数は、フックコードの実行後に本来の分岐先である特定の関数へ分岐し、当該特定の関数が実行された後は元のブロックへとリターンされる。なお、フック専用関数は、検出対象コード毎に用意される。

図２１では、矢印が分岐元と分岐先を表し、点線がフックコードを伴わない通常の分岐を表し、実線がフックコードを伴う分岐を表している。元のコードにおいて、関数呼出しにより、検出対象コードから特定のコードへ分岐していたとする。この場合、検出対象コードからアドレスｘに分岐し、特定のコードの実行後、アドレスｙから元のブロックに分岐する。

第１解析部１１０は、検出対象コードの分岐先を書き換え、分岐先をフック専用関数の開始アドレスｚとする。フック専用関数では、フックコードの後に特定のコードへの分岐命令が埋め込まれている。特定のコードの実行後は、元のブロックへ戻る。

フック専用関数により、特定のコードが実行される前に必ずフックコードが実行され、検出対象コードの実行を制御することが可能となる。なお、フック専用関数を使用することで、プログラム実行時の処理負荷が増加するので、コードサイズの問題が生じた場合に本変更例を適用することが好ましい。

＜第４実施形態＞
本実施形態では、制御情報記憶部４００が記憶するプログラム制御情報が更新される場合に対応可能な構成について説明する。プログラム制御情報に含まれる検出対象コードが更新された場合、解析情報記憶部１１４が記憶する解析情報も更新される必要がある。

第２解析部１２０が動的解析を実行中にプログラム制御情報が更新された場合、動的解析を停止し、解析情報の再生成が完了するまで動的解析が中断される。このため、解析情報の再生成は、できるだけ短時間で行う必要がある。

（プログラム解析システムの構成）
図２２は、本実施形態に係るプログラム解析システムの構成を示す機能ブロック図である。図２２に示すように、制御情報記憶部４００は候補コードを記憶する点で、図３とは異なる。候補コードは、プログラム制御除法の更新により、検出対象コードとなる可能性のあるコードである。

例えば、特定のユーザがプログラムを利用する場合にのみプログラムの機能制限を行う場合、当該機能を呼出すコードは、候補コードとなり、当該プログラムが利用される場合には検出対象コードとなる。プログラム制御情報の更新により検出対象コードが更新される場合でも、新たな検出対象コードは、候補コードの中から選択される。

また、第１解析部１１０は、再生成情報記憶部１１７を備える点で、図３とは異なる。本実施形態に係る解析情報生成部１１３は、解析情報に加えて、再生成情報を生成する。解析情報生成部１１３は、候補コードを含むブロックを登録ブロックとする。再生成情報は、解析情報と同様に、ブロックＩＤ、開始アドレス及び終了アドレスを含む。

プログラム制御情報の更新により、解析情報を更新する際、第１解析部１１０（具体的には、第１検出部１１２）によって解析しなければならないブロックは、再生成情報記憶部１１７に登録されたブロックのみとなる。具体的には、再生成情報に登録されたすべてのブロックに対してブロック解析処理を実行し、解析情報を更新する。

本実施形態に係るブロック解析処理では、ブロックを次の３つに分類する。

（１）検出対象コードを含むブロック
（２）検出対象コードではない候補コードのみを含むブロック
（３）候補コードを含まないブロック
上記（１）に分類されるブロックは、再生成情報にのみ登録されるべきブロックである。上記（２）に分類されるブロックは、解析情報及び再生成情報の両方に登録されるべきブロックである。上記（３）に分類されるブロックは、解析情報にのみ登録されるべきブロックである。

（再生成情報の生成方法）
次に、ブロック解析処理における再生成情報の生成方法について説明する。図２３は、ブロック解析処理における再生成情報の生成方法を示すフローチャートである。図２３では、上述した第１実施形態に係る処理フローから、新たにステップＳ２００７〜ステップＳ２０１０が追加されている。

ステップＳ２００７において、第１解析部１１０は、検出対象コードを含むブロックを再生成情報に登録する。

ステップＳ２００８において、第１解析部１１０は、当該コードが検出対象コードではない場合に、当該コードが候補コードに該当するか否かを判定する。当該コードが候補コードに該当しない場合、ステップＳ２００４に進む。一方、当該コードが候補コードに該当する場合は、ステップＳ２００９に進み、当該コードが再生成情報に既に登録されているか否かが判定される。当該コードが再生成情報に登録されていなければ、ステップＳ２０１０において、当該ブロックが再生成情報に登録される。
なお、ステップＳ２００９が必要な理由は、当該ブロックに複数の候補コードが存在した場合に、当該ブロックの解析処理中は複数回ステップＳ２０１０に進む可能性があり、再生成情報の重複登録が発生する可能性があるためである。

（作用・効果）
本実施形態によれば、第１解析部１１０は、検出対象コードがいずれかの候補コードに変更された場合に、再生成情報に登録されたブロックから新たな検出対象コードを検出する。したがって、再生成情報を予め生成しておくことで、プログラム制御情報が更新されてもプログラムコード全体を再解析する必要が無くなる。

＜第５実施形態＞
本実施形態では、図１４のステップＳ３００１の処理、すなわち、解析対象ブロックの登録ブロック内検索処理に着目する。解析対象ブロックは、コード実行装置２００が出力する解析対象ブロックアドレスにより決定される。この解析対象ブロックアドレスは、プログラムカウンタが指すアドレス、すなわち次に実行されるべきコードのアドレスである。

一般的に、プログラム内で実行されるコードは局所性を持ち、プログラム全体のコードが一様に実行されるわけではなく、一部のコードが集中的に実行されることが多い。従って、出力される解析対象ブロックアドレスにも局所性が存在し、一部のアドレスが多く該当する可能性が高い。

一部のコードが集中的に実行される場合、解析対象ブロック（解析情報記憶部１１４）においても同様に、一部のブロックが繰り返し検索されることとなり、検索結果として、同じ登録ブロックが頻繁にアクセスされることとなる。

（プログラム解析システムの構成）
図２４は、本実施形態に係るプログラム解析システムの構成図である。図２４に示すように、第２解析部１２０は、履歴情報記憶部１２７を備える点で、図３とは異なっている。履歴情報記憶部１２７は、図２５に示すように、登録ブロック（検出対象コードを含まないブロック）のブロックＩＤと、当該登録ブロックの開始アドレスと、当該登録ブロックの終了アドレスと、当該登録ブロックがコード実行部２１０によって実行された回数とを対応付けた履歴情報を記憶する。

履歴情報記憶部１２７に記憶される履歴情報は、第１解析部１１０の解析情報生成部１１３によって利用される。解析情報生成部１１３は、履歴情報に基づき、解析情報記憶部１１４に記憶されている解析情報を更新する。

具体的には、解析情報生成部１１３は、特定部１２１によってアクセスされる頻度の高い登録ブロックが、より短い時間で検索されるように解析情報記憶部１１４のデータ構造を変更する。こうすることで、ステップＳ３００１の処理、すなわち、特定部１２１が解析情報記憶部１１４中の登録ブロックを検索する際に実行される処理が高速化される。

例えば、初回のプログラム実行時において、特定部１２１は、解析情報記憶部１１４に記憶される解析情報を利用して、プログラムコード中の解析対象ブロック（登録ブロック）を特定するとともに、コード実行部２１０によって実行された登録ブロックを記録した履歴情報を生成する。

プログラムの実行終了後、解析情報生成部１１３は、生成された履歴情報を用いて、解析情報記憶部１１４に記憶される解析情報を更新する。例えば、解析情報記憶部１１４に記憶される各データが、エントリの上位から線形検索される場合、解析情報記憶部１１４は、履歴情報により、実行回数が多い登録ブロックをより上位に配置する。図２５の例では、ブロックＩＤ２のブロックが、ブロックＩＤ１のブロックよりも上位に配置される。

尚、データ検索に利用されるデータ構造は、ハッシュテーブルを利用したインデックスを持つのが一般的である。この場合、インデックスにより検索されるデータは、Ｏ（１）で探索可能であり、理想的には上述したような線形検索は発生しない。

しかし、実際には同一インデックスに射影される複数のデータが存在するために、一度インデックスによりデータを絞った後は、線形検索が実行される。そのため、ハッシュテーブルを利用して解析情報を実現した場合でも、履歴情報を利用した解析情報の更新は有用であると言える。

（作用・効果）
本実施形態によれば、初回のプログラム実行結果に応じて、解析情報が更新される。第２解析部は、次回のプログラム実行時においては、更新された解析情報を利用して、プログラムコードが解析される。これにより、初回のプログラム実行と比較して、次回のプログラム実行時においては、短時間でプログラムの解析を行うことが可能となる。

＜第６実施形態＞
本実施形態では、図７のステップＳ１００３の処理、すなわち、解析したブロックの分岐先アドレスを全て取得する処理に注目する。このような処理を実現するためには、当該ブロックに含まれる分岐命令を検出し、分岐先を取得する必要がある。

ここで、実行可能形式のプログラムコードを解析対象とした場合、分岐命令は、大きく直接分岐命令と間接分岐命令に分けられる。直接分岐命令は、命令中に分岐先アドレスが明記されているため、分岐先の取得が容易である。

一方で、間接分岐命令は、プログラムカウンタを利用した分岐である。間接分岐命令におけるプログラムカウンタの値は、当該命令とは別の命令により決定されており、プログラム実行時以外での値の特定は困難である。そのため、ステップＳ１００３において、解析対象ブロックが間接分岐命令を含む場合、第１解析部１１０は、間接分岐命令の分岐先の取得が非常に困難である。

一方で、間接分岐命令の分岐先は、プログラム実行時には容易に特定可能である。なぜなら、プログラム実行時には、プログラムカウンタに分岐先の値が代入されるので、当該分岐命令を解析するだけで、分岐先を特定可能となるためである。

そこで、本実施形態では、ブロックに間接分岐命令が存在した場合に、第２解析部１２０の第２検出部１２２は、プログラム実行時において間接分岐命令の分岐先を記録する。

（プログラム解析システムの構成）
図２６は、本実施形態に係るプログラム解析システムの構成図である。図２６に示す通り、第２解析部１２０は、分岐先情報記憶部１２８を備える点で、図３とは異なっている。

第２解析部１２０の第２検出部１２２は、プログラム実行時に、間接分岐命令を検出し、分岐元のブロックを特定可能な情報（当該ブロックＩＤ、当該ブロックアドレス）と、当該分岐命令による分岐先とを分岐先情報として分岐先情報記憶部１２８に格納する。

上記述べた通り、間接分岐命令が検出できれば、プログラム実行時の分岐先の特定は容易である。また、アーキテクチャ依存ではあるが、間接分岐命令は高々数種類に限定されるため、第２検出部１２２による間接分岐命令の検出は容易である。例えば、ＡＲＭ^ＴＭアーキテクチャにおけるアセンブラコードの場合の間接分岐命令は、例えば、図２７に示す通りとなる。

（分岐先検出処理）
次に、本実施形態に係る分岐先検出処理について説明する。図２８は、分岐先検出処理の概要を示す図である。図２８において、ブロック０は、間接分岐命令によりブロック１に分岐する。分岐先情報がない場合、このブロック０からの分岐先であるブロック１のアドレスを特定することは非常に困難である。このため、図２８（ａ）に示すように、ブロック１〜３において検出漏れが生じる。

一方、分岐先情報を用いることで、ブロック０からの分岐先であるブロック１のアドレスが特定され、ブロック０を解析後にブロック１が特定される。さらに、図２８（ｂ）に示すように、ブロック１の分岐先のプログラムコード（ブロック２，３）が解析可能となる。

なお、図２８に示すように、分岐先情報記憶部１２８は、分岐先のブロックＩＤと、分岐元のブロックＩＤと、分岐先アドレスとを対応付けた分岐先情報を記憶する。

図２９は、解析情報生成処理の処理フローを示すフローチャートである。図２９では、ステップＳ１０１１が追加されている点で、図７とは異なっている。ステップＳ１０１１及びステップＳ１００３では、第１検出部１１２は、分岐先情報を用いて、分岐先アドレスをすべて取得する。

（作用・効果）
本実施形態によれば、第１検出部１２２において検出対象コードの検出漏れが存在していた場合に、第１検出部１２２は、分岐先情報を利用することで、検出漏れが生じていた検出対象コードが検出可能となる。

＜その他の実施形態＞
上記のように、本発明は第１〜第６実施形態によって記載したが、この開示の一部をなす論述及び図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施形態、実施例及び運用技術が明らかとなる。

上述した実施形態では、検出対象コードが分岐命令である場合について説明したが、検出対象コードが分岐命令以外の命令であってもよい。

また、上述した実施形態では、コード実行装置２００を備えるプログラム解析システムについて説明したが、本発明は、コード実行装置を備えないプログラム解析システムにも応用可能である。

このように本発明は、ここでは記載していない様々な実施形態等を包含するということを理解すべきである。したがって、本発明はこの開示から妥当な特許請求の範囲の発明特定事項によってのみ限定されるものである。

本発明の背景技術を説明するための図である（その１）。 本発明の背景技術を説明するための図である（その２）。 本発明の第１実施形態に係るプログラム解析システムの機能ブロック図である。 本発明の第１実施形態に係る解析情報の一例を示す図である。 本発明の第１実施形態に係る解析情報生成処理を説明するための図である（その１）。 本発明の第１実施形態に係る解析情報生成処理を説明するための図である（その２）。 本発明の第１実施形態に係る解析情報生成処理の処理フローを示すフローチャートである。 本発明の第１実施形態に係る解析情報生成処理を説明するための図である（その３）。 本発明の第１実施形態に係る解析情報生成処理を説明するための図である（その４）。 本発明の第１実施形態に係るブロック解析処理の処理フローを示すフローチャートである。 本発明の第１実施形態に係るブロック解析処理を説明するための図である（その１）。 本発明の第１実施形態に係るブロック解析処理を説明するための図である（その２）。 本発明の第１実施形態に係るブロック解析処理を説明するための図である（その３）。 本発明の第１実施形態に係る動的解析処理の処理フローを示すフローチャートである。 本発明の第１実施形態に係る動的解析処理の具体例を示す図である（その１）。 本発明の第１実施形態に係る動的解析処理の具体例を示す図である（その２）。 本発明の第１実施形態に係る動的解析処理の具体例を示す図である（その３）。 本発明の第２実施形態に係る検出対象コードの検出処理フローを示すフローチャートである。 本発明の第３実施形態に係るプログラム解析システムの構成を示す機能ブロック図である。 本発明の第３実施形態に係るブロック解析処理の処理フローを示すフローチャートである。 本発明の第３実施形態に係るブロック解析処理を説明するための図である。 本発明の第４実施形態に係るプログラム解析システムの構成を示す機能ブロック図である。 本発明の第４実施形態に係るブロック解析処理における再生成情報の生成方法を示すフローチャートである。 本発明の第５実施形態に係るプログラム解析システムの構成を示す機能ブロック図である。 本発明の第５実施形態に係る履歴情報の一例を示す図である。 本発明の第６実施形態に係るプログラム解析システムの構成を示す機能ブロック図である。 間接分岐命令の一例を示す図である。 本発明の第６実施形態に係る分岐先検出処理の概要を示す図である。 本発明の第６実施形態に係る解析情報生成処理の処理フローを示すフローチャートである。

符号の説明

１００…コード検出装置、１１０…第１解析部、１１１…ブロック生成部、１１２…第１検出部、１１３…解析情報生成部、１１４…解析情報記憶部、１１５…フックコード追加部、１１６…静的解析済みコード記憶部、１１７…再生成情報記憶部、１２０…第２解析部、１２１…特定部、１２２…第２検出部、１２３…コード出力部、１２４…コンパイル部、１２５…フックコード追加部、１２６…キャッシュ記憶部、１２７…履歴情報記憶部、１２８…分岐先情報記憶部、２００…コード実行装置、２１０…コード実行部、２２０…コード制御部、３００…プログラムコード記憶部、３２０…動的解析済みコード記憶部、４００…制御情報記憶部、８００…制御ポリシー記憶部

Claims (17)

1. 複数のコードを含むプログラムコードを解析することで検出対象コードを検出するコード検出装置であって、
   前記プログラムコードの実行前に、前記プログラムコードを解析する第１解析部と、
   前記プログラムコードの実行中に、前記第１解析部による解析結果を用いて前記プログラムコードを解析する第２解析部とを備え、
   前記第１解析部は、
   前記プログラムコードから前記検出対象コードを検出する第１検出部と、
   前記第１検出部による検出結果に基づき、前記プログラムコードのうち前記第２解析部が解析対象としない領域である非解析対象領域を特定するための解析情報を生成する解析情報生成部とを備え、
   前記第２解析部は、
   前記解析情報を参照し、前記解析情報が示す非解析対象領域を除いた領域を前記プログラムコード中の前記解析対象領域として特定する特定部と、
   前記特定部によって特定された前記解析対象領域から前記検出対象コードを検出する第２検出部とを備え、
   前記第１解析部が生成する前記解析情報は、前記プログラムコードのうち前記検出対象コードを含まない領域を非解析対象領域として特定する情報を含み、
   前記第２解析部は、前記プログラムコードの実行中に、前記プログラムコードを実行するコード実行部によって与えられる次に実行されるべきプログラムコードのアドレスに基づいて、前記プログラムコードのうち解析すべきプログラムコードを特定し、前記解析情報を元に当該プログラムコードが解析対象領域であるか否かを判定することを特徴とするコード検出装置。
2. 前記検出対象コードの実行を制御するためのコードであるフックコードを含むプログラム制御情報を記憶する制御情報記憶部をさらに備え、
   前記第２解析部は、前記解析対象領域から検出された前記検出対象コードに前記フックコードを追加することを特徴とする請求項１に記載のコード検出装置。
3. 前記検出対象コードの実行を制御するためのコードであるフックコードを含むプログラム制御情報を記憶する制御情報記憶部をさらに備え、
   前記第１解析部は、前記プログラムコードから検出された前記検出対象コードに前記フックコードを追加し、
   前記特定部は、前記第１解析部により前記フックコードの追加されていない領域を前記解析対象領域として特定することを特徴とする請求項１に記載のコード検出装置。
4. 前記第１解析部は、前記プログラムコードのサイズまたは処理負荷に応じて、前記プログラムコードから検出された前記検出対象コードに前記フックコードを追加するか否かを判定することを特徴とする請求項３に記載のコード検出装置。
5. 前記第１解析部は、前記フックコードを含むフック専用関数へ分岐する分岐命令を、前記フックコードとして前記検出対象コードに追加することを特徴とする請求項３に記載のコード検出装置。
6. 前記検出対象コードを特定する情報を含むプログラム制御情報を記憶する制御情報記憶部をさらに備え、
   前記第１検出部は、前記プログラム制御情報が更新された場合、更新後の検出対象コードを特定する情報に基づいて前記プログラムコードから前記更新後の検出対象コードを検出し、
   前記解析情報生成部は、前記第１検出部による前記更新後の検出対象コードの検出結果に基づき、前記解析情報を更新することを特徴とする請求項１に記載のコード検出装置。
7. 前記検出対象コードを特定する情報と、前記検出対象コードの変更先候補のコードである候補コードを特定する情報を含むプログラム制御情報を記憶する制御情報記憶部をさらに備え、
   前記第１検出部は、前記プログラム制御情報に基づき、前記プログラムコードから前記検出対象コード及び前記候補コードを検出し、
   前記解析情報生成部は、前記第１検出部による検出結果に基づき、前記プログラムコードのうち前記候補コードを含む領域を特定する再生成情報を生成し、
   前記第１検出部は、前記プログラム制御情報中の前記検出対象コードを特定する情報が変更された場合、前記再生成情報によって特定される領域から、変更された検出対象コードを検出することを特徴とする請求項１に記載のコード検出装置。
8. 前記検出対象コードは、前記プログラムコード中の特定のコードを呼出す制御移動命令であり、
   前記第１検出部及び前記第２検出部は、
   前記プログラムコードから制御移動命令を検出した場合、検出された制御移動命令の呼出先コードが前記特定のコードであるか否かを判定し、
   前記検出された制御移動命令の呼出先コードが前記特定のコードである場合、前記検出された制御移動命令が前記検出対象コードであると判定することを特徴とする請求項１に記載のコード検出装置。
9. 前記第２解析部は、前記解析対象領域から検出された前記検出対象コードに前記フックコードを追加すると共に、前記解析対象領域をコンパイル処理し、コンパイル処理後の前記解析対象領域である解析済みコードを記憶するキャッシュ記憶部をさらに備え、
   前記第２検出部は、前記解析対象領域から前記検出対象コードが検出された場合であって、前記検出対象コードを含む前記解析対象領域に対応する解析済みコードが前記キャッシュ記憶部に記憶されている場合、前記コンパイル処理を省略し、前記解析済みコードを出力することを特徴とする請求項１に記載のコード検出装置。
10. 前記非解析対象領域を特定する情報は、前記非解析対象領域の開始アドレスを含むことを特徴とする請求項９に記載のコード検出装置。
11. 前記第１解析部は、前記プログラムコードを２つの分岐命令で挟まれた領域毎に分割し、分割された領域毎に前記検出対象コードの検出処理を行うことで前記非解析対象領域を検出することを特徴とする請求項１に記載のコード検出装置。
12. 前記第１解析部は、前記非解析対象領域を特定する情報を含む前記解析情報を記憶する解析情報記憶部をさらに備え、
    前記第２解析部は、前記非解析対象領域を特定する情報と、前記非解析対象領域が実行された回数とを対応付けた履歴情報を記憶する履歴情報記憶部をさらに備え、
    前記解析情報生成部は、前記履歴情報記憶部に記憶されている前記履歴情報に基づき、前記解析情報記憶部に登録されているとともに、前記特定部によってアクセスされる頻度の高い登録領域が、より短い時間で検索されるように前記解析情報記憶部のデータ構造を変更することによって、前記解析情報記憶部に記憶されている前記解析情報を更新することを特徴とする請求項１に記載のコード検出装置。
13. 前記履歴情報記憶部に記憶される前記非解析対象領域を特定する情報は、少なくとも前記非解析対象領域の開始アドレスを含むことを特徴とする請求項１２に記載のコード検出装置。
14. 前記特定部は、前記解析情報記憶部中の上位から下位へ前記非解析対象領域を特定する情報を参照することで、前記次に実行されるプログラムコードの領域が前記非解析対象領域であるか否かを特定し、
    前記解析情報生成部は、
    前記履歴情報において一定回数以上に対応する前記非解析対象領域を特定する情報を、前記解析情報記憶部中の上位に設定し、
    前記履歴情報において一定回数未満に対応する前記非解析対象領域を特定する情報を、前記解析情報記憶部中の下位に設定することを特徴とする請求項１２に記載のコード検出装置。
15. 前記検出対象コードは、分岐命令であり、
    前記第２解析部は、コンパイル処理後の前記解析対象領域である解析済みコードに所定の分岐命令が含まれる場合に、前記所定の分岐命令を特定する情報、及び前記所定の分岐命令の分岐先を分岐先情報として記憶する分岐先情報記憶部をさらに備え、
    前記第１検出部は、前記分岐先情報記憶部に記憶される前記分岐先情報を参照し、前記分岐先情報を用いて前記検出対象コードを検出することを特徴とする請求項１に記載のコード検出装置。
16. 前記所定の分岐命令は、他の命令の実行結果に応じて分岐先が定まる間接分岐命令であり、
    前記分岐先情報記憶部は、前記解析済みコードが実行される際に前記分岐先情報を記憶することを特徴とする請求項１５に記載のコード検出装置。
17. 複数のコードを含むプログラムコードを解析することで検出対象コードを検出するコード検出方法であって、
    前記プログラムコードの実行前に、前記プログラムコードを解析する第１ステップと、
    前記プログラムコードの実行中に、前記第１解析ステップによる解析結果を用いて前記プログラムコードを解析する第２ステップとを備え、
    前記第１ステップは、
    前記プログラムコードから前記検出対象コードを検出する第１検出ステップと、
    前記第１検出ステップによる検出結果に基づき、前記プログラムコードのうち前記第２ステップが解析対象としない領域である非解析対象領域を特定するための解析情報を生成する解析情報生成ステップとを備え、
    前記第２ステップは、
    前記解析情報を参照し、前記解析情報が示す非解析対象領域を除いた領域を前記プログラムコード中の前記解析対象領域として特定する特定ステップと、
    前記特定ステップによって特定された前記解析対象領域から前記検出対象コードを検出する第２検出ステップとを備え、
    前記第１ステップが生成する前記解析情報は、前記プログラムコードのうち前記検出対象コードを含まない領域を非解析対象領域として特定する情報を含み、
    前記第２ステップは、前記プログラムコードの実行中に与えられる次に実行されるべきプログラムコードのアドレスに基づいて、前記プログラムコードのうち解析すべきプログラムコードを特定し、前記解析情報を元に当該プログラムコードが解析対象領域であるか否かを判定することを特徴とするコード検出方法。

Images