# KLEE 筆記
###### tags: `資安`

[toc]

Paper: [KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs](https://llvm.org/pubs/2008-12-OSDI-KLEE.pdf)
> 之後有空再看

---

## 教學

- [Try KLEE for Yourself](http://klee.github.io/tutorials/)
- [KLEE学习笔记](https://blog.csdn.net/u013648063/article/details/109548600)

## code

範例

#include <klee/klee.h>

int get_sign(int number)
{
    ...
}

int main() {
  int a;
  klee_make_symbolic(&a, sizeof(a), "a");
  return get_sign(a);
}

- `klee_make_symbolic` 建立 KLEE 的符號
- `klee_assume` 建立約束 (如 `klee_assume(re[SIZE-1] == '\0' & re[0] == '^')`)，注意使用的是 `&`, `|` 而非 `&&`, `||`

## 編譯

clang -I ../../include -emit-llvm -c -g -O0 -Xclang -disable-O0-optnone get_sign.c

以上會產生 `get_sign.bc` 文件

- `-I ...` 把 klee.h 引入到編譯中
- `-emit-llvm` 產生 bitcode
- `-c` 只跑前處理、編譯、組譯，不跑鏈結之類的
- `-g` 加上 debug info
- `-O0 -Xclang -disable-O0-optnone` 關掉優化

### wllvm

另一種產生 bitcode 的方式是使用 wllvm，通常會用在測試大型專案，指令如下

wllvm -g -O0 -Xclang -disable-O0-optnone get_sign.c

指令與上面類似，但是不需要 `-emit-llvm` 和 `-c` 選項 (而通常專案中也不會有 klee library，所以一般不會需要 `-I ../../include` 選項)

跑出來會產生執行檔，但是含有 `bitcode` 的 header，可以用 `extract-bc` 工具取出裡面的 bitcode

extract-bc get_sign

另外如果有要進行路徑覆蓋率的優化的話，不能用 `O0` 選項，而會需要改成以下參數

`-g -O1 -Xclang -disable-llvm-passes -D__NO_STRING_INLINES -D_FORTIFY_SOURCE=0 -U__OPTIMIZE__`

- `-O1 -Xclang -disable-llvm-passes` 在 O1 下需要關的優化選項
- `-D__NO_STRING_INLINES -D_FORTIFY_SOURCE=0 -U__OPTIMIZE__` 避免一些安全性上更改函數而 klee 辨識不出的問題

## 執行

klee [--only-output-states-covering-new] get_sign.bc

輸出的相關測試會在 `klee-last/` 資料夾

- `--only-output-states-covering-new` 只輸出會有不同狀態的測試
- `--optimize` 優化路徑覆蓋率的選項，可能需要在產生 bytecode 的地方使用 `O1` 而非 `O0` 最佳化選項

### 動態輸入變數執行

如遇檔案、stdin、argv 等，可以搭配 `-posix-runtime` KLEE 選項及 `-sym-arg` 等檔案選項進行爆破，可參考[這裡](http://klee.github.io/docs/options/#symbolic-environment)

klee -posix-runtime password.bc -sym-arg <N> #只有單一 arg，爆破長度為 N
klee -posix-runtime password.bc -sym-args <MIN> <MAX> <N> #有 MIN ~ MAX 個 arg，個別爆破長度為 N
klee -posix-runtime password.bc -sym-stdin <N> #爆破 stdin，爆破長度為 N bytes
klee -posix-runtime password.bc -sym-files <FILE> <NUM> <N> #產生檔案 <NUM> 個 <FILE> 檔案，爆破長度為 N bytes

另外如果有用到一些 libc 函數如 `strcmp` 等，需要在 klee 參數再加入 `--libc=uclibc` 選項執行，詳見下方[坑/strcmp 與 argv](#strcmp-與-argv)

## 查看測試

ktest-tool klee-last/xxx.ktest

## Replay
### KLEE_FILE

:::warning
在[動態輸入變數執行](#動態輸入變數執行)部分產生出來的 ktest 似乎無法用 KTEST_FILE 的方式 replay，待確認是否有其他方法

> [time=Tue, Apr 11, 2023 1:21 AM]
> 經測試發現可以使用 `klee-replay` 的方式正常進行 replay
> 
:::

先編譯

gcc -I ../../include -L ~/klee_build/lib/ get_sign.c -lkleeRuntest

輸出 `a.out`

執行:

KTEST_FILE=klee-last/xxx.ktest ./a.out
echo $?

觀察執行狀態碼

### klee-replay

另一種 replay 的方式是使用 `klee-replay` 進行 replay，適合多次性的批次任務

首先先執行上面的編譯任務後，執行以下程式碼進行 replay

klee-replay a.out klee-last/test000001.ktest

後面改成 `klee-last/*.ktest` 即可變成多檔案 replay

## 觀察路徑覆蓋
### 觀察路徑覆蓋率

在一般單純只是要查看路徑覆蓋率的話，可以使用 `klee-stats` 工具查看

klee-stats klee-last

注意這邊只要給資料夾作為工具的參數即可

### kacahegrind

如果需要進一步查看路徑覆蓋的情況的話，可以使用 `kcachegrind` 工具，相關 docker 安裝可以查看這篇我寫的安裝教學文: [KLEE 的魔法之旅 — 在 KLEE docker 版本中安裝及使用 kcachegrind](https://medium.com/@frank1314168/klee-的魔法之旅-在-klee-docker-版本中安裝及使用-kcachegrind-83a947dad5cb) ~~偷偷葉配一下~~ ~~雖然應該只有我會看這篇筆記啦 :D~~

kcachegrind klee-last/run.istats

### gcov

而如果不想要使用 GUI 工具的話，也可以使用 `gcov` 工具，不過較為繁瑣

首先需要編譯出可以統計覆蓋率的 binary

clang -g -fprofile-arcs -ftest-coverage password.c

無論是用 `klee-replay` 或是手動的方式執行該 binary 後，會生成出 `.gcda` 檔案，用以讓 gcov 進行統計 (:star:所以每次重新統計時要記得刪掉該檔案)

gcov a.out

執行後生成 `a.out.gcov` 檔案，直接用文字編輯器打開即可看到統計結果


其中的 `#####` 就是沒有被覆蓋到的意思

## 坑
### strcmp 與 argv

在用 strcmp 比較輸入字串的程式，如果使用[動態輸入變數執行](#動態輸入變數執行)的話 (如 argv)，似乎無法成功爆破路徑

程式碼:

#include <stdio.h>
#include <string.h>

int check_password(char *buf) {
  if(strcmp(buf, "password") == 0)
    return 1;
  return 0;
}

int main(int argc, char **argv) {
  if (argc < 2)
     return 1;
  
  if (check_password(argv[1])) {
    printf("Password found!\n");
    printf("Password: %s\n", argv[1]);
    return 0;
  }

  return 1;
}

執行結果:


> [time=Tue, Apr 11, 2023 1:16 AM]
> 經進一步測試發現在執行 klee 時加入 `--libc=uclibc` 選項即可正常運行
>