基于格式比较的未知协议消息聚类

2023-04-06 43351 words 87 minutes

Contents

原文链接：https://doi.org/10.1016/j.comnet.2020.107296 复现结果：https://github.com/chenzongyao200127/Clustering_of_unknown_protocol_messages_based_on_format_comparison

阅读目的：精读这篇论文，协助师兄复现论文的算法

Abstract

As a solution to detect and analyse unknown or proprietary protocols, Protocol Reverse Engineering(PRE) has been developed swiftly in recent years. In this field, message clustering aimed at protocol format serves as a fundamental solution for differentiating of unknown protocol messages. This paper works on the problem of format-oriented message clustering of unknown protocols, including messages from proprietary or non-cooperative network environments with their specifications unknown. By introducing basic rules of ABNF, we define Token Format Distance (TFD) and Message Format Distance (MFD) to represent format similarity of tokens and messages, and introduce Jaccard Distance and an optimized sequence alignment algorithm (MFD measurement) to compute them. Then, a distance matrix is built by MFD and we feed it to DBSCAN algorithm to cluster unknown protocol messages into classes with different formats. In this process, we design an unsupervised clustering strategy with Silhouette Coefficient and Dunn Index applied to parameter selecting of DBSCAN. In experiment on two datasets, the harmonic average v-measures of homogeneity and completeness on result clusters are both above 0.91, with fmis and coverages no less than 0.97. Together with iqr of v-measure and fmi bellow 0.1 and 0.03 separately in boxplot analyses, this method is proved to have remarkable validity and stability. Comprehensive analyses and comparisons on these indexes also show considerable advantages of our method over previous work.

翻译：

作为一种检测和分析未知或专有协议的解决方案，协议逆向工程（PRE）近年来得到了迅速发展。在这个领域，针对协议格式的消息聚类是区分未知协议消息的基本解决方案。

本文研究未知协议的面向格式的消息聚类问题，包括来自专有或非合作网络环境的未知规范的消息。通过引入ABNF的基本规则，我们定义了Token Format Distance (TFD) 和 Message Format Distance (MFD) 以表示token和消息的格式相似性，并引入Jaccard Distance和优化的序列对齐算法（MFD度量）来计算它们。然后，我们使用MFD构建一个距离矩阵，并将其输入DBSCAN算法，将未知协议消息聚类为具有不同格式的类。在这个过程中，我们设计了一个无监督聚类策略，将轮廓系数和Dunn指数应用于DBSCAN的参数选择。

在对两个数据集的实验中，结果聚类的同质性和完整性的调和平均v-measures均在0.91以上，fmis和覆盖率s均不低于0.97。同时，通过箱线图分析，v-measure和fmi的iqr分别低于0.1和0.03，证明了该方法具有显著的有效性和稳定性。对这些指标的综合分析和比较还表明，我们的方法比以前的工作具有相当的优势。

Backus-Naur Form (ABNF) 规则是什么？

Backus-Naur Form（BNF）是一种用于描述上下文无关文法的表示法，广泛用于描述编程语言、数据格式和通信协议的语法。ABNF（扩展的巴科斯-诺尔范式，Augmented Backus-Naur Form）是BNF的一种扩展，它支持更多的表示方式和更严格的语法规则。ABNF最初在RFC 2234中定义，后来在RFC 5234和RFC 7405中得到更新和扩展。

ABNF由一系列生产式（production）组成，每个生产式定义了一个非终结符（non-terminal）和它可以扩展为的符号序列。每个生产式包含一个左侧的非终结符，一个分隔符（::=），以及一个右侧的符号序列。符号序列可以包含终结符（例如字符或数字字面量）、非终结符（在其他生产式中定义）以及组合符号（例如选择、重复和分组）。

以下是一个简单的ABNF示例，描述了一个由字母和数字组成的标识符：

identifier = letter *(letter / digit)
letter     = %x41-5A / %x61-7A ; A-Z / a-z
digit      = %x30-39 ; 0-9

在这个例子中，我们有三个生产式：

identifier 是主要的非终结符，定义了一个标识符。它以一个 letter 开始，后面可以跟任意数量的 letter 或 digit。
letter 是一个非终结符，表示一个字母。它可以是大写字母（A-Z，表示为 %x41-5A）或小写字母（a-z，表示为 %x61-7A）。
digit 是一个非终结符，表示一个数字。它可以是0-9之间的任意数字（表示为 %x30-39）。

其中，%x 表示十六进制数值，- 表示一个范围，/ 表示选择（或），* 表示重复（跟在括号后面表示重复括号内的元素）。

ABNF广泛用于定义各种标准，例如互联网工程任务组（IETF）的许多RFC文档。

Backus-Naur Form（BNF）及其扩展Augmented Backus-Naur Form（ABNF）是用于表示形式化语法的元语言。形式化语法定义了一种形式语言的结构和规则。BNF和ABNF广泛用于描述编程语言、数据格式和通信协议的语法。它们能够清晰、简洁地表示语法规则，使得人们可以准确理解和实现这些规则。

BNF的创建背景：BNF的历史可以追溯到20世纪50年代，当时计算机科学家John Backus为了描述IBM 704汇编程序的语法而发明了这种表示法。后来，他的同事Peter Naur将这种表示法应用到ALGOL 60编程语言的定义中，并对其进行了改进。因此，这种表示法以这两位科学家的名字命名为Backus-Naur Form。

ABNF的创建背景：虽然BNF非常有用，但它的表示能力有限，对于某些复杂的语法规则可能不够方便和清晰。因此，扩展的巴科斯-诺尔范式（ABNF）应运而生。ABNF在BNF的基础上引入了更丰富的表示手段和更严格的语法规则，使得描述语法更加灵活和精确。ABNF最初在RFC 2234中定义，后来在RFC 5234和RFC 7405中得到更新和扩展。

ABNF的主要用途：

编程语言的定义：ABNF可以用来描述编程语言的语法结构，帮助编译器和解释器开发者理解和实现语言规则。
数据格式的定义：ABNF可以用来描述各种数据格式（如JSON、XML等）的语法规则，方便开发者编写解析器和生成器。
通信协议的定义：ABNF可以用来描述通信协议（如HTTP、SMTP等）的消息格式和语法规则，帮助开发者实现协议的解析和构建。
文档和标准规范：许多技术标准和规范（如IETF的RFC文档）使用ABNF来描述相关技术的语法和格式，确保实现的一致性和互操作性。

总之，BNF和ABNF是描述形式语言语法的强大工具，它们在计算机科学和软件工程领域具有广泛的应用。通过使用这些表示法，开发者可以更轻松地理解、实现和传播复杂的技术规则。

具体的例子

以下是一个使用ABNF规则表示简化版的HTTP/1.1请求消息的例子。这个例子仅包含了基本的组成部分，实际的HTTP/1.1规范要复杂得多。我们将关注请求行（request line）、头部字段（header fields）和CRLF（回车换行）。

; 一个简化版的HTTP/1.1请求消息
http-message = request-line CRLF header-field *CRLF CRLF

; 请求行包括请求方法、请求URI和HTTP版本
request-line = method SP request-uri SP http-version CRLF

; 请求方法
method = "GET" / "POST" / "PUT" / "DELETE" / "HEAD"

; 请求的统一资源标识符（URI）
request-uri = <一个符合URI规范的字符串，例如"/index.html"或"https://example.com/index.html"，此处未进一步定义>

; HTTP版本
http-version = "HTTP/" 1*DIGIT "." 1*DIGIT

; 头部字段包括字段名和字段值
header-field = field-name ":" OWS field-value OWS

; 字段名
field-name = token

; 字段值
field-value = *( field-content / obs-fold )

; 字段内容
field-content = field-vchar / SP / HTAB

; 字段值字符
field-vchar = VCHAR / obs-text

; 可选的空白
OWS = *( SP / HTAB )

; 回车换行
CRLF = CR LF

; 基本的字符定义
SP = %x20          ; 空格符
HTAB = %x09         ; 水平制表符
CR = %x0D           ; 回车符
LF = %x0A           ; 换行符
VCHAR = %x21-7E     ; 可见的US-ASCII字符
token = 1*tchar
tchar = "!" / "#" / "$" / "%" / "&" / "'" / "*" / "+" / "-" / "." / "^" / "_" / "`" / "|" / "~" / DIGIT / ALPHA
obs-text = %x80-FF
obs-fold = CRLF ( SP / HTAB )
DIGIT = %x30-39     ; 数字0-9
ALPHA = %x41-5A / %x61-7A  ; A-Z / a-z

在这个例子中，我们使用了ABNF规则描述了简化版的HTTP/1.1请求消息的基本结构。请注意，这个例子并不涵盖完整的HTTP/1.1规范。在实际应用中，你需要根据具体的协议标准来定义更为详细的ABNF规则。

以下是一个使用ABNF规则表示简化版的JSON（JavaScript Object Notation）数据格式的例子。这个例子仅包含了基本的组成部分，实际的JSON规范要更为详细。我们将关注JSON对象（object）、数组（array）、值（value）、键（key）和字符串（string）。

; 简化版的JSON数据格式
json = object / array

; JSON对象
object = "{" [ key-value-pair *( "," key-value-pair ) ] "}"
key-value-pair = string ":" value

; JSON数组
array = "[" [ value *( "," value ) ] "]"

; JSON值
value = string / number / object / array / "true" / "false" / "null"

; JSON键
key = string

; JSON字符串
string = %x22 *char %x22 ; 字符串由双引号包围

; 字符
char = unescaped / escaped
unescaped = %x20-21 / %x23-5B / %x5D-10FFFF ; 所有不需要转义的Unicode字符
escaped = %x5C ( %x22 / %x5C / %x2F / %x62 / %x66 / %x6E / %x72 / %x74 / %x75 4HEXDIG ) ; 转义字符序列

; 数字
number = [ "-" ] int [ frac ] [ exp ]
int = "0" / ( %x31-39 *DIGIT ) ; 非零数字开头的整数
frac = "." 1*DIGIT
exp = ( "e" / "E" ) [ "+" / "-" ] 1*DIGIT

; 基本的字符定义
DIGIT = %x30-39 ; 数字0-9
HEXDIG = DIGIT / "A" / "B" / "C" / "D" / "E" / "F" ; 十六进制数字

在这个例子中，我们使用了ABNF规则描述了简化版的JSON数据格式的基本结构。请注意，这个例子并不涵盖完整的JSON规范。在实际应用中，你需要根据具体的编程语言标准来定义更为详细的ABNF规则。

1. Introduction

There are numerous private protocols and web services proliferating in the rapid development of internet, bringing much challenge to researchers and network administrators [1], [2], [3]. Inspection on these unknown protocols is attracting increasingly attentions for its applications in network management and intrusion detection [4], [5], [6], and Protocol Reverse Engineering (PRE) has been developed in recent years aiming at the reverse analyzing of those kinds of protocols [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30], [31]. Methods of PRE could be roughly divided into two fields: binary analyzing of unknown protocol implementation [11], [12], [13], [14], [15], [16], [17], [18], [32] and statistic analyzing of unknown protocol traffic [19], [20], [21], [22], [31]. Although techniques based on binary analyzing could usually obtain more sophisticated specification of target protocol by monitoring concrete processing of protocol message data [13], [14], [15], [16], [17], [18], [23], [24], in most network confrontation or administration scenes where binary code of protocols are unavailable (terminal of communication unaccessible), analyzing on unknown protocol message data (net-trace) instead of binary code has to take over this mission on extracting target protocol features or further more protocol message specifications by relative methods in PRE.

翻译：

在互联网的快速发展中，众多私有协议和Web服务的激增给研究人员和网络管理员带来了很大的挑战。对这些未知协议的检查越来越受到关注，因为它在网络管理和[入侵检测]方面具有应用价值。近年来，协议逆向工程（PRE）已经开发出来，旨在对这些协议进行逆向分析。PRE的方法大致可以分为两个领域：未知协议实现的二进制分析和未知协议流量的统计分析。尽管基于二进制分析的技术通常可以通过监测协议消息数据的具体处理获得更复杂的目标协议规范，但在大多数网络对抗或管理场景中，协议的[二进制代码]都是无法获取的（通信终端无法访问），而对未知协议消息数据（网络跟踪）进行分析，而不是二进制代码，必须接管此任务，通过PRE中的相关方法来提取目标协议特征或进一步的协议消息规范。

Main process of net-trace based PRE usually includes clustering of messages, tokenization, keywords or features extraction, and construction of unknown protocol formats [7], [25], [26], [30]. Although sometimes clustering could be executed together with other processes [21] or separately [18], generally speaking, clustering messages into different classes at the very start could greatly facilitate the subsequent analyses, especially format extracting from different messages clusters [20], [22], [27], [28], [29]. Therefore, clustering of messages, especially clustering aimed at protocol formats, is of great importance in process of net-trace based PRE. On this issue, the key points mainly consist in the measurement of message format distance and implementation of cluster algorithm, which are studied intensively in this paper.

翻译：

基于网络跟踪的 PRE 的主要过程通常包括消息聚类、标记化、关键字或特征提取以及未知协议格式的构建。尽管有时聚类可以与其他过程一起执行或单独执行，但总的来说，在最开始将消息聚类到不同的类别中可以大大促进后续分析，特别是从不同消息集群中提取格式。因此，在基于网络跟踪的 PRE 过程中，消息聚类（尤其是针对协议格式的聚类）具有重要意义。在这个问题上，关键点主要在于消息格式距离的度量和聚类算法的实现，这些将在本文中进行深入研究。

这段话中的聚类具体是什么意思？

聚类是一种无监督学习方法，它的目的是将一组数据对象（在这里是消息）组织成多个类别或簇，使得相似的对象属于同一个簇，而不相似的对象属于不同的簇。相似性通常通过一种距离度量来定义，例如欧几里得距离、余弦相似度等。聚类算法试图在没有预先知道类别的情况下发现数据中的结构。

举个例子，假设你有一个电子邮件服务器，上面有大量未分类的电子邮件。你希望对这些电子邮件进行分类，以便了解它们的主题。由于电子邮件的数量非常大，手动分类是不现实的。这时，你可以使用聚类算法。

聚类算法的一个常见例子是 K-means 算法。K-means 的基本思想是将数据分为 K 个簇，每个簇都有一个中心点。算法首先随机选择 K 个初始中心点，然后迭代地执行以下步骤：

将每个数据点分配给距离最近的中心点所在的簇。
根据分配给簇的数据点重新计算簇的中心点。

这个过程会不断重复，直到簇的中心点不再发生显著变化或达到预定的迭代次数。

回到电子邮件的例子，你可以将每封电子邮件表示为一个特征向量（例如，通过计算单词频率），然后使用 K-means 算法将这些向量分组。最后，每个簇将包含一组相似的电子邮件，这些电子邮件可能涉及相似的主题。在原始问题中，聚类用于将网络跟踪中的消息按照其格式进行分组，从而更容易地从不同的消息集群中提取协议格式。这对于理解和分析网络协议非常有帮助。

针对未知协议格式的聚类是指在没有关于网络协议格式的先验知识的情况下，对网络流量数据（如数据包或消息）进行分类和分析。这种方法试图通过分析网络流量的结构和模式，自动地发现和推断未知协议的特征和格式。它对于分析和识别新出现的协议、恶意流量以及混合在已知协议流量中的未知协议流量非常有用。

具体来说，针对未知协议格式的聚类首先需要对网络流量数据进行预处理，例如提取特征（如数据包长度、传输层协议类型等）、标记化（将数据包的内容划分为有意义的单元，如字节、字符串等）等。接下来，使用聚类算法将相似的数据包或消息分组到相同的簇中。每个簇中的数据包可能代表了一个特定的协议或协议的某个特征。

举个例子，假设你捕获了大量网络流量数据，其中包含了多种已知和未知的协议。为了分析这些数据，你可以先对数据包进行预处理，例如提取数据包的长度、首部字段等特征。然后，使用聚类算法（如 K-means 或 DBSCAN）将数据包分组。在这个过程中，相似的数据包会被分到同一个簇中。

通过观察每个簇的特征，你可能会发现某些簇包含了已知协议的数据包，而其他簇可能包含了未知协议的数据包。这时候，你可以进一步分析未知协议簇中的数据包，提取其结构和模式，以便推断出未知协议的格式和特征。这对于理解新出现的协议、识别恶意流量以及优化网络性能等方面非常有价值。

For the first point on measurement of message format distance, traditional distance metrics such as Euclidean distance are not suitable when measuring similarity of message formats. Instead, people introduce other distance measure methods to perform this task by analyzing methods taking protocol communication environment [23], message keywords [21], [28], or message token sequence alignment [21], [23] into consideration. In some certain situations, the first two methods could get relative ideal results with manual help. But when facing totally unknown protocols without any prior knowledge, sequence alignment based message distance method becomes the best (or maybe the last) choice to measure unknown protocol message format similarity automatically. While in our research, we find that sequence alignment based on comparison of token values or types, like people usually do in PRE [21], [23], [27], could not fully represent the distance of message format.Those either too overgeneralized or overspecialized methods definitely limit performance of message format distinction.

翻译：

对于第一点关于消息格式距离的测量，在测量消息格式的相似性时，传统的距离度量如欧氏距离并不适合。相反，人们通过分析考虑协议通信环境、消息关键词或消息标记序列对齐的方法，引入其他距离测量方法来执行这一任务。在某些特定情况下，前两种方法可以在人工帮助下得到相对理想的结果。但是当面对完全未知的协议而没有任何先验知识时，基于序列对齐的消息距离方法成为自动测量未知协议消息格式相似性的最佳（也可能是最后）选择。而在我们的研究中，我们发现基于标记值或类型的比较的序列对齐（sequence alignment based on comparison of token values or types），像人们通常在PRE中做的那样，不能完全代表消息格式的距离。这些过于笼统或过于专业化的方法肯定会限制消息格式区分的性能。

