On Automated N-way Program Merging for Facilitating Family-based Analyses of Variant-rich Software

Abstract

In this work, we report about research results initially published in ACM Transactions on Software Engineering and Methodology (TOSEM), volume 28 Issue 3, 2019. 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-flow 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.