Model-based approaches to the verification of non-terminating Cyber-Physical Systems (CPSs) usually rely on numerical simulation of the System Under Verification (SUV) model under input scenarios of possibly varying duration, chosen among those satisfying given constraints. Such constraints typically stem from requirements (or assumptions) on the SUV inputs and its operational environment as well as from the enforcement of additional conditions aiming at, e.g., prioritising the (often extremely long) verification activity, by, e.g., focusing on scenarios explicitly exercising selected requirements, or avoiding vacuity in their satisfaction. In this setting, the possibility to efficiently sample at random (with a known distribution, e.g., uniformly) within, or to efficiently enumerate (possibly in a uniformly random order) scenarios among those satisfying the given constraints is a key enabler for the viability of the verification process, e.g., via simulation-based statistical model checking. Unfortunately, in case of non-trivial combinations of constraints, iterative approaches like Markovian random walks in the space of sequences of inputs in general fail in extracting scenarios according to a given distribution, and can be very inefficient to produce legal scenarios of interest. We show how, given a set of constraints on the input scenarios succinctly defined by finite memory monitors, a data structure (scenario generator) can be synthesised, from which any-horizon scenarios satisfying the input constraints can be efficiently extracted by (possibly uniform) random sampling or (randomised) enumeration. Our approach enables seamless support to virtually all simulation-based approaches to CPS verification, ranging from simple random testing to statistical model checking and formal (i.e., exhaustive) verification.
翻译:以模型为基础的方法来核查非结束性网络-物理系统(CPS),这种方法通常依赖在可能不同期限的输入假设情景下对核查系统(SUV)模型进行数字模拟,这种模拟可能是在满足特定限制的情况下选择的,这些限制通常来自对SUV投入及其业务环境的要求(或假设),以及执行其他条件,目的是,例如,通过以模拟为基础的统计模式检查,优先考虑(通常非常长的)核查活动,例如,通过明确采用某些要求的假设情景,或避免其满意度的出现。在这一背景下,有可能在随机(已知的随机分布,例如统一)内部或高效率地(以统一的随机顺序)抽样抽取“核查系统”模型模型模型模型模型模型模型模型模型模型模型模型模型模型,例如明确使用某些限制,或避免其满意度出现空洞。