[논문 리뷰] The Art, Science, and Engineering of Fuzzing: A Survey
원문 : https://arxiv.org/abs/1812.00140
[목차]
4. Scheduling
퍼징에서 scheduling은 다음 fuzz iteration을 위해 fuzz configuration을 선택하는 것을 의미한다. 전술했듯이, 각 configuration의 내용은 퍼저의 유형에 따라 다르다.
간단한 퍼저의 경우 스케줄링이 단순하다. 예를 들어, zzuf의 기본 모드는 하나의 configuration만 허용한다. BFF나 AFLFast과 같이 더 복잡한(:advanced) 퍼저의 경우, 기발한 스케줄링 알고리즘이 해당 퍼저의 성공과 직결되는 아주 중요한 요소로 작용했다.
이 섹션에서 블랙 박스 퍼징과 그레이 박스 퍼징의 스케줄링 알고리즘만을 다룬다. 화이트 박스 퍼징의 스케줄링은 symbolic executor에 복잡한 설정이 필요해서 생략한다. 궁금한 독자는 다음 연구를 참고하라: <Billions and billions of constraints: Whitebox fuzz testing in production>.
4.1 The Fuzz Configuration Scheduling (FCS) Problem
스케줄링의 목표는 configuration에 대해 현재 사용 가능한 정보를 분석하고 가장 유리한 결과(예: unique한 버그의 수가 많아지거나, 생성된 입력 set을 통해 커버리지 최대화하기 등)로 이어질 가능성이 있는 정보를 선택하는 것이다.
기본적으로 모든 스케줄링 알고리즘은 탐색(:exploration)과 익스플로잇(exploitation)의 trade off 문제에 직면하게 된다.
- exploration
향후 결정을 위해 각 configuration에 대한 더 정확한 정보 수집에 시간을 할애하는 것이 합리적이다.
- exploration
현재 가장 유리한 결과물로 이어질 것 같은 configuration을 퍼징하는 것이 합리적이다.
Woo의 연구 <Scheduling black-box mutational fuzzing>에서 이러한 고질적인 문제를 Fuzz Configuration Scheduling (FCS) Problem라고 정의했다.
Algorithm 1에서 제시한 model fuzzer에서 SCHEDULE은 현재 fuzz configuration set인 , 현재 시간인 , time out인 세 가지를 기반으로 다음 configuration을 선택한다. 이 configuration은 다음 fuzz iteration을 위해 쓰인다.
SCHEDULE은 오직 의사결정(:decision-making)에 관한 동작일 뿐이다. 이 결정의 기반이 되는 정보는 PREPROCESS와 CONFUPDATE에서 획득되며, 이 지식으로 가 업데이트(:augment)된다.
4.2 Black-box FCS Algorithms
블랙 박스 환경에서 FCS 알고리즘이 사용할 수 있는 정보는 fuzz configuration의 결과(크래시와 버그의 수, 소요 시간) 뿐이다.
Householder and Foote의 연구 <Probability-based parameter selection for black-box fuzz testing>에서 변이 기반 블랙 박스 퍼저 CERT BFF에서 이런 정보가 어떻게 활용될 수 있는지 처음 제시되었다. 해당 연구에서 더 높은 성공률()을 가진 configuration이 더 유리하다고 가정했다. 실제로 BFF에서 uniform-sampling scheduling 알고리즘을 적용하여, ffmpeg 프로그램을 5백만 번 실행했다. 결과적으로 unique crash가 85% 증가한 것을 관찰할 수 있었으며, 이를 통해 FCS algorithm이 향상되면 잠재적으로 이점이 있을 수 있다는 것을 입증했다.
얼마 지나지 않아 Woo의 연구 <Scheduling black-box mutational fuzzing>에서 이 아이디어를 여러 측면에서 개선하였다.
- 일련의 Bernoulli trial에서 Weighted Coupon Collector’s Problem with Unknown Weights (WCCP/UW)라는 문제로 변이 기반 블랙 박스 퍼징의 수학적인 모델을 개선했다. 전자(Bernoulli trials)는 각 configuration이 고정적인 최종 성공 확률을 가지고 있다고 가정하고 시간이 지남에 따라 학습한다. 후자(WCCP/UW)는 upper-bound를 명시적으로 유지한다(as it decays).
- WCCP/UW 모델이 multi-armed bandit(MAB) 문제에 대한 알고리즘을 investigate하도록 유도했으며, 이는 decision science에서 exploration vs exploitation 문제에 대처하기 위한 전형적인 방식(:formalism)이다. 이를 위해 아직 decayed된 것으로 알려지지 않은 configuration을 정확하게 exploit하는 MAB 알고리즘을 구상할 수 있었다.
- 그들은 퍼징을 더 빠르게 할 수 있는 configuration이 더 많은 unique bug를 발견하거나 향후 성공 확률에 대한 upperbound를 더 빠르게 감소시킬 수 있다고 보았다. 이를 통해 configuration에 사용한 시간으로 성공 확률을 정규화하여, 더 빠른 configuration이 유리하도록 했다.
- BFF에서 fuzz iterations(BFF에서 epoch에 해당) per configuration selection이었던 기존의 fuzz run의 orchestration을 fixed amount of time per selection으로 변경했다. 덕분에 BFF는 느린 configuration에 시간 낭비하지 않을 수 있게 되었다.
결과적으로 기존 BFF와 비교했을 때 동일한 시간 동안 unique 버그를 1.5배 더 많이 발견할 수 있다는 것을 보여주었다.
4.3 Grey-box FCS Algorithms
그레이 박스 환경에서, FCS 알고리즘은 더 많은 정보들(예: 커버리지 획득 정보 등)을 사용해 configuration을 선택할 수 있다.
AFL은 이 분야의 선두주자인데, evolutionary algorithm(EA)을 사용한다. 간단히 말하면, EA는 fitness의 가치가 있는 configuration set을 유지한다. EA는 fit한(이하 더 효과적인으로 해석) configuration을 선택하고 나중에 새로운 configuration이 될 수 있는 자식을 생성하기 위해 mutation이나 재조합과 같은 유전적 변형(:genetic transformation)을 적용한다. 이는 이렇게 만들어진 configuration이 효과적일 가능성이 높을 것이라는 가정을 기반으로 한다.
EA의 관점에서 FCS를 이해하려면 다음 세 가지를 잘 정의해야 한다.
(i) configuration을 효과적으로 만드는 요소
(ii) configuration 선택 방법
(iii) 선택된 configuration가 사용되는 방법
AFL에서는 control-flow edge를 실행하는 configuration 중, 가장 빠르고 가장 작은 configuration 입력을 포함하는 configuration을 가장 효과적(AFL에서는 favorite라는 용어를 사용)이라고 판단한다. AFL은 config 큐를 원형 큐(circular queue) 형태로 유지하면서 다음으로 효과적인 configuration을 선택하고, 일정한 횟수만큼 실행한다.
빠른 configuration이 효과적이라고 판단하는 것은 블랙 박스 환경의 FCS와 유사하다.
최근에 AFLFast는 위 세 가지 측면에서 AFL을 개선했다.
1. AFLFast는 입력이 "favorite"이 되도록 두 가지 기준을 추가했다.
(i) control flow edge를 실행하는 configuration 중에서 AFLFast는 가장 적게 선택되는 configuration을 선호한다. 이는 edge를 실행하는 configuration들 사이에서 cycling하는 효과가 있었고, 덕분에 exploration 관점에서 유리하다.
(ii) (i)이 동일한 경우 가장 적게 실행된 경로를 탐색할 수 있는 configuration을 더 선호한다. 이는 아직 커버하지 못한 영역을 탐색할 수 있게 해주는 희귀한 경로를 더 많이 찾게 해주는 효과가 있다.
2. AFLFast round-robin 방식 대신 우선순위에 따라 효과적인 다음 configuration을 선택하는 방식을 사용한다.
특히 효과적인 configuration은 덜 선택되거나 더 희귀한 경로를 탐색할 수 있는 경우 우선순위가 높다. 첫 번째 개선사항(위에서 추가한 두 가지 기준)과 유사하게, 효과적인 configuration들 간의 탐색을 늘리고 희귀한 경로를 많이 탐색할 수 있는 효과가 있다.
3. AFLFast는 power schedule을 기반으로 선택된 configuration을 다양한 횟수만큼 퍼징한다.
AFLFast의 FAST power schedule은 "energy"라는 작은 값에서 시작하는데, 이는 configuration들 간의 초기 탐색을 보장하고 충분한 탐색을 위해 limit까지 지수 단위로 증가한다. 또한 동일한 경로를 탐색하는 입력의 수를 energy를 기반으로 정규화하여 더 적게 퍼징되는 configuration을 탐색할 수 있도록 한다.
AFLFast의 이러한 변화들은 효과적이었다. 24시간 동안 퍼징한 결과, AFL이 발견하지 못한 버그를 3개 더 발견했으며, 두 퍼저 모두 발견한 6개의 버그는 평균 7배 더 빠르게 발견했다.
AFLGo는 특정 프로그램의 위치를 타겟으로 우선순위 속성(:attribution)을 수정하여 AFLFast를 확장했다. Hawkeye는 시드 스케줄링과 입력 생성 단계에서 정적 분석을 활용하여 directed fuzzing을 개선했다. FairFuzz는 시드와 rare branch의 각 쌍에 대해 mutation mask를 적용하여 campaign이 rare branch를 실행하도록 했다. QTEP은 정적 분석을 통해 바이너리의 어떤 부분이 더 "결함(:faulty)"인지 추론하고, 이를 포함하는 configuration에서 우선순위를 부여하는 방식을 사용한다.
Uploaded by Notion2Tistory v1.1.0