GSOC Static Analyzer Proposal

Hello All,

I am planning on proposing a project for Google Summer of Code this summer, and would like to get your feedback before I write up a formal proposal.

I would like to work on improving support for C++ in the static analyzer. Specifically, I think it would be valuable to improve the checkers for undefined behavior including those already suggested.

Also, I think it would be helpful to extend the static analyzer to check for stylistic violations. For example, projects like LLVM have suggestions like, “Don’t use else after a return”. These warnings would often be noisy, and project dependent, so it would be useful to make those options configurable and suppressible.

I am also interested in implementing several of the optimization checkers. Specifically, it would be valuable to have warnings about postfix increment and pass by value give an idea of how large the object being copied is.

I would be very interested to hear your feedback, specifically, if you think this project would be valuable.

Thank You,
Adam Schnitzer

All these ideas sound valuable. I recommend initially focusing on just one
of them though, and get to the others as time permits.

-- Sean Silva

I would like to work on improving support for C++ in the static analyzer. Specifically, I think it
would be valuable to improve the checkers for undefined behavior including those already suggested.

I'd be happy to provide feedback on a more specific version of this part of the proposal.

In particular, a useful starting point (maybe this already exists?) would be a list of all C/C++ undefined behaviors broken down by whether Clang/LLVM...

- can reliably provide a compile-time diagnostic

- can reliably provide a runtime diagnostic

- cannot provide any diagnostic, but implements a predictable behavior

- cannot provide any diagnostic and also implements unpredictable behavior

Obviously the last category is the interesting place for future work.

John

John and Sean,

Thank you very much for the feedback. I have a better idea of scope and where to focus.

John, I think you’re absolutely right, with -fsanitize=undefined and others, more behavior is being caught at runtime/compile time. I will start working on a list of behaviors for which no diagnostics currently exist, and select a subset to focus on.

Adam

John and Sean,

Thank you very much for the feedback. I have a better idea of scope and
where to focus.

John, I think you're absolutely right, with -fsanitize=undefined and others,
more behavior is being caught at runtime/compile time. I will start working
on a list of behaviors for which no diagnostics currently exist, and select
a subset to focus on.

My apologies for stepping in and bike shedding: I would really enjoy
something for 'implementation defined' behaviors also. Its not always
portable, and I find it to be a key indicator of code quality.

Perhaps another switch would be in order(-fsanitzie=implementation)?

Jeff

I agree, it would be nice to have diagnostics for implementation defined behavior as well.

However, it seems like there would be some degree of overlap. For example, we already
have -fsanitize=shift, which, I believe, technically checks implementation defined,
rather than undefined behavior (language lawyers feel free to correct me).

I think it could be very interesting to check some behaviors not covered
in the sanitizers statically. Do you have thoughts about static versus dynamic
checking?

Adam

A list of all undefined/implementation defined/unspecified behaviour in
ANSI-C and a classification of which can be determined statically and/or
dynamically can be found in Les Hatton's Safer C. Perhaps that could be of
help when examining where Clang is on those items?

Best Regards
Magnus Reftel

Thanks, I’ll check that out.

Maybe it would be helpful if I compiled a general list of what UB is being caught and where. Would anyone else have any interest?

Adam

+1

It would be good to focus on one or several of checks and have a concrete plan of how they will be implemented. You can send the specifics to the list to get some feedback. Additional bonus would be to choose the checks that are not currently covered by other tools in clang/llvm family but this is not a requirement in my opinion.

I would choose something from C++ undefined behavior or the optimization buckets you mention above. Try to aim for the checks that have a high payoff (in the number of possible bugs/bug severity) and are easier to implement in the static analyzer (do not require too much infrastructure support).

Anna.

Anna,

Thank you for the feedback. I am working on identifying checkers that would be valuable, and can
be implemented in the existing static analyzer infrastructure. I will report back with a draft of
planned deliverables and implementation plans.

I am also working on one of the simpler checkers to get some practice with the analyzer.
The “Unary Plus with Unsigned” checker seemed like a good place to get started, unless
you think there is one that might be better.

