Control flow graphs are a well-known graphical representation of programs that capture the control flow but abstract from program details. In this paper, we derive decision graphs that reduce control flow graphs but preserve the branching structure of programs. As an application to software engineering, we use decision graphs to compare and clarify different definitions of branch covering in software testing. 1. Introduction Graphs that represent the control flow of programs have been studied since many years and are known under the names of control flow graphs or program graphs. There are mainly two types of such graphs: one that associates one node with each statement in programs, see, for example, [1], where control flow graphs are applied to optimization or [2] for the application in software engineering; and the other that replaces maximal sets of consecutive nodes with a single entry and a single exit called blocks or segments, by single nodes, for example, [3, 4]. Blocks can be derived from the control flow graphs of the first type or constructed directly from the programs. Both types capture the control flow by abstraction from the program details. Since the control flow through programs is determined by the decisions, for example, the if-then-else-constructs, based on the data and the conditions in such constructs, it is promising to keep in graphical representations of programs only the decisions and the control flow between them and thus defining a reduction of control flow graphs that preserves the branching structure. In this paper, we will study control flow graphs (of the first type) and derive decision graphs [5, 6] that represent the branching structure of programs based on the definition of program graphs reduced to DD-paths by Paige [7]. Statement coverage and branch coverage are widely used in software testing. The first property can be checked with control flow graphs since each node represents a statement (or block of statements). When regarding branch coverage, analogously, the question arises, in which in graph type, each edge represents a branch. More general, decision graphs can be derived not only from control flow graphs but also from arbitrary directed graphs and thus represent the branching structure of the graphs. We show that the branches in a graph correspond to the edges in the derived decision graph. As an application, we compare different definitions of branch covering in software testing that already existed but were specified in different ways in order to find where they differ from each other and thus get new
References
[1]
J. Ferrante, K. J. Ottenstein, and J. D. Warren, “The program dependence graph and its use in optimization,” ACM Transactions on Programming Languages and Systems, vol. 9, no. 3, pp. 319–349, 1987.
[2]
I. Sommerville, Software Engineering, Pearson Education Limited, Boston, Mass, USA, 7th edition, 2004.
[3]
A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley Longman, Amsterdam, The Netherlands, 2nd edition, 2007.
[4]
H. Zhu, P. A. V. Hall, and J. H. R. May, “Software unit test coverage and adequacy,” ACM Computing Surveys, vol. 29, no. 4, pp. 366–427, 1997.
[5]
R. Gold, “Control flow graphs and code coverage,” International Journal of Applied Mathematics and Computer Science, vol. 20, no. 4, pp. 739–749, 2010.
[6]
R. Gold, “On cyclomatic complexity and decision graphs,” in Proceedings of the 10th International Conference of Numerical Analysis and Applied Mathematics (ICNAAM '12), vol. 1479 of AIP Conference Proceedings, pp. 2170–2173, Kos, Greece, September 2012.
[7]
M. R. Paige, “On partitioning program graphs,” IEEE Transactions on Software Engineering, vol. 3, no. 6, pp. 386–393, 1977.
[8]
J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, London, UK, 2008.
[9]
R. Diestel, Graph Theory, Springer, New York, NY, USA, 4th edition, 2010.
[10]
P. Jalote, An Integrated Approach to Software Engineering, Springer, New York, NY, USA, 3rd edition, 2005.
[11]
P. G. Frankl and E. J. Weyuker, “Provable improvements on branch testing,” IEEE Transactions on Software Engineering, vol. 19, no. 10, pp. 962–975, 1993.
[12]
S. Rapps and E. J. Weyuker, “Data flow analysis techniques for test data selection,” in Proceedings of the 6th International Conference on Software Engineering (ICSE '82), pp. 272–278, Tokyo, Japan, 1982.
[13]
R. M. Hierons, M. Harman, and C. J. Fox, “Branch-coverage testability transformation for unstructured programs,” The Computer Journal, vol. 48, no. 4, pp. 421–436, 2005.
[14]
A. Bertolino and M. Marré, “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, 1994.
[15]
G. M. Kapfhammer, “Software testing,” in Computer Science Handbook, A. B. Tucker, Ed., Chapman & Hall/CRC, 2nd edition, 2004.
[16]
J. W. Laski and B. Korel, “A data flow oriented program testing strategy,” IEEE Transactions on Software Engineering, vol. 9, no. 3, pp. 347–354, 1983.
[17]
L. J. White, “Basic mathematical definitions and results in testing,” in Computer Program Testing, B. Chandrasekaran and S. Radicchi, Eds., North-Holland, New York, NY, USA, 1981.
[18]
N. Gupta, A. P. Mathur, and M. L. Soffa, “Generating test data for branch coverage,” in Proceedings of the 15th IEEE International Conference on Automated Software Engineering, pp. 219–227, Grenoble, France, September 2000.
[19]
F. E. Allen and J. Cocke, “Graph-theoretic constructs for program control flow analysis,” Research Report RC 3923, IBM Research, 1972.
[20]
S. R. Kosaraju, “Analysis of structured programs,” in Proceedings of the 5th Annual ACM Symposium on Theory of Computing, pp. 240–252, Austin, Tex, USA, 1973.
[21]
C. Berge, The Theory of Graphs, Dover, New York, NY, USA, 2001.
[22]
T. J. McCabe, “A complexity measure,” IEEE Transactions on Software Engineering, vol. 2, no. 4, pp. 308–320, 1976.
[23]
B. Henderson-Sellers and D. Tegarden, “The theoretical extension of two versions of cyclomatic complexity to multiple entrylexit modules,” Software Quality Journal, vol. 3, no. 4, pp. 253–269, 1994.
[24]
T. Reps, S. Horwitz, and M. Sagiv, “Precise interprocedural dataflow analysis via graph reachability,” in Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 49–61, January 1995.
[25]
P. Emanuelsson and U. Nilsson, “A comparative study of industrial static analysis tools,” Electronic Notes in Theoretical Computer Science, vol. 217, pp. 5–21, 2008.
[26]
M. J. Harrold and G. Rothermel, “Performing data flow testing on classes,” in Proceedings of the 2nd ACM SIGSOFT Symposium on Foundations of Software Engineering (SIGSOFT '94), pp. 154–163, December 1994.
[27]
M. J. Harrold and G. Rothermel, “A coherent family of analyzable graphical representations for object-oriented software,” Tech. Rep. OSUCISRC-11/96-TR60, Department of Computer and Information Science, The Ohio State University, 1996.
[28]
D. Bruschi, L. Martignoni, and M. Monga, “Detecting self-mutating malware using control-flow graph matching,” in Proceedings of the 3rd International Conference on Detection of Intrusions and Malware & Vulnerability Assessment (DIMVA '06), R. Büschkes and P. Laskov, Eds., vol. 4064 of Lecture Notes in Computer Science, pp. 129–143, Springer, Berlin, Germany, July 2006.
[29]
M. Abadi, M. Budiu, ú. Erlingsson, and J. Ligatti, “Control-flow integrity principles, implementations, and applications,” ACM Transactions on Information and System Security, vol. 13, no. 1, article 4, 40 pages, 2009.
[30]
H. Theiling, “Extracting safe and precise control flow from binaries,” in Proceedings of the 7th International Conference on Real-Time Computing Systems and Applications, pp. 23–30, Cheju Island, South Korea, December 2000.
[31]
Y. Wenjian, J. Liehui, Y. Qing, et al., “A control flow graph reconstruction method from binaries based on XML,” in Proceedings of the International Forum on Computer Science-Technology and Applications (IFCSTA '09), pp. 226–229, Chongqing, China, December 2009.
[32]
L. Tan, “The worst case execution time tool challenge 2006,” Technical Report for the External Test STTT, TR 045, ICB/Computer Science, University of Duisburg-Essen, 2007.
[33]
Q. Zhang and I. G. Harris, “A data flow fault coverage metric for validation of behavioral HDL descriptions,” in Proceedings of the International Conference on Computer-Aided Design (ICCAD '00), San Jose, Calif, USA, November 2000.
[34]
W. Sadiq and M. E. Orlowska, “Analyzing process models using graph reduction techniques,” Information Systems, vol. 25, no. 2, pp. 117–134, 2000.
[35]
D. Draheim, Business Process Technology: A Unified View on Business Processes, Workflows and Enterprise Applications, Springer, Berlin, Germany, 2010.
[36]
P. A. Brooks and A. M. Memon, “Automated GUI testing guided by usage profiles,” in Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE '07), pp. 333–342, Atlanta, Ga, USA, November 2007.
[37]
A. M. Memon, “An event-flow model of GUI-based applications for testing,” Software Testing Verification and Reliability, vol. 17, no. 3, pp. 137–157, 2007.
[38]
A. M. Memon, M. L. Soffa, and M. E. Pollack, “Coverage criteria for GUI testing,” in Proceedings of the 8th European Software Engineering Conference with the 9th ACM SIGSOFT International Symposium on the Foundations of Software Engineering, pp. 256–267, Vienna, Austria, September 2001.
[39]
H. Raiffa and R. Schlaifer, Applied Statistical Decision Theory, Division of Research, Graduate School of Business Administration, Harvard University, 3rd edition, 1964.
[40]
F. V. Jensen and T. D. Nielsen, Bayesian Networks and Decision Graphs, Springer, New York, NY, USA, 2nd edition, 2007.
[41]
J. J. Oliver, “Decision graphs—an extension of decision trees,” Tech. Rep. CS 92/173, Department of Computer Science, Monash University, Melbourne, Australia, 1992.
[42]
L. Tanner, M. Schreiber, J. G. H. Low et al., “Decision tree algorithms predict the diagnosis and outcome of dengue fever in the early phase of illness,” PLoS Neglected Tropical Diseases, vol. 2, no. 3, article e196, 2008.
