KCOV: code coverage for fuzzing

fuzzing용 KCOV와 준비 사항

KCOV: fuzzing을 위한 code coverage

KCOV는 coverage-guided fuzzing에 적합한 형태로 kernel code coverage 정보를 수집하고 노출합니다. 실행 중인 kernel의 coverage data는 debugfs의 `kcov` 파일을 통해 내보냅니다. coverage 수집은 task 단위로 활성화하므로 단일 system call의 정확한 coverage를 포착할 수 있습니다.

KCOV의 목표는 가능한 한 많은 coverage를 모으는 것이 아닙니다. syscall input의 함수로서 비교적 안정적인 coverage를 수집하는 것이 목표입니다. 이를 위해 remote coverage 수집을 활성화한 경우를 제외하면 soft/hard interrupt의 coverage를 수집하지 않고 scheduler나 locking처럼 본질적으로 비결정적인 kernel 영역도 일부 제외합니다.

KCOV는 code coverage 외에 comparison operand도 수집할 수 있습니다. 자세한 내용은 'Comparison operand 수집' 절을 참조하십시오.

syscall handler의 coverage data뿐 아니라 background kernel task나 soft interrupt에서 실행되는, annotation이 지정된 kernel 영역의 coverage도 수집할 수 있습니다. 자세한 내용은 'Remote coverage 수집' 절을 참조하십시오.

사전 요구 사항

KCOV는 compiler instrumentation에 의존하며 GCC 6.1.0 이상 또는 kernel이 지원하는 어떤 Clang version이든 필요합니다.

comparison operand 수집은 GCC 8 이상 또는 Clang에서 지원합니다.

KCOV를 활성화하려면 kernel을 다음과 같이 구성하십시오.

CONFIG_KCOV=y

comparison operand 수집을 활성화하려면 다음을 설정하십시오.

CONFIG_KCOV_ENABLE_COMPARISONS=y

debugfs를 mount한 뒤에만 coverage data에 접근할 수 있습니다.

mount -t debugfs none /sys/kernel/debug

단일 syscall coverage 수집

Coverage 수집

다음 program은 test program 안에서 KCOV를 사용해 단일 syscall의 coverage를 수집하는 방법을 보여 줍니다.

#include <stdio.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/ioctl.h>
#include <sys/mman.h>
#include <unistd.h>
#include <fcntl.h>
#include <linux/types.h>

#define KCOV_INIT_TRACE                        _IOR('c', 1, unsigned long)
#define KCOV_ENABLE                        _IO('c', 100)
#define KCOV_DISABLE                        _IO('c', 101)
#define COVER_SIZE                        (64<<10)

#define KCOV_TRACE_PC  0
#define KCOV_TRACE_CMP 1

