[4장] Fuzzing: Art, Science, and Engineering 번역

4 SCHEDULING

In fuzzing, scheduling means selecting a fuzz configuration for the next fuzz iteration. As we have explained in §2.1, the content of each configuration depends on the type of the fuzzer.

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

 

For simple fuzzers, scheduling can be straightforward—for example, zzuf [103] in its default mode allows only one configuration and thus there is simply no decision to make.

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

 

But for more advanced fuzzers such as BFF [49] and AFLFast [37], a major factor to their success lies in their innovative scheduling algorithms.

그러나 BFF[49] 및 AFLFast[37]와 같은 더 발전된 퍼저의 경우, 성공의 주요 요인은 혁신적인 스케줄링 알고리즘에 있다.

 

In this section, we will discuss scheduling algorithms for black- and greybox fuzzing only; scheduling in white-box fuzzing requires a complex setup unique to symbolic executors and we refer the reader to another source [38].

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

4.1 The Fuzz Configuration Scheduling (FCS) Problem

The goal of scheduling is to analyze the currently-available information about the configurations and pick one that is likely to lead to the most favorable outcome,

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

 

e.g., finding the most number of unique bugs, or maximizing the coverage attained by the set of generated inputs.

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

⇒ unique bug / coverage

 

Fundamentally, every scheduling algorithm confronts the same exploration vs. exploitation conflict—time can either be spent on gathering more accurate information on each configuration to inform future decisions (explore), or on fuzzing the configurations that are currently believed to lead to more favorable outcomes (exploit).

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

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

 

In our model fuzzer (Algorithm 1), the function SC H E D U L E selects the next configuration based on (i) the current set of fuzz configurations C, (ii) the current time telapsed, and (iii) the total time budget tlimit. This configuration is then used for the next fuzz iteration.

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

 

Notice that SC H E D U L E is only about decision-making. The information on which this decision is based is acquired by PR E P R O C E S S and CO N FUP D A T E, which augment C with this knowledge.

SCHEDULE은 의사 결정에만 관한 것이다. 이 결정의 기초가 되는 정보는 PREPROCESS와 CONFUPDATE에 의해 획득되며, 이 지식으로 C를 증가시킨다.

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

 

4.2 Black-box FCS Algorithms

In the black-box setting, the only information an FCS algorithm can use is the fuzz outcomes of a configuration—the number of crashes and bugs found with it and the amount of time spent on it so far. Householder and Foote [107] were the first to study how such information can be leveraged in the CERT BFF black-box mutational fuzzer [49].

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

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

 

