Search

Developing software is difficult. A challenging part of production development is ensuring programs are correct and fast, two properties satisfied with software testing and optimisation. While both tasks still rely on manual effort and expertise, the recent surge in software applications has led them to become tedious and time-consuming. Under this fast-pace environment, manual testing and optimisation hinders productivity significantly and leads to error-prone or sub-optimal programs that waste energy and lead users to frustration. In this thesis, we propose three novel approaches to automate software testing and optimisation with modern language models based on deep learning. In contrast to our methods, existing few techniques in these two domains have limited scalability and struggle when they face real-world applications. Our first contribution lies in the field of software testing and aims to automate the test oracle problem, which is the procedure of determining the correctness of test executions. The test oracle is still largely manual, relying on human experts. Automating the oracle is a non-trivial task that requires software specifications or derived information that are often too difficult to extract. We present the first application of deep language models over program execution traces to predict runtime correctness. Our technique classifies test executions of large-scale codebases used in production as "pass" or "fail". Our proposed approach reduces by 86% the amount of test inputs an expert has to label by training only on 14% and classifying the rest automatically. Our next two contributions improve the effectiveness of compiler optimisation. Compilers optimise programs by applying heuristic-based transformations constructed by compiler engineers. Selecting the right transformations requires extensive knowledge of the compiler, the subject program and the target architecture. Predictive models have been successfully used to automate heuristics construction but their performance is hindered by a shortage of training benchmarks in quantity and feature diversity. Our next contributions address the scarcity of compiler benchmarks by generating human-likely synthetic programs to improve the performance of predictive models. Our second contribution is BENCHPRESS, the first steerable deep learning synthesizer for executable compiler benchmarks. BENCHPRESS produces human-like programs that compile at a rate of 87%. It targets parts of the feature space previously unreachable by other synthesizers, addressing the scarcity of high-quality training data for compilers. BENCHPRESS improves the performance of a device mapping predictive model by 50% when it introduces synthetic benchmarks into its training data. BENCHPRESS is restricted by a feature-agnostic synthesizer that requires thou sands of random inferences to select a few that target the desired features. Our third contribution addresses this inefficiency. We develop BENCHDIRECT, a directed language model for compiler benchmark generation. BENCHDIRECT synthesizes programs by jointly observing the source code context and the compiler features that are targeted. This enables efficient steerable generation on large scale tasks. Compared to BENCHPRESS, BENCHDIRECT matches successfully 1.8× more Rodinia target benchmarks, while it is up to 36% more accurate and up to 72% faster in targeting three different feature spaces for compilers. All three contributions demonstrate the exciting potential of deep learning and language models to simplify the testing of programs and the construction of better optimi sation heuristics for compilers. The outcomes of this thesis provides developers with tools to keep up with the rapidly evolving landscape of software engineering.

