図面 (/)

技術 未知のバイナリプログラムに対する有効な入力の決定

出願人 富士通株式会社
発明者 ムルティー・プラヴィーンコポス・ボグダン
出願日 2016年3月29日 (5年8ヶ月経過) 出願番号 2016-065195
公開日 2016年12月22日 (5年0ヶ月経過) 公開番号 2016-218997
状態 特許登録済
技術分野 デバッグ/監視
主要キーワード テスト設備 コンピュータエンティティ ユニットテスト 縦型探索 ホワイトボックス 目的処理 ストリング表現 例示的形態
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2016年12月22日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (7)

課題

未知バイナリプログラムに対する有効な入力を決定する方法が提供される。

解決手段

当該方法は、未知のバイナリプログラムに対する複数の入力シーケンスであって、それぞれ2以上の異なる入力を有する、複数の入力シーケンスを得るステップ、を有する。入力シーケンスの入力は、未知のバイナリプログラムの有効な入力であっても良い。方法は、各々の入力シーケンスについて別個に、前記未知のバイナリプログラムの計装バージョンを実行するステップ、を更に有しても良い。未知のバイナリプログラムの計装バージョンの各々の実行について、未知のバイナリプログラムの計装バージョンの実行により生成される実行トレースを記録することにより、実行トレースセットが生成されても良い。方法は、前記実行トレースセットを比較するステップと、実行トレースセットの比較に基づき、前記入シーケンスのうちのどれを、前記未知のバイナリプログラムが有効であるとして受け入れるかを決定するステップと、を更に有しても良い。

概要

背景

バイナリプログラムの効率的なテストは、どの入力がバイナリプログラムにとって有効かという知識により向上され得る。バイナリプログラムは、人間がテキストとして解釈できるコード及びルーチンを有し得る。しかしながら、バイナリプログラムのコード及びルーチンに含まれるテキストは、人間には読めない。バイナリプログラムのコード及びルーチンは人間が読めないので、バイナリプログラムの人間のテスターは、コード及びルーチンを見直すことによりバイナリプログラムの有効な入力を決定することができない。その結果、人間のテスターは、どの入力がバイナリプログラムにとって有効かを決定するために、バイナリプログラムに関連する仕様書文書、又はソースコードを見直す場合がある。次に、これらの有効な入力は、バイナリプログラムのより効率的なテストを達成するために用いることができる。

概要

未知のバイナリプログラムに対する有効な入力を決定する方法が提供される。 当該方法は、未知のバイナリプログラムに対する複数の入力シーケンスであって、それぞれ2以上の異なる入力を有する、複数の入力シーケンスを得るステップ、を有する。入力シーケンスの入力は、未知のバイナリプログラムの有効な入力であっても良い。方法は、各々の入力シーケンスについて別個に、前記未知のバイナリプログラムの計装バージョンを実行するステップ、を更に有しても良い。未知のバイナリプログラムの計装バージョンの各々の実行について、未知のバイナリプログラムの計装バージョンの実行により生成される実行トレースを記録することにより、実行トレースセットが生成されても良い。方法は、前記実行トレースセットを比較するステップと、実行トレースセットの比較に基づき、前記入シーケンスのうちのどれを、前記未知のバイナリプログラムが有効であるとして受け入れるかを決定するステップと、を更に有しても良い。

目的

しかしながら、未知のバイナリプログラム102に対する入力を決定したことは、未知のバイナリプログラム102に入力を提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

未知バイナリプログラムに対する有効な入力シーケンスを決定する方法であって、前記方法は、未知のバイナリプログラムに対する複数の入力シーケンスを得るステップであって、前記入シーケンスの各々は、2以上の異なる入力を有し、前記入力シーケンスの入力は、前記未知のバイナリプログラムに対して有効な入力として決定される、ステップと、各々の入力シーケンスについて別個に前記未知のバイナリプログラムの計装バージョンを実行するステップであって、前記未知のバイナリプログラムの前記計装バージョンの各々の実行は、前記未知のバイナリプログラムの前記計装バージョンへの入力として前記入力シーケンスのうちの1つを用いる、ステップと、前記未知のバイナリプログラムの前記計装バージョンの各々の実行について、前記未知のバイナリプログラムの前記計装バージョンの前記実行により生成される実行トレースを記録することにより、実行トレースセットを生成するステップと、前記実行トレースセットを比較するステップと、前記実行トレースセットの比較に基づき、前記入力シーケンスのうちのどれを前記未知のバイナリプログラムが有効として受け入れるかを決定するステップと、を有する方法。

請求項2

前記入力は、前記未知のバイナリプログラムに対して有効であると決定されたコマンドと、前記コマンドに関連する引数と、を有し、前記引数も、前記未知のバイナリプログラムに対して有効であると決定される、請求項1に記載の方法。

請求項3

前記実行トレースセットを生成するステップは、前記実行トレースセットに含めるために、前記未知のバイナリプログラムの前記計装バージョンの各々の実行について、前記実行トレースの一部を選択するステップであって、前記実行トレースセットのために選択された前記実行トレースの一部は、前記入力シーケンスの最後の入力が前記未知のバイナリプログラムに提供された後に生成された実行トレースである、ステップを含む、請求項1に記載の方法。

請求項4

前記実行トレースセットに含めるために前記実行トレースの一部を選択するステップは、入力を有しないで前記未知のバイナリプログラムの前記計装バージョンを実行するステップと、入力を有しない前記実行の終わりに、前記未知のバイナリプログラムの前記計装バージョンの実行により生成された複数の実行トレースを決定するステップと、前記決定した複数の実行トレースをパーティション実行トレースとして設定するステップと、前記パーティション実行トレースの最後から2番目の発生と最後の発生との間に生じる実行トレースの一部に基づき、前記入力シーケンスを用いて前記未知のバイナリプログラムの前記計装バージョンの実行中に生成された実行トレースの一部を選択するステップと、を有する、請求項3に記載の方法。

請求項5

前記実行トレースセットの各々について制御フローグラフを生成するステップ、を更に有し、前記実行トレースセットを比較するステップは、前記制御フローグラフの各々についてストリング表現を生成するステップと、前記ストリング表現を比較するステップと、を有する、請求項1に記載の方法。

請求項6

各々の制御フローグラフについて前記ストリング表現を生成するステップは、縦型探索アルゴリズム又は横型探索アルゴリズムを実施するステップを有する、請求項5に記載の方法。

請求項7

前記実行トレースセットのうちの1つのセットの中の実行トレースは、前記未知のバイナリプログラムの前記計装バージョンにより出力され且つ前記未知のバイナリプログラムの非計装バージョンにより出力されない、前記未知のバイナリプログラムの中で実行される直線的命令セットに関連するメモリアドレスを表す、請求項1に記載の方法。

請求項8

各々の入力シーケンスの中の最後の入力は同じであり、前記複数の入力シーケンスは入力シーケンスセットであり、前記方法は、複数の他の入力シーケンスセットについて請求項1に記載の方法を繰り返すステップ、を更に有し、前記他の入力シーケンスセットのうちの各々のセットの各々の入力シーケンスの最後の入力は、同じであり、各々の入力シーケンスセットの最後の入力は、他の入力シーケンスセットの最後の入力と異なる、請求項7に記載の方法。

請求項9

前記実行トレースセットの比較が、前記実行トレースセットは同じであると示すとき、前記入力シーケンスのいずれも、前記未知のバイナリプログラムにより受け入れられないと決定される、請求項1に記載の方法。

請求項10

前記実行トレースセットの比較が、前記実行トレースセットのうちの1つが前記実行トレースセットのうちの同じである少なくとも別の2つと異なることを示すとき、前記実行トレースセットのうちの該1つに対応する入力シーケンスは、前記未知のバイナリプログラムにより受け入れられると決定される、請求項1に記載の方法。

請求項11

命令を含む1又は複数の非一時的コンピュータ可読媒体であって、前記命令は、1又は複数のプロセッサにより実行されると、未知のバイナリプログラムに対する有効な入力シーケンスを決定する工程を実行し、前記工程は、未知のバイナリプログラムに対する複数の入力シーケンスを得るステップであって、前記入力シーケンスの各々は、2以上の異なる入力を有し、前記入力シーケンスの入力は、前記未知のバイナリプログラムに対して有効な入力として決定される、ステップと、各々の入力シーケンスについて別個に前記未知のバイナリプログラムの計装バージョンを実行するステップであって、前記未知のバイナリプログラムの前記計装バージョンの各々の実行は、前記未知のバイナリプログラムの前記計装バージョンへの入力として前記入力シーケンスのうちの1つを用いる、ステップと、前記未知のバイナリプログラムの前記計装バージョンの各々の実行について、前記未知のバイナリプログラムの前記計装バージョンの前記実行により生成される実行トレースを記録することにより、実行トレースセットを生成するステップと、前記実行トレースセットを比較するステップと、前記実行トレースセットの比較に基づき、前記入力シーケンスのうちのどれを前記未知のバイナリプログラムが有効として受け入れるかを決定するステップと、を有する、1又は複数の非一時的コンピュータ可読媒体。

請求項12

前記入力は、前記未知のバイナリプログラムにより有効であると決定されたコマンドと、前記コマンドに関連する引数と、を有し、前記引数も前記未知のバイナリプログラムにとって有効であると決定される、請求項11に記載の1又は複数の非一時的コンピュータ可読媒体。

請求項13

前記実行トレースセットを生成するステップは、前記実行トレースセットに含めるために、前記未知のバイナリプログラムの前記パーティショニング済みバージョンの各々の実行について、前記実行トレースの一部を選択するステップであって、前記実行トレースセットのために選択された前記実行トレースの一部は、前記入力シーケンスの最後の入力が前記未知のバイナリプログラムに提供された後に生成された実行トレースである、ステップ、を更に有する、請求項11に記載の1又は複数の非一時的コンピュータ可読媒体。

請求項14

前記実行トレースセットに含めるために前記実行トレースの一部を選択するステップは、入力を有しないで前記未知のバイナリプログラムの前記計装バージョンを実行するステップと、入力を有しない前記実行の終わりに、前記未知のバイナリプログラムの前記計装バージョンの実行により生成された複数の実行トレースを決定するステップと、前記決定した複数の実行トレースをパーティション実行トレースとして設定するステップと、前記パーティション実行トレースの最後から2番目の発生と最後の発生との間に生じる実行トレースの一部に基づき、前記入力シーケンスを用いて前記未知のバイナリプログラムの前記計装バージョンの実行中に生成された実行トレースの一部を選択するステップと、を更に有する、請求項13に記載の1又は複数の非一時的コンピュータ可読媒体。

請求項15

前記工程は、前記実行トレースセットの各々について制御フローグラフを生成するステップ、を更に有し、前記実行トレースセットを比較するステップは、前記制御フローグラフの各々についてストリング表現を生成するステップと、前記ストリング表現を比較するステップと、を有する、請求項11に記載の1又は複数の非一時的コンピュータ可読媒体。

請求項16

