UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Evaluating Lexical Approximation of Program Dependence

Lee, S; Binkley, D; Gold, N; Islam, S; Krinke, J; Yoo, S; (2020) Evaluating Lexical Approximation of Program Dependence. Journal of Systems and Software , 160 , Article 110459. 10.1016/j.jss.2019.110459. Green open access

Gold_Evaluating Lexical Approximation of Program Dependence_AAM.pdf - Accepted version

Download (509kB) | Preview


Complex dependence analysis typically provides an underpinning approximation of true program dependence. We investigate the effectiveness of using lexical information to approximate such dependence, introducing two new deletion operators to Observation-Based Slicing (ORBS). ORBS provides direct observation of program dependence, computing a slice using iterative, speculative deletion of program parts. Deletions become permanent if they do not affect the slicing criterion. The original ORBS uses a bounded deletion window operator that attempts to delete consecutive lines together. Our new deletion operators attempt to delete multiple, non-contiguous lines that are lexically similar to each other. We evaluate the lexical dependence approximation by exploring the trade-off between the precision and the speed of dependence analysis performed with new deletion operators. The deletion operators are evaluated independently, as well as collectively via a novel generalization of ORBS that exploits multiple deletion operators: Multi-operator Observation-Based Slicing (MOBS). An empirical evaluation using three Java projects, six C projects, and one multi-lingual project written in Python and C finds that the lexical information provides a useful approximation to the underlying dependence. On average, MOBS can delete 69% of lines deleted by the original ORBS, while taking only 36% of the wall clock time required by ORBS.

Type: Article
Title: Evaluating Lexical Approximation of Program Dependence
Open access status: An open access version is available from UCL Discovery
DOI: 10.1016/j.jss.2019.110459
Publisher version: https://doi.org/10.1016/j.jss.2019.110459
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: ORBSM, Program slicing, Lexical analysis
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10085557
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item