int main(int argc, char **argv)
{
    int fd;
    unsigned long *cover, n, i;

    /* A single fd descriptor allows coverage collection on a single
     * thread.
     */
    fd = open("/sys/kernel/debug/kcov", O_RDWR);
    if (fd == -1)
            perror("open"), exit(1);
    /* Setup trace mode and trace size. */
    if (ioctl(fd, KCOV_INIT_TRACE, COVER_SIZE))
            perror("ioctl"), exit(1);
    /* Mmap buffer shared between kernel- and user-space. */
    cover = (unsigned long*)mmap(NULL, COVER_SIZE * sizeof(unsigned long),
                                 PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
    if ((void*)cover == MAP_FAILED)
            perror("mmap"), exit(1);
    /* Enable coverage collection on the current thread. */
    if (ioctl(fd, KCOV_ENABLE, KCOV_TRACE_PC))
            perror("ioctl"), exit(1);
    /* Reset coverage from the tail of the ioctl() call. */
    __atomic_store_n(&cover[0], 0, __ATOMIC_RELAXED);
    /* Call the target syscall call. */
    read(-1, NULL, 0);
    /* Read number of PCs collected. */
    n = __atomic_load_n(&cover[0], __ATOMIC_RELAXED);
    for (i = 0; i < n; i++)
            printf("0x%lx\n", cover[i + 1]);
    /* Disable coverage collection for the current thread. After this call
     * coverage can be enabled for a different thread.
     */
    if (ioctl(fd, KCOV_DISABLE, 0))
            perror("ioctl"), exit(1);
    /* Free resources. */
    if (munmap(cover, COVER_SIZE * sizeof(unsigned long)))
            perror("munmap"), exit(1);
    if (close(fd))
            perror("close"), exit(1);
    return 0;
}

`addr2line`을 거친 program 출력은 다음과 같습니다.

SyS_read
fs/read_write.c:562
__fdget_pos
fs/file.c:774
__fget_light
fs/file.c:746
__fget_light
fs/file.c:750
__fget_light
fs/file.c:760
__fdget_pos
fs/file.c:784
SyS_read
fs/read_write.c:562

program이 여러 thread의 coverage를 독립적으로 수집해야 한다면 각 thread에서 `/sys/kernel/debug/kcov`를 별도로 열어야 합니다.

interface는 test process를 효율적으로 fork할 수 있도록 세밀하게 설계되었습니다. parent process가 `/sys/kernel/debug/kcov`를 열고 trace mode를 활성화하며 coverage buffer를 mmap한 다음 loop에서 child process를 fork할 수 있습니다. child process는 coverage만 활성화하면 됩니다. thread가 종료될 때 coverage는 자동으로 비활성화됩니다.

Comparison operand 수집

Comparison operand 수집

comparison operand 수집은 coverage 수집과 비슷합니다.

/* Same includes and defines as above. */

/* Number of 64-bit words per record. */
#define KCOV_WORDS_PER_CMP 4

/*
 * The format for the types of collected comparisons.
 *
 * Bit 0 shows whether one of the arguments is a compile-time constant.
 * Bits 1 & 2 contain log2 of the argument size, up to 8 bytes.
 */

#define KCOV_CMP_CONST          (1 << 0)
#define KCOV_CMP_SIZE(n)        ((n) << 1)
#define KCOV_CMP_MASK           KCOV_CMP_SIZE(3)

int main(int argc, char **argv)
{
    int fd;
    uint64_t *cover, type, arg1, arg2, is_const, size;
    unsigned long n, i;

    fd = open("/sys/kernel/debug/kcov", O_RDWR);
    if (fd == -1)
            perror("open"), exit(1);
    if (ioctl(fd, KCOV_INIT_TRACE, COVER_SIZE))
            perror("ioctl"), exit(1);
    /*
    * Note that the buffer pointer is of type uint64_t*, because all
    * the comparison operands are promoted to uint64_t.
    */
    cover = (uint64_t *)mmap(NULL, COVER_SIZE * sizeof(unsigned long),
                                 PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
    if ((void*)cover == MAP_FAILED)
            perror("mmap"), exit(1);
    /* Note KCOV_TRACE_CMP instead of KCOV_TRACE_PC. */
    if (ioctl(fd, KCOV_ENABLE, KCOV_TRACE_CMP))
            perror("ioctl"), exit(1);
    __atomic_store_n(&cover[0], 0, __ATOMIC_RELAXED);
    read(-1, NULL, 0);
    /* Read number of comparisons collected. */
    n = __atomic_load_n(&cover[0], __ATOMIC_RELAXED);
    for (i = 0; i < n; i++) {
            uint64_t ip;

            type = cover[i * KCOV_WORDS_PER_CMP + 1];
            /* arg1 and arg2 - operands of the comparison. */
            arg1 = cover[i * KCOV_WORDS_PER_CMP + 2];
            arg2 = cover[i * KCOV_WORDS_PER_CMP + 3];
            /* ip - caller address. */
            ip = cover[i * KCOV_WORDS_PER_CMP + 4];
            /* size of the operands. */
            size = 1 << ((type & KCOV_CMP_MASK) >> 1);
            /* is_const - true if either operand is a compile-time constant.*/
            is_const = type & KCOV_CMP_CONST;
            printf("ip: 0x%lx type: 0x%lx, arg1: 0x%lx, arg2: 0x%lx, "
                    "size: %lu, %s\n",
                    ip, type, arg1, arg2, size,
            is_const ? "const" : "non-const");
    }
    if (ioctl(fd, KCOV_DISABLE, 0))
            perror("ioctl"), exit(1);
    /* Free resources. */
    if (munmap(cover, COVER_SIZE * sizeof(unsigned long)))
            perror("munmap"), exit(1);
    if (close(fd))
            perror("close"), exit(1);
    return 0;
}

KCOV의 code coverage 수집 mode와 comparison operand 수집 mode는 서로 배타적이므로 동시에 사용할 수 없습니다.

Remote coverage와 handle 형식

Remote coverage 수집

userspace process가 발생시킨 syscall handler의 coverage뿐 아니라 다른 context에서 실행되는 kernel 영역의 coverage도 수집할 수 있습니다. 이를 `remote` coverage라고 합니다.

KCOV로 remote coverage를 수집하려면 다음이 필요합니다.

1. coverage를 수집할 code section에 `kcov_remote_start`와 `kcov_remote_stop` annotation을 지정하도록 kernel code를 수정합니다.

2. coverage를 수집하는 userspace process에서 `KCOV_ENABLE` 대신 `KCOV_REMOTE_ENABLE`을 사용합니다.

`kcov_remote_start`, `kcov_remote_stop` annotation과 `KCOV_REMOTE_ENABLE` ioctl은 특정 coverage collection section을 식별하는 handle을 받습니다. handle 사용 방식은 해당 code section이 실행되는 context에 따라 다릅니다.

KCOV는 다음 context의 remote coverage 수집을 지원합니다.

1. global kernel background task. kernel boot 중 제한된 수의 instance로 생성되는 task입니다. 예를 들어 USB HCD 하나마다 USB `hub_event` worker 하나가 생성됩니다.

2. local kernel background task. userspace process가 kernel interface와 상호작용할 때 생성되며 보통 process가 종료되면 함께 종료됩니다. 예를 들어 vhost worker가 있습니다.

3. soft interrupt.

1번과 3번에서는 고유한 global handle을 선택해 해당 `kcov_remote_start` 호출에 전달해야 합니다. userspace process는 이 handle을 `kcov_remote_arg` struct의 `handles` array field에 넣어 `KCOV_REMOTE_ENABLE`에 전달합니다. 그러면 사용 중인 KCOV device가 handle이 참조하는 code section에 연결됩니다. 서로 다른 code section을 식별하는 여러 global handle을 한 번에 전달할 수 있습니다.

2번에서는 userspace process가 0이 아닌 handle을 `kcov_remote_arg` struct의 `common_handle` field로 전달해야 합니다. 이 common handle은 현재 `task_struct`의 `kcov_handle` field에 저장되며 사용자 지정 kernel code 변경을 통해 새로 생성한 local task에 전달해야 합니다. local task는 전달받은 handle을 `kcov_remote_start`와 `kcov_remote_stop` annotation에 사용해야 합니다.

KCOV는 global handle과 common handle에 미리 정의된 형식을 사용합니다. 각 handle은 `u64` integer이며 현재 top byte 하나와 하위 4byte만 사용합니다. byte 4-7은 예약되어 있으므로 0이어야 합니다.

global handle에서는 top byte가 handle이 속한 subsystem id를 나타냅니다. 예를 들어 KCOV는 USB subsystem id로 `1`을 사용합니다. 하위 4byte는 subsystem 안의 task instance id입니다. 각 `hub_event` worker는 USB bus 번호를 task instance id로 사용합니다.

common handle은 특정 subsystem에 속하지 않으므로 subsystem id로 예약값 `0`을 사용합니다. 하위 4byte는 common handle을 `KCOV_REMOTE_ENABLE`에 전달한 userspace process가 생성한 모든 local task의 집합 instance를 식별합니다.

system에서 단일 userspace process의 coverage만 수집한다면 common handle instance id에 어떤 값이든 사용할 수 있습니다. 여러 process가 common handle을 사용한다면 process마다 고유한 instance id를 사용해야 합니다. process id를 common handle instance id로 사용하는 방법이 있습니다.

다음 program은 process가 생성한 local task와 USB bus 1번을 처리하는 global task 양쪽에서 KCOV coverage를 수집하는 방법을 보여 줍니다.

/* Same includes and defines as above. */

struct kcov_remote_arg {
    __u32                trace_mode;
    __u32                area_size;
    __u32                num_handles;
    __aligned_u64        common_handle;
    __aligned_u64        handles[0];
};

#define KCOV_INIT_TRACE                        _IOR('c', 1, unsigned long)
#define KCOV_DISABLE                        _IO('c', 101)
#define KCOV_REMOTE_ENABLE                _IOW('c', 102, struct kcov_remote_arg)

#define COVER_SIZE        (64 << 10)

#define KCOV_TRACE_PC        0

#define KCOV_SUBSYSTEM_COMMON        (0x00ull << 56)
#define KCOV_SUBSYSTEM_USB        (0x01ull << 56)

#define KCOV_SUBSYSTEM_MASK        (0xffull << 56)
#define KCOV_INSTANCE_MASK        (0xffffffffull)

static inline __u64 kcov_remote_handle(__u64 subsys, __u64 inst)
{
    if (subsys & ~KCOV_SUBSYSTEM_MASK || inst & ~KCOV_INSTANCE_MASK)
            return 0;
    return subsys | inst;
}

#define KCOV_COMMON_ID        0x42
#define KCOV_USB_BUS_NUM        1

int main(int argc, char **argv)
{
    int fd;
    unsigned long *cover, n, i;
    struct kcov_remote_arg *arg;

    fd = open("/sys/kernel/debug/kcov", O_RDWR);
    if (fd == -1)
            perror("open"), exit(1);
    if (ioctl(fd, KCOV_INIT_TRACE, COVER_SIZE))
            perror("ioctl"), exit(1);
    cover = (unsigned long*)mmap(NULL, COVER_SIZE * sizeof(unsigned long),
                                 PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
    if ((void*)cover == MAP_FAILED)
            perror("mmap"), exit(1);

    /* Enable coverage collection via common handle and from USB bus #1. */
    arg = calloc(1, sizeof(*arg) + sizeof(uint64_t));
    if (!arg)
            perror("calloc"), exit(1);
    arg->trace_mode = KCOV_TRACE_PC;
    arg->area_size = COVER_SIZE;
    arg->num_handles = 1;
    arg->common_handle = kcov_remote_handle(KCOV_SUBSYSTEM_COMMON,
                                                    KCOV_COMMON_ID);
    arg->handles[0] = kcov_remote_handle(KCOV_SUBSYSTEM_USB,
                                            KCOV_USB_BUS_NUM);
    if (ioctl(fd, KCOV_REMOTE_ENABLE, arg))
            perror("ioctl"), free(arg), exit(1);
    free(arg);

    /*
     * Here the user needs to trigger execution of a kernel code section
     * that is either annotated with the common handle, or to trigger some
     * activity on USB bus #1.
     */
    sleep(2);

    /*
     * The load to the coverage count should be an acquire to pair with
     * pair with the corresponding write memory barrier (smp_wmb()) on
     * the kernel-side in kcov_move_area().
     */
    n = __atomic_load_n(&cover[0], __ATOMIC_ACQUIRE);
    for (i = 0; i < n; i++)
            printf("0x%lx\n", cover[i + 1]);
    if (ioctl(fd, KCOV_DISABLE, 0))
            perror("ioctl"), exit(1);
    if (munmap(cover, COVER_SIZE * sizeof(unsigned long)))
            perror("munmap"), exit(1);
    if (close(fd))
            perror("close"), exit(1);
    return 0;
}