Search NASA⌕ Search

SEARCH · Search NASA

Results for “Formal analysis”

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 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRSDate not supplied

Formal Analysis of the Compact Position Reporting Algorithm

This presentation documents the formal analysis of the compact position reporting (CPR) algorithm. CPR is a fundamental part of Automatic Dependent Surveillance - Broadcast (ADS-B), which is a global protocol for aircraft communication. The formal analysis found and corrected issues with the algorithm, proposed simplifications, and created a formally verified reference implementation, all of which are incorporated in the governing standards document.

Formal Methods↗
NASA NTRS2014

State Event Models for the Formal Analysis of Human-Machine Interactions

The work described in this paper was motivated by our experience with applying a framework for formal analysis of human-machine interactions (HMI) to a realistic model of an autopilot. The framework is built around a formally defined conformance relation called "fullcontrol" between an actual system and the mental model according to which the system is operated. Systems are well-designed if they can be described by relatively simple, full-control, mental models for their human operators. For this reason, our framework supports automated generation of minimal full-control mental models for HMI systems, where both the system and the mental models are described as labelled transition systems (LTS). The autopilot that we analysed has been developed in the NASA Ames HMI prototyping tool ADEPT. In this paper, we describe how we extended the models that our HMI analysis framework handles to allow adequate representation of ADEPT models. We then provide a property-preserving reduction from these extended models to LTSs, to enable application of our LTS-based formal analysis algorithms. Finally, we briefly discuss the analyses we were able to perform on the autopilot model with our extended framework.

State-event Models↗
NASA NTRS2016

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↗
NASA NTRS2012

An Ontology for State Analysis: Formalizing the Mapping to SysML

State Analysis is a methodology developed over the last decade for architecting, designing and documenting complex control systems. Although it was originally conceived for designing robotic spacecraft, recent applications include the design of control systems for large ground-based telescopes. The European Southern Observatory (ESO) began a project to design the European Extremely Large Telescope (E-ELT), which will require coordinated control of over a thousand articulated mirror segments. The designers are using State Analysis as a methodology and the Systems Modeling Language (SysML) as a modeling and documentation language in this task. To effectively apply the State Analysis methodology in this context it became necessary to provide ontological definitions of the concepts and relations in State Analysis and greater flexibility through a mapping of State Analysis into a practical extension of SysML. The ontology provides the formal basis for verifying compliance with State Analysis semantics including architectural constraints. The SysML extension provides the practical basis for applying the State Analysis methodology with SysML tools. This paper will discuss the method used to develop these formalisms (the ontology), the formalisms themselves, the mapping to SysML and approach to using these formalisms to specify a control system and enforce architectural constraints in a SysML model.

Wagner, David A.↗
NASA NTRS2001

Fast Formal Analysis of Requirements via "Topoi Diagrams"

Early testing of requirements can decrease the cost of removing errors in software projects. However, unless done carefully, that testing process can significantly add to the cost of requirements analysis. We show here that requirements expressed as topoi diagrams can be built and tested cheaply using our SP2 algorithm, the formal temporal properties of a large class of topoi can be proven very quickly, in time nearly linear in the number of nodes and edges in the diagram. There are two limitations to our approach. Firstly, topoi diagrams cannot express certain complex concepts such as iteration and sub-routine calls. Hence, our approach is more useful for requirements engineering than for traditional model checking domains. Secondly, out approach is better for exploring the temporal occurrence of properties than the temporal ordering of properties. Within these restrictions, we can express a useful range of concepts currently seen in requirements engineering, and a wide range of interesting temporal properties.

Menzies, Tim↗
NASA NTRS2000

Formal Analysis of the Remote Agent Before and After Flight

This paper describes two separate efforts that used the SPIN model checker to verify deep space autonomy flight software. The first effort occurred at the beginning of a spiral development process and found five concurrency errors early in the design cycle that the developers acknowledge would not have been found through testing. This effort required a substantial manual modeling effort involving both abstraction and translation from the prototype LISP code to the PROMELA language used by SPIN. This experience and others led to research to address the gap between formal method tools and the development cycle used by software developers. The Java PathFinder tool which directly translates from Java to PROMELA was developed as part of this research, as well as automatic abstraction tools. In 1999 the flight software flew on a space mission, and a deadlock occurred in a sibling subsystem to the one which was the focus of the first verification effort. A second quick-response "cleanroom" verification effort found the concurrency error in a short amount of time. The error was isomorphic to one of the concurrency errors found during the first verification effort. The paper demonstrates that formal methods tools can find concurrency errors that indeed lead to loss of spacecraft functions, even for the complex software required for autonomy. Second, it describes progress in automatic translation and abstraction that eventually will enable formal methods tools to be inserted directly into the aerospace software development cycle.

Havelund, Klaus↗
NASA NTRS1990

Improving system reliability through formal analysis and use of checks in software

