Concolic testing 과 AddressSanitizer를 사용한 메모리 에러 검출

개요

테스트 케이스 자동생성을 위해 사용하는 기법 중 Concolic Testing이란 기법이 있다.(자세한 내용은 이분야의 대가이신 KAIST 김문주 교수님 홈페이지(Link)에서 알아보기로 하자.) Concolic Testing을 사용하면 소스코드가 가질 수 있는 다양한 패쓰 조합에 대한 테스트 케이스를 생성해주며, 실제 구동함에 따른 결과를 확인할 수 있다. 이에 최근에 메모리 에러 검출에 도움이 되는 AddressSanitizer에 대해 알아보니 두 개 기법을 조합하면 좋을 것 같아 시도해보았다.

Concolic Testing : 테스트 케이스 자동 생성 + SW실행
AddressSanitizer : SW실행에 따른 각종 Memory 관련 에러 검출

준비물

CROWN : Concolic Testing 도구 (Link) (현재는 github에서 내려간 상태이며, CREST를 사용해도 괜찮음)

예제 코드를 아래와 같이 작성하였다. 심볼릭 처리 대상인 x 값에 따라 경로를 달리 탐색하며, 음수일 경우는 Memory Leak을 발생시켰으며, 양수일 경우 Memory Overflow를 발생시키도록 하였다. Concolic Testing을 적용하여 실행하였을때 제대로 메모리 에러를 검출하는지 알아보자.

예제코드

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include <crown.h>

int get_sign(int x) {
        if ( x == 0 ) {
                return 0;
        } else if ( x < 0 ) {
                char *p = (char *)malloc(16);
                return -1;
        } else {
                char *p = (char *)malloc(x);
                p[x] = 0xaa;
                free(p);
                return 1;
        }
}

int main(int argc, char *argv[]) {
        int x;

        SYM_int(x);

        printf("input x = %d\n", x);
        get_sign(x);

        return 0;
}

사용 Makefile

DIR=/media/Download/CROWN
CILLY=$(DIR)/cil/bin/cilly
SOLVER_DIR=${DIR}
CC=gcc
CILLYCOVFLAGS=--save-temps --doCrownInstrument
CILLYFLAGS=--save-temps --doCrownInstrument
CFLAGS= -I${DIR}/include -m64
LDFLAGS= -L${DIR}/lib -m64 -lcrown-fp -lstdc++ -L${SOLVER_DIR}/lib -lz3 \
        -g -lm -fopenmp -lrt
BCFLAGS= --coverage
SOURCES= example.c
TARGET= example

all: $(SOURCES) clean
        $(CILLY) $(CILLYCOVFLAGS) $(SOURCES) -o $(TARGET) $(CFLAGS) $(LDFLAGS)
        rm -f branches cfg cfg_branches cfg_func_map funcount idcount stmtcount
        $(CILLY) $(CILLYFLAGS) $(SOURCES) -o $(TARGET) $(CFLAGS) $(LDFLAGS)
        $(CC) -o $(TARGET)_replay $(SOURCES) $(CFLAGS) -L$(DIR)/lib \
                -lcrown-replay $(BCFLAGS)
        ${DIR}/bin/process_cfg

clean:
        rm -f $(TARGET) $(TARGET)_replay *.cil.c *.i *.o *.gcno *.gcov
        rm -f branches cfg cfg_branches cfg_func_map funcount idcount stmtcount szd_execution input coverage

수행내용

CROWN만으로 빌드하여 실행하면 아래와 같은 결과를 얻을 수 있다. 테스트 케이스를 3개를 성공적으로 만들어서 경로 탐색을 마친것을 확인할 수 있다. 다만, 코드에 일부러 심어놓은 Memory 에러들을 자체적으로 탐지하지 못한 것을 알수 있다.

AddressSanitizer를 사용하여 다시 빌드하고, Memory 에러들을 검출하는지 알아보자. CFLAGS에 -fsanitize=address 옵션을 주어 다시 빌드하여 재실행하면 아래와 같은 결과를 얻을 수 있다.

Iteration 1 : Memory leak

Iteration 2 : Heap buffer overflow

Iteration 2의 Heap buffer overflow 에러 검출 화면

전체 로그

klee@2192db3eaee1:/media/workspace/crown_tutorial_1$ run_crown ./example 100 -dfs
-------------------------
input x = 0

=================================================================
==7424==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 128 byte(s) in 1 object(s) allocated from:
    #0 0x14de1997a6b2 in operator new[](unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x996b2)
    #1 0x403547 in __CrownInit libcrown/crown.cc:170
    #2 0x40323e in __globinit_example /media/workspace/crown_tutorial_1/example.c:30
    #3 0x402fa0 in main /media/workspace/crown_tutorial_1/example.c:28
    #4 0x14de18d8282f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

