[PAPER REVIEW] Neuzz: Efficientfuzzing with neural program learning

BACKGROUND

Fuzzing

랜덤 테스트 입력을 생성하고 생성한 입력으로 타겟 프로그램을 실행하여 잠재적 보안 취약점을 트리거한다. 퍼징의 단순성과 적은 성능 오버헤드로 리얼월드 프로그램의 다양한 취약점을 발견하는데 많이 사용해왔다.

퍼징에서의 최적화 문제

• 제한된 시간 동안 발견할 수 있는 취약점을 개수를 최대화하는 입력을 찾는 것이 목표
• 대부분의 퍼저는 코드 커버리지(ex. edge coverage)를 높여서 취약점을 발견할 가능성을 높이기 위해 가능한 많은 프로그램 코드를 실행함
• 퍼저에서 최적화 위해 진화 알고리즘 사용
  • 코드 커버리지를 최대화하는 입력 생성하는 것
    • 초기 시드 입력을 시작으로, 시드에 랜덤 변형을 가하면서 새로운 입력을 생성하고, 타겟 프로그램에 이 입력을 줘서 실행해서 유망한 입력(새로운 코드 커버리지를 달성할)만 추후 mutation에 사용하기 위해 저장
    • 입력 corpus가 커지면, 진화적 방식은 새로운 코드에 도달하는데 효율성이 떨어지게 됨

 

최적화 문제

$F(x)$ subject to

최적화 문제 구성요소

• $x$ : vector
• $F(x)$ : 최대화 또는 최소화하려는 objective function
• $C_i(x)$ : constraint function

최적화 문제 목표

• $C_i(x)$를 충족하면서 $F(x)$를 최소화 또는 최대화하는 $x$를 구하는 것

최적화 방법

1. Function smoothness & optimization
   • objective/constaraint 함수가 부드러울수록, 최적화 알고리즘에서 기울기나 고차 도함수 계산의 정확도 높아짐
   → 본 논문에서는 constraint 함수를 사용하지 않는 unconstrained optimization 문제를 다룸 $C = \empty$ → gradient-guided approach 사용
2. convexity & gradient-guided optimization
   • convex function(블록함수): 그래프의 두 점을 연결한 곡선보다 위에 있는 함수를 convex라고 함
   • $f(tx + (1-t)y) \leq tf(x) + (1-t)f(y), \forall t \in [0,1]$
   • non-convex function: gradient-guided approach가 non-convex 함수에서 objective function이 모든 값에서 더 큰 값이지만 전체 매개변수 범위에서 다른 곳에 다른 더 큰 값이 존재하는 로컬 최적화 문제가 있음
