之间的耦合程度。
(4)数据依赖：用与度量程序控制流相似的方法，数据依赖 也 能 被 度 量 。 在 流 程 图 中 ，用 结 点 来 阐 明 谓 词 子 句 和 变 量 定
义。Bieman 和 Debnath 建议用广义程序图(generalised program graph，GPG) 的 形 式 来 表 示 。
1 程序代码相似度度量技术
早在 20 世纪 70 年代初，就有学者研究阻止大规模拷贝程 序 的 技 术 和 软 件 ，出 现 了 一 批 比 较 典 型 的 程 序 源 代 码 剽 窃 检 测系统[1-4]。Halstead 提出的软件科学度量方法是最早和最典型 的属性计数法。Halstead 度量方法以程序中出现的操作符和操 作 数 为 计 数 对 象 ，以 它 们 的 出 现 次 数 作 为 计 数 目 标 来 计 算 程 序容量和工作量。Rottenstone 在 1976 年首次将 Halstead 的软 件科学度量方法投入应用，实现了第一个针对于 Fortran 代码 的 剽 窃 检 测 系 统 。 但 是 ，单 纯 的 属 性 计 数 法 抛 弃 了 太 多 的 程 序结构信息，导致检测结果的错误率太高。Verso 和 Wise 在
×
1, 2 = 1
2
=1
(3)
2
2
1.2 结 构 度 量 技 术
=1
=1
采 用 结 构 度 量 技 术 的 剽 窃 检 测 系 统 中 ，通 过 对 程 序 的 内
部 结 构 进 行 分 析 比 较 来 判 断 两 段 程 序 代 码 的 相 似 性 。结 构 度
量 技 术 中 使 用 的 相 似 度 度 量 方 法 主 要 有 ：点 阵 图 法 、Levensh-
路 径 数 目 。该 方 法 首 先 将 程 序 代 码 转 换 为 一 个 带 有 惟 一 入 口
和 出 口 结 点 的 控 制 流 图 。 这 种 方 法 具 有 语 言 依 赖 性 ，这 意 味
着 在 创 建 控 制 流 图 前 ，必 须 理 解 编 写 代 码 的 语 言 的 语 法 和 语
Study on similarity measurement of program code
DENG Ai-ping (Department of Computer Science, Hunan Institute of Humanitles, Science and Technology, Loudi 417000, China)
tein 距离、最长公共子序列法、最长公共子串法。
1.2.1 点 阵 图 (dotplot)法 点阵图 [5] 是一种视觉展示两个代码块 (或任意文本) 之间
字 符 串 匹 配 模 式 的 技 术 。 重 要 的 是 ，点 阵 图 不 是 一 种 特 定 的
语 言 ，因 此 它 不 要 求 了 解 被 比 较 的 代 码 的 语 法 和 语 义 。 这 一
1996 年指出，对于仅仅使用属性计数法的检测算法，增加向量 维数并不能改善错误率。改进属性计数法的措施就是加入程 序的结构信息，结合结构度量来检测剽窃。McCabe 提出的圈 复杂度方法是一种典型的结构度量法。它通过计算执行路径 的数量来衡量一个程序中的控制流。圈复杂度只给出了程序 的 一 个 结 构 特 征 即 控 制 流 ，往 往 需 要 与 其 它 特 征 结 合 使 用 ，因 此常作为属性计数法中的一个度量指标。其它的结构度量法 还有分析控制结构、计算代码嵌套深度、分析数据依赖关系等。 在实际应用中，很多代码剽窃检测系统将两种度量方法相结 合。Donaldson et al.开发的 ACCUSE 系统结合属性计数法和结 构度量法来实现对 Fortran 程序代码的剽窃检测。最近提出的 系统大都是通过对表达源程序结构的字符串进行比较来达到 剽窃检测的目的，如：Plague, JPlag, SIM, MOSS,YAP 系列等。
程 是 ：首 先 ，选 择 两 个 程 序 并 将 其 处 理 为 标 记 序 列 ；然 后 连 接
这 两 个 序 列 ；最 后 对 生 成 的 序 列 进 行 自 我 比 较 。
第 29 卷 第 17 期 Vol. 29 No. 17
计算机工程与设计
Computer Engineering and Design
2008 年 9 月 Sept. 2008
程序代码相似度度量算法研究
邓爱萍 (湖南人文科技学院 计算机科学技术系，湖南 娄底 417000)
摘 要：代 码剽窃是程序设 计课程中经常 出现的一种作弊 行为，检测剽窃的源代 码、验 证学生程序作业 的原创性在教 学中 很重 要。程序代码的 相似度度量是 剽窃检测的关键 技术。通过对 现有程序代码相 似度度量技术进 行研究后，基于 Karp-Rabin 和最 长公共子串算法 思想，提出了一 种改进的源代码 相似度度量算 法，即串的散列值 匹配算法。 关键 词：源代码; 相 似度度量; 剽窃 检测; 串匹配算 法; 散列值匹 配 中图 法分类号：TP311.52 文献标 识码：A 文 章编号：1000-7024 (2008) 17-4636-04
收稿日期：2007-09-16 E-mail：ld_dengaiping@ 作者简介：邓爱萍 (1977－)，女，湖南涟源人，硕士，讲师，研究方向为计算机辅助教育技术。
－ 4636 －
的软件度量指标，以便于将程序映射到一个 n 维的笛卡尔空 间 ，然 后 利 用 向 量 空 间 模 型 来 度 量 程 序 代 码 相 似 性 。
(5)嵌套深度：这是一个简单的度量标准，通过赋给每个代 码 行 一 个 深 度 值 ，返 回 一 个 程 序 的 平 均 嵌 套 深 度 。 平 均 值 是
由这些深度值的总和除以程序中语句的个数计算而来。
(6) 控 制 结 构 ：给 出 现 在 程 序 中 的 每 一 种 类 型 的 控 制 结 构 赋予一个权值，例如给一个 if...then 结构赋予权值 3，所有权值 的总和常用来表示一个程序的复杂度。
式中： = 汇量。
= log2 1+ 2——程序长度； =
(1) 1+ 2 ——程序所用的词
(2) 控制流：控制流常用 McCabe 提出的圈复杂度 (cyclomatic complexity)来度量。圈复杂度是一种为程序逻辑复杂性 提 供 定 量 测 度 的 软 件 度 量 方 法 ，用 于 计 算 程 序 的 基 本 的 独 立
综 上 所 述 ，应 用 于 程 序 代 码 剽 窃 检 测 系 统 中 的 代 码 相 似 度 度 量 方 法 可 分 成 两 类 ：属 性 计 数 技 术 和 结 构 度 量 技 术 。 1.1 属 性 计 数 技 术
在剽窃检测算法的发展过程中，大多数工作集中在 Halstead 的软件科学理论。这些基于软件科学度量的算法是从程 序中提取出数个软件度量特征，计算每一个程序的 n 个不同
义 。 在 程 序 控 制 流 程 图 中 ，节 点 表 示 程 序 中 一 个 顺 序 代 码 单
元，边表示程序中产生的分枝。一个有 条边和 个节点的控
制流图 G，其圈复杂度定义为
= +2
(2)
其中： = 控制流图中的模块数。 (3) 结 构 ：这 个 度 量 标 准 考 虑 到 使 用 一 些 指 标 去 阐 明 模 块
另外，Faith 和 Robinson 提出使用 24 个分量来评估代码的 相似程度，前 10 个是主要针对初学者的低级的剽窃，其它的 用于有经验的剽窃；Jankowitz 方法通过对代码中的主程序和 方 法 进 行 语 法 分 析 ，得 到 静 态 执 行 树 ，用 于 对 代 码 的 分 析 等 。
点使得点阵图法具有很大的灵活性。
点阵图的主要优势是它依赖于人的视觉系统去检测相似
模 式 。然 而 ，简 单 的 用 人 眼 去 揭 露 剽 窃 ，如 何 量 化 每 个 比 较 结
果 的 问 题 成 为 了 点 阵 图 的 主 要 缺 点 。它 意 味 着 解 释 一 个 人 复
制 了 多 少 别 人 的 代 码 将 不 能 由 值 来 表 示 。点 阵 图 法 的 操 作 过
Abstract：Code plagiarism is one kind of cheat behavior, which appears frequently in the programming curriculum. Detection of source code plagiarism is important to verify the originality of students’ project works. The code similarity measurement is the key technology in the plagiarizing detection. The similarity measurement of program code is studied first, then the string’s hash value matching arithmetic which based on Karp-Rabin and longest common substring algorithm is provided, and the results show the improved arithmetic is effective. Key words：source code; similarity measure; plagiarism detection; string matching arithmetic; hash value matching
1.1.1 常 用 的 属 性 计 数 法度 量 指 标 在属性计数技术中，有以下 6 个常用的代码相似度度量
指标，被描述为一个“6 元组”向量。 (1)容量：容量被认为是任何算法实现的大小的反映，常使