Summary-based context-sensitive data-dependence analysis in presence of callbacks. (English) Zbl 1346.68066
Proceedings of the 42nd ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’15, Mumbai, India, January 12–18, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3300-9). 83-95 (2015).
MSC:
| 68N30 | Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q45 | Formal languages and automata |
Keywords:
CFL reachability; context-sensitive analysis; summary-based analysis; TAL reachability; tree-adjoining languagesReferences:
| [1] | GitHub Home. https://github.com/. |
| [2] | SPECjvm2008 Benchmark Suite. http://www.spec.org/jvm2008/. |
| [3] | S. A. Bohner and R. S. Arnold. Software Change Impact Analysis. IEEE Computer Society Press, 1996. |
| [4] | S. Chaudhuri. Subcubic algorithms for recursive state machines. In Proc. POPL, pages 159-169, 2008. 10.1145/1328438.1328460 · Zbl 1295.68142 |
| [5] | L. Chen, J. Qian, Y. Zhou, P. Wang, and B. Xu. Identifying extract class refactoring opportunities for internetware. Science China Information Sciences, 57(7):1-18, 2014. |
| [6] | R. Chugh, J. A. Meister, R. Jhala, and S. Lerner. Staged information flow for javascript. In Proc. PLDI, pages 50-62, 2009. 10.1145/1542476.1542483 |
| [7] | I. Dillig, T. Dillig, A. Aiken, and M. Sagiv. Precise and compact modular procedure summaries for heap manipulating programs. In Proc. PLDI, pages 567-577, 2011. 10.1145/1993498.1993565 |
| [8] | G. Gazdar. Applicability of indexed grammars to natural languages. In U. Reyle and C. Rohrer, editors, Natural Language Parsing and Linguistic Theories, pages 69-94, 1988. |
| [9] | S. Horwitz, T. Reps, and M. Sagiv. Demand interprocedural dataflow analysis. In Proc. FSE, pages 104-115, 1995. 10.1145/222124.222146 |
| [10] | S. Itzhaky, N. Bjørner, T. W. Reps, M. Sagiv, and A. V. Thakur. Property-directed shape analysis. In Proc. CAV, pages 35-51, 2014. 10.1007/978-3-319-08867-9_3 |
| [11] | A. K. Joshi, L. S. Levy, and M. Takahashi. Tree adjunct grammars. Journal of Computer and System Sciences, 10(1):136-163, 1975. 10.1016/S0022-0000(75)80019-5 · Zbl 0326.68053 |
| [12] | J. Kodumal and A. Aiken. The set constraint/cfl reachability connection in practice. In Proc. PLDI, pages 207-218, 2004. 10.1145/996841.996867 |
| [13] | J. Kodumal and A. Aiken. Regularly annotated set constraints. In Proc. PLDI, pages 331-341, 2007. 10.1145/1250734.1250772 |
| [14] | R. Komondoor and G. Ramalingam. Recovering data models via guarded dependences. In Proc. WCRE, pages 110-119, 2007. 10.1109/WCRE.2007.40 |
| [15] | D. J. Kuck, R. H. Kuhn, D. A. Padua, B. Leasure, and M. Wolfe. Dependence graphs and compiler optimizations. In Proc. POPL, pages 207-218, 1981. 10.1145/567532.567555 |
| [16] | C. Lattner, A. Lenharth, and V. Adve. Making context-sensitive points- to analysis with heap cloning practical for the real world. In Proc. PLDI, pages 278-289, 2007. 10.1145/1250734.1250766 |
| [17] | A. Lecomte and C. Retoré. Extending lambek grammars: a logical account of minimalist grammars. In Proc. ACL, pages 362-369, 2001. 10.3115/1073012.1073059 |
| [18] | S. Litvak, N. Dor, R. Bodík, N. Rinetzky, and M. Sagiv. Field-sensitive program dependence analysis. In Proc. FSE, pages 287-296, 2010. 10.1145/1882291.1882334 |
| [19] | R. Madhavan, G. Ramalingam, and K. Vaswani. Modular heap analysis for higher-order programs. In Proc. SAS, pages 370-387, 2012. 10.1007/978-3-642-33125-1_25 |
| [20] | D. Melski and T. Reps. Interconvertibility of a class of set constraints and context-free-language reachability. TCS, 248(1-2):29-98, 2000. 10.1016/S0304-3975(00)00049-9 · Zbl 0949.68087 |
| [21] | M. Naik and A. Aiken. Conditional must not aliasing for static race detection. In Proc. POPL, pages 327-338, 2007. 10.1145/1190216.1190265 · Zbl 1295.68073 |
| [22] | M. Pnueli. Two approaches to interprocedural data flow analysis. Program flow analysis: Theory and applications, pages 189-234, 1981. |
| [23] | C. Pollard. Gneralized Phrase Structure Grammars, Head Grammars and Natural Language. PhD thesis, Stanford University, 1984. |
| [24] | P. Pratikakis, J. S. Foster, and M. Hicks. Existential label flow inference via cfl reachability. In Proc. SAS, pages 88-106, 2006. 10.1007/11823230_7 · Zbl 1225.68075 |
| [25] | P. Pratikakis, J. S. Foster, and M. W. Hicks. LOCKSMITH: Context- sensitive correlation analysis for race detection. In Proc. PLDI, pages 320-331, 2006. 10.1145/1133981.1134019 |
| [26] | G. Ramalingam. Context-sensitive synchronization-sensitive analysis is undecidable. TOPLAS, 22(2):416-430, 2000. 10.1145/349214.349241 |
| [27] | J. Rehof and M. Fähndrich. Type-based flow analysis: From poly- morphic subtyping to CFL-reachability. In Proc. POPL, pages 54-66, 2001. 10.1145/360204.360208 · Zbl 1323.68226 |
| [28] | T. Reps. Shape analysis as a generalized path problem. In Proc. PEPM, pages 1-11, 1995. 10.1145/215465.215466 |
| [29] | T. Reps. Program analysis via graph reachability. Information and Software Technology, 40(11-12):701-726, 1998. |
| [30] | T. Reps. Undecidability of context-sensitive data-dependence analysis. TOPLAS, 22(1):162-186, 2000. 10.1145/345099.345137 |
| [31] | T. Reps, S. Horwitz, M. Sagiv, and G. Rosay. Speeding up slicing. In Proc. FSE, pages 11-20, 1994. 10.1145/193173.195287 |
| [32] | T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Proc. POPL, pages 49-61, 1995. 10.1145/199448.199462 |
| [33] | N. Rinetzky, A. Poetzsch-Heffter, G. Ramalingam, M. Sagiv, and E. Yahav. Modular shape analysis for dynamically encapsulated programs. In Proc. ESOP, pages 220-236, 2007. |
| [34] | A. Rountev, S. Kagan, and T. Marlowe. Interprocedural dataflow analysis in the presence of large libraries. In Proc. CC, pages 2-16. Springer, 2006. 10.1007/11688839_2 |
| [35] | M. Sagiv, T. Reps, and S. Horwitz. Precise interprocedural dataflow analysis with applications to constant propagation. TCS, 167(1-2): 131-170, 1996. 10.1016/0304-3975(96)00072-2 · Zbl 0874.68133 |
| [36] | Y. Schabes and K. Vijay-Shanker. Deterministic left to right parsing of tree adjoining languages. In Proc. ACL, pages 276-283, 1990. 10.3115/981823.981858 |
| [37] | M. Sridharan and R. Bodík. Refinement-based context-sensitive points-to analysis for Java. In Proc. PLDI, pages 387-400, 2006. 10.1145/1133981.1134027 |
| [38] | M. Sridharan, D. Gopan, L. Shan, and R. Bodík. Demand-driven points-to analysis for Java. In Proc. OOPSLA, pages 57-76, 2005. 10.1145/1094811.1094817 |
| [39] | M. Steedman. Combinators and grammars. In R. Oehrle, E. Bach, and D. Wheeler, editors, Categorial Grammars and Natural Language Structures, pages 417-442, 1988. |
| [40] | C. Sun, N. Xi, S. Gao, Z. Chen, and J. Ma. Automated enforcement for relaxed information release with reference points. Science China Information Sciences, 57(11):1-19, 2014. · Zbl 1456.68023 |
| [41] | K. Vijay-Shanker and D. J. Weir. The equivalence of four extensions of context-free grammars. Mathematical Systems Theory, 27(6):511-546, 1994. 10.1007/BF01191624 · Zbl 0813.68129 |
| [42] | D. Weir. Characterizing mildly context-sensitive grammar formalisms. PhD thesis, University of Pennsylvania, 1988. |
| [43] | T. Xie, L. Zhang, X. Xiao, Y.-F. Xiong, and D. Hao. Cooperative software testing and analysis: Advances and challenges. JCST, 29(4): 713-723, 2014. |
| [44] | G. Xu and A. Rountev. Merging equivalent contexts for scalable heap- cloning-based context-sensitive points-to analysis. In Proc. ISSTA, pages 225-235, 2008. 10.1145/1390630.1390658 |
| [45] | G. Xu, A. Rountev, and M. Sridharan. Scaling CFL-reachability-based points-to analysis using context-sensitive must-not-alias analysis. In Proc. ECOOP, pages 98-122, 2009. 10.1007/978-3-642-03013-0_6 |
| [46] | M. Yannakakis. Graph-theoretic methods in database theory. In Proc. PODS, pages 230-242, 1990. 10.1145/298514.298576 |
| [47] | X. Zhang, R. Mangal, M. Naik, and H. Yang. Hybrid top-down and bottom-up interprocedural analysis. In Proc. PLDI, pages 249-258, 2014. 10.1145/2594291.2594328 |
| [48] | X. Zheng and R. Rugina. Demand-driven alias analysis for C. In Proc. POPL, pages 351-363, 2008. 10.1145/1328438.1328464 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
