ORBS: Language-Independent Program Slicing

Current slicing techniques cannot handle systems written in multiple programming languages. Observation-Based Slicing (ORBS) is a language-independent slicing technique capable of slicing multi-language systems, including systems which contain (third party) binary components. A potential slice obtained through repeated statement deletion is validated by observing the behaviour of the program: if the slice and original program behave the same under the slicing criterion, the deletion is accepted. The resulting slice is similar to a dynamic slice. We evaluate five variants of ORBS on ten programs of different sizes and languages showing that it is less expensive than similar existing techniques. We also evaluate it on bash and four other systems to demonstrate feasible large-scale operation in which a parallelised ORBS needs up to 82% less time when using four threads. The results show that an ORBS slicer is simple to construct, effective at slicing, and able to handle systems written in multiple languages without specialist analysis tools.

ORBS is described in detail in:

D. Binkley, N. Gold, M. Harman, S. Islam, J. Krinke, S. Yoo: ORBS: Language-Independent Program Slicing. Foundations of Software Engineering (FSE), Hong Kong, China, November 2014.
[PDF] ©ACM, 2014.
(Supersedes Research Note RN/13/13, 2013.)

The generated slices as presented in the above paper is available for download.  If you use the data for your own research, please cite the above FSE 2014 paper.

This work was in part funded by the EPSRC (EP/G060525/2) and the NSF (CCF 0916081).  Data from the EPSRC-funded parts are available from Jens Krinke subject to licence and confidentiality restrictions.

The ORBS system as presented in the above paper is available for download below.

ORBS v1.0

Copyright (c) 2014 University College London

This software is licensed under GPL version 3 and may be redistributed strictly under the terms of that licence a copy of which can be found here. If you are interested in a commercial licence for commercial redistribution purposes, please contact Jens Krinke <j.krinke@ucl.ac.uk>.

ORBS and the Limits of Static Slicing

Observation-based slicing is a recently-introduced, language-independent, slicing technique based on the dependencies observable from program behaviour. Due to the well-known limits of dynamic analysis, we may only compute an under- approximation of the true observation-based slice. However, because the observation-based slice captures all possible dependence that can be observed, even such approximations can yield insight into the limitations of static slicing. For example, a static slice, S that is strictly smaller than the corresponding observation based slice is potentially unsafe. We present the results of three sets of experiments on 12 different programs, including benchmarks and larger programs, which investigate the relationship between static and observation-based slicing. We show that, in extreme cases, observation-based slices can find the true minimal static slice, where static techniques cannot. For more typical cases, our results illustrate the potential for observation-based slicing to highlight limitations in static slicers. Finally, we report on the sensitivity of observation-based slicing to test quality. 

D. Binkley, N. Gold, M. Harman, S. Islam, J. Krinke, S. Yoo: ORBS and the Limits of Static Slicing15th IEEE International Working Conference on Source Code Analysis and Manipulation, Bremen, Germany, September 2015.

Visual ORBS

A spin-off is Visual ORBS, Observation-Based Slicing for Picture Description Languages.

This page was last modified on 04 Nov 2016.