Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Correctness proofs”

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 73 records · Page 4

Diagnosing a Failed Proof in Fault-Tolerance: A Disproving Challenge Problem

This paper proposes a challenge problem in disproving. We describe a fault-tolerant distributed protocol designed at NASA for use in a fly-by-wire system for next-generation commercial aircraft. An early design of the protocol contains a subtle bug that is highly unlikely to be caught in fault injection testing. We describe a failed proof of the protocol's correctness in a mechanical theorem prover (PVS) with a complex unfinished proof conjecture. We use a model checking suite (SAL) to generate a concrete counterexample to the unproven conjecture to demonstrate the existence of a bug. However, we argue that the effort required in our approach is too high and propose what conditions a better solution would satisfy. We carefully describe the protocol and bug to provide a challenging but feasible case study for disproving research.

Pike, Lee↗

Towards composition of verified hardware devices

Computers are being used where no affordable level of testing is adequate. Safety and life critical systems must find a replacement for exhaustive testing to guarantee their correctness. Through a mathematical proof, hardware verification research has focused on device verification and has largely ignored system composition verification. To address these deficiencies, we examine how the current hardware verification methodology can be extended to verify complete systems.

Schubert, E. Thomas↗

Derivation and experimental verification of clock synchronization theory

The objective of this work is to validate mathematically derived clock synchronization theories and their associated algorithms through experiment. Two theories are considered, the Interactive Convergence Clock Synchronization Algorithm and the Mid-Point Algorithm. Special clock circuitry was designed and built so that several operating conditions and failure modes (including malicious failures) could be tested. Both theories are shown to predict conservative upper bounds (i.e., measured values of clock skew were always less than the theory prediction). Insight gained during experimentation led to alternative derivations of the theories. These new theories accurately predict the clock system's behavior. It is found that a 100% penalty is paid to tolerate worst case failures. It is also shown that under optimal conditions (with minimum error and no failures) the clock skew can be as much as 3 clock ticks. Clock skew grows to 6 clock ticks when failures are present. Finally, it is concluded that one cannot rely solely on test procedures or theoretical analysis to predict worst case conditions. conditions.

INTERACTIVE CONVERGENCE CLOCK↗

An Abstract Interpretation Framework for the Round-Off Error Analysis of Floating-Point Programs

This paper presents an abstract interpretation framework for the round-off error analysis of floating-point programs. This framework defines a parametric abstract analysis that computes, for each combination of ideal and floating-point execution path of the program, a sound over-approximation of the accumulated floating-point round-off error that may occur. In addition, a Boolean expression that characterizes the input values leading to the computed error approximation is also computed. An abstraction on the control flow of the program is proposed to mitigate the explosion of the number of elements generated by the analysis. Additionally, a widening operator is defined to ensure the convergence of recursive functions and loops. An instantiation of this framework is implemented in the prototype tool PRECiSA that generates formal proof certificates stating the correctness of the computed round-off errors.

Titolo, Laura↗

PRECiSA: a static analysis tool for floating-point programs

This presentation introduces PRECiSA, a static analysis framework for analyzing floating-point programs. PRECiSA computes round-off error bounds for a class of floating-point programs, and produces a formal proof certificate of the correctness of these bounds. PRECiSA also has the capability of generating C code which is instrumented to detect unstable branching conditions from a real-number algorithm specification.

Floating-point↗

Dynamic Stability and Gravitational Balancing of Multiple Extended Bodies

Feasibility of a non-invasive compensation scheme was analyzed for precise positioning of a massive extended body in free fall using gravitational forces influenced by surrounding source masses in close proximity. The N-body problem of classical mechanics is a paradigm used to gain insight into the physics of the equivalent N-body problem subject to control forces. The analysis addressed how a number of control masses move around the proof mass so that the proof mass position can be accurately and remotely compensated when exogenous disturbances are acting on it, while its sensitivity to gravitational waves remains unaffected. Past methods to correct the dynamics of the proof mass have considered active electrostatic or capacitive methods, but the possibility of stray capacitances on the surfaces of the proof mass have prompted the investigation of other alternatives, such as the method presented in this paper. While more rigorous analyses of the problem should be carried out, the data show that, by means of a combined feedback and feed-forward control approach, the control masses succeeded in driving the proof mass along the specified trajectory, which implies that the proof mass can, in principle, be balanced via gravitational forces only while external perturbations are acting on it. This concept involves the dynamic stability of a group of massive objects interacting gravitationally under active control, and can apply to drag-free control of spacecraft during missions, to successor gravitational wave space borne sensors, or to any application requiring flying objects to be precisely controlled in position and attitude relative to another body via gravitational interactions only.

Quadrelli, Marco↗

Synthesizing Safety Conditions for Code Certification Using Meta-Level Programming