各々の制御フローグラフについて前記ストリング表現を生成するステップは、縦型探索アルゴリズム又は横型探索アルゴリズムを実施するステップを有する、請求項15に記載の1又は複数の非一時的コンピュータ可読媒体。

請求項17

前記実行トレースセットのうちの1つのセットの中の実行トレースは、前記未知のバイナリプログラムの前記計装バージョンにより出力され且つ前記未知のバイナリプログラムの非計装バージョンにより出力されない、前記未知のバイナリプログラムの中で実行される直線的命令セットに関連するメモリアドレスを表す、請求項11に記載の1又は複数の非一時的コンピュータ可読媒体。

請求項18

各々の入力シーケンスの中の最後の入力は同じであり、前記複数の入力シーケンスは入力シーケンスセットであり、前記工程は、複数の他の入力シーケンスセットについて請求項11に記載の工程を繰り返すステップ、を更に有し、前記他の入力シーケンスセットのうちの各々のセットの各々の入力シーケンスの最後の入力は、同じであり、各々の入力シーケンスセットの最後の入力は、他の入力シーケンスセットの最後の入力と異なる、請求項17に記載の1又は複数の非一時的コンピュータ可読媒体。

請求項19

前記実行トレースセットの比較が、前記実行トレースセットは同じであると示すとき、前記入力シーケンスのいずれも、前記未知のバイナリプログラムにより受け入れられないと決定される、請求項11に記載の1又は複数の非一時的コンピュータ可読媒体。

請求項20

前記実行トレースセットの比較が、前記実行トレースセットのうちの1つが前記実行トレースセットのうちの同じである少なくとも別の2つと異なることを示すとき、前記実行トレースセットのうちの該1つに対応する入力シーケンスは、前記未知のバイナリプログラムにより受け入れられると決定される、請求項11に記載の1又は複数の非一時的コンピュータ可読媒体。

技術分野

0001

本願明細書で議論する実施形態は、未知バイナリプログラムに対する有効な入力の決定に関する。

背景技術

0002

バイナリプログラムの効率的なテストは、どの入力がバイナリプログラムにとって有効かという知識により向上され得る。バイナリプログラムは、人間がテキストとして解釈できるコード及びルーチンを有し得る。しかしながら、バイナリプログラムのコード及びルーチンに含まれるテキストは、人間には読めない。バイナリプログラムのコード及びルーチンは人間が読めないので、バイナリプログラムの人間のテスターは、コード及びルーチンを見直すことによりバイナリプログラムの有効な入力を決定することができない。その結果、人間のテスターは、どの入力がバイナリプログラムにとって有効かを決定するために、バイナリプログラムに関連する仕様書文書、又はソースコードを見直す場合がある。次に、これらの有効な入力は、バイナリプログラムのより効率的なテストを達成するために用いることができる。

0003

一実施形態の一態様によると、未知のバイナリプログラムに対する有効な入力を決定する方法が提供される。方法は、未知のバイナリプログラムのための複数の入力シーケンスを得るステップを有する。入力シーケンスの各々は、2以上の異なる入力を有しても良い。入力は、未知のバイナリプログラムの有効な入力として予め決定されても良い。方法は、各々の入力シーケンスについて別個に、前記未知のバイナリプログラムの計装バージョンを実行するステップ、を更に有する。未知のバイナリプログラムの計装バージョンの各々の実行は、入力シーケンスのうちの1つを、未知のバイナリプログラムの計装バージョンへの入力として用いても良い。

0004

未知のバイナリプログラムの計装バージョンの各々の実行について、未知のバイナリプログラムの計装バージョンの実行により生成される実行トレースを記録することにより、実行トレースセットが生成されても良い。方法は、前記実行トレースセットを比較するステップと、実行トレースセットの比較に基づき、前記入シーケンスのうちのどれを、前記未知のバイナリプログラムが有効であるとして受け入れるかを決定するステップと、も有しても良い。

0005

実施形態の目的及び利点が理解され、少なくとも特に特許請求の範囲で指摘された要素、特徴及び組合せを用いて達成されるだろう。

0006

上述の全体的説明及び以下の詳細な説明の両方は、例示及び説明のためであり、本開示の範囲を限定しないことが理解される。

図面の簡単な説明

0007

例示的な実施形態は、添付の図面を用いて、更なる特異性及び詳細事項と共に記載され説明される。
例示的な入力シーケンス決定処理を示す。
制御フローグラフ構築する例示的な方法のフローチャートである。
例示的な制御フローグラフ及び制御フローグラフの例示的なストリング表現を示す。
例示的な入力決定処理を示す。
例示的な入力決定システムブロック図である。
未知のバイナリプログラムの有効な入力シーケンスを決定する例示的な方法のフローチャートである。

実施例

0008

未知のバイナリプログラムに対する有効な入力シーケンスを決定するための許容可能な方法は、種々の要素を含み得る。1つの要素は、未知のバイナリプログラムに含まれるコード及びルーチン(デッドコードを除く)の高い割合をカバーすることを含み得る。例えば、未知のバイナリプログラムをテストするために選択される1又は複数のテスト入力又は入力シーケンスは、未知のバイナリプログラムのコード及びルーチンの100パーセント又は100パーセント近くをカバーし得る(例えば、デッドコード及びルーチンを除いて、バイナリプログラムの90パーセント乃至100パーセント)。幾つかの現在の方法は、未知のバイナリプログラムをテストするためにランダムテスト入力の生成に頼っている。残念ながら、未知のバイナリプログラムをテストするためにランダムテスト入力の生成を含むテスト方法は、未知のバイナリプログラムのコード及びルーチンの高い割合を常にカバーすることができないことがある。なぜなら、ランダムに生成されたテキスト入力は、未知のバイナリプログラムのコード及びルーチンの高い割合を常にカバーするという目的とは本質的に矛盾し得るからである。その結果、幾つかの既存の方法は、バイナリプログラムのコ—ド及びルーチンの高い割合を常にカバーすることができない。したがって、これらの方法は受け入れ難い。

0009

未知のバイナリプログラムの有効な入力シーケンスを決定するための許容可能な方法の別の要素は、未知のバイナリプログラムに関連する仕様書、文書又はソースコードを有しないで効率的に実装可能な能力を含み得る。この要件は、コンピュータシステムにとってソフトウェアの中の脆弱性を自動的に決定することが有益である、自律ソフトウェアセキュリティの分野で有益であり得る。幾つかの状況では、未知のバイナリプログラムは、未知のバイナリプログラムの人間のテスターに利用可能であるが、未知のバイナリプログラムに関連する仕様書、文書又はソースコードは利用可能ではないことがある。幾つかの既存の方法は、未知のバイナリプログラムに対する有効な入力を決定しようとする。しかしながら、これらの方法は、ランダムに生成されたテスト入力に頼り、又は他の欠点を有する。

0010

未知のバイナリプログラムに対する有効な入力シーケンスを決定するための更に別の要素は、プラットフォーム独立性を有し得る。プラットフォーム独立性は、他の利点を提供すると共に、方法の移植性を有利に向上できる。

0011

現在、上述の要素を含む、未知のバイナリプログラムに対する有効な入力シーケンスを決定するための方法は存在しない。種々の方法が、未知のバイナリプログラムに対する有効な入力を決定するために用いられる。しかしながら、これらの方法のいずれも、未知のバイナリプログラムに対する有効な入力シーケンスを決定する許容可能な方法の上述の要素を全く又はその一部でさえ提供しない。

0012

1つのこのような方法は、「シンボル実行」として参照され得る。シンボル実行アプローチは、場合によってはプログラムのクラッシュを含む種々の実行経路に沿ってプログラムを駆動し得る、未知のバイナリプログラムに対する入力を決定するステップを含む。このアプローチは、幾つかの独立した事例で成功し得る。しかしながら、シンボル実行アプローチに関連する1つの欠点は、未知のバイナリプログラムに関連するソースファイルの使用である。幾つかの事例では、ソースファイルは利用できない場合がある。その結果、シンボル実行アプローチの実施は、これらの事例では可能でない場合がある。他の欠点は、シンボル実行アプローチが良好にスケーリングされず、したがって多くの共通シナリオで動作しないことであり得る。例えば、シンボル実行アプローチは、浮動小数点演算を含む又はプログラムの実行中に集められた入力に対する非線形制約を含むプログラムと共に動作する知られている問題を有する。少なくともこれらの理由から、シンボル実行アプローチは、未知のバイナリプログラムに対する有効な入力を決定する許容可能な方法ではない。

0013

別の方法は、「ブラックボックスファジング」として知られる。このアプローチは、ストリングの選択、及び該ストリングのランダムな変更、を含み得る。ストリングは、各々の変更の後に、入力として未知のバイナリプログラムに供給され得る。このアプローチは所与の十分な時間動作するが、ブラックボックスファジングにより生成された入力の大部分は無効な入力である。これは、追加の有効な入力を変化させ及び識別するために有効な入力が必要なので、問題である。ブラックボックスファジングに関連する更なる問題は、このアプローチがランダム入力に頼っているため、ブラックボックスファジングを実施した結果が高いカバレッジを達成するか否かが分からないので、未知のバイナリプログラムの高いカバレッジを保証できないことである。

0014

別の方法は、「ホワイトボックスファジング」として知られる。ホワイトボックスファジングアプローチは、ブラックボックスファジングと類似するが、テスト入力を生成するために分析され得るシンボル制約を集めるために、有効な入力が使用される点が異なる。ホワイトボックスファジングアプローチは、ランダムに届けられたのではない少なくとも幾つかの入力を含むので、ブラックボックスファジングより改善されたと考えられる。しかしながら、ホワイトボックスアプローチは、テスト入力を決定するために実施される前に、前提条件として有効な入力を必要とする。幾つかの例では、有効な入力は、ホワイトボックスファジングアプローチのシードとして利用できない。この理由から、単独で実施されるホワイトボックスファジングアプローチは、未知のバイナリプログラムに対する有効な入力を決定する問題を解決できない。

0015

別の方法は、プログラムのコードがユニットに分割され体系的にテストされる「ユニットテスト」として知られている。幾つかの例ではユニットテストはバイナリプログラムの高いカバレッジテストを達成できるが、このアプローチは、常に、ソースファイル又はバイナリプログラムの仕様書のようなバイナリプログラムに関連する他の文書を必要とする。この情報無しでは、ユニットテストは実施できない。したがって、ユニットテストアプローチは、ソースファイル又は何らかの他の文書を必要とするので、未知のバイナリプログラムに対する有効な入力を決定する問題を解決できない。ユニットテストに関連する別の欠点は、プラットフォーム依存性である。ユニットテストアプローチは、低速且つ高価であるとも考えられる。

0016

別の方法は、「仕様に基づくテスト」として知られる。しかしながら、名称が意味するように、仕様に基づくテストアプローチは、常に、ソースファイル又は未知のバイナリプログラムに関連する他の文書を必要とする。したがって、このアプローチは、ソースファイル又は何らかの他の文書を必要とするので、未知のバイナリプログラムに対する有効な入力を決定する問題を解決できない。ユニットテストと同様に、仕様に基づくテストアプローチは、プラットフォーム依存であり、低速且つ高価であると考えられる。

