The creation of Bayesian networks often requires the specification of a large number of parameters, making it highly desirable to be able to learn these parameters from historical data. In many cases, such data has uncertainty associated with it, including cases in which this data comes from unstructured analysis or from sensors. When creating diagnosis networks, for example, unstructured analysis algorithms can be run on the historical text descriptions or images of previous cases so as to extract data for learning Bayesian network parameters, but such derived data has inherent uncertainty associated with it due to the nature of such algorithms. Because of the inability of current Bayesian network parameter learning algorithms to incorporate such uncertainty, common approaches either ignore this uncertainty, thus reducing the resulting accuracy, or completely disregard such data. We present an approach for learning Bayesian network parameters that explicitly incorporates such uncertainty, and which is a natural extension of the Bayesian network formalism. We present a generalization of the Expectation Maximization parameter learning algorithm that enables it to handle any historical data with likelihood-evidence-based uncertainty, as well as an empirical validation demonstrating the improved accuracy and convergence enabled by our approach. We also prove that our extended algorithm maintains the convergence and correctness properties of the original EM algorithm, while explicitly incorporating data uncertainty in the learning process.

This paper presents CHASE, a framework for requirement capture, formalization, and validation for cyber-physical systems. CHASE combines a practical front-end formal specification language based on patterns with a rigorous verification back-end based on assume-guarantee contracts. The front-end language can express temporal properties of networks using a declarative style, and supports automatic translation from natural-language constructs to low-level mathematical languages. The verification back-end leverages the mathematical formalism of contracts to reason about system requirements and determine inconsistencies and dependencies between them. CHASE features a modular and extensible software infrastructure that can support different domain-specific languages, modeling formalisms, and analysis tools. We illustrate its effectiveness on industrial design examples, including control of aircraft power distribution networks and arbitration of a mixed-criticality automotive bus.

We present a new algorithm for computing interprocedural dominators. The algorithm identifies a set of special nodes, which are the only ones that can have interprocedural dominance edges, and extends the intraprocedural dominator trees by deriving those edges. The computation of the dominators of each node is independent of the computation of any other node, and therefore can be done on demand for each node as required. For the same reason, the algorithm lends itself naturally to parallelization. The algorithm has been implemented, and is shown to be practical for large programs. Because of its cooperative caching behavior, the algorithm gains a large performance boost when running on parallel hardware. We also present an efficient way of extending the algorithm for computing interprocedural dominance frontiers and control dependence.

One of the challenges in maintaining legacy systems is to be able to locate business logic in the code, and isolate it for different purposes, including implementing requested changes, refactoring, eliminating duplication, unit testing, and extracting business logic into a rule engine. Our new idea is an iterative method to identify the business logic in the code and visualize this information to gain better understanding of the logic distribution in the code, as well as developing a domain-specific business vocabulary. This new method combines and extends several existing technologies, including search, aggregation, and visualization. We evaluated the visualization method on a large-scale application and found that it yields useful results, provided an appropriate vocabulary is available.

We have developed a static-analysis algorithm that extracts statecharts from procedural implementations of state machines. The extracted statecharts are semantically-equivalent to the original program, and can be used for further development instead of the procedural code. We have implemented this algorithm in a tool called StatRec. We report on the results of running StatRec on a number of examples, including an implementation of the TCP protocol.

Program slicing is a useful technique in tools for program understanding and transformation. Computing correct and accurate slices for unstructured programs is particularly difficult. We present a new family of slicing algorithms that are proved correct and are more accurate than the best previous algorithms. An empirical study shows significant improvements of our algorithms on real code.

Design by contract is a practical methodology for evolving code together with its specification. The contract has important methodological implications on the design of the program. In addition, tools that instrument the code to check for contract violations help the development process by catching errors close to their sources. This is complicated by several factors, such as the need to collect preconditions from supertypes. There are two issues involved in the implementation of such a tool: the correct enforcement of the theoretical principles, and the instrumentation of the code. Most previous tools tackle both issues, but have subtle failures in one or the other. This paper describes Jose, a tool for design by contract in Java, which uses AspectJ, an aspect-oriented extension of Java, to instrument the program. This allows us to leverage the expertise of the AspectJ developers in instrumenting Java programs, and concentrate on the correct implementation of the design by-contract principles. This approach has the added benefit that it can be generalized to other object-oriented languages that have aspect-oriented extensions. We describe the design decisions made in the implementation of Jose, and the features of AspectJ that helped or hindered this implementation

Design by contract is a practical methodology for evolving code together with its specification; it helps prevent many errors, and catch others close to their sources. Unfortunately, writing (and maintaining) contracts requires a non-trivial investment of time and effort. We are developing a tool, called Discern, to statically analyze existing programs and discover draft contracts for them. Discern works by propagating weakest preconditions and strongest postconditions through the code. Known pre- and postconditions of operations used in the code help refine the contract; conversely, new assertions discovered can be propagated to clients of the method being analyzed. As usual, loops make the analysis difficult; heuristics are used to recognize the most common loop forms and extract useful information about them. Discern uses a library containing specifications of the most-used language libraries. With the manual addition of one postcondition and tagging of 3 assertions as invariants, Discern computed the correct preconditions for all but one method of Java’s Vector class, and similar results were obtained for StringBuffer.

