Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “model checking”

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 145 records · Page 8
All sourcesNASA NTRSDOE OSTI
NASA NTRS2000

Verification and Validation of Autonomy Software at NASA

Autonomous software holds the promise of new operation possibilities, easier design and development, and lower operating costs. However, as those system close control loops and arbitrate resources on-board with specialized reasoning, the range of possible situations becomes very large and uncontrollable from the outside, making conventional scenario-based testing very inefficient. Analytic verification and validation (V&V) techniques, and model checking in particular, can provide significant help for designing autonomous systems in a more efficient and reliable manner, by providing a better coverage and allowing early error detection. This article discusses the general issue of V&V of autonomy software, with an emphasis towards model-based autonomy, model-checking techniques, and concrete experiments at NASA.

Pecheur, Charles↗
NASA NTRS2000

Verification and Validation of Autonomy Software at NASA

Autonomous software holds the promise of new operation possibilities, easier design and development and lower operating costs. However, as those system close control loops and arbitrate resources on board with specialized reasoning, the range of possible situations becomes very large and uncontrollable from the outside, making conventional scenario-based testing very inefficient. Analytic verification and validation (V&V) techniques, and model checking in particular, can provide significant help for designing autonomous systems in a more efficient and reliable manner, by providing a better coverage and allowing early error detection. This article discusses the general issue of V&V of autonomy software, with an emphasis towards model-based autonomy, model-checking techniques and concrete experiments at NASA.

Pecheur, Charles↗
NASA NTRS2004

Abstraction and Assume-Guarantee Reasoning for Automated Software Verification

Compositional verification and abstraction are the key techniques to address the state explosion problem associated with model checking of concurrent software. A promising compositional approach is to prove properties of a system by checking properties of its components in an assume-guarantee style. This article proposes a framework for performing abstraction and assume-guarantee reasoning of concurrent C code in an incremental and fully automated fashion. The framework uses predicate abstraction to extract and refine finite state models of software and it uses an automata learning algorithm to incrementally construct assumptions for the compositional verification of the abstract models. The framework can be instantiated with different assume-guarantee rules. We have implemented our approach in the COMFORT reasoning framework and we show how COMFORT out-performs several previous software model checking approaches when checking safety properties of non-trivial concurrent programs.

Chaki, S.↗
NASA NTRS2002

Learning Assumptions for Compositional Verification

Compositional verification is a promising approach to addressing the state explosion problem associated with model checking. One compositional technique advocates proving properties of a system by checking properties of its components in an assume-guarantee style. However, the application of this technique is difficult because it involves non-trivial human input. This paper presents a novel framework for performing assume-guarantee reasoning in an incremental and fully automated fashion. To check a component against a property, our approach generates assumptions that the environment needs to satisfy for the property to hold. These assumptions are then discharged on the rest of the system. Assumptions are computed by a learning algorithm. They are initially approximate, but become gradually more precise by means of counterexamples obtained by model checking the component and its environment, alternately. This iterative process may at any stage conclude that the property is either true or false in the system. We have implemented our approach in the LTSA tool and applied it to the analysis of a NASA system.

Cobleigh, Jamieson M.↗
NASA NTRS2011

Automated Verification of Specifications with Typestates and Access Permissions

We propose an approach to formally verify Plural specifications based on access permissions and typestates, by model-checking automatically generated abstract state-machines. Our exhaustive approach captures all the possible behaviors of abstract concurrent programs implementing the specification. We describe the formal methodology employed by our technique and provide an example as proof of concept for the state-machine construction rules. The implementation of a fully automated algorithm to generate and verify models, currently underway, provides model checking support for the Plural tool, which currently supports only program verification via data flow analysis (DFA).

Siminiceanu, Radu I.↗
NASA NTRS2008

Automated Assume-Guarantee Reasoning by Abstraction Refinement

