Prof. T.H. Tse (The University of Hong Kong)
Dr W.K. Chan (City University of Hong Kong)
and Prof. Francis C.M. Lau (The University of Hong Kong)

* Supported in part by the General Research Fund of the Research Grants Council of Hong Kong (Project No. 716612).

Testing is the most widely practiced activity that assures software quality. A multithreaded software application accepts an input and may execute different sequences of statements to compute an output. The huge number of possible interleaving sequences of statements for the same input makes it difficult to test the application and detect concurrency failures such as race conditions, which refer to multiple threads accessing the same memory location in an unsynchronized order, with at least one of them through a write access. Their presence often indicates serious problems.

In this project, we propose a CARISMA framework to support a Context-sensitive Approach for Race-condItion test case Selection for Multithreaded software Applications. We study CARISMA in three dimensions:

(a) We propose a memory-based partitioning strategy for race detection, and integrate it with code-based and time-based partitioning. Instead of treating all memory locations as equals, we classify them in terms of their execution contexts. The use of a "similarity" concept and an iterative approach allows us to significantly discard a large number of memory locations or skip the tracking of a large number of memory access operations without compromising the effectiveness of race detection. We further propose random, proportional sampling, and adaptive random test case allocation schemes for race detection.

(b) We propose three context-sensitive test case selection techniques with different granularities: coarse location sampling, fine location sampling, and access sampling. Instead of counting memory accesses, we enhance the effectiveness further by counting only write operations.

(c) CARISMA is designed to work with dynamic data race detection tools, most of which are either based on locksets or the happens-before relation. We construct prototypes and empirical studies to validate the feasibility of integrating our approach with various dynamic race detection tools.

To the best of our knowledge, this is the first major project that comprehensively addresses the selection of test cases to detect race conditions in multithreaded software applications. Our initial finding shows that our proposed approach significantly outperforms existing sampling techniques for data race detection.

Prof. T.H. Tse (The University of Hong Kong),
Dr W.K. Chan (City University of Hong Kong),
and Prof. Ben Kao (The University of Hong Kong)

* Supported in part by the General Research Fund of the Research Grants Council of Hong Kong (Project No. 717811).

The growth of the Internet brings about new software applications whose behaviors are built on individual components (known as services), each of which is selected at runtime among a pool of candidate components provided by different service providers. These applications are known as adaptive service-based software (ASBS). Each involves a program-understandable interface such as a WSDL document, and machine-readable messages typically in XML format.

Testing is the most widely practiced activity that assures software quality. Given a large pool of candidate services, a key property of ASBS is its ultra-late binding to a specific subset (which we call a configuration) at runtime. Reconfigurations may take place whenever necessary. A major difficulty in testing is the need to assure any possible configuration among the large pool of services. This is a fundamental challenge to traditional program testing, where only one implementation is tested at a time. We will collect ASBS from open-source repositories, comprehensively study viable mutation operators for ASBS, and conduct a data analysis of the effect of such operators to answer fundamental research questions. The empirical results will be useful not only for the latter part of this project but also other service-oriented research.

Another challenge in the quality assurance of ASBS is the need to know when testing can be adequate in the presence of an open-ended number of services. We propose two different approaches: First, based on our research on XPath Rewriting Graph (XRG) patterns, we will develop algorithms to produce new XRG patterns that specify adaptive fault relations. We will organize the XRG patterns into a test adequacy subsumption hierarchy. The second approach involves data mining. We will mine failure correlation strengths of definition-use patterns, design XML similarity metrics that correlate with fault-revealing capability, and develop optimization algorithms that maximize the failure correlation strengths and XML similarities.

We will also investigate the efficiency aspect of test case generation. We will construct a prototype system to validate the feasibility of the techniques, and evaluate the techniques by controlled experiments and case studies of industrial-strength applications.

This project is innovative in several aspects. To the best of our knowledge, this is the first major project addressing the testing of ASBS. In particular, it is the first work that empirically studies the propagation of reconfiguration faults; tackles the test adequacy for ultra-late binding of adaptive services; and uses XRG and data mining techniques to unveil test adequacy properties.

Prof. Willy Susilo (University of Wollongong, Australia),
Prof. T.Y. Chen (Swinburne University of Technology, Australia),
Dr Zhi Quan Zhou (University of Wollongong, Australia),
Dr Fei-Ching Kuo (Swinburne University of Technology, Australia),
and Prof. T.H. Tse (The University of Hong Kong),

* Supported in part by a linkage grant of AU$240,000 from the Australian Research Council (Project No. LP100200208) and a partnership fund of AU$165,000 from Partech Systems Pty. Ltd.

