KLEE를 사용하여 GNU Coreutils를 테스트하는 방법에 대한 튜토리얼
더 자세한 KLEE 사용 설명으로, OSDI’08 Coreutils 실험 설명에 따라 KLEE를 사용하여 GNU Coreutils를 테스트하는 방법을 살펴보겠다.
본 튜토리얼은 uClibc 및 POSIX 런타임 지원과 함께 구성 및 빌드된 KLEE로 가정한다.
모든 테스트는 64비트 리눅스 머신에서 수행되었다.
1단계: gcov와 함께 coreutils 빌드하기
먼저 coreutils 소스를 다운로드하고 압축을 해제한다.
이 예시에서는 OSDI 논문에서 사용된 버전보다 높은 8.32 버전을 사용하지만, Coreutils의 어떤 버전이든지 간에 상관없다.
그러나 최근 버전의 경우, make -C src arch hostname 단계를 건너뛸 수 있다. (8.32 버전에서도 이 단계가 생략되었음)
LLVM으로 빌드하기 전에 gcov 지원이 있는 coreutils 버전을 먼저 빌드해보자.
이후에 KLEE에서 생성한 테스트 케이스의 커버리지 정보를 얻는 데 사용할 것이다.
coreutils 디렉토리 안에서 우리는 하위 디렉토리(obj-gcov)에서 일반적인 구성 및 빌드 단계를 진행할 것이다.
단계는 다음과 같다:
coreutils-8.32$ mkdir obj-gcov coreutils-8.32$ cd obj-gcov obj-gcov$ ../configure --disable-nls CFLAGS="-g -fprofile-arcs -ftest-coverage" ... verify that configure worked ... obj-gcov$ make -j4
-disable-nls 옵션을 사용하여 빌드하는 이유는 이것이 C 라이브러리에 더욱더 많은 초기화를 추가하기 때문이다.
KLEE가 실행할 실행 파일은 아니지만, KLEE가 생성하는 테스트 케이스가 기계어 코드가 없는 이진 파일에서 올바르게 작동할 가능성을 높이기 위해 동일한 컴파일러 플래그를 사용하려고 한다.
이제 objc-gcov/src 디렉토리에 coreutils 세트가 있을 것이다.
예를 들어:
obj-gcov$ cd src obj-gcov/src$ ls -l ls echo cat -rwxr-xr-x 1 ubuntu ubuntu 173208 Nov 12 06:36 cat -rwxr-xr-x 1 ubuntu ubuntu 146720 Nov 12 06:36 echo -rwxr-xr-x 1 ubuntu ubuntu 583632 Nov 12 06:36 ls obj-gcov/src$ ./cat --version cat (GNU coreutils) 8.32 Copyright (C) 2020 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later <https://gnu.org/licenses/gpl.html>. This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. Written by Torbjorn Granlund and Richard M. Stallman.
추가로, 이러한 실행 파일은 gcov 지원을 사용하여 빌드되어야 한다.
따라서 실행 파일 중 하나를 실행하면 현재 디렉터리에 .gcda 파일이 생성된다.
이 파일에는 프로그램 실행 시 실행된 코드에 대한 정확한 정보가 포함되어 있다.
자세한 내용은 Gcov 문서를 참조하길 바란다.
우리는 gcov 도구 자체를 사용하여 커버리지 정보의 인간이 읽을 수 있는 형태를 생성할 수 있다.
이를 테면:
src$ rm -f *.gcda # 남아 있는 gcov 파일 제거 src$ ./echo** src$ ls -l echo.gcda -rw-r--r-- 1 ubuntu ubuntu 640 Nov 12 06:53 echo.gcda src$ gcov echo File '../src/echo.c' Lines executed:21.85% of 119 Creating 'echo.c.gcov' Cannot open source file ../src/echo.c File '../src/system.h' Lines executed:0.00% of 15 Creating 'system.h.gcov' Cannot open source file ../src/system.h Lines executed:19.40% of 134
기본적으로 gcov는 프로그램에서 실행된 라인 수를 보여준다.
(.h 헤더파일에는 echo.c로 컴파일된 코드가 포함되어 있음)
2단계: WLLVM 설치하기
KLEE를 사용하여 실제 소프트웨어를 테스트하는 어려운 부분 중 하나는 최종 프로그램이 LLVM bitCode파일이 되고 네이티브 이진 파일이 아니어야 한다는 것이다.
소프트웨어의 빌드 시스템은 ‘ar’, ‘libtool’ 및 ‘ld’와 같은 도구를 사용할 수 있으며
이러한 도구는 일반적으로 LLVM bitCode 파일을 이해하지 못한다.
Coreutils의 경우, 우리는 전체 프로그램 LLVM 비트코드 파일을 빌드하기 위한 도구인 whole-program-llvm (WLLVM)을 사용한다.
WLLVM에는 4가지 파이썬 실행 파일이 포함되어 있다.
wllvm은 C 컴파일러이고, wllvm++은 C++ 컴파일러이며, bitCode를 빌드 제품(오브젝트 파일, 실행 파일, 라이브러리 또는 아카이브)에서 추출하는 도구인 extract-bc 및 설정 오버사이트를 감지하는 wllvm-sanity-checker도 포함된다.
이 튜토리얼에서는 WLLVM 버전 1.3.1(2023.11.12 기준 최신버전)을 사용한다.
whole-program-llvm을 설치하는 가장 간단한 방법은 pip3를 사용하는 것이다.
$ pip3 install --upgrade wllvm
WLLVM을 성공적으로 실행하려면, 환경 변수 LLVM_COMPILER를 기본 LLVM 컴파일러 (dragonegg 또는 clang)로 설정해야 한다.
이 튜토리얼에서는 clang을 사용한다.
$ export LLVM_COMPILER=clang
환경 변수를 영구적으로 설정하고 싶다면,
해당 환경 변수를 쉘 프로파일(ex: .bashrc)에 추가시키면 된다.
3단계: LLVM을 사용하여 Coreutils 빌드하기
이전과 마찬가지로, 네이티브 실행 파일과 LLVM 버전에 쉽게 액세스할 수 있도록 별도의 디렉토리에서 빌드할 것이다.
해당 단계는 다음과 같다.
coreutils-8.32$ mkdir obj-llvm coreutils-8.32$ cd obj-llvm obj-llvm$ CC=wllvm ../configure --disable-nls CFLAGS="-g -O1 -Xclang -disable-llvm-passes -D__NO_STRING_INLINES -D_FORTIFY_SOURCE=0 -U__OPTIMIZE__" ... verify that configure worked ... obj-llvm$ make -j4 ... verify that make worked ...
주목해야될 2가지 변경사항이 있다.
첫째, KLEE를 사용하여 테스트할 이진 파일에 gcov instrumentation을 추가하고 싶지 않아서 -fprofile-arcs -ftest-coverage 플래그를 뺐다.
두번째로, CFLAGS에 -O1 -Xclang -disable-llvm-passes 플래그를 추가시켰다.
이것은 -O0을 추가하는 것과 유사하지만, LLVM 5.0 이후에는 -O0으로 컴파일하면 KLEE가 자체 최적화를 수행하지 못하게 만든다. (이후에 우리가 수행할 것).
따라서 우리는 -O1로 컴파일하지만, 명시적으로 모든 최적화를 비활성화한다.
자세한 내용은 이 문제점을 참고하길 바란다.
O0 -Xclang -disable-O0-optnone를 사용할 수도 있지만 나중에 최적화를 수행할 것이므로 -O1 -Xclang -disable-llvm-passes로 컴파일하는 것이 더 나은 선택이다.
-O1 버전은 최적화에 더 적합한 비트코드를 생성하므로 이 경우에는 그것(-O1)을 더 선호한다.
D__NO_STRING_INLINES -D_FORTIFY_SOURCE=0 -U__OPTIMIZE__는 또 다른 중요한 플래그 집합이다.
LLVM의 나중 버전에서 clang은 특정 라이브러리 함수의 안정적인 버전을 생성한다.
예를 들어, fprintf를 __fprintf_chk로 대체하는데, KLEE가 이를 모델링하지 않는다.
이것은 외부 함수로 처리되고 상태를 구체화시키게 되는데, 이로 인해 예상치 못한 결과가 발생할 수 있다.
모든 것이 잘 진행되었다면 이제 Coreutils 실행 파일이 있을 것이다.
예를 들면:
obj-llvm$ cd src src$ ls -l ls echo cat -rwxr-xr-x 1 ubuntu ubuntu 113544 Nov 12 07:28 cat -rwxr-xr-x 1 ubuntu ubuntu 92952 Nov 12 07:28 echo -rwxr-xr-x 1 ubuntu ubuntu 379776 Nov 12 07:28 ls src$ ./cat --version cat (GNU coreutils) 8.32 Copyright (C) 2020 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later <https://gnu.org/licenses/gpl.html>. This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. Written by Torbjorn Granlund and Richard M. Stallman.
LLVM 비트코드 파일 대신 실행 파일을 얻은 것을 알 수 있다.
이것은 WLLVM이 두 단계로 작동하기 때문이다.
첫 번째 단계에서 WLLVM은 표준 컴파일러를 호출하고 각 객체 파일에 대해 비트코드 컴파일러를 호출하여 LLVM 비트코드를 생성한다.
WLLVM은 생성된 비트코드 파일의 위치를 객체 파일의 특별한 섹션에 저장한다.
객체 파일이 함께 연결될 때, 위치는 모든 구성 파일의 위치를 저장하기 위해 연결된다.
빌드가 완료된 후, WLLVM 유틸리티인 extract-bc를 사용하여 특별한 섹션의 내용을 읽고 모든 비트코드를 단일 전체 프로그램 비트코드 파일로 연결할 수 있다.
모든 Coreutils의 LLVM 비트코드 버전을 얻기 위해, 모든 실행 파일을 extract-bc을 통해 호출할 수 있다.
src$ find . -executable -type f | xargs -I '{}' extract-bc '{}'
src$ ls -l ls.bc
-rw-r--r-- 1 ubuntu ubuntu 776796 Nov 12 08:09 ls.bc
4단계: KLEE를 인터프리터로 사용하기
KLEE의 핵심은 LLVM 비트코드의 인터프리터일 뿐이라는것.
이를 테면, 이전에 수행한 cat 명령을 KLEE를 사용하여 실행하는 방법은 다음과 같다.
참고로, 이 단계를 수행하려면 KLEE를 uClibc와 POSIX 런타임 지원으로 구성하고 빌드해야 한다. (만약 아직 하지 않았다면, 지금 그 작업을 수행해야 한다.. OTL 4번 과정인 (Optional) Build uclibc and the POSIX environment model 참고할 것)
src$ klee --libc=uclibc --posix-runtime ./cat.bc --version KLEE: NOTE: Using klee-uclibc : /usr/local/lib/klee/runtime/klee-uclibc.bca KLEE: NOTE: Using model: /usr/local/lib/klee/runtime/libkleeRuntimePOSIX.bca KLEE: output directory is "/home/klee/coreutils-6.11/obj-llvm/src/./klee-out-0" Using STP solver backend KLEE: WARNING ONCE: function "vasnprintf" has inline asm KLEE: WARNING: undefined reference to function: __ctype_b_loc KLEE: WARNING: undefined reference to function: klee_posix_prefer_cex KLEE: WARNING: executable has module level assembly (ignoring) KLEE: WARNING ONCE: calling external: syscall(16, 0, 21505, 42637408) KLEE: WARNING ONCE: calling __user_main with extra arguments. KLEE: WARNING ONCE: calling external: getpagesize() KLEE: WARNING ONCE: calling external: vprintf(43649760, 51466656) cat (GNU coreutils) 6.11 License GPLv3+: GNU GPL version 3 or later This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. Written by Torbjorn Granlund and Richard M. Stallman. Copyright (C) 2008 Free Software Foundation, Inc. KLEE: WARNING ONCE: calling close_stdout with extra arguments. KLEE: done: total instructions = 28988 KLEE: done: completed paths = 1 KLEE: done: generated tests = 1
이번에는 훨씬 더 많은 출력이 나왔다! 한번 살펴보도록 하자.
먼저 KLEE 명령어부터 말하자면, KLEE 명령줄의 일반적인 형태는 먼저 KLEE 자체의 인수, 그 다음에 실행할 LLVM 비트코드 파일(cat.bc), 그리고 애플리케이션에 전달할 인수들(–version이 이 경우에 해당)이 있다.
일반 네이티브 애플리케이션을 실행하면 C 라이브러리와 링크되었을 것이다.
하지만, 이 경우에는 KLEE가 LLVM 비트코드 파일을 직접 실행하고 있다.
KLEE가 효과적으로 작동하려면, 프로그램이 호출할 수 있는 모든 외부 함수에 대한 정의가 필요하다.
우리는 KLEE와 함께 사용하기 위해 uClibc C 라이브러리를 수정했다.
–libc=uclibc KLEE 인수는 KLEE에게 그 라이브러리를 로드하고 실행 전에 애플리케이션에 링크하도록 지시한다.
마찬가지로, 일반 네이티브 애플리케이션은 write()와 같은 낮은 수준의 기능을 제공하는 운영 체제 위에서 실행된다.
이러한 함수들에 대한 정의가 KLEE에도 필요하다.
KLEE와 uClibc 라이브러리와 함께 사용할 수 있는 POSIX 런타임을 제공하여 대부분의 명령행 애플리케이션에서 사용되는, 대부분의 운영 체제 기능을 제공한다.
–posix-runtime 인수는 KLEE에게 이 라이브러리도 링크하도록 지시한다.
이전과 같이 cat은 버전 정보를 출력한다. (이번에는 모든 텍스트가 출력됨).
하지만 이제는 KLEE가 추가로 여러 정보를 출력해준다.
이 경우 대부분의 이 경고는 무해하지만, 완전한 이해를 위해 이것이 무엇을 의미하는지 설명해보겠다.
- undefined reference to function: ___ctype_b_loc:
이 경고는 프로그램에 __ctype_b_loc 함수를 호출하는 부분이 있지만, 해당 함수가 어디에서도 정의되지 않았다는 것을 의미한다. (만약 uClibc와 POSIX 런타임을 링크하지 않았다면 이러한 경고가 훨씬 더 많이 나왔을 것이다).
프로그램이 실행되는 동안 이 함수를 호출하게 되면, KLEE가 이를 해석하지 못하고 프로그램을 종료할 수 있다. - executable has module level assembly (ignoring):
실행 파일에는 파일 레벨 인라인 어셈블리가 있는 파일이 포함되어 있는데, KLEE가 이를 이해할 수 없다는 것을 의미한다.
이 경우, 이것은 uClibc에서 나온 것이며 사용되지 않기 때문에 안전하다. - calling __user_main with extra arguments:
함수가 예상보다 더 많은 인수로 호출되었다는 것을 의미한다. 거의 항상 무해하다고 보면 되는데, 이 경우 __user_main은 사실상 cat의 main() 함수이며, uClibc와 링크할 때 KLEE가 이름을 바꾼다.
main()은 시작시 uClibc 자체에서 환경 포인터와 같은 추가적인 인수로 호출된다. - calling external: getpagesize():
프로그램에서 사용되지만, 정의되지 않은 함수를 KLEE가 호출하는 예를 의미한다. 이러한 경우 KLEE가 실제 함수를 호출하려고 시도한다.
그 함수가 프로그램 메모리 중 어떤 부분에도 쓰거나 심볼 값을 조작하지 않는 한, 이것은 때로는 안전할 수 있다.
예를 들어 getpagesize() 함수가 있는데, 이는 단순히 상수를 반환한다.
일반적으로 KLEE는 특정 경고를 한 번만 출력한다. 또한 이러한 경고는 KLEE 출력 디렉토리의 warnings.txt에도 기록된다.
5단계: 애플리케이션에 심볼릭 데이터를 소개하기
KLEE가 프로그램을 일반적으로 해석할 수 있음을 보았지만, KLEE의 실제 목적은 프로그램의 일부 입력을 심볼릭하게 만들어 프로그램을 보다 체계적으로 탐구하는 것이다.
예를 들어, echo 애플리케이션에서 KLEE를 실행해보겠다.
uClibc와 POSIX 런타임을 사용할 때, KLEE는 런타임 라이브러리 내에 제공되는 특별한 함수(klee_init_env)로 프로그램의 main() 함수를 대체한다.
이 함수는 애플리케이션의 일반적인 명령행 처리를 변경하며, 특히 심볼릭 인수를 생성하는 것을 지원한다.
예를 들어, –help를 전달하면 다음과 같은 결과가 나온다:
src$ klee --libc=uclibc --posix-runtime ./echo.bc --help
...
usage: (klee_init_env) [options] [program arguments]
-sym-arg <N> - Replace by a symbolic argument with length N
-sym-args <MIN> <MAX> <N> - Replace by at least MIN arguments and at most
MAX arguments, each with maximum length N
-sym-files <NUM> <N> - Make NUM symbolic files ('A', 'B', 'C', etc.),
each with size N
-sym-stdin <N> - Make stdin symbolic with size N.
-sym-stdout - Make stdout symbolic.
-max-fail <N> - Allow up to N injected failures
-fd-fail - Shortcut for '-max-fail 1'
...
예를 들어, 심볼릭한 3글자 인수를 사용하여 echo를 실행해보겠다.
src$ klee --libc=uclibc --posix-runtime ./echo.bc --sym-arg 3
KLEE: NOTE: Using klee-uclibc : /usr/local/lib/klee/runtime/klee-uclibc.bca
KLEE: NOTE: Using model: /usr/local/lib/klee/runtime/libkleeRuntimePOSIX.bca
KLEE: output directory is "/home/klee/coreutils-6.11/obj-llvm/src/./klee-out-1"
Using STP solver backend
KLEE: WARNING ONCE: function "vasnprintf" has inline asm
KLEE: WARNING: undefined reference to function: __ctype_b_loc
KLEE: WARNING: undefined reference to function: klee_posix_prefer_cex
KLEE: WARNING: executable has module level assembly (ignoring)
KLEE: WARNING ONCE: calling external: syscall(16, 0, 21505, 39407520)
KLEE: WARNING ONCE: calling __user_main with extra arguments.
..
KLEE: WARNING: calling close_stdout with extra arguments.
...
KLEE: WARNING ONCE: calling external: printf(42797984, 41639952)
..
KLEE: WARNING ONCE: calling external: vprintf(41640400, 52740448)
..
Echo the STRING(s) to standard output.
-n do not output the trailing newline
-e enable interpretation of backslash escapes
-E disable interpretation of backslash escapes (default)
--help display this help and exit
--version output version information and exit
Usage: ./echo.bc [OPTION]... [STRING]...
echo (GNU coreutils) 6.11
Copyright (C) 2008 Free Software Foundation, Inc.
If -e is in effect, the following sequences are recognized:
\\0NNN the character whose ASCII code is NNN (octal)
\\\\ backslash
\\a alert (BEL)
\\b backspace
License GPLv3+: GNU GPL version 3 or later
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
\\c suppress trailing newline
\\f form feed
\\n new line
\\r carriage return
\\t horizontal tab
\\v vertical tab
NOTE: your shell may have its own version of echo, which usually supersedes
the version described here. Please refer to your shell's documentation
for details about the options it supports.
Report bugs to <[email protected]>.
Written by FIXME unknown.
KLEE: done: total instructions = 64546
KLEE: done: completed paths = 25
KLEE: done: generated tests = 25
이곳의 결과는 조금 더 흥미로운데, KLEE는 프로그램을 통해 25개의 경로를 탐색해냈다.
모든 경로의 출력이 서로 섞여 있긴 하지만, 무작위 문자를 반복 출력하는 것뿐만 아니라 일부 텍스트 블록도 출력되었음을 알 수 있다.
coreutils의 echo가 일부 인수를 받는다는 것에 놀라실 텐데,
이 경우에는 –v(버전을 나타내는 –version의 줄임말)와 –h(도움말을 나타내는 –help의 줄임말) 옵션을 탐색한 경우이다.
KLEE의 내부 통계를 간단히 볼 수 있도록 출력 디렉토리에서 klee-stats를 실행하여 KLEE의 내부 통계의 간단한 요약을 얻을 수도 있다.
(참고: KLEE는 항상 가장 최근의 출력 디렉토리에 klee-last라는 심볼릭 링크를 생성함)
src$ klee-stats klee-last ------------------------------------------------------------------------ | Path | Instrs| Time(s)| ICov(%)| BCov(%)| ICount| TSolver(%)| ------------------------------------------------------------------------ |klee-last| 64546| 0.15| 22.07| 14.14| 19943| 62.97| ------------------------------------------------------------------------
여기서 ICov는 커버된 LLVM 명령어 백분율을 나타내며, BCov는 커버된 분기의 백분율을 의미한다.
백분율이 왜 이렇게 낮은지 궁금할 수 있다.
echo가 얼마나 더 많은 코드를 가질 수 있을까?
주된 이유는 이러한 숫자가 비트코드 파일의 모든 명령어나 분기를 사용하여 계산되기 때문이다.
이에는 실행되지 않을 수도 있는 많은 라이브러리 코드가 포함된다.
–optimize 옵션을 KLEE에 전달하여 이 문제 (또는 기타 문제)를 해결할 수 있다.
이 옵션은 KLEE가 실행하기 전에 비트코드 모듈에 대해 LLVM 최적화 패스를 실행하도록 하며 특히 dead code를 제거한다.
비트코드 파일을 사용할 때는 주로 이 플래그를 사용하는 것이 좋다.
다음은 –optimize를 활성화했을 때의 결과이다:
src$ klee --optimize --libc=uclibc --posix-runtime ./echo.bc --sym-arg 3 ... KLEE: done: total instructions = 33991 KLEE: done: completed paths = 25 KLEE: done: generated tests = 25 src$ klee-stats klee-last ------------------------------------------------------------------------ | Path | Instrs| Time(s)| ICov(%)| BCov(%)| ICount| TSolver(%)| ------------------------------------------------------------------------ |klee-last| 33991| 0.13| 30.16| 21.91| 8339| 80.66| ------------------------------------------------------------------------
이번에는 명령어 커버리지가 약 6% 정도 상승하였으며, KLEE가 더 빨리 실행되고 더 적은 명령어를 실행하는 것을 볼 수 있다.
나머지 코드의 대부분은 여전히 라이브러리 함수에 있으며, 최적화 프로그램이 제거하지 못하는 위치에 있다.
이를 확인하고 echo 내부에서 커버되지 않은 코드를 찾으려면,
KLEE 실행 결과를 시각화하기 위해 KCachegrind를 사용할 수 있다.
6단계: kcachegrind를 사용하여 KLEE의 진행 상황 시각화하기
KCachegrind는 valgrind의 callgrind 플러그인을 위해 작성된 훌륭한 프로파일링 시각화 도구이다.
이미 설치되어 있지 않다면, 현대적인 Linux 배포판에서는 일반적으로 플랫폼의 소프트웨어 설치 도구(예: apt-get 또는 yum)를 통해 쉽게 설치할 수 있다.
KLEE는 기본적으로 테스트 출력 디렉토리에 run.istats 파일을 작성하는데, 이 파일은 사실 KCachegrind 파일이다.
이 예제에서는 –optimize를 사용하지 않고 실행한 run.istats 파일이므로 결과를 더 쉽게 이해할 수 있을 것이다.
KCachegrind가 이미 설치되어 있으면 다음 명령을 실행하면 된다:
src$ kcachegrind klee-last/run.istats
KCachegrind를 열면 아래와 비슷한 창이 표시된다.
“Instructions” 통계가 선택되어 있는지 확인하기 위해 메뉴에서 “View” > “Primary Event Type” > “Instructions”를 선택하고, “Source Code” 뷰가 선택되어 있는지 확인해야 된다.
(아래 스크린샷에서 오른쪽 패널에 해당)
KCachegrind 자체가 복잡한 응용 프로그램이기에 관심 있는 사용자는 더 많은 정보와 문서를 위해 KCachegrind 웹사이트를 참조해야 한다.
그러나 기본적으로 한 패널은 “Flat Profile”을 보여주며, 이는 각 함수에서 실행된 명령어 수를 보여주는 목록이다.
“Self” 열은 함수 자체에서 실행된 명령어 수이며, “Incl” (포함) 열은 함수에서 실행된 명령어 수 또는 해당 함수가 호출한 함수 중 어느 것이나 실행한 명령어 수를 의미한다.
KLEE는 실행에 관한 여러 통계를 포함하고 있다.
관심 있는 통계로, “Uncovered Instructions” ← 이 통계를 선택하고,
함수 목록을 다시 정렬하면 다음과 같은 결과를 볼 수 있을 것이다:
대부분의 커버되지 않은 명령어가 우리가 예상한 대로 라이브러리 코드에 있음을 알 수 있다.
그러나 __user_main 함수를 선택하면 echo 자체 내에서 커버되지 않은 코드를 찾을 수 있다.
이 경우 대부분의 커버되지 않은 명령어는 do_v9 변수에 의해 보호되는 큰 if 문 내에 있다.
좀 더 살펴보면, 이것이 -e가 전달될 때 true로 설정되는 플래그임을 알 수 있다.
KLEE가 이 코드를 탐구하지 않은 이유는 우리가 하나의 심볼릭 인수만 전달했기 때문이다.
이 코드를 실행하려면 다음과 같은 명령줄이 필요하다.
$ echo -e \\a
실제로 KCachegrind 숫자를 해석하려는 경우,
이해해야 할 미묘한 점은 이 숫자가 모든 상태를 통합하여 누적된 이벤트를 포함한다는 것이다.
예를 들어 다음과 같은 코드를 고려해보면…
Line 1: a = 1;
Line 2: if (...)
Line 3: printf("hello\\n");
Line 4: b = c;
일반적인 응용 프로그램에서는 Line 1의 문장이 한 번만 실행되었다면, Line 4의 문장은 최대 한 번 실행될 수 있다.
그러나 KLEE가 응용 프로그램을 실행할 때는, Line 2에서 별도의 프로세스를 생성하고 분기할 수 있다.
이 경우, Line 4는 Line 1보다 더 많이 실행될 수 있다!
또 다른 유용한 정보가 있는데, KLEE는 실제 응용 프로그램이 실행되는 동안 주기적으로 run.istats 파일을 작성한다.
이는 긴 실행 시간을 가진 응용 프로그램의 상태를 모니터링하는 한 가지 방법을 제공한다.
(또 다른 방법은 klee-stats 도구를 사용하는 방법이 되겠다)
7단계: KLEE가 생성한 테스트 케이스를 다시 실행하기
잠시 KLEE에서 멀어져 KLEE가 생성한 테스트 케이스만 살펴보겠다.
klee-last 디렉토리 내부를 살펴보면 25개의 .ktest 파일이 있을 것이다.
src$ ls klee-last assembly.ll test000004.ktest test000012.ktest test000020.ktest info test000005.ktest test000013.ktest test000021.ktest messages.txt test000006.ktest test000014.ktest test000022.ktest run.istats test000007.ktest test000015.ktest test000023.ktest run.stats test000008.ktest test000016.ktest test000024.ktest test000001.ktest test000009.ktest test000017.ktest test000025.ktest test000002.ktest test000010.ktest test000018.ktest warnings.txt test000003.ktest test000011.ktest test000019.ktest
이러한 파일은 KLEE가 따랐던 경로를 재현하기 위해 심볼릭 데이터에 사용할 실제 값들을 포함하고 있다.
(코드 커버리지를 얻기 위한 것이든, 버그를 재현하기 위한 것이든)
또한 이 파일은 값을 추적하고 런타임 버전을 추적하기 위해 POSIX 런타임에서 생성한 추가적인 메타데이터를 포함한다.
ktest-tool을 사용하여 한 파일의 내용을 개별적으로 살펴볼 수 있다.
$ ktest-tool klee-last/test000001.ktest ktest file : 'klee-last/test000001.ktest' args : ['./echo.bc', '--sym-arg', '3'] num objects: 2 object 0: name: 'arg0' object 0: size: 4 object 0: data: '\\x00\\x00\\x00\\x00' object 1: name: 'model_version' object 1: size: 4 object 1: data: '\\x01\\x00\\x00\\x00'
이 경우, 이 테스트 케이스는 값 \x00\x00\x00\x00을 첫 번째 인수로 전달해야 함을 나타낸다.
그러나 .ktest 파일은 일반적으로 직접 확인하기 위한 것이 아니다.
POSIX 런타임을 위해 .ktest 파일을 읽고 KLEE가 따랐던 경로를 재현하는데 필요한 데이터를 자동으로 전달하는 도구인 klee-replay를 제공한다.
이 도구가 어떻게 작동하는지 보려면, 네이티브 실행 파일을 빌드한 디렉토리로 돌아가면 확인할 수 있다:
src$ cd .. obj-llvm$ cd .. coreutils-6.11$ cd obj-gcov obj-gcov$ cd src src$ ls -l echo -rwxrwxr-x 1 klee klee 135984 Nov 21 21:58 echo
klee-replay 도구를 사용하려면 실행할 실행 파일과 사용할 .ktest 파일을 지정하면 된다.
프로그램 인수, 입력 파일 등은 모두 .ktest 파일의 데이터를 기반으로 생성된다.
src$ klee-replay ./echo ../../obj-llvm/src/klee-last/test000001.ktest klee-replay: TEST CASE: ../../obj-llvm/src/klee-last/test000001.ktest klee-replay: ARGS: "./echo" "" klee-replay: EXIT STATUS: NORMAL (0 seconds)
여기서 첫 두 줄과 마지막 줄은 klee-replay 도구 자체에서 나온 것이다.
첫 두 줄은 실행 중인 테스트 케이스를 나열하고 응용 프로그램에 전달되는 인수의 구체적인 값들을 나타낸다.
(이전에 .ktest 파일에서 보았던 것과 일치함을 참고할 것)
마지막 줄은 프로그램의 종료 상태와 실행하는 데 걸린 시간을 나타낸다.
klee-replay 도구를 사용하여 여러 테스트 케이스를 하나씩 연이어 실행하도록 설정할 수도 있다.
이렇게 하여 gcov 커버리지를 klee-stats에서 얻은 숫자와 한번 비교해보자면…
src$ rm -f *.gcda # Get rid of any stale gcov files src$ klee-replay ./echo ../../obj-llvm/src/klee-last/*.ktest klee-replay: TEST CASE: ../../obj-llvm/src/klee-last/test000001.ktest klee-replay: ARGS: "./echo" "@@@" @@@ klee-replay: EXIT STATUS: NORMAL (0 seconds) _..._ klee-replay: TEST CASE: ../../obj-llvm/src/klee-last/test000022.ktest klee-replay: ARGS: "./echo" "--v" echo (GNU coreutils) 6.11 Copyright (C) 2008 Free Software Foundation, Inc. _..._ src$ gcov echo File '../../src/echo.c' Lines executed:52.43% of 103 Creating 'echo.c.gcov' File '../../src/system.h' Lines executed:100.00% of 3 Creating 'system.h.gcov'
여기서 echo.c의 숫자는 klee-stats 숫자보다 크게 나타난다.
이는 gcov가 한 파일의 라인만 고려하기 때문이며, 전체 응용 프로그램을 고려하지 않기 때문이다.
kcachegrind와 마찬가지로 gcov가 출력한 커버리지 파일을 검사하여 어떤 라인이 커버되었는지, 어떤 라인이 커버되지 않았는지 정확히 볼 수 있다.
여기 출력에서 일부분을 살펴보면…
-: 193: }
-: 194:
23: 195:just_echo:
-: 196:
23: 197: if (do_v9)
-: 198: {
10: 199: while (argc > 0)
-: 200: {
#####: 201: char const *s = argv[0];
-: 202: unsigned char c;
-: 203:
#####: 204: while ((c = *s++))
-: 205: {
#####: 206: if (c == '\\\\' && *s)
-: 207: {
#####: 208: switch (c = *s++)
-: 209: {
#####: 210: case 'a': c = '\\a'; break;
#####: 211: case 'b': c = '\\b'; break;
#####: 212: case 'c': exit (EXIT_SUCCESS);
#####: 213: case 'f': c = '\\f'; break;
#####: 214: case 'n': c = '\\n'; break;
가장 왼쪽 열은 각 라인이 실행된 횟수를 나타낸다.
–는 라인에 실행 가능한 코드가 없음을 의미하고, #####은 해당 라인이 커버되지 않았음을 의미한다.
여기 보듯이, 여기서 커버되지 않은 라인들은 정확히 kcachegrind에서 보고된 커버되지 않은 라인들과 일치한다.
더 복잡한 응용 프로그램을 테스트하기에 앞서 간단한 echo.c에 대한 양호한 커버리지를 얻을 수 있는지 확인해보겠다.
이전의 그 문제는 데이터를 충분히 심볼릭하게 만들지 않았기 때문인데, echo에 심볼릭 인수 두 개를 제공하면 프로그램 전체를 커버하는 데 충분해야 한다.
POSIX 런타임 –sym-args 옵션을 사용하여 여러 옵션을 전달할 수 있다.
다음은 obj-llvm/src 디렉토리로 다시 전환해서, 수행해야 할 단계이다:
src$ klee **--only-output-states-covering-new** **--optimize --libc=**uclibc **--posix-runtime** ./echo.bc **--sym-args** 0 2 4 ... KLEE: done: total instructions = 7611521 KLEE: done: completed paths = 10179 KLEE: done: generated tests = 57
-sym-args 옵션의 형식은 실제로 전달할 최소 및 최대 인수의 수와 각 인수에 사용할 길이를 지정한다.
이 경우 –sym-args 0 2 4는 0에서 2개의 인수(포함)를 전달하고, 각 인수의 최대 길이는 4자로 지정한다.
또한 KLEE 명령줄에 –only-output-states-covering-new 옵션을 추가시켰다.
기본적으로 KLEE는 탐색하는 모든 경로에 대한 테스트 케이스를 작성한다.
프로그램이 커질수록 이 옵션은 덜 유용해지는데, 이러한 이유는 많은 테스트 케이스가 동일한 경로를 탐색하게 되며 각각을 계산하거나(또는 다시 실행)하는 것은 시간 낭비가 되기 때문이다.
이 옵션을 사용하면 KLEE에게 코드에서 새로운 명령어를 커버하거나 오류를 만나는 경로에 대해서만 테스트 케이스를 작성하도록 지시한다.
출력의 마지막 줄에서 볼 수 있듯이, KLEE는 코드를 거의 10,000개의 경로를 탐색했지만, 57개의 테스트 케이스만 작성해야 했다.
obj-gcov/src 디렉토리로 돌아가서 가장 최신의 테스트 케이스 세트를 다시 실행하면, 이제 echo.c에 대한 합리적인 커버리지를 얻을 수 있다:
src$ rm -f *.gcda # Get rid of any stale gcov files src$ klee-replay ./echo ../../obj-llvm/src/klee-last/*.ktest klee-replay: TEST CASE: ../../obj-llvm/src/klee-last/test000001.ktest klee-replay: ARGS: "./echo" ... src$ gcov echo File '../../src/echo.c' Lines executed:97.09% of 103 Creating 'echo.c.gcov' File '../../src/system.h' Lines executed:100.00% of 3 Creating 'system.h.gcov'
완벽한 100% 라인 커버리지를 얻지 못한 이유에 대한 설명은 독자에게 의문을 남기고 가겠다.
8단계: 커버리지 분석을 위해 zcov 도구 사용하기
커버리지 결과를 시각화하기 위해 zcov 도구를 사용할 수도 있다.
출처 및 번역
https://klee.github.io/tutorials/testing-coreutils/
