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 271 records · Page 15

A Practical Approach to Implementing Real-Time Semantics

This paper investigates implementations of process algebras which are suitable for modeling concurrent real-time systems. It suggests an approach for efficiently implementing real-time semantics using dynamic priorities. For this purpose a proces algebra with dynamic priority is defined, whose semantics corresponds one-to-one to traditional real-time semantics. The advantage of the dynamic-priority approach is that it drastically reduces the state-space sizes of the systems in question while preserving all properties of their functional and real-time behavior. The utility of the technique is demonstrated by a case study which deals with the formal modeling and verification of the SCSI-2 bus-protocol. The case study is carried out in the Concurrency Workbench of North Carolina, an automated verification tool in which the process algebra with dynamic priority is implemented. It turns out that the state space of the bus-protocol model is about an order of magnitude smaller than the one resulting from real-time semantics. The accuracy of the model is proved by applying model checking for verifying several mandatory properties of the bus protocol.

Luettgen, Gerald↗

An Efficient Universal Trajectory Language

The Efficient Universal Trajectory Language (EUTL) is a language for specifying and representing trajectories for Air Traffic Management (ATM) concepts such as Trajectory-Based Operations (TBO). In these concepts, the communication of a trajectory between an aircraft and ground automation is fundamental. Historically, this trajectory exchange has not been done, leading to trajectory definitions that have been centered around particular application domains and, therefore, are not well suited for TBO applications. The EUTL trajectory language has been defined in the Prototype Verification System (PVS) formal specification language, which provides an operational semantics for the EUTL language. The hope is that EUTL will provide a foundation for mathematically verified algorithms that manipulate trajectories. Additionally, the EUTL language provides well-defined methods to unambiguously determine position and velocity information between the reported trajectory points. In this paper, we present the EUTL trajectory language in mathematical detail.

Hagen, George E.↗

Secure Image Hash Comparison for Warhead Verification

The effort to inspect and verify warheads in the context of possible future arms control treaties is rife with security and implementation issues. In this paper we review prior work on perceptual image hashing for template-based warhead verification. Furthermore, we formalize the notion of perceptual hashes and demonstrate that large classes of such functions are likely not cryptographically secure. We close with a brief discussion of fully homomorphic encryption as an alternative technique.

Bruillard, Paul J.↗

The specification-based validation of reliable multicast protocol: Problem Report

Reliable Multicast Protocol (RMP) is a communication protocol that provides an atomic, totally ordered, reliable multicast service on top of unreliable IP multicasting. In this report, we develop formal models for RMP using existing automated verification systems, and perform validation on the formal RMP specifications. The validation analysis help identifies some minor specification and design problems. We also use the formal models of RMP to generate a test suite for conformance testing of the implementation. Throughout the process of RMP development, we follow an iterative, interactive approach that emphasizes concurrent and parallel progress of implementation and verification processes. Through this approach, we incorporate formal techniques into our development process, promote a common understanding for the protocol, increase the reliability of our software, and maintain high fidelity between the specifications of RMP and its implementation.

Wu, Yunqing↗

The Specification-Based Validation of Reliable Multicast Protocol

Reliable Multicast Protocol (RMP) is a communication protocol that provides an atomic, totally ordered, reliable multicast service on top of unreliable IP multicasting. In this report, we develop formal models for RMP using existing automated verification systems, and perform validation on the formal RMP specifications. The validation analysis help identifies some minor specification and design problems. We also use the formal models of RMP to generate a test suite for conformance testing of the implementation. Throughout the process of RMP development, we follow an iterative, interactive approach that emphasizes concurrent and parallel progress of the implementation and verification processes. Through this approach, we incorporate formal techniques into our development process, promote a common understanding for the protocol, increase the reliability of our software, and maintain high fidelity between the specifications of RMP and its implementation.

Wu, Yunqing↗

Experiences applying Formal Approaches in the Development of Swarm-Based Space Exploration Systems

