1 of 38

Digital Watermarks for

LLVM Intermediate Representation

R. Nagayama, L. Chen, H. Inaba

Kyoto Institute of Technology

2 of 38

Digital Watermarks

Embedding Information in Content

2

3 of 38

Digital Watermarks

Embedding Information in Content

​

3

4 of 38

Digital Watermarks

Embedding Information in Content

​

4

5 of 38

Digital Watermarks

Embedding Information in Content

​

5

6 of 38

Digital Watermarks

Embedding Information in Content

6

Upload

7 of 38

Digital Watermarks

Embedding Information in Content

​

7

?

Upload

8 of 38

Digital Watermarks

Embedding Information in Content

​

8

Embed

9 of 38

Digital Watermarks

Embedding Information in Content

9

Embed

Upload

10 of 38

Digital Watermarks

Embedding Information in Content

​

10

Embed

​

Upload

11 of 38

Overwrite Attack

Background ▷ 1. Modifying the Program Binary ▷ Overwrite Attack

Embed

P

P

Deliver

w

P

w

w

Developer

12 of 38

Overwrite Attack

Background ▷ 1. Modifying the Program Binary ▷ Overwrite Attack

Embed

P

P

Deliver

w

Embed

P

z

P

w

w

z

Attacker

Developer

Erase/Overwrite Watermarks with the Same Method

13 of 38

2. Modifying the Source Code

Background ▷ 2. Modifying the Source Code

Embed

Src

Compile

w

Deliver

P

w

w

Attacker

Developer

P

w

Src

Can’t Overwrite ∵Can’t Access the Source Codes

14 of 38

Basic Blocks

14

%C = add i32 %A, %B

Basic Block

%E = sub i32 %C, %D

br label %L

%B = load i32* %y

%A = load i32* %x

・Sequence of instructions

・Only one branch instruction (Terminator)

・ at the end

Function

BasicBlock 3

BasicBlock 2

BasicBlock 1

・Chunk of basic blocks

15 of 38

Method-1: Changing the Order of Basic Blocks

​

int main(void) {

int a = 2;

if (a % 2)

puts("Odd");

else

puts("Even");

return 0;

}

C

16 of 38

Method-1: Changing the Order of Basic Blocks

​

int main(void) {

int a = 2;

if (a % 2)

puts("Odd");

else

puts("Even");

return 0;

}

C

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %6, label %8

​

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %10

​

; <label>:8:

%9 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %10

​

; <label>:10:

ret i32 0

}

LLVM IR

17 of 38

Method-1: Changing the Order of Basic Blocks

​

int main(void) {

int a = 2;

if (a % 2)

puts("Odd");

else

puts("Even");

return 0;

}

C

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %6, label %8

​

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %10

​

; <label>:8:

%9 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %10

​

; <label>:10:

ret i32 0

}

LLVM IR

18 of 38

Method-1: Changing the Order of Basic Blocks

​

int main(void) {

int a = 2;

if (a % 2)

puts("Odd");

else

puts("Even");

return 0;

}

C

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %6, label %8

​

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %10

​

; <label>:8:

%9 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %10

​

; <label>:10:

ret i32 0

}

LLVM IR

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %9, label %6

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %8

​

; <label>:8:

ret i32 0

​

; <label>:9:

%10 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %8

}

Embedded IR

19 of 38

Method-1: Changing the Order of Basic Blocks

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %6, label %8

​

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %10

​

; <label>:8:

%9 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %10

​

; <label>:10:

ret i32 0

}

LLVM IR

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %9, label %6

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %8

​

; <label>:8:

ret i32 0

​

; <label>:9:

%10 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %8

}

​

Embedded IR

20 of 38

Method-1: Changing the Order of Basic Blocks

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %6, label %8

​

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %10

​

; <label>:8:

%9 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %10

​

; <label>:10:

ret i32 0

}

LLVM IR

​

​

main:� .cfi_startproc�# %bb.0:� pushq %rbp� .cfi_def_cfa_offset 16� .cfi_offset %rbp, -16� movq %rsp, %rbp� .cfi_def_cfa_register %rbp� subq $16, %rsp� movl $0, -4(%rbp)� movl $2, -8(%rbp)� movl -8(%rbp), %eax� cltd� movl $2, %ecx� idivl %ecx� cmpl $0, %edx� je .LBB0_2�# %bb.1:� movabsq $.L.str, %rdi� callq puts� movl %eax, -12(%rbp)� jmp .LBB0_3�.LBB0_2:� movabsq $.L.str.1, %rdi� callq puts� movl %eax, -16(%rbp)�.LBB0_3:� xorl %eax, %eax� addq $16, %rsp� popq %rbp� .cfi_def_cfa %rsp, 8� retq

x86_64 asm

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %9, label %6

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %8

​

; <label>:8:

ret i32 0

​

; <label>:9:

%10 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %8

}

​

Embedded IR

21 of 38

Method-1: Changing the Order of Basic Blocks

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %6, label %8

​

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %10

​

; <label>:8:

%9 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %10

​

; <label>:10:

ret i32 0

}

LLVM IR

​

​

