一、Call Graph的定义
Call Graph （调用图）是通常用于表示程序中各个函数之间调用关系的一种图，其中每个节点代表一个函数，每条有向边则代表函数之间的调用关系。Call Graph在软件维护、分析和测试中有着广泛的应用，例如：代码实现缺陷检测、代码优化以及变化可视化等领域。
二、Call Graph的构建
Call Graph的构建方法通常可以分为两种：静态构建和动态构建。
1. 静态构建
静态分析是在不执行程序的情况下对程序进行分析。一般需要对程序进行编译，在编译阶段生成中间代码或汇编代码，并最终对生成的中间代码或汇编代码进行解析和检测。该方法存在着精度高和适用范围广等优点。静态分析常用的工具如：GCC、LLVM、IDA等。
//静态构建callgraph的代码示例
1.构造callgraph
struct CallGraphBuilder
{
private Hashtable nodesVisited;
public CallGraphBuilder()
{
nodesVisited = new Hashtable();
}
public void constructCallGraph()
{
//do something
}
}
2. 遍历代码
public class Node
{
private String name;//代表函数名
private HashSet children;
public Node(String name)
{
this.name = name;
children = new HashSet();
}
public HashSet getChildren()
{
return children;
}
public void addChild(Node child)
{
children.add(child);
}
public String getName()
{
return name;
}
public String toString()
{
return getName();
}
}
public class CallGraph
{
private Hashtable nodes;
public CallGraph()
{
nodes = new Hashtable();
}
public Node getNode(String name)
{
return (Node)nodes.get(name);
}
public void addNode(Node node)
{
nodes.put(node.getName(), node);
}
public String toString()
{
String result = "";
for(Enumeration e = nodes.elements(); e.hasMoreElements();)
{
result += e.nextElement() + "\n";
}
return result;
}
}
3. 遍历函数
private void parseFunctionsInSection(Section section, int sectionLength)
{
int sectionIndex = 0;
int functionSize = sizeof(Function); //获取函数大小
while (sectionIndex getNode(func->name);
if (newNode == NULL)
{
newNode = new Node(func->name);
m_graph->addNode(newNode);
}
Node *currNode = newNode;
for (int j=0; jnumCallees; j++)
{
Node *calleeNode = m_graph->getNode(func->callees[j]);
if (calleeNode == NULL)
{
calleeNode = new Node(func->callees[j]);
m_graph->addNode(calleeNode);
}
currNode->addChild(calleeNode);
}
sectionIndex += functionSize;
}
}
2. 动态构建
动态分析是在程序运行的时候进行分析，通过跟踪用户的输入以及系统调用，动态分析能够检测出更多的可能性错误，如内存泄漏等。但是，由于在运行时必须启动程序的所有逻辑路径以及检测覆盖率，因此分析速度相对较慢，而且可能会存在漏检的情况。动态分析常用的工具如：Valgrind、Gcov等。
//动态构建callgraph的代码示例
1. 重载dlopen函数，实现安装intercepter
void *dlopen(const char *filename, int flag)
{
void *handle;
handle = (*orig_dlopen)(filename, flag);
if(!filename)
return handle;
if(string(filename).rfind("mylib.so") == string::npos)//不需要监控库调用。
return handle;
ofstream main_log;
main_log.open("main.log",ios::out|ios::app);
string exefilename = GetExeName();
main_log << "Exe Name is" << exefilename << endl;
char buf[256];
sprintf(buf, "hijacked dlopen:%s\n", filename);
m_librarystack.push_back(exefilename);//程序开始，将其作为stack底部元素处理
m_librarystack.push_back(string(filename));//程序开始，将其作为stack底部元素处理
main_log << "push lib:" << string(filename) <addNode(string(filename));//CallGraph中添加结点
return handle;
}
2. 插桩函数，记录函数调用信息
void callstack_enter(const char*symname)
{
int tid = (int) pthread_self();
// 栈为空则返回
if(m_librarystack.empty())
return ;
if(!IsTargetProcess()) // 记录目标进程相关信息，根据具体项目进行定义
return ;
pthread_mutex_lock(&s_mutex);
string exename = GetName();
string libname = m_librarystack.back();
// 重入函数则退出
if(symname == NULL || symname[0] == '\0' || strcmp(symname,"callstack_enter") == 0)
{
pthread_mutex_unlock(&s_mutex);
return;
}
// 忽略一些特定的函数
if(!IsFunctionValid(string(symname[1] == '_' ? symname+2 : symname)))
{
pthread_mutex_unlock(&s_mutex);
return;
}
// 添加调用边
if(callgraph && libname != exename)
{
pthread_mutex_lock(&callgraph_mutex);
callgraph->addEdge(m_latest_func, symname);
pthread_mutex_unlock(&callgraph_mutex);
}
m_calldepth++;
m_latest_func = symname;
pthread_mutex_unlock(&s_mutex);
}
3. 遍历CallGraph
void traverse_callgraph(string libname)
{
ofstream main_log;
main_log.open("main.log",ios::out|ios::app);
vector liblist;
Queue q;
q.enqueue(callgraph->getNode(libname));
main_log << libname << " ----" << endl;
while(!q.isEmpty())
{
Node *curnode;
Node **childnode;
curnode = q.dequeue();
main_log <getName() < ";
childnode = curnode->getChildrenList();
for(int i = 0; childnode[i] != NULL; i++)
{
main_log <getName() <getName()) == -1)
{
q.enqueue(childnode[i]);
liblist.push_back(childnode[i]->getName());
}
}
main_log << endl;
}
main_log << "end---" << endl;
mainlog.close();
}
三、Call Graph的应用
1. 检测函数嵌套
通过Call Graph，我们可以清晰地了解到程序中函数的调用关系，从而可以检测出函数嵌套的情况。同时，我们还可以根据规则，对于嵌套层数超过限制的函数进行警告或者修改。
//检测嵌套是否超过限制的代码示例
#include "CallGraph.h"
int max_depth = 4;
string cur_func;
int cur_depth = 0;
bool recursion = false;
void DetectRecursion(string func_name)
{
cur_func = func_name;
recursion = true;
Node *node = callgraph->getNode(func_name);
if(node == NULL)
{
return;
}
DFS(node,0);
if(recursion)
{
cout<<"ERROR! function "<<cur_func<<" has Recursion."< max_depth)
{
return;
}
Node **children;
children = node->getChildrenList();
if(children == NULL)
{
return;
}
for(i=0; children[i] != NULL; i++)
{
if(children[i]->getName() == cur_func)
{
recursion = true;
return ;
}
DFS(children[i],depth+1);
}
}
2. 检测函数调用关系
Call Graph允许我们对函数的调用链进行可视化操作，有助于开发者快速定位程序出现的问题。例如：一个函数的返回没有在调用者处进行检查，这就可能导致程序的异常退出；一个函数的形参和实参数量不一致，也可能导致程序的异常退出等。
//检测函数调用关系的代码示例
#include "CallGraph.h"
void analysis_function_call_relationship(Node *node)
{
Node **children;
children = node->getChildrenList();
if(children == NULL)
{
return;
}
int j = 0;
while(children[j] != NULL)
{
if(callgraph->findEdge(children[j]->getName(), node->getName()))
{
cout <getName() << " call " <getName() << endl;
}
j++;
}
j = 0;
while(children[j] != NULL)
{
analysis_function_call_relationship(children[j]);
j++;
}
}
3. 检测函数变化
Call Graph的变化可视化功能可以帮助开发者快速捕捉程序的变化情况。例如：在修改了一个函数后，会导致哪些函数的调用链发生了变化？这些变化对于整个程序的功能影响有多大？这些问题都可以通过使用Call Graph进行分析得到解答。
//检测函数变化的代码示例
#include "CallGraph.h"
void analysis_code_change(CallGraph *oldGraph, CallGraph *newGraph)
{
Node **oldNodes = oldGraph->getNodesList();
Node **newNodes = newGraph->getNodesList();
for(int i = 0; oldNodes[i] != NULL; i++)
{
if(newGraph->findNode(oldNodes[i]->getName()) == NULL)
{
cout<<"Function removed : "<getName() <findNode(newNode->getName()) == NULL)
{
cout<<"Function added : "<getName()<getNode(newNode->getName());
Node **oldChildren = oldNode->getChildrenList();
Node **newChildren = newNode->getChildrenList();
int oldChildNum = 0;
int newChildNum = 0;
while(oldChildren[oldChildNum] != NULL)
{
oldChildNum++;
}
while(newChildren[newChildNum] != NULL)
{
newChildNum++;
}
if(oldChildNum != newChildNum)
{
cout<<"Call relationship changed for: "<getName()<<endl;
}
}
}
}
四、总结
Call Graph是一种强大的工具，可以用于程序分析、测试和维护等领域。无论是静态构建还是动态构建，Call Graph的构建过程都需要使用算法对程序代码进行深入分析，从而得出准确的结果。在使用Call Graph进行应用时，我们还需要对函数的调用关系有着深刻的理解，并能够熟练地使用Call Graph提供的接口进行分析。最后，希望文章对于读者能够有所启发和帮助，加深对于Call Graph的理解。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/198303.html
微信扫一扫 
支付宝扫一扫 