[PAPER REVIEW] CarpetFuzz: Automatic Program Option Constraint Extraction from Documentation for Fuzzing (USENIX SEC'23)

BACKGROUND

Coverage-guided fuzzing

• 성공적인 취약점 발견 기술 중 하나
• 입력을 변형해가면서 코드 커버리지를 증가시켜서 소프트웨어 내 잠재적인 보안 위반을 트리거함
• 기존 연구는 퍼징 과정에서 커버리지를 증가시키기 위한 최적화 기술(seed selection, seed schedule, mutation, feedback)에 집중

 

MOTIVATION

• 최신 퍼저는 고정된 프로그램 옵션 조합을 사용해서만 트리거 할 수 있는 탐색되지 않은 코드가 있음
  • 기존 퍼저는 특정 command-line 옵션을 사용하여 프로그램을 퍼징하지 않았기 때문
  • command-line 옵션은 프로그램의 실행을 변형할 수 있음을 알려주는 것이기 때문에, 입력을 변경하는 것이 아닌 특정 옵션으로만 도달 가능한 코드가 있음 → 하지만 제보된 취약점은 적은 옵션만이 사용됨 예) Libtiff의 2014년부터 2020년까지 103개의 CVE는 20개의 서로 다른 옵션이 사용되었고, 이는 전체 옵션 중 9.8%뿐임. 나머지 옵션에 의존적인 코드는 탐색되지 않았음을 의미
  • 옵션의 조합이 방대하기 때문에 iterate하는 것은 불가능 예) ImageMagick은 242개의 옵션이 있고, 가능한 조합은 7.1 x $10^{72}$
• 옵션 조합 변형의 한계
  • 단순히 옵션을 변형하는 것은 제약조건을 고려하지 않기 때문에 많은 유효하지 않은 조합을 만들어 냄
  • 예) openssl-rsa에서 변형 알고리즘으로 생성된 조합의 11%만이 유효했음
• 챌린지
  • 옵션의 관계는 주로 문서에서 자연어로 기술되어있음 ⇒ 문서에서 옵션 사이 관계를 자동으로 찾는 방법필요
  • 옵션 사이 관계 식별한 후, 옵션 사이 충돌, 의존성 등 관계를 자동으로 추출하는데 어려움이 있음
    • 관계와 관련된 옵션을 자동으로 위치시키는데 어려움이 있음
    • 옵션 사이 관계는 완전 다르게 해석될 수 있음

⇒ NLP를 활용하여 자동으로 프로그램 문서에서 옵션 설명을 추출하고 옵션 관계를 분석하여 유효하지 않은 조합은 사전에 필터링하고 퍼징 시 유효한 옵션 조합만 제공

 

DESIGN

1. 프로그램 문서에서 OPTIONS 섹션을 파싱하여 모든 옵션과 옵션 관련 설명 추출
2. 머신러닝 모델 사용하여 설명에 옵션 관계가 기술되어 있는지 추론 → 이러한 관계 설명 부분은 문서 내 적기 때문(ex. tiffcp 문서에는 3.4%)
   • entropy-based uncertainty sampling과 active learning 사용하여 학습 데이터 라벨링에 휴리스틱 줄임
   • 설명에서 특징을 요약하고 NLP 사용해서 이러한 특징을 만족하는 모든 문장 조합을 찾음
3. mixing forward, backward traversal 방법 사용하여 dependency tree에서 관계와 관련된 노드를 찾음
4. polarity-based finite state machine 사용하여 concrete 관계 결정
5. 관계를 만족하지 않는 조합 필터링

 

EVALUATION

• CarpetFuzz는 문서에서 옵션 관계를 96.10% 정확도로 추출하고 recall은 88.85%
• 추출한 관계를 통해 테스트해야 할 옵션 조합을 67.91% 줄임
• AFL이 다른 퍼저가 발견하지 못한 경로를 45.97% 더 발견하는데 도움
• 20개의 유명한 프로그램에 적용 결과, 43개의 발견되지 않은 취약점 발견하고 30개 취약점에서 CVE ID 등재

 

CONCLUSION

CONCLUSION

• 프로그램 옵션의 추출하는 NLP 기반 퍼징 보조 기술
• 프로그램 문서에서 옵션과의 관계를 정확하게 추출하고 유효하지 않은 옵션 조합을 67.91% 필터링함
• CarpetFuzz는 유효한 옵션을 생성함으로써 AFL이 45.97% 더 많은 경로를 찾는데 돕고, CVE 30개 등재

CONTRIBUTION

• 새로운 기술 제안: 처음으로 NLP를 사용하여 문서에서 프로그램 옵션에 대한 제약조건을 자동으로 추출하고 식별하는 새로운 기술 제안
• 20개의 리얼월드 오픈소스 프로그램으로 평가한 결과, 추출 정확도 88.85%이며 30개의 CVE 등재
• 오픈소스: https://github.com/waugustus/CarpetFuzz

---

여러 프로그램을 퍼저로 테스트할 때 프로그램에서 여러 옵션을 조합했을 때 유효하지 않은 적이 많고, 어떤 옵션 조합을 사용해야 프로그램의 깊은 경로를 탐색할 수 있을지 생각했어서, 유효하지 않은 옵션은 필터링하고 유효한 옵션만을 퍼저에 제공하는 기술의 아이디어가 획기적이고 유용하다고 생각했다.