요약

타깃이 자동으로 정해지는 다중 지향성 퍼징으로, 정적분석 결과인 수천 개의 예상지점을 가지고 인풋을 스케쥴링 함.

키워드

큐 컬링 | Sanitizer-guided fuzzing (SGF)

1. 목적

• 다이나믹 큐 컬링으로 퍼저의 성능 최적화 (w/ .favored flag)
• 시드-타깃 거리 계산 개선 (w/ function-lvl CG, CFG, and Static analysis)
• 타깃 우선순위 동적 조정 (w/ instrumentation)

2. 핵심 개념

• 다이나믹 타깃 우선순위
  • 타깃 메타데이터 (hit_freq, reached, triggered) 활용
  • 런타임 중 타깃 상태 갱신
  • 덜 탐험된 타깃 우선순위 상승
• 다이나믹 시드-함수 거리
  • 정적 거리 맵 (LLVM-IR 기반 분석)
    • f_i (prologue BB m) 에 f를 call하는 BB m_f가 있을 시, dbb(f_i, f) = mindbb(m, m_f)
    • 함수인 이유 : BB 단위면 오버헤드가 심해서
    • 함수 내부는 일반 퍼징 테크닉 활용
  • 다이나믹 런타임 거리 계산
    • 시드가 지나는 각 함수와 목표 함수간 거리의 min
  • indirect call은 고려하지 않지만, 잘 핸들됨을 예제로 보임
  • 기존 Directed Greybox Fuzzing (DGF), Sanitizer-guided fuzzing (SGF)에서 쓰이던 조화평균 거리가, 여러 타깃의 정보를 어 흐릿하게 만들어 버리는 단점을 해결.

3. 구현

• 모든 sanitizer 레이블 고려
  • llvm bc에 instrument한 그 각 줄을 타깃으로
  • sanitizer 레이블은 compiler-rt
• LLVM 기반 정적 분석 1,500LoC
  • CFG, CG 추출
  • 정적 함수 거리 계산
• AFL/AFL++ 확장
  • cull_queue에서 inter-function exploration 구현 2,000LoC
• 컴파일러 Instrumentation 200LoC
  • 런타임 거리 갱신
  • 타깃 메타데이터 기록

4. 전략

• 큐컬링
  • 함수 간 탐색 (inter-function exploration)
    • 미도달 함수마다, 가장 가까운 시드.favored = 1
  • 함수 내 탐색 (intra-function exploration)
  • 타깃 발동 기반 exploitation
    • t.reached를 모아, 가장 적게 건드린 20%의 각각마다, 가장 빠르게 도달하는 시드.favored = 1
  • 각 행위가 목적달성 못하고 오랜시간 지나면 다음행위로
  • 자세한 건 cull_queue (FishFuzz)
• 타깃 크기 관리
  • 대규모 타깃 집합 (>20k)에서도 효과적 동작
  • 작은 타깃 집합(~10)에서 한계 존재

5. 결과

• 벤치마크 성능 비교
  • TortoiseFuzz, SAVIOR의 벤치마크 + ad-hoc 벤치마크 (Two-Stage)
    • 제외: non-resolvable exception, non-compatible to OS
  • 기존 DGF(SGF 포함) 대비 개선
  • 30 real-world program 대상 실험, 1주일
    • TortoiseFuzz [27], SAVIOR [7], GREYONE [9], FuzzGen 의 프로그램 대상
    • 38개 새로운 CVE 발견
• 다양한 프로그램에서 탐색 및 버그 발견 효과 확인
• UBSan 벤치마크는 타깃이 버그가 아니라 그냥 의도된 overflow일 수도 있음

6. 이전 연구와 비교

• SGF vs FishFuzz
  • SGF: 정적 타깃 우선순위
  • FishFuzz: 다이나믹 타깃 우선순위
• ParmeSan, SAVIOR
  • ParmeSan : 큐컬링한 이후에는 우선순위가 불변
  • FishFuzz는 더 빠른 타깃 검수 가능
• Two-stage Fuzzing (exploration + exploitation)
  • FishFuzz는 큐컬링과 타깃 우선순위로 개선
  • 기존 AFLFast, FairFuzz, EcoFuzz, K-Scheduler

7. 한계점

• cxxfilt에선 FFAFL이 우세, CVE-2017-13731은 FFAFL++과 AFL++만 발동
  • “이것은 FishFuzz가 intra-ftn. explor.은 건드리지 않기 때문이다”
• 보통 exploitation을 길게하면 좋지만, UBSan같이 간단한 타깃은 아님
• 타깃집합이 ~10로 작으면 FishFuzz가 별로다.
  • 여러 개 만들고 트레이드오프 계산필요