Limiting taint propagation with head=yes

Motivation

The output of tg is verbose (see issue #29). One way is to limit the variables or bytes that are tainted, but I may not know which variable or bytes to focus on yet. When analyzing an executable for the first time, I want to get a feel for some of the functions that process tainted data.

Besides limiting the variables or bytes, another way is to limit how far the taint is propagated using the --head=yes option (think of it as similar to the Linux head command that reads only the first few lines of any text).

Heartbleed

Consider the heartbleed bug (CVE-2014-0160) in function dtls1_process_heartbeat (tests/heartbleed.c):

21: /* Read type and payload length first */
22: hbtype = *p++;
23: //! extracting the length of the payload from the heartbeat request package
24: n2s(p, payload);
25: pl = p;
...
34: unsigned char *buffer, *bp;
41: buffer = OPENSSL_malloc(1 + 2 + payload + padding);
42: bp = buffer;
45: *bp++ = 0;
46: s2n(payload, bp);
...
53: memcpy(bp, pl, payload);
55: RAND_pseudo_bytes(p, padding);
57: r = dtls1_write_bytes(s, TLS1_RT_HEARTBEAT, buffer, 3 + payload + padding);

The bug is on line 53, because payload, the size field passed to memcpy, is tainted, and a large value will cause an out-of-bounds read. The output of tg is 682 lines. With the --head=yes option, the output is reduced to 109 lines:

$ valgrind --tool=taintgrind --head=yes tests/heartbleed
...
0x1089EB: dtls1_process_heartbeat (heartbleed.c:22) | movzx eax, byte ptr [rax] | Load:1 | 0x2 | t76_635 <- data[0]:1ffefffd30
0x1089EB: dtls1_process_heartbeat (heartbleed.c:22) | t146_101 <- t76_635
0x1089EB: dtls1_process_heartbeat (heartbleed.c:22) | t75_522 <- t146_101
0x1089EB: dtls1_process_heartbeat (heartbleed.c:22) | t147_8 <- t75_522
0x1089EB: dtls1_process_heartbeat (heartbleed.c:22) | t74_628 <- t147_8
0x1089EB: dtls1_process_heartbeat (heartbleed.c:22) | r2_10770 <- t74_628
0x1089EB: dtls1_process_heartbeat (heartbleed.c:22) | t78_294 <- r2_10770
0x1089EB: dtls1_process_heartbeat (heartbleed.c:22) | t148_103 <- t78_294
0x1089EB: dtls1_process_heartbeat (heartbleed.c:22) | t77_563 <- t148_103
0x1089EB: dtls1_process_heartbeat (heartbleed.c:22) | r2_10771 <- t77_563
0x1089F0: dtls1_process_heartbeat (heartbleed.c:22) | mov word ptr [rbp - 0x2a], ax | Store:2 | 0x2 | hbtype:1ffefffcb6 <- t77_563
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | movzx eax, byte ptr [rax] | Load:1 | 0x0 | t87_374 <- data[1]:1ffefffd31
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t149_11 <- t87_374
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t86_180 <- t149_11
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t150_11 <- t86_180
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t85_385 <- t150_11
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | r2_10772 <- t85_385
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t90_348 <- r2_10772
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t151_15 <- t90_348
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t89_354 <- t151_15
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t152_13 <- t89_354
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t88_217 <- t152_13
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t153_11 <- t88_217
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t91_332 <- t153_11
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t154_14 <- t91_332
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t93_281 <- t154_14
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | Shl64 | 0x0 | t22_6693 <- t93_281
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t155_11 <- t22_6693
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t103_1173 <- t155_11
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t156_14 <- t103_1173
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t104_1166 <- t156_14
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t157_7 <- t104_1166
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t106_959 <- t157_7
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t158_10 <- t106_959
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | t105_1119 <- t158_10
0x1089F8: dtls1_process_heartbeat (heartbleed.c:24) | r4_8056 <- t105_1119
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | movzx eax, byte ptr [rax] | Load:1 | 0x4 | t113_375 <- data[2]:1ffefffd32
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t159_10 <- t113_375
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t112_380 <- t159_10
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t160_10 <- t112_380
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t111_1041 <- t160_10
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | r2_10773 <- t111_1041
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t116_76 <- r2_10773
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t161_9 <- t116_76
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t115_85 <- t161_9
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t162_9 <- t115_85
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t114_85 <- t162_9
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t163_9 <- t114_85
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t117_87 <- t163_9
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t164_9 <- t105_1119
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t119_75 <- t164_9
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | Or32 | 0x4 | t31_4233 <- t117_87 t119_75
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t165_8 <- t31_4233
0x108A0B: dtls1_process_heartbeat (heartbleed.c:24) | t122_117 <- t165_8
0x108A13: dtls1_process_heartbeat (heartbleed.c:24) | t166_5 <- t122_117
0x108A13: dtls1_process_heartbeat (heartbleed.c:24) | t125_18 <- t166_5
0x108A13: dtls1_process_heartbeat (heartbleed.c:24) | mov dword ptr [rbp - 0x24], eax | Store:4 | 0x4 | payload:1ffefffcbc <- t125_18
0x108A23: dtls1_process_heartbeat (heartbleed.c:32) | cmp word ptr [rbp - 0x2a], 2 | Load:2 | 0x2 | t43_1734 <- hbtype:1ffefffcb6
0x108A23: dtls1_process_heartbeat (heartbleed.c:32) | t167_5 <- t43_1734
0x108A23: dtls1_process_heartbeat (heartbleed.c:32) | t137_8 <- t167_5
0x108A23: dtls1_process_heartbeat (heartbleed.c:32) | r19_25851 <- t137_8
0x108A28: dtls1_process_heartbeat (heartbleed.c:32) | t171_5 <- t137_8
0x108A2A: dtls1_process_heartbeat (heartbleed.c:41) | mov edx, dword ptr [rbp - 0x24] | Load:4 | 0x4 | t16_13283 <- payload:1ffefffcbc
0x108A2A: dtls1_process_heartbeat (heartbleed.c:41) | t15_14083 <- t16_13283
0x108A2A: dtls1_process_heartbeat (heartbleed.c:41) | r4_8057 <- t15_14083
0x108A2D: dtls1_process_heartbeat (heartbleed.c:41) | t23_9510 <- t15_14083
0x108A5A: dtls1_process_heartbeat (heartbleed.c:46) | mov eax, dword ptr [rbp - 0x24] | Load:4 | 0x4 | t52_1517 <- payload:1ffefffcbc
0x108A5A: dtls1_process_heartbeat (heartbleed.c:46) | t51_1854 <- t52_1517
0x108A5A: dtls1_process_heartbeat (heartbleed.c:46) | t53_1714 <- t51_1854
0x108A5A: dtls1_process_heartbeat (heartbleed.c:46) | t55_1657 <- t53_1714
0x108A5A: dtls1_process_heartbeat (heartbleed.c:46) | Shr64 | 0x0 | t11_23881 <- t55_1657
0x108A5A: dtls1_process_heartbeat (heartbleed.c:46) | t65_580 <- t11_23881
0x108A5A: dtls1_process_heartbeat (heartbleed.c:46) | t66_826 <- t65_580
0x108A5A: dtls1_process_heartbeat (heartbleed.c:46) | t68_1340 <- t66_826
0x108A5A: dtls1_process_heartbeat (heartbleed.c:46) | t67_697 <- t68_1340
0x108A5A: dtls1_process_heartbeat (heartbleed.c:46) | r4_8225 <- t67_697
0x108A66: dtls1_process_heartbeat (heartbleed.c:46) | t73_632 <- r4_8225
0x108A66: dtls1_process_heartbeat (heartbleed.c:46) | mov byte ptr [rax], dl | Store:1 | 0x0 | 422a261_unknownobj <- t73_632
0x108A70: dtls1_process_heartbeat (heartbleed.c:46) | mov edx, dword ptr [rbp - 0x24] | Load:4 | 0x4 | t80_693 <- payload:1ffefffcbc
0x108A70: dtls1_process_heartbeat (heartbleed.c:46) | t79_405 <- t80_693
0x108A70: dtls1_process_heartbeat (heartbleed.c:46) | r4_8226 <- t79_405
0x108A73: dtls1_process_heartbeat (heartbleed.c:46) | t81_1089 <- r4_8226
0x108A73: dtls1_process_heartbeat (heartbleed.c:46) | mov byte ptr [rax], dl | Store:1 | 0x4 | 422a262_unknownobj <- t81_1089
0x108A7A: dtls1_process_heartbeat (heartbleed.c:53) | mov edx, dword ptr [rbp - 0x24] | Load:4 | 0x4 | t87_415 <- payload:1ffefffcbc
0x108A7A: dtls1_process_heartbeat (heartbleed.c:53) | t86_192 <- t87_415
0x108A7A: dtls1_process_heartbeat (heartbleed.c:53) | r4_8227 <- t86_192
0x4CE7460: memcpy@GLIBC_2.2.5 (memmove-vec-unaligned-erms.S:129) | t2_21051 <- r4_8227
0x4CE7460: memcpy@GLIBC_2.2.5 (memmove-vec-unaligned-erms.S:129) | r19_39709 <- t2_21051
0x4CE7567: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:267) | t2_21052 <- r4_8227
0x4CE7567: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:267) | t12_24033 <- t2_21052
0x4CE7567: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:267) | t3_17244 <- t12_24033
0x4CE7567: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:267) | r19_39710 <- t3_17244
0x4CE756A: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:268) | And64 | 0x4 | t16_18657 <- t3_17244
0x4CE756C: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:269) | t2_21053 <- r4_8227
0x4CE756C: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:269) | t12_24034 <- t2_21053
0x4CE756C: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:269) | t3_17245 <- t12_24034
0x4CE756C: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:269) | r19_39711 <- t3_17245
0x4CE756F: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:270) | And64 | 0x4 | t16_18658 <- t3_17245
0x4CE758F: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:306) | t10_24352 <- r4_8227
0x4CE758F: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:306) | mov ecx, dword ptr [rsi + rdx - 4] | Load:4 | 0x2020202 | t13_20686 <- data[3]:1ffefffd33
0x4CE758F: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:306) | t12_24035 <- t13_20686
0x4CE758F: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:306) | r3_10187 <- t12_24035
0x4CE7593: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:307) | mov esi, dword ptr [rsi] | Load:4 | 0x2020202 | t15_21785 <- data[3]:1ffefffd33
0x4CE7593: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:307) | t14_21379 <- t15_21785
0x4CE7593: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:307) | r8_2193 <- t14_21379
0x4CE7595: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:308) | t21_11566 <- t12_24035
0x4CE7595: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:308) | mov dword ptr [rdi + rdx - 4], ecx | Store:4 | 0x2020202 | 422a263_unknownobj <- t21_11566
0x4CE7599: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:309) | t23_17654 <- t14_21379
0x4CE7599: __memcpy_sse2_unaligned_erms (memmove-vec-unaligned-erms.S:309) | mov dword ptr [rdi], esi | Store:4 | 0x2020202 | 422a263_unknownobj <- t23_17654