0017

他の方法は、「リバースコードエンジニアリング」を含み得る。これらのアプローチは、「情報交換分析」アプローチ、「分解」アプローチ、及び「デコンパイル」アプローチを含み得る。情報交換分析アプローチは、未知のバイナリプログラムにより情報が交換されない場合、効率的ではないことがある。したがって、この理由から、このアプローチは、限られ許容可能ではない。分解アプローチは、生のアセンブリコードの静的又は動的分析に頼る。これは多くの欠点を有する。例えば、生のアセンブリコードの静的又は動的分析は、計算コストが高く、不正確であり、良好にスケーリングされず、有意な性能オーバヘッドを導入する可能性が高い。デコンパイルアプローチは、未知のバイナリプログラムに関連するソースコードを再構成し、ソースコード及び未知のバイナリプログラムを用いてテストを進めようとする。しかしながら、実際はソースコードファイルが再構成しようと試みる元のソースコードと実質的に異なるために、実際にはデコンパイルアプローチは、多くの状況で動作せず、使用できない又は高品質ではないソースコードファイルをレンダリングしてしまう場合がある。

0018

本開示で議論する幾つかの実施形態は、未知のバイナリプログラムに対する有効な入力シーケンスを決定するシステム及び/又は方法に関連する。上述の及び他の実施形態では、有効な入力シーケンスは、2以上の入力コマンド及び引数のシーケンスであっても良い。未知のバイナリプログラムに対する有効な入力シーケンスを決定することにより、未知のバイナリプログラムは、未知のバイナリプログラムのいかなる知識も有しないでテストできる。

0019

幾つかの実施形態では、未知のバイナリプログラムに対する有効な入力シーケンスは、複数の入力シーケンスにより未知のバイナリプログラムを実行することに基づき決定される。複数の入力シーケンスを用いた未知のバイナリプログラムの実行中に、未知のバイナリプログラムの実行トレースセットは、複数の入力シーケンスの各々の実行中に記録されても良い。実行トレースセットは、比較されても良い。比較に基づき、特定の入力シーケンスが、未知のバイナリプログラムに新しい状態へ移させる、未知のバイナリプログラムに対する有効な入力シーケンスである可能性が高いか否かが決定されても良い。

0020

幾つかの実施形態では、本開示に記載のシステム及び/又は方法は、ランダム入力生成に頼らなくても良い。この方法では、本開示に記載のシステム及び/又は方法は、有効な入力シーケンスを用いて未知のバイナリプログラムの高いカバレッジを達成できる。比較すると、ブラックボックスファジング及びその他のようなランダム入力生成に頼る他の技術は、未知のバイナリプログラムの高いカバレッジを達成できないことがある。

0021

幾つかの実施形態では、本開示に記載のシステム及び/又は方法は、ラプラットフォーム独立であっても良い。その結果、本開示に記載のシステム及び/又は方法は、移植可能であり、種々の動作環境で使用され得る。幾つかの実施形態では、本開示に記載のシステム及び/又は方法は、ソースコード又は未知のバイナリプログラムに関連する文書を有しないで成功裏実装され得る。幾つかの実施形態では、本開示に記載のシステム及び/又は方法は、パケットスニフィング、バス分析又は情報交換に頼る任意の他の方法を有しないで実装され得る。その結果、本開示に記載のシステム及び/又は方法は、リバースコードエンジニアリング技術を使用しないで実施され得る。

0022

図1は、本開示に記載の少なくとも1つの実施形態により構成される例示的な入力シーケンス決定処理100を示す。幾つかの実施形態では、処理100は、未知のバイナリプログラム102への入力の有効なシーケンスを決定するために、計装(instrumentation)モジュール110、実行モジュール120、パーティションモジュール130、及び決定モジュール150を用いても良い。代替又は追加で、処理100は、フローグラフモジュール140も用いても良い。

0023

計装モジュール110は、未知のバイナリプログラム102を受信するよう構成されても良い。未知のバイナリプログラム102は、バイナリプログラム全体、又はプログラムの1又は複数の機能若しくは他の特長のようなバイナリプログラムの部分であっても良い。上述の及び他の実施形態では、未知のバイナリプログラム102は、プログラムのコンパイルされたバージョンを有しても良い。プログラムは、プログラムの機能を記述するコード及びルーチンを有しても良い。プログラムのコード及びルーチンは、プログラム及びプログラムのコンパイルされたバージョンである未知のバイナリプログラム102にとって有効であり得る入力を定めても良い。幾つかの実施形態では、プログラムに対する入力は、1又は複数の入力ストリングを有しても良い。コード及びルーチンにより有効であると定められない入力は、プログラムに対する、したがって未知のバイナリプログラム102に対する無効な入力であり得る。

0024

幾つかの実施形態では、未知のバイナリプログラム102は、処理状態を把握するプログラムであっても良い。上述の及び他の実施形態では、処理状態を把握するプログラムは、過去の記憶を有するプログラムであっても良い。処理状態を把握するプログラムでは、前のトランザクションは、記憶されても良く、現在のトランザクションに影響を与えても良い。例えば、受信された前のデータ入力に関する情報は、変数に格納され、現在のデータ入力の処理に影響を与えるために使用されても良い。処理状態を把握するプログラムとして、プログラムは、処理状態を把握しないプログラムであってはならない。上述の及び他の実施形態では、処理状態を把握しないプログラムは、過去の記憶を有しないプログラムであっても良い。その結果、全ての要求又はトランザクションは、まるで最初に実行され及び前の要求又はトランザクションに関連しないかのようにプログラムにより実行され得る独立した要求又はトンザクションであっても良い。したがって、後続の入力は他の入力と独立であり、前の入力は後続の結果又はプログラム応答に影響を与えない。

0025

未知のバイナリプログラム102は、処理装置による実行のために、バイナリ形式エンコードされ及び非一時的コンピュータ可読記憶媒体に格納されたコード及びルーチンを有しても良い。未知のバイナリプログラム102のコード及びルーチンはテキストとして人間により解釈され得る部分を有しても良いが、未知のバイナリプログラム102のコード及びルーチンは、人間に可読でなくても良い。上述及び他の実施形態では、コード及びルーチンは、機械により可読あっても良い。例えば、コード及びルーチンは、バイナリ又は何らかの他の機械可読フォーマットであっても良い。

0026

未知のバイナリプログラム102に対する有効な入力は分からないので、未知のバイナリプログラム102は、「未知」であり得る。例えば、未知のバイナリプログラム102に関連する仕様、文書、又はソースコードは、未知のバイナリプログラム102の人間のテスター又は他のテスト設備に利用可能でなくても良い。その結果、人間のテスター又は他のテスト設備のテスターは、未知のバイナリプログラム102の有効な入力を決定することができなくても良い。

0027

計装モジュール110は、未知のバイナリプログラム102に基づき、計装(instrumented)バイナリプログラム112を生成するよう構成されても良い。上述の及び他の実施形態では、計装バイナリプログラム112を生成するために、計装モジュール110は、未知のバイナリプログラム102を計装(instrument)しても良い。未知のバイナリプログラム102を計装するために、計装モジュール110は、未知のバイナリプログラム102に追加コード命令を入力しても良い。追加コード命令は、未知のバイナリプログラム102の実行又は実行時間に関する情報を出力しても良い。計装バイナリプログラム112の中の追加コード命令により出力される追加情報は、計装バイナリプログラム112の実行トレースであっても良い。例えば、幾つかの実施形態では、実行トレースは、未知のバイナリプログラム102の実行中の、特に、メモリアドレスレジスタ値関数呼び出しスレッド、及び割り込み信号、に関する情報を有しても良い。

0028

別の例として、実行トレースは、未知のバイナリプログラム102により実行される命令ブロックの開始メモリアドレスであっても良い。未知のバイナリプログラム102により実行される命令ブロックは、単一の開始命令と単一の終了命令とを有する命令セットであっても良い。上述の及び他の実施形態では、単一の開始命令と単一の終了命令とを有する命令セットは、ジャンプ又はジャンプ目標を有しない未知のバイナリプログラム102の中の直線的ブロックであっても良い。

0029

幾つかの実施形態では、実行トレースは、時間の関数として出力されても良い。例えば、実行トレースは、時間的な実行順序で出力されても良い。したがって、第1の命令ブロックが第1の時間に実行されると、第1の実行トレースは、第1の時間における第1の命令ブロックの実行の記録であっても良い。第2の命令ブロックが第2の時間に実行されても良く、第2の実行トレースは、第2の時間における第2の命令ブロックの実行の記録であっても良い。第1の命令ブロックが第3の時間に再び実行されても良く、第3の実行トレースは、第3の時間における第1の命令ブロックの実行の記録であっても良い。上述の及び他の実施形態では、第2の命令ブロックは、未知のバイナリプログラム102のリストの中で、第1の命令ブロックの前にあっても良いが、実行の時間は、未知のバイナリプログラム102の中の命令リストの代わりに、実行トレースを順序付けるために用いられても良い。

0030

上述の及び他の実施形態では、実行トレースは、未知のバイナリプログラム102の計装無しでは未知のバイナリプログラム102により出力されない計装バイナリプログラム112により出力される情報であっても良い。したがって、実行トレースは未知のバイナリプログラム102の計装の結果として生じ、未知のバイナリプログラム102の通常の出力ではない。

0031

幾つかの実施形態では、計装モジュール110は、PINのようなバイナリ計装プログラム又は何らかの他のバイナリ計装プログラムを有しても良い。計装モジュール110は、計装バイナリプログラム112を、実行モジュール120に提供しても良い。

0032

実行モジュール120は、計装バイナリプログラム112と、入力シーケンス104と、を受信するよう構成されても良い。幾つかの実施形態では、入力シーケンス104は、各々、未知のバイナリプログラム102に対する2以上の異なる入力を有しても良い。幾つかの実施形態では、未知のバイナリプログラム102に対する入力は、予め発見され及び未知のバイナリプログラム102に対する有効な入力であると決定されても良い。しかしながら、未知のバイナリプログラム102に対する入力を決定したことは、未知のバイナリプログラム102に入力を提供する有効なシーケンスを示さない。例えば、未知のバイナリプログラム102は4個の異なる入力を認識することが発見されても良い。入力のうちの1つを受信した後に、未知のバイナリプログラム102は、入力のうちの別のもの又は同じものを期待しても良い。上述の及び他の実施形態では、未知のバイナリプログラム102に提供され得る、16個の異なる2入力長入力シーケンスが存在しても良い。処理100は、16個の異なる2入力長入力シーケンスのうちのどれが、未知のバイナリプログラム102に対する有効な入力シーケンスであるかを決定するよう構成されても良い。

0033

幾つかの実施形態では、有効な2入力長シーケンスを決定した後に、処理100は、有効な3入力長、4入力長、又は5入力長シーケンス又は他の長さのシーケンスが存在するかどうかを決定しても良い。幾つかの実施形態では、上述のように、未知のバイナリプログラム102は、処理状態を把握するプログラムであっても良い。上述の及び他の実施形態では、入力又は入力シーケンスを入れることにより別の状態に入った後に、未知のバイナリプログラム102に対する追加入力が発見されても良い。上述の及び他の実施形態では、処理100は、有効な入力シーケンスを決定するとき、追加入力を用いても良い。

