Computational Complexity of Edge Coverage Problem for Constrained Control Flow Graphs

1. Introduzione e Definizione del Problema

Il paper affronta il problema della copertura degli archi (Edge Coverage - EC) nel contesto del testing software white-box, estendendo i tradizionali Grafi del Flusso di Controllo (CFG) con vincoli espliciti.

• Il Problema: Il testing basato sui percorsi standard (path-based testing) soffre di un "divario semantico" (semantic gap). I CFG puri ammettono percorsi che sono sintatticamente validi ma semanticamente infeasibili (impossibili da eseguire), violano pattern di esecuzione obbligatori o superano limiti di risorse realistiche. Di conseguenza, generare set di test per la copertura degli archi su CFG non vincolati può portare a testare percorsi irrealistici o a ignorare vincoli di dominio critici.
• Obiettivo: Determinare la complessità computazionale di trovare un set di test che garantisca la copertura di tutti gli archi del grafo rispettando un insieme di vincoli specifici tra i vertici.
• Modello: Il problema è modellato su un cCFG (Constrained Control Flow Graph), definito come una tupla $(V, E, s, t, C, X)$, dove $C$ è un insieme di vincoli e $X$ ne definisce il tipo.

2. Tipologie di Vincoli

Gli autori analizzano cinque tipi di vincoli che modellano diverse esigenze di testing:

1. POSITIVE ($C^+$): Richiede che in almeno un percorso di test, il vertice $x$ preceda il vertice $y$.
2. NEGATIVE ($C^-$): Vieta che in alcun percorso di test, $x$ preceda $y$.
3. ONCE ($C^1$): Richiede che esista esattamente un percorso di test in cui $x$ precede $y$, con l'ulteriore condizione che $x$ appaia una sola volta prima di $y$ e $y$ una sola volta dopo $x$ in quel percorso.
4. MAX-ONCE ($C^{\le 1}$): Permette che $x$ preceda $y$ in al massimo un percorso di test (simile a ONCE ma meno restrittivo sulla frequenza).
5. ALWAYS ($C^=$): Se un percorso di test contiene $x$, deve necessariamente contenere anche $y$ successivamente nello stesso percorso.

3. Metodologia e Risultati Teorici

Gli autori hanno studiato la complessità computazionale del problema decisionale: "Esiste un set di test ammissibile che raggiunge la copertura degli archi rispettando i vincoli di tipo $X$?".

Risultati di Complessità (Teoremi 1-4)

• Vincoli POSITIVE ($C^+$):

  • Complessità: P (Tempo Polinomiale).
  • Approccio: È possibile estendere le costruzioni standard per la copertura degli archi aggiungendo percorsi specifici per soddisfare ogni vincolo. La raggiungibilità può essere verificata tramite algoritmi come DFS o BFS.
  • Risultato: Il problema è decidibile in tempo polinomiale.

• Vincoli NEGATIVE ($C^-$), MAX-ONCE ($C^{\le 1}$), ONCE ($C^1$) e ALWAYS ($C^=$):

  • Complessità: NP-Completo.
  • Dimostrazione: Per tutti e quattro i casi, gli autori hanno fornito riduzioni polinomiali dal problema 3-SAT (o varianti come POSITIVE 1-in-3 SAT per il caso ALWAYS).
  • Implicazione: Anche per classi di grafi ristrette (come i grafi aciclici), trovare un set di test ottimale che soddisfi questi vincoli è computazionalmente intrattabile nel caso generale. Le prove costruiscono "gadget" nel grafo che simulano le clausole e le variabili logiche del 3-SAT, dove la copertura degli archi corrisponde alla soddisfacibilità della formula.

Risultati su Fixed-Parameter Tractability (FPT)

• Vincoli NEGATIVE ($C^-$):
  • Sebbene il problema sia NP-completo, gli autori dimostrano che è FPT (Fixed-Parameter Tractable) rispetto al numero di vincoli $|C|$.
  • Algoritmo: Viene proposto l'algoritmo HasEdgeCoverageWithNegative.
  • Logica: L'algoritmo si basa sull'osservazione che un percorso rispetta i vincoli negativi se e solo se è "c-proper" per una certa sequenza $c$ di vertici vincolati. L'algoritmo esplora tutte le permutazioni possibili dei vertici vincolati (il cui numero è fattoriale rispetto a $|C|$, ma costante rispetto alla dimensione del grafo) e verifica in tempo polinomiale se esiste un percorso che copre gli archi rimanenti rispettando l'ordine imposto da quella sequenza.
  • Complessità: $f(|C|) \cdot p(|V| + |E|)$, dove $f$ è una funzione esponenziale/fattoriale nel numero di vincoli e $p$ è un polinomio nella dimensione del grafo.

4. Contributi Chiave

1. Formalizzazione Rigorosa: Definizione precisa del problema di copertura degli archi su CFG con vincoli di tipo vertex-based (non solo edge-based come in lavori precedenti).
2. Classificazione della Complessità: Distinzione netta tra vincoli "facili" (POSITIVE, risolvibili in P) e vincoli "difficili" (NEGATIVE, ONCE, MAX-ONCE, ALWAYS, tutti NP-completi).
3. Algoritmo FPT: Sviluppo di un algoritmo pratico per il caso NEGATIVE, dimostrando che se il numero di vincoli è piccolo (come spesso accade in scenari reali), il problema è risolvibile efficientemente nonostante la complessità teorica generale.
4. Analisi dei Gadget: Costruzione dettagliata di riduzioni da 3-SAT che dimostrano la durezza del problema anche su grafi aciclici, smentendo l'ipotesi che la struttura semplice del grafo possa semplificare il problema.

5. Significato e Conclusioni

Il lavoro ha un'importanza significativa per l'ingegneria del software e il testing:

• Realismo nel Testing: Dimostra che l'introduzione di vincoli semantici (necessari per evitare test inutili o impossibili) trasforma drasticamente la natura del problema di generazione dei test, rendendolo intrattabile per la maggior parte dei casi pratici.
• Guida per gli Strumenti: Fornisce una base teorica per gli sviluppatori di strumenti di testing automatico. Suggerisce che per vincoli complessi (come "mai dopo" o "esattamente una volta"), non ci si può aspettare algoritmi polinomiali generali, ma si deve fare affidamento su euristiche o approcci FPT quando il numero di vincoli è limitato.
• Lavori Futuri: Gli autori identificano come direzione di ricerca futura l'estensione del modello a vincoli misti (combinazione di diversi tipi di vincoli nello stesso grafo) e l'investigazione della FPT per i vincoli ONCE, MAX-ONCE e ALWAYS.

In sintesi, il paper stabilisce che mentre la copertura di base è gestibile, l'aggiunta di vincoli semantici realistici eleva la complessità del problema a NP-completo, offrendo però una via di fuga pratica (FPT) per il caso dei vincoli negativi.