Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “temporal logic”

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 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
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 NTRS2020

Integrated Modeling and Development of Component-Based Embedded Software in Scala

Programming of embedded systems is challenging due to the low-level design patterns normally applied in the implementation of such systems. Furthermore, programming languages normally considered suitable for this level of programming, such as C and C++, are themselves low-level compared to more modern programming languages. We report on an effort exploring modeling and programming of embedded systems in modern high-level programming languages combining object-oriented and functional programming. We present an integration of four separate internal DSLs (libraries), considered useful for embedded program- ming, in the Scala programming language, for programming and testing component-based systems. These include a DSL for defining components and their connections, and a DSL for programming the individual components as hierarchical state machines. Two additional DSLs support testing, and include a DSL for writing temporal logic flavored test oracles for monitoring program executions, and a DSL for rule-based test input generation. The paper discusses the gap between Scala as used here and the needs for embedded systems programming.

Bocchino, Robert↗
NASA NTRS2023

Wildfire-fighting Use Case Requirements to Monitor

In this technical report, we provide requirements for a wildfire-fighting use-case, towards the Safety Demonstrator 1. The use case will incorporate ground and airborne assets operating in a coordinated fashion, and will comprise five activities, from detection to the execution of the initial attack. Depending on the activity and the data involved, the requirements identified may be non-probabilistic or probabilistic. In both cases, we first identify some of the requirements we wish to monitor, and then present a formalization using the language of requirements of the NASA requirements elicitation tool FRET. To formalize probabilistic requirements, we use a novel extension to FRET’s requirements language that incorporates notions of probability, and discuss how requirements can be translated into existing probabilistic temporal logics like PCTL. We exemplify how some of the requirements presented can be monitored using the existing tools Ogma and Copilot. We close with a summary and future directions.

Requirements↗
NASA NTRS2024

Discrete Event Simulation-Based Timeline Validation Using R2U2

The Gateway Vehicle Systems Manager (VSM), the top-level software control system in a distributed, hierarchical Autonomous System Management Architecture is, like most modern spacecraft software control systems, heavily data-driven. For example, schedules (timelines) will be developed on the ground and, due to the high degree of autonomy, contain complex procedures involving conditional branching, variable timing, and resource contention resolution. In order to verify that an uploaded timeline will function correctly, it is necessary to explore the feasible set of possible executions. While it is possible to test a timeline using a mission simulation, the complexity of the system and duration of a timeline limits the number of trials and therefore the test coverage. To address this problem, the VSM team is using a discrete event system model that can rapidly generate from a timeline sets of event sequences using Monte Carlo techniques. To achieve rapid and trustworthy checking of the event sequences, we use an offline version of the runtime model checking tool R2U2. This presentation describes the approach the VSM team is using to implement the discrete event simulation and evaluate event sequences using R2U2. The presentation will discuss: 1. Description of the timelines by VSM in the context of VSM operations 2. Expansion of a timeline into a sequence of atomic events 3. Adjustment, in the Monte Carlo environment, of an event sequence to account for uncertainty, external events, and failures 4. Definition of R2U2 input and mission-time linear temporal logic files 5. Generation and use of R2U2 verdict sequences 6. Lessons learned and future work

Verification↗
NASA NTRS2024

Runtime Verification of Hard Realtime Systems With Copilot: A Tutorial

This presentation is a tutorial on RV using Copilot, a runtime verification framework for real-time embedded systems. Copilot monitors are written in a compositional, stream-based language with support for a variety of Temporal Logics (TL), which results in robust, high-level specifications that are easier to understand than their traditional counterparts. The framework translates monitor specifications into C code with static memory requirements, which can be compiled to run on embedded hardware.

runtime monitoring↗
NASA NTRS1993

Agent oriented programming: An overview of the framework and summary of recent research

This is a short overview of the agent-oriented programming (AOP) framework. AOP can be viewed as an specialization of object-oriented programming. The state of an agent consists of components called beliefs, choices, capabilities, commitments, and possibly others; for this reason the state of an agent is called its mental state. The mental state of agents is captured formally in an extension of standard epistemic logics: beside temporalizing the knowledge and belief operators, AOP introduces operators for commitment, choice and capability. Agents are controlled by agent programs, which include primitives for communicating with other agents. In the spirit of speech-act theory, each communication primitive is of a certain type: informing, requesting, offering, etc. This document describes these features in more detail and summarizes recent results and ongoing AOP-related work.

