lnu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Gutzmann, Tobias
Publications (10 of 14) Show all publications
Gutzmann, T. (2013). Benchmarking Points-to Analysis. (Doctoral dissertation). Linnaeus University Press
Open this publication in new window or tab >>Benchmarking Points-to Analysis
2013 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

Points-to analysis is a static program analysis that, simply put, computes which objects created at certain points of a given program might show up at which other points of the same program. In particular, it computes possible targets of a call and possible objects referenced by a field. Such information is essential input to many client applications in optimizing compilers and software engineering tools.

Comparing experimental results with respect to accuracy and performance is required in order to distinguish the promising from the less promising approaches to points-to analysis. Unfortunately, comparing the accuracy of two different points-to analysis implementations is difficult, as there are many pitfalls in the details. In particular, there are no standardized means to perform such a comparison, i.e, no benchmark suite - a set of programs with well-defined rules of how to compare different points-to analysis results - exists. Therefore, different researchers use their own means to evaluate their approaches to points-to analysis. To complicate matters, even the same researchers do not stick to the same evaluation methods, which often makes it impossible to take two research publications and reliably tell which one describes the more accurate points-to analysis.

In this thesis, we define a methodology on how to benchmark points-to analysis. We create a benchmark suite, compare three different points-to analysis implementations with each other based on this methodology, and explain differences in analysis accuracy.

We also argue for the need of a Gold Standard, i.e., a set of benchmark programs with exact analysis results. Such a Gold Standard is often required to compare points-to analysis results, and it also allows to assess the exact accuracy of points-to analysis results. Since such a Gold Standard cannot be computed automatically, it needs to be created semi-automatically by the research community. We propose a process for creating a Gold Standard based on under-approximating it through optimistic (dynamic) analysis and over-approximating it through conservative (static) analysis. With the help of improved static and dynamic points-to analysis and expert knowledge about benchmark programs, we present a first attempt towards a Gold Standard.

We also provide a Web-based benchmarking platform, through which researchers can compare their own experimental results with those of other researchers, and can contribute towards the creation of a Gold Standard.

Place, publisher, year, edition, pages
Linnaeus University Press, 2013
Series
Linnaeus University Dissertations ; 133/2013
Keywords
Points-to Analysis, Dataflow Analysis, Static Analysis, Dynamic Analysis, Gold Standard
National Category
Computer Sciences
Research subject
Computer Science, Software Technology
Identifiers
urn:nbn:se:lnu:diva-25298 (URN)978-91-87427-25-1 (ISBN)
Public defence
2013-05-17, M1083, Hus M, Växjö, 13:00 (English)
Opponent
Supervisors
Available from: 2013-04-12 Created: 2013-04-11 Last updated: 2018-01-11Bibliographically approved
Gutzmann, T., Lundberg, J. & Löwe, W. (2012). Collections Frameworks for Points-to Analysis. In: IEEE 12th International Working Conference on Source Code Analysis and Manipulation (SCAM) 2012: . Paper presented at Twelfth IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2012), 23-24 Sept, 2012, Riva del Garda, Italy (pp. 4-13). IEEE
Open this publication in new window or tab >>Collections Frameworks for Points-to Analysis
2012 (English)In: IEEE 12th International Working Conference on Source Code Analysis and Manipulation (SCAM) 2012, IEEE, 2012, p. 4-13Conference paper, Published paper (Refereed)
Abstract [en]

Points-to information is the basis for many analysesand transformations, e.g., for program understanding andoptimization. Collections frameworks are part of most modern programming languages’ infrastructures and used by many applications. The richness of features and the inherent structure of collection classes affect both performance and precision of points-to analysis negatively.

In this paper, we discuss how to replace original collections frameworks with versions specialized for points-to analysis. We implement such a replacement for the Java Collections Framework and support its benefits for points-to analysis by applying it to three different points-to analysis implementations. In experiments, context-sensitive points-to analyses require, on average, 16-24% less time while at the same time being more precise. Context-insensitive analysis in conjunction with inlining also benefits in both precision and analysis cost.

