基于行为motifs的多线程程序抄袭检测方法

田振洲 王宁宁 王 清 高 聪 刘 烃 郑庆华

1(西安邮电大学计算机学院 西安 710121)2(陕西省网络数据分析与智能处理重点实验室(西安邮电大学) 西安 710121)3(西安交通大学电信学院 西安 710049)

开源软件社区以及社交编程网站如GitHub，CodeShare等的蓬勃发展，带来了软件工业的繁荣.然而，伴随而来的软件抄袭问题亦日趋严重，滥用他人代码的情况屡见不鲜.2009年，全球最大软件商微软的MSN(Microsoft service network)聚酷被Plurk指责抄袭了其80%的代码；同年，国内“绿坝”被曝抄袭CyberSitter的大量代码；2015年，APICloud涉嫌抄袭数字天堂的DCloud，鉴定报告证实其不仅直接挪用了DCloud的dll文件，还抄袭了DCloud的真机运行等功能的大量源码.2018年8月的“红芯风波”更是闹得沸沸扬扬，宣称自主研发国产内核的红芯浏览器被爆仅仅是换壳谷歌Chrome.近年来，移动应用的抄袭更是愈演愈烈，如手游《巨龙之怒》抄袭蓝港代码的诉讼案件、iOS平台PP助手抄袭事件，以及普遍存在的重打包的安卓应用这类新形式的抄袭[1].

软件胎记[2-3](software birthmark)是从软件代码或其执行过程中抽取出的一些不易改变且可唯一地对软件身份进行标识的特征.胎记技术通过衡量胎记相似性判断软件间可能存在的抄袭，是实现软件抄袭检测的一种行之有效的手段.其中，动态胎记技术[4-6]具体地执行软件并从捕获的执行轨迹中构建胎记，因能更精准地刻画软件的行为和语义，比静态胎记技术往往表现出更优秀的抗混淆能力和检测效果.然而，线程交织的不确定性使得多线程程序的行为也表现出很大的不确定性，这给动态胎记技术带来不可忽视的影响[7-8].例如，在相同输入下对同一个多线程程序执行多次，从这些执行轨迹中单独构建的动态胎记往往会体现出很大的不同，甚至会判定同一个程序与其自身不存在抄袭关系[9].

针对这个问题，本文方法的基本思路是：通过动态监控捕获一个多线程程序在同一输入下的多条执行轨迹，识别出轨迹间的相似部分，并从中抽象出具有一定差异容忍能力且频繁出现的行为模式(称之为行为motifs)，建模该多线程程序的行为，以期降低线程交织不确定性的影响.

本文的主要贡献有3方面:

1) 提出了一种新的多线程程序行为表示方法及提取方法，即利用抽象自多线程程序执行轨迹间相似部分的行为motifs，建模多线程程序的行为；这些行为motifs具体是通过对执行轨迹进行修剪、精确匹配以及扩展和抽象得到的.

2) 在行为motifs基础上，提出了一种新的线程感知胎记——motifs胎记；参照软件胎记技术的基本流程，设计了基于motifs胎记的多线程程序抄袭检测方法，并实现了原型系统MotifPD.

3) 在一个公开的软件抄袭样本集上验证了方法的有效性.实验表明，motifs胎记是一种可靠的线程感知胎记；MotifPD不仅可有效对抗主流的代码混淆技术，检测性能也优于现有的2种多线程程序抄袭检测方法：线程相关系统调用胎记(thread-related system call birthmark, TreSB)和线程切片胎记(thread-oblivious birthmark, TOB).

1 相关工作

本文工作围绕源码缺失情境下多线程程序的抄袭检测展开，提出的方法属于软件动态胎记技术的范畴.2004年，Tamada等人[2]首次提出了软件胎记的概念，开启了基于软件胎记的抄袭检测研究的先河，随后涌现出一系列优秀的静态[10-11]和动态[5-6,12]的软件胎记技术，具体可以查阅综述性文献[4]中对现有的软件抄袭检测方法，以及动静态软件胎记技术的系统介绍.

通过对程序执行过程进行分析抽取动态胎记,在对抗代码混淆方面表现出更大的优势，获得了研究者的青睐[4,8].然而，线程交织的不确定性使动态胎记技术在检测多线程程序抄袭方面的性能大打折扣.

Tian等人[7]首次提出了多线程程序的抄袭检测问题，引入了线程感知胎记的概念；并提出了TOB框架[9]，基于“切片-合并”的基本思想，扩展传统动态胎记以支持多线程程序的抄袭检测.他们利用TOB框架改良了3种经典的动态胎记：动态关键指令序列胎记(dynamic key instruction sequence birthmark, DYKIS)[5]、系统调用短序列胎记(system call short sequence birthmark, SCSSB)[13]、JBirth[14]进行了改良；实验结果表明，原胎记经改良后均可提升检测多线程程序抄袭的能力.然而，该项工作的基本假设“每个线程内发生的事件相对稳定”并不总是满足，线程间的交互和相互影响可能会导致每个线程内发生的事件产生变化.此外，通过线程切片并为每个线程单独构建胎记确实很大程度上可以减小交织的影响，但也使得胎记难以捕捉程序的整体行为，在分析线程间交互特别复杂的程序时难免会产生一定的漏报.

后来，Tian等人[15]又基于线程相关的系统调用，提出了一种新的线程感知胎记TreSB，其利用对线程交织实施影响和控制的线程相关系统调用，建模多线程程序交互过程体现出的行为特性.该方法在通用性方面不及TOB，其仅是针对多线程程序设计的具体线程感知胎记方法；因其主要利用了与线程操作相关的特征，故只能用于多线程程序的抄袭检测，且在线程交互较少的情况下并不适用.

2 motifs提取

传统动态胎记技术不适用于检测多线程程序抄袭的根本原因在于，线程交织的不确定性最终引起程序执行轨迹的变化，而从中构建动态胎记时它们对这些变化的容忍不足.因而，保证方法有效性的关键在于，从多变的执行轨迹中提取的特征须具备一定的差异容忍能力，以降低线程交织不确定性的影响.

现有的2种线程感知胎记方法TOB和TreSB，无论是采用“切片-合并”还是“利用特定元素(即线程相关系统调用)”的思想，均是从一条执行轨迹中抽取不易被线程交织干扰的特征.在DNA序列分析领域，motif(模体，也称基序.本文中当指代单个模体或修饰模体识别技术时用单数形式motif，其他情况下均用其复数形式motifs)识别从一组DNA序列中探测共有的序列模式，这组DNA序列往往比较相似，但因为变异的存在不会完全一致；同时，识别出来的motifs往往不会原样出现在所有序列中.对于多线程程序而言，多数情况下同一输入意味着同一程序功能的执行，同时并非所有的程序部分都会涉及交织，因而其在同一输入下的多条执行轨迹往往比较相似.受到DNA序列分析中motif识别的启发，本文尝试从多线程程序在同一输入下的多条相似的执行轨迹中识别行为motifs(定义1)，并用其建模该多线程程序的行为.

定义1.多线程程序的行为motifs.给定多线程程序P在同一输入I下的多条执行轨迹，设计算法α从中提取出一系列模式，这些模式捕捉了存在差异的执行轨迹间的相似部分，且算法α提供抽象策略保证提取的模式具备一定的差异容忍能力，按照这种方式提取的模式，称作多线程程序的行为motifs，也称多线程程序的行为模式.

图1描述了提取motifs的基本流程.具体地，以程序的同一输入下多次运行捕获的多条执行轨迹为输入，经过轨迹修剪、gram匹配、扩展抽象3个阶段，提取出行为motifs.

Fig. 1 Basic process of extracting motifs
图1 motifs提取基本流程

2.1 轨迹修剪

系统调用序列刻画了软件与操作系统的交互过程，被广泛用于建模程序行为.同时，作为操作系统的最小功能单元，系统调用是用户态应用程序请求操作系统内核服务的唯一手段，较难被删除和篡改，因而诸多胎记技术如SCSSB[13]，SCDG(system call dependency graph birthmark)[16]，TOB[9]，TreSB[15]等均利用系统调用构建胎记以提升对抗代码混淆[17]的能力.本文的执行轨迹也是指由系统调用构成的序列，通过动态插桩监控程序执行得到.

