Как мы можем сравнить два графика зависимости программы?

Question

Это один из примеров график зависимости программы. **

Это код, который генерирует выше графика. Я хочу сравнить два графика этих типов, есть ли какой-либо метод, который сравнивает этот граф для процента сходства. Я также думаю, что для сравнения изображения графика, чтобы получить процент сходства, пожалуйста, предложите, как я могу это сделать.

digraph cfg { 
subgraph cluster_sum { 
graph [label="sum"]; 
s1[label="i = 0;"]; 
s1 -> s2; 
s2[label="sum_0 = 0;"]; 
s2 -> s3; 
s3[label="i = x;"]; 
s3 -> s4; 
s4[label="<loop>"]; 
s4 -> s6; 
s6[label="if i <= y"]; 
s6 -> s8; 
s6 -> s7; 
s7[label="<break>"]; 
s7 -> s11; 
s8[label="<enter block>"]; 
s8 -> s9; 
s9[label="sum_0 -= i;"]; 
s9 -> s10; 
s10[label="i ++;"]; 
s10 -> s4; 
s11[label="<return>"]; 
} 
subgraph cluster_main { 
    graph [label="main"]; 
    s13[label="res = 0;"]; 
    s13 -> s14; 
    s14[label="a = 2;"]; 
    s14 -> s15; 
    s15[label="b = 5;"]; 
    s15 -> s16; 
    s16[label="res = sum(a,b);"]; 
    s16 -> s17; 
    s17[label="printf(\"%d\",res);"]; 
    s17 -> s18; 
    s18[label="__retres = 0;"]; 
    s18 -> s21; 
    s21[label="<return>"]; 
    } 
    } 

Answer 1

ну, в общем, он является открытым и неразрешим? вопрос. Вы можете оценить обе программы, используя абстрактную интерпретацию и сравнить результаты. Но я не думаю, что вы ожидаете ответа.

Самый простой подход заключается в преобразовании графика (который может быть прочитан в OCaml с использованием библиотеки ocamlgraph) в нормализованную форму, где все синтаксические различия удаляются (например, все переменные переименовываются с использованием общей схемы именования или заменяются регулярные выражения), а затем вы можете сравнить полученные графики, основываясь на вашей функции сравнения.

Но это, конечно, просто хак. Для более сложных вы должны пройти несколько курсов по анализу программ, написать диссертацию и ответить на вопрос, что в целом это неразрешимо ... Но в конце концов вы напишете что-то вроде BinDiff.

Что касается сравнения двух изображений, то я думаю, что это еще более грубый взлом. Но обычный подход - сделать двумерную свертку, которая вернет вам меру равенства. В библиотеке OCaml fftw есть все, что вам нужно.

Answer 2

Плохой подход, сравнивающий графики при просмотре их визуализированных изображений: Graphviz свободно заменяет положение узлов и в значительной степени даже с небольшой модификацией графиков.

Вы должны сравнивать графики более алгебраическим образом, но алгоритм будет сильно зависеть от того, как вы определяете «подобие». Если бы я был вами, я попробую отредактировать расстояние от деревьев. Недавно я использовал его для измерения «подобия» выражений типа OCaml (да, их АСТ - это в основном деревья, но могут иметь петли) и получили хороший результат. Вы можете найти много информации, выполнив поиск «редактирование расстояния от дерева».

Потоки выполнения программы имеют петли, поэтому, вероятно, их следует сравнивать как общие направленные графы, а не деревья с небольшим количеством циклов. Я считаю, что для этого должны быть некоторые исследовательские работы, но я вообще не осведомлен.

Для реализации я никогда не пробовал, но OCamlDot (http://zoggy.github.io/ocamldot/) можно было использовать для анализа формата точечного файла для получения алгебраического представления графов.