OpenJPEG Code Coverage 코드 작성 및 알고리즘 설명

OpenJPEG Code Coverage 코드 작성 및 알고리즘 설명

Index

• Coveraged-Guided Fuzzing

• OpenJPEG Code Coverage Algorithm

  • OpenJPEG coverage.c

  • Coveraged-Guided Fuzzing Algorithm

Coverage-Guided Fuzzing

Coverage-Guided Fuzzing은 code coverage 정보를 이용하여 다양한 input을 생성함으로써, 바이너리의 전체적인 control flow를 탐색하도록 하는 방식입니다.

동작 설명

Coverage-Guided Fuzzing은 다음과 같은 방식으로 동작합니다.

1. 초기 seed 데이터를 mutation을 위해 queue에 넣는다.

2. queue에 존재하는 seed를 선택하고, mutation을 수행하여 test case를 생성한다.

3. 생성한 모든 test case를 실행하여 code coverage를 측정하고 crash 여부를 확인한다.

4. 실행한 test case가 code coverage를 증가시키면, 해당 test case를 seed로서 queue에 넣고 다음 라운드의 mutation의 가장 우선순위에 놓는다. 그렇지 않는다면 그냥 버린다.

5. crash가 발생한다면 report에 추가한다.

6. 2로 돌아간다.

pseudo-code

다음은 Coverage-Guided Fuzzing을 코드로 구현한 예시입니다.

// Coverage-guided fuzzing algorithm.
​
let corpus = initial_set_of_inputs();
loop {
    let old_input = choose_one(&corpus);
    let new_input = mutate(old_input);
    let result = run_fuzz_target(new_input);
​
    // If the fuzz target crashed/panicked/etc report
    // that.
    if result.is_interesting() {
        report_interesting(new_input);
    }
​
    // If executing the input hit new code paths, add
    // it to our corpus.
    if result.executed_new_code_paths() {
        corpus.insert(new_input);
    }
}

Coverage-Guided Fuzzing의 장점

일반적인 Mutation-based Fuzzing과 비교했을 때, Coverage-Guided Fuzzing의 장점은 다음과 같습니다.

1. Maximize Binary's Behavior code coverage를 측정함으로써 타겟 바이너리의 동작을 최대화하여 퍼징을 시도할 수 있습니다.각각의 path에 대한 input을 시드로 구성함으로써 다양한 path에 대해 정밀한 퍼징이 가능합니다.

2. Execution Feedback coverage 정보를 피드백으로 하여, mutation 시 변환할 위치의 우선순위를 정할 수 있어 효율적인 퍼징이 가능합니다.

OpenJPEG Code Coverage Algorithm

OpenJPEG에 대한 Coverage Algorithm은 크게 두 가지로 이루어져있습니다.

• trace-pc-guard 기능을 활용하여 OpenJPEG 프로그램 내의 Coverage 정보를 측정해서 bitmap 형태로 Fuzzer에 제공합니다.

• Fuzzer는 제공된 Coverage 정보를 활용하여 Fuzzing을 시도합니다.

OpenJPEG coverage.c

프로그램의 Coverage 정보를 측정하여 Fuzzer에 제공하는 부분입니다. 주요 동작은 다음과 같습니다.

• Coverage 정보를 bitmap 형태로 저장

• 공유 메모리를 이용하여 해당 데이터를 Fuzzer에 제공

// trace-pc-guard-cb.cc
#include <stdint.h>
#include <stdio.h>
#include <sanitizer/coverage_interface.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
​
​
void* shmAddr = NULL;
​
void memory_init(){
    int shmID;
​
    if ((shmID = shmget((key_t)1337, 0x1000, IPC_CREAT | 0666)) < 0){
        fprintf(stderr, "shmget() error!\n");
        exit(-1);
    }
​
    if ((shmAddr = shmat(shmID, (void*) 0, 0)) < 0 ){
        fprintf(stderr, "shmat() error\n");
        exit(-1);
    }
​
    memset(shmAddr, 0, 0x1000);
}
​
​
void __sanitizer_cov_trace_pc_guard_init(uint32_t *start, uint32_t *stop) {
  static uint64_t N;  // Counter for the guards.
  if (start == stop || *start) return;  // Initialize only once.
      
  memory_init();
  for (uint32_t *x = start; x < stop; x++)
    *x = N++;  // Guards should start from 0.
​
  printf("INIT: %p %p\n", start, stop);
  printf("Shared Memory : %p\n", shmAddr);
}
​
​
void __sanitizer_cov_trace_pc_guard(uint32_t *guard) {
  if (!*guard) return;
  
  uint8_t* pSharedBuffer = shmAddr;
  int idx = (*guard / 8);
  
  pSharedBuffer[idx] |= 1 << (*guard % 8);
  *guard = 0;
}