原始的执行轨迹并不适用于直接提取motifs.首先，失败的系统调用不能正确地反映程序行为[11,13]，比如程序中的打开文件操作，可能会出现打开失败的情况，相应的系统调用open会被执行多次，失败的那些将被视作噪声过滤掉.其次，部分系统调用具有先天的随机性，如系统调用futex提供了一种方式使线程保持阻塞直到满足特定的条件，且只有当预计阻塞时间较长时才会被调用，因而其出现次数在不同次执行时体现出固有的随机性，应当被作为噪声过滤掉.另一类是负责内存管理的系统调用，如mmap和brk等.前者在涉及到特别大块的内存分配时才被调用，后者则依据实际需要调整堆尺寸的大小.一般来说，malloc函数被调用时会攫取大块的内存空间，然后依据实际需要将其分割成较小的内存块，这就导致并非每次malloc都会有对应的系统调用被执行.因而，所有负责内存管理的系统调用也被视作噪声过滤掉.

2.2 gram匹配

motifs抽象自多条执行轨迹的相似部分，对此算法首先识别执行轨迹间所有的精确匹配区间，然后以它们为基础进行双向的扩展和抽象.

对于精确匹配区间的识别，本文算法目前是在计算k-gram[18]基础上经过搜索和严格匹配得到，故识别出来的匹配区间都是固定长度的，长度均为k.

假定s=(e1,e2,…,en)为多线程程序P在某输入下某次运行时捕获且经过了修剪的执行轨迹.

首先，利用k-gram算法将其切分成一系列长度为k的gram：grams(s,k)={gi|gi=(ei,ei+1,…,ei+k-1)}，1≤i≤n-k+1.

然后，∀gi∈grams(s,k)，在其他执行轨迹中查找所有与之精确匹配的子序列，这些子序列的起止范围就定义了gi的所有精确匹配区间.

例1.给定2条修剪过的执行轨迹s=ABCDE和t=ABCFDMABCFE,当k=2时，对于s中的gram BC，t中有2处与其匹配，即BC在t中的精确匹配区间为[2,3]和[7,8].

2.3 扩展和抽象

对gram及其精确匹配区间进行进一步的扩展和抽象，以对抗线程交织不确定性引入的差异.进行扩展时，gram及其精确匹配分别以自身为中心，以步长为1在各自的执行轨迹上双向交替进行.

例1中的gram BC经3轮扩展后变为ABCDE，其精确匹配区间扩展后对应的匹配序列分别为ABCFD和ABCFE.显然，扩展引入了非精确匹配关系，即每次扩展均可能使gram与其匹配区间对应的序列不再完全一致.

对此，对扩展后的gram及其非精确匹配，利用Smith-Waterman算法[19]求取二者匹配度最高的子序列.Smith-Waterman算法基于2序列中元素间的相似性计算1个得分矩阵，然后从矩阵中得分最高元素开始回溯求得最佳匹配.得分矩阵的计算依赖于匹配得分、失配得分以及插入或删除引入的空位罚分.

具体地，得分矩阵计算为

(1)

其中，c[i,j]为矩阵中第i行、j列的元素.sc为匹配或失配得分，2系统调用相同时为匹配，sc取正值；否则为失配，sc取负值.gap为空位罚分，取负值，表示对采取删除或插入操作的处罚.

例2.扩展得到的非精确匹配对ABCDE和ABCFD，经Smith-Waterman比对，可得最佳匹配ABC-D和ABCFD，其中“-”表示插入空位.对另一个非精确匹配对ABCDE和ABCFE，Smith-Waterman识别出ABCDE和ABCFE为最佳匹配.

最后，对Smith-Waterman识别的匹配序列进行抽象.具体地，将匹配序列中对应位置不一致的元素全部用“-”替代，并将生成的短序列记作一个行为motif.比如，从例2的匹配对ABC-D和ABCFD中将抽象出行为motif ABC-D；从另一匹配对ABCDE和ABCFE中可抽象ABC-E.利用“-”替代不一致的元素，使得提取的行为motifs可以容忍执行轨迹中的细微差异，从而降低线程交织不确定性的影响.

算法1描述了从2条执行轨迹中提取motifs的完整过程.

算法1.行为motifs提取算法.

输入：修剪过的执行轨迹s和t、k-gram的参数k、迭代终止阈值γ；

输出：motifs及其频数构成的键值对集合M.

①M←∅；

② 利用k-gram切分s为短序列集grams(s,k)；

③ forg∈grams(s,k) do

④E←findExactMatch(g,t)；

⑤ forr∈EMdo

⑥d←1；*扩展方向标记*

⑦g′←g,canExpand←TRUE；

len(t)-1 then

⑨canExpand←FALSE；

⑩ end if

len(t)-1 then

