Search NASA⌕ Search

SEARCH · Search NASA

Results for “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 253 records · Page 14

Validating Requirements for Fault Tolerant Systems Using Model Checking

Model checking is shown to be an effective tool in validating the behavior of a fault tolerant embedded spacecraft controller. The case study presented here shows that by judiciously abstracting away extraneous complexity, the state space of the model could be exhaustively searched allowing critical functional requirements to be validated down to the design level. Abstracting away detail not germane to the problem of interest leaves by definition a partial specification behind. The success of this procedure shows that it is feasible to effectively validate a partial specification with this technique. Three anomalies were found in the system one of which is an error in the detailed requirements, and the other two are missing/ambiguous requirements. Because the method allows validation of partial specifications, it also is an effective methodology towards maintaining fidelity between a co-evolving specification and an implementation.

Schneider, Francis↗

Turbomachinery Design Quality Checks to Avoid Friction Induced Structural Failure

A unique configuration of the P&W SSME Alternate Fuel Turbopump turbine disk/blade assembly, combined with a severe thermal environment, resulted in several structural anomalies that were driven by frictional contact forces. Understanding the mechanics of these problems provides new quality checks for future turbo machinery designs. During development testing in 1997 of the SSME alternate fuel turbopump at Stennis Space Center, several potentially serious problems surfaced with the turbine disk/blade assembly that had not been experienced in extensive earlier testing. Changes to the operational thermal environment were noted based on analytical prediction of modifications that affected performance and on stationary thermal measurements adjacent to the rotor assembly. A detailed structural investigation was required to reveal the mechanism of distress induced by the change. The turbine disk experienced cracking in several locations due to increased thermal gradient induced stress during start and shutdown transients. This was easily predictable using standard analysis procedures and expected once the thermal environment was characterized. What was not expected was the curling of a piston ring used for blade axial retention in the disk, indentation of the axial face of the blade attachment by a spacer separating the first and second stage blades, and most significantly, galling and cracking of the blade root attachment that could have resulted in blade release. Past experience, in gas turbine environments, set a precedent of never relying on friction for help and to evaluate it only in specific instances where it was obvious that it would degrade capability. In each of the three cases above, friction proved to be a determining factor that pushed the components into an unsatisfactory mode of operation. The higher than expected temperatures and rapid thermal transients combined with friction to move beyond past experience. The turbine disk/blade assembly configuration contributed to the potential for these problems to occur by limiting the radial deflection from thermals and centrifugal loading. The cooled solid bore configuration was chosen to improve rotordynamic stability by limiting the length of rotor overhang while still protecting the roller bearing by maintaining zero slope under the inner race. During a start transient, the rim area of the disk heats rapidly and expands axially and circumferentially and requires corresponding radial and axial growth of the disk to maintain relative positioning of the disk, blades, spacers and retainer rings. The stiffness, large thermal mass, and bore cooling flow combine to severely limit the disk rim radial growth which results in the potential for relative movement between these parts. Friction then becomes a player in the determination of component stress.

Moore, Jerry H.↗

Model Checking Verification and Validation at JPL and the NASA Fairmont IV and V Facility

We show how a technology transfer effort was carried out. The successful use of model checking on a pilot JPL flight project demonstrates the usefulness and the efficacy of the approach. The pilot project was used to model a complex spacecraft controller. Software design and implementation validation were carried out successfully. To suggest future applications we also show how the implementation validation step can be automated. The effort was followed by the formal introduction of the modeling technique as a part of the JPL Quality Assurance process.

Schneider, Frank↗

Analyzing Mode Confusion via Model Checking

Mode confusion is one of the most serious problems in aviation safety. Today's complex digital flight decks make it difficult for pilots to maintain awareness of the actual states, or modes, of the flight deck automation. NASA Langley leads an initiative to explore how formal techniques can be used to discover possible sources of mode confusion. As part of this initiative, a flight guidance system was previously specified as a finite Mealy automaton, and the theorem prover PVS was used to reason about it. The objective of the present paper is to investigate whether state-exploration techniques, especially model checking, are better able to achieve this task than theorem proving and also to compare several verification tools for the specific application. The flight guidance system is modeled and analyzed in Murphi, SMV, and Spin. The tools are compared regarding their system description language, their practicality for analyzing mode confusion, and their capabilities for error tracing and for animating diagnostic information. It turns out that their strengths are complementary.

Luettgen, Gerald↗

Low Density Parity Check Codes Based on Finite Geometries: A Rediscovery and More

Low density parity check (LDPC) codes with iterative decoding based on belief propagation achieve astonishing error performance close to Shannon limit. No algebraic or geometric method for constructing these codes has been reported and they are largely generated by computer search. As a result, encoding of long LDPC codes is in general very complex. This paper presents two classes of high rate LDPC codes whose constructions are based on finite Euclidean and projective geometries, respectively. These classes of codes a.re cyclic and have good constraint parameters and minimum distances. Cyclic structure adows the use of linear feedback shift registers for encoding. These finite geometry LDPC codes achieve very good error performance with either soft-decision iterative decoding based on belief propagation or Gallager's hard-decision bit flipping algorithm. These codes can be punctured or extended to obtain other good LDPC codes. A generalization of these codes is also presented.

Kou, Yu↗

Cycle 2 Nonlinear Design Optimization Analytical Cross Checks

The objectives of the Cycle 2 Nonlinear Design Optimization Anlaytical Cross Checks are to: 1) Understand the variability in the predicted performance levels of the nonlinear designs arising from the use of different inviscid (full potential/Euler) and viscous (Navier-Stokes) analysis methods; and 2) Provide the information required to allow the performance levels of all three designs to be validated using the data from the NCV (nonlinear Cruise Validation) model test.

Bencze, Dan↗

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↗

Combining Static Analysis and Model Checking for Software Analysis

We present an iterative technique in which model checking and static analysis are combined to verify large software systems. The role of the static analysis is to compute partial order information which the model checker uses to reduce the state space. During exploration, the model checker also computes aliasing information that it gives to the static analyzer which can then refine its analysis. The result of this refined analysis is then fed back to the model checker which updates its partial order reduction. At each step of this iterative process, the static analysis computes optimistic information which results in an unsafe reduction of the state space. However we show that the process converges to a fired point at which time the partial order information is safe and the whole state space is explored.

Brat, Guillaume↗

Low Density Parity Check Codes: Bandwidth Efficient Channel Coding

Low Density Parity Check (LDPC) Codes provide near-Shannon Capacity performance for NASA Missions. These codes have high coding rates R=0.82 and 0.875 with moderate code lengths, n=4096 and 8176. Their decoders have inherently parallel structures which allows for high-speed implementation. Two codes based on Euclidean Geometry (EG) were selected for flight ASIC implementation. These codes are cyclic and quasi-cyclic in nature and therefore have a simple encoder structure. This results in power and size benefits. These codes also have a large minimum distance as much as d,,, = 65 giving them powerful error correcting capabilities and error floors less than lo- BER. This paper will present development of the LDPC flight encoder and decoder, its applications and status.

Fong, Wai↗

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↗

Thermodynamic Pressure/Temperature Transducer Health Check

A device and procedure for checking the health of a pressure transducer in situ is provided. The procedure includes measuring a fixed change in pressure above ambient pressure and a fixed change in pressure below ambient pressure. This is done by first sealing an enclosed volume around the transducer with a valve. A piston inside the sealed volume is increasing the pressure. A fixed pressure below ambient pressure is obtained by opening the valve, driving the piston The output of the pressure transducer is recorded for both the overpressuring and the underpressuring. By comparing this data with data taken during a preoperative calibration, the health of the transducer is determined from the linearity, the hysteresis, and the repeatability of its output. The further addition of a thermometer allows constant offset error in the transducer output to be determined.

Christopher D Immer↗

(abstract) Automated Constraint Checking of Spacecraft Command Sequences

