7 CONFIGURATION UPDATING

CONFUPDATE 함수의 기본 내용

CONFUPDATE (set of Configuration(C)를 수정하는 함수)는 black-box fuzzer와 grey-box,white-box를 구분짓는 핵심적인 함수다.

CONFUPDATE는 fuzzing을 실행하면서 얻은 실행 정보와 configuration을 이용해서 set of Configuration(C)을 수정하는 함수로, 가장 간단한 구조로는 수정되지 않은 set of Configuration(C)를 반환한다.

• 즉 가장 기본적인 구조로는 파라미터로 받은 Configuration set(C)를 그대로 반환한다

black-box fuzzer와 그 외의 fuzzer의 CONFUPDATE 차이점

black-box fuzzer는 bug oracle을 평가하는 것 외에 추가적으로 프로그램 내부에서 정보를 획득할수가 없다. 따라서 C를 수정할 정보가 없기 때문에 일반적으로 C를 수정하지 않고 그대로 둔다.

• bug oracle : 타겟이 되는 프로그램이 주어진 입력으로 실행할 때 특정 보안 정책을 위반하는지 판별하는 프로그램
• 즉 보안정책이 위배되었는지만 알 수 있고 프로그램 내부 어떤 지점에서 어떤 입력값에 의해 문제가 생긴건지, 어떤 문제가 생긴건지에 대한 정보를 추가적으로 알 수가 없어서 C를 수정할 근거가 없어 그대로 반환한다.

반대로 grey-box,white box fuzzer는 CONFUPDATE 함수가 더 정교하게 구현되어 있어서 새로운 fuzz configuration 을 추가하거나 대체된 구식 fuzz configuration을 제거할 수 있다는 점에서 다르다.

• 대체된 구식 fuzz configuration의 의미 : 새로운 fuzz configuration이 기존의 fuzz configuration의 결과를 포함하는 더 좋은 결과(예를 들면 커버리지)를 얻을 수 있다면 이 기존 fuzz configuration은 대체될 수 있는 구식 fuzz configuration이다.

CONFUPDATE 함수의 효과

CONFUPDATE 함수는 fuzzing iteration을 수행하면서 수집한 모든 정보를 향후 모든 fuzzing iteration에서 사용할 수 있게 해준다.

그래서 이를 이용하기 위해 white-box fuzzer는 grey-box,black-box fuzzer보다 일반적으로 test case를 적게 만들기 때문에 다양한 fuzz configuration을 갖기 위해서 test case가 새로 생길 때마다 새로운 fuzz configuration을 만들어준다.

For example, white-box fuzzers typically create a new fuzz configuration for every new test case produced, since they produce relatively few test cases compared to black- and grey-box fuzzers.

예를 들어서, white-box fuzzer는 일반적으로 black, grey box 퍼저에 비해 상대적으로 적은 수의 test case를 생성하기 때문에 새로운 test case가 생성될때마다 새로운 fuzz configuration을 생성한다

7.1 Evolutionary Seed Pool Update

진화 알고리즘(Evolutionary Algorithm, EA)은 변이, 재조합 , 선택등과 같은 생물학적 진화 메커니즘을 포함하는 휴리스틱 기반의 접근 방식이다. fuzzing의 맥락에서, EA는 새로운 개체가 발견됨에 따라 fuzzing 캠페인의 과정에서 진화되는 유망한 개체(seed)의 seed 풀을 유지한다.

fuzzing의 맥락에서 진화 알고리즘은 fuzzing 캠페인을 진행하면서 더 좋은 결과를 가질 것으로 예상되는 유망한 seed의 pool을 유지하는 것을 의미한다. 많은 grey-box fuzzer에서 이 개념을 사용하고 있다.

진화 알고리즘에서 가장 중요한 과정은 fuzzing CONFUPDATE 단계에서 새로운 configuration을 set of Configuration에 추가하는 과정이다. 대부분의 진화 알고리즘 기반의 fuzzer들은 test case를 통해 새로운 node나 branch coverage가 발견되면 seed pool에 추가하는 방식을 사용한다.

• 이 방식을 node와 branch coverage를 기반으로 한 fitness function을 사용한다 라고 말한다.

EA의 가장 중요한 과정은 새로운 configuration을 set of configuration C에 추가하는 것이다. 이 과정은 퍼징의 CONFUPDATE 단계에서 진행한다. 대부분의 EA 기반 퍼저는 새로운 node 나 branch coverage가 test case에 의해 발견되면 seed pool에 추가하는 방식으로 node나 branch coverage를 기반으로한 fitness function을 사용한다.

seed의 수 보다 더 많은 경로 탐색이 가능할 수 있으므로 seed pool은 현재 PUT의 탐색한 경로를 나타내기 위한 도달 가능한 모든 경로의 subselection을 의미한다.

As the number of reachable paths can be orders of magnitude larger than the number of seeds, the seed pool is intended to be a diverse subselection of all reachable paths in order to represent the current exploration of the PUT. Also note that seed pools of different size can have the same coverage (as mentioned in §3.2, p. 7).

도달가능한 경로의 수는 seed 수보다 훨씬 클 수 있으므로, seed 풀은 PUT의 현재 탐색을 나타내기위해 도달 가능한 다양한 하위선택(subselection)으로 의도된다(intended to be). 또한 3.2에서 이야기 했듯이 크기가 다른 seed 풀은 동일한 coverage를 가질 수 있다.

