SEARCH · Engineering Papers

Results for “formal verification”

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 379 records · Page 21

All sources NASA NTRS DOE OSTI

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

Intelligent Lemma Selection for Formal Methods Proofs

To help in formally verifying the correctness of various systems, NASA constructs mathematical proofs using the proof assistant PVS (Prototype Verification System). Throughout this effort, NASA has amassed a library of tens of thousands of proven lemmas. While these lemmas can often be applied to new problems, their abundance can make lemma selection a non-trivial task. This project focuses on creating a lemma selector for use in PVS based on existing systems MePo, MaSh, and MeSh, which were written for other proof assistants. An initial benchmark system makes selections based on symbol-level similarity while the final lemma selector is a hybrid system, combining the classical approach used in the benchmark with a machine learning approach which leverages the lemmas' past usage.

Connor T Baumler↗

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 NTRS2001

A Scalable Analysis Toolkit

The Scalable Analysis Toolkit (SAT) project aimed to demonstrate that it is feasible and useful to statically detect software bugs in very large systems. The technical focus of the project was on a relatively new class of constraint-based techniques for analysis software, where the desired facts about programs (e.g., the presence of a particular bug) are phrased as constraint problems to be solved. At the beginning of this project, the most successful forms of formal software analysis were limited forms of automatic theorem proving (as exemplified by the analyses used in language type systems and optimizing compilers), semi-automatic theorem proving for full verification, and model checking. With a few notable exceptions these approaches had not been demonstrated to scale to software systems of even 50,000 lines of code. Realistic approaches to large-scale software analysis cannot hope to make every conceivable formal method scale. Thus, the SAT approach is to mix different methods in one application by using coarse and fast but still adequate methods at the largest scales, and reserving the use of more precise but also more expensive methods at smaller scales for critical aspects (that is, aspects critical to the analysis problem under consideration) of a software system. The principled method proposed for combining a heterogeneous collection of formal systems with different scalability characteristics is mixed constraints. This idea had been used previously in small-scale applications with encouraging results: using mostly coarse methods and narrowly targeted precise methods, useful information (meaning the discovery of bugs in real programs) was obtained with excellent scalability.

Aiken, Alexander↗

NASA NTRSDate not supplied

Formal Methods in the Air

This is an overview of some of the successes of the Formal Methods team at NASA Langley. It includes discussion of the development of the Well-Clear definition for uncrewed aircraft and the subsequent creation of the DAIDALUS Detect and Avoid library, followed by discussion of the team's verification of the Compact Position Reporting algorithm, which led to the development of tools for floating-point analysis.

Formal Methods↗

NASA NTRS2013

Final Report - Regulatory Considerations for Adaptive Systems

This report documents the findings of a preliminary research study into new approaches to the software design assurance of adaptive systems. We suggest a methodology to overcome the software validation and verification difficulties posed by the underlying assumption of non-adaptive software in the requirementsbased- testing verification methods in RTCA/DO-178B and C. An analysis of the relevant RTCA/DO-178B and C objectives is presented showing the reasons for the difficulties that arise in showing satisfaction of the objectives and suggested additional means by which they could be satisfied. We suggest that the software design assurance problem for adaptive systems is principally one of developing correct and complete high level requirements and system level constraints that define the necessary system functional and safety properties to assure the safe use of adaptive systems. We show how analytical techniques such as model based design, mathematical modeling and formal or formal-like methods can be used to both validate the high level functional and safety requirements, establish necessary constraints and provide the verification evidence for the satisfaction of requirements and constraints that supplements conventional testing. Finally the report identifies the follow-on research topics needed to implement this methodology.

Wilkinson, Chris↗

NASA NTRS2003

Automated Environment Generation for Software Model Checking

A key problem in model checking open systems is environment modeling (i.e., representing the behavior of the execution context of the system under analysis). Software systems are fundamentally open since their behavior is dependent on patterns of invocation of system components and values defined outside the system but referenced within the system. Whether reasoning about the behavior of whole programs or about program components, an abstract model of the environment can be essential in enabling sufficiently precise yet tractable verification. In this paper, we describe an approach to generating environments of Java program fragments. This approach integrates formally specified assumptions about environment behavior with sound abstractions of environment implementations to form a model of the environment. The approach is implemented in the Bandera Environment Generator (BEG) which we describe along with our experience using BEG to reason about properties of several non-trivial concurrent Java programs.

Tkachuk, Oksana↗

DOE OSTI2025

Orthogonality broadcasting and quantum position verification

The no-cloning theorem leads to information-theoretic security in various quantum cryptographic protocols. However, this security typically derives from a possibly weaker property that classical information encoded in certain quantum states cannot be broadcast. To formally capture this property, we introduce the study of ‘orthogonality broadcasting.’ When attempting to broadcast the orthogonality of two different qubit bases, we establish that the power of classical and quantum communication is equivalent. However, quantum communication is shown to be strictly more powerful for broadcasting orthogonality in higher dimensions. We then relate orthogonality broadcasting to quantum position verification and provide a new method for establishing error bounds in the no pre-shared entanglement model that can address protocols previous methods could not. Our key technical contribution is an uncertainty relation that uses the geometric relation of the states that undergo broadcasting rather than the non-commutative aspect of the final measurements.

