퍼징 테스트 케이스 생성

퍼즈 테스팅의 분류 (표 3)

기준	종류	내용
입력 주입 형태	단순	키보드 입력값 변경
	파일	소프트웨어가 읽는 파일 변경
	네트워크	송수신 패킷 변경
입력 처리 방법	생성 기반	완전히 새 입력 생성
입력 처리 방법	변이 기반	기존 입력 일부 변경
분석 정도	덤(블랙박스)	구조 분석 없이 무작위
	스마트(화이트박스)	소스코드 분석
	바이너리(그레이박스)	역공학으로 취약 예상 지점

논문은 굵게 표시한 변이 기반 바이너리 파일 퍼징을 다룹니다.

논문의 제안 (그림 8)

입력 파일 분석: 파일을 16진수로 보고, 파일 형식 템플릿(010 Editor)으로 헤더·데이터 영역을 나눕니다.
테스팅 영역 추출: 공개된 기존 취약점 정보와 간단한 변이(SWAP, BIT-FLIPPING, 00/FF 대입)로 반응이 큰 영역만 고릅니다.
테스트 케이스 생성: 고른 영역에 FLIPPING 알고리즘을 적용해, 1~4바이트를 골라 그 바이트들이 가질 수 있는 모든 값의 조합을 만듭니다.

핵심 주장: 테스트 영역을 줄여 효율을 높이고, 여러 바이트를 함께 바꿔 기존 기법이 놓치는 결함까지 찾는다.

그림 4 · 변이 기반 바이너리 파일 퍼징 과정

그림 8 · 제안 테스트 케이스 생성 기법

그림 1 · 멀티미디어 소프트웨어 취약점 분포

파일 형식 취약점이 약 44%로 가장 많습니다(논문 인용 자료).

그림 2 · 멀티미디어 파일의 일반 구조

헤더에는 형식·크기·비트율 같은 필드가 있고, 소프트웨어는 이 값을 믿고 메모리를 할당하거나 데이터를 읽습니다. 그래서 헤더가 퍼징의 주된 대상이 됩니다.

원본 영역을 네 바이트 i j k l로 놓고, 각 기법이 어떤 테스트 케이스를 만드는지 직접 펼쳐 봅니다(그림 6·7·12). 빨간 칸이 바뀐 바이트입니다.

기법 보여 줄 개수

ijkl

기법끼리 서로 못 찾는 변이

논문 4.1절은 두 기존 기법이 서로 보완적임을 보였습니다.

SWAP만 만드는 변이: 두 바이트의 위치가 바뀐 경우(예: i j → j i). BIT-FLIPPING은 한 번에 한 바이트만 바꾸므로 두 바이트가 동시에 바뀐 상태를 만들지 못합니다.
BIT-FLIPPING만 만드는 변이: 한 바이트가 새로운 값이 된 경우(예: 00 → 07). SWAP은 이미 있는 값을 옮길 뿐 새 값을 만들지 못합니다.
FLIPPING d≥2: 두 바이트 이상을 동시에 아무 값으로 바꾸므로 위 둘을 모두 포함합니다. 하지만 그 대가가 ③ 탭의 경우의 수 폭발입니다.

여러 바이트를 함께 바꿔야 드러나는 결함(예: 크기 필드와 실제 데이터 길이가 함께 어긋나는 경우)이 있다는 점에서 다중 바이트 변이의 필요성 자체는 타당합니다. 문제는 “모든 값을 다 시도하는” 방식입니다.

그림 6 · SWAP 기법

그림 7 · BIT-FLIPPING 기법

영역 길이와 변이 바이트 수에 따른 테스트 케이스 수

영역 길이 c 4바이트 FLIPPING 최대 d 4 테스트 1건 소요 1.0초 병렬 실행 장비 1대

