[analyzer] Improve the modeling of `memset()`.

[MTC]

Summary

This patch originates from https://reviews.llvm.org/D31868. There are two key points in this patch:

• Add OverwriteRegion(), this method used to model memset() or something like that.
• Improve the modeling of memset.

For OverwriteRegion(), is basically invalidate region and bind default. But I think this
method requires more in-depth thinking and more extensive testing.

For evalMemset(), this patch only considers the case where the buffer's offset is zero. And
if the whole region is memseted, bind a default value. According to the value for overwriting,
decide how to update the string length.

For void *memset(void *dest, int ch, size_t count):

• 1). offset is 0, ch is '\0' and count < dest-buffer's length. Invalidate the buffer and set the string length to 0.
• 2). offset is 0, ch is '\0' and count == dest-buffer's length. Bind \0 to the buffer with default binding and set the string length to 0.
• 3). offset is 0, ch is not '\0' and count < dest-buffer's length. Invalidate the buffer and set the string length >= count.
• 4). offset is 0, ch is not '\0' and count == dest-buffer's length. Bind ch to the buffer and set the string length >= count.

In addition, memset can bind anything to the region, so getBindingForDerivedDefaultValue()'s logic needs some adjustment. The solution in this patch is certainly not correct.

I have tested this patch on sqlite, but there's no difference int the warnings. This patch is very primitive and requires a lot of advice so that it can be perfected.

Thanks in advance for the review!

[NoQ]

Why do you need separate code for null and non-null character? The function's semantics doesn't seem to care.

I'd rather consider the case of non-concrete character separately. Because wiping a region with a symbol is not something we currently support; a symbolic default binding over a region means a different thing and it'd be equivalent to invalidation, so for non-concrete character we don't have a better choice than to invalidate. For concrete non-zero character, on the contrary, a default binding would work just fine.

Could you explain why didn't a straightforward bindLoc over a base region wasn't doing the thing you wanted? I.e., why is new Store API function necessary?

[NoQ]

In addition, memset can bind anything to the region, so getBindingForDerivedDefaultValue()'s logic needs some adjustment. The solution in this patch is certainly not correct.

Yeah, i guess you meant here the thing that i was saying about concrete bindings. If we only limit ourselves to concrete bindings, it should work well.

[MTC]

Thanks for your review, NoQ!

Why do you need separate code for null and non-null character? The function's semantics doesn't seem to care.

Thank you for your advice, I will remove the duplicate code！

I'd rather consider the case of non-concrete character separately. Because wiping a region with a symbol is not something we currently support; a symbolic default binding over a region means a different thing and it'd be equivalent to invalidation, so for non-concrete character we don't have a better choice than to invalidate. For concrete non-zero character, on the contrary, a default binding would work just fine.

Thank you for your reminding, I overlooked this point. However for non-concrete character, the symbol value, if we just invalidate the region, the constraint information of the non-concrete character will be lost. Do we need to consider this?

Could you explain why didn't a straightforward bindLoc over a base region wasn't doing the thing you wanted? I.e., why is new Store API function necessary?

I am also very resistant to adding new APIs. One is that I am not very familiar with RegionStore. One is that adding a new API is always the last option.

• The semantics of memset() need default binding, and only bindDefault() can guarantee that. However bindDefault() is just used to initialize the region and can only be called once on the same region.
• Only when the region is TypedValueRegion and the value type is ArrayType or StructType, bindLoc() can add a default binding. So if we want to continue using default binding, bindLoc() is not the correct choice.

And if I use bindLoc() instead of overwriteRegion(), there will be some crashes occured because bindLoc() broke some assumptions, e.g. bindArray() believes that the value for binding should be CompoundVal, LazyCompoundVal or UnknownVal.

[MTC]

According to @NoQ's suggestion, remove the duplicated code.

[MTC]

Thank you for your reminding, I overlooked this point. However for non-concrete character, the symbol value, if we just invalidate the region, the constraint information of the non-concrete character will be lost. Do we need to consider this?

Sorry for my hasty question, analyzer does not support to bind a symbol with a default binding.

The update of this diff is as follows.

• If the char value is not concrete, just invalidate the region.
• Add a test about symbolic char value.
• A little code refactoring.

[MTC]

Kindly ping!

[MTC]

ping^2

[a.sidorin]

Hi Henry. I had a quick look at the patch, here are some remarks.

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

2092

"So we call"?

2100

I think we can use the argument type here (which is int).
One more question. Could we use SVal::isZeroConstant() here instead? Do we need the path-sensitivity for the value or we can just check if the value is a constant zero?

2103

"argument"

2127

Could you please factor this chunk to a function? It makes the method too big.

lib/StaticAnalyzer/Core/ProgramState.cpp

148

Do clients of overwriteRegion really need to call checkers?

lib/StaticAnalyzer/Core/RegionStore.cpp

446

LLVM naming conventions say that function names should start with small letter.

1718

Could you please explain what is the reason of this change? Do we get new value kinds?

lib/StaticAnalyzer/Core/Store.cpp

72

Could we make this method pure virtual?

[MTC]

Sorry for the long delay, I have just finished my holiday.

Thanks a lot for the review, I will fix the typo in next update.

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

2100

Yea, it's should be int.

SVal::isZeroConstant() is enough here, thanks!

One question that has nothing to do with the patch, I would like to know if there is a standard to determine whether there is a need for state splitting.

2127

will do.

lib/StaticAnalyzer/Core/ProgramState.cpp

148

It is possible that my understanding of the engine is not enough, I think we need to call processRangeChange() for memory change. memset() will overwrite the memory region, so I think there is a need to call this API.

What do you think?

lib/StaticAnalyzer/Core/RegionStore.cpp

1718

