为专有VM格式编写反汇编器的解析器生成器

Question

我正在尝试编写Mindstorms EV3 VM二进制文件的反汇编器，最好使用Python进行编写，因为我非常熟悉它。 我有详细说明指令集，操作码，参数，数据类型等文档，可在此处找到，但我无法从中构建出一个实际的反汇编器。

据我所知，编写反汇编器与编写编译器并没有太大的区别，只是一个更加复杂的确定性有限状态机。 然而，除此之外，我找不到任何关于如何编写反汇编器的书籍或指南。我尝试使用编译器编写工具，如Lex和Yacc（或在Python中使用PLY），但是所有这些工具都无法满足我的需求。

Lex和Yacc组合似乎不适用于我想要做的事情，因为它执行与我想要做的相反的操作。它从文本生成标记，然后将其转换为字节码，而我有字节码，想将其转换为标记，然后再将其转换为文本。在我看来，我唯一的选择是编写自己的解析器生成器，但我想避免这样做，因为这似乎需要很多工作。

我还面临的另一个问题是我不知道如何处理以null结尾的字符串和参数编码（某些参数由带有特定位设置的字节前缀，告诉VM要期望什么长度和类型，这意味着我不能用简单的DFA以字节级别解析整个字节码）。

那么，如何编写此类格式的反汇编器？

- Azsgy

---

你是对的，你需要进行反向操作。但是使用词法分析器和Yacc组合并不完全不能实现这一点。您需要预处理输入，以便能够将有意义的输入提供给词法分析器，或编写自己的词法分析器，接受字节而不是字符（尽管字符只是基于字符集转换的字节）。您读取的每个字节确定了随后可接受的输入及其长度，因此如果某个位被设置，则仅意味着您读取了不同的字节值并处于不同的状态。 - Ma3x

请记住，根据用途不同，这可能违反所购买产品的规定（最终用户协议）。不确定这是否符合您的要求，但可以在此处查看一些想法：https://github.com/ev3dev/lms-hacker-tools/blob/master/EV3/lmsdisasm.py - Ma3x

我用Python（Krakatau）编写了一个Java类文件反汇编器，这可能会对你有所帮助。我真的不认为有什么难点。你不需要任何花哨的框架，只需编写代码来实现你想要的功能即可。 - Antimony

解析器生成器是处理具有复杂语法输入的工具。由于编译代码旨在高效执行，因此它自然与之完全相反。因此，将解析器生成器等工具纳入其中是过度的，会增加您的工作量而不是减少它。对于大多数格式，可以将反汇编器实现为直接单遍转换器。 - Holger

@Holger 好的，如果Ira的答案不起作用，看起来我会选择那个。 - Azsgy

Answer 1

编写二进制反汇编器实际上意味着您想要指定二进制数据的模式以及解码实体之间的关系（如果您识别出两个指令，则合理地假设它们不重叠）。

传统的解析器并不擅长这样做（尽管您可以为一系列指令编写语法，假设单个位或字节作为标记；您仍然需要处理指令序列之间的间隙）。

我见过的最聪明的方法是由Norman Ramsey和他的团队开发的一个名为SLED的工具，它允许您为二进制数据编写简洁的模式，并将其自动组装成二进制编码器和解码器。这篇研究论文讨论了SLED和一些类似的系统。一个关键点：这些远不止于“解析器生成器”，但概念相似：许多模式用于描述数据，代码生成器将这些模式组装成一个有效的引擎来匹配它们。

为了让你了解这些工具的外观，我提供了一个基于我在这个领域的一些工作的部分 x86-64 编码片段。其想法是定义带有约束条件的命名模式，以便最终可以编写指令定义。以下是一个小部分的简要示例（整个代码大约有 1200 行）：

datatype SIB
 { ScaleSize:     unsigned encoding { Times1=0 Times2=1 Times4=2 Times8=3} 2 bits
   ScaledIndex:   unsigned encoding { EAX=0 ECX=1 EDX=2 EBX=3 none=4 EBP=5         ESI=6 EDI=7 } 3 bits
   IndexRegister: unsigned encoding { EAX=0 ECX=1 EDX=2 EBX=3 ESP=4  EBP,disp32=5  ESI=6 EDI=7 } 3 bits
 }

