[Paper Review] FuzzGuard: Filtering out Unreachable Inputs in Directed Grey-box Fuzzing through Deep Learning

BACKGROUND

Fuzzing

타겟 프로그램에 많은 입력을 줘서 프로그램 예외를 분석하여 버그를 노출시키는 소프트웨어 테스트 기술

 

grey-box fuzzing

높은 효율성과 성능

1. Coverage-based grey-box fuzzing (CGF)
   • 목표: 크래시를 더 많이 트리거하기 위해 코드 커버리지를 증가시킴
   • 예시: AFL
2. Directed grey-box fuzzing (DGF)
   • 목표: 버그가 있는 코드 내 버그를 트리거하기 위한 입력 생성
   • 랜덤 입력으로는 버그를 트리거 할 가능성이 낮기 때문에, DGF는 타겟 프로그램을 instrument하여 얻은 런타임 정보를 기반으로 버그 코드에 도달할 수 있는 입력을 생성
   • 이미 알려진 취약점을 기반으로 PoC exploit을 생성하여 버그 코드에 적용하도록 하는 퍼저도 있음
   • 예시: AFLGo, SemFuzz, Hawkeye
     • AFLGo: CFG에서 basic block 사이 거리를 계산하고 entrypoint에서 버그가 있는 코드까지의 path를 계산한 후, mutation 시 적합한 입력이 선택되도록 거리를 utilize

 

MOTIVATION

DGF에서 생성된 많은 입력은 타겟 버그 코드에 도달하지 못함

• 버그 코드가 많은 복잡한 constraint 속에 있는 경우 해당 버그 코드에 도달하기 어렵다.
• ⇒ DGF인 AFLGo 퍼저로 실험한 결과, 91.7%가 넘는 입력은 버그 코드에 도달하지 못함
• 버그 코드에 도달 불가능한 입력은 퍼징 과정에서 많은 시간 소모
• ⇒ constraint가 복잡할수록 constraint 해결 시간 증가하기 때문

pattern recognization

• pattern recognization은 이전에 알지 못하는 이미지도 성공적으로 분류함
• 입력을 패턴으로 보고 버그 코드에 도달 가능한 입력 식별
• 이전 실행에서 타겟 코드에 도달한 것으로 라벨링 된 많은 양의 입력을 대상으로 모델을 학습
• 학습된 모델은 새롭게 생성된 입력을 받았을 때 버그 코드에 도달 가능성을 예측 (타겟 프로그램 실행 없이)

challenge

1. 균형 잡힌 라벨링된 데이터 부족
   • 퍼징 초기에는 도달 가능한 입력이 없어서 퍼징 과정에서 도달 가능한 입력은 불균형함
   • ⇒ 도달 가능한 입력이 하나의 bit flip으로 변형된 입력을 만들었을 때 이 입력은 실행 경로를 바꾸고 도달 불가능한 입력이 될 수 있기 때문
   • 균형 잡힌 라벨링된 데이터 없이는 학습된 모델이 over-fitting 될 수 있음
2. 데이터의 대표성 부족
   • 새롭게 생성된 도달 가능한 입력은 training set 내 도달 가능한 입력과 다른 양상을 띌 수 있음
   • ⇒ 이 새로운 입력은 이전에 본 적 없는 새로운 실행 경로에서 왔기 때문
   • 이로 인해 학습된 모델은 도달 가능한 새로운 입력도 예측하지 못할 수 있음
   • ⇒ 하나의 실행 경로를 갖는 입력으로 모델을 학습하면 새로운 실행 경로로 가는 도달 가능한 새로운 입력을 예측하지 못할 수 있음
3. 효율성
   • 학습 시간 비용과 예측 시간 비용에 제한이 있어야 함
   • ⇒ 입력의 도달 가능성을 예측하는 시간이 프로그램 실행 시간보다 길다면, 예측이 의미가 없기 때문

 

DESIGN

FuzzGuard

• 이전 실행을 학습한 기반으로 새롭게 생성된 입력이 타겟 버그 코드에 도달할 수 있는지 예측하고 도달할 수 없으면 해당 입력으로 실행하지 않아서 실행 시간을 줄일 수 있음

 

