lnu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
Memory efficient context-sensitive program analysis
Linnaeus University, Faculty of Technology, Department of computer science and media technology (CM). (DISA;DISTA)ORCID iD: 0000-0002-7555-7335
Linnaeus University, Faculty of Technology, Department of computer science and media technology (CM). (DISA;DISTA)ORCID iD: 0000-0001-9775-4594
Linnaeus University, Faculty of Technology, Department of computer science and media technology (CM). (DISA;DISTA)ORCID iD: 0000-0002-7565-3714
2021 (English)In: Journal of Systems and Software, ISSN 0164-1212, E-ISSN 1873-1228, Vol. 177, article id 110952Article in journal (Refereed) Published
Abstract [en]

Static program analysis is in general more precise if it is sensitive to execution contexts (execution paths). But then it is also more expensive in terms of memory consumption. For languages with conditions and iterations, the number of contexts grows exponentially with the program size. This problem is not just a theoretical issue. Several papers evaluating inter-procedural context-sensitive data-flow analysis report severe memory problems, and the path-explosion problem is a major issue in program verification and model checking.

In this paper we propose χ-terms as a means to capture and manipulate context-sensitive program information in a data-flow analysis. χ-terms are implemented as directed acyclic graphs without any redundant subgraphs.

To show the efficiency of our approach we run experiments comparing the memory usage of χ-terms with four alternative data structures. Our experiments show that χ-terms clearly outperform all the alternatives in terms of memory efficiency.

Place, publisher, year, edition, pages
Elsevier, 2021. Vol. 177, article id 110952
Keywords [en]
Static program analysis, Data-flow analysis, Context-sensitivity
National Category
Computer Sciences
Research subject
Computer and Information Sciences Computer Science, Computer Science
Identifiers
URN: urn:nbn:se:lnu:diva-102450DOI: 10.1016/j.jss.2021.110952ISI: 000641355800001Scopus ID: 2-s2.0-85103928999Local ID: 2021OAI: oai:DiVA.org:lnu-102450DiVA, id: diva2:1547376
Available from: 2021-04-26 Created: 2021-04-26 Last updated: 2021-05-27Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Hedenborg, MathiasLundberg, JonasLöwe, Welf

Search in DiVA

By author/editor
Hedenborg, MathiasLundberg, JonasLöwe, Welf
By organisation
Department of computer science and media technology (CM)
In the same journal
Journal of Systems and Software
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 97 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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