논문 요약: 회색상자 퍼징 (Greybox Fuzzing) 의 상호작용 효과

1. 연구 배경 및 문제 정의 (Problem)

회색상자 퍼징 (Greybox Fuzzing) 은 시드 (seed) 입력에 무작위로 선택된 변형기 (mutators, 예: 비트 뒤집기, 바이트 삭제 등) 를 적용하여 새로운 테스트 입력을 생성하고, 코드 커버리지가 증가하는 입력을 시드 코퍼스에 추가하는 자동화 소프트웨어 테스트 도구입니다.

기존의 대표적인 퍼징 도구인 **AFL++**는 32 가지 변형기를 사용하며, 각 변형기가 선택될 확률이 고정되어 있습니다. 기존 연구들 (MOPT 등) 은 각 변형기가 독립적으로 'interesting input'(코드 커버리지를 증가시키는 입력) 을 생성할 확률을 최적화하는 데 초점을 맞추었습니다.

핵심 가설:
저자들은 변형기들이 **독립적이지 않고 상호작용 (Interaction Effect)**을 일으킬 수 있다고 가정합니다. 즉, 특정 변형기 A 가 적용된 후 변형기 B 가 적용되는 순서 (시퀀스) 가, 단순히 각 변형기의 개별 성능 합보다 더 많은 interesting input 을 생성할 수 있다는 것입니다. 기존 연구는 이 상호작용 효과를 고려하지 않고 변형기를 독립적으로 샘플링하므로, 더 효율적인 변형기 시퀀스를 놓치고 있을 가능성이 있습니다.

2. 방법론 (Methodology)

저자들은 이 가설을 검증하고 이를 활용한 새로운 퍼징 전략을 제안하기 위해 다음과 같은 단계를 거쳤습니다.

2.1. 상호작용 효과 검증 (RQ1)

• 데이터 수집: AFL++ 를 13 개의 타겟 프로그램 (FuzzBench 벤치마크) 에서 실행하여, 모든 가능한 변형기 쌍 $\langle i, j \rangle$가 생성한 interesting input 의 수를 수집했습니다.
• 모델링: 두 변형기를 독립 변수로, 생성된 interesting input 수를 종속 변수로 하는 선형 모델 (Linear Model) 을 적합시켰습니다.
  • 식: $\hat{N}(i, j) = \mu + \alpha_i + \beta_j + \gamma_{ij}$
  • 여기서 $\gamma_{ij}$는 두 변형기 간의 상호작용 항입니다.
• 분석: 분산 분석 (ANOVA) 을 통해 상호작용 항 $\gamma_{ij}$가 통계적으로 유의미한지 검정했습니다.

2.2. MuoFuzz 제안 (RQ2, RQ3)

상호작용 효과가 존재함을 확인한 후, 이를 활용하는 새로운 퍼저 MuoFuzz를 개발했습니다.

• 핵심 아이디어: 다음 변형기를 선택할 확률을 **이전 변형기에 조건부 (Conditional)**로 설정합니다. 즉, $Pr(m_n = j | m_{n-1} = i)$를 학습합니다.
• 동작 단계:
  1. 학습 단계 (Training Phase): AFL++ 의 변형 전략을 수정하여 (변형기 길이 $l=2$, 균일 무작위 샘플링), 초기 $T_{train}$시간 동안 변형기 쌍 $\langle i, j \rangle$가 생성한 interesting input 수 $N(i, j)$를 집계합니다. 이를 기반으로 조건부 확률 분포 $Pr(j|i) = \frac{N(i, j)}{\sum N(i, k)}$를 학습합니다.
  2. 가이드드 변형 단계 (Guided Mutation Phase): 학습된 확률 분포를 사용하여 마르코프 랜덤 워크 (Markov Random Walk) 방식으로 변형기 시퀀스를 생성합니다. 첫 번째 변형기는 무작위로 선택하고, 이후 변형기는 이전 변형기에 기반한 확률 분포에서 샘플링합니다.

2.3. 실험 설정

• 벤치마크: FuzzBench (13 개 프로그램) 및 MAGMA (실제 버그 8 개 프로그램).
• 비교 대상:
  • AFL++: 고정된 변형기 선택 확률 사용.
  • MOPT: 각 변형기의 선택 확률을 독립적으로 최적화 (상호작용 고려 안 함).