算法1中，行④中函数findExactMatch返回指定gram在另一条轨迹中的所有精确匹配区间，行⑧～⑩以及～判断是否可以继续扩展，行～实现沿轨迹指定方向的扩展，行中smith-Waterman函数比对扩展后的非精确匹配对，行中函数abstract从比对识别的最佳匹配序列中抽象出motif,行～更新M中的键值对.另外，对每对精确匹配迭代地进行扩展、比对和抽象时，算法1中行～会按照式(2)计算惩罚因子pf，当pf≥γ时，提前终止迭代，以提高motifs提取的效率.

pf=len(η)len(ζ)，

(2)

其中，len(η)和len(ζ)分别表示扩展得到的非精确匹配序列以及提取出来的motif的长度.

算法1的时间复杂度为O(n3)，其中n为经过修剪的执行轨迹的长度，最坏情形发生在执行轨迹s和t完全一致，且每条执行轨迹中均只包含重复单一元素的情况下.在实际情况下，程序的执行轨迹往往由一系列不同的系统调用组成，同时多线程程序在同一输入下的执行轨迹尽管比较相似，但一般不会完全一致，因而最坏情况基本不会发生.

算法1中最耗时的部分在于扩展-比对-抽象的操作，该操作的迭代次数越多时间开销越大.具体地，该操作的迭代次数取决于2个参数，一是惩罚因子的阈值γ，该阈值越大迭代终止条件越不容易满足，迭代次数越多.本文认为γ=2是一个合理的选择，即当扩展后的非精确匹配对的长度为从中提取出的motif长度的2倍以上时，认为继续扩展的意义不大而终止迭代，因为继续迭代提取出的motifs有极大可能会与之前一致.k值是另外一个影响迭代次数的因子，因为扩展-比对-抽象操作是在精确匹配对基础上展开的，而k值决定了精确匹配对的数量.k值越小，长度为k的子序列完全匹配的可能性就越大，即精确匹配对数量越多，导致总的迭代次数越多，时间开销越大.当然，可以通过增大k值或减小γ值来加速迭代的终止，但可能会导致某些有代表性的motifs提取不出来，即会降低motifs的多样性.本文4.4节具体分析了k值对方法的检测效果和效率的影响.

3 基于motifs的软件抄袭检测

迭代利用算法1处理多线程程序在同一输入下的执行轨迹集，基于提取的行为motifs构建motifs胎记，并通过衡量motifs胎记的相似性，实现多线程程序间潜在抄袭的检测.

3.1 motifs胎记

3.2 胎记相似性计算

motifs胎记是键值对集合的形式，与线程感知胎记TreSB和TOB一样，在余弦相似度基础上引入参数θ，以将motifs的频数相似性考虑进来.

首先，计算二者键集合的并集，有：

其中，

最终，2个motifs胎记的相似性为

3.3 抄袭判定

最终，依据式(3)给出判定结果.

(3)

其中，ε为可调节的检测阈值.

3.4 系统实现

基于本文所提方法实现了多线程程序抄袭检测系统MotifPD，由动态监控模块、胎记生成模块，以及相似性计算和抄袭判定模块组成.

动态监控模块负责监控程序执行，记录运行过程中调用的系统调用.该模块基于Pin动态插桩框架[20]实现，利用接口函数PIN_AddSyscallEntry-Function和PIN_AddSyscallExitFunction，分别在系统调用执行前后插入监控和分析代码，以捕获系统调用的相关信息.图2给出了捕捉的执行轨迹的片段，每行对应一条具体的系统调用，形式为“调用发生时所在线程的ID#系统调用号#系统调用名#具体参数#返回值”.胎记生成模块处理监控模块记录的执行轨迹，经预处理、gram匹配和扩展抽象，实现motifs胎记的提取.相似性计算和抄袭判定模块具体实现了3.2节和3.3节的算法，不再赘述.

Fig. 2 Trace snippet captured by the dynamic monitoring module图2 动态监控模块捕获的执行轨迹片段

4 实验分析

4.1 实验对象及参数设置

在一个公共的软件抄袭样本集[21]上验证了MotifPD的有效性，并与TreSB和TOB进行了对比分析.该样本集共计包含234个不同版本的多线程程序，由35个涉及不同领域的多线程程序在一系列混淆策略下衍生而来.采取的混淆策略包括：

S1. 利用不同的编译器及优化选项(llvm，gcc，o0-os)这类相对较弱的混淆手段生成目标代码.