Shoham, Yoav↗
NASA NTRS1999

Using Model Checking to Validate AI Planner Domain Models

This report describes an investigation into using model checking to assist validation of domain models for the HSTS planner. The planner models are specified using a qualitative temporal interval logic with quantitative duration constraints. We conducted several experiments to translate the domain modeling language into the SMV, Spin and Murphi model checkers. This allowed a direct comparison of how the different systems would support specific types of validation tasks. The preliminary results indicate that model checking is useful for finding faults in models that may not be easily identified by generating test plans.

Penix, John↗
NASA NTRS2011

Checking Flight Rules with TraceContract: Application of a Scala DSL for Trace Analysis

Typically during the design and development of a NASA space mission, rules and constraints are identified to help reduce reasons for failure during operations. These flight rules are usually captured in a set of indexed tables, containing rule descriptions, rationales for the rules, and other information. Flight rules can be part of manual operations procedures carried out by humans. However, they can also be automated, and either implemented as on-board monitors, or as ground based monitors that are part of a ground data system. In the case of automated flight rules, one considerable expense to be addressed for any mission is the extensive process by which system engineers express flight rules in prose, software developers translate these requirements into code, and then both experts verify that the resulting application is correct. This paper explores the potential benefits of using an internal Scala DSL for general trace analysis, named TRACECONTRACT, to write executable specifications of flight rules. TRACECONTRACT can generally be applied to analysis of for example log files or for monitoring executing systems online.

temporal logic↗
NASA NTRS2014

Model Checking Degrees of Belief in a System of Agents

Reasoning about degrees of belief has been investigated in the past by a number of authors and has a number of practical applications in real life. In this paper we present a unified framework to model and verify degrees of belief in a system of agents. In particular, we describe an extension of the temporal-epistemic logic CTLK and we introduce a semantics based on interpreted systems for this extension. In this way, degrees of beliefs do not need to be provided externally, but can be derived automatically from the possible executions of the system, thereby providing a computationally grounded formalism. We leverage the semantics to (a) construct a model checking algorithm, (b) investigate its complexity, (c) provide a Java implementation of the model checking algorithm, and (d) evaluate our approach using the standard benchmark of the dining cryptographers. Finally, we provide a detailed case study: using our framework and our implementation, we assess and verify the situational awareness of the pilot of Air France 447 flying in off-nominal conditions.

MAS Verification↗
NASA NTRS2011

Runtime Verification with State Estimation

We introduce the concept of Runtime Verification with State Estimation and show how this concept can be applied to estimate theprobability that a temporal property is satisfied by a run of a program when monitoring overhead is reduced by sampling. In such situations, there may be gaps in the observed program executions, thus making accurate estimation challenging. To deal with the effects of sampling on runtime verification, we view event sequences as observation sequences of a Hidden Markov Model (HMM), use an HMM model of the monitored program to "fill in" sampling-induced gaps in observation sequences, and extend the classic forward algorithm for HMM state estimation (which determines the probability of a state sequence, given an observation sequence) to compute the probability that the property is satisfied by an execution of the program. To validate our approach, we present a case study based on the mission software for a Mars rover. The results of our case study demonstrate high prediction accuracy for the probabilities computed by our algorithm. They also show that our technique is much more accurate than simply evaluating the temporal property on the given observation sequences, ignoring the gaps.

sampling↗
NASA NTRS2017

MESA: Message-Based System Analysis Using Runtime Verification

In this paper, we present a novel approach and framework for run-time verication of large, safety critical messaging systems. This work was motivated by verifying the System Wide Information Management (SWIM) project of the Federal Aviation Administration (FAA). SWIM provides live air traffic, site and weather data streams for the whole National Airspace System (NAS), which can easily amount to several hundred messages per second. Such safety critical systems cannot be instrumented, therefore, verification and monitoring has to happen using a nonintrusive approach, by connecting to a variety of network interfaces. Due to a large number of potential properties to check, the verification framework needs to support efficient formulation of properties with a suitable Domain Specific Language (DSL). Our approach is to utilize a distributed system that is geared towards connectivity and scalability and interface it at the message queue level to a powerful verification engine. We implemented our approach in the tool called MESA: Message-Based System Analysis, which leverages the open source projects RACE (Runtime for Airspace Concept Evaluation) and TraceContract. RACE is a platform for instantiating and running highly concurrent and distributed systems and enables connectivity to SWIM and scalability. TraceContract is a runtime verication tool that allows for checking traces against properties specified in a powerful DSL. We applied our approach to verify a SWIM service against several requirements.We found errors such as duplicate and out-of-order messages.