quantum cryptography↗

NASA NTRS1990

Expert system verification and validation study. Delivery 1: Survey and interview questions

The NASA funded questionnaire is presented to help define the state-of-the-practice in the formal evaluation of Expert Systems on current NASA and industry applications. The answers to this questionnaire, together with follow-up interviews, will provide realistic answers to the following questions: (1) How much evaluation is being performed; (2) What evaluation techniques are in use; and (3) What, if any, are the unique issues in evaluating Expert Systems.

Source record↗

NASA NTRS2015

Real-Time Kennedy Space Center and Cape Canaveral Air Force Station High-Resolution Model Implementation and Verification

Customer: NASA's Launch Services Program (LSP), Ground Systems Development and Operations (GSDO), and Space Launch System (SLS) programs. NASA's LSP, GSDO, SLS and other programs at Kennedy Space Center (KSC) and Cape Canaveral Air Force Station (CCAFS) use the daily and weekly weather forecasts issued by the 45th Weather Squadron (45 WS) as decision tools for their day-to-day and launch operations on the Eastern Range (ER). For example, to determine if they need to limit activities such as vehicle transport to the launch pad, protect people, structures or exposed launch vehicles given a threat of severe weather, or reschedule other critical operations. The 45 WS uses numerical weather prediction models as a guide for these weather forecasts, particularly the Air Force Weather Agency (AFWA) 1.67 kilometer Weather Research and Forecasting (WRF) model. Considering the 45 WS forecasters' and Launch Weather Officers' (LWO) extensive use of the AFWA model, the 45 WS proposed a task at the September 2013 Applied Meteorology Unit (AMU) Tasking Meeting requesting the AMU verify this model. Due to the lack of archived model data available from AFWA, verification is not yet possible. Instead, the AMU proposed to implement and verify the performance of an ER version of the AMU high-resolution WRF Environmental Modeling System (EMS) model (Watson 2013) in real-time. The tasking group agreed to this proposal; therefore the AMU implemented the WRF-EMS model on the second of two NASA AMU modeling clusters. The model was set up with a triple-nested grid configuration over KSC/CCAFS based on previous AMU work (Watson 2013). The outer domain (D01) has 12-kilometer grid spacing, the middle domain (D02) has 4-kilometer grid spacing, and the inner domain (D03) has 1.33-kilometer grid spacing. The model runs a 12-hour forecast every hour, D01 and D02 domain outputs are available once an hour and D03 is every 15 minutes during the forecast period. The AMU assessed the WRF-EMS 1.33-kilometer domain model performance for the 2014 warm season (May-September). Verification statistics were computed using the Model Evaluation Tools, which compared the model forecasts to observations. The mean error values were close to 0 and the root mean square error values were less than 1.8 for mean sea-level pressure (millibars), temperature (degrees Kelvin), dewpoint temperature (degrees Kelvin), and wind speed (per millisecond), all very small differences between the forecast and observations considering the normal magnitudes of the parameters. The precipitation forecast verification results showed consistent under-forecasting of the precipitation object size. This could be an artifact of calculating the statistics for each hour rather than for the entire 12-hour period. The AMU will continue to generate verification statistics for the 1.33-kilometer WRF-EMS domain as data become available in future cool and warm seasons. More data will produce more robust statistics and reveal a more accurate assessment of model performance. Once the formal task was complete, the AMU conducted additional work to better understand the wind direction results. The results were stratified diurnally and by wind speed to determine what effects the stratifications would have on the model wind direction verification statistics. The results are summarized in the addendum at the end of this report. In addition to verifying the model's performance, the AMU also made the output available in the Advanced Weather Interactive Processing System II (AWIPS II). This allows the 45 WS and AMU staff to customize the model output display on the AMU and Range Weather Operations AWIPS II client computers and conduct real-time subjective analyses. In the future, the AMU will implement an updated version of the WRF-EMS model that incorporates local data assimilation. This model will also run in real-time and be made available in AWIPS II.

Numerical Weather Prediction↗

NASA NTRSDate not supplied

Capturing and Analyzing Requirements with FRET

