Proof or Consequences the Verification of Curiosity's Software
No abstract available
logic model checking↗
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.
Statistical Symbolic Execution with Informed Sampling
Symbolic execution techniques have been proposed recently for the probabilistic analysis of programs. These techniques seek to quantify the likelihood of reaching program events of interest, e.g., assert violations. They have many promising applications but have scalability issues due to high computational demand. To address this challenge, we propose a statistical symbolic execution technique that performs Monte Carlo sampling of the symbolic program paths and uses the obtained information for Bayesian estimation and hypothesis testing with respect to the probability of reaching the target events. To speed up the convergence of the statistical analysis, we propose Informed Sampling, an iterative symbolic execution that first explores the paths that have high statistical significance, prunes them from the state space and guides the execution towards less likely paths. The technique combines Bayesian estimation with a partial exact analysis for the pruned paths leading to provably improved convergence of the statistical analysis. We have implemented statistical symbolic execution with in- formed sampling in the Symbolic PathFinder tool. We show experimentally that the informed sampling obtains more precise results and converges faster than a purely statistical analysis and may also be more efficient than an exact symbolic analysis. When the latter does not terminate symbolic execution with informed sampling can give meaningful results under the same time and memory limits.
Reliability↗
Assume-Guarantee Abstraction Refinement Meets Hybrid Systems
Compositional verification techniques in the assume- guarantee style have been successfully applied to transition systems to efficiently reduce the search space by leveraging the compositional nature of the systems under consideration. We adapt these techniques to the domain of hybrid systems with affine dynamics. To build assumptions we introduce an abstraction based on location merging. We integrate the assume-guarantee style analysis with automatic abstraction refinement. We have implemented our approach in the symbolic hybrid model checker SpaceEx. The evaluation shows its practical potential. To the best of our knowledge, this is the first work combining assume-guarantee reasoning with automatic abstraction-refinement in the context of hybrid automata.
Reliability↗
Spot: A Programming Language for Verified Flight Software
The C programming language is widely used for programming space flight software and other safety-critical real time systems. C, however, is far from ideal for this purpose: as is well known, it is both low-level and unsafe. This paper describes Spot, a language derived from C for programming space flight systems. Spot aims to maintain compatibility with existing C code while improving the language and supporting verification with the SPIN model checker. The major features of Spot include actor-based concurrency, distributed state with message passing and transactional updates, and annotations for testing and verification. Spot also supports domain-specific annotations for managing spacecraft state, e.g., communicating telemetry information to the ground. We describe the motivation and design rationale for Spot, give an overview of the design, provide examples of Spot's capabilities, and discuss the current status of the implementation.
validation↗
Automated Analysis of Stateflow Models
Stateflow is a widely used modeling framework for embedded and cyber physical systems where control software interacts with physical processes. In this work, we present a framework a fully automated safety verification technique for Stateflow models. Our approach is two-folded: (i) we faithfully compile Stateflow models into hierarchical state machines, and (ii) we use automated logic-based verification engine to decide the validity of safety properties. The starting point of our approach is a denotational semantics of State flow. We propose a compilation process using continuation-passing style (CPS) denotational semantics. Our compilation technique preserves the structural and modal behavior of the system. The overall approach is implemented as an open source toolbox that can be integrated into the existing Mathworks Simulink Stateflow modeling framework. We present preliminary experimental evaluations that illustrate the effectiveness of our approach in code generation and safety verification of industrial scale Stateflow models.
Stateflow↗
Formalizing and Analyzing Requirements with FRET
Formal verification and simulation are powerful tools to validate requirements against complex systems. Requirements are developed in early stages of the software lifecycle and are typically written in ambiguous natural language. There is a gap between such requirements and formal notations that can be used by verification tools, and lack of support for proper association of requirements with software artifacts for verification. We propose to write requirements in an intuitive, structured natural language with formal semantics, and to support formalization and model/code verification as a smooth, well-integrated process. To this end, we have developed an end-to-end, open source requirements analysis framework that checks Simulink models against requirements written structured natural language.
Mavridou, Anastasia↗
A Flexible Statechart-to-model-checker Translator
Many current-day software design tools offer some variant of statechart notation for system specification. We, like others, have built an automatic translator from (a subset of) statecharts to a model checker, for use to validate behavioral requirements.
statecharts↗
Safety and Certification in Increasingly Autonomous Aviation Systems
Explore the source record for details and available documents.
System Safety↗
Automated Verification of Programmable Logic Controller Programs Against Structured Natural Language Requirements
PLCverif is an actively developed project at CERN, enabling the formal verification of Programmable Logic Controller (PLC) programs in critical systems. In this paper, we present our work on improving the formal requirements specification experience in PLCverif through the use of natural language. To this end, we integrate NASA’s FRET, a formal requirement elicitation and authoring tool, into PLCverif. FRET is used to specify formal requirements in structured natural language, which automatically translates into temporal logic formulae. FRET’s output is then directly used by PLCverif for verification purposes. We discuss practical challenges that PLCverif users face when authoring requirements and the FRET features that help alleviate these problems. We present the new requirement formalization workflow and report our experience using it on two critical CERN case studies.
formal methods↗
Trustworthy Autonomy for Gateway Vehicle System Manager
The Vehicle System Manager (VSM) is the highest-level software control system in the Gateway hierarchical Autonomous System Management Architecture. The VSM provides four function categories: Mission Management and Timeline Execution, Resource Management, Fault Management, Vehicle Control and Operation. VSM provides various levels of automation ranging from fully autonomous operations with no flight crew and minimal ground monitoring to advisory automation when Gateway is crewed and has full ground monitoring. Trustworthiness is achieved via verified specification, comprehensive development verification, and real-time verification using assume-guarantee contracts. Development verification includes semantic verification of the data model via peer review and testing and assume-guarantee contracts implemented using the PlusCal/TLA+ environment. VSM also uses runtime assume-guarantee contracts, implemented in R2U2 via a runtime monitor that feeds the necessary telemetry data to R2U2 and which receives and responds to the R2U2 verdict stream. The full lifecycle verification approach and use of assume-guarantee contracts provides increased trustworthiness to VSM. Preliminary results provide encouragement that VSM can be both autonomous and trustworthy.
Assume-guarantee contracts↗
Preliminary Application of Formal Verification to An Autonomy Architecture for Unmanned Aircraft
There is a desire to design autonomous systems in such a way that capabilities can be easily added or re- combined to produce new behaviors while preserving their safety properties. ICAROUS, a prototype software architecture for building safety-centric autonomous unmanned aircraft applications, is designed to support this type of extensibility and re-configurability. In ICAROUS, core capabilities are implemented as individual soft- ware services, so that enabling access to new capabilities simply requires adding new services. To make use of these capabilities, ICAROUS includes a specialized service that provides a general framework for config- uring the relative priorities, conditions, and rules that govern how different modules should be engaged and disengaged during flight. The inherent complexity of coordinating multiple modules under changing conditions makes it difficult to determine whether a particular configuration could have erroneous behaviors in certain circumstances. A robust set of integration tests can help discover errors, but testing can only realistically cover a relatively small proportion of total system behaviors. Developing good tests and interpreting the results to pinpoint the cause of errors when they arise can also be very time-consuming. To supplement testing, formal methods can be used to model and analyze complex systems, achieving better coverage and simplifying the process of finding, understanding, and fixing errors. To demonstrate these benefits, this paper explores the ap- plication of formal methods to ICAROUS. In particular, the Spin model checker is used to specify requirements for and model portions of the system, then verify whether the model satisfies the requirements and find and fix errors when it does not.
Formal Methods↗
Preliminary Application of Formal Verification to An Autonomy Architecture for Unmanned Aircraft
There is a desire to design autonomous systems in such a way that capabilities can be easily added or re-combined to produce new behaviors while preserving their safety properties. ICAROUS, a prototype software architecture for building safety-centric autonomous unmanned aircraft applications, is designed to support this type of extensibility and re-configurability. In ICAROUS, core capabilities are implemented as individual soft- ware services, so that enabling access to new capabilities simply requires adding new services. To make use of these capabilities, ICAROUS includes a specialized service that provides a general framework for config- uring the relative priorities, conditions, and rules that govern how different modules should be engaged and disengaged during flight. The inherent complexity of coordinating multiple modules under changing conditions makes it difficult to determine whether a particular configuration could have erroneous behaviors in certain circumstances. A robust set of integration tests can help discover errors, but testing can only realistically cover a relatively small proportion of total system behaviors. Developing good tests and interpreting the results to pinpoint the cause of errors when they arise can also be very time-consuming. To supplement testing, formal methods can be used to model and analyze complex systems, achieving better coverage and simplifying the process of finding, understanding, and fixing errors. To demonstrate these benefits, this paper explores the ap- plication of formal methods to ICAROUS. In particular, the Spin model checker is used to specify requirements for and model portions of the system, then verify whether the model satisfies the requirements and find and fix errors when it does not.
Formal Methods↗
Applicability of Developed Calculation Models to Predict Long-term Behavior of Metal Seals - Necessary Scope of Tests - 19311
The long-term sealing behavior of metal seals, assembled in the lid system of casks for transportation and storage of radioactive materials, has been investigated. For that purpose, phenomenological models describing the time- and temperature dependent behavior have been introduced by BAM since 2016, e.g. by using the time-temperature superposition principle. Results have shown that these models describe the relaxation behavior adequately and are suitable for extrapolations. In this work, the applicability of these models is checked by analyzing the necessary scope of tests, which must be carried out to get sufficient information about the long-term behavior of metal seals based on short-term tests. (authors)
12 MANAGEMENT OF RADIOACTIVE AND NON-RADIOACTIVE W↗
Three-dimensional computer model for the atmospheric general circulation experiment
An efficient, flexible, three-dimensional, hydrodynamic, computer code has been developed for a spherical cap geometry. The code will be used to simulate NASA's Atmospheric General Circulation Experiment (AGCE). The AGCE is a spherical, baroclinic experiment which will model the large-scale dynamics of our atmosphere; it has been proposed to NASA for future Spacelab flights. In the AGCE a radial dielectric body force will simulate gravity, with hot fluid tending to move outwards. In order that this force be dominant, the AGCE must be operated in a low gravity environment such as Spacelab. The full potential of the AGCE will only be realized by working in conjunction with an accurate computer model. Proposed experimental parameter settings will be checked first using model runs. Then actual experimental results will be compared with the model predictions. This interaction between experiment and theory will be very valuable in determining the nature of the AGCE flows and hence their relationship to analytical theories and actual atmospheric dynamics.
Roberts, G. O.↗
Learning an Eddy Viscosity Model Using Shrinkage and Bayesian Calibration: A Jet-in-Crossflow Case Study
In this paper, we demonstrate a statistical procedure for learning a high-order eddy viscosity model (EVM) from experimental data and using it to improve the predictive skill of a Reynolds-averaged Navier–Stokes (RANS) simulator. The method is tested in a three-dimensional (3D), transonic jet-in-crossflow (JIC) configuration. The process starts with a cubic eddy viscosity model (CEVM) developed for incompressible flows. It is fitted to limited experimental JIC data using shrinkage regression. The shrinkage process removes all the terms from the model, except an intercept, a linear term, and a quadratic one involving the square of the vorticity. The shrunk eddy viscosity model is implemented in an RANS simulator and calibrated, using vorticity measurements, to infer three parameters. The calibration is Bayesian and is solved using a Markov chain Monte Carlo (MCMC) method. A 3D probability density distribution for the inferred parameters is constructed, thus quantifying the uncertainty in the estimate. The phenomenal cost of using a 3D flow simulator inside an MCMC loop is mitigated by using surrogate models (“curve-fits”). A support vector machine classifier (SVMC) is used to impose our prior belief regarding parameter values, specifically to exclude nonphysical parameter combinations. The calibrated model is compared, in terms of its predictive skill, to simulations using uncalibrated linear and CEVMs. Finally, we find that the calibrated model, with one quadratic term, is more accurate than the uncalibrated simulator. The model is also checked at a flow condition at which the model was not calibrated.
42 ENGINEERING↗
Synthesis of Correct Digital Controller Models from Specifications by Model Transformation (21-0320)
The design of high consequence controllers (in weapons systems, autonomy, etc.) that do what they are supposed to do is a significant challenge. Testing simply does not come close to meeting the requirements for assurance. Today circuit designers at Sandia (and elsewhere) typically capture the core behavior of their components using state models in tools such as STATEFLOW. They then check that their models meet certain requirements (e.g. “The system bus must not deadlock” or “both traffic lights at an intersection must not be green at the same time”) using tools called model checkers. If the model checker returns “yes” then the property is guaranteed to be satisfied by the model. However, there are several drawbacks to this industry practice: (1) there is a lot of detail to get right, this is particularly challenging when there are multiple components requiring complex coordination (2) any errors returned by the model checker have to be traced back through the design and fixed, necessitating rework, (3) there are severe scalability problems with this approach, particularly when dealing with concurrency. All this places high demands on the designers who now face not only an accelerated schedule but also controllers of increasing complexity. This report describes a new and fundamentally different approach to the construction of safety-critical digital controllers. Instead of directly constructing a complete model and then trying to verify it, the designer can start with an initial abstract (think “sketch”) model plus the requirements, from which a correct concrete model is automatically synthesized. There is no need for post-hoc verification of required functional properties. Having tool to carry this out will significantly impact the nation’s ability to ensure the safety of high-consequence digital systems. The approach has been implemented in a prototype tool, along with a suite of examples, including ones that reflect actual problems faced by designers. Our approach operates on a variant of Statecharts developed at Sandia called Qspecs. Statecharts are a widely used formalism for developing concurrent reactive systems, supporting scalability through allowing state models containing composite states, which are the serial or parallel composition of substates which can themselves contain statecharts. Statecharts enable an incremental style of development, in which states are progressively refined to incorporate greater detail in an incremental model of software development. Our approach formulates a set of constraints from the structure of the models and the requirements and propagates these constraints to a fixpoint. The solution to the constraints is an inductive invariant along with guards on the transitions. We also show how our approach extends to implementation refinement, decomposition, composition, and elaboration. We currently handle safety requirements written in LTL (Linear Temporal Logic)
42 ENGINEERING↗
Updraft Model for Development of Autonomous Soaring Uninhabited Air Vehicles
Large birds and glider pilots commonly use updrafts caused by convection in the lower atmosphere to extend flight duration, increase cross-country speed, improve range, or simply to conserve energy. Uninhabited air vehicles may also have the ability to exploit updrafts to improve performance. An updraft model was developed at NASA Dryden Flight Research Center (Edwards, California) to investigate the use of convective lift for uninhabited air vehicles in desert regions. Balloon and surface measurements obtained at the National Oceanic and Atmospheric Administration Surface Radiation station (Desert Rock, Nevada) enabled the model development. The data were used to create a statistical representation of the convective velocity scale, w*, and the convective mixing-layer thickness, zi. These parameters were then used to determine updraft size, vertical velocity profile, spacing, and maximum height. This paper gives a complete description of the updraft model and its derivation. Computer code for running the model is also given in conjunction with a check case for model verification.
Allen, Michael J.↗
SU-E-T-272: Direct Verification of a Treatment Planning System Megavoltage Linac Beam Photon Spectra Models, and Analysis of the Effects On Patient Plans
Purpose: For the photon dose calculation Philips Pinnacle Treatment Planning System (TPS) uses collapsed cone convolution algorithm, which relies on energy spectrum of the beam in computing the scatter component. The spectrum is modeled based on Linac’s standard commissioning data and typically is not independently verified. We explored a methodology of using transmission measurements in combination with regularization data processing to unfold Linac spectra. The measured spectra were compared to those modeled by the TPS, and the effect on patient plans was evaluated. Methods: Transmission measurements were conducted in narrow-beam geometry using a standard Farmer ionization chamber. Two attenuating materials and two build -up caps, having different atomic numbers, served to enhance discrimination between absorption of low and high-energy portions of the spectra, thus improving the accuracy of the results. The data was analyzed using a regularization technique implemented through spreadsheet-based calculations. Results: The unfolded spectra were found to deviate from the TPS beam models. The effect of such deviations on treatment planning was evaluated for patient plans through dose distribution calculations with either TPS modeled or measured energy spectra. The differences were reviewed through comparison of isodose distributions, and quantified based on maximum dose values for critical structures. While in most cases no drastic differences in the calculated doses were observed, plans with deviations of 4 to 8% in the maximum dose values for critical structures were discovered. The anatomical sites with large scatter contributions are the most vulnerable to inaccuracies in the modeled spectrum. Conclusion: An independent check of the TPS model spectrum is highly desirable and should be included as part of commissioning of a new Linac. The effect is particularly important for dose calculations in high heterogeneity regions. The developed approach makes acquisition of megavoltage Linac beam spectra achievable in a typical radiation oncology clinic.
60 APPLIED LIFE SCIENCES↗