Blockchains are the underlying technology for making secure online transactions using cryptocurrencies such as Bitcoins and Ethers. Executing, verifying, and enforcing credible transactions on permissionless blockchains is done using smart contracts. Smart contracts are publicly available programs that run on the Ethereum network and can be implemented by Solidity language. Solidity is the most popular programming language to implement smart contracts. Smart contracts help exchange money, property, shares or anything of value in a transparent, conflict-free way while reducing transaction costs associated with third-party contractors. A major challenge in developing smart contracts is to guarantee that they are correct and free of security weaknesses, since bugs in their implementation may result in significant financial losses. For example, a single line that triggered integer overflow vulnerability in the BeautyChain (BECToken) contract caused a large number of stolen tokens - worth approximately $12 million. In the last few years, analysis and testing of smart contracts have raised considerable interest, and numerous techniques have been proposed to check the presence of vulnerabilities in them. However, the security and correctness of smart contracts is still a big question in academia and industry because of the problems in proposed techniques such as high false-positive rate, path explosion, and lack of support for Solidity constructs. This thesis presents novel approaches for automated test input generation and test effectiveness measurement for Solidity smart contracts. To achieve this, we address significant challenges related to smart contract execution, namely Solidity languagespecific data and features, and the extent of vulnerability detection. The thesis makes the following four contributions within automated testing. First, we propose an analysis, instrumentation, optimisation and code generation framework, SIF, using pre-defined helper functions that do not require any expert Solidity programming. This framework is capable of providing an interface to easily and effectively understand, manipulate and analyse Solidity code. Second, we present an automated framework, SolAnalyser, for detecting vulnerabilities over Solidity smart contracts. Our framework automatically inserts relevant assert statements as pre and post conditions for each arithmetic operation in the contract. Then, it generates a smart contract with relevant property assertions as output. Finally, our framework executes the generated smart contract with property assertions with automatically generated test inputs (from Contribution 3), and reports vulnerabilities, if any. Third, we implement different test input generation techniques for Solidity smart contracts. The techniques we implemented are based on fuzzing, genetic algorithm (GA), and satisfiability modulo theories (SMT) solver. Fuzzing relies on random input generation depending on contract interface. GA imitates the natural evolution to produce test input. SMT solver aims to solve given constraints for a practical subset of inputs. As the fourth contribution, we implement a framework, CovCal, to evaluate the effectiveness of different test input generation techniques. CovCal analyses them with respect to different coverage metrics, which are specific to Solidity structure, and fault-finding ability. We evaluate our frameworks, i.e., SIF, SolAnalyser and CovCal, and the testing techniques under different smart contract datasets that contain 1755 smart contracts and a wide variety of the Solidity constructs. We can infer the following from these experiments: (1) SIF is capable of supporting all the Solidity constructs, correctly instrumenting the Solidity code, and is user-friendly. (2) SolAnalyser is capable of detecting defined vulnerability types. (3) CovCal is capable of measuring the effectiveness of the test inputs automatically, in terms of code coverage and fault-finding capability in the Solidity smart contracts. (4) All of these techniques are able to generate valid test inputs for the Solidity smart contracts and detect any vulnerabilities in the tested contracts. All of these implementations and evaluations are open-sourced and have been used by other research groups.

Quantum machine learning (QML) has proven to be a fruitful area in which to search for applications of quantum computers. This is particularly true for those available in the near term, so called noisy intermediate-scale quantum (NISQ) devices. In this thesis, we develop and study QML algorithms in three application areas. We focus our attention towards heuristic algorithms of a variational (meaning hybrid quantum-classical) nature, using parameterised quantum circuits as the underlying quantum machine learning model. The variational nature of these models makes them especially suited for NISQ computers. We order these applications in terms of the increasing complexity of the data presented to them. Firstly, we study a variational quantum classifier in supervised machine learning, and focus on how (classical) data, feature vectors, may be encoded in such models in a way that is robust to the inherent noise on NISQ computers. We provide a framework for studying the robustness of these classification models, prove theoretical results relative to some common noise channels, and demonstrate extensive numerical results reinforcing these findings. Secondly, we move to a variational generative model called the Born machine, where the data becomes a (classical or quantum) probability distribution. Now, the problem falls into the category of unsupervised machine learning. Here, we develop new training methods for the Born machine which outperform the previous state of the art, discuss the possibility of quantum advantage in generative modelling, and perform a systematic comparison of the Born machine relative to a classical competitor, the restricted Boltzmann machine. We also demonstrate the largest scale implementation (28 qubits) of such a model on real quantum hardware to date, using the Rigetti superconducting platform. Finally, for our third QML application, the data becomes purely quantum in nature. We focus on the problem of approximately cloning quantum states, an important primitive in the foundations of quantum mechanics. For this, we develop a variational quantum algorithm which can learn to clone such states, and show how this algorithm can be used to improve quantum cloning fidelities on NISQ hardware. Interestingly, this application can be viewed as either supervised or unsupervised in nature. Furthermore, we demonstrate how this can algorithm can be used to discover novel implementable attacks on quantum cryptographic protocols, focusing on quantum coin flipping and key distribution as examples. For the algorithm, we derive differentiable cost functions, prove theoretical guarantees such as faithfulness, and incorporate state of the art methods such as quantum architecture search.

