Applications of information theory and artificial intelligence to software testing

Created by W.Langdon from gp-bibliography.bib Revision:1.8051

@PhdThesis{Ibias-Martinez:thesis,

• author = "Alfredo {Ibias Martinez}",
• title = "Applications of information theory and artificial intelligence to software testing",
• school = "Facultad de Informatica, Universidad Complutense de Madrid",
• year = "2021",
• address = "Spain",
• month = dec,
• keywords = "genetic algorithms, genetic programming, SBSE, ACO, Artificial intelligent, computer Algorithms, computer software, Software Testing, Information Theory, Artificial Intelligence, Evolutionary Algorithms, Machine Learning, Failed Error Propagation (FEP), Test Case Generation, Software Product Lines, Mutation Testing",
• URL = "https://eprints.ucm.es/id/eprint/74119/",
• URL = "https://books.google.co.uk/books?id=Np0yzwEACAAJ",
• URL = "https://eprints.ucm.es/id/eprint/74119/1/T43374.pdf",
• size = "276 pages",
• abstract = "Software Testing is a critical field for the software industry, as it has the main tools used to ensure the reliability of the produced software. Currently, more than 50percent of the time and resources for creating a software product are diverted to testing tasks, from unit testing to system testing. Moreover, there is a huge interest into automatising this field, as software gets bigger and the amount of required testing increases. However, Software Testing is not only an industry oriented field; it is also a really interesting field with a noble goal (improving the reliability of software systems) that at the same time is full of problems to solve. Therefore, it leaves space for imagination to dream and try to address such problems through the application of tools from other fields. In this thesis, such fields are Information Theory and Artificial Intelligence. Information Theory is a field with a strong mathematical basis. Its main goal is to measure the information of a string based on the commonality of its components. Artificial Intelligence is an algorithmic field that tries to approximate solutions for exponentially complex problems. Both fields are full of tools and methodologies that could help addressing some of the problems that Software Testing arise. Moreover, although both fields can seem disparate, with tools that would be better fitted to solve different kinds of problems, in fact that is not always the case. Along the research carried out during this thesis we found multiple situations where the use of tools from Information Theory improves an Artificial Intelligence-based solution and vice versa. Actually, these synergies make this thesis a compact work more than a compilation of methods.

  The main goal of this thesis is, therefore, to address different problems from the Software Testing field and devise ways of solving (or approximate a solution for) such problems using tools and results coming from the Information Theory and Artificial Intelligence fields. Specifically, this thesis addresses the Failed Error Propagation (FEP) problem, the test case generation problem, the Integration Testing of Software Product Lines (SPLs) problem, and the selection of hard-to-kill mutants for Mutation Testing problem. These four problems are addressed from different perspectives, looking for the best method to try to solve each of them.

  This way, for the test case generation problem we propose both an evolutionary method based on a Grammar-Guided Genetic Programming Algorithm and an Information Theory-based measure (initially developed to choose between test cases) to guide such algorithm, with the goal of generating test cases with high fault finding capability. This is one of those cases where both fields join forces to obtain really good solutions. Additionally, we develop a Grammar Guided Genetic Programming Algorithm to generate test cases guided by coverage metrics, with the goal of increasing the coverability of the produced test cases.

  For the Failed Error Propagation problem our work focuses on the use of Information Theory based measures to address it. Specifically, we focus on a previously proposed information theoretic measure called Squeeziness that measures the likelihood of FEP in a System Under Test (SUT), and we adapt it to work in a black-box scenario, in a non-deterministic one, and even to work with notions of entropy different from the original Shannon's entropy. Additionally, we develop a tool to automatically compute this last version. It is inside this tool where another case of these two fields helping each other can be found: we implement an Artificial Neural Network to automatically estimate the best notion of entropy to use for the given SUT.

  In another line of work, our research to address the selection of hard-to-kill-mutants problem delves in the idea of using swarm intelligence to solve a complex problem. Specifically, with the goal of reducing the amount of useful mutants, we develop a swarm intelligence algorithm, inspired in the Particle Swarm Optimisation one, to decide which mutants are the harder-to-kill ones. Finally, in order to solve the Integration Testing of SPLs problem we use an Ant Colony Optimisation algorithm to select features either with a low testing cost or with a high probability of being requested. The goal is to simplify the testing processes through the reduction of the number of feature combinations needed to test an SPL.

  The outcomes of all these proposals are relevant, improve the state-of-the-art and set new precedents for future work. Moreover, they open newlines of work for further development of the proposals and for improving the obtained solutions. Thus, this thesis makes its humble contribution to the aforementioned fields, for the enjoyment of whoever find it interesting.",

• notes = "also known as \cite{martinez2022applications}

  In english

  Supervisor: Manuel Nunez Garcia",

}

Genetic Programming entries for Alfredo Ibias

Citations