Engineering Papers⌕ Search

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.

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

At least 451 records · Page 25

First-Order Runtime Verification using BDDs

Runtime Verification (RV) expedites the analyses of execution traces for detecting system errors and for statistical and quality analysis. Having started modestly, with checking temporal properties that are based on propositional (yes/no) values, the current practice of RV often involves properties that are parametrized by the data observed in the input trace. The specifications are based on various formalisms, such as automata, temporal logics, rule systems, and stream processing. Checking execution traces that are data intensive against a specification that imposes strong dependencies between the data, poses a nontrivial challenges; in particular if runtime verification has to be performed online, while many events that carry data appear within small time proximities. Towards achieving this goal, it was recently suggested to represent relations over the observed data values, based on BDDs, where data elements are enumerated and then converted into bit vectors. This representation provided a very simple and natural extension of an RV algorithm from propositional to first-order LTL, but more importantly, was shown to contribute to the memory compactness and to the speed, as was demonstrated using a corresponding implementation. We extend here the capabilities of BDD-based RV with the ability to express timing constraints, where the monitored events include (integer) clock values. We show how to efficiently operate on BDDs that represent both relations on (enumerations of) values and time dependencies, as required by the addition of the time constraints. We demonstrate our algorithm with an efficient implementation and provide experimental results.

Peled, Doron↗

Runtime Verification - 17 Years Later

Runtime verification is the discipline of analyzing program executions using rigorous methods. The discipline covers such topics as specification-based monitoring, where single executions are checked against formal specifications; predictive runtime analysis, where properties about a system are predicted/inferred from single (good) executions; specification mining from execution traces; visualization of execution traces; and to be fully general: computation of any interesting information from execution traces. Finally, runtime verification also includes fault protection, where monitors actively protect a running system against errors. The paper is written as a response to the ‘Test of Time Award’ attributed to the authors for their 2001 paper [45]. The present paper provides a brief overview of what lead to that paper, what has happened since, and some perspectives on the future of the field.

Rosu, Grigore↗

A Temporal Differential Dynamic Logic Formal Embedding

Differential dynamic logic is a formal framework to specify and reason about hybrid programs (HPs). The core of dL is a proof calculus that contains a collection of axioms and rules for the rigorous verification of properties of HPs. Recently, dL has been embedded within the theorem prover Prototype Verification System (PVS) resulting in the tool Plaidypvs2. The integration of dL into PVS expands its expressive power; user defined functions, such as trigonometric and other transcendental functions, can be used inside the dL framework, and meta-reasoning about HPs can be performed, including reasoning about entire classes of HPs, specified using dependent types in PVS. The differential temporal dynamic logic (dTL2) extends dL with temporal logic operators to reason about all the states reachable during the execution of an HP. This paper presents a work in progress focusing on embedding dTL2 in PVS as an extension of Plaidypvs. Plaidypvs is expanded with the formalization of a trace semantics for HPs, the definition of the LTL temporal operators eventually and globally, and the implementation of the proof calculus for dTL2. This new embedding has the same capabilties as Plaidypvs, which allows user defined functions and meta-reasoning of properties of HPs. To the best of the authors’ knowledge this is the first implementation of dTL2.

differential dynamic logic↗

SU-F-T-06: Development of a Formalism for Practical Dose Measurements in Brachytherapy in the German Standard DIN 6803

Purpose: In the steep dose gradients in the vicinity of a radiation source and due to the properties of the changing photon spectra, dose measurements in Brachytherapy usually have large uncertainties. Working group DIN 6803-3 is presently discussing recommendations for practical brachytherapy dosimetry incorporating recent theoretical developments in the description of brachytherapy radiation fields as well as new detectors and phantom materials. The goal is to prepare methods and instruments to verify dose calculation algorithms and for clinical dose verification with reduced uncertainties. Methods: After analysis of the distance dependent spectral changes of the radiation field surrounding brachytherapy sources, the energy dependent response of typical brachytherapy detectors was examined with Monte Carlo simulations. A dosimetric formalism was developed allowing the correction of their energy dependence as function of source distance for a Co-60 calibrated detector. Water equivalent phantom materials were examined with Monte Carlo calculations for their influence on brachytherapy photon spectra and for their water equivalence in terms of generating equivalent distributions of photon spectra and absorbed dose to water. Results: The energy dependence of a detector in the vicinity of a brachytherapy source can be described by defining an energy correction factor kQ for brachytherapy in the same manner as in existing dosimetry protocols which incorporates volume averaging and radiation field distortion by the detector. Solid phantom materials were identified which allow precise positioning of a detector together with small correctable deviations from absorbed dose to water. Recommendations for the selection of detectors and phantom materials are being developed for different measurements in brachytherapy. Conclusion: The introduction of kQ for brachytherapy sources may allow more systematic and comparable dose measurements. In principle, the corrections can be verified or even determined by measurement in a water phantom and comparison with dose distributions calculated using the TG43 dosimetry formalism. Project is supported by DIN Deutsches Institut fuer Normung.

60 APPLIED LIFE SCIENCES↗

