(57)【要約】【課題】未知のバイナリプログラムのための入力シーケンスを発見する方法が提供される。【解決手段】方法は、未知のバイナリプログラムのための第１入力シーケンスを取得することを含んでよい。方法は、第１入力シーケンスから複数の変異入力シーケンスを生成し、第１入力シーケンス及び／又は変異入力シーケンスを入力として用いて未知のバイナリプログラムを実行することを更に含んでよい。方法は、未知のバイナリプログラムの実行の１つ以上のブランチカウント及び実行トレースを記録し、未知のバイナリプログラムの他の実行トレースとは異なる又は異なったブランチカウントを有している実行トレースを選択することを更に含んでよい。選択された実行トレース内のブランチは、シンボリックパス条件を生成するよう無効にされてよく、シンボリックパス条件は、未知のバイナリプログラムのための第２入力シーケンスを発見するために解かれてよい。【選択図】図４
2018005890.tif 000002
【特許請求の範囲】
【請求項１】
未知のバイナリプログラムのための有効な入力シーケンスを決定する方法であって、
未知のバイナリプログラムのための第１入力シーケンスを取得し、
前記未知のバイナリプログラムの複数の実行を実施し、前記複数の実行の夫々は、前記第１入力シーケンスの複数の異なるミューテーションのうちの異なる１つを入力として使用し、前記複数の実行の夫々は、ブランチカウント及び実行トレースの生成をもたらし、
前記第１入力シーケンスの前記複数の異なるミューテーションのうちの１つのミューテーションを前記未知のバイナリプログラムへの前記入力として使用する実行による第１ブランチカウントが、前記第１入力シーケンスを前記未知のバイナリプログラムへの前記入力として使用する前記未知のバイナリプログラムの実行による第２ブランチカウントと異なる場合に、前記第１入力シーケンスの前記複数の異なるミューテーションのうちの当該１つのミューテーションを選択し、
前記第１入力シーケンスの前記複数の異なるミューテーションのうちの前記選択された１つのミューテーションに対応する第１実行トレース内の第１ブランチ条件を無効にし、
前記無効にされた第１ブランチ条件を有する前記第１実行トレースに対応する第１シンボリックパス条件を生成し、
第２入力シーケンスを取得するよう前記第１シンボリックパス条件を解き、
前記未知のバイナリプログラムの複数の第２実行を実施し、前記複数の第２実行の夫々は、前記第２入力シーケンスの複数の異なるミューテーションのうちの異なる１つを入力として使用し、
前記第２入力シーケンスの前記複数の異なるミューテーションのうちの１つのミューテーションを前記未知のバイナリプログラムへの前記入力として使用する実行による第３ブランチカウントが、前記第２入力シーケンスを前記未知のバイナリプログラムへの前記入力として使用する前記未知のバイナリプログラムの実行による第４ブランチカウントと異なる場合に、前記第２入力シーケンスの前記複数の異なるミューテーションのうちの当該１つのミューテーションを選択する
ことを有する方法。
【請求項２】
前記第２入力シーケンスの前記複数の異なるミューテーションのうちの前記選択された１つに対応する第２実行トレース内の第２ブランチ条件を無効にし、
前記無効にされた第２ブランチ条件を有する第２実行トレースに対応する第２シンボリックパス条件を生成し、
第３入力シーケンスを取得するよう前記第２シンボリックパス条件を解く
ことを更に有する請求項１に記載の方法。
【請求項３】
入力シーケンスは１つ以上の変数を含む、
請求項１に記載の方法。
【請求項４】
ブランチ条件を無効にすることは、条件を変更して、該条件の後の異なるブランチが前記未知のバイナリプログラムの実行中にとられるようにすることを含む、
請求項１に記載の方法。
【請求項５】
前記第１入力シーケンスの前記複数の異なるミューテーションは、前記第１入力シーケンスに対する追加、控除、又は変更を含む、
請求項１に記載の方法。
【請求項６】
前記第１入力シーケンスの前記複数の異なるミューテーションは、前記第１入力シーケンスのブランチカウント及び前記ミューテーションのブランチカウントに基づく、
請求項５に記載の方法。
【請求項７】
前記未知のバイナリプログラムの複数の実行を実施することは、計装された未知のバイナリプログラムの複数の実行を実施することを含み、前記計装された未知のバイナリプログラムは、前記未知のバイナリプログラムの実行による前記ブランチカウント及び前記実行トレースを出力する前記未知のバイナリプログラム内の追加コード命令を含む、
請求項１に記載の方法。
【請求項８】
未知のバイナリプログラムのための有効な入力シーケンスを決定する方法であって、
未知のバイナリプログラムのための第１入力シーケンスを取得し、
前記未知のバイナリプログラムの複数の実行を実施し、前記複数の実行の夫々は、前記第１入力シーケンスの複数の異なるミューテーションのうちの異なる１つを入力として使用し、前記複数の実行の夫々は、ブランチカウント及び実行トレースの生成をもたらし、
前記第１入力シーケンスの前記複数の異なるミューテーションのうちの１つのミューテーションを前記未知のバイナリプログラムへの前記入力として使用する実行による第１ブランチカウントが、前記第１入力シーケンスを前記未知のバイナリプログラムへの前記入力として使用する前記未知のバイナリプログラムの実行による第２ブランチカウントと異なる場合に、前記第１入力シーケンスの前記複数の異なるミューテーションのうちの当該１つのミューテーションを選択し、
前記第１入力シーケンスの前記複数の異なるミューテーションのうちの前記選択された１つのミューテーションに対応する前記実行トレース内のブランチ条件を無効にし、
前記無効にされたブランチ条件を有する前記実行トレースに対応するシンボリックパス条件を生成し、
第２入力シーケンスを取得するよう前記シンボリックパス条件を解く
ことを有する方法。
【請求項９】
ブランチ条件を無効にすることは、条件を変更して、該条件の後の異なるブランチが前記未知のバイナリプログラムの実行中にとられるようにすることを含む、
請求項８に記載の方法。
【請求項１０】
前記第１入力シーケンスの前記複数の異なるミューテーションは、前記第１入力シーケンスに対する追加、控除、又は変更を含む、
請求項８に記載の方法。
【請求項１１】
前記第１入力シーケンスの前記複数の異なるミューテーションは、前記第１入力シーケンスのブランチカウント及び前記ミューテーションのブランチカウントに基づく、
請求項１０に記載の方法。
【請求項１２】
前記未知のバイナリプログラムの複数の実行を実施することは、計装された未知のバイナリプログラムの複数の実行を実施することを含み、前記計装された未知のバイナリプログラムは、前記未知のバイナリプログラムの実行による前記ブランチカウント及び前記実行トレースを出力する前記未知のバイナリプログラム内の追加コード命令を含む、
請求項８に記載の方法。
【請求項１３】
前記シンボリックパス条件は第１シンボリックパス条件であり、当該方法は、
前記未知のバイナリプログラムの複数の第２実行を実施し、前記複数の第２実行の夫々は、前記第２入力シーケンスの複数の異なるミューテーションのうちの異なる１つを入力として使用し、
前記第２入力シーケンスの前記複数の異なるミューテーションのうちの１つのミューテーションを前記未知のバイナリプログラムへの前記入力として使用する実行による第３ブランチカウントが、前記第２入力シーケンスを前記未知のバイナリプログラムへの前記入力として使用する前記未知のバイナリプログラムの実行による第４ブランチカウントと異なる場合に、前記第２入力シーケンスの前記複数の異なるミューテーションのうちの当該１つのミューテーションを選択し、
前記第２入力シーケンスの前記複数の異なるミューテーションのうちの前記選択された１つに対応する第２実行トレース内の第２ブランチ条件を無効にし、
前記無効にされた第２ブランチ条件を有する第２実行トレースに対応する第２シンボリックパス条件を生成し、
第３入力シーケンスを取得するよう前記第２シンボリックパス条件を解く
ことを更に有する、請求項１２に記載の方法。
【請求項１４】
１つ以上のプロセッサによって実行される場合に、該１つ以上のプロセッサに、未知のバイナリプログラムのための有効な入力シーケンスを決定する動作を実行させる命令を含む１つ以上の非一時的なコンピュータ可読媒体であって、
前記動作は、
未知のバイナリプログラムのための第１入力シーケンスを取得し、
前記未知のバイナリプログラムの複数の実行を実施し、前記複数の実行の夫々は、前記第１入力シーケンスの複数の異なるミューテーションのうちの異なる１つを入力として使用し、前記複数の実行の夫々は、ブランチカウント及び実行トレースの生成をもたらし、
前記第１入力シーケンスの前記複数の異なるミューテーションのうちの１つのミューテーションを前記未知のバイナリプログラムへの前記入力として使用する実行による第１ブランチカウントが、前記第１入力シーケンスを前記未知のバイナリプログラムへの前記入力として使用する前記未知のバイナリプログラムの実行による第２ブランチカウントと異なる場合に、前記第１入力シーケンスの前記複数の異なるミューテーションのうちの当該１つのミューテーションを選択し、
前記第１入力シーケンスの前記複数の異なるミューテーションのうちの前記選択された１つのミューテーションに対応する前記実行トレース内のブランチ条件を無効にし、
前記無効にされたブランチ条件を有する前記実行トレースに対応するシンボリックパス条件を生成し、
第２入力シーケンスを取得するよう前記シンボリックパス条件を解く
ことを有する、１つ以上の非一時的なコンピュータ可読媒体。
【請求項１５】
入力シーケンスは１つ以上の変数を含む、
請求項１４に記載の１つ以上の非一時的なコンピュータ可読媒体。
【請求項１６】
ブランチ条件を無効にすることは、条件を変更して、該条件の後の異なるブランチが前記未知のバイナリプログラムの実行中にとられるようにすることを含む、
請求項１４に記載の１つ以上の非一時的なコンピュータ可読媒体。
【請求項１７】
前記第１入力シーケンスの前記複数の異なるミューテーションは、前記第１入力シーケンスに対する追加、控除、又は変更を含む、
請求項１４に記載の１つ以上の非一時的なコンピュータ可読媒体。
【請求項１８】
前記第１入力シーケンスの前記複数の異なるミューテーションは、前記第１入力シーケンスのブランチカウント及び前記ミューテーションのブランチカウントに基づく、
請求項１７に記載の１つ以上の非一時的なコンピュータ可読媒体。
【請求項１９】
前記未知のバイナリプログラムの複数の実行を実施することは、計装された未知のバイナリプログラムの複数の実行を実施することを含み、前記計装された未知のバイナリプログラムは、前記未知のバイナリプログラムの実行による前記ブランチカウント及び前記実行トレースを出力する前記未知のバイナリプログラム内の追加コード命令を含む、
請求項１４に記載の１つ以上の非一時的なコンピュータ可読媒体。
【請求項２０】
前記シンボリックパス条件は第１シンボリックパス条件であり、前記動作は、
前記未知のバイナリプログラムの複数の第２実行を実施し、前記複数の第２実行の夫々は、前記第２入力シーケンスの複数の異なるミューテーションのうちの異なる１つを入力として使用し、
前記第２入力シーケンスの前記複数の異なるミューテーションのうちの１つのミューテーションを前記未知のバイナリプログラムへの前記入力として使用する実行による第３ブランチカウントが、前記第２入力シーケンスを前記未知のバイナリプログラムへの前記入力として使用する前記未知のバイナリプログラムの実行による第４ブランチカウントと異なる場合に、前記第２入力シーケンスの前記複数の異なるミューテーションのうちの当該１つのミューテーションを選択し、
前記第２入力シーケンスの前記複数の異なるミューテーションのうちの前記選択された１つに対応する第２実行トレース内の第２ブランチ条件を無効にし、
前記無効にされた第２ブランチ条件を有する第２実行トレースに対応する第２シンボリックパス条件を生成し、
第３入力シーケンスを取得するよう前記第２シンボリックパス条件を解く
ことを更に有する、請求項１９に記載の１つ以上の非一時的なコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書で説明される実施形態は、未知のプログラムバイナリのための入力発見に関係がある。
【背景技術】
【０００２】
バイナリファイルの効率的な試験は、どの入力がバイナリファイルにとって有効であるかを知っていることによって改善され得る。バイナリファイルは、人間がテキストとして解釈することができるコード及びルーチンを含みうる。しかし、バイナリファイルのコード及びルーチンに含まれるテキストは、人間が読むことができない。バイナリファイルの人間である試験者が、バイナリファイルのコード及びルーチンを見直すことによってバイナリファイルのための有効な入力を決定することは不可能である。これは、コード及びルーチンを人間が読むことができないからである。結果として、人間である試験者は、どの入力がバイナリファイルにとって有効であるかを決定するために、バイナリファイルに関連した仕様書、資料又はソースコードを見直すこととなる。そのような有効な入力は、次いで、バイナリファイルのより効率的な試験を実現するために使用され得る。いくつかの状況において、バイナリファイルに関連した仕様書、資料及びソースコードは、入手不可能でありうる。そのような状況では、プロセスは、バイナリファイルのための入力を発見するために使用され得る。
【発明の概要】
【０００３】
実施形態の態様に従って、未知のバイナリプログラムのための入力シーケンスを発見する方法が開示される。方法は、未知のバイナリプログラムのための第１入力シーケンスを取得し、未知のバイナリプログラムの複数の実行を実施することを含んでよい。複数の実行の夫々は、第１入力シーケンスの複数の異なるミューテーション（mutations）のうちの異なる１つを入力として使用してよく、複数の実行の夫々は、ブランチカウント及び実行トレースの生成をもたらし得る。方法は、第１入力シーケンスの複数の異なるミューテーションのうちの１つのミューテーションを未知のバイナリプログラムへの入力として使用する実行による第１ブランチカウントが、第１入力シーケンスを未知のバイナリプログラムへの入力として使用する未知のバイナリプログラムの実行による第２ブランチカウントと異なる場合に、第１入力シーケンスの複数の異なるミューテーションのうちの当該１つのミューテーションを選択することを更に含んでよい。方法は、第１入力シーケンスの複数の異なるミューテーションのうちの選択された１つのミューテーションに対応する実行トレース内のブランチ条件を無効にすることを更に含んでよい。方法は、無効にされたブランチ条件を有する実行トレースに対応するシンボリックパス条件を生成し、該シンボリックパス条件を解いて第２入力シーケンスを取得することを更に含んでよい。
【０００４】
実施形態の目的及び利点は、少なくとも、特許請求の範囲で特に指し示されている要素、特徴、及び組み合わせによって、実現及び達成されるだろう。
【０００５】
前述の概要及び以下の詳細な説明はいずれも、例証及び説明であり、請求されている本開示の限定でないことが理解されるべきである。
【図面の簡単な説明】
【０００６】
例となる実施形態は、添付の図面の使用を通じて、更なる特定及び詳細をもって記載及び説明されるだろう。
【０００７】
【図１】例となる入力シーケンス決定プロセスを表す。
【０００８】
【図２】例となる入力決定システムのブロック図である。
【０００９】
【図３Ａ】未知のバイナリプログラムのための入力シーケンスを発見する方法の例のフローチャートである。
【００１０】
【図３Ｂ】未知のバイナリプログラムのための入力シーケンスを発見する方法の例のフローチャートである。
【００１１】
【図４】未知のバイナリプログラムのための入力シーケンスを発見する方法の他の例のフローチャートである。
【発明を実施するための形態】
【００１２】
未知のバイナリプログラムのための入力シーケンスを発見するための満足な方法は、様々な要素を含んでよい。１つの要素は、未知のバイナリプログラムに含まれているコード及びルーチンの高い割合をカバーすることを含んでよい（デッドコードを除く。）。例えば、未知のバイナリプログラムを試験するために選択される１つ以上の試験入力又は入力シーケンスは、未知のバイナリプログラムのコード及びルーチンの１００パーセント又はほぼ１００パーセントをカバーし得る（例えば、デッドコード及びルーチンを除く、バイナリプログラムの９０から１００パーセント）。いくつかの現在の方法は、未知のバイナリプログラムを試験するためのランダムな試験入力の生成に依存する。あいにく、未知のバイナリプログラムを試験するためのランダムな試験入力の生成を含む試験方法は、未知のバイナリプログラムのコード及びルーチンの高い割合を一貫してカバーすることができない可能性がある。これは、ランダムに生成された試験入力が、未知のバイナリプログラムのコード及びルーチンの高い割合を一貫してカバーするという目標と本質的に相容れないことがあるためである。結果として、いくつかの既存の方法は、バイナリプログラムのコード及びルーチンの高い割合を一貫してカバーすることができないので、それらの方法は受け入れられないと見なされる。
【００１３】
未知のバイナリプログラムのための入力シーケンスを発見する満足な方法の他の要素は、未知のバイナリプログラムに関連した仕様、資料、又はソースコードなしで有効に実施される能力を含んでよい。この要件は、ソフトウェア内の脆弱性を自動的に特定することがコンピュータシステムにとって有益である自律ソフトウェアセキュリティの分野において有益であり得る。いくつかの状況において、未知のバイナリプログラムは、未知のバイナリプログラムの人間である試験者に利用可能であり得るが、未知のバイナリプログラムに関連した仕様、資料及びソースコードは入手不可能であることがある。いくつかの既存の方法は、未知のバイナリプログラムのための入力を発見しようと試みる。しかし、それらの方法は、ランダムに生成された試験入力に依存するか、あるいは、他の欠点を有している。
【００１４】
未知のバイナリプログラムのための入力シーケンスを発見する満足な方法の更なる他の要素は、プラットフォーム非依存性を含んでよい。プラットフォーム非依存性は、メソッドロジの移植性を有益に改善するとともに、他の利点を提供し得る。
【００１５】
現在、それらは、上記の要素を含む、未知のバイナリプログラムのための入力シーケンスを発見する方法であるように思われない。様々な方法が、未知のバイナリプログラムのための入力シーケンスを発見するために使用されてきた。しかし、それらの方法のいずれもが、未知のバイナリプログラムのための入力シーケンスを発見する満足な方法の上記の要素の全て又は一部でさえも提供しない。
【００１６】
１つのそのような方法は、“シンボリック実行（symbolic  execution）”と呼ばれ得る。シンボリック実行アプローチは、様々な実行パスに沿ってプログラムを駆動し得る未知のバイナリプログラムのための入力を決定することを含む。このアプローチは、いくつかの場合において成功を収めることができる。しかし、孤立して使用されるシンボリック実行アプローチに関連した１つの欠点は、未知のバイナリプログラムに関連したソースファイルの使用である。いくつかの場合に、ソースファイルは入手不可能でありうる。結果として、シンボリック実行アプローチの実施は、そのような場合において不可能でありうる。少なくともこの理由により、シンボリック実行アプローチは、それだけでは、未知のバイナリプログラムのための入力を発見する満足な方法でない。
【００１７】
他の方法は、“ブラックボックス・ファジング（black-box  fuzzing）”として知られている。このアプローチは、文字列を選択し、該文字列をランダムに変更することを含んでよい。文字列は、夫々の変更後に入力として未知のバイナリプログラムへ供給され得る。このアプローチは、十分な時間を与えられれば正常に機能することができるが、ブラックボックス・ファジングによって生成される入力のほとんどは無効な入力である。これは、有効な入力が、更なる有効な入力を変異させて識別するために必要とされるので、問題がある。ブラックボックス・ファジングに関連した更なる問題は、このアプローチが未知のバイナリプログラムの高い被覆率を保証しない点である。これは、それがランダムな入力に依存するからである。故に、ブラックボックス・ファジングを実施した結果が高い被覆率を達成するかどうかを知ることは不可能である。結果として、如何なる他のメソッドロジにもよらない“ブラックボックス・ファジング”アプローチの実施は、未知のバイナリプログラムのための入力を発見する満足な方法であり得ない。
【００１８】
他の方法は、“ホワイトボックス・ファジング（white-box  fuzzing）”として知られている。ホワイトボックス・ファジングアプローチは、有効な入力が記号制約を集めるために使用される点を除いて、ブラックボックス・ファジングと同様である。記号制約は、その場合に、試験入力を生成するために解析され得る。ホワイトボックス・ファジングアプローチは、ランダムには到達されない少なくともいくつかの入力を含むので、ブラックボックス・ファジングに対する改善と見なされ得る。しかし、ホワイトボックスアプローチは、それが試験入力を決定するために実施され得るより前に、有効な入力を前提条件として必要とする。いくつかの場合に、有効な入力は、ホワイトボックス・ファジングアプローチのためのシードとして利用可能でない。この理由により、単独で実施されるホワイトボックス・ファジングアプローチは、未知のバイナリプログラムのための入力を発見するという問題を解決することができない可能性がある。
【００１９】
他の方法は、“単体テスト（unit  testing）”として知られている。この単体テストにおいて、プログラムのコードは、ユニットに分けられて、体系的に試験される。単体テストは、いくつかの場合においてバイナリプログラムの高被覆率の試験を達成することができうるが、このアプローチは、未知のバイナリプログラムの仕様といった、未知のバイナリプログラムに関連したソースファイル又は他の資料を常に必要とする。この情報がないと、単体テストは実施され得ない。そのようなものとして、単体テストアプローチは、それがソースファイル又は何らかの他の資料を必要とするので、未知のバイナリプログラムのための入力を発見するという問題を解決することができない。単体テストアプローチに付随する他の欠点は、それがプラットフォームに依存する点である。単体テストアプローチはまた、遅く且つ費用がかかると考えられている。
【００２０】
他の方法は、“仕様に基づくテスト（specification-based  testing）”として知られている。しかし、名前が示すように、仕様に基づくテストのアプローチは、未知のバイナリプログラムに関連したソースファイル又は他の資料を常に必要とする。そのようなものとして、このアプローチは、それがソースファイル又は何らかの他の資料を必要とするので、未知のバイナリプログラムのための入力を発見するという問題を解決することができない。単体テストと同様に、仕様に基づくテストのアプローチもプラットフォームに依存し、遅く且つ費用がかかると考えられている。
【００２１】
他の方法は、“リバース・コード・エンジニアリング（reverse  code  engineering）”を含んでよい。リバース・コード・エンジニアリングアプローチは、“情報交換解析（information  exchange  analysis）”アプローチ、“ディスアセンブル（disassembly）”アプローチ、及び“デコンパイル（decompilation）”アプローチを含んでよい。情報交換解析アプローチは、情報が未知のバイナリプログラムによって交換されない場合には実施され得ず、故に、このアプローチは制限され、この理由により好ましくない。ディスアセンブルアプローチは、生の（raw）アセンブルコードの静的又は動的解析に依存し、これは多数の欠点を有している。例えば、生のアセンブルコードの静的又は動的解析は、計算コストが高く、不正確であり、スケーラビリティに問題があり、相当の性能オーバーヘッドを導入する可能性がある。デコンパイルアプローチは、未知のバイナリプログラムに関連したソースコードを再構成し、ソースコード及び未知のバイナリプログラムを用いてテストを進めようと試みる。しかし、実際には、デコンパイルアプローチは、多くの状況で正常に機能せず、使用できないか又は高品質でないソースコードを提供しうる。これは、実際に、そのソースコードが、デコンパイルアプローチが再構成ようと試みる元のソースコードとは実質的に異なるからである。
【００２２】
本開示で説明されるいくつかの実施形態は、未知のバイナリプログラムのための入力シーケンスを発見するシステム及び／又は方法に関係がある。それら及び他の実施形態において、入力シーケンスは、未知のバイナリプログラムのための２つ以上の変数の列であってよい。未知のバイナリプログラムのための入力シーケンスを発見することによって、未知のバイナリプログラムは、未知のバイナリプログラムの如何なる知識も有さずに試験され得る。
【００２３】
いくつかの実施形態において、未知のバイナリプログラムのための第２入力シーケンスは、第１入力シーケンスの複数のミューテーションを生成することと、第１入力シーケンス及び複数の変異（mutated）入力シーケンスを用いて未知のバイナリプログラムの複数の実行を実施することとに基づき、発見され得る。未知のバイナリプログラムの異なる実行の間、未知のバイナリプログラムの各実行中に遭遇されるブランチの数を示すブランチカウントが記録されてよい。未知のバイナリプログラムの異なる実行によるブランチカウントは、互いと比較されてよい。代替的に、又はその上、未知のバイナリプログラムの異なる実行の間、１つ以上のブランチ命令の実行は、実行トレースにおいて記録されてよい。未知のバイナリプログラムの異なる実行による実行トレースは、互いと比較されてよい。記録されたブランチカウント及び／又は実行トレースのうちの１つ以上が他のブランチカウント及び／又は実行トレースと異なる場合に、異なるブランチカウント又は異なる実行トレースに対応する実行トレースは選択されてよい。選択された実行トレース内のブランチは無視されてよく、シンボリックパス条件は、選択された実行トレース内の無効にされたブランチ及び残りのブランチから生成されてよい。シンボリックパス条件は、第２入力シーケンスを生成するよう解かれてよい。
【００２４】
いくつかの実施形態において、本開示で記載されるシステム及び／又は方法はまた、プラットフォームから独立し得る。結果として、本開示で記載されるシステム及び／又は方法は、移植可能であって、様々な動作環境で使用され得る。いくつかの実施形態において、本開示で記載されるシステム及び／又は方法はまた、未知のバイナリプログラムに関連したソースコード又は資料なしでうまく実施され得る。いくつかの実施形態において、本開示で記載されるシステム及び／又は方法はまた、情報交換に依存するパケット・スニッフィング（packet  sniffing）、バス解析及び／又は何らかの他のメソッドロジによらずに実施され得る。結果として、本開示で記載されるシステム及び／又は方法は、リバース・コード・エンジニアリング技術の使用なしで実施され得る。
【００２５】
図１は、本開示で記載される少なくとも１つの実施形態に従って構成される、例となる入力シーケンス決定プロセス１００を表す。いくつかの実施形態において、プロセス１００は、未知のバイナリプログラム１０２のための入力シーケンス１５４を発見するために、計装モジュール１６０、実行モジュール１１０、ミューテーションモジュール１２０、選択モジュール１３０、無効化モジュール１４０、及びソルバー（solver）モジュール１５０を使用してよい。
【００２６】
一般に、プロセス１００は、未知のバイナリプログラム１０２のための入力シーケンスを繰り返し発見するために使用されてよい。例えば、プロセス１００は、プロセス１００の第１の繰り返しの間、入力シーケンス１５４を発見するために、入力シーケンス１０４及び入力シーケンス１０４のミューテーションを使用してよい。プロセス１００の第２の繰り返しの間、入力シーケンス１５４及び入力シーケンス１５４のミューテーションは、入力シーケンス１５４に取って代わる他の入力シーケンスを発見するために使用されてよい。他の入力シーケンスは、プロセス１００の次の繰り返しのための入力シーケンスとして使用されてよい。このようにして、プロセス１００で説明されている入力シーケンス１５４は、プロセス１００の各繰り返しの間に変化しうる。プロセス１００におけるモジュールの説明は、プロセス１００の例を受けて与えられる。
【００２７】
計装モジュール１６０は、未知のバイナリプログラム１０２を受け取るよう構成されてよい。未知のバイナリプログラム１０２は、１つ以上の関数又はプログラムの他の態様のような、バイナリプログラム全体又はバイナリプログラムの一部分であってよい。それら及び他の実施形態において、未知のバイナリプログラム１０２は、プログラムのコンパイルされたバージョンを含んでよい。プログラムは、プログラムの機能性を記述するコード及びルーチンを含んでよい。プログラムのコード及びルーチンは、プログラムにとって有効でありうる入力と、プログラムのコンパイルされたバージョンである未知のバイナリプログラム１０２とを定義してよい。いくつかの実施形態において、プログラムのための入力は、１つ以上の入力列を含んでよい。コード及びルーチンによって有効と定義されていない入力は、プログラムにとって、ひいては未知のバイナリプログラム１０２にとって、無効な入力であってよい。
【００２８】
未知のバイナリプログラム１０２は、バイナリ形式で符号化されて、プロセッシングデバイスによる実行のために非一時的なコンピュータ可読媒体に記憶されているコード及びルーチンを含んでよい。未知のバイナリプログラム１０２のコード及びルーチンは、テキストとして人間によって解釈され得る部分を含み得るが、未知のバイナリプログラム１０２のコード及びルーチンは、人間が読むことができないものでありうる。それら及び他の実施形態において、コード及びルーチンは、マシン読出可能であってよい。例えば、コード及びルーチンは、バイナリ又は何らかの他のマシン読出可能なフォーマットであってよい。
【００２９】
未知のバイナリプログラム１０２は、未知のバイナリプログラム１０２のための有効な入力シーケンスが知られていない可能性があるので、“未知”でありうる。例えば、未知のバイナリプログラム１０２に関連した仕様、資料、及び／又はソースコードは、未知のバイナリプログラム１０２の人間である試験者又は他の試験設備に利用可能でないことがある。結果として、人間である試験者又は他の試験設備は、未知のバイナリプログラム１０２のための有効な入力シーケンスを決定することができないことがある。
【００３０】
計装モジュール１６０は、未知のバイナリプログラム１０２に基づき、計装された未知のバイナリプログラム１６２を生成するよう構成されてよい。それら及び他の実施形態において、計装された未知のバイナリプログラム１６２を生成するよう、計装モジュール１６０は、未知のバイナリプログラム１０２を計装してよい。未知のバイナリプログラム１０２を計装するよう、計装モジュール１６０は、未知のバイナリプログラム１０２において追加コード命令を入力してよい。未知のバイナリプログラム１０２は、計装された未知のバイナリプログラムであってよい。追加コード命令は、未知のバイナリプログラム１０２の実行又はランタイムに関する情報を出力し得る。例えば、追加コード命令は、未知のバイナリプログラム１０２の実行中に遭遇されたブランチの数のブランチカウント、未知のバイナリプログラム１０２の実行中に実行されたコード命令の実行トレース、又は未知のバイナリプログラム１０２の実行中にアクセスされたメモリアドレスに関する情報を出力してよい。
【００３１】
いくつかの実施形態において、計装モジュール１６０は、ＰＩＮ又は何らかの他のバイナリ計装プログラムのような、バイナリ計装プログラムを含んでよい。計装モジュール１６０は、計装された未知のバイナリプログラム１６２を実行モジュール１１０へ供給してよい。
【００３２】
実行モジュール１１０は、計装された未知のバイナリプログラム１６２並びに入力シーケンス１０４、複数の変異入力シーケンス１２４、及び／又は入力シーケンス１５４を受け取るよう構成されてよい。
【００３３】
いくつかの実施形態において、入力シーケンス１０４は、計装された未知のバイナリプログラム１６２のための１つの入力を含んでよい。代替的に、又はその上、入力シーケンス１０４は、計装された未知のバイナリプログラム１６２のための２つ以上の異なる入力を含んでよい。それら及び他の実施形態において、入力シーケンス１０４の異なる入力は、いくつの方法においてもフォーマットされ得る入力のタイプの中でも特に、変数、数字、文字列（例えば、コマンド及びレスポンス）であってよい。それら及び他の実施形態において、入力は、未知のバイナリプログラムにとって有効と決定されるコマンド及びそのコマンドに関連した引数を含んでよい。
【００３４】
いくつかの実施形態において、計装された未知のバイナリプログラム１６２のための入力は、計装された未知のバイナリプログラム１６２のための有効な入力であるとこれまで発見も決定もされたことがなくてよい。代替的に、又はその上、計装された未知のバイナリプログラム１６２のための入力シーケンス１０４の入力は、計装された未知のバイナリプログラム１６２のための有効な入力であるとこれまで発見及び決定されたことがあってよい。
【００３５】
実行モジュール１１０は、計装された未知のバイナリプログラム１６２を実行するよう構成されてよい。いくつかの実施形態において、実行モジュール１１０は、計装された未知のバイナリプログラム１６２を複数回実行してよい。例えば、実行モジュール１１０は、入力シーケンス１０４及び複数の変異入力シーケンス１２４の夫々について別々に、計装された未知のバイナリプログラム１６２を実行するよう構成されてよい。代替的に、又はその上、実行モジュール１１０は、入力シーケンス１５４について別個に、計装された未知のバイナリプログラム１６２を実行するよう構成されてよい。
【００３６】
それら及び他の実施形態において、未知のバイナリプログラム１６２の各実行は、計装された未知のバイナリプログラム１６２のための入力として入力シーケンス１０４、入力シーケンス１５４、及び複数の変異入力シーケンス１２４のうちの１つを使用して実施されてよい。例えば、１つの入力シーケンス１０４及び３つの変異入力シーケンス１２４がある場合には、実行モジュール１１０は、計装された未知のバイナリプログラム１６２を４回、すなわち、入力シーケンス１０４について１回、そして、３つの変異入力シーケンス１２４の夫々について１回ずつ、実行してよい。
【００３７】
実行モジュール１１０は、計装された未知のバイナリプログラム１６２の各実行についてブランチカウント１１６及び実行トレース１１８を生成し出力するよう構成されてよい。いくつかの実施形態において、実行トレース１１８は、計装された未知のバイナリプログラム１６２の実行中に実行された未知のバイナリプログラム１０２の命令ごとのリストであってよい。代替的に、又はその上、実行トレース１１８は、計装された未知のバイナリプログラム１６２の実行中に実行された未知のバイナリプログラム１０２のブランチ命令ごとのリストであってよい。代替的に、又はその上、実行トレース１１８は、計装された未知のバイナリプログラム１６２の実行中に実行された未知のバイナリプログラム１０２の条件付きブランチ命令ごとのリストであってよい。
【００３８】
いくつかの実施形態において、命令は、プロセッサの単一の動作であってよい。例えば、命令は、実行モジュール１１０に、２つの変数を追加させ、２つの変数を取り去らせ、変数をコピーさせ、あるいは、プログラム内の他の位置へ分岐させ得る。命令はまた、実行モジュール１１０に他の動作を実施させ得る。未知のバイナリプログラム１０２内のブランチ命令は、その実行により、実行モジュール１１０が順番に次の命令ではなく別の命令シーケンスを実行することを生じさせ得る命令であってよい。ブランチ命令は無条件であってよく、それは、命令が実行される時点で如何なる条件も無視して分岐することを生じさせ得る。ブランチ命令はまた、条件付きであってよく、それは、ロジック条件の結果に応じてブランチ命令の実行後に複数の異なる命令のうちの１つが実行されることを生じさせ得る。例えば、条件付きブランチ命令の実行は、変数がある量以上である場合に、ブランチ命令の実行に続いて、第１の命令又は第１の命令シーケンスが実行されることを生じさせ得る。ブランチ命令の実行は、変数がその量に満たない場合に、ブランチ命令の実行に続いて、第２の命令又は第２の命令シーケンスが実行されることを生じさせ得る。ブランチ命令は、未知のバイナリプログラム１０２内のどの命令又は命令シーケンスがブランチ命令の実行後に実行されるかを決定するロジック条件を有してよい。
【００３９】
ブランチカウント１１６は、計装された未知のバイナリプログラム１６２の実行中に実行されたブランチ命令の数のカウントであってよい。ブランチカウント１１６は、計装された未知のバイナリプログラム１６２の実行によって生成された実行トレース１１８内のブランチ命令の数を数えることによって、決定され得る。代替的に、又はその上、計装された未知のバイナリプログラム１６２の実行は、ブランチカウント１１６の生成及び出力を生じさせ得る。
【００４０】
計装された未知のバイナリプログラム１６２の各実行の間に、入力シーケンス１０４、入力シーケンス１５４、及び複数の変異入力シーケンス１２４のうちの１つを用いて、実行モジュール１１０は、ブランチカウント１１６及び実行トレース１１８を記録するよう構成されてよい。実行モジュール１１０は、ブランチカウント１１６及び実行トレース１１８の複数の組をこのようにして生成してよい。ブランチカウント１１６及び実行トレース１１８の各組は、入力シーケンス１０４、入力シーケンス１５４、及び複数の変異入力シーケンス１２４のうちの１つに対応する。記録されたブランチカウント１１６及び実行トレース１１８の組のうちの夫々の組は、互いと、且つ、実行される場合に、記録されたブランチカウント１１６及び実行トレース１１８のその組を生じさせる入力シーケンス１０４、入力シーケンス１５４、又は複数の変異入力シーケンス１２４のうちの１つと対応し、関連付けられてよい。記録されたブランチカウント１１６及び実行トレース１１８の組は、選択モジュール１３０へ供給されてよく、ブランチカウント１１６は、ミューテーションモジュール１２０へ供給されてよい。
【００４１】
ミューテーションモジュール１２０は、入力シーケンス１０４及びブランチカウント１１６を受け取って、複数の変異入力シーケンス１２４を生成するよう構成されてよい。ミューテーションモジュール１２０は、入力シーケンス１０４に対して追加、控除又は変更を行うことによって、複数の変異入力シーケンス１２４を生成してよい。例えば、入力シーケンス１０４が“ＨＩＫＥ”である場合に、ミューテーションモジュール１２０は、変異入力シーケンス１２４、“ＨＩＫＥＲ”を生成するよう、入力シーケンス１０４に追加してよい。代替的に、ミューテーションモジュール１２０は、変異入力シーケンス１２４として“ＨＩ”を生成するよう、入力シーケンス１０４から取り去ってよい。ミューテーションモジュール１２０は、変異入力シーケンス１２４として“ＢＩＫＥ”を生成するよう、入力シーケンス１０４を変更してよい。ミューテーションモジュール１２０はまた、入力シーケンス１０４を変更し且つ入力シーケンス１０４に追加することによって、変異入力シーケンス１２４として“ＢＩＫＥＲ”を生成するよう、連続的なミューテーションを入力シーケンス１０４に対して行ってよい。その上、ミューテーションモジュール１２０は、入力シーケンス１０４の一部分のみを変異させてよい。例えば、入力シーケンス１０４が“ＧＥＴ  ａａａａ”である場合に、ミューテーションモジュール１２０は、変異入力シーケンス１２４として“ＧＥＴ＜ｋｅｙ＞”を生成するよう、入力シーケンス１０４の“ＧＥＴ”部分を変異させずに、“ａａａａ”部分を変異させてよい。
【００４２】
ミューテーションモジュール１２０はまた、ソルバーモジュール１５０からの第２入力シーケンス１５４及び実行モジュール１１０からのブランチカウント１１６を受け取って、複数の変異入力シーケンス１２４を生成するよう構成されてよい。ミューテーションモジュール１２０は、第２入力シーケンス１５４に対して追加、控除、又は変更を行うことによって、変異入力シーケンス１２４を生成してよい。ミューテーションモジュール１２０は、複数の変異入力シーケンス１２４を生成してよい。
【００４３】
ミューテーションモジュール１２０は、変異入力シーケンス１２４を生成する際に、入力としてブランチカウント１１６を使用してよい。例えば、ミューテーションモジュール１２０は、変異入力シーケンス１２４を入力として使用する計装された未知のバイナリプログラム１６２の実行のブランチカウント１１６が、入力シーケンス１０４、入力シーケンス１５４、及び他の変異入力シーケンス１２４を入力として使用する計装された未知のバイナリプログラム１６２の実行のブランチカウント１１６と異なる場合に、入力シーケンス１０４、入力シーケンス１５４、及び／又は変異入力シーケンス１２４を選択的に変異させてよい。例えば、入力シーケンス１０４“ＨＩＫＥ”のブランチカウント１１６が１であり、変異入力シーケンス１２４“ＢＩＫＥ”のブランチカウント１１６が１であり、変異入力シーケンス１２４“ＨＩＫＥＲ”のブランチカウント１１６が２である場合に、ミューテーションモジュール１２０は、変異入力シーケンス１２４“ＢＩＫＥ”の更なるミューテーションを実施することよりむしろ、変異入力シーケンス１２４“ＨＩＫＥＲ”の更なるミューテーションを実施することを選択してよい。ミューテーションモジュール１２０は、複数の変異入力シーケンス１２４を実行モジュール１１０へ供給してよい。
【００４４】
選択モジュール１３０は、実行モジュール１１０によって生成されるブランチカウント１１６及び実行トレース１１８の組を取得してよい。選択モジュール１３０は、実行モジュール１１０で生成される実行トレース１１８から１つ以上を選択するよう構成されてよい。選択モジュール１３０は、実行トレース１１８及び／又は実行トレースに関連したブランチカウント１１６に基づき、特定の実行トレース１１８を選択してよい。
【００４５】
プロセス１００の最初の繰り返しについて、選択モジュール１３０は、夫々の実行トレース１１８を、入力シーケンス１０４に対応する実行トレース１１８と、及び実行モジュール１１０から取得された夫々の他の実行トレース１１８と比較して、当該実行トレース１１８が、入力シーケンス１０４に対応する実行トレース１１８及び実行モジュール１１０から取得された夫々の他の実行トレース１１８の一部又は全てと異なっているかどうかを判定してよい。選択モジュール１３０は、実行トレース１１８が、入力シーケンス１０４に対応する実行トレース１１８及び実行モジュール１１０から取得された夫々の他の実行トレース１１８の一部又は全てと異なっている場合に、その実行トレース１１８を選択してよい。いくつかの実施形態において、選択モジュール１３０は、既に行われている重複する解析を避けて、速度を上げるのを助けるよう及び／又は解析の被覆率を改善するよう、入力シーケンス１０４に対応する実行トレース１１８及び実行モジュール１１０から取得された夫々の他の実行トレース１１８の全て又は一部と異なる実行トレース１１８を選択してよい。
【００４６】
プロセス１００の続く繰り返しについて、選択モジュール１３０は、夫々の実行トレース１１８を入力シーケンス１０４に対応する実行トレース１１８、入力シーケンス１５４に対応する実行トレース１１８、実行モジュール１１０から取得された夫々の他の実行トレース１１８、及び既に選択されたことがある複数の実行トレース１３８と比較して、当該実行トレース１１８が、既に選択されたことがある実行トレース１１８及び実行トレース１３８の一部又は全てと異なっているかどうかを判定してよい。選択モジュール１３０は、実行トレース１１８が、入力シーケンス１０４に対応する実行トレース１１８、入力シーケンス１５４に対応する実行トレース１１８、実行モジュール１１０から取得された夫々の他の実行トレース１１８、及び既に選択されたことがある複数の実行トレース１３８と異なっている場合に、その実行トレース１１８を選択してよい。いくつかの実施形態において、選択モジュール１３０は、既に行われている重複する解析を避けて、速度を上げるのを助けるよう及び／又は解析の被覆率を改善するよう、入力シーケンス１０４に対応する実行トレース１１８、入力シーケンス１５４に対応する実行トレース１１８、実行モジュール１１０から取得された夫々の他の実行トレース１１８、及び既に選択されたことがある複数の実行トレース１３８の全て又は一部と異なる実行トレース１１８を選択してよい。
【００４７】
いくつかの実施形態において、プロセス１００の最初の繰り返しについて、選択モジュール１３０は、夫々の実行トレース１１８に対応するブランチカウント１１６を、入力シーケンス１０４に及び実行モジュール１１０から取得された夫々の他の実行トレース１１８に対応するブランチカウント１１６の夫々と比較して、当該実行トレース１１８に対応するブランチカウント１１６が、入力シーケンス１０４に及び実行モジュール１１０から取得された夫々の他の実行トレース１１８に対応するブランチカウント１１６の夫々と異なっているかどうかを判定してよい。選択モジュール１３０は、実行トレース１１８に対応するブランチカウント１１６が、入力シーケンス１０４及び実行モジュール１１０から取得された夫々の他の実行トレース１１８の一部及び全てに対応するブランチカウント１１６の夫々と異なっている場合に、その実行トレース１１８を選択してよい。いくつかの実施形態において、既に行われている重複する解析を避けて、速度を上げるのを助けるよう及び／又は解析の被覆率を改善するよう、実行トレース１１８に対応するブランチカウント１１６が、入力シーケンス１０４及び実行モジュール１１０から取得された夫々の他の実行トレース１１８の一部及び全てに対応するブランチカウント１１６の夫々と異なっている場合に、その実行トレース１１８を選択してよい。
【００４８】
いくつかの実施形態において、プロセス１００の続く繰り返しについて、選択モジュール１３０は、夫々の実行トレース１１８に対応するブランチカウント１１６を比較して、当該実行トレース１１８に対応するブランチカウント１１６が、既に選択されたことがある実行トレース１３８、入力シーケンス１０４及び入力シーケンス１５４に対応する実行トレース１１８、並びに実行モジュール１１０から取得された夫々の他の実行トレース１１８の全てに対応するブランチカウント１１６の夫々と異なっているかどうかを判定してよい。選択モジュール１３０は、実行トレース１１８に対応するブランチカウント１１６が、既に選択されたことがある実行トレース１３８の一部又は全てに対応するブランチカウント１１６と、並びに、入力シーケンス１０４、入力シーケンス１５４、及び実行モジュール１１０から取得された夫々の他の実行トレース１１８に対応するブランチカウント１１６と異なっている場合に、その実行トレース１１８を選択してよい。
【００４９】
例えば、多くの変異入力シーケンス１２４は、計装された未知のバイナリプログラム１６２への入力として使用される場合に、計装された未知のバイナリプログラム１６２の実行が瞬時に、場合によっては最初のブランチ命令において、終了することを生じさせ得る。これは、入力が未知のバイナリプログラム１０２によって受け入れられないからである。それら及び他の実施形態において、プロセス１００の最初の繰り返しの間、選択モジュール１３０は、入力シーケンス１０４の実行トレース１１８及び他の変異入力シーケンス１２４に対応する実行トレース１１８の一部又は全てに対応する他のブランチカウント１１６と異なるブランチカウント１１６に対応する実行トレース１１８を選択してよい。それら及び他の実施形態において、プロセス１００の続く繰り返しの間に、選択モジュール１３０は、既に選択されたことがある実行トレース１３８の一部又は全てに対応する他のブランチカウント１１６と、並びに、入力シーケンス１０４、入力シーケンス１５４、及び実行モジュール１１０から取得された夫々の他の実行トレース１１８に対応するブランチカウント１１６と異なるブランチカウント１１６に対応する実行トレース１１８を選択してよい。いくつかの実施形態において、入力シーケンス１０４の実行トレース１１８及び他の変異入力シーケンス１２４に対応する実行トレース１１８の全てに対応するブランチカウント１１６と異なるブランチカウント１１６に対応する実行トレース１１８をプロセス１００の最初の繰り返しの間に選択すること、並びに入力シーケンス１０４の実行トレース１１８及び他の変異入力シーケンス１２４に対応する実行トレース１１８の全てに対応するブランチカウント１１６と異なるブランチカウント１１６に対応する実行トレース１１８をプロセス１００の続く繰り返しの間に選択することは、探索される未知のバイナリプログラム１０２の量の増大を生じさせ得る。探索される未知のバイナリプログラム１０２の量の増大は、選択された実行トレース１３８が、選択されたことがない未知のバイナリプログラム１０２のブランチ命令に対応するために、起こり得る。いくつかの実施形態において、選択モジュール１３０は、実行トレース１１８に対応するブランチカウント１１６、実行トレース１１８に対応する入力シーケンス１０４、入力シーケンス１５４、又は変異入力シーケンス１２４がどれくらい最近に生成されたか、あるいは、何らかの他の優先方式に従って、複数の実行トレース１１８を選択し、それらの実行トレース１１８を優先順位付けしてよい。最も高い優先度を有する実行トレース１１８は、選択された実行トレース１３８として指定されてよい。選択された実行トレース１３８は、無効化モジュール１４０へ供給されてよい。
【００５０】
無効化モジュール１４０は、選択された実行トレース１３８及び未知のバイナリプログラム１０２を取得してよい。無効化モジュール１４０は、選択された実行トレース１３８を変更するよう構成されてよい。無効化モジュール１４０は、実行トレース１１８内のブランチ命令を選択し、該選択されたブランチに対応するブランチ条件を生成し、該ブランチ条件を無効にし、無効にされたブランチ条件を選択された実行トレース１３８に組み込むことによって、選択された実行トレース１３８を変更してよい。
【００５１】
例えば、いくつかの実施形態において、実行トレース１３８は、未知のバイナリプログラム１０２内のブランチ命令に対応するブランチ命令を含んでよい。未知のバイナリプログラム１０２内のブランチ命令は、条件又は制約であってよいロジック条件又は複数のロジック条件を含んでよく、それは、どの命令がブランチ命令の実行の後に実行されるかを決定してよい。選択された実行トレース１３８を用いて、無効化モジュール１４０は、選択された実行トレース１３８内のブランチ命令を選択してよい。無効化モジュール１４０は、選択された実行トレース１３８内の最初のブランチ命令、選択された実行トレース１３８内の最後のブランチ命令、又は選択された実行トレース１３８内のいずれかの他のブランチ命令を選択してよい。いくつかの実施形態において、無効化モジュール１４０は、少なくとも１つのブランチ命令を選択してよい。いくつかの実施形態において、無効化モジュール１４０は、単一のブランチ命令を選択してよい。いくつかの実施形態において、無効化モジュール１４０の１つの繰り返しの間に、無効化モジュール１４０は、選択された実行トレース１３８内の最後のブランチ命令を選択してよい。無効化モジュール１４０の次の繰り返しの間に、無効化モジュール１４０は、選択された実行トレース１３８内の最後から２番目のブランチ命令を選択してよい。無効化モジュール１４０は、選択された実行トレース１３８内のブランチ命令の夫々を以降の繰り返しの間に選択するまで、繰り返してよい。
【００５２】
無効化モジュール１４０は、未知のバイナリプログラム１０２を用いて、選択された実行トレース１３８の選択されたブランチ命令に対応するブランチ条件を生成してよい。ブランチ条件は、未知のバイナリプログラム１０２のブランチ命令内のロジック条件を決定することによって、生成され得る。ロジック条件は、真であるときに、ブランチ命令の実行に、選択された実行トレース１３８と同じ命令をブランチ命令の実行後に実行させ得る。ブランチ条件は、ロジック制約又は条件であってよい。無効化モジュール１４０は、新しいブランチ条件を生成するようブランチ条件を無効にしてよい。新しいブランチ条件は、真であるときに、ブランチ命令の実行に、選択された実行トレース１３８とは異なる命令をブランチ命令の実行後に実行させ得るロジック条件であってよい。例えば、ブランチ条件は、変数をある量と比較して、変数がその量よりも大きいかどうかを判定してよい。変数がその量よりも大きいとき、ブランチ命令から起こる第１の命令が実行されてよい。変数がその量に満たないとき、ブランチ命令から起こる第２の命令が実行されてよい。選択された実行トレース１３８に対応する入力シーケンスを用いて実行モジュール１１０によって実行されるときに、第１の命令が実行された場合には、無効化モジュール１４０は、ブランチ条件を無効にして、新しいブランチ条件を生成してよい。新しいブランチ条件は、その新しいブランチ条件が真であるときに第２の命令が実行されることを生じさせる。実行トレース１３８が１つよりも多いブランチ命令を含む場合には、ブランチ命令はいくつでも選択されてよく、対応するブランチ条件は、新しいパスを生成するよう無効にされてよい。
【００５３】
無効化モジュール１４０はまた、無効にされることが選択されていない選択された実行トレース１３８のブランチ命令のためのブランチ条件を生成するよう構成されてよい。無効にされることが選択されなかった選択された実行トレース１３８の各ブランチ命令について、無効化モジュール１４０は、未知のバイナリプログラム１０２のブランチ命令に関連したロジック条件を決定してよい。無効化モジュール１４０は、真であるロジック条件が、ブランチ命令の実行に、選択された実行トレース１３８に対応するブランチ命令から起こる命令を実行させるかどうかを判定してよい。真であるロジック条件が、ブランチ命令の実行に、選択された実行トレース１３８に対応するブランチ命令から起こる命令を実行させる場合には、無効化モジュール１４０は、ロジック条件をブランチ条件として選択してよい。
【００５４】
いくつかの実施形態において、無効にされるブランチ命令及び無効にされないブランチ命令のためのブランチ条件は、シンボリックパス条件１４２を生成するよう結合されてよい。よって、シンボリックパス条件１４２は、無効にされることが選択されないブランチ命令に対応するブランチ条件及び無効にされるブランチ命令に対応する新しいブランチ条件の夫々の集合であってよい。いくつかの実施形態において、無効化モジュール１４０は、選択されたブランチ命令より前にある、無効にされないブランチ命令に対応するブランチ条件を結合し、選択されたブランチ命令より後にある、無効にされないブランチ命令に対応するブランチ条件を結合しないよう構成されてよい。例えば、選択された実行トレース１３８が４つのブランチ命令を有しており、３番目のブランチ命令が無効にされるよう選択される場合には、無効化モジュール１４０は、最初のブランチのブランチ条件、２番目のブランチのブランチ条件、及び３番目のブランチの新しいブランチ条件を結合してシンボリックパス条件１４２を生成してよく、４番目のブランチのブランチ条件は結合されない。
【００５５】
いくつかの実施形態において、無効化モジュール１４０は、シンボリックパス条件１４２を生成するよう無効にされるブランチ命令に対応する新しいブランチ条件により無効にされないブランチ命令に対応するブランチ条件に基づき、未知のバイナリプログラム１０２を記号的に実行するよう構成されてよい。シンボリックパス条件１４２は、ブランチ条件及び新しいブランチ条件並びに選択された実行トレース１３８に対応する入力シーケンス１０４、入力シーケンス１５４、又は変異入力シーケンス１２４に対して実行される動作の組であってよい。シンボリックパス条件１４２は、どのような入力シーケンスが、選択された実行トレース１３８内の命令に対応しない無効にされたブランチ命令から起こる命令を未知のバイナリプログラム１０２の実行が進めることを生じさせ得るのか、を記号的に示してよい。無効化モジュール１４０は、シンボリックパス条件１４２をソルバーモジュール１５０へ供給してよい。
【００５６】
未知のバイナリプログラム１０２の具体的な実行（concrete  execution）は、特定の入力による未知のバイナリプログラム１０２の実行であってよい。例えば、入力としての入力シーケンス１０４による未知のバイナリプログラム１０２の実行は、未知のバイナリプログラム１０２の具体的な実行であってよい。代替的に、又はその上、入力としての入力シーケンス１５４による未知のバイナリプログラム１０２の実行は、未知のバイナリプログラム１０２の具体的な実行であってよい。代替的に、又はその上、入力としての変異入力シーケンス１２４による未知のバイナリプログラム１０２の実行は、未知のバイナリプログラム１０２の具体的な実行であってよい。未知のバイナリプログラム１０２の夫々の具体的な実行について、その実行は、入力に基づき未知のバイナリプログラム１０２内の夫々の命令を評価してよい。未知のバイナリプログラム１０２のシンボリック実行は、特定の入力よりむしろシンボリック値による未知のバイナリプログラム１０２の実行であってよい。例えば、入力としてのシンボリック値ｘによる未知のバイナリプログラム１０２の実行は、未知のバイナリプログラム１０２の具体的な実行であってよい。未知のバイナリプログラム１０２のシンボリック実行の間、その実行は、シンボリック値ｘに基づき未知のバイナリプログラム１０２内の夫々の命令を評価し、その実行中にシンボリック表現を保持してよい。
【００５７】
無効化モジュール１４０の動作の例が続く。この例では、選択された実行トレース１３８は３つのブランチ命令を有してよい。無効化モジュール１４０は第３のブランチ命令を選択してよい。選択された実行トレース１３８内の第３のブランチ命令に対応する未知のバイナリプログラム１０２内のブランチ条件は、“入力が４つ以上の母音を有している”であってよい。無効化モジュール１４０は、そのブランチ条件を無効にして、新しいブランチ条件“入力が４つよりも少ない母音を有している”を生成してよい。無効化モジュール１４０は、選択されていない第１及び第２のブランチ命令に対応するブランチ条件を生成してよい。第１のブランチ命令に対応するブランチ条件は、“入力が文字‘Ｔ’から始まる”であってよい。第２のブランチ命令に対応するブランチ条件は、“入力が‘Ｒ’を２番目の文字として有している”であってよい。無効化モジュール１４０は、選択された実行トレース１３８の第１及び第２のブランチ命令に対応するブランチ条件を新しいブランチ条件と結合して、シンボリックパス条件１４２“入力が文字‘Ｔ’から始まり、且つ、入力が‘Ｒ’を２番目の文字として有しており、且つ、入力が４つよりも少ない母音を有している”を生成してよい。シンボリックパス条件１４２は、ソルバーモジュール１５０へ供給されてよい。
【００５８】
ソルバーモジュール１５０は、シンボリックパス条件１４２を解いて入力シーケンス１５４を生成するよう構成されてよい。入力として入力シーケンス１５４を使用する未知のバイナリプログラム１０２の実行は、選択されたブランチの後に別の命令を有する選択された実行トレース１３８に対応する実行トレース１１８を生じさせ得る。いくつかの実施形態において、ソルバーモジュール１５０は、新しい入力シーケンス１５４を生成するために、定理証明を用いてシンボリックパス条件１４２を解いてよい。定理証明は、プロセッサ及びコンピュータ命令を用いて数学の定理を証明する方法であってよい。代替的に、又はその上、記号制約を解く如何なる既知の方法も、新しい入力シーケンス１５４を生成するようシンボリックパス条件１４２を解くために用いられてよい。ソルバーモジュール１５０は、新しい入力シーケンス１５４を実行モジュール１１０及び／又はミューテーションモジュール１２０へ供給してよい。
【００５９】
ソルバーモジュール１５０の動作の例が続く。この例では、シンボリックパス条件１４２は、“入力が文字‘Ｔ’から始まり、且つ、入力が‘Ｒ’を２番目の文字として有しており、且つ、入力が４つよりも少ない母音を有している”であってよい。ソルバーモジュール１５０は、シンボリックパス条件１４２を解いて第２入力シーケンス１５４“ＴＲＥＥ”を生成してよい。第２入力シーケンス１５４“ＴＲＥＥ”は、シンボリックパス条件１４２における条件の夫々を満足する。すなわち、最初の文字は“Ｔ”であり、２番目の文字は“Ｒ”であり、２つの母音（４つに満たない。）が存在する。
【００６０】
プロセス１００の最初の繰り返しの後、ソルバーモジュール１５０は、新しい入力シーケンス１５４を実行モジュール１１０及びミューテーションモジュール１２０へ供給してよい。プロセス１００は、２回、３回、又はその後何回でも繰り返してよい。プロセス１００の夫々の繰り返しの間、ミューテーションモジュール１２０は、入力シーケンス１５４から複数の変異入力シーケンス１２４を生成してよい。実行モジュール１１０は、入力シーケンス１５４及び変異入力シーケンス１２４の複数回の実行を実施してよい。プロセス１００の夫々の繰り返しの間、選択モジュール１３０は、プロセス１００の如何なる前の繰り返しの間に選択された選択された実行トレース１３８とも実行トレース１１８が異なる場合に、実行トレース１１８を選択してよい。無効化モジュール１４０は、シンボリックパス条件１４２を生成してよい。ソルバーモジュール１５０は、入力シーケンス１５４を生成するようシンボリックパス条件１４２を解いてよい。プロセス１００の繰り返しは再び開始してよい。
【００６１】
プロセス１００は、実行すべき且つ試験すべきいっそう多くの未知のバイナリプログラム１０２を見つけるよう実施されてよい。プロセス１００は、未知のバイナリプログラム１０２の更なるブランチを発見するよう２回、３回、又はその後何回でも繰り返してよい。いくつかの実施形態において、プロセス１００は、プロセス１００の最初の繰り返しの間に発見されなかった更なる入力を２回目の繰り返し、３回目の繰り返し、又はいずれかのその後の繰り返しにおいて発見し得る。プロセス１００の夫々のその後の繰り返しは、実行すべき且つ試験すべきいっそう多くの未知のバイナリプログラム１０２を発見し得る。
【００６２】
プロセス１００の例が続く。入力シーケンス１０４は、単一の入力“ＨＥＬＬＯ”を有してよい。実行モジュール１１０は、入力シーケンス１０４“ＨＥＬＬＯ”を用いて未知のバイナリプログラム１０２を実行してよい。その実行は、１のブランチカウント１１６及び実行トレース１１８を生じさせ得る。
【００６３】
ミューテーションモジュール１２０は、変更、追加、及び控除によって変異入力シーケンス１２４“ＣＥＬＬＯ”、“ＨＥＬＬＯ  ＯＫ”、及び“ＨＥ”を夫々生成するよう入力シーケンス１０４を変異させてよい。実行モジュール１１０はまた、入力シーケンス１０４の３つの異なった変異入力シーケンス１２４の夫々を用いて未知のバイナリプログラム１０２を実行して、３つの異なった変異入力シーケンス１２４についてブランチカウント１１６及び実行トレース１１８を生成してよい。“ＣＥＬＬＯ”の変異入力シーケンス１２４について、ブランチカウント１１６は“１”であってよく、“ＨＥ”の変異入力シーケンス１２４について、ブランチカウント１１６は１であってよく、“ＨＥＬＬＯ  ＯＫ”の変異入力シーケンス１２４について、ブランチカウント１１６は２であってよい。
【００６４】
選択モジュール１３０は、３つの入力シーケンス１２４の夫々についてのブランチカウント１１６と、入力シーケンス１０４についてのブランチカウント１１６とを比較し、そして、“ＨＥＬＬＯ  ＯＫ”の変異入力シーケンス１２４に対応する実行トレース１１８に対応するブランチカウント１１６が他の変異入力シーケンスのブランチカウント１１６及び入力シーケンス１０４“ＨＥＬＬＯ”のブランチカウント１１６（それらは全て１である。）と異なるので、“ＨＥＬＬＯ  ＯＫ”の変異入力シーケンス１２４に対応する実行トレース１１８を選択してよい。無効化モジュール１４０は、選択された実行トレース１３８内の２番目のブランチ命令を選択し、“ＨＥＬＬＯ  ＯＫ”についての実行トレース１１８内の２番目のブランチ命令に対応するブランチ条件を無効にして、新しいシンボリックパス条件１４２を生成してよい。ソルバーモジュール１５０は、次いで、新しいシンボリックパス条件１４２を解いて、新しい入力シーケンス１５４“ＨＥＬＬＯ＜ｔｏｋｅｎ＞”を生成してよい。
【００６５】
変更、追加、又は削除は、本開示の適用範囲から逸脱することなしに、プロセス１００に対して行われてよい。いくつかの実施形態において、モジュールの１つ以上は、異なる順序で実施されてよい。他の実施形態において、プロセス１００は、複数回実施されてよい。プロセス１００が複数回実施される場合には、連続的な入力シーケンス１５４が実行モジュール１１０及びミューテーションモジュール１２０へ供給されてよい。ミューテーションモジュール１２０は、更なる変異入力シーケンス１２４を生成するよう追加、控除、変更、及び／又は他の変形を通じて、連続的な入力シーケンス１５４の夫々を入力シーケンス１０４と同じように変異させてよい。更なる変異入力シーケンス１２４は、実行モジュール１１０へ供給されてよい。
【００６６】
いくつかの実施形態において、計装モジュール１６０はなくてよく、実行モジュール１１０は、計装された未知のバイナリプログラム１６２の実行の代わりに、未知のバイナリプログラム１０２の実行を実施してよい。いくつかの実施形態において、選択モジュール１３０は、変異入力シーケンス１２４を選択し、変異入力シーケンス１２４と、選択された変異入力シーケンス１２４に対応する実行トレース１１８とを無効化モジュール１４０へ供給してよい。
【００６７】
図２は、本開示で記載される少なくとも１つの実施形態に従って構成され得る、例となる入力決定システム２００のブロック図である。図２で説明されるように、システム２００は、プロセッサ２１０、メモリ２１２、データ記憶部２１４、及び通信ユニット２１６を含んでよい。
【００６８】
一般に、プロセッサ２１０は、様々なコンピュータハードウェア又はソフトウェアモジュールを含む如何なる適切な特別目的又は汎用のコンピュータ、コンピューティングエンティティ、又はプロセッシングデバイスも含んでよく、如何なる適用可能なコンピュータ可読記憶媒体においても記憶されている命令を実行するよう構成されてよい。例えば、プロセッサ２１０は、マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ（ＤＳＰ；Digital  Signal  Processor）、特定用途向け集積回路（ＡＳＩＣ；Application-Specific  Integrated  Circuit）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ；Field-Programmable  Gate  Array）、あるいは、プログラム命令を解釈及び／若しくは実行するよう並びに／又はデータを処理するよう構成されるあらゆる他のデジタル又はアナログ回路を含んでよい。図２では単一のプロセッサとして説明されているが、プロセッサ２１０は、本願で記載されている動作をいくつでも個別的に又は集合的に実施するよう構成されるいくつのネットワーク又は物理位置を介しても分散されるプロセッサをいくつでも含んでよい。いくつかの実施形態において、プロセッサ２１０は、メモリ２１２、データ記憶部２１４、又はメモリ２１２及びデータ記憶部２１４に記憶されているプログラム命令を解釈及び／若しくは実行し並びに／又はデータを処理してよい。いくつかの実施形態において、プロセッサ２１０は、データ記憶部２１４からプログラム命令をフェッチし、プログラム命令をメモリ２１２にロードしてよい。プログラム命令がメモリ２１２にロードされた後、プロセッサ２１０は、図１、３及び４のプロセス１００、方法３００、及び／又は方法４００を夫々実施する命令のような、プログラム命令を実行してよい。
【００６９】
メモリ２１２及びデータ記憶部２１４は、コンピュータ実行可能命令又はデータ構造を搬送する又は記憶しているコンピュータ可読記憶媒体又は１つ以上のコンピュータ可読記憶媒体を含んでよい。そのようなコンピュータ可読記憶媒体は、プロセッサ２１０のような、汎用又は特別目的のコンピュータによってアクセスされ得る如何なる利用可能な媒体であってもよい。例として、制限なしに、そのようなコンピュータ可読記憶媒体は、ランダムアクセスメモリ（ＲＡＭ；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）若しくは他の光ディスクストレージ、磁気ディスクストレージ若しくは他の磁気記憶デバイス、フラッシュメモリデバイス（例えば、ソリッドステート・メモリデバイス）、又はコンピュータ実行可能命令若しくはデータ構造の形で所望のプログラムコードを搬送若しくは記憶するために使用されてよく且つ汎用若しくは特別目的のコンピュータによってアクセスされ得るあらゆる他の記憶媒体を含んでよい。それら及び他の実施形態において、本願で説明される語「非一時的（non-transitory）」は、In  re  Nuijten,  500  F.3d  1346のFederal  Circuit判決（Fed.  Cir.  2007）において特許可能な対象の適用範囲外にあると認められたそのようなタイプの一時的な媒体を除外すると解釈されるべきである。上記の組み合わせも、コンピュータ可読媒体の適用範囲内に含まれてよい。
【００９６】
コンピュータ実行可能命令は、例えば、汎用コンピュータ、特別目的のコンピュータ、又は特別目的のプロセッシングデバイス（例えば、１つ以上のプロセッサ）に特定の機能又は機能群を実施させる命令及びデータを有する。対象は、構造的な特徴及び／又は方法論的な動作に特有の言語で記載されてきたが、添付の特許請求の範囲で定義される対象は、上記の具体的な特徴又は動作に必ずしも制限されないことが理解されるべきである。むしろ、上記の具体的な特徴及び動作は、特許請求の範囲を実施する形態の例として開示される。
【００９７】
本願で使用されるように、語「モジュール」又は「コンポーネント」は、コンピュータシステムの汎用ハードウェア（例えば、コンピュータ可読媒体、プロセッシングデバイス、など）によって記憶及び／又は実行され得るモジュール若しくはコンポーネント及び／又はソフトウェアオブジェクト若しくはソフトウェアルーチンの操作を実施するよう構成される特定のハードウェア実装を指してよい。いくつかの実施形態において、本願で記載される種々のコンポーネント、モジュール、エンジン、及びサービスは、コンピュータシステムで（例えば、別個のスレッドとして）実行するオブジェクト又はプロセスとして実施されてよい。
【００９８】
本願で記載されるシステム及び方法のいくつかは、概して、ソフトウェア（汎用ハードウェアによって記憶及び／又は実行される。）において実施されるものとして記載されるが、特定のハードウェア実装又はソフトウェア及び特定のハードウェア実装の組み合わせも可能であり、考えられる。本明細書において、「コンピューティングエンティティ」は、本願で先に定義されたようなあらゆるコンピュータシステム、又はコンピュータシステムで実行されるあらゆるモジュール若しくはモジュールの組み合わせであってよい。
【００９９】
本開示で、特に添付の特許請求の範囲（例えば、添付の特許請求の範囲の本文）で使用される語は、一般的に、“非限定的な（open）”用語として意図されている（例えば、語「含んでいる（including）」は、“〜を含んでいるが、〜に制限されない”との意に解釈されるべきであり、語「備えている（having）」は、「少なくとも〜を備えている」との意に解釈されるべきであり、語「含む（includes）」は、“〜を含むが、〜に制限されない”との意に解釈されるべきである、など。）。
【０１００】
加えて、導入されたクレーム記載（introduced  claim  recitation）において特定の数が意図される場合、そのような意図は当該クレーム中に明確に記載され、そのような記載がない場合は、そのような意図も存在しない。理解を促すために、例えば、後続の添付された特許請求の範囲では、「少なくとも１つの（at  least  one）」及び「１つ以上の（one  or  more）」といった導入句を使用し、クレーム記載を導入することがある。しかし、このような句を使用するからといって、「a」又は「an」といった不定冠詞によりクレーム記載を導入した場合に、たとえ同一のクレーム内に、「１つ以上の」又は「少なくとも１つの」といった導入句と「a」又は「an」といった不定冠詞との両方が含まれるとしても、当該導入されたクレーム記載を含む特定のクレームが、当該記載事項を１しか含まない例に限定されるということが示唆されると解釈されるべきではない（例えば、「a」及び／又は「an」は、「少なくとも１つの」又は「１つ以上の」を意味すると解釈されるべきである。）。定冠詞を使用してクレーム記載を導入する場合にも同様のことが当てはまる。
【０１０１】
更には、導入されたクレーム記載において特定の数が明示されている場合であっても、そのような記載は、通常、少なくとも記載された数を意味するように解釈されるべきであることは、当業者には理解されるであろう（例えば、他に修飾語のない、単なる「２つの記載事項」という記載がある場合、この記載は、少なくとも２つの記載事項、又は２つ以上の記載事項を意味する。）。更に、「Ａ、Ｂ及びＣなどのうち少なくとも１つ」に類する表記が使用される場合、一般的に、そのような構造は、Ａのみ、Ｂのみ、Ｃのみ、ＡとＢの両方、ＡとＣの両方、ＢとＣの両方、及び／又はＡとＢとＣの全て、などを含むよう意図される。例えば、語「及び／又は（and/or）」の使用は、この方法で解釈されるよう意図される。
【０１０２】
更に、２つ以上の選択可能な用語を表す如何なる離接語及び／又は離接句も、明細書、特許請求の範囲、又は図面のいずれであろうと、それら用語のうちの１つ、それらの用語のうちのいずれか、あるいは、それらの用語の両方を含む可能性を意図すると理解されるべきである。例えば、「Ａ又はＢ」という句は、「Ａ又はＢ」、あるいは、「Ａ及びＢ」の可能性を含むことが理解されるべきである。
【０１０３】
加えて、語「第１（first）」、「第２（second）」、「第３（third）」などの使用は、要素の特定の順序又は数を示すために本願で必ずしも使用されているわけではない。一般に、語「第１」、「第２」、「第３」などは、異なる要素どうしを総称的な識別子として区別するために使用される。語「第１」、「第２」、「第３」などが特定の順序を示すとの明示がない限りは、それらの語が特定の順序を示すと理解されるべきではない。更には、語「第１」、「第２」、「第３」などが要素の特定の数を示すとの明示がない限りは、それらの語が要素の特定の数を示すと理解されるべきではない。例えば、第１のウィジェットは、第１の側面を有するものとして記載されることがあり、第２のウィジェットは、第２の側面を有するものとして記載されることがある。第２のウィジェットに対する語「第２の側面」の使用は、第２のウィジェットのその側面を第１のウィジェットの「第１の側面」特別するためであって、第２のウィジェットが２つの側面を有していることを示すためではない。
【０１０４】
本願で挙げられている全ての例及び条件付き言語は、当該技術の促進に本発明者によって寄与される概念及び本発明を読者が理解するのを助ける教育上の目的を意図され、そのような具体的に挙げられている例及び条件に制限されないと解釈されるべきである。本開示の実施形態が詳細に記載されてきたが、様々な変更、置換、及び代替が、本発明の主旨及び適用範囲から逸脱することなしに行われてよい。
【０１０５】
上記の実施形態に加えて、以下の付記を開示する。
（付記１）
未知のバイナリプログラムのための有効な入力シーケンスを決定する方法であって、
未知のバイナリプログラムのための第１入力シーケンスを取得し、
前記未知のバイナリプログラムの複数の実行を実施し、前記複数の実行の夫々は、前記第１入力シーケンスの複数の異なるミューテーションのうちの異なる１つを入力として使用し、前記複数の実行の夫々は、ブランチカウント及び実行トレースの生成をもたらし、
前記第１入力シーケンスの前記複数の異なるミューテーションのうちの１つのミューテーションを前記未知のバイナリプログラムへの前記入力として使用する実行による第１ブランチカウントが、前記第１入力シーケンスを前記未知のバイナリプログラムへの前記入力として使用する前記未知のバイナリプログラムの実行による第２ブランチカウントと異なる場合に、前記第１入力シーケンスの前記複数の異なるミューテーションのうちの当該１つのミューテーションを選択し、
前記第１入力シーケンスの前記複数の異なるミューテーションのうちの前記選択された１つのミューテーションに対応する第１実行トレース内の第１ブランチ条件を無効にし、
前記無効にされた第１ブランチ条件を有する前記第１実行トレースに対応する第１シンボリックパス条件を生成し、
第２入力シーケンスを取得するよう前記第１シンボリックパス条件を解き、
前記未知のバイナリプログラムの複数の第２実行を実施し、前記複数の第２実行の夫々は、前記第２入力シーケンスの複数の異なるミューテーションのうちの異なる１つを入力として使用し、
前記第２入力シーケンスの前記複数の異なるミューテーションのうちの１つのミューテーションを前記未知のバイナリプログラムへの前記入力として使用する実行による第３ブランチカウントが、前記第２入力シーケンスを前記未知のバイナリプログラムへの前記入力として使用する前記未知のバイナリプログラムの実行による第４ブランチカウントと異なる場合に、前記第２入力シーケンスの前記複数の異なるミューテーションのうちの当該１つのミューテーションを選択する
ことを有する方法。
（付記２）
前記第２入力シーケンスの前記複数の異なるミューテーションのうちの前記選択された１つに対応する第２実行トレース内の第２ブランチ条件を無効にし、
前記無効にされた第２ブランチ条件を有する第２実行トレースに対応する第２シンボリックパス条件を生成し、
第３入力シーケンスを取得するよう前記第２シンボリックパス条件を解く
ことを更に有する付記１に記載の方法。
（付記３）
入力シーケンスは１つ以上の変数を含む、
付記１に記載の方法。
（付記４）
ブランチ条件を無効にすることは、条件を変更して、該条件の後の異なるブランチが前記未知のバイナリプログラムの実行中にとられるようにすることを含む、
付記１に記載の方法。
（付記５）
前記第１入力シーケンスの前記複数の異なるミューテーションは、前記第１入力シーケンスに対する追加、控除、又は変更を含む、
付記１に記載の方法。
（付記６）
前記第１入力シーケンスの前記複数の異なるミューテーションは、前記第１入力シーケンスのブランチカウント及び前記ミューテーションのブランチカウントに基づく、
付記５に記載の方法。
（付記７）
前記未知のバイナリプログラムの複数の実行を実施することは、計装された未知のバイナリプログラムの複数の実行を実施することを含み、前記計装された未知のバイナリプログラムは、前記未知のバイナリプログラムの実行による前記ブランチカウント及び前記実行トレースを出力する前記未知のバイナリプログラム内の追加コード命令を含む、
付記１に記載の方法。
（付記８）
未知のバイナリプログラムのための有効な入力シーケンスを決定する方法であって、
未知のバイナリプログラムのための第１入力シーケンスを取得し、
前記未知のバイナリプログラムの複数の実行を実施し、前記複数の実行の夫々は、前記第１入力シーケンスの複数の異なるミューテーションのうちの異なる１つを入力として使用し、前記複数の実行の夫々は、ブランチカウント及び実行トレースの生成をもたらし、
前記第１入力シーケンスの前記複数の異なるミューテーションのうちの１つのミューテーションを前記未知のバイナリプログラムへの前記入力として使用する実行による第１ブランチカウントが、前記第１入力シーケンスを前記未知のバイナリプログラムへの前記入力として使用する前記未知のバイナリプログラムの実行による第２ブランチカウントと異なる場合に、前記第１入力シーケンスの前記複数の異なるミューテーションのうちの当該１つのミューテーションを選択し、
前記第１入力シーケンスの前記複数の異なるミューテーションのうちの前記選択された１つのミューテーションに対応する前記実行トレース内のブランチ条件を無効にし、
前記無効にされたブランチ条件を有する前記実行トレースに対応するシンボリックパス条件を生成し、
第２入力シーケンスを取得するよう前記シンボリックパス条件を解く
ことを有する方法。
（付記９）
ブランチ条件を無効にすることは、条件を変更して、該条件の後の異なるブランチが前記未知のバイナリプログラムの実行中にとられるようにすることを含む、
付記８に記載の方法。
（付記１０）
前記第１入力シーケンスの前記複数の異なるミューテーションは、前記第１入力シーケンスに対する追加、控除、又は変更を含む、
付記８に記載の方法。
（付記１１）
前記第１入力シーケンスの前記複数の異なるミューテーションは、前記第１入力シーケンスのブランチカウント及び前記ミューテーションのブランチカウントに基づく、
付記１０に記載の方法。
（付記１２）
前記未知のバイナリプログラムの複数の実行を実施することは、計装された未知のバイナリプログラムの複数の実行を実施することを含み、前記計装された未知のバイナリプログラムは、前記未知のバイナリプログラムの実行による前記ブランチカウント及び前記実行トレースを出力する前記未知のバイナリプログラム内の追加コード命令を含む、
付記８に記載の方法。
（付記１３）
前記シンボリックパス条件は第１シンボリックパス条件であり、当該方法は、
前記未知のバイナリプログラムの複数の第２実行を実施し、前記複数の第２実行の夫々は、前記第２入力シーケンスの複数の異なるミューテーションのうちの異なる１つを入力として使用し、
前記第２入力シーケンスの前記複数の異なるミューテーションのうちの１つのミューテーションを前記未知のバイナリプログラムへの前記入力として使用する実行による第３ブランチカウントが、前記第２入力シーケンスを前記未知のバイナリプログラムへの前記入力として使用する前記未知のバイナリプログラムの実行による第４ブランチカウントと異なる場合に、前記第２入力シーケンスの前記複数の異なるミューテーションのうちの当該１つのミューテーションを選択し、
前記第２入力シーケンスの前記複数の異なるミューテーションのうちの前記選択された１つに対応する第２実行トレース内の第２ブランチ条件を無効にし、
前記無効にされた第２ブランチ条件を有する第２実行トレースに対応する第２シンボリックパス条件を生成し、
第３入力シーケンスを取得するよう前記第２シンボリックパス条件を解く
ことを更に有する、付記１２に記載の方法。
（付記１４）
１つ以上のプロセッサによって実行される場合に、該１つ以上のプロセッサに、未知のバイナリプログラムのための有効な入力シーケンスを決定する動作を実行させる命令を含む１つ以上の非一時的なコンピュータ可読媒体であって、
前記動作は、
未知のバイナリプログラムのための第１入力シーケンスを取得し、
前記未知のバイナリプログラムの複数の実行を実施し、前記複数の実行の夫々は、前記第１入力シーケンスの複数の異なるミューテーションのうちの異なる１つを入力として使用し、前記複数の実行の夫々は、ブランチカウント及び実行トレースの生成をもたらし、
前記第１入力シーケンスの前記複数の異なるミューテーションのうちの１つのミューテーションを前記未知のバイナリプログラムへの前記入力として使用する実行による第１ブランチカウントが、前記第１入力シーケンスを前記未知のバイナリプログラムへの前記入力として使用する前記未知のバイナリプログラムの実行による第２ブランチカウントと異なる場合に、前記第１入力シーケンスの前記複数の異なるミューテーションのうちの当該１つのミューテーションを選択し、
前記第１入力シーケンスの前記複数の異なるミューテーションのうちの前記選択された１つのミューテーションに対応する前記実行トレース内のブランチ条件を無効にし、
前記無効にされたブランチ条件を有する前記実行トレースに対応するシンボリックパス条件を生成し、
第２入力シーケンスを取得するよう前記シンボリックパス条件を解く
ことを有する、１つ以上の非一時的なコンピュータ可読媒体。
（付記１５）
入力シーケンスは１つ以上の変数を含む、
付記１４に記載の１つ以上の非一時的なコンピュータ可読媒体。
（付記１６）
ブランチ条件を無効にすることは、条件を変更して、該条件の後の異なるブランチが前記未知のバイナリプログラムの実行中にとられるようにすることを含む、
付記１４に記載の１つ以上の非一時的なコンピュータ可読媒体。
（付記１７）
前記第１入力シーケンスの前記複数の異なるミューテーションは、前記第１入力シーケンスに対する追加、控除、又は変更を含む、
付記１４に記載の１つ以上の非一時的なコンピュータ可読媒体。
（付記１８）
前記第１入力シーケンスの前記複数の異なるミューテーションは、前記第１入力シーケンスのブランチカウント及び前記ミューテーションのブランチカウントに基づく、
付記１７に記載の１つ以上の非一時的なコンピュータ可読媒体。
（付記１９）
前記未知のバイナリプログラムの複数の実行を実施することは、計装された未知のバイナリプログラムの複数の実行を実施することを含み、前記計装された未知のバイナリプログラムは、前記未知のバイナリプログラムの実行による前記ブランチカウント及び前記実行トレースを出力する前記未知のバイナリプログラム内の追加コード命令を含む、
付記１４に記載の１つ以上の非一時的なコンピュータ可読媒体。
（付記２０）
前記シンボリックパス条件は第１シンボリックパス条件であり、前記動作は、
前記未知のバイナリプログラムの複数の第２実行を実施し、前記複数の第２実行の夫々は、前記第２入力シーケンスの複数の異なるミューテーションのうちの異なる１つを入力として使用し、
前記第２入力シーケンスの前記複数の異なるミューテーションのうちの１つのミューテーションを前記未知のバイナリプログラムへの前記入力として使用する実行による第３ブランチカウントが、前記第２入力シーケンスを前記未知のバイナリプログラムへの前記入力として使用する前記未知のバイナリプログラムの実行による第４ブランチカウントと異なる場合に、前記第２入力シーケンスの前記複数の異なるミューテーションのうちの当該１つのミューテーションを選択し、
前記第２入力シーケンスの前記複数の異なるミューテーションのうちの前記選択された１つに対応する第２実行トレース内の第２ブランチ条件を無効にし、
前記無効にされた第２ブランチ条件を有する第２実行トレースに対応する第２シンボリックパス条件を生成し、
第３入力シーケンスを取得するよう前記第２シンボリックパス条件を解く
ことを更に有する、付記１９に記載の１つ以上の非一時的なコンピュータ可読媒体。
【符号の説明】
【０１０６】
１００          入力シーケンス決定プロセス
１０２          未知のバイナリプログラム
１０４，１５４  入力シーケンス
１１０          実行モジュール
１１６          ブランチカウント
１１８          実行トレース
１２０          ミューテーションモジュール
１２４          変異入力シーケンス
１３０          選択モジュール
１３８          選択された実行トレース
１４０          無効化モジュール
１４２          シンボリックパス条件
１５０          ソルバーモジュール
１６０          計装モジュール
１６２          計装された未知のバイナリプログラム
２００          入力決定システム
２１０          プロセッサ
２１２          メモリ
２１４          データ記憶部
２１６          通信ユニット
【図１】
2018005890.tif 000003
【図２】
2018005890.tif 000004
【図３Ａ】
2018005890.tif 000005
【図３Ｂ】
2018005890.tif 000006
【図４】
2018005890.tif 000007