SEARCH · Engineering Papers

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 289 records · Page 16

All sources NASA NTRS DOE OSTI

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.↗

NASA NTRS2016

Deductive Evaluation: Formal Code Analysis With Low User Burden

We describe a framework for symbolically evaluating iterative C code using a deductive approach that automatically discovers and proves program properties. Although verification is not performed, the method can infer detailed program behavior. Software engineering work flows could be enhanced by this type of analysis. Floyd-Hoare verification principles are applied to synthesize loop invariants, using a library of iteration-specific deductive knowledge. When needed, theorem proving is interleaved with evaluation and performed on the fly. Evaluation results take the form of inferred expressions and type constraints for values of program variables. An implementation using PVS (Prototype Verification System) is presented along with results for sample C functions.

Di Vito, Ben. L↗

NASA NTRS2017

Some Observations on Damage Tolerance Analyses in Pressure Vessels

AIAA standards S080 and S081 are applicable for certification of metallic pressure vessels (PV) and composite overwrap pressure vessels (COPV), respectively. These standards require damage tolerance analyses with a minimum reliable detectible flaw/crack and demonstration of safe life four times the service life with these cracks at the worst-case location in the PVs and oriented perpendicular to the maximum principal tensile stress. The standards require consideration of semi-elliptical surface cracks in the range of aspect ratios (crack depth a to half of the surface length c, i.e., (a/c) of 0.2 to 1). NASA-STD-5009 provides the minimum reliably detectible standard crack sizes (90/95 probability of detection (POD) for several non-destructive evaluation (NDE) methods (eddy current (ET), penetrant (PT), radiography (RT) and ultrasonic (UT)) for the two limits of the aspect ratio range required by the AIAA standards. This paper tries to answer the questions: can the safe life analysis consider only the life for the crack sizes at the two required limits, or endpoints, of the (a/c) range for the NDE method used or does the analysis need to consider values within that range? What would be an appropriate method to interpolate 90/95 POD crack sizes at intermediate (a/c) values? Several procedures to develop combinations of a and c within the specified range are explored. A simple linear relationship between a and c is chosen to compare the effects of seven different approaches to determine combinations of aj and cj that are between the (a/c) endpoints. Two of the seven are selected for evaluation: Approach I, the simple linear relationship, and a more conservative option, Approach III. For each of these two Approaches, the lives are computed for initial semi-elliptic crack configurations in a plate subjected to remote tensile fatigue loading with an R-ratio of 0.1, for an assumed material evaluated using NASGRO (registered 4) version 8.1. These calculations demonstrate that for this loading, using Approach I and the initial detectable crack sizes at the (a/c) endpoints in 5009 specified for the ET and UT NDE methods, the smallest life is not at the two required limits of the (a/c) range, but rather is at an intermediate configuration in the range (a/c) of 0.4 to 0.6. Similar analyses using both Approach I and III with the initial detectable crack size at the (a/c) endpoints in 5009 for PT NDE showed the smallest life may be at an (a/c) endpoint or an intermediate (a/c), depending upon which Approach is used. As such, analyses that interrogate only the two (a/c) values of 0.2 and 1 may result in unconservative life predictions. The standard practice may need to be revised based on these results.

Raju, Ivatury S.↗

NASA NTRS2017

An Efficient Universal Trajectory Language

The Efficient Universal Trajectory Language (EUTL) is a language for specifying and representing trajectories for Air Traffic Management (ATM) concepts such as Trajectory-Based Operations (TBO). In these concepts, the communication of a trajectory between an aircraft and ground automation is fundamental. Historically, this trajectory exchange has not been done, leading to trajectory definitions that have been centered around particular application domains and, therefore, are not well suited for TBO applications. The EUTL trajectory language has been defined in the Prototype Verification System (PVS) formal specification language, which provides an operational semantics for the EUTL language. The hope is that EUTL will provide a foundation for mathematically verified algorithms that manipulate trajectories. Additionally, the EUTL language provides well-defined methods to unambiguously determine position and velocity information between the reported trajectory points. In this paper, we present the EUTL trajectory language in mathematical detail.

Hagen, George E.↗

NASA NTRS2017

Map Projection Induced Variations in Locations of Polygon Geofence Edges

This Paper under-estimates answers to the following question under various constraints: If a geofencing algorithm uses a map projection to determine whether a position is inside/outside a polygon region, how far outside/inside the polygon can the point be and the algorithm determine that it is inside/outside (the opposite and therefore incorrect answer)? Geofencing systems for unmanned aircraft systems (UAS) often model stay-in and stay-out regions using 2D polygons with minimum and maximum altitudes. The vertices of the polygons are typically input as latitude-longitude pairs, and the edges as paths between adjacent vertices. There are numerous ways to generate these paths, resulting in numerous potential locations for the edges of stay-in and stay-out regions. These paths may be geodesics on a spherical model of the earth or geodesics on the WGS84 reference ellipsoid. In geofencing applications that use map projections, these paths are inverse images of straight lines in the projected plane. This projected plane may be a projection of a spherical earth model onto a tangent plane, called an orthographic projection. Alternatively, it may be a projection where the straight lines in the projected plane correspond to straight lines in the latitudelongitude coordinate system, also called a Plate Carr´ee projection. This paper estimates distances between different edge paths and an oracle path, which is a geodesic on either the spherical earth or the WGS84 ellipsoidal earth. This paper therefore estimates how far apart different edge paths can be rather than comparing their path lengths, which are not considered. Rather, the comparision is between the actual locations of the edges between vertices. For edges drawn using orthographic projections, this maximum distance increases as the distance from the polygon vertices to the projection point increases. For edges drawn using Plate Carr´ee projections, this maximum distance increases as the vertices become further from the equator. Distances between geodesics on a spherical earth and a WGS84 ellipsoidal earth are also analyzed, using the WGS84 ellipsoid as the oracle. Bounds on the 2D distance between a straight line and a great circle path, in an orthographically projected plane rather than on the surface of the earth, have been formally verified in the PVS theorem prover, meaning that they are mathematically correct in the absence of floating point errors.

Neeley, Paula↗

NASA NTRS2018

The Number of Support Constraints for Overlapping Set Optimization with Nested Admissible Sets Is Equal to One

This paper reports on the formalization of a recent result by Crespo, et al., as found in the references. The formalized result bounds the number of support constraints in a particular type of optimization problem. The problem involves discovering an optimal member of a family of sets that overlaps each member of a constraining collection of sets. The particular case addressed here concerns optimizations in which the family of sets is nested. The primary results were formalized in the interactive theorem prover PVS and support the claim that a single support constraint exists in very general circumstances.

Siratt, John↗

NASA NTRS2018

A Formally Verified Floating-Point Implementation of the Compact Position Reporting Algorithm

The Automatic Dependent Surveillance-Broadcast (ADS-B) system allows aircraft to communicate their current state, including position and velocity information, to other aircraft in their vicinity and to ground stations. The Compact Position Reporting (CPR) algorithm is the ADS-B module responsible for the encoding and decoding of aircraft positions. CPR is highly sensitive to computer arithmetic since it heavily relies on functions that are intrinsically unstable such as floor and modulo. In this paper, a formally-verified double-precision floating-point implementation of the CPR algorithm is presented. The verification proceeds in three steps. First, an alternative version of CPR, which reduces the floating-point rounding error is proposed. Then, the Prototype Verification System (PVS) is used to formally prove that the ideal real-number counterpart of the improved algorithm is mathematically equivalent to the standard CPR definition. Finally, the static analyzer Frama-C is used to verify that the double-precision implementation of the improved algorithm is correct with respect to its operational requirement. The alternative algorithm is currently being considered for inclusion in the revised version of the ADS-B standards document as the reference implementation of the CPR algorithm.

Laura Titolo↗

NASA NTRS2019

Provably Correct Floating-Point Implementation of a Point-In-Polygon Algorithm

The problem of determining whether or not a point lies inside a given polygon occurs in many applications. In air traffic management concepts, a correct solution to the point-in-polygon problem is critical to geofencing systems for Unmanned Aerial Vehicles and in weather avoidance applications. Many mathematical methods can be used to solve the point-in-polygon problem. Unfortunately, a straightforward floating- point implementation of these methods can lead to incorrect results due to round-off errors. In particular, these errors may cause the control flow of the program to diverge with respect to the ideal real-number algorithm. This divergence potentially results in an incorrect point-in- polygon determination even when the point is far from the edges of the polygon. This paper presents a provably correct implementation of a point-in-polygon method that is based on the computation of the winding number. This implementation is mechanically generated from a source- to-source transformation of the ideal real-number specification of the algorithm. The correctness of this implementation is formally verified within the Frama-C analyzer, where the proof obligations are discharged using the Prototype Verification System (PVS).

Moscato, Mariano M.↗

NASA NTRSDate not supplied

Automatic Generation of Guard-Stable Floating-Point Code

In floating-point programs, test instability occurs when the control flow of a conditional statement diverges from its ideal execution under real arithmetic. This phenomenon is caused by the presence of round-off errors in floating-point computations. Writing programs that correctly handle test instability often require expertise on finite precision computations and rounding errors. This paper presents a fully automatic tool chain that generates and formally verifies a test-stable floating-point C program from its functional specification in real arithmetic. The generated program is instrumented to soundly detect when unstable tests may occur and, in these cases, to issue a warning. The proposed approach combines the PRECiSA floating-point static analyzer, the Frama-C software verification suite, and the PVS theorem prover.

Floating-Point Arithmetic↗

NASA NTRS2021

NASA KSC Internship Experience & Project Report

As part of the Spring 2021 Engineering Student Trainee rotation with the National Aeronautics and Space Administration (NASA) through the Pathways program at Kennedy Space Center (KSC). I served under KSC’s Engineering directorate as a Pneumatics Engineering Intern for the Environmental and Life support Systems branch (NE-XF). During my Internship, I primarily supported the Exploration Ground Systems (EGS) program under the direct supervision of NE-XF Pneumatics Senior Engineer, Ruben Jaca, and NE-XF matrix supervisor, Stephen M. Anthony. I worked on the completion of a Pressure Vessel and Pressurized System (PVS) certification for a Payload Accommodation Subsystem (PAS) prototype. As part of the Pathways program, I was additionally exposed to various career and skill enhancement activities.

Internship↗

NASA NTRSDate not supplied

Interpretation and Formalization of the Right-of-Way Rules

This paper presents an interpretation and mathematical definition of the right-of-way rules as stated in USA, Title 14 of the Code of Federal Regulations, Part 91, Section 91.113 (14 CFR 91.113). In an encounter between two aircraft, the right-of-way rules in 14 CFR 91.113 defines which aircraft, if any, has the right-of-way and which aircraft must maneuver to stay well clear of the other aircraft. The objective of the work presented in this paper is to give an unambiguous interpretation of the rules. From the interpretation, a precise mathematical formulation is created that can be used for analysis and proof of properties. The mathematical formulation has been defined in the Prototype Verification System (PVS) and properties of well formedness and core properties of the formalization have been mechanically proved. Additional objectives are to use the mathematical formulation to code a rule compliant virtual pilot that can be used in simulation experiments and to possibly use the rule compliant virtual pilot in autonomous operations.

right-of-way↗

NASA NTRSDate not supplied

Interpretation and Formalization of the Right-of-Way Rules

This paper presents an interpretation and mathematical definition of the right-of-way rules as stated in USA, Title 14 of the Code of Federal Regulations, Part 91, Section 91.113 (14 CFR 91.113). In an encounter between two aircraft, the right-of-way rules defines which aircraft, if any, has the right-of-way and which AQ2 aircraft must maneuver to stay well clear of the other aircraft. The objective of the work presented in this paper is to give an unambiguous interpretation of the rules. From the interpretation, a precise mathematical formulation is created that can be used for analysis and proof of properties. The mathematical formulation has been defined in the Prototype Verification System (PVS) and properties of well formedness and core properties of the formalization have been mechanically proved. This mathematical formulation can be implemented digitally, so that right-of-way rules can be used in simulation or in future autonomous operations.

Right-of-Way↗

NASA NTRSDate not supplied

Formalization of the Bellman-Ford Algorithm for Airspace Applications

This paper describes the formal verification of one of the most well-known algorithms for finding the shortest path between all vertices in a directed graph, namely the Bellman-Ford algorithm. This formal verification, performed in the Prototype Verification System (PVS), is motivated by two applications in the aerospace domain which use the algorithm for path planning. The first is a pre-flight calculation that uses an adapted version of Bellman-Ford to find a route intended to maximize GNSS availability throughout the flight. The second is a more traditional application intended to find the shortest path between an autonomous aircraft's current position and a goal waypoint, while avoiding regions of space specified by geofences. A novel aspect of this formal verification effort is the inclusion of two distinct models of computation for the algorithm, one being a traditional serial computation, and the other being an explicitly parallel computation. The ability to use parallel computation in the Bellman-Ford algorithm is in fact why it was chosen over other traditionally more performant algorithms, especially for the GNSS application, where the size of the graph makes a purely serial computation infeasible.

formal verification↗

DOE OSTI2015

CS-Studio Scan System Parallelization

For several years, the Control System Studio (CS-Studio) Scan System has successfully automated the operation of beam lines at the Oak Ridge National Laboratory (ORNL) High Flux Isotope Reactor (HFIR) and Spallation Neutron Source (SNS). As it is applied to additional beam lines, we need to support simultaneous adjustments of temperatures or motor positions. While this can be implemented via virtual motors or similar logic inside the Experimental Physics and Industrial Control System (EPICS) Input/Output Controllers (IOCs), doing so requires a priori knowledge of experimenters requirements. By adding support for the parallel control of multiple process variables (PVs) to the Scan System, we can better support ad hoc automation of experiments that benefit from such simultaneous PV adjustments.

43 PARTICLE ACCELERATORS↗