SEARCH · Search NASA

Results for “PVs”

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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 127 records · Page 7

All sources NASA NTRS DOE OSTI

NASA NTRS2006

Diagnosing a Failed Proof in Fault-Tolerance: A Disproving Challenge Problem

This paper proposes a challenge problem in disproving. We describe a fault-tolerant distributed protocol designed at NASA for use in a fly-by-wire system for next-generation commercial aircraft. An early design of the protocol contains a subtle bug that is highly unlikely to be caught in fault injection testing. We describe a failed proof of the protocol's correctness in a mechanical theorem prover (PVS) with a complex unfinished proof conjecture. We use a model checking suite (SAL) to generate a concrete counterexample to the unproven conjecture to demonstrate the existence of a bug. However, we argue that the effort required in our approach is too high and propose what conditions a better solution would satisfy. We carefully describe the protocol and bug to provide a challenging but feasible case study for disproving research.

Pike, Lee↗

NASA NTRS2008

A Formal Framework for the Analysis of Algorithms That Recover From Loss of Separation

We present a mathematical framework for the specification and verification of state-based conflict resolution algorithms that recover from loss of separation. In particular, we propose rigorous definitions of horizontal and vertical maneuver correctness that yield horizontal and vertical separation, respectively, in a bounded amount of time. We also provide sufficient conditions for independent correctness, i.e., separation under the assumption that only one aircraft maneuvers, and for implicitly coordinated correctness, i.e., separation under the assumption that both aircraft maneuver. An important benefit of this approach is that different aircraft can execute different algorithms and implicit coordination will still be achieved, as long as they all meet the explicit criteria of the framework. Towards this end we have sought to make the criteria as general as possible. The framework presented in this paper has been formalized and mechanically verified in the Prototype Verification System (PVS).

Butler, RIcky W.↗

NASA NTRS2008

Embedded ESD Protection Proof of Concept

The purpose of this project is to characterize and correlate Electrostatic Discharge (ESD) sensitivity levels of an Integrated Circuit (IC) package using Transmission Line Pulse (TLP) and Human Body Model (HBM) methods. This characterization will be used as a baseline ESD sensitivity level to demonstrate improvement to the ESD sensitivity of the IC package through the use of EPI-FLO(Trade Mark) Polymer Voltage Suppression (PVS) protection devices developed and manufactured by Electronic Polymers, Inc. (EPI).

Human Body Model (HBM) methods↗

NASA NTRS2005

Hybrid Verification of an Air Traffic Operational Concept

A concept of operations for air traffic management consists of a set of flight rules and procedures aimed to keep aircraft safely separated. This paper reports on the formal verification of separation properties of the NASA's Small Aircraft Transportation System, Higher Volume Operations (SATS HVO) concept for non-towered, non-radar airports. Based on a geometric description of the SATS HVO air space, we derive analytical formulas to compute spacing requirements on nominal approaches. Then, we model the operational concept by a hybrid non-deterministic asynchronous state transition system. Using an explicit state exploration technique, we show that the spacing requirements are always satisfied on nominal approaches. All the mathematical development presented in this paper has been formally verified in the Prototype Verification System (PVS). Keywords. Formal verification, hybrid systems, air traffic management, theorem proving

Munoz, Cesar A.↗

NASA NTRS2009

A Mode-Shape-Based Fault Detection Methodology for Cantilever Beams

An important goal of NASA's Internal Vehicle Health Management program (IVHM) is to develop and verify methods and technologies for fault detection in critical airframe structures. A particularly promising new technology under development at NASA Langley Research Center is distributed Bragg fiber optic strain sensors. These sensors can be embedded in, for instance, aircraft wings to continuously monitor surface strain during flight. Strain information can then be used in conjunction with well-known vibrational techniques to detect faults due to changes in the wing's physical parameters or to the presence of incipient cracks. To verify the benefits of this technology, the Formal Methods Group at NASA LaRC has proposed the use of formal verification tools such as PVS. The verification process, however, requires knowledge of the physics and mathematics of the vibrational techniques and a clear understanding of the particular fault detection methodology. This report presents a succinct review of the physical principles behind the modeling of vibrating structures such as cantilever beams (the natural model of a wing). It also reviews two different classes of fault detection techniques and proposes a particular detection method for cracks in wings, which is amenable to formal verification. A prototype implementation of these methods using Matlab scripts is also described and is related to the fundamental theoretical concepts.

Tejada, Arturo↗

NASA NTRS2009

Formally Verified Practical Algorithms for Recovery from Loss of Separation

In this paper, we develop and formally verify practical algorithms for recovery from loss of separation. The formal verification is performed in the context of a criteria-based framework. This framework provides rigorous definitions of horizontal and vertical maneuver correctness that guarantee divergence and achieve horizontal and vertical separation. The algorithms are shown to be independently correct, that is, separation is achieved when only one aircraft maneuvers, and implicitly coordinated, that is, separation is also achieved when both aircraft maneuver. In this paper we improve the horizontal criteria over our previous work. An important benefit of the criteria approach is that different aircraft can execute different algorithms and implicit coordination will still be achieved, as long as they all meet the explicit criteria of the framework. Towards this end we have sought to make the criteria as general as possible. The framework presented in this paper has been formalized and mechanically verified in the Prototype Verification System (PVS).