main:� .cfi_startproc�# %bb.0:� pushq %rbp� .cfi_def_cfa_offset 16� .cfi_offset %rbp, -16� movq %rsp, %rbp� .cfi_def_cfa_register %rbp� subq $16, %rsp� movl $0, -4(%rbp)� movl $2, -8(%rbp)� movl -8(%rbp), %eax� cltd� movl $2, %ecx� idivl %ecx� cmpl $0, %edx� je .LBB0_2�# %bb.1:� movabsq $.L.str, %rdi� callq puts� movl %eax, -12(%rbp)� jmp .LBB0_3�.LBB0_2:� movabsq $.L.str.1, %rdi� callq puts� movl %eax, -16(%rbp)�.LBB0_3:� xorl %eax, %eax� addq $16, %rsp� popq %rbp� .cfi_def_cfa %rsp, 8� retq

x86_64 asm

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %9, label %6

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %8

​

; <label>:8:

ret i32 0

​

; <label>:9:

%10 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %8

}

​

Embedded IR

22 of 38

Method-1: Changing the Order of Basic Blocks

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %6, label %8

​

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %10

​

; <label>:8:

%9 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %10

​

; <label>:10:

ret i32 0

}

LLVM IR

​

​

main:� .cfi_startproc�# %bb.0:� pushq %rbp� .cfi_def_cfa_offset 16� .cfi_offset %rbp, -16� movq %rsp, %rbp� .cfi_def_cfa_register %rbp� subq $16, %rsp� movl $0, -4(%rbp)� movl $2, -8(%rbp)� movl -8(%rbp), %eax� cltd� movl $2, %ecx� idivl %ecx� cmpl $0, %edx� je .LBB0_2�# %bb.1:� movabsq $.L.str, %rdi� callq puts� movl %eax, -12(%rbp)� jmp .LBB0_3�.LBB0_2:� movabsq $.L.str.1, %rdi� callq puts� movl %eax, -16(%rbp)�.LBB0_3:� xorl %eax, %eax� addq $16, %rsp� popq %rbp� .cfi_def_cfa %rsp, 8� retq

x86_64 asm

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %9, label %6

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %8

​

; <label>:8:

ret i32 0

​

; <label>:9:

%10 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %8

}

​

Embedded IR

​

​

main:� .cfi_startproc�# %bb.0:� pushq %rbp� .cfi_def_cfa_offset 16� .cfi_offset %rbp, -16� movq %rsp, %rbp� .cfi_def_cfa_register %rbp� subq $16, %rsp� movl $0, -4(%rbp)� movl $2, -8(%rbp)� movl -8(%rbp), %eax� cltd� movl $2, %ecx� idivl %ecx� cmpl $0, %edx� jne .LBB0_3�# %bb.1:� movabsq $.L.str.1, %rdi� callq puts� movl %eax, -12(%rbp)�.LBB0_2:� xorl %eax, %eax� addq $16, %rsp� popq %rbp� .cfi_def_cfa %rsp, 8� retq�.LBB0_3:� .cfi_def_cfa %rbp, 16� movabsq $.L.str, %rdi� callq puts� movl %eax, -16(%rbp)� jmp .LBB0_2

x86_64 asm

23 of 38

Method-1: Changing the Order of Basic Blocks

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %6, label %8

​

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %10

​

; <label>:8:

%9 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %10

​

; <label>:10:

ret i32 0

}

LLVM IR

​

​

main:� .cfi_startproc�# %bb.0:� pushq %rbp� .cfi_def_cfa_offset 16� .cfi_offset %rbp, -16� movq %rsp, %rbp� .cfi_def_cfa_register %rbp� subq $16, %rsp� movl $0, -4(%rbp)� movl $2, -8(%rbp)� movl -8(%rbp), %eax� cltd� movl $2, %ecx� idivl %ecx� cmpl $0, %edx� je .LBB0_2�# %bb.1:� movabsq $.L.str, %rdi� callq puts� movl %eax, -12(%rbp)� jmp .LBB0_3�.LBB0_2:� movabsq $.L.str.1, %rdi� callq puts� movl %eax, -16(%rbp)�.LBB0_3:� xorl %eax, %eax� addq $16, %rsp� popq %rbp� .cfi_def_cfa %rsp, 8� retq

x86_64 asm

​

​

define dso_local i32 @main() #0 {

%1 = alloca i32, align 4

%2 = alloca i32, align 4

store i32 0, i32* %1, align 4

store i32 2, i32* %2, align 4

%3 = load i32, i32* %2, align 4

%4 = srem i32 %3, 2

%5 = icmp ne i32 %4, 0

br i1 %5, label %9, label %6

; <label>:6:

%7 = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i32 0, i32 0))

br label %8

​

; <label>:8:

ret i32 0

​

; <label>:9:

%10 = call i32 @puts(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0))

br label %8

}

​

Embedded IR

​

​

