More Web Proxy on the site http://driver.im/

research-article

Lattice based modularization of static analyses

Authors:

G. Salvaneschi,

M. MeziniAuthors Info & Claims

ISSTA '18: Companion Proceedings for the ISSTA/ECOOP 2018 Workshops

Pages 113 - 118

https://doi.org/10.1145/3236454.3236509

Published: 16 July 2018 Publication History

Abstract

Static analyses which compute conceptually independent information, e.g., class immutability or method purity are typically developed as standalone, closed analyses. Complementary information that could improve the analyses is either ignored by making a sound over-approximation or it is also computed by the analyses, but at a rudimentary level. For example, an immutability analysis requires field mutability information, alias/escape information, and information about the concurrent behavior of methods to correctly classify classes like java.lang.String or java.util.BigDecimal. As a result, without properly supporting the integration of independently developed, mutually benefiting analysis, many analyses will not correctly classify relevant entities.

We propose to use explicitly reified lattices that encode the information about a source code element's properties (e.g., a method's purity or a class' immutability) as the sole interface between mutually dependent analyses. This enables the composition of multiple analyses. Our case study shows that using such an approach enables highly scalable, lightweight implementations of modularized static analyses.

References

[1]

S. Arzt, S. Rasthofer, C. Fritz, E. Bodden, A. Bartel, J. Klein, Y. Le Traon, D. Octeau, and P. McDaniel. 2014. FlowDroid: Precise Context, Flow, Field, Object-sensitive and Lifecycle-aware Taint Analysis for Android Apps (PLDI).

Digital Library

[2]

M. Bravenboer and Y. Smaragdakis. 2009. Strictly Declarative Specification of Sophisticated Points-to Analyses (OOPSLA).

Digital Library

[3]

J.-D. Choi, M. Gupta, M. Serrano, V. C. Sreedhar, and S. Midkiff. 1999. Escape Analysis for Java. In OOPSLA.

Digital Library

[4]

P. Cousot and R. Cousot. 2014. Abstract Interpretation: Past, Present and Future (CSL-LICS).

Digital Library

[5]

M. Eichberg, M. Kahl, D. Saha, M. Mezini, and K. Ostermann. 2007. Automatic Incrementalization of Prolog Based Static Analyses (PADL).

Digital Library

[6]

M. Eichberg, M. Mezini, S. Kloppenburg, K. Ostermann, and B. Rank. 2006. Integrating and Scheduling an Open Set of Static Analyses. (ASE).

Digital Library

[7]

Torbjörn Ekman and Görel Hedin. 2007. The Jastadd Extensible Java Compiler (OOPSLA).

Digital Library

[8]

M. Finifter, A. Mettler, N. Sastry, and D. Wagner. 2008. Verifiable functional purity in Java (CCS).

Digital Library

[9]

P. Haller, S. Geries, M. Eichberg, and G. Salvaneschi. 2016. Reactive Async: expressive deterministic concurrency (SCALA).

Digital Library

[10]

W. Huang and A. Milanova. 2012. ReImInfer: Method purity inference for Java (FSE).

Digital Library

[11]

W. Huang, A. Milanova, W. Dietl, and M. D. Ernst. 2012. ReIm & ReImInfer: Checking and inference of reference immutability and method purity (OOPSLA).

Digital Library

[12]

P. Klint, T. van der Storm, and J. J. Vinju. 2009. RASCAL: A Domain Specific Language for Source Code Analysis and Manipulation (SCAM).

Digital Library

[13]

T. Kotzmann and H. Mössenböck. 2005. Escape Analysis in the Context of Dynamic Compilation and Deoptimization (VEE).

Digital Library

[14]

Sorin Lerner, David Grove, and Craig Chambers. 2002. Composing dataflow analyses and transformations (POPL).

Digital Library

[15]

Ralf M. 2014. Scalable Automated Incrementalization for Real-Time Static Analyses. Ph.D. Dissertation. Technische Universität Darmstadt.

[16]

F. Nielson, H. Nielson, and C. Hankin. 2005. Principles of Program Analysis.

Digital Library

[17]

D. Pearce. 2011. JPure: a modular purity system for Java (CC).

Digital Library

[18]

T. Reps, S. Horwitz, and M. Sagiv. 1995. Precise Interprocedural Dataflow Analysis via Graph Reachability (POPL).

Digital Library

[19]