0034

幾つかの実施形態では、シーケンスの中の2以上の異なる入力は、順序付けられて、入力がそれらの関連する順序で未知のバイナリプログラム102に提供されるようにしても良い。例えば、入力シーケンス104のうちの1つの中の第1の入力は、未知のバイナリプログラム102に最初に提供されても良く、入力シーケンス104のうちの1つの中の第2の入力は、未知のバイナリプログラム102に2番目に提供されても良い。

0035

幾つかの実施形態では、入力シーケンス104のために使用される入力は、それぞれ、未知のバイナリプログラム102に対するコマンドと、該コマンドに関連する引数と、を有しても良い。引数は、コマンドを受信した後に、未知のバイナリプログラム102により期待されても良い。例えば、コマンドは、未知のバイナリプログラム102が特定の関数を呼び出すことになる、未知のバイナリプログラム102の中の「呼び出し」コマンドであっても良い。上述の及び他の実施形態では、「呼び出し」コマンドに関連する引数は、未知のバイナリプログラム102の実行のそのポイントで呼び出され得る、未知のバイナリプログラム102の内部関数であっても良い。別の例として、未知のバイナリプログラム102の中のコマンドは、未知のバイナリプログラム102の機能を増大させる「権限付与」コマンドであっても良い。上述の及び他の実施形態では、「権限付与」コマンドの引数は、未知のバイナリプログラム102に未知のバイナリプログラム102の他の処理を実行させるための、未知のバイナリプログラム102により使用されるトークン又はパスワードであっても良い。入力シーケンスの有効なコマンド及び引数を決定する方法の更なる説明は、図4に関連して記載され得る。代替又は追加で、入力シーケンス104の構成の更なる説明は、図4に関して記載され得る。

0036

実行モジュール120は、入力シーケンス104の各々について別個に、計装バイナリプログラム112を実行するよう構成されても良い。上述の及び他の実施形態では、計装バイナリプログラム112の各々の実行は、入力シーケンス104のうちの1つを計装バイナリプログラム112に対する入力として用いて実行されても良い。例えば、3個の入力シーケンス104が存在する場合、実行モジュール120は、計装バイナリプログラム112を、3個の入力シーケンス104の各々について1回の3回実行しても良い。

0037

入力シーケンス104のうちの1つを用いる計装バイナリプログラム112の各々の実行中に、実行モジュール120は、計装バイナリプログラム112により生成された実行トレースを記録するよう構成されても良い。したがって、実行モジュール120は、複数の実行トレースセット122を生成しても良い。実行トレースセット122の各々は、計装バイナリプログラム112の1回の実行について生成されても良い。例えば、入力シーケンス104のうちの1つを用いる実行モジュール120の1回の実行中に生成された実行トレースは、実行トレースセット122のうちの1つを形成しても良い。したがって、実行トレースセット122のうちの各々のセットは、入力シーケンス104のうちの1つに対応し及び関連付けられても良い。

0038

実行トレースセット122の中の実行トレースは、計装バイナリプログラム112の中の基本命令ブロックの実行の記録であっても良い。幾つかの実施形態では、実行トレースは、実行される1又は複数の命令ブロックに関連するメモリ位置の数値のような数値を含み又はそれに関連付けられても良い。例えば、ブロックは、実行トレースに関連するメモリ位置で実行を開始する、いかなるジャンプ又はジャンプ目標を有しない直線的コードピースであっても良い。上述の及び他の実施形態では、別の実行トレースは、コードが別のメモリ位置へジャンプするとき、開始しても良い。次の実行トレースは、他のメモリ位置を含み又はそれに関連付けられても良い。実行トレースセット122は、パーティションモジュール130に提供されても良い。

0039

パーティションモジュール130は、実行トレースセット122を受信するよう構成されても良い。幾つかの実施形態では、パーティションモジュール130は、実行トレースセット122の各々をパーティショニングするよう更に構成されても良い。上述の及び他の実施形態では、実行トレースセット122の各々をパーティショニングするステップは、実行トレースセット122の各々のパーティション位置を決定するステップを有しても良い。

0040

パーティション位置を決定するために、パーティションモジュール130は、実行トレースセット122の各々の中の、特定の実行トレース又は実行トレースシーケンスの位置を特定しても良い。特定の実行トレース又は実行トレースシーケンスは、パーティション位置であっても良い。幾つかの実施形態では、特定の実行トレース又は実行トレースシーケンスは、計装バイナリプログラム112にいかなる入力も適用しないで、計装バイナリプログラム112を実行することに基づき決定されても良い。上述の及び他の実施形態では、特定の実行トレース又は実行トレースシーケンスは、計装バイナリプログラム112の実行中にロギングされた最後の実行トレース又は最後の実行トレースシーケンスであっても良い。例えば、最後の実行トレースシーケンスは、2、3、4、5、6、又はそれより多くの実行トレースを有しても良い。上述の及び他の実施形態では、特定の実行トレース又は実行トレースシーケンスは、パーティションフラグとして参照されても良い。

0041

幾つかの実施形態では、パーティションフラグは、バイナリプログラム112が入力を期待していることの指示であっても良い。例えば、パーティションフラグが、計装バイナリプログラム112の実行中にロギングされた最後の実行トレース又は最後の実行トレースシーケンスであるときである。ロギングされた最後の実行トレース又は最後の実行トレースシーケンスであるパーティションフラグは、計装バイナリプログラム112が停止され、継続する前に入力を待っていることを示し得る。上述の及び他の実施形態では、したがって、パーティションフラグは、計装バイナリプログラム112が開始し及び特定の入力に対する作用を停止する、実行トレース112のセットの各々の中の位置を示しても良い。例えば、計装バイナリプログラム112は、2入力のシーケンスに基づき実行しても良い。実行により生成された実行トレースは、パーティションフラグの3個のインスタンスを有しても良い。実行トレースの始めとパーティションフラグの第1のインスタンスとの間は、第1の入力を受信する前の、計装バイナリプログラム112の実行を示しても良い。パーティションフラグの第1のインスタンスとパーティションフラグの第2のインスタンスとの間は、第1の入力を受信している最中及びその後、且つ第2の入力を受信する前の、計装バイナリプログラム112の実行を示しても良い。パーティションフラグの第2のインスタンスとパーティションフラグの第3のインスタンスとの間は、第2の入力を受信している最中及びその後の、計装バイナリプログラム112の実行を示しても良い。

0042

パーティションモジュール130は、パーティションフラグの位置を決定するために、実行トレース112のセットの各々を個別に見直しても良い。幾つかの実施形態では、パーティションフラグは、複数回生じても良い。実行トレースセット122の中のパーティションフラグの位置は、パーティション位置であっても良い。パーティションモジュール130は、実行トレースセット122を、それらの対応するパーティション位置に基づき、区分して、パーティショニング済み実行トレースセット132を生成しても良い。例えば、2入力のシーケンスでは、実行トレースセットは、3個の部分に区分されても良い。第1の部分は、計装バイナリプログラム112によりいかなる入力も受信されないときに対応しても良い。第2の部分は、計装バイナリプログラム112により第1の入力が受信され作用されるときに対応しても良い。第3の部分は、計装バイナリプログラム112により第2の入力が受信され作用される場所に対応しても良い。パーティションモジュール130は、決定モジュール150に、パーティショニング済み実行トレースセット132を送信しても良い。

0043

決定モジュール150は、パーティションモジュール130から、パーティショニング済み実行トレースセット132を受信しても良い。決定モジュール150は、パーティショニング済み実行トレースセット132を比較するよう構成されても良い。パーティショニング済み実行トレースセット132の比較に基づき、決定モジュール150は、入力シーケンス104が存在する場合にはそのうちのどれを、未知のバイナリプログラムが有効として受け付けるかを決定しても良い。

0044

幾つかの実施形態では、決定モジュール150は、パーティショニング済み実行トレースセット132の全部を比較しても良い。代替又は追加で、決定モジュール150は、計装バイナリプログラム112への同じ入力の実行に基づき生成されるパーティショニング済み実行トレースセット132を比較しても良い。例えば、決定モジュール150は、各々の入力シーケンスの最後の入力の実行に対応する、パーティショニング済み実行トレースセット132の最後のパーティションを比較しても良い。最後の入力が有効であると決定された場合、入力シーケンス全体が正しい入力シーケンスであることが示唆され得る。したがって、上述の及び他の実施形態では、最後の入力に対応するパーティショニング済み実行トレースセット132の最後のパーティションが比較されても良く、パーティショニング済み実行トレースセット132のパーティションは比較されなくても良い。

0045

上述の及び他の実施形態では、パーティショニング済み実行トレースセット132の最後のパーティションが、最後のパーティションが全て同じであることを示すとき、入力シーケンスのいずれも、シーケンシャル入力として未知のバイナリプログラム102により受け入れられないと決定されても良い。最後のパーティションの全部が同じとき、未知のバイナリプログラム102が最後の入力の全部を同じ方法で処理したことを示し得る。各々の最後の入力を同じ方法で処理することは、未知のバイナリプログラム102が最後の入力を有効な入力として受け入れなかったことを示し得る。したがって、最後の入力の全部は無効であり得る。

0046

幾つかの実施形態では、パーティショニング済み実行トレースセット132の比較が、最後のパーティションのうちの少なくとも別の2つが同じであること、及び1又は複数の他の最後のパーティションが、最後のパーティションのうちの該同じ2つと異なることを示すとき、最後のパーティションのうちの1又は複数を生成するために使用された入力シーケンスは、未知のバイナリプログラム102により有効な入力シーケンスとして受け入れられたことを示し得る。最後のパーティションの一部が、同じである最後のパーティションのうちの他のものと異なるとき、未知のバイナリプログラム102は異なる方法で最後の入力の一部を処理したことを示し得る。最後の入力の一部を異なる方法で処理することは、未知のバイナリプログラム102が最後の入力シーケンスの一部を受け入れ、他の部分を受け入れなかったことを示し得る。受け入れられない入力は、未知のバイナリプログラム102により同じく処理される傾向があっても良いが、受け入れられた最後の入力は、各々、未知のバイナリプログラム102により異なる方法で処理されても良い。したがって、最後の入力の一部は有効であり、他は無効であり得る。

0047

幾つかの実施形態では、処理100は、フローグラフモジュール140を有しても良い。上述の及び他の実施形態では、パーティションモジュール130は、決定モジュール150ではなく、フローグラフモジュール140に、パーティショニング済み実行トレースセット132を送信しても良い。

0048