Place, publisher, year, edition, pages
IEEE, 2012
Keywords
Points-to analysis, collections frameworks
National Category
Computer Sciences
Research subject
Computer and Information Sciences Computer Science, Computer Science
Identifiers
urn:nbn:se:lnu:diva-22027 (URN)10.1109/SCAM.2012.24 (DOI)2-s2.0-84872300572 (Scopus ID)978-1-4673-2398-7 (ISBN)
Conference
Twelfth IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2012), 23-24 Sept, 2012, Riva del Garda, Italy
Available from: 2012-10-12 Created: 2012-10-12 Last updated: 2018-05-17Bibliographically approved
Gutzmann, T. & Löwe, W. (2011). Custom-made Instrumentation Based on Static Analysis. In: WODA 2011: Ninth International Workshop on Dynamic Analysis (pp. 18-23).
Open this publication in new window or tab >>Custom-made Instrumentation Based on Static Analysis
2011 (English)In: WODA 2011: Ninth International Workshop on Dynamic Analysis, 2011, p. 18-23Conference paper, Published paper (Refereed)
Abstract [en]

Many dynamic analysis tools capture the occurrences of events at runtime. The longer programs are being monitored, the more accurate the data they provide to the user. Then, the runtime overhead must be kept as low as possible, because it decreases the user's productivity. Runtime performance overhead occurs due to identifying events, and storing them in a result data-structure. We address the latter issue by generating custom-made instrumentation code for each program. By using static analysis to get a~priori knowledge about which events of interest can occur and where they can occur, tailored code for storing those events can be generated for each program. We evaluate our idea by comparing the runtime overhead of a general purpose dynamic analysis tool that captures points-to information for Java programs with approaches based on custom-made instrumentation code. Experiments suggest highly reduced performance overhead for the latter.

Keywords
Dynamic analysis, static analysis, points-to analysis
National Category
Computer Sciences
Research subject
Computer and Information Sciences Computer Science, Computer Science
Identifiers
urn:nbn:se:lnu:diva-13633 (URN)
Available from: 2011-07-31 Created: 2011-07-31 Last updated: 2018-01-12Bibliographically approved
Gutzmann, T., Lundberg, J. & Löwe, W. (2011). Feedback-driven Points-to Analysis. In: 26th Symposium On Applied Computing (SAC 2011), TaiChung, March 21-24, 2011.
Open this publication in new window or tab >>Feedback-driven Points-to Analysis
2011 (English)In: 26th Symposium On Applied Computing (SAC 2011), TaiChung, March 21-24, 2011, 2011Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, we present feedback-driven points-to analysis where any classical points-to analysis has its points-to results at certain program points guarded by a-priori upper bounds. Such upper bounds can come from other points-to analyses – this is of interest when different approaches are not strictlyordered in terms of accuracy – and from human insight, i.e., manual proofs that certain points-to relations are infeasible for every program run.

Keywords
Points-to analysis, expert knowledge
National Category
Computer Sciences
Research subject
Computer and Information Sciences Computer Science, Computer Science
Identifiers
urn:nbn:se:lnu:diva-9225 (URN)
Available from: 2010-11-02 Created: 2010-11-02 Last updated: 2018-05-17Bibliographically approved
Gutzmann, T., Lundberg, J. & Löwe, W. (2010). Feedback-driven Points-to Analysis.
Open this publication in new window or tab >>Feedback-driven Points-to Analysis
2010 (English)Report (Other academic)
Abstract [en]

Points-to analysis is a static program analysis that extracts reference information from agiven input program. Its accuracy is limited due to abstractions that any such analysisneeds to make. Further, the exact analysis results are unknown, i.e., no so-called GoldStandard exists for points-to analysis. This hinders the assessment of new ideas to pointstoanalysis, as results can be compared only relative to results obtained by other inaccurateanalyses.

