[PAPER REVIEW] The Bandit’s States: Modeling State Selection for Stateful Network Fuzzing as Multi-armed Bandit Problem (Euro S&P'23)

BACKGROUND

Fuzzing

• 무작위 입력을 생성하여 SUT(System Under Test)로 전송하는 테스트 기법
• 입력에 대한 SUT의 동작을 분석하여 이상 징후, 잠재적 버그 및 취약성 식별

네트워크 퍼저

• 네트워크 패킷을 랜덤으로 변형하여 네트워크 인터페이스의 예기치 않은 동작과 취약점 유도
• 네트워크 프로토콜에서는 퍼저가 상태를 인식해야 심층적 취약점을 찾을 수 있음

Multi-armed Bandit(MAB)

• 비문맥 강화학습 에이전트가 여러 행동 중 반복적으로 exploration 대 exploitation 문제를 고려하여 선택해야 하는 문제
• 에이전트는 보상을 극대화하는 것이 목표

 

MOTIVATION

네트워크 프로토콜에서 다음에 테스트할 상태를 결정하는 문제가 있음

• 퍼저는 알려진 상태와 테스트되지 않은 상태 사이 균형 유지 필요

→ exploration과 exploitation 딜레마를 multi-armed bandit을 사용하여 모델링하는 방식 제안

→ 이러한 MAB 문제로 상태 선택 문제를 모델링하는 방식이 퍼징 성능 향상에 효과적인지를 분석하는 것이 목표

 

DESIGN

state selection 문제를 MAB 문제로 모델링 → 기존에 제안된 알고리즘 활용

1. stochastic multi-armed bandit
2. adversarial multi-armed bandit
   • 커버리지가 한 번만 발견될 수 있으므로 보상 확률이 시간이 지남에 따라 감소하는 점 고려

 

IMPLEMENTATION

AFL++ 기반으로 EPS, EXP, UCB, UCBT 알고리즘을 적용한 4개의 MAB 퍼저 구현

 

EVALUATION

RQ1. MAB 문제로 모델링하는 접근 방식이 퍼저의 성능에 영향을 주는가?

• 4개의 grey-box MAB 퍼저 구현 결과, 유의미한 성능 향상을 보이지 않음

RQ2. MAB 기반으로 상태를 선택하는 퍼저가 기존의 최신 퍼저인 AFLNet과 비교했을 때 어떠한지?

• baseline fuzzer로 AFLNet을 비교한 결과, AFLNet이 모든 MAB 퍼저보다 커버리지 측면에서 더 성능이 좋음

 

CONCLUSION

CONCLUSION

• 상태 선택 알고리즘이 퍼저에 중요한 영향을 미치는지에 대한 질문에 기여 → 통계적으로 상태 선택 알고리즘에서 MAB 문제의 적용은 유의미한 영향을 미치지 않음
• Future work: MAB 사용한 모델링을 심층적으로 분석하여 하이퍼파라미터를 튜닝하여 퍼저의 성능에 미치는 영향을 이해

CONTRIBUTION

• 네트워크 퍼징에서 상태 선택 문제를 MAB 문제로 모델링하는 새로운 접근방식 제안
• MAB 모델의 접근 방식 통해 퍼징 성능 향상시키기 위한 실험 수행