Вестник БГУ. Математика, информатика
Библиографическое описание:
, МЕТОД ВИЗУАЛИЗАЦИИ ГРАФА ПОТОКОВ УПРАВЛЕНИЯ // Вестник БГУ. Математика, информатика. - 2018. №2. . - С. 50-62.
Заглавие:
МЕТОД ВИЗУАЛИЗАЦИИ ГРАФА ПОТОКОВ УПРАВЛЕНИЯ
Финансирование:
Коды:
Аннотация:
В работе предложен метод визуализации графа потоков управления, позволяющий анализировать сложные графовые представления программ, полученные после обработки исходного кода компилятором либо в процессе декомпиляции исполняемого кода. Метод основан на выделении в управляющем графе регионов с одним входным и одним выходным узлом с последую- щей их заменой на абстрактные узлы. Таким образом, в результате выполнения семантически эквивалентных преобразований исходный граф сворачивается в один абстрактный узел, содержащий в себе иерархию выделенных регионов, каждому из которых ставится в соответствие один из предопределенных шаблонов отображения. В итоге задача визуализации управляющего графа сводится к описанию правил отображения шаблонов. Предложенный метод позволяет выделять в управляющем графе подграфы, соответствующие высокоуровневым операторам языков программирования, что дает возможность использовать изобразительные соглашения, принятые при рисовании блок-схем.
Ключевые слова:
визуализация; управляющий граф; структурный анализ; исходный код; декомпиляция; блок-схема; машинный код; программа; компилятор; доминатор.
Список литературы:
Frohlich M., Werner M. Demonstration of the Interactive Graph – Visualization Sytem daVinci // LNCS 894. 1995. P. 266–269.
Sander G. Graph layout through the VCG tool // LNCS 894. 1995. P. 194–205.
Himsolt M. Graphlet system (system demonstration) // LNCS 1990. 1996. P. 233–240.
Lauer H., Ettrich M., Soukup K. GraVis system demonstration // LNCS 1353. 1997. P. 344–349.
Bridgeman S., Garg A., Tamassia R. A graph drawing and translation service on the WWW // LNCS 1190. 1996. P. 45–52.
Gasner E. R., North S. C. An open graph visualization system and its applications to software engineering. URL: http://www.graphviz.org/Documentation/GN99.pdf (дата обращения: 12.06.2018).
Золотухин Т. А. Визуализация графов при помощи программного средства Visual Graph // Информатика в науке и образовании. 2012. С. 135–148.
Михайлов А. А. Анализ графа потоков управления в задаче декомпиляции подпрограмм объектных файлов dcuil // Вестн. Новосиб. гос. ун-та. Сер. Инфор- мационные технологии. 2014. Т. 12, вып. 2. С. 74–79.
Касьянов В. Н. Визуализация информации на основе графовых моделей // Вычисл. технологии. 1999. Т. 11, № 11. С. 1123–1135.
Tutte W. T. How to draw a graph // Proc. London Math. Society. 1963. Vol. 13(52). P. 743–768.
Eades P. A heuristic for graph drawing // Congressus Numerantium. 1984. Vol. 42. P. 149–160.
Kamada T., Kawai S. An algorithm for drawing general undirected graphs // In- form. Process. Lett. 1989. Vol. 31. P. 7–15.
Eades P., Xuemin L. How to draw a directed graph // Visual Languages. 1989. IEEE Workshop on. 1989. P. 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 Queen- sland. 1986. P. 13.
Alfred V. Aho, Sethi Ravi, Jeffrey D. Ullman. Compilers: Principles, Tech- niques And Tools. Publisher: Addison Wesle, 1986. P. 1038.
Cifuentes C. Structuring decompiled graphs // Compiler Construction. Springer Berlin Heidelberg. 1996. P. 91–105.
Johnson R., Pearson D. and Pingali K. Finding regions fast: Single entry single exit and control regions in linear time. Tech. rep. Cornell University, Ithaca, NY, 1993. P. 13.
Sander G. Graph layout through the VCG tool // LNCS 894. 1995. P. 194–205.
Himsolt M. Graphlet system (system demonstration) // LNCS 1990. 1996. P. 233–240.
Lauer H., Ettrich M., Soukup K. GraVis system demonstration // LNCS 1353. 1997. P. 344–349.
Bridgeman S., Garg A., Tamassia R. A graph drawing and translation service on the WWW // LNCS 1190. 1996. P. 45–52.
Gasner E. R., North S. C. An open graph visualization system and its applications to software engineering. URL: http://www.graphviz.org/Documentation/GN99.pdf (дата обращения: 12.06.2018).
Золотухин Т. А. Визуализация графов при помощи программного средства Visual Graph // Информатика в науке и образовании. 2012. С. 135–148.
Михайлов А. А. Анализ графа потоков управления в задаче декомпиляции подпрограмм объектных файлов dcuil // Вестн. Новосиб. гос. ун-та. Сер. Инфор- мационные технологии. 2014. Т. 12, вып. 2. С. 74–79.
Касьянов В. Н. Визуализация информации на основе графовых моделей // Вычисл. технологии. 1999. Т. 11, № 11. С. 1123–1135.
Tutte W. T. How to draw a graph // Proc. London Math. Society. 1963. Vol. 13(52). P. 743–768.
Eades P. A heuristic for graph drawing // Congressus Numerantium. 1984. Vol. 42. P. 149–160.
Kamada T., Kawai S. An algorithm for drawing general undirected graphs // In- form. Process. Lett. 1989. Vol. 31. P. 7–15.
Eades P., Xuemin L. How to draw a directed graph // Visual Languages. 1989. IEEE Workshop on. 1989. P. 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 Queen- sland. 1986. P. 13.
Alfred V. Aho, Sethi Ravi, Jeffrey D. Ullman. Compilers: Principles, Tech- niques And Tools. Publisher: Addison Wesle, 1986. P. 1038.
Cifuentes C. Structuring decompiled graphs // Compiler Construction. Springer Berlin Heidelberg. 1996. P. 91–105.
Johnson R., Pearson D. and Pingali K. Finding regions fast: Single entry single exit and control regions in linear time. Tech. rep. Cornell University, Ithaca, NY, 1993. P. 13.
Статья.pdf