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

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

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.