Store data in bitmap form

__sanitizer_cov_trace_pc_guard_init()과정을 통해, OpenJPEG 프로그램의 basic block을 0부터 시작하는 숫자의 값으로 id를 정합니다. basic block 마다 1 bit의 공간을 할당하여 호출된 basic block은 1로, 호출되지 않은 basic block은 0으로 나타냅니다. 0~7 까지의 basic block을 첫 번째 바이트로, 8~15 까지의 basic block을 두 번째 바이트로 나타내는 bitmap의 형태로 데이터를 관리합니다.

Pass data in Shared Memory

I/O 부하를 줄이기 위해서 공유 메모리를 이용하여 Fuzzer에게 Coverage 정보를 전달하기 위해, 메모리를 할당하는 memory_init() 과정을 수행합니다. openjpeg-data의 데이터로 프로그램을 실행해본 결과, idx 값이 최대 1133을 기록하였기 때문에 지나는 모든 경로를 포함할 수 있도록 충분히 큰 0x1000의 크기로 메모리를 할당했습니다.

존재하는 모든 block을 포함하려하거나, 다른 프로그램에서도 메모리 크기에 대해서 범용적으로 사용하고자 한다면, (stop - start) / 4 의 크기로 메모리를 할당하고, 공유 메모리를 size | bitmap 등의 구조로 구성함으로써 Fuzzer로 데이터를 전달할 수 있습니다.

Coveraged-Guided Fuzzing Algorithm

Fuzzer의 main에서 하는 동작은 다음과 같습니다.

• Coverage 정보를 가져올 공유 메모리 할당

• 제공된 seed 파일을 읽어들여 corpus에 추가

• corpus를 mutation하여 input 생성

• 생성된 input 데이터로 "in/cur_input" 파일 생성

• Target 프로그램 실행

#include <iostream>
#include <fstream>
#include <cstdio>
#include <stdlib.h>
#include <signal.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/mman.h>
#include <sys/wait.h>
#include <queue>
#include <vector>
#include <dirent.h>
#include <string.h>
//#include <openssl/sha.h>
#include "sha256.h"
​
using namespace std;
​
#define TARGET  "/home/bob/openjpeg/build/bin/opj_decompress"
​
void* shmAddr;
int totalpath = 0;
int totalexec = 0;
int crash = 0;
​
queue<uint8_t *> input;
vector<uint8_t *> corpus;
vector<uint8_t *> path;
​
...
    
void shared_memory_init(){
    int shmID;
    
    if ((shmID = shmget((key_t)1337, 0x1000, IPC_CREAT | 0666)) < 0 ){
        perror("shmget() error!\n");
        exit(-1);
    }
    
    if ((shmAddr = shmat(shmID, (void*)0, 0)) == (void*)-1){
        perror("shmat() error!\n");
        exit(-1);
    }
}
​
void init_corpus(){
    
    DIR *dir;
    struct dirent *entry;
    string in_dir = "./in/";
​
    if (!(dir = opendir(in_dir.c_str()))){
        perror("open dir error!\n");
    }
​
    while ((entry = readdir(dir))){
        if (!strcmp(entry->d_name, ".") || !strcmp(entry->d_name,"..")) continue;
        string filename(entry->d_name);
        ifstream in(in_dir + filename, ios::ate);
​
        if (in.fail()){
            perror("open file error!\n");
            exit(-1);
        }
​
        uint32_t length = in.tellg();
        in.seekg(0, ios::beg);
​
        uint8_t* buf = new uint8_t[length+1+4];
        memcpy(buf, &length, 4);
        in.read((char*)buf + 4, length);
​
        corpus.push_back(buf);
    }
}
​
void create_input(){
    // make cur_input file by <vector>input
    uint8_t* data = input.front();
    uint32_t length;
​
    memcpy((char*)&length, data, 4);
​
    ofstream out("out/cur_input.j2k", ios::binary);
    out.write((char*)data + 4, length);
    out.close();
    input.pop();
}
​
...
​
int main(int argc, char* argv[]){
​
    char* target = TARGET;
    char* argvs[] = {TARGET, "-i", "out/cur_input.j2k", "-o", "out/tmp.pgm", NULL};
​
    printf("[+] target : %s\n", target);
​
    shared_memory_init();
    init_corpus();
​
    while (true){
    
        for (int i = 0; i < corpus.size(); i++){
            mutation(corpus[i]);
​
            // run target with the input created by mutation.
            int input_size = input.size();
            for (int j = 0; j < input_size; j++){
                create_input();
                //use_radamsa(); // test
                run_target(target, argvs);
            }
        }
    }
​
    return 0;
}

