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

Question

我正在尝试为 Mindstorms EV3 VM 二进制文件编写反汇编程序，最好是 Python，因为我对它非常熟悉。我有详细说明指令集、操作码、参数、数据类型等的文档 available here 但我无法从中构建实际的反汇编程序。

据我了解，编写反汇编程序与编写编译器没有太大区别，因为它只是一个美化的确定性有限状态机。然而，除此之外，我找不到任何关于写作的书籍或指南。我尝试使用编译器编写工具，例如 Lex 和 Yacc（或 python PLY），但是所有这些工具都以某种方式让我失望。

Lex 和 Yacc 组合似乎不是我可以使用的东西，因为它与我想做的相反。它从文本生成标记，然后将其转换为字节码，而我有字节码并想将其转换为标记，然后再将其转换为文本。在我看来，我唯一的选择是编写自己的解析器生成器，我想避免这样做，因为它看起来工作量很大。

我遇到的另一个问题是我不知道如何处理诸如以 null 结尾的字符串和参数编码之类的事情（一些参数以一个字节为前缀，其中设置了某些位告诉 VM 期望的长度和类型，我认为这意味着我无法在字节级别使用简单的 DFA 解析整个字节码）

我该如何为这样的格式编写反汇编程序？

Answer 1

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

传统的解析器并不能很好地做到这一点（尽管您当然可以为一系列指令编写语法，假设单个位或字节作为标记；您仍然必须处理指令序列之间的间隙）。

我见过的最聪明的方法是 Norman Ramsey 和他的团队开发的名为 SLED 的工具，它可以让您为二进制数据编写简洁的模式，然后 assemble 将其自动转换为二进制编码器和解码器.这research paper discusses SLED和一些类似的系统。关键点：这些远不止 "parser generator" 但概念相似：许多模式来描述数据，代码生成器 assemble 将模式转换为高效引擎以匹配它们。

为了让您了解这些工具的外观，我根据我在该领域所做的一些工作提供了部分 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=*)

如果你真的要解码只是一个带有简单指令集的简单虚拟机，也许你不需要所有这些功能，因为"simple VM"不需要'不要跨字节边界打包位或拆分数据，and/or 您可以破解违反这些假设的少数情况。随着人们的 VM 变得越来越复杂（它们经过多年发展），它们必然会变得更加复杂。 YMMV.

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

Parser generator for writing a disassembler for a proprietary VM format

parsing

bytecode

disassembly

parser-generator