THE ALGORITHM OF CONSTRUCTING CONTROL FLOW GRAPH BASED ON A PROGRAM WRITTEN IN C

Authors

  • D. V. Fedasyuk Lviv Polytechnic National University, Lviv, Ukraine, Ukraine
  • R. S. Chopey Lviv Polytechnic National University, Lviv, Ukraine, Ukraine

DOI:

https://doi.org/10.15588/1607-3274-2018-2-17

Keywords:

control flow graph, automated testing, Keil uVision, ARM, embedded systems.

Abstract

Actuality. The work considers the problem of automated construction of the control flow graph using the text of a program written in
C. The graph construction is an important step in the structural testing of embedded systems.
Objective. The work is aimed at creation of a fast algorithm for constructing the control flow graph from a source code. Such an
automatically generated graph can be used by existing tools for automated testing.
Method. We propose an algorithm for constructing the control flow graph from the program written in C language, which preprocesses
the source code of the program by removing comments and blank lines, determines the number of vertices and edges of the control flow graph
by means of program text syntactic analysis, and then formats, fills and stores the incidence matrix in a separate text file. This file can be
passed as input data for some existing automated testing tools. Moreover, the content of the text file can be visualized by existing tools for graphic representation of graphs.
Results. We’ve developed a software module that implements the proposed algorithm. The module can be used for experiments aimed at
studying the dependence of the control flow graph’s time construction on the amount of lines in a source code.
Conclusions. The conducted experiments confirmed the operability of the proposed algorithm and the software module developed on its
basis. The results have proved the applicability of the algorithm, thus it can be recommended for further use together with automated testing
tools to reduce the time required for testing of embedded software.

References

Aho A. V., Lam M. S., Sethi R., Ullman J. D. : eds. Compilers: Principles, techniques, and tools. Amsterdam, Addison Wesley, 2007, 1038 p. ISBN: 0321486811

Allen F., Cocke J. Graph-theoretic constructs for program control flow analysis : Research Report : RC-3923, IBM Thomas J. Watson Research Center – IBM, 1972, 130 p.

Ferrante J., Ottenstein K. J., Warren J. D. The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems, 1987, No. 9, pp. 319–349. DOI: 10.1145/24039.24041

Gold R. On cyclomatic complexity and decision graphs, Proceedings of the 10th International Conference of Numerical Analysis and Applied Mathematics (ICNAAM ’12), 2007,

Vol. 1479, pp. 2170–2173. DOI: 10.1063/1.4756622

Henderson-Sellers B., Tegarden D. The theoretical extension of two versions of cyclomatic complexity to multiple entry/exit modules, Software Quality Journal, 1994, Vol. 3, pp. 253–269. DOI: 10.1007/BF00403560

Jalote P. An integrated approach to software engineering. New York, Springer, 2005, 566 p. ISBN: 978-0-387-28132-2

Sommerville I. Software Engineering. Pearson, Addison Wesley, 2004, 750 p. ISBN: 0321210263

Frankl P. G., Weyuker E. J. Provable improvements on branch testing, IEEE Transactions on Software Engineering, 1993, Vol. 19, pp. 962–975. DOI: 10.1109/32.245738

Gold R. Control flow graphs and code coverage, International Journal of Applied Mathematics & Computer Science, 2010, Vol. 20, pp. 739–749. DOI: 10.2478/v10006-010-0056-9 10. Zhu H., Hall P. A., May J. H. Software unit test coverage and adequacy, ACM Computing Surveys, 1997, Vol. 29, pp. 366–427. DOI: 10.1145/267580.267590

Fedasyuk D., Chopey R., Knysh B. Architecture of a tool for

automated testing the worst-case execution time of real-time

embedded systems’ firmware, 14th International conference, The experience of designing and application of cad systems in

microelectronics, 2017, pp. 278–282. DOI: 10.1109/

CADSM.2017.7916134

Hossain M. I., Lee W. J., Youngsul S. Integration testing approach using usage patterns of global variables [Electronic resource], Researchgate, 2012. Access mode: https://www.researchgate.net/publication/255173431_Integration_Testing_Approach_using_

Usage_Patterns_of_Global_Variables.

Muha Ju. P., Sekachjov V. A. Algoritm dlja preobrazovanija

programmnogo koda na jazyke vysokogo urovnja v graf-shemu, Izvestija volgogradskogo gosudarstvennogo tehnicheskogo universiteta, 2009, No. 3, pp. 58–63.

Cooper K. D., Harvey T. J., Waterman T. Building a control-flow graph from scheduled assembly code [Electronic resource], Researchgate, 2013. Access mode: https://www.researchgate.net/publication/2572750.

Amine A., Mohammed B., Jean-Louis L. Generating control flow graph from Java card byte code, Information Science and

Technology (CIST), 2014, pp. 206–212. DOI: 10.1109/

CIST.2014.7016620 16. Graph Online [Electronic resource]: Creating graph from

incidence matrix. Access mode: http://graphonline.ru/en/

Downloads

How to Cite

Fedasyuk, D. V., & Chopey, R. S. (2018). THE ALGORITHM OF CONSTRUCTING CONTROL FLOW GRAPH BASED ON A PROGRAM WRITTEN IN C. Radio Electronics, Computer Science, Control, (2). https://doi.org/10.15588/1607-3274-2018-2-17

Issue

No. 2 (2018): Radio Electronics, Computer Science, Control

Section

Progressive information technologies

License

Copyright (c) 2018 D. V. Fedasyuk, R. S. Chopey

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Creative Commons Licensing Notifications in the Copyright Notices

The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.

The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.

The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.