4 SCHEDULING

퍼징에서 스케줄링은 다음 퍼징 반복을 위한 fuzz configuration을 선택하는 것을 의미한다. § 2.1에서 설명한 바와 같이, 각 fuzz configuration의 내용은 퍼저의 유형에 따라 달라진다.

간단한 퍼저의 경우 스케줄링이 간단할 수 있다. 예를 들어, 기본 모드의 zzuf은 하나의 fuzz configuration만 허용(allows only one configuration)하기 때문에 스케줄링 결정을 내릴 필요가 없다.

그러나 BFF 및 AFLFast와 같은 좀 더 발전된 퍼저의 경우 혁신적인 스케줄링 알고리즘을 사용한다.

이 섹션에서는 black-box 및 grey-box 퍼징에 대한 스케줄링 알고리즘에 대해서만 논의한다. 화이트박스 퍼징에서 스케줄링을 하려면 symbolic executors를 위해 특별히 복잡한 설정(a complex setup unique to symbolic executors)이 필요하다. 관심있으면 다른 자료들을 찾아보길바란다.

4.1 The Fuzz Configuration Scheduling (FCS) Problem

scheduling의 목표는 configurations에 대한 현재 사용 가능한 정보를 분석하고 가장 유리한 결과를 초래할 가능성이 있는 것을 선택하는 것이다.

예를 들어, 가장 많은 수의 고유한 버그를 찾거나 생성된 입력 집합(the set of generated inputs)에 의해 coverage를 최대화하는 것이다.

⇒ scheduling의 목표 : unique bug 찾기 / coverage 넓히기

기본적으로, 모든 스케줄링 알고리즘은 탐색(exploration) vs 익스플로잇(exploitation) 문제에 직면한다.

미래의 의사 결정을 위해 각 configuration에 대해 보다 정확한 정보를 수집하는데에 집중하거나 (exploration), 현재에 지금 당장 더 유리한 결과를 가져올 것으로 생각되는 configuration을 이용해서 fuzzing을 하는 곳(exploitation)에 시간을 할애할 수 있다.

⇒ exploration : 새로운 취약점이 발생할 법한 곳을 찾는 것

⇒ exploitation : 여기서 취약점이 발생하는 것은 거의 사실인데, 실제로 취약점을 유발하는 인풋을 찾는 것

우리의 모델 퍼저(알고리즘 1)에서 SCHEDULE 함수는 (i) 현재 fuzz configurations C, (ii) 현재 시간 경과 (telapsed) 및 (iii) 총 시간 예산(최대 사용가능한 시간) (tlimit)에 기초하여 다음 configuration을 선택한다. 그런 다음 이 configuration은 다음 퍼지 반복에 사용된다.

SCHEDULE은 의사 결정(decision-making)에만 관한 것이다. 이 결정의 기초가 되는 정보는 PREPROCESS와 CONFUPDATE에 의해 얻을 수 있으며, 이를 이용해서 fuzz configurations C를 업데이트한다. (augment C with this knowledge)

⇒ PREPROCESS와 CONFUPDATE가 끝나면 SCHEDULE의 의사결정을 위한 정보를 건내받을 수 있고, 이 정보들로 C 를 업데이트할 수 있다.

4.2 Black-box FCS Algorithms

블랙박스의 경우, FCS 알고리즘이 사용할 수 있는 유일한 정보는 configuration의 퍼징 결과이다.

즉, 지금까지 발견된 충돌과 버그의 수와 그에 소요된 시간뿐이다. Householder와 Foote는 그러한 정보가 CERT BFF black-box mutational fuzzer에서 어떻게 활용될 수 있는지를 최초로 연구했다.