Software is playing increasingly important roles in avionics systems. It is widely used in navigation and, in some cases, in control loops that maintain aircraft stability. To guarantee the safety of flight systems, the FAA requires that critical components have a probability of failure no greater than 10(exp -9) per hour of flight. Software is being used to diagnose system components for failure. SIFT (Software Implemented Fault Tolerance) was a computer system developed to study the use of software to check for failure and manage processor reconfiguration. To guarantee that software satisfies its specifications, formal verification can be used. With this a program and its specification are viewed as mathematical objects, and a mathematical proof is used to show that the program and its specification are equivalent. In previous research, a theory of checking was developed to offer assistance in analyzing specifications and designing run-time checks. In the theory, checking is considered abstractly in terms of n-ary relations much like those of relational database theory. Within the theory check are categorized, checks on input and checks on results are considered, and formal attention is given to the minimization and logical combination of checks. The focus is upon input checks and the obstacles in checking input to critical systems. A central concern is with a property referred to as independence. The concern is with circumstances under which it is possible to apply isolated, independent checks to separate sensor inputs and be assure that all illegal input will be properly detected. Presently, independence is being investigated and checked in the context of the GCS (Guidance and Control System). The GCS simulator is intended for testing software that implements control laws for landing spacecraft. The large number of inputs and their complex interrelationships provide an exciting context in which to investigate independence and the difficulties of supplying input checks.

Staknis, Mark E.↗
NASA NTRS1998

Formal Analysis of Human Automation Interaction: The Problem of Display Correctness

This presentation attempted to develop a quantitative method for evaluating the effectiveness of autoflight displays. Researchers sought to develop a methodology for evaluation of display correctness and develop a methodology for display synthesis. Topics covered included: mode awareness, industry/research contributions, human-machine interface analysis, research objectives, modeling, flight guidance project and evaluation.

Degani, Asaf↗
NASA NTRS2012

Integrated Formal Analysis of Timed-Triggered Ethernet

We present new results related to the verification of the Timed-Triggered Ethernet (TTE) clock synchronization protocol. This work extends previous verification of TTE based on model checking. We identify a suboptimal design choice in a compression function used in clock synchronization, and propose an improvement. We compare the original design and the improved definition using the SAL model checker.

Dutertre, Bruno↗
NASA NTRSDate not supplied

Capturing and Analyzing Requirements with FRET

FRET is an open source tool, developed at NASA Ames, for writing, understanding, formalizing, and analyzing requirements. In practice, requirements are typically written in natural language, which is ambiguous and consequently not amenable to formal analysis. Since formal, mathematical notations are unintuitive, requirements in FRET are entered in a restricted, natural language, called FRETish with precise unambiguous meaning. FRET helps users write FRETish requirements both by providing grammar information and examples during editing, but also through English and diagrammatic explanations to clarify subtle semantic issues. For each requirement, FRET automatically produces formalizations and supports interactive simulation of produced formalizations to ensure that they capture user intentions. Through its analysis portal, FRET connects to analysis tools by exporting verification code. Currently FRET connects to (1) the CoCoSim automated analysis tool for the verification of Simulink and Stateflow models, and (2) the Copilot runtime monitoring tool for the analysis of C programs. FRET also supports the consistency/realizability analysis of requirements for identifying conflicting requirements. In this tutorial, we introduce FRET and learn to speak and analyze FRETish through several examples.

FRET↗
NASA NTRSDate not supplied

FRET Tutorial

In this tutorial, we present the FRET tool for writing, understanding, formalizing and analyzing requirements. In practice, requirements are typically written in natural language, which is ambiguous and consequently not amenable to formal analysis. Since formal, mathematical notations are unintuitive, requirements in FRET are entered in a restricted, natural language, called FRETish with precise unambiguous meaning. This tutorial explains how requirements can be captured in FRETish and subsequently formalized in temporal logics and in the synchronous data flow language Lustre. We show, through multiple examples, how FRET assists users in understanding FRETish requirements and clarifying subtle semantic issues through English and diagrammatic explanations as well as interactive simulation. FInally, this tutorial describes how FRET can be used to perform realizability checking for identifying conflicting requirements and the connection of FRET with (1) the CoCoSim automated analysis tool for the verification of Simulink and Stateflow models, and (2) the Copilot runtime monitoring tool for the analysis of C programs.

FRET↗
NASA NTRS2013

Validation and Verification of LADEE Models and Software

The Lunar Atmosphere Dust Environment Explorer (LADEE) mission will orbit the moon in order to measure the density, composition and time variability of the lunar dust environment. The ground-side and onboard flight software for the mission is being developed using a Model-Based Software methodology. In this technique, models of the spacecraft and flight software are developed in a graphical dynamics modeling package. Flight Software requirements are prototyped and refined using the simulated models. After the model is shown to work as desired in this simulation framework, C-code software is automatically generated from the models. The generated software is then tested in real time Processor-in-the-Loop and Hardware-in-the-Loop test beds. Travelling Road Show test beds were used for early integration tests with payloads and other subsystems. Traditional techniques for verifying computational sciences models are used to characterize the spacecraft simulation. A lightweight set of formal methods analysis, static analysis, formal inspection and code coverage analyses are utilized to further reduce defects in the onboard flight software artifacts. These techniques are applied early and often in the development process, iteratively increasing the capabilities of the software and the fidelity of the vehicle models and test beds.