几个概念的简单介绍：

欧氏距离（Euclidean distance）：欧氏距离是一个衡量两点之间距离的度量，通常用于计算两个点在欧几里得空间中的距离。在二维空间中，两点之间的欧氏距离可以用勾股定理求解。对于高维空间，其计算公式为：$d(\mathbf{p}, \mathbf{q}) = \sqrt{\sum_{i=1}^n (p_i - q_i)^2}$，其中 $\mathbf{p}$ 和 $\mathbf{q}$ 是两个 $n$ 维向量。然而，对于消息格式的相似性度量，欧氏距离并不适用，因为消息格式之间的差异可能并不是简单的数值差异。
协议通信环境：协议通信环境是指在通信协议中，消息是如何在发送者和接收者之间传输的。在这个环境中，通信双方需要遵循一定的格式和规则来发送和接收数据。例如，HTTP 协议是基于 TCP/IP 的应用层协议，用于在客户端和服务器之间传输超文本数据。了解协议通信环境有助于我们更好地理解消息格式的相似性。
消息关键词：在通信协议中，消息关键词是用来标识消息内容、类型或功能的特定单词或短语。例如，在HTTP协议中，GET和POST是请求方法的关键词，用于标识请求的类型。通过比较消息中的关键词，我们可以在一定程度上衡量消息格式的相似性。
消息标记序列对齐的方法：这种方法是一种基于序列对齐算法的距离测量方法，主要用于衡量两个消息格式的相似性。序列对齐算法在生物信息学中被广泛应用于比较DNA或蛋白质序列。在计算机网络领域，消息标记序列对齐的方法可以通过比较两个消息中的标记值或类型来计算它们之间的相似性。例如，将消息1的标记序列 “A-B-C” 与消息2的标记序列 “A-D-C” 对齐，我们可以发现它们有两个相同的标记 “A” 和 “C”，从而得到它们之间的相似性。

For the second point on implementation of cluster algorithm, when clustering messages of different protocols in PRE, researchers use various algorithms, such as PAM [18], UPGMA [23], recursive clustering [21], and so on, to cluster protocol messages into classes representing different formats. However, most of those cluster algorithms rely much on manual involvement, like the choice of cluster numbers in PAM [18], generation strategy from phylogenetic trees to clusters in UPGMA [23], and other parameter setting problems.

翻译：

对于第二点关于聚类算法的实现，在PRE中对不同协议的消息进行聚类时，研究人员使用各种算法，如PAM、UPGMA、递归聚类等，将协议消息聚集到代表不同格式的类中。然而，大多数这些聚类算法在很大程度上依赖于人工参与，例如在PAM中选择聚类数量，UPGMA中从系统发育树到聚类的生成策略，以及其他参数设置问题。

In this paper, we make an intensive study on the above-mentioned problems and propose our corresponding solutions. To measure format similarity of unknown protocol messages in a proper granularity, we propose relative measurements, Token Format Distance (TFD) and Message Format Distance (MFD), based on core rules of Augmented Backus-Naur Form (ABNF) [33]. By designing formalized definitions and computing methods of TFD and MFD, we introduce rules of ABNF for the first time to promote reverse analyzing of unknown protocol message format features. To improve automation degree of the clustering process, we introduce two unsupervised cluster quality metrics, Silhouette Coefficient [34] and Dunn Index [35], and design an unsupervised clustering strategy to guide the adjustment of parameters and relieve dependence on artificial assignment. A density-based cluster algorithm DBSCAN [36] is chosen to implement the clustering of messages from unknown protocols.

翻译：

在这篇论文中，我们对上述问题进行了深入研究，并提出了相应的解决方案。为了以适当的粒度测量未知协议消息的格式相似度，我们提出了基于增强巴科斯-诺尔范式（ABNF）[33]核心规则的相对测量，即令牌格式距离（TFD）和消息格式距离（MFD）。通过设计TFD和MFD的正式定义和计算方法，我们首次将ABNF规则引入未知协议消息格式特征的反向分析。为了提高聚类过程的自动化程度，我们引入了两个无监督聚类质量指标，轮廓系数[34]和邓恩指数[35]，并设计了一个无监督聚类策略来指导参数的调整，减轻对人工分配的依赖。我们选择基于密度的聚类算法DBSCAN [36]来实现未知协议的消息聚类。

Contributions of this paper are summarized as follows:

We introduce core rules of ABNF for the first time to measure format similarity of basic message token units, and define it as Token Format Distance (TFD). By designing computation of TFD based on ABNF and Jaccard Index, we make this reverse analysis independent of external assistance. (Section 3.1)
With TFD as computing basis, we define Message Format Distance (MFD) to measure the syntax distance of unknown protocol messages. A dynamic programming algorithm MFD measurement is designed to compute MFD as an optimization of Needleman Wunsch algorithm [37] and Levenshtein Distance [38], thus we make this reverse analysis process concentrated on internal data features. (Section 3.2)
Taking a message distance matrix formed by MFD as input, we design an unsupervised clustering strategy to cluster messages with unknown formats into different classes by DBSCAN algorithm, under the direction of two cluster quality metrics, Silhouette Coefficient and Dunn Index. In this way, manual intervention is decreased greatly in the process of PRE. (Section 3.3)

To present our method, rest of this paper is organized as follows: we discuss the related work in Section 2. Section 3 is the detailed description of our approach. Implementation and evaluations of the proposed method is presented in Section 4. We conclude this paper and discuss future work in Section 5.

翻译：

本文的贡献总结如下：

我们首次引入ABNF的核心规则来测量基本消息令牌单位的格式相似度，并将其定义为令牌格式距离（TFD）。通过基于ABNF和杰卡德指数（Jaccard Index）设计TFD计算，我们使这种反向分析独立于外部辅助。（第3.1节）

以TFD为计算基础，我们定义消息格式距离（MFD）来测量未知协议消息的语法距离。我们设计了一个基于动态规划的MFD测量算法，作为Needleman Wunsch算法[37]和Levenshtein距离[38]的优化，从而使这个反向分析过程集中在内部数据特征上。（第3.2节）

以由MFD形成的消息距离矩阵为输入，我们设计了一个无监督聚类策略，通过DBSCAN算法将未知格式的消息聚类为不同的类别，受到轮廓系数和邓恩指数（Silhouette Coefficient and Dunn Index）两个聚类质量指标的指导。这样，PRE过程中的人工干预大大减少了。（第3.3节）

为了介绍我们的方法，本文的其余部分安排如下：第2节讨论相关工作。第3节详细描述了我们的方法。第4节介绍了所提方法的实现和评估。我们在第5节总结本文并讨论未来工作。

To deal with the identification and classification of traffic generated by unknown protocols, PRE researchers have made some attempts on reverse analyzing unknown protocols by statistic analyzing when only protocol data is accessible [20], [21], [22], [27], [28], [29]. Generally speaking, present methods used to distinguish unknown protocol messages in PRE could be divided into three types: message format-oriented [21], [22], [23], [27], protocol automata state oriented [18], [28] and semantic template oriented [20], [29].

翻译：

为了处理未知协议产生的流量的识别和分类问题，PRE研究人员在仅能访问协议数据时，通过统计分析对未知协议进行了一些尝试。一般来说，目前用于区分PRE中未知协议消息的方法可以分为三种类型：消息格式为导向]，协议自动机状态为导向，以及语义模板为导向。

The first type is the most commonly used method in PRE. Researchers usually adopt format identifiers/keywords or sequence alignment methods to measure message similarity in aspect of format, and then classify message format clusters in combination with cluster algorithms.

翻译：

第一种类型是PRE中最常用的方法。研究人员通常采用格式标识符/关键字或序列对齐方法来衡量格式方面的消息相似性，然后结合聚类算法对消息格式聚类进行分类。

As a typical sequence alignment algorithm, Needleman Wunsch (NW) algorithm [37] is early used in many PRE works like RolePlayer [27] and Discover [21] to align messages and data stream. In Discover [21], messages are tokenized into binary and text classes, and a coarse-grained initial clustering based on NW algorithm is used to align message token patterns, followed by a fine-grained recursive clustering based on format distinguishers identified by artificial defined property and semantics. As a pioneering research work on message format analysis in PRE, Discover expands this area and has much influence on later works [22], [23].

翻译：

作为典型的序列对齐算法，Needleman Wunsch（NW）算法很早就被用于许多PRE成果，如RolePlayer和Discover，以对齐消息和数据流。在Discover中，消息被划分为二进制和文本类别，基于NW算法的粗粒度初始聚类用于对齐消息令牌模式，然后基于人工定义的属性和语义识别的格式区分器进行细粒度递归聚类。作为PRE领域关于消息格式分析的开创性研究工作，Discover拓展了这个领域并对后来的研究产生了很大影响。

这段文字中提到了三个与序列对齐和模式识别相关的算法：Needleman-Wunsch (NW) 算法、RolePlayer 和 Discover。下面分别对这三个算法进行介绍。

Needleman-Wunsch (NW) 算法：这是一种典型的序列对齐算法，用于寻找两个序列之间的最佳全局对齐。它通过动态规划算法来生成一个得分矩阵，用于衡量两个序列的相似度。NW算法的核心思想是通过遍历两个序列，计算它们之间的匹配和不匹配得分，以找到最优的对齐方式。

使用背景：在生物信息学、自然语言处理和模式识别等领域，NW算法被广泛应用于分析和比较序列数据。
RolePlayer：这是一个用于PRE（Pattern Recognition Engine，模式识别引擎）的工作的算法。RolePlayer利用NW算法对数据流和消息进行序列对齐，以识别序列中的特定模式。尽管这段文字没有提供更多关于RolePlayer的详细信息，但我们可以推测，它可能是一种基于序列对齐的模式识别方法。

使用背景：RolePlayer可能用于数据挖掘、网络安全和通信等领域，对数据流和消息进行模式识别和分类。
Discover：这是一种用于PRE的消息格式分析算法。Discover首先将消息划分为二进制和文本类别，并使用基于NW算法的粗粒度初始聚类对消息标记模式进行对齐。接下来，它使用基于人工定义的属性和语义识别的格式区分器进行细粒度的递归聚类。

使用背景：Discover是一项关于PRE消息格式分析的开创性研究工作，对后续相关工作产生了很大影响。Discover可能应用于消息传输、数据挖掘和网络安全等领域，对数据流和消息进行格式分析和识别。

这段文字介绍了三个与序列对齐和模式识别相关的算法：Needleman-Wunsch (NW) 算法、RolePlayer 和 Discover。这些算法在数据挖掘、网络安全和通信等领域具有广泛的应用前景，用于分析和识别序列数据和消息格式。

In [23], Netzob uses semantic information and contextual data collected from control or monitor of protocol implementations, or manually specified contextual information to cluster unknown protocol messages based on an extension of NW algorithm. With the facilitate of protocol implementation and manual intervention, Netzob outperforms several state-of-the-art message cluster and field boundary identification methods [20], [21]. Lately in [22], messages are clustered by an agglomerative hierarchical clustering algorithm with complete linkage clustering criteria [39] based on Jaccard similarity coefficient [40] of n-gram frequency distributions, before packet structure extraction based on a segment-based multiple sequence alignment implementation Dialign-2 [41], [42].

翻译：

在文献[23]中，Netzob 使用从协议实现的控制或监控中收集的语义信息和上下文数据，或手动指定的上下文信息，基于 NW 算法的扩展对未知协议消息进行聚类。在协议实现和人工干预的帮助下，Netzob 超越了几种最先进的消息聚类和字段边界识别方法[20]，[21]。最近在文献[22]中，在基于 Dialign-2 的段落为基础的多序列对齐实现之前，消息通过一种基于 Jaccard 相似性系数[40]的 n-gram 频率分布的凝聚层次聚类算法进行聚类，其中采用了完全链接聚类准则[39]。

凝聚层次聚类算法：这是一种自底向上的聚类方法，其中数据点最初被视为单独的簇，然后通过迭代地合并最接近的簇来构建层次结构。在这里，采用了完全链接聚类准则，它计算簇间所有数据点对之间的距离，并以最大距离作为簇间距离。聚类过程基于 Jaccard 相似性系数，这是一种衡量集合相似性的指标，用于计算 n-gram 频率分布之间的相似性。

Jaccard similarity coefficient

在引文中，Jaccard 相似性系数（Jaccard similarity coefficient）是一种用于衡量两个集合之间相似度的指标。Jaccard 系数的定义如下：

Jaccard(A, B) = (A ∩ B) / (A ∪ B)

其中，A 和 B 分别表示两个集合，A ∩ B 表示集合 A 和 B 的交集元素数量，A ∪ B 表示集合 A 和 B 的并集元素数量。Jaccard 系数的值在 0 和 1 之间，其中 0 表示两个集合完全不相似，1 表示两个集合完全相同。

在给定的文章段落中，Jaccard 相似性系数被用于衡量 n-gram 频率分布之间的相似性。n-gram 是一种将文本或序列划分为 n 个连续字符的方法。通过计算两个 n-gram 频率分布之间的 Jaccard 系数，可以得到它们之间的相似性。

下面是一个简单的示例：

假设我们有两个字符串：

A = "abcdefg"
B = "bcdefgh"

我们可以将这两个字符串划分为 2-gram（即，n = 2）：

A 的 2-grams: {ab, bc, cd, de, ef, fg}
B 的 2-grams: {bc, cd, de, ef, fg, gh}

计算 Jaccard 系数：

交集 (A ∩ B) = {bc, cd, de, ef, fg}，数量为 5
并集 (A ∪ B) = {ab, bc, cd, de, ef, fg, gh}，数量为 7

Jaccard(A, B) = 5 / 7 ≈ 0.71

在这个例子中，两个字符串的 Jaccard 相似性系数为 0.71，表示它们具有较高的相似性。

Researches on second type usually have similar procedure of protocol automata reverse including message classification, state type labeling and state machine inferring. In Prospex [18] and Veritas [28], messages are clustered using Partitioning Around Medoids(PAM) algorithm based on message features similarity measured by Jaccard Index [43] before further building protocol state machine. These message features are obtained from binary analysis and system configuration in Prospex, and represented by frequency subsequences which are ascertained by K-S test in Veritas, respectively.

翻译：

第二种类型的研究通常有类似的协议自动机逆向程序，包括消息分类、状态类型标记和状态机推断。在Prospex[18]和Veritas[28]中，在进一步建立协议状态机之前，使用Partitioning Around Medoids(PAM)算法根据Jaccard Index[43]测量的消息特征相似度对消息进行聚类。这些消息特征在Prospex中是通过二进制分析和系统配置获得的，在Veritas中则是通过K-S测试确定的频率子序列表示。

The last type including [20] and [29] is minority work on protocol message semantic analysis. Krueger et al developed ASAP in [20]. By constructing an alphabet of tokens derived by delimiters and n-gram, ASAP maps message payloads to vectors, and use matrix factorization to identify base directions and coordinate tuples. These coordinate tuples are remapped to semantical representation of messages by a greedy algorithm to concatenate n-grams into message semantic templates. As an extension of ASAP, PRISMA [29] uses a similar method of matrix factorization to map messages into events, and further inferences a state machine represented by Markov Model to stand for the grammar of target protocol.

翻译：

最后一类包括[20]和[29]是少数人的协议消息语义分析工作。Krueger等人在[20]中开发了ASAP。通过构建一个由分隔符和n-gram衍生的标记字母表，ASAP将消息有效载荷映射为向量，并使用矩阵分解来识别基本方向和坐标图元。这些坐标图元通过一个贪心的算法被重新映射为消息的语义表示，将n-grams连接成消息语义模板。作为ASAP的扩展，PRISMA[29]使用类似的矩阵分解方法将消息映射为事件，并进一步推断由马尔可夫模型代表的状态机，以代表目标协议的语法。

To sum up, clustering based on NW algorithm is the most commonly used method to classify unknown protocol messages with different formats, but there are still some deficiencies remain: dependence on external assistance, less consideration of format, and parameter selection of cluster algorithm. Firstly, methods in [21], [22], [23], [27] have much dependence on artificial participation as well as system or environment information, such as recognition of format distinguishers in [21] and contextual information needed in [23], and this weakens the ability of PRE in non-cooperate condition. Secondly, the NW algorithm applied in these researches is usually based on the comparison of token values, but the similarity of token format is less considered, and this limits the performance of message format differentiating. The type-based NW algorithm in [21] and contextual semantic information based extension of it in [23] could be regarded as initial attempts on grammar oriented extension version, which deserves more study. Lastly, cluster algorithms used in former researches usually have the problem of parameter selection, which greatly reduce the automation of PRE. As for the latter two types of message clustering we discuss above, there are no theoretical proves of mapping relationships between automata state type or message semantic and message format type so far so good, therefore, essentially speaking, methods of latter two types are not suitable for message format clustering in PRE.

翻译：

总之，基于 NW 算法的聚类是将具有不同格式的未知协议消息进行分类的最常用方法，但仍然存在一些不足：依赖外部辅助、格式考虑不足和聚类算法的参数选择。首先，[21]、[22]、[23]、[27] 等方法在很大程度上依赖人工参与以及系统或环境信息，例如 [21] 中的格式区分符识别和 [23] 中所需的上下文信息，这削弱了非合作条件下 PRE 的能力。其次，这些研究中应用的 NW 算法通常是基于令牌值的比较，但很少考虑令牌格式的相似性，这限制了消息格式区分的性能。[21] 中的基于类型的 NW 算法以及 [23] 中基于上下文语义信息的扩展可以看作是面向语法扩展版本的初步尝试，值得进一步研究。最后，前述研究中使用的聚类算法通常存在参数选择问题，这大大降低了 PRE 的自动化程度。

