Weeks 9 and 10

I think I forgot to line up a reading for this week. Would anyone object strongly if we take a week off?

That leaves just Week 10 to go. Here's what I propose: Instead of reading a paper, the assignment for everyone is to cook up a new program analysis. You don't have to implement it, of course, but I'd like you to give it some thought with respect both to usefulness and practical application. Try to devise something that ...

• You would actually use. Is there something you find tedious or error-prone when programming, that could be addressed with a program analysis?
• Is not currently available, or is not available in contexts where you want it (e.g., the compiler might do it, but when you really need it is in your IDE or editor).
• Can be practically implemented. While I will not ask you to prove this by actually implementing it, I would like you to think it through far enough to sketch how an implementation would work, and be able to argue that it would be reasonably efficient for its intended purpose. (“Reasonably efficient” can have different meanings depending on context. An analysis that would be perfectly reasonable in an external analysis tool that runs each time you compile your code might be far too expensive to run within the text editor as you type.)

Also consider whether the analysis can or should be static, dynamic, or some combination of the two, what it's scope is (procedure or object? whole program?), and what (if any) extra information it requires of the user.

OK?

Reading: Correspondence between CPS and SSA

Tuesday, Dan will lead us in discussion of

Kelsey, R. A. 1995. A correspondence between continuation passing style and static single assignment form. In Papers From the 1995 ACM SIGPLAN Workshop on intermediate Representations (San Francisco, California, United States, January 22 - 22, 1995). ACM, New York, NY, 13-22. DOI= http://doi.acm.org/10.1145/202529.202532

Reading assignment: Trace collection through slicing

Suzanne will lead discussion of

Zhai, J., Sheng, T., He, J., Chen, W., and Zheng, W. 2009. FACT: fast communication trace collection for parallel applications through program slicing. In Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis (Portland, Oregon, November 14 - 20, 2009). SC '09. ACM, New York, NY, 1-12. DOI= http://doi.acm.org/10.1145/1654059.1654087

String predicates as finite automata

One of the interesting things mentioned in the paper we discussed Tuesday was work on using automata to characterize strings. If you're interested in the paper that was reference [54], the IEEE DL link is:
http://doi.ieeecomputersociety.org/10.1109/TAIC.PART.2007.34

A related paper is Precise
analysis of string expressions by A. Christensen, A. Møller, and M. Schwartzbach, in Proc. 10th International
Static Analysis Symposium (SAS’03) June 2004.

Paper: Trends in symbolic execution

Dan will lead discussion of A Survey of New Trends in Symbolic Execution for Software Testing and Analysis, by Corina S. Păsăreanu and Willem Visser.  This looks like a nice overview as well as having a couple of new twists.

Paper: Symbolic complexity bounds

With apologies for being late in posting this ...

 http://research.microsoft.com/en-us/um/people/sumitg/pubs/cav09_speed.pdf

Related project:
http://research.microsoft.com/en-us/um/people/sumitg/pubs/speed.html

---

Addendum Monday evening: Wow, I didn't understand much of that. It seems that they are describing a bunch of refinements to a basic technique that involves placing a counter variable in the code and then inferring numerical bounds on the counter. Unfortunately I don't understand that basic technique of using counter variables. There are gobs of citations to reference [9], which is a POPL 2009 paper. I had a look at that paper, though not a deep one ... it does seem to be more complete, but it too seems to be building on the basic technique with counters, and again without explanation. I guess it's supposed be something that the intended audience already knows. But I don't.

Anybody know something about this? I'm sure I can track it down, but I'm also pretty sure I can't do it before class tomorrow.

FindBugs papers

The  FindBugs web page (  http://findbugs.sourceforge.net/#papers  ) links to two papers, both presented at PASTE 2007.  They are

• Finding More Null Pointer Bugs, But Not Too Many, by David Hovemeyer, York College of Pennsylvania and William Pugh, Univ. of Maryland, 7th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, June, 2007
• Evaluating Static Analysis Defect Warnings On Production Software, Nathaniel Ayewah and William Pugh, Univ. of Maryland, and J. David Morgenthaler, John Penix and YuQian Zhou, Google, Inc., 7th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, June, 2007 

An earlier paper, from OOPSLA 2004, gives a more thorough description of the basic ideas in FindBugs.  It is

• Hovemeyer, D. and Pugh, W. 2004. Finding bugs is easy. In Companion To the 19th Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications (Vancouver, BC, CANADA, October 24 - 28, 2004). OOPSLA '04. ACM, New York, NY, 132-136. DOI= http://doi.acm.org/10.1145/1028664.1028717

Although the OOPSLA paper is older, I think we need the general overview, so I'd like to suggest we read that one.  But actually I'd like to read that plus the null pointer detection paper, to see how the (fairly simple) pattern detection in the original version of FindBugs is extended and refined to be more effective.

Dysy paper link

It's
Csallner, C., Tillmann, N., and Smaragdakis, Y. 2008. DySy: dynamic symbolic execution for invariant inference. In Proceedings of the 30th international Conference on Software Engineering (Leipzig, Germany, May 10 - 18, 2008). ICSE '08. ACM, New York, NY, 281-290. DOI= http://doi.acm.org/10.1145/1368088.1368127

The background paper on symbolic execution is
King, J. C. 1976. Symbolic execution and program testing. Commun. ACM 19, 7 (Jul. 1976), 385-394. DOI= http://doi.acm.org/10.1145/360248.360252

We will meet in Deschutes 160 (first floor conference room)

I just signed us up for room 160, one floor down from where we were last week.  It has a table, which feels more "seminar-like" to me than the desks in 260 ... and besides, it was available and 260 wasn't.

Reading link, new time

The Daikon paper by Ernst et al is available from his web site here as well as from IEEE.

Tuesday 10am has been proposed as an alternative time to meet.  Please let me know if that does not work for you ... I think it's definitely an improvement over Monday 4pm.  I'm not sure yet about a room, but I'm reasonably confident we can find something.  OK?

Welcome to the Seminar on Program Analysis

I will use this blog in lieu of a course web page to post links to readings, schedule, etc.

We have so far:
    Week 2:  Anthony leading discussion of Ernst's IEEE TSE paper on dynamic invariant detection (Daikon)
    Week 3:  Jed (backup Dan) leading discussion of Csallner's ICSE paper on dynamic symbolic execution in dynamic invariant detection (DySy).

Be sure to fill in the Doodle poll put together by Daniel to find a better seminar meeting time.

The first is
Ernst, M. D., Cockrell, J., Griswold, W. G., and Notkin, D. 2001. Dynamically Discovering Likely Program Invariants to Support Program Evolution. IEEE Trans. Softw. Eng. 27, 2 (Feb. 2001), 99-123. DOI= http://dx.doi.org/10.1109/32.908957

Theoretically this is available through our library, but I'm finding it difficult to use the IEEE digital library from home through the library account.  You should be able to use the DOI link while using a computer at school.