Control flow graphs and code coverage

Robert Gold

International Journal of Applied Mathematics and Computer Science (2010)

  • Volume: 20, Issue: 4, page 739-749
  • ISSN: 1641-876X

Abstract

top
The control flow of programs can be represented by directed graphs. In this paper we provide a uniform and detailed formal basis for control flow graphs combining known definitions and results with new aspects. Two graph reductions are defined using only syntactical information about the graphs, but no semantical information about the represented programs. We prove some properties of reduced graphs and also about the paths in reduced graphs. Based on graphs, we define statement coverage and branch coverage such that coverage notions correspond to node coverage, and edge coverage, respectively.

How to cite

top

Robert Gold. "Control flow graphs and code coverage." International Journal of Applied Mathematics and Computer Science 20.4 (2010): 739-749. <http://eudml.org/doc/208022>.

@article{RobertGold2010,
abstract = {The control flow of programs can be represented by directed graphs. In this paper we provide a uniform and detailed formal basis for control flow graphs combining known definitions and results with new aspects. Two graph reductions are defined using only syntactical information about the graphs, but no semantical information about the represented programs. We prove some properties of reduced graphs and also about the paths in reduced graphs. Based on graphs, we define statement coverage and branch coverage such that coverage notions correspond to node coverage, and edge coverage, respectively.},
author = {Robert Gold},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {directed graph; control flow graph; graph reduction; software testing; statement coverage; branch coverage},
language = {eng},
number = {4},
pages = {739-749},
title = {Control flow graphs and code coverage},
url = {http://eudml.org/doc/208022},
volume = {20},
year = {2010},
}

TY - JOUR
AU - Robert Gold
TI - Control flow graphs and code coverage
JO - International Journal of Applied Mathematics and Computer Science
PY - 2010
VL - 20
IS - 4
SP - 739
EP - 749
AB - The control flow of programs can be represented by directed graphs. In this paper we provide a uniform and detailed formal basis for control flow graphs combining known definitions and results with new aspects. Two graph reductions are defined using only syntactical information about the graphs, but no semantical information about the represented programs. We prove some properties of reduced graphs and also about the paths in reduced graphs. Based on graphs, we define statement coverage and branch coverage such that coverage notions correspond to node coverage, and edge coverage, respectively.
LA - eng
KW - directed graph; control flow graph; graph reduction; software testing; statement coverage; branch coverage
UR - http://eudml.org/doc/208022
ER -

References

top
  1. Jalote, P. (2005). An Integrated Approach to Software Engineering, Springer, New York, NY. Zbl0784.68002
  2. Kosaraju, S. (1973). Analysis of structured programs, Proceedings of the 5th Annual ACM Symposium on Theory of Computing, Austin, TX, USA, pp. 240-252. Zbl0305.68011
  3. McCabe, T. (1976). A complexity measure, IEEE Transactions on Software Engineering SE-2(4): 308-320. Zbl0352.68066
  4. Paige, M. (1977). On partitioning program graphs, IEEE Transactions on Software Engineering SE-3(6): 386-393. Zbl0361.68025
  5. Rapps, S. and Weyuker, E. (1982). Data flow analysis techniques for test data selection, Proceedings of the 6th International Conference on Software Engineering, Tokyo, Japan, pp. 272-278. 
  6. Sommerville, I. (2004). Software Engineering, 7th Edn., Pearson Education Limited, Boston, MA. Zbl1151.68300
  7. Tan, L. (2006). The Worst Case Execution Time Tool Challenge 2006: The External Test, Technical report, http://www.absint.com/ait/wcet tool challenge 2006 final report.pdf. 
  8. White, L. (1981). Basic mathematical definitions and results in testing, in B. Chandrasekaran and S. Radicchi (Eds.), Computer Program Testing, North-Holland, New York, NY. 
  9. Zhu, H., Hall, P. and May, J. (1997). Software unit test coverage and adequacy, ACM Computing Surveys 29(4): 366-427. 

NotesEmbed ?

top

You must be logged in to post comments.