至于我们上面讨论的后两种类型的消息聚类，迄今为止，并没有关于自动机状态类型或消息语义与消息格式类型之间映射关系的理论证明，因此，从本质上讲，后两种方法不适用于 PRE 中的消息格式聚类。

在这段话中，作者提到了基于 Needleman-Wunsch (NW) 算法的聚类方法在处理未知协议消息分类时的一些不足之处和相关研究。首先，我们需要了解 NW 算法是一种序列对齐算法，通常用于生物信息学中的 DNA 序列和蛋白质序列对齐。在这里，NW 算法被用于对未知协议消息进行分类。

这段话提到的具体例子如下：

文献 [21]：这篇研究中，NW 算法用于识别协议消息中的格式区分符。然而，这项方法在很大程度上依赖人工参与和系统或环境信息。这种依赖性削弱了在非合作条件下协议逆向工程（PRE）的能力。简言之，为了使这种方法有效，你需要对系统或环境有足够的了解，而这通常难以实现。
文献 [23]：这篇研究中，NW 算法被扩展为基于上下文语义信息。然而，这种方法同样需要大量的上下文信息，这在实际应用中可能难以获得。这同样削弱了 PRE 的能力。
NW 算法的局限性：在这些研究中使用的 NW 算法通常是基于令牌值的比较，但很少考虑令牌格式的相似性。这限制了消息格式区分的性能。文献 [21] 中基于类型的 NW 算法和文献 [23] 中基于上下文语义信息的扩展可以看作是面向语法扩展版本的初步尝试，值得进一步研究。
聚类算法参数选择问题：在前述研究中使用的聚类算法通常存在参数选择问题。这意味着为了获得有效的结果，需要手动选择适当的参数，这大大降低了 PRE 的自动化程度。

总之，这段文字讨论了基于 NW 算法的聚类方法在处理未知协议消息分类时的一些不足之处，并提到了一些具体的研究例子（如文献 [21] 和 [23]）。这些不足包括对外部辅助的依赖、格式考虑不足和聚类算法参数选择问题。

非合作条件下协议逆向工程（PRE）

非合作条件下协议逆向工程（PRE）是指在对通信协议进行逆向分析时，分析者无法获得协议设计者的直接帮助或协议相关的文档和源代码。在这种情况下，分析者需要通过观察协议的实际通信行为、分析网络流量和捕获的数据包等手段来推断协议的工作原理和结构。这种分析通常比较困难，因为分析者需要在缺乏直接信息的情况下理解协议的细节。

非合作条件下 PRE 的挑战包括：

缺乏关于协议设计、实现和运行环境的详细信息。
很难直接获取协议的源代码或文档。
需要通过分析网络流量和捕获的数据包来推测协议的工作原理。

在上文提到的 NW 算法在处理未知协议消息分类时的不足之处中，依赖外部辅助（如人工参与和系统或环境信息）会削弱非合作条件下 PRE 的能力，因为这些外部辅助很难在实际应用中获得。因此，寻求更加自动化和独立的方法来处理协议逆向工程问题是研究的重要方向。

Contributions of this paper solves these problems in three ways. Format attribute similarity is extracted from message internal content by TFD (Section 3.1) integrating grammar information in token comparison without any environment knowledge, thus relieves the external dependence. Based on TFD, we define MFD (Section 3.2) and develop another extension of NW algorithm from a novel perspective of syntax similarity to measure message distance, and in this way, the comparison of messages is concentrated on format. By introducing cluster quality metrics to direct the tuning of parameters, we design an unsupervised clustering strategy to separate unknown protocol messages by a density based cluster algorithm (Section 3.3), so to solve the parameter selection problem. Concrete work of this paper is explained in Section 3.

翻译：

本文的贡献通过三种方式解决了这些问题。通过 TFD（第 3.1 节）从消息内部内容中提取格式属性相似性，整合令牌比较中的语法信息，无需任何环境知识，从而减轻了外部依赖。

基于 TFD，我们定义了 MFD（第 3.2 节），并从语法相似性的新颖角度开发了 NW 算法的另一个扩展，以衡量消息距离，这样，消息的比较就集中在格式上。

通过引入聚类质量指标指导参数的调整，我们设计了一种基于密度的聚类算法（第 3.3 节）分离未知协议消息的无监督聚类策略，以解决参数选择问题。本文的具体工作详见第 3 节。

3. Unsupervised clustering based on format similarity

As introduced in Section 1, work of this paper contains mainly three processes: definition and computing of Token Format Distance(TFD), define and measurement of Message Format Distance (MFD), and unsupervised clustering strategy based on MFD, as shown in Fig. 1.

Fig. 1. Structure of this paper.

First of all, payloads of hybrid unknown protocol packages are extracted as target of our work to be clustered. For each message without any analysis, data inside is separated into tokens of bytes with possible attributes attached based on ABNF [33]. Based on the attribute sets of tokens, we use Jaccard Index [44] to represent the similarity of tokens in different message, i.e. TFD (Section 3.1).

Then, based on TFD, we define MFD in Section 3.2 to measure message similarity in aspect of syntax and an optimized message token sequence alignment algorithm is designed based on NW algorithm and LD algorithm.

With the distance matrix built in last step by MFD as input, we design an unsupervised clustering strategy in Section 3.3 to divide messages into classes following different formats with the application of DBSCAN algorithm [36].

翻译：

首先，我们提取混合未知协议数据包的有效负载作为目标进行聚类。对于每个未经分析的消息，我们根据 ABNF（巴科斯-诺尔范式） [33] 将数据内部划分为带有可能属性的字节标记。基于标记的属性集，我们使用 Jaccard 指数 [44] 来表示不同消息中标记的相似性，即 TFD（第 3.1 节）。

然后，基于 TFD，我们在第 3.2 节中定义 MFD 以测量语法方面的消息相似性，并基于 NW 算法和 LD（莱文斯坦距离）算法设计了一种优化的消息标记序列对齐算法。

借助上一步使用 MFD 构建的距离矩阵作为输入，我们在第 3.3 节设计了一种无监督聚类策略，采用 DBSCAN 算法 [36] 将遵循不同格式的消息划分为不同类。

读完了3.3好像没有具体讲无监督聚类策略，只是列了两个判断聚类效果的指标😅

3.1. Token format distance measurement

Generally speaking, when reverse analyzing formats of unknown protocols, the differentiating problem of messages comes down to the measurement of tokens that make up messages. In existing works, tokenization is usually realized by n-gram [20], [22], [28], or data type (binary or text) [21]. The former tokenization was introduced from natural language process in the first place, and the later method is assigned manually. In [23], as the basic semantic unit, each half-byte is attached by a multiset of semantic tags come from monitoring of environment or manually assign, and then these units are compared according to a self-defined similarity function.

翻译：

一般来说，在对未知协议的格式进行逆向分析时，消息的区分问题归结为对组成消息的标记（tokens）的度量。在现有的工作中，标记化（tokenization）通常是通过 n-gram [20]，[22]，[28] 或数据类型（二进制或文本）[21]来实现的。前者的标记化最初是从自然语言处理中引入的，后者是手动分配的。在 [23] 中，作为基本语义单位，每个半字节都附加有一个从环境监控或手动分配的语义标签的多重集合，然后根据自定义的相似性函数比较这些单位。

标记化问题是指将复杂的数据结构（如网络通信协议的消息）分解为更小、更易于处理的基本单位（如标记或tokens）的过程。这些基本单位可以用来表示数据的组成部分，从而帮助研究人员或算法更好地理解和分析数据。在网络通信协议的逆向分析中，标记化是关键步骤，因为它有助于揭示协议的底层结构和规则。

In this paper, we trace the tokenization problem back to the basic official definition of network communication protocols, RFC documents [33], [45], and partition protocol messages into tokens by byte, which is used to define core rules of protocols as basic units. Those core rules of message format minimum unit form a series of value sets indicating different value types when forming combined grammatical units.

翻译：

在本文中，我们将标记化问题追溯到网络通信协议的基本官方定义，即 RFC 文档 [33]，[45]，并将协议消息按字节划分为标记，这些标记用于定义协议的核心规则作为基本单位。消息格式最小单位的这些核心规则形成一系列值集，表示在形成组合语法单位时的不同值类型。

For values of different offsets in diverse messages from unknown protocols, they could be recognized as varied grammar elements, and their attributes would become explicit after context grammar inference. While at the first beginning of protocol reverse engineering, source material that could be used as basis of clustering of message format, is remained to be those core rules of ABNF [33] grammar of each unknown protocols. Although in fact, there could be private protocols abandon this basic rules of protocol grammar, or even use other coding scheme other than ASCII, we believe this kind of protocols are seldom exist and reverse analyzing of them should be totally redesigned specifically.

翻译：

对于来自未知协议的不同消息中不同偏移量的值，它们可以被识别为不同的语法元素，而在上下文语法推断之后，它们的属性将变得明确。

然而，在协议逆向工程的最初阶段，可以用作消息格式聚类基础的原始材料，仍然是每个未知协议的 ABNF [33] 语法的核心规则。

尽管实际上可能存在放弃协议语法基本规则的私有协议，甚至使用其他编码方案而非 ASCII，但我们认为这类协议很少存在，且对它们的逆向分析应该完全重新特别设计。

We rearrange these core rules defined in [33] into mappings of attributes and value sets as in Table 1.

Table 1. Core rules of ABNF.

Attribute	Value Set	Explanation
CR	0x0D	carriage return （回车）
LF	0x0A	linefeed（换行）
HTAB	0x09	horizontal tab（制表符）
SP	0x20	space
DQUOTE	0x22	double quote
ALPHA	0x41-0x5A, 0x61-0x7A	A-Z, a-z
CHAR	0x01-0x7F	any 7-bit US-ASCII character
CTL	0x00-0x1F	controls（控制符）
DIGIT	0x30-0x39	0–9
HEXDIG	0x30-0x39, 0x41-0x46	digit and A-F
OCTET	0x00-0xFF	8 bits of data
VCHAR	0x21-0x7E	visible (printing) characters（可见字符）

In this case, the format similarity of values from different messages is transformed to the measurement of attribute sets these two values might possess. As researchers usually do in [18], [22], Jaccard Distance (JD) based on Jaccard Index (JI) is applied to compute the token distances. Some notations and arrangements are given here in advance.

As the message clustering process is usually a step before more intricate analysis on unknown protocols, such as partition of message fields, we define message tokens to be successive bytes and assign them the attributes (Eq. (1)) they might process (Table 1) as elements of fields they belong to.

翻译：

在这种情况下，来自不同消息的值的格式相似性被转化为这两个值可能具有的属性集的度量。正如研究人员通常在[18]、[22]中所做的那样，基于Jaccard指数（JI）的Jaccard距离（JD）被用来计算标记之间的距离。这里提前给出了一些符号和安排。

由于消息聚类过程通常是在对未知协议进行更复杂分析之前的步骤，例如消息字段的划分，我们将消息标记定义为连续字节，并为它们分配属性（等式（1）），作为它们所属字段的元素（表1）。

For two tokens $m$ and $n$, their format element attribute sets are: $A_{m} = {a_1, a_2, …}$ and $A_{n} = {a_1, a_2, …}$ where $a_i ∈ Attr$.

Take part of an HTTP message for demonstration as shown in Table 2. According to core rules of ABNF, the first byte ‘P’ with hexadecimal 0x50 will be assigned with attributes ALPHA, CHAR, OCTET, VCHAR, which has the same attributes with other subsequent characters in same field like ‘O’, ‘S’, ‘T’, and ‘H’, ‘T’, ‘P’ in next text field. Marker symbols such as ‘ ’, ‘/’, ‘\r’, and ‘\n’ have partial similar attributes. In this way, original data bytes are labeled by different attribute sets, through which their syntax similarity could be measured. These labels might seem to be a little bit complicated at first sight. But when we are facing a totally unknown protocol and no knowledge of it is available, analyzing data attribute from the very basic elements becomes a relative basic and reliable idea.

翻译：

对于两个标记$m$和$n$，它们的格式元素属性集分别为：$A_{m} = {a_1, a_2, …}$ 和 $A_{n} = {a_1, a_2, …}$，其中 $a_i ∈ Attr$。

以表2中展示的HTTP消息的一部分为例。根据ABNF的核心规则，第一个字节’P’（十六进制0x50）将被赋予属性ALPHA、CHAR、OCTET、VCHAR，这与同一字段中的其他后续字符（如’O’、‘S’、‘T’）以及下一个文本字段中的’H’、‘T’、‘P'具有相同的属性。标记符号如' ’、‘/’、‘\r'和'\n'具有部分相似的属性。通过这种方式，原始数据字节被不同的属性集标记，通过这些标记可以衡量它们的语法相似性。这些标签乍一看可能有点复杂。但是，当我们面临一个完全未知的协议且没有可用的知识时，从最基本的元素分析数据属性成为一个相对基本且可靠的想法。

Table 2. Example HTTP message token attributes.

content	hex	attribute
P	50	{ALPHA, CHAR, OCTET, VCHAR}
O	4F	{ALPHA, CHAR, OCTET, VCHAR}
S	53	{ALPHA, CHAR, OCTET, VCHAR}
T	54	{ALPHA, CHAR, OCTET, VCHAR}
	20	{SP, CHAR, OCTET}
/	2F	{CHAR, OCTET, VCHAR}
a	61	{ALPHA, CHAR, OCTET, VCHAR}
	20	{SP, CHAR, OCTET}
H	48	{ALPHA, CHAR, OCTET, VCHAR}
T	54	{ALPHA, CHAR, OCTET, VCHAR}
T	54	{ALPHA, CHAR, OCTET, VCHAR}
P	50	{ALPHA, CHAR, OCTET, VCHAR}
/	2F	{CHAR, OCTET, VCHAR}
1	31	{CHAR, DIGIT, HEXDIG, OCTET, VCHAR}
.	2E	{CHAR, OCTET, VCHAR}
1	31	{CHAR, DIGIT, HEXDIG, OCTET, VCHAR}
\r	0D	{CTL, CR, CHAR, OCTET}
\n	0A	{CTL, LF, CHAR, OCTET}

To measure the similarity of attribute sets attached to message tokens, we ues Jaccard Index and corresponding Jaccard Distance to represent relative syntax attribute similarity and difference.

翻译：

为了衡量附加在信息标记上的属性集的相似性，我们使用Jaccard指数和相应的Jaccard距离来表示相对语法属性的相似性和差异。

As shown in Fig. 2, we assign four sets of attributes: $A_{11}, A_{10}, A_{01}, A_{00}$:

where A11 stands for the intersection of two token attribute set i.e. set of attributes both m and n have. Union of A10, A01, A11 indicates all attributes that Am and An cover.

Fig. 2. Attribute sets of token m and n.

Thereupon, JI and JD could be defined by Eqs. (6) and (7).

In this way, the TFD represented by Jaccard Index of token m and n, $TFD(m,n) = D_J (m,n)$ could be used to measure their syntax difference, which will be used to make up corresponding message distance. This is explained in Section 3.2. Fig. 3 shows an demonstration of token compare of two HTTP message, together with relative token syntax labeling. Color depth of those cells stands for relative token distance. The darker of one cell, the corresponding tokens have more syntax similarity.

翻译：

通过这种方式，由标记m和n的Jaccard指数表示的TFD，$TFD(m,n) = D_J (m,n)$ 可用于衡量它们的语法差异，这将用于构成相应的消息距离。这在第3.2节中有解释。

图3展示了两个HTTP消息的标记比较，以及相关的标记语法标记。这些单元格的颜色深度代表相对的标记距离。一个单元格越暗，对应的标记在语法上越相似。

Fig. 3. Token Format Distance of two example HTTP messages.

实现消息字节生成属性集的算法:

根据给出的属性表，我们可以编写一个函数来为给定的消息字节生成属性集。以下是一个可能的实现：

def get_attributes(byte):
    attributes = set()
    
    if byte == 0x0D:
        attributes.add("CR")
    if byte == 0x0A:
        attributes.add("LF")
    if byte == 0x09:
        attributes.add("HTAB")
    if byte == 0x20:
        attributes.add("SP")
    if byte == 0x22:
        attributes.add("DQUOTE")
    if 0x41 <= byte <= 0x5A or 0x61 <= byte <= 0x7A:
        attributes.add("ALPHA")
    if 0x01 <= byte <= 0x7F:
        attributes.add("CHAR")
    if 0x00 <= byte <= 0x1F:
        attributes.add("CTL")
    if 0x30 <= byte <= 0x39:
        attributes.add("DIGIT")
    if 0x30 <= byte <= 0x39 or 0x41 <= byte <= 0x46:
        attributes.add("HEXDIG")
    if 0x00 <= byte <= 0xFF:
        attributes.add("OCTET")
    if 0x21 <= byte <= 0x7E:
        attributes.add("VCHAR")
    
    return attributes

def generate_attribute_sets(message):
    attribute_sets = []
    for byte in message:
        attributes = get_attributes(byte)
        attribute_sets.append(attributes)
    return attribute_sets

get_attributes函数接受一个字节值（0-255之间的整数）并返回一个与该字节关联的属性集。

generate_attribute_sets函数接受一个消息（作为字节值列表）并使用get_attributes函数为每个字节生成一个属性集。然后返回一个包含属性集的列表。

计算任意两个字节之间的TFD：

def token_format_distance(set1, set2):
    return 1 - len(set1.intersection(set2)) / len(set1.union(set2))

def calculate_tfd_matrix(message1_attribute_sets, message2_attribute_sets):
    tfd_matrix = [[0 for _ in range(len(message2_attribute_sets))] for _ in range(len(message1_attribute_sets))]
    
    for i, set1 in enumerate(message1_attribute_sets):
        for j, set2 in enumerate(message2_attribute_sets):
            tfd_matrix[i][j] = token_format_distance(set1, set2)
    
    return tfd_matrix