In this paper, we present feedback-driven points-to analysis. We suggest performing(any classical) points-to analysis with the points-to results at certain programpoints guarded by a-priori upper bounds. Such upper bounds can come from other pointstoanalyses – this is of interest when different approaches are not strictly ordered in termsof accuracy – and from human insight, i.e., manual proofs that certain points-to relationsare infeasible for every program run. This gives us a tool at hand to compute very accuratepoints-to analysis and, ultimately, to manually create a Gold Standard.

Publisher
p. 12
National Category
Computer Sciences
Research subject
Computer and Information Sciences Computer Science; Computer and Information Sciences Computer Science, Computer Science
Identifiers
urn:nbn:se:lnu:diva-9212 (URN)
Available from: 2010-11-01 Created: 2010-11-01 Last updated: 2018-05-17Bibliographically approved
Gutzmann, T. & Löwe, W. (2010). Reducing the Performance Overhead of Dynamic Analysis through Custom-made Agents. In: 5th International Workshop on Program Comprehension through Dynamic Analysis (PCODA 2010) (pp. 1-6).
Open this publication in new window or tab >>Reducing the Performance Overhead of Dynamic Analysis through Custom-made Agents
2010 (English)In: 5th International Workshop on Program Comprehension through Dynamic Analysis (PCODA 2010), 2010, p. 1-6Conference paper, Published paper (Refereed)
Abstract [en]

The usefulness of dynamic analysis tools for programcomprehension increases with the amount oftime a given analyzed program is monitored. Thus, monitoring the analyzed program in a production environment should give the best picture of how the program actually works. However, high performance overhead is especially undesirable in such a setting, because it decreases the user’s productivity. Performance overhead occurs due to recognizing events that are of interest to the agent monitoring the program run and storing those events in data-structures. We propose to address this issue by creating a custom-made agent for each program. By using static analysis to get a priori knowledge about which events of interest can occur and where they can occur, tailored code for recognizing and storing those events can be generated for each program. We evaluate our idea by comparing a "general purpose" dynamic agent that captures fine-grained points-to information with custom-made agents that do the same job for specific programs. The latter show highly reduced performance overhead in practice. We also investigate how the precision of the static analysis affects the performance of the custom-made agents.

Keywords
Dynamic analysis, static analysis, points-to analysis
National Category
Computer Sciences
Research subject
Computer and Information Sciences Computer Science, Computer Science
Identifiers
urn:nbn:se:lnu:diva-9223 (URN)
Available from: 2010-11-02 Created: 2010-11-02 Last updated: 2018-01-12Bibliographically approved
Lincke, R., Gutzmann, T. & Löwe, W. (2010). Software Quality Prediction Models Compared. In: Software Quality Prediction Models Compared: . Paper presented at The 10th International Conference on Quality Software.
Open this publication in new window or tab >>Software Quality Prediction Models Compared
2010 (English)In: Software Quality Prediction Models Compared, 2010Conference paper, Published paper (Refereed)
Abstract [en]

Numerous empirical studies confirm that many software metrics aggregated in software quality prediction models are valid predictors for qualities of general interest like maintainability and correctness. Even these general quality models differ quite a bit, which raises the question: Do the differences matter? The goal of our study is to answer this question for a selection of quality models that have previously been published in empirical studies. We compare these quality models statistically by applying them to the same set of software systems, i.e., to altogether 328 versions of 11 open-source software systems. Finally, we draw conclusions from quality assessment using the different quality models, i.e., we calculate a quality trend and compare these conclusions statistically. We identify significant differences among the quality models. Hence, the selection of the quality model has influence on the quality assessment of software based on software metrics.

National Category
Computer Sciences
Research subject
Computer and Information Sciences Computer Science, Computer Science
Identifiers
urn:nbn:se:lnu:diva-6038 (URN)
Conference
The 10th International Conference on Quality Software
Available from: 2010-06-10 Created: 2010-06-10 Last updated: 2018-01-12Bibliographically approved
Gutzmann, T. (2010). Towards a Gold Standard for Points-to Analysis. (Licentiate dissertation).
Open this publication in new window or tab >>Towards a Gold Standard for Points-to Analysis
2010 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