Graphics Processing Units (GPUs) are massively parallel processors offering performance acceleration and energy efficiency unmatched by current processors (CPUs) in computers. These advantages along with recent advances in the programmability of GPUs have made them widely used in various general-purpose computing domains. However, this has also made testing GPU kernels critical to ensure that their behaviour meets the requirements of the design and specification. Despite the advances in programmability, GPU kernels are hard to code and analyse due to the high complexity of memory sharing patterns, striding patterns for memory accesses, implicit synchronisation, and combinatorial explosion of thread interleavings. Existing few techniques for testing GPU kernels use symbolic execution for test generation that incur a high overhead, have limited scalability and do not handle all data types. In this thesis, we present novel approaches to measure test effectiveness and generate tests automatically for GPU kernels. To achieve this, we address significant challenges related to the GPU execution and memory model, and the lack of customised thread scheduling and global synchronisation. We make the following contributions: First, we present a framework, CLTestCheck, for assessing the quality of test suites developed for GPU kernels. The framework can measure code coverage using three different coverage metrics that are inspired by faults found in real kernel code. Fault finding capability of the test suite is also measured by the framework to seed different types of faults in the kernel and reported in the form of mutation score, which is the ratio of the number of uncovered faults to the total number of seeded faults. Second, with the goal of being fast, effective and scalable, we propose a test generation technique, CLFuzz, for GPU kernels that combines mutation-based fuzzing for fast test generation and selective SMT solving to help cover unreachable branches by fuzzing. Fuzz testing for GPU kernels has not been explored previously. Our approach for fuzz testing randomly mutates input kernel argument values with the goal of increasing branch coverage and supports GPU-specific data types such as images. When fuzz testing is unable to increase branch coverage with random mutations, we gather path constraints for uncovered branch conditions, build additional constraints to represent the context of GPU execution such as number of threads and work-group size, and invoke the Z3 constraint solver to generate tests for them. Finally, to help uncover inter work-group data races and replay these bugs with fixed work-group schedules, we present a schedule amplifier, CLSchedule, that simulates multiple work-group schedules, with which to execute each of the generated tests. By reimplementing the OpenCL API, CLSchedule executes the kernel with a fixed work-group schedule rather than the default arbitrary schedule. It also executes the kernel directly, without requiring the developer to manually provide boilerplate host code. The outcome of our research can be summarised as follows: 1. CLTestCheck is applied to 82 publicly available GPU kernels from industry-standard benchmark suites along with their test suites. The experiment reveals that CLTestCheck is capable of automatically measuring the effectiveness of test suites, in terms of code coverage, faulting finding capability and revealing data races in real OpenCL kernels. 2. CLFuzz can automatically generate tests and achieve close to 100% coverage and mutation score for the majority of the data set of 217 GPU kernels collected from open-source projects and industry-standard benchmarks. 3. CLSchedule is capable of exploring the effect of work-group schedules on the 217 GPU kernels and uncovers data races in 21 of them. The techniques developed in this thesis demonstrate that we can measure the effectiveness of tests developed for GPU kernels with our coverage criteria and fault seeding methods. The result is useful in highlighting code portions that may need developers' further attention. Our automated test generation and work-group scheduling approaches are also fast, effective and scalable, with small overhead incurred (average of 0.8 seconds) and scalability to large kernels with complex data structures.