def print_tfd_matrix(tfd_matrix):
    print("Token Format Distance Matrix:")
    for row in tfd_matrix:
        print([round(x, 2) for x in row])

message1 = [0x50, 0x4F, 0x53, 0x54, 0x20, 0x2F, 0x20, 0x48, 0x54, 0x54, 0x50]
message2 = [0x47, 0x45, 0x54, 0x20, 0x2F, 0x20, 0x48, 0x54, 0x54, 0x50]

message1_attribute_sets = generate_attribute_sets(message1)
message2_attribute_sets = generate_attribute_sets(message2)

tfd_matrix = calculate_tfd_matrix(message1_attribute_sets, message2_attribute_sets)
print_tfd_matrix(tfd_matrix)

这个版本的代码首先使用calculate_tfd_matrix函数计算两个消息之间任意两个字节的TFD矩阵。然后使用print_tfd_matrix函数以易于阅读的格式打印TFD矩阵。

3.2. Message format distance measurement

Sequence alignment algorithms like NW algorithm [37] have been used in PRE to find message structure or measure sequence similarity [21], [22], [27]. In NW algorithm, a greedy strategy is applied based on the comparison of elements with 0/1 values. In this paper, we redefine the similarity of basic elements to be tokens with different syntax attributes, thus token similarity is optimized to be a variable ranged in [0, 1]. Correspondingly, taking the text similarity measurement Levenshtein Distance (LD) Algorithm i.e. edit distance [38] widely used in NLP (Natural Language Processing) as reference, we define MFD based on TFD introduced in Section 3.1 to measure the distance of messages from the point of syntax.

The basic LD algorithm is used to measure the edit distance by matching elements. Its compute process could be expressed as follows:

翻译：

像NW算法[37]这样的序列比对算法已经被用于PRE中寻找消息结构或测量序列相似性[21]，[22]，[27]。在NW算法中，采用了一种基于0/1值元素比较的贪婪策略。

在本文中，我们将基本元素的相似性重新定义为具有不同语法属性的标记（tokens with different syntax attributes），因此标记相似性被优化为一个范围在[0，1]之间的变量。相应地，以广泛应用于NLP（自然语言处理）的文本相似性度量Levenshtein距离（LD）算法，即编辑距离[38]为参考，我们基于第3.1节中介绍的TFD定义MFD，以从语法角度测量消息之间的距离。

基本的LD算法用于通过匹配元素来测量编辑距离。其计算过程可表示如下：

1. For j = 0 or i = 0, d[i][0] = i; d[0][j] = j;
2. if str1[i] == str2[j], then temp = 0, else temp = 1;
3. d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + temp)

这段伪代码是实现Levenshtein距离（LD）算法的核心部分。Levenshtein距离（也称为编辑距离）是一种用于测量两个字符串之间差异的度量，通过计算将一个字符串转换为另一个字符串所需的最少单字符编辑操作（插入、删除或替换）的数量。这里的伪代码描述了计算两个字符串str1和str2之间的Levenshtein距离的动态规划方法。

以下是伪代码的解释：

初始化动态规划矩阵d的边界条件。当i = 0时，d[i][0] = i表示将str1的前i个字符变为空字符串需要的操作次数。同样地，当j = 0时，d[0][j] = j表示将str2的前j个字符变为空字符串需要的操作次数。
对于str1的第i个字符和str2的第j个字符，如果它们相等，则temp = 0（不需要进行替换操作）；否则，temp = 1（需要进行替换操作）。
计算d[i][j]的值，这是将str1的前i个字符转换为str2的前j个字符所需的最少操作次数。为此，我们选择以下三个值中的最小值：
- d[i-1][j] + 1：将str1的前i-1个字符转换为str2的前j个字符所需的操作次数，再加上1次删除操作。
- d[i][j-1] + 1：将str1的前i个字符转换为str2的前j-1个字符所需的操作次数，再加上1次插入操作。
- d[i-1][j-1] + temp：将str1的前i-1个字符转换为str2的前j-1个字符所需的操作次数，再加上temp次替换操作（如果需要）。

最后，d[len(str1)][len(str2)]的值即为str1和str2之间的Levenshtein距离。

当然可以。假设我们需要计算两个字符串之间的Levenshtein距离，字符串str1为"kitten”，字符串str2为"sitting”。我们可以按照之前提到的伪代码来计算它们之间的距离。

初始化动态规划矩阵d：

   | - | s | i | t | t | i | n | g |
---|---|---|---|---|---|---|---|---|
-  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
k  | 1 |   |   |   |   |   |   |   |
i  | 2 |   |   |   |   |   |   |   |
t  | 3 |   |   |   |   |   |   |   |
t  | 4 |   |   |   |   |   |   |   |
e  | 5 |   |   |   |   |   |   |   |
n  | 6 |   |   |   |   |   |   |   |

使用伪代码中提到的动态规划方法填充矩阵：

   | - | s | i | t | t | i | n | g |
---|---|---|---|---|---|---|---|---|
-  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
k  | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
i  | 2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
t  | 3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
t  | 4 | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
e  | 5 | 5 | 4 | 3 | 2 | 3 | 4 | 5 |
n  | 6 | 6 | 5 | 4 | 3 | 4 | 3 | 4 |

矩阵右下角的值d[6][7] = 4表示"kitten"和"sitting"之间的Levenshtein距离为4。

这意味着我们需要进行以下4个操作才能将"kitten"转换为"sitting”：

将"k"替换为"s”（替换操作）
将"e"替换为"i”（替换操作）
将"n"替换为"t”（替换操作）
在末尾添加"g”（插入操作）

In both original LD and NW algorithm, elements are compared by matching their values, and the result is either match or not. While in work of this paper, tokens are compared to get a token distance in scope [0,1]. To apply the idea of LD or NW algorithm, we make some optimization.

Firstly, values in the first row and column are kept the same, cause when one of the comparing token sequence is empty, their difference is naturally the length of the other sequence. Secondly, when fill in the other blanks in the distance matrix of tokens, we replace the matching of sequence element by TFD. As the matching result is no longer 0/1, we optimized the iteration equation to be:

翻译：

在原始的LD和NW算法中，元素通过匹配它们的值进行比较，结果要么匹配要么不匹配。然而，在这篇论文的工作中，标记进行比较以获得一个范围在[0,1]之间的标记距离。为了应用LD或NW算法的思想，我们进行了一些优化。

首先，第一行和第一列的值保持不变，因为当比较的标记序列中的一个为空时，它们之间的差异自然是另一个序列的长度。

其次，在填充标记距离矩阵的其他空格时，我们用TFD替换序列元素的匹配。由于匹配结果不再是0/1，我们将迭代方程优化为：
3. d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + TFD(t_i, t_j))

where $t_i$ and $t_j$ are the $i$ th and $j$ th tokens of each message token sequence.

这样做的意义在于能够更精确地度量两个序列之间的差异。在原始的LD和NW算法中，元素仅通过其值进行匹配，导致结果只有匹配或不匹配两种情况。在这篇论文的改进方法中，通过计算标记之间的距离（范围在[0,1]之间），可以更精确地度量两个序列之间的相似性。这有助于在实际应用中更好地解决问题，如自然语言处理、生物信息学等领域。

修改后的伪代码如下：

function token_based_distance(seq1, seq2):
    n = length(seq1)
    m = length(seq2)

    # 初始化距离矩阵
    d = create_matrix(n+1, m+1)

    # 填充第一行和第一列
    for i in range(n+1):
        d[i][0] = i
    for j in range(m+1):
        d[0][j] = j

    # 动态规划填充矩阵
    for i in range(1, n+1):
        for j in range(1, m+1):
            # 计算标记距离
            token_distance = TFD(seq1[i-1], seq2[j-1])

            # 更新距离矩阵
            d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + token_distance)

    # 返回序列之间的距离
    return d[n][m]

Concrete description of the measurement of MFD is shown Algorithm 1. For the demonstration of two HTTP messages we show in Section 3.1, the token sequence alignment matrix could be calculated as Algorithm 1. And the result is shown in Fig. 4, where the value in bottom right corner represents for the MFD of two HTTP message token sequences.

翻译：

MFD测量的具体描述如算法1所示。对于我们在第3.1节展示的两个HTTP消息，标记序列对齐矩阵可以按照算法1计算。结果如图4所示，其中右下角的值代表两个HTTP消息标记序列的MFD。

Algorithm 1. MFD (Message Format Distance) measurement.

Fig. 4. MFD calculation of two example HTTP messages.

To verify this MFD calculation algorithm, we take three samples to compute their syntax distances, and the results are shown in Fig. 5. Obviously, messages HTTP1 and HTTP2 of same protocol have significant smaller MFD value (5.92) than those between them and message DNS (18.57 and 16.73). Systematic tests and verifications will be taken in Section 4.

翻译：

为了验证这个MFD计算算法，我们选取了三个样本来计算它们的语法距离，结果如图5所示。显然，相同协议的消息HTTP1和HTTP2之间的MFD值（5.92）明显小于它们与DNS消息之间的值（18.57和16.73）。系统性的测试和验证将在第4节进行。

Fig. 5. MFD in three messages.

In practice, as the length of message head with protocol syntax is unknown, we usually calculate MFD on the first certain bytes of matching messages, for the sake of computational efficiency. Concrete decision of the head length will be discussed in Section 3.3.

翻译：

在实际应用中，由于协议语法的消息头长度未知，为了计算效率，我们通常在匹配消息的前几个字节上计算MFD。关于头部长度的具体决策将在第3.3节中讨论。

这段话描述了在实际应用中计算消息的MFD时所面临的一个挑战。由于消息头部的长度可能是未知的，因此在计算过程中不能直接使用完整的消息。为了提高计算效率，我们通常仅在匹配消息的前几个字节上计算MFD。这种方法可以降低计算复杂度，但同时需要对头部长度进行合适的选择，以便在保持计算效率的同时，获得有意义和可靠的结果。

例如，在网络流量分析中，我们可能需要比较不同协议的消息，如HTTP和DNS。由于这些协议的消息头部长度可能不同，因此在计算MFD时，我们可以选择一个适当的头部长度，如前50个字节。这样，我们可以比较两个消息在这50个字节内的相似性，而不需要处理整个消息。

需要注意的是，头部长度的选择可能会影响计算结果的准确性。如果选择的头部长度过短，可能无法捕捉到足够的信息来区分不同的协议。如果头部长度过长，则可能导致计算效率降低。因此，在实际应用中需要对头部长度进行权衡和选择。具体的决策过程将在文献中的第3.3节进行讨论。

代码实现

为了实现完整的计算MFD的python代码，我们可以将两段伪代码结合起来。

###################
def token_format_distance(set1, set2):
    return 1 - len(set1.intersection(set2)) / len(set1.union(set2))

def generate_attribute_sets(message):
    return [set([byte]) for byte in message]

def calculate_tfd_matrix(message1_attribute_sets, message2_attribute_sets):
    tfd_matrix = [[0 for _ in range(len(message2_attribute_sets))] for _ in range(len(message1_attribute_sets))]
    
    for i, set1 in enumerate(message1_attribute_sets):
        for j, set2 in enumerate(message2_attribute_sets):
            tfd_matrix[i][j] = token_format_distance(set1, set2)
    
    return tfd_matrix

def print_tfd_matrix(tfd_matrix):
    print("Token Format Distance Matrix:")
    for row in tfd_matrix:
        print([round(x, 2) for x in row])
###################
        
def token_based_distance(seq1, seq2):
    n = len(seq1)
    m = len(seq2)

    # 初始化距离矩阵
    d = [[0 for _ in range(m+1)] for _ in range(n+1)]

    # 填充第一行和第一列
    for i in range(n+1):
        d[i][0] = i
    for j in range(m+1):
        d[0][j] = j

    seq1_attribute_sets = generate_attribute_sets(seq1)
    seq2_attribute_sets = generate_attribute_sets(seq2)
    tfd_matrix = calculate_tfd_matrix(seq1_attribute_sets, seq2_attribute_sets)

    # 动态规划填充矩阵
    for i in range(1, n+1):
        for j in range(1, m+1):
            # 计算标记距离
            token_distance = tfd_matrix[i-1][j-1]

            # 更新距离矩阵
            d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + token_distance)

    # 返回序列之间的距离
    return d[n][m]

message1 = [0x50, 0x4F, 0x53, 0x54, 0x20, 0x2F, 0x20, 0x48, 0x54, 0x54, 0x50]
message2 = [0x47, 0x45, 0x54, 0x20, 0x2F, 0x20, 0x48, 0x54, 0x54, 0x50]

distance = token_based_distance(message1, message2)
print("MFD between message1 and message2:", distance)

这段代码首先实现了generate_attribute_sets函数，然后将两段伪代码结合在一起。

token_based_distance函数首先根据输入序列生成属性集合，并计算TFD矩阵。接下来，使用动态规划填充距离矩阵，并返回序列之间的MFD。最后，我们使用示例消息来计算和打印它们之间的MFD。

3.3. Unsupervised clustering strategy

The message format distance measurement MFD introduced in Section 3.2 is applied to form a message distance matrix, instead of Euclidean distance used in most cluster algorithms like PAM algorithm in [18], [28]. In terms of the distribution characteristics of unknown message format distances, we employ the density based DBSCAN algorithm [36] to conduct the cluster step. This algorithm is once used to cluster internet traffic of public protocols [46] by utilizing statistic feature vectors as flow similarity. While in this paper, it is used to realize the clustering of unknown protocol messages by unsupervised machine learning.

Different from partition or hierarchical based cluster methods, the basic idea of DBSCAN is to find elements or regions with enough density (Fig. 6). This algorithm has an advantage in finding clusters in any shapes, as long as the elements are density connected. This advantage is pretty important when we deal with cluster problem of unknown protocol messages, because the shape of clusters is uncertain (Fig. 7) and what’s more, the elements’ distances are calculated in a high dimensional space, other than Euclidean space which is widely used in most cluster algorithms.

翻译：

在第3.2节中引入的消息格式距离测量MFD被应用于形成消息距离矩阵，而不是大多数聚类算法（如[18]、[28]中的PAM算法）中使用的欧几里得距离。根据未知消息格式距离的分布特征，我们采用基于密度的DBSCAN算法[36]来进行聚类步骤。此算法曾用于通过利用统计特征向量作为流相似性来聚类公共协议的互联网流量[46]。然而在本文中，它被用于通过无监督机器学习实现未知协议消息的聚类。

与分区或基于层次的聚类方法不同，DBSCAN的基本思想是找到具有足够密度的元素或区域（图6）。只要元素是密度相连，该算法在找到任何形状的聚类方面具有优势。当我们处理未知协议消息的聚类问题时，这个优势非常重要，因为聚类的形状是不确定的（图7），而且，元素的距离是在高维空间中计算的，而不是在欧几里得空间中，后者被广泛应用于大多数聚类算法。

DBSCAN

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的空间聚类算法，它可以识别任意形状的聚类，同时对噪声数据具有较好的鲁棒性。DBSCAN的基本思想是将具有足够密度的区域视为一个簇，并将密度相连的区域连接在一起。

DBSCAN算法主要有三个核心概念：

邻域（ε-neighborhood）：对于给定数据点p，其ε-邻域包含在以p为中心且半径为ε的圆内的所有数据点。
核心点（Core point）：如果一个数据点的ε-邻域内至少包含MinPts个其他数据点，那么该数据点被认为是一个核心点。
密度相连（Density-connected）：如果存在一个点序列p1, p2, …, pn，其中每个点pi和pi+1是直接密度可达的（即它们是彼此的核心点），那么数据点p和q就是密度相连的。

DBSCAN算法的基本步骤如下：

选择一个未被访问的数据点，找到其ε-邻域中的所有数据点。
如果该数据点的ε-邻域内包含至少MinPts个其他数据点，则创建一个新簇并将该数据点及其邻域内的所有数据点添加到该簇中。标记这些点为已访问。
对于该簇中的每个数据点，找到其ε-邻域中的所有数据点。如果该点是核心点，并且其邻域中存在尚未属于任何簇的数据点，则将这些数据点添加到当前簇中，并标记为已访问。
重复上述过程，直到所有数据点都被访问过。

举例说明：

假设我们有一组二维数据点，我们将ε设为1，MinPts设为4。在开始聚类之前，所有数据点都被标记为未访问。

从数据点集合中随机选择一个未访问的数据点A，并找到其ε-邻域中的所有数据点。
假设A的ε-邻域内有5个其他数据点，超过MinPts的要求。因此，我们创建一个新簇并将A及其邻域内的数据点添加到该簇中。标记这些点为已访问。
对于簇中的每个数据点（包括A），找到其ε-邻域中的所有数据点。对于每个邻域内的核心点，如果它们尚未属于任何簇，将它们添加到当前簇中。
继续执行步骤3，直到簇中所有数据点的邻域都被检查过。然后返回步骤1，直到所有数据点都被访问过。

最终，DBSCAN将找到具有足够密度的簇，并将它们连接在一起。在这个过程中，任何不属于任何簇的数据点将被视为噪声。

Fig. 6. Basic idea of DBSCAN.

Fig. 7. Cluster example compare. See ref. [47], [48].

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）和K-means是两种常用的聚类算法，它们在处理数据时有很大的不同。下面是它们之间的详细比较：

1. 算法原理：

DBSCAN：基于密度的聚类算法，它把密度相连的区域划分为一个簇，并能有效地处理噪声数据。核心思想是通过判断每个数据点的ε-邻域内的数据点数量来识别簇，从而找到具有足够密度的区域。
K-means：基于距离的聚类算法，通过最小化簇内数据点与簇中心的距离平方和来划分簇。算法迭代过程中不断更新簇中心，直至收敛。

2. 形状与大小：

DBSCAN：能够发现任意形状的簇，不受形状限制。
K-means：通常假设簇呈圆形或球形，对非凸形状的簇处理效果较差。

