(57)【要約】      （修正有）【課題】自動コンピュータプログラム検査動作のための入力を識別する方法を提供する。【解決手段】自動コンピュータプログラム検査動作のための入力を識別する方法は、コンピュータ可読プログラム（以下単にプログラム）の実行中にプログラムに第１パスを取らせるためにプログラムの実行中に使用されるプログラムのための第１入力を取得するＳ５１０。プログラムの実行中にプログラムに第２パスを取らせるためにプログラムの実行中に使用されるプログラムのための第２入力を取得するＳ５２０。第１入力及び第２入力の両方に共通の値シーケンスを識別するＳ５３０。値シーケンスが第１入力及び第２入力の両方に共通であることに応答して、値シーケンスと新しい値とを含む第３入力を生成し、第３入力はプログラムの実行中に使用されるよう構成されるＳ５４０。【選択図】図５
2020119513.tif 000002
【特許請求の範囲】
【請求項１】
方法であって、
コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第１パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムの第１入力を取得するステップと、
前記コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第２パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムの第２入力を取得するステップと、
前記第１入力及び前記第２入力の両方に共通の値シーケンスを識別するステップと、
前記値シーケンスが前記第１入力及び前記第２入力の両方に共通であることに基づき、前記値シーケンス及び新しい値を含む第３入力を生成するステップであって、前記第３入力は前記コンピュータ可読プログラムの実行中に使用されるよう構成される、ステップと、
を含む方法。
【請求項２】
前記コンピュータ可読プログラムの第１反復への第１入力セットに対して第１ファジング演算を実行するステップと、
前記コンピュータ可読プログラムの第２反復への第２入力セットに対して第２ファジング演算を実行するステップであって、前記第２ファジング演算は、前記第１ファジング演算が前記第１入力セットに包含するための入力を識別するのと異なる方法で、前記第２入力セットに包含するための入力を識別する、ステップと、
を更に含み、
前記第１ファジング演算は、
前記コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第１反復パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムの前記第１入力セットから第１反復入力を取得するステップと、
前記コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第２反復パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムの前記第２入力セットから第２反復入力を取得するステップと、
前記第１反復入力及び前記第２反復入力の両方に共通の第２値シーケンスを識別するステップと、
前記第２値シーケンスが前記第１反復入力及び前記第２反復入力の両方に共通であることに基づき、前記第２値シーケンス及び別の新しい値を含む第４入力を生成するステップであって、前記第４入力は、前記コンピュータ可読プログラムの実行中に使用されるよう構成される、ステップと、
を含む、請求項１に記載の方法。
【請求項３】
第１回数だけ前記第１ファジング演算を実行するステップと、
第２回数だけ前記第２ファジング演算を実行するステップと、
前記第１入力セット及び前記第２入力セットのうちの少なくとも１つを解析して、長さ閾より長い長さを有する、前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の入力数を決定するステップと、
前記決定した入力数が待ち行列閾を満たすことに基づき、前記第１回数と前記第２回数との間の比を調整するステップと、
を更に含む請求項２に記載の方法。
【請求項４】
前記長さ閾は、前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の前記入力の全部の平均長さと、前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の前記入力の全部の長さの標準偏差と、に基づく、請求項３に記載の方法。
【請求項５】
前記待ち行列閾は、前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の入力の合計数に基づく、請求項３に記載の方法。
【請求項６】
前記新しい値は、前の入力に基づき変更される、請求項１に記載の方法。
【請求項７】
前記コンピュータ可読プログラムを取得するステップであって、前記コンピュータ可読プログラムはコード部分を含む、ステップと、
第５入力を用いて前記コンピュータ可読プログラムを実行するステップと、
前記第５入力を用いて実行されたときに前記コンピュータ可読プログラムの前記実行中に前記コード部分の実行回数を追跡するステップと、
前記コード部分の前記実行回数を、前記コンピュータ可読プログラムを実行するときの前記コード部分の前の最高実行回数と比較するステップと、
前記実行回数が前記前の最高実行回数より大きいことに応答して、
前記実行回数を前記前の最高実行回数として格納するステップと、
前記第５入力を変更動作の行われる入力プールに追加するステップと、
を更に含む請求項１に記載の方法。
【請求項８】
前記コンピュータ可読プログラムの第１反復への第３入力セットに対して第１ファジング演算を実行するステップと、
前記コンピュータ可読プログラムの第２反復への第４入力セットに対して第２ファジング演算を実行するステップであって、前記第２ファジング演算は、前記第１ファジング演算が前記第３入力セットに包含するための入力を識別するのと異なる方法で、前記第４入力セットに包含するための入力を識別する、ステップと、
を更に含み、
前記第１ファジング演算は、
前記コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第１反復パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムの前記第１入力セットから第１反復入力を取得するステップと、
前記コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第２反復パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムの前記第２入力セットから第２反復入力を取得するステップと、
前記第１反復入力及び前記第２反復入力の両方に共通の第２値シーケンスを識別するステップと、
前記第２値シーケンスが前記第１反復入力及び前記第２反復入力の両方に共通であることに基づき、
前記第２値シーケンス及び別の新しい値を含む第６入力を生成するステップと、
前記第６入力を前記第１入力セットに追加するステップと、
前記第１入力セットからの第３反復入力を用いて前記コンピュータ可読プログラムを実行するステップと、
前記第３反復入力を用いて、前記コンピュータ可読プログラムの前記実行中にコード部分の所与の実行回数を追跡するステップと、
前記所与の実行回数を、前記コンピュータ可読プログラムを実行するときの前記コード部分の前の最高実行回数と比較するステップと、
前記所与の実行回数が前記前の最高実行回数より大きいことに応答して、
前記所与の実行回数を前記前の最高実行回数として格納するステップと、
前記第３反復入力の変更されたバージョンを前記第１入力セットに追加するステップと、
を更に含む請求項１に記載の方法。
【請求項９】
第１回数だけ前記第１ファジング演算を実行するステップと、
第２回数だけ前記第２ファジング演算を実行するステップと、
前記第１入力セット及び前記第２入力セットのうちの少なくとも１つを解析して、長さ閾より長い長さを有する、前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の入力数を決定するステップと、
前記コンピュータ可読プログラムを表す制御フローグラフを取得するステップと、
前記第１ファジング演算及び前記第２ファジング演算の間に取られた前記制御フローグラフの中のパスを示すトレースを取得するステップと、
前記トレース及び前記制御フローグラフを解析して、前記コンピュータ可読プログラムの実行に関連する条件を満たし且つ前記トレースによりトラバースされない前記制御フローグラフのブランチ数を決定するステップと、
前記条件を満たし且つ前記トレースによりトラバースされない前記制御フローグラフの前記ブランチ数がトレース閾を満たすことに応答して、及び前記長さ閾より長い長さを有する前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の前記入力数が待ち行列閾を満たすことに基づき、前記第１回数と前記第２回数との間の比を調整するステップと、
を更に含む請求項８に記載の方法。
【請求項１０】
方法であって、
コード部分を含むコンピュータ可読プログラムを取得するステップと、
第１入力を用いて前記コンピュータ可読プログラムを実行するステップと、
前記第１入力を用いる前記コンピュータ可読プログラムの前記実行中に前記コード部分の実行回数を追跡するステップと、
前記コード部分の前記実行回数を、前記コンピュータ可読プログラムを実行するときの前記コード部分の前の最高実行回数と比較するステップと、
前記実行回数が前記前の最高実行回数より大きいことに応答して、
前記実行回数を前記前の最高実行回数として格納するステップと、
前記第１入力を変更動作の行われる第１入力プールに追加するステップと、
を含む方法。
【請求項１１】
前記コンピュータ可読プログラムの第１反復への第１入力セットに対して第１ファジング演算を実行するステップであって、前記第１入力セットは前記第１入力プールの変更されたバージョンを含む、ステップと、
前記コンピュータ可読プログラムの第２反復への第２入力セットに対して第２ファジング演算を実行するステップであって、前記第２入力セットは前記第２入力プールの変更されたバージョンを含み、前記第２ファジング演算は、前記第１ファジング演算が前記第１入力プールの入力を識別するのと異なる方法で、前記第２入力プールの入力を識別する、ステップと、
を更に含み、
前記第１ファジング演算は、
前記第１入力セットからの第１反復入力を用いて前記コンピュータ可読プログラムを実行するステップと、
前記第１反復入力を用いる前記コンピュータ可読プログラムの前記実行中に、前記コード部分の所与の実行回数を追跡するステップと、
前記所与の回数を前記前の最高実行回数と比較するステップと、
前記所与の回数が前記前の最高実行回数より大きいことに応答して、
前記所与の数を前記前の最高実行回数として格納するステップと、
前記第１反復入力を前記第１入力プールに追加するステップと、
を含む、請求項１０に記載の方法。
【請求項１２】
前記方法は、
第１回数だけ、前記第１ファジング演算を実行するステップと、
第２回数だけ、前記第２ファジング演算を実行するステップと、
前記コンピュータ可読プログラムを表す制御フローグラフを取得するステップと、
前記第１ファジング演算及び前記第２ファジング演算の間に、前記コンピュータ可読プログラムにより取り込まれた前記制御フローグラフの中のパスを示すトレースを取得するステップと、
前記トレース及び前記制御フローグラフを解析して、前記コンピュータ可読プログラムの実行回数に関する条件を満たし且つ前記トレースによりトラバースされない前記制御フローグラフのブランチの数を決定するステップと、
前記条件を満たし且つ前記トレースによりトラバースされない前記制御フローグラフの前記ブランチの数がトレース閾を満たすことに応答して、前記第１回数と前記第２回数との間の比を調整するステップと、
を更に有する請求項１１に記載の方法。
【請求項１３】
前記条件は、前記ブランチの実行中に１度より多く実行される第２コード部分に対応する前記制御フローグラフのブランチにより満たされる、請求項１２に記載の方法。
【請求項１４】
前記変更動作は、
前記第１入力を変更して、前記第１入力の変更されたバージョンを生成するステップと、
前記第１入力の前記変更されたバージョンを前記第１入力セットに追加するステップと、
を含む、請求項１１に記載の方法。
【請求項１５】
前記第１入力を変更する前記ステップは、
前記第１入力の中の１つ以上のビットをランダムにフリッピングするステップと、
前記第１入力の中の１つ以上の値をランダムに繰り返すステップと、
前記第１入力から１つ以上の値をランダムに除去するステップと、
前記第１入力に別の入力からの値をランダムに追加するステップと、
のうちの少なくとも１つを含む、請求項１４に記載の方法。
【請求項１６】
前記コンピュータ可読プログラムは複数のコード部分を含み、前記方法は、前記複数のコード部分のうちの所与のコード部分の各々について、
前記第１入力を用いる前記コンピュータ可読プログラムの前記実行中に、前記所与のコ―ド部分の所与の実行回数を追跡するステップと、
前記所与のコード部分の前記所与の実行回数を、前記コンピュータ可読プログラムを実行するときの前記所与のコード部分の所与の前の最高実行回数と比較するステップと、
前記所与の回数が前記所与の前の最高実行回数より大きいことに応答して、
前記所与の回数を前記所与のコード部分の前記所与の前の最高実行回数として格納するステップと、
前記第１入力を前記第１入力プールに追加するステップと、
を更に含む請求項１０に記載の方法。
【請求項１７】
前記コード部分の前記前の最高実行回数を表す８ビット数値を格納するステップ、を更に含む請求項１０に記載の方法。
【請求項１８】
コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第１パスを取らせるために前記コンピュータ可読プログラムの実行中に使用されるコンピュータ可読プログラムの第２入力を取得するステップと、
コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第２パスを取らせるために前記コンピュータ可読プログラムの実行中に使用されるコンピュータ可読プログラムの第３入力を取得するステップと、
前記第２入力及び前記第３入力の両方に共通の値シーケンスを識別するステップと、
前記値シーケンスが前記第２入力及び前記第３入力の両方に共通であることに基づき、それぞれ前記第２入力及び前記第３入力の両方に共通の前記値シーケンスとそれぞれの新しい値とを含む複数の入力を含むよう前記第１入力セットを変更するステップと、
を更に含む請求項１０に記載の方法。
【請求項１９】
前記コンピュータ可読プログラムの第１反復への第１入力セットに対して第１ファジング演算を実行するステップであって、前記第１入力セットは前記第１入力プールの中の入力の変更されたバージョンを含む、ステップと、
前記コンピュータ可読プログラムの第２反復への第２入力セットに対して第２ファジング演算を実行するステップであって、前記第２入力セットは前記第２入力プールの中の入力の変更されたバージョンを含み、前記第２ファジング演算は、前記第１ファジング演算が前記第１入力プールの入力を識別するのと異なる方法で、前記第２入力プールの入力を識別する、ステップと、
を更に含み、
前記第２入力及び前記第３入力の両方に共通の前記値シーケンスをそれぞれ含む前記複数の入力は、前記第１ファジング演算を用いて生成され、前記第１ファジング演算は、
前記第１入力セットからの反復入力を用いて前記コンピュータ可読プログラムを実行するステップと、
前記反復入力を用いる前記コンピュータ可読プログラムの前記実行中に、前記コード部分の所与の実行回数を追跡するステップと、
前記所与の回数を前記前の最高実行回数と比較するステップと、
前記所与の回数が前記前の最高実行回数より大きいことに応答して、
前記所与の回数を前記前の最高実行回数として格納するステップと、
前記反復入力を前記第１入力プールに追加するステップと、
を更に含む、請求項１８に記載の方法。
【請求項２０】
第１回数だけ前記第１ファジング演算を実行するステップと、
第２回数だけ前記第２ファジング演算を実行するステップと、
前記コンピュータ可読プログラムを表す制御フローグラフを取得するステップと、
前記第１ファジング演算及び前記第２ファジング演算からトレースを取得するステップと、
前記トレース及び前記制御フローグラフを解析して、条件を満たし且つ前記トレースによりカバーされない前記制御フローグラフのブランチ数を決定するステップと、
前記第１入力セット及び前記第２入力セットのうちの少なくとも１つを解析して、長さ閾より長い長さを有する、前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の入力数を決定するステップと、
前記条件を満たし且つ前記トレースによりカバーされない前記制御フローグラフの前記ブランチ数がトレース閾を満たすことに応答して、及び前記長さ閾より長い長さを有する前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の前記入力数が待ち行列閾を満たすことに基づき、前記第１回数と前記第２回数との間の比を調整するステップと、
を更に含む請求項１９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示で議論される実施形態は、自動コンピュータプログラム検査動作のための入力を識別することに関する。
【背景技術】
【０００２】
コンピュータプログラムは、多くの産業において重要である。コンピュータプログラム開発、検査、及び／又はデバッグは、コンピュータプログラム検査及び／又はデバッグの幾つかの側面を支援し又は自動化するツールから利益を享受し得る。
【発明の概要】
【０００３】
本開示の一実施形態は、コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第１パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムのための第１入力を取得するステップを含む方法を含んでよい。当該方法は、前記コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第２パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムのための第２入力を取得するステップを更に含んでよい。当該方法は、前記第１入力及び前記第２入力の両方に共通の値シーケンスを識別するステップを更に含んでよい。当該方法は、前記値シーケンスが前記第１入力及び前記第２入力の両方に共通であることに基づき、前記値シーケンスと新しい値とを含む第３入力を生成するステップであって、前記第３入力は、前記コンピュータ可読プログラムの実行中に使用されるよう構成される、ステップを更に含んでよい。
【０００４】
本開示の別の実施形態は、コード部分を含むコンピュータ可読プログラムを取得するステップを含む方法を含んでよい。当該方法は、第１入力を用いてコンピュータ可読プログラムを実行するステップを更に含んでよい。前記方法は、前記第１入力を用いる前記コンピュータ可読プログラムの前記実行中の前記コード部分の実行数を追跡するステップを更に含んでよい。前記方法は、コード部分の実行回数を、前記コンピュータ可読プログラムを実行するときの前記コード部分の前の最高実行回数と比較するステップを更に含んでよい。前記方法は、前記実行回数が前記前の最高実行回数より大きいことに応答して、実前記行回数を前記前の最高実行回数として格納するステップを更に含んでよい。前記方法は、前記実行回数が前記前の最高実行回数より大きいことに応答して、前記第１入力を、変更動作の対象である第１入力プールに追加するステップを更に含んでよい。
【０００５】
実施形態の目的及び利点のうちの１つ以上が、少なくとも特に特許請求の範囲で指摘された要素、特徴及び組合せにより実現され又は達成されるだろう。
【０００６】
上述の全体的説明及び以下の詳細な説明の両方は、例示及び説明のために与えられ、本開示の範囲を限定しないことが理解される。
【図面の簡単な説明】
【０００７】
例示的な実施形態は、添付の図面を用いて、更なる特異性及び詳細事項と共に記載され説明される。
【０００８】
【図１】自動コンピュータプログラム検査動作のための入力を識別する例示的なシステムのブロック図である。
【０００９】
【図２Ａ】自動コンピュータプログラム検査動作のための入力を識別する別の例示的なシステムのブロック図である。
【００１０】
【図２Ｂ】自動コンピュータプログラム検査動作のための入力を識別する際に使用される例示的な入力及びプログラムパスを示す。
【００１１】
【図３】自動コンピュータプログラム検査動作のための入力を識別する別の例示的なシステムのブロック図である。
【００１２】
【図４】自動コンピュータプログラム検査動作を行う例示的なシステムのブロック図である。
【００１３】
【図５】自動コンピュータプログラム検査動作のための入力を識別する例示的な処理のフローチャートである。
【００１４】
【図６】自動コンピュータプログラム検査動作のための入力を識別する別の例示的な処理のフローチャートである。
【００１５】
【図７】例示的なコンピューティングシステムのブロック図である。
【００１６】
全ての図は本開示に記載の少なくとも１つの実施形態に従う。
【発明を実施するための形態】
【００１７】
本開示は、自動コンピュータプログラム検査動作に関する。特に、本開示は、自動コンピュータプログラム検査を実行するための有用な入力を識別することに関する。幾つかの実施形態では、有用な入力は、共通の値シーケンスを共有する２以上の入力を識別することにより、及び該共通の値シーケンスを含むが他の値も含む新しい値を生成することにより、識別され得る。追加又は代替として、幾つかの実施形態では、入力は、特定プログラムコードセクションがコンピュータプログラムの自動検査中に前に実行されたより多くの回数だけ、該特定のプログラムコードセクションを実行させる入力を選択することにより識別されてよい。このような入力は、（例えば、複数回実行されているプログラムコードの特定セクションを生じる入力を変更することにより）新しい入力の基礎を形成する。
【００１８】
本開示は、入力の識別、及び入力、プログラム動作、等の様々な識別された側面に基づきどんな種類の入力識別が使用されるかの比の平衡化のための複数のアプローチを用いることにも関連し得る。
【００１９】
本開示のこのような実施形態は、特定の方法でコンピュータの動作を向上する。例えば、本開示の実施形態は、自動コンピュータプログラム検査動作を促進して、有用な入力を識別することにより一層効率的に動作し得る。例えば、自動コンピュータプログラム検査動作の目標がコンピュータプログラムを複数回又は全部のブランチを検査することである場合、有用な入力を識別することは、自動コンピュータプログラム検査動作が、前に実行されなかったブランチの実行を引き起こし得る入力を、他の自動コンピュータプログラム検査動作、例えば標準的なファジングより速く識別することを可能にし得る。例えば、本開示の実施形態は、自動コンピュータプログラム検査動作の目標を達成する可能性がランダム入力よりも高くなり得る有用な入力を識別することにより、計算時間及び／又はリソースを節約し得る。
【００２０】
追加又は代替として、本開示の実施形態は、コンピューティングリソースをより効率的に割り当てるために複数の自動コンピュータプログラム検査動作の間の比を調整することにより、自動コンピュータプログラム検査動作の効率を向上し得る。例えば、幾つかの例では、第１ファジング演算は、第２ファジング演算よりも、特定コンピュータプログラムにより良好に適することがある。第１及び第２ファジング演算を用いてコンピューティングリソースの間の比を調整することにより、コンピューティングリソース及び／又はコストが節約され得る。
【００２１】
図１は、本開示に記載の少なくとも一実施形態による、自動コンピュータプログラム検査動作のための入力を識別する例示的なシステム１００のブロック図である。システム１００は、入力セット１０２からの１つ以上の入力を用いてコンピュータ可読プログラムコード１４０を実行し得るコンピュータ可読プログラム実行部１２０を含んでよい。例えば、入力セット１０２からの入力は、コンピュータ可読プログラムコード１４０の実行において使用されてよい。その結果、入力セット１０２の所与の入力に基づくコンピュータ可読プログラムコード１４０の実行が観察され得る。コンピュータ可読プログラムコード１４０の実行に基づき、入力セット１０２からの１つ以上の入力は、入力プール１１２に追加されてよい。入力プール１１２からの１つ以上の入力は、入力セット１０２に追加されるべき追加入力を生成するために、変更部１３０により変更されてよい。
【００２２】
幾つかの実施形態では、コンピュータ可読プログラムコード１４０は、任意の適切なフォーマットの任意のコンピュータ可読プログラムからのコードであってよい。コンピュータ可読プログラムコード１４０は、自動コンピュータプログラム検査動作の対象であると識別され又は選択されてよい。
【００２３】
幾つかの実施形態では、入力セット１０２は、任意の適切なフォーマット（例えば、バイナリ、１６進数、又はASCII（American  Standard  code  for  Information  Interchange））の、コンピュータ可読プログラム１２０の実行のために提供されるべき１つ以上の値又はデータセットを含んでよい。幾つかの実施形態では、入力セット１０２は、例えば検査のための初期入力セット１０２のために、ランダムに生成されてよい。追加又は代替として、入力セット１０２は、１つ以上の他の入力（例えば、共通入力のリスト）に基づき生成された入力を含んでよい。及び／又は、入力セット１０２は、コンピュータ可読プログラムコード１４０に関連する又はそれに基づく入力を含んでよい。例えば、入力セット１０２は、どんな種類の入力がコンピュータ可読プログラムコード１４０により受け付けられるか又は期待されるかに基づき生成された入力を含んでよい。
【００２４】
幾つかの実施形態では、コンピュータ可読プログラム実行部１２０は、入力セット１０２からの１つ以上の入力を用いてコンピュータ可読プログラムコード１４０を実行するよう構成されてよい。例えば、コンピュータ可読プログラム実行部１２０は、各実行のために、入力セット１０２からの異なる入力を用いてコンピュータ可読プログラムコード１４０を繰り返し実行するよう構成されてよい。入力セット１０２からの入力を用いるコンピュータ可読プログラムコード１４０の実行に基づき、コンピュータ可読プログラム実行部１２０は、入力プール１１２に追加するために、入力セット１０２からの１つ以上の入力を選択するよう構成されてよい。例えば、コンピュータ可読プログラム実行部１２０は、特定入力に関連する入力に対する更なる実行が有用である又は関心があるか否かを決定するよう構成されてよい。
【００２５】
幾つかの実施形態では、コンピュータ可読プログラム実行部１２０は、特定入力に関連する入力に対する更なる実行が有用であり得るか否かを決定するために使用される１つ以上の基準を含んでよい。例えば、自動コンピュータプログラム検査動作の目標は、コンピュータ可読プログラムを複数回又は全部のブランチを検査することであってよい。コンピュータ可読プログラム実行部１２０は、入力セット１０２からの異なる入力を用いる実行により実行されたブランチを観察し及び／又は記録するよう構成されてよい。コンピュータ可読プログラム実行部１２０は、入力プール１１２への追加のために、コンピュータ可読プログラムコード１４０の実行を任意の前の実行により到達しなかったブランに到達させる入力を選択するよう構成されてよい。追加又は代替として、入力プール１１２への包含のために入力を選択する基準も考慮される。該基準の更なる例は、図３に関連して更に議論される。
【００２６】
幾つかの実施形態では、コンピュータ可読プログラム実行部１２０は、コンピュータ可読プログラムコード１４０を検査するよう構成されてよい。例えば、コンピュータ可読プログラム実行部１２０は、入力セット１０２からの種々の入力を用いてコンピュータ可読プログラムコード１４０の実行結果を観察及び／又は記録するよう構成されてよい。例えば、コンピュータ可読プログラム実行部１２０は、強制終了、予期しない動作、脆弱性、期待されるプログラム動作、又は他の結果を記録してよい。このように、本開示の実施形態は、コンピュータ可読プログラムの自動コンピュータ可読プログラム検査動作が進行している間に、コンピュータ可読プログラムの自動検査のための入力を識別し得る。
【００２７】
幾つかの実施形態では、コンピュータ可読プログラム実行部１２０は、コンピューティングシステムが自動コンピュータ可読プログラム検査動作のための入力を識別することに関連する１つ以上の動作を実行することを可能にするよう構成されるコード及びルーチンを含んでよい。追加又は代替で、コンピュータ可読プログラム実行部１２０は、プロセッサ、（例えば、１つ以上の動作を実行する又はその実行を制御する）マイクロプロセッサ、FPGA（field−programmable  gate  array）及び／又はASIC（application−specific  integrated  circuit）を含むハードウェアを用いて実装されてよい。幾つかの他の例では、コンピュータ可読プログラム実行部１２０は、ハードウェア及びソフトウェアの組み合わせを用いて実装されてよい。本開示では、コンピュータ可読プログラム実行部１２０により実行されるとして記載される動作は、コンピュータ可読プログラム実行部１２０がシステムに実行するよう指示し得る動作を有してよい。
【００２８】
幾つかの実施形態では、入力プール１１２は、入力セット１０２から選択された１つ以上の入力を含んでよい。特定入力が、特定入力に関連する入力に基づく更なる検査が有用であり得るという決定に基づき、入力プール１１２に含まれてよい。
【００２９】
幾つかの実施形態では、変更部１３０は、１つ以上の入来する入力、例えば入力プール１１２からの所与の入力を変更して、入来する入力に基づき１つ以上の新しい入力を生成するよう構成されてよい。例えば、入来する入力が与えられると、変更部１３０は、該入来する入力の１つ以上の値を変更し、１つ以上の新しい値を入来する入力に追加し、又は１つ以上の値を入来する入力から除去して、入力セット１０２に追加されるべき新しい入力を生成してよい。上述及び他の実施形態で、追加される新しい値は、ランダムに生成され、他の入力から取り込まれ、又は入力値リスト（例えば、一般的なエラーを含む値のリスト）から取り込まれてよい。
【００３０】
幾つかの実施形態では、変更部１３０により使用される変更の技術は、入力プール１１２の中の１つより多くの入力に基づいてよい。例えば、変更部１３０は、入力プール１１２の１つより多くの入力に共通の値を識別し、入力プール１１２の１つより多くの入力に共通の値に追加する際に特定の値を変更して、入力セット１０２の新しい入力を生成するよう構成されてよい。追加又は代替として、変更部１３０は、入力プール１１２の１つ以上の入力の部分を結合して、新しい入力を形成するよう構成されてよい。変更の技術の１つ以上の例は、図２Ａ及び２Ｂに関連して以下により詳細に記載される。
【００３１】
幾つかの実施形態では、変更部１３０は、コンピュータシステムに入力を変更するための１つ以上の動作を実行させるよう構成されるコード及びルーチンを含んでよい。追加又は代替で、変更部１３０は、プロセッサ、（例えば、１つ以上の動作を実行する又はその実行を制御する）マイクロプロセッサ、FPGA（field−programmable  gate  array）及び／又はASIC（application−specific  integrated  circuit）を含むハードウェアを用いて実装されてよい。幾つかの他の例では、変更部１３０は、ハードウェア及びソフトウェアの組み合わせを用いて実装されてよい。本開示では、変更部１３０により実行されるとして記載される動作は、変更部１３０が対応するシステムに実行するよう指示し得る操作を有してよい。
【００３２】
システム１００の動作の一例として、コンピュータ可読プログラムコード１４０は、自動コンピュータプログラム検査動作の対象であるソフトウェアであってよい。コンピュータ可読プログラム実行部１２０は、コンピュータ可読プログラムコード１４０を検査するよう構成されてよい。入力セット１０２は、コンピュータ可読プログラムコード１４０の実行中に使用される入力であってよい。コンピュータ可読プログラム実行部１２０が入力セット１０２からの入力を用いてコンピュータ可読プログラムコード１４０を実行しているとき、コンピュータ可読プログラム実行部１２０は、実行のうちのいずれかが１つ以上の基準を満たすかどうかを決定してよい。
【００３３】
例えば、検査の目標は、コンピュータ可読プログラムコード１４０を複数回又は全部のブランチを検査することであってよい。基準は、前に実行されなかったブランチの実行を引き起こす任意の入力が、基準を満たすこと、であってよい。このような基準は、前に実行されなかったブランチに実行を到達させる任意の入力が、更に前に実行されなかったブランチに実行を到達させ得る可能な変形を有する、という前提に基づいてよい。別の基準は、ブランチが前に実行されたより多くの回数だけブランチの実行を引き起こす任意の入力が、基準を満たすこと、であってよい。
【００３４】
入力セット１０２の特定入力を用いるコンピュータ可読プログラムコード１４０の実行が基準を満たすことに基づき、該特定入力は、入力プール１１２に追加されてよい。変更部１３０は、入力プール１１２の中の入力を変更して、更なる検査のために、入力セット１０２に追加されるべき、このような入力の変更バージョンを生成するよう構成されてよい。
【００３５】
例えば、入力セット１０２からの入力「EBPM０００１」を用いるコンピュータ可読プログラムコード１４０の実行が、コンピュータプログラムを前の未到達ブランチに到達させた場合、該入力は入力プール１１２に含まれてよい。変更部１３０は、該入力を変更して、例えば「EBPM０００２」、「EBPM００１０」、及び「PMEB０００１」のような入力を生成してよい。変更された入力の各々は、入力セット１０２に追加されてよく、コンピュータ可読プログラムコード１４０の後の実行の間に使用されてよい。
【００３６】
本開示の範囲から逸脱することなくシステム１００に対し変更、追加又は省略が行われてよい。例えば、幾つかの実施形態では、並列に動作するコンピュータ可読プログラム実行部１２０の複数のインスタンスがあってよい。コンピュータ可読プログラム実行部１２０の複数のインスタンスは、同じコンピュータ可読プログラムコード１４０を用いて、入力セット１０２及び／又は入力プール１１２を操作してよい。同様に、変更部１３０の複数のインスタンスがあってよい。さらに、動作の順序は、異なる実装に従い変化してよい。
【００３７】
図２Ａは、本開示に記載の少なくとも一実施形態による、自動コンピュータプログラム検査動作のための入力を識別する別の例示的なシステム２００のブロック図である。システム２００は、図１のシステム１００に関して上述したものと同様又は同じであってよい、入力セット１０２、入力プール１１２、コンピュータ可読プログラム実行部１２０、変更部１３０、及びコンピュータ可読プログラムコード１４０を含んでよい。
【００３８】
図２Ａには５個の入力が示される。第１入力２０６Ａ、第２入力２０６Ｂ、第３入力２０６Ｃ、第４入力２０６Ｄ、及び第５入力２０６Ｅ（集合的に入力２０６と呼ばれる）である。図示の５個の入力２０６の各々は、値シーケンスを含んでよい。したがって、図２Ａには５個の値シーケンス、つまり、第１値シーケンス２０８Ａ、第２値シーケンス２０８Ｂ、第３値シーケンス２０８Ｃ、第４値シーケンス２０８Ｄ、第５値シーケンス２０８Ｅ（集合的に、値シーケンス２０８と呼ばれる）が示される。図示の５個の入力２０６の各々は、値を含んでよい。したがって、図２Ａには５個の値が示される、つまり、第１値２０９Ａ、第２値２０９Ｂ、第３値２０９Ｃ、第４値２０９Ｄ、及び第５値２０９Ｅ（集合的に値２０６と呼ばれる）である。しかしながら、入力、値シーケンス、及び／又は値の数は、異なる実装に従い変化してよい。
【００３９】
幾つかの実施形態では、コンピュータ可読プログラム実行部１２０は、入力２０６を用いてコンピュータ可読プログラムコード１４０を実行してよい。例えば、コンピュータ可読プログラム実行部１２０は、コンピュータ可読プログラムコード１４０を、ある実行中に第１入力２０６Ａを用いて、別の実行中に第２入力２０６Ｂを用いて実行してよい。第１入力２０６Ａ及び第２入力２０６Ｂの各々は、第１入力２０６Ａ及び第２入力２０６Ｂが入力プール１１２の含むべきものとして入力を識別する基準のうちの１つ以上を満たすことに基づき、入力プール１１２に包含するために選択されてよい。説明の目的で、第１入力２０６Ａは、第３入力２０６Ｃとして入力プール１１２に含まれてよい。そして、第２入力２０６Ｂは、第４入力２０６Ｄとして入力プール１１２に含まれてよい。
【００４０】
幾つかの実施形態では、変更部１３０は、入力プール１１２の中の入力の１つ以上に基づき、新しい入力を生成してよい。例えば、変更部１３０は、第３入力２０６Ｃ及び第４入力２０６Ｄのうちの１つ以上に基づき、第５入力２０６Ｅを生成してよい。幾つかの実施形態では、変更部１３０は、第３入力２０６Ｃ及び第４入力２０６Ｄのうちの両方に基づき、第５入力２０６Ｅを生成してよい。幾つかの実施形態では、変更部１３０は、入力プール１１２の中の入力２０６の１つ以上に共通の値シーケンス２０８を保持することにより、変更された入力を生成してよい。例えば、第３入力２０６Ｃ及び第４入力２０６Ｄの各々は、第３入力２０６Ｃ及び第４入力２０６Ｄの両方に共通の値シーケンス２０８を含んでよい。例えば、第３値シーケンス２０８Ｃ及び第４値シーケンス２０８Ｄは同じ値を含んでよい。さらに、第３入力２０６Ｃ及び第４入力２０６Ｄは、異なる１つ以上の値を含んでよい。例えば、第３入力２０６Ｃ及び第４入力２０６Ｄは、異なる値であってよい。変更部１３０は、第３及び／又は第４値２０９Ｃ／２０９Ｄを変更してよい。例えば、図２Ａを参照して、第３入力２０６Ｃは「EBPM２０１８」であってよく、第４入力２０６Ｄは「EBPM１９７０」であってよく、第３値シーケンス２０８Ｃ及び第４値シーケンス２０８Ｄは両方とも「EBPM」であってよく、第３値２０９Ｃは「２０１８」であってよく、第４値２０９Ｄは「１９７０」であってよい。
【００４１】
幾つかの実施形態では、変更部１３０は、入力プール１１２の入力２０６のうちの１つ以上の間の１つ以上の共通点を識別するよう構成されてよい。変更部１３０は、入力プール１１２の入力２０６の間の共通点に基づき、追加入力を生成するよう構成されてよい。例えば、変更部１３０は、値シーケンス２０８Ｃが第４値シーケンス２０８Ｄ、例えば「EBPM」と同じであることを識別してよい。追加又は代替として、変更部１３０は、第５入力２０６Ｅが第３値シーケンス２０８Ｃ及び第４値シーケンス２０８Ｄ、例えば「EBPM」と同じである第５値シーケンス２０８Ｅを含むように、第５入力２０６Ｅを生成するよう構成されてよい。
【００４２】
追加又は代替として、変更部１３０は、第５入力２０６Ｅが第３値２０９Ｃ及び第４値２０９Ｄのいずれかと異なる第５値２０９Ｅを含むように、第５入力２０６Ｅを生成するよう構成されてよい。例えば、第５値２０９Ｅは「１７７６」であってよく、その結果、第５入力２０６Ｅは「EBPM１７７６」であってよい。
【００４３】
値の変化の一例では、幾つかの実施形態で、第５値２０９Ｅは、例えば第３値２０９Ｃ及び／又は第４値２０９Ｄのような１つ以上の値に基づきランダムに生成されてよい。例えば、変更部１３０は、第３値２０９Ｃの１つ以上のビットをランダムにフリップし、第３値２０９Ｃのセクションを繰り返し、第３値２０９Ｃの部分を除去し、及び／又は第３値２０９Ｃの部分を第４値２０９Ｄの部分と結合してよい。追加又は代替として、第５値２０９Ｅは、１つ以上の他の値に基づいてよい。例えば、第５値２０９Ｅは共通の値のリストから取得されてよい。追加又は代替として、第５値２０９Ｅはランダムに生成されてよい。
【００４４】
本開示の範囲から逸脱することなくシステム２００に対し変更、追加又は省略が行われてよい。例えば、３個の入力のみが入力セット１０２に示され、２個の入力のみが入力プール１１２に示されるが、入力セット１０２及び入力プール１１２の各々は、数百又は数千又はそれより多くの入力のような、任意の数の入力を含んでよい。さらに、第５入力２０６Ｅは、単一の入力であるとして記載されたが、任意の数の入力が値シーケンス２０８に基づき生成されてよい。さらに、第５入力２０６Ｅは、２個の入力、つまり第３値２０６Ｃ及び第４入力２０６Ｄに基づくように記載されたが、第５入力２０６Ｅは任意の数の入力２０６に基づいてよい。さらに、動作の順序は、異なる実装に従い変化してよい。
【００４５】
図２Ｂは、本開示に記載の少なくとも一実施形態による、自動コンピュータプログラム検査動作のための入力を識別する際に使用される例示的な入力２０６及びプログラムパス２０７を示す。例えば、図２Ｂは、図２Ａに関して原文通りに何が記載されたかを視覚的に示し得る。
【００４６】
例えば、第１入力２０６Ａは「EBPM２０１８」であってよく、コンピュータ可読プログラムコード１４０の実行に第５パス２０７Ａを取らせてよい。第５パス２０７Ａは、自動コンピュータプログラム検査動作の間に、コンピュータ可読プログラムコードの任意の前の実行により取られなくてよい。したがって、第１入力２０６Ａは、入力プール１１２への包含のための基準を満たし、したがって、入力プール１１２への包含のために第３入力２０６Ｃとして選択されてよい。第２入力２０６Ｂは「EBPM１９７０」であってよく、コンピュータ可読プログラムコード１４０の実行に第２パス２０７Ｂを取らせてよい。第２パス２０７Ｂは、自動コンピュータプログラム検査動作の間に、コンピュータ可読プログラムコードの任意の前の実行により取られなくてよい。したがって、第２入力２０６Ｂは、入力プール１１２への包含のための基準を満たし、したがって、入力プール１１２への包含のために第４入力２０６Ｄとして選択されてよい。しかしながら、任意の基準が本開示と調和する。
【００４７】
幾つかの実施形態では、変更部１３０は、第３入力２０６Ｃ及び第４入力２０６Ｄの両方が同じ値シーケンス２０８、例えば「EBPM」を含むと識別するよう構成されてよい。
【００４８】
幾つかの実施形態では、変更部１３０は、値シーケンス２０８、例えば「EBPM」を第５値シーケンス２０８Ｅとして含むよう、第５入力２０６Ｅを生成するよう構成されてよい。変更部１３０は、第３入力２０６Ｃ及び第４入力２０６Ｄの値、例えば「１７７６」と異なってよい第５入力２０６Ｅに含むよう、１つ以上の新しい値２０９Ｅを生成するよう構成されてよい。
【００４９】
図３は、本開示に記載の少なくとも一実施形態による、自動コンピュータプログラム検査動作のための入力を識別する別の例示的なシステム３００のブロック図である。システム３００は、図１のシステム１００及び／又は図２のシステム２００に関して上述したものと同様又は同じであってよい、入力セット１０２、入力プール１１２、コンピュータ可読プログラム実行部１２０、変更部１３０、及びコンピュータ可読プログラムコード１４０を含んでよい。しかしながら、入力プール１１２に含まれるべき入力を選択するための基礎は、追加又は代替の基礎を含んでよい。
【００５０】
幾つかの実施形態では、コード部分３４２は、コンピュータ可読プログラムコード１４０の一部分を含んでよい。コード部分３４２は、任意のサイズの一部分を含んでよい。例えば、コード部分３４２は、コンピュータ可読プログラムコード１４０を関数、メソッド、ブロック、コードライン、演算命令のブロック、又は個別演算命令に分割してよい。コンピュータ可読プログラムコード１４０の全体は、コード部分３４２に分割されてよい。追加又は代替として、具体的に検査されているコンピュータ可読プログラムコード１４０の一部は、コード部分３４２に分割されてよい。
【００５１】
幾つかの実施形態では、コンピュータ可読プログラム実行部１２０は、コンピュータ可読プログラムコード１４０の実行毎に、コード部分３４２の各々の実行回数を追跡してよい。例えば、コンピュータ可読プログラム実行部１２０は、入力セット１０２の第１入力を用いてコンピュータ可読プログラムコード１４０を実行してよい。コンピュータ可読プログラム実行部１２０は、コード部分３４２の各々が第１入力を用いる実行中に何回実行されるかを追跡してよい。
【００５２】
幾つかの実施形態では、コンピュータ可読プログラム実行部１２０は、コード部分３４２の各々の最大実行回数を最大実行数３２２として格納するよう構成されてよい。最大実行数３２２は、各コード部分３４２がコンピュータ可読プログラムコード１４０の前の実行中に実行された最大回数を含んでよい。
【００５３】
幾つかの実施形態では、コンピュータ可読プログラム実行部１２０は、入力セット１０２からの特定入力を用いてコンピュータ可読プログラムコード１４０を実行するよう構成されてよい。コンピュータ可読プログラム実行部１２０は、各コード部分３４２の実行回数を追跡するよう構成されてよい。コンピュータ可読プログラム実行部１２０は、各コード部分３４２の実行回数の各々を最大実行数３２２の中の対応する実行回数と比較するよう構成されてよい。特定入力を用いる実行が、特定コード部分３４２が任意の前の実行の間に実行された及び最大回数３２２に記録されたより多くの回数だけ、コンピュータ可読プログラム実行部１２０に特定コード部分３４２を実行させた場合、コンピュータ可読プログラム実行部１２０は、該特定入力を入力プール１１２に含め、最大回数３２２を更新するよう構成されてよい。
【００５４】
表１は、入力の例、及びコンピュータ可読プログラム実行部１２０の応答を与える。
表１
【表１】
2020119513.tif 000003
【００５５】
例えば、表１を参照すると、コンピュータ可読プログラムコード１４０の部分「a→b」は、特定入力Xを用いるコンピュータ可読プログラムコード１４０の実行の前に、コンピュータ可読プログラムコード１４０の任意の実行中に、最大でも１回実行され得る。同様に、コンピュータ可読プログラムコード１４０の前の実行中に、部分「b→c」は３回実行されてよく、部分「c→d」は１回実行されてよく、部分「d→e」は６回実行されてよい。各部分の最大実行回数は、最大実行数３２２に格納されてよい。例えば、最大実行数３２２は、表１の第２列に提示する情報を含んでよい。
【００５６】
コンピュータ可読プログラム実行部１２０は、入力Xを用いてコンピュータ可読プログラムコード１４０を実行してよい。これに応答して、部分「a→b」は１回実行されてよく、部分「b→c」は１回実行されてよく、部分「c→d」は３回実行されてよく、部分「d→e」は６回実行されてよい。
【００５７】
コンピュータ可読プログラム実行部１２０は、各部分の実行回数を最大実行数３２２に格納された対応する部分の実行回数と比較してよい。例えば、入力Xを用いる実行中の１回の部分「a→b」の実行は、入力Xの前の入力により部分「a→b」が実行された１回と比較されてよい。部分「a→b」が同じ回数だけ実行されていることに応答して、入力Xを入力プール１１２に追加することなく、入力Xが廃棄されるべきか否かを決定するために、残りの部分がチェックされてよい。
【００５８】
入力Xを用いる実行中の１回の部分「b→c」の実行は、入力Xの前の入力により部分「b→c」が実行された３回と比較されてよい。部分「b→c」が前の実行の間より多くの回数だけ実行されていることに応答して、入力Xを入力プール１１２に追加することなく、入力Xが廃棄されるべきか否かを決定するために、残りの部分がチェックされてよい。
【００５９】
入力Xを用いる実行中の３回の部分「c→d」の実行は、入力Xの前の入力により部分「c→d」が実行された１回と比較されてよい。部分「c→d」が、任意の前の実行より多くの回数だけ、入力Xを用いる実行中に実行されていることに応答して、入力Xは入力プール１１２に追加されてよく、最大実行数３２２は、部分「c→d」が入力Xを用いて実行された回数に更新されてよい。例えば、最大実行数３２２は、表１の第２列を表す情報を表すよう更新されてよい。
【００６０】
入力Xを用いる実行中の６回の部分「d→e」の実行は、入力Xの前の入力により部分「d→e」が実行された６回と比較されてよい。部分「d→e」が同じ回数だけ実行されていることに応答して、何も起こらなくてよい。
【００６１】
コンピュータ可読プログラム実行部１２０は、コード部分が前に実行されたより多くの回数の該コード部分の実行を、入力プール１１２への包含のために入力を選択する基準として使用するよう構成されてよい。コード部分が前に実行されたより多くの回数だけコード部分の実行を生じる入力は、更なる検査のために有用であり得る。
【００６２】
幾つかの実施形態では、最大実行数３２２は、特定コード部分の各々を表す１つのコンポーネントを有するデータ構造により表されてよい。例えば、最大実行数３２２は、コンピュータ可読プログラムコード１４０内の各コード部分について８ビットの数値、例えば０から２５５までの整数を含んでよい。上述及び他の実施形態では、検査が、コンピュータプログラムに２５５より多くの回数だけ特定コード部分を実行させる場合、追加情報が失われることがある。このようなアプローチは、データ構造が本願明細書に記載の改良されたアプローチを利用することを可能にし得ると同時に、情報を格納するために少量のコンピュータリソースしか利用しない。幾つかの実施形態では、本願明細書に記載のアプローチは、伝統的なファジング演算と比べて、同量の又は少量の記憶コンピューティングリソースを利用し得る。
【００６３】
本開示の範囲から逸脱することなくシステム３００に対し変更、追加又は省略が行われてよい。さらに、動作の順序は、異なる実装に従い変化してよい。
【００６４】
図４は、本開示に記載の少なくとも一実施形態による、自動コンピュータプログラム検査動作を行う例示的なシステム４００のブロック図である。通常、システム４００は、自動コンピュータプログラム検査動作を、２以上の異なるファジング演算４５０を用いてコンピュータ可読プログラムコード１４０に対して行ってよい。コンピュータ可読プログラムコード１４０は、図１、２Ａ及び／又は３のコンピュータ可読プログラムコード１４０と同じ又は実質的に同様であってよい。ファジングバランサ４６０は、２以上の異なるファジング演算４５０の間のバランスを決定してよい。
【００６５】
２つのファジング演算は図４に示される。つまり、第１ファジング演算４５０Ａ、及び第２ファジング演算４５０Ｂである（集合的に、ファジング演算４５０と呼ばれる）。図示のファジング演算４５０の各々は、コンピュータ可読プログラム実行部１２０を含んでよい。したがって、２個のコンピュータ可読プログラム実行部１２０が図４に示される。つまり、コンピュータ可読プログラム実行部１２０Ａ、及びコンピュータ可読プログラム実行部１２０Ｂである（集合的に、コンピュータ可読プログラム実行部１２０と呼ばれる）。図示のファジング演算４５０の各々は、入力セット１０２を含んでよい。したがって、２個の入力セット１０２が図４に示される。つまり、第１入力セット１０２Ａ、及び第２入力セット１０２Ｂである（集合的に、入力セット１０２と呼ばれる）。しかしながら、ファジング演算４５０、コンピュータ可読プログラム実行部１２０、及び／又は入力セット１０２の数は、異なる実装に従い変化し得る。
【００６６】
幾つかの実施形態では、１つ以上のファジング演算４５０は、図１のシステム１００、図２Ａのシステム２００、及び／又は図３のシステム３０と同様又は同じであってよい。例えば、１つ以上のファジング演算４５０は、図３のシステム３００が入力セット１０２の入力を識別する方法と同様に、入力セット１０２の入力を識別してよい。追加又は代替として、１つ以上のファジング演算４５０は、図２Ａのシステム２００が入力を変更する方法と同様に、入力を変更してよい。このように、図示されないが、ファジング演算４５０は、それぞれ入力プール及び変更部を含んでよい。追加又は代替として、１つ以上のファジング演算４５０は、図２Ａのシステム及び／又は図３のシステム３００の両方の１つ以上の特徴を含んでよい。追加又は代替として、１つ以上のファジング演算４５０は、図１のシステム１００、図２Ａのシステム２００、及び／又は図３のシステム３０と異なってよい。
【００６７】
システム４００は、２つ以上の異なる自動コンピュータプログラム検査動作を２つ以上の異なるファジング演算４５０を用いて実行するよう構成されてよい。ファジングバランサ４６０は、ファジング演算４５０の動作を評価し、コンピュータ可読プログラムコード１４０の検査の目標と調和してファジング演算４５０をどのように平衡させるかを決定するよう構成されてよい。例えば、ファジングバランサ４６０は、２つ以上のファジング演算４５０の動作を比較して、該２つ以上のファジング演算４５０のうちのどれが、コンピュータ可読プログラムコード１４０の検査の目標に関してより効率的に実行しているか、ファジング演算４５０のどれがコンピュータ可読プログラムコード１４０に最適か、及び／又はファジング演算４５０の現在状態、を決定するよう構成されてよい。ファジングバランサ４６０は、例えば、コンピュータ可読プログラムコード１４０のブランチの全部を実行するという目標に関して、より効率的に動作している１つ以上のファジング演算４５０に、より多くのコンピューティングリソースを割り当てるよう構成されてよい。システム４００は、ファジングバランサ４６０の割り当てに従い、自動コンピュータプログラム検査動作を実行し続けてよい。２つ以上のファジング演算４５０の間で割り当て可能なコンピューティングリソースは、多数のコンピューティングシステム又はプロセッサ、又は動作を実行するための時間の期間若しくは割合を含んでよい。
【００６８】
幾つかの実施形態では、ファジングバランサ４６０は、ファジング演算部４５０により実行されているファジング演算に関連する１つ以上の基準を用いることにより、ファジング演算４５０のうちのどれが、検査の目標に関してより効率的に実行しているか、ファジング演算４５０のうちのどれが、コンピュータ可読プログラムコード１４０に最適か、及び／又はファジング演算４５０の現在状態、を決定するよう構成されてよい。
【００６９】
例えば、図２Ａ及び２Ｂに関して上述したものと同様に、第１ファジング演算４５０Ａがファジング演算を実行している場合には、第１ファジング演算４５０Ａにより多くのコンピューティングリソースを割り当てるか否かを決定するための基準は、第１入力セット１０２Ａ及び／又は第２入力セット１０２Ｂの中の値に基づいてよい。幾つかの実施形態では、ファジングバランサ４６０は、１つ以上の入力セット１０２を分析して、長さ閾及び／又は共通性閾を満たす入力の数を決定するよう構成されてよい。
【００７０】
幾つかの実施形態では、長さ閾は、長さ、又は入力の中の値若しくは文字の数、に基づく条件を含んでよい。長さ閾は、値若しくは文字の数、例えば４、８又は１６個、であってよい。追加又は代替として、長さ閾は、入力セットの中の他の入力に関連してよい。例えば、長さ閾は、１つ以上の入力セット１０２の中の入力の平均長に基づいてよい。追加又は代替として、長さ閾は、１つ以上の入力セット１０２の中の全部の入力の長さの標準偏差に基づいてよい。例えば、長さ閾は、平均長より標準偏差だけ長い長さを有する任意の入力により満たされてよい。
【００７１】
幾つかの実施形態では、共通性閾は、入力セット１０２の２つ以上の入力により共有され得る文字若しくは値の数に基づく条件であってよい。共通性閾は、２つ以上の入力の中で同じ文字の数、例えば４、８又は１６個、であってよい。追加又は代替として、共通性閾は、入力セットの中の１つ以上の入力の長さに関連してよい。例えば、共通性閾は、２個の入力が、該入力の一方の全長の半分の又は入力セット１０２の中の平均入力の３分の１の長さの、共通の値を有するとき、満たされてよい。
【００７２】
幾つかの実施形態では、ファジングバランサ４６０は、１つ以上の入力セット１０２の中の、長さ閾及び／又は共通性閾を満たす入力の数を分析して、長さ閾及び／又は共通性閾を満たす入力の数が待ち行列閾を満たすか否かを決定するよう構成されてよい。幾つかの実施形態では、待ち行列閾は、長さ閾及び共通性閾の両方を満たす入力の数に基づく条件を含んでよい。他の実施形態では、待ち行列閾は、長さ閾を満たし且つ共通性閾を満たさない入力の数に基づく条件を含んでよい。待ち行列閾は、入力の数、例えば１６、３２又は６４個、であってよい。追加又は代替として、待ち行列閾は、入力セット１０２のうちの１つ以上の中の入力の数に関連してよい。例えば、待ち行列閾は、入力セットの中の入力の半分又は３分の２が長さ閾を満たすとき、満たされてよい。
【００７３】
図２Ａ及び２Ｂに関して上述したファジング演算は、複数の入力に共通の値シーケンスに基づき、入力セット１０２の入力を識別し及び／又は変更し得るので、ファジングバランサ４６０は、入力セット１０２を分析して、ファジング演算部４５０のうちの１つ以上に追加リソースを割り当てるべきか否かを決定するよう構成されてよい。例えば、ファジングバランサ４６０は、入力セット１０２を分析して、入力セット１０２の入力のうちの１つ以上の長さを決定し、それらを長さ閾と比較するよう構成されてよい。追加又は代替として、ファジングバランサ４６０は、入力セット１０２の入力のうちの２つ以上に共通する値若しくは文字の数を分析して、入力セット１０２のどれだけ多くの入力が共通性閾を満たすかを決定するよう構成されてよい。追加又は代替として、ファジングバランサ４６０は、入力セットのどれだけ多くの入力が長さ閾及び共通性閾を満たすかを決定するよう構成されてよい。追加又は代替として、ファジングバランサ４６０は、入力セットのどれだけ多くの入力が長さ閾を満たし且つ共通性閾を満たさないかを決定するよう構成されてよい。代替として、ファジングバランサ４６０は、入力セット１０２の、長さ閾及び共通性閾を満たす入力の数を待ち行列閾と比較して、１つ以上のファジング演算部４５０に更なるリソースを割り当てるか否かを決定するよう構成されてよい。さらに、ファジングバランサ４６０は、入力セット１０２の、長さ閾を満たし且つ共通性閾を満たさない入力の数を待ち行列閾と比較して、１つ以上のファジング演算部４５０に更なるリソースを割り当てるか否かを決定するよう構成されてよい。
【００７４】
幾つかの実施形態では、第１ファジング演算部４５０Ａは、図３に関して上述したものと同様のファジング演算を実施しており、更なるコンピューティングリソースを第１ファジング演算部４５０Ａに割り当てるか否かを決定するための基準は、制御フローグラフの中の非トラバースブランチに基づいてよい。幾つかの実施形態では、ファジング演算部４５０及び／又はファジングバランサ４６０のうちの１つ以上は、コンピュータ可読プログラムコード１４０の制御フローグラフを取得してよい。コンピュータ可読プログラムコード１４０の実行中にカバーされるブランチのトレース又はリストは、格納され、制御フローグラフと比較されてよい。比較は、非トラバースブランチを決定するために使用されてよい。上述及び他の実施形態では、非トラバースブランチは、ファジングバランサ４６０により２つ以上のファジング演算部４５０の間でリソースをどのように割り当てるかを決定するための基礎であってよい。追加又は代替として、ファジングバランサ４６０によりリソースをどのように割り当てるかを決定する基準は、コンピュータ可読プログラムコード１４０の実行に関連する別の条件を満たす非トラバースブランチに基づいてよい。例えば、基準は、ループを含む又は制御フローグラフ内のブランチの反復する実行を生じさせる非トラバーストレースの数に基づいてよい。
【００７５】
幾つかの実施形態では、非トラバースブランチの数は、特定ファジング演算部４５０に追加リソースを割り当てるか否かを決定するために、トレース閾と比較されてよい。トレース閾は、非トラバースブランチ及び／又はループを含む非トラバースブランチの数を含んでよい。トレース閾は、例えば１０２４、２０４８、又は４０９６のようなブランチの数であってよい。追加又は代替として、トレース閾は、制御フローグラフの中のブランチ及び／又はループの合計数に関連し得る。例えば、トレース条件は、ブランチの４分の３が非トラバースである場合に、満たされてよい。
【００７６】
図３に関して上述したファジング演算は、ブランチの実行された回数に基づき、入力セット１０２の入力を識別し得るので、ファジングバランサ４６０は、非トラバースブランチを分析して、ファジング演算部４５０のうちの１つ以上に追加リソースを割り当てるべきか否かを決定するよう構成されてよい。例えば、ファジングバランサ４６０は、非トラバースブランチ及び／又は非トラバースループを分析し、それらをトレース閾と比較して、１つ以上のファジング演算部４５０に更なるリソースを割り当てるか否かを決定するよう構成されてよい。
【００７７】
別個に記載したが、図２Ａ及び２Ｂに関して記載したファジング演算は、図３に関して記載したファジング演算と共に実施されてよい。追加又は代替として、別個に記載したが、ファジングバランサ４６０は、長さ閾、共通性閾、待ち行列閾、及び／又はトレース閾のうちのいずれか又は全部に基づき、ファジング演算の平衡化を決定してよい。
【００７８】
システム４００の動作の一例では、ファジング演算部４５０の各々は、異なるファジング演算を用いてコンピュータ可読プログラムコード１４０を実行してよい。ファジング演算部４５０が進行するにつれ、それらは、それら個々の入力セット１０２に含めるべき入力を識別し及び／又は変更してよい。したがって、幾つかの実行の後に、第１入力セット１０２Ａは第２入力セット１０２Ｂと異なってよい。さらに、トレースが記録され、ファジング演算の各々の非トラバースブランチが更新されてよい。ファジングバランサ４６０は、入力セット１０２及び／又は非トラバースブランチの各々を分析して、ファジング演算をどのように平衡化するかを決定してよい。
【００７９】
例えば、第１ファジング演算部４５０Ａは、共通値シーケンスに基づき、入力を変更するファジング演算を実施してよい。ファジングバランサ４６０は、第１入力セット１０２Ａの中の全部の入力の２分の１が、４個の値より長く、第１入力セット１０２の中の少なくとも１つの他の入力と共通の、値シーケンスを含むことを決定してよい。この決定に基づき、ファジングバランサ４６０は、追加コンピューティングリソースを第１ファジング演算部４５０Ａに割り当ててよい。別の例として、ファジングバランサ４６０は、１０個の値より長い１００個の入力のうち、０個が共通値シーケンスを共有することを決定してよい。この決定に基づき、ファジングバランサ４６０は、第１ファジング演算部４５０Ａに割り当てられたコンピューティングリソースのうちの幾つかの割り当てを解除し、それらを別のファジング演算部４５０に割り当ててよい。
【００８０】
別の例として、第２ファジング演算部４５０Ｂは、コンピュータ可読プログラムコード１４０のブランチに該ブランチが前に実行されたより多くの回数実行させる入力に基づき、第２入力セット１０２Ｂの入力を識別するファジング演算を実施してよい。このような実施形態では、ファジングバランサ４６０は、制御フローグラフが１０００個のループを含むこと、及びそれらの４分の１がトラバースされたことを決定してよい。これらの決定に基づき、ファジングバランサ４６０は、追加コンピューティングリソースを第２ファジング演算部４５０Ｂに割り当ててよい。別の例として、ファジングバランサ４６０は、制御フローグラフが１０００個のループを含むこと、及びそれらの４分の３がトラバースされたことを決定してよい。これらの決定に基づき、ファジングバランサ４６０は、第２ファジング演算部４５０Ｂに割り当てられたコンピューティングリソースのうちの幾つかの割り当てを解除し、それらを別のファジング演算部４５０に割り当ててよい。
【００８１】
本開示の範囲から逸脱することなくシステム４００に対し変更、追加又は省略が行われてよい。例えば、ファジング演算部４５０のうちの１つ以上は、入力セット１０２を共有してよい。さらに、動作の順序は、異なる実装に従い変化してよい。
【００８２】
図５は、本開示に記載の少なくとも一実施形態による、自動コンピュータプログラム検査動作のための入力を識別する例示的な処理５００のフローチャートである。幾つかの実施形態では、処理５００に関連する演算のうちの１つ以上は、図１のシステム１００、図２Ａのシステム２００、図３のシステム３００、又は図４のシステム４００により実行されてよい。処理５００は、任意の適切なシステム、機器、又は装置により実行されてよい。例えば、図７のコンピューティングシステム７００は、処理５００に関連する演算のうちの１又は複数を実行してよい。別個のブロックにより図示したが、所望の実装に依存して、処理５００のブロックのうちの１つ以上に関連するステップ及び工程は、更なるブロックに分割され、少ないブロックに結合され、又は除去されてよい。
【００８３】
ブロック５１０で、コンピュータ可読プログラムの第１入力は、コンピュータプログラムの実行により取得されてよい。第１入力は、上述のように、図１の入力セット１０２の入力又は図２Ａの第１入力２０６Ａと同じ又は同様であってよい。コンピュータ可読プログラムは、上述の図１のコンピュータ可読プログラムコード１４０と同じ又は実質的に同様であってよい。コンピュータ可読プログラム実行部は、図１のコンピュータ可読プログラム実行部１２０と同じ又は実質的に同様であってよい。コンピュータ可読プログラム実行部は、第１入力を用いてコンピュータ可読プログラムを実行してよい。第１入力は、コンピュータ可読プログラムに、コンピュータ可読プログラムの実行中に第１パスを取らせてよい。幾つかの実施形態では、コンピュータ可読プログラムは、第１入力を用いて実行してよく、第１パスが観察され及び／又は記録されてよい。
【００８４】
ブロック５２０で、コンピュータ可読プログラムの第２入力が取得されてよい。第２入力は、上述のように、図１の入力セット１０２の入力又は図２Ａの第２入力２０６Ｂと同じ又は同様であってよい。第２入力は、コンピュータ可読プログラムの実行中にコンピュータ可読プログラムに第２パスを取らせるために、コンピュータ可読プログラムの実行中に使用されてよい。幾つかの実施形態では、コンピュータ可読プログラムは、第２入力を用いて実行されてよく、第２パスが観察され及び／又は記録されてよい。第２パスは、第１パスと異なってよい。幾つかの実施形態では、第２パスが第１パスと異なるか否かを決定するために、第１パスは第２パスと比較されてよい。
【００８５】
ブロック５３０で、第１入力及び第２入力の両方に共通の値シーケンスが識別されてよい。値シーケンスは、図２Ａ及び２Ｂに関して上述した値シーケンス２０８と同じ又は同様であってよい。幾つかの実施形態では、値シーケンスは、値シーケンスが長さ閾を満たす場合にのみ識別されてよい。
【００８６】
ブロック５４０で、第１入力及び第２入力の両方に共通の値シーケンスに基づき、第３入力が生成されてよい。第３入力は、上述のように、図１の入力セット１０２の入力又は図２Ａの第５入力２０６Ｅと同じ又は同様であってよい。第３入力は、第１及び第２入力の両方に共通の値シーケンスと、新しい値と、を含んでよい。上述及び他の実施形態では、第３入力は、コンピュータ可読プログラムの実行中に使用されるよう構成されてよく、他の入力セットに追加されてよい。新しい値は、ランダム値、第１及び／又は第２入力の一方又は両方に基づき変更された値、等であってよい。
【００８７】
幾つかの実施形態では、処理５００は複数回繰り返されてよく、コンピュータ可読プログラムに前に取られなかったパスを取らせる各入力は格納されてよい。さらに、コンピュータ可読プログラムに前に取られなかったパスを取らせる入力と任意の前に格納された入力との間の共通値シーケンスが存在するか否かを決定するために、コンピュータ可読プログラムに前に取られなかったパスを取らせる各入力は、格納された入力と比較されてよい。追加又は代替として、格納された入力のうちのいずれかが、格納された入力のうちの１つより多くの間に共通する値シーケンスを含むか否かを決定するために、格納された入力が分析されてよい。
【００８８】
本開示の範囲から逸脱することなく処理５００に対し変更、追加又は省略が行われてよい。さらに、動作の順序は、異なる実装に従い変化してよい。
【００８９】
図６は、本開示に記載の少なくとも一実施形態による、自動コンピュータプログラム検査動作のための入力を識別する別の例示的な処理６００のフローチャートである。幾つかの実施形態では、処理６００に関連する演算のうちの１つ以上は、図１のシステム１００、図２Ａのシステム２００、図３のシステム３００、又は図４のシステム４００により実行されてよい。処理６００は、任意の適切なシステム、機器、又は装置により実行されてよい。例えば、図７のコンピューティングシステム７００は、処理６００に関連する演算のうちの１又は複数を実行してよい。別個のブロックにより図示したが、所望の実装に依存して、処理６００のブロックのうちの１つ以上に関連するステップ及び工程は、更なるブロックに分割され、少ないブロックに結合され、又は除去されてよい。
【００９０】
ブロック６１０で、コンピュータ可読プログラムは、コンピュータ可読プログラムの実行により取得されてよい。コンピュータ可読プログラムはコード部分を含んでよい。コンピュータ可読プログラムは、上述の図１のコンピュータ可読プログラムコード１４０と同じ又は実質的に同様であってよい。コード部分は、上述のように図３のコード部分３４２のうちのコード部分と同じ又は同様であってよい。コンピュータ可読プログラム実行部は、上述の図１のコンピュータ可読プログラム実行部１２０と同じ又は実質的に同様であってよい。
【００９１】
ブロック６２０で、コンピュータ可読プログラムは、第１入力を用いてコンピュータプログラム実行部により実行されてよい。第１入力は、上述のように図１の入力セット１０２の入力と同じ又は同様であってよい。
【００９２】
ブロック６３０で、第１入力を用いるコンピュータ可読プログラムの実行中のコード部分の実行数が追跡され及び／又は格納されてよい。
【００９３】
ブロック６４０で、コード部分の実行数は、コンピュータ可読プログラムを実行するとき、コード部分の前の最高実行回数と比較されてよい。例えば、コンピュータ可読プログラムは、複数の異なる入力を用いて複数回実行されていてよい。コンピュータ可読プログラムが実行された複数回の各々について、コード部分の実行回数が、追跡され及び／又は図３の最大実行数３２２のようなテーブルに格納されてよい。
【００９４】
ブロック６５０で、実行回数が前の最高実行回数より大きいことに応答して、実行回数は、前の最高実行回数として格納されてよい。実行回数の前の最高実行回数としての格納が行われてよい。その結果、処理６００は、繰り返し実行し、最高実行回数は、実行が前の最高実行回数を超えるときはいつでも更新されてよい。
【００９５】
ブロック６６０で、実行回数が前の最高実行回数より大きいことに応答して、第１入力が、変更動作の対象である第１入力プールに追加されてよい。
【００９６】
幾つかの実施形態では、処理６００は、複数回繰り返されてよく、前の最高実行回数より多くの回数だけコード部分を実行する各入力は、入力プールに追加されてよく、前の最高実行回数は更新されてよい。
【００９７】
幾つかの実施形態では、処理６００は、コンピュータ可読プログラム内部の複数のコード部分に適用されてよい。例えば、第１入力を用いる実行は、複数のコード部分に関して追跡されてよい。また、複数のコード部分の各々について、前の最高実行回数が存在してよい。例えば、図３の最大実行数３２２は、複数のコード部分の各々について、前の最高実行回数を有する表を含んでよい。第１入力を用いる実行が前の最高実行回数のうちのいずれよりも大きい場合、第１入力は入力プールに追加されてよく、前の最高実行回数が更新されてよい。
【００９８】
幾つかの実施形態では、第１入力プールの入力は、入力セットに追加されるべき新しい入力を生成するよう変更されてよい。例えば、第１入力は、第１入力の中の１つ以上のビットのランダムなフリッピング、第１入力の中の１つ以上の値の繰り返し、第１入力から１つ以上の値の除去、第１入力への別の入力からの１つ以上の値の追加、により変更されてよい。
【００９９】
幾つかの実施形態では、第１入力の１つ以上の変更されたバージョンは、処理６００の中で第１入力として使用されてよい。
【０１００】
本開示の範囲から逸脱することなく処理６００に対し変更、追加又は省略が行われてよい。さらに、動作の順序は、異なる実装に従い変化してよい。
【０１０１】
当業者は、システム１００、システム２００、システム３００、システム４００、処理５００、処理６００、及び本願明細書に開示した他の処理及び方法において、その処理及び方法で実行される機能が異なる順序で実施されてよいことを理解するだろう。さらに、概略のステップ及び動作は、単に例として提供され、幾つかのステップ及び動作は、開示の実施形態の本質から逸脱することなく、任意であり、より少ないステップ及び動作に結合され、又は追加ステップ及び動作に拡張されてよい。
【０１０２】
本願明細書に記載した実施形態は、以下に更に詳細に議論するように、種々のコンピュータハードウェア又はソフトウェアモジュールを備えた特定用途又は汎用コンピュータの使用を含み得る。
【０１０３】
図７は、本開示の特定の少なくとも一実施形態にしたがってよい例示的なコンピューティングシステム７００のブロック図である。図７に示すように、コンピューティングシステム７００は、プロセッサ７０２と、メモリ７０４と、データ記憶装置７０６と、通信ユニット７０８と、を有してよい。
【０１０４】
図１〜４のシステム１００、２００、３００、及び／又は４００の１つ以上のコンポーネントは、図７のコンピューティングシステム７００のようなコンピューティングシステム上に実装されてよい。例えば、コンピュータ可読プログラムコード１４０は、メモリ７０４及び／又はデータ記憶装置７０６に格納されてよい。プロセッサ７０２は、コンピュータ可読プログラム実行部１２０及び／又は変更部１３０に関連する１つ以上の演算を実行してよい。プロセッサ７０２は、コンピュータ可読プログラムコード１４０を実行するためにメモリ７０４及び／又はデータ記憶装置７０６に格納された入力セット１０２の種々の入力を呼び出すことにより、コンピュータ可読プログラムコード１４０を実行してよい。そして、入力プール１１２及び最大実行数３２２は、メモリ７０４及び／又はデータ記憶装置７０６に格納されてよい。さらに、ファジング演算部４５０は、メモリ７０４及びデータ記憶装置７０６を用いてプロセッサ７０２により同様に実行されてよい。さらに、プロセッサ７０２は、どれだけ多くの処理サイクルが異なるファジング演算部４５０のために設けられるかを平衡化するために、ファジングバランサ４６０に関連する１つ以上の演算を実行してよい。
【０１０５】
概して、プロセッサ７０２は、任意の適切な特定用途向け又は汎用コンピュータ、コンピューティングエンティティ、又は種々のコンピュータハードウェア若しくはソフトウェアモジュールを有してよく、任意の適切なコンピュータ可読媒体に格納された命令を実行するよう構成され得る処理装置を用いて実施されてよい。例えば、プロセッサ７０２は、マイクロプロセッサ、マイクロコントローラ、デジタシグナルプロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（FPGA）又はプログラム命令を解釈し及び／若しくは実行し並びに／又はデータを処理するよう構成された任意の他のデジタル若しくはアナログ回路を有してよい。図７には単一のプロセッサを示したが、プロセッサ７０２は、本願明細書に記載の任意の数の演算を個々に又は共同で実行するよう構成される任意の数のネットワーク又は物理的位置に渡り分散される任意の数のプロセッサを有してよいことが理解される。幾つかの実施形態では、プロセッサ７０２は、プログラム命令を解釈し及び／又は実行し、及び／又はメモリ７０４、データ記憶装置７０６又はメモリ７０４及びデータ記憶装置７０６に格納されたデータを処理してよい。幾つかの実施形態では、プロセッサ７０２は、データ記憶７０６からプログラム命令をフェッチし、該プログラム命令をメモリ７０４にロードしてよい。プログラム命令がメモリ７０４にロードされた後、プロセッサ７０２は、それぞれ図１〜４のシステム１００、２００、３００及び／又は４００に関して記載した１つ以上の演算を実行するための命令のようなプログラム命令を実行してよい。例えば、命令は、自動コンピュータプログラム検査における入力の識別を促進してよい。
【０１０６】
メモリ７０４及びデータ記憶装置７０６は、コンピュータ実行可能命令又はデータ構造を運ぶ又は格納しているコンピュータ可読記憶媒体又は１つ以上のコンピュータ可読記憶媒体を含み得る。このようなコンピュータ可読媒体は、プロセッサ７０２のような汎用又は特定目的コンピュータによりアクセスできる任意の利用可能な媒体であり得る。例として且つ限定ではなく、このようなコンピュータ可読媒体は、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read−Only  Memory）、ＥＥＰＲＯＭ（Electrically  Erasable  Programmable  Read−Only  Memory）、ＣＤ−ＲＯＭ（Compact  Disc  Read−Only  Memory）又は他の光ディスク記憶装置、磁気ディスク記憶装置又は他の磁気記憶装置、フラッシュメモリ装置（例えば、固体メモリ素子）を含む非一時的コンピュータ可読記憶媒体、又はコンピュータにより実行可能な命令若しくはデータ構造の形式でプログラムコード手段を伝える若しくは格納するために用いられ汎用若しくは特定目的コンピュータによりアクセス可能な他の記憶媒体を有し得る。上述の組合せも、コンピュータ可読記憶媒体の範囲に包含され得る。コンピュータ実行可能命令は、例えば、プロセッサ７０２に特定の工程又は工程のグループを実行させるよう構成される命令及びデータを含み得る。上述及び他の実施形態では、本願明細書で説明されるような用語「非一時的」は、Federal  Circuit  decision  of  In  re  Nuijten,  ５００  F.３d  １３４６  (Fed.  Cir.  ７００７)における特許可能な対象の範囲から外れると考えられる種類の一時的媒体のみを除隊するものと考えられるべきである。上述の組合せも、コンピュータ可読媒体の範囲に包含され得る。
【０１０７】
通信ユニット７０８は、コンピュータ可読プログラム及び／又は入力を受信し、コンピュータ可読プログラム及び／又は入力をデータ記憶装置７０６に提供するよう構成されてよい。通信ユニット７０８は、レコード、データセット、及び／又は仮定に基づくデータセットを受信して、該レコード、データセット、及び／又は仮定に基づくデータセットをデータ記憶装置７０６に提供するよう構成されてよい。通信ユニット７０８は、コンピューティングシステム７００とネットワーク１４０との間の通信を可能にし又は助けるよう構成される任意の装置、システム、コンポーネント、又はコンポーネントの集合を有してよい。例えば、通信ユニット７０８は、限定ではなく、モデム、ネットワークカード（無線又は有線）、赤外線通信装置、光通信装置、（アンテナのような）無線通信装置、及び／又は（Ｂｌｕｅｔｏｏｔｈ（登録商標）装置、８０２．６装置（例えば、ＭＡＮ（Metropolitan  Area  Network））、ＷｉＦｉ装置、ＷｉＭａｘ装置、セルラ通信設備、等のような）チップセット、及び／又は同様のものを含み得る。通信ユニット７０８は、少数の例を挙げると、セルラネットワーク、ＷｉＦｉネットワーク、ＭＡＮ、光ネットワーク、等のようなもの、及び／又はリモート装置を含む本開示に記載される任意の他の装置と、データを交換させることができる。
【０１０８】
本開示の範囲から逸脱することなくコンピューティングシステム７００に対し変更、追加又は省略が行われてよい。例えば、データ記憶装置７０６は、複数の場所に置かれ、ネットワークを通じてプロセッサ７０２によりアクセスされてよい。
【０１０９】
本願明細書で用いられるように、用語「モジュール」又は「コンポーネント」は、モジュール若しくはコンポーネントの動作を実行するよう構成される特定ハードウェア実装、及び／又はコンピューティングシステムの汎用ハードウェア（例えばコンピュータ可読媒体、処理装置、等）に格納され及び／又はそれらにより実行され得るソフトウェアオブジェクト若しくはソフトウェアルーチンを表してよい。幾つかの実施形態では、本願明細書に記載されたのと異なるコンポーネント、モジュール、エンジン及びサービスは、（例えば、別個のスレッドとして）コンピューティングシステムで実行されるオブジェクト又は処理として実施されてよい。
【０１１０】
本願明細書に記載のシステム及び方法の幾つかは概して（汎用ハードウェアに格納される及び／又はそれにより実行される）ソフトウェアで実装されるように記載されたが、専用ハードウェアの実装又はソフトウェアと専用ハードウェアの組み合わせの実装も可能であり考えられる。この説明では、「コンピュータエンティティ」は、本願明細書で先に定められたようにコンピューティングシステム、又はコンピューティングシステムで実行されるモジュール若しくはモジュールの組合せであってよい。
【０１１１】
本開示で及び特に添付の特許請求の範囲（例えば、添付の特許請求の範囲の本体）で使用される用語は、概して、広義の（open）用語と考えられる（例えば、用語「含む（including）」は「含むが、限定されない」と解釈されるべきであり、用語「有する（having）」は「少なくとも有する」と解釈されるべきであり、用語「含む（includes）」は「含むが、限定されない」と解釈されるべきである）。
【０１１２】
さらに、特定数の導入された請求項の引用が意図される場合、このような意図は、請求項の中に明示的に示され、このような引用が存在しない場合はこのような意図が存在しない。例えば、理解の助けとして、以下の添付の特許請求の範囲は、請求項の引用を導入するために、「少なくとも１つの」及び「１又は複数の」をいう前置語句の使用を含み得る。しかしながら、このような語句の使用は、同じ請求項が前置語句「１又は複数」又は「少なくとも１つの」及び「ａ又はａｎ」のような不定冠詞を含むときでも、不定冠詞「ａ、ａｎ」による請求項引用の導入がこのような導入された請求項引用を含む任意の特定の請求項をこのような引用を１つだけ含む実施形態に限定することを示すと考えられてはならない（例えば、「ａ」及び／又は「ａｎ」は「少なくとも１つの」又は「１又は複数の」を意味すると解釈されるべきである）。同様のことは、請求項引用を導入するために使用される定冠詞の使用についても該当する。
【０１１３】
さらに、特定数の導入された請求項引用が明示的に引用される場合、当業者は、このような引用が少なくとも引用された番号を意味することと解釈されるべきであることを認識するだろう（例えば、「２つの引用」はそのままで、他の変更が無ければ、少なくとも２つの引用、又は２以上の引用を意味する）。さらに、「Ａ、Ｂ、Ｃ、等のうちの少なくとも１つ」又は「Ａ、Ｂ、Ｃ、等のうちの１又は複数」に類似する慣例が用いられる例では、通常、このような構成は、Ａのみ、Ｂのみ、Ｃのみ、Ａ及びＢを一緒に、Ａ及びＣを一緒に、Ｂ及びＣを一緒に、又はＡ、Ｂ、Ｃを一緒に、等を含むと意図される。
【０１１４】
さらに、２以上の代替用語を表す任意の離接語又は語句は、説明、請求項、又は図面の中であるかに係わらず、用語のうちの１つ、用語のうちのいずれか、又は両方の用語を含む可能性を包含すると理解されるべきである。例えば、語句「Ａ又はＢ」は、「Ａ」又は「Ｂ」又は「Ａ及びＢ」の可能性を含むと理解されるべきである。さらに、幾つかの場所における用語「及び／又は」の使用は、用語「又は」が用語のうちのいずれかのみを含むと理解されるべきであることを意味せず、反対に両方の用語の可能性を含む。
【０１１５】
さらに、用語「第１」、「第２」、「第３」等の使用は、本願明細書において必ずしも要素の特定の順序又は数を暗示するために使用されない。通常、用語「第１」、「第２」、「第３」等は、一般的識別子として、異なる要素の間を区別するために使用される。用語「第１」、「第２」、「第３」等が特定の順序を暗示することを示さない場合も、これらの用語が特定の順序を暗示すると解釈されるべきではない。さらに、用語「第１」、「第２」、「第３」等が要素の特定の数を暗示することを示さない場合も、これらの用語が要素の特定の数を暗示すると解釈されるべきではない。例えば、第１ウィジェットは第１側面を有するとして記載されてよく、第２ウィジェットは第２側面を有するとして記載されてよい。第２ウィジェットに関する用語「第２側面」の使用は、第２ウィジェットのこのような側面を、第１ウィジェットの「第１側面」から区別するためであってよく、第２ウィジェットが２つの側面を有することを暗示しない。
【０１１６】
本願明細書に記載された全ての例及び条件文は、教育上の目的で、読者が本発明の原理及び発明者により考案された概念を理解するのを助け、技術を促進させるためであり、これらの特に記載された例及び条件に限定されないものと考えられるべきである。本開示の実施形態が詳細に記載されたが、種々の変更、置換及び修正が本開示の精神及び範囲から逸脱することなく行われうることが理解されるべきである。
【０１１７】
以上の実施形態に加えて、更に以下の付記を開示する。
（付記１）  方法であって、
コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第１パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムの第１入力を取得するステップと、
前記コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第２パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムの第２入力を取得するステップと、
前記第１入力及び前記第２入力の両方に共通の値シーケンスを識別するステップと、
前記値シーケンスが前記第１入力及び前記第２入力の両方に共通であることに基づき、前記値シーケンス及び新しい値を含む第３入力を生成するステップであって、前記第３入力は前記コンピュータ可読プログラムの実行中に使用されるよう構成される、ステップと、
を含む方法。
（付記２）  前記コンピュータ可読プログラムの第１反復への第１入力セットに対して第１ファジング演算を実行するステップと、
前記コンピュータ可読プログラムの第２反復への第２入力セットに対して第２ファジング演算を実行するステップであって、前記第２ファジング演算は、前記第１ファジング演算が前記第１入力セットに包含するための入力を識別するのと異なる方法で、前記第２入力セットに包含するための入力を識別する、ステップと、
を更に含み、
前記第１ファジング演算は、
前記コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第１反復パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムの前記第１入力セットから第１反復入力を取得するステップと、
前記コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第２反復パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムの前記第２入力セットから第２反復入力を取得するステップと、
前記第１反復入力及び前記第２反復入力の両方に共通の第２値シーケンスを識別するステップと、
前記第２値シーケンスが前記第１反復入力及び前記第２反復入力の両方に共通であることに基づき、前記第２値シーケンス及び別の新しい値を含む第４入力を生成するステップであって、前記第４入力は、前記コンピュータ可読プログラムの実行中に使用されるよう構成される、ステップと、
を含む、付記１に記載の方法。
（付記３）  第１回数だけ前記第１ファジング演算を実行するステップと、
第２回数だけ前記第２ファジング演算を実行するステップと、
前記第１入力セット及び前記第２入力セットのうちの少なくとも１つを解析して、長さ閾より長い長さを有する、前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の入力数を決定するステップと、
前記決定した入力数が待ち行列閾を満たすことに基づき、前記第１回数と前記第２回数との間の比を調整するステップと、
を更に含む付記２に記載の方法。
（付記４）  前記長さ閾は、前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の前記入力の全部の平均長さと、前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の前記入力の全部の長さの標準偏差と、に基づく、付記３に記載の方法。
（付記５）  前記待ち行列閾は、前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の入力の合計数に基づく、付記３に記載の方法。
（付記６）  前記新しい値は、前の入力に基づき変更される、付記１に記載の方法。
（付記７）  前記コンピュータ可読プログラムを取得するステップであって、前記コンピュータ可読プログラムはコード部分を含む、ステップと、
第５入力を用いて前記コンピュータ可読プログラムを実行するステップと、
前記第５入力を用いて実行されたときに前記コンピュータ可読プログラムの前記実行中に前記コード部分の実行回数を追跡するステップと、
前記コード部分の前記実行回数を、前記コンピュータ可読プログラムを実行するときの前記コード部分の前の最高実行回数と比較するステップと、
前記実行回数が前記前の最高実行回数より大きいことに応答して、
前記実行回数を前記前の最高実行回数として格納するステップと、
前記第５入力を変更動作の行われる入力プールに追加するステップと、
を更に含む付記１に記載の方法。
（付記８）  前記コンピュータ可読プログラムの第１反復への第３入力セットに対して第１ファジング演算を実行するステップと、
前記コンピュータ可読プログラムの第２反復への第４入力セットに対して第２ファジング演算を実行するステップであって、前記第２ファジング演算は、前記第１ファジング演算が前記第３入力セットに包含するための入力を識別するのと異なる方法で、前記第４入力セットに包含するための入力を識別する、ステップと、
を更に含み、
前記第１ファジング演算は、
前記コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第１反復パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムの前記第１入力セットから第１反復入力を取得するステップと、
前記コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第２反復パスを取らせるために前記コンピュータ可読プログラムの実行中に使用される前記コンピュータ可読プログラムの前記第２入力セットから第２反復入力を取得するステップと、
前記第１反復入力及び前記第２反復入力の両方に共通の第２値シーケンスを識別するステップと、
前記第２値シーケンスが前記第１反復入力及び前記第２反復入力の両方に共通であることに基づき、
前記第２値シーケンス及び別の新しい値を含む第６入力を生成するステップと、
前記第６入力を前記第１入力セットに追加するステップと、
前記第１入力セットからの第３反復入力を用いて前記コンピュータ可読プログラムを実行するステップと、
前記第３反復入力を用いて、前記コンピュータ可読プログラムの前記実行中にコード部分の所与の実行回数を追跡するステップと、
前記所与の実行回数を、前記コンピュータ可読プログラムを実行するときの前記コード部分の前の最高実行回数と比較するステップと、
前記所与の実行回数が前記前の最高実行回数より大きいことに応答して、
前記所与の実行回数を前記前の最高実行回数として格納するステップと、
前記第３反復入力の変更されたバージョンを前記第１入力セットに追加するステップと、
を更に含む付記１に記載の方法。
（付記９）  第１回数だけ前記第１ファジング演算を実行するステップと、
第２回数だけ前記第２ファジング演算を実行するステップと、
前記第１入力セット及び前記第２入力セットのうちの少なくとも１つを解析して、長さ閾より長い長さを有する、前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の入力数を決定するステップと、
前記コンピュータ可読プログラムを表す制御フローグラフを取得するステップと、
前記第１ファジング演算及び前記第２ファジング演算の間に取られた前記制御フローグラフの中のパスを示すトレースを取得するステップと、
前記トレース及び前記制御フローグラフを解析して、前記コンピュータ可読プログラムの実行に関連する条件を満たし且つ前記トレースによりトラバースされない前記制御フローグラフのブランチ数を決定するステップと、
前記条件を満たし且つ前記トレースによりトラバースされない前記制御フローグラフの前記ブランチ数がトレース閾を満たすことに応答して、及び前記長さ閾より長い長さを有する前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の前記入力数が待ち行列閾を満たすことに基づき、前記第１回数と前記第２回数との間の比を調整するステップと、
を更に含む付記８に記載の方法。
（付記１０）  方法であって、
コード部分を含むコンピュータ可読プログラムを取得するステップと、
第１入力を用いて前記コンピュータ可読プログラムを実行するステップと、
前記第１入力を用いる前記コンピュータ可読プログラムの前記実行中に前記コード部分の実行回数を追跡するステップと、
前記コード部分の前記実行回数を、前記コンピュータ可読プログラムを実行するときの前記コード部分の前の最高実行回数と比較するステップと、
前記実行回数が前記前の最高実行回数より大きいことに応答して、
前記実行回数を前記前の最高実行回数として格納するステップと、
前記第１入力を変更動作の行われる第１入力プールに追加するステップと、
を含む方法。
（付記１１）  前記コンピュータ可読プログラムの第１反復への第１入力セットに対して第１ファジング演算を実行するステップであって、前記第１入力セットは前記第１入力プールの変更されたバージョンを含む、ステップと、
前記コンピュータ可読プログラムの第２反復への第２入力セットに対して第２ファジング演算を実行するステップであって、前記第２入力セットは前記第２入力プールの変更されたバージョンを含み、前記第２ファジング演算は、前記第１ファジング演算が前記第１入力プールの入力を識別するのと異なる方法で、前記第２入力プールの入力を識別する、ステップと、
を更に含み、
前記第１ファジング演算は、
前記第１入力セットからの第１反復入力を用いて前記コンピュータ可読プログラムを実行するステップと、
前記第１反復入力を用いる前記コンピュータ可読プログラムの前記実行中に、前記コード部分の所与の実行回数を追跡するステップと、
前記所与の回数を前記前の最高実行回数と比較するステップと、
前記所与の回数が前記前の最高実行回数より大きいことに応答して、
前記所与の数を前記前の最高実行回数として格納するステップと、
前記第１反復入力を前記第１入力プールに追加するステップと、
を含む、付記１０に記載の方法。
（付記１２）  前記方法は、
第１回数だけ、前記第１ファジング演算を実行するステップと、
第２回数だけ、前記第２ファジング演算を実行するステップと、
前記コンピュータ可読プログラムを表す制御フローグラフを取得するステップと、
前記第１ファジング演算及び前記第２ファジング演算の間に、前記コンピュータ可読プログラムにより取り込まれた前記制御フローグラフの中のパスを示すトレースを取得するステップと、
前記トレース及び前記制御フローグラフを解析して、前記コンピュータ可読プログラムの実行回数に関する条件を満たし且つ前記トレースによりトラバースされない前記制御フローグラフのブランチの数を決定するステップと、
前記条件を満たし且つ前記トレースによりトラバースされない前記制御フローグラフの前記ブランチの数がトレース閾を満たすことに応答して、前記第１回数と前記第２回数との間の比を調整するステップと、
を更に有する付記１１に記載の方法。
（付記１３）  前記条件は、前記ブランチの実行中に１度より多く実行される第２コード部分に対応する前記制御フローグラフのブランチにより満たされる、付記１２に記載の方法。
（付記１４）  前記変更動作は、
前記第１入力を変更して、前記第１入力の変更されたバージョンを生成するステップと、
前記第１入力の前記変更されたバージョンを前記第１入力セットに追加するステップと、
を含む、付記１１に記載の方法。
（付記１５）  前記第１入力を変更する前記ステップは、
前記第１入力の中の１つ以上のビットをランダムにフリッピングするステップと、
前記第１入力の中の１つ以上の値をランダムに繰り返すステップと、
前記第１入力から１つ以上の値をランダムに除去するステップと、
前記第１入力に別の入力からの値をランダムに追加するステップと、
のうちの少なくとも１つを含む、付記１４に記載の方法。
（付記１６）  前記コンピュータ可読プログラムは複数のコード部分を含み、前記方法は、前記複数のコード部分のうちの所与のコード部分の各々について、
前記第１入力を用いる前記コンピュータ可読プログラムの前記実行中に、前記所与のコ―ド部分の所与の実行回数を追跡するステップと、
前記所与のコード部分の前記所与の実行回数を、前記コンピュータ可読プログラムを実行するときの前記所与のコード部分の所与の前の最高実行回数と比較するステップと、
前記所与の回数が前記所与の前の最高実行回数より大きいことに応答して、
前記所与の回数を前記所与のコード部分の前記所与の前の最高実行回数として格納するステップと、
前記第１入力を前記第１入力プールに追加するステップと、
を更に含む付記１０に記載の方法。
（付記１７）  前記コード部分の前記前の最高実行回数を表す８ビット数値を格納するステップ、を更に含む付記１０に記載の方法。
（付記１８）  コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第１パスを取らせるために前記コンピュータ可読プログラムの実行中に使用されるコンピュータ可読プログラムの第２入力を取得するステップと、
コンピュータ可読プログラムの実行中に前記コンピュータ可読プログラムに第２パスを取らせるために前記コンピュータ可読プログラムの実行中に使用されるコンピュータ可読プログラムの第３入力を取得するステップと、
前記第２入力及び前記第３入力の両方に共通の値シーケンスを識別するステップと、
前記値シーケンスが前記第２入力及び前記第３入力の両方に共通であることに基づき、それぞれ前記第２入力及び前記第３入力の両方に共通の前記値シーケンスとそれぞれの新しい値とを含む複数の入力を含むよう前記第１入力セットを変更するステップと、
を更に含む付記１０に記載の方法。
（付記１９）  前記コンピュータ可読プログラムの第１反復への第１入力セットに対して第１ファジング演算を実行するステップであって、前記第１入力セットは前記第１入力プールの中の入力の変更されたバージョンを含む、ステップと、
前記コンピュータ可読プログラムの第２反復への第２入力セットに対して第２ファジング演算を実行するステップであって、前記第２入力セットは前記第２入力プールの中の入力の変更されたバージョンを含み、前記第２ファジング演算は、前記第１ファジング演算が前記第１入力プールの入力を識別するのと異なる方法で、前記第２入力プールの入力を識別する、ステップと、
を更に含み、
前記第２入力及び前記第３入力の両方に共通の前記値シーケンスをそれぞれ含む前記複数の入力は、前記第１ファジング演算を用いて生成され、前記第１ファジング演算は、
前記第１入力セットからの反復入力を用いて前記コンピュータ可読プログラムを実行するステップと、
前記反復入力を用いる前記コンピュータ可読プログラムの前記実行中に、前記コード部分の所与の実行回数を追跡するステップと、
前記所与の回数を前記前の最高実行回数と比較するステップと、
前記所与の回数が前記前の最高実行回数より大きいことに応答して、
前記所与の回数を前記前の最高実行回数として格納するステップと、
前記反復入力を前記第１入力プールに追加するステップと、
を更に含む、付記１８に記載の方法。
（付記２０）  第１回数だけ前記第１ファジング演算を実行するステップと、
第２回数だけ前記第２ファジング演算を実行するステップと、
前記コンピュータ可読プログラムを表す制御フローグラフを取得するステップと、
前記第１ファジング演算及び前記第２ファジング演算からトレースを取得するステップと、
前記トレース及び前記制御フローグラフを解析して、条件を満たし且つ前記トレースによりカバーされない前記制御フローグラフのブランチ数を決定するステップと、
前記第１入力セット及び前記第２入力セットのうちの少なくとも１つを解析して、長さ閾より長い長さを有する、前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の入力数を決定するステップと、
前記条件を満たし且つ前記トレースによりカバーされない前記制御フローグラフの前記ブランチ数がトレース閾を満たすことに応答して、及び前記長さ閾より長い長さを有する前記第１入力セット及び前記第２入力セットのうちの前記少なくとも１つの中の前記入力数が待ち行列閾を満たすことに基づき、前記第１回数と前記第２回数との間の比を調整するステップと、
を更に含む付記１９に記載の方法。
【符号の説明】
【０１１８】
１００  システム
１０２  入力セット
１１２  入力プール
１２０  コンピュータ可読プログラム実行部
１３０  変更部
１４０  コンピュータ可読プログラムコード
【図１】
2020119513.tif 000004
【図２Ａ】
2020119513.tif 000005
【図２Ｂ】
2020119513.tif 000006
【図３】
2020119513.tif 000007
【図４】
2020119513.tif 000008
【図５】
2020119513.tif 000009
【図６】
2020119513.tif 000010
【図７】
2020119513.tif 000011