published_or_final_version / abstract / Computer Science / Master / Master of Philosophy

published_or_final_version / abstract / Computer Science / Doctoral / Doctor of Philosophy

Software testing is the most widely practiced approach to assure the correctness of programs. Despite decades of research progress, software testing is still considered very resource-demanding and time-consuming. In the recent decade, the wide adoption of multithreaded programs and the service-based architecture has further aggravated the problem that we are facing. In this thesis, we study issues in software testing where resource constraints (such as time spent and memory space allocated) are important considerations, and we look for testing techniques that are significantly advanced in effectiveness and efficiency given limited quotas of resources, which we refer to as budget. Our main focus is on two types of systems: concurrent systems and service-based systems. The concurrent system is a class of computing system where programs are designed as collections of interacting and parallel computational processes. Unfortunately, concurrent programs are well known to be difficult to write and test: various concurrency bugs still exist in heavily-tested programs. To make it worse, detecting concurrency bugs is expensive, which is, for example, notorious for dynamic detection techniques that target high precision. This thesis proposes a dynamic sampling framework, CARISMA, to reduce the overhead dramatically while still largely preserving the bug detection capability. To achieve its goal, CARISMA intelligently allocates the limited budget on the computation resource through sampling. The core of CARISMA is a budget estimation and allocation framework whose correctness has been proven mathematically. Another source of cost comes from the nondeterministic nature of concurrent systems. A common practice to test concurrent system is through stress testing where a system is executed with a large number of test cases to achieve a high coverage of the execution space. Stress testing is inherently costly. To this end, it is critical that the bug detection for each execution is effective, which demands a powerful test oracle. This thesis proposes such a test oracle, OLIN, which reports anomalies in the concurrent executions of programs. OLIN finds concurrency bugs that are consistently missed by previous techniques and incurs low overhead. OLIN can achieve a higher effectiveness within given time and computational budgets. Service-based systems are composed of loosely coupled and unassociated units of functional units and are often highly concurrent and distributed. We have witnessed their prosperity in recent decades. Service-based systems are highly dynamic and regression testing techniques are applied to ensure their previously established functionality and correctness are not adversely affected by subsequent evolutions. However, regression testing is expensive and our thesis focuses on the prioritization of regression test cases to improve the effectiveness of testing within predefined constraints. This thesis proposes a family of prioritization metrics for regression testing of location-based services and presents a case study to evaluate their performance. In conclusion, this thesis makes the following contributions to software testing and analysis: (1) a dynamic sampling framework for concurrency bug detection, (2) a test oracle for concurrent testing, and (3) a family of test case prioritization techniques for service-based systems. These contributions significantly improve the effectiveness and efficiency of resource utilization in software testing. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Software maintenance is an expensive part of the software lifecycle: estimates put its cost at up to two-thirds of the entire cost of software. Regression testing, which tests software after it has been modified to help assess and increase its reliability, is responsible for a large part of this cost. Thus, making regression testing more efficient and effective is worthwhile. This thesis performs two experiments with regression testing techniques. The first experiment involves two regression test selection techniques, Dejavu and Pythia. These techniques select a subset of tests from the original test suite to be rerun instead of the entire original test suite in an attempt to save valuable testing time. The experiment investigates the cost and benefit tradeoffs between these techniques. The data indicate that Dejavu can occasionally select smaller test suites than Pythia while Pythia often is more efficient at figuring out which test cases to select than Dejavu. The second experiment involves the investigation of program spectra as a tool to enhance regression testing. Program spectra characterize a program's behavior. The experiment investigates the applicability of program spectra to the detection of faults in modified software. The data indicate that certain types of spectra identify faults on a consistent basis. The data also reveal cost-benefit tradeoffs among spectra types. / Graduation date: 2000

published_or_final_version / Computer Science and Information Systems / Master / Master of Philosophy

Thesis (M.S.)--University of Hawaii at Manoa, 2006. / Includes bibliographical references (leaves 96-97). / x, 97 leaves, bound ill. 29 cm

