The use of program dependence graphs in software engineering

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The use of program dependence graphs in software engineering

Full text

Pdf (2.58 MB)

Source

International Conference on Software Engineering archive
Proceedings of the 14th international conference on Software engineering table of contents

Melbourne, Australia

Pages: 392 - 411

Year of Publication: 1992

ISBN:0-89791-504-6

Authors

Susan Horwitz
Thomas Reps

Sponsors

IEEE-CS\TCSE : TC on Software Engineering
ACS :
IEA :
IREE :
SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 108, Citation Count: 39

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/143062.143156 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
	2	B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
	3	Ball, T., Horwitz, S., and Reps, T., "Correctness of an algorithm for reconstituting a program from a dependence graph," Technical Report 947, Department of Computer Sciences, University of Wisconsin- Madison (July 1990).
	4	Utpal Banerjee, Speedup of ordinary programs, 1979
	5	John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
	6	V Berzins, On merging software extensions, Acta Informatica, v.23 n.6, p.607-619, Nov. 1986 [doi>10.1007/BF00264309]
	7	Binkley, D., Horwitz, S., and Reps, T., "Identifying semantic differences in programs with procedures," Unpublished report, Computer Sciences Department, University of Wisconsin, Madison, WI (September 1991).
	8	David Wendell Binkley, Multi-procedure program integration, University of Wisconsin at Madison, Madison, WI, 1992
	9	R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
	10	Donzeau-Gouge, V., Huet, G., Kahn, G., and Lang, B., "Programming environments based on structured editors: The MENTOR experience," pp. 128-140 in Interactive Programming Environments, cd. D. Barstow, E. Sandewall, and H. Shrobe, McGraw-Hill, New York (1984).
	11	Feather, M. S., "Detecting interference when merging specification evolutions," Unpublished report, Information Sciences Institute, University of Southern California, Marina del Rey, CA (1989).
	12	Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
	13	Keith Brian Gallagher, Using program slicing in software maintenance, University of Maryland at Baltimore County, Catonsville, MD, 1990
	14	Hoffmaun, C. M., Group-Theoretic Algorithms and Graph Isornorphism, Lecture Notes in Computer Science, Vol. 136, Springer- Verlag, New York, NY (1982).
	15	Hopcroft, J. E., "An n log n algorithm for minimizing the states of a finite automation," The Theory of Machines and Computations, pp. 189-196(1971).
	16	S. Horwitz , J. Prins , T. Reps, On the adequacy of program dependence graphs for representing programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.146-157, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73573]
	17	S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, ACM SIGPLAN Notices, v.24 n.7, p.28-40, July 1989
	18	Susan Horwitz , Jan Prins , Thomas Reps, Integrating noninterfering versions of programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.345-387, July 1989 [doi>10.1145/65979.65980]
	19	Susan Horwitz, Identifying the semantic and textual differences between two versions of a program, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.234-245, June 1990, White Plains, New York, United States
	20	Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
	21	Susan Horwitz , Thomas Reps, Efficient comparison of program slices, Acta Informatica, v.28 n.9, p.713-732, Nov. 1991
	22	Hwang, J.C., Du, M.W., and Chou, C.R., "Finding program slices for recursive procedures," in Proceedings of IEEE COMPSAC 88, (Chicago, IL, Oct. 3-7, 1988), IEEE Computer Society, Washington, DC (1988).
	23	Kuck, D. J., Muraoka, Y., and Chen, S. C., "On the number of operations simultaneously executable in FORTRAN-like programs and their resulting speed-up," IEEE Transactions on Computers C-21, pp. 1293-1310 (December 1972).
	24	D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
	25	A. Lakhotia , L. Sterling, Composing recursive logic programs with clausal join, New Generation Computing, v.6 n.2-3, p.211-225, March-April 1988 [doi>10.1007/BF03037138]
	26	J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
	27	Luks, E., "Isomosphism of bounded valence can be tested in polynomial time," pp. 42-49 in Proceedings of the Twenty-First IEEE Symposium on Foundations of Computer Science (Syracuse, NY, October 1980), IEEE Computer Society, Washington, DC (1980).
	28	T. Mogenson , K. Holst, Terminology, New Generation Computing, v.6 n.2-3, p.303-307, March-April 1988
	29	Notkin, D., Ellison, R.J., Staudt, B. J., Kaiser, G. E., Kant, E., Habermann, A.N., Ambriola, V., and Montangero, C., Special issue on the GANDALF project, Journal of Systems and Software 5(2)(May 1985).
	30	Karl J. Ottenstein , Linda M. Ottenstein, The program dependence graph in a software development environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.177-184, April 1984
	31	A. Podgurski , L. A. Clarke, A Formal Model of Program Dependences and its Implications for Software Testing, Debugging, and Maintenance, IEEE Transactions on Software Engineering, v.16 n.9, p.965-979, September 1990 [doi>10.1109/32.58784]
	32	Thomas W. Reps , Tim Teitelbaum, The synthesizer generator: a system for constructing language-based editors, Springer-Verlag New York, Inc., New York, NY, 1989
	33	Reps, T. and Yang, W., "The semantics of program slicing," Technical Report 777, Department of Computer Sciences, University of Wisconsin-Madison (June 1988).
	34	T. Reps , T. Bricker, Illustrating interference in interfering versions of programs, ACM SIGSOFT Software Engineering Notes, v.14 n.7, p.46-55, Nov. 1989
	35	Reps, T., "Demonstration of a prototype tool for program integration," Technical Report 819, Department of Computer Sciences, University of Wisconsin-Madison (January 1989).
	36	T. Reps, Algebraic properties of program integration, Proceedings of the third European symposium on programming on ESOP '90, p.326-340, May 1990, Copenhagen, Denmark
	37	Repa, T., "The Wisconsin program-integration system reference manual," Unpublished document, Department of Computer Sciences, University of Wisconsin, Madison, WI (April 1990).
	38	Thomas Reps, Algebraic properties of program integration, Science of Computer Programming, v.17 n.1-3, p.139-215, Dec. 1991
	39	B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
	40	Shapiro, R. M. and Saint, H., "The representation of algorithm," Technical Reprot CA-7002-1432, Massachusetts Computer Associates (February 1970).
	41	Weiser, M., "Program slicing," IEEE Transactions on Software Engineering SE-10(4) pp. 352-357 (July 1984).
	42	Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982
	43	Yang, W., Horwitz, S., and Reps, T., "Detecting program components with equivalent behaviors," Technical Report 840, Department of Computer Sciences, University of Wisconsin, Madison, WI (April 1989).
	44	Wuu Yang , Thomas Reps , Susan Horwitz, A new algorithm for semantics-based program integration, 1990
	45	Wuu Yang, Identifying syntactic differences between two programs, Software—Practice & Experience, v.21 n.7, p.739-755, July 1991 [doi>10.1002/spe.4380210706]
	46	Wuu Yang , Susan Horwitz , Thomas Reps, A program integration algorithm that accommodates semantics-preserving transformations, ACM Transactions on Software Engineering and Methodology (TOSEM), v.1 n.3, p.310-354, July 1992 [doi>10.1145/131736.131756]

