Falcon IL 中间语言设计与实现详解

1. 中间语言(IL)与中间表示(IR)基础

中间表示(IR)是程序从一种状态转换到另一种状态时的存储方式，而中间语言(IL)是IR使用的一种特定语言，用于编码程序语义以便后续分析。两者概念常被混用。

2. Falcon IL的设计背景

Falcon IL是作者在多个IL实现经验基础上设计的：

• 早期实现过RREIL的复制品（无控制流）
• 使用过Queso框架的IL（完全提升为控制流图）
• 实验过Binary Toolkit的Bins IL
• 研究过Angr的VEX IR和LLVM IR
• 使用过BAP IL和Binary Ninja的LLIL/MLIL

3. IL的分类维度

3.1 指令复杂度谱系

• RREIL：最简单的three-form IL（OP DST, LHS, RHS）
• VEX IR：最复杂，有上百条指令类型（为Valgrind性能优化）
• 中间类型：BAP IL、LLVM IR、Binary Ninja IL（支持表达式）

3.2 表达式支持

支持表达式的IL允许 a = b * (c + 7) 这样的形式，而非表达式IL需要分解为多条指令：

temp0 = c + 7
a = b + temp0

4. Falcon IL的核心设计

4.1 基本操作类型

Assign { dst: Scalar, src: Expression }
Store { index: Expression, src: Expression }
Load { dst: Scalar, src: Expression }
Branch { target: Expression }
Raise { expr: Expression } // 后改为Intrinsic

4.2 表达式类型

Scalar(scalar)
Constant(constant)
Add(lhs, rhs)
Sub(lhs, rhs)
Mul(lhs, rhs)
Divu(lhs, rhs)
Modu(lhs, rhs)
Divs(lhs, rhs)
Mods(lhs, rhs)
And(lhs, rhs)
Or(lhs, rhs)
Shl(lhs, rhs)
Shr(lhs, rhs)
Cmpeq(lhs, rhs)
Cmpneq(lhs, rhs)
Cmplts(lhs, rhs)
Cmpltu(lhs, rhs)
Trun(bits, rhs)
Sext(bits, rhs)
Zext(bits, rhs)

4.3 程序结构

• Instruction：包含Operation及元数据（地址、注释、位置）
• Block和Edge组成ControlFlowGraph
• Function由CFG组成
• Program由函数组成

5. 关键设计决策与演进

5.1 可读性设计

Falcon IL示例：

[ Block: 0x0 ]
804849B 00 exc:32 = (esp:32 + 0x4:32)
804849F 01 temp_0.0:32 = (esp:32 & 0xFFFFFFF0:32)
804849F 02 ZF:1 = (temp_0.0:32 == 0.0:32)
804849F 03 SF:1 = trun.1((temp_0.0:32 >> 0x1F:32))

5.2 跳转指令编码策略

• 过程间跳转（Call）：显式编码为Branch操作
• 过程内直接跳转：隐式转换为CFG边（不生成IL指令）
• 间接跳转：显式编码为Branch操作
• 条件跳转：转换为带条件的CFG边

5.3 重要演进点

5.3.1 Raise到Intrinsic的转变

• 初始设计：用Raise处理特殊指令（如系统调用）
• 问题：无法处理MIPS rdhwr等复杂指令
• 解决方案：引入更灵活的Intrinsic操作

5.3.2 引入Ite表达式

• 初始设计：条件赋值转换为控制流
• 问题：状态合并困难
• 解决方案：添加Ite表达式支持

5.3.3 MIPS延迟槽处理

解决方案示例：

1000 00 branching_condition:1 = ($v0:32 == 0x0:32)
1004 01 $v0 = (0x0:32 + 0x1:32)
// 边条件为branching_condition:1

5.3.4 引入Nop操作

• 目的：保留跳转指令地址信息
• 特性：无实际语义，分析时可忽略
• 优势：保持地址信息而不影响分析和可读性

6. 设计哲学与经验总结

1. 没有万能IL：不同分析需要不同的IL表示形式
2. 信息完整性：初始IL应保留所有原始信息，后续可转换
3. 渐进式演进：根据实际需求逐步完善IL设计
4. 可读性与功能性平衡：在保持分析能力的同时提高可读性

7. Falcon IL应用场景

• 静态分析（跨x86和MIPS架构）
• 符号执行（如DARPA CGC挑战赛）
• 二进制程序分析（如检测MIPS libc函数参数错误）

8. 与其他IL的对比

Falcon IL在简单性、表达能力和可读性之间取得了平衡，特别适合二进制程序分析场景。