P2P僵尸网络深度追踪——Mozi（二）二叉树吃瓜记

“由此顺藤摸瓜，很快破获了这起盗窃案。”—— 1982.6.30《人民日报》

PS: 上一篇Mozi系列首发文章评论区惊现预言家，是的，我们来了！

距离Mozi（Mozi僵尸网络）系列首篇文章发布已经过去一周多，截止5月15日，我们探测到148万个历史感染节点，其中有83万个节点来自中国，占比约为56%。
为什么短短二十日就探测到13万新的Mozi节点？是如何探测的呢？
知微实验室采用了多种方法主动探测Mozi节点，现分享我们第一种有趣的方法。本文首先介绍Mozi寄生的P2P网络的底层原理、Mozi的同伙握手机制和节点聚集现象，然后介绍本实验室的原创核心技术“一种针对新型P2P僵尸网络Mozi的渐进式节点主动追踪装置”（高玩可直接移步第二节），最后分析了该方法的优点和不足。知微实验室致力于物联网安全研究，希望与各位安全同行一起交流合作，助力物联网安全。

一、P2P网络底层原理

有别于传统的僵尸网络通信方法，Mozi采用了P2P进行通信与控制，节点进行身份校验，通信流程和通信内容加密，这些措施提高了僵尸网络的隐匿度和顽固程度，极大增加了僵尸网络追踪和清理的难度，迫切需要一种新型的针对P2P型僵尸网络的追踪方法。
由于Mozi寄生于正常的P2P网络之中，因此，从结合了P2P网络底层原理与Mozi特性的关联分析中发现网络追踪新方法是一个合理的研究方向。

1.1 DHT算法与Kademlia协议

Kademlia协议（以下简称Kad）是美国纽约大学的PetarP. Maymounkov和David Mazieres.在2002年发布的一项研究结果《Kademlia: A peerto -peer information system based on the XOR metric》。简单的说，Kad是一种分布式哈希表（DHT）技术，通过独特的以异或算法（XOR）为距离度量基础，建立了一种全新的DHT拓扑结构，大大提高了路由查询速度。
在2005 年5 月著名的BiTtorrent 在4.1.0 版实现基于Kademlia协议的DHT 技术后，很快国内的BitComet 和BitSpirit 也实现了和BitTorrent 兼容的DHT 技术，实现trackerless下载方式。
Kad 现已成为DHT的主流实现方式，Mozi寄生的P2P网络也是基于Kad实现的。

1.2 Kademlia协议

Kademlia算法是一种分布式哈希存储及路由的算法，基于Kad协议实现的P2P网络的每个节点均存放部分资源。此时，需要考虑的问题如下：

a. 如何分配存储内容到各个节点

b. 如何找到存储文件的节点/地址/路径

如何快速高效的进行目标节点的路由，是Kad所解决的一个重要问题。

1.2.1 节点距离

Kademlia网络中数据关键值（Key）、节点ID（NodeID）均用160个bit表示，NodeID是加入网络时随机分配的。Kad协议规定每一个节点维护如下2个信息：

a. 需要存储的资源，资源以<key, value>对的形式存储，可以理解为文件名的哈希值和文件内容

b. 一个路由表，称为“k-bucket”，按Node ID分层，记录有限个数的其他节点的ID、IP地址、端口

在Kad网络中，两个节点之间距离Dinstance并不是依靠物理距离、路由器跳数来衡量的，而是依靠节点ID的异或距离，即：
假定两个节点的ID分别为A、B，则A与B的距离例如：A = 110, B = 111，那么对上面描述的另一种理解方式：如果将整个网络的节点梳理为一个按节点ID排列的二叉树，树最末端的每个叶子便是一个节点。每一个节点的位置都由其 ID 值的最短前缀唯一的确定。由节点组成Kad网络节点树的过程如下：

