SeedSmith: LLM-Driven Seed Synthesis for Directed Fuzzing

기술 요약: SeedSmith

문제 정의

지향적 퍼징(Directed fuzzing)은 사용자가 정의한 "싱크(sink)" 함수를 향해 퍼저를 유도함으로써 취약점을 찾아내는 것을 목표로 합니다. 그러나 본 논문은 지향적 퍼저가 광범한 캠페인 이후에도 크래시를 트리거하는 데 성공하지 못하게 만드는 두 가지 근본적인 과제를 식별했습니다.

1. 간접 호출의 불완전한 정적 분석 (C1): 많은 지향적 퍼저는 탐색을 가이드하기 위해 거리 메트릭(distance metrics)을 계산할 때 정적 분석에 의존합니다. 그러나 간접 호출(함수 포인터 또는 가상 디스패치를 통한 호출)은 정적으로 해결하기 매우 어렵습니다. 호출 그래프에서 호출 엣지(call edges)가 누락되면 거리 메트릭이 신뢰할 수 없게 되어, 전체 도달 가능한 경로가 퍼저의 가이드 알고리즘에서 보이지 않게 됩니다.
2. 크래시 전제 조건에 대한 시맨틱 가이드 부족 (C2): 퍼저가 싱크에 도달하더라도, 크래시를 트리거하려면 정밀한 입력 수준의 조건(예: 특정 필드 값, 형식 제약 또는 데이터 흐름 의존성)을 충족해야 하는 경우가 많습니다. 이러한 조건들은 커버리지 기반 피드백에는 보이지 않으며, 단순한 바이트 단위 변이(mutation)로는 실용적인 시간 예산 내에 이들을 동시에 충족하기 어렵습니다.

기존의 시드 생성 기술은 이러한 문제를 효과적으로 해결하지 못합니다. 문법 기반(Grammar-based) 및 포맷 기반 방식은 구조적으로 유효한 입력을 생성하지만 "싱크 인지 능력(sink awareness)"이 부족하여, 특정 취약점을 타겟팅하거나 이를 트리거하는 데 필요한 전제 조건을 해결하는 데 실패합니다. 반대로, 기존의 LLM 기반 접근 방식은 정적 분석 요약에 의존하는 원샷 프롬프팅(one-shot prompting)을 사용하는 경우가 많아, 전통적인 정적 분석에서 나타나는 불완전성과 반복적 추론의 부재라는 문제를 그대로 물려받게 됩니다.

방법론: SeedSmith

저자들은 숙련된 보안 분석가가 크래시를 트리거하는 입력을 구성하는 워크플로우를 재현하도록 설계된 에이전트 기반 LLM 파이프라인인 SeedSmith를 제안합니다. SeedSmith는 퍼저 불가지론적(fuzzer-agnostic) 시드 생성 프런트엔드로 작동하며, 이는 퍼저의 내부 로직을 수정하지 않고도 모든 다운스트림 변이 기반 퍼저의 초기 시드 코퍼스를 개선할 수 있음을 의미합니다.

이 시스템은 두 단계의 에이전트 파이프라인으로 설계되었습니다:

1. 타겟 준비 (Target Preparation)

에이전트 실행 전에, SeedSmith는 경량 정적 분석 및 인스트루멘테이션(instrumentation)을 수행합니다:

• 프로젝트 인덱싱: 함수 이름을 소스 코드 위치로 매핑하는 인덱스를 구축합니다.
• 호출 경로 식별: CodeQL을 사용하여 정적 호출 그래프를 추출합니다. 타입 시그니처 매칭을 통해 간접 호출을 해결하려고 시도하지만, 이 과정이 과잉 근사되거나 불완전할 수 있음을 인정합니다. 결정적으로, LLM의 컨텍스트 윈도우에 맞추기 위해 호출 그래프를 선형화된 표현으로 압축하는 경로 최적화(path optimization) 단계를 적용합니다(공통된 접두사/접미사를 보존하고 갈라지는 중간 부분을 축소함).
• 인스트루멘테이션: 크래시 탐지를 위해 새니타이저(ASAN, MSAN 또는 UBSAN)와 함께 타겟을 컴파일합니다.

2. 에이전트 기반 코드 탐색 (분석 에이전트)

이 단계는 컨텍스트 인식 코드 검색 도구를 갖춘 LLM 에이전트를 사용하여 코드베이스를 반복적으로 탐색함으로써 C1과 C2를 해결합니다.

• 반복적 추론: 원샷 프롬프팅과 달리, 에이전트는 하네스(harness)와 싱크 함수에서 시작하여, 간접 호출을 해결하고 데이터 흐름을 추적하기 위해 코드베이스를 반복적으로 쿼리합니다.
• 컨텍스트 인식 검색: 검색 도구는 고정된 라인 윈도우를 반환하지 않습니다. 대신, 시맨틱하게 완전한 단위(예: 함수 매치에 대한 전체 함수 본문, 변수 매치에 대한 전역 선언, 또는 구조체 매치에 대한 타입 정의)를 반환합니다. 이를 통해 에이전트는 정적 분석이 놓치는 간접 호출을 해결하고 입력 형식 요구 사항을 이해할 수 있습니다.
• 출력: 에이전트는 싱크 위치, 검증된 호출 경로, 크래시 전제 조건 및 생성 전략을 포함하는 구조화된 **분석 보고서(Analysis Report)**를 생성합니다.

3. 에이전트 기반 시드 생성 (시드 생성 에이전트)

