4. Crash Clustering with Similarity Metrics

Why deterministic signatures are not enough

Signature grouping (as produced by symbolication plus normalized stack hashing) is a partition: every report lands in exactly one bucket, and two reports are either identical or unrelated. That is excellent for deduplication and for stable issue IDs, but it is brittle in two directions. First, it over-splits: a single refactor that renames a helper, inlines a function, or shifts one frame in the call chain produces a brand-new signature for what is semantically the same defect. Second, it under-merges: two genuinely different root causes that happen to share the same top frame (a common `dispatch`/`run`/`main` entry point) collapse into one bucket, hiding a real regression inside a noisy one.

Fuzzy clustering addresses both problems by replacing the binary "same signature?" test with a graded similarity score over the stack trace, then grouping reports whose pairwise similarity exceeds a threshold. The trade-off is that clustering introduces its own failure modes — threshold sensitivity, non-determinism, and cluster drift — so the practical task is not "replace signatures with clustering" but "use clustering where it adds signal and measure whether it actually does."

Choosing a similarity metric for stack traces

A stack trace is an ordered sequence of frames, each with a module, a symbol, and often a line/offset. Three metric families are worth implementing, and they capture different notions of "similar":

• Token-based (Jaccard / cosine over frame sets). Treat each frame as a token (e.g., module!symbol), build the set, and compute |A∩B| / |A∪B|. Order-insensitive, cheap, robust to frame reordering and to a few extra/missing frames. It will happily merge two crashes that share many library frames but differ at the faulting frame, so it is best used as a coarse pre-filter.
• Sequence edit distance (Levenshtein over frame sequences). Order-sensitive and captures insertion/deletion of frames, which is exactly what refactors and inlining produce. Normalize by the longer sequence length to get a similarity in [0,1]. Cost is O(n·m) per pair, so it needs blocking or a length filter to stay tractable.
• Weighted top-frame similarity. Weight frames by depth (the faulting frame and its immediate callers matter most) and combine with a small penalty for differing exception type. This is the closest analogue to how a human triages: "same fault site, same exception, similar callers."

A defensible default is a composite: require the exception type to match, require the top-k frames (say k=3) to have Jaccard ≥ 0.5, then rank candidates by normalized edit distance. This keeps the fault site dominant while tolerating churn deeper in the stack.

Reference implementation

The following is a self-contained Python module. It takes a list of crash reports (each with an exception and a frames list of module!symbol strings), computes pairwise similarity, and produces clusters via single-linkage agglomeration at a configurable threshold. It also computes a deterministic signature baseline so the two can be compared on the same data.

from dataclasses import dataclass, field
from itertools import combinations
from collections import defaultdict

@dataclass
class Crash:
    id: str
    exception: str
    frames: list[str]          # ordered, index 0 = faulting frame

def jaccard(a: set, b: set) -> float:
    if not a and not b:
        return 1.0
    return len(a & b) / len(a | b)

def levenshtein(a: list, b: list) -> int:
    if len(a) < len(b):
        a, b = b, a
    prev = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        cur = [i]
        for j, cb in enumerate(b, 1):
            cur.append(min(prev[j] + 1, cur[j - 1] + 1,
                           prev[j - 1] + (ca != cb)))
        prev = cur
    return prev[-1]

def seq_similarity(a: list, b: list) -> float:
    if not a and not b:
        return 1.0
    return 1.0 - levenshtein(a, b) / max(len(a), len(b))

def similarity(c1: Crash, c2: Crash, top_k: int = 3) -> float:
    if c1.exception != c2.exception:
        return 0.0
    top_j = jaccard(set(c1.frames[:top_k]), set(c2.frames[:top_k]))
    if top_j < 0.5:
        return 0.0
    return 0.5 * top_j + 0.5 * seq_similarity(c1.frames, c2.frames)

def cluster(crashes: list[Crash], threshold: float = 0.7) -> list[list[Crash]]:
    parent = {c.id: c.id for c in crashes}
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(x, y):
        parent[find(x)] = find(y)
    for c1, c2 in combinations(crashes, 2):
        if similarity(c1, c2) >= threshold:
            union(c1.id, c2.id)
    groups = defaultdict(list)
    for c in crashes:
        groups[find(c.id)].append(c)
    return sorted(groups.values(), key=len, reverse=True)

def signature_baseline(crashes: list[Crash]) -> list[list[Crash]]:
    groups = defaultdict(list)
    for c in crashes:
        groups[(c.exception, tuple(c.frames))].append(c)
    return sorted(groups.values(), key=len, reverse=True)

Two implementation details matter for correctness. First, single-linkage (union-find) is used deliberately: it chains reports through intermediate similarity, which is what you want when a refactor produces a spectrum of near-identical stacks. The cost is chaining — a long bridge of moderately similar reports can merge two distinct clusters. If that becomes a problem, switch to complete-linkage (require all pairs in a cluster to exceed the threshold) at the cost of more, tighter clusters. Second, the top_k gate is a hard filter, not a soft weight; it prevents the edit-distance term from rescuing pairs that share only deep library frames.

Evaluating cluster quality

Clustering has no ground truth by default, so quality must be assessed on two axes: internal coherence (are members actually similar?) and external agreement with a labeled sample (does the clustering match human triage?). For a labeled subset of n reports with known issue IDs, compute pairwise precision/recall/F1: a pair is a true positive if it is co-clustered and shares a label, a false positive if co-clustered but differently labeled, and a false negative if same label but separated. This is the standard BCubed/pairwise framing and it directly exposes the over-merge (low precision) vs over-split (low recall) trade-off.

For unlabeled data, use the silhouette score on the similarity matrix (treating 1 - similarity as distance) and, more usefully in practice, track cluster stability: re-run clustering on bootstrap resamples of the reports and measure how often pairs stay together (the Jaccard stability index). Unstable clusters are usually threshold artifacts and should not be promoted to issues.

Running the comparison on a labeled sample

To make the evaluation concrete, take a labeled subset of 200 reports with 12 known issue IDs. Run signature_baseline and cluster(threshold=0.70), then compute pairwise precision/recall against the labels. A typical outcome on real data is that the signature baseline has high precision (it rarely merges distinct issues) but low recall (it splits refactored stacks), while fuzzy clustering trades some precision for substantially higher recall. The decision rule is not "pick the higher F1" but "pick the operating point that matches the downstream consumer": if clusters feed an automated triage classifier (case 6), favor recall so no regression is missed; if clusters become user-facing issue IDs, favor precision so users are not shown merged, unrelated crashes.

Two failure symptoms are worth recognizing during this run. If fuzzy clustering produces one giant cluster containing most reports, the threshold is too low or the top_k gate is being bypassed — inspect the similarity distribution and raise the threshold until the largest cluster is a plausible fraction of the total. If it produces almost as many clusters as the signature baseline, the threshold is too high or the exception-type gate is rejecting legitimate merges (e.g., the same defect surfacing as both NullPointerException and IllegalStateException after a guard was added); in that case, relax the exception gate to a soft penalty rather than a hard zero.