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 
19power. Most of the projects listed here are infrastructure-related so this list 
20is an addition to the <a href="potential_checkers.html">potential checkers 
21list</a>. If you are interested in tackling one of these, please send an email 
22to the <a href=http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev>cfe-dev
23mailing list</a> to notify other members of the community.</p>
24
25<ul>  
26  <li>Core Analyzer Infrastructure
27  <ul>
28    <li>Explicitly model standard library functions with <tt>BodyFarm</tt>.
29    <p><tt><a href="http://clang.llvm.org/doxygen/classclang_1_1BodyFarm.html">BodyFarm</a></tt> 
30    allows the analyzer to explicitly model functions whose definitions are 
31    not available during analysis. Modeling more of the widely used functions 
32    (such as the members of <tt>std::string</tt>) will improve precision of the
33    analysis. 
34    <i>(Difficulty: Easy, ongoing)</i><p>
35    </li>
36
37    <li>Handle floating-point values.
38    <p>Currently, the analyzer treats all floating-point values as unknown.
39    However, we already have most of the infrastructure we need to handle
40    floats: RangeConstraintManager. This would involve adding a new SVal kind
41    for constant floats, generalizing the constraint manager to handle floats
42    and integers equally, and auditing existing code to make sure it doesn't
43    make untoward assumptions.
44    <i> (Difficulty: Medium)</i></p>
45    </li>
46    
47    <li>Implement generalized loop execution modeling.
48    <p>Currently, the analyzer simply unrolls each loop <tt>N</tt> times. This 
49    means that it will not execute any code after the loop if the loop is 
50    guaranteed to execute more than <tt>N</tt> times. This results in lost 
51    basic block coverage. We could continue exploring the path if we could 
52    model a generic <tt>i</tt>-th iteration of a loop.
53    <i> (Difficulty: Hard)</i></p>
54    </li>
55
56    <li>Enhance CFG to model C++ temporaries properly.
57    <p>There is an existing implementation of this, but it's not complete and
58    is disabled in the analyzer.
59    <i>(Difficulty: Medium; current contact: Alex McCarthy)</i></p>    
60
61    <li>Enhance CFG to model exception-handling properly.
62    <p>Currently exceptions are treated as "black holes", and exception-handling
63    control structures are poorly modeled (to be conservative). This could be
64    much improved for both C++ and Objective-C exceptions.
65    <i>(Difficulty: Medium)</i></p>    
66
67    <li>Enhance CFG to model C++ <code>new</code> more precisely.
68    <p>The current representation of <code>new</code> does not provide an easy
69    way for the analyzer to model the call to a memory allocation function
70    (<code>operator new</code>), then initialize the result with a constructor
71    call. The problem is discussed at length in
72    <a href="http://llvm.org/bugs/show_bug.cgi?id=12014">PR12014</a>.
73    <i>(Difficulty: Easy; current contact: Karthik Bhat)</i></p>
74
75    <li>Enhance CFG to model C++ <code>delete</code> more precisely.
76    <p>Similarly, the representation of <code>delete</code> does not include
77    the call to the destructor, followed by the call to the deallocation
78    function (<code>operator delete</code>). One particular issue 
79    (<tt>noreturn</tt> destructors) is discussed in
80    <a href="http://llvm.org/bugs/show_bug.cgi?id=15599">PR15599</a>
81    <i>(Difficulty: Easy; current contact: Karthik Bhat)</i></p>    
82
83    <li>Implement a BitwiseConstraintManager to handle <a href="http://llvm.org/bugs/show_bug.cgi?id=3098">PR3098</a>.
84    <p>Constraints on the bits of an integer are not easily representable as
85    ranges. A bitwise constraint manager would model constraints such as "bit 32
86    is known to be 1". This would help code that made use of bitmasks</code>.
87    <i>(Difficulty: Medium)</i></p>
88    </li>
89
90    <li>Track type info through casts more precisely.
91    <p>The DynamicTypePropagation checker is in charge of inferring a region's
92    dynamic type based on what operations the code is performing. Casts are a
93    rich source of type information that the analyzer currently ignores. They
94    are tricky to get right, but might have very useful consequences.
95    <i>(Difficulty: Medium)</i></p>    
96
97    <li>Design and implement alpha-renaming.
98    <p>Implement unifying two symbolic values along a path after they are 
99    determined to be equal via comparison. This would allow us to reduce the 
100    number of false positives and would be a building step to more advanced 
101    analyses, such as summary-based interprocedural and cross-translation-unit 
102    analysis. 
103    <i>(Difficulty: Hard)</i></p>
104    </li>    
105  </ul>
106  </li>
107
108  <li>Bug Reporting 
109  <ul>
110    <li>Add support for displaying cross-file diagnostic paths in HTML output
111    (used by <tt>scan-build</tt>).
112    <p>Currently <tt>scan-build</tt> output does not display reports that span 
113    multiple files. The main problem is that we do not have a good format to
114    display such paths in HTML output. <i>(Difficulty: Medium)</i> </p>
115    </li>
116    
117    <li>Refactor path diagnostic generation in <a href="http://clang.llvm.org/doxygen/BugReporter_8cpp_source.html">BugReporter.cpp</a>.
118    <p>It would be great to have more code reuse between "Minimal" and 
119    "Extensive" PathDiagnostic generation algorithms. One idea is to create an 
120    IR for representing path diagnostics, which would be later be used to 
121    generate minimal or extensive report output. <i>(Difficulty: Medium)</i></p>
122    </li>
123  </ul>
124  </li>
125
126  <li>Other Infrastructure 
127  <ul>
128    <li>Rewrite <tt>scan-build</tt> (in Python).
129    <p><i>(Difficulty: Easy)</i></p>
130    </li>
131
132    <li>Do a better job interposing on a compilation.
133    <p>Currently, <tt>scan-build</tt> just sets the <tt>CC</tt> and <tt>CXX</tt>
134    environment variables to its wrapper scripts, which then call into an
135    underlying platform compiler. This is problematic for any project that
136    doesn't exclusively use <tt>CC</tt> and <tt>CXX</tt> to control its
137    compilers.
138    <p><i>(Difficulty: Medium-Hard)</i></p>
139    </li>
140
141    <li>Create an <tt>analyzer_annotate</tt> attribute for the analyzer 
142    annotations.
143    <p>We would like to put all analyzer attributes behind a fence so that we 
144    could add/remove them without worrying that compiler (not analyzer) users 
145    depend on them. Design and implement such a generic analyzer attribute in 
146    the compiler. <i>(Difficulty: Medium)</i></p>
147    </li>
148  </ul>
149  </li>
150
151  <li>Enhanced Checks
152  <ul>
153    <li>Implement a production-ready StreamChecker.
154    <p>A SimpleStreamChecker has been presented in the Building a Checker in 24 
155    Hours talk 
156    (<a href="http://llvm.org/devmtg/2012-11/Zaks-Rose-Checker24Hours.pdf">slides</a>
157    <a href="http://llvm.org/devmtg/2012-11/videos/Zaks-Rose-Checker24Hours.mp4">video</a>). 
158    We need to implement a production version of the checker with richer set of 
159    APIs and evaluate it by running on real codebases. 
160    <i>(Difficulty: Easy)</i></p>
161    </li>
162
163    <li>Extend Malloc checker with reasoning about custom allocator, 
164    deallocator, and ownership-transfer functions.
165    <p>This would require extending the MallocPessimistic checker to reason 
166    about annotated functions. It is strongly desired that one would rely on 
167    the <tt>analyzer_annotate</tt> attribute, as described above. 
168    <i>(Difficulty: Easy)</i></p>
169    </li>
170
171    <li>Implement a BitwiseMaskingChecker to handle <a href="http://llvm.org/bugs/show_bug.cgi?id=16615">PR16615</a>.
172    <p>Symbolic expressions of the form <code>$sym &amp; CONSTANT</code> can range from 0 to <code>CONSTANT-</code>1 if CONSTANT is <code>2^n-1</code>, e.g. 0xFF (0b11111111), 0x7F (0b01111111), 0x3 (0b0011), 0xFFFF, etc. Even without handling general bitwise operations on symbols, we can at least bound the value of the resulting expression. Bonus points for handling masks followed by shifts, e.g. <code>($sym &amp; 0b1100) >> 2</code>.
173    <i>(Difficulty: Easy)</i></p>
174    </li>
175
176    <li>Implement iterators invalidation checker.
177    <p><i>(Difficulty: Easy)</i></p>
178    </li>
179    
180    <li>Write checkers which catch Copy and Paste errors.
181    <p>Take a look at the
182    <a href="http://pages.cs.wisc.edu/~shanlu/paper/TSE-CPMiner.pdf">CP-Miner</a>
183    paper for inspiration. 
184    <i>(Difficulty: Medium-Hard; current contacts: Per Viberg and Daniel Fahlgren)</i></p>
185    </li>  
186  </ul>
187  </li>
188</ul>
189
190</div>
191</div>
192</body>
193</html>
194
195