Search

This dissertation introduces a hybrid strategy for automated testing of Android applications that combines reinforcement learning and test suite prioritization. These approaches aim to improve the effectiveness of the testing process by employing reinforcement learning algorithms, namely Q-learning and SARSA (State-Action-Reward-State-Action), for automated test case generation. The studies provide compelling evidence that reinforcement learning techniques hold great potential in generating test cases that consistently achieve high code coverage; however, the generated test cases may not always be in the optimal order. In this study, novel test case prioritization methods are developed, leveraging pairwise event interactions coverage, application state coverage, and application activity coverage, so as to optimize the rates of code coverage specifically for SARSA-generated test cases. Additionally, test suite prioritization techniques are introduced based on UI element coverage, test case cost, and test case complexity to further enhance the ordering of SARSA-generated test cases. Empirical investigations demonstrate that applying the proposed test suite prioritization techniques to the test suites generated by the reinforcement learning algorithm SARSA improved the rates of code coverage over original orderings and random orderings of test cases.

Most common vulnerabilities in modern software applications are due to errors in string manipulation code. String constraint solvers are essential components of program analysis techniques for detecting and repairing vulnerabilities that are due to string manipulation errors. In this dissertation, we present an automata-based string constraint solver for vulnerability analysis of string manipulating programs.Given a string constraint, we generate an automaton that accepts all solutions that satisfy the constraint. Our string constraint solver can also map linear arithmetic constraints to automata in order to handle constraints on string lengths. By integrating our string constraint solver to a symbolic execution tool, we can check for string manipulation errors in programs. Recently, quantitative and probabilistic program analyses techniques have been proposed which require counting the number of solutions to string constraints. We extend our string constraint solver with model counting capability based on the observation that, using an automata-based constraint representation, model counting reduces to path counting, which can be solved precisely. Our approach is parameterized in the sense that, we do notassume a finite domain size during automata construction, resulting in a potentially infinite set of solutions, and our model counting approach works for arbitrarily large bounds.We have implemented our approach in a tool called ABC (Automata-Based model Counter) using a constraint language that is compatible with the SMTLIB language specification used by satifiabilty-modula-theories solvers. This SMTLIB interface facilitates integration of our constraint solver with existing symbolic execution tools. We demonstrate the effectiveness of ABC on a large set of string constraints extracted from real-world web applications.We also present automata-based testing techniques for string manipulating programs. A vulnerability signature is a characterization of all user inputs that can be used to exploit a vulnerability. Automata-based static string analysis techniques allow automated computation of vulnerability signatures represented as automata. Given a vulnerability signature represented as an automaton, we present algorithms for test case generation based on state, transition, and path coverage. These automaticallygenerated test cases can be used to test applications that are not analyzable statically, and to discover attack strings that demonstrate how the vulnerabilities can be exploited. We experimentally comparedifferent coverage criteria and demonstrate the effectiveness of our test generation approach.

Abstract: Software testing is an expensive task that consumes around half of a project’s effort. To reduce the cost of testing and improve the software quality, test cases can be produced automatically. Random Testing (RT) is a low cost and straightforward automated test generation approach. However, its effectiveness is not satisfactory. To increase the effectiveness of RT, researchers have developed more effective test generation approaches such as Adaptive Random Testing (ART) which improves the testing by increasing the test case coverage of the input domain. This research proposes new test case generation methods that improve the effectiveness of the test cases by increasing the diversity of the test cases. Numerical, string, and tree test case structures are investigated. For numerical test generation, the use of Centroidal Voronoi Tessellations (CVT) is proposed. Accordingly, a test case generation method, namely Random Border CVT (RBCVT), is introduced which can enhance the previous RT methods to improve their coverage of the input space. The generated numerical test cases by the other methods act as the input to the RBCVT algorithm and the output is an improved set of test cases. An extensive simulation study and a mutant based software testing investigation have been performed demonstrating that RBCVT outperforms previous methods. For string test cases, two objective functions are introduced to produce effective test cases. The diversity of the test cases is the first objective, where it can be measured through string distance functions. The second objective is guiding the string length distribution into a Benford distribution which implies shorter strings have, in general, a higher chance of failure detection. When both objectives are enforced via a multi-objective optimization algorithm, superior string test sets are produced. An empirical study is performed with several real-world programs indicating that the generated string test cases outperform test cases generated by other methods. Prior to tree test generation study, a new tree distance function is proposed. Although several distance or similarity functions for trees have been introduced, their failure detection performance is not always satisfactory. This research proposes a new similarity function for trees, namely Extended Subtree (EST), where a new subtree mapping is proposed. EST generalizes the edit base distances by providing new rules for subtree mapping. Further, the new approach seeks to resolve the problems and limitations of previous approaches. Extensive evaluation frameworks are developed to evaluate the performance of the new approach against previous methods. Clustering and classification case studies are performed to provide an evaluation against different tree distance functions. The experimental results demonstrate the superior performance of the proposed distance function. In addition, an empirical runtime analysis demonstrates that the new approach is one of the best tree distance functions in terms of runtime efficiency. Finally, the study on the string test case generation is extended to tree test case generation. An abstract tree model is defined by a user based on a program under the test. Then, tree test cases are produced according to the model where diversity is maximized through an evolutionary optimization technique. Real world programs are used to investigate the performance of generated test cases where superior performance of the introduced method is demonstrated compared to the previous methods. Further, the proposed tree distance function is compared against the previous functions in the tree test case generation context. The proposed tree distance function outperforms other functions in tree test generation.

Test cases are represented in various formats depending on the process, the technique or the tool used to generate the tests. While different test case representations are necessary, this diversity challenges us in comparing test cases and leveraging strengths among them - a common test representation will help. In this thesis, we define a new Test Case Language (TCL) that can be used to represent test cases that vary in structure and are generated by multiple test generation frameworks. We also present a methodology for transforming test cases of varying representations into a common format where they can be matched and analyzed. With the common representation in our test case description language, we define five advice functions to leverage the testing strength from one type of tests to improve the effectiveness of other type(s) of tests. These advice functions analyze test input values, method call sequences, or test oracles of one source test suite to derive advice, and utilize the advice to amplify the effectiveness of an original test suite. Our assessment shows that the amplified test suite derived from the advice functions has improved values in terms of code coverage and mutant kill score compared to the original test suite before the advice functions applied.