You are required to read and agree to the below before accessing a full-text version of an article in the IDE article repository.
The full-text document you are about to access is subject to national and international copyright laws. In most cases (but not necessarily all) the consequence is that personal use is allowed given that the copyright owner is duly acknowledged and respected. All other use (typically) require an explicit permission (often in writing) by the copyright owner.
For the reports in this repository we specifically note that
- the use of articles under IEEE copyright is governed by the IEEE copyright policy (available at http://www.ieee.org/web/publications/rights/copyrightpolicy.html)
- the use of articles under ACM copyright is governed by the ACM copyright policy (available at http://www.acm.org/pubs/copyright_policy/)
- technical reports and other articles issued by M‰lardalen University is free for personal use. For other use, the explicit consent of the authors is required
- in other cases, please contact the copyright owner for detailed information
By accepting I agree to acknowledge and respect the rights of the copyright owner of the document I am about to access.
If you are in doubt, feel free to contact webmaster@ide.mdh.se
Static Backward Demand-Driven Slicing
Publication Type:
Conference/Workshop Paper
Venue:
ACM Sigplan-Sigact Symposium on Partial Evaluation and Program Manipulation
DOI:
10.1145/2678015.2682538
Abstract
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.
Bibtex
@inproceedings{Lisper3798,
author = {Bj{\"o}rn Lisper and Abu Naser Masud and Husni Khanfar},
title = {Static Backward Demand-Driven Slicing},
isbn = {978-1-4503-3297-2},
pages = {115--126},
month = {January},
year = {2015},
booktitle = {ACM Sigplan-Sigact Symposium on Partial Evaluation and Program Manipulation},
publisher = {ACM},
url = {http://www.es.mdu.se/publications/3798-}
}