Coverage Explorer: Coverage-guided Test Generation for Cyber Physical Systems

📄 arXiv: 2312.02313v1 📥 PDF

作者: Sanaz Sheikhi, Stanley Bak

分类: eess.SY, math.NA

发布日期: 2023-12-04

💡 一句话要点

提出Coverage Explorer，通过覆盖引导的测试生成方法提升网络物理系统测试效率。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 网络物理系统 测试生成 覆盖引导 替代模型 模型预测控制

📋 核心要点

  1. 网络物理系统测试面临挑战，传统软硬件测试方法无法提供充分的覆盖率。
  2. Coverage Explorer框架通过覆盖引导的采样和替代模型，系统地生成测试用例，探索CPS状态空间。
  3. 实验表明，该框架在多个CPS基准测试中优于随机测试和S-TaLiRo等方法。

📝 摘要（中文）

本文提出了一种针对网络物理系统（CPS）的测试框架，旨在系统地生成测试用例，有效探索CPS的状态空间。该框架引入了一种以覆盖为中心的采样技术，并结合基于聚类的方法来训练替代模型。然后，该框架在替代模型中使用模型预测控制（MPC）来生成针对CPS规范量身定制的测试用例。为了评估该框架的有效性，我们将其应用于多个基准测试，从运动学车辆到无人机防撞系统（ACAS XU）和自动变速器系统。进行了与替代测试生成策略（包括随机测试）以及使用S-TaLiRo进行伪造的比较分析。

🔬 方法详解

问题定义：网络物理系统（CPS）的测试至关重要，但传统的软件和硬件测试方法无法提供足够的覆盖率，难以发现潜在的安全隐患。现有的测试方法，如随机测试，效率低下，而形式化验证方法（如S-TaLiRo）在处理复杂系统时面临可扩展性问题。因此，需要一种能够系统地生成测试用例，有效探索CPS状态空间的方法。

核心思路：Coverage Explorer的核心思路是利用覆盖率信息引导测试用例的生成。首先，通过覆盖率指标来指导采样，更有针对性地探索未充分测试的状态空间。其次，使用替代模型（surrogate model）来近似复杂的CPS行为，从而加速测试过程。最后，利用模型预测控制（MPC）在替代模型中生成满足CPS规范的测试用例。

技术框架：Coverage Explorer框架主要包含以下几个模块：1) 覆盖率引导的采样：根据覆盖率指标选择下一个要探索的状态空间区域。2) 基于聚类的替代模型训练：使用聚类算法对状态空间进行划分，并为每个簇训练一个替代模型，以近似CPS在该区域的行为。3) 基于MPC的测试用例生成：利用模型预测控制在替代模型中生成测试用例，目标是最大化覆盖率并满足CPS的安全规范。4) 测试用例执行与评估：将生成的测试用例应用于实际的CPS或其仿真模型，并评估其覆盖率和有效性。

关键创新：Coverage Explorer的关键创新在于将覆盖率信息融入到测试用例生成过程中。传统的测试方法通常是随机的或基于启发式的，而Coverage Explorer通过覆盖率指标来指导采样，从而更有针对性地探索未充分测试的状态空间，提高测试效率。此外，使用基于聚类的替代模型可以有效地近似复杂的CPS行为，加速测试过程。

关键设计：在覆盖率引导的采样中，需要选择合适的覆盖率指标，例如状态空间的划分粒度。在替代模型训练中，需要选择合适的聚类算法和替代模型类型（例如高斯过程或神经网络）。在基于MPC的测试用例生成中，需要定义合适的奖励函数，以平衡覆盖率和安全规范。此外，还需要考虑替代模型的精度和计算成本，以及MPC的优化算法。

📊 实验亮点

实验结果表明，Coverage Explorer在多个CPS基准测试中优于随机测试和S-TaLiRo。例如，在ACAS XU防撞系统中，Coverage Explorer能够更快地发现违反安全规范的测试用例，并且覆盖率显著高于其他方法。具体数据未知，但结论是Coverage Explorer在测试效率和覆盖率方面具有明显优势。

🎯 应用场景

该研究成果可广泛应用于各种网络物理系统的测试，例如自动驾驶汽车、无人机、机器人和智能电网等。通过提高测试效率和覆盖率，可以更有效地发现CPS中的潜在安全隐患，从而提高系统的可靠性和安全性。未来，该方法可以进一步扩展到更复杂的CPS，并与其他测试技术相结合，形成更完善的测试体系。

📄 摘要（原文）

Given the safety-critical functions of autonomous cyber-physical systems (CPS) across diverse domains, testing these systems is essential. While conventional software and hardware testing methodologies offer partial insights, they frequently do not provide adequate coverage in a CPS. In this study, we introduce a testing framework designed to systematically formulate test cases, effectively exploring the state space of CPS. This framework introduces a coverage-centric sampling technique, coupled with a cluster-based methodology for training a surrogate model. The framework then uses model predictive control within the surrogate model to generates test cases tailored to CPS specifications. To evaluate the efficacy of the framework, we applied it on several benchmarks, spanning from a kinematic car to systems like an unmanned aircraft collision avoidance system (ACAS XU) and automatic transmission system. Comparative analyses were conducted against alternative test generation strategies, including randomized testing, as well as falsification using S-TaLiRo.