Busca meta-heurística para resolução de CSP em teste de software

Abstract

Os algoritmos de busca meta-heurística vêm sendo pesquisados em inúmeros domínios, inclusive na resolução de restrições. Devido à sua capacidade de atuação em problemas que a solução é desconhecida, são utilizados em diversas situações. Os algoritmos evolutivos são uma família dos algoritmos de busca, que simulam o comportamento da natureza. Os problemas de satisfação de restrição (CSP) são compostos por um conjunto de conjunções de variáveis, caracterizando uma restrição. Valores são associados às variáveis, os quais devem satisfazer a restrição, caso contrário, são considerados inválidos. Problemas de resolução de restrição estão associados a diversos contextos, desde problemas de alocação de recursos a design de circuitos integrados. Algoritmos de busca meta-heurística vêm sendo utilizados para a solução de CSP, resolvendo o problema da limitação dos provadores de teoremas, que necessitam modelar uma teoria para serem capazes de encontrar uma solução. Neste trabalho, investigamos o uso do algoritmo de busca meta heurística em um tipo de teste de software (execução concólica) que é tratado como um problema de CSP. A execução concólica se baseia no teste simbólico, o qual extrai as decisões internas de um programa que formam uma restrição, também conhecidas como Path Condition (PC). Estas restrições são formadas a partir das variáveis de entrada, portanto, a solução de uma restrição determina as entradas necessárias para percorrer um determinado caminho no software. As técnicas clássicas utilizam provadores de teoremas, os quais são limitados a teoria suportada, e métodos de randomização, que geram valores aleatórios para as variáveis, reduzindo a complexidade da restrição. A presente dissertação teve como objetivo criar e analisar o desempenho de solucionadores baseados em algoritmos de busca meta-heurística, sendo comparados às técnicas clássicas utilizadas neste contexto. Os resultados mostraram que o uso de heurísticas de busca pode permitir a criação de novas técnicas de resolução de restrição, no contexto de teste simbólico