corpus나 path는 연속적으로 참조하기 때문에 둘 모두 vector를 사용하였고, input의 경우 추가/삭제가 빈번하기 때문에 queue를 이용하였습니다.

Initialize Shared Memory

shared_memory_init()을 통해 Target 프로그램의 Coverage 정보를 받아올 공유 메모리를 생성합니다.

Initialize Corpus

init_corpus()를 통해 "./in" 디렉토리 내부에 존재하는 Seed 파일들을 읽어와서 메모리를 할당하여 데이터를 저장한 뒤, 해당 포인터들을 Corpus에 저장합니다. 데이터의 크기를 저장하기 위해, 초기 4바이트는 데이터의 크기를 저장하고 +4 위치부터 데이터를 저장합니다.

Seed 파일을 input으로 실행한 path 경로와, Seed 파일을 mutation 한 결과를 input으로 실행한 path 경로가 동일한 경우를 기대하여 초기 Seed 값을 input에 바로 제공하지 않았습니다.

Create cur_input

프로그램의 입력은 cur_input 파일로 이루어지므로 input에서 가져온 데이터를 길이를 나타내는 앞 4바이트를 잘라내고 파일로 만듭니다.

Mutation

corpus에서 가져온 데이터들을 mutation 하여 input을 생성합니다. 뒤에서 설명될 is_newPath() 함수로 new Path를 기록하는 input이 새로운 corpus로서 제공되기 때문에, 다양한 path에 대하여 input을 생성할 수 있게 됩니다. mutation()의 경우 제대로 구현되지 않았기 때문에, 간단하게 설명하겠습니다.

void mutation(uint8_t* _data){
    uint8_t* data = _data + 4;
    uint32_t length;
    
    memcpy((char*)&length, _data, 4);
​
    uint8_t* new_data;
    
    switch(random){
        case 1: 
            // check buffer overflow
        case 2:
            // check Known Value (-1, 0, 1, INT_MAX, ...)
        case 3:
            // bit flip
        case 4:
            ...
    }
    
    input.push(new_data);
}

length | data 형태로 구성된 _data를 구분한 뒤, 위와 같이 랜덤하게 Mutation 방법을 선택합니다. 길이를 많이 늘려서 bof를 탐지하는 방법, -1, 0, INT_MAX 값 등의 Known Value를 넣는 방법, bit flip 방법 등 다양하게 구성하였습니다.

좀 더 정밀하게 구성한다면, 바꾼 byte의 위치를 bitmap 형태 등으로 관리하여, 생성한 input이 새로운 path를 지나는 경우에 해당 byte나 그 주변 값을 바꾸도록 할 수도 있을 것 같습니다.

Run Target with input

생성된 cur_input 파일을 인자로 하여 프로그램을 실행시킵니다. 주요 기능은 다음과 같습니다.

• fork()를 사용하여 Target 프로세스를 실행

• 자식 프로세스가 종료될 때까지 기다린 뒤, crash가 발생했는지 확인. 발생했다면 리포트에 추가

• new path가 나타났는지 확인. 나타났다면 해당 input을 corpus에 추가

