Computational Complexity of Edge Coverage Problem for Constrained Control Flow Graphs

1. Problema Investigado

O artigo aborda o problema de cobertura de arestas (Edge Coverage - EC) em Gráficos de Fluxo de Controle (CFGs) que foram estendidos com restrições explícitas (cCFGs).

• Contexto: No teste de software de caixa branca, a cobertura de arestas é um critério fundamental para garantir que todas as transições entre blocos de código sejam testadas.
• A Lacuna Semântica: Os CFGs tradicionais são frequentemente permissivos demais, admitindo caminhos de execução que são semanticamente inviáveis (não podem ocorrer na prática), violam padrões de execução obrigatórios ou excedem custos de execução realistas.
• O Desafio: O objetivo é determinar a complexidade computacional de encontrar um conjunto de testes que atinja a cobertura de todas as arestas do gráfico, respeitando simultaneamente um conjunto de restrições definidas sobre os vértices (nós) do gráfico.

2. Metodologia e Definições

Os autores definem formalmente o problema utilizando um cCFG como uma 6-tupla $G = (V, E, s, t, C, X)$, onde $C$ é um conjunto de restrições e $X$ define o tipo de restrição.

São analisados cinco tipos de restrições:

1. POSITIVE ($C^+$): Exige que, em pelo menos um caminho de teste, o vértice $x$ preceda o vértice $y$.
2. NEGATIVE ($C^-$): Proíbe que qualquer caminho de teste contenha $x$ precedendo $y$.
3. ONCE ($C^1$): Exige que exista exatamente um caminho de teste onde $x$ precede $y$, com a condição adicional de que $x$ e $y$ apareçam apenas uma vez nessa ordem específica naquele caminho.
4. MAX ONCE ($C^{\le 1}$): Permite que $x$ preceda $y$ em no máximo um caminho de teste.
5. ALWAYS ($C^=$): Se um caminho de teste contém $x$, ele deve conter $y$ posteriormente no mesmo caminho.

A metodologia envolve a análise de complexidade computacional através de:

• Reduções Polinomiais: Demonstração de que o problema é NP-completo reduzindo instâncias do problema 3-SAT (ou variações como POSITIVE 1-in-3 SAT) para o problema de cobertura de arestas com restrições.
• Construção de Gadgets: Criação de estruturas de gráfico específicas (gadgets) que simulam cláusulas e variáveis lógicas, onde a cobertura de arestas e o respeito às restrições correspondem à satisfação da fórmula booleana.
• Algoritmos FPT (Fixed-Parameter Tractable): Desenvolvimento de algoritmos que são eficientes quando um parâmetro específico (número de restrições) é pequeno, mesmo que o problema geral seja NP-difícil.

3. Principais Contribuições e Resultados

O artigo estabelece a fronteira de complexidade para o problema de cobertura de arestas sob diferentes tipos de restrições:

A. Complexidade de Decisão (NP-Completude)

• POSITIVE ($C^+$): O problema é Polinomial (P). É possível construir um conjunto de testes em tempo polinomial verificando a alcançabilidade entre os vértices das restrições e adicionando caminhos específicos para satisfazê-las.
• NEGATIVE ($C^-$), ONCE ($C^1$), MAX ONCE ($C^{\le 1}$) e ALWAYS ($C^=$): O problema de decidir se existe um conjunto de testes viável que atinja a cobertura de arestas é NP-Completo.
  • As provas para $C^-$, $C^1$ e $C^{\le 1}$ utilizam reduções do 3-SAT padrão.
  • A prova para $C^=$ utiliza uma redução do problema POSITIVE 1-in-3 SAT.
  • Importante: A NP-completude mantém-se válida mesmo para classes restritas de grafos, como grafos acíclicos (DAGs).

B. Tratamento de Parâmetros Fixos (FPT) para Restrições Negativas

• Embora o problema com restrições NEGATIVE seja NP-completo no geral, os autores apresentam um algoritmo FPT (Fixed-Parameter Tractable) em relação ao número de restrições.
• Algoritmo Proposto: O algoritmo HasEdgeCoverageWithNegative explora o fato de que um caminho válido deve ser "c-apropriado" (c-proper) em relação a uma sequência de vértices das restrições.
  • O algoritmo gera todas as permutações válidas das restrições (limitado por $O(2^{|C|!})$).
  • Para cada permutação, utiliza uma sub-rotina FindProperPath que constrói caminhos no grafo induzido, garantindo que as restrições negativas sejam respeitadas.
  • A complexidade é $f(|C|) \cdot p(|V| + |E|)$, onde $f$ é uma função exponencial apenas no número de restrições e $p$ é polinomial no tamanho do grafo.

4. Significado e Impacto

• Fundamentação Teórica: Este trabalho preenche uma lacuna na literatura, fornecendo a primeira análise teórica rigorosa da complexidade do teste baseado em caminhos com restrições. Antes disso, não havia clareza sobre a dificuldade computacional de gerar testes que respeitassem regras semânticas complexas.
• Implicações Práticas:
  • Para restrições POSITIVE, ferramentas de teste podem ser desenvolvidas com garantias de eficiência.
  • Para restrições NEGATIVE, ONCE, MAX ONCE e ALWAYS, os resultados indicam que encontrar o conjunto de testes ótimo é computacionalmente intratável para instâncias grandes. Isso justifica o uso de heurísticas ou a limitação do número de restrições em ferramentas práticas.
  • O algoritmo FPT para restrições negativas oferece uma solução viável para sistemas onde o número de regras de exclusão (ex: "após o contrato assinado, não pode haver auditoria") é pequeno, mas o código é grande.
• Direções Futuras: Os autores sugerem investigar se algoritmos FPT existem para os outros tipos de restrições (ONCE, MAX ONCE, ALWAYS) e estender o modelo para permitir múltiplos tipos de restrições simultaneamente no mesmo gráfico, o que seria mais fiel aos sistemas reais.

Conclusão

O artigo demonstra que a introdução de restrições semânticas em gráficos de fluxo de controle transforma drasticamente a complexidade do problema de cobertura de arestas. Enquanto restrições de "presença" (POSITIVE) são tratáveis, restrições de "ausência", "contagem" e "implicação" tornam o problema NP-completo, exigindo abordagens especializadas como algoritmos FPT para ser resolvido na prática em cenários com poucas restrições.