深入理解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 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/zh-tw/n/198303.html