Today, software is all around us, impacting our everyday lives in fundamental ways. Developing software whose behaviour is reliable, predictable and correct is therefore crucial. This has made software testing a critical part of the development process and has led to the emergence of rigorous testing practices and standards. Testing any non-trivial system, however, is time-consuming and takes up the bulk of development time. Modern software engineering practices involve the repeated execution of large test suites, as part of regular build, test and release cycles. A common approach to speeding up testing without sacrificing rigour is distributing test executions among computer clusters and cloud servers, but this can be complex and expensive due to the costs of testing infrastructure and energy consumption. This thesis presents a novel approach to accelerating test execution by parallelising it using Graphics Processing Units (GPUs) - powerful and low-cost hardware accelerators that are readily available in the majority of modern desktops. It demonstrates that GPUs can be used to dramatically reduce test execution time at a lower cost compared to other parallel approaches. To achieve this, it addresses significant challenges related to usability, performance and scope, and makes three separate contributions: First, a GPU testing framework, ParTeCL, is developed to automatically transform the system under test into GPU source code and launch test execution in parallel on the GPU threads. ParTeCL performs the entire testing process transparently without requiring any expert GPU programming and architecture knowledge. Second, two types of systems are used to evaluate the applicability and effectiveness of the approach - sequential C programs form the embedded systems domain and Finite State Machine (FSM) models. To enable testing them on the GPU, compiler-based transformations and FSM implementations are developed and included in ParTeCL. Finally, GPU performance is extensively analysed and optimised through a combination of standard and domain specific techniques. Evaluation on programs from the two domains demonstrates that the GPU outperforms a standard 16-core Central Processing Unit (CPU) by up to 4× (avg. 1.4×) for embedded systems and up to 9×(avg. 4.5×) for FSMs. The techniques developed in this thesis demonstrate the exciting possibilities of using specialised hardware architectures, such as GPUs, for the acceleration of software test execution. Through integration into the testing process, they could provide rapid feedback, reducing the amount of costly bug-fixing in later stages of development.

The requirements and responsibilities assumed by software have increasingly rendered it to be large and complex. Testing to ensure that software meets all its requirements and is free from failures is a difficult and time-consuming task that necessitates the use of large test suites, containing many test cases. Time needed to compile and execute large test suites has become prohibitive. Current optimization techniques aim to reduce the test suite size by removing redundant test cases. However, as systems become larger, the number of essential test cases is still very large and affects the software life-cycle. In this thesis, we explore techniques for reducing the compilation and the execution time of test suites without removing any test cases or changing computing infrastructure. All of our proposed techniques can be used in conjunction with existing test suite optimisations. 1. For test suite compilation, we propose a data transformation that reduces the number of instructions in the test code, which in turn reduces compilation time. Using two well known compilers, GCC and Clang, we conduct empirical evaluations using subject programs from industry standard benchmarks and an industry provided program. We evaluate compilation speedup, execution time, scalability and correctness of the proposed test code transformation. 2. For test suite execution, we propose a novel approach to improve instruction locality across test case executions. Our approach measures the distance between test case executions (number of different instructions). We then schedule the test cases for execution so that the distance between neighboring test cases is minimised. We empirically evaluate our approach with 20 subject programs and test suites from the SIR repository, EEMBC suite and LLVM Symbolizer to compare execution times and cache misses with test case orderings using our approach versus a traditional ordering maximising coverage and random permutations. We also assess overhead of algorithms in generating orderings that optimise instruction cache locality. 3. In our final contribution, we target execution time of heterogeneous test suites and assess the effect of device-based test case scheduling. We propose a test case scheduling algorithm which improves the load balancing between multiple devices of a heterogeneous system in an attempt to reduce the overall test suite execution time. We conduct empirical evaluation on a large-scaled, industrial test suite targeting implementations of the SYCL standard which has been developed by Codeplay Software. The outcome of our research can be summarized as follows: 1. Our data transformation approach resulted in significant compilation speedups in the range of 1.3×to 69×. Our experiments show that the gains in compilation time allow significantly more test cases to be included in test suites, improving scalability of test code compilation. 2. Our instruction-based test case scheduling algorithms were able to achieve a maximum execution speedup of 29.48%. Performance gains were considerable for programs and test suites where the average number of different instructions executed between test cases was high. 3. Finally, we found that a maximum of 25.42% speed-up is achieved by our device based test scheduling algorithm when compared to parallel test case execution of a heterogeneous test suite without test scheduling. Our proposed techniques are able to significantly reduce the compilation as well as the execution time of test suites without eliminating any test cases or upgrading computing infrastructure. Our data transformation results in faster test code compilation while our test case scheduling algorithms achieve significant speed-ups for programs executing on single-CPU, multi-CPU as well as heterogeneous architectures. As systems get more complex, they require frequent and extensive testing. Our techniques provide safe and efficient means of compiling and executing test suites which, in combination with existing test suite optimisations, can significantly reduce the cost of software testing.