Reductions of Control Flow Graphs

Authors: Robert Gold

Abstract:

Control flow graphs are a well-known representation of the sequential control flow structure of programs with a multitude of applications. Not only single functions but also sets of functions or complete programs can be modeled by control flow graphs. In this case the size of the graphs can grow considerably and thus makes it difficult for software engineers to analyze the control flow. Graph reductions are helpful in this situation. In this paper we define reductions to subsets of nodes. Since executions of programs are represented by paths through the control flow graphs, paths should be preserved. Furthermore, the composition of reductions makes a stepwise analysis approach possible.

Keywords: Control flow graph, graph reduction.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1091178

References:

[1] M. Abadi, M. Budiu, U. Erlingsson and J. Ligatti. 2009. Control- ´ flow integrity principles, implementations, and applications. ACM Transactions on Information and System Security, vol. 13, no. 1, pp. 4:1-4:40.
[2] A.V. Aho, M.S. Lam, R. Sethi and J.D. Ullman. 2007.Compilers: Principles, techniques, and tools. Amsterdam: Addison-Wesley Longman, 2. ed.
[3] F.E. Allen and J. Cocke. 1972. Graph-theoretic constructs for program control flow analysis. Research Report RC 3923, IBM Research.
[4] A. Bertolino and M. Marre. 1994. Automatic generation of path ´ covers based on the control flow analysis of computer programs. IEEE Transactions on Software Engineering, vol. 20, no. 12, pp. 885-899.
[5] J.A. Bondy and U.S.R. Murty. 2008. Graph theory. London: Springer.
[6] P.A. Brooks and A.M. Memon. 2007. Automated GUI testing guided by usage profiles. Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE ’07), Atlanta, USA, 05. – 09.11.2007, pp. 333–342.
[7] D. Bruschi, L. Martignoni and M. Monga. 2006. Detecting self-mutating malware using control-flow graph matching. In: R. Buschkes and P. Laskov (eds.), ¨ Proceedings of the Third International Conference on Detection of Intrusions and Malware & Vulnerability Assessment (DIMVA ’06), Berlin, Germany, 13. – 14.07.2006, Lecture Notes in Computer Science 4064, Berlin, Heidelberg: Springer, pp. 129–143.
[8] R. Diestel. 2010. Graph theory. New York, Berlin, Heidelberg: Springer, 4. ed.
[9] D. Draheim. 2010. Business process technology: A unified view on business processes, workflows and enterprise applications. Berlin, Heidelberg: Springer.
[10] J. Ferrante, K.J. Ottenstein and J.D. Warren. 1987. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, vol. 9, no. 3, pp. 319– 349.
[11] P.G. Frankl and E.J. Weyuker. 1993. Provable improvements on branch testing. IEEE Transactions on Software Engineering, vol. 19, no. 10, pp. 962–975.
[13] R. Gold. 2012. On cyclomatic complexity and decision graphs. Proceedings of the 10th International Conference of Numerical Analysis and Applied Mathematics (ICNAAM ’12), Kos, Greece, 19. – 25.09.2012, AIP Conf. Proc. 1479, pp. 2170–2173.
[14] R. Gold. 2013. Decision graphs and their application to software testing. ISRN Software Engineering, vol. 2013.
[15] R. Gold. 2013. The decision structure of programs. Proceedings of the International Research Conference on Information Technology and Computer Sciences, IRCITCS 2013, Kuala Lumpur, Malaysia, 28. - 30.09.2013.
[16] N. Gupta, A.P. Mathur and M.L. Soffa. 2000. Generating test data for branch coverage. Proceedings of the Fifteenth IEEE International Conference on Automated Software Engineering, Grenoble, France, 11. – 15.09.2000, pp. 219–227.
[17] M.J. Harrold and G. Rothermel. 1994. Performing data flow testing on classes. Proceedings of the 2nd ACM SIGSOFT Symposium on Foundations of Software Engineering, December 1994, pp. 154–163.
[18] M.J. Harrold and G. Rothermel. 1996. A coherent family of analyzable graphical representations for object-oriented software. Technical Report OSU-CISRC-11/96-TR60, Department of Computer and Information Science, The Ohio State University.
[19] B. Henderson-Sellers and D. Tegarden. 1994. The theoretical extension of two versions of cyclomatic complexity to multiple entry/exit modules. Software Quality Journal, vol. 3, no. 4, pp. 253–269.
[20] R.M. Hierons, M. Harman and C.J. Fox. 2005. Branch-coverage testability transformation for unstructured programs. The Computer Journal, vol. 48, no. 4, pp. 421–436.
[21] P. Jalote. 2005. An integrated approach to software engineering. New York: Springer, 3. ed.
[22] G.M. Kapfhammer. 2004. Software testing. In: A.B. Tucker (ed.), Computer Science Handbook, Chapman & Hall/CRC, 2. ed.
[23] W.J. Laski and B. Korel. 1983. A data flow oriented program testing strategy. IEEE Transactions on Software Engineering, vol. SE-9, no. 3, pp. 347–354.
[24] T.J. McCabe. 1976. A complexity measure. IEEE Transactions on Software Engineering, vol. SE-2, no. 4, pp. 308–320.
[25] A.M. Memon. 2007. An event-flow model of GUI-based applications for testing. Software Testing, Verification and Reliability, vol. 17, no. 3, pp. 137–157.
[26] A.M. Memon, M.L. Soffa and M.E. Pollack. 2001. Coverage criteria for GUI testing. Proceedings of the 8th European Software Engineering Conference held jointly with the 9th ACM SIGSOFT International Symposium on Foundations of Software Engineering, Vienna, Austria, pp. 256–267.
[27] M.R. Paige. 1977. On partitioning program graphs. IEEE Transactions on Software Engineering, vol. SE-3, no. 6, pp. 386–393.
[28] S. Rapps and E.J. Weyuker. 1982. Data flow analysis techniques for test data selection. Proceedings of the 6th International Conference on Software Engineering, Tokyo, Japan, 1982, pp. 272–278.
[29] T. Reps, S. Horwitz and M. Sagiv. 1995. Precise interprocedural dataflow analysis via graph reachability. Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 49–61.
[30] W. Sadiq and M.E. Orlowska. 2000. Analyzing process models using graph reduction techniques. Information systems, vol. 25, no. 2, pp. 117–134.
[31] I. Sommerville. 2004. Software engineering. Boston: Pearson Education Limited, 7. ed.
[32] H. Theiling. 2000. Extracting safe and precise control flow from binaries. Proceedings of the Seventh International Conference on Real-Time Computing Systems and Applications, Cheju Island, South Korea, 12. – 14.12.2000, pp. 23–30.
[33] Z.Wang and X. Jiang. 2010. HyperSafe: A lightweight approach to provide lifetime hypervisor control-flow integrity. Proceedings of the IEEE Symposium on Security and Privacy (SP), Oakland, USA, 16. – 19.05.2010.
[34] Y. Wenjian, J. Liehui, Y. Qing, Z. Lina and L. Jizhong. 2009. A control flow graph reconstruction method from binaries based on XML. Proceedings of the International Forum on Computer Science-Technology and Applications, IFCSTA ’09, Chongqing, 25. – 27.12.2009, pp. 226–229.
[35] L.J. White. 1981. Basic mathematical definitions and results in testing. In: B. Chandrasekaran and S. Radicchi (eds.), Computer Program Testing, New York: North-Holland.
[36] Q. Zhang and I.G. Harris. 2000. A data flow fault coverage metric for validation of behavioral HDL descriptions. International Conference on Computer-Aided Design (ICCAD ’00), San Jose, USA, 05.11.2000.
[37] H. Zhu, P.A.V. Hall and J.H.R. May. 1997. Software unit test coverage and adequacy. ACM Computing Surveys, vol. 29, no. 4, pp. 366–427.