FLIPPING은 d개 바이트를 고르는 위치 C(c, d)가지 × 그 바이트들의 값 256^d가지를 d = 1…최대 d까지 더합니다(논문 3.3절의 설명대로 계산). 테스트 1건 = 변이 파일 하나를 대상 소프트웨어로 열고 이상 여부를 확인하는 시간입니다.

로그 눈금으로 본 증가 속도

SWAPBIT-FLIPPINGFLIPPING d≤2FLIPPING d≤4

표 7·8 · 세 기법의 영역과 소요 시간

영역은 수백~수만 분의 1로 줄었는데 시간은 왜 2/3에 그칠까

테스트 영역 크기 (일반 대비 %)소요 시간 (일반 대비 %)

제안 기법은 테스트 영역을 일반 기법의 평균 0.06%로 줄였지만, 소요 시간은 평균 65.3%로만 줄었습니다. 영역 축소 효과를 다중 바이트 조합(256^d)이 대부분 상쇄했기 때문입니다.

수치를 맞춰 보면

그림 16 · AVI·FLV 파일 구조와 영역 번호

그림 10 · 테스팅 영역 추출 과정

“모든 값을 다 시도”하는 대신, 오늘날 퍼저는 경계값(interesting values)과 코드 커버리지 피드백으로 경우의 수를 줄입니다. 같은 영역에서 두 방식의 테스트 케이스 수를 비교해 봅니다.

영역 길이 c 8바이트 동시 변이 바이트 d 2 바이트당 경계값 개수 k 8

경계값의 예: 0x00, 0x01, 0x7F, 0x80, 0xFE, 0xFF처럼 부호·오버플로 경계에 걸리는 값, 그리고 크기 필드라면 실제 길이 ±1. 논문도 영역 추출 단계에서 00·FF를 넣어 보았는데, 같은 생각을 생성 단계까지 넓히면 256^d 대신 k^d로 줄어듭니다.

2017년 이후 표준이 된 접근

커버리지 기반 퍼징(AFL/AFL++, libFuzzer, honggfuzz): 새 코드 경로를 연 입력만 남겨 다음 변이의 씨앗으로 씁니다. “어느 영역이 취약한가”를 사람이 고르는 대신 실행 피드백이 고릅니다.
결정적 단계 + 무작위 단계: 비트·바이트 뒤집기, 경계값 대입, 산술 증감을 짧게 훑은 뒤 무작위 조합(havoc)으로 넘어갑니다. 모든 조합을 다 시도하지 않습니다.
구조 인지 퍼징: 파일 형식 문법이나 사전(dictionary)을 써서 형식을 깨지 않으면서 필드를 바꿉니다. 논문의 010 Editor 템플릿 아이디어를 자동화한 셈입니다.
새니타이저(ASan, UBSan): 크래시로 드러나지 않는 메모리 오류까지 즉시 잡아 결함 판정을 정확하게 합니다.
지속 퍼징: OSS-Fuzz처럼 코드 변경마다 계속 돌리는 체계가 일반화되었습니다. 논문에서 쓴 CERT FOE는 이후 CERT BFF로 통합되었습니다.

현재 관점의 검토 의견