NASA is researching advanced technologies for future exploration missions using intelligent swarms of robotic vehicles. One of these missions is the Autonomous Nan0 Technology Swarm (ANTS) mission that will explore the asteroid belt using 1,000 cooperative autonomous spacecraft. The emergent properties of intelligent swarms make it a potentially powerful concept, but at the same time more difficult to design and ensure that the proper behaviors will emerge. NASA is investigating formal methods and techniques for verification of such missions. The advantage of using formal methods is the ability to mathematically verify the behavior of a swarm, emergent or otherwise. Using the ANTS mission as a case study, we have evaluated multiple formal methods to determine their effectiveness in modeling and ensuring desired swarm behavior. This paper discusses the results of this evaluation and proposes an integrated formal method for ensuring correct behavior of future NASA intelligent swarms.

Rouff, Christopher A.↗

Reactive system verification case study: Fault-tolerant transputer communication

A reactive program is one which engages in an ongoing interaction with its environment. A system which is controlled by an embedded reactive program is called a reactive system. Examples of reactive systems are aircraft flight management systems, bank automatic teller machine (ATM) networks, airline reservation systems, and computer operating systems. Reactive systems are often naturally modeled (for logical design purposes) as a composition of autonomous processes which progress concurrently and which communicate to share information and/or to coordinate activities. Formal (i.e., mathematical) frameworks for system verification are tools used to increase the users' confidence that a system design satisfies its specification. A framework for reactive system verification includes formal languages for system modeling and for behavior specification and decision procedures and/or proof-systems for verifying that the system model satisfies the system specifications. Using the Ostroff framework for reactive system verification, an approach to achieving fault-tolerant communication between transputers was shown to be effective. The key components of the design, the decoupler processes, may be viewed as discrete-event-controllers introduced to constrain system behavior such that system specifications are satisfied. The Ostroff framework was also effective. The expressiveness of the modeling language permitted construction of a faithful model of the transputer network. The relevant specifications were readily expressed in the specification language. The set of decision procedures provided was adequate to verify the specifications of interest. The need for improved support for system behavior visualization is emphasized.

Crane, D. Francis↗

Proceedings of the Second NASA Formal Methods Symposium

This publication contains the proceedings of the Second NASA Formal Methods Symposium sponsored by the National Aeronautics and Space Administration and held in Washington D.C. April 13-15, 2010. Topics covered include: Decision Engines for Software Analysis using Satisfiability Modulo Theories Solvers; Verification and Validation of Flight-Critical Systems; Formal Methods at Intel -- An Overview; Automatic Review of Abstract State Machines by Meta Property Verification; Hardware-independent Proofs of Numerical Programs; Slice-based Formal Specification Measures -- Mapping Coupling and Cohesion Measures to Formal Z; How Formal Methods Impels Discovery: A Short History of an Air Traffic Management Project; A Machine-Checked Proof of A State-Space Construction Algorithm; Automated Assume-Guarantee Reasoning for Omega-Regular Systems and Specifications; Modeling Regular Replacement for String Constraint Solving; Using Integer Clocks to Verify the Timing-Sync Sensor Network Protocol; Can Regulatory Bodies Expect Efficient Help from Formal Methods?; Synthesis of Greedy Algorithms Using Dominance Relations; A New Method for Incremental Testing of Finite State Machines; Verification of Faulty Message Passing Systems with Continuous State Space in PVS; Phase Two Feasibility Study for Software Safety Requirements Analysis Using Model Checking; A Prototype Embedding of Bluespec System Verilog in the PVS Theorem Prover; SimCheck: An Expressive Type System for Simulink; Coverage Metrics for Requirements-Based Testing: Evaluation of Effectiveness; Software Model Checking of ARINC-653 Flight Code with MCP; Evaluation of a Guideline by Formal Modelling of Cruise Control System in Event-B; Formal Verification of Large Software Systems; Symbolic Computation of Strongly Connected Components Using Saturation; Towards the Formal Verification of a Distributed Real-Time Automotive System; Slicing AADL Specifications for Model Checking; Model Checking with Edge-valued Decision Diagrams; and Data-flow based Model Analysis.

