(57)【要約】【課題】本明細書において、Ｗｅｂアプリケーション向けの自動テスト入力の生成のための方法及び装置が開示される。【解決手段】１つの実施形態において、この方法は、プログラムのソース間変換を実行するステップと、テスト入力値のセットに基づいてプログラムに解釈を実行するステップと、記号によりプログラムを実行するステップと、プログラムの実行中に遭遇した１つ又は複数の条件式の各々について記号的制約を記録するステップであって、１つ又は複数の可能な実行パスを特定するためにプログラムの文字列操作を分析するステップ、及び、数式及び文字列の制約として条件式の各々の変数の値を表す記号入力を生成するステップであって、有限状態トランスデューサ（ＦＳＴ）を使用して文字列操作をモデル化し、扱いにくい副次式の代わりにプログラムの実行から値を供給することにより文字列値への制約を生成することを含むステップを含むステップと、記録された文字列の制約を解決した結果に基づいて後続の反復中にプログラムを駆動する新しい入力を生成するステップとを備える。【選択図】図１０Ａ
2011503721.tif 000002
【特許請求の範囲】
【請求項１】
プログラムをテストするためのテスト入力を生成する方法であって、
前記プログラムのソース間変換を実行するステップと、
テスト入力値のセットに基づいて前記プログラムに解釈を実行するステップと、
記号により前記プログラムを実行するステップと、
前記プログラムの実行中に遭遇した１つ又は複数の条件式の各々について記号的制約を記録するステップであって、
１つ又は複数の可能な実行パスを特定するために前記プログラムの文字列操作を分析するステップ、及び、
数式及び文字列の制約として前記条件式の各々の変数の値を表す記号入力を生成するステップであって、有限状態トランスデューサ（ＦＳＴ）を使用して文字列操作をモデル化し、扱いにくい副次式の代わりに前記プログラムの実行から値を供給することにより文字列値への制約を生成することを含むステップ
を含むステップと、
前記記録された文字列の制約を解決した結果に基づいて後続の反復中に前記プログラムを駆動する新しい入力を生成するステップと
を備える方法。
【請求項２】
システムによって実行されるとき、前記システムに方法を実行させる命令を格納する１つ又は複数のコンピュータ可読記憶媒体を有する製造品であって、
前記方法は、
前記プログラムのソース間変換を実行するステップと、
テスト入力値のセットに基づいて前記プログラムに解釈を実行するステップと、
記号により前記プログラムを実行するステップと、
前記プログラムの実行中に遭遇した１つ又は複数の条件式の各々について記号的制約を記録するステップであって、
１つ又は複数の可能な実行パスを特定するために前記プログラムの文字列操作を分析するステップ、及び、
数式及び文字列の制約として前記条件式の各々の変数の値を表す記号入力を生成するステップであって、有限状態トランスデューサ（ＦＳＴ）を使用して文字列操作をモデル化し、扱いにくい副次式の代わりに前記プログラムの実行から値を供給することにより文字列値への制約を生成することを含むステップ
を含むステップと、
前記記録された文字列の制約を解決した結果に基づいて後続の反復中に前記プログラムを駆動する新しい入力を生成するステップと
を備える、製造品。
【請求項３】
Ｗｅｂアプリケーションを受信するステップと、
文字列の制約、及び前記文字列の制約の決定手順を使用して、前記Ｗｅｂアプリケーションにｃｏｎｃｏｌｉｃテストを適用するステップと
を備える方法。
【請求項４】
システムによって実行されるとき、前記システムに方法を実行させる命令を格納する１つ又は複数のコンピュータ可読記憶媒体を有する製造品であって、
前記方法は、
Ｗｅｂアプリケーションを受信するステップと、
文字列の制約、及び前記文字列の制約の決定手順を使用して、前記Ｗｅｂアプリケーションにｃｏｎｃｏｌｉｃテストを適用するステップと
を備える、製造品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラムの分析の分野に関し、さらに詳細には、本発明は、プログラムの実行から収集された記号的制約及び具体値に基づいてテスト入力を生成することに関する。
【０００２】
（優先権）
本特許出願は、２００７年１１月８日に出願された「Ａｕｔｏｍａｔｅｄ  Ｔｅｓｔ  Ｉｎｐｕｔ  Ｇｅｎｅｒａｔｉｏｎ  ｆｏｒ  Ｗｅｂ  Ａｐｐｌｉｃａｔｉｏｎｓ」という名称の対応する仮特許出願である第６０／９８６５５２号の優先権を主張し、参照によりこれを組み込むものである。
【背景技術】
【０００３】
（発明の背景）
【０００４】
ユーザが日常の活動をＷｅｂアプリケーションに頼る傾向はますます高まっているが、それに応じてＷｅｂアプリケーションも引き続き、より多くの機能を提供し、より多くの機密データを扱い、より多くのソースに基づいてコンテンツを動的に生成している。重要な領域におけるＷｅｂアプリケーションの役割の増大は、他のＷｅｂアプリケーションとの相互作用だけにとどまらず、ユーザのローカルシステムとの相互作用と相まって、バグの影響を増幅させ、正確さの必要性を高めている。
【０００５】
テストは、バグを特定するため、及び開発者がバグの修正に使用する具体的な入力及びトレースを提供するために、広く使用される手法である。しかし、手動のテストには、広範囲に及ぶ人的取り組みが必要となり、膨大なコストがかかる。加えて、品質保証（ＱＡ）テストは通常、ソフトウェアがすべきことをすべて実行できることを保証するが、ソフトウェアがすべきではないことを実行できるかどうかを確認することはなく、そのような機能は通常セキュリティホールとなる。テストへの従来の取り組みでは、入力として乱数値を生成してきた。無作為に生成された入力値は、冗長になる場合も多く、特定のプログラムの振る舞い全体を見逃すことも多い。ランタイム値を使用するテスト入力の生成、つまりｃｏｎｃｏｌｉｃテストは、多くのグループによって推進されてきた。これらの手法は、記号的制約及び具体値の両方をプログラムの実行から収集し、具体値を使用して次の入力を生成するための制約の解決に役立てる。ｃｏｎｃｏｌｉｃテストへの以前の取り組みは、主として、数値への制約、ポインタベースのデータ構造、及びスレッドのインターリービングを扱う。これは、Ｃ及びＪａｖａ（登録商標）のような言語が奨励するプログラミングのスタイルには適切であるが、スクリプト言語は、特にＷｅｂアプリケーションの事情において使用される場合、文字列及び連想配列がより中心的な役割を果たすスタイルを奨励する。
【０００６】
その他は、ＳＱＬのＬＩＫＥ述部によって指定される正規言語の文字列の等価及び包含をサポートすることを含む、データベース支援のＪａｖａ（登録商標）プログラムを分析するためにｃｏｎｃｏｌｉｃテストを拡大させてきた。これらは、Ｊａｖａ（登録商標）プログラムがＳＱＬクエリを生成する多言語プログラミングの形態をサポートする。しかし、この手法は、文字列の操作をサポートしない。これらは、標準ｃｏｎｃｏｌｉｃ検査と同じプロパティを調べる。
【０００７】
このようにして、ｃｏｎｃｏｌｉｃテストへの以前の取り組みは、Ｃ又はＪａｖａ（登録商標）で作成されたデスクトップアプリケーションのテスト入力の生成を自動化する上で役立ったが、ＰＨＰのようなスクリプト言語で作成されたＷｅｂアプリケーションは、さまざまな難題をもたらす。
【０００８】
第１に、ＰＨＰは、スクリプト言語であり、コンパイル済み言語ではない。そのような言語は、特にＷｅｂアプリケーションの事情において、数値及びデータ構造がより中心的な役割を果たすＪａｖａ（登録商標）のような言語とは対照的に、文字列中心及び配列中心の傾向がより強いプログラミングのスタイルを奨励する。このような制限の中で、スクリプト言語は任意のメタプログラミングを可能にするが、多くのＰＨＰプログラムは、動的な特徴を中程度しか利用しない。加えて、ＰＨＰのＷｅｂアプリケーションは、すべてのユーザ入力を文字列の形態で受信し、多くの文字列操作及び変換関数が、これらの値に適用されてもよい。
【０００９】
第２に、自動テスト入力の生成を有用なものにするため、一般的なエラーのクラスが出現したときを特定するテストオラクルが必要とされる。Ｃプログラムにおけるいくつかの一般的なエラーのクラスは、メモリエラーである。Ｊａｖａ（登録商標）では、大抵のメモリエラーを除去しているが、Ｊａｖａ（登録商標）プログラムは依然としてＮＵＬＬポインタの間接参照エラーを有している場合もあり、ＰＨＰプログラムでは、（インタープリタにバグが無ければ）メモリ破損エラーは全くない。したがって、他の種類のテストオラクルが必要とされる。
【００１０】
Ｗｅｂアプリケーションのテストへの以前の取り組みには、静的なＷｅｂページと、（リンクによって定義された）Ｗｅｂページ間における緩く構造化された制御フローに重点を置いてきたものもあり、また従来のテストからの技法を受け継いでいるサーバサイドのコードに重点を置いてきたものもある。Ｗｅｂアプリケーションへの初期の取り組みでは、主として静的ページに重点を置き、網羅率の測定基準はページ網羅率であった。
【００１１】
その他のテスト技法には、Ｗｅｂアプリケーションへの入力値の影響をテストしようと試みるものもあるが、これらはインターフェイスの仕様を必要とし、広範なユーザ対話がなければコード網羅率を保証することができない。場合によっては、自動化技法がインターフェイス仕様を導くこともあり、また開発者がインターフェイス仕様を提供する必要があることもあるが、いずれの場合でも、テストシステムは基本的に、ユーザ提供の値の仕様によって制約される可能性のあるファズテストを実行する。その他のテスト機構には、より信頼性の高いコード網羅率を提供するものもあるが、これらはユーザに新しい入力を繰り返し要求するので、自動化を犠牲にする。
【００１２】
Ｗｅｂアプリケーションの静的な分析が行われてきた。しかし、提案されているような技法は、動的に構築された文字列値を考慮しないので、これらは直接のユーザ入力が機密シンクに流れるかどうかを確認することしかできない。
【００１３】
ＰＨＰはランタイムシステムがデータ値をコードとして解釈する動的な特徴をサポートするが、動的な特徴は静的な分析を妨げるので、発明者に知られている技法はすべて実効性が限られている。ＰＨＰが提供する標準の動的な特徴により、文字列値は、含めるファイルの名前、読み取り／書き込みするための変数の名前、呼び出すメソッドの名前、インスタンス化するクラスの名前、及び実行するコードの文字列表現を指定することができる。上記で説明されるＰＨＰの静的な分析はすべて、動的な特徴で失敗するか、それらを楽観的に扱う（つまり、無視する）か、それぞれに値を提供するようユーザに依頼するか、又はこれらの３つの組み合わせのいずれかを行う。多くのＰＨＰアプリケーションは、たとえば、動的に読み込まれたモジュール、又はコードを処理するデータベースに、動的ディスパッチを実施するなど、動的な特徴を広範に使用する。そのようなコードでは、静的な分析は、有用な結果をもたらすことができない。
【００１４】
しかし、多くの現実世界のＰＨＰプログラムにおいて、解釈済み文字列の値は、たとえば、ファクトリーパターンなどのＰＨＰコード内の定数文字列、既知のデータベース方式からのカラム名、又は保護されたコンフィギュレーションファイルからのフィールド名のような、信頼される値からしかもたらされない。そのような場合、解釈済み文字列の値は、ユーザ入力に間接的にしか依存せず、任意の所定の実行に対して、ユーザ入力の述部は動的に構築されない。
【発明の概要】
【発明が解決しようとする課題】
【００１５】
本発明は、プログラムの実行から収集された記号的制約及び具体値に基づいてテスト入力を生成する。
【課題を解決するための手段】
【００１６】
Ｗｅｂアプリケーション向けの自動テスト入力の生成のための方法及び装置が、本明細書において開示される。１つの実施形態において、この方法は、プログラムのソース間変換を実行するステップと、テスト入力値のセットに基づいてプログラムに対して解釈を実行するステップと、記号によりプログラムを実行するステップと、プログラムの実行中に遭遇した１つ又は複数の条件式の各々について記号的制約を記録するステップであって、１つ又は複数の可能な実行パスを特定するためにプログラムの文字列操作を分析するステップ、及び、数式及び文字列の制約として条件式の各々の変数の値を表す記号入力を生成するステップであって、有限状態トランスデューサ（ＦＳＴ）を使用して文字列操作をモデル化し、扱いにくい副次式の代わりにプログラムの実行から値を供給することにより、文字列値への制約を生成することを含むステップを含むステップと、記録された文字列の制約を解決した結果に基づいた後続の反復中にプログラムを駆動する新しい入力を生成するステップとを備える。
【発明の効果】
【００１７】
本発明の実施形態は、完全自動化であること、インターフェイス仕様を必要としないこと、文字列操作を処理すること、インジェクション脆弱性を検出すること、スクリプト言語用のテスト入力を生成して、それが汎用メタプログラミングを使用できること、を含む多くの利点を有するが、これらに限定されることはない。
【図面の簡単な説明】
【００１８】
【図１】ＦＳＴ合成アルゴリズムの１つの実施形態を示す図である。
【図２】例示的なＦＳＡイメージ構築を示す図である。
【図３】ＦＳＴ連結アルゴリズムの１つの実施形態を示す図である。
【図４】ＦＳＴ反転アルゴリズムの１つの実施形態を示す図である。
【図５】例示的な式言語を示す図である。
【図６】定数式を具体値と置き換えるアルゴリズムの１つの実施形態を示す図である。
【図７】文字列操作の反転を示す図である。
【図８】中間制約を示す図である。
【図９】一変量の文字列制約解決アルゴリズムの１つの実施形態を示す図である。
【図１０Ａ】テスト入力を生成するためのプロセスの１つの実施形態を示す流れ図である。
【図１０Ｂ】テスト入力を生成するためのプロセスのもう１つの実施形態を示す流れ図である。
【図１１】例示的なＰＨＰコードを示す図である。
【図１２】Ａ及びＢ  ＦＳＴ表現の１つの例を示す図である。（「００」を別の文字列に連結するＦＳＴ表現、及びそのＦＳＴの反転；σ∈Σ）
【図１３】Ａ及びＢ  ＦＳＴ表現のもう１つの例を示す図である。（ｅｒｅｇ”００［０−９］＋のＦＳＴ表現、及び図１２のｂのＦＳＴを介するそのイメージ；σ∈Σ）
【図１４】コンピュータシステムの１つの実施形態を示すブロック図である。
【発明を実施するための形態】
【００１９】
（本発明の詳細な説明）
本発明は、以下に示される詳細な説明、及び添付されている本発明のさまざまな実施形態の図面からさらに深く理解されるが、これらは本発明を特定の実施形態に限定するものと見なすべきではなく、説明及び理解を目的とするに過ぎない。
【００２０】
プログラム実行から収集された記号的制約及び具体値に基づいて入力文字列を生成する方法及び装置が開示される。１つの実施形態において、文字列中心及び配列中心の操作をカバーして、分岐網羅率又は（有界）パス網羅率のうちの指定されたコード網羅率の測定基準を達成する、アプリケーション用のテストケースが自動的に生成される。１つの実施形態において、ライブラリ文字列関数は、有限状態トランスデューサ（ＦＳＴ）として表され、文字列への制約は、等価の制約及び包含の制約を含む。入力変数を解決するために、これらのＦＳＴを合成すること及び反転することが可能である。有限状態トランスデューサを使用して制約が正確に表現できない場合、有限状態トランスデューサである近似を構築するために具体値が使用されてもよい。１つの実施形態において、テスト入力の生成プロセスの一環として、プロセスが使用され、ＳＱＬインジェクション攻撃及びクロスサイトスクリプティングを防ぐために文字列値を既存のポリシーと照合する。１つの実施形態において、テスト入力の生成プロセスは十分に自動化されており、インターフェイス仕様は必要ではなく、文字列操作を処理し、インジェクションの脆弱性を検出し、スクリプト言語用にテスト入力を生成するが、これは汎用メタプログラミングを使用してもよい。
【００２１】
以下の説明において、本発明をさらに十分に解説するために、多くの詳細が示される。しかし、本発明が、これらの具体的な詳細を用いなくても実施され得ることは、当業者には明らかであろう。その他の例において、よく知られた構造及びデバイスは、本発明を不明瞭にすることを避けるために、詳細にではなく、ブロック図の形態で示される。
【００２２】
以下の詳細な説明の一部には、コンピュータメモリ内のデータビットに対する操作のアルゴリズム及び記号的表現に関して提示されるものもある。これらのアルゴリズムの説明及び表現は、データ処理分野における当業者によって、各自の取り組みの内容を他の当業者に最も効果的に伝達するために使用される手段である。本明細書において、及び一般において、アルゴリズムは、望ましい結果を導く首尾一貫した一連のステップであると考えられる。ステップとは、物理量の物理的操作を必要とするものである。通常、ただし必須ではないが、これらの量は、格納、転送、結合、比較、及びその他操作が可能な電気信号又は磁気信号の形態を取る。主として一般的な用法の理由から、これらの信号を、ビット、値、要素、記号、文字、項、数などとして示すことが、場合によっては利便であることが判明している。
【００２３】
しかし、これらの用語及び類似する用語はすべて、適切な物理量に関連付けられるべきであり、これらの量に適用される簡便なラベルに過ぎないことを念頭に置く必要がある。以下の説明から明らかであるとして具体的に言及されていない限り、説明全体を通じて、「処理する（ｐｒｏｃｅｓｓｉｎｇ）」、「演算処理（ｃｏｍｐｕｔｉｎｇ）」、「計算する（ｃａｌｃｕｌａｔｉｎｇ）」、「決定する（ｄｅｔｅｒｍｉｎｉｎｇ）」、又は「表示する（ｄｉｓｐｌａｙｉｎｇ）」などの用語を使用する説明は、コンピュータシステムのレジスタ及びメモリ内の物理（電子）量として表されるデータを、コンピュータシステムのメモリ、レジスタ、又は他のそのような情報記憶装置、伝送装置、又は表示装置内の物理量として同様に表されるその他のデータに、操作及び変換するコンピュータシステム又は類似した電子演算装置の動作及びプロセスを示すことを理解されたい。
【００２４】
本発明はまた、本明細書における操作を実行する装置に関する。この装置は、必要な目的のために特別に構成されてもよく、又、この装置は、コンピュータに格納されたコンピュータプログラムによって選択的に起動又は再構成された汎用コンピュータを備えていてもよい。そのようなコンピュータプログラムは、フロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ、及び光磁気ディスクを含む任意のタイプのディスク、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード若しくは光カードや、電子命令の格納に適し、各々コンピュータシステムバスに結合された任意のタイプの媒体のようなコンピュータ可読記憶媒体に格納されてもよいが、これらに限定されることはない。本明細書において提示されるアルゴリズム及び表示は、任意の特定のコンピュータ又はその他の装置に本質的に関連するものではない。さまざまな汎用システムは、本明細書における教示に従ってプログラムと共に使用されてもよく、又、必要な方法ステップを実行するためにさらに特殊化された装置を構築することが利便であると判明することもある。さまざまなこれらのシステムに必要とされる構造は、以下の説明から示される。加えて、本発明は、任意の特定のプログラミング言語を参照して説明されているわけではない。本明細書において説明される本発明を教示するために、さまざまなプログラミング言語が使用されてもよいことが理解されよう。
【００２５】
機械可読媒体は、機械（たとえば、コンピュータ）によって読み取り可能な形態で、情報を格納又は伝送する任意の機構を含む。たとえば、機械可読媒体は、読み取り専用メモリ（「ＲＯＭ」）、ランダムアクセスメモリ（「ＲＡＭ」）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイス、電気、光、音響若しくはその他の形態の伝播される信号（たとえば、搬送波、赤外線信号、デジタル信号など）を含む。
【００２６】
（概要）
１つの実施形態において、本明細書で説明されるテスト入力の生成プロセスは、Ｗｅｂアプリケーション（たとえば、ＰＨＰ  Ｗｅｂアプリケーション）にｃｏｎｃｏｌｉｃテストを適用する。テストを適用するために、１つの実施形態において、文字列値に対する制約は、有限状態トランスデューサ（ＦＳＴ）を使用して文字列操作をモデル化することにより生成され、文字列値を強調する制約解決アルゴリズムが使用される。ＰＨＰにおいて、数多くのライブラリ関数が１つの型の引数を取って別の型の値を返すだけではなく、ランタイムシステム自身は、多くのさまざまな動的型キャストを容易に実行する。その結果、生成される制約の部分式は、数値型及び配列を含むその他の型にわたるものであってもよい。この制約を解決するため、ＦＳＴが反転される。ｃｏｎｃｏｌｉｃテストのフレームワークは、扱いにくい部分式の代わりに、プログラムの実行から値を供給することによって、制約の解決を助ける。数値制約の場合、「扱いにくい部分式」は、一般に非線形の項を意味する。１つの実施形態において、部分式が異なる型を有する複数の変数にわたる制約は、解決するのが困難になるが、そのような制約については、その値は、制約内の変数ごとに、他の値を具体値に固定することにより解決される。
【００２７】
図１０Ａは、テスト入力を生成するためのプロセスの１つの実施形態を示す流れ図である。プロセスは、ハードウェア（回路、専用論路など）、ソフトウェア（汎用コンピュータシステム又は専用マシンで実行されるようなもの）、又はその組み合わせを備えることができる処理ロジックによって実行される。
【００２８】
図１０Ａを参照すると、プロセスは、プログラムのソース間変換を実行する処理ロジックにより開始する（処理ブロック１００１）。１つの実施形態において、プログラムは、スクリプト言語で作成される。１つの実施形態において、スクリプト言語は、Ｗｅｂアプリケーションの一部である。１つの実施形態において、スクリプト言語はＰＨＰである。
【００２９】
ソース間変換を実行した後、処理ロジックは、テスト入力値のセットに基づいてプログラムに対して解釈操作を実行する（処理ブロック１００２）。１つの実施形態において、テスト入力は、プログラムの実行から収集された記号的文字列の制約及び具体値に基づいて動的に生成された入力文字列である。１つの実施形態において、入力文字列は、文字列中心及び配列中心の操作をカバーするアプリケーションのテストケースである。１つの実施形態において、テストケースは、指定されたコード網羅率の測定基準を達成する。コード網羅率の測定基準は、分岐網羅率及び有界パス網羅率で構成されるグループのうちの１つである。
【００３０】
処理ロジックは、解釈の後に、プログラムを記号により実行し（処理ブロック１００３）、プログラムの実行中に遭遇した１つ又は複数の条件式の各々について記号的制約を記録する（処理ブロック１００４）。１つの実施形態において、処理ロジックは、１つ又は複数の可能な実行パスを特定するためにプログラムの文字列操作を分析し、条件式の各々の変数の値を表す記号入力を数式及び文字列制約として生成することによって、１つ又は複数の条件式ごとに記号的制約を記録するが、これには有限状態トランスデューサ（ＦＳＴ）を使用して文字列操作をモデル化し、扱いにくい部分式の代わりにプログラムの実行から値を供給することにより文字列値に制約を生成するステップを含む。
【００３１】
１つの実施形態において、記号入力を生成するステップは、制約に対して式を解決することによって式の１つの変数に文字列の制約を生成するステップを備える。１つの実施形態において、ＦＳＴは、ライブラリ文字列関数を表し、この方法は、ＦＳＴを使用してプログラムの文字列操作を分析するステップをさらに備える。１つの実施形態において、この方法は、ＦＳＴを反転させることによって入力変数の制約を解決するためにＦＳＴを使用するステップをさらに備える。１つの実施形態において、ＦＳＴを使用して文字列操作をモデル化するステップは、１つの式につき１つだけの変数の出現を考慮することによってプログラムの式を近似させるステップを備える。１つの実施形態において、少なくとも１つの記号式は、この記号式が非線形になるとき、具体値に置き換えられる。
【００３２】
１つの実施形態において、プログラムの実行中に遭遇した条件式の記号的制約を解決するステップは、Ｂｏｏｌｅａｎ制御式の各変数の出現ごとに、式のコピーを作成するステップ、及び、この実行からの式内のその他のすべての変数の出現を、それらの具体値に設定して、それによりセット内の各式が単一の変数の出現のみを有し、その変数に依存しない各部分式はその具体値と置き換えられる式のセットを生成するステップを備える。
【００３３】
１つの実施形態において、この方法は、プログラム内に存在し得る障害点を特定するステップと、この障害点からのバックワードスライスを近似的に計算するステップとをさらに備え、制約はこのバックワードスライスからのみ記録される。
【００３４】
プログラムの実行中に遭遇した１つ又は複数の条件式の各々について記号的制約を記録するステップの後、処理ロジックは、記録された文字列の制約を解決した結果に基づいて後続の反復中にプログラムを駆動するために新しい入力を生成する（処理ブロック１００５）。１つの実施形態において、後続の反復中にプログラムを駆動するために、記録された制約の分析に基づいて、新しい入力を生成するステップは、反転させる式をリストから選択するステップと、リスト内の式に続く式を廃棄するステップとを備える。
【００３５】
１つの実施形態において、この方法は、ＳＱＬインジェクション攻撃を防ぐために、文字列値を１つ又は複数の既存のポリシーと照合するステップをさらに備える。１つの実施形態において、少なくとも１つのセキュリティポリシーは、トークン内の文字が非リテラルである任意のＳＱＬクエリを汚染されたものとして分類し、この方法は、そのようなクエリが特定された場合にエラーのフラグを立てるステップを含む。１つの実施形態において、少なくとも１つのセキュリティポリシーは、クライアントのＪａｖａＳｃｒｉｐｔ（登録商標）インタープリタを呼び出すＷｅｂアプリケーションの出力ドキュメントの文字列を汚染されたものとして分類し、この方法は、そのような文字列が特定された場合にエラーのフラグを立てるステップを含む。
【００３６】
（定義）
本明細書における目的のため、有限状態オートマトン及び有限状態トランスデューサは、ラベル付け関数を含むように定義される。
定義６．１（有限状態オートマトン）  有限状態オートマトン（ＦＳＡ）は、６タプル（Ｑ、Σ、ｑ０、ｑｆ、δ、Ｌ）であり、最初の５つの項は標準的な方法で定義され、Ｌ：Ｑ→（Ｖ×Ｄ）は部分ラベル付け関数であり、ここでＶはプログラム変数の集合、Ｄは集合である。
定義６．２（有限状態トランスデューサ）  有限状態トランスデューサ（ＦＳＴ）は、６タプル（Ｑ、Σ、ｑ０、ｑｆ、δ、Ｌ）であり、ここでδ⊆Ｑ×（Σ∪｛∈｝）×（Σ∪｛∈｝）×Ｑ、ただし第１のシンボルは入力シンボルであり、第２のシンボルは出力シンボルである。残りの項はＦＳＡに関して定義される。
定義６．３（代入）  ｐ＝ｑ０ａ…ｑｉａｉｓａｊｑｊ…ｑｆをＦＳＡ  Ｆ＝（Ｑ，Σ，ｑ０，ｑｆ，δ，Ｌ）経由のパスとし、ｓ＝ｑａａｌ…ａnｑｚをｐの部分列とし、（ｖ，ｄ）をｓの各ｑについてＬ（ｑ）＝（ｖ，ｄ）、Ｌ（ｑｉ）≠（ｖ，ｄ）、且つＬ（ｑｊ）≠（ｖ，ｄ）であるような組とする。次いで、ｓのΣａ１…ａｎへの射影はｖに対する代入である。
【００３７】
（ＦＳＴ）
図１、図２、図３、及び図４は、ＦＳＴの標準的操作のアルゴリズムを示す。さらに具体的には、図１はＦＳＴ合成アルゴリズムの１つの実施形態を示し、図２は例示的なＦＳＡイメージ構築を示し、図３はＦＳＴ連結アルゴリズムの１つの実施形態を示し、図４はＦＳＴ反転アルゴリズムの１つの実施形態を示す。
【００３８】
図１から図４を参照すると、各々のアルゴリズムは、アルゴリズムが入力オートマトンの状態へのラベル付けを出力オートマトンまで行うような方法で提示される。図２に示されるＦＳＴを介するＦＳＡのイメージを検出するためのアルゴリズムにおいて、両方の入力状態がラベル付けされている場合、アルゴリズムはイメージ遷移を構築しない。これは、出力ＦＳＡ経由の各パスがプログラム変数の付値に一意に射影され得るプロパティを保持する。簡潔にするため、及び表示を不明瞭にすることを避けるため、これらのＦＳＴ操作は、本明細書において、従来の簡略表記を使用して、それぞれアルゴリズムの第１行に指定されているように示される。
【００３９】
図５は、ＰＨＰのような言語からのブール演算式の文法の１つの実施形態を示し、文法は、式の抽象構文ツリーの構造を暗黙的に定義する。図５を参照すると、ｅは式に使用され、ｃは定数に使用され、ｆは関数に使用され、ｖは変数に使用される。文法は、文字列型、ブール型、及び配列型の値、さらに数値型の値を返す一部の代表的な関数を含む。そのような関数は、当技術分野においてよく知られており、一部の例は文法に含まれてきた。標題のプログラムの実行から記録された制約は、この文法によってもたらされる。文法は各関数の引数の個数を指定することはないが、ＰＨＰのランタイムシステムは、関数が正しい数の引数を有するプログラムのみを実行する。プログラムの実行から収集された制約が分析されるので、ＰＨＰのランタイムシステムは、各関数が正しい数の引数を渡すことを保証する。
【００４０】
本明細書において説明されるテスト入力の生成プロセスを使用して、標題のプログラムの実行が、プログラムで条件として使用される式のいくつかの抽象構文ツリー（ＡＳＴ）を生成し、これらのＡＳＴは具体値で注釈が付けられる。式の変数について解決を試みる前に、すべてのサブツリーは、サブツリーが実行時に仮定した具体値を持つ変数に依存しない場合、各ＡＳＴで置き換えられる。これは、一部の近似値を使用せざるをえない状態を回避する。
【００４１】
図６は、定数式を具体値と置き換える、Ｂｏｕｎｄと呼ばれるアルゴリズムの１つの実施形態を示す。図６を参照すると、アルゴリズムは、式ツリーｔを取り、それを、変数（ｖ）、定数（ｃ）、キャスト、２項演算、配列参照、及び関数呼び出しという、図５において有り得る種類の式（ｅ）と照合する。各々の場合において、すべての部分式が定数であれば、返された組の第１の値が示すように式全体は定数であり、式は対応する具体値で置き換えられる。
【００４２】
図７は、文字列式を反転させる、Ｉｎｖｅｒｔと呼ばれるアルゴリズムの１つの実施形態を示す。つまり、図７のアルゴリズムは、式ツリー内の関数、演算子、及び定数の逆の効果を有するＦＳＴを生成する。各々のライブラリ文字列関数について、その関数のセマンティックスをモデル化するＦＳＴは、当技術分野においてよく知られている方法で定義される。これらは、プログラムで、たとえばＦｔｒｉｍとして出現する。１つの実施形態において、ライブラリ関数に対応する各ＦＳＴは、空のラベル付け関数を有する。
【００４３】
図８は、制約解決アルゴリズムにおいて中間制約として使用される中間制約の定義を示す。
【００４４】
図９は、実例を挙げるために文字列の制約を中心に取り上げた、制約解決アルゴリズムの一般的構造の１つの実施形態である。図９を参照すると、アルゴリズムは、パラメータ化された制約及び式を取り、変数値への制約を生成する。
【００４５】
最後に、１つの実施形態において、図９のアルゴリズムによって生成されたＦＳＡ  Ａ＝（Ｑ，Σ，ｑ０，ｑｆ，δ，Ｌ）を前提として、可能な言語代入の集合は以下のように生成される（
【数１】
2011503721.tif 000003
はクロス乗積を表す）。
【数２】
2011503721.tif 000004
各Ａ∈Ａｓｓｎは、ＦＳＡへの変数の可能な代入を表し、各Ａ∈Ａについて、Ａ∈Ａ（ｖ，ｄ）である場合、ｖ∈Λ（Ａ）である。
【００４６】
各プログラム変数ｖに対して、
【数３】
2011503721.tif 000005
であるように、各述部ｐのＡｓｓｎにＡが存在する場合、変数への代入が存在する。
本明細書において説明される技法は、ＳＱＬインジェクション攻撃が可能であるかどうかを決定し、可能である場合には、攻撃を生じる入力を生成するアルゴリズムを含む。Ｆ＝（Ｑ，Σ，ｑ０，ｑｆ，δ，Ｌ）をＦＳＴとし、Ｇ＝（Ｓ，Σ，Ｖ，Ｒ）を正規化ＳＱＬ文法とする。◇を未使用のシンボルとする（つまり、
【数４】
2011503721.tif 000006
）。Ｆ’＝（Ｑ，Σ∪｛◇｝，ｑ０，ｑｆ，δ’）とし、
ここで
【数５】
2011503721.tif 000007
Ｇ’＝（Ｓ’，Σ∪｛◇｝，Ｖ’，Ｒ’）＝Ｆ’（Ｇ）とする。Λ（Ｇ’）は、Ｆ−１が適用されたプログラム変数の値の言語である。Ｍ＝｛ａ，ｌ，ｒ，ｎ，ｅ｝とし、要素はそれぞれ「すべて（ａｌｌ）」、「左（ｌｅｆｔ）」、「右（Ｒｉｇｈｔ）」、「なし（ｎｏｎｅ）」、及び「エラー（ｅｒｒｏｒ）」の簡略記号である。攻撃が可能であるかどうかを決定するため、関数Ｈ：Ｖ∪｛◇｝→Π（Ｍ）が使用され、ここでＨは以下の最小解によって与えられる。
【００４７】
Ｈ（◇）＝｛ｎ｝
【００４８】
（ν→νｌ）∈Ｒ’について、
Ｈ（ν）⊇Ｈ（νｌ）
【００４９】
（ν→νｌνｒ）∈Ｒ’について、
【数６】
2011503721.tif 000008
【００５０】
ｅ∈Ｈ（ν）であるようなν∈Ｎ’が存在する場合、記号的制約によれば、攻撃は可能である。１つの実施形態において、これが当てはまる場合、このパスに攻撃を生じるすべての入力の文法ＧＡ＝（Ｓ’，Σ，ＶＡ，ＲＡ）は、以下のように生成される。
【００５１】
νＡ＝Ｖ’∪｛νＡ｜ｅ∈Ｈ（ν）∧Ｓ’⇒＊Ｇ’ν｝とし、
【００５２】
ＲＡ＝Ｒ’｜（ν’＼｛Ｓ’｝→Σ）∪｛Ｓ’→νＡ｜νＡ∈ＶＡ｝とする。ただし、Ｒ’｜（ν’＼｛Ｓ’｝→Σ）は、定義域Ｖ’＼｛Ｓ’｝から変域Σへの関数空間へのＲ’の射影を示す。次いで、ＧＡは、攻撃を生じる可能性の高い値の言語を生成するため、対応する変数への正規言語制約とＡＮＤ演算されてもよい。文脈自由文法の言語の文字列を見出すことは容易である。
【００５３】
（さらに詳細な処理の流れ）
図１０Ｂは、テスト入力を生成するためのプロセスのもう１つの実施形態を示す流れ図である。プロセスは、ハードウェア（回路、専用論路など）、ソフトウェア（汎用コンピュータシステム又は専用マシンで実行されるようなもの）、又はその組み合わせを備えることができる処理ロジックによって実行される。
【００５４】
図１０Ｂを参照すると、プロセスは、ソースプログラムファイル（たとえば、ＰＨＰファイル）にソース間変換を実行する処理ロジックにより開始する（処理ブロック１０１１）。１つの実施形態において、ソース間変換は、ファイルを３アドレスコードに入れ、実行をログに記録する関数呼び出しに命令文をラップする。
【００５５】
ソース間変換の後、処理ロジックは、一部のテスト入力値を使用して変換済みプログラムで解釈操作を実行する（処理ブロック１０１２）。処理ロジックはまた、テスト入力値を解釈操作に供給して、操作を容易にする（処理ブロック１０１３）。テスト入力値は、初期入力値のセットであってもよく、又、図１０Ｂのプロセスの以前の実行の結果として生成されたテスト入力値のセットであってもよい。
【００５６】
１つの実施形態において、解釈操作は、ＰＨＰインタープリタによって実行される。もう１つの実施形態において、解釈操作は、Ｇｒａｓｐのような修正されたＰＨＰインタープリタによって実行される。
【００５７】
１つの実施形態において、解釈中に、処理ロジックは、さらに多くのプログラムファイルを動的に含むことができ（処理ブロック１０１４）、これは同じソース間変換の手続きを踏む。
【００５８】
解釈操作が完了した後、処理ロジックは、実行ログを生成し（処理ブロック１０１５）、処理ロジックは、当技術分野においてよく知られている方法で記号的実行を行う（処理ブロック１０１６）。次に、処理ロジックは、ＡＳＴに具体値で注釈を付けて（処理ブロック１０１７）、バウンディング（境界決定）プロセスを適用する（処理ブロック１０１８）。１つの実施形態において、処理ロジックは、図６のバウンディング（境界決定）プロセスを適用する。
【００５９】
バウンディング（境界決定）の後、処理ロジックは、有界のＡＳＴに具体値で注釈を付け（処理ブロック１０１９）、補完する１つの式を選択し（処理ブロック１０２０）、制約解決を実行する（処理ブロック１０２１）。１つの実施形態において、処理ロジックは、図９の制約解決を適用する。制約解決プロセスは、さらなるテストに備えて新しい入力値を生成する。
【００６０】
以下では、図１０Ｂのプロセスの使用を表す実証的な例を説明して、本明細書において開示されるテストフレームワークによる自動入力テスト生成を実行する。
【００６１】
図１１は、上記で説明されている技法を示すために使用される一部のサンプルのＰＨＰソースコードを示す。図１１を参照すると、このコードはユーザＩＤを受け取り、他のアクションを実行するためにユーザを認証しようと試みる。ユーザのＩＤがデータベースに見つからない場合、プログラムはエラーメッセージを表示して終了する。この特定のコード断片は、動的な特徴を使用しないが、それでもなお本明細書において説明されている主要ポイントの一部を説明する上で役立つ。動的な特徴の存在下で、解釈済み文字列の具体値は、単に記録され、それらの値は、上記で示されている制約の生成及び解決において使用される。
【００６２】
標準ｃｏｎｃｏｌｉｃテストの場合におけるように、プログラムは、標準ランタイムシステムを使用して具体的に、しかも記号的に、実行するために装備されている。記号的実行はＲＡＭマシンのレベルにおいて行われるが、これはつまり名前から記号的位置へのマップが保持され、記号的位置から記号的値へのマップが保持されるという意味である。そのようにすることで、分析には、オフラインのエイリアス解析が必要なくなる。本明細書において説明されるテストフレームワークは、プログラムの実行で出現する各条件式について記号的制約を記録する。
【００６３】
第１の反復で、テストフレームワークは、入力パラメータを提供することなくプログラムを実行する。テストフレームワークは、第１０行でｉｓｓｅｔ条件に遭遇したとき、以下の制約を記録し、
【数７】
2011503721.tif 000009
プログラムは、第２１行に到達して終了する。プログラムが収集する制約の各々は、言語包含制約として表現される。次の実行に対して、テストフレームワークは、以下の制約を反転し、
【数８】
2011503721.tif 000010
Σ＊内の最短値として、空文字列の∫を検出し、＿ＧＥＴのパラメータ”ｕｓｅｒｉｄ”を””””に設定してプログラムを返す。これは、テストであるＰＨＰプログラムのインターフェイスを指定する必要もなく、インターフェイスを推測するために静的な分析が必要とされることもないという、本明細書に説明されている手法の有用な特徴を示している。テストフレームワークが供給しないパラメータをプログラムが期待する場合、そのパラメータは、反転されたときに、次の実行にパラメータが含められるようにする制約に出現する。これは、変数が設定されているかどうかを明示的な条件が確認するだけではなく、初期化されていない任意の変数がいつ使用されるかを確認する場合にも当てはまる。
【００６４】
第２の反復で、フレームワークは、以下の制約を収集し、
【００６５】
［ＧＥＴ［ｕｓｅｒｉｄ］∈Σ＊，ＧＥＴ［ｕｓｅｒｉｄ］∈｛∫｝］
再び第２１行に到達して終了する。この例の場合、第１２行の条件は有効であると仮定される。テストフレームワークは、最後の制約を反転して、以下のプログラムの計算ツリーの縦型検索を実行する。
【数９】
2011503721.tif 000011
【００６６】
ここでも同様に、テストフレームワークは、Σ＋内の最短値を選択するが、この場合「ａ」である。
【００６７】
第３の反復で、フレームワークは、以下の制約を収集する。
【数１０】
2011503721.tif 000012
【００６８】
ここで最後に示したような制約の反転は、この制約が文字列操作のｖｉｚ．連結を含むので、従来提案されてきた技法を超える技法が必要となる。
【００６９】
（制約の解決）
正規の制約を有する語等式の充足可能性の問題は、ＰＳＰＡＣＥ完全であるが、これは当技術分野においてよく知られている。しかし、上記で開示される制約言語は、ＦＳＴとして表される非決定性有理関係が含まれており、言語制約の多くのクラスが決定不能であるため、これよりもさらに表現に富んでいる。したがって、生成される可能性のある制約の言語ですべての制約が正しく解決され得るわけではない。しかし、ｃｏｎｃｏｌｉｃテストフレームワークの利点は、制約解決アルゴリズムが不完全、又はたとえ誤っていてもよく、疑陽性が報告されることはないことである。１つの実施形態において、入力変数が出現する一般的な事例は、各々の言語包含制約の左辺に限られる。
【００７０】
上記で説明されているように、１つの実施形態において、有限状態トランスデューサ（ＦＳＴ）は、文字列操作を反転させるために使用される。図１２のＡは、ＦＳＴが、カリー化関数「００．」、つまり、文字列「００」をその引数の先頭に付加する関数を表すことを示す。図１２のＢを参照すると、最初の２つの遷移は各々何も読み取らず、「０」を出力し、第３の遷移は読み取ったものをすべて出力する。ＦＳＴは、入力シンボルを、各遷移で出力シンボルと交換することにより反転されてもよい。図１２のＢは、反転されたＦＳＴを示す。
【００７１】
図１３のＡは、図１１の第２４行で正規表現を照合する文字列の言語のＦＳＡ表現を示す。正規表現はアンカー（「文字列の始め」に’＾’及び「文字列の終わり」に’＄’）を持たないので、パターンは、ＦＳＡが示すように文字列のどこかに出現するのみである。図１２のＢのＦＳＴは、先頭に付加する「００」の反転を表すので、このＦＳＴは、図１３のＡのＦＳＡに適用されて、図１３のＢのＦＳＡを生成することができる。このＦＳＡの言語は、第２４行の条件式が真と評価するＧＥＴ［ｕｓｅｒｉｄ］の値の言語を表す。これまでのように、このＦＳＡの言語は、プログラムにその計算ツリーの新しいパスを取らせる値の言語を検出するため、同じ変数のその他のＦＳＡの言語とＡＮＤ演算される。次いで、「０」のような新しい値は、ｕｓｅｒｉｄ  ＧＥＴパラメータに選択されてもよい。
【００７２】
（テストオラクル）
有用なものにするため、自動テスト入力の生成には、プログラムの実行ごとにフィードバックをもたらすテストオラクルが必要である。１つの実施形態において、このフィードバックは、合格又は不合格という形を取る。１つの実施形態において、少なくとも２種類のオラクルが使用される。第１に、セキュリティテスターは、多くの場合、入力がＷｅｂブラウザにアラートウィンドウをポップアップ表示させるかどうかを調べる。表示させる場合、これはクロスサイトスクリプティング（ＸＳＳ）脆弱性を示す。第２に、テスターは、複数の自然言語向けに構成されるように作成されたサイトの対応するページが同じ構造を有するかどうかを調べる。同じ構造を有していない場合、これは言語のうちの１つで一部のデータが紛失していることを示す。これらのテストオラクルは、本明細書において説明されるテストフレームワークに使用可能である。
【００７３】
Ｇｒａｓｐは、文字レベルの汚染検出（ｔａｉｎｔｉｎｇ）を実行して、セキュリティポリシーが汚染検出に基づいて文字列で定義されるようにするＰＨＰインタープリタの修正バージョンである。そのようなポリシーの代表的な例は、ＳＱＬインジェクション攻撃を、リテラル以外のトークン内の文字が汚染されているか、又はさらに一般的には、構文的に限定されている部分列のみが汚染されているＳＱＬクエリとして、定義する。ＳＱＬ文法（ＣＦＧ）Ｇ＝（Ｖ，Σ，Ｓ，Ｒ）及びクエリ文字列σ＝σ１σ２σ３∈Σ＊を前提として、Ｘ∈Ｖ且つＳ⇒＊Ｇσ１Ｘσ３⇒＊Ｇσ１σ２σ３であるような文形式σ１Ｘσ３が存在する場合、σ２は構文的にσに限定されている。もう１つの実施形態において、Ｗｅｂアプリケーションの出力文書の汚染された文字列がクライアントＪａｖａＳｃｒｉｐｔ（登録商標）インタープリタを呼び出してはならないというポリシーなど、その他の汚染ベースのポリシーが使用される。これは、ＸＳＳ脆弱性を検出するための、あまりヒューリスティックではない手法である。
【００７４】
上記で説明されているポリシーのような汚染ベースのポリシーを使用することの利点は、結果として実行失敗に至るような入力を生成しようとする試行と、バグと、を発見できることである。ＳＱＬインジェクション脆弱性の場合、データベースＡＰＩでクエリ関数の各呼び出しの前に、暗黙的ＳＱＬ条件がクエリの文字列値に適用される。その条件は、プログラム内、又はプログラムの実行で出現することはない。条件は単に、記号的実行における制約として記録される。制約は、ユーザ入力からのクエリ内の部分列が構文的に限定されることを指定する。この制約を反転させるため、以前と同様に、クエリ文字列を構築した操作を反転させるトランスデューサが構築される。ＳＱＬ  ＣＦＧのイメージは、その変換器を介して構築される。１つの実施形態において、ＦＳＴを介するＣＦＧによって表される文脈自由の言語のイメージは、ＣＦＧ及びＦＳＡのＡＮＤ演算を構築するためにＣＦＬ到達可能性アルゴリズムの適合を使用して構築される。
【００７５】
結果として得られるＣＦＧ  Ｇ’の構造は、クエリ文字列を構築するために値が使用されるＰＨＰ変数νについて、下位文法Ｇνがν∈Λ（Ｇν）となるようにＧ’から抽出されるように、ＳＱＬ  ＣＦＧの構造に対応する。ＳＱＬ述部は、Ｇνの構造に基づいてνの可能なすべての値が安全であるかどうかを、記号により確認する。実行している例の場合、この述部は有効ではない。反転させるのではなく、ＧνＧ’νから抽出された、その補集合を取ることにより、Λ（Ｇν）⊆Λ（Ｇ’ν）であるνの値と、Λ（Ｇ’ν）のすべての文字列と、に対する文法は、攻撃入力を表す。Ｇ’νは、Ｇνの構造に基づいているので、構築することができる。
【００７６】
νへの制約を解決するため、Λ（Ｇ’ν）と、νの範囲を限定する他の正規言語のＡＮＤ演算と、のＡＮＤ演算が行われる。結果はＣＦＧであり、ＣＦＧの言語内の単語を検出することは、線形時間で行われてもよい。次いで、そのような語は、次のテスト実行のために入力として供給され、実際にその単語がセキュリティポリシーに違反する場合、ランタイムシステムがこれを捕らえる。２つのＣＦＧのＡＮＤ演算は一般に構築することができないので、１つの実施形態において、１つのＳＱＬ制約のみが一度に１変数ずつ処理される。実行している例の場合、ＳＱＬ述部を解決した結果は非常に複雑であるため、意味のある図式で示すことはできないが、アルゴリズムは「０’ＯＲ’ａ’＝’ａ」のような文字列を生成し、これが結果として攻撃となる。
【００７７】
本発明の実施形態は、完全自動化であること、インターフェイス仕様を必要としないこと、文字列操作を処理すること、インジェクション脆弱性を検出すること、スクリプト言語用のテスト入力を生成して、それが汎用メタプログラミングを使用できること、を含む多くの利点を有するが、これらに限定されることはない。
【００７８】
（コンピュータシステムの一例）
図１４は、本明細書において説明される１つ又は複数の操作を実行することができる例示的なコンピュータシステムを示すブロック図である。図１４を参照すると、コンピュータシステム１４００は、例示的なクライアント又はサーバコンピュータシステムを備えることができる。コンピュータシステム１４００は、情報を通信するための通信機構又はバス１４１１、及び、情報を処理するためにバス１４１１に結合されたプロセッサ１４１２を備える。プロセッサ１４１２は、マイクロプロセッサを含むが、たとえばＰｅｎｔｉｕｍ（登録商標）、ＰｏｗｅｒＰＣ（登録商標）、Ａｌｐｈａ（登録商標）などのようなマイクロプロセッサに限定されることはない。
【００７９】
システム１４００は、プロセッサ１４１２によって実行されるべき情報及び命令を格納するためにバス１４１１に結合された、ランダムアクセスメモリ（ＲＡＭ）、又はその他の動的記憶装置１４０４（メインメモリとして示される）をさらに備える。メインメモリ１４０４はまた、プロセッサ１４１２による命令の実行中に、一時変数又はその他の中間情報を格納するために使用されてもよい。
【００８０】
コンピュータシステム１４００はまた、プロセッサ１４１２の静的情報及び命令を格納するためにバス１４１１に結合された、読み取り専用メモリ（ＲＯＭ）、及び／又は、その他の静的記憶装置１４０６、並びに、磁気ディスク又は光ディスク及びその対応するディスクドライブなどのデータ記憶装置１４０７を備える。データ記憶装置１４０７は、情報及び命令を格納するためにバス１４１１に結合される。
【００８１】
コンピュータシステム１４００は、コンピュータユーザに情報を表示するためにバス１４１１に結合された、陰極線管（ＣＲＴ）又は液晶ディスプレイ（ＬＣＤ）などの表示デバイス１４２１にさらに結合されてもよい。英数字及びその他のキーを含む英数字入力デバイス１４２２もまた、情報及びコマンド選択をプロセッサ１４１２に通信するためにバス１４１１に結合されてもよい。追加のユーザ入力デバイスは、方向情報及びコマンド選択をプロセッサ１４１２に通信するため、及び、ディスプレイ１４２１上のカーソル移動を制御するためにバス１４１１に結合された、マウス、トラックボール、トラックパッド、スタイラス、又はカーソル方向キーなどのカーソル制御機器１４２３である。
【００８２】
バス１４１１に結合することができるもう１つのデバイスは、ハードコピーデバイス１４２４であるが、これは紙、フィルム、又は同様の種類の媒体のような媒体に情報を記録するために使用されてもよい。バス１４１１に結合することができるもう１つのデバイスは、電話又は手持ち式パームデバイスと通信する有線／無線通信機能１４２５である。
【００８３】
システム１４００のコンポーネント、及び関連するハードウェアの、いずれか又はすべてを本発明に使用することができることに留意されたい。しかし、コンピュータシステムのその他の構成が、デバイスの一部又は全部を含むことができることを理解されたい。前述の説明を読んだ後、当業者にはおそらく、本発明の多くの変更及び修正が明らかとなるであろうが、例示により示され説明される特定の実施形態が限定的なものと見なされることは決して意図されていないことを理解されたい。したがって、さまざまな実施形態の詳細への参照は、それ自体が本発明に必須であると見なされる特徴のみを列挙する特許請求の範囲を限定することを意図されていない。
【図１】
2011503721.tif 000013
【図２】
2011503721.tif 000014
【図３】
2011503721.tif 000015
【図４】
2011503721.tif 000016
【図５】
2011503721.tif 000017
【図６】
2011503721.tif 000018
【図７】
2011503721.tif 000019
【図８】
2011503721.tif 000020
【図９】
2011503721.tif 000021
【図１０Ａ】
2011503721.tif 000022
【図１０Ｂ】
2011503721.tif 000023
【図１１】
2011503721.tif 000024
【図１２】
2011503721.tif 000025
【図１３】
2011503721.tif 000026
【図１４】
2011503721.tif 000027
【手続補正書】
【提出日】平成22年7月7日(2010.7.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
プログラムをテストするためのテスト入力を生成する方法であって、
前記プログラムのソース間変換を実行するステップと、
テスト入力値のセットに基づいて前記プログラムに解釈を実行するステップと、
記号により前記プログラムを実行するステップと、
前記プログラムの実行中に遭遇した１つ又は複数の条件式の各々について記号的制約を記録するステップであって、
１つ又は複数の可能な実行パスを特定するために前記プログラムの文字列操作を分析するステップ、及び、
数式及び文字列の制約として前記条件式の各々の変数の値を表す記号入力を生成するステップであって、有限状態トランスデューサ（ＦＳＴ）を使用して文字列操作をモデル化し、扱いにくい副次式の代わりに前記プログラムの実行から値を供給することにより文字列値への制約を生成することを含むステップ
を含むステップと、
前記記録された文字列の制約を解決した結果に基づいて後続の反復中に前記プログラムを駆動する新しい入力を生成するステップと
を備える方法。
【請求項２】
前記テスト入力は、前記プログラムの実行から収集された記号的文字列の制約及び具体値に基づいて動的に生成された入力文字列である、請求項１に記載の方法。
【請求項３】
前記入力文字列は、文字列中心及び配列中心の操作をカバーするアプリケーションのテストケースである、請求項２に記載の方法。
【請求項４】
前記テストケースは、指定されたコード網羅率の測定基準を達成する、請求項１に記載の方法。
【請求項５】
前記コード網羅率の測定基準は、分岐網羅率及び有界パス網羅率で構成されるグループのうちの１つである、請求項４に記載の方法。
【請求項６】
前記プログラムの実行中に遭遇した各々の条件式について記号的制約を記録するステップは、
Ｂｏｏｌｅａｎ制御式の各変数の出現ごとに、前記式のコピーを作成するステップと、
前記実行からの前記式内のその他のすべての変数の出現を、それらの具体値に設定して、それによりセット内の各式が単一の変数の出現のみを有し、その変数に依存しない各部分式はその具体値と置き換えられる式の前記セットを生成するステップと
を備える、請求項１に記載の方法。
【請求項７】
後続の反復中に前記プログラムを駆動するために、前記記録された制約の分析に基づいて、新しい入力を生成するステップは、
反転させる式をリストから選択するステップと、
前記リスト内の前記式に続く式を廃棄するステップと
を備える、請求項６に記載の方法。
【請求項８】
記号入力を生成するステップは、制約に対して式を解決することによって前記式の１つの変数に文字列の制約を生成するステップを備える、請求項１に記載の方法。
【請求項９】
１つの記号式は、前記１つの記号式が非線形になるとき、具体値に置き換えられるステップをさらに備える、請求項１に記載の方法。
【請求項１０】
前記ＦＳＴは、ライブラリ文字列関数を表し、前記ＦＳＴを使用して前記プログラムの文字列操作を分析するステップをさらに備える、請求項１に記載の方法。
【請求項１１】
前記ＦＳＴを反転させることによって入力変数の制約を解決するために前記ＦＳＴを使用するステップをさらに備える、請求項１に記載の方法。
【請求項１２】
ＦＳＴを使用して文字列操作をモデル化するステップは、１つの式につき１つだけの変数の出現を考慮することによって前記プログラムの式を近似させるステップを備える、請求項１に記載の方法。
【請求項１３】
前記プログラム内に存在し得る障害点を特定するステップと、
前記障害点からのバックワードスライスを近似的に計算するステップであって、制約は前記バックワードスライスからのみ記録されるステップと
をさらに備える、請求項１に記載の方法。
【請求項１４】
前記点は、クエリをデータベースに送信するためにＡＰＩ関数が呼び出される点を含む、請求項１３に記載の方法。
【請求項１５】
これらの点が出現するすべての関数を、分析されるべき関数のセットに追加するステップをさらに備える、請求項１４に記載の方法。
【請求項１６】
すべての関数を追加するステップは、
関数呼び出しの始めにスタックトレースを記録することによって制御依存関係を解決するステップと、
前記関数を呼び出した関数を、分析されるべき関数の前記セットに追加するステップと
を備える、請求項１５に記載の方法。
【請求項１７】
制御依存関係を解決するステップは、
記号的値を調べるステップと、
分岐がどこで関数呼び出しを終了させるかを決定するステップと
を備え、さらに、それらの関数を関数の前記セットに追加する、請求項１６に記載の方法。
【請求項１８】
ＳＱＬインジェクション攻撃を防ぐために、文字列値を１つ又は複数の既存のポリシーと照合するステップをさらに備える、請求項１に記載の方法。
【請求項１９】
少なくとも１つのセキュリティポリシーは、トークン内の文字が非リテラルである任意のＳＱＬクエリを汚染されたものとして分類し、そのようなクエリが特定された場合にエラーのフラグを立てるステップを含む、請求項１８に記載の方法。
【請求項２０】
少なくとも１つのセキュリティポリシーは、クライアントのＪａｖａＳｃｒｉｐｔ（登録商標）インタープリタを呼び出すＷｅｂアプリケーションの出力ドキュメントの文字列を汚染されたものとして分類し、そのような文字列が特定された場合にエラーのフラグを立てるステップを含む、請求項１８に記載の方法。
【請求項２１】
制約を記録するステップは、結果として、単一の関数を超える制約を選択的に記録するステップになる、請求項１に記載の方法。
【請求項２２】
前記プログラムは、スクリプト言語で作成される、請求項１に記載の方法。
【請求項２３】
前記スクリプト言語は、Ｗｅｂアプリケーションの一部である、請求項２２に記載の方法。
【請求項２４】
前記スクリプト言語は、ＰＨＰである、請求項２２に記載の方法。
【請求項２５】
システムによって実行されるとき、前記システムに方法を実行させる命令を格納する１つ又は複数のコンピュータ可読記憶媒体を有する製造品であって、
前記方法は、
前記プログラムのソース間変換を実行するステップと、
テスト入力値のセットに基づいて前記プログラムに解釈を実行するステップと、
記号により前記プログラムを実行するステップと、
前記プログラムの実行中に遭遇した１つ又は複数の条件式の各々について記号的制約を記録するステップであって、
１つ又は複数の可能な実行パスを特定するために前記プログラムの文字列操作を分析するステップ、及び、
数式及び文字列の制約として前記条件式の各々の変数の値を表す記号入力を生成するステップであって、有限状態トランスデューサ（ＦＳＴ）を使用して文字列操作をモデル化し、扱いにくい副次式の代わりに前記プログラムの実行から値を供給することにより文字列値への制約を生成することを含むステップ
を含むステップと、
前記記録された文字列の制約を解決した結果に基づいて後続の反復中に前記プログラムを駆動する新しい入力を生成するステップと
を備える、製造品。
【請求項２６】
Ｗｅｂアプリケーションを受信するステップと、
文字列の制約、及び前記文字列の制約の決定手順を使用して、前記Ｗｅｂアプリケーションにｃｏｎｃｏｌｉｃテストを適用するステップと
を備える方法。
【請求項２７】
ＳＱＬインジェクション攻撃及びクロスサイトスクリプティングを防ぐために文字列値を１つ又は複数のポリシーと照合するステップをさらに備える、請求項２６に記載の方法。
【請求項２８】
システムによって実行されるとき、前記システムに方法を実行させる命令を格納する１つ又は複数のコンピュータ可読記憶媒体を有する製造品であって、
前記方法は、
Ｗｅｂアプリケーションを受信するステップと、
文字列の制約、及び前記文字列の制約の決定手順を使用して、前記Ｗｅｂアプリケーションにｃｏｎｃｏｌｉｃテストを適用するステップと
を備える、製造品。
【国際調査報告】
2011503721.tif 000028
2011503721.tif 000029
2011503721.tif 000030