CMU炸弹实验室Phase4：func4递归逻辑与输入求解问询

已知信息 #

• Phase4接收2个输入
• 第一个输入必须≤14（0xe）
• 第二个输入必须为3
• func4需返回eax=3才能通过关卡

func4汇编代码 #

func4:
   endbr64 
   sub    $0x8,%rsp
   mov    %edx,%ecx
   sub    %esi,%ecx
   shr    %ecx
   add    %esi,%ecx
   cmp    %edi,%ecx
   ja     0x5555555556f9 <func4+32>
   mov    $0x0,%eax
   jb     0x555555555705 <func4+44>
   add    $0x8,%rsp
   ret    
   lea    -0x1(%rcx),%edx
   call   0x5555555556d9 <func4>
   add    %eax,%eax
   jmp    0x5555555556f4 <func4+27>
   lea    0x1(%rcx),%esi
   call   0x5555555556d9 <func4>
   lea    0x1(%rax,%rax,1),%eax
   jmp    0x5555555556f4 <func4+27>

phase_4汇编代码 #

Dump of assembler code for function phase_4:
=> 0x0000555555555713 <+0>: sub    $0x18,%rsp
   0x0000555555555717 <+4>: lea    0x8(%rsp),%rcx
   0x0000555555555720 <+13>: lea    0xc(%rsp),%rdx
   0x0000555555555725 <+18>: lea    0x1c7a(%rip),%rsi        # 0x5555555573a6
   0x000055555555572c <+25>: mov    $0x0,%eax
   0x0000555555555731 <+30>: call   0x5555555552e0 <__isoc99_sscanf@plt>
   0x0000555555555736 <+35>: cmp    $0x2,%eax
   0x0000555555555739 <+38>: jne    0x555555555742 <phase_4+47>
   0x000055555555573b <+40>: cmpl   $0xe,0xc(%rsp)
   0x0000555555555740 <+45>: jbe    0x555555555747 <phase_4+52>
   0x0000555555555742 <+47>: call   0x555555555c42 <explode_bomb>
   0x0000555555555747 <+52>: mov    $0xe,%edx
   0x000055555555574c <+57>: mov    $0x0,%esi
   0x0000555555555751 <+62>: mov    0xc(%rsp),%edi
   0x0000555555555755 <+66>: call   0x5555555556d9 <func4>
   0x000055555555575a <+71>: cmp    $0x3,%eax
   0x000055555555575d <+74>: jne    0x555555555766 <phase_4+83>
   0x000055555555575f <+76>: cmpl   $0x3,0x8(%rsp)
   0x0000555555555764 <+81>: je     0x55555555576b <phase_4+88>
   0x0000555555555766 <+83>: call   0x555555555c42 <explode_bomb>
   0x000055555555576b <+88>: add    $0x18,%rsp
   0x000055555555576f <+92>: ret    

已梳理结论 #

• 采用类似二分查找的递归方式
• 上层分支将eax翻倍（add %eax,%eax）
• 下层分支将eax翻倍并加1（lea 0x1(%rax,%rax,1),%eax）
• 基准情况返回0

待明确问题 #

1. 递归调用如何逐步构建出eax=3？
2. 何种输入能触发正确的分支序列？

问题解答 #

1. 递归构建eax=3的路径 #

首先将func4的汇编逻辑转化为伪代码，参数对应关系为func4(target, left, right)，初始调用是func4(input1, 0, 14)：

int func4(int target, int left, int right) {
    int mid = left + (right - left)/2;
    if (mid > target) {
        int res = func4(target, left, mid-1);
        return res * 2;
    } else if (mid < target) {
        int res = func4(target, mid+1, right);
        return res * 2 + 1;
    } else {
        return 0;
    }
}

要得到返回值3（二进制11），可反向推导路径：

• 3 = 1*2 +1 → 上一层递归返回1，且走右分支（mid < target）
• 1 = 0*2 +1 → 再上一层递归返回0（基准情况），且走右分支

正向验证有两种有效路径：

路径一（target=13）

1. 初始调用：func4(13,0,14)，mid=7 <13 → 调用func4(13,8,14)，最终返回res*2+1
2. 第二层调用：func4(13,8,14)，mid=11 <13 → 调用func4(13,12,14)，最终返回res*2+1
3. 第三层调用：func4(13,12,14)，mid=13 ==13 → 返回0
4. 第二层返回0*2+1=1，第一层返回1*2+1=3，符合要求

路径二（target=12）

1. 初始调用：func4(12,0,14)，mid=7 <12 → 调用func4(12,8,14)，最终返回res*2+1
2. 第二层调用：func4(12,8,14)，mid=11 <12 → 调用func4(12,12,14)，最终返回res*2+1
3. 第三层调用：func4(12,12,14)，mid=13 >12 → 调用func4(12,12,12)返回0，本层返回0*2=0
4. 第二层返回0*2+1=1，第一层返回1*2+1=3，符合要求

2. 触发正确分支的输入 #

结合phase_4的校验逻辑：

• 第二个输入必须为3（由cmpl $0x3,0x8(%rsp)强制校验）
• 第一个输入需满足上述两种递归路径，即12或13

因此有效输入为12 3或13 3。

内容的提问来源于stack exchange，提问作者Toan Lam