This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Add InvalidPtrChecker
ClosedPublic

Authored by zukatsinadze on Mar 1 2021, 9:05 AM.

Details

Summary

This patch introduces a new checker: alpha.security.cert.env.InvalidPtr

Checker finds usage of invalidated pointers.

Based on the following SEI CERT Rules:
ENV34-C: https://wiki.sei.cmu.edu/confluence/x/8tYxBQ
ENV31-C: https://wiki.sei.cmu.edu/confluence/x/5NUxBQ

Diff Detail

Event Timeline

zukatsinadze created this revision.Mar 1 2021, 9:05 AM
zukatsinadze requested review of this revision.Mar 1 2021, 9:05 AM

Please suggest which package to use for the checker.
CERT rules are ENV, however, it deals with non-ENV functions as well.

Also, I am having a problem with checkDeadSymbols, it is similar to one xazax.hun faced here: http://reviews.llvm.org/D14203 (many many years ago)
envp memory region is marked dead too early in case of aliasing. Please check the snippets, the second one is problematic:

int main(int argc, char **argv, char *envp[]) {
  putenv((char*) "NAME=VALUE"); // envp invalidated
  envp[0]; // gives error
}

int main(int argc, char **argv, char *envp[]) {
  char **e = envp;
  putenv((char*) "NAME=VALUE"); // envp invalidated
  e[0]; // does not give error :(

  // warnOnDeadSymbol reports 'envp' dead here
} 

int main(int argc, char **argv, char *envp[]) {
  char **e = envp;
  putenv((char*) "NAME=VALUE"); // envp invalidated
  e[0]; // gives error again

  /*
    use 'envp' somehow here
  */
}

Fixed docs.

Attaching results of CodeChecker run on some projects.

Removed code repetition from the tests.

NoQ added a comment.Mar 3 2021, 5:19 PM

CERT rules are typically very vague and don't map nicely into specific static analysis algorithms. A lot of CERT rules flag valid code as well as bugs. I want you to explain what *exactly* does the checker checks (say, in the form of a state machine, i.e. what sequences of events in the program does it find) and whether flagged code is expected to be always invalid.

// warnOnDeadSymbol reports 'envp' dead here

If it reports the symbol as dead after the warning would have been emitted then the problem must be elsewhere. There must be other differences in the analysis *before* the buggy statement. Nothing that happens after the buggy statement should ever matter.

Also the behavior of checkDeadSymbols looks correct here, I don't see any problems from your description. The symbol is reported dead when there's a guarantee that it won't be encountered anymore during analysis. If the parameter variable and the aliasing variable aren't used anymore and the symbol isn't stored anywhere else then the symbol is correctly marked as dead.

Why are you even tracking reg_$0<envp>? It's obvious from the structure of the symbol that it's an environment pointer, there's no need to keep it in maps.

clang/docs/analyzer/checkers.rst
2103–2104

It's very important to explain whether the "unanticipated behavior" is an entirely psychological concept ("most people don't understand how this works but this can occasionally also be a valid solution if you know what you're doing") or a 100% clear indication of a bug ("such code can never be correct", eg. it instantly causes undefined behavior, or the written value can never be read later so there's absolutely no point in writing it, or something like that).

@NoQ, thanks for the comments.

In D97699#2601804, @NoQ wrote:

... and whether flagged code is expected to be always invalid.

C standard says "may be overwritten", so I guess it's undefined behavior.

In D97699#2601804, @NoQ wrote:

... I want you to explain what *exactly* does the checker checks ...

There are two problems that are checked.
First: if we have 'envp' argument of main present and we modify the environment in some way (say setenv, putenv...), it "may" reallocate the whole environment memory, but 'envp' will still point to the old location.
Second: if we have a pointer pointing to the result of 'getenv' (and some other non-reentrant functions, there are 5 of them implemented now, but can be easily extended to others, since checker is general enough) and we call 'getenv' again the previous result "may" be overwritten.
The idea of the checker is simple and somewhat comparable to MallocChecker or UseAfterFree (in a sense that 'free' invalidates region). We have a map of previous function call results and after a subsequent call, we invalidate the previous region. And we warn on dereference of such pointer or if we have it as an argument to function call (to avoid some false negatives), which is not inlined.
I will add a description in a checker file.

And about checkDeadSymbols, I get your point, but I am interested why checker has different behavior on these two examples:

int main(int argc, char **argv, char *envp[]) {
  putenv((char*) "NAME=VALUE"); // envp invalidated
  envp[0]; // gives error
}
int main(int argc, char **argv, char *envp[]) {
  char **e = envp;
  putenv((char*) "NAME=VALUE"); // envp invalidated
  e[0]; // does not give error
}