フローグラフモジュール140は、パーティションモジュール130から、パーティショニング済み実行トレースセット132を受信するよう構成されても良い。フローグラフモジュール140は、パーティショニング済み実行トレースセット132の各々のパーティションの各々について、制御フローグラフを決定するよう更に構成されても良い。制御フローグラフは、実行トレースセット122に基づき、計装バイナリプログラム112の実行によりトラバースされる経路を表しても良い。制御フローグラフは、図3に示される。概して、制御フローグラフは、エッジによりリンクされるノードを有する。幾つかの実施形態では、ノードは、直線的コードのブロックを表す単一の実行トレースを表し得る。直線的コードの異なるブロックの間のジャンプ又は変化は、エッジにより表され得る。上述の及び他の実施形態では、実行トレースのうちの1又は複数はノードにより表され、エッジは、次の1又は複数の実行トレースへの変化を表し得る。フローグラフモジュール140は、制御フローグラフ142を決定モジュール150へ送信しても良い。

0049

図2は、本願明細書に記載の少なくとも1つの実施形態に従い構成され得る、パーティショニング済み実行トレースセットの各々のパーティションの各々について制御フローグラフを構築する例示的な方法200を示す。方法200は、幾つかの実施形態では、図5のシステム500のようなシステムにより実施されても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。

0050

方法200は、ブロック202で開始し、実行トレースが選択されても良い。幾つかの実施形態では、選択された第1の実行トレースは、パーティショニング済み実行トレースセット132のうちの1つのセットからのパーティションの第1の実行トレースであっても良い。第1の実行トレースが選択された後に、第2の及び後続の実行トレースの選択は、パーティションの実行トレースシーケンスの中の次の実行トレースに基づいても良い。

0051

ブロック204で、選択された実行トレースがグラフの中に示されるかどうかが決定されても良い。選択された実行トレースがグラフの中に示されると、方法200はブロック206へ進んでも良い。選択された実行トレースがグラフの中に示されないとき、方法200はブロック208へ進んでも良い。幾つかの実施形態では、実行トレースが、グラフの中に既にあるノードと関連する又はそれに含まれるメモリ位置と同じ又はそれと類似するメモリ位置を含む又はそれに関連するとき、選択された実行トレースは、グラフの中に示されても良い。

0052

ブロック206で、グラフの中で選択された実行トレースを示す、グラフの中に既に存在するノードは、現在のノードとして設定されても良い。方法200は、ブロック202に戻り、別の実行トレースがパーティショニング済み実行トレースセット132から選択されても良い。

0053

ブロック208で、選択された実行トレースを表す新しいノードが生成されても良い。ブロック210で、新しいノードは、現在のノードからエッジにより付加されても良い。新しいノードが第1のノードであるとき、新しいノードは制御フローグラフの中の第1のノードであるので、新しいノードは、現在のノードから付加されなくても良い。

0054

ブロック212で、新しいノードは、現在のノードとして設定されても良い。方法200は、ブロック202に戻り、別の実行トレースがパーティショニング済み実行トレースセット132から選択されても良い。

0055

業者は、この処理及び本願明細書に開始した他の処理及び方法において、その処理及び方法で実行される機能が異なる順序で実施されても良いことを理解するだろう。さらに、概略のステップ及び動作は、単に例として提供され、幾つかのステップ及び動作は、開示の実施形態の本質から逸脱することなく、任意であり、より少ないステップ及び動作に組み合わされ、又は追加ステップ及び動作に拡張されても良い。

0056

本願明細書に記載の少なくとも一実施形態に従い構成され得る例示的な制御フローグラフ300は図3に示される。制御フローグラフ300は、図3にも示される実行トレースリスト320に基づき構築されても良い。実行トレースリスト320は、12、14、15、14、16、12、18と番号を付された7個の記録された実行トレースを有しても良い。制御フローグラフ300は、5個のノード、つまり第1のノード302、第2のノード304、第3のノード306、第4のノード308、及び第5のノード310を有しても良い。

0057

制御フローグラフ300を構築するために実行トレースリスト320からの7個の記録された実行トレースを用いる方法200の例示的な実行を以下に説明する。番号12を付された第1の実行トレースが選択されても良い。第1の実行トレースは新しいノードなので、第1のノード302が生成され、現在のノードとして設定されても良い。番号14を付された第2の実行トレースが選択されても良い。第2の実行トレースは、第1のノード302により表される実行トレースと異なるので、新しいノード、つまり第2のノード304が生成される。第2のノード304は、第1のノード302である現在のノードに付加される。第2のノード304は、現在のノードとして設定される。

0058

番号15を付された第3の実行トレースが選択されても良い。第3の実行トレースは、第1のノード302又は第2のノード304により表される実行トレースと異なるので、新しいノード、つまり第3のノード306が生成される。第3のノード306は、第2のノード304である現在のノードに付加される。第3のノード306は、現在のノードとして設定される。

0059

番号14を付された第4の実行トレースが選択されても良い。第4の実行トレースは、第2のノード304により表される実行トレースと同じなので、第2のノード304は現在のノードとして設定され、別の実行トレースが選択される。

0060

番号16を付された第5の実行トレースが選択されても良い。第5の実行トレースは、第1のノード302、第2のノード304又は第3のノード306により表される実行トレースと異なるので、新しいノード、つまり第4のノード308が生成される。第4のノード308は、第2のノード304である現在のノードに付加される。第4のノード308は、現在のノードとして設定される。

0061

番号12を付された第6の実行トレースが選択されても良い。第6の実行トレースは、第1のノード302により表される実行トレースと同じなので、第1のノード302は現在のノードとして設定され、別の実行トレースが選択される。

0062

番号18を付された第7の実行トレースが選択されても良い。第7の実行トレースは、他のノードにより表される実行トレースと異なるので、新しいノード、つまり第5のノード310が生成される。第5のノード310は、第1のノード302である現在のノードに付加される。第5のノード310は、現在のノードとして設定される。

0063

図1に戻り、決定モジュール150は、フローグラフモジュール140から制御フローグラフ142を受信しても良い。決定モジュール150は、制御フローグラフ142を比較するよう構成されても良い。制御フローグラフ142の比較に基づき、決定モジュール150は、入力シーケンス104が存在する場合にはそのうちのどれを、未知のバイナリプログラムが有効として受け付けるかを決定しても良い。

0064

幾つかの実施形態では、決定モジュール150は、フローグラフモジュール140からの制御フローグラフの全部を比較しても良い。代替又は追加で、決定モジュール150は、計装バイナリプログラム112への同じ入力の実行に基づき生成されるパーティショニング済み実行トレースセット132に対応する制御フローグラフを比較しても良い。例えば、決定モジュール150は、各々の入力シーケンスの最後の入力の実行に対応する、パーティショニング済み実行トレースセット132の最後のパーティションについて生成される制御フローグラフ142を比較しても良い。最後の入力が有効であると決定された場合、入力シーケンス全体が正しい入力シーケンスであることが示唆され得る。したがって、上述の及び他の実施形態では、最後の入力に対応する制御フローグラフ142は比較され、他の入力に対応する制御フローグラフ142は比較されなくても良い。

0065

上述の及び他の実施形態では、制御フローグラフ142の比較が、入力シーケンスの各々の最後の入力の制御フローグラフ142が全て同じであることを示すとき、入力シーケンスのいずれも、シーケンシャル入力として未知のバイナリプログラム102により受け入れられないと決定されても良い。制御フローグラフ142の全部が同じとき、未知のバイナリプログラム102が最後の入力の全部を同じ方法で処理したことを示し得る。各々の最後の入力を同じ方法で処理することは、未知のバイナリプログラム102が最後の入力を有効な入力として受け入れなかったことを示し得る。したがって、最後の入力の全部は無効であり得る。

0066

幾つかの実施形態では、各々の入力シーケンスの最後の入力についての制御フローグラフ142の比較が、制御フローグラフ142のうちの少なくとも別の2つが同じであり、1又は複数の他の制御フローグラフ142が制御フローグラフ142のうちの該同じ2つと異なることを示すとき、制御フローグラフ142のうちの1又は複数を生成するために使用された入力シーケンスは、未知のバイナリプログラム102により有効な入力シーケンスとして受け入れられることを示し得る。制御フローグラフ142のうちの一部が、同じ制御フローグラフ142のうちの他のものと異なるとき、未知のバイナリプログラム102は異なる方法で最後の入力の一部を処理したことを示し得る。最後の入力の一部を異なる方法で処理することは、未知のバイナリプログラム102が最後の入力シーケンスの一部を受け入れ、他の部分を受け入れなかったことを示し得る。受け入れられない入力は、未知のバイナリプログラム102により同じく処理される傾向があっても良いが、受け入れられた最後の入力は、各々、未知のバイナリプログラム102により異なる方法で処理されても良い。したがって、最後の入力の一部は有効であり、他は無効であり得る。

0067

幾つかの実施形態では、決定モジュール150は、制御フローグラフ142の各々について、ストリング表現を生成するよう構成されても良い。上述の及び他の実施形態では、制御フローグラフのストリング表現は、制御フローグラフを直接比較する代わりに、比較されても良い。上述の及び他の実施形態では、制御フローグラフのストリング表現は、制御フローグラフの体系的トラバースに制御フローグラフのノードを含めるストリングを有しても良い。制御フローグラフの体系的トラバースのための種々のアルゴリズムは、制御フローグラフを体系的にトラバースする方法の中でも特に、縦型探索横型探索、を含む。

0068

図3は、本願明細書に記載の少なくとも1つの実施形態により構成される、制御フローグラフ300の例示的なストリング表現330を示す。ストリング表現330は、実行トレースリスト320のシーケンシャル順序で、実行トレースリスト320と異なる値の全部を有する。ストリング表現330を生成する一例は次の通りである。ストリング表現330は、第1のノード302において開始し、第1のノード302を記録する。ストリング表現330は、左へ進み、第2のノード304を記録する。ストリング表現330は、左へ進み、第3のノード306を記録する。ストリング表現330は左へ進めないので、ストリング表現330は、制御フローグラフ300を上に第3のノード306まで進み、次に、右へ第4のノード308まで進む。ストリング表現330は、右又は左へ進めない、又は既に右及び左に進んでいるので、ストリング表現330は、第1のノード302へ及び第5のノード310の右へ進み、ストリング表現330を完了する。

0069

本開示の範囲から逸脱することなく処理100に対し変更、追加又は省略が行われても良い。例えば、幾つかの実施形態では、パーティションモジュール130は、実行トレースセット122の各々のパーティション位置及び実行トレースセット122を、フローグラフモジュール140へ送信し、実行トレースセット122をパーティショニングしなくても良い。上述の及び他の実施形態では、フローグラフモジュール140は、実行トレースセット122をパーティショニングしても良い。

0070

代替又は追加で、パーティションモジュール130は、実行トレースセット122の各々の1又は複数のパーティションをフローグラフモジュール140へ送信し、実行トレースセット122の各々のパーティションの全部をフローグラフモジュール140へ送信しなくても良い。例えば、上述の及び他の実施形態では、パーティションモジュール130は、実行トレースセット122の各々の最後のパーティションを送信しても良い。上述の及び他の実施形態では、制御フローグラフ142は、実行トレースセット122の各々の最後のパーティションを有しても良い。

0071

