[Paper] RandSet: 퍼징 시드 스케줄링을 위한 무작위 코퍼스 축소

Source: arXiv - 2602.22729v1

위에 제공된 내용만으로는 번역할 텍스트가 없습니다. 번역을 원하는 본문을 알려주시면 도와드리겠습니다.

개요

이 논문은 RandSet을 소개한다. 이는 가벼운 무작위화 기법으로, 퍼저의 시드 코퍼스를 축소하면서도 대상 프로그램에 제공되는 입력의 다양성을 유지(그리고 심지어 향상)시킨다. 코퍼스 축소를 집합‑커버 문제로 간주하고 해결 과정에 무작위성을 도입함으로써, RandSet은 코퍼스를 원래 크기의 몇 퍼센트 수준으로 줄여, 현대 퍼저를 방해하는 “seed explosion” 병목 현상을 크게 완화한다.

Source: …

주요 기여

• 무작위 집합‑커버 공식화 – 코퍼스 축소를 집합‑커버 문제로 정의하고, 작지만 다양성 있는 시드 하위 집합을 제공하는 빠른 확률적 알고리즘으로 해결합니다.
• 저오버헤드 통합 – RandSet을 세 가지 주류 퍼저(AFL++, LibAFL, Centipede)에 구현했으며, 실행 시간 오버헤드가 1–4 %에 불과해 고빈도 시드 스케줄링에 실용적입니다.
• 실증적 검증 – 독립 실행형 프로그램, FuzzBench 벤치마크, 그리고 Magma 버그 탐지 스위트에서 RandSet이 코퍼스 크기를 원본의 **≈4–6 %**로 줄이면서 평균 +16 % 커버리지를 제공하고, 최신 기술보다 최대 7개의 실제 버그를 추가로 발견함을 입증했습니다.
• 다양성‑우선 설계 – 축소 단계에서 무작위성을 도입하면 cull_queue, AFL‑cmin, MinSet과 같은 결정론적 축소기보다 보다 다양하고 풍부한 시드 선택이 자연스럽게 이루어짐을 보여줍니다.

방법론

1. Feature extraction – 각 시드는 실행될 때 트리거되는 특징(예: 코드 분기, 입력 토큰)의 집합으로 표현됩니다.
2. Set‑cover problem – 목표는 전체 코퍼스에서 관찰된 모든 특징을 포괄하는 최소한의 시드 하위 집합을 선택하는 것입니다.
3. Randomized greedy algorithm – NP‑hard인 set‑cover 문제를 정확히 풀지 않고, RandSet은 “가장 가치 있는” 후보(가장 많은 미탐색 특징을 커버하는 시드) 풀에서 무작위로 시드를 반복적으로 선택합니다. 이 무작위성은:
   • 각 실행마다 다른 축소된 하위 집합을 보장하여 다양성을 유지합니다.
   • O(|C| · log |F|) 시간에 실행됩니다 (|C| = 코퍼스 크기, |F| = 특징 수). 이는 대상 프로그램을 실행하는 비용에 비해 무시할 수 있을 정도입니다.
4. Scheduling – 퍼저의 일반적인 시드 선택 루프가 축소된 하위 집합으로 리다이렉트됩니다. 하위 집합이 매우 작기 때문에 스케줄러는 원래의 폭발적인 비용 없이도 우선순위 큐, 에너지 할당 등 더 풍부한 휴리스틱을 적용할 수 있습니다.

결과 및 발견

• 다양성: RandSet의 축소된 집합은 결정론적 리듀서가 여러 시드를 몇 개의 “대표”로 압축하는 경우와 달리, 보다 넓은 범위의 고유 특징을 포함합니다.
• 속도: 무작위 탐욕 단계는 수만 개의 시드가 있는 코퍼스에서도 밀리초 단위로 완료되며, 반복마다 축소가 가능하도록 합니다(즉, 퍼저가 RandSet을 자주 재실행할 수 있음).
• 호환성: 기본 퍼징 엔진에 대한 변경이 전혀 필요하지 않았으며, RandSet은 기존 시드‑큐 관리 API에 그대로 연결됩니다.

실용적인 시사점

• Scalable fuzzing pipelines – 팀은 지속적으로 커지는 코퍼라로 인한 메모리 및 CPU 압박 없이 퍼저를 몇 주 동안 실행할 수 있습니다.
• Better resource allocation – 작고 고품질의 시드 풀을 통해 개발자는 보다 공격적인 변이 전략, 시드당 더 긴 실행 시간, 혹은 더 많은 코어를 활용한 병렬 퍼징을 적용할 수 있습니다.
• Improved CI integration – 지속적 통합 퍼징 작업은 종종 시간 제한에 걸리는데, RandSet의 낮은 오버헤드 덕분에 CI당 더 많은 커버리지를 얻고 버그를 더 빨리 발견할 수 있습니다.
• Cross‑fuzzer adoption – RandSet은 AFL++, LibAFL, Centipede와 함께 작동하므로, 이미 이러한 도구를 사용하는 프로젝트는 단일 라이브러리 임포트와 약간의 설정 변경만으로 도입할 수 있습니다.

제한 사항 및 향후 작업

• Feature definition dependency – RandSet의 효과는 특징 추출(분기 커버리지, 토큰화 등)의 품질에 달려 있습니다. 부실하거나 지나치게 거친 특징은 최적이 아닌 부분 집합을 초래할 수 있습니다.
• Randomness variance – 무작위성은 다양성을 높이지만 재현성에서 비결정성을 도입합니다; 필요할 경우 결정적 실행을 위해 시드를 고정하라고 저자들이 제안합니다.
• Dynamic program behavior – 동작이 시간에 따라 크게 변하는 프로그램(예: 상태를 유지하는 서버)의 경우 정적 특징 집합이 오래될 수 있으며, 향후 연구에서는 적응형 특징 업데이트를 탐구할 수 있습니다.
• Extending beyond coverage – 현재 공식은 커버리지 특징에 초점을 맞추고 있으므로, 충돌 유발 가능성, 입력 크기 다양성 등 다른 메트릭을 포함하도록 RandSet을 확장하는 것이 열린 연구 과제입니다.

저자

• Yuchong Xie
• Kaikai Zhang
• Yu Liu
• Rundong Yang
• Ping Chen
• Shuai Wang
• Dongdong She

논문 정보

• arXiv ID: 2602.22729v1
• 분류: cs.SE, cs.CR
• 출판일: 2026년 2월 26일
• PDF: PDF 다운로드