(57)【要約】課題  オブジェクト指向型言語で記述されたプログラムを対象に、実行時に生成される特定のオブジェクトに対して発行されるメソッド呼出のパターンが与えられたパターン定義の規則に従うか否かをプログラム解析により検査する。解決手段  オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査システムは、プログラムのプログラム情報に記録された抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係する抽象オブジェクトを抽出する抽出部と、プログラムのコンテキストを考慮したポインタ解析結果を用いて、抽象オブジェクトに対して検査に間係するメソッド呼出を行うメソッド呼出場所を判定する判定部と、関数間に跨った制御フローグラフを作成しデータフロー解析を行ってメソッド呼出パターンがパターン定義に従っているか検査する検査部を含む。【特許請求の範囲】
【請求項１】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査システムであって、
前記プログラムのコンテキストを考慮したポインタ解析結果を用いることにより、検査対象オブジェクトに対して検査に間係するメソッド呼出を行う呼出場所を識別する手段を備える
ことを特徴とするパターン検査システム。
【請求項２】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査システムであって、
前記プログラムのプログラム情報に記録された抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係する抽象オブジェクトを抽出する抽出手段と、
前記プログラムのコンテキストを考慮したポインタ解析結果を用いて、前記抽象オブジェクトに対して検査に間係するメソッド呼出を行うメソッド呼出場所を判定する判定手段と、
関数間に跨った制御フローグラフを作成しデータフロー解析を行って前記メソッド呼出パターンが前記パターン定義に従っているか検査する検査手段
とを備えたことを特徴とするパターン検査システム。
【請求項３】
前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する手段と、
前記プログラムのポインタ解析結果を記憶するポインタ解析結果記憶装置と、
抽象オブジェクトとメソッド呼出場所と関数内制御フローグラフとコールグラフとを記憶するプログラム情報記憶装置とを備えることを特徴とする請求項２に記載のパターン検査システム。
【請求項４】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査システムであって、
前記プログラムのプログラム情報に記録された抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係する抽象オブジェクトを抽出するリソース識別部と、
前記プログラムのコンテキストを考慮したポインタ解析結果を用いて、前記抽象オブジェクトに対して関係するメソッド呼出場所を識別し、展開したコールグラフを生成するコールグラフ展開部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記抽象オブジェクトを参照するか否かを判定する機能を備えた検査用グラフ生成部と、
関数間に跨った制御フローグラフを作成しデータフロー解析を行って前記メソッド呼出パターンが前記パターン定義に従っているか検査するパターン検査部
とを備えたことを特徴とするパターン検査システム。
【請求項５】
前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する手段と、
前記ポインタ解析結果を記憶するポインタ解析結果記憶装置と、
前記抽象オブジェクトとメソッド呼出場所と関数内制御フローグラフとコールグラフとを記憶するプログラム情報記憶装置とを備えることを特徴とする請求項４に記載のパターン検査システム。
【請求項６】
オブジェクト・センシティブなポインタ解析によって得られる前記ポインタ解析結果を利用することを特徴とする請求項１から請求項５の何れか１項に記載のパターン検査システム。
【請求項７】
ＣＦＡ型のポインタ解析による前記ポインタ解析結果を利用することを特徴とする請求項１から請求項５の何れか１項に記載のパターン検査システム。
【請求項８】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査システムであって、
前記プログラムのプログラム情報に記録されたコンテキスト抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係するコンテキスト抽象オブジェクトを抽出するリソース識別部と、
前記プログラムのコンテキストを考慮したポインタ解析結果を用いて、コンテキスト抽象オブジェクトに対して関係するメソッド呼出場所を識別し、展開したコールグラフを生成するコールグラフ展開部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記コンテキスト抽象オブジェクトを参照するか否かを判定する機能を備えた検査用グラフ生成部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記コンテキスト抽象オブジェクトが生成されるか否かを判定し、関数間に跨った制御フローグラフを作成するデータフロー解析を行って前記メソッド呼出パターンが前記パターン定義に従っているか検査するパターン検査部
とを備えたことを特徴とするパターン検査システム。
【請求項９】
参照変数と抽象オブジェクトに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する手段と、
前記ポインタ解析結果を記憶するポインタ解析結果記憶装置と、
コンテキスト抽象オブジェクトとメソッド呼出場所と関数内制御フローグラフとコールグラフとを記憶するプログラム情報記憶装置とを備えることを特徴とする請求項８に記載のパターン検査システム。
【請求項１０】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査装置であって、
前記プログラムのコンテキストを考慮したポインタ解析結果を用いることにより、検査対象オブジェクトに対して検査に間係するメソッド呼出を行う呼出場所を識別する手段を備える
ことを特徴とするパターン検査装置。
【請求項１１】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査装置であって、
前記プログラムのプログラム情報に記録された抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係する抽象オブジェクトを抽出する抽出手段と、
前記プログラムのコンテキストを考慮したポインタ解析結果を用いて、前記抽象オブジェクトに対して検査に間係するメソッド呼出を行うメソッド呼出場所を判定する判定手段と、
関数間に跨った制御フローグラフを作成しデータフロー解析を行って前記メソッド呼出パターンが前記パターン定義に従っているか検査する検査手段
とを備えたことを特徴とするパターン検査装置。
【請求項１２】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査装置であって、
前記プログラムのプログラム情報に記録された抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係する抽象オブジェクトを抽出するリソース識別部と、
前記抽象オブジェクトに対して関係するメソッド呼出場所を識別し、展開したコールグラフを生成するコールグラフ展開部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記抽象オブジェクトを参照するか否かを判定する機能を備えた検査用グラフ生成部と、
関数間に跨った制御フローグラフを作成しデータフロー解析を行って前記メソッド呼出パターンが前記パターン定義に従っているか検査するパターン検査部
とを備えたことを特徴とするパターン検査装置。
【請求項１３】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査システムであって、
前記プログラムのプログラム情報に記録されたコンテキスト抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係するコンテキスト抽象オブジェクトを抽出するリソース識別部と、
前記プログラムの参照変数と抽象オブジェクトに対してコンテキストを考慮したポインタ解析結果を用いて、コンテキスト抽象オブジェクトに対して関係するメソッド呼出場所を識別し、展開したコールグラフを生成するコールグラフ展開部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記コンテキスト抽象オブジェクトを参照するか否かを判定する機能を備えた検査用グラフ生成部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記コンテキスト抽象オブジェクトが生成されるか否かを判定し、関数間に跨った制御フローグラフを作成するデータフロー解析を行って前記メソッド呼出パターンが前記パターン定義に従っているか検査するパターン検査部
とを備えたことを特徴とするパターン検査装置。
【請求項１４】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査方法であって、
前記プログラムのコンテキストを考慮したポインタ解析結果を用いることにより、検査対象オブジェクトに対して検査に間係するメソッド呼出を行う呼出場所を識別するステップ
を備えることを特徴とするパターン検査方法。
【請求項１５】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査システムであって、
前記プログラムのプログラム情報に記録された抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係する抽象オブジェクトを抽出するステップと、
前記プログラムのコンテキストを考慮したポインタ解析結果を用いて、前記抽象オブジェクトに対して検査に間係するメソッド呼出を行うメソッド呼出場所を判定するステップと、
関数間に跨った制御フローグラフを作成しデータフロー解析を行って前記メソッド呼出パターンが前記パターン定義に従っているか検査するステップ
とを備えることを特徴とするパターン検査方法。
【請求項１６】
前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得するステップを含むことを特徴とする請求項１５に記載のパターン検査方法。
【請求項１７】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査方法であって、
前記プログラムのプログラム情報に記録された抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係する抽象オブジェクトを抽出するステップと、
前記抽象オブジェクトに対して関係するメソッド呼出場所を識別し、展開したコールグラフを生成するステップと、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記抽象オブジェクトを参照するか否かを判定するステップと、
関数間に跨った制御フローグラフを作成しデータフロー解析を行って前記メソッド呼出パターンが前記パターン定義に従っているか検査するステップ
とを備えることを特徴とするパターン検査方法。
【請求項１８】
前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得するステップを含むことを特徴とする請求項１７に記載のパターン検査方法。
【請求項１９】
オブジェクト・センシティブなポインタ解析によって得られる前記ポインタ解析結果を利用することを特徴とする請求項１４から請求項１８の何れか１項に記載のパターン検査方法。
【請求項２０】
ＣＦＡ型のポインタ解析による前記ポインタ解析結果を利用することを特徴とする請求項１４から請求項１８の何れか１項に記載のパターン検査方法。
【請求項２１】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査方法であって、
前記プログラムのプログラム情報に記録されたコンテキスト抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係するコンテキスト抽象オブジェクトを抽出するステップと、
前記プログラムのポインタ解析結果を用いて、コンテキスト抽象オブジェクトに対して関係するメソッド呼出場所を識別し、展開したコールグラフを生成するステップと、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記コンテキスト抽象オブジェクトを参照するか否かを判定するステップと、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記コンテキスト抽象オブジェクトが生成されるか否かを判定し、関数間に跨った制御フローグラフを作成するデータフロー解析を行って前記メソッド呼出パターンが前記パターン定義に従っているか検査するステップ
とを備えることを特徴とするパターン検査方法。
【請求項２２】
参照変数と抽象オブジェクトに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得するステップを含むことを特徴とする請求項２１に記載のパターン検査方法。
【請求項２３】
コンピュータ上で実行され、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体であって、
前記パターン検査プログラムが、
前記プログラムのコンテキストを考慮したポインタ解析結果を用いることにより、検査対象オブジェクトに対して検査に間係するメソッド呼出を行う呼出場所を識別する処理を
前記コンピュータに実行させることを特徴とする記録媒体。
【請求項２４】
コンピュータ上で実行され、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体であって、
前記パターン検査プログラムが、
前記プログラムのプログラム情報に記録された抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係する抽象オブジェクトを抽出する処理と、
前記プログラムのコンテキストを考慮したポインタ解析結果を用いて、前記抽象オブジェクトに対して検査に間係するメソッド呼出を行うメソッド呼出場所を判定する処理と、
関数間に跨った制御フローグラフを作成しデータフロー解析を行って前記メソッド呼出パターンが前記パターン定義に従っているか検査する処理を
前記コンピュータに実行させることを特徴とする記録媒体。
【請求項２５】
前記パターン検査プログラムが、前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する処理を含むことを特徴とする請求項２４に記載の記録媒体。
【請求項２６】
コンピュータ上で実行され、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体であって、
前記パターン検査プログラムが、
前記プログラムのプログラム情報に記録された抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係する抽象オブジェクトを抽出する処理と、
前記抽象オブジェクトに対して関係するメソッド呼出場所を識別し、展開したコールグラフを生成する処理と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記抽象オブジェクトを参照するか否かを判定する処理と、
関数間に跨った制御フローグラフを作成しデータフロー解析を行って前記メソッド呼出パターンが前記パターン定義に従っているか検査する処理を
前記コンピュータに実行させることを特徴とする記録媒体。
【請求項２７】
前記パターン検査プログラムが、前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する処理を含むことを特徴とする請求項２６に記載のパターン検査方法。
【請求項２８】
前記パターン検査プログラムが、オブジェクト・センシティブなポインタ解析によって得られる前記ポインタ解析結果を利用することを特徴とする請求項２３から請求項２７の何れか１項に記載の記録媒体。
【請求項２９】
前記パターン検査プログラムが、ＣＦＡ型のポインタ解析による前記ポインタ解析結果を利用することを特徴とする請求項２３から請求項２７の何れか１項に記載の記録媒体。
【請求項３０】
コンピュータ上で実行され、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体であって、
前記パターン検査プログラムが、
前記プログラムのプログラム情報に記録されたコンテキスト抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係するコンテキスト抽象オブジェクトを抽出する処理と、
前記プログラムのポインタ解析結果を用いて、コンテキスト抽象オブジェクトに対して関係するメソッド呼出場所を識別し、展開したコールグラフを生成する処理と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記コンテキスト抽象オブジェクトを参照するか否かを判定する処理と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記コンテキスト抽象オブジェクトが生成されるか否かを判定し、関数間に跨った制御フローグラフを作成するデータフロー解析を行って前記メソッド呼出パターンが前記パターン定義に従っているか検査する処理を
前記コンピュータに実行させることを特徴とする記録媒体。
【請求項３１】
前記パターン検査プログラムが、参照変数と抽象オブジェクトに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する処理を含むことを特徴とする請求項３０に記載の記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン検査システム、パターン検査方法およびパターン検査用プログラムを記録した記憶媒体に関し、特にコンテキストを考慮したポインタ解析結果を用いて高い精度でパターンを検査できるパターン検査システム、パターン検査装置、パターン検査方法およびパターン検査用プログラムに関する。
【背景技術】
【０００２】
一般に、この種のパターン検査システムは、プログラム実行時に当該プログラムの中で適切なパターンで関数呼出しが発生するか否かを検査する。【０００３】
関連するパターン検査システムの例として、実際にプログラムを実行させることなく、プログラムのソースコードを解析し実行時の振る舞いを解析する検査システムの一例が、特許文献１と非特許文献１にそれぞれ記載されている。また、プログラム実行時にプログラムの振る舞いを監視し検査する検査システムの一例が、特許文献２に記載されている。【０００４】
このように、パターンを検査する方法としては、プログラムを実行せずに解析する方法と実行中に監視して検出する方法の２種類が存在する。このうち、特許文献２に記載されているような実行時にプログラムの動作を監視して異常を検出する方法は、プログラムの実行速度の低下を招くという問題点を有している。【０００５】
以下、関連する技術としてプログラムを実行させることなく解析する検査システムについてより詳細に述べる。【０００６】
この種の検査システムは、プログラムと、関数呼出しパターンの規則とを入力として受け付けると、与えられたプログラムが実行時に与えられた関数呼び出しのパターンを守るか否かを、プログラムを解析することにより判定し、その判定結果を出力する。【０００７】
このような検査システムは、プログラムの構文を解析する構文解析部と、関数内の制御フローを生成する関数内制御フローグラフ生成部と、関数間にまたがった制御フローグラフを生成する関数間制御フローグラフ生成部と、与えられたパスが妥当かどうかを検査するパス検査部と、関数間制御フローグラフとパス検査部とを用いてパターンが守られているか否かを検査するデータフロー解析部とから構成される。【０００８】
図２の例を用いて、より具体的に検査システムの動作を説明する。図２のプログラム例は、オブジェクト指向型言語で記述したプログラムのソースコードである。【０００９】
構文解析部は、プログラムのソースコードを解析して、プログラムを構成する文や、式、制御構造など各要素を、プログラミング言語の文法に従って判別する。関数内制御フローグラフ生成部は、各メソッド毎に関数内制御フローグラフを生成する。【００１０】
関数内制御フローグラフは、プログラムの各文をノードとし、プログラムの制御の流れに従ってノードを有向辺で接続した有向グラフである。図２のプログラム例の場合は、メソッドmainとfuncのそれぞれについて関数内制御フローグラフを生成する。【００１１】
関数間制御フローグラフ生成部は、各メソッドの関数内制御フローグラフをメソッド呼出に従って接続した関数間制御フローグラフを生成する。図２の例では、mainメソッドからfuncメソッドが呼び出されている。そのためmain中のfuncメソッド呼出を行う文に対応した関数内制御フローグラフのノードから、funcメソッドの開始ノード（entry）に対して有向辺を張り、funcメソッドの終端ノード（exit）から対応する呼出しの戻り場所に有向辺を張る。２つの呼出しがあるため、図２では経路１、経路２、経路３、経路４の合計４本の有向辺が追加される。【００１２】
データフロー解析部は、このようにして得られた関数間制御フローグラフを用いてパターンを検査する。関数間制御フローグラフでは、例えば、経路１から経路４、あるいは、経路３から経路２、のように実際のプログラムの実行ではありえない経路が存在する。これらの経路は、関数呼出しに対応する正しい戻り場所に戻らないような経路であり、プログラム実行時には発生する可能性がない経路であるため、検査精度を低下させる要因となる。【００１３】
そこで、データフロー解析部は、経路が与えられると、その経路に登場する関数呼出しノードと戻りノードが適切に対応しているか否かを判定するパス検査部を用いて、パス検査部が妥当と判定した経路についてのみ検査する。データフロー解析部は、データフロー解析を用いて、すべての妥当な経路について発生しうる関数呼出しのパターンを解析すると、与えられたパターン定義に従うか否かを検査する。従わないものが有る場合は、その旨を表示する。
【特許文献１】特開２００４−１４５３８１号公報（図１）
【特許文献２】特開２００２−３３３９９２号公報（図１）
【非特許文献１】トーマス・レプ（ThomasReps）、他２名、“プリサイス  インタープロシーデュラル  データフロー  アナリシス  ヴィア  グラフ  リーチャビリティ”（Precise InterproceduralDataflow Analysis via Graph Reachability）、米国、１９９５年、エーシーエム ピー・オー・ピー・エル’９５予稿集（ACMPOPL’95）、４９−６１頁
【発明の開示】
【発明が解決しようとする課題】
【００１４】
第１の問題点は、上述した関連する検査システムでは、オブジェクト指向型言語により記述されたプログラムの関数（メソッド）間に跨った関数（メソッド）呼出しパターンを検査できないことである。【００１５】
その理由は、オブジェクト指向型言語では、特定のオブジェクトに対して発行されるメソッド呼出順序を検査する必要があるが、上述した関連のパス検査システムは、関数呼出しの順番のみを考慮し、その関数がどの対象（メモリ上に記録されたデータ）に対して作用を与えるかを何ら考慮していないためである。【００１６】
したがって、上述した関連する検査システムは、プログラム中に登場する各参照変数（ポインタ変数）が実行時にどのオブジェクトを指すかを判別できない。その結果、オブジェクト指向型言語を検査すると、正しいプログラムであるにもかかわらず誤りがあると判断する、または誤ったプログラムを正しいと判断する、などの誤った判定が多発し、意味のある検査が実行できない。【００１７】
例えば、図２の例で、１行目で生成されるRのオブジェクトと、３行目で生成されるRのオブジェクトがある。関連の検査システムは、funcの中で呼び出されるreleaseメソッド呼出が、１行目で生成されたオブジェクトを参照するのか３行目で生成されたオブジェクトを参照するのかを区別できない。【００１８】
第２の問題点は、特定の実行経路で、当該経路に登場するメソッド中に登場する参照変数が、特定のオブジェクトを参照するかどうかを判定できないことである。【００１９】
その理由は、上述した関連する検査システムは、関数呼出しの対応関係のみしか考慮していないためである。【００２０】
図２の例において、検査システムは、経路１と経路２、および経路３と経路４の２通りであることを発見するが、前記の経路に含まれるfunc内の参照変数pが当該経路の場合にどのオブジェクトを参照するのかを区別できない。【００２１】
パターンを精度良く検査するためには、経路１からfuncが呼出される場合は
p は1行目で生成されたR型のオブジェクトを指し、経路３からfuncが呼出される場合は p は３行目で生成されたR型のオブジェクトを指すことを検査システムが発見できる必要がある。【００２２】
（発明の目的）
本発明の目的は、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを、プログラムを実行することなしに、関数間に跨って検査できるパターン検査システムを提供することにある。【００２３】
本発明の他の目的は、特定のオブジェクトに対して発行されるメソッド呼出パターンを精度良く検査するパターン検査システムを提供することにある。
【課題を解決するための手段】
【００２４】
本発明の第１のパターン検査システムは、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査システムであって、プログラムのコンテキストを考慮したポインタ解析結果を用いることにより、検査対象オブジェクトに対して検査に間係するメソッド呼出を行う呼出場所を識別する手段を含む。【００２５】
本発明の第２のパターン検査システムは、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査システムであって、プログラムのプログラム情報に記録された抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係する抽象オブジェクトを抽出する抽出手段と、プログラムのコンテキストを考慮したポインタ解析結果を用いて、抽象オブジェクトに対して検査に関係するメソッド呼出を行うメソッド呼出場所を判定する判定手段と、関数間に跨った制御フローグラフを作成しデータフロー解析を行ってメソッド呼出パターンがパターン定義に従っているか検査する検査手段とを含む。【００２６】
本発明の第１のパターン検査装置は、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査装置であって、プログラムのコンテキストを考慮したポインタ解析結果を用いることにより、検査対象オブジェクトに対して検査に間係するメソッド呼出を行う呼出場所を識別する手段を含む。【００２７】
本発明の第２のパターン検査装置は、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査装置であって、プログラムのプログラム情報に記録された抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係する抽象オブジェクトを抽出する抽出手段と、プログラムのコンテキストを考慮したポインタ解析結果を用いて、抽象オブジェクトに対して検査に間係するメソッド呼出を行うメソッド呼出場所を判定する判定手段と、関数間に跨った制御フローグラフを作成しデータフロー解析を行ってメソッド呼出パターンがパターン定義に従っているか検査する検査手段とを含む。【００２８】
本発明の第１のパターン検査方法は、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査方法であって、プログラムのコンテキストを考慮したポインタ解析結果を用いることにより、検査対象オブジェクトに対して検査に間係するメソッド呼出を行う呼出場所を識別するステップを有する。【００２９】
本発明の第２のパターン検査方法は、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査システムであって、プログラムのプログラム情報に記録された抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係する抽象オブジェクトを抽出するステップと、プログラムのコンテキストを考慮したポインタ解析結果を用いて、抽象オブジェクトに対して検査に間係するメソッド呼出を行うメソッド呼出場所を判定するステップと、関数間に跨った制御フローグラフを作成しデータフロー解析を行ってメソッド呼出パターンがパターン定義に従っているか検査するステップを有する。【００３０】
本発明の第１のパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体は、コンピュータ上で実行され、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体であって、パターン検査プログラムが、プログラムのコンテキストを考慮したポインタ解析結果を用いることにより、検査対象オブジェクトに対して検査に間係するメソッド呼出を行う呼出場所を識別する処理をコンピュータに実行させる。【００３１】
本発明の第２のパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体は、コンピュータ上で実行され、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに対して発行されるメソッド呼出パターンを検査するパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体であって、パターン検査プログラムが、プログラムのプログラム情報に記録された抽象オブジェクトからパターン定義に記述された検査対象クラス名を参照して検査に関係する抽象オブジェクトを抽出する処理と、プログラムのコンテキストを考慮したポインタ解析結果を用いて、抽象オブジェクトに対して検査に間係するメソッド呼出を行うメソッド呼出場所を判定する処理と、関数間に跨った制御フローグラフを作成しデータフロー解析を行ってメソッド呼出パターンがパターン定義に従っているか検査する処理をコンピュータに実行させる。
【発明の効果】
【００３２】
第１の効果は、関数内、または関数間に跨って特定の抽象オブジェクトに対して発行されるメソッドのパターンを検査できることにある。
その理由は、プログラム中に登場する参照変数が、プログラム実行時にどの抽象オブジェクトを参照するかを考慮して、検査対象となる特定の抽象オブジェクトに対して発行されるメソッド呼出の呼出パターンを検査するためである。【００３３】
第２の効果は、パターン検査の誤検出率を削減できることにある。
その理由は、展開したコールグラフ中の各メソッドに登場する参照変数が検査対象の抽象オブジェクトを参照するか否かを、コンテキストを考慮したポインタ解析結果を用いて判定し、実際に参照する場合にのみ、そのメソッド呼出が発生するものとして扱うためである。
【図面の簡単な説明】
【００３４】
【図１】本発明の第１の実施の形態によるパターン検査システムの構成を示すブロック図である。
【図２】サンプルプログラムとその関数間に跨る制御フローグラフの例を示す図である。
【図３】本発明の第１の実施の形態によるパターン定義の構成例を示す図である。
【図４】本発明の第１の実施の形態によるポインタ解析結果の構成例を示す図である。
【図５】本発明の第１の実施の形態による抽象オブジェクトの構成例を示す図である。
【図６】本発明の第１の実施の形態によるメソッド呼出場所の構成例を示す図である。
【図７】本発明の第１の実施の形態による有向グラフの構成例を示す図である。
【図８】本発明の第２の実施の形態によるポインタ解析結果の構成例を示す図である。
【図９】本発明の第２の実施の形態によるコンテキスト抽象オブジェクトの構成例を示す図である。
【図１０】本発明の第１の実施の形態による動作を示すフローチャートである。
【図１１】本発明の第１の実施の形態によるコールグラフ展開部の動作の詳細を示すフローチャートである。
【図１２】本発明の第１の実施の形態による検査用グラフ生成部の動作の詳細を示すフローチャートである。
【図１３】本発明の第１の実施の形態によるオブジェクト・センシティブなポインタ解析結果を用いた検査用グラフ生成部の動作の詳細を示すフローチャートである。
【図１４】本発明の第１の実施の形態によるＣＦＡ型のポインタ解析結果を用いた検査用グラフ生成部の動作の詳細を示すフローチャートである。
【図１５】本発明の第２の実施の形態によるオブジェクト・センシティブなポインタ解析結果を用いた検査用グラフ生成部の動作の詳細を示すフローチャートである。
【図１６】本発明の第２の実施の形態によるＣＦＡ型のポインタ解析結果を用いた検査用グラフ生成部の動作の詳細を示すフローチャートである。
【図１７】本発明の第１の実施の形態によるパターン検査装置のハードウェア構成を示すブロック図である。
【発明を実施するための最良の形態】
【００３５】
次に、本発明の実施の形態について図面を参照して詳細に説明する。【００３６】
（第１の実施の形態）
図１を参照すると、本発明の第１の実施の形態によるパターン検査システムは、プログラム制御により動作するパターン検査装置１１と、情報を記憶する記憶装置１２と、キーボードなどの入力装置１３と、ディスプレイ装置や印刷装置などの出力装置１４と、オブジェクト指向言語で記述されたプログラムを格納するファイルなどの検査対象プログラム１５を記憶するプログラム記憶部２０と、検査パターンを格納したファイルなどのパターン定義１６を記憶するパターン定義記憶部２１とを含む。【００３７】
検査対象プログラム１５は、ＪａｖａやＣ＃などのオブジェクト指向型言語で記述されたプログラムであり、そのコード形式はコンパイル前のソースコードあるいはコンパイル後の実行コードのどちらでも良い。【００３８】
パターン定義１６は、あるオブジェクトに対して発行されるメソッド呼出パターン規則を記述したものであり、パターン検査システム利用者が独自に定義しても良いし、あらかじめパターン検査システムに組み込んでおいても良い。【００３９】
パターン定義１６の一例を図３に示す。パターン定義１６は検査対象クラス名５１ａと、検査対象メソッド５１ｂと、検査パターン５１ｃとから構成される。検査対象クラス名５１ａは、当該呼出しパターンを守るべきオブジェクトのクラスを示す。検査対象メソッド５１ｂは、パターンに関係するメソッドの集合を示す。検査パターン５１ｃは、前記メソッドが前記オブジェクトに対して発行される際に守られるべきパターンを示す。【００４０】
検査パターン５１ｃは、例えば、有限オートマトンとして記述できる。有限オートマトンは、状態と、状態を結ぶ辺、および辺に対して割り当てられるラベルとからなり、１つの開始状態、複数の受理状態を持つ。ある状態から別の状態への遷移はメソッド呼出により発生するため、前状態と後状態とメソッドの３つ組により有限オートマトンの遷移関係を表現できる。【００４１】
ある実行系列で特定のオブジェクトに対して発行されるメソッド呼出の列が検査パターンを表現した前記有限オートマトンにより受理されれば、当該実行系列は前記オブジェクトに対してメソッド呼出パターンの規則を守っていると判断する。【００４２】
パターン検査装置１１を構成する各要素について、図１、図４、５、６、７を用いて、その概略を説明する。【００４３】
前処理部１１１は、検査対象プログラム１５を解析してパターン検査に必要な各種のプログラム情報をプログラム情報記憶装置１２１に保存し、さらに検査対象プログラム１５に対してコンテキストを考慮したポインタ解析を適用し、そのポインタ解析結果５２をポインタ解析結果記憶装置１２２に保存する。【００４４】
プログラム情報は、プログラム中でメソッド呼出が発生する場所を記録したメソッド呼出場所５４（図６参照）や、オブジェクトが生成される場所と生成されるオブジェクトの型とを関係付けて記録した抽象オブジェクト５３（図５参照）や、メソッド呼出の関係を記録したコールグラフ（図７の有向グラフ５５参照）などを含む。コールグラフは、図７に示すような有向グラフ５５の構成により表現できる。コールグラフにおけるノードはメソッドに対応する。あるメソッドＡがメソッドＢを呼出す場合、コールグラフの有向辺はメソッドＡとＢのペア（Ａ，Ｂ）を含む。【００４５】
ポインタ解析結果５２の構成例を図４に示す。ポインタ解析結果５２は、変数とコンテキストと抽象オブジェクトの３つ組から成る。変数がコンテキストで抽象オブジェクトを参照する可能性がある場合に、その３つ組がポインタ解析結果に含まれる。【００４６】
リソース識別部１１２は、プログラム情報記憶装置１２１からオブジェクトの生成場所を示す抽象オブジェクト５３に関する情報を読み込み、パターン定義１６により指定された検査対象となるオブジェクトの生成場所を識別する。【００４７】
検査対象となるオブジェクトの集合を特にリソースと呼ぶ。識別されたリソースは抽象オブジェクト５３と１対１に対応付けられる。リソース識別部１１２は、リソースの集合、すなわち、検査対象とするべき抽象オブジェクト５３の集合を得ると、その集合に含まれる抽象オブジェクト５３を１つずつコールグラフ展開部１１３に送り、パターン検査部１１５より当該抽象オブジェクト５３に対する検査が完了した通知を得ると、まだ処理していない抽象オブジェクト５３を再びコールグラフ展開部１１３に送る。すべての抽象オブジェクト５３を処理した段階で検査処理が完了となる。【００４８】
コールグラフ展開部１１３は、リソース識別部１１２から１つの抽象オブジェクト５３を受け取ると、プログラム情報記憶装置１２１からコールグラフを読み込み、読み込んだコールグラフを展開する。【００４９】
このコールグラフ展開部１１３は、一般的なパターン検査システムのパス検査部と同様に、メソッド呼出の対応関係をとるための役割を果たす。展開したコールグラフと、リソース識別部１１２より送られた抽象オブジェクト５３とが検査用グラフ生成部１１４に送られる。【００５０】
さらに、コールグラフ展開部１１３は、プログラム情報記憶装置１２１からメソッド呼出場所５４を読み込み、前記抽象オブジェクトに対して発行されるパターン検査に関係があるメソッド呼出場所５４の集合を、前記抽象オブジェクト５３に対応するパターン定義を参照して計算し、その結果を検査用グラフ生成部１１４に送付する。【００５１】
検査用グラフ生成部１１４は、抽象オブジェクト５３と、展開したコールグラフと、検査に関係するメソッド呼出場所５４の集合とを受け取ると、ポインタ解析結果記憶装置１２２からポインタ解析結果５２を読み込む。【００５２】
検査用グラフ生成部１１４は、展開したコールグラフ中に登場する検査に関係するメソッド呼出場所５４の変数が、展開したコールグラフにより与えられるコンテキストで前記抽象オブジェクト５３を参照するか否かを、ポインタ解析結果５２を用いて判定する。【００５３】
そして、前記抽象オブジェクト５３を参照すると判定された展開したコールグラフのノードとメソッド呼出場所５４の組み合わせが、パターン検査部１１５に送られる。また、展開したコールグラフもパターン検査部１１５に送られる。【００５４】
パターン検査部１１５は、展開したコールグラフと、展開したコールグラフのノードとメソッド呼出場所５４の組み合わせの集合とを受け取ると、関数間制御フローグラフを構築し、データフロー解析により前記抽象オブジェクト５３に対して発行されるメソッド呼出のパターンが、パターン定義５１により定義される規則に従うか否かを判定し、その判定結果を出力装置１４を用いて出力する。【００５５】
なお、図１に示すパターン検査装置１１の構成においては、本発明の特徴的な構成要素のみを示し、その他の構成要素については説明を分かりやすくするために省略している。【００５６】
ここで、パターン検査装置１１のハードウェア構成の説明をする。【００５７】
図１７は、第１の実施の形態によるパターン検査装置１１のハードウェア構成を示すブロック図である。【００５８】
図１７を参照すると、パターン検査装置１１は、一般的なコンピュータ装置と同様のハードウェア構成によって実現することができ、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）３０１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等のメインメモリであり、データの作業領域やデータの一時退避領域に用いられる主記憶部３０２を備えている。【００５９】
また、ネットワーク上で情報の送受信を行う通信制御部３０３、液晶ディスプレイ、プリンタやディスプレイ装置等の表示部３０４、キーボードやマウス等の入力部３０５、周辺機部と接続してデータの送受信を行うインタフェース部３０６、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、磁気ディスク、半導体メモリ等の不揮発性メモリ等から構成される補助記憶部３０７、本情報処理装置の上記各構成要素を相互に接続するシステムバス３０８等を備えている。例えば、補助記憶部３０７として、本実施の形態による記憶装置１２を含むことが可能である。【００６０】
本実施の形態によるパターン検査装置１１は、その動作を、上述した各構成要素による機能を実現するプログラムを組み込んだ、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）等のハードウェア部品からなる回路部品を実装してハードウェア的に実現することは勿論として、上記した各構成要素の各機能を提供するプログラムを、コンピュータ処理装置上のＣＰＵ３０１で実行することにより、ソフトウェア的に実現することができる。【００６１】
すなわち、ＣＰＵ３０１が、補助記憶部３０７に格納されているプログラムを、主記憶部３０２にロードして実行し、パターン検査装置１１の動作を制御することにより、上述した各機能をソフトウェア的に実現する。【００６２】
次に、図１及び図１０のフローチャートを参照して本実施の形態の全体の動作について詳細に説明する。【００６３】
まず、入力装置１３を用いて、検査対象プログラム１５とパターン定義１６とがパターン検査装置１１に読み込まれる（ステップＳ１１）。【００６４】
次に、前処理部１１１は、検査対象プログラム１５に対して字句解析、構文解析などの基本的な解析を適用し、抽象オブジェクト５３やメソッド呼出場所５４、また、メソッド内部の関数内制御フローグラフなどをプログラム情報記憶装置１２１に記録する（ステップＳ１２）。【００６５】
関数内制御フローグラフは、プログラムの最小実行単位である文をノードとし、メソッド内の制御フローに従って各ノードを接続した有向グラフであり、例えば、有向グラフ５５の構成をとる。１つの実施例では、Ｊａｖａであれば、スート(Soot (http://www.sable.mcgill.ca/soot/index.html))という解析基盤を用いることで前記プログラム情報を得られる。なお、抽象オブジェクト５３やメソッド呼出場所５４に含まれる「場所」はプログラム中の最小実行単位となる文を一意に示す識別子とする。【００６６】
さらに、前処理部１１１は、コンテキストを考慮したポインタ解析をプログラム１５に適用し、その結果得られるポインタ解析結果５２の集合をポインタ解析結果記憶装置１２２に格納する（ステップＳ１２）。１つの実施例では、Ｊａｖａであれば、コンテキストを考慮したポインタ解析結果はPaddle (http://www.sable.mcgill.ca/paddle/)という解析基盤を用いることで得られる。【００６７】
また、前処理部１１１は、前記ポインタ解析により得られるメソッド呼出の関係を表現したコールグラフをプログラム情報記憶装置１２１に記録する（ステップＳ１２）。【００６８】
次に、リソース識別部１１２は、プログラム情報記憶装置１２１から抽象オブジェクト５３の集合を読み込む。前記抽象オブジェクト５３のうち、その型がパターン定義１６に含まれる検査対象クラス名と一致するような抽象オブジェクト５３を抽出する（ステップＳ１３）。【００６９】
また、他の実施の形態では、リソース識別部１１２が、前記抽象オブジェクト５３のうち、その型がパターン定義１６に含まれる検査対象クラス名と一致するか、検査対象クラスのサブクラスの名前と一致するような抽象オブジェクト５３を抽出するようにしても良い。【００７０】
このステップＳ１３により抽出された抽象オブジェクト５３の集合は、パターン定義１６によりパターンが定義されている検査するべきオブジェクト（リソース）を示している。なお、抽象オブジェクト５３に対応するパターン定義５１とは、当該抽象オブジェクト５３の型に合致する検査対象クラス名を持つパターン定義１６を示すものとする。【００７１】
次に、リソース識別部１１２は、得られた抽象オブジェクト５３の集合から、まだ処理していない抽象オブジェクト５３を１つ選択しコールグラフ展開部１１３に渡す（ステップＳ１４）。すべての抽象オブジェクト５３の処理が完了したら、全体の処理を終了する。【００７２】
コールグラフ展開部１１３は、プログラム情報記憶装置１２１からコールグラフを読み込むと、読み込んだコールグラフから展開したコールグラフを生成する（ステップＳ１５）。
【００７３】
ここで、コールグラフ展開部１１３によるコールグラフの展開処理（ステップＳ１５）について図１１のフローチャートを用いてより詳細に説明する。図１１のフローチャートはステップＳ１５の処理の詳細を示している。【００７４】
まず、コールグラフ展開部１１３は、プログラム情報記憶装置１２１からメソッド呼出場所５４の集合を読み込み、ポインタ解析結果記憶装置１２２からポインタ解析結果５２の集合を読み込むと、メソッド呼出場所５４の集合から、受け付けた抽象オブジェクト５３に関係するもののみを抽出する。【００７５】
メソッド呼出場所５４が抽象オブジェクト５３に関係するか否かは次のように判定する。【００７６】
すなわち、メソッド呼出場所５４に含まれる変数と与えられた抽象オブジェクト５３との組み合わせが前記ポインタ解析結果５２の集合に含まれており、かつ前記メソッド呼出場所５４に含まれるメソッド名が、前記抽象オブジェクト５３に対応するパターン定義１６の検査対象メソッドの集合に含まれているのならば、当該メソッド呼出場所５４は前記抽象オブジェクト５３と関係する、と判定する。【００７７】
なお、ポインタ解析結果５２の集合に、ある変数と抽象オブジェクトとの組み合わせが含まれるか否かの判定は、前記変数と任意のコンテキスト（空のコンテキストを含む）と前記抽象オブジェクトとの３つ組がポインタ解析結果５２の集合に含まれているか否かを判定することと等価とする。【００７８】
前記抽出したメソッド呼出場所５４の集合を、抽象オブジェクト５３の検査に関係するメソッド呼出場所５４の集合、あるいは単に、検査に関係するメソッド呼出場所５４の集合、と記述する。検査に関係するメソッド呼出場所５４を含むメソッドを検査に関係するメソッドと判断し、収集する（ステップＳ５１）。【００７９】
次に、読み込んだコールグラフから検査に関係する部分グラフを抽出する（ステップＳ５２）。【００８０】
なお、パターン検査に必ずしも本ステップが必要ではなく、ステップＳ５１からステップＳ５３に処理を移しても良い。ただし、一般に、コールグラフを展開すると膨大な規模の有向グラフとなるため、不要な部分を本ステップにおいて取り除いておくことが計算時間の短縮や消費メモリ量の削減につながり、好ましい。【００８１】
受け付けた抽象オブジェクト５３に含まれる場所を含むメソッドと、前記抽象オブジェクト５３の検査に関係するメソッドとを「関心があるメソッド」と呼ぶ。部分グラフは有向グラフであり、例えば、図７に示すような有向グラフ５５の構成を持つ。部分グラフの頂点には、関心があるメソッドと、コールグラフの中で関心があるメソッドに到達するすべてのメソッドを含める。有向グラフ中のあるノードから到達可能なノードの集合を算出する方法は広く知られている。【００８２】
次に、コールグラフの有向辺に含まれる（メソッド１、メソッド２）のペアのうち、メソッド２が部分グラフの頂点のメソッド集合に含まれるようなペアを、部分グラフの有向辺に含める。こうして得られた部分グラフは、コールグラフのエントリ・ポイントから関心があるメソッドに到達する任意の経路に含まれるすべてのノード（メソッド）と、その経路に対応する有向辺とを含む。【００８３】
次に、ステップＳ５２で得られた部分グラフ、あるいはステップＳ５２の処理を省略する場合はコールグラフ、を展開する（ステップＳ５３）。【００８４】
再帰的なメソッド呼出を含む場合、部分グラフ、またはコールグラフは循環を含む有向グラフになる。そのため、本実施の形態では、グラフ中の各Ｓｔｒｏｎｇｌｙ
Ｃｏｎｎｅｃｔｅｄ Ｃｏｍｐｏｎｅｎｔ（ＳＣＣ）を１つのノードに縮退した非循環有向グラフに変換し、各ノードへの入力辺が１つになるようにノードを複製する。【００８５】
その後、前記複製したグラフに含まれるＳｔｒｏｎｇｌｙ Ｃｏｎｎｅｃｔｅｄ Ｃｏｍｐｏｎｅｎｔの要素を元の接続関係を維持するように復元して、展開したグラフを得る。【００８６】
このような展開方法は、例えば、非特許文献：Ondrej
Lhotak著、Program Analysis Using Binary Decision Diagrams、米国、2006年、McGill大学、博士論文、104-106頁(online:
http://plg.uwaterloo.ca/~olhotak/pubs/thesis-olhotak-phd.ps)に記載されており、当該技術分野の専門家には広く知られている。【００８７】
展開したコールグラフの頂点は、メソッドと識別子のペアの集合から成る。展開したコールグラフでは、１つのノードに複数のメソッドが対応するため、識別子により同じメソッドに対応する異なるノードを識別する。識別子は、したがって、同じメソッドに対応するノードの間で唯一の値をとるものとする。有向辺は、メソッドと識別子のペアを要素とするペアの集合である。【００８８】
以上がステップＳ１５のコールグラフ展開処理の動作の詳細である。【００８９】
次に、検査用グラフ生成部１１４は、コールグラフ展開部１１３より展開したコールグラフと、抽象オブジェクト５３と、前記抽象オブジェクト５３の検査に関係するメソッド呼出場所５４の集合とを受け付けると、ポインタ解析結果記憶装置１２２からポインタ解析結果５２を読み込み、検査用グラフを生成する（ステップＳ１６）。【００９０】
この検査用グラフを生成するための動作の詳細を図１２のフローチャートを用いて説明する。【００９１】
まず、検査用グラフ生成部１１４は、展開したコールグラフの中から、まだ処理していない未処理のノードを１つ選択する（ステップＳ６１、Ｓ６２）。【００９２】
次に、検査に関係するメソッド呼出場所の集合の中から、まだ処理していないメソッド呼出場所を１つ選択する（ステップＳ６３、Ｓ６４）。処理していないメソッド呼出場所がない場合はステップＳ６１に戻る。【００９３】
選択したノードを構成するメソッドが前記メソッド呼出場所を含む場合、ステップＳ６６の処理に移り、含まない場合はステップＳ６３に戻る（ステップＳ６５）。【００９４】
展開したコールグラフに選択したノードの親ノードが存在する場合はステップＳ６７に、存在しない場合はステップＳ６８に処理を移す（ステップＳ６６）。親ノードが存在するとは、展開したコールグラフの有向辺に（親ノード、選択ノード）なるペアが含まれることを示す。【００９５】
親ノードが存在する場合は、当該ノードのコンテキストで前記メソッド呼出場所の変数が前記抽象オブジェクトを参照するか否かを判定する（ステップＳ６７）。本判定処理の詳細は後述する。参照すると判定された場合はステップＳ６８に、そうでない場合はステップＳ６３に戻る。【００９６】
ステップＳ６８では、当該ノードと当該メソッド呼出場所５４のペアをリソース利用箇所と呼ぶ集合に追加する。リソース利用箇所に含まれるノードとメソッド呼出場所のペアは次の性質を有する。【００９７】
すなわち、当該ノードにより与えられるコンテキストにおいてメソッド呼出場所５４に含まれる変数は前記抽象オブジェクト５３を参照し、かつメソッド呼出場所５４では、検査に関係するメソッド呼出が発生する、という性質である。【００９８】
ステップＳ６１で、すべてのノードの処理が終了すると、検査用グラフ生成部１１４は、作成したリソース利用箇所（展開したコールグラフのノードとメソッド呼出場所５４の組み合わせの集合）と展開したコールグラフと、前記抽象オブジェクト５３と、をパターン検査部１１５に渡してステップＳ１６の処理を終える。なお、ステップＳ１６が始まる段階でのリソース利用箇所は空の集合とする。
【００９９】
最後に、パターン検査部１１５は、リソース利用箇所と展開したコールグラフを受け取ると、関数間に跨った制御フローグラフを生成し、当該制御フローグラフに対してデータフロー解析をにより、前記抽象オブジェクトに対応したパターン定義５１の検査パターンが守られているか否かを検査し、その結果を、出力装置１４を用いて表示する（ステップＳ１７）。【０１００】
パターン検査部１１５のパターン検査方法についてより詳細に説明する。【０１０１】
関数間に跨った制御フローグラフは以下のような方法で作成する。
（１）展開したコールグラフの各ノードを構成する各メソッドの関数内制御フローグラフをプログラム情報記録装置１２１から読み込む。
（２）展開したコールグラフのすべての有向辺（ノードＡ，ノードＢ）について、Ａを構成するメソッドの関数内制御フローグラフ内に登場する全てのＢを構成するメソッドのメソッド呼出場所からＢを構成するメソッドの関数内制御フローグラフのエントリノードに有向辺を引く。
（３）Ｂを構成するメソッドの関数内制御フローグラフのすべての終端ノードからＡを構成するメソッドの関数内制御フローグラフの対応するＢを構成するメソッドのメソッド呼出の戻り場所への有向辺を引く。【０１０２】
例えば、上記において、ノードＡを構成するメソッドをｍ１とし、ノードＢを構成するメソッドをｍ２とすると、ｍ１の関数内制御フローグラフ内に登場する全てのｍ２メソッド呼出場所からｍ２の関数内制御フローグラフのエントリノードに有向辺を引き、ｍ２の関数内制御フローグラフのすべての終端ノードからｍ１の関数内制御フローグラフの対応するｍ２メソッド呼出の戻り場所への有向辺を引くことで、関数間に跨った制御フローグラフが作成される。【０１０３】
関数間に跨った制御フローグラフの作成方法は一般的なパターン検査システムとほぼ同様であるが、一般的なシステムでは、展開していないコールグラフから関数間に跨った制御フローグラフを生成するのに対して、本発明の第１の実施の形態によるパターン検査システムでは、展開したコールグラフから関数間に跨った制御フローグラフを生成する点が異なっている。【０１０４】
得られた関数間に跨った制御フローグラフのうち、当該抽象オブジェクト５３に含まれる場所に対応するノードを、検査対象オブジェクトを生成するノードとして記録する。また、前記リソース利用箇所に含まれるノードとメソッド呼出場所５４の組により決定されるノードを当該抽象オブジェクト５３に対してパターンに関係するメソッド呼出を行うノードとして記録する。それ以外のノードは検査に関係しないノードとして記録する。【０１０５】
なお、展開したコールグラフのノードとメソッド呼出場所５４が与えられると、まず、関数間に跨った制御フローグラフから前記展開したコールグラフのノードに対応する部分グラフ（前記ノードを構成するメソッドに対応した関数内の制御フローグラフ）が識別され、次に、前記部分グラフからメソッド呼出場所５４に含まれる場所に対応するノードが識別される。【０１０６】
これにより、当該抽象オブジェクト５３を生成するノードと、当該抽象オブジェクト５３に対してパターンに関係するメソッド呼出を行うノードと、それ以外の検査に関係しないノードの３種類のノードを含む有向グラフ（関数間に跨った制御フローグラフ）が得られる。【０１０７】
そこで、前記パターン定義１６に定義された有限オートマトンが、前記有向グラフの各ノードでどのような状態を取り得るかをデータフロー解析により計算する。有向グラフの終端ノードで有限オートマトンが受理状態以外の状態を取る場合にはパターンに違反すると判定する。【０１０８】
また、有限オートマトンに定義されていない遷移が発生した場合もパターン違反と見なしても良い。このようなデータフロー解析による判定方法については、当該技術分野の当業者に広く知られている。【０１０９】
以上の動作により、プログラム実行時に生成される特定のオブジェクトに対して発行されるメソッドのパターンが与えられたパターンの規則に従うか否かを判定できる。【０１１０】
次に、検査用グラフ生成部１１４の処理である、図１２に示したフローチャートのステップＳ６７の詳細な動作を図１３、図１４に示すフローチャートを用いて説明する。【０１１１】
本ステップでは、検査対象である当該抽象オブジェクト５３を参照する可能性がある当該メソッド呼出場所５４の変数が、展開したコールグラフにおける当該ノードにより与えられるコンテキストにおいて当該抽象オブジェクト５３を参照するか否かを、ポインタ解析結果５２を用いて判定する。判定方法は利用するポインタ解析の種類に依存する。【０１１２】
第１の実施の形態ではオブジェクト・センシティブ（object
sensitive）と呼ばれる種類のポインタ解析を利用する。この種のポインタ解析は、例えば、非特許文献：アナ・ミラノバ（Ana Milanova）、他２名、“パラメタライズド
オブジェクト センシティビティ フォー ポインツ・トゥー アナリシス フォー ジャヴァ”（Parameterized Object Sensitivity
for Points-to Analysis for Java）、米国、２００５年、エーシーエム トランザクション オン ソフトウェア エンジニアリング  アンド  メソドロジー（ACM
Transaction on Software Engineering and Methodology）、１４巻、１号、１−４１頁に記載されている。【０１１３】
この種のポインタ解析結果では、コンテキストが抽象オブジェクトの列により表現される。したがって、オブジェクト・センシティブなポインタ解析結果は、変数、コンテキストとしての抽象オブジェクト、抽象オブジェクトと３つ組により構成される。コンテキストとしての抽象オブジェクトは、当該変数が登場するメソッドのレシーバ・オブジェクトである。なお、１つの実施例では、Ｊａｖａであれば、そのようなポインタ解析結果はPaddle(http://www.sable.mcgill.ca/paddle/)という解析基盤を用いることで得られる。【０１１４】
図１３のフローチャートはオブジェクト・センシティブなポインタ解析結果を用いた場合に、判定に利用する関数の動作を示しており、再帰呼出を含む。前記関数は当該ノードから探索的に展開したコールグラフの親ノードをたどってパスが妥当か否かを判定する。ステップＳ６７では、前記関数 validPath に対して、当該ノードと、当該メソッド呼出場所５４の変数と、当該抽象オブジェクト５３と、空のリストと、深さを示す数値を与え、その結果が真であれば妥当であると判断し、偽であれば妥当でないと判断する。【０１１５】
深さを示す数値は探索の深さを指定するために用いられる。全てを探索する場合は深さを０未満の値にすればよい。良い精度を得るためには０未満の値を指定することが好ましい。性能を考慮すると３程度の深さを指定すると好ましい。【０１１６】
図１３のフローチャートを用いて関数の動作の詳細を説明する。関数の引数は、展開したコールグラフ中の特定のノードを示すnode、変数var、抽象オブジェクトa、履歴history、最大の深さdepthである。本関数はnodeにより指定されたコンテキストでvarがaを参照するか否かを判定する。【０１１７】
最初に、履歴を示すリストhistoryにnodeを追加する（ステップＳＡ１）。【０１１８】
次に、展開したコールグラフ中にnodeの親ノードが存在するか否かを判定し、存在しない場合はコンテキストが得られないのでステップＳＡ１２に移る。存在する場合はステップＳＡ３に移る（ステップＳＡ２）。【０１１９】
ステップＳＡ３では、探索の深さを調べる。depthの値が０と等しければステップＳＡ１２に移り、そうでない場合はステップＳＡ４に移る。【０１２０】
ステップＳＡ１２では、変数varが抽象オブジェクトaを参照するか否かをポインタ解析結果を用いて判定する。varと任意のコンテキスト（空のコンテキストを含む）とaの３つ組がポインタ解析結果の集合に含まれていれば真を返し、そうでないならば偽を返す。【０１２１】
ステップＳＡ４では、nodeの親ノードのうち処理していないものがあれば１つを選択してステップＳＡ５に移る。すべての親ノードを処理した場合は偽を返す。【０１２２】
ステップＳＡ５では前記親ノードがhistoryに含まれるならばステップＳＡ４に戻る。そうでないならばステップＳＡ６に移る。【０１２３】
ステップＳＡ６では、当該nodeを構成するメソッドがstaticメソッドであるか否かを判定し、staticメソッドならばステップＳＡ８に移り、そうでない場合にはステップＳＡ７に移る。【０１２４】
ステップＳＡ８では、前記親ノードと、変数varと、抽象オブジェクトaと、履歴historyと、depth-1
を再帰的に本関数に適用し、その結果が真ならば真を返し、偽ならばステップＳＡ４に戻る。【０１２５】
なお、staticメソッドの場合、レシーバ・オブジェクトが存在しない。この時、staticメソッドを呼出すメソッドのレシーバ・オブジェクトをコンテキストとして利用するようなポインタ解析を本実施の形態では想定している。【０１２６】
また別の実施の形態として、staticメソッドの場合はコンテキストを空とするオブジェクト・センシティブなポインタ解析を利用することもできる。この種のポインタ解析を用いた実施の形態では、ステップＳＡ８の動作が次のように変わる。つまり、ステップＳＡ８で、変数varが抽象オブジェクトaを参照するか否かをポインタ解析結果を用いて判定する。そして、varと任意のコンテキスト（空のコンテキストを含む）とaの３つ組がポインタ解析結果の集合に含まれていれば真を返し、そうでないならばステップＳＡ４に戻る。【０１２７】
ステップＳＡ７では、前記親ノードを構成するメソッドに含まれるメソッド呼出場所５４のうち、当該nodeを構成するメソッドをメソッド名として持つようなメソッド呼出場所５４を抽出し、それぞれについてステップＳＡ９から始まる処理を適用する。すべての抽出したメソッド呼出場所５４の処理を終えた場合はステップＳＡ４に戻る。【０１２８】
ステップＳＡ９では、前記選択されたメソッド呼出場所５４の変数が参照する抽象オブジェクトの集合を求め、それぞれについてステップＳＡ１０から始まる処理を適用する。前記抽象オブジェクトの集合の要素をすべて処理し終えたらステップＳＡ７に戻る。変数が参照する抽象オブジェクトの集合は、ポインタ解析結果５２のうち、前記変数を含むポインタ解析結果５２に含まれる抽象オブジェクトを集めることにより得られる。本ステップで選択した抽象オブジェクトをa2と呼ぶ。【０１２９】
ステップＳＡ１０では、関数の引数に登場する変数varが、前記選択した抽象オブジェクトa2をコンテキストとして、関数の引数に登場する抽象オブジェクトaを参照するか否かをポインタ解析結果を用いて判定する。参照するならばステップＳＡ１１に、そうでないならばステップＳＡ９に移る。例えば、varとa2とaの３つ組がポインタ解析結果の集合に含まれていれば、varはa2のコンテキストでaを参照すると判定する。【０１３０】
ステップＳＡ１１では、さらに、前記選択したメソッド呼出場所５４に含まれる変数が前記親ノードにより与えられるコンテキストでa2を参照するか否かを判定するために、前記親ノードと前記選択したメソッド呼出場所５４に含まれる変数と、a2と、履歴historyと、depth-1を引数として本関数に適用する。関数の返り値が真ならば真を返し、偽ならばステップＳＡ９に戻る。【０１３１】
以上の手続きにより、オブジェクト・センシティブなポインタ解析結果を用いて、当該変数が当該ノードにより与えられるコンテキストで当該抽象オブジェクトを参照するか否かを判定できる。【０１３２】
図１２のステップＳ６７の他の実施の形態では、メソッドの呼出場所をコンテキストに利用するＣＦＡ型のポインタ解析を利用する。この種のポインタ解析結果は、変数と、メソッド呼出場所と、抽象オブジェクトの３つ組により構成される。１つの実施例では、Ｊａｖａであれば、そのようなポインタ解析結果はＰａｄｄｌｅ（http://www.sable.mcgill.ca/paddle/）という解析基盤を用いることで得られる。【０１３３】
図１４のフローチャートは、ＣＦＡ型のポインタ解析結果を用いた場合に、判定に利用する手続き型の関数の動作を示しており、ステップＳ６７での経路の妥当性を判定するために利用する。関数の引数は、展開したコールグラフ中の特定のノードを示すnode、変数var、抽象オブジェクトa、である。ステップＳ６７は、関数validPathに対して、当該ノードと、当該メソッド呼出場所５４に含まれる変数と、当該抽象オブジェクト５３と、空のリストと、深さを示す数値を与え、その結果が真であれば妥当であると判断し、偽ならば妥当ではないと判断する。深さを示す数値の適切な値は、オブジェクト・センシティブな解析の場合と同様である。【０１３４】
図１４のフローチャートを用いて、関数の動作の詳細を説明する。【０１３５】
最初に、展開したコールグラフ中にnodeの親ノードが存在するか否かを判定し、存在しない場合はコンテキストが得られないのでステップＳＢ５に移る。存在する場合はステップＳＢ２に移る（ステップＳＢ１）。【０１３６】
ステップＳＢ５では、変数varが抽象オブジェクトaを参照するか否かをポインタ解析結果を用いて判定する。varと任意のコンテキスト（空のコンテキストを含む）とaの３つ組がポインタ解析結果の集合に含まれていれば真を返し、そうでないならば偽を返す。【０１３７】
ステップＳＢ２では、nodeの親ノードのうち処理していないものがあれば１つを選択してステップＳＢ３に移る。すべての親ノードを処理した場合は偽を返す。【０１３８】
ステップＳＢ３では、前記親ノードを構成するメソッドに含まれるメソッド呼出場所５４のうち、当該nodeを構成するメソッドをメソッド名として持つようなメソッド呼出場所５４を抽出し、それぞれについてステップＳＢ４の処理を適用する。【０１３９】
ステップＳＢ４では、前記選択されたメソッド呼出場所５４をコンテキストとして、ポインタ解析結果を用いて、前記変数varが前記抽象オブジェクトaを参照するか判定する。判定は、varと前記選択されたメソッド呼出場所５４とaの３つ組がポインタ解析結果に含まれていればvarは本コンテキストでaを指すと判断する。参照する場合は真を返し、参照しない場合はステップＳＢ３に戻る。【０１４０】
以上の手続きにより、ＣＦＡ型のポインタ解析結果を用いて、当該変数が当該ノードにより与えられるコンテキストで当該抽象オブジェクトを参照するか否かを判定できる。【０１４１】
なお、オブジェクト・センシティブなポインタ解析も、ＣＦＡ型のポインタ解析結果も利用するコンテキストの長さに関する指定ができる。前記実施の形態はそれぞれ長さが１の場合の動作を記載したが、長さが１より大きい場合は、親ノードから到達するさらに親のノードを必要なコンテキストの長さに到達するまで探索し、その親ノードの組み合わせについてコンテキストを生成して検査することで、同様に判定できる。
【０１４２】
（第１の実施の形態による効果）
次に、本実施の形態の効果について説明する。
本実施の形態では、ポインタ解析結果を用いてメソッド呼出場所に登場する変数がどの抽象オブジェクトを参照するかを調査するように構成されているため、特定の場所で生成されるオブジェクトに対して発行されるメソッド呼出のパターンを検査できる。
また、本実施の形態では、さらに、展開したコールグラフ上のノード中に登場する変数が検査対象の抽象オブジェクトを参照するか否かを、コンテキストを考慮したポインタ解析結果を用いて判定するように構成されているため、より精度良くパターンを検査できる。【０１４３】
（第２の実施の形態）
次に、本発明の第２の実施の形態について詳細に説明する。【０１４４】
第２の実施の形態では、抽象オブジェクトに対してもコンテキストを考慮したポインタ解析を用いる点が第１の実施の形態と相違する。抽象オブジェクトに対してもコンテキストを考慮したポインタ解析の解析結果であるポインタ解析結果５６は、例えば、図８に示すような構成を有する。【０１４５】
背景技術において説明した関連するパターン検査システムでは、前述した問題点以外に、特定の経路で生成されたオブジェクトを、特定の経路に登場する参照変数が参照するかどうかを判定できないため、異なる実行経路で生成されるオブジェクトを区別してパターンを検査できないという問題点を有していた。本第２の実施の形態によるパターン検査システムは、このような問題点を解消する。【０１４６】
ポインタ解析結果５６は、変数と、コンテキスト１と、抽象オブジェクトと、コンテキスト２の４つ組からなり、コンテキスト１において、変数は、コンテキスト２の場合に生成される抽象オブジェクトを参照すると解釈される。特定のコンテキストで生成されるオブジェクトの集合をコンテキスト抽象オブジェクトと称し、コンテキスト抽象オブジェクト５７は、図９に示すような構成を有する。【０１４７】
第２の実施の形態によるパターン検査システムのパターン検査装置１１の全体構成は、図１に示した第１の実施の形態と同じであり、パターン検査装置１１を構成する各要素の機能が、第１の実施の形態と以下のように相違する。【０１４８】
図１を参照すると、パターン検査装置１１の前処理部１１１が、ポインタ解析結果５２ではなく、図８に示すポインタ解析結果５６の集合を生成し、検査対象プログラム１５から、図９に示すコンテキスト抽象オブジェクト５７の集合を生成する点が第１の実施の形態と相違する。【０１４９】
また、リソース識別部１１２が、パターン検査に関係する抽象オブジェクト５３ではなく、パターン検査に関係するコンテキスト抽象オブジェクト５７を抽出し、抽出したコンテキスト抽象オブジェクト５７の集合の要素一つ一つに対して検査を行う点が第１の実施の形態と相違する。【０１５０】
また、コールグラフ展開部１１３が、抽象オブジェクト５３ではなく、コンテキスト抽象オブジェクト５７を用いて検査に関係するメソッド呼出場所５４を抽出する点が第１の実施の形態と相違する。【０１５１】
また、検査用グラフ生成部１１４が、抽象オブジェクト５３ではなく、コンテキスト抽象オブジェクト５７を用いて変数がコンテキスト抽象オブジェクト５７を参照するか否かを識別する点が第１の実施の形態と相違する。【０１５２】
また、パターン検査部１１５が、抽象オブジェクト５３ではなく、コンテキスト抽象オブジェクト５７を用いて検査対象とするオブジェクトの生成ノードを判定する点が第１の実施の形態と相違する。【０１５３】
次に、図１０のフローチャートを参照して、特に第１の実施の形態と相違する第２の実施の形態の動作を詳細に説明する。【０１５４】
ステップＳ１１の動作は第１の実施の形態と同様である。【０１５５】
ステップＳ１２では、前処理部１１２は、参照変数だけでなく、参照変数が参照するオブジェクトに対してもコンテキストを考慮したポインタ解析を用いてポインタ解析結果５６を生成し、ポインタ解析結果記憶装置１２２に記録する点が第１の実施の形態と相違する。好ましい実施例として、Ｊａｖａであれば、ポインタ解析結果５６は、Ｐａｄｄｌｅ（http://www.sable.mcgill.ca/paddle/）という解析基盤を用いることで得られる。また、ポインタ解析結果５６などを用いてコンテキスト抽象オブジェクト５７をプログラム情報記憶装置１２１に記録する点が第１の実施の形態と相違する。【０１５６】
第２の実施の形態では、抽象オブジェクト５３ではなく、コンテキスト抽象オブジェクト５７に対してどのようなパターンでメソッドが発行されるのかを検査する。【０１５７】
ステップＳ１３では、リソース識別部１１２が、パターン定義１６の検査対象クラス名を用いて、パターン検査を行う必要があるコンテキスト抽象オブジェクト５７の集合を抽出する点が第１の実施の形態と相違する。あるコンテキスト抽象オブジェクト５７があるパターン定義１６に関係するか否かは、コンテキスト抽象オブジェクト５７に含まれる型の情報を用いることにより第１の実施の形態の場合と同様に判定する。【０１５８】
ステップＳ１４では、リソース識別部１１２は、前記抽出したコンテキスト抽象オブジェクト５７の集合の要素を一つずつ取り出し、コールグラフ展開部１１３に渡す点が第１の実施の形態と相違する。【０１５９】
ステップＳ１５の動作をより詳細に示した図１１のフローチャートを用いて、第２の実施の形態の動作を説明する。【０１６０】
ステップＳ５１において検査に関係するメソッド呼出場所５４とメソッドを識別する際に、抽象オブジェクト５３ではなくコンテキスト抽象オブジェクト５７を利用し、またポインタ解析結果５２ではなくポインタ解析結果５６を利用する点が第１の実施の形態と相違する。【０１６１】
メソッド呼出場所５４の変数が、渡されたコンテキスト抽象オブジェクト５７を参照するならば、当該メソッド呼出場所５４は検査に関係する。【０１６２】
メソッド呼出場所５４の変数が前記渡されたコンテキスト抽象オブジェクト５７を参照するか否かは次のようにして判定する。【０１６３】
（１）メソッド呼出場所５４の変数と同じ変数を含むポインタ解析結果５６であること。
（２）前記ポインタ解析結果５６に含まれる抽象オブジェクトとコンテキスト２の組み合わせが前記コンテキスト抽象オブジェクトと等しいこと。
上記のような条件を満たすポインタ解析結果５６が存在すればメソッド呼出場所５４は検査に関係する。【０１６４】
ステップＳ５２は前記検査に関係するメソッド呼出場所５４の集合を用いて処理する。その動作は第１の実施の形態と同様である。また、ステップＳ５３の動作も第１の実施の形態と同様である。【０１６５】
次に、ステップＳ１６の動作をより詳細に示した図１２のフローチャートを用いて、第２の実施の形態の動作を説明する。ここでは、ステップＳ６７の動作のみが第１の実施の形態と相違する。【０１６６】
ステップＳ６７では、利用するポインタ解析結果の種類に依存してその動作が変わる。オブジェクト・センシティブなポインタ解析を用いた場合に利用する第２の実施の形態による判定用の関数の動作を図１５に、ＣＦＡ型のポインタ解析を用いた場合に利用する第２の実施の形態による判定用の関数の動作を図１６にそれぞれ示す。【０１６７】
まず、図１５に示すフローチャートを用いて、その動作の詳細を説明する。【０１６８】
関数cvalidPathは展開したコールグラフのノードnodeと、変数varと、コンテキスト抽象オブジェクトaと、履歴historyと、最大の深さdepthを引数に持つ。cvalidPathは、nodeにより与えられるコンテキストで変数varがコンテキスト抽象オブジェクトaを参照する場合に真を返し、それ以外の場合に偽を返す。【０１６９】
ステップＳＣ１、ＳＣ２，ＳＣ３，ＳＣ４，ＳＣ５，ＳＣ６、ＳＣ７、は図１３に示した第１の実施の形態の関数validPathの動作ステップＳＡ１、ＳＡ２，ＳＡ３，ＳＡ４，ＳＡ５，ＳＡ６、ＳＡ７と、それぞれ同様である。【０１７０】
ステップＳ８は、再帰的に cvalidPathに、ステップＳＣ４で選択された親ノードと、引数として与えられた変数varと,引数として与えられたコンテキスト抽象オブジェクト５７と、history、とdepth-1を引数として適用し、返りが真なら真を返し、偽ならばステップＳＣ４に戻る。【０１７１】
ステップＳＣ９では、ステップＳＣ７で選択されたメソッド呼出場所５４の参照変数が参照する抽象オブジェクト５３の集合を求め、それぞれについてステップＳＣ１０から始まる処理を適用する。【０１７２】
ポインタ解析結果５６を用いてメソッド呼出場所５４の参照変数が参照する抽象オブジェクト５３の集合を求める方法は、次の通りである。
当該メソッド呼出場所５４に含まれる変数と同じ変数を含むポインタ解析結果５６に含まれる抽象オブジェクト５３の集合を算出する。【０１７３】
ステップＳＣ１０では、ポインタ解析結果５６を用いてステップＳＣ９で選択された抽象オブジェクト５３をコンテキストとして、引数で与えられた変数varが、引数で与えられたコンテキスト抽象オブジェクトaを参照するか否かを判定する。【０１７４】
前記変数varと、前記抽象オブジェクト５３と、コンテキスト抽象オブジェクトaに含まれる抽象オブジェクトと、コンテキスト抽象オブジェクトaに含まれるコンテキストの４つ組がポインタ解析結果５６の集合に含まれるならば、変数varはコンテキスト抽象オブジェクトaを前記抽象オブジェクトのコンテキストで参照すると判断する。参照する場合はステップＳＣ１１に進み、そうでない場合はステップＳＣ９に戻る。【０１７５】
ステップＳＣ１１では、第１の実施の形態で用いた図１３に示す関数validPathを、引数として、ステップＳＣ４で選択された親ノードと、ステップＳＣ７で選択されたメソッド呼出場所５４に含まれる変数と、ステップＳＣ９で選択された抽象オブジェクトと、hisotryと、depth-1を用いて適用する。【０１７６】
返り値が真ならば真を返し、偽ならば、ステップＳＣ９に戻る。なお、validPathはポインタ解析５２に対して定義されているものであるが、ポインタ解析５６はポインタ解析５２を包含する情報を有するため、同様に適用可能である。例えば、先に示したように、ポインタ解析結果５６を用いて、ある変数が参照する抽象オブジェクトの集合を算出できる。【０１７７】
次に、図１６に示すフローチャートを用いてＣＦＡ型のポインタ解析を用いた場合に利用する第２の実施の形態による判定用の関数の動作を示す。【０１７８】
cvalidPathは引数として、展開したコールグラフのノードnodeと、変数varと、コンテキスト抽象オブジェクトaを受け取ると、nodeにより与えられるコンテキストで変数varがコンテキスト抽象オブジェクトaを参照する場合に真を返し、それ以外の場合は偽を返す関数である。【０１７９】
ステップＳＤ１，ＳＤ２，ＳＤ３，は図１４に示した第１の実施の形態の関数 validPathの動作ステップＳＢ１，ＳＢ２，ＳＢ３とそれぞれ同様である。【０１８０】
ステップＳＤ４は、ステップＳＤ３選択されたメソッド呼出場所５４をコンテキストとして、ポインタ解析結果５６を用いて、変数varがコンテキスト抽象オブジェクトaを参照するか否かを判定し、参照する場合は真を返し、それ以外の場合はステップＳＤ３に戻る。【０１８１】
変数varと、前記メソッド呼出場所５４と、引数として与えられたコンテキスト抽象オブジェクトa
に含まれる抽象オブジェクトと、引数として与えられたコンテキスト抽象オブジェクトa に含まれるコンテキストの４つ組が、ポインタ解析結果５６に含まれるかを判定し、含まれるならば、varはaを参照すると判定する。【０１８２】
ステップＳＤ５は、変数varがコンテキスト抽象オブジェクトaを参照するか否かをポインタ解析結果５６を用いて判定する。varと、任意のコンテキスト（空のコンテキストを含む）と、aに含まれる抽象オブジェクトと、aに含まれるコンテキストとの４つ組がポインタ解析結果５６の集合に含まれていれば真を返し、そうでないならば偽を返す。【０１８３】
次に、第２の実施の形態のパターン検査（図１０のステップＳ１７）の動作について説明する。【０１８４】
第２の実施の形態のパターン検査部１１５は、関数間に跨った制御フローグラフを生成後に、検査対象オブジェクトを生成する場所を識別する動作のみが第１の実施の形態と相違する。【０１８５】
第２の実施の形態では、検査対象オブジェクトはコンテキスト抽象オブジェクト５７である。生成ノードを識別する方法は抽象オブジェクトのコンテキストとして何を用いるかにより変化する。【０１８６】
ポインタ解析結果５６に含まれるコンテキスト１とコンテキスト２に利用するコンテキストの種類の組み合わせは、オブジェクト・センシティブとオブジェクト・センシティブ、オブジェクト・センシティブとＣＦＡ型、ＣＦＡ型とオブジェクト・センシティブ、ＣＦＡ型とＣＦＡ型の４種類が考えられるが、ＣＦＡ型とオブジェクト・センシティブの組み合わせは意味を成さないため、残る３種類の組み合わせに対する実施の形態を述べる。【０１８７】
まず、参照変数と抽象オブジェクトに対してオブジェクト・センシティブとオブジェクト・センシティブの組み合わせのコンテキストを利用するポインタ解析を用いる実施の形態について説明する。この組み合わせがもっとも好適である。【０１８８】
まず、検査対象のコンテキスト抽象オブジェクト５７に含まれる場所を含むメソッドに対応する展開したコールグラフ中の全てのノードについて検査を行う。【０１８９】
この検査方法は次の通りである。当該コンテキスト抽象オブジェクト５７に含まれるコンテキストが空の場合は真を返し、そうでない場合は、当該ノードの親ノードと、当該ノードの前記親ノードに含まれる当該ノードを構成するメソッドを呼び出すメソッド呼出場所５４の変数varと、当該コンテキスト抽象オブジェクト５７に含まれる抽象オブジェクトとを図１３に示す関数validPathに適用し、返り値が真になるような親ノードに含まれるメソッド呼出場所５４が存在すれば、本検査の結果として真を返し、そうでない場合は偽を返す。検査結果が真になるようなノードについて、当該ノードと前記コンテキスト抽象オブジェクト５７に含まれる場所により識別される関数間制御フローグラフ内のノードを、検査対象オブジェクトを生成するノードとして記録する。【０１９０】
次に、参照変数と抽象オブジェクトに対してオブジェクト・センシティブとＣＦＡ型の組み合わせのコンテキストを利用するポインタ解析、または、ＣＦＡ型とＣＦＡ型の組み合わせのコンテキストを利用するポインタ解析を用いる実施の形態について述べる。【０１９１】
コンテキスト抽象オブジェクト５７に含まれるコンテキストはメソッド呼出場所５４である。まず、検査対象のコンテキスト抽象オブジェクト５７に含まれる場所を含むメソッドに対応する展開したコールグラフ中の全てのノードについて検査を行う。【０１９２】
この検査方法は次の通りである。当該ノードの親ノードに、当該コンテキスト抽象オブジェクト５７に含まれるコンテキストのメソッド呼出場所５４に含まれる場所を含むノードが存在すれば真を返し、そうでないならば偽を返す。検査結果が真になるようなノードについて、当該ノードと前記コンテキスト抽象オブジェクト５７に含まれる場所により識別される関数間制御フローグラフ内のノードを、検査対象オブジェクトを生成するノードとして記録する。【０１９３】
（第２の実施の形態による効果）
次に、第２の実施の形態による効果について説明する。
背景技術において説明した関連するパターン検査システムでは、特定の経路で生成されたオブジェクトを、特定の経路に登場する参照変数が参照するかどうかを判定できないため、異なる実行経路で生成されるオブジェクトを区別してパターンを検査できないという問題があったが、本第２の実施の形態では、同じ場所で生成されるオブジェクトであっても、コンテキストが異なるものを異なる検査対象オブジェクトとして検査するように構成されているため、異なる実行経路で生成されるオブジェクトを区別してパターンを検査できる。【０１９４】
より詳しくは、抽象オブジェクトに対してコンテキストを考慮したポインタ解析結果を用いて、特定のコンテキストで生成される抽象オブジェクトを参照する参照変数により発行されるメソッド呼出のパターンを検査するためである。【０１９５】
なお、本説明中に登場するdepth-1はdepthという変数の値から1を引いた値という意味である。【０１９６】
なお、オブジェクト・センシティブなポインタ解析結果を利用する場合の検査用グラフ生成部１１４は、図１３用いて説明した動作では、関数validPathの処理にhistoryという履歴を用いたが、最大の深さを指定すれば必ずしも履歴を利用する必要はない。従って、図１３のステップＳＡ1、ステップＳＡ５の処理を省略する。【０１９７】
また、図１３に示すvalidPathの処理において、履歴として展開したコールグラフのノードを利用するのではなく、展開したコールグラフと抽象オブジェクトの組を利用しても良い。この場合、図１３に示す処理のステップＳＡ１とステップＳＡ５の処理を無くし、新たに、ステップＳＡ６とＳＡ８の間に、新しいステップを追加する。この新しいステップでは、当該
node とnull との組み合わせが履歴historyに含まれるか否かを判定し、含まれる場合はステップＳＡ４に戻り、含まれない場合は、履歴hisotryに前記nodeとnullとの組を追加してステップＳＡ８の処理に移る。【０１９８】
さらに、ステップＳＡ１０とステップＳＡ１１の間に新しいステップを追加する。この新しいステップでは、当該nodeとステップＳＡ９で選択された抽象オブジェクトとの組が履歴historyに含まれるか否かを判定し、含まれる場合はステップＳＡ９に戻り、含まれない場合は、前記nodeと前記抽象オブジェクトとの組とを履歴hisotryに加えてステップＳＡ１１の処理に移る。これにより履歴に展開されたグラフのノードと抽象オブジェクトとを履歴に用いたvalidPathの処理を実現することができる。【０１９９】
図１５に示すパターン検査部が利用する関数cvalidPathの履歴も同様の修正で展開されたグラフのノードと抽象オブジェクトとの組を履歴に用いることが可能である。【０２００】
以上好ましい実施の形態と実施例をあげて本発明を説明したが、本発明は必ずしも、上記実施の形態及び実施例に限定されるものでなく、その技術的思想の範囲内において様々に変形して実施することができる。【０２０１】
この出願は、２００７年８月２日に出願された日本出願特願２００７−２０１５８４を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０２０２】
本発明によれば、プログラム中からパターン定義に違反する部位を検出するパターン検査装置や、パターンを検査する機能をプログラム開発環境の警告機能、補完機能といった用途にも適用できる。
【図１】
2009017231.tif 000002
【図２】
2009017231.tif 000003
【図３】
2009017231.tif 000004
【図４】
2009017231.tif 000005
【図５】
2009017231.tif 000006
【図６】
2009017231.tif 000007
【図７】
2009017231.tif 000008
【図８】
2009017231.tif 000009
【図９】
2009017231.tif 000010
【図１０】
2009017231.tif 000011
【図１１】
2009017231.tif 000012
【図１２】
2009017231.tif 000013
【図１３】
2009017231.tif 000014
【図１４】
2009017231.tif 000015
【図１５】
2009017231.tif 000016
【図１６】
2009017231.tif 000017
【図１７】
2009017231.tif 000018
【手続補正書】
【提出日】平成21年2月26日(2009.2.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
（削除）
【請求項２】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査システムであって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いされている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出する抽出手段と、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を判定する判定手段と、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査する検査手段と、
前記検査の結果を出力する出力手段と
を備えたことを特徴とするパターン検査システム。
【請求項３】
前記コンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する手段と、
前記プログラムのポインタ解析結果を記憶するポインタ解析結果記憶装置と、
前記抽象オブジェクトと前記メソッド呼出場所と前記制御フローグラフとを記憶するプログラム情報記憶装置とを備えることを特徴とする請求項２に記載のパターン検査システム。
【請求項４】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査システムであって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出するリソース識別部と、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するコールグラフ展開部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記抽象オブジェクトを参照するか否かを判定する機能を備えた検査用グラフ生成部と、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するパターン検査部と、
前記検査の結果を出力する出力部と
を備えたことを特徴とするパターン検査システム。
【請求項５】
前記コンテキストを考慮したポインタ解析を適用しポインタ解析結果を取得する手段と、
前記ポインタ解析結果を記憶するポインタ解析結果記憶装置と、
前記抽象オブジェクトと前記メソッド呼出場所と前記制御フローグラフと前記コールグラフとを記憶するプログラム情報記憶装置とを備えることを特徴とする請求項４に記載のパターン検査システム。
【請求項６】
オブジェクト・センシティブなポインタ解析によって得られる前記ポインタ解析結果を利用することを特徴とする請求項２から請求項５の何れか１項に記載のパターン検査システム。
【請求項７】
ＣＦＡ型のポインタ解析による前記ポインタ解析結果を利用することを特徴とする請求項２から請求項５の何れか１項に記載のパターン検査システム。
【請求項８】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査システムであって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられているコンテキスト抽象オブジェクトから前記検査対象のクラス名に関係するコンテキスト抽象オブジェクトを抽出するリソース識別部と、
コンテキストを考慮したポインタ解析を行って、前記抽出されたコンテキスト抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するコールグラフ展開部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記コンテキスト抽象オブジェクトを参照するか否かを判定する機能を備えた検査用グラフ生成部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記コンテキスト抽象オブジェクトが生成されるか否かを判定し、前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するパターン検査部と、
前記検査の結果を出力する出力部と
を備えたことを特徴とするパターン検査システム。
【請求項９】
参照変数と抽象オブジェクトに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する手段と、
前記ポインタ解析結果を記憶するポインタ解析結果記憶装置と、
前記コンテキスト抽象オブジェクトと前記メソッド呼出場所と前記制御フローグラフと前記コールグラフとを記憶するプログラム情報記憶装置とを備えることを特徴とする請求項８に記載のパターン検査システム。
【請求項１０】
（削除）
【請求項１１】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査装置であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いされている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出する抽出手段と、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を判定する判定手段と、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査する検査手段と、
前記検査の結果を出力する出力手段と
を備えたことを特徴とするパターン検査装置。
【請求項１２】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査装置であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出するリソース識別部と、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するコールグラフ展開部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記抽象オブジェクトを参照するか否かを判定する機能を備えた検査用グラフ生成部と、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するパターン検査部と、
前記検査の結果を出力する出力部と
を備えたことを特徴とするパターン検査装置。
【請求項１３】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査装置であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられているコンテキスト抽象オブジェクトから前記検査対象のクラス名に関係するコンテキスト抽象オブジェクトを抽出するリソース識別部と、
前記プログラムの参照変数と抽象オブジェクトに対してコンテキストを考慮したポインタ解析を行って、前記抽出されたコンテキスト抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するコールグラフ展開部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記コンテキスト抽象オブジェクトを参照するか否かを判定する機能を備えた検査用グラフ生成部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記コンテキスト抽象オブジェクトが生成されるか否かを判定し、前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するパターン検査部と、
前記検査の結果を出力する出力部と
を備えたことを特徴とするパターン検査装置。
【請求項１４】
（削除）
【請求項１５】
コンピュータによって、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査方法であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いされている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出するステップと、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を判定するステップと、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するステップと、
前記検査の結果を出力するステップと
を備えることを特徴とするパターン検査方法。
【請求項１６】
前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得するステップを含むことを特徴とする請求項１５に記載のパターン検査方法。
【請求項１７】
コンピュータによって、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査方法であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出するステップと、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するステップと、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記抽象オブジェクトを参照するか否かを判定するステップと、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するステップと、
前記検査の結果を出力するステップと
を備えることを特徴とするパターン検査方法。
【請求項１８】
前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得するステップを含むことを特徴とする請求項１７に記載のパターン検査方法。
【請求項１９】
オブジェクト・センシティブなポインタ解析によって得られる前記ポインタ解析結果を利用することを特徴とする請求項１５から請求項１８の何れか１項に記載のパターン検査方法。
【請求項２０】
ＣＦＡ型のポインタ解析による前記ポインタ解析結果を利用することを特徴とする請求項１５から請求項１８の何れか１項に記載のパターン検査方法。
【請求項２１】
コンピュータによって、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査方法であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられているコンテキスト抽象オブジェクトから前記検査対象のクラス名に関係するコンテキスト抽象オブジェクトを抽出するステップと、
コンテキストを考慮したポインタ解析を行って、前記抽出されたコンテキスト抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するステップと、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記コンテキスト抽象オブジェクトを参照するか否かを判定するステップと、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記コンテキスト抽象オブジェクトが生成されるか否かを判定し、前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するステップと、
前記検査の結果を出力するステップと
を備えることを特徴とするパターン検査方法。
【請求項２２】
参照変数と抽象オブジェクトに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得するステップを含むことを特徴とする請求項２１に記載のパターン検査方法。
【請求項２３】
（削除）
【請求項２４】
コンピュータ上で実行され、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記パターン検査プログラムが、
前記プログラムで用いされている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出する処理と、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を判定する処理と、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査する処理と、
前記検査の結果を出力するステップとを
前記コンピュータに実行させることを特徴とする記録媒体。
【請求項２５】
前記パターン検査プログラムが、前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する処理を含むことを特徴とする請求項２４に記載の記録媒体。
【請求項２６】
コンピュータ上で実行され、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記パターン検査プログラムが、
前記プログラムで用いられている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出する処理と、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成する処理と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記抽象オブジェクトを参照するか否かを判定する処理と、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査する処理と、
前記検査の結果を出力するステップとを
前記コンピュータに実行させることを特徴とする記録媒体。
【請求項２７】
前記パターン検査プログラムが、前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する処理を含むことを特徴とする請求項２６に記載のパターン検査方法。
【請求項２８】
前記パターン検査プログラムが、オブジェクト・センシティブなポインタ解析によって得られる前記ポインタ解析結果を利用することを特徴とする請求項２４から請求項２７の何れか１項に記載の記録媒体。
【請求項２９】
前記パターン検査プログラムが、ＣＦＡ型のポインタ解析による前記ポインタ解析結果を利用することを特徴とする請求項２４から請求項２７の何れか１項に記載の記録媒体。
【請求項３０】
コンピュータ上で実行され、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記パターン検査プログラムが、
前記プログラムで用いられているコンテキスト抽象オブジェクトから前記検査対象のクラス名に関係するコンテキスト抽象オブジェクトを抽出するステップと、
コンテキストを考慮したポインタ解析を行って、前記抽出されたコンテキスト抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するステップと、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記コンテキスト抽象オブジェクトを参照するか否かを判定するステップと、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記コンテキスト抽象オブジェクトが生成されるか否かを判定し、前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するステップと、
前記検査の結果を出力するステップとを
前記コンピュータに実行させることを特徴とする記録媒体。
【請求項３１】
前記パターン検査プログラムが、参照変数と抽象オブジェクトに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する処理を含むことを特徴とする請求項３０に記載の記録媒体。
【手続補正書】
【提出日】平成21年6月22日(2009.6.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
（削除）
【請求項２】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査システムであって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出する抽出手段と、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を判定する判定手段と、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査する検査手段と、
前記検査の結果を出力する出力手段と
を備えたことを特徴とするパターン検査システム。
【請求項３】
前記コンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する手段と、
前記プログラムのポインタ解析結果を記憶するポインタ解析結果記憶装置と、
前記抽象オブジェクトと前記メソッド呼出場所と前記制御フローグラフとを記憶するプログラム情報記憶装置とを備えることを特徴とする請求項２に記載のパターン検査システム。
【請求項４】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査システムであって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出するリソース識別部と、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するコールグラフ展開部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記抽象オブジェクトを参照するか否かを判定する機能を備えた検査用グラフ生成部と、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するパターン検査部と、
前記検査の結果を出力する出力部と
を備えたことを特徴とするパターン検査システム。
【請求項５】
前記コンテキストを考慮したポインタ解析を適用しポインタ解析結果を取得する手段と、
前記ポインタ解析結果を記憶するポインタ解析結果記憶装置と、
前記抽象オブジェクトと前記メソッド呼出場所と前記制御フローグラフと前記コールグラフとを記憶するプログラム情報記憶装置とを備えることを特徴とする請求項４に記載のパターン検査システム。
【請求項６】
オブジェクト・センシティブなポインタ解析によって得られる前記ポインタ解析結果を利用することを特徴とする請求項２から請求項５の何れか１項に記載のパターン検査システム。
【請求項７】
ＣＦＡ型のポインタ解析による前記ポインタ解析結果を利用することを特徴とする請求項２から請求項５の何れか１項に記載のパターン検査システム。
【請求項８】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査システムであって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられているコンテキスト抽象オブジェクトから前記検査対象のクラス名に関係するコンテキスト抽象オブジェクトを抽出するリソース識別部と、
コンテキストを考慮したポインタ解析を行って、前記抽出されたコンテキスト抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するコールグラフ展開部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記コンテキスト抽象オブジェクトを参照するか否かを判定する機能を備えた検査用グラフ生成部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記コンテキスト抽象オブジェクトが生成されるか否かを判定し、前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するパターン検査部と、
前記検査の結果を出力する出力部と
を備えたことを特徴とするパターン検査システム。
【請求項９】
参照変数と抽象オブジェクトに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する手段と、
前記ポインタ解析結果を記憶するポインタ解析結果記憶装置と、
前記コンテキスト抽象オブジェクトと前記メソッド呼出場所と前記制御フローグラフと前記コールグラフとを記憶するプログラム情報記憶装置とを備えることを特徴とする請求項８に記載のパターン検査システム。
【請求項１０】
（削除）
【請求項１１】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査装置であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出する抽出手段と、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を判定する判定手段と、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査する検査手段と、
前記検査の結果を出力する出力手段と
を備えたことを特徴とするパターン検査装置。
【請求項１２】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査装置であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出するリソース識別部と、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するコールグラフ展開部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記抽象オブジェクトを参照するか否かを判定する機能を備えた検査用グラフ生成部と、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するパターン検査部と、
前記検査の結果を出力する出力部と
を備えたことを特徴とするパターン検査装置。
【請求項１３】
オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査装置であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられているコンテキスト抽象オブジェクトから前記検査対象のクラス名に関係するコンテキスト抽象オブジェクトを抽出するリソース識別部と、
前記プログラムの参照変数と抽象オブジェクトに対してコンテキストを考慮したポインタ解析を行って、前記抽出されたコンテキスト抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するコールグラフ展開部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記コンテキスト抽象オブジェクトを参照するか否かを判定する機能を備えた検査用グラフ生成部と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記コンテキスト抽象オブジェクトが生成されるか否かを判定し、前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するパターン検査部と、
前記検査の結果を出力する出力部と
を備えたことを特徴とするパターン検査装置。
【請求項１４】
（削除）
【請求項１５】
コンピュータによって、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査方法であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出するステップと、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を判定するステップと、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するステップと、
前記検査の結果を出力するステップと
を備えることを特徴とするパターン検査方法。
【請求項１６】
前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得するステップを含むことを特徴とする請求項１５に記載のパターン検査方法。
【請求項１７】
コンピュータによって、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査方法であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出するステップと、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するステップと、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記抽象オブジェクトを参照するか否かを判定するステップと、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するステップと、
前記検査の結果を出力するステップと
を備えることを特徴とするパターン検査方法。
【請求項１８】
前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得するステップを含むことを特徴とする請求項１７に記載のパターン検査方法。
【請求項１９】
オブジェクト・センシティブなポインタ解析によって得られる前記ポインタ解析結果を利用することを特徴とする請求項１５から請求項１８の何れか１項に記載のパターン検査方法。
【請求項２０】
ＣＦＡ型のポインタ解析による前記ポインタ解析結果を利用することを特徴とする請求項１５から請求項１８の何れか１項に記載のパターン検査方法。
【請求項２１】
コンピュータによって、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査方法であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記プログラムで用いられているコンテキスト抽象オブジェクトから前記検査対象のクラス名に関係するコンテキスト抽象オブジェクトを抽出するステップと、
コンテキストを考慮したポインタ解析を行って、前記抽出されたコンテキスト抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するステップと、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記コンテキスト抽象オブジェクトを参照するか否かを判定するステップと、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記コンテキスト抽象オブジェクトが生成されるか否かを判定し、前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するステップと、
前記検査の結果を出力するステップと
を備えることを特徴とするパターン検査方法。
【請求項２２】
参照変数と抽象オブジェクトに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得するステップを含むことを特徴とする請求項２１に記載のパターン検査方法。
【請求項２３】
（削除）
【請求項２４】
コンピュータ上で実行され、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記パターン検査プログラムが、
前記プログラムで用いられている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出する処理と、
コンテキストを考慮したポインタ解析を行って、前記抽出された抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を判定する処理と、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査する処理と、
前記検査の結果を出力するステップとを
前記コンピュータに実行させることを特徴とする記録媒体。
【請求項２５】
前記パターン検査プログラムが、前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する処理を含むことを特徴とする請求項２４に記載の記録媒体。
【請求項２６】
コンピュータ上で実行され、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記パターン検査プログラムが、
前記プログラムで用いられている抽象オブジェクトから前記検査対象のクラス名に関係する抽象オブジェクトを抽出する処理と、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記抽象オブジェクトを参照するか否かを判定する処理と、
前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査する処理と、
前記検査の結果を出力するステップとを
前記コンピュータに実行させることを特徴とする記録媒体。
【請求項２７】
前記パターン検査プログラムが、前記プログラムに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する処理を含むことを特徴とする請求項２６に記載のパターン検査方法。
【請求項２８】
前記パターン検査プログラムが、オブジェクト・センシティブなポインタ解析によって得られる前記ポインタ解析結果を利用することを特徴とする請求項２４から請求項２７の何れか１項に記載の記録媒体。
【請求項２９】
前記パターン検査プログラムが、ＣＦＡ型のポインタ解析による前記ポインタ解析結果を利用することを特徴とする請求項２４から請求項２７の何れか１項に記載の記録媒体。
【請求項３０】
コンピュータ上で実行され、オブジェクト指向型言語で記述されたプログラムを対象に、当該プログラムを実行する際に生成されるオブジェクトに発行されるメソッドの呼出しパターンを検査するパターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体であって、
検査対象のクラス名と検査対象のメソッドの呼出しパターンを定義するパターン定義のデータを備え、
前記パターン検査プログラムが、
前記プログラムで用いられているコンテキスト抽象オブジェクトから前記検査対象のクラス名に関係するコンテキスト抽象オブジェクトを抽出するステップと、
コンテキストを考慮したポインタ解析を行って、前記抽出されたコンテキスト抽象オブジェクトに発行されるメソッドの呼出しを行うメソッド呼出場所を識別し、展開したコールグラフを生成するステップと、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記メソッド呼出場所に含まれる変数が前記コンテキスト抽象オブジェクトを参照するか否かを判定するステップと、
前記展開したコールグラフの各ノードにより与えられるコンテキストで前記コンテキスト抽象オブジェクトが生成されるか否かを判定し、前記メソッド呼出場所に用いたメソッド間に跨ったメソッドの呼出しの制御フローグラフを作成し、これにデータフロー解析を行って前記メソッドの呼出しパターンが前記検査対象の呼出しパターンに従っているか検査するステップと、
前記検査の結果を出力するステップとを
前記コンピュータに実行させることを特徴とする記録媒体。
【請求項３１】
前記パターン検査プログラムが、参照変数と抽象オブジェクトに対してコンテキストを考慮したポインタ解析を適用し前記ポインタ解析結果を取得する処理を含むことを特徴とする請求項３０に記載の記録媒体。
【請求項３２】
オブジェクト指向型言語で記述された検査対象のプログラムに対してコンテキストを考慮したポインタ解析を適用して、前記プログラム中でメソッド呼出場所、オブジェクトの生成場所、およびメソッド呼出しの関係を記録したコールグラフから構成されるプログラム情報をプログラム情報記憶装置に保存し、前記コンテキストを有するポインタ解析結果をポインタ解析結果記憶装置に保存する前処理部と、
前記プログラム情報記憶装置に格納された、前記オブジェクトに対して発行される前記メソッドの呼出しパターン規則を記述したパターン定義を読み出し、前記プログラム情報記憶装置から前記オブジェクトの生成場所を読み込み、前記パターン定義により指定された検査対象となる前記オブジェクトの生成場所を識別するリソース識別部と、
前記ポインタ解析結果を用いて、前記オブジェクトに対して関係する前記メソッドの呼出場所を識別し、前記コールグラフから前記メソッドの呼出場所に関係する展開したコールグラフを生成するコールグラフ展開部と、
前記展開したコールグラフの各ノードにより与えられる前記コンテキストで前記メソッド呼出場所に含まれる変数が前記オブジェクトを参照するか否かを判定する検査用グラフを生成する検査用グラフ生成部と、
前記検査用グラフと前記メソッドの呼出場所から関数間制御フローグラフを構築し、前記オブジェクトに対して発行される前記メソッドの呼出のパターンが、前記パターン定義に従うか否かを判定検査するパターン検査部と、
を備えたことを特徴とするパターン検査システム。
【請求項３３】
オブジェクト指向型言語で記述された検査対象のプログラムに対してコンテキストを考慮したポインタ解析を適用して、前記プログラム中でメソッドの呼出しが発生する場所を記録したメソッド呼出場所、オブジェクトの生成場所と生成される前記オブジェクトの型とを関係付けて記録した抽象オブジェクト、および前記メソッド呼出しの関係を記録したコールグラフから構成されるプログラム情報をプログラム情報記憶装置に保存し、変数とコンテキストと前記抽象オブジェクトの３つ組から構成されるポインタ解析結果をポインタ解析結果記憶装置に保存する前処理部と、
前記プログラム情報記憶装置に格納された、前記オブジェクトに対して発行される前記メソッドの呼出しパターン規則を記述し、呼出しパターンを守るべきオブジェクトのクラスを示す検査対象クラス名と、前記パターンに関係するメソッドの集合を示す検査対象メソッドと、前記メソッドが前記オブジェクトに対して発行される際に守られるべき検査パターンから構成されるパターン定義を読み出し、前記プログラム情報記憶装置から前記オブジェクトの生成場所を読み込み、前記検査対象クラス名と一致する検査対象となる前記抽象オブジェクトの生成場所の集合を抽出するリソース識別部と、
前記プログラム情報記憶装置から前記メソッド呼出場所の集合を読み込み、ポインタ解析結果記憶装置から前記ポインタ解析結果の集合を読み込むと、前記メソッド呼出場所の集合から、前記抽象オブジェクトに関係する前記メソッド呼出場所を抽出し、前記コールグラフから前記関係する前記メソッド呼出場所からなる展開したコールグラフを生成するコールグラフ展開部と、
前記コールグラフ展開部より前記展開したコールグラフと、前記抽象オブジェクトと、前記抽象オブジェクトの検査に関係する前記メソッド呼出場所の集合とを受け付けると、前記ポインタ解析結果記憶装置から前記ポインタ解析結果を読み込み、前記展開したコールグラフの各ノードにより与えられる前記コンテキストで前記メソッド呼出場所に含まれる変数が前記オブジェクトを参照するか否かを判定する検査用グラフを生成する検査用グラフ生成部と、
前記検査用グラフと前記メソッドの呼出場所から関数間制御フローグラフを構築し、前記オブジェクトに対して発行される前記メソッドの呼出のパターンが、前記パターン定義に従うか否かを、検査対象である前記抽象オブジェクトを参照する可能性がある当前記メソッド呼出場所の前記変数が、前記展開したコールグラフにおけるノードにより与えられる前記コンテキストにおいて前記抽象オブジェクトを参照するか否かを、前記ポインタ解析結果を用いて判定するパターン検査部と、
を備えたことを特徴とするパターン検査システム。
【請求項３４】
前記前処理部が、抽象オブジェクトに対してもコンテキストを考慮したポインタ解析を行い、
前記パターン検査部が、関数間に跨った制御フローグラフを生成後に、検査対象オブジェクトを生成する場所を識別することを特徴とする請求項３２または３３に記載のパターン検査システム。
【請求項３５】
オブジェクト指向型言語で記述された検査対象のプログラムに対してコンテキストを考慮したポインタ解析を適用して、前記プログラム中でメソッド呼出場所、オブジェクトの生成場所、およびメソッド呼出しの関係を記録したコールグラフから構成されるプログラム情報をプログラム情報記憶装置に保存し、前記コンテキストを有するポインタ解析結果をポインタ解析結果記憶装置に保存するステップと、
前記プログラム情報記憶装置に格納された、前記オブジェクトに対して発行される前記メソッドの呼出しパターン規則を記述したパターン定義を読み出し、前記プログラム情報記憶装置から前記オブジェクトの生成場所を読み込み、前記パターン定義により指定された検査対象となる前記オブジェクトの生成場所を識別するステップと、
前記ポインタ解析結果を用いて、前記オブジェクトに対して関係する前記メソッドの呼出場所を識別し、前記コールグラフから前記メソッドの呼出場所に関係する展開したコールグラフを生成するステップと、
前記展開したコールグラフの各ノードにより与えられる前記コンテキストで前記メソッド呼出場所に含まれる変数が前記オブジェクトを参照するか否かを判定する検査用グラフを生成するステップと、、
前記検査用グラフと前記メソッドの呼出場所から関数間制御フローグラフを構築し、前記オブジェクトに対して発行される前記メソッドの呼出のパターンが、前記パターン定義に従うか否かを判定検査するステップと
を備えたことを特徴とするパターン検査方法。
【請求項３６】
パターン検査プログラムを格納するコンピュータ読み取り可能な記録媒体であって、
前記パターン検査プログラムが、
オブジェクト指向型言語で記述された検査対象のプログラムに対してコンテキストを考慮したポインタ解析を適用して、前記プログラム中でメソッド呼出場所、オブジェクトの生成場所、およびメソッド呼出しの関係を記録したコールグラフから構成されるプログラム情報をプログラム情報記憶装置に保存し、前記コンテキストを有するポインタ解析結果をポインタ解析結果記憶装置に保存する処理と、
前記プログラム情報記憶装置に格納された、前記オブジェクトに対して発行される前記メソッドの呼出しパターン規則を記述したパターン定義を読み出し、前記プログラム情報記憶装置から前記オブジェクトの生成場所を読み込み、前記パターン定義により指定された検査対象となる前記オブジェクトの生成場所を識別する処理と、
前記ポインタ解析結果を用いて、前記オブジェクトに対して関係する前記メソッドの呼出場所を識別し、前記コールグラフから前記メソッドの呼出場所に関係する展開したコールグラフを生成する処理と、
前記展開したコールグラフの各ノードにより与えられる前記コンテキストで前記メソッド呼出場所に含まれる変数が前記オブジェクトを参照するか否かを判定する検査用グラフを生成する処理と、
前記検査用グラフと前記メソッドの呼出場所から関数間制御フローグラフを構築し、前記オブジェクトに対して発行される前記メソッドの呼出のパターンが、前記パターン定義に従うか否かを判定検査する処理とを
コンピュータに実行させることを特徴とする記録媒体。