그들은 더 높은 observed success rate (#bugs / #runs : #는 횟수)을 가진 configuration이 선호되어야 한다고 가정했다.

실제로, BFF에서 uniform-sampling scheduling 알고리듬을 교체한 후, 그들은 500만 번의 ffmpeg 실행에서 85% 더 많은 고유 충돌을 관찰하여 더 발전된 FCS 알고리즘의 이점을 보여주었다.

이후 이를 이용해서 다양한 연구를 진행했고 발전시켰다.

발전시킨 연구의 예시를 살펴보면

먼저, black-box mutational fuzzing의 수학적 모델을 a sequence of Bernoulli trials에서 Weighted Coupon Collector’s Problem with Unknown Weights (WCCP/UW)로 개선했다.

전자(a sequence of Bernoulli trials)는 각 configuration이 고정된 최종 성공 확률을 가지고 있다고 가정하고 시간이 지남에 따라 이를 학습하는 반면, 후자(Weighted Coupon Collector’s Problem with Unknown Weights (WCCP/UW))는 쇠퇴할수록 이 확률에 대한 상한(upper bound)을 명시적으로 유지한다.

⇒ 쇠퇴할 수록 확률에 대한 상한을 명시적으로 유지?? ⇒ 아무리 성공확률이 높아도 이 정도라는 정보를 기억하고 있는 것. 각 configuration이 안 좋아질때마다(as it decays) 아무리 성공확률은 높아도 이정도! 라는걸

둘째, WCCP/UW모델(Woo et al)은 자연스럽게 다중 multi-armed bandit (MAB) problems에 대한 알고리즘을 조사하도록 유도하는데, 이는 의사결정 과학(decision science)에서 the exploration vs. exploitation conflict에 대처하기 위한 대중적인 형식주의(popular formalism)이다.

끝으로 그들은 아직 쇠퇴하지 않은 것(have decayed yet)으로 알려진 구성(exploit configurations)을 정확하게 이용할 수 있는 MAB 알고리즘을 설계할 수 있었다.

다른 조건이 모두 동일할 때 퍼징 속도가 빠른 configuration이 unique bug를 더 많이 수집하고, 미래의 성공률에 대한 upper-bound를 줄이는데(decrease the upperbound on its future success probability) 좋다는 사실을 제시했다.

이것은 정해진 시간동안의 configuration의 성공 확률을 정규화하도록 영감을 주었고(inspired), 따라서 더 빠른 실행속도를 가진 configuration이 더 선호되도록 했다.

넷째, 그들은 BFF에서 퍼지 런의 오케스트레이션(the orchestration of fuzz runs)을 선택된 configuration당 고정된 퍼징 반복 횟수("BFF 용어에서 epochs") (a fixed number of fuzz iterations per configuration selection (“epochs” in BFF parlance)) 에서 configuration 선택당 고정된 시간(a fixed amount of time per selection.)으로 변경했다.

⇒ 한 번의 configuration selection 마다 고정된 iteration 횟수를 실행하는 대신 제한된 시간 동안 가능한 만큼만 iteration을 실행하도록 BFF를 바꿔 느린 configuration에 시간 낭비를 방지함

⇒ 무튼 더 좋아짐. ‘무조건 퍼지 반복 몇번은 끝내고 다음 구성하자’를 ‘이 시간동안 되는만큼 다 실행해’로 바꿈.

이 변경으로 BFF는 더 이상 다음 번째 configuration을 다시 선택하기 이전에 느린 configuration에서 더 많은 시간을 보내도록 강요받지 않는다. (no longer forced to spend more time)

⇒ 무조건 몇번 실행 해야하는게 아니라 특정 시간동안만 실행이니까.

위의 내용을 종합하여, 기존 BFF와 동일한 시간을 사용하여 발견된 고유 버그(unique bugs)수에 비해 1.5배 증가했다는 연구결과가 있다.

4.3 Grey-box FCS Algorithms

grey-box setting에서 FCS 알고리즘은 각 구성에 대한 보다 풍부한 정보 (예: the coverage attained when fuzzing a configuration)를 사용하도록 선택할 수 있다.

AFL은 이 범주의 선구자이며 진화 알고리즘(Evolutionary Algorithm : EA)을 기반으로 한다.

EA는 configuration 집합(population of configurations)을 유지하며, 각 구성에는 "fitness"라는 값이 있다.

EA는 적합한 형태의 configuration을 선택하고 이를 돌연변이 및 재조합(mutation and recombination)과 같은 유전자 변형(genetic transformations)에 적용하여 자손을 생산하며, 이는 나중에 새로운 configuration이 될 수 있다.

⇒ 이렇게 생성된 구성이 더 fit할 가능성이 높다는 가설이 있다.

EA의 맥락에서 FCS를 이해하려면 (i) configuration을 fit하게 만드는 것, (ii) configuration을 선택하는 방법, (iii) 선택한 configuration을 사용하는 방법을 정의해야한다.

높은 수준의 근사치로(As a high-level approximation), AFL은 control-flow edge를 실행하는 configuration 중 가장 빠르고 가장 작은 입력을 포함하는 것("AFL 용어로 favorite")을 적합하다고 간주한다.

높은 수준의 근사치로, control flow edge를 실행하는 구성 중에서 AFL은 가장 빠르고 가장 작은 입력을 포함하는 구성을 적합하다고 간주한다(AFL 용어로 'fitness').

AFL은 configuration 원형 큐를 유지하며, 큐에서 적합한 다음 configuration을 선택(돌아가며 선택)한다.

한번 configuration이 선택되면 AFL은 기본적으로 일정한 수(constant number)의 실행을 위해 해당 configuration을 퍼징한다. FCS의 관점에서 볼 때 블랙박스 세팅에서 빠른 configuration은 두루두루 선호 된다는걸 잊지말자.(preference for fast configurations is common for the black-box setting)

최근에 AFLFast by Bohohme et al.은 아래의 세 가지 측면에서 AFL을 개선했다.

첫째, AFLFast는 입력이 "favorite"이 되기 위한 두 가지 우선적인 기준을 추가한다:

(i) control flow edge를 사용하는 구성 중에서 AFLFast는 가장 덜 선택된 configuration을 선호한다.

이것은 이 edge를 실행하는 configurations들 사이에서 순환(cycling)하는 효과를 가지고 있어서 탐색(exploration)을 증가시킨다.

(ii) (i)에 동점이 있을 경우, AFLFast는 가장 적게 실행된(that has been exercised least) 경로를 선호한다.

⇒ AFLFast는 입력이 "favorite"이 되기 위한 두 가지 우선적인 기준을 추가함

1. 가장 덜 선택된 configuration
2. 가장 적게 실행된 경로

이것은 희귀한 경로(rare paths)의 실행을 증가시키는 효과가 있으며, 이는 관찰되지 않은 행동을 더 많이 발견할 수 있다.

둘째, AFLFast는 AFL의 라운드 로빈 선택(round-robin selection)을 포기하고 우선 순위에 따라 다음 fit configuration을 선택한다.

특히, fit configuration은 자주 선택되지 않거나, 자주 실행되지 않은 경로를 실행할때, 다른 configuration보다 더 높은 우선 순위를 갖는다.

첫 번째 변경과 유사하게, fit configurations 사이의 exploration과 희귀 경로의 실행을 증가시키는 효과를 가진다.

⇒ the exploration among fit configurations & the exercising of rare paths 증가

셋째, AFLFast는 선택한 구성을 power schedule에 따라 가변 횟수로 퍼징한다.

AFLFast의 FAST power schedule은 configuration 간의 초기 탐색(exploration)을 보장하기 위해 작은 "에너지(energy)" 값으로 시작한다. 그리고 FAST power schedule은 기하급수적으로 증가하여 충분한 exploitation을 신속하게 보장한다.

또한 동일한 경로를 실행하는 생성된 입력의 수에 따라 에너지를 정규화하여(normalizes the energy) 퍼징 빈도가 낮은 configuration(less-frequently fuzzed configurations)의 탐색을 촉진한다.

⇒ 잘 안들여본 부분들 집중해서 퍼징 한다는 것 같은 맥락.

AFL은 24시간 평가에서 AFL이 발견하지 못한 3개의 버그를 발견했으며, AFL이 발견한 6개의 다른 버그에서 AFL보다 평균 7배 더 빨랐다.

이외에도 다양하게 scheduling 방식을 선택하는 퍼저들이 있다.

[다양하게 scheduling 방식을 선택하는 퍼저]

1. ALGo는 **특정 프로그램 위치**를 대상으로 우선 순위 속성을 수정하여 AFLFast를 확장한다.
2.  Hawkeeye는 시드 스케줄링 및 입력 생성에서 정적 분석을 활용하여 directed fuzzing을 추가로 개선한다.

3.   FairFuzz는 seed와 희귀한 분기(rare branches) 각 쌍에 대해 mutation mask를 사용하여 희귀한 분기(rare branches)를 실행하는 campaign을 안내한다.
4.  QTEP은 정적 분석을 사용하여 바이너리에서 어느 부분이 더 ‘faulty’한지 추론하고 이를 포함하는 configuration의 우선 순위를 매긴다.