In code certification the code consumer publishes a safety policy and the code producer generates a proof that the produced code is in compliance with the published safety policy. In this paper, a novel viewpoint approach towards an implementational re-use oriented framework for code certification is taken. It adopts ingredients from Necula's approach for proof-carrying code, but in this work safety properties can be analyzed on a higher code level than assembly language instructions. It consists of three parts: (1) The specification language is extended to include generic pre-conditions that shall ensure safety at all states that can be reached during program execution. Actual safety requirements can be expressed by providing domain-specific definitions for the generic predicates which act as interface to the environment. (2) The Floyd-Hoare inductive assertion method is refined to obtain proof rules that allow the derivation of the proof obligations in terms of the generic safety predicates. (3) A meta-interpreter is designed and experimentally implemented that enables automatic synthesis of proof obligations for submitted programs by applying the modified Floyd-Hoare rules. The proof obligations have two separate conjuncts, one for functional correctness and another for the generic safety obligations. Proof of the generic obligations, having provided the actual safety definitions as context, ensures domain-specific safety of program execution in a particular environment and is simpler than full program verification.

Eusterbrock, Jutta↗

Elastic Properties in Tension and Shear of High Strength Nonferrous Metals and Stainless Steel - Effect of Previous Deformation and Heat Treatment

A resume is given of an investigation of the influence of plastic deformation and of annealing temperature on the tensile and shear elastic properties of high strength nonferrous metals and stainless steels in the form of rods and tubes. The data were obtained from earlier technical reports and notes, and from unpublished work in this investigation. There are also included data obtained from published and unpublished work performed on an independent investigation. The rod materials, namely, nickel, monel, inconel, copper, 13:2 Cr-Ni steel, and 18:8 Cr-Ni steel, were tested in tension; 18:8 Cr-Ni steel tubes were tested in shear, and nickel, monel, aluminum-monel, and Inconel tubes were tested in both tension and shear. There are first described experiments on the relationship between hysteresis and creep, as obtained with repeated cyclic stressing of annealed stainless steel specimens over a constant load range. These tests, which preceded the measurements of elastic properties, assisted in devising the loading time schedule used in such measurements. From corrected stress-set curves are derived the five proof stresses used as indices of elastic or yield strength. From corrected stress-strain curves are derived the secant modulus and its variation with stress. The relationship between the forms of the stress-set and stress-strain curves and the values of the properties derived is discussed. Curves of variation of proof stress and modulus with prior extension, as obtained with single rod specimens, consist in wavelike basic curves with superposed oscillations due to differences of rest interval and extension spacing; the effects of these differences are studied. Oscillations of proof stress and modulus are generally opposite in manner. The use of a series of tubular specimens corresponding to different amounts of prior extension of cold reduction gave curves almost devoid of oscillation since the effects of variation of rest interval and extension spacing were removed. Comparison is also obtained between the variation of the several properties, as measured in tension and in shear. The rise of proof stress with extension is studied, and the work-hardening rates of the various metals evaluated. The ratio between the tensile and shear proof stresses for the various annealed and cold-worked tubular metals is likewise calculated. The influence of annealing or tempering temperature on the proof stresses and moduli for the cold-worked metals and for air-hardened 13:2 Cr-Ni steel is investigated. An improvement of elastic strength generally is obtained, without important loss of yield strength, by annealing at suitable temperature. The variation of the proof stress and modulus of elasticity with plastic deformation or annealing temperature is explained in terms of the relative dominance of three important factors: namely, (a) internal stress, (b) lattice-expansion or work-hardening, and (c) crystal reorientation. Effective values of Poisson's ratio were computed from tensile and shear moduli obtained on tubular specimens. The variation of Poisson's ratio with plastic deformation and annealing temperature is explained in terms of the degree of anisotropy produced by changes of (a) internal stress and (b) crystal orientation.

METALS - ELASTICITY↗

Report on the formal specification and partial verification of the VIPER microprocessor

The VIPER microprocessor chip is partitioned into four levels of abstractions. At the highest level, VIPER is described with decreasingly abstract sets of functions in LCF-LSM. At the lowest level are the gate-level models in proprietary CAD languages. The block-level and gate-level specifications are also given in the ELLA simulation language. Among VIPER's deficiencies are the fact that there is no notion of external events in the top-level specification, and it is impossible to use the top-level specifications to prove abstract properties of programs running on VIPER computers. There is no complete proof that the gate-level specifications implement the top-level specifications. Cohn's proof that the major-state machine correctly implements the top-level specifications has no formal connection with any of the other proof attempts. None of the latter address resetting the machine, memory timeout, forced error, or single step modes.

Brock, Bishop↗

A verified design of a fault-tolerant clock synchronization circuit: Preliminary investigations

Schneider demonstrates that many fault tolerant clock synchronization algorithms can be represented as refinements of a single proven correct paradigm. Shankar provides mechanical proof that Schneider's schema achieves Byzantine fault tolerant clock synchronization provided that 11 constraints are satisfied. Some of the constraints are assumptions about physical properties of the system and cannot be established formally. Proofs are given that the fault tolerant midpoint convergence function satisfies three of the constraints. A hardware design is presented, implementing the fault tolerant midpoint function, which is shown to satisfy the remaining constraints. The synchronization circuit will recover completely from transient faults provided the maximum fault assumption is not violated. The initialization protocol for the circuit also provides a recovery mechanism from total system failure caused by correlated transient faults.