Step1：先把key（如节点ID）以二进制形式表示，然后从高位到低位依次按Step2~Step3处理。
Step2：二进制的第n位对应二叉树的第n层。
Step3：如果当前位是1，进入右子树，如果是0则进入左子树（认为设定，可以反过来）。
Step4：按照高位到低位处理完后，这个Key值就对应于二叉树上的某个叶子节点。

当我们把所有节点ID都按照上述步骤操作后，这些节点形成一颗二叉树，如图1所示：

图1. 二叉树编码叶子结点

任意一个kad网络中的节点均是上述节点树的一个全路径叶子节点。节点树的高度等于Kad规定的P2P节点ID的bit长度。

1.2.2 节点树拆分

每一个节点都可以从自己的视角来对二叉树进行拆分，把这颗二叉树分解为一系列连续的，不包含自己的子树。最高层的子树，由整颗树不包含自己的树的另一半组成；下一层子树由剩下部分不包含自己的一半组成；依此类推，直到分割完整颗树。
拆分规则是从根节点开始，把不包含自己的子树拆分出来，然后在剩下的子树再拆分不包含自己的下一层子树，以此类推，直到最后只剩下自己。如上图所示，以节点ID为6（110）为视角进行拆分，可以得到3个子树（灰色圆圈）。而以节点101为视角拆分，则可以得到图2的二叉树：

图2. 二叉树拆分左右子树

Kad默认的散列值空间是m=160（散列值有160bit），所以拆分以后的子树最多有160个。而考虑到实际网络中节点个数远远没有2^160个，所以子树的个数明显小于160个。

1.2.3 K-bucket机制

假设每个节点ID是N bits。每个节点按照自己视角拆分完子树后，一共可以得到N个子树。如果分别知道N个子树里的1个节点，那么当前节点就可以利用这N个节点进行递归路由，达到整个二叉树的任何一个子树和节点。并且，维护这N个节点的代价取决于树高。Kademlia默认160的树高相对来说维护代价并不高。
在实际使用过程中，考虑到健壮性（每个节点可能退出或者宕机）问题，只知道一个节点是不够的，需要多几个节点才比较保险。所以，Kad论文提出K-桶（K-bucket）的概念：

每个节点在完成拆分子树以后，要记录每个子树里面K个节点。

这里K是一个系统级常量，由软件系统自己设定（BT下载使用的Kad算法中，K设定为8）。K桶在这里实际上就是路由表。
每个节点按照自己视角拆分完子树后，可以得到N个子树，那么就需要维护N个路由表（对应N个K-桶）。Kad算法中就使用了K-桶的概念来存储其他邻近节点的状态信息，这些信息由 (IP address,UDP port,Node ID) 数据列表构成（Kad 网络是靠 UDP 协议交换信息的）。每一个这样的列表都称之为一个 K 桶，并且每个 K 桶内部信息存放位置是根据上次看到的时间顺序排列，最近（ least-recently）看到的放在头部，最后（most-recently）看到的放在尾部，每个桶都有不超过 K个的数据项，如图3和图4所示。

图3. K桶示意图
图4. K桶链接图

由于每个 K 桶覆盖距离的范围呈指数关系增长，这就形成了离自己近的节点的信息多，离自己远的节点的信息少，从而可以保证路由查询过程是收敛。因为是用指数方式划分区间，经过证明，对于一个有 N 个节点的 Kad 网络，最多只需要经过logN 步查询，就可以准确定位到目标节点。

1.2.4 协议操作

Kademlia 协议包括四种远程 RPC 操作：PING、STORE、FIND_NODE、FIND_VALUE。

a. PING 操作的作用是探测一个节点，用以判断其是否仍然在线；

b. STORE 操作的作用是通知一个节点存储一个 <key,value> 对，以便以后查询需要；

