Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Formal Verification”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 487 records · Page 27

Generating Code Review Documentation for Auto-Generated Mission-Critical Software

Model-based design and automated code generation are increasingly used at NASA to produce actual flight code, particularly in the Guidance, Navigation, and Control domain. However, since code generators are typically not qualified, there is no guarantee that their output is correct, and consequently auto-generated code still needs to be fully tested and certified. We have thus developed AUTOCERT, a generator-independent plug-in that supports the certification of auto-generated code. AUTOCERT takes a set of mission safety requirements, and formally verifies that the autogenerated code satisfies these requirements. It generates a natural language report that explains why and how the code complies with the specified requirements. The report is hyper-linked to both the program and the verification conditions and thus provides a high-level structured argument containing tracing information for use in code reviews.

Denney, Ewen↗

Verification and validation of a reliable multicast protocol

This paper describes the methods used to specify and implement a complex communications protocol that provides reliable delivery of data in multicast-capable, packet-switching telecommunication networks. The protocol, called the Reliable Multicasting Protocol (RMP), was developed incrementally by two complementary teams using a combination of formal and informal techniques in an attempt to ensure the correctness of the protocol implementation. The first team, called the Design team, initially specified protocol requirements using a variant of SCR requirements tables and implemented a prototype solution. The second team, called the V&V team, developed a state model based on the requirements tables and derived test cases from these tables to exercise the implementation. In a series of iterative steps, the Design team added new functionality to the implementation while the V&V team kept the state model in fidelity with the implementation through testing. Test cases derived from state transition paths in the formal model formed the dialogue between teams during development and served as the vehicles for keeping the model and implementation in fidelity with each other. This paper describes our experiences in developing our process model, details of our approach, and some example problems found during the development of RMP.

Callahan, John R.↗

Probability of Loss of Assured Safety in Systems with Multiple Time-Dependent Failure Modes: Incorporation of Delayed Link Failure in the Presence of Aleatory Uncertainty

Probability of loss of assured safety (PLOAS) is modeled for weak link (WL)/strong link (SL) systems in which one or more WLs or SLs could potentially degrade into a precursor condition to link failure that will be followed by an actual link failure after some amount of elapsed time. The descriptor loss of assured safety (LOAS) is used because failure of the WL system places the entire system in an inoperable configuration while failure of the SL system before failure of the WL system, although undesirable, does not necessarily result in an unintended operation of the entire system. Thus, safety is “assured” by failure of the WL system before failure of the SL system. Here, the following topics are considered: (i) Definition of precursor occurrence time cumulative distribution functions (CDFs) for individual WLs and SLs, (ii) Formal representation, approximation and illustration of PLOAS with (a) constant delay times, (b) aleatory uncertainty in delay times, and (c) delay times defined by functions of link properties at occurrence times for link failure precursors, and (iii) Procedures for the verification of PLOAS calculations for the three indicated definitions of delayed link failure.

58 GEOSCIENCES↗

DMTN-107: Options for Alert Production in LSST Operations Year 1

This document reviews five options for alert production in LSST Operations Year 1 (LOY1), taking into account any implications on LSST formal requirements including up-scopes, down-scopes or explicit violations. The Data Management System Science Team's preferred option for maximizing LSST science is to generate template images from as much of the data from the commissioning and/or science verification phases as possible and use them to run Difference Image Analysis and alert production during LOY1. A proposal to increase the sky area covered during commissioning via a "filler" scheduler program is also presented. As a potential moderate up-scope, this study presents an option to build interim templates on a $\sim$monthly basis during LOY1, which could increase the accessible sky area by ~1000-2000 deg**2 per month, and should be reconsidered closer to the start of Operations.

79 ASTRONOMY AND ASTROPHYSICS↗

Software Safety Analysis of a Flight Guidance System

This document summarizes the safety analysis performed on a Flight Guidance System (FGS) requirements model. In particular, the safety properties desired of the FGS model are identified and the presence of the safety properties in the model is formally verified. Chapter 1 provides an introduction to the entire project, while Chapter 2 gives a brief overview of the problem domain, the nature of accidents, model based development, and the four-variable model. Chapter 3 outlines the approach. Chapter 4 presents the results of the traditional safety analysis techniques and illustrates how the hazardous conditions associated with the system trace into specific safety properties. Chapter 5 presents the results of the formal methods analysis technique model checking that was used to verify the presence of the safety properties in the requirements model. Finally, Chapter 6 summarizes the main conclusions of the study, first and foremost that model checking is a very effective verification technique to use on discrete models with reasonable state spaces. Additional supporting details are provided in the appendices.

