ArkAnalyzer PAG构建技术：程序赋值图模型实现原理

在ArkTS语言的静态程序分析中，指针分析（Pointer Analysis）是确保代码质量和安全性的关键技术。传统的指针分析算法面临着精度与效率的权衡难题——如何在保证分析准确性的同时，控制计算复杂度？ArkAnalyzer通过引入**程序赋值图（Program Assignment Graph，PAG）** 模型，为ArkTS语言提供了高效的指针分析解决方案。PAG将复杂的指针关系抽象为图..

gitblog_00088

1118人浏览 · 2025-08-30 08:18:14

gitblog_00088 · 2025-08-30 08:18:14 发布

ArkAnalyzer PAG构建技术：程序赋值图模型实现原理

【免费下载链接】arkanalyzer 方舟分析器：面向ArkTS语言的静态程序分析框架项目地址: https://gitcode.com/openharmony-sig/arkanalyzer

引言：静态程序分析的核心挑战

在ArkTS语言的静态程序分析中，指针分析（Pointer Analysis）是确保代码质量和安全性的关键技术。传统的指针分析算法面临着精度与效率的权衡难题——如何在保证分析准确性的同时，控制计算复杂度？

ArkAnalyzer通过引入程序赋值图（Program Assignment Graph，PAG） 模型，为ArkTS语言提供了高效的指针分析解决方案。PAG将复杂的指针关系抽象为图结构，通过图遍历算法实现精确的指针指向关系推导。

PAG核心概念与架构设计

PAG节点类型体系

ArkAnalyzer的PAG模型定义了8种核心节点类型，每种类型对应不同的程序实体：

节点类型	枚举值	描述	典型用途
HeapObj	0	堆对象节点	new表达式创建的对象
LocalVar	1	局部变量节点	函数内的局部变量
RefVar	2	引用变量节点	实例字段、静态字段引用
Param	3	参数节点	函数参数
ThisRef	4	this引用节点	方法中的this指针
Function	5	函数节点	函数对象
GlobalThis	6	全局this节点	全局作用域的this
ExportInfo	7	导出信息节点	模块导出对象

PAG边类型分类

PAG边定义了6种不同的赋值关系，每种边类型具有特定的语义：

enum PagEdgeKind {
    Address,           // 地址赋值边：o = new Obj()
    Copy,              // 拷贝赋值边：a = b
    Load,              // 加载边：x = o.f
    Write,             // 存储边：o.f = x
    This,              // this传递边：method.call(obj)
    InterProceduralCopy // 过程间拷贝边：参数传递
}

PAG构建算法实现

函数级PAG构建

ArkAnalyzer采用分层构建策略，首先为每个函数构建独立的FuncPag：

mermaid

过程间PAG整合

通过Context-Sensitive分析，将函数级PAG整合为完整的程序PAG：

public buildPagFromFuncPag(funcID: FuncID, cid: ContextID): void {
    let funcPag = this.funcPags.get(funcID);
    if (funcPag === undefined) return;
    
    this.addEdgesFromFuncPag(funcPag, cid, funcID);
    this.addCallsEdgesFromFuncPag(funcPag, cid);
    this.addDynamicCallSite(funcPag, funcID, cid);
    this.addUnknownCallSite(funcPag, funcID);
}

动态调用处理机制

函数指针调用解析

对于ArkTS中的动态调用（函数指针、方法调用），PAG构建器采用基于指向集（Points-to Set）的解析策略：

private getDynamicCallee(ptNode: PagNode, value: Value, 
                        ivkExpr: AbstractInvokeExpr, cs: ICallSite): ArkMethod[] {
    if (ptNode instanceof PagFuncNode) {
        // 函数指针调用：直接获取方法签名
        return [this.scene.getMethod(ptNode.getMethod())!];
    }
    
    // 实例方法调用：基于类继承层次解析
    let calleeName = ivkExpr.getMethodSignature().getMethodSubSignature().getMethodName();
    let cls: ArkClass | null = this.scene.getClass(
        (value as ArkNewExpr).getType().getClassSignature()
    );
    
    // 遍历继承链查找方法实现
    while (cls) {
        let method = cls.getMethodWithName(calleeName);
        if (method) return [method];
        cls = cls.getSuperClass();
    }
    
    return [];
}

上下文敏感分析

ArkAnalyzer支持多种上下文敏感策略，通过ContextSelector实现：

switch (config.contextType) {
    case ContextType.CallSite:
        this.ctxSelector = new KCallSiteContextSelector(kLimit);
        break;
    case ContextType.Obj:
        this.ctxSelector = new KObjContextSelector(kLimit);
        break;
    case ContextType.Func:
        this.ctxSelector = new KFuncContextSelector(kLimit);
        break;
}

高级特性实现

this指针处理

PAG对this指针进行特殊处理，确保面向对象特性的正确分析：

public addThisRefCallEdge(cid: ContextID, baseLocal: Local, 
                         callee: ArkMethod, calleeCid: ContextID): NodeID {
    let thisRefNodeID = this.recordThisRefNode(callee, calleeCid);
    let srcNodeId = this.pag.hasCtxNode(cid, baseLocal);
    
    this.pag.addPagEdge(this.pag.getNode(srcNodeId) as PagNode, 
                       this.pag.getNode(thisRefNodeID) as PagNode, 
                       PagEdgeKind.This);
    return srcNodeId;
}

插件架构扩展

通过插件机制支持SDK方法、存储系统等特殊处理：

const pluginResult = this.pluginManager.processCallSite(
    staticCS, cid, baseClassPTNode, this.cg
);
if (pluginResult.handled) {
    logger.debug(`Plugin handled call site ${cs.callStmt.toString()}`);
} else {
    this.processNormalMethodPagCallEdge(staticCS, cid, baseClassPTNode);
}

性能优化策略

惰性构建与缓存

PAG采用惰性构建策略，避免不必要的计算：

public getOrClonePagNode(src: PagNode, basePt: NodeID): PagNode {
    let cloneSet = this.clonedNodeMap.get(src.getID());
    if (cloneSet) {
        let nodeID = cloneSet.get(basePt);
        if (nodeID) return this.getNode(nodeID) as PagNode;
    }
    
    // 未找到时创建新节点
    let cloneNode = this.addPagNode(src.getCid(), src.getValue(), src.getStmt(), false);
    cloneNode.setClonedFrom(src.getID());
    cloneSet.set(basePt, cloneNode.getID());
    return cloneNode;
}

工作列表算法

采用高效的工作列表算法管理分析过程：

public handleReachable(): boolean {
    if (this.worklist.length === 0) return false;
    
    this.funcHandledThisRound.clear();
    while (this.worklist.length > 0) {
        let csFunc = this.worklist.shift() as CSFuncID;
        this.buildPagFromFuncPag(csFunc.funcID, csFunc.cid);
        this.addToFuncHandledListThisRound(csFunc.funcID);
    }
    return true;
}