Dear LLVM developers:<br> Here is my another proposal of LLVM. Any suggestion would be welcome!<br>
<p class="MsoNormal" style="text-indent:14.9pt"><b><span style="font-size:15.0pt;font-family:"Times New Roman","serif"" lang="EN-US"><span style> </span><span style> </span></span></b><b><span style="font-size:15pt;font-family:"Times New Roman","serif"" lang="EN-US"><span style> <br>
</span></span></b></p><p class="MsoNormal" style="text-indent:14.9pt"><b><span style lang="EN-US"></span></b><b><span style lang="EN-US"> Integrate Baggy Bounds Checking into SAFECode</span></b><b><span style lang="EN-US"></span></b></p>
<p class="MsoNormal"><b style><span style lang="EN-US"> </span></b></p>
<p class="MsoNormal"><b style><span style="font-size:14.0pt;font-family:"Times New Roman","serif"" lang="EN-US">Abstract:</span></b><b style><span style="font-family:"Times New Roman","serif"" lang="EN-US">
</span></b><span style lang="EN-US"><span style> </span></span><span lang="EN-US">Baggy Bounds Checking </span><span style lang="EN-US">(BBC) is an efficient bounds checking technique that
pad and align objects to powers of two and enable allocation bounds. It uses a
contiguous array as bounds table to enable efficient bounds lookup and thus has
low overhead at runtime. This project is aims to integrate BBC into SAFECode. <span style> </span><span style> </span></span><b><span style lang="EN-US"></span></b></p>
<p class="MsoNormal"><b style><span style lang="EN-US"> </span></b></p>
<p class="MsoNormal"><b style><span style="font-size:14.0pt;font-family:"Times New Roman","serif"" lang="EN-US">Motivation</span></b><b style><span style lang="EN-US"></span></b></p>
<p class="MsoNormal"><span style lang="EN-US">BBC is presented in the
paper [1], which uses a binary buddy allocator that pads and aligns objects to
powers of two. Thus it can just use only a single byte stored in a contiguous
array to compute the base and the size of a pointer. It is an efficient defense
against out-of-bounds errors and the authors claim that it is more than two
times faster than the fasted previous techniques. By integrating BBC into
SAFECode, users can use SAFECode in a more efficient way to check spatial errors.
<span style> </span></span></p>
<p class="MsoNormal"><span style="font-family:"Times New Roman","serif"" lang="EN-US"> </span></p>
<p class="MsoNormal"><b style><span style="font-size:14.0pt;font-family:"Times New Roman","serif"" lang="EN-US">Project Detail</span></b></p>
<p class="MsoNormal"><span style="font-family:"Times New Roman","serif"" lang="EN-US"><span style> </span></span><span style lang="EN-US"><span style> </span>BBC enforces allocation bounds instead of
object bounds. It constrains allocation sizes and alignment to powers of two. For
instance,</span></p>
<p class="MsoNormal"><span style lang="EN-US"><span style> </span>x = malloc (200). BBC allocs the size of x to
be 256 instead:</span></p>
<p class="MsoNormal"><span style lang="EN-US"><span style> </span>x = malloc (256).</span></p>
<p class="MsoNormal"><span style lang="EN-US"><span style> </span>Previous techniques that recorded a pointer to
the start of the object and its size in bounds table, which requires at least
eight bytes. By enabling allocation bounds, BBC can use only a single byte to
encode bounds information. This single byte is set to be log</span><sub><span style lang="EN-US">2</span></sub><span style lang="EN-US">(size). We use ‘e’ to stand for this byte. As for
the above instance, e = 8. The base and the size of a pointer <i style>p</i> can be computed as the following:</span></p>
<p class="MsoNormal" style="text-indent:12.0pt"><i style><span style lang="EN-US">size = 1 << e;</span></i></p>
<p class="MsoNormal" style="text-indent:12.0pt"><i style><span style lang="EN-US">base = p & ~(size -1);</span></i></p>
<p class="MsoNormal"><span style lang="EN-US"><span style> </span>BBC uses a contiguous array to implement
bounds table. Each entry of this table stores the above single byte. Also, application
memory is divided into aligned <i style>slots</i>
with <i style>slot_size</i> bytes. The bound table
has an entry for each slot. When checking whether a pointer is out of bound or
not, BBC can enable optimized bounds checks. For instance,<i style> p</i> is a pointer, we want to check whether the following pointer
arithmetic is safe or not: q = p + i. An explicit bonds check is as the following:</span></p>
<p class="MsoNormal"><span style lang="EN-US">First we need compute
the size and the base of <i style>p: </i></span></p>
<p class="MsoNormal" style="text-indent:12.0pt"><i style><span style lang="EN-US">Size = 1 << table[p>>slot_size]</span></i></p>
<p class="MsoNormal" style="text-indent:12.0pt"><i style><span style lang="EN-US">Base= p & ~(size-1)</span></i></p>
<p class="MsoNormal"><span style lang="EN-US">Then we check whether <i style>q </i>satisfies this condition: </span></p>
<p class="MsoNormal" style="text-indent:12.0pt"><i style><span style lang="EN-US">q >= base && q < base +
size</span></i></p>
<p class="MsoNormal"><span style lang="EN-US">BBC optimizes it as the
following:</span></p>
<p class="MsoNormal" style="text-indent:12.0pt"><i style><span style lang="EN-US">(p^q) >> table[p>>slot_size]
==0 </span></i></p>
<p class="MsoNormal"><span style lang="EN-US">It means that if <i style>q </i>is in bound, it should have the same
prefix with only the e least significant bits modified, where e is the binary logarithm
of the allocation size, stored in the p>>slot_size entry of the bonds table.</span></p>
<p class="MsoNormal"><span style lang="EN-US"><span style> </span>Here I give an example to explain how BBC
works. (We set slot_size to be 16)</span></p>
<p class="MsoNormal"><span style lang="EN-US">p =malloc (100); // It
returns the address 0x12345600</span></p>
<p class="MsoNormal"><span style lang="EN-US">BCD pads and aligns the
size to be 128</span></p>
<p class="MsoNormal" style="margin-left:12.0pt"><span style lang="EN-US">p = malloc (128); So the upper bound of p is
0x12345680 and the lower bound of p is 0x12345600. <i style><span style="background:#d9d9d9">table
[p>>slot_size] = table[p>>16] = log2128 = 7</span></i></span></p>
<p class="MsoNormal"><span style lang="EN-US">There is pointer
arithmetic: </span></p>
<p class="MsoNormal" style="text-indent:12.0pt"><span style lang="EN-US">q = p + 144 = 0x12345690.</span></p>
<p class="MsoNormal"><span style lang="EN-US">We check: (p^q)
>>table[p>>slot_size] = 0x00000090>>7 != 0 So q is out of
bound.</span></p>
<p class="MsoNormal"><span style lang="EN-US"> </span></p>
<p class="MsoNormal"><span style lang="EN-US"><span style> </span>Currently some initial work of BBC has been done
in SAFECode. But there is still a lot of work to do. The padding and alignment
transform works with LLVM 2.x and needs to be updated to LLVM 3. There are no
run time checks of BBC, including pointer arithmetic and array indexing, in the
trunk of SAFECode now. Also I will extend BBC to check pointer dereferences and
access to scalar fields in structure. So this project is to complete BBC at runtime
in SAFECode.</span></p>
<p class="MsoNormal"><b style><span style lang="EN-US"> </span></b></p>
<p class="MsoNormal"><b style><span style="font-size:14.0pt;font-family:"Times New Roman","serif"" lang="EN-US">Timeline</span></b></p>
<p class="MsoNormal"><span style lang="EN-US">The following plan is scheduled
as weeks. </span></p>
<p class="MsoNormal" style="text-indent:11.9pt"><span style lang="EN-US">[1-2] make padding and alignment transform work
with LLVM 3.</span></p>
<p class="MsoNormal" style="text-indent:11.9pt"><span style lang="EN-US">[3-5] Add run-time checks, including each
pointer arithmetic and array indexing operation.</span></p>
<p class="MsoNormal" style="text-indent:11.9pt"><span style lang="EN-US">[6-9] Extend BBC to include the following checks:
access to scalar fields in structures and pointer dereferences.</span></p>
<p class="MsoNormal" style="text-indent:11.9pt"><span style lang="EN-US">[10-11] Test and improvement, make BBC works
well with the test-suite.</span></p>
<p class="MsoNormal" style="text-indent:11.9pt"><span style lang="EN-US">[12] Document for BBC support in SAFECode.</span></p>
<p class="MsoNormal"><span style lang="EN-US"> </span></p>
<p class="MsoNormal"><b style><span style="font-size:14.0pt;font-family:"Times New Roman","serif"" lang="EN-US">Project experience</span></b></p>
<p class="MsoNormal"><b style><span style lang="EN-US"> </span></b></p>
<p class="MsoNormal"><span style lang="EN-US">In GSoC2009, I took part
in a project: support Scilab language on SWIG [2]. I added a backend module in
SWIG, so that it can support all the C features for Scilab language: variables,
functions, constants, enums, structs, unions, pointers and arrays. </span></p>
<p class="MsoNormal"><span style lang="EN-US"> </span></p>
<p class="MsoNormal"><span style lang="EN-US">In GSoC2010, I also
successfully finished a project called“epfs”[3] , which means embedding Python
from Scilab. This project</span><span style="font-family:"Times New Roman","serif"" lang="EN-US">
introduce</span><span style lang="EN-US">s</span><span style="font-family:"Times New Roman","serif"" lang="EN-US"> a mechanism to load
and use Python code from Scilab</span><span style lang="EN-US">. </span></p>
<p class="MsoNormal" style><b style><span style lang="EN-US"> </span></b></p>
<p class="MsoNormal" style><span style lang="EN-US">I have about one year’s
experience for LLVM. I use it mainly to implement control flow integrity for
Operating Systems and thus improve system security. </span><span style="font-family:"Times New Roman","serif"" lang="EN-US">I recently submitted a patch for <i style>Target.h</i> file to improve compatibility
with SWIG, which has been applied on the trunk.</span><span style lang="EN-US"></span></p>
<p class="MsoNormal" style><span style lang="EN-US"> </span></p>
<p class="MsoNormal" style><b style><span style lang="EN-US"> </span></b></p>
<p class="MsoNormal"><b style><span style="font-size:14.0pt;font-family:"Times New Roman","serif"" lang="EN-US">Biography</span></b></p>
<p class="MsoNormal"><span style lang="EN-US">Name:<b style> </b>Baozeng Ding</span></p>
<p class="MsoNormal"><span style lang="EN-US">University:<b style> </b></span><span style="font-family:"Times New Roman","serif"" lang="EN-US">Institute</span><span style="font-family:"Times New Roman","serif"" lang="EN-US"> of Software</span><span style="font-family:"Times New Roman","serif"" lang="EN-US">,</span><span style lang="EN-US"> </span><span style="font-family:"Times New Roman","serif"" lang="EN-US">Chinese</span><span style="font-family:"Times New Roman","serif"" lang="EN-US"> Academy</span><span style="font-family:"Times New Roman","serif"" lang="EN-US"> of Science</span><span style lang="EN-US"></span></p>
<p class="MsoNormal"><span style lang="EN-US">Email: <a href="mailto:sploving1@gmail.com">sploving1@gmail.com</a></span></p>
<p class="MsoNormal"><span style lang="EN-US">IRC name: sploving</span></p>
<p class="MsoNormal"><span style lang="EN-US"> </span></p>
<p class="MsoNormal"><b style><span style="font-size:14.0pt;font-family:"Times New Roman","serif"" lang="EN-US">References</span></b><b style><span style lang="EN-US"></span></b></p>
<p class="MsoNormal" style="margin-left:21.0pt"><span style="font-size:10.5pt;font-family:"Times New Roman","serif"" lang="EN-US"><span style>[1].<span style="font:7.0pt "Times New Roman"">
</span></span></span><span style lang="EN-US">P. Akritidis,M. Costa,M. Castro, and S. Hand. Baggy Bounds Checking: An
Efficient and Backwards-Compatible Defenseagainst Out-of-Bounds Errors. In Proceedings
of the 18th USENIX Security Symposium, August 2009.</span></p>
<p class="MsoNormal" style="margin-left:21.0pt"><span class="MsoHyperlink"><span style lang="EN-US"><span style>[2].<span style="font:7.0pt "Times New Roman"">
</span></span></span></span><span class="MsoHyperlink"><span style lang="EN-US"><a href="http://code.google.com/p/google-summer-of-code-2009-swig/downloads/list"><span style="font-family:"Times New Roman","serif"">http://code.google.com/p/google-summer-of-code-2009-swig/downloads/list</span></a></span></span><span class="MsoHyperlink"><span style lang="EN-US"></span></span></p>
<p class="MsoNormal" style="margin-left:21.0pt"><span class="MsoHyperlink"><span style lang="EN-US"><span style>[3].<span style="font:7.0pt "Times New Roman"">
</span></span></span></span><span class="MsoHyperlink"><span style lang="EN-US"><a href="http://forge.scilab.org/index.php/p/epfs/"><span style="font-family:"Times New Roman","serif"">http://forge.scilab.org/index.php/p/epfs/</span></a></span></span><span class="MsoHyperlink"><span style lang="EN-US"> </span></span></p>
<p class="MsoNormal"><b style><span style lang="EN-US"> </span></b></p>
<br clear="all"><br>-- <br> Best Regards,<br> Baozeng Ding<br> OSTG,NFS,ISCAS<br><br><br>