blob: dc39eedb2f5f48b840b660e107166dbfd42d2b95 [file] [log] [blame]
Kostya Serebryanyda63c1d2016-02-26 21:33:56 +00001//===- FuzzerTracePC.cpp - PC tracing--------------------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9// Trace PCs.
Kostya Serebryanya00b2432016-09-14 02:13:06 +000010// This module implements __sanitizer_cov_trace_pc_guard[_init],
11// the callback required for -fsanitize-coverage=trace-pc-guard instrumentation.
Kostya Serebryanyda63c1d2016-02-26 21:33:56 +000012//
Kostya Serebryanyda63c1d2016-02-26 21:33:56 +000013//===----------------------------------------------------------------------===//
14
Kostya Serebryany95b1a432016-10-19 00:12:03 +000015#include <map>
16#include <set>
17#include <sstream>
18
Kostya Serebryany1c73f1b2016-10-05 22:56:21 +000019#include "FuzzerCorpus.h"
Kostya Serebryany86586182016-09-21 21:17:23 +000020#include "FuzzerDefs.h"
Kostya Serebryanya5f94fb2016-10-14 20:20:33 +000021#include "FuzzerDictionary.h"
Kostya Serebryany95b1a432016-10-19 00:12:03 +000022#include "FuzzerExtFunctions.h"
Kostya Serebryany6f5a8042016-09-21 01:50:50 +000023#include "FuzzerTracePC.h"
Kostya Serebryany86586182016-09-21 21:17:23 +000024#include "FuzzerValueBitMap.h"
Kostya Serebryanyda63c1d2016-02-26 21:33:56 +000025
26namespace fuzzer {
Mike Aizatsky1aa501e2016-05-10 23:43:15 +000027
Kostya Serebryanya00b2432016-09-14 02:13:06 +000028TracePC TPC;
Mike Aizatsky1aa501e2016-05-10 23:43:15 +000029
Kostya Serebryanya9b0dd02016-09-29 17:43:24 +000030void TracePC::HandleTrace(uint32_t *Guard, uintptr_t PC) {
31 uint32_t Idx = *Guard;
Kostya Serebryany8e781a82016-09-18 04:52:23 +000032 if (!Idx) return;
Kostya Serebryany06b87572016-10-26 00:42:52 +000033 if (!PCs[Idx % kNumPCs])
34 PCs[Idx % kNumPCs] = PC;
Kostya Serebryany0800b812016-09-23 23:51:58 +000035 uint8_t *CounterPtr = &Counters[Idx % kNumCounters];
36 uint8_t Counter = *CounterPtr;
Kostya Serebryany0800b812016-09-23 23:51:58 +000037 if (UseCounters) {
38 if (Counter < 128)
39 *CounterPtr = Counter + 1;
40 else
41 *Guard = 0;
42 } else {
43 *CounterPtr = 1;
Kostya Serebryany87a598e2016-09-23 01:20:07 +000044 *Guard = 0;
Kostya Serebryany0800b812016-09-23 23:51:58 +000045 }
Kostya Serebryanyda63c1d2016-02-26 21:33:56 +000046}
Kostya Serebryanya5277d52016-09-15 01:30:18 +000047
Kostya Serebryany275e2602016-10-25 23:52:25 +000048size_t TracePC::GetTotalPCCoverage() {
49 size_t Res = 0;
Kostya Serebryany06b87572016-10-26 00:42:52 +000050 for (size_t i = 1; i < GetNumPCs(); i++)
Kostya Serebryany275e2602016-10-25 23:52:25 +000051 if (PCs[i])
52 Res++;
53 return Res;
54}
55
Kostya Serebryanya9b0dd02016-09-29 17:43:24 +000056void TracePC::HandleInit(uint32_t *Start, uint32_t *Stop) {
Kostya Serebryany3e36ec12016-09-17 05:04:47 +000057 if (Start == Stop || *Start) return;
58 assert(NumModules < sizeof(Modules) / sizeof(Modules[0]));
Kostya Serebryanya9b0dd02016-09-29 17:43:24 +000059 for (uint32_t *P = Start; P < Stop; P++)
Kostya Serebryany8e781a82016-09-18 04:52:23 +000060 *P = ++NumGuards;
Kostya Serebryany3e36ec12016-09-17 05:04:47 +000061 Modules[NumModules].Start = Start;
62 Modules[NumModules].Stop = Stop;
63 NumModules++;
64}
65
66void TracePC::PrintModuleInfo() {
67 Printf("INFO: Loaded %zd modules (%zd guards): ", NumModules, NumGuards);
68 for (size_t i = 0; i < NumModules; i++)
69 Printf("[%p, %p), ", Modules[i].Start, Modules[i].Stop);
70 Printf("\n");
Kostya Serebryanyda63c1d2016-02-26 21:33:56 +000071}
Kostya Serebryanya5277d52016-09-15 01:30:18 +000072
Kostya Serebryanybc3789a2016-09-17 06:01:55 +000073void TracePC::ResetGuards() {
Kostya Serebryanya9b0dd02016-09-29 17:43:24 +000074 uint32_t N = 0;
Kostya Serebryanybc3789a2016-09-17 06:01:55 +000075 for (size_t M = 0; M < NumModules; M++)
Kostya Serebryany17d176e12016-10-13 16:19:09 +000076 for (uint32_t *X = Modules[M].Start, *End = Modules[M].Stop; X < End; X++)
Kostya Serebryany8e781a82016-09-18 04:52:23 +000077 *X = ++N;
78 assert(N == NumGuards);
Kostya Serebryanybc3789a2016-09-17 06:01:55 +000079}
80
Kostya Serebryany1c73f1b2016-10-05 22:56:21 +000081size_t TracePC::FinalizeTrace(InputCorpus *C, size_t InputSize, bool Shrink) {
82 if (!UsingTracePcGuard()) return 0;
83 size_t Res = 0;
84 const size_t Step = 8;
85 assert(reinterpret_cast<uintptr_t>(Counters) % Step == 0);
86 size_t N = Min(kNumCounters, NumGuards + 1);
87 N = (N + Step - 1) & ~(Step - 1); // Round up.
88 for (size_t Idx = 0; Idx < N; Idx += Step) {
89 uint64_t Bundle = *reinterpret_cast<uint64_t*>(&Counters[Idx]);
90 if (!Bundle) continue;
91 for (size_t i = Idx; i < Idx + Step; i++) {
92 uint8_t Counter = (Bundle >> (i * 8)) & 0xff;
93 if (!Counter) continue;
94 Counters[i] = 0;
95 unsigned Bit = 0;
96 /**/ if (Counter >= 128) Bit = 7;
97 else if (Counter >= 32) Bit = 6;
98 else if (Counter >= 16) Bit = 5;
99 else if (Counter >= 8) Bit = 4;
100 else if (Counter >= 4) Bit = 3;
101 else if (Counter >= 3) Bit = 2;
102 else if (Counter >= 2) Bit = 1;
103 size_t Feature = (i * 8 + Bit);
104 if (C->AddFeature(Feature, InputSize, Shrink))
105 Res++;
Kostya Serebryanya5277d52016-09-15 01:30:18 +0000106 }
107 }
Kostya Serebryany1c73f1b2016-10-05 22:56:21 +0000108 if (UseValueProfile)
109 ValueProfileMap.ForEach([&](size_t Idx) {
110 if (C->AddFeature(NumGuards + Idx, InputSize, Shrink))
111 Res++;
112 });
Kostya Serebryanyd2169222016-10-01 01:04:29 +0000113 return Res;
Kostya Serebryanya5277d52016-09-15 01:30:18 +0000114}
115
Kostya Serebryany09845172016-09-15 22:16:15 +0000116void TracePC::HandleCallerCallee(uintptr_t Caller, uintptr_t Callee) {
117 const uintptr_t kBits = 12;
118 const uintptr_t kMask = (1 << kBits) - 1;
Kostya Serebryany1c73f1b2016-10-05 22:56:21 +0000119 uintptr_t Idx = (Caller & kMask) | ((Callee & kMask) << kBits);
120 HandleValueProfile(Idx);
Kostya Serebryany09845172016-09-15 22:16:15 +0000121}
122
Kostya Serebryany95b1a432016-10-19 00:12:03 +0000123static bool IsInterestingCoverageFile(std::string &File) {
124 if (File.find("compiler-rt/lib/") != std::string::npos)
125 return false; // sanitizer internal.
126 if (File.find("/usr/lib/") != std::string::npos)
127 return false;
128 if (File.find("/usr/include/") != std::string::npos)
129 return false;
130 if (File == "<null>")
131 return false;
132 return true;
133}
134
Kostya Serebryanya5b2e542016-10-26 00:20:51 +0000135void TracePC::PrintNewPCs() {
136 if (DoPrintNewPCs) {
137 if (!PrintedPCs)
138 PrintedPCs = new std::set<uintptr_t>;
Kostya Serebryany06b87572016-10-26 00:42:52 +0000139 for (size_t i = 1; i < GetNumPCs(); i++)
Kostya Serebryanya5b2e542016-10-26 00:20:51 +0000140 if (PCs[i] && PrintedPCs->insert(PCs[i]).second)
141 PrintPC("\tNEW_PC: %p %F %L\n", "\tNEW_PC: %p\n", PCs[i]);
142 }
143}
144
Kostya Serebryanyb706b482016-09-18 21:47:08 +0000145void TracePC::PrintCoverage() {
Kostya Serebryany95b1a432016-10-19 00:12:03 +0000146 if (!EF->__sanitizer_symbolize_pc) {
147 Printf("INFO: __sanitizer_symbolize_pc is not available,"
148 " not printing coverage\n");
149 return;
150 }
151 std::map<std::string, std::vector<uintptr_t>> CoveredPCsPerModule;
152 std::map<std::string, uintptr_t> ModuleOffsets;
153 std::set<std::string> CoveredFiles, CoveredFunctions, CoveredLines;
Kostya Serebryanyb706b482016-09-18 21:47:08 +0000154 Printf("COVERAGE:\n");
Kostya Serebryany06b87572016-10-26 00:42:52 +0000155 for (size_t i = 1; i < GetNumPCs(); i++) {
Kostya Serebryany95b1a432016-10-19 00:12:03 +0000156 if (!PCs[i]) continue;
157 std::string FileStr = DescribePC("%s", PCs[i]);
158 if (!IsInterestingCoverageFile(FileStr)) continue;
159 std::string FixedPCStr = DescribePC("%p", PCs[i]);
160 std::string FunctionStr = DescribePC("%F", PCs[i]);
161 std::string LineStr = DescribePC("%l", PCs[i]);
162 // TODO(kcc): get the module using some other way since this
163 // does not work with ASAN_OPTIONS=strip_path_prefix=something.
164 std::string Module = DescribePC("%m", PCs[i]);
165 std::string OffsetStr = DescribePC("%o", PCs[i]);
166 uintptr_t FixedPC = std::stol(FixedPCStr, 0, 16);
167 uintptr_t PcOffset = std::stol(OffsetStr, 0, 16);
168 ModuleOffsets[Module] = FixedPC - PcOffset;
169 CoveredPCsPerModule[Module].push_back(PcOffset);
170 CoveredFunctions.insert(FunctionStr);
171 CoveredFiles.insert(FileStr);
172 if (!CoveredLines.insert(FileStr + ":" + LineStr).second)
173 continue;
174 Printf("COVERED: %s %s:%s\n", FunctionStr.c_str(),
175 FileStr.c_str(), LineStr.c_str());
176 }
177
178 for (auto &M : CoveredPCsPerModule) {
179 std::set<std::string> UncoveredFiles, UncoveredFunctions;
180 std::map<std::string, std::set<int> > UncoveredLines; // Func+File => lines
181 auto &ModuleName = M.first;
182 auto &CoveredOffsets = M.second;
183 uintptr_t ModuleOffset = ModuleOffsets[ModuleName];
184 std::sort(CoveredOffsets.begin(), CoveredOffsets.end());
185 Printf("MODULE_WITH_COVERAGE: %s\n", ModuleName.c_str());
186 // sancov does not yet fully support DSOs.
187 // std::string Cmd = "sancov -print-coverage-pcs " + ModuleName;
188 std::string Cmd = "objdump -d " + ModuleName +
189 " | grep 'call.*__sanitizer_cov_trace_pc_guard' | awk -F: '{print $1}'";
190 std::string SanCovOutput;
191 if (!ExecuteCommandAndReadOutput(Cmd, &SanCovOutput)) {
192 Printf("INFO: Command failed: %s\n", Cmd.c_str());
193 continue;
194 }
195 std::istringstream ISS(SanCovOutput);
196 std::string S;
197 while (std::getline(ISS, S, '\n')) {
198 uintptr_t PcOffset = std::stol(S, 0, 16);
199 if (!std::binary_search(CoveredOffsets.begin(), CoveredOffsets.end(),
200 PcOffset)) {
201 uintptr_t PC = ModuleOffset + PcOffset;
202 auto FileStr = DescribePC("%s", PC);
203 if (!IsInterestingCoverageFile(FileStr)) continue;
204 if (CoveredFiles.count(FileStr) == 0) {
205 UncoveredFiles.insert(FileStr);
206 continue;
207 }
208 auto FunctionStr = DescribePC("%F", PC);
209 if (CoveredFunctions.count(FunctionStr) == 0) {
210 UncoveredFunctions.insert(FunctionStr);
211 continue;
212 }
213 std::string LineStr = DescribePC("%l", PC);
214 uintptr_t Line = std::stoi(LineStr);
215 std::string FileLineStr = FileStr + ":" + LineStr;
216 if (CoveredLines.count(FileLineStr) == 0)
217 UncoveredLines[FunctionStr + " " + FileStr].insert(Line);
218 }
219 }
220 for (auto &FileLine: UncoveredLines)
221 for (int Line : FileLine.second)
222 Printf("UNCOVERED_LINE: %s:%d\n", FileLine.first.c_str(), Line);
223 for (auto &Func : UncoveredFunctions)
224 Printf("UNCOVERED_FUNC: %s\n", Func.c_str());
225 for (auto &File : UncoveredFiles)
226 Printf("UNCOVERED_FILE: %s\n", File.c_str());
Kostya Serebryanyb706b482016-09-18 21:47:08 +0000227 }
228}
229
Kostya Serebryany379359c2016-10-05 01:09:40 +0000230// Value profile.
231// We keep track of various values that affect control flow.
232// These values are inserted into a bit-set-based hash map.
233// Every new bit in the map is treated as a new coverage.
234//
235// For memcmp/strcmp/etc the interesting value is the length of the common
236// prefix of the parameters.
237// For cmp instructions the interesting value is a XOR of the parameters.
238// The interesting value is mixed up with the PC and is then added to the map.
239
240void TracePC::AddValueForMemcmp(void *caller_pc, const void *s1, const void *s2,
241 size_t n) {
242 if (!n) return;
243 size_t Len = std::min(n, (size_t)32);
244 const uint8_t *A1 = reinterpret_cast<const uint8_t *>(s1);
245 const uint8_t *A2 = reinterpret_cast<const uint8_t *>(s2);
246 size_t I = 0;
247 for (; I < Len; I++)
248 if (A1[I] != A2[I])
249 break;
250 size_t PC = reinterpret_cast<size_t>(caller_pc);
251 size_t Idx = I;
252 // if (I < Len)
253 // Idx += __builtin_popcountl((A1[I] ^ A2[I])) - 1;
254 TPC.HandleValueProfile((PC & 4095) | (Idx << 12));
255}
256
257void TracePC::AddValueForStrcmp(void *caller_pc, const char *s1, const char *s2,
258 size_t n) {
259 if (!n) return;
260 size_t Len = std::min(n, (size_t)32);
261 const uint8_t *A1 = reinterpret_cast<const uint8_t *>(s1);
262 const uint8_t *A2 = reinterpret_cast<const uint8_t *>(s2);
263 size_t I = 0;
264 for (; I < Len; I++)
265 if (A1[I] != A2[I] || A1[I] == 0)
266 break;
267 size_t PC = reinterpret_cast<size_t>(caller_pc);
268 size_t Idx = I;
269 // if (I < Len && A1[I])
270 // Idx += __builtin_popcountl((A1[I] ^ A2[I])) - 1;
271 TPC.HandleValueProfile((PC & 4095) | (Idx << 12));
272}
273
Kostya Serebryany17d176e12016-10-13 16:19:09 +0000274template <class T>
Kostya Serebryany379359c2016-10-05 01:09:40 +0000275ATTRIBUTE_TARGET_POPCNT
Kostya Serebryany17d176e12016-10-13 16:19:09 +0000276#ifdef __clang__ // g++ can't handle this __attribute__ here :(
277__attribute__((always_inline))
278#endif // __clang__
279void TracePC::HandleCmp(void *PC, T Arg1, T Arg2) {
280 uintptr_t PCuint = reinterpret_cast<uintptr_t>(PC);
Kostya Serebryanya5f94fb2016-10-14 20:20:33 +0000281 uint64_t ArgXor = Arg1 ^ Arg2;
282 uint64_t ArgDistance = __builtin_popcountl(ArgXor) + 1; // [1,65]
Kostya Serebryany17d176e12016-10-13 16:19:09 +0000283 uintptr_t Idx = ((PCuint & 4095) + 1) * ArgDistance;
Kostya Serebryanya5f94fb2016-10-14 20:20:33 +0000284 TORCInsert(ArgXor, Arg1, Arg2);
Kostya Serebryany17d176e12016-10-13 16:19:09 +0000285 HandleValueProfile(Idx);
Kostya Serebryany379359c2016-10-05 01:09:40 +0000286}
287
Kostya Serebryanyda63c1d2016-02-26 21:33:56 +0000288} // namespace fuzzer
289
Dan Liew59144072016-06-06 20:27:09 +0000290extern "C" {
Kostya Serebryany32661f92016-08-18 20:52:52 +0000291__attribute__((visibility("default")))
Kostya Serebryanya9b0dd02016-09-29 17:43:24 +0000292void __sanitizer_cov_trace_pc_guard(uint32_t *Guard) {
Kostya Serebryanya00b2432016-09-14 02:13:06 +0000293 uintptr_t PC = (uintptr_t)__builtin_return_address(0);
Kostya Serebryanya5277d52016-09-15 01:30:18 +0000294 fuzzer::TPC.HandleTrace(Guard, PC);
Kostya Serebryanyda63c1d2016-02-26 21:33:56 +0000295}
Dan Liew59144072016-06-06 20:27:09 +0000296
Kostya Serebryany32661f92016-08-18 20:52:52 +0000297__attribute__((visibility("default")))
Kostya Serebryanya9b0dd02016-09-29 17:43:24 +0000298void __sanitizer_cov_trace_pc_guard_init(uint32_t *Start, uint32_t *Stop) {
Kostya Serebryanya5277d52016-09-15 01:30:18 +0000299 fuzzer::TPC.HandleInit(Start, Stop);
Dan Liew59144072016-06-06 20:27:09 +0000300}
Kostya Serebryany09845172016-09-15 22:16:15 +0000301
302__attribute__((visibility("default")))
303void __sanitizer_cov_trace_pc_indir(uintptr_t Callee) {
304 uintptr_t PC = (uintptr_t)__builtin_return_address(0);
305 fuzzer::TPC.HandleCallerCallee(PC, Callee);
306}
Kostya Serebryany379359c2016-10-05 01:09:40 +0000307
Kostya Serebryany379359c2016-10-05 01:09:40 +0000308__attribute__((visibility("default")))
Kostya Serebryany17d176e12016-10-13 16:19:09 +0000309void __sanitizer_cov_trace_cmp8(uint64_t Arg1, uint64_t Arg2) {
310 fuzzer::TPC.HandleCmp(__builtin_return_address(0), Arg1, Arg2);
Kostya Serebryany379359c2016-10-05 01:09:40 +0000311}
312__attribute__((visibility("default")))
Kostya Serebryany17d176e12016-10-13 16:19:09 +0000313void __sanitizer_cov_trace_cmp4(uint32_t Arg1, uint32_t Arg2) {
314 fuzzer::TPC.HandleCmp(__builtin_return_address(0), Arg1, Arg2);
Kostya Serebryany379359c2016-10-05 01:09:40 +0000315}
316__attribute__((visibility("default")))
Kostya Serebryany17d176e12016-10-13 16:19:09 +0000317void __sanitizer_cov_trace_cmp2(uint16_t Arg1, uint16_t Arg2) {
318 fuzzer::TPC.HandleCmp(__builtin_return_address(0), Arg1, Arg2);
Kostya Serebryany379359c2016-10-05 01:09:40 +0000319}
320__attribute__((visibility("default")))
Kostya Serebryany17d176e12016-10-13 16:19:09 +0000321void __sanitizer_cov_trace_cmp1(uint8_t Arg1, uint8_t Arg2) {
322 fuzzer::TPC.HandleCmp(__builtin_return_address(0), Arg1, Arg2);
Kostya Serebryany379359c2016-10-05 01:09:40 +0000323}
324
325__attribute__((visibility("default")))
326void __sanitizer_cov_trace_switch(uint64_t Val, uint64_t *Cases) {
Kostya Serebryanyd19919a2016-10-11 01:14:41 +0000327 uint64_t N = Cases[0];
328 uint64_t *Vals = Cases + 2;
329 char *PC = (char*)__builtin_return_address(0);
330 for (size_t i = 0; i < N; i++)
331 if (Val != Vals[i])
Kostya Serebryany17d176e12016-10-13 16:19:09 +0000332 fuzzer::TPC.HandleCmp(PC + i, Val, Vals[i]);
Kostya Serebryany379359c2016-10-05 01:09:40 +0000333}
334
335__attribute__((visibility("default")))
336void __sanitizer_cov_trace_div4(uint32_t Val) {
Kostya Serebryany17d176e12016-10-13 16:19:09 +0000337 fuzzer::TPC.HandleCmp(__builtin_return_address(0), Val, (uint32_t)0);
Kostya Serebryany379359c2016-10-05 01:09:40 +0000338}
339__attribute__((visibility("default")))
340void __sanitizer_cov_trace_div8(uint64_t Val) {
Kostya Serebryany17d176e12016-10-13 16:19:09 +0000341 fuzzer::TPC.HandleCmp(__builtin_return_address(0), Val, (uint64_t)0);
Kostya Serebryany379359c2016-10-05 01:09:40 +0000342}
343__attribute__((visibility("default")))
344void __sanitizer_cov_trace_gep(uintptr_t Idx) {
Kostya Serebryany17d176e12016-10-13 16:19:09 +0000345 fuzzer::TPC.HandleCmp(__builtin_return_address(0), Idx, (uintptr_t)0);
Kostya Serebryany379359c2016-10-05 01:09:40 +0000346}
347
348} // extern "C"