3. 簇的数量：

DBSCAN：不需要事先指定簇的数量，算法会自动识别出合适数量的簇。
K-means：需要事先指定簇的数量K，对于不同的K值，聚类结果可能有很大差异。

4. 对噪声的敏感性：

DBSCAN：对于噪声数据具有较好的鲁棒性，可以将噪声数据点识别并排除在簇之外。
K-means：对噪声数据敏感，噪声数据点可能影响簇中心的计算及最终聚类结果。

5. 收敛速度与迭代次数：

DBSCAN：时间复杂度在合适的数据结构下为O(nlogn)，其中n是数据点数量。通常具有较高的计算效率。
K-means：收敛速度可能较慢，因为算法需要多次迭代以更新簇中心。时间复杂度为O(n * K * I * d)，其中n是数据点数量，K是簇数量，I是迭代次数，d是维度。

6. 参数选择：

DBSCAN：需要选择两个参数：邻域半径ε和最小数据点数MinPts。合适的参数值对算法性能有很大影响。
K-means：只需指定簇的数量K。然而，选择合适的K值也可能是个挑战，可能需要尝试不同的K值并评估聚类结果。

总之，DBSCAN和K-means在聚类任务上有各自的优缺点。DBSCAN能处理任意形状的簇且对噪声有鲁棒性，但参数选择对结果影响较大。而K-means需要预先设定簇数量，对噪声敏感，但参数较少。在实际应用中，可以根据数据特点和需求选择合适的聚类算法。

当处理未知协议消息的聚类问题时，DBSCAN具有一些优势，使其成为一个更合适的选择：

不需要预先指定簇数量：在处理未知协议消息时，我们可能不知道有多少种不同的消息类型（即簇的数量）。DBSCAN不需要预先设定簇数量，它可以自动根据数据密度识别簇，这在处理未知协议消息时很有用。
能够处理噪声：在实际通信过程中，可能会收到一些噪声消息，这些消息与其他协议消息无关。DBSCAN能够识别并处理这些噪声数据，使得聚类结果更准确。
对任意形状的簇都有效：由于未知协议消息的特点，不同类型的消息可能在特征空间中呈现不同的分布形状。DBSCAN能够发现任意形状的簇，因此非常适合处理这种情况。
基于密度的聚类原理：DBSCAN的密度概念有助于在特征空间中自然地划分簇。这使得算法能够将具有相似特征的未知协议消息聚集在一起，从而更容易地识别出它们。
鲁棒性：DBSCAN对于异常值和噪声具有较好的鲁棒性。在处理未知协议消息时，这一优点有助于确保聚类结果的稳定性和准确性。

综上所述，DBSCAN在处理未知协议消息的聚类问题时具有很大的优势。然而，需要注意的是，DBSCAN对参数选择（如邻域半径ε和最小数据点数MinPts）的敏感性。在实际应用中，可能需要尝试不同的参数组合以获得最佳聚类结果。

In this paper, we use the MFD based on format similarity defined in Section 3.2 to get the distance matrix of unknown protocol messages which are to be clustered. Then the DBSCAN algorithm is applied on this distance matrix. There are many indexes to measure the quality of a cluster result. When analyzing mixed unknown protocol messages, supervised indexes like homogeneity, completeness, adjusted rand index and so on become unavailable because of lack of standard results. Therefore, we choose two unsupervised cluster quality measure indexes, Silhouette Coefficient [34] and Dunn Index [35], to assist choosing appropriate parameters of cluster algorithm.

Definition of a Silhouette Coefficient on one sample is in Eq. (9).

翻译：

在本文中，我们使用第3.2节中定义的基于格式相似性的MFD来获取待聚类的未知协议消息的距离矩阵。然后，将DBSCAN算法应用于此距离矩阵。有许多指标可以衡量聚类结果的质量。在分析混合未知协议消息时，由于缺乏标准结果，有监督指标如同质性、完整性、调整后的兰德指数等变得无法使用。

因此，我们选择两个无监督聚类质量度量指标，轮廓系数 [34]和邓恩指数 [35]，以协助选择合适的聚类算法参数。

一个样本的轮廓系数定义参见公式(9)

where data point $i ∈ Ci$. $a_i$ is the mean intra-cluster distance indicating how well $i$ is assigned to its cluster with smaller $a_i$ stands for better assignment of $i$. $b_i$ is the nearest mean distance between $i$ and other clusters, and the bigger $b_i$ is, the better $i$ is separated from other clusters. The value of $s_i$ range in $[-1,1]$ . When $a_i ≪ b_i$, indicating the intra-cluster distance is much smaller than those between clusters, $s_i$ will be close to $1$, which means a better partition result of samples. On the contrary, if $s_i < 0$, then $i$ is better to be clustered into some neighbouring cluster to avoid $a_i > b_i$. Besides this, if $i$ is located on the border of two clusters, $s_i$ will be close to $0$.

翻译：

其中数据点 $i ∈ Ci$。$a_i$ 是簇内平均距离，表示数据点 $i$ 被分配到其所属簇的程度，$a_i$ 较小表示 $i$ 的分配更好。$b_i$ 是数据点 $i$ 与其他簇之间的最近平均距离，$b_i$ 越大，$i$ 与其他簇的分离程度越好。$s_i$ 的值范围在 $[-1,1]$ 之间。当 $a_i ≪ b_i$ 时，表示簇内距离远小于簇间距离，$s_i$ 将接近 $1$，这意味着样本的划分结果更好。相反，如果 $s_i < 0$，则数据点 $i$ 更适合被归入某个相邻簇，以避免 $a_i > b_i$。此外，如果数据点 $i$ 位于两个簇的边界上，$s_i$ 将接近 $0$。

轮廓系数（Silhouette Coefficient）是一种用于评估聚类效果的无监督度量方法。它结合了内部紧密性（簇内的点距离较近）和外部分离性（簇间的点距离较远）来评价聚类结果。轮廓系数的值范围在-1到1之间，其中较高的值表示聚类效果更好。轮廓系数可用于确定最优的聚类数量或评估聚类算法的性能。

轮廓系数的计算方法如下：

对于每个数据点 i，计算它与同一个簇内其他数据点的平均距离，记为 a(i)。这反映了簇内紧密性。
对于每个数据点 i，计算它与其他簇中所有数据点的平均距离，找出最小的一个，记为 b(i)。这反映了簇间分离性。
对于每个数据点 i，计算轮廓系数：

$s(i) = (b(i) - a(i)) / max(a(i), b(i))$

对于整个数据集，所有数据点的轮廓系数的平均值称为整体轮廓系数。较高的整体轮廓系数表示聚类效果较好。

举例说明：

假设我们有一个数据集，包括以下6个点（用坐标表示）：

A1 = (1, 1)
A2 = (1, 2)
A3 = (2, 2)
B1 = (5, 5)
B2 = (6, 5)
B3 = (6, 6)

现在我们将这些点分为两个簇：A = {A1, A2, A3} 和 B = {B1, B2, B3}。

计算轮廓系数的过程如下：

对于簇A中的点A1，计算它与A2和A3的平均距离 a(A1) = (1 + sqrt(2)) / 2 ≈ 0.91。
计算A1与簇B中的点B1、B2和B3的平均距离，然后找到最小的一个，即 b(A1) = (sqrt(32) + sqrt(41) + sqrt(50)) / 3 ≈ 5.12。
计算A1的轮廓系数：s(A1) = (5.12 - 0.91) / max(5.12, 0.91) ≈ 0.82。

以此类推，可以计算出其他点的轮廓系数，然后取平均值得到整体轮廓系数。

需要注意的是，轮廓系数对于数据集中的噪声点和异常点比较敏感。因此，在实际应用中，通常需要结合其他评估指标来评价聚类效果。

Then, average of $s_i$ over all samples: $𝑆𝐶(𝐶) = \frac{1}{|𝐶|}\sum_{i ∈𝐶}𝑠_i$ is defined to be one of the measure indexes of whole cluster result, Silhouette Coefficient, indicating how tightly those points are grouped into clusters. Obviously, the bigger this index is, the better those samples are grouped.

翻译：

然后，计算所有样本的 $s_i$ 平均值，得到整体聚类结果的度量指标之一：轮廓系数（Silhouette Coefficient），表示为 $𝑆𝐶(𝐶) = \frac{1}{|𝐶|}\sum_{i ∈𝐶}𝑠_i$ 。轮廓系数表示点群被分组到簇中的紧密程度。显然，该指标越大，样本的分组效果越好。

Definition of Dunn Index is shown in Eq. (12): $$ 𝐷𝐼_𝑚 = \frac{\min_{1 \leq 𝑖 \leq 𝑗 \leq 𝑚} \delta(𝐶_𝑖, 𝐶_𝑗)}{\max_{1 \leq 𝑘 \leq 𝑚} \Delta_𝑘} \qquad (12) $$

where $m$ is the number of clusters with $\delta(𝐶_𝑖, 𝐶_𝑗) = \min_{𝑥 ∈𝐶_𝑖,𝑦 ∈𝐶_𝑗} 𝑑(𝑥, 𝑦)$ indicating the minimum distance between-class, and $\Delta_𝑘 = \max_{𝑥,𝑦 ∈𝐶_𝑘} 𝑑(𝑥, 𝑦)$ indicating the maximum distance within class, respectively. $x$ and $y$ are elements in class $Ci$ or $Cj$, and $d(x, y)$ is the distance of these two elements. Obviously, bigger DI values support for larger separation and compactness between and within classes, which means better quality of result clusters.

翻译：

邓恩指数（Dunn Index）的定义如下式 (12) 所示： $$ 𝐷𝐼_𝑚 = \frac{\min_{1 \leq 𝑖 \leq 𝑗 \leq 𝑚} \delta(𝐶_𝑖, 𝐶_𝑗)}{\max_{1 \leq 𝑘 \leq 𝑚} \Delta_𝑘} \qquad (12) $$ 其中，$m$ 是簇的数量，$\delta(𝐶_𝑖, 𝐶_𝑗) = \min_{𝑥 ∈𝐶_𝑖,𝑦 ∈𝐶_𝑗} 𝑑(𝑥, 𝑦)$ 表示类间最小距离，而 $\Delta_𝑘 = \max_{𝑥,𝑦 ∈𝐶_𝑘} 𝑑(𝑥, 𝑦)$ 分别表示类内最大距离。$x$ 和 $y$ 是类 $C_i$ 或 $C_j$ 中的元素，$d(𝑥, 𝑦)$ 是这两个元素之间的距离。显然，较大的邓恩指数值支持类间和类内的较大分离和紧凑性，这意味着结果簇的质量更好。

邓恩指数（Dunn Index, DI）是一种用于评估聚类算法性能的度量指标。它衡量了类间的分离程度和类内的紧凑性，因此可以用来评价聚类结果的质量。邓恩指数值越大，意味着聚类结果的质量越好。

邓恩指数的计算方法如下：

$$ 𝐷𝐼_𝑚 = \frac{\min_{1 \leq 𝑖 \leq 𝑗 \leq 𝑚} \delta(𝐶_𝑖, 𝐶_𝑗)}{\max_{1 \leq 𝑘 \leq 𝑚} \Delta_𝑘} $$

其中：

$m$ 是簇的数量。
$\delta(𝐶_𝑖, 𝐶_𝑗) = \min_{𝑥 ∈𝐶_𝑖,𝑦 ∈𝐶_𝑗} 𝑑(𝑥, 𝑦)$ 是类间最小距离，表示不同类之间的最近数据点之间的距离。
$\Delta_𝑘 = \max_{𝑥,𝑦 ∈𝐶_𝑘} 𝑑(𝑥, 𝑦)$ 是类内最大距离，表示同一类中最远数据点之间的距离。
$d(𝑥, 𝑦)$ 是数据点 $x$ 和 $y$ 之间的距离。

邓恩指数通过计算类间最小距离与类内最大距离的比值来评估聚类结果。较大的邓恩指数值表示类间距离较大，类内距离较小，聚类效果较好。

举例说明：

假设有以下聚类结果，共有 3 个簇：$C_1 = {1, 2, 3}$，$C_2 = {4, 5, 6}$ 和 $C_3 = {7, 8, 9}$。以下是数据点之间的距离矩阵：

   1  2  3  4  5  6  7  8  9
1  0  1  2  9 10 11 20 21 22
2  1  0  1 10  9 10 21 20 21
3  2  1  0 11 10  9 22 21 20
4  9 10 11  0  1  2 13 14 15
5 10  9 10  1  0  1 14 13 14
6 11 10  9  2  1  0 15 14 13
7 20 21 22 13 14 15  0  1  2
8 21 20 21 14 13 14  1  0  1
9 22 21 20 15 14 13  2  1  0

计算邓恩指数：

类间最小距离：$C_1$ 和 $C_2$ 之间的最小距离为 9；$C_1$ 和 $C_3$ 之间的最小距离为 20；$C_2$ 和 $C_3$ 之间的最小距离为 13。因此，$\delta(𝐶_𝑖, 𝐶_𝑗) = 9$。
类内最大距离：$C_1$ 的最大距离为 2；$C_2$ 的最大距离为 2；$C_3$ 的最大距离为 2。因此，$\Delta_𝑘 = 2$。
邓恩指数：$𝐷I_𝑚 = \frac{\delta(𝐶_𝑖, 𝐶_𝑗)}{\Delta_𝑘} = \frac{9}{2} = 4.5$

在这个例子中，邓恩指数为 4.5。邓恩指数越高，表示聚类结果的类间距离越大，类内距离越小，聚类效果越好。需要注意的是，邓恩指数在实际应用中可能受到数据集、距离度量等因素的影响，因此，最好将其与其他聚类评估指标结合使用，以获得更全面的聚类性能评价。

In work of this paper, we select the optimal parameters of DBSCAN with the assistance of Silhouette Coefficient and Dunn Index by picking the parameters that lead to the maximum of their mean value which we define as Eq. (13), and m stands for number of clusters. $$ 𝑠𝑑 = \frac{(𝑆𝐶_𝑚 + 𝐷𝐼_𝑚)}{2} \qquad (13) $$

翻译：

在本文的工作中，我们通过选择使它们的平均值最大化的参数来在轮廓系数和邓恩指数的辅助下选择 DBSCAN 的最佳参数，我们将其定义为式 (13)，其中 $m$ 代表簇的数量。 $$ 𝑠𝑑 = \frac{(𝑆𝐶_𝑚 + 𝐷𝐼_𝑚)}{2} \qquad (13) $$

这里提到的俩指标应该都是有现成代码的~

以下是一些使用 Python 语言实现的邓恩指数和轮廓系数计算的开源库链接：

scikit-learn：这是一个非常流行的 Python 机器学习库，提供了大量的机器学习算法实现，包括聚类算法。在 scikit-learn 中，轮廓系数可以使用 silhouette_score 函数进行计算。

轮廓系数文档：https://scikit-learn.org/stable/modules/generated/sklearn.metrics.silhouette_score.html

示例代码：

from sklearn.metrics import silhouette_score
from sklearn.cluster import KMeans
import numpy as np
   
X = np.array([[1, 2], [1, 4], [1, 0], [4, 2], [4, 4], [4, 0]])
kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
labels = kmeans.labels_
silhouette_avg = silhouette_score(X, labels)
print("The average silhouette_score is :", silhouette_avg)

scikit-learn-extra：这是一个扩展 scikit-learn 功能的库，提供了一些额外的聚类算法和评估指标。在 scikit-learn-extra 中，邓恩指数可以使用 dunn 函数进行计算。

邓恩指数文档：https://scikit-learn-extra.readthedocs.io/en/latest/generated/sklearn_extra.metrics.dunn.html

示例代码：

# 请先安装 scikit-learn-extra: pip install scikit-learn-extra
from sklearn_extra.metrics import dunn
from sklearn.cluster import KMeans
import numpy as np
   
X = np.array([[1, 2], [1, 4], [1, 0], [4, 2], [4, 4], [4, 0]])
kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
labels = kmeans.labels_
dunn_score = dunn(X, labels)
print("The dunn score is :", dunn_score)

这些库提供了邓恩指数和轮廓系数的现成实现，注意，这些库可能需要安装额外的依赖包，如 NumPy 和 SciPy

4. Experiment and analysis

Testing of our proposal is introduced in this section. The datasets used for testing are introduced firstly, together with relative preprocessing work.

To decide the optimal parameter configuration, we apply sd from Eq. (13) introduced in Section 3.3 to help tuning relative parameters, and use homogeneity, completeness, their harmonic mean V-measure and fmi (Fowlkes-Mallows index [49]) to check the performance of our method.

翻译：

在本节中，我们将介绍我们提案的测试。首先，我们将介绍用于测试的数据集，以及相关的预处理工作。

为了确定最优的参数配置，我们应用第3.3节中引入的等式（13）中的sd来帮助调整相关参数，并使用同质性、完整性、它们的调和平均值V-measure和Fowlkes-Mallows指数（fmi）来检查我们方法的性能。 $$ 𝑠𝑑 = \frac{(𝑆𝐶_𝑚 + 𝐷𝐼_𝑚)}{2} \qquad (13) $$

As the message clustering method we introduced in this paper could be divided into two parts: MFD calculation and unsupervised clustering, comparison experiments are token on these two parts separately, which are three sequence alignment methods (MFD, value based NW algorithm (v-NW for short) and type-based NW algorithm (t-NW)) and three clustering algorithms (DBSCAN, UPGMA and PAM), details are explained in Section 4.3.

翻译：

由于我们在本文中介绍的消息聚类方法可以分为两部分：MFD计算和无监督聚类，所以我们分别对这两部分进行比较实验，包括三种序列对齐方法（MFD、基于值的NW算法（简称v-NW）和基于类型的NW算法（简称t-NW））以及三种聚类算法（DBSCAN、UPGMA和PAM），详细说明见第4.3节。

