lnu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
SSA-Based Simulated Execution
Linnaeus University, Faculty of Science and Engineering, School of Computer Science, Physics and Mathematics. (Computer Science)
Linnaeus University, Faculty of Science and Engineering, School of Computer Science, Physics and Mathematics. (Computer Science)
Linnaeus University, Faculty of Science and Engineering, School of Computer Science, Physics and Mathematics. (Computer Science)ORCID iD: 0000-0002-7565-3714
2012 (English)In: Patterns, Programming and Everything / [ed] Karin K. Breitman och R. Nigel Horspool, London: Springer, 2012, 75-90 p.Chapter in book (Refereed)
Abstract [en]

Most scalable approaches to inter-procedural dataflow analysis do not take into account the order in which fields are accessed, and methods are executed, at run-time. That is, they have no inter-procedural flow-sensitivity. In this chapter we present an approach to dataflow analysis named \emph{Simulated Execution}. It is flow-sensitive in the sense that a memory accessing operation (call or field access) will never be affected by another memory access that is executed there after in all runs of a program. This makes Simulated Execution strictly more precise than the most frequently used flow-insensitive approaches. We also outline a proof of correctness using abstract interpretation. Finally, although we present Simulated Execution as a dataflow algorithm applied to context-insensitive Points-to Analysis, it can be applied on any inter-procedural dataflow problem and in a context-sensitive manner.

Place, publisher, year, edition, pages
London: Springer, 2012. 75-90 p.
National Category
Computer Science
Research subject
Computer and Information Sciences Computer Science, Computer Science
Identifiers
URN: urn:nbn:se:lnu:diva-19151DOI: 10.1007/978-1-4471-2350-7ISBN: 978-1-4471-2349-1 (print)ISBN: 978-1-4471-2350-7 (print)OAI: oai:DiVA.org:lnu-19151DiVA: diva2:529909
Available from: 2012-05-31 Created: 2012-05-31 Last updated: 2017-01-27Bibliographically approved
In thesis
1. Fast and Precise Points-to Analysis
Open this publication in new window or tab >>Fast and Precise Points-to Analysis
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
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. The software engineering applications are often user-interactive, or used in an edit-compile cycle, and need the points-to analysis to be fast and precise.

In this compilation thesis, we present a new context- and flow-sensitive approach to points-to analysis that is both fast and precise. This is accomplished by a new SSA-based flow-sensitive dataflow algorithm (Paper 1) and a new context-sensitive analysis (Paper 2). Compared to other well-known analysis approaches our approach 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 in Paper 2.

Paper 3 is a systematic comparison of ten different variants of context-sensitive points-to analysis using different call-depths  for separating the contexts. Previous works indicate that analyses with a call-depth  only provides slightly better precision than context-insensitive analysis and they find no substantial precision improvement when using a more expensive analyses with call-depth . The hypothesis in Paper 3 is that substantial differences between the context-sensitive approaches show if (and only if) the precision is measured by more fine-grained metrics focusing on individual objects (rather than methods and classes) and references between them. These metrics are justified by the many applications requiring such detailed object reference information.

The main results in Paper 3 show that the differences between different context-sensitive analysis techniques are substantial, also the differences between the context-insensitive and the context-sensitive analyses with call-depth are substantial. The major surprise was that increasing the call-depth  did not lead to any substantial precision improvements. This is a negative result since it indicates that, in practice, we cannot get a more precise points-to analysis by increasing the call-depth. Further investigations show that substantial precision improvements can be detected for but they occur at such a low detail level that they are unlikely to be of any practical use.

Place, publisher, year, edition, pages
Växjö: Linnaeus University Press, 2014. 52 p.
Series
Linnaeus University Dissertations, 175/2014
National Category
Computer Science
Research subject
Computer and Information Sciences Computer Science, Computer Science
Identifiers
urn:nbn:se:lnu:diva-36236 (URN)978-91-87427-89-3 (ISBN)
Public defence
2014-06-13, M1083, Södrasalen, Hus M, Växjö, 13:00 (English)
Opponent
Supervisors
Available from: 2014-08-21 Created: 2014-08-02 Last updated: 2017-01-27Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Lundberg, JonasHedenborg, MathiasLöwe, Welf
By organisation
School of Computer Science, Physics and Mathematics
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 157 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf