[cfe-dev] Buffer bounds checking for C in static analysis

Ted Kremenek kremenek at apple.com
Tue Jan 19 11:54:22 CST 2010


Another big missing feature is reasoning about (linear) constraints between symbolic values.  For example:

  p = malloc(len);
  if (i > len)
    p[i] = ...

Right now we track range constraints on individual symbolic values (e.g., the values of 'i' and 'len' respectively), but don't track linear constraints between symbolic values.  Doing so really is a prerequisite for doing interesting buffer overflow checking on arrays of dynamic size.

Tracking linear constraints between symbolic values would likely be a big win in the analyzer's overall precision, and not just useful for buffer overflow checking.  Doing this would reduce down to implementing a new ConstraintManager (that possibly was built on the currently existing ones).

On Jan 18, 2010, at 11:34 PM, Zhongxing Xu wrote:

> Hi Chris,
> 
> The current clang static analyzer only has a basic array bounds checker (ArrayBoundChecker.cpp). Its function is very simple: whenever a location is visited, if it's an array element, compare its index with the size of the array. Some errors it can detect:
> 
> int a[4];
> a[4] = 3;
> 
> and
> int *p = malloc(12);
> p[3] = 3;
> 
> That is, the current analyzer has the basic infrastructure for detecting out-of-bound array access.
> 
> The complexity of bounds checking arises from two facts: (may be there are others)
> 
> a. Many out-of-bound accesses occur in loops. Depending on the length of the buffer, it may require looping many times before triggering the out-of-bound access. But currently we only unwrap the loop for 2 or 3 times.
> 
> b. There are several string manipulation functions, such as strcpy(), strcat(). Currently we don't handle them. One simple way is to provide a fake implementation of them and inline them into the call site, and treat them as normal loops. Another way is to create some linear constraints over the arguments of them, and solve it. But this has complexity that we need to model the actual length of the string and the size of the array.
> 
> Some other projects includes integer overflow checking. This has not been implemented at all in clang.
> 
> Also inter-procedural analysis is required to enhance all other checks.
> 
> 2010/1/19 Chris Hacking <chacking at cs.washington.edu>
> Hi all,
> 
> I'm a student (part of a group of 3) looking for a project involving
> software engineering tools, preferably static analysis. I do a lot of work
> in C and have long felt that a static analysis tool for bounds checking on
> memory buffers (arrays/strings) would be very helpful. I saw that this was a
> requested feature for the Clang analysis tool, but there's very little info
> and it's apparently not fully developed yet. Therefore I have two questions:
> 
> What is the state of bounds checking for C in the Clang analyzer, in terms
> of how far it has gotten and how much work is progressing on it?
> 
> Is there another static analysis area that the Clang static analyzer needs
> implemented that would be a reasonable project for a few CS grad students?
> 
> Thanks,
> Chris Hacking
> 
> There's no place I can be,
> Since I found Serenity.
> But you can't take the sky from me.
> 
> 
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
> 
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.cs.uiuc.edu/pipermail/cfe-dev/attachments/20100119/c5846bfc/attachment-0001.html 


More information about the cfe-dev mailing list