TL;DR
This paper tackles the challenge of "conjunctive synthesis" for cyber-physical systems (CPS), where a system must satisfy multiple, potentially conflicting, requirements simultaneously. They propose a novel approach that reframes this as a constrained optimization problem, leveraging a technique called Multiple Constraint Ranking (MCR) with an evolutionary algorithm (CMA-ES) to effectively handle the inherent complexities and "scale problem" often encountered in such tasks.
What Problem Does This Paper Address?
Ensuring the reliability of cyber-physical systems (CPS) is crucial, but formally verifying them is often difficult due to their complex, hybrid nature and the lack of perfect system models. "Falsification," a lighter-weight formal method, aims to find counterexamples to specifications. However, a significant challenge arises when synthesizing systems that must satisfy multiple requirements at once – a "conjunctive synthesis" problem. These requirements can be contradictory, demanding delicate trade-offs. Existing optimization-based falsification methods struggle with this, particularly due to the "scale problem," where the robustness values of different requirements can vary drastically, masking the true difficulty of satisfying some. This paper addresses how to effectively synthesize CPS that meet these complex, conjunctive specifications.
Methods
The core contribution is reframing the conjunctive synthesis problem as a constrained optimization problem. Instead of trying to optimize a single objective function that combines all requirements (which suffers from the scale problem), they propose to optimize one requirement while treating the others as constraints.
They then integrate this with Multiple Constraint Ranking (MCR), a technique designed to handle multiple, potentially conflicting constraints without requiring users to manually tune parameters for each constraint's scale. MCR works by ranking candidate solutions based on their constraint satisfaction and objective function performance, rather than relying solely on raw robustness values.
This MCR technique is combined with CMA-ES (Covariance Matrix Adaptation Evolution Strategy), a powerful evolutionary algorithm well-suited for optimization-based falsification. The paper details how MCR can be seamlessly integrated into CMA-ES's iterative process, allowing it to effectively search for input signals that satisfy all conjunctive specifications.
Datasets
The paper evaluates their approach using several benchmark models and specifications commonly found in the falsification literature:
- Automatic Transmission (AT): A model with inputs (throttle, brake) and outputs (gear, rpm, speed). Specifications tested include AT1p, AT2, AT3p1,p2, which involve constraints on speed, RPM, and gear.
- Automotive Fuel Control (AFC): A model with inputs (throttle, engine) and outputs (mode, air-fuel ratio deviation). Specifications focus on mode transitions and engine behavior.
- Wind Turbine (WT): A model with input (wind speed) and outputs (blade pitch, generator torque, rotor speed). Specifications involve operating ranges for wind speed, torque, and rotor speed.
These benchmarks are used to demonstrate the effectiveness of their MCR-based approach, particularly on instances where the scale problem is prominent.
Key Insights and Ideas
- Reframing Conjunctive Synthesis: The most significant insight is transforming conjunctive synthesis into a constrained optimization problem. This allows for a more structured approach to handling conflicting requirements.
- MCR as a Solution to the Scale Problem: MCR proves to be a highly effective constraint handling technique for the scale problem. By using rankings instead of raw robustness values, it prevents one requirement's large robustness value from dominating the optimization process.
- Seamless Integration with Evolutionary Algorithms: The paper demonstrates that MCR can be modularly integrated with existing evolutionary algorithms like CMA-ES, making it a practical extension for current falsification tools.
- Objective Choice Matters, But MCR Mitigates Extremes: While the choice of which conjunct to optimize can influence performance, MCR generally leads to more robust and successful synthesis compared to standard methods, even with less optimal objective choices.
Key Results
The experiments show that their proposed "MCR" approach significantly improves success rates (SR) in conjunctive synthesis, especially for challenging problem instances that exhibit the scale problem.
- For the hardest instance, AT12300, standard Breach (using CMA-ES) achieved an SR of 0, while MCR achieved an SR of approximately 50% (9 out of 20 trials).
- Across various benchmarks, MCR consistently achieved comparable or higher success rates than standard Breach implementations.
- While MCR sometimes incurs a higher execution time (e.g., several times longer), this overhead is deemed admissible given the substantial increase in success rate. The average execution time for successful trials was often comparable or only moderately higher.
Limitations and Future Work
- Limitations: The paper acknowledges that the choice of which conjunct to use as the objective in the constrained optimization problem can still influence performance, although MCR mitigates the severity of this impact. The current work focuses on specifications that are conjunctions of temporal logic formulas.
- Future Work: The authors suggest extending their constrained optimization approach to more general forms of specifications beyond simple disjunctions. Investigating methods for automatically choosing the "best" objective conjunct for a given problem is also identified as a promising future direction.
Summary updated