They postulated that a configuration with a higher observed success rate (#bugs / #runs) should be preferred.

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

 

Indeed, after replacing the uniform-sampling scheduling algorithm in BFF, they observed 85% more unique crashes over 5 million runs of ffmpeg, demonstrating the potential benefit of more advanced FCS algorithms.

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

 

Shortly after, the above idea was improved on multiple fronts by Woo et al. [225].

얼마 지나지 않아, 위 아이디어는 Woo et al등 에 의해 여러 연구의 최전선에서 개선되었다.

⇒ 다른 사람들이 이걸이용해서 다양한 연구를 진행했고 발전시켰다.

 

First, they refined the mathematical model of black-box mutational fuzzing from a sequence of Bernoulli trials [107] to the Weighted Coupon Collector’s Problem with Unknown Weights (WCCP/UW).

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

 

Whereas the former assumes each configuration has a fixed eventual success probability and learns it over time, the latter explicitly maintains an upper-bound on this probability as it decays.

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

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

 

Second, the WCCP/UW model naturally leads Woo et al. to investigate algorithms for multi-armed bandit (MAB) problems, which is a popular formalism to cope with the exploration vs. exploitation conflict in decision science [34].

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

 

To this end, they were able to design MAB algorithms to accurately exploit configurations that are not known to have decayed yet.

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

 

Third, they observed that, all else being equal, a configuration that is faster to fuzz allows a fuzzer to either collect more unique bugs with it, or decrease the upperbound on its future success probability more rapidly.

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

 

This inspired them to normalize the success probability of a configuration by the time that has been spent on it, thus causing a faster configuration to be more preferable.

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

 

Fourth, they changed the orchestration of fuzz runs in BFF from a fixed number of fuzz iterations per configuration selection (“epochs” in BFF parlance) to a fixed amount of time per selection.

넷째, 그들은 BFF에서 퍼지 런의 오케스트레이션을 configuration 선택당 고정된 퍼지 반복 횟수("BFF 용어에서 epochs")에서 configuration 선택당 고정된 시간으로 변경했다.

a fixed number of fuzz iterations per configuration selection (“epochs” in BFF parlance) ⇒ a fixed amount of time per selection 로 수정했다.

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

⇒ 무튼 더 좋아짐.

⇒ 무조건 퍼지 반복 몇번은 끝내고 다음 구성하자 ⇒ 이 시간동안 되는만큼 다 실행해

 

With this change, BFF is no longer forced to spend more time in a slow configuration before it can re-select.

이 변경으로 BFF는 더 이상 configuration re-select 전에 느린 configuration에서 더 많은 시간을 보내도록 강요받지 않는다.

⇒ 무조건 몇번 실행해야하는거 X이니까.

 

By combining the above, the evaluation [225] showed a 1.5× increase in the number of unique bugs found using the same amount of time as the existing BFF.

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

 

4.3 Grey-box FCS Algorithms

In the grey-box setting, an FCS algorithm can choose to use a richer set of information about each configuration, e.g., the coverage attained when fuzzing a configuration.

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

 

AFL [231] is the forerunner in this category and it is based on an evolutionary algorithm (EA).

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

 

Intuitively, an EA maintains a population of configurations, each with some value of “fitness”.

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

 

An EA selects fit configurations and applies them to genetic transformations such as mutation and recombination to produce offspring, which may later become new configurations.

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

 

The hypothesis is that these produced configurations are more likely to be fit.

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

 

To understand FCS in the context of an EA, we need to define (i) what makes a configuration fit, (ii) how configurations are selected, and (iii) how a selected configuration is used.

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

 

As a high-level approximation, among the configurations that exercise a control-flow edge, AFL considers the one that contains the fastest and smallest input to be fit (“favorite” in AFL parlance).

AFL은 control-flow edge를 실행하는 configuration 중 fit할 수 있는 가장 빠르고 가장 작은 입력을 포함하는 구성("AFL 용어에서 favorite")을 높은 수준의 근사치로 간주한다.

 

AFL maintains a queue of configurations, from which it selects the next fit configuration essentially as if the queue is circular.

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

 

Once a configuration is selected, AFL fuzzes it for essentially a constant number of runs. From the perspective of FCS, notice that the preference for fast configurations is common for the black-box setting [225].

한번 configuration이 선택되면 AFL은 기본적으로 일정한 수(constant number)의 실행을 위해 해당 configuration을 퍼징한다. FCS의 관점에서 볼 때 빠른 configuration에 대한 선호는 블랙박스 설정[225]에 공통적으로 적용된다는걸 잊지말자.

 

Recently, AFLFast by B ¨ohme et al. [37] has improved upon AFL in each of the three aspects above.

최근에 AFLFast by Bohohme et al. [37]은 위의 세 가지 측면에서 AFL을 개선했다.

 

First, AFLFast adds two overriding criteria for an input to become a “favorite”:

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

 

(i) Among the configurations that exercise a control flow edge, AFLFast favors the one that has been chosen least.

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

 

This has the effect of cycling among configurations that exercise this edge, thus increasing exploration.

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

 

(ii) When there is a tie in (i), AFLFast favors the one that exercises a path that has been exercised least.

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

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

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

This has the effect of increasing the exercise of rare paths, which may uncover more unobserved behavior.

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

 

Second, AFLFast forgoes the round-robin selection in AFL and instead selects the next fit configuration based on a priority.

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

 

In particular, a fit configuration has a higher priority than another if it has been chosen less often or, when tied, if it exercises a path that has been exercised less often.

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

 

In the same spirit as the first change, this has the effect of increasing the exploration among fit configurations and the exercising of rare paths.

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

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

 

Third, AFLFast fuzzes a selected configuration a variable number of times as determined by a power schedule.

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

 

The FAST power schedule in AFLFast starts with a small “energy” value to ensure initial exploration among configurations and increases exponentially up to a limit to quickly ensure sufficient exploitation. (영어 문장해석...)

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

 

In addition, it also normalizes the energy by the number of generated inputs that exercise the same path, thus promoting explorations of less-frequently fuzzed configurations.

또한 동일한 경로를 실행하는 생성된 입력의 수에 따라 에너지를 정규화하여 퍼지 빈도가 낮은 configuration의 탐색을 촉진한다.

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

 

The overall effect of these changes is very significant—in a 24-hour evaluation, B ¨ohme et al. observed AFLFast discovered 3 bugs that AFL did not, and was on average 7× faster than AFL on 6 other bugs that were discovered by both.

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

 

AFLGo [36] extends AFLFast by modifying its priority attribution in order to target specific program locations.

ALGo[36]는 특정 프로그램 위치를 대상으로 우선 순위 속성을 수정하여 AFLFast를 확장한다.

 

Hawkeye [53] further improves directed fuzzing by leveraging a static analysis in its seed scheduling and input generation.

Hawkeeye[53]는 시드 스케줄링 및 입력 생성에서 정적 분석을 활용하여 directed fuzzing을 추가로 개선한다.

 

FairFuzz [136] guides the campaign to exercise rare branches by employing a mutation mask for each pair of a seed and a rare branch.

FairFuzz[136]는 seed와 희귀한 분기의 각 쌍에 대해 mutation mask를 사용하여 희귀한 분기를 실행하는 campaign을 안내한다.

 

QTEP [218] uses static analysis to infer which part of the binary is more ‘faulty’ and prioritize configurations that cover them

QTEP [218]은 정적 분석을 사용하여 바이너리에서 어느 부분이 더 ‘faulty’한지 추론하고 이를 포함하는 configuration의 우선 순위를 매긴다.