summaryrefslogtreecommitdiff
path: root/design/mock/pair.py
blob: 1311b95f0b6691ecfe2dbca86ab5b91765efb79c (plain) (blame)
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
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)