4.1. Data collection and preprocessing

Despite the truth that the unsupervised clustering method we designed in this paper is suitable for messages of unknown protocol from any layer of the internet, as well as messages in any network architecture, we test it on common network protocols with ground truth of message format labels available to check its performances. Usually, those messages with unknown formats we need to distinguish exist in certain network area or gateway. Thus, we test the performance of our method on two datasets: one is collected in a local area network under controlled experimental environment with the diversity of protocols ensured [50], the other is captured from a local university gateway for 20 seconds in 2017/11/21, to simulate common network management scenarios. In the experiment, we test the ability of our method in distinguishing different message formats treating these messages formats as unknown, and then compare the result with ground truth to check the final performance of our method.

翻译：

尽管我们在本文中设计的无监督聚类方法适用于互联网任何层次的未知协议消息，以及任何网络架构中的消息，但为了检查其性能，我们在具有已知消息格式标签的常见网络协议上进行测试。通常，我们需要区分的未知格式消息存在于某个网络区域或网关中。

因此，我们在两个数据集上测试我们方法的性能：一个是在受控实验环境下的局域网中收集的数据，确保协议的多样性；

另一个是在2017年11月21日，从一个本地大学网关中捕获的20秒数据，以模拟常见的网络管理场景。

在实验中，我们测试了我们的方法在将这些消息格式视为未知的情况下区分不同消息格式的能力，并将结果与已知的真实数据进行对比，以检查我们方法的最终性能。

To eliminate interference from encapsulation of other protocols in network or transport layers like IP and TCP and facilitate the test concentrating on message content, we filter out application layer payloads where most unknown protocol exist from the initial collected data by a commonly used open-source package manipulation tool Scapy [51]. Ground truth labels of message formats are set during this process.

翻译：

为了消除来自网络或传输层其他协议（如IP、TCP）封装的干扰，并使测试集中在消息内容上，我们使用常用的开源包操作工具Scapy从初始收集的数据中过滤出应用层有效载荷，这也是大多数未知协议所在的位置。在此过程中设置了消息格式的真实标签。

Details of the two datasets filtered and labeled by Scapy are shown in Tables 3 and 4. For the “PPTP control” label in set1-upc, there are 13 different control message labels exist, and we omit the minor details for brevity.

翻译：

经Scapy过滤和标记的两个数据集的详细信息如表3和表4所示。对于set1-upc中的“PPTP control”标签，存在13个不同的控制消息标签，为了简洁起见，我们省略了次要细节。

Table 3. Details of set1-upc.

message label	number	message label	number
NBNS query request	98,994	NTP Header	84,439
DNS	59,097	Skinny	1474
PPTP	771	PPTP control	421
VXLAN	32	NBT Session Packet	19
NBNS query response	3
total number:	245,250	size:	36.8MB

这份表格展示了名为 “set1-upc” 的数据集的详细信息。数据集包含了多种网络协议相关的消息类型（message label），以及每种类型的数量（number）。下面是对表格内容的详细解读。

表格中列出了以下消息类型及其数量：

NBNS query request：98,994个
NTP Header：84,439个
DNS：59,097个
Skinny：1,474个
PPTP：771个
PPTP control：421个
VXLAN：32个
NBT Session Packet：19个
NBNS query response：3个

表格还提供了数据集的总数和大小信息：

总数（total number）：245,250个
大小（size）：36.8MB

简要解释一下这些缩写：

NBNS：NetBIOS Name Service，一种名字解析服务，用于将网络上的计算机名解析为对应的IP地址。
NTP：Network Time Protocol，一种网络时间同步协议，用于使计算机和网络设备的时钟保持同步。
DNS：Domain Name System，一种域名解析系统，用于将网址解析为IP地址。
Skinny：Skinny Client Control Protocol (SCCP)，一种用于VoIP电话系统的通信协议。
PPTP：Point-to-Point Tunneling Protocol，一种用于实现虚拟专用网络（VPN）的协议。
VXLAN：Virtual Extensible Local Area Network，一种用于创建虚拟局域网（VLAN）的协议。
NBT：NetBIOS over TCP/IP，是在TCP/IP协议上实现NetBIOS服务的技术。

Table 4. Details of set2-campus.

message label	number	message label	number
DNS	2733	SNMP	58
BOOTP	53	RADIUS	11
total number:	2855	size:	518KB

这份表格展示了名为 “set2-campus” 的数据集的详细信息。数据集包含了多种网络协议相关的消息类型（message label），以及每种类型的数量（number）。下面是对表格内容的详细解读。

表格中列出了以下消息类型及其数量：

DNS：2,733个
SNMP：58个
BOOTP：53个
RADIUS：11个

表格还提供了数据集的总数和大小信息：

总数（total number）：2,855个
大小（size）：518KB

简要解释一下这些缩写：

DNS：Domain Name System，一种域名解析系统，用于将网址解析为IP地址。
SNMP：Simple Network Management Protocol，一种网络管理协议，用于监控和管理网络设备（如交换机、路由器等）的性能和配置。
BOOTP：Bootstrap Protocol，一种网络引导协议，用于在无盘工作站启动时自动获取IP地址和其他网络配置信息。
RADIUS：Remote Authentication Dial-In User Service，一种远程身份验证协议，用于在网络中提供集中式的身份验证、授权和计费管理。

这个数据集（set2-campus）与某个校园网络环境有关，因为它包含了一些典型的校园网络协议，如DNS、SNMP、BOOTP和RADIUS。

In our experiments, to increase computing efficiency, set1-upc is separated into 240 subsets with each composed of 1024 messages and set2-campus 12 subsets with each 256 messages (minor slice to get more but not derisory subsets). Experiments are conducted on each subset and average performance of them are taken as the final result.

在我们的实验中，为了提高计算效率，将 set1-upc 分成了240个子集，每个子集由1024条消息组成；将 set2-campus 分成了12个子集，每个子集由256条消息组成（稍微切片以获得更多但不是微不足道的子集）。实验在每个子集上进行，并以它们的平均性能作为最终结果。

这里 minor slice to get more but not derisory subsets 的意思是，通过将数据集进行稍微细分（minor slice），可以得到更多的子集，但这些子集的数量不至于过多而变得无足轻重（not derisory）。换句话说，作者在划分数据集时要确保子集的数量适中，既能提高计算效率，又不会导致子集太多而影响实验结果的可靠性。

4.2. Measurement indexes and parameter configuration

4.2.1. Measurement indexes

To measure the performance of unsupervised clustering strategy based on MFD proposed in this paper, we take the most commonly used indexes: homogeneity indicating the closeness of each cluster contains only members of a single class, completeness indicating how much all members of a given class are assigned to the same cluster, and $v-measure$[52] which is the harmonic mean of homogeneity and completeness, together with $fmi$ [49] defined as the geometric mean of the pairwise precision and recall, to make an overall evaluation.

为了衡量本文提出的基于MFD的无监督聚类策略的性能，我们采用了最常用的指标：同质性（homogeneity）表示每个簇仅包含单个类别成员的紧密程度，完整性（completeness）表示给定类别的所有成员被分配到同一个簇的程度，以及 v-measure，它是同质性和完整性的调和平均值，再加上 fmi，它被定义为成对精确度和召回率的几何平均值，以进行全面评估。

Let $G$ be the ground truth labels of a message set, and $P$ the predicted labels by our method, concrete definitions of the first three indexes are given bellow:

翻译：

令G为消息集的真实标签，P为我们方法的预测标签，以下给出了前三个指标的具体定义：

where $𝐻(𝐺|𝑃) = -∑^{|𝐺|}{𝑔=1}∑^{|𝑃|}{𝑝=1}(𝑛_{𝑔,𝑝}/𝑛)⋅log(𝑛_{𝑔,𝑝}/𝑛_𝑝)$ is the conditional entropy of ground truth label set and predicted label set, with $n$ the label set size, $n_g$ and $n_p$ each label number in ground truth label set and predicted label set, and $n_{g,p}$ the label number from ground truth label set $G$ assigned to predicted label set $P$. $𝐻(𝐺) = -∑^{|𝐺|}_{𝑔=1}(𝑛_𝑔/𝑛)⋅log(𝑛_𝑔/𝑛)$ is the entropy of ground truth label set. $H(P|G)$ and $H(P)$ are defined symmetrically.

翻译：

其中，$𝐻(𝐺|𝑃) = -∑^{|𝐺|}{𝑔=1}∑^{|𝑃|}{𝑝=1}(𝑛_{𝑔,𝑝}/𝑛)⋅log(𝑛_{𝑔,𝑝}/𝑛_𝑝)$ 是真实标签集和预测标签集的条件熵，$𝑛$ 是标签集的大小，$𝑛_𝑔$ 和$𝑛_𝑝$ 分别是真实标签集和预测标签集中的每个标签数量，$𝑛_{g,p}$ 是从真实标签集 $𝐺$ 分配给预测标签集 $𝑃$ 的标签数量。

$𝐻(𝐺) = -∑^{|𝐺|}_{𝑔=1}(𝑛_𝑔/𝑛)⋅log(𝑛_𝑔/𝑛)$ 是真实标签集的熵。$H(𝑃|𝐺)$ 和 $H(𝑃)$ 被对称地定义。

Definition of fmi [49] is shown in Eq. (17), where TP (True Positive) is the number of message pairs that belong to same clusters in both of ground-truth labels and predicted labels, FP (False Positive) is the number of message pairs that belong to same cluster in predicted labels but not in ground-truth labels, and FN (False Negative) is the number of message pairs that belong to same cluster in ground-truth labels but not in predicted labels.

$fmi$ 的定义如公式（17）所示，其中 $TP$（True Positive）是在真实标签和预测标签的簇中都属于同一簇的消息对的数量，$FP$（False Positive）是属于预测标签中的同一簇但不属于真实标签中的同一簇的消息对的数量，$FN$（False Negative）是属于真实标签中的同一簇但不属于预测标签中的同一簇的消息对的数量。

Besides, as the DBSCAN algorithm is capable of identifying noise sample, we add another index $coverage$ (Eq. (18)) to check the percentage of samples that could be successfully clustered.

翻译：

此外，由于DBSCAN算法能够识别噪声样本，我们添加了另一个指数覆盖率（覆盖率 = (总样本数 - 噪声数) / 总样本数）来检查可以成功聚类的样本的百分比。

4.2.2. Parameter configuration

According to the unsupervised clustering strategy introduced in Section 3.3, three parameters would be decided before application: $head length$ of unknown protocol messages, $eps$ and $minpts$ in DBSCAN, like shown in Eq. (19). Influences of these parameters is analyzed in this section, and the optimal parameter configuration is set accordingly.

翻译：

根据第3.3节介绍的无监督聚类策略，在应用前需要决定三个参数：未知协议信息的头部长度，DBSCAN中的eps和minpts，如公式（19）所示。本节将分析这些参数的影响，并相应地设定最佳参数配置。

这段话提到的三个参数与无监督聚类策略和DBSCAN算法有关。

未知协议消息的头部长度：在处理未知协议的网络流量数据时，我们需要考虑提取和分析消息的一部分，而不是整个消息。通常，协议消息的头部包含了足够的信息来帮助我们识别和分类消息。因此，在聚类过程中，我们只需要关注头部长度为一定字节的消息部分，这有助于减少计算复杂性和提高分析效率。
eps（ε）：这是DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法中的一个关键参数。eps表示用于确定样本之间邻域关系的距离阈值。如果两个样本之间的距离小于等于eps，则它们被认为是相互邻接的。eps值的选择对算法的性能有很大影响，因为它直接影响到聚类的密度和范围。过小的eps值可能导致样本被错误地标记为噪声，而过大的值可能导致不同聚类之间的边界变得模糊。
minpts（MinPts）：这是DBSCAN算法中的另一个关键参数。minpts表示一个样本要成为核心样本所需的最小邻居样本数。这个参数决定了聚类的密度，如果minpts值过小，可能导致噪声样本被错误地纳入聚类；如果值过大，可能导致算法识别不出足够的核心样本来形成聚类。

在使用无监督聚类策略时，需要仔细选择这三个参数的值，以便获得最佳的聚类结果。为了找到最优的参数设置，通常需要分析这些参数对聚类性能的影响，并根据实际数据和应用场景进行调整。

As mentioned in Section 3.2, the message headlength of unknown protocols is usually unknown, and probably have different head lengths. Thus, when aligning mixed unknown protocol messages, our choice of headlength would partly influence the alignment quality, as well as compute efficiency. Too short head length might be not enough to distinguish protocol formats, while overlong considered could be influenced by payloads and will reduce the computing efficiency.

翻译：

正如第3.2节中提到的，未知协议的消息头部长度通常是未知的，可能有不同的头部长度。因此，在对混合未知协议消息进行对齐时，我们选择的头部长度会部分影响对齐质量以及计算效率。过短的头部长度可能不足以区分协议格式，而过长的头部长度可能会受到有效载荷的影响，降低计算效率。

Fig. 8 a shows the cluster performance ($v-measure$ see in Section 4.2.1) on MFD matrix computed from message head with lengths in range $[4, 40]$ with step length 4, where $minpts=3$ and $eps ∈ [0, 20]$. When $headlength$ is too short, like $4$, $8$ or $12$, the clustering result is easily to get a less ideal result or limit $eps$ to a narrow interval, which increases the difficulty to search for optimal cluster parameters. When $headlength$ ≥ 20, the performance curves keeps a homologous variation. For the messages of unknown protocols, we assume them have a similar distribution of headlength with these existing ones. And therefore, we consider the parameter $headlength$ in Eq. (19) to be $20$ in our message format clustering method, to guarantee an appropriate search range of $eps$ and limit the cost of this method in an acceptable extent. Note that the $headlength$ here is used to limit the length of token sequence we compare their syntax similarity, but not the real message headlength of each messages.

翻译：

图8a展示了基于消息头部长度范围为[4, 40]、步长为4计算的MFD矩阵上的聚类性能（ $v-measure$ ），其中 $minpts=3$ 和 $eps ∈ [0, 20]$。当 $headlength$ 过短，如4、8或12时，聚类结果容易得到较不理想的结果或将 $eps$ 限制在较窄的区间内，这增加了寻找最优聚类参数的难度。当 $headlength$ ≥ 20时，性能曲线保持同源变化。

对于未知协议的消息，我们假设它们的头部长度分布与现有消息相似。因此，我们认为公式(19)中的参数 $headlength$ 为20，以保证适当的 $eps$ 搜索范围，并将该方法的成本限制在可接受的范围内。需要注意的是，这里的 $headlength$ 用于限制我们比较语法相似性的令牌序列长度，而不是每个消息的实际消息头长度。

$$ 𝑜𝑝𝑡 ( 𝐶) = arg\ max_{ℎ𝑒𝑎𝑑𝑙𝑒𝑛𝑔𝑡ℎ,𝑒𝑝𝑠,𝑚𝑖𝑛𝑝𝑡𝑠}𝑠𝑑 $$ $$ headlength = 20 $$

Fig. 8. Test on headlength and minpts.

The parameter $minpts$ of DBSCAN stipulates the density of clusters, and a lower value usually means more clusters would be built from noise. Test of performance on different minpts values shows highly similarity, see Fig. 8b where $headlength = 20$ and $eps ∈ [0, 20]$. We tend to attribute this property to the similarity in message format in high dimensions of MFD we define in Section 3.2, which means obvious distinctions exist in different message formats. When clustering messages from unknown protocols, we set $minpts$ a relative small value 3 to cover more protocols.

翻译：

DBSCAN的参数 $minpts$ 规定了簇的密度，较低的值通常意味着更多的簇会从噪声中构建。不同 $minpts$ 值上性能的测试显示出高度相似性，参见图8b，其中 $headlength = 20$ 和 $eps ∈ [0, 20]$。我们倾向于将这一特性归因于我们在第3.2节中定义的 MFD 高维度中消息格式的相似性，这意味着不同消息格式存在明显的差异。在聚类来自未知协议的消息时，我们将 $minpts$ 设置为相对较小的值3，以涵盖更多协议。 $$ minpts = 3 $$

Lastly, $eps$ of DBSCAN could be determined given $head length$ and $minpts$ by making $SC(C)$ get its maximum value as set in Eq. (19). We take extensive experiments to test the influence of $eps$ on performance of DBSCAN, and an sample of 2nd subset of set1-upc is shown in Fig. 9. As supervised and unsupervised measurements of cluster results respectively, sd and v-measure have similar trends as $eps$ increasing, and they get relative preferable results when $eps$ in middle range of [0,10]. For the example shown in Fig. 9, $sd$ gets its optimal value 0.77 when $eps = 2.4$, and corresponding $v-measure$ gets a relative high value of 0.95 (abnormal value range is filtered, details are shown in the following).

翻译：

最后，给定 $head length$ 和 $minpts$，可以通过使 $SC(C)$ 达到其最大值来确定DBSCAN的 $eps$，如公式(19)中所设定。我们进行了大量实验来测试 $eps$ 对DBSCAN性能的影响，集1-upc的第二子集的一个示例显示在图9中。作为聚类结果的有监督和无监督度量，$sd$ 和 $v-measure$ 随着 $eps$ 的增加具有相似的趋势，并且当 $eps$ 在[0,10]的中间范围内时，它们获得相对较好的结果。

对于图9中显示的示例，当 $eps = 2.4$ 时，$sd$ 达到其最佳值0.77，对应的 $v-measure$ 达到相对较高的值0.95（异常值范围已被过滤，详细信息见下文）。

Fig. 9. Performances on set1-upc-split2.