Butler, Ricky W.↗

NASA NTRS2009

Compositional Verification of a Communication Protocol for a Remotely Operated Vehicle

This paper presents the specification and verification in the Prototype Verification System (PVS) of a protocol intended to facilitate communication in an experimental remotely operated vehicle used by NASA researchers. The protocol is defined as a stack-layered com- position of simpler protocols. It can be seen as the vertical composition of protocol layers, where each layer performs input and output message processing, and the horizontal composition of different processes concurrently inhabiting the same layer, where each process satisfies a distinct requirement. It is formally proven that the protocol components satisfy certain delivery guarantees. Compositional techniques are used to prove these guarantees also hold in the composed system. Although the protocol itself is not novel, the methodology employed in its verification extends existing techniques by automating the tedious and usually cumbersome part of the proof, thereby making the iterative design process of protocols feasible.

Goodloe, Alwyn E.↗

NASA NTRS2009

Formal methods for modeling and analysis of hybrid systems

A technique based on the use of a quantifier elimination decision procedure for real closed fields and simple theorem proving to construct a series of successively finer qualitative abstractions of hybrid automata is taught. The resulting abstractions are always discrete transition systems which can then be used by any traditional analysis tool. The constructed abstractions are conservative and can be used to establish safety properties of the original system. The technique works on linear and non-linear polynomial hybrid systems: the guards on discrete transitions and the continuous flows in all modes can be specified using arbitrary polynomial expressions over the continuous variables. An exemplar tool in the SAL environment built over the theorem prover PVS is detailed. The technique scales well to large and complex hybrid systems.

Tiwari, Ashish↗

NASA NTRS2010

How Formal Methods Impels Discovery: A Short History of an Air Traffic Management Project

In this paper we describe a process of algorithmic discovery that was driven by our goal of achieving complete, mechanically verified algorithms that compute conflict prevention bands for use in en route air traffic management. The algorithms were originally defined in the PVS specification language and subsequently have been implemented in Java and C++. We do not present the proofs in this paper: instead, we describe the process of discovery and the key ideas that enabled the final formal proof of correctness

Butler, Ricky W.↗

NASA NTRS2010

A Machine-Checked Proof of A State-Space Construction Algorithm

This paper presents the correctness proof of Saturation, an algorithm for generating state spaces of concurrent systems, implemented in the SMART tool. Unlike the Breadth First Search exploration algorithm, which is easy to understand and formalise, Saturation is a complex algorithm, employing a mutually-recursive pair of procedures that compute a series of non-trivial, nested local fixed points, corresponding to a chaotic fixed point strategy. A pencil-and-paper proof of Saturation exists, but a machine checked proof had never been attempted. The key element of the proof is the characterisation theorem of saturated nodes in decision diagrams, stating that a saturated node represents a set of states encoding a local fixed-point with respect to firing all events affecting only the node s level and levels below. For our purpose, we have employed the Prototype Verification System (PVS) for formalising the Saturation algorithm, its data structures, and for conducting the proofs.

Catano, Nestor↗

NASA NTRS2010

Formal Verification of Air Traffic Conflict Prevention Bands Algorithms

In air traffic management, a pairwise conflict is a predicted loss of separation between two aircraft, referred to as the ownship and the intruder. A conflict prevention bands system computes ranges of maneuvers for the ownship that characterize regions in the airspace that are either conflict-free or 'don't go' zones that the ownship has to avoid. Conflict prevention bands are surprisingly difficult to define and analyze. Errors in the calculation of prevention bands may result in incorrect separation assurance information being displayed to pilots or air traffic controllers. This paper presents provably correct 3-dimensional prevention bands algorithms for ranges of track angle; ground speed, and vertical speed maneuvers. The algorithms have been mechanically verified in the Prototype Verification System (PVS). The verification presented in this paper extends in a non-trivial way that of previously published 2-dimensional algorithms.

Narkawicz, Anthony J.↗

NASA NTRS2009

Stochastic Formal Correctness of Numerical Algorithms

We provide a framework to bound the probability that accumulated errors were never above a given threshold on numerical algorithms. Such algorithms are used for example in aircraft and nuclear power plants. This report contains simple formulas based on Levy's and Markov's inequalities and it presents a formal theory of random variables with a special focus on producing concrete results. We selected four very common applications that fit in our framework and cover the common practices of systems that evolve for a long time. We compute the number of bits that remain continuously significant in the first two applications with a probability of failure around one out of a billion, where worst case analysis considers that no significant bit remains. We are using PVS as such formal tools force explicit statement of all hypotheses and prevent incorrect uses of theorems.

Daumas, Marc↗

NASA NTRS2013

The Next Generation of Cold Immersion Dry Suit Design Evolution for Hypothermia Prevention

