From b57b2073acf85e985f513a12d8aae725f8942689 Mon Sep 17 00:00:00 2001 From: van Hauser Date: Wed, 3 Jul 2019 12:05:58 +0200 Subject: LAF_... -> AFL_LLVM_LAF_... --- llvm_mode/afl-clang-fast.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'llvm_mode/afl-clang-fast.c') diff --git a/llvm_mode/afl-clang-fast.c b/llvm_mode/afl-clang-fast.c index 1e2e04ea..5bc4ae8c 100644 --- a/llvm_mode/afl-clang-fast.c +++ b/llvm_mode/afl-clang-fast.c @@ -120,21 +120,21 @@ static void edit_params(u32 argc, char** argv) { http://clang.llvm.org/docs/SanitizerCoverage.html#tracing-pcs-with-guards */ // laf - if (getenv("LAF_SPLIT_SWITCHES")) { + if (getenv("LAF_SPLIT_SWITCHES")||getenv("AFL_LLVM_LAF_SPLIT_SWITCHES")) { cc_params[cc_par_cnt++] = "-Xclang"; cc_params[cc_par_cnt++] = "-load"; cc_params[cc_par_cnt++] = "-Xclang"; cc_params[cc_par_cnt++] = alloc_printf("%s/split-switches-pass.so", obj_path); } - if (getenv("LAF_TRANSFORM_COMPARES")) { + if (getenv("LAF_TRANSFORM_COMPARES")||getenv("AFL_LLVM_LAF_TRANSFORM_COMPARES")) { cc_params[cc_par_cnt++] = "-Xclang"; cc_params[cc_par_cnt++] = "-load"; cc_params[cc_par_cnt++] = "-Xclang"; cc_params[cc_par_cnt++] = alloc_printf("%s/compare-transform-pass.so", obj_path); } - if (getenv("LAF_SPLIT_COMPARES")) { + if (getenv("LAF_SPLIT_COMPARES")||getenv("AFL_LLVM_LAF_SPLIT_COMPARES")) { cc_params[cc_par_cnt++] = "-Xclang"; cc_params[cc_par_cnt++] = "-load"; cc_params[cc_par_cnt++] = "-Xclang"; -- cgit 1.4.1 From aaa810c64a7d54d21df6c74c3f7b77fb06d273fe Mon Sep 17 00:00:00 2001 From: van Hauser Date: Wed, 3 Jul 2019 12:11:02 +0200 Subject: add -lrt with afl-gcc/clang automatically in mmap mode --- Makefile | 8 ++++---- afl-gcc.c | 4 ++++ llvm_mode/Makefile | 8 ++++---- llvm_mode/afl-clang-fast.c | 4 ++++ 4 files changed, 16 insertions(+), 8 deletions(-) (limited to 'llvm_mode/afl-clang-fast.c') diff --git a/Makefile b/Makefile index 7acdd049..14b5ce0e 100644 --- a/Makefile +++ b/Makefile @@ -176,10 +176,10 @@ endif all_done: test_build @if [ ! "`which clang 2>/dev/null`" = "" ]; then echo "[+] LLVM users: see llvm_mode/README.llvm for a faster alternative to afl-gcc."; fi @echo "[+] All done! Be sure to review the README - it's pretty short and useful." -ifeq "$(SHMAT_OK)" "0" - @echo "[!] shmat isn't working on your platform - compile every target with -lrt:" - @echo "[!] CFLAGS=-lrt LDFLAGS=-lrt CC=afl-gcc CXX=afl-g++ ./configure" -endif +#ifeq "$(SHMAT_OK)" "0" +# @echo "[!] shmat isn't working on your platform - compile every target with -lrt:" +# @echo "[!] CFLAGS=-lrt LDFLAGS=-lrt CC=afl-gcc CXX=afl-g++ ./configure" +#endif @if [ "`uname`" = "Darwin" ]; then printf "\nWARNING: Fuzzing on MacOS X is slow because of the unusually high overhead of\nfork() on this OS. Consider using Linux or *BSD. You can also use VirtualBox\n(virtualbox.org) to put AFL inside a Linux or *BSD VM.\n\n"; fi @! tty <&1 >/dev/null || printf "\033[0;30mNOTE: If you can read this, your terminal probably uses white background.\nThis will make the UI hard to read. See docs/status_screen.txt for advice.\033[0m\n" 2>/dev/null diff --git a/afl-gcc.c b/afl-gcc.c index 8d3988c7..467a9bc1 100644 --- a/afl-gcc.c +++ b/afl-gcc.c @@ -252,6 +252,10 @@ static void edit_params(u32 argc, char** argv) { } +#ifdef USEMMAP + cc_params[cc_par_cnt++] = "-lrt"; +#endif + if (!getenv("AFL_DONT_OPTIMIZE")) { #if defined(__FreeBSD__) && defined(__x86_64__) diff --git a/llvm_mode/Makefile b/llvm_mode/Makefile index e2ed07d6..d3e0c739 100644 --- a/llvm_mode/Makefile +++ b/llvm_mode/Makefile @@ -154,10 +154,10 @@ test_build: $(PROGS) all_done: test_build @echo "[+] All done! You can now use '../afl-clang-fast' to compile programs." -ifeq "$(SHMAT_OK)" "0" - @echo "[!] shmat isn't working on your platform - compile every target with -lrt:" - @echo "[!] CFLAGS=-lrt LDFLAGS=-lrt CC=afl-clang-fast CXX=afl-clang-fast++ ./configure" -endif +#ifeq "$(SHMAT_OK)" "0" +# @echo "[!] shmat isn't working on your platform - compile every target with -lrt:" +# @echo "[!] CFLAGS=-lrt LDFLAGS=-lrt CC=afl-clang-fast CXX=afl-clang-fast++ ./configure" +#endif .NOTPARALLEL: clean diff --git a/llvm_mode/afl-clang-fast.c b/llvm_mode/afl-clang-fast.c index 1e2e04ea..366389b4 100644 --- a/llvm_mode/afl-clang-fast.c +++ b/llvm_mode/afl-clang-fast.c @@ -246,6 +246,10 @@ static void edit_params(u32 argc, char** argv) { } +#ifdef USEMMAP + cc_params[cc_par_cnt++] = "-lrt"; +#endif + cc_params[cc_par_cnt++] = "-D__AFL_HAVE_MANUAL_CONTROL=1"; cc_params[cc_par_cnt++] = "-D__AFL_COMPILER=1"; cc_params[cc_par_cnt++] = "-DFUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION=1"; -- cgit 1.4.1 From 864056fcaaeea0e156e650b7a0f6182e81db566a Mon Sep 17 00:00:00 2001 From: van Hauser Date: Sat, 13 Jul 2019 11:08:13 +0200 Subject: initial commit --- Makefile | 2 +- llvm_mode/LLVMInsTrim.so.cc | 197 ++++++++++++++++++++++++ llvm_mode/Makefile | 6 +- llvm_mode/MarkNodes.cc | 355 ++++++++++++++++++++++++++++++++++++++++++++ llvm_mode/MarkNodes.h | 11 ++ llvm_mode/afl-clang-fast.c | 8 +- 6 files changed, 572 insertions(+), 7 deletions(-) create mode 100644 llvm_mode/LLVMInsTrim.so.cc create mode 100644 llvm_mode/MarkNodes.cc create mode 100644 llvm_mode/MarkNodes.h (limited to 'llvm_mode/afl-clang-fast.c') diff --git a/Makefile b/Makefile index 601f29a7..0d0d6b79 100644 --- a/Makefile +++ b/Makefile @@ -147,7 +147,7 @@ install: all rm -f $${DESTDIR}$(BIN_PATH)/afl-as if [ -f afl-qemu-trace ]; then install -m 755 afl-qemu-trace $${DESTDIR}$(BIN_PATH); fi ifndef AFL_TRACE_PC - if [ -f afl-clang-fast -a -f afl-llvm-pass.so -a -f afl-llvm-rt.o ]; then set -e; install -m 755 afl-clang-fast $${DESTDIR}$(BIN_PATH); ln -sf afl-clang-fast $${DESTDIR}$(BIN_PATH)/afl-clang-fast++; install -m 755 afl-llvm-pass.so afl-llvm-rt.o $${DESTDIR}$(HELPER_PATH); fi + if [ -f afl-clang-fast -a -f libLLVMInsTrim.so -a -f afl-llvm-rt.o ]; then set -e; install -m 755 afl-clang-fast $${DESTDIR}$(BIN_PATH); ln -sf afl-clang-fast $${DESTDIR}$(BIN_PATH)/afl-clang-fast++; install -m 755 libLLVMInsTrim.so afl-llvm-rt.o $${DESTDIR}$(HELPER_PATH); fi else if [ -f afl-clang-fast -a -f afl-llvm-rt.o ]; then set -e; install -m 755 afl-clang-fast $${DESTDIR}$(BIN_PATH); ln -sf afl-clang-fast $${DESTDIR}$(BIN_PATH)/afl-clang-fast++; install -m 755 afl-llvm-rt.o $${DESTDIR}$(HELPER_PATH); fi endif diff --git a/llvm_mode/LLVMInsTrim.so.cc b/llvm_mode/LLVMInsTrim.so.cc new file mode 100644 index 00000000..2a13981d --- /dev/null +++ b/llvm_mode/LLVMInsTrim.so.cc @@ -0,0 +1,197 @@ +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/LegacyPassManager.h" +#include "llvm/IR/Module.h" +#include "llvm/Pass.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/IPO/PassManagerBuilder.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include +#include + +#include "MarkNodes.h" + +using namespace llvm; + +static cl::opt MarkSetOpt("markset", cl::desc("MarkSet"), + cl::init(false)); +static cl::opt LoopHeadOpt("loophead", cl::desc("LoopHead"), + cl::init(false)); + +namespace { + struct InsTrim : public ModulePass { + private: + std::mt19937 generator; + int total_instr = 0; + + unsigned genLabel() { + return generator() % 65536; + } + + public: + static char ID; + InsTrim() : ModulePass(ID), generator(0) {} + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + } + + StringRef getPassName() const override { + return "InstTrim Instrumentation"; + } + + bool runOnModule(Module &M) override { + if (getenv("LOOPHEAD")) { + LoopHeadOpt = true; + MarkSetOpt = true; + } else if (getenv("MARKSET")) { + MarkSetOpt = true; + } + + LLVMContext &C = M.getContext(); + IntegerType *Int8Ty = IntegerType::getInt8Ty(C); + IntegerType *Int32Ty = IntegerType::getInt32Ty(C); + + GlobalVariable *CovMapPtr = new GlobalVariable( + M, PointerType::getUnqual(Int8Ty), false, GlobalValue::ExternalLinkage, + nullptr, "__afl_area_ptr"); + + GlobalVariable *OldPrev = new GlobalVariable( + M, Int32Ty, false, GlobalValue::ExternalLinkage, 0, "__afl_prev_loc", + 0, GlobalVariable::GeneralDynamicTLSModel, 0, false); + + unsigned total_rs = 0; + unsigned total_hs = 0; + + for (Function &F : M) { + if (!F.size()) { + continue; + } + + std::unordered_set MS; + if (!MarkSetOpt) { + for (auto &BB : F) { + MS.insert(&BB); + } + total_rs += F.size(); + } else { + auto Result = markNodes(&F); + auto RS = Result.first; + auto HS = Result.second; + + MS.insert(RS.begin(), RS.end()); + if (!LoopHeadOpt) { + MS.insert(HS.begin(), HS.end()); + total_rs += MS.size(); + } else { + DenseSet> EdgeSet; + DominatorTreeWrapperPass *DTWP = + &getAnalysis(F); + auto DT = &DTWP->getDomTree(); + + total_rs += RS.size(); + total_hs += HS.size(); + + for (BasicBlock *BB : HS) { + bool Inserted = false; + for (auto BI = pred_begin(BB), BE = pred_end(BB); + BI != BE; ++BI + ) { + auto Edge = BasicBlockEdge(*BI, BB); + if (Edge.isSingleEdge() && DT->dominates(Edge, BB)) { + EdgeSet.insert({*BI, BB}); + Inserted = true; + break; + } + } + if (!Inserted) { + MS.insert(BB); + total_rs += 1; + total_hs -= 1; + } + } + for (auto I = EdgeSet.begin(), E = EdgeSet.end(); I != E; ++I) { + auto PredBB = I->first; + auto SuccBB = I->second; + auto NewBB = SplitBlockPredecessors(SuccBB, {PredBB}, ".split", + DT, nullptr, false); + MS.insert(NewBB); + } + } + + auto *EBB = &F.getEntryBlock(); + if (succ_begin(EBB) == succ_end(EBB)) { + MS.insert(EBB); + total_rs += 1; + } + + for (BasicBlock &BB : F) { + if (MS.find(&BB) == MS.end()) { + continue; + } + IRBuilder<> IRB(&*BB.getFirstInsertionPt()); + IRB.CreateStore(ConstantInt::get(Int32Ty, genLabel()), OldPrev); + } + } + + for (BasicBlock &BB : F) { + auto PI = pred_begin(&BB); + auto PE = pred_end(&BB); + if (MarkSetOpt && MS.find(&BB) == MS.end()) { + continue; + } + + IRBuilder<> IRB(&*BB.getFirstInsertionPt()); + Value *L = NULL; + if (PI == PE) { + L = ConstantInt::get(Int32Ty, genLabel()); + } else { + auto *PN = PHINode::Create(Int32Ty, 0, "", &*BB.begin()); + DenseMap PredMap; + for (auto PI = pred_begin(&BB), PE = pred_end(&BB); + PI != PE; ++PI + ) { + BasicBlock *PBB = *PI; + auto It = PredMap.insert({PBB, genLabel()}); + unsigned Label = It.first->second; + PN->addIncoming(ConstantInt::get(Int32Ty, Label), PBB); + } + L = PN; + } + + LoadInst *PrevLoc = IRB.CreateLoad(OldPrev); + Value *PrevLocCasted = IRB.CreateZExt(PrevLoc, IRB.getInt32Ty()); + + LoadInst *MapPtr = IRB.CreateLoad(CovMapPtr); + Value *MapPtrIdx = IRB.CreateGEP(MapPtr, + IRB.CreateXor(PrevLocCasted, L)); + + LoadInst *Counter = IRB.CreateLoad(MapPtrIdx); + Value *Incr = IRB.CreateAdd(Counter, ConstantInt::get(Int8Ty, 1)); + IRB.CreateStore(Incr, MapPtrIdx); + total_instr++; + } + } + + errs() << total_instr << " locations instrumented ("<< total_rs << "," << total_hs << ")\n"; + return false; + } + }; // end of struct InsTrim +} // end of anonymous namespace + +char InsTrim::ID = 0; + +static void registerAFLPass(const PassManagerBuilder &, + legacy::PassManagerBase &PM) { + PM.add(new InsTrim()); +} + +static RegisterStandardPasses RegisterAFLPass( + PassManagerBuilder::EP_OptimizerLast, registerAFLPass); + +static RegisterStandardPasses RegisterAFLPass0( + PassManagerBuilder::EP_EnabledOnOptLevel0, registerAFLPass); diff --git a/llvm_mode/Makefile b/llvm_mode/Makefile index b6ab0c61..a66f18ab 100644 --- a/llvm_mode/Makefile +++ b/llvm_mode/Makefile @@ -67,7 +67,7 @@ ifeq "$(origin CC)" "default" endif ifndef AFL_TRACE_PC - PROGS = ../afl-clang-fast ../afl-llvm-pass.so ../afl-llvm-rt.o ../afl-llvm-rt-32.o ../afl-llvm-rt-64.o ../compare-transform-pass.so ../split-compares-pass.so ../split-switches-pass.so + PROGS = ../afl-clang-fast ../libLLVMInsTrim.so ../afl-llvm-rt.o ../afl-llvm-rt-32.o ../afl-llvm-rt-64.o ../compare-transform-pass.so ../split-compares-pass.so ../split-switches-pass.so else PROGS = ../afl-clang-fast ../afl-llvm-rt.o ../afl-llvm-rt-32.o ../afl-llvm-rt-64.o ../compare-transform-pass.so ../split-compares-pass.so ../split-switches-pass.so endif @@ -91,8 +91,8 @@ endif $(CC) $(CFLAGS) $< -o $@ $(LDFLAGS) ln -sf afl-clang-fast ../afl-clang-fast++ -../afl-llvm-pass.so: afl-llvm-pass.so.cc | test_deps - $(CXX) $(CLANG_CFL) -shared $< -o $@ $(CLANG_LFL) +../libLLVMInsTrim.so: LLVMInsTrim.so.cc MarkNodes.cc | test_deps + $(CXX) $(CLANG_CFL) -DLLVMInsTrim_EXPORTS -fno-rtti -fPIC -std=gnu++11 -shared $< -o $@ $(CLANG_LFL) # laf ../split-switches-pass.so: split-switches-pass.so.cc | test_deps diff --git a/llvm_mode/MarkNodes.cc b/llvm_mode/MarkNodes.cc new file mode 100644 index 00000000..3c2129ef --- /dev/null +++ b/llvm_mode/MarkNodes.cc @@ -0,0 +1,355 @@ +#include +#include +#include +#include +#include +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" +#include "llvm/Pass.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" + +using namespace llvm; + +DenseMap LMap; +std::vector Blocks; +std::set Marked , Markabove; +std::vector< std::vector > Succs , Preds; + +void reset(){ + LMap.clear(); + Blocks.clear(); + Marked.clear(); + Markabove.clear(); +} + +uint32_t start_point; + +void labelEachBlock(Function *F) { + // Fake single endpoint; + LMap[NULL] = Blocks.size(); + Blocks.push_back(NULL); + + // Assign the unique LabelID to each block; + for (auto I = F->begin(), E = F->end(); I != E; ++I) { + BasicBlock *BB = &*I; + LMap[BB] = Blocks.size(); + Blocks.push_back(BB); + } + + start_point = LMap[&F->getEntryBlock()]; +} + +void buildCFG(Function *F) { + Succs.resize( Blocks.size() ); + Preds.resize( Blocks.size() ); + for( size_t i = 0 ; i < Succs.size() ; i ++ ){ + Succs[ i ].clear(); + Preds[ i ].clear(); + } + + uint32_t FakeID = 0; + for (auto S = F->begin(), E = F->end(); S != E; ++S) { + BasicBlock *BB = &*S; + uint32_t MyID = LMap[BB]; + //if (succ_begin(BB) == succ_end(BB)) { + //Succs[MyID].push_back(FakeID); + //Marked.insert(MyID); + //} + for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { + Succs[MyID].push_back(LMap[*I]); + } + } +} + +std::vector< std::vector > tSuccs; +std::vector tag , indfs; + +void DFStree(size_t now_id) { + if(tag[now_id]) return; + tag[now_id]=true; + indfs[now_id]=true; + for (auto succ: tSuccs[now_id]) { + if(tag[succ] and indfs[succ]) { + Marked.insert(succ); + Markabove.insert(succ); + continue; + } + Succs[now_id].push_back(succ); + Preds[succ].push_back(now_id); + DFStree(succ); + } + indfs[now_id]=false; +} +void turnCFGintoDAG(Function *F) { + tSuccs = Succs; + tag.resize(Blocks.size()); + indfs.resize(Blocks.size()); + for (size_t i = 0; i < Blocks.size(); ++ i) { + Succs[i].clear(); + tag[i]=false; + indfs[i]=false; + } + DFStree(start_point); + for (size_t i = 0; i < Blocks.size(); ++ i) + if( Succs[i].empty() ){ + Succs[i].push_back(0); + Preds[0].push_back(i); + } +} + +uint32_t timeStamp; +namespace DominatorTree{ + std::vector< std::vector > cov; + std::vector dfn, nfd, par, sdom, idom, mom, mn; + + bool Compare(uint32_t u, uint32_t v) { + return dfn[u] < dfn[v]; + } + uint32_t eval(uint32_t u) { + if( mom[u] == u ) return u; + uint32_t res = eval( mom[u] ); + if(Compare(sdom[mn[mom[u]]] , sdom[mn[u]])) { + mn[u] = mn[mom[u]]; + } + return mom[u] = res; + } + + void DFS(uint32_t now) { + timeStamp += 1; + dfn[now] = timeStamp; + nfd[timeStamp - 1] = now; + for( auto succ : Succs[now] ) { + if( dfn[succ] == 0 ) { + par[succ] = now; + DFS(succ); + } + } + } + + void DominatorTree(Function *F) { + if( Blocks.empty() ) return; + uint32_t s = start_point; + + // Initialization + mn.resize(Blocks.size()); + cov.resize(Blocks.size()); + dfn.resize(Blocks.size()); + nfd.resize(Blocks.size()); + par.resize(Blocks.size()); + mom.resize(Blocks.size()); + sdom.resize(Blocks.size()); + idom.resize(Blocks.size()); + + for( uint32_t i = 0 ; i < Blocks.size() ; i ++ ) { + dfn[i] = 0; + nfd[i] = Blocks.size(); + cov[i].clear(); + idom[i] = mom[i] = mn[i] = sdom[i] = i; + } + + timeStamp = 0; + DFS(s); + + for( uint32_t i = Blocks.size() - 1 ; i >= 1u ; i -- ) { + uint32_t now = nfd[i]; + if( now == Blocks.size() ) { + continue; + } + for( uint32_t pre : Preds[ now ] ) { + if( dfn[ pre ] ) { + eval(pre); + if( Compare(sdom[mn[pre]], sdom[now]) ) { + sdom[now] = sdom[mn[pre]]; + } + } + } + cov[sdom[now]].push_back(now); + mom[now] = par[now]; + for( uint32_t x : cov[par[now]] ) { + eval(x); + if( Compare(sdom[mn[x]], par[now]) ) { + idom[x] = mn[x]; + } else { + idom[x] = par[now]; + } + } + } + + for( uint32_t i = 1 ; i < Blocks.size() ; i += 1 ) { + uint32_t now = nfd[i]; + if( now == Blocks.size() ) { + continue; + } + if(idom[now] != sdom[now]) + idom[now] = idom[idom[now]]; + } + } +}; // End of DominatorTree + +std::vector Visited, InStack; +std::vector TopoOrder, InDeg; +std::vector< std::vector > t_Succ , t_Pred; + +void Go(uint32_t now, uint32_t tt) { + if( now == tt ) return; + Visited[now] = InStack[now] = timeStamp; + + for(uint32_t nxt : Succs[now]) { + if(Visited[nxt] == timeStamp and InStack[nxt] == timeStamp) { + Marked.insert(nxt); + } + t_Succ[now].push_back(nxt); + t_Pred[nxt].push_back(now); + InDeg[nxt] += 1; + if(Visited[nxt] == timeStamp) { + continue; + } + Go(nxt, tt); + } + + InStack[now] = 0; +} + +void TopologicalSort(uint32_t ss, uint32_t tt) { + timeStamp += 1; + + Go(ss, tt); + + TopoOrder.clear(); + std::queue wait; + wait.push(ss); + while( not wait.empty() ) { + uint32_t now = wait.front(); wait.pop(); + TopoOrder.push_back(now); + for(uint32_t nxt : t_Succ[now]) { + InDeg[nxt] -= 1; + if(InDeg[nxt] == 0u) { + wait.push(nxt); + } + } + } +} + +std::vector< std::set > NextMarked; +bool Indistinguish(uint32_t node1, uint32_t node2) { + if(NextMarked[node1].size() > NextMarked[node2].size()){ + uint32_t _swap = node1; + node1 = node2; + node2 = _swap; + } + for(uint32_t x : NextMarked[node1]) { + if( NextMarked[node2].find(x) != NextMarked[node2].end() ) { + return true; + } + } + return false; +} + +void MakeUniq(uint32_t now) { + bool StopFlag = false; + if (Marked.find(now) == Marked.end()) { + for(uint32_t pred1 : t_Pred[now]) { + for(uint32_t pred2 : t_Pred[now]) { + if(pred1 == pred2) continue; + if(Indistinguish(pred1, pred2)) { + Marked.insert(now); + StopFlag = true; + break; + } + } + if (StopFlag) { + break; + } + } + } + if(Marked.find(now) != Marked.end()) { + NextMarked[now].insert(now); + } else { + for(uint32_t pred : t_Pred[now]) { + for(uint32_t x : NextMarked[pred]) { + NextMarked[now].insert(x); + } + } + } +} + +void MarkSubGraph(uint32_t ss, uint32_t tt) { + TopologicalSort(ss, tt); + if(TopoOrder.empty()) return; + + for(uint32_t i : TopoOrder) { + NextMarked[i].clear(); + } + + NextMarked[TopoOrder[0]].insert(TopoOrder[0]); + for(uint32_t i = 1 ; i < TopoOrder.size() ; i += 1) { + MakeUniq(TopoOrder[i]); + } +} + +void MarkVertice(Function *F) { + uint32_t s = start_point; + + InDeg.resize(Blocks.size()); + Visited.resize(Blocks.size()); + InStack.resize(Blocks.size()); + t_Succ.resize(Blocks.size()); + t_Pred.resize(Blocks.size()); + NextMarked.resize(Blocks.size()); + + for( uint32_t i = 0 ; i < Blocks.size() ; i += 1 ) { + Visited[i] = InStack[i] = InDeg[i] = 0; + t_Succ[i].clear(); + t_Pred[i].clear(); + } + timeStamp = 0; + uint32_t t = 0; + //MarkSubGraph(s, t); + //return; + + while( s != t ) { + MarkSubGraph(DominatorTree::idom[t], t); + t = DominatorTree::idom[t]; + } + +} + +// return {marked nodes} +std::pair, + std::vector >markNodes(Function *F) { + assert(F->size() > 0 && "Function can not be empty"); + + reset(); + labelEachBlock(F); + buildCFG(F); + turnCFGintoDAG(F); + DominatorTree::DominatorTree(F); + MarkVertice(F); + + std::vector Result , ResultAbove; + for( uint32_t x : Markabove ) { + auto it = Marked.find( x ); + if( it != Marked.end() ) + Marked.erase( it ); + if( x ) + ResultAbove.push_back(Blocks[x]); + } + for( uint32_t x : Marked ) { + if (x == 0) { + continue; + } else { + Result.push_back(Blocks[x]); + } + } + + return { Result , ResultAbove }; +} diff --git a/llvm_mode/MarkNodes.h b/llvm_mode/MarkNodes.h new file mode 100644 index 00000000..e3bf3ce5 --- /dev/null +++ b/llvm_mode/MarkNodes.h @@ -0,0 +1,11 @@ +#ifndef __MARK_NODES__ +#define __MARK_NODES__ + +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include + +std::pair, + std::vector> markNodes(llvm::Function *F); + +#endif diff --git a/llvm_mode/afl-clang-fast.c b/llvm_mode/afl-clang-fast.c index 5bc4ae8c..2034f10a 100644 --- a/llvm_mode/afl-clang-fast.c +++ b/llvm_mode/afl-clang-fast.c @@ -32,6 +32,7 @@ #include #include #include +#include static u8* obj_path; /* Path to runtime libraries */ static u8** cc_params; /* Parameters passed to the real CC */ @@ -87,7 +88,7 @@ static void find_obj(u8* argv0) { return; } - FATAL("Unable to find 'afl-llvm-rt.o' or 'afl-llvm-pass.so'. Please set AFL_PATH"); + FATAL("Unable to find 'afl-llvm-rt.o' or 'libLLVMInsTrim.so'. Please set AFL_PATH"); } @@ -113,7 +114,7 @@ static void edit_params(u32 argc, char** argv) { } /* There are two ways to compile afl-clang-fast. In the traditional mode, we - use afl-llvm-pass.so to inject instrumentation. In the experimental + use libLLVMInsTrim.so to inject instrumentation. In the experimental 'trace-pc-guard' mode, we use native LLVM instrumentation callbacks instead. The latter is a very recent addition - see: @@ -150,7 +151,8 @@ static void edit_params(u32 argc, char** argv) { cc_params[cc_par_cnt++] = "-Xclang"; cc_params[cc_par_cnt++] = "-load"; cc_params[cc_par_cnt++] = "-Xclang"; - cc_params[cc_par_cnt++] = alloc_printf("%s/afl-llvm-pass.so", obj_path); + cc_params[cc_par_cnt++] = alloc_printf("%s/libLLVMInsTrim.so", obj_path); +// cc_params[cc_par_cnt++] = alloc_printf("%s/afl-llvm-pass.so", obj_path); #endif /* ^USE_TRACE_PC */ cc_params[cc_par_cnt++] = "-Qunused-arguments"; -- cgit 1.4.1 From 32525238238e96ec0ce64a36f70558f76bc90ff5 Mon Sep 17 00:00:00 2001 From: van Hauser Date: Mon, 15 Jul 2019 11:22:54 +0200 Subject: fixing commit fuckup --- Makefile | 2 +- docs/ChangeLog | 8 +++----- docs/README | 3 +-- docs/env_variables.txt | 22 +++++++++++++++++----- llvm_mode/LLVMInsTrim.so.cc | 2 +- llvm_mode/Makefile | 13 ++++++++----- llvm_mode/README.llvm | 19 ++++++++++++------- llvm_mode/afl-clang-fast.c | 16 +++++++++------- 8 files changed, 52 insertions(+), 33 deletions(-) (limited to 'llvm_mode/afl-clang-fast.c') diff --git a/Makefile b/Makefile index 60dfde18..6b580381 100644 --- a/Makefile +++ b/Makefile @@ -194,7 +194,7 @@ install: all rm -f $${DESTDIR}$(BIN_PATH)/afl-as if [ -f afl-qemu-trace ]; then install -m 755 afl-qemu-trace $${DESTDIR}$(BIN_PATH); fi ifndef AFL_TRACE_PC - if [ -f afl-clang-fast -a -f libLLVMInsTrim.so -a -f afl-llvm-rt.o ]; then set -e; install -m 755 afl-clang-fast $${DESTDIR}$(BIN_PATH); ln -sf afl-clang-fast $${DESTDIR}$(BIN_PATH)/afl-clang-fast++; install -m 755 libLLVMInsTrim.so afl-llvm-rt.o $${DESTDIR}$(HELPER_PATH); fi + if [ -f afl-clang-fast -a -f libLLVMInsTrim.so -a -f afl-llvm-rt.o ]; then set -e; install -m 755 afl-clang-fast $${DESTDIR}$(BIN_PATH); ln -sf afl-clang-fast $${DESTDIR}$(BIN_PATH)/afl-clang-fast++; install -m 755 libLLVMInsTrim.so afl-llvm-pass.so afl-llvm-rt.o $${DESTDIR}$(HELPER_PATH); fi else if [ -f afl-clang-fast -a -f afl-llvm-rt.o ]; then set -e; install -m 755 afl-clang-fast $${DESTDIR}$(BIN_PATH); ln -sf afl-clang-fast $${DESTDIR}$(BIN_PATH)/afl-clang-fast++; install -m 755 afl-llvm-rt.o $${DESTDIR}$(HELPER_PATH); fi endif diff --git a/docs/ChangeLog b/docs/ChangeLog index 9cdca49b..116029ea 100644 --- a/docs/ChangeLog +++ b/docs/ChangeLog @@ -17,9 +17,9 @@ sending a mail to . Version ++2.52d (tbd): ----------------------------- - - added instrim a much better llvm_mode instrumentation - (https://github.com/csienslab/instrim) - - added MOpt (github.com/puppet-meteor/MOpt-AFL) mode + - added instrim, a much faster llvm_mode instrumentation at the cost of + path discovery. See llvm_mode/README.instrim (https://github.com/csienslab/instrim) + - added MOpt (github.com/puppet-meteor/MOpt-AFL) mode, see docs/README.MOpt - added code to make it more portable to other platforms than Intel Linux - added never zero counters for afl-gcc and optional (because of an optimization issue in llvm < 9) for llvm_mode (AFL_LLVM_NEVER_ZERO=1) @@ -41,8 +41,6 @@ Version ++2.52d (tbd): tests as the random numbers are deterministic then - llvm_mode LAF_... env variables can now be specified as AFL_LLVM_LAF_... that is longer but in line with other llvm specific env vars - - ... your idea or patch? - ----------------------------- diff --git a/docs/README b/docs/README index 54e3e4a4..3a6c2921 100644 --- a/docs/README +++ b/docs/README @@ -23,8 +23,7 @@ american fuzzy lop plus plus https://github.com/puppet-meteor/MOpt-AFL Also newly integrated is instrim, a very effective CFG llvm_mode - instrumentation implementation which replaced the original afl one and is - from https://github.com/csienslab/instrim + instrumentation implementation from https://github.com/csienslab/instrim A more thorough list is available in the PATCHES file. diff --git a/docs/env_variables.txt b/docs/env_variables.txt index 8e2723d7..e58327b4 100644 --- a/docs/env_variables.txt +++ b/docs/env_variables.txt @@ -109,11 +109,21 @@ Then there are a few specific features that are only available in llvm_mode: See llvm_mode/README.whitelist for more information. - OTHER - ===== - - Setting LOOPHEAD=1 optimized loops. afl-fuzz will only be able to - see the path the loop took, but not how many times it was called - (unless its a complex loop). + INSTRIM + ======= + This feature increases the speed by whopping 20% but at the cost of a + lower path discovery and thefore coverage. + + - Setting AFL_LLVM_INSTRIM activates this mode + + - Setting AFL_LLVM_INSTRIM LOOPHEAD=1 expands on INSTRIM to optimize loops. + afl-fuzz will only be able to see the path the loop took, but not how + many times it was called (unless its a complex loop). + + See llvm_mode/README.instrim + + NOT_ZERO + ======== - Setting AFL_LLVM_NOT_ZERO=1 during compilation will use counters that skip zero on overflow. This is the default for llvm >= 9, @@ -121,6 +131,8 @@ Then there are a few specific features that are only available in llvm_mode: slowdown due a performance issue that is only fixed in llvm 9+. This feature increases path discovery by a little bit. + See llvm_mode/README.neverzero + 3) Settings for afl-fuzz ------------------------ diff --git a/llvm_mode/LLVMInsTrim.so.cc b/llvm_mode/LLVMInsTrim.so.cc index 8e9f7667..81cf98c4 100644 --- a/llvm_mode/LLVMInsTrim.so.cc +++ b/llvm_mode/LLVMInsTrim.so.cc @@ -96,7 +96,7 @@ namespace { OKF("LLVM neverZero activated (by hexcoder)\n"); #endif - if (getenv("LOOPHEAD")) { + if (getenv("AFL_LLVM_INSTRIM_LOOPHEAD") != NULL || getenv("LOOPHEAD") != NULL) { LoopHeadOpt = true; } diff --git a/llvm_mode/Makefile b/llvm_mode/Makefile index d0d4b690..2b685ddc 100644 --- a/llvm_mode/Makefile +++ b/llvm_mode/Makefile @@ -94,7 +94,7 @@ endif ifndef AFL_TRACE_PC - PROGS = ../afl-clang-fast ../libLLVMInsTrim.so ../afl-llvm-rt.o ../afl-llvm-rt-32.o ../afl-llvm-rt-64.o ../compare-transform-pass.so ../split-compares-pass.so ../split-switches-pass.so + PROGS = ../afl-clang-fast ../afl-llvm-pass.so ../libLLVMInsTrim.so ../afl-llvm-rt.o ../afl-llvm-rt-32.o ../afl-llvm-rt-64.o ../compare-transform-pass.so ../split-compares-pass.so ../split-switches-pass.so else PROGS = ../afl-clang-fast ../afl-llvm-rt.o ../afl-llvm-rt-32.o ../afl-llvm-rt-64.o ../compare-transform-pass.so ../split-compares-pass.so ../split-switches-pass.so endif @@ -104,7 +104,7 @@ ifneq "$(CLANGVER)" "$(LLVMVER)" CXX = $(shell llvm-config --bindir)/clang++ endif -all: test_deps test_shm $(PROGS) test_build all_done +all: test_shm test_deps $(PROGS) test_build all_done ifeq "$(SHMAT_OK)" "1" @@ -132,10 +132,10 @@ endif @which $(CC) >/dev/null 2>&1 || ( echo "[-] Oops, can't find '$(CC)'. Make sure that it's in your \$$PATH (or set \$$CC and \$$CXX)."; exit 1 ) @echo "[*] Checking for matching versions of '$(CC)' and '$(LLVM_CONFIG)'" ifneq "$(CLANGVER)" "$(LLVMVER)" - @echo "WARNING: we have llvm-config version $(LLVMVER) and a clang version $(CLANGVER)" - @echo "Retrying with the clang compiler from llvm: CC=`llvm-config --bindir`/clang" + @echo "[!] WARNING: we have llvm-config version $(LLVMVER) and a clang version $(CLANGVER)" + @echo "[!] Retrying with the clang compiler from llvm: CC=`llvm-config --bindir`/clang" else - @echo "we have llvm-config version $(LLVMVER) with a clang version $(CLANGVER), good." + @echo "[*] We have llvm-config version $(LLVMVER) with a clang version $(CLANGVER), good." endif @echo "[*] Checking for '../afl-showmap'..." @test -f ../afl-showmap || ( echo "[-] Oops, can't find '../afl-showmap'. Be sure to compile AFL first."; exit 1 ) @@ -148,6 +148,9 @@ endif ../libLLVMInsTrim.so: LLVMInsTrim.so.cc MarkNodes.cc | test_deps $(CXX) $(CLANG_CFL) -DLLVMInsTrim_EXPORTS -fno-rtti -fPIC -std=gnu++11 -shared $< MarkNodes.cc -o $@ $(CLANG_LFL) +../afl-llvm-pass.so: afl-llvm-pass.so.cc | test_deps + $(CXX) $(CLANG_CFL) -DLLVMInsTrim_EXPORTS -fno-rtti -fPIC -std=gnu++11 -shared $< -o $@ $(CLANG_LFL) + # laf ../split-switches-pass.so: split-switches-pass.so.cc | test_deps $(CXX) $(CLANG_CFL) -shared $< -o $@ $(CLANG_LFL) diff --git a/llvm_mode/README.llvm b/llvm_mode/README.llvm index 77c406f8..779ff47c 100644 --- a/llvm_mode/README.llvm +++ b/llvm_mode/README.llvm @@ -88,13 +88,18 @@ which C/C++ files to actually intrument. See README.whitelist For splitting memcmp, strncmp, etc. please see README.laf-intel -As the original afl llvm_mode implementation has been replaced with -then much more effective instrim (https://github.com/csienslab/instrim/) -there is an option for optimizing loops. This optimization shows which -part of the loop has been selected, but not how many time a loop has been -called in a row (unless its a complex loop and a block inside was -instrumented). If you want to enable this set the environment variable -LOOPHEAD=1 +Then there is an optimized instrumentation strategy that uses CFGs and +markers to just instrument what is needed. This increases speed by 20-25% +however has a lower path discovery. +If you want to use this, set AFL_LLVM_INSTRIM=1 +See README.instrim + +Finally if your llvm version is 8 or lower, you can activate a mode that +prevents that a counter overflow result in a 0 value. This is good for +path discovery, but the llvm implementation for intel for this functionality +is not optimal and was only fixed in llvm 9. +You can set this with AFL_LLVM_NOT_ZERO=1 +See README.neverzero 4) Gotchas, feedback, bugs diff --git a/llvm_mode/afl-clang-fast.c b/llvm_mode/afl-clang-fast.c index 249eea7d..19bad86c 100644 --- a/llvm_mode/afl-clang-fast.c +++ b/llvm_mode/afl-clang-fast.c @@ -88,7 +88,7 @@ static void find_obj(u8* argv0) { return; } - FATAL("Unable to find 'afl-llvm-rt.o' or 'libLLVMInsTrim.so'. Please set AFL_PATH"); + FATAL("Unable to find 'afl-llvm-rt.o' or 'afl-llvm-pass.so.cc'. Please set AFL_PATH"); } @@ -113,11 +113,11 @@ static void edit_params(u32 argc, char** argv) { cc_params[0] = alt_cc ? alt_cc : (u8*)"clang"; } - /* There are two ways to compile afl-clang-fast. In the traditional mode, we - use libLLVMInsTrim.so to inject instrumentation. In the experimental + /* There are three ways to compile with afl-clang-fast. In the traditional + mode, we use afl-llvm-pass.so, then there is libLLVMInsTrim.so which is + much faster but has less coverage. Finally tere is the experimental 'trace-pc-guard' mode, we use native LLVM instrumentation callbacks - instead. The latter is a very recent addition - see: - + instead. For trace-pc-guard see: http://clang.llvm.org/docs/SanitizerCoverage.html#tracing-pcs-with-guards */ // laf @@ -151,8 +151,10 @@ static void edit_params(u32 argc, char** argv) { cc_params[cc_par_cnt++] = "-Xclang"; cc_params[cc_par_cnt++] = "-load"; cc_params[cc_par_cnt++] = "-Xclang"; - cc_params[cc_par_cnt++] = alloc_printf("%s/libLLVMInsTrim.so", obj_path); -// cc_params[cc_par_cnt++] = alloc_printf("%s/afl-llvm-pass.so", obj_path); + if (getenv("AFL_LLVM_INSTRIM") != NULL || getenv("INSTRIM_LIB") != NULL) + cc_params[cc_par_cnt++] = alloc_printf("%s/libLLVMInsTrim.so", obj_path); + else + cc_params[cc_par_cnt++] = alloc_printf("%s/afl-llvm-pass.so", obj_path); #endif /* ^USE_TRACE_PC */ cc_params[cc_par_cnt++] = "-Qunused-arguments"; -- cgit 1.4.1 From ce842648ae0462f339625ab395a9d71a9ecd319d Mon Sep 17 00:00:00 2001 From: van Hauser Date: Thu, 25 Jul 2019 11:18:14 +0200 Subject: afl_trace_pc fix --- docs/ChangeLog | 1 + llvm_mode/afl-clang-fast.c | 7 ++++--- 2 files changed, 5 insertions(+), 3 deletions(-) (limited to 'llvm_mode/afl-clang-fast.c') diff --git a/docs/ChangeLog b/docs/ChangeLog index 3b43366d..09ad77ec 100644 --- a/docs/ChangeLog +++ b/docs/ChangeLog @@ -18,6 +18,7 @@ Version ++2.52d (dev): ----------------------------- - unicorn_mode got added - thanks to domenukk for the patch! + - fix llvm_mode AFL_TRACE_PC with modern llvm - fix a crash in qemu_mode which also exists in stock afl - added libcompcov, a laf-intel implementation for qemu! :) see qemu_mode/libcompcov/README.libcompcov diff --git a/llvm_mode/afl-clang-fast.c b/llvm_mode/afl-clang-fast.c index 19bad86c..a4bb7539 100644 --- a/llvm_mode/afl-clang-fast.c +++ b/llvm_mode/afl-clang-fast.c @@ -144,9 +144,10 @@ static void edit_params(u32 argc, char** argv) { // /laf #ifdef USE_TRACE_PC - cc_params[cc_par_cnt++] = "-fsanitize-coverage=trace-pc-guard"; - cc_params[cc_par_cnt++] = "-mllvm"; - cc_params[cc_par_cnt++] = "-sanitizer-coverage-block-threshold=0"; + cc_params[cc_par_cnt++] = "-fsanitize-coverage=trace-pc-guard"; // edge coverage by default + //cc_params[cc_par_cnt++] = "-mllvm"; + //cc_params[cc_par_cnt++] = "-fsanitize-coverage=trace-cmp,trace-div,trace-gep"; + //cc_params[cc_par_cnt++] = "-sanitizer-coverage-block-threshold=0"; #else cc_params[cc_par_cnt++] = "-Xclang"; cc_params[cc_par_cnt++] = "-load"; -- cgit 1.4.1