Question

句法分析程序是反编译器的第一个阶段。它所扮演的角色是把一个字节序列组织成该语言的一个短语或语句。检查这个字节序列的句法结构，即该语言拥有的字符串。有效的字符串用一个语法分析树表示出来，做为下一个阶段 (语义分析程序) 的输入。句法分析程序与语义分析程序之间的关系见图 4-2 所示。语法分析器(parser) 即句法分析程序(syntax ananlyzer)。

图 4-2: 语法分析器和语义分析程序之间的交互

机器语言的句法能够用语法准确地加以规定。在机器语言中，只规定了指令或语句；而没有象高级语言那样规定控制结构。一般来说，任何语言规定都是通过语法做出准确的注解。

反编译器语法分析器的主要困难是区分代码和数据，亦即，确定内存里哪些字节是代码、哪些字节是数据。这个问题源自冯·诺依曼体系结构的先天不足，因此需要用启发式 (试探方法) 来解决。

句法错误

二进制程序中几乎不会出现语法错误，编译器总是为被编译的程序生成能够在机器上正确运行的代码。但是，假如机器体系结构升级产生新的机器——它支持所有前任机器，新体系结构的机器指令集是旧体系结构机器指令集的一个扩展。i80486 就是如此，它支持所有前任 i8086、i80186、i80286 和 i80386 的指令集。因此，如果为 i8086 编写一个语法分析器，那么它不能识别所有新的机器指令从而必定造成一个错误。反之，如果语法分析器是为最新的机器 i80486 编写的，那么所有的指令应该都会被识别，可能不会遇到语法错误的情况。

4.1.1 有限状态自动机

有限状态自动机(FSA) 是一个语言识别程序。输入一个字符串，如果对于该语言是有效的它回答 yes，否则回答 no。字符串即是某个给定字母表的一个符号序列。任意给定一个字符串，FSA 能够确定它是不是该语言的有效字符串。

定义 1

一个 有限状态自动机 是一个数学模型，它由以下组成：

l 一个有限状态集 S

l 一个初始状态 s0

l 一个最终状态或接受状态集 F

l 一个输入符号字母表∑

l 一个转变函数 T：state×symbol → state

FSA 可以用转变图(transition diagram) 来图形化地表现。这些图的组成如图 4-3 所示。字母表符号标示了状态的转变。在转变图中没有显式地表现错误的转变，而是以任何非有效符号标签隐含地表现从一个状态到一个错误状态的转变。

图 4-3: FSA 转变图的组成

通配符语言是一个元语言，用于在一个语言中指定通配符条件 [Gou88]。两个元符号是‘*’和‘%’。元符号‘*’代表任何由零个或者更多个字母表∑的符号组成的序列，‘%’代表任何一个单一的字母表符号。

例子 1

令 ∑=f {a, b, c}。以通配符表达式 a*说明，该语言接受任何以 a 开头的字符串。用一个 FSA 表示如下：

非确定性的有限状态自动机

每当一个状态有两个或多个转变是用相同的符号标示的，或者当空字符串(ε) 标示一个转变的时候，那么 FSA 就是非确定性的 (NFSA)。此时，无法用一个 (state, symbol) 元组唯一地标识下一个状态。

确定性的有限状态自动机

一个确定性的有限状态自动机 (DFSA) 是一个没有用ε字符串标示其转变的 FSA，能够唯一地标识或确定一个 (state, symbol) 元组的下一个状态。

任何 NFSA 可以通过构造子集的方法转换成一个等价 DFSA。这个方法在文献中已经有说明，详细请看参考文献[ASU86b, Gou88, FJ88a]。另外，构造一个最小状态 DFSA 的方法见参考文献[ASU86b]。

4.1.2 有限状态自动机和语法分析器

任何机器语言都能用一个 FSA (即，接受或拒绝任意字符串的识别程序) 表现。字母表∑是一个十六进制数字 00..FF 的有限集 (即，数字用一个字节表示)，一个字符串就是一个字节序列。那些它能够认识的机器语言指令就是该语言的有效字符串。

例子 2

对于一条 i80286 机器指令

83E950 ; sub cx, 50