Miner, Paul S.↗

Automating the Generation of Heterogeneous Aviation Safety Cases

A safety case is a structured argument, supported by a body of evidence, which provides a convincing and valid justification that a system is acceptably safe for a given application in a given operating environment. This report describes the development of a fragment of a preliminary safety case for the Swift Unmanned Aircraft System. The construction of the safety case fragment consists of two parts: a manually constructed system-level case, and an automatically constructed lower-level case, generated from formal proof of safety-relevant correctness properties. We provide a detailed discussion of the safety considerations for the target system, emphasizing the heterogeneity of sources of safety-relevant information, and use a hazard analysis to derive safety requirements, including formal requirements. We evaluate the safety case using three classes of metrics for measuring degrees of coverage, automation, and understandability. We then present our preliminary conclusions and make suggestions for future work.

Denney, Ewen W.↗

Automatic Estimation of Verified Floating-Point Round-Off Errors via Static Analysis

This paper introduces a static analysis technique for computing formally verified round-off error bounds of floating-point functional expressions. The technique is based on a denotational semantics that computes a symbolic estimation of floating-point round-o errors along with a proof certificate that ensures its correctness. The symbolic estimation can be evaluated on concrete inputs using rigorous enclosure methods to produce formally verified numerical error bounds. The proposed technique is implemented in the prototype research tool PRECiSA (Program Round-o Error Certifier via Static Analysis) and used in the verification of floating-point programs of interest to NASA.

Moscato, Mariano↗

A Measure-Theoretic Proof of the Markov Property for Hybrid Systems with Markovian Inputs

The behavior of a general hybrid system in discrete time can be represented by a non-linear difference equation x(k+1) = Fk(x(k), theta(k)), where theta(k) is assumed to be a finite state Markov chain. An important step in the stability analysis of these systems is to establish the Markov property of (x(k), theta(k)). There are, however, no complete proofs of this property which are simple to understand. This paper aims to correct this problem by presenting a complete and explicit proof, which uses only basic measure-theoretical concepts.

Tejada, Arturo↗

On the Markov Property for Nonlinear Discrete-Time Systems with Markovian Inputs

The behavior of a general hybrid system in discrete-time can be represented by a non-linear difference equation x(k + 1) = Fk(x(k), theta(k)), where theta(k) is assumed to be a finite-state Markov chain. An important step in the stability analysis of these systems is to establish the Markov property of (x(k), theta(k)). There are, however, no complete proofs of this property which are simple to understand. This paper aims to correct this problem by presenting a complete and explicit proof, which uses only fundamental measure-theoretical concepts.

Tejada, Arturo↗

A Generic Software Safety Document Generator

Formal certification is based on the idea that a mathematical proof of some property of a piece of software can be regarded as a certificate of correctness which, in principle, can be subjected to external scrutiny. In practice, however, proofs themselves are unlikely to be of much interest to engineers. Nevertheless, it is possible to use the information obtained from a mathematical analysis of software to produce a detailed textual justification of correctness. In this paper, we describe an approach to generating textual explanations from automatically generated proofs of program safety, where the proofs are of compliance with an explicit safety policy that can be varied. Key to this is tracing proof obligations back to the program, and we describe a tool which implements this to certify code auto-generated by AutoBayes and AutoFilter, program synthesis systems under development at the NASA Ames Research Center. Our approach is a step towards combining formal certification with traditional certification methods.

Denney, Ewen↗

Testing First-Order Logic Axioms in AutoCert

AutoCert [2] is a formal verification tool for machine generated code in safety critical domains, such as aerospace control code generated from MathWorks Real-Time Workshop. AutoCert uses Automated Theorem Provers (ATPs) [5] based on First-Order Logic (FOL) to formally verify safety and functional correctness properties of the code. These ATPs try to build proofs based on user provided domain-specific axioms, which can be arbitrary First-Order Formulas (FOFs). These axioms are the most crucial part of the trusted base, since proofs can be submitted to a proof checker removing the need to trust the prover and AutoCert itself plays the part of checking the code generator. However, formulating axioms correctly (i.e. precisely as the user had really intended) is non-trivial in practice. The challenge of axiomatization arise from several dimensions. First, the domain knowledge has its own complexity. AutoCert has been used to verify mathematical requirements on navigation software that carries out various geometric coordinate transformations involving matrices and quaternions. Axiomatic theories for such constructs are complex enough that mistakes are not uncommon. Second, adjusting axioms for ATPs can add even more complexity. The axioms frequently need to be modified in order to have them in a form suitable for use with ATPs. Such modifications tend to obscure the axioms further. Thirdly, speculating validity of the axioms from the output of existing ATPs is very hard since theorem provers typically do not give any examples or counterexamples.

Ahn, Ki Yung↗