<div dir="ltr">On Fri, Apr 12, 2013 at 1:08 PM, Adam Schnitzer <span dir="ltr"><<a href="mailto:adamschn@umich.edu" target="_blank" class="cremed">adamschn@umich.edu</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Richard, This is very helpful. Thank you for sharing.<div>
<br></div><div>As John pointed out, looking at multiple modification of an lvalue over a sequence </div><div>point seems interesting. And it doesn't look like something that UBSan is currently </div>
<div>getting. Although it might be difficult to get all violations of that type, catching</div><div>some simpler ones seems like a good goal.</div></blockquote><div><br></div><div style>There are two different things you might be interested in here. One is easy, the other is useful ;-)</div>
<div style><br></div><div style>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:</div>
<div style><br></div><div style> int n;</div><div style> int &f() { return n; }</div><div style> int g(int, int);</div><div style> int k = g(f()++, n);</div><div style><br></div><div style>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.</div>
<div style><br></div><div style>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:</div>
<div style>1) runtime instrumentation to catch this is hard (this is similar to what TSan checks for), and</div><div style>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).</div>
<div style><br></div><div style>Example false positive, to give you a taste of why this is hard:</div><div style><br></div><div style>std::map<int, string*> stuff;</div><div style>string build(int);</div><div style>
string &get(int k) {</div><div style> string *&p = stuff[k];</div><div style> if (!p) p = new string(build(k));</div><div style> return *p;</div><div style>}</div><div style>void f(string &a, string &b);</div>
<div style>void g() {</div><div style> f(get(1), get(2)); // indeterminately-sequenced modifications to 'stuff' ...</div><div style> // ... but this is almost certainly fine, if the results of the 'build' calls</div>
<div style> // don't depend on the order in which they're called</div><div style>}</div><div style><br></div><div style>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.</div>
<div style><br></div><div style>[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.]</div>
<div style> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span class=""><font color="#888888"><div>
Adam</div></font></span><div class=""><div class="h5"><div><br><div class="gmail_quote">On Fri, Apr 12, 2013 at 2:23 PM, Richard Smith <span dir="ltr"><<a href="mailto:richard@metafoo.co.uk" target="_blank" class="cremed">richard@metafoo.co.uk</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>On Wed, Apr 10, 2013 at 2:07 PM, Adam Schnitzer <span dir="ltr"><<a href="mailto:adamschn@umich.edu" target="_blank" class="cremed">adamschn@umich.edu</a>></span> wrote:<br>
</div><div class="gmail_extra"><div class="gmail_quote"><div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">John and Sean,<div><br></div><div>Thank you very much for the feedback. I have a better idea of scope and where to focus.</div>
<div><br></div><div>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.</div>
</blockquote><div><br></div></div><div>I made such a list when I started UBSan, and have (mostly) kept it up-to-date with what we currently catch:</div><div><br></div><div><a href="https://docs.google.com/document/d/1o7Xw6dohIuHLOve3hxtTjCrrUbd2NHUgmq_WGrao6js/edit#heading=h.pgx8h2ru49tm" target="_blank" class="cremed">https://docs.google.com/document/d/1o7Xw6dohIuHLOve3hxtTjCrrUbd2NHUgmq_WGrao6js/edit#heading=h.pgx8h2ru49tm</a><br>
</div><div> </div><div>This only covers core language undefined behavior; the standard library is another country ;)</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div>
<span><font color="#888888"><div>Adam</div></font></span><div><div><div><br><div class="gmail_quote">On Wed, Apr 10, 2013 at 1:54 PM, John Regehr <span dir="ltr"><<a href="mailto:regehr@cs.utah.edu" target="_blank" class="cremed">regehr@cs.utah.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
I would like to work on improving support for C++ in the static analyzer. Specifically, I think it<br>
would be valuable to improve the checkers for undefined behavior including those already suggested.<br>
</blockquote>
<br></div>
I'd be happy to provide feedback on a more specific version of this part of the proposal.<br>
<br>
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...<br>
<br>
- can reliably provide a compile-time diagnostic<br>
<br>
- can reliably provide a runtime diagnostic<br>
<br>
- cannot provide any diagnostic, but implements a predictable behavior<br>
<br>
- cannot provide any diagnostic and also implements unpredictable behavior<br>
<br>
Obviously the last category is the interesting place for future work.<span><font color="#888888"><br>
<br>
John<br>
</font></span></blockquote></div><br></div>
</div></div><br></div><div>_______________________________________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@cs.uiuc.edu" target="_blank" class="cremed">cfe-dev@cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev" target="_blank" class="cremed">http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev</a><br>
<br></div></blockquote></div><br></div></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div></div>