[PAPER REVIEW] MEUZZ: Smart Seed Scheduling for Hybrid Fuzzing

BACKGROUND

Hybrid fuzzing

• fuzzing과 비교했을 때 hybrid fuzzing은 추가로 concolic execution(퍼징된 경로를 다시 가서 경로의 조건을 해결하고 새로운 경로를 시도하는 것)가 있다.
• 목표: 높은 기능(concolic execution으로 복잡한 조건을 풀어서 커버리지와 버그를 갖는)을 하는 시드를 알아내는 것
• 하이브리드 퍼저에서 제한된 시간에서 콘콜릭 실행을 효율적으로 사용하기 위한 시드를 추정하는 것이 중요
• 하이브리드 퍼징 흐름
  • 언제 퍼저가 콘콜릭 엔진을 실행할지 모니터링
  • 콘콜릭 실행에 사용되는 환경변수 설정
  • 퍼저와 콘콜릭 실행기 사이에서 입력을 선택하고 필터링

 

휴리스틱 기반 시드 선택 방식

1. 새로운 코드 커버리지에 도달하면서 작은 크기를 갖는 시드를 선호하는 방식으로 시드를 선택
2. 한계: 다른 프로그램에는 동일하게 수행되지 않음
3. 시드 크기가 작을수록 좋은 기능을 갖는다
4. 평가 결과, 특정 프로그램에는 적용되지 않음

 

지도 학습 (supervised machine learning)

• 라벨링된 데이터로부터 학습하고 학습된 지식을 알지 못하는 데이터에 적용하는 기계학습
• classification과 regression이 주요 요소
  • classification: 카테코리를 예측
  • regression: 이전에 관찰한 데이터를 기반으로 새로운 데이터에 대한 수치 값을 예측
• 언제 모델이 업데이트되느냐에 따른 분류(online, offline)
  • online learning
    • 학습 환경에 매 초마다 바뀔 수 있어서 새로운 샘플이 들어올 때마다 모델을 업데이트 하는 것
    • ex. stochastic gradient descent(SGD) 알고리즘 사용
  • offline learning
    • 새로운 데이터가 보일 때 전체 데이터셋을 대상으로 모델을 재학습
    • ex. random forest(RF) → 단점: 학습 시간이 오래걸리고 높은 전력 소모로 online fuzzing에는 적합하지 않음

---

MOTIVATION

하이브리드 퍼징에서 최적화된 시드 선택의 중요성

하이브리드 퍼징에서 휴리스틱 방식으로 시드를 스케줄링하는 방법은 서로 다른 프로그램에 일반화하여 적용 불가능

• 한계: 휴리스틱 기반 방식은 최적화되지 않은 시드를 선택하면 시간 제약 때문에 콘콜릭 실행에서 이익을 얻을 수 없어 버그 탐지 속도를 느리게 할 수 있다.
• 최적화된 시드 스케줄링을 사용하지 않는 하이브리드 퍼징 단점
  • 하이브리드 퍼징에서 콘콜릭 실행은 느리기 때문에 속도를 높일 수 없고, 대체로 경로 폭발 문제나 timeout 문제를 직면한다.
  • 시드 스케줄링 방식이 퍼징 결과의 품질에 큰 영향을 미친다.

→ 이러한 문제 해결 위해 지도 학습을 하이브리드 퍼저에 적용하여 일반화할 수 있는 시드 스케줄링 방식 사용하는 MEUZZ 제안

기계학습 알고리즘 방식에서의 시드 선택의 효율성

• 실험 결과, 프로그램마다 학습 기반으로 자동으로 시드를 선택하는 전략이 서로 다른 프로그램에 대한 시드 선택 시 규칙을 고려하지 않아도 됨
• ML을 시드 선택에 적용할 수 있는데, 시드 선택 또한 학습할 수 있기 때문

---

DESIGN

 

Figure 3: System overview of MEUZZ

비슷하거나 동일한 프로그램을 대상으로 과거의 시드 스케줄링을 한 지식을 기반으로 어떤 새로운 시드가 더 좋은 퍼징 성능을 가져올지 결정

학습 위해 추출하는 정보: 코드 도달 가능성, 동적 분석에서 특성 추출

(1) 사전에 정의된 시드나 빈 시드로 프로그램을 퍼징

(2) 특징 추출

(3) 예측: 추출된 특성은 알지 못하는 시드의 커버리지를 예측하는데 사용

(4) 콘콜릭 엔진은 잠재적으로 영향력이 있는 시드를 받아서 변형에 사용

(5) 콘콜릭 실행으로 선택된 시드의 descendant tree를 추론

