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