识别它的 FSA 首先需要确定 83 是一个操作码(sub)、这个操作码有两个字节或更多字节的操作数。第二个字节编码目标寄存器操作数 (较低的 3 位)，以及指明在这个字节之后用多少字节表示其它信息：如果较高两位是 0 或 2，那么在第二字节后面的两个字节也是目标操作数的一部分；如果这两位的值是 1，那么在第二字节后面的一个字节是目标操作数的一部分；否则，该目标操作数没有使用更多字节。在我们的例子中，较低的三位等于 1，即是寄存器 cx，而较高两位是 3，说明目标操作数没有使用更多字节。最后，最末尾的一个字节是立即常数操作数，在这个例子里是 50。这个例子的 FSA 见图 4-4 所示。

图 4-4 : FSA 例子

机器语言也可以用一个无语境语法(CFG) 来描述；如，正则表达式是无语境语法的一个子集。在参考文献[ASU86a]中提出把 NFSA 机械地转换成 CFG 的一个算法。CFGs 被用来描述原本有递归结构的高级构造，但由于机器语言没有使用递归构造，所以用 CFGs 定义递归不是必要的。

4.1.3 代码和数据的区分

句法分析程序的功能就是，从一个程序的入口点开始解析机器指令，跟随该程序所有可能的路径（路线)。语法分析器面临的主要问题是在一个冯·诺依曼机器里面数据和代码看上去没什么不同，因此不容易确定某一条指令后面的一些字节是属于另一条指令抑或是数据。这一节讨论从代码中确定数据所要用到的启发式。

当源二进制程序被装入内存以后，装载器返回该程序在内存里最初的开始地址。这个地址是完全的二进制程序的启动地址，因为程序要从这里开始运行，所以它一定是一条指令的地址。此外，如果已经从二进制程序查出编译器签名，就可以把程序 main 函数入口点作为最初的启动地址；亦即，略过所有的编译器启动代码，直接从相应源码的主程序开始地址开始。图 4-5 举例说明一个“hello world”程序的样本代码。由装载器返回的入口点是 CS:0000，即是完整程序的入口点 (包括编译器启动代码)。由编译器签名分析器给出的入口点是 CS:01FA，即主程序的开始地址。在这篇论文中，为了保持普遍性，我们都将假定入口点为编译器签名分析器给出的那个地址。这里叙述的方法对二者都适用，但是举例比较偏重后者。编译器签名的生成技术和检测技术请看第 8 章。

	helloc	proc far
CS:0000	start: mov	dx,*
CS:0003	mov	cs:*,dx
...	...		; start-up code
CS:011A	call	_main
CS:011D	...		; exit code
	helloc	endp
...	...
	_main	proc near
CS:01FA	push	bp
CS:01FB	mov	bp,sp
CS:01FD	mov	ax,194h
CS:0200	push	ax
CS:0201	call	_printf
CS:0204	pop	cx
CS:0205	pop	bp
CS:0206	ret
	_main	endp

图 4-5: 一个“hello world”程序的样本代码

R.N. Horspool 和 N. Marovac 的一篇文章重点讨论了代码和数据的区分问题。该文提到这个问题等价于停机问题，因为冯·诺依曼体系结构是在运行时计算数据地址和分支目标地址，所以不可能区分数据和指令 [HM79]。该文中提出一个取得指令保存单元最大集的算法。在最初的问题上应用分支界限方法(branch and bound) 做些修改，使之等价于从所有候选树中寻找一个最大树集的组合问题。这次实践发现该算法完全不适用。

实践证明，在密集机器指令集 (比如 Intel 体系结构) 中，由于几乎任何字节组合都是一个有效的机器指令，该算法不能工作，因而很难知道哪里是不是数据，所以很难确定代码边界。这个算法一个简单的反面例子可通过存放在代码段的一个 case 表来说明 (见图 4-6)。在 CS:0DDB 上这条变址跳转指令之后，通过变址进入 case 表内，该表本身被定义从 CS:0DE0 开始，但是却由于它包含有效指令字节，而被该算法当作代码看待。在这个 i80286 代码例子中，0E 相当于 push CS，而 2B 相当于 sub，它会把另一个字节当成变元，即这个例子中的 0E，结果造成 sub ax,[bp]，等等。因此所产生的代码是错误的。

