Constrained Optimization for Falsification and Conjunctive Synthesis

Sota Sato, Masaki Waga, Ichiro Hasuo

Abstract

Conjunctive synthesis in Cyber-Physical Systems (CPS) involves finding input signals that satisfy multiple requirements simultaneously. Traditional optimization-based approaches often fail due to the "scale problem," where requirements with large numerical ranges dominate the search process. This paper presents a novel approach using Multiple Constraint Ranking (MCR) within a constrained optimization framework. By ranking candidate solutions rather than relying on raw robustness values, the proposed method effectively normalizes disparate physical units. Experimental results on standard benchmarks demonstrate significant improvements in success rates and computational efficiency compared to state-of-the-art tools.

Introduction

Designing and verifying Cyber-Physical Systems (CPS)—such as autonomous vehicles or medical devices—is a complex task due to the interplay between discrete logic and continuous physical dynamics. Engineers frequently employ falsification to identify inputs that violate specifications, or synthesis to find inputs that satisfy them. A significant challenge arises with "conjunctive" specifications, where multiple, often conflicting, requirements must be met at once (e.g., reaching a target speed while maintaining engine RPM within a safe range).

The Scale Problem

In standard optimization-based synthesis, "robustness values" guide the search by quantifying how well a requirement is satisfied. Typically, the goal is to maximize the minimum robustness across all conjuncts. However, CPS requirements often involve variables with vastly different numerical scales—for instance, RPM in the thousands versus gear numbers in single digits.

This leads to the Scale Problem: the optimizer becomes "blind" to small-scale requirements because it is preoccupied with large-scale changes in other variables. As illustrated in the table below, an individual $u_1$ might show a very high robustness in one dimension (1400) but a low one in another (-2). Standard min-max optimization may fail to prioritize the critical small-scale requirements.

The Scale Problem: Large robustness values (e.g., 1400) can dominate smaller ones (e.g., -2), making it difficult for optimizers to balance multiple requirements.

Methodology

We propose reframing the synthesis task as a constrained optimization problem. Instead of maximizing the minimum robustness, we select one requirement as the primary objective and treat the remaining conjuncts as constraints that must remain above a zero-threshold.

Multiple Constraint Ranking (MCR)

The core of our approach is the Multiple Constraint Ranking (MCR) method, integrated with the CMA-ES (Covariance Matrix Adaptation Evolution Strategy) optimizer. MCR addresses the scale problem by using the relative ranks of candidate solutions rather than raw values. Candidates are evaluated based on:

  1. Constraint Violation Count: The number of unsatisfied requirements.
  2. Relative Constraint Rank: How a candidate compares to others for each specific constraint.
  3. Objective Rank: The candidate's performance relative to the primary goal.

By utilizing ranks, the algorithm automatically normalizes different physical units (e.g., Volts, RPM, Meters), ensuring that no single requirement disproportionately influences the search process.

Experimental Results

The MCR method was evaluated using standard CPS benchmarks, including Automatic Transmission (AT), Fuel Control (AFC), and Wind Turbine (WT) models. These benchmarks represent high-dimensional, complex search spaces typical of industrial applications.

Experimental results comparing success rates (SR) and execution times between the baseline tool (Breach) and the proposed MCR method.

As shown in the results table, MCR significantly outperformed the baseline tool (Breach), particularly on difficult instances. For the AT1_2300 benchmark, Breach failed in all trials (0/20), while MCR achieved a 45% success rate. In the Wind Turbine (WT) benchmark, MCR achieved a 100% success rate and was significantly faster, reducing execution time from 327.9 seconds to 140.7 seconds. The method also demonstrated robustness to the choice of the primary objective; even the "worst-case" objective selection outperformed or matched the standard non-constrained approach.

Conclusion

The integration of Multiple Constraint Ranking into a constrained optimization framework provides a robust solution to the scale problem in CPS synthesis. By prioritizing relative performance over raw numerical values, MCR enables more effective navigation of complex, multi-scale requirement landscapes. Future work will explore automated objective selection and extending the framework to handle more complex logical structures.

Summary updated

BibTeX
@misc{sato2020constrained,
  author = {Sota Sato and Masaki Waga and Ichiro Hasuo},
  title = {{Constrained Optimization for Falsification and Conjunctive Synthesis}},
  year = {2020},
  eprint = {2012.00319},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.00319},
}
Figure