[LLVMdev] summer of code idea— checking boun ds overflow bugs

[yiqiuping1986]

2010-04-01 



yiqiuping1986 



发件人： John Criswell 
发送时间： 2010-03-30  23:44:58 
收件人： 易秋萍 
抄送： llvmdev at cs.uiuc.edu 
主题： Re: [LLVMdev] summer of code idea— checking boun ds overflow bugs 
 
易秋萍 wrote:

Hi,

Some days ago I am interested in detecting undefined behaviors
in C programs based on Clang. After several days’ investigation, I think
checking bounds overflow bugs is more interesting, because bounds
overflow is one of the most frequently encountered errors in C programs.
For example, performing pointer arithmetic without checking bounds
can cause bounds overflow. To increase the accuracy of finding bugs,
I want to write several passes, based on slicing, inline and summary
function
 / (partial) transition function, to implement intre-procedural analysis.
Does some person have interest in the project? I need a mentor,
and wait for your reply.

John wrote:

The SAFECode project (http://safecode.cs.illinois.edu) is very
interested in having a static array bounds checking analysis pass.
However, we're not interested in a static analysis tool, and we're not
interested in something that works on Clang's IR. What we want is a one
or more LLVM IR analysis passes that tells us which getelementptr (GEP)
instructions in a program are statically known not to overflow (this
allows us to eliminate run-time checks for such instructions).
Such a pass exists in the SAFECode project's source tree, but it has not
been maintained well over the years and has fallen into disuse (it also
had some engineering limitations, such as using exec() to repeatedly
execute the Omega compiler for constraint solving). Either getting that
code to work again or replacing it with something better would be
beneficial.
If you'd be willing to work on something that works with SAFECode, I'd
be willing to mentor your project. I do, however, have one condition:
you need to find a specific static array bounds checking algorithm and
understand how it works. I don't see a specific algorithm or paper
reference above.

Did you mean implementing a new static array bouns checking algorithm 
with SAFECode is a better idea than that with LLVM?
I am not sure whether it's feasible to finish it within a summer, under the 
condition that I have little knowledge of SAFECode project.

A good starting point for algorithms might be Dinakar's paper (see
Section 5): http://llvm.org/pubs/2005-02-TECS-SAFECode.html. There has
also been talk of implementing the ABCD algorithm in LLVM
(http://portal.acm.org/citation.cfm?id=349342); you may want to read
about that algorithm as well.
As an aside, I've written a pass that finds the inter-procedural static
backwards slice of an LLVM value (disclaimer: it uses DSA to find the
targets of indirect function calls). I'm pretty sure we could release it
to the public if you find that you need it for your project.
-- John T.
> Best Reagards!
>
> Qiuping Yi
>
_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu          http://llvm.cs.uiuc.edu 
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100401/375b7502/attachment.html>