c. FIND_NODE 操作使用一个 160 bit 的 ID 作为参数。本操作的接受者返回它所知道的更接近目标 ID 的 K 个节点的 (IP address, UDP port, Node ID) 信息。这些节点的信息可以是从一个单独的 K 桶获得，也可以从多个 K 桶获得（如果最接近目标 ID 的 K 桶未满）。不管是哪种情况，接受者都将返回 K 个节点的信息给操作发起者。但如果接受者所有 K 桶的节点信息加起来也没有 K 个，则它会返回全部节点的信息给发起者。

d. FIND_VALUE 操作和 FIND_NODE 操作类似，不同的是它只需要返回一个节点的 (IP address, UDP port, Node ID) 信息。如果本操作的接受者收到同一个 key 的 STORE 操作，则会直接返回存储的 value 值。

为了防止伪造地址，在所有 RPC 操作中，接受者都需要响应一个随机的 160 bit 的 ID 值。另外，为了确信发送者的网络地址，PING 操作还可以附带在接受者的 RPC 回复信息中。

1.2.5 递归路由

Kad 技术的最大特点之一就是能够提供快速的节点查找机制，并且还可以通过参数进行查找速度的调节。假如节点 X 要查找节点 Y，Kad 按照如下递归操作步骤进行递归路由查找：

a. 计算X 到 Y的距离：

b. 从 X 的第个 K 桶中取出 α 个节点的信息，同时进行 FIND_NODE 操作。如果这个 K 桶中的信息少于 α 个，则从附近多个桶中选择距离最接近D的总共 α 个节点。

c. 对接受到查询操作的每个节点，如果发现自己就是 Y，则回答自己是最接近Y 的；否则测量自己和 Y的距离，并从自己对应的 K 桶中选择 α 个节点的信息给 X。

d. X对新接收到的每个节点都再次执行 FIND_NODE 操作，此过程不断重复执行，直到每一个分支都有节点响应自己是最接近Y的。

e. 通过上述查找操作，X 得到了 K个最接近Y的节点信息。

这里用“最接近”这个说法，是因为节点Y不一定存在网络中，也就是说Y没有分配给任何一台电脑。这里 α 也是为系统优化而设立的一个参数，就像 K 一样。在 BitTorrent 实现中，取值为 α=3。

1.2.6 总结

读者只需要记住的是，假设节点A向Kad网络中的一个节点C发送查找节点B的Find_node请求：

那么，如果B！= C，A收到C的返回R 为 C的K-bucket路由表中离B最近的α个节点：

我们将C定义为中继路由节点，B为目标节点。

1.3 Mozi特性及节点聚集现象

1.3.1 节点聚集

在我们研究Mozi样本的时候，发现Mozi节点ID的前缀有2种：

a. 样本文件硬编码的888888（0x383838383838）

b. config配置文件中的hp指令所指定的前缀，最常见的88888888（0x3838383838383838）

Mozi节点ID的硬编码前缀的特性，可等价认定Mozi节点在P2P网络某些特定子树下出现了聚集现象：
1621387248_60a467f061e91df409e46.png!small?1621387246901 比如0x383838383838下的节点聚集如图5所示：

图5. 0x383838383838下的节点聚集图

1.3.2 同伙握手机制

Mozi节点在通过正常的P2P通信加入网络后，为了快速区分通信的P2P节点是否同样为Mozi节点，使用1:v4:flag(4 bytes)这样的标识来识别流量是否由其同类节点发出，达到同伙握手识别的目的，如图6所示。

图6. 使用标识识别流量

flag字节含义如下：

