CStringChecker.cpp revision fc8f0e14ad142ed811e90fbd9a30e419e301c717
1//= CStringChecker.h - 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 "clang/StaticAnalyzer/Core/Checker.h" 17#include "clang/StaticAnalyzer/Core/CheckerManager.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 19#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 20#include "clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h" 21#include "llvm/ADT/StringSwitch.h" 22 23using namespace clang; 24using namespace ento; 25 26namespace { 27class CStringChecker : public Checker< eval::Call, 28 check::PreStmt<DeclStmt>, 29 check::LiveSymbols, 30 check::DeadSymbols, 31 check::RegionChanges 32 > { 33 mutable llvm::OwningPtr<BugType> BT_Null, BT_Bounds, BT_BoundsWrite, 34 BT_Overlap, BT_NotCString; 35public: 36 static void *getTag() { static int tag; return &tag; } 37 38 bool evalCall(const CallExpr *CE, CheckerContext &C) const; 39 void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const; 40 void checkLiveSymbols(const GRState *state, SymbolReaper &SR) const; 41 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; 42 bool wantsRegionChangeUpdate(const GRState *state) const; 43 44 const GRState *checkRegionChanges(const GRState *state, 45 const MemRegion * const *Begin, 46 const MemRegion * const *End) const; 47 48 typedef void (CStringChecker::*FnCheck)(CheckerContext &, 49 const CallExpr *) const; 50 51 void evalMemcpy(CheckerContext &C, const CallExpr *CE) const; 52 void evalMempcpy(CheckerContext &C, const CallExpr *CE) const; 53 void evalMemmove(CheckerContext &C, const CallExpr *CE) const; 54 void evalBcopy(CheckerContext &C, const CallExpr *CE) const; 55 void evalCopyCommon(CheckerContext &C, const CallExpr *CE, 56 const GRState *state, 57 const Expr *Size, const Expr *Source, const Expr *Dest, 58 bool Restricted = false, 59 bool IsMempcpy = false) const; 60 61 void evalMemcmp(CheckerContext &C, const CallExpr *CE) const; 62 63 void evalstrLength(CheckerContext &C, const CallExpr *CE) const; 64 void evalstrnLength(CheckerContext &C, const CallExpr *CE) const; 65 void evalstrLengthCommon(CheckerContext &C, const CallExpr *CE, 66 bool IsStrnlen = false) const; 67 68 void evalStrcpy(CheckerContext &C, const CallExpr *CE) const; 69 void evalStrncpy(CheckerContext &C, const CallExpr *CE) const; 70 void evalStpcpy(CheckerContext &C, const CallExpr *CE) const; 71 void evalStrcpyCommon(CheckerContext &C, const CallExpr *CE, bool returnEnd, 72 bool isBounded, bool isAppending) const; 73 74 void evalStrcat(CheckerContext &C, const CallExpr *CE) const; 75 void evalStrncat(CheckerContext &C, const CallExpr *CE) const; 76 77 void evalStrcmp(CheckerContext &C, const CallExpr *CE) const; 78 79 // Utility methods 80 std::pair<const GRState*, const GRState*> 81 static assumeZero(CheckerContext &C, 82 const GRState *state, SVal V, QualType Ty); 83 84 static const GRState *setCStringLength(const GRState *state, 85 const MemRegion *MR, SVal strLength); 86 static SVal getCStringLengthForRegion(CheckerContext &C, 87 const GRState *&state, 88 const Expr *Ex, const MemRegion *MR); 89 SVal getCStringLength(CheckerContext &C, const GRState *&state, 90 const Expr *Ex, SVal Buf) const; 91 92 const StringLiteral *getCStringLiteral(CheckerContext &C, 93 const GRState *&state, 94 const Expr *expr, 95 SVal val) const; 96 97 static const GRState *InvalidateBuffer(CheckerContext &C, 98 const GRState *state, 99 const Expr *Ex, SVal V); 100 101 static bool SummarizeRegion(llvm::raw_ostream& os, ASTContext& Ctx, 102 const MemRegion *MR); 103 104 // Re-usable checks 105 const GRState *checkNonNull(CheckerContext &C, const GRState *state, 106 const Expr *S, SVal l) const; 107 const GRState *CheckLocation(CheckerContext &C, const GRState *state, 108 const Expr *S, SVal l, 109 bool IsDestination = false) const; 110 const GRState *CheckBufferAccess(CheckerContext &C, const GRState *state, 111 const Expr *Size, 112 const Expr *FirstBuf, 113 const Expr *SecondBuf = NULL, 114 bool FirstIsDestination = false) const; 115 const GRState *CheckOverlap(CheckerContext &C, const GRState *state, 116 const Expr *Size, const Expr *First, 117 const Expr *Second) const; 118 void emitOverlapBug(CheckerContext &C, const GRState *state, 119 const Stmt *First, const Stmt *Second) const; 120}; 121 122class CStringLength { 123public: 124 typedef llvm::ImmutableMap<const MemRegion *, SVal> EntryMap; 125}; 126} //end anonymous namespace 127 128namespace clang { 129namespace ento { 130 template <> 131 struct GRStateTrait<CStringLength> 132 : public GRStatePartialTrait<CStringLength::EntryMap> { 133 static void *GDMIndex() { return CStringChecker::getTag(); } 134 }; 135} 136} 137 138//===----------------------------------------------------------------------===// 139// Individual checks and utility methods. 140//===----------------------------------------------------------------------===// 141 142std::pair<const GRState*, const GRState*> 143CStringChecker::assumeZero(CheckerContext &C, const GRState *state, SVal V, 144 QualType Ty) { 145 DefinedSVal *val = dyn_cast<DefinedSVal>(&V); 146 if (!val) 147 return std::pair<const GRState*, const GRState *>(state, state); 148 149 SValBuilder &svalBuilder = C.getSValBuilder(); 150 DefinedOrUnknownSVal zero = svalBuilder.makeZeroVal(Ty); 151 return state->assume(svalBuilder.evalEQ(state, *val, zero)); 152} 153 154const GRState *CStringChecker::checkNonNull(CheckerContext &C, 155 const GRState *state, 156 const Expr *S, SVal l) const { 157 // If a previous check has failed, propagate the failure. 158 if (!state) 159 return NULL; 160 161 const GRState *stateNull, *stateNonNull; 162 llvm::tie(stateNull, stateNonNull) = assumeZero(C, state, l, S->getType()); 163 164 if (stateNull && !stateNonNull) { 165 ExplodedNode *N = C.generateSink(stateNull); 166 if (!N) 167 return NULL; 168 169 if (!BT_Null) 170 BT_Null.reset(new BuiltinBug("API", 171 "Null pointer argument in call to byte string function")); 172 173 // Generate a report for this bug. 174 BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Null.get()); 175 EnhancedBugReport *report = new EnhancedBugReport(*BT, 176 BT->getDescription(), N); 177 178 report->addRange(S->getSourceRange()); 179 report->addVisitorCreator(bugreporter::registerTrackNullOrUndefValue, S); 180 C.EmitReport(report); 181 return NULL; 182 } 183 184 // From here on, assume that the value is non-null. 185 assert(stateNonNull); 186 return stateNonNull; 187} 188 189// FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor? 190const GRState *CStringChecker::CheckLocation(CheckerContext &C, 191 const GRState *state, 192 const Expr *S, SVal l, 193 bool IsDestination) const { 194 // If a previous check has failed, propagate the failure. 195 if (!state) 196 return NULL; 197 198 // Check for out of bound array element access. 199 const MemRegion *R = l.getAsRegion(); 200 if (!R) 201 return state; 202 203 const ElementRegion *ER = dyn_cast<ElementRegion>(R); 204 if (!ER) 205 return state; 206 207 assert(ER->getValueType() == C.getASTContext().CharTy && 208 "CheckLocation should only be called with char* ElementRegions"); 209 210 // Get the size of the array. 211 const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion()); 212 SValBuilder &svalBuilder = C.getSValBuilder(); 213 SVal Extent = svalBuilder.convertToArrayIndex(superReg->getExtent(svalBuilder)); 214 DefinedOrUnknownSVal Size = cast<DefinedOrUnknownSVal>(Extent); 215 216 // Get the index of the accessed element. 217 DefinedOrUnknownSVal Idx = cast<DefinedOrUnknownSVal>(ER->getIndex()); 218 219 const GRState *StInBound = state->assumeInBound(Idx, Size, true); 220 const GRState *StOutBound = state->assumeInBound(Idx, Size, false); 221 if (StOutBound && !StInBound) { 222 ExplodedNode *N = C.generateSink(StOutBound); 223 if (!N) 224 return NULL; 225 226 BuiltinBug *BT; 227 if (IsDestination) { 228 if (!BT_BoundsWrite) { 229 BT_BoundsWrite.reset(new BuiltinBug("Out-of-bound array access", 230 "Byte string function overflows destination buffer")); 231 } 232 BT = static_cast<BuiltinBug*>(BT_BoundsWrite.get()); 233 } else { 234 if (!BT_Bounds) { 235 BT_Bounds.reset(new BuiltinBug("Out-of-bound array access", 236 "Byte string function accesses out-of-bound array element")); 237 } 238 BT = static_cast<BuiltinBug*>(BT_Bounds.get()); 239 } 240 241 // FIXME: It would be nice to eventually make this diagnostic more clear, 242 // e.g., by referencing the original declaration or by saying *why* this 243 // reference is outside the range. 244 245 // Generate a report for this bug. 246 RangedBugReport *report = new RangedBugReport(*BT, BT->getDescription(), N); 247 248 report->addRange(S->getSourceRange()); 249 C.EmitReport(report); 250 return NULL; 251 } 252 253 // Array bound check succeeded. From this point forward the array bound 254 // should always succeed. 255 return StInBound; 256} 257 258const GRState *CStringChecker::CheckBufferAccess(CheckerContext &C, 259 const GRState *state, 260 const Expr *Size, 261 const Expr *FirstBuf, 262 const Expr *SecondBuf, 263 bool FirstIsDestination) const { 264 // If a previous check has failed, propagate the failure. 265 if (!state) 266 return NULL; 267 268 SValBuilder &svalBuilder = C.getSValBuilder(); 269 ASTContext &Ctx = C.getASTContext(); 270 271 QualType sizeTy = Size->getType(); 272 QualType PtrTy = Ctx.getPointerType(Ctx.CharTy); 273 274 // Check that the first buffer is non-null. 275 SVal BufVal = state->getSVal(FirstBuf); 276 state = checkNonNull(C, state, FirstBuf, BufVal); 277 if (!state) 278 return NULL; 279 280 // Get the access length and make sure it is known. 281 SVal LengthVal = state->getSVal(Size); 282 NonLoc *Length = dyn_cast<NonLoc>(&LengthVal); 283 if (!Length) 284 return state; 285 286 // Compute the offset of the last element to be accessed: size-1. 287 NonLoc One = cast<NonLoc>(svalBuilder.makeIntVal(1, sizeTy)); 288 NonLoc LastOffset = cast<NonLoc>(svalBuilder.evalBinOpNN(state, BO_Sub, 289 *Length, One, sizeTy)); 290 291 // Check that the first buffer is sufficiently long. 292 SVal BufStart = svalBuilder.evalCast(BufVal, PtrTy, FirstBuf->getType()); 293 if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) { 294 SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc, 295 LastOffset, PtrTy); 296 state = CheckLocation(C, state, FirstBuf, BufEnd, FirstIsDestination); 297 298 // If the buffer isn't large enough, abort. 299 if (!state) 300 return NULL; 301 } 302 303 // If there's a second buffer, check it as well. 304 if (SecondBuf) { 305 BufVal = state->getSVal(SecondBuf); 306 state = checkNonNull(C, state, SecondBuf, BufVal); 307 if (!state) 308 return NULL; 309 310 BufStart = svalBuilder.evalCast(BufVal, PtrTy, SecondBuf->getType()); 311 if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) { 312 SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc, 313 LastOffset, PtrTy); 314 state = CheckLocation(C, state, SecondBuf, BufEnd); 315 } 316 } 317 318 // Large enough or not, return this state! 319 return state; 320} 321 322const GRState *CStringChecker::CheckOverlap(CheckerContext &C, 323 const GRState *state, 324 const Expr *Size, 325 const Expr *First, 326 const Expr *Second) const { 327 // Do a simple check for overlap: if the two arguments are from the same 328 // buffer, see if the end of the first is greater than the start of the second 329 // or vice versa. 330 331 // If a previous check has failed, propagate the failure. 332 if (!state) 333 return NULL; 334 335 const GRState *stateTrue, *stateFalse; 336 337 // Get the buffer values and make sure they're known locations. 338 SVal firstVal = state->getSVal(First); 339 SVal secondVal = state->getSVal(Second); 340 341 Loc *firstLoc = dyn_cast<Loc>(&firstVal); 342 if (!firstLoc) 343 return state; 344 345 Loc *secondLoc = dyn_cast<Loc>(&secondVal); 346 if (!secondLoc) 347 return state; 348 349 // Are the two values the same? 350 SValBuilder &svalBuilder = C.getSValBuilder(); 351 llvm::tie(stateTrue, stateFalse) = 352 state->assume(svalBuilder.evalEQ(state, *firstLoc, *secondLoc)); 353 354 if (stateTrue && !stateFalse) { 355 // If the values are known to be equal, that's automatically an overlap. 356 emitOverlapBug(C, stateTrue, First, Second); 357 return NULL; 358 } 359 360 // assume the two expressions are not equal. 361 assert(stateFalse); 362 state = stateFalse; 363 364 // Which value comes first? 365 ASTContext &Ctx = svalBuilder.getContext(); 366 QualType cmpTy = Ctx.IntTy; 367 SVal reverse = svalBuilder.evalBinOpLL(state, BO_GT, 368 *firstLoc, *secondLoc, cmpTy); 369 DefinedOrUnknownSVal *reverseTest = dyn_cast<DefinedOrUnknownSVal>(&reverse); 370 if (!reverseTest) 371 return state; 372 373 llvm::tie(stateTrue, stateFalse) = state->assume(*reverseTest); 374 if (stateTrue) { 375 if (stateFalse) { 376 // If we don't know which one comes first, we can't perform this test. 377 return state; 378 } else { 379 // Switch the values so that firstVal is before secondVal. 380 Loc *tmpLoc = firstLoc; 381 firstLoc = secondLoc; 382 secondLoc = tmpLoc; 383 384 // Switch the Exprs as well, so that they still correspond. 385 const Expr *tmpExpr = First; 386 First = Second; 387 Second = tmpExpr; 388 } 389 } 390 391 // Get the length, and make sure it too is known. 392 SVal LengthVal = state->getSVal(Size); 393 NonLoc *Length = dyn_cast<NonLoc>(&LengthVal); 394 if (!Length) 395 return state; 396 397 // Convert the first buffer's start address to char*. 398 // Bail out if the cast fails. 399 QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy); 400 SVal FirstStart = svalBuilder.evalCast(*firstLoc, CharPtrTy, First->getType()); 401 Loc *FirstStartLoc = dyn_cast<Loc>(&FirstStart); 402 if (!FirstStartLoc) 403 return state; 404 405 // Compute the end of the first buffer. Bail out if THAT fails. 406 SVal FirstEnd = svalBuilder.evalBinOpLN(state, BO_Add, 407 *FirstStartLoc, *Length, CharPtrTy); 408 Loc *FirstEndLoc = dyn_cast<Loc>(&FirstEnd); 409 if (!FirstEndLoc) 410 return state; 411 412 // Is the end of the first buffer past the start of the second buffer? 413 SVal Overlap = svalBuilder.evalBinOpLL(state, BO_GT, 414 *FirstEndLoc, *secondLoc, cmpTy); 415 DefinedOrUnknownSVal *OverlapTest = dyn_cast<DefinedOrUnknownSVal>(&Overlap); 416 if (!OverlapTest) 417 return state; 418 419 llvm::tie(stateTrue, stateFalse) = state->assume(*OverlapTest); 420 421 if (stateTrue && !stateFalse) { 422 // Overlap! 423 emitOverlapBug(C, stateTrue, First, Second); 424 return NULL; 425 } 426 427 // assume the two expressions don't overlap. 428 assert(stateFalse); 429 return stateFalse; 430} 431 432void CStringChecker::emitOverlapBug(CheckerContext &C, const GRState *state, 433 const Stmt *First, const Stmt *Second) const { 434 ExplodedNode *N = C.generateSink(state); 435 if (!N) 436 return; 437 438 if (!BT_Overlap) 439 BT_Overlap.reset(new BugType("Unix API", "Improper arguments")); 440 441 // Generate a report for this bug. 442 RangedBugReport *report = 443 new RangedBugReport(*BT_Overlap, 444 "Arguments must not be overlapping buffers", N); 445 report->addRange(First->getSourceRange()); 446 report->addRange(Second->getSourceRange()); 447 448 C.EmitReport(report); 449} 450 451const GRState *CStringChecker::setCStringLength(const GRState *state, 452 const MemRegion *MR, 453 SVal strLength) { 454 assert(!strLength.isUndef() && "Attempt to set an undefined string length"); 455 if (strLength.isUnknown()) 456 return state; 457 458 MR = MR->StripCasts(); 459 460 switch (MR->getKind()) { 461 case MemRegion::StringRegionKind: 462 // FIXME: This can happen if we strcpy() into a string region. This is 463 // undefined [C99 6.4.5p6], but we should still warn about it. 464 return state; 465 466 case MemRegion::SymbolicRegionKind: 467 case MemRegion::AllocaRegionKind: 468 case MemRegion::VarRegionKind: 469 case MemRegion::FieldRegionKind: 470 case MemRegion::ObjCIvarRegionKind: 471 return state->set<CStringLength>(MR, strLength); 472 473 case MemRegion::ElementRegionKind: 474 // FIXME: Handle element regions by upper-bounding the parent region's 475 // string length. 476 return state; 477 478 default: 479 // Other regions (mostly non-data) can't have a reliable C string length. 480 // For now, just ignore the change. 481 // FIXME: These are rare but not impossible. We should output some kind of 482 // warning for things like strcpy((char[]){'a', 0}, "b"); 483 return state; 484 } 485} 486 487SVal CStringChecker::getCStringLengthForRegion(CheckerContext &C, 488 const GRState *&state, 489 const Expr *Ex, 490 const MemRegion *MR) { 491 // If there's a recorded length, go ahead and return it. 492 const SVal *Recorded = state->get<CStringLength>(MR); 493 if (Recorded) 494 return *Recorded; 495 496 // Otherwise, get a new symbol and update the state. 497 unsigned Count = C.getNodeBuilder().getCurrentBlockCount(); 498 SValBuilder &svalBuilder = C.getSValBuilder(); 499 QualType sizeTy = svalBuilder.getContext().getSizeType(); 500 SVal strLength = svalBuilder.getMetadataSymbolVal(CStringChecker::getTag(), 501 MR, Ex, sizeTy, Count); 502 state = state->set<CStringLength>(MR, strLength); 503 return strLength; 504} 505 506SVal CStringChecker::getCStringLength(CheckerContext &C, const GRState *&state, 507 const Expr *Ex, SVal Buf) const { 508 const MemRegion *MR = Buf.getAsRegion(); 509 if (!MR) { 510 // If we can't get a region, see if it's something we /know/ isn't a 511 // C string. In the context of locations, the only time we can issue such 512 // a warning is for labels. 513 if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&Buf)) { 514 if (ExplodedNode *N = C.generateNode(state)) { 515 if (!BT_NotCString) 516 BT_NotCString.reset(new BuiltinBug("API", 517 "Argument is not a null-terminated string.")); 518 519 llvm::SmallString<120> buf; 520 llvm::raw_svector_ostream os(buf); 521 os << "Argument to byte string function is the address of the label '" 522 << Label->getLabel()->getName() 523 << "', which is not a null-terminated string"; 524 525 // Generate a report for this bug. 526 EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString, 527 os.str(), N); 528 529 report->addRange(Ex->getSourceRange()); 530 C.EmitReport(report); 531 } 532 533 return UndefinedVal(); 534 } 535 536 // If it's not a region and not a label, give up. 537 return UnknownVal(); 538 } 539 540 // If we have a region, strip casts from it and see if we can figure out 541 // its length. For anything we can't figure out, just return UnknownVal. 542 MR = MR->StripCasts(); 543 544 switch (MR->getKind()) { 545 case MemRegion::StringRegionKind: { 546 // Modifying the contents of string regions is undefined [C99 6.4.5p6], 547 // so we can assume that the byte length is the correct C string length. 548 SValBuilder &svalBuilder = C.getSValBuilder(); 549 QualType sizeTy = svalBuilder.getContext().getSizeType(); 550 const StringLiteral *strLit = cast<StringRegion>(MR)->getStringLiteral(); 551 return svalBuilder.makeIntVal(strLit->getByteLength(), sizeTy); 552 } 553 case MemRegion::SymbolicRegionKind: 554 case MemRegion::AllocaRegionKind: 555 case MemRegion::VarRegionKind: 556 case MemRegion::FieldRegionKind: 557 case MemRegion::ObjCIvarRegionKind: 558 return getCStringLengthForRegion(C, state, Ex, MR); 559 case MemRegion::CompoundLiteralRegionKind: 560 // FIXME: Can we track this? Is it necessary? 561 return UnknownVal(); 562 case MemRegion::ElementRegionKind: 563 // FIXME: How can we handle this? It's not good enough to subtract the 564 // offset from the base string length; consider "123\x00567" and &a[5]. 565 return UnknownVal(); 566 default: 567 // Other regions (mostly non-data) can't have a reliable C string length. 568 // In this case, an error is emitted and UndefinedVal is returned. 569 // The caller should always be prepared to handle this case. 570 if (ExplodedNode *N = C.generateNode(state)) { 571 if (!BT_NotCString) 572 BT_NotCString.reset(new BuiltinBug("API", 573 "Argument is not a null-terminated string.")); 574 575 llvm::SmallString<120> buf; 576 llvm::raw_svector_ostream os(buf); 577 578 os << "Argument to byte string function is "; 579 580 if (SummarizeRegion(os, C.getASTContext(), MR)) 581 os << ", which is not a null-terminated string"; 582 else 583 os << "not a null-terminated string"; 584 585 // Generate a report for this bug. 586 EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString, 587 os.str(), N); 588 589 report->addRange(Ex->getSourceRange()); 590 C.EmitReport(report); 591 } 592 593 return UndefinedVal(); 594 } 595} 596 597const StringLiteral *CStringChecker::getCStringLiteral(CheckerContext &C, 598 const GRState *&state, const Expr *expr, SVal val) const { 599 600 // Get the memory region pointed to by the val. 601 const MemRegion *bufRegion = val.getAsRegion(); 602 if (!bufRegion) 603 return NULL; 604 605 // Strip casts off the memory region. 606 bufRegion = bufRegion->StripCasts(); 607 608 // Cast the memory region to a string region. 609 const StringRegion *strRegion= dyn_cast<StringRegion>(bufRegion); 610 if (!strRegion) 611 return NULL; 612 613 // Return the actual string in the string region. 614 return strRegion->getStringLiteral(); 615} 616 617const GRState *CStringChecker::InvalidateBuffer(CheckerContext &C, 618 const GRState *state, 619 const Expr *E, SVal V) { 620 Loc *L = dyn_cast<Loc>(&V); 621 if (!L) 622 return state; 623 624 // FIXME: This is a simplified version of what's in CFRefCount.cpp -- it makes 625 // some assumptions about the value that CFRefCount can't. Even so, it should 626 // probably be refactored. 627 if (loc::MemRegionVal* MR = dyn_cast<loc::MemRegionVal>(L)) { 628 const MemRegion *R = MR->getRegion()->StripCasts(); 629 630 // Are we dealing with an ElementRegion? If so, we should be invalidating 631 // the super-region. 632 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 633 R = ER->getSuperRegion(); 634 // FIXME: What about layers of ElementRegions? 635 } 636 637 // Invalidate this region. 638 unsigned Count = C.getNodeBuilder().getCurrentBlockCount(); 639 return state->invalidateRegion(R, E, Count, NULL); 640 } 641 642 // If we have a non-region value by chance, just remove the binding. 643 // FIXME: is this necessary or correct? This handles the non-Region 644 // cases. Is it ever valid to store to these? 645 return state->unbindLoc(*L); 646} 647 648bool CStringChecker::SummarizeRegion(llvm::raw_ostream& os, ASTContext& Ctx, 649 const MemRegion *MR) { 650 const TypedRegion *TR = dyn_cast<TypedRegion>(MR); 651 if (!TR) 652 return false; 653 654 switch (TR->getKind()) { 655 case MemRegion::FunctionTextRegionKind: { 656 const FunctionDecl *FD = cast<FunctionTextRegion>(TR)->getDecl(); 657 if (FD) 658 os << "the address of the function '" << FD << "'"; 659 else 660 os << "the address of a function"; 661 return true; 662 } 663 case MemRegion::BlockTextRegionKind: 664 os << "block text"; 665 return true; 666 case MemRegion::BlockDataRegionKind: 667 os << "a block"; 668 return true; 669 case MemRegion::CXXThisRegionKind: 670 case MemRegion::CXXTempObjectRegionKind: 671 os << "a C++ temp object of type " << TR->getValueType().getAsString(); 672 return true; 673 case MemRegion::VarRegionKind: 674 os << "a variable of type" << TR->getValueType().getAsString(); 675 return true; 676 case MemRegion::FieldRegionKind: 677 os << "a field of type " << TR->getValueType().getAsString(); 678 return true; 679 case MemRegion::ObjCIvarRegionKind: 680 os << "an instance variable of type " << TR->getValueType().getAsString(); 681 return true; 682 default: 683 return false; 684 } 685} 686 687//===----------------------------------------------------------------------===// 688// evaluation of individual function calls. 689//===----------------------------------------------------------------------===// 690 691void CStringChecker::evalCopyCommon(CheckerContext &C, 692 const CallExpr *CE, 693 const GRState *state, 694 const Expr *Size, const Expr *Dest, 695 const Expr *Source, bool Restricted, 696 bool IsMempcpy) const { 697 // See if the size argument is zero. 698 SVal sizeVal = state->getSVal(Size); 699 QualType sizeTy = Size->getType(); 700 701 const GRState *stateZeroSize, *stateNonZeroSize; 702 llvm::tie(stateZeroSize, stateNonZeroSize) = assumeZero(C, state, sizeVal, sizeTy); 703 704 // Get the value of the Dest. 705 SVal destVal = state->getSVal(Dest); 706 707 // If the size is zero, there won't be any actual memory access, so 708 // just bind the return value to the destination buffer and return. 709 if (stateZeroSize) { 710 C.addTransition(stateZeroSize); 711 if (IsMempcpy) 712 state->BindExpr(CE, destVal); 713 else 714 state->BindExpr(CE, sizeVal); 715 return; 716 } 717 718 // If the size can be nonzero, we have to check the other arguments. 719 if (stateNonZeroSize) { 720 721 // Ensure the destination is not null. If it is NULL there will be a 722 // NULL pointer dereference. 723 state = checkNonNull(C, state, Dest, destVal); 724 if (!state) 725 return; 726 727 // Get the value of the Src. 728 SVal srcVal = state->getSVal(Source); 729 730 // Ensure the source is not null. If it is NULL there will be a 731 // NULL pointer dereference. 732 state = checkNonNull(C, state, Source, srcVal); 733 if (!state) 734 return; 735 736 // Ensure the buffers do not overlap. 737 state = stateNonZeroSize; 738 state = CheckBufferAccess(C, state, Size, Dest, Source, 739 /* FirstIsDst = */ true); 740 if (Restricted) 741 state = CheckOverlap(C, state, Size, Dest, Source); 742 743 if (state) { 744 745 // If this is mempcpy, get the byte after the last byte copied and 746 // bind the expr. 747 if (IsMempcpy) { 748 loc::MemRegionVal *destRegVal = dyn_cast<loc::MemRegionVal>(&destVal); 749 750 // Get the length to copy. 751 SVal lenVal = state->getSVal(Size); 752 NonLoc *lenValNonLoc = dyn_cast<NonLoc>(&lenVal); 753 754 // Get the byte after the last byte copied. 755 SVal lastElement = C.getSValBuilder().evalBinOpLN(state, BO_Add, 756 *destRegVal, 757 *lenValNonLoc, 758 Dest->getType()); 759 760 // The byte after the last byte copied is the return value. 761 state = state->BindExpr(CE, lastElement); 762 } 763 764 // Invalidate the destination. 765 // FIXME: Even if we can't perfectly model the copy, we should see if we 766 // can use LazyCompoundVals to copy the source values into the destination. 767 // This would probably remove any existing bindings past the end of the 768 // copied region, but that's still an improvement over blank invalidation. 769 state = InvalidateBuffer(C, state, Dest, state->getSVal(Dest)); 770 C.addTransition(state); 771 } 772 } 773} 774 775 776void CStringChecker::evalMemcpy(CheckerContext &C, const CallExpr *CE) const { 777 // void *memcpy(void *restrict dst, const void *restrict src, size_t n); 778 // The return value is the address of the destination buffer. 779 const Expr *Dest = CE->getArg(0); 780 const GRState *state = C.getState(); 781 state = state->BindExpr(CE, state->getSVal(Dest)); 782 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true); 783} 784 785void CStringChecker::evalMempcpy(CheckerContext &C, const CallExpr *CE) const { 786 // void *mempcpy(void *restrict dst, const void *restrict src, size_t n); 787 // The return value is a pointer to the byte following the last written byte. 788 const Expr *Dest = CE->getArg(0); 789 const GRState *state = C.getState(); 790 791 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true, true); 792} 793 794void CStringChecker::evalMemmove(CheckerContext &C, const CallExpr *CE) const { 795 // void *memmove(void *dst, const void *src, size_t n); 796 // The return value is the address of the destination buffer. 797 const Expr *Dest = CE->getArg(0); 798 const GRState *state = C.getState(); 799 state = state->BindExpr(CE, state->getSVal(Dest)); 800 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1)); 801} 802 803void CStringChecker::evalBcopy(CheckerContext &C, const CallExpr *CE) const { 804 // void bcopy(const void *src, void *dst, size_t n); 805 evalCopyCommon(C, CE, C.getState(), 806 CE->getArg(2), CE->getArg(1), CE->getArg(0)); 807} 808 809void CStringChecker::evalMemcmp(CheckerContext &C, const CallExpr *CE) const { 810 // int memcmp(const void *s1, const void *s2, size_t n); 811 const Expr *Left = CE->getArg(0); 812 const Expr *Right = CE->getArg(1); 813 const Expr *Size = CE->getArg(2); 814 815 const GRState *state = C.getState(); 816 SValBuilder &svalBuilder = C.getSValBuilder(); 817 818 // See if the size argument is zero. 819 SVal sizeVal = state->getSVal(Size); 820 QualType sizeTy = Size->getType(); 821 822 const GRState *stateZeroSize, *stateNonZeroSize; 823 llvm::tie(stateZeroSize, stateNonZeroSize) = 824 assumeZero(C, state, sizeVal, sizeTy); 825 826 // If the size can be zero, the result will be 0 in that case, and we don't 827 // have to check either of the buffers. 828 if (stateZeroSize) { 829 state = stateZeroSize; 830 state = state->BindExpr(CE, svalBuilder.makeZeroVal(CE->getType())); 831 C.addTransition(state); 832 } 833 834 // If the size can be nonzero, we have to check the other arguments. 835 if (stateNonZeroSize) { 836 state = stateNonZeroSize; 837 // If we know the two buffers are the same, we know the result is 0. 838 // First, get the two buffers' addresses. Another checker will have already 839 // made sure they're not undefined. 840 DefinedOrUnknownSVal LV = cast<DefinedOrUnknownSVal>(state->getSVal(Left)); 841 DefinedOrUnknownSVal RV = cast<DefinedOrUnknownSVal>(state->getSVal(Right)); 842 843 // See if they are the same. 844 DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV); 845 const GRState *StSameBuf, *StNotSameBuf; 846 llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf); 847 848 // If the two arguments might be the same buffer, we know the result is zero, 849 // and we only need to check one size. 850 if (StSameBuf) { 851 state = StSameBuf; 852 state = CheckBufferAccess(C, state, Size, Left); 853 if (state) { 854 state = StSameBuf->BindExpr(CE, svalBuilder.makeZeroVal(CE->getType())); 855 C.addTransition(state); 856 } 857 } 858 859 // If the two arguments might be different buffers, we have to check the 860 // size of both of them. 861 if (StNotSameBuf) { 862 state = StNotSameBuf; 863 state = CheckBufferAccess(C, state, Size, Left, Right); 864 if (state) { 865 // The return value is the comparison result, which we don't know. 866 unsigned Count = C.getNodeBuilder().getCurrentBlockCount(); 867 SVal CmpV = svalBuilder.getConjuredSymbolVal(NULL, CE, Count); 868 state = state->BindExpr(CE, CmpV); 869 C.addTransition(state); 870 } 871 } 872 } 873} 874 875void CStringChecker::evalstrLength(CheckerContext &C, 876 const CallExpr *CE) const { 877 // size_t strlen(const char *s); 878 evalstrLengthCommon(C, CE, /* IsStrnlen = */ false); 879} 880 881void CStringChecker::evalstrnLength(CheckerContext &C, 882 const CallExpr *CE) const { 883 // size_t strnlen(const char *s, size_t maxlen); 884 evalstrLengthCommon(C, CE, /* IsStrnlen = */ true); 885} 886 887void CStringChecker::evalstrLengthCommon(CheckerContext &C, const CallExpr *CE, 888 bool IsStrnlen) const { 889 const GRState *state = C.getState(); 890 const Expr *Arg = CE->getArg(0); 891 SVal ArgVal = state->getSVal(Arg); 892 893 // Check that the argument is non-null. 894 state = checkNonNull(C, state, Arg, ArgVal); 895 896 if (state) { 897 SVal strLength = getCStringLength(C, state, Arg, ArgVal); 898 899 // If the argument isn't a valid C string, there's no valid state to 900 // transition to. 901 if (strLength.isUndef()) 902 return; 903 904 // If the check is for strnlen() then bind the return value to no more than 905 // the maxlen value. 906 if (IsStrnlen) { 907 const Expr *maxlenExpr = CE->getArg(1); 908 SVal maxlenVal = state->getSVal(maxlenExpr); 909 910 NonLoc *strLengthNL = dyn_cast<NonLoc>(&strLength); 911 NonLoc *maxlenValNL = dyn_cast<NonLoc>(&maxlenVal); 912 913 QualType cmpTy = C.getSValBuilder().getContext().IntTy; 914 const GRState *stateTrue, *stateFalse; 915 916 // Check if the strLength is greater than or equal to the maxlen 917 llvm::tie(stateTrue, stateFalse) = 918 state->assume(cast<DefinedOrUnknownSVal> 919 (C.getSValBuilder().evalBinOpNN(state, BO_GE, 920 *strLengthNL, *maxlenValNL, 921 cmpTy))); 922 923 // If the strLength is greater than or equal to the maxlen, set strLength 924 // to maxlen 925 if (stateTrue && !stateFalse) { 926 strLength = maxlenVal; 927 } 928 } 929 930 // If getCStringLength couldn't figure out the length, conjure a return 931 // value, so it can be used in constraints, at least. 932 if (strLength.isUnknown()) { 933 unsigned Count = C.getNodeBuilder().getCurrentBlockCount(); 934 strLength = C.getSValBuilder().getConjuredSymbolVal(NULL, CE, Count); 935 } 936 937 // Bind the return value. 938 state = state->BindExpr(CE, strLength); 939 C.addTransition(state); 940 } 941} 942 943void CStringChecker::evalStrcpy(CheckerContext &C, const CallExpr *CE) const { 944 // char *strcpy(char *restrict dst, const char *restrict src); 945 evalStrcpyCommon(C, CE, 946 /* returnEnd = */ false, 947 /* isBounded = */ false, 948 /* isAppending = */ false); 949} 950 951void CStringChecker::evalStrncpy(CheckerContext &C, const CallExpr *CE) const { 952 // char *strcpy(char *restrict dst, const char *restrict src); 953 evalStrcpyCommon(C, CE, 954 /* returnEnd = */ false, 955 /* isBounded = */ true, 956 /* isAppending = */ false); 957} 958 959void CStringChecker::evalStpcpy(CheckerContext &C, const CallExpr *CE) const { 960 // char *stpcpy(char *restrict dst, const char *restrict src); 961 evalStrcpyCommon(C, CE, 962 /* returnEnd = */ true, 963 /* isBounded = */ false, 964 /* isAppending = */ false); 965} 966 967void CStringChecker::evalStrcat(CheckerContext &C, const CallExpr *CE) const { 968 //char *strcat(char *restrict s1, const char *restrict s2); 969 evalStrcpyCommon(C, CE, 970 /* returnEnd = */ false, 971 /* isBounded = */ false, 972 /* isAppending = */ true); 973} 974 975void CStringChecker::evalStrncat(CheckerContext &C, const CallExpr *CE) const { 976 //char *strncat(char *restrict s1, const char *restrict s2, size_t n); 977 evalStrcpyCommon(C, CE, 978 /* returnEnd = */ false, 979 /* isBounded = */ true, 980 /* isAppending = */ true); 981} 982 983void CStringChecker::evalStrcpyCommon(CheckerContext &C, const CallExpr *CE, 984 bool returnEnd, bool isBounded, 985 bool isAppending) const { 986 const GRState *state = C.getState(); 987 988 // Check that the destination is non-null. 989 const Expr *Dst = CE->getArg(0); 990 SVal DstVal = state->getSVal(Dst); 991 992 state = checkNonNull(C, state, Dst, DstVal); 993 if (!state) 994 return; 995 996 // Check that the source is non-null. 997 const Expr *srcExpr = CE->getArg(1); 998 SVal srcVal = state->getSVal(srcExpr); 999 state = checkNonNull(C, state, srcExpr, srcVal); 1000 if (!state) 1001 return; 1002 1003 // Get the string length of the source. 1004 SVal strLength = getCStringLength(C, state, srcExpr, srcVal); 1005 1006 // If the source isn't a valid C string, give up. 1007 if (strLength.isUndef()) 1008 return; 1009 1010 // If the function is strncpy, strncat, etc... it is bounded. 1011 if (isBounded) { 1012 // Get the max number of characters to copy. 1013 const Expr *lenExpr = CE->getArg(2); 1014 SVal lenVal = state->getSVal(lenExpr); 1015 1016 NonLoc *strLengthNL = dyn_cast<NonLoc>(&strLength); 1017 NonLoc *lenValNL = dyn_cast<NonLoc>(&lenVal); 1018 1019 QualType cmpTy = C.getSValBuilder().getContext().IntTy; 1020 const GRState *stateTrue, *stateFalse; 1021 1022 // Check if the max number to copy is less than the length of the src. 1023 llvm::tie(stateTrue, stateFalse) = 1024 state->assume(cast<DefinedOrUnknownSVal> 1025 (C.getSValBuilder().evalBinOpNN(state, BO_GT, 1026 *strLengthNL, *lenValNL, 1027 cmpTy))); 1028 1029 if (stateTrue) { 1030 // Max number to copy is less than the length of the src, so the actual 1031 // strLength copied is the max number arg. 1032 strLength = lenVal; 1033 } 1034 } 1035 1036 // If this is an appending function (strcat, strncat...) then set the 1037 // string length to strlen(src) + strlen(dst) since the buffer will 1038 // ultimately contain both. 1039 if (isAppending) { 1040 // Get the string length of the destination, or give up. 1041 SVal dstStrLength = getCStringLength(C, state, Dst, DstVal); 1042 if (dstStrLength.isUndef()) 1043 return; 1044 1045 NonLoc *srcStrLengthNL = dyn_cast<NonLoc>(&strLength); 1046 NonLoc *dstStrLengthNL = dyn_cast<NonLoc>(&dstStrLength); 1047 1048 // If src or dst cast to NonLoc is NULL, give up. 1049 if ((!srcStrLengthNL) || (!dstStrLengthNL)) 1050 return; 1051 1052 QualType addTy = C.getSValBuilder().getContext().getSizeType(); 1053 1054 strLength = C.getSValBuilder().evalBinOpNN(state, BO_Add, 1055 *srcStrLengthNL, *dstStrLengthNL, 1056 addTy); 1057 } 1058 1059 SVal Result = (returnEnd ? UnknownVal() : DstVal); 1060 1061 // If the destination is a MemRegion, try to check for a buffer overflow and 1062 // record the new string length. 1063 if (loc::MemRegionVal *dstRegVal = dyn_cast<loc::MemRegionVal>(&DstVal)) { 1064 // If the length is known, we can check for an overflow. 1065 if (NonLoc *knownStrLength = dyn_cast<NonLoc>(&strLength)) { 1066 SVal lastElement = 1067 C.getSValBuilder().evalBinOpLN(state, BO_Add, *dstRegVal, 1068 *knownStrLength, Dst->getType()); 1069 1070 state = CheckLocation(C, state, Dst, lastElement, /* IsDst = */ true); 1071 if (!state) 1072 return; 1073 1074 // If this is a stpcpy-style copy, the last element is the return value. 1075 if (returnEnd) 1076 Result = lastElement; 1077 } 1078 1079 // Invalidate the destination. This must happen before we set the C string 1080 // length because invalidation will clear the length. 1081 // FIXME: Even if we can't perfectly model the copy, we should see if we 1082 // can use LazyCompoundVals to copy the source values into the destination. 1083 // This would probably remove any existing bindings past the end of the 1084 // string, but that's still an improvement over blank invalidation. 1085 state = InvalidateBuffer(C, state, Dst, *dstRegVal); 1086 1087 // Set the C string length of the destination. 1088 state = setCStringLength(state, dstRegVal->getRegion(), strLength); 1089 } 1090 1091 // If this is a stpcpy-style copy, but we were unable to check for a buffer 1092 // overflow, we still need a result. Conjure a return value. 1093 if (returnEnd && Result.isUnknown()) { 1094 SValBuilder &svalBuilder = C.getSValBuilder(); 1095 unsigned Count = C.getNodeBuilder().getCurrentBlockCount(); 1096 strLength = svalBuilder.getConjuredSymbolVal(NULL, CE, Count); 1097 } 1098 1099 // Set the return value. 1100 state = state->BindExpr(CE, Result); 1101 C.addTransition(state); 1102} 1103 1104void CStringChecker::evalStrcmp(CheckerContext &C, const CallExpr *CE) const { 1105 //int strcmp(const char *restrict s1, const char *restrict s2); 1106 1107 const GRState *state = C.getState(); 1108 1109 // Check that the first string is non-null 1110 const Expr *s1 = CE->getArg(0); 1111 SVal s1Val = state->getSVal(s1); 1112 state = checkNonNull(C, state, s1, s1Val); 1113 if (!state) 1114 return; 1115 1116 // Check that the second string is non-null. 1117 const Expr *s2 = CE->getArg(1); 1118 SVal s2Val = state->getSVal(s2); 1119 state = checkNonNull(C, state, s2, s2Val); 1120 if (!state) 1121 return; 1122 1123 // Get the string length of the first string or give up. 1124 SVal s1Length = getCStringLength(C, state, s1, s1Val); 1125 if (s1Length.isUndef()) 1126 return; 1127 1128 // Get the string length of the second string or give up. 1129 SVal s2Length = getCStringLength(C, state, s2, s2Val); 1130 if (s2Length.isUndef()) 1131 return; 1132 1133 // Get the string literal of the first string. 1134 const StringLiteral *s1StrLiteral = getCStringLiteral(C, state, s1, s1Val); 1135 if (!s1StrLiteral) 1136 return; 1137 llvm::StringRef s1StrRef = s1StrLiteral->getString(); 1138 1139 // Get the string literal of the second string. 1140 const StringLiteral *s2StrLiteral = getCStringLiteral(C, state, s2, s2Val); 1141 if (!s2StrLiteral) 1142 return; 1143 llvm::StringRef s2StrRef = s2StrLiteral->getString(); 1144 1145 // Compare string 1 to string 2 the same way strcmp() does. 1146 int result = s1StrRef.compare(s2StrRef); 1147 1148 // Build the SVal of the comparison to bind the return value. 1149 SValBuilder &svalBuilder = C.getSValBuilder(); 1150 QualType intTy = svalBuilder.getContext().IntTy; 1151 SVal resultVal = svalBuilder.makeIntVal(result, intTy); 1152 1153 // Bind the return value of the expression. 1154 // Set the return value. 1155 state = state->BindExpr(CE, resultVal); 1156 C.addTransition(state); 1157} 1158 1159//===----------------------------------------------------------------------===// 1160// The driver method, and other Checker callbacks. 1161//===----------------------------------------------------------------------===// 1162 1163bool CStringChecker::evalCall(const CallExpr *CE, CheckerContext &C) const { 1164 // Get the callee. All the functions we care about are C functions 1165 // with simple identifiers. 1166 const GRState *state = C.getState(); 1167 const Expr *Callee = CE->getCallee(); 1168 const FunctionDecl *FD = state->getSVal(Callee).getAsFunctionDecl(); 1169 1170 if (!FD) 1171 return false; 1172 1173 // Get the name of the callee. If it's a builtin, strip off the prefix. 1174 IdentifierInfo *II = FD->getIdentifier(); 1175 if (!II) // if no identifier, not a simple C function 1176 return false; 1177 llvm::StringRef Name = II->getName(); 1178 if (Name.startswith("__builtin_")) 1179 Name = Name.substr(10); 1180 1181 FnCheck evalFunction = llvm::StringSwitch<FnCheck>(Name) 1182 .Cases("memcpy", "__memcpy_chk", &CStringChecker::evalMemcpy) 1183 .Case("mempcpy", &CStringChecker::evalMempcpy) 1184 .Cases("memcmp", "bcmp", &CStringChecker::evalMemcmp) 1185 .Cases("memmove", "__memmove_chk", &CStringChecker::evalMemmove) 1186 .Cases("strcpy", "__strcpy_chk", &CStringChecker::evalStrcpy) 1187 .Cases("strncpy", "__strncpy_chk", &CStringChecker::evalStrncpy) 1188 .Cases("stpcpy", "__stpcpy_chk", &CStringChecker::evalStpcpy) 1189 .Cases("strcat", "__strcat_chk", &CStringChecker::evalStrcat) 1190 .Cases("strncat", "__strncat_chk", &CStringChecker::evalStrncat) 1191 .Case("strlen", &CStringChecker::evalstrLength) 1192 .Case("strnlen", &CStringChecker::evalstrnLength) 1193 .Case("strcmp", &CStringChecker::evalStrcmp) 1194 .Case("bcopy", &CStringChecker::evalBcopy) 1195 .Default(NULL); 1196 1197 // If the callee isn't a string function, let another checker handle it. 1198 if (!evalFunction) 1199 return false; 1200 1201 // Check and evaluate the call. 1202 (this->*evalFunction)(C, CE); 1203 return true; 1204} 1205 1206void CStringChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const { 1207 // Record string length for char a[] = "abc"; 1208 const GRState *state = C.getState(); 1209 1210 for (DeclStmt::const_decl_iterator I = DS->decl_begin(), E = DS->decl_end(); 1211 I != E; ++I) { 1212 const VarDecl *D = dyn_cast<VarDecl>(*I); 1213 if (!D) 1214 continue; 1215 1216 // FIXME: Handle array fields of structs. 1217 if (!D->getType()->isArrayType()) 1218 continue; 1219 1220 const Expr *Init = D->getInit(); 1221 if (!Init) 1222 continue; 1223 if (!isa<StringLiteral>(Init)) 1224 continue; 1225 1226 Loc VarLoc = state->getLValue(D, C.getPredecessor()->getLocationContext()); 1227 const MemRegion *MR = VarLoc.getAsRegion(); 1228 if (!MR) 1229 continue; 1230 1231 SVal StrVal = state->getSVal(Init); 1232 assert(StrVal.isValid() && "Initializer string is unknown or undefined"); 1233 DefinedOrUnknownSVal strLength 1234 = cast<DefinedOrUnknownSVal>(getCStringLength(C, state, Init, StrVal)); 1235 1236 state = state->set<CStringLength>(MR, strLength); 1237 } 1238 1239 C.addTransition(state); 1240} 1241 1242bool CStringChecker::wantsRegionChangeUpdate(const GRState *state) const { 1243 CStringLength::EntryMap Entries = state->get<CStringLength>(); 1244 return !Entries.isEmpty(); 1245} 1246 1247const GRState * 1248CStringChecker::checkRegionChanges(const GRState *state, 1249 const MemRegion * const *Begin, 1250 const MemRegion * const *End) const { 1251 CStringLength::EntryMap Entries = state->get<CStringLength>(); 1252 if (Entries.isEmpty()) 1253 return state; 1254 1255 llvm::SmallPtrSet<const MemRegion *, 8> Invalidated; 1256 llvm::SmallPtrSet<const MemRegion *, 32> SuperRegions; 1257 1258 // First build sets for the changed regions and their super-regions. 1259 for ( ; Begin != End; ++Begin) { 1260 const MemRegion *MR = *Begin; 1261 Invalidated.insert(MR); 1262 1263 SuperRegions.insert(MR); 1264 while (const SubRegion *SR = dyn_cast<SubRegion>(MR)) { 1265 MR = SR->getSuperRegion(); 1266 SuperRegions.insert(MR); 1267 } 1268 } 1269 1270 CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>(); 1271 1272 // Then loop over the entries in the current state. 1273 for (CStringLength::EntryMap::iterator I = Entries.begin(), 1274 E = Entries.end(); I != E; ++I) { 1275 const MemRegion *MR = I.getKey(); 1276 1277 // Is this entry for a super-region of a changed region? 1278 if (SuperRegions.count(MR)) { 1279 Entries = F.remove(Entries, MR); 1280 continue; 1281 } 1282 1283 // Is this entry for a sub-region of a changed region? 1284 const MemRegion *Super = MR; 1285 while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) { 1286 Super = SR->getSuperRegion(); 1287 if (Invalidated.count(Super)) { 1288 Entries = F.remove(Entries, MR); 1289 break; 1290 } 1291 } 1292 } 1293 1294 return state->set<CStringLength>(Entries); 1295} 1296 1297void CStringChecker::checkLiveSymbols(const GRState *state, 1298 SymbolReaper &SR) const { 1299 // Mark all symbols in our string length map as valid. 1300 CStringLength::EntryMap Entries = state->get<CStringLength>(); 1301 1302 for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end(); 1303 I != E; ++I) { 1304 SVal Len = I.getData(); 1305 if (SymbolRef Sym = Len.getAsSymbol()) 1306 SR.markInUse(Sym); 1307 } 1308} 1309 1310void CStringChecker::checkDeadSymbols(SymbolReaper &SR, 1311 CheckerContext &C) const { 1312 if (!SR.hasDeadSymbols()) 1313 return; 1314 1315 const GRState *state = C.getState(); 1316 CStringLength::EntryMap Entries = state->get<CStringLength>(); 1317 if (Entries.isEmpty()) 1318 return; 1319 1320 CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>(); 1321 for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end(); 1322 I != E; ++I) { 1323 SVal Len = I.getData(); 1324 if (SymbolRef Sym = Len.getAsSymbol()) { 1325 if (SR.isDead(Sym)) 1326 Entries = F.remove(Entries, I.getKey()); 1327 } 1328 } 1329 1330 state = state->set<CStringLength>(Entries); 1331 C.generateNode(state); 1332} 1333 1334void ento::registerCStringChecker(CheckerManager &mgr) { 1335 mgr.registerChecker<CStringChecker>(); 1336} 1337