테스트 케이스 리듀서는 과소평가된 디버깅 도구

 (tratt.net)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 큰 입력에서 문제를 일으키는 부분을 찾을 때 테스트 케이스 리듀서는 입력을 자동으로 줄여 디버깅을 쉽게 만듦
  • 리듀서는 프로그램, 입력, 흥미성 테스트를 받아 더 짧은 후보 입력이 같은 문제를 재현하는지 반복 확인함
  • 단순한 줄 삭제 리듀서도 /usr/share/dict/words에서 긴 단어 하나를 남기고, C 예제에서는 10초 미만에 78줄을 54줄로 줄임
  • 흥미성 테스트는 과도한 축소, 느린 실행, 무한 실행, 병렬 실행 환경 때문에 정확하고 빠르게 작성해야 함
  • 입력 길이뿐 아니라 오류 발생 빈도나 실행 추적 길이 같은 지표를 흥미성 테스트에 넣으면 비결정적 버그와 큰 추적 로그 디버깅에 도움이 됨

테스트 케이스 축소

  • 큰 입력에서 프로그램이 충돌하고 입력의 어느 부분이 원인인지 모를 때, 입력을 줄이면 문제 원인 파악이 쉬워짐
  • 수동 축소는 텍스트 편집기에서 입력 일부를 삭제한 뒤 같은 충돌이 유지되는지 확인하는 방식임
  • 수동 축소는 사람이 많은 삭제 기회를 놓치기 쉽고, 삭제 후 프로그램이 정상 종료되거나 다른 정상 오류를 낼 수 있음
  • 서로 떨어진 A와 B 부분을 함께 삭제해야 효과가 나는 경우 검색 공간이 크게 늘어남

테스트 케이스 리듀서의 기본 구조

  • 테스트 케이스 리듀서는 프로그램, 입력, 흥미성 테스트를 받아 입력을 더 짧게 만드는 도구임
  • 흥미성 테스트는 축소된 입력이 관심 있는 오류를 재현하면 0을 반환하고, 그렇지 않으면 0이 아닌 값을 반환함
  • 테스트 케이스 리듀서는 95~99% 축소가 흔하며, 디버깅을 훨씬 쉽게 만들 수 있음
  • 리듀서는 입력의 어떤 부분을 제거해야 하는지 의미적으로 이해하지 않아도 작동함

  • 단순 리듀서 예제

    • 예제 프로그램은 파일에서 줄을 읽고 길이가 25보다 큰 줄이 있으면 Word too long을 출력함
    • 흥미성 테스트는 프로그램 출력에 Word too long이 있으면 0, 없으면 1을 반환함
    • 단순 Python 리듀서는 입력을 줄 단위로 읽고, 한 줄을 삭제한 후보 입력을 임시 파일에 쓴 뒤 흥미성 테스트를 실행함
    • 후보 입력이 흥미롭다면 현재 입력을 후보로 바꾸고, 더 이상 줄일 수 없으면 결과를 stdout에 출력함
    • /usr/share/dict/words에 실행한 결과는 antidisestablishmentarianism만 남김

더 강한 리듀서와 Shrink Ray

  • 78줄 C 프로그램 예제는 FAST=0과 FAST=1 설정에서 서로 다른 출력을 내는 문제를 다룸
  • 흥미성 테스트는 두 설정으로 컴파일한 뒤 FAST=0 출력이 0d754a56이고 FAST=1 출력이 그 값과 다를 때만 통과함
  • 단순 리듀서는 10초 미만에 78줄 C 입력을 54줄로 줄여 줄 수 기준 약 30% 축소함
  • 흥미로운 후보를 찾을 때마다 처음 줄부터 다시 삭제하도록 i=0을 추가하면 실행 시간은 거의 10배가 되고 3줄을 더 줄임
  • Shrink Ray는 여러 축소 규칙과 병렬 실행을 제공하며, --no-clang-delta를 붙이면 C에 대한 특수 지식을 쓰지 않음
  • Shrink Ray는 약 15분 후 바이트 기준 60% 넘게 입력을 줄였고, 다른 사례에서는 약 20분 뒤 90% 축소를 찾은 뒤 99%까지 더 줄임
  • Shrink Ray는 표준 주석 문법을 알고 초기에 제거를 시도하며, 정수를 더 작은 값으로 줄이는 시도도 수행함

