(57)【特許請求の範囲】
【請求項１】
未知の有効な入力を有するバイナリモジュールのための１つ以上のテスト入力として印刷可能文字の組を選択し、
前記バイナリモジュールのための前記１つ以上のテスト入力として前記印刷可能文字の組を用いて前記バイナリモジュールを実行し、
前記印刷可能文字の組に含まれる印刷可能文字の夫々について、前記印刷可能文字の組を用いて実行されることに応答して前記バイナリモジュールによって実行される命令の数を決定し、
１つ以上の前記印刷可能文字の夫々について実行される前記命令の数に関連する前記１つ以上の印刷可能文字を含むセットデータを生成し、
前記１つ以上の印刷可能文字に関連する前記命令の数と閾範囲との比較に基づき、前記バイナリモジュールのための１つ以上の有効な入力として１つ以上の印刷可能文字を識別するよう、前記セットデータを解析する
ことを有する方法。
【請求項２】
前記セットデータに含まれる前記命令の数について最頻値を決定し、該最頻値を用いて前記閾範囲を決定する
ことを更に有する請求項１に記載の方法。
【請求項３】
前記閾範囲は、上限及び下限を有し、当該方法は、
指定される試験定数と前記最頻値とを合計することによって、前記閾範囲の前記上限を決定し、
前記最頻値を前記指定される試験定数から減じることによって、前記閾範囲の前記下限を決定する
ことを更に有する、請求項２に記載の方法。
【請求項４】
前記解析は、前記バイナリモジュールのための前記１つ以上の有効な入力に含まれる印刷可能文字の１つ以上のタイプを識別し、該印刷可能文字の１つ以上のタイプが前記バイナリモジュールにとって有効なタイプであると決定することを有する、
請求項１に記載の方法。
【請求項５】
前記テスト入力のうちの１つは、前記バイナリモジュールのための当該テスト入力としてコマンド及び引数を含み、
前記解析は、前記コマンド及び前記引数を含む前記テスト入力が前記バイナリモジュールのための前記１つ以上の有効な入力に含まれるかどうかを判断することを有する、
請求項１に記載の方法。
【請求項６】
前記解析は、前記バイナリモジュールのための最大入力サイズを決定することを有する、
請求項１に記載の方法。
【請求項７】
前記最大入力サイズは、バッファオーバーフローイベントを引き起こす、
請求項６に記載の方法。
【請求項８】
前記バイナリモジュールにとっての例外に関連する１つ以上の入力特性を決定するよう前記１つ以上の有効な入力をファジングする
ことを更に有する請求項１に記載の方法。
【請求項９】
前記バイナリモジュールのための１つ以上の有効な入力を決定するよう、ホワイトボックス・ファザーに前記１つ以上の有効な入力をシードする
ことを更に有する請求項１に記載の方法。
【請求項１０】
前記バイナリモジュールのための２つ以上の有効な入力を含むストリングを構築する
ことを更に有する請求項１に記載の方法。
【請求項１１】
未知の有効な入力を有するバイナリモジュールのための１つ以上のテスト入力として印刷可能文字の組を選択し、
前記バイナリモジュールのための前記１つ以上のテスト入力として前記印刷可能文字の組を用いて前記バイナリモジュールを実行し、
前記印刷可能文字の組に含まれる印刷可能文字の夫々について、前記印刷可能文字の組を用いて実行されることに応答して前記バイナリモジュールによって実行される命令の数を決定し、
１つ以上の前記印刷可能文字の夫々について実行される前記命令の数に関連する前記１つ以上の印刷可能文字を含むセットデータを生成し、
前記１つ以上の印刷可能文字に関連する前記命令の数と閾範囲との比較に基づき、前記バイナリモジュールのための１つ以上の有効な入力として１つ以上の印刷可能文字を識別するよう、前記セットデータを解析する
動作の実行又はその制御を行うようプロセッシングデバイスによって実行可能であるコンピュータ命令を記憶している非一時的なコンピュータ可読媒体。
【請求項１２】
前記動作は、前記セットデータに含まれる前記命令の数について最頻値を決定し、該最頻値を用いて前記閾範囲を決定することを更に有する、
請求項１１に記載の非一時的なコンピュータ可読媒体。
【請求項１３】
前記閾範囲は、上限及び下限を有し、前記動作は、
指定される試験定数と前記最頻値とを合計することによって、前記閾範囲の前記上限を決定し、
前記最頻値を前記指定される試験定数から減じることによって、前記閾範囲の前記下限を決定する
ことを更に有する、請求項１２に記載の非一時的なコンピュータ可読媒体。
【請求項１４】
前記解析は、前記バイナリモジュールのための前記１つ以上の有効な入力に含まれる印刷可能文字の１つ以上のタイプを識別し、該印刷可能文字の１つ以上のタイプが前記バイナリモジュールにとって有効なタイプであると決定することを有する、
請求項１１に記載の非一時的なコンピュータ可読媒体。
【請求項１５】
前記テスト入力のうちの１つは、前記バイナリモジュールのための当該テスト入力としてコマンド及び引数を含み、
前記解析は、前記コマンド及び前記引数を含む前記テスト入力が前記バイナリモジュールのための前記１つ以上の有効な入力に含まれるかどうかを判断することを有する、
請求項１１に記載の非一時的なコンピュータ可読媒体。
【請求項１６】
前記解析は、前記バイナリモジュールのための最大入力サイズを決定することを有する、
請求項１１に記載の非一時的なコンピュータ可読媒体。
【請求項１７】
前記最大入力サイズは、バッファオーバーフローイベントを引き起こす、
請求項１６に記載の非一時的なコンピュータ可読媒体。
【請求項１８】
前記動作は、前記バイナリモジュールにとっての例外に関連する１つ以上の入力特性を決定するよう前記１つ以上の有効な入力をファジングすることを更に有する
請求項１１に記載の非一時的なコンピュータ可読媒体。
【請求項１９】
前記動作は、前記バイナリモジュールのための１つ以上の有効な入力を決定するよう、ホワイトボックス・ファザーに前記１つ以上の有効な入力をシードすることを更に有する、
請求項１１に記載の非一時的なコンピュータ可読媒体。
【請求項２０】
前記動作は、前記バイナリモジュールのための２つ以上の有効な入力を含むストリングを構築することを更に有する、
請求項１１に記載の非一時的なコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
ここで論じられる実施形態は、未知のバイナリモジュールのための有効な入力を決定することに関係している。
【背景技術】
【０００２】
バイナリファイルの効率的な試験は、どの入力がバイナリファイルにとって有効であるかとの認識によって改善され得る。バイナリファイルは、人がテキストとして解釈し得るコード及びルーチンを含んでよい。しかし、バイナリファイルのコード及びルーチンに含まれるテキストは、人が読むことができないものである。コード及びルーチンは、人が読むことができないものであるから、バイナリファイルのコード及びルーチンを見直すことによってバイナリファイルにとっての有効な入力を決定することは、バイナリファイルの人である試験者には不可能である。結果として、人である試験者は、どの入力がバイナリファイルにとって有効であるのかを決定するために、バイナリファイルに関連する仕様、文書、又はソースコードを見直し得る。そのような有効な入力は、次いで、バイナリファイルのより効率的な試験を達成するために使用されてよい。
【発明の概要】
【０００３】
実施形態の態様によれば、方法は、未知の有効な入力を有するバイナリモジュールのための１つ以上のテスト入力として印刷可能文字の組を選択することを有する。当該方法は、前記バイナリモジュールのための前記１つ以上のテスト入力として前記印刷可能文字の組を用いて前記バイナリモジュールを実行することを更に有する。当該方法は、前記印刷可能文字の組に含まれる印刷可能文字の夫々について、前記印刷可能文字の組を用いて実行されることに応答して前記バイナリモジュールによって実行される命令の数を決定することを更に有する。当該方法は、１つ以上の前記印刷可能文字の夫々について実行される前記命令の数に関連する前記１つ以上の印刷可能文字を含むセットデータを生成することを更に有する。当該方法は、前記１つ以上の印刷可能文字に関連する前記命令の数と閾範囲との比較に基づき、前記バイナリモジュールのための１つ以上の有効な入力として１つ以上の印刷可能文字を識別するよう、前記セットデータを解析することを更に有する。
【０００４】
実施形態の目的及び利点は、少なくとも、特許請求の範囲で特に示されている要素、特徴、及び組み合わせによって、実現、達成される。
【０００５】
上記の概要及び下記の詳細な説明はいずれも、例示的且つ説明的であり、請求されている発明を制限するものではないことが理解されるべきである。
【図面の簡単な説明】
【０００６】
例となる実施形態は、添付の図面を使用して、更なる特定及び詳細をもって記載、説明される。
【０００７】
【図１Ａ】有効入力決定システムのための動作環境の例のブロック図である。
【０００８】
【図１Ｂ】有効入力決定システムの例のブロック図である。
【０００９】
【図２Ａ】複数の繰り返しにより連続してストリングを構築する例を表すブロック図である。
【００１０】
【図２Ｂ】複数の繰り返しにより並行してストリングを構築する例を表すブロック図である。
【００１１】
【図３】未知のバイナリモジュールのための有効な入力を決定するシステムの例のブロック図である。
【００１２】
【図４】未知のバイナリモジュールのための有効な入力のサイズを決定するシステムのブロック図である。
【００１３】
【図５Ａ】未知のバイナリモジュールのための有効な入力を決定する方法のフロー図を例示する。
【図５Ｂ】図５Ａからの続きであって、未知のバイナリモジュールのための有効な入力を決定する方法のフロー図を例示する。
【図５Ｃ】図５Ｂからの続きであって、未知のバイナリモジュールのための有効な入力を決定する方法のフロー図を例示する。
【図５Ｄ】図５Ｃからの続きであって、未知のバイナリモジュールのための有効な入力を決定する方法のフロー図を例示する。
【発明を実施するための形態】
【００１４】
ここで論じられる実施形態は、未知のバイナリモジュールのための有効な入力を決定することに関係している。有効な入力は、未知のバイナリモジュールのための有効な入力ストリングを含んでよい。有効な入力ストリングは、１つ以上の有効な文字を含んでよい。有効な入力ストリング及び有効な文字は、以下で、より詳細に記載される。
【００１５】
未知のバイナリモジュールは、プログラムのためのバイナリファイルを含んでよい。バイナリファイルは、バイナリ形式で符号化されて、プロセッシングデバイスによる実行のために非一時的なコンピュータ可読記憶媒体に記憶されているコード及びルーチンを含んでよい。バイナリファイルのコード及びルーチンは、人によってテキストとして解釈され得る部分を含み得るが、バイナリファイルのコード及びルーチンは、人が読むことができないものである。
【００１６】
人である試験者は、バイナリモジュールに含まれるバイナリファイルにとっての如何なる有効な入力も知り得ないので、バイナリモジュールは“未知”と記載されてよい。例えば、バイナリファイルに関連する仕様、文書又はソースコードは、バイナリモジュールの人である試験者には利用不可能であってよく、故に、試験者は、バイナリモジュールに含まれるバイナリファイルのための有効な入力を決定することができないことがある。
【００１７】
現在、未知のバイナリモジュールのための有効な入力を決定するための許容可能な方法は存在しない。未知のバイナリモジュールのための有効な入力を決定するための許容可能な方法であると見なされるためのいくつかの要件がある。第１の要件には、未知のバイナリモジュールのバイナリファイルに含まれるコード及びルーチン（デッドコードを除く。）の高い割合を一貫してカバーすることが挙げられ得る。例えば、バイナリファイルを試験するために選択された１つ以上のテスト入力は、バイナリファイルのためのコード及びルーチンの１００パーセント又は１００パーセント近く（例えば、デッドコード及びルーチンを除く、バイナリファイルの９０パーセントから１００パーセント）をカバーしてよい。既存の方法のいくつかは、未知のバイナリファイルを試験するためのランダムなテスト入力の生成に依存する。あいにく、ランダムに生成されるテスト入力は、未知のバイナリファイルのためのコード及びルーチンの高い割合を一貫してカバーするという目標と本質的に相容れないので、未知のバイナリファイルを試験するためのランダムなテスト入力の生成を含む試験方法は、未知のバイナリファイルのためのコード及びルーチンの高い割合を一貫してカバーすることができない。結果として、そのような既存の方法は、バイナリファイルのためのコード及びルーチンの高い割合を一貫してカバーすることができず、故に、それらの方法は許容可能であると見なされない。
【００１８】
未知のバイナリモジュールのための有効な入力を決定するための許容可能な方法と見なされるための他の要件には、バイナリファイルに関連する仕様、文書又はソースコードなしで有効に実施される能力が挙げられ得る。この要件は、ソフトウェアにおける脆弱性を自動で判断することがコンピュータシステムにとって有益である自律ソフトウェアセキュリティの分野において有益であり得る。いくつかの状況において、バイナリファイルは、バイナリモジュールの人である試験者に利用可能であってよいが、バイナリファイルに関連する仕様、文書及びソースコードは利用不可能であってよい。いくつかの既存の方法は、未知のバイナリモジュールのための有効な入力を決定しようと試みる。しかし、それのような方法は、ランダムに生成されたテスト入力に依存するか、又は他の欠陥を有する。
【００１９】
未知のバイナリモジュールのための有効な入力を決定するための許容可能な方法と見なされるための他の要件には、プラットフォーム非依存性が挙げられ得る。プラットフォーム非依存性は、有益なことには、メソッドロジの移植性を改善するとともに、他の利点を提供し得る。
【００２０】
上述されたように、未知のバイナリモジュールのための有効な入力を決定しようと試みる方法が存在する。あいにく、そのような方法は、それらが許容可能であると見なされないようにする多数の欠陥を伴う。
【００２１】
１つのそのような方法は、“シンボリック実行”と呼ばれてよい。シンボリック実行アプローチは、プログラムをクラッシュするかもしれない様々な実行パスに沿ってプログラムを駆動し得る未知のバイナリモジュールに含まれるバイナリファイルのための入力を決定することを含む。このアプローチは、いくつかの孤立した場合においては成功し得る。しかし、シンボリック実行アプローチに関連する１つの欠陥は、バイナリモジュールに関連するソースファイルがこのアプローチを実施するために必要とされ得ることである。いくつかの場合に、ソースファイルは利用可能でない。結果として、いくつかの場合に、シンボリック実行アプローチの実施は、ソースファイルが必要とされるが利用可能でないために、不可能であり、シンボリック実行アプローチは、許容可能なメッソドロジと見なされない。シンボリック実行アプローチの他の欠陥は、スケーリングがうまくできないことである。シンボリック実行アプローチはまた、多数の一般的なシナリオとともに働かない。例えば、シンボリック実行アプローチは、浮動小数点基底を含むプログラムとともに働くか、又はプログラムの実行中に収集される入力に対する制約が非線形である場合に、既知の問題を伴う。それらの利用及び他のために、シンボリック実行アプローチは、未知のバイナリモジュールのための有効な入力を決定する許容可能な方法でない。
【００２２】
他のアプローチは“ブラックボックス・ファジング”として知られている。このアプローチは、ストリングを選択し、ストリングをランダムに変更することを含んでよい。ストリングは、夫々の変更後に入力としてバイナリモジュールへ供給されてよい。このアプローチは、十分な時間を所与として働き得るが、ブラックボックス・ファジングによって生成される入力の大部分は無効な入力である。これは、有効な入力が更なる有効な入力を変化させ且つ識別するために必要とされるので、問題である。ブラックボックス・ファジングに伴う更なる問題は、このアプローチが、ランダムな入力に依存しているために、未知のバイナリモジュールに含まれるバイナリファイルの広いカバレッジを保証しないことであり、故に、ブラックボックス・ファジングを実施した結果が広いカバレッジを達成するかどうかを知ることは、不可能である。
【００２３】
他のアプローチは“ホワイトボックス・ファジング”として知られている。ホワイトボックス・ファジングアプローチは、有効な入力がシンボル制約を集めるために使用され、次いで、シンボル制約がテスト入力を生成するために解析され得る点を除いて、ブラックボックス・ファジングと同様である。ホワイトボックス・ファジングアプローチは、ランダムに到達されない少なくともいくつかの入力を含むので、ブラックボックス・ファジングに対する改善と見なされてよい。しかし、ホワイトボックス・ファジングアプローチは、テスト入力を決定するよう実施され得る前の前提条件として有効な入力を必要とする。いくつかの場合に、有効な入力は、ホワイトボックス・ファジングアプローチのためのシードとして利用可能でない。この理由のために、ホワイトボックス・ファジングアプローチは、それ自体によって、未知のバイナリモジュールのための有効な入力を決定するという問題を解決することができない。
【００２４】
他のアプローチは、プログラムのためのコードがユニットに分割され、体系的に試験される“単体試験”として知られている。単体試験は、いくつかの場合において、広いカバレッジのバイナリファイルの試験を達成することができるが、このアプローチは、例えばプログラムのための仕様などの、バイナリファイルに関連するソースファイル又は他の文書を常に必要とする。この情報なしでは、単体試験は実施され得ない。そのようなものとして、単体試験アプローチは、ソースファイル又は何らかの他の文書を必要とするので、未知のバイナリモジュールのための有効な入力を決定するという問題を解決することができない。単体試験アプローチに伴う他の欠陥は、それがプラットフォームに依存することである。単体試験アプローチはまた、遅く且つ高価であると考えられる。
【００２５】
他のアプローチは“仕様に基づく試験”として知られている。しかし、名前が暗示するように、仕様に基づく試験アプローチは、例えばプログラムのための仕様などの、バイナリファイルに関連するソースファイル又は他の文書を常に必要とする。そのようなものとして、このアプローチは、ソースファイル又は何らかの他の文書を必要とするので、未知のバイナリモジュールのための有効な入力を決定するという問題を解決することができない。単体試験と同様に、仕様に基づく試験アプローチはまた、プラットフォームに依存するとともに、遅く且つ高価であると考えられる。
【００２６】
他のアプローチには、“リバースコードエンジニアリング”が挙げられ得る。そのようなアプローチには、“情報交換解析”アプローチ、“ディスアセンブリ”アプローチ、及び“デコンパイル”アプローチが含まれ得る。情報交換解析アプローチは、情報がプログラムによって交換されない場合には有効でないことがあり、故に、このアプローチは、この理由のために制限され、許容可能でない。ディスアセンブリアプローチは、生のアセンブリコードの静的又は動的な解析に依存する。これは多数の欠陥を伴う。例えば、生のアセンブリコードの静的又は動的な解析は、計算コストが高く、不正確であり、スケーリングがうまくできず、深刻な性能オーバーヘッドを導入する可能性がある。デコンパイルアプローチは、バイナリファイルに関連するソースコードを再構築し、ソースコード及びバイナリファイルを用いて試験を進めようと試みる。しかし、実際には、デコンパイルアプローチは、多くの状況において働かず、再構築しようと試みる原ソースコードとは実際上実質的に異なるために有用でなかったり又は品質が低かったりするソースコードファイルを与えうる。
【００２７】
それら及び他のシステムの欠陥は、ここで記載される有効入力決定システムによって解消され得る。いくつかの実施において、有効入力決定システムは、ランダムな入力生成に依存しなくてよい。このように、有効入力決定システムは、１つ以上の有効な入力を決定する場合にプログラムの広いカバレッジを達成し得る。比べると、例えばブラックボックス・ファジングのような、ランダムな入力生成に依存する技術は、有効な入力を決定する場合に広いカバレッジを達成することができない。有効入力決定システムはまた、プラットフォーム非依存性であってよい。このように、有効入力決定システムは、移植可能であって、様々な動作環境において使用されてよい。有効入力決定システムはまた、プログラム又はバイナリファイルに関連するソースコード又は文書なしで成功裏に実施されてよい。このように、有効入力決定システムは、未知のバイナリモジュールのための有効な入力を決定するために使用されてよい。有効入力決定システムはまた、情報交換に依存するパケットスニッフィング、バス解析又はその他メソッドロジによらずに実施されてよい。このように、有効入力決定システムは、リバースコードエンジニアリング技術の使用を含むことなしに実施されてよい。
【００２８】
ここで記載される有効入力決定システムは、コンピュータデバイスを有してよい。例えば、有効入力決定システムは、パーソナルコンピュータ、ラップトップ、タブレットコンピュータ、サーバ、又はサーバソフトウェアを含む如何なるプロせっせベースのコンピュータデバイスも含んでよい。有効入力決定システムは、メモリ及びプロセッサデバイスを有してよい。プロセッサデバイスは、図５Ａ、５Ｂ、５Ｃ及び５Ｄを参照して後述される方法５００の１つ以上のステップを実行するようプログラムされてよい。有効入力決定システムの１つ以上の例となる実施は、以下で記載される。
【００２９】
未知のバイナリモジュールのバイナリファイルは、プログラムのコンパイルされたバージョンを含んでよい。プログラムは１つ以上の入力を受け入れてよい。プログラムのための入力は、１つ以上の入力ストリングを含んでよい。プログラムは、プログラムの機能性を記述するコード及びルーチンを含んでよい。プログラムのコード及びルーチンは、プログラム及び該プログラムのコンパイルされたバージョンであるバイナリファイルにとってどの入力が有効であるのかを定義してもよい。プログラムのコード及びルーチンによって有効であるとして定義されない如何なる入力も、プログラム及びバイナリファイルにとって無効な入力であってよい。プログラム及びバイナリファイルにとって無効である入力は、バイナリファイルを含むバイナリモジュールにとっても無効であってよい。
【００３０】
プログラムのための入力ストリングは、１つ以上のインデックスと、１つ以上の印刷可能文字とを含んでよい。インデックスは、印刷可能文字が現れるストリングにおける位置を含んでよい。例えば、受け入れられる入力ストリングが“Hello”及び“Howdy”である場合に、インデックスは“０”、“１”、“２”、“３”及び“４”である。この例では、インデックス“０”での有効な文字は、印刷可能文字“H”を含む。インデックス“１”での有効な文字は、印刷可能文字“e”及び“o”を含む。インデックス“２”での有効な文字は、印刷可能文字“l”及び“w”を含む。インデックス“３”の有効な文字は、“l”及び“d”を含む。インデックス“４”での有効な文字は、“o”及び“y”を含む。
【００３１】
有効な入力ストリングと見なされるよう、入力ストリングに含まれる文字の夫々は、プログラム又はバイナリファイルにとって有効であってよい。有効な入力ストリングのいずれかの所与のインデックスについて、入力ストリングでの使用に利用可能な印刷可能文字の大部分は、無効であってよい。有効入力決定システムは、印刷可能文字の組を受け、その印刷可能文字の組を繰り返し試験して、未知のバイナリモジュールのための有効な入力ストリングの異なるインデックスごとにそれらが有効な文字であるかどうかを判定するよう構成されてよい。
【００３２】
例えば、印刷可能文字の組に含まれる印刷可能文字の夫々は、入力ストリングの所与のインデックスについて未知のバイナリモジュールのためのテスト入力として使用されてよい。テスト入力は、１つ以上の印刷可能文字のストリングを含んでよい。複数の印刷可能文字がテスト入力に含まれる場合について、異なる印刷可能文字は、それらがテスト入力の異なるインデックスと関連付けられるように、連結されてよい。
【００３３】
有効入力決定システムのメモリは、ユーザ空間を含んでよい。ユーザ空間は、ユーザプロセッサが実行するメモリの部分を含んでよい。例えば、ユーザ空間は、テスト入力が所与のインデックスにおいて未知のバイナリモジュールにとって有効であるかどうかを判定するよう未知のバイナリモジュールがテスト入力を用いて実行され得るメモリの部分を含んでよい。
【００３４】
いくつかの実施において、有効入力決定システムは、未知のバイナリモジュールのための入力としてテスト入力を用いて未知のバイナリモジュールが実行される場合にユーザ空間において実行される命令の数を解析することによって、テスト入力が所与のインデックスにとって有効であるかどうかを判定してよい。所与のインデックス“ｉ”において、未知のバイナリモジュールは、未知のバイナリモジュールのためのテスト入力として使用されるべき“ｉ＋１”個の文字を含む入力ストリングを供給されてよい。いくつかの実施において、印刷可能文字の組に含まれる印刷可能文字の夫々（“［スペース］”を除く。）は、所与のインデックスにおいて未知のバイナリモジュールのためのテスト入力として使用されてよい。未知のバイナリモジュールは、未知のバイナリモジュールのための入力としてテスト入力を用いて実行されることに応答して、メモリのユーザ空間において命令を実行してよい。テスト入力ごとに実行される命令の数は、モニタされ、記録されてよい。有効入力決定システムは、所与のインデックスでのテスト入力ごとにユーザ空間において実行される命令の数を解析してよい。
【００３５】
いくつかの実施において、有効入力決定システムは、所与のインデックスにある印刷可能文字について実行される命令の数を決定してよい。実行される命令の数は、有効入力決定システムのメモリに記憶され、その数の命令が実行されることを生じさせた印刷可能文字と関連付けられてよい。有効入力決定システムは、特定の印刷可能文字について実行される命令の数が閾範囲外にあるかどうかを判定してよい。いくつかの実施において、このプロセスは、印刷可能文字の組に含まれる印刷可能文字の夫々が異なるテスト入力として使用され得るので、その組に含まれる印刷可能文字の夫々について繰り返されてよい。有効入力決定システムは、閾範囲外にある値を持った命令の数に関連する印刷可能文字が、未知のバイナリモジュールのための有効な入力における包含のための候補であり得ると決定してよい。閾範囲内にある値を持った命令の数に関連する印刷可能文字は、未知のバイナリモジュールのための有効な入力における包含のための候補から除外されてよい。
【００３６】
閾範囲は、実行される命令の数の最頻値及び試験定数に基づき有効入力決定システムによって決定されてよい。最頻値は、実行される命令の数についての最頻値を含んでよい。例えば、実行される命令の数は、組において記憶されてよい。組は、１つ以上の数値を含んでよい。数値は、入力ごとに実行される命令の数を表してよい。例えば、第１の入力は、１００個の命令が実行されることを生じさせたとする。第１の入力についての数値は、数“１００”であってよい。組は、他の入力についての他の数値を含んでよい。最頻値は、組において最もよく現れる数値を含んでよい。
【００３７】
試験定数は、“イプシロン”又は“試験定数”と呼ばれ得る。試験定数は、如何なる正の実数も含んでよい。閾範囲の上限は、試験定数を最頻値に加えることによって、有効入力決定システムによって決定されてよい。閾範囲の下限は、試験定数を最頻値から減じることによって、有効入力決定システムによって決定されてよい。上述されたように、いくつかの実施において、有効入力決定システムは、未知のバイナリモジュールのための異なるテスト入力として夫々の印刷可能文字を使用し、テスト入力ごとに実行される命令の数を含むデータの組を記録する。閾範囲を決定するために使用される最頻値は、テスト入力ごとに実行される命令の数を含むデータの組についての最頻値を含んでよい。いくつかの実施において、有効入力決定システムは、未知のバイナリモジュールのための入力として使用することで閾範囲の外にある実行される命令の数を生じさせる如何なる印刷可能文字も、未知のバイナリモジュールのための有効な入力ストリングにおける包含のための候補であると決定してよい。
【００３８】
本発明の実施形態は、添付の図面を参照して説明される。
【００３９】
図１Ａは、ここで記載される少なくとも１つの実施形態に従って配置される、有効入力決定システムのための例となる動作環境１００のブロック図である。動作環境１００は、次の要素、すなわち、印刷可能文字データ１２０と、バイナリモジュール１３０と、有効入力決定システム１０５と、有効入力データ１４０とを含んでよい。印刷可能文字データ１２０及びバイナリモジュール１３０は、有効入力決定システム１０５へ入力されてよい。有効入力決定システム１０５は、有効入力データ１４０を出力してよい。有効入力決定システム１０５は、印刷可能文字データ１２０及びバイナリモジュール１３０の１つ以上を受けることに応答して、有効入力データ１４０を出力してよい。
【００４０】
印刷可能文字データ１２０は、１つ以上の印刷可能文字を記述するデータを含んでよい。例えば、印刷可能文字データ１２０は、印刷可能文字の組を記述するデータを含んでよい。いくつかの実施において、印刷可能文字データ１２０は、１つ以上の印刷可能文字のリストを含んでよい。
【００４１】
バイナリモジュール１３０はバイナリファイルを含んでよい。バイナリファイルは、プログラムのコンパイルされたバージョンを含んでよい。プログラムは、プロセッサベースのコンピュータデバイスについての機能性を提供するよう構成されたコード及びルーチンを含んでよい。バイナリモジュール１３０は、“未知”のバイナリモジュールとして記載されてよい。バイナリモジュールの人である試験者は、バイナリモジュールに含まれるバイナリファイルのための如何なる有効な入力も知り得ないので、バイナリモジュール１３０は“未知”と記載されてよい。例えば、バイナリファイルに関連する仕様、文書又はソースコードは、利用不可能であってよく、故に、人である試験者は、バイナリモジュール１３０に含まれるバイナリファイルのための有効な入力を決定することができないことがある。
【００４２】
バイナリファイルは、バイナリ形式で符号化されているコード及びルーチンを含んでよい。バイナリファイルのコード及びルーチンは、テキストとして人によって解釈され得る部分を含んでよいが、バイナリファイルのコード及びルーチンは、人が読むことができないものである。
【００４３】
有効入力決定システム１０５は、プロセッサベースのコンピュータデバイスを有してよい。例えば、有効入力決定システム１０５は、ハードウェアのパーソナルコンピュータ、ラップトップ、タブレットコンピュータ、サーバデバイス、又はサーバとして機能するよう構成された如何なる他のプロセッサベースのコンピュータデバイスも有してよい。
【００４４】
いくつかの実施において、有効入力決定システム１０５は、図５Ａ、５Ｂ、５Ｃ及び５Ｄを参照して後述される方法５００の１つ以上のブロックを実行するようプログラムされているプロセッサベースのコンピュータデバイスを有してよい。例えば、有効入力決定システム１０５は、図５Ａ、５Ｂ、５Ｃ及び５Ｄを参照して後述される方法５００の１つ以上のブロックを実行するようプログラムされている特別目的のコンピュータデバイスを有してよい。
【００４５】
有効入力決定システム１０５は、印刷可能文字データ１２０及びバイナリモジュール１３０を入力として受けるよう構成されてよい。有効入力決定システム１０５は、有効入力データ１４０を決定するよう印刷可能文字データ１２０を解析してよい。
【００４６】
有効入力決定システム１０５は、コンピュータシステムが、そのコンピュータシステムにおける有効な入力及び挙動並びに効果が知られていないバイナリモジュール１３０を実行することを可能にすることによって、コンピュータシステムの性能を改善してよい。このように、有効入力決定システム１０５は、コンピュータシステムが、さもなければ役に立たなくなり得るバイナリモジュール１３０を使用することを可能にしてよい。例えば、有効入力決定システム１０５は、有益なことには、バイナリモジュール１３０の最大入力サイズを決定してよい。バイナリモジュール１３０のための最大入力サイズは、バイナリモジュール１３０がコンピュータシステムによって実行される場合にバッファオーバーフローイベントを引き起こす入力サイズを有してよい（なお、いくつかの例では、最大入力サイズを超えることは、バッファオーバーフローイベントを生じさせ得ない。）。然るに、最大入力サイズに関する情報を有することは、有益なことには、コンピュータシステムがバッファオーバーフローイベントを引き起こさずにバイナリモジュール１３０を実行することを可能にすることによって、コンピュータシステムを改善し得る。
【００４７】
有効入力データ１４０は、バイナリモジュール１３０のための１つ以上の有効な入力を記述するデータを含んでよい。有効入力決定システム１０５は、印刷可能文字データ１２０及びバイナリモジュール１３０に基づき有効入力データ１４０を決定してよい。有効入力データ１４０によって記述されるバイナリモジュール１３０のための有効な入力は、バイナリモジュール１３０のための有効な入力に含まれる有効な文字として印刷可能文字データ１２０から有効入力決定システム１０５によって選択された１つ以上の印刷可能文字を含んでよい。有効入力データ１４０によって記述される有効な入力は、１つ以上の有効な入力ストリングを含んでよい。例えば、有効入力データ１４０によって記述される有効な入力は、印刷可能文字データ１２０から選択された有効な文字の１つ以上を含むストリングを含んでよい。
【００４８】
有効入力データ１４０は、バッファモジュール１３０のための更なる有効な入力を決定するために使用されてよい。例えば、有効入力データ１４０によって記述される有効な入力は、ホワイトボックス・ファザーのためのシードとして使用されてよい。ホワイトボックス・ファザーは、次いで、有効入力データ１４０によって記述される有効な入力に基づき、バイナリモジュール１３０のための更なる有効な入力を決定してよい。
【００４９】
有効入力決定システム１０５によって決定される有効入力データ１４０は、バイナリモジュール１３０にとっての例外に関連する１つ以上の入力文字を決定するためにも使用されてよい。例えば、有効入力データ１４０によって記述される１つ以上の有効な入力は、ファザーのための入力として使用されてよい。ファザーは、データのどの特性がコンピュータシステムにおいて例外、メモリ・リーク又は他の欠陥を引き起こし得るのかを決定するようデータを解析するために使用されるコード及びルーチンを含んでよい。１つ以上の有効な入力は、ファザーによってファジングされてよい。１つ以上の有効な入力をファジングすることは、有益なことには、どの入力特性が例外、メモリ・リーク又は他の欠陥に関連するのかを記述するデータを提供し得る。このように、有効入力決定システム１０５によって決定される有効入力データ１４０は、コンピュータシステムに関連する例外、メモリ・リーク又は他の欠陥の事実を減らすことによって、コンピュータシステムの性能を改善するために使用されてよい。
【００５０】
有効入力決定システム１０５は、プロセッシングデバイス１０２及びメモリ１０６を有してよい。プロセッシングデバイス１０２は、算術論理演算ユニット、マイクロプロセッサ、汎用コントローラ、又は演算処理を実行して、電子表示信号を表示デバイスへ供給する何らかの他のプロセッサ若しくはプロセッサアレイを有してよい。プロセッシングデバイス１０２はデータ信号を処理してよい。プロセッシングデバイス１０２は、複数命令セットコンピュータ（ＣＩＳＣ）アーキテクチャ、縮小命令セットコンピュータ（ＲＩＳＣ）アーキテクチャ、又は命令セットの組み合わせを実装するアーキテクチャを含む様々なコンピュータアーキテクチャを有してよい。図１Ａには１つのプロセッシングデバイス１０２しか示されていないが、複数のプロセッシングデバイス１０２が含まれてよい。他のプロセッサ、オペレーティングシステム、センサ、ディスプレイ、及び物理構成が可能である。
【００５１】
いくつかの実施において、プロセッシングデバイス１０２は、図５Ａ、５Ｂ、５Ｃ及び５Ｄを参照して後述される方法５００の１つ以上のブロックを実行するようプログラムされてよい。例えば、プロセッシングデバイス１０２は、図５Ａ、５Ｂ、５Ｃ及び５Ｄを参照して後述される方法５００の１つ以上のブロックを実行するようプログラムされている特別目的のコンピュータデバイスを有してよい。
【００５２】
メモリ１０６は、非一時的なコンピュータ可読媒体を有してよい。メモリ１０６は、プロセッシングデバイス１０２によって実行され得る命令及び／又はデータを記憶してよい。命令及び／又はデータは、ここで記載される技術を実行するためのコードを含んでよい。メモリ１０６は、動的ランダムアクセスメモリ（ＤＲＡＭ）デバイス、静的ランダムアクセスメモリ（ＳＲＡＭ）デバイス、フラッシュメモリ、又は何らかの他のメモリデバイスを有してよい。いくつかの場合に、メモリ１０６は、ハードディスクドライブ、フロッピー（登録商標）ディスクドライブ、ＣＤ−ＲＯＭデバイス、ＤＶＤ−ＲＯＭデバイス、ＤＶＤ−ＲＡＭデバイス、ＤＶＤ−ＲＷデバイス、フラッシュメモリデバイス、又はより持続的に情報を記憶するための何らかの他の大容量記憶デバイスを含む不揮発性メモリ又は同様の永久記憶デバイス及び媒体を更に有してよい。いくつかの実施において、印刷可能文字データ１２０、バイナリモジュール１３０及び有効入力データ１４０の１つ以上は、メモリ１０６において記憶されてよい。
【００５３】
いくつかの実施において、プロセッシングデバイス１０２は、メモリ１０６に記憶されている命令及び／又はデータにアクセスし、実行するよう、メモリ１０６へ通信上結合されてよい。例えば、メモリ１０６は、図５Ａ、５Ｂ、５Ｃ及び５Ｄを参照して後述される方法５００の１つ以上のブロックを実行するようプログラムされているコード及びルーチンを記憶してよく、プロセッシングデバイス１０２は、メモリ１０６にアクセスし、それに記憶されているコード及びルーチンを実行して、方法５００の１つ以上のブロックを実行してよい。
【００５４】
いくつかの実施において、メモリ１０６はユーザ空間を有してよい。ユーザ空間は、ユーザプロセスが実行されるメモリ１０６の部分を含んでよい。例えば、バイナリモジュール１３０は、メモリ１０６のユーザ空間において実行され、走らされてよい。
【００５５】
図１Ｂは、ここで記載される少なくとも１つの実施形態に従って配置される、例となる有効入力決定システム１０５のブロック図である。いくつかの実施において、有効入力決定システム１０５は、ストリングビルダモジュール１１０と、実行モジュール１１２と、フィルタモジュール１１４とを有してよい。
【００５６】
ストリングビルダモジュール１１０は、テスト入力データ１２２を実行モジュール１１２へ供給するよう構成されるコード及びルーチンを有してよい。テスト入力データ１２２は、印刷可能文字データ１２０からストリングビルダモジュール１１０によって選択される１つ以上の印刷可能文字を記述するデータを含んでよい。ストリングビルダモジュール１１０は、テスト入力データ１２２に含まれる１つ以上の印刷可能文字を選択してよい。それにより、選択された印刷可能文字は、所与のインデックスにおいてバイナリモジュール１３０のための有効な入力ストリームに含まれるべき１つ以上の有効な文字をそれらが含むかどうかを判定するよう、実行モジュール１１２及びフィルタモジュール１１４によって試験されてよい。
【００５７】
いくつかの実施において、ストリングビルダモジュール１１０は、印刷可能文字データ１２０に含まれる全ての印刷可能文字が実行モジュール１１２及びフィルタモジュール１１４によって試験されるまで、テスト入力データ１２２となるよう印刷可能文字データ１２０から印刷可能文字を繰り返し選択してよい。このように、有効入力決定システム１０５は、印刷可能文字データ１２０に含まれる利用可能な印刷可能文字がバイナリモジュール１３０のためのテスト入力となり得るので、バイナリモジュール１３０のための有効な文字を決定するときにテスト入力のランダムな選択に依存しない。
【００５８】
実行モジュール１１２及びフィルタモジュール１１４を参照して以下で更に詳細に記載されるように、実行モジュール１１２及びフィルタモジュール１１４は、テスト入力データ１２２によって記述される１つ以上の印刷可能文字の中から所与のインデックスについて１つ以上の有効な文字の存在を判定するよう、テスト入力データ１２２を解析してよい。
【００５９】
いくつかの実施において、テスト入力データ１２２は、コマンド及び引数を含んでよい。実行モジュール１１２及びフィルタモジュール１１４はテスト入力データ１２２を解析してよい。解析は、コマンド及び引数を含むテスト入力データ１２２が、有効入力データ１４０によって記述される１つ以上の有効な入力に含まれるかどうかを判定することを含んでよい。
【００６０】
ストリングビルダモジュール１１０は、有効文字データ１３８を受けてよい。例えば、ストリングビルダモジュール１１０は、フィルタモジュール１１４から有効文字データ１３８を受けてよい。フィルタモジュール１１４及び有効文字データ１３８を参照して以下で更に詳細に記載されるように、有効文字データ１３８は、バイナリモジュール１３０のための有効な入力ストリングの所与のインデックスについての１つ以上の有効な文字を記述してよい。
【００６１】
ストリングビルダモジュール１１０は、有効文字データ１３８に基づきバイナリモジュール１３０のための１つ以上の有効な入力を形成するよう構成されるコード及びルーチンを含んでよい。有効な入力は、有効文字データ１３８によって記述される有効な文字の１つ以上から構築されるストリングを含んでよい。このストリングは、バイナリモジュール１３０のための有効な入力ストリングを含んでよい。ストリングビルダモジュール１１０は、繰り返しプロセスを用いて有効な入力ストリングを構築してよい。図２Ａ及び２Ｂは、いくつかの実施に従って有効入力決定システム１０５によって構築されるストリングの例を表す。
【００６２】
いくつかの実施において、ストリングビルダモジュール１１０は、実行モジュール１１２及びフィルタモジュール１１４の１つ以上へ通信上結合されてよい。ストリングビルダモジュール１１０は、次の要素、すなわち、印刷可能文字データ１２０、テスト入力データ１２２、及び有効入力データ１４０のうちの１つ以上を有してよい。
【００６３】
印刷可能文字データ１２０及び有効入力データ１４０は、図１Ａを参照して上述された。故に、それらの説明はここで繰り返されない。
【００６４】
テスト入力データ１２２は、有効入力データ１４０における包含の候補として印刷可能文字データ１２０から選択された１つ以上の印刷可能文字を記述するデータを含んでよい。テスト入力データ１２２によって記述される異なる印刷可能文字は、夫々、集合的に又は個別的に“テスト入力”と呼ばれてよい。テスト入力データ１２２は実行モジュール１１２へ供給されてよい。実行モジュール１１２は、バイナリモジュール１３０のための入力としてテスト入力データ１２２によって記述されるテスト入力を用いて、バイナリモジュール１３０を実行してよい。実行モジュール１１２は、テスト入力データ１２２の実行に基づきセットデータ１３２を決定してよい。フィルタモジュール１１４は、テスト入力データ１２２に含まれる１つ以上の文字が有効な入力ストリングの所与のインデックスについて有効な文字であると決定してよい。フィルタモジュール１１４は、セットデータ１３２に基づき有効な文字を識別してよい。フィルタモジュール１１４は、１つ以上の有効な文字を記述する有効文字データ１３８をストリングビルダモジュール１１０へ送出してよい。
【００６５】
ストリングビルダモジュール１１０は有効文字データ１３８を受けてよい。いくつかの実施において、有効文字データ１３８によって記述される有効な文字は、有効入力データ１４０における包含のための候補を含んでよい。ストリングビルダモジュール１１０は、例えば図１Ａについて上述されたメモリ１０６のような、メモリにおいて、有効文字データ１３８を記憶してよい。いくつかの実施において、ストリングビルダモジュール１１０は、バイナリモジュール１３０のための１つ以上の有効な入力ストリングとして、有効文字データ１３８によって記述される有効な文字を記憶してよい。１つ以上の有効な入力ストリングは、１つ以上の有効な入力に含まれ、有効入力データ１４０によって記述されてよい。このように、有効な文字は、印刷可能文字データ１２０から選択され、バイナリモジュール１３０のための入力としての有効性を解析され、有効入力データ１４０によって記述されるバイナリモジュール１３０のための１つ以上の有効な入力ストリングとして記憶されてよい。
【００６６】
実行モジュール１１２は、テスト入力データ１２２を用いてバイナリモジュール１３０を実行するよう構成されるコード及びルーチンを含んでよい。いくつかの実施において、実行モジュール１１２は、図１を参照して上述されたメモリ１０６のユーザ空間において、テスト入力データ１２２を用いてバイナリモジュール１３０を実行してよい。いくつかの実施において、実行モジュール１１２は、例えばperf、GND  Debugger（ときどき“ＧＤＢ”と呼ばれる。）、ValgrindのCallgrindツール、又はその他性能解析ツールのような、性能解析ツールを用いて、バイナリモジュール１３０を実行してよい。このように、実行モジュール１１２は、テスト入力データ１２２を用いてバイナリモジュール１３０を実行し、バイナリモジュール１３０によって実行される命令の数をモニタし、その数を、バイナリモジュール１３０のための入力としてテスト入力データ１２２を用いてバイナリモジュール１３０を実行した後に数え、バイナリモジュール１３０によって実行される命令の数と、それらの命令の実行に関連する印刷可能文字とを記述するデータを記憶してよい。実行される命令の数を記述する記憶されたデータは、セットデータ１３２を参照して以下で更に詳細に記載される。
【００６７】
いくつかの実施において、バイナリモジュール１３０によって実行される命令の数をモニタし、数えるためにperfを使用することは、実行される命令の数の不正確なカウントを生じさせ得る。然るに、いくつかの実施において、実行モジュール１１２は、ハードコードされた値をカウントに加えるよう構成されてよい。ハードコードされた値は、１から１００までの範囲から選択される正の整数又は浮動小数であってよい。いくつかの実施において、実行モジュール１１２は、カウントの有効性を確かめるために、バイナリモジュール１３０を２回以上実行してよい。バイナリモジュール１３０の複数回の実行にわたるカウントの差を実行モジュール１１２が識別することによりカウントが不正確であると判断される場合は、実行モジュール１１２は、ハードコードされた値を選択し、それをカウントに加えるよう構成されてよい。カウントのための更なるエラー検出及び訂正は、図４を参照して以下で更に詳細に記載される。
【００６８】
いくつかの実施において、実行モジュール１１２は、ストリングビルダモジュール１１０及びフィルタモジュール１１４の１つ以上へ通信上結合されてよい。実行モジュール１１２は、次の要素、すなわち、インタラクションモジュール１２６、モニタモジュール１２８、及びバイナリモジュール１３０の１つ以上を有してよい。バイナリモジュール１３０は、図１を参照して上述された。故に、これの説明はここでは繰り返されない。
【００６９】
インタラクションモジュール１２６は、実行モジュール１１２と、ストリングビルダモジュール１１０と、フィルタモジュール１１４との間のインタラクションを管理するよう構成されるコード及びルーチンを含んでよい。いくつかの実施において、インタラクションモジュール１２６は、ストリングビルダモジュール１１０からデータを受けてよい。例えば、インタラクションモジュール１２６は、ストリングビルダモジュール１１０からテスト入力データ１２２を受けてよい。いくつかの実施において、インタラクションモジュール１２６は、フィルタモジュール１１４及びストリングビルダモジュール１１０へデータを送出してよい。例えば、インタラクションモジュール１２６は、セットデータ１３２をフィルタモジュール１１４へ送出してよい。セットデータ１３２は、以下の段落で更に詳細に記載される。
【００７０】
モニタモジュール１２８は、バイナリモジュール１３０のための入力としてテスト入力データ１２２を用いてバイナリモジュール１３０を実行することに応答して、ユーザ空間において実行される命令の数の実行をモニタするよう構成されるコード及びルーチンを含んでよい。モニタモジュール１２８は、例えばメモリ１０６のようなメモリにおいて実行される命令の数を記憶してよい。モニタモジュール１２８は、実行される命令の数が、その数の命令が実行されることを生じさせる、テスト入力データ１２２によって記述されるテスト入力と関連付けられるように、実行される命令の数を記憶してよい。テスト入力データ１２２によって記述されるテスト入力は、印刷可能文字データ１２０から選択される１つ以上の印刷可能文字を含んでよい。実行される命令の数及びその数についての関連するテスト入力は、セットデータ１３２として記憶されてよい。セットデータ１３２は、関連するデータの１つ以上の対を記述してよい。各対は、（１）テスト入力と、（２）関連するテスト入力を用いて実行されるときにバイナリモジュール１３０によって実行される命令の数とを含んでよい。インタラクションモジュール１２６は、セットデータ１３２をフィルタモジュール１１４へ送出してよい。
【００７１】
フィルタモジュール１１４は、セットデータ１３２を解析し、所与のインデックスについて１つ以上の有効な文字を決定するよう構成されるコード及びルーチンを含んでよい。フィルタモジュール１１４は、セットデータ１３２の解析に基づき１つ以上の有効な文字を決定してよい。有効な文字は、バイナリモジュール１３０のための有効な入力を形成するために使用されてよい。有効な文字は、有効文字データ１３８によって記述されてよい。フィルタモジュール１１４は、ストリングビルダモジュール１１０及び実行モジュール１１２の１つ以上へ通信上結合されてよい。フィルタモジュール１１４は、次の要素、すなわち、セットデータ１３２、モードモジュール１３４、及びレンジモジュール１３６の１つ以上を有してよい。セットデータ１３２は、実行モジュール１１２を参照して上述された。故に、これの説明はここで繰り返されない。
【００７２】
モードモジュール１３４は、セットデータ１３２を解析して、セットデータ１３２に含まれる１つ以上の数について最頻値（又はモード（mode））を決定するよう構成されるコード及びルーチンを含んでよい。最頻値は、モードデータによって記述されてよい。モードモジュール１３４は、例えば図１Ａを参照して上述されたメモリ１０６のような、メモリにおいて、モードデータを記憶してよい。モードモジュール１３４は、モードデータをレンジモジュール１３６へ供給するようレンジモジュール１３６へ通信上結合されてよい。
【００７３】
レンジモジュール１３６は、閾範囲（又はレンジ（range））を決定するよう構成されるコード及びルーチンを含んでよい。レンジモジュール１３６は、モードデータによって記述される最頻値に基づき閾範囲を決定してよい。例えば、レンジモジュール１３６は、最頻値及び試験定数に基づき閾範囲を決定してよい。試験定数は、如何なる正の実数又は浮動小数も有してよい。試験定数は、有効入力決定システム１０５の人である試験者によって供給されてよい。例えば、試験定数は、有効入力決定システム１０５の人である試験者によって与えられる特定の正の実数を有してよい。有効入力決定システム１０５の人であるユーザには、バイナリモジュール１３０の人である試験者を含まれ得る。
【００７４】
閾範囲は、条件及び下限を含んでよい。レンジモジュール１３６は、試験定数を最頻値に加えることによって、閾範囲の上限を決定してよい。レンジモジュール１３６は、試験定数を最頻値から減じることによって、閾範囲の下限を決定してよい。このように、レンジモジュール１３６は閾範囲を決定してよい。閾範囲は、閾データによって記述されてよい。レンジモジュール１３６は、例えば図１Ａを参照して上述されたメモリ１０６のような、メモリにおいて、閾データを記憶してよい。
【００７５】
レンジモジュール１３６は、１つ以上の有効な文字を決定するよう構成されるコード及びルーチンを含んでよい。例えば、レンジモジュール１３６は、バイナリモジュール１３０のための有効な入力ストリングの所与のインデックスについて１つ以上の有効な文字を決定してよい。いくつかの実施において、レンジモジュール１３６は、バイナリモジュール１３０のための入力として使用することで閾範囲の外にある実行される命令の数を生じさせる、セットデータ１３２に含まれる如何なる印刷可能文字も、有効な文字であると決定してよい。いくつかの実施において、レンジモジュール１３６によって決定された夫々の有効な文字は、バイナリモジュール１３０のための有効な入力ストリングにおける包含の候補であってよい。
【００７６】
有効文字データ１３８は、レンジモジュール１３６によって決定された１つ以上の有効な文字を記述するデータを含んでよい。いくつかの実施において、有効文字データ１３８は、バイナリモジュール１３０のための有効な入力ストリングの所与のインデックスについての１つ以上の有効な文字を記述してよい。フィルタモジュール１１４は、有効文字データ１３８をストリングビルダモジュール１１０へ供給してよい。いくつかの実施において、フィルタモジュール１１４は、例えば図１Ａを参照して上述されたメモリ１０６のような、メモリにおいて、有効文字データ１３８を記憶してよい。
【００７７】
いくつかの実施において、ストリングビルダモジュール１１０、実行モジュール１１２、インタラクションモジュール１２６、モニタモジュール１２８、バイナリモジュール１３０、フィルタモジュール１１４、モードモジュール１３４、及びレンジモジュール１３６の１つ以上は、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）又は特定用途向け集積回路（ＡＳＩＣ）を含むハードウェアを用いて実装されてよい。いくつかの他の場合では、ストリングビルダモジュール１１０、実行モジュール１１２、インタラクションモジュール１２６、モニタモジュール１２８、バイナリモジュール１３０、フィルタモジュール１１４、モードモジュール１３４、及びレンジモジュール１３６は、ハードウェアとソフトウェアとの組み合わせを用いて実装されてよい。よって、ストリングビルダモジュール１１０、実行モジュール１１２、インタラクションモジュール１２６、モニタモジュール１２８、バイナリモジュール１３０、フィルタモジュール１１４、モードモジュール１３４、及びレンジモジュール１３６は、ハードウェアデバイスとして実装されてよい。
【００７８】
図２Ａは、ここで記載される少なくとも１つの実施形態に従って配置される、複数の繰り返しにより連続してストリングを構築する例２００を表すブロック図である。図２Ａに示されるストリングは、図１Ａ及び１Ｂを参照して上述された有効入力決定システム１０５によって構築されてよい。ストリングは、図１Ａ及び１Ｂを参照して上述されたバイナリモジュール１３０のための有効な入力を含んでよい。
【００７９】
この例２００において、ストリングの初期状態は、図２Ａの左手側に表されている。ストリングは、複数の繰り返しにわたって構築されてよい。図２Ａに表されている最後の繰り返しは“繰り返し３”である。これは、図２Ａの右手側に表されている。最初に、ストリングは、図２Ａの左手側に表されているストリングの初期状態に示されるように、空であってよい。しかし、この例２００における“繰り返し３”では、有効入力決定システム１０５は、有効な文字“h”、“e”、“l”及び“p”を含むストリングを構築している。それらの有効な文字によって形成されたストリングは、語“help”を含む。然るに、この例２００では、有効入力決定システム１０５は、ストリング“help”が、図１Ａ及び１Ｂを参照して上述されたバイナリモジュール１３０のための有効な入力であると決定している。
【００８０】
図２Ｂは、ここで記載される少なくとも１つの実施形態に従って配置される、複数の繰り返しにより並行してストリングを構築する例を２０５表すブロック図である。ストリングは、図１Ａ及び１Ｂを参照して上述された有効入力決定システム１０５によって構築されてよい。ストリングは、図１Ａ及び１Ｂを参照して上述されたバイナリモジュール１３０のための有効な入力を含んでよい。
【００８１】
この例２０５において、ストリングの初期状態は、図２Ｂの左手側に表されている。ストリングは、複数の繰り返しにわたって構築されてよい。図２Ｂに表されている最後の繰り返しは“繰り返し３”である。これは、図２Ｂの右手側に表されている。最初に、ストリングは、図２Ｂの左手側に表されているストリングの初期状態に示されるように、空であってよい。しかし、この例２０５における“繰り返し３”では、有効入力決定システム１０５は、２つのストリングを構築している。第１のストリングは、有効な文字“h”、“e”、“l”及び“p”を含む。それらの有効な文字によって形成された第１のストリングは、語“help”を含む。然るに、この例２０５では、有効入力決定システム１０５は、ストリング“help”が、バイナリモジュール１３０のための有効な入力であると決定している。第２のストリングは、有効な文字“c”、“u”及び“t”を含む。それらの有効な文字によって形成された第２のストリングは、語”cut”を含む。然るに、この例２０５では、有効入力決定システム１０５は、ストリング“cut”が、バイナリモジュール１３０のための有効な入力であると決定している。
【００８２】
図３は、ここで記載される少なくとも１つの実施形態に従って配置される、未知のバイナリモジュールのための有効な入力を決定する例となるシステム３００のブロック図である。図３のシステム３００は、図１Ａ及び１Ｂを参照して上述された有効入力決定システム１０５の例であってよい。
【００８３】
システム３００は、プロセッシングデバイス１０２と、メモリ１０６とを有してよい。プロセッシングデバイス１０２及びメモリ１０６は、図１Ａを参照して上述された。故に、その説明はここで繰り返されない。システム３００の様々な構成要素は、バス３２０を介して互いと通信上結合されてよい。
【００８４】
図示されている実施形態では、メモリ１０６は、ストリングビルダモジュール１１０と、実行モジュール１１２と、フィルタモジュール１１４と、システムデータ３０８とを記憶してよい。ストリングビルダモジュール１１０、実行モジュール１１２、及びフィルタモジュール１１４は、図１Ａ及び１Ｂを参照して上述された。故に、それらの説明はここで繰り返されない。システムデータ３０８は、システム３００がその機能性を提供するために使用される如何なるデータも含んでよい。例えば、システムデータ３０８は、印刷可能文字データ１２０、テスト入力データ１２２、有効入力データ１４０、セットデータ１３２、又は有効文字データ１３８の１つ以上といった、図１Ａ及び１Ｂを参照して上述されたデータのいずれかを含んでよい。
【００８５】
いくつかの実施において、システム３００は、図５Ａ、５Ｂ、５Ｃ及び５Ｄを参照して後述される方法５００の１つ以上のブロックを実行するようプログラムされているプロセッサベースのコンピュータデバイスを有してよい。
【００８６】
図４は、ここで記載される少なくとも１つの実施形態に従って配置される、未知のバイナリモジュールのための有効な入力のサイズを決定するシステム４００のブロック図である。システム４００は、プロセッサベースのコンピュータデバイスを有してよい。例えば、システム４００は、ハードウェアのパーソナルコンピュータ、タブレットコンピュータ、メインフレーム、サーバデバイス、又はサーバとして機能するよう構成された如何なる他のプロセッサベースのコンピュータデバイスも有してよい。いくつかの実施において、図４のシステム４００は、図１Ａ及び１Ｂを参照して上述された有効入力決定システム１０５の例であってよい。いくつかの実施において、図１Ａ及び１Ｂを参照して上述された有効入力決定システム１０５は、システム４００の１つ以上の要素を含むよう変更されてよい。
【００８７】
システム４００は、次の要素、すなわち、ストリングビルダモジュール１１０、実行モジュール１１２、及び入力サイズ決定モジュール４１０を有してよい。ストリングビルダモジュール１１０は、実行モジュール１１２及び入力サイズ決定モジュール４１０へ通信上結合されてよい。実行モジュール１１２は、ストリングビルダモジュール１１０及び入力サイズ決定モジュール４１０へ通信上結合されてよい。入力サイズ決定モジュール４１０は、ストリングビルダモジュール１１０及び実行モジュール１１２へ通信上結合されてよい。ストリングビルダモジュール１１０及び実行モジュール１１２は、図１Ｂを参照して上述された。故に、それらの説明はここで繰り返されない。
【００８８】
ストリングビルダモジュール１１０は、次の要素、すなわち、印刷可能文字データ１２０、テスト入力データ１２２、及び入力モジュール４０５を有してよい。印刷可能文字データ１２０及びテスト入力データ１２２は、図１Ａ及び１Ｂを参照して上述された。故に、それらの説明はここで繰り返されない。
【００８９】
入力モジュール４０５は、テスト入力データ１２２によって記述されるテスト入力の１つ以上に含まれるインデックスの数を設定するコード及びルーチンを含んでよい。このように、入力モジュール４０５は、テスト入力データ１２２によって記述され且つ実行モジュール１１２へ供給されるテスト入力のサイズを変更してよい。
【００９０】
実行モジュール１１２は、次の要素、すなわち、インタラクションモジュール１２６、モニタモジュール１２８、バイナリモジュール１３０、及びセットデータ１３２を有してよい。インタラクションモジュール１２６、モニタモジュール１２８、バイナリモジュール１３０及びセットデータ１３２は、図１Ｂを参照して上述された。故に、それらの説明はここで繰り返されない。
【００９１】
実行モジュール１１２は、ストリングビルダモジュール１１０からテスト入力データ１２２を受けてよい。実行モジュール１１２は、テスト入力データ１２２を用いてバイナリモジュール１３０を実行し、実行後にバイナリモジュール１３０によって実行された命令をモニタし、実行された命令の数と、実行された命令の数に関連するテスト入力とを記述するセットデータ１３２を記憶することによって、セットデータ１３２を決定してよい。実行モジュール１１２は、セットデータ１３２を入力サイズ決定モジュール４１０へ供給してよい。
【００９２】
テスト入力データ１２２によって記述されるテスト入力のサイズは、入力モジュール４０５によって設定されてよい。図１Ｂを参照して上述されたように、実行モジュール１１２は、１つ以上の性能解析ツールを有してよい。いくつかの実施において、実行モジュール１１２に含まれる性能解析ツールは、テスト入力のために使用されるテスト入力データ１２２と、バイナリモジュール１３０のための入力としてテスト入力データ１２２を用いてバイナリモジュール１３０を実行することに応答して実行されるコマンドの数との整合の前に、システム４００が指定されたバイト数のデータを受けたかどうかを判定するよう構成されてよい。実験は、この問題が、テスト入力に含まれるべき有効な文字を決定することより前にテスト入力のサイズを決定することによって、解決又は軽減され得ることを示している。テスト入力のサイズが知られると、図１Ａ及び１Ｂを参照して上述された有効入力決定システム１０５は、そのサイズの空のテスト入力ストリングから開始し、一度に１つのインデックスずつテスト入力の文字を変更して、有効な入力ストリングを決定してよい。
【００９３】
入力サイズ決定モジュール４１０は、セットデータ１３２を解析し、テスト入力のサイズを記述するサイズデータ４２０を決定するよう構成されるコード及びルーチンを含んでよい。入力サイズ決定モジュール４１０は、サイズデータ４２０をストリングビルダモジュール１１０の入力モジュール４０５へ供給してよい。ストリングビルダモジュール１１０は、サイズデータ４２０に基づきテスト入力のサイズを決定してよい。このように、テスト入力のサイズは、バイナリモジュール１３０のためのテスト入力の前回のインスタンスの結果を記述するセットデータ１３２の解析に基づき、入力サイズ決定モジュール４１０によって繰り返し決定されてよい。システム４００の性能は、入力サイズ決定モジュール４１０によって提供される機能性に基づき、時間にわたって改善されてよい。
【００９４】
いくつかの実施において、有効入力決定システム１０５は、テスト入力のサイズを決定するよう構成され得る入力サイズ決定モジュール４１０を有してよい。
【００９５】
いくつかの実施において、入力サイズ決定モジュール４１０は、straceプログラムとread()システムコールとの組み合わせを含むよう構成されてよい。straceプログラムは、バイナリモジュール１３０の実行中に呼び出される如何なるシステムコールも記述するデータをモニタし、記憶するよう構成されるコード及びルーチンを含んでよい。read()システムコールを呼び出すことは、有効な入力ストリングのサイズを決定するよう解析され得るパラメータを入力サイズ決定モジュール４１０に供給してよい。read()はシステムコールであるから、入力サイズ決定モジュール４１０は、テスト入力のサイズを決定するよう解析され得るread()システムコールを呼び出すことで生じるパラメータを抽出するよう構成されるコード及びルーチンを含んでよい。このように、入力サイズ決定モジュール４１０は、バイナリモジュール１３０のためのテスト入力のサイズを記述するサイズデータ４２０をストリングビルダモジュール１１０に供給するよう構成されてよい。
【００９６】
いくつかの実施において、入力サイズ決定モジュール４１０は、テスト入力データ１２２を用いてバイナリモジュール１３０を実行し、バイナリモジュール１３０によって実行された命令の数を数え、バイナリモジュール１３０によって実行された命令を解析しながらサイズデータ４２０によって記述される有効な入力ストリングのサイズをインクリメントすることによって、サイズデータ４２０を決定するよう構成されてよい。
【００９７】
実験は、システム４００の性能を改善するよう入力サイズ決定モジュール４１０のコード及びルーチンにおいて利用され得る３つの観測結果を示している。それら３つの観測結果は、これより簡潔に説明される。
【００９８】
第１に、実験は、バイナリモジュール１３０によって実行される命令の数が、サイズデータ４２０によって記述される有効な入力ストリングのサイズの一次関数であり得ることを示している。この一次関数は“線形サイズ決定関数”と呼ばれ得る。線形サイズ決定関数は、入力サイズ決定モジュール４１０のコード及びルーチンに含まれてよい。線形サイズ決定関数は、バイナリモジュール１３０によって実行される命令の観測された数に基づき、サイズデータ４２０によって記述されるテスト入力サイズを如何にして変更すべきかを決定するために使用されてよい。例えば、テスト入力は、バイナリモジュール１３０によって実行される命令の数を線形サイズ決定関数に従わせるよう、入力サイズ決定モジュール４１０によって決定された方法で変更されてよい。
【００９９】
第２に、実験は、いくつかの場合に、バイナリモジュール１３０が、バイナリモジュール１３０のための入力としてテスト入力１２２を用いて実行されることに応答して時期尚早に終了し得ることも示している。かかる場合に、実行される命令の記録される数は、テスト入力のサイズが、入力のために割り当てられているメモリのサイズを超える場合に、減ってよい。
【０１００】
第３に、実験は、バイナリモジュール１３０によって実行される命令の数の差が、異なる条件に基づき変動し得ることも示している。例えば、実行モジュール１１２を参照して図１Ｂについて上述されたように、バイナリモジュール１３０は、バイナリモジュール１３０によって実行される命令の数のカウントの不正確さを特定するために、入力として同じテスト入力データ１２２を用いて複数回実行されてよい。いくつかの実施において、バイナリモジュール１３０によって実行される命令の数の差は、有効な入力ストリングのサイズが奇数又は偶数のいずれかであるかに基づき変動し得る。変動が、有効な入力ストリングのサイズが奇数又は偶数のいずれかであるかに関連していると知られる場合には、入力サイズ決定モジュール４１０は、（１）有効な入力ストリングのサイズが変動を生じさせる奇数又は偶数に対応する場合を特定し、（２）モニタモジュール１２８によって記録される変動に合わせて調整するようカウントを加算又は減算してよい。例えば、テスト入力のサイズは、カウントを線形サイズ決定関数に従わせるよう入力サイズ決定モジュール４１０によって変更されてよい。
【０１０１】
入力サイズ決定モジュール４１０は、変動の原因が知られていない場合に、異なる処置をとってよい。例えば、入力サイズ決定モジュール４１０は、バイナリモジュール１３０によって実行される命令の数の差が未知の条件に基づき変動し得る場合にサイズデータ４２０を決定するよう構成されるコード及びルーチンを有してよい。例えば、入力サイズ決定モジュール４１０は、セットデータ１３２において決定される変動の存在に対応する異なるサイズを決定するよう、テスト入力の異なるサイズを用いてバイナリモジュール１３０を実行してよい。このように、入力サイズ決定モジュール４１０は、変動を生じさせ得る異なるサイズデータ４２０を決定してよい。
【０１０２】
変動を生じさせるサイズが決定された後、入力サイズ決定モジュール４１０は、（１）テスト入力のサイズが変動を生じさせるサイズに対応する場合を特定し、（２）変動に合わせて調整するようモニタモジュール１２８によって記録されるカウントを加算又は減算してよい。例えば、カウントは、カウントを線形サイズ決定関数に従わせるよう、入力サイズ決定モジュール４１０によって変更されてよい。代替的に、サイズデータ４２０は、線形サイズ決定関数に更に従うカウントを生じさせるよう変更されてよい。サイズデータ４２０によって示されるサイズが大きくなるにつれて、カウントについての更なる変則性の存在は、入力サイズ決定モジュール４１０によって決定されてよい。それらの変則性が存在すると決定される場合には、入力サイズ決定モジュール４１０は、カウントを変更するよう更なる調整を行ってよい。
【０１０３】
いくつかの実施において、ストリングビルダモジュール１１０の入力モジュール４０５は、テスト入力のサイズを増大させるよう構成されるコード及びルーチンを有してよい。入力モジュール４０５は、セットデータ１３２における変化が入力サイズ決定モジュール４１０によって検出されるまで、テスト入力のサイズを増大させてよい。変化が入力サイズ決定モジュール４１０によって検出される前に、入力モジュール４０５は、夫々の繰り返しによりテスト入力のサイズを倍にしてよい。例えば、第１のテスト入力は１インデックス長であってよく、第２のテスト入力は２インデックス長であってよく、第３のテスト入力は４インデックス長であってよい。第４のテスト入力は、入力サイズ決定モジュール４１０がセットデータ１３２における変化を検出しない限りは、８インデックス長であってよい。入力サイズ決定モジュール４１０は、セットデータ１３２における変化が入力サイズ決定モジュール４１０によって検出されたかどうかの通知を与えるよう、入力モジュール４０５へ通信上結合されてよい。変化が検出された後、入力モジュール４０５は、検出された変化の後で夫々の繰り返しごとに２分の１ずつテスト入力のサイズを低減してよい。
【０１０４】
入力サイズ決定モジュール４１０は、次の要素、すなわち、セットデータ１３２、解析モジュール４１５、及びサイズデータ４２０を有してよい。セットデータ１３２は、図１Ｂを参照して上述された。故に、その説明はここで繰り返されない。図４に表されているセットデータ１３２は、セットデータ１３２の内容の例を含む。この例は、実例であって、限定でないよう意図される。サイズデータ４２０は、入力モジュール４０５を参照して上述された。故に、その説明はここで繰り返されない。
【０１０５】
解析モジュール４１５は、セットデータ１３２を解析し、線形サイズ決定関数に従うサイズデータ４２０を決定するよう構成されるコード及びルーチンを有してよい。解析モジュール４１５は、サイズデータ４２０をストリングビルダモジュール１１０の入力モジュール４０５へ供給してよい。
【０１０６】
図５Ａ、５Ｂ、５Ｃ及び５Ｄは、ここで記載される少なくとも１つの実施形態に従って配置される、未知のバイナリモジュールのための有効な入力ストリングを決定する方法５００のフロー図を例示する。方法５００は、いくつかの実施において、図１Ａ及び１Ｂの有効入力決定システム１０５、図３のシステム３００、及び／又は図４のシステム４００のようなシステムによって、全体として又は部分的に実行されてよい。例えば、図１又は３のプロセッシングデバイス１０２は、図５Ａ、５Ｂ、５Ｃ及び５Ｄの方法５００のブロックの１つ以上によって表される機能及び動作を実行するように、メモリ１０６に記憶されているコンピュータ命令を実行するようプログラムされてよい。たとえ個別のブロックとして表されているとしても、様々なブロックは、所望の実施に応じて、更なるブロックに分けられても、より少ないブロックへとまとめられても、あるいは、削除されてもよい。
【０１０７】
有効な入力ストリングは１つ以上のインデックスを含んでよい。有効な入力ストリングのインデックス部分は、ゼロベースのシステムによって記述されてよい。有効な入力ストリングの第１のインデックスは“ｉ＝０”と記述されてよい。このとき、文字“ｉ”はインデックス部分を示し、数“０”は、第１のインデックスがストリングの“０”部分にあることを示す。有効な入力ストリングの第２のインデックスは“ｉ＝１”と記述されてよく、有効な入力ストリングの第３のインデックスは“ｉ＝２”と記述されてよい。有効な入力ストリングは１つ以上のインデックスを含んでよく、夫々は、この段落において第１、第２及び第３のインデックスの記述によって確立されるパターンに従って記述されてよい。方法５００のブロック５０２、５０４、５０６、５０８、５１０、５１２、５１４、５１６、５１８、５２０及び５２２の１つ以上は、有効な入力ストリングの第１のインデックスについて実行されてよい。有効な入力ストリングが第２のインデックスを含む場合には、ブロック５２４、５２６、５２８及び５３０の１つ以上は第２のインデックスについて実行されてよい。ブロック５２４、５２６、５２８及び５３０の１つ以上は、方法５００が有効な入力ストリングの終わりを決定するまで繰り返し実行されてよい。方法５００は、方法５００が有効な入力ストリングの全てのインデックスについて有効な文字を決定した場合に、有効な入力ストリングの終わりを決定してよい。
【０１０８】
方法５００は、図５Ａのブロック５０２で開始してよい。ブロック５０２で、空のストリングの第１のインデックスについての印刷可能文字のリストは、決定されてよい。ブロック５０４で、１つの印刷可能文字は、バイナリモジュールのためのテスト入力となるよう、印刷可能文字のリストから選択されてよい。バイナリモジュールは、有効な入力が知られていない未知のバイナリモジュールであってよい。ブロック５０６で、バイナリモジュールは、選択された文字をバイナリモジュールのための入力として用いて実行されてよい。ブロック５０６でバイナリモジュールを実行することは、複数の命令がユーザ空間において実行されることを生じさせ得る。ブロック５０８で、実行された命令の数が決定されてよい。
【０１０９】
方法５００のブロック５０４、５０６及び５０８は、印刷可能文字のリストに含まれる文字の夫々がバイナリモジュールのためのテスト入力として使用されるまで繰り返されてよい。
【０１１０】
ブロック５１０で、いずれかの印刷可能文字が、ブロック５０４乃至５０８によって記載されたようにバイナリモジュールのためのテスト入力として使用されることなくブロック５０２のリストに残っているかどうかに関して、決定がなされてよい。バイナリモジュールのためのテスト入力として使用されていない印刷可能文字がブロック５０２のリストに残っていると決定される場合は、方法５００はブロック５０４へ戻ってよい。バイナリモジュールのためのテスト入力として使用されていない印刷可能文字が５０２のリストがブロック５０２のリストに残っていないと決定される場合は、方法５００は、図５Ｂに表されるブロック５１２へ進んでよい。
【０１１１】
これより図５Ｂを参照すると、方法５００はブロック５１２で続いてよい。ブロック５１２で、数及び印刷可能文字の組を記述するセットデータが記憶されてよい。数及び印刷可能文字の組は、テスト入力として使用された夫々の印刷可能文字と、ブロック５０８で印刷可能文字の夫々について実行されると決定された命令の数とを記述してよい。セットデータは、組に含まれる各印刷可能文字が、その印刷可能文字がバイナリモジュールのためのテスト入力として使用された場合に実行された命令の数と関連付けられ得るように、構成されてよい。ブロック５１４で、最頻値は、セットデータに含まれる数の組について決定されてよい。ブロック５１６で、閾範囲は、試験定数に基づき決定されてよい。ブロック５１８で、閾範囲の外にある数に関連付けられている如何なる印刷可能文字も、有効な入力ストリングの現在のインデックスについての有効な文字として識別されてよい。ブロック５１８で識別された１つ以上の有効な文字を記述する有効文字データは、メモリに記憶されてよい。ブロック５１８で識別され、有効文字データによって記述される有効な文字の１つ以上は、有効な入力ストリングの現在のインデックスについての有効な文字として使用されてよい。
【０１１２】
ブロック５２０で、印刷可能文字がブロック５１８で閾範囲の外にあると決定されたかどうかに関して、決定がなされてよい。印刷可能文字がブロック５１８で閾範囲の外にあると決定されなかった場合は、有効な文字はブロック５１８で識別されておらず、方法５００は、バイナリモジュールのための有効な入力ストリングの終わりを特定してよい。少なくとも１つの印刷可能文字がブロック５１８で閾範囲の外にあると決定された場合は、少なくとも１つの有効な文字がブロック５１８で識別されており、方法５００は、図５Ｃに表されているブロック５２２へ進んでよい。
【０１１３】
これより図５Ｃを参照すると、方法５００はブロック５２２で続いてよい。ブロック５２２で、方法５００は、ブロック５１８で識別された１つ以上の有効な文字について記憶されている有効文字データから有効な文字の１つを選択してよい。ブロック５２４で、方法５００は、ブロック５０２で決定された印刷可能文字のリストから印刷可能文字の１つを選択してよい。ブロック５２６で、方法５００は、バイナリモジュールのための連結入力を形成するよう、ブロック５２２の選択された有効な文字と、ブロック５２４の選択された印刷可能文字とを連結してよい。連結入力は、ブロック５２２の有効な文字が前回のインデックスのために使用され、ブロック５２４の印刷可能文字が現在のインデックスのために使用されるように、構成されてよい。いくつかの実施において、連結入力は、有効な文字が前回のインデックスについて有効であると既に決定されており、一方、印刷可能文字が現在のインデックスについて有効であるかどうかは決定されていないので、このようにして構成されてよい。
【０１１４】
ブロック５２８で、方法５００は、連結入力を用いてバイナリモジュールを実行してよい。ブロック５２８は、連結入力を用いてバイナリモジュールを実行することに応答して実行される命令の数をモニタすることを含んでよい。ブロック５２８は、連結入力と、連結入力を用いてバイナリモジュールを実行することに応答して実行される命令の数とを記述するセットデータを記憶することを更に含んでよい。
【０１１５】
ブロック５３０で、いずれかの印刷可能文字が、現在のインデックス部分について連結入力の要素として使用されることなくブロック５０２のリストに残っているかどうかに関して、決定がなされてよい。現在のインデックス部分について連結入力の要素として使用されていない印刷可能文字がブロック５０２のリストに残っていると決定される場合は、方法５００はブロック５２４へ戻ってよい。現在のインデックス部分について連結入力の要素として使用されていない印刷可能文字がブロック５０２のリストに残っていないと決定する場合は、方法５００は、図５Ｄに表されているブロック５３２へ進んでよい。
【０１１６】
これより図５Ｄを参照すると、方法５００はブロック５３２で続いてよい。ブロック５３２で、方法５００は、閾範囲の外にある実行された命令の数を生じさせた、ブロック５２８のセットデータに含まれる如何なる印刷可能文字も識別してよい。方法５００は、ブロック５３２で閾範囲外の数に関連付けられている如何なる印刷可能文字も、現在のインデックスについての有効な文字であると決定すること含んでよい。方法５００は、現在のインデックスについての有効な文字を記述する有効文字データを記憶することを含んでよい。
【０１１７】
ブロック５３４で、印刷可能文字がブロック５３２で識別されたかどうかに関して、決定がなされてよい。印刷可能文字がブロック５３２で閾範囲の外にあると決定されなかった場合は、有効な文字はブロック５３２で識別されておらず、方法５００は、バイナリモジュールのための有効な入力ストリングの終わりを特定する。少なくとも１つの印刷可能文字がブロック５３２で閾範囲の外にあると決定された場合は、少なくとも１つの印刷可能文字がブロック５３２で特定されており、方法５００はブロック５３６へ進んでよい。ブロック５３６で、方法５００は、有効な入力ストリングが決定されるまで、ブロック５２２、５２４、５２６、５２８、５３０及び５３２の１つ以上を繰り返してよい。
【０１１８】
ここで記載される実施形態は、以下で更に詳細に論じられるように、様々なコンピュータハードウェア又はソフトウェアモジュールを含む特別目的又は汎用のコンピュータの使用を含んでよい。
【０１１９】
ここで記載される実施形態は、コンピュータ実行可能命令又はデータ構造を搬送する又は記憶しているコンピュータ可読媒体を用いて実施されてよい。かかるコンピュータ可読媒体は、汎用又は特別目的のコンピュータによってアクセスされ得る如何なる利用可能な媒体であってもよい。一例として、制限なしに、かかるコンピュータ可読媒体は、ランダムアクセスメモリ（ＲＡＭ）、読出専用メモリ（ＲＯＭ）、電気的消去可能なプログラム可能読出専用メモリ（ＥＥＰＲＯＭ）、コンパクトディスク型読出専用メモリ（ＣＤ−ＲＯＭ）若しくは他の光ディスクストレージ、磁気ディスクストレージ若しくは他の磁気ストレージデバイス、フラッシュメモリデバイス（例えば、ソリッドステートメモリデバイス）、又はコンピュータ実行可能命令若しくはデータ構造の形で所望のプログラムコードを搬送若しくは記憶するために使用されてよく且つ汎用若しくは特別目的のコンピュータによってアクセスされ得る如何なる他の記憶媒体も含む非一時的なコンピュータ可読記憶媒体を含んでよい。上記の組み合わせも、コンピュータ可読媒体の適用範囲内に含まれてよい。
【０１２０】
コンピュータ実行可能命令は、例えば、汎用のコンピュータ、特別目的のコンピュータ、又は特別目的のプロセッシングデバイス（例えば、１つ以上のプロセッサ）に、ある機能又は機能群を実行させる命令及びデータを有する。たとえ対象が構造的な特徴及び／又は方法論的な動作に特有の言語で記載されているとしても、添付の特許請求の範囲で定義されている対象は、必ずしも、上記の特定の特徴又は動作に制限されないことが理解されるべきである。むしろ、上記の特定の特徴及び動作は、特許請求の範囲を実施する形態の例として開示されている。
【０１２１】
ここで使用されるように、語“モジュール”又は“コンポーネント”は、コンピュータシステムの汎用のハードウェア（例えば、コンピュータ可読媒体、プロセッシングデバイス、など）において記憶及び／又は実行され得るモジュール若しくはコンポーネントの動作及び／又はソフトウェアオブジェクト若しくはソフトウェアルーチンを実行するよう構成される特定のハードウェア実施に言及してよい。いくつかの実施形態では、ここで記載される異なるコンポーネント、モジュール、エンジン、及びサービスは、コンピュータシステムにおいて（例えば、別個のスレッドとして）実行するオブジェクト又はプロセスとして実施されてよい。ここで記載されるシステム及び方法のいくつかは、概して、（汎用のハードウェアにおいて記憶及び／又は実行される）ソフトウェアで実施されるものとして記載されているが、特定のハードウェア実施又はソフトウェアと特定のハードウェア実施との組み合わせも可能であり、考えられている。本明細書において、“コンピュータエンティティ”は、ここで予め定義されている如何なるコンピュータシステムであっても、あるいは、コンピュータシステムで実行される如何なるモジュール又はモジュールの組み合わせであってもよい。
【０１２２】
ここで挙げられている全ての例及び条件付き語は、当該技術の促進に本発明者によって寄与される概念及び発明を読者が理解するのを助ける教育的な目的を意図されており、そのような具体的に挙げられている例及び条件に制限されないものとして解釈されるべきである。本発明の実施形態は詳細に記載されてきたが、様々な変更、置換及び代替が、本発明の主旨及び適用範囲から外れることなしにそれらに対してなされてよいことが理解されるべきである。
【０１２３】
上記の実施形態に加えて、以下の付記を開示する。
（付記１）
未知の有効な入力を有するバイナリモジュールのための１つ以上のテスト入力として印刷可能文字の組を選択し、
前記バイナリモジュールのための前記１つ以上のテスト入力として前記印刷可能文字の組を用いて前記バイナリモジュールを実行し、
前記印刷可能文字の組に含まれる印刷可能文字の夫々について、前記印刷可能文字の組を用いて実行されることに応答して前記バイナリモジュールによって実行される命令の数を決定し、
１つ以上の前記印刷可能文字の夫々について実行される前記命令の数に関連する前記１つ以上の印刷可能文字を含むセットデータを生成し、
前記１つ以上の印刷可能文字に関連する前記命令の数と閾範囲との比較に基づき、前記バイナリモジュールのための１つ以上の有効な入力として１つ以上の印刷可能文字を識別するよう、前記セットデータを解析する
ことを有する方法。
（付記２）
前記セットデータに含まれる前記命令の数について最頻値を決定し、該最頻値を用いて前記閾範囲を決定する
ことを更に有する付記１に記載の方法。
（付記３）
前記閾範囲は、上限及び下限を有し、当該方法は、
指定される試験定数と前記最頻値とを合計することによって、前記閾範囲の前記上限を決定し、
前記最頻値を前記指定される試験定数から減じることによって、前記閾範囲の前記下限を決定する
ことを更に有する、付記２に記載の方法。
（付記４）
前記解析は、前記バイナリモジュールのための前記１つ以上の有効な入力に含まれる印刷可能文字の１つ以上のタイプを識別し、該印刷可能文字の１つ以上のタイプが前記バイナリモジュールにとって有効なタイプであると決定することを有する、
付記１に記載の方法。
（付記５）
前記テスト入力のうちの１つは、前記バイナリモジュールのための当該テスト入力としてコマンド及び引数を含み、
前記解析は、前記コマンド及び前記引数を含む前記テスト入力が前記バイナリモジュールのための前記１つ以上の有効な入力に含まれるかどうかを判断することを有する、
付記１に記載の方法。
（付記６）
前記解析は、前記バイナリモジュールのための最大入力サイズを決定することを有する、
付記１に記載の方法。
（付記７）
前記最大入力サイズは、バッファオーバーフローイベントを引き起こす、
付記６に記載の方法。
（付記８）
前記バイナリモジュールにとっての例外に関連する１つ以上の入力特性を決定するよう前記１つ以上の有効な入力をファジングする
ことを更に有する付記１に記載の方法。
（付記９）
前記バイナリモジュールのための１つ以上の有効な入力を決定するよう、ホワイトボックス・ファザーに前記１つ以上の有効な入力をシードする
ことを更に有する付記１に記載の方法。
（付記１０）
前記バイナリモジュールのための２つ以上の有効な入力を含むストリングを構築する
ことを更に有する付記１に記載の方法。
（付記１１）
未知の有効な入力を有するバイナリモジュールのための１つ以上のテスト入力として印刷可能文字の組を選択し、
前記バイナリモジュールのための前記１つ以上のテスト入力として前記印刷可能文字の組を用いて前記バイナリモジュールを実行し、
前記印刷可能文字の組に含まれる印刷可能文字の夫々について、前記印刷可能文字の組を用いて実行されることに応答して前記バイナリモジュールによって実行される命令の数を決定し、
１つ以上の前記印刷可能文字の夫々について実行される前記命令の数に関連する前記１つ以上の印刷可能文字を含むセットデータを生成し、
前記１つ以上の印刷可能文字に関連する前記命令の数と閾範囲との比較に基づき、前記バイナリモジュールのための１つ以上の有効な入力として１つ以上の印刷可能文字を識別するよう、前記セットデータを解析する
動作の実行又はその制御を行うようプロセッシングデバイスによって実行可能であるコンピュータ命令を記憶している非一時的なコンピュータ可読媒体。
（付記１２）
前記動作は、前記セットデータに含まれる前記命令の数について最頻値を決定し、該最頻値を用いて前記閾範囲を決定することを更に有する、
付記１１に記載の非一時的なコンピュータ可読媒体。
（付記１３）
前記閾範囲は、上限及び下限を有し、前記動作は、
指定される試験定数と前記最頻値とを合計することによって、前記閾範囲の前記上限を決定し、
前記最頻値を前記指定される試験定数から減じることによって、前記閾範囲の前記下限を決定する
ことを更に有する、付記１２に記載の非一時的なコンピュータ可読媒体。
（付記１４）
前記解析は、前記バイナリモジュールのための前記１つ以上の有効な入力に含まれる印刷可能文字の１つ以上のタイプを識別し、該印刷可能文字の１つ以上のタイプが前記バイナリモジュールにとって有効なタイプであると決定することを有する、
付記１１に記載の非一時的なコンピュータ可読媒体。
（付記１５）
前記テスト入力のうちの１つは、前記バイナリモジュールのための当該テスト入力としてコマンド及び引数を含み、
前記解析は、前記コマンド及び前記引数を含む前記テスト入力が前記バイナリモジュールのための前記１つ以上の有効な入力に含まれるかどうかを判断することを有する、
付記１１に記載の非一時的なコンピュータ可読媒体。
（付記１６）
前記解析は、前記バイナリモジュールのための最大入力サイズを決定することを有する、
付記１１に記載の非一時的なコンピュータ可読媒体。
（付記１７）
前記最大入力サイズは、バッファオーバーフローイベントを引き起こす、
付記１６に記載の非一時的なコンピュータ可読媒体。
（付記１８）
前記動作は、前記バイナリモジュールにとっての例外に関連する１つ以上の入力特性を決定するよう前記１つ以上の有効な入力をファジングすることを更に有する
付記１１に記載の非一時的なコンピュータ可読媒体。
（付記１９）
前記動作は、前記バイナリモジュールのための１つ以上の有効な入力を決定するよう、ホワイトボックス・ファザーに前記１つ以上の有効な入力をシードすることを更に有する、
付記１１に記載の非一時的なコンピュータ可読媒体。
（付記２０）
前記動作は、前記バイナリモジュールのための２つ以上の有効な入力を含むストリングを構築することを更に有する、
付記１１に記載の非一時的なコンピュータ可読媒体。
【符号の説明】
【０１２４】
１０２          プロセッシングデバイス
１０５          有効入力決定システム
１０６          メモリ
１１０          ストリングビルダモジュール
１１２          実行モジュール
１１４          フィルタモジュール
１２０          印刷可能文字データ
１２２          テスト入力データ
１２６          インタラクションモジュール
１２８          モニタモジュール
１３０          バイナリモジュール
１３２          セットデータ
１３４          モードモジュール
１３６          レンジモジュール
１３８          有効文字データ
１４０          有効入力データ
３００，４００  システム
３０８          システムデータ
４０５          入力モジュール
４１０          入力サイズ決定モジュール
４１５          解析モジュール
４２０          サイズデータ
５００          方法
【図１Ａ】
0006544253.tif 000002
【図１Ｂ】
0006544253.tif 000003
【図２Ａ】
0006544253.tif 000004
【図２Ｂ】
0006544253.tif 000005
【図３】
0006544253.tif 000006
【図４】
0006544253.tif 000007
【図５Ａ】
0006544253.tif 000008
【図５Ｂ】
0006544253.tif 000009
【図５Ｃ】
0006544253.tif 000010
【図５Ｄ】
0006544253.tif 000011