S2. 应用专业的混淆工具，包括SandMark，Zelix KlassMaster，Allatori，DashO，JShrink，Pro-Guard，RetroGuard，构造强力混淆副本.

S3. 利用加壳混淆工具UPX(the ultimate packer for executables)处理目标代码.

表1给出了该数据集包含软件名称(“Name”列)、版本号(“Version”列)在内的一些基本信息.“#Ver”列给出了每个软件(含原始程序在内)的抄袭副本总数，以及采用各混淆手段生成的抄袭副本个数；“Size of Program”列则标出了每个软件的所有副本中最大副本的尺寸.关于该数据集的其他信息，网站[21]和文献[15]中都作了详细介绍，此处不再赘述.

Table 1 Outline of the Multi-threaded Program Plagiarism Benchmark表1 多线程程序抄袭样本集基本信息

Notes: Each value in the “Total” column gives the number of total versions of the corresponding program. It equals to the number of plagiarism copies (generated with obfuscation strategy S1, S2 and S3) plus one original version.

此外，MotifPD的效果依赖于一些参数，如无特别说明下文实验中各参数的默认设置为：gram匹配阶段k=3，扩展抽象阶段γ=2，生成motifs胎记时阈值Φ=10；另外，每个程序均提供多个输入，同一输入均驱动程序执行4次.

4.2 胎记的弹性和可信性评估

软件胎记的品质高低由其弹性(resilience)和可信性(credibility)来衡量[4].这里引用Collberg等人[3]对这2个基本特性的描述.

1) 弹性.假定程序Q是通过对程序P应用语义保留的代码混淆τ生成的抄袭版本，利用胎记技术计算二者的相似性SIM(P,Q)，如果SIM(P,Q)≥1-ε，则认为该胎记技术对于τ而言具备弹性.

2) 可信性.对于2个独立开发的软件P和Q，利用胎记技术计算二者的相似性SIM(P,Q),如果SIM(P,Q)<ε，则认为该胎记技术具备可信性.

更直观地讲，弹性刻画了胎记技术识别抄袭的能力，即要保证胎记能对抗各类语义保留的代码混淆，混淆后利用胎记依然可以识别出原程序与其混淆版本的同源性；可信性则要求从独立实现的软件中抽取出的胎记总不相似，刻画了胎记技术区分独立开发软件的能力.

为了评估motifs胎记的弹性，将公共数据集中各程序的原始版本作为原告，采用各种混淆策略的衍生版本作为被告，构成一系列的原告-被告比较对，并利用MotifPD计算这些比较对的相似性.图3给出了各种混淆策略下比较对的相似性的分布情况，其中纵轴刻画了计算得到的相似值落入到图例所示各区间的比例.可以看到几乎所有比较对的相似度都在0.9以上，表明motifs胎记对该公共数据集中涉及到的混淆手段均具备很好的抵抗效果.

为了评估motifs胎记的可信性，选用数据集中相互独立开发的软件作为实验对象，具体包括6个多线程压缩解压缩软件、10个Web浏览器以及5个音频播放软件，并利用MotifPD计算它们之间的相似性.图4统计了同类软件间和不同软件间的相似性的分布情况.可以看到，不同类软件间的相似性普遍很低，都在0.1以下.同类软件由于在功能上具有较大的一致性，它们之间的相似性略高，但绝大多数依然落入到较低的相似区间.其中有少数几个比较对的相似性在0.2甚至0.4以上.通过人工检查发现，采用了相同算法或共同依赖于某些功能模块，是导致MotifPD在处理这些比较对时得出较高相似性的原因.比如压缩解压缩pbzip2和lbzip2的相似性为0.25，因为它们都是基于Burrows-Wheeler压缩算法实现的并行版本；浏览器arora，Dooble，epiphany，luakit，midori均采用了WebKit布局引擎，MotifPD在计算它们之间相似性时也得到较高的值.

Fig. 3 Resilience evaluation of motifs birthmark图3 motifs胎记的弹性评估

Fig. 4 Credibility evaluation of motifs birthmark图4 motifs胎记的可信性评估

4.3 与其他胎记技术的对比分析

本节将MotifPD与其他2种线程感知胎记技术TreSB和TOB(1)TOB是一个线程感知胎记框架，提供了2种模型SA和SS，改良传统动态胎记以支持多线程程序的抄袭检测.对比实验中的TOB指的是改良的SCSSB，并用TOBSA和TOBSS区分其在改良SCSSB时具体用的是何种模型.以及同样基于系统调用的动态胎记技术SCSSB[13]的总体性能进行系统地比较.

