From 3629e3ef0fc999ba9c1e0f43db061bdcc875d735 Mon Sep 17 00:00:00 2001 From: Julian Büning Date: Sat, 27 Oct 2018 22:14:50 +0200 Subject: implement FunctionAliasPass --- lib/Module/CMakeLists.txt | 1 + lib/Module/FunctionAlias.cpp | 246 +++++++++++++++++++++++++++++++++++++ lib/Module/KModule.cpp | 1 + lib/Module/Passes.h | 18 +++ test/Feature/FunctionAlias.c | 89 ++++++++++++++ test/Feature/FunctionAliasExit.c | 31 +++++ test/Feature/FunctionAliasVarArg.c | 58 +++++++++ 7 files changed, 444 insertions(+) create mode 100644 lib/Module/FunctionAlias.cpp create mode 100644 test/Feature/FunctionAlias.c create mode 100644 test/Feature/FunctionAliasExit.c create mode 100644 test/Feature/FunctionAliasVarArg.c diff --git a/lib/Module/CMakeLists.txt b/lib/Module/CMakeLists.txt index 5f234237..f78575fb 100644 --- a/lib/Module/CMakeLists.txt +++ b/lib/Module/CMakeLists.txt @@ -8,6 +8,7 @@ #===------------------------------------------------------------------------===# set(KLEE_MODULE_COMPONENT_SRCS Checks.cpp + FunctionAlias.cpp InstructionInfoTable.cpp InstructionOperandTypeCheckPass.cpp IntrinsicCleaner.cpp diff --git a/lib/Module/FunctionAlias.cpp b/lib/Module/FunctionAlias.cpp new file mode 100644 index 00000000..83b763f7 --- /dev/null +++ b/lib/Module/FunctionAlias.cpp @@ -0,0 +1,246 @@ +//===-- FunctionAliasPass.cpp -----------------------------------*- C++ -*-===// +// +// The KLEE Symbolic Virtual Machine +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "Passes.h" +#include "klee/Internal/Support/ErrorHandling.h" +#include "klee/OptionCategories.h" + +#include "llvm/IR/GlobalAlias.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Regex.h" + +using namespace llvm; + +namespace { + +cl::list + FunctionAlias("function-alias", + cl::desc("Replace functions that match name or regular " + "expression pattern with an alias to the function " + "whose name is given by replacement"), + cl::value_desc("name|pattern>:= LLVM_VERSION(3, 9) + assert((M.ifunc_size() == 0) && "Unexpected ifunc"); +#endif + + for (const auto &pair : FunctionAlias) { + bool matchFound = false; + + // regex pattern can contain colons, e.g. in character classes, + // but replacement function name cannot + std::size_t lastColon = pair.rfind(':'); + if (lastColon == std::string::npos) { + klee_error("function-alias: no replacement given"); + } + std::string pattern = pair.substr(0, lastColon); + std::string replacement = pair.substr(lastColon + 1); + + if (pattern.empty()) + klee_error("function-alias: name or pattern cannot be empty"); + if (replacement.empty()) + klee_error("function-alias: replacement cannot be empty"); + + if (pattern == replacement) { + klee_error("function-alias: @%s cannot replace itself", pattern.c_str()); + } + + // check if replacement function exists + GlobalValue *replacementValue = M.getNamedValue(replacement); + if (!isFunctionOrGlobalFunctionAlias(replacementValue)) + klee_error("function-alias: replacement function @%s could not be found", + replacement.c_str()); + + // directly replace if pattern is not a regex + GlobalValue *match = M.getNamedValue(pattern); + if (isFunctionOrGlobalFunctionAlias(match)) { + if (tryToReplace(match, replacementValue)) { + modified = true; + klee_message("function-alias: replaced @%s with @%s", pattern.c_str(), + replacement.c_str()); + continue; + } + } + if (match != nullptr) { + // pattern is not a regex, but no replacement was found + klee_error("function-alias: no (replacable) match for '%s' found", + pattern.c_str()); + } + + Regex regex(pattern); + std::string error; + if (!regex.isValid(error)) { + klee_error("function-alias: '%s' is not a valid regex: %s", + pattern.c_str(), error.c_str()); + } + + std::vector matches; + + // find matches for regex +#if LLVM_VERSION_CODE >= LLVM_VERSION(5, 0) + for (GlobalValue &global : M.global_values()) { +#else + // chain iterators of alias list and function list + auto firstIt = M.getAliasList().begin(); + auto firstIe = M.getAliasList().end(); + auto secondIt = M.getFunctionList().begin(); + auto secondIe = M.getFunctionList().end(); + for (bool firstList = true;; + (firstList && (++firstIt != firstIe)) || (++secondIt != secondIe)) { + GlobalValue *gv = nullptr; + if (firstIt == firstIe) + firstList = false; + if (firstList) { + gv = cast(&*firstIt); + } else { + if (secondIt == secondIe) + break; + gv = cast(&*secondIt); + } + GlobalValue &global = *gv; +#endif + if (!global.hasName()) + continue; + + if (!isFunctionOrGlobalFunctionAlias(&global)) + continue; + + SmallVector matchVec; + bool match = regex.match(global.getName(), &matchVec); + if (match && matchVec[0].str() == global.getName().str()) { + if (global.getName().str() == replacement) { + klee_warning("function-alias: do not replace @%s (matching '%s') " + "with @%s: cannot replace itself", + global.getName().str().c_str(), pattern.c_str(), + replacement.c_str()); + continue; + } + matches.push_back(&global); + } + } + + // replace all found regex matches + for (GlobalValue *global : matches) { + // name will be invalidated by tryToReplace + std::string name = global->getName().str(); + if (tryToReplace(global, replacementValue)) { + modified = true; + matchFound = true; + klee_message("function-alias: replaced @%s (matching '%s') with @%s", + name.c_str(), pattern.c_str(), replacement.c_str()); + } + } + + if (!matchFound) { + klee_error("function-alias: no (replacable) match for '%s' found", + pattern.c_str()); + } + } + + return modified; +} + +const FunctionType *FunctionAliasPass::getFunctionType(const GlobalValue *gv) { + const Type *type = gv->getType(); + while (type->isPointerTy()) { + const PointerType *ptr = cast(type); + type = ptr->getElementType(); + } + return cast(type); +} + +bool FunctionAliasPass::checkType(const GlobalValue *match, + const GlobalValue *replacement) { + const FunctionType *MFT = getFunctionType(match); + const FunctionType *RFT = getFunctionType(replacement); + assert(MFT != nullptr && RFT != nullptr); + + if (MFT->getReturnType() != RFT->getReturnType()) { + klee_warning("function-alias: @%s could not be replaced with @%s: " + "return type differs", + match->getName().str().c_str(), + replacement->getName().str().c_str()); + return false; + } + + if (MFT->isVarArg() != RFT->isVarArg()) { + klee_warning("function-alias: @%s could not be replaced with @%s: " + "one has varargs while the other does not", + match->getName().str().c_str(), + replacement->getName().str().c_str()); + return false; + } + + if (MFT->getNumParams() != RFT->getNumParams()) { + klee_warning("function-alias: @%s could not be replaced with @%s: " + "number of parameters differs", + match->getName().str().c_str(), + replacement->getName().str().c_str()); + return false; + } + + std::size_t numParams = MFT->getNumParams(); + for (std::size_t i = 0; i < numParams; ++i) { + if (MFT->getParamType(i) != RFT->getParamType(i)) { + klee_warning("function-alias: @%s could not be replaced with @%s: " + "parameter types differ", + match->getName().str().c_str(), + replacement->getName().str().c_str()); + return false; + } + } + return true; +} + +bool FunctionAliasPass::tryToReplace(GlobalValue *match, + GlobalValue *replacement) { + if (!checkType(match, replacement)) + return false; + + GlobalAlias *alias = GlobalAlias::create("", replacement); + match->replaceAllUsesWith(alias); + alias->takeName(match); + match->eraseFromParent(); + + return true; +} + +bool FunctionAliasPass::isFunctionOrGlobalFunctionAlias(const GlobalValue *gv) { + if (gv == nullptr) + return false; + + if (isa(gv)) + return true; + + if (const auto *ga = dyn_cast(gv)) { + const auto *aliasee = dyn_cast(ga->getAliasee()); + if (!aliasee) { + // check if GlobalAlias is alias bitcast + const auto *cexpr = dyn_cast(ga->getAliasee()); + if (!cexpr || !cexpr->isCast()) + return false; + aliasee = dyn_cast(cexpr->getOperand(0)); + } + return isFunctionOrGlobalFunctionAlias(aliasee); + } + + return false; +} + +char FunctionAliasPass::ID = 0; + +} // namespace klee diff --git a/lib/Module/KModule.cpp b/lib/Module/KModule.cpp index 2ee49f23..315942b5 100644 --- a/lib/Module/KModule.cpp +++ b/lib/Module/KModule.cpp @@ -287,6 +287,7 @@ void KModule::optimiseAndPrepare( } pm3.add(new IntrinsicCleanerPass(*targetData)); pm3.add(new PhiCleanerPass()); + pm3.add(new FunctionAliasPass()); pm3.run(*module); } diff --git a/lib/Module/Passes.h b/lib/Module/Passes.h index d5f8d821..4fb0cfd7 100644 --- a/lib/Module/Passes.h +++ b/lib/Module/Passes.h @@ -167,6 +167,24 @@ public: bool checkPassed() const { return instructionOperandsConform; } }; +/// FunctionAliasPass - Enables a user of KLEE to specify aliases to functions +/// using -function-alias=: which are injected as +/// GlobalAliases into the module. The replaced function is removed. +class FunctionAliasPass : public llvm::ModulePass { + +public: + static char ID; + FunctionAliasPass() : llvm::ModulePass(ID) {} + bool runOnModule(llvm::Module &M) override; + +private: + static const llvm::FunctionType *getFunctionType(const llvm::GlobalValue *gv); + static bool checkType(const llvm::GlobalValue *match, const llvm::GlobalValue *replacement); + static bool tryToReplace(llvm::GlobalValue *match, llvm::GlobalValue *replacement); + static bool isFunctionOrGlobalFunctionAlias(const llvm::GlobalValue *gv); + +}; + #ifdef USE_WORKAROUND_LLVM_PR39177 /// WorkaroundLLVMPR39177Pass - Workaround for LLVM PR39177 within KLEE repo. /// For more information on this, please refer to the comments in diff --git a/test/Feature/FunctionAlias.c b/test/Feature/FunctionAlias.c new file mode 100644 index 00000000..2fcb5beb --- /dev/null +++ b/test/Feature/FunctionAlias.c @@ -0,0 +1,89 @@ +// RUN: %clang %s -emit-llvm %O0opt -c -o %t.bc +// RUN: rm -rf %t.klee-out +// RUN: not %klee --output-dir=%t.klee-out -function-alias=:oneint %t.bc 2>&1 | FileCheck --check-prefix=CHECK-EMPTY --check-prefix=CHECK-ERROR %s +// RUN: rm -rf %t.klee-out +// RUN: not %klee --output-dir=%t.klee-out -function-alias=oneint: %t.bc 2>&1 | FileCheck --check-prefix=CHECK-EMPTY --check-prefix=CHECK-ERROR %s +// RUN: rm -rf %t.klee-out +// RUN: not %klee --output-dir=%t.klee-out -function-alias=oneint:oneint %t.bc 2>&1 | FileCheck --check-prefix=CHECK-SAME --check-prefix=CHECK-ERROR %s +// RUN: rm -rf %t.klee-out +// RUN: not %klee --output-dir=%t.klee-out -function-alias=oneint:oneshort %t.bc 2>&1 | FileCheck --check-prefix=CHECK-TYPE-MISMATCH --check-prefix=CHECK-ERROR %s +// RUN: rm -rf %t.klee-out +// RUN: not %klee --output-dir=%t.klee-out -function-alias=oneint:twoints %t.bc 2>&1 | FileCheck --check-prefix=CHECK-TYPE-MISMATCH --check-prefix=CHECK-ERROR %s +// RUN: rm -rf %t.klee-out +// RUN: not %klee --output-dir=%t.klee-out -function-alias=twoints:twoshorts2int %t.bc 2>&1 | FileCheck --check-prefix=CHECK-TYPE-MISMATCH --check-prefix=CHECK-ERROR %s +// RUN: rm -rf %t.klee-out +// RUN: not %klee --output-dir=%t.klee-out -function-alias=oneint:unknownfunction %t.bc 2>&1 | FileCheck --check-prefix=CHECK-UNKNOWN --check-prefix=CHECK-ERROR %s +// RUN: rm -rf %t.klee-out +// RUN: %klee --output-dir=%t.klee-out -function-alias=twoints:twointsmul %t.bc 2>&1 | FileCheck --check-prefix=CHECK-SUCCESS %s +// RUN: rm -rf %t.klee-out +// RUN: not %klee --output-dir=%t.klee-out -function-alias=xxx.*:somethingwithtwoints %t.bc 2>&1 | FileCheck --check-prefix=CHECK-REGEX-NO-MATCH --check-prefix=CHECK-ERROR %s +// RUN: rm -rf %t.klee-out +// RUN: %klee --output-dir=%t.klee-out -function-alias=twoints.*:somethingwithtwoints %t.bc 2>&1 | FileCheck --check-prefix=CHECK-REGEX-PREFIX %s +// RUN: rm -rf %t.klee-out +// RUN: %klee --output-dir=%t.klee-out -function-alias=.*twoints.*:twoints %t.bc 2>&1 | FileCheck --check-prefix=CHECK-REGEX-INFIX %s +// RUN: rm -rf %t.klee-out +// RUN: %klee --output-dir=%t.klee-out -function-alias=two.*:twoints %t.bc 2>&1 | FileCheck --check-prefix=CHECK-REGEX-TYPE-MISMATCH %s +// RUN: rm -rf %t.klee-out +// RUN: %klee --output-dir=%t.klee-out -function-alias=somethingwith.*:twoints -function-alias=twoints:twointsmul %t.bc 2>&1 | FileCheck --check-prefix=CHECK-MULTIPLE %s +// RUN: rm -rf %t.klee-out +// RUN: %klee --output-dir=%t.klee-out -output-module -function-alias=oneshort:shortminusone %t.bc 2>&1 | FileCheck --check-prefix=CHECK-BITCAST-ALIAS %s + +#include +#include +#include + +// CHECK-EMPTY: KLEE: ERROR: function-alias: {{name or pattern|replacement}} cannot be empty + +// CHECK-SAME: KLEE: ERROR: function-alias: @oneint cannot replace itself + +// CHECK-TYPE-MISMATCH: KLEE: WARNING: function-alias: @{{[a-z0-9]+}} could not be replaced with @{{[a-z0-9]+}} + +// CHECK-SUCCESS: KLEE: function-alias: replaced @twoints with @twointsmul + +// CHECK-REGEX-NO-MATCH: KLEE: ERROR: function-alias: no (replacable) match for 'xxx.*' found + +// CHECK-REGEX-PREFIX: KLEE: function-alias: replaced @twoints (matching 'twoints.*') with @somethingwithtwoints +// CHECK-REGEX-PREFIX: KLEE: function-alias: replaced @twointsmul (matching 'twoints.*') with @somethingwithtwoints + +// CHECK-REGEX-INFIX: KLEE: WARNING: function-alias: do not replace @twoints (matching '.*twoints.*') with @twoints: cannot replace itself +// CHECK-REGEX-INFIX: KLEE: function-alias: replaced @twointsmul (matching '.*twoints.*') with @twoints +// CHECK-REGEX-INFIX: KLEE: function-alias: replaced @somethingwithtwoints (matching '.*twoints.*') with @twoints + +// CHECK-REGEX-TYPE-MISMATCH: KLEE: WARNING: function-alias: @twoshorts2int could not be replaced with @twoints: parameter types differ +// CHECK-REGEX-TYPE-MISMATCH: KLEE: function-alias: replaced @twointsmul (matching 'two.*') with @twoints + +// CHECK-MULTIPLE: KLEE: function-alias: replaced @somethingwithtwoints (matching 'somethingwith.*') with @twoints +// CHECK-MULTIPLE: KLEE: function-alias: replaced @twoints with @twointsmul + +// CHECK-BITCAST-ALIAS: function-alias: replaced @oneshort with @shortminusone + +int __attribute__ ((noinline)) oneint(int a) { return a; } +short __attribute__ ((noinline)) oneshort(short a) { return a + 1; } +int __attribute__ ((noinline)) minusone(int a) { return a - 1; } +int __attribute__ ((noinline)) twoints(int a, int b) { return a + b; } +int __attribute__ ((noinline)) twoshorts2int(short a, short b) { return a + b + 2; } +int __attribute__ ((noinline)) twointsmul(int a, int b) { return a * b + 5; } +int __attribute__ ((noinline)) somethingwithtwoints(int a, int b) { return 2 * a + 3 * b; } + +extern short shortminusone(short) __attribute__((alias("minusone"))); + +int main() { + short a = 2; + short b = 3; + int result = 0; + result += shortminusone(a); + result += oneint(a); + result += oneshort(a); + result += twoints(a, b); + result += twoshorts2int(a, b); + result += twointsmul(a, b); + result += somethingwithtwoints(a, b); + // CHECK-ERROR-NOT: result = + // CHECK-SUCCESS: result = 48 + // CHECK-REGEX-PREFIX: result = 52 + // CHECK-REGEX-INFIX: result = 28 + // CHECK-REGEX-TYPE-MISMATCH: result = 36 + // CHECK-MULTIPLE: result = 46 + // CHECK-BITCAST-ALIAS: 40 + printf("result = %d\n", result); +} diff --git a/test/Feature/FunctionAliasExit.c b/test/Feature/FunctionAliasExit.c new file mode 100644 index 00000000..b30838d0 --- /dev/null +++ b/test/Feature/FunctionAliasExit.c @@ -0,0 +1,31 @@ +// RUN: %clang %s -emit-llvm %O0opt -c -o %t.bc +// RUN: rm -rf %t.klee-out +// RUN: %klee --output-dir=%t.klee-out -function-alias=exit:end %t.bc 2>&1 | FileCheck %s + +#include +#include +#include + +// CHECK: KLEE: function-alias: replaced @exit with @end + +void start(int x) { + // CHECK: START + printf("START\n"); + if (x == 53) + // CHECK: END: status = 1 + exit(1); +} + +void __attribute__ ((noinline)) end(int status) { + printf("END: status = %d\n", status); + klee_silent_exit(status); +} + +int main() { + int x; + klee_make_symbolic(&x, sizeof(x), "x"); + + start(x); + // CHECK: END: status = 0 + end(0); +} diff --git a/test/Feature/FunctionAliasVarArg.c b/test/Feature/FunctionAliasVarArg.c new file mode 100644 index 00000000..17893772 --- /dev/null +++ b/test/Feature/FunctionAliasVarArg.c @@ -0,0 +1,58 @@ +// RUN: %clang %s -emit-llvm %O0opt -c -o %t.bc +// RUN: rm -rf %t.klee-out +// RUN: %klee --output-dir=%t.klee-out -function-alias=printf:highlight_prefix_printf %t.bc 2>&1 | FileCheck --check-prefix=CHECK-HIGHLIGHT %s +// RUN: rm -rf %t.klee-out +// RUN: not %klee --output-dir=%t.klee-out -function-alias=printf:printf_format_only %t.bc 2>&1 | FileCheck --check-prefix=CHECK-VA-FAIL %s +// RUN: rm -rf %t.klee-out +// RUN: %klee --output-dir=%t.klee-out -function-alias=printf:printf_format_only_with_varargs %t.bc 2>&1 | FileCheck --check-prefix=CHECK-VA-SUCCESS %s + +#include +#include +#include + +// CHECK-HIGHLIGHT: KLEE: function-alias: replaced @printf with @highlight_prefix_printf +int highlight_prefix_printf(const char *format, ...) { + va_list args; + int result; + const char *bold_start = "*+*"; + const char *bold_end = "*+*"; + + va_start(args, format); + const char *prefix = va_arg(args, const char *); + + const char *prefixless_format = strstr(format, "%s") + 2; + size_t new_length = strlen(bold_start) + strlen(prefix) + strlen(bold_end) + strlen(prefixless_format) + 1; + char *new_format = (char *)malloc(new_length); + memset(new_format, 0, new_length); + strcat(new_format, bold_start); + strcat(new_format, prefix); + strcat(new_format, bold_end); + strcat(new_format, prefixless_format); + result = vfprintf(stdout, new_format, args); + va_end(args); + + free(new_format); + return result; +} + +// CHECK-VA-FAIL: KLEE: WARNING: function-alias: @printf could not be replaced with @printf_format_only: one has varargs while the other does not +int printf_format_only(const char *format) { + int result; + result = puts(format); + return result; +} + +// CHECK-VA-SUCCESS: KLEE: function-alias: replaced @printf with @printf_format_only_with_varargs +int printf_format_only_with_varargs(const char *format, ...) { + int result; + result = puts(format); + return result; +} + +int main() { + int i = 42; + // CHECK: KLEE: some warning about 42 + // CHECK-HIGHLIGHT: *+*KLEE*+* + // CHECK-VA-SUCCESS: %s: some warning about %d + printf("%s: some warning about %d\n", "KLEE", i); +} -- cgit 1.4.1