In fact, the TFD we define in Section 3.1 gets an expected value of 0.44 on randomly distributed data. After the message token sequence alignment, MFD will has an average of 8.8. That means clusters could possibly get meaningless result such as all in one cluster when eps is bigger than 8.8, like the latter part in Fig. 9. Conversely, if eps is too small, effective clusters would fail to be formed because of the strict distance requirement in DBSCAN, just like the former part in Fig. 9. Therefore, to guarantee the effectiveness of clustering, we restrict the search area of eps in a reasonable scope of [2.2, 6.6] considering the average of MFD as reference. Average performances in Fig. 10 on two datasets show the similarity in curves of supervised metrics (homogeneity, completeness, v-measure, fmi) and unsupervised metrics (sd) and the rationality of our method. When dealing with each subset, eps is dependent on concrete distribution to get the optimal performance.

翻译：

实际上，我们在第3.1节中定义的$TFD$在随机分布数据上的期望值为0.44。在消息令牌序列对齐之后，$MFD$的平均值为8.8。这意味着当$eps$大于8.8时，簇可能会获得无意义的结果，例如图9后半部分中的所有簇都在一个簇中。相反，如果$eps$过小，由于DBSCAN中严格的距离要求，有效簇将无法形成，就像图9前半部分那样。因此，为了保证聚类的有效性，我们考虑到$MFD$的平均值作为参考，将$eps$的搜索范围限制在合理的范围$[2.2, 6.6]$内。

图10中两个数据集的平均性能显示了有监督度量（同质性（homogeneity）、完整性（completeness）、v-measure、fmi）和无监督度量（sd）曲线的相似性以及我们方法的合理性。

在处理每个子集时，$eps$取决于具体分布以获得最佳性能

Fig. 10. Average performance on eps.

4.3. Experiment and comparison

In this section, we take the experiment to test our method in comparison with several state-of-the-art methods as introduced in Sections 1 and 2. As the message format clustering method proposed in this paper is composed of two parts: token sequence alignment and message clustering, we compare it with two varieties of sequence alignment NW algorithm (type-based NW and value based NW) and two clustering algorithms (UPGMA and PAM). Among them, the combination of value based NW algorithm and UPGMA is used in Netzob [23] in a semi-supervised way, type-based NW algorithm is once used in Discover [21] to distinguish messages, and PAM is a frequently used algorithm to cluster messages in PRE.

翻译：

在本节中，我们进行实验，将我们的方法与第1和2节中介绍的几种最先进的方法进行比较。由于本文提出的消息格式聚类方法由两部分组成：token序列对齐和消息聚类，我们将其与两种变体的序列对齐NW算法（基于类型的NW和基于值的NW）和两种聚类算法（UPGMA和PAM）进行比较。其中，基于值的NW算法和UPGMA的组合以半监督的方式用于Netzob [23]，基于类型的NW算法曾在Discover [21]中用于区分消息，而PAM是PRE中经常用于聚类消息的算法。

In contrast experiments, the strategy of parameter decision is similar with the method we proposed, thereby minimize probable artificial intervention. For PAM, the number of clusters is chosen by optimal unsupervised metric sd. The height of phylogenetic tree of UPGMA to export cluster result is also decided by optimal sd but in a stable range with extreme sd values eliminated (h > 2). If the utmost height of a phylogenetic tree is no more than 2, then we consider the messages in that subset have highly similarity and they are clustered into one class.

翻译：

在对照实验中，参数决策策略与我们提出的方法类似，从而最大限度地减少可能的人为干预。

对于PAM，通过最佳无监督度量sd选择簇的数量。

UPGMA的系统发育树高度用于导出聚类结果，同样由最佳的sd决定，但在一个稳定的范围内，排除了极端的sd值（h > 2）。如果系统发育树的最大高度不超过2，那么我们认为该子集中的消息高度相似，它们被聚类为一个类别。

phylogenetic tree

在这个上下文中，系统发育树被用于表示消息之间的相似性。每个节点代表一个消息，而分支表示这些消息之间的相似性。在这种情况下，树中节点之间的距离可能代表了消息之间的某种度量，例如编辑距离或其他相似性度量。

以文本消息为例：

消息1：Hello, how are you?
消息2：Hi, how are you?
消息3：Hey, what's up?
消息4：Hello, how's it going?

这些消息可以通过某种度量（如编辑距离）进行比较。基于这些度量，可以构建一个系统发育树来表示它们之间的相似性。例如，消息1和消息4可能更相似，因为它们都以“Hello”开头；而消息2和消息3可能更接近，因为它们都是简短的问候。构建出的系统发育树可能如下所示：

        ┌───────消息1
        │       ┌───────消息4
        ├───────┤
        │       │       ┌───────消息2
        └───────┼───────┤
                └───────┼───────消息3

在这个例子中，系统发育树展示了不同文本消息之间的相似性，并可以用于识别相似消息的聚类。在实验中，树的高度（h）用于确定聚类结果。在这个上下文中，高度是指树的最长分支长度。通过选择一个合适的高度阈值，可以将具有高度相似性的消息聚类在一起。

Results in Tables 5 and 6 show the performance of these methods in measurements of homogeneity (hom.), completeness (com.), v-measure (v.), fmi and coverage (cov.), which are introduced in Section 4.2.1. Corresponding measurement values are average of all subsets in each dataset. As noise samples might exist in result of DBSCAN, coverage is tested on the method we propose, while UPGMA and PAM could set all samples into clusters, hence relative places are left blank.

翻译：

表5和表6中的结果展示了这些方法在同质性（hom.）、完整性（com.）、V-度量（v.）、FMI和覆盖率（cov.）方面的性能，这些指标在第4.2.1节中介绍。相应的测量值是每个数据集中所有子集的平均值。由于DBSCAN结果中可能存在噪声样本，因此覆盖率是针对我们提出的方法进行测试的，而UPGMA和PAM可以将所有样本设置为簇，因此相关位置留空。

Table 5. Performance on set1-upc.

v-NW和t-NW分别表示两种层次聚类方法，它们使用不同的距离度量。

v-NW：这是一种基于变差距离（variance-based distance）的层次聚类方法。变差距离度量在计算两个观测点之间的距离时，会考虑数据的方差。这种方法对于不同尺度的数据集可能表现较好。
t-NW：这是一种基于时间序列距离（time series distance）的层次聚类方法。时间序列距离度量特别适用于时间序列数据，它能够捕捉时间序列的动态特征。这种方法在处理具有时间相关性的数据集时表现较好。

表格中的PAM表示Partitioning Around Medoids（基于中心点的划分），它是一种基于中心点的划分聚类方法。该方法试图最小化簇内观测点与其对应中心点之间的距离总和。在这个表格中，v-NW-PAM和t-NW-PAM表示分别在这两种层次聚类方法上应用PAM算法。

Table 6. Performance on set2-campus.

When checking the generality of MFD by comparing metrics in same color, we could find in Table 5 on set1-upc that most values in the first group of MFD outperform other groups with a few have pretty close values on metrics of v. and fmi.. In Table 6 on set2-campus, MFD keeps its advantage especially in combination with DBSCAN, even though t-NW have slightly better results (no more than 0.06) on v. and fmi. in some cases. This situation could be attributed to the variety of field values in set1-upc and similarity of those in set2-campus for their different data composition. In fact, the strategy of MFD could be regarded as a trade-off between v-NW and t-NW in the view of grammar which are either meticulous or rough. Therefore, in an overall consideration, MFD shows more fitness in measuring grammar distance of message from unknown protocols.

翻译：

在通过比较相同颜色的指标来检查MFD的通用性时，我们可以在set1-upc的表5中发现，MFD的第一组中的大多数值优于其他组，尽管在v.和fmi.指标上有一些值相当接近。在set2-campus的表6中，MFD保持了它的优势，尤其是与DBSCAN结合时，尽管在某些情况下t-NW在v.和fmi.指标上的结果略好（不超过0.06）。

这种情况可以归因于set1-upc中字段值的多样性和set2-campus中字段值的相似性，因为它们具有不同的数据组成。实际上，从语法的角度来看，MFD的策略可以被视为v-NW和t-NW之间的权衡，它们要么细致，要么粗糙。因此，在整体考虑下，MFD在测量未知协议消息的语法距离方面表现出更高的适应性。

The comparison of three cluster algorithms could be found in each sub-group led by three sequence alignment algorithms. The result in both datasets shows that when combined with MFD or v-NW, DBSCAN outperforms UPGMA and PAM on all indexes. When combined with t-NW, this advantage is remained on set2-campus while not on set1-upc. The overall performance of DBSCAN shows its ability on clustering messages. By getting remarkable v. and fmi. results of 0.9150 and 0.9724 on set1-upc and better on set2-campus with 0.9957 and 1.0, the combination of MFD and DBSCAN under our unsupervised clustering strategy shows its superiority in general, thus verifies the effectiveness of our method with admirable performance.

翻译：

在由三种序列对齐算法引导的每个子组中，可以找到三种聚类算法的比较。这两个数据集的结果显示，当与MFD或v-NW结合时，DBSCAN在所有指标上优于UPGMA和PAM。当与t-NW结合时，这种优势在set2-campus数据集上保持，但在set1-upc数据集上则没有。

DBSCAN的整体性能表明了它在聚类消息方面的能力。通过在set1-upc数据集上获得0.9150和0.9724的显著v.和fmi.结果，并在set2-campus数据集上表现得更好，分别为0.9957和1.0，MFD和DBSCAN组合在我们的无监督聚类策略下显示出其优越性，从而验证了我们方法的有效性和令人钦佩的性能。

In Fig. 11, MFD&DBSCAN proposed in this paper is compared with two typical methods v-NW&UPGMA and t-NW&PAM in boxplots on two datasets. Obviously, performance of MFD&DBSCAN is superior to the other two on both datasets. Although iqr of MFD&DBSCAN’s homogeneity is a bit bigger than the other two in Fig. 11a, its v. as a harmonic average of homogeneity and completeness has an iqr of 0.0834 and it is much smaller than those of the other two methods which are 0.4347 and 0.6036, indicating the superior of centrality and stability of our method. And so as fmi. on the same dataset (0.0200 vs. 0.2526, 0.4108). In Fig. 11b, MFD&DBSCAN outperforms completely with a nearly perfect performance centralized to 1.0 on all metrics. Generally speaking, the boxplots in Fig. 11 further illustrate the stability and effectiveness of our method on different datasets.

翻译：

在图11中，本文提出的MFD&DBSCAN与两种典型方法v-NW&UPGMA和t-NW&PAM在两个数据集上的箱线图进行了比较。显然，MFD&DBSCAN在两个数据集上的性能均优于另外两种方法。

尽管在图11a中，MFD&DBSCAN的同质性的四分位距略大于另外两种方法，但其作为同质性和完整性的调和平均值的v.具有0.0834的四分位距，远小于另外两种方法的0.4347和0.6036，表明我们方法的中心性和稳定性优越。在同一数据集上的fmi.也是如此（0.0200与0.2526、0.4108相比）。

在图11b中，MFD&DBSCAN在所有指标上完全胜出，表现接近完美且集中在1.0。总的来说，图11中的箱线图进一步说明了我们方法在不同数据集上的稳定性和有效性。

Fig. 11. Performance on metric distribution.

5. Conclusion and future work

In this paper, we propose two format similarity measurements and an unsupervised clustering strategy to distinguish internet messages from unknown protocols into classes with different formats. Measurement of token similarity is defined as Token Format Distance based on core rules of Augmented Backus-Naur Form and computed by Jaccard Index. An optimized algorithm based on Needleman Wunsch algorithm and Levenshtein Distance is designed as Message Format Distance measurement to define format similarity of message token sequences. Based on DBSCAN algorithm, we introduce the unsupervised clustering strategy by employing two unsupervised cluster quality evaluation indexes, Silhouette Coefficient and Dunn Index, together with a parameter selection strategy to promote the automatization of this process.

翻译：

在本文中，我们提出了两种格式相似性度量和一种无监督聚类策略，用于将来源于未知协议的互联网消息划分为具有不同格式的类别。基于增广巴科斯-诺尔范式的核心规则，通过Jaccard指数计算，定义了基于令牌相似性的度量，称为令牌格式距离。我们设计了一种基于Needleman Wunsch算法和Levenshtein距离的优化算法，作为消息格式距离度量，用于定义消息令牌序列的格式相似性。基于DBSCAN算法，我们引入了一种无监督聚类策略，通过使用两种无监督聚类质量评估指标——轮廓系数和邓恩指数，结合参数选择策略，以提高该过程的自动化程度。

Experiments compared with state-of-the-art methods verifies advantages of our method. For the cluster quality indexes we tested on homogeneity, completeness, v-measure of the former two, together with fmi, our method gets an average result of (0.8827, 0.9808, 0.9150, 0.9724) with coverage 0.9923 on subsets of set1-upc, and an admirable result of (0.9918, 1.000, 0.9957, 1.000) with coverage 0.9772 on set2-campus. Both results on two datasets outperform the compared methods in general, and they prove the effectiveness of our method. Boxplot analyses support for stability of this method by minor iqrs of (0.0834, 0.0200) analyzed on v. and fmi. in set1-upc and (0.0, 0.0) in set2-campus, and they are all significantly superior to those of other methods.

翻译：

与现有方法的实验比较验证了我们方法的优势。对于我们在同质性、完整性、前两者的v-measure以及fmi上测试的聚类质量指标，我们的方法在set1-upc子集上获得了平均结果（0.8827，0.9808，0.9150，0.9724），覆盖率为0.9923；在set2-campus上获得了令人钦佩的结果（0.9918，1.000，0.9957，1.000），覆盖率为0.9772。

两个数据集上的结果总体上优于比较方法，并证明了我们方法的有效性。箱线图分析支持该方法的稳定性，通过在set1-upc上分析v.和fmi.的较小四分位距（0.0834，0.0200），以及在set2-campus上的（0.0，0.0），它们都明显优于其他方法。

As a basic syntax regular widely used in protocol format development, rules of ABNF deserve more study and utilization in PRE, such as message syntax reconstruction and this paper proves the importance of ABNF in PRE process. Theoretically, the token sequence comparison process in this paper could be optimized to extract similar syntax components between messages. After extending this idea to reverse general syntax on multi-sequence, syntax structure of messages with same format is promising to be reversed. And these messages are right the cluster result of this paper.

翻译：

作为协议格式开发中广泛使用的基本语法规则，ABNF的规则在PRE中值得更多的研究和利用，如消息语法重构，本文证明了ABNF在PRE过程中的重要性。

从理论上讲，本文中的令牌序列比较过程可以优化为在消息之间提取相似的语法组件。将这个想法扩展到多序列上的通用语法反推，具有相同格式的消息的语法结构有望被还原。而这些消息正是本文的聚类结果。

Besides, although the processing order of format cluster or syntax extraction differs among works, the most popular and ultimate object of PRE is to rebuild a complete specification of an unknown protocol. Thus, the point is what we can get other than details of analysis. In this respect, unsupervised machine learning based on neural networks might be a worthy trial. But the problems of constructing feasible network architectures and modeling of learning target need to be solved. Lin et al. [53] is an admirable pioneering study on this area and it is also one of our research directions [50].

翻译：

此外，尽管格式聚类或语法提取的处理顺序在不同的工作中有所不同，但PRE最流行和最终的目标是重建一个未知协议的完整规范。因此，问题是我们除了分析细节之外还能得到什么。在这方面，基于神经网络的无监督机器学习可能是值得尝试的。但是，构建可行的网络架构和学习目标建模的问题需要解决。Lin等人[53]在这方面是一项令人钦佩的开创性研究，它也是我们的研究方向之一[50]。

实验复现

根据作者回复的邮件“关于这篇文章的处理细节，读取协议数据包用的是scapy，聚类部分直接调用sklearn库中接口即可，辅以参数调节。序列比对部分根据文方法介绍基本可以复现的”可以得到一些实验库信息~

前置知识

Scapy

Scapy是一个强大的Python库，用于创建、分析和操作网络数据包。它允许用户轻松地构造网络数据包、发送它们并捕获返回的数据包以进行分析。Scapy支持众多协议，可以用于网络扫描、路由跟踪、攻击检测等多种网络任务。Scapy的灵活性和可扩展性使其在网络安全和网络研究领域非常受欢迎。

Scapy的主要特点：

以交互式命令行界面提供，也可以作为库导入到Python脚本中。
支持广泛的网络协议，包括IP、TCP、UDP、ICMP、ARP等。
可以轻松地构造、解析和修改网络数据包。
支持数据包嗅探、捕获和分析。
可以实现数据包注入，用于测试网络设备、协议和安全防护措施。

Scapy举例：

以下是使用Scapy构造和发送网络数据包的简单示例。首先安装Scapy：

$ pip install scapy

接下来，编写一个Python脚本，使用Scapy构造一个简单的ICMP Echo请求数据包（ping请求）并发送给目标IP地址。

from scapy.all import *

# 构造IP数据包
ip = IP(dst="8.8.8.8")  # 目标IP地址，这里使用Google的公共DNS服务器

# 构造ICMP Echo请求数据包
icmp = ICMP(type="echo-request")  # "echo-request"表示ICMP Echo请求

# 构造完整的数据包
packet = ip / icmp

# 发送数据包并捕获响应
response = sr1(packet, timeout=2, verbose=0)

# 分析响应
if response is not None:
    if response[ICMP].type == "echo-reply":
        print("Ping成功！")
    else:
        print("收到非预期的ICMP响应。")
else:
    print("未收到响应。")

上述示例中，我们首先从scapy.all模块导入所有功能，接着创建一个IP数据包并设置目标地址。然后，构造一个ICMP Echo请求数据包。通过将ip和icmp对象相除，我们可以轻松地将它们组合成完整的数据包。最后，使用sr1()函数发送数据包并捕获响应。如果收到预期的ICMP Echo应答，脚本将输出“Ping成功！”。

这只是Scapy功能的一个简单示例，Scapy还可以用于执行更复杂的网络任务，如端口扫描、ARP欺骗、DNS欺骗等。