Multiscale equatorial electrojet turbulence: Energy conservation, coupling, and cascades in a baseline 2-D fluid model

In this paper, progress in understanding the coupling between plasma instabilities in the equatorial electrojet based on a unified fluid model is reported. Simulations with parameters set to various ionospheric background conditions revealed properties of the gradient-drift and Farley-Buneman instabilities. Notably, sharper density gradients increase linear growth rates at all scales, whereas variations in cross-field E × B drift velocity only affect small-scale instabilities. A formalism defining turbulent fluctuation energy for the system is introduced, and the turbulence is analyzed within this framework. This exercise serves as a useful verification test of the numerical simulations and also elucidates the physics underlying the ionospheric turbulence. Various physical mechanisms involved in the energetics are categorized as sources, sinks, nonlinear transfer, and cross-field coupling. The physics of the nonlinear transfer terms is studied to identify their roles in producing energy cascades, which explain the generation of small-scale structures that are stable in the linear regime. The theory of two-step energy cascading to generate the 3 m plasma irregularities in the equatorial electrojet is verified for the first time in the fluid regime. Finally, in addition, the nonlinearity of the system allows the possibility of an inverse energy cascade, potentially responsible for generating large-scale plasma structures at the top of the electrojet as found in different rocket and radar observations.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Applying Formal Methods to NASA Projects: Transition from Research to Practice

NASA project managers attempt to manage risk by relying on mature, well-understood process and technology when designing spacecraft. In the case of crewed systems, the margin for error is even tighter and leads to risk aversion. But as we look to future missions to the Moon and Mars, the complexity of the systems will increase as the spacecraft and crew work together with less reliance on Earth-based support. NASA will be forced to look for new ways to do business. Formal methods technologies can help NASA develop complex but cost effective spacecraft in many domains, including requirements and design, software development and inspection, and verification and validation of vehicle subsystems. To realize these gains, the technologies must be matured and field-tested so that they are proven when needed. During this discussion, current activities used to evaluate FM technologies for Orion spacecraft design will be reviewed. Also, suggestions will be made to demonstrate value to current designers, and mature the technology for eventual use in safety-critical NASA missions.

Othon, Bill↗

Developing Formal Correctness Properties from Natural Language Requirements

This viewgraph presentation reviews the rationale of the program to transform natural language specifications into formal notation.Specifically, automate generation of Linear Temporal Logic (LTL)correctness properties from natural language temporal specifications. There are several reasons for this approach (1) Model-based techniques becoming more widely accepted, (2) Analytical verification techniques (e.g., model checking, theorem proving) significantly more effective at detecting types of specification design errors (e.g., race conditions, deadlock) than manual inspection, (3) Many requirements still written in natural language, which results in a high learning curve for specification languages, associated tools and increased schedule and budget pressure on projects reduce training opportunities for engineers, and (4) Formulation of correctness properties for system models can be a difficult problem. This has relevance to NASA in that it would simplify development of formal correctness properties, lead to more widespread use of model-based specification, design techniques, assist in earlier identification of defects and reduce residual defect content for space mission software systems. The presentation also discusses: potential applications, accomplishments and/or technological transfer potential and the next steps.

requirements engineering↗

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

Towards Automated Reasoning Chains for Verification of LLM-Generated Scientific Code

With the rise of Large Language Model (LLM) generated code, including in domains like scientific computing, ensuring not only syntactical, but also mathematical correctness, has become a critical task. Traditional formal methods approaches often struggle with the ambiguity of floating-point code, and full symbolic execution is extremely costly and limited. We propose a chain-of-reasoning approach that iteratively lifts basic semantics from code into the SPIRAL system and then establishes numerical equivalency to the desired mathematical operation. Here, we leverage the ample mathematical knowledge already formalized in SPIRAL to enable the system to recognize not just different implementations of the same algorithm but fully separate approaches to solving the given problem. The chain establishes tight error bounds on the output of given code with respect to the true continuous solution it approximates, quantifying all sources of error. We demonstrate this approach by establishing the correctness of a pseudospectral solver for a simple 1-dimensional Poisson problem.