CS:0DDB	jmp CS:0DE0[bx]
CS:0DE0	0E2B	; push CS
CS:0DE2	0E13	; sub ax,[bp]
	...

图 4-6: 反面例子

这一节将提出一个不同方法，从一个已经装入内存的二进制程序指令确定代码。它提供启发式方法解决在代码段之间发现数据的特殊情况。

处理

如前述，从代码确定数据的过程是建立在程序的初始入口点是一条指令这个基础之上。从这条指令开始，沿着这条路径循序地解析出指令，直至控制流改变或者到达路径终点。在前一情况下，目标地址(es) 成为新的内存入口点，因为在该地址上一定是一条有效指令使程序可以继续运行。在后一情况下，当前路径结束了，由于我们不能确定后面那些字节是代码还是数据，所以不再沿着这条路径扫描指令。

控制流的改变是由于跳转和子过程调用。条件跳转把控制流向一分为二：若条件为真，就跟随目标分支地址，否则跟随那个条件分支后面的地址。为了得到所有可能执行代码，两条路径都要被语法分析器跟随。无条件跳转把控制流向转移到目标地址；语法分析器只需要跟随这唯一的一条路径。子过程调用把控制流向转移到被调用的子过程，而且在它返回以后，再分析这个子过程调用的下一条指令。对于子过程没有返回的情况，这条子过程调用指令后面的字节不被分析，因为不能确定这些字节是什么 (代码或数据)。

每当遇到一个子过程返回指令或程序结束，也就到达路径终点了。程序的结束通常为一个规定的指令序列，它们让操作系统终止当前进程 (或者说，该程序)。这个指令序列因操作系统而不同，所以对于不同的源机器，这部分代码是不同的。不过，确定是否遇到程序结束 (即，程序完成或者停机) 不是等价于解决停机问题，因为所跟随的这条路径必然不是可执行程序会跟随的，也就是说，去往这条路径的分支条件永远不可能在程序运行期间变成真；例如，在无限循环中的程序。

例子 3

在 Intel 体系结构上，程序的结束是通过中断指令指明。终止一个程序有不同的方法，其中有一些方法利用程序段前缀，通常叫作 PSP；关于 PSP 的更多信息请参考附录 B。在 DOS 下面有 7 个不同方法终止一个程序：

1. 用返回代码终止进程：int 21h，功能号 4Ch。这是在.exe 文件中最普遍使用的方法。

2. 终止进程：int 20h。代码段 cs 必须指向 PSP。这个方法通常用于.com 文件，因为 cs 已经指向 PSP 段。

3. 热启动/终止向量：在 PSP 的偏移 00h 处包含 int 20h 指令。寄存器 cs 必须指向 PSP 段。

4. 返回指令:：在程序启动之前将返回地址入栈。当程序即将终结的时候，它返回在栈上这个地址。这个方法在 CP/M 操作系统中使用，因为热启动向量的地址在栈上。初始化 DOS 的.com 程序利用这个技术。

5. 终止进程功能：int 21h，功能号 00h。寄存器 cs 必须指向 PSP。

6. 终止并且驻留：int 27h。寄存器 cs 必须指向 PSP。

7. 终止并且驻留功能：int 21h，功能号 31h。

确定一个子过程是否返回 (亦即，完成或停机) 很困难，因为该子过程可能利用自修改代码或者把数据当作代码来执行、并且在这个数据里面的某一条指令上终止。一般来说，我们对正常情况下的解决方案感兴趣，因为不正常的情况需要通过单步调试和用户输入来解决问题。如果一个子过程到达程序终点或者调用了另一个到达程序终点的子过程，那么它是不返回的 (例如，一个调用 exit(.) 的 C 语言子过程)。有可能通过模拟程序终止指令序列的有关寄存器值来确定一个子过程是否已经到达程序终点。在例子 3 这些情况下，就要跟踪寄存器 ah 而且多数情况还要跟踪寄存器 cs。