FRET is an open source tool, developed at NASA Ames, 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. FRET helps users write FRETish requirements both by providing grammar information and examples during editing, but also through English and diagrammatic explanations to clarify subtle semantic issues. For each requirement, FRET automatically produces formalizations and supports interactive simulation of produced formalizations to ensure that they capture user intentions. Through its analysis portal, FRET connects to analysis tools by exporting verification code. Currently FRET connects to (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 also supports the consistency/realizability analysis of requirements for identifying conflicting requirements. In this tutorial, we introduce FRET and learn to speak and analyze FRETish through several examples.

FRET↗

NASA NTRS1999

Position Estimation Verification Testing for the Video Guidance Sensor and Dynamic Overhead Target Simulator

The Video Guidance Sensor, part of the Automated Rendezvous and Capture mechanism, is due to undergo formal qualification testing at Marshall Space Flight Center. Before it undergoes this qualification, a test was needed to verify repeatability of the sensor, and to allow different sensor configurations to be compared. This test was developed at the Flight Robotics Laboratory. The test uses a software script to drive the sensor target to the same position and thus allows sensor runs to be compared. The sensor target is the Dynamic Overhead Target Simulator. The simulator uses encoders as its position indicator. Distance Measuring Device's were used to independently verify the software script, the sensor reading, and the target position. The test area, sensor, and other test equipment are briefly described. The actual data is tabulated and will serve as a baseline for future tests. The software script was found to be adequate for the test. Position repeatability was acceptable for all the equipment. The system test is now ready to be used in formal qualification testing.

Gaines, Joseph↗

NASA NTRS1989

Advanced orbiting systems test-bedding and protocol verification

The Consultative Committee for Space Data Systems (CCSDS) has begun the development of a set of protocol recommendations for Advanced Orbiting Systems (SOS). The AOS validation program and formal definition of AOS protocols are reviewed, and the configuration control of the AOS formal specifications is summarized. Independent implementations of the AOS protocols by NASA and ESA are discussed, and cross-support/interoperability tests which will allow the space agencies of various countries to share AOS communication facilities are addressed.

Noles, James↗

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 NTRS1996

Software Development Technologies for Reactive, Real-Time, and Hybrid Systems

The research is directed towards the design and implementation of a comprehensive deductive environment for the development of high-assurance systems, especially reactive (concurrent, real-time, and hybrid) systems. Reactive systems maintain an ongoing interaction with their environment, and are among the most difficult to design and verify. The project aims to provide engineers with a wide variety of tools within a single, general, formal framework in which the tools will be most effective. The entire development process is considered, including the construction, transformation, validation, verification, debugging, and maintenance of computer systems. The goal is to automate the process as much as possible and reduce the errors that pervade hardware and software development.

Manna, Zohar↗

NASA NTRS2000

Model Checking JAVA Programs Using Java Pathfinder

This paper describes a translator called JAVA PATHFINDER from JAVA to PROMELA, the "programming language" of the SPIN model checker. The purpose is to establish a framework for verification and debugging of JAVA programs based on model checking. This work should be seen in a broader attempt to make formal methods applicable "in the loop" of programming within NASA's areas such as space, aviation, and robotics. Our main goal is to create automated formal methods such that programmers themselves can apply these in their daily work (in the loop) without the need for specialists to manually reformulate a program into a different notation in order to analyze the program. This work is a continuation of an effort to formally verify, using SPIN, a multi-threaded operating system programmed in Lisp for the Deep-Space 1 spacecraft, and of previous work in applying existing model checkers and theorem provers to real applications.

Havelund, Klaus↗

NASA NTRS1996

Verification of IEEE Compliant Subtractive Division Algorithms

A parameterized definition of subtractive floating point division algorithms is presented and verified using PVS. The general algorithm is proven to satisfy a formal definition of an IEEE standard for floating point arithmetic. The utility of the general specification is illustrated using a number of different instances of the general algorithm.

Miner, Paul S.↗

NASA NTRSDate not supplied

An Analysis of Extended Reality Mockups for Use in Verification: Phase 2

NASA commercial providers are increasing their use of Virtual Reality (VR) and Hybrid Reality (HR) technologies in their system development process. The use of these technologies, collectively referred to as Extended Reality (XR) technologies, has been limited to the development phase, but there have been requests to integrate VR and HR mockups into verifications. Verifications require, at minimum, a high-fidelity mockup for activities involving human participation (tests, demonstrations, inspections). HR technology shares many of the strengths but may not share some of the critical shortcomings of VR. Specifically, HR allows for integrating physical objects, such as a suit, which may be critical to evaluating a system. Adopting HR technology still has many of the same challenges as VR. Namely, there is little to no data about the validity of evaluations conducted with HR mockups, an established process, or criteria for evaluating the appropriateness of HR mockups. Because verifications are final and only need to happen once, HR mockups must be adequately vetted before being approved for use in verifications. Further hindering the adoption of these technologies is the lack of consensus on what constitutes a high-fidelity XR mockup. Even for physical mockups, there are guidelines and common criteria, but nothing has been formalized. Discussion about when an XR mockup can be used would be greatly helped by clearly defining what a high-fidelity XR mockup is and how it might be measured. The team will engage with relevant stakeholders to learn more about the benefits and challenges of adopting hybrid reality mockups for verification. The team will build upon work from Phase 1 by maturing a framework to guide decisions for evaluating XR mockups for use in verifications. The team will also conduct experimental studies to evaluate advantages and tradeoffs of hybrid/mixed reality relative to physical and virtual reality mockups. Finally, data from Phase 1 and Phase 2 will be synthesized into a set of best practices for developing and validating XR mockups for verification. We will highlight the work conducted to date in Phase 2. We will present the status of the XR for Verification Framework, a summary of best practices identified thus far, and give a synopsis of future work.

verification testing↗