001-新的调用图

总计一下新的调用图

思路：

考虑到通常的图神经网络检测方法使用的图都是基于单独的类调用图、函数调用图、api调用图等，或是在此基础上增加图剪枝和压缩策略减少图的大小从而降低计算复杂度。安卓程序的恶意行为通常具有跨层次协作特征，在架构层通过类继承实现恶意代码注入（如BaseAdapter子类监听用户输入），在逻辑层通过方法间调用构建攻击链（如init() → executeExploit()），系统层通过敏感API组合触发恶意负载（如getLocation + encrypt + sendHTTP）。现有方法的单层次图结构可能导致关键攻击模式的信息割裂。我们构建了一个融合多层次多模态特征信息的图结构来进行安卓恶意软件检测

方法论

特征预处理

源代码反编译

我们首先使用 APKTool 对 APK 文件进行解压，得到 “AndroidManifest. xml” 和 “classes.dex” 文件，使用 LibRadar检测 APK 文件中包含的第三方库，然后使用 JADX 对 “classes.dex” 文件进行反编译，得到 Java 的源代码。

敏感API数据库构建

应用程序编程接口（API）是一些预定义的函数。通过API，可以为应用程序快速扩展功能，而无需了解其如何实现，从而提高开发效率。

在java源代码中，class中的方法会调用API，而调用API需要对应的权限，权限又有其对于的android:protectionLevel。根据Android官方文档，Android权限声明中的android:protectionLevel用于说明权限中隐含的潜在风险，并指示系统在确定是否将权限授予请求授权的应用时要遵循的流程。每个保护级别都包含基本权限类型以及零个或多个标志。例如，"dangerous" 保护级别没有标志。相反，保护级别 "signature|privileged" 是 "signature" 基本权限类型和 "privileged" 标志的组合。【<权限> | Android Developers】我们重点关注与安全相关的四种 protection Level
1.normal：普通权限，应用程序可以在安装时自动获得对隔离的应用级功能的访问，对其他应用程序、系统或用户的风险最小化。
2. Signature：只有当应用使用与定义权限的应用或操作系统相同的证书进行签名时，系统才会授予该应用签名权限。实现特权服务（例如自动填充或 VPN 服务）的应用程序也会使用签名权限。这些应用需要服务绑定签名权限，以便只有系统才能绑定到这些服务。
3. dangerous：具有较高风险的权限，此类权限允许请求授权的应用访问用户私人数据或获取可对用户造成不利影响的设备控制权。
4. privileged：特权权限，仅授予作为特权应用程序安装在系统映像上的应用程序。

==【GCN_AMD】文章提出从安卓源代码（AOSP）中提取API所需权限、权限的protection level从而组合成API-protection level映射表，我们参考【GCN_AMD】==等人提出的方法通过解析AOSP源码，提取@SystemApi、@RequiresPermission等注解信息，共标注1625个核心API，并建立映射表。我们将其赋予相应风险系数后的分布如下表所示：

保护等级	API数量	占比	风险系数	示例API
Privileged	283	17.5%	0.9	sendSMS
Dangerous	479	29.5%	0.7	getDeviceId
Signature	622	38.1%	0.5	installPackage
Normal	241	14.9%	0.1	getSystemService

语义特征提取

介绍CodeBERT

代码切片

为克服预训练模型CodeBERT的512 tokens输入限制，提出基于抽象语法树（AST）的上下文感知分段算法，其设计遵循三个核心原则：

语法完整性约束：以语法结构单元（如if/for/try代码块）为不可分割的最小单元，避免拆分导致语义断裂
语义关键点保留：通过敏感API数据库（包含356个高风险系统API）确保每个分段至少包含一个关键语义元素
动态重叠机制：对长度超过512 tokens的超长代码块，采用30%重叠率的滑动窗口切分，保持上下文连贯性

算法1 代码分段算法伪代码如下：

def split_code(code):  
    ast = parse_ast(code)  # 生成抽象语法树  
    chunks = []  
    current_chunk = []  
    for node in ast.traverse():  
        if token_count(current_chunk + node) > 500:  
            chunks.append(current_chunk)  
            current_chunk = [node]  # 新建分片  
        else:  
            current_chunk.append(node)  
    return filter_key_chunks(chunks)  # 过滤无关键语义的分段

算法首先通过深度优先遍历AST节点，在保证语法完整性的前提下进行动态分片。后处理阶段采用基于规则的关键词匹配过滤器，丢弃不包含敏感API或安全关键词的分段。实验表明，该算法在AndroZoo数据集上实现98.3%的语义完整性保持率。

深度语义特征提取

CodeBERT编码

