The goal of this research is to develop fundamental theory, efficient algorithms, and realistic experiments for the analysis and design of safety-critical cyber-physical transportation systems with human operators. The research focuses on preventing crashes between automobiles at road intersections, since these account for about 40% of overall vehicle crashes. Specifically, the main objective of this work is to design provably safe driver-assist systems that understand driver?s intentions and provide warnings/overrides to prevent collisions. In order to pursue this goal, hybrid automata models for the driver-vehicles-intersection system, incorporating driver behavior and performance as an integral part, are derived from human-factors experiments. A partial order of these hybrid automata models is constructed, according to confidence levels on the model parameters. The driver-assist design problem is then formulated as a set of partially ordered hybrid differential games with imperfect information, in which games are ordered according to parameter confidence levels. The resulting designs are validated experimentally in a driving simulator and in large-scale computer simulations. This research leverages the potential of embedded control and communication technologies to prevent crashes at traffic intersections, by enabling networks of smart vehicles to cooperate with each other, with the surrounding infrastructure, and with their drivers to make transportation safer, more enjoyable, and more efficient. The work is based on a collaboration among researchers in formal methods, autonomous control, and human factors who are studying realistic and provably correct warning/override algorithms that can be readily transitioned to production vehicles.

The objective of this project is to research tools to manage uncertainty in the design and certification process of safety-critical aviation systems. The research focuses on three innovative ideas to support this objective. First, probabilistic techniques will be introduced to specify system-level requirements and bound the performance of dynamical components. These will reduce the design costs associated with complex aviation systems consisting of tightly integrated components produced by many independent engineering organizations. Second, a framework will be created for developing software components that use probabilistic execution to model and manage the risk of software failure. These techniques will make software more robust, lower the cost of validating code changes, and allow software quality to be integrated smoothly into overall system-level analysis. Third, techniques from Extreme Value Theory will be applied to develop adaptive verification and validation procedures. This will enable early introduction of new and advanced aviation systems. These systems will initially have restricted capabilities, but these restrictions will be gradually relaxed as justified by continual logging of data from in-service products. The three main research aims will lead to a significant reduction in the costs and time required for fielding new aviation systems. This will enable, for example, the safe and rapid implementation of next generation air traffic control systems that have the potential of tripling airspace capacity with no reduction in safety. The proposed methods are also applicable to other complex systems including smart power grids and automated highways. Integrated into the research is an education plan for developing a highly skilled workforce capable of designing safety critical systems. This plan centers around two main activities: (a) creation of undergraduate labs focusing on safety-critical systems, and (b) integration of safety-critical concepts into a national robotic snowplow competition. These activities will provide inspirational, real-world applications to motivate student learning.

The objective of this research is to prove that cyber-physical systems are safe before they are deployed. The approaches the research investigates are extensions of approaches used to test communications protocols. The problems with cyber-physical systems are that 1) they are much more complicated than communications protocols, 2) time is a more critical component of these systems, and 3) in a competitive environment there are likely to be many implementations that must interoperate. The complexity of communications protocols is reduced by using a layered architecture. Each layer provides a well defined service to the next layer. This research is developing multi-dimensional architectures that reflect the different ways that the cyber-physical system interacts with the physical world. The techniques are evaluated on a driver-assisted merge protocol. An architecture for the merge protocol has four dimensions organized as stacks for communications, external sensors, vehicle monitoring and control, and timing. This architecture will also be useful during standardization. Timing increases verification complexity by increasing the number of potential execution paths. The research conducted in this project explores how to reduce the number of paths by synchronizing clocks and using simultaneous operations. This approach is reasonable because of the timing accuracy now available with GPS. A two step verification process is used that creates an unambiguous model of the cyber-physical system, first proving that the model is safe, then checking that each implementation conforms to the model. This reduces the number and cost of tests for a three-party merge protocol. Specifically, assuming there are N implementation versions for different manufacturers and models, this approach reduces the number of necessary interaction tests, which would be cubic in N, to a single model verification and N conformance tests.

Implantable Cardiac Defibrillators (ICDs) are at the forefront of preventing sudden death in patients suffering from ventricular arrhythmias. ICDs have evolved into complex Cyber-Physical Systems (CPS)which tightly sensing, hardware, and software to diagnose arrythmias based on electrogram signals and control cardiac excitation. These devices are life-critical, yet the Verification and Validation (V&V) techniques used for establishing their safety have remained somewhat informal, and rely largely on extensive unit testing. There have been a number of exciting developments in formal verification technologies. This proposal introduces these techniques into the ICD verification process, and will demonstrate their suitability for application in other medical devices. The project will develop a model-based framework for ICDs, and will apply formal verification techniques, such as model checking and reachability analysis, to high-fidelity cardiac electrophysiological models that capture the electrical excitation induced by the ICD's control software. Through extensive collaboration with FDA research staff, the proposal will demonstrate the effectiveness of formal verification technology and suitability in medical device applications.

Trustworthy operation of next-generation complex power grid critical infrastructures requires mathematical and practical verification solutions to guarantee the correct infrastructural functionalities. This project develops the foundations of theoretical modeling, synthesis and real-world deployment of a formal and scalable controller code verifier for programmable logic controllers (PLCs) in cyber-physical settings. PLCs are widely used for control automation in industrial control systems. A PLC is typically connected to an engineering workstation where engineers develop the control logic to process the input values from sensors and issue control commands to actuators. The project focuses on protecting infrastructures against malicious control injection attacks on PLCs, such as Stuxnet, that inject malicious code on the device to drive the underlying physical platform to an unsafe state. The broader impact of this proposal is highly significant. It offers potential for real-time security for critical infrastructure systems covering sectors such as energy and manufacturing. The project's intellectual merit is in providing a mathematical and practical verification framework for cyber-physical systems through integration of offline formal methods, online monitoring solutions, and power systems analysis. Offline formal methods do not scale for large-scale platforms due to their exhaustive safety analysis of all possible system states, while online monitoring often reports findings too late for preventative action. This project takes a hybrid approach that dynamically predicts the possible next security incidents and reports to operators before an unsafe state is encountered, allowing time for response. The broader impact of this project is in providing practical mathematical analysis capabilities for general cyber-physical safety-critical infrastructure with potential direct impact on our national security. The research outcomes are integrated into education modules for graduate, undergraduate, and K-12 classrooms.