scapy读取协议数据包

以下是如何使用Scapy读取协议数据包的详细介绍和示例：

首先，确保安装了Scapy库。如果还未安装，可以使用以下命令安装：

pip install scapy

1. 读取数据包

要使用Scapy读取数据包，需要使用rdpcap()函数。这个函数从指定的文件中读取数据包，并将它们存储在一个列表中。以下是一个示例：

from scapy.all import *

packets = rdpcap('example.pcap')

在这个例子中，我们从名为example.pcap的文件中读取数据包，并将它们存储在packets列表中。

2. 分析数据包

读取数据包后，可以使用Scapy的内置函数和属性来分析它们。例如，可以使用summary()函数打印数据包的摘要信息：

for packet in packets:
    print(packet.summary())

这将打印出每个数据包的摘要信息，包括源地址、目的地址、协议类型等。

3. 获取特定协议层的数据

要访问数据包中特定协议层的数据，可以使用层名称作为属性。例如，以下代码提取了每个数据包中的IP层信息：

for packet in packets:
    ip_layer = packet[IP]
    print(ip_layer)

您还可以访问层中的特定字段，例如源IP地址和目的IP地址：

for packet in packets:
    src_ip = packet[IP].src
    dst_ip = packet[IP].dst
    print("Source IP:", src_ip, "Destination IP:", dst_ip)

同样，您可以访问其他协议层的数据，如TCP、UDP等：

for packet in packets:
    if TCP in packet:
        tcp_layer = packet[TCP]
        print(tcp_layer)
    elif UDP in packet:
        udp_layer = packet[UDP]
        print(udp_layer)

示例：从pcap文件中提取HTTP请求

以下示例展示了如何从pcap文件中提取HTTP请求：

from scapy.all import *
from scapy.layers.http import HTTPRequest

packets = rdpcap("example.pcap")

for packet in packets:
    if packet.haslayer(HTTPRequest):
        http_request = packet[HTTPRequest]
        http_method = http_request.Method.decode()
        http_uri = http_request.Path.decode()
        http_host = packet[IP].dst
        print(f"HTTP Request: {http_method} {http_uri} to {http_host}")

这个示例首先从example.pcap读取数据包，然后检查每个数据包是否包含HTTPRequest层。如果是，则提取HTTP方法、请求URI和目的IP地址，并打印它们。

使用Scapy确定消息的应用层协议信息并取出应用层头部的方法依赖于所分析的应用层协议。Scapy支持一些应用层协议，如HTTP、DNS等。以下是一个示例，展示了如何使用Scapy确定数据包的应用层协议信息（HTTP和DNS），并提取应用层头部。

from scapy.all import *
from scapy.layers.http import HTTPRequest, HTTPResponse
from scapy.layers.dns import DNS, DNSQR, DNSRR

packets = rdpcap('example.pcap')

for packet in packets:
    if packet.haslayer(HTTPRequest):
        print("Application Layer Protocol: HTTP (Request)")
        http_request = packet[HTTPRequest]
        print("HTTP Request Header:")
        print(http_request.show())

    elif packet.haslayer(HTTPResponse):
        print("Application Layer Protocol: HTTP (Response)")
        http_response = packet[HTTPResponse]
        print("HTTP Response Header:")
        print(http_response.show())

    elif packet.haslayer(DNS):
        print("Application Layer Protocol: DNS")
        dns_layer = packet[DNS]
        print("DNS Header:")
        print(dns_layer.show())

        if packet.haslayer(DNSQR):
            print("DNS Query:")
            dns_query = packet[DNSQR]
            print(dns_query.show())

        if packet.haslayer(DNSRR):
            print("DNS Response:")
            dns_response = packet[DNSRR]
            print(dns_response.show())

    else:
        print("Unknown or unsupported application layer protocol.")

在这个示例中，首先从example.pcap文件中读取数据包。然后，遍历每个数据包并检查它们是否包含HTTP请求、HTTP响应或DNS层。如果找到了这些层，我们就确定了应用层协议，并使用show()方法打印相应的头部信息。同时，Scapy并不支持所有应用层协议。

对于不支持的协议，可能需要编写自定义的解析器，或者使用其他库（如dpkt）来解析应用层数据。在这种情况下，可以使用Scapy来提取传输层（TCP或UDP）的有效载荷，然后将有效载荷传递给相应的解析器以提取应用层头部信息。

sklearn - Clustering

scikit-learn（简称sklearn）是一个用于Python编程语言的机器学习库。它提供了许多用于分类、回归、聚类、降维以及模型选择和预处理的算法。scikit-learn具有简单易用的API，且在性能和可扩展性方面表现良好，使其成为Python机器学习领域最受欢迎的库之一。

关于scikit-learn的信息和示例，请访问其官方网站：https://scikit-learn.org/stable/。

无监督数据的聚类可以使用 sklearn.cluster 模块来执行。

每个聚类算法都有两种变体：一种是类，实现了 fit 方法以在训练数据上学习聚类；另一种是函数，给定训练数据，返回一个整数标签数组，对应于不同的聚类。对于类来说，训练数据上的标签可以在 labels_ 属性中找到。

输入数据

需要注意的一件重要事情是，该模块中实现的算法可以接受不同类型的矩阵作为输入。所有方法都接受形状为（n_samples, n_features）的标准数据矩阵。这些可以从 sklearn.feature_extraction 模块的类中获取。对于 AffinityPropagation、SpectralClustering 和 DBSCAN，还可以输入形状为（n_samples, n_samples）的相似性矩阵。这些可以从 sklearn.metrics.pairwise 模块的函数中获得。

Overview of clustering methods

DBSCAN

The DBSCAN algorithm views clusters as areas of high density separated by areas of low density. Due to this rather generic view, clusters found by DBSCAN can be any shape, as opposed to k-means which assumes that clusters are convex shaped. The central component to the DBSCAN is the concept of core samples, which are samples that are in areas of high density. A cluster is therefore a set of core samples, each close to each other (measured by some distance measure) and a set of non-core samples that are close to a core sample (but are not themselves core samples). There are two parameters to the algorithm, min_samples and eps, which define formally what we mean when we say dense. Higher min_samples or lower eps indicate higher density necessary to form a cluster.

翻译：

DBSCAN 算法将聚类视为高密度区域，这些区域由低密度区域分隔开。由于这种相当通用的观点，DBSCAN找到的聚类可以是任何形状，而不是k-means假设聚类是凸形状。DBSCAN的核心组成部分是核心样本的概念，它们是位于高密度区域的样本。因此，一个聚类是一组核心样本，每个样本彼此靠近（通过某种距离度量来衡量），以及一组靠近核心样本的非核心样本（但它们本身不是核心样本）。该算法有两个参数，min_samples 和 eps，它们正式定义了我们在谈论密集时的含义。

较高的 min_samples 或较低的 eps 表示形成聚类所需的更高密度。

More formally, we define a core sample as being a sample in the dataset such that there exist min_samples other samples within a distance of eps, which are defined as neighbors of the core sample. This tells us that the core sample is in a dense area of the vector space. A cluster is a set of core samples that can be built by recursively taking a core sample, finding all of its neighbors that are core samples, finding all of their neighbors that are core samples, and so on. A cluster also has a set of non-core samples, which are samples that are neighbors of a core sample in the cluster but are not themselves core samples. Intuitively, these samples are on the fringes of a cluster.

翻译：

更正式地说，我们将数据集中的一个核心样本定义为：存在 min_samples 个其他样本在 eps 距离内，它们被定义为核心样本的邻居。这告诉我们核心样本位于向量空间的密集区域。一个聚类是一组核心样本，可以通过递归地选择一个核心样本，找到所有作为核心样本的邻居，找到它们所有作为核心样本的邻居，依此类推来构建。一个聚类还包括一组非核心样本，这些样本是聚类中核心样本的邻居，但它们本身不是核心样本。直观地说，这些样本位于聚类的边缘。

Any core sample is part of a cluster, by definition. Any sample that is not a core sample, and is at least eps in distance from any core sample, is considered an outlier by the algorithm.

翻译：

“根据定义，任何核心样本都是簇的一部分。任何非核心样本，只要与任何核心样本的距离至少为 eps，算法就将其视为离群点。

While the parameter min_samples primarily controls how tolerant the algorithm is towards noise (on noisy and large data sets it may be desirable to increase this parameter), the parameter eps is crucial to choose appropriately for the data set and distance function and usually cannot be left at the default value. It controls the local neighborhood of the points. When chosen too small, most data will not be clustered at all (and labeled as -1 for “noise”). When chosen too large, it causes close clusters to be merged into one cluster, and eventually the entire data set to be returned as a single cluster. Some heuristics for choosing this parameter have been discussed in the literature, for example based on a knee in the nearest neighbor distances plot (as discussed in the references below).

翻译：

尽管参数 min_samples 主要控制算法对噪声的容忍程度（在嘈杂和大型数据集上，可能需要增加此参数），但参数 eps 对于数据集和距离函数至关重要，通常不能保留默认值。它控制了点的局部邻域。当选择过小时，大部分数据根本不会被聚类（并被标记为 “-1” 表示“噪声”）。当选择过大时，它会导致相邻的簇合并成一个簇，最终整个数据集都被返回为一个簇。

文献中已经讨论了一些选择此参数的启发式方法，例如基于最近邻距离图的膝部。

In the figure below, the color indicates cluster membership, with large circles indicating core samples found by the algorithm. Smaller circles are non-core samples that are still part of a cluster. Moreover, the outliers are indicated by black points below.

翻译：

在下图中，颜色表示簇的成员关系，大圆圈表示算法找到的核心样本。较小的圆圈是仍然属于簇的非核心样本。此外，离群点用下方的黑色点表示。

Demo of DBSCAN clustering algorithm

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) finds core samples in regions of high density and expands clusters from them. This algorithm is good for data which contains clusters of similar density.

See the Comparing different clustering algorithms on toy datasets example for a demo of different clustering algorithms on 2D datasets.

1. Data generation

We use make_blobs to create 3 synthetic clusters.

from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler

centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(
    n_samples=750, centers=centers, cluster_std=0.4, random_state=0
)

X = StandardScaler().fit_transform(X)

这段代码的目的是生成一个包含3个簇的合成数据集，并对其进行标准化。接下来，我们将详细分析这段代码的每一部分。

导入必要的库：

from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler

make_blobs 函数用于生成符合高斯分布的数据集，通常用于聚类或分类算法的测试。StandardScaler 类用于对数据进行标准化处理。

定义簇中心：

centers = [[1, 1], [-1, -1], [1, -1]]

这里，我们定义了3个簇中心，分别为 (1, 1)、(-1, -1) 和 (1, -1)。

生成数据集：

X, labels_true = make_blobs(
    n_samples=750, centers=centers, cluster_std=0.4, random_state=0
)

使用 make_blobs 函数生成包含750个样本的数据集。这里，n_samples 参数定义了数据集中样本的数量，centers 参数定义了簇中心的坐标，cluster_std 参数定义了每个簇的标准差（控制簇的紧密程度），random_state 参数用于设置随机数生成器的种子以确保结果的可重复性。

make_blobs 函数返回两个值：X 是一个包含750个样本的二维数组，labels_true 是一个包含每个样本所属簇的真实标签的一维数组。

数据标准化：

X = StandardScaler().fit_transform(X)

使用 StandardScaler 类对数据集进行标准化处理。标准化是将数据的均值转换为0，标准差转换为1的过程。这对于许多机器学习算法（特别是基于距离的算法）非常重要，因为它确保所有特征具有相同的尺度。fit_transform 方法首先计算数据集的均值和标准差，然后使用这些值将数据集转换为标准化形式。

至此，我们已经成功生成了一个包含3个簇的合成数据集 X 并对其进行了标准化处理。

We can visualize the resulting data:

import matplotlib.pyplot as plt

plt.scatter(X[:, 0], X[:, 1])
plt.show()

2. Compute DBSCAN

One can access the labels assigned by DBSCAN using the labels_ attribute. Noisy samples are given the label math:-1.

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn import metrics

db = DBSCAN(eps=0.3, min_samples=10).fit(X)
labels = db.labels_

# Number of clusters in labels, ignoring noise if present.
n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)
n_noise_ = list(labels).count(-1)

print("Estimated number of clusters: %d" % n_clusters_)
print("Estimated number of noise points: %d" % n_noise_)

Output:
Estimated number of clusters: 3
Estimated number of noise points: 18

这段代码的目的是使用DBSCAN算法对之前生成的数据集进行聚类，并输出聚类结果的统计信息。接下来，我们将详细分析这段代码的每一部分。

导入必要的库：

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn import metrics

numpy 是一个用于处理数组和矩阵的库。DBSCAN 类来自 sklearn.cluster，用于实现DBSCAN聚类算法。metrics 模块包含用于评估聚类性能的指标。

对数据集进行DBSCAN聚类：

db = DBSCAN(eps=0.3, min_samples=10).fit(X)

使用 DBSCAN 类创建一个DBSCAN聚类器的实例，设置参数 eps 为 0.3 和 min_samples 为 10。然后，使用 fit 方法对数据集 X 进行聚类。

minpts（论文中提到的最小点数）是DBSCAN算法的一个参数。在 sklearn.cluster.DBSCAN 类中，它对应于参数 min_samples。minpts（或 min_samples）用于确定在一个簇内的某个数据点周围必须有多少个邻居才能将该数据点视为核心点。换句话说，如果在一个数据点的邻域（半径为 eps）中有至少 minpts 个其他数据点，那么这个数据点就被认为是一个核心点。

DBSCAN算法基于密度的概念对数据集进行聚类。在DBSCAN中，一个簇是一个密度相连的区域，与其他簇的密度相隔离。minpts 参数在确定一个簇的密度时起着关键作用。

如果将 minpts 设得过小，那么可能会将噪声点误分类为核心点，导致聚类结果不稳定。相反，如果将 minpts 设得过大，可能会导致簇之间的界限不明确，使一些本应属于同一簇的点被分开。因此，选择合适的 minpts 值对于获得好的聚类结果至关重要。

获取聚类标签：

labels = db.labels_

db.labels_ 属性包含每个样本的聚类标签。噪声点将被赋予标签 -1。

计算聚类数量和噪声点数量：

n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)
n_noise_ = list(labels).count(-1)

n_clusters_ 计算去除噪声点后的簇的数量。首先，通过创建一个标签集合并计算其长度来获取唯一标签的数量。然后，如果 -1（表示噪声）在标签中，从簇的数量中减去1。

n_noise_ 计算标签中噪声点的数量。首先将标签转换为列表，然后使用 count 方法统计 -1（表示噪声）的出现次数。

输出聚类结果统计信息：

print("Estimated number of clusters: %d" % n_clusters_)
print("Estimated number of noise points: %d" % n_noise_)

打印估计的簇数量和噪声点数量。

Clustering algorithms are fundamentally unsupervised learning methods. However, since make_blobs gives access to the true labels of the synthetic clusters, it is possible to use evaluation metrics that leverage this “supervised” ground truth information to quantify the quality of the resulting clusters.

翻译：

聚类算法基本上是无监督学习方法。然而，由于 make_blobs 提供了对合成簇真实标签的访问，因此可以使用利用这种“监督”基准信息的评估指标来量化生成簇的质量。

Examples of such metrics are the homogeneity, completeness, V-measure, Rand-Index, Adjusted Rand-Index and Adjusted Mutual Information (AMI).If the ground truth labels are not known, evaluation can only be performed using the model results itself. In that case, the Silhouette Coefficient comes in handy.

翻译：

这些指标的例子有同质性、完整性、V-度量、Rand-Index、调整后的 Rand-Index 和调整后的互信息（AMI）。如果不知道真实标签，评估只能使用模型本身的结果来进行。在这种情况下，轮廓系数非常有用。

For more information, see the Adjustment for chance in clustering performance evaluation example or the Clustering performance evaluation module.

更多信息，请参见聚类性能评估中的机会调整示例或聚类性能评估模块。

print(f"Homogeneity: {metrics.homogeneity_score(labels_true, labels):.3f}")
print(f"Completeness: {metrics.completeness_score(labels_true, labels):.3f}")
print(f"V-measure: {metrics.v_measure_score(labels_true, labels):.3f}")
print(f"Adjusted Rand Index: {metrics.adjusted_rand_score(labels_true, labels):.3f}")
print(
    "Adjusted Mutual Information:"
    f" {metrics.adjusted_mutual_info_score(labels_true, labels):.3f}"
)
print(f"Silhouette Coefficient: {metrics.silhouette_score(X, labels):.3f}")

Output:
Homogeneity: 0.953
Completeness: 0.883
V-measure: 0.917
Adjusted Rand Index: 0.952
Adjusted Mutual Information: 0.916
Silhouette Coefficient: 0.626

Plot results

Core samples (large dots) and non-core samples (small dots) are color-coded according to the asigned cluster. Samples tagged as noise are represented in black.

unique_labels = set(labels)
core_samples_mask = np.zeros_like(labels, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True

colors = [plt.cm.Spectral(each) for each in np.linspace(0, 1, len(unique_labels))]
for k, col in zip(unique_labels, colors):
    if k == -1:
        # Black used for noise.
        col = [0, 0, 0, 1]

    class_member_mask = labels == k

    xy = X[class_member_mask & core_samples_mask]
    plt.plot(
        xy[:, 0],
        xy[:, 1],
        "o",
        markerfacecolor=tuple(col),
        markeredgecolor="k",
        markersize=14,
    )

    xy = X[class_member_mask & ~core_samples_mask]
    plt.plot(
        xy[:, 0],
        xy[:, 1],
        "o",
        markerfacecolor=tuple(col),
        markeredgecolor="k",
        markersize=6,
    )

plt.title(f"Estimated number of clusters: {n_clusters_}")
plt.show()