Search NASA⌕ Search

SEARCH · Search NASA

Results for “Formal Methods”

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 181 records · Page 10

The MINERVA Software Development Process

This paper presents a software development process for safety-critical software components of cyber-physical systems. The process is called MINERVA, which stands for Mirrored Implementation Numerically Evaluated against Rigorously Verified Algorithms. The process relies on formal methods for rigorously validating code against its requirements. The software development process uses: (1) a formal specification language for describing the algorithms and their functional requirements, (2) an interactive theorem prover for formally verifying the correctness of the algorithms, (3) test cases that stress the code, and (4) numerical evaluation on these test cases of both the algorithm specifications and their implementations in code. The MINERVA process is illustrated in this paper with an application to geo-containment algorithms for unmanned aircraft systems. These algorithms ensure that the position of an aircraft never leaves a predetermined polygon region and provide recovery maneuvers when the region is inadvertently exited.

Narkawicz, Anthony↗

Three-color resonance ionization spectroscopy of Zr in Si

As our society becomes technologically more complex, computers are being used in greater and greater numbers of high consequence systems. Giving a machine control over the lives of humans can be disturbing, especially if the software that is run on such a machine has bugs. Formal reasoning is one of the most powerful techniques available to demonstrate the correctness of a piece of software. When reasoning about software and its development, one frequently encounters expressions that contain partial functions. As might be expected, the presence of partial functions introduces an additional dimension of difficulty to the reasoning framework. This difficulty produces an especially strong impact in the case of high consequence systems. An ability to use formal methods for constructing software is essential if we want to obtain greater confidence in such systems through formal reasoning. This is only reasonable under automation of software development and verification. However, the ubiquitous presence of partial functions prevents a uniform application to software of any tools not specifically accounting for partial functions. In this paper we will describe a framework for reasoning about software, based on the nonstrict explicit domain approach, that is applicable to a large class of software/hardware systems. In this framework the Hoare triples containing partial functions can be reasoned about automatically in a well-defined and uniform manner.

Hansen, C. S.↗

Formal Analysis of Extended Well-Clear Boundaries for Unmanned Aircraft

This paper concerns the application of formal methods to the definition of a detect and avoid concept for unmanned aircraft systems (UAS). In particular, it illustrates how formal analysis was used to explain and correct unexpected behaviors of the logic that issues alerts when two aircraft are predicted not to be well clear from one another. As a result of this analysis, a recommendation was proposed to, and subsequently adopted by, the US standards organization that defines the minimum operational requirements for the UAS detect and avoid concept.

Munoz, Cesar↗

KLOKKOS: Automated test generation for performance-portable programs

SAND2024-13830O The KLOKKOS project provides a suite of test generation and validation tools to increase maintainability and portability of Kokkos programs. KLOKKOS, a portmanteau of Klee and Kokkos, is developing an automated test generation for performance-portable programs using Clang/low-level virtual machine (LLVM) and formal methods. KLOKKOS is based on several topics in computer science: the development of symbolic and concolic analysis of LLVM and C++ codes, formal semantics and type theory, C++ templates and language features, LLVM compiler infrastructure, and data parallel primitives. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525

SciDAC↗

Fault tolerant system performance modeling

With the proliferation of complex digital systems on aircraft, the need to accurately predict system performance early in the system design cycle becomes imperative. In the past, system designers have relied on ad hoc methods for evaluating performance issues. This has produced systems that have not always worked as originally intended. To alleviate these design deficiencies, formal methods, with supporting tools, must be adhered to during the system design process. The use of performance modeling tools is becoming widely accepted as a way to address timing considerations of system design. An additional incentive for the use of these tools is that they allow the system architect to analyze system component interactions (i.e., bus contention, contention of functions for a processing site, and system repair activity on application performance). This inherent flexibility can result in an explicit specification of the system architecture. This paper addresses a method that supports performance modeling of fault tolerant systems using a discrete event simulation tool. An additional focus is on lessons learned from analyzing these classes of problems. The methodology and supporting work provide system architects with the capability to specify candidate architectures and accurately predict their performance in the early stages of design, where changes to system design is most cost effective. The work has been supported under NASA contract NAS1-18099. Integrated Airframe Propulsion Control System Architecture (IAPSA II). This contract addresses methodology, analysis, and detailed design of integrated control system architectures suitable for high-performance aircraft of the 1990's.

