[analyzer] Done some changes to detect Uninitialized read by the char array manipulation functions

[phyBrackets]

Summary

Few weeks back I was experimenting with reading the uninitialized values from src , which is actually a bug but the CSA seems to give up at that point . I was curious about that and I pinged @steakhal on the discord and according to him this seems to be a genuine issue and needs to be fix. So I goes with fixing this bug and thanks to @steakhal who help me creating this patch. This feature seems to break some tests but this was the genuine problem and the broken tests also needs to fix in certain manner. I add a test but yeah we need more tests,I'll try to add more tests.Thanks

[steakhal]

I'm looking forward to this check.

clang/test/Analysis/bstring.c

300–311

Basically, the store has 4 direct bindings for the src cluster.
At bit offset 0, 32, 64, 96, the values 1, 2, 3, 4 (ints) respectively.
However, in the memcopy modeling, we calculate the byte offset of the very last touched byte, which is byte 15.
Consequently, we will do a lookup in the store for acquiring a binding starting at bit offset 15*8, aka. 120.
However, there is no binding for that offset. What we have instead, is a binding starting at offset 96, associating an integer, which is 4 bytes long, thus this entry actually refers to the bits [96-128], so it overlaps with the byte at [120-128].
From this, we should be able to prove that the given bits must have been initialized to some value.

What I cannot remember off the top of my head, what was the type of the ER. I hope it was char, but I cannot recall.
If that was char, then we have a bug in the store.

[NoQ]

This looks like a good check to ultimately have but we probably won't be able to move it out of alpha until the extents issue is fixed (which is going to be a fairly intrusive fix).

clang/test/Analysis/bstring.c

300–311

Yes, this is correct. It looks like we can't have this check until we address 43459.

[NoQ]

I removed the [NFCi] marker because this commit does introduce functional change (a new checker).

[NoQ]

Also I think we might be able to enable this checker for the situation when the buffer is *completely* uninitialized. It is relatively easy for RegionStore to answer whether there are any bindings in a top-level region.

[steakhal]

Oh wait, should we accept this given this serious limitation?

clang/include/clang/StaticAnalyzer/Checkers/Checkers.td

475–479

We also need documentation in the clang/docs/analyzer/checkers.rst.
Please also note the limitation we experienced and described here.
Also refer back to the Umbrella GitHub issue in that section.

clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp

262

378

Remove this line.

[phyBrackets]

@steakhal would you just help, where in the file and what exactly write to in the documentation?

[NoQ]

Oh wait, should we accept this given this serious limitation?

This check lands as alpha so it's fine. We know what to do to move it out of alpha; it's somewhat difficult but definitely not impossible, so there's a way forward with this, and the code added by this patch is ultimately correct.

clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp

600

Yeah, dumps need to be removed from the final code.

[phyBrackets]

Revised the changes

[steakhal]

clang/docs/analyzer/checkers.rst

2634–2647

I was thinking about something like this.

[phyBrackets]

update the documentation for the uninitialized read checker

[phyBrackets]

aligned the indentation

[phyBrackets]

fix some alignment issue

[steakhal]

Approved, given that it looks and compiles fine with oxygen.
Thank you.

[NoQ]

clang/test/Analysis/bstring.c

310

Hmm, given that your change suppresses some existing tests, maybe disable your checker on this file and copy the updated tests to a new file that would have the checker enabled?

[phyBrackets]

clang/test/Analysis/bstring.c

310

I don't know how will it affect that but still that's an exception and from these exceptions test cases, we are updated about how it gonna fail on some tests cases and try to work on those exceptions.

[phyBrackets]

Hey @NoQ and @steakhal , can i land this patch ?

[steakhal]

You should copy the mempcpy14, mempcpy15 test cases into a separate file, and cut the top; while disabling this alpha.unix.cstring.UninitializedRead checker in the existing test file(s) and explicitly enable in the new separated file.
This way it wouldn't interfere with the existing test cases, since it would halt the analyzer (emits a sink node).
After that, you could land it.

[steakhal]

clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp

377

You should make this check optional, only if the 'checker' was enabled.

[phyBrackets]

Created the separate test file for UninitializedRead checker

[phyBrackets]

Hey @NoQ and @steakhal , will you just check , if everything looks fine or not! The test cases run successfully tho now!

[steakhal]

Please mark the done comments as "done" with the corresponding button prior to submitting an update.