4.3.1 检测效果的对比分析

各胎记技术检测效果的评估采用TreSB[15]和TOB[9]这2篇文献中使用的3种指标，包括URC[22](union of resilience and credibility)，F-Measure，MCC[23](Matthews correlation coefficient).其中URC是为了综合考量胎记弹性和可信性而专门设计的指标，但存在偏爱更大阈值的不足[5]；F-Measure和MCC则是信息检索与数据挖掘领域常用的综合性指标.

为方便描述，定义下列符号.

1)EP.由存在抄袭关系的比较对构成的集合，即∀(P,Q)∈EP，都有程序Q抄袭自程序P.

2)JP.由被抄袭检测系统判定为抄袭的比较对构成的集合，即∀(P,Q)∈JP，程序Q被判定为抄袭了程序P.

3)EI.由相互独立的比较对构成的集合，即∀(P,Q)∈EI，程序Q与程序P相互独立.

4)JI.由被抄袭检测系统判定为相互独立的比较对构成的集合，即∀(P,Q)∈JI，程序Q被判定为与程序P相互独立.

基于上述符号约定，URC可表示为

(4)

对于F-Measure，采用最常用的F1，其是准确率(Precision)和召回率(Recall)的调和平均数.

(5)

其中，

MCC综合考虑了真正、真负、假正和假负，在正负类样本不均衡的情况下也可以对检测效果做出合理的评估.本文实验样本中，抄袭对的数量要远高于非抄袭对的数量，即正负类样本不均衡，因而MCC的评估结果相比F1更加可信.

(6)

其中，TP=|EP∩JP|，FN=|EP∩JI|，FP=|EI∩JP|，TN=|EI∩JI|.

对于每种度量指标而言，在同一阈值下其值越高，表明方法的检测性能越好.图5(a)～5(c)分别给出不同阈值下(2)URC是基于式(3)定义的指标，要求必须有1-ε≥ε，故ε的有效范围为0～0.5.而为了采用F-Measure和MCC，TOB和TreSB通过移除“无法判定”部分，将抄袭检测描述为一个二分类问题(当SIM(P,Q)≥ε时判定为抄袭，否则判定为不存在抄袭)，故采用这2种指标时ε的有效取值范围为0～1.各胎记技术相对于3种度量标准的对比结果.可以看到，对于任意一种度量，MotifPD对应的曲线在整个x轴上几乎总在其他曲线之上，表明在任意阈值下MotifPD的检测性能几乎总优于其他几种胎记技术.

Fig. 5 Overall performance evaluation with respect to three different metrics图5 相对于3种不同度量标准的总体性能比较

为了更直观地量化比较各胎记技术的应用效果，性能增益PerGain[9]是基于各曲线下的面积AUC(area under the curve)并以SCSSB作为基准得到，刻画了各线程感知胎记技术相对于传统动态胎记SCSSB的性能提升程度.

(7)

其中，X可取{MotifPD,TOBSA,TOBSS,TreSB}中的任意1种，AUCX和AUCSCSSB分别表示线程感知胎记和SCSSB的AUC值.

表2给出了各线程感知胎记技术相对于3种度量标准的PerGain值.可以看到MotifPD的性能增益始终是最高的，表明MotifPD可以更好地应对多线程程序的抄袭.

Table 2 Comparative Quantification of the Thread-oblivious Birthmarks Based on PerGain表2 各线程感知胎记技术基于PerGain的量化比较

4.3.2 时间开销的对比分析

MotifPD与其他3种动态胎记技术均主要包含3个阶段：执行轨迹捕获、胎记生成以及相似性计算.对于执行轨迹的捕获，均利用Pin动态插桩监控程序执行来实现，动态监控带来的负载平均为3倍左右；因为本文实验均基于相同的执行轨迹集，在该阶段各方法的开销一致.因而，本节重点对比MotifPD与其他方法在后2个阶段的时间开销.

