BSU Bulletin. Mathematics, Informatics
Bibliographic description:
, CONTROL FLOW GRAPH VISUALIZATION // BSU Bulletin. Mathematics, Informatics. - 2018. №2. . - С. 50-62.
Title:
CONTROL FLOW GRAPH VISUALIZATION
Financing:
Codes:
Annotation:
The article presents a technique for analyzing and visualizing the control flow graph of a compiled software. The method is based on allocating regions with one input and one output node in the control graph with their subsequent replacement by ab- stract nodes. Thus, as a result of performing semantically equivalent transforma- tions, the original graph is collapsed into one abstract node that contains a hierarchy of selected regions, each of which is associated with one of the predefined display patterns. As a result, the task of visualization of the control graph is reduced to the description of rules for displaying patterns. The proposed method makes it possible to recognize the high-level programming structures and user statements to construct a flow-chart notation of the original program.
Keywords:
visualization; control graph; structural analysis; back code; decompiling; chart; machine code; program; compiler; dominator.
List of references:
Frohlich M., Werner M. Demonstration of the Interactive Graph – Visualization Sytem da Vinci. LNCS. 1995. V. 894. Pp. 266–269.
Sander G. Graph Layout through the VCG Tool. LNCS. V. 894. 1995. Pp. 194– 205.
Himsolt M. Graphlet System (system demonstration). LNCS. V. 1990. 1996. P. 233–240.
Lauer H., Ettrich M., Soukup K. GraVis System Demonstration. LNCS. V. 1353. 1997. Pp. 344–349.
Bridgeman S., Garg A., Tamassia R. A Graph Drawing and Translation Service on the WWW. LNCS. No. 1190. 1996. Pp. 45–52.
Gasner E. R., North S. C. An Open Graph Visualization System and Its Applica- tions to Software Engineering. URL: http://www.graphviz.org/Documentation/ GN99.pdf (accessed June 12, 2018).
Zolotukhin T. A. Vizualizatsiya grafov pri pomoshchi programmnogo sredstva [Graph Visualization by Means of Visual Graph Software]. Informatika v nauke i obra- zovanii —Informatics in Science and Education. 2012. Pp. 135–148.
Mikhailov A. A. Analiz grafa potokov upravleniya v zadache dekompilyatsii podprogramm ob"ektnykh failov dcuil [Control Flow Graph Analysis in the Problem of Decompiling Subprograms of dcuil Object Files]. Vestnik Novosibirskogo gosu- darstvennogo universiteta. Ser. Informatsionnye tekhnologii — Bulletin of Novosibirsk State University. Ser. Information Technology. 2014. V. 12. No. 2. Pp. 74–79.
Kas'yanov V. N. Vizualizatsiya informatsii na osnove grafovykh modelei Vychis- litel’nye tekhnologii [Visualization of Information Based on Graph Models]. 1999. V. 11. No. 11. Pp. 1123–1135.
Tutte W. T. How to Draw a Graph. Proc. London Math. Society. 1963. No. 13(52). Pp. 743–768.
Eades P. A Heuristic for Graph Drawing. Congressus Numerantium. 1984. No. 42. Pp. 149–160.
Kamada T., Kawai S. An Algorithm for Drawing General Undirected Graphs.
Inform. Process. Lett. 1989. No. 31. Pp. 7–15.
Eades P., Xuemin L. How to Draw a Directed Graph. IEEE Workshop on Visual Languages. 1989. Pp. 13–17.
Eades P. and Wormald N. C. The Median Heuristic for Drawing 2-Layered Networks. Technical Report 69. Dept. of Computer Science. University of Queensland, 1986. P. 13.
Aho A. V., Ravi Sethi, Jeffrey D. Compilers: Principles, Techniques, and Tools. Ullman: Addison Wesle, 1986. P. 1038.
Cifuentes C. Structuring decompiled graphs. Compiler Construction. Berlin, Heidelberg: Springer, 1996. Pp. 91–105.
Johnson R., Pearson D., and Pingali K. Finding Regions Fast: Single Entry Sin- gle Exit and Control Regions in Linear Time. Tech. rep. NY, Ithaca: Cornell Univer- sity, 1993. P. 13.
Sander G. Graph Layout through the VCG Tool. LNCS. V. 894. 1995. Pp. 194– 205.
Himsolt M. Graphlet System (system demonstration). LNCS. V. 1990. 1996. P. 233–240.
Lauer H., Ettrich M., Soukup K. GraVis System Demonstration. LNCS. V. 1353. 1997. Pp. 344–349.
Bridgeman S., Garg A., Tamassia R. A Graph Drawing and Translation Service on the WWW. LNCS. No. 1190. 1996. Pp. 45–52.
Gasner E. R., North S. C. An Open Graph Visualization System and Its Applica- tions to Software Engineering. URL: http://www.graphviz.org/Documentation/ GN99.pdf (accessed June 12, 2018).
Zolotukhin T. A. Vizualizatsiya grafov pri pomoshchi programmnogo sredstva [Graph Visualization by Means of Visual Graph Software]. Informatika v nauke i obra- zovanii —Informatics in Science and Education. 2012. Pp. 135–148.
Mikhailov A. A. Analiz grafa potokov upravleniya v zadache dekompilyatsii podprogramm ob"ektnykh failov dcuil [Control Flow Graph Analysis in the Problem of Decompiling Subprograms of dcuil Object Files]. Vestnik Novosibirskogo gosu- darstvennogo universiteta. Ser. Informatsionnye tekhnologii — Bulletin of Novosibirsk State University. Ser. Information Technology. 2014. V. 12. No. 2. Pp. 74–79.
Kas'yanov V. N. Vizualizatsiya informatsii na osnove grafovykh modelei Vychis- litel’nye tekhnologii [Visualization of Information Based on Graph Models]. 1999. V. 11. No. 11. Pp. 1123–1135.
Tutte W. T. How to Draw a Graph. Proc. London Math. Society. 1963. No. 13(52). Pp. 743–768.
Eades P. A Heuristic for Graph Drawing. Congressus Numerantium. 1984. No. 42. Pp. 149–160.
Kamada T., Kawai S. An Algorithm for Drawing General Undirected Graphs.
Inform. Process. Lett. 1989. No. 31. Pp. 7–15.
Eades P., Xuemin L. How to Draw a Directed Graph. IEEE Workshop on Visual Languages. 1989. Pp. 13–17.
Eades P. and Wormald N. C. The Median Heuristic for Drawing 2-Layered Networks. Technical Report 69. Dept. of Computer Science. University of Queensland, 1986. P. 13.
Aho A. V., Ravi Sethi, Jeffrey D. Compilers: Principles, Techniques, and Tools. Ullman: Addison Wesle, 1986. P. 1038.
Cifuentes C. Structuring decompiled graphs. Compiler Construction. Berlin, Heidelberg: Springer, 1996. Pp. 91–105.
Johnson R., Pearson D., and Pingali K. Finding Regions Fast: Single Entry Sin- gle Exit and Control Regions in Linear Time. Tech. rep. NY, Ithaca: Cornell Univer- sity, 1993. P. 13.
Article.pdf