크래시 상관관계는 거짓말한다. 진짜 버그를 가리키게 만드는 방법

Statistical debugging은 근본 원인이 아닌 predicate의 정렬된 목록을 준다. 모든 분기와 null check를 계측하고, 십만 번의 실행을 돌리면, 알고리즘이 점수판을 건네준다. parser.c:144의 buffer_idx > max_len의 중요도는 0.94다. main.c:38의 log_file != NULL도 마찬가지다. 하나는 버그고, 다른 하나는 프로그램이 크래시할 때마다 참인 것일 뿐이다.

높은 상관관계는 predicate와 크래시가 공존한다는 것을 의미한다. predicate가 크래시를 유발했다는 것은 아니다. 모든 크래시가 동일한 정리 경로를 지나간다면, 그 경로상의 모든 predicate가 유죄로 보일 것이다. 가해자를 방관자들로부터 분리할 방법이 필요하다.

상관관계 점수가 실제로 측정하는 것

표준 지표는 Liblit 등이 Cooperative Bug Isolation에서 도입한 importance다. Importance는 두 숫자의 곱이다: increase와 support.

Increase는 predicate가 참일 때와 거짓일 때의 크래시율 차이다. p != NULL이 크래시 실행의 99%에서 참이고 비크래시 실행의 98%에서 참이라면, increase는 0.01이다. 그 predicate는 모든 크래시에서 실행되어도 쓸모없다.

Support는 predicate가 참인 모든 실행의 비율이다. 드물지만 완벽한 예측자가 순위를 지배하는 것을 막는다. 한 번만 실행되고 그 실행이 크래시하는 predicate는 높은 increase와 거의 0인 support를 가진다.

importance(pred) = (P(crash | pred=True) - P(crash | pred=False)) * P(pred=True)

이것은 노이즈를 잘 걸러낸다. 버그를 위치시키지는 않는다. 높은 importance를 가진 predicate는 버그일 수도, 버그를 잡는 안전 장치일 수도, 크래시에 가는 모든 경로에서 공통적인 연산일 수도 있다.

유죄처럼 보이는 predicate가 종종 무죄인 이유

42번 줄의 off-by-one 오류를 생각해 보자. 루프 범위가 < 대신 <=를 사용한다. 크래시는 20줄 뒤에서 일어난다. 루프 조건은 매 반복마다 실행된다. 45번 줄의 경계 확인은 매 반복마다 실행된다. 10번 줄의 null check는 시작 시 한 번 실행된다. 이들 모두 높은 support를 가지고 크래시 실행에 모두 나타난다.

문제는 시간적·인과적 거리다. 크래시 직전에 실행되는 predicate는 시작 시의 것보다 관련성이 높을 가능성이 크다. 동일한 함수 내부의 predicate는 유틸리티 로거 내부의 것보다 관련성이 높을 가능성이 크다. Statistical debugging은 이것을 무시한다. 당신이 다시 추가해야 한다.

도달 가능성과 거리로 필터링하는 방법

첫 번째 정제는 제어 흐름 도달 가능성이다. 크래시 실행에서 항상 참이지만, 동일한 코드에 도달한 비크래시 실행에서도 항상 참인 predicate는 의심스럽지 않다. 그것은 그 경로의 특성일 뿐이다.

조건부 확률을 계산하라. “이 predicate가 크래시를 얼마나 자주 일으키는가?” 대신 “프로그램이 제어 흐름의 이 지점에 도달했다는 조건 하에 이 predicate가 얼마나 자주 크래시를 일으키는가?”라고 물어라. 함수에 도달한다는 조건 하에 크래시율이 변하지 않는다면, 그 predicate는 정보를 추가하지 않는다.

두 번째 정제는 공간적 거리다. Importance로 순위를 매긴 후, 크래시 지점으로부터의 거리로 재순위 매긴다. 이것은 휴리스틱이다. 버그는 멀리 전파될 수 있다. 하지만 대부분의 memory corruption과 null 역참조 버그는 올바른 동작에서 처음으로 벗어난 predicate로부터 몇 줄 안에 있다.

다음은 importance를 계산하고 거리로 필터링하는 가벼운 구현이다:

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 scored