代码语义特征通过预训练模型CodeBERT提取，其优势在于：

保留代码的语法结构特性（如控制流、数据依赖）
捕捉潜在的安全敏感模式（如加密操作、反射调用）
128维向量可平衡信息密度与计算效率

对每个代码分段 $C_{i}$ 生成语义向量：

h_{i} = CodeBERT (C_{i}) \in R^{768}

其中，分段编码采用均值池化策略：

h_{i} = \frac{1}{L} \sum_{t = 1}^{L} h_{i}^{(t)}

特征压缩网络

提出层次化Transformer压缩器（如图2），在保证性能的同时降低计算复杂度：

局部窗口注意力：将n个分段划分为k组 $k = ⌈ n / 8 ⌉$ ，组内做多头注意力

h_{g}^{(l)} = Attention (W_{q} H_{g}, W_{k} H_{g}, W_{v} H_{g})

跨组池化：对各组输出进行动态加权池化 $z = \sum_{g = 1}^{k} α_{g} \cdot MaxPool (h_{g}^{(l)})$
轻量级投影：双线性映射降维

z_{o u t} = W_{2} (GELU (W_{1} z))

优势对比：

方法	参数量	F1值	时延(ms)
Hier-Transformer	0.9M	93.5%	9.7
CNN	0.3M	91.2%	5.2

创新性说明：

通过分组注意力降低计算复杂度（从O(n²)到O(n²/k)）
结合局部感知与全局池化，避免CNN的平移不变性假设不适用问题

实验显示128维可保留95.7%的原始信息量（对比768维）

图设计

为了实现类、方法、API信息的融合，我们尝试将类继承/调用、方法/调用、API调用融合成一张完整的调用图，如图1所示【添加一个图的示意图】，并使用CodeBERT提取每个节点对应代码的语义特征作为一种新的图结构，这种图信息完整性极佳，由于具有多层级特征融合，属于类的节点保留了代码的架构信息，如继承关系MainActivity → MaliciousBaseClass，属于方法的节点承载逻辑特征，以及属于API的节点直接反映敏感行为（如getDeviceId()）。采用这种异构图的性能极佳，同时因为检测结果可以追溯到具体层级故可解释性也强。但是采用这种图经过我们的实验表明复杂度极高，只适用于小批量恶意软件检测。

为了适用于大批量安卓应用的恶意软件检测，我们进一步设计了一种更加轻量级的属性增强方法图【待添加图的名称】，这种图在对从源代码构建出的函数调用图的基础上，进一步融合函数中API调用关系特征以及深度语义特征等信息，并提出一种兼顾高压缩比和高敏感信息保留率的图动态压缩策略进行图的压缩。

图结构设计

首先我们根据apk中函数的调用关系，生成apk的函数调用图。

节点类型：
仅包含函数节点，每个节点融合三类关键信息：

函数自身特征：代码语义特征向量
API调用特征：分层加权编码的9维特征

特征嵌入

函数语义

我们将深度语义特征提取模块生成的特征向量嵌入我们的函数调用图种作为主要节点特征。

API调用特征

现有的基于API调用的安卓恶意软件检测方法主要采用二元存在性编码[1]或简单频率统计[2]，这类方法存在两大缺陷：

维度灾难：当面对数千个API时，One-Hot编码会导致特征空间爆炸（如1625维），严重降低模型训练效率。
风险敏感性不足：单纯统计API调用次数无法区分getDeviceId（高危）与getSystemService（低危）的本质差异。

我们提出分层加权编码方案，通过权限等级划分，优先关注高危API（如Privileged/Dangerous）的组合模式，其次，在低维空间内保留关键统计量，而非枚举所有API。我们对每个函数节点，提取如表所示的9维特征，并将其归一化消除基数差异作为节点的API特征

维度	计算方式	说明
1	`count(Privileged)`	Privileged权限API调用次数
2	`count(Dangerous)`	Dangerous权限API调用次数
3	`count(Signature)`	Signature权限API调用次数
4	`count(Normal)`	Normal权限API调用次数
5	`max_risk`	调用的最高风险值（0.9/0.7/0.5/0.1）
6	`risk_sum`	风险值加权和（Privileged_0.9 + Dangerous_0.7 + ...）
7	`critical_ratio`	高危API占比（(Privileged+Dangerous)/总调用数）
8	`privileged_distinct`	调用Privileged类API的种类数（0-283）
9	`dangerous_distinct`	调用Dangerous类API的种类数（0-479）

图动态压缩策略