Making certain that spacecraft command sequences do not violate any constraints is often tedious and expensive in terms of both personnel and software development. To reduce this cost, we have pursued the development of a flexible system for specifying models of spacecraft behavior in response to commands as well as constraints on that behavior. The potential need for modeling complex spacecraft behavior required that the system be designed to be usable both on a conventional workstation and a parallel supercomputer. Finally, it needed to be intuitive enough for the the intended mission operations users to easily design sets of rules and models to automate tedious, resource-consuming constraint checking of commands. We have defined a Specification And Verification Environment (SAVE) for spacecraft flight rules.

automation spacecraft command sequences constraint↗

Model Checking Abstract PLEXIL Programs with SMART

We describe a method to automatically generate discrete-state models of abstract Plan Execution Interchange Language (PLEXIL) programs that can be analyzed using model checking tools. Starting from a high-level description of a PLEXIL program or a family of programs with common characteristics, the generator lays the framework that models the principles of program execution. The concrete parts of the program are not automatically generated, but require the modeler to introduce them by hand. As a case study, we generate models to verify properties of the PLEXIL macro constructs that are introduced as shorthand notation. After an exhaustive analysis, we conclude that the macro definitions obey the intended semantics and behave as expected, but contingently on a few specific requirements on the timing semantics of micro-steps in the concrete executive implementation.

Siminiceanu, Radu I.↗

Fast acting check valve

A check valve which closes more rapidly to prevent wearing of the valve seat and of the valve member that seals thereagainst, including a solenoid or other actuator that aids the normal spring to quickly close the valve at approximately the time when downpath fluid flow would stop, the actuator then being deenergized. The control circuit that operates the actuator can include a pair of pressure sensors sensing pressure both upstream and downstream from the valve seat. Where the valve is utilized to control flow to or from a piston pump, energization of the actuator can be controlled by sensing when the pump piston reaches its extreme of travel.

Perkins, Gerald S.↗

Model Checking with Edge-Valued Decision Diagrams

We describe an algebra of Edge-Valued Decision Diagrams (EVMDDs) to encode arithmetic functions and its implementation in a model checking library. We provide efficient algorithms for manipulating EVMDDs and review the theoretical time complexity of these algorithms for all basic arithmetic and relational operators. We also demonstrate that the time complexity of the generic recursive algorithm for applying a binary operator on EVMDDs is no worse than that of Multi- Terminal Decision Diagrams. We have implemented a new symbolic model checker with the intention to represent in one formalism the best techniques available at the moment across a spectrum of existing tools. Compared to the CUDD package, our tool is several orders of magnitude faster

Roux, Pierre↗

A Machine-Checked Proof of A State-Space Construction Algorithm

This paper presents the correctness proof of Saturation, an algorithm for generating state spaces of concurrent systems, implemented in the SMART tool. Unlike the Breadth First Search exploration algorithm, which is easy to understand and formalise, Saturation is a complex algorithm, employing a mutually-recursive pair of procedures that compute a series of non-trivial, nested local fixed points, corresponding to a chaotic fixed point strategy. A pencil-and-paper proof of Saturation exists, but a machine checked proof had never been attempted. The key element of the proof is the characterisation theorem of saturated nodes in decision diagrams, stating that a saturated node represents a set of states encoding a local fixed-point with respect to firing all events affecting only the node s level and levels below. For our purpose, we have employed the Prototype Verification System (PVS) for formalising the Saturation algorithm, its data structures, and for conducting the proofs.

Catano, Nestor↗

Software Model Checking of ARINC-653 Flight Code with MCP

The ARINC-653 standard defines a common interface for Integrated Modular Avionics (IMA) code. In particular, ARINC-653 Part 1 specifies a process- and partition-management API that is analogous to POSIX threads, but with certain extensions and restrictions intended to support the implementation of high reliability flight code. MCP is a software model checker, developed at NASA Ames, that provides capabilities for model checking C and C++ source code. In this paper, we present recent work aimed at implementing extensions to MCP that support ARINC-653, and we discuss the challenges and opportunities that consequentially arise. Providing support for ARINC-653 s time and space partitioning is nontrivial, though there are implicit benefits for partial order reduction possible as a consequence of the API s strict interprocess communication policy.

Thompson, Sarah J.↗