代码相似性研究中的抽象相似性分析

可在www.sciencedirect.com在线获取理论计算机科学电子笔记331（2017）87-99www.elsevier.com/locate/entcs抽象相似性分析Mila Dalla Preda和Vanessa VidaliDiartimentodiInformatica，Universita`deglistudidiVerona，Italy摘要代码相似性是程序分析的一个重要组成部分，在计算机科学的许多领域都有应用。基于图形的程序表示，如控制流程图和依赖图，通常被用作决定代码相似性的基础。事实上，许多相似性算法观察这些基于图形的表示程序的特定属性，以决定两个程序是否相似。在这项工作中，我们提出了一个通用的框架相似性分析程序的相似性表示在抽象的控制流程图表示。特别是，我们认为抽象的控制流程图的基本块保留字：代码相似，抽象解释。1介绍代码相似性研究两个程序是否相似，或者一个程序是否与另一个程序的一部分相似（代码包含）。代码相似性是程序分析的一个重要组成部分，在计算机科学的许多领域都有应用，例如代码片段大集合的逆向工程[13，16]，克隆检测[2，8]，程序知识产权侵权行为的识别[1，17，12]，恶意软件检测[9，10，15]，软件维护[11，19]，软件取证[2，14]。在这些应用程序中，当比较两个代码片段时，重要的是要考虑由于代码演变、编译器优化和编译后混淆而引起的变化。这些代码更改会产生语法不同但具有相同预期行为的代码片段。这意味着重要的是要识别通过编译器优化或代码混淆获得的相同程序的修改。为此，我们需要从语法变化和实现细节中抽象出来，这些细节不会改变程序的预期行为，也就是说，在一定程度上保留了程序的语义。1电子邮件：mila. univr.it，vanessa. studenti.univr.it2这项工作得到了MIUR FIRB 2013项目FACE RBFR 13AJFT的支持http://dx.doi.org/10.1016/j.entcs.2017.02.0061571-0661/© 2017作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。88M. Dalla Preda，V.Vidali/Electronic Notes in Theoretical Computer Science 331（2017）87为了同时考虑语义意义和句法模式，现有的相似性分析工具通常采用混合的句法/符号和语义表示程序，例如控制流程图和依赖图，它们表示控制流程或程序指令之间的依赖关系最近，在[7]中，作者研究了使用符号有限自动机（SFA）及其抽象来分析代码相似性。SFA在[18]中被引入作为传统有限状态自动机的扩展，用于建模具有有限字母表潜力的语言。SFA中的转换被建模为在给定的布尔代数中解释的约束，提供约束的语义解释，因此识别语言的（潜在的无限）结构组件（参见[5，18]）。在[7]中，作者展示了如何使用SFA来表示用任意编程语言编写的程序的语法和语义，其思想是用表示程序指令的语法标签来标记转换，而它们的解释由这些指令的语义给出。因此，SFAs提供了理想的形式化设置，以便在同一个模型中处理程序的语法结构及其预期语义的抽象。在[7]中提出了一个形式化的框架，用于抽象SFAs的语法和语义属性，从而抽象表示为SFAs的程序。这个形式化的框架在理解现有的相似性分析工具，以及基于程序的语义和语法特性的相似性分析工具的开发中是非常有用的。本文中提出的工作和我们提出的原型实现可以被视为[7]中提出的软件相似性一般理论的实验验证的第一步。在本文中，我们考虑程序的标准控制流图（CFG）表示，它是相对于[7]中提出的程序的SFA表示的简化模型。事实上，一个CFG可以很容易地转换成一个SFA，其中自动机同构于CFG，基本块标记自动机转换，并且基本块的解释是恒等函数（这是因为程序的CFG表示不考虑基本块的解释）。在试图建立一个相似性分析工具参数上的程序的属性，我们决定从简单的CFGs开始。因此，在这项工作中，我们提出了一个通用的框架，代码相似的概念是形式化的抽象，在抽象的解释意义上，程序的CFG。我们提出了一种用于测试代码相似性的方法，该方法对用于决定相似性的CFG的基本块的属性是参数化的事实上，许多现有的算法相似性分析可以解释在我们的框架，通过形式化的抽象属性的块的CFG，他们认为。这使我们能够通过比较表征它们的抽象来比较现有的相似性算法。此外，所提出的相似性测试的精度可以通过修改被观察到的CFG的抽象属性来调整。我们提供了一个原型实现所提出的方法，使我们能够测试两个片段的代码的相似性，相对于三个不同的基本块的抽象属性。M. Dalla Preda，V.Vidali/Electronic Notes in Theoretical Computer Science 331（2017）8789[f−d=efλx. {y|x≤f（y）}]。def+def⊆×论文结构第2节回顾了论文中使用的基本概念在第三节中，我们提出了一个基于CFG的抽象解释的相似性分析框架。在第4节中，我们提出了我们的实现的细节，并讨论了我们所获得的结果。论文最后讨论了今后的工作。2背景数学符号。 给定一个集合S，我们用（S）表示 S 的幂集。×P，≤ P表示序关系≤的偏序集P，而序关系≤的完备格P，最小上界（lub）≤，最大下界（glb）最大元素T和最小元素T表示为×P，≤，T，。±表示函数之间的逐点排序。 f：C→ D在完备格上是可加的（或共加性），对于任何Y <$C，f（<$Y）=<$f（Y）（f（<$Y）=f（Y））。右（右）左）的伴随函数f是f= λx。 {y|f（y）≤ x}有向图定义为一个有序对G=（N，E），其中N是节点的集合，E N N是表示图的边的有序对的集合。有向图G=（N，E）的子图是有向图GJ=（NJ，EJ），其中NJ<$N且EJ<$E。我们用Sub（G）表示图的可能子图的集合G.两个图G1=（N1，E1）和G2 =（N2，E2）是同构的，如果存在（n1，NJ1）∈E1（n2，NJ2）∈E2，其中f（n1） =n2，f（NJ1） =NJ2. 我们不和他一起|G|thenumberofno desof图G.抽象解释。 抽象解释用于对属性而不是（具体）数据值进行推理[3]。 逼近可以等价地用Galois连接或闭包算子表示[4]。 Galois连接（GC）是一个元组（C，α，γ，A），其中×C，≤C →A是具体域，×A，≤A → A是抽象域，α：C → A是抽象映射，γ：A → C是具体化映射，它们形成一个邻接：αy∈A，x∈C：α（x）≤Ay惠x≤Cγ（y）[3，4]. α（分别为左（左），右（右）。右）-伴随的γ（resp. α），并且它是加性的（分别为共添加剂，即其保留润滑剂（相应地，glb）的域的所有子集（包括空集）。回想一下，元组（C，α，γ，A）是GC i <$α is additive i<$γis co-additive。实际上，一个加性抽象映射α诱导一个具体化映射γ，反之亦然，形式上γ（y）= γ {x|α（x≤y}和α（x）=<${y|x≤γ（y）}。偏序集×C，≤ C上的上闭包算子或闭包是一个单调、幂等、广延的算子C→C（即C → C）。 c ∈C：c ≤ c（c））。闭包是由它们的定点集合唯一确定的。C上所有闭包的集合记为uco（C）。因此C的抽象整环格同构于uco（C）[3，4]。 若C是完备格，则有×uco（C），±，H，H，λx. T，id ∈ C是一个完备格，其中id =λx，x且对每一个ρ，η∈uco（C），ρ±ηi∈C：ρ（y）≤η（y）i ∈ η（C）<$ρ（C）.如果（C，α，γ，A）是GC，则<$A=γ<$α是与A相关的闭包，使得<$A（C）是与A同构的完备格。90M. Dalla Preda，V.Vidali/Electronic Notes in Theoretical Computer Science 331（2017）87defα3抽象相似性分析框架我们考虑用CFG表示的程序。程序的CFG是一个图，其中节点由非分支指令序列给出，边表示可能的控制流。 更正式地说，让I是由i覆盖的可能程序指令的集合，我们定义集合B ={b = i1.. In|<$i ∈ [1，n]：ii∈I，ii是非基准指令}，表示可能的基本块。 程序P∈ I的CFG是一个图GP=（NP，EP），其中节点集NP<$B指定P的基本块，边EP<$NP×NP表示程序P执行期间可能的控制流。考虑基本块幂集的具体整环×B（B），α，γ，B（B）与一个抽象整环×B，≤α相关的一个特殊抽象函数α：β（B）→ B，该抽象函数α：β（B）→B产生一个Galois联络×B（B），α，γ，B. 设基本块上的一个抽象函数α，我们称两个CFGsG和GJ是α-等价的，记为G<$αGJ，如果它们是同构图，并且相应的基本块被α抽象为相同的抽象基本块.给定基本块的抽象，可以导出表示为相对于集合包含排序的CFG的幂集域上的闭包算子的CFG的抽象，即，×（CFG），×定义3.1一个基本抽象α：B→ B →B→B →B导出一个闭包ρα∈defuco（λ（CFG））：ρα= λX. {GJ∈CFG| <$G∈X：G<$GJ}。给出一个基本块抽象α：β（B）→Bβ，由ρα定义的CFG抽象将α等价的CFG集合在一起，即具有相同形状且对应的基本块相对于α不可区分的CFG。观察到两个α等价的CFG对应于两个具有相同控制结构的程序，以及通过块抽象α抽象为相同抽象对象的相应基本块。我们使用α-等价的概念来定义下面的CFG相似性检验定义3.2考虑α：β（B）→Bβ，两个CFG1和G2如下：•G1和G2是α相似的i <$ρα（G1）=ρα（G2），即如果G1<$αG2，•G1是α-包含在G2中的，记G1≤αG2i <$i存在H2∈Sub（G2）使得ρα（G1）=ρα（H2），即如果G1<$αH2.很明显，α-相似性分类为α-等价的相似CFG，而α-包含验证了一个CFG和另一个CFG的可能子图之间的α参数α固定了要观察的基本块的属性以确定同构CFG之间的相似性。当然，如果α考虑基本块的语法属性，则相似性测试将对语法变化敏感，而从语法细节中抽象并查看基本块的语义属性的抽象α将对语法代码变化（例如由代码混淆引起的）更具弹性。然而，这种可扩展性仅是块级的。 事实上，α相似性检验在尊重它对程序的控制流结构具有灵活性，而对基本块中的代码片段则具有灵活性这使我们能够识别为相似的，只有M. Dalla Preda，V.Vidali/Electronic Notes in Theoretical Computer Science 331（2017）8791defdef通过句法变换获得的程序，即，代码混淆和编译器优化，这些都是按块工作的。例如，α-相似性测试不能识别通过语义控制流转换（如不透明谓词插入、循环展开、循环优化的代码移动等）获得的相似程序;另一方面，通过选择合适的块抽象α，α-相似性测试允许我们识别通过块方式工作的代码转换（如变量重命名、表达式整形等）获得的相似程序。很明显，抽象相似性检验的精确度取决于抽象α的选择，因此也取决于它所诱导的闭包ρα如果α= λX. 然后，所提出的方法将具有相同形状的所有CFG分类为相似，而不管基本块中存在的代码。另一方面，如果α=λX.X，则意味着所提出的方法仅将具有相同形状和完全相同的基本块的相似CFG分类。 一般来说，如果α1±α2意味着当两个CFGα1相似时，它们也是α2相似的，但反之亦然。这意味着，在所提出的正式框架的抽象相似性分析，它是可能的比较不同的相似性工具，相对于所使用的基本块的抽象的相对程度的精度。现有的相似性分析工具，CFGs的工作可以在拟议的框架进行比较，通过指定的CFGs的抽象，他们隐式地使用。给定一个程序变换T：Prog→Prog和一个基本块抽象α：B（B）→B（P），我们认为α-相似性检验对变换T不敏感，如果P∈Prog，我们有GP<$αGT（P），这意味着α-相似性检验承认P和T（P）是同一程序的突变有趣的是，在所提出的用于相似性分析的形式化框架中，可以形式化地表征某个α相似性测试对其不敏感的程序变换类。我们用δT∈uco（ω（CFG））表示程序的CFG上变换T：Prog→Prog所保持的最具体的性质，即：δT= H {δ∈uco（ω（CFG））|P∈Prog：δ（GP）= δ（GT（P））}.回想一下，在[6]中，作者提供了一个系统的方法来导出程序变换T所保持的最具体的性质δT。因此，给定一个基本块抽象α：B（B）→B（B），我们将α-相似性不敏感的程序变换集定义为：Tα={T：Prog→Prog|ρα±δT}这意味着通过Tα中的变换获得的程序P的修改是α相似的，如下所述定理3.3设α：B→B→ T，T∈Tα，则f或任意programP，证明了GP与GT（P）是α相似的，即GP<$αGT（P）.图1表示基于以下三个模块的代码相似性分析的工作流程：（1）CFG提取器，（2）抽象引擎和（3）相似性检查。假设有一组程序，我们希望根据它们的相似性对其进行分类。我们要做的第一件事是通过使用静态或动态方法来提取这些程序接下来需要92M. Dalla Preda，V.Vidali/Electronic Notes in Theoretical Computer Science 331（2017）87图1.一、抽象相似性分析工具的工作流程和模块来固定我们想要使用的基本块的抽象属性α，我们必须自动抽象这些CFG的基本块。最后对抽象的CFG进行相似性检查，它可以用于将α相似的CFG分组在一起。4原型实现我们已经实现了图1中描述的相似性分析方法。在下文中，我们提供了我们的实现和一些实验的描述。CFGExtractor：我们实现了一个从相应的执行轨迹中动态地提取程序CFG的算法，从而研究有效执行了什么以及对系统的影响。这在分析恶意程序时可能是有用的，其中代码可能被打包，或者在分析采用代码混淆的代码时可能是有用的，例如不透明的谓词插入以妨碍逆向工程。事实上，通过分析包含加密部分的程序的执行轨迹，可以发现和理解加密/解密引擎，有时还可以发现和理解所使用的密钥。在程序运行结束后，我们使用程序跟踪来检查程序行的执行轨迹。O-线调查提供较少的控制比交互式调试，但允许我们有一个对整个跟踪视图。事实上，通过程序跟踪，我们不仅能够收集每个基本块的次数，或控制窗口的边缘已遍历像在profiling，但也实际列表已执行的块或边缘的。特别地，我们认为有限动态跟踪是在特定输入上执行期间遇到的操作和指令序列的记录。形式上，一个有限的动态轨迹可以表示为一个集合t ra ce=×ii.. . ，ijj，whereiii.. . ij是P中的指令。一Tracer是一个程序Tracer，它接受一个程序P及其一组输入X，并在X上执行P，返回表示执行指令序列的跟踪集。因此，给定程序P和输入x1，.，xn∈X：Tracer（P，x1）= trace1，.， Tracer（P，xn）= trace n.在我们的实现中，我们使用计时器收集有限的动态跟踪，以便在非终止的情况下在有限的时间后结束计算。每个轨迹然后被表示为单个图，其中每个指令被包含在由指令的行号标识的节点中，并且执行流程由有向边给出。如果轨迹从同一点经过不止一次，则不会添加节点，但会使用现有节点并重新连接，因为节点标识唯一。这允许我们表示循环。然后，通过节点识别，将表示单个动态轨迹的这些图合并在一起以创建唯一的图。最后，通过以下方式将图交换为CFG：M. Dalla Preda，V.Vidali/Electronic Notes in Theoretical Computer Science 331（2017）8793将节点分组为基本块，其中每个基本块包含没有跳转的指令序列。所提出的CFG提取器是基于动态分析的，因此它可能无法覆盖所有可能的程序执行。抽象引擎：一旦提取了CFG，就可以执行抽象。在我们的实现中，我们考虑了在单个指令上工作的基本块抽象。 其主要思想是使用类型化符号变量抽象基本块中的指令，以便独立于变量名。这是通过在块内一致地用符号变量替换变量名来实现的替换是一致的，因为同一个块中的同一个变量的两次出现除了抽象变量名之外，还抽象常量这可以表示为基本块抽象α：I（B）→BI，其中每个基本块根据指令抽象β：I→BI（其中BI是抽象指令的集合）抽象如下：α（ib）=β（i）α（b）α（b）=β我们将考虑只观察到赋值指令的指令集β：I→ I，如果i是赋值指令，则形式上β（i）∈I，否则β（i） =I。我们实现了三种不同的指令抽象，这些抽象有一个共同的基础，每个新版本都保留了以前版本的改进。让我们回想一下，赋值指令计算表达式（右侧），并将结果值赋值给目标（左侧）。我们考虑字符串类型和数字类型的变量（包括整数，浮点数和布尔值），而其他类型设置为未知。在我们的抽象中，每个常量都被抽象为它的类型：例如，“hello world”被抽象为str（字符串），而3被抽象为num（数字）。相反，每个变量都被抽象成一个符号名称（在下文中，我们使用大写字母来表示变量的符号名称）。我们给右边的变量赋一个默认值，这些变量之前没有声明或使用过。例如，如果一个基本块包含赋值y= x，但以前没有使用x，则抽象将此赋值重写为B =def[A]，其中A和B是变量的符号名称，def[A]表示符号变量A的默认值。此外，我们将函数复合视为单个函数：fun1（fun2（x），y）可以看作是现在让我们描述我们已经实现的指令抽象。指令抽象β1. 这个抽象使用正则表达式来区分表达式和函数。我们在名称和符号对象之间构建了两个不相交的绑定集：varName，它收集具有相关符号名称的变量名称;funcName，它收集具有相关符号名称的函数名称。这两组是不相交的。当处理一个任务时，我们从右手边开始。通过这种方式，我们可以识别默认值和可能的表达式运算符。如果它包含数字或字符串，则此值将替换为标记numb或str. 如果有一个已使用的 变量，则 其对应的 符号名为94M. Dalla Preda，V.Vidali/Electronic Notes in Theoretical Computer Science 331（2017）87从varName集合中恢复;否则我们在变量和它的新符号名之间创建一个新的绑定，我们将其添加到varName。对函数执行相同的过程，其中函数名存储在funcName中。然后在左手侧重复该过程在表1的第二列中，我们报告了根据指令抽象β1抽象的基本块的一些示例。例如，在第一个基本块的抽象中，我们可以观察到符号名A在第一次赋值的左手边和第三次赋值的右手边被绑定到变量x此外，抽象认识到最后一次赋值的右侧变量a之前没有定义过，因此它必须引用默认值。指令抽象β2. 这种抽象与我们所考虑的编程语言的一个特定特性有关。在Python中编程时，我们注意到函数名可以与变量相关联，然后使用它来调用。例如，我们可以用这种方式重命名print函数print（“Hello world”）：首先我们创建一个变量a=“print”，然后调用a（“Hello world”），结果将是相同的。所以很容易混淆函数的名称。因此，我们决定修改第一个抽象，将函数名也放在varName中。这可以在表1中最后一个基本块的抽象中观察到。这个基本块赋值给变量x，然后将变量x用作赋值u = f（x）中的参数和v = x（3）中的函数。我们可以观察到，基本块抽象α1（由指令抽象β1引起）没有识别出在最后一条语句中被调用的函数是x，因此使用了函数fun0的新符号名。而基本块抽象α2（由指令抽象β2引起）捕获这种依赖性，并在两种情况下将x抽象为符号名B。另一方面，这种抽象失去了变量名和函数名之间指令抽象β3. 在最后一次尝试中，我们通过保留一些关于右侧表达式语法的信息并通过用类型信息注释符号名来细化抽象β 1。我们没有明确提到表达式中使用的运算符，但我们使用标记expr< args>来指示所有数值、字符串和函数表达式，其中是表达式中使用的符号对象列表。 由于这可能导致表达式类型信息的丢失，我们决定显式添加类型信息。我们假设一个类型优先级：string>> number >> unknown，这意味着，在一个包含字符串、数字和其他东西的表达式中，整个表达式被认为是一个字符串，等等。因此，赋值指令的抽象语法变为var：type = expr。例如，在表1的最后一列中，我们可以看到第一个基本块的最后一个赋值z = x + a是如何在D>中抽象的：number=exprA，def[C]。我们使用一个推理系统来为符号名分配类型。 很明显，即使这三个抽象概念是相关的，它们也有自己的特点。这个简单的例子显示了我们的相似性测试方法对于所选择的基本块抽象的灵活性。我们使用术语抽象CFG来指代其中M. Dalla Preda，V.Vidali/Electronic Notes in Theoretical Computer Science 331（2017）8795Σ| 门恩|（一）否则1m=基本块提取α1提取α2提取α3x = 1y = 5+2*3z = x + aA =数量B=数字+数字 * 数字D = A + def[C]A =数量B=数字+数字 * 数字D = A + def[C]A：number=expr> B：number=expr> D：number=expr A，def[C]>X = aa = 5B= def[A]A =数量B= def[A]A =数量B：未知=expr def[A]>A：number=expr>x =“a”y=“a”+b”z=“a”+5v = aw = sA =压力B =str+strC=str+intF = def[E]A =压力B =str+strC=str+intF = def[E]A：string=expr>B ： string=expr>C：string=expr>D ：string=expr A>F：string=expr def[E]>x =f（3）y = f（3）+2z = f（3）+“a”s= g（3，y）t=f（b）u =f（x）v = x（3）一= fun0（数字）B= fun0（数量）+数量 C=fun0（number）+str D =fun1（number，B）F = fun0（def[E]）G=fun0（A）H= fun2（数字）B = A（数量）C = A（数量）+数量D=A（numb）+str F = E（numb，C）H= A（def[G]）I=A（B）J = B（数量）B：未知=expr A（）> C：数字=expr A（）> D：字符串=expr A（）> F：未知=expr E（），C> H：未知=expr A（def[G]））> I：未知=expr A（B）>J：未知=expr B（）>表1由指令抽象βi导出的基本块抽象αi的示例，其中i∈ {1， 2， 3}每个基本块都是根据特定的基本块抽象来抽象的。相似性检查：当检查两个抽象CFG之间的相似性时，我们首先验证两个抽象CFG是否同构。如果它们不同构，我们检查其中一个是否同构于另一个的子图。当两个抽象CFGsG1=（N1，E1）和G2=（N2，E2）之间存在可能的匹配M<$N1×N2时，我们继续分析块相似性.块相似性在匹配节点（m，n）的单个对上执行，其中m∈N1且n∈N2：⎩|门恩|注意，由于我们已经考虑的基本块抽象在单个指令上工作，因此我们可以将块相似性度量为公共抽象指令的数量这样，我们将基本块视为指令集，从而丢失了关于这些指令执行顺序的任何信息。接下来，全局相似性的图形计算通过总结块相似性相对于所考虑的图形的最大尺寸全局相似度（M）=（m，n）∈M块相似度（m，n）最大值（|G1|、|G2|）（二）观察全局相似性（M）∈[0， 1]。 相似性可以通过块相似性（m，n）=96M. Dalla Preda，V.Vidali/Electronic Notes in Theoretical Computer Science 331（2017）8712关于通过实验计算的经验阈值ω∈[0，1]测试相似性y（G， G）=.YES globalsimilary（M）≥ω（三）实现细节：该项目是用Python开发的，用于分析Python程序。这是因为我们对CFG的动态提取感兴趣，Python操作员使用一个简单的模块，称为Trace[20]，它允许我们跟踪程序执行，生成带注释的语句覆盖列表，打印调用者/被调用者关系以及在程序运行期间执行的列表函数，而无需检测程序。引导我们选择Python的另一个动机是需要研究图同构。事实上，我们使用NetworkX[21]，这是一个用于创建，操作和研究复杂网络的结构，动力学和功能的Pydot是DOT语言的接口，用于创建、处理、修改和处理图形，它还提供图形绘制和图形布局算法。我们决定使用它也是因为它比其他图形分析库有两个显著的优势：（1）它可以直接读取和写入点文件（不是原生支持，但它将它们转换为原生图形对象），以及（2）它为图形（子）同构测试提供了一个近似算法[22]：VF 2算法的实现[23]。简单地说，给定两个图G和H，如果G是H的子图，则该过程尝试匹配此外，Python还提供了一个代码混淆模块，我们需要测试所提出的相似性工具。事实上，我们在测试中使用的混淆技术是Python模块PyMini文件[24]所使用的，例如变量和函数名的混淆以及指令的重新排序实验和结果：我们已经验证了我们的原型，用于分析以下类别的程序的相似性• 混淆程序：在这种情况下，我们比较程序和它们的混淆变体;• 受感染的程序：在这种情况下，我们开发了一种玩具病毒，它在每个受感染的Python程序的开头复制自己，然后我们将此病毒与受感染的程序及其混淆进行比较。特别地，在我们的实验中，我们使用所提出的三个指令抽象来测试程序对的相似性，并检查α相似性（即，同构）和α-包容（即，子图同构）。在表2中，我们给出了我们已经运行的一些实验的结果我们所考虑的程序是两个计算更大公约数（GCD）的简单程序GCD 1和GCD 2。特别是，GCD 1包含在GCD2中，因为GCD 2包含与可能用户的更多交互 我们还考虑两个完全不同的版本的斐波那契算法：迭代FibIterat和递归FibRecurs，和玩具病毒病毒，我们已经开发。prefixobf-in programs表示混淆的变体，而prefix inf-与否，否则M. Dalla Preda，V.Vidali/Electronic Notes in Theoretical Computer Science 331（2017）8797感染的形式。因此，例如inf-GCD 1表示被病毒Virus感染的程序GCD 1，而obf-GCD 1表示被Python模块PyMini fier提供的混淆过程混淆的程序GCD 1（即变量和函数的重命名以及指令重新排序）。前两列显示了我们正在测试相似性的两个程序，而其他三列显示了每个抽象的相似性测试结果，这些测试是由我们的原型实现获得的。对于列左侧的每个基本块抽象，当考虑整个图上的同构时，我们报告全局相似性值，而在列的右侧，我们报告子图同构的相似性结果。程序1节目2文章摘要α1伊索莫夫亚同素异形摘要α2伊索莫夫亚同素异形文章摘要α3伊索莫夫亚同素异形FibIteratFibRecurs000000GCD1GCD 200.400.400.47病毒inf-GCD 100.7600.7600.78病毒inf-GCD200.7500.7500.75GCD1inf-GCD 100.6800.6800.67GCD 2inf-GCD200.6600.6600.66inf-GCD 1inf-GCD200.300.300.33GCD1obf-GCD 10.860.860.860.860.880.88GCD 2obf-GCD 20.820.820.830.830.830.83病毒obf病毒0.850.850.850.850.850.85FibRecursobf-FibRecurs0.840.840.840.840.840.84FibIteratobf-FibIterat0.830.830.830.830.830.83obf-FibIteratobf-FibRecurs00.4700.4700.48obf-GCD 1obf-GCD 200.400.400.42obf病毒inf-GCD 100.7500.7500.76obf病毒inf-GCD200.7400.7400.75表2同构与子同构的实验证实，当检查子图同构时，我们可以捕获更多的相似性。事实上，受感染的程序和它们的原始版本之间的相似性只能在考虑子图同构时被捕获，而代码的混淆变体之间的相似性也可以在考虑整个抽象CFG上的同构同时，子图同构导致全局相似性值通常低于当发现整个图之间的同构时获得的值，这取决于全局相似性的定义，该定义考虑整个图的局部相似性，而不仅仅是已经找到的匹配的大小这并不奇怪，我们已经获得的结果与三个abstrac-的，而不是彼此接近这是因为这些抽象共享许多共同的特征：它们都只考虑赋值指令，并且它们对这些指令执行类似的抽象特别是α1和α2的结果是相等的期望一个测试（GCD 2vs.obf-GCD 2）：在这种情况下，在原始程序中，混淆器通过不同的赋值变量重命名函数，第一个抽象没有捕获到同一个对象的绑定（首先将元素识别为实变量，然后识别为函数），而第二个抽象做到了。实验结果表明，α_3比其它两种方法更精确，98M. Dalla Preda，V.Vidali/Electronic Notes in Theoretical Computer Science 331（2017）87我们的期望只有在一种情况下（GCD 1与inf-GCD 1），α3失去了精度，因为不相等的部分代码比子图同构捕获的部分代码稍大。从我们已经运行的实验（比上表中列出的更多）中，我们能够建议将阈值固定在0.74。如果我们在表2中考虑的测试中使用这个阈值，我们可以看到有我们能够捕捉到的相似性和我们无法识别的其他相似性。此外，对于这个阈值，这三个抽象的行为方式是相同的。所执行的测试证实，我们的原型对死代码插入不敏感，因为CFG是动态提取的，并且对变量，函数，类和方法的重命名不敏感，因为考虑了基本的块抽象。它对代码换位也不敏感，因为每个基本块被认为是一个指令集，基于集合的相似性检查可以捕获混合代码，但它在精度上有所损失，因为集合是无序的。在某种程度上，我们对指令替换也不敏感，因为抽象只寻找赋值，而不是所有可能的指令。另一方面，这导致catch程序具有相同的赋值，但在语义上可能不同5结论和今后的工作到目前为止所做的工作可以被看作是第一步的相似性工具的参数上的程序属性用于决定相似性的发展，它可以在许多方面进行扩展。我们只植入和考虑了三个基本块抽象，它们彼此非常相似，并且作用于基本块的一个可能的改进是设计考虑整个块的语法或语义属性的抽象。我们提出的整体相似性测试方法按块工作，与[7]一致，但也与许多现有的相似性分析工具（如[13，9]）一致。为了克服这一限制，我们应该考虑整个CFGs的性质，而不仅仅是基本块的性质。在这个方向上，我们计划使用一些时序逻辑来表达图的属性。我们计划将相似性分析扩展到程序的SFA表示。我们已经有了一个将CFG转换为SFA的算法。我们需要的是开发考虑标记转换的谓词的句法方面和确定什么被SFA识别的谓词的语义的SFA的抽象。这个过程需要做很多工作，这也是我们计划在不久的将来要做的引用[1] A. 艾肯莫斯：一个检测软件剽窃的系统。https://theory.stanford.edu/ ~ aiken/moss/[2] C. Colberg 和 J. Nagra 。 监 视 软 件 ： 用 于 软 件 保 护 的 混 淆 、 水 印 和 篡 改 。 第 一 版 ， Addison-WesleyProfessional，2009年。[3] P. Cousot和R.库索抽象解释（Abstract interpretation）：一种统一的格模型，用于通过构造或近似定点来静态分析程序。在Proc. of the4th ACM Symposium on Principles of Programming Languages（POPL77），pages 238252.北京：人民出版社，1977年。M. Dalla Preda，V.Vidali/Electronic Notes in Theoretical Computer Science 331（2017）8799[4] P. Cousot和 R.库 索 程 序 分析 框 架 的 系 统 设 计 。 在 Proc. of the6th ACM Symposium on Principles ofProgramming Languages（POPL 79），pages 269282.北京：人民出版社，1979年。[5] L. DAntoni和M.维恩斯符号自动机的最小化。第41届ACM SIGPLAN-SIGACT Symposium on Principlesof Programming Languages，POPL，第541 - 554页。ACM，2014年。[6] M. Dalla Preda和R.贾科巴齐基于语义的抽象解释代码混淆在Journal of Computer Security，num 6，vol 17，pages 855 - 908.2009[7] M.达拉普雷达河Giacobazzi，A.拉克提亚和我。马斯特罗埃尼抽象符号自动机：可执行文件的混合语法/语义相似性分析。第42届ACM SIGPLAN- SIGACT Symposium on Principles of ProgrammingLanguages，POPL 2015。第329 - 341页，2015年。[8] R. Komondoor和S.霍维茨使用切片来识别源代码中的重复。第八届国际静态分析研讨会论文集（SAS），第40-56页，Springer 2001。[9] C. K rugel，E. Kirda，D. Mutz，W. K.Ro bertson和G.维格纳利用可执行文件结构信息的多态性恶意代码检测。在Proc.Recent Advances in Intrusion Detection，第8届国际研讨会，RAID 2005。第207 - 226页，Springer LNCS 3858，2005。[10] D.阿 夫奇 湖Martignoni 和M. Monga. 使 用控 制流 图 匹配 检测 自 变异 恶意 软件 。 在Proc.Detection ofIntrusions and Malware Vulnerability Assessment ， Third International Conference ， DIMVA2006，第129 - 143页，Springer LNCS 4046，2006年。[11] D. Gao，M. Reiter和D.歌BinHunt：Automatically Finding Semantic Difference in Binary Programs. 在proc第10届信息和通信安全国际会议，第238 - 255页，Springer-Verlag，2008年[12] K. Jeonguk，S.Hyungjoon，K.Dongjin，J.永植角Seong-je，P.Minkyu，H.Sangchul和K.成白通过Reversing和K-gram标记来测量Android应用程序的相似性在Proc. of theResearch