3. fuzzing as unconstrained optimization
   • 퍼징 == unconstrained optimization problem → 고정된 입력으로 프로그램을 테스트했을 때 발견할 수 있는 버그/취약점 수를 최대화하는 것이 목표
   • objective function: $F_p(x)$ ⇒ 입력 $x$로 타겟 프로그램 $p$를 실행했을 때 입력 $x$가 버그/취약점을 트리거하면 1을 리턴 → 효율적으로 최적화가 어려움
   • 대부분 greybox fuzzing에서는 테스트하는 코드 양을 최대화함 → $F^`_p(x)$ 프로그램 $P$에 입력 $x$를 줘서 실행했을 때 새롭게 커버된 edge가 있을 때 해당 새롭게 제어된 edge 수를 리턴 ⇒ 이때 대부분 evolutionary 기술 사용하는데, 리얼월드 프로그램은 서로 다른 실행 경로에서 서로 다른 동작을 하기 때문에 불연속성을 가져서 여기에 gradient-guided optimization 적용이 어려움

 

Feedforward neural network (FFNN)

• 노드 간 사이클을 형성하지 않고 노드를 연결하는 인공 신경망

---

MOTIVATION

퍼징의 한계 → 트리거하기 어려운 버그 찾는데 효율적이지 않음

진화 알고리즘은 다양한 버그를 유발할 수 입력을 생성하지만, 무작위 변이 시퀀스에 갇히는 문제 발생

 

gradient-guided 최적화가 퍼징에 적용하기 어려움

gradient-guided 최적화

• 진화 알고리즘 대안으로 제시됨.
• 기본 함수의 기울기나 고차원 미분을 효율적으로 활용하여 기계학습과 같은 영역의 고차원 구조의 최적화 문제를 해결하여 진화 알고리즘보다 뛰어난 성능 보임
• 한계: 서로 다른 리얼월드 프로그램의 branch가 서로 다른 행동을 보이는 불연속적인 행동 때문에 리얼월드 프로그램을 퍼징하는데 적용하기 어려움

→ 복잡한 실제 프로그램의 분기 동작에 대한 부드러운(smoothing) 근사치를 점진적으로 학습할 수 있는 대리 신경망 모델(FFNN)을 gradient-guided 입력 생성 방식과 함께 사용하여 퍼징 과정에서 효율성을 높임

---

DESIGN

1. neural program smoothing

프로그램의 불연속적인 분기 동작을 부드럽게 근사화하는 것은 기울기 유도 최적화에서 기울기나 고차 미분을 정확하게 계산하는데 필수적

평활화 과정(smoothing process)의 목표는 큰 오류 없이(원래 프로그램 동작에서 최소한의 편차만 발생) 프로그램의 분기 동작을 모방하는 부드러운 함수를 만드는 것

→ **feed-foward 신경망(NN) 사용 (**비선형 함수의 복잡성 추정 가능, 기울기나 고차 도함수에 대한 효율적이고 정확한 계산 가능)

 

2. gradient-guided optimization

smooth NN model이 학습된 후, 기울기나 고차 미분을 효율적으로 계산하는 데 사용하여 최적의 솔루션에 빠르게 수렴 가능

NN 모델의 부드러운 근사치의 기울기를 구해서 버그 발견을 최대화할 수 있는 타겟 변형 위치를 식별

→ gradient-guided input generation 방식 구현함

gradient-guided input generation

• 입력의 각 바이트 중에서 가장 높은 기울기 값을 가지는 바이트를 식별하고 해당 바이트를 변형하는 것
• 각 입력 바이트에서 기울기의 sign 값을 체크해서 objective function을 최대화/최소화하기 위해 어떤 방향으로 mutation해야 하는지 결정
• mutation bound 범위를 0~255로 제한하도록 clip 함수 사용

 

3. incremental learning

• AFL와 같은 evolutionary fuzzer 사용하여 생성된 테스트 입력을 NN 모델의 입력으로 모델을 학습
• 초기 학습 데이터는 프로그램 공간의 작은 영역만 커버할 수 있지만, 퍼징 과정에서 얻은 프로그램의 새로운 동작(새로운 edge 트리거되었을 때)을 포착한 새로운 데이터로 NN 모델을 학습하여 점진적인 학습을 수행하여 모델이 항상 업데이트되도록 함

NN 개선 문제

• 이전에 학습한 정보를 망각하는 문제 (딥러닝에서 stability-plasticity dilemma에 해당) 해결→ 새로운 작업을 학습할 때 가중치를 계속 바꿔줘서 너무 많은 변형이 이루어지지 않도록 해서 기존에 학습한 표현을 망각하지 않도록 함
• → coverage-based filtration 방식 사용 ⇒ old와 new 데이터에 대한 압축 요약 생성하여 이전 데이터와 함께 새로운 데이터에 대해 모델을 재학습하여 효율적으로 NN 학습

---

IMPLEMENTATION

환경

Ubuntu 16.04/18.04

초기 seed corpus

• AFL 1시간 학습 후 생성된 테스트케이스 사용

base fuzzer

AFL fuzzer 코드 기반으로 neuzz.c 작성

NN model 아키텍처

• kera 2.1.3
• Tensorflow 1.4.1 (backend)
• fully-connected layer
  • hidden layer의 activation function: ReLU
  • output layer의 활성화 함수: sigmoid → 새로운 edge 커버 여부 확인 위해
• epoch: 50 (전체 데이터셋으로 완전한 학습을 50회 진행) → 높은 정확도 (평균 95%) 위해
• 학습 방법
  • 각 10개 프로그램으로 2분 미만으로 학습
  • 학습 시간은 20분 미만

mutation and retraining

• mutation 알고리즘을 사용해서 1M mutation 진행
• 파라미터 i(iteration)를 10으로 설정한 후 5120개의 변형된 입력을 생성하고, 이 중에서 100개의 neuron 출력(100개의 탐색되지 않은 edge를 표현하는)을 랜덤으로 선정
• AFL의 forkserver를 이용하여 선정한 100개의 변형된 입력으로 타겟 프로그램 실행
• 새로운 edge를 커버한 새로운 입력을 점진적 재학습에 사용

model parameter (parameter tuning)

• readelf, libjpeg, libxml, mupdf의 4개의 프로그램의 edge coverage를 최대화를 보장하는 최적의 파라미터를 탐색

---

EVALUATION

서로 다른 6개의 파일 포맷을 갖는 10개의 리얼월드 프로그램을 대상으로 10개의 최선 퍼저와 비교

LAVA-M 데이터, CGC 데이터셋

→ 평가 결과, 버그 탐지와 edge coverage 측면에서 모든 퍼저보다 outperformed

edge coverage 비교

---

RELATED WORK

기존의 smoothing 기술 연구

• S et al., A et al. - 기호 실행에 너무 의존적이라 경로 폭발, 불완전한 환경 모델링, 큰 기호 메모리 모델링 오버헤드에 대한 한계로 규모가 큰 프로그램에는 적용이 어려움

딥러닝에서의 stability-plasticity dilemma 해결하기 위한 연구

1. 분산 모델, 정규화 또는 여러 모델로 앙상블을 생성하여 망각을 최소화하기 위해 새 모델과 기존 모델에 대해 별도의 표현 유지
2. 이전 데이터의 요약본 유지하면서 새로운 데이터에 대해 모델을 재학습하여 학습 효율성 높임

---

CONCLUSION

contribution

• 퍼징에 gradient-guided 기술 적용 시 프로그램의 smoothing의 중요성을 처음으로 고려함