This webpage shows the proposed order of topics to be covered in the course. Under each week (after week 2) there will be 3 papers listed which are the possible choices for each student to present. Some weeks will have more than 3 papers listed as choices, but only 3 will be covered each week. Instructions about selecting at least 2 of these papers over the semester (the total per student depends on our class size), will appear on the top class webpage:
References: Matthew S. Hecht, Flow Analysis of Computer Programs, Ch 9, Monotone Dataflow Frameworks** (book is out of print, but will be on reserve in the library on campus)
Thomas Marlowe & Barbara G. Ryder, “Properties of Data Flow Frameworks: A Unified Model”, Acta Informatica, Vol. 28, pp 121-163, 1990** (a reference work about terms and definitions in dataflow analysis; lots of examples too) available from:
Or any standard compiler textbook, chapter on optimization technology, look at definitions of the classical dataflow problems: reaching definitions, live uses of variables, available expressions
References: Jeanne Ferrante, Karl Ottenstein, & Joe Warren, “The Program Dependence Graph and its Use in Optimization”, ACM TOPLAS vol 9, no 3, July 1987 ** (first sections of the paper have good definitions of data and control dependence. PDG was used to parallelize programs)
S. Horwitz, T. Reps, & D. Binkley, “Interprocedural Slicing Using Dependence Graphs”, PLDI 1988, pp 35-46. (same authors and title, ACM TOPLAS, vol 12, no 1, Jan 1990, pp 26-60).
Jeff Dean, Dave Grove, & Craig Chambers, “Optimization of object-oriented Program using Static Class Hierarchy Analysis”, ECOOP 1995, pp 77-101. (CHA)**
David Bacon & Peter Sweeney, “Fast Static Analysis of C++ Virtual Function Calls”, OOPSLA 1996, pp 324-341, (RTA)**
Ana Milanova, Atanas Rountev, Barbara G. Ryder, “Points-to Analysis for Java Using Annotated Constraints”, OOPSLA 2001**
Dave Grove & Craig Chambers, “Call graph Construction in OO Languages”, OOPSLA 1997. Related later TOPLAS paper: “A Framework for Call Graph Construction Algorithms”, ACM TOPLAS vol 23, no 6, Nov 2001, pp 685-7467
Milanova, A. Rountev, B. G. Ryder, “Parameterized Object Sensitivity for Points-to Analysis for Java”, ISSTA 2002. (Reference: A. Milnova, A. Rountev, B.G. Ryder, “Parameterized Object Sensitivity for Points-to Analysis for Java”, ACM Transactions on Software Engineering Methodology, vol 14, no 1, pp 1-414. January 2005**)
O. Lhotak & L. Hendren, “Context-sensitive Points-to Analysis: is it worth it?”, CC 2006
Y. Smaragdakis, G. Kastrinis, G. Balatsouras, “Introspective Analysis: Context-sensitivity, Across the Board”, PLDI 2014. (Java)
Ball, Thomas, and James R. Larus. Efficient path profiling. Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture. pp. 46-57, 1996.** (selective instrumentation, profiling procedural acyclic paths)
James R. Larus, “Whole Program Path”, PLDI 1999**
Mark Weiser, .Program Slicing. TSE, 1984. (the original static slicing, intraprocedurally precise but interprocedurally imprecise because it does not model calling contexts: Mark Weiser, “Programmers use Slices when Debugging”, CACM vol 25, no 7, pp 446-452, July 1982.**
M. Sridharan, S. Fink, R. Bodik, “Thin Slicing”, PLDI 2007.
Zhang, Xiangyu, Rajiv Gupta, and Youtao Zhang. Precise dynamic slicing algorithms. ICSE, 2003.( best paper award, trace-based dynamic slicing with enhanced precision; three algorithms of same precision but different efficiency)
D. Denning & P.J. Denning, “Certification of Programs for Secure Information Flow”, CACM July 1997, vol 20, no 7**
A. Sabelfeld & A. Myers, “Language-based Information-flow Security”, IEEE Journal on Selected Areas of Communication, Vo 21, No 1, Jan 2003**
D. Wagner and D. Dean, "Intrusion Detection Via Static Analysis", IEEE Symosium on Security and Privacy, 2001, pp 156-169.
W. G. Halfond & A. Orso, “WASP: Protecting Web Applications Using Positive Tainting and Syntax-aware Evaluation”, IEEE TSE, Vol 34, no 1, Jan/Feb 2008.
O. Tripp et al. “TAJ: Effective Taint Analysis of Web Applications”, PLDI 2009
Arzt, Steven, Siegfried Rasthofer, Christian Fritz, Eric Bodden, Alexandre Bartel, Jacques Klein, Yves Le Traon, Damien Octeau, and Patrick McDaniel. Flowdroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps. PLDI, pp. 259-269, 2014. (taint analysis framework for android apps)
Feng, Y., Anand, S., Dillig, I., & Aiken, A. Apposcopy: Semantics-based detection of android malware through static analysis. FSE, pp. 576-587, 2014. (identifying Android malware that steals private user information, using static taint analysis and Inter-component call graph)
S. Yang, D. Yan, H. Wu, Y, Wang, A. Rountev, “Static Control-flow Analysis of User-driven Callbacks in Android Applications”, ICSE 2015.
William Enck et al., “TaintDroid: An Information –flow tracking System for Realtime Privacy Monitoring on Smartphones”, OSDI, 2010.
Roee Hay, Omer Tripp and Marco Pistoia (IBM, Israel; IBM Research, USA), “Dynamic Detection of Inter-application Communication Vulnerabilities in Android.” ISSTA 2015.
J. King, “Symbolic Execution and Program Testing”, CACM 1976**
P. Godefroid, Nils Klarlund, K. Sen “DART: Directed Automated Random Testing”, PLDI 2005**
B. Dufour, B.G. Ryder, and G. Sevitsky, "A Scalable technique for Characterizing the Usagge of Temporaries in Framework-intensive Java Applications", FSE 2008
S. Artzi, A. Keizun, D. Glasser, M. Ernst, "Combined Static and Dynamic Mutability Analysis", ASE 2007.
M.I. Gordon, D. Kim, J. Perkins, l. Gilham, N. Nguyen, and Martin Rinard, "InformationFlow Analysis of Android Applications in DroidSafe", NDSS 2015.
A. Holkner and J. Harland, "Evaluating the dynamic behavior of Python Applications" Proceedings of the 32nd Australian Conference on Compuer Science Volumn 91, 2009.
X. Zhang, R. Gupta, and N. Gupta, "Locating Faults through Automated Predicate Switching", ICSE 2006
Discussion of Ben Livshits et al., "Viewpoint: in Defense of Soundiness: A Manifesto", CACM Vol 58 no 1, Feb 2015
Last edited at 9:35pm on Dec 6,2015