Munoz, Cesar↗

Simplifying Requirements Formalization for Resource-Constrained Mission-Critical Software

Developing critical software requires adherence to rigorous software development practices, such as formal requirement specification and verification. Despite their importance, such practices are often considered as complex and challenging tasks that require a strong formal methods background. In this paper, we present our work on simplifying the formal requirements specification experience for resource-constrained mission critical software through the use of structured natural language. To this end, we connect NASA’s FRET, a formal requirement elicitation and authoring tool with the Shelley model checking framework for MicroPython code. We report our experience on using these tools to specify requirements and analyze code from the NASA Ames PHALANX exploration concept.

PHALANX exploration concept↗

An Evaluation of Extended Reality Technologies for Use in Verification Testing at NASA 2024 HRP IWS Abstract

BACKGROUND At NASA, verification testing is the formal process of ensuring that a product conforms to requirements set by a project or program. Some verification methods, such as Demonstrations and Test, require either the end product or a mockup of the product with sufficient fidelity to stand-in for the product during the test. Traditionally, these mockups have been physical (e.g., foam-core and wood) but there is growing interest in exploring new methods for testing with these mockups. These methods include virtual reality (VR), mixed reality, and augmented reality which are collectively referred to as eXtended Reality (XR) technologies. VR has already been adopted and used by many in the aerospace industry as a tool for use in early design phases (e.g., developmental testing) and may have the most potential for use in verification tests. Benefits of using VR mockups offer cost effectiveness, ease of iteration, simulation of hazardous conditions (e.g., an egress through a hatch with smoke obscuring vision), and the ability to simulate microgravity conditions, which are challenging to do with physical mockups. However, the validity of test results obtained from VR mockup demonstrations or testing, compared to the current gold standard of physical mockups, remains uncertain. It is unlikely that there is one clean answer as there are many different types of verification outcomes and each XR technology must be evaluated on its own merits. This is not an issue during developmental testing as the design is still in flux and the total success of the design is not dependent upon the results of a developmental test. Verification tests, however, only happen once, assuming no change to the design, and the results are used to certify the product. Therefore, establishing the validity of XR mockup-based verification outcomes is essential before considering them for any use in verification tests. OBJECTIVE AND METHOD To address this concern, the Human Research Program has funded a project to explore and qualify how XR technologies might be used in verification demonstration and testing at NASA. Currently, we are conducting a review of the literature on the utilization of XR mockups for design activities, prototyping, and user testing. We are employing the Strengths, Weaknesses, Opportunities, and Threats (SWOT) analysis method to identify the pros, cons, and barriers to adoption of XR technologies for verification testing at NASA. Additionally, we are developing a framework to guide the deployment of XR mockups for verification tests. Building upon available evidence from the literature and subject-matter expert feedback, our goal for the framework is to provide guidelines for which forms of XR mockups are suitable for a given verification test, when only physical mockups should be employed and to highlight areas for which more evidence is needed. To further refine our framework and to contribute to the body of evidence, we are planning a lab-based experiment comparing a VR mockup to a physical twin for a set of select verification outcomes. ANTICIPATED RESULTS In this presentation, we will present the work we conducted to evaluate XR technologies for use in verification tests at NASA. We will summarize and report our findings from the SWOT analysis and our lab-based study, and we will present the current state of the XR Technologies for Verification Testing framework. We will conclude by summarizing remaining work and future directions for the project. Technologies for Verification Testing framework. We will conclude by summarizing remaining work and future directions for the project.

Extended Reality↗

Using Penelope to assess the correctness of NASA Ada software: A demonstration of formal methods as a counterpart to testing

