一句话：提出基于可扩展逻辑组的新采样器，首次可对 Linux 内核这类超大可配置系统高效生成随机有效配置。
软件系统的可配置性日益增强，Linux 内核是典型代表：它支持数千个可配置特征，可适配从手机到超级计算机的各类硬件。对可配置系统上的诸多问题（如补全部分配置以获得能耗最低或优化其他质量属性的实例）而言，穷举分析所有配置在理论上可行，但配置空间通常极其庞大而无法实际计算，因此只能通过分析配置样本来近似求解。然而生成这类样本并不容易：特征之间往往存在相互依赖，构成的约束使配置空间大为收缩，随机获得一个合法配置的概率极低。为此已有多种先进的采样器被提出，但迄今没有任何采样器能够处理 Linux 内核这类高度可配置的复杂系统。本文提出一种新的采样器，其理论基础是作者提出的「可扩展逻辑组」（extensible logic groups）。作者将该采样器与五种已有方法进行对比，结果表明该工具在速度与可扩展性上均表现最佳。
Software systems are becoming increasingly configurable. A paradigmatic example is the Linux kernel, which can be adjusted for a tremendous variety of hardware devices, from mobile phones to supercomputers, thanks to the thousands of configurable features it supports. In principle, many relevant problems on configurable systems, such as completing a partial configuration to get the system instance that consumes the least energy or optimizes any other quality attribute, could be solved through exhaustive analysis of all configurations. However, configuration spaces are typically colossal and cannot be entirely computed in practice. Alternatively, configuration samples can be analyzed to approximate the answers. Generating those samples is not trivial since features usually have inter-dependencies that constrain the configuration space. Therefore, getting a single valid configuration by chance is extremely unlikely. As a result, advanced samplers are being proposed to generate random samples at a reasonable computational cost. However, to date, no sampler can deal with highly configurable complex systems, such as the Linux kernel. This paper proposes a new sampler that does scale for those systems, based on an original theoretical approach called extensible logic groups. The sampler is compared against five other approaches. Results show our tool to be the fastest and most scalable one.
@inproceedings{paperbot7313,
title = {Scalable Sampling of Highly-Configurable Systems: Generating Random Instances of the Linux Kernel},
author = {David Fernandez-Amoros and Ruben Heradio and Christoph Mayr-Dorn and Alexander Egyed},
booktitle = {ASE},
year = {2022},
doi = {10.1145/3551349.3556899}
}