对齐用于面片分析的结构列表

Question

我目前正在逆向工程一个定期更新的多人游戏。网络协议使用了一个定制的序列化框架，我现在能够恢复关于正在交换的消息的大量信息。对于每条消息，我可以检索所述消息的完整结构和该消息的类型（例如身份验证、聊天、移动…）。然而，我遇到的一个问题是，消息和消息类型会定期添加和删除，而且消息可能会添加或删除字段消息和消息类型的总体顺序保持不变

我现在正在寻找一种方法，如何最好地利用我所拥有的信息，将更新的消息结构与旧的消息结构相匹配，在旧的消息结构中，我已经确定了一些消息和字段的含义。也就是说，给定如下两组消息，我如何传输已经反向工程的信息（新消息中的注释）

旧消息：

Authentication:
 message Login:
  opcode: 1
  fields:
  - string mail
  - string password

 message LoginResponse:
  opcode: 2
  fields:
  - string token

Chat:
 message ChatSend:
  opcode: 3
  fields:
  - string channel
  - string message
 message ChatReceive:
  opcode: 4
  fields:
  - string channel
  - string user
  - string message

新消息：

Type1: # Authentication
 message Unk1: # Login
  opcode: 1
  fields:
  - string unk1 # mail
  - string unk2 # password
  _ string unk3 # new field
  
 message Unk2: # LoginResponse
  opcode: 2
  fields:
  - string unk1 # token

Type2: # new Type
  message Unk3:
   opcode: 3
   fields:
   - Vec3 unk1
   - float unk2

Type3: # Chat
 message Unk4: # ChatSend
  opcode: 4
  fields:
  - string unk1 # channel
  - string unk2 # message
 message Unk5: # new message
  opcode: 5
  fields:
  - string unk1
  - string unk2
 message Unk6: # ChatReceive
  opcode: 6
  fields:
  - string unk1 # channel
  - string unk2 # user
  - string unk3 # message

一些附加信息：大约有60种不同类型的消息，每种消息类型最多大约有100条消息。我也欢迎使用伪代码或python的解决方案

Answer 1

更好、更可持续的解决方案是重新设计生成与名称和格式一致的消息的系统。这将使它更具可扩展性

如果这真的不是一个选项，那么您可能希望通过使用Levenshtein之类的库计算字符串差异来探索一种可能的算法。这里，让我们关注最外层的数据（类型）。只需对内部数据（消息和字段）执行相同的概念

假设这些是新旧消息中类型之间的匹配：

^{tb1}$

其中：

• 旧消息的一个示例，例如O1：

Authentication:
 message Login:
  opcode: 1
  fields:
  - string mail
  - string password

• 新消息的示例，例如N1：

Type1:
 message Unk1:
  opcode: 1
  fields:
  - string unk1
  - string unk2
  - string unk3

对于每个旧消息，计算到每个新消息的Levenshtein距离，并选择最小距离。最小距离表示它是最近的等效字符串。让我们假设下面的数字是每个Ox:Ny对的计算距离

^{tb2}$

但是由于消息的顺序保持不变，O4映射到N7，而O5映射到前面的N6是错误的。而且O6是错误的，因为它映射到相同的N7。现在，在选择最小距离之前，我们必须执行其他步骤

• 检查较早的O是否映射到当前选择的N之后的N例如，当较早的O4映射到较晚的N7时，这里是O5映射到N6。
  • 如果存在，请检查早期O的所有是否比当前的N更接近其映射的N。
    • 如果所有这些早期的O都更接近它们的N，那么我们不能改变它，因为它的相似性比当前的更接近。相反，我们将尝试选择到当前O的第二个最小距离，并重复相同的步骤
    • 但是，如果当前的O映射到当前选择的N，而不是之前的任何一个O映射到它们各自的N，那么我们将为当前的O选择当前选择的N。然后，我们将所有使用相等或更晚的N的早期O标记为已删除

通过这些附加步骤，更新后的表格将是：

^{tb3}$

正如您所看到的，O5被从N6（距离4）重新映射到N8（距离5），因为O4使用了后面的N7。但是，由于O6被映射到N7，而N7与使用N等于或晚于N7（即O4和O5的较早的O的距离更近（1）

现在，我们知道：

• O1是N1
• O2是N4
• O3是N5
• O4被删除
• O5被删除
• O6是N7
• 而所有未关闭的N都是新添加的，即N2、N3、N6、N8