Folklore confirmed

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Folklore confirmed: reducible flow graphs are exponentially larger

Full text

Pdf (204 KB)

Source

ACM SIGPLAN Notices archive
Volume 38 , Issue 1 (January 2003) table of contents

Pages: 106 - 114

Year of Publication: 2003

ISSN:0362-1340

Also published in ...

Authors

Larry Carter	UC San Diego, La Jolla, CA
Jeanne Ferrante	UC San Diego, La Jolla, CA
Clark Thomborson	University of Auckland, Auckland, New Zealand

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 43, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/640128.604141 What is a DOI?

ABSTRACT

Many program analysis techniques used by compilers are applicable only to programs whose control flow graphs are reducible. Node-splitting is a technique that can be used to convert any control flow graph to a reducible one. However, as has been observed for various node-splitting algorithms, there can be an exponential blowup in the size of the graph.We prove that exponential blowup is unavoidable. In particular, we show that any reducible graph that is equivalent to the complete graph on n nodes (or to related bounded-degree control flow graphs) must have at least 2^n-1 nodes. While this result is not a surprise, it may be relevant to the quest for finding methods of obfuscation for software protection.

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	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	2	F. Allen and J. Cocke. Graph-theoretic constructs for program control flow analysis. Technical Report RC-3923, IBM Research, 1972.
	3	Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
	4	Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
	5	J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
	6	Zahira Ammarguellat, A Control-Flow Normalization Algorithm and its Complexity, IEEE Transactions on Software Engineering, v.18 n.3, p.237-251, March 1992 [doi>10.1109/32.126773]
	7	Boaz Barak , Oded Goldreich , Russell Impagliazzo , Steven Rudich , Amit Sahai , Salil P. Vadhan , Ke Yang, On the (Im)possibility of Obfuscating Programs, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.1-18, August 19-23, 2001
	8	Stanley Chow , Yuan Gu , Harold Johnson , Vladimir A. Zakharov, An Approach to the Obfuscation of Control-Flow of Sequential Computer Programs, Proceedings of the 4th International Conference on Information Security, p.144-155, October 01-03, 2001
	9	J. Cocke and R. Miller. Some analysis techniques for optimizing computer programs. In Proceedings of the Second Intl. Conf. of Systems Science, January 1969.
	10	Christian Collberg , Clark Thomborson , Douglas Low, Breaking Abstractions and Unstructuring Data Structures, Proceedings of the 1998 International Conference on Computer Languages, p.28, May 14-16, 1998
	11	Christian Collberg , Clark Thomborson , Douglas Low, Manufacturing cheap, resilient, and stealthy opaque constructs, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-196, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268962]
	12	A. Erosa and L. Hendren. Taming control flow: A structured approach to eliminating goto statements. In International Conference on Computer Languages, May 1994.
	13	Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
	14	Johan Janssen , Henk Corporaal, Controlled Node Splitting, Proceedings of the 6th International Conference on Compiler Construction, p.44-58, April 24-26, 1996
	15	Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
	16	S. Unger and F. Mueller. Handling Irreducible Loops: Optimized Node Splitting vs. DJ-Graphs. Technical Report TR 01-146, Institut f. Informatik, Humboldt-University, Jan. 2001.
	17	Chenxi Wang , Jonathan Hill , John Knight , Jack Davidson, Software Tamper Resistance: Obstructing Static Analysis of Programs, University of Virginia, Charlottesville, VA, 2000