Framework based software tends to get bloated by accumulating optional features (or concerns) just-in-case they are needed. The good news is that such feature bloat need not always cause runtime execution bloat. The bad news is that often enough, only a few statements from an optional concern may cause execution bloat that may result in as much as 50% runtime overhead.

In this paper we present an automated technique for localizing faults in data-centric programs. Data-centric programs primarily interact with databases to get collections of content, process each entry in the collection(s), and output another collection or write it back to the database. One or more entries in the output may be faulty. In our approach, we gather the execution trace of a faulty program. We use a novel, precise slicing algorithm to break the trace into multiple slices, such that each slice maps to an entry in the output collection. We then compute the semantic difference between the slices that correspond to correct entries and those that correspond to incorrect ones. The "diff" helps to identify potentially faulty statements.

Given the high costs of software testing and fixing bugs after release, early detection of bugs using static analysis can result in significant savings. However, despite their many benefits, recent availability of many such tools, and evidence of a positive return-on-investment, static-analysis tools are not used widely because of various usability and usefulness problems. The usability inhibitors include the lack of features, such as capabilities to merge reports from multiple tools and view warning deltas between two builds of a system. The usefulness problems are related primarily to the accuracy of the tools: identification of false positives (or, spurious bugs) and uninteresting bugs among the true positives. In this paper, we present the details of an online portal, developed at IBM Research, to address these problems and promote the adoption of static-analysis tools. We report our experience with the deployment of the portal within the IBM developer community. We also highlight the problems that we have learned are important to address, and present our approach toward solving some of those problems.

Although many static-analysis techniques have been developed for automatically detecting bugs, such as null dereferences, fewer automated approaches have been presented for analyzing whether and how such bugs are fixed. Attempted bug fixes may be incomplete in that a related manifestation of the bug remains unfixed. In this paper, we characterize the “completeness” of attempted bug fixes that involve the flow of invalid values from one program point to another, such as null dereferences, in Java programs. Our characterization is based on the definition of a bug neighborhood, which is a scope of flows of invalid values. We present an automated analysis that, given two versions P and P' of a program, identifies the bugs in P that have been fixed in P', and classifies each fix as complete or incomplete. We implemented our technique for null-dereference bugs and conducted empirical studies using open-source projects. Our results indicate that, for the projects we studied, many bug fixes are not complete, and thus, may cause failures in subsequent executions of the program.

Null dereference is a commonly occurring defect in Java programs, and many static-analysis tools identify such defects. However, most of the existing tools perform a limited interprocedural analysis. In this paper, we present an interprocedural path-sensitive and context-sensitive analysis for identifying null dereferences. Starting at a dereference statement, our approach performs a backward demand-driven analysis to identify precisely paths along which null values may flow to the dereference. The demand-driven analysis avoids an exhaustive program exploration, which lets it scale to large programs. We present the results of empirical studies conducted using large open-source and commercial products. Our results show that: (1) our approach detects fewer false positives, and significantly more interprocedural true positives, than other commonly used tools; (2) the analysis scales to large subjects; and (3) the identified defects are often deleted in subsequent releases, which indicates that the reported defects are important.

Model-driven development (MDD) is widely used to develop modern business applications. MDD involves creating models at different levels of abstractions. Starting with models of domain concepts, these abstractions are successively refined, using transforms, to design-level models and, eventually, code-level artifacts. Although many tools exist that support transform creation and verification, tools that help users in understanding and using transforms are rare. In this paper, we present an approach for assisting users in understanding model transformations and debugging their input models. We use automated program-analysis techniques to analyze the transform code and compute constraints under which a transformation may fail or be incomplete. These code-level constraints are mapped to the input model elements to generate model-level rules. The rules can be used to validate whether an input model violates transform constraints, and to support general user queries about a transformation. We have implemented the analysis in a tool called XYLEM. We present empirical results, which indicate that (1) our approach can be effective in inferring useful rules, and (2) the rules let users efficiently diagnose a failing transformation without examining the transform source code.

This paper addresses the challenging problem of verifying the safety of pointer dereferences in real Java programs. We provide an automatic approach to this problem based on a sound interprocedural analysis. We present a staged expanding-scope algorithm for interprocedural abstract interpretation, which invokes sound analysis with partial programs of increasing scope. This algorithm achieves many benefits typical of whole-program interprocedural analysis, but scales to large programs by limiting analysis to small program fragments. To address cases where the static analysis of program fragments fails to prove safety, the analysis also suggests possible annotations which, if a user accepts, ensure the desired properties. Experimental evaluation on a number of Java programs shows that we are able to verify 90% of all dereferences soundly and automatically, and further reduce the number of remaining dereferences using non-nullness annotations.

Slicing is a well-known program reduction technique where for a given program P and a variable of interest v at some statement P in the program, a program slice contains those set of statements belonging to P that affect v . This article presents two algorithms for interprocedural slicing of concurrent programs--a context-insensitive algorithm and a context-sensitive algorithm. The context-insensitive algorithm is efficient and correct (it includes every statement that may affect the slicing criterion) but is imprecise since it may include certain extra statements that are unnecessary. Precise slicing has been shown to be undecidable for concurrent programs. However, the context-sensitive algorithm computes correct and reasonably precise slices, but has a worst-case exponential-time complexity. Our context-sensitive algorithm computes a closure of dependencies while ensuring that statements sliced in each thread belong to a realizable path in that thread.A realizable path in a thread with procedure calls is one that reflects the fact that when a procedure finishes, execution returns to the site of the most recently executed call in that thread. One of the novelties of this article is a practical solution to determine whether a given set of statements in a thread may belong to a realizable path. This solution is precise even in the presence of recursion and long call chains in the flow graph.The slicing algorithms are applicable to concurrent programs with shared memory, interleaving semantics, explicit wait/notify synchronization and monitors. We first give a solution for a simple model of concurrency and later show how to extend the solution to the Java concurrency model. We have implemented the algorithms for Java bytecode and give experimental results.

A composite service is typically specified using a language such as BPEL4WS and orchestrated by a single coordinator node in a centralized manner. The coordinator receives the client request, makes the required data transformations and invokes the component Web services as per the specification. However, in certain scenarios businesses might want to impose restrictions on access to the data they provide or the source from which they can accept data. Centralized orchestration can lead to violation of these data flow constraints as the central coordinator has access to the input and output data of all the component Web services. In many cases existing methods of data encryption and authentication are not sufficient to handle such constraints. These data flow constraints, thus, present obstacles for composite Web service orchestration. In this paper we propose a solution for orchestrating composite Web services under data flow constraints. The solution is based on decentralized orchestration, in which a composite Web service is broken into a set of partitions, one partition per component Web service. To overcome data flow constraints, each partition is executed within the same domain as the corresponding component Web service and hence, has the same access rights. However, there are, in general, many ways to decentralize a composite Web service. We apply a rule based filtering mechanism to choose a set of partitions that does not violate the specified dataflow constraints.

We are interested in static analysis of Java classes with the goal of discovering the preconditions under which a certain program point within a method may be reached, taking into account the effects of previous method calls on an object of that class. The information pertinent to this computation is represented as the object's typestate, which is a finite set of relevant predicates that abstract the object's actual state. The execution of a method depends on an object's current typestate as well as other input parameters; the object may transition to a different typestate during the method's execution.It is common for objects to contain references to other ob-jects. In such cases, an object's behavior may depend on, in addition to its own state, the state of objects it has a refer-ence to. The main contribution of this paper is to discover relevant object typestates, as well as transitions between typestates, in the presence of inter-object references. Our analysis first performs a combined predicate discovery and predicate abstraction to derive "boolean" versions of Java classes given as input. It then uses abstract interpretation to compute the typestate transitions caused by method calls. A novel aspect of this work is that a set of Java classes is analyzed in isolation, without any client program being pro-vided. To do this, the analysis simulates all possible client's actions via a synthetic heap, all of whose interesting config-urations are explored by our analysis.The information we compute can be put to use in several ways. It can be used in checking whether a given client code erroneously uses a set of Java classes in a way that can throw an exception. It can also be used in creating test drivers for Java classes in order to exercise all relevant code paths in the corresponding methods.

Distributed enterprise applications today are increasingly being built from services available over the web. A unit of functionality in this framework is a web service, a software application that exposes a set of "typed'' connections that can be accessed over the web using standard protocols. These units can then be composed into a composite web service. BPEL (Business Process Execution Language) is a high-level distributed programming language for creating composite web services.

Web Services are emerging as the standard mechanism for making information and software available programmatically via the Internet, and as building blocks for applications. A composite web service may be built using multiple component web services. Once its specification has been developed, the composite service may be orchestrated either using a centralized engine or in a decentralized fashion. Decentralized orchestration brings performance benefits, and improves scalability and concurrency. Dynamic binding coupled with decentralized orchestration adds high availability and fault tolerance to the system. However in such systems, the coordination between components needs to be carefully designed to ensure correct execution of the composite and to limit the synchronization overheads. In this paper, we categorize different forms of concurrency and provide an algorithm to identify these forms in a composite service specification. We explore different mechanisms for transferring data between the components in the presence of different forms of concurrency. Then we experimentally evaluate the efficiency and scalability of each mechanism. We also analyze the coordination requirements of a decentralized orchestration in the presence of dynamic binding and fault propagation.

Slicing is a well-known program analysis technique for analyzing sequential programs and found useful in debugging, testing and reverse engineering. This paper extends the notion of slicing to concurrent programs with shared memory, interleaving semantics and mutual exclusion. Interference among concurrent threads or processes complicates the computation of slices of concurrent programs. Further, unlike slicing of sequential programs, a slicing algorithm for concurrent programs needs to differentiate between loop-independent data dependence and certain loop-carried data dependences.

This paper describes our experience in developing techniques for repairing date affected programs using standard compiler technology. Starting with date-ness information of certain variables based on their declarations, we propagate this information through all possible control paths, using date inference rules to traverse across individual statements. Our approach is fine grained enough to infer the date-ness of each occurrence of a variable. After detecting date-ness of variables, we renovate programs by applying a transformation using base year strategy. These techniques have been implemented as a tool set for renovating date affected COBOL programs. Copyright © 1999 John Wiley & Sons, Ltd.