Current automated approaches for compositional model checking in the assume-guarantee style are based on learning of assumptions as deterministic automata. We propose an alternative approach based on abstraction refinement. Our new method computes the assumptions for the assume-guarantee rules as conservative and not necessarily deterministic abstractions of some of the components, and refines those abstractions using counter-examples obtained from model checking them together with the other components. Our approach also exploits the alphabets of the interfaces between components and performs iterative refinement of those alphabets as well as of the abstractions. We show experimentally that our preliminary implementation of the proposed alternative achieves similar or better performance than a previous learning-based implementation.

Pasareanu, Corina S.↗
NASA NTRS1991

Controlling state explosion during automatic verification of delay-insensitive and delay-constrained VLSI systems using the POM verifier

Delay-insensitive VLSI systems have a certain appeal on the ground due to difficulties with clocks; they are even more attractive in space. We answer the question, is it possible to control state explosion arising from various sources during automatic verification (model checking) of delay-insensitive systems? State explosion due to concurrency is handled by introducing a partial-order representation for systems, and defining system correctness as a simple relation between two partial orders on the same set of system events (a graph problem). State explosion due to nondeterminism (chiefly arbitration) is handled when the system to be verified has a clean, finite recurrence structure. Backwards branching is a further optimization. The heart of this approach is the ability, during model checking, to discover a compact finite presentation of the verified system without prior composition of system components. The fully-implemented POM verification system has polynomial space and time performance on traditional asynchronous-circuit benchmarks that are exponential in space and time for other verification systems. We also sketch the generalization of this approach to handle delay-constrained VLSI systems.

Probst, D.↗
DOE OSTI2018

Intact Infiltration Model Design Check for E-Area LLWF

A design check will be performed on the infiltration-rate time profile for the intact case for the proposed E-Area Low-Level Waste Facility (LLWF) final closure cap design.

12 MANAGEMENT OF RADIOACTIVE AND NON-RADIOACTIVE W↗
NASA NTRS2001

Verification and Validation of Model-Based Autonomous Systems

This paper presents a three year project (FY99 to FY01) on the verification and validation of model based autonomous systems. The topics include: 1) Project Profile; 2) Model-Based Autonomy; 3) The Livingstone MIR; 4) MPL2SMV; 5) Livingstone to SMV Translation; 6) Symbolic Model Checking; 7) From Livingstone Models to SMV Models; 8) Application In-Situ Propellant Production; 9) Closed-Loop Verification Principle; 10) Livingstone PathFinder (LPF); 11) Publications and Presentations; and 12) Future Directions. This paper is presented in viewgraph form.

Pecheur, Charles↗
NASA NTRS2012

Experience Report: A Do-It-Yourself High-Assurance Compiler

Embedded domain-specific languages (EDSLs) are an approach for quickly building new languages while maintaining the advantages of a rich metalanguage. We argue in this experience report that the "EDSL approach" can surprisingly ease the task of building a high-assurance compiler.We do not strive to build a fully formally-verified tool-chain, but take a "do-it-yourself" approach to increase our confidence in compiler-correctness without too much effort. Copilot is an EDSL developed by Galois, Inc. and the National Institute of Aerospace under contract to NASA for the purpose of runtime monitoring of flight-critical avionics. We report our experience in using type-checking, QuickCheck, and model-checking "off-the-shelf" to quickly increase confidence in our EDSL tool-chain.

Pike, Lee↗
NASA NTRS2010

Decision Engines for Software Analysis Using Satisfiability Modulo Theories Solvers

