Delta debugging e riduzione automatica

In parole semplici

Il delta debugging è la generalizzazione automatica della bisezione: dato un input grande che provoca un bug, lo riduce fino al minimo che lo conserva. La tecnica è di Andreas Zeller (è di lui anche il libro Why Programs Fail).

Non serve scriverla a mano ogni volta: librerie e tool la implementano. Capire l’idea ti permette di non perdere mezz’ora a tagliare un input a mano quando un loop può farlo in 30 secondi.

Parole nuove

• delta debugging (ddmin): algoritmo che minimizza un input che produce un certo esito.
• input minimizzabile: stringa, array, file, sequenza di azioni — qualunque cosa abbia “parti”.
• oracolo: funzione che dato un input dice “bug presente?” sì/no.
• shrinker: componente di un property-based test che riduce input falliti.

Cosa impari

• Capire il loop fondamentale del delta debugging.
• Riconoscere quando applicarlo.
• Conoscere strumenti pratici (fast-check, Hypothesis, shrinker integrati).

L’idea base

Hai un input I grande che fa fallire un test (l’oracolo dice “bug”). Vuoi un input più piccolo che faccia ancora fallire.

Algoritmo elementare:

1. Dividi I in n parti.
2. Per ogni sottoinsieme di parti (escluse alcune): prova.
3. Se un sottoinsieme fa ancora fallire, sostituisci I con esso, raddoppia n.
4. Se nessuno fa fallire, dimezza il numero di parti (granularità più fine).
5. Ripeti finché ogni rimozione fa cessare il bug.

Il risultato è un input “1-minimal”: rimuovere qualunque parte fa sparire il bug.

Esempio concreto

Input che fa fallire un parser:

<div id="x" class="y" data-z="w"><span>ciao</span></div><p>altro</p>

L’oracolo (parser(input) lancia eccezione?) ritorna “bug”.

Delta debugging prova:

1. Rimuove <p>altro</p> → bug presente → tieni.
2. Rimuove <span>ciao</span> → bug ancora presente → tieni.
3. Rimuove class="y" → bug sparisce → ripristina.
4. Rimuove data-z="w" → bug presente → tieni.

Stato attuale:

<div id="x" class="y"></div>

Continua finché ogni rimozione fa sparire il bug. Risultato: input minimo.

Quando applicarlo

• Input grandi (file da 100 KB, payload JSON da 1 MB) che provocano errore.
• Sequenza di azioni utente che porta al crash (riduci la sequenza).
• Esempi falliti dei property-based test.
• Bug nei dati (modulo 4.5).

Quando l’input è già piccolo (< 50 caratteri) e tu vedi a occhio, il delta debugging è overkill.

Strumenti pratici

Property-based testing con shrinker integrato

• fast-check (JS): genera input casuali, e se fallisce riduce automaticamente all’input minimo.

import fc from "fast-check";

fc.assert(fc.property(
  fc.array(fc.integer()),
  (numeri) => media(numeri) >= 0
));
// se fallisce, fast-check mostra il caso ridotto

• Hypothesis (Python), PropEr (Erlang), QuickCheck (Haskell, originale): stessa filosofia.

Tool dedicati

• C-Reduce (per programmi C/C++).
• Pernosco, rr + tool di riduzione per stack di sistema.

Riduzione “creativa”: non solo togliere

A volte ridurre non basta togliere. Bisogna sostituire:

• numeri grandi → 0 o 1;
• stringhe → "";
• date complesse → 1970-01-01;
• oggetti annidati → null o {}.

Algoritmi avanzati di delta debugging includono queste sostituzioni.

Esercizio guidato

1. Prendi una funzione che fallisce con un input grande (anche generato ad arte).
2. Scrivi un oracolo: una funzione oracle(input) che ritorna true se il bug si vede.
3. Implementa il delta debugging “ingenuo”: prova a togliere un elemento alla volta, tieni se l’oracolo dice ancora true.
4. Confronta l’input iniziale con quello ridotto.

Esempio per array:

function ddmin(input, oracle) {
  let attuale = [...input];
  let cambiato = true;
  while (cambiato) {
    cambiato = false;
    for (let i = 0; i < attuale.length; i++) {
      const tentativo = attuale.slice(0, i).concat(attuale.slice(i + 1));
      if (oracle(tentativo)) {
        attuale = tentativo;
        cambiato = true;
        break;
      }
    }
  }
  return attuale;
}

Lento ma istruttivo. Per la produzione, usa fast-check o equivalenti.

Errori frequenti del principiante

• Oracolo lento. Il delta debugging esegue molte volte: se l’oracolo dura 5 secondi, la riduzione dura ore.
• Oracolo non deterministico. Falsi negativi falsano la riduzione. Stabilizza prima.
• Riduzione che fa cambiare il tipo di bug. A volte la riduzione “trova un altro bug”: registralo, non confonderlo con il primo.
• Fermarsi al primo input ridotto. Talvolta una seconda passata stringe ulteriormente.