Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Code Relatives: Detecting Similarly Behaving Software

论文下载

  • 作者:Fang-Hsiang Su, Jonathan Bell, Kenneth Harvey, Simha Sethumadhavan, Gail Kaiser and Tony Jebara
  • 单位:Columbia University
  • 出处:FSE’16

Abs & Intro

在先前的一些相似性检测工作中,主要是检测执行输出是否相同,或者是否有相同的特征identifier或者结构

simions:codes with dynamically similar functional input/output

  • 然而检测simions的方法也是有限制的,由于面对对象语言可以定义新的数据类型,输出数据可以被定义包装成完全不同的数据类型。
  • simion detector在处理不同结构类型的输出时存在着一定的困难。

希望能够通过学习结果的计算过程,通过比较计算过程来判定代码相似性

Code relatives: continuous or discontinuous code fragments that exhibit similar behavior, but may be expressed in structurally or even conceptually different ways.

System Design

DyCLINK由两部分组成:online graph construction以及offline (sub)graph matching

Fig

本文选择了Java作为目标语言,所以DyCLINK会记录执行过程中的JAVA字节码。如果要检测其他语言,只需要实现相应的online graph construction,而后续的子图匹配过程是语言无关

Constructing Graphs

根据动态执行记录的trace。构建相应的graph。其中每个节点代表一条指令,每条边代表指令间的依赖关系。这个图中包含目标方法的所有指令,以及所有目标方法所调用的方法的指令

定义了三种类型的依赖边

  • depinst: A data dependency between an instruction and one of its operands.
  • depwrite: A read-after-write dependency on a variable.
  • depcontrol: A weighted edge indicating that some instructions are controlled by another (e.g., through a jump),corresponding to the frequency that control will follow that edge based on the observed executions.

LinkSub: Link-analysis-based Subgraph Isomorphism Algorithm

接下来的相似性检测过程可以当做一个子图同构问题。

为了提高效率,首先利用粗粒度的筛选缩小目标集合。这里由于依赖关系图类似于一个网络,所以引入PageRank的算法,对源代码段构成的图中的节点进行排位。

PageRank: https://en.wikipedia.org/wiki/PageRank

并根据排位选出其中排位最高的节点,作为source graph的centroid。如果target graph中含有centroid instruction,则它就有可能是source graph的code relative。

接着有根据两个图的distributions of instructions(?),计算他们的Euclidean distance,根据设定的阈值,进一步缩小目标代码集合。

两轮筛选过后利用link analysis来分析目标代码段和源代码段之间的相似度:

  • DyCLINK calculates a PageRank dynamic vector, DV , for the candidate subgraph (LinkAnalysis), where the result is a sorted vector of all of the instructions (vertices from the subgraph), ordered by PageRank.
  • Finally, use the Jaro-Winkler Distance to measure the similarity of two DV s, which represents the similarity between two Gdigs.

Jaro–Winkler distance:https://en.wikipedia.org/wiki/Jaro-Winkler_distanc

Evaluation

文章的测试用例选取了多年Google Code Jam Competition中accepted的答案作为相似性分析的对象。 并将其与SourcererCC以及HitoshiIO作比较

第一个实验说明了Code Relatives的filtering的所带来的效率,以及它的分析时间:

Fig

第二个实验是关于Code Relatives作为Code search的能力,通过和SourcererCC以及HitoshiIO的比较,说明Code Relatives一般能检测出更多功能相似的代码:

Fig

最后一个实验是关于Code Relatives用于KNN算法的准确性:

Fig