Butler, Ricky W.↗

Portable Wireless LAN Device and Two-Way Radio Threat Assessment for Aircraft VHF Communication Radio Band

This document summarizes the safety analysis performed on a Flight Guidance System (FGS) requirements model. In particular, the safety properties desired of the FGS model are identified and the presence of the safety properties in the model is formally verified. Chapter 1 provides an introduction to the entire project, while Chapter 2 gives a brief overview of the problem domain, the nature of accidents, model based development, and the four-variable model. Chapter 3 outlines the approach. Chapter 4 presents the results of the traditional safety analysis techniques and illustrates how the hazardous conditions associated with the system trace into specific safety properties. Chapter 5 presents the results of the formal methods analysis technique model checking that was used to verify the presence of the safety properties in the requirements model. Finally, Chapter 6 summarizes the main conclusions of the study, first and foremost that model checking is a very effective verification technique to use on discrete models with reasonable state spaces. Additional supporting details are provided in the appendices.

Nguyen, Truong X.↗

Recommendations on Evidence and Process for Certification of Learning-enabled Components in Aerospace Systems

This report primarily identifies a collection of relevant and necessary evidence for assurance of machine learnt components (MLCs)—also known as learning-enabled components—integrated into aircraft systems, and gives preliminary suggestions on the elements of a certification process that invoke the identified evidence. The main focus is on feedforward neural networks that are static and trained offline through supervised learning. A brief background on the generic elements of the lifecycle of an MLC is given to contextualize the assurance considerations and, consequently, the evidence that is relevant and necessary to support certification. At the level of an MLC, those considerations relate to: (i) the consistency and correctness of MLC contributions to system functions in the context of a validated functional intent; and (ii) the absence of MLC contributions to aircraft-level failure conditions. At an ML model level, confidence in model and data properties contribute to assurance of the containing MLC, in particular: (a) generalizability and robustness of models, in the presence of inputs not previously seen during training, disturbances to inputs, and unexpected inputs; and (b) valid data, i.e., data that are at least representative, relevant, complete, and accurate. Evidence for the above span the elements of the ML lifecycle, and includes, at a minimum, lifecycle artifacts that pertain to: (1) properties of requirements capturing functional intent, safety constraints, and aspects of the intended use and operating environment; (2) model performance, model complexity and design, and algorithm choice; (3) achievement of required performance at the levels of a trained model during model development, a trained model after model development is complete, and a trained model that is transformed into an executable equivalent; (4) model implementation aspects necessary for transforming a trained model into the executable equivalent; (5) integration of the executable trained model into the containing MLC, and eventually the larger system; and, (6) lastly, the verification and validation (V&V) of each of the above. Such V&V lifecycle artifacts themselves include: aspects of coverage, e.g., of various levels of requirements by the input space of the model and the data; traceability (where applicable); application of formal methods for property specification, analysis, and checking. Examples of evidence generation methods and tools further ground the discussion on what constitutes evidence, and the contribution to assurance during certification. The identified assurance considerations and supporting evidence is not a comprehensive set. Additionally, neither what should be considered as sufficient evidence relative to the assigned criticality of an MLC, nor how criticality ought to be determined and adjusted, have been considered in this report. However, suggestions are made for potential activities of the ML lifecycle that are aimed at providing confidence that an MLC can be relied upon when integrated into its containing (aircraft) system. Those activities are proposed as candidate elements of a certification process for MLCs. The main purpose of this report to inform regulatory guidance and consensus standards that may be used to meet the safety intent of the applicable regulations.

Aviation safety↗

The role of criteria in design and management of space systems

Explicit requirements and standards arising in connection with space systems management serve as a framework for technical management and furnish legally binding control of development, verification, and operations. As a project develops, additional requirements are derived which are unique to the system in question; these are designated 'derived requirements'. The reliability and cost-effectiveness of a space system are best ensured where a balance has arisen between formal (legally binding) and informal. Attention is presently given to the development of criteria consistent with total quality management.

Blair, J. C.↗

Improving Automated Strategies for Univariate Quantifier Elimination