model initialization

1. 입력 생성 및 도달 가능성 라벨링

많은 입력을 생성하면서 해당 입력이 버그를 트리거했는지 확인한다. Fuzzguard는 해당 입력과 입력의 도달 가능성을 저장한다.

1. FuzzGuard는 라벨링된 데이터 대상으로 모델 학습

• 이 라벨된 데이터를 입력으로 initial 모델을 학습시킨다. 이때 라벨된 데이터는 unbalance하다.
• (Challenge 1)데이터 불균형 문제 해결: step-forwarding approach 사용
  • 타겟의 중간 단계에서 버그 코드에서 사전 지배 코드를 선택하고 실행 시 이 사전 지배 코드에 먼저 도달하도록 한다. ⇒ 모델이 항상 학습 초기에 사전 지배 코드에 먼저 도달하기 때문에 빨리 균형된 데이터를 얻을 수 있다. 실행 시간도 감소
  • pre-dominating node:
    • 버그 코드를 dominate하는 노드
    • 버그 코드를 실행하는 경로는 pre-dominating node에 전달됨
    • pre-dominating로 표시된 node의 도달 가능성은 보장됐기 때문에 모델 학습 시 pre-dominating node에 도달하지 못하는 입력은 버그 코드에 도달 가능성이 없는 입력이므로 필터링 → 이렇게 pre-dominating node의 balance 된 데이터 얻을 수 있음
