Busca meta-heurÃstica para resoluÃÃo de CSP em teste de software

AUTOR(ES)

Mitsuo Takaki

DATA DE PUBLICAÇÃO

2009

RESUMO

The meta-heuristic search algorithms have been researched in several domains, including in constraint satisfaction problem. Due to its good adaptability to be used in problems where the actual solution is unknown, they are applied in innumerous contexts. The evolutive algorithms are a search algorithm family that simulates the nature behavior. The constraint satisfaction problem (CSP) is a set of variables conjunction, compounding a constraint. Values are associated to the variables, which should satisfy the constraint; otherwise, it violates the restriction. CSP are related to innumerous domains, from resource allocation to integrated circuits design. Meta-heuristic search algorithms have been used for solving CSP, surpassing the theorem prover limitation problem that needs a theory modeling in order to be able to find a solution. This work, we investigated the usage of meta-heuristic search algorithms in a kind of software test (concolic execution) that is dealt as a constraint satisfaction problem. The concolic execution is based on the symbolic test, which is a technique used to gather internal decisions of software, which compound a restriction also called as Path Condition (PC). These restrictions are formed by the input variables, thus, the solution of them is used as input data to traverse a specific path in the software. The classical techniques use theorem prover, which are constrained by the theory supported, and randomization methods, that generates random values for the variables, reducing the constraint complexity. The current dissertation had as main objective to create and analyze the performance of meta-heuristic search based solvers, being compared to the classical techniques used in this context. The results have shown that the usage of search heuristics may allow the creation of new constraint satisfaction techniques in the symbolic test domain

ASSUNTO(S)

problema de satisfaÃÃo de restriÃÃo inteligÃncia artificial algoritmos de busca meta-heurÃstica concolic execution constraint satisfaction problem execuÃÃo concÃlica ciencia da computacao meta-heuristic search algorithms

Documentos Relacionados

• OrtorretificaÃÃo digital de imagens de satÃlites de alta resoluÃÃo espacial
• Um protÃtipo de sistema especialista para detecÃÃo e resoluÃÃo de conflitos no seqÃenciamento de aeronaves.
• ObtenÃÃo de radiografia industrial digital de alta resoluÃÃo utilizando radiaÃÃo sincroton e imaging plate
• O algoritmo talus na resoluÃÃo do problema do controle Ãtimo
• A influÃncia dos suportes de representaÃÃo na resoluÃÃo de problemas com estruturas multiplicativas