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的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

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

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

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

Synthesizing Legacy String Code for FPGAs Using Bounded Automata Learning

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

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

Multiplicative Weights Algorithms for Parallel Automated Software Repair

用于并行自动软件修复的乘法权重算法

• DOI: 10.1109/ipdps49936.2021.00107
• 发表时间: 2021
• 期刊: International Parallel and Distributed Processing Symposium
• 作者: Renzullo, Joseph;Weimer, Westley;Forrest, Stephanie
• 通讯作者: Forrest, Stephanie

CirFix: automatically repairing defects in hardware design code

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