Engineering topics

Tkachuk, Oksana

Publications and source records attributed to Tkachuk, Oksana.

10 records

NASA NTRS2017

MESA: Message-Based System Analysis Using Runtime Verification

In this paper, we present a novel approach and framework for run-time verication of large, safety critical messaging systems. This work was motivated by verifying the System Wide Information Management (SWIM) project of the Federal Aviation Administration (FAA). SWIM provides live air traffic, site and weather data streams for the whole National Airspace System (NAS), which can easily amount to several hundred messages per second. Such safety critical systems cannot be instrumented, therefore, verification and monitoring has to happen using a nonintrusive approach, by connecting to a variety of network interfaces. Due to a large number of potential properties to check, the verification framework needs to support efficient formulation of properties with a suitable Domain Specific Language (DSL). Our approach is to utilize a distributed system that is geared towards connectivity and scalability and interface it at the message queue level to a powerful verification engine. We implemented our approach in the tool called MESA: Message-Based System Analysis, which leverages the open source projects RACE (Runtime for Airspace Concept Evaluation) and TraceContract. RACE is a platform for instantiating and running highly concurrent and distributed systems and enables connectivity to SWIM and scalability. TraceContract is a runtime verication tool that allows for checking traces against properties specified in a powerful DSL. We applied our approach to verify a SWIM service against several requirements.We found errors such as duplicate and out-of-order messages.

Message-based System↗

NASA NTRS2016

RACE: Building Airspace Simulations Faster and Better with Actors

Large, distributed aerospace simulations traditionally have been the domain of customized, closed designs, using statically compiled code based on specialized messaging systems such as DDS and HLA. While this can be suitable for one-off systems or specialized in-house product lines, it increases development costs and lowers extensibility. We propose to use contemporary internet software technology to solve this problem.Our Runtime for Airspace Concept Evaluation (RACE) architecture was born out of the need to rapidly develop and evaluate what-if scenarios that involve the whole National Airspace System (NAS), live NAS data feeds such as the FAA's System Wide Information Management (SWIM) servers, and existing flight simulators. It had to run on off-the-shelf hardware, be open sourced, and support visualization components up to multiple synchronized large screen geo viewers used in situation rooms. Most of all, it had to be extensible - being a viable platform for the development of future simulation components.

Mehlitz, Peter↗

NASA NTRS2015

Environment Modeling Using Runtime Values for JPF-Android

Software applications are developed to be executed in a specific environment. This environment includes external native libraries to add functionality to the application and drivers to fire the application execution. For testing and verification, the environment of an application is simplified abstracted using models or stubs. Empty stubs, returning default values, are simple to generate automatically, but they do not perform well when the application expects specific return values. Symbolic execution is used to find input parameters for drivers and return values for library stubs, but it struggles to detect the values of complex objects. In this work-in-progress paper, we explore an approach to generate drivers and stubs based on values collected during runtime instead of using default values. Entry-points and methods that need to be modeled are instrumented to log their parameters and return values. The instrumented applications are then executed using a driver and instrumented libraries. The values collected during runtime are used to generate driver and stub values on- the-fly that improve coverage during verification by enabling the execution of code that previously crashed or was missed. We are implementing this approach to improve the environment model of JPF-Android, our model checking and analysis tool for Android applications.

Verification↗

NASA NTRS2015

Are We There Yet? Determining the Adequacy of Formalized Requirements and Test Suites

Structural coverage metrics have traditionally categorized code as either covered or uncovered. Recent work presents a stronger notion of coverage, checked coverage, which counts only statements whose execution contributes to an outcome checked by an oracle. While this notion of coverage addresses the adequacy of the oracle, for Model-Based Development of safety critical systems, it is still not enough; we are also interested in how much of the oracle is covered, and whether the values of program variables are masked when the oracle is evaluated. Such information can help system engineers identify missing requirements as well as missing test cases. In this work, we add to the idea of checked coverage an analysis of requirements coverage to help provide insight to engineers as to whether the requirements or the test suite need to be improved. We implement our approach based on a dynamic backward slicing technique and evaluate it on several systems developed in Simulink. The results of our preliminary study show that even for systems with comprehensive test suites and good sets of requirements, our approach can identify cases where more tests or more requirements are needed to improve coverage numbers.

