 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
17.9% |
7 / 39 |
| Generated: |
2009-05-17 22:47 |
|
Branches Executed: |
38.5% |
15 / 39 |
| |
|
Line Coverage: |
48.3% |
29 / 60 |
| |
 |
|
 |
1 : //===- Searcher.h - --*- C++ -*-===//
2 :
3 : #ifndef KLEE_SEARCHER_H
4 : #define KLEE_SEARCHER_H
5 :
6 : #include <vector>
7 : #include <set>
8 : #include <map>
9 : #include <queue>
10 :
11 : namespace llvm {
12 : class BasicBlock;
13 : class Function;
14 : class Instruction;
15 : }
16 :
17 : namespace klee {
18 : template<class T> class DiscretePDF;
19 : class ExecutionState;
20 : class Executor;
21 :
22 140: class Searcher {
23 : public:
24 : virtual ~Searcher();
25 :
26 : virtual ExecutionState &selectState() = 0;
27 :
28 : virtual void update(ExecutionState *current,
29 : const std::set<ExecutionState*> &addedStates,
30 : const std::set<ExecutionState*> &removedStates) = 0;
31 :
32 : virtual bool empty() = 0;
33 :
34 : // prints name of searcher as a klee_message()
35 : // TODO: could probably make prettier or more flexible
36 0: virtual void printName() {klee_message("<unnamed searcher>");};
37 :
38 : // pgbovine - to be called when a searcher gets activated and
39 : // deactivated, say, by a higher-level searcher; most searchers
40 : // don't need this functionality, so don't have to override.
41 0: virtual void activate() {};
42 0: virtual void deactivate() {};
43 :
44 : // utility functions
45 :
46 210: void addState(ExecutionState *es, ExecutionState *current = 0) {
47 : std::set<ExecutionState*> tmp;
48 210: tmp.insert(es);
49 420: update(current, tmp, std::set<ExecutionState*>());
50 210: }
51 :
52 80: void removeState(ExecutionState *es, ExecutionState *current = 0) {
53 : std::set<ExecutionState*> tmp;
54 80: tmp.insert(es);
55 160: update(current, std::set<ExecutionState*>(), tmp);
56 80: }
57 : };
58 :
86: branch 2 taken
0: branch 3 not taken
0: branch 7 not taken
0: branch 8 not taken
59 258: class DFSSearcher : public Searcher {
60 : std::vector<ExecutionState*> states;
61 :
62 : public:
63 : ExecutionState &selectState();
64 : void update(ExecutionState *current,
65 : const std::set<ExecutionState*> &addedStates,
66 : const std::set<ExecutionState*> &removedStates);
67 2262: bool empty() { return states.empty(); }
68 82: void printName() {klee_message("DFSSearcher");};
69 : };
70 :
71 : // pg - experiment with various things for educational purposes :)
0: branch 2 not taken
0: branch 3 not taken
0: branch 7 not taken
0: branch 8 not taken
72 0: class PGSearcher : public Searcher {
73 : private:
74 : std::vector<ExecutionState*> states;
75 :
76 : // TRUE iff this searcher is actively being used to select states
77 : // starts off active BY DEFAULT
78 : bool isActive;
79 :
80 : // if isActive, stubbornly run this one state until it terminates
81 : ExecutionState* currentlyRunning;
82 :
83 : public:
84 0: PGSearcher() : isActive(true), currentlyRunning(NULL) {};
85 : ExecutionState &selectState();
86 : void update(ExecutionState *current,
87 : const std::set<ExecutionState*> &addedStates,
88 : const std::set<ExecutionState*> &removedStates);
89 : void activate();
90 : void deactivate();
91 0: bool empty() { return states.empty(); }
92 0: void printName() {klee_message("PGSearcher");};
93 : };
94 :
95 :
96 : // pg - experiment with alternating searchers based upon the
97 : // performance of each one - the underlying intuition is to use one
98 : // searcher until it seems to be flattening out and running out of
99 : // steam, and then to run the next one
100 : class PGSupervisedSearcher : public Searcher {
101 : typedef std::vector<Searcher*> searchers_ty;
102 :
103 : // start execution with the first searcher and then round-robin
104 : // when it seems to start sucking, based on metrics of sucking
105 : // as defined below ...
106 : searchers_ty searchers;
107 :
108 : // must be in-bounds of searchers vector:
109 : unsigned index;
110 :
111 :
112 : // metrics to use to determine whether the current searcher is
113 : // sucking or not ...
114 :
115 : // total number of states that have terminated thus far:
116 : unsigned numTerminatedStates;
117 : // those that have covered new (relevant) code:
118 : unsigned numTerminatedCovnewStates;
119 :
120 : // same as above, except reset whenever searcher switches
121 : unsigned numTerminatedStatesCurSearcher;
122 : unsigned numTerminatedCovnewStatesCurSearcher;
123 :
124 : // number of terminated states that covered new code from the LAST
125 : // time that the searcher with that index ran
126 : std::vector<unsigned> numTerminatedCovnewStatesLastSearcher;
127 :
128 : // how many seconds to allow this search to go on for
129 : // without achieving new coverage ...
130 : std::vector<unsigned> timeoutForSearcher;
131 :
132 : // number of terminated states that have elapsed without
133 : // achieving new coverage:
134 : unsigned numTermStatesSinceNewCov;
135 :
136 : // switching based on time is important since PGSearcher might be
137 : // stuck on a particularly nasty state with constraints that take
138 : // forever to solve or other weird environmental slowness issues
139 :
140 : // last wall clock time in which a terminated state
141 : // achieved new coverage (units should be in seconds, I think)
142 : double lastTimeTermStateHadNewCov;
143 :
144 : double approxStartTime;
145 :
146 : // TODO: discount the past like networking and only consider recent
147 : // performance (e.g., how much new coverage have you gotten in the
148 : // past 50 terminated states?)
149 :
150 : public:
151 : PGSupervisedSearcher(const std::vector<Searcher*> &_searchers);
152 : ~PGSupervisedSearcher();
153 :
154 : ExecutionState &selectState();
155 : void update(ExecutionState *current,
156 : const std::set<ExecutionState*> &addedStates,
157 : const std::set<ExecutionState*> &removedStates);
158 0: bool empty() { return searchers[0]->empty(); }
159 0: void printName() {
160 : klee_message("<PGSupervisedSearcher> containing %u searchers:",
161 0: (unsigned) searchers.size());
0: branch 0 not taken
0: branch 1 not taken
162 0: for (searchers_ty::iterator it = searchers.begin(), ie = searchers.end();
163 : it != ie; ++it)
164 0: (*it)->printName();
165 0: klee_message("</PGSupervisedSearcher>");
166 0: }
167 : };
168 :
169 :
7: branch 2 taken
0: branch 3 not taken
0: branch 7 not taken
0: branch 8 not taken
170 21: class RandomSearcher : public Searcher {
171 : std::vector<ExecutionState*> states;
172 :
173 : public:
174 : ExecutionState &selectState();
175 : void update(ExecutionState *current,
176 : const std::set<ExecutionState*> &addedStates,
177 : const std::set<ExecutionState*> &removedStates);
178 1672: bool empty() { return states.empty(); }
179 4: void printName() {klee_message("RandomSearcher");};
180 : };
181 :
182 : class WeightedRandomSearcher : public Searcher {
183 : public:
184 : enum WeightType {
185 : Depth,
186 : QueryCost,
187 : InstCount,
188 : CPInstCount,
189 : MinDistToUncovered,
190 : CoveringNew
191 : };
192 :
193 : private:
194 : Executor &executor;
195 : DiscretePDF<ExecutionState*> *states;
196 : WeightType type;
197 : bool updateWeights;
198 :
199 : double getWeight(ExecutionState*);
200 :
201 : public:
202 : WeightedRandomSearcher(Executor &executor, WeightType type);
203 : ~WeightedRandomSearcher();
204 :
205 : ExecutionState &selectState();
206 : void update(ExecutionState *current,
207 : const std::set<ExecutionState*> &addedStates,
208 : const std::set<ExecutionState*> &removedStates);
209 : bool empty();
210 4: void printName() {
2: branch 0 taken
2: branch 1 taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
0: branch 6 not taken
211 4: switch(type) {
212 : case Depth:
213 2: klee_message("WeightedRandomSearcher::Depth"); return;
214 : case QueryCost:
215 2: klee_message("WeightedRandomSearcher::QueryCost"); return;
216 : case InstCount:
217 0: klee_message("WeightedRandomSearcher::InstCount"); return;
218 : case CPInstCount:
219 0: klee_message("WeightedRandomSearcher::CPInstCount"); return;
220 : case MinDistToUncovered:
221 0: klee_message("WeightedRandomSearcher::MinDistToUncovered"); return;
222 : case CoveringNew:
223 0: klee_message("WeightedRandomSearcher::CoveringNew"); return;
224 : default:
225 0: klee_message("WeightedRandomSearcher::<unknown type>"); return;
226 : }
227 : };
228 : };
229 :
230 : class RandomPathSearcher : public Searcher {
231 : Executor &executor;
232 :
233 : public:
234 : RandomPathSearcher(Executor &_executor);
235 : ~RandomPathSearcher();
236 :
237 : ExecutionState &selectState();
238 : void update(ExecutionState *current,
239 : const std::set<ExecutionState*> &addedStates,
240 : const std::set<ExecutionState*> &removedStates);
241 : bool empty();
242 0: void printName() {klee_message("RandomPathSearcher");};
243 : };
244 :
245 : class MergingSearcher : public Searcher {
246 : Executor &executor;
247 : std::set<ExecutionState*> statesAtMerge;
248 : Searcher *baseSearcher;
249 : llvm::Function *mergeFunction;
250 :
251 : private:
252 : llvm::Instruction *getMergePoint(ExecutionState &es);
253 :
254 : public:
255 : MergingSearcher(Executor &executor, Searcher *baseSearcher);
256 : ~MergingSearcher();
257 :
258 : ExecutionState &selectState();
259 : void update(ExecutionState *current,
260 : const std::set<ExecutionState*> &addedStates,
261 : const std::set<ExecutionState*> &removedStates);
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
262 0: bool empty() { return baseSearcher->empty() && statesAtMerge.empty(); }
263 5: void printName() {klee_message("MergingSearcher (TODO: can print more details)");}
264 : };
265 :
266 : class BumpMergingSearcher : public Searcher {
267 : Executor &executor;
268 : std::map<llvm::Instruction*, ExecutionState*> statesAtMerge;
269 : Searcher *baseSearcher;
270 : llvm::Function *mergeFunction;
271 :
272 : private:
273 : llvm::Instruction *getMergePoint(ExecutionState &es);
274 :
275 : public:
276 : BumpMergingSearcher(Executor &executor, Searcher *baseSearcher);
277 : ~BumpMergingSearcher();
278 :
279 : ExecutionState &selectState();
280 : void update(ExecutionState *current,
281 : const std::set<ExecutionState*> &addedStates,
282 : const std::set<ExecutionState*> &removedStates);
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
283 0: bool empty() { return baseSearcher->empty() && statesAtMerge.empty(); }
284 0: void printName() {klee_message("BumpMergingSearcher (TODO: can print more details)");}
285 : };
286 :
287 : class BatchingSearcher : public Searcher {
288 : Searcher *baseSearcher;
289 : double timeBudget;
290 : unsigned instructionBudget;
291 :
292 : ExecutionState *lastState;
293 : double lastStartTime;
294 : unsigned lastStartInstructions;
295 :
296 : public:
297 : BatchingSearcher(Searcher *baseSearcher,
298 : double _timeBudget,
299 : unsigned _instructionBudget);
300 : ~BatchingSearcher();
301 :
302 : ExecutionState &selectState();
303 : void update(ExecutionState *current,
304 : const std::set<ExecutionState*> &addedStates,
305 : const std::set<ExecutionState*> &removedStates);
306 3144: bool empty() { return baseSearcher->empty(); }
307 8: void printName() {
308 8: klee_message("<BatchingSearcher> timeBudget: %.3g, instructionBudget: %u, baseSearcher:", timeBudget, instructionBudget);
309 8: baseSearcher->printName();
310 8: klee_message("</BatchingSearcher>");
311 8: }
312 : };
313 :
314 : class OwningSearcher : public Searcher {
315 : Executor &executor;
316 : Searcher *baseSearcher;
317 : std::map<ExecutionState*, std::set<llvm::BasicBlock*> > bbMap;
318 : unsigned unpausedStates;
319 : std::set<ExecutionState*> deadStates;
320 :
321 : private:
322 : void printMap();
323 : void resurrect(std::set<llvm::BasicBlock*> &bbs);
324 : void splitStates(std::set<llvm::BasicBlock*> &bbs,
325 : std::set<ExecutionState*> &states);
326 :
327 : public:
328 : OwningSearcher(Executor &executor, Searcher *baseSearcher);
329 : ~OwningSearcher();
330 :
331 : ExecutionState &selectState();
332 : void update(ExecutionState *current,
333 : const std::set<ExecutionState*> &addedStates,
334 : const std::set<ExecutionState*> &removedStates);
8: branch 1 taken
3136: branch 2 taken
8: branch 3 taken
0: branch 4 not taken
335 3152: bool empty() { return baseSearcher->empty() && deadStates.empty(); }
336 4: void printName() {klee_message("OwningSearcher (TODO: can print more details)");}
337 : };
338 :
339 : class IterativeDeepeningTimeSearcher : public Searcher {
340 : Searcher *baseSearcher;
341 : double time, startTime;
342 : std::set<ExecutionState*> pausedStates;
343 :
344 : public:
345 : IterativeDeepeningTimeSearcher(Searcher *baseSearcher);
346 : ~IterativeDeepeningTimeSearcher();
347 :
348 : ExecutionState &selectState();
349 : void update(ExecutionState *current,
350 : const std::set<ExecutionState*> &addedStates,
351 : const std::set<ExecutionState*> &removedStates);
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
352 0: bool empty() { return baseSearcher->empty() && pausedStates.empty(); }
353 4: void printName() {klee_message("IterativeDeepeningTimeSearcher (TODO: can print more details)");}
354 : };
355 :
356 : class InterleavedSearcher : public Searcher {
357 : typedef std::vector<Searcher*> searchers_ty;
358 :
359 : searchers_ty searchers;
360 : unsigned index;
361 :
362 : public:
363 : explicit InterleavedSearcher(const searchers_ty &_searchers);
364 : ~InterleavedSearcher();
365 :
366 : ExecutionState &selectState();
367 : void update(ExecutionState *current,
368 : const std::set<ExecutionState*> &addedStates,
369 : const std::set<ExecutionState*> &removedStates);
370 0: bool empty() { return searchers[0]->empty(); }
371 0: void printName() {
372 : klee_message("<InterleavedSearcher> containing %u searchers:",
373 0: (unsigned) searchers.size());
0: branch 0 not taken
0: branch 1 not taken
374 0: for (searchers_ty::iterator it = searchers.begin(), ie = searchers.end();
375 : it != ie; ++it)
376 0: (*it)->printName();
377 0: klee_message("</InterleavedSearcher>");
378 0: }
379 : };
380 :
381 : }
382 :
383 : #endif
Generated: 2009-05-17 22:47 by zcov