This report discusses improved support for univariate quantifier elimination in the Prototype Verification System (PVS). Previously, PVS had three strategies for quantifier elimination—hutch, tarski, and sturm. Of these, only hutch is able to decide queries in any input format—sturm only works on queries regarding a single polynomial on an interval and tarski resolves queries in the universal existential fragment. This paper describes an extended version of tarski. The extension is accomplished by formally verifying a disjunctive normal form transformation in PVS and using tarski on each conjunctive clause. Additionally, a preprocessing step is added to the decision procedure underlying tarski. This preprocessing is designed to exploit properties of polynomial structure to quickly resolve queries that have certain formats. The preprocessing produces dramatic speedup when it succeeds in resolving a query, and seems to introduce negligible overhead when it does not resolve a query. Finally, testing reveals some ways to improve the hutch and tarski strategies.

Polynomial Constraints↗

Design verification of SIFT

A SIFT reliable aircraft control computer system, designed to meet the ultrahigh reliability required for safety critical flight control applications by use of processor replications and voting, was constructed for SRI, and delivered to NASA Langley for evaluation in the AIRLAB. To increase confidence in the reliability projections for SIFT, produced by a Markov reliability model, SRI constructed a formal specification, defining the meaning of reliability in the context of flight control. A further series of specifications defined, in increasing detail, the design of SIFT down to pre- and post-conditions on Pascal code procedures. Mechanically checked mathematical proofs were constructed to demonstrate that the more detailed design specifications for SIFT do indeed imply the formal reliability requirement. An additional specification defined some of the assumptions made about SIFT by the Markov model, and further proofs were constructed to show that these assumptions, as expressed by that specification, did indeed follow from the more detailed design specifications for SIFT. This report provides an outline of the methodology used for this hierarchical specification and proof, and describes the various specifications and proofs performed.

Moser, Louise↗

STP: A Mechanized Logic for Specification and Verification

A logic and proof theory that was mechanized and successfully applied to prove nontrivial properties of a fully distributed fault tolerant system is described. The system is close to achieving the critical balance in man machine interaction necesary for successful application by users other than the system developers. Motivation for the form of man machine interaction embodied by STP is discussed. A formal description of the logic and the proof theory is contained, and the description illustrated with an example. The use of STP in a large scale effort to prove nontrivial properties on SIFT, a distributed Software Implemented Fault Tolerant operating system for aircraft flight control is discussed. Finally, directions for further work are described.

Shostak, R. E.↗

Reflecting on Planning Models: A Challenge for Verification and Validation of Planning Systems

We discuss the opportunities for autonomous sys- tems to perform reflection on their planners by adapting the models used to build plans. We first describe model-based planning systems, a form of automated planning system driven by declarative models of the planning domain. These models include descriptions of the conditions and effects of actions on the state of the world. When planning the activities of cyber-physical systems, the command and data representation of the system must be formally abstracted to the actions and states described in the planning system model. When the execution of a plan either fails or produces unexpected outcomes, the execution trace can be abstracted and compared to the predicted state according to the planning model, producing a list of discrepancies; these discrepancies can then be used to fix the model. This provides part of a reflection capability, namely, a set of well-formed problems with the domain model, the abstractions, or both. The challenge lies in the rest of the reflection capability, namely, a set of techniques for changing the models or the abstractions. We discuss these challenges and describe some of the options for addressing them

Mission Planning↗

Probability of Loss of Assured Safety in Systems with Multiple Time-Dependent Failure Modes: Incorporation of Delayed Link Failure in the Presence of Aleatory Uncertainty.

Probability of loss of assured safety (PLOAS) is modeled for weak link (WL)/strong link (SL) systems in which one or more WLs or SLs could potentially degrade into a precursor condition to link failure that will be followed by an actual failure after some amount of elapsed time. The following topics are considered: (i) Definition of precursor occurrence time cumulative distribution functions (CDFs) for individual WLs and SLs, (ii) Formal representation of PLOAS with constant delay times, (iii) Approximation and illustration of PLOAS with constant delay times, (iv) Formal representation of PLOAS with aleatory uncertainty in delay times, (v) Approximation and illustration of PLOAS with aleatory uncertainty in delay times, (vi) Formal representation of PLOAS with delay times defined by functions of link properties at occurrence times for failure precursors, (vii) Approximation and illustration of PLOAS with delay times defined by functions of link properties at occurrence times for failure precursors, and (viii) Procedures for the verification of PLOAS calculations for the three indicated definitions of delayed link failure.

97 MATHEMATICS AND COMPUTING↗

The Homogeneous Cooling State as a Verification Test for Kinetic Theory-Based Continuum Models of Gas–Solid Flows