Points-to analysis is a static program analysis that computes reference informationfor a given input program. It serves as input to many client applicationsin optimizing compilers and software engineering tools. Unfortunately, the Gold Standard – i.e., the exact reference information for a given program– is impossible to compute automatically for all but trivial cases, and thus, little can been said about the accuracy of points-to analysis.

This thesis aims at paving the way towards a Gold Standard for points-to analysis. For this, we discuss theoretical implications and practical challenges that occur when comparing results obtained by different points-to analyses. We also show ways to improve points-to analysis by different means, e.g., combining different analysis implementations, and a novel approach to path sensitivity.

We support our theories with a number of experiments.

Publisher
p. 111
Keywords
Points-to Analysis, Dataflow Analysis, Static Analysis, Dynamic Analysis, Gold Standard
Research subject
Computer and Information Sciences Computer Science
Identifiers
urn:nbn:se:vxu:diva-7381 (URN)
Presentation
2010-03-05, Weber, 13:15 (English)
Opponent
Supervisors
Available from: 2010-03-03 Created: 2010-02-27 Last updated: 2014-05-08Bibliographically approved
Gutzmann, T. & Steijger, T. (2009). Backporting Java 5 Code. In: Ninth IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2009): (pp. 121-122).
Open this publication in new window or tab >>Backporting Java 5 Code
2009 (English)In: Ninth IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2009), 2009, p. 121-122Conference paper, Published paper (Refereed)
Abstract [en]

Java 5 has introduced a number of new syntactical language features that make development faster, easier, and safer. However, at the same time, it has also introduced downward incompatibilities: code written for Java 5 cannot be used on pre-Java 5 platforms. This tool demonstration presents a number of source-to-source transformations that backport source code written for the Java 5 platform to legacy platforms. Developers who are, for different reasons, still bound to legacy platforms can benefit with help of this tool from the new language features, and they can use thirdparty components written for more recent platforms. Compared to existing tools, ours is the first that can backport all new syntactical Java 5 language features while the user maintains full control of the source code.

National Category
Computer and Information Sciences
Research subject
Computer and Information Sciences Computer Science
Identifiers
urn:nbn:se:vxu:diva-6004 (URN)10.1109/SCAM.2009.21 (DOI)978-0-7695-3793-1 (ISBN)
Note

Tool demonstration

Available from: 2009-10-08 Created: 2009-10-08 Last updated: 2018-01-13Bibliographically approved
Lundberg, J., Gutzmann, T., Edvinsson, M. & Löwe, W. (2009). Fast and Precise Points-to Analysis. Information and Software Technology, 51(10), 1428-1439
Open this publication in new window or tab >>Fast and Precise Points-to Analysis
2009 (English)In: Information and Software Technology, ISSN 0950-5849, E-ISSN 1873-6025, Vol. 51, no 10, p. 1428-1439Article in journal (Refereed) Published
Abstract [en]

Many software engineering applications require points-to analysis. These client applications range from optimizing compilers to integrated program development environments (IDEs) and from testing environments to reverse-engineering tools. Moreover, software engineering applications used in an edit-compile cycle need points-to analysis to be fast and precise.

In this article, we present a new context- and flow-sensitive approach to points-to analysis where calling contexts are distinguished by the points-to sets analyzed for their call target expressions. Compared to other well-known context-sensitive techniques it is faster in practice, on average, twice as fast as the call string approach and by an order of magnitude faster than the object-sensitive technique. In fact, it shows to be only marginally slower than a context-insensitive baseline analysis. At the same time, it provides higher precision than the call string technique and is similar in precision to the object-sensitive technique. We confirm these statements with experiments using a number of abstract precision metrics and a concrete client application: escape analysis.

Keywords
Points-to analysis; Dataflow analysis; Escape analysis
National Category
Computer Sciences
Research subject
Computer and Information Sciences Computer Science
Identifiers
urn:nbn:se:vxu:diva-5907 (URN)10.1016/j.infsof.2009.04.012 (DOI)
Available from: 2009-09-25 Created: 2009-09-25 Last updated: 2018-05-17Bibliographically approved
Organisations

Search in DiVA

Show all publications