<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META content="text/html; charset=utf-8" http-equiv=Content-Type>
<META name=GENERATOR content="MSHTML 8.00.6001.18828">
<STYLE>@font-face {
font-family: 宋体;
}
@font-face {
font-family: Verdana;
}
@font-face {
font-family: @宋体;
}
@page Section1 {size: 595.3pt 841.9pt; margin: 72.0pt 90.0pt 72.0pt 90.0pt; layout-grid: 15.6pt; }
P.MsoNormal {
TEXT-JUSTIFY: inter-ideograph; TEXT-ALIGN: justify; MARGIN: 0cm 0cm 0pt; FONT-FAMILY: "Times New Roman"; FONT-SIZE: 10.5pt
}
LI.MsoNormal {
TEXT-JUSTIFY: inter-ideograph; TEXT-ALIGN: justify; MARGIN: 0cm 0cm 0pt; FONT-FAMILY: "Times New Roman"; FONT-SIZE: 10.5pt
}
DIV.MsoNormal {
TEXT-JUSTIFY: inter-ideograph; TEXT-ALIGN: justify; MARGIN: 0cm 0cm 0pt; FONT-FAMILY: "Times New Roman"; FONT-SIZE: 10.5pt
}
A:link {
COLOR: blue; TEXT-DECORATION: underline
}
SPAN.MsoHyperlink {
COLOR: blue; TEXT-DECORATION: underline
}
A:visited {
COLOR: purple; TEXT-DECORATION: underline
}
SPAN.MsoHyperlinkFollowed {
COLOR: purple; TEXT-DECORATION: underline
}
SPAN.EmailStyle17 {
FONT-STYLE: normal; FONT-FAMILY: Verdana; COLOR: windowtext; FONT-WEIGHT: normal; TEXT-DECORATION: none; mso-style-type: personal-compose
}
DIV.Section1 {
page: Section1
}
UNKNOWN {
FONT-SIZE: 10pt
}
BLOCKQUOTE {
MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px; MARGIN-LEFT: 2em
}
OL {
MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px
}
UL {
MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px
}
</STYLE>
</HEAD>
<BODY style="MARGIN: 10px; FONT-FAMILY: verdana; FONT-SIZE: 10pt">
<DIV><FONT color=#969696 size=2 face=Verdana></FONT> </DIV>
<DIV><FONT color=#969696 size=2 face=Verdana></FONT> </DIV>
<DIV><FONT color=#969696 size=2 face=Verdana></FONT> </DIV>
<DIV><FONT color=#969696 size=2 face=Verdana>2010-04-01 </FONT></DIV><FONT
color=#969696 size=2 face=Verdana>
<HR style="WIDTH: 100px" align=left color=#b5c4df SIZE=1>
</FONT>
<DIV><FONT size=2 face=Verdana><FONT color=#969696><SPAN>yiqiuping1986</SPAN>
</FONT></FONT></DIV><FONT color=#969696>
<HR color=#b5c4df SIZE=1>
</FONT>
<DIV><FONT size=2 face=Verdana><FONT color=#969696><STRONG>发件人：</STRONG> John
Criswell </FONT></FONT></DIV>
<DIV><FONT size=2 face=Verdana><FONT color=#969696><STRONG>发送时间：</STRONG>
2010-03-30 23:44:58 </FONT></FONT></DIV>
<DIV><FONT size=2 face=Verdana><FONT color=#969696><STRONG>收件人：</STRONG> 易秋萍
</FONT></FONT></DIV>
<DIV><FONT size=2 face=Verdana><FONT color=#969696><STRONG>抄送：</STRONG>
llvmdev@cs.uiuc.edu </FONT></FONT></DIV>
<DIV><FONT size=2 face=Verdana><FONT color=#969696><STRONG>主题：</STRONG> Re:
[LLVMdev] summer of code idea— checking boun ds overflow bugs
</FONT></FONT></DIV>
<DIV><FONT size=2 face=Verdana></FONT><FONT color=#969696> </FONT></DIV>
<DIV><FONT size=2 face=Verdana>
<DIV><FONT color=#969696>易秋萍 wrote:</FONT></DIV>
<DIV><FONT color=#969696></FONT> </DIV>
<DIV><FONT color=#969696>Hi,</FONT></DIV>
<DIV><FONT color=#969696></FONT> </DIV>
<DIV><FONT
color=#969696>Some days ago I am interested in detecting undefined behaviors</FONT></DIV>
<DIV><FONT
color=#969696>in C programs based on Clang. After several days’ investigation, I think</FONT></DIV>
<DIV><FONT
color=#969696>checking bounds overflow bugs is more interesting, because bounds</FONT></DIV>
<DIV><FONT
color=#969696>overflow is one of the most frequently encountered errors in C programs.</FONT></DIV>
<DIV><FONT
color=#969696>For example, performing pointer arithmetic without checking bounds</FONT></DIV>
<DIV><FONT
color=#969696>can cause bounds overflow. To increase the accuracy of finding bugs,</FONT></DIV>
<DIV><FONT
color=#969696>I want to write several passes, based on slicing, inline and summary</FONT></DIV>
<DIV><FONT color=#969696>function</FONT></DIV>
<DIV><FONT
color=#969696> / (partial) transition function, to implement intre-procedural analysis.</FONT></DIV>
<DIV><FONT
color=#969696>Does some person have interest in the project? I need a mentor,</FONT></DIV>
<DIV><FONT
color=#969696>and wait for your reply.</FONT></DIV>
<DIV><FONT color=#969696></FONT> </DIV>
<DIV><FONT color=#969696>John wrote:</FONT></DIV>
<DIV><FONT color=#969696></FONT> </DIV>
<DIV><FONT color=#969696></FONT></DIV>
<DIV><FONT
color=#969696>The SAFECode project (http://safecode.cs.illinois.edu) is very</FONT></DIV>
<DIV><FONT
color=#969696>interested in having a static array bounds checking analysis pass.</FONT></DIV>
<DIV><FONT
color=#969696>However, we're not interested in a static analysis tool, and we're not</FONT></DIV>
<DIV><FONT
color=#969696>interested in something that works on Clang's IR. What we want is a one</FONT></DIV>
<DIV><FONT
color=#969696>or more LLVM IR analysis passes that tells us which getelementptr (GEP)</FONT></DIV>
<DIV><FONT
color=#969696>instructions in a program are statically known not to overflow (this</FONT></DIV>
<DIV><FONT
color=#969696>allows us to eliminate run-time checks for such instructions).</FONT></DIV>
<DIV><FONT color=#969696></FONT></DIV>
<DIV><FONT
color=#969696>Such a pass exists in the SAFECode project's source tree, but it has not</FONT></DIV>
<DIV><FONT
color=#969696>been maintained well over the years and has fallen into disuse (it also</FONT></DIV>
<DIV><FONT
color=#969696>had some engineering limitations, such as using exec() to repeatedly</FONT></DIV>
<DIV><FONT
color=#969696>execute the Omega compiler for constraint solving). Either getting that</FONT></DIV>
<DIV><FONT
color=#969696>code to work again or replacing it with something better would be</FONT></DIV>
<DIV><FONT color=#969696>beneficial.</FONT></DIV>
<DIV><FONT color=#969696></FONT></DIV>
<DIV><FONT
color=#969696>If you'd be willing to work on something that works with SAFECode, I'd</FONT></DIV>
<DIV><FONT
color=#969696>be willing to mentor your project. I do, however, have one condition:</FONT></DIV>
<DIV><FONT
color=#969696>you need to find a specific static array bounds checking algorithm and</FONT></DIV>
<DIV><FONT
color=#969696>understand how it works. I don't see a specific algorithm or paper</FONT></DIV>
<DIV><FONT color=#969696>reference above.</FONT></DIV>
<DIV><FONT color=#969696></FONT> </DIV>
<DIV>Did you mean implementing a new static array bouns checking algorithm
</DIV>
<DIV>with SAFECode is a better idea than that with LLVM?</DIV>
<DIV>I am not sure whether it's feasible to finish it within a summer, under the
</DIV>
<DIV>condition that I have little knowledge of SAFECode project.</DIV>
<DIV><FONT color=#969696></FONT> </DIV>
<DIV><FONT color=#969696></FONT></DIV>
<DIV><FONT
color=#969696>A good starting point for algorithms might be Dinakar's paper (see</FONT></DIV>
<DIV><FONT
color=#969696>Section 5): http://llvm.org/pubs/2005-02-TECS-SAFECode.html. There has</FONT></DIV>
<DIV><FONT
color=#969696>also been talk of implementing the ABCD algorithm in LLVM</FONT></DIV>
<DIV><FONT
color=#969696>(http://portal.acm.org/citation.cfm?id=349342); you may want to read</FONT></DIV>
<DIV><FONT
color=#969696>about that algorithm as well.</FONT></DIV>
<DIV><FONT color=#969696></FONT></DIV>
<DIV><FONT
color=#969696>As an aside, I've written a pass that finds the inter-procedural static</FONT></DIV>
<DIV><FONT
color=#969696>backwards slice of an LLVM value (disclaimer: it uses DSA to find the</FONT></DIV>
<DIV><FONT
color=#969696>targets of indirect function calls). I'm pretty sure we could release it</FONT></DIV>
<DIV><FONT
color=#969696>to the public if you find that you need it for your project.</FONT></DIV>
<DIV><FONT color=#969696></FONT></DIV>
<DIV><FONT color=#969696>-- John T.</FONT></DIV>
<DIV><FONT color=#969696></FONT></DIV>
<DIV><FONT color=#969696>> Best Reagards!</FONT></DIV>
<DIV><FONT color=#969696>></FONT></DIV>
<DIV><FONT color=#969696>> Qiuping Yi</FONT></DIV>
<DIV><FONT color=#969696>></FONT></DIV>
<DIV><FONT color=#969696></FONT></DIV>
<DIV><FONT color=#969696></FONT></DIV>
<DIV><FONT
color=#969696>_______________________________________________</FONT></DIV>
<DIV>LLVM Developers mailing list</DIV>
<DIV><A href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</A>
<A
href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</A> </DIV>
<DIV><A
href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</A>
</DIV>
<DIV><FONT color=#969696></FONT></DIV></FONT></DIV></BODY></HTML>