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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:66654", author = "Robert Gold", title = "Reductions of Control Flow Graphs", 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.", volume = "8", number = "3", pages = "433-8", }
