skip to main content
10.1145/2676726.2676997acmconferencesArticle/Chapter ViewAbstractPublication PagespoplConference Proceedingsconference-collections
research-article

Summary-Based Context-Sensitive Data-Dependence Analysis in Presence of Callbacks

Published: 14 January 2015 Publication History

Abstract

Building a summary for library code is a common approach to speeding up the analysis of client code. In presence of callbacks, some reachability relationships between library nodes cannot be obtained during library-code summarization. Thus, the library code may have to be analyzed again during the analysis of the client code with the library summary. In this paper, we propose to summarize library code with tree-adjoining-language (TAL) reachability. Compared with the summary built with context-free-language (CFL) reachability, the summary built with TAL reachability further contains conditional reachability relationships. The conditional reachability relationships can lead to much lighter analysis of the library code during the client code analysis with the TAL-reachability-based library summary. We also performed an experimental comparison of context-sensitive data-dependence analysis with the TAL-reachability-based library summary and context-sensitive data-dependence analysis with the CFL-reachability-based library summary using 15 benchmark subjects. Our experimental results demonstrate that the former has an 8X speed-up over the latter on average.

Supplementary Material

MOV File (2676997.mov)

References

[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.
[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.
[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.
[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]
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.
[11]
A. K. Joshi, L. S. Levy, and M. Takahashi. Tree adjunct grammars. Journal of Computer and System Sciences, 10(1):136--163, 1975.
[12]
J. Kodumal and A. Aiken. The set constraint/cfl reachability connection in practice. In Proc. PLDI, pages 207--218, 2004.
[13]
J. Kodumal and A. Aiken. Regularly annotated set constraints. In Proc. PLDI, pages 331--341, 2007.
[14]
R. Komondoor and G. Ramalingam. Recovering data models via guarded dependences. In Proc. WCRE, pages 110--119, 2007.
[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.
[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.
[17]
A. Lecomte and C. Retoré. Extending lambek grammars: a logical account of minimalist grammars. In Proc. ACL, pages 362--369, 2001.
[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.
[19]
R. Madhavan, G. Ramalingam, and K. Vaswani. Modular heap analysis for higher-order programs. In Proc. SAS, pages 370--387, 2012.
[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.
[21]
M. Naik and A. Aiken. Conditional must not aliasing for static race detection. In Proc. POPL, pages 327--338, 2007.
[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.
[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.
[26]
G. Ramalingam. Context-sensitive synchronization-sensitive analysis is undecidable. TOPLAS, 22(2):416--430, 2000.
[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.
[28]
T. Reps. Shape analysis as a generalized path problem. In Proc. PEPM, pages 1--11, 1995.
[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.
[31]
T. Reps, S. Horwitz, M. Sagiv, and G. Rosay. Speeding up slicing. In Proc. FSE, pages 11--20, 1994.
[32]
T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Proc. POPL, pages 49--61, 1995.
[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.
[35]
M. Sagiv, T. Reps, and S. Horwitz. Precise interprocedural dataflow analysis with applications to constant propagation. TCS, 167(1--2): 131--170, 1996.
[36]
Y. Schabes and K. Vijay-Shanker. Deterministic left to right parsing of tree adjoining languages. In Proc. ACL, pages 276--283, 1990.
[37]
M. Sridharan and R. Bodík. Refinement-based context-sensitive points-to analysis for Java. In Proc. PLDI, pages 387--400, 2006.
[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.
[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.
[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.
[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.
[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.
[46]
M. Yannakakis. Graph-theoretic methods in database theory. In Proc. PODS, pages 230--242, 1990.
[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.
[48]
X. Zheng and R. Rugina. Demand-driven alias analysis for C. In Proc. POPL, pages 351--363, 2008.

Cited By

View all
  • (2024)Better Not Together: Staged Solving for Context-Free Language ReachabilityProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680346(1112-1123)Online publication date: 11-Sep-2024
  • (2024) Octopus: Scaling Value-Flow Analysis via Parallel Collection of Realizable Path ConditionsACM Transactions on Software Engineering and Methodology10.1145/363274333:3(1-33)Online publication date: 24-Jan-2024
  • (2024)LibAlchemy: A Two-Layer Persistent Summary Design for Taming Third-Party Libraries in Static Bug-Finding SystemsProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639132(1-13)Online publication date: 20-May-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
POPL '15: Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
January 2015
716 pages
ISBN:9781450333009
DOI:10.1145/2676726
  • cover image ACM SIGPLAN Notices
    ACM SIGPLAN Notices  Volume 50, Issue 1
    POPL '15
    January 2015
    682 pages
    ISSN:0362-1340
    EISSN:1558-1160
    DOI:10.1145/2775051
    • Editor:
    • Andy Gill
    Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 January 2015

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. cfl reachability
  2. context-sensitive analysis
  3. summary-based analysis
  4. tal reachability
  5. tree adjoining languages

Qualifiers

  • Research-article

Funding Sources

Conference

POPL '15
Sponsor:

Acceptance Rates

POPL '15 Paper Acceptance Rate 52 of 227 submissions, 23%;
Overall Acceptance Rate 860 of 4,328 submissions, 20%

Upcoming Conference

POPL '26

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)53
  • Downloads (Last 6 weeks)6
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Better Not Together: Staged Solving for Context-Free Language ReachabilityProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680346(1112-1123)Online publication date: 11-Sep-2024
  • (2024) Octopus: Scaling Value-Flow Analysis via Parallel Collection of Realizable Path ConditionsACM Transactions on Software Engineering and Methodology10.1145/363274333:3(1-33)Online publication date: 24-Jan-2024
  • (2024)LibAlchemy: A Two-Layer Persistent Summary Design for Taming Third-Party Libraries in Static Bug-Finding SystemsProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639132(1-13)Online publication date: 20-May-2024
  • (2024)Partial program analysis for staged compilation systemsFormal Methods in System Design10.1007/s10703-024-00458-xOnline publication date: 13-Jun-2024
  • (2023)Recursive State Machine Guided Graph Folding for Context-Free Language ReachabilityProceedings of the ACM on Programming Languages10.1145/35912337:PLDI(318-342)Online publication date: 6-Jun-2023
  • (2023)ODDFuzz: Discovering Java Deserialization Vulnerabilities via Structure-Aware Directed Greybox Fuzzing2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179377(2726-2743)Online publication date: May-2023
  • (2022)Indexing the extended Dyck-CFL reachability for context-sensitive program analysisProceedings of the ACM on Programming Languages10.1145/35633396:OOPSLA2(1438-1468)Online publication date: 31-Oct-2022
  • (2022)Modular information flow through ownershipProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523445(1-14)Online publication date: 9-Jun-2022
  • (2022)Efficient algorithms for dynamic bidirected Dyck-reachabilityProceedings of the ACM on Programming Languages10.1145/34987246:POPL(1-29)Online publication date: 12-Jan-2022
  • (2022)Fast Graph Simplification for Interleaved-Dyck ReachabilityACM Transactions on Programming Languages and Systems10.1145/349242844:2(1-28)Online publication date: 27-May-2022
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media