두 번째 논문은 Angora : Efficient Fuzzing by Principled Search 이다.
고민할 거리도 많았고, 직접 손으로 그려보기도 하면서 읽은 논문이었던만큼 흥미로웠다.
Angora도 찾아보니까 토끼의 한 종류인 것 같다. 논문에서 AFL 이랑 비교하는 부분이 많이 나오는데, 제목도 혹시 노린건가 싶다 (?)
Angora
: "The main goal of Angora is to increase branch coverage by solving path constraints without symbolic execution."
Angora는 mutation-based fuzzer이다.
Angora의 가장 큰 목적은 위에 논문에서 발췌한 문장에서 나와있듯, path constraints를 symbolic execution 없이 효율적으로 풀어 궁극적으로 branch coverage를 높이는 데에 있다.
어떻게 symbolic execution 없이 path constraints를 효율적으로 풀 수 있을까?
이에 대한 답으로 Angora는 다음과 같은 기술들을 소개한다.
1) context-sensitive branch count
2) scalable byte-level taint tracking
3) search based on gradient descent
4) type and shape inference
5) input length exploration
조금 더 각 기술들에 대한 부연 설명을 하자면,
2) scalable byte-level taint tracking : input의 어떤 bytes들이 해당 조건문으로 들어가는지 파악하고, 이 bytes들만 mutate 시킨다. (input 전체를 mutate 하는 것이 아니라)
3) search based on gradient descent : input의 어떤 bytes들을 mutate할 지 찾았다면, 어떻게 mutate할 지 찾아야 한다.
path constraint를 어떤 black box function의 제약으로 보고, "경사하강법"을 사용해서 constraint를 푼다. 딥러닝에서 나오는 경사하강법 맞다. 작년 여름에 딥러닝을 공부하길 잘했다는 생각이 들었던 부분.
4) type and shape inference : 경사하강법을 적용할 때, black box function의 인자들에 대해서 미분값을 구할텐데, 이 때 인자들의 type과 shape에 대한 정보가 필요하다. 항상 네 개의 consecutive 한 byte가 같이 해당 분기에서 사용된다면, 이 네 개의 bytes들을 각각 하나의 인자로 보는 것이 아니라, 하나의 integer로 생각할 수 있을 것이다.
하나씩 파헤쳐 보자.
context-sensitive branch count
AFL 과의 비교로 시작되는 섹션이다.
저번에 올린 AFL 포스팅을 보고 오면 좋을 것 같다.
AFL은 각각의 run에 대해서 각각의 branch가 몇번 실행되었는지 path trace table에 기록해둔다.
이 때, table의 인덱스는 h((l_prev,l_cur))의 값이다. h는 해시 함수이다.
또한, AFL은 different runs에 대해서 global branch coverage table을 가지고 있다.
AFL에서 new internal state 란,
1. 새로운 branch를 실행시켰을 때 (path trace table에는 있는데, global table에는 없는)
2. 해당 branch가 이전과는 다른 실행 횟수를 가졌을 때 (다른 buckets에 들어갈 때)
이러한 AFL의 문제는 무엇일까?
바로 branch coverage를 계산할 때, call context를 고려하지 않았다는 것이다.
그래서 Angora는 "context-sensitive branch coverage"를 coverage metric으로 사용한다.
Angora는 branch를 (l_prev, l_cur, context) 튜플로 정의한다.
이 때, l_prev와 l_cur은 AFL 때와 동일하게 블럭들의 ID라고 생각하면 되고, context는 h(stack)으로 나타내어지는 값인데, h는 해시 함수이고, stack은 call stack의 상태를 의미한다.
하지만, branch를 이렇게 표현하면 unique한 branch가 너무 많아질 수 있다는 문제가 있다. 특히 깊은 재귀 함수에 빠졌을 때 말이다.
이를 해결하기 위해서 hash function으로 xor 연산을 사용한다. stack에 있는 모든 call sites들의 ID를 xor한 값을 반환하는데, f 라는 함수가 계속해서 자기 자신을 부르는 경우, 많아야 2개의 unique한 branch가 생성된다. (xor 자기 자신과 하면 0이 만들어지고, 또 한번 xor 하면 자기 자신이 나오게 된다.) call site는 말그대로 함수를 부르는 곳이고, Angora가 프로그램 instrument를 할 때, call site 별로 랜덤한 ID를 부여한다.
다음과 같은 코드가 있을 때, input으로 100과 010으로 주어졌을 때 상황을 각각 고려해보자.
context-insensitive 한 AFL의 경우 두 상황 모두 같은 branch를 커버하는 것으로 판단해 line 5의 새로운 internal state를 무시하게 된다. (100 일 때, line 4와 line 10 실행 / 010 일 때 똑같이 line 10과 line 4 실행, 하지만 전에 똑같이 실행된 것으로 판단해서 이 input이 new internal state를 trigger할 수 없는 input으로 판단) 즉, AFL은 call context를 하나도 고려하지 않고, 결과적으로 어떤 branch가 cover 되었는지 table count를 보고 판단해버린다.
이제 Angora의 예시를 보자. 똑같은 100과 010이 주어진 상황이다.
첫번째 run, 100 입력에 대해서는 branch (3,4,[19]) 와 (3,10,[21])이 실행된다. (여기서 수는 라인 넘버이다.)
두번째 run, 010 입력에 대해서는 branch (3,10,[19]) 과 (3,4,[21])이 실행된다. => 두번째 run은 첫번째 run가 다른 것으로 판단해서 new internal state이고, 이는 input[2]를 1로 바꿨을 때 crash site로 연결될 수 있다.
scalable byte-level taint tracking
앞서 초반부에 언급했듯이, 입력의 어떤 부분이 조건문에서 사용되는지 파악하는 것이 중요하다.
하지만, 보통 byte-level taint tracking은 비싸다.
그렇지만 Angora의 key insight는 program 의 대부분의 run에 대해서 taint tracking이 불필요하다는 것이다.
먼저, 입력에 대해서 taint tracking을 돌릴 때, 입력의 어떤 byte offsets들이 해당 조건 분기문으로 들어가는지 기록할 수 있고, 그 다음에 해당 byte offsets를 mutate하게 되면, taint tracking을 그 이후에는 하지 않고 그냥 run할 수 있다.
Angora는 프로그램의 각각의 변수에 taint label t라는 것을 달아놓는데, 이는 그 변수에 sink할 수 있는 입력의 byte offsets들을 뜻한다. 보통 naive 한 구현에서는 이를 bit vector로 구현하고, 입력의 i번째 byte가 i번째 bit에 대응한다고 보면 된다.
하지만, 이러한 구현은 입력의 사이즈가 커짐에 따라서 bit vector가 linear하게 증가해서 엄청 큰 입력에 대해서는 쓰기 힘들다. 하지만 큰 입력은 어떠한 프로그램에 대해서 버그를 찾는 데에 꼭 필요한 요소이므로 이 자료구조는 적합하지 않다.
그래서 Angora에서 소개하는 자료구조는 두 개의 component가 있는데,
1. bit vectors에서 labels 를 매핑하는 이진 트리
2. labels에서 bit vectors를 매핑하는 table
이다. 이 자료구조에서 taint label은 index로 나타내어 진다. 이 부분을 읽으면서 이해한 구조를 그림으로 그려보았다.
위에 그림과 코멘트를 자세히 읽으면, 논문을 이해하는 데에 도움이 될 것이다.
우선, 이진 트리에 대해서 간략히 부연 설명하자면, 이진 트리의 리프 노드들은 bit vectors를 뜻한다. 루트 노드로부터 왼쪽으로 가면 0, 오른쪽으로 가면 1로 해서 bit vectors를 만들어 나갈 수 있고, 마지막 리프 노드에서 해당 bit vectors를 알아낼 수 있다.(루트 노드까지 타고올라가면서 bit vectors를 재구성할 수 있다.) 이 노드들은 각각 taint label, 즉 2번 테이블에서의 인덱스를 저장하고 있다.
테이블에서는 taint label을 인덱스로 하고, entry로 해당 bit vectors의 노드의 주소 값을 가지고 있다. (이진 트리의 노드를 가리키는 포인터이다.)
이렇게 상호 참조가 가능한 두 가지 자료구조를 통해서 space complexity를 O(l log l)로 줄일 수 있다. (l이 bit vectors의 개수라고 했을 때) 자세한 설명은 그림을 참조하면 좋겠다.
Search algorithm based on gradient descent
Angora 의 재밌는 특징 중 하나가 path constraint를 SMT Solver를 사용해 푸는 것이 아니라 머신러닝에서 사용되는 경사하강법(gradient descent)를 사용하여 해당 조건을 만족하는 값을 구한다는 것이다.
실제 딥러닝에서는 가중치에 대한 비용 함수에서 경사하강법을 통해 비용을 줄이는 최적의 가중치 값을 찾아나간다.
하지만, 가중치 학습에 있어서 경사하강법의 한계 중 하나는 local minimum에 빠질 수 있다는 점이다. 전체로 보았을 때는 최적이 아니지만, 최적에 도달했다고 판단할 수 있는 것이다.
이러한 문제는 fuzzing에서 고려할 필요가 없는 것이, 우리는 path constraint를 푸는 값들만 찾으면 되는 것이지 굳이 그 값들이 최적의 값일 필요는 없다.
한 가지 아쉬운 점은 black-box function f(x)에 대해서 analytic form으로 미분된 식을 표현할 수 없다는 것이다.
그래서 결국 수치 미분을 통해 gradient 값을 근사할 수 밖에 없는데, 수치 미분을 하게 되면 (f(x + δv i) - f(x)) / δ 를 계산해야 한다.
함수 값을 f(x)에서 한 번, f(x + δv i)에서 한 번 계산해야 해서 프로그램을 두 번 돌리는 방식으로 계산한다.
하지만, x + δv i 에 대해서 프로그램을 돌릴 때 우리가 현재 보고 있는 path constraint에 도달하기 전에 다른 branch로 빠지게 될 수 있어서, 이럴 경우에는 δ 를 -1로 바꾸어서 다시 한번 돌리고, 이래도 안 되면 아예 해당 direction으로 이동하지 않도록 derivative를 0으로 만들어버린다.
진짜 중요한 문제는 여기서 x가 해당 조건문에서의 조건에 흘러 들어온 input의 특정 byte offsets 이라는 것인데, type 정보와 shape 정보가 없으면 효과적인 경사하강법을 적용할 수 없다.
if ( i * i < 10 && j < 1 ) 라는 조건문을 만족하는 i와 j를 경사하강을 통해 찾는다면, x 벡터가 i, j 를 나타내게 되면 효과적으로 해당 조건을 만족하는 i와 j 값을 찾을텐데, i 와 j 가 입력의 어딘가에 각각 4 bytes 부분을 사용하고 있다는 것을 고려하지 않고, 이 4bytes들을 각각 따로 1개의 byte 씩 x 벡터의 원소로 보게 되면, 각각의 byte들에 대해 f(x + δv i) 를 계산하게 되고, 이는 효과적으로 값을 찾아내는 것을 방해한다.
결국 효과적인 경사하강법을 위해서는 (1) 입력의 어떤 bytes들이 프로그램에서 하나의 value로 사용되고 있는지를 알아야 하고(shape), (2) 해당 값의 type이 무엇인지 알아야 한다(type).
Shape and type inference
Angora는 이를 dynamic taint analysis를 통해 해결한다.
입력의 어느 부분이 i와 j variable에 들어가는지 파악하는 것이다.
taint analysis에서 어떤 instruction이 input bytes의 특정 sequence를 어떤 variable에 읽어들이고 있고, 그 sequence 사이즈가 primitive type size, 즉 (1, 2, 4, 8) 과 같다면 이러한 sequence에 태그를 달아 같이 사용된다고 표시한다. (byte, word, dword, qword)
만약 어떤 충돌이 발생하면, 가장 작은 size를 선택한다.
Input length exploration
마지막으로 Angora는 효과적으로 input의 length를 언제 mutate할지 판단한다.
입력 길이를 늘림으로써 새로운 branch 탐색이 가능하다고 판단할 때에만 길이를 늘린다.
read-like function의 return 값이 조건문에서 사용되어 해당 조건이 만족되지 않는다면, Angora는 입력 길이를 늘여 read-like function이 요청한 만큼의 입력을 더 받아들일 수 있도록 길이를 조정한다.
Reference:
https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8418633
※ Any feedbacks and corrections are welcome. Feel free to comment down below.
