Le statistical debugging vous donne une liste triée de prédicats, pas une cause racine. Vous instrumentez chaque branche et chaque null check, exécutez cent mille exécutions, et l’algorithme vous remet un tableau de scores. buffer_idx > max_len à parser.c:144 a une importance de 0,94. log_file != NULL à main.c:38 aussi. L’un d’eux est le bug. L’autre se trouve juste être vrai chaque fois que le programme crashe.
Une forte corrélation signifie qu’un prédicat et un crash coexistent. Cela ne signifie pas que le prédicat a causé le crash. Si chaque crash passe par le même chemin de nettoyage, chaque prédicat sur ce chemin aura l’air coupable. Vous avez besoin d’un moyen de séparer le coupable des simples témoins.
Ce que le score de corrélation mesure réellement
La métrique standard est l’importance, introduite par Liblit et al. dans Cooperative Bug Isolation. L’importance est le produit de deux nombres : increase et support.
L’increase est la différence entre le taux de crash quand un prédicat est vrai et quand il est faux. Si p != NULL est vrai dans 99 % des exécutions qui crashent et 98 % des exécutions qui ne crashent pas, l’increase est de 0,01. Ce prédicat est inutile même s’il se déclenche à chaque crash.
Le support est la fraction de toutes les exécutions où le prédicat est vrai. Il empêche les prédicteurs rares mais parfaits de dominer le classement. Un prédicat qui ne se déclenche qu’une seule fois mais dont l’exécution crashe obtient un increase élevé et un support proche de zéro.
importance(pred) = (P(crash | pred=True) - P(crash | pred=False)) * P(pred=True)Cela filtre bien le bruit. Cela ne localise pas les bugs. Un prédicat avec une forte importance peut être le bug, la vérification de sécurité qui l’attrape, ou une opération commune sur chaque chemin vers le crash.
Pourquoi les prédicats coupables d’apparence sont souvent innocents
Considérez une erreur off-by-one à la ligne 42 où une borne de boucle utilise <= au lieu de <. Le crash se produit vingt lignes plus loin. La condition de boucle se déclenche à chaque itération. Une vérification de bornes à la ligne 45 se déclenche à chaque itération. Le null check à la ligne 10 se déclenche une fois au démarrage. Tous ont un support élevé et apparaissent dans les exécutions qui crashent.
Le problème est la distance temporelle et causale. Un prédicat qui s’exécute quelques instants avant le crash est plus susceptible d’être lié que celui du démarrage. Un prédicat à l’intérieur de la même fonction est plus susceptible d’être lié que celui dans un logger utilitaire. Le statistical debugging ignore cela à moins que vous ne le rajoutiez.
Comment filtrer par accessibilité et distance
Le premier raffinement est l’accessibilité dans le flux de contrôle. Un prédicat qui est toujours vrai dans les exécutions qui crashent mais aussi toujours vrai dans les exécutions qui ne crashent pas qui atteignent le même code n’est pas suspect. C’est juste une propriété de ce chemin.
Calculez une probabilité conditionnelle. Au lieu de demander « combien de fois ce prédicat fait-il crasher ? », demandez « combien de fois fait-il crasher étant donné que le programme a atteint ce point dans le flux de contrôle ? » Si le taux de crash ne change pas quand vous conditionnez sur l’atteinte de la fonction, le prédicat n’ajoute pas d’information.
Le deuxième raffinement est la distance spatiale. Après le classement par importance, reclassez par distance du site du crash. C’est une heuristique. Les bugs peuvent se propager loin. Mais la plupart des bugs de corruption de mémoire et de null dereference vivent à quelques lignes du prédicat qui diverge d’abord du comportement correct.
Voici une implémentation légère qui calcule l’importance et filtre par distance :
from dataclasses import dataclass
from typing import List, Set
@dataclass(frozen=True)
class Predicate:
pid: str
file: str
line: int
expr: str
@dataclass
class Run:
crashed: bool
crash_file: str = ""
crash_line: int = 0
predicates: Set[Predicate] = None
def importance(pred: Predicate, runs: List[Run]) -> float:
total = len(runs)
with_pred = [r for r in runs if pred in r.predicates]
without_pred = [r for r in runs if pred not in r.predicates]
if not with_pred or not without_pred:
return 0.0
crash_with = sum(1 for r in with_pred if r.crashed) / len(with_pred)
crash_without = sum(1 for r in without_pred if r.crashed) / len(without_pred)
support = len(with_pred) / total
return (crash_with - crash_without) * support
def avg_distance(pred: Predicate, runs: List[Run]) -> float:
crash_runs = [r for r in runs if r.crashed]
if not crash_runs:
return float('inf')
dists = []
for r in crash_runs:
if pred.file != r.crash_file:
return float('inf')
dists.append(abs(pred.line - r.crash_line))
return sum(dists) / len(dists)
def rank_predicates(runs: List[Run]) -> List[tuple]:
all_preds = set()
for r in runs:
all_preds.update(r.predicates)
scored = []
for p in all_preds:
imp = importance(p, runs)
dist = avg_distance(p, runs)
# Higher importance is better, lower distance is better.
if dist == float('inf'):
score = imp * 0.1
else:
score = imp / (1 + dist / 10)
scored.append((score, imp, dist, p))
scored.sort(key=lambda x: x[0], reverse=True)
return scoredLa fonction de scoring est délibérément simple. Dans les architectures en couches, utilisez une pénalité de distance plus faible. Dans les parsers compacts, une pénalité forte fonctionne mieux.
Du prédicat à la ligne exacte : triangulation
Un prédicat n’est toujours pas un emplacement de bug. C’est une expression booléenne comme i <= buf->len. Pour arriver à un numéro de ligne, regardez le prédicat dans son contexte.
La question clé : quelle est la négation de ce prédicat, et la négation empêcherait-elle le crash ? Si le prédicat est p == NULL et que le crash est un null dereference, la négation l’empêcherait. Cela fait du prédicat une cause directe. Si le prédicat est log_level > 2 et que le crash est un buffer overflow, la négation ne change rien. Le prédicat est un témoin.
Vous pouvez automatiser cela partiellement. Pour chaque prédicat bien classé, forcez-le à faux dans un cas de reproduction. Si le crash disparaît, vous avez trouvé la condition contrôlante. Le bug est généralement l’affectation ou la comparaison qui a rendu le prédicat vrai en premier lieu.
Le classement statistique réduit la recherche de milliers de prédicats à une poignée. Un test ciblé ou une courte session de débogueur boucle la boucle.
Le compromis : couverture contre précision
Plus vous instrumentez de prédicats, plus vous avez de puissance statistique, mais plus vous générez de faux positifs. Instrumenter chaque accès mémoire produit des millions de prédicats. La plupart corrèleront faiblement avec le crash par hasard.
La solution est l’instrumentation sélective. Commencez avec les null checks, les bounds checks, les valeurs de retour d’erreur, et les conditions de branche dans les fonctions de la stack trace. Ceux-ci sont les plus susceptibles de séparer le comportement crasant du non-crasant.
Vous avez aussi besoin d’assez d’exécutions. Le score d’importance est une statistique d’échantillon. Avec cent exécutions, le bruit domine. Avec dix mille, le signal se précise. La règle empirique des papiers CBI est d’au moins mille exécutions par bug. Les crashes rares ont besoin de volume.
Ce que cela ne peut pas attraper
Le statistical debugging trouve des bugs qui se manifestent comme des déviations observables de prédicats. Il ne trouvera pas les régressions de performance, les erreurs de logique qui restent dans les bornes, ou les race conditions que l’instrumentation perturbe.
C’est aussi fondamentalement post-hoc. Les crashes se sont déjà produits. Vous faites de la forensique sur un dataset. La valeur est de réduire l’espace de recherche de « l’ensemble du codebase » à « peut-être cinquante lignes ».
Un exemple minimal de bout en bout
Voici comment les pièces s’assemblent avec des données simulées :
# Simulate runs for a bug at parser.c:42 (off-by-one loop bound)
runs = []
# 900 non-crashing runs
for _ in range(900):
runs.append(Run(
crashed=False,
predicates={
Predicate("p1", "parser.c", 10, "buf != NULL"),
Predicate("p2", "parser.c", 42, "i <= buf->len"), # the bug
Predicate("p3", "parser.c", 45, "i < buf->len"),
}
))
# 100 crashing runs: all hit the bug predicate
for _ in range(100):
runs.append(Run(
crashed=True,
crash_file="parser.c",
crash_line=62,
predicates={
Predicate("p1", "parser.c", 10, "buf != NULL"),
Predicate("p2", "parser.c", 42, "i <= buf->len"),
Predicate("p3", "parser.c", 45, "i < buf->len"),
Predicate("p4", "main.c", 5, "argc > 1"), # startup, irrelevant
}
))
results = rank_predicates(runs)
for score, imp, dist, pred in results[:3]:
print(f"{pred.file}:{pred.line} {pred.expr:20s} "
f"score={score:.3f} importance={imp:.3f} avg_dist={dist:.1f}")L’exécution de cela donne à p2 à parser.c:42 le score le plus élevé parce qu’il a à la fois une forte importance et une courte distance du crash. p1 a une importance similaire mais est plus éloigné. p4 est pénalisé pour être dans un fichier différent.
Commencez par le crash que vous investigatez déjà
Vous n’avez pas besoin d’un framework de niveau recherche. Choisissez un crash qui se reproduit fréquemment. Ajoutez de l’instrumentation aux cinq prédicats les plus intéressants dans la call stack. Exécutez votre suite de tests ou votre trafic de production. Calculez l’importance et la distance. Si un prédicat sépare les exécutions crasantes des non-crasantes et est proche du site du crash, vous avez réduit la recherche.
Le statistical debugging ne remplace pas les stack traces ou les débogueurs. C’est un remplacement pour lire chaque ligne de code entre main et le segfault. La corrélation vous amène dans le voisinage. L’accessibilité, la distance, et une vérification rapide de la négation vous amènent à la porte.