Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-22T06:21:59.917Z Has data issue: false hasContentIssue false
  • English
  • Français

On the computational complexity of dynamic slicing problems for program schemas

Published online by Cambridge University Press:  27 October 2011

SEBASTIAN DANICIC ,
ROBERT. M. HIERONS  and
MICHAEL R. LAURENCE
SEBASTIAN DANICIC
Affiliation:
Department of Computing, Goldsmiths College, University of London, London SE14 6NW, United Kingdom Email: [email protected]
ROBERT. M. HIERONS
Affiliation:
Department of Information Systems and Computing, Brunel University, Middlesex, UB8 3PH, United Kingdom Email: [email protected]
MICHAEL R. LAURENCE
Affiliation:
Department of Computing, Goldsmiths College, University of London, London SE14 6NW, United Kingdom Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Given a program, a quotient can be obtained from it by deleting zero or more statements. The field of program slicing is concerned with computing a quotient of a program that preserves part of the behaviour of the original program. All program slicing algorithms take account of the structural properties of a program, such as control dependence and data dependence, rather than the semantics of its functions and predicates, and thus work, in effect, with program schemas. The dynamic slicing criterion of Korel and Laski requires only that program behaviour is preserved in cases where the original program follows a particular path, and that the slice/quotient follows this path. In this paper we formalise Korel and Laski's definition of a dynamic slice as applied to linear schemas, and also formulate a less restrictive definition in which the path through the original program need not be preserved by the slice. The less restrictive definition has the benefit of leading to smaller slices. For both definitions, we compute complexity bounds for the problems of establishing whether a given slice of a linear schema is a dynamic slice and whether a linear schema has a non-trivial dynamic slice, and prove that the latter problem is NP-hard in both cases. We also give an example to prove that minimal dynamic slices (whether or not they preserve the original path) need not be unique.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 21 , Special Issue 6: Programming Language Interference and Dependence , December 2011 , pp. 1339 - 1362
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Agrawal, H., DeMillo, R. A. and Spafford, E. H. (1993) Debugging with dynamic slicing and backtracking. Software Practice and Experience 23 (6)589–616.CrossRefGoogle Scholar
Agrawal, H. and Horgan, J. R. (1990) Dynamic program slicing. In: Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation. SIGPLAN Notices 25 246–256.CrossRefGoogle Scholar
Ashcroft, E. A. and Manna, Z. (1975) Translating program schemas to while-schemas. SIAM Journal on Computing 4 (2)125–146.CrossRefGoogle Scholar
Beszédes, A., Gergely, T., Szabó, Z. M., Csirik, J. and Gyimóthy, T. (2001) Dynamic slicing method for maintenance of large C programs. In: Proceedings of the Fifth European Conference on Software Maintenance and Reengineering (CSMR 2001), IEEE Computer Society 105–113.CrossRefGoogle Scholar
Binkley, D., Danicic, S., Gyimóthy, T., Harman, M., Kiss, Á. and Korel, B. (2006) Theoretical foundations of dynamic program slicing. Theoretical Computer Science 360 (1–3)23–41.CrossRefGoogle Scholar
Canfora, G., Cimitile, A., De Lucia, A. and Lucca, G. A. D. (1994) Software salvaging based on conditions. In: Proceedings of the International Conference on Software Maintenance (ICSM'96), IEEE Computer Society 424–433.Google Scholar
Cimitile, A., De Lucia, A. and Munro, M. (1996) A specification driven slicing process for identifying reusable functions. Software maintenance: Research and Practice 8 145–178.3.0.CO;2-9>CrossRefGoogle Scholar
Cook, S. A. (1971) The complexity of theorem-proving procedures. In: STOC '71: Proceedings of the third annual ACM symposium on Theory of computing, ACM Press 151–158.CrossRefGoogle Scholar
Danicic, S., Fox, C., Harman, M., Hierons, R., Howroyd, J. and Laurence, M. R. (2005) Static program slicing algorithms are minimal for free liberal program schemas. The Computer Journal 48 (6)737–748.CrossRefGoogle Scholar
Danicic, S., Harman, M., Hierons, R., Howroyd, J. and Laurence, M. R. (2007) Equivalence of linear, free, liberal, structured program schemas is decidable in polynomial time. Theoretical Computer Science 373 (1−2)1–18.CrossRefGoogle Scholar
De Lucia, A., Fasolino, A. R. and Munro, M. (1996) Understanding function behaviours through program slicing. In: Proceedings of the 4th IEEE Workshop on Program Comprehension, IEEE Computer Society 9–18.Google Scholar
Gallagher, K. B. (1992) Evaluating the surgeon's assistant: Results of a pilot study. In: Proceedings of the International Conference on Software Maintenance, IEEE Computer Society 236–244.Google Scholar
Gallagher, K. B. and Lyle, J. R. (1991) Using program slicing in software maintenance. IEEE Transactions on Software Engineering 17 (8)751–761.CrossRefGoogle Scholar
Gopal, R. (1991) Dynamic program slicing based on dependence graphs. In: Proceedings IEEE Conference on Software Maintenance, IEEE Computer Society 191–200.Google Scholar
Greibach, S. (1975) Theory of program structures: schemes, semantics, verification. Springer-Verlag Lecture Notes in Computer Science 36.CrossRefGoogle Scholar
Harman, M., Fox, C., Hierons, R. M., Hu, L., Danicic, S. and Wegener, J. (2002) Vada: A transformation-based system for variable dependence analysis. In: Proceedings IEEE International Workshop on Source Code Analysis and Manipulation (SCAM 2002), IEEE Computer Society 55–64.Google Scholar
Harman, M., Hierons, R. M., Danicic, S., Howroyd, J. and Fox, C. (2001) Pre/post conditioned slicing. In: Proceedings IEEE International Conference on Software Maintenance (ICSM'01), IEEE Computer Society 138–147.Google Scholar
Hunt, H. B., Constable, R. L. and Sahni, S. (1980) On the computational complexity of program scheme equivalence. SIAM J. Comput 9 (2)396–416.CrossRefGoogle Scholar
Ianov, Y. I. (1960) The logical schemes of algorithms. In: Problems of Cybernetics 1, Pergamon Press 82–140.Google Scholar
Jones, B., Sthamer, H.-H. and Eyres, D. (1996) Automatic structural testing using genetic algorithms. The Software Engineering Journal 11 299–306.CrossRefGoogle Scholar
Kamkar, M. (1993) Interprocedural dynamic slicing with applications to debugging and testing, Ph.D. Thesis, Department of Computer Science and Information Science, Linköping University, Sweden. (Available as Linköping Studies in Science and Technology, Dissertations, Number 297.)Google Scholar
Kamkar, M. (1998) Application of program slicing in algorithmic debugging. In: Harman, M. and Gallagher, K. (eds.) Information and Software Technology 40 (Special Issue on Program Slicing) 637–645.CrossRefGoogle Scholar
Kamkar, M., Shahmehri, N. and Fritzson, P. (1992) Interprocedural dynamic slicing. In: Bruynooghe, M. and Wirsing, M. (eds.) Programming Language Implementation and Logic Programming, 4th International Symposium, PLILP'92, Proceedings. Springer-Verlag Lecture Notes in Computer Science 631 370–384.CrossRefGoogle Scholar
Korel, B. (1995) Computation of dynamic slices for programs with arbitrary control flow. In: Ducassé, M. (ed.) 2nd International Workshop on Automated Algorithmic Debugging (AADEBUG'95) 71–86.Google Scholar
Korel, B. and Laski, J. (1988) Dynamic program slicing. Information Processing Letters 29 (3)155–163.CrossRefGoogle Scholar
Korel, B. and Rilling, J. (1998) Dynamic program slicing methods. In: Harman, M. and Gallagher, K. (eds.) Information and Software Technology 40 (Special Issue on Program Slicing) 647–659.CrossRefGoogle Scholar
Laurence, M. R. (2005) Characterising minimal semantics-preserving slices of function-linear, free, liberal program schemas. Journal of Logic and Algebraic Programming 72 (2)157–172.CrossRefGoogle Scholar
Laurence, M. R., Danicic, S., Harman, M., Hierons, R. and Howroyd, J. (2003) Equivalence of conservative, free, linear program schemas is decidable. Theoretical Computer Science 290 831–862.CrossRefGoogle Scholar
Laurence, M. R., Danicic, S., Harman, M., Hierons, R. and Howroyd, J. (2004) Equivalence of linear, free, liberal, structured program schemas is decidable in polynomial time. Technical Report ULCS-04-014, University of Liverpool. (Available at http://www.csc.liv.ac.uk/research/techreports/.)Google Scholar
Luckham, D. C., Park, D. M. R. and Paterson, M. S. (1970) On formalised computer programs. Journal of Computer and System Sciences 4 (3)220–249.CrossRefGoogle Scholar
Lyle, J. R. and Weiser, M. (1987) Automatic program bug location by program slicing. In: Proceedings 2nd International Conference on Computers and Applications, IEEE Computer Society 877–882.Google Scholar
Manna, Z. (1974) Mathematical Theory of Computation, McGraw–Hill.Google Scholar
Müller-Olm, M. (2004) Precise interprocedural dependence analysis of parallel programs. Theoretical Computer Science 31 (1)325–388.CrossRefGoogle Scholar
Müller-Olm, M. and Seidl, H. (2004a) Computing polynomial program invariants. Information Processing Letters 91 (5)233–244.CrossRefGoogle Scholar
Müller-Olm, M. and Seidl, H. (2004b) Precise interprocedural analysis through linear algebra. In Proceedings of Principles of Programming Languages (POPL'04). SIGPLAN Notices 39 (1)330–341.CrossRefGoogle Scholar
Paterson, M. S. (1967) Equivalence Problems in a Model of Computation, Ph.D. thesis, University of Cambridge.Google Scholar
Rutledge, J. D. (1964) On Ianov's program schemata. J. ACM 11 (1)1–9.CrossRefGoogle Scholar
Sabelfeld, V. K. (1990) An algorithm for deciding functional equivalence in a new class of program schemes. Theoretical Computer Science 71 265–279.CrossRefGoogle Scholar
Wegener, J., Grimm, K., Grochtmann, M., Sthamer, H. and Jones, B. F. (1996) Systematic testing of real-time systems. In: Proceedings 4th International Conference on Software Testing Analysis and Review (EuroSTAR 96).Google Scholar
Wegener, J., Sthamer, H., Jones, B. F. and Eyres, D. E. (1997) Testing real-time systems using genetic algorithms. Software Quality 6 (2)127–135.CrossRefGoogle Scholar
Weiser, M. (1984) Program slicing. IEEE Transactions on Software Engineering 10 (4)352–357.CrossRefGoogle Scholar
Weiser, M. and Lyle, J. R. (1985) Experiments on slicing-based debugging aids. In: Soloway, E. and Iyengar, S. (eds.) Empirical studies of programmers, chapter 12, Ablex Publishing Corporation 187–197.Google Scholar