Domain-Specific Modeling Languages (DSMLs) rely on model-based techniques to deliver tailored languages to meet specific needs, such as system modeling, formal verification, and code generation. A DSML has specific static and dynamic behavior rules that must be properly assessed before processing the model. The definition of these rules remains a challenge. Meta-modeling techniques usually lack the foundational elements required to fully express behavioral semantics. In this context, using an interactive theorem prover provides a mathematical foundation with which the semantics of a DSML can be defined. This includes an abstract syntax tree, typing rules, and derivation of an executable simulator. In this paper, we report on an ongoing effort to capture the SAE AADL language using Coq along with specific analysis capabilities. Our contribution provides an unambiguous semantics for a large set of the language and can be used as a foundation to build rich analysis capabilities.

To support the dynamic composition of various devices/apps into a medical system at point-of-care, a set of communication patterns to describe the communication needs of devices has been proposed. To address timing requirements, each pattern breaks common timing properties into finer ones that can be enforced locally by the components. Common timing requirements for the underlying communication substrate are derived from these local properties. The local properties of devices are assured by the vendors at the development time. Although organizations procure devices that are compatible in terms of their local properties and middleware, they may not operate as desired. The latency of the organization network interacts with the local properties of devices. To validate the interaction among the timing properties of components and the network, we formally specify such systems in Timed Rebeca. We use model checking to verify the derived timing requirements of the communication substrate in terms of the network and device models. We provide a set of templates as a guideline to specify medical systems in terms of the formal model of patterns. A composite medical system using several devices is subject to state-space explosion. We extend the reduction technique of Timed Rebeca based on the static properties of patterns. We prove that our reduction is sound and show the applicability of our approach in reducing the state space by modeling two clinical scenarios made of several instances of patterns.

Safety-critical system engineering and traditional safety analyses have for decades been focused on problems caused by natural or accidental phenomena. Security analyses, on the other hand, focus on preventing intentional, malicious acts that reduce system availability, degrade user privacy, or enable unauthorized access. In the context of safety-critical systems, safety and security are intertwined, e.g., injecting malicious control commands may lead to system actuation that causes harm. Despite this intertwining, safety and security concerns have traditionally been designed and analyzed independently of one another, and examined in very different ways. In this work we examine a new hazard analysis technique---Systematic Analysis of Faults and Errors (SAFE)---and its deep integration of safety and security concerns. This is achieved by explicitly incorporating a semantic framework of error "effects" that unifies an adversary model long used in security contexts with a fault/error categorization that aligns with previous approaches to hazard analysis. This categorization enables analysts to separate the immediate, component-level effects of errors from their cause or precise deviation from specification.

Medical devices are increasingly being developed not as standalone units but as network-aware machines that can be integrated via high-assurance middleware and coordinated with software into clinically useful applications for Medical Application Platforms (MAP apps). While this concept is still emerging, both regulators and vendors recognize that these apps can be as powerful as purpose-built medical devices, and they are struggling to understand the appropriate techniques to support risk assessment and safety claims. Before being approved for market, the reliability of medical devices is typically ascertained by performing one of a number of hardware-centric, reliability-focused analyses. However, these techniques are not a good fit for the combined hardware and software systems that are defined by MAP apps, nor is their emphasis on reliability appropriate when the end goal is safety. In this work, we tailor a modern, systems-based hazard analysis technique (STAMP / STPA) to the domain of MAP apps by leveraging our prior work in safety-critical systems engineering for medical software. We also build on our previously developed AADL-based language and tooling for the semi-formal modeling of MAP app architectures to provide a proof-of-concept tool that aids the transition between design and analysis. This tool takes as input an architectural model annotated with both new and re-purposed constructs from AADL (as well as its error modeling annex) and produces as output a report in our proposed format. We ground our approach by using a clinically-sourced scenario that serves as a motivating example: we provide an annotated architectural model and hazard analysis report that serve as exemplars of our technique and tooling.

