[analyzer] Don't escape local static memregions on bind

[steakhal]

Summary

When the engine processes a store to a variable, it will eventually call
ExprEngine::processPointerEscapedOnBind(). This function is supposed to
invalidate (put the given locations to an escape list) the locations
which we cannot reason about.

Unfortunately, local static variables are also put into this list.

This patch relaxes the guard condition, so that beyond stack variables,
static local variables are also ignored.

[NoQ]

clang/test/Analysis/malloc-static-storage.cpp

34–39

The main problem with static locals is that this can happen the other way round:

void malloc_escape() {
  static int *p;
  escape(p);
  p = (int *)malloc(sizeof(int));
  p = 0; // no-leak
}

[NoQ]

clang/test/Analysis/malloc-static-storage.cpp

34–39

Wait, I misread. I'm thinking of a situation like this:

void malloc_escape() {
  static int *p;
  escape(&p); // added '&'
  p = (int *)malloc(sizeof(int));
  p = 0; // no-leak
}

[NoQ]

clang/test/Analysis/malloc-static-storage.cpp

34–39

Technically this is also a problem with non-static locals if we complicate the situation a little bit:

void malloc_escape() {
  int *p;
  escape(&p);
  p = (int *)malloc(sizeof(int));
  free_whatever_escaped();
  p = 0; // currently false leak warning
}

We've had a lovely conversation about this with @xazax.hun in D71041 and D71224 but we've failed to produce a good solution back then.

[NoQ]

Ok screw it, my static example is still broken. There's technically still a leak in it because there's no time for the other code to kick in between p = (int *)malloc(sizeof(int)); and p = 0; to read the value from p.

But in practice there could be a lot of things going on in between, that with your patch might not trigger enough escapes. Let me disconnect from the original test case and try to build a few examples more carefully.

void foo() {
  static int *p;
  escape(&p);
  p = malloc(sizeof(int));
  free_whatever_escaped();
  p = 0; // no-leak
}

This isn't a leak, regardless of whether the variable is static or not. Currently we display a leak when the variable is non-static (bad) but don't display a leak when the variable is static (good). IIUC your patch might break this. The important part is that in this case there's no direct connection between the tracked pointer p and the escaped region &p because p isn't stored in &p until the next line. So if you remove invalidation of p on free_whatever_escaped();, it'll cause a new false positive in the static case.

void foo(cond) {
  static int *p;
  if (cond) {
    p = malloc(sizeof(int));
    free_whatever_escaped();
    p = 0; // no-leak
  }
  escape(&p);
}

In this case there's no leak as long as the first invocation of the function always has cond set to false. In this case, again, there's no direct connection between &p and the return value of malloc() when direct escape of &p happens. On top of that, the direct escape of &p isn't observed at all until much later in the analysis. But just because the local is static, and the function can be called multiple times, the escape at the end of the analysis may "affect" our decision-making at the beginning of the analysis. I suspect your patch breaks this example as well.

So basically in order to do the right thing here, you need to make sure there are no direct escapes of that static variable *anywhere* in the function. But as long as there's no direct escapes, you're probably good to go. With non-static locals you only need to observe escapes *before* the leak (but possibly before the allocation as well), which we currently don't do a good job at anyway.

Then, again, it's possible that your patch improves FP rates than what we currently have, just by being a different trade-off, given how artificial my examples are, but we'll need some data to figure it out.

[steakhal]

Finally, I had some time to come back to this.
Thanks for taking the time for such a detailed response, kudos! @NoQ

In D139534#3999455, @NoQ wrote:

Ok screw it, my static example is still broken. There's technically still a leak in it because there's no time for the other code to kick in between p = (int *)malloc(sizeof(int)); and p = 0; to read the value from p.

But in practice there could be a lot of things going on in between, that with your patch might not trigger enough escapes. Let me disconnect from the original test case and try to build a few examples more carefully.

void foo() {
  static int *p;
  escape(&p);
  p = malloc(sizeof(int));
  free_whatever_escaped();
  p = 0; // no-leak
}

This isn't a leak, regardless of whether the variable is static or not. Currently we display a leak when the variable is non-static (bad) but don't display a leak when the variable is static (good). IIUC your patch might break this. The important part is that in this case there's no direct connection between the tracked pointer p and the escaped region &p because p isn't stored in &p until the next line. So if you remove invalidation of p on free_whatever_escaped();, it'll cause a new false positive in the static case.

Yes, I'd introduce FP for this case.

void foo(cond) {
  static int *p;
  if (cond) {
    p = malloc(sizeof(int));
    free_whatever_escaped();
    p = 0; // no-leak
  }
  escape(&p);
}

