Fuzz Testing 을 어떻게 평가해야 믿을 만한 결과를 도출할 수 있을지? 에 대해 다루는 논문이다.
이번 포스팅에서는 논문을 섹션 바이 섹션으로 분석하기보다도 결론 정도를 간단히 정리해보고자 한다. 어떻게 fuzzer를 evaluate 해야 하는지에 대한 어느정도의 방향성 말이다.
앞으로 내가 읽을 많은 Fuzzer 관련 논문들의 evaluation 섹션을 좀 더 비판적으로 읽을 수 있을 수 있는 시각을 제공해주었다는 점에서 인상 깊었던 논문이다.
이 논문은 현재까지 많은 Fuzzing 관련 논문들이 사용한 evaluation 기법들이 실제로는 틀린 결과로 이어질 수 있다는 점을 지적하면서, 어떠한 방법으로 Fuzzer를 평가해야 좀 더 신뢰 가능한 결과로 이어질 수 있는지 그 methodology를 제시한다.
Fuzzers are primarily evaluated experimentally.
논문에서 핵심을 관통하는 말인 것 같다.
어떻게 하면 경험적으로 새롭게 소개된 fuzzer가 현존하는 fuzzer보다 좋다는 것을 밝힐 수 있을까?
- 현재 fuzzer A와 비교할 baseline fuzzer B 를 선택하는 것
- fuzzer를 돌릴 sample target program을 선정하는 것(the benchmark suite)
- 선택한 benchmark suite에 fuzzer A와 B를 돌렸을 때, 어떤 기준으로 각각의 성능을 평가할 것인지
- configuration parameters 정하기 (the seed file, timeout of a fuzzing run, etc)
fuzz testing algorithm을 평가하기 위해서는 위와 같은 과정이 꼭 필요할 것이다.
이 논문에서는 32개의 fuzzing 관련 최근 논문들에 대해서 그들의 experimental methodologies 들을 분석했고, 다음과 같은 사항들을 발견했다.
- 많은 논문들이 여러번의 실행을 하지 않았다는 것과 여러번의 실행을 했더라도 실행마다 달라지는 성능을 통계적으로 설명하지 않았다는 것.
- 많은 논문들이 fuzzer의 성능을 the number of distinct bugs found 로 평가하지 않고, AFL coverage profile 이나 stack hashes와 같은 heristics를 사용하여 "unique crashes"를 세어서 평가했다는 점.
- 많은 논문들이 short timeouts를 걸어뒀다는 것.
- 많은 논문들이 seed choices의 영향에 대해서 제대로 고려하지 않았다는 점.
- target programs의 선택에 있어 많은 논문들이 차이를 보였다는 점 => 성능을 비교하기 어렵다.
결론적으로 이 논문에서 말하고자 하는 fuzzer에 대한 좋은 evaluation 이란 무엇이냐면
- 여러번의 실험을 통해서 fuzzer에 대한 통계적인 검증을 하는 것.
- 다양한 benchmark target programs 에 대해 테스트해보는 것.
- distinct bugs 를 성능 평가의 기준으로 삼는 것.
- empty seed를 포함해 다양한 seed choices를 고려하는 것.
- timeouts는 적어도 24시간으로 설정하고, 그 이하로 설정할 경우, 그 정당성에 대한 설명이 필요하고, 실행 시간동안 성능을 plot화 하는 것.
이다.
이 중 distinct bugs에 대해서 좀 더 알아보자.
What is a distinct bug?
이 논문에서 말하는 distinct bug 란 무엇일까?
결국에는 개발자들이 crashing input을 사용해서 자기들의 프로그램을 디버그하고, 고쳐서 더이상 crash가 나지 않게 할 것이다.
이런 bug fix는 해당 input에 대해서만 국한된 것이 아니라, 보통 일반적으로 그 crashing input과 유사한 입력들에 대해서도 일반적으로 적용될 것이다. 예를 들어서, buffer overrun을 막기 위해서 input length 체크를 하는 bug fix를 했다고 하면, 그 입력에 대해서만 패치가 된 것이 아니라, buffer overrun을 일으킬만한 길이의 모든 입력에 대해서도 성공적으로 적용되었을 것이다.
그렇기 때문에, 어떤 프로그램 p가 input I가 입력으로 주어졌을 때 crash가 났는데, bug fix 이후에 더이상 crash가 발견되지 않으면, 해당 Input I를 고쳐진 bug와 연관지을 수 있다. 또한, 어떤 프로그램이 두 개의 input I1, I2 이 주어지면 crash가 나고, 두 개의 입력 모두 bug fix 이후 더이상 crash를 일으키지 않는다면, 두 input I1, I2는 모두 "같은 버그"로 연관지을 수 있을 것이다.
이렇게 같은 버그로 묶어진 input은 서로 다른 것으로 보지 않는다는 것이다. 결국에는 distinct bugs 의 개수를 가지고 fuzzer의 성능을 판단하는 것이 더 정확하다고 말하고 있다.
기존의 논문들은 보통 ground-truth(distinct bugs)가 없을 때, AFL Coverage Profile 을 통해서 unique crashes를 가려내거나, stack hashes를 통해서 unique crashes를 가려내는데, 이 두 방법은 모두 적절치 못하다고 설명하고 있다.
먼저, AFL Coverage Profile 이다.
AFL과 AFLfast를 AFL Coverage Profile을 기반으로 성능을 측정한 것이다. y-axis가 the total number of unique crash-inducing inputs이다.
단순히 unique crashing inputs를 찾아낸 개수만 봐서는 AFLfast가 AFL을 압도하지만, 실질적으로 distinct bugs를 기준으로보면 거의 AFL과 AFLfast가 동일하다. (각 막대 그래프 바로 위에 숫자가 적혀있는데, 이 것이 distinct bugs들의 개수이다.)
따라서, the number of crashing inputs를 기준으로 fuzzer의 성능을 판단하는 것은 적절하지 못한 결론으로 이어질 수 있다는 것이다.
두번째는 stack hashes이다.
stack-hashes는 crash가 발생했을 때의 call context를 보고, 이를 해싱하여 unique crashes를 구분하는 것이다.
이 때, 몇 개의 stack frames를 볼 지에 따라서, unique crashes로 분류하는 개수가 달라진다.
위 예시는 f와 g 모두 format() 함수를 부르는데, format() 함수 내에서 인자로 받아온 string을 corrupt 시켜서 후에 output() 함수에서 crash가 발생하는 구조이다.
결국에는
1. f() -> format() -> prepare() -> output()
2. g() -> format() -> prepare() -> output()
이 순서대로 함수 호출이 될 것이다.
하지만, 우리가 볼 스택 프레임의 개수를 3개로 설정한다면, f와 g는 서로 다른 경로가 분명함에도 format(), prepare(), output()을 가지고 해싱을 하기 때문에 두 입력은 동일하게 분류될 것이다.
이러한 stack hashes를 ground truth인 distinct bugs와 비교해봤을 때, AFL Coverage Profile을 바탕으로 측정한 것보다는 bugs를 overcount 하는 것이 덜했지만(still overcount), 해시가 unique하지 않다는 문제가 있었다.
위 표를 보자.
총 591개의 hashes가 9개의 bugs에 매치된다. 여전히 distinct bugs에 비해 overcount 하는 것을 볼 수 있다.
하지만, 더 큰 문제는, 예를 들어, Bug B에 대해서 362개의 해시 중 343개만 Bug B에만 연관된 input에 match되고, 나머지 19개는 다른 crashing input에 대해서도 매칭이 되었다는 것이다.
이는 stack hashes를 이용해서 inputs들을 de-duplicate할 때 문제가 일어날 수 있다는 것을 뜻하는데, 그 이유는 이러한 false matches들을 discard 해버리기 때문이다.
많은 fuzzer에 대한 논문이 잘못된 결과로 이어질 수 있는 평가 방법을 사용한다는 점이 놀라웠고, 앞으로는 fuzzer에 관한 논문을 읽을 때 조금 더 비판적인 시각을 가지고, 세심히 읽어야 겠다는 생각을 하게 되었다. (특히 evaluation 섹션, 정말로 이 fuzzer가 비교 대상인 fuzzer보다 성능이 좋은 것이 맞는지?)
Reference:
https://arxiv.org/pdf/1808.09700.pdf
※ Any feedbacks and corrections are welcome. Feel free to comment down below.
