Page 280 - 《软件学报》2026年第5期
P. 280

刘书宁 等: 基于代码变更语义分析的缺陷隔离方法                                                        2159


                                                                                    D  描述了子提交之间的依
                 c i  必须在提交  c j  之后, 即所有的提交都在其依赖项提交之后进行. 因此, 依赖关系集合
                 赖顺序, 构成了一个有向无环图. 在本文中, 选择            Kahn  算法  [32] 用于对由子提交集合   C  和依赖关系集合    D 构成的有
                 向无环图进行拓扑排序, 从而生成一个满足依赖关系的线性序列. Kahn                    算法基于贪心思想, 首先, 对于图中的每个
                 节点  (子提交  c i ), 计算其入度  (即依赖于其他节点的数量), 这表示每个子提交被其他子提交依赖的程度, 将所有入
                 度为  0  的节点放入一个队列中, 这些节点表示没有依赖关系的子提交, 可以作为排序的起点. 反复从队列中取出入
                 度为  0  的节点, 将其加入最终的排序结果. 同时, 移除该节点及其出边                (即该节点对其他节点的依赖关系). 对于每
                 条出边所指向的节点        (即依赖当前节点的子提交), 将其入度减           1. 如果某个节点的入度减少至         0, 则将其加入队列.
                 重复上述过程, 直到队列为空. 通过该算法能够得到满足所有依赖关系的线性有序子提交序列                             C = {c 1 ,c 2 ,...,c n }, 其
                                                         (   )
                 中每个子提交     c i  的提交顺序都满足   D 中的依赖关系      c i ,c j , 即当  c i 7→ c j  时   c i  出现在  c j  之后.
                    该序列确保了每个子提交按照正确的提交顺序进行排列, 避免了依赖冲突, 保证了提交的依赖关系得到严格
                 遵循. 这不仅为后续的缺陷隔离提供了清晰的操作顺序, 还有效减少了由于提交顺序错误导致的依赖问题, 确保后
                 续操作不受先前未处理变更的干扰, 便于在后续流程中更加高效地识别和隔离缺陷.
                  2.4.2    缺陷变更隔离

                    给定拆解后的提交集合         C  中, DISAC  需要找到实际引发缺陷的提交        c bug ∈ C, 并进行隔离. 与  DD  不同, DISAC
                                                                                                c bug  的过程
                 已经根据集合之间的依赖关系           D  将提交集合   C  建模为具有线性关系的提交序列进行搜索. 因此, 查找
                 变为在线性区间      [c 1 ,c n ] 中寻找真实的缺陷引入提交   c bug , 其中  c 1  是最早的提交,  c n  是最新的提交.
                    DISAC  在线性区间上使用二分查找算法进行搜索. 函数               F (c i ) 用于表示提交  c i  对代码的测试结果, 返回值是
                 通过  (PASS) 或失败  (FAIL), 目标是找到第   1  个导致测试结果从     PASS  转变为  FAIL  的提交  c bug . 在每一步, 选择当
                                        i+ j
                                       ⌊   ⌋
                 前区间的中点提交      c m , 即  m =  , 其中   i 和   j 是当前搜索区间的左右边界索引, 测试该中点提交         c m  的结果  F (c m ).
                                         2
                 如果  F (c m ) = FAIL∧ F (c m−1 ) = PASS, 则  c m  是引入缺陷的提交, 即  c bug = c , 停止搜索; 如果  F (c m ) = PASS, 则意味
                                                                         m
                                                     [    ]
                 着缺陷出现在     c m  之后, 因此将搜索区间缩小为       c m+1 ,c j ; 如果  F (c m ) = FAIL∧ F (c m−1 ) = FAIL, 则意味着缺陷出现在
                 c m  之前, 将搜索区间缩小为     [c i ,c m−1 ]. 根据上述步骤缩小搜索区间, 直到区间内只有一个提交或找到符合               F (c i ) =
                 FAIL∧ F (c i−1 ) = PASS, 则可以确定  c bug = c .
                                                 i
                    由于  DISAC  已经根据提交之间的依赖关系          D  将  C  建模为线性区间, 因此可以确保在查找过程中不会违反提
                                                                                                     c j  的
                 交之间的依赖顺序. 例如, 如果        c i 7→ c j  (即   c i  依赖于  ), 则在二分查找过程中, 任何包含  c i  的区间必须在包含
                                                        c j
                 区间之前. 这保证了查找过程中的逻辑一致性.
                                  c bug  后, DISAC     ∗         ∗      c i  及其前序依赖的提交, 即隔离到的与缺陷
                    在找到缺陷提交                  选择子集    C ⊆ C, 其中  C  中包含
                 相关的所有提交.
                  3   实验设计

                  3.1   研究问题

                    为了评估本文提出的基于代码变更语义分析的缺陷隔离方法                      DISAC  的有效性, 我们研究了以下几个问题.
                    ● RQ1: 与增量调试方法相比, DISAC      方法在缺陷隔离任务中的性能如何?
                    ● RQ2: DISAC  方法是否能够增强现有增量调试技术的性能?
                    ● RQ3: 本文提出的    DISAC  方法中不同组成部分如何影响缺陷隔离总体方法的性能?
                    ● RQ4: DISAC  方法与增量调试方法在辅助缺陷根因确定任务中的作用和价值如何?
                  3.2   实验数据
                    为了评估     DISAC  方法在缺陷隔离任务上的性能, 我们使用了               Defects4J [20] 和回归缺陷  [21] 两个数据集.
                 Defects4J 是一个广泛使用的经过人工验证的缺陷数据集, 它由               835  个从真实  Java 项目中收集到的缺陷及其修复
                 组成. 对于每个缺陷, 它提供了原始缺陷版本             ( V obug ) 和缺陷修正版本  ( V ofix ), 它们之间的代码差异包含了与缺陷无
   275   276   277   278   279   280   281   282   283   284   285