점수 함수는 의도적으로 단순하다. 계층화된 아키텍처에서는 더 약한 거리 페널티를 사용하라. 빡빡한 파서에서는 강한 페널티가 더 잘 작동한다.

Predicate에서 정확한 줄까지: 삼각 측량

Predicate는 여전히 버그 위치가 아니다. i <= buf->len 같은 Boolean 표현식이다. 줄 번호에 도달하려면 맥락 속에서 predicate를 봐야 한다.

핵심 질문: 이 predicate의 부정은 무엇이며, 그 부정이 크래시를 막을 수 있는가? Predicate가 p == NULL이고 크래시가 null 역참조라면, 부정은 크래시를 막을 것이다. 이것은 그 predicate를 직접적인 원인으로 만든다. Predicate가 log_level > 2이고 크래시가 버퍼 오버플로우라면, 부정은 아무것도 바꾸지 않는다. 그 predicate는 방관자다.

이것을 부분적으로 자동화할 수 있다. 각 상위 순위 predicate에 대해, 재현 케이스에서 강제로 거짓으로 만든다. 크래시가 사라지면, 당신은 제어 조건을 찾은 것이다. 버그는 보통 처음에 predicate를 참으로 만든 할당이나 비교 자체다.

통계적 순위는 수천 개의 predicate에서 소수로 탐색 범위를 좁힌다. 타겟 테스트나 짧은 디버거 세션이 마무리한다.

트레이드오프: 커버리지 대 정확도

계측하는 predicate가 많을수록 통계적 힘은 커지지만, 거짓 양성도 더 많이 생성한다. 모든 메모리 액세스를 계측하면 수백만 개의 predicate가 나온다. 대부분은 우연히 약한 상관관계를 가질 것이다.

해결책은 선택적 계측이다. null check, 경계 check, 오류 반환 값, 스택 트레이스의 함수 분기 조건부터 시작하라. 이것들이 크래시 실행과 비크래시 실행을 가장 잘 분리할 가능성이 높다.

충분한 실행도 필요하다. Importance 점수는 샘플 통계량이다. 백 번의 실행에서는 노이즈가 지배한다. 만 번이면 신호가 선명해진다. CBI 논문의 경험 법칙은 버그당 최소 천 번의 실행이다. 드문 크래시는 볼륨이 필요하다.

이것이 잡아내지 못하는 것

Statistical debugging은 관측 가능한 predicate 편차로 나타나는 버그를 찾는다. 성능 저하, 경계 내에 머무는 논리 오류, 계측이 방해하는 race condition은 찾지 못할 것이다.

또한 본질적으로 사후적이다. 크래시는 이미 일어났다. 데이터셋에 대한 법의학적 분석을 하는 것이다. 가치는 탐색 공간을 “전체 codebase”에서 “아마도 50줄”로 줄이는 것이다.

최소한의 종단간 예시

시뮬레이션된 데이터로 각 부분이 어떻게 맞아떨어지는지 보자:

# 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}")

이것을 실행하면 parser.c:42의 p2가 높은 importance와 크래시에 짧은 거리를 모두 가지므로 가장 높은 점수를 받는다. p1은 유사한 importance를 가지지만 더 멀리 떨어져 있다. p4는 다른 파일에 있어서 페널티를 받는다.

이미 조사 중인 크래시부터 시작하라

연구급 프레임워크가 필요한 것이 아니다. 자주 재현되는 크래시 하나를 고르라. 호출 스택에서 가장 흥미로운 다섯 개의 predicate에 계측을 추가하라. 테스트 스위트나 운영 환경 트래픽을 실행하라. Importance와 거리를 계산하라. 하나의 predicate가 크래시 실행과 비크래시 실행을 분리하고 크래시 지점에 가까이 있다면, 탐색 범위를 좁힌 것이다.

Statistical debugging은 스택 트레이스나 디버거의 대체재가 아니다. main과 segfault 사이의 모든 코드 줄을 읽는 것의 대체재다. 상관관계가 당신을 근처에 데려간다. 도달 가능성, 거리, 부정에 대한 빠른 확인이 문 앞에 데려다준다.