• 평가 지표: 24 시간 후 달성한 코드 커버리지, 발견된 버그 수, 시간 대비 커버리지 도달 속도.

3. 주요 기여 (Key Contributions)

1. 실증적 증거: AFL++ 기반 퍼징에서 변형기 쌍 간의 상호작용 효과가 interesting input 생성 수에 통계적으로 유의미한 영향을 미친다는 것을 입증했습니다.
2. 새로운 변형 전략 (MuoFuzz): 이전 변형기에 조건부인 확률 분포를 학습하고 이를 활용하여 변형기 시퀀스를 생성하는 새로운 전략을 제안하고 구현했습니다.
3. 성능 검증: 최신 퍼저 (AFL++, MOPT) 와의 비교를 통해 MuoFuzz 가 더 높은 코드 커버리지를 달성하고, 기존 퍼저가 놓친 버그를 발견했음을 실험적으로 증명했습니다.

4. 실험 결과 (Results)

4.1. 코드 커버리지 (FuzzBench)

• 성능: MuoFuzz 는 13 개 프로그램 중 10 개에서 AFL++ 보다 높은 median 커버리지를 달성했습니다. MOPT 와 비교했을 때도 8 개 프로그램에서 더 높은 성능을 보였습니다.
• 통계적 유의성: Mann-Whitney U 검정 결과, 대부분의 프로그램에서 통계적으로 유의미한 차이를 보였습니다 ($p < 0.05$).
• 속도: MuoFuzz 는 AFL++ 가 24 시간 만에 도달한 커버리지 수준에 평균 15 시간 만에 도달했습니다 (AFL++ 는 24 시간 소요). 이는 퍼징 초기에 더 효율적인 경로를 탐색함을 의미합니다.

4.2. 버그 발견 (MAGMA)

• 버그 발견: MuoFuzz 는 AFL++ 가 놓친 4 개의 버그 중 3 개를 추가로 발견했습니다.
• 고유성: MOPT 와는 총 발견 버그 수는 비슷했으나, 발견한 버그의 종류가 달랐습니다. 특히, 상호작용 효과가 약한 프로그램 (openssl 등) 에서 성능 차이가 없거나 오히려 떨어지는 경향을 보였습니다. 이는 제안된 방법이 상호작용 효과가 존재하는 경우에 효과적임을 시사합니다.

4.3. Ablation Study (하이퍼파라미터 분석)

• 컨텍스트 길이: 이전 변형기를 2 개 이상 ($p=2$) 고려하면 차원의 저주 (curse of dimensionality) 로 인해 성능이 저하되었습니다. 직전 변형기 1 개만 고려하는 것이 최적이었습니다.
• 시퀀스 길이: MAB(Multi-Armed Bandit) 알고리즘을 통해 동적으로 시퀀스 길이를 결정하는 것이 고정된 길이를 사용하는 것보다 성능이 좋았습니다.
• 첫 번째 변형기: 첫 변형기를 가중치 (성능 기반) 로 선택하는 것보다 무작위 선택이 전체적인 탐색 (Exploration) 을 증가시켜 더 좋은 결과를 낳았습니다.

5. 의의 및 결론 (Significance)

• 패러다임 전환: 기존 퍼징 연구가 개별 변형기의 최적화에 집중했다면, 본 논문은 변형기 간의 시퀀스적 상호작용이 퍼징 효율성에 결정적임을 밝혔습니다.
• 기술적 유사성: 제안된 방법은 자연어 처리의 **N-gram 언어 모델 (Bigram)**과 유사합니다. 이전 토큰 (변형기) 을 기반으로 다음 토큰의 확률을 학습하는 방식입니다.
• 실용성: MuoFuzz 는 기존 AFL++ 코드를 기반으로 하므로 구현이 간단하며, 학습 단계가 퍼징 루프 내에 경량으로 통합되어 있어 오버헤드가 적습니다.
• 향후 연구 방향: 더 복잡한 언어 모델 (RNN, Transformer) 을 적용하거나, 변형 위치 (position) 에 대한 상호작용까지 고려하는 연구로 확장할 수 있음을 제시했습니다.

결론적으로, MuoFuzz 는 변형기 간의 상호작용 효과를 학습하고 활용함으로써, 기존 퍼징 도구보다 더 빠르고 효과적으로 소프트웨어의 취약점을 발견할 수 있음을 입증했습니다.