Cyber-Physical Systems (CPSs) typically involve a software component that controls a physical subsystem. Examples include medical devices, cars, planes, power grids, etc. For many of these systems, a failure can have catastrophic consequences. It is thus necessary to develop a methodology that guarantees safety for such CPSs.

It is usually difficult to guarantee safety of a CPS through design. On the other hand, verifying that a given CPS can not fail is in general not computationally tractable. Further, we often still want to use a CPS even if it can fail as long as the failure can be detected so that an appropriate corrective action can be taken. The approach that we investigated in this work is thus to monitor the system as it runs and raise an alarm when the safety violation is detected.

Monitoring the system for safety violations is challenging for several reasons. To start with, safe behavior is typically specified using variables that can not be directly observed. Instead, the monitor needs to rely on the observations of the system provided by the sensors to decide whether to raise an alarm. Further, the behavior of the system is typically probabilistic so the monitor needs to operate in the space of probabilities rather than directly in the space of variable values.

In our research, we first developed a framework for modeling probabilistic CPSs and for describing safety requirements (safety property). We next investigated under what conditions does a monitor exist given the system and the safety requirements. Namely, in some cases it is not possible to distinguish whether the system is operating correctly or not from sensor measurements. When a monitor exists, it is important that the rate of false alarms as well as the rate of missed alarms are minimized. We have identified different classes of systems (monitorable, strongly monitorable) based on what rates of missed alarms and false alarms are achievable for the system for a given safety property. We have also developed a methodology for designing so called threshold monitors that allow the user to tune a parameter (threshold) in order to make these rates as low as desired. In general, the lower the limit the longer the monitor needs to observe the system before it makes the decision whether to raise an alarm. For an important subset of CPSs we were able to derive an expression that relates this time to the rates of false alarms and missed alarms; the expression depends both on the system and on the safety property.

In order to reduce the time it takes the monitor to make a decision we also investigated monitors that use more complex decision rules (so called partially observable Markov decision processes - POMDPs). These monitors are computationally demanding so we also developed computationally efficient implementations that approximate the decision rules and can run in real time. Both these monitors and threshold monitors were successfully tested on a mobile robot that needs to avoid obstacles, demonstrating that the proposed methodology is suitable for applications.

In some cases, CPSs can be abstracted and described with models where variables only take values on a finite set. In this case, efficient (polynomial time) algorithms have been developed for checking whether a monitor for the system exist. Further, we have shown that monitoring can also done more efficiently than in the general case.

The results from this research have the potential to affect many areas such as health-care, automotive industry, transportation and energy. Primarily, these areas will benefit from the fact that the proposed monitors reduce the need for costly testing and verification while not sacrificing system safety. The developed methodology will also make the design and deployment of CPSs safer and decrease the cost of producing such systems.
In addition to research, this pr...

Please report errors in award information by writing to: awardsearch@nsf.gov.