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 127 records · Page 7

Runtime Monitoring with R2U2 for Aircraft Systems with Neural Networks

R2U2 (Realizable, Responsive, Unobtrusive Unit) is a hardware-supported tool and framework for real-time system monitoring and software health management of cyber-physical systems. During system operation, R2U2 continuously monitors properties about safety, performance, and security of the vehicle and its vital components and can perform diagnostic reasoning. Efficient observers for past-time and future-time Metric Temporal Logic, fast reasoners for Bayesian Networks, and model-based prognostics algorithms are key components of R2U2 and designed for minimal computational footprint. R2U2 has been implemented in software supporting ROS, NASA's cFS/cFE, and Simulink and as an FPGA configuration. The synergistic combination of monitors and observers in R2U2 makes it possible to design powerful models for system runtime monitoring, diagnostics, software health management, prognostics, and security monitoring. In this presentation, I will give a detailed overview of the R2U2 architecture and its features and will discuss the application of R2U2 for safety-monitoring of a neural-network based autonomous centerline tracking system (ACT) for autonomous aircraft.

Runtime Monitoring↗

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↗

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↗

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↗

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↗

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↗

Quantifying Uncertainty in Epidemiological Models

Modern epidemiology has made use of a number of mathematical models, including ordinary differential equation (ODE) based models and agent based models (ABMs) to describe the dynamics of how a disease may spread within a population and enable the rational design of strategies for intervention that effectively contain the spread of the disease. Although such predictions are of fundamental importance in preventing the next global pandemic, there is a significant gap in trusting the outcomes/predictions solely based on such models. Hence, there is a need to develop approaches such that mathematical models can be calibrated against historical data. In addition, there is a need to develop rigorous uncertainty quantification approaches that can provide insights into when a model will fail and characterize the confidence in the (possibly multiple) model outcomes/predictions, when such retrospective analysis cannot be performed. In this paper, we outline an approach to develop uncertainty quantification approaches for epidemiological models using formal methods and model checking. By specifying the outcomes expected from a model in a suitable spatio-temporal logic, we use probabilistic model checking methods to quantify the probability with which the epidemiological model satisfies the specification. We argue that statistical model checking methods can solve the uncertainty quantification problem for complex epidemiological models.

model checking↗

Digital Analytics, Causal Knowledge Acquisition and Reasoning for Technical Language Processing

Complex engineering systems such as nuclear power plants (NPPs) generate and collect large amounts of equipment reliability (ER) data elements that contain information on the status of components, assets, and systems. Some of this information is textual in form and can be found in documents such as incident reports (IRs) and work orders (WOs). Analyses of textual data in current NPPs-using natural language processing (NLP) methods-have been expanded over the last decade, and it is only recently that the true potential of such analyses has emerged. So far, applications of NLP methods have mostly been limited to classification and prediction, the goal being to identify the nature of the textual element (e.g., safety or non-safety related). Here, we target a more complex problem: automatically extracting knowledge from a textual element in order to assist system engineers in conducting system health assessments. Knowledge extraction is a very broad concept, and its definition may vary depending on the application context. Our methods are a blend of both rule-based and machine learning (ML) algorithms. For our purposes, knowledge extraction means identifying the systems or assets mentioned in a given textual element, as well as the type of event described (e.g., component failure or maintenance activity). In addition, we want to capture details such as measured quantities and the temporal/cause-effect relations between events. In this tool, we also demonstrate how textual data elements are preprocessed in order to handle typos, acronyms, and abbreviations. One main feature of these methods is that they are not based solely on data, but are in fact model-based. In other words, they also rely on MBSE models that are designed to capture-from a functional point of view-the architecture of the systems/assets under consideration. The main purpose of such models is to digitally emulate system engineers' knowledge of system and asset architecture and to identify dependencies among systems, assets, and components. Provided these models, analyses of textual and numeric ER data can be performed by first identifying the OPM model elements to which the ER data elements are referring. The relationships between ER data elements are then identified by checking for any temporal or logical dependencies.

Mandelli, Diego [Idaho National Laboratory (INL), ↗

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↗

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↗

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↗

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↗

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↗

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↗

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↗

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↗

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↗