Message-based System↗
NASA NTRS2020

Operability on the Europa Clipper Mission: Challenges and Opportunities

Flight and ground system operability has been a focus area on the Europa Clipper Project since early in its formulation phase. This has given the operations team the opportunity to influence the design, with a goal of increasing overall system operability. This paper presents example operability challenges, opportunities, and solutions arising from the pre-Critical Design Review (CDR) system design. The integrated wing assembly design directly couples a scientific instrument (the REASON sounding radar) to the spacecraft’s power source (solar array wing panels). Impacts to mission operations of this design include: increased slew durations; solar array pointing constraints during inner cruise, Europa flybys, and orbit trim maneuvers; and stray light intrusions into the stellar reference units’ keep out zones. The use of CCSDS File Delivery Protocol (CFDP) Class-2 for reliable downlink of the large volume of Europa Clipper science data is described, along with nominal and off-nominal use cases. The effort to improve post-launch spacecraft visibility by adding a third low-gain antenna to the spacecraft is detailed. The design of the bulk data store has necessitated the implementation of accountable data products (ADPs), accountability identifiers (AIDs), and metadata packets to provide end-to-end science data accountability. To streamline and automate the flight rules generation and checking process, a first order and temporal logic-based solution of expressing flight rules without ambiguity, and whose programmatic implementation can be automated, is proposed. The focus on operability has had a positive influence on Europa Clipper design decisions, although cost, schedule, budget, heritage, and other technical concerns have many times outweighed operability concerns. However, experience to date demonstrates that this approach to operability results in more thorough, balanced consideration of the effect of early design trades and decisions on the operations phase of a mission than seen in many previous missions, and provides operations development insight into prioritizing work to go.

Signorelli, Joel↗
NASA NTRS2021

Operability on the Europa Clipper Mission: Challenges and Opportunities

Flight and ground system operability has been a focus area on the Europa Clipper Project since early in its formulation phase. This has given the operations team the opportunity to influence the design, with a goal of increasing overall system operability. This paper presents example operability challenges, opportunities, and solutions arising from the Critical Design Review (CDR) system design. The integrated wing assembly design directly couples a scientific instrument (the REASON sounding radar) to the spacecraft’s power source (solar array wing panels). Impacts to mission operations of this design include: increased slew durations; solar array pointing constraints during inner cruise, Europa flybys, and orbit trim maneuvers; and stray light intrusions into the stellar reference units’ keep out zones. The use of CCSDS File Delivery Protocol (CFDP) Class-2 for reliable downlink of the large volume of Europa Clipper science data is described, along with nominal and off-nominal use cases. The effort to improve post-launch spacecraft visibility by adding a third low-gain antenna to the spacecraft is detailed. The design of the bulk data store has necessitated the implementation of accountable data products (ADPs), accountability identifiers (AIDs), and metadata packets to provide end-to-end science data accountability. To streamline and automate the flight rules generation and checking process, a first order and temporal logic-based solution of expressing flight rules without ambiguity, and whose programmatic implementation can be automated, is proposed. The focus on operability has had a positive influence on Europa Clipper design decisions, although cost, schedule, budget, heritage, and other technical concerns have many times outweighed operability concerns. However, experience to date demonstrates that this approach to operability results in more thorough, balanced consideration of the effect of early design trades and decisions on the operations phase of a mission than seen in many previous missions, and provides operations development insight into prioritizing work to go.

Kumar, Meghana↗
NASA NTRSDate not supplied

Authoring, Analyzing, and Monitoring Requirements for a Lift-Plus-Cruise Aircraft