“모든 값의 조합”은 실행할 수 없습니다. 4바이트 영역에 d = 4까지 적용하면 약 43억 건이고, 논문의 AVI 추출 영역(약 0.08 KB)에 그대로 적용하면 천문학적인 수가 됩니다(③ 탭). 표 8의 932시간과 맞지 않으므로, 실제로 어떤 d와 어떤 영역에 적용했는지 밝혀야 합니다.
효율의 기준이 시간뿐입니다. 비교 지표가 테스트 경로 길이와 소요 시간뿐이고, 각 기법이 찾은 결함 수, 고유 크래시 수, 코드 커버리지가 없습니다. “기존 기법이 못 찾는 취약점을 추가로 발견했다”는 주장에 수치가 필요합니다.
시간 모델의 입력값이 없습니다. 수식 1(p = l·c·t/m)의 c(1회 변이 시간), t(바이트당 변이 횟수), m(장비 수)을 제시하지 않아 표 8을 재현할 수 없습니다. 일반 기법의 1,075시간을 파일 전체 BIT-FLIPPING으로 역산하면 테스트 1건에 약 2.4 ms인데, 플레이어를 실행해 결과를 확인하기에는 너무 짧습니다.
영역 추출이 사람의 판단에 의존합니다. 표 5의 반응(“음향 오류”, “인식 불가”)을 보고 취약 영역을 고르는데, 증상이 드러나지 않는 영역의 결함은 처음부터 제외됩니다. 영역 추출 단계 자체의 미탐률을 평가해야 합니다.
결함 판정 기준이 약합니다. “재생 중 정지”, “기능 오류” 같은 관찰 증상과 크래시를 구분해 보고해야 합니다. 메모리 오류 여부(새니타이저나 디버거 기반 분류)와 같은 결함의 중복 제거(triage)도 필요합니다.
비교 대상이 오래되었습니다. 2017년에는 이미 AFL(2013~)과 libFuzzer가 널리 쓰였습니다. 커버리지 기반 퍼저와 같은 시간을 주고 비교했다면 제안 기법의 위치가 분명해졌을 것입니다.
실험 범위가 좁습니다. 영상 파일 2종(AVI, FLV), 플레이어 2종, 파일 하나씩만 실험했고, ImageMagick 5.5.7(2003년 버전)은 매우 오래된 판입니다. 여러 입력 파일, 여러 버전, 반복 실행이 필요합니다.
표기 오류: 그림 3 캡션 “CVE-2008-574”는 본문의 CVE-2008-5745와 다르고, “AVX 파일”은 AVS로 보입니다. 표 8 ‘헤더 대비’ 비율도 표의 시간으로 다시 계산하면 433.7% → 435.5%, 219.5% → 220.2%로 조금 다릅니다.

수업 과제

③ 탭에서 영역 길이 8바이트, d = 2일 때의 테스트 케이스 수를 손으로 계산하고, 하루 안에 끝내려면 장비가 몇 대 필요한지 구하세요.
⑤ 탭의 경계값 방식으로 같은 영역을 테스트하면 몇 건으로 줄어드는지 계산하고, 그 대신 무엇을 놓칠 수 있는지 토론하세요.
“기법 A가 기법 B보다 효율적이다”를 보이기 위한 실험 설계(지표, 반복 횟수, 통계 검정)를 작성하세요.
직접 작성한 작은 파서 프로그램(교육용)을 libFuzzer나 AFL++로 퍼징하고, 커버리지가 시간에 따라 늘어나는 그래프를 그려 보세요.

연구를 보강한다면

제안 알고리즘의 d와 영역별 테스트 케이스 수를 표로 공개
찾은 고유 결함 수, 커버리지, 첫 결함까지 걸린 시간으로 효율 비교
AFL++ 등 커버리지 기반 퍼저와 같은 시간 예산으로 비교
경계값·사전 기반 변이로 다중 바이트 조합의 경우의 수를 줄이는 개선안
새니타이저를 쓴 결함 판정과 중복 제거, 발견 결함의 책임 있는 공개 절차 기술

그림 9 · 입력 파일 분석 과정

그림 11 · FLIPPING 알고리즘 흐름도(일부)

그림 12 · 4바이트 영역의 순차 변이 방식

그림 출처: 김상수·강동수, 「멀티미디어 파일 취약점 분석을 위한 퍼징 기반 테스트 케이스 생성 기법」, 보안공학연구논문지 14(6), pp.441–458, 2017. 교육 목적으로 출처를 밝혀 인용합니다.

연구·교육용 데모 · 테스트 케이스 수와 시간은 논문의 규칙으로 계산한 값이며, 이 페이지는 실제 변이 파일을 만들거나 소프트웨어를 실행하지 않습니다.