clang/test/Analysis/bstring_UninitRead.c

67–85 ↗

(On Diff #412391)

I don't think you should copy these as well.
The matching logic is already tested in bstring.c.

That being said, a single RUN line should be enough in this file.

91–94 ↗

(On Diff #412391)

[phyBrackets]

clang/test/Analysis/bstring_UninitRead.c

67–85 ↗

(On Diff #412391)

I'm not able to run test successfully with single RUN ,

// RUN: -analyzer-checker=alpha.unix.cstring.UninitializedRead

[steakhal]

clang/test/Analysis/bstring_UninitRead.c

1–84 ↗

(On Diff #412391)

I was thinking about something like this.

[phyBrackets]

clang/test/Analysis/bstring_UninitRead.c

67–85 ↗

(On Diff #412391)

wait , I think I got this! Thanks

[phyBrackets]

Remove unneccesary RUN and some macros definitions

[steakhal]

The core checkers should be always enabled.

clang/test/Analysis/bstring_UninitRead.c

2 ↗

(On Diff #412452)

[phyBrackets]

enabled the core checker

[phyBrackets]

clang/test/Analysis/bstring_UninitRead.c

2 ↗

(On Diff #412452)

Yeah done! Thanks

[phyBrackets]

@steakhal , if everything looks fine, can i land this ?

[steakhal]

Yup, land it!

[phyBrackets]

https://github.com/llvm/llvm-project/commit/bd1917c88a32c0930864d04f4e71155dcc3fa592 , Hey @steakhal , I land it but why it is not showing the

  void emitUninitializedReadBug(CheckerContext &C, ProgramStateRef State,
                             const Expr *E) const;
``` ?

[ymandel]

Looks like this broke the build. I'm getting:

FAILED: tools/clang/lib/StaticAnalyzer/Checkers/CMakeFiles/obj.clangStaticAnalyzerCheckers.dir/CStringChecker.cpp.o
/usr/bin/clang++-11 ... -std=c++14 -MD -MT tools/clang/lib/StaticAnalyzer/Checkers/CMakeFiles/obj.clangStaticAnalyzerCheckers.dir/CStringChecker.cpp.o -MF tools/clang/lib/StaticAnalyzer/Checkers/CMakeFiles/obj.clangStaticAnalyzerCheckers.dir/CStringChecker.cpp.o.d -o tools/clang/lib/StaticAnalyzer/Checkers/CMakeFiles/obj.clangStaticAnalyzerCheckers.dir/CStringChecker.cpp.o -c .../llvm-project/clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp
.../llvm-project/clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp:376:7: error: use of undeclared identifier 'emitUninitializedReadBug'
      emitUninitializedReadBug(C, StInBound, Buffer.Expression);
      ^
/usr/local/.../llvm-project/clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp:592:22: error: out-of-line definition of 'emitUninitializedReadBug' does not match any declaration in '(anonymous namespace)::CStringChecker'
void CStringChecker::emitUninitializedReadBug(CheckerContext &C,
                     ^~~~~~~~~~~~~~~~~~~~~~~~
2 errors generated.
FAILED: tools/clang/lib/StaticAnalyzer/Checkers/CMakeFiles/obj.clangStaticAnalyzerCheckers.dir/CStringChecker.cpp.o
/usr/bin/clang++-11 ... -std=c++14 -MD -MT tools/clang/lib/StaticAnalyzer/Checkers/CMakeFiles/obj.clangStaticAnalyzerCheckers.dir/CStringChecker.cpp.o -MF tools/clang/lib/StaticAnalyzer/Checkers/CMakeFiles/obj.clangStaticAnalyzerCheckers.dir/CStringChecker.cpp.o.d -o tools/clang/lib/StaticAnalyzer/Checkers/CMakeFiles/obj.clangStaticAnalyzerCheckers.dir/CStringChecker.cpp.o -c .../llvm-project/clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp
.../llvm-project/clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp:376:7: error: use of undeclared identifier 'emitUninitializedReadBug'
      emitUninitializedReadBug(C, StInBound, Buffer.Expression);
      ^
.../llvm-project/clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp:592:22: error: out-of-line definition of 'emitUninitializedReadBug' does not match any declaration in '(anonymous namespace)::CStringChecker'
void CStringChecker::emitUninitializedReadBug(CheckerContext &C,
                     ^~~~~~~~~~~~~~~~~~~~~~~~
2 errors generated.

[ronlieb]

broke our hip buildbot as well.

https://lab.llvm.org/buildbot/#/builders/165/builds/17076

[dyung]

And the PS4 build bots:

https://lab.llvm.org/buildbot/#/builders/139/builds/18001
https://lab.llvm.org/buildbot/#/builders/216/builds/801

[ymandel]

Can you rollback until a fix is found?

[shafik]

Looks like it also broke lldb green dragon incremental as well: https://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/41865/consoleFull#-27141295349ba4694-19c4-4d7e-bec5-911270d8a58c

[dyung]

Thanks for fixing the problem with the original commit, but in the future, if you make follow-up commits, can you change the commit message to reflect what the commit contains? Having three different commits with the exact same commit message can be very confusing.

[steakhal]

I would recommend committing changes in the morning, to give some time for the bots to chew through your commit. This way you could react to breakages and revert if needed.

[martong]

Maybe it is not too late to update the clang/docs/ReleaseNotes.rst? A new checker is certainly important for the users. Many thanks!

[phyBrackets]

In D120489#3493313, @martong wrote:

Maybe it is not too late to update the clang/docs/ReleaseNotes.rst? A new checker is certainly important for the users. Many thanks!

Yeah done! Thanks.

clang/docs/analyzer/checkers.rst

  }
 
 .. _alpha-unix-cstring-OutOfBounds:
 
 alpha.unix.cstring.OutOfBounds (C)
 """"""""""""""""""""""""""""""""""
 Check for out-of-bounds access in string functions; applies to:`` strncopy, strncat``.
 
-
 .. code-block:: c
 
  void test() {
    int y = strlen((char *)&test); // warn
  }
 
+.. _alpha-unix-cstring-UninitializedRead:
+
+alpha.unix.cstring.UninitializedRead (C)
+""""""""""""""""""""""""""""""""""""""""
+Check for uninitialized reads from common memory copy/manipulation functions such as:
+ ``memcpy, mempcpy, memmove, memcmp, strcmp, strncmp, strcpy, strlen, strsep`` and many more.
+
+.. code-block:: c 
+
+ void test() {
+  char src[10];
+  char dst[5];
+  memcpy(dst,src,sizeof(dst)); // warn: Bytes string function accesses uninitialized/garbage values
+ }
+
+Limitations:
+ 
+  Due to limitations of the memory modeling in the analyzer, one can likely
+  observe a lot of false-positive reports like this:
+  
+     .. code-block:: c
+
+     void false_positive() {
+      int src[] = {1, 2, 3, 4};
+        int dst[5] = {0};
+        memcpy(dst, src, 4 * sizeof(int)); // false-positive:
+         // The 'src' buffer was correctly initialized, yet we cannot conclude
+        // that since the analyzer could not see a direct initialization of the
+       // very last byte of the source buffer.
+       }
+
+    More details at the corresponding `GitHub issue <https://github.com/llvm/llvm-project/issues/43459>`_.
+
 .. _alpha-nondeterminism-PointerIteration:
 
 alpha.nondeterminism.PointerIteration (C++)
 """""""""""""""""""""""""""""""""""""""""""
 Check for non-determinism caused by iterating unordered containers of pointers.
 
 .. code-block:: c
 

clang/include/clang/StaticAnalyzer/Checkers/Checkers.td

def CStringBufferOverlap : Checker<"BufferOverlap">,
   HelpText<"Checks for overlap in two buffer arguments">,
   Dependencies<[CStringModeling]>,
   Documentation<HasAlphaDocumentation>;
 
 def CStringNotNullTerm : Checker<"NotNullTerminated">,
   HelpText<"Check for arguments which are not null-terminating strings">,
   Dependencies<[CStringModeling]>,
   Documentation<HasAlphaDocumentation>;
  
+def CStringUninitializedRead : Checker<"UninitializedRead">,
+  HelpText<"Checks if the string manipulation function would read uninitialized bytes">,
+  Dependencies<[CStringModeling]>,
+  Documentation<HasAlphaDocumentation>;
+  
 } // end "alpha.unix.cstring"
 
 let ParentPackage = Unix in {
 
 def UnixAPIMisuseChecker : Checker<"API">,
   HelpText<"Check calls to various UNIX/Posix functions">,
   Documentation<HasDocumentation>;
 

clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp

 enum class ConcatFnKind { none = 0, strcat = 1, strlcat = 2 };
 class CStringChecker : public Checker< eval::Call,
                                          check::PreStmt<DeclStmt>,
                                          check::LiveSymbols,
                                          check::DeadSymbols,
                                          check::RegionChanges
                                          > {
   mutable std::unique_ptr<BugType> BT_Null, BT_Bounds, BT_Overlap,
-      BT_NotCString, BT_AdditionOverflow;
+      BT_NotCString, BT_AdditionOverflow, BT_UninitRead;
 
   mutable const char *CurrentFunctionDescription;
 
 public:
   /// The filter is used to filter out the diagnostics which are not enabled by
   /// the user.
   struct CStringChecksFilter {
     DefaultBool CheckCStringNullArg;
     DefaultBool CheckCStringOutOfBounds;
     DefaultBool CheckCStringBufferOverlap;
     DefaultBool CheckCStringNotNullTerm;
+    DefaultBool CheckCStringUninitializedRead;
 
     CheckerNameRef CheckNameCStringNullArg;
     CheckerNameRef CheckNameCStringOutOfBounds;
     CheckerNameRef CheckNameCStringBufferOverlap;
     CheckerNameRef CheckNameCStringNotNullTerm;
+    CheckerNameRef CheckNameCStringUninitializedRead;
   };
 
   CStringChecksFilter Filter;
 
   static void *getTag() { static int tag; return &tag; }
 
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
   void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
public:
 
   void emitNullArgBug(CheckerContext &C, ProgramStateRef State, const Stmt *S,
                       StringRef WarningMsg) const;
   void emitOutOfBoundsBug(CheckerContext &C, ProgramStateRef State,
                           const Stmt *S, StringRef WarningMsg) const;
   void emitNotCStringBug(CheckerContext &C, ProgramStateRef State,
                          const Stmt *S, StringRef WarningMsg) const;
   void emitAdditionOverflowBug(CheckerContext &C, ProgramStateRef State) const;
+  void emitUninitializedReadBug(CheckerContext &C, ProgramStateRef State,
+                                const Expr *E) const;
 
   ProgramStateRef checkAdditionOverflow(CheckerContext &C,
                                             ProgramStateRef state,
                                             NonLoc left,
                                             NonLoc right) const;
 
   // Return true if the destination buffer of the copy function may be in bound.
   // Expects SVal of Size to be positive and unsigned.
if (StOutBound && !StInBound) {
 
     // Emit a bug report.
     ErrorMessage Message =
         createOutOfBoundErrorMsg(CurrentFunctionDescription, Access);
     emitOutOfBoundsBug(C, StOutBound, Buffer.Expression, Message);
     return nullptr;
   }
 
+  // Ensure that we wouldn't read uninitialized value.
+  if (Access == AccessKind::read) {
+    if (StInBound->getSVal(ER).isUndef()) {
+      emitUninitializedReadBug(C, StInBound, Buffer.Expression);
+      return nullptr;
+    }
+  }
+
   // Array bound check succeeded.  From this point forward the array bound
   // should always succeed.
   return StInBound;
 }
 
 ProgramStateRef CStringChecker::CheckBufferAccess(CheckerContext &C,
                                                   ProgramStateRef State,
                                                   AnyArgExpr Buffer,
ProgramStateRef CStringChecker::CheckBufferAccess(CheckerContext &C,
   // Check that the first buffer is sufficiently long.
   SVal BufStart =
       svalBuilder.evalCast(BufVal, PtrTy, Buffer.Expression->getType());
   if (Optional<Loc> BufLoc = BufStart.getAs<Loc>()) {
 
     SVal BufEnd =
         svalBuilder.evalBinOpLN(State, BO_Add, *BufLoc, LastOffset, PtrTy);
 
+    State = CheckLocation(C, State, Buffer, BufStart, Access);
     State = CheckLocation(C, State, Buffer, BufEnd, Access);
 
     // If the buffer isn't large enough, abort.
     if (!State)
       return nullptr;
   }
 
   // Large enough or not, return this state!
if (ExplodedNode *N = C.generateErrorNode(State)) {
     auto Report = std::make_unique<PathSensitiveBugReport>(*BT, WarningMsg, N);
     Report->addRange(S->getSourceRange());
     if (const auto *Ex = dyn_cast<Expr>(S))
       bugreporter::trackExpressionValue(N, Ex, *Report);
     C.emitReport(std::move(Report));
   }
 }
 
+void CStringChecker::emitUninitializedReadBug(CheckerContext &C,
+                                              ProgramStateRef State,
+                                              const Expr *E) const {
+  if (ExplodedNode *N = C.generateErrorNode(State)) {
+    const char *Msg =
+        "Bytes string function accesses uninitialized/garbage values";
+    if (!BT_UninitRead)
+      BT_UninitRead.reset(
+          new BuiltinBug(Filter.CheckNameCStringUninitializedRead,
+                         "Accessing unitialized/garbage values", Msg));
+
+    BuiltinBug *BT = static_cast<BuiltinBug *>(BT_UninitRead.get());
+
+    auto Report = std::make_unique<PathSensitiveBugReport>(*BT, Msg, N);
+    Report->addRange(E->getSourceRange());
+    bugreporter::trackExpressionValue(N, E, *Report);
+    C.emitReport(std::move(Report));
+  }
+}
+
 void CStringChecker::emitOutOfBoundsBug(CheckerContext &C,
                                         ProgramStateRef State, const Stmt *S,
                                         StringRef WarningMsg) const {
   if (ExplodedNode *N = C.generateErrorNode(State)) {
     if (!BT_Bounds)
       BT_Bounds.reset(new BuiltinBug(
           Filter.CheckCStringOutOfBounds ? Filter.CheckNameCStringOutOfBounds
                                          : Filter.CheckNameCStringNullArg,
#define REGISTER_CHECKER(name)                                                 \
   }                                                                            \
                                                                                \
   bool ento::shouldRegister##name(const CheckerManager &mgr) { return true; }
 
 REGISTER_CHECKER(CStringNullArg)
 REGISTER_CHECKER(CStringOutOfBounds)
 REGISTER_CHECKER(CStringBufferOverlap)
 REGISTER_CHECKER(CStringNotNullTerm)
+REGISTER_CHECKER(CStringUninitializedRead)
 No newline at end of file

clang/test/Analysis/bstring.c

 
 #else /* VARIANT */
 
 #define memcpy BUILTIN(memcpy)
 void *memcpy(void *restrict s1, const void *restrict s2, size_t n);
 
 #endif /* VARIANT */
 
+void top(char *dst) {
+  char buf[10];
+  memcpy(dst, buf, 10); // expected-warning{{Bytes string function accesses uninitialized/garbage values}}
+  (void)buf;
+}
 
 void memcpy0 () {
   char src[] = {1, 2, 3, 4};
   char dst[4] = {0};
 
   memcpy(dst, src, 4); // no-warning
 
   clang_analyzer_eval(memcpy(dst, src, 4) == dst); // expected-warning{{TRUE}}
void mempcpy12() {
   mempcpy(0, a, 0); // no-warning
 }
 
 void mempcpy13() {
   char a[4] = {0};
   mempcpy(a, 0, 0); // no-warning
 }
 
 void mempcpy14() {
   int src[] = {1, 2, 3, 4};
   int dst[5] = {0};
   int *p;
 
-  p = mempcpy(dst, src, 4 * sizeof(int));
+  p = mempcpy(dst, src, 4 * sizeof(int)); // expected-warning{{Bytes string function accesses uninitialized/garbage values}}
+  // FIXME: This behaviour is actually Unexpected and needs to be fix, 
+  // mempcpy seems to consider the src buffered byte as uninitialized
+  // and returning undef which is actually not the case It should return something like Unknown .
 
-  clang_analyzer_eval(p == &dst[4]); // expected-warning{{TRUE}}
+  clang_analyzer_eval(p == &dst[4]); // no-warning (above is fatal)
 }
 
 struct st {
   int i;
   int j;
 };
 
 void mempcpy15() {
   struct st s1 = {0};
   struct st s2;
   struct st *p1;
   struct st *p2;
 
   p1 = (&s2) + 1;
-  p2 = mempcpy(&s2, &s1, sizeof(struct st));
+  p2 = mempcpy(&s2, &s1, sizeof(struct st)); // expected-warning{{Bytes string function accesses uninitialized/garbage values}}
+  // FIXME: It seems same as mempcpy14() case.
   
-  clang_analyzer_eval(p1 == p2); // expected-warning{{TRUE}}
+  clang_analyzer_eval(p1 == p2); // no-warning (above is fatal)
 }
 
 void mempcpy16() {
   struct st s1[10] = {{0}};
   struct st s2[10];
   struct st *p1;
   struct st *p2;