If I manually force keeping envp region in state when I check if (!SymReaper.isLiveRegion(E)) { , then it reports as expected.

In D97699#2601804, @NoQ wrote:

Why are you even tracking reg_$0<envp>? It's obvious from the structure of the symbol that it's an environment pointer, there's no need to keep it in maps.

envp is confusable with argv: int main(int argc, char *argv[], char *envp[]) so we obtain envp's region from main() to match it later.

clang/docs/analyzer/checkers.rst
2103–2104

The standard terminology is very vague, like that:

The getenv function returns a pointer to a string associated with the matched list member. The string pointed to shall not be modified by the program but may be overwritten by a subsequent call to the getenv function.

What the hell. 😕 I think it is about table-doubling and reallocating the entire environment pointer table at some point which makes sense in case of the non-getter function calls. For the getters I think another processes could overwrite the environ pointer between two getter calls and problem could occur because of such table-doubling. To resolve the issue we need to call strdup() and create a copy of the current environment entry instead of having a pointer to it as I see.

@zukatsinadze it would be great to see a real reference with real issues in real world software. Is the true evil the multiple chained getter calls?

zukatsinadze added inline comments.Mar 21 2021, 5:16 PM
clang/docs/analyzer/checkers.rst
2103–2104

it would be great to see a real reference with real issues in real world software

I've attached some results up in the thread. Checker gave several valuable reports on several projects if that's what you mean.

Is the true evil the multiple chained getter calls?

Besides SEI CERT, there are many other reputable resources stating the same problem with getenv.

https://www.ibm.com/support/knowledgecenter/SSLTBW_2.2.0/com.ibm.zos.v2r2.bpxbd00/getenv.htm
https://www.keil.com/support/man/docs/armlib/armlib_chr1359122850667.htm
https://pubs.opengroup.org/onlinepubs/009696799/functions/getenv.html
https://pubs.opengroup.org/onlinepubs/7908799/xsh/getenv.html
https://www.gnu.org/software/libc/manual/html_node/Environment-Access.html
https://man7.org/linux/man-pages/man3/getenv.3p.html

zukatsinadze added inline comments.Mar 21 2021, 5:49 PM
clang/docs/analyzer/checkers.rst
2103–2104

Actual problem is that getenv is returning a pointer to its internal static buffer instead of giving pointer to environ, that's why the string will change with a subsequent call.

zukatsinadze edited the summary of this revision. (Show Details)

Gentle ping

  • Diff with context
  • Added some more tests
  • Updated documentation

@NoQ can you please have another look at this? I think it will be a useful checker.

ormris removed a subscriber: ormris.Jun 3 2021, 10:06 AM

Overall I think it's a useful checker not only for checking the getenv() but a bunch of other functions as well, which might return a pointer to a statically allocated buffer.
The implementation could be polished a bit but it's ok I think.

About the produced reports, they were all useful and clear.
It is triggered only if it sees evidence(*) of the use of the invalidated pointer and highlights where it was produced and later invalidated.

(*) escaping via a conservatively evaluated function call also counts as such. There are pros and cons to this, but in this case, it seems like it's a good choice.

clang/docs/analyzer/checkers.rst
2057

?

clang/test/Analysis/cert/env34-c-cert-examples.c
27–28

I just want to highlight the capabilities of this checker.
Here we are using the invalid tmpvar pointer in a conservatively evaluated function call, and we still have a warning. Which is awesome.

Just imagine that getenv() would return a pointer to the same static buffer, then the strcmp() would always succeed, which is likely a bug.

I have not too deep knowledge about checker development but still found (hopefully valid) issues, even if only a part of them.

clang/docs/analyzer/checkers.rst
2117

From my understanding the "unanticipated behavior" here is clearly a bug: We do not know if the envp points to any valid location. It is not guaranteed that the original value is preserved (in this case it would have sense to use it). And it is not known if it will point to the new and correct array. Unless we know how the internal implementation exactly works.

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

I have multiple issues with the documentation texts but they look not final anyway. And the package and checker names could be better. There are already checkers for CERT rules that do not reside in the cert package, it is not good to have some checkers in a cert package and some not. It is likely that checkers will check for more rules or parts of the rules. Checker aliases are a better solution for the cert checker names. (And now the cert would contain checker with name not matching a rule: InvalidPtr.) The name InvalidPtr sounds too general, even if in an `env˙ package.

clang/lib/StaticAnalyzer/Checkers/cert/InvalidPtrChecker.cpp
29

I think we do not need to repeat the documentation here.

181

Is it not possible to use const MemRegion * then?

193

evalCall should be used only if the called function is exclusively modeled by this checker which is not the case here. The checkPostCall should be sufficient instead of evalCall.

228

auto is not to be used if the type is not clearly visible in the context. And this would be exactly auto ** here. (But better is const MemRegion **.) Makes the later statement (assign to PrevReg) "messy" (and auto is bad there too).

228

.data is unnecessary here?

320

addTransition is not needed here, the state was not modified.
Save the error node returned by generateNonFatalErrorNode and pass it to the next call of generateNonFatalErrorNode as the Pred parameter.

342

Are these casts really needed?

steakhal added inline comments.Jun 4 2021, 2:27 PM
clang/lib/StaticAnalyzer/Checkers/cert/InvalidPtrChecker.cpp
181

The trait stuff is only specialized for void pointers, instead of for any pointer type.
TBH I don't know why is that.

zukatsinadze marked 2 inline comments as done.

@balazske Thanks for the comments!

Updated diff after suggested changes.

zukatsinadze marked an inline comment as done and an inline comment as not done.Jun 8 2021, 10:40 AM
zukatsinadze added inline comments.
clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
957

Agreed. We can come back to wordsmithing later.

clang/lib/StaticAnalyzer/Checkers/cert/InvalidPtrChecker.cpp
228

.data seems to be necessary.

no known conversion from 'llvm::StringRef' to 'typename ProgramStateTrait<PreviousCallResultMap>::key_type' (aka 'const char *') for 1st argument

342

Yes, as steakhal mentioned above, trait is specialized for void*

Charusso resigned from this revision.Jul 30 2021, 10:12 AM

@NoQ, what do you think?

steakhal resigned from this revision.Aug 31 2021, 2:17 AM

I think it looks good, I don't have much objection to this.
I've also participated in the offline-review of this patch, so the current shape of this reflects my intentions, thus I resign.
At the same time, I'm requesting others to have a look at this, I genuinely think it has great value!
@Szelethus @martong @NoQ

Note: I'd like to highlight that on not modeled functions it behaves slightly differently than expected.

And about checkDeadSymbols, I get your point, but I am interested why checker has different behavior on these two examples:

a1 int main(int argc, char **argv, char *envp[]) {
a2   putenv((char*) "NAME=VALUE"); // envp invalidated
a3   envp[0]; // gives error
a4 }
b1 int main(int argc, char **argv, char *envp[]) {
b2   char **e = envp;
b3   putenv((char*) "NAME=VALUE"); // envp invalidated
b4   e[0]; // does not give error
b5 }

If I manually force keeping envp region in state when I check if (!SymReaper.isLiveRegion(E)) { , then it reports as expected.

This is because we use the result of the live variable analysis to drive the cleanup mechanism (i.e. garbage collection) of the analyzer. This data-flow analysis is finished before the path sensitive symbolic execution is started. In the first example, envp becomes dead at line a3 because that is the last point where we read it. In the second exmplae, envp becomes dead at line b2 because that is the last location where we read it's value. And it seems like our live variable analysis does not handle aliasing.
In my humble opinion, the engine should be using a lexical based scoping analysis to drive the callbacks of checkDeadSymbols. Or, perhaps, we should have another callback that is called at the end of the scope based lifetime. (RFC @NoQ). Currently, the engine might report a symbol/region as dead even if that is still live in the lexical scoping sense.
On the other hand, having the cleanup mechanism eagerly removing dead symbols and all of their dependency helps the analyzer to keep it's State as small as absolutely needed, all the time. This way it can be as terse in the memory and as fast in runtime as possible.

Nice work!

clang/lib/StaticAnalyzer/Checkers/cert/InvalidPtrChecker.cpp
160

Why is it const void *? Why can't we use const MemRegion * and get rid of the ugly reinterpret_cast? There must be a reason ,which I'd like to see documented in the comments.

164

I think we could use the canonical FunctionDecl* as the key instead of const char *. Then all the eval functions like evalGetenv and alike could be substituted with one simple function.

222–225

Would it be possible to add a NoteTag here and eliminate the PreviousCallVisitor?

343

I think we should delete the code of this callback, since we can't use it.

steakhal added inline comments.Sep 10 2021, 7:59 AM
clang/lib/StaticAnalyzer/Checkers/cert/InvalidPtrChecker.cpp
160

The trait is only specialized to const void* and void* see here:

https://github.com/llvm/llvm-project/blob/main/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h#L298-L323

template <> struct ProgramStatePartialTrait<void *>
template <> struct ProgramStatePartialTrait<const void *>

I'm not exactly sure why don't we specialize to any pointer type of type T.

Thanks for the review @martong

I've fixed all the suggestions.

zukatsinadze marked 4 inline comments as done.Sep 13 2021, 6:40 AM
zukatsinadze added inline comments.
clang/lib/StaticAnalyzer/Checkers/cert/InvalidPtrChecker.cpp
164

Thanks! Those functions annoyed me a lot.

martong accepted this revision.Sep 13 2021, 8:11 AM

Excellent! Thanks!

This revision is now accepted and ready to land.Sep 13 2021, 8:11 AM
steakhal added inline comments.Sep 13 2021, 9:12 AM
clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
42

Please, insert this in its sorted place.

Gentle ping, I think we can land this, please do so. Let me know if there is an issue with, .e.g missing commit rights, etc...

This revision was automatically updated to reflect the committed changes.
zukatsinadze marked an inline comment as done.