The output shows lines 22, 24 and 32, the locations where the tainted bytes are read directly from the packet data. The output also shows request bytes being copied to the response buffer, and these are unmodified as well. It is still quite verbose, but at least memcpy shows up, which is where the bug was.

Under the hood

The intuition of --head=yes is to limit taint propagation to where the original variable or byte value(s) remain unmodified. This means that propagation is limited to only a few instructions dealing with data transfer without modification:

• Loads and Stores to/from memory
• Gets and Puts to/from registers
• Transfers between tmp variables (RdTmps)
• Unary transfer operations involving at least a byte of data
• Certain binary operations that preserve the data

For all other instructions, the shadow variables are marked as untainted, so no taint is propagated beyond the above instructions.

Experiments

I ran some tests with and without --head=yes to see how the performance varies. To stress tg, I ran some PDF parsers on a blank PDF, tainting all 1,114 bytes. For each test case, I ran it 3 times and took the average run time. I also recorded the number of lines in the output (#lines), and the number of unique functions in the output using awk '/\|/ {print $2}' | sort | uniq | wc -l.

Below are the results.

Test case	--head=yes Time (#lines) [#functions]	--head=no Time (#lines) [#functions]
tests/sign32	4.541s (22) [2]	4.576s (34) [2]
tests/heartbleed	4.551s (109) [3]	4.661s (682) [17]
gzip -c	7.130s (35,893) [8]	14.778s (255,831) [15]
pdf2txt	52.554s (370,532) [18]	1:02.060s (487,654) [24]
evince	1:56.846s (250,785) [41]	28:09.937s (3,977,085) [1,216]

For simple or small programs, the difference is not much. The difference is greater for larger, more complex programs, such as evince, and the time is reduced to about 5%, the number of lines of output is about 6%, and the number of functions is reduced to about 3%.

Conclusion

The --head=yes is an option for those who want to taint all bytes or variables, but are ok with limiting how far the taint is propagated in return for some speed up.