• 학습 모델 : CNN model
  • 분류 작업 수행
  • RNN은 바이트의 나열을 학습하는데 적합하고 긴 데이터가 들어오면 이전 feature를 망각할 수 있음. CNN은 긴 데이터 처리하는데 적합하고 학습 시간이 더 느림
  • 모델은 3-layer로 구성
    • layer 1 : 바이트 간 관계 학습
    • 나머지 2개 레이어 : 고차원 feature 학습 (예. 여러 바이트를 결합하여 임력에서 필드 생성, 실행에 영향을 줄 수 있는 바이트를 결합

 

model prediction

퍼저가 새로운 입력을 생성하면 FuzzGuard는 이 입력의 도달 가능성을 예측

(Challenge 2) 모델은 새로운 양상을 보이는 생성된 입력의 도달 가능성을 예측할 수 없는 문제 해결: representative data selection approach 사용

• 각 mutation 단계에서 실행과 학습에서 사용하기 위한 입력을 가져와서 학습 데이터로 사용 (각 mutation마다 이전에 본적 없는 새로운 양상을 보이는 입력을 샘플링해서 모델이 이를 학습하게 함)
• 효율성 증가 및 모델 정확도 증가
• 도달 가능성이 있는 입력만 타겟에 입력으로 줘서 실행
• 큰 값으로 구성된 입력의 5%만 실행에 사용해도 시간 비용 커서 적은 입력만 선택
  • 서로 다른 seed로부터 서로 다른 mutation을 적용하여 생성된 input set 2개의 분산이 비슷하다면 이 중에서 적은 입력만 선택 → seed similarity degree(SSD)로 계산 : 만약 두 seed가 비슷하고 mutation 전략이 identifal하면 결합한 집합에서 적은 입력을 선택

 

model updating

• 2단계에서 새롭게 수집된 도달 가능한 입력을 대상으로 모델 업데이트
• (Challenge 3) 모델 업데이트 시 시간 제한 문제 해결: incremental learning 사용
  • 한 번에 모든 데이터를 학습하지 않고 매 시간 모델에 데이터 집합을 줘서 학습함
  • 모델 재학습 없이 기존에 학습한 지식을 유지하면서 새로운 데이터에 적응
• 언제 모델을 업데이트해야 하는가
  • 모델 정확도를 위해서 새로운 라벨링된 데이터 셋이 있으면 해당 데이터로 학습해야 하지만, 너무 빈번하게 모델을 업데이트하면 학습에 많은 시간을 소요하고 퍼징 효율성에 영향 줄 수 있고 너무 모델 업데이트를 안 하면 정확도가 떨어짐
  • 모델 업데이트 시기: 모델이 “outdated”되었을 때, 즉 새로운 pre-dominating node에 도달했을 때 모델 정확도가 떨어지게 됨. False positive rate를 계속 기록하다가 False positive rate인 감마가 threshold를 넘어갈 때 모델 업데이트함. 업데이트 후 다시 False positive rate를 0으로 초기화하고 기록 계속
• 입력을 바로 mutate하지 않고 버그에 도달 불가능한(버그를 트리거할 가능성이 없는) 입력을 필터링하여 효율성 증가시킴
• 도달 가능성이 없는 입력은 data pool(PUI)에 저장해서 추후 모델 업데이트하면서 정확도가 높아지면 그때 다시 도달 가능성 체크 → missing PoC 없도록

 

IMPLEMENTATION

AFLGo 기반으로 FuzzGuard 구현

 

MODEL INITIALIZATION

• 모델 학습 시작 시기: balanced data가 충분히 모였을 때 → 구현 상으론 5만개의 balance input 모이면 학습 시작
• 모델 학습 전, 타겟에 입력 실행해서 도달 가능성 기록
• 버그 코드의 pre-dominating node 사전에 알아야 함 → LLVM을 이용하여 타겟 프로그램의 call graph(CG)와 control flow graph(CFG) 생성하고 NetworkX를 이용하여 pre-dominating node 자동으로 찾음

MODEL PREDICTION&UPDATING

• seed similarity degree(SSD)의 threshold(세타 s)를 0.85로 설정
• 각 mutation에서 입력 sampling rate = 5% → SSD > threshold 되면 sampling rate = 1 - 세타 s(3%보다 적음) → 평가 상으로 이 threshold 설정이 성능 가장 좋았음

MODEL IMPLEMENTATION

training model

• PyTorch 사용하여 CNN model 구현
• 3개의 1차원 convolution layer (k=3,stride=1)
  • 하나의 1차원 convolution layer는 각 입력을 row 순서로 받고 각 row는 1024바이트
  • 각 convolution layer는 pooling layer 뒤에
  • Activation function: ReLU
• Dropout Layer
  • Disabling rate =20%
  • 신경망에서 over-fitting 방지 위해 사용
• fully-connected layer
  • 신경망 끝에 위치
  • 각 노드에 대해 각 타겟 경로에서 버그 코드로의 도달 가능성 scoring 위해 사용
• Adam Optimizer
  • function coverage 학습을 빠르고 안정적이게 하기 위해 사욜

Deployment of Fuuzguard

• 타겟에 입력 전달 전 Fuzzguard로 전달되고, 해당 입력의 실행 경로가 버그 코드에 도달 가능한 경우에만 입력을 반환
• 타겟 실행 후, AFLGo의 afl-fuzz.c에 함수 Checker() 추가하여 도달 가능성이 있는 해당 입력을 Checker에 줘서 모델이 해당 입력으로 학슺하여 모델 업데이트 가능하게 함

 

EVALUATION

10개 프로그램 대상 45개 취약점 이용한 성능 평가 → vanila AFLGo와 비교

AFLGo 대비 1.3배~17.1배 성능 증가

 

RELATED WORK

퍼징 성능을 높이기 위해 딥러닝을 적용한 연구

• Godefroid et al. 높은 코드 커버리지를 갖는 입력을 생성하기 위해 RNN 적용
• Rajpal et al. 입력의 어떤 부분이 코드 커버리지를 높이는지 알기 위해 RNN-guided mutation filter 사용함. 이렇게 알아낸 위치를 중심으로 입력을 mutation하여 더 높은 코드 커버리지 얻음
• Nichols et al. AFL의 성능을 향상시키기 위해 입력이 프로그램에서 실행된 경로를 예측하는데 GAN 사용
• Angora, NEUZZ path constraint를 해결하기 위해 gradient descent 알고리즘을 사용하고 코드 커버리지 높이기 위해 모델을 학습

 

CONCLUSION

Contribution

• 도달 불가능한 입력을 식별하고 제거하는 데 딥러닝을 적용한 새로운 기술
• AFLGo와 같은 기존 최신 퍼저와 비교했을 때 88%까지 퍼징 시간 단축