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.

This project focuses on the formal design of semi-autonomous automotive Cyber Physical Systems (CPS). Rather than disconnecting the driver from the vehicle, the goal is to obtain a vehicle where the degree of autonomy is continuously changed in real-time as a function of certified uncertainty ranges for driver behavior and environment reconstruction. The highly integrated research plan will advance the science and engineering for CPS by developing methods for (1) reconstructing 3D scenes which incorporate high-level topological and low-level metric information, (2) extracting driver behavioral models from large datasets using geometry, reasoning and inferences, (3) designing provably-safe control schemes which trade-off real-time feasibility and conservatism by using the evidence collected during actual driving. Assisting humans in controlling complex and safety-critical systems is a global challenge. In order to improve the safety of human-operated CPS we need to provide guarantees in the reconstruction of the environment where the humans and the CPS operate, and to develop control systems that use predictive cognitive models of the human when interacting with the CPS. A successful and integrated research in both areas will impact not only the automotive sector but many other human-operated systems. These include telesurgery, homeland security, assisted rehabilitation, power networks, environmental monitoring, and all transportation CPS. Graduate, undergraduate and underrepresented engineering students will benefit through classroom instruction, involvement in the research and a continuous interaction with industrial partners who are leaders in the field of assisted driving.

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.

The project investigates a formal verification framework for artificial pancreas (AP) controllers that automate the delivery of insulin to patients with type-1 diabetes (T1D). AP controllers are safety critical: excessive insulin delivery can lead to serious, potentially fatal, consequences. The verification framework under development allows designers of AP controllers to check that their control algorithms will operate safely and reliably against large disturbances that include patient meals, physical activities, and sensor anomalies including noise, delays, and sensor attenuation. The intellectual merits of the project lie in the development of state-of-the-art formal verification tools, that reason over mathematical models of the closed-loop including external disturbances and insulin-glucose response. These tools perform an exhaustive exploration of the closed loop system behaviors, generating potentially adverse situations for the control algorithm under verification. In addition, automatic techniques are being investigated to help AP designers improve the control algorithm by tuning controller parameters to eliminate harmful behaviors and optimize performance. The broader significance and importance of the project are to minimize the manual testing effort for AP controllers, integrate formal tools in the certification process, and ultimately ensure the availability of safe and reliable devices to patients with type-1 diabetes. The framework is made available to researchers who are developing AP controllers to help them verify and iteratively improve their designs. The team is integrating the research into the educational mission by designing hands-on courses to train undergraduate students in the science of Cyber-Physical Systems (CPS) using the design of AP controllers as a motivating example. Furthermore, educational material that explains the basic ideas, current challenges and promises of the AP concept is being made available to a wide audience that includes patients with T1D, their families, interested students, and researchers. The research is being carried out collaboratively by teams of experts in formal verification for Cyber-Physical Systems, control system experts with experience designing AP controllers, mathematical modeling experts, and clinical experts who have clinically evaluated AP controllers. To enable the construction of the verification framework from the current state-of-the-art verification tools, the project is addressing major research challenges, including (a) building plausible mathematical models of disturbances from available clinical datasets characterizing human meals, activity patterns, and continuous glucose sensor anomalies. The resulting models are integrated in a formal verification framework; (b) simplifying existing models of insulin glucose response using smaller but more complex delay differential models; (c) automating the process of abstracting the controller implementation for the purposes of verification; (d) producing verification results that can be interpreted by control engineers and clinical researchers without necessarily understanding formal verification techniques; and (e) partially automating the process of design improvements to potentially eliminate severe faults and improve performance. The framework is evaluated on a set of promising AP controller designs that are currently under various stages of clinical evaluation.

This project develops a theoretical framework as well as software tools to support testing and verification of a Cyber-Physical System (CPS) within a Model-Based Design (MBD) process. The theoretical bases of the framework are stochastic optimization methods, and robustness notions of formal specification languages. The project's research comprises three components: development of conditions on the algorithms and on the structure of the CPS for inferring finite-time guarantees on the randomized testing process; the study of testing methods that can support modular and compositional system design; and investigation of appropriate notions of conformance between two system models and between a model and its implementation on a computational platform. All of these components are needed to support testing and verification in all the stages of an MBD process as well as to support component reuse, incremental system improvements and modular design. The evaluation of the framework is driven by the problems of verifying automotive control systems and medical devices. As safety-critical CPS become ubiquitous, the need for design methods that guarantee correct system functionality and performance becomes more urgent. Certification and government agencies need dependable testing and verification tools to incorporate in certification standards and procedures. The concrete benefits to the society are both in terms of reduced catastrophic design errors in new products and in terms of reduced economic costs for new product development. The former increases the confidence in new technologies while the latter improves the competitiveness of the companies that utilize such technologies. The theoretical results of this project are being incorporated into software tools for testing, verification and validation of complex CPS. The evaluation focus of the project on verifying infusion pumps and automotive control software ultimately helps in avoiding harmful losses due to errors in these safety-critical systems. The use of any software tool that is based on formal or semi-formal methods requires engineers with solid training on these technologies. This proposal puts forward an education curriculum for developing new courses that introduce formal and semi-formal methods for CPS at all levels of higher education, i.e., undergraduate, graduate and continuing education. Particular attention is devoted into on-line continuing education of practicing engineers who must acquire new MBD skills.

This project aims to achieve key technology, infrastructure, and regulatory science advances for next generation medical systems based on the concept of medical application platforms (MAPs). A MAP is a safety/security-critical real-time computing platform for: (a) integrating heterogeneous devices and medical IT systems, (b) hosting application programs ("apps") that provide medical utility through the ability to both acquire information and update/control integrated devices, IT systems, and displays. The project will develop formal architectural and behavioral specification languages for defining MAPs, with a focus on techniques that enable compositional reasoning about MAP component interoperability and safety. These formal languages will include an extensible property language to enable the specification of real-time, quality-of-service, and attributes specific to medical contexts that can be leveraged by code generation, testing, and verification tools. The project will work closely with a synergistic team of clinicians, device industry partners, regulators, and medical device interoperability and safety standard organizations to develop an open source MAP innovation platform to enable key stakeholders within the nation's health care ecosphere to identify, prototype, and evaluate solutions to key technology and regulatory challenges that must be overcome to develop a commodity market of regulated MAP components. Because MAPs provide pre-built certified infrastructure and building blocks for rapidly developing multi-device medical applications, this research has the potential to usher in a new paradigm of medical system that significantly increases the pace of innovation, lowers development costs, enables new functionality by aggregating multiple devices into a system of systems, and achieves greater system safety.