深入理解Call Graph

一、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 < sectionLength)//

    {
        Function *func = (Function *) &section[sectionIndex];
        Node *newNode = m_graph->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) << endl;
    main_log.close();  

    callgraph->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 << curnode->getName() << " ------> ";  
        childnode = curnode->getChildrenList(); 

        for(int i = 0; childnode[i] != NULL; i++)
        {
            main_log << childnode[i]->getName() << ",";
            if(CheckInList(liblist,childnode[i]->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 "<<<" 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 << node->getName() << " call " << children[j]->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 : "<< oldNodes[i]->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()<
      


       
四、总结


       
Call Graph是一种强大的工具，可以用于程序分析、测试和维护等领域。无论是静态构建还是动态构建，Call Graph的构建过程都需要使用算法对程序代码进行深入分析，从而得出准确的结果。在使用Call Graph进行应用时，我们还需要对函数的调用关系有着深刻的理解，并能够熟练地使用Call Graph提供的接口进行分析。最后，希望文章对于读者能够有所启发和帮助，加深对于Call Graph的理解。