SHF: Small: Collaborative Research: Understanding and Evolving Search-based Software Improvement

SHF：小型：协作研究：理解和发展基于搜索的软件改进

• 批准号: 1908233
• 负责人: Stephanie Forrest
• 金额: $ 25万
• 依托单位: Arizona State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1908233&HistoricalAwards=false
• 关键词: SHF; Small; Collaborative; Research; Understanding

Software is pervasive, supporting entertainment, finances, health care, travel, and social interactions. Latent software glitches, or bugs, are costly to diagnose and repair. Today, most software bugs are repaired by highly-trained software engineers, but it is uneconomical to repair all such bugs manually, and even for important security-critical problems there can be long delays between bug discoveries and fixes. This project develops improved methods for automatically finding repairs for software bugs, thus addressing a key component of the high cost of software maintenance. Techniques for automated software improvement have matured over the pastdecade, and industry has begun adopting the more successful approaches. Despite these successes, current methods can repair only a fraction of presented bugs. The project focuses on extending the range of existing techniques, which search for small changes to the buggy program that will repair the error. Current approaches use search that is analogous to "looking for one's keys under a streetlamp": they search where it is easy, not where it would be most effective. By leveraging insights from evolutionarybiology and on-line learning methods, new algorithms will be developed that explore more aggressively, thus finding more repairs for more complex bugs more often and more consistently. In addition to repairing bugs, the new algorithms will be tested on other aspects of software improvement, for instance, reducing how much energy a program uses when it executes.All search algorithms face a tradeoff between exploration and exploitation, balancing continued refinement of current good solutions against looking for even better solutions farther afield. Current methods for search-based software improvement overemphasize exploitation, limiting searches to only one or two changes to the original program. To search more aggressively, the project focuses on the space of "neutral" or "safe" program edits, adapting the concept of the space of neutral mutations in biology, where there is extensive theory and analysis to describe its topology and account for negative interactions among mutations. The project: (1) adapts these analyses to the software domain, (2) uses them to design new program-improvement algorithms, and (3) tests the algorithms quantitatively using three important software-improvement domains: software repair, energy optimization, and optimizing speed/accuracy tradeoffs. The resulting algorithm is a radical departure from existing search-based methods, because it eliminates two key components: selection of the highest-performing samples from a population and recombination of high-performing partial solutions. By focusing on exploration, and by quantifying important properties of the search space, the project complements work by other researchers to improve mutation operators, fault localization, and fitness functions.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

软件无处不在，支持着娱乐、金融、医疗、旅游和社会互动。潜在的软件故障或漏洞的诊断和修复是昂贵的。今天，大多数软件错误都是由训练有素的软件工程师修复的，但是手动修复所有这些错误是不经济的，甚至对于重要的安全关键问题，在错误发现和修复之间也可能有很长的延迟。该项目开发了改进的方法，用于自动查找软件错误的修复，从而解决了软件维护高成本的一个关键组成部分。自动化软件改进的技术在过去的十年中已经成熟，并且行业已经开始采用更成功的方法。尽管取得了这些成功，但目前的方法只能修复一小部分出现的错误。该项目专注于扩展现有技术的范围，这些技术搜索对有bug的程序进行的微小更改，以修复错误。目前的搜索方法类似于“在路灯下找钥匙”：他们搜索容易找到的地方，而不是最有效的地方。通过利用进化生物学和在线学习方法的见解，将开发出更积极探索的新算法，从而更频繁、更一致地为更复杂的错误找到更多的修复方法。除了修复漏洞，新算法还将在软件改进的其他方面进行测试，例如，减少程序执行时的能耗。所有的搜索算法都面临着探索和利用之间的权衡，平衡当前良好解决方案的持续改进与寻找更远的更好解决方案之间的平衡。当前基于搜索的软件改进方法过分强调利用，将搜索限制在对原始程序的一两个更改上。为了更积极地搜索，该项目专注于“中性”或“安全”程序编辑的空间，适应生物学中中性突变空间的概念，其中有广泛的理论和分析来描述其拓扑结构并解释突变之间的负相互作用。该项目：(1)将这些分析适应于软件领域，(2)使用它们来设计新的程序改进算法，以及(3)使用三个重要的软件改进领域定量地测试算法：软件修复、能量优化和优化速度/精度权衡。由此产生的算法与现有的基于搜索的方法完全不同，因为它消除了两个关键组成部分：从总体中选择性能最高的样本，以及高性能部分解的重组。通过专注于探索和量化搜索空间的重要属性，该项目补充了其他研究人员在改进突变算子、故障定位和适应度函数方面的工作。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Improving source-code representations to enhance search-based software repair

改进源代码表示以增强基于搜索的软件修复

• DOI: 10.1145/3512290.3528864
• 发表时间: 2022
• 期刊: Massachusetts
• 作者: Reiter, Pemma;Espinoza, Antonio M.;Doupé, Adam;Wang, Ruoyu;Weimer, Westley;Forrest, Stephanie
• 通讯作者: Forrest, Stephanie

A biological perspective on evolutionary computation

• DOI: 10.1038/s42256-020-00278-8
• 发表时间: 2021-01-01
• 期刊: NATURE MACHINE INTELLIGENCE
• 影响因子: 23.8
• 作者: Miikkulainen, Risto;Forrest, Stephanie
• 通讯作者: Forrest, Stephanie

What Can Program Repair Learn From Code Review?

• DOI: 10.1145/3524459.3527352
• 发表时间: 2022-05
• 期刊: 2022 IEEE/ACM International Workshop on Automated Program Repair (APR)
• 作者: Madeline Endres;Pemma Reiter;S. Forrest;Westley Weimer

AI reflections in 2021

2021 年人工智能反思

• DOI: 10.1038/s42256-021-00435-7
• 发表时间: 2022
• 期刊: Nature Machine Intelligence
• 影响因子: 23.8
• 作者: Buckner, Cameron;Miikkulainen, Risto;Forrest, Stephanie;Milano, Silvia;Zou, James;Prunk, Carina;Irrgang, Christopher;Cohen, I. Glenn;Su, Hao;Murphy, Robin R.
• 通讯作者: Murphy, Robin R.

Digging into Semantics: Where Do Search-Based Software Repair Methods Search?

• DOI: 10.1007/978-3-031-14721-0_1
• 发表时间: 2022
• 作者: Hammad Ahmad;Padriac Cashin;S. Forrest;Westley Weimer