This new utility patent is an active design that relies on the lung's role as an organic heat exchanger for providing deep body core heating of air. It is based on the fact that the greatest heat loss mechanism for an insulated human body immersed in a cold water environment is due to heat loss through respiration. This innovation successfully merges two existing technologies (cold immersion suit and existing valve technologies) to produce a new product that helps prevent against the onset of hypothermia at sea. During normal operations, a human maintains an approximate body temperature of [98.6 F (37 C)]. A mechanism was developed to recover the warm temperature from the body and reticulate it in a survival suit. The primary intention is to develop an encompassing systems design that can both easily and cost effectively be integrated in all existing currently manufactured cold water survival suits, and as such, it should be noted that the cold water immersion suit is only used as a framework or tool for laying out the required design elements. At the heart of the suit is the Warm Air Recovery (WAR) system, which relies on a single, large Main Purge Valve (MPV) and secondary Purge Valves (PV) to operate. The main purge valve has a thin membrane, which is normally closed, and acts as a one-way check valve. When warm air is expelled from the lungs, it causes the main purge valve to open. Air forced from the MPV is dumped directly into the suit, thereby providing warmth to the torso, legs, and arms. A slight positive over-pressure in the suit causes warm waste air (or water if the suit is punctured) to be safely vented into the sea through large PVs located at the bottom of each arm and leg. The secondary purge valves act to prevent the buildup of large concentrations of CO2 gas and help guard against asphyxia. It is noted that the MPV causes the inhalation and exhalation cycles to be completely isolated from one another in the current suit design.

Galofaro, Joel↗

NASA NTRS2013

Verification of Numerical Programs: From Real Numbers to Floating Point Numbers

Numerical algorithms lie at the heart of many safety-critical aerospace systems. The complexity and hybrid nature of these systems often requires the use of interactive theorem provers to verify that these algorithms are logically correct. Usually, proofs involving numerical computations are conducted in the infinitely precise realm of the field of real numbers. However, numerical computations in these algorithms are often implemented using floating point numbers. The use of a finite representation of real numbers introduces uncertainties as to whether the properties veri ed in the theoretical setting hold in practice. This short paper describes work in progress aimed at addressing these concerns. Given a formally proven algorithm, written in the Program Verification System (PVS), the Frama-C suite of tools is used to identify sufficient conditions and verify that under such conditions the rounding errors arising in a C implementation of the algorithm do not affect its correctness. The technique is illustrated using an algorithm for detecting loss of separation among aircraft.

Goodloe, Alwyn E.↗

NASA NTRS2015

Advancements of the Lightweight Integrated Solar Array and Transceiver (LISA-T) Small Spacecraft System

This paper describes recent advancements of the Lightweight Integrated Solar Array and Transceiver (LISA-T) currently being developed at NASA's Marshall Space Flight Center. The LISA-T array comprises a launch stowed, orbit deployed structure on which thin-film photovoltaic (PV) and antenna devices are embedded. The system provides significant electrical power generation at low weights, high stowage efficiency, and without the need for solar tracking. Leveraging high-volume terrestrial-market PVs also gives the potential for lower array costs. LISA-T is addressing the power starvation epidemic currently seen by many small-scale satellites while also enabling the application of deployable antenna arrays. Herein, an overview of the system and its applications are presented alongside sub-system development progress and environmental testing plans/initial results.

Russell, Tiffany↗

NASA NTRS2015

Advancements of the Lightweight Integrated Solar Array and Transceiver (LISA-T) Small Spacecraft System

Lockett, Tiffany Russell↗

NASA NTRS2015

Software Validation via Model Animation

This paper explores a new approach to validating software implementations that have been produced from formally-verified algorithms. Although visual inspection gives some confidence that the implementations faithfully reflect the formal models, it does not provide complete assurance that the software is correct. The proposed approach, which is based on animation of formal specifications, compares the outputs computed by the software implementations on a given suite of input values to the outputs computed by the formal models on the same inputs, and determines if they are equal up to a given tolerance. The approach is illustrated on a prototype air traffic management system that computes simple kinematic trajectories for aircraft. Proofs for the mathematical models of the system's algorithms are carried out in the Prototype Verification System (PVS). The animation tool PVSio is used to evaluate the formal models on a set of randomly generated test cases. Output values computed by PVSio are compared against output values computed by the actual software. This comparison improves the assurance that the translation from formal models to code is faithful and that, for example, floating point errors do not greatly affect correctness and safety properties.

Dutle, Aaron M.↗

NASA NTRS2016

Deductive Evaluation: Implicit Code Verification With Low User Burden

We describe a framework for symbolically evaluating C code using a deductive approach that discovers and proves program properties. The framework applies Floyd-Hoare verification principles in its treatment of loops, with a library of iteration schemes serving to derive loop invariants. During evaluation, theorem proving is performed on-the-fly, obviating the generation of verification conditions normally needed to establish loop properties. A PVS-based prototype is presented along with results for sample C functions.

Di Vito, Ben L.↗