Life-critical applications warrant a higher level of software reliability than has yet been achieved. Since it is not certain that traditional methods alone can provide the required ultra reliability, new methods should be examined as supplements or replacements. This paper describes a mathematical counterpart to the traditional process of empirical testing. ORA's Penelope verification system is demonstrated as a tool for evaluating the correctness of Ada software. Grady Booch's Ada calendar utility package, obtained through NASA, was specified in the Larch/Ada language. Formal verification in the Penelope environment established that many of the package's subprograms met their specifications. In other subprograms, failed attempts at verification revealed several errors that had escaped detection by testing.

Eichenlaub, Carl T.↗

Bridging the Gap Between Requirements and Model Analysis : Evaluation on Ten Cyber-Physical Challenge Problems

Formal verfication and simulation are powerful tools to validate requirements against complex systems. [Problem] Requirements are developed in early stages of the software lifecycle and are typically written in ambiguous natural language. There is a gap between such requirements and formal notations that can be used by verification tools, and lack of support for proper association of requirements with software artifacts for verification. [Principal idea] We propose to write requirements in an intuitive, structured natural language with formal semantics, and to support formalization and model/code verification as a smooth, well-integrated process. [Contribution] We have developed an end-to-end, open source requirements analysis framework that checks Simulink models against requirements written in structured natural language. Our framework is built in the Formal Requirements Elicitation Tool (fret); we use fret's requirements language named fretish, and formalization of fretish requirements in temporal logics. Our proposed framework contributes the following features: 1) automatic extraction of Simulink model information and association of fretish requirements with target model signals and components; 2) translation of temporal logic formulas into synchronous dataflow cocospec specifications as well as Simulink monitors, to be used by verification tools; we establish correctness of our translation through extensive automated testing; 3) interpretation of counterexamples produced by verification tools back at requirements level. These features support a tight integration and feedback loop between high level requirements and their analysis. We demonstrate our approach on a major case study: the Ten Lockheed Martin Cyber-Physical, aerospace-inspired challenge problems.

Mavridou, Anastasia↗

Open Building Control

Best practice control sequences are often not implemented correctly, or are not implemented at all, in large commercial buildings. This typically leads to 10-30 percent energy waste, along with reduced occupant productivity and unnecessary equipment wear. The current process of designing and implementing such control sequences is a manual process that starts with designers who often don’t have adequate training, then requires controls programmers to interpret and program a verbose written sequence. This process has been shown to fail to deliver high performance control sequences at scale. The Open Building Control project digitizes the current control delivery process. The project is developing tools for system designers to select control sequences, assess their energy performance and load flexibility potential using whole building simulation, specify the sequence for implementation using machine-to-machine translation by a control provider and formally testing the as-installed sequences by a commissioning agent. The project developed tools for each stage of this delivery process. The key innovation of the project is the development of the Control Description Language, a language that allows such a digitized control delivery process with end-to-end verification. Libraries of control sequences have been implemented using the Control Description Language, and their performance has been demonstrated using whole building energy simulation. An automated translation of such sequences to a commercial control product line has been conducted using a prototype translator. Tools for formal verification of as-installed control sequences relative to their specification have been developed and demonstrated. The American Society of Heating, Refrigerating and Air-Conditioning Engineers (ASHRAE) started the process of forming a committee to make this language an ASHRAE/ANSI Standard. This new standard will complement existing and emerging ASHRAE standards for building communication and semantic modeling by providing a standard for expressing the control logic - the actual brain of the building. We expect this language and the process it enables to be an important contribution to the deployment of high performance building control sequences at scale because it allows taming the complexity of the control delivery process, which is continually increasing due to the need for higher performance and increased load flexibility to meet goals for net zero energy and increased renewable integration.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

Verification and Validation Activities for the Multi-Fidelity Toolkit