The area of software analysis, testing and verification is now undergoing a revolution thanks to the use of automated and scalable support for logical methods. A well-recognized premise is that at the core of software analysis engines is invariably a component using logical formulas for describing states and transformations between system states. The process of using this information for discovering and checking program properties (including such important properties as safety and security) amounts to automatic theorem proving. In particular, theorem provers that directly support common software constructs offer a compelling basis. Such provers are commonly called satisfiability modulo theories (SMT) solvers. Z3 is a state-of-the-art SMT solver. It is developed at Microsoft Research. It can be used to check the satisfiability of logical formulas over one or more theories such as arithmetic, bit-vectors, lists, records and arrays. The talk describes some of the technology behind modern SMT solvers, including the solver Z3. Z3 is currently mainly targeted at solving problems that arise in software analysis and verification. It has been applied to various contexts, such as systems for dynamic symbolic simulation (Pex, SAGE, Vigilante), for program verification and extended static checking (Spec#/Boggie, VCC, HAVOC), for software model checking (Yogi, SLAM), model-based design (FORMULA), security protocol code (F7), program run-time analysis and invariant generation (VS3). We will describe how it integrates support for a variety of theories that arise naturally in the context of the applications. There are several new promising avenues and the talk will touch on some of these and the challenges related to SMT solvers. Proceedings

Bjorner, Nikolaj↗
DOE OSTI2023

Formal Experimentation and Analysis of Handheld RFID Readers as a Tool for Nuclear Material Accounting

Commercial, off-the-shelf Radio Frequency Identification (RFID) systems have been successfully deployed for inventory tracking in numerous industries, but their viability in the tracking of complex environments containing nuclear material is less understood. Of primary interest in this setting is a RFID tracking system for nuclear material accounting which can reliably identify as many tags as possible with high accuracy, while also reducing an operator’s exposure to radiation. In this work, we develop a formal statistical approach to identify relevant handheld RFID reader settings which optimize tagging performance. To achieve this goal, we design a full factorial split-plot experiment for a static shelf configuration scene with 50 randomly placed nuclear material containers affixed with RFID tags. We use Bayesian inference to fit a second-order response surface model which expresses the probability of a successful match for each container as a function of the experimental factors. Such effects are allowed to vary across individual containers and the containers’ population in its entirety to estimate overall effects. Uncertainties of estimates and predictions are quantified via their corresponding posterior distributions. Following extensive model checking and validation, the fitted model is used to identify experimental factors which maximize matching probabilities at both the container-level and for the full shelf configuration scene. We also analyze sensitivity of performance to relevant factors.

25 ENERGY STORAGE↗
NASA NTRS2004

Towards Time Automata and Multi-Agent Systems

The design of reactive systems must comply with logical correctness (the system does what it is supposed to do) and timeliness (the system has to satisfy a set of temporal constraints) criteria. In this paper, we propose a global approach for the design of adaptive reactive systems, i.e., systems that dynamically adapt their architecture depending on the context. We use the timed automata formalism for the design of the agents' behavior. This allows evaluating beforehand the properties of the system (regarding logical correctness and timeliness), thanks to model-checking and simulation techniques. This model is enhanced with tools that we developed for the automatic generation of code, allowing to produce very quickly a running multi-agent prototype satisfying the properties of the model.

Hutzler, G.↗
NASA NTRS2003

The HiVy toolset

The HiVy toolset provides model checking for statecharts. This is achieved by translating statechart specifications into the input language of the spin model checker.

model checking statechart translation validation↗
NASA NTRS2009

Model Based Analysis and Test Generation for Flight Software

We describe a framework for model-based analysis and test case generation in the context of a heterogeneous model-based development paradigm that uses and combines Math- Works and UML 2.0 models and the associated code generation tools. This paradigm poses novel challenges to analysis and test case generation that, to the best of our knowledge, have not been addressed before. The framework is based on a common intermediate representation for different modeling formalisms and leverages and extends model checking and symbolic execution tools for model analysis and test case generation, respectively. We discuss the application of our framework to software models for a NASA flight mission.

Pasareanu, Corina S.↗
NASA NTRSDate not supplied

Trustworthy Autonomy for Gateway Vehicle System Manager

This webinar will present techniques for achieving trusted autonomous operations that are being pioneered on the NASA Lunar Gateway Vehicle System Manager (VSM). The challenges of achieving trusted autonomy faced by the VSM project are similar to challenges in underwater autonomous systems. The webinar will describe the overall approach to verification and present in detail the use of design-time (development) assume-guarantee contracts using model checking and runtime (operational) assume-guarantee contracts. The webinar will conclude with a summary of lessons learned to date and future challenges.

Assume-guarantee contracts↗