From 6142fa676731e158622ca7956c150c58bc57f1f2 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Wed, 11 Nov 2026 10:38:37 -0300 Subject: design: the graph of a function's blocks; two runs as a pair From the user. The disassembly's alternate form at a larger scale is the graph of its basic blocks: a block a box of rows with its offset, lines and visit count; execution flows down and a back edge is the one thing that climbs, in its loop's lane with the turn count; what the run never reached folds away. On the map it takes the disassembly's place; in the working frame a blocks lens draws its shape and the rows are its view. Verbs leave and turn carry the mark along an edge. Two runs of one program share a frame as a pair: the seam is the gutter, the source shared above, rows only one run has and values that differ marked at the seam. The scene it is made for sets a plain build against an ASan one in a stack overflow: the frame beside its shadow bytes, the store beside its check, and the step where they part. Co-Authored-By: Claude Fable 5.2 Claude-Session: https://claude.ai/code/session_016Y9MNCKgYCGiANnEwcEQxa --- design/mock/22-graph-sort.png | Bin 0 -> 226841 bytes design/mock/22-graph-sort.svg | 453 ++++++++++++++++++++++++++++ design/mock/23-graph-open.png | Bin 0 -> 169887 bytes design/mock/23-graph-open.svg | 229 ++++++++++++++ design/mock/24-graph-strip.png | Bin 0 -> 155495 bytes design/mock/24-graph-strip.svg | 596 +++++++++++++++++++++++++++++++++++++ design/mock/25-blocks-lens-480.png | Bin 0 -> 32015 bytes design/mock/25-blocks-lens.png | Bin 0 -> 191630 bytes design/mock/25-blocks-lens.svg | 464 +++++++++++++++++++++++++++++ design/mock/26-pair-rest-480.png | Bin 0 -> 30674 bytes design/mock/26-pair-rest.png | Bin 0 -> 208546 bytes design/mock/26-pair-rest.svg | 417 ++++++++++++++++++++++++++ design/mock/27-pair-store-480.png | Bin 0 -> 21819 bytes design/mock/27-pair-store.png | Bin 0 -> 154167 bytes design/mock/27-pair-store.svg | 218 ++++++++++++++ design/mock/28-pair-part-480.png | Bin 0 -> 32174 bytes design/mock/28-pair-part.png | Bin 0 -> 214064 bytes design/mock/28-pair-part.svg | 428 ++++++++++++++++++++++++++ design/mock/context.py | 12 +- design/mock/graph.py | 583 ++++++++++++++++++++++++++++++++++++ design/mock/libc-open.dis | 84 ++++++ design/mock/overflow.c | 10 + design/mock/pair.py | 231 ++++++++++++++ design/mock/reverse-O0.dis | 37 +++ design/mock/sort-O0.dis | 61 ++++ 25 files changed, 3818 insertions(+), 5 deletions(-) create mode 100644 design/mock/22-graph-sort.png create mode 100644 design/mock/22-graph-sort.svg create mode 100644 design/mock/23-graph-open.png create mode 100644 design/mock/23-graph-open.svg create mode 100644 design/mock/24-graph-strip.png create mode 100644 design/mock/24-graph-strip.svg create mode 100644 design/mock/25-blocks-lens-480.png create mode 100644 design/mock/25-blocks-lens.png create mode 100644 design/mock/25-blocks-lens.svg create mode 100644 design/mock/26-pair-rest-480.png create mode 100644 design/mock/26-pair-rest.png create mode 100644 design/mock/26-pair-rest.svg create mode 100644 design/mock/27-pair-store-480.png create mode 100644 design/mock/27-pair-store.png create mode 100644 design/mock/27-pair-store.svg create mode 100644 design/mock/28-pair-part-480.png create mode 100644 design/mock/28-pair-part.png create mode 100644 design/mock/28-pair-part.svg create mode 100644 design/mock/graph.py create mode 100644 design/mock/libc-open.dis create mode 100644 design/mock/overflow.c create mode 100644 design/mock/pair.py create mode 100644 design/mock/reverse-O0.dis create mode 100644 design/mock/sort-O0.dis (limited to 'design/mock') diff --git a/design/mock/22-graph-sort.png b/design/mock/22-graph-sort.png new file mode 100644 index 0000000..b77304a Binary files /dev/null and b/design/mock/22-graph-sort.png differ diff --git a/design/mock/22-graph-sort.svg b/design/mock/22-graph-sort.svg new file mode 100644 index 0000000..21d4041 --- /dev/null +++ b/design/mock/22-graph-sort.svg @@ -0,0 +1,453 @@ + + + + + + +sort.c +lines 1 to 22 of 22 +1 +int +a +[ +8 +] += +{ +4 +, +9 +, +17 +, +31 +, +12 +, +26 +, +5 +, +20 +} +; +2 +3 +void +swap +( +int +* +x +, +int +* +y +) +{ +4 +int +t += +* +x +; +5 +* +x += +* +y +; +6 +* +y += +t +; +7 +} +8 +9 +void +sort +( +int +n +) +{ +10 +for +( +int +i += +1 +; +i +< +n +; +i ++ ++ +) +{ +11 +int +j += +i +; + + +12 +while +( +j +> +0 +& +& +a +[ +j +- +1 +] +> +a +[ +j +] +) +{ + +13 +swap +( +& +a +[ +j +- +1 +] +, +& +a +[ +j +] +) +; + +14 +j +- +- +; +15 +} +16 +} +17 +} +18 +19 +int +main +( +void +) +{ +20 +sort +( +8 +) +; +21 +return +0 +; +22 +} +the map: sort's disassembly as its graph, two columns wide (1024 to 2816), at moment 370 of 465 in sort + + + +disassembly · sort +its blocks · visits so far · the edges the run took + + + + +6 + + + + + + + + +11 + + +5 + + +5 + + +×5 + + +×5 + + + +401143 +lines 9 to 10 +×1 ++0 +9 +push +rbp ++1 +mov +rbp, rsp ++4 +sub +rsp, 0x18 ++8 +mov +[rbp - 0x14], edi ++b +10 +mov +[rbp - 8] + + + + +, 1 ++12 +jmp +4011e1 + + + +40115a +lines 11 to 12 +×6 ++17 +11 +mov +eax, [rbp - 8] ++1a +mov +[rbp - 4], eax ++1d +12 +jmp +4011a2 + + + +401162 +lines 13 to 14 +×5 ++1f +13 +mov +eax, [rbp - 4] ++22 +cdqe + ++24 +lea +rdx, [rax*4] ++2c +lea +rax, [rip + 0x2eaa] ++33 +add +rdx, rax ++36 +mov +eax, [rbp - 4] ++39 +sub +eax, 1 ++3c +cdqe + ++3e +lea +rcx, [rax*4] ++46 +lea +rax, [rip + 0x2e90] ++4d +add +rax, rcx ++50 +mov +rsi, rdx ++53 +mov +rdi, rax ++56 +call +401116 + + +swap ++5b +14 +sub +[rbp - 4] + + + + +, 1 + + + +4011a2 +line 12 +×11 ++5f +12 +cmp +[rbp - 4] + + + + +, 0 ++63 +jle +4011dd + + + +4011a8 +line 12 +×11 ++65 +12 +mov +eax, [rbp - 4] ++68 +sub +eax, 1 ++6b +cdqe + ++6d +lea +rdx, [rax*4] ++75 +lea +rax, [rip + 0x2e61] ++7c +mov +edx, [rdx + rax*1] +404030 +◂ +17 ++7f +mov +eax, [rbp - 4] ++82 +cdqe + ++84 +lea +rcx, [rax*4] + ++8c +lea +rax, [rip + 0x2e4a] + ++93 +mov +eax, [rcx + rax*1] +404034 +◂ +5 + ++96 +cmp +edx, eax +17 + : +5 + +zf + sf + of + + + ++98 +jg +401162 +taken + · reads zf sf of + + + +4011dd +line 10 +×5 ++9a +10 +add +[rbp - 8] + + + + +, 1 + + + +4011e1 +line 10 +×6 ++9e +10 +mov +eax, [rbp - 8] ++a1 +cmp +eax, [rbp - 0x14] ++a4 +jl +40115a + + + +4011ed +line 17 ++aa +17 +nop + ++ab +nop + ++ac +leave + ++ad +ret + + + + diff --git a/design/mock/23-graph-open.png b/design/mock/23-graph-open.png new file mode 100644 index 0000000..20b08c6 Binary files /dev/null and b/design/mock/23-graph-open.png differ diff --git a/design/mock/23-graph-open.svg b/design/mock/23-graph-open.svg new file mode 100644 index 0000000..f6154e7 --- /dev/null +++ b/design/mock/23-graph-open.svg @@ -0,0 +1,229 @@ + + + +the map: libc's open as its graph · 19 blocks, the run reached 8 so far; the 11 it never reached are folded into five boxes + + + +disassembly · open · libc.so.6 +no source · 19 blocks · folded: 11 never reached + + + + +1 + + + + +1 + + + + +1 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +7ffff7d10ec0 +×1 ++0 +endbr64 + ++4 +push +rbp ++5 +mov +rbp, rsp ++8 +sub +rsp, 0x70 ++c +mov +[rbp - 0x30], rdx ++10 +mov +rax, fs:0x28 ++19 +mov +[rbp - 0x48], rax ++1d +xor +eax, eax ++1f +test +sil, 0x40 ++23 +jne +7ffff7d10f90 + + + +7ffff7d10ee9 +×1 ++29 +mov +eax, esi ++2b +xor +r10d, r10d ++2e +not +eax ++30 +test +eax, 0x410000 ++35 +je +7ffff7d10f90 + + + +7ffff7d10efb +×1 ++3b +mov +r11, fs:0x10 ++44 +movsxd +rdx, esi ++47 +mov +eax, [r11 + 0x308] ++4e +cmp +[rip + 0x11018b] + +, 0 ++55 +jne +7ffff7d10fb0 + + + +7ffff7d10fb0 +×1 ++f0 +mov +rsi, rdi ++f3 +xor +r9d, r9d + ++f6 +xor +r8d, r8d + ++f9 +mov +rdi, 0xffffffffffffff9c + ++100 +mov +eax, 0x101 + + + ++105 +syscall + +openat + nr 257 ++107 +mov +rdx, rax + + + +7ffff7d10fca ++10a +cmp +rax, 0xfffffffffffff000 ++110 +ja +7ffff7d10fe8 + + + +7ffff7d10fd2 ++112 +mov +eax, edx + + + +7ffff7d10fd4 ++114 +mov +rdx, [rbp - 0x48] ++118 +sub +rdx, fs:0x28 ++121 +jne +7ffff7d10fec + + + +7ffff7d10fe3 ++123 +leave + ++124 +ret + + + + + ++d0 to +eb +never reached +the O_CREAT path: the mode from the varargs + + ++5b to +b3 +4 blocks never reached +multi-threaded: a cancellable call + + ++128 to +cd +3 blocks never reached +an error: errno set, -1 returned + + ++136 to +149 +2 blocks never reached +cancelled + + ++12c to +130 +2 blocks never reached +the canary broken + diff --git a/design/mock/24-graph-strip.png b/design/mock/24-graph-strip.png new file mode 100644 index 0000000..390a859 Binary files /dev/null and b/design/mock/24-graph-strip.png differ diff --git a/design/mock/24-graph-strip.svg b/design/mock/24-graph-strip.svg new file mode 100644 index 0000000..e9db6d9 --- /dev/null +++ b/design/mock/24-graph-strip.svg @@ -0,0 +1,596 @@ + + + + +1 +the condition +cur at jne, the compare's chips framed; the second turn + + + +disassembly · reverse + + + + + +1 + + + + +×1 + + + +401188 +lines 17 to 20 +×1 ++0 +17 +push +rbp ++1 +mov +rbp, rsp ++4 +18 +mov +[rbp - 0x18] + + + + + + + + +, 0 ++c +19 +mov +rax, [rip + 0x2e7d] ++13 +mov +[rbp - 0x10], rax ++17 +20 +jmp +4011c9 + + + +4011a1 +lines 21 to 24 +×1 ++19 +21 +mov +rax, [rbp - 0x10] ++1d +mov +rax, [rax + 8] ++21 +mov +[rbp - 8], rax ++25 +22 +mov +rax, [rbp - 0x10] ++29 +mov +rdx, [rbp - 0x18] ++2d +mov +[rax + 8], rdx ++31 +23 +mov +rax, [rbp - 0x10] ++35 +mov +[rbp - 0x18], rax ++39 +24 +mov +rax, [rbp - 8] ++3d +mov +[rbp - 0x10], rax + + + +4011c9 +line 20 +×2 ++41 +20 +cmp +[rbp - 0x10] + + + + + + + + +, 0 +1004070 + : +0 + +zf + + + ++46 +jne +4011a1 +taken + · reads zf + + + +4011d0 +lines 26 to 27 ++48 +26 +mov +rax, [rbp - 0x18] ++4c +mov +[rip + 0x2e3d], rax ++53 +27 +nop + ++54 +pop +rbp ++55 +ret + + + + + +2 +the edge taken +the edge lit gold, the mark on it, halfway + + + +disassembly · reverse + + + + + +2 + + + + +×1 + + + +401188 +lines 17 to 20 +×1 ++0 +17 +push +rbp ++1 +mov +rbp, rsp ++4 +18 +mov +[rbp - 0x18] + + + + + + + + +, 0 ++c +19 +mov +rax, [rip + 0x2e7d] ++13 +mov +[rbp - 0x10], rax ++17 +20 +jmp +4011c9 + + + +4011a1 +lines 21 to 24 +×2 ++19 +21 +mov +rax, [rbp - 0x10] ++1d +mov +rax, [rax + 8] ++21 +mov +[rbp - 8], rax ++25 +22 +mov +rax, [rbp - 0x10] ++29 +mov +rdx, [rbp - 0x18] ++2d +mov +[rax + 8], rdx ++31 +23 +mov +rax, [rbp - 0x10] ++35 +mov +[rbp - 0x18], rax ++39 +24 +mov +rax, [rbp - 8] ++3d +mov +[rbp - 0x10], rax + + + +4011c9 +line 20 +×2 ++41 +20 +cmp +[rbp - 0x10] + + + + + + + + +, 0 ++46 +jne +4011a1 + + + +4011d0 +lines 26 to 27 ++48 +26 +mov +rax, [rbp - 0x18] ++4c +mov +[rip + 0x2e3d], rax ++53 +27 +nop + ++54 +pop +rbp ++55 +ret + + + + + + + +3 +the loop's turn +the back edge climbs, the mark on it; its count struck: the second turn + + + +disassembly · reverse + + + + + +2 + + + + + +×2 + + + +401188 +lines 17 to 20 +×1 ++0 +17 +push +rbp ++1 +mov +rbp, rsp ++4 +18 +mov +[rbp - 0x18] + + + + + + + + +, 0 ++c +19 +mov +rax, [rip + 0x2e7d] ++13 +mov +[rbp - 0x10], rax ++17 +20 +jmp +4011c9 + + + +4011a1 +lines 21 to 24 +×2 ++19 +21 +mov +rax, [rbp - 0x10] ++1d +mov +rax, [rax + 8] ++21 +mov +[rbp - 8], rax ++25 +22 +mov +rax, [rbp - 0x10] ++29 +mov +rdx, [rbp - 0x18] ++2d +mov +[rax + 8], rdx ++31 +23 +mov +rax, [rbp - 0x10] ++35 +mov +[rbp - 0x18], rax ++39 +24 +mov +rax, [rbp - 8] ++3d +mov +[rbp - 0x10], rax + + + +4011c9 +line 20 +×3 ++41 +20 +cmp +[rbp - 0x10] + + + + + + + + +, 0 ++46 +jne +4011a1 + + + +4011d0 +lines 26 to 27 ++48 +26 +mov +rax, [rbp - 0x18] ++4c +mov +[rip + 0x2e3d], rax ++53 +27 +nop + ++54 +pop +rbp ++55 +ret + + + + + + + +4 +the way out +not taken: down to the exit, landed + + + +disassembly · reverse + + + + + +3 + + +1 + + +×3 + + + +401188 +lines 17 to 20 +×1 ++0 +17 +push +rbp ++1 +mov +rbp, rsp ++4 +18 +mov +[rbp - 0x18] + + + + + + + + +, 0 ++c +19 +mov +rax, [rip + 0x2e7d] ++13 +mov +[rbp - 0x10], rax ++17 +20 +jmp +4011c9 + + + +4011a1 +lines 21 to 24 +×3 ++19 +21 +mov +rax, [rbp - 0x10] ++1d +mov +rax, [rax + 8] ++21 +mov +[rbp - 8], rax ++25 +22 +mov +rax, [rbp - 0x10] ++29 +mov +rdx, [rbp - 0x18] ++2d +mov +[rax + 8], rdx ++31 +23 +mov +rax, [rbp - 0x10] ++35 +mov +[rbp - 0x18], rax ++39 +24 +mov +rax, [rbp - 8] ++3d +mov +[rbp - 0x10], rax + + + +4011c9 +line 20 +×4 ++41 +20 +cmp +[rbp - 0x10] + + + + + + + + +, 0 ++46 +jne +4011a1 + + + +4011d0 +lines 26 to 27 +×1 + + + ++48 +26 +mov +rax, [rbp - 0x18] ++4c +mov +[rip + 0x2e3d], rax ++53 +27 +nop + ++54 +pop +rbp ++55 +ret + + + + + diff --git a/design/mock/25-blocks-lens-480.png b/design/mock/25-blocks-lens-480.png new file mode 100644 index 0000000..80276c3 Binary files /dev/null and b/design/mock/25-blocks-lens-480.png differ diff --git a/design/mock/25-blocks-lens.png b/design/mock/25-blocks-lens.png new file mode 100644 index 0000000..1a348eb Binary files /dev/null and b/design/mock/25-blocks-lens.png differ diff --git a/design/mock/25-blocks-lens.svg b/design/mock/25-blocks-lens.svg new file mode 100644 index 0000000..3504f8e --- /dev/null +++ b/design/mock/25-blocks-lens.svg @@ -0,0 +1,464 @@ + + + + + + +the blocks of sort +its blocks · the visits · the path + + + + + + + + + + + + + + + + + + +×5 + + +×5 + + ++0 +×1 + + ++17 +×6 + + ++1f +×5 + + ++5f +×11 + + ++65 +×11 + + ++9a +×5 + + ++9e +×6 + + ++aa + + + +disassembly +sort · +84 to +a1 +4011 +c7 +12 +lea +rcx, [rax*4] + +4011 +cf +lea +rax, [rip + 0x2e4a] + +4011 +d6 +mov +eax, [rcx + rax*1] +404034 +◂ +5 + +4011 +d9 +cmp +edx, eax +17 + : +5 + +zf + sf + of + + + +4011 +db +jg +401162 +taken + · reads zf sf of +4011 +dd +10 +add +[rbp - 8] + + + + +, 1 +4011 +e1 +mov +eax, [rbp - 8] + + + +sort.c +lines 1 to 21 of 22 +1 +int +a +[ +8 +] += +{ +4 +, +9 +, +17 +, +31 +, +12 +, +26 +, +5 +, +20 +} +; +2 +3 +void +swap +( +int +* +x +, +int +* +y +) +{ +4 +int +t += +* +x +; +5 +* +x += +* +y +; +6 +* +y += +t +; +7 +} +8 +9 +void +sort +( +int +n +) +{ +10 +for +( +int +i += +1 +; +i +< +n +; +i ++ ++ +) +{ +11 +int +j += +i +; + + +12 +while +( +j +> +0 +& +& +a +[ +j +- +1 +] +> +a +[ +j +] +) +{ + +13 +swap +( +& +a +[ +j +- +1 +] +, +& +a +[ +j +] +) +; + +14 +j +- +- +; +15 +} +16 +} +17 +} +18 +19 +int +main +( +void +) +{ +20 +sort +( +8 +) +; +21 +return +0 +; + + + +registers +stack +heap +code +data +rwx + +read-only +rax +5 + +rbx +0 +rcx +0x10 +16 +rdx +0x11 +17 + +rsi +404034 + + +0x1f0000001a +rdi +404030 + + +0x1a00000005 +rbp +7fffffffecf0 + + +7fffffffed00 + + +7fffffffedb0 + + +7fffffffee10 + + +0 +rsp +7fffffffecd8 + + +0x800000000 +r8 +7ffff7e19680 +r9 +7ffff7e1afa0 +r10 +7fffffffea60 + + +0 +r11 +7ffff7ffca90 + + +0x786843bb9f54c5c1 +r12 +7fffffffee38 + + +7fffffffefea + + +"./sort" +r13 +1 +r14 +7ffff7ffd000 + + +7ffff7ffe3c0 + + +0 +r15 +403e10 + + +4010e0 +__do_global_dtors_aux + + +rip +4011db +sort+152 +cf + +PF + +AF +zf +sf + +IF +df +of + + + +stack +six words from rsp · the frames they belong to +rsp + ++0 +7fffffffe +cd8 + + +0x800000000 ++8 +7fffffffe +ce0 + + +0 ++10 +i, j +7fffffffe +ce8 + + +0x400000006 +rbp + ++18 +saved rbp +7fffffffe +cf0 + + +7fffffffed00 + + + + + ++20 +7fffffffe +cf8 + + +4011ff +main+14 ++28 +7fffffffe +d00 + + +7fffffffedb0 + + +7fffffffee10 + + +0 + + + +sort(8) + + +moment 370 of 465 +The sixth pass, its third compare: 17 : 5, so jg goes back to the swap. +The swap has run 5 times so far; the outer loop has turned 5. + diff --git a/design/mock/26-pair-rest-480.png b/design/mock/26-pair-rest-480.png new file mode 100644 index 0000000..be057a5 Binary files /dev/null and b/design/mock/26-pair-rest-480.png differ diff --git a/design/mock/26-pair-rest.png b/design/mock/26-pair-rest.png new file mode 100644 index 0000000..d5eca7f Binary files /dev/null and b/design/mock/26-pair-rest.png differ diff --git a/design/mock/26-pair-rest.svg b/design/mock/26-pair-rest.svg new file mode 100644 index 0000000..c6bbd84 --- /dev/null +++ b/design/mock/26-pair-rest.svg @@ -0,0 +1,417 @@ + + + + + + +overflow.c · both builds +lines 2 to 6 of 10 +2 +__attribute__ +( +( +noinline +) +) +static +void +fill +( +void +) +{ +3 +char +buf +[ +16 +] +; + + +4 +for +( +int +i += +0 +; +i +< +32 +; +i ++ ++ +) +buf +[ +i +] += +' +A +' +; +5 +} +6 + + +asan + + + + +disassembly +plain · fill +4011 +44 +4 +mov +[rbp - 0x14] + + + + +, 0 + +4011 +4b +cmp +[rbp - 0x14] + + + + +, 0x20 + +4011 +4f +jge +401165 + +4011 +51 +movsxd +rax, [rbp - 0x14] + + + + + + + + +4011 +55 +mov +[rbp + rax - 0x10] + +, 0x41 +7fffffffecdf + + +0 +4011 +5a +mov +eax, [rbp - 0x14] +4011 +5d +add +eax, 1 +4011 +60 +mov +[rbp - 0x14], eax +4011 +63 +jmp +40114b + + + +plain · registers +the line's registers, and rip +rax +0xf +15 +rbp +7fffffffece0 + + +7fffffffed00 +rsp +7fffffffece0 + + +rip +401155 +fill+21 + + + +plain · stack +red zone, buf, the frame · rsp at +0 · the frames they belong to +-30 +7fffffffec +b0 + + +0 +-28 +7fffffffec +b8 + + +0 +-20 +7fffffffec +c0 + + +0 +-18 +i, high half +7fffffffec +c8 + + +0xf00000000 +-10 +buf[0..7] +7fffffffec +d0 + + +"AAAAAAAA" +-8 +buf[8..15] +7fffffffec +d8 + + +"AAAAAAA" +rbp rsp + ++0 +saved rbp +7fffffffec +e0 + + +7fffffffed00 ++8 +return +7fffffffec +e8 + + +401134 +main+20 ++10 +7fffffffec +f0 + + +0 ++18 +7fffffffec +f8 + + +0 + + + +fill + + + +disassembly +asan · fill +523d +26 +4 +mov +rax, [rbx + 0x18] +523d +2a +movsxd +rcx, [rbx + 0x64] + + + + + + +523d +2e +add +rax, rcx + +523d +31 +mov +[rbx], rax + +523d +34 +shr +rax, 3 +rax +0xf7ffeb1e005 + + + +523d +38 +mov +al, [rax + 0x7fff8000] +f807eb16005 + + +0 +523d +3e +mov +[rbx + 0xf], al +523d +41 +cmp +al, 0 +523d +43 +je +523d5b + + + + + + + + + + + +asan · registers +the line's registers, and rip +rax +0xf7ffeb1e005 +rbx +7fffffffec20 + + +7bfff58f002f +rcx +0xf +15 + + +rip +523d38 +fill+216 + + + +asan · fake stack +the fake frame, its shadow · the real stack's way back · the frames they belong to +magic +7 +bfff58f0000 + + +0x41b58ab3 +descr +7 +bfff58f0008 + + +5387a7 + + +"1 32 16 5 buf:3" +pc +7 +bfff58f0010 + + +523c60 +fill +real stack +7 +bfff58f0018 + + +7fffffffec10 +buf[0..7] +7 +bfff58f0020 + + +"AAAAAAAA" +buf[8..15] +7 +bfff58f0028 + + +"AAAAAAA" +redzone +7 +bfff58f0030 + + +0 +redzone +7 +bfff58f0038 + + +7bfff58e8000 +rbp + +saved rbp +7 +fffffffecc0 + + +7fffffffece0 +return +7 +fffffffecc8 + + +523c54 +main+20 + + + +fill + +f1 + +f1 + +f1 + +f1 +00 +00 + +f3 + +f3 + + + + + + + +i 15 · moments 156 / 753 +The same line, two builds: plain stores the byte; ASan first +reads the byte of shadow that stands for it: 00, so it may. + diff --git a/design/mock/27-pair-store-480.png b/design/mock/27-pair-store-480.png new file mode 100644 index 0000000..6fb2409 Binary files /dev/null and b/design/mock/27-pair-store-480.png differ diff --git a/design/mock/27-pair-store.png b/design/mock/27-pair-store.png new file mode 100644 index 0000000..2563ead Binary files /dev/null and b/design/mock/27-pair-store.png differ diff --git a/design/mock/27-pair-store.svg b/design/mock/27-pair-store.svg new file mode 100644 index 0000000..637f851 --- /dev/null +++ b/design/mock/27-pair-store.svg @@ -0,0 +1,218 @@ + + + + + + +disassembly +asan · line 4, one turn · 17 instructions +523d +1e +4 +cmp +[rbx + 0x64] + + + + +, 0x20 +523d +22 +jl +523d26 +523d +24 +jmp +523d6c +523d +26 +mov +rax, [rbx + 0x18] +7bfff58f0020 +523d +2a +movsxd +rcx, [rbx + 0x64] + + + + + +523d +2e +add +rax, rcx +rax +7bfff58f0023 + + +"AAA" +523d +31 +mov +[rbx], rax +523d +34 +shr +rax, 3 +rax +0xf7ffeb1e004 +523d +38 +mov +al, [rax + 0x7fff8000] +f807eb16004 + + +0 +523d +3e +mov +[rbx + 0xf], al +523d +41 +cmp +al, 0 +0 + : +0 + + +ZF +523d +43 +je +523d5b +taken + · reads ZF +523d45 +mov +cl, [rbx + 0xf] +523d48 +mov +rax, [rbx] +523d4b +and +rax, 7 +523d4f +cmp +al, cl +523d51 +jl +523d5b +523d53 +mov +rdi, [rbx] +523d56 +call +4e8450 +__asan_report_store1 +523d +5b +mov +rax, [rbx] +523d +5e +mov +[rax] + +, 0x41 +7bfff58f0023 + + +0x41 +65 +523d +61 +mov +eax, [rbx + 0x64] +523d +64 +add +eax, 1 +523d +67 +mov +[rbx + 0x64], eax +523d +6a +jmp +523d1e + + + + + + + + + + + + + + + + + + + + +plain · line 4, one turn · 8 instructions +each row facing its counterpart +4011 +4b +4 +cmp +[rbp - 0x14] + + + + +, 0x20 +4011 +4f +jge +401165 +4011 +51 +movsxd +rax, [rbp - 0x14] + + + + + +rax +3 +4011 +55 +mov +[rbp + rax - 0x10] + +, 0x41 +7fffffffecd3 + + +0x41 +65 +4011 +5a +mov +eax, [rbp - 0x14] +4011 +5d +add +eax, 1 +4011 +60 +mov +[rbp - 0x14], eax +4011 +63 +jmp +40114b +the check: plain has nothing here +Plain: one store. ASan: the address, its shadow byte (addr >> 3 + 7fff8000), +a compare with 0, a branch; the partial check and the report only if it is not 0. + diff --git a/design/mock/28-pair-part-480.png b/design/mock/28-pair-part-480.png new file mode 100644 index 0000000..adaeb20 Binary files /dev/null and b/design/mock/28-pair-part-480.png differ diff --git a/design/mock/28-pair-part.png b/design/mock/28-pair-part.png new file mode 100644 index 0000000..8651eb6 Binary files /dev/null and b/design/mock/28-pair-part.png differ diff --git a/design/mock/28-pair-part.svg b/design/mock/28-pair-part.svg new file mode 100644 index 0000000..e5cd106 --- /dev/null +++ b/design/mock/28-pair-part.svg @@ -0,0 +1,428 @@ + + + + + + +overflow.c · both builds +lines 2 to 6 of 10 +2 +__attribute__ +( +( +noinline +) +) +static +void +fill +( +void +) +{ +3 +char +buf +[ +16 +] +; + + +4 +for +( +int +i += +0 +; +i +< +32 +; +i ++ ++ +) +buf +[ +i +] += +' +A +' +; +5 +} +6 + + +asan + + + + +disassembly +plain · fill +4011 +44 +4 +mov +[rbp - 0x14] + + + + +, 0 + +4011 +4b +cmp +[rbp - 0x14] + + + + +, 0x20 + +4011 +4f +jge +401165 + +4011 +51 +movsxd +rax, [rbp - 0x14] + + + + + + + + +4011 +55 +mov +[rbp + rax - 0x10] + +, 0x41 +7fffffffece0 + + +0x41 +65 +4011 +5a +mov +eax, [rbp - 0x14] +4011 +5d +add +eax, 1 +4011 +60 +mov +[rbp - 0x14], eax +4011 +63 +jmp +40114b + + + +plain · registers +the line's registers, and rip +rax +0x10 +16 +rbp +7fffffffece0 + + +7fffffffed41 +rsp +7fffffffece0 + + +rip +401155 +fill+21 + + + +plain · stack +red zone, buf, the frame · rsp at +0 · the frames they belong to +-30 +7fffffffec +b0 + + +0 +-28 +7fffffffec +b8 + + +0 +-20 +7fffffffec +c0 + + +0 +-18 +i, high half +7fffffffec +c8 + + +0x1000000000 +-10 +buf[0..7] +7fffffffec +d0 + + +"AAAAAAAA" +-8 +buf[8..15] +7fffffffec +d8 + + +"AAAAAAAA" +rbp rsp + ++0 +saved rbp +7fffffffec +e0 + + + +7fffffffed41 ++8 +return +7fffffffec +e8 + + +401134 +main+20 ++10 +7fffffffec +f0 + + +0 ++18 +7fffffffec +f8 + + +0 + + + +fill + + + +disassembly +asan · fill +523d +26 +4 +mov +rax, [rbx + 0x18] +523d +2a +movsxd +rcx, [rbx + 0x64] + + + + + + +523d +2e +add +rax, rcx + +523d +31 +mov +[rbx], rax + +523d +34 +shr +rax, 3 +rax +0xf7ffeb1e006 + + + +523d +38 +mov +al, [rax + 0x7fff8000] + +f807eb16006 + + +0xf3 +243 +523d +3e +mov +[rbx + 0xf], al +523d +41 +cmp +al, 0 +f3 + : +0 + +zf +523d +43 +je +523d5b +not taken + + + + + + + + + + + +asan · registers +the line's registers, and rip +rax +0xf7ffeb1e006 +rbx +7fffffffec20 + + +7bfff58f0030 +rcx +0x10 +16 + + +rip +523d38 +fill+216 + + + +asan · fake stack +the fake frame, its shadow · the real stack's way back · the frames they belong to +magic +7 +bfff58f0000 + + +0x41b58ab3 +descr +7 +bfff58f0008 + + +5387a7 + + +"1 32 16 5 buf:3" +pc +7 +bfff58f0010 + + +523c60 +fill +real stack +7 +bfff58f0018 + + +7fffffffec10 +buf[0..7] +7 +bfff58f0020 + + +"AAAAAAAA" +buf[8..15] +7 +bfff58f0028 + + +"AAAAAAAA" +redzone +7 +bfff58f0030 + + +0 +redzone +7 +bfff58f0038 + + +7bfff58e8000 +rbp + +saved rbp +7 +fffffffecc0 + + +7fffffffece0 +return +7 +fffffffecc8 + + +523c54 +main+20 + + + +fill + +f1 + +f1 + +f1 + +f1 +00 +00 + +f3 + + +f3 + + + + + + + +i 16 · moments 164 / 770 +i = 16, one past buf: plain writes 'A' into the saved rbp. ASan reads +the shadow first: f3, a redzone. Its branch to the store is not taken. + diff --git a/design/mock/context.py b/design/mock/context.py index a040109..d58683c 100644 --- a/design/mock/context.py +++ b/design/mock/context.py @@ -332,14 +332,15 @@ def registers(g, y, regs, flags, marks): return where -def stack(g, y, rows, frames, note=None, rsp=None, roles=None, touched=(), chain_too=False): +def stack(g, y, rows, frames, note=None, rsp=None, roles=None, touched=(), chain_too=False, title="stack", + ink_of=None): """rows: (slot, pins, links, end[, marks]). frames: (name, first row, last row), newest first: the backtrace, drawn on the words that are each frame; a first row under 0 runs above the window. The window is the newest frame's. A frame's name is never cut for a chain: the chains on the rows it sits on end 12 before it. rsp: the slots' offsets from it are drawn (pwndbg's column). roles: {row: (what the slot is, ink)}: a local's name, `saved rbp`, `return`, ranged right where the chain's room ends; the chain ends 12 before it. Returns each row's y.""" - y0 = panel(g, RX, y, CW, len(rows), "stack", note=(note or "%s words from rsp" % {6: "six", 8: "eight"}[len(rows)]) + y0 = panel(g, RX, y, CW, len(rows), title, note=(note or "%s words from rsp" % {6: "six", 8: "eight"}[len(rows)]) + " · the frames they belong to") lead = shared([r[0] for r in rows]) room = {} # a row's chain ends here, where a frame's name begins @@ -376,7 +377,8 @@ def stack(g, y, rows, frames, note=None, rsp=None, roles=None, touched=(), chain text, ink = roles[i] g.t(end_x, b(yy), text, S, ink, MONO, "end") end_x -= len(text) * A + 12 - chain(g, first, yy, [(slot, STACK)] + links, end, marks[0] if marks else None, room=end_x, lead=lead) + chain(g, first, yy, [(slot, ink_of(slot) if ink_of else STACK)] + links, end, marks[0] if marks else None, + room=end_x, lead=lead) # the arcs: a word holding the address of a slot in the window. The frame chain (a saved rbp) is the spans' # already, and is drawn only when the step touches it. slots = {r[0]: ys[i] for i, r in enumerate(rows)} @@ -538,8 +540,8 @@ def insn_rows(g, y0, rows, cur_line, w=0, lead=None, sizes=False): for i, (a, line, mn, ops, st, note) in enumerate(rows): yy = y0 + i * ROW where[a] = yy - dim = st == "out" - if dim or st == "other_first": # a function ends: a rule, and the next one's name + dim = st in ("out", "skip") # skip: on the page, not on the path this run takes + if st in ("out", "other_first"): # a function ends: a rule, and the next one's name g.rect(LX + 2, yy, CW - 4, 2, RULE) if st == "cur": g.path(f"M{LX + 20},{yy + 12} l-10,-6 v12 Z", fill=current_row(g, LX + 2, yy, CW - 4, 24)) diff --git a/design/mock/graph.py b/design/mock/graph.py new file mode 100644 index 0000000..e9b8f2b --- /dev/null +++ b/design/mock/graph.py @@ -0,0 +1,583 @@ +#!/usr/bin/env python3 +"""The disassembly's other form: a function as a graph of its basic blocks, with what the run did on it. + + python3 -B graph.py # 22-graph-sort, 23-graph-open, 24-graph-strip, 25-blocks-lens (.svg) + +Data: sort and reverse from anim/tools/sort.c and list.c (cc -O0 -g -no-pie), their disassembly in +sort-O0.dis and reverse-O0.dis (objdump -dl), the paths their runs took from `ztrace dbg` stepped by instruction; +libc's `open` from objdump of /usr/lib/libc.so.6 (libc-open.dis), its path the one mock 16's run took. +""" +import re +from collections import Counter + +import gen +import dense as D +import context as C +from context import (PAGE, RAISED, RULE, VELLUM, BRIGHT, DIM, FAINT, GOLD, KW, CODE, HEAP, STACK, DATA, A, S, ROW, TAG, + PAD, MONO, BOLD, b, ph, mix, Svg) + +HERE = __file__.rsplit("/", 1)[0] +NORETURN = {"__stack_chk_fail", "__syscall_do_cancel"} +TRAIL = gen.TRAIL + + +def read_dis(name, lines=True): + """(address, line, mnemonic, operands, target) from objdump -d[l] -M intel.""" + out, line = [], None + for l in open(f"{HERE}/{name}"): + m = re.search(r"\.c:(\d+)", l) + if m and not re.match(r"^\s+[0-9a-f]+:", l): + line = int(m.group(1)) + continue + m = re.match(r"^\s+([0-9a-f]+):\s+(\S+)\s*(.*)$", l) + if not m: + continue + mnem, ops = m.group(2), m.group(3) + if mnem in ("addr32", "bnd", "notrack") and ops: # a prefix: the instruction is what follows it + mnem, _, ops = ops.partition(" ") + ops = ops.strip() + tgt = re.match(r"([0-9a-f]+) <([^>]+)>", ops) + callee = tgt.group(2) if tgt else None + ops = re.sub(r"\s*<[^>]+>", "", re.sub(r"\s+#.*", "", ops)).strip() + mn, ops = D.conv(mnem, ops) + out.append((int(m.group(1), 16), line if lines else None, mn, ops, int(tgt.group(1), 16) if tgt else None, callee)) + return out + + +class Block: + def __init__(self, name, rows): + self.name, self.rows = name, rows + self.a = rows[0][0] + self.out = [] # (target name, kind): taken, fall, jmp + self.ret = rows[-1][2] == "ret" + + +def blocks(insns, base): + """Basic blocks: a leader at the entry, at every jump's target and after every jump, ret or call that does not + return. Padding (nops after a jump) is left out. Names are offsets: +5f.""" + lo, hi = insns[0][0], insns[-1][0] + lead = {lo} + for i, (a, ln, mn, ops, t, callee) in enumerate(insns): + ends = mn.startswith("j") or mn == "ret" or (mn == "call" and callee in NORETURN) + if ends and i + 1 < len(insns): + lead.add(insns[i + 1][0]) + if mn.startswith("j") and t and lo <= t <= hi: + lead.add(t) + out, cur = {}, [] + for r in insns: + if r[0] in lead and cur: + out[cur[0][0]] = cur + cur = [] + cur.append(r) + out[cur[0][0]] = cur + bl = {} + for a, rows in out.items(): + if all(r[2] in ("nop", "xchg") for r in rows): + continue # padding between functions' paths: not a block + bl[a] = Block("+%x" % (a - base), rows) + order = sorted(bl) + for i, a in enumerate(order): + last = bl[a].rows[-1] + nxt = bl[a].rows[-1][0] + 1 + nxt = next((x for x in order if x > a), None) + mn, t, callee = last[2], last[4], last[5] + if mn == "jmp": + bl[a].out = [(t, "jmp")] + elif mn.startswith("j"): + bl[a].out = [(t, "taken"), (nxt, "fall")] + elif mn == "ret" or (mn == "call" and callee in NORETURN): + bl[a].out = [] + else: + bl[a].out = [(nxt, "fall")] + bl[a].out = [(x, k) for x, k in bl[a].out if x in bl] + return bl + + +def layers(bl, entry): + """Back edges by a depth-first walk from the entry; layers by the longest path over the rest; a block that + returns in the last layer.""" + back, state = set(), {} + + def walk(a): + state[a] = 1 + for t, k in bl[a].out: + if state.get(t) == 1: + back.add((a, t)) + elif t not in state: + walk(t) + state[a] = 2 + walk(entry) + lay = {a: 0 for a in bl} + for _ in bl: + for a in bl: + for t, k in bl[a].out: + if (a, t) not in back: + lay[t] = max(lay[t], lay[a] + 1) + last = max(lay.values()) + for a in bl: + if bl[a].ret: + lay[a] = last + (0 if all(lay[x] < last or bl[x].ret for x in bl) else 1) + return lay, back + + +# ---- a block, at the map's size: a head and insn rows -------------------------------------------------------- +X_OFF, X_LINE, X_MN, X_OPS = 72, 116, 128, 212 + + +def block_w(blk, base, note_w=0): + return max(300, X_OPS + max(len(r[3]) for r in blk.rows) * A + 24 + note_w) + + +def fold_rows(rows, keep): + """A block longer than 16 rows: its first four and last four, the middle one `more` row.""" + if len(rows) <= 16 or keep: + return rows + return rows[:4] + [None] + rows[-4:] + + +def draw_block(g, x, y, w, blk, base, st): + """st: count (visits), cur (the pc's address in it), trail (ran rows), notes {address: note}, cur_line.""" + if hasattr(blk, "folded"): # blocks the whole recording never reached: one dashed box, no rows + h = TAG + ROW + PAD + g.rect(x, y, w, h, PAGE) + g.frame(x, y, w, h, RULE, 2, "12 8") + g.t(x + 12, b(y), "+%x to +%x" % (blk.rows[0][0] - base, blk.rows[-1][0] - base), S, FAINT, MONO) + g.t(x + w - 12, b(y), "%d blocks never reached" % len(blk.folded) if len(blk.folded) > 1 else "never reached", + 18, FAINT, "sans", "end") + g.t(x + 12, b(y + TAG), blk.name, 18, DIM, "sans") + return h, {} + rows = fold_rows(blk.rows, st.get("cur")) + h = TAG + len(rows) * ROW + PAD + reached = st.get("count", 0) > 0 + g.rect(x, y, w, h, PAGE) + g.rect(x, y, w, TAG, RAISED if reached else PAGE) + g.frame(x, y, w, h, GOLD if st.get("cur") else RULE, 2) # not reached yet: plain, no count + ink = CODE + C.addr(g, x + 12, y, blk.a, ink) + lines = sorted({r[1] for r in blk.rows if r[1]}) + if lines: + g.t(x + 12 + len("%x" % blk.a) * A + 16, b(y), "line %d" % lines[0] if len(lines) == 1 else + "lines %d to %d" % (lines[0], lines[-1]), 18, FAINT, "sans") + if reached: + g.t(x + w - 12, b(y), "×%d" % st["count"], S, VELLUM, MONO, "end") + yy, last_line, at = y + TAG, None, {} + for r in rows: + if r is None: + C.more(g, x + X_OFF - 36, yy) + g.t(x + X_MN, b(yy), "%d rows" % (len(blk.rows) - 8), S, FAINT, MONO) + yy += ROW + continue + a, ln, mn, ops, t, callee = r + at[a] = yy + dim_ = False + if a == st.get("cur"): + g.path(f"M{x + 20},{yy + 12} l-10,-6 v12 Z", fill=C.current_row(g, x + 2, yy, w - 4, 24)) + elif a in st.get("trail", []): + g.rect(x + 2, yy + 1, 4, ROW - 2, TRAIL[st["trail"].index(a)]) + g.t(x + X_OFF, b(yy), "+%x" % (a - base), S, FAINT if not dim_ else mix(FAINT, PAGE, 0.4), MONO, "end") + if ln and ln != last_line: + on = ln == st.get("cur_line") and st.get("cur") + g.t(x + X_LINE, b(yy), str(ln), S, GOLD if on else FAINT, BOLD if on else MONO, "end") + last_line = ln + fade = (lambda c: mix(c, PAGE, 0.55)) if dim_ else (lambda c: c) + g.t(x + X_MN, b(yy), mn, S, fade(FAINT if mn in ("nop", "endbr64") else KW), + MONO if mn in ("nop", "endbr64") else BOLD) + if t and (mn.startswith("j") or mn == "call"): + ex = C.addr(g, x + X_OPS, yy, t, fade(CODE)) + else: + ex = C.operands(g, x + X_OPS, yy, mn, ops, fade(VELLUM)) + note = st.get("notes", {}).get(a) + if note: + nx = max(ex + 2 * A, x + X_OPS + 20 * A) + for s_, ink_ in note: + if ink_ == "chip": + g.rect(nx, yy + 2, 32, 20, RAISED) + g.t(nx + 16, b(yy), s_, S, BRIGHT, BOLD, "middle") + nx += 38 + else: + g.t(nx, b(yy), s_, S, ink_, MONO) + nx += len(s_) * A + if mn == "call" and callee: # a call that comes back: out of the block's side and in again a row down + hx = x + w + g.path(f"M{hx},{yy + 12} h14 q6,0 6,6 v12 q0,6 -6,6 h-8", fade(DIM) if reached else RULE, 2) + g.path(f"M{hx},{yy + 36} l8,-4 v8 Z", fill=fade(DIM) if reached else RULE) + g.t(hx + 28, b(yy) + 12, callee, S, fade(VELLUM), MONO) + yy += ROW + if blk.ret: # the way out: a stub and a bar under the block + cx = x + w / 2 + g.rect(cx - 1, y + h, 2, 14, DIM if reached else RULE) + g.rect(cx - 14, y + h + 14, 28, 3, DIM if reached else RULE) + return h, at + + +# ---- the graph: placement and edges ----------------------------------------------------------------------- +def arrow(g, pts, *a, **k): + """gen.arrow, its repeated and straight-through points dropped.""" + q = [] + for p in pts: + if q and abs(p[0] - q[-1][0]) < 0.5 and abs(p[1] - q[-1][1]) < 0.5: + continue + if len(q) >= 2 and (abs(q[-2][0] - q[-1][0]) < 0.5 and abs(q[-1][0] - p[0]) < 0.5 or + abs(q[-2][1] - q[-1][1]) < 0.5 and abs(q[-1][1] - p[1]) < 0.5): + q[-1] = p + continue + q.append(p) + gen.arrow(g, q, *a, **k) + +def place(bl, lay, cols, widths, heights, x0, y0, pitch, gap): + """Each block at its column (a scene's layout, by the rule in the catalogue) and its layer.""" + nl = max(lay.values()) + 1 + lh = [max([heights[a] for a in bl if lay[a] == k] or [0]) for k in range(nl)] + ly = [y0] + for k in range(1, nl): + ly.append(ly[-1] + lh[k - 1] + gap) + pos = {a: (x0 + cols[a] * pitch, ly[lay[a]]) for a in bl} + return pos, lh, ly + + +def edges(g, bl, lay, back, pos, widths, heights, lh, ly, gap, st, base, lane_x0, channel_x, small=False): + """Every edge: forward ones down from the bottom by the side their target lies on, along the gap's middle, down + into the target's top; one that would cross a block runs in the right channel; a back edge leaves the bottom, + goes out to its loop's lane on the left, climbs it and enters its header's head from the side: the one thing + that climbs. Ink: never taken `rule`; taken in the run `dim`; the last three taken the trail's golds.""" + sw0 = 2 + trail = st.get("edge_trail", []) + counts = st.get("edge_counts", {}) + backs = sorted([(a, t) for a, t in back], key=lambda e: -(lay[e[0]] - lay[e[1]])) + lane = {e: lane_x0 + i * (10 if small else 16) for i, e in enumerate(backs)} + inc = {} + for a in bl: + for t, k in bl[a].out: + if (a, t) not in back: + inc.setdefault(t, []).append(a) + track = {} + for a in sorted(bl, key=lambda a: (lay[a], pos[a][0])): + x, y = pos[a] + w, h = widths[a], heights[a] + outs = bl[a].out + for t, kind in outs: + e = (a, t) + n = counts.get(e, 0) + ink = TRAIL[trail.index(e)] if e in trail else DIM if n else RULE + sw = 3 if trail and e == trail[0] else sw0 + tx, ty = pos[t] + tw_ = widths[t] + if e in back: + lx = lane[e] + k = track.get(lay[a], 0) + track[lay[a]] = k + 1 + by = ly[lay[a]] + lh[lay[a]] + (8 if small else 14) + k * 8 + sx = x + (16 if small else 40) + hy = ty + (12 if not small else 12) + pts = [(sx, y + h), (sx, by), (lx, by), (lx, hy), (tx - 1, hy)] + st.setdefault("paths", {})[e] = pts + arrow(g, pts, ink, sw, r=4 if small else 8, hl=7 if small else 10, hw=8 if small else 10) + if n: # the loop's turns, on the lane under its turn into the header + if st.get("struck_count") == e: # the count is a value: written, it is struck + g.rect(lx + 1, hy + 8, 10 + len(str(n)) * 11, 20, C.SOFT) + g.t(lx + 5, hy + 22, "×%d" % n, 18, BRIGHT, "sansb") + else: + g.t(lx + 5, hy + 22, "×%d" % n, 18, FAINT, "sans") + continue + # the side the target lies on picks the port + srcs = sorted(inc.get(t, []), key=lambda s_: pos[s_][0]) + slot = srcs.index(a) + tx_ = tx + tw_ / 2 + (slot - (len(srcs) - 1) / 2) * (16 if small else 48) + crosses = any(lay[a] < lay[o] < lay[t] and pos[o][0] - 8 < tx_ < pos[o][0] + widths[o] + 8 for o in bl) + side = 1 if crosses else (tx + tw_ / 2) - (x + w / 2) # the channel is on the right + sx = x + w / 2 if abs(side) < w / 2 - 40 and not crosses else ( + x + w - (16 if small else 40) if side > 0 else x + (16 if small else 40)) + gy = ly[lay[a]] + lh[lay[a]] + gap / 2 + track.get(("f", lay[a]), 0) * 6 + track[("f", lay[a])] = track.get(("f", lay[a]), 0) + 1 + between = [o for o in bl if lay[a] < lay[o] < lay[t] and pos[o][0] - 8 < tx_ < pos[o][0] + widths[o] + 8] + if between: # it would cross a block: the right channel + gy2 = ly[lay[t]] - gap / 2 + pts = [(sx, y + h), (sx, gy), (channel_x, gy), (channel_x, gy2), (tx_, gy2), (tx_, ty)] + else: + pts = [(sx, y + h), (sx, gy), (tx_, gy), (tx_, ty)] + st.setdefault("paths", {})[e] = pts + arrow(g, pts, ink, sw, r=4 if small else 8, hl=7 if small else 10, hw=8 if small else 10) + if n and kind != "jmp" and not small and len(outs) > 1: + g.t(sx + 8, y + h + 20, str(n), S, FAINT, MONO) + + +def graph(g, x, y, w, title, note, bl, entry, base, cols, st, pitch=None, gap=48, notes_w=0): + """The panel: its tag, the blocks at the map's size, the edges. Returns the blocks' row positions.""" + lay, back = layers(bl, entry) + widths = {a: 520 if hasattr(bl[a], "folded") else block_w(bl[a], base, notes_w if st["blocks"].get(a, {}).get("notes") + else 0) for a in bl} + heights = {a: TAG + (ROW if hasattr(bl[a], "folded") else + len(fold_rows(bl[a].rows, st["blocks"].get(a, {}).get("cur"))) * ROW) + PAD for a in bl} + nb = len([e for e in back]) + lane_x0 = x + 24 + x0 = x + 24 + nb * 16 + 24 + pitch = pitch or max(widths.values()) + 56 + pos, lh, ly = place(bl, lay, cols, widths, heights, x0, y + TAG + 36, pitch, gap) + channel_x = max(pos[a][0] + widths[a] for a in bl) + 32 + hgt = max(pos[a][1] + heights[a] for a in bl) - y + 48 + C.tag(g, x, y, w, hgt, title, focus=True, note=note) + edges(g, bl, lay, back, pos, widths, heights, lh, ly, gap, st, base, lane_x0, channel_x) + ats = {} + for a in bl: + s_ = st["blocks"].get(a, {}) + _, at = draw_block(g, pos[a][0], pos[a][1], widths[a], bl[a], base, s_) + ats.update(at) + return pos, ats, hgt + + +def run_state(bl, path, upto, base): + """Visits and edge counts over the path's first `upto` blocks; the last three edges taken.""" + p = path[:upto] + cnt = Counter(p) + ec = Counter(zip(p, p[1:])) + trail = list(reversed(list(zip(p, p[1:]))[-3:])) + return cnt, ec, trail + + +# ---- the data --------------------------------------------------------------------------------------------- +SORT = read_dis("sort-O0.dis") +SORT_BASE = 0x401143 +SORT_BL = blocks(SORT, SORT_BASE) +SB = sorted(SORT_BL) # B0 .. B7 by address +NAMES = dict(zip("B0 B1 B2 B3 B4 B5 B6 B7".split(), SB)) +SORT_PATH = [NAMES[n] for n in ("B0 B6 B1 B3 B4 B5 B6 B1 B3 B4 B5 B6 B1 B3 B4 B5 B6 B1 B3 B4 B2 B3 B4 B2 B3 B4 B5 B6 B1 " + "B3 B4 B2 B3 B4 B5 B6 B1 B3 B4 B2 B3 B4 B2 B3 B4 B2 B3 B4 B2 B3 B4 B2 B3 B4 B5 B6 B1 " + "B3 B4 B2 B3 B4 B2 B3 B4 B5 B6 B7").split()] +SORT_COLS = {NAMES["B0"]: 0, NAMES["B6"]: 0, NAMES["B1"]: 0, NAMES["B3"]: 0, NAMES["B4"]: 0, NAMES["B2"]: 0, + NAMES["B5"]: 1, NAMES["B7"]: 1} + + +def sort_state(upto, cur, trail_rows, notes=None, cur_line=12): + cnt, ec, trail = run_state(SORT_BL, SORT_PATH, upto, SORT_BASE) + blk = {a: {"count": cnt.get(a, 0)} for a in SORT_BL} + ca = max(a for a in SORT_BL if a <= cur) + blk[ca].update(cur=cur, trail=trail_rows, notes=notes or {}, cur_line=cur_line) + return {"blocks": blk, "edge_counts": ec, "edge_trail": trail} + + +# the 11th time through the compare: i = 6, j = 4, a[3] = 17 against a[4] = 5 (moment 370 of the stepped run) +UPTO = [i for i, a in enumerate(SORT_PATH) if a == NAMES["B4"]][10] + 1 +NOTES_370 = {0x4011bf: [("404030 ", HEAP), ("◂ ", FAINT), ("17", VELLUM)], + 0x4011d6: [("404034 ", HEAP), ("◂ ", FAINT), ("5", VELLUM)], + 0x4011d9: [("17", VELLUM), (" : ", FAINT), ("5", VELLUM), (" ", FAINT), ("zf", DIM), (" sf", DIM), (" of", DIM)], + 0x4011db: [("taken", VELLUM), (" · reads zf sf of", FAINT)]} + + +def frame_sort_map(name): + """Mock 22: on the map, the disassembly column as sort's graph, two columns wide, beside the source whole.""" + gen.W, gen.H = 2900, 1800 + g = Svg() + D.put(112) + src = open(HERE + "/../../anim/tools/sort.c").read().split("\n") + C.LX = 112 + C.source(g, 96, 22, src, 1, 12, [13, 14], "sort.c", 22) + C.LX = 64 + g.t(112, 60, "the map: sort's disassembly as its graph, two columns wide (1024 to 2816), at moment 370 of 465 in sort", + 22, DIM, "sans") + st = sort_state(UPTO, 0x4011db, [0x4011d9, 0x4011d6, 0x4011cf], NOTES_370) + graph(g, 1024, 96, 1792, "disassembly · sort", "its blocks · visits so far · the edges the run took", + SORT_BL, SB[0], SORT_BASE, SORT_COLS, st, pitch=560, notes_w=30 * A) + g.save(name) + + +# ---- libc's open: unreached blocks folded ----------------------------------------------------------------- +OPEN = read_dis("libc-open.dis", lines=False) +OPEN_BASE = 0x110ec0 +L = 0x7ffff7c00000 + + +def rebase(rows): + return [(a + L, ln, mn, ops, (t + L) if t else None, callee) for a, ln, mn, ops, t, callee in rows] + + +OPEN_BL = blocks(rebase(OPEN), OPEN_BASE + L) +OPEN_PATH = [a + L for a in (0x110ec0, 0x110ee9, 0x110efb, 0x110fb0, 0x110fca, 0x110fd2, 0x110fd4, 0x110fe3)] + + +def fold_unreached(bl, path, groups): + """Blocks the run never reached, a connected run of them one box: `5 blocks not reached`.""" + out = {a: bl[a] for a in bl if a in path} + for name, members in groups: + rows = [r for m in members for r in bl[m].rows] + fb = Block(name, rows) + fb.folded = members + out[members[0]] = fb + rep = {m: ms[0] for _, ms in groups for m in ms} + for a, blk in list(out.items()): + seen = [] + for t, k in (blk.out if not hasattr(blk, "folded") else [o for m in blk.folded for o in bl[m].out]): + t2 = rep.get(t, t) + if t2 != a and t2 in out and (t2, k) not in seen and t2 not in [s_ for s_, _ in seen]: + seen.append((t2, k)) + blk.out = seen + blk.ret = blk.ret if not hasattr(blk, "folded") else False + return out + + +def frame_open_map(name): + """Mock 23: libc's open, 19 blocks, of which the run reached 8; the 11 it did not are folded into three boxes. + The pc is at the `syscall` (mock 16's moment 4).""" + gen.W, gen.H = 2000, 2000 + g = Svg() + o = lambda x: x + L + groups = [("the O_CREAT path: the mode from the varargs", [o(0x110f90)]), + ("multi-threaded: a cancellable call", [o(0x110f1b), o(0x110f23), o(0x110f2b), o(0x110f6d)]), + ("an error: errno set, -1 returned", [o(0x110fe8), o(0x110f79), o(0x110f7e)]), + ("cancelled", [o(0x110ff6), o(0x111009)]), + ("the canary broken", [o(0x110fec), o(0x110ff0)])] + groups = [(n, [m for m in ms if m in OPEN_BL]) for n, ms in groups] + bl = fold_unreached(OPEN_BL, OPEN_PATH, groups) + cols = {a: 0 for a in bl} + for n, ms in groups: + cols[ms[0]] = 1 + st = {"blocks": {a: {"count": 1} for a in OPEN_PATH}, "edge_counts": Counter(zip(OPEN_PATH, OPEN_PATH[1:])), + "edge_trail": list(reversed(list(zip(OPEN_PATH, OPEN_PATH[1:]))[1:4]))} + st["blocks"][o(0x110fb0)].update(cur=o(0x110fc5), trail=[o(0x110fc0), o(0x110fb9), o(0x110fb6)], + notes={o(0x110fc5): [("openat", BRIGHT), (" nr 257", FAINT)]}) + st["edge_counts"] = Counter(zip(OPEN_PATH[:4], OPEN_PATH[1:4])) + st["edge_trail"] = list(reversed(list(zip(OPEN_PATH[:4], OPEN_PATH[1:4])))) + for a in OPEN_PATH[4:]: + st["blocks"][a]["count"] = 0 # not yet: the run is at the syscall + for _, ms in groups: + st["blocks"][ms[0]] = {"count": 0} + g.t(64, 60, "the map: libc's open as its graph · 19 blocks, the run reached 8 so far; the 11 it never reached are " + "folded into five boxes", 22, DIM, "sans") + graph(g, 64, 96, 1872, "disassembly · open · libc.so.6", "no source · 19 blocks · folded: 11 never reached", + bl, OPEN_PATH[0], OPEN_BASE + L, cols, st, pitch=880, gap=40, notes_w=18 * A) + g.save(name) + + +# ---- reverse: a loop's turn, as a strip ------------------------------------------------------------------- +REV = read_dis("reverse-O0.dis") +REV_BASE = 0x401188 +REV_BL = blocks(REV, REV_BASE) +RB = sorted(REV_BL) +R0, R1, R2, R3 = RB +REV_PATH = [R0, R2, R1, R2, R1, R2, R1, R2, R3] + + +def frame_strip(name): + """Mock 24: reverse's loop, four instants: the condition about to be decided; its edge taken, the mark + travelling it; the back edge's turn, the count going up; the way out.""" + gen.W, gen.H = 3840, 1120 + g = Svg() + cols = {R0: 0, R1: 0, R2: 0, R3: 0} + inst = [ + ("1", "the condition", "cur at jne, the compare's chips framed; the second turn", 4, 0x4011ce, + {0x4011c9: [("1004070", HEAP), (" : ", FAINT), ("0", VELLUM), (" ", FAINT), ("zf", DIM)], + 0x4011ce: [("taken", VELLUM), (" · reads zf", FAINT)]}, None), + ("2", "the edge taken", "the edge lit gold, the mark on it, halfway", 5, None, {}, (R2, R1)), + ("3", "the loop's turn", "the back edge climbs, the mark on it; its count struck: the second turn", 6, None, {}, (R1, R2)), + ("4", "the way out", "not taken: down to the exit, landed", 9, 0x4011d0, {}, None), + ] + for k, (num, title, sub, upto, cur, notes, moving) in enumerate(inst): + dx = 64 + k * 940 + g.o.append(f'') + g.t(64, 40, num, 28, GOLD, "sansb") + g.t(92, 40, title, 28, VELLUM, "sansm") + g.t(64, 70, sub, 20, FAINT, "sans") + cnt, ec, trail = run_state(REV_BL, REV_PATH, upto, REV_BASE) + st = {"blocks": {a: {"count": cnt.get(a, 0)} for a in REV_BL}, "edge_counts": ec, "edge_trail": trail} + if cur: + ca = max(a for a in REV_BL if a <= cur) + st["blocks"][ca].update(cur=cur, notes=notes, cur_line=20 if ca == R2 else 21 if ca == R1 else 26) + if moving == (R1, R2): + st["struck_count"] = moving + pos, ats, hgt = graph(g, 64, 96, 900, "disassembly · reverse", "", REV_BL, R0, REV_BASE, cols, st, pitch=470, + gap=48, notes_w=18 * A) + if moving: # the mark between blocks: the gold plaque halfway along the edge it takes + pts = st["paths"][moving] + seg = [(p, q, abs(q[0] - p[0]) + abs(q[1] - p[1])) for p, q in zip(pts, pts[1:])] + half, run = sum(l for _, _, l in seg) / 2, 0 + for p, q, l in seg: + if run + l >= half: + f = (half - run) / l + mx, my = p[0] + (q[0] - p[0]) * f, p[1] + (q[1] - p[1]) * f + break + run += l + g.rect(mx - 12, my - 12, 24, 24, GOLD) + up = q[1] < p[1] + g.path(f"M{mx},{my + (-6 if up else 6)} l-6,{8 if up else -8} h12 Z", fill=gen.INK) + g.o.append("") + g.save(name) + + +# ---- the working frame: a `blocks` lens, the graph as shapes, its view the disassembly ----------------------- +def silhouette(g, x, y, w, h, bl, entry, base, cols, st, title): + """The graph without its text: a block a box 24 high, as wide as its rows (8 a row, 72 at least), its offset + and visits; the pc's gold; edges and lanes as on the map, small.""" + lay, back = layers(bl, entry) + widths = {a: max(132, 60 + len(bl[a].rows) * 10) for a in bl} + heights = {a: 24 for a in bl} + nb = len(back) + x0 = x + 24 + nb * 10 + 16 + pos, lh, ly = place(bl, lay, cols, widths, heights, x0 + 60, y + TAG + 14, 300, 12) + C.tag(g, x, y, w, h, title, focus=True, note="its blocks · the visits · the path") + edges(g, bl, lay, back, pos, widths, heights, lh, ly, 12, st, base, x + 24, max(pos[a][0] + widths[a] for a in bl) + 20, + small=True) + for a in bl: + s_ = st["blocks"].get(a, {}) + bx, by = pos[a] + cur = s_.get("cur") + g.rect(bx, by, widths[a], 24, RAISED if s_.get("count") else PAGE) + g.frame(bx, by, widths[a], 24, GOLD if cur else RULE, 2 if not cur else 3) + g.t(bx + 8, b(by), "+%x" % (a - base), S, VELLUM if s_.get("count") else FAINT, MONO) + if s_.get("count"): + g.t(bx + widths[a] - 8, b(by), "×%d" % s_["count"], S, DIM, MONO, "end") + return pos + + +def frame_lens(name): + """Mock 25: sort at moment 370 in the working frame with the `blocks` lens: its drawing the graph as shapes, + its view the disassembly round the pc (moved from the program column, which is the source's alone).""" + gen.W, gen.H = 1920, 1080 + g = Svg() + st = sort_state(UPTO, 0x4011db, [0x4011d9, 0x4011d6, 0x4011cf], NOTES_370) + pos = silhouette(g, 64, 48, 880, 296, SORT_BL, SB[0], SORT_BASE, {a: c for a, c in SORT_COLS.items()}, st, + "the blocks of sort") + # its view: the disassembly, seven rows round the pc, the block's rows bracketed as the drawing's gold box + C.LX, C.CW = 976, 880 + rows = [(a, ln, mn, [(t, CODE)] if t and mn.startswith("j") else [(ops, VELLUM)], + "cur" if a == 0x4011db else {0x4011d9: "trail0", 0x4011d6: "trail1", 0x4011cf: "trail2"}.get(a), + ("runs", NOTES_370[a]) if a in NOTES_370 else None) + for a, ln, mn, ops, t, callee in SORT if 0x4011c7 <= a <= 0x4011e1] # seven rows: the view's + C.disasm(g, 48, rows, "sort · +84 to +a1", 12) + C.LX, C.CW = 64, 880 + # the program column: the source alone + src = open(HERE + "/../../anim/tools/sort.c").read().split("\n") + C.source(g, 356, 21, src, 1, 12, [14, 13], "sort.c", 22) + # registers and the stack, moment 370 + S_, H_ = STACK, HEAP + E = [(0x7fffffffed00, S_), (0x7fffffffedb0, S_), (0x7fffffffee10, S_)] + regs = [("rax", [], ("int", 5)), ("rbx", [], ("int", 0)), ("rcx", [], ("int", 0x10)), ("rdx", [], ("int", 0x11)), + ("rsi", [(0x404034, DATA)], ("int", 0x1f0000001a)), ("rdi", [(0x404030, DATA)], ("int", 0x1a00000005)), + ("rbp", [(0x7fffffffecf0, S_)] + E, ("int", 0)), ("rsp", [(0x7fffffffecd8, S_)], ("int", 0x800000000)), + ("r8", [(0x7ffff7e19680, DATA)], None), ("r9", [(0x7ffff7e1afa0, DATA)], None), + ("r10", [(0x7fffffffea60, S_)], ("int", 0)), ("r11", [(0x7ffff7ffca90, DATA)], ("int", 0x786843bb9f54c5c1)), + ("r12", [(0x7fffffffee38, S_), (0x7fffffffefea, S_)], ("str", "./sort")), ("r13", [], ("int", 1)), + ("r14", [(0x7ffff7ffd000, DATA), (0x7ffff7ffe3c0, DATA)], ("int", 0)), + ("r15", [(0x403e10, DATA), (0x4010e0, CODE, "__do_global_dtors_aux")], None), + ("rip", [(0x4011db, CODE, "sort+152")], None)] + flags = [("CF", 0, 0), ("PF", 1, 0), ("AF", 1, 0), ("ZF", 0, 0), ("SF", 0, 0), ("IF", 1, 0), ("DF", 0, 0), ("OF", 0, 0)] + C.RX = 976 + C.registers(g, 260, regs, flags, {"rax": {0: "tick"}, "rdx": {0: "tick"}}) + C.stack(g, 712, [(0x7fffffffecd8, ["rsp"], [], ("int", 0x800000000)), (0x7fffffffece0, [], [], ("int", 0)), + (0x7fffffffece8, [], [], ("int", 0x400000006)), (0x7fffffffecf0, ["rbp"], E, ("int", 0)), + (0x7fffffffecf8, [], [(0x4011ff, CODE, "main+14")], None), + (0x7fffffffed00, [], E[1:], ("int", 0))], + [("sort(8)", 0, 4)], rsp=0x7fffffffecd8, + roles={2: ("i, j", VELLUM), 3: ("saved rbp", DIM)}) + C.clock(g, 370, 465) + gen.caption(g, [[("The sixth pass, its third compare: ",), ("17 : 5", "mono"), (", so ",), ("jg", "mono"), + (" goes back to the swap.",)], + [("The swap has run 5 times so far; the outer loop has turned 5.",)]]) + g.save(name) + + +if __name__ == "__main__": + assert len(SORT_BL) == 8 and len(REV_BL) == 4, (len(SORT_BL), len(REV_BL)) + assert Counter(SORT_PATH)[NAMES["B4"]] == 17 and Counter(SORT_PATH)[NAMES["B2"]] == 10 + frame_sort_map("22-graph-sort") + frame_open_map("23-graph-open") + frame_strip("24-graph-strip") + frame_lens("25-blocks-lens") diff --git a/design/mock/libc-open.dis b/design/mock/libc-open.dis new file mode 100644 index 0000000..d3c3caf --- /dev/null +++ b/design/mock/libc-open.dis @@ -0,0 +1,84 @@ + 110ec0: endbr64 + 110ec4: push rbp + 110ec5: mov rbp,rsp + 110ec8: sub rsp,0x70 + 110ecc: mov QWORD PTR [rbp-0x30],rdx + 110ed0: mov rax,QWORD PTR fs:0x28 + 110ed9: mov QWORD PTR [rbp-0x48],rax + 110edd: xor eax,eax + 110edf: test sil,0x40 + 110ee3: jne 110f90 <__open+0xd0> + 110ee9: mov eax,esi + 110eeb: xor r10d,r10d + 110eee: not eax + 110ef0: test eax,0x410000 + 110ef5: je 110f90 <__open+0xd0> + 110efb: mov r11,QWORD PTR fs:0x10 + 110f04: movsxd rdx,esi + 110f07: mov eax,DWORD PTR [r11+0x308] + 110f0e: cmp BYTE PTR [rip+0x11018b],0x0 # 2210a0 <__libc_single_threaded> + 110f15: jne 110fb0 <__open+0xf0> + 110f1b: test al,0x1 + 110f1d: jne 110fb0 <__open+0xf0> + 110f23: test al,0x10 + 110f25: jne 110fb0 <__open+0xf0> + 110f2b: push 0x0 + 110f2d: mov rcx,rdi + 110f30: mov r8,rdx + 110f33: mov esi,0x101 + 110f38: push 0x0 + 110f3a: mov rdx,0xffffffffffffff9c + 110f41: lea rdi,[r11+0x308] + 110f48: mov r9,r10 + 110f4b: mov QWORD PTR [rbp-0x68],r11 + 110f4f: call a08c0 <__syscall_cancel_arch> + 110f54: mov r11,QWORD PTR [rbp-0x68] + 110f58: mov rdx,rax + 110f5b: mov ecx,DWORD PTR [r11+0x308] + 110f62: pop rax + 110f63: mov rax,rdx + 110f66: pop rsi + 110f67: cmp rdx,0xfffffffffffffffc + 110f6b: jne 110fca <__open+0x10a> + 110f6d: and ecx,0x39 + 110f70: cmp ecx,0x8 + 110f73: je 110ff6 <__open+0x136> + 110f79: mov edx,0x4 + 110f7e: mov rax,QWORD PTR [rip+0x107d6b] # 218cf0 <_GLOBAL_OFFSET_TABLE_+0x180> + 110f85: mov DWORD PTR fs:[rax],edx + 110f88: mov eax,0xffffffff + 110f8d: jmp 110fd4 <__open+0x114> + 110f8f: nop + 110f90: lea rax,[rbp+0x10] + 110f94: mov DWORD PTR [rbp-0x60],0x10 + 110f9b: movsxd r10,DWORD PTR [rbp-0x30] + 110f9f: mov QWORD PTR [rbp-0x58],rax + 110fa3: lea rax,[rbp-0x40] + 110fa7: mov QWORD PTR [rbp-0x50],rax + 110fab: jmp 110efb <__open+0x3b> + 110fb0: mov rsi,rdi + 110fb3: xor r9d,r9d + 110fb6: xor r8d,r8d + 110fb9: mov rdi,0xffffffffffffff9c + 110fc0: mov eax,0x101 + 110fc5: syscall + 110fc7: mov rdx,rax + 110fca: cmp rax,0xfffffffffffff000 + 110fd0: ja 110fe8 <__open+0x128> + 110fd2: mov eax,edx + 110fd4: mov rdx,QWORD PTR [rbp-0x48] + 110fd8: sub rdx,QWORD PTR fs:0x28 + 110fe1: jne 110fec <__open+0x12c> + 110fe3: leave + 110fe4: ret + 110fe5: nop DWORD PTR [rax] + 110fe8: neg edx + 110fea: jmp 110f7e <__open+0xbe> + 110fec: mov QWORD PTR [rbp-0x8],rbx + 110ff0: addr32 call 12e340 <__stack_chk_fail> + 110ff6: mov rax,QWORD PTR [rbp-0x48] + 110ffa: sub rax,QWORD PTR fs:0x28 + 111003: mov QWORD PTR [rbp-0x8],rbx + 111007: jne 110ff0 <__open+0x130> + 111009: call 94890 <__syscall_do_cancel> + 11100e: xchg ax,ax diff --git a/design/mock/overflow.c b/design/mock/overflow.c new file mode 100644 index 0000000..bbd9a73 --- /dev/null +++ b/design/mock/overflow.c @@ -0,0 +1,10 @@ +// A loop writes 32 bytes into a 16-byte stack buffer. +__attribute__((noinline)) static void fill(void) { + char buf[16]; + for (int i = 0; i < 32; i++) buf[i] = 'A'; +} + +int main(void) { + fill(); + return 0; +} diff --git a/design/mock/pair.py b/design/mock/pair.py new file mode 100644 index 0000000..1311b95 --- /dev/null +++ b/design/mock/pair.py @@ -0,0 +1,231 @@ +#!/usr/bin/env python3 +"""A `pair`: two builds of one program against each other. overflow.c, built plain and with clang's +AddressSanitizer (-O0 -g -fno-omit-frame-pointer -no-pie -fno-stack-protector), each recorded by instruction from +`fill` with ztrace; the frames, the shadow and the report are those recordings'. + + python3 -B pair.py # 26-pair-rest, 27-pair-store, 28-pair-part (.svg) +""" +import gen +import context as C +from context import (PAGE, RAISED, RULE, VELLUM, BRIGHT, DIM, FAINT, GOLD, KW, CODE, STACK, DATA, HEAP, LIT, READ, + A, S, ROW, TAG, PAD, MONO, BOLD, b, ph, mix, Svg) + +HERE = __file__.rsplit("/", 1)[0] +SRC = open(HERE + "/overflow.c").read().split("\n") +S_, D_, C_ = STACK, DATA, CODE +LEFT, RIGHT = 64, 976 +P = VELLUM + +PLAIN = [(0x401144, 4, "mov", "dword ptr [rbp - 0x14], 0"), (0x40114b, 4, "cmp", "dword ptr [rbp - 0x14], 0x20"), + (0x40114f, 4, "jge", 0x401165), (0x401151, 4, "movsxd", "rax, dword ptr [rbp - 0x14]"), + (0x401155, 4, "mov", "byte ptr [rbp + rax - 0x10], 0x41"), (0x40115a, 4, "mov", "eax, dword ptr [rbp - 0x14]"), + (0x40115d, 4, "add", "eax, 1"), (0x401160, 4, "mov", "dword ptr [rbp - 0x14], eax"), (0x401163, 4, "jmp", 0x40114b), + (0x401165, 5, "pop", "rbp"), (0x401166, 5, "ret", "")] +ASAN = [(0x523d1e, 4, "cmp", "dword ptr [rbx + 0x64], 0x20"), (0x523d22, 4, "jl", 0x523d26), (0x523d24, 4, "jmp", 0x523d6c), + (0x523d26, 4, "mov", "rax, qword ptr [rbx + 0x18]"), (0x523d2a, 4, "movsxd", "rcx, dword ptr [rbx + 0x64]"), + (0x523d2e, 4, "add", "rax, rcx"), (0x523d31, 4, "mov", "qword ptr [rbx], rax"), (0x523d34, 4, "shr", "rax, 3"), + (0x523d38, 4, "mov", "al, byte ptr [rax + 0x7fff8000]"), (0x523d3e, 4, "mov", "byte ptr [rbx + 0xf], al"), + (0x523d41, 4, "cmp", "al, 0"), (0x523d43, 4, "je", 0x523d5b), (0x523d45, 4, "mov", "cl, byte ptr [rbx + 0xf]"), + (0x523d48, 4, "mov", "rax, qword ptr [rbx]"), (0x523d4b, 4, "and", "rax, 7"), (0x523d4f, 4, "cmp", "al, cl"), + (0x523d51, 4, "jl", 0x523d5b), (0x523d53, 4, "mov", "rdi, qword ptr [rbx]"), (0x523d56, 4, "call", 0x4e8450), + (0x523d5b, 4, "mov", "rax, qword ptr [rbx]"), (0x523d5e, 4, "mov", "byte ptr [rax], 0x41"), + (0x523d61, 4, "mov", "eax, dword ptr [rbx + 0x64]"), (0x523d64, 4, "add", "eax, 1"), + (0x523d67, 4, "mov", "dword ptr [rbx + 0x64], eax"), (0x523d6a, 4, "jmp", 0x523d1e)] +ONLY = {0x523d24, 0x523d26, 0x523d2e, 0x523d31, 0x523d34, 0x523d38, 0x523d3e, 0x523d41, 0x523d43, 0x523d45, 0x523d48, + 0x523d4b, 0x523d4f, 0x523d51, 0x523d53, 0x523d56, 0x523d5b} # rows the plain build has no counterpart for +NAMES = {0x4e8450: "__asan_report_store1"} +FAKE = 0x7bfff58f0000 + + +def rows_of(code, first, n, states, notes): + out = [] + for a, ln, mn, ops in code: + if a < first or len(out) == n: + continue + parts = [((ops, NAMES[ops]) if ops in NAMES else ops, C_)] if isinstance(ops, int) else ([(ops, P)] if ops else []) + out.append((a, ln, mn, parts, states.get(a), notes.get(a))) + return out + + +def bar(g, x, y, ink, w=4, h=ROW): + """`only here` (dim) and `differs` (bright): a bar on the row's edge that faces the seam.""" + g.rect(x, y + 1, w, h - 2, ink) + + +def at_side(x): + C.LX = x + C.RX = x + + +def regs(g, x, y, title, rows, marks=None): + y0 = C.panel(g, x, y, C.CW, len(rows), title, note="the line's registers, and rip") + marks = marks or {} + for i, (name, links, end) in enumerate(rows): + yy = y0 + i * ROW + if name == "rip": + g.t(x + 12, b(yy), name, S, C.current_row(g, x + 2, yy, C.CW - 4, 54), BOLD) + else: + g.t(x + 12, b(yy), name, S, DIM, MONO) + if links: + C.chain(g, x + 72, yy, links, end, marks.get(name), room=x + C.CW - 12) + elif marks.get(name, {}).get(0) == "strike": + s_ = "0x%x" % end[1] + g.t(x + 72, b(yy), s_, S, C.struck(g, x + 67, yy, len(s_) * A + 10), BOLD) + else: + C.integer(g, x + 72, yy, end[1]) + + +def shadow_cell(g, x, y, v, read=False): + """A shadow byte on the row of the eight bytes it stands for, in the offset's place.""" + if v >= 0xf0: # a redzone: poisoned, on the freed hatch + g.rect(x - 3, y + 2, 30, ROW - 4, "url(#hatch)") + g.t(x, b(y), "%02x" % v, S, BRIGHT, BOLD) + else: + g.t(x, b(y), "%02x" % v, S, FAINT, MONO) + if read: + g.frame(x - 6, y, 36, ROW, READ, 2) + + +def source_pair(g, cur_l, cur_r, waiting_r=False): + """The source shared across both columns; the left run's mark on the number, the right run's at the right end.""" + C.LX, C.CW = 64, 1792 + ys = C.source(g, 48, 5, SRC, 2, cur_l, [], "overflow.c · both builds", 10) + y_r = 48 + TAG + PAD + (cur_r - 2) * ROW + xr = 64 + 1792 - 2 - 24 + if cur_r != cur_l: + g.rect(64 + 2, y_r, 1792 - 4, ROW, C.WASH) + g.rect(xr, y_r, 24, ROW, GOLD) + g.path(f"M{xr + 8},{y_r + 12} l8,-6 v12 Z", fill=gen.INK) + g.t(xr - 10, b(y_r), "asan", 18, DIM, "sans", "end") + g.t(64 + 46 + 60, b(ys) if False else b(ys), "", 18, DIM, "sans") + C.CW = 880 + return ys + + +def frame(name, part): + """The pair at the loop. part=False: i = 15, both builds at the line's store (plain) and its check (asan). + part=True: i = 16, the step in which they part: plain's store struck into the saved rbp; asan's check read f3.""" + gen.W, gen.H = 1920, 1080 + g = Svg() + i = 16 if part else 15 + source_pair(g, 4, 4) + # ---- the left column: plain ---- + at_side(LEFT) + pn = {0x401155: ("chain", [(0x7fffffffece0 if part else 0x7fffffffecdf, S_)], + ("int", 0x41) if part else ("int", 0), {"end": "strike"} if part else None)} + ps = {0x401155: "cur", 0x401151: "trail0", 0x40114f: "trail1", 0x40114b: "trail2"} + C.disasm(g, 212, rows_of(PLAIN, 0x401144, 9, ps, pn), "plain · fill", 4) + regs(g, LEFT, 472, "plain · registers", + [("rax", [], ("int", i)), ("rbp", [(0x7fffffffece0, S_), (0x7fffffffed41 if part else 0x7fffffffed00, S_)], None), + ("rsp", [(0x7fffffffece0, S_)], None), ("rip", [(0x401155, C_, "fill+21")], None)], + {"rax": {0: "tick"}}) + sv = 0x7fffffffed41 if part else 0x7fffffffed00 + prow = [(0x7fffffffecb0, [], [], ("int", 0)), (0x7fffffffecb8, [], [], ("int", 0)), + (0x7fffffffecc0, [], [], ("int", 0)), (0x7fffffffecc8, [], [], ("int", i << 32)), + (0x7fffffffecd0, [], [], ("str", "AAAAAAAA")), (0x7fffffffecd8, [], [], ("str", "AAAAAAA" if not part else "AAAAAAAA")), + (0x7fffffffece0, ["rbp", "rsp"], [(sv, S_)], None) + (({1: "strike"},) if part else ()), + (0x7fffffffece8, [], [(0x401134, C_, "main+20")], None), + (0x7fffffffecf0, [], [], ("int", 0)), (0x7fffffffecf8, [], [], ("int", 0))] + py = C.stack(g, 612, prow, [("fill", 3, 7)], note="red zone, buf, the frame · rsp at +0", rsp=0x7fffffffece0, + roles={3: ("i, high half", VELLUM), 4: ("buf[0..7]", VELLUM), 5: ("buf[8..15]", VELLUM), + 6: ("saved rbp", DIM), 7: ("return", DIM)}, title="plain · stack") + # ---- the right column: asan ---- + at_side(RIGHT) + an = {0x523d38: ("chain", [(0xf807eb16006 if part else 0xf807eb16005, D_)], ("int", 0xf3 if part else 0), + {0: "read"} if part else None), + 0x523d34: ("set", "rax", [], ("int", (FAKE + 0x20 + i) >> 3))} + ast = {0x523d38: "cur", 0x523d34: "trail0", 0x523d31: "trail1", 0x523d2e: "trail2"} + if part: + an[0x523d41] = ("runs", [("f3", VELLUM), (" : ", FAINT), ("0", VELLUM), (" ", FAINT), ("zf", DIM)]) + an[0x523d43] = ("runs", [("not taken", DIM)]) + ar = rows_of(ASAN, 0x523d26, 9, ast, an) + at = C.disasm(g, 212, ar, "asan · fill", 4) + for a, yy in at.items(): + if a in ONLY: + bar(g, RIGHT + 2, yy, DIM) # its seam is on its left + regs(g, RIGHT, 472, "asan · registers", + [("rax", [], ("int", (FAKE + 0x20 + i) >> 3)), ("rbx", [(0x7fffffffec20, S_), (FAKE + 0x20 + i, D_)], None), + ("rcx", [], ("int", i)), ("rip", [(0x523d38, C_, "fill+216")], None)], {"rax": {0: "tick"}}) + arow = [(FAKE + 0x00, [], [], ("int", 0x41b58ab3)), (FAKE + 0x08, [], [(0x5387a7, VELLUM)], ("str", "1 32 16 5 buf:3")), + (FAKE + 0x10, [], [(0x523c60, C_, "fill")], None), (FAKE + 0x18, [], [(0x7fffffffec10, S_)], None), + (FAKE + 0x20, [], [], ("str", "AAAAAAAA")), (FAKE + 0x28, [], [], ("str", "AAAAAAA" if not part else "AAAAAAAA")), + (FAKE + 0x30, [], [], ("int", 0)), (FAKE + 0x38, [], [(0x7bfff58e8000, D_)], None)] + ay = C.stack(g, 612, arow + [(0x7fffffffecc0, ["rbp"], [(0x7fffffffece0, S_)], None), + (0x7fffffffecc8, [], [(0x523c54, C_, "main+20")], None)], + [("fill", 0, 9)], note="the fake frame, its shadow · the real stack's way back", rsp=None, + roles={0: ("magic", DIM), 1: ("descr", DIM), 2: ("pc", DIM), 3: ("real stack", DIM), + 4: ("buf[0..7]", VELLUM), 5: ("buf[8..15]", VELLUM), 6: ("redzone", DIM), 7: ("redzone", DIM), + 8: ("saved rbp", DIM), 9: ("return", DIM)}, title="asan · fake stack", + ink_of=lambda a: S_ if a >= 0x7ffffffde000 else D_) + sh = [0xf1, 0xf1, 0xf1, 0xf1, 0, 0, 0xf3, 0xf3] + ys = sorted(ay.values()) if isinstance(ay, dict) else ay + base_y = 612 + TAG + PAD + for k, v in enumerate(sh): + shadow_cell(g, RIGHT + 88, base_y + k * ROW, v, read=part and k == 6) + # the real stack is another region: a rule before its two rows + g.rect(RIGHT + 2, base_y + 8 * ROW, C.CW - 4, 2, RULE) + # `differs`: the rows that face each other across the seam and hold different things (buf's end: saved rbp vs redzone) + for k in (6, 7): + bar(g, LEFT + 880 - 6, base_y + k * ROW, BRIGHT if part or k == 6 else BRIGHT) + bar(g, RIGHT + 2, base_y + k * ROW, BRIGHT) + # the clock: one rule, each run's moment + g.rect(64, 899, 1792, 2, RULE) + g.rect(64, 898, 1792 * (17 if part else 16) / 33, 4, GOLD) + g.t(1648, 934, "i %d · moments %d / %d" % (i, 164 if part else 156, 770 if part else 753), S, FAINT, MONO, "end") + if part: + gen.caption(g, [[("i = 16, one past ",), ("buf", "mono"), (": plain writes ",), ("'A'", "mono"), + (" into the saved rbp. ASan reads",)], + [("the shadow first: ",), ("f3", "mono"), (", a redzone. Its branch to the store is not taken.",)]]) + else: + gen.caption(g, [[("The same line, two builds: plain stores the byte; ASan first",)], + [("reads the byte of shadow that stands for it: ",), ("00", "mono"), (", so it may.",)]]) + g.save(name) + + +def sheet_store(name): + """Mock 27: one turn of the loop, row by row, the plain build's rows facing their counterparts in the ASan + build's; the rows only ASan has barred on the seam side, the plain side's page facing them. i = 3.""" + gen.W, gen.H = 1920, 1080 + g = Svg() + face = {0x40114b: 0x523d1e, 0x40114f: 0x523d22, 0x401151: 0x523d2a, 0x401155: 0x523d5e, 0x40115a: 0x523d61, + 0x40115d: 0x523d64, 0x401160: 0x523d67, 0x401163: 0x523d6a} + order = [a for a, *_ in ASAN] + notes = {0x523d26: ("chain", [(FAKE + 0x20, D_)], None, None), + 0x523d2e: ("set", "rax", [(FAKE + 0x23, D_)], ("str", "AAA")), + 0x523d34: ("set", "rax", [], ("int", (FAKE + 0x23) >> 3)), + 0x523d38: ("chain", [(0xf807eb16004, D_)], ("int", 0), None), + 0x523d41: ("runs", [("0", VELLUM), (" : ", FAINT), ("0", VELLUM), (" ", FAINT), ("ZF", "chip")]), + 0x523d43: ("runs", [("taken", VELLUM), (" · reads ZF", FAINT)]), + 0x523d5e: ("chain", [(FAKE + 0x23, D_)], ("int", 0x41), None)} + skipped = {0x523d45, 0x523d48, 0x523d4b, 0x523d4f, 0x523d51, 0x523d53, 0x523d56} # the partial check: not run at 00 + ar = [(a, ln, mn, [((ops, NAMES[ops]) if ops in NAMES else ops, C_)] if isinstance(ops, int) else ([(ops, P)] if ops else []), + "skip" if a in skipped else None, notes.get(a)) for a, ln, mn, ops in ASAN] + at_side(RIGHT) + y = 96 + at = C.disasm(g, y, ar, "asan · line 4, one turn · 17 instructions", 4) + for a, yy in at.items(): + if a in ONLY: + bar(g, RIGHT + 2, yy, DIM) + # the plain side: each row at its counterpart's height; page where it has none + at_side(LEFT) + C.tag(g, LEFT, y, 880, ph(len(ASAN)), "plain · line 4, one turn · 8 instructions", + note="each row facing its counterpart") + pnotes = {0x401151: ("set", "rax", [], ("int", 3)), + 0x401155: ("chain", [(0x7fffffffecd3, S_)], ("int", 0x41), None)} + for a, ln, mn, ops in PLAIN: + if a not in face: + continue + parts = [(ops, C_)] if isinstance(ops, int) else [(ops, P)] + C.insn_rows(g, at[face[a]], [(a, ln if a == 0x40114b else None, mn, parts, None, pnotes.get(a))], 4, lead=4) + gaps = [a for a in order if a in ONLY and a not in skipped] + g.t(LEFT + 400, at[0x523d34] + 18, "the check: plain has nothing here", 18, FAINT, "sans") + gen.caption(g, [[("Plain: one store. ASan: the address, its shadow byte (",), ("addr >> 3", "mono"), + (" + ",), ("7fff8000", "mono"), ("),", )], + [("a compare with 0, a branch; the partial check and the report only if it is not 0.",)]]) + g.save(name) + + +if __name__ == "__main__": + frame("26-pair-rest", False) + sheet_store("27-pair-store") + frame("28-pair-part", True) diff --git a/design/mock/reverse-O0.dis b/design/mock/reverse-O0.dis new file mode 100644 index 0000000..80487a3 --- /dev/null +++ b/design/mock/reverse-O0.dis @@ -0,0 +1,37 @@ +0000000000401188 : +reverse(): +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/list.c:17 + 401188: push rbp + 401189: mov rbp,rsp +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/list.c:18 + 40118c: mov QWORD PTR [rbp-0x18],0x0 +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/list.c:19 + 401194: mov rax,QWORD PTR [rip+0x2e7d] # 404018 + 40119b: mov QWORD PTR [rbp-0x10],rax +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/list.c:20 + 40119f: jmp 4011c9 +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/list.c:21 + 4011a1: mov rax,QWORD PTR [rbp-0x10] + 4011a5: mov rax,QWORD PTR [rax+0x8] + 4011a9: mov QWORD PTR [rbp-0x8],rax +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/list.c:22 + 4011ad: mov rax,QWORD PTR [rbp-0x10] + 4011b1: mov rdx,QWORD PTR [rbp-0x18] + 4011b5: mov QWORD PTR [rax+0x8],rdx +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/list.c:23 + 4011b9: mov rax,QWORD PTR [rbp-0x10] + 4011bd: mov QWORD PTR [rbp-0x18],rax +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/list.c:24 + 4011c1: mov rax,QWORD PTR [rbp-0x8] + 4011c5: mov QWORD PTR [rbp-0x10],rax +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/list.c:20 (discriminator 1) + 4011c9: cmp QWORD PTR [rbp-0x10],0x0 + 4011ce: jne 4011a1 +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/list.c:26 + 4011d0: mov rax,QWORD PTR [rbp-0x18] + 4011d4: mov QWORD PTR [rip+0x2e3d],rax # 404018 +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/list.c:27 + 4011db: nop + 4011dc: pop rbp + 4011dd: ret + diff --git a/design/mock/sort-O0.dis b/design/mock/sort-O0.dis new file mode 100644 index 0000000..c159f50 --- /dev/null +++ b/design/mock/sort-O0.dis @@ -0,0 +1,61 @@ +0000000000401143 : +sort(): +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/sort.c:9 + 401143: push rbp + 401144: mov rbp,rsp + 401147: sub rsp,0x18 + 40114b: mov DWORD PTR [rbp-0x14],edi +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/sort.c:10 + 40114e: mov DWORD PTR [rbp-0x8],0x1 + 401155: jmp 4011e1 +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/sort.c:11 + 40115a: mov eax,DWORD PTR [rbp-0x8] + 40115d: mov DWORD PTR [rbp-0x4],eax +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/sort.c:12 + 401160: jmp 4011a2 +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/sort.c:13 + 401162: mov eax,DWORD PTR [rbp-0x4] + 401165: cdqe + 401167: lea rdx,[rax*4+0x0] + 40116f: lea rax,[rip+0x2eaa] # 404020 + 401176: add rdx,rax + 401179: mov eax,DWORD PTR [rbp-0x4] + 40117c: sub eax,0x1 + 40117f: cdqe + 401181: lea rcx,[rax*4+0x0] + 401189: lea rax,[rip+0x2e90] # 404020 + 401190: add rax,rcx + 401193: mov rsi,rdx + 401196: mov rdi,rax + 401199: call 401116 +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/sort.c:14 + 40119e: sub DWORD PTR [rbp-0x4],0x1 +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/sort.c:12 (discriminator 1) + 4011a2: cmp DWORD PTR [rbp-0x4],0x0 + 4011a6: jle 4011dd +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/sort.c:12 (discriminator 2) + 4011a8: mov eax,DWORD PTR [rbp-0x4] + 4011ab: sub eax,0x1 + 4011ae: cdqe + 4011b0: lea rdx,[rax*4+0x0] + 4011b8: lea rax,[rip+0x2e61] # 404020 + 4011bf: mov edx,DWORD PTR [rdx+rax*1] + 4011c2: mov eax,DWORD PTR [rbp-0x4] + 4011c5: cdqe + 4011c7: lea rcx,[rax*4+0x0] + 4011cf: lea rax,[rip+0x2e4a] # 404020 + 4011d6: mov eax,DWORD PTR [rcx+rax*1] + 4011d9: cmp edx,eax + 4011db: jg 401162 +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/sort.c:10 (discriminator 1) + 4011dd: add DWORD PTR [rbp-0x8],0x1 +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/sort.c:10 (discriminator 2) + 4011e1: mov eax,DWORD PTR [rbp-0x8] + 4011e4: cmp eax,DWORD PTR [rbp-0x14] + 4011e7: jl 40115a +/home/goblin/00-projects/0x4200.cafe/01-computeranim/anim/tools/sort.c:17 + 4011ed: nop + 4011ee: nop + 4011ef: leave + 4011f0: ret + -- cgit v1.3