The Multi-Fidelity Toolkit (MFTK) is a simulation tool being developed at Sandia National Laboratories for aerodynamic predictions of compressible flows over a range of physics fidelities and computational speeds. These models include the Reynolds-Averaged-Navier-Stokes (RANS) equations, the Euler equations, and modified Newtonian aerodynamics (MNA) equations, and they can be invoked independently or coupled with hierarchical Kriging to interpolate between high-fidelity simulations using lower-fidelity data. However, as with any new simulation capability, verification and validation are necessary to gather credibility evidence. This work describes formal code- and solution-verification activities as well as model validation with uncertainty considerations. Code verification is performed on the MNA model by comparing with an analytical solution for flat-plate and inclined-plate geometries. Solution-verification activities include grid-refinement studies of HIFiRE-1 wind tunnel measurements, which are used for validation, for all model fidelities. A thorough treatment of the validation comparison with prediction error and validation uncertainty is also presented.

42 ENGINEERING↗

Expanded verification and validation studies of hypersonic aerodynamics with multiple physics-fidelity models

Hypersonic aerothermodynamics is an important domain of modern multiphysics simulation. The Multi-Fidelity Toolkit is a simulation tool being developed at Sandia National Laboratories to predict aerodynamic properties for compressible flows from a range of physics fidelities and computational speeds. These models include the Reynolds-averaged Navier–Stokes (RANS) equations, the Euler equations with momentum-energy integral technique (MEIT), and modified Newtonian aerodynamics with flat-plate boundary layer (MNA+FPBL) equations, and they can be invoked independently or coupled with hierarchical Kriging to interpolate between high-fidelity simulations using lower-fidelity data. However, as with any new simulation capability, verification and validation are necessary to gather credibility evidence. This work describes formal code- and solution-verification activities, as well as model validation with uncertainty considerations. Code verification activities on the MNA+FPBL model build on previous work by focusing on the viscous portion of the model. Viscous quantities of interest are compared against those from an analytical solution for flat-plate, inclined-plate, and cone geometries. The code verification methodology for the MEIT model is also presented. Test setup and results of code verification tests on the laminar and turbulent models within MEIT are shown. Solution-verification activities include grid-refinement studies on simulations that model the HIFiRE-1 wind tunnel experiments. These experiments are used for validation of all model fidelities. A thorough validation comparison with prediction error and uncertainty is also presented. Three additional HIFiRE-1 experimental runs are simulated in this study, and the solution verification and validation work examines the effects of the associated parameter changes on model performance. Finally, a study is presented that compares the computational costs and fidelities from each of the different models.

42 ENGINEERING↗

The use of a formal simulator to verify a simple real time control program

The authors present an initial and elementary investigation of the formal specification and mechanical verification of programs that interact with environments. They describe a mechanical proof that a simple, real time control program keeps a vehicle on a straightline course in a variable crosswind. To formalize the specification they define a mathematical function which models the interaction of the program and its environment. They then state and proved two theorems about this function: the simulated vehicle never gets farther than three units away from the intended course, and it comes to the course if the wind ever remains steady for at least four sampling units.

Boyer, R. S.↗

A verified model of fault-tolerance

The main objectives are: a model of a replicated system with exact-match voting; a fault model that includes transients; a theorem that establishes the conditions under which the system provides fault tolerance; a formal specification of the model; and a mechanically checked verification of the theorem that is consonant with the journal-level presentation. Formal specification and verification revealed typos in the original report, exposed omission in original proof, led to the stronger theorem and more elegant proof, and confirmed that Enhanced Hierarchical Development Methodology (EHDM) has the capability to specify interesting and useful properties in a direct, natural, and readable manner.

Rushby, John↗

Third NASA Langley Formal Methods Workshop

This publication constitutes the proceedings of NASA Langley Research Center's third workshop on the application of formal methods to the design and verification of life-critical systems. This workshop brought together formal methods researchers, industry engineers, and academicians to discuss the potential of NASA-sponsored formal methods and to investigate new opportunities for applying these methods to industry problems. contained herein are copies of the material presented at the workshop, summaries of many of the presentations, a complete list of attendees, and a detailed summary of the Langley formal methods program. Much of this material is available electronically through the World-Wide Web via the following URL.

Holloway, C. Michael↗