Testing and Debugging are often the most difficult phase of software development. This is especially true of embedded systems which are usually concurrent, have real-time performance and correctness constraints and which execute in the field in an environment which may not permit internal scrutiny of the software behaviour. Although good software engineering practices help, they will never eliminate the need for testing and debugging. This is because failings in the specification and design are often only discovered through testing and understanding these failings and how to correct them comes from debugging. These observations suggest that embedded software should be designed in a way which makes testing and debugging easier and that tools which support these activities are required. Due to the often hostile environment in which the finished embedded system will function, it is necessary to have a platform which allows the software to be developed and tested "in vitro". The Testbed system achieves these goals by providing dynamic modification and process migration facilities for use during development as well as powerful monitoring and background debugging support. These facilities are built on a basic run-time harness supporting an event-driven programming model with a global communication mechanism. This programming model is well suited to the reactive nature of embedded systems. The main research contributions of this work are in the areas of finding deadlock-free, path-optimal routings for networks and of dynamic modification with automated conversion of data which may include pointers.

This dissertation examines, based on a case study, the feasibility of using model programs as a practical solution to the oracle problem in software testing. The case study pertains especially to testing algorithmically complex software and it evaluates the approach proposed in this dissertation against testing that is based on manual outcome prediction. In essence, the experiment entailed developing a model program for testing a medium-size industrial application that implements a complex scheduling algorithm. One of the most difficult tasks in software testing is to adjudicate on whether a program passed or failed a test. Because that usually requires "predicting" the correct program outcome, the problem of devising a mechanism for correctness checking (i.e., a "test oracle") is usually referred to as the "oracle problem". In practice, the most direct solution to the oracle problem is to pre-calculate manually the expected program outcomes. However, especially for algorithmically complex software, that is usually time consuming and error-prone. Although alternatives to the manual approach have been suggested in the testing literature, only few formal experiments have been conducted to evaluate them. A potential alternative to manual outcome prediction, which is evaluated in this dissertation, is to write one or more model programs that conform to the same functional specification (or parts of that specification) as the primary program (Le., the software to be delivered). Subjected to the same input, the programs should produce identical outputs. Disagreements indicate either the presence of software faults or specification defects. The absence of disagreements does not guarantee the correctness of the results since the programs may erroneously agree on outputs. However, if the test data is adequate and the implementations are diverse, it is unlikely that the programs will consistently fail and still reach agreement. This testing approach is based on a principle that is applied primarily in software fault-tolerance: "N-version diversity". In this dissertation, the approach is called "testing using M model programs" or, in short, "M-mp testing". The advantage of M-mp testing is that the programs, together, constitute an approximate, but continuously perfecting, test oracle. Human assistance is required only to analyse and arbitrate program disagreements. Consequently, the testing process can be automated to a very large degree. The main disadvantage of the approach is the extra effort required for constructing and maintaining the model programs. The case study that is presented in this dissertation provides prima facie evidence to suggest that the M-mp approach may be more cost-effective than testing based on manual outcome prediction. Of course, the validity of such a conclusion is dependent upon the specific context in which the experiment was carried out. However, there are good indications that the results of the experiment are generally applicable to testing algorithmically complex software. / Dissertation (MSc (Computer Science))--University of Pretoria, 2007. / Computer Science / unrestricted

Regression testing is an expensive testing process used to validate changes made to previously tested software. Different regression testing techniques can have different impacts on the cost-effectiveness of testing. This cost-effectiveness can also vary with different characteristics of test suites. One such characteristic, test suite granularity, reflects the way in which test cases are organized within a test suite; another characteristic, test grouping technique, involves the way in which the test inputs are grouped into test cases. Various cost-benefits tradeoffs have been attributed to choices of test suite granularity and test grouping technique, but little research has formally examined these tradeoffs. In this thesis, we conducted several controlled experiments, examining the effects of test suite granularity and test grouping technique on the costs and benefits of several regression testing methodologies across ten releases of a non-trivial software system, empire. Our results expose essential tradeoffs to consider when designing test suites for use in regression testing evolving systems. / Graduation date: 2003

published_or_final_version / abstract / Computer Science / Master / Master of Philosophy