Dynamic Slicing↗

NASA NTRS2015

Generation of Library Models for Verification of Android Applications

Android applications are difficult to verify and test since they have many external dependencies. To overcome this problem, environment generation can be used to create a model of the environment to simulate the behavior of these external dependencies. Creating this environment model manually is a tedious process and although there are many techniques available to generate models, the key lies in identifying how these techniques can be applied to a specific domain. In this paper we discuss two static analysis tools OCSEGen and Modgen and how they can be applied to the Android domain to generate models for specific parts of the environment.

Verification↗

NASA NTRS2014

Improving Coverage of Test Cases Generated by Symbolic PathFinder for Programs with Loops

Symbolic execution is a program analysis technique that is used for many purposes, one of which is test-case generation. For loop-free programs, this generates a test-set that achieves path coverage. Program loops, however, imply exponential growth of the number of paths in the best case and non-termination in the worst case. In practice, the number of loop unwindings needs to be bounded for analysis. We consider symbolic execution in the context of the tool Symbolic Pathfinder. This tool extends the model-checker Java Pathfinder and relies on its bounded state-space exploration for termination. We present an implementation of k-bounded loop unwinding, which increases the amount of user-control over the symbolic execution of loops. Bounded unwinding can be viewed as a naive way to prune paths through loops. When using symbolic execution for test-case generation, naively pruning paths is likely at the cost of coverage. In order to improve coverage of branches within a loop body, we present a technique that semi-automatically concretizes variables used in a loop. The basic technique is limited and we therefore present annotations to manually steer symbolic execution towards certain branches, as well as ideas on how the technique can be extended to be more widely applicable.

Programs With Loops↗

NASA NTRS2014

OCSEGen: Open Components and Systems Environment Generator

To analyze a large system, one often needs to break it into smaller components.To analyze a component or unit under analysis, one needs to model its context of execution, called environment, which represents the components with which the unit interacts. Environment generation is a challenging problem, because the environment needs to be general enough to uncover unit errors, yet precise enough to make the analysis tractable. In this paper, we present a tool for automated environment generation for open components and systems. The tool, called OCSEGen, is implemented on top of the Soot framework. We present the tool's current support and discuss its possible future extensions.

User Specifications↗

NASA NTRS2014

Helping System Engineers Bridge the Peaks

In our experience at NASA, system engineers generally follow the Twin Peaks approach when developing safety-critical systems. However, iterations between the peaks require considerable manual, and in some cases duplicate, effort. A significant part of the manual effort stems from the fact that requirements are written in English natural language rather than a formal notation. In this work, we propose an approach that enables system engineers to leverage formal requirements and automated test generation to streamline iterations, effectively "bridging the peaks". The key to the approach is a formal language notation that a) system engineers are comfortable with, b) is supported by a family of automated V&V tools, and c) is semantically rich enough to describe the requirements of interest. We believe the combination of formalizing requirements and providing tool support to automate the iterations will lead to a more efficient Twin Peaks implementation at NASA.

Requirements↗

NASA NTRS2011

Automatic Extraction of JPF Options and Documentation

Documenting existing Java PathFinder (JPF) projects or developing new extensions is a challenging task. JPF provides a platform for creating new extensions and relies on key-value properties for their configuration. Keeping track of all possible options and extension mechanisms in JPF can be difficult. This paper presents jpf-autodoc-options, a tool that automatically extracts JPF projects options and other documentation-related information, which can greatly help both JPF users and developers of JPF extensions.

Static Analysis↗

NASA NTRS2003

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↗