Previous applications of symbolic execution (Sym-Exe) have focused on bug-finding and test-case generation. However, SymExe has the potential to significantly improve usability and automation when applied to verification of software contracts in safety-critical systems. Due to the lack of support for processing software contracts and ad hoc approaches for introducing a variety of over/under-approximations and optimizations, most SymExe implementations cannot precisely characterize the verification status of contracts. Moreover, these tools do not provide explicit justifications for their conclusions, and thus they are not aligned with trends toward evidence-based verification and certification. We introduce the concept of explicating symbolic execution (xSymExe) that builds on a strong semantic foundation, supports full verification of rich software contracts, explicitly tracks where over/under-approximations are introduced or avoided, precisely characterizes the verification status of each contractual claim, and associates each claim with explications for its reported verification status. We report on case studies in the use of Bakar Kiasan, our open source xSymExe tool for Spark Ada.

This tool paper describes the design and implementation of an interactive environment for discovering and browsing information flow in SPARK programs. SPARK is a subset of Ada that has been used in a number of industrial contexts for implementing certified safety and security critical systems. SPARK requires explicit specification of information flow properties in the form of procedure contracts. To write such contracts, developers need to understand the data and control dependencies in the program. Our tool Bakar Alir, implemented as an Eclipse Plug-in, utilizes classic slicing and chopping techniques to assist developers in writing information flow contracts.

Medical cyber-physical systems (MCPS) are life-critical, context-aware, networked systems of medical devices. These systems are increasingly used in hospitals to provide high-quality continuous care for patients. The need to design complex MCPS that are both safe and effective has presented numerous challenges, including achieving high assurance in system software, intoperability, context-aware intelligence, autonomy, security and privacy, and device certifiability. In this paper, we discuss these challenges in developing MCPS, some of our work in addressing them, and several open research issues.

Maintaining integrity, consistency, and enforcing conformance in architectures of large-scale systems requires specification and enforcement of many different forms of structural constraints. While type systems have proved effective for enforcing structural constraints in programs and data structures, most architectural modeling frameworks include only weak notions of typing or rely on first-order logic constraint languages that have steep learning curves and that become unwieldy when scaling to large systems.

Recent work has demonstrated that symbolic execution techniques can serve as a basis for formal analysis capable of automatically checking heap-manipulating software components against strong interface specifications. In this paper, we present an enhancement to existing symbolic execution algorithms for object-oriented programs that significantly improves upon the algorithms currently implemented in Bogor/Kiasan and JPF. To motivate and justify the new strategy for handling heap data in our enhanced approach, we present a significant empirical study of the performance of related algorithms and an interesting case counting analysis of the heap shapes that can appear in several widely used Java data structure packages.

The notion of control dependence underlies many program analysis and transformation techniques. Despite being widely used, existing definitions and approaches to calculating control dependence are difficult to apply directly to modern program structures because these make substantial use of exception processing and increasingly support reactive systems designed to run indefinitely. This article revisits foundational issues surrounding control dependence, and develops definitions and algorithms for computing several variations of control dependence that can be directly applied to modern program structures. To provide a foundation for slicing reactive systems, the article proposes a notion of slicing correctness based on weak bisimulation, and proves that some of these new definitions of control dependence generate slices that conform to this notion of correctness. This new framework of control dependence definitions, with corresponding correctness results, is even able to support programs with irreducible control flow graphs. Finally, a variety of properties show that the new definitions conservatively extend classic definitions. These new definitions and algorithms form the basis of the Indus Java slicer, a publicly available program slicer that has been implemented for full Java.

Best program practices in software engineering emphasize software components that are loosely coupled and can be independently developed by different vendors. While these approaches improve the process of software development, however, they present a number of challenges involving reasoning about the correctness of individual components as well as their integration. Design-by-contract reasoning offers a promising approach to reason about software components by requiring software contracts that describe the behaviors of the components. This allows one to focus at satisfying the contract of each component, i.e., it allows compositional reasoning. In this paper, we present Kiasan, a technique that combines symbolic execution, model checking, theorem proving, and constraint solving to support design-by-contract reasoning of object-oriented software. There are a number of interesting tradeoffs between Kiasan other approaches such as ESC/Java. While checking in Kiasan is sometime more expensive, Kiasan can check much stronger behavioral properties of object-oriented software including properties/software that makes extensive use of heap-allocated data. In addition, Kiasan naturally generates counter examples, visualization of code effects, and JUnit test cases that are driven by code and user-supplied specifications. We present Kiasan and describe how it is implemented on top of the Bogor framework. Furthermore, we present a case study in which Kiasan is applied to a variety of examples and we discuss insights gained from our experience.

