klee
SpecialFunctionHandler.cpp
Go to the documentation of this file.
1//===-- SpecialFunctionHandler.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
11
12#include "ExecutionState.h"
13#include "Executor.h"
14#include "Memory.h"
15#include "MemoryManager.h"
16#include "MergeHandler.h"
17#include "Searcher.h"
18#include "StatsTracker.h"
19#include "TimingSolver.h"
20
21#include "klee/Config/config.h"
23#include "klee/Module/KModule.h"
26#include "klee/Support/Debug.h"
29
30#include "llvm/ADT/Twine.h"
31#include "llvm/IR/DataLayout.h"
32#include "llvm/IR/Instructions.h"
33#include "llvm/IR/Module.h"
34
35#include <errno.h>
36#include <sstream>
37
38using namespace llvm;
39using namespace klee;
40
41namespace {
42cl::opt<bool>
43 ReadablePosix("readable-posix-inputs", cl::init(false),
44 cl::desc("Prefer creation of POSIX inputs (command-line "
45 "arguments, files, etc.) with human readable bytes. "
46 "Note: option is expensive when creating lots of "
47 "tests (default=false)"),
48 cl::cat(TestGenCat));
49
50cl::opt<bool>
51 SilentKleeAssume("silent-klee-assume", cl::init(false),
52 cl::desc("Silently terminate paths with an infeasible "
53 "condition given to klee_assume() rather than "
54 "emitting an error (default=false)"),
55 cl::cat(TerminationCat));
56} // namespace
57
60
62
63// FIXME: We are more or less committed to requiring an intrinsic
64// library these days. We can move some of this stuff there,
65// especially things like realloc which have complicated semantics
66// w.r.t. forking. Among other things this makes delayed query
67// dispatch easier to implement.
69#define add(name, handler, ret) { name, \
70 &SpecialFunctionHandler::handler, \
71 false, ret, false }
72#define addDNR(name, handler) { name, \
73 &SpecialFunctionHandler::handler, \
74 true, false, false }
75 addDNR("__assert_rtn", handleAssertFail),
76 addDNR("__assert_fail", handleAssertFail),
77 addDNR("__assert", handleAssertFail),
78 addDNR("_assert", handleAssert),
79 addDNR("abort", handleAbort),
80 addDNR("_exit", handleExit),
81 { "exit", &SpecialFunctionHandler::handleExit, true, false, true },
82 addDNR("klee_abort", handleAbort),
83 addDNR("klee_silent_exit", handleSilentExit),
84 addDNR("klee_report_error", handleReportError),
85 add("calloc", handleCalloc, true),
86 add("free", handleFree, false),
87 add("klee_assume", handleAssume, false),
88 add("klee_check_memory_access", handleCheckMemoryAccess, false),
89 add("klee_get_valuef", handleGetValue, true),
90 add("klee_get_valued", handleGetValue, true),
91 add("klee_get_valuel", handleGetValue, true),
92 add("klee_get_valuell", handleGetValue, true),
93 add("klee_get_value_i32", handleGetValue, true),
94 add("klee_get_value_i64", handleGetValue, true),
95 add("klee_define_fixed_object", handleDefineFixedObject, false),
96 add("klee_get_obj_size", handleGetObjSize, true),
97 add("klee_get_errno", handleGetErrno, true),
98#ifndef __APPLE__
99 add("__errno_location", handleErrnoLocation, true),
100#else
101 add("__error", handleErrnoLocation, true),
102#endif
103 add("klee_is_symbolic", handleIsSymbolic, true),
104 add("klee_make_symbolic", handleMakeSymbolic, false),
105 add("klee_mark_global", handleMarkGlobal, false),
106 add("klee_open_merge", handleOpenMerge, false),
107 add("klee_close_merge", handleCloseMerge, false),
108 add("klee_prefer_cex", handlePreferCex, false),
109 add("klee_posix_prefer_cex", handlePosixPreferCex, false),
110 add("klee_print_expr", handlePrintExpr, false),
111 add("klee_print_range", handlePrintRange, false),
112 add("klee_set_forking", handleSetForking, false),
113 add("klee_stack_trace", handleStackTrace, false),
114 add("klee_warning", handleWarning, false),
115 add("klee_warning_once", handleWarningOnce, false),
116 add("malloc", handleMalloc, true),
117 add("memalign", handleMemalign, true),
118 add("realloc", handleRealloc, true),
119
120#ifdef SUPPORT_KLEE_EH_CXX
121 add("_klee_eh_Unwind_RaiseException_impl", handleEhUnwindRaiseExceptionImpl, false),
122 add("klee_eh_typeid_for", handleEhTypeid, true),
123#endif
124
125 // operator delete[](void*)
126 add("_ZdaPv", handleDeleteArray, false),
127 // operator delete(void*)
128 add("_ZdlPv", handleDelete, false),
129
130 // operator new[](unsigned int)
131 add("_Znaj", handleNewArray, true),
132 // operator new(unsigned int)
133 add("_Znwj", handleNew, true),
134
135 // FIXME-64: This is wrong for 64-bit long...
136
137 // operator new[](unsigned long)
138 add("_Znam", handleNewArray, true),
139 // operator new(unsigned long)
140 add("_Znwm", handleNew, true),
141
142 // Run clang with -fsanitize=signed-integer-overflow and/or
143 // -fsanitize=unsigned-integer-overflow
144 add("__ubsan_handle_add_overflow", handleAddOverflow, false),
145 add("__ubsan_handle_sub_overflow", handleSubOverflow, false),
146 add("__ubsan_handle_mul_overflow", handleMulOverflow, false),
147 add("__ubsan_handle_divrem_overflow", handleDivRemOverflow, false),
148
149#undef addDNR
150#undef add
151};
152
153SpecialFunctionHandler::const_iterator SpecialFunctionHandler::begin() {
155}
156
158 // NULL pointer is sentinel
160}
161
163 ++index;
165 {
166 // Out of range, return .end()
167 base=0; // Sentinel
168 index=0;
169 }
170
171 return *this;
172}
173
175 return sizeof(handlerInfo)/sizeof(handlerInfo[0]);
176}
177
179 : executor(_executor) {}
180
182 std::vector<const char *> &preservedFunctions) {
183 unsigned N = size();
184
185 for (unsigned i=0; i<N; ++i) {
186 HandlerInfo &hi = handlerInfo[i];
187 Function *f = executor.kmodule->module->getFunction(hi.name);
188
189 // No need to create if the function doesn't exist, since it cannot
190 // be called in that case.
191 if (f && (!hi.doNotOverride || f->isDeclaration())) {
192 preservedFunctions.push_back(hi.name);
193 // Make sure NoReturn attribute is set, for optimization and
194 // coverage counting.
195 if (hi.doesNotReturn)
196 f->addFnAttr(Attribute::NoReturn);
197
198 // Change to a declaration since we handle internally (simplifies
199 // module and allows deleting dead code).
200 if (!f->isDeclaration())
201 f->deleteBody();
202 }
203 }
204}
205
207 unsigned N = sizeof(handlerInfo)/sizeof(handlerInfo[0]);
208
209 for (unsigned i=0; i<N; ++i) {
210 HandlerInfo &hi = handlerInfo[i];
211 Function *f = executor.kmodule->module->getFunction(hi.name);
212
213 if (f && (!hi.doNotOverride || f->isDeclaration()))
214 handlers[f] = std::make_pair(hi.handler, hi.hasReturnValue);
215 }
216}
217
218
220 Function *f,
221 KInstruction *target,
222 std::vector< ref<Expr> > &arguments) {
223 handlers_ty::iterator it = handlers.find(f);
224 if (it != handlers.end()) {
225 Handler h = it->second.first;
226 bool hasReturnValue = it->second.second;
227 // FIXME: Check this... add test?
228 if (!hasReturnValue && !target->inst->use_empty()) {
230 "expected return value from void special function");
231 } else {
232 (this->*h)(state, target, arguments);
233 }
234 return true;
235 } else {
236 return false;
237 }
238}
239
240/****/
241
242// reads a concrete string from memory
243std::string
245 ref<Expr> addressExpr) {
246 ObjectPair op;
247 addressExpr = executor.toUnique(state, addressExpr);
248 if (!isa<ConstantExpr>(addressExpr)) {
250 state, "Symbolic string pointer passed to one of the klee_ functions");
251 return "";
252 }
253 ref<ConstantExpr> address = cast<ConstantExpr>(addressExpr);
254 if (!state.addressSpace.resolveOne(address, op)) {
256 state, "Invalid string pointer passed to one of the klee_ functions");
257 return "";
258 }
259 const MemoryObject *mo = op.first;
260 const ObjectState *os = op.second;
261
262 auto relativeOffset = mo->getOffsetExpr(address);
263 // the relativeOffset must be concrete as the address is concrete
264 size_t offset = cast<ConstantExpr>(relativeOffset)->getZExtValue();
265
266 std::ostringstream buf;
267 char c = 0;
268 for (size_t i = offset; i < mo->size; ++i) {
269 ref<Expr> cur = os->read8(i);
270 cur = executor.toUnique(state, cur);
271 assert(isa<ConstantExpr>(cur) &&
272 "hit symbolic char while reading concrete string");
273 c = cast<ConstantExpr>(cur)->getZExtValue(8);
274 if (c == '\0') {
275 // we read the whole string
276 break;
277 }
278
279 buf << c;
280 }
281
282 if (c != '\0') {
283 klee_warning_once(0, "String not terminated by \\0 passed to "
284 "one of the klee_ functions");
285 }
286
287 return buf.str();
288}
289
290/****/
291
292void SpecialFunctionHandler::handleAbort(ExecutionState &state,
293 KInstruction *target,
294 std::vector<ref<Expr>> &arguments) {
295 assert(arguments.size() == 0 && "invalid number of arguments to abort");
296 executor.terminateStateOnError(state, "abort failure",
297 StateTerminationType::Abort);
298}
299
300void SpecialFunctionHandler::handleExit(ExecutionState &state,
301 KInstruction *target,
302 std::vector<ref<Expr>> &arguments) {
303 assert(arguments.size() == 1 && "invalid number of arguments to exit");
305}
306
307void SpecialFunctionHandler::handleSilentExit(
308 ExecutionState &state, KInstruction *target,
309 std::vector<ref<Expr>> &arguments) {
310 assert(arguments.size() == 1 && "invalid number of arguments to exit");
311 executor.terminateStateEarly(state, "", StateTerminationType::SilentExit);
312}
313
314void SpecialFunctionHandler::handleAssert(ExecutionState &state,
315 KInstruction *target,
316 std::vector<ref<Expr>> &arguments) {
317 assert(arguments.size() == 3 && "invalid number of arguments to _assert");
319 state, "ASSERTION FAIL: " + readStringAtAddress(state, arguments[0]),
320 StateTerminationType::Assert);
321}
322
323void SpecialFunctionHandler::handleAssertFail(
324 ExecutionState &state, KInstruction *target,
325 std::vector<ref<Expr>> &arguments) {
326 assert(arguments.size() == 4 &&
327 "invalid number of arguments to __assert_fail");
329 state, "ASSERTION FAIL: " + readStringAtAddress(state, arguments[0]),
330 StateTerminationType::Assert);
331}
332
333void SpecialFunctionHandler::handleReportError(
334 ExecutionState &state, KInstruction *target,
335 std::vector<ref<Expr>> &arguments) {
336 assert(arguments.size() == 4 &&
337 "invalid number of arguments to klee_report_error");
338
339 // arguments[0,1,2,3] are file, line, message, suffix
341 state, readStringAtAddress(state, arguments[2]),
342 StateTerminationType::ReportError, "",
343 readStringAtAddress(state, arguments[3]).c_str());
344}
345
346void SpecialFunctionHandler::handleOpenMerge(ExecutionState &state,
347 KInstruction *target,
348 std::vector<ref<Expr> > &arguments) {
349 if (!UseMerge) {
350 klee_warning_once(0, "klee_open_merge ignored, use '-use-merge'");
351 return;
352 }
353
354 state.openMergeStack.push_back(
356
357 if (DebugLogMerge)
358 llvm::errs() << "open merge: " << &state << "\n";
359}
360
361void SpecialFunctionHandler::handleCloseMerge(ExecutionState &state,
362 KInstruction *target,
363 std::vector<ref<Expr> > &arguments) {
364 if (!UseMerge) {
365 klee_warning_once(0, "klee_close_merge ignored, use '-use-merge'");
366 return;
367 }
368 Instruction *i = target->inst;
369
370 if (DebugLogMerge)
371 llvm::errs() << "close merge: " << &state << " at [" << *i << "]\n";
372
373 if (state.openMergeStack.empty()) {
374 std::ostringstream warning;
375 warning << &state << " ran into a close at " << i << " without a preceding open";
376 klee_warning("%s", warning.str().c_str());
377 } else {
378 assert(executor.mergingSearcher->inCloseMerge.find(&state) ==
380 "State cannot run into close_merge while being closed");
381 executor.mergingSearcher->inCloseMerge.insert(&state);
382 state.openMergeStack.back()->addClosedState(&state, i);
383 state.openMergeStack.pop_back();
384 }
385}
386
387void SpecialFunctionHandler::handleNew(ExecutionState &state,
388 KInstruction *target,
389 std::vector<ref<Expr> > &arguments) {
390 // XXX should type check args
391 assert(arguments.size()==1 && "invalid number of arguments to new");
392
393 executor.executeAlloc(state, arguments[0], false, target);
394}
395
396void SpecialFunctionHandler::handleDelete(ExecutionState &state,
397 KInstruction *target,
398 std::vector<ref<Expr> > &arguments) {
399 // FIXME: Should check proper pairing with allocation type (malloc/free,
400 // new/delete, new[]/delete[]).
401
402 // XXX should type check args
403 assert(arguments.size()==1 && "invalid number of arguments to delete");
404 executor.executeFree(state, arguments[0]);
405}
406
407void SpecialFunctionHandler::handleNewArray(ExecutionState &state,
408 KInstruction *target,
409 std::vector<ref<Expr> > &arguments) {
410 // XXX should type check args
411 assert(arguments.size()==1 && "invalid number of arguments to new[]");
412 executor.executeAlloc(state, arguments[0], false, target);
413}
414
415void SpecialFunctionHandler::handleDeleteArray(ExecutionState &state,
416 KInstruction *target,
417 std::vector<ref<Expr> > &arguments) {
418 // XXX should type check args
419 assert(arguments.size()==1 && "invalid number of arguments to delete[]");
420 executor.executeFree(state, arguments[0]);
421}
422
423void SpecialFunctionHandler::handleMalloc(ExecutionState &state,
424 KInstruction *target,
425 std::vector<ref<Expr> > &arguments) {
426 // XXX should type check args
427 assert(arguments.size()==1 && "invalid number of arguments to malloc");
428 executor.executeAlloc(state, arguments[0], false, target);
429}
430
431void SpecialFunctionHandler::handleMemalign(ExecutionState &state,
432 KInstruction *target,
433 std::vector<ref<Expr>> &arguments) {
434 if (arguments.size() != 2) {
436 "Incorrect number of arguments to memalign(size_t alignment, size_t size)");
437 return;
438 }
439
440 std::pair<ref<Expr>, ref<Expr>> alignmentRangeExpr =
441 executor.solver->getRange(state.constraints, arguments[0],
442 state.queryMetaData);
443 ref<Expr> alignmentExpr = alignmentRangeExpr.first;
444 auto alignmentConstExpr = dyn_cast<ConstantExpr>(alignmentExpr);
445
446 if (!alignmentConstExpr) {
447 executor.terminateStateOnUserError(state, "Could not determine size of symbolic alignment");
448 return;
449 }
450
451 uint64_t alignment = alignmentConstExpr->getZExtValue();
452
453 // Warn, if the expression has more than one solution
454 if (alignmentRangeExpr.first != alignmentRangeExpr.second) {
456 0, "Symbolic alignment for memalign. Choosing smallest alignment");
457 }
458
459 executor.executeAlloc(state, arguments[1], false, target, false, 0,
460 alignment);
461}
462
463#ifdef SUPPORT_KLEE_EH_CXX
464void SpecialFunctionHandler::handleEhUnwindRaiseExceptionImpl(
465 ExecutionState &state, KInstruction *target,
466 std::vector<ref<Expr>> &arguments) {
467 assert(arguments.size() == 1 &&
468 "invalid number of arguments to _klee_eh_Unwind_RaiseException_impl");
469
470 ref<ConstantExpr> exceptionObject = dyn_cast<ConstantExpr>(arguments[0]);
471 if (!exceptionObject.get()) {
472 executor.terminateStateOnExecError(state, "Internal error: Symbolic exception pointer");
473 return;
474 }
475
476 if (isa_and_nonnull<SearchPhaseUnwindingInformation>(
477 state.unwindingInformation.get())) {
479 state,
480 "Internal error: Unwinding restarted during an ongoing search phase");
481 return;
482 }
483
485 std::make_unique<SearchPhaseUnwindingInformation>(exceptionObject,
486 state.stack.size() - 1);
487
489}
490
491void SpecialFunctionHandler::handleEhTypeid(ExecutionState &state,
492 KInstruction *target,
493 std::vector<ref<Expr>> &arguments) {
494 assert(arguments.size() == 1 &&
495 "invalid number of arguments to klee_eh_typeid_for");
496
497 executor.bindLocal(target, state, executor.getEhTypeidFor(arguments[0]));
498}
499#endif // SUPPORT_KLEE_EH_CXX
500
501void SpecialFunctionHandler::handleAssume(ExecutionState &state,
502 KInstruction *target,
503 std::vector<ref<Expr> > &arguments) {
504 assert(arguments.size()==1 && "invalid number of arguments to klee_assume");
505
506 ref<Expr> e = arguments[0];
507
508 if (e->getWidth() != Expr::Bool)
509 e = NeExpr::create(e, ConstantExpr::create(0, e->getWidth()));
510
511 bool res;
512 bool success __attribute__((unused)) = executor.solver->mustBeFalse(
513 state.constraints, e, res, state.queryMetaData);
514 assert(success && "FIXME: Unhandled solver failure");
515 if (res) {
516 if (SilentKleeAssume) {
518 } else {
520 state, "invalid klee_assume call (provably false)");
521 }
522 } else {
523 executor.addConstraint(state, e);
524 }
525}
526
527void SpecialFunctionHandler::handleIsSymbolic(ExecutionState &state,
528 KInstruction *target,
529 std::vector<ref<Expr> > &arguments) {
530 assert(arguments.size()==1 && "invalid number of arguments to klee_is_symbolic");
531
532 executor.bindLocal(target, state,
533 ConstantExpr::create(!isa<ConstantExpr>(arguments[0]),
534 Expr::Int32));
535}
536
537void SpecialFunctionHandler::handlePreferCex(ExecutionState &state,
538 KInstruction *target,
539 std::vector<ref<Expr> > &arguments) {
540 assert(arguments.size()==2 &&
541 "invalid number of arguments to klee_prefex_cex");
542
543 ref<Expr> cond = arguments[1];
544 if (cond->getWidth() != Expr::Bool)
545 cond = NeExpr::create(cond, ConstantExpr::alloc(0, cond->getWidth()));
546
547 state.addCexPreference(cond);
548}
549
550void SpecialFunctionHandler::handlePosixPreferCex(ExecutionState &state,
551 KInstruction *target,
552 std::vector<ref<Expr> > &arguments) {
553 if (ReadablePosix)
554 return handlePreferCex(state, target, arguments);
555}
556
557void SpecialFunctionHandler::handlePrintExpr(ExecutionState &state,
558 KInstruction *target,
559 std::vector<ref<Expr> > &arguments) {
560 assert(arguments.size()==2 &&
561 "invalid number of arguments to klee_print_expr");
562
563 std::string msg_str = readStringAtAddress(state, arguments[0]);
564 llvm::errs() << msg_str << ":" << arguments[1] << "\n";
565}
566
567void SpecialFunctionHandler::handleSetForking(ExecutionState &state,
568 KInstruction *target,
569 std::vector<ref<Expr> > &arguments) {
570 assert(arguments.size()==1 &&
571 "invalid number of arguments to klee_set_forking");
572 ref<Expr> value = executor.toUnique(state, arguments[0]);
573
574 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(value)) {
575 state.forkDisabled = CE->isZero();
576 } else {
577 executor.terminateStateOnUserError(state, "klee_set_forking requires a constant arg");
578 }
579}
580
581void SpecialFunctionHandler::handleStackTrace(ExecutionState &state,
582 KInstruction *target,
583 std::vector<ref<Expr> > &arguments) {
584 state.dumpStack(outs());
585}
586
587void SpecialFunctionHandler::handleWarning(ExecutionState &state,
588 KInstruction *target,
589 std::vector<ref<Expr> > &arguments) {
590 assert(arguments.size()==1 && "invalid number of arguments to klee_warning");
591
592 std::string msg_str = readStringAtAddress(state, arguments[0]);
593 klee_warning("%s: %s", state.stack.back().kf->function->getName().data(),
594 msg_str.c_str());
595}
596
597void SpecialFunctionHandler::handleWarningOnce(ExecutionState &state,
598 KInstruction *target,
599 std::vector<ref<Expr> > &arguments) {
600 assert(arguments.size()==1 &&
601 "invalid number of arguments to klee_warning_once");
602
603 std::string msg_str = readStringAtAddress(state, arguments[0]);
604 klee_warning_once(0, "%s: %s", state.stack.back().kf->function->getName().data(),
605 msg_str.c_str());
606}
607
608void SpecialFunctionHandler::handlePrintRange(ExecutionState &state,
609 KInstruction *target,
610 std::vector<ref<Expr> > &arguments) {
611 assert(arguments.size()==2 &&
612 "invalid number of arguments to klee_print_range");
613
614 std::string msg_str = readStringAtAddress(state, arguments[0]);
615 llvm::errs() << msg_str << ":" << arguments[1];
616 if (!isa<ConstantExpr>(arguments[1])) {
617 // FIXME: Pull into a unique value method?
618 ref<ConstantExpr> value;
619 bool success __attribute__((unused)) = executor.solver->getValue(
620 state.constraints, arguments[1], value, state.queryMetaData);
621 assert(success && "FIXME: Unhandled solver failure");
622 bool res;
623 success = executor.solver->mustBeTrue(state.constraints,
624 EqExpr::create(arguments[1], value),
625 res, state.queryMetaData);
626 assert(success && "FIXME: Unhandled solver failure");
627 if (res) {
628 llvm::errs() << " == " << value;
629 } else {
630 llvm::errs() << " ~= " << value;
631 std::pair<ref<Expr>, ref<Expr>> res = executor.solver->getRange(
632 state.constraints, arguments[1], state.queryMetaData);
633 llvm::errs() << " (in [" << res.first << ", " << res.second <<"])";
634 }
635 }
636 llvm::errs() << "\n";
637}
638
639void SpecialFunctionHandler::handleGetObjSize(ExecutionState &state,
640 KInstruction *target,
641 std::vector<ref<Expr> > &arguments) {
642 // XXX should type check args
643 assert(arguments.size()==1 &&
644 "invalid number of arguments to klee_get_obj_size");
646 executor.resolveExact(state, arguments[0], rl, "klee_get_obj_size");
647 for (Executor::ExactResolutionList::iterator it = rl.begin(),
648 ie = rl.end(); it != ie; ++it) {
650 target, *it->second,
651 ConstantExpr::create(it->first.first->size,
652 executor.kmodule->targetData->getTypeSizeInBits(
653 target->inst->getType())));
654 }
655}
656
657void SpecialFunctionHandler::handleGetErrno(ExecutionState &state,
658 KInstruction *target,
659 std::vector<ref<Expr> > &arguments) {
660 // XXX should type check args
661 assert(arguments.size()==0 &&
662 "invalid number of arguments to klee_get_errno");
663#ifndef WINDOWS
664 int *errno_addr = executor.getErrnoLocation(state);
665#else
666 int *errno_addr = nullptr;
667#endif
668
669 // Retrieve the memory object of the errno variable
670 ObjectPair result;
671 bool resolved = state.addressSpace.resolveOne(
672 ConstantExpr::create((uint64_t)errno_addr, Expr::Int64), result);
673 if (!resolved)
674 executor.terminateStateOnUserError(state, "Could not resolve address for errno");
675 executor.bindLocal(target, state, result.second->read(0, Expr::Int32));
676}
677
678void SpecialFunctionHandler::handleErrnoLocation(
679 ExecutionState &state, KInstruction *target,
680 std::vector<ref<Expr> > &arguments) {
681 // Returns the address of the errno variable
682 assert(arguments.size() == 0 &&
683 "invalid number of arguments to __errno_location/__error");
684
685#ifndef WINDOWS
686 int *errno_addr = executor.getErrnoLocation(state);
687#else
688 int *errno_addr = nullptr;
689#endif
690
692 target, state,
693 ConstantExpr::create((uint64_t)errno_addr,
694 executor.kmodule->targetData->getTypeSizeInBits(
695 target->inst->getType())));
696}
697void SpecialFunctionHandler::handleCalloc(ExecutionState &state,
698 KInstruction *target,
699 std::vector<ref<Expr> > &arguments) {
700 // XXX should type check args
701 assert(arguments.size()==2 &&
702 "invalid number of arguments to calloc");
703
704 ref<Expr> size = MulExpr::create(arguments[0],
705 arguments[1]);
706 executor.executeAlloc(state, size, false, target, true);
707}
708
709void SpecialFunctionHandler::handleRealloc(ExecutionState &state,
710 KInstruction *target,
711 std::vector<ref<Expr> > &arguments) {
712 // XXX should type check args
713 assert(arguments.size()==2 &&
714 "invalid number of arguments to realloc");
715 ref<Expr> address = arguments[0];
716 ref<Expr> size = arguments[1];
717
718 Executor::StatePair zeroSize =
719 executor.fork(state, Expr::createIsZero(size), true, BranchType::Realloc);
720
721 if (zeroSize.first) { // size == 0
722 executor.executeFree(*zeroSize.first, address, target);
723 }
724 if (zeroSize.second) { // size != 0
725 Executor::StatePair zeroPointer =
726 executor.fork(*zeroSize.second, Expr::createIsZero(address), true,
727 BranchType::Realloc);
728
729 if (zeroPointer.first) { // address == 0
730 executor.executeAlloc(*zeroPointer.first, size, false, target);
731 }
732 if (zeroPointer.second) { // address != 0
734 executor.resolveExact(*zeroPointer.second, address, rl, "realloc");
735
736 for (Executor::ExactResolutionList::iterator it = rl.begin(),
737 ie = rl.end(); it != ie; ++it) {
738 executor.executeAlloc(*it->second, size, false, target, false,
739 it->first.second);
740 }
741 }
742 }
743}
744
745void SpecialFunctionHandler::handleFree(ExecutionState &state,
746 KInstruction *target,
747 std::vector<ref<Expr> > &arguments) {
748 // XXX should type check args
749 assert(arguments.size()==1 &&
750 "invalid number of arguments to free");
751 executor.executeFree(state, arguments[0]);
752}
753
754void SpecialFunctionHandler::handleCheckMemoryAccess(ExecutionState &state,
755 KInstruction *target,
756 std::vector<ref<Expr> >
757 &arguments) {
758 assert(arguments.size()==2 &&
759 "invalid number of arguments to klee_check_memory_access");
760
761 ref<Expr> address = executor.toUnique(state, arguments[0]);
762 ref<Expr> size = executor.toUnique(state, arguments[1]);
763 if (!isa<ConstantExpr>(address) || !isa<ConstantExpr>(size)) {
764 executor.terminateStateOnUserError(state, "check_memory_access requires constant args");
765 } else {
766 ObjectPair op;
767
768 if (!state.addressSpace.resolveOne(cast<ConstantExpr>(address), op)) {
770 "check_memory_access: memory error",
771 StateTerminationType::Ptr,
772 executor.getAddressInfo(state, address));
773 } else {
774 ref<Expr> chk =
775 op.first->getBoundsCheckPointer(address,
776 cast<ConstantExpr>(size)->getZExtValue());
777 if (!chk->isTrue()) {
779 "check_memory_access: memory error",
780 StateTerminationType::Ptr,
781 executor.getAddressInfo(state, address));
782 }
783 }
784 }
785}
786
787void SpecialFunctionHandler::handleGetValue(ExecutionState &state,
788 KInstruction *target,
789 std::vector<ref<Expr> > &arguments) {
790 assert(arguments.size()==1 &&
791 "invalid number of arguments to klee_get_value");
792
793 executor.executeGetValue(state, arguments[0], target);
794}
795
796void SpecialFunctionHandler::handleDefineFixedObject(ExecutionState &state,
797 KInstruction *target,
798 std::vector<ref<Expr> > &arguments) {
799 assert(arguments.size()==2 &&
800 "invalid number of arguments to klee_define_fixed_object");
801 assert(isa<ConstantExpr>(arguments[0]) &&
802 "expect constant address argument to klee_define_fixed_object");
803 assert(isa<ConstantExpr>(arguments[1]) &&
804 "expect constant size argument to klee_define_fixed_object");
805
806 uint64_t address = cast<ConstantExpr>(arguments[0])->getZExtValue();
807 uint64_t size = cast<ConstantExpr>(arguments[1])->getZExtValue();
808 MemoryObject *mo = executor.memory->allocateFixed(address, size, state.prevPC->inst);
809 executor.bindObjectInState(state, mo, false);
810 mo->isUserSpecified = true; // XXX hack;
811}
812
813void SpecialFunctionHandler::handleMakeSymbolic(ExecutionState &state,
814 KInstruction *target,
815 std::vector<ref<Expr> > &arguments) {
816 std::string name;
817
818 if (arguments.size() != 3) {
820 "Incorrect number of arguments to klee_make_symbolic(void*, size_t, char*)");
821 return;
822 }
823
824 name = arguments[2]->isZero() ? "" : readStringAtAddress(state, arguments[2]);
825
826 if (name.length() == 0) {
827 name = "unnamed";
828 klee_warning("klee_make_symbolic: renamed empty name to \"unnamed\"");
829 }
830
832 executor.resolveExact(state, arguments[0], rl, "make_symbolic");
833
834 for (Executor::ExactResolutionList::iterator it = rl.begin(),
835 ie = rl.end(); it != ie; ++it) {
836 const MemoryObject *mo = it->first.first;
837 mo->setName(name);
838
839 const ObjectState *old = it->first.second;
840 ExecutionState *s = it->second;
841
842 if (old->readOnly) {
843 executor.terminateStateOnUserError(*s, "cannot make readonly object symbolic");
844 return;
845 }
846
847 // FIXME: Type coercion should be done consistently somewhere.
848 bool res;
849 bool success __attribute__((unused)) = executor.solver->mustBeTrue(
850 s->constraints,
851 EqExpr::create(
852 ZExtExpr::create(arguments[1], Context::get().getPointerWidth()),
853 mo->getSizeExpr()),
854 res, s->queryMetaData);
855 assert(success && "FIXME: Unhandled solver failure");
856
857 if (res) {
858 executor.executeMakeSymbolic(*s, mo, name);
859 } else {
860 executor.terminateStateOnUserError(*s, "Wrong size given to klee_make_symbolic");
861 }
862 }
863}
864
865void SpecialFunctionHandler::handleMarkGlobal(ExecutionState &state,
866 KInstruction *target,
867 std::vector<ref<Expr> > &arguments) {
868 assert(arguments.size()==1 &&
869 "invalid number of arguments to klee_mark_global");
870
872 executor.resolveExact(state, arguments[0], rl, "mark_global");
873
874 for (Executor::ExactResolutionList::iterator it = rl.begin(),
875 ie = rl.end(); it != ie; ++it) {
876 const MemoryObject *mo = it->first.first;
877 assert(!mo->isLocal);
878 mo->isGlobal = true;
879 }
880}
881
882void SpecialFunctionHandler::handleAddOverflow(
883 ExecutionState &state, KInstruction *target,
884 std::vector<ref<Expr>> &arguments) {
885 executor.terminateStateOnError(state, "overflow on addition",
886 StateTerminationType::Overflow);
887}
888
889void SpecialFunctionHandler::handleSubOverflow(
890 ExecutionState &state, KInstruction *target,
891 std::vector<ref<Expr>> &arguments) {
892 executor.terminateStateOnError(state, "overflow on subtraction",
893 StateTerminationType::Overflow);
894}
895
896void SpecialFunctionHandler::handleMulOverflow(
897 ExecutionState &state, KInstruction *target,
898 std::vector<ref<Expr>> &arguments) {
899 executor.terminateStateOnError(state, "overflow on multiplication",
900 StateTerminationType::Overflow);
901}
902
903void SpecialFunctionHandler::handleDivRemOverflow(
904 ExecutionState &state, KInstruction *target,
905 std::vector<ref<Expr>> &arguments) {
906 executor.terminateStateOnError(state, "overflow on division or remainder",
907 StateTerminationType::Overflow);
908}
void *__dso_handle __attribute__((__weak__))
Implementation of the region based merging.
#define addDNR(name, handler)
static SpecialFunctionHandler::HandlerInfo handlerInfo[]
#define add(name, handler, ret)
bool resolveOne(const ref< ConstantExpr > &address, ObjectPair &result) const
static ref< ConstantExpr > create(uint64_t v, Width w)
Definition: Expr.h:1079
static ref< ConstantExpr > alloc(const llvm::APInt &v)
Definition: Expr.h:1065
Expr::Width getPointerWidth() const
Returns width of the pointer in bits.
Definition: Context.h:41
static const Context & get()
get - Return the global singleton instance of the Context.
Definition: Context.cpp:30
ExecutionState representing a path under exploration.
stack_ty stack
Stack representing the current instruction stream.
std::unique_ptr< UnwindingInformation > unwindingInformation
Keep track of unwinding state while unwinding, otherwise empty.
bool forkDisabled
Disables forking for this state. Set by user code.
SolverQueryMetaData queryMetaData
Statistics and information.
ConstraintSet constraints
Constraints collected so far.
std::vector< ref< MergeHandler > > openMergeStack
The objects handling the klee_open_merge calls this state ran through.
AddressSpace addressSpace
Address space used by this state (e.g. Global and Heap)
void dumpStack(llvm::raw_ostream &out) const
void addCexPreference(const ref< Expr > &cond)
KInstIterator prevPC
Pointer to instruction which is currently executed.
MemoryManager * memory
Definition: Executor.h:113
void terminateStateOnExit(ExecutionState &state)
Definition: Executor.cpp:3638
void addConstraint(ExecutionState &state, ref< Expr > condition)
Definition: Executor.cpp:1194
std::string getAddressInfo(ExecutionState &state, ref< Expr > address) const
Get textual information regarding a memory address.
Definition: Executor.cpp:3543
ObjectState * bindObjectInState(ExecutionState &state, const MemoryObject *mo, bool isLocal, const Array *array=0)
Definition: Executor.cpp:3938
ref< ConstantExpr > getEhTypeidFor(ref< Expr > type_info)
Return the typeid corresponding to a certain type_info
Definition: Executor.cpp:1641
TimingSolver * solver
Definition: Executor.h:112
std::vector< std::pair< std::pair< const MemoryObject *, const ObjectState * >, ExecutionState * > > ExactResolutionList
Definition: Executor.h:258
StatePair fork(ExecutionState &current, ref< Expr > condition, bool isInternal, BranchType reason)
Definition: Executor.cpp:1003
ref< Expr > toUnique(const ExecutionState &state, ref< Expr > &e)
Definition: Executor.cpp:1258
void terminateState(ExecutionState &state)
Remove state from queue and delete state.
Definition: Executor.cpp:3596
void executeAlloc(ExecutionState &state, ref< Expr > size, bool isLocal, KInstruction *target, bool zeroMemory=false, const ObjectState *reallocFrom=0, size_t allocationAlignment=0)
Definition: Executor.cpp:3955
void bindLocal(KInstruction *target, ExecutionState &state, ref< Expr > value)
Definition: Executor.cpp:1248
void terminateStateEarly(ExecutionState &state, const llvm::Twine &message, StateTerminationType terminationType)
Definition: Executor.cpp:3648
std::pair< ExecutionState *, ExecutionState * > StatePair
Definition: Executor.h:101
void terminateStateOnExecError(ExecutionState &state, const llvm::Twine &message, const llvm::Twine &info="")
Definition: Executor.cpp:3761
void executeMakeSymbolic(ExecutionState &state, const MemoryObject *mo, const std::string &name)
Definition: Executor.cpp:4268
std::unique_ptr< KModule > kmodule
Definition: Executor.h:107
void terminateStateOnUserError(ExecutionState &state, const llvm::Twine &message)
Definition: Executor.cpp:3661
void resolveExact(ExecutionState &state, ref< Expr > p, ExactResolutionList &results, const std::string &name)
Definition: Executor.cpp:4110
MergingSearcher * mergingSearcher
Definition: Executor.h:206
void executeGetValue(ExecutionState &state, ref< Expr > e, KInstruction *target)
Definition: Executor.cpp:1314
void unwindToNextLandingpad(ExecutionState &state)
Definition: Executor.cpp:1532
void executeFree(ExecutionState &state, ref< Expr > address, KInstruction *target=0)
Definition: Executor.cpp:4076
void terminateStateOnError(ExecutionState &state, const llvm::Twine &message, StateTerminationType terminationType, const llvm::Twine &longMessage="", const char *suffix=nullptr)
Definition: Executor.cpp:3713
int * getErrnoLocation(const ExecutionState &state) const
Returns the errno location in memory of the state.
Definition: Executor.cpp:4667
static const Width Int64
Definition: Expr.h:104
static const Width Int32
Definition: Expr.h:103
static ref< Expr > createIsZero(ref< Expr > e)
Definition: Expr.cpp:322
virtual Width getWidth() const =0
bool isTrue() const
isTrue - Is this the true expression.
Definition: Expr.h:1156
static const Width Bool
Definition: Expr.h:100
MemoryObject * allocateFixed(uint64_t address, uint64_t size, const llvm::Value *allocSite)
void setName(std::string name) const
Definition: Memory.h:105
unsigned size
size in bytes
Definition: Memory.h:52
bool isUserSpecified
Definition: Memory.h:59
ref< ConstantExpr > getSizeExpr() const
Definition: Memory.h:112
ref< Expr > getOffsetExpr(ref< Expr > pointer) const
Definition: Memory.h:115
Represents one klee_open_merge() call. Handles merging of states that branched from it.
Definition: MergeHandler.h:96
std::set< ExecutionState * > inCloseMerge
Definition: Searcher.h:215
ref< Expr > read8(unsigned offset) const
Definition: Memory.cpp:364
void(SpecialFunctionHandler::* Handler)(ExecutionState &state, KInstruction *target, std::vector< ref< Expr > > &arguments)
std::string readStringAtAddress(ExecutionState &state, ref< Expr > address)
SpecialFunctionHandler(Executor &_executor)
bool handle(ExecutionState &state, llvm::Function *f, KInstruction *target, std::vector< ref< Expr > > &arguments)
void prepare(std::vector< const char * > &preservedFunctions)
bool getValue(const ConstraintSet &, ref< Expr > expr, ref< ConstantExpr > &result, SolverQueryMetaData &metaData)
bool mustBeFalse(const ConstraintSet &, ref< Expr >, bool &result, SolverQueryMetaData &metaData)
bool mustBeTrue(const ConstraintSet &, ref< Expr >, bool &result, SolverQueryMetaData &metaData)
std::pair< ref< Expr >, ref< Expr > > getRange(const ConstraintSet &, ref< Expr > query, SolverQueryMetaData &metaData)
T * get() const
Definition: Ref.h:129
Definition: main.cpp:291
llvm::cl::OptionCategory TestGenCat
llvm::cl::opt< bool > UseMerge
llvm::cl::opt< bool > DebugLogMerge
void void void void klee_warning_once(const void *id, const char *msg,...) __attribute__((format(printf
llvm::cl::OptionCategory TerminationCat
void void void klee_warning(const char *msg,...) __attribute__((format(printf
std::pair< const MemoryObject *, const ObjectState * > ObjectPair
Definition: AddressSpace.h:25
llvm::Instruction * inst
Definition: KInstruction.h:34
bool hasReturnValue
Intrinsic terminates the process.
bool doNotOverride
Intrinsic has a return value.