[Patch] [Analyzer] BugReporter.cpp:2869: Assertion failed: !RemainingNodes.empty() && "No error node found in the trimmed graph" (PR 24184)

[MaggieYi]

Summary

Dear All,

I would like to propose a patch to solve an assertion failure reported by Dmitry in https://llvm.org/bugs/show_bug.cgi?id=24184.

The assertion is caused by reusing a “filler” ExplodedNode as an error node. The “filler” nodes are only used for intermediate processing and are not essential for analyzer history, so they can be reclaimed when the ExplodedGraph is trimmed by the “collectNode” function. When a checker finds a bug, they generate a new transition in the ExplodedGraph. The analyzer will try to reuse the existing predecessor node. If it cannot, it creates a new ExplodedNode, which always has a tag to uniquely identify the creation site. The assertion is caused when the analyzer reuses a “filler” node.

In the test case, some “filler” nodes were reused and then reclaimed later when the ExplodedGraph was trimmed. This caused an assertion because the node was needed to generate the report. The “filler” nodes should not be reused as error nodes. The patch adds a constraint to prevent this happening, which solves the problem and makes the test cases pass.

Please let me know if this is an acceptable patch.

Regards,

Ying Yi
SN Systems Ltd - Sony Computer Entertainment Group.

[zaks.anna]

I have some minor nits but looks good otherwise. Thanks for fixing this!

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

290–293

Please, remove the reference to the method name, the comment might get stale if the function name changes. Also, please, remove the PR reference from here.

test/Analysis/malloc.c

1389–1390

Some wordsmithing: Object "a->p" is returned after being freed by calling "realloc".

[MaggieYi]

Hi Anna,

Many thanks for your comments. I have modified the patch to address your comments. Please let me know what you think.

PS: If the updated patch looks good to you, could you please commit it for me (as I do not have commit access) ?

Many thanks,
Ying Yi

[MaggieYi]

Ping

[xazax.hun]

Committed in http://reviews.llvm.org/rL246188.

Thanks for the patch.

[MaggieYi]

Thanks for helping me review and submit the patch.

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

public:
   /// \sa clang::Lexer::getSpelling(), clang::Lexer::getImmediateMacroName().
   StringRef getMacroNameOrSpelling(SourceLocation &Loc);
 
 private:
   ExplodedNode *addTransitionImpl(ProgramStateRef State,
                                  bool MarkAsSink,
                                  ExplodedNode *P = nullptr,
                                  const ProgramPointTag *Tag = nullptr) {
-    if (!State || (State == Pred->getState() && !Tag && !MarkAsSink))
+    // It may not be safe to use the "Pred" node with no tag because the "Pred"
+    // node may be recycled in the reclamation function.
+    if (!State || (State == Pred->getState() && !Tag && !MarkAsSink &&
+                   Pred->getLocation().getTag()))
       return Pred;
 
     Changed = true;
     const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
     if (!P)
       P = Pred;
 
     ExplodedNode *node;

test/Analysis/PR24184.cpp

+// RUN: %clang_cc1 -w -analyze -analyzer-eagerly-assume -fcxx-exceptions -analyzer-checker=core -analyzer-checker=alpha.core.PointerArithm,alpha.core.CastToStruct -analyzer-max-loop 64 -verify %s
+// RUN: %clang_cc1 -w -analyze -analyzer-checker=core -analyzer-checker=cplusplus -fcxx-exceptions -analyzer-checker alpha.core.PointerArithm,alpha.core.CastToStruct -analyzer-max-loop 63 -verify %s
+
+// These tests used to hit an assertion in the bug report. Test case from http://llvm.org/PR24184.
+typedef struct {
+  int cbData;
+  unsigned pbData;
+} CRYPT_DATA_BLOB;
+
+typedef enum { DT_NONCE_FIXED } DATA_TYPE;
+int a;
+typedef int *vcreate_t(int *, DATA_TYPE, int, int);
+void fn1(unsigned, unsigned) {
+  char b = 0;
+  for (; 1; a++, &b + a * 0) // expected-warning{{Pointer arithmetic done on non-array variables means reliance on memory layout, which is dangerous}}
+    ;
+}
+
+vcreate_t fn2;
+struct A {
+  CRYPT_DATA_BLOB value;
+  int m_fn1() {
+    int c;
+    value.pbData == 0;
+    fn1(0, 0);
+  }
+};
+struct B {
+  A IkeHashAlg;
+  A IkeGType;
+  A NoncePhase1_r;
+};
+class C {
+  int m_fn2(B *);
+  void m_fn3(B *, int, int, int);
+};
+int C::m_fn2(B *p1) {
+  int *d;
+  int e = p1->IkeHashAlg.m_fn1();
+  unsigned f = p1->IkeGType.m_fn1(), h;
+  int g;
+  d = fn2(0, DT_NONCE_FIXED, (char)0, p1->NoncePhase1_r.value.cbData);
+  h = 0 | 0;
+  m_fn3(p1, 0, 0, 0);
+}
+
+// case 2:
+typedef struct {
+  int cbData;
+  unsigned char *pbData;
+} CRYPT_DATA_BLOB_1;
+typedef unsigned uint32_t;
+void fn1_1(void *p1, const void *p2) { p1 != p2; }
+
+void fn2_1(uint32_t *p1, unsigned char *p2, uint32_t p3) {
+  unsigned i = 0;
+  for (0; i < p3; i++)
+    fn1_1(p1 + i, p2 + i * 0);    // expected-warning{{Pointer arithmetic done on non-array variables means reliance on memory layout, which is dangerous}}
+}
+
+struct A_1 {
+  CRYPT_DATA_BLOB_1 value;
+  uint32_t m_fn1() {
+    uint32_t a;
+    if (value.pbData)
+      fn2_1(&a, value.pbData, value.cbData);
+    return 0;
+  }
+};
+struct {
+  A_1 HashAlgId;
+} *b;
+void fn3() {
+  uint32_t c, d;
+  d = b->HashAlgId.m_fn1();
+  d << 0 | 0 | 0;
+  c = 0;
+  0 | 1 << 0 | 0 && b;
+}
+
+// case 3:
+struct ST {
+  char c;
+};
+char *p;
+int foo1(ST);
+int foo2() {
+  ST *p1 = (ST *)(p);      // expected-warning{{Casting a non-structure type to a structure type and accessing a field can lead to memory access errors or data corruption}}
+  while (p1->c & 0x0F || p1->c & 0x07)
+    p1 = p1 + foo1(*p1);
+}
+
+int foo3(int *node) {
+  int i = foo2();
+  if (i)
+    return foo2();
+}
 No newline at end of file

test/Analysis/malloc.c

 struct HasPtr {
   char *p;
 };
 
 char* reallocButNoMalloc(struct HasPtr *a, int c, int size) {
   int *s;
   char *b = realloc(a->p, size);
   char *m = realloc(a->p, size); // expected-warning {{Attempt to free released memory}}
-  return a->p;
+  //PR24184: Object "a->p" is returned after being freed by calling "realloc".
+  return a->p; // expected-warning {{Use of memory after it is freed}}
 }
 
 // We should not warn in this case since the caller will presumably free a->p in all cases.
 int reallocButNoMallocPR13674(struct HasPtr *a, int c, int size) {
   int *s;
   char *b = realloc(a->p, size);
   if (b == 0)
     return -1;