Computer science students need to learn how to write high-quality software. An important methodology for achieving quality is design-by-contract, in which code is developed together with its specification, which is given as class invariants and method pre- and postconditions. This paper describes practical experience in teaching design-by-contract and other principles of object-oriented programming and design by a comprehensive set of programming exercises. These are implemented in Java, augmented with a design-by-contract tool. The conceptual gap between the theoretical principles taught in the course and the capabilities of this programming environment causes pedagogical problems; these problems and some solutions are discussed in this paper.

Old-generation database models, such as the indexed-sequential, hierarchical, or network models, provide record-level access to their data, with all application logic residing in the hosting program. In contrast, relational databases can perform complex operations, such as filter, aggregation, and join, on multiple records without an external specification of the record-access logic. Programs written for relational databases attempt to move as much of the application logic as possible into the database, in order to make the most of the optimizations performed internally by the database.This conceptual gap between the programming styles makes automatic high-quality translation of programs written for the older database models to the relational model difficult. It is not enough to convert just the database-access operations, since this would result in unacceptably inefficient programs. It is necessary to convert parts of the application logic from the procedural style of the hosting program (which is almost always Cobol) to the declarative style of SQL.This article describes an automatic system, called MIDAS, that performs high-quality reengineering of legacy database programs in this way. MIDAS is based on the paradigm of translation by abstraction, transformation, and reimplementation. The abstract representation is based on the Plan Calculus, with the addition of Query Graphs, introduced in this article in order to abstract the temporal behavior of database access patterns.The results of MIDAS's translation were found to be superior to those of the naive translation that only converts database-access operations in terms of readability, size of code, speed, and network data traffic. Initial industrial experience with MIDAS also demonstrates the high quality of its translations on large-scale programs.

The relational database model is currently the target of choice for the conversion of legacy software that uses older models (such as indexed-sequential, hierarchical or network models). The relational model makes up for its lower efficiency by a greater expressive power and by optimization of queries, using indexes and other means. However, sophisticated analysis is required in order to take advantage of these features, since converting each database access operation separately does not use the greater expressive power of the target database and does not enable it to perform useful optimizations. By analyzing the behavior of the host program around the database access operations, it is possible to discover patterns such as filtering, joins and aggregative operations. It is then possible to remove those operations from the host program and re-implement them in the target database query language. This paper describes an automatic system, called MIDAS (MIgrator of Database Application Systems), that performs high-quality reengineering of legacy database programs in this way. The results of MIDAS were found to be superior to those of the naive one-to-one translation in terms of readability, size, speed and network data traffic.

Debugging is one of the main uses of simulation. Localizing bugs or finding the reasons for unclear behavior involves going backwards in time, whereas simulation goes forward in time. Therefore, identifying causes with the aid of most existing simulation tools usually requires repeating the simulation several times, each time with reduced holes in the sieve. An alternative is simulation by deduction, a technique in which the steps in the dynamic behavior of the simulated model are deduced by a reasoning system. A simulation system that uses simulation by deduction can give direct answers to questions about the reasons for the simulation results. By recording the support for its deductions, such a system can answer “why” and “why not” questions about the scenario. Another benefit of simulation by deduction is that it enables symbolic simulation, that is, simulating a scenario given only a partial description of the environment and the simulated model. This allows verifying properties of an evolving design at any stage of the design process, and thus checking the consequences of the design decisions made so far. In order to allow deducing as much as possible from partial information, the axiom system has to be minimalistic, i.e., axioms have to require the minimum amount of knowledge of simulation inputs. These ideas were implemented in a system called SIP, which simulates the behavior of reactive systems. SIP is capable of answering “why,” “why not,” and “what if” questions. It also has a limited capability of dealing with partial knowledge. SIP is based on a reasoning system that is responsible for deducing the effects of the external inputs on the state of the simulated model, and recording the support for its deductions. The logical basis for the deduction of a step in SIP is provided by a minimalistic axiom system for statecharts. Although SIP simulates reactive systems described as statecharts, the principle of simulation by deduction is applicable to other types of systems and descriptions, provided only that they have a well-defined formal semantics.

The authors' experience in the Programmer's Apprentice project in applying knowledge representation and automated reasoning to support software development is summarized. A system, called Cake, is described that comprises seven layers of knowledge representation and reasoning facilities: truth maintenance, Boolean constraint propagation, equality, types, algebra, frames, and Plan Calculus. Sessions with two experimental software development tools implemented using Cake, the Requirements Apprentice and the Debugging Assistant, are also included.>

A propositional version of Feldman and Harel's Pr (DL) is defined, and shown to be decidable. The logic allows propositional-level formulas involving probabilistic programs, and contains full real-number theory for dealing with probabilities. The decidability proof introduces model schemes, which seem to be the most basic structures relating programs and probabilities.

A logic, Pr(DL), is presented, which enables reasoning about probabilistic programs or, alternatively, reasoning probabilistically about conventional programs. The syntax of Pr(DL) derives from Pratt's first-order dynamic logic and the semantics extends Kozen's semantics of probabilistic programs. An axiom system for Pr(DL) is presented and shown to be complete relative to an extension of first-order analysis. For discrete probabilities it is shown that first-order analysis actually suffices. Examples are presented, both of the expressive power of Pr(DL), and of a proof in the axiom system.