memset() can bind anything to the region with default binding, if there is no such change, it will trigger llvm_unreachable().

I don't think much about it, just put return val; here. Any suggestions?

lib/StaticAnalyzer/Core/Store.cpp

72

To be honest, I implemented this function according to BindDefault(). And I also think pure virtual is better, thanks.

[MTC]

• fix typos
• code refactoring, add auxiliary method memsetAux()
• according to a.sidorin's suggestions, remove the useless state splitting.
• make StoreManager::overwriteRegion() pure virtual

[NoQ]

Hmm, ok, it seems that i've just changed the API in D46368, and i should have thought about this use case. Well, at least i have some background understanding of these problems now. Sorry for not keeping eye on this problem.

In D44934#1051002, @NoQ wrote:

Why do you need separate code for null and non-null character? The function's semantics doesn't seem to care.

I guess i can answer myself here:

int32_t x;
memset(&x, 1, sizeof(int32_t));
clang_analyzer_eval(x == 0x1010101); // should be TRUE

I really doubt that we support this case.

So, yeah, zero character is indeed special.

And since zero character is special, i guess we could use the new bindDefaultZero() API, and perform a simple invalidation in the non-zero character case. @MTC, would this be enough for your use case? Or is it really important for you to support the non-zero character case? Cause my example is fairly artificial, and probably i'm worrying too much about it. If nobody really codes that way, i'm fine with supporting the non-zero character case via a simple default binding. In this case we should merge bindDefaultZero() with your overwriteRegion() (i'd prefer your function name, but please keep the empty class check).

lib/StaticAnalyzer/Core/ProgramState.cpp

118

Note: notifyChanges declared here :)

148

Well, we need to make sure we don't notify checkers recursively. In bindLoc() we have the notifyChanges parameter, i guess we need to have something similar here as well, if we really need to notify checkers.

Technically, yeah, we need to notify checkers. Like, if you memset() a string to '\0', string checker needs to know that its length has also become 0. Wait, we already are in the string checker, and we're already doing that. I guess it's not that important at the moment, so i'd rather delay it until we need it, and see if we have shared checker states available earlier and if they help.

Also getOwningEngine() is never null.

[MTC]

In D44934#1088771, @NoQ wrote:

Hmm, ok, it seems that i've just changed the API in D46368, and i should have thought about this use case. Well, at least i have some background understanding of these problems now. Sorry for not keeping eye on this problem.

In D44934#1051002, @NoQ wrote:

Why do you need separate code for null and non-null character? The function's semantics doesn't seem to care.

I guess i can answer myself here:

int32_t x;
memset(&x, 1, sizeof(int32_t));
clang_analyzer_eval(x == 0x1010101); // should be TRUE

I really doubt that we support this case.

So, yeah, zero character is indeed special.

Thank you, Artem! I did not consider this common situation. This patch does not really support this situation, in this patch the value of x will be 1, it's not correct!

And since zero character is special, i guess we could use the new bindDefaultZero() API, and perform a simple invalidation in the non-zero character case.

Agree with you. The core problem here is that there is no perfect way to bind default for non-zero value, not the string length stuff. So invalidate the destination buffer but still set string length for non-zero character is OK. Right?