흥미성 테스트 작성의 어려움

  • 테스트 케이스 리듀서는 흥미성 테스트를 문자 그대로 따르므로, 테스트가 잘못 통과하면 원하는 지점보다 더 줄어드는 과도한 축소가 발생함
  • Shrink Ray는 흥미성 테스트가 빈 입력을 받아들이는지 명시적으로 검사하며, 이런 상황은 자주 발생할 수 있음
  • C 예제에서 단순히 두 출력이 다른지만 확인하면 중요하지 않거나 오해를 부를 수 있는 출력 차이가 흥미로운 입력으로 분류될 수 있음
  • test "$slow_out" = "0d754a56" 검사는 느린 버전이 실제로 기대한 동작을 하는지 확인해 과도한 축소 가능성을 낮춤

  • 속도와 타임아웃

    • 흥미성 테스트가 빠르면 리듀서가 초당 수백 번 실행할 수 있음
    • 중간 크기 예제도 수십만 번의 축소 시도로 이어질 수 있어 흥미성 테스트 최적화가 전체 시간에 큰 영향을 줌
    • 자동 코어 덤프 생성을 끄는 방식으로 흥미성 테스트를 약 3배 빠르게 만든 사례가 있음
    • 리듀서는 i-=1 같은 줄을 제거해 종료되는 프로그램을 무한 실행 프로그램으로 바꿀 수 있음
    • 프로그램이 0.1초에 실행되는데 타임아웃을 60초로 잡으면 전체 축소가 큰 폭으로 느려짐
    • 빠른 프로그램은 timeout을 1~2초로 올림 처리하고, 그 외에는 초기 실행 시간의 약 1.5~2배로 잡는 방식이 사용됨

  • 병렬 실행

    • Shrink Ray 같은 리듀서는 흥미성 테스트를 병렬로 실행함
    • Shrink Ray는 각 흥미성 테스트를 임시 디렉터리에서 실행하고 해당 디렉터리를 자동 정리함
    • 임시 디렉터리만으로 충분하지 않은 경우도 있으며, 필요한 조치는 사례별로 달라짐

흥미성 테스트로 결정성 유도

  • 예제 조각은 len([])==0 때문에 0으로 나누기 오류를 만들지만, random.random() < 0.33 조건 때문에 약 3분의 1 실행에서만 문제가 발생함
  • 비결정적 버그는 오류가 무작위로 나타났다 사라져 가설 검증을 더 어렵고 오래 걸리게 만듦
  • 리듀서가 random.random() 호출을 제거하거나 조건식을 바꾸면 비결정적 오류가 결정적 오류로 바뀔 수 있음
  • 실제 비결정성은 입력의 여러 부분이 불리하게 상호작용하는 경우가 많아 제거가 어려울 수 있음
  • 테스트 케이스 리듀서는 입력 길이를 “더 좋음”의 대리 지표로 쓰는 언덕 오르기 알고리듬처럼 동작함
  • 언덕 오르기 접근은 지역 최적점에 갇히기 쉽고, 짧은 입력이 항상 오류 탐색에 더 좋은 것은 아님

  • 반복 실행 방식

    • 비결정적 버그를 다룰 때 흥미성 테스트가 입력을 여러 번 실행하고, 관심 오류가 한 번 이상 발생하면 입력을 받아들이는 방식이 사용됨
    • 이 방식은 오류 발생 빈도를 높이는 데 도움이 될 수 있음
    • 한 번 이상 발생하면 통과하는 테스트는 비결정적 입력도 받아들이므로, 축소가 진행되며 비결정성이 오히려 커질 수 있음
    • 더 엄격한 방식은 n번 반복 모두에서 오류가 발생할 때만 입력을 받아들이는 테스트임
    • 엄격한 테스트는 초기 입력이 통과할 확률이 낮아 Shrink Ray를 시작하기 어렵고, 예제의 3회 반복 조건에서는 초기 통과 확률이 3.6%임
    • 실용적 우회는 먼저 “n회 중 1회 이상 오류” 테스트로 시작하고, 오류가 더 자주 발생하는 축소 입력을 얻으면 “n회 연속 오류” 테스트로 바꾸는 방식임

전역 카운터와 다른 목표 지표

  • 수동 개입은 강력하지만 Shrink Ray를 지켜봐야 하고 개입 시점을 놓치기 쉬움
  • 입력 길이가 아닌 다른 속성으로 리듀서를 유도하려면 단일 흥미성 테스트 안에서 해당 속성을 강제할 수 있음
  • yk 디버깅에서는 입력 길이보다 실행 추적 길이, 즉 프로그램이 실행한 명령 수에 가까운 값이 더 중요하게 쓰임
  • YKD_LOG="$t:jit-asm" 출력은 텍스트 추적 IR과 기계어 명령을 파일에 쓰며, 짧은 jit-asm 출력이 디버깅을 쉽게 만듦
  • wc -l은 로그 파일 줄 수를 세어 추적 길이에 가까운 대리 지표로 쓰임
  • 흥미성 테스트는 현재 추적 줄 수가 이전 최저 줄 수보다 크면 입력을 흥미롭지 않은 것으로 처리하고, 최저값은 /tmp/global_best에 저장함
  • 이 방식은 병렬 축소에서 안전하지 않고 리듀서 호출 방식에 대한 가정을 포함하지만, 버리는 짧은 스크립트로는 감수 가능한 불완전성으로 취급됨
  • yk 세그폴트 사례에서 일반 축소는 40K줄 추적을 남겼지만, 이 기법은 더 큰 축소 입력 대신 10.1K줄 추적을 만들었고 30분 안에 근본 버그를 파악하게 함