\`flag(4 bytes)

- - -

offset:
0 -----random
1 -----hard-code(0x42) or from [ver]
2 -----calc by algorithm
3 -----calc by algorithm\`

二、渐进式路由追踪技术【吃瓜核心技巧】

Mozi节点在特定子树下的聚集，是该项追踪技术的基本点。
追踪特定子树的目标就是尽可能多的获取到这些子树下的节点，然后进行Mozi节点的确认。与漫无目的进行随机节点的Mozi确认方式相比，这种“顺藤摸瓜”式主动探测方式可以很快地揪出潜伏在kad二叉树下的“墨子”，极大的提升了追踪效率。

（感谢Mozi（一）评论区热心网友提供）

2.1 基于中继路由节点的渐进式收敛追踪

现在需要解决的第一个问题就是如何尽可能多的获取特定子树下的节点。此时，就用到了我们在2.2.6节提到的Kad协议的特点：节点在响应find_node请求时会返回自己路由表中离目标节点最近的α个节点。
如果我们以正常P2P节点作为中继路由节点，向其发送目标为特定子树下随机节点的find_node请求，正常P2P节点会将自己路由表中离特定子树随机节点最近的α个节点返回。这α个节点可能直接存在于特定子树中，即使不在特定子树，其离特定子树也相对更近。如果返回的节点不在特定子树中，我们将以此节点为中继路由节点，继续进行路由表数据的获取，如此循环往复。
通过探测正常P2P节点的特定路由表数据，我们可收集到在特定子树下的大量节点。以如图7所示子树为例，我们分析获取到的路由表情况：

图7. 特定子树举例

假设图中红色线圈标出的子树为特定子树（即节点ID前缀固定），E为我们的伪装节点用于发送探测数据，D为我们选择的中继路由节点。
此时，E向D发送find_node请求，目标节点为特定节子树中的随机节点A，公式表达为：
根据我们之前拆分子树的分析，A、B、C节点均可能会出现在D的同一个k桶中，即：
由于K桶长度的限制，E收到的节点中，A、B、C均可能出现，也可能均不出现。节点存在于路由表中的概率与节点的异或距离存在正相关。
即使E只收到了不在特定子树中的C节点，由于D(C, B) < D(E, B)，所以C的路由表中记录特定子树节点的概率会更高，获取特定子树节点的过程是渐进收敛的。
由于获取特定子树节点的过程是收敛的，所以在经过若干次迭代后，探测节点肯定会获取到特定子树下的节点。
这个收敛的过程，输入为（正常的中继路由P2P节点，特定子树下的随机ID），执行者为探测节点，输出为中继路由节点K桶中记录的特定子树下的节点。
需要注意的是，我们利用的是中继路由节点的K-bucket数据，而不是真实存在的特定子树节点，所以我们只需要构造一个随机的特定子树节点ID就可以了。
总结来讲，该技术的核心思路为：通过模仿P2P路由寻址，构造特定子树下的随机节点ID（可能不存在），在P2P网络中搜索正常P2P节点的路由表中特定子树节点（真实存在）的记录。

2.2 目标节点的确认

基于Mozi特有的同伙识别机制，我们向2.1节中获取的大量特定子树下节点发送握手请求，通过1.3.2节展示的同伙握手方法来判定节点是否属于Mozi节点，达到节点身份确认和存活性判断的目的。

2.3 中继路由金字塔数据存储模型

2.1节提出的收敛追踪，需要存活于P2P网络中的正常节点作为中继路由节点。那么，我们最后需要解决的问题是如何收集足够多的中继路由节点。我们能想到的最简单的方法是与一些公开的P2P节点进行通信，从公共节点的响应中获取大量正常节点并循环迭代即可。常见的可用公开P2P节点如下：

dht.transmissionbt.com:6881

router.bittorrent.com:6881

router.utorrent.com:6881

bttracker.debian.org:6881

中继路由节点与特定子树的距离决定了特定节点的挖掘效率。为了加快追踪速度，我们设计一个中继路由金字塔存储模型，基于节点ID的前8个bit对中继路由节点进行分类，探测程序可快速定位距离特定子树较近的中继路由节点。（NodeID、IP、PORT）可唯一标记一个P2P节点。我们取中继路由节点NodeID的前8个bit作为计算单元，与特定子树前缀的前8个bit进行异或计算，异或值决定了中继路由节点在金字塔存储模型中的位置。金字塔存储模型设计如图8所示：

图8. 金字塔存储模型

假设：中继路由节点ID为A，特定子树的前缀ID为B，f为取节点ID前N个bit的函数，那么中继路由节点应该存储的层级L为：
比如：f(A) = 0x36, f(B) = 0x38, f取前8个bit，那么,则中继路由节点的信息（A ，IP of A， Port of A）应该被存入金字塔存储模型的第5层。
金字塔存储模型构建完毕后，每次进行追踪时，优先选取金字塔中的高层节点作为中继路由节点进行探测。同时，如果高层节点数量不足，需要抽取低层节点进行探测以补充高层节点。
在实际使用时，初始化节点可选取上面列出的P2P公共节点，将公共节点首先放入金字塔存储模型，然后展开持续的特定子树探测和金字塔存储数据模型的数据更新工作。
在工程实践中，我们选用MongoDB进行金字塔存储模型数据的存储。数据结构如下：

{
 "_id": "ip:port",
 "access": int, //访问次数，默认0
 "level": int, //层级，1-8
 "latest": int,// 最近访问时间
 "logTime": Date //录入时间，有效期6小时
 }

使用Redis缓存需要入库的节点，编写后台Worker消费Redis数据录入Mongo，完成数据存储。
当需要使用中继路由节点时，通过API按照一定的调度算法从MongoDB获取节点即可。总体数据架构如图9所示：

图9. 总体数据架构示例

三、追踪装置工程设计

3.1 追踪装置逻辑流程

图10. 追踪装置逻辑流程示例

从图10中的蓝色流程可以看到，依靠金字塔数据模型和主动追踪装置，整个追踪流程形成了一个数据闭环，金字塔数据模型不断汇总追踪装置的上报数据，同时又为外部分散的追踪装置提供数据来源。
低层节点拉取模块通过访问金字塔数据接口，获取到离特定子树较远的中继路由节点。此类节点在输入到中继节点探测发包模块后，会输出更高层次即离特定子树更近的中继路由节点。因此，低层节点拉取模块的意义在于能够不断的将更高层次的中继路由节点输入到金字塔数据模型，为高层节点拉取模块输血。
特定节点追踪装置可以在网络中部署若干个，多路并行的追踪装置可以极大提高追踪的效率。

四、一小时统计数据

根据2.3节的金字塔存储模型划分层级1至8，我们统计了一小时内的活跃数据，并抽样100000个中继节点进行探测，根据其中的Mozi节点数量绘制图11。随着层级增加，Mozi节点数量也呈阶梯式增加。

层级	中继节点	Mozi节点	Mozi节点比率
1	100000	467	0.47%
2	100000	10984	10.98%
3	100000	23479	23.48%
4	100000	26548	26.55%
5	100000	65573	65.57%
6	100000	80452	80.45%
7	100000	95412	95.41%
8	100000	99998	99.99%

图11. 一小时抽样数据统计

数据统计能够表明，该渐进式节点主动追踪装置能够快速有效的挖掘潜伏在正常P2P网络中的特殊节点，准确率近乎100%。此外，对于在P2P网络中挖掘特定节点的类似问题，本装置能够起到极大的借鉴作用。

五、优缺点分析

5.1 优点

该方法直接聚焦于特定子树下节点的挖掘，收敛速度快，能在短时间内挖掘到大量的存活节点。同时，对于与Mozi特性类似的特定子树下特定节点的挖掘问题，都可以使用该方法。这也是该方法的最大理论价值。

5.2 缺点

此方法所依赖的P2P特性暂不会发生大的改变，而依赖的Mozi的特性有可能发生变化，比如NodeID的prefix。该方法不能主动感知到实际Mozi节点ID前缀的改变，只能人工指定。所以，为了弥补该缺点，需要使用我们提出的另一种方法实时感知样本prefix，作为本方法的ID prefix输入（下一篇文章将详细介绍此方法）。两种方法共生，相互支持。