이 단계는 분석 보고서를 소비하여 구체적인 테스트 입력을 생성합니다.

• 프로그래밍적 구성: 원시 바이트를 생성하는 대신, 에이전트는 구조적 제약을 충족하는 입력을 구성하기 위해 포맷 라이브러리(예: 이미지를 위한 PIL)를 사용하는 Python 스크립트를 출력합니다.
• 정제 루프 (Refinement Loop): 생성된 시드는 새니타이저가 적용된 바이너리에 대해 검증됩니다. 실행 피드백(크래시, 새니타이저 출력, 종료 코드)은 반복적인 루프(최대 10회)를 통해 에이전트에게 전달되어 스크립트를 정제합니다.
• 비용 최적ization: 탐색 단계에는 더 무거운 코드 추론 모델을 사용하고, 시드 생성 단계에는 더 저렴한 모델을 사용합니다.

주요 기여

1. 한계점 식별: 본 논문은 간접 호출의 불완전한 정적 분석(C1)과 크래시 전제 조건에 대한 시맨틱 가이드 부족(C2)을 지향적 퍼징 및 기존 시드 생성의 주요 병목 현상으로 공식적으로 식별했습니다.
2. SeedSmith 시스템: 시맨틱하게 유효한, 싱크를 타겟팅하는 시드를 생성하기 위해 코드베이스를 반복적으로 탐색하는 에이전트 기반 LLM 파이프라인을 설계하고 구현했습니다. 이는 온디맨드 방식으로 간접 호출을 해결하고 크래시 전제 조건을 추론하여 정적 분석 스냅샷의 한계를 극복합니다.
3. 대규모 평가: 26개 프로젝트에 걸친 23개의 Magma 버그와 115개의 ARVO 챌린지를 대상으로 종합적인 평가를 수행하여, 크래시 발견 및 크래시 도달 시간(time-to-crash)의 상당한 개선을 입증했습니다.

결과

저자들은 Magma 및 ARVO 벤치마크에서 네 가지 다운스트림 퍼저(AFL++, AFLGo, AFLRun, FairFuzz)를 사용하여 SeedSmith를 평가했습니다.

• Magma 성능:

  • SeedSmith 시드를 사용한 퍼저는 기본 시드 대비 기하 평균 크래시 시간 단축 속도가 **11.51× (AFL++)에서 14.66× (AFLGo)**에 달했습니다.
  • SeedSmith는 기본 시드가 24시간 내에 절대 트리거하지 못한 2개의 추가 버그(PDF011, SQL013)를 발견했습니다.
  • 5개의 버그는 "원샷(one-shot)" 방식으로 트리거되었습니다(LLM이 생성한 시드가 퍼저의 변이 없이 즉시 크래시를 발생시킴).
  • SeedSmith는 Magma 서브셋에서 크래시 발생 수와 크래시 시간 모두에서 Locus(시드가 아닌 술어(predicate)를 합성하는 대안적 LLM 증강 접근 방식)보다 우수한 성능을 보였습니다.

• ARVO 성능:

  • SeedSmith는 퍼저가 다양한 입력 형식(예: 바이너리 헤더, 프로토콜 문법)을 가진 16개의 이전 도달 불가능한 버그를 트리거할 수 있게 했습니다.
  • 크래시가 트리거된 59개의 ARVO 타겟에 대해, SeedSmith는 AFL++에서 3.09×, AFLRun에서 **3.02×**의 속도 향상을 가져왔습니다.
  • ARVO에서의 주요 기여는 단순히 기존 경로를 가속화하는 것이 아니라, 기본 코퍼스로는 완전히 도달할 수 없었던 크래시를 해제했다는 점입니다.

• 퍼저 불가지론 (Fuzzer Agnosticism): 결과는 SeedSmith가 커버리지 가이드 퍼저(AFL++와 같은)와 지향적 퍼저(AFLGo와 같은) 모두를 개선함을 보여줍니다. 특히, SeedSmith 시드를 사용한 AFL++가 타겟 크래시를 노출하는 데 있어 AFLGo보다 뛰어난 성능을 보였는데, 이는 고품질 시드가 범용 퍼저에게 지향적 퍼징 능력을 부여할 수 있음을 시사합니다.

의의

본 논문은 SeedSmith가 올바른 제어 흐름 경로를 인코딩하고 핵심 크래시 전제 조건을 충족하는 시드를 제공함으로써 "맹목적 탐색"에서 "지역적 정제(local refinement)"로의 전환을 나타낸다고 주장합니다. 경로를 반복적으로 추적하고, 간접 호출을 해결하며, 입력 제약 조건을 추론하는 보안 분석가의 수동 워크플로우를 자동화함으로써, SeedSmith는 정적 분석과 전통적인 시드 생성 방식이 남긴 근본적인 격차를 해결합니다.

그 의의는 다음과 같습니다:

1. 시드 품질을 퍼저 내부 로직으로부터 분리: 변이 기반 퍼저와 호환되는 드롭인(drop-in) 프런트엔드로 작동합니다.
2. 정적 분석의 한계 극복: LLM을 사용하여 정적 도구가 놓치는 간접 호출을 해결하고 시맨틱 제약 조건을 추론합니다.
3. 심층 취약점 해제: 이전에 도달 불가능했던 복잡한 실제 시나리오(ARVO)에서 크래시를 성공적으로 트리거함으로써, 초기 시드 코퍼스가 퍼징 파이프라인에서 매우 중요하면서도 종종 간과되는 개입 지점임을 입증했습니다.