Adam

Thanks, I'll check that out.
Maybe it would be helpful if I compiled a general list of what UB is being caught and
where. Would anyone else have any interest?

I'd be happy to help with this. Starting with the Hatton book is a good idea, though it's pretty old.

Also here's a bit of work done by some people on the C standards committee:

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1278
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1331.pdf
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1344.htm

I don't know if anything has come of this or not, but obviously the notion that some undefined behaviors are worse than others is useful.

John

I think it could be very interesting to check some behaviors not covered
in the sanitizers statically. Do you have thoughts about static versus dynamic
checking?

I think the only real answer is to devise the most appropriate solution for each kind of undefined behavior. Obviously static checking is great when it can be done reliably and efficiently.

A random undefined behavior that I find interseting and that nobody has ever checked for in a systematic way (that I know of) is the one concerning multiple references to an lvalue (one of which is a store) that are in between a pair of sequence points.

Clearly some versions can be detected statically and both GCC and LLVM provide a warning for "i = i++;".

On the other hand it's easy to come up with versions of this code that defeat static analysis, but that would not be hard to detect dynamically.

A separate question is whether this particular undefined behavior (which is seen in real codes) is worth checking for. I'm not sure about that, but Clang/LLVM actually does put a different value into i for the code above than do gcc and icc.

John

John and Sean,

Thank you very much for the feedback. I have a better idea of scope and
where to focus.

John, I think you're absolutely right, with -fsanitize=undefined and
others, more behavior is being caught at runtime/compile time. I will start
working on a list of behaviors for which no diagnostics currently exist,
and select a subset to focus on.

I made such a list when I started UBSan, and have (mostly) kept it
up-to-date with what we currently catch:

https://docs.google.com/document/d/1o7Xw6dohIuHLOve3hxtTjCrrUbd2NHUgmq_WGrao6js/edit#heading=h.pgx8h2ru49tm

This only covers core language undefined behavior; the standard library is
another country :wink:

Adam

Richard, This is very helpful. Thank you for sharing.

As John pointed out, looking at multiple modification of an lvalue over a sequence
point seems interesting. And it doesn’t look like something that UBSan is currently
getting. Although it might be difficult to get all violations of that type, catching
some simpler ones seems like a good goal.

Adam

Richard, This is very helpful. Thank you for sharing.

As John pointed out, looking at multiple modification of an lvalue over a
sequence
point seems interesting. And it doesn't look like something that UBSan is
currently
getting. Although it might be difficult to get all violations of that
type, catching
some simpler ones seems like a good goal.

There are two different things you might be interested in here. One is
easy, the other is useful :wink:

The easy (but not very useful) one is catching undefined behavior due to
unsequenced reads/writes to the same location (this is undefined behavior,
and is Object Model item 4 in the document). This is "easy" because (1) we
already have implementation experience (in the static check for this bug)
of finding unsequenced operations, and we would "just" need to generate the
code to check whether any of the unsequenced and potentially-conflicting
operations are actually operating on the same location. Unfortunately, I
don't expect this to catch very many bugs which the static check misses;
this will probably only catch cases where the modified objects are the same
but not "obviously" the same, such as:

  int n;
  int &f() { return n; }
  int g(int, int);
  int k = g(f()++, n);

However, providing the sequencing information to the IR can allow further
optimizations (for instance, a sequencing-based alias analysis can discover
that "f()"s result does not alias "n" in the above code), so there may be
value in this beyond detecting UB bugs.

The useful (but not easy) one is catching cases where the operations are
indeterminately sequenced, rather than unsequenced (this happens when the
accesses are not directly part of the same full-expression, for instance if
one of them is within a function call, and does not provoke undefined
behavior). It's hard because:
1) runtime instrumentation to catch this is hard (this is similar to what
TSan checks for), and
2) removing false positives is hard (most cases of indeterminately
sequenced accesses are benign, because the end result of the program is the
same either way).

Example false positive, to give you a taste of why this is hard:

std::map<int, string*> stuff;
string build(int);
string &get(int k) {
  string *&p = stuff[k];
  if (!p) p = new string(build(k));
  return *p;
}
void f(string &a, string &b);
void g() {
  f(get(1), get(2)); // indeterminately-sequenced modifications to 'stuff'
...
  // ... but this is almost certainly fine, if the results of the 'build'
calls
  // don't depend on the order in which they're called
}

One reasonable heuristic for detecting issues here would be to provide a
mechanism to randomize the evaluation order (subject to the sequencing
rules and with a seed for debugability), and then either (a) just run the
tests for the program, or (b) run the program in parallel with multiple
different orders and check that the "observable behavior" (library IO
calls, etc) is the same.

[As an aside, thinking about "sequence points" is likely to prove unhelpful
to you. The "sequence points" rules are known to be broken, and the
"sequenced before" rules in C11 and C++11 are intended to describe how the
"sequenced before" rules were really meant to work.]

One reasonable heuristic for detecting issues here would be to provide a mechanism to randomize the
evaluation order (subject to the sequencing rules and with a seed for debugability), and then either
(a) just run the tests for the program, or (b) run the program in parallel with multiple different
orders and check that the "observable behavior" (library IO calls, etc) is the same.

This isn't hard and should definitely be done.

There are most likely other unspecified behaviors where some optional randomization would be easy and useful.

John

Unfortunately, I don't expect this to catch very many bugs which the static check misses; this will
probably only catch cases where the modified objects are the same but not "obviously" the same

I still think this would be useful since any kind of indirection defeats the static check--a function call as in your example below isn't even needed.

John

John and Richard,

Thank you for the great ideas. The idea of incorporating a randomization heuristic is very interesting.
It certainly seems like a technique that could be applied in other contexts.

As far as the new “sequence points” rules, I guess it’s time to hit the standard again. I finally thought
I understood the C++03 rules too.

Adam

Hello All,

I am planning on proposing a project for Google Summer of Code this summer,
and would like to get your feedback before I write up a formal proposal.

I would like to work on improving support for C++ in the static analyzer.
Specifically, I think it would be valuable to improve the checkers for
undefined behavior including those already suggested.

Also, I think it would be helpful to extend the static analyzer to check for
stylistic violations. For example, projects like LLVM have suggestions like,
"Don't use else after a return". These warnings would often be noisy, and
project dependent, so it would be useful to make those options configurable
and suppressible.

Many stylistic issues wouldn't likely need the full power of the Clang
Static Analyzer. I suspect it would be better to factor such checks
out of the SA and then have the SA as one (allbeit expensive)
configurable check alongside many others. But I could be wrong - not
sure how lightweight the SA can be if it's doing simple things.

I am also interested in implementing several of the optimization checkers.
Specifically, it would be valuable to have warnings about postfix increment
and pass by value give an idea of how large the object being copied is.

Aside: pass by value is actually surprisingly /good/ in the presence
of move semantics/swaptimizations. But those could be detected.

Hello All,

I am planning on proposing a project for Google Summer of Code this summer,
and would like to get your feedback before I write up a formal proposal.

I would like to work on improving support for C++ in the static analyzer.
Specifically, I think it would be valuable to improve the checkers for
undefined behavior including those already suggested.

Also, I think it would be helpful to extend the static analyzer to check for
stylistic violations. For example, projects like LLVM have suggestions like,
“Don’t use else after a return”. These warnings would often be noisy, and
project dependent, so it would be useful to make those options configurable
and suppressible.

Many stylistic issues wouldn’t likely need the full power of the Clang
Static Analyzer. I suspect it would be better to factor such checks
out of the SA and then have the SA as one (allbeit expensive)
configurable check alongside many others. But I could be wrong - not
sure how lightweight the SA can be if it’s doing simple things.

The static analyzer contains several syntactic, AST-based checkers - they are essentially StmtVisitors. These are much faster than regular analyzer checkers, which rely on path-sensitive symbolic program execution. Currently, there is no analyzer mode, which would only run the syntactic checkers, but it would be relatively easy to add one.

Anna.