Granular and multiphase (gas–solids) kinetic theory-based models have emerged a leading modeling strategy for the simulation of particle flows. Similar to the Navier–Stokes equations of single-phase flow, although substantially more complex, kinetic theory-based continuum models are typically solved with computational fluid dynamic (CFD) codes. Under the assumptions of the so-called homogeneous cooling state (HCS), the governing equations simplify to an analytical solution describing the “cooling” of fluctuating particle velocity, or granular temperature. The HCS is used here to verify the implementation of a recent multiphase kinetic theory-based model in the open source mfix code. In this work, results from the partial verification test show that the available implicit (backward) Euler time integration scheme converges to the analytical solution with the expected first-order rate. A second-order accurate backward differentiation formula (BDF) is also implemented and observed to converge at a rate consistent with its formal accuracy.

Computational fluid dynamics↗

Understanding and Verifying Neural Networks

Deep Neural Networks (DNNs) have gained immense popularity in recent times and have widespread use in applications such as image classification, sentiment analysis, speech recognition and also in safety-critical applications such as autonomous driving. However, they suffer limitations such as lack of explainability and robustness which raise safety and security concerns in their usage. Further, the complex structure and large input spaces of DNNs act as an impediment to thorough verification and testing. The SafeDNN project at the Robust Software Engineering (RSE) group at NASA aims at exploring techniques to ensure that systems that use deep neural networks are safe, robust and interpretable. In this talk, I will be presenting our technique Prophecy that automatically infers formal properties of deep neural network models. The tool extracts patterns based on neuron activations as preconditions that imply certain desirable output properties of the model. I would be highlighting case studies that use Prophecy in obtaining explanations for network decisions, understanding correct and incorrect behavior, providing formal guarantees wrt safety and robustness, and debugging neural network models. We have applied the tool on image classification networks, neural network controllers providing turn advisories in unmanned aircrafts, regression models used for autonomous center-line tracking in aircrafts and neural network object detectors

Deep Neural Networks↗

Secure System Composition and Type Checking using Cryptographic Proofs [Slides]

We can use formal methods to verify that systems compose correctly without the possibility of incorrect behavior. This means exhaustively checking that System A’s postconditions agree with System B’s preconditions. If so, it is safe to compose. Normal Setting: Every computational path must be accounted for and checked. Verification cost (time) is multiplicative across systems.

97 MATHEMATICS AND COMPUTING↗

Formal Methods for Automated Diagnosis of Autosub 6000

This is a progress report on applying formal methods in the context of building an automated diagnosis and recovery system for Autosub 6000, an Autonomous Underwater Vehicle (AUV). The diagnosis task involves building abstract models of the control system of the AUV. The diagnosis engine is based on Livingstone 2, a model-based diagnoser originally built for aerospace applications. Large parts of the diagnosis model can be built without concrete knowledge about each mission, but actual mission scripts and configuration parameters that carry important information for diagnosis are changed for every mission. Thus we use formal methods for generating the mission control part of the diagnosis model automatically from the mission script and perform a number of invariant checks to validate the configuration. After the diagnosis model is augmented with the generated mission control component model, it needs to be validated using verification techniques.

Ernits, Juhan↗

Documentation, User Support, and Verification of Wind Turbine and Plant Models (Final Report)

As part of the Utility Wind Energy Integration Group (UWIG) and EnerNex's Wind Turbine Modeling Project, EnerNex has received ARRA (federal stimulus) funding through the Department of Energy (DOE) to further the progress of wind turbine and wind plant models. Despite the large existing and planned wind generation deployment, industry-standard models for wind generation have not been formally adopted. Models commonly provided for interconnection studies are not adequate for use in general transmission planning studies, where public, non-proprietary, documented and validated models are needed. NERC MOD (North American Electric Reliability Corporation) reliability standards require that power flow and dynamics models be provided, in accordance with regional requirements and procedures. The goal of this project is to accelerate the appropriate use of generic wind turbine models for transmission network analysis by: (1) Defining proposed enhancements to the generic wind turbine model structures that would allow representation of more advanced; (2) Comparative testing of the generic models against more detailed (and sometimes proprietary) versions developed by turbine vendors; (3) Developing recommended parameters for the generic models to best mimic the performance of specific commercial wind turbines; (4) Documenting results of the comparative simulations in an application guide for users; (5) Conducting technology transfer activities in regional workshops for dissemination of knowledge and information gained, and to engage electric power and wind industry personnel in the project while underway; (6) Designing of a "living" homepage to establish an online resource for transmission planners.

17 WIND ENERGY↗