本文架构
- 1. 动机
- 2.KLEE简介
- 3.KLEE的代码工程结构
- 4. 从KLEE主函数入手
- main函数
- step1: 初始化
- step2：加载.bc文件
- 进行符号执行
- 读取测试用例
- 输出日志信息
1. 动机
最近准备对KLEE进行修改使其符合我的需要，因此免不了需要对源码进行修改。读懂源码是对在其进行修改之前的必经之路。但其工程量巨大，该如何下手呢？
于是我将阅读源码过程中所得分享出来，希望能为同样学习KLEE的同行之人提供一些参考。内容可能写的存在纰漏，还请大家及时指出，不吝赐教。
程序分析-klee工具分析
符号执行, KLEE 与 LLVM
2.KLEE简介
KLEE（可读作“克利”）是一个基于符号执行的自动化测试工具，旨在帮助发现软件中的错误和漏洞。该工具可以用于分析 C/C++ 程序，并生成能够触发程序错误路径的测试用例。KLEE的主要目标是执行程序的所有可能路径，而不仅仅是具体输入下的一条路径。通过符号执行技术，它能够在未提供具体输入的情况下模拟程序执行的各种路径，从而发现隐藏在程序中的潜在漏洞。
KLEE的核心思想是将程序中的输入视为符号（symbol），而不是具体的数值。这意味着在执行过程中，KLEE不会给定实际输入值，而是用符号代替输入，从而创建了一种执行路径的符号表示。然后，KLEE使用约束求解器来解决程序中各种条件语句的约束，以确定是否存在输入，能够导致程序执行到不同的路径上。
KLEE的工作流程可以分为几个主要步骤：
符号执行： KLEE通过对程序进行符号执行，以符号形式代表程序的输入和执行路径。在执行过程中，它记录了执行路径上的每个条件分支以及相应的约束条件。路径探索： KLEE使用路径探索技术来导航程序的不同执行路径。它会尝试通过不同的路径执行程序，并在执行过程中收集约束条件。约束求解： 在执行过程中，KLEE将收集到的约束条件传递给约束求解器，以确定是否存在一组输入能够满足这些约束条件。如果找到了满足条件的输入，那么就找到了一条可以导致特定程序路径执行的输入序列。测试用例生成： 当约束求解器找到满足条件的输入时，KLEE会生成相应的测试用例，并将其用于进一步的测试和验证。
KLEE的强大之处在于它能够自动化地发现程序中的潜在错误，例如内存泄漏、空指针解引用、整数溢出等。通过覆盖程序的多个执行路径，KLEE可以提高测试覆盖率，从而增加程序的健壮性和可靠性。
3.KLEE的代码工程结构
从【Github】KLEE: Symbolic Execution Engine下载KLEE的源代码。
git clone https://github.com/klee/klee.git
使用你电脑中的IDE（本文使用的是jetbrain公司的CLion）打开后可以看到其工程结构如下所示：
以弄懂其大致流程为目标导向，我们只需要关注其include和lib文件夹。
其中：
include文件夹包含了KLEE的所有接口信息，你可以在该文件下获取大部分KLEE的数据结构信息。lib文件夹包含了KLEE核心内容的具体实现，即我们需要阅读的大部分源码。将该文件夹展开还能进一步获取信息：
| 文件夹名 | 存放内容说明 |
|---|---|
lib/Basic | Low level support for both klee and kleaver which should be independent of LLVM. |
lib/Support | Higher level support, but only used by klee. This can use LLVM facilities. |
lib/Expr | The core kleaver expression library. |
lib/Solver | The kleaver solver library. |
lib/Module | klee facilities for working with LLVM modules, including the shadow module/instruction structures we use during execution. |
lib/Core | The core symbolic virtual machine. |
其中Core是我们最关心的内容，里面包含了对符号执行模拟器(Executor)、符号执行树(ExecutionTree)以及符号执行状态(ExecutionState)等关键概念的定义(.h)和实现(.cpp)。
|-- AddressSpace.cpp
|-- AddressSpace.h
|-- CallPathManager.cpp
|-- CallPathManager.h
|-- Context.cpp
|-- Context.h
|-- CoreStats.cpp
|-- CoreStats.h
|-- ExecutionState.cpp
|-- ExecutionState.h
|-- Executor.cpp
|-- Executor.h
|-- ExecutorUtil.cpp
|-- ExternalDispatcher.cpp
|-- ExternalDispatcher.h
|-- GetElementPtrTypeIterator.h
|-- ImpliedValue.cpp
|-- ImpliedValue.h
|-- Memory.cpp
|-- Memory.h
|-- MemoryManager.cpp
|-- MemoryManager.h
|-- MergeHandler.cpp
|-- MergeHandler.h
|-- PTree.cpp
|-- PTree.h
|-- Searcher.cpp
|-- Searcher.h
|-- SeedInfo.cpp
|-- SeedInfo.h
|-- SpecialFunctionHandler.cpp
|-- SpecialFunctionHandler.h
|-- StatsTracker.cpp
|-- StatsTracker.h
|-- TimingSolver.cpp
|-- TimingSolver.h
|-- UserSearcher.cpp
|-- UserSearcher.h
但大家也可以看见，内容过多，虽然去除头文件但依然还有十几个文件。回想当初学习C语言时，面对繁多的函数定义，我们要了解一个程序的执行流程（基本执行思路）时，都是从主函数入手的。这给我们提供了一个有益的思路：从主函数开始我们的阅读！
当然，也有的文章直接从core下的文件入手，这里给供大家参考吧~
【安全客Blog】KLEE 源码阅读笔记
4. 从KLEE主函数入手
KLEE的主函数并不在我们上述的重要工程目录中。它位于tool/klee/main.cpp中我们点开这个文件后可以发现：（这TM也有近两千行代码~）。一点开Structure，五花八门的函数定义和结构体定义。
但！没关系，我们关注的只有main函数！(大概位于1200行左右，由于我添加了注释所以跟原始的可能有偏差)
main函数
让我们看看主函数主要做了什么。
step1: 初始化
- step1: 初始化加载各种初始环境
- step2: 调用
parseArguments()分析你在命令行中对KLEE做出的配置。 - step3: 设置异常处理函数
SetInterruptFunction()
KCommandLine::KeepOnlyCategories(
{&ChecksCat, ... &ExecTreeCat});
llvm::InitializeNativeTarget();//初始化环境
parseArguments(argc, argv);//分析传入的命令行参数
..
//设置异常处理函数
// 会报一些错
sys::SetInterruptFunction(interrupt_handle);
step2：加载.bc文件
现在开始加载.bc字节码文件进行符号分析
int main(int argc, char **argv, char **envp)
// Load the bytecode...
// 加载字节码
std::string errorMsg;
LLVMContext ctx;
...
std::vector<std::unique_ptr<llvm::Module>> loadedModules;
/**
* loadFile 需要解析bc文件，bc文件是一个整体运行单元
*/
if (!klee::loadFile(InputFile, ctx, loadedModules, errorMsg)) {
klee_error("error loading program '%s': %s", InputFile.c_str(),
errorMsg.c_str());
}
// linkModule 将bc文件中的module合并为一个整体的module
std::unique_ptr<llvm::Module> M(klee::linkModules(
loadedModules,
"" /* link all modules together */,
errorMsg));
if (!M) {//链接错误的话，报错
klee_error("error loading program '%s': %s", InputFile.c_str(),
errorMsg.c_str());
}
//链接完成，返回mainModule
llvm::Module *mainModule = M.get();
...
// 将这个module作为第一个项
// Push the module as the first entry
loadedModules.emplace_back(std::move(M));
std::string LibraryDir = KleeHandler::getRunTimeLibraryPath(argv[0]);
//配置module基本信息
Interpreter::ModuleOptions Opts(LibraryDir.c_str(), EntryPoint, opt_suffix,
/*Optimize=*/OptimizeModule,
/*CheckDivZero=*/CheckDivZero,
/*CheckOvershift=*/CheckOvershift);
// 遍历已经加载完毕的modules，以找到主函数main
for (auto &module : loadedModules) {
mainFn = module->getFunction("main");
if (mainFn)
break;
}
// 找到入口点
if (EntryPoint.empty())
klee_error("entry-point cannot be empty");
// 找到入口函数
for (auto &module : loadedModules) {
entryFn = module->getFunction(EntryPoint);
if (entryFn)
break;
}
if (!entryFn)
klee_error("Entry function '%s' not found in module.", EntryPoint.c_str());
//如果设置了POSIX运行时环境
if (WithPOSIXRuntime) {
...
}
// 如果设置了UBSan运行时
if (WithUBSanRuntime) {
...
}
// 如果设置了libcxx
if (Libcxx) {
...
}
// gen
switch (Libc) {
..
}
// 检查是否成功加载字节码库
for (const auto &library : LinkLibraries) {
if (!klee::loadFile(library, mainModule->getContext(), loadedModules,
errorMsg))
klee_error("error loading bitcode library '%s': %s", library.c_str(),
errorMsg.c_str());
}
int pArgc;
char **pArgv;
char **pEnvp;
//如果设置了Environ 环境
if (Environ != "") {
std::vector<std::string> items;
// 打开环境配置信息
std::ifstream f(Environ.c_str());
if (!f.good())
klee_error("unable to open --environ file: %s", Environ.c_str());
//读取环境配置文件
while (!f.eof()) {
std::string line;
std::getline(f, line);
line = strip(line);
if (!line.empty())
items.push_back(line);
}//end of the while(!f.eif())
f.close();//关闭文件
pEnvp = new char *[items.size()+1];
unsigned i=0;
for (; i != items.size(); ++i)
pEnvp[i] = strdup(items[i].c_str());
pEnvp[i] = 0;
} else {
pEnvp = envp;
}
pArgc = InputArgv.size() + 1;
pArgv = new char *[pArgc];
for (unsigned i=0; i<InputArgv.size()+1; i++) {
std::string &arg = (i==0 ? InputFile : InputArgv[i-1]);
unsigned size = arg.size() + 1;
char *pArg = new char[size];
std::copy(arg.begin(), arg.end(), pArg);
pArg[size - 1] = 0;
pArgv[i] = pArg;
}//end of for
进行符号执行
Interpreter是进行符号执行的重要部件
Interpreter::InterpreterOptions IOpts;
IOpts.MakeConcreteSymbolic = MakeConcreteSymbolic;
KleeHandler *handler = new KleeHandler(pArgc, pArgv);
Interpreter *interpreter =
theInterpreter = Interpreter::create(ctx, IOpts, handler);
// 条件为假则终止程序继续执行
assert(interpreter);
handler->setInterpreter(interpreter);
//输出详细信息(info)
for (int i = 0; i < argc; i++)
//逐个输出你刚才设置的命令行参数
handler->getInfoStream() << argv[i] << (i + 1 < argc ? " " : "\n");
handler->getInfoStream() << "PID: " << getpid() << "\n";
// 最终的module
// Get the desired main function. klee_main initializes uClibc
// locale and other data and then calls main.
auto finalModule = interpreter->setModule(loadedModules, Opts);
entryFn = finalModule->getFunction(EntryPoint);
if (!entryFn)
klee_error("Entry function '%s' not found in module.", EntryPoint.c_str());
externalsAndGlobalsCheck(finalModule);
//重放路径
std::vector<bool> replayPath;
if (!ReplayPathFile.empty()) {
//加载重放路径文件
KleeHandler::loadPathFile(ReplayPathFile, replayPath);
interpreter->setReplayPath(&replayPath);
}
// 这一部分也是打印到日志info里面
// 开始时间
auto startTime = std::time(nullptr);
{ // output clock info and start time
std::stringstream startInfo;
startInfo << time::getClockInfo()
<< "Started: "
<< std::put_time(std::localtime(&startTime), "%Y-%m-%d %H:%M:%S") << '\n';
handler->getInfoStream() << startInfo.str();
handler->getInfoStream().flush();
// 输出到info文件中
}
读取测试用例
// 读取用例文件
if (!ReplayKTestDir.empty() || !ReplayKTestFile.empty()) {
assert(SeedOutFile.empty());
assert(SeedOutDir.empty());
std::vector<std::string> kTestFiles = ReplayKTestFile;
for (std::vector<std::string>::iterator
it = ReplayKTestDir.begin(), ie = ReplayKTestDir.end();
it != ie; ++it)
KleeHandler::getKTestFilesInDir(*it, kTestFiles);
std::vector<KTest*> kTests;
for (std::vector<std::string>::iterator
it = kTestFiles.begin(), ie = kTestFiles.end();
it != ie; ++it) {
KTest *out = kTest_fromFile(it->c_str());
if (out) {
kTests.push_back(out);
} else {
klee_warning("unable to open: %s\n", (*it).c_str());
}
}
if (RunInDir != "") {
int res = chdir(RunInDir.c_str());
if (res < 0) {
klee_error("Unable to change directory to: %s - %s", RunInDir.c_str(),
sys::StrError(errno).c_str());
}
}
unsigned i=0;
for (std::vector<KTest*>::iterator
it = kTests.begin(), ie = kTests.end();
it != ie; ++it) {
KTest *out = *it;
interpreter->setReplayKTest(out);
llvm::errs() << "KLEE: replaying: " << *it << " (" << kTest_numBytes(out)
<< " bytes)"
<< " (" << ++i << "/" << kTestFiles.size() << ")\n";
// XXX should put envp in .ktest ?
interpreter->runFunctionAsMain(entryFn, out->numArgs, out->args, pEnvp);
if (interrupted) break;
}//end of for
interpreter->setReplayKTest(0);
//当测试用例不为空
while (!kTests.empty()) {
kTest_free(kTests.back());
kTests.pop_back();
}
}
//当replay路径为空时，从SeedOutFile中读取用例生成种子
else {
std::vector<KTest *> seeds;
for (std::vector<std::string>::iterator
it = SeedOutFile.begin(), ie = SeedOutFile.end();
it != ie; ++it) {
KTest *out = kTest_fromFile(it->c_str());
if (!out) {
klee_error("unable to open: %s\n", (*it).c_str());
}
seeds.push_back(out);
}
//输入测试用例
for (std::vector<std::string>::iterator
it = SeedOutDir.begin(), ie = SeedOutDir.end();
it != ie; ++it) {
std::vector<std::string> kTestFiles;
KleeHandler::getKTestFilesInDir(*it, kTestFiles);
for (std::vector<std::string>::iterator
it2 = kTestFiles.begin(), ie = kTestFiles.end();
it2 != ie; ++it2) {
//从文件中读取用例
KTest *out = kTest_fromFile(it2->c_str());
if (!out) {
klee_error("unable to open: %s\n", (*it2).c_str());
}
// 将out加入用例队列
seeds.push_back(out);
}
// kTest是一种记录程序执行路径的文件格式，文件包含了程序
// 执行结束时的状态信息，如寄存器值、内存的内容等
if (kTestFiles.empty()) {
klee_error("seeds directory is empty: %s\n", (*it).c_str());
}
}
// 如果存在测试用例,开始使用其进行测试
if (!seeds.empty()) {
klee_message("KLEE: using %lu seeds\n", seeds.size());
interpreter->useSeeds(&seeds);
}// end of if
if (RunInDir != "") {
int res = chdir(RunInDir.c_str());
if (res < 0) {
klee_error("Unable to change directory to: %s - %s",
RunInDir.c_str(),
sys::StrError(errno).c_str());
}
}// end of if
interpreter->runFunctionAsMain(entryFn, pArgc, pArgv, pEnvp);
// 释放种子
while (!seeds.empty()) {
// 释放最后一个队列中的最后一个用例
kTest_free(seeds.back());
seeds.pop_back();
}
}
输出日志信息
// 结束时间，计算测试执行时间。输出日志信息
auto endTime = std::time(nullptr);
{ // output end and elapsed time
std::uint32_t h;
std::uint8_t m, s;
std::tie(h,m,s) = time::seconds(endTime - startTime).toHMS();
std::stringstream endInfo;
endInfo << "Finished: "
<< std::put_time(std::localtime(&endTime), "%Y-%m-%d %H:%M:%S") << '\n'
<< "Elapsed: "
<< std::setfill('0') << std::setw(2) << h
<< ':'
<< std::setfill('0') << std::setw(2) << +m
<< ':'
<< std::setfill('0') << std::setw(2) << +s
<< '\n';
handler->getInfoStream() << endInfo.str();
handler->getInfoStream().flush();
}
// 释放所有参数
// Free all the args.
for (unsigned i=0; i<InputArgv.size()+1; i++)
//释放数组
delete[] pArgv[i];
delete[] pArgv;
delete interpreter;
// 获取统计信息
uint64_t queries =
*theStatisticManager->getStatisticByName("SolverQueries");
...
uint64_t forks =
*theStatisticManager->getStatisticByName("Forks");
handler->getInfoStream()
<< "KLEE: done: explored paths = " << 1 + forks << "\n";
// Write some extra information in the info file which users won't
// necessarily care about or understand.?
// 查询的相关信息，这的结果体现在info文件中
if (queries)
handler->getInfoStream()
<< "KLEE: done: avg. constructs per query = "
<< queryConstructs / queries << "\n";
handler->getInfoStream()
<< "KLEE: done: total queries = " << queries << "\n"
<< "KLEE: done: valid queries = " << queriesValid << "\n"
<< "KLEE: done: invalid queries = " << queriesInvalid << "\n"
<< "KLEE: done: query cex = " << queryCounterexamples << "\n";
// 一些统计的信息
std::stringstream stats;
stats << '\n'
<< "KLEE: done: total instructions = " << instructions << '\n'
<< "KLEE: done: completed paths = " << handler->getNumPathsCompleted()
<< '\n'
<< "KLEE: done: partially completed paths = "
<< handler->getNumPathsExplored() - handler->getNumPathsCompleted()
<< '\n'
<< "KLEE: done: generated tests = " << handler->getNumTestCases()
<< '\n';
return 0;
}
这一部分也就对应我们测试后生成的info文件中的内容
几个月前学习时写的草稿，若有错误和不足，还望不吝赐教。
![[实战]推流服务SRS安装](https://i-blog.csdnimg.cn/direct/66deda12253e4d0e9559ce1221108c05.png)
