On Automated N-way Program Merging for Facilitating Family-based Analyses of Variant-rich Software
On Automated N-way Program Merging for Facilitating Family-based Analyses of Variant-rich Software
复制标题
关于自动 N 路程序合并以促进基于族的富变体软件分析
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Malte Lochau
中科院分区：
文献类型：
--
作者：
Dennis Reuling;U. Kelter;Johannes Bürdek;Malte Lochau
：在这项工作中，我们报告了最初发表在 ACM Transactions on Software Engineering and Methodology (TOSEM)，第 28 卷，第 3 期，2019 [Re19] 上的研究成果。如今，软件有许多不同但相似的变体，通常通过克隆和拥有从通用代码衍生而来。与逐个变体的方法相比，基于家族的分析策略显示出提高富含变体程序的质量保证效率的巨大潜力。不幸的是，这些策略需要一种叠加的程序表示，以语法良好、语义合理和变量保留的方式包含所有程序变体，这在实践中很难手动获得。在本次演讲中，我们介绍了用于生成程序变体叠加的 SiMPOSE 方法，以促进对富含变体的软件进行基于系列的分析。我们利用一种新颖的 N 路模型合并方法来表示 C 程序的控制流自动机 (CFA)，这是许多最新软件分析工具使用的抽象。为了应对 N 路合并的复杂性，我们使用相似性传播来减少 N 路匹配的数量，并实现任意变体子集的增量合并。我们将 SiMPOSE 工具应用于实际的 C 程序，并研究基于系列的程序分析的适用性和效率/有效性权衡。我们的结果表明，与逐个变体相比，在稳定有效性下，单元测试生成的效率提高了 2.6 倍，模型检查的效率提高了 2.4 倍。
: In this work, we report about research results initially published in ACM Transactions on Software Engineering and Methodology (TOSEM), volume 28 Issue 3, 2019 [Re19]. Nowadays software comes in many different, yet similar variants, often derived from common code via clone-and-own. Family-based-analysis strategies show promising potentials for improving efficiency of quality assurance for variant-rich programs, as compared to variant-by-variant approaches. Unfortunately, these strategies require one superimposed program representation containing all program variants in a syntactically well-formed, semantically sound, and variant-preserving manner, which is hard to obtain manually in practice. In this talk, we present our methodology SiMPOSE for generating superimpositions of program variants to facilitate family-based analyses of variant-rich software. We utilize a novel N-way model-merging methodology for control-Ćow automaton (CFA) representations of C programs, an abstraction used by many recent software-analysis tools. To cope with the complexity of N-way merging, we use similarity-propagation to reduce the number of N-way matches and enable incremental merging of arbitrary subsets of variants. We apply our SiMPOSE tool to realistic C programs and investigate applicability and efficiency/effectiveness trade-offs of family-based program analyses. Our results reveal efficiency improvements by a factor of up to 2.6 for unit-test generation and 2.4 for model-checking under stable effectiveness, as compared to variant-by-variant.