Discrete event simulation↗

Using formal specification in the Guidance and Control Software (GCS) experiment. Formal design and verification technology for life critical systems

The goal of this task was to investigate how formal methods could be incorporated into a software engineering process for flight-control systems under DO-178B and to demonstrate that process by developing a formal specification for NASA's Guidance and Controls Software (GCS) Experiment. GCS is software to control the descent of a spacecraft onto a planet's surface. The GCS example is simplified from a real example spacecraft, but exhibits the characteristics of realistic spacecraft control software. The formal specification is written in Larch.

Weber, Doug↗

On the Formalization of Development and Assessment Process for Digital Twins in the Nearly Autonomous Management and Control System

In recent years, the autonomous control system has been encouraged in advanced reactors for restoring economic viability, simplifying the operation and maintenance, and enabling remote-site power generations [1]. Since the reactor is expected to be operated for a long period of time with a limited number of individuals onsite, it is recommended that the autonomous control system should have access to very realistic models of the state of processes in the whole lifecycle, together with these process behaviors in interaction with their environment in the real world. As a result, digital twin (DT) technology is suggested in autonomous control systems. DT is defined as a digital representation of a physical object or system, which contains a record for the histories of loads, operation and maintenance status, predictions for the near-term transient of important state variables, and decision-making process [2]. Since machine learning (ML) can recognize patterns within a complex system in real-time applications, it has been used to build DTs in the autonomous control systems for advanced reactors. Meanwhile, due to the rareness of operation data in accident scenarios, the development and assessment of DTs is expected to be mainly driven by simulations. Although the capability and feasibility of ML-based DTs are recognized in improving the safety and efficiency of reactor control, a major concern from the regulatory commission and the nuclear industry is whether the information from a DT is developed and assessed in accordance with expectation and requirements by the target decision. Such concerns not only affect the acceptance criteria for DTs, but also values that can be extracted from DTs and autonomous control system during operations. Inspired by the success of formal methods in improving the reliability and robustness of computer programming and software development, it is suggested that the development and assessment process (DAP) for both separate DTs and integral control system should be formalized in a transparent, consistent, and improvable manner. In this study, a digital-twin development and assessment process (DT-DAP) is proposed by adapting the evaluation model development and assessment process (EMDAP) [3] to requirements by the autonomous control system, ML algorithms, and DT technology. To demonstrate the framework, a baseline nearly autonomous management and control (NAMAC) system with ML-based DTs for diagnosis and prognosis is developed and assessed based on the framework. It is found that with selected testing methods and techniques, the DT-DAP can help identify errors in DTs and NAMAC which would otherwise be left unverified. Meanwhile, it is found that the DT-DAP can improve the DTs and NAMAC by continuously learning and iterating through different elements.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

Structural design using equilibrium programming

Multiple nonlinear programming methods are combined in the method of equilibrium programming. Equilibrium programming theory has been appied to problems in operations research, and in the present study it is investigated as a framework to solve structural design problems. Several existing formal methods for structural optimization are shown to actually be equilibrium programming methods. Additionally, the equilibrium programming framework is utilized to develop a new structural design method. Selected computational results are presented to demonstrate the methods.

Scotti, Stephen J.↗

High level design proof of a reliable computing platform

The main objectives are: to establish hardware/software platform for ultra-reliable computing; to use fault tolerant computer architecture; to use formal methods to prevent design and implementation errors; and to construct reliability model to quantify reliability estimate. The results show that: ultra-reliable control systems are hard to achieve; simple fault tolerant design is postulated; formal specification of design is constructed; and preliminary correctness proofs are obtained.

Divito, Ben L.↗

Formalisms for user interface specification and design

The application of formal methods to the specification and design of human-computer interfaces is described. A broad outline of human-computer interface problems, a description of the field of cognitive engineering and two relevant research results, the appropriateness of formal specification techniques, and potential NASA application areas are described.

Auernheimer, Brent J.↗

Runtime Verification: From Propositional to First-Order Temporal Logic

Runtime Verification is a branch of formal methods concerned with analysis of execution traces for the purpose of determining the state or general quality of the executing system. The field covers numerous approaches, one of which is specification-based runtime verification, where execution traces are checked against formal specifications. The paper presents syntax, semantics, and monitoring algorithms for respectively propositional and first-order temporal logics. In propositional logics the observed events in the execution trace are represented using atomic propositions, while first-order logic allows universal and existential quantification over data occurring as arguments in events. Monitoring of the first-order case is drastically more challenging than the propositional case, and we present a solution for this problem based on BDDs. We furthermore discuss monitorability of temporal properties by dividing them into different classes representing different degrees of monitorability.

