Page 128 - 《软件学报》2021年第7期

2046 Journal of Software 软件学报 Vol.32, No.7, July 2021

Fig.5 Transformation rules
图 5 转换规则
_
Lock Unlock、 规则展现了 GUARD 是如何分析锁的.当 thread lock 函数被调用时,GUARD 将一个标签添
加至锁集 L l 中,对应地,当 thread unlock 函数被调用时,它将相应锁集中的锁去除.这两条转换规则模拟了加锁
_
和去锁的语义.
CallingContext 规则描述了 GUARD 实现上下文敏感的核心策略.对于 NL 中的所有标签,按调用点 ID 将每
个标签中的 CS 进行拼接.注意,每个 CS 的 ID 是拼接而成的,因此 GUARD 可以从一个 CS 中提取出一个调用链.
按照这种方式,GUARD 能够通过分析 CS 中的各 ID 识别出不同的调用上下文.
从图 5 可以看出,GUARD 将 thread _ join 或同步操作( thread wait 和 thread notify )分别存储在  和
_
_
j wn
中,而不是清除相应的线程标签.这么做的原因在于,被清除的标签可能会隐含其他函数的 MHP 关系,清除线程
标签可能会带来漏报.
3.1.2 MHP 分析
在定义线程标签和转换规则后,GUARD 根据转换规则通过自底向上和自顶向下分析的方法进行 MHP 分
析.自底向上分析会为每个节点计算线程标签,自顶向下分析将调用者的线程标签传递给它们的被调用者.
在自底向上分析的过程中,GUARD 以逆拓扑序分析函数.在此阶段,GUARD 根据图 5 所示的转换规则创建
并更新线程标签.在此阶段后,GUARD 可以通过路径查询两条指令的 MHP 关系.但这一阶段没有路径信息
GUARD,无法高效地查询 MHP 关系,这是因为,GUARD 需要从两条指令所能到达的路径中提取出所有标签.为
了不失一般性,GUARD 的目标是,无论是否有路径信息都能查询 MHP 关系,因为有些 MHP 关系的查询有路径
信息而有些没有,因此 GUARD 执行第 2 阶段的自顶向下分析.
在自顶向下分析的过程中,GUARD 以函数的拓扑序分析函数标签.它将调用者的线程标签传递给被调用
者,从而每个函数都能知晓其全局线程标签.通过这种方式,GUARD 总结出了全局线程标签,并且不需要路径信
息就能高效地查询两条指令的 MHP 关系.
3.2 基于Source-Sink的检测框架
该框架提供了两种基础分析:一种需求驱动的、路径、上下文敏感的值流分析和一个基于 Source-Sink 的
检测框架.值流分析提供了数据依赖信息,以此来识别线程操作的标识.例如,对 thread _ join (tid tid 必须与被执
),
_
_
行 join 操作的线程的标识相同.类似地, thread notify 或 thread lock 的线程标识也应该通过值流分析传递给对
应的 thread wait 或 thread unlock .GUARD 借助别名分析的方式解决这个问题,GUARD 首先会进行完备但不
_
_