@MTC, would this be enough for your use case? Or is it really important for you to support the non-zero character case? Cause my example is fairly artificial, and probably i'm worrying too much about it. If nobody really codes that way, i'm fine with supporting the non-zero character case via a simple default binding. In this case we should merge bindDefaultZero() with your overwriteRegion() (i'd prefer your function name, but please keep the empty class check).

Based on my limited programming experience, I think memset with non-zero character is common. However given that we can't handle non-zero character binding problems very well, we should now support only zero character. After all, IMHO, correctness of semantic is also important for the analyzer.

I will update this patch to only handle zero character case. In the future, as I am more familiar with the RegionStore, maybe I can solve the problem of non-zero character binding.

[MTC]

• Since there is no perfect way to handle the default binding of non-zero character, remove the default binding of non-zero character. Use bindDefaulrZero() instead of overwriteRegion() to bind the zero character.
• Reuse assume() instead of isZeroConstant() to determine whether it is zero character. The purpose of this is to be able to set the string length when dealing with non-zero symbol character.

[MTC]

ping.

[NoQ]

Thank you! Looks good overall.

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

1013–1014

Please say something here (or above) about why do we want our offset to be 0:

We're about to model memset by producing a "default binding" in the Store. Our current implementation - RegionStore - doesn't support default bindings that don't cover the whole base region.

1037

I think we should use StateNonNullChar (that's computed below) instead of CharVal.isZeroConstant() because the Environment doesn't provide a guarantee that all symbols within it are collapsed to constants where applicable.

1055

I think this should use IntTy here. Because that's the type of the memset's argument, and that's what assumeZero() expects.

test/Analysis/string.c

1474

Typo: should :)

[MTC]

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

1037

Yea, thanks!

1055

I confirmed again that memset() will convert the value to unsigned char first, see http://en.cppreference.com/w/c/string/byte/memset.

In the next update, I will evalCast(value, UnsignedCharTy, IntTy) first, therefore, I will continue to use UnsignedCharTy.

test/Analysis/string.c

1474

thanks, will do!

[MTC]

• According to NoQ's suggestion, use assumeZero() instead of isZeroConstant() to determine whether the value is 0.
• Add test memset26_upper_UCHAR_MAX() and memset27_symbol()
• Since memset( void *dest, int ch, size_t count) will converts the value ch to unsigned char, we call evalCast() accordingly.

[NoQ]

Thanks! This looks great now.

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

1055

Aha, yup, it does convert to unsigned char, but assumeZero() doesn't. The new code looks correct.

include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h

ProgramStateRef bindLoc(Loc location,
                           SVal V,
                           const LocationContext *LCtx,
                           bool notifyChanges = true) const;
 
   ProgramStateRef bindLoc(SVal location, SVal V, const LocationContext *LCtx) const;
 
   ProgramStateRef bindDefault(SVal loc, SVal V, const LocationContext *LCtx) const;
 
+  // Create a new state by invalidating the given region and binging the new
+  // value with default binding.
+  ProgramStateRef overwriteRegion(SVal Loc, SVal V,
+                                  const LocationContext *LCtx) const;
+
   ProgramStateRef killBinding(Loc LV) const;
 
   /// \brief Returns the state with bindings for the given regions
   ///  cleared from the store.
   ///
   /// Optionally invalidates global regions as well.
   ///
   /// \param Regions the set of regions to be invalidated.

include/clang/StaticAnalyzer/Core/PathSensitive/Store.h

public:
   /// \param[in] val The value to bind to location \c loc.
   /// \return A StoreRef object that contains the same
   ///   bindings as \c store with the addition of having the value specified
   ///   by \c val bound to the location given for \c loc.
   virtual StoreRef Bind(Store store, Loc loc, SVal val) = 0;
 
   virtual StoreRef BindDefault(Store store, const MemRegion *R, SVal V);
 
+  // Clears out the specified region from the store and bind a new value with
+  // default binding.
+  virtual StoreRef OverwriteRegion(Store store, const MemRegion *R, SVal V);
+
   /// \brief Create a new store with the specified binding removed.
   /// \param ST the original store, that is the basis for the new store.
   /// \param L the location whose binding should be removed.
   virtual StoreRef killBinding(Store ST, Loc L) = 0;
 
   /// getInitialStore - Returns the initial "empty" store representing the
   ///  value bindings upon entry to an analyzed function.
   virtual StoreRef getInitialStore(const LocationContext *InitLoc) = 0;

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

 //===----------------------------------------------------------------------===//
 
 void CStringChecker::evalCopyCommon(CheckerContext &C,
                                     const CallExpr *CE,
                                     ProgramStateRef state,
                                     const Expr *Size, const Expr *Dest,
                                     const Expr *Source, bool Restricted,
                                     bool IsMempcpy) const {
   CurrentFunctionDescription = "memory copy function";
 
   // See if the size argument is zero.
   const LocationContext *LCtx = C.getLocationContext();
   SVal sizeVal = state->getSVal(Size, LCtx);
   QualType sizeTy = Size->getType();
 
   ProgramStateRef stateZeroSize, stateNonZeroSize;
   std::tie(stateZeroSize, stateNonZeroSize) =
     assumeZero(C, state, sizeVal, sizeTy);
 
   // Get the value of the Dest.
   SVal destVal = state->getSVal(Dest, LCtx);
 
   // If the size is zero, there won't be any actual memory access, so
   // just bind the return value to the destination buffer and return.
   if (stateZeroSize && !stateNonZeroSize) {
     stateZeroSize = stateZeroSize->BindExpr(CE, LCtx, destVal);
     C.addTransition(stateZeroSize);
     return;
   }
 
   // If the size can be nonzero, we have to check the other arguments.
   if (stateNonZeroSize) {
     state = stateNonZeroSize;
 
     // Ensure the destination is not null. If it is NULL there will be a
     // NULL pointer dereference.
     state = checkNonNull(C, state, Dest, destVal);
     if (!state)
       return;
 
     // Get the value of the Src.
     SVal srcVal = state->getSVal(Source, LCtx);
 
     // Ensure the source is not null. If it is NULL there will be a
     // NULL pointer dereference.
     state = checkNonNull(C, state, Source, srcVal);
     if (!state)
       return;
 
     // Ensure the accesses are valid and that the buffers do not overlap.
     const char * const writeWarning =
       "Memory copy function overflows destination buffer";
     state = CheckBufferAccess(C, state, Size, Dest, Source,
                               writeWarning, /* sourceWarning = */ nullptr);
     if (Restricted)
       state = CheckOverlap(C, state, Size, Dest, Source);
 
     if (!state)
       return;

 
 void CStringChecker::evalMemset(CheckerContext &C, const CallExpr *CE) const {
   if (CE->getNumArgs() != 3)
     return;
 
   CurrentFunctionDescription = "memory set function";
 
   const Expr *Mem = CE->getArg(0);
+  const Expr *CharE = CE->getArg(1);
   const Expr *Size = CE->getArg(2);
+
   ProgramStateRef State = C.getState();
+  SValBuilder &svalBuilder = C.getSValBuilder();
+  ASTContext &Ctx = C.getASTContext();
+  QualType CmpType = svalBuilder.getConditionType();
 
   // See if the size argument is zero.
   const LocationContext *LCtx = C.getLocationContext();
   SVal SizeVal = State->getSVal(Size, LCtx);
   QualType SizeTy = Size->getType();
 
   ProgramStateRef StateZeroSize, StateNonZeroSize;
   std::tie(StateZeroSize, StateNonZeroSize) =
       assumeZero(C, State, SizeVal, SizeTy);
 
   // Get the value of the memory area.
   SVal MemVal = State->getSVal(Mem, LCtx);
 
+  // Get the value for writing.
+  SVal CharVal = State->getSVal(CharE, LCtx);
+
   // If the size is zero, there won't be any actual memory access, so
   // just bind the return value to the Mem buffer and return.
   if (StateZeroSize && !StateNonZeroSize) {
     StateZeroSize = StateZeroSize->BindExpr(CE, LCtx, MemVal);
     C.addTransition(StateZeroSize);
     return;
   }
 
   // Ensure the memory area is not null.
   // If it is NULL there will be a NULL pointer dereference.
   State = checkNonNull(C, StateNonZeroSize, Mem, MemVal);
   if (!State)
     return;
 
   State = CheckBufferAccess(C, State, Size, Mem);
   if (!State)
     return;
+
+  const MemRegion *MR = MemVal.getAsRegion();
+  if (!MR)
+    return;
+
+  // Get the offset and the base region to figure out whether the offset of
+  // buffer is 0.
+  RegionOffset Offset = MR->getAsOffset();
+  const MemRegion *BR = Offset.getRegion();
+
+  Optional<NonLoc> SizeNL = SizeVal.getAs<NonLoc>();
+
+  // void *memset(void *dest, int ch, size_t count);
+  // For now we can only handle the case of offset is 0 and concrete char value.
+  if (Offset.isValid() && !Offset.hasSymbolicOffset() &&
+      Offset.getOffset() == 0 && CharVal.isConstant() && SizeNL) {
+    // Get the base region's extent.
+    auto *SubReg = cast<SubRegion>(BR);
+    DefinedOrUnknownSVal Extent = SubReg->getExtent(svalBuilder);
+
+    ProgramStateRef StateWholeReg, StateNotWholeReg;
+    std::tie(StateWholeReg, StateNotWholeReg) =
+        State->assume(svalBuilder.evalEQ(State, Extent, *SizeNL));
+
+    if (StateWholeReg && !StateNotWholeReg) {
+      // If the 'memset()' acts on the whole region of destination buffer,
+      // bind the second argument's value to the destination buffer with
+      // 'default binding'.
+      State = State->overwriteRegion(svalBuilder.makeLoc(BR), CharVal,
+                                     C.getLocationContext());
+    } else {
+      // If the destination buffer's extent is not equal to the value of
+      // third argument, just invalidate buffer.
+      //
+      // FIXME: This is a hack, 'InvalidateBuffer()' calls
+      // 'invalidateRegions()', which will remove the <MemRegion, SVal> pair
+      // in CStringLength map. So calls 'InvalidateBuffer()' after getting
+      // old string length and before setting the new string length.
       State = InvalidateBuffer(C, State, Mem, C.getSVal(Mem),
-                           /*IsSourceBuffer*/false, Size);
-  if (!State)
-    return;
+                               /*IsSourceBuffer*/ false, Size);
+    }
+
+    ProgramStateRef StateNullChar, StateNonNullChar;
+    std::tie(StateNullChar, StateNonNullChar) =
+        assumeZero(C, State, CharVal, Ctx.UnsignedCharTy);
+
+    if (StateNullChar && !StateNonNullChar) {
+      // If the value of the second arguement of 'memset()' is zero, set the
+      // string length of destination buffer to 0 directly.
+      State = setCStringLength(StateNullChar, MR,
+                               svalBuilder.makeZeroVal(Ctx.getSizeType()));
+    } else if (!StateNullChar && StateNonNullChar) {
+      SVal NewStrLen = svalBuilder.getMetadataSymbolVal(
+          CStringChecker::getTag(), MR, CE, Ctx.getSizeType(),
+          C.getLocationContext(), C.blockCount());
+
+      // If the value of second argument is not zero, then the string length
+      // is at least the size argument.
+      SVal NewStrLenGESize = svalBuilder.evalBinOp(StateNonNullChar, BO_GE,
+                                                   NewStrLen, SizeVal, CmpType);
+
+      State = setCStringLength(
+          StateNonNullChar->assume(
+              NewStrLenGESize.castAs<DefinedOrUnknownSVal>(), true),
+          MR, NewStrLen);
+    }
+  } else {
+    // If the offset is not zero and char value is not concrete, we can do
+    // nothing but invalidate the buffer.
+    State = InvalidateBuffer(C, State, Mem, C.getSVal(Mem),
+                             /*IsSourceBuffer*/ false, Size);
+  }
 
   State = State->BindExpr(CE, LCtx, MemVal);
   C.addTransition(State);
 }
 
 static bool isCPPStdLibraryFunction(const FunctionDecl *FD, StringRef Name) {
   IdentifierInfo *II = FD->getIdentifier();
   if (!II)

lib/StaticAnalyzer/Core/ProgramState.cpp

ProgramStateManager::removeDeadBindings(ProgramStateRef state,
 
   ProgramStateRef Result = getPersistentState(NewState);
   return ConstraintMgr->removeDeadBindings(Result, SymReaper);
 }
 
 ProgramStateRef ProgramState::bindLoc(Loc LV,
                                       SVal V,
                                       const LocationContext *LCtx,
                                       bool notifyChanges) const {
   ProgramStateManager &Mgr = getStateManager();
   ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(),
                                                              LV, V));
   const MemRegion *MR = LV.getAsRegion();
   if (MR && Mgr.getOwningEngine() && notifyChanges)
     return Mgr.getOwningEngine()->processRegionChange(newState, MR, LCtx);
 
   return newState;
 }
 
 ProgramStateRef ProgramState::bindDefault(SVal loc,
                                           SVal V,
                                           const LocationContext *LCtx) const {
   ProgramStateManager &Mgr = getStateManager();
   const MemRegion *R = loc.castAs<loc::MemRegionVal>().getRegion();
   const StoreRef &newStore = Mgr.StoreMgr->BindDefault(getStore(), R, V);
   ProgramStateRef new_state = makeWithStore(newStore);
   return Mgr.getOwningEngine() ?
            Mgr.getOwningEngine()->processRegionChange(new_state, R, LCtx) :
            new_state;
 }
 
+ProgramStateRef
+ProgramState::overwriteRegion(SVal Loc, SVal V,
+                              const LocationContext *LCtx) const {
+  ProgramStateManager &Mgr = getStateManager();
+  const MemRegion *R = Loc.castAs<loc::MemRegionVal>().getRegion();
+  const StoreRef &NewStore = Mgr.StoreMgr->OverwriteRegion(getStore(), R, V);
+  ProgramStateRef NewState = makeWithStore(NewStore);
+  return Mgr.getOwningEngine()
+             ? Mgr.getOwningEngine()->processRegionChange(NewState, R, LCtx)
+             : NewState;
+}
+
 typedef ArrayRef<const MemRegion *> RegionList;
 typedef ArrayRef<SVal> ValueList;
 
 ProgramStateRef
 ProgramState::invalidateRegions(RegionList Regions,
                              const Expr *E, unsigned Count,
                              const LocationContext *LCtx,
                              bool CausedByPointerEscape,

lib/StaticAnalyzer/Core/RegionStore.cpp

if (B.lookup(Key)) {
       B = removeSubRegionBindings(B, SR);
     } else {
       B = B.addBinding(Key, V);
     }
 
     return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this);
   }
 
