mdh.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
Static Backward Demand-Driven Slicing
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0001-5297-6548
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-4872-1208
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0001-9410-1344
2015 (English)In: PEPM '15 Proceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation, 2015, 115-126 p.Conference paper, Published paper (Refereed)
Abstract [en]

Program slicing identifies the program parts that may affect certain properties of the program, such as the outcomes of conditions affecting the program flow. Ottenstein’s Program Dependence Graph (PDG) based algorithm is the state-of-practice for static slicing today: it is well-suited in applications where many slices are computed, since the cost of building the PDG then can be amortized over the slices. But there are applications that require few slices of a given program, and where computing all the dependencies may be unnecessary. We present a light-weight interprocedural algorithm for backward static slicing where the data dependence analysis is done using a variant of the Strongly Live Variables (SLV) analysis. This allows us to avoid building the Data Dependence Graph, and to slice program statements “on-the-fly” during the SLV analysis which is potentially faster for computing few slices. Furthermore we use an abstract interpretation-based value analysis to extend our slicing algorithm to slice low-level code, where data dependencies are not evident due to dynamically calculated addresses. Our algorithm computes slices as sets of Control Flow Graph nodes: we show how to adapt existing techniques to generate executable slices that correspond to semantically correct code, where jump statements have been inserted at appropriate places. We have implemented our slicing algorithms, and made an experimental evaluation comparing them with the standard PDG-based algorithm for a number of example programs. We obtain the same accuracy as for PDG-based slicing, sometimes with substantial improvements in performance.

Place, publisher, year, edition, pages
2015. 115-126 p.
Keyword [en]
Static backward slicing, Unstructured control flow, Data flow equations, Computational complexity, Strongly live variable, Abstract Interpretation
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:mdh:diva-28103DOI: 10.1145/2678015.2682538Scopus ID: 2-s2.0-84947975458ISBN: 978-1-4503-3297-2 (print)OAI: oai:DiVA.org:mdh-28103DiVA: diva2:819879
Conference
ACM Sigplan-Sigact Symposium on Partial Evaluation and Program Manipulation PEPM, 12-18 Jan 2015, Mumbai, India
Projects
APARTS - Advanced Program Analysis for Real-Time SystemsSYNOPSIS - Safety Analysis for Predictable Software Intensive SystemsTOCSYC - Testing of Critical System Characteristics (KKS)
Available from: 2015-06-11 Created: 2015-06-08 Last updated: 2016-10-31Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Lisper, BjörnMasud, Md Abu NaserKhanfar, Husni

Search in DiVA

By author/editor
Lisper, BjörnMasud, Md Abu NaserKhanfar, Husni
By organisation
Embedded Systems
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 22 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