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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
DOE OSTI2020

Model predictive control for voltage restoration in microgrids using temporal logic specifications

Power system operation will encounter numerous voltage variabilities as the proliferation of renewable energy continues. Real-time monitoring and communication technologies can potentially improve voltage stability by enabling the rapid detection of voltage deviations and the implementation of corrective actions. These corrective actions will only be effective in restoring stability if they are chosen in a timely and scalable manner. This paper considers the problem of power systems’ load voltage control in order to simultaneously address both magnitude and time voltage specifications. In order to comply with grid codes and avoid unnecessary relay protection actions, a model predictive control (MPC)-based control strategy employing temporal logic specifications (TLSs) is proposed. The TLSs strategy is introduced as a formalism to control the voltage variation at a critical load bus against operational bounds over time. The control objective is to schedule optimal control input signals from the available supportive energy storage systems, which provide reactive power injections, leading to satisfying the specified finite-time restoration described by the TLSs with minimal control efforts. The simulation results display that the TLSs strategy for power systems’ voltage control synthesis is extremely significant.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS2017

First Order Temporal Logic Monitoring with BDDs

Runtime verification is aimed at analyzing execution traces stemming from a running program or system. The traditional purpose is to detect the lack of conformance with respect to a formal specification. Numerous efforts in the field have focused on monitoring so-called parametric specifications, where events carry data, and formulas can refer to such. Since a monitor for such specifications has to store observed data, the challenge is to have an efficient representation and manipulation of Boolean operators, quantification, and lookup of data. The fundamental problem is that the actual values of the data are not necessarily bounded or provided in advance. In this work we explore the use of Binary Decision Diagrams (BDDs) for representing observed data. Our experiments show a substantial improvement in performance compared to related work.

Ulus, Dogan↗
NASA NTRS1988

Specifying real-time systems with interval logic

Pure temporal logic makes no reference to time. An interval temporal logic and an extension to that logic which includes real time constraints are described. The application of this logic by giving a specification for the well-known lift (elevator) example is demonstrated. It is shown how interval logic can be extended to include a notion of process. How the specification language and verification environment of EHDM could be enhanced to support this logic is described. A specification of the alternating bit protocol in this extended version of the specification language of EHDM is given.

Rushby, John↗
DOE OSTI2024

Real-Time Protocol Engineering with the B Language

It is an invariant that critical cyberphysical systems should not fail. Mission assurance requires systems to behave with predictability, especially in their ability to satisfy real-time constraints. The NIST standard for Engineering Trustworthy Secure Systems, National Institute of Standards and Technology (NIST) Special Publication (SP) 800-160v1r1 states that formal methods are the highest level for meeting assurance requirements. There is a tension between the formal method software development process (Figure 1), which does not introduce time specificity until the latter stages of the development process (concrete model), and the need to gain confidence that time constraints will be satisfied. This paper formalizes the practical application of temporal entities e.g. Propositional Temporal Logic (PTL), Temporal Logic of Actions Plus (TLA+), etc. to critical systems.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2005

Jeagle: a JAVA Runtime Verification Tool

We introduce the temporal logic Jeagle and its supporting tool for runtime verification of Java programs. A monitor for an Jeagle formula checks if a finite trace of program events satisfies the formula. Jeagle is a programming oriented extension of the rule-based powerful Eagle logic that has been shown to be capable of defining and implementing a range of finite trace monitoring logics, including future and past time temporal logic, real-time and metric temporal logics, interval logics, forms of quantified temporal logics, and so on. Monitoring is achieved on a state-by-state basis avoiding any need to store the input trace. Jeagle extends Eagle with constructs for capturing parameterized program events such as method calls and method returns. Parameters can be the objects that methods are called upon, arguments to methods, and return values. Jeagle allows one to refer to these in formulas. The tool performs automated program instrumentation using AspectJ. We show the transformational semantics of Jeagle.

DAmorim, Marcelo↗
NASA NTRS2004

Program Monitoring with LTL in EAGLE

We briefly present a rule-based framework called EAGLE, shown to be capable of defining and implementing finite trace monitoring logics, including future and past time temporal logic, extended regular expressions, real-time and metric temporal logics (MTL), interval logics, forms of quantified temporal logics, and so on. In this paper we focus on a linear temporal logic (LTL) specialization of EAGLE. For an initial formula of size m, we establish upper bounds of O(m(sup 2)2(sup m)log m) and O(m(sup 4)2(sup 2m)log(sup 2) m) for the space and time complexity, respectively, of single step evaluation over an input trace. This bound is close to the lower bound O(2(sup square root m) for future-time LTL presented. EAGLE has been successfully used, in both LTL and metric LTL forms, to test a real-time controller of an experimental NASA planetary rover.

Barringer, Howard↗
NASA NTRS2003

EAGLE can do Efficient LTL Monitoring

We briefly present a rule-based framework, called EAGLE, that has been shown to be capable of defining and implementing finite trace monitoring logics, including future and past time temporal logic, extended regular expressions, real-time logics, interval logics, forms of quantified temporal logics, and so on. In this paper we show how EAGLE can do linear temporal logic (LTL) monitoring in an efficient way. We give an upper bound on the space and time complexity of this monitoring.

Barringer, Howard↗
NASA NTRS2003

EAGLE Monitors by Collecting Facts and Generating Obligations

We present a rule-based framework, called EAGLE, that has been shown to be capable of defining and implementing a range of finite trace monitoring logics, including future and past time temporal logic, extended regular expressions, real-time and metric temporal logics, interval logics, forms of quantified temporal logics, and so on. A monitor for an EAGLE formula checks if a finite trace of states satisfies the given formula. We present, in details, an algorithm for the synthesis of monitors for EAGLE. The algorithm is implemented as a Java application and involves novel techniques for rule definition, manipulation and execution. Monitoring is achieved on a state-by-state basis avoiding any need to store the input trace of states. Our initial experiments have been successful as EAGLE detected a previously unknown bug while testing a planetary rover controller.

Barrnger, Howard↗
NASA NTRSDate not supplied

Monitoring ROS2: From Requirements to Autonomous Robots

Context/Goals - Capture mission requirements in high-level language. - Monitor requirements for robots. At a Glance - Transform requirements into runtime monitors for ROS2: - Requirements elicitation.* - Transform requirements into Temporal Logic formulas.* - Transform Temporal Logic formulas into runtime monitors.* - Generate hard real-time code for monitors.* - Generate ROS2 application directly from requirements.+ *Steps done in prior work. +Steps extended from prior work.

Runtime verification↗
NASA NTRS2002

Program Instrumentation and Trace Analysis

Several attempts have been made recently to apply techniques such as model checking and theorem proving to the analysis of programs. This shall be seen as a current trend to analyze real software systems instead of just their designs. This includes our own effort to develop a model checker for Java, the Java PathFinder 1, one of the very first of its kind in 1998. However, model checking cannot handle very large programs without some kind of abstraction of the program. This paper describes a complementary scalable technique to handle such large programs. Our interest is turned on the observation part of the equation: How much information can be extracted about a program from observing a single execution trace? It is our intention to develop a technology that can be applied automatically and to large full-size applications, with minimal modification to the code. We present a tool, Java PathExplorer (JPaX), for exploring execution traces of Java programs. The tool prioritizes scalability for completeness, and is directed towards detecting errors in programs, not to prove correctness. One core element in JPaX is an instrumentation package that allows to instrument Java byte code files to log various events when executed. The instrumentation is driven by a user provided script that specifies what information to log. Examples of instructions that such a script can contain are: 'report name and arguments of all called methods defined in class C, together with a timestamp'; 'report all updates to all variables'; and 'report all acquisitions and releases of locks'. In more complex instructions one can specify that certain expressions should be evaluated and even that certain code should be executed under various conditions. The instrumentation package can hence be seen as implementing Aspect Oriented Programming for Java in the sense that one can add functionality to a Java program without explicitly changing the code of the original program, but one rather writes an aspect and compiles it into the original program using the instrumentation. Another core element of JPaX is an observation package that supports the analysis of the generated event stream. Two kinds of analysis are currently supported. In temporal analysis the execution trace is evaluated against formulae written in temporal logic. We have implemented a temporal logic evaluator on finite traces using the Maude rewriting system from SRI International, USA. Temporal logic is defined in Maude by giving its syntax as a signature and its semantics as rewrite equations. The resulting semantics is extremely efficient and can handle event streams of hundreds of millions events in few minutes. Furthermore, the implementation is very succinct. The second form of even stream analysis supported is error pattern analysis where an execution trace is analyzed using various error detection algorithms that can identify error-prone programming practices that may potentially lead to errors in some different executions. Two such algorithms focusing on concurrency errors have been implemented in JPaX, one for deadlocks and the other for data races. It is important to note, that a deadlock or data race potential does not need to occur in order for its potential to be detected with these algorithms. This is what makes them very scalable in practice. The data race algorithm implemented is the Eraser algorithm from Compaq, however adopted to Java. The tool is currently being applied to a code base for controlling a spacecraft by the developers of that software in order to evaluate its applicability.

Havelund, Klaus↗
NASA NTRS1983

An interval logic for higher-level temporal reasoning

Prior work explored temporal logics, based on classical modal logics, as a framework for specifying and reasoning about concurrent programs, distributed systems, and communications protocols, and reported on efforts using temporal reasoning primitives to express very high level abstract requirements that a program or system is to satisfy. Based on experience with those primitives, this report describes an Interval Logic that is more suitable for expressing such higher level temporal properties. The report provides a formal semantics for the Interval Logic, and several examples of its use. A description of decision procedures for the logic is also included.

Schwartz, R. L.↗
DOE OSTI2026

Resilience Through Data-Driven, Intelligent Designed Control: A Formal Methods Approach

The PNNL and GTRI team developed a strategy to integrate temporal logic rule specification for detection of cyber-intrusion in the source code and control algorithms of CPS using advanced cyber-data. The GTRI team utilized its capabilities in rule synthesis and temporal logic specifications for software assurance and verification to detect and predict impact of cyber-intrusions and malware in the computational and control algorithms of cyber-physical systems. The team also developed a testing and verification approach that could be used to validate the suggested approach against a realistic use-case CPS showcasing improvements in system impact prediction performance. Temporal logic offers a compact expression of events in absolute and relative time and has a formalized translation to state machines. As such, temporal logic rules can feasibly be synthesized to any system as a rule engine, with the process being formally verified to be correct. The goal here is to utilize temporal logic rules to detect cyber-attacks and manipulations in the computational algorithms and provide real-time software assurance and verification guarantees.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1998

Cooperation Among Theorem Provers

This is a final report, which supports NASA's PECSEE (Persistent Cognizant Software Engineering Environment) effort and complements the Kestrel Institute project "Inference System Integration via Logic Morphism". The ultimate purpose of the project is to develop a superior logical inference mechanism by combining the diverse abilities of multiple cooperating theorem provers. In many years of research, a number of powerful theorem-proving systems have arisen with differing capabilities and strengths. Resolution theorem provers (such as Kestrel's KITP or SRI's, SNARK) deal with first-order logic with equality but not the principle of mathematical induction. The Boyer-Moore theorem prover excels at proof by induction but cannot deal with full first-order logic. Both are highly automated but cannot accept user guidance easily. The PVS system (from SRI) in only automatic within decidable theories, but it has well-designed interactive capabilities: furthermore, it includes higher-order logic, not just first-order logic. The NuPRL system from Cornell University and the STeP system from Stanford University have facilities for constructive logic and temporal logic, respectively - both are interactive. It is often suggested - for example, in the anonymous "QED Manifesto"-that we should pool the resources of all these theorem provers into a single system, so that the strengths of one can compensate for the weaknesses of others, and so that effort will not be duplicated. However, there is no straightforward way of doing this, because each system relies on its own language and logic for its success. Thus. SNARK uses ordinary first-order logic with equality, PVS uses higher-order logic. and NuPRL uses constructive logic. The purpose of this project, and the companion project at Kestrel, has been to use the category-theoretic notion of logic morphism to combine systems with different logics and languages. Kestrel's SPECWARE system has been the vehicle for the implementation.

Waldinger, Richard J.↗
NASA NTRSDate not supplied

Runtime Analysis with R2U2: A Tool Exhibition Report

We present R2U2 (Realizable, Responsive, Unobtrusive Unit), a hardware- supported tool and framework for the continuous monitoring of safetycritical and embedded cyber-physical systems.With the widespread advent of autonomous systems such as Unmanned Aerial Systems (UAS), satellites, rovers, and cars, real-time, on-board decision making requires unobtrusive monitoring of properties for safety, performance, security, and system health. R2U2 models combine past-time and future-time Metric Temporal Logic, “mission time” Linear Temporal Logic, probabilistic reasoning with Bayesian Networks, and modelbased prognostics. The R2U2 monitoring engine can be instantiated as a hardware solution, running on an FPGA, or as a software component. The FPGA realization enables R2U2 to monitor complex cyber-physical systems without any overhead or instrumentation of the flight software. In this tool exhibition report, we present R2U2 and demonstrate applications on system runtime monitoring, diagnostics, software health management, and security monitoring for a UAS. Our tool demonstration uses a hardware-based processor-in-the-loop “iron-bird” configuration.

Johann Martin Schumann↗
NASA NTRS2010

TPSAS-NF1676L-9990-DND

PVS (Prototype Veri cation System)1 is an interactive environment for the specification and verification of systems. PVS provides a strongly typed specification language, which is based on Higher-Order Logic. The type system of PVS supports: sub-typing, dependent-types, abstract data types, parametric types, records, unions, and tuples. The PVS theorem prover includes decision procedures for a variety of theories such as linear arithmetic, propositional logic, and temporal logic. This seminar will provide a gentle introduction to the basic and advanced features of PVS, including: theory interpretations, real number proving, batch proving, rapid prototyping, and strategy development. All these features are illustrated with simple examples and exercises.

César Muñoz↗