[原创]表情包引发的悬案，浅谈编译器优化
2023-2-12 17:1:0 Author: bbs.pediy.com(查看原文) 阅读量:18 收藏

[原创]表情包引发的悬案，浅谈编译器优化

2023-2-12 17:01 3293

某日在群里看到这张很怪的表情包，想着这不是扯淡么，一看到运行结果顿时傻眼了。。。

1

2

3

4

5

6

7

int main(){

    while(1) ;

}

void unreachable(){

    printf("HelloWorld\n");

}

先放一个在线编译C代码的网站：https://godbolt.org/

编译选项 结果
gcc全版本 -O0/O1/O2 死循环
g++全版本 -O0/O1/O2 死循环
clang（C语言） 全版本 -O0/O1/O2 死循环
clang++（C++） >= 13.0.0 -O0 死循环
clang++（C++） >= 13.0.0 -O1/O2 打印并正常退出

初步结果：只有在比较新的C++上才会触发，稳定复现，因此选定 clang++ test.cpp -O1 作为目标进行研究。

objdump/gdb 误入歧途

通过 objdump -d a.out 可以看到，_start 函数直接调用了 unreachable 函数。（一口盐汽水就喷了在屏幕上。。。）

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Disassembly of section .text:

0000000000001050 <_start>:

    1050:       f3 0f 1e fa             endbr64

    1054:       31 ed                   xor    %ebp,%ebp

    1056:       49 89 d1                mov    %rdx,%r9

    1059:       5e                      pop    %rsi

    105a:       48 89 e2                mov    %rsp,%rdx

    105d:       48 83 e4 f0             and    $0xfffffffffffffff0,%rsp

    1061:       50                      push   %rax

    1062:       54                      push   %rsp

    1063:       45 31 c0                xor    %r8d,%r8d

    1066:       31 c9                   xor    %ecx,%ecx

    1068:       48 8d 3d d1 00 00 00    lea    0xd1(%rip),%rdi       

    106f:       ff 15 6b 2f 00 00       call   *0x2f6b(%rip)       

    1075:       f4                      hlt

    1076:       66 2e 0f 1f 84 00 00    cs nopw 0x0(%rax,%rax,1)

gdb 调试，很诡异，也直接就断在了 unreachable 里，说明二进制确实执行到了这里。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

gdb a.out

(gdb) b main

Breakpoint 1 at 0x1140

(gdb) r

Starting program: /tmp/a.out

[Thread debugging using libthread_db enabled]

Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Breakpoint 1, 0x0000555555555140 in unreachable() ()

(gdb) disassemble $pc

Dump of assembler code for function _Z11unreachablev:

=> 0x0000555555555140 <+0>:     push   %rax

   0x0000555555555141 <+1>:     lea    0xebc(%rip),%rdi       

   0x0000555555555148 <+8>:     call   0x555555555030 <[email protected]>

   0x000055555555514d <+13>:    pop    %rax

   0x000055555555514e <+14>:    ret

End of assembler dump.

(gdb)

什么？还有程序没有main、从别的函数开始执行？这连接器是抽什么风？

readelf 初见端倪

说实话，我还是第一次见到 “没有main函数、但是能运行” 的程序，于是查看符号表，发现main函数还在，和unreachable指向同一个偏移，但函数大小为0

1

2

3

4

5

6

7

8

9

readelf -s a.out

Symbol table '.symtab' contains 37 entries:

  Num:    Value          Size Type    Bind   Vis      Ndx Name

  22: 0000000000001140     0 FUNC    GLOBAL DEFAULT   15 main

  23: 0000000000001140    15 FUNC    GLOBAL DEFAULT   15 _Z11unreachablev

objdump -t a.out

0000000000001140 g     F .text  0000000000000000              main

0000000000001140 g     F .text  000000000000000f              _Z11unreachablev

也就是说，main函数的函数体被清空了，恰好指向了unreachable的位置，“越界”执行了下一个函数的代码。

查看汇编

clang++ -c -S test.cpp -O1 得到 test.s 汇编文件。 我去掉了汇编大部分不必要的注释，但故意保留了一部分，才能让读者知道，他读的是汇编 。可以看到，main函数里一条指令都没有，全部都是点开头的或者井号开头的注释。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

        .globl  main                           

        .p2align        4, 0x90

        .type   main,@function

