hybrid fuzzing

Fuzzing Methodology

hybrid fuzzing

라온화이트햇 핵심연구팀 원요한

hybrid fuzzing

이 문서는 hybrid fuzzing을 사용한 퍼저 논문중 하나인 링크의 내용을 요약 및 hybrid fuzzing에 대한 장점/문제점에 대해 작성하였습니다.

Fuzzing

Fuzzing 이란, 비정상적인 입력을 받아 타겟 프로그램의 입력으로 만들어 소프트웨어 버그를 찾는 자동화 방법입니다. Fuzzer의 목표는 여러가지 버그를 찾아 결과적으로 프로그램의 버그를 줄이는 것입니다. 그러므로 많은 수의 버그를 찾을 수 있는 여러가지 방법론이 등장했는데, 그 중 하나인 Coverage-guided fuzzing 와 Hybrid fuzzing 을 소개합니다.

Coverage-guided Fuzzing

Coverage-guided Fuzzing은 코드 분기에 도달하는 입력을 feedback하여 다음에 사용될 입력이 됩니다. 따라서, 적절한 입력에 대해서 좋은 coverage를 가질 수 있지만 입력이 적절하지 않을 경우 버그를 찾는데 적지않은 시간이 듭니다. 그 예시로는 아래와 같습니다.

먼저, 테스트를 위해 AFL을 clone한 이후, 컴파일 해줍니다. 그 이후에 아래의 코드를 afl-clang으로 컴파일 합니다.

// afl-clang -o test test.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[]) {
    char buffer[0x10];
    char name[0x10];
    char pass[0x10];
    int a, b;

    printf("name> ");
    read(0, name, 0x0f);
    printf("pass> ");
    read(0, pass, 0x0f);

    if(!strcmp(name, "cat") && !strcmp(pass, "wow")) {
        scanf("%d %d", &a, &b);
        getchar();
        if(a + b == 0x9505)
            gets(buffer);
    }

    return 0;
}

이후에 아래의 명령어를 입력해 input 폴더를 생성 후, 입력으로 넣을 문자열을 파일로 생성합니다.

➜  mkdir inp
➜  echo -ne "cat\nwow\n123 456\nAAAAAAA" > inp/01.txt
➜  fuzz cat inp/01.txt
cat
wow
123 456
AAAAAAAA

위와 같이 입력과 afl-clang으로 컴파일된 파일을 사용하여 다음과 같은 명령어로 퍼징을 시작합니다.

afl-fuzz -i inp -o out ./test @@

/assets/2020-10-01/hybrid_fuzzing.png

위의 그림 보다 더 많은 시간 동안 fuzzing해도 unique crash를 발견할 수 없는 것을 볼 수 있습니다. 이는 분기에 도달하는 입력을 다음 입력으로 하기 때문에, 분기에 도달하는 입력을 찾기 전까지 무작위로 대입해 발생하는 문제입니다. 이런 문제를 해결하기 위해서는 Symbolic/Concolic execution을 사용해 분기를 통과하기 위한 입력을 계산을 한 이후, 다음 입력에 적용해야 합니다.

Hybrid Fuzzing

위에서 설명한 기법이 Hybrid Fuzzing 이란 Fuzzing 방법론입니다. 이는 분기 조건을 만족하기 위한 Symbolic/Concolic execution을 사용해 새로운 분기로 나아갈 수 있도록 입력을 발견하는 Fuzzing 방법론입니다. 그 예시로 아래의 그림을 보면 fuzzer에서 agent를 통해 분기 조건을 풀 수 있도록 요청 하면 해제 후, 다음 입력에 추가해 fuzzer가 해당 입력 값을 사용하여 도달할 수 있는 분기를 최대화 합니다.

/assets/2020-10-01/hybrid_fuzzing_1.png

따라서, Coverage-guided Fuzzing과 Symbolic execution의 장점이 합쳐져 많은 버그를 찾을 수 있을 것으로 생각됩니다. 하지만 단점 또한 그대로 적용돼 거의 모든 분기에 도달할 수 있는 반면 도달하기 위한 연산량의 정도에 따라 성능이 Coverage-guided Fuzzing과 비슷하거나 보다 조금 나은 정도로 처리할 수 있을 것으로 보입니다. 이 방법론에서 발생하는 문제점들은 다음과 같습니다.

문제점

symbolic execution에 필요한 비용이 커, 퍼징 속도의 저하
불필요한 조건 존재 시 성능 하락
과한 리소스 할당으로 인한 조건 처리 성능 하락
2개 이상의 복잡한 조건에 대한 처리

따라서, 위와 같은 문제점들을 해결하기 위해서는 다음과 같은 작업이 필요할 것으로 생각됩니다.

symbolic execution의 비용을 최소화하기 위한 최적의 알고리즘 및 구조 적용
- 동일한 실행 환경을 구축해 symbolic/concolic execution 서버를 구축해 fuzzer와 서버 간 통신으로 성능 하락 최소화
불필요한 조건을 제거 또는 최적화를 통해 최소한의 식으로 표현
- symbolic solver (ex. z3) 사용

이러한 작업들을 진행할 경우 적은 시간으로 많은 버그를 발견할 수 있을 것 예상되지만, 아직은 규모가 큰 프로그램에 대해서 Fuzzing은 어려울 것으로 보입니다. 따라서 필요한 함수를 따로 떼어내 컴파일한 파일에 대해서 적용할 경우, 거의 모든 분기에 대해서 탐색할 수 있으므로 버그를 찾는 데에 유용할 것으로 생각됩니다.

← → Top