+  // Clears out the specified region from the store and bind a new value with
+  // default binding.
+  StoreRef OverwriteRegion(Store store, const MemRegion *R, SVal V) override {
+    RegionBindingsRef B = getRegionBindings(store);
+    B = removeSubRegionBindings(B, cast<SubRegion>(R))
+            .addBinding(BindingKey::Make(R, BindingKey::Default), V);
+
+    return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this);
+  }
+
   /// Attempt to extract the fields of \p LCV and bind them to the struct region
   /// \p R.
   ///
   /// This path is used when it seems advantageous to "force" loading the values
   /// within a LazyCompoundVal to bind memberwise to the struct region, rather
   /// than using a Default binding at the base of the entire region. This is a
   /// heuristic attempting to avoid building long chains of LazyCompoundVals.
   ///
if (val.isUnknownOrUndef())
       return val;
 
     // Lazy bindings are usually handled through getExistingLazyBinding().
     // We should unify these two code paths at some point.
     if (val.getAs<nonloc::LazyCompoundVal>() ||
         val.getAs<nonloc::CompoundVal>())
       return val;
 
-    llvm_unreachable("Unknown default value");
+    return val;
   }
 
   return None;
 }
 
 SVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion,
                                         RegionBindingsRef LazyBinding) {
   SVal Result;

lib/StaticAnalyzer/Core/Store.cpp

const ElementRegion *StoreManager::MakeElementRegion(const SubRegion *Base,
   NonLoc idx = svalBuilder.makeArrayIndex(index);
   return MRMgr.getElementRegion(EleTy, idx, Base, svalBuilder.getContext());
 }
 
 StoreRef StoreManager::BindDefault(Store store, const MemRegion *R, SVal V) {
   return StoreRef(store, *this);
 }
 
+StoreRef StoreManager::OverwriteRegion(Store store, const MemRegion *R, SVal V) {
+  return StoreRef(store, *this); 
+}
+
 const ElementRegion *StoreManager::GetElementZeroRegion(const SubRegion *R,
                                                         QualType T) {
   NonLoc idx = svalBuilder.makeZeroArrayIndex();
   assert(!T.isNull());
   return MRMgr.getElementRegion(T, idx, R, Ctx);
 }
 
 const MemRegion *StoreManager::castRegion(const MemRegion *R, QualType CastToTy) {

test/Analysis/bstring.cpp

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix.cstring,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -verify %s
-// RUN: %clang_analyze_cc1 -DUSE_BUILTINS -analyzer-checker=core,unix.cstring,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -verify %s
-// RUN: %clang_analyze_cc1 -DVARIANT -analyzer-checker=core,unix.cstring,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -verify %s
-// RUN: %clang_analyze_cc1 -DUSE_BUILTINS -DVARIANT -analyzer-checker=core,unix.cstring,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -verify %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix.cstring,unix.Malloc,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -verify %s
+// RUN: %clang_analyze_cc1 -DUSE_BUILTINS -analyzer-checker=core,unix.cstring,unix.Malloc,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -verify %s
+// RUN: %clang_analyze_cc1 -DVARIANT -analyzer-checker=core,unix.cstring,alpha.unix.cstring,unix.Malloc,debug.ExprInspection -analyzer-store=region -verify %s
+// RUN: %clang_analyze_cc1 -DUSE_BUILTINS -DVARIANT -analyzer-checker=core,unix.cstring,alpha.unix.cstring,unix.Malloc,debug.ExprInspection -analyzer-store=region -verify %s
+// RUN: %clang_analyze_cc1 -DSUPPRESS_OUT_OF_BOUND -analyzer-checker=core,unix.cstring,unix.Malloc,alpha.unix.cstring.BufferOverlap,alpha.unix.cstring.NotNullTerminated,debug.ExprInspection -analyzer-store=region -verify %s
 
 #include "Inputs/system-header-simulator-cxx.h"
 #include "Inputs/system-header-simulator-for-malloc.h"
 
 // This provides us with four possible mempcpy() definitions.
 // See also comments in bstring.c.
 
 #ifdef USE_BUILTINS
class b {
   void d() {
     int e = c;
     f += e;
     mempcpy(f, &a, g);
   }
   unsigned *f;
 };
 }
+
+void *memset(void *dest, int ch, std::size_t count);
+namespace memset_non_pod {
+class Base {
+public:
+  int b_mem;
+  Base() : b_mem(1) {}
+};
+
+class Derived : public Base {
+public:
+  int d_mem;
+  Derived() : d_mem(2) {}
+};
+
+void memset1_inheritance() {
+  Derived d;
+  memset(&d, 0, sizeof(Derived));
+  clang_analyzer_eval(d.b_mem == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(d.d_mem == 0); // expected-warning{{TRUE}}
+}
+
+#ifdef SUPPRESS_OUT_OF_BOUND
+void memset2_inheritance_field() {
+  Derived d;
+  memset(&d.d_mem, 0, sizeof(Derived));
+  clang_analyzer_eval(d.b_mem == 0); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(d.d_mem == 0); // expected-warning{{UNKNOWN}}
+}
+
+void memset3_inheritance_field() {
+  Derived d;
+  memset(&d.b_mem, 0, sizeof(Derived));
+  clang_analyzer_eval(d.b_mem == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(d.d_mem == 0); // expected-warning{{TRUE}}
+}
+#endif
+
+void memset4_array_nonpod_object() {
+  Derived array[10];
+  clang_analyzer_eval(array[1].b_mem == 1); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(array[1].d_mem == 2); // expected-warning{{UNKNOWN}}
+  memset(&array[1], 0, sizeof(Derived));
+  clang_analyzer_eval(array[1].b_mem == 0); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(array[1].d_mem == 0); // expected-warning{{UNKNOWN}}
+}
+
+void memset5_array_nonpod_object() {
+  Derived array[10];
+  clang_analyzer_eval(array[1].b_mem == 1); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(array[1].d_mem == 2); // expected-warning{{UNKNOWN}}
+  memset(array, 0, sizeof(array));
+  clang_analyzer_eval(array[1].b_mem == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(array[1].d_mem == 0); // expected-warning{{TRUE}}
+}
+
+void memset6_new_array_nonpod_object() {
+  Derived *array = new Derived[10];
+  clang_analyzer_eval(array[2].b_mem == 1); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(array[2].d_mem == 2); // expected-warning{{UNKNOWN}}
+  memset(array, 0, 10 * sizeof(Derived));
+  clang_analyzer_eval(array[2].b_mem == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(array[2].d_mem == 0); // expected-warning{{TRUE}}
+  delete [] array;
+}
+
+void memset7_placement_new() {
+  Derived *d = new Derived();
+  clang_analyzer_eval(d->b_mem == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(d->d_mem == 2); // expected-warning{{TRUE}}
+
+  memset(d, 0, sizeof(Derived));
+  clang_analyzer_eval(d->b_mem == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(d->d_mem == 0); // expected-warning{{TRUE}}
+
+  Derived *d1 = new (d) Derived();
+  clang_analyzer_eval(d1->b_mem == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(d1->d_mem == 2); // expected-warning{{TRUE}}
+
+  memset(d1, 0, sizeof(Derived));
+  clang_analyzer_eval(d->b_mem == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(d->d_mem == 0); // expected-warning{{TRUE}}
+}
+
+class BaseVirtual {
+public:
+  int b_mem;
+  virtual int get() { return 1; }
+};
+
+class DerivedVirtual : public BaseVirtual {
+public:
+  int d_mem;
+};
+
+#ifdef SUPPRESS_OUT_OF_BOUND
+void memset8_virtual_inheritance_field() {
+  DerivedVirtual d;
+  memset(&d.b_mem, 0, sizeof(Derived));
+  clang_analyzer_eval(d.b_mem == 0); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(d.d_mem == 0); // expected-warning{{UNKNOWN}}
+}
+#endif
+} // namespace memset_non_pod
+
+#ifdef SUPPRESS_OUT_OF_BOUND
+void memset1_new_array() {
+  int *array = new int[10];
+  memset(array, 0, 10 * sizeof(int));
+  clang_analyzer_eval(array[2] == 0); // expected-warning{{TRUE}}
+  memset(array + 1, 'a', 10 * sizeof(9));
+  clang_analyzer_eval(array[2] == 0); // expected-warning{{UNKNOWN}}
+  delete [] array;
+}
+#endif

test/Analysis/null-deref-ps-region.c

if (i != 1) {
     int *p = 0;
     i = *p; // no-warning
   }
 }
 
 void foo() {
   int *x = malloc(sizeof(int));
   memset(x, 0, sizeof(int));
-  int n = 1 / *x; // FIXME: no-warning
+  int n = 1 / *x; // expected-warning {{Division by zero}}
   free(x);
 }
 
 void bar() {
   int *x = malloc(sizeof(int));
   memset(x, 0, 1);
   int n = 1 / *x; // no-warning
   free(x);

test/Analysis/string.c

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix.cstring,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -Wno-null-dereference -verify %s
-// RUN: %clang_analyze_cc1 -DUSE_BUILTINS -analyzer-checker=core,unix.cstring,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -Wno-null-dereference -verify %s
-// RUN: %clang_analyze_cc1 -DVARIANT -analyzer-checker=core,unix.cstring,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -Wno-null-dereference -verify %s
-// RUN: %clang_analyze_cc1 -DUSE_BUILTINS -DVARIANT -analyzer-checker=alpha.security.taint,core,unix.cstring,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -Wno-null-dereference -verify %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix.cstring,unix.Malloc,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -Wno-null-dereference -verify %s
+// RUN: %clang_analyze_cc1 -DUSE_BUILTINS -analyzer-checker=core,unix.cstring,unix.Malloc,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -Wno-null-dereference -verify %s
+// RUN: %clang_analyze_cc1 -DVARIANT -analyzer-checker=core,unix.cstring,unix.Malloc,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -Wno-null-dereference -verify %s
+// RUN: %clang_analyze_cc1 -DUSE_BUILTINS -DVARIANT -analyzer-checker=alpha.security.taint,core,unix.cstring,unix.Malloc,alpha.unix.cstring,debug.ExprInspection -analyzer-store=region -Wno-null-dereference -verify %s
+// RUN: %clang_analyze_cc1 -DSUPPRESS_OUT_OF_BOUND -analyzer-checker=core,unix.cstring,unix.Malloc,alpha.unix.cstring.BufferOverlap,alpha.unix.cstring.NotNullTerminated,debug.ExprInspection -analyzer-store=region -Wno-null-dereference -verify %s
 
 //===----------------------------------------------------------------------===
 // Declarations
 //===----------------------------------------------------------------------===
 
 // Some functions are so similar to each other that they follow the same code
 // path, such as memcpy and __memcpy_chk, or memcmp and bcmp. If VARIANT is
 // defined, make sure to use the variants instead to make sure they are still
void strsep_changes_input_string() {
   strsep(&s, "b"); // no-warning
 
   // The real strsep will change the first delimiter it finds into a NUL
   // character. For now, we just model the invalidation.
   clang_analyzer_eval(str[1] == 'b'); // expected-warning{{UNKNOWN}}
 }
 
 //===----------------------------------------------------------------------===
+// memset()
+//===----------------------------------------------------------------------===
+
+void *memset( void *dest, int ch, size_t count );
+
+void* malloc(size_t size);
+void free(void*);
+
+void memset1_char_array_null() {
+  char str[] = "abcd";
+  clang_analyzer_eval(strlen(str) == 4); // expected-warning{{TRUE}}
+  memset(str, '\0', 2);
+  clang_analyzer_eval(strlen(str) == 0); // expected-warning{{TRUE}}
+}
+
+void memset2_char_array_null() {
+  char str[] = "abcd";
+  clang_analyzer_eval(strlen(str) == 4); // expected-warning{{TRUE}}
+  memset(str, '\0', strlen(str) + 1);
+  clang_analyzer_eval(strlen(str) == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(str[2] == 0);      // expected-warning{{TRUE}}
+}
+
+void memset3_char_malloc_null() {
+  char *str = (char *)malloc(10 * sizeof(char));
+  memset(str + 1, '\0', 8);
+  clang_analyzer_eval(str[1] == 0); // expected-warning{{UNKNOWN}}
+  free(str);
+}
+
+void memset4_char_malloc_null() {
+  char *str = (char *)malloc(10 * sizeof(char));
+  //void *str = malloc(10 * sizeof(char));
+  memset(str, '\0', 10);
+  clang_analyzer_eval(str[1] == 0);      // expected-warning{{TRUE}}
+  clang_analyzer_eval(strlen(str) == 0); // expected-warning{{TRUE}}
+  free(str);
+}
+
+#ifdef SUPPRESS_OUT_OF_BOUND
+void memset5_char_malloc_overflow_null() {
+  char *str = (char *)malloc(10 * sizeof(char));
+  memset(str, '\0', 12);
+  clang_analyzer_eval(str[1] == 0); // expected-warning{{UNKNOWN}}
+  free(str);
+}
+#endif
+
+void memset6_char_array_nonnull() {
+  char str[] = "abcd";
+  clang_analyzer_eval(strlen(str) == 4); // expected-warning{{TRUE}}
+  memset(str, '0', 2);
+  clang_analyzer_eval(str[0] == 'a');    // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(strlen(str) == 4); // expected-warning{{UNKNOWN}}
+}
+
+void memset7_char_array_nonnull() {
+  char str[5] = "abcd";
+  clang_analyzer_eval(strlen(str) == 4); // expected-warning{{TRUE}}
+  memset(str, '0', 5);
+  clang_analyzer_eval(str[0] == '0');    // expected-warning{{TRUE}}
+  clang_analyzer_eval(strlen(str) >= 5); // expected-warning{{TRUE}}
+}
+
+#ifdef SUPPRESS_OUT_OF_BOUND
+void memset8_char_array_nonnull() {
+  char str[5] = "abcd";
+  clang_analyzer_eval(strlen(str) == 4); // expected-warning{{TRUE}}
+  memset(str, '0', 10);
+  clang_analyzer_eval(str[0] != '0'); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(strlen(str) >= 10); // expected-warning{{TRUE}}
+  clang_analyzer_eval(strlen(str) < 10); // expected-warning{{FALSE}}
+}
+#endif
+
+struct POD_memset {
+  int num;
+  char c;
+};
+
+void memset10_struct() {
+  struct POD_memset pod;
+  char *str = (char *)&pod;
+  pod.num = 1;
+  pod.c = 1;
+  clang_analyzer_eval(pod.num == 0); // expected-warning{{FALSE}}
+  memset(str, 0, sizeof(struct POD_memset));
+  clang_analyzer_eval(pod.num == 0); // expected-warning{{TRUE}}
+}
+
+#ifdef SUPPRESS_OUT_OF_BOUND
+void memset11_struct_field() {
+  struct POD_memset pod;
+  pod.num = 1;
+  pod.c = '1';
+  memset(&pod.num, 0, sizeof(struct POD_memset));
+
+  clang_analyzer_eval(pod.num == 0);  // expected-warning{{TRUE}}
+  clang_analyzer_eval(pod.c == '\0'); // expected-warning{{TRUE}}
+}
+
+void memset12_struct_field() {
+  struct POD_memset pod;
+  pod.num = 1;
+  pod.c = '1';
+  memset(&pod.c, 0, sizeof(struct POD_memset));
+  clang_analyzer_eval(pod.num == 0); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(pod.c == 0);   // expected-warning{{UNKNOWN}}
+}
+
+union U_memset {
+  int i;
+  double d;
+  char c;
+};
+
+void memset13_union_field() {
+  union U_memset u;
+  u.i = 5;
+  memset(&u.i, '\0', sizeof(union U_memset));
+  // Note: This should be TRUE, analyzer can't handle union perfectly now.
+  clang_analyzer_eval(u.d == 0); // expected-warning{{UNKNOWN}}
+}
+#endif
+
+void memset14_region_cast() {
+  char *str = (char*)malloc(10 * sizeof(int));
+  int *array = (int*)str;
+  memset(array, 0, 10 * sizeof(int));
+  clang_analyzer_eval(str[10] == '\0'); // expected-warning{{TRUE}}
+  clang_analyzer_eval(strlen((char*)array) == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(strlen(str) == 0); // expected-warning{{TRUE}}
+  free(str);
+}
+
+void memset15_region_cast() {
+  char *str = (char*)malloc(10 * sizeof(int));
+  int *array = (int*)str;
+  memset(array, 0, 5 * sizeof(int));
+  clang_analyzer_eval(str[10] == '\0'); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(strlen((char*)array) == 0); // expected-warning{{TRUE}}
+  clang_analyzer_eval(strlen(str) == 0); // expected-warning{{TRUE}}
+  free(str);
+}
+
+
+void memset16_region_cast() {
+  char *str = (char*)malloc(10 * sizeof(int));
+  int *array = (int*)str;
+  memset(array, '0', 10 * sizeof(int));
+  clang_analyzer_eval(str[10] == '0'); // expected-warning{{TRUE}}
+  clang_analyzer_eval(strlen((char*)array) >= 10 * sizeof(int)); // expected-warning{{TRUE}}
+  clang_analyzer_eval(strlen(str) >= 10 * sizeof(int)); // expected-warning{{TRUE}}
+  free(str);
+}
+
+#ifdef SUPPRESS_OUT_OF_BOUND
+void memset17_region_cast() {
+  char *str = (char*)malloc(10 * sizeof(int));
+  int *array = (int*)str;
+  memset(array, '0', 12 * sizeof(int));
+  clang_analyzer_eval(str[10] == '0'); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(strlen((char*)array) >= 12 * sizeof(int)); // expected-warning{{TRUE}}
+  clang_analyzer_eval(strlen(str) >= 12 * sizeof(int)); // expected-warning{{TRUE}}
+  free(str);
+}
+
+void memset18_memset_multiple_times() {
+  char *str = (char *)malloc(10 * sizeof(char));
+  clang_analyzer_eval(strlen(str) == 0); // expected-warning{{UNKNOWN}}
+
+  memset(str + 2, '\0', 10 * sizeof(char));
+  clang_analyzer_eval(strlen(str) == 0); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(str[1] == '\0');   // expected-warning{{UNKNOWN}}
+
+  memset(str, '0', 10 * sizeof(char));
+  clang_analyzer_eval(strlen(str) >= 10); // expected-warning{{TRUE}}
+  clang_analyzer_eval(str[1] == '0');     // expected-warning{{TRUE}}
+
+  free(str);
+}
+
+void memset19_memset_multiple_times() {
+  char *str = (char *)malloc(10 * sizeof(char));
+  clang_analyzer_eval(strlen(str) == 0); // expected-warning{{UNKNOWN}}
+
+  memset(str, '0', 10 * sizeof(char));
+  clang_analyzer_eval(strlen(str) >= 10); // expected-warning{{TRUE}}
+  clang_analyzer_eval(str[1] == '0');     // expected-warning{{TRUE}}
+
+  memset(str + 2, '\0', 10 * sizeof(char));
+  clang_analyzer_eval(strlen(str) >= 10); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(str[1] == '0');     // expected-warning{{UNKNOWN}}
+
+  free(str);
+}
+#endif
+
+int memset20_scalar() {
+  int *x = malloc(sizeof(int));
+  *x = 10;
+  memset(x, 0, sizeof(int));
+  int num = 1 / *x; // expected-warning{{Division by zero}}
+  free(x);
+  return num;
+}
+
+int memset21_scalar() {
+  int *x = malloc(sizeof(int));
+  memset(x, 0, 1);
+  int num = 1 / *x;
+  free(x);
+  return num;
+}
+
+void memset22_array() {
+  int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
+  clang_analyzer_eval(array[1] == 2); // expected-warning{{TRUE}}
+  memset(array, 0, sizeof(array));
+  clang_analyzer_eval(array[1] == 0); // expected-warning{{TRUE}}
+}
+
+
+void memset23_array_pod_object() {
+  struct POD_memset array[10];
+  array[1].num = 10;
+  array[1].c = 'c';
+  clang_analyzer_eval(array[1].num == 10); // expected-warning{{TRUE}}
+  memset(&array[1], 0, sizeof(struct POD_memset));
+  clang_analyzer_eval(array[1].num == 0); // expected-warning{{UNKNOWN}}
+}
+
+void memset24_array_pod_object() {
+  struct POD_memset array[10];
+  array[1].num = 10;
+  array[1].c = 'c';
+  clang_analyzer_eval(array[1].num == 10); // expected-warning{{TRUE}}
+  memset(array, 0, sizeof(array));
+  clang_analyzer_eval(array[1].num == 0); // expected-warning{{TRUE}}
+}
+
+//===----------------------------------------------------------------------===
 // FIXMEs
 //===----------------------------------------------------------------------===
 
 // The analyzer_eval call below should evaluate to true. We are being too 
 // aggressive in marking the (length of) src symbol dead. The length of dst 
 // depends on src. This could be explicitely specified in the checker or the 
 // logic for handling MetadataSymbol in SymbolManager needs to change.
 void strcat_symbolic_src_length(char *src) {
if (strlen(y) >= 4)
     return;
 
   char x[4];
   strncpy(x, y, 4); // no-warning
 
   // This time, we know that y fits in x anyway.
   clang_analyzer_eval(strlen(x) <= 3); // expected-warning{{UNKNOWN}}
 }
+
+// The analyzer does not support binding a symbol with default binding.
+void memset25_symbol(char c) {
+  char array[10] = {0};
+  if (c > 10)
+    return;
+
+  memset(array, c, 10);
+
+  // This should be TRUE.
+  clang_analyzer_eval(array[4] <= 10); // expected-warning{{UNKNOWN}}
+}