Svadev mailing list

[John Criswell <criswell AT illinois.edu>]

On 9/24/12 11:43 AM, Kumud Bhandari wrote:
> Hello,
> We are two graduate students taking COMP527 (Computer Security) course 
> at Rice University with Prof. Dan Wallach. We are interested in 
> looking into SAFEcode for our final project for this course. We found 
> a number of open projects listed on SAFECode's website 
> (http://safecode.cs.illinois.edu/projects.html). We were particularly 
> interested in following topics:

Hi!  Nice to see an email from students at Rice University.  My advisor, 
Vikram Adve, was a postdoc at Rice, IIRC.

First, the good news: most of these projects are still open, so if any 
of them interest you, you can work on them.

Second, whether a project will be suitable for a semester project 
depends upon whether you'll be doing one project together or two 
individual projects.  It will also depend on how much compiler 
experience you have.  Have either of you taken a compiler course?

Third, you may want to think about whether a project can be the starting 
point for a research paper.  Many of the projects below involve no 
research.  At Illinois, we try to find, if possible, projects that can 
be part of a larger research paper.

On to the specific projects:

> -> Improve static array bounds checking

I believe Ott Tinn wrote a simple optimization pass that does some 
static array bounds checking.  However, I suspect that there's plenty of 
other static array bounds checking passes that could be written, 
including ones that are inter-procedural and/or that can handle values 
read from memory objects (all the existing analyses only handle values 
that are always in SSA form).  There's also a number of approaches to 
try (e.g., using range analysis, using an SMT solver, etc.).

The project can be challenging but I think would make a good project.  
If you decide to pick such a project, please email the list.  I and my 
fellow students wrote a static array bounds checking analysis for 
SAFECode using the CVC3 SMT solver (sadly, it hasn't turned out as well 
as we'd hoped), so I think I can provide some valuable insights on what 
to try.

If you think of something clever, you might be able to get a research 
publication out of the project.

> -> Create a simpler CompleteChecks pass

No one has worked on this project yet, but it's a pretty simple 
project.  The original idea was to use intra-procedural data-flow 
analysis to find which checks are not influenced by external code and to 
make those checks complete.  Such an analysis is easy to write; to make 
the project more difficult, one could write an inter-procedural analysis.

I don't think there's really good research material here, but you might 
be able to squeeze out a workshop paper or 2nd/3rd tier conference paper 
by looking at the question of how much analysis is needed to make the 
majority of checks complete.  Will intra-procedural be able to make most 
checks complete?  What about inter-procedural analysis on each 
compilation unit?  Is whole-program analysis really required to make 
most checks complete?

> -> And some other optimizations such type-safety optimization (with 
> garbage collection),  and hoisting checks out of monotonic loops.

The type-safety optimization has already been implemented, and it 
works.  It's simply disabled because SAFECode is not using automatic 
pool allocation or garbage collection at present, so the optimization is 
technically unsound.  Adding garbage collection is probably too simple 
for a semester project unless you also write your own specialized 
garbage collector.

The monotonic loop optimization is still open; it was on our new 
research programmer's TODO list, but sadly, we piled some more work on 
top of that, so he hasn't gotten to it yet.  If you wanted to work on 
that optimization, you could, although I don't think it's a good 
semester project: it won't yield a research paper, and hoisting code out 
of loops is a common topic in compiler classes.  Hoisting memory safety 
checks is just a bit more tedious.

That said, there are many other things that might be more difficult to 
write that would be useful:

o) An inter-procedural analysis that tells us where memory can be 
freed.  Many optimizations are disabled on heap objects because we 
haven't proven that the heap object will not be freed.  This inhibits 
the fastcheck (i.e., the oddly named exactcheck optimization), redundant 
check elimination, loop hoisting, etc., etc.

o) A redundant pointer arithmetic check elimination pass.  For 
operations like finding offsets into structures, only two checks are 
needed: a check for accessing the first element, and a check for 
accessing the last element.  If those two checks pass, then accessing 
any other element is guaranteed to be safe.  Various techniques 
(including SMT solvers) could be used to find and eliminate such checks.

o) Inter-procedural check elimination: This would essentially be Ott 
Tinn's transform but applied inter-procedurally.  This would eliminate a 
check in a callee, for example, if it is always verified safe first 
within all callers.

-- John T.