Model checking has proven to be an effective technology for verification and debugging in hardware and more recently in software domains. We believe that recent trends in both the requirements for software systems and the processes by which systems are developed suggest that domain-specific model checking engines may be more effective than general purpose model checking tools. To overcome limitations of existing tools which tend to be monolithic and non-extensible, we have developed an extensible and customizable model checking framework called Bogor. In this tutorial, we give an overview of (a) Bogor's direct support for modeling object-oriented designs and implementations, (b) its facilities for extending and customizing its modeling language and algorithms to create domain-specific model checking engines, and (c) pedagogical materials that we have developed to describe the construction of model checking tools built on top of the Bogor infrastructure

The use of component models such as Enterprise Java Beans and the CORBA Component Model (CCM) in application development is expanding rapidly. Even in real-time safety/mission-critical domains, component-based development is beginning to take hold as a mechanism for incorporating non-functional aspects such as real-time, quality-of-service, and distribution. To form an effective basis for development of such systems, we believe that support for reasoning about correctness properties of component-based designs is essential. In this paper, we present Cadena - an integrated environment for building and modeling CCM systems. Cadena provides facilities for defining component types using CCM IDL, specifying dependency information and transition System semantics for these types, assembling systems from CCM components, visualizing various dependence relationships between components, specifying and verifying correctness properties of models of CCM systems derived from CCM IDL, component assembly information, and Cadena specifications, and producing CORBA stubs and skeletons implemented in Java. We are applying Cadena to avionics applications built using Boeing's Bold Stroke framework.

The use of component models such as Enterprise Java Beans and the CORBA Component Model (CCM) in application development is expanding rapidly. Even in real-time safety-critical and mission-critical domains, component-based development is beginning to take hold as a mechanism for in-corporating non-functional aspects such as real-time, quality-of-service, and distribution.

Model checking is emerging as a popular technology for reasoning about behavioral properties of a wide variety of software artifacts including: requirements models, architectural descriptions, designs, implementations, and process models. The complexity of model checking is well-known, yet cost-effective analyses have been achieved by exploiting, for example, naturally occurring abstractions and semantic properties of a target software artifact. semantic properties of target software artifacts. Adapting a model checking tool to exploit this kind of domain knowledge often requires in-depth knowledge of the tool's implementation.We believe that with appropriate tool support, domain experts will be able to develop efficient model checking-based analyses for a variety of software-related models. To explore this hypothesis, we have developed Bogor, a model checking framework with an extensible input language for defining domain-specific constructs and a modular interface design to ease the optimization of domain-specific state-space encodings, reductions and search algorithms. We present the pattern-oriented design of Bogor and discuss our experiences adapting it to efficiently model check Java programs and event-driven component-based designs.

Concurrency is used in modern software systems as a means of addressing performance, availability, and reliability requirements. The collaboration of multiple independently executing components is fundamental to meeting such requirements and such collaboration is realized by synchronizing component execution.Using current technologies developers are faced with a tension between correct synchronization and performance. Developers can be confident when simple forms of synchronization are used, for example, locking all accesses to shared data. Unfortunately, such simple approaches can result in significant run-time overhead, and, in fact, there are many cases in which such simple approaches cannot implement required synchronization policies. Implementing more sophisticated (and less constraining) synchronization policies may improve run-time performance and satisfy synchronization requirements, but fundamental difficulties in reasoning about concurrency make it difficult to assess their correctness.This paper describes an approach to automatically synthesizing complex synchronization implementations from formal high-level specifications. Moreover, the generated coded is designed to be processed easily by software model-checking tools such as Bandera. This enables the generated synchronization solutions to be verified for important system correctness properties. We believe this is an effective approach because the tool-support provided makes it simple to use, it has a solid semantic foundation, it is language independent, and we have demonstrated that it is powerful enough to solve numerous challenging synchronization problems.