핵심 정리

  • 테스트 케이스 리듀서는 컴파일러 작성자에게만 유용한 도구가 아니며, 비컴파일러 문제에도 쓰일 수 있음
  • 입력 길이를 줄이는 기본 목적 외에도 오류 빈도, 벽시계 시간, 비결정성 수준, 추적 길이 같은 속성을 흥미성 테스트로 유도할 수 있음
  • 흥미성 테스트의 정확도, 실행 속도, 타임아웃, 병렬 실행 안전성이 리듀서의 실제 효과를 좌우함
  • 리듀서는 입력과 프로그램의 의미를 거의 이해하지 않아도, 문제를 더 작은 형태로 유지해 디버깅 생산성을 높일 수 있음

함께 보면 좋은 글 β

GN⁺   [-]
Lobste.rs 의견들

  • 진짜 궁금한데, 자동 테스트 케이스 축소의 가치를 인정하지 않는 사람이 있나? “과소평가”라는 말은 테스트 케이스 축소를 항상 원하지 않는 사람이 있다는 뜻처럼 들림
    버그를 바로 특정할 수 있더라도, 회귀 테스트용으로는 축소된 사례가 필요하지 않나?

    • 보통 개발자는 이걸 기법으로 생각해본 적조차 없을 것 같음
    • 글 첫 줄이 “Test-case reducers are less well known than they should be, [...]”인데, 몇 년 동안 사람들에게 퍼징과 속성 기반 테스트를 쓰라고 권해온 입장에서도 딱 그랬음
      둘 다 실패 사례 축소나 “shrinking” 같은 형태를 자주 포함하고, 덕분에 훨씬 실용적으로 쓸 수 있음
    • 퍼저에서는 대략 알고 있음. 퍼저가 실패 사례를 찾은 뒤 자동으로 줄여주고, 그 부분은 아주 잘 동작함
      다만 퍼징 전반, 특히 AmericanFuzzyLop과 AFL++ 를 써본 경험상 설정이 너무 고통스러워서 대체로 피하게 됨
      내가 만나는 버그 대부분도 “이 입력 파일을 넣으면 잘못 동작한다”가 아니라 “어딘가의 어떤 사용자에게 잘못 동작한다”에 가까움. 가끔은 “특정 조건에서 일련의 단계를 거치면 잘못 동작한다”까지 줄일 수는 있는데, 1) “사용자가 순서대로 뭔가 하는 것”에 자동 테스트 케이스 축소기를 어떻게 적용할지 잘 모르겠고, 2) 일단 로컬에서 재현할 방법을 찾으면 디버깅의 99%는 끝난 셈임
      아마 글쓴이는 이런 내 태도를 “과소평가”라고 볼 것 같음
    • 테스트 케이스 축소가 뭔지 아는 사람부터가 소수일 것 같음

  • 이 글과 예시는 비컴파일러 상황에서도 축소기가 더 널리 쓰여야 한다고 말하면서도, 관점은 상당히 컴파일러 작성자 쪽에 치우쳐 있음
    ~silentbicycle이 쓴 것처럼 대부분의 테스트 케이스 축소는 퍼저나 속성 기반 테스트의 맥락에서 일어나며, 더 큰 프레임워크 안에 축소 기능이 내장되어 있음. 컴파일러는 독립형 테스트 케이스 축소기가 유용한 특이한 영역 중 하나임. 독립형 축소기가 도움이 되는 다른 경우가 또 있는지는 잘 모르겠음
    결정성 부분도 흥미로움. 예시는 버그를 유발하는 입력 파일, 즉 스크립트 때문에 결정성이 생기는 경우로 시작하지, 버그가 있는 프로그램인 인터프리터 자체의 특성으로 결정적인 것은 아님. 글이 “interestingness” 기법이 버그 있는 프로그램 자체가 비결정적인 비컴파일러 상황에서도 통한다는 뜻인지 명확하지 않음
    테스트 문제를 퍼징과 테스트 케이스 축소에 맞게 바꾸는 방법으로는, 번호가 붙은 명령형 명령 모음을 만드는 걸 추천함. 각 명령에는 테스트 실패를 감지할 수 있는 가벼운 일관성 검사를 넣고, 바로 크래시가 나지 않는 경우도 잡게 함. 무거운 일관성 검사는 별도 명령으로 빼는 편이 테스트 속도를 덜 늦춤. 단순 무작위 테스트에서는 테스트 하네스가 뭔가 깨질 때까지 명령을 무작위로 고르고, 이후 퍼저 하네스로 바꿀 때는 퍼지 입력 바이트 스트림으로 명령을 고르게 하면 됨. 그러면 결정적인 회귀 테스트와 테스트 케이스 축소 같은 좋은 것들을 자동으로 얻을 수 있음
    libfuzzer에게 명시적으로 테스트 케이스를 줄이라고 시켜서는 별 성과가 없었는데, 아마 libfuzzer가 입력을 생성하는 동안 이미 줄였기 때문인 것 같음. 그래서 범용 퍼저가 테스트 케이스를 줄이는 데 도움 되는 interestingness 검사를 더 시도해볼 동기는 생기지 않았음. 다른 사람들은 성공한 적이 있는지 궁금함

    • 완전 동의함. 이런 방식을 자주 씀. 상태가 있는 인터페이스의 기호적 표현을 만들고, 보통 switch-case나 match 기반의 단순 인터프리터를 만든 다음, 연산 목록을 무작위로 생성해 실행하고, 사전/사후 조건 위반이나 내부 손상을 잡는 assert를 유발한 입력을 줄임
      속성 기반 테스트, 퍼징, 가벼운 모델 검사 중 무엇으로 부르든, 깊은 버그를 찾는 데 놀랄 만큼 효과적일 수 있음. 각각의 연산은 개별적으로는 올바르지만 서로의 가정이 조금 어긋난 상태 있는 인터페이스를 많이 봤고, 이런 연산들이 예상 못 한 방식으로 조합되면 내부 손상으로 커짐
      연산 목록을 인메모리 해시 테이블이나 리스트 기반의 단순 구현과 나란히 실행하고 결과가 일치하는지도 확인하면 유용함. 차이가 나면 대개 버그이거나 더 잘 문서화해야 할 경계 사례임
    • 가끔 운송 최적화를 다루는데, 불변식이 깨지는 꽤 복잡한 시나리오를 자주 만남. 테스트 케이스 축소기가 있으면 정말 좋겠지만, 예전에는 수동으로 줄이는 데 만족해야 했음[0]
      안타깝게도 데이터 파일이 너무 복잡해서 shrinkray가 처리하기는 어려울 것 같음. 서로 다른 여러 “파일”의 표 형식 데이터를 읽고, 장거리 의존성도 있어서 축소 방법에 대한 도메인 지식을 직접 인코딩해야 할 듯함
      AI 발전 속도를 보면 다음에 이런 시나리오가 생기면 맞춤형 축소기를 작성할 것 같음
      [0] 애매한 존재론을 끌어오자면, 최적화 문제는 비용을 최소화하는 탐색 문제이고, 이건 사실상 컴파일러와 같은 것이므로 완벽한 예시는 아님

  • 이걸 pytest로 작성한 테스트에 어떻게 적용할지 알아내려고 세 번 읽었음
    테스트 스위트의 복잡도를 줄이고 싶어서, 일하지 않을 때 네 번째로 다시 읽어볼 생각임

    • Python을 쓴다면 첫 단계는 테스트 케이스 축소가 내장된 Hypothesis를 도입하는 것임

  • 작년에 CI의 테스트 실행 순서 문제를 보다가, 테스트 목록을 줄이는 데 도움 되는 도구를 만들었음
    기본적으로 줄들을 반씩 잘라가며 실행해보는 방식이었음
    스크립트 자체는 꽤 버그가 많지만, 5000개 테스트 목록이 내 동시성 버그를 일으키는 4개 정도의 테스트 목록으로 줄어드는 건 멋졌음
    내 경우에 Shrink Ray가 그냥 동작했을지 정말 궁금함. “테스트를 기준으로 줄 집합을 줄이기”는 표준 명령줄 도구 묶음에 들어가야 할 기능이라고 진심으로 생각함

  • 이 주제와 관련해, 속성 기반 테스트도 테스트의 반례를 만들기 위해 생성된 입력의 상태 공간을 “축소”하는 꽤 비슷한 접근을 씀
    속성 기반 테스트의 장점은 탐색 공간을 유도하고 구조화할 수 있다는 것임. 입력을 프로그램을 모델링하는 상태 기계를 구동하는 전이 집합으로 만들 수 있음
    이 기법이 특히 데이터베이스와 분산 시스템처럼 잘 맞는 영역에서도 너무 덜 쓰이는 걸 볼 때마다 놀람. 바로 지난주에도 $WORK에서 이런 테스트를 몇 시간도 안 걸려 만들었고, 우리 시스템이 수렴하지 않는다는 걸 빠르게 발견함. 테스트가 동료들에게 보여주면 바로 이해할 수 있는 깔끔한 추적을 출력해줬음
    개인적으로는 복잡한 시스템을 디버깅할 때 투자 대비 효과가 가장 좋은 테스트 기법이라고 봄

답변달기