(57)【特許請求の範囲】
【請求項１】
イリーガル・パターンとターゲット・メソッドを有するコンピュータ・プログラムとをプロセッサによって受け取るステップであって、前記ターゲット・メソッドは１つ又は複数個のリターン・ステートメント及び複数個の基本ブロックを有する、前記受け取るステップと、
前記イリーガル・パターンに関連する前記ターゲット・メソッドの各リターン・ステートメントが一定のブール値を返送するように、前記ターゲット・メソッドを前記プロセッサによって正規化するステップと、
１つ又は複数個の対応する基本ブロックが真の一定のブール値を返送するように、正規化されたターゲット・メソッドの１つ又は複数個の対応するパスに対する第１のパス条件を前記プロセッサによって決定するステップと、
単項２階ロジック（Ｍ２Ｌ）技法を使って前記第１のパス条件の不充足可能性を前記プロセッサによって決定するステップであって、前記第１のパス条件の不充足可能性は、当該第１のパス条件が、イリーガル・パターンを含む入力ストリングに関して真の一定のブール値を常に返送するかどうかを判断し、前記第１のパス条件の不充足可能性が偽であることは、当該第１のパス条件が、イリーガル・パターンを含む入力ストリングに関して真の一定のブール値を必ずしも返送するとは限らないということを意味し、前記第１のパス条件の不充足可能性が真であることは、当該第１のパス条件が、イリーガル・パターンを含む入力ストリングに関して真の一定のブール値を返送しないということを意味する、前記決定するステップと、
前記第１のパス条件の不充足可能性が偽である場合、前記ターゲット・メソッドが有益なバリデータではないということを前記プロセッサによって報告するステップと
を含む方法。
【請求項２】
バリデータは、入力ストリングが前記コンピュータ・プログラムにおけるセキュリティ・センシティブなオペレーションに関連して安全に使用され得るか否かを判断するためのプロセスである、請求項１に記載の方法。
【請求項３】
前記第１のパス条件の不充足可能性が真である場合、前記ターゲット・メソッドが有益なバリデータであるということを前記プロセッサによって報告するステップを更に含む、請求項１に記載の方法。
【請求項４】
前記１つ又は複数個の対応する基本ブロックが偽の一定のブール値を返送するように、前記正規化されたターゲット・メソッドの１つ又は複数個の対応するパスに対する第２のパス条件を前記プロセッサによって決定するステップと、
前記第２のパス条件の不充足可能性を、前記Ｍ２Ｌ技法を使って前記プロセッサによって決定するステップと
を更に含む、請求項１に記載の方法。
【請求項５】
前記第２のパス条件の不充足可能性が偽である場合、前記ターゲット・メソッドが無益なバリデータでないということを前記プロセッサによって報告するステップを更に含む、請求項４に記載の方法。
【請求項６】
前記第２のパス条件の不充足可能性が真である場合、前記ターゲット・メソッドが無益なバリデータであるということを前記プロセッサによって報告するステップを更に含む、請求項５に記載の方法。
【請求項７】
前記第１のパス条件の不充足可能性を決定するステップは、
前記１つ又は複数個の対応するパスにおける変数に対して可能なストリングのセットを決定するステップであって、前記変数は、前記１つ又は複数個の対応するパスにおけるブランチ条件によって抑制され、前記ターゲット・メソッドの入力パラメータは前記イリーガル・パターンにマッチするストリングであると仮定される、前記決定するステップ
を含む、請求項１に記載の方法。
【請求項８】
前記第１のパス条件の不充足可能性を決定するステップは、
１つ又は複数個のパス条件を使って前記変数を抑制するステップ
を更に含む、請求項７に記載の方法。
【請求項９】
前記第１のパス条件の不充足可能性を決定するステップは、
前記パス条件によって抑制された変数及び当該変数に対する決定された可能なストリングのセットに対応する前記第１のパス条件の不充足可能性を、前記Ｍ２Ｌ技法を使って決定するステップ
を更に含む、請求項８に記載の方法。
【請求項１０】
コンピュータ可読記憶媒体に格納され、プロセッサによって実行されることにより１つの方法を遂行するコンピュータ・プログラムであって、前記方法は、
イリーガル・パターンとターゲット・メソッドを有するターゲット・コンピュータ・プログラムとを受け取るステップであって、前記ターゲット・メソッドは複数個の基本ブロックを有する、前記受け取るステップと、
前記イリーガル・パターンに関連する前記ターゲット・メソッドの各リターン・ステートメントが一定のブール値を返送するように、前記ターゲット・メソッドを正規化するステップと、
正規化された前記ターゲット・メソッドの１つ又は複数個の対応する第１のパス条件及び第２のパス条件を、１つ又は複数個の対応する基本ブロックが前記第１のパス条件に対して真の一定のブール値を返送するように及び前記第２のパス条件に対して偽の一定のブール値を返送するように、決定するステップと、
単項２階ロジック（Ｍ２Ｌ）技法を使って前記第１のパス条件の不充足可能性及び前記第２のパス条件の不充足可能性を決定するステップであって、前記第１のパス条件の不充足可能性は、当該第１のパス条件が、イリーガル・パターンを含む入力ストリングに関して真の一定のブール値を常に返送するかどうかを判断し、前記第１のパス条件の不充足可能性が偽であることは、当該第１のパス条件が、イリーガル・パターンを含む入力ストリングに関して真の一定のブール値を必ずしも返送するとは限らないということを意味し、前記第１のパス条件の不充足可能性が真であることは、当該第１のパス条件が、イリーガル・パターンを含む入力ストリングに関して真の一定のブール値を返送しないということを意味し、前記第２のパス条件の不充足可能性は、当該第２のパス条件が、イリーガル・パターンを含む入力ストリングに関して偽のブール値を常に返送するかどうかを判断し、前記第２のパス条件の不充足可能性が偽であることは、当該第２のパス条件が、イリーガル・パターンを含む入力ストリングに関して偽の一定のプール値を必ずしも返送するとは限らないということを意味し、前記第２のパス条件の不充足可能性が真であることは、当該第２のパス条件が、イリーガル・パターンを含む入力ストリングに関して偽の一定のプール値を返送しないということを意味する、前記決定するステップと、
前記第１のパス条件の不充足可能性が偽である場合、前記ターゲット・メソッドが有益なバリデータではないということを報告するステップと、
前記第１のパス条件の不充足可能性が真である場合、前記ターゲット・メソッドが有益なバリデータであるということを報告するステップと、
前記第２のパス条件の不充足可能性が偽である場合、前記ターゲット・メソッドが無益なバリデータでないということを報告するステップと、
前記第２のパス条件の不充足可能性が真である場合、前記ターゲット・メソッドが無益なバリデータであるということを報告するステップと
を含む、コンピュータ・プログラム。
【請求項１１】
前記バリデータは、入力ストリングが前記コンピュータ・プログラムにおけるセキュリティ・センシティブなオペレーションに関連して安全に使用され得るか否かを判断するためのプロセスである、請求項１０に記載のコンピュータ・プログラム。
【請求項１２】
前記第１のパス条件及び前記第２のパス条件の不充足可能性を決定するステップは、
前記１つ又は複数個の対応するパスにおける変数に対して可能なストリングのセットを決定するステップであって、前記変数は、前記１つ又は複数個の対応するパスにおけるブランチ条件によって抑制され、前記ターゲット・メソッドの入力パラメータは前記イリーガル・パターンにマッチするストリングであると仮定される、前記決定するステップ
を含む、請求項１０に記載のコンピュータ・プログラム。
【請求項１３】
前記第１のパス条件及び前記第２のパス条件の不充足可能性を決定するステップは、
１つ又は複数個のパス条件を使って前記変数を抑制するステップ
を更に含む、請求項１２に記載のコンピュータ・プログラム。
【請求項１４】
前記第１のパス条件及び前記第２のパス条件の不充足可能性を決定するステップは、
前記パス条件によって抑制された変数及び当該変数に対する決定された可能なストリングのセットに対応するパス条件の不充足可能性を、前記Ｍ２Ｌ技法を使って決定するステップ
を更に含む、請求項１３に記載のコンピュータ・プログラム。
【請求項１５】
プロセッサと、
イリーガル・パターンと、複数個の基本ブロックを有するターゲット・メソッドを持ったターゲット・コンピュータ・プログラムとを格納するコンピュータ可読データ記憶装置と、
少なくともハードウェアによって具現化されたバリデータ決定コンポーネントであって、
（ａ）前記イリーガル・パターンに関連するターゲット・メソッドの各リターン・ステートメントが一定のブール値を返送するように、前記ターゲット・メソッドを正規化し、
（ｂ）１つ又は複数個の対応する基本ブロックが真の一定のブール値を返送するように、正規化されたターゲット・メソッドの１つ又は複数個の対応するパスに対して第１のパス条件を決定し、
（ｃ）単項２階ロジック（Ｍ２Ｌ）技法を使って前記第１のパス条件の不充足可能性を決定し、前記第１のパス条件の不充足可能性は、当該第１のパス条件が、イリーガル・パターンを含む入力ストリングに関して真の一定のブール値を常に返送するかどうかを判断し、前記第１のパス条件の不充足可能性が偽であることは、当該第１のパス条件が、イリーガル・パターンを含む入力ストリングに関して真の一定のブール値を必ずしも返送するとは限らないということを意味し、前記第１のパス条件の不充足可能性が真であることは、当該第１のパス条件が、イリーガル・パターンを含む入力ストリングに関して真の一定のブール値を返送しないということを意味し、
（ｄ）前記第１のパス条件の不充足可能性が偽である場合、前記ターゲット・メソッドが有益なバリデータでないということを報告する、
前記バリデータ決定コンポーネントと、
を含むシステム。
【請求項１６】
前記バリデータは、入力ストリングが前記コンピュータ・プログラムにおけるセキュリティ・センシティブ・オペレーションに関連して安全に使用され得るか否かを判断するためのプロセスである、請求項１５に記載のシステム。
【請求項１７】
前記バリデータ決定コンポーネントは、前記第１のパス条件の不充足可能性が真である場合、前記ターゲット・メソッドが有益なバリデータであるということを報告するものである、請求項１５に記載のシステム。
【請求項１８】
前記バリデータ決定コンポーネントは、前記１つ又は複数個の対応するパスにおける変数に対する可能なストリングのセットを決定することによって前記第１のパス条件の不充足可能性を決定するものであり、
前記変数は、前記１つ又は複数個の対応するパスにおけるブランチ条件によって抑止され、前記ターゲット・メソッドの入力パラメータは前記イリーガル・パターンにマッチするストリングであると仮定される、請求項１５に記載のシステム。
【請求項１９】
前記バリデータ決定コンポーネントは、１つ又は複数個のパス条件を使って前記変数を抑制することによって前記第１のパス条件の不充足可能性を決定するものである、請求項１８に記載のシステム。
【請求項２０】
前記バリデータ決定コンポーネントは、前記パス条件によって抑制された変数及び当該変数に対する決定された可能なストリングのセットに対応する前記第１のパス条件の不充足可能性を、前記Ｍ２Ｌ技法を使って決定することにより、前記パス条件の不充足可能性を決定するものである、請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ・プログラムのメソッドがバリデータであるかどうかを判断する方法及びシステムに関する。
【背景技術】
【０００２】
バリデータ（validator）は、イントラネットおよびインターネット上のウェブ・アプリケーションに関連してセキュリティ・センシティブなオペレーションにおいて入力ストリングが安全に使用され得るかどうかを検証するコンピュータ・プログラムのメソッド又はプロセスである。この点に関して、バリデータは、そのようなセキュリティ・センシティブなオペレーションにおいて安全に入力ストリングを使用することができるようにその入力ストリングを処理するコンピュータ・プログラムのメソッドであるサニタイザ（sanitizer）とは区別される。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
従って、バリデータ及びサニタイザは、ウェブ・アプリケーションおよびそれの基礎となるデータのセキュリティを危険に曝すことによりウェブ・アプリケーションを誤って遂行させるような悪質な入力ストリングにそのウェブ・アプリケーションが曝されないことを保証するために使用される。
【課題を解決するための手段】
【０００４】
本発明の実施例の方法は、或るイリーガル・パターン（不正なパターン）及びターゲット・メソッドを有するコンピュータ・プログラムを受け取るプロセッサを含む。ターゲット・メソッドは、１つ又は複数個のリターン・ステートメント及び複数個の基本ブロックを有する。イリーガル・パターンに関係のある上記ターゲット・メソッドの各リターン・ステートメントが一定のブール値を返送するように、上記ターゲット・メソッドはプロセッサにより正規化される。１つ又は複数個の対応する基本ブロックが「真」の一定のブール値を返送するように、正規化されたターゲット・メソッドの１つ又は複数個の対応するパスに対する第１のパス条件がプロセッサによって決定される。第１のパス条件の不充足可能性（unsatisfiability）が、単項２階ロジック（Ｍ２Ｌ）技法を使ってプロセッサにより決定される。第１のパス条件の不充足可能性が真である場合、プロセッサは、ターゲット・メソッドが有益なバリデータであるということを報告する。第１のパス条件の不充足可能性が「偽」である場合、上記プロセッサは、ターゲット・メソッドが有益な（positive）バリデータではないということを報告する。
【０００５】
本発明の実施例のコンピュータ可読データ非一時的記憶媒体は、その上にコンピュータ・プログラムを格納される。プロセッサによるコンピュータ・プログラムの実行は１つのメソッドを遂行させる。上記メソッドは、ターゲット・メソッドが１つのイリーガル・パターンとターゲット・メソッドを有するターゲット・コンピュータ・プログラムとを受け取るステップを含む。ターゲット・メソッドは、１つ又は複数個のリターン・ステートメント及び複数個の基本ブロックを有する。イリーガル・パターンに関連する上記ターゲット・メソッドの各リターン・ステートメントが一定のブール値を返送するように、ターゲット・メソッドは正規化される。
【０００６】
１つ又は複数個の対応する基本ブロックが第１のパス条件にとっては真である一定のブール値を返送し、第２のパス条件にとっては偽である一定のブール値を返送するというような、正規化されたターゲット・メソッドの１つ又は複数個の対応するパスに対する第１のパス条件及び第２のパス条件が決定される。第１のパス条件の不充足可能性及び第２のパス条件の不充足可能性は、単項２階ロジック（Ｍ２Ｌ）技法を使用して決定される。第１のパス条件の不充足可能性が偽である場合、ターゲット・メソッドは有益なバリデータではないとして報告される。第１のパス条件の不充足可能性が真である場合、ターゲット・メソッドは有益なバリデータとして報告される。第２のパス条件の不充足可能性が偽である場合、ターゲット・メソッドは無益な（negative）バリデータではないとして報告される。第２のパス条件の不充足可能性が真である場合、ターゲット・メソッドは無益なバリデータとして報告される。
【０００７】
本発明の実施例のシステムは、プロセッサ、コンピュータ可読データ記憶媒体、及びバリデータ決定コンポーネントを含む。コンピュータ可読データ記憶媒体は、イリーガル・パターンと、ターゲット・メソッドを有するターゲット・コンピュータ・プログラムとを格納する。ターゲット・メソッドは複数個の基本ブロックを有する。バリデータ決定コンポーネントは、少なくともハードウェアによって具現化される。コンポーネントは、イリーガル・パターンに関連するターゲット・メソッドの各リターン・ステートメントが一定のブール値を返送するように、ターゲット・メソッドを正規化するためのものである。コンポーネントは、１つ又は複数個の対応する基本ブロックが真の一定のブール値を返送するような、正規化されたターゲット・メソッドの１つ又は複数個の対応するパスに対する第１のパス条件を決定するためのものである。コンポーネントは、単項２階ロジック（Ｍ２Ｌ）技法を使用して、第１のパス条件の不充足可能性を決定するためのものであり、第１のパス条件の不充足可能性が真である場合、ターゲット・メソッドは有益なバリデータである。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施例に従って、ターゲット・メソッドがバリデータであるかどうかを判断するための方法のフローチャートである。
【図２】本発明の実施例に従って、ターゲット・メソッドに対するパス条件の不充足可能性を決定するために、図１の方法において使用することができる方法のフローチャートである。
【図３】本発明の実施例に従って、基本的なターゲット・メソッドに関して図１及び図２の方法の例示的な遂行を（Ａ）、（Ｂ）、（Ｃ）、（Ｄ）、及び（Ｅ）として示す図である。
【図４】本発明の実施例に従って代表的なシステムを示す簡易的なブロック図である。
【発明を実施するための形態】
【０００９】
本発明の実施例に関する以下の詳細な説明では、添付図面を参照して、本発明を実施し得る特定の実施例が一例として示される。これらの実施例は、当業者が本発明を実行することを可能にするために十分詳細に説明される。本発明の主旨及び技法的範囲から逸脱することなく、他の実施例を利用することが可能であり、論理的、機械的、及び他の変更を施すことも可能である。従って、以下の詳細な説明の記述は限定的な意味に解釈されるべきではなく、本発明の実施例の範囲は請求項の記述によってのみ定義される。
【００１０】
「背景技術」の項において述べたように、バリデータは、入力ストリングがセキュリティ・センシティブなオペレーションにおいて安全に使用され得るかどうかを確認するコンピュータ・プログラムのメソッドである。簡単なバリデータの一例は、例えば、「Valid(String s{return !s.contained(“<”);})」  というコンピュータ・プログラムである。このコンピュータ・プログラムは、入力ストリングｓが文字“<”を含むか否かを判断する。それが肯定される場合、入力ストリングは、セキュリティ・センシティブなオペレーションの範囲内では安全に使用され得ない。
【００１１】
バリデータがその機能を正確に遂行するためには、バリデータが正確に且つ適切に機能を遂行するということを決定するために、そのバリデータ自体が確認されなければならない。正しくない簡単なバリデータの一例は、例えば、「public static Boolean isValid(String s{return !s.substring(1).contains(“<”);} )」というコンピュータ・プログラムである。このコンピュータ・プログラムは、入力ストリングｓの一部分が文字“＜”を含むか否かをまさに判断する。そのコンピュータ・プログラムはストリングｓ全体をチェックするのではないので、そのコンピュータ・プログラムはその機能を適切に遂行するものではない。
【００１２】
バリデータが有益なバリデータ及び／又は無益なバリデータであり得るということに留意されたい。バリデータが有益なバリデータおよび無益なバリデータの両方である場合、そのバリデータは、完全なバリデータ又は単にバリデータと呼ばれ得る。有益なバリデータは、入力ストリングが不正文字を含むときには常に真のブール値を返送しないバリデータである。無益なバリデータは、入力ストリングが不正文字を含むときには常に偽のブール値を返送しないバリデータである。バリデータは、厳密には、それが有益なバリデータ、無益なバリデータ、又は、有益なバリデータ及び無益なバリデータの両方（即ち、完全なバリデータ）であるかどうかに関して検証され得る。
【００１３】
既存のストリング検証技法は、バリデータの検証に十分には適していない。それに比べて、本明細書にはバリデータを検証するための方策が示される。特に、図１は、本発明の実施例に従って、ターゲット・コンピュータ・プログラムのターゲット・メソッドがバリデータであるかどうかを判断するための方法１００を示す。その方法１００は、非一時的なコンピュータ可読データ記憶媒体に格納されたコンピュータ・プログラムとして具現化することが可能である。コンピューティング装置のプロセッサのようなプロセッサによるそのコンピュータ・プログラムの実行は、方法１００が遂行されるという結果に帰着する。このコンピュータ・プログラムと、方法１００を遂行するコンピュータ・プログラムに関連するターゲット・コンピュータ・プログラムとを混同してはならない。同様に、方法１００と、その方法を遂行するメソッドに関連するターゲット・メソッドとを混同してはならない。
【００１４】
イリーガル・パターンと、ターゲット・メソッドを有するターゲット・コンピュータ・プログラムとが受け取られる（ステップ１０２）。イリーガル・パターンは、ターゲット・コンピュータ・プログラムのターゲット・メソッドが１つのパターンに関連したバリデータであることに関してテストされる、そのパターンである。例えば、ターゲット・メソッドは、ストリング“＜”が入力ストリング内にあるか否かを検証するためのものである場合、そのストリング“＜”は、このターゲット・メソッドがテストされるパターンに関連したイリーガル・パターンである。
【００１５】
ターゲット・メソッドは１つ又は複数個のリターン・ステートメントを有する。リターン・ステートメントは、入力ストリングがイリーガル・パターンを含んでいるか否かを返送する、上記ターゲット・メソッド内の１つの又は一連の命令である。ターゲット・メソッド内には２つ以上のリターン・ステートメントがあってもよい。ターゲット・メソッドは、更に、複数個の基本ブロックを有する。基本ブロックは、単に、ターゲット・メソッドのリターン・ステートメントに通じる１つ又は一連の命令である。
【００１６】
ターゲット・メソッドは、イリーガル・パターンに関連する各リターン・ステートメントが一定のブール値を返送するために正規化される（ステップ１０４）。一定のブール値は真または偽である。そのようなブール値は、イリーガル・パターンを含む入力ストリングに対してリターン・ステートメントが常に真を返送する（又は、常に偽を返送する）という点で一定であると言える。ターゲット・メソッド内のリターン・ステートメントは、本来、一定のブール値以外の値を返送し得る。従って、ターゲット・メソッドを正規化することは、イリーガル・パターンに関連する各リターン・ステートメントが代わりに真又は偽を返送するよう、ターゲット・メソッドを修正することを意味する。
【００１７】
ターゲット・メソッド（正規化された）の１つ又は複数個の対応するパスに関する第１のパス条件は、その第１のパス条件の１つ又は複数個の対応する基本ブロックが真の一定のブール値を返送するように決定される（ステップ１０６）。パス条件は、２つのパスのうちのどちらのパスがフォローされるべきかを決定するために評価される、ターゲット・メソッド内のステートメントである。例えば、パス条件は、IF／THEN／ELSEシリーズの命令の一部分であってもよい。パス条件の１つ又は複数個の対応する基本ブロックは、ターゲット・メソッド内のパス条件を評価する１つの命令又は一連の命令である。
【００１８】
第１のパス条件の不充足可能性は、単項２階ロジック（Ｍ２Ｌ）技法を使って決定される（ステップ１０８）。第１のパス条件の不充足可能性は、第１のパス条件が、イリーガル・パターンを含む入力ストリングに関して真のその一定のブール値を常に返送するかどうかを判断する。第１のパス条件の不充足可能性が偽である場合、これは、第１のパス条件が、イリーガル・パターンを含む入力ストリングに関して真の、その関連する一定のブール値を必ずしも返送するとは限らないということを意味する。それに比べて、この不充足可能性が真である場合、これは、第１のパス条件が、イリーガル・パターンを含む入力ストリングに関して真の、その関連する一定のブール値を返送しないということを意味する。
【００１９】
第１のパス条件の不充足可能性が偽である場合、ターゲット・メソッドが有益なバリデータ（即ち、真の関連する一定のブール値に対するバリデータ）ではあり得ないということがわかり、方法１００は、ターゲット・メソッドが有益なバリデータではないということを報告する（ステップ１１０）。これに比べて、第１のパス条件の不充足可能性が真である場合、ターゲット・メソッドが有益なバリデータであるということがわかり、方法１００は、ターゲット・メソッドが有益なバリデータであるということを報告する（ステップ１１２）。同様に、ターゲット・メソッドが有益なバリデータであるか否かは、方法１００では、これまでのところ第１のパス条件の不充足可能性に基づいて評価され、報告されていた。ステップ１１０及び１１２の報告は、グラフィカル・ユーザ・インターフェース（ＧＵＩ）上に表示されたメッセージ、電子メールのような電子メッセージ等のごとき１つ又は複数個の様々な形式を取り得る。
【００２０】
次に、ターゲット・メソッド（正規化された）の同じ１つまたは複数個のパスに対する第２のパス条件が決定され、従って、同じ１つ又は複数個の対応する基本ブロックが偽の一定のブール値を返送する（ステップ１１４）。第２のパス条件は、第１のパス条件に対する結果として生じるパス条件である。第１のパス条件は真の一定のブール値を返送するが、それに対応して第２のパス条件は偽の一定のブール値を返送する。
【００２１】
第２のパス条件の不充足可能性も、Ｍ２Ｌ技法を使用して決定される（ステップ１１６）。第２のパス条件の不充足可能性は、第２のパス条件が、イリーガル・パターンを含む入力ストリングに関する偽の、その一定のブール値を常に返送するかどうかを判断する。第２のパス条件の不充足可能性が偽である場合、これは、第２のパス条件が、イリーガル・パターンを含む入力ストリングに関して偽の、その関連する一定のブール値を必ずしも常に返送するとは限らないということを意味する。これに比べて、この不充足可能性が真である場合、これは、第２のパス条件が、イリーガル・パターンを含む入力ストリングに関して偽のその関連する一定のブール値を返送しない、ということを意味する。
【００２２】
第２のパス条件の不充足可能性が偽である場合、ターゲット・メソッドは無益なバリデータ（即ち、偽の関連するブール値に対するバリデータ）ではあり得ないということがわかり、方法１００は、ターゲット・メソッドが無益なバリデータではないということを報告する（ステップ１１８）。これに比べて、第２のパス条件の不充足可能性が真である場合、ターゲット・メソッドが無益なバリデータであることがわかり、方法１００は、ターゲット・メソッドが無益なバリデータであるということを報告する（ステップ１２０）。同様に、ターゲット・メソッドがバリデータであるか否かは、第２のパス条件の不充足可能性に基づいて、評価及び報告されている。ステップ１１８及び１２０の報告も、ＧＵＩ上に表示されたメッセージ、電子メールのような電子メッセージ等のごとき１つ又は複数個の様々な形式を取り得る。
【００２３】
図２は、本発明の実施例に従ってパス条件の不充足可能性を決定する方法２００を示す。その方法２００は、方法１００のステップ１０８及び１１６を具現化するために使用することが可能である。パス条件の１つ又は複数個の対応するパスにおける変数に関して１セットの可能なストリングが決定される（ステップ２０２）。その変数は、１つ又は複数個の対応するパスにおけるブランチ条件によって抑制される。ターゲット・メソッドの入力パラメータは、前述のように、イリーガル・パターンと一致するストリングであると仮定される。ブランチ条件は、１つ又は複数個の対応するパスが後続することを指示する。そのため、そのストリングのセットは、１つ又は複数個の対応するパスが後続することを指示するブランチ条件をその変数が受け入れそして実現し得るストリングの全部とはいえなくても多数を含む。
【００２４】
変数は、パス条件自体によって更に抑制される（ステップ２０４）。例えば、パス条件自体がブランチ条件よりももっと特殊な制約を有する場合、変数はこれらの制約によって更に抑制される。結局、パス条件の不充足可能性は、抑制された変数及びこの変数に対して決定された可能なストリングのセットに対応するＭ２Ｌ式を使用して決定される（ステップ２０６）。
【００２５】
方法２００のＭ２Ｌ技法ベースの提案は、下記の２つの米国特許出願に記述された一般的な提案に従って具現化することが可能である。第１の特許出願は、２０１０年６月２９日に申請され、米国特許出願１２/８２５,６１０を割り当てられた「ストリングの有効性を決定するためのシステム、方法、及びプログラム（System,method, and program for determining validity of string）」と題するものである。第２の特許出願は、２０１０年１０月１９日に申請され、米国特許出願番号１２/９０７,９７４を割り当てられた「コンピュータ・プログラムのモジュラ及び／又は需要主導型ストリング分析（Modular and/ordemand-driven string analysis of a computer program）」と題するものである。これらの特許出願の両方とも、方法２００を具現化するために使用することができるＭ２Ｌベースの近似方法を開示している。しかし、どちらの特許出願も、バリデータの検証に関連して不充足可能性を決定することを開示していない。
【００２６】
図３の（Ａ）乃至（Ｅ）は、原始的バリデータに関連して方法１００及び２００の例示的な動作を示す。図３の（Ａ）は、本発明の実施例に従って、ターゲット・コンピュータ・プログラムのターゲット・メソッドを示す。方法１００は、図３の（Ａ）のターゲット・メソッドが適切なバリデータであるか否かを、方法２００を使って決定するためのものである。そのため、方法１００は、それのステップ１０２において図３の（Ａ）のターゲット・メソッドを受け取る。
【００２７】
図３の（Ｂ）は、本発明の実施例に従って、方法１００のステップ１０４の正規化が行われた後の図３の（Ａ）のターゲット・メソッドを示す。図３の（Ｃ）は、方法１００のステップ１０６のパス条件の決定が行われた後の図３の（Ｂ）の正規化されたターゲット・メソッドを示す。図３の（Ｄ）は、方法２００のステップ２０２が行なわれた後の図３の（Ｃ）の正規化されたターゲット・メソッドを示す。図３の（Ｅ）は、方法２００のステップ２０４が行なわれた後の図３の（Ｄ）の正規化されたターゲット・メソッドを示す。そのため、方法２００のステップ２０６は、図３の（Ｅ）に示されたターゲット・メソッドに関連して行われ得る。
【００２８】
要するに、図４は、本発明の実施例に従って代表的なシステム４００を示す。システム４００は、デスクトップ・コンピュータのような１つ又は複数個のコンピューティング装置において具現化することが可能である。システム４００は、プロセッサ４０２、コンピュータ可読データ記憶媒体４０４、及びバリデータ決定コンポーネント４０６を含む。コンピュータ可読データ記憶媒体４０４はイリーガル・パターン４０８及びターゲット・コンピュータ・プログラム４１０を格納し、ターゲット・コンピュータ・プログラム４１０はターゲット・メソッド４１２を有し、ターゲット・メソッド４１２自体は多くの基本ブロック４１４を有する。
【００２９】
バリデータ決定コンポーネント４０６は、プロセッサ４０２を使用して具現化される。例えば、１つの実施例では、コンポーネント４０６は、媒体４０４のようなコンピュータ可読データ記憶媒体又は別のコンピュータ可読データ記憶媒体４０４上に格納された１つ又は複数個のコンピュータ・プログラムであってもよい。従って、プロセッサ４０２によるこれらのコンピュータ・プログラムの実行は、その結果として、コンポーネント４０６の機能が実現されることになる。バリデータ決定コンポーネント４０６は、特にターゲット・メソッド４１２がイリーガル・パターン４０８に関連したバリデータであるかどうかを判断するために、ターゲット・メソッド４１２に関連して方法１００及び２００を遂行する。
【００３０】
当業者には明らかなように、本発明の態様は、システム、メソッド、又はコンピュータ・プログラムとして具現化され得る。従って、本発明の実施例の態様は、全体的にハードウェアの実施例、全体的にソフトウェアの実施例（ファームウェア、駐在ソフトウェア、マイクロコード等を含む）、又は、一般に「回路」、「モジュール」、又は「システム」と呼ばれるソフトウェア及びハードウェア態様を結合した実施例の形式を取り得る。更に、本発明の態様は、コンピュータ可読プログラム・コードを組み込まれた１つ又は複数個のコンピュータ可読媒体において具現化されるコンピュータ・プログラムの形式を取り得る。
【００３１】
１つ又は複数個のコンピュータ可読媒体の任意の組み合わせを利用することも可能である。コンピュータ可読媒体は、コンピュータ可読信号媒体又はコンピュータ可読記憶媒体であってもよい。例えば、コンピュータ可読記憶媒体は、例えば、電子的、磁気的、光学的、電磁気的、赤外線、又は半導体システム、装置、もしくはデバイス、或いは上記のものの任意の適切な組み合わせであってもよいが、それらに限定されない。コンピュータ可読記憶媒体の更なる特殊な例（限定的なリスト）は、下記の装置、即ち、１つ又は複数個のワイヤを有する電気的接続体、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリー（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）、消去可能プログラマブル読取り専用メモリ（ＥＰＲＯＭ又はフラッシュ・メモリ）、光ファイバ、ポータブル・コンパクト・ディスク読取り専用メモリ（ＣＤ−ＲＯＭ）、光学的記憶装置置、磁気的記憶装置、又はこれらの装置の任意の適切な組み合わせを含む。本明細書との関連では、コンピュータ可読記憶媒体は、命令実行システム、装置、又はデバイスによる使用、或いはそれに関連した使用のために、プログラムを内蔵又は格納することができる任意の実体的な媒体であってもよい。
【００３２】
コンピュータ可読信号媒体は、例えば、搬送波のベースバンドにおいて、又はそれの一部として、そこに組み込まれたコンピュータ可読プログラム・コードと共に、伝播されたデータ信号を含み得る。そのような伝播された信号は、電磁気的、光学的、又はそれらの任意の適切な組み合わせを含むが、それに限定されない任意の種々の形式を取り得る。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体でなく、命令実行システム、装置、又はデバイスによる使用或いはそのシステム等に関連する使用のためにプログラムを伝送、伝播、又は搬送することができる、任意のコンピュータ可読媒体であってもよい。コンピュータ可読媒体上に具現化されたプログラム・コードは、無線、有線、光ファイバ・ケーブル、ＲＦ等、又は前述のものの任意の適切な組み合わせを含むが、それらに限定されない任意の適切な媒体を使って送信され得る。
【００３３】
一般に、コンピュータ・プログラムは、１つ又は複数個のコンピュータ・プログラムが格納されるコンピュータ可読媒体に格納される。１つ又は複数個のハードウェア装置における１つ又は複数個のプロセッサによるコンピュータ可読媒体からのコンピュータ・プログラムの実行は、１つのメソッドを遂行させる。例えば、遂行されるべきメソッドは、上述のメソッドのうちの１つ又は複数個であってもよい。
【００３４】
コンピュータ・プログラム自体はコンピュータ・プログラム・コードを含む。本発明の実施態様に関するオペレーションを実行するためのコンピュータ・プログラム・コードは、Java、Smalltalk、C++等ようなオブジェクト指向プログラミング言語、及び、「Ｃ」プログラミング言語又は同様のプログラミング言語のような従来の手続型プログラミング言語を含む１つ又は複数個のプログラミング言語の任意の組み合わせで書かれてもよい。プログラム・コードは、ユーザのコンピュータ上で全体的に実行されたり、ユーザのコンピュータ上で部分的に実行されたり、独立型ソフトウェア・パッケージとしてユーザのコンピュータ上で部分的に又はリモート・コンピュータ上で部分的に実行されたり、或いはリモート・コンピュータまたはサーバ上で全体的に実行されたりし得る。後者の場合、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）又は広域ネットワーク（ＷＡＮ）を含む任意のタイプのネットワークを介してユーザのコンピュータに接続されてもよく、或いは、（例えば、インターネット・サービス・プロバイダを利用してインターネットを介して）外部コンピュータへの接続が行われてもよい。
【００３５】
本発明の実施例に従って、本発明の態様が、方法、装置（システム）、およびコンピュータ・プログラムのフローチャート及び／又はブロック図を参照して説明された。そのフローチャート及び／又はブロック図の各ブロック、並びにフローチャート及び／又はブロック図におけるブロックの組み合わせがコンピュータ・プログラム命令によって具現化され得るということは当然である。これらのコンピュータ・プログラム命令は、汎用コンピュータ、特殊目的コンピュータ、又は、マシンを製造するための他のプログラマブル・データ処理装置のプロセッサに提供され得る。従って、そのコンピュータ又は他のプログラマブル・データ処理装置のプロセッサによって実行される命令は、そのフローチャート、ブロック図において指定された機能／行為を具現化するための手段を創出し得る。
【００３６】
コンピュータ、他のプログラマブル・データ処理装置、又は他のデバイスを指示するコンピュータ・プログラム命令はコンピュータ可読媒体に格納され、そのコンピュータ可読媒体に格納された命令は、フローチャート及び／又はブロック図において指定された機能／行為を具現化する命令を含む製品を作り出すというように特定の態様で機能し得る。
【００３７】
コンピュータ・プログラム命令は、コンピュータ、他のプログラマブル・データ処理装置、又は他のデバイス上にもロードされ、そのコンピュータ、他のプログラマブル装置、又は他のデバイスにおいて実行される命令が、フローチャート及び／又はブロック図のブロックにおいて指定された機能／行為を具現化するためのプロセスを提供するよう、コンピュータ活用のプロセスを生じさせるためにそのコンピュータ、他のプログラマブル装置、又は他のデバイスにおいて一連の動作ステップを遂行させる。
【００３８】
添付図面におけるフローチャート及びブロック図は、本発明の様々な実施例に従って、システム、方法、及びコンピュータ・プログラムの可能な実施態様のアーキテクチャ、機能、及びオペレーションを示す。この点に関して、フローチャート又はブロック図における各ブロックは、指定された論理的機能を具現化するための１つ又は複数個の実行可能な命令を含むコードのモジュール、セグメント、又は部分を表わし得る。或る代替の実施態様では、ブロックに記された機能が図面に記された順序から外れて生じ得るということに留意されたい。例えば、連続して示された２つのブロックが実際には実質的に同時に実行されることもあり、或いは、時には、それらのブロックが関連の機能に依存して逆の順序で実行されることもある。更に、ブロック図及び／又はフローチャートの各ブロック、並びにブロック図及び／又はフローチャートのブロックの結合が、指定の機能又は行為を遂行する特別目的のハードウェア・ベースのシステムによって、又は特別目的のハードウェア及びコンピュータ命令の組み合わせによって具現化されることも可能である、ということにも留意されたい。
【００３９】
結局、特定の実施例が本明細書において図示され、説明されたが、同じ目的を達成すると判断される任意の構成がその示された特定の実施例に代わって置き換え可能であるということは当業者には明らかであろう。従って、本願は、本発明の実施例の如何なるアダプテーションまたは変更もカバーすることを意図される。従って、本発明が「特許請求の範囲」の記載およびそれにおける均等物によってのみ限定されるということは当然である。
【図１】
0005700675.tif 000002
【図２】
0005700675.tif 000003
【図３】
0005700675.tif 000004
【図４】
0005700675.tif 000005