Oschatz, Quentin [Carnegie Mellon University,Pitts↗

Formal Methods Case Studies for DO-333

RTCA DO-333, Formal Methods Supplement to DO-178C and DO-278A provides guidance for software developers wishing to use formal methods in the certification of airborne systems and air traffic management systems. The supplement identifies the modifications and additions to DO-178C and DO-278A objectives, activities, and software life cycle data that should be addressed when formal methods are used as part of the software development process. This report presents three case studies describing the use of different classes of formal methods to satisfy certification objectives for a common avionics example - a dual-channel Flight Guidance System. The three case studies illustrate the use of theorem proving, model checking, and abstract interpretation. The material presented is not intended to represent a complete certification effort. Rather, the purpose is to illustrate how formal methods can be used in a realistic avionics software development project, with a focus on the evidence produced that could be used to satisfy the verification objectives found in Section 6 of DO-178C.

Cofer, Darren↗

Systematic Benchmarking of Diagnostic Technologies for an Electrical Power System

Automated health management is a critical functionality for complex aerospace systems. A wide variety of diagnostic algorithms have been developed to address this technical challenge. Unfortunately, the lack of support to perform large-scale V&V (verification and validation) of diagnostic technologies continues to create barriers to effective development and deployment of such algorithms for aerospace vehicles. In this paper, we describe a formal framework developed for benchmarking of diagnostic technologies. The diagnosed system is the Advanced Diagnostics and Prognostics Testbed (ADAPT), a real-world electrical power system (EPS), developed and maintained at the NASA Ames Research Center. The benchmarking approach provides a systematic, empirical basis to the testing of diagnostic software and is used to provide performance assessment for different diagnostic algorithms.

Kurtoglu, Tolga↗

SU-F-BRE-01: A Rapid Method to Determine An Upper Limit On a Radiation Detector's Correction Factor During the QA of IMRT Plans

Purpose: Discrepancies in the verification of the absorbed dose to water from an IMRT plan using a radiation dosimeter can be wither caused by 1) detector specific nonstandard field correction factors as described by the formalism of Alfonso et al. 2) inaccurate delivery of the DQA plan. The aim of this work is to develop a simple/fast method to determine an upper limit on the contribution of composite field correction factors to these discrepancies. Methods: Indices that characterize the non-flatness of the symmetrised collapsed delivery (VSC) of IMRT fields over detector-specific regions of interest were shown to be correlated with IMRT field correction factors. The indices introduced are the uniformity index (UI) and the mean fluctuation index (MF). Each one of these correlation plots have 10 000 fields generated with a stochastic model. A total of eight radiation detectors were investigated in the radial orientation. An upper bound on the correction factors was evaluated by fitting values of high correction factors for a given index value. Results: These fitted curves can be used to compare the performance of radiation dosimeters in composite IMRT fields. Highly water-equivalent dosimeters like the scintillating detector (Exradin W1) and a generic alanine detector have been found to have corrections under 1% over a broad range of field modulations (0 – 0.12 for MF and 0 – 0.5 for UI). Other detectors have been shown to have corrections of a few percent over this range. Finally, a full Monte Carlo simulations of 18 clinical and nonclinical IMRT field showed good agreement with the fitted curve for the A12 ionization chamber. Conclusion: This work proposes a rapid method to evaluate an upper bound on the contribution of correction factors to discrepancies found in the verification of DQA plans.

07 ISOTOPE AND RADIATION SOURCES↗

Theorem Proving in Intel Hardware Design

For the past decade, a framework combining model checking (symbolic trajectory evaluation) and higher-order logic theorem proving has been in production use at Intel. Our tools and methodology have been used to formally verify execution cluster functionality (including floating-point operations) for a number of Intel products, including the Pentium(Registered TradeMark)4 and Core(TradeMark)i7 processors. Hardware verification in 2009 is much more challenging than it was in 1999 - today s CPU chip designs contain many processor cores and significant firmware content. This talk will attempt to distill the lessons learned over the past ten years, discuss how they apply to today s problems, outline some future directions.

O'Leary, John↗

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↗

Quantitative Analysis Guidance in Safety Software Validation

Quantitative analysis in software development has been a challenging topic over the years in safety software. While qualitative processes for vigorous safety software verification and validation (V and V) have been provided through standard such as IEEE 1012, quantitative analysis for V and V tasks such as correctness, completeness or accuracy evaluation have not been formally defined. In practice, there are quantitative analyses in terms of using software metrics. Many of these software metrics are useful in analyzing the test results. Some of them are used for providing guidance in code evaluation activities e.g. numbers of line of codes not exceeding certain limits, recursive calls are not allowed, etc. However, few can be used for providing quantitative analysis guidance for the V and V tasks such as completeness evaluation. AREVA Federal Services (AFS) has provided services for many nuclear projects in US. Through compliance with IEEE 1012, AFS V and V processes have provided vigorous qualitative processes ensuring quality level of the software products used in the project meeting the required nuclear software level. In addition, quantitative analysis is developed to provide structured validation framework ensuring 'zero defect' in the software products. This paper describes some aspects of the quantitative approaches using a sample safety application. (authors)

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Synthesizing Certified Code

Code certification is a lightweight approach to demonstrate software quality on a formal level. Its basic idea is to require producers to provide formal proofs that their code satisfies certain quality properties. These proofs serve as certificates which can be checked independently. Since code certification uses the same underlying technology as program verification, it also requires many detailed annotations (e.g., loop invariants) to make the proofs possible. However, manually adding theses annotations to the code is time-consuming and error-prone. We address this problem by combining code certification with automatic program synthesis. We propose an approach to generate simultaneously, from a high-level specification, code and all annotations required to certify generated code. Here, we describe a certification extension of AUTOBAYES, a synthesis tool which automatically generates complex data analysis programs from compact specifications. AUTOBAYES contains sufficient high-level domain knowledge to generate detailed annotations. This allows us to use a general-purpose verification condition generator to produce a set of proof obligations in first-order logic. The obligations are then discharged using the automated theorem E-SETHEO. We demonstrate our approach by certifying operator safety for a generated iterative data classification program without manual annotation of the code.

Whalen, Michael↗