CITED BY 39

	Christopher Colby , Patrice Godefroid , Lalita Jategaonkar Jagadeesan, Automatically closing open reactive programs, ACM SIGPLAN Notices, v.33 n.5, p.345-357, May 1998
	Timothy Griffin , Richard Hull, A framework for implementing hypothetical queries, ACM SIGMOD Record, v.26 n.2, p.231-242, June 1997
	Debra J. Richardson , T. Owen O'Malley , Cynthia Tittle Moore , Stephanie Leif Aha, Developing and integrating ProDAG in the Arcadia environment, ACM SIGSOFT Software Engineering Notes, v.17 n.5, p.109-119, Dec. 1992
	T. Mens, A State-of-the-Art Survey on Software Merging, IEEE Transactions on Software Engineering, v.28 n.5, p.449-462, May 2002
	Jukka Paakki, Attribute grammar paradigms—a high-level methodology in language implementation, ACM Computing Surveys (CSUR), v.27 n.2, p.196-255, June 1995
	Daniel Le Métayer, Program analysis for software engineering: new applications, new requirements, new tools, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996
	Gregg Rothermel , Mary Jean Harrold, Selecting tests and identifying test coverage requirements for modified software, Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis, p.169-184, August 17-19, 1994, Seattle, Washington, United States
	Debra J. Richardson, TAOS: Testing with Analysis and Oracle Support, Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis, p.138-153, August 17-19, 1994, Seattle, Washington, United States
	Jingde Cheng, Task dependence nets for concurrent systems with Ada 95 and its applications, Proceedings of the conference on TRI-Ada '97, p.67-78, November 09-13, 1997, St. Louis, Missouri, United States
	David Mandelin , Lin Xu , Rastislav Bodík , Doug Kimelman, Jungloid mining: helping to navigate the API jungle, ACM SIGPLAN Notices, v.40 n.6, June 2005
	John Hatcliff , Xinghua Deng , Matthew B. Dwyer , Georg Jung , Venkatesh Prasad Ranganath, Cadena: an integrated development, analysis, and verification environment for component-based systems, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
	Chris J. Newburn , Derek B. Noonburg , John Paul Shen, A PDG-based Tool and its Use in Analyzing Program Control Dependences, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.157-168, August 24-26, 1994
	Paul Anderson , Thomas Reps , Tim Teitelbaum, Design and Implementation of a Fine-Grained Software Inspection Tool, IEEE Transactions on Software Engineering, v.29 n.8, p.721-733, August 2003
	Akira Nishimatsu , Minoru Jihira , Shinji Kusumoto , Katsuro Inoue, Call-mark slicing: an efficient and economical way of reducing slice, Proceedings of the 21st international conference on Software engineering, p.422-431, May 16-22, 1999, Los Angeles, California, United States
	Erik Trainer , Stephen Quirk , Cleidson de Souza , David Redmiles, Bridging the gap between technical and social dependencies with Ariadne, Proceedings of the 2005 OOPSLA workshop on Eclipse technology eXchange, p.26-30, October 16-17, 2005, San Diego, California
	Sagar Chaki , Alex Groce , Ofer Strichman, Explaining abstract counterexamples, ACM SIGSOFT Software Engineering Notes, v.29 n.6, November 2004
	David Binkley, Semantics Guided Regression Test Cost Reduction, IEEE Transactions on Software Engineering, v.23 n.8, p.498-516, August 1997
	Gerardo Canfora , Aniello Cimitile , Ugo de Carlini, A Logic-Based Approach to Reverse Engineering Tools Production, IEEE Transactions on Software Engineering, v.18 n.12, p.1053-1064, December 1992
	Zhenqiang Chen , Baowen Xu , Jianjun Zhao, An overview of methods for dependence analysis of concurrent programs, ACM SIGPLAN Notices, v.37 n.8, August 2002
	Jukka Paakki , Jussi Koskinen , Airi Salminen, From relational program dependencies to hypertextual access structures, Nordic Journal of Computing, v.4 n.1, p.3-36, Spring 1997
	Holger Cleve , Andreas Zeller, Locating causes of program failures, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA
	Bi-Xin Li , Xiao-Cong Fan , Jun Pang , Jian-Jun Zhao, A model for slicing JAVA programs hierarchically, Journal of Computer Science and Technology, v.19 n.6, p.848-858, November 2004
	Myungchul Kim , Sangjo Yoo , Jinhee Park , Sungwon Kang , Soon J. Hyun , Hyuckjae Lee, A dynamic protocol conformance test method, Journal of Systems and Software, v.67 n.1, p.31-43, 15 July 2003
	Karl Lermer , Colin J. Fidge , Ian J. Hayes, A theory for execution-time derivation in real-time programs, Theoretical Computer Science, v.346 n.1, p.3-27, 23 November 2005
	Heike Wehrheim, Slicing techniques for verification re-use, Theoretical Computer Science, v.343 n.3, p.509-528, 17 October 2005
	Mathieu Verbaere , Ran Ettinger , Oege de Moor, JunGL: a scripting language for refactoring, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China
	Hon F. Li , Juergen Rilling , Dhrubajyoti Goswami, Granularity-Driven Dynamic Predicate Slicing Algorithms for Message Passing Systems, Automated Software Engineering, v.11 n.1, p.63-89, January 2004
	Jonathon T. Giffin , Somesh Jha , Barton P. Miller, Detecting Manipulated Remote Call Streams, Proceedings of the 11th USENIX Security Symposium, p.61-79, August 05-09, 2002
	João Paulo Fernandes , João Saraiva, Tools and libraries to model and manipulate circular programs, Proceedings of the 2007 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 15-16, 2007, Nice, France
	David Binkley, Source Code Analysis: A Road Map, 2007 Future of Software Engineering, p.104-119, May 23-25, 2007
	Jaakko Korpi , Jussi Koskinen, Grace: automated slicing for visual basic, Proceedings of the 25th conference on IASTED International Multi-Conference: Software Engineering, p.204-209, February 13-15, 2007, Innsbruck, Austria
	Gyöngyi Szilágyi , Tibor Gyimóthy , Jan Małuszyński, Static and Dynamic Slicing of Constraint Logic Programs, Automated Software Engineering, v.9 n.1, p.41-65, January 2002
	Feng Chen , Traian Florin Serbanuta , Grigore Rosu, jPredictor: a predictive runtime analysis tool for java, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany
	Liang Gu , Xuhua Ding , Robert Huijie Deng , Bing Xie , Hong Mei, Remote attestation on program execution, Proceedings of the 3rd ACM workshop on Scalable trusted computing, October 31-31, 2008, Alexandria, Virginia, USA
	Junko Shirogane , Hajime Iwata , Kazuhiro Fukaya , Yoshiaki Fukazawa, GUI Change Method according to Roles of Widgets and Change Patterns, IEICE - Transactions on Information and Systems, v.E91-D n.4, p.907-920, April 2008
	João Carlos Silva , João Saraiva , José Creissac Campos, A generic library for GUI reasoning and testing, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Martin Th Görg , Jianjun Zhao, Identifying semantic differences in AspectJ programs, Proceedings of the eighteenth international symposium on Software testing and analysis, July 19-23, 2009, Chicago, IL, USA
	Junko Shirogane , Kazuhiro Fukaya , Yoshiaki Fukazawa, Support Method for Source Code Modification in Changing GUI Widgets, Proceeding of the 2006 conference on Knowledge-Based Software Engineering: Proceedings of the Seventh Joint Conference on Knowledge-Based Software Engineering, p.31-40, May 21, 2006
	Colin J. Fidge , Diane Corney, Integrating hardware and software information flow analyses, ACM SIGPLAN Notices, v.44 n.7, July 2009