(57)【要約】【課題】  自動候補修正パッチ生成の方法を提供する。【解決手段】  自動候補修正パッチ生成の方法は、プロジェクトコードに基づき修正表現を合成するステップを含み得る。簡潔修正表現は、コードデータベースから検索されてよい。修正表現セットは、合成された修正表現及び検索された修正表現に基づき生成されてよい。修正表現セットは、合成された修正表現及び検索された修正表現から更に合成された更なる修正表現を含んでよい。候補パッチは、修正スキーマ及び修正表現セットに基づき生成されてよい。【選択図】  図３
2020126603.tif 000002
【特許請求の範囲】
【請求項１】
自動候補修正パッチ生成の方法であって、前記方法は、
プロジェクトコードに基づき修正表現を合成するステップと、
コードデータベースから簡潔修正表現を検索するステップと、
前記合成した修正表現と前記検索した修正表現とに基づき、修正表現セットを生成するステップであって、前記合成した修正表現と前記検索した修正表現とに基づき更なる修正表現を更に合成するステップを含む、ステップと、
修正スキーマ及び前記修正表現セットに基づき、候補パッチを生成するステップと、
を含む方法。
【請求項２】
前記候補パッチをランク付けするステップ、を更に含む請求項１に記載の方法。
【請求項３】
前記候補パッチをランク付けする前記ステップは、
前記候補パッチの前記修正表現が前記プロジェクトコードの中で一緒に生じる頻度、
前記候補パッチの前記修正表現が前記プロジェクトコードの中のバグのあるメソッド内で一緒に生じる頻度、
前記候補パッチの述語構造が前記コードデータベース内で生じる頻度、
前記候補パッチの対イディオムが前記コードデータベース内で生じる頻度、
に基づく、請求項２に記載の方法。
【請求項４】
前記候補パッチの前記修正表現が前記プロジェクトコードの中で一緒に生じる前記頻度は、第１スコアに関連付けられ、
前記候補パッチの前記修正表現が前記プロジェクトコードの中のバグのあるメソッド内で一緒に生じる前記頻度は、第２スコアに関連付けられ、
前記候補パッチの述語構造が前記コードデータベース内で生じる前記頻度は、第３スコアに関連付けられ、
前記候補パッチの対イディオムが前記コードデータベース内で生じる前記頻度は、第４スコアに関連付けられ、
前記候補パッチをランク付けする前記ステップは、第１重み値によりスケーリングされた前記第１スコア、第２重み値によりスケーリングされた前記第２スコア、第３重み値によりスケーリングされた前記第３スコア、及び第４重み値によりスケーリングされた前記第４スコアの和に基づく、請求項３に記載の方法。
【請求項５】
前記候補パッチをランク付けする前記ステップは、前記候補パッチの前記修正表現が前記プロジェクトコード内で一緒に生じる頻度に基づく、請求項２に記載の方法。
【請求項６】
前記候補パッチをランク付けする前記ステップは、前記候補パッチの前記修正表現が前記プロジェクトコード内のバグのあるメソッド内で一緒に生じる頻度に基づく、請求項２に記載の方法。
【請求項７】
前記候補パッチをランク付けする前記ステップは、前記候補パッチの述語構造が前記コードデータベース内で生じる頻度に基づく、請求項２に記載の方法。
【請求項８】
前記候補パッチをランク付けする前記ステップは、前記候補パッチの対イディオムが前記コードデータベース内で生じる頻度に基づく、請求項２に記載の方法。
【請求項９】
前記候補パッチの前記ランク付けの順序で、前記候補パッチを検査するステップ、を更に含む請求項２に記載の方法。
【請求項１０】
前記コードデータベースから前記簡潔修正表現を検索する前記ステップは、前記候補パッチが生成されたコード部分に類似するコード部分と、前記候補パッチが生成された前記コード部分に類似しないコード部分と、の両方から修正表現を検索するステップを含む、請求項１に記載の方法。
【請求項１１】
命令を格納するよう構成された非一時的コンピュータ可読記憶媒体であって、前記命令は、実行されることに応答して、システムに自動候補修正パッチ生成の動作を実行させ、前記動作は、
プロジェクトコードに基づき修正表現を合成するステップと、
コードデータベースから簡潔修正表現を検索するステップと、
前記合成した修正表現と前記検索した修正表現とに基づき、修正表現セットを生成するステップであって、前記合成した修正表現と前記検索した修正表現とに基づき更なる修正表現を更に合成するステップを含む、ステップと、
修正スキーマ及び前記修正表現セットに基づき、候補パッチを生成するステップと、
を含む、コンピュータ可読記憶媒体。
【請求項１２】
前記動作は、前記候補パッチをランク付けするステップを更に含む、請求項１１に記載のコンピュータ可読記憶媒体。
【請求項１３】
前記候補パッチをランク付けする前記ステップは、
前記候補パッチの前記修正表現が前記プロジェクトコードの中で一緒に生じる頻度、
前記候補パッチの前記修正表現が前記プロジェクトコードの中のバグのあるメソッド内で一緒に生じる頻度、
前記候補パッチの述語構造が前記コードデータベース内で生じる頻度、
前記候補パッチの対イディオムが前記コードデータベース内で生じる頻度、
に基づく、請求項１２に記載のコンピュータ可読記憶媒体。
【請求項１４】
前記候補パッチの前記修正表現が前記プロジェクトコードの中で一緒に生じる前記頻度は、第１スコアに関連付けられ、
前記候補パッチの前記修正表現が前記プロジェクトコードの中のバグのあるメソッド内で一緒に生じる前記頻度は、第２スコアに関連付けられ、
前記候補パッチの述語構造が前記コードデータベース内で生じる前記頻度は、第３スコアに関連付けられ、
前記候補パッチの対イディオムが前記コードデータベース内で生じる前記頻度は、第４スコアに関連付けられ、
前記候補パッチをランク付けする前記ステップは、第１重み値によりスケーリングされた前記第１スコア、第２重み値によりスケーリングされた前記第２スコア、第３重み値によりスケーリングされた前記第３スコア、及び第４重み値によりスケーリングされた前記第４スコアの和に基づく、請求項１３に記載のコンピュータ可読記憶媒体。
【請求項１５】
前記候補パッチをランク付けする前記ステップは、前記候補パッチの前記修正表現が前記プロジェクトコード内で一緒に生じる頻度に基づく、請求項１２に記載のコンピュータ可読記憶媒体。
【請求項１６】
前記候補パッチをランク付けする前記ステップは、前記候補パッチの前記修正表現が前記プロジェクトコード内のバグのあるメソッド内で一緒に生じる頻度に基づく、請求項１２に記載のコンピュータ可読記憶媒体。
【請求項１７】
前記候補パッチをランク付けする前記ステップは、前記候補パッチの述語構造が前記コードデータベース内で生じる頻度に基づく、請求項１２に記載のコンピュータ可読記憶媒体。
【請求項１８】
前記候補パッチをランク付けする前記ステップは、前記候補パッチの対イディオムが前記コードデータベース内で生じる頻度に基づく、請求項１２に記載のコンピュータ可読記憶媒体。
【請求項１９】
前記動作は、前記候補パッチの前記ランク付けの順序で、前記候補パッチを検査するステップ、を更に含む請求項１２に記載のコンピュータ可読記憶媒体。
【請求項２０】
前記コードデータベースから前記簡潔修正表現を検索する前記ステップは、前記候補パッチが生成されたコード部分に類似するコード部分と、前記候補パッチが生成された前記コード部分に類似しないコード部分と、の両方から修正表現を検索するステップを含む、請求項１１に記載のコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示で議論される実施形態は、自動候補修正パッチ生成に関する。
【背景技術】
【０００２】
ソフトウェアプログラムは、意図したように動作できない欠陥又は障害（通常、「バグ」と呼ばれる）をそれらの中に含むことがある。多くの場合、ソフトウェアプログラムの中の欠陥を識別し及び修正しようとして、自動修正システムが使用される。
【０００３】
本願明細書で請求される主題は、上述のような欠点を解決する実施形態や上述のような環境でのみ機能する実施形態に限定されない。むしろ、この背景技術は、単に、本願明細書に記載される複数の実施形態が実施される技術分野の一例を説明するために提供される。
【発明の概要】
【０００４】
一実施形態の一態様によると、自動候補修正パッチ生成の方法は、プロジェクトコードに基づき修正表現を合成するステップを含み得る。簡潔修正表現は、コードデータベースから検索されて（mined）よい。修正表現セットは、合成された修正表現及び検索された修正表現に基づき生成されてよい。修正表現セットは、合成された修正表現及び検索された修正表現から更に合成された更なる修正表現を含んでよい。候補パッチは、修正スキーマ及び修正表現セットに基づき生成されてよい。
【０００５】
実施形態の目的及び利点が理解され、少なくとも特に特許請求の範囲で指摘された要素、特徴及び組合せを用いて達成されるだろう。
【０００６】
上述の全体的説明及び以下の詳細な説明の両方は、例示及び説明のためであり、特許請求の範囲を限定しないことが理解される。
【図面の簡単な説明】
【０００７】
例示的な実施形態は、添付の図面を用いて、更なる特異性及び詳細事項と共に記載され説明される。
【０００８】
【図１】ソフトウェアプログラムの修正に関連する例示的な環境を表す図である。
【０００９】
【図２】ソフトウェアプログラムを修正するために構成され得る例示的なコンピューティングシステムを示す。
【００１０】
【図３】候補ソフトウェア修正パッチを生成し、ランク付けし、及び検査する例示的な方法のフローチャートである。
【発明を実施するための形態】
【００１１】
本開示に記載の幾つかの実施形態は、ソフトウェアプログラムを修正するためのソフトウェアパッチを生成する方法及びシステムに関する。ソフトウェアプログラムは、ソフトウェアプログラムを意図しない方法で動作させ得る欠陥又は障害（通常、「バグ」として参照される）を含むことがある。さらに、ソフトウェアプログラムを修正するために、欠陥を検出し及びソフトウェアパッチを生成するよう、自動修正システム及び技術が使用されることがある。しかしながら、自動修正システム及び技術は、ソフトウェアプログラムの欠陥を修正するためにパッチを生成するとき、粗悪なジョブを行うことがある。
【００１２】
例えば、幾つかの自動修正システムは、制約ソルバーに基づくアプローチを利用することがあり、テストケースから制約を生成し及び制約を解決することにより、パッチを合成することがある。このようなアプローチは、メソッド起動のような潜在的に複雑なプログラム構造を扱う際に限定的であることがある。幾つかの他の自動修正システムは、生成及び評価に基づくアプローチを利用することがあり、候補パッチを合成するために単純な変数及びオブジェクトを利用することがある。候補パッチは、ヒューリスティック又は機械学習技術に基づき繰り返し評価され得る。このようなアプローチは、修正空間の激増をなくすために、限られた修正表現に制約されることがある。更に他の自動修正システムは、バグを修正するために、プロジェクトのライブラリから類似するコードを利用してよい。欠陥を修正し得るコードがプロジェクトライブラリ内に存在しない場合、パッチは生成されなくてよい。
【００１３】
ソフトウェア修正及びデバッグ（ここでは一般に「ソフトウェア修正」と呼ばれる）は、ソフトウェア開発に有意なコストを追加する。幾つかの測定によると、ソフトウェア修正は、ソフトウェア開発者からプログラミング時間の約５０％を要求し得る。ソフトウェア欠陥及びそれらの修正は、コンピュータ技術の構成概念であり得る。例えば、ソフトウェア及びソフトウェア欠陥は、コンピュータ技術分野の外部に存在するものではない。
【００１４】
幾つかの実施形態では、修正ツールは、ソフトウェア開発環境のためのスタンドアロンツールとして及び／又はプラグインツールとして展開されてよい。代替又は追加で、修正ツールは、ソフトウェア開発者を支援するためのサービスとして展開されてよい。例えば、修正ツールは、インターネットに基づくサービスの一部であってよい。修正ツールは、ソフトウェア開発、診断、パッチ、及びアップグレードサービスを支援してよい。
【００１５】
本開示の実施形態は、合成プログラムアーチファクト及び検索されたプログラムアーチファクトを結合して、自動修正ツールの範囲を向上し得る。さらに、実施形態は、関連範囲内の修正空間の完全性を促進する方法で、合成に基づく特徴及び検索に基づく特徴に相乗効果を与え得ると同時に、合成に基づく特徴と検索に基づく特徴を結合する結果として、修正空間の爆発を直接的方法で抑える。例えば、実施形態は、検索に基づく特徴の包括的リストを利用して、正しい修正表現を推定し得る。
【００１６】
幾つかの実施形態は、限定ではなく、共起分析、コンテキスト分析、及びスキーマ駆動分析を利用してよい。本開示の実施形態は、既存の修正ツールが妥当と思われるパッチの識別に失敗し得るソフトウェア欠陥のために妥当と思われるパッチの識別を促進し得る。
【００１７】
本開示の実施形態を、添付の図面を参照して以下に説明する。
【００１８】
図１は、プロジェクトコード１１６に関連付けられたソフトウェアプログラムのようなソフトウェアプログラムを修正することに関連する例示的な自動ソフトウェア修正システム１００を表す図である。自動ソフトウェア修正システム１００は、欠陥について被検査コード１０４を分析するよう構成される修正モジュール１０６を含んでよい。修正モジュール１０６は、変更被検査コード１０８を出力するよう更に構成されてよい。変更被検査コード１０８は、修正モジュール１０６により実行された修正操作により被検査コード１０４に対して行われた１又は複数の変更を含んでよい。例えば、変更された被検査コード１０４は、ソフトウェアプログラムの欠陥を修正する妥当なパッチを含んでよい。
【００１９】
被検査コード１０４は、例えばソフトウェアプログラム、ソフトウェアプログラムのコード、ライブラリ、アプリケーション、スクリプト、又は処理装置による実行のための他のロジック若しくは命令のような、電子データを有してよい。幾つかの実施形態では、被検査コード１０４は、ソフトウェアプログラムの完全なインスタンスを有してよい。追加又は代替で、被検査コード１０４は、ソフトウェアプログラムの一部を有してよい。被検査コード１０４は、ソフトウェアプログラムのために使用され得る任意の適切な種類のコンピュータ言語で書かれてよい。被検査コード１０４は、１つ以上の欠陥を含んでよい。
【００２０】
修正モジュール１０６は、コンピューティング装置に、被検査コード１０４の１つ以上の変更を実行させて変更被検査コード１０８を生成させるよう構成されるコード及びルーチンを有してよい。追加又は代替で、修正モジュール１０６は、プロセッサ、（例えば、１つ以上の操作を実行する又はその実行を制御する）マイクロプロセッサ、FPGA（field-programmable  gate  array）又はASIC（application-specific  integrated  circuit）を含むハードウェアを用いて実装されてよい。幾つかの他の例では、修正モジュール１０６は、ハードウェア及びソフトウェアの組み合わせを用いて実装されてよい。本開示では、修正モジュール１０６により実行されるとして記載される操作は、修正モジュール１０６が対応するシステムに実行するよう指示し得る操作を有してよい。
【００２１】
修正モジュール１０６は、被検査コード１０４の中の１つ以上の欠陥を修正する（訂正するとしても参照される）ために使用され得る被検査コード１０４に対する一連の修正操作を実行するよう構成されてよい。幾つかの実施形態では、修正モジュール１０６は、１つ以上の修正スキーマ１１２及び１つ以上のテストスーツ１１１に基づき修正操作のうちの１つ以上を実行するよう構成されてよい。
【００２２】
スキーマ１１２は、本願明細書に記載のような修正表現を入力されるとき、被検査コード１０４の欠陥を修正する候補パッチを形成し得るコードテンプレートを含んでよい。本願明細書に記載のように、１つ以上のテストスーツの検査を満たす候補パッチは、変更された被検査コード１０８又は変更された被検査コード１０８の一部として出力されてよい。変更は、欠陥を修正する又は修正しようとし得る被検査コード１０４内の変更を含んでよい。本開示では、実行され得る変更は、「候補パッチ」と呼ばれてよい。
【００２３】
テストスーツ１１１は、被検査コード１０４のためのテストケースとして動作し得る１つ以上のルーチンを含んでよい。テストスーツ１１１は、被検査コード１０４が指定された方法で動作するか否かを決定するよう構成されてよい。テストスーツ１１１は、任意の適切な技術に従い構成されてよい。
【００２４】
修正モジュール１０６は、被検査コード１０４の中の１つ以上の障害及び対応する障害位置を検出し又は決定するために、被検査コード１０４に対してテストスーツ１１１のうちの１つ以上を適用するよう構成されてよい。幾つかの実施形態では、修正モジュール１０６は、テスト実行の実行として参照され得る、テストスーツ１１１に含まれる１つ以上のテストを実行するよう構成されてよい。合格するテスト実行は、「合格テスト実行」として参照され得る。失敗するテスト実行は、「失敗テスト実行」として参照され得る。幾つかの実施形態では、被検査コード１０４の欠陥位置及び対応する欠陥は、欠陥位置に現れるコードを実行する失敗テスト実行に基づき識別されてよい。本開示では、１つ以上のテストスーツ１１１を満たす候補パッチは、「妥当なパッチ」と呼ばれてよい。
【００２５】
幾つかの実施形態では、修正モジュール１０６は、本願明細書に記載のように候補パッチを生成するよう構成されてよい。
【００２６】
幾つかの実施形態では、修正モジュール１０６は、コードデータベース１１４及びプロジェクトコード１１６を含み得るコードソース１１８にアクセスするよう構成されてよい。コードデータベース１１４は、ビッグコードから導出され得る共通コードパターンを含んでよい。例えば、共通コードパターンは、GitHub等のような既存ソフトウェアプログラムの１つ以上のレポジトリに格納され得る既存ソフトウェアプログラムの既存コードから導出されてよい。
【００２７】
本開示の範囲から逸脱することなく図１に対し変更、追加又は省略が行われてよい。例えば、自動ソフトウェア修正システム１００は、本開示で示され説明されたものより多くの又は少ない要素を有してよい。さらに、幾つかの実施形態では、１つ以上のルーチン、１つ以上の命令、又は修正モジュール１０６のコード、テストスーツ１１１、及び修正テンプレート１１２の少なくとも一部は、それらが同じ要素であり得る又は修正モジュール１０６、テストスーツ１１１、及び修正テンプレート１１２の２つ以上の部分と考えられてよい共通セクションを有し得るように結合されてよい。
【００２８】
図２は、本開示の特定の少なくとも一実施形態による例示的なコンピューティングシステム２０２のブロック図を示す。コンピューティングシステム２０２は、修正モジュール（例えば、修正モジュール１０６）と関連付けられた１つ以上の操作を実施し又は指示するよう構成されてよい。コンピューティングシステム２０２は、プロセッサ２５０、メモリ２５２、及びデータ記憶装置２５４を有してよい。プロセッサ２５０、メモリ２５２、及びデータ記憶装置２５４は、通信可能に結合されてよい。
【００２９】
概して、プロセッサ２５０は、任意の適切な特定用途向け又は汎用コンピュータ、コンピューティングエンティティ、又は種々のコンピュータハードウェア若しくはソフトウェアモジュールを有してよく、任意の適切なコンピュータ可読媒体に格納された命令を実行するよう構成され得る処理装置を用いて実施されてよい。例えば、プロセッサ２５０は、マイクロプロセッサ、マイクロコントローラ、デジタシグナルプロセッサ（DSP）、特定用途向け集積回路（ASIC）、フィールドプログラマブルゲートアレイ（FPGA）又はプログラム命令を解釈し及び／若しくは実行し並びに／又はデータを処理するよう構成された任意の他のデジタル若しくはアナログ回路を有してよい。図２には単一のプロセッサを示したが、プロセッサ２５０は、本開示で説明される任意の数の操作を個々に又は共同で実行する又は実行を指示するよう構成される任意の数のプロセッサを有してよい。さらに、プロセッサのうちの１つ以上は、異なるサーバのような１つ以上の異なる電子装置に存在してよい。
【００３０】
幾つかの実施形態では、プロセッサ２５０は、プログラム命令を解釈し及び／又は実行し、及び／又はメモリ２５２、データ記憶２５４又はメモリ２５２及びデータ記憶装置２５４に格納されたデータを処理してよい。幾つかの実施形態では、プロセッサ２５０は、データ記憶装置２５４からプログラム命令をフェッチし、該プログラム命令をメモリ２５２にロードしてよい。プログラム命令がメモリ２５２にロードされた後、プロセッサ２５０は該プログラム命令を実行してよい。
【００３１】
例えば、幾つかの実施形態では、修正モジュールは、プログラム命令としてデータ記憶装置２５４に含まれてよい。プロセッサ２５０は、データ記憶装置２５４から修正モジュールのプログラム命令をフェッチしてよく、修正モジュールのプログラム命令をメモリ２５２にロードしてよい。修正モジュールのプログラム命令がメモリ２５２にロードされた後、プロセッサ２５０は、コンピューティングシステムが命令により指示されるように修正モジュールと関連する操作を実施できるように、プログラム命令を実行してよい。
【００３２】
メモリ２５２及びデータ記憶装置２５４は、コンピュータ実行可能命令又はデータ構造を伝える又は格納しているコンピュータ可読記憶媒体を含み得る。このようなコンピュータ可読媒体は、プロセッサ２５０のような汎用又は特定目的コンピュータによりアクセスできる任意の利用可能な媒体を含み得る。例として且つ限定ではなく、このようなコンピュータ可読媒体は、RAM（Random  Access  Memory）、ROM（Read-Only  Memory）、EEPROM（Electrically  Erasable  Programmable  Read-Only  Memory）、CD-ROM（Compact  Disc  Read-Only  Memory）又は他の光ディスク記憶装置、磁気ディスク記憶装置又は他の磁気記憶装置、フラッシュメモリ装置（例えば、固体メモリ素子）を含む有形又は非一時的コンピュータ可読記憶媒体、又はコンピュータにより実行可能な命令若しくはデータ構造の形式で特定のプログラムコード手段を伝える若しくは格納するために用いられ汎用若しくは特定目的コンピュータによりアクセス可能な他の記憶媒体を有し得る。上述の組合せも、コンピュータ可読記憶媒体の範囲に包含され得る。コンピュータ実行可能命令は、例えば、プロセッサ２５０に特定の工程又は工程のグループを実行させるよう構成される命令及びデータを含み得る。
【００３３】
本開示の範囲から逸脱することなくコンピューティングシステム２０２に対し変更、追加又は省略が行われてよい。例えば、幾つかの実施形態では、コンピューティングシステム２０２は、明示的に示され又は記載されてない任意の数の他のコンポーネントを有してよい。
【００３４】
図３は、候補パッチを生成し及びテストする方法３００を示す。方法３００は、図１の修正モジュール１０６により及び図２のコンピューティングシステム２０２により実行されてよい。候補パッチは、図１の被検査コード１０４に対応し得る、特定の潜在的欠陥のある（「バグのある」）コード部分を修正しようとする試みの中で、生成されテストされてよい。幾つかの例では、複数のコード部分は、バグ位置特定として記載され得る、潜在的な欠陥として識別されてよい。任意で、バグ報告は、潜在的な欠陥のあるコード部分を識別しようとする試みの中で分析されてよい。代替又は追加で、テストケースの分析及び他のコード診断は、潜在的な欠陥のあるコード部分を識別するために利用されてよい。特定の潜在的な欠陥のあるコード部分が選択されてよく（「選択されたコード部分」）、該コード部分に対して、候補パッチが生成されテストされてよい。例えば、複数の潜在的な欠陥のあるコード部分が、該部分が欠陥がある可能性によりランク付けされてよく、最も欠陥のある可能性が高いと識別されたコード部分が選択されてよい。
【００３５】
方法３００は、ブロック３０２で、修正表現を合成することにより、開始し得る。修正表現は、より複雑なコード部分を生成するためにコード文法を通じて定義されてよい、コードに基づく代替と考えられてよい。幾つかの実施形態では、修正表現の合成は、少なくとも部分的に、文法解析、及び潜在的な欠陥のあるコード部分に関連するコード範囲に基づいてよい。例えば、修正表現は、Java(登録商標)プログラミング言語文法に基づいてよい。代替又は追加で、修正表現は、潜在的な欠陥のあるコード部分の範囲内の、変数、フィールド、配列アクセス、メソッド起動、等、又はそれらの組み合わせに基づいてよい。
【００３６】
一例として且つ限定ではなく、以下の表は、仮定に基づく、潜在的な欠陥のあるコード部分のために合成され得る修正表現のリストを提供する。
【表１】
2020126603.tif 000003
【００３７】
方法３００は、ブロック３０４で、修正表現を検索することにより、継続し得る。修正表現は、図１のプロジェクトコード１１６のようなプロジェクトコード、及び図１のコードデータベース１１４のようなコードデータベース、等から検索されてよい。幾つかの実施形態では、表現は、類似する又は同様のバグ報告、テストケース、等を有するコードから検索されてよい。代替又は追加で、表現は、類似しないバグ報告、テストケース、等を有するコードから検索されてよい。例えば、修正表現は、選択されたコード部分と類似するコード、及び選択されたコード部分と類似しないコード、の両方から検索されてよい。幾つかの実施形態では、最長共通シーケンス（longest  common  sequence：LCS）アルゴリズムが、選択されたコード部分とプロジェクトコード又はコードデータベースからのコード部分との間の類似性を定量化する類似性スコアを生成するために利用されてよい。トークン化が、LCSアルゴリズムによる利用のためにトークンを生成するために、選択されたコード部分及びプロジェクトコード又はコードデータベースからのコード部分に対して実行されてよい。LCSアルゴリズムは、選択されたコード部分とプロジェクトコード又はコードデータベースからの所与のコード部分との間の類似性スコアをもたらしてよい。幾つかの構成では、類似性スコアは、コード部分の間に類似性がないことを表し得る０と、コード部分の間の完全な類似性を表す１と、の間であってよい。例として、例えば０．８のような特定の閾より高い類似性スコアを有するコード部分は、類似すると考えられてよい。特定の閾より低い類似性スコアを有するコード部分は、類似しないと考えられてよい。
【００３８】
幾つかの実施形態では、検索された修正表現は、比較的きめが細くてよい。つまり、検索された修正表現は、幾つかの検索に基づく修正生成ツールの利用し得る完全なパッチとは対照的に、比較的簡潔であってよい。幾つかの実施形態では、修正表現は、選択されたコード部分と類似するコードから、及び選択されたコード部分と類似しないコードから、検索されてよい。
【００３９】
一例として且つ限定ではなく、以下の表は、仮定に基づく、潜在的な欠陥のあるコード部分のために検索され得る修正表現のリストを提供する。
【表２】
2020126603.tif 000004
【００４０】
方法３００は、合成された修正表現及び検索された修正表現から修正表現セットを生成することにより、ブロック３０６へと継続してよい。例えば、修正表現セットは、合成された修正表現及び検索された修正表現を結合すること、及び重複する修正表現を除去することを通じて、形成されてよい。さらに、更なる修正表現は、検索された表現及び合成された表現から合成されてよい。更なる修正表現は、１つ以上の特定のスキーマ種類に従ってよい。例えば、特定スキーマ種類がブール表現を用いる場合、更なる修正表現は、合成された表現及び検索された表見から更に合成された、ブール修正表現を含んでよい。例として、合成された表現及び検索された表現が、修正表現A、B、及びCを含む場合、更なるブール修正表現は、A+B+C、A=B+C、A>B+C、等を含んでよい。
【００４１】
方法３００は、修正スキーマを選択することにより、ブロック３０８へと継続してよい。幾つかの実施形態では、修正スキーマは、少なくとも部分的にヒューリスティック法に基づき選択されてよい。代替又は追加で、スキーマは、少なくとも部分的に、潜在的な欠陥のあるコード部分に位置するコードに基づき選択されてよい。例として、可能な修正スキーマは、仮定に基づく潜在的な欠陥のあるコード部分の、if挿入（If  Insertion）、メソッド起動挿入（Method  Invocation  Insertion）、メソッド起動変更（Method  Invocation  Change）、等を含んでよい。
【００４２】
例えば、以下のif挿入修正スキーマが選択されてよい。
【数１】
2020126603.tif 000005
【００４３】
幾つかの実施形態では、より多くの特定の修正スキーマが選択されてよい。例えば、if挿入修正スキーマの以下の変形は、仮定に基づく潜在的な欠陥のあるコード部分のために選択されてよい。
【数２】
2020126603.tif 000006
【００４４】
方法３００は、候補パッチを生成することにより、ブロック３１０へと継続してよい。例えば、生成した修正表現セットのうちの修正表現は、選択された修正スキーマの中で利用されてよい。コード文法は、候補パッチを生成する際に観察され得る。例えば、ブール表現と見なされる修正表現は、ブール表現に関連付けられた修正スキーマの位置で使用されてよい。
【００４５】
例として、以下の候補パッチは、仮定に基づく潜在的な欠陥のあるコード部分のために生成されてよい。
【数３】
2020126603.tif 000007
【数４】
2020126603.tif 000008
【００４６】
方法３００は、候補パッチをランク付けすることにより、ブロック３１２へと継続してよい。幾つかの実施形態では、上位にランク付けされた候補パッチのうちの何らかの所定数の候補パッチは、テストのために有望であるとして更に識別されてよい。例えば、上位２００万個のランク付けされた候補パッチは、テストのために有望であると識別されてよいが、何らかの他の数のランク付けされた候補パッチがテストのために有望であると識別されてよい。代替として、テストのために有望であると識別された候補パッチは、閾ランク付けスコアに基づいてよい。例えば、閾より高いランク付けスコアを有する候補パッチは、テストのために有望であると考えられてよい。幾つかの構成では、閾より低いランク付けスコアを有する候補パッチは、テストのために有望であると考えられなくてよい。幾つかの更なる構成では、候補パッチをテストのために有望であると識別するために、識別技術の結合が使用されてよい。
【００４７】
幾つかの実施形態では、候補パッチは、バグのあるクラスにおける頻度及び共起分析に関連付けられたスコアによりランク付けされてよい。このようなスコアは、ここでは参照符号f１により識別される。f１スコアは、候補パッチの修正表現がプロジェクトコード内で一緒に生じる頻度の分析に基づいてよい。例として、仮定に基づくプロジェクトコードは、表現A、B、及びCを含んでよく、A及びBがプロジェクトコード内で時折一緒に現れ、A及びCはプロジェクトコード内で一緒に現れない。A及びBの修正表現を含む仮定に基づくプロジェクトコードのための候補パッチは、A及びCの修正表現を含む候補パッチより相対的に高いf１スコアを与えられてよい。
【００４８】
代替又は追加で、候補パッチは、バグのあるメソッドにおける頻度及び共起分析に関連付けられたスコアによりランク付けされてよい。このようなスコアは、ここでは参照符号f２により識別される。f２スコアは、候補パッチの修正表現の間の関係がプロジェクトコード内の特定のバグのあるメソッド内で一緒に生じる頻度の分析に基づいてよい。例として、仮定に基づくプロジェクトコードは、表現A、B、及びC、並びに特定のメソッドがバグであり得る複数のメソッド、を含んでよい。A及びBが特定のバグのあるメソッド内で一緒に現れ、且つA及びCが特定のバグのあるメソッド内で一緒に現れない場合、A及びBの修正表現を含む仮定に基づくプロジェクトコードは、A及びCの修正表現を含む候補パッチより相対的に高いf２スコアを与えられてよい。
【００４９】
代替又は追加で、候補パッチは、述語構造の頻度に関連付けられたスコアによりランク付けされてよい。このようなスコアは、ここでは参照符号f３により識別される。f３スコアは、候補パッチの述語構造が、図１のコードデータベース１１４のようなコードデータベース内で生じる頻度の分析に基づいてよい。例として、コードデータベースは、「A==B」の複数の発生を含んでよく、「A>B」及び「A<B」は現れない又は滅多に現れない。「A==B」を含む仮定に基づくプロジェクトコードのための候補パッチは、「A>B」又は「A<B」を含む候補パッチより相対的に高いf３スコアを与えられてよい。
【００５０】
代替又は追加で、候補パッチは、対イディオムの頻度に関連付けられたスコアによりランク付けされてよい。f４スコアは、候補パッチの対イディオムが、図１のコードデータベース１１４のようなコードデータベース内で生じる頻度の分析に基づいてよい。例として、コードデータベースは、他のテキスト対の数を上回り得る、テキスト「start」を含む対応する表現と対にされたテキスト「end」を含む表現の複数の発生を含んでよい。しばしば一緒に現れることのある用語の他の例は、「high」及び「low」、「minimum」及び「maximum」、「height」及び「width」、等を含み得る。例えば「start」及び「end」を含む仮定に基づくプロジェクトコードのための候補パッチは、あまり一緒に現れない何らかの他の用語対を含む候補パッチより相対的に高いf４スコアを与えられてよい。
【００５１】
幾つかの実施形態では、特定候補パッチの合計スコアは、f１、f２、f３、及びf４スコアの加重和を含んでよい。例えば、合計スコアは、Sθ(f１,f２,f３,f４)に等しくてよい。ここで、θ=[w１,w２,w３,w４]であり、これは重みベクトルであってよく、[f１,f２,f３,f４]は特定候補パッチの特徴ベクトルであってよい。幾つかの例では、特定候補パッチのランク付けスコアは、f１、f２、f３、及びf４スコアの非加重和に等しくてよい（例えば、各スコアの重みが等しい）。
【００５２】
方法３００は、候補パッチを選択することにより、ブロック３１４へと継続してよい。選択された候補パッチは、最も高くランク付けされた未テスト候補パッチであってよい。
【００５３】
方法３００は、選択された候補パッチをテストすることにより、ブロック３１６へと継続してよい。選択された候補パッチは、図１のテストスーツ１１１のようなテストスーツを用いてテストされてよい。
【００５４】
方法３００は、選択された候補パッチが関連テストに合格するか否かを決定することにより、ブロック３１８へと継続してよい。選択された候補パッチが関連テストに合格したと決定された場合、方法は、選択された候補パッチを妥当なパッチとして分類することにより、ブロック３２０へと継続してよい。
【００５５】
選択された候補パッチが関連テストに合格しなかったと決定された場合、方法は、テストのために利用可能な候補パッチが残っているか否かを決定することにより、ブロック３２２へと継続してよい。未テスト候補パッチがテストのために利用可能であると決定された場合、方法３００は、最も高くランク付けされた未テスト候補パッチを選択することにより、ブロック３１４へと戻ってよい。
【００５６】
もはやテストのために利用可能な未テスト候補パッチが無いと決定された場合、方法３００は、修正表現セットから候補パッチを生成するために利用可能な修正スキーマが残っているか否かを決定することにより、ブロック３２４へと継続してよい。候補パッチを生成するために利用可能な修正スキーマが残っていると決定された場合、方法は、次の修正スキーマを選択することにより、ブロック３０８へと戻ってよい。幾つかの実施形態では、候補パッチを生成するために利用可能な修正スキーマが残っていないと決定された場合、異なる潜在的な欠陥のあるコード部分が選択されてよく、方法３００は、該異なる潜在的な欠陥のあるコード部分について繰り返されてよい。
【００５７】
本開示の範囲から逸脱することなく方法３００に対し変更、追加又は省略が行われてよい。例えば、方法３００の工程は、異なる順序で実施されてよい。例えば、コードを正規化することに関連する動作は、記載された又は図示されたものと異なる順序で実行されてよく、又は同時に実行されてよい。
【００５８】
追加又は代替で、２以上の工程が同時に実行されてよい。さらに、概略のステップ及び動作は、単に例として提供され、幾つかのステップ及び動作は、開示の実施形態の本質から逸脱することなく、任意であり、より少ないステップ及び動作に組み合わされ、又は追加ステップ及び動作に拡張されてよい。例えば、幾つかの実施形態では、ハッシュ関数を計算することに関連する動作は省略されてよい。さらに、幾つかの実施形態では、方法３００は反復的に実行されてよく、ここで、一度に、単一の障害位置が分析されてよい。追加又は代替で、１つ以上のブロックに関連する１つ以上の工程は、既存コードの複数のウインドウに関して一度に実行されてよい。
【００５９】
上述のように、本開示で記載した実施形態は、以下に更に詳細に議論するように、種々のコンピュータハードウェア又はソフトウェアモジュールを備えた特定用途又は汎用コンピュータ（例えば、図２のプロセッサ２５０）の使用を含み得る。さらに、上述のように、本開示に記載の実施形態は、コンピュータ実行可能命令又はデータ構造を伝える又はそれを格納されたコンピュータ可読媒体（例えば、図２のメモリ２５２又はデータ記憶装置２５４）を用いて実施されてよい。
【００６０】
本開示で用いられるように、用語「モジュール」は、モジュールのアクションを実行するよう構成される特定ハードウェア実装、及び／又はコンピューティングシステムの汎用ハードウェア（例えばコンピュータ可読媒体、処理装置、等）に格納され及び／又はそれらにより実行され得るソフトウェアオブジェクト又はソフトウェアルーチンを表してよい。幾つかの実施形態では、本開示に記載されたのと異なるモジュール及びメソッドは、（例えば、別個のスレッドとして）コンピューティングシステムで実行されるオブジェクト又は処理として実施されてよい。本開示に記載のシステム及び方法の幾つかは概して（汎用ハードウェアに格納される及び／又はそれにより実行される）ソフトウェアで実装されるように記載されたが、専用ハードウェアの実装又はソフトウェアと専用ハードウェアの組み合わせの実装も可能であり考えられる。この説明では、「コンピュータエンティティ」は、本開示で先に定められたようにコンピューティングシステム、又はコンピューティングシステムで実行されるモジュール若しくはモジュールの組合せであってよい。
【００６１】
本開示で及び特に添付の特許請求の範囲（例えば、添付の特許請求の範囲の本体）で使用される用語は、概して、広義の（open）用語と考えられる（例えば、用語「含む（including）」は「含むが、限定されない」と解釈されるべきであり、用語「有する（having）」は「少なくとも有する」と解釈されるべきであり、用語「含む（includes）」は「含むが、限定されない」と解釈されるべきである）。
【００６２】
さらに、特定数の導入された請求項の引用が意図される場合、このような意図は、請求項の中に明示的に示され、このような引用が存在しない場合はこのような意図が存在しない。例えば、理解の助けとして、以下の添付の特許請求の範囲は、請求項の引用を導入するために、「少なくとも１つの」及び「１又は複数の」をいう前置語句の使用を含み得る。しかしながら、このような語句の使用は、同じ請求項が前置語句「１又は複数」又は「少なくとも１つの」及び「ａ又はａｎ」のような不定冠詞を含むときでも、不定冠詞「ａ、ａｎ」による請求項引用の導入がこのような導入された請求項引用を含む任意の特定の請求項をこのような引用を１つだけ含む実施形態に限定することを示すと考えられてはならない（例えば、「ａ」及び／又は「ａｎ」は「少なくとも１つの」又は「１又は複数の」を意味すると解釈されるべきである）。同様のことは、請求項引用を導入するために使用される定冠詞の使用についても該当する。
【００６３】
さらに、特定数の導入された請求項引用が明示的に引用される場合、当業者は、このような引用が少なくとも引用された番号を意味することと解釈されるべきであることを認識するだろう（例えば、「２つの引用」はそのままで、他の変更が無ければ、少なくとも２つの引用、又は２以上の引用を意味する）。さらに、「Ａ、Ｂ、Ｃ、等のうちの少なくとも１つ」又は「Ａ、Ｂ、Ｃ、等のうちの１又は複数」に類似する慣例が用いられる例では、通常、このような構成は、Ａのみ、Ｂのみ、Ｃのみ、Ａ及びＢを一緒に、Ａ及びＣを一緒に、Ｂ及びＣを一緒に、又はＡ、Ｂ、Ｃを一緒に、等を含むと意図される。
【００６４】
さらに、２以上の代替用語を表す任意の離接語又は語句は、説明、請求項、又は図面の中であるかに係わらず、用語のうちの１つ、用語のうちのいずれか、又は両方の用語を含む可能性を包含すると理解されるべきである。例えば、語句「Ａ又はＢ」は、「Ａ」又は「Ｂ」又は「Ａ及びＢ」の可能性を含むと理解されるべきである。
【００６５】
本開示に記載された全ての例及び条件文は、教育上の目的で、読者が本開示の原理及び発明者により考案された概念を理解するのを助け、技術を促進させるためであり、これらの特に記載された例及び条件に限定されないものと考えられるべきである。本開示の実施形態が詳細に記載されたが、種々の変更、置換及び修正が本開示の範囲から逸脱することなく行われ得る。
【００６６】
以上の実施形態に加え、更に以下の付記を開示する。
（付記１）  自動候補修正パッチ生成の方法であって、前記方法は、
プロジェクトコードに基づき修正表現を合成するステップと、
コードデータベースから簡潔修正表現を検索するステップと、
前記合成した修正表現と前記検索した修正表現とに基づき、修正表現セットを生成するステップであって、前記合成した修正表現と前記検索した修正表現とに基づき更なる修正表現を更に合成するステップを含む、ステップと、
修正スキーマ及び前記修正表現セットに基づき、候補パッチを生成するステップと、
を含む方法。
（付記２）  前記候補パッチをランク付けするステップ、を更に含む付記１に記載の方法。
（付記３）  前記候補パッチをランク付けする前記ステップは、
前記候補パッチの前記修正表現が前記プロジェクトコードの中で一緒に生じる頻度、
前記候補パッチの前記修正表現が前記プロジェクトコードの中のバグのあるメソッド内で一緒に生じる頻度、
前記候補パッチの述語構造が前記コードデータベース内で生じる頻度、
前記候補パッチの対イディオムが前記コードデータベース内で生じる頻度、
に基づく、付記２に記載の方法。
（付記４）  前記候補パッチの前記修正表現が前記プロジェクトコードの中で一緒に生じる前記頻度は、第１スコアに関連付けられ、
前記候補パッチの前記修正表現が前記プロジェクトコードの中のバグのあるメソッド内で一緒に生じる前記頻度は、第２スコアに関連付けられ、
前記候補パッチの述語構造が前記コードデータベース内で生じる前記頻度は、第３スコアに関連付けられ、
前記候補パッチの対イディオムが前記コードデータベース内で生じる前記頻度は、第４スコアに関連付けられ、
前記候補パッチをランク付けする前記ステップは、第１重み値によりスケーリングされた前記第１スコア、第２重み値によりスケーリングされた前記第２スコア、第３重み値によりスケーリングされた前記第３スコア、及び第４重み値によりスケーリングされた前記第４スコアの和に基づく、付記３に記載の方法。
（付記５）  前記候補パッチをランク付けする前記ステップは、前記候補パッチの前記修正表現が前記プロジェクトコード内で一緒に生じる頻度に基づく、付記２に記載の方法。
（付記６）  前記候補パッチをランク付けする前記ステップは、前記候補パッチの前記修正表現が前記プロジェクトコード内のバグのあるメソッド内で一緒に生じる頻度に基づく、付記２に記載の方法。
（付記７）  前記候補パッチをランク付けする前記ステップは、前記候補パッチの述語構造が前記コードデータベース内で生じる頻度に基づく、付記２に記載の方法。
（付記８）  前記候補パッチをランク付けする前記ステップは、前記候補パッチの対イディオムが前記コードデータベース内で生じる頻度に基づく、付記２に記載の方法。
（付記９）  前記候補パッチの前記ランク付けの順序で、前記候補パッチを検査するステップ、を更に含む付記２に記載の方法。
（付記１０）  前記コードデータベースから前記簡潔修正表現を検索する前記ステップは、前記候補パッチが生成されたコード部分に類似するコード部分と、前記候補パッチが生成された前記コード部分に類似しないコード部分と、の両方から修正表現を検索するステップを含む、付記１に記載の方法。
（付記１１）  命令を格納するよう構成された非一時的コンピュータ可読記憶媒体であって、前記命令は、実行されることに応答して、システムに自動候補修正パッチ生成の動作を実行させ、前記動作は、
プロジェクトコードに基づき修正表現を合成するステップと、
コードデータベースから簡潔修正表現を検索するステップと、
前記合成した修正表現と前記検索した修正表現とに基づき、修正表現セットを生成するステップであって、前記合成した修正表現と前記検索した修正表現とに基づき更なる修正表現を更に合成するステップを含む、ステップと、
修正スキーマ及び前記修正表現セットに基づき、候補パッチを生成するステップと、
を含む、コンピュータ可読記憶媒体。
（付記１２）  前記動作は、前記候補パッチをランク付けするステップを更に含む、付記１１に記載のコンピュータ可読記憶媒体。
（付記１３）  前記候補パッチをランク付けする前記ステップは、
前記候補パッチの前記修正表現が前記プロジェクトコードの中で一緒に生じる頻度、
前記候補パッチの前記修正表現が前記プロジェクトコードの中のバグのあるメソッド内で一緒に生じる頻度、
前記候補パッチの述語構造が前記コードデータベース内で生じる頻度、
前記候補パッチの対イディオムが前記コードデータベース内で生じる頻度、
に基づく、付記１２に記載のコンピュータ可読記憶媒体。
（付記１４）  前記候補パッチの前記修正表現が前記プロジェクトコードの中で一緒に生じる前記頻度は、第１スコアに関連付けられ、
前記候補パッチの前記修正表現が前記プロジェクトコードの中のバグのあるメソッド内で一緒に生じる前記頻度は、第２スコアに関連付けられ、
前記候補パッチの述語構造が前記コードデータベース内で生じる前記頻度は、第３スコアに関連付けられ、
前記候補パッチの対イディオムが前記コードデータベース内で生じる前記頻度は、第４スコアに関連付けられ、
前記候補パッチをランク付けする前記ステップは、第１重み値によりスケーリングされた前記第１スコア、第２重み値によりスケーリングされた前記第２スコア、第３重み値によりスケーリングされた前記第３スコア、及び第４重み値によりスケーリングされた前記第４スコアの和に基づく、付記１３に記載のコンピュータ可読記憶媒体。
（付記１５）  前記候補パッチをランク付けする前記ステップは、前記候補パッチの前記修正表現が前記プロジェクトコード内で一緒に生じる頻度に基づく、付記１２に記載のコンピュータ可読記憶媒体。
（付記１６）  前記候補パッチをランク付けする前記ステップは、前記候補パッチの前記修正表現が前記プロジェクトコード内のバグのあるメソッド内で一緒に生じる頻度に基づく、付記１２に記載のコンピュータ可読記憶媒体。
（付記１７）  前記候補パッチをランク付けする前記ステップは、前記候補パッチの述語構造が前記コードデータベース内で生じる頻度に基づく、付記１２に記載のコンピュータ可読記憶媒体。
（付記１８）  前記候補パッチをランク付けする前記ステップは、前記候補パッチの対イディオムが前記コードデータベース内で生じる頻度に基づく、付記１２に記載のコンピュータ可読記憶媒体。
（付記１９）  前記動作は、前記候補パッチの前記ランク付けの順序で、前記候補パッチを検査するステップ、を更に含む付記１２に記載のコンピュータ可読記憶媒体。
（付記２０）  前記コードデータベースから前記簡潔修正表現を検索する前記ステップは、前記候補パッチが生成されたコード部分に類似するコード部分と、前記候補パッチが生成された前記コード部分に類似しないコード部分と、の両方から修正表現を検索するステップを含む、付記１１に記載のコンピュータ可読記憶媒体。
【符号の説明】
【００６７】
１００  自動ソフトウェア修正システム
１０４  被検査コード
１０６  修正モジュール
１０８  変更された被検査コード
１１１  テストスーツ
１１２  スキーマ
１１４  コードデータベース
１１６  プロジェクトコード
１１８  コードソース
【図１】
2020126603.tif 000009
【図２】
2020126603.tif 000010
【図３】
2020126603.tif 000011