(6) 이전에 선택된 시드의 descendant tree를 기반으로 라벨링

(7) 학습 과정의 타입에 따라 모델을 업데이트 또는 재학습

 

feature engineering (특징 추출)

코드의 도달 가능성과 동적 분석을 기반으로 특성을 경량화하는 과정 → MEUZZ는 개별적인 특성 추출에 5 micro second만 소요

고려하는 특성: bug-triggering, coverage, constraint solving, empirical

1. bug-triggering
   • 기존 연구인 Savior에 영감을 받아, 도달 가능한 sanitizer instrumentation 수를 버그를 트리거할 수 있는 측정으로 사용 Sanitizer instrumentation은 놓치는 버그가 없는 sound 분석이므로 과 근사치 제공
   • 추출하는 특성
     • count of reachable sanitizer instrumentation: 시드에서 트리거되는 경로에서의 모든 분기에 대해 도달 가능한 sanitizer instrumentation 수가 계산되고 합해진다.
     • count of reached sanitizer instrumentation: 주어진 시드에서 트리거될 수 있는 경로 내 모든 분기에 대해 퍼저에서 도달된 sanitizer instrumentation의 수를 합한다.
2. coverage
   • 콘콜릭 실행은 복잡한 분기 조건을 해결하는데 좋은데, 하나의 입력으로 실행했을 때 많은 해결되지 않은 분기가 있다면 이는 코드 커버리지를 증가할 수 있다. 조건문과 동일한 곳에서 왔으면 이는 neighbor branch라 한다.
   • 시드의 새로운 커버리지 가능성 추정 위한 특성 추출
     • count of undiscovered neighbor branches: 주어진 시드에서 트리거된 경로 상의 모든 분기에 대해, 이웃과 비교하여 모든 이전 분기가 트리거되었는지 확인하고 이전에 발견하지 못한 이웃 분기를 합한다.
3. constraint solving
   • 콘콜릭 실행의 해결 능력에 영향을 주는 특성을 가져온다. 이러한 특성은 전체 하이브리드 퍼저에 영향 줄 수 있다.
   • 추출하는 특성
     • count of external call: 외부 함수를 만났을 때 경로 실행이 멈추게 되어 외부 함수 호출은 콘콜릭 실행기에 부정적인 영향을 준다. 따라서 주어진 시드에서 실행되는 경로에서의 외부 함수 호출 수를 기록한다.
     • count of comparison instruction: 주어진 시드로 실행된 경로에서 cmp 명령어 수를 기록하는 특성이다. 비교문은 실행 경로에서 제약조건에 해당하므로 나중에 SMT solver에서 해결되어야 한다. 하지만 constraint solving에 시간소모가 많이 되고 타임아웃의 원인이 될 때가 있다.
     • count of indirect call: 주어진 시드로 실행된 경로 상에서 간접 호출 명령어의 수를 기록하는 것이다. 간접 호출은 Symbolic pointer가 있는 간접 호출을 콘콜릭 실행기가 만났을 때 state 폭발 문제가 발생할 수 있다. (심볼릭 포인터에서는 해결할 수 있는)
     • length of path: 주어진 입력에서 실행된 분기의 수를 기록하는 특성이다. 큰 반복문의 졵재를 식별하는데 도움이 되는데, 큰 반복문은 state 폭발이나 solver 타임아웃의 원인이 될 수 있기 때문이다.
4. empirical
   • 기존 연구의 empirical 관찰을 기반으로 한 특성으로 ,퍼징 성능에 영향을 줄 수 있음
     • input size: 기존의 휴리스틱 방식을 사용한 도구에서 시드 스케줄링 결정을 하는데 입력 크기를 다뤘다. 짧은 입력은 빠르게 실행을 끝내서 콘롤릭 실행기나 퍼저가 다른 입력으로 탐색할 기회를 준다. 큰 입력은 더 많은 기능을 트리거할 가능성이 있다. 따라서 본 연구의 접근 방식에서는 입력 크기를 잠재적인 특성으로 고려하였다.
     • first seed with new coverage: 주어진 시드가 새로운 분기를 발견했는지 여부에 대한 boolean 값. 이는 해당 시드가 더 새로운 커버리지를 트리거할 가능성이 있다고 봄.
     • queue size: 당시의 쿼리에서 퍼징 큐에서 얼마나 많은 양의 입력이 ㄱ저장되었는지를 기록하는 특성으로 큐가 길면 새로운 커버리지를 발견할 가능성이 적다고 본다.

 

data labeling

라벨링은 지도 학습에서 필수적인 단계로, 잘 라벨링되었으면 더 그럴듯하게 예측할 수 있다.

