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

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 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准。

项目成果

Debugging with Stack Overflow: Web Search Behavior in Novice and Expert Programmers

使用 Stack Overflow 进行调试：新手和专家程序员的 Web 搜索行为

• DOI: 10.1145/3510456.3514147
• 发表时间: 2022-05-01
• 期刊: 2022 IEEE/ACM 44th International Conference on Software Engineering: Software Engineering Education and Training (ICSE-SEET)
• 作者: Annie Li;Madeline Endres;Westley Weimer
• 通讯作者: Westley Weimer

Synthesizing Legacy String Code for FPGAs Using Bounded Automata Learning

使用有界自动机学习合成 FPGA 的遗留字符串代码

• DOI: 10.1109/mm.2022.3178037
• 发表时间: 2022-09
• 期刊: IEEE Micro
• 影响因子: 3.6
• 作者: Angstadt, Kevin;Tracy, Tommy;Skadron, Kevin;Jeannin, Jean;Weimer, Westley
• 通讯作者: Weimer, Westley

What can program repair learn from code review?

程序修复可以从代码审查中学到什么？

• DOI: 10.1145/3524459.3527352
• 发表时间: 2022-05
• 期刊: International Workshop on Automated Program Repair
• 作者: Endres, Madeline;Reiter, Pemma;Forrest, Stephanie;Weimer, Westley
• 通讯作者: Weimer, Westley

MA-ABC: a memetic algorithm optimizing attractiveness, balance, and cost for capacitated Arc routing problems

MA-ABC：一种模因算法，优化容量弧路由问题的吸引力、平衡和成本

• DOI: 10.1145/3449639.3459268
• 发表时间: 2021-06-26
• 期刊: Proceedings of the Genetic and Evolutionary Computation Conference
• 作者: Muhilan Ramamoorthy;S. Forrest;V. Syrotiuk
• 通讯作者: V. Syrotiuk

CirFix: automatically repairing defects in hardware design code

CirFix：自动修复硬件设计代码中的缺陷

• DOI: 10.1145/3503222.3507763
• 发表时间: 2022-02-28
• 期刊: Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems
• 作者: Hammad Ahmad;Yu Huang;Westley Weimer
• 通讯作者: Westley Weimer