Gundy-Burlet, Karen↗
NASA NTRS2021

MBSE Validation and Verification: Case Study for LADEE

The Lunar Atmosphere Dust Environment Explorer (LADEE) mission orbited the moon in order to measure the density, composition, and time variability of the lunar dust environment. The successful mission launched September 7, 2013 and was de-orbited and impacted the moon's surface on April 17, 2014. The ground-side and onboard flight software for the mission was developed using a “Model-Based Software Engineering” (MBSE) methodology combined with strong reuse of Government and Commercial Off-The Shelf (G/COTS) components. Models of the spacecraft and flight software were developed in a graphical dynamics modeling package. Flight Software requirements were prototyped and refined using the simulated models. After the model was shown to work as desired in the simulation framework, C-code software was automatically generated from the models. The auto-generated software was then tested in real-time Processor-in-the-Loop and Hardware-in-the-Loop test beds. “Traveling Road Show” test beds were used for early integration tests with payloads and other subsystems. Traditional techniques for verifying computational sciences models were used to characterize the spacecraft simulation. A lightweight set of formal methods analysis, static analysis, formal inspection, and code coverage analyses were utilized to further reduce defects in the onboard flight software artifacts. These techniques were applied early and often in the development process, iteratively increasing the capabilities of software and fidelity of vehicle models and test beds.

Model-Based Software Engineering, Validation and V↗
NASA NTRS2008

NASA Langley's Formal Methods Research in Support of the Next Generation Air Transportation System

This talk will provide a brief introduction to the formal methods developed at NASA Langley and the National Institute for Aerospace (NIA) for air traffic management applications. NASA Langley's formal methods research supports the Interagency Joint Planning and Development Office (JPDO) effort to define and develop the 2025 Next Generation Air Transportation System (NGATS). The JPDO was created by the passage of the Vision 100 Century of Aviation Reauthorization Act in Dec 2003. The NGATS vision calls for a major transformation of the nation s air transportation system that will enable growth to 3 times the traffic of the current system. The transformation will require an unprecedented level of safety-critical automation used in complex procedural operations based on 4-dimensional (4D) trajectories that enable dynamic reconfiguration of airspace scalable to geographic and temporal demand. The goal of our formal methods research is to provide verification methods that can be used to insure the safety of the NGATS system. Our work has focused on the safety assessment of concepts of operation and fundamental algorithms for conflict detection and resolution (CD&R) and self- spacing in the terminal area. Formal analysis of a concept of operations is a novel area of application of formal methods. Here one must establish that a system concept involving aircraft, pilots, and ground resources is safe. The formal analysis of algorithms is a more traditional endeavor. However, the formal analysis of ATM algorithms involves reasoning about the interaction of algorithmic logic and aircraft trajectories defined over an airspace. These trajectories are described using 2D and 3D vectors and are often constrained by trigonometric relations. Thus, in many cases it has been necessary to unload the full power of an advanced theorem prover. The verification challenge is to establish that the safety-critical algorithms produce valid solutions that are guaranteed to maintain separation under all possible scenarios. Current research has assumed perfect knowledge of the location of other aircraft in the vicinity so absolute guarantees are possible, but increasingly we are relaxing the assumptions to allow incomplete, inaccurate, and/or faulty information from communication sources.

Butler, Ricky W.↗
NASA NTRS2020

Bridging the Gap Between Requirements and Simulink Model Analysis

Formal verification and simulation are powerful tools for the verification of requirements against complex systems. Requirements are developed in early stages of the software lifecycle and are typically expressed in natural language. There is a gap between such requirements and their software implementations.We present a framework that bridges this gap by supporting a tight integration and feedback loop between high-level requirements and their analysis against software artifacts. Our framework implements an analysis portal within the fret requirements elicitation tool, thus forming an end-to-end, open-source environment where requirements are written in an intuitive, structured natural language, and are verified automatically against Simulink models.

Mavridou, Anastasia↗
NASA NTRSDate not supplied

Bridging the Gap Between Requirements and Simulink Model Analysis

Formal veri fication and simulation are powerful tools for the veri fication of requirements against complex systems. Requirements are developed in early stages of the software lifecycle and are typically expressed in natural language. There is a gap between such requirements and their software implementations. We present a framework that bridges this gap by supporting a tight integration and feedback loop between high-level requirements and their analysis against software artifacts. Our framework implements an analysis portal within the fret requirements elicitation tool, thus forming an end-to-end, open-source environment where requirements are written in an intuitive, structured natural language, and are veri fied automatically against Simulink models.

FRET↗