clang/www/analyzer/open_projects.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
   2           "http://www.w3.org/TR/html4/strict.dtd">
   3 <html>
   4 <head>
   5   <title>Open Projects</title>
   6   <link type="text/css" rel="stylesheet" href="menu.css">
   7   <link type="text/css" rel="stylesheet" href="content.css">
   8   <script type="text/javascript" src="scripts/menu.js"></script>
   9 </head>
  10 <body>
  11
  12 <div id="page">
  13 <!--#include virtual="menu.html.incl"-->
  14 <div id="content">
  15
  16 <h1>Open Projects</h1>
  17
  18 <p>This page lists several projects that would boost analyzer's usability and
  19 power. Most of the projects listed here are infrastructure-related so this list
  20 is an addition to the <a href="potential_checkers.html">potential checkers
  21 list</a>. If you are interested in tackling one of these, please send an email
  22 to the <a href=https://lists.llvm.org/mailman/listinfo/cfe-dev>cfe-dev
  23 mailing list</a> to notify other members of the community.</p>
  24
  25 <ul>
  26   <li>Release checkers from "alpha"
  27     <p>New checkers which were contributed to the analyzer,
  28     but have not passed a rigorous evaluation process,
  29     are committed as "alpha checkers" (from "alpha version"),
  30     and are not enabled by default.</p>
  31
  32     <p>Ideally, only the checkers which are actively being worked on should be in
  33     "alpha",
  34     but over the years the development of many of those has stalled.
  35     Such checkers should either be improved
  36     up to a point where they can be enabled by default,
  37     or removed from the analyzer entirely.
  38
  39     <ul>
  40       <li><code>alpha.security.ArrayBound</code> and
  41       <code>alpha.security.ArrayBoundV2</code>
  42       <p>Array bounds checking is a desired feature,
  43       but having an acceptable rate of false positives might not be possible
  44       without a proper
  45       <a href="https://en.wikipedia.org/wiki/Widening_(computer_science)">loop widening</a> support.
  46       Additionally, it might be more promising to perform index checking based on
  47       <a href="https://en.wikipedia.org/wiki/Taint_checking">tainted</a> index values.
  48       <p><i>(Difficulty: Medium)</i></p></p>
  49       </li>
  50
  51       <li><code>alpha.unix.StreamChecker</code>
  52         <p>A SimpleStreamChecker has been presented in the Building a Checker in 24
  53         Hours talk
  54         (<a href="https://llvm.org/devmtg/2012-11/Zaks-Rose-Checker24Hours.pdf">slides</a>
  55         <a href="https://youtu.be/kdxlsP5QVPw">video</a>).</p>
  56
  57         <p>This alpha checker is an attempt to write a production grade stream checker.
  58         However, it was found to have an unacceptably high false positive rate.
  59         One of the found problems was that eagerly splitting the state
  60         based on whether the system call may fail leads to too many reports.
  61         A <em>delayed</em> split where the implication is stored in the state
  62         (similarly to nullability implications in <code>TrustNonnullChecker</code>)
  63         may produce much better results.</p>
  64         <p><i>(Difficulty: Medium)</i></p>
  65       </li>
  66     </ul>
  67   </li>
  68
  69   <li>Improve C++ support
  70   <ul>
  71     <li>Handle construction as part of aggregate initialization.
  72       <p><a href="https://en.cppreference.com/w/cpp/language/aggregate_initialization">Aggregates</a>
  73       are objects that can be brace-initialized without calling a
  74       constructor (that is, <code><a href="https://clang.llvm.org/doxygen/classclang_1_1CXXConstructExpr.html">
  75       CXXConstructExpr</a></code> does not occur in the AST),
  76       but potentially calling
  77       constructors for their fields and base classes
  78       These
  79       constructors of sub-objects need to know what object they are constructing.
  80       Moreover, if the aggregate contains
  81       references, lifetime extension needs to be properly modeled.
  82
  83       One can start untangling this problem by trying to replace the
  84       current ad-hoc <code><a href="https://clang.llvm.org/doxygen/classclang_1_1ParentMap.html">
  85       ParentMap</a></code> lookup in <a href="https://clang.llvm.org/doxygen/ExprEngineCXX_8cpp_source.html#l00430">
  86       <code>CXXConstructExpr::CK_NonVirtualBase</code></a> branch of
  87       <code>ExprEngine::VisitCXXConstructExpr()</code>
  88       with proper support for the feature.
  89       <p><i>(Difficulty: Medium) </i></p></p>
  90     </li>
  91
  92     <li>Handle array constructors.
  93       <p>When an array of objects is allocated (say, using the
  94          <code>operator new[]</code> or defining a stack array),
  95          constructors for all elements of the array are called.
  96          We should model (potentially some of) such evaluations,
  97          and the same applies for destructors called from
  98          <code>operator delete[]</code>.
  99          See tests cases in <a href="https://github.com/llvm/llvm-project/tree/main/clang/test/Analysis/handle_constructors_with_new_array.cpp">handle_constructors_with_new_array.cpp</a>.
 100       </p>
 101       <p>
 102       Constructing an array requires invoking multiple (potentially unknown)
 103       amount of constructors with the same construct-expression.
 104       Apart from the technical difficulties of juggling program points around
 105       correctly to avoid accidentally merging paths together, we'll have to
 106       be a judge on when to exit the loop and how to widen it.
 107       Given that the constructor is going to be a default constructor,
 108       a nice 95% solution might be to execute exactly one constructor and
 109       then default-bind the resulting LazyCompoundVal to the whole array;
 110       it'll work whenever the default constructor doesn't touch global state
 111       but only initializes the object to various default values.
 112       But if, say, we're making an array of strings,
 113       depending on the implementation you might have to allocate a new buffer
 114       for each string, and in this case default-binding won't cut it.
 115       We might want to come up with an auxiliary analysis in order to perform
 116       widening of these simple loops more precisely.
 117       </p>
 118     </li>
 119
 120     <li>Handle constructors that can be elided due to Named Return Value Optimization (NRVO)
 121       <p>Local variables which are returned by values on all return statements
 122          may be stored directly at the address for the return value,
 123          eliding the copy or move constructor call.
 124          Such variables can be identified using the AST call <code>VarDecl::isNRVOVariable</code>.
 125       </p>
 126     </li>
 127
 128     <li>Handle constructors of lambda captures
 129       <p>Variables which are captured by value into a lambda require a call to
 130          a copy constructor.
 131          This call is not currently modeled.
 132       </p>
 133     </li>
 134
 135     <li>Handle constructors for default arguments
 136       <p>Default arguments in C++ are recomputed at every call,
 137          and are therefore local, and not static, variables.
 138          See tests cases in <a href="https://github.com/llvm/llvm-project/tree/main/clang/test/Analysis/handle_constructors_for_default_arguments.cpp">handle_constructors_for_default_arguments.cpp</a>.
 139       </p>
 140       <p>
 141       Default arguments are annoying because the initializer expression is
 142       evaluated at the call site but doesn't syntactically belong to the
 143       caller's AST; instead it belongs to the ParmVarDecl for the default
 144       parameter. This can lead to situations when the same expression has to
 145       carry different values simultaneously -
 146       when multiple instances of the same function are evaluated as part of the
 147       same full-expression without specifying the default arguments.
 148       Even simply calling the function twice (not necessarily within the
 149       same full-expression) may lead to program points agglutinating because
 150       it's the same expression. There are some nasty test cases already
 151       in temporaries.cpp (struct DefaultParam and so on). I recommend adding a
 152       new LocationContext kind specifically to deal with this problem. It'll
 153       also help you figure out the construction context when you evaluate the
 154       construct-expression (though you might still need to do some additional
 155       CFG work to get construction contexts right).
 156       </p>
 157     </li>
 158
 159     <li>Enhance the modeling of the standard library.
 160       <p>The analyzer needs a better understanding of STL in order to be more
 161       useful on C++ codebases.
 162       While full library modeling is not an easy task,
 163       large gains can be achieved by supporting only a few cases:
 164       e.g. calling <code>.length()</code> on an empty
 165       <code>std::string</code> always yields zero.
 166     <p><i>(Difficulty: Medium)</i></p><p>
 167     </li>
 168
 169     <li>Enhance CFG to model exception-handling.
 170       <p>Currently exceptions are treated as "black holes", and exception-handling
 171       control structures are poorly modeled in order to be conservative.
 172       This could be improved for both C++ and Objective-C exceptions.
 173       <p><i>(Difficulty: Hard)</i></p></p>
 174     </li>
 175   </ul>
 176   </li>
 177
 178   <li>Core Analyzer Infrastructure
 179   <ul>
 180     <li>Handle unions.
 181       <p>Currently in the analyzer the value of a union is always regarded as
 182       an unknown.
 183       This problem was
 184       previously <a href="https://lists.llvm.org/pipermail/cfe-dev/2017-March/052864.html">discussed</a>
 185       on the mailing list, but no solution was implemented.
 186       <p><i> (Difficulty: Medium) </i></p></p>
 187     </li>
 188
 189     <li>Floating-point support.
 190       <p>Currently, the analyzer treats all floating-point values as unknown.
 191       This project would involve adding a new <code>SVal</code> kind
 192       for constant floats, generalizing the constraint manager to handle floats,
 193       and auditing existing code to make sure it doesn't
 194       make incorrect assumptions (most notably, that <code>X == X</code>
 195       is always true, since it does not hold for <code>NaN</code>).
 196       <p><i> (Difficulty: Medium)</i></p></p>
 197     </li>
 198
 199     <li>Improved loop execution modeling.
 200       <p>The analyzer simply unrolls each loop <tt>N</tt> times before
 201       dropping the path, for a fixed constant <tt>N</tt>.
 202       However, that results in lost coverage in cases where the loop always
 203       executes more than <tt>N</tt> times.
 204       A Google Summer Of Code
 205       <a href="https://summerofcode.withgoogle.com/archive/2017/projects/6071606019358720/">project</a>
 206       was completed to make the loop bound parameterizable,
 207       but the <a href="https://en.wikipedia.org/wiki/Widening_(computer_science)">widening</a>
 208       problem still remains open.
 209
 210       <p><i> (Difficulty: Hard)</i></p></p>
 211     </li>
 212
 213     <li>Basic function summarization support
 214       <p>The analyzer performs inter-procedural analysis using
 215       either inlining or "conservative evaluation" (invalidating all data
 216       passed to the function).
 217       Often, a very simple summary
 218       (e.g. "this function is <a href="https://en.wikipedia.org/wiki/Pure_function">pure</a>") would be
 219       enough to be a large improvement over conservative evaluation.
 220       Such summaries could be obtained either syntactically,
 221       or using a dataflow framework.
 222       <p><i>(Difficulty: Hard)</i></p><p>
 223     </li>
 224
 225     <li>Implement a dataflow flamework.
 226       <p>The analyzer core
 227       implements a <a href="https://en.wikipedia.org/wiki/Symbolic_execution">symbolic execution</a>
 228       engine, which performs checks
 229       (use-after-free, uninitialized value read, etc.)
 230       over a <em>single</em> program path.
 231       However, many useful properties
 232       (dead code, check-after-use, etc.) require
 233       reasoning over <em>all</em> possible in a program.
 234       Such reasoning requires a
 235       <a href="https://en.wikipedia.org/wiki/Data-flow_analysis">dataflow analysis</a> framework.
 236       Clang already implements
 237       a few dataflow analyses (most notably, liveness),
 238       but they implemented in an ad-hoc fashion.
 239       A proper framework would enable us writing many more useful checkers.
 240       <p><i> (Difficulty: Hard) </i></p></p>
 241     </li>
 242
 243     <li>Track type information through casts more precisely.
 244       <p>The <code>DynamicTypePropagation</code>
 245       checker is in charge of inferring a region's
 246       dynamic type based on what operations the code is performing.
 247       Casts are a rich source of type information that the analyzer currently ignores.
 248       <p><i>(Difficulty: Medium)</i></p></p>
 249     </li>
 250
 251   </ul>
 252   </li>
 253
 254   <li>Fixing miscellaneous bugs
 255     <p>Apart from the open projects listed above,
 256        contributors are welcome to fix any of the outstanding
 257        <a href="https://bugs.llvm.org/buglist.cgi?component=Static%20Analyzer&list_id=147756&product=clang&resolution=---">bugs</a>
 258        in the Bugzilla.
 259        <p><i>(Difficulty: Anything)</i></p></p>
 260   </li>
 261
 262 </ul>
 263
 264 </div>
 265 </div>
 266 </body>
 267 </html>