main:                                  

        .cfi_startproc

.Lfunc_end0:

        .size   main, .Lfunc_end0-main

        .cfi_endproc

        .globl  _Z11unreachablev               

        .p2align        4, 0x90

        .type   _Z11unreachablev,@function

_Z11unreachablev:                      

        .cfi_startproc

        pushq   %rax

        leaq    .Lstr(%rip), %rdi

        popq    %rax

        retq

去除全部注释后就是，main 和 _Z11unreachablev 指向同一段汇编代码：

1

2

3

4

5

6

7

main:                                  

_Z11unreachablev:                      

        pushq   %rax

        leaq    .Lstr(%rip), %rdi

        popq    %rax

        retq

查看IR

clang++ -emit-llvm -S -c test.cpp -O1 得到 test.ll IR文件。可以看出，确实在IR阶段main的内容就发生了变换，由原先的死循环被替换成了 unreachable。注意，这个unreachable是一条名叫UnreachableInstruction的指令，并非函数名

1

2

3

4

; Function Attrs: mustprogress nofree norecurse noreturn nosync nounwind readnone uwtable willreturn

define dso_local noundef i32 @main() local_unnamed_addr

  unreachable

}

对比 -O0 的输出结果。

1

2

3

4

5

6

7

8

9

; Function Attrs: mustprogress noinline norecurse nounwind optnone uwtable

define dso_local noundef i32 @main()

  %1 = alloca i32, align 4

  store i32 0, i32* %1, align 4

  br label %2

2:                                                ; preds = %0, %2

  br label %2, !llvm.loop !6

}

最终，可以得到结论，这个反常的现象是在IR层面的编译器优化引起的。

背景知识

2022年我也遇到过编译器优化引发的逻辑错误，被 dmxcsnsbh 一眼看穿，并推荐我文章：https://www.blackhat.com/eu-20/briefings/schedule/#finding-bugs-compiler-knows-but-doesnt-tell-you-dissecting-undefined-behavior-optimizations-in-llvm-21128 。于是我第一反应就是 LLVM 进行了优化，但这个是不是 UB 引起的，一眼没看出来。

dump llvm ir transform

通过命令：clang++ -mllvm --print-before-all -mllvm --print-after-all test.cpp -O1 拿到每个pass的所有输入和输出。

经过搜索，找到如下日志，表明经过 LoopDeletionPass 的处理，原先的循环被替换成了 unreachable instruction：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

*** IR Dump Before LoopDeletionPass on Parallel Loop at depth 1 containing: %1<header><latch> ***

; Preheader:

  br label %1

; Loop:

1:                                                ; preds = %0, %1

  br label %1, !llvm.loop !5

*** IR Dump After LoopDeletionPass on Parallel Loop at depth 1 containing: %1<header><latch> (invalidated) ***

; ModuleID = 'test.cpp'

source_filename = "test.cpp"

target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"

target triple = "x86_64-pc-linux-gnu"

@.str = private unnamed_addr constant [12 x i8] c"HelloWorld\0A\00", align 1

@str = private unnamed_addr constant [11 x i8] c"HelloWorld\00", align 1

; Function Attrs: mustprogress nofree norecurse noreturn nosync nounwind readnone uwtable willreturn

define dso_local noundef i32 @main() local_unnamed_addr

  unreachable

}

粗略阅读代码

代码位于：https://llvm.org/doxygen/LoopDeletion_8cpp_source.html

1

2

3

4

// This file implements the Dead Loop Deletion Pass. This pass is responsible

// for eliminating loops with non-infinite computable trip counts that have no

// side effects or volatile instructions, and do not contribute to the

// computation of the function's return value.

大意就是，删除对执行无影响的死循环。个人观点，已经是死循环了，所以标记为 unreachable 也是说得过去的。

LoopDeletionPass 继承了 LoopPass，实现 runOnLoop，调用 deleteLoopIfDead，内部使用 isLoopDead 判断是否需要被移除，移除时调用来自 LoopUtils.h 的 deleteDeadLoop 来执行。

而 deleteDeadLoop 中，出现了关键的 CreateUnreachable ：

1

2

3

4

5

6

7