Peled, Doron↗

Multinode Multi-GPU Two-Electron Integrals: Code Generation Using the Regent Language

The computation of two-electron repulsion integrals (ERIs) is often the most expensive step of integral-direct self-consistent field methods. Formally it scales as O(N 4 ), where N is the number of Gaussian basis functions used to represent the molecular wave function. In practice, this scaling can be reduced to O(N 2 ) or less by neglecting small integrals with screening methods. The contributions of the ERIs to the Fock matrix are of Coulomb (J) and exchange (K) type and require separate algorithms to compute matrix elements efficiently. We previously implemented highly efficient GPU-accelerated J-matrix and K-matrix algorithms in the electronic structure code TeraChem. Although these implementations supported the use of multiple GPUs on a node, they did not support the use of multiple nodes. This presents a key bottleneck to cutting-edge ab initio simulations of large systems, e.g., excited state dynamics of photoactive proteins. We present our implementation of multinode multi-GPU J- and K-matrix algorithms in TeraChem using the Regent programming language. Regent directly supports distributed computation in a task-based model and can generate code for a variety of architectures, including NVIDIA GPUs. We demonstrate multinode scaling up to 45 GPUs (3 nodes) and benchmark against hand-coded TeraChem integral code. Finally, we also outline our metaprogrammed Regent implementation, which enables flexible code generation for integrals of different angular momenta.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

The multi-assumption architecture and testbed (MAAT v1.0): R code for generating ensembles with dynamic model structure and analysis of epistemic uncertainty from multiple sources

Abstract. Here, computer models are ubiquitous tools used to represent systems across many scientific and engineering domains. For any given system, many computer models exist, each built on different assumptions and demonstrating variability in the ways in which these systems can be represented. This variability is known as epistemic uncertainty, i.e. uncertainty in our knowledge of how these systems operate. Two primary sources of epistemic uncertainty are (1) uncertain parameter values and (2) uncertain mathematical representations of the processes that comprise the system. Many formal methods exist to analyse parameter-based epistemic uncertainty, while process-representation-based epistemic uncertainty is often analysed post hoc, incompletely, informally, or is ignored. In this model description paper we present the multi-assumption architecture and testbed (MAAT v1.0) designed to formally and completely analyse process-representation-based epistemic uncertainty. MAAT is a modular modelling code that can simply and efficiently vary model structure (process representation), allowing for the generation and running of large model ensembles that vary in process representation, parameters, parameter values, and environmental conditions during a single execution of the code. MAAT v1.0 approaches epistemic uncertainty through sensitivity analysis, assigning variability in model output to processes (process representation and parameters) or to individual parameters. In this model description paper we describe MAAT and, by using a simple groundwater model example, verify that the sensitivity analysis algorithms have been correctly implemented. The main system model currently coded in MAAT is a unified, leaf-scale enzyme kinetic model of C 3 photosynthesis. In the Appendix we describe the photosynthesis model and the unification of multiple representations of photosynthetic processes. The numerical solution to leaf-scale photosynthesis is verified and examples of process variability in temperature response functions are provided. For rapid application to new systems, the MAAT algorithms for efficient variation of model structure and sensitivity analysis are agnostic of the specific system model employed. Therefore MAAT provides a tool for the development of novel or toy models in many domains, i.e. not only photosynthesis, facilitating rapid informal and formal comparison of alternative modelling approaches.

54 ENVIRONMENTAL SCIENCES↗

Autonomous Ocean World Exploration: Advancement of a Virtual Testbed

