klee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UserSearcher.cpp
Go to the documentation of this file.
1 //===-- UserSearcher.cpp --------------------------------------------------===//
2 //
3 // The KLEE Symbolic Virtual Machine
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "Common.h"
11 
12 #include "UserSearcher.h"
13 
14 #include "Searcher.h"
15 #include "Executor.h"
16 
17 #include "llvm/Support/CommandLine.h"
18 
19 using namespace llvm;
20 using namespace klee;
21 
22 namespace {
23  cl::list<Searcher::CoreSearchType>
24  CoreSearch("search", cl::desc("Specify the search heuristic (default=random-path interleaved with nurs:covnew)"),
25  cl::values(clEnumValN(Searcher::DFS, "dfs", "use Depth First Search (DFS)"),
26  clEnumValN(Searcher::BFS, "bfs", "use Breadth First Search (BFS)"),
27  clEnumValN(Searcher::RandomState, "random-state", "randomly select a state to explore"),
28  clEnumValN(Searcher::RandomPath, "random-path", "use Random Path Selection (see OSDI'08 paper)"),
29  clEnumValN(Searcher::NURS_CovNew, "nurs:covnew", "use Non Uniform Random Search (NURS) with Coverage-New"),
30  clEnumValN(Searcher::NURS_MD2U, "nurs:md2u", "use NURS with Min-Dist-to-Uncovered"),
31  clEnumValN(Searcher::NURS_Depth, "nurs:depth", "use NURS with 2^depth"),
32  clEnumValN(Searcher::NURS_ICnt, "nurs:icnt", "use NURS with Instr-Count"),
33  clEnumValN(Searcher::NURS_CPICnt, "nurs:cpicnt", "use NURS with CallPath-Instr-Count"),
34  clEnumValN(Searcher::NURS_QC, "nurs:qc", "use NURS with Query-Cost"),
35  clEnumValEnd));
36 
37  cl::opt<bool>
38  UseIterativeDeepeningTimeSearch("use-iterative-deepening-time-search",
39  cl::desc("(experimental)"));
40 
41  cl::opt<bool>
42  UseBatchingSearch("use-batching-search",
43  cl::desc("Use batching searcher (keep running selected state for N instructions/time, see --batch-instructions and --batch-time)"),
44  cl::init(false));
45 
46  cl::opt<unsigned>
47  BatchInstructions("batch-instructions",
48  cl::desc("Number of instructions to batch when using --use-batching-search"),
49  cl::init(10000));
50 
51  cl::opt<double>
52  BatchTime("batch-time",
53  cl::desc("Amount of time to batch when using --use-batching-search"),
54  cl::init(5.0));
55 
56 
57  cl::opt<bool>
58  UseMerge("use-merge",
59  cl::desc("Enable support for klee_merge() (experimental)"));
60 
61  cl::opt<bool>
62  UseBumpMerge("use-bump-merge",
63  cl::desc("Enable support for klee_merge() (extra experimental)"));
64 
65 }
66 
67 
69  return (std::find(CoreSearch.begin(), CoreSearch.end(), Searcher::NURS_MD2U) != CoreSearch.end() ||
70  std::find(CoreSearch.begin(), CoreSearch.end(), Searcher::NURS_CovNew) != CoreSearch.end() ||
71  std::find(CoreSearch.begin(), CoreSearch.end(), Searcher::NURS_ICnt) != CoreSearch.end() ||
72  std::find(CoreSearch.begin(), CoreSearch.end(), Searcher::NURS_CPICnt) != CoreSearch.end() ||
73  std::find(CoreSearch.begin(), CoreSearch.end(), Searcher::NURS_QC) != CoreSearch.end());
74 }
75 
76 
78  Searcher *searcher = NULL;
79  switch (type) {
80  case Searcher::DFS: searcher = new DFSSearcher(); break;
81  case Searcher::BFS: searcher = new BFSSearcher(); break;
82  case Searcher::RandomState: searcher = new RandomSearcher(); break;
83  case Searcher::RandomPath: searcher = new RandomPathSearcher(executor); break;
84  case Searcher::NURS_CovNew: searcher = new WeightedRandomSearcher(WeightedRandomSearcher::CoveringNew); break;
85  case Searcher::NURS_MD2U: searcher = new WeightedRandomSearcher(WeightedRandomSearcher::MinDistToUncovered); break;
86  case Searcher::NURS_Depth: searcher = new WeightedRandomSearcher(WeightedRandomSearcher::Depth); break;
87  case Searcher::NURS_ICnt: searcher = new WeightedRandomSearcher(WeightedRandomSearcher::InstCount); break;
88  case Searcher::NURS_CPICnt: searcher = new WeightedRandomSearcher(WeightedRandomSearcher::CPInstCount); break;
89  case Searcher::NURS_QC: searcher = new WeightedRandomSearcher(WeightedRandomSearcher::QueryCost); break;
90  }
91 
92  return searcher;
93 }
94 
96 
97  // default values
98  if (CoreSearch.size() == 0) {
99  CoreSearch.push_back(Searcher::RandomPath);
100  CoreSearch.push_back(Searcher::NURS_CovNew);
101  }
102 
103  Searcher *searcher = getNewSearcher(CoreSearch[0], executor);
104 
105  if (CoreSearch.size() > 1) {
106  std::vector<Searcher *> s;
107  s.push_back(searcher);
108 
109  for (unsigned i=1; i<CoreSearch.size(); i++)
110  s.push_back(getNewSearcher(CoreSearch[i], executor));
111 
112  searcher = new InterleavedSearcher(s);
113  }
114 
115  if (UseBatchingSearch) {
116  searcher = new BatchingSearcher(searcher, BatchTime, BatchInstructions);
117  }
118 
119  // merge support is experimental
120  if (UseMerge) {
121  assert(!UseBumpMerge);
122  assert(std::find(CoreSearch.begin(), CoreSearch.end(), Searcher::RandomPath) == CoreSearch.end()); // XXX: needs further debugging: test/Features/Searchers.c fails with this searcher
123  searcher = new MergingSearcher(executor, searcher);
124  } else if (UseBumpMerge) {
125  searcher = new BumpMergingSearcher(executor, searcher);
126  }
127 
128  if (UseIterativeDeepeningTimeSearch) {
129  searcher = new IterativeDeepeningTimeSearcher(searcher);
130  }
131 
132  llvm::raw_ostream &os = executor.getHandler().getInfoStream();
133 
134  os << "BEGIN searcher description\n";
135  searcher->printName(os);
136  os << "END searcher description\n";
137 
138  return searcher;
139 }
Searcher * constructUserSearcher(Executor &executor)
virtual void printName(llvm::raw_ostream &os)
Definition: Searcher.h:45
virtual llvm::raw_ostream & getInfoStream() const =0
Searcher * getNewSearcher(Searcher::CoreSearchType type, Executor &executor)
const InterpreterHandler & getHandler()
Definition: Executor.h:401
bool userSearcherRequiresMD2U()