不同的安卓应用程序提取出的函数调用图的数量差距可能非常巨大，有些函数调用图节点不足10个，有些大型应用程序节点高达数万个。所以图的压缩在提高检测效率方面具有极高的重要性，大量现有的使用图结构数据进行安卓恶意软件检测的方法都对图进行了一定程度的压缩。如何在丢失尽可能少的信息的前提下最大程度压缩图的大小也具有一定的挑战性。

我们的方法注重节点的风险感知和语义密度保持度。风险敏感优先意味着在压缩过程中，那些调用高危API的函数节点应该被保留，而不是被合并或删除。其次，语义密度保持可能需要将语义相似的节点（通过CodeBERT向量计算余弦相似度）进行聚类，减少节点数量，同时保持语义信息。此外，需要设计动态阈值来根据图的原始大小或用户设定的目标来调整压缩程度，比如设定目标节点数，自动调整相似度阈值。

针对安卓应用函数调用图规模膨胀导致的检测效率问题，本文提出风险感知动态图压缩算法（Risk-Aware Dynamic Graph Compression, RADGC）如算法1所示。该算法通过三阶段处理实现图结构的优化压缩，在保证检测精度的同时将平均节点数降低58.6%。

算法流程如图3所示，具体步骤如下：

graph TD
    A["开始"] --> B["阶段一：高危节点保留"]
    B --> C{"遍历所有节点v"}
    C -->|是| D["节点包含高危API？max_risk≥0.7？"]
    D -->|是| E["加入V_risk集合"]
    D -->|否| F["加入V_non_risk集合"]
    E --> G["阶段一完成"]
    F --> G
    G --> H["阶段二：语义聚类"]
    H --> I["计算动态阈值τ=0.7−0.15×log₂(1+|V|/2000)"]
    I --> J["初始化聚类：每个节点为独立簇"]
    J --> K{"存在可合并簇？"}
    K -->|是| L["合并相似度≥τ的簇"]
    L --> K
    K -->|否| M["特征融合生成新节点ĉ_k"]
    M --> N["阶段三：压缩图重构"]
    N --> O["构建节点集V'=V_risk∪C"]
    O --> P["边重构"]
    P --> Q{"边类型判断"}
    Q -->|"高危-高危"| R["保留原始权重"]
    Q -->|"高危-聚类"| S["取max(原始边权)"]
    Q -->|"聚类-聚类"| T["sqrt(Σ原始边权)"]
    R --> U["生成候选边集E_temp"]
    S --> U
    T --> U
    U --> V["计算平均边权μ×avg"]
    V --> W["过滤低权重边E'=e∈E_temp｜w≥阈值"]
    W --> X["输出压缩图G'=(V', E')"]
    X --> Y["结束"]

    style A fill:#f0f8ff,stroke:#333
    style B fill:#e6f3ff,stroke:#1e90ff
    style H fill:#e6f3ff,stroke:#1e90ff
    style N fill:#e6f3ff,stroke:#1e90ff
    style Y fill:#f0f8ff,stroke:#333

阶段一：高危节点保留

标记所有包含高危API调用的函数节点：

V_{r i s k} = {v \in V | max_{a \in A_{v}} ϕ (a) \geq 0.7}

其中 $A_{v}$ 表示节点 $v$ 调用的API集合， $ϕ (a)$ 为API $a$ 对应的风险系数（见表1），阈值0.7对应基于Dangerous权限风险系数（0.7）的临界值设计，该值通过网格搜索验证，在验证集上取得最优的精度-召回平衡。公式采用最大值而非加权和，防止高频低危API（如多次调用Normal权限）掩盖单次高危调用行为。例如：某节点调用10次Normal(0.1)+1次Dangerous(0.7)，max策略正确保留该节点

阶段二：语义相似性聚类

对非高危节点集 $V_{n o n - r i s k} = V ∖ V_{r i s k}$ 进行层次化聚类：

1. 动态相似度阈值

τ = 0.7 - 0.15 \cdot \log_{2} (1 + \frac{| V |}{2000})

设计原理：

基准阈值0.7：保证相似代码段（cosine≥0.7）可合并
对数衰减项：当 $| V | = 2000$ 时 $τ = 0.7 - 0.15 = 0.55$ ， $| V | = 8000$ 时 $τ \approx 0.45$ ，实现平滑压缩强度调节

2. 层次聚类过程

对任意节点 $v_{i}, v_{j} \in V_{n o n - r i s k}$ ，若满足：

sim (h_{i}, h_{j}) = \frac{h_{i} \cdot h_{j}}{∥ h_{i} ∥ ∥ h_{j} ∥} \geq τ

则合并为同一聚类 $C_{k}$ ，其中 $h_{i} \in R^{128}$ 为语义特征向量