8

} else {

  assert(L->hasNoExitBlocks() &&

          "Loop should have either zero or one exit blocks.");

  Builder.SetInsertPoint(OldTerm);

  Builder.CreateUnreachable();

  Preheader->getTerminator()->eraseFromParent();

}

答案：所以答案很简单。。。

  1. 因为删除了死循环，导致main函数里只有一句 unreachable instruction
  2. 在codegen阶段，后端认为 main 里只有一句 unreachable，不需要创建对应的汇编指令，只有一个符号，函数长度为0
  3. 恰好在该位置，生成了与main函数相邻的函数，而main的长度为0，所以main实际指向了相邻的函数（没有人规定两个符号不能指向同一个偏移）
  4. 后续连接过程不会遇到任何问题，造成诡异的情况发生了

C++里是UB。https://en.cppreference.com/w/cpp/language/ub ，Infinite loop without side-effects 。

C语言里不是UB，见 ISO/IEC 9899 J.2 Undefined behavior 后，并没有找到和loop相关的关键词。

包括官方还给了一个demo，优化后fermat直接返回true（不解释了，不会，自行领悟）

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

bool fermat()

{

    const int max_value = 1000;

    // Endless loop with no side effects is UB

    for (int a = 1, b = 1, c = 1; true; )

    {

        if (((a * a * a) == ((b * b * b) + (c * c * c))))

            return true; // disproved :)

        a++;

        if (a > max_value)

        {

            a = 1;

            b++;

        }

        if (b > max_value)

        {

            b = 1;

            c++;

        }

        if (c > max_value)

            c = 1;

    }

    return false; // not disproved

}

int main()

{

    std::cout << "Fermat's Last Theorem ";

    fermat()

        ? std::cout << "has been disproved!\n"

        : std::cout << "has not been disproved.\n";

}

获得两个未经处理的 ll 文件：clang test.c -O0 -emit-llvm -c -S -o test.c.ll 和 clang++ test.cpp -O0 -emit-llvm -c -S -o test.cpp.ll。

将 optnone 移除掉：sed -i 's/optnone//' test.c.ll 和 sed -i 's/optnone//' test.cpp.ll。

使用 opt 将 LoopDeletionPass 作用于 C 的 IR 和 CPP 的 IR。（因为需要编译llvm，因为要看LLVM_DEBUG的日志，需要开启 DLLVM_ENABLE_ASSERTIONS=TRUE）

二者执行起来日志分别为：

opt作用于C语言

1

2

3

4

opt -debug-only=loop-delete -passes=loop-deletion test.c.ll -S -o /dev/null

Analyzing Loop for deletion: Loop at depth 1 containing: %2<header><latch>

Could not compute SCEV MaxBackedgeTakenCount and was not required to make progress.

Loop is not invariant, cannot delete.

opt作用于C++语言

1

2

3

opt -debug-only=loop-delete -passes=loop-deletion test.cpp.ll -S -o /dev/null

Analyzing Loop for deletion: Parallel Loop at depth 1 containing: %2<header><latch>

Loop is invariant, delete it!

显然，二者出现了偏差，略微diff一下。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

-; Function Attrs: noinline nounwind  uwtable

-define dso_local i32 @main()

+; Function Attrs: mustprogress noinline norecurse nounwind  uwtable

+define dso_local noundef i32 @main()

   %1 = alloca i32, align 4

   store i32 0, i32* %1, align 4

   br label %2

 2:                                                ; preds = %0, %2

-  br label %2

+  br label %2, !llvm.loop !6

 }

+!6 = distinct !{!6, !7}

+!7 = !{!"llvm.loop.mustprogress"}

不清楚哪里引起的，把这个6和7补上去，C语言就可以正确地被处理为unreachable了，研究了很久，超出知识范围了，看不懂，反正就 LoopPass 认为 MaxBackedgeTakenCount 的数据不对，不给删。

结合上文说的C里不算UB、C++里算UB，编译器这么做也是完全正确的。

有时我自己也写点死循环，UB竟在我身边，UB竟是我自己。

[招生]科锐逆向工程师培训46期预科班将于 2023年02月09日 正式开班


文章来源: https://bbs.pediy.com/thread-276082.htm
如有侵权请联系:admin#unsafe.sh