In this case there's no leak as long as the first invocation of the function always has cond set to false. In this case, again, there's no direct connection between &p and the return value of malloc() when direct escape of &p happens. On top of that, the direct escape of &p isn't observed at all until much later in the analysis. But just because the local is static, and the function can be called multiple times, the escape at the end of the analysis may "affect" our decision-making at the beginning of the analysis. I suspect your patch breaks this example as well.

Yes, we will report a FP there with my patch.

So basically in order to do the right thing here, you need to make sure there are no direct escapes of that static variable *anywhere* in the function. But as long as there's no direct escapes, you're probably good to go. With non-static locals you only need to observe escapes *before* the leak (but possibly before the allocation as well), which we currently don't do a good job at anyway.

I agree that we could improve escape handling of static variables by checking if that could have escaped *anywhere*. Although, I don't plan to invest time there.

Then, again, it's possible that your patch improves FP rates than what we currently have, just by being a different trade-off, given how artificial my examples are, but we'll need some data to figure it out.

According to my differential analysis, I saw only 2 new issues and 1 disappearing issue.
The test corpus includes roughly 170 projects, including really big ones; windows, Linux, old, new, C and C++ projects as well.
Also, note that we are not using the default set of checks, nor the cc1 driver.

The two new issues were both TPs, for memory leaks. I'll elaborate on these later.
I haven't investigated the single disappearing issue, which was about The right operand of '<' is a garbage value. In the context, I could see some local static variables though.

---

Here is the gist of one *new* TP:

// OpenJDK src/java.base/unix/native/libjava/java_props_md.c
#define NULL ((void*)0)
typedef unsigned int uid_t;
extern struct passwd *getpwuid(uid_t uid);
extern uid_t getuid();
extern char *strdup(const char *s);
extern char *getenv(const char *name);
struct passwd {
  char *pw_dir;
};

typedef struct {
  char *user_home;
} java_props_t;

java_props_t *GetJavaProperties(struct JNIEnv *env) {
  static java_props_t sprops;

  struct passwd *pwent = getpwuid(getuid());
  sprops.user_home = pwent ? strdup(pwent->pw_dir) : NULL; // taking 'true' branch; allocating memory by 'strdup'
  if (sprops.user_home == NULL || sprops.user_home[0] == '\0' ||
      sprops.user_home[1] == '\0') {
    char *user_home = getenv("HOME");
    if ((user_home != NULL) && (user_home[0] != '\0'))
      sprops.user_home = user_home; // leaking previous `sprops.user_home` !
  }
}

The other TP in the Samba project looks quite similar but involves a loop complicating things.

---

By looking at the results, I think my patch helps more than hinders, and I'm also not expecting many users severely impacted by this change.

clang/test/Analysis/malloc-static-storage.cpp

34–39

Awesome xref. I'll read it. Thanks!

[steakhal]

• Add two test cases demonstrating the false-positives this patch will introduce. These are semantically equivalent to the one mentioned in the comments by @NoQ.

[steakhal]

Let me know if you have further concerns. @xazax.hun @NoQ

[xazax.hun]

Sorry, I got a bit swamped, will try to take a look next week. In the meantime, did you have a chance to run this over some open source projects? Did you find any interesting diffs?

[steakhal]

In D139534#4029097, @xazax.hun wrote:

Sorry, I got a bit swamped, will try to take a look next week. In the meantime, did you have a chance to run this over some open source projects? Did you find any interesting diffs?

Yea I did. Check my response to Artem. I no longer have the results, but the diff was surprisingly small. However, I feel confident about the measurment itself.

Thanks for your time. You don't need to rush.

[xazax.hun]

Here is the gist of one *new* TP:

Where would sprops get escaped? Did I miss that or was that reduced out of the example?

Overall, this looks like a hard nut to crack. Escaping too much or too little are both problematic, and we don't have the information we need to make the decision. The question is whether we want to make an absolute decision or come up with a heuristic like:

static int* p;
MyStruct reachable(&p);

indirect(&reachable);
direct(&p);

escaping when direct is called, but not escaping when indirect is called.

Do you see any patterns in the real-world results that would show a pattern? I am not opposed to making a change, but I wonder if we should start documenting these decisions somewhere that are likely need revision in the future when we have more data. What do you think?

[steakhal]

In D139534#4034719, @xazax.hun wrote:

Here is the gist of one *new* TP:

Where would sprops get escaped? Did I miss that or was that reduced out of the example?

You are right, it 'never' escapes, yet in the past we modelled all stores to local statics as an 'immediate escape'.
This is what I think we should not do. And this is what this patch removes.

Overall, this looks like a hard nut to crack. Escaping too much or too little are both problematic, and we don't have the information we need to make the decision. The question is whether we want to make an absolute decision or come up with a heuristic like:

static int* p;
MyStruct reachable(&p);

indirect(&reachable);
direct(&p);

escaping when direct is called, but not escaping when indirect is called.

Do you see any patterns in the real-world results that would show a pattern? I am not opposed to making a change, but I wonder if we should start documenting these decisions somewhere that are likely need revision in the future when we have more data. What do you think?

I've seen only those 3 diffs: 2 new 1 absent issues. But there could be projects which make use of local static variables a lot. It was the case with one of our customers, but I cannot comment on that. I could somehow find open-source projects affected, but I'm not sure if it would be easy unless you have projects in mind.

[xazax.hun]

In D139534#4036783, @steakhal wrote:

In D139534#4034719, @xazax.hun wrote:

Here is the gist of one *new* TP:

Where would sprops get escaped? Did I miss that or was that reduced out of the example?

You are right, it 'never' escapes, yet in the past we modelled all stores to local statics as an 'immediate escape'.
This is what I think we should not do. And this is what this patch removes.

Oh, now I understand. Yeah, I guess the idea was that we only have escape information for the current path, but the static's address might have escaped in another path that we did not process. Overall, I think those cases should be rare, so I do support this change.

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

 ProgramStateRef ExprEngine::processPointerEscapedOnBind(
     ProgramStateRef State, ArrayRef<std::pair<SVal, SVal>> LocAndVals,
     const LocationContext *LCtx, PointerEscapeKind Kind,
     const CallEvent *Call) {
   SmallVector<SVal, 8> Escaped;
   for (const std::pair<SVal, SVal> &LocAndVal : LocAndVals) {
     // Cases (1) and (2).
     const MemRegion *MR = LocAndVal.first.getAsRegion();
-    if (!MR || !MR->hasStackStorage()) {
+    if (!MR ||
+        !isa<StackSpaceRegion, StaticGlobalSpaceRegion>(MR->getMemorySpace())) {
       Escaped.push_back(LocAndVal.second);
       continue;
     }
 
     // Case (3).
     if (const auto *VR = dyn_cast<VarRegion>(MR->getBaseRegion()))
       if (VR->hasStackParametersStorage() && VR->getStackFrame()->inTopFrame())
         if (const auto *RD = VR->getValueType()->getAsCXXRecordDecl())

clang/test/Analysis/malloc-static-storage.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix.Malloc -verify %s
+
+typedef __typeof(sizeof(int)) size_t;
+void* malloc(size_t size);
+void *calloc(size_t num, size_t size);
+void free(void * ptr);
+
+void escape(void *);
+void next_statement();
+
+void conditional_malloc(bool coin) {
+  static int *p;
+
+  if (coin) {
+    p = (int *)malloc(sizeof(int));
+  }
+  p = 0; // Pointee of 'p' dies, which is recognized at the next statement.
+  next_statement(); // expected-warning {{Potential memory leak}}
+}
+
+void malloc_twice() {
+  static int *p;
+  p = (int *)malloc(sizeof(int));
+  next_statement();
+  p = (int *)malloc(sizeof(int));
+  next_statement(); // expected-warning {{Potential memory leak}}
+  p = 0;
+  next_statement(); // expected-warning {{Potential memory leak}}
+}
+
+void malloc_escape() {
+  static int *p;
+  p = (int *)malloc(sizeof(int));
+  escape(p); // no-leak
+  p = 0; // no-leak
+}
+
+void free_whatever_escaped();
+void malloc_escape_reversed() {
+  static int *p;
+  escape(&p);
+  p = (int *)malloc(sizeof(int));
+  free_whatever_escaped();
+  p = 0; // FIXME: We should not report a leak here.
+  next_statement(); // expected-warning {{Potential memory leak}}
+}
+
+int *malloc_return_static() {
+  static int *p = (int *)malloc(sizeof(int));
+  return p; // no-leak
+}
+
+int malloc_unreachable(int rng) {
+  // 'p' does not escape and never freed :(
+  static int *p;
+
+  // For the second invocation of this function, we leak the previous pointer.
+  // FIXME: We should catch this at some point.
+  p = (int *)malloc(sizeof(int));
+  *p = 0;
+
+  if (rng > 0)
+    *p = rng;
+
+  return *p; // FIXME: We just leaked 'p'. We should warn about this.
+}
+
+void malloc_cond(bool cond) {
+  static int *p;
+  if (cond) {
+    p = (int*)malloc(sizeof(int));
+    free_whatever_escaped();
+    p = 0; // FIXME: We should not report a leak here.
+    next_statement(); // expected-warning {{Potential memory leak}}
+  }
+  escape(&p);
+}