⇒ 시드보다 못가본 경로가 훨씬 더 많을테니, 시드는 최대한 그 경로들을 건드릴 수 있는게 좋음. 그래서 시드풀은 PUT의 현재 탐색을 나타내기위해 도달가능한 모든 경로의 다양한 경우로 의도된다??

→ seed pool은 현재 PUT의 exploration을 나타내기 위해 도달가능한 모든 경로의 subselection을 의미함.

진화 알고리즘의 성능 개선을 위한 전략 및 예시

A common strategy in EA fuzzers is to refine(정제하다, 다듬다) the fitness function so that it can detect more subtle(미묘한) and granular(섬세한? 알맹이가 든?) indicators of improvements.

진화 알고리즘을 사용하는 fuzzer들은 얼마나 성능이 더 좋아졌는지 알 수 있도록 fitness function을 수정하며 다듬는다.

예를 들어, AFL [231]은 branch가 실행되는 횟수를 기록하여 fitness function 정의를 개선한다.

몇몇 fuzzer들은 seed 집합에 violating test case를 추가한다. BFF는 이러한 특징을 crash recycling이라고 부른다.

• violating test case : 보안 정책을 위배하는 테스트 케이스

STADS는 fuzzing campaign을 통해 새로운 configuration이 얼마나 나오는지 추정하기 위해 생태학에서 영감을 받은 통계학적 프레임워크를 사용한다.

또 다른 fitness function을 다듬는 일반적인 방법은 복잡한 branch 조건을 평가할때 충족하는 조건의 비율을 측정하는 것이다.

예를 들어, LAF-INTEL 은 간단하게 multi-byte comparison을 여러 branch로 나눈다. 이렇게 해서 새로운 seed가 중간의 바이트 비교를 통과(a new seed passes an intermediate byte comparison)할때 탐지할 수 있다.

• multi-byte comparison을 single byte comparison 으로 분할하는 방법
  1. =이나 <=같은 operator는 단순하게 > 또는 < 과 ==의 체인으로 변경
  2. signed integer comparision은 single only comparision과 unsigned comparision의 체인으로 변경
  3. 64bit, 32bit, 16bit의 모든 unsigned integer comparision를 여러개의 8bit comparision 체인으로 분할
• 즉 ≥을 >와 == 으로 단계를 나누어서 branch를 만들었기 때문에 새로운 seed가 이 나눈 branch를 통과할 때 탐지할 수 있다는 의미

LibFuzzer [7], Honggfuzz [204], go-fuzz [215] 및 Steelix [138]에서 모든 비교를 instrument 하고 좀 더 진전이 있는 모든 test case를 seed 풀에 추가한다. 이러한 아이디어를 이용한 clang [119]용 독립형 instrumentation 모듈도 출시되었다.

Steelix [138]는 비교 instruction에 영향을 미치는 입력 offset을 확인하고, Angora[170]는 각 branch가 갖는 calling context 를 고려하여 AFL의 fitness 기준을 개선한다.

VUzzer(EA Fuzzer 예시)

VUzzer는 EA 기반 퍼저로 각 기본 블록의 가중치를 결정하는 사용자 정의 프로그램의 결과에 기반한 fitness 함수를 사용한다.

먼저 built-in program을 이용해서 기본블록을 normal 또는 error handling (EH)로 분류한다. normal 블록의 경우 가중치는 이 블록을 포함하고 있는 제어흐름 그래프(CFG)의 무작위 경로가 방문할 확률에 반비례 한다. (실행이 잘 안되면 안될수록 가중치 높음) 이는 VUzzer가 앞에서 언급한 무작위 경로에서 적게 실행되는 nomal 블록을 실행하게 하는 configuration을 선호하도록 한다.

EH 블록의 가중치는 음수이며, 그것의 크기는 이 configuration에 의해 실행되는 EH 블록의 수에 대한 기본 블록의 수의 비율이다.

이러한 음의 가중치는 EH 블록을 통과하면, 버그가 종종 handling 되지 않은 오류와 일치하기 때문에 취약점을 건드릴 가능성이 낮다는 가설을 기반으로 오류 처리(EH) 블록의 실행을 억제하는 데 사용된다.

• EH 블록 통과시, 버그 = 핸들링 되지 않은 오류 , 즉 취약점을 건드릴 가능성이 낮다.

7.2 Maintaining a Minset

새로운 fuzzing configuration을 만들다보면 너무 많은 configurations을 만들 수 있는 위험이 있다. 이러한 위험을 줄이기 위해서 일반적으로 test case의 minset 또는 minimal set을 유지하며 coverage를 극대화하는 방법을 쓴다.

• Minsetting은 PREPROCESS 할때도 사용된다. (3.2 참고)

일부 fuzzer는 configuration 업데이트에 특화된 minset을 유지하는 변형 방식을 사용한다. 예를 들어, Cyberdyne [92]처럼 minset에 없는 구성을 완전히 제거하기보다, AFL [231]은 minset configuration 을 유리한 것으로 표시하기 위해 도태 절차(culling procedure)를 사용한다. 이렇게 표시한 좋은 fuzzing configuration은 SCHEDULE 함수 때에 선택할 가능성이 높아진다. AFL의 제작자는 “이는 queue cycling 속도와 test case diversity 사이의 합리적인 균형을 제공한다”고 언급한다.