1//= CStringChecker.cpp - Checks calls to C string functions --------*- C++ -*-// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This defines CStringChecker, which is an assortment of checks on calls 11// to functions in <string.h>. 12// 13//===----------------------------------------------------------------------===// 14 15#include "ClangSACheckers.h" 16#include "InterCheckerAPI.h" 17#include "clang/Basic/CharInfo.h" 18#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 19#include "clang/StaticAnalyzer/Core/Checker.h" 20#include "clang/StaticAnalyzer/Core/CheckerManager.h" 21#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 22#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 23#include "llvm/ADT/STLExtras.h" 24#include "llvm/ADT/SmallString.h" 25#include "llvm/ADT/StringSwitch.h" 26#include "llvm/Support/raw_ostream.h" 27 28using namespace clang; 29using namespace ento; 30 31namespace { 32class CStringChecker : public Checker< eval::Call, 33 check::PreStmt<DeclStmt>, 34 check::LiveSymbols, 35 check::DeadSymbols, 36 check::RegionChanges 37 > { 38 mutable OwningPtr<BugType> BT_Null, 39 BT_Bounds, 40 BT_Overlap, 41 BT_NotCString, 42 BT_AdditionOverflow; 43 44 mutable const char *CurrentFunctionDescription; 45 46public: 47 /// The filter is used to filter out the diagnostics which are not enabled by 48 /// the user. 49 struct CStringChecksFilter { 50 DefaultBool CheckCStringNullArg; 51 DefaultBool CheckCStringOutOfBounds; 52 DefaultBool CheckCStringBufferOverlap; 53 DefaultBool CheckCStringNotNullTerm; 54 }; 55 56 CStringChecksFilter Filter; 57 58 static void *getTag() { static int tag; return &tag; } 59 60 bool evalCall(const CallExpr *CE, CheckerContext &C) const; 61 void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const; 62 void checkLiveSymbols(ProgramStateRef state, SymbolReaper &SR) const; 63 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; 64 bool wantsRegionChangeUpdate(ProgramStateRef state) const; 65 66 ProgramStateRef 67 checkRegionChanges(ProgramStateRef state, 68 const InvalidatedSymbols *, 69 ArrayRef<const MemRegion *> ExplicitRegions, 70 ArrayRef<const MemRegion *> Regions, 71 const CallEvent *Call) const; 72 73 typedef void (CStringChecker::*FnCheck)(CheckerContext &, 74 const CallExpr *) const; 75 76 void evalMemcpy(CheckerContext &C, const CallExpr *CE) const; 77 void evalMempcpy(CheckerContext &C, const CallExpr *CE) const; 78 void evalMemmove(CheckerContext &C, const CallExpr *CE) const; 79 void evalBcopy(CheckerContext &C, const CallExpr *CE) const; 80 void evalCopyCommon(CheckerContext &C, const CallExpr *CE, 81 ProgramStateRef state, 82 const Expr *Size, 83 const Expr *Source, 84 const Expr *Dest, 85 bool Restricted = false, 86 bool IsMempcpy = false) const; 87 88 void evalMemcmp(CheckerContext &C, const CallExpr *CE) const; 89 90 void evalstrLength(CheckerContext &C, const CallExpr *CE) const; 91 void evalstrnLength(CheckerContext &C, const CallExpr *CE) const; 92 void evalstrLengthCommon(CheckerContext &C, 93 const CallExpr *CE, 94 bool IsStrnlen = false) const; 95 96 void evalStrcpy(CheckerContext &C, const CallExpr *CE) const; 97 void evalStrncpy(CheckerContext &C, const CallExpr *CE) const; 98 void evalStpcpy(CheckerContext &C, const CallExpr *CE) const; 99 void evalStrcpyCommon(CheckerContext &C, 100 const CallExpr *CE, 101 bool returnEnd, 102 bool isBounded, 103 bool isAppending) const; 104 105 void evalStrcat(CheckerContext &C, const CallExpr *CE) const; 106 void evalStrncat(CheckerContext &C, const CallExpr *CE) const; 107 108 void evalStrcmp(CheckerContext &C, const CallExpr *CE) const; 109 void evalStrncmp(CheckerContext &C, const CallExpr *CE) const; 110 void evalStrcasecmp(CheckerContext &C, const CallExpr *CE) const; 111 void evalStrncasecmp(CheckerContext &C, const CallExpr *CE) const; 112 void evalStrcmpCommon(CheckerContext &C, 113 const CallExpr *CE, 114 bool isBounded = false, 115 bool ignoreCase = false) const; 116 117 void evalStrsep(CheckerContext &C, const CallExpr *CE) const; 118 119 // Utility methods 120 std::pair<ProgramStateRef , ProgramStateRef > 121 static assumeZero(CheckerContext &C, 122 ProgramStateRef state, SVal V, QualType Ty); 123 124 static ProgramStateRef setCStringLength(ProgramStateRef state, 125 const MemRegion *MR, 126 SVal strLength); 127 static SVal getCStringLengthForRegion(CheckerContext &C, 128 ProgramStateRef &state, 129 const Expr *Ex, 130 const MemRegion *MR, 131 bool hypothetical); 132 SVal getCStringLength(CheckerContext &C, 133 ProgramStateRef &state, 134 const Expr *Ex, 135 SVal Buf, 136 bool hypothetical = false) const; 137 138 const StringLiteral *getCStringLiteral(CheckerContext &C, 139 ProgramStateRef &state, 140 const Expr *expr, 141 SVal val) const; 142 143 static ProgramStateRef InvalidateBuffer(CheckerContext &C, 144 ProgramStateRef state, 145 const Expr *Ex, SVal V, 146 bool IsSourceBuffer); 147 148 static bool SummarizeRegion(raw_ostream &os, ASTContext &Ctx, 149 const MemRegion *MR); 150 151 // Re-usable checks 152 ProgramStateRef checkNonNull(CheckerContext &C, 153 ProgramStateRef state, 154 const Expr *S, 155 SVal l) const; 156 ProgramStateRef CheckLocation(CheckerContext &C, 157 ProgramStateRef state, 158 const Expr *S, 159 SVal l, 160 const char *message = NULL) const; 161 ProgramStateRef CheckBufferAccess(CheckerContext &C, 162 ProgramStateRef state, 163 const Expr *Size, 164 const Expr *FirstBuf, 165 const Expr *SecondBuf, 166 const char *firstMessage = NULL, 167 const char *secondMessage = NULL, 168 bool WarnAboutSize = false) const; 169 170 ProgramStateRef CheckBufferAccess(CheckerContext &C, 171 ProgramStateRef state, 172 const Expr *Size, 173 const Expr *Buf, 174 const char *message = NULL, 175 bool WarnAboutSize = false) const { 176 // This is a convenience override. 177 return CheckBufferAccess(C, state, Size, Buf, NULL, message, NULL, 178 WarnAboutSize); 179 } 180 ProgramStateRef CheckOverlap(CheckerContext &C, 181 ProgramStateRef state, 182 const Expr *Size, 183 const Expr *First, 184 const Expr *Second) const; 185 void emitOverlapBug(CheckerContext &C, 186 ProgramStateRef state, 187 const Stmt *First, 188 const Stmt *Second) const; 189 190 ProgramStateRef checkAdditionOverflow(CheckerContext &C, 191 ProgramStateRef state, 192 NonLoc left, 193 NonLoc right) const; 194}; 195 196} //end anonymous namespace 197 198REGISTER_MAP_WITH_PROGRAMSTATE(CStringLength, const MemRegion *, SVal) 199 200//===----------------------------------------------------------------------===// 201// Individual checks and utility methods. 202//===----------------------------------------------------------------------===// 203 204std::pair<ProgramStateRef , ProgramStateRef > 205CStringChecker::assumeZero(CheckerContext &C, ProgramStateRef state, SVal V, 206 QualType Ty) { 207 Optional<DefinedSVal> val = V.getAs<DefinedSVal>(); 208 if (!val) 209 return std::pair<ProgramStateRef , ProgramStateRef >(state, state); 210 211 SValBuilder &svalBuilder = C.getSValBuilder(); 212 DefinedOrUnknownSVal zero = svalBuilder.makeZeroVal(Ty); 213 return state->assume(svalBuilder.evalEQ(state, *val, zero)); 214} 215 216ProgramStateRef CStringChecker::checkNonNull(CheckerContext &C, 217 ProgramStateRef state, 218 const Expr *S, SVal l) const { 219 // If a previous check has failed, propagate the failure. 220 if (!state) 221 return NULL; 222 223 ProgramStateRef stateNull, stateNonNull; 224 llvm::tie(stateNull, stateNonNull) = assumeZero(C, state, l, S->getType()); 225 226 if (stateNull && !stateNonNull) { 227 if (!Filter.CheckCStringNullArg) 228 return NULL; 229 230 ExplodedNode *N = C.generateSink(stateNull); 231 if (!N) 232 return NULL; 233 234 if (!BT_Null) 235 BT_Null.reset(new BuiltinBug(categories::UnixAPI, 236 "Null pointer argument in call to byte string function")); 237 238 SmallString<80> buf; 239 llvm::raw_svector_ostream os(buf); 240 assert(CurrentFunctionDescription); 241 os << "Null pointer argument in call to " << CurrentFunctionDescription; 242 243 // Generate a report for this bug. 244 BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Null.get()); 245 BugReport *report = new BugReport(*BT, os.str(), N); 246 247 report->addRange(S->getSourceRange()); 248 bugreporter::trackNullOrUndefValue(N, S, *report); 249 C.emitReport(report); 250 return NULL; 251 } 252 253 // From here on, assume that the value is non-null. 254 assert(stateNonNull); 255 return stateNonNull; 256} 257 258// FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor? 259ProgramStateRef CStringChecker::CheckLocation(CheckerContext &C, 260 ProgramStateRef state, 261 const Expr *S, SVal l, 262 const char *warningMsg) const { 263 // If a previous check has failed, propagate the failure. 264 if (!state) 265 return NULL; 266 267 // Check for out of bound array element access. 268 const MemRegion *R = l.getAsRegion(); 269 if (!R) 270 return state; 271 272 const ElementRegion *ER = dyn_cast<ElementRegion>(R); 273 if (!ER) 274 return state; 275 276 assert(ER->getValueType() == C.getASTContext().CharTy && 277 "CheckLocation should only be called with char* ElementRegions"); 278 279 // Get the size of the array. 280 const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion()); 281 SValBuilder &svalBuilder = C.getSValBuilder(); 282 SVal Extent = 283 svalBuilder.convertToArrayIndex(superReg->getExtent(svalBuilder)); 284 DefinedOrUnknownSVal Size = Extent.castAs<DefinedOrUnknownSVal>(); 285 286 // Get the index of the accessed element. 287 DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>(); 288 289 ProgramStateRef StInBound = state->assumeInBound(Idx, Size, true); 290 ProgramStateRef StOutBound = state->assumeInBound(Idx, Size, false); 291 if (StOutBound && !StInBound) { 292 ExplodedNode *N = C.generateSink(StOutBound); 293 if (!N) 294 return NULL; 295 296 if (!BT_Bounds) { 297 BT_Bounds.reset(new BuiltinBug("Out-of-bound array access", 298 "Byte string function accesses out-of-bound array element")); 299 } 300 BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Bounds.get()); 301 302 // Generate a report for this bug. 303 BugReport *report; 304 if (warningMsg) { 305 report = new BugReport(*BT, warningMsg, N); 306 } else { 307 assert(CurrentFunctionDescription); 308 assert(CurrentFunctionDescription[0] != '\0'); 309 310 SmallString<80> buf; 311 llvm::raw_svector_ostream os(buf); 312 os << toUppercase(CurrentFunctionDescription[0]) 313 << &CurrentFunctionDescription[1] 314 << " accesses out-of-bound array element"; 315 report = new BugReport(*BT, os.str(), N); 316 } 317 318 // FIXME: It would be nice to eventually make this diagnostic more clear, 319 // e.g., by referencing the original declaration or by saying *why* this 320 // reference is outside the range. 321 322 report->addRange(S->getSourceRange()); 323 C.emitReport(report); 324 return NULL; 325 } 326 327 // Array bound check succeeded. From this point forward the array bound 328 // should always succeed. 329 return StInBound; 330} 331 332ProgramStateRef CStringChecker::CheckBufferAccess(CheckerContext &C, 333 ProgramStateRef state, 334 const Expr *Size, 335 const Expr *FirstBuf, 336 const Expr *SecondBuf, 337 const char *firstMessage, 338 const char *secondMessage, 339 bool WarnAboutSize) const { 340 // If a previous check has failed, propagate the failure. 341 if (!state) 342 return NULL; 343 344 SValBuilder &svalBuilder = C.getSValBuilder(); 345 ASTContext &Ctx = svalBuilder.getContext(); 346 const LocationContext *LCtx = C.getLocationContext(); 347 348 QualType sizeTy = Size->getType(); 349 QualType PtrTy = Ctx.getPointerType(Ctx.CharTy); 350 351 // Check that the first buffer is non-null. 352 SVal BufVal = state->getSVal(FirstBuf, LCtx); 353 state = checkNonNull(C, state, FirstBuf, BufVal); 354 if (!state) 355 return NULL; 356 357 // If out-of-bounds checking is turned off, skip the rest. 358 if (!Filter.CheckCStringOutOfBounds) 359 return state; 360 361 // Get the access length and make sure it is known. 362 // FIXME: This assumes the caller has already checked that the access length 363 // is positive. And that it's unsigned. 364 SVal LengthVal = state->getSVal(Size, LCtx); 365 Optional<NonLoc> Length = LengthVal.getAs<NonLoc>(); 366 if (!Length) 367 return state; 368 369 // Compute the offset of the last element to be accessed: size-1. 370 NonLoc One = svalBuilder.makeIntVal(1, sizeTy).castAs<NonLoc>(); 371 NonLoc LastOffset = svalBuilder 372 .evalBinOpNN(state, BO_Sub, *Length, One, sizeTy).castAs<NonLoc>(); 373 374 // Check that the first buffer is sufficiently long. 375 SVal BufStart = svalBuilder.evalCast(BufVal, PtrTy, FirstBuf->getType()); 376 if (Optional<Loc> BufLoc = BufStart.getAs<Loc>()) { 377 const Expr *warningExpr = (WarnAboutSize ? Size : FirstBuf); 378 379 SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc, 380 LastOffset, PtrTy); 381 state = CheckLocation(C, state, warningExpr, BufEnd, firstMessage); 382 383 // If the buffer isn't large enough, abort. 384 if (!state) 385 return NULL; 386 } 387 388 // If there's a second buffer, check it as well. 389 if (SecondBuf) { 390 BufVal = state->getSVal(SecondBuf, LCtx); 391 state = checkNonNull(C, state, SecondBuf, BufVal); 392 if (!state) 393 return NULL; 394 395 BufStart = svalBuilder.evalCast(BufVal, PtrTy, SecondBuf->getType()); 396 if (Optional<Loc> BufLoc = BufStart.getAs<Loc>()) { 397 const Expr *warningExpr = (WarnAboutSize ? Size : SecondBuf); 398 399 SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc, 400 LastOffset, PtrTy); 401 state = CheckLocation(C, state, warningExpr, BufEnd, secondMessage); 402 } 403 } 404 405 // Large enough or not, return this state! 406 return state; 407} 408 409ProgramStateRef CStringChecker::CheckOverlap(CheckerContext &C, 410 ProgramStateRef state, 411 const Expr *Size, 412 const Expr *First, 413 const Expr *Second) const { 414 if (!Filter.CheckCStringBufferOverlap) 415 return state; 416 417 // Do a simple check for overlap: if the two arguments are from the same 418 // buffer, see if the end of the first is greater than the start of the second 419 // or vice versa. 420 421 // If a previous check has failed, propagate the failure. 422 if (!state) 423 return NULL; 424 425 ProgramStateRef stateTrue, stateFalse; 426 427 // Get the buffer values and make sure they're known locations. 428 const LocationContext *LCtx = C.getLocationContext(); 429 SVal firstVal = state->getSVal(First, LCtx); 430 SVal secondVal = state->getSVal(Second, LCtx); 431 432 Optional<Loc> firstLoc = firstVal.getAs<Loc>(); 433 if (!firstLoc) 434 return state; 435 436 Optional<Loc> secondLoc = secondVal.getAs<Loc>(); 437 if (!secondLoc) 438 return state; 439 440 // Are the two values the same? 441 SValBuilder &svalBuilder = C.getSValBuilder(); 442 llvm::tie(stateTrue, stateFalse) = 443 state->assume(svalBuilder.evalEQ(state, *firstLoc, *secondLoc)); 444 445 if (stateTrue && !stateFalse) { 446 // If the values are known to be equal, that's automatically an overlap. 447 emitOverlapBug(C, stateTrue, First, Second); 448 return NULL; 449 } 450 451 // assume the two expressions are not equal. 452 assert(stateFalse); 453 state = stateFalse; 454 455 // Which value comes first? 456 QualType cmpTy = svalBuilder.getConditionType(); 457 SVal reverse = svalBuilder.evalBinOpLL(state, BO_GT, 458 *firstLoc, *secondLoc, cmpTy); 459 Optional<DefinedOrUnknownSVal> reverseTest = 460 reverse.getAs<DefinedOrUnknownSVal>(); 461 if (!reverseTest) 462 return state; 463 464 llvm::tie(stateTrue, stateFalse) = state->assume(*reverseTest); 465 if (stateTrue) { 466 if (stateFalse) { 467 // If we don't know which one comes first, we can't perform this test. 468 return state; 469 } else { 470 // Switch the values so that firstVal is before secondVal. 471 std::swap(firstLoc, secondLoc); 472 473 // Switch the Exprs as well, so that they still correspond. 474 std::swap(First, Second); 475 } 476 } 477 478 // Get the length, and make sure it too is known. 479 SVal LengthVal = state->getSVal(Size, LCtx); 480 Optional<NonLoc> Length = LengthVal.getAs<NonLoc>(); 481 if (!Length) 482 return state; 483 484 // Convert the first buffer's start address to char*. 485 // Bail out if the cast fails. 486 ASTContext &Ctx = svalBuilder.getContext(); 487 QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy); 488 SVal FirstStart = svalBuilder.evalCast(*firstLoc, CharPtrTy, 489 First->getType()); 490 Optional<Loc> FirstStartLoc = FirstStart.getAs<Loc>(); 491 if (!FirstStartLoc) 492 return state; 493 494 // Compute the end of the first buffer. Bail out if THAT fails. 495 SVal FirstEnd = svalBuilder.evalBinOpLN(state, BO_Add, 496 *FirstStartLoc, *Length, CharPtrTy); 497 Optional<Loc> FirstEndLoc = FirstEnd.getAs<Loc>(); 498 if (!FirstEndLoc) 499 return state; 500 501 // Is the end of the first buffer past the start of the second buffer? 502 SVal Overlap = svalBuilder.evalBinOpLL(state, BO_GT, 503 *FirstEndLoc, *secondLoc, cmpTy); 504 Optional<DefinedOrUnknownSVal> OverlapTest = 505 Overlap.getAs<DefinedOrUnknownSVal>(); 506 if (!OverlapTest) 507 return state; 508 509 llvm::tie(stateTrue, stateFalse) = state->assume(*OverlapTest); 510 511 if (stateTrue && !stateFalse) { 512 // Overlap! 513 emitOverlapBug(C, stateTrue, First, Second); 514 return NULL; 515 } 516 517 // assume the two expressions don't overlap. 518 assert(stateFalse); 519 return stateFalse; 520} 521 522void CStringChecker::emitOverlapBug(CheckerContext &C, ProgramStateRef state, 523 const Stmt *First, const Stmt *Second) const { 524 ExplodedNode *N = C.generateSink(state); 525 if (!N) 526 return; 527 528 if (!BT_Overlap) 529 BT_Overlap.reset(new BugType(categories::UnixAPI, "Improper arguments")); 530 531 // Generate a report for this bug. 532 BugReport *report = 533 new BugReport(*BT_Overlap, 534 "Arguments must not be overlapping buffers", N); 535 report->addRange(First->getSourceRange()); 536 report->addRange(Second->getSourceRange()); 537 538 C.emitReport(report); 539} 540 541ProgramStateRef CStringChecker::checkAdditionOverflow(CheckerContext &C, 542 ProgramStateRef state, 543 NonLoc left, 544 NonLoc right) const { 545 // If out-of-bounds checking is turned off, skip the rest. 546 if (!Filter.CheckCStringOutOfBounds) 547 return state; 548 549 // If a previous check has failed, propagate the failure. 550 if (!state) 551 return NULL; 552 553 SValBuilder &svalBuilder = C.getSValBuilder(); 554 BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); 555 556 QualType sizeTy = svalBuilder.getContext().getSizeType(); 557 const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy); 558 NonLoc maxVal = svalBuilder.makeIntVal(maxValInt); 559 560 SVal maxMinusRight; 561 if (right.getAs<nonloc::ConcreteInt>()) { 562 maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, right, 563 sizeTy); 564 } else { 565 // Try switching the operands. (The order of these two assignments is 566 // important!) 567 maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, left, 568 sizeTy); 569 left = right; 570 } 571 572 if (Optional<NonLoc> maxMinusRightNL = maxMinusRight.getAs<NonLoc>()) { 573 QualType cmpTy = svalBuilder.getConditionType(); 574 // If left > max - right, we have an overflow. 575 SVal willOverflow = svalBuilder.evalBinOpNN(state, BO_GT, left, 576 *maxMinusRightNL, cmpTy); 577 578 ProgramStateRef stateOverflow, stateOkay; 579 llvm::tie(stateOverflow, stateOkay) = 580 state->assume(willOverflow.castAs<DefinedOrUnknownSVal>()); 581 582 if (stateOverflow && !stateOkay) { 583 // We have an overflow. Emit a bug report. 584 ExplodedNode *N = C.generateSink(stateOverflow); 585 if (!N) 586 return NULL; 587 588 if (!BT_AdditionOverflow) 589 BT_AdditionOverflow.reset(new BuiltinBug("API", 590 "Sum of expressions causes overflow")); 591 592 // This isn't a great error message, but this should never occur in real 593 // code anyway -- you'd have to create a buffer longer than a size_t can 594 // represent, which is sort of a contradiction. 595 const char *warning = 596 "This expression will create a string whose length is too big to " 597 "be represented as a size_t"; 598 599 // Generate a report for this bug. 600 BugReport *report = new BugReport(*BT_AdditionOverflow, warning, N); 601 C.emitReport(report); 602 603 return NULL; 604 } 605 606 // From now on, assume an overflow didn't occur. 607 assert(stateOkay); 608 state = stateOkay; 609 } 610 611 return state; 612} 613 614ProgramStateRef CStringChecker::setCStringLength(ProgramStateRef state, 615 const MemRegion *MR, 616 SVal strLength) { 617 assert(!strLength.isUndef() && "Attempt to set an undefined string length"); 618 619 MR = MR->StripCasts(); 620 621 switch (MR->getKind()) { 622 case MemRegion::StringRegionKind: 623 // FIXME: This can happen if we strcpy() into a string region. This is 624 // undefined [C99 6.4.5p6], but we should still warn about it. 625 return state; 626 627 case MemRegion::SymbolicRegionKind: 628 case MemRegion::AllocaRegionKind: 629 case MemRegion::VarRegionKind: 630 case MemRegion::FieldRegionKind: 631 case MemRegion::ObjCIvarRegionKind: 632 // These are the types we can currently track string lengths for. 633 break; 634 635 case MemRegion::ElementRegionKind: 636 // FIXME: Handle element regions by upper-bounding the parent region's 637 // string length. 638 return state; 639 640 default: 641 // Other regions (mostly non-data) can't have a reliable C string length. 642 // For now, just ignore the change. 643 // FIXME: These are rare but not impossible. We should output some kind of 644 // warning for things like strcpy((char[]){'a', 0}, "b"); 645 return state; 646 } 647 648 if (strLength.isUnknown()) 649 return state->remove<CStringLength>(MR); 650 651 return state->set<CStringLength>(MR, strLength); 652} 653 654SVal CStringChecker::getCStringLengthForRegion(CheckerContext &C, 655 ProgramStateRef &state, 656 const Expr *Ex, 657 const MemRegion *MR, 658 bool hypothetical) { 659 if (!hypothetical) { 660 // If there's a recorded length, go ahead and return it. 661 const SVal *Recorded = state->get<CStringLength>(MR); 662 if (Recorded) 663 return *Recorded; 664 } 665 666 // Otherwise, get a new symbol and update the state. 667 SValBuilder &svalBuilder = C.getSValBuilder(); 668 QualType sizeTy = svalBuilder.getContext().getSizeType(); 669 SVal strLength = svalBuilder.getMetadataSymbolVal(CStringChecker::getTag(), 670 MR, Ex, sizeTy, 671 C.blockCount()); 672 673 if (!hypothetical) { 674 if (Optional<NonLoc> strLn = strLength.getAs<NonLoc>()) { 675 // In case of unbounded calls strlen etc bound the range to SIZE_MAX/4 676 BasicValueFactory &BVF = svalBuilder.getBasicValueFactory(); 677 const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy); 678 llvm::APSInt fourInt = APSIntType(maxValInt).getValue(4); 679 const llvm::APSInt *maxLengthInt = BVF.evalAPSInt(BO_Div, maxValInt, 680 fourInt); 681 NonLoc maxLength = svalBuilder.makeIntVal(*maxLengthInt); 682 SVal evalLength = svalBuilder.evalBinOpNN(state, BO_LE, *strLn, 683 maxLength, sizeTy); 684 state = state->assume(evalLength.castAs<DefinedOrUnknownSVal>(), true); 685 } 686 state = state->set<CStringLength>(MR, strLength); 687 } 688 689 return strLength; 690} 691 692SVal CStringChecker::getCStringLength(CheckerContext &C, ProgramStateRef &state, 693 const Expr *Ex, SVal Buf, 694 bool hypothetical) const { 695 const MemRegion *MR = Buf.getAsRegion(); 696 if (!MR) { 697 // If we can't get a region, see if it's something we /know/ isn't a 698 // C string. In the context of locations, the only time we can issue such 699 // a warning is for labels. 700 if (Optional<loc::GotoLabel> Label = Buf.getAs<loc::GotoLabel>()) { 701 if (!Filter.CheckCStringNotNullTerm) 702 return UndefinedVal(); 703 704 if (ExplodedNode *N = C.addTransition(state)) { 705 if (!BT_NotCString) 706 BT_NotCString.reset(new BuiltinBug(categories::UnixAPI, 707 "Argument is not a null-terminated string.")); 708 709 SmallString<120> buf; 710 llvm::raw_svector_ostream os(buf); 711 assert(CurrentFunctionDescription); 712 os << "Argument to " << CurrentFunctionDescription 713 << " is the address of the label '" << Label->getLabel()->getName() 714 << "', which is not a null-terminated string"; 715 716 // Generate a report for this bug. 717 BugReport *report = new BugReport(*BT_NotCString, 718 os.str(), N); 719 720 report->addRange(Ex->getSourceRange()); 721 C.emitReport(report); 722 } 723 return UndefinedVal(); 724 725 } 726 727 // If it's not a region and not a label, give up. 728 return UnknownVal(); 729 } 730 731 // If we have a region, strip casts from it and see if we can figure out 732 // its length. For anything we can't figure out, just return UnknownVal. 733 MR = MR->StripCasts(); 734 735 switch (MR->getKind()) { 736 case MemRegion::StringRegionKind: { 737 // Modifying the contents of string regions is undefined [C99 6.4.5p6], 738 // so we can assume that the byte length is the correct C string length. 739 SValBuilder &svalBuilder = C.getSValBuilder(); 740 QualType sizeTy = svalBuilder.getContext().getSizeType(); 741 const StringLiteral *strLit = cast<StringRegion>(MR)->getStringLiteral(); 742 return svalBuilder.makeIntVal(strLit->getByteLength(), sizeTy); 743 } 744 case MemRegion::SymbolicRegionKind: 745 case MemRegion::AllocaRegionKind: 746 case MemRegion::VarRegionKind: 747 case MemRegion::FieldRegionKind: 748 case MemRegion::ObjCIvarRegionKind: 749 return getCStringLengthForRegion(C, state, Ex, MR, hypothetical); 750 case MemRegion::CompoundLiteralRegionKind: 751 // FIXME: Can we track this? Is it necessary? 752 return UnknownVal(); 753 case MemRegion::ElementRegionKind: 754 // FIXME: How can we handle this? It's not good enough to subtract the 755 // offset from the base string length; consider "123\x00567" and &a[5]. 756 return UnknownVal(); 757 default: 758 // Other regions (mostly non-data) can't have a reliable C string length. 759 // In this case, an error is emitted and UndefinedVal is returned. 760 // The caller should always be prepared to handle this case. 761 if (!Filter.CheckCStringNotNullTerm) 762 return UndefinedVal(); 763 764 if (ExplodedNode *N = C.addTransition(state)) { 765 if (!BT_NotCString) 766 BT_NotCString.reset(new BuiltinBug(categories::UnixAPI, 767 "Argument is not a null-terminated string.")); 768 769 SmallString<120> buf; 770 llvm::raw_svector_ostream os(buf); 771 772 assert(CurrentFunctionDescription); 773 os << "Argument to " << CurrentFunctionDescription << " is "; 774 775 if (SummarizeRegion(os, C.getASTContext(), MR)) 776 os << ", which is not a null-terminated string"; 777 else 778 os << "not a null-terminated string"; 779 780 // Generate a report for this bug. 781 BugReport *report = new BugReport(*BT_NotCString, 782 os.str(), N); 783 784 report->addRange(Ex->getSourceRange()); 785 C.emitReport(report); 786 } 787 788 return UndefinedVal(); 789 } 790} 791 792const StringLiteral *CStringChecker::getCStringLiteral(CheckerContext &C, 793 ProgramStateRef &state, const Expr *expr, SVal val) const { 794 795 // Get the memory region pointed to by the val. 796 const MemRegion *bufRegion = val.getAsRegion(); 797 if (!bufRegion) 798 return NULL; 799 800 // Strip casts off the memory region. 801 bufRegion = bufRegion->StripCasts(); 802 803 // Cast the memory region to a string region. 804 const StringRegion *strRegion= dyn_cast<StringRegion>(bufRegion); 805 if (!strRegion) 806 return NULL; 807 808 // Return the actual string in the string region. 809 return strRegion->getStringLiteral(); 810} 811 812ProgramStateRef CStringChecker::InvalidateBuffer(CheckerContext &C, 813 ProgramStateRef state, 814 const Expr *E, SVal V, 815 bool IsSourceBuffer) { 816 Optional<Loc> L = V.getAs<Loc>(); 817 if (!L) 818 return state; 819 820 // FIXME: This is a simplified version of what's in CFRefCount.cpp -- it makes 821 // some assumptions about the value that CFRefCount can't. Even so, it should 822 // probably be refactored. 823 if (Optional<loc::MemRegionVal> MR = L->getAs<loc::MemRegionVal>()) { 824 const MemRegion *R = MR->getRegion()->StripCasts(); 825 826 // Are we dealing with an ElementRegion? If so, we should be invalidating 827 // the super-region. 828 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 829 R = ER->getSuperRegion(); 830 // FIXME: What about layers of ElementRegions? 831 } 832 833 // Invalidate this region. 834 const LocationContext *LCtx = C.getPredecessor()->getLocationContext(); 835 836 bool CausesPointerEscape = false; 837 RegionAndSymbolInvalidationTraits ITraits; 838 // Invalidate and escape only indirect regions accessible through the source 839 // buffer. 840 if (IsSourceBuffer) { 841 ITraits.setTrait(R, 842 RegionAndSymbolInvalidationTraits::TK_PreserveContents); 843 ITraits.setTrait(R, RegionAndSymbolInvalidationTraits::TK_SuppressEscape); 844 CausesPointerEscape = true; 845 } 846 847 return state->invalidateRegions(R, E, C.blockCount(), LCtx, 848 CausesPointerEscape, 0, 0, &ITraits); 849 } 850 851 // If we have a non-region value by chance, just remove the binding. 852 // FIXME: is this necessary or correct? This handles the non-Region 853 // cases. Is it ever valid to store to these? 854 return state->killBinding(*L); 855} 856 857bool CStringChecker::SummarizeRegion(raw_ostream &os, ASTContext &Ctx, 858 const MemRegion *MR) { 859 const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(MR); 860 861 switch (MR->getKind()) { 862 case MemRegion::FunctionTextRegionKind: { 863 const NamedDecl *FD = cast<FunctionTextRegion>(MR)->getDecl(); 864 if (FD) 865 os << "the address of the function '" << *FD << '\''; 866 else 867 os << "the address of a function"; 868 return true; 869 } 870 case MemRegion::BlockTextRegionKind: 871 os << "block text"; 872 return true; 873 case MemRegion::BlockDataRegionKind: 874 os << "a block"; 875 return true; 876 case MemRegion::CXXThisRegionKind: 877 case MemRegion::CXXTempObjectRegionKind: 878 os << "a C++ temp object of type " << TVR->getValueType().getAsString(); 879 return true; 880 case MemRegion::VarRegionKind: 881 os << "a variable of type" << TVR->getValueType().getAsString(); 882 return true; 883 case MemRegion::FieldRegionKind: 884 os << "a field of type " << TVR->getValueType().getAsString(); 885 return true; 886 case MemRegion::ObjCIvarRegionKind: 887 os << "an instance variable of type " << TVR->getValueType().getAsString(); 888 return true; 889 default: 890 return false; 891 } 892} 893 894//===----------------------------------------------------------------------===// 895// evaluation of individual function calls. 896//===----------------------------------------------------------------------===// 897 898void CStringChecker::evalCopyCommon(CheckerContext &C, 899 const CallExpr *CE, 900 ProgramStateRef state, 901 const Expr *Size, const Expr *Dest, 902 const Expr *Source, bool Restricted, 903 bool IsMempcpy) const { 904 CurrentFunctionDescription = "memory copy function"; 905 906 // See if the size argument is zero. 907 const LocationContext *LCtx = C.getLocationContext(); 908 SVal sizeVal = state->getSVal(Size, LCtx); 909 QualType sizeTy = Size->getType(); 910 911 ProgramStateRef stateZeroSize, stateNonZeroSize; 912 llvm::tie(stateZeroSize, stateNonZeroSize) = 913 assumeZero(C, state, sizeVal, sizeTy); 914 915 // Get the value of the Dest. 916 SVal destVal = state->getSVal(Dest, LCtx); 917 918 // If the size is zero, there won't be any actual memory access, so 919 // just bind the return value to the destination buffer and return. 920 if (stateZeroSize && !stateNonZeroSize) { 921 stateZeroSize = stateZeroSize->BindExpr(CE, LCtx, destVal); 922 C.addTransition(stateZeroSize); 923 return; 924 } 925 926 // If the size can be nonzero, we have to check the other arguments. 927 if (stateNonZeroSize) { 928 state = stateNonZeroSize; 929 930 // Ensure the destination is not null. If it is NULL there will be a 931 // NULL pointer dereference. 932 state = checkNonNull(C, state, Dest, destVal); 933 if (!state) 934 return; 935 936 // Get the value of the Src. 937 SVal srcVal = state->getSVal(Source, LCtx); 938 939 // Ensure the source is not null. If it is NULL there will be a 940 // NULL pointer dereference. 941 state = checkNonNull(C, state, Source, srcVal); 942 if (!state) 943 return; 944 945 // Ensure the accesses are valid and that the buffers do not overlap. 946 const char * const writeWarning = 947 "Memory copy function overflows destination buffer"; 948 state = CheckBufferAccess(C, state, Size, Dest, Source, 949 writeWarning, /* sourceWarning = */ NULL); 950 if (Restricted) 951 state = CheckOverlap(C, state, Size, Dest, Source); 952 953 if (!state) 954 return; 955 956 // If this is mempcpy, get the byte after the last byte copied and 957 // bind the expr. 958 if (IsMempcpy) { 959 loc::MemRegionVal destRegVal = destVal.castAs<loc::MemRegionVal>(); 960 961 // Get the length to copy. 962 if (Optional<NonLoc> lenValNonLoc = sizeVal.getAs<NonLoc>()) { 963 // Get the byte after the last byte copied. 964 SVal lastElement = C.getSValBuilder().evalBinOpLN(state, BO_Add, 965 destRegVal, 966 *lenValNonLoc, 967 Dest->getType()); 968 969 // The byte after the last byte copied is the return value. 970 state = state->BindExpr(CE, LCtx, lastElement); 971 } else { 972 // If we don't know how much we copied, we can at least 973 // conjure a return value for later. 974 SVal result = C.getSValBuilder().conjureSymbolVal(0, CE, LCtx, 975 C.blockCount()); 976 state = state->BindExpr(CE, LCtx, result); 977 } 978 979 } else { 980 // All other copies return the destination buffer. 981 // (Well, bcopy() has a void return type, but this won't hurt.) 982 state = state->BindExpr(CE, LCtx, destVal); 983 } 984 985 // Invalidate the destination (regular invalidation without pointer-escaping 986 // the address of the top-level region). 987 // FIXME: Even if we can't perfectly model the copy, we should see if we 988 // can use LazyCompoundVals to copy the source values into the destination. 989 // This would probably remove any existing bindings past the end of the 990 // copied region, but that's still an improvement over blank invalidation. 991 state = InvalidateBuffer(C, state, Dest, C.getSVal(Dest), 992 /*IsSourceBuffer*/false); 993 994 // Invalidate the source (const-invalidation without const-pointer-escaping 995 // the address of the top-level region). 996 state = InvalidateBuffer(C, state, Source, C.getSVal(Source), 997 /*IsSourceBuffer*/true); 998 999 C.addTransition(state); 1000 } 1001} 1002 1003 1004void CStringChecker::evalMemcpy(CheckerContext &C, const CallExpr *CE) const { 1005 if (CE->getNumArgs() < 3) 1006 return; 1007 1008 // void *memcpy(void *restrict dst, const void *restrict src, size_t n); 1009 // The return value is the address of the destination buffer. 1010 const Expr *Dest = CE->getArg(0); 1011 ProgramStateRef state = C.getState(); 1012 1013 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true); 1014} 1015 1016void CStringChecker::evalMempcpy(CheckerContext &C, const CallExpr *CE) const { 1017 if (CE->getNumArgs() < 3) 1018 return; 1019 1020 // void *mempcpy(void *restrict dst, const void *restrict src, size_t n); 1021 // The return value is a pointer to the byte following the last written byte. 1022 const Expr *Dest = CE->getArg(0); 1023 ProgramStateRef state = C.getState(); 1024 1025 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true, true); 1026} 1027 1028void CStringChecker::evalMemmove(CheckerContext &C, const CallExpr *CE) const { 1029 if (CE->getNumArgs() < 3) 1030 return; 1031 1032 // void *memmove(void *dst, const void *src, size_t n); 1033 // The return value is the address of the destination buffer. 1034 const Expr *Dest = CE->getArg(0); 1035 ProgramStateRef state = C.getState(); 1036 1037 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1)); 1038} 1039 1040void CStringChecker::evalBcopy(CheckerContext &C, const CallExpr *CE) const { 1041 if (CE->getNumArgs() < 3) 1042 return; 1043 1044 // void bcopy(const void *src, void *dst, size_t n); 1045 evalCopyCommon(C, CE, C.getState(), 1046 CE->getArg(2), CE->getArg(1), CE->getArg(0)); 1047} 1048 1049void CStringChecker::evalMemcmp(CheckerContext &C, const CallExpr *CE) const { 1050 if (CE->getNumArgs() < 3) 1051 return; 1052 1053 // int memcmp(const void *s1, const void *s2, size_t n); 1054 CurrentFunctionDescription = "memory comparison function"; 1055 1056 const Expr *Left = CE->getArg(0); 1057 const Expr *Right = CE->getArg(1); 1058 const Expr *Size = CE->getArg(2); 1059 1060 ProgramStateRef state = C.getState(); 1061 SValBuilder &svalBuilder = C.getSValBuilder(); 1062 1063 // See if the size argument is zero. 1064 const LocationContext *LCtx = C.getLocationContext(); 1065 SVal sizeVal = state->getSVal(Size, LCtx); 1066 QualType sizeTy = Size->getType(); 1067 1068 ProgramStateRef stateZeroSize, stateNonZeroSize; 1069 llvm::tie(stateZeroSize, stateNonZeroSize) = 1070 assumeZero(C, state, sizeVal, sizeTy); 1071 1072 // If the size can be zero, the result will be 0 in that case, and we don't 1073 // have to check either of the buffers. 1074 if (stateZeroSize) { 1075 state = stateZeroSize; 1076 state = state->BindExpr(CE, LCtx, 1077 svalBuilder.makeZeroVal(CE->getType())); 1078 C.addTransition(state); 1079 } 1080 1081 // If the size can be nonzero, we have to check the other arguments. 1082 if (stateNonZeroSize) { 1083 state = stateNonZeroSize; 1084 // If we know the two buffers are the same, we know the result is 0. 1085 // First, get the two buffers' addresses. Another checker will have already 1086 // made sure they're not undefined. 1087 DefinedOrUnknownSVal LV = 1088 state->getSVal(Left, LCtx).castAs<DefinedOrUnknownSVal>(); 1089 DefinedOrUnknownSVal RV = 1090 state->getSVal(Right, LCtx).castAs<DefinedOrUnknownSVal>(); 1091 1092 // See if they are the same. 1093 DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV); 1094 ProgramStateRef StSameBuf, StNotSameBuf; 1095 llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf); 1096 1097 // If the two arguments might be the same buffer, we know the result is 0, 1098 // and we only need to check one size. 1099 if (StSameBuf) { 1100 state = StSameBuf; 1101 state = CheckBufferAccess(C, state, Size, Left); 1102 if (state) { 1103 state = StSameBuf->BindExpr(CE, LCtx, 1104 svalBuilder.makeZeroVal(CE->getType())); 1105 C.addTransition(state); 1106 } 1107 } 1108 1109 // If the two arguments might be different buffers, we have to check the 1110 // size of both of them. 1111 if (StNotSameBuf) { 1112 state = StNotSameBuf; 1113 state = CheckBufferAccess(C, state, Size, Left, Right); 1114 if (state) { 1115 // The return value is the comparison result, which we don't know. 1116 SVal CmpV = svalBuilder.conjureSymbolVal(0, CE, LCtx, C.blockCount()); 1117 state = state->BindExpr(CE, LCtx, CmpV); 1118 C.addTransition(state); 1119 } 1120 } 1121 } 1122} 1123 1124void CStringChecker::evalstrLength(CheckerContext &C, 1125 const CallExpr *CE) const { 1126 if (CE->getNumArgs() < 1) 1127 return; 1128 1129 // size_t strlen(const char *s); 1130 evalstrLengthCommon(C, CE, /* IsStrnlen = */ false); 1131} 1132 1133void CStringChecker::evalstrnLength(CheckerContext &C, 1134 const CallExpr *CE) const { 1135 if (CE->getNumArgs() < 2) 1136 return; 1137 1138 // size_t strnlen(const char *s, size_t maxlen); 1139 evalstrLengthCommon(C, CE, /* IsStrnlen = */ true); 1140} 1141 1142void CStringChecker::evalstrLengthCommon(CheckerContext &C, const CallExpr *CE, 1143 bool IsStrnlen) const { 1144 CurrentFunctionDescription = "string length function"; 1145 ProgramStateRef state = C.getState(); 1146 const LocationContext *LCtx = C.getLocationContext(); 1147 1148 if (IsStrnlen) { 1149 const Expr *maxlenExpr = CE->getArg(1); 1150 SVal maxlenVal = state->getSVal(maxlenExpr, LCtx); 1151 1152 ProgramStateRef stateZeroSize, stateNonZeroSize; 1153 llvm::tie(stateZeroSize, stateNonZeroSize) = 1154 assumeZero(C, state, maxlenVal, maxlenExpr->getType()); 1155 1156 // If the size can be zero, the result will be 0 in that case, and we don't 1157 // have to check the string itself. 1158 if (stateZeroSize) { 1159 SVal zero = C.getSValBuilder().makeZeroVal(CE->getType()); 1160 stateZeroSize = stateZeroSize->BindExpr(CE, LCtx, zero); 1161 C.addTransition(stateZeroSize); 1162 } 1163 1164 // If the size is GUARANTEED to be zero, we're done! 1165 if (!stateNonZeroSize) 1166 return; 1167 1168 // Otherwise, record the assumption that the size is nonzero. 1169 state = stateNonZeroSize; 1170 } 1171 1172 // Check that the string argument is non-null. 1173 const Expr *Arg = CE->getArg(0); 1174 SVal ArgVal = state->getSVal(Arg, LCtx); 1175 1176 state = checkNonNull(C, state, Arg, ArgVal); 1177 1178 if (!state) 1179 return; 1180 1181 SVal strLength = getCStringLength(C, state, Arg, ArgVal); 1182 1183 // If the argument isn't a valid C string, there's no valid state to 1184 // transition to. 1185 if (strLength.isUndef()) 1186 return; 1187 1188 DefinedOrUnknownSVal result = UnknownVal(); 1189 1190 // If the check is for strnlen() then bind the return value to no more than 1191 // the maxlen value. 1192 if (IsStrnlen) { 1193 QualType cmpTy = C.getSValBuilder().getConditionType(); 1194 1195 // It's a little unfortunate to be getting this again, 1196 // but it's not that expensive... 1197 const Expr *maxlenExpr = CE->getArg(1); 1198 SVal maxlenVal = state->getSVal(maxlenExpr, LCtx); 1199 1200 Optional<NonLoc> strLengthNL = strLength.getAs<NonLoc>(); 1201 Optional<NonLoc> maxlenValNL = maxlenVal.getAs<NonLoc>(); 1202 1203 if (strLengthNL && maxlenValNL) { 1204 ProgramStateRef stateStringTooLong, stateStringNotTooLong; 1205 1206 // Check if the strLength is greater than the maxlen. 1207 llvm::tie(stateStringTooLong, stateStringNotTooLong) = 1208 state->assume(C.getSValBuilder().evalBinOpNN( 1209 state, BO_GT, *strLengthNL, *maxlenValNL, cmpTy) 1210 .castAs<DefinedOrUnknownSVal>()); 1211 1212 if (stateStringTooLong && !stateStringNotTooLong) { 1213 // If the string is longer than maxlen, return maxlen. 1214 result = *maxlenValNL; 1215 } else if (stateStringNotTooLong && !stateStringTooLong) { 1216 // If the string is shorter than maxlen, return its length. 1217 result = *strLengthNL; 1218 } 1219 } 1220 1221 if (result.isUnknown()) { 1222 // If we don't have enough information for a comparison, there's 1223 // no guarantee the full string length will actually be returned. 1224 // All we know is the return value is the min of the string length 1225 // and the limit. This is better than nothing. 1226 result = C.getSValBuilder().conjureSymbolVal(0, CE, LCtx, C.blockCount()); 1227 NonLoc resultNL = result.castAs<NonLoc>(); 1228 1229 if (strLengthNL) { 1230 state = state->assume(C.getSValBuilder().evalBinOpNN( 1231 state, BO_LE, resultNL, *strLengthNL, cmpTy) 1232 .castAs<DefinedOrUnknownSVal>(), true); 1233 } 1234 1235 if (maxlenValNL) { 1236 state = state->assume(C.getSValBuilder().evalBinOpNN( 1237 state, BO_LE, resultNL, *maxlenValNL, cmpTy) 1238 .castAs<DefinedOrUnknownSVal>(), true); 1239 } 1240 } 1241 1242 } else { 1243 // This is a plain strlen(), not strnlen(). 1244 result = strLength.castAs<DefinedOrUnknownSVal>(); 1245 1246 // If we don't know the length of the string, conjure a return 1247 // value, so it can be used in constraints, at least. 1248 if (result.isUnknown()) { 1249 result = C.getSValBuilder().conjureSymbolVal(0, CE, LCtx, C.blockCount()); 1250 } 1251 } 1252 1253 // Bind the return value. 1254 assert(!result.isUnknown() && "Should have conjured a value by now"); 1255 state = state->BindExpr(CE, LCtx, result); 1256 C.addTransition(state); 1257} 1258 1259void CStringChecker::evalStrcpy(CheckerContext &C, const CallExpr *CE) const { 1260 if (CE->getNumArgs() < 2) 1261 return; 1262 1263 // char *strcpy(char *restrict dst, const char *restrict src); 1264 evalStrcpyCommon(C, CE, 1265 /* returnEnd = */ false, 1266 /* isBounded = */ false, 1267 /* isAppending = */ false); 1268} 1269 1270void CStringChecker::evalStrncpy(CheckerContext &C, const CallExpr *CE) const { 1271 if (CE->getNumArgs() < 3) 1272 return; 1273 1274 // char *strncpy(char *restrict dst, const char *restrict src, size_t n); 1275 evalStrcpyCommon(C, CE, 1276 /* returnEnd = */ false, 1277 /* isBounded = */ true, 1278 /* isAppending = */ false); 1279} 1280 1281void CStringChecker::evalStpcpy(CheckerContext &C, const CallExpr *CE) const { 1282 if (CE->getNumArgs() < 2) 1283 return; 1284 1285 // char *stpcpy(char *restrict dst, const char *restrict src); 1286 evalStrcpyCommon(C, CE, 1287 /* returnEnd = */ true, 1288 /* isBounded = */ false, 1289 /* isAppending = */ false); 1290} 1291 1292void CStringChecker::evalStrcat(CheckerContext &C, const CallExpr *CE) const { 1293 if (CE->getNumArgs() < 2) 1294 return; 1295 1296 //char *strcat(char *restrict s1, const char *restrict s2); 1297 evalStrcpyCommon(C, CE, 1298 /* returnEnd = */ false, 1299 /* isBounded = */ false, 1300 /* isAppending = */ true); 1301} 1302 1303void CStringChecker::evalStrncat(CheckerContext &C, const CallExpr *CE) const { 1304 if (CE->getNumArgs() < 3) 1305 return; 1306 1307 //char *strncat(char *restrict s1, const char *restrict s2, size_t n); 1308 evalStrcpyCommon(C, CE, 1309 /* returnEnd = */ false, 1310 /* isBounded = */ true, 1311 /* isAppending = */ true); 1312} 1313 1314void CStringChecker::evalStrcpyCommon(CheckerContext &C, const CallExpr *CE, 1315 bool returnEnd, bool isBounded, 1316 bool isAppending) const { 1317 CurrentFunctionDescription = "string copy function"; 1318 ProgramStateRef state = C.getState(); 1319 const LocationContext *LCtx = C.getLocationContext(); 1320 1321 // Check that the destination is non-null. 1322 const Expr *Dst = CE->getArg(0); 1323 SVal DstVal = state->getSVal(Dst, LCtx); 1324 1325 state = checkNonNull(C, state, Dst, DstVal); 1326 if (!state) 1327 return; 1328 1329 // Check that the source is non-null. 1330 const Expr *srcExpr = CE->getArg(1); 1331 SVal srcVal = state->getSVal(srcExpr, LCtx); 1332 state = checkNonNull(C, state, srcExpr, srcVal); 1333 if (!state) 1334 return; 1335 1336 // Get the string length of the source. 1337 SVal strLength = getCStringLength(C, state, srcExpr, srcVal); 1338 1339 // If the source isn't a valid C string, give up. 1340 if (strLength.isUndef()) 1341 return; 1342 1343 SValBuilder &svalBuilder = C.getSValBuilder(); 1344 QualType cmpTy = svalBuilder.getConditionType(); 1345 QualType sizeTy = svalBuilder.getContext().getSizeType(); 1346 1347 // These two values allow checking two kinds of errors: 1348 // - actual overflows caused by a source that doesn't fit in the destination 1349 // - potential overflows caused by a bound that could exceed the destination 1350 SVal amountCopied = UnknownVal(); 1351 SVal maxLastElementIndex = UnknownVal(); 1352 const char *boundWarning = NULL; 1353 1354 // If the function is strncpy, strncat, etc... it is bounded. 1355 if (isBounded) { 1356 // Get the max number of characters to copy. 1357 const Expr *lenExpr = CE->getArg(2); 1358 SVal lenVal = state->getSVal(lenExpr, LCtx); 1359 1360 // Protect against misdeclared strncpy(). 1361 lenVal = svalBuilder.evalCast(lenVal, sizeTy, lenExpr->getType()); 1362 1363 Optional<NonLoc> strLengthNL = strLength.getAs<NonLoc>(); 1364 Optional<NonLoc> lenValNL = lenVal.getAs<NonLoc>(); 1365 1366 // If we know both values, we might be able to figure out how much 1367 // we're copying. 1368 if (strLengthNL && lenValNL) { 1369 ProgramStateRef stateSourceTooLong, stateSourceNotTooLong; 1370 1371 // Check if the max number to copy is less than the length of the src. 1372 // If the bound is equal to the source length, strncpy won't null- 1373 // terminate the result! 1374 llvm::tie(stateSourceTooLong, stateSourceNotTooLong) = state->assume( 1375 svalBuilder.evalBinOpNN(state, BO_GE, *strLengthNL, *lenValNL, cmpTy) 1376 .castAs<DefinedOrUnknownSVal>()); 1377 1378 if (stateSourceTooLong && !stateSourceNotTooLong) { 1379 // Max number to copy is less than the length of the src, so the actual 1380 // strLength copied is the max number arg. 1381 state = stateSourceTooLong; 1382 amountCopied = lenVal; 1383 1384 } else if (!stateSourceTooLong && stateSourceNotTooLong) { 1385 // The source buffer entirely fits in the bound. 1386 state = stateSourceNotTooLong; 1387 amountCopied = strLength; 1388 } 1389 } 1390 1391 // We still want to know if the bound is known to be too large. 1392 if (lenValNL) { 1393 if (isAppending) { 1394 // For strncat, the check is strlen(dst) + lenVal < sizeof(dst) 1395 1396 // Get the string length of the destination. If the destination is 1397 // memory that can't have a string length, we shouldn't be copying 1398 // into it anyway. 1399 SVal dstStrLength = getCStringLength(C, state, Dst, DstVal); 1400 if (dstStrLength.isUndef()) 1401 return; 1402 1403 if (Optional<NonLoc> dstStrLengthNL = dstStrLength.getAs<NonLoc>()) { 1404 maxLastElementIndex = svalBuilder.evalBinOpNN(state, BO_Add, 1405 *lenValNL, 1406 *dstStrLengthNL, 1407 sizeTy); 1408 boundWarning = "Size argument is greater than the free space in the " 1409 "destination buffer"; 1410 } 1411 1412 } else { 1413 // For strncpy, this is just checking that lenVal <= sizeof(dst) 1414 // (Yes, strncpy and strncat differ in how they treat termination. 1415 // strncat ALWAYS terminates, but strncpy doesn't.) 1416 1417 // We need a special case for when the copy size is zero, in which 1418 // case strncpy will do no work at all. Our bounds check uses n-1 1419 // as the last element accessed, so n == 0 is problematic. 1420 ProgramStateRef StateZeroSize, StateNonZeroSize; 1421 llvm::tie(StateZeroSize, StateNonZeroSize) = 1422 assumeZero(C, state, *lenValNL, sizeTy); 1423 1424 // If the size is known to be zero, we're done. 1425 if (StateZeroSize && !StateNonZeroSize) { 1426 StateZeroSize = StateZeroSize->BindExpr(CE, LCtx, DstVal); 1427 C.addTransition(StateZeroSize); 1428 return; 1429 } 1430 1431 // Otherwise, go ahead and figure out the last element we'll touch. 1432 // We don't record the non-zero assumption here because we can't 1433 // be sure. We won't warn on a possible zero. 1434 NonLoc one = svalBuilder.makeIntVal(1, sizeTy).castAs<NonLoc>(); 1435 maxLastElementIndex = svalBuilder.evalBinOpNN(state, BO_Sub, *lenValNL, 1436 one, sizeTy); 1437 boundWarning = "Size argument is greater than the length of the " 1438 "destination buffer"; 1439 } 1440 } 1441 1442 // If we couldn't pin down the copy length, at least bound it. 1443 // FIXME: We should actually run this code path for append as well, but 1444 // right now it creates problems with constraints (since we can end up 1445 // trying to pass constraints from symbol to symbol). 1446 if (amountCopied.isUnknown() && !isAppending) { 1447 // Try to get a "hypothetical" string length symbol, which we can later 1448 // set as a real value if that turns out to be the case. 1449 amountCopied = getCStringLength(C, state, lenExpr, srcVal, true); 1450 assert(!amountCopied.isUndef()); 1451 1452 if (Optional<NonLoc> amountCopiedNL = amountCopied.getAs<NonLoc>()) { 1453 if (lenValNL) { 1454 // amountCopied <= lenVal 1455 SVal copiedLessThanBound = svalBuilder.evalBinOpNN(state, BO_LE, 1456 *amountCopiedNL, 1457 *lenValNL, 1458 cmpTy); 1459 state = state->assume( 1460 copiedLessThanBound.castAs<DefinedOrUnknownSVal>(), true); 1461 if (!state) 1462 return; 1463 } 1464 1465 if (strLengthNL) { 1466 // amountCopied <= strlen(source) 1467 SVal copiedLessThanSrc = svalBuilder.evalBinOpNN(state, BO_LE, 1468 *amountCopiedNL, 1469 *strLengthNL, 1470 cmpTy); 1471 state = state->assume( 1472 copiedLessThanSrc.castAs<DefinedOrUnknownSVal>(), true); 1473 if (!state) 1474 return; 1475 } 1476 } 1477 } 1478 1479 } else { 1480 // The function isn't bounded. The amount copied should match the length 1481 // of the source buffer. 1482 amountCopied = strLength; 1483 } 1484 1485 assert(state); 1486 1487 // This represents the number of characters copied into the destination 1488 // buffer. (It may not actually be the strlen if the destination buffer 1489 // is not terminated.) 1490 SVal finalStrLength = UnknownVal(); 1491 1492 // If this is an appending function (strcat, strncat...) then set the 1493 // string length to strlen(src) + strlen(dst) since the buffer will 1494 // ultimately contain both. 1495 if (isAppending) { 1496 // Get the string length of the destination. If the destination is memory 1497 // that can't have a string length, we shouldn't be copying into it anyway. 1498 SVal dstStrLength = getCStringLength(C, state, Dst, DstVal); 1499 if (dstStrLength.isUndef()) 1500 return; 1501 1502 Optional<NonLoc> srcStrLengthNL = amountCopied.getAs<NonLoc>(); 1503 Optional<NonLoc> dstStrLengthNL = dstStrLength.getAs<NonLoc>(); 1504 1505 // If we know both string lengths, we might know the final string length. 1506 if (srcStrLengthNL && dstStrLengthNL) { 1507 // Make sure the two lengths together don't overflow a size_t. 1508 state = checkAdditionOverflow(C, state, *srcStrLengthNL, *dstStrLengthNL); 1509 if (!state) 1510 return; 1511 1512 finalStrLength = svalBuilder.evalBinOpNN(state, BO_Add, *srcStrLengthNL, 1513 *dstStrLengthNL, sizeTy); 1514 } 1515 1516 // If we couldn't get a single value for the final string length, 1517 // we can at least bound it by the individual lengths. 1518 if (finalStrLength.isUnknown()) { 1519 // Try to get a "hypothetical" string length symbol, which we can later 1520 // set as a real value if that turns out to be the case. 1521 finalStrLength = getCStringLength(C, state, CE, DstVal, true); 1522 assert(!finalStrLength.isUndef()); 1523 1524 if (Optional<NonLoc> finalStrLengthNL = finalStrLength.getAs<NonLoc>()) { 1525 if (srcStrLengthNL) { 1526 // finalStrLength >= srcStrLength 1527 SVal sourceInResult = svalBuilder.evalBinOpNN(state, BO_GE, 1528 *finalStrLengthNL, 1529 *srcStrLengthNL, 1530 cmpTy); 1531 state = state->assume(sourceInResult.castAs<DefinedOrUnknownSVal>(), 1532 true); 1533 if (!state) 1534 return; 1535 } 1536 1537 if (dstStrLengthNL) { 1538 // finalStrLength >= dstStrLength 1539 SVal destInResult = svalBuilder.evalBinOpNN(state, BO_GE, 1540 *finalStrLengthNL, 1541 *dstStrLengthNL, 1542 cmpTy); 1543 state = 1544 state->assume(destInResult.castAs<DefinedOrUnknownSVal>(), true); 1545 if (!state) 1546 return; 1547 } 1548 } 1549 } 1550 1551 } else { 1552 // Otherwise, this is a copy-over function (strcpy, strncpy, ...), and 1553 // the final string length will match the input string length. 1554 finalStrLength = amountCopied; 1555 } 1556 1557 // The final result of the function will either be a pointer past the last 1558 // copied element, or a pointer to the start of the destination buffer. 1559 SVal Result = (returnEnd ? UnknownVal() : DstVal); 1560 1561 assert(state); 1562 1563 // If the destination is a MemRegion, try to check for a buffer overflow and 1564 // record the new string length. 1565 if (Optional<loc::MemRegionVal> dstRegVal = 1566 DstVal.getAs<loc::MemRegionVal>()) { 1567 QualType ptrTy = Dst->getType(); 1568 1569 // If we have an exact value on a bounded copy, use that to check for 1570 // overflows, rather than our estimate about how much is actually copied. 1571 if (boundWarning) { 1572 if (Optional<NonLoc> maxLastNL = maxLastElementIndex.getAs<NonLoc>()) { 1573 SVal maxLastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal, 1574 *maxLastNL, ptrTy); 1575 state = CheckLocation(C, state, CE->getArg(2), maxLastElement, 1576 boundWarning); 1577 if (!state) 1578 return; 1579 } 1580 } 1581 1582 // Then, if the final length is known... 1583 if (Optional<NonLoc> knownStrLength = finalStrLength.getAs<NonLoc>()) { 1584 SVal lastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal, 1585 *knownStrLength, ptrTy); 1586 1587 // ...and we haven't checked the bound, we'll check the actual copy. 1588 if (!boundWarning) { 1589 const char * const warningMsg = 1590 "String copy function overflows destination buffer"; 1591 state = CheckLocation(C, state, Dst, lastElement, warningMsg); 1592 if (!state) 1593 return; 1594 } 1595 1596 // If this is a stpcpy-style copy, the last element is the return value. 1597 if (returnEnd) 1598 Result = lastElement; 1599 } 1600 1601 // Invalidate the destination (regular invalidation without pointer-escaping 1602 // the address of the top-level region). This must happen before we set the 1603 // C string length because invalidation will clear the length. 1604 // FIXME: Even if we can't perfectly model the copy, we should see if we 1605 // can use LazyCompoundVals to copy the source values into the destination. 1606 // This would probably remove any existing bindings past the end of the 1607 // string, but that's still an improvement over blank invalidation. 1608 state = InvalidateBuffer(C, state, Dst, *dstRegVal, 1609 /*IsSourceBuffer*/false); 1610 1611 // Invalidate the source (const-invalidation without const-pointer-escaping 1612 // the address of the top-level region). 1613 state = InvalidateBuffer(C, state, srcExpr, srcVal, /*IsSourceBuffer*/true); 1614 1615 // Set the C string length of the destination, if we know it. 1616 if (isBounded && !isAppending) { 1617 // strncpy is annoying in that it doesn't guarantee to null-terminate 1618 // the result string. If the original string didn't fit entirely inside 1619 // the bound (including the null-terminator), we don't know how long the 1620 // result is. 1621 if (amountCopied != strLength) 1622 finalStrLength = UnknownVal(); 1623 } 1624 state = setCStringLength(state, dstRegVal->getRegion(), finalStrLength); 1625 } 1626 1627 assert(state); 1628 1629 // If this is a stpcpy-style copy, but we were unable to check for a buffer 1630 // overflow, we still need a result. Conjure a return value. 1631 if (returnEnd && Result.isUnknown()) { 1632 Result = svalBuilder.conjureSymbolVal(0, CE, LCtx, C.blockCount()); 1633 } 1634 1635 // Set the return value. 1636 state = state->BindExpr(CE, LCtx, Result); 1637 C.addTransition(state); 1638} 1639 1640void CStringChecker::evalStrcmp(CheckerContext &C, const CallExpr *CE) const { 1641 if (CE->getNumArgs() < 2) 1642 return; 1643 1644 //int strcmp(const char *s1, const char *s2); 1645 evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ false); 1646} 1647 1648void CStringChecker::evalStrncmp(CheckerContext &C, const CallExpr *CE) const { 1649 if (CE->getNumArgs() < 3) 1650 return; 1651 1652 //int strncmp(const char *s1, const char *s2, size_t n); 1653 evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ false); 1654} 1655 1656void CStringChecker::evalStrcasecmp(CheckerContext &C, 1657 const CallExpr *CE) const { 1658 if (CE->getNumArgs() < 2) 1659 return; 1660 1661 //int strcasecmp(const char *s1, const char *s2); 1662 evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ true); 1663} 1664 1665void CStringChecker::evalStrncasecmp(CheckerContext &C, 1666 const CallExpr *CE) const { 1667 if (CE->getNumArgs() < 3) 1668 return; 1669 1670 //int strncasecmp(const char *s1, const char *s2, size_t n); 1671 evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ true); 1672} 1673 1674void CStringChecker::evalStrcmpCommon(CheckerContext &C, const CallExpr *CE, 1675 bool isBounded, bool ignoreCase) const { 1676 CurrentFunctionDescription = "string comparison function"; 1677 ProgramStateRef state = C.getState(); 1678 const LocationContext *LCtx = C.getLocationContext(); 1679 1680 // Check that the first string is non-null 1681 const Expr *s1 = CE->getArg(0); 1682 SVal s1Val = state->getSVal(s1, LCtx); 1683 state = checkNonNull(C, state, s1, s1Val); 1684 if (!state) 1685 return; 1686 1687 // Check that the second string is non-null. 1688 const Expr *s2 = CE->getArg(1); 1689 SVal s2Val = state->getSVal(s2, LCtx); 1690 state = checkNonNull(C, state, s2, s2Val); 1691 if (!state) 1692 return; 1693 1694 // Get the string length of the first string or give up. 1695 SVal s1Length = getCStringLength(C, state, s1, s1Val); 1696 if (s1Length.isUndef()) 1697 return; 1698 1699 // Get the string length of the second string or give up. 1700 SVal s2Length = getCStringLength(C, state, s2, s2Val); 1701 if (s2Length.isUndef()) 1702 return; 1703 1704 // If we know the two buffers are the same, we know the result is 0. 1705 // First, get the two buffers' addresses. Another checker will have already 1706 // made sure they're not undefined. 1707 DefinedOrUnknownSVal LV = s1Val.castAs<DefinedOrUnknownSVal>(); 1708 DefinedOrUnknownSVal RV = s2Val.castAs<DefinedOrUnknownSVal>(); 1709 1710 // See if they are the same. 1711 SValBuilder &svalBuilder = C.getSValBuilder(); 1712 DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV); 1713 ProgramStateRef StSameBuf, StNotSameBuf; 1714 llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf); 1715 1716 // If the two arguments might be the same buffer, we know the result is 0, 1717 // and we only need to check one size. 1718 if (StSameBuf) { 1719 StSameBuf = StSameBuf->BindExpr(CE, LCtx, 1720 svalBuilder.makeZeroVal(CE->getType())); 1721 C.addTransition(StSameBuf); 1722 1723 // If the two arguments are GUARANTEED to be the same, we're done! 1724 if (!StNotSameBuf) 1725 return; 1726 } 1727 1728 assert(StNotSameBuf); 1729 state = StNotSameBuf; 1730 1731 // At this point we can go about comparing the two buffers. 1732 // For now, we only do this if they're both known string literals. 1733 1734 // Attempt to extract string literals from both expressions. 1735 const StringLiteral *s1StrLiteral = getCStringLiteral(C, state, s1, s1Val); 1736 const StringLiteral *s2StrLiteral = getCStringLiteral(C, state, s2, s2Val); 1737 bool canComputeResult = false; 1738 1739 if (s1StrLiteral && s2StrLiteral) { 1740 StringRef s1StrRef = s1StrLiteral->getString(); 1741 StringRef s2StrRef = s2StrLiteral->getString(); 1742 1743 if (isBounded) { 1744 // Get the max number of characters to compare. 1745 const Expr *lenExpr = CE->getArg(2); 1746 SVal lenVal = state->getSVal(lenExpr, LCtx); 1747 1748 // If the length is known, we can get the right substrings. 1749 if (const llvm::APSInt *len = svalBuilder.getKnownValue(state, lenVal)) { 1750 // Create substrings of each to compare the prefix. 1751 s1StrRef = s1StrRef.substr(0, (size_t)len->getZExtValue()); 1752 s2StrRef = s2StrRef.substr(0, (size_t)len->getZExtValue()); 1753 canComputeResult = true; 1754 } 1755 } else { 1756 // This is a normal, unbounded strcmp. 1757 canComputeResult = true; 1758 } 1759 1760 if (canComputeResult) { 1761 // Real strcmp stops at null characters. 1762 size_t s1Term = s1StrRef.find('\0'); 1763 if (s1Term != StringRef::npos) 1764 s1StrRef = s1StrRef.substr(0, s1Term); 1765 1766 size_t s2Term = s2StrRef.find('\0'); 1767 if (s2Term != StringRef::npos) 1768 s2StrRef = s2StrRef.substr(0, s2Term); 1769 1770 // Use StringRef's comparison methods to compute the actual result. 1771 int result; 1772 1773 if (ignoreCase) { 1774 // Compare string 1 to string 2 the same way strcasecmp() does. 1775 result = s1StrRef.compare_lower(s2StrRef); 1776 } else { 1777 // Compare string 1 to string 2 the same way strcmp() does. 1778 result = s1StrRef.compare(s2StrRef); 1779 } 1780 1781 // Build the SVal of the comparison and bind the return value. 1782 SVal resultVal = svalBuilder.makeIntVal(result, CE->getType()); 1783 state = state->BindExpr(CE, LCtx, resultVal); 1784 } 1785 } 1786 1787 if (!canComputeResult) { 1788 // Conjure a symbolic value. It's the best we can do. 1789 SVal resultVal = svalBuilder.conjureSymbolVal(0, CE, LCtx, C.blockCount()); 1790 state = state->BindExpr(CE, LCtx, resultVal); 1791 } 1792 1793 // Record this as a possible path. 1794 C.addTransition(state); 1795} 1796 1797void CStringChecker::evalStrsep(CheckerContext &C, const CallExpr *CE) const { 1798 //char *strsep(char **stringp, const char *delim); 1799 if (CE->getNumArgs() < 2) 1800 return; 1801 1802 // Sanity: does the search string parameter match the return type? 1803 const Expr *SearchStrPtr = CE->getArg(0); 1804 QualType CharPtrTy = SearchStrPtr->getType()->getPointeeType(); 1805 if (CharPtrTy.isNull() || 1806 CE->getType().getUnqualifiedType() != CharPtrTy.getUnqualifiedType()) 1807 return; 1808 1809 CurrentFunctionDescription = "strsep()"; 1810 ProgramStateRef State = C.getState(); 1811 const LocationContext *LCtx = C.getLocationContext(); 1812 1813 // Check that the search string pointer is non-null (though it may point to 1814 // a null string). 1815 SVal SearchStrVal = State->getSVal(SearchStrPtr, LCtx); 1816 State = checkNonNull(C, State, SearchStrPtr, SearchStrVal); 1817 if (!State) 1818 return; 1819 1820 // Check that the delimiter string is non-null. 1821 const Expr *DelimStr = CE->getArg(1); 1822 SVal DelimStrVal = State->getSVal(DelimStr, LCtx); 1823 State = checkNonNull(C, State, DelimStr, DelimStrVal); 1824 if (!State) 1825 return; 1826 1827 SValBuilder &SVB = C.getSValBuilder(); 1828 SVal Result; 1829 if (Optional<Loc> SearchStrLoc = SearchStrVal.getAs<Loc>()) { 1830 // Get the current value of the search string pointer, as a char*. 1831 Result = State->getSVal(*SearchStrLoc, CharPtrTy); 1832 1833 // Invalidate the search string, representing the change of one delimiter 1834 // character to NUL. 1835 State = InvalidateBuffer(C, State, SearchStrPtr, Result, 1836 /*IsSourceBuffer*/false); 1837 1838 // Overwrite the search string pointer. The new value is either an address 1839 // further along in the same string, or NULL if there are no more tokens. 1840 State = State->bindLoc(*SearchStrLoc, 1841 SVB.conjureSymbolVal(getTag(), CE, LCtx, CharPtrTy, 1842 C.blockCount())); 1843 } else { 1844 assert(SearchStrVal.isUnknown()); 1845 // Conjure a symbolic value. It's the best we can do. 1846 Result = SVB.conjureSymbolVal(0, CE, LCtx, C.blockCount()); 1847 } 1848 1849 // Set the return value, and finish. 1850 State = State->BindExpr(CE, LCtx, Result); 1851 C.addTransition(State); 1852} 1853 1854 1855//===----------------------------------------------------------------------===// 1856// The driver method, and other Checker callbacks. 1857//===----------------------------------------------------------------------===// 1858 1859bool CStringChecker::evalCall(const CallExpr *CE, CheckerContext &C) const { 1860 const FunctionDecl *FDecl = C.getCalleeDecl(CE); 1861 1862 if (!FDecl) 1863 return false; 1864 1865 // FIXME: Poorly-factored string switches are slow. 1866 FnCheck evalFunction = 0; 1867 if (C.isCLibraryFunction(FDecl, "memcpy")) 1868 evalFunction = &CStringChecker::evalMemcpy; 1869 else if (C.isCLibraryFunction(FDecl, "mempcpy")) 1870 evalFunction = &CStringChecker::evalMempcpy; 1871 else if (C.isCLibraryFunction(FDecl, "memcmp")) 1872 evalFunction = &CStringChecker::evalMemcmp; 1873 else if (C.isCLibraryFunction(FDecl, "memmove")) 1874 evalFunction = &CStringChecker::evalMemmove; 1875 else if (C.isCLibraryFunction(FDecl, "strcpy")) 1876 evalFunction = &CStringChecker::evalStrcpy; 1877 else if (C.isCLibraryFunction(FDecl, "strncpy")) 1878 evalFunction = &CStringChecker::evalStrncpy; 1879 else if (C.isCLibraryFunction(FDecl, "stpcpy")) 1880 evalFunction = &CStringChecker::evalStpcpy; 1881 else if (C.isCLibraryFunction(FDecl, "strcat")) 1882 evalFunction = &CStringChecker::evalStrcat; 1883 else if (C.isCLibraryFunction(FDecl, "strncat")) 1884 evalFunction = &CStringChecker::evalStrncat; 1885 else if (C.isCLibraryFunction(FDecl, "strlen")) 1886 evalFunction = &CStringChecker::evalstrLength; 1887 else if (C.isCLibraryFunction(FDecl, "strnlen")) 1888 evalFunction = &CStringChecker::evalstrnLength; 1889 else if (C.isCLibraryFunction(FDecl, "strcmp")) 1890 evalFunction = &CStringChecker::evalStrcmp; 1891 else if (C.isCLibraryFunction(FDecl, "strncmp")) 1892 evalFunction = &CStringChecker::evalStrncmp; 1893 else if (C.isCLibraryFunction(FDecl, "strcasecmp")) 1894 evalFunction = &CStringChecker::evalStrcasecmp; 1895 else if (C.isCLibraryFunction(FDecl, "strncasecmp")) 1896 evalFunction = &CStringChecker::evalStrncasecmp; 1897 else if (C.isCLibraryFunction(FDecl, "strsep")) 1898 evalFunction = &CStringChecker::evalStrsep; 1899 else if (C.isCLibraryFunction(FDecl, "bcopy")) 1900 evalFunction = &CStringChecker::evalBcopy; 1901 else if (C.isCLibraryFunction(FDecl, "bcmp")) 1902 evalFunction = &CStringChecker::evalMemcmp; 1903 1904 // If the callee isn't a string function, let another checker handle it. 1905 if (!evalFunction) 1906 return false; 1907 1908 // Make sure each function sets its own description. 1909 // (But don't bother in a release build.) 1910 assert(!(CurrentFunctionDescription = NULL)); 1911 1912 // Check and evaluate the call. 1913 (this->*evalFunction)(C, CE); 1914 1915 // If the evaluate call resulted in no change, chain to the next eval call 1916 // handler. 1917 // Note, the custom CString evaluation calls assume that basic safety 1918 // properties are held. However, if the user chooses to turn off some of these 1919 // checks, we ignore the issues and leave the call evaluation to a generic 1920 // handler. 1921 if (!C.isDifferent()) 1922 return false; 1923 1924 return true; 1925} 1926 1927void CStringChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const { 1928 // Record string length for char a[] = "abc"; 1929 ProgramStateRef state = C.getState(); 1930 1931 for (DeclStmt::const_decl_iterator I = DS->decl_begin(), E = DS->decl_end(); 1932 I != E; ++I) { 1933 const VarDecl *D = dyn_cast<VarDecl>(*I); 1934 if (!D) 1935 continue; 1936 1937 // FIXME: Handle array fields of structs. 1938 if (!D->getType()->isArrayType()) 1939 continue; 1940 1941 const Expr *Init = D->getInit(); 1942 if (!Init) 1943 continue; 1944 if (!isa<StringLiteral>(Init)) 1945 continue; 1946 1947 Loc VarLoc = state->getLValue(D, C.getLocationContext()); 1948 const MemRegion *MR = VarLoc.getAsRegion(); 1949 if (!MR) 1950 continue; 1951 1952 SVal StrVal = state->getSVal(Init, C.getLocationContext()); 1953 assert(StrVal.isValid() && "Initializer string is unknown or undefined"); 1954 DefinedOrUnknownSVal strLength = 1955 getCStringLength(C, state, Init, StrVal).castAs<DefinedOrUnknownSVal>(); 1956 1957 state = state->set<CStringLength>(MR, strLength); 1958 } 1959 1960 C.addTransition(state); 1961} 1962 1963bool CStringChecker::wantsRegionChangeUpdate(ProgramStateRef state) const { 1964 CStringLengthTy Entries = state->get<CStringLength>(); 1965 return !Entries.isEmpty(); 1966} 1967 1968ProgramStateRef 1969CStringChecker::checkRegionChanges(ProgramStateRef state, 1970 const InvalidatedSymbols *, 1971 ArrayRef<const MemRegion *> ExplicitRegions, 1972 ArrayRef<const MemRegion *> Regions, 1973 const CallEvent *Call) const { 1974 CStringLengthTy Entries = state->get<CStringLength>(); 1975 if (Entries.isEmpty()) 1976 return state; 1977 1978 llvm::SmallPtrSet<const MemRegion *, 8> Invalidated; 1979 llvm::SmallPtrSet<const MemRegion *, 32> SuperRegions; 1980 1981 // First build sets for the changed regions and their super-regions. 1982 for (ArrayRef<const MemRegion *>::iterator 1983 I = Regions.begin(), E = Regions.end(); I != E; ++I) { 1984 const MemRegion *MR = *I; 1985 Invalidated.insert(MR); 1986 1987 SuperRegions.insert(MR); 1988 while (const SubRegion *SR = dyn_cast<SubRegion>(MR)) { 1989 MR = SR->getSuperRegion(); 1990 SuperRegions.insert(MR); 1991 } 1992 } 1993 1994 CStringLengthTy::Factory &F = state->get_context<CStringLength>(); 1995 1996 // Then loop over the entries in the current state. 1997 for (CStringLengthTy::iterator I = Entries.begin(), 1998 E = Entries.end(); I != E; ++I) { 1999 const MemRegion *MR = I.getKey(); 2000 2001 // Is this entry for a super-region of a changed region? 2002 if (SuperRegions.count(MR)) { 2003 Entries = F.remove(Entries, MR); 2004 continue; 2005 } 2006 2007 // Is this entry for a sub-region of a changed region? 2008 const MemRegion *Super = MR; 2009 while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) { 2010 Super = SR->getSuperRegion(); 2011 if (Invalidated.count(Super)) { 2012 Entries = F.remove(Entries, MR); 2013 break; 2014 } 2015 } 2016 } 2017 2018 return state->set<CStringLength>(Entries); 2019} 2020 2021void CStringChecker::checkLiveSymbols(ProgramStateRef state, 2022 SymbolReaper &SR) const { 2023 // Mark all symbols in our string length map as valid. 2024 CStringLengthTy Entries = state->get<CStringLength>(); 2025 2026 for (CStringLengthTy::iterator I = Entries.begin(), E = Entries.end(); 2027 I != E; ++I) { 2028 SVal Len = I.getData(); 2029 2030 for (SymExpr::symbol_iterator si = Len.symbol_begin(), 2031 se = Len.symbol_end(); si != se; ++si) 2032 SR.markInUse(*si); 2033 } 2034} 2035 2036void CStringChecker::checkDeadSymbols(SymbolReaper &SR, 2037 CheckerContext &C) const { 2038 if (!SR.hasDeadSymbols()) 2039 return; 2040 2041 ProgramStateRef state = C.getState(); 2042 CStringLengthTy Entries = state->get<CStringLength>(); 2043 if (Entries.isEmpty()) 2044 return; 2045 2046 CStringLengthTy::Factory &F = state->get_context<CStringLength>(); 2047 for (CStringLengthTy::iterator I = Entries.begin(), E = Entries.end(); 2048 I != E; ++I) { 2049 SVal Len = I.getData(); 2050 if (SymbolRef Sym = Len.getAsSymbol()) { 2051 if (SR.isDead(Sym)) 2052 Entries = F.remove(Entries, I.getKey()); 2053 } 2054 } 2055 2056 state = state->set<CStringLength>(Entries); 2057 C.addTransition(state); 2058} 2059 2060#define REGISTER_CHECKER(name) \ 2061void ento::register##name(CheckerManager &mgr) {\ 2062 mgr.registerChecker<CStringChecker>()->Filter.Check##name = true; \ 2063} 2064 2065REGISTER_CHECKER(CStringNullArg) 2066REGISTER_CHECKER(CStringOutOfBounds) 2067REGISTER_CHECKER(CStringBufferOverlap) 2068REGISTER_CHECKER(CStringNotNullTerm) 2069 2070void ento::registerCStringCheckerBasic(CheckerManager &Mgr) { 2071 registerCStringNullArg(Mgr); 2072} 2073