# US 2016/0253437 A1 · Verified Runtime Validation of Verified Cyber-Physical System Models

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2016/0253437 A1
- Document ID: US20160253437A1
- Status: Published application
- Kind: A1
- Application number: 15/026,690
- Filed: 2014-10-10
- Published: 2016-09-01
- Earliest claimed: 2013-10-11
- Assignees: Carnegie Mellon University
- Applicants: Carnegie Mellon University
- Inventors: André Platzer; Stefan Mitsch
- Web page: https://patentgrep.com/patent/US20160253437A1

## CPC

- G06F 30/3323: using formal methods, e.g. equivalence checking or property checking
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for ensuring that verification results about models apply to cyber-physical systems (CPS) implementations is presented. The invention provides correctness guarantees for CPS executions at runtime. Offline verification of CPS models are combined with runtime validation of system executions for compliance with the model. The invention ensures that the verification results obtained for the model apply to the actual system runs by monitoring the behavior of the world for compliance with the model, assuming the system dynamics deviation is bounded. If, at some point, the observed behavior no longer complies with the model, such that offline verification results no longer apply, provably safe fallback actions are initiated. The invention includes a systematic technique to synthesize provably correct monitors automatically from CPS proofs in differential dynamic logic.

## Claims

### Claim 1

A process of synthesizing a monitor for a cyber-physical system (CPS) from a proven hybrid model, comprising the steps of:
a. deriving a monitor specification from said hybrid model;
b. transforming said model and said monitor specification into a set of monitor conditions; and
c. generating code implementing said set of monitor conditions to create said monitor.

### Claim 2 (depends on 1)

The process of claim 1 wherein said CPS includes a controller running control software, said controller reading sensors and controlling actuators, and wherein said hybrid model models both the actions of said controller and the resulting changes in state of said CPS.

### Claim 3 (depends on 2)

The process of claim 2 further comprising the step of executing said monitor in conjunction with said control software, to guarantee compliance of said CPS with said proven hybrid model.

### Claim 4 (depends on 2)

The process of claim 2 wherein said step of transforming said model and monitor specification into a set of monitor conditions further comprises applying a theorem prover to said model and said monitor specification.

### Claim 5 (depends on 2)

The process of claim 2 wherein said step of deriving a set of monitor conditions further comprises analyzing said monitor specification and applying proof rules to remove any differential equations to produce said set of monitor conditions containing only first-order logic.

### Claim 6 (depends on 2)

The process of claim 2 where said monitor consists of a model monitor, a controller monitor and a prediction monitor.

### Claim 7 (depends on 6)

The process of claim 6 wherein said model monitor compares a current state of said CPS with a previous state of said CPS and determines if the difference between said current state and said previous state is in compliance with said proven hybrid model.

### Claim 8 (depends on 6)

The process of claim 6 wherein said controller monitor monitors said controller to check compliance with said proven hybrid model.

### Claim 9 (depends on 6)

The process of claim 6 wherein said prediction monitor allows deviations of said cyber-physical system from said hybrid model to account for real-world imperfections.

### Claim 10 (depends on 7)

The process of claim 7 wherein said model monitor, said controller monitor an said prediction monitor read said sensors to determine the current state of said CPS.

### Claim 11 (depends on 10)

The process of claim 10 wherein said model monitor runs prior to said control software and determines if physical behavior which occurred between said previous state of said CPS and said current state of said CPS is in compliance with said proven hybrid model.

### Claim 12 (depends on 11)

The process of claim 11 wherein said model monitor will raise an error if the difference between said current state and said previous state is not in compliance with said proven hybrid model.

### Claim 13 (depends on 8)

The process of claim 8 wherein said controller monitor runs after said controller software and determines if physical actions to be taken by said controller will result in a said CPS being in compliance with said proven hybrid model.

### Claim 14 (depends on 13)

The process of claim 13 wherein said controller monitor will raise an error if said physical actions to be taken by said controller will result in a said CPS not being in compliance with said proven hybrid model.

### Claim 15 (depends on 9)

The process of claim 9 wherein said prediction monitor runs after said control software and determines if physical actions to be taken by said controller will result in a said CPS being in compliance with said proven hybrid model in the presence of bounded deviations between said CPS and said proven hybrid model.

### Claim 16 (depends on 15)

The process of claim 15 wherein said prediction monitor will raise an error if said physical actions to be taken by said controller will result in a said CPS not being in compliance with said proven hybrid model.

### Claim 17 (depends on 1)

The process of claim 1 wherein said proven hybrid model is expressed in differential dynamic logic.

### Claim 18 (depends on 17)

The process of claim 17 wherein said proven hybrid model comprises a set of formulas of the form:
Φ→[α*]ψ with invariant ψ→[α]ψ s.t Φ→φ and φ→ψ (1)

### Claim 19 (depends on 1)

The process of claim 1 wherein said monitor specification comprises a set of specification conjectures for model monitors of the form:
ø|constant→αYVm+.

### Claim 20 (depends on 1)

The process of claim 1 wherein said monitor specification comprises a set of specification conjectures for controller monitors of the form:
ø|const→αctrlYVc+.

### Claim 21 (depends on 1)

The process of claim 1 wherein said monitor specification comprises a set of specification conjectures for prediction monitors of the form:
ø|constφ)→αctrl(YVp+[αδplant]φ).

### Claim 22 (depends on 1)

The process of claim 1 wherein said steps are automated if said proven hybrid model is of the form (αctrl;αplant) without nested loops, with solvable differential equations in αplant and a disturbed plant αδplant with constant additive disturbance δ.

### Claim 23 (depends on 11)

The process of claim 11 wherein compliance with said model monitor guarantees that the properties of said proven hybrid model are present in said CPS before said controller software is executed.

### Claim 24 (depends on 13)

The process of claim 13 wherein said compliance with said controller monitor guarantees that the properties of said proven hybrid model are present in said CPS after said controller software was executed.

### Claim 25 (depends on 15)

The process of claim 15 wherein compliance with said prediction monitor guarantees that the properties of said proven hybrid model will still be present in future states of said CPS.

### Claim 26 (depends on 1)

The process of claim 1 wherein said steps of said process are automated in accordance with an algorithm.