bool is_newPath(){
    uint8_t *digest = sha256((unsigned char*)shmAddr, 0x1000);
​
    for (int i = 0; i < path.size(); i++){
        if (!memcmp(digest, path[i], 32)) return false;
    }
​
    path.push_back(digest);
    totalpath++;
​
    return true;
}
​
bool is_crashed(pid_t state){
    if(WIFSIGNALED(state)) {
        return true;
    }
    return false;
}
​
void Add_cur_input(){
    ifstream in("out/cur_input.j2k", ios::ate);
    if (in.fail()){
        perror("open cur_input error!\n");
        exit(-1);
    }
    uint32_t length = in.tellg();
    in.seekg(0, ios::beg);
    uint8_t* buf = new uint8_t[length+1];
    in.read((char*)buf, length);
    
    string fileName = "out/crash/input_" + to_string(crash);
    ofstream out(fileName, ios::binary);
    out.write((char*)buf, length);
    out.close();
}
​
void Add_state(int state){
    ofstream out("out/crash_log", ios::app);
    out << "======================================" << endl;
    out << "crash " << crash << endl;
    out << "  signal : " << (int)WTERMSIG(state) << endl;
    out.close();
    crash++;
}
​
void Add_to_report(int state){
    Add_cur_input();
    Add_state(state);
}
​
void Add_to_corpus(){
    ifstream in("out/cur_input.j2k", ios::ate);
    if (in.fail()){
        perror("open cur_input error!\n");
        exit(-1);
    }
    uint32_t length = in.tellg();
    in.seekg(0, ios::beg);
​
    uint8_t* buf = new uint8_t[length+1+4];
    memcpy(buf, &length, 4);
    in.read((char*)buf+4, length);
    corpus.insert(corpus.begin(), buf);
}
​
void run_target(char* target, char* argvs[]){
​
    pid_t pid = fork();
    int state;
​
    if (pid < 0){
        perror("fork() error!\n");
        exit(-1);
    }
    else if (pid == 0){
        execv(target, argvs);
        totalexec++;
        exit(0);
    }
    else {
        wait(&state);
​
        // Check if the testcase causes crash.
        if (is_crashed(state)){
            Add_to_report(state);
        }
​
​
        // Check if the testcase hits new code path.
        if (is_newPath()){
            // If it hits new code path, Add to corpus.
            Add_to_corpus();
        }
    }       
}

Target 프로그램 실행

자식 프로세스를 생성한 뒤, execv()를 이용하여 Target 프로그램을 실행합니다. totalexec 횟수를 증가시킵니다.

Check crash

자식 프로세스가 종료될 때까지 대기한 뒤, is_crash()를 이용하여 자식 프로세스가 비정상적으로 종료되었는지 확인합니다. 비정상적으로 종료가 되었다면, Add_to_report()를 호출하여 crash가 발생한 input과 crash log를 out 디렉토리에 추가합니다.

Check new Path

Coverage-Guided Fuzzing의 핵심입니다. 현재의 input으로 발생한 Path와 기존 Path들을 SHA2 시그니처 검사를 통해 비교하여 새로운 Path가 발견되었는지 확인합니다. 발견하였다면, 해당 input을 corpus에 추가합니다. 본 기능은 is_newPath()를 통해 다음과 같이 동작합니다.

1. 공유 메모리에 존재하는 값을 가져온 뒤, SHA2 (SHA256)를 이용하여 해쉬 값을 계산합니다.

2. path vector에 존재하는 hash 값들과 비교합니다. 만약 동일한 값이 존재하는 경우 false를 리턴합니다.

3. 동일한 값이 없는 경우, 해당 hash 값을 path에 추가한 뒤, 현재 cur_input을 corpus에 추가합니다. 다음 라운드에서 최우선 순위에 놓기 위하여 가장 첫 번째에 추가합니다.

Conclude

위와 같이 Coverage-Guided Fuzzer를 만들어보았습니다.

첨부한 소스코드 외에 다른 코드는 github에 있습니다.

Reference

• http://www.zedwood.com/article/cpp-sha256-function

• Full-speed fuzzing: Reducing fuzzing overhead through coverage-guided tracing

• https://fitzgeraldnick.com/2019/09/04/combining-coverage-guided-and-generation-based-fuzzing.html