Requirements specification and analysis is widely applied to ensure the correctness of industrial systems in safety critical domains. Requirements are often initially written in natural language, which is highly ambiguous, and as a second step transformed into a language with rigorous semantics for formal analysis. [Question/problem] In this paper, we report on our experience in requirements creation and analysis, as well as run-time monitor generation using the Formal Requirement Elicitation Tool (FRET), on an industrial case study for a Lift-Plus-Cruise concept aircraft. [Principal ideas/results] We study the creation of requirements directly in the structured language of FRET without a prior definition of the same requirements in natural language. We focus on requirements describing state machines and discuss the challenges that we faced, in terms of creating requirements and generating monitors. We demonstrate how realizability, i.e., checking whether a requirements specification can be implemented, is crucial for understanding temporal interdependencies among requirements. [Contribution] Our study is the first complete attempt at using FRET to create industrial, realizable requirements and generate run-time monitors. Insight from lessons learned was materialized into new features in the FRET and JKind analysis frameworks.

Requirements engineering↗
NASA NTRSDate not supplied

Authoring, Analyzing, and Monitoring Requirements for a Lift-Plus-Cruise Aircraft

Requirements specification and analysis is widely applied to ensure the correctness of industrial systems in safety critical domains. Requirements are often initially written in natural language, which is highly ambiguous, and as a second step transformed into a language with rigorous semantics for formal analysis. In this paper, we report on our experience in requirements creation and analysis, as well as run-time monitor generation using the Formal Requirement Elicitation Tool (FRET), on an industrial case study for a Lift-Plus-Cruise concept aircraft. We study the creation of requirements directly in the structured language of FRET without a prior definition of the same requirements in natural language. We focus on requirements describing state machines and discuss the challenges that we faced, in terms of creating requirements and generating monitors. We demonstrate how realizability, i.e., checking whether a requirements specification can be implemented, is crucial for understanding temporal interdependencies among requirements. Our study is the first complete attempt at using FRET to create industrial, realizable requirements and generate run-time monitors. Insight from lessons learned was materialized into new features in the FRET and JKind analysis frameworks.

Requirements engineering↗
DOE OSTI2024

Model-Based Approaches to Generate Knowledge from Data in a Plant Reliability Context

One challenge that nuclear power plant system engineers are facing is that the amount of equipment reliability (ER) data being continuously generated are extremely large. These data elements come in different forms: textual (e.g., condition reports) and numeric (e.g., generated by monitoring systems) and they provide system engineers with valuable insights and information regarding the discovery of anomalous behaviors or degradation trends, the identification of the possible causes behind such behaviors and trends, and the prediction of their direct consequences. This paper directly targets the generation of knowledge from ER data by putting “data into context”. Here, we employ model-based system engineering (MBSE) models of systems and assets to represent and capture their architecture and functional (i.e., cause-effect) relations. ER data elements are processed by identifying first which elements of the developed MBSE elements they are referring to. This task is much harder for textual data since the information contained in issue or maintenance reports needs to “be understood” by a computational tool. Here we called this process “knowledge extraction” where our methods to extract knowledge from textual data. Lastly, once numeric and textual ER data elements have been processed and “understood”, we discover possible cause-effect relations among them. This is performed by observing if a logical connection through the MBSE models exists, and if there is a temporal relation among them. The logic and temporal are the two main ingredients to perform “machine reasoning” from ER data.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Model-Based Approaches to Generate Knowledge from Data in a Plant Reliability Context

One challenge that nuclear power plant system engineers are facing is continuous generation of an extremely large amount of equipment reliability (ER) data. These data elements come in textual (e.g., condition reports) and numeric (e.g., generated by monitoring systems) forms. They provide system engineers with valuable insights and information by discovering anomalous behaviors or degradation trends, identifying possible causes behind such behaviors and trends, and predicting their direct consequences. This paper directly targets the knowledge generation from ER data by putting “data into context.” We employ model-based system engineering (MBSE) of systems and assets to represent and capture their architecture and functional (i.e., cause-effect) relations. ER data elements are processed by first identifying which of the developed MBSE elements they are referring to. This task is harder for textual data since the information contained in issue or maintenance reports needs to be “understood” by a computational tool. We called this process “knowledge extraction” since our methods extract knowledge from textual data. Last, once numeric and textual ER data elements have been processed and “understood,” we discover possible cause-effect relations among them. This is performed by observing whether a logical connection through the MBSE models exists, and if there is a temporal relationship among them. The logic and temporal are the two main ingredients to perform “machine reasoning” from ER data.

97 - MATHEMATICS AND COMPUTING↗