(57)【特許請求の範囲】
【請求項１】
未知のバイナリプログラムに対する有効な入力シーケンスを決定する方法であって、前記方法は、
未知のバイナリプログラムに対する複数の入力シーケンスを得るステップであって、前記入力シーケンスの各々は、２以上の異なる入力を有し、前記入力シーケンスの入力は、前記未知のバイナリプログラムに対して有効な入力として決定される、ステップと、
各々の入力シーケンスについて別個に前記未知のバイナリプログラムの計装バージョンを実行するステップであって、前記未知のバイナリプログラムの前記計装バージョンの各々の実行は、前記未知のバイナリプログラムの前記計装バージョンへの入力として前記入力シーケンスのうちの１つを用いる、ステップと、
前記未知のバイナリプログラムの前記計装バージョンの各々の実行について、前記未知のバイナリプログラムの前記計装バージョンの前記実行により生成される実行トレースを記録することにより、実行トレースセットを生成するステップと、
前記実行トレースセットを比較するステップと、
前記実行トレースセットの比較に基づき、前記入力シーケンスのうちのどれを前記未知のバイナリプログラムが有効として受け入れるかを決定するステップと、
を有する方法。
【請求項２】
前記入力は、前記未知のバイナリプログラムに対して有効であると決定されたコマンドと、前記コマンドに関連する引数と、を有し、前記引数も、前記未知のバイナリプログラムに対して有効であると決定される、請求項１に記載の方法。
【請求項３】
前記実行トレースセットを生成するステップは、前記実行トレースセットに含めるために、前記未知のバイナリプログラムの前記計装バージョンの各々の実行について、前記実行トレースの一部を選択するステップであって、前記実行トレースセットのために選択された前記実行トレースの一部は、前記入力シーケンスの最後の入力が前記未知のバイナリプログラムに提供された後に生成された実行トレースである、ステップを含む、請求項１に記載の方法。
【請求項４】
前記実行トレースセットに含めるために前記実行トレースの一部を選択するステップは、
入力を有しないで前記未知のバイナリプログラムの前記計装バージョンを実行するステップと、
入力を有しない前記実行の終わりに、前記未知のバイナリプログラムの前記計装バージョンの実行により生成された複数の実行トレースを決定するステップと、
前記決定した複数の実行トレースをパーティション実行トレースとして設定するステップと、
前記パーティション実行トレースの最後から２番目の発生と最後の発生との間に生じる実行トレースの一部に基づき、前記入力シーケンスを用いて前記未知のバイナリプログラムの前記計装バージョンの実行中に生成された実行トレースの一部を選択するステップと、
を有する、請求項３に記載の方法。
【請求項５】
前記実行トレースセットの各々について制御フローグラフを生成するステップ、を更に有し、
前記実行トレースセットを比較するステップは、
前記制御フローグラフの各々についてストリング表現を生成するステップと、
前記ストリング表現を比較するステップと、
を有する、請求項１に記載の方法。
【請求項６】
各々の制御フローグラフについて前記ストリング表現を生成するステップは、縦型探索アルゴリズム又は横型探索アルゴリズムを実施するステップを有する、請求項５に記載の方法。
【請求項７】
前記実行トレースセットのうちの１つのセットの中の実行トレースは、前記未知のバイナリプログラムの前記計装バージョンにより出力され且つ前記未知のバイナリプログラムの非計装バージョンにより出力されない、前記未知のバイナリプログラムの中で実行される直線的命令セットに関連するメモリアドレスを表す、請求項１に記載の方法。
【請求項８】
各々の入力シーケンスの中の最後の入力は同じであり、前記複数の入力シーケンスは入力シーケンスセットであり、前記方法は、複数の他の入力シーケンスセットについて請求項１に記載の方法を繰り返すステップ、を更に有し、前記他の入力シーケンスセットのうちの各々のセットの各々の入力シーケンスの最後の入力は、同じであり、各々の入力シーケンスセットの最後の入力は、他の入力シーケンスセットの最後の入力と異なる、請求項７に記載の方法。
【請求項９】
前記実行トレースセットの比較が、前記実行トレースセットは同じであると示すとき、前記入力シーケンスのいずれも、前記未知のバイナリプログラムにより受け入れられないと決定される、請求項１に記載の方法。
【請求項１０】
前記実行トレースセットの比較が、前記実行トレースセットのうちの１つが前記実行トレースセットのうちの同じである少なくとも別の２つと異なることを示すとき、前記実行トレースセットのうちの該１つに対応する入力シーケンスは、前記未知のバイナリプログラムにより受け入れられると決定される、請求項１に記載の方法。
【請求項１１】
命令を含む１又は複数の非一時的コンピュータ可読媒体であって、前記命令は、１又は複数のプロセッサにより実行されると、未知のバイナリプログラムに対する有効な入力シーケンスを決定する工程を実行し、前記工程は、
未知のバイナリプログラムに対する複数の入力シーケンスを得るステップであって、前記入力シーケンスの各々は、２以上の異なる入力を有し、前記入力シーケンスの入力は、前記未知のバイナリプログラムに対して有効な入力として決定される、ステップと、
各々の入力シーケンスについて別個に前記未知のバイナリプログラムの計装バージョンを実行するステップであって、前記未知のバイナリプログラムの前記計装バージョンの各々の実行は、前記未知のバイナリプログラムの前記計装バージョンへの入力として前記入力シーケンスのうちの１つを用いる、ステップと、
前記未知のバイナリプログラムの前記計装バージョンの各々の実行について、前記未知のバイナリプログラムの前記計装バージョンの前記実行により生成される実行トレースを記録することにより、実行トレースセットを生成するステップと、
前記実行トレースセットを比較するステップと、
前記実行トレースセットの比較に基づき、前記入力シーケンスのうちのどれを前記未知のバイナリプログラムが有効として受け入れるかを決定するステップと、
を有する、１又は複数の非一時的コンピュータ可読媒体。
【請求項１２】
前記入力は、前記未知のバイナリプログラムにより有効であると決定されたコマンドと、前記コマンドに関連する引数と、を有し、前記引数も前記未知のバイナリプログラムにとって有効であると決定される、請求項１１に記載の１又は複数の非一時的コンピュータ可読媒体。
【請求項１３】
前記実行トレースセットを生成するステップは、前記実行トレースセットに含めるために、前記未知のバイナリプログラムの前記計装バージョンの各々の実行について、前記実行トレースの一部を選択するステップであって、前記実行トレースセットのために選択された前記実行トレースの一部は、前記入力シーケンスの最後の入力が前記未知のバイナリプログラムに提供された後に生成された実行トレースである、ステップ、を更に有する、請求項１１に記載の１又は複数の非一時的コンピュータ可読媒体。
【請求項１４】
前記実行トレースセットに含めるために前記実行トレースの一部を選択するステップは、
入力を有しないで前記未知のバイナリプログラムの前記計装バージョンを実行するステップと、
入力を有しない前記実行の終わりに、前記未知のバイナリプログラムの前記計装バージョンの実行により生成された複数の実行トレースを決定するステップと、
前記決定した複数の実行トレースをパーティション実行トレースとして設定するステップと、
前記パーティション実行トレースの最後から２番目の発生と最後の発生との間に生じる実行トレースの一部に基づき、前記入力シーケンスを用いて前記未知のバイナリプログラムの前記計装バージョンの実行中に生成された実行トレースの一部を選択するステップと、
を更に有する、請求項１３に記載の１又は複数の非一時的コンピュータ可読媒体。
【請求項１５】
前記工程は、前記実行トレースセットの各々について制御フローグラフを生成するステップ、を更に有し、
前記実行トレースセットを比較するステップは、
前記制御フローグラフの各々についてストリング表現を生成するステップと、
前記ストリング表現を比較するステップと、
を有する、請求項１１に記載の１又は複数の非一時的コンピュータ可読媒体。
【請求項１６】
各々の制御フローグラフについて前記ストリング表現を生成するステップは、縦型探索アルゴリズム又は横型探索アルゴリズムを実施するステップを有する、請求項１５に記載の１又は複数の非一時的コンピュータ可読媒体。
【請求項１７】
前記実行トレースセットのうちの１つのセットの中の実行トレースは、前記未知のバイナリプログラムの前記計装バージョンにより出力され且つ前記未知のバイナリプログラムの非計装バージョンにより出力されない、前記未知のバイナリプログラムの中で実行される直線的命令セットに関連するメモリアドレスを表す、請求項１１に記載の１又は複数の非一時的コンピュータ可読媒体。
【請求項１８】
各々の入力シーケンスの中の最後の入力は同じであり、前記複数の入力シーケンスは入力シーケンスセットであり、前記工程は、複数の他の入力シーケンスセットについて請求項１１に記載の工程を繰り返すステップ、を更に有し、前記他の入力シーケンスセットのうちの各々のセットの各々の入力シーケンスの最後の入力は、同じであり、各々の入力シーケンスセットの最後の入力は、他の入力シーケンスセットの最後の入力と異なる、請求項１７に記載の１又は複数の非一時的コンピュータ可読媒体。
【請求項１９】
前記実行トレースセットの比較が、前記実行トレースセットは同じであると示すとき、前記入力シーケンスのいずれも、前記未知のバイナリプログラムにより受け入れられないと決定される、請求項１１に記載の１又は複数の非一時的コンピュータ可読媒体。
【請求項２０】
前記実行トレースセットの比較が、前記実行トレースセットのうちの１つが前記実行トレースセットのうちの同じである少なくとも別の２つと異なることを示すとき、前記実行トレースセットのうちの該１つに対応する入力シーケンスは、前記未知のバイナリプログラムにより受け入れられると決定される、請求項１１に記載の１又は複数の非一時的コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本願明細書で議論する実施形態は、未知のバイナリプログラムに対する有効な入力の決定に関する。
【背景技術】
【０００２】
バイナリプログラムの効率的なテストは、どの入力がバイナリプログラムにとって有効かという知識により向上され得る。バイナリプログラムは、人間がテキストとして解釈できるコード及びルーチンを有し得る。しかしながら、バイナリプログラムのコード及びルーチンに含まれるテキストは、人間には読めない。バイナリプログラムのコード及びルーチンは人間が読めないので、バイナリプログラムの人間のテスターは、コード及びルーチンを見直すことによりバイナリプログラムの有効な入力を決定することができない。その結果、人間のテスターは、どの入力がバイナリプログラムにとって有効かを決定するために、バイナリプログラムに関連する仕様書、文書、又はソースコードを見直す場合がある。次に、これらの有効な入力は、バイナリプログラムのより効率的なテストを達成するために用いることができる。
【発明の概要】
【０００３】
一実施形態の一態様によると、未知のバイナリプログラムに対する有効な入力を決定する方法が提供される。方法は、未知のバイナリプログラムのための複数の入力シーケンスを得るステップを有する。入力シーケンスの各々は、２以上の異なる入力を有しても良い。入力は、未知のバイナリプログラムの有効な入力として予め決定されても良い。方法は、各々の入力シーケンスについて別個に、前記未知のバイナリプログラムの計装バージョンを実行するステップ、を更に有する。未知のバイナリプログラムの計装バージョンの各々の実行は、入力シーケンスのうちの１つを、未知のバイナリプログラムの計装バージョンへの入力として用いても良い。
【０００４】
未知のバイナリプログラムの計装バージョンの各々の実行について、未知のバイナリプログラムの計装バージョンの実行により生成される実行トレースを記録することにより、実行トレースセットが生成されても良い。方法は、前記実行トレースセットを比較するステップと、実行トレースセットの比較に基づき、前記入力シーケンスのうちのどれを、前記未知のバイナリプログラムが有効であるとして受け入れるかを決定するステップと、も有しても良い。
【０００５】
実施形態の目的及び利点が理解され、少なくとも特に特許請求の範囲で指摘された要素、特徴及び組合せを用いて達成されるだろう。
【０００６】
上述の全体的説明及び以下の詳細な説明の両方は、例示及び説明のためであり、本開示の範囲を限定しないことが理解される。
【図面の簡単な説明】
【０００７】
例示的な実施形態は、添付の図面を用いて、更なる特異性及び詳細事項と共に記載され説明される。
【図１】例示的な入力シーケンス決定処理を示す。
【図２】制御フローグラフを構築する例示的な方法のフローチャートである。
【図３】例示的な制御フローグラフ及び制御フローグラフの例示的なストリング表現を示す。
【図４】例示的な入力決定処理を示す。
【図５】例示的な入力決定システムのブロック図である。
【図６】未知のバイナリプログラムの有効な入力シーケンスを決定する例示的な方法のフローチャートである。
【発明を実施するための形態】
【０００８】
未知のバイナリプログラムに対する有効な入力シーケンスを決定するための許容可能な方法は、種々の要素を含み得る。１つの要素は、未知のバイナリプログラムに含まれるコード及びルーチン（デッドコードを除く）の高い割合をカバーすることを含み得る。例えば、未知のバイナリプログラムをテストするために選択される１又は複数のテスト入力又は入力シーケンスは、未知のバイナリプログラムのコード及びルーチンの１００パーセント又は１００パーセント近くをカバーし得る（例えば、デッドコード及びルーチンを除いて、バイナリプログラムの９０パーセント乃至１００パーセント）。幾つかの現在の方法は、未知のバイナリプログラムをテストするためにランダムテスト入力の生成に頼っている。残念ながら、未知のバイナリプログラムをテストするためにランダムテスト入力の生成を含むテスト方法は、未知のバイナリプログラムのコード及びルーチンの高い割合を常にカバーすることができないことがある。なぜなら、ランダムに生成されたテキスト入力は、未知のバイナリプログラムのコード及びルーチンの高い割合を常にカバーするという目的とは本質的に矛盾し得るからである。その結果、幾つかの既存の方法は、バイナリプログラムのコ―ド及びルーチンの高い割合を常にカバーすることができない。したがって、これらの方法は受け入れ難い。
【０００９】
未知のバイナリプログラムの有効な入力シーケンスを決定するための許容可能な方法の別の要素は、未知のバイナリプログラムに関連する仕様書、文書又はソースコードを有しないで効率的に実装可能な能力を含み得る。この要件は、コンピュータシステムにとってソフトウェアの中の脆弱性を自動的に決定することが有益である、自律ソフトウェアセキュリティの分野で有益であり得る。幾つかの状況では、未知のバイナリプログラムは、未知のバイナリプログラムの人間のテスターに利用可能であるが、未知のバイナリプログラムに関連する仕様書、文書又はソースコードは利用可能ではないことがある。幾つかの既存の方法は、未知のバイナリプログラムに対する有効な入力を決定しようとする。しかしながら、これらの方法は、ランダムに生成されたテスト入力に頼り、又は他の欠点を有する。
【００１０】
未知のバイナリプログラムに対する有効な入力シーケンスを決定するための更に別の要素は、プラットフォーム独立性を有し得る。プラットフォーム独立性は、他の利点を提供すると共に、方法の移植性を有利に向上できる。
【００１１】
現在、上述の要素を含む、未知のバイナリプログラムに対する有効な入力シーケンスを決定するための方法は存在しない。種々の方法が、未知のバイナリプログラムに対する有効な入力を決定するために用いられる。しかしながら、これらの方法のいずれも、未知のバイナリプログラムに対する有効な入力シーケンスを決定する許容可能な方法の上述の要素を全く又はその一部でさえ提供しない。
【００１２】
１つのこのような方法は、「シンボル実行」として参照され得る。シンボル実行アプローチは、場合によってはプログラムのクラッシュを含む種々の実行経路に沿ってプログラムを駆動し得る、未知のバイナリプログラムに対する入力を決定するステップを含む。このアプローチは、幾つかの独立した事例で成功し得る。しかしながら、シンボル実行アプローチに関連する１つの欠点は、未知のバイナリプログラムに関連するソースファイルの使用である。幾つかの事例では、ソースファイルは利用できない場合がある。その結果、シンボル実行アプローチの実施は、これらの事例では可能でない場合がある。他の欠点は、シンボル実行アプローチが良好にスケーリングされず、したがって多くの共通シナリオで動作しないことであり得る。例えば、シンボル実行アプローチは、浮動小数点演算を含む又はプログラムの実行中に集められた入力に対する非線形制約を含むプログラムと共に動作する知られている問題を有する。少なくともこれらの理由から、シンボル実行アプローチは、未知のバイナリプログラムに対する有効な入力を決定する許容可能な方法ではない。
【００１３】
別の方法は、「ブラックボックスファジング」として知られる。このアプローチは、ストリングの選択、及び該ストリングのランダムな変更、を含み得る。ストリングは、各々の変更の後に、入力として未知のバイナリプログラムに供給され得る。このアプローチは所与の十分な時間動作するが、ブラックボックスファジングにより生成された入力の大部分は無効な入力である。これは、追加の有効な入力を変化させ及び識別するために有効な入力が必要なので、問題である。ブラックボックスファジングに関連する更なる問題は、このアプローチがランダム入力に頼っているため、ブラックボックスファジングを実施した結果が高いカバレッジを達成するか否かが分からないので、未知のバイナリプログラムの高いカバレッジを保証できないことである。
【００１４】
別の方法は、「ホワイトボックスファジング」として知られる。ホワイトボックスファジングアプローチは、ブラックボックスファジングと類似するが、テスト入力を生成するために分析され得るシンボル制約を集めるために、有効な入力が使用される点が異なる。ホワイトボックスファジングアプローチは、ランダムに届けられたのではない少なくとも幾つかの入力を含むので、ブラックボックスファジングより改善されたと考えられる。しかしながら、ホワイトボックスアプローチは、テスト入力を決定するために実施される前に、前提条件として有効な入力を必要とする。幾つかの例では、有効な入力は、ホワイトボックスファジングアプローチのシードとして利用できない。この理由から、単独で実施されるホワイトボックスファジングアプローチは、未知のバイナリプログラムに対する有効な入力を決定する問題を解決できない。
【００１５】
別の方法は、プログラムのコードがユニットに分割され体系的にテストされる「ユニットテスト」として知られている。幾つかの例ではユニットテストはバイナリプログラムの高いカバレッジテストを達成できるが、このアプローチは、常に、ソースファイル又はバイナリプログラムの仕様書のようなバイナリプログラムに関連する他の文書を必要とする。この情報無しでは、ユニットテストは実施できない。したがって、ユニットテストアプローチは、ソースファイル又は何らかの他の文書を必要とするので、未知のバイナリプログラムに対する有効な入力を決定する問題を解決できない。ユニットテストに関連する別の欠点は、プラットフォーム依存性である。ユニットテストアプローチは、低速且つ高価であるとも考えられる。
【００１６】
別の方法は、「仕様に基づくテスト」として知られる。しかしながら、名称が意味するように、仕様に基づくテストアプローチは、常に、ソースファイル又は未知のバイナリプログラムに関連する他の文書を必要とする。したがって、このアプローチは、ソースファイル又は何らかの他の文書を必要とするので、未知のバイナリプログラムに対する有効な入力を決定する問題を解決できない。ユニットテストと同様に、仕様に基づくテストアプローチは、プラットフォーム依存であり、低速且つ高価であると考えられる。
【００１７】
他の方法は、「リバースコードエンジニアリング」を含み得る。これらのアプローチは、「情報交換分析」アプローチ、「分解」アプローチ、及び「デコンパイル」アプローチを含み得る。情報交換分析アプローチは、未知のバイナリプログラムにより情報が交換されない場合、効率的ではないことがある。したがって、この理由から、このアプローチは、限られ許容可能ではない。分解アプローチは、生のアセンブリコードの静的又は動的分析に頼る。これは多くの欠点を有する。例えば、生のアセンブリコードの静的又は動的分析は、計算コストが高く、不正確であり、良好にスケーリングされず、有意な性能オーバヘッドを導入する可能性が高い。デコンパイルアプローチは、未知のバイナリプログラムに関連するソースコードを再構成し、ソースコード及び未知のバイナリプログラムを用いてテストを進めようとする。しかしながら、実際はソースコードファイルが再構成しようと試みる元のソースコードと実質的に異なるために、実際にはデコンパイルアプローチは、多くの状況で動作せず、使用できない又は高品質ではないソースコードファイルをレンダリングしてしまう場合がある。
【００１８】
本開示で議論する幾つかの実施形態は、未知のバイナリプログラムに対する有効な入力シーケンスを決定するシステム及び／又は方法に関連する。上述の及び他の実施形態では、有効な入力シーケンスは、２以上の入力コマンド及び引数のシーケンスであっても良い。未知のバイナリプログラムに対する有効な入力シーケンスを決定することにより、未知のバイナリプログラムは、未知のバイナリプログラムのいかなる知識も有しないでテストできる。
【００１９】
幾つかの実施形態では、未知のバイナリプログラムに対する有効な入力シーケンスは、複数の入力シーケンスにより未知のバイナリプログラムを実行することに基づき決定される。複数の入力シーケンスを用いた未知のバイナリプログラムの実行中に、未知のバイナリプログラムの実行トレースセットは、複数の入力シーケンスの各々の実行中に記録されても良い。実行トレースセットは、比較されても良い。比較に基づき、特定の入力シーケンスが、未知のバイナリプログラムに新しい状態へ移させる、未知のバイナリプログラムに対する有効な入力シーケンスである可能性が高いか否かが決定されても良い。
【００２０】
幾つかの実施形態では、本開示に記載のシステム及び／又は方法は、ランダム入力生成に頼らなくても良い。この方法では、本開示に記載のシステム及び／又は方法は、有効な入力シーケンスを用いて未知のバイナリプログラムの高いカバレッジを達成できる。比較すると、ブラックボックスファジング及びその他のようなランダム入力生成に頼る他の技術は、未知のバイナリプログラムの高いカバレッジを達成できないことがある。
【００２１】
幾つかの実施形態では、本開示に記載のシステム及び／又は方法は、ラプラットフォーム独立であっても良い。その結果、本開示に記載のシステム及び／又は方法は、移植可能であり、種々の動作環境で使用され得る。幾つかの実施形態では、本開示に記載のシステム及び／又は方法は、ソースコード又は未知のバイナリプログラムに関連する文書を有しないで成功裏に実装され得る。幾つかの実施形態では、本開示に記載のシステム及び／又は方法は、パケットスニフィング、バス分析又は情報交換に頼る任意の他の方法を有しないで実装され得る。その結果、本開示に記載のシステム及び／又は方法は、リバースコードエンジニアリング技術を使用しないで実施され得る。
【００２２】
図１は、本開示に記載の少なくとも１つの実施形態により構成される例示的な入力シーケンス決定処理１００を示す。幾つかの実施形態では、処理１００は、未知のバイナリプログラム１０２への入力の有効なシーケンスを決定するために、計装（instrumentation）モジュール１１０、実行モジュール１２０、パーティションモジュール１３０、及び決定モジュール１５０を用いても良い。代替又は追加で、処理１００は、フローグラフモジュール１４０も用いても良い。
【００２３】
計装モジュール１１０は、未知のバイナリプログラム１０２を受信するよう構成されても良い。未知のバイナリプログラム１０２は、バイナリプログラム全体、又はプログラムの１又は複数の機能若しくは他の特長のようなバイナリプログラムの部分であっても良い。上述の及び他の実施形態では、未知のバイナリプログラム１０２は、プログラムのコンパイルされたバージョンを有しても良い。プログラムは、プログラムの機能を記述するコード及びルーチンを有しても良い。プログラムのコード及びルーチンは、プログラム及びプログラムのコンパイルされたバージョンである未知のバイナリプログラム１０２にとって有効であり得る入力を定めても良い。幾つかの実施形態では、プログラムに対する入力は、１又は複数の入力ストリングを有しても良い。コード及びルーチンにより有効であると定められない入力は、プログラムに対する、したがって未知のバイナリプログラム１０２に対する無効な入力であり得る。
【００２４】
幾つかの実施形態では、未知のバイナリプログラム１０２は、処理状態を把握するプログラムであっても良い。上述の及び他の実施形態では、処理状態を把握するプログラムは、過去の記憶を有するプログラムであっても良い。処理状態を把握するプログラムでは、前のトランザクションは、記憶されても良く、現在のトランザクションに影響を与えても良い。例えば、受信された前のデータ入力に関する情報は、変数に格納され、現在のデータ入力の処理に影響を与えるために使用されても良い。処理状態を把握するプログラムとして、プログラムは、処理状態を把握しないプログラムであってはならない。上述の及び他の実施形態では、処理状態を把握しないプログラムは、過去の記憶を有しないプログラムであっても良い。その結果、全ての要求又はトランザクションは、まるで最初に実行され及び前の要求又はトランザクションに関連しないかのようにプログラムにより実行され得る独立した要求又はトンザクションであっても良い。したがって、後続の入力は他の入力と独立であり、前の入力は後続の結果又はプログラム応答に影響を与えない。
【００２５】
未知のバイナリプログラム１０２は、処理装置による実行のために、バイナリ形式にエンコードされ及び非一時的コンピュータ可読記憶媒体に格納されたコード及びルーチンを有しても良い。未知のバイナリプログラム１０２のコード及びルーチンはテキストとして人間により解釈され得る部分を有しても良いが、未知のバイナリプログラム１０２のコード及びルーチンは、人間に可読でなくても良い。上述及び他の実施形態では、コード及びルーチンは、機械により可読あっても良い。例えば、コード及びルーチンは、バイナリ又は何らかの他の機械可読フォーマットであっても良い。
【００２６】
未知のバイナリプログラム１０２に対する有効な入力は分からないので、未知のバイナリプログラム１０２は、「未知」であり得る。例えば、未知のバイナリプログラム１０２に関連する仕様、文書、又はソースコードは、未知のバイナリプログラム１０２の人間のテスター又は他のテスト設備に利用可能でなくても良い。その結果、人間のテスター又は他のテスト設備のテスターは、未知のバイナリプログラム１０２の有効な入力を決定することができなくても良い。
【００２７】
計装モジュール１１０は、未知のバイナリプログラム１０２に基づき、計装（instrumented）バイナリプログラム１１２を生成するよう構成されても良い。上述の及び他の実施形態では、計装バイナリプログラム１１２を生成するために、計装モジュール１１０は、未知のバイナリプログラム１０２を計装（instrument）しても良い。未知のバイナリプログラム１０２を計装するために、計装モジュール１１０は、未知のバイナリプログラム１０２に追加コード命令を入力しても良い。追加コード命令は、未知のバイナリプログラム１０２の実行又は実行時間に関する情報を出力しても良い。計装バイナリプログラム１１２の中の追加コード命令により出力される追加情報は、計装バイナリプログラム１１２の実行トレースであっても良い。例えば、幾つかの実施形態では、実行トレースは、未知のバイナリプログラム１０２の実行中の、特に、メモリアドレス、レジスタ値、関数呼び出し、スレッド、及び割り込み信号、に関する情報を有しても良い。
【００２８】
別の例として、実行トレースは、未知のバイナリプログラム１０２により実行される命令ブロックの開始メモリアドレスであっても良い。未知のバイナリプログラム１０２により実行される命令ブロックは、単一の開始命令と単一の終了命令とを有する命令セットであっても良い。上述の及び他の実施形態では、単一の開始命令と単一の終了命令とを有する命令セットは、ジャンプ又はジャンプ目標を有しない未知のバイナリプログラム１０２の中の直線的ブロックであっても良い。
【００２９】
幾つかの実施形態では、実行トレースは、時間の関数として出力されても良い。例えば、実行トレースは、時間的な実行順序で出力されても良い。したがって、第１の命令ブロックが第１の時間に実行されると、第１の実行トレースは、第１の時間における第１の命令ブロックの実行の記録であっても良い。第２の命令ブロックが第２の時間に実行されても良く、第２の実行トレースは、第２の時間における第２の命令ブロックの実行の記録であっても良い。第１の命令ブロックが第３の時間に再び実行されても良く、第３の実行トレースは、第３の時間における第１の命令ブロックの実行の記録であっても良い。上述の及び他の実施形態では、第２の命令ブロックは、未知のバイナリプログラム１０２のリストの中で、第１の命令ブロックの前にあっても良いが、実行の時間は、未知のバイナリプログラム１０２の中の命令リストの代わりに、実行トレースを順序付けるために用いられても良い。
【００３０】
上述の及び他の実施形態では、実行トレースは、未知のバイナリプログラム１０２の計装無しでは未知のバイナリプログラム１０２により出力されない計装バイナリプログラム１１２により出力される情報であっても良い。したがって、実行トレースは未知のバイナリプログラム１０２の計装の結果として生じ、未知のバイナリプログラム１０２の通常の出力ではない。
【００３１】
幾つかの実施形態では、計装モジュール１１０は、ＰＩＮのようなバイナリ計装プログラム又は何らかの他のバイナリ計装プログラムを有しても良い。計装モジュール１１０は、計装バイナリプログラム１１２を、実行モジュール１２０に提供しても良い。
【００３２】
実行モジュール１２０は、計装バイナリプログラム１１２と、入力シーケンス１０４と、を受信するよう構成されても良い。幾つかの実施形態では、入力シーケンス１０４は、各々、未知のバイナリプログラム１０２に対する２以上の異なる入力を有しても良い。幾つかの実施形態では、未知のバイナリプログラム１０２に対する入力は、予め発見され及び未知のバイナリプログラム１０２に対する有効な入力であると決定されても良い。しかしながら、未知のバイナリプログラム１０２に対する入力を決定したことは、未知のバイナリプログラム１０２に入力を提供する有効なシーケンスを示さない。例えば、未知のバイナリプログラム１０２は４個の異なる入力を認識することが発見されても良い。入力のうちの１つを受信した後に、未知のバイナリプログラム１０２は、入力のうちの別のもの又は同じものを期待しても良い。上述の及び他の実施形態では、未知のバイナリプログラム１０２に提供され得る、１６個の異なる２入力長入力シーケンスが存在しても良い。処理１００は、１６個の異なる２入力長入力シーケンスのうちのどれが、未知のバイナリプログラム１０２に対する有効な入力シーケンスであるかを決定するよう構成されても良い。
【００３３】
幾つかの実施形態では、有効な２入力長シーケンスを決定した後に、処理１００は、有効な３入力長、４入力長、又は５入力長シーケンス又は他の長さのシーケンスが存在するかどうかを決定しても良い。幾つかの実施形態では、上述のように、未知のバイナリプログラム１０２は、処理状態を把握するプログラムであっても良い。上述の及び他の実施形態では、入力又は入力シーケンスを入れることにより別の状態に入った後に、未知のバイナリプログラム１０２に対する追加入力が発見されても良い。上述の及び他の実施形態では、処理１００は、有効な入力シーケンスを決定するとき、追加入力を用いても良い。
【００３４】
幾つかの実施形態では、シーケンスの中の２以上の異なる入力は、順序付けられて、入力がそれらの関連する順序で未知のバイナリプログラム１０２に提供されるようにしても良い。例えば、入力シーケンス１０４のうちの１つの中の第１の入力は、未知のバイナリプログラム１０２に最初に提供されても良く、入力シーケンス１０４のうちの１つの中の第２の入力は、未知のバイナリプログラム１０２に２番目に提供されても良い。
【００３５】
幾つかの実施形態では、入力シーケンス１０４のために使用される入力は、それぞれ、未知のバイナリプログラム１０２に対するコマンドと、該コマンドに関連する引数と、を有しても良い。引数は、コマンドを受信した後に、未知のバイナリプログラム１０２により期待されても良い。例えば、コマンドは、未知のバイナリプログラム１０２が特定の関数を呼び出すことになる、未知のバイナリプログラム１０２の中の「呼び出し」コマンドであっても良い。上述の及び他の実施形態では、「呼び出し」コマンドに関連する引数は、未知のバイナリプログラム１０２の実行のそのポイントで呼び出され得る、未知のバイナリプログラム１０２の内部関数であっても良い。別の例として、未知のバイナリプログラム１０２の中のコマンドは、未知のバイナリプログラム１０２の機能を増大させる「権限付与」コマンドであっても良い。上述の及び他の実施形態では、「権限付与」コマンドの引数は、未知のバイナリプログラム１０２に未知のバイナリプログラム１０２の他の処理を実行させるための、未知のバイナリプログラム１０２により使用されるトークン又はパスワードであっても良い。入力シーケンスの有効なコマンド及び引数を決定する方法の更なる説明は、図４に関連して記載され得る。代替又は追加で、入力シーケンス１０４の構成の更なる説明は、図４に関して記載され得る。
【００３６】
実行モジュール１２０は、入力シーケンス１０４の各々について別個に、計装バイナリプログラム１１２を実行するよう構成されても良い。上述の及び他の実施形態では、計装バイナリプログラム１１２の各々の実行は、入力シーケンス１０４のうちの１つを計装バイナリプログラム１１２に対する入力として用いて実行されても良い。例えば、３個の入力シーケンス１０４が存在する場合、実行モジュール１２０は、計装バイナリプログラム１１２を、３個の入力シーケンス１０４の各々について１回の３回実行しても良い。
【００３７】
入力シーケンス１０４のうちの１つを用いる計装バイナリプログラム１１２の各々の実行中に、実行モジュール１２０は、計装バイナリプログラム１１２により生成された実行トレースを記録するよう構成されても良い。したがって、実行モジュール１２０は、複数の実行トレースセット１２２を生成しても良い。実行トレースセット１２２の各々は、計装バイナリプログラム１１２の１回の実行について生成されても良い。例えば、入力シーケンス１０４のうちの１つを用いる実行モジュール１２０の１回の実行中に生成された実行トレースは、実行トレースセット１２２のうちの１つを形成しても良い。したがって、実行トレースセット１２２のうちの各々のセットは、入力シーケンス１０４のうちの１つに対応し及び関連付けられても良い。
【００３８】
実行トレースセット１２２の中の実行トレースは、計装バイナリプログラム１１２の中の基本命令ブロックの実行の記録であっても良い。幾つかの実施形態では、実行トレースは、実行される１又は複数の命令ブロックに関連するメモリ位置の数値のような数値を含み又はそれに関連付けられても良い。例えば、ブロックは、実行トレースに関連するメモリ位置で実行を開始する、いかなるジャンプ又はジャンプ目標を有しない直線的コードピースであっても良い。上述の及び他の実施形態では、別の実行トレースは、コードが別のメモリ位置へジャンプするとき、開始しても良い。次の実行トレースは、他のメモリ位置を含み又はそれに関連付けられても良い。実行トレースセット１２２は、パーティションモジュール１３０に提供されても良い。
【００３９】
パーティションモジュール１３０は、実行トレースセット１２２を受信するよう構成されても良い。幾つかの実施形態では、パーティションモジュール１３０は、実行トレースセット１２２の各々をパーティショニングするよう更に構成されても良い。上述の及び他の実施形態では、実行トレースセット１２２の各々をパーティショニングするステップは、実行トレースセット１２２の各々のパーティション位置を決定するステップを有しても良い。
【００４０】
パーティション位置を決定するために、パーティションモジュール１３０は、実行トレースセット１２２の各々の中の、特定の実行トレース又は実行トレースシーケンスの位置を特定しても良い。特定の実行トレース又は実行トレースシーケンスは、パーティション位置であっても良い。幾つかの実施形態では、特定の実行トレース又は実行トレースシーケンスは、計装バイナリプログラム１１２にいかなる入力も適用しないで、計装バイナリプログラム１１２を実行することに基づき決定されても良い。上述の及び他の実施形態では、特定の実行トレース又は実行トレースシーケンスは、計装バイナリプログラム１１２の実行中にロギングされた最後の実行トレース又は最後の実行トレースシーケンスであっても良い。例えば、最後の実行トレースシーケンスは、２、３、４、５、６、又はそれより多くの実行トレースを有しても良い。上述の及び他の実施形態では、特定の実行トレース又は実行トレースシーケンスは、パーティションフラグとして参照されても良い。
【００４１】
幾つかの実施形態では、パーティションフラグは、バイナリプログラム１１２が入力を期待していることの指示であっても良い。例えば、パーティションフラグが、計装バイナリプログラム１１２の実行中にロギングされた最後の実行トレース又は最後の実行トレースシーケンスであるときである。ロギングされた最後の実行トレース又は最後の実行トレースシーケンスであるパーティションフラグは、計装バイナリプログラム１１２が停止され、継続する前に入力を待っていることを示し得る。上述の及び他の実施形態では、したがって、パーティションフラグは、計装バイナリプログラム１１２が開始し及び特定の入力に対する作用を停止する、実行トレース１１２のセットの各々の中の位置を示しても良い。例えば、計装バイナリプログラム１１２は、２入力のシーケンスに基づき実行しても良い。実行により生成された実行トレースは、パーティションフラグの３個のインスタンスを有しても良い。実行トレースの始めとパーティションフラグの第１のインスタンスとの間は、第１の入力を受信する前の、計装バイナリプログラム１１２の実行を示しても良い。パーティションフラグの第１のインスタンスとパーティションフラグの第２のインスタンスとの間は、第１の入力を受信している最中及びその後、且つ第２の入力を受信する前の、計装バイナリプログラム１１２の実行を示しても良い。パーティションフラグの第２のインスタンスとパーティションフラグの第３のインスタンスとの間は、第２の入力を受信している最中及びその後の、計装バイナリプログラム１１２の実行を示しても良い。
【００４２】
パーティションモジュール１３０は、パーティションフラグの位置を決定するために、実行トレース１１２のセットの各々を個別に見直しても良い。幾つかの実施形態では、パーティションフラグは、複数回生じても良い。実行トレースセット１２２の中のパーティションフラグの位置は、パーティション位置であっても良い。パーティションモジュール１３０は、実行トレースセット１２２を、それらの対応するパーティション位置に基づき、区分して、パーティショニング済み実行トレースセット１３２を生成しても良い。例えば、２入力のシーケンスでは、実行トレースセットは、３個の部分に区分されても良い。第１の部分は、計装バイナリプログラム１１２によりいかなる入力も受信されないときに対応しても良い。第２の部分は、計装バイナリプログラム１１２により第１の入力が受信され作用されるときに対応しても良い。第３の部分は、計装バイナリプログラム１１２により第２の入力が受信され作用される場所に対応しても良い。パーティションモジュール１３０は、決定モジュール１５０に、パーティショニング済み実行トレースセット１３２を送信しても良い。
【００４３】
決定モジュール１５０は、パーティションモジュール１３０から、パーティショニング済み実行トレースセット１３２を受信しても良い。決定モジュール１５０は、パーティショニング済み実行トレースセット１３２を比較するよう構成されても良い。パーティショニング済み実行トレースセット１３２の比較に基づき、決定モジュール１５０は、入力シーケンス１０４が存在する場合にはそのうちのどれを、未知のバイナリプログラムが有効として受け付けるかを決定しても良い。
【００４４】
幾つかの実施形態では、決定モジュール１５０は、パーティショニング済み実行トレースセット１３２の全部を比較しても良い。代替又は追加で、決定モジュール１５０は、計装バイナリプログラム１１２への同じ入力の実行に基づき生成されるパーティショニング済み実行トレースセット１３２を比較しても良い。例えば、決定モジュール１５０は、各々の入力シーケンスの最後の入力の実行に対応する、パーティショニング済み実行トレースセット１３２の最後のパーティションを比較しても良い。最後の入力が有効であると決定された場合、入力シーケンス全体が正しい入力シーケンスであることが示唆され得る。したがって、上述の及び他の実施形態では、最後の入力に対応するパーティショニング済み実行トレースセット１３２の最後のパーティションが比較されても良く、パーティショニング済み実行トレースセット１３２のパーティションは比較されなくても良い。
【００４５】
上述の及び他の実施形態では、パーティショニング済み実行トレースセット１３２の最後のパーティションが、最後のパーティションが全て同じであることを示すとき、入力シーケンスのいずれも、シーケンシャル入力として未知のバイナリプログラム１０２により受け入れられないと決定されても良い。最後のパーティションの全部が同じとき、未知のバイナリプログラム１０２が最後の入力の全部を同じ方法で処理したことを示し得る。各々の最後の入力を同じ方法で処理することは、未知のバイナリプログラム１０２が最後の入力を有効な入力として受け入れなかったことを示し得る。したがって、最後の入力の全部は無効であり得る。
【００４６】
幾つかの実施形態では、パーティショニング済み実行トレースセット１３２の比較が、最後のパーティションのうちの少なくとも別の２つが同じであること、及び１又は複数の他の最後のパーティションが、最後のパーティションのうちの該同じ２つと異なることを示すとき、最後のパーティションのうちの１又は複数を生成するために使用された入力シーケンスは、未知のバイナリプログラム１０２により有効な入力シーケンスとして受け入れられたことを示し得る。最後のパーティションの一部が、同じである最後のパーティションのうちの他のものと異なるとき、未知のバイナリプログラム１０２は異なる方法で最後の入力の一部を処理したことを示し得る。最後の入力の一部を異なる方法で処理することは、未知のバイナリプログラム１０２が最後の入力シーケンスの一部を受け入れ、他の部分を受け入れなかったことを示し得る。受け入れられない入力は、未知のバイナリプログラム１０２により同じく処理される傾向があっても良いが、受け入れられた最後の入力は、各々、未知のバイナリプログラム１０２により異なる方法で処理されても良い。したがって、最後の入力の一部は有効であり、他は無効であり得る。
【００４７】
幾つかの実施形態では、処理１００は、フローグラフモジュール１４０を有しても良い。上述の及び他の実施形態では、パーティションモジュール１３０は、決定モジュール１５０ではなく、フローグラフモジュール１４０に、パーティショニング済み実行トレースセット１３２を送信しても良い。
【００４８】
フローグラフモジュール１４０は、パーティションモジュール１３０から、パーティショニング済み実行トレースセット１３２を受信するよう構成されても良い。フローグラフモジュール１４０は、パーティショニング済み実行トレースセット１３２の各々のパーティションの各々について、制御フローグラフを決定するよう更に構成されても良い。制御フローグラフは、実行トレースセット１２２に基づき、計装バイナリプログラム１１２の実行によりトラバースされる経路を表しても良い。制御フローグラフは、図３に示される。概して、制御フローグラフは、エッジによりリンクされるノードを有する。幾つかの実施形態では、ノードは、直線的コードのブロックを表す単一の実行トレースを表し得る。直線的コードの異なるブロックの間のジャンプ又は変化は、エッジにより表され得る。上述の及び他の実施形態では、実行トレースのうちの１又は複数はノードにより表され、エッジは、次の１又は複数の実行トレースへの変化を表し得る。フローグラフモジュール１４０は、制御フローグラフ１４２を決定モジュール１５０へ送信しても良い。
【００４９】
図２は、本願明細書に記載の少なくとも１つの実施形態に従い構成され得る、パーティショニング済み実行トレースセットの各々のパーティションの各々について制御フローグラフを構築する例示的な方法２００を示す。方法２００は、幾つかの実施形態では、図５のシステム５００のようなシステムにより実施されても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。
【００５０】
方法２００は、ブロック２０２で開始し、実行トレースが選択されても良い。幾つかの実施形態では、選択された第１の実行トレースは、パーティショニング済み実行トレースセット１３２のうちの１つのセットからのパーティションの第１の実行トレースであっても良い。第１の実行トレースが選択された後に、第２の及び後続の実行トレースの選択は、パーティションの実行トレースシーケンスの中の次の実行トレースに基づいても良い。
【００５１】
ブロック２０４で、選択された実行トレースがグラフの中に示されるかどうかが決定されても良い。選択された実行トレースがグラフの中に示されると、方法２００はブロック２０６へ進んでも良い。選択された実行トレースがグラフの中に示されないとき、方法２００はブロック２０８へ進んでも良い。幾つかの実施形態では、実行トレースが、グラフの中に既にあるノードと関連する又はそれに含まれるメモリ位置と同じ又はそれと類似するメモリ位置を含む又はそれに関連するとき、選択された実行トレースは、グラフの中に示されても良い。
【００５２】
ブロック２０６で、グラフの中で選択された実行トレースを示す、グラフの中に既に存在するノードは、現在のノードとして設定されても良い。方法２００は、ブロック２０２に戻り、別の実行トレースがパーティショニング済み実行トレースセット１３２から選択されても良い。
【００５３】
ブロック２０８で、選択された実行トレースを表す新しいノードが生成されても良い。ブロック２１０で、新しいノードは、現在のノードからエッジにより付加されても良い。新しいノードが第１のノードであるとき、新しいノードは制御フローグラフの中の第１のノードであるので、新しいノードは、現在のノードから付加されなくても良い。
【００５４】
ブロック２１２で、新しいノードは、現在のノードとして設定されても良い。方法２００は、ブロック２０２に戻り、別の実行トレースがパーティショニング済み実行トレースセット１３２から選択されても良い。
【００５５】
当業者は、この処理及び本願明細書に開始した他の処理及び方法において、その処理及び方法で実行される機能が異なる順序で実施されても良いことを理解するだろう。さらに、概略のステップ及び動作は、単に例として提供され、幾つかのステップ及び動作は、開示の実施形態の本質から逸脱することなく、任意であり、より少ないステップ及び動作に組み合わされ、又は追加ステップ及び動作に拡張されても良い。
【００５６】
本願明細書に記載の少なくとも一実施形態に従い構成され得る例示的な制御フローグラフ３００は図３に示される。制御フローグラフ３００は、図３にも示される実行トレースリスト３２０に基づき構築されても良い。実行トレースリスト３２０は、１２、１４、１５、１４、１６、１２、１８と番号を付された７個の記録された実行トレースを有しても良い。制御フローグラフ３００は、５個のノード、つまり第１のノード３０２、第２のノード３０４、第３のノード３０６、第４のノード３０８、及び第５のノード３１０を有しても良い。
【００５７】
制御フローグラフ３００を構築するために実行トレースリスト３２０からの７個の記録された実行トレースを用いる方法２００の例示的な実行を以下に説明する。番号１２を付された第１の実行トレースが選択されても良い。第１の実行トレースは新しいノードなので、第１のノード３０２が生成され、現在のノードとして設定されても良い。番号１４を付された第２の実行トレースが選択されても良い。第２の実行トレースは、第１のノード３０２により表される実行トレースと異なるので、新しいノード、つまり第２のノード３０４が生成される。第２のノード３０４は、第１のノード３０２である現在のノードに付加される。第２のノード３０４は、現在のノードとして設定される。
【００５８】
番号１５を付された第３の実行トレースが選択されても良い。第３の実行トレースは、第１のノード３０２又は第２のノード３０４により表される実行トレースと異なるので、新しいノード、つまり第３のノード３０６が生成される。第３のノード３０６は、第２のノード３０４である現在のノードに付加される。第３のノード３０６は、現在のノードとして設定される。
【００５９】
番号１４を付された第４の実行トレースが選択されても良い。第４の実行トレースは、第２のノード３０４により表される実行トレースと同じなので、第２のノード３０４は現在のノードとして設定され、別の実行トレースが選択される。
【００６０】
番号１６を付された第５の実行トレースが選択されても良い。第５の実行トレースは、第１のノード３０２、第２のノード３０４又は第３のノード３０６により表される実行トレースと異なるので、新しいノード、つまり第４のノード３０８が生成される。第４のノード３０８は、第２のノード３０４である現在のノードに付加される。第４のノード３０８は、現在のノードとして設定される。
【００６１】
番号１２を付された第６の実行トレースが選択されても良い。第６の実行トレースは、第１のノード３０２により表される実行トレースと同じなので、第１のノード３０２は現在のノードとして設定され、別の実行トレースが選択される。
【００６２】
番号１８を付された第７の実行トレースが選択されても良い。第７の実行トレースは、他のノードにより表される実行トレースと異なるので、新しいノード、つまり第５のノード３１０が生成される。第５のノード３１０は、第１のノード３０２である現在のノードに付加される。第５のノード３１０は、現在のノードとして設定される。
【００６３】
図１に戻り、決定モジュール１５０は、フローグラフモジュール１４０から制御フローグラフ１４２を受信しても良い。決定モジュール１５０は、制御フローグラフ１４２を比較するよう構成されても良い。制御フローグラフ１４２の比較に基づき、決定モジュール１５０は、入力シーケンス１０４が存在する場合にはそのうちのどれを、未知のバイナリプログラムが有効として受け付けるかを決定しても良い。
【００６４】
幾つかの実施形態では、決定モジュール１５０は、フローグラフモジュール１４０からの制御フローグラフの全部を比較しても良い。代替又は追加で、決定モジュール１５０は、計装バイナリプログラム１１２への同じ入力の実行に基づき生成されるパーティショニング済み実行トレースセット１３２に対応する制御フローグラフを比較しても良い。例えば、決定モジュール１５０は、各々の入力シーケンスの最後の入力の実行に対応する、パーティショニング済み実行トレースセット１３２の最後のパーティションについて生成される制御フローグラフ１４２を比較しても良い。最後の入力が有効であると決定された場合、入力シーケンス全体が正しい入力シーケンスであることが示唆され得る。したがって、上述の及び他の実施形態では、最後の入力に対応する制御フローグラフ１４２は比較され、他の入力に対応する制御フローグラフ１４２は比較されなくても良い。
【００６５】
上述の及び他の実施形態では、制御フローグラフ１４２の比較が、入力シーケンスの各々の最後の入力の制御フローグラフ１４２が全て同じであることを示すとき、入力シーケンスのいずれも、シーケンシャル入力として未知のバイナリプログラム１０２により受け入れられないと決定されても良い。制御フローグラフ１４２の全部が同じとき、未知のバイナリプログラム１０２が最後の入力の全部を同じ方法で処理したことを示し得る。各々の最後の入力を同じ方法で処理することは、未知のバイナリプログラム１０２が最後の入力を有効な入力として受け入れなかったことを示し得る。したがって、最後の入力の全部は無効であり得る。
【００６６】
幾つかの実施形態では、各々の入力シーケンスの最後の入力についての制御フローグラフ１４２の比較が、制御フローグラフ１４２のうちの少なくとも別の２つが同じであり、１又は複数の他の制御フローグラフ１４２が制御フローグラフ１４２のうちの該同じ２つと異なることを示すとき、制御フローグラフ１４２のうちの１又は複数を生成するために使用された入力シーケンスは、未知のバイナリプログラム１０２により有効な入力シーケンスとして受け入れられることを示し得る。制御フローグラフ１４２のうちの一部が、同じ制御フローグラフ１４２のうちの他のものと異なるとき、未知のバイナリプログラム１０２は異なる方法で最後の入力の一部を処理したことを示し得る。最後の入力の一部を異なる方法で処理することは、未知のバイナリプログラム１０２が最後の入力シーケンスの一部を受け入れ、他の部分を受け入れなかったことを示し得る。受け入れられない入力は、未知のバイナリプログラム１０２により同じく処理される傾向があっても良いが、受け入れられた最後の入力は、各々、未知のバイナリプログラム１０２により異なる方法で処理されても良い。したがって、最後の入力の一部は有効であり、他は無効であり得る。
【００６７】
幾つかの実施形態では、決定モジュール１５０は、制御フローグラフ１４２の各々について、ストリング表現を生成するよう構成されても良い。上述の及び他の実施形態では、制御フローグラフのストリング表現は、制御フローグラフを直接比較する代わりに、比較されても良い。上述の及び他の実施形態では、制御フローグラフのストリング表現は、制御フローグラフの体系的トラバースに制御フローグラフのノードを含めるストリングを有しても良い。制御フローグラフの体系的トラバースのための種々のアルゴリズムは、制御フローグラフを体系的にトラバースする方法の中でも特に、縦型探索、横型探索、を含む。
【００６８】
図３は、本願明細書に記載の少なくとも１つの実施形態により構成される、制御フローグラフ３００の例示的なストリング表現３３０を示す。ストリング表現３３０は、実行トレースリスト３２０のシーケンシャル順序で、実行トレースリスト３２０と異なる値の全部を有する。ストリング表現３３０を生成する一例は次の通りである。ストリング表現３３０は、第１のノード３０２において開始し、第１のノード３０２を記録する。ストリング表現３３０は、左へ進み、第２のノード３０４を記録する。ストリング表現３３０は、左へ進み、第３のノード３０６を記録する。ストリング表現３３０は左へ進めないので、ストリング表現３３０は、制御フローグラフ３００を上に第３のノード３０６まで進み、次に、右へ第４のノード３０８まで進む。ストリング表現３３０は、右又は左へ進めない、又は既に右及び左に進んでいるので、ストリング表現３３０は、第１のノード３０２へ及び第５のノード３１０の右へ進み、ストリング表現３３０を完了する。
【００６９】
本開示の範囲から逸脱することなく処理１００に対し変更、追加又は省略が行われても良い。例えば、幾つかの実施形態では、パーティションモジュール１３０は、実行トレースセット１２２の各々のパーティション位置及び実行トレースセット１２２を、フローグラフモジュール１４０へ送信し、実行トレースセット１２２をパーティショニングしなくても良い。上述の及び他の実施形態では、フローグラフモジュール１４０は、実行トレースセット１２２をパーティショニングしても良い。
【００７０】
代替又は追加で、パーティションモジュール１３０は、実行トレースセット１２２の各々の１又は複数のパーティションをフローグラフモジュール１４０へ送信し、実行トレースセット１２２の各々のパーティションの全部をフローグラフモジュール１４０へ送信しなくても良い。例えば、上述の及び他の実施形態では、パーティションモジュール１３０は、実行トレースセット１２２の各々の最後のパーティションを送信しても良い。上述の及び他の実施形態では、制御フローグラフ１４２は、実行トレースセット１２２の各々の最後のパーティションを有しても良い。
【００７１】
図４は、本願明細書に記載の少なくとも１つの実施形態に従って構成され得る例示的な入力決定処理４００を示す。処理４００は、入力モジュール４１０を使用しても良く、実行モジュール４２０は、未知のバイナリプログラム４１４に対する入力４１２及び未知のバイナリプログラム４１４に対する入力シーケンス４３０を決定する。未知のバイナリプログラム４１４の中の所与の状態に対する有効な入力を決定するシステム及び方法は、係属中の米国特許出願番号１４／６２０，１０６、２０１５年２月１１日に記載されている。該米国特許出願は、参照することによりその全体が本願明細書に組み込まれる。
【００７２】
幾つかの実施形態では、処理４００は、未知のバイナリプログラム４１４の状態に対する入力４１２を決定しても良い。幾つかの実施形態では、入力４１２は、１又は複数の１又は複数のインデックスを有し得る入力ストリングの中の１又は複数の印刷可能文字であっても良い。プログラムの入力ストリングは、１又は複数のインデックス及び１又は複数の印刷可能文字を有しても良い。インデックスは、印刷可能文字が生じるストリングの中の位置を有しても良い。例えば、受け入れられる入力ストリングが「Ｈｅｌｌｏ」及び「Ｈｏｗｄｙ」である場合、インデックスは「０」、「１」、「２」、「３」、「４」である。本例では、インデックス「０」の有効な文字は、印刷可能文字「Ｈ」を有する。インデックス「１」の有効な文字は、印刷可能文字「ｅ」及び「ｏ」を有する。インデックス「２」の有効な文字は、印刷可能文字「ｌ」及び「ｗ」を有する。インデックス「３」の有効な文字は、印刷可能文字「ｌ」及び「ｄ」を有する。インデックス「４」の有効な文字は、印刷可能文字「ｏ」及び「ｙ」を有する。
【００７３】
有効な入力ストリングと見なされると、入力ストリングに含まれる文字の各々は、未知のバイナリプログラム４１４に対して有効であり得る。有効な入力ストリングの任意の所与のインデックスについて、入力ストリングの中で使用するために利用可能な印刷可能文字の大部分は、無効であり得る。処理４００は、それらが未知のバイナリプログラム４１４に対する有効な入力ストリングの異なるインデックスについて有効な文字であるかどうかを決定するために、印刷可能文字セットを繰り返しテストするよう構成されても良い。
【００７４】
入力モジュール４１０は、印刷可能文字を選択し、実行モジュール４２０に入力４１２として提供するよう構成されても良い。実行モジュール４２０は、第１の印刷可能文字を入力４１２として用いて、未知のバイナリプログラム４１４を実行しても良い。実行モジュール４２０は、入力４１２を用いる未知のバイナリプログラム４１４の実行中に、未知のバイナリプログラム４１４により実行される命令の数を記録しても良い。実行される命令の数は、実行モジュール４２０により命令数４２２として出力されても良い。命令数４２２は、入力モジュール４１０に提供されても良い。
【００７５】
入力モジュール４１０は、命令数４２２が閾範囲より大きいか否かを決定しても良い。入力モジュール４１０は、命令数４２２が閾範囲より大きいとき、第１の印刷可能文字が未知のバイナリプログラム４１４の状態に有効な入力として含まれる候補であり得ると決定しても良い。入力モジュール４１０は、命令数４２２が閾範囲より小さい又はそれに等しいとき、第１の印刷可能文字が未知のバイナリプログラム４１４の第１の状態に有効な入力として含まれる候補でないと決定しても良い。
【００７６】
閾範囲は、実行される命令の数及びテスト制約のモードに基づき決定されても良い。モードは、実行される命令数のモードを有しても良い。例えば、実行される命令数は、セットに格納されても良い。セットは、１又は複数の値を有しても良い。数値は、入力モジュール４１０により提供される各々の入力について実行される命令数を表しても良い。例えば、１００個の命令を生じる第１の入力が実行されると仮定する。第１の入力についての数値は、数「１００」であっても良い。セットは、他の入力についての他の数値を有しても良い。モードは、セットの中で最も頻繁に現れる数値を有しても良い。
【００７７】
テスト制約は、「イプシロン」又は「テスト制約」として参照されても良い。テスト制約は、任意の正の実数を有しても良い。閾範囲の上限は、テスト制約をモードに加算することにより決定されても良い。
【００７８】
第１の印刷可能文字が未知のバイナリプログラム４１４の状態において有効な入力の候補でないとき、入力モジュール４１０は、第２の印刷可能文字を実行モジュール４２０に実行のために提供しても良い。同様の方法で、入力モジュール４１０は、第２の印刷可能文字が未知のバイナリプログラム４１４の状態に有効な入力として含まれる候補であるかどうかを決定しても良い。処理４００は、入力モジュール４１０が未知のバイナリプログラム４１４の状態における有効な入力に含むための候補である文字を決定するまで、指示として動作し続けても良い。
【００７９】
入力モジュール４１０は、入力４１２を形成するために、別の文字を候補文字と連結しても良い。特に、入力モジュール４１０は、第１の候補文字を第１のインデックス位置に、他の文字を第２のインデックス位置に、配置しても良い。上述の及び他の実施形態では、候補文字と他の文字との連結は、部分的に有効な入力として参照されても良い。入力モジュール４１０は、入力４１２を、実行モジュール４２０に提供しても良い。
【００８０】
実行モジュール４２０は、入力４１２を用いて、未知のバイナリプログラム４１４を実行しても良い。未知のバイナリプログラム４１４の実行に基づき、実行モジュール４２０は、命令数４２２を出力しても良い。入力モジュール４１０は、第２のインデックス位置にある他の文字が未知のバイナリプログラム４１４の状態における有効な入力に含まれるための候補であり得るかどうかを、命令数４２２に基づき決定しても良い。
【００８１】
処理４００は、同様の方法で、未知のバイナリプログラム４１４の状態について処理４００により決定され得る有効な入力の全部又は大部分が決定されるまで、続いても良い。
【００８２】
幾つかの実施形態では、入力モジュール４１０は、有効な入力を結合して、入力シーケンス４３０を形成しても良い。幾つかの実施形態では、入力モジュール４１０は、入力シーケンスセット４３０を形成しても良い。入力シーケンスセットの各々は、最後の入力が同じであり且つ各々のシーケンスの中の残りの入力が異なる入力シーケンス４３０を有しても良い。
【００８３】
幾つかの実施形態では、入力シーケンス４３０の入力は、コマンド及びそれに関連する引数であっても良い。上述の及び他の実施形態では、処理４００が所与のコマンドの有効な引数を決定するために可能な印刷可能文字と一緒にコマンドを入力として提供し得る点を除き、処理４００は、コマンドが発見されるのと同様の方法でコマンドの有効な引数を決定しても良い。
【００８４】
幾つかの実施形態では、入力モジュール４１０は、決定された有効な入力に対して所定の入力シーケンス長の全ての可能な入力シーケンス順列を構築しても良く、入力シーケンス順列の全部を入力シーケンス４３０として提供しても良い。上述の及び他の実施形態では、図１の処理１００のような処理は、入力シーケンス４３０のうちのどれが未知のバイナリプログラム４１４に対して有効な入力シーケンスであるかを決定しても良い。上述の及び他の実施形態では、処理は、入力シーケンス４３０の各々を実行し、結果として生じる実行トレースを区分し、制御フローグラフを生成し、制御フローグラフを比較して入力シーケンス４３０のうちのどれが有効であるかを決定しても良い。幾つかの実施形態では、処理は、同じ最後の入力を有する入力シーケンスについて、制御フローグラフを比較して、入力シーケンス４３０のうちのどれが有効かを決定しても良い。幾つかの実施形態では、有効な入力シーケンスを決定した後に、処理４００は、有効な入力シーケンスを入力４１２の開始として用いて、未知のバイナリプログラム４１４に対する追加入力を発見しても良い。上述の及び他の実施形態では、追加入力は、追加入力シーケンス４３０を生成するために用いられても良い。追加入力シーケンス４３０は、次に、図１の処理１００のような処理に提供されても良い。この方法では、処理４００及び図１の処理１００に類似する処理は、一緒に用いられても良い。本開示の範囲から逸脱することなく処理４００に対し変更、追加又は省略が行われても良い。
【００８５】
図５は、本願明細書に記載の少なくとも１つの実施形態により配置され得る例示的な入力決定システム５００のブロック図を示す。図５に示すように、システム５００は、プロセッサ５１０と、メモリ５１２と、データ記憶装置５１４と、通信ユニット５１８と、を有しても良い。
【００８６】
概して、プロセッサ５１０は、任意の適切な特定用途向け又は汎用コンピュータ、コンピューティングエンティティ、又は種々のコンピュータハードウェア若しくはソフトウェアモジュールを有しても良く、任意の適切なコンピュータ可読媒体に格納された命令を実行するよう構成され得る処理装置を用いて実施されても良い。例えば、プロセッサ５１０は、マイクロプロセッサ、マイクロコントローラ、デジタシグナルプロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（FPGA）又はプログラム命令を解釈し及び／若しくは実行し並びに／又はデータを処理するよう構成された任意の他のデジタル若しくはアナログ回路を有しても良い。図５には単一のプロセッサを示したが、プロセッサ５１０は、本願明細書に記載の任意の数の演算を個々に又は共同で実行するよう構成される任意の数のネットワーク又は物理的位置に渡り分散される任意の数のプロセッサを有しても良いことが理解される。幾つかの実施形態では、プロセッサ５１０は、プログラム命令を解釈し及び／又は実行し、及び／又はメモリ５１２、データ記憶装置５１４又はメモリ５１２及びデータ記憶装置５１４に格納されたデータを処理してもよい。幾つかの実施形態では、プロセッサ５１０は、データ記憶５１４からプログラム命令をフェッチし、該プログラム命令をメモリ５１２にロードしても良い。プログラム命令がメモリ５１２にロードされた後、プロセッサ５１０は、それぞれ図１、４、６の処理１００、処理４００及び／又は方法６００を実行するための命令のようなプログラム命令を実行しても良い。
【００８７】
メモリ５１２及びデータ記憶装置５１４は、コンピュータ実行可能命令又はデータ構造を伝える又は格納しているコンピュータ可読記憶媒体又は１又は複数のコンピュータ可読記憶媒体を含み得る。このようなコンピュータ可読媒体は、プロセッサ５１０のような汎用又は特定目的コンピュータによりアクセスできる任意の利用可能な媒体であり得る。例として且つ限定ではなく、このようなコンピュータ可読媒体は、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read−Only  Memory）、ＥＥＰＲＯＭ（Electrically  Erasable  Programmable  Read−Only  Memory）、ＣＤ−ＲＯＭ（Compact  Disc  Read−Only  Memory）又は他の光ディスク記憶装置、磁気ディスク記憶装置又は他の磁気記憶装置、フラッシュメモリ装置（例えば、固体メモリ素子）を含む非一時的コンピュータ可読記憶媒体、又はコンピュータにより実行可能な命令若しくはデータ構造の形式で所望のプログラムコード手段を伝える若しくは格納するために用いられ汎用若しくは特定目的コンピュータによりアクセス可能な他の記憶媒体を有し得る。上述の組合せも、コンピュータ可読記憶媒体の範囲に包含され得る。コンピュータ実行可能命令は、例えば、プロセッサ５１０に特定の工程又は工程のグループを実行させるよう構成される命令及びデータを含み得る。
【００８８】
通信ユニット５１６は、未知のバイナリプログラムを受信し、未知のバイナリプログラムをデータ記憶装置５１４に提供するよう構成されても良い。データ記憶装置５１４により受信された後、プロセッサ５１０を用いる未知のバイナリプログラムに対する入力及び入力シーケンス、並びに命令は、データ記憶装置に格納される。幾つかの実施形態では、決定された入力及び入力シーケンスは、通信ユニット５１６を用いてシステム５００の外部に提供されても良い。
【００８９】
本開示の範囲から逸脱することなくシステム５００に対し変更、追加又は省略が行われても良い。例えば、データ記憶装置５１４は、複数の場所に置かれ、ネットワークを通じてプロセッサ５１０によりアクセスされても良い。
【００９０】
図６は、本願明細書に記載した少なくとも１つの実施形態に従って構成された、未知のバイナリプログラムに対する有効な入力シーケンスを決定する別の例示的な方法６００のフローチャートを示す。方法６００は、幾つかの実施形態では、図５のシステム５００のようなシステムにより実施されても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。
【００９１】
方法６００は、ブロック６０２で開始し、未知のバイナリプログラムに対する複数の入力シーケンスが得られても良い。幾つかの実施形態では、入力シーケンスの各々は、２以上の異なる入力を有しても良い。入力は、未知のバイナリプログラムの有効な入力として予め決定されても良い。幾つかの実施形態では、入力は、未知のバイナリプログラムに対して有効であると決定されたコマンド、及び該コマンドと関連する引数と、を有しても良い。引数も、未知のバイナリプログラムに対して有効であると決定されても良い。幾つかの実施形態では、各々の入力シーケンスの中の最後の入力は同じであっても良い。
【００９２】
ブロック６０４で、未知のバイナリプログラムの計装バージョンは、各々の入力シーケンスについて別個に実行されても良い。未知のバイナリプログラムの計装バージョンの各々の実行は、入力シーケンスのうちの１つを、未知のバイナリプログラムの計装バージョンへの入力として用いても良い。
【００９３】
ブロック６０６で、未知のバイナリプログラムの計装バージョンの各々の実行について、未知のバイナリプログラムの計装バージョンの実行により生成される実行トレースを記録することにより、実行トレースセットが生成されても良い。幾つかの実施形態では、実行トレースセットの生成は、未知のバイナリプログラムの計装バージョンの各々の実行について、実行トレースセットに含めるために実行トレースの一部を選択するステップを有しても良い。上述の及び他の実施形態では、実行トレースセットのために選択された実行トレースの一部は、入力シーケンスの最後の入力が未知のバイナリプログラムに提供された後に生成された実行トレースであっても良い。
【００９４】
幾つかの実施形態では、実行トレースセットに含めるための実行トレースの一部の選択は、複数のステップ又は工程を有しても良い。例えば、実行トレースの一部を選択するステップは、いかなる入力も有しないで未知のバイナリプログラムの計装バージョンを実行するステップと、いかなる入力も有しない実行の終了時に未知のバイナリプログラムの計装バージョンの実行により生成される複数の実行トレースを決定するステップと、を有しても良い。上述の及び他の実施形態では、実行トレースの一部の選択は、決定した複数の実行トレースをパーティション実行トレースとして設定するステップと、入力シーケンスを用いる未知のバイナリプログラムの計装バージョンの実行中に生成される実行トレースの部分を、パーティション実行トレースの最後から２番目の発生と最後の発生との間で生じる実行トレースの部分に基づき、選択するステップと、を更に有しても良い。
【００９５】
ブロック６０８で、実行トレースセットは比較されても良い。幾つかの実施形態では、実行トレースセットのうちの１つのセットの中の実行トレースは、未知のバイナリプログラムの計装バージョンにより出力され且つ未知のバイナリプログラムの非計装バージョンにより出力されない未知のバイナリプログラムの中で実行される直線的命令セットに関連するメモリアドレスを表しても良い。
【００９６】
ブロック６１０で、実行トレースセットの比較に基づき、入力シーケンスのうちのどれを、未知のバイナリプログラムが有効であるとして受け入れるかが決定されても良い。幾つかの実施形態では、実行トレースセットの比較が、実行トレースセットは同じであると示すとき、入力シーケンスのいずれも、未知のバイナリプログラムにより受け入れられないと決定されても良い。代替で又は追加で、実行トレースセットの比較が、実行トレースセットのうちの１つが実行トレースセットのうちの同じである少なくとも別の２つと異なることを示すとき、実行トレースセットのうちの該１つに対応する入力シーケンスは、未知のバイナリプログラムにより受け入れられると決定されても良い。
【００９７】
当業者は、この処理及び本願明細書に開始した他の処理及び方法において、その処理及び方法で実行される機能が異なる順序で実施されても良いことを理解するだろう。さらに、概略のステップ及び動作は、単に例として提供され、幾つかのステップ及び動作は、開示の実施形態の本質から逸脱することなく、任意であり、より少ないステップ及び動作に組み合わされ、又は追加ステップ及び動作に拡張されても良い。
【００９８】
例えば、方法６００は、実行トレースセットの各々について制御フローグラフを生成するステップを更に有しても良い。上述の及び他の実施形態では、実行トレースセットの比較は、制御フローグラフの各々のストリング表現を生成するステップと、該ストリング表現を比較するステップと、を有しても良い。上述の及び他の実施形態では、各々の制御フローグラフについてストリング表現を生成するステップは、縦型探索アルゴリズム又は横型探索アルゴリズムを実施するステップを有しても良い。
【００９９】
幾つかの実施形態では、各々の入力シーケンスの中の最後の入力は同じであっても良い。上述の及び他の実施形態では、複数の入力シーケンスは、それぞれ複数の入力シーケンスを含む複数の入力シーケンスセットの中の１つの入力シーケンスセットであっても良い。他の入力シーケンスセットのうちの各々のセットの各々の入力シーケンスの最後の入力は、同じであっても良く、各々の入力シーケンスセットの最後の入力は異なっても良い。例えば、それぞれ４個の入力シーケンスを有する４個の入力シーケンスセットが存在しても良い。第１の入力シーケンスセットの中の各々の入力シーケンスの最後の入力は、同じであっても良く、第２の入力シーケンスセットの中の各々の入力シーケンスの最後の入力は同じであっても良く、第３の入力シーケンスセットの中の各々の入力シーケンスの最後の入力は、同じであっても良く、第４の入力シーケンスセットの中の各々の入力シーケンスの最後の入力は同じであっても良い。ある入力シーケンスセットの中の入力シーケンスの最後の入力は、他の入力シーケンスセットと比べて異なっても良い。上述の及び他の実施形態では、方法６００は、入力シーケンスセットの各々について方法６００の動作、ステップ、又は工程を実行するステップを更に有しても良い。
【０１００】
本願明細書に記載した実施形態は、以下に更に詳細に議論するように、種々のコンピュータハードウェア又はソフトウェアモジュールを備えた特定用途又は汎用コンピュータの使用を含み得る。
【０１０１】
本願明細書に記載した実施形態は、コンピュータにより実行可能な命令又はデータ構造を伝える又は格納しているコンピュータ可読媒体を用いて実施され得る。このようなコンピュータ可読媒体は、汎用又は特定目的コンピュータによりアクセスできる利用可能な媒体であり得る。例として且つ限定ではなく、このようなコンピュータ可読媒体は、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read−Only  Memory）、ＥＥＰＲＯＭ（Electrically  Erasable  Programmable  Read−Only  Memory）、ＣＤ−ＲＯＭ（Compact  Disc  Read−Only  Memory）又は他の光ディスク記憶装置、磁気ディスク記憶装置又は他の磁気記憶装置、フラッシュメモリ装置（例えば、固体メモリ素子）を含む非一時的コンピュータ可読記憶媒体、又はコンピュータにより実行可能な命令若しくはデータ構造の形式で所望のプログラムコード手段を伝える若しくは格納するために用いられ汎用若しくは特定目的コンピュータによりアクセス可能な他の媒体を有し得る。上述の組合せも、コンピュータ可読媒体の範囲に包含され得る。
【０１０２】
コンピュータにより実行可能な命令は、例えば、汎用コンピュータ、特定目的コンピュータ（例えば、１又は複数のプロセッサ）又は特定目的処理装置に特定の機能又は機能グループを実行させる命令及びデータを有する。本発明の主題は構造的特徴及び／又は方法論的動作に特有の言葉で記載されたが、本発明の主題は、特許請求の範囲に定められる上述の特定の特徴又は動作に限定されないことが理解されるべきである。むしろ、上述の特定の特徴及び動作は、特許請求の範囲の実施の例示的形態として開示されたものである。
【０１０３】
本願明細書で用いられるように、用語「モジュール」又は「コンポーネント」は、モジュール若しくはコンポーネントの動作を実行するよう構成される特定ハードウェア実装、及び／又はコンピューティングシステムの汎用ハードウェア（例えばコンピュータ可読媒体、処理装置、等）に格納され及び／又はそれらにより実行され得るソフトウェアオブジェクト若しくはソフトウェアルーチンを表しても良い。幾つかの実施形態では、本願明細書に記載されたのと異なるコンポーネント、モジュール、エンジン及びサービスは、（例えば、別個のスレッドとして）コンピューティングシステムで実行されるオブジェクト又は処理として実施されても良い。
【０１０４】
本願明細書に記載のシステム及び方法の幾つかは概して（汎用ハードウェアに格納される及び／又はそれにより実行される）ソフトウェアで実装されるように記載されたが、専用ハードウェアの実装又はソフトウェアと専用ハードウェアの組み合わせの実装も可能であり考えられる。この説明では、「コンピュータエンティティ」は、本願明細書で先に定められたようにコンピューティングシステム、又はコンピューティングシステムで実行されるモジュール若しくはモジュールの組合せであっても良い。
【０１０５】
本開示で及び特に添付の特許請求の範囲（例えば、添付の特許請求の範囲の本体）で使用される用語は、概して、広義の（open）用語と考えられる（例えば、用語「含む（including）」は「含むが、限定されない」と解釈されるべきであり、用語「有する（having）」は「少なくとも有する」と解釈されるべきであり、用語「含む（includes）」は「含むが、限定されない」と解釈されるべきである）。
【０１０６】
さらに、特定数の導入された請求項の引用が意図される場合、このような意図は、請求項の中に明示的に示され、このような引用が存在しない場合はこのような意図が存在しない。例えば、理解の助けとして、以下の添付の特許請求の範囲は、請求項の引用を導入するために、「少なくとも１つの」及び「１又は複数の」をいう前置語句の使用を含み得る。しかしながら、このような語句の使用は、同じ請求項が前置語句「１又は複数」又は「少なくとも１つの」及び「ａ又はａｎ」のような不定冠詞を含むときでも、不定冠詞「ａ、ａｎ」による請求項引用の導入がこのような導入された請求項引用を含む任意の特定の請求項をこのような引用を１つだけ含む実施形態に限定することを示すと考えられてはならない（例えば、「ａ」及び／又は「ａｎ」は「少なくとも１つの」又は「１又は複数の」を意味すると解釈されるべきである）。同様のことは、請求項引用を導入するために使用される定冠詞の使用についても該当する。
【０１０７】
さらに、特定数の導入された請求項引用が明示的に引用される場合、当業者は、このような引用が少なくとも引用された番号を意味することと解釈されるべきであることを認識するだろう（例えば、「２つの引用」はそのままで、他の変更が無ければ、少なくとも２つの引用、又は２以上の引用を意味する）。さらに、「Ａ、Ｂ、Ｃ、等のうちの少なくとも１つ」又は「Ａ、Ｂ、Ｃ、等のうちの１又は複数」に類似する慣例が用いられる例では、通常、このような構成は、Ａのみ、Ｂのみ、Ｃのみ、Ａ及びＢを一緒に、Ａ及びＣを一緒に、Ｂ及びＣを一緒に、又はＡ、Ｂ、Ｃを一緒に、等を含むと意図される。例えば、用語「及び／又は」の仕様は、このように考えられることを意図している。
【０１０８】
さらに、２以上の代替用語を表す任意の離接語又は語句は、説明、請求項、又は図面の中であるかに係わらず、用語のうちの１つ、用語のうちのいずれか、又は両方の用語を含む可能性を包含すると理解されるべきである。例えば、語句「Ａ又はＢ」は、「Ａ」又は「Ｂ」又は「Ａ及びＢ」の可能性を含むと理解されるべきである。
【０１０９】
本願明細書に記載された全ての例及び条件文は、教育上の目的で、読者が本発明の原理及び発明者により考案された概念を理解するのを助け、技術を促進させるためであり、これらの特に記載された例及び条件に限定されないものと考えられるべきである。本開示の実施形態が詳細に記載されたが、種々の変更、置換及び修正が本開示の精神及び範囲から逸脱することなく行われうることが理解されるべきである。
【０１１０】
以上の実施形態に加えて、更に以下の付記を開示する。
（付記１）  未知のバイナリプログラムに対する有効な入力シーケンスを決定する方法であって、前記方法は、
未知のバイナリプログラムに対する複数の入力シーケンスを得るステップであって、前記入力シーケンスの各々は、２以上の異なる入力を有し、前記入力シーケンスの入力は、前記未知のバイナリプログラムに対して有効な入力として決定される、ステップと、
各々の入力シーケンスについて別個に前記未知のバイナリプログラムの計装バージョンを実行するステップであって、前記未知のバイナリプログラムの前記計装バージョンの各々の実行は、前記未知のバイナリプログラムの前記計装バージョンへの入力として前記入力シーケンスのうちの１つを用いる、ステップと、
前記未知のバイナリプログラムの前記計装バージョンの各々の実行について、前記未知のバイナリプログラムの前記計装バージョンの前記実行により生成される実行トレースを記録することにより、実行トレースセットを生成するステップと、
前記実行トレースセットを比較するステップと、
前記実行トレースセットの比較に基づき、前記入力シーケンスのうちのどれを前記未知のバイナリプログラムが有効として受け入れるかを決定するステップと、
を有する方法。
（付記２）  前記入力は、前記未知のバイナリプログラムに対して有効であると決定されたコマンドと、前記コマンドに関連する引数と、を有し、前記引数も、前記未知のバイナリプログラムに対して有効であると決定される、付記１に記載の方法。
（付記３）  前記実行トレースセットを生成するステップは、前記実行トレースセットに含めるために、前記未知のバイナリプログラムの前記計装バージョンの各々の実行について、前記実行トレースの一部を選択するステップであって、前記実行トレースセットのために選択された前記実行トレースの一部は、前記入力シーケンスの最後の入力が前記未知のバイナリプログラムに提供された後に生成された実行トレースである、ステップを含む、付記１に記載の方法。
（付記４）  前記実行トレースセットに含めるために前記実行トレースの一部を選択するステップは、
入力を有しないで前記未知のバイナリプログラムの前記計装バージョンを実行するステップと、
入力を有しない前記実行の終わりに、前記未知のバイナリプログラムの前記計装バージョンの実行により生成された複数の実行トレースを決定するステップと、
前記決定した複数の実行トレースをパーティション実行トレースとして設定するステップと、
前記パーティション実行トレースの最後から２番目の発生と最後の発生との間に生じる実行トレースの一部に基づき、前記入力シーケンスを用いて前記未知のバイナリプログラムの前記計装バージョンの実行中に生成された実行トレースの一部を選択するステップと、
を有する、付記３に記載の方法。
（付記５）  前記実行トレースセットの各々について制御フローグラフを生成するステップ、を更に有し、
前記実行トレースセットを比較するステップは、
前記制御フローグラフの各々についてストリング表現を生成するステップと、
前記ストリング表現を比較するステップと、
を有する、付記１に記載の方法。
（付記６）  各々の制御フローグラフについて前記ストリング表現を生成するステップは、縦型探索アルゴリズム又は横型探索アルゴリズムを実施するステップを有する、付記５に記載の方法。
（付記７）  前記実行トレースセットのうちの１つのセットの中の実行トレースは、前記未知のバイナリプログラムの前記計装バージョンにより出力され且つ前記未知のバイナリプログラムの非計装バージョンにより出力されない、前記未知のバイナリプログラムの中で実行される直線的命令セットに関連するメモリアドレスを表す、付記１に記載の方法。
（付記８）  各々の入力シーケンスの中の最後の入力は同じであり、前記複数の入力シーケンスは入力シーケンスセットであり、前記方法は、複数の他の入力シーケンスセットについて付記１に記載の方法を繰り返すステップ、を更に有し、前記他の入力シーケンスセットのうちの各々のセットの各々の入力シーケンスの最後の入力は、同じであり、各々の入力シーケンスセットの最後の入力は、他の入力シーケンスセットの最後の入力と異なる、付記７に記載の方法。
（付記９）  前記実行トレースセットの比較が、前記実行トレースセットは同じであると示すとき、前記入力シーケンスのいずれも、前記未知のバイナリプログラムにより受け入れられないと決定される、付記１に記載の方法。
（付記１０）  前記実行トレースセットの比較が、前記実行トレースセットのうちの１つが前記実行トレースセットのうちの同じである少なくとも別の２つと異なることを示すとき、前記実行トレースセットのうちの該１つに対応する入力シーケンスは、前記未知のバイナリプログラムにより受け入れられると決定される、付記１に記載の方法。
（付記１１）  命令を含む１又は複数の非一時的コンピュータ可読媒体であって、前記命令は、１又は複数のプロセッサにより実行されると、未知のバイナリプログラムに対する有効な入力シーケンスを決定する工程を実行し、前記工程は、
未知のバイナリプログラムに対する複数の入力シーケンスを得るステップであって、前記入力シーケンスの各々は、２以上の異なる入力を有し、前記入力シーケンスの入力は、前記未知のバイナリプログラムに対して有効な入力として決定される、ステップと、
各々の入力シーケンスについて別個に前記未知のバイナリプログラムの計装バージョンを実行するステップであって、前記未知のバイナリプログラムの前記計装バージョンの各々の実行は、前記未知のバイナリプログラムの前記計装バージョンへの入力として前記入力シーケンスのうちの１つを用いる、ステップと、
前記未知のバイナリプログラムの前記計装バージョンの各々の実行について、前記未知のバイナリプログラムの前記計装バージョンの前記実行により生成される実行トレースを記録することにより、実行トレースセットを生成するステップと、
前記実行トレースセットを比較するステップと、
前記実行トレースセットの比較に基づき、前記入力シーケンスのうちのどれを前記未知のバイナリプログラムが有効として受け入れるかを決定するステップと、
を有する、１又は複数の非一時的コンピュータ可読媒体。
（付記１２）  前記入力は、前記未知のバイナリプログラムにより有効であると決定されたコマンドと、前記コマンドに関連する引数と、を有し、前記引数も前記未知のバイナリプログラムにとって有効であると決定される、付記１１に記載の１又は複数の非一時的コンピュータ可読媒体。
（付記１３）  前記実行トレースセットを生成するステップは、前記実行トレースセットに含めるために、前記未知のバイナリプログラムの前記パーティショニング済みバージョンの各々の実行について、前記実行トレースの一部を選択するステップであって、前記実行トレースセットのために選択された前記実行トレースの一部は、前記入力シーケンスの最後の入力が前記未知のバイナリプログラムに提供された後に生成された実行トレースである、ステップ、を更に有する、付記１１に記載の１又は複数の非一時的コンピュータ可読媒体。
（付記１４）  前記実行トレースセットに含めるために前記実行トレースの一部を選択するステップは、
入力を有しないで前記未知のバイナリプログラムの前記計装バージョンを実行するステップと、
入力を有しない前記実行の終わりに、前記未知のバイナリプログラムの前記計装バージョンの実行により生成された複数の実行トレースを決定するステップと、
前記決定した複数の実行トレースをパーティション実行トレースとして設定するステップと、
前記パーティション実行トレースの最後から２番目の発生と最後の発生との間に生じる実行トレースの一部に基づき、前記入力シーケンスを用いて前記未知のバイナリプログラムの前記計装バージョンの実行中に生成された実行トレースの一部を選択するステップと、
を更に有する、付記１３に記載の１又は複数の非一時的コンピュータ可読媒体。
（付記１５）  前記工程は、前記実行トレースセットの各々について制御フローグラフを生成するステップ、を更に有し、
前記実行トレースセットを比較するステップは、
前記制御フローグラフの各々についてストリング表現を生成するステップと、
前記ストリング表現を比較するステップと、
を有する、付記１１に記載の１又は複数の非一時的コンピュータ可読媒体。
（付記１６）  各々の制御フローグラフについて前記ストリング表現を生成するステップは、縦型探索アルゴリズム又は横型探索アルゴリズムを実施するステップを有する、付記１５に記載の１又は複数の非一時的コンピュータ可読媒体。
（付記１７）  前記実行トレースセットのうちの１つのセットの中の実行トレースは、前記未知のバイナリプログラムの前記計装バージョンにより出力され且つ前記未知のバイナリプログラムの非計装バージョンにより出力されない、前記未知のバイナリプログラムの中で実行される直線的命令セットに関連するメモリアドレスを表す、付記１１に記載の１又は複数の非一時的コンピュータ可読媒体。
（付記１８）  各々の入力シーケンスの中の最後の入力は同じであり、前記複数の入力シーケンスは入力シーケンスセットであり、前記工程は、複数の他の入力シーケンスセットについて付記１１に記載の工程を繰り返すステップ、を更に有し、前記他の入力シーケンスセットのうちの各々のセットの各々の入力シーケンスの最後の入力は、同じであり、各々の入力シーケンスセットの最後の入力は、他の入力シーケンスセットの最後の入力と異なる、付記１７に記載の１又は複数の非一時的コンピュータ可読媒体。
（付記１９）  前記実行トレースセットの比較が、前記実行トレースセットは同じであると示すとき、前記入力シーケンスのいずれも、前記未知のバイナリプログラムにより受け入れられないと決定される、付記１１に記載の１又は複数の非一時的コンピュータ可読媒体。
（付記２０）  前記実行トレースセットの比較が、前記実行トレースセットのうちの１つが前記実行トレースセットのうちの同じである少なくとも別の２つと異なることを示すとき、前記実行トレースセットのうちの該１つに対応する入力シーケンスは、前記未知のバイナリプログラムにより受け入れられると決定される、付記１１に記載の１又は複数の非一時的コンピュータ可読媒体。
【符号の説明】
【０１１１】
１０２  バイナリプログラム
１０４  入力シーケンス
１１０  計装モジュール
１１２  計装バイナリプログラム
１２０  実行モジュール
１２２  実行トレースセット
１３０  パーティションモジュール
１３２  パーティショニング済み実行トレースセット
１４０  フローグラフモジュール
１４２  フローグラフ
１５０  決定モジュール
３００  フローグラフ
３２０  実行トレース
３３０  ストリング表現
４１０  入力モジュール
４１２  入力
４１４  バイナリプログラム
４２０  実行モジュール
４２２  命令カウント
４３０  入力シーケンス
５００  決定システム
５１０  プロセッサ
５１２  メモリ
５１４  データ記憶
５１６  通信ユニット
【図１】
0006728874.tif 000002
【図２】
0006728874.tif 000003
【図３】
0006728874.tif 000004
【図４】
0006728874.tif 000005
【図５】
0006728874.tif 000006
【図６】
0006728874.tif 000007