encoding Grp1     { ADD=0 OR ADC SBB AND SUB XOR CMP }
encoding Grp1A    { POP=0 * * * * * * * }
encoding Grp2     { ROL=0 ROR RCL RCR SHL,SAL SHR  * SAR }
encoding Grp3     { TESTIbIz=0 * NOT NEG MULAX,MULrAX IMULAL,IMULrAX DIVAL,DIVrAX IDIVAL,IDIVrAX }
encoding Grp4     { INCEb=0  DECEb * * * * * * }
encoding Grp5     { INCEv=0  DECEv CALLNEv CALLFEp  JMPNEv JMPFEp  PUSHEv * }
encoding Grp6     { SLDTRvMW=0 STRRvMw LLDTEw LTREw VERREw VERWEw * * }
encoding Grp7mem  { SGDTMs=0                          SIDTMs        LGDTMs LIDTMs SMSWMwRv * LMSWEw INVLPGMb }
encoding Grp7reg  { VMCALL,VMLAUNCH,VMRESUME,VMXOFF=0 MONITOR,MWAIT *      *      SMSWMwRv * LMSWEw SWAPGS }
encoding Grp8     { *=0 * * * BT BTS BTR BTC }
encoding Grp9mem  { * CMPXCH8BMq,CMPXCH16BMdq * * * * VMPTRLDMq,VMCLEARMq,VMXONMq VMPTRSTMq }
encoding Grp9reg  { *=0 * * * * * * * }
encoding Grp10    { * * * * * * * }
encoding Grp11Ib  { MOVEbIb * * * * * * * }
encoding Grp11Iz  { MOVEvIz * * * * * * * }
encoding Grp12mem { * * * * * * * * }
encoding Grp12reg { *=0 * * PSRLWNqIb,PSRLWUdqIb *             PSRAWNqIb,PSRAWUdqIb * PSLLWNqIb,PSLLWUdqIb * }
encoding Grp13mem { * * * * * * * * }
encoding Grp13reg { *=0 * * PSRLDNqIb,PSLRDUdqIb *             PSRADNqIb,PSRADUdqIb * PSLLDNqIb,PSLLDUdqIb * }
encoding Grp14mem { * * * * * * * * }
encoding Grp14reg { *=0 * * PSRLQNqIb,PSRLQUdqIb  PSRLDQUdqIb  *                    * PSLLQNqIb,PSLLQUdqIb PSLLDQUDqIb }
encoding Grp15mem { FXSAVE=0 FXRSTOR LDMXCSR STMXCSR * * * CFLUSH }
encoding Grp15reg { *=0 * * * LFENCE MFENCE SFENCE }
encoding Grp16mem { PREFETCHNTA=0 PREFETCHT0 PREFETCHT1 PREFETCHT2 * * * } 
encoding Grp16reg { * * * * * * * * }

...

instruction { ADCr64Immediate => Grp1.ADC
      ADDr64Immediate => Grp1.ADD
      ANDr64Immediate => Grp1.AND
      CMPr64Immediate => Grp1.CMP
      ORr64Immediate  => Grp1.OR
      SBBr64Immediate => Grp1.SBB
      SUBr64Immediate => Grp1.SUB
      XORr64Immediate => Grp1.XOR
    }
   (Target: Register32, Immediate: signed 32 bits)
   BasicInstruction
   & prefix_length0
   & if Intel64 => prefix_REX(W=On R=Target:3)
   & OneByteOpcode & Subcode=ImmGrp1EvIz
   & ModRM(Mod=reg RSlashM=Target:2-0 reg=*)

如果你只是解码一个简单的虚拟机和一组简单的指令，也许你不需要所有这些能力，因为“简单的虚拟机”不会将位打包或将数据分割成字节边界，并且/或者你可以通过一些违反这些假设的情况来进行黑客攻击。随着人们的虚拟机变得更加复杂（它们经过多年的演化），它们必然变得更加复杂。YMMV。

- Ira Baxter