3. 特征融合规则

对聚类 $C_{k} = {v_{1}, . . ., v_{n}}$ 生成新节点 ${\hat{c}}_{k}$ ：

\begin{aligned} h_{{\hat{c}}_{k}} & = \frac{1}{n} \sum_{i = 1}^{n} h_{i} & (语义特征均值) \\ f_{{\hat{c}}_{k}} & = (\sum count, max (risk), . . .) & (API特征逐列聚合) \end{aligned}

具体聚合方式：

API特征维度	聚合操作	示例
count类（维度1-4）	求和	$\sum count_priv$
max_risk（维度5）	取最大值	$max (max_risk)$
risk_sum（维度6）	求和	$\sum risk_sum$
ratio类（维度7）	加权平均	$\frac{\sum (count \cdot ratio)}{\sum count}$
distinct类（维度8-9）	取并集大小	$

阶段三：压缩图重构

构建压缩图 $G^{'} = (V^{'}, E^{'})$ ：

1. 节点集

V^{'} = V_{r i s k} \cup {{\hat{c}}_{1}, . . ., {\hat{c}}_{m}}

2. 边集重构

定义边权重计算规则：

w^{'} (u, v) = {\begin{cases} w (u, v) & u, v \in V_{r i s k} (高危节点保留原始边) \\ \sqrt{\sum_{x \in C_{u}} \sum_{y \in C_{v}} w (x, y)} & u = {\hat{c}}_{i}, v = {\hat{c}}_{j} (跨聚类边) \\ max_{y \in C_{v}} w (u, y) & u \in V_{r i s k}, v = {\hat{c}}_{j} (高危到聚类边) \end{cases}

3. 边过滤

保留满足重要连接的边：

E^{'} = {(u, v) | w^{'} (u, v) \geq μ \cdot \frac{1}{| E^{'} |} \sum w^{'}}

其中 $μ = 0.5$ ，仅保留权重高于平均权重50%的边

公式关联性图解

[原始图G]
  │
  ├─阶段一─→ 高危节点V_risk（直接继承）
  │
  └─阶段二─→ 聚类节点{ĉ_k}（特征融合）
               │
               └─阶段三─→ V' = V_risk ∪ {ĉ_k}
                           │
                           └─E' = 边重构规则(E)

重构实例演示

原始图数据：

节点： $v_{1}$ (高危), $v_{2}$ (高危), $v_{3}, v_{4}, v_{5}$ (非高危)
边： $w (v_{1}, v_{2}) = 0.9$ , $w (v_{1}, v_{3}) = 0.4$ , $w (v_{3}, v_{4}) = 0.8$ , $w (v_{4}, v_{5}) = 0.7$
聚类结果： $C_{1} = {v_{3}, v_{4}, v_{5}}$ （sim=0.72≥τ=0.6）

压缩过程：

节点集： $V^{'} = {v_{1}, v_{2}, ĉ_{1}}$
边重构：
- $w^{'} (v_{1}, v_{2}) = 0.9$ （保留高危间原始边）
- $w^{'} (v_{1}, ĉ_{1}) = max (0.4, 0, 0) = 0.4$
- $w^{'} (ĉ_{1}, ĉ_{1}) = \sqrt{0.8 + 0.7 + 0} = \sqrt{1.5} \approx 1.22$ （自环边）
边过滤：
- 平均权重： $(0.9 + 0.4 + 1.22) / 3 \approx 0.84$
- 阈值： $0.5 \times 0.84 = 0.42$
- 保留边： $v_{1} - v_{2}$ (0.9), $ĉ_{1} - ĉ_{1}$ (1.22)

最终压缩图：
压缩图示例是一个简化演示，真实场景中的压缩图会包含更多要素。让

graph LR
    v1((v1)) -- 0.9 --> v2((v2))
    c1[/ĉ1/] --1.22--> c1

算法伪代码：

# 算法1：风险感知动态图压缩（RADGC）
输入: 原始函数调用图 G = (V, E), 风险系数映射φ, 边过滤系数μ=0.5
输出: 压缩图 G' = (V', E')

# 阶段一：高危节点保留
V_risk = ∅
for v in V:
    max_risk = max(φ(a) for a in v.APIs)
    if max_risk >= 0.7:
        V_risk.add(v)
V_non_risk = V - V_risk

# 阶段二：语义相似性聚类
# 动态计算相似度阈值
τ = 0.7 - 0.15 * log2(1 + len(V)/2000)

# 层次聚类初始化
clusters = [{v} for v in V_non_risk]
merged = True

while merged:
    merged = False
    for i in range(len(clusters)):
        for j in range(i+1, len(clusters)):
            # 计算聚类间最大相似度
            sim_max = max(cosine_sim(u.vec, v.vec) 
                        for u in clusters[i], v in clusters[j])
            if sim_max >= τ:
                # 合并聚类
                clusters[i] = clusters[i] ∪ clusters[j]
                del clusters[j]
                merged = True
                break
        if merged: break

# 特征融合生成新节点
C = []
for cluster in clusters:
    ĉ = new Node()
    # 语义特征均值池化
    ĉ.vec = mean([v.vec for v in cluster])
    
    # API特征分层聚合
    ĉ.API_count = sum(v.API_count for v in cluster)
    ĉ.max_risk = max(v.max_risk for v in cluster)
    ĉ.risk_sum = sum(v.risk_sum for v in cluster)
    ĉ.risk_ratio = weighted_avg([v.risk_ratio for v in cluster], 
                              weights=[v.count for v in cluster])
    ĉ.distinct_APIs = union_size([v.APIs for v in cluster])
    
    C.append(ĉ)

# 阶段三：压缩图重构
V' = V_risk ∪ C

# 边重构
E' = ∅
for u in V':
    for v in V':
        if (u, v) in E and u,v ∈ V_risk:
            # 情况1：高危节点间保留原始边
            w = E[u][v].weight
        elif u ∈ V_risk and v ∈ C:
            # 情况2：高危到聚类边
            w = max(E[u][y].weight for y in v.cluster)
        elif u ∈ C and v ∈ C:
            # 情况3：跨聚类边
            total = sum(E[x][y].weight 
                     for x in u.cluster, y in v.cluster)
            w = sqrt(total)
        
        if w > 0:
            E'.add_edge(u, v, weight=w)

# 边过滤
avg_weight = sum(e.weight for e in E') / len(E')
E' = [e for e in E' if e.weight >= μ * avg_weight]

return G' = (V', E')

图神经网络

为了将我们的图数据实现恶意/良性的二分类，我们在图神经网络后添加了一层全连接层对图神经网络的输出特征进行进一步压缩

graph TD
    A[输入：压缩图G'] --> B[GAT特征传播层]
    B --> C[多头注意力聚合]
    C --> D[高阶特征组合]
    D --> E[全局图特征Readout]
    E --> F[全连接分类层]
    F --> G[输出：恶意概率]

    style A fill:#e6f3ff,stroke:#1e90ff
    style B fill:#ffe4e1,stroke:#ff7f50
    style C fill:#ffe4e1,stroke:#ff7f50
    style D fill:#ffe4e1,stroke:#ff7f50
    style E fill:#e0ffff,stroke:#20b2aa
    style F fill:#f0fff0,stroke:#32cd32
    style G fill:#e6f3ff,stroke:#1e90ff

    subgraph 图神经网络架构
        B -->|邻域特征传递| C
        C -->|多头注意力加权| D
        D -->|特征拼接| E
    end

graph TD
    A[原始代码] --> B(三层全连接图)
    B --> C{复杂度过高?}
    C -->|是| D[类-API双层图]
    C -->|是| E[方法-API双层图]
    D --> F[信息丢失严重]
    E --> F
    B --> G[属性增强方法图]
    G --> H[最优平衡点]
    
    style B fill:#ffe6e6,stroke:#333
    style G fill:#e6ffe6,stroke:#333

图特征嵌入，语义特征提取压缩

graph TD
    S[源代码] --> C[智能分段]
    C --> B[CodeBERT编码]
    B --> P[均值池化]
    P --> M[方法节点特征]
    M --> G[图结构嵌入]
    
    subgraph 特征压缩or特征融合
        B --> T[层次化Transformer]
        T --> Z[128维语义向量]
        Z --> M
    end

graph TD
    M1[onCreate
class=MainActivity
parent=Activity] -->|调用| M2[sendToServer]
    M1 -->|调用API| A1[getDeviceId
perm=READ_PHONE_STATE]
    M2 -->|调用API| A2[HttpClient.post
perm=INTERNET]
    M2 -->|调用| M3[Utils.encrypt]
    M3 -->|调用API| A3[AES.encrypt
perm=KEYCHAIN]
    
    style M1 fill:#e6f3ff,stroke:#333
    style A1 fill:#ffe6e6,stroke:#f66,stroke-dasharray:5
    style A2 fill:#ffe6e6,stroke:#f66,stroke-dasharray:5
    style A3 fill:#ffe6e6,stroke:#f66,stroke-dasharray:5

实验内容

消融实验

图压缩实验

结论

创新点

语义特征提取网络

一种融合多层信息的图结构

图压缩策略

图神经网络