最初的区分代码和数据的算法见图 4-7 所示。为了掌握寄存器信息，用一个 machState 记录寄存器值。使用一个 state 变量 (这个记录类型的变量) 保存寄存器的当前值 (亦即，机器的当前状态)。使用一个位映像图（点阵) 储存每一个被装入内存的字节的有关信息，每一个内存字节用两个位元表现：

0：代表一个未知的数值 (亦即，内存单元还没有被分析)。

1：代表一个代码字节。

2：代表一个数据字节。

3：代表一个字节，该字节既用作数据也作为代码。

该算法以递归方式实现。每当需要跟随一个非向下直通的(non fall-through) 路径的时候，就复制一份当前 state 的拷贝并且用这个状态拷贝来递归调用 parse 子过程、继续跟随该路径。

procedure parse (machState *state) done = FALSE; while (! done) getNextInst (state, &inst); if (alreadyParsed (inst)) /* check if instruction already parsed */ done = TRUE; break; end if setBitmap (CODE, inst); case (inst.opcode) of conditional jump: *stateCopy = *state; parse (stateCopy); /* fall-through */ state->ip = targetAdr (inst); /* target branch address */ if (hasBeenParsed (state->ip)) /* check if code already parsed */ done = TRUE; end if unconditional jump: state->ip = targetAdr (inst); /* target branch address */ if (hasBeenParsed (state->ip)) /* check if code already parsed */ done = TRUE; end if procedure call: /* Process non-library procedures only */ if (! isLibrary (targetAdr (inst))) *stateCopy = *state; stateCopy->ip = targetAdr (inst); parse (stateCopy); /* process target procedure */ end if procedure return: done = TRUE; /* end of procedure */ move: if (destination operand is a register) updateState (state, inst.sourceOp, inst.destOp); end if interrupt: if (end of program via interrupt) done = TRUE; /* end of program */ end if end case end while end procedure

图 4-7: 最初的句法分析算法

间接寻址模式

间接寻址模式利用一个寄存器或者内存单元的值确定一条指令的目标地址 (该指令使用这个寻址模式)。间接寻址模式能够用于无条件跳转 (例如，实现变址的 case 表) 和子过程调用指令。这个寻址模式的主要问题是内存值可以在程序运行期间被改变，因而对程序做静态分析不能确定内存单元是否已经被修改从而无法求出正确的值。对于寄存器值也是同样的，除非一直模仿寄存器的内容，然而很可能在某个循环中使用寄存器，因此需要虚拟执行循环。

在 i80286 中，一条间接的指令可能是在段之内或者跨段之间。在前一情况下，用寄存器或内存单元保存一个 16 位偏移地址，后一情况则是一个 32 位地址 (即，段和偏移)。

在高级语言 (如 C 语言) 中，函数调用指针的实现就是间接的子过程调用。考虑下面的 C 程序：

typedef char (*tfunc)(); tfunc func[2] = {func1, func2}; char func1() {/* some code here */} char func2() {/* some code here */} main() { func[0](); func[1](); }

在主程序里，对函数 func1() 和 func2() 的调用是通过一个函数指针和这些函数数组的一个索引。这个程序的反汇编代码如下：

CS:0094	B604			; address of proc1 (04B6)
CS:0098	C704			; address of proc2 (04C7)
	...
	proc_1	PROC FAR
CS:04B6	55	push	bp
...	...
CS:04C6	CB	retf
	proc_1	ENDP
	proc_2	PROC FAR
CS:04C7	55	push	bp
...	...
CS:04D7	CB	retf
	proc_2	ENDP
	main	PROC FAR
CS:04D8	55	push	bp
CS:04D9	8BEC	mov	bp,sp
CS:04DB	FF1E9400	call	0094	; intra-segment indirect call
CS:04DF	FF1E9800	call	0098	; intra-segment indirect call
CS:04E3	5D	pop	bp
CS:04E4	CB	retf
	main	ENDP

用每个子过程地址的内存偏移地址代替函数指针 (即，分别是 04B6 和 04C7)。如果这些地址在程序运行期间没有被修改，我们可以从这些内存单元的内容得到那些函数的目标地址。我们的实现就是，函数的目标地址用子过程调用指令代替，把它看作一个普通的子过程调用，反编译 C 程序的结果如下：

void proc_1() {/* some code */} void proc_2() {/* some code */} void main() { proc_1(); proc_2(); }

Case 语句

高级语言通过一个叫作 case 语句的高级构造来实现多路 (或 n 路) 分支。在这个构造中，有 n 个不同的路径可能被执行。这个构造没有相应的低级机器指令，因此不同的编译器作者可能用不同的方法定义一个 case 表。

如果 case 的数目不是太多 (即，少于 10 个)，一个 case 用一序列的条件跳转来实现，每个检测一个单独的数值并且把控制转移到相应的代码。考虑下面的汇编代码片断

	cmp	al,8	; start of case
	je	lab1
	cmp	al,7Fh
	je	lab2
	cmp	al,4
	je	lab3
	cmp	al,18h
	je	lab4
	cmp	al,1Bh
	je	lab5
	jmp	endCase
lab1:	...
...
lab5:	...
...
endCase:	...		; end of case

在这个代码片断中，寄存器 al 跟 5 个不同的字节数值做比较，如果结果是相等的，就无条件跳转到处理该 case 的标签。如果寄存器跟 5 个选项中任何一个都不相等，程序就无条件跳转到这组 case 结束处。

实现 case 语句更紧凑的一个办法是，使用一个索引表，其中保存 n 个目标标签地址：每个地址对应那 n 种情况其中之一。用一个变址的跳转指令进入该表。先对表索引值检查该表的上下限，以避免错误的索引号。在确定索引值不越界以后，再执行变址的跳转指令。考虑下面的代码片断：

cs:0DCF		cmp	ax,17h	; 17h == 24
cs:0DD2		jbe	startCase
cs:0DD4		jmp	endCase
cs:0DD7	startCase:
		mov	bx,ax
cs:0DD9		shl	bx,1
cs:0DDB		jmp	word ptr cs:0DE0[bx]	; indexed jump
cs:0DE0		0E13	; dw lab1	; start of indexed table
cs:0DE2		0E1F	; dw lab2
		...
cs:0EOE		11F4	; dw lab24	; end of indexed table
cs:0E10	lab1:
		...
cs:11C7	lab24:
		...
cs:11F4	endCase:		; end of case
		...

case 表在代码段中被定义为数据，而且紧跟在变址的跳转之后和任何目标分支标签之前。寄存器 ax 保存进入该表的索引值。这个寄存器跟上限 24 做比较。如果寄存器大于 24，将不执行这组指令序列的其它部分并且把控制转移给最后一个标签，即这组 case 结束后的第一条指令。另一方面，如果寄存器小于或等于 24，就到第一个标签，并且寄存器 bx 被设置为表内偏移。因为字长是 2，case 表标签偏移是 2，所以原来的表内索引被乘以 2 求出在 2 字节表内的正确偏移。然后，变址的跳转指令确定该 case 表是在 cs 段中偏移 0DE0 处 (对于这个例子，也就是在内存中下一个字节)。因此，目标跳转地址是这个表的 24 个不同可选地址中任何一个。

另一个非常相似的实现 case 语句方法是，把 case 表放置在子过程的末尾，进入该表的变址寄存器就是保存表内偏移的寄存器 (在下面代码片断中寄存器 bx)：

cs:0BE7		cmp	bx,17h	; 17h == 24
cs:0BEA		jbe	startCase
cs:0BEC		jmp	jumpEnd
cs:0BEF	startCase:
		shl	bx,1
cs:0BF1		jmp	word ptr cs:0FB8[bx]	; indexed jump
cs:0BF6	jumpEnd:
		jmp	endCase
cs:0BF9	lab1:
		...
cs:0F4C	lab24:
		...
cs:0F88	endCase:			; end of case
		...
cs:0FB5		ret		; end of procedure
cs:0FB8		0BF9	; dw lab1	; start of indexed table
cs:0FBA		0C04	; dw lab2
		...
cs:0FE6		0F4C	; dw lab24	; end of indexed table

实现 case 语句的第三个方法是把所有变址分支放在 case 表后面。在这个方法中，代码跳过所有的目标跳转地址，检查索引表的上限 (在下面的代码片断中是 31)，校准作为表内索引的寄存器，然后分支转移到那个位置：

cs:0C65		jmp	startCase
cs:0C68	lab5:
...		...
cs:1356	lab31:
...		...
cs:1383	lab2:
...		...
cs:13B8		1403	; dw endCase	; Start of indexed table
cs:13BA		1383	; dw lab2
...		...
cs:13F4		1356	; dw lab31	; End of indexed table
cs:13F6	startCase:
		cmp	ax,1Fh	; 1Fh == 31
cs:13F9		jae	endCase
cs:13FB		xchg	ax,bx
cs:13FC		shl	bx,1
cs:13FE		jmp	word ptr cs:13B8[bx]	; indexed jump
cs:1403	endCase:
		...
cs:1444		ret

case 语句一个不同的实现是，使用一串字符选项代为编号。考虑下面的代码片断：

cs:246A	4C6C68464E6F 785875646973 ; db 'LlhFNoxXudiscpneEfgG%'
cs:2476	63706E654566 674725
cs:247F		256C	; dw lab1	; start of table
cs:2481		2573	; dw lab2
...		...
cs:24A7		24DF	; dw lab21
...		...
cs:24C4	procStart:
		push	bp
...		...
cs:2555		mov	di,cs
cs:2557		mov	es,di	; es = cs
cs:2559		mov	di,246Ah	; di = start of string
cs:255C		mov	cx,15h	; cx = upper bound
cs:255F		repne	scasb
cs:2561		sub	di,246Bh
cs:2565		shl	di,1
cs:2567		jmp	word ptr cs:247F[di]	; indexed jump
cs:256C	lab1:
...		...
cs:26FF	lab12:
...		...
cs:2714		ret

字符选项字符串被放置于 cs:246A。寄存器 al 保存所要核对的当前字符选择项，es:di 指向作为比较的内存字符串，repne scasb 指令在 es:di 所指向的字符串里面寻找与寄存器 al 的第一个匹配。执行以后，寄存器 di 就指向那个匹配字符。然后将这个寄存器减去字符串的开始地址和一，就是在变址跳转表内的索引值，该表被放置于代码段上该子过程之前。这个方法紧凑而且精彩。

不幸的是，case 语句没有固定的表示法，因此需要首先手动检查二进制代码以确定它是如何实现 case 语句的。不同的编译器使用不同的实现，但是通常一个特定厂商的编译器只使用一两种不同 case 表表示法。case 表的确定是一个启发式方法，它操作一组预先定义的一般化实现。反编译器能处理的实现方法越多，它所能产生的输出就越好。在使用启发式方法的时候，需要首先满足预备条件：即，如果遇到索引表而索引表的上下限无法确定，就不能应用所建议的启发式方法。

最后的算法

最后区分数据/代码的算法见图 4-8 所示。该算法在图 4-7 的算法的基础上，增加处理变址跳转和间接的跳转与调用。

procedure parse (machState *state) done = FALSE; while (! done) getNextInst (state, &inst); if (alreadyParsed (inst)) /* check if instruction already parsed */ done = TRUE; break; end if setBitmap (CODE, inst); case (inst.opcode) of conditional jump: *stateCopy = *state; parse (stateCopy); /* fall-through */ state->ip = targetAdr (inst); /* target branch address */ if (hasBeenParsed(state->ip)) /* check if code already parsed */ done = TRUE; end if unconditional jump: if (direct jump) state->ip = targetAdr(inst); /* target branch address */ if (hasBeenParsed(state->ip)) /* check if code already parsed */ done = TRUE; end if else /* indirect jump */ check for case table, if found, determine bounds of the table. if (bounds determined) for (all entries i in the table) *stateCopy = *state; stateCopy->ip = targetAdr(targetAdr(table[i])); parse (stateCopy); end for else /* cannot continue along this path */ done = TRUE; end if end if procedure call: /* Process non-library procedures only */ if (! isLibrary (targetAdr (inst))) *stateCopy = *state; if (direct call) stateCopy->ip = targetAdr(inst); else /* indirect call */ stateCopy->ip = targetAdr(targetAdr(inst)); end if parse (stateCopy); /* process target procedure */ end if /* other cases (procedure return, move, interrupt) remain the same */ end case end while end procedure

图 4-8: 最后的语法分析器算法