Andarwin 的 理论，设计与实现

Copyright

shtech.org2017

数据结构

Extract Semantic Vector Stage

Table Name: semantic_vector
Field: { “_id” : ObjectId(“5832a81d3a7cab0d422738f4”), “app_index” : “0”, “app_name” : “0142d70748992bbef33d2e0d5fa525d8a7e537e3.apk”, “method_name” : “(com.baoruan.theme.kkbzkacfigIauXjdxvP.DownloadService)>”, “method_index” : “1”, “semantic_vector” : [ 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ] }

问题 app_name 字段冗余

LSH Stage

Table Name: sv_lsh
Field: { “_id” : ObjectId(“58289cce3a7cab19b9f055cd”), “hash_code” : “0,-1,-1,-1,-1,-1,0,0,”, “value” : [ [ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 ] ], “cluster_id” : 0 , “frequency”: 16}

Minhash Signature

(((346282, 2512263, 2053996, 1613803, 281348, 1093902, 17136, 118044, 10453, 658471, 99073, 7024655, 211376, 2392043, 865, 451707, 1519910, 91361, 506234, 2396259, 2360410, 1812846, 3401448, 1140450, 148422, 616812, 627515, 948804, 85961, 507351, 1534244, 1041838), u’app92’), 0)

基石理念

层次划分

App

通常指一个 apk 文件, 用 dex2jar, enjarify 处理后， 会得到一系列 Java class 文件。

举个例子

.
└── asia
    └── rgmhpmj
        └── shlktj
            └── upuvung
                ├── a0.class
                ├── a1.class
                ├── a2.class
                ├── a5.class
                ├── a9.class
                ├── a.class
                ├── b0.class
                ├── b2.class
                ├── b3.class
                ├── b6.class
                ├── r8.class
                ├── R$anim.class
                ├── R$attr.class
                ├── R.class
                ├── R$color.class
                ├── R$drawable.class
                ├── R$id.class
                ├── R$integer.class
                ├── R$layout.class
                ├── R$menu.class
                ├── R$string.class
                ├── R$style.class
                ├── s0.class
                ├── s2.class
                ├── s8.class
                ├── s9.class
                ├── s.class
                ├── t0.class
                ├── t2.class
                ├── t4.class
                ├── t5.class
                ├── t9.class
                ├── t.class
......
                ├── z4.class
                ├── z7.class
                ├── z8.class
                └── z9.class

4 directories, 123 files

Class

对于一个 Java Class 文件， 它会有若干个 Method。

这里顺带提供一 Java Class 与 Jimple 转换的例子, 详情参考 A Survivor’s Guide to Java Program Analysis with Soot 。

Java Code

public class Foo {
  public static void main(String[] args) {
    Foo f = new Foo();
    int a = 7;
    int b = 14;
    int x = (f.bar(21) + a) * b;
  }

  public int bar(int n) { return n + 42; }
}

对应的 Jimple Code

public static void main(java.lang.String[]) {
  java.lang.String[] r0;
  Foo $r1, r2;
  int i0, i1, i2, $i3, $i4;
  r0 := @parameter0: java.lang.String[];
  $r1 = new Foo;
  specialinvoke $r1.<Foo: void <init>()>();
  r2 = $r1;
  i0 = 7;
  i1 = 14;
  // InvokeStmt
  $i3 = virtualinvoke r2.<Foo: int bar()>(21);
  $i4 = $i3 + i0;
  i2 = $i4 * i1;
  return;
}

public int bar() {
  Foo r0;
  int i0, $i1;
  r0 := @this: Foo; // IdentityStmt
  i0 := @parameter0: int; // IdentityStmt
$i1 = i0 + 21; // AssignStmt
return \$i1; // ReturnStmt
}

关于 Jimple 的实现细节 在 soot.jimple 和 soot.jimple.internal 包中。

The Jimple intermediate representation is available in the packages soot.jimple, soot.jimple.internal and an extensive collection of optimizations are available in soot.jimple.toolkits. especially soot.jimple.toolkits.scalar and soot.jimple.toolkits.annotation.\.

Control Flow Graph

基于 Soot 生成的控制流图，此处使用的 IR (Intermediate Representations) 是 Jimple 。

关于 Jimple Statement 有哪些类型。
具体包括：
In Jimple, statements correspond to Soot Units and can be used as such.
Jimple has 15 statements, the core statements are: NopStmt, IdentityStmt and AssignStmt.
Statements for intraprocedural control-flow: IfStmt, GotoStmt, TableSwitchStmt(corresponds to the JVM tableswitch instruction) and LookupSwitchStmt(corresponds to the JVM lookupswitch instruction).
Statements for interprocedural control-flow: InvokeStmt, ReturnStmt and ReturnVoidStmt. Monitor statements: EnterMonitorStmt and ExitMonitorStmt.
The last two are: ThrowStmt, RetStmt (return from a JSR, not created when making Jimple from byte code).

Semantic Vectors

注意到 每一个 App 包含 多个 Java Class， 每一个 Java Class 包含 多个 Java Method.

