An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems
We present the first systematic analysis of the characteristics of patch search spaces for automatic patch generation systems. We analyze the search spaces of two current state-of- the-art systems, SPR and Prophet, with 16 different search space configurations. Our results are derived from an analys...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Published: |
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/101211 |
| _version_ | 1811094728829042688 |
|---|---|
| author | Long, Fan Rinard, Martin |
| author2 | Martin Rinard |
| author_facet | Martin Rinard Long, Fan Rinard, Martin |
| author_sort | Long, Fan |
| collection | MIT |
| description | We present the first systematic analysis of the characteristics of patch search spaces for automatic patch generation systems. We analyze the search spaces of two current state-of- the-art systems, SPR and Prophet, with 16 different search space configurations. Our results are derived from an analysis of 1104 different search spaces and 768 patch generation executions. Together these experiments consumed over 9000 hours of CPU time on Amazon EC2.The analysis shows that 1) correct patches are sparse in the search spaces (typically at most one correct patch per search space per defect), 2) incorrect patches that nevertheless pass all of the test cases in the validation test suite are typically orders of magnitude more abundant, and 3) leveraging information other than the test suite is therefore critical for enabling the system to successfully isolate correct patches.We also characterize a key tradeoff in the structure of the search spaces. Larger and richer search spaces that contain correct patches for more defects can actually cause systems to find fewer, not more, correct patches. We identify two reasons for this phenomenon: 1) increased validation times because of the presence of more candidate patches and 2) more incorrect patches that pass the test suite and block the discovery of correct patches. These fundamental properties, which are all characterized for the first time in this paper, help explain why past systems often fail to generate correct patches and help identify challenges, opportunities, and productive future directions for the field. |
| first_indexed | 2024-09-23T16:04:08Z |
| id | mit-1721.1/101211 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:04:08Z |
| publishDate | 2016 |
| record_format | dspace |
| spelling | mit-1721.1/1012112019-04-12T15:56:50Z An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems Long, Fan Rinard, Martin Martin Rinard Program Analysis and Compilation Program repair We present the first systematic analysis of the characteristics of patch search spaces for automatic patch generation systems. We analyze the search spaces of two current state-of- the-art systems, SPR and Prophet, with 16 different search space configurations. Our results are derived from an analysis of 1104 different search spaces and 768 patch generation executions. Together these experiments consumed over 9000 hours of CPU time on Amazon EC2.The analysis shows that 1) correct patches are sparse in the search spaces (typically at most one correct patch per search space per defect), 2) incorrect patches that nevertheless pass all of the test cases in the validation test suite are typically orders of magnitude more abundant, and 3) leveraging information other than the test suite is therefore critical for enabling the system to successfully isolate correct patches.We also characterize a key tradeoff in the structure of the search spaces. Larger and richer search spaces that contain correct patches for more defects can actually cause systems to find fewer, not more, correct patches. We identify two reasons for this phenomenon: 1) increased validation times because of the presence of more candidate patches and 2) more incorrect patches that pass the test suite and block the discovery of correct patches. These fundamental properties, which are all characterized for the first time in this paper, help explain why past systems often fail to generate correct patches and help identify challenges, opportunities, and productive future directions for the field. 2016-02-18T20:45:03Z 2016-02-18T20:45:03Z 2016-02-18 2016-02-18T20:45:03Z http://hdl.handle.net/1721.1/101211 MIT-CSAIL-TR-2016-003 45 p. application/pdf |
| spellingShingle | Program repair Long, Fan Rinard, Martin An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems |
| title | An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems |
| title_full | An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems |
| title_fullStr | An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems |
| title_full_unstemmed | An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems |
| title_short | An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems |
| title_sort | analysis of the search spaces for generate and validate patch generation systems |
| topic | Program repair |
| url | http://hdl.handle.net/1721.1/101211 |
| work_keys_str_mv | AT longfan ananalysisofthesearchspacesforgenerateandvalidatepatchgenerationsystems AT rinardmartin ananalysisofthesearchspacesforgenerateandvalidatepatchgenerationsystems AT longfan analysisofthesearchspacesforgenerateandvalidatepatchgenerationsystems AT rinardmartin analysisofthesearchspacesforgenerateandvalidatepatchgenerationsystems |