反编译原理①:基本块

反编译原理系列:基本块 | 表达式 | 控制流 | 优化与输出

本文的主要参考文献为Decompiler Design

本系列是对Furikiri反编译器项目的一些总结。原本有打算汉化Decompiler Design(以下简称DD),但是一直没有时间(已经拖了五个月了),所以这里先把比较关键的部分记录下来。因此,本文中的举例将采用TJS2语言及其汇编指令(DD中是C语言/X86汇编)。TJS2的字节码采用的是基于寄存器的指令集,类似于X86汇编,但TJS2语言中没有指针和goto,因此相对简单。该教程对于任何寄存器指令集的语言(如C语言)都有直接参考价值。除此之外,高级语言的虚拟机如JVM(Java)、CLR(C#)等通常采用基于栈的指令集,在基本块分析和表达式生成上可能会有少许不同,但大部分还是可以参考的。

 

基本块

基本块(Basic Block,简称“块”)是(反)编译原理中的概念,是(汇编)指令的集合。

【定义】基本块是一串连续的指令,它的首条指令是进入并执行这一串指令的唯一入口,它的最后一条指令是退出这一串指令的唯一出口。(换言之,在执行时,一个基本块中的指令要么全部被执行,要么全部不执行。)

每条跳转语句(如无条件跳转JMP、满足条件则跳转JF、不满足条件则跳转JNF等)的目的地址会是一个基本块的开始,每条跳转语句本身会是一个基本块的结束。

从一大段汇编中划分出所有的基本块,并确定它们之间的跳转关系,也就生成了这段汇编代码的控制流图(Control Flow Graph, CFG)。这对于后续识别代码的逻辑结构(分支、循环)是非常有必要的。

有了上面的定义,识别基本块的算法就非常好理解了。我们只需要对每条跳转指令(JMP、JF、JNF、函数返回RET)进行重点分析。除了RET之外,每条跳转语句之后通常会分为两个基本块,一个紧挨着跳转语句所在的基本块(不跳转),另一个是跳转语句的目的地址开始的基本块(跳转)。在扫描基本块的过程中,还要同时记录基本块之间的跳转关系,即一个基本块可以由哪些基本块跳转过来(这个基本块的前驱predecessor/From),以及它可以跳转到哪些基本块(这个基本块的后继successor/To)。

具体的算法伪代码(摘自DD,如有不理解之处也可参见Furikiri实际代码中的ScanBlocks方法):

Block *get_block_at(Address start_address)
{
    Block *block = find in BlockList a block for start_address
    if block == not found
	block = new Block at start_address
        blockList += block
    return block
}

CreateBasicBlocks(current_procedure)
{
    current_address = current_procedure->entry_address
    block = get_block_at(current_address)
    current_procedure->entry_block = block
    workList.push = current_address
    while workList not empty
        current_address = workList.pop
        block = get_block_at(current_address)
next:
        label = find label at address higher than current_address
        branch = find branch at address higher than current_address

        if label->address < branch->address_after_branch
            block->length = label->address - block->address
            current_address = label->address
	    next_block = get_block_at(current_address)
            next_block->preds += block
            block->succs += next_block
            block = next_block
	    goto next
	end if

	block->length = branch->address_after_branch - block->address
        if branch is return	// returns have no known destination
	    continue
        end if

	next_block = get_block_at(branch->destination)
        next_block->preds += block
        block->succs += next_block
        workList.push = branch->destination
        if branch is not conditional
            continue           // will resume from branch destination
        end if
	next_block = get_block_at(branch->address_after_branch)
        next_block->preds += block
        block->succs += next_block
        block = next_block
        current_address = block->address
        goto next
    end while

    sort blockList by block's start address
}

在识别基本块、完成控制流图的构建之后,我们基本上就达到了类似于IDA中的Flow Chart的效果:

图1:IDA中的控制流图

支配树

上文中我们已经建立了CFG,从CFG中我们可以看到,除了正常向下(继续执行后面代码)的边之外,还有很多向上(返回之前代码)的跳转边,即回边(back edge)。后者经常出现在循环结构(如for、while、do while)中。(除了循环结构之外,还有可能是goto语句手动跳转。但是在TJS2中不存在goto,所以我们不需要考虑这种情况。即使需要考虑goto,在此步骤中我们也可以将其视为循环,在后续恢复循环结构时如遇失败再转换为goto语句即可。)

我们可以把条件跳转指令如JF、JNF都反编译为if(...) goto (地址),但这样无法表现出原代码中的循环逻辑。因此我们首先要从CFG中识别出循环,进而将循环转化为具体的循环结构。

为了识别出循环,我们需要计算每个基本块的(前序)支配树(Dominator Tree)和后序支配树(Post Dominator Tree)。(本文中“支配”默认是指前序支配。)

定义】在计算机科学中,若控制流图的开始节点(可以理解为源)到 节点n 的每一条路径均要经过 节点d,则称 节点d (前序)支配 节点n。

若控制流图的 节点n 到终结节点的每一条路径均要经过 节点d,则称 节点d 后序支配 节点n。

易得,每个节点(前序&后序)支配它自己。

在反编译过程中,节点就是基本块。如何通过支配树识别循环呢?

下图是一个do-while结构的控制流图。通过上文中的定义我们可知,1支配234,2支配34,3支配4。通常顺序执行情况下,一个节点的后继节点不会支配它,比如2不支配1(抵达1不需要经过2),3不支配2(抵达2不需要经过3,因为可以只经过1),4不支配3。但作为3的后继节点(之一)的2却能支配3(抵达3必须经过2)。注意从3出发的深色的回边使得2成为了3的后继节点。

图2:do-while的控制流图

当发现了这条回边,也就是符合“节点A的一个后继节点B支配A”这个条件,我们就认为这里存在一个循环(Loop),其中B是这个循环的头节点(Header),A是这个循环的尾结点。在上图中,2是循环的头节点。找到头节点后,我们从尾节点开始遍历前驱节点,直到抵达头节点,这些节点就构成了一个循环。(根据支配的定义,在头节点之后的 尾结点的前驱节点 一定被头节点支配。)

识别并记录循环,后续就可以将循环进一步转换为具体的while、for等结构。这将在“控制流”一章中讲解。

这就是支配树在识别循环上的作用。下面的算法可以计算支配树(摘自DD,如有不理解之处也可参见Furikiri实际代码中的ComputeDominators方法):

ComputeDominators()
{
   int nBlocks = block_list.size();
   int i = 0;
 
   for each block in block_list {
      block->id = i++;
      block->dominators = new BitVector(nBlocks)
      block->dominators->SetAllBitsTo(1)
   }
 
   block = block_list[0]
   block->dominators->SetAllBitsTo(0)
   block->dominators->SetBit(block->id)
 
   BitVector T(nBlocks)
 
   do {
      changed = false
 
      for each block in block_list {
 
        if (block == entry_block)
            continue
 
        for each pred in block->predecessors {
            T.SetAllBitsTo(0)
            T.Or(block->dominators)
            block->dominators->And(pred->dominators)
            block->dominators->SetBit(block->id)
            if (block->dominators != T)
                changed = true
 
        }
 
      }
 
   } while (changed);
}

 

下面的算法可以根据支配树识别循环(摘自DD,如有不理解之处也可参见Furikiri实际代码中的ComputeNaturalLoops方法):

NaturalLoopForEdge(Block header, Block tail)
{
    Stack workList;
    Loop  loop;
 
    loop = new Loop();
 
    loop->header = header
    loop->blocks += header
 
    if header != tail {
        loop->blocks += tail
        workList += tail
    }
    while workList not empty {
        block = workList.pop
        for each pred in block->predecessors {
            if not loop->find(pred) {
                loop->blocks += pred
                workList += pred
            }
        }
    }
    return loop
}
 
ComputeNaturalLoops()
{
    LoopSet   loopSet;
 
    for each block in block_list {
        if (block == entry_block)
            continue

        for each succ in block->successors {
 
            // Every successor that dominates its predecessor
            // must be the header of a loop.
            // That is, block -> succ is a back edge.
 
            if block->dominators->find(succ)
                loopSet += NaturalLoopForEdge(succ, block);
 
        }
    }
}

 

尽管此处没有用到,但后序支配树在反编译中也是有用的(如识别循环中的break以及if条件合并,这些内容可能会在后续文章中讲解),因此在计算(前序)支配树时应当一并计算(如有不解之处可参见Furikiri源码)。

 

添加评论

Loading