J. Rodriguez and O. Lhoták. 2011. Actor-based parallel dataflow analysis (CC).

Digital Library

[20]

Mooly Sagiv, Thomas Reps, and Susan Horwitz. 1996. Precise interprocedural dataflow analysis with applications to constant propagation. Theoretical Computer Science 167 (1996).

Digital Library

[21]

J. Späth, L. Nguyen Quang Do, K. Ali, and E. Bodden. 2016. Boomerang: Demand-Driven Flow- and Context-Sensitive Pointer Analysis for Java (ECOOP).

Cited By

Helm DRoth TKeidel SReif MMezini MChristakis MPradel M(2024)Unimocg: Modular Call-Graph Algorithms for Consistent Handling of Language FeaturesProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652109(51-62)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652109
Keshani MGousios GProksch S(2023)Frankenstein: fast and lightweight call graph generation for software buildsEmpirical Software Engineering10.1007/s10664-023-10388-729:1Online publication date: 16-Nov-2023
https://dl.acm.org/doi/10.1007/s10664-023-10388-7
Salis VSotiropoulos TLouridas PSpinellis DMitropoulos D(2021)PyCG: Practical Call Graph Generation in Python2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)10.1109/ICSE43902.2021.00146(1646-1657)Online publication date: May-2021
https://doi.org/10.1109/ICSE43902.2021.00146
Show More Cited By

Recommendations

Improving static analyses of C programs with conditional predicates

Static code analysis is increasingly used to guarantee the absence of undesirable behaviors in industrial programs. Designing sound analyses is a continuing trade-off between precision and complexity. Notably, dataflow analyses often perform overly wide ...
Numerical static analysis with Soot
SOAP '13: Proceedings of the 2nd ACM SIGPLAN International Workshop on State Of the Art in Java Program analysis

Numerical static analysis computes an approximation of all the possible values that a numeric variable may assume, in any execution of the program. Many numerical static analyses have been proposed exploiting the theory of abstract interpretation, which ...
Design and implementation of sparse global analyses for C-like languages
PLDI '12: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation

In this article we present a general method for achieving global static analyzers that are precise, sound, yet also scalable. Our method generalizes the sparse analysis techniques on top of the abstract interpretation framework to support relational as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA '18: Companion Proceedings for the ISSTA/ECOOP 2018 Workshops

July 2018

143 pages

ISBN:9781450359399

DOI:10.1145/3236454

Conference Chairs:
Julian Dolby
IBM Thomas J. Watson Research Center
,
William G. J. Halfond
University of Southern California
,
Ashish Mishra
Northeastern University, United States.

Copyright © 2018 ACM.

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSTA '18

Sponsor:

ISSTA '18: International Symposium on Software Testing and Analysis

July 16 - 21, 2018

Amsterdam, Netherlands

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
188
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)5

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Helm DRoth TKeidel SReif MMezini MChristakis MPradel M(2024)Unimocg: Modular Call-Graph Algorithms for Consistent Handling of Language FeaturesProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652109(51-62)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652109
Keshani MGousios GProksch S(2023)Frankenstein: fast and lightweight call graph generation for software buildsEmpirical Software Engineering10.1007/s10664-023-10388-729:1Online publication date: 16-Nov-2023
https://dl.acm.org/doi/10.1007/s10664-023-10388-7
Salis VSotiropoulos TLouridas PSpinellis DMitropoulos D(2021)PyCG: Practical Call Graph Generation in Python2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)10.1109/ICSE43902.2021.00146(1646-1657)Online publication date: May-2021
https://doi.org/10.1109/ICSE43902.2021.00146
Roth THelm DReif MMezini MGrundy J(2021)CiFiProceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE51524.2021.9678903(979-990)Online publication date: 15-Nov-2021
https://dl.acm.org/doi/10.1109/ASE51524.2021.9678903
Reif MKübler FEichberg MHelm DMezini MZhang DMøller A(2019)Judge: identifying, understanding, and evaluating sources of unsoundness in call graphsProceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3293882.3330555(251-261)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.1145/3293882.3330555
Helm DKübler FEichberg MReif MMezini MHuchard MKästner CFraser G(2018)A unified lattice model and framework for purity analysesProceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering10.1145/3238147.3238226(340-350)Online publication date: 3-Sep-2018
https://dl.acm.org/doi/10.1145/3238147.3238226

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents