독점 VM 형식의 디스어셈블러를 작성하기위한 파서 생성기

Question

Mindstorms EV3 VM 바이너리에 대한 디스어셈블러를 작성하려고합니다. 나는 설명서를 설정하는 지시, opcodes, 매개 변수, 데이터 형식 등 available here입니다하지만 난 실제 해체를 구축하는 데 문제가 있습니다.

내가 알고 있듯이, 디스어셈블러를 작성하는 것은 컴파일러를 작성하는 것과 별반 다르지 않으며, 그것은 단지 영광 스럽은 결정 론적 유한 상태 기계입니다. 그러나 그 이상으로 나는 서적이나 서적을 구할 수 없다. 필자는 Lex와 Yacc (또는 Python PLY)와 같은 컴파일러 작성 도구를 사용하려고 시도했지만 모든 도구가 어떤 식 으로든 실패합니다.

Lex와 Yacc 콤보는 내가하고 싶은 것과 반대로하기 때문에 사용할 수있는 것으로 보이지 않습니다. 텍스트에서 토큰을 생성 한 다음 바이트 코드로 바꾸고 바이트 코드를 토큰으로 변환하여 텍스트로 변환합니다. 필자가 볼 수있는 유일한 옵션은 필자 자신의 파서 생성기를 작성하는 것인데, 나는 그것이 많은 작업처럼 보이기 때문에 피하고 싶다.

또 다른 문제는 null로 끝나는 문자열 및 매개 변수 인코딩과 같은 문제를 처리하는 방법을 모르겠다는 것입니다. 일부 인수에는 예상 길이와 유형을 VM에 알려주는 특정 비트가있는 바이트가 접두어로 붙습니다. 바이트 크기에서 간단한 DFA로 전체 바이트 코드를 파싱 할 수 없다는 것을 의미하는 것으로 추정 됨)

어떻게 이런 형식의 디스어셈블러를 작성하겠습니까?

Answer 1

이진 디스어셈블러를 쓰는 것은 실제로 바이너리 데이터의 패턴과 디코드 엔티티 간의 관계를 지정하려는 것을 의미합니다. 두 개의 명령어를 인식하면 겹치지 않는다고 가정하는 것이 합리적입니다.

종래의 파서는이 작업을 매우 잘 수행하지 않습니다. 개별 비트 또는 바이트를 토큰으로 가정하는 일련의 명령어에 대한 문법을 ​​작성할 수 있지만, 여전히 인스턴스 작성 시퀀스 사이의 틈을 처리해야합니다.

내가 본 가장 현명한 접근 방식은 Norman Ramsey와 그의 팀에서 SLED라고하는 도구입니다.이 도구는 바이너리 데이터에 대한 간결한 패턴을 작성하고이를 바이너리 인코더와 디코더로 자동 어셈블 할 수있게합니다. 이 research paper discusses SLED 및 여러 유사한 시스템. 요점 : "파서 생성기"이상의 개념이지만 개념은 비슷합니다. 데이터를 설명하는 패턴이 많으며 패턴을 효율적인 엔진으로 조합하여 모두 일치시키는 코드 생성기입니다.

이러한 도구의 모양을 알려주기 위해 필자는이 영역에서 수행 한 일부 작업을 기반으로 한 부분적인 x86-64 인코딩 조각을 제공합니다. 아이디어는 결국 명령 정의를 작성할 수 있도록 작성한 명명 된 패턴 (제약 조건 포함)을 정의하는 것입니다. 여기에 작은 부분에 대한 간단한 샘플입니다 (모든 일이 몇 가지 1,200 선입니다) : 당신이 정말로 간단한 명령어 세트와 단지 간단한 가상 머신을 디코딩하는 경우

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=*) 

, 어쩌면 당신은 모든 필요가 없습니다 "단순 VM"이 비트를 압축하거나 바이트 경계를 넘어 데이터를 분할하지 못하거나 이러한 가정을 위반하는 몇 가지 사례를 해킹 할 수 있기 때문에이 기능을 사용할 수 있습니다. 사람들의 VM이 점점 복잡해지면서 (수년에 걸쳐 진화하면서), VM은 점점 더 복잡해집니다. YMMV.