The search for life (extinct or extant) and potentially habitable bodies in our solar system and beyond is one of the 12 priority science questions outlined in the National Acadamies’ 2022 decadal survey [5]. Extraterrestrial destinations containing liquid water present an opportunity to search for life as we know it, and in recent years an increasing number of such locations have been discovered within our solar system. Several Jovian moons—Europa, Ganymede, and Callisto [10]—and the Saturnian moons Enceladus [8] and Titan [9] are known or suspected to harbor massive subsurface oceans. Of these "ocean worlds", Europa is the focus of at least one planned NASA orbiter mission, Europa Clipper [4], and an early lander mission concept, the Europa Lander [2, 3]. Whereas most robotic missions to the Moon and Mars (e.g. orbiters, rovers, landers) to date have had ground controllers on Earth tightly involved in mission operations, missions to more distant worlds will require a high degree of onboard autonomy due to long communication lags and blackouts, harsh environments (radiation, cold), and more limited battery and hardware life. The past decade has seen great advances in both AI technologies and computing scalability and performance that offer promising solutions for spacecraft autonomy and motivate the software system and research programs described in this paper. The Ocean Worlds Autonomy Testbed for Exploration, Research, and Simulation (OceanWATERS) [1], which has been in development at the NASA Ames Research Center since 2018, is a virtual environment for testing lander autonomy solutions. It is built on the Robot Operating System (ROS), runs on consumer-grade Linux workstations, and was released as open source in 2020. OceanWATERS provides a physical and visual simulation of a prototypical lander in a Europa-like environment (Figure 1). The lander was modeled after requirements and specifications made in JPL’s Europa Lander Study of 2016 [3]. Simulated lander systems include stereo cameras and spotlights mounted on an antenna mast that pans and tilts, a 6 degrees of freedom (DoF) robotic arm with a force-torque sensor and two interchangeable end effectors, and a battery pack power system. The environment consists of multiple terrain models including a highly detailed model sourced from the FROST dataset [11], simulation of surrounding planetary bodies based on an ephemeris model, and lighting from the sun with associated surface illumination, reflectance, and shadows. Operations supported by OceanWATERS include panoramic and directed imaging of the environment and lander workspace, Cartesian and joint-level arm commanding, grinding of the terrain surface (e.g. digging a trench), and scooping of ground material (Figure 2) which can be discarded or collected as science samples in a receptacle that can be emptied (science operations themselves are not simulated). These operations are realized as ROS Actions and are complimented by a wide selection of telemetry that is continually produced by each lander subsystem. The power system model is driven by the open-source Generic Software Architecture for Prognostics (GSAP) [11] that predicts the battery’s remaining useful life and other characteristics. As a testbed for high-level autonomy, OceanWATERS provides an execution framework based on PLEXIL [12], an open-source plan specification language and execution engine developed largely at Ames. NASA's initial development of OceanWATERS, as well the Ocean Worlds Lander Autonomy Testbed (OWLAT) [6], a complimentary physical testbed developed at JPL, was the first step in a plan for realizing candidate onboard autonomy solutions for such planetary landers. In 2020 NASA solicited applications for its Autonomous Robotics Research for Ocean Worlds (ARROW) program, and in 2021 the similar Concepts for Ocean worlds Life Detection Technology (COLDTech) program. Collectively six research teams, based in universities and companies across the United States, were awarded grants to develop and demonstrate autonomy solutions on OceanWATERS and OWLAT. These 1–2-year projects have now finished or are nearing completion, and a wide variety of autonomy challenges in ocean world surface missions were addressed. Prototyped and demonstrated solutions have included autonomous discovery, response and adaptation to system faults and unexpected environmental events, world model synthesis through perception, plan synthesis using learned models, methods to optimize sample target selection and prioritize science data transmission, extension of PLEXIL for stochastic decision-making, and an integration of a model of JPL’s mission-ready COLDArm [7]. Technologies used in these projects include many forms of machine learning, causal reasoning, automated planning, Markov decision processes, formal methods, and other advanced techniques. A more detailed summary of the ARROW and COLDTech projects is given herein. OceanWATERS has had significant enhancements since its open-source release in 2020. Many of its new features were driven or shaped by feedback from the ARROW and COLDTech teams and requirements of their projects. In support of enabling autonomous adaptation to spacecraft faults (a specific capability solicited by both programs), a fault injection and detection framework was developed that supports a wide and growing range of fault types such as locked joints, image loss, and battery failures. The power system model was completed and integrated into the simulator, starting as a single-cell battery model and later upgraded to a multi-cell model with associated faults such as cell disconnection. Arm/terrain interaction was improved by adding a force-torque sensor and associated faults, and an analytic dig force model based on the Balovnev bucket force equations. Environment fidelity was increased by modeling terrain deformation resulting from digging and scooping; visual improvements were made in textures, lighting, and shadows. To facilitate interoperation with OWLAT, a unified command and telemetry interface between the testbeds was developed at the ROS level, along with a PLEXIL interface. The number of lander operations was greatly expanded (e.g. with Cartesian-based arm and antenna movement), and a framework was designed for users to build their own lander actions. A GUI for PLEXIL plan selection was created (Figure 3), and an expansive set of plans were added, such as those that illustrate patterns for fault handling. This paper provides a self-contained high-level description of OceanWATERS, focusing on more detailed coverage of the aforementioned enhancements. It provides a high-level summary of the projects undertaken by participants in the ARROW and COLDTech programs and how these efforts have helped shape OceanWATERS. Finally, potential future work and directions for the testbed are listed, as likely informed by the recent planetary science decadal survey [5].

