버그 찾기

AI 요약

생성형 테스트가 예제 기반 단위 테스트보다 버그를 더 잘 찾는지 살펴봅니다. 글쓴이는 정규식 엔진에서 발견된 버그를 사례로 삼아, 작은 무작위 테스터(fuzzer)를 직접 만들고 버그를 찾는 과정을 설명합니다. 알고 있던 버그뿐 아니라 다른 버그도 하나 발견했지만, 이 사례만으로 퍼징의 효과를 단정할 수는 없다고 선을 긋습니다. 목적은 효과를 증명하기보다 테스트 기법을 보여주는 데 있습니다.

정답을 비교할 기준을 마련합니다

대상 버그는 오래된 regex crate에서 정규식 .abb|b와 입력 zabb를 처리할 때 발생했습니다. 올바른 결과는 zabb 전체가 매치되는 것이지만, 해당 버전은 b를 첫 매치로 반환했습니다.

글쓴이는 정규식과 입력 문자열을 무작위로 생성한 뒤, 같은 API를 제공하는 regex와 regex_lite의 결과를 비교하는 방법을 제안합니다. 알고리즘을 테스트할 때는 정답을 아는 기준, 즉 오라클(oracle)과 결과를 대조하는 방식이 특히 중요하다고 설명합니다. 예를 들어 복잡도가 O(N log N)인 구현과 O(N²)인 구현을 각각 만들고 결과를 비교할 수 있습니다. 글에서는 기존 정규식 구현끼리 교차 검사하는 방식을 택합니다. 테스트를 설계할 때 오라클을 마련하는 일도 시스템 개발의 일부라는 주장입니다. TigerBeetle의 Jepsen 테스트에서는 내부 타임스탬프를 API로 노출해 테스트가 버그를 찾기 쉽게 했고, 내부 시뮬레이터 VOPR도 필요한 정보에 접근하도록 함께 설계했다고 소개합니다.

크고 무작위인 입력보다 작고 까다로운 입력을 만듭니다

수 기가바이트짜리 입력을 던지면 버그가 나올 것이라고 기대하기 쉽지만, 글쓴이는 몇 가지 기능이 얽힌 작고 까다로운 입력이 더 효과적이라고 설명합니다. 모든 문자가 제각각인 긴 문자열보다 a와 b만 반복하는 문자열이 버그를 더 잘 드러낼 수도 있습니다.

문자열 생성기는 먼저 사용할 문자 집합을 정합니다. 단위 테스트에 등장하는 문자를 모아 중복을 제거하면 시작점으로 쓸 알파벳을 얻습니다. 매 테스트마다 그중 일부를 뽑고, 길이도 무작위로 정한 뒤 문자열을 만듭니다. 이렇게 하면 다양한 문자를 포함하는 문자열과 소수 문자만 반복하는 문자열을 모두 만들 수 있습니다. 반복 실행 속도를 높이도록 메모리도 재사용합니다.

정규식 생성에도 같은 원리를 적용합니다. 교대(alternation), 반복(repetition), 와일드카드, 리터럴 같은 기능 가운데 사용할 기능을 고르고, 각 기능에 0부터 100까지 가중치를 부여합니다. 가중치를 바탕으로 기능을 선택하고, 정규식 크기를 무작위로 정합니다. 재귀적으로 정규식을 만들 때는 출력 버퍼를 계속 전달하고, 분기마다 크기를 나눠 생성 크기를 조절합니다. 정규식 컴파일에 시간이 걸리므로, 같은 정규식 쌍에 여러 입력 문자열을 시험합니다.

퍼저가 버그를 놓치면 생성기도 점검합니다

글쓴이는 퍼저가 이미 알려진 버그를 잡지 못하면 곧바로 제품 코드를 고치기보다 퍼저가 해당 버그와 비슷한 사례를 찾도록 개선해야 한다고 말합니다. 그 뒤에 수정 사항을 추가하고 단위 테스트를 작성하라는 순서입니다. 퍼징이 모든 버그를 찾지는 못하며, 다른 곳에서 버그가 더 발견될 수 있으므로 여러 방어 기법과 런타임 완화책도 필요하다고 덧붙입니다.

정교한 테스트 케이스 축소나 전수 탐색, 커버리지 기반 탐색이 없어도 무작위 수 생성기(PRNG)를 잘 활용하면 효과적인 테스트를 만들 수 있다고 설명합니다. 분포 자체를 무작위화하는 방식은 swarm testing이라고 부릅니다. 글의 요점은 오라클을 마련하고, 큰 입력보다 작고 복합적인 사례를 만들며, 한 가지 테스트 방식에만 의존하지 않는 것입니다.

Lobsters 반응

• @bakkot — 좋은 글입니다. 사소한 지적을 하나 하자면, 여러 정규식 구현의 결과를 비교하는 건 오라클을 두는 것과 완전히 같지는 않습니다. 두 구현에 같은 버그가 있을 수도 있습니다. 이런 방식은 차등 퍼징(differential fuzzing)이며, 정규식처럼 이미 여러 구현이 있는 문제에서는 특히 쓰기 쉽고 유용합니다. 다만 문제를 발견한 뒤 어느 구현이 틀렸는지 확인해야 합니다. 두 방법을 모두 알아두면 좋습니다. 소인수분해처럼 실제 오라클을 둘 수 있는 문제도 있습니다.
  • @amw-zero — 버그가 없다고 보장되는 소인수분해 오라클은 무엇인가요?
  • @drmorr — 보통 테스트 입력을 만들 때 먼저 소인수를 고르고, 그 수들을 곱해 소인수분해 알고리즘에 넣습니다. 그러면 결과가 처음에 고른 소인수와 같은지 확인할 수 있습니다.
• @nytpu — 이 이야기의 진짜 교훈은 여러 방식으로 테스트해야 한다는 점이라고 생각합니다. TDD 단위 테스트만 고집하거나 통합 테스트, 퍼징, 속성 기반 테스트, 정상이라고 알려진 구현 또는 서로 다른 방식으로 버그가 있을 수 있는 구현과의 비교 중 하나만 하는 것도 좋지 않습니다. 제가 만든 복잡한 소프트웨어에서는 회귀 테스트를 포함해 적용한 테스트 방식마다 눈에 띄는 버그를 적어도 하나씩 잡았습니다. 버그는 변경이 이어지면 다시 나타나기 때문입니다.

원문: matklad.github.io / 번역·요약: Trawling