main:� .cfi_startproc�# %bb.0:� pushq %rbp� .cfi_def_cfa_offset 16� .cfi_offset %rbp, -16� movq %rsp, %rbp� .cfi_def_cfa_register %rbp� subq $16, %rsp� movl $0, -4(%rbp)� movl $2, -8(%rbp)� movl -8(%rbp), %eax� cltd� movl $2, %ecx� idivl %ecx� cmpl $0, %edx� jne .LBB0_3�# %bb.1:� movabsq $.L.str.1, %rdi� callq puts� movl %eax, -12(%rbp)�.LBB0_2:� xorl %eax, %eax� addq $16, %rsp� popq %rbp� .cfi_def_cfa %rsp, 8� retq�.LBB0_3:� .cfi_def_cfa %rbp, 16� movabsq $.L.str, %rdi� callq puts� movl %eax, -16(%rbp)� jmp .LBB0_2

x86_64 asm

24 of 38

Instructions

24

%C = add i32 %A , %B

25 of 38

Instructions

25

%C = add i32 %A , %B

Output

26 of 38

Instructions

26

%C = add i32 %A , %B

Output

Opcode

27 of 38

Instructions

27

%C = add i32 %A , %B

Input1

Input2

Opcode

Output

28 of 38

Instructions

28

%C = add i32 %A , %B

Input1

Input2

Opcode

Output

of Commutative instruction can be swapped

Input1

Input2

29 of 38

Method-2: Swapping Instruction Operands

2. 埋め込み方法 ▷ 命令オペランドの入れ替え ▷ 埋め込み結果

​

if (i % 3 == 0)

C

30 of 38

Method-2: Swapping Instruction Operands

2. 埋め込み方法 ▷ 命令オペランドの入れ替え ▷ 埋め込み結果

​

if (i % 3 == 0)

​

%9 = urem i8 %3, 3�%10 = icmp eq i8 %9, 0�br i1 %10, label %11, label %13

LLVM IR

C

31 of 38

Method-2: Swapping Instruction Operands

2. 埋め込み方法 ▷ 命令オペランドの入れ替え ▷ 埋め込み結果

​

if (i % 3 == 0)

​

%9 = urem i8 %3, 3�%10 = icmp eq i8 %9, 0�br i1 %10, label %11, label %13

LLVM IR

C

32 of 38

Method-2: Swapping Instruction Operands

2. 埋め込み方法 ▷ 命令オペランドの入れ替え ▷ 埋め込み結果

​

if (i % 3 == 0)

​

%9 = urem i8 %3, 3�%10 = icmp eq i8 %9, 0�br i1 %10, label %11, label %13

LLVM IR

C

​

%9 = urem i8 %3, 3�%10 = icmp eq i8 0, %9�br i1 %10, label %11, label %13

Embedded IR

33 of 38

Method-2: Swapping Instruction Operands

2. 埋め込み方法 ▷ 命令オペランドの入れ替え ▷ 埋め込み結果

​

if (i % 3 == 0)

​

%9 = urem i8 %3, 3�%10 = icmp eq i8 %9, 0�br i1 %10, label %11, label %13

LLVM IR

​

movb 31(%rsp), %al� movzbw %al, %ax� movb $3, %cl� divb %cl� shrw $8, %ax� movb %al, %cl� cmpb $0, %cl� jne .LBB0_5

x86_64 asm

C

​

%9 = urem i8 %3, 3�%10 = icmp eq i8 0, %9�br i1 %10, label %11, label %13

Embedded IR

​

xorl %eax, %eax�movb %al, %cl�movb 31(%rsp), %dl�movzbw %dl, %ax�movb $3, %sil�divb %sil�shrw $8, %ax�movb %al, %sil�cmpb %sil, %cl�jne .LBB0_5

Embedded asm

34 of 38

Method-2: Swapping Instruction Operands

2. 埋め込み方法 ▷ 命令オペランドの入れ替え ▷ 埋め込み結果

​

if (i % 3 == 0)

​

%9 = urem i8 %3, 3�%10 = icmp eq i8 %9, 0�br i1 %10, label %11, label %13

LLVM IR

​

movb 31(%rsp), %al� movzbw %al, %ax� movb $3, %cl� divb %cl� shrw $8, %ax� movb %al, %cl� cmpb $0, %cl� jne .LBB0_5

x86_64 asm

C

​

%9 = urem i8 %3, 3�%10 = icmp eq i8 0, %9�br i1 %10, label %11, label %13

Embedded IR

​

xorl %eax, %eax�movb %al, %cl�movb 31(%rsp), %dl�movzbw %dl, %ax�movb $3, %sil�divb %sil�shrw $8, %ax�movb %al, %sil�cmpb %sil, %cl�jne .LBB0_5

Embedded asm

35 of 38

Evaluation

zlib::deflate(200MB) with no watermarks

35

​

No opt

IRO

MCO

LTO

ave t

10250 ms

7602 ms

4425 ms

4411 ms

stddev σ

46 ms

49 ms

49 ms

40 ms

36 of 38

Evaluation

zlib::deflate(200MB) with IR level opt (IRO)

36

■

No watermark

■

Method-1

■

Method-2

■

Method-3

37 of 38

Evaluation

zlib::deflate(200MB) with machine code opt (MCO)

37

■

No watermark

■

Method-3

38 of 38

Thanks

All materials including the poster and this slides

are available at:

https://nagayamaryoga.github.io/study

(almost JP)