K Michael Dalal↗

Assuring Intelligent Systems: Contingency Management for UAS

Unmanned aircraft systems (UAS) collaborate with humans to operate in diverse, safety-critical applications. However, assurance technologies need to be integrated into the design process in order to guarantee safe behavior, thereby enabling UAS operations in the National Airspace System (NAS). In this paper, formal methods are integrated with learning-enabled systems representations. The generation and representation of knowledge are captured via monadic second-order logic rules in the cognitive architecture Soar. These rules are translated into timed automata, and a proof of correctness for the translation is provided so that safety and liveness properties can be checked in the formal verification environment Uppaal. This approach is agnostic to the learning mechanism used to generate the learned rules (e.g., chunking, etc.). An example of a fault-tolerant, learning-enabled UAS deciding which of four contingency procedures to execute under a lost link scenario while overflying an urban area is used to illustrate the approach.

Intelligent Systems↗

Towards Automated Reasoning Chains for Verification of LLM-Generated Scientific Code

With the rise of Large Language Model (LLM) generated code, including in domains like scientific computing, ensuring not only syntactical, but also mathematical correctness, has become a critical task. Traditional formal methods approaches often struggle with the ambiguity of floating-point code, and full symbolic execution is extremely costly and limited. We propose a chain-of-reasoning approach that iteratively lifts basic semantics from code into the SPIRAL system and then establishes numerical equivalency to the desired mathematical operation. Here, we leverage the ample mathematical knowledge already formalized in SPIRAL to enable the system to recognize not just different implementations of the same algorithm but fully separate approaches to solving the given problem. The chain establishes tight error bounds on the output of given code with respect to the true continuous solution it approximates, quantifying all sources of error. We demonstrate this approach by establishing the correctness of a pseudospectral solver for a simple 1-dimensional Poisson problem.

Oschatz, Quentin [Carnegie Mellon University,Pitts↗

Evaluation of a Guideline by Formal Modelling of Cruise Control System in Event-B

Recently a set of guidelines, or cookbook, has been developed for modelling and refinement of control problems in Event-B. The Event-B formal method is used for system-level modelling by defining states of a system and events which act on these states. It also supports refinement of models. This cookbook is intended to systematize the process of modelling and refining a control problem system by distinguishing environment, controller and command phenomena. Our main objective in this paper is to investigate and evaluate the usefulness and effectiveness of this cookbook by following it throughout the formal modelling of cruise control system found in cars. The outcomes are identifying the benefits of the cookbook and also giving guidance to its future users.

Yeganefard, Sanaz↗

A Provably Correct Floating-Point Implementation of Well Clear Avionics Concepts

The NASA DAIDALUS library provides formal definitions for Detect-and-Avoid avionics concepts such as when an aircraft is well-clear with respect to the surrounding air traffic, i.e., it does not operate in such proximity to create a collision hazard. While several properties are proven correct for DAIDALUS assuming ideal real number arithmetic, an actual implementation that uses floating-point numbers may behave unexpectedly because of round-off errors and run-time exceptions. This paper presents an experience report on the application of a formal methods toolchain to extract and verify floating-point C code from a real-valued specification of the well-clear module of DAIDALUS. This toolchain comprises the PVS theorem prover, the PRECiSA floating-point analyzer and code generator, and the Frama-C analysis suite. The generated code is automatically instrumented to detect when the control flow of the floating-point program may diverge from the ideal real number specification, and it is annotated with contracts that state the maximum accumulated round-off error. The absence of overflows is also formally verified for the generated code. In order to apply the toolchain to an industrial case study such as DAIDALUS, a formally verified pre-processing of the input specification is performed, which includes a program slicing and several semantic-preserving simplifications.

Program verification↗