对齐结构列表以进行补丁分析
Aligning lists of structs for patch analysis
我目前正在对一款定期更新的多人游戏进行逆向工程。网络协议使用自定义序列化框架，我现在能够恢复有关正在交换的消息的大量信息。对于每条消息，我可以检索所述消息的完整结构和该消息的类型（例如身份验证、聊天、移动...）。但是，我遇到的一个问题是定期添加和删除消息和消息类型，并且消息可能添加或删除了字段。 消息的总体顺序和消息类型保持不变！
我现在正在寻找一种方法来最好地利用我必须将更新的消息结构与我已经确定了某些消息和字段的含义的旧消息结构相匹配的信息。也就是说，给定如下两组消息，我如何传输已经被逆向工程的信息（新消息中的注释）？
旧消息：
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.
的解决方案
更好、更可持续的解决方案是重新设计生成消息的系统，使其与名称和格式保持一致。这将使它更具可扩展性。
如果这确实不是一个选项，您可能想通过使用 Levenshtein 等库计算字符串差异来探索一种可能的算法。在这里，让我们关注最外层的数据（类型）。只需对内部数据（消息和字段）执行相同的概念。
假设这些是旧消息和新消息中类型之间的匹配：
Old Messages
New Messages
Remarks
O1
N1
N2
new
N3
new
O2
N4
O3
N5
O4
deleted
O5
deleted
N6
new
O6
N7
N8
new
其中：
- 旧消息的示例，例如
O1:
Authentication:
message Login:
opcode: 1
fields:
- string mail
- string password
- 新消息的示例，例如
N1:
Type1:
message Unk1:
opcode: 1
fields:
- string unk1
- string unk2
- string unk3
对于每条旧消息，计算每条新消息的编辑距离和select最小距离。最小距离表示它是最接近的等效字符串。假设下面的数字是每个 Ox 的计算距离：Ny 对
O#
N1
N2
N3
N4
N5
N6
N7
N8
Smallest Distance
O1
3
10
7
11
14
8
5
12
N1
O2
8
9
6
2
9
7
8
17
N4
O3
9
7
7
9
3
13
7
6
N5
O4
7
9
8
15
16
6
3
10
N7
O5
5
7
9
8
11
4
10
5
N6
O6
9
6
7
8
8
14
1
11
N7
但是由于消息的顺序保持不变，O4 映射到 N7 而 O5 映射到更早的 N6 是错误的。 O6 也是错误的，因为它映射到相同的 N7。现在我们必须在选择最小距离之前执行额外的步骤
- 检查是否将较早的
O 映射到等于或晚于当前选择的 N 的 N，例如当较早的 O4 映射到较晚的 N7 时，这里是 O5 映射到 N6。
- 如果存在，请检查 所有 之前
O 是否比当前 N 更接近它们的映射 N。
- 如果所有较早的
O 都更接近他们的 N，那么我们无法更改它，因为它的相似性比当前的更接近。相反，我们会尝试选择到当前 O 的第二小距离并重复相同的步骤。
- 但是如果当前
O 映射到当前选择的 N 比之前的 O 更接近它们各自的 N，那么我们会选择当前选择 N 作为当前 O。然后我们会将所有使用相同或更高版本 N 的较早 O 标记为已删除。
通过这些额外的步骤，更新后的 table 将是：
O#
N1
N2
N3
N4
N5
N6
N7
N8
Smallest Distance
O1
3
10
7
11
14
8
5
12
N1
O2
8
9
6
2
9
7
8
17
N4
O3
9
7
7
9
3
13
7
6
N5
O4
7
9
8
15
16
6
3
10
N7 Deleted
O5
5
7
9
8
11
4
10
5
N6 N8 Deleted
O6
9
6
7
8
8
14
1
11
N7
如您所见，O5 从 N6（距离 4）重新映射到 N8（距离 5），因为 O4 使用了稍后的 N7。但是随后两者都被标记为已删除，因为 O6 被映射到 N7，它更接近（距离为 1）较早的 O，后者使用 N 等于或晚于 N7（即O4和O5）。
现在，我们知道：
O1 是 N1O2 是 N4O3 是 N5O4被删除O5被删除O6 是 N7- 而所有未选择的
N 是新添加的，即 N2、N3、N6、N8
我目前正在对一款定期更新的多人游戏进行逆向工程。网络协议使用自定义序列化框架，我现在能够恢复有关正在交换的消息的大量信息。对于每条消息，我可以检索所述消息的完整结构和该消息的类型（例如身份验证、聊天、移动...）。但是，我遇到的一个问题是定期添加和删除消息和消息类型，并且消息可能添加或删除了字段。 消息的总体顺序和消息类型保持不变！
我现在正在寻找一种方法来最好地利用我必须将更新的消息结构与我已经确定了某些消息和字段的含义的旧消息结构相匹配的信息。也就是说，给定如下两组消息，我如何传输已经被逆向工程的信息（新消息中的注释）？
旧消息：
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.
的解决方案更好、更可持续的解决方案是重新设计生成消息的系统，使其与名称和格式保持一致。这将使它更具可扩展性。
如果这确实不是一个选项，您可能想通过使用 Levenshtein 等库计算字符串差异来探索一种可能的算法。在这里，让我们关注最外层的数据（类型）。只需对内部数据（消息和字段）执行相同的概念。
假设这些是旧消息和新消息中类型之间的匹配：
| Old Messages | New Messages | Remarks |
|---|---|---|
| O1 | N1 | |
| N2 | new | |
| N3 | new | |
| O2 | N4 | |
| O3 | N5 | |
| O4 | deleted | |
| O5 | deleted | |
| N6 | new | |
| O6 | N7 | |
| N8 | new |
其中：
- 旧消息的示例，例如
O1:
Authentication:
message Login:
opcode: 1
fields:
- string mail
- string password
- 新消息的示例，例如
N1:
Type1:
message Unk1:
opcode: 1
fields:
- string unk1
- string unk2
- string unk3
对于每条旧消息，计算每条新消息的编辑距离和select最小距离。最小距离表示它是最接近的等效字符串。假设下面的数字是每个 Ox 的计算距离：Ny 对
| O# | N1 | N2 | N3 | N4 | N5 | N6 | N7 | N8 | Smallest Distance |
|---|---|---|---|---|---|---|---|---|---|
| O1 | 3 | 10 | 7 | 11 | 14 | 8 | 5 | 12 | N1 |
| O2 | 8 | 9 | 6 | 2 | 9 | 7 | 8 | 17 | N4 |
| O3 | 9 | 7 | 7 | 9 | 3 | 13 | 7 | 6 | N5 |
| O4 | 7 | 9 | 8 | 15 | 16 | 6 | 3 | 10 | N7 |
| O5 | 5 | 7 | 9 | 8 | 11 | 4 | 10 | 5 | N6 |
| O6 | 9 | 6 | 7 | 8 | 8 | 14 | 1 | 11 | N7 |
但是由于消息的顺序保持不变，O4 映射到 N7 而 O5 映射到更早的 N6 是错误的。 O6 也是错误的，因为它映射到相同的 N7。现在我们必须在选择最小距离之前执行额外的步骤
- 检查是否将较早的
O映射到等于或晚于当前选择的N的N，例如当较早的O4映射到较晚的N7时，这里是O5映射到N6。- 如果存在，请检查 所有 之前
O是否比当前N更接近它们的映射N。- 如果所有较早的
O都更接近他们的N，那么我们无法更改它，因为它的相似性比当前的更接近。相反，我们会尝试选择到当前O的第二小距离并重复相同的步骤。 - 但是如果当前
O映射到当前选择的N比之前的O更接近它们各自的N，那么我们会选择当前选择N作为当前O。然后我们会将所有使用相同或更高版本N的较早O标记为已删除。
- 如果所有较早的
- 如果存在，请检查 所有 之前
通过这些额外的步骤，更新后的 table 将是：
| O# | N1 | N2 | N3 | N4 | N5 | N6 | N7 | N8 | Smallest Distance |
|---|---|---|---|---|---|---|---|---|---|
| O1 | 3 | 10 | 7 | 11 | 14 | 8 | 5 | 12 | N1 |
| O2 | 8 | 9 | 6 | 2 | 9 | 7 | 8 | 17 | N4 |
| O3 | 9 | 7 | 7 | 9 | 3 | 13 | 7 | 6 | N5 |
| O4 | 7 | 9 | 8 | 15 | 16 | 6 | 3 | 10 | |
| O5 | 5 | 7 | 9 | 8 | 11 | 4 | 10 | 5 | |
| O6 | 9 | 6 | 7 | 8 | 8 | 14 | 1 | 11 | N7 |
如您所见，O5 从 N6（距离 4）重新映射到 N8（距离 5），因为 O4 使用了稍后的 N7。但是随后两者都被标记为已删除，因为 O6 被映射到 N7，它更接近（距离为 1）较早的 O，后者使用 N 等于或晚于 N7（即O4和O5）。
现在，我们知道：
O1是N1O2是N4O3是N5O4被删除O5被删除O6是N7- 而所有未选择的
N是新添加的，即N2、N3、N6、N8