Rachet - Compatibility Testing of Component-based Systems

Principle Investigators

Related Information

Overall Project Description

Modern component-based systems are typically composed of multiple components, where each component can have multiple versions, evolves over time, and may be developed by independent groups of developers. Since each possible combination of the components and their versions may be realized on an end-user's machine, testing the compatibility of multi-component based systems on top of possible field configurations is very important to improve system quality, and also to rationally manage support activities. However, the large number of potential field configurations makes it very difficult for developers to perform large-scale compatibility testing, so developers often pare down the test set to a small number of popular or default configurations and also must customize the configurations manually.

This project aims at developing methods and a tool called Rachet to support large-scale compatibility testing of evolving component-based systems. The research has so far focused on testing for correct builds of components in various configurations. Rachet features include:

• Compatibility testing of a system build
  

  We regard a system build as a set of components and associated versions that a developer wants to consider as part of the configuration space of a component-based system. We have developed (1) a formal modeling scheme to encode the entire configuration space of the system, (2) a method to produce a reduced set of configurations compared to the exhaustive set of configurations, via a directed sampling approach, that has been shown to effectively identify compatibilities between components in the model , and (3) methods to test configurations on top of virtual machines via hardware virtualization technology.

• Compatibility testing of a sequence of system builds
  

  In order to accommodate component evolution, we have developed (1) algorithms to compute differences in component compatibility between system builds, for a sequence of builds over time, (2) a formal test adequacy criterion based on covering the differences, and (3) cache-aware configuration sampling and testing methods that attempt to reuse effort from previous testing sessions.

• Preference-driven compatibility testing
  

  Developers often have different levels of interest across components and their versions, and also the time and resource available for compatibility testing can be limited. Under these conditions, it is necessary to prioritize the test order of configurations. We have therefore developed a method by which developers can easily specify a preference order for components and their versions. Our prioritization mechanism computes the importance of each configuration based on the specified preferences, and then tests configurations in user preference order.

Modeling the System Configuration Space and Generating Configurations

An Annotated Component Dependency Model (ACDM) encodes the entire configuration space for a system. The model has two parts: a Component Dependency Graph (CDG) and Annotations (Ann). A CDG is a directed acyclic graph used to specify dependencies between components. Ann is used to specify component versions and constraints between components. A CDG has two types of nodes: component nodes (shown as circles) and relation nodes (shown as rectangles). In a CDG, if there is a path between a component node (say c1) to another component (say c2), and if the path does not contain any other component node, we say that c1 directly depends on c2. (e.g., the relation between GFortran and the other blue-colored components in Figure 1.)

We identify all direct dependency relationships between components and for each relationship create concrete instantiations called DD-instances with versions of components in the relationship. We have developed an algorithm that generates a set of configurations that ensures that each DD-instance is tested by at least one configuration.

<Figure 1. CDG for InterComm System>

Test Plan

Each configuration contains a sequence of DD-instances, where each DD-instance encode a component version and a set of other component versions on which the component directly depends. From the observation that configurations often share common sub-sequences, we combine all configurations into a single prefix tree called a test plan. The test plan for the InterComm component is shown in Figure 2. The test plan is executed by dispatching configurations to multiple virtual machines running on a compute grid.

<Figure 2. InterComm test plan and its execution employing 8 client machines>

System Architecture

<Figure 3. Rachet Architecture>

Compatibility Results for Real-World Systems

The Rachet process has been extensively applied to two scientific middlware components, InterComm and PETSc. For the process, we employed up to 4 versions for components in the CDG in Figure 1. We then generated and tested configurations to test all inter-component compatibilitie. We discovered several failure patterns from the test, and conveyed that information to the developers of each package.

Rachet has only been applied for components in the high-performance computing domain. However, we also plan to apply the process to components from other domains, and have started the process for the Sugar interface of the OLPC (One Laptop Per Child) project.