[analyzer] Check NULL pointer dereference issue for memset function

[xiangzhai]

Summary

Hi LLVM developers,

As Anna mentioned:

One idea is to check that we do not pass a pointer that is known to be NULL to functions that are known to dereference pointers such as memcpy. There is a checker that determines if a null pointer could be dereferenced already, but there is no extension to check if such a pointer could be passed to a function tat could dereference it.

So I implemented evalMemset in the CStringChecker to detect null-deref issue. please review my patch, thanks a lot!

Regards,
Leslie Zhai

[danielmarjamaki]

Thanks! Looks like a valueable addition.

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

2004 ↗

(On Diff #94627)

even better: != 3

2009 ↗

(On Diff #94627)

The name "S" does not tell me much.. how about something like Data / DataArg / PtrArg / ..?

2011 ↗

(On Diff #94627)

Variables should start with capital.. State, SizeVal, SizeTy, ...

2034 ↗

(On Diff #94627)

use early return:

if (!stateNonZeroSize)
  return;

[xiangzhai]

Hi Daniel,

Thanks for your review!

Sorry I am not available until this Friday, then I will update my patch.

Regards,
Leslie Zhai

[NoQ]

This looks correct! Thanks for taking this up.

One of the possible improvements for future work here would be to actually bind the second argument value to the buffer instead of just invalidating it. Like, after memset(buf, 0, sizeof(buf)) the analyzer should know that all values in the buf array are 0. In the analyzer we have the notion of *default bindings* to handle that (see documentation in docs/analyzer/RegionStore.txt for more details). However, they would only work when the whole region is memseted, not when we're wiping a smaller portion of the region. But the special case of memseting the whole region is important enough to be worth handling separately anyway. In order to detect this special case, you can find the region's *extent* and see if it's exactly equal to the size argument (ideally, handle comparison with the assume method). This would work not only for arrays, but also for regions allocated via malloc or C++ operator new. There is an attempt to do a similar thing for strdup in D20863 (mixed with more complicated stuff).

Since we're in CStringChecker, we may also want to see how memset affects our model of string length. If we memset to zero everything from the beginning of the region, the length of the resulting C string is 0; if not to zero, then the length of the resulting C string is at least the size argument; if not from the beginning, then we've no idea, unless we knew the length before and it was less then the offset from which we started memseting.

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

2025 ↗

(On Diff #94627)

Trailing spaces here.

2037 ↗

(On Diff #94627)

One more trailing space.

2051–2052 ↗

(On Diff #94627)

And a few more trailing spaces :) I usually catch those with a colored git diff and highlight them in my editor as well, and also have a hotkey to clang-format current line, which is probably the most handy.

[xiangzhai]

Hi Artem,

Thanks for your review! I will update my patch tomorrow :)

Regards,
Leslie Zhai

[xiangzhai]

Hi All,

I have updated my patch as your suggestion, please review it, thanks a lot!

Regards,
Leslie Zhai

[xiangzhai]

Hi Artem,

If it looks good to you, I want to try commit by myself for testing commit, thanks!

Regards,
Leslie Zhai

[danielmarjamaki]

Please click "Done" on fixed review comments.

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

2038 ↗

(On Diff #95273)

This "if (StateNonZeroSize)" condition is useless now since you added a early return

2039 ↗

(On Diff #95273)

I suggest code cleanup:

State = StateNonZeroSize;
State = checkNonNull(C, State, Mem, MemVal);

Change that to:

State = checkNonNull(C, StateNonZeroSize, Mem, MemVal);

2063 ↗

(On Diff #95273)

indentation. I personally like the clang-format-diff script also. That would cleanup all your changes.

cd llvm/tools/clang
svn diff | python tools/clang-format/clang-format-diff.py -i

It should work with git diff also but I have not tried that.

[NoQ]

Wow, so you're doing the binding thing now? Thanks! It was not critical for landing this patch, so you could have fixed comments here, allowing us to commit what's already done, and then proceed with further improvements. It's also easier to review and aligns with the LLVM's policy of incremental development.

Could you add test cases for the new feature? For instance,

void foo() {
  int *x = malloc(sizeof(int));
  memset(x, 0, sizeof(int));
  1 / *x; // expected-warning{{Division by zero}}
}

void bar() {
  int *x = malloc(sizeof(int));
  memset(x, 0, 1);
  1 / *x; // no-warning
}

Tests that involve setting memory to anything but 0 are also welcome!

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

2066 ↗

(On Diff #95273)

I believe that if the size is not the same, you'd still need to do invalidation.

[xiangzhai]

Hi All,

Thanks for your review! I will update my patch tomorrow! Almost 4+ days no see, I miss you :)

Regards,
Leslie Zhaii

[xiangzhai]

Hi Artem,

so you're doing the binding thing now?

No! it only works for RetVal for example int *ret = memset(x, 0, sizeof(int)); please see my testcase:

void foo() {
  int *x = malloc(sizeof(int));
  int *ret = memset(x, 0, sizeof(int));
  int n = 1 / *ret; // expected-warning {{Division by zero}}
  free(x);
}

but not work for MemVal for example int n = 1 / *x;

Please carefully review my patch to point out my fault: wrongly use bindDefault? I have tried bindDefault for MemVal, and for RetVal. thanks a lot!

Regards,
Leslie Zhai

[xiangzhai]

Hi Artem,

Because memcpy checked NULL pointer dereference for src:

state = checkNonNull(C, state, Source, srcVal);
...

so such testcase can not point out my fault:

void f15 () {                                                                      
  int *x = malloc(sizeof(int));                                                    
  memcpy(x, 0, sizeof(int)); // expected-warning {{Null pointer argument in call to memory copy function}}
  int n = 1 / *x;                                                                  
  free(x);                                                                         
}

And I have no idea how to copy RetVal to Mem s:

if (StateSameSize) {                                                            
      SVal ConstVal = State->getSVal(Const, LCtx);                                  
      State = State->BindExpr(CE, LCtx, RetVal);                                    
      // Actually bind the second argument value to the buffer.                     
      State = State->bindDefault(RetVal, ConstVal, LCtx);                           
      // FIXME: Copy to Mem                                                         
      const MemRegion *MR = RetVal.getAsRegion();                                   
      if (!MR)                                                                      
        return;                                                                     
      MR = MR->StripCasts();                                                        
      if (const TypedValueRegion *TVR = MR->getAs<TypedValueRegion>()) {            
        MemVal = SB.makeLazyCompoundVal(StoreRef(State->getStore(),                 
                    State->getStateManager().getStoreManager()), TVR);              
        State = State->BindExpr(CE, LCtx, MemVal);                                  
      }                                                                             
      C.addTransition(State);                                                       
    }

Please give me some advice, thanks a lot!

Regards,
Leslie Zhai

[NoQ]

I've a feeling we need to roll this back a little bit.

The memset() function does the following:

1. Accesses pointers in range R = [first argument, first argument + third argument] and crashes when accessing an invalid pointer.
2. Writes second argument to all bytes in range R.
3. Returns its first argument.

Assuming R is an empty set, steps 1 and 2 are skipped.

We handle step 1 through checkNonNull and checkBufferAccess. These easy-to-use functions are already available in the checker, just pass the arguments there directly.

For step 2, we decided to skip most of the step, instead invalidating the whole base region around R. There's a separate task to come up with a better behavior here, but we decided to do it later, probably in the next patch. So for now, the relationship between the size of the buffer and the third argument are not relevant and should not be considered - this is an idea for the future.

Finally, step 3 can be done by binding the call expression to the symbolic value of the first argument through BindExpr. You are already doing this in the zero-size case, but it should be similar in all cases. There is no need to construct a new symbol here - just use the existing SVal.

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

2045–2049 ↗

(On Diff #96344)

Here you construct a new symbol that represents the pointer returned. However, we return our first argument, which is already denoted by symbolic value MemVal, so we don't need a new symbol here - we'd return MemVal directly, and work on it directly during invalidation.

Also, note that it's not necessarily on the heap.

2034 ↗

(On Diff #94627)

In fact this early return is unnecessary. Of the two states returned by assume(), at least one is always non-null (we have an assertion for that). However, the since the situation (StateZeroSize && !StateNonZeroSize) was checked above, it follows from (!StateNonZeroSize) that StateZeroSize is also null, which contradicts the above.

So we can assert here that StateNonZeroSize is not null.

[xiangzhai]

Hi Artem,

Thank you so much! you are my mentor teach me patiently and carefully, I will update my patch tomorrow, good night from my timezone:)

Regards,
Leslie Zhai

[xiangzhai]

Hi Artem,

Please review my updated patch, thanks a lot!

Regards,
Leslie Zhai

[NoQ]

The code looks good now! A few minor comments and we can commit this :)

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

2010 ↗

(On Diff #97042)

This variable is unused. It might make buildbots angry.

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

25 ↗

(On Diff #97042)

Could you mark this as FIXME? Eg:

int n = 1 / *x; // FIXME: no-warning

Because eventually it should warn.

36 ↗

(On Diff #97042)

Can we make function names more fancy?

Eg. "testConcreteNull", "testStackArray", "testHeapSymbol", etc.

[xiangzhai]

Hi Artem,

Long time no see! miss you :)

I will update my patch next Thursday! I am doing my work assignment about L4 right now.

Regards,
Leslie Zhai

[xiangzhai]

Hi Artem,

I updated my patch please review it, thanks a lot!

Regards,
Leslie Zhai

[xiangzhai]

Kindly ping Artem and Anna :)

[NoQ]

Thanks, this was very useful, please commit!

[MTC]

One of the possible improvements for future work here would be to actually bind the second argument value to the buffer instead of just invalidating it. Like, after memset(buf, 0, sizeof(buf)) the analyzer should know that all values in the buf array are 0. In the analyzer we have the notion of *default bindings* to handle that (see documentation in docs/analyzer/RegionStore.txt for more details).

BindDefault() is the only function that can make the default binding, is it? If so, evalMemset() uses bindDefault(), the binding may not take effect. Because the current BindDefault() logic is that if the memory area has been initialized, then the default binding will no longer be done, see https://github.com/llvm-mirror/clang/blob/master/lib/StaticAnalyzer/Core/RegionStore.cpp#L429. Before evalMemset(), MallocMemAux() in MallocChecker.cpp may have already made the default binding. Am I right?

Thank you!

[xiangzhai]

Dear Henry,

Sorry for my poor English, please Create a New patch or provide Chinese translation :)

Regards,
Leslie Zhai

[NoQ]

In D31868#904814, @MTC wrote:

One of the possible improvements for future work here would be to actually bind the second argument value to the buffer instead of just invalidating it. Like, after memset(buf, 0, sizeof(buf)) the analyzer should know that all values in the buf array are 0. In the analyzer we have the notion of *default bindings* to handle that (see documentation in docs/analyzer/RegionStore.txt for more details).

BindDefault() is the only function that can make the default binding, is it? If so, evalMemset() uses bindDefault(), the binding may not take effect. Because the current BindDefault() logic is that if the memory area has been initialized, then the default binding will no longer be done, see https://github.com/llvm-mirror/clang/blob/master/lib/StaticAnalyzer/Core/RegionStore.cpp#L429. Before evalMemset(), MallocMemAux() in MallocChecker.cpp may have already made the default binding. Am I right?

Seems so, and it also looks super counter-intuitive. We definitely do need to overwrite default bindings from time to time. When RegionStore itself wants to overwrite a default binding, it does removeBindings() first (see invalidateGlobalRegion() as an example). I think ProgramState::bindDefault() should behave this way as well, not sure about impact of such change.

cfe/trunk/lib/StaticAnalyzer/Checkers/CStringChecker.cpp

void evalStrcmpCommon(CheckerContext &C,
                         bool isBounded = false,
                         bool ignoreCase = false) const;
 
   void evalStrsep(CheckerContext &C, const CallExpr *CE) const;
 
   void evalStdCopy(CheckerContext &C, const CallExpr *CE) const;
   void evalStdCopyBackward(CheckerContext &C, const CallExpr *CE) const;
   void evalStdCopyCommon(CheckerContext &C, const CallExpr *CE) const;
+  void evalMemset(CheckerContext &C, const CallExpr *CE) const;
 
   // Utility methods
   std::pair<ProgramStateRef , ProgramStateRef >
   static assumeZero(CheckerContext &C,
                     ProgramStateRef state, SVal V, QualType Ty);
 
   static ProgramStateRef setCStringLength(ProgramStateRef state,
                                               const MemRegion *MR,
void CStringChecker::evalStdCopyCommon(CheckerContext &C,
   SValBuilder &SVB = C.getSValBuilder();
 
   SVal ResultVal = SVB.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
   State = State->BindExpr(CE, LCtx, ResultVal);
 
   C.addTransition(State);
 }
 
+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 *Size = CE->getArg(2);
+  ProgramStateRef State = C.getState();
+
+  // 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);
+
+  // 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;
+  State = InvalidateBuffer(C, State, Mem, C.getSVal(Mem),
+                           /*IsSourceBuffer*/false, Size);
+  if (!State)
+    return;
+
+  State = State->BindExpr(CE, LCtx, MemVal);
+  C.addTransition(State);
+}
+
 static bool isCPPStdLibraryFunction(const FunctionDecl *FD, StringRef Name) {
   IdentifierInfo *II = FD->getIdentifier();
   if (!II)
     return false;
 
   if (!AnalysisDeclContext::isInStdNamespace(FD))
     return false;
 
bool CStringChecker::evalCall(const CallExpr *CE, CheckerContext &C) const {
   if (C.isCLibraryFunction(FDecl, "memcpy"))
     evalFunction =  &CStringChecker::evalMemcpy;
   else if (C.isCLibraryFunction(FDecl, "mempcpy"))
     evalFunction =  &CStringChecker::evalMempcpy;
   else if (C.isCLibraryFunction(FDecl, "memcmp"))
     evalFunction =  &CStringChecker::evalMemcmp;
   else if (C.isCLibraryFunction(FDecl, "memmove"))
     evalFunction =  &CStringChecker::evalMemmove;
+  else if (C.isCLibraryFunction(FDecl, "memset"))
+    evalFunction =  &CStringChecker::evalMemset;
   else if (C.isCLibraryFunction(FDecl, "strcpy"))
     evalFunction =  &CStringChecker::evalStrcpy;
   else if (C.isCLibraryFunction(FDecl, "strncpy"))
     evalFunction =  &CStringChecker::evalStrncpy;
   else if (C.isCLibraryFunction(FDecl, "stpcpy"))
     evalFunction =  &CStringChecker::evalStpcpy;
   else if (C.isCLibraryFunction(FDecl, "strcat"))
     evalFunction =  &CStringChecker::evalStrcat;

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

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,alpha.core -std=gnu99 -analyzer-store=region -verify %s
-// expected-no-diagnostics
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,alpha.core,unix,alpha.unix -std=gnu99 -analyzer-store=region -verify %s
 
+#include "Inputs/system-header-simulator.h"
+
+typedef __typeof(sizeof(int)) size_t;
+void *memset(void *__s, int __c, size_t __n);
+void *malloc(size_t __size);
+void free(void *__ptr);
 
 // The store for 'a[1]' should not be removed mistakenly. SymbolicRegions may
 // also be live roots.
 void f14(int *a) {
   int i;
   a[1] = 1;
   i = a[1];
   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
+  free(x);
+}
+
+void bar() {
+  int *x = malloc(sizeof(int));
+  memset(x, 0, 1);
+  int n = 1 / *x; // no-warning
+  free(x);
+}
+
+void testConcreteNull() {
+  int *x = 0;
+  memset(x, 0, 1); // expected-warning {{Null pointer argument in call to memory set function}}
+}
+
+void testStackArray() {
+  char buf[13];
+  memset(buf, 0, 1); // no-warning
+}
+
+void testHeapSymbol() {
+  char *buf = (char *)malloc(13);
+  memset(buf, 0, 1); // no-warning
+  free(buf);
+}
+
+void testStackArrayOutOfBound() {
+  char buf[1];
+  memset(buf, 0, 1024); // expected-warning {{Memory set function accesses out-of-bound array element}}
+}
+
+void testHeapSymbolOutOfBound() {
+  char *buf = (char *)malloc(1);
+  memset(buf, 0, 1024); // expected-warning {{Memory set function accesses out-of-bound array element}}
+  free(buf);
+}
+
+void testStackArraySameSize() {
+  char buf[1];
+  memset(buf, 0, sizeof(buf)); // no-warning
+}
+
+void testHeapSymbolSameSize() {
+  char *buf = (char *)malloc(1);
+  memset(buf, 0, 1); // no-warning
+  free(buf);
+}