図4は、本願明細書に記載の少なくとも1つの実施形態に従って構成され得る例示的な入力決定処理400を示す。処理400は、入力モジュール410を使用しても良く、実行モジュール420は、未知のバイナリプログラム414に対する入力412及び未知のバイナリプログラム414に対する入力シーケンス430を決定する。未知のバイナリプログラム414の中の所与の状態に対する有効な入力を決定するシステム及び方法は、係属中の米国特許出願番号14/620,106、2015年2月11日に記載されている。該米国特許出願は、参照することによりその全体が本願明細書に組み込まれる。

0072

幾つかの実施形態では、処理400は、未知のバイナリプログラム414の状態に対する入力412を決定しても良い。幾つかの実施形態では、入力412は、1又は複数の1又は複数のインデックスを有し得る入力ストリングの中の1又は複数の印刷可能文字であっても良い。プログラムの入力ストリングは、1又は複数のインデックス及び1又は複数の印刷可能文字を有しても良い。インデックスは、印刷可能文字が生じるストリングの中の位置を有しても良い。例えば、受け入れられる入力ストリングが「Hello」及び「Howdy」である場合、インデックスは「0」、「1」、「2」、「3」、「4」である。本例では、インデックス「0」の有効な文字は、印刷可能文字「H」を有する。インデックス「1」の有効な文字は、印刷可能文字「e」及び「o」を有する。インデックス「2」の有効な文字は、印刷可能文字「l」及び「w」を有する。インデックス「3」の有効な文字は、印刷可能文字「l」及び「d」を有する。インデックス「4」の有効な文字は、印刷可能文字「o」及び「y」を有する。

0073

有効な入力ストリングと見なされると、入力ストリングに含まれる文字の各々は、未知のバイナリプログラム414に対して有効であり得る。有効な入力ストリングの任意の所与のインデックスについて、入力ストリングの中で使用するために利用可能な印刷可能文字の大部分は、無効であり得る。処理400は、それらが未知のバイナリプログラム414に対する有効な入力ストリングの異なるインデックスについて有効な文字であるかどうかを決定するために、印刷可能文字セットを繰り返しテストするよう構成されても良い。

0074

入力モジュール410は、印刷可能文字を選択し、実行モジュール420に入力412として提供するよう構成されても良い。実行モジュール420は、第1の印刷可能文字を入力412として用いて、未知のバイナリプログラム414を実行しても良い。実行モジュール420は、入力412を用いる未知のバイナリプログラム414の実行中に、未知のバイナリプログラム414により実行される命令の数を記録しても良い。実行される命令の数は、実行モジュール420により命令数422として出力されても良い。命令数422は、入力モジュール410に提供されても良い。

0075

入力モジュール410は、命令数422が閾範囲より大きいか否かを決定しても良い。入力モジュール410は、命令数422が閾範囲より大きいとき、第1の印刷可能文字が未知のバイナリプログラム414の状態に有効な入力として含まれる候補であり得ると決定しても良い。入力モジュール410は、命令数422が閾範囲より小さい又はそれに等しいとき、第1の印刷可能文字が未知のバイナリプログラム414の第1の状態に有効な入力として含まれる候補でないと決定しても良い。

0076

閾範囲は、実行される命令の数及びテスト制約のモードに基づき決定されても良い。モードは、実行される命令数のモードを有しても良い。例えば、実行される命令数は、セットに格納されても良い。セットは、1又は複数の値を有しても良い。数値は、入力モジュール410により提供される各々の入力について実行される命令数を表しても良い。例えば、100個の命令を生じる第1の入力が実行されると仮定する。第1の入力についての数値は、数「100」であっても良い。セットは、他の入力についての他の数値を有しても良い。モードは、セットの中で最も頻繁に現れる数値を有しても良い。

0077

テスト制約は、「イプシロン」又は「テスト制約」として参照されても良い。テスト制約は、任意の正の実数を有しても良い。閾範囲の上限は、テスト制約をモードに加算することにより決定されても良い。

0078

第1の印刷可能文字が未知のバイナリプログラム414の状態において有効な入力の候補でないとき、入力モジュール410は、第2の印刷可能文字を実行モジュール420に実行のために提供しても良い。同様の方法で、入力モジュール410は、第2の印刷可能文字が未知のバイナリプログラム414の状態に有効な入力として含まれる候補であるかどうかを決定しても良い。処理400は、入力モジュール410が未知のバイナリプログラム414の状態における有効な入力に含むための候補である文字を決定するまで、指示として動作し続けても良い。

0079

入力モジュール410は、入力412を形成するために、別の文字を候補文字と連結しても良い。特に、入力モジュール410は、第1の候補文字を第1のインデックス位置に、他の文字を第2のインデックス位置に、配置しても良い。上述の及び他の実施形態では、候補文字と他の文字との連結は、部分的に有効な入力として参照されても良い。入力モジュール410は、入力412を、実行モジュール420に提供しても良い。

0080

実行モジュール420は、入力412を用いて、未知のバイナリプログラム414を実行しても良い。未知のバイナリプログラム414の実行に基づき、実行モジュール420は、命令数422を出力しても良い。入力モジュール410は、第2のインデックス位置にある他の文字が未知のバイナリプログラム414の状態における有効な入力に含まれるための候補であり得るかどうかを、命令数422に基づき決定しても良い。

0081

処理400は、同様の方法で、未知のバイナリプログラム414の状態について処理400により決定され得る有効な入力の全部又は大部分が決定されるまで、続いても良い。

0082

幾つかの実施形態では、入力モジュール410は、有効な入力を結合して、入力シーケンス430を形成しても良い。幾つかの実施形態では、入力モジュール410は、入力シーケンスセット430を形成しても良い。入力シーケンスセットの各々は、最後の入力が同じであり且つ各々のシーケンスの中の残りの入力が異なる入力シーケンス430を有しても良い。

0083

幾つかの実施形態では、入力シーケンス430の入力は、コマンド及びそれに関連する引数であっても良い。上述の及び他の実施形態では、処理400が所与のコマンドの有効な引数を決定するために可能な印刷可能文字と一緒にコマンドを入力として提供し得る点を除き、処理400は、コマンドが発見されるのと同様の方法でコマンドの有効な引数を決定しても良い。

0084

幾つかの実施形態では、入力モジュール410は、決定された有効な入力に対して所定の入力シーケンス長の全ての可能な入力シーケンス順列を構築しても良く、入力シーケンス順列の全部を入力シーケンス430として提供しても良い。上述の及び他の実施形態では、図1の処理100のような処理は、入力シーケンス430のうちのどれが未知のバイナリプログラム414に対して有効な入力シーケンスであるかを決定しても良い。上述の及び他の実施形態では、処理は、入力シーケンス430の各々を実行し、結果として生じる実行トレースを区分し、制御フローグラフを生成し、制御フローグラフを比較して入力シーケンス430のうちのどれが有効であるかを決定しても良い。幾つかの実施形態では、処理は、同じ最後の入力を有する入力シーケンスについて、制御フローグラフを比較して、入力シーケンス430のうちのどれが有効かを決定しても良い。幾つかの実施形態では、有効な入力シーケンスを決定した後に、処理400は、有効な入力シーケンスを入力412の開始として用いて、未知のバイナリプログラム414に対する追加入力を発見しても良い。上述の及び他の実施形態では、追加入力は、追加入力シーケンス430を生成するために用いられても良い。追加入力シーケンス430は、次に、図1の処理100のような処理に提供されても良い。この方法では、処理400及び図1の処理100に類似する処理は、一緒に用いられても良い。本開示の範囲から逸脱することなく処理400に対し変更、追加又は省略が行われても良い。

0085

図5は、本願明細書に記載の少なくとも1つの実施形態により配置され得る例示的な入力決定システム500のブロック図を示す。図5に示すように、システム500は、プロセッサ510と、メモリ512と、データ記憶装置514と、通信ユニット518と、を有しても良い。

0086

概して、プロセッサ510は、任意の適切な特定用途向け又は汎用コンピュータコンピューティングエンティティ、又は種々のコンピュータハードウェア若しくはソフトウェアモジュールを有しても良く、任意の適切なコンピュータ可読媒体に格納された命令を実行するよう構成され得る処理装置を用いて実施されても良い。例えば、プロセッサ510は、マイクロプロセッサマイクロコントローラ、デジタシグナルプロセッサ(DSP)、特定用途向け集積回路ASIC)、フィールドプログラマブルゲートアレイFPGA)又はプログラム命令を解釈し及び/若しくは実行し並びに/又はデータを処理するよう構成された任意の他のデジタル若しくはアナログ回路を有しても良い。図5には単一のプロセッサを示したが、プロセッサ510は、本願明細書に記載の任意の数の演算を個々に又は共同で実行するよう構成される任意の数のネットワーク又は物理的位置に渡り分散される任意の数のプロセッサを有しても良いことが理解される。幾つかの実施形態では、プロセッサ510は、プログラム命令を解釈し及び/又は実行し、及び/又はメモリ512、データ記憶装置514又はメモリ512及びデータ記憶装置514に格納されたデータを処理してもよい。幾つかの実施形態では、プロセッサ510は、データ記憶514からプログラム命令をフェッチし、該プログラム命令をメモリ512にロードしても良い。プログラム命令がメモリ512にロードされた後、プロセッサ510は、それぞれ図1、4、6の処理100、処理400及び/又は方法600を実行するための命令のようなプログラム命令を実行しても良い。

0087

メモリ512及びデータ記憶装置514は、コンピュータ実行可能命令又はデータ構造を伝える又は格納しているコンピュータ可読記憶媒体又は1又は複数のコンピュータ可読記憶媒体を含み得る。このようなコンピュータ可読媒体は、プロセッサ510のような汎用又は特定目的コンピュータによりアクセスできる任意の利用可能な媒体であり得る。例として且つ限定ではなく、このようなコンピュータ可読媒体は、RAM(Random Access Memory)、ROM(Read−Only Memory)、EEPROM(Electrically Erasable Programmable Read−Only Memory)、CD−ROM(Compact Disc Read−Only Memory)又は他の光ディスク記憶装置磁気ディスク記憶装置又は他の磁気記憶装置フラッシュメモリ装置(例えば、固体メモリ素子)を含む非一時的コンピュータ可読記憶媒体、又はコンピュータにより実行可能な命令若しくはデータ構造の形式で所望のプログラムコード手段を伝える若しくは格納するために用いられ汎用若しくは特定目的コンピュータによりアクセス可能な他の記憶媒体を有し得る。上述の組合せも、コンピュータ可読記憶媒体の範囲に包含され得る。コンピュータ実行可能命令は、例えば、プロセッサ510に特定の工程又は工程のグループを実行させるよう構成される命令及びデータを含み得る。

0088

通信ユニット516は、未知のバイナリプログラムを受信し、未知のバイナリプログラムをデータ記憶装置514に提供するよう構成されても良い。データ記憶装置514により受信された後、プロセッサ510を用いる未知のバイナリプログラムに対する入力及び入力シーケンス、並びに命令は、データ記憶装置に格納される。幾つかの実施形態では、決定された入力及び入力シーケンスは、通信ユニット516を用いてシステム500の外部に提供されても良い。

0089