利用 Soot 和 FlowDroid， 我们将一个 App 中所有的 Java Method 都提取出来，并计算每个 Java Method 的 CFG。
每个 Java Method 和 CFG 一一对应。 但 Java Method 可能会出现重复的情况 (例如一些第三方库，在多个App中出现)。并且 CFG 也会出现重复的情况， CFG 出现重复的原因有两种，其一， 这两个 Java Method 的实质内容相同(它们是同一个第三方库的同一个Method，在两个不同的App里均使用了该第三方库); 其二，这两个方法属于不同类的构造方法，它们的内容一致，都使用默认的构造方法方式，即 A.init() 和 B.init(), 在逻辑意义上，他们是不同的方法，但在 CFG层面，内容是一致的。

对 Java Method 生成的 CFG 中统计不同类别 node 的数量，这个结果我们称之为 Semantic Vector。
需要说明的是， 从 CFG 到 Semantic Vector， 信息是有损失的。

与 Java Method 一一对应的 CFG 中， 每一个 Node 都代表一个 Jimple 语句 (Jimple Statement)。
并且 Jimple 中对不同语句 有做分类， 详见 CFG 章节。

这里有一个比较重要但又容易被忽视的细节，忽略 节点数 过少的 CFG。
4.1 Andarwin discards semantic blocks with fewer than 10 nodes, as small semantic blocks typically represent trivial and uncharacteristic code.

[Question]
How to determine this threshold？
We determined this threshold through manually analyzing apps and discovering that even a few lines of code can result in fairly large semantic blocks once the code is translated into static single assignment form, a requirement for the construction of PDGs. In Section 5.10, we explore ways to capture edge information from the PDGs in the semantic vectors.

Code Clone (feature)

feature
code clone

When two semantic blocks are code clones, they share the majority of their nodes (in CFG) and, thus, their semantic vectors will be similar. Therefore, by finding the nearest neighbors of a semantic vector, we can identify potential code clones.
Not all of the nearest neighbors will be code clone, as two completely unrelated semantic blocks could have the same frequency of node types. This is due to the lossy nature of our semantic vector characterization: many PDGs may generate the same semantic vector.
Specifically, the number of PDGs that generates a given semantic vector increases combinatorially with the magnitude of the semantic vector. Fortunately, our evaluation shows that these collisions are infrequent in practice (Section 5.10).

Code Clone 指 复用代码，或者是稍微修改原始代码
此处的思路是， 如果 两个 Method 是 Code Clone， 那么 这两个 Method 的 Semantic Vector 应该是非常接近的(在欧式距离上)。
使用 LSH 将 欧式距离接近 的 Semantic Vector 聚成若干个 Approximate Cluster。
Cluster 中所有 Semantic Vector 对应的 Method 被认为是 复用或者抄袭。

Feature Vector

每个 Code Clone (Feature) 都有自己的id编号， 每个 Code Clone 会对应一组 Semantic Vector， 而每个Semantic Vector 对应一个 App 的 Method。
一个 App 所有的 Method 会对应 一组 Semantic Vector， 这组 Semantic Vector 又会和一组 Code Clone 对应。 取一个维度是 Code Clone 总数的 vector，其中每一维对应一个Code Clone，如果 App 包含该维度对应的 Code Clone，这一维的值为1,否则这维的值为0。 这个 Vector 即是 App 的 Feature Vector。

数据库设计

semantic_vector

{ app_id: 1, app_name: dadkjal.apk, method_id:1, method_name: dadkjal.init(), semantic_vector: [1,3,2,4,6,7] }

遍历一遍 semantic vector 表， 为所有 semantic vector 编号
{ semantic_vector_id:1, app_id: 1, app_name: dadkjal.apk, method_id:1, method_name: dadkjal.init(), semantic_vector: [1,3,2,4,6,7] }

code_clone_detection

{ code_clone_id: 1, key: lsh_key, value: [semantic_vector_id1, semantic_vector_id2, semantic_vector_id3] }

feature_vector

{ app_id:1, value: [code_clone_id1, code_clone_id2 ]}

transposition_feature_vector

{ code_clone_id:1, value: [app_id1, app_id2, app_id3] }

full_similarity_detection_raw

full_similarity_detection_merged

full_similarity_detection_final

partial_similarity_detection_raw

partial_similarity_detection_merged

partial_similarity_detection_final

新功能实现

指定 App 找 Code Clone

设待查找App 名字为 A1
用 pickle 把 MinhashLSH dump 到磁盘。
load MinhashLSH
计算 App 的 Feature Vector, 直接 Query A1 的 Feature Vector,可以获得一组 App {A2, A3 … An }， 再 根据 Jaccard Similarity 从高到低排序输出结果。

指定 App 的某个 Method，寻找类似的 Method

计算 该 Method 的 semantic vector， 在 LSH 中 query 该 semantic vector， 可以得到一个 cluster， 该 cluster 中存储的是一组 semantic_vector_id. 这组 semantic_vector_id 与 某个App的某个Method 一一对应。

关于 Online Detection 模式

????