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

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

• 批准号: 1908633
• 负责人: Westley Weimer
• 金额: $ 25万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1908633&HistoricalAwards=false
• 关键词: SHF; Small; Collaborative; Research; Understanding; 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.

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