本開示の範囲から逸脱することなくシステム500に対し変更、追加又は省略が行われても良い。例えば、データ記憶装置514は、複数の場所に置かれ、ネットワークを通じてプロセッサ510によりアクセスされても良い。

0090

図6は、本願明細書に記載した少なくとも1つの実施形態に従って構成された、未知のバイナリプログラムに対する有効な入力シーケンスを決定する別の例示的な方法600のフローチャートを示す。方法600は、幾つかの実施形態では、図5のシステム500のようなシステムにより実施されても良い。別個のブロックとして示したが、所望の実装に依存して、種々のブロックは、更なるブロックに分割され、少ないブロックに結合され、又は除去されても良い。

0091

方法600は、ブロック602で開始し、未知のバイナリプログラムに対する複数の入力シーケンスが得られても良い。幾つかの実施形態では、入力シーケンスの各々は、2以上の異なる入力を有しても良い。入力は、未知のバイナリプログラムの有効な入力として予め決定されても良い。幾つかの実施形態では、入力は、未知のバイナリプログラムに対して有効であると決定されたコマンド、及び該コマンドと関連する引数と、を有しても良い。引数も、未知のバイナリプログラムに対して有効であると決定されても良い。幾つかの実施形態では、各々の入力シーケンスの中の最後の入力は同じであっても良い。

0092

ブロック604で、未知のバイナリプログラムの計装バージョンは、各々の入力シーケンスについて別個に実行されても良い。未知のバイナリプログラムの計装バージョンの各々の実行は、入力シーケンスのうちの1つを、未知のバイナリプログラムの計装バージョンへの入力として用いても良い。

0093

ブロック606で、未知のバイナリプログラムの計装バージョンの各々の実行について、未知のバイナリプログラムの計装バージョンの実行により生成される実行トレースを記録することにより、実行トレースセットが生成されても良い。幾つかの実施形態では、実行トレースセットの生成は、未知のバイナリプログラムの計装バージョンの各々の実行について、実行トレースセットに含めるために実行トレースの一部を選択するステップを有しても良い。上述の及び他の実施形態では、実行トレースセットのために選択された実行トレースの一部は、入力シーケンスの最後の入力が未知のバイナリプログラムに提供された後に生成された実行トレースであっても良い。

0094

幾つかの実施形態では、実行トレースセットに含めるための実行トレースの一部の選択は、複数のステップ又は工程を有しても良い。例えば、実行トレースの一部を選択するステップは、いかなる入力も有しないで未知のバイナリプログラムの計装バージョンを実行するステップと、いかなる入力も有しない実行の終了時に未知のバイナリプログラムの計装バージョンの実行により生成される複数の実行トレースを決定するステップと、を有しても良い。上述の及び他の実施形態では、実行トレースの一部の選択は、決定した複数の実行トレースをパーティション実行トレースとして設定するステップと、入力シーケンスを用いる未知のバイナリプログラムの計装バージョンの実行中に生成される実行トレースの部分を、パーティション実行トレースの最後から2番目の発生と最後の発生との間で生じる実行トレースの部分に基づき、選択するステップと、を更に有しても良い。

0095

ブロック608で、実行トレースセットは比較されても良い。幾つかの実施形態では、実行トレースセットのうちの1つのセットの中の実行トレースは、未知のバイナリプログラムの計装バージョンにより出力され且つ未知のバイナリプログラムの非計装バージョンにより出力されない未知のバイナリプログラムの中で実行される直線的命令セットに関連するメモリアドレスを表しても良い。

0096

ブロック610で、実行トレースセットの比較に基づき、入力シーケンスのうちのどれを、未知のバイナリプログラムが有効であるとして受け入れるかが決定されても良い。幾つかの実施形態では、実行トレースセットの比較が、実行トレースセットは同じであると示すとき、入力シーケンスのいずれも、未知のバイナリプログラムにより受け入れられないと決定されても良い。代替で又は追加で、実行トレースセットの比較が、実行トレースセットのうちの1つが実行トレースセットのうちの同じである少なくとも別の2つと異なることを示すとき、実行トレースセットのうちの該1つに対応する入力シーケンスは、未知のバイナリプログラムにより受け入れられると決定されても良い。

0097

当業者は、この処理及び本願明細書に開始した他の処理及び方法において、その処理及び方法で実行される機能が異なる順序で実施されても良いことを理解するだろう。さらに、概略のステップ及び動作は、単に例として提供され、幾つかのステップ及び動作は、開示の実施形態の本質から逸脱することなく、任意であり、より少ないステップ及び動作に組み合わされ、又は追加ステップ及び動作に拡張されても良い。

0098

例えば、方法600は、実行トレースセットの各々について制御フローグラフを生成するステップを更に有しても良い。上述の及び他の実施形態では、実行トレースセットの比較は、制御フローグラフの各々のストリング表現を生成するステップと、該ストリング表現を比較するステップと、を有しても良い。上述の及び他の実施形態では、各々の制御フローグラフについてストリング表現を生成するステップは、縦型探索アルゴリズム又は横型探索アルゴリズムを実施するステップを有しても良い。

0099

幾つかの実施形態では、各々の入力シーケンスの中の最後の入力は同じであっても良い。上述の及び他の実施形態では、複数の入力シーケンスは、それぞれ複数の入力シーケンスを含む複数の入力シーケンスセットの中の1つの入力シーケンスセットであっても良い。他の入力シーケンスセットのうちの各々のセットの各々の入力シーケンスの最後の入力は、同じであっても良く、各々の入力シーケンスセットの最後の入力は異なっても良い。例えば、それぞれ4個の入力シーケンスを有する4個の入力シーケンスセットが存在しても良い。第1の入力シーケンスセットの中の各々の入力シーケンスの最後の入力は、同じであっても良く、第2の入力シーケンスセットの中の各々の入力シーケンスの最後の入力は同じであっても良く、第3の入力シーケンスセットの中の各々の入力シーケンスの最後の入力は、同じであっても良く、第4の入力シーケンスセットの中の各々の入力シーケンスの最後の入力は同じであっても良い。ある入力シーケンスセットの中の入力シーケンスの最後の入力は、他の入力シーケンスセットと比べて異なっても良い。上述の及び他の実施形態では、方法600は、入力シーケンスセットの各々について方法600の動作、ステップ、又は工程を実行するステップを更に有しても良い。

0100

本願明細書に記載した実施形態は、以下に更に詳細に議論するように、種々のコンピュータハードウェア又はソフトウェアモジュールを備えた特定用途又は汎用コンピュータの使用を含み得る。

0101

本願明細書に記載した実施形態は、コンピュータにより実行可能な命令又はデータ構造を伝える又は格納しているコンピュータ可読媒体を用いて実施され得る。このようなコンピュータ可読媒体は、汎用又は特定目的コンピュータによりアクセスできる利用可能な媒体であり得る。例として且つ限定ではなく、このようなコンピュータ可読媒体は、RAM(Random Access Memory)、ROM(Read−Only Memory)、EEPROM(Electrically Erasable Programmable Read−Only Memory)、CD−ROM(Compact Disc Read−Only Memory)又は他の光ディスク記憶装置、磁気ディスク記憶装置又は他の磁気記憶装置、フラッシュメモリ装置(例えば、固体メモリ素子)を含む非一時的コンピュータ可読記憶媒体、又はコンピュータにより実行可能な命令若しくはデータ構造の形式で所望のプログラムコード手段を伝える若しくは格納するために用いられ汎用若しくは特定目的コンピュータによりアクセス可能な他の媒体を有し得る。上述の組合せも、コンピュータ可読媒体の範囲に包含され得る。

0102

コンピュータにより実行可能な命令は、例えば、汎用コンピュータ、特定目的コンピュータ(例えば、1又は複数のプロセッサ)又は特定目的処理装置に特定の機能又は機能グループを実行させる命令及びデータを有する。本発明の主題構造的特徴及び/又は方法論的動作に特有言葉で記載されたが、本発明の主題は、特許請求の範囲に定められる上述の特定の特徴又は動作に限定されないことが理解されるべきである。むしろ、上述の特定の特徴及び動作は、特許請求の範囲の実施の例示的形態として開示されたものである。

0103

本願明細書で用いられるように、用語「モジュール」又は「コンポーネント」は、モジュール若しくはコンポーネントの動作を実行するよう構成される特定ハードウェア実装、及び/又はコンピューティングシステムの汎用ハードウェア(例えばコンピュータ可読媒体、処理装置、等)に格納され及び/又はそれらにより実行され得るソフトウェアオブジェクト若しくはソフトウェアルーチンを表しても良い。幾つかの実施形態では、本願明細書に記載されたのと異なるコンポーネント、モジュール、エンジン及びサービスは、(例えば、別個のスレッドとして)コンピューティングシステムで実行されるオブジェクト又は処理として実施されても良い。

0104

本願明細書に記載のシステム及び方法の幾つかは概して(汎用ハードウェアに格納される及び/又はそれにより実行される)ソフトウェアで実装されるように記載されたが、専用ハードウェアの実装又はソフトウェアと専用ハードウェアの組み合わせの実装も可能であり考えられる。この説明では、「コンピュータエンティティ」は、本願明細書で先に定められたようにコンピューティングシステム、又はコンピューティングシステムで実行されるモジュール若しくはモジュールの組合せであっても良い。

0105

本開示で及び特に添付の特許請求の範囲(例えば、添付の特許請求の範囲の本体)で使用される用語は、概して、広義の(open)用語と考えられる(例えば、用語「含む(including)」は「含むが、限定されない」と解釈されるべきであり、用語「有する(having)」は「少なくとも有する」と解釈されるべきであり、用語「含む(includes)」は「含むが、限定されない」と解釈されるべきである)。

0106

さらに、特定数の導入された請求項の引用が意図される場合、このような意図は、請求項の中に明示的に示され、このような引用が存在しない場合はこのような意図が存在しない。例えば、理解の助けとして、以下の添付の特許請求の範囲は、請求項の引用を導入するために、「少なくとも1つの」及び「1又は複数の」をいう前置語句の使用を含み得る。しかしながら、このような語句の使用は、同じ請求項が前置語句「1又は複数」又は「少なくとも1つの」及び「a又はan」のような不定詞を含むときでも、不定冠詞「a、an」による請求項引用の導入がこのような導入された請求項引用を含む任意の特定の請求項をこのような引用を1つだけ含む実施形態に限定することを示すと考えられてはならない(例えば、「a」及び/又は「an」は「少なくとも1つの」又は「1又は複数の」を意味すると解釈されるべきである)。同様のことは、請求項引用を導入するために使用される定冠詞の使用についても該当する。

0107

さらに、特定数の導入された請求項引用が明示的に引用される場合、当業者は、このような引用が少なくとも引用された番号を意味することと解釈されるべきであることを認識するだろう(例えば、「2つの引用」はそのままで、他の変更が無ければ、少なくとも2つの引用、又は2以上の引用を意味する)。さらに、「A、B、C、等のうちの少なくとも1つ」又は「A、B、C、等のうちの1又は複数」に類似する慣例が用いられる例では、通常、このような構成は、Aのみ、Bのみ、Cのみ、A及びBを一緒に、A及びCを一緒に、B及びCを一緒に、又はA、B、Cを一緒に、等を含むと意図される。例えば、用語「及び/又は」の仕様は、このように考えられることを意図している。