Direct leak of 56 byte(s) in 1 object(s) allocated from:
    #0 0x14de1997a532 in operator new(unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x99532)
    #1 0x41b9d7 in crown::AtomicExprWriter::Clone() const libcrown/atomic_expression_writer.cc:21
    #2 0x41d586 in crown::SymbolicMemoryWriter::MemElem::read(unsigned long, unsigned long, crown::Value_t) const libcrown/symbolic_memory_writer.cc:83
    #3 0x41cf0c in crown::SymbolicMemoryWriter::read(unsigned long, crown::Value_t) const libcrown/symbolic_memory_writer.cc:194
    #4 0x4089f9 in crown::SymbolicInterpreter::Load(int, unsigned long, crown::Value_t) libcrown/symbolic_interpreter.cc:77
    #5 0x403c9b in __CrownLoad libcrown/crown.cc:326
    #6 0x4030e1 in main /media/workspace/crown_tutorial_1/example.c:28
    #7 0x14de18d8282f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

SUMMARY: AddressSanitizer: 184 byte(s) leaked in 2 allocation(s).
Iteration 1 (0s, 0.0s): covered 1 branches [1 reach funs, 4 reach branches].(1, 0)
-------------------------
input x = -1

=================================================================
==7427==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 128 byte(s) in 1 object(s) allocated from:
    #0 0x152d4f33a6b2 in operator new[](unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x996b2)
    #1 0x403547 in __CrownInit libcrown/crown.cc:170
    #2 0x40323e in __globinit_example /media/workspace/crown_tutorial_1/example.c:30
    #3 0x402fa0 in main /media/workspace/crown_tutorial_1/example.c:28
    #4 0x152d4e74282f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

Direct leak of 56 byte(s) in 1 object(s) allocated from:
    #0 0x152d4f33a532 in operator new(unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x99532)
    #1 0x41b9d7 in crown::AtomicExprWriter::Clone() const libcrown/atomic_expression_writer.cc:21
    #2 0x41d586 in crown::SymbolicMemoryWriter::MemElem::read(unsigned long, unsigned long, crown::Value_t) const libcrown/symbolic_memory_writer.cc:83
    #3 0x41cf0c in crown::SymbolicMemoryWriter::read(unsigned long, crown::Value_t) const libcrown/symbolic_memory_writer.cc:194
    #4 0x4089f9 in crown::SymbolicInterpreter::Load(int, unsigned long, crown::Value_t) libcrown/symbolic_interpreter.cc:77
    #5 0x403c9b in __CrownLoad libcrown/crown.cc:326
    #6 0x4030e1 in main /media/workspace/crown_tutorial_1/example.c:28
    #7 0x152d4e74282f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

Direct leak of 16 byte(s) in 1 object(s) allocated from:
    #0 0x152d4f339602 in malloc (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x98602)
    #1 0x4028d4 in get_sign /media/workspace/crown_tutorial_1/example.c:12
    #2 0x403133 in main /media/workspace/crown_tutorial_1/example.c:28
    #3 0x152d4e74282f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

SUMMARY: AddressSanitizer: 200 byte(s) leaked in 3 allocation(s).
Iteration 2 (0s, 0.34s): covered 3 branches [1 reach funs, 4 reach branches].(3, 1)
-------------------------
input x = 536870912
=================================================================
==7430==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x14d277bba800 at pc 0x000000402cda bp 0x7ffc7933edf0 sp 0x7ffc7933ede0
WRITE of size 1 at 0x14d277bba800 thread T0
    #0 0x402cd9 in get_sign /media/workspace/crown_tutorial_1/example.c:16
    #1 0x403133 in main /media/workspace/crown_tutorial_1/example.c:28
    #2 0x14d27b75882f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
    #3 0x4024a8 in _start (/media/workspace/crown_tutorial_1/example+0x4024a8)

0x14d277bba800 is located 0 bytes to the right of 536870912-byte region [0x14d257bba800,0x14d277bba800)
allocated by thread T0 here:
    #0 0x14d27c34f602 in malloc (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x98602)
    #1 0x402ab1 in get_sign /media/workspace/crown_tutorial_1/example.c:15
    #2 0x403133 in main /media/workspace/crown_tutorial_1/example.c:28
    #3 0x14d27b75882f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

SUMMARY: AddressSanitizer: heap-buffer-overflow /media/workspace/crown_tutorial_1/example.c:16 get_sign
Shadow bytes around the buggy address:
  0x029acef6f4b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x029acef6f4c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x029acef6f4d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x029acef6f4e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x029acef6f4f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x029acef6f500:[fa]fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x029acef6f510: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x029acef6f520: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x029acef6f530: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x029acef6f540: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x029acef6f550: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
==7430==ABORTING
Iteration 3 (0s, 0.65s): covered 3 branches [1 reach funs, 4 reach branches].(3, 3)
Prediction failed!
klee@2192db3eaee1:/media/workspace/crown_tutorial_1$

로그가 좀 복잡한데, Iteration 1 / Iteration 2 부분에 보면 memory leaks과 heap-buffer-overflow 를 제대로 검출한 것을 확인할 수 있었다.

crown API에서 지속적으로 leak이 발생하였다고 report가 되는데, 무시할 수 있을지 모르겠다.

gcc version 5.4.0에서는 -fsanitize-blacklist 옵션이 없다고 나온다.

저작자표시 비영리 동일조건

Joohyun's BLOG

Concolic testing 과 AddressSanitizer를 사용한 메모리 에러 검출

개요

준비물

수행내용

티스토리툴바

Concolic testing 과 AddressSanitizer를 사용한 메모리 에러 검출

개요

준비물

수행내용

'Testing Tools' Related Articles

티스토리툴바