View in EDS HTML Full Text PDF Full Text

Symbol-Specific Sparsification of Interprocedural Distributive Environment Problems.

Saved in:
Bibliographic Details
Title: Symbol-Specific Sparsification of Interprocedural Distributive Environment Problems.
Authors: Karakaya, Kadiray1 kadiray.karakaya@upb.de, Bodden, Eric1,2 eric.bodden@uni-paderborn.de
Source: ICSE: International Conference on Software Engineering. 2024, p1-12. 12p.
Subjects: Data flow computing, Sparse graphs, Graph theory, Algorithms, Algebra
Abstract: Previous work has shown that one can often greatly speed up static analysis by computing data flows not for every edge in the program's control-flow graph but instead only along definition-use chains. This yields a so-called sparse static analysis. Recent work on SparseDroid has shown that specifically taint analysis can be "sparsified" with extraordinary effectiveness because the taint state of one variable does not depend on those of others. This allows one to soundly omit more flow-function computations than in the general case. In this work, we now assess whether this result carries over to the more generic setting of so-called Interprocedural Distributive Environment (IDE) problems. Opposed to taint analysis, IDE comprises distributive problems with large or even infinitely broad domains, such as typestate analysis or linear constant propagation. Specifically, this paper presents Sparse IDE, a framework that realizes sparsification for any static analysis that fits the IDE framework. We implement Sparse IDE in SparseHeros, as an extension to the popular Heros IDE solver, and evaluate its performance on real-world Java libraries by comparing it to the baseline IDE algorithm. To this end, we design, implement and evaluate a linear constant propagation analysis client on top of SparseHeros. Our experiments show that, although IDE analyses can only be sparsified with respect to symbols and not (numeric) values, Sparse IDE can nonetheless yield significantly lower runtimes and often also memory consumptions compared to the original IDE. [ABSTRACT FROM AUTHOR]
Copyright of ICSE: International Conference on Software Engineering is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 185196372
AccessLevel: 6
PubType: Conference
PubTypeId: conference
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Symbol-Specific Sparsification of Interprocedural Distributive Environment Problems.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Karakaya%2C+Kadiray%22">Karakaya, Kadiray</searchLink><relatesTo>1</relatesTo><i> kadiray.karakaya@upb.de</i><br /><searchLink fieldCode="AR" term="%22Bodden%2C+Eric%22">Bodden, Eric</searchLink><relatesTo>1,2</relatesTo><i> eric.bodden@uni-paderborn.de</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22ICSE%3A+International+Conference+on+Software+Engineering%22">ICSE: International Conference on Software Engineering</searchLink>. 2024, p1-12. 12p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Data+flow+computing%22">Data flow computing</searchLink><br /><searchLink fieldCode="DE" term="%22Sparse+graphs%22">Sparse graphs</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+theory%22">Graph theory</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Algebra%22">Algebra</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Previous work has shown that one can often greatly speed up static analysis by computing data flows not for every edge in the program's control-flow graph but instead only along definition-use chains. This yields a so-called sparse static analysis. Recent work on SparseDroid has shown that specifically taint analysis can be "sparsified" with extraordinary effectiveness because the taint state of one variable does not depend on those of others. This allows one to soundly omit more flow-function computations than in the general case. In this work, we now assess whether this result carries over to the more generic setting of so-called Interprocedural Distributive Environment (IDE) problems. Opposed to taint analysis, IDE comprises distributive problems with large or even infinitely broad domains, such as typestate analysis or linear constant propagation. Specifically, this paper presents Sparse IDE, a framework that realizes sparsification for any static analysis that fits the IDE framework. We implement Sparse IDE in SparseHeros, as an extension to the popular Heros IDE solver, and evaluate its performance on real-world Java libraries by comparing it to the baseline IDE algorithm. To this end, we design, implement and evaluate a linear constant propagation analysis client on top of SparseHeros. Our experiments show that, although IDE analyses can only be sparsified with respect to symbols and not (numeric) values, Sparse IDE can nonetheless yield significantly lower runtimes and often also memory consumptions compared to the original IDE. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of ICSE: International Conference on Software Engineering is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=185196372
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1145/3597503.3639092
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 12
        StartPage: 1
    Subjects:
      – SubjectFull: Data flow computing
        Type: general
      – SubjectFull: Sparse graphs
        Type: general
      – SubjectFull: Graph theory
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Algebra
        Type: general
    Titles:
      – TitleFull: Symbol-Specific Sparsification of Interprocedural Distributive Environment Problems.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Karakaya, Kadiray
      – PersonEntity:
          Name:
            NameFull: Bodden, Eric
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 05
              Text: 2024
              Type: published
              Y: 2024
          Titles:
            – TitleFull: ICSE: International Conference on Software Engineering
              Type: main
ResultId 1