Embedded software is a key enabling technology for the majority of Australian manufacturing industries, including strategically important sectors such as the automotive industry. Embedded wireless communication technologies are playing an increasingly significant role in Australia with a wide range of critical applications ranging from natural disaster early warning to personal health monitoring. Embedded wireless communications software, however, is difficult to test and debug owing to the complexity of the operational environment and complications arising from the interplay between software and hardware. This project will develop an effective and automatic technology to alleviate these difficulties and achieve higher quality software.

Prof. T.H. Tse (The University of Hong Kong),
Prof. T.Y. Chen (Swinburne University of Technology, Australia),
and Dr W.K. Chan (City University of Hong Kong)

* Supported in part by the General Research Fund of the Research Grants Council of Hong Kong (Project No. 717308).

In service computing, a service usually collaborates with other services. It may also comprise other services and self-offering actions. The testing of a service is complex and needs to address both the concurrent and sequential dimensions of service composition. As service compositions may be complicated, it is attractive to apply compositional testing, which means the assurance of the overall quality of an entire service composition based on the testing of individual (or groups of) services. Previous work focuses on addressing the concurrent dimension, since the sequentiality aspect is thought of as relatively easy. However, we have identified quite a number of non-trivial problems in the latter aspect that cannot be handled satisfactorily by existing techniques. We propose, therefore, to address the sequential dimension in this project.

We conduct a formal analysis of conformance testing in the context of sequential service composition. We propose to use process algebra as the platform to handle the issue and model a service as a process. We have identified a number of counterexamples to show that there are subtle problems to hinder compositional testing in sequential composition of services. We propose the notion of sequential extension as the basis for tackling such difficulties. A service which sequentially extends another service will enable the latter to be decomposed sequentially into component services. These component services can be abstracted individually and compositionally and, at the same time, the former service should conform to the resultant service composition thus constructed. We target to produce a series of mathematical theorems to show that the notions support compositional conformance testing. To show the practicality of our formal framework, we shall then implement it in a testing tool and conduct experimentation to verify the viability of our proposal.

Prof. T.H. Tse (The University of Hong Kong),
Prof. T.Y. Chen (Swinburne University of Technology, Australia),
and Dr W.K. Chan (City University of Hong Kong)

* Supported in part by the General Research Fund of the Research Grants Council of Hong Kong (Project No. 716507).

Program debugging aims at localizing faults and removing them. Through instrumented executions, dynamic fault localization techniques provide a candidate set of faulty positions in a program.

Pervasive computing is of emerging importance in today's applications. The debugging of such complex systems is crucial for assuring their quality, but the task is difficult because of context-sensitive issues in a volatile and unpredictable environment.

In this project, we propose to study fault-localization techniques for conventional programs and further develop them for pervasive computing. We shall investigate the dynamic properties of program executions and design statistical fault localization techniques for both conventional and context-aware applications. Behavioral statistics are derived from successful and failed runs. We shall contrast not only the former against the latter, but also the changing trends in both situations. Through detailed analyses and modeling of the statistical footprints of how faults diverge and propagate, the project aims at integrating our model with a data-centric approach to effectively and robustly rank the fault-relevance of program predicates, with a view to reducing the number of candidate faulty positions. In particular, footprints specific to pervasive applications will be explored. The integration of testing and debugging tools for wireless sensor network applications will also be studied.

Prof. T.H. Tse (The University of Hong Kong) and
Prof. T.Y. Chen (Swinburne University of Technology, Australia)

* Supported in part by the General Research Fund of the Research Grants Council of Hong Kong (Project No. 717506).

Ubiquitous computing means computing anywhere and at any time. Context-sensitive ubiquitous software dynamically adapts its operations according to the changing environment. One of the strategic directions of Hong Kong is to become a world-class base for supply chain management. Ubiquitous middleware-based sensor network systems are envisaged to be an essential enabling technology. Nevertheless, many researchers have emphasized the difficulties in assuring the quality of such software, because context-sensitive applications operate in a highly volatile and unpredictable environment. We were the first research group to embark on their testing techniques. We propose a major project to comprehensively address both the integration and unit testing of these systems.

In integration testing, we propose a model in Communicating Sequential Processes to generate test cases that conform to the components in a ubiquitous environment. We make use of a notion of anti-extension, which can help to alleviate the state-explosion problem in test case generation.

Context detections and function activations are the duties of the middleware. In unit testing, test oracles may not be immediately available for a component under test. We propose the application of metamorphic testing to solve the problem, focusing on isotropic context properties. They can reveal failures not identifiable by conventional testing methods.

This project has important theoretical and practical implications. It will solve the major difficulties in testing complex context-sensitive middleware-based ubiquitous software. It will also illustrate the usefulness of formal approaches to software testing in practical situations.