Cornelius Aschermann, Sergej Schumilo, Ali Abbasi, and Thorsten Holz 2020 IEEE Symposium on Security and Privacy (SP)
개요
기존 Fuzzer들은 Complex한 State machine들을 정확하게 추적하지 못하였다. IJON은 개발자가 소스코드에 Annotation을 할수 있도록 하여서, 보다 정확한 State guidance fuzzing이 가능하도록 하였다.
Motivation
Fuzzer들이 점차 발전하고 있지만, Fuzzing에서 사용하는 Guidance인 코드 커버리지는 Fuzzer입장에서는 불충분한 정보이다. 새로운 State탐색이 최종 Bug를 위한 Detection에 어느정도 기여하고 있는지 Fuzzer는 알 수 없기 때문이다 (본 연구뒤에 자동으로 이러한 정보를 습득하기 위한 연구들이 나옴). 예를 들어서 같은 코드 커버리지를 가지더라도, 값이 다를 경우 다른 결과가 나올 수 있지만, 커버리지만 사용하면 커버리지를 넘는 결과를 도출할 수 없다.
Background
American Fuzzy Lop을 예를 들어서 어떻게 상용 Fuzzer들이 Code coverage를 측정하는지 설명하였다. AFL과 같은 퍼저들은 Control flow graph에서 Edge에 얼만큼 많이 도달하였는지를 Binary instrumentation이나 Intel PT와 같은 하드웨어를 통해서 측정한다. 엣지는 source basic block id ([math]\displaystyle{ id_s }[/math])와 destination block id ([math]\displaystyle{ id_t }[/math])의 랜덤한 값으로(보통 점프 주소를 해시값떠서) 지정된다. 특정한 엣지를 나타내기 위해서는 엣지의 count수를 저장하고 있는 bitmap으로 점프해야 하는데, bitmap의 index는 [math]\displaystyle{ (id_s \times 2) \oplus id_t }[/math]로 나타내진다.
최종적으로 특정한 Input에 대한 결과는 shared map에 저장되는데, 각각의 테스트에서 얼만큼 edge에 도달하였는지의 수를 저장한다. shared map의 각 bit는 0-255의 숫자를 저장하며, 보통 1,2,3,4,8,16,...2^n의 케이스를 분리하여서 Coverage를 계산한다. 퍼저는 동시에 global bitmap을 지니고 있는데, 전체 fuzzing에서 도달한 모든 edge들의 count수를 저장하고 있다. AFL은 전에 볼 수 없었던 수의 iteration이 특정 edge에서 발생하면, 그 Input을 Interesting test case로 간주, Corpus에 저장한다.
Design
- State Exploration
State Exploration을 위해선 다음 3가지를 고려해야 한다.
- Known Relevant State Values: 명확히 small subset of state만 흥미로운 케이스여서 그에따라서 측정해야 하는 경우, 즉 변수(State)가 특정 패턴으로 바뀔 것으로 예측되는 부분이다. 논문의 나오는 예시는 미로 게임을 들었다. 게임에서 플레리어의 x축과 y축 좌표는 명시적으로 Code-coverage에 추가하여야 미로를 효율적으로 탐색할 수 있다.
- Known State Changes: Known Relevant State Values를 추적할 수는 없지만, State를 변경시킬 것이라고 예측되는 코드의 부분이다. 예를 들어서 switch-case문으로 특정 변수의 값에 따라서, 다음 State를 결정하는 분기를 예시로 들수 있다. 기존 퍼저와 같은 경우에는 랜덤하게 작동하기 떄문에 임의의 순서로 Switch-case를 통과하지만, Annotation을 통하여 흥미로운 순서로 State를 변화시키도록 할 수 있다.
- Missing Intermediate State: State가 변화하더라도, 혹은 State를 변화시키는 코드가 있는 부분도 흥미로운 부분이 아닐 경우이다 (~KRSV and ~KSC). 예를 들어서 해쉬값을 뜨는 함수같은 경우에는, 그 Return값도 무의미하고 Hash를 뜨는 과정도 Code coverage에 있어서는 무의미하다.
- Feedback Machine
- 개발자가 Annotatio을 통하여 Fuzzer의 작동에 영향을 미칠 수 있도록 하였다. 개발자는 프로그램 코드를 분석하여 쉽게 Annotation을 추가할 수 있도록 디자인 하였다. Annotation은 Source code에 추가하는 Small code patch로 디자인 하였다.
- IJON-Enable / IJON-Disable: IJON-ENABLE ~ IJON-Disable부분에서는 Code coverage측정이 포함되지 않도록 하였다. 이 명령어는 Missing Intermeidate State에 해당하는 부분을 Code coverage측정에서 제외하기 위해서 주로 사용되었다.
- IJON-INC / IJON-SET: IJON-INC나 IJON-SET은 bitmap의 특정 entry를 조작할 수 있도록 하였다. 이를 통하여, 새로운 값이 새로운 code coverage로 간주되도록 하였다. 즉 변수의 변화를 새로운 edge로 추가하는 것과 같은 역활을 하도록 한다. 이 Annotation은 위의 3가지 경우에 모두 적용할 수 있다.
- IJON-State: 가상의 State를 추가하는 것으로 IJON-State값이 변경되면 새로운 Edge의 변경은 무조건 새로운 Coverage로 간주된다. IJON-State는 주로 Known State Change를 해결하기 위해서 사용된다. 위의 예시에서 Message를 IJON-State로 넣으면, 새로운 메시지에 대해서 새로운 Coverage로 간주하도록 하여, 모든 메시지 조합에 대한 Code-coverage를 효율적으로 계산할 수 있다.
- IJON-Max: State variable의 Maximum variable로 향하도록 Coverage를 조절할 수 있다. 이를 통하여 Hill climbing-based black box optimizer로 Code coverage를 조절할 수 있다. 논문에서는 예시로 Super mario게임을 들며, 게임의 x좌표가 최대가 되도록 유도하는 것이 Goal에 도달 할 수 있는 방향임을 제시하고, Coverage를 그쪽으로 유도해야 함을 설명하였다.
Conclusion
IJON은 코드 커버리지가 Fuzzing의 전부가 아님을 다시한번 보이고, 그 해결방안으로 Practical한 Solution을 제시하였다. 비록, 개발자의 수동작업에 의존한 작업을 요구하지만, 코드 커버리지를 넘는 그 무었인가가 필요함을 보인것은 중요한 Contribution포인트가 된다.