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