Numerous researchers have reported success in reasoning about properties of small programs using finite-state verification techniques. We believe, as do most researchers in this area, that in order to scale those initial successes to realistic programs, aggressive abstraction of program data will be necessary. Furthermore, we believe that to make abstraction-based verification usable by non-experts significant tool support will be required. In this paper we describe how several different program analysis and transformation techniques are integrated into the Bandera toolset to provide facilities for abstracting Java programs to produce compact, finite-state models that are amenable to verification for example via model checking. We illustrate the application of Bandera's abstraction facilities to analyze a realistic multi-threaded Java program.

Finite-state verification techniques, such as model checking, have shown promise as a cost-effective means for finding defects in hardware designs. To date, the application of these techniques to software has been hindered by several obstacles. Chief among these is the problem of constructing a finite-state model that approximates the executable behavior of the software system of interest. Current best-practice involves hand-construction of models which is expensive (prohibitive for all but the smallest systems), prone to errors (which can result in misleading verification results), and difficult to optimize (which is necessary to combat the exponential complexity of verification algorithms).

Despite emerging tool support for assertion-checking and testing of object-oriented programs, providing convincing evidence of program correctness remains a difficult challenge. This is especially true for multi-threaded programs. Techniques for reasoning about finite-state systems have been developing rapidly over the past decade and have the potential to form the basis of powerful software validation theologies.We have developed the Bandera toolset [1] to harness the power of existing model checking tools to apply them to reason about correctness requirements of Java programs. Bandera provides tool support for defining and managing collections of requirements for a program, for extracting compact finite-state models of the program to enable tractable analysis, and for displaying analysis results to the user through a debugger-like interface. This paper describes and illustrates the use of Bandera's source-level user interface for model checking Java programs.

Thirty-five years ago, thunks were used to simulate call-by-name under call-by-value in Algol 60. Twenty years ago, Plotkin presented continuation-based simulations of call-by-name under call-by-value and vice versa in the λ-calculus. We connect all three of these classical simulations by factorizing the continuation-based call-by-name simulation [Cscr ]n with a thunk-based call-by-name simulation [Tscr ] followed by the continuation-based call-by-value simulation [Cscr ]v, extended to thunks.formula hereWe show that [Tscr ] actually satisfies all of Plotkin's correctness criteria for [Cscr ]n (i.e. his Indifference, Simulation and Translation theorems). Furthermore, most of the correctness theorems for [Cscr ]n can now be seen as simple corollaries of the corresponding theorems for [Cscr ]v and [Tscr ].

We formalize a partial evaluator for Eugenio Moggi's computational metalanguage. This formalization gives an evaluation-order independent view of binding-time analysis and program specialization, including a proper treatment of call unfolding. It also enables us to express the essence of ‘control-based binding-time improvements’ for let expressions. Specifically, we prove that the binding-time improvements given by ‘continuation-based specialization’ can be expressed in the metalanguage via monadic laws.

We unify previous work on the continuation-passing style (CPS) transformations in a generic framework based on Moggi's computational met a-language.This framework is used to obtain GPS transformations for a variety of evaluation strategies and to characterize the corresponding administrative reductions and inverse transformations.We establish generic formal connections between operational semantics and equational theories.Formal properties of transformations for specific evaluation orders follow as corollaries.Essentially, we factor transformations through Moggi's computational meta-language.Mapping A-terms into the met a-language captures computational properties (e.g., partiality, strictness) and evaluation order explicitly in both the term and the type structure of the meta-language.The CPS transformation is then obtained by applying a generic transformation from terms and types in the meta-language to CPS terms and types, based on a typed term representation of the continuation monad.We prove an adequacy property for the generic transformation and establish an equational correspondence between the meta-language and CPS terms.These generic results generalize Plotkin's seminal theorems, subsume more recent results, and enable new uses of CPS transformations and their inverses.We discuss how to apply these results to compilation.