목표: 사용성이 있는 (쓸모있는) 시드를 선택하는 것

시드의 실용성을 확인하는 방법: 해당 시드를 퍼저에 줘서 결과를 확인 → genetic algorithm(GA)를 사용하는 퍼저에서 결과는 input descendant tree가 나오는데, 퍼저의 큐에서 시드를 parent-child 관계로 나타낸 것이다. 이때 edge는 앞선 시드와 앞선 시드로부터 변형되어 생성된 시드를 연결한다. 콘콜릭 실행으로 생성된 입력이 분기의 neighbor일 때 GA 알고리즘을 사용하여 나중에 변형하기 위해 큐에 넣는다. 시드의 descendant tree가 커지면 퍼저의 코드 커버리지를 더 높이는데 해당 시드가 기여할 수 있는 것이므로 입력 descendant tree의 크기를 라벨로 하여 라벨링을 한다. ㅈ

 

prediction & training

시드의 유망성을 예측하기 위해 데이터 준비

시드의 descendant tree의 노드에 라벨링된 시드가 많이 있으면, 퍼저에서 새롭게 생성된 입력에 대해 regression 모델이 실용성을 예측하고 잠재성 있는 시드를 콘콜릭 엔진에 전달한다.

초기 입력은 샘플이 적기 때문에 모델이 랜덤이나 naive하게 예측하지만, 더 많은 시드가 생성될 수록 모델이 업데이트되면서 모델이 안정적이게 된다.

퍼징 과정에서 실시간으로 시드가 변형될 때 모델 업데이트와 예측은 제한된 시간 윈도우에서 이루어져야 한다. 이 제한은 Online learning 접근 방식으로, 모델이 새로운 데이터가 있을 때만 점진적으로 업데이트될 수 있다. 모델은 모든 이전 데이터를 저장하지 않고 매 반복회차마다 모델을 학습하지 않고 이전 모델과 퍼징이 만드는 역사, 들어오는 입력 기반으로 점진적으로 학습이 이루어진다.

 

updating model

online 또는 offline과 같이 학습 타입에 따라 동적으로 모델을 업데이트하고 재학습하는 과정이 필요하다.

online learning의 경우 recursive least square(RLS) 알고리즘을 사용하여 선형 모델을 업데이트한다. offline learning의 경우, 모델은 모든 과거 데이터 기반으로 매 반복회차마다 재학습되어야 한다. 새로운 시드가 있을 때마다 모든 데이터셋에 대해 재학습하는 건 시간 소모가 커 보이지만 평가 결과 실용적임을 알 수 있다.

---

IMPLEMENTATION

engine

Fuzzer engine: AFL-2.52b

concolic execution engine: SAVIOR (KLEE의 re-engineered variant)

ML engine: svf(도달 가능성 예측)

instrumentation tool: UBSAN

 

feature extraction

undiscovered branch: 컴파일 타입에서 분기를 기록하고, 트리거된 분기에서 이웃이 커버되었는지 확인하는데 사용

cmp, call instruction: 컴파일 시간에서 특성을 추출

size, queue size, new coverage: 런타입 입력 replay나 operating system api 통해 특징 추출

bug triggering 특성: 타겟 프로그램을 먼저 UBSan으로 계측한 후, SVF를 기반으로 도달 가능성을 분석하

sanitizer instrumentation 양: SVF 기반으로 한 도달 가능성을 분석하여 이 수를 추출

트리거된 분기 수집: 입력 통해서

 

label inference

AFL의 큐에서 시드 이름이 [id, source, mutation, new cov] 형태이므로,큐 내의 시드를 횡단하는 방식으로 seed descendant tree 크기를 계산했다.

---

EVALUATION

• 모델 이식성 검증: 리얼월드 프로그램 대상 24시간 실험 진행 결과, 56개의 실험 중 68%에서 모델 이식에 성공
• 모델 재사용성 검증: 리얼월드 프로그램 대상 24시간 실험 진행 결과,  평균 7.1% 더 많은 커버리지 확보

---

RELATED WORK

휴리스틱 기반 시드 선택 방식

• AFLfast, Digfuzz → 퍼저에서 적게 탐색된 경로에 우선순위를 주는 휴리스틱한 방식
• Savior → UBSan 라벨링된 코드 경로에 대한 시드를 선호
• QYSM, ProFuzzer → 작은 크기의 시드 선호

---

CONCLUSION

contribution

• 효율적이고 일반화된 접근 방식으로, 시드 우선순위와 스케줄링에 ML을 적용한 최초의 연구
• 실용적인 특징과 라벨 기술
• ML 모델의 재사용성과 확장성
• 오픈소스