表3给出了各胎记技术在胎记生成阶段(Phase Ⅱ)以及相似性计算阶段(Phase Ⅲ)的平均时间开销.在胎记生成阶段，MotifPD生成胎记的平均时间显著高于其他方法，约为其他方法的84倍；其他方法因为均是直接利用k-gram生成胎记，它们的胎记生成开销十分接近.在相似性计算阶段，各方法的时间开销区别不大，只有TOBSS因为需要利用最大带权二分图匹配实现相似性计算，开销略高，比较1对胎记平均需要20 ms.可以看到，MotifPD生成胎记的过程比较耗时，在检测效率方面要低于其他动态胎记技术，但对于抄袭检测而言，检测的准确性相比检测效率更加重要，后续计划优化扩展-抽象的迭代过程，提升motifs胎记的提取效率.

Table 3 Average Time Cost of Each Birthmarking Method in Phase Ⅱ and Phase Ⅲ Respectively表3 各胎记技术在Phase Ⅱ和Phase Ⅲ的平均时间开销 ms

4.4 k值的影响分析

精确匹配阶段k值的选择，直接影响着motifs提取的效率以及提取出的motifs的多样性，从而会对整个方法的检测效果和检测效率产生影响，本节结合实验具体分析k值的选择问题.

图6给出了不同k值下MotifPD相对于3种度量指标的检测效果.可以看出，当k=1或k>10时，检测效果不佳；取值在2～10之间时，检测效果的差异不大.当k=1时，从图7中可以看出识别出的精确匹配对数量会非常多，导致即使对于非抄袭对而言，也会存在不少motifs一致，从而引起误报；随着k值的增大，识别出的精确匹配对的数量会不断减少，结合图8可以看出这将导致提取出的motifs的数量和多样性减少，当减少到一定程度，如k>10时，会使得计算抄袭对的相似性时得到较低值，从而引发漏报.比如，k=15时，有192对抄袭对的相似性在0.9以下；k=10时，相似性在0.9以下的抄袭对仅有28对.

Fig. 8 Impact of k on motifs diversity图8 k值对motifs多样性的影响

通过2.3节的分析，可以知道k值还影响着motifs提取的效率.图7给出了取不同k值时生成motifs胎记的平均时间开销，可以看出随着k值的增大，时间开销逐渐下降，特别是在k值由1增大为3的过程中，时间开销显著下降.因此，综合对检测效果和检测效率的影响，k=3是一个较为合理的选择.

5 方法的局限性讨论

MotifPD从程序在同一输入下多次运行对应的多条执行轨迹中提取motifs来降低线程交织不确定性的影响.因而在处理单线程程序时，MotifPD将表现出与传统动态胎记技术基本一致的检测效果；同时在以下2种情况下，MotifPD将退化至传统动态胎记技术的水平.

1) 处理线程间交织程度特别高的程序时.提取motifs的前提是程序在同一输入下的多条执行轨迹中存在相似部分，线程间高度的交织显然会导致捕获的轨迹极不相似，使得提取的motifs过少甚至无法提取.然而，时序约束使得某些功能模块必须顺次执行，用于共享资源安全访问而设置的各种锁也会大大减少交织度，因而现实中绝大多数多线程程序的交织程度不会过于复杂.

2) 混淆导致原告和被告程序执行轨迹差异很大的情况下.动态胎记技术本质上是通过衡量原告和被告程序的执行行为的相似性检测抄袭，如果存在某些混淆手段使得原被告程序在相同输入的执行轨迹出现很大差异，跟传统动态胎记技术一样MotifPD将无法检测出抄袭.MotifPD采用的是由系统调用构成的执行轨迹，对系统调用进行删除、修改或替换的混淆方式会挫败本文检测方法.然而，系统调用作为用户态应用程序请求操作系统内核服务的唯一手段，较难被删除和篡改，因而实施此类混淆的代价很高，特别对于多线程程序而言，随机或刻意的修改很容易引入微妙的并行问题.

6 总 结

本文提出了一种新的线程感知胎记技术以解决多线程程序的抄袭检测问题.该方法从程序在同一输入下多次运行所捕获的执行轨迹中，经轨迹修剪、gram匹配和扩展抽象，识别轨迹间的相似部分并抽象出可以抵抗线程交织干扰的motifs；在此基础上构建motifs胎记，并通过衡量motifs胎记的相似性检测程序间潜在的抄袭.基于本文方法实现了抄袭检测工具MotifPD，在公共数据集上开展的实验表明，其能有效对抗当下主流的代码混淆手段，比多线程程序抄袭检测方法TreSB和TOB表现出更优秀的检测能力.不过，motifs胎记的构建时间开销要高于TreSB和TOB，对此接下来计划优化扩展-抽象的迭代过程.