0108

さらに、2以上の代替用語を表す任意の離接語又は語句は、説明、請求項、又は図面の中であるかに係わらず、用語のうちの1つ、用語のうちのいずれか、又は両方の用語を含む可能性を包含すると理解されるべきである。例えば、語句「A又はB」は、「A」又は「B」又は「A及びB」の可能性を含むと理解されるべきである。

0109

本願明細書に記載された全ての例及び条件文は、教育上の目的で、読者が本発明の原理及び発明者により考案された概念を理解するのを助け、技術を促進させるためであり、これらの特に記載された例及び条件に限定されないものと考えられるべきである。本開示の実施形態が詳細に記載されたが、種々の変更、置換及び修正が本開示の精神及び範囲から逸脱することなく行われうることが理解されるべきである。

0110

以上の実施形態に加えて、更に以下の付記を開示する。
(付記1)未知のバイナリプログラムに対する有効な入力シーケンスを決定する方法であって、前記方法は、
未知のバイナリプログラムに対する複数の入力シーケンスを得るステップであって、前記入力シーケンスの各々は、2以上の異なる入力を有し、前記入力シーケンスの入力は、前記未知のバイナリプログラムに対して有効な入力として決定される、ステップと、
各々の入力シーケンスについて別個に前記未知のバイナリプログラムの計装バージョンを実行するステップであって、前記未知のバイナリプログラムの前記計装バージョンの各々の実行は、前記未知のバイナリプログラムの前記計装バージョンへの入力として前記入力シーケンスのうちの1つを用いる、ステップと、
前記未知のバイナリプログラムの前記計装バージョンの各々の実行について、前記未知のバイナリプログラムの前記計装バージョンの前記実行により生成される実行トレースを記録することにより、実行トレースセットを生成するステップと、
前記実行トレースセットを比較するステップと、
前記実行トレースセットの比較に基づき、前記入力シーケンスのうちのどれを前記未知のバイナリプログラムが有効として受け入れるかを決定するステップと、
を有する方法。
(付記2) 前記入力は、前記未知のバイナリプログラムに対して有効であると決定されたコマンドと、前記コマンドに関連する引数と、を有し、前記引数も、前記未知のバイナリプログラムに対して有効であると決定される、付記1に記載の方法。
(付記3) 前記実行トレースセットを生成するステップは、前記実行トレースセットに含めるために、前記未知のバイナリプログラムの前記計装バージョンの各々の実行について、前記実行トレースの一部を選択するステップであって、前記実行トレースセットのために選択された前記実行トレースの一部は、前記入力シーケンスの最後の入力が前記未知のバイナリプログラムに提供された後に生成された実行トレースである、ステップを含む、付記1に記載の方法。
(付記4) 前記実行トレースセットに含めるために前記実行トレースの一部を選択するステップは、
入力を有しないで前記未知のバイナリプログラムの前記計装バージョンを実行するステップと、
入力を有しない前記実行の終わりに、前記未知のバイナリプログラムの前記計装バージョンの実行により生成された複数の実行トレースを決定するステップと、
前記決定した複数の実行トレースをパーティション実行トレースとして設定するステップと、
前記パーティション実行トレースの最後から2番目の発生と最後の発生との間に生じる実行トレースの一部に基づき、前記入力シーケンスを用いて前記未知のバイナリプログラムの前記計装バージョンの実行中に生成された実行トレースの一部を選択するステップと、
を有する、付記3に記載の方法。
(付記5) 前記実行トレースセットの各々について制御フローグラフを生成するステップ、を更に有し、
前記実行トレースセットを比較するステップは、
前記制御フローグラフの各々についてストリング表現を生成するステップと、
前記ストリング表現を比較するステップと、
を有する、付記1に記載の方法。
(付記6) 各々の制御フローグラフについて前記ストリング表現を生成するステップは、縦型探索アルゴリズム又は横型探索アルゴリズムを実施するステップを有する、付記5に記載の方法。
(付記7) 前記実行トレースセットのうちの1つのセットの中の実行トレースは、前記未知のバイナリプログラムの前記計装バージョンにより出力され且つ前記未知のバイナリプログラムの非計装バージョンにより出力されない、前記未知のバイナリプログラムの中で実行される直線的命令セットに関連するメモリアドレスを表す、付記1に記載の方法。
(付記8) 各々の入力シーケンスの中の最後の入力は同じであり、前記複数の入力シーケンスは入力シーケンスセットであり、前記方法は、複数の他の入力シーケンスセットについて付記1に記載の方法を繰り返すステップ、を更に有し、前記他の入力シーケンスセットのうちの各々のセットの各々の入力シーケンスの最後の入力は、同じであり、各々の入力シーケンスセットの最後の入力は、他の入力シーケンスセットの最後の入力と異なる、付記7に記載の方法。
(付記9) 前記実行トレースセットの比較が、前記実行トレースセットは同じであると示すとき、前記入力シーケンスのいずれも、前記未知のバイナリプログラムにより受け入れられないと決定される、付記1に記載の方法。
(付記10) 前記実行トレースセットの比較が、前記実行トレースセットのうちの1つが前記実行トレースセットのうちの同じである少なくとも別の2つと異なることを示すとき、前記実行トレースセットのうちの該1つに対応する入力シーケンスは、前記未知のバイナリプログラムにより受け入れられると決定される、付記1に記載の方法。
(付記11)命令を含む1又は複数の非一時的コンピュータ可読媒体であって、前記命令は、1又は複数のプロセッサにより実行されると、未知のバイナリプログラムに対する有効な入力シーケンスを決定する工程を実行し、前記工程は、
未知のバイナリプログラムに対する複数の入力シーケンスを得るステップであって、前記入力シーケンスの各々は、2以上の異なる入力を有し、前記入力シーケンスの入力は、前記未知のバイナリプログラムに対して有効な入力として決定される、ステップと、
各々の入力シーケンスについて別個に前記未知のバイナリプログラムの計装バージョンを実行するステップであって、前記未知のバイナリプログラムの前記計装バージョンの各々の実行は、前記未知のバイナリプログラムの前記計装バージョンへの入力として前記入力シーケンスのうちの1つを用いる、ステップと、
前記未知のバイナリプログラムの前記計装バージョンの各々の実行について、前記未知のバイナリプログラムの前記計装バージョンの前記実行により生成される実行トレースを記録することにより、実行トレースセットを生成するステップと、
前記実行トレースセットを比較するステップと、
前記実行トレースセットの比較に基づき、前記入力シーケンスのうちのどれを前記未知のバイナリプログラムが有効として受け入れるかを決定するステップと、
を有する、1又は複数の非一時的コンピュータ可読媒体。
(付記12) 前記入力は、前記未知のバイナリプログラムにより有効であると決定されたコマンドと、前記コマンドに関連する引数と、を有し、前記引数も前記未知のバイナリプログラムにとって有効であると決定される、付記11に記載の1又は複数の非一時的コンピュータ可読媒体。
(付記13) 前記実行トレースセットを生成するステップは、前記実行トレースセットに含めるために、前記未知のバイナリプログラムの前記パーティショニング済みバージョンの各々の実行について、前記実行トレースの一部を選択するステップであって、前記実行トレースセットのために選択された前記実行トレースの一部は、前記入力シーケンスの最後の入力が前記未知のバイナリプログラムに提供された後に生成された実行トレースである、ステップ、を更に有する、付記11に記載の1又は複数の非一時的コンピュータ可読媒体。
(付記14) 前記実行トレースセットに含めるために前記実行トレースの一部を選択するステップは、
入力を有しないで前記未知のバイナリプログラムの前記計装バージョンを実行するステップと、
入力を有しない前記実行の終わりに、前記未知のバイナリプログラムの前記計装バージョンの実行により生成された複数の実行トレースを決定するステップと、
前記決定した複数の実行トレースをパーティション実行トレースとして設定するステップと、
前記パーティション実行トレースの最後から2番目の発生と最後の発生との間に生じる実行トレースの一部に基づき、前記入力シーケンスを用いて前記未知のバイナリプログラムの前記計装バージョンの実行中に生成された実行トレースの一部を選択するステップと、
を更に有する、付記13に記載の1又は複数の非一時的コンピュータ可読媒体。
(付記15) 前記工程は、前記実行トレースセットの各々について制御フローグラフを生成するステップ、を更に有し、
前記実行トレースセットを比較するステップは、
前記制御フローグラフの各々についてストリング表現を生成するステップと、
前記ストリング表現を比較するステップと、
を有する、付記11に記載の1又は複数の非一時的コンピュータ可読媒体。
(付記16) 各々の制御フローグラフについて前記ストリング表現を生成するステップは、縦型探索アルゴリズム又は横型探索アルゴリズムを実施するステップを有する、付記15に記載の1又は複数の非一時的コンピュータ可読媒体。
(付記17) 前記実行トレースセットのうちの1つのセットの中の実行トレースは、前記未知のバイナリプログラムの前記計装バージョンにより出力され且つ前記未知のバイナリプログラムの非計装バージョンにより出力されない、前記未知のバイナリプログラムの中で実行される直線的命令セットに関連するメモリアドレスを表す、付記11に記載の1又は複数の非一時的コンピュータ可読媒体。
(付記18) 各々の入力シーケンスの中の最後の入力は同じであり、前記複数の入力シーケンスは入力シーケンスセットであり、前記工程は、複数の他の入力シーケンスセットについて付記11に記載の工程を繰り返すステップ、を更に有し、前記他の入力シーケンスセットのうちの各々のセットの各々の入力シーケンスの最後の入力は、同じであり、各々の入力シーケンスセットの最後の入力は、他の入力シーケンスセットの最後の入力と異なる、付記17に記載の1又は複数の非一時的コンピュータ可読媒体。
(付記19) 前記実行トレースセットの比較が、前記実行トレースセットは同じであると示すとき、前記入力シーケンスのいずれも、前記未知のバイナリプログラムにより受け入れられないと決定される、付記11に記載の1又は複数の非一時的コンピュータ可読媒体。
(付記20) 前記実行トレースセットの比較が、前記実行トレースセットのうちの1つが前記実行トレースセットのうちの同じである少なくとも別の2つと異なることを示すとき、前記実行トレースセットのうちの該1つに対応する入力シーケンスは、前記未知のバイナリプログラムにより受け入れられると決定される、付記11に記載の1又は複数の非一時的コンピュータ可読媒体。

0111

102バイナリプログラム
104入力シーケンス
110計装モジュール
112 計装バイナリプログラム
120実行モジュール
122実行トレースセット
130パーティションモジュール
132パーティショニング済み実行トレースセット
140フローグラフモジュール
142 フローグラフ
150決定モジュール
300 フローグラフ
320 実行トレース
330ストリング表現
410入力モジュール
412 入力
414 バイナリプログラム
420 実行モジュール
422命令カウント
430 入力シーケンス
500決定システム
510プロセッサ
512メモリ
514データ記憶
516 通信ユニット

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