blob: 4328c19b7fd3dae24a5c6a393e804d36c59478ac [file] [log] [blame]
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +02001/*
2 *
3 * honggfuzz - sanitizer coverage feedback parsing
4 * -----------------------------------------------
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License"); you may
7 * not use this file except in compliance with the License. You may obtain
8 * a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
15 * implied. See the License for the specific language governing
16 * permissions and limitations under the License.
17 *
18 */
19
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +020020/*
21 * Clang sanitizer coverage (sancov) data parsing functions. Supported methods:
22 * - raw unified data (preferred method)
23 * - individual data per executable/DSO (not preferred since lots of data lost if instrumented
24 * code exits abnormally or with sanitizer unhandled signal (common in Android OS)
Robert Swiecki72d2bef2016-01-19 14:39:26 +010025 *
26 * For raw-unpack method a global (shared across workers) Trie is created for the chosen
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +020027 * initial seed and maintained until seed is replaced. Trie nodes store the loaded (as exposed
28 * from *.sancov.map file) execs/DSOs from target application using the map name as key. Trie node
29 * data struct (trieData_t) maintains information for each instrumented map including a bitmap with
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +020030 * all hit relative BB addresses (realBBAddr - baseAddr to circumvent ASLR). Map's bitmap is updated while
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +020031 * new areas on target application are discovered based on absolute elitism implemented at
32 * fuzz_sanCovFeedback().
Robert Swiecki72d2bef2016-01-19 14:39:26 +010033 *
Anestis Bechtsoudisa7c56ce2016-02-07 12:53:20 +020034 * For individual data files a pid (fuzzer's thread or remote process) based filename search is performed
35 * to identify all files belonging to examined execution. This method doesn't implement yet bitmap runtime
36 * data to detect newly discovered areas. It's mainly used so far as a comparison metric for raw-unpack method
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +020037 * and stability check for sancov experimental features such as coverage counters:
38 * http://clang.llvm.org/docs/SanitizerCoverage.html
39 */
40
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +020041#include "common.h"
42#include "sancov.h"
43
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +020044#include <ctype.h>
Jagger00265602016-03-10 02:36:27 +010045#include <dirent.h>
46#include <inttypes.h>
47#include <stdio.h>
48#include <stdlib.h>
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +020049#include <string.h>
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +020050#include <sys/mman.h>
Jagger00265602016-03-10 02:36:27 +010051#include <sys/stat.h>
52#include <sys/types.h>
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +020053
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +020054#include "files.h"
55#include "log.h"
Jagger00265602016-03-10 02:36:27 +010056#include "util.h"
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +020057
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +020058/* sancov files magic values */
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +020059#define kMagic32 0xC0BFFFFFFFFFFF32
60#define kMagic64 0xC0BFFFFFFFFFFF64
61
Robert Swiecki72d2bef2016-01-19 14:39:26 +010062/*
Anestis Bechtsoudis0ddd0782016-12-28 18:33:28 +020063 * Each DSO/executable that has been compiled with enabled coverage instrumentation
64 * is detected from compiler_rt runtime library when loaded. When coverage_direct
65 * method is selected, runtime library is pre-allocating kPcArrayMmapSize [1] byte
66 * chunks until the total size of chunks is greater than the number of inserted
67 * guards. This effectively means that we might have a large unused (zero-filled)
68 * area that we can't identify at runtime (we need to do binary inspection).
69 *
70 * Runtime maintained data structs size overhead is not affected since fixed-size
71 * bitmap is used. However, the way the display coverage statistics are generated
72 * is not very accurate because:
73 * a) ASan compiled DSO might get loaded although not followed from monitoring
74 execution affecting the counters
75 * b) Not all zero-fill chunks translate into non-hit basic block as they might
76 * be the chunk padding
77 *
78 * Probably there aren't many we can do to deal with this issue without introducing
79 * a huge performance overhead at an already costly feedback method.
80 *
81 * [1] 'https://llvm.org/svn/llvm-project/compiler-rt/branches/release_38/lib/sanitizer_common/sanitizer_coverage_libcdep.cc'
82 */
83#define kPcArrayMmapSize (64 * 1024)
84
85/*
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +020086 * bitmap implementation
87 */
Jagger3db1d952016-03-10 02:02:46 +010088static bitmap_t *sancov_newBitmap(uint32_t capacity)
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +020089{
Jagger679c2052016-03-18 22:53:53 +010090 bitmap_t *pBM = util_Malloc(sizeof(bitmap_t));
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +020091 pBM->capacity = capacity;
92 pBM->nChunks = (capacity + 31) / 32;
Jagger74d0d102016-03-18 22:55:59 +010093 pBM->pChunks = util_Calloc(pBM->nChunks * sizeof(uint32_t));
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +020094 return pBM;
95}
96
Jagger3db1d952016-03-10 02:02:46 +010097static inline bool sancov_queryBitmap(bitmap_t * pBM, uint32_t index)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +020098{
Anestis Bechtsoudis58c45d22016-01-10 15:05:39 +020099 if (index > pBM->capacity) {
100 LOG_E("bitmap overflow (%u)", index);
101 return false;
102 }
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200103 if (pBM->pChunks[index / 32] & (1 << (index % 32))) {
104 return true;
105 }
106 return false;
107}
108
Jagger3db1d952016-03-10 02:02:46 +0100109static inline void sancov_setBitmap(bitmap_t * pBM, uint32_t index)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200110{
111 /* This will be removed. So far checks only to verify accepted ranges. */
112 if (index >= pBM->capacity) {
113 LOG_E("Out of range index (%u > %u)", index, pBM->capacity);
114 }
115 pBM->pChunks[index / 32] |= (1 << (index % 32));
116}
117
Jagger3db1d952016-03-10 02:02:46 +0100118static inline void sancov_destroyBitmap(bitmap_t * pBM)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200119{
120 free(pBM->pChunks);
121 free(pBM);
122}
123
Robert Swiecki72d2bef2016-01-19 14:39:26 +0100124/*
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200125 * Trie implementation
126 */
Jagger3db1d952016-03-10 02:02:46 +0100127static node_t *sancov_trieCreateNode(char key)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200128{
Jagger679c2052016-03-18 22:53:53 +0100129 node_t *node = (node_t *) util_Malloc(sizeof(node_t));
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200130 node->key = key;
131 node->next = NULL;
132 node->children = NULL;
133 node->parent = NULL;
134 node->prev = NULL;
135
136 /* Zero init node's data struct */
137 memset(&node->data, 0, sizeof(trieData_t));
138 return node;
139}
140
Jagger3db1d952016-03-10 02:02:46 +0100141static node_t *sancov_trieSearch(node_t * root, const char *key)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200142{
143 node_t *pNodeLevel = root, *pNodePtr = NULL;
144 int nodeLevelId = 0;
145 while (1) {
146 node_t *pNodeFound = NULL, *pCurNode = NULL;
147 for (pCurNode = pNodeLevel; pCurNode != NULL; pCurNode = pCurNode->next) {
148 if (pCurNode->key == *key) {
149 pNodeFound = pCurNode;
150 nodeLevelId++;
151 break;
152 }
153 }
154 if (pNodeFound == NULL) {
155 return NULL;
156 }
157 if (*key == '\0') {
158 pNodePtr = pCurNode;
159 return pNodePtr;
160 }
161 pNodeLevel = pNodeFound->children;
162 key++;
163 }
164}
165
Robert Swiecki40ef8402016-03-10 15:14:13 +0100166static void sancov_trieAdd(node_t ** root, const char *key)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200167{
168 if (*root == NULL) {
169 LOG_E("Invalid Trie (NULL root node)");
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +0200170 return;
171 }
172
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200173 /* Traverse Trie */
174 node_t *pTravNode = (*root)->children;
175 if (pTravNode == NULL) {
176 /* First node */
Anestis Bechtsoudis267f0d82016-01-08 16:02:50 +0200177 for (pTravNode = *root; *key != '\0'; pTravNode = pTravNode->children) {
Jagger3db1d952016-03-10 02:02:46 +0100178 pTravNode->children = sancov_trieCreateNode(*key);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200179 pTravNode->children->parent = pTravNode;
180 key++;
181 }
Jagger3db1d952016-03-10 02:02:46 +0100182 pTravNode->children = sancov_trieCreateNode('\0');
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200183 pTravNode->children->parent = pTravNode;
184 return;
185 }
186
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200187 while (*key != '\0') {
188 if (*key == pTravNode->key) {
189 key++;
190 pTravNode = pTravNode->children;
191 } else {
192 break;
193 }
194 }
195 while (pTravNode->next) {
196 if (*key == pTravNode->next->key) {
197 key++;
Robert Swiecki40ef8402016-03-10 15:14:13 +0100198 sancov_trieAdd(&(pTravNode->next), key);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200199 return;
200 }
201 pTravNode = pTravNode->next;
202 }
203 if (*key) {
Jagger3db1d952016-03-10 02:02:46 +0100204 pTravNode->next = sancov_trieCreateNode(*key);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200205 } else {
Jagger3db1d952016-03-10 02:02:46 +0100206 pTravNode->next = sancov_trieCreateNode(*key);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200207 }
208 pTravNode->next->parent = pTravNode->parent;
209 pTravNode->next->prev = pTravNode;
210 if (!*key) {
211 return;
212 }
213 key++;
214 for (pTravNode = pTravNode->next; *key; pTravNode = pTravNode->children) {
Jagger3db1d952016-03-10 02:02:46 +0100215 pTravNode->children = sancov_trieCreateNode(*key);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200216 pTravNode->children->parent = pTravNode;
217 key++;
218 }
Jagger3db1d952016-03-10 02:02:46 +0100219 pTravNode->children = sancov_trieCreateNode('\0');
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200220 pTravNode->children->parent = pTravNode;
221
222 return;
223}
224
Jagger3db1d952016-03-10 02:02:46 +0100225static inline void sancov_trieFreeNode(node_t * node)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200226{
227 /* First destroy bitmap heap buffers allocated for instrumented maps */
228 if (node->data.pBM) {
Jagger3db1d952016-03-10 02:02:46 +0100229 sancov_destroyBitmap(node->data.pBM);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200230 }
231 free(node);
232}
233
Jagger3db1d952016-03-10 02:02:46 +0100234static inline void sancov_trieCreate(node_t ** root)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200235{
236 /* Create root node if new Trie */
Jagger3db1d952016-03-10 02:02:46 +0100237 *root = sancov_trieCreateNode('\0');
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200238}
239
240/* Destroy Trie - iterate nodes and free memory */
Robert Swiecki3bfc33c2016-03-14 18:12:41 +0100241UNUSED static void sancov_trieDestroy(node_t * root)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200242{
243 node_t *pNode = root;
244 node_t *pNodeTmp = root;
245 while (pNode) {
246 while (pNode->children) {
247 pNode = pNode->children;
248 }
249
250 if (pNode->prev && pNode->next) {
251 pNodeTmp = pNode;
252 pNode->next->prev = pNode->prev;
253 pNode->prev->next = pNode->next;
Jagger3db1d952016-03-10 02:02:46 +0100254 sancov_trieFreeNode(pNodeTmp);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200255 } else if (pNode->prev && !pNode->next) {
256 pNodeTmp = pNode;
257 pNode->prev->next = NULL;
Jagger3db1d952016-03-10 02:02:46 +0100258 sancov_trieFreeNode(pNodeTmp);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200259 } else if (!pNode->prev && pNode->next) {
260 pNodeTmp = pNode;
261 pNode->parent->children = pNode->next;
262 pNode->next->prev = NULL;
263 pNode = pNode->next;
Jagger3db1d952016-03-10 02:02:46 +0100264 sancov_trieFreeNode(pNodeTmp);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200265 } else {
266 pNodeTmp = pNode;
267 if (pNode->parent == NULL) {
268 /* Root */
Jagger3db1d952016-03-10 02:02:46 +0100269 sancov_trieFreeNode(pNodeTmp);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200270 return;
271 }
272 pNode = pNode->parent;
273 pNode->children = NULL;
Jagger3db1d952016-03-10 02:02:46 +0100274 sancov_trieFreeNode(pNodeTmp);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200275 }
276 }
277}
278
279/* Modified interpolation search algorithm to search for nearest address fit */
Jagger3db1d952016-03-10 02:02:46 +0100280static inline uint64_t sancov_interpSearch(uint64_t * buf, uint64_t size, uint64_t key)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200281{
282 /* Avoid extra checks assuming caller always provides non-zero array size */
283 uint64_t low = 0;
284 uint64_t high = size - 1;
285 uint64_t mid = high;
286
287 while (buf[high] != buf[low] && key >= buf[low] && key <= buf[high]) {
288 mid = low + (key - buf[low]) * ((high - low) / (buf[high] - buf[low]));
289 if (buf[mid] < key) {
290 low = mid + 1;
291 } else if (key < buf[mid]) {
292 high = mid - 1;
293 } else {
294 return mid;
295 }
296 }
297 return mid;
298}
299
300/* qsort struct comparison function (memMap_t struct start addr field) */
Jagger3db1d952016-03-10 02:02:46 +0100301static int sancov_qsortCmp(const void *a, const void *b)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200302{
303 memMap_t *pA = (memMap_t *) a;
304 memMap_t *pB = (memMap_t *) b;
305 if (pA->start < pB->start) {
306 return -1;
307 } else if (pA->start > pB->start) {
308 return 1;
309 } else {
310 /* Normally we should never hit that case */
311 LOG_W("Duplicate map start addr detected");
312 return 0;
313 }
314
315}
316
Jagger3db1d952016-03-10 02:02:46 +0100317static bool sancov_sanCovParseRaw(honggfuzz_t * hfuzz, fuzzer_t * fuzzer)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200318{
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +0200319 int dataFd = -1;
320 uint8_t *dataBuf = NULL;
321 off_t dataFileSz = 0, pos = 0;
Jaggerf26b1b62016-03-19 01:59:30 +0100322 bool is32bit = true;
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +0200323 char covFile[PATH_MAX] = { 0 };
Jagger247c3b42016-03-21 23:24:05 +0100324 pid_t targetPid = (hfuzz->linux.pid > 0) ? hfuzz->linux.pid : fuzzer->pid;
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +0200325
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200326 /* Fuzzer local runtime data structs - need free() before exit */
327 uint64_t *startMapsIndex = NULL;
328 memMap_t *mapsBuf = NULL;
329
330 /* Local counters */
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200331 uint64_t nBBs = 0; /* Total BB hits found in raw file */
332 uint64_t nZeroBBs = 0; /* Number of non-hit instrumented BBs */
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200333 uint64_t mapsNum = 0; /* Total number of entries in map file */
334 uint64_t noCovMapsNum = 0; /* Loaded DSOs not compiled with coverage */
335
Anestis Bechtsoudis267f0d82016-01-08 16:02:50 +0200336 /* File line-by-line read help buffers */
Jaggerd6f74bb2016-03-19 02:51:18 +0100337 __block char *pLine = NULL;
Anestis Bechtsoudis267f0d82016-01-08 16:02:50 +0200338 size_t lineSz = 0;
339
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200340 /* Coverage data analysis starts by parsing map file listing */
341 snprintf(covFile, sizeof(covFile), "%s/%s/%d.sancov.map", hfuzz->workDir, _HF_SANCOV_DIR,
Anestis Bechtsoudisa7c56ce2016-02-07 12:53:20 +0200342 targetPid);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200343 if (!files_exists(covFile)) {
344 LOG_D("sancov map file not found");
345 return false;
346 }
347 FILE *fCovMap = fopen(covFile, "rb");
348 if (fCovMap == NULL) {
349 PLOG_E("Couldn't open '%s' - R/O mode", covFile);
Jaggerf26b1b62016-03-19 01:59:30 +0100350 return false;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200351 }
Jagger4fe18692016-04-22 23:15:07 +0200352 defer {
353 fclose(fCovMap);
354 };
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +0200355
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200356 /* First line contains PC length (32/64-bit) */
Anestis Bechtsoudis267f0d82016-01-08 16:02:50 +0200357 if (getline(&pLine, &lineSz, fCovMap) == -1) {
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200358 LOG_E("Invalid map file '%s'", covFile);
Jaggerf26b1b62016-03-19 01:59:30 +0100359 return false;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200360 }
Jagger4fe18692016-04-22 23:15:07 +0200361 defer {
362 free(pLine);
363 pLine = NULL;
364 };
Jaggerf26b1b62016-03-19 01:59:30 +0100365
Anestis Bechtsoudis267f0d82016-01-08 16:02:50 +0200366 int pcLen = atoi(pLine);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200367 if (pcLen == 32) {
368 is32bit = true;
369 } else if (pcLen == 64) {
370 is32bit = false;
371 } else {
372 LOG_E("Invalid PC length (%d) in map file '%s'", pcLen, covFile);
373 }
Anestis Bechtsoudis1fc7cd42015-12-26 17:54:15 +0200374
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200375 /* See if #maps is available from previous run to avoid realloc inside loop */
Jaggerd34417d2016-03-16 01:26:54 +0100376 uint64_t prevMapsNum = ATOMIC_GET(hfuzz->sanCovCnts.dsoCnt);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200377 if (prevMapsNum > 0) {
Jagger679c2052016-03-18 22:53:53 +0100378 mapsBuf = util_Malloc(prevMapsNum * sizeof(memMap_t));
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +0200379 }
Jaggerf26b1b62016-03-19 01:59:30 +0100380 /* It's OK to free(NULL) */
Jagger4fe18692016-04-22 23:15:07 +0200381 defer {
382 free(mapsBuf);
383 };
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +0200384
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200385 /* Iterate map entries */
386 for (;;) {
Anestis Bechtsoudis267f0d82016-01-08 16:02:50 +0200387 if (getline(&pLine, &lineSz, fCovMap) == -1) {
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200388 break;
389 }
390
391 /* Trim trailing whitespaces, not sure if needed copied from upstream sancov.py */
Anestis Bechtsoudis267f0d82016-01-08 16:02:50 +0200392 char *lineEnd = pLine + strlen(pLine) - 1;
Jagger43c33e52016-03-11 22:16:26 +0100393 while (lineEnd > pLine && isspace((int)*lineEnd)) {
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200394 lineEnd--;
395 }
396 *(lineEnd + 1) = 0;
397
Robert Swiecki72d2bef2016-01-19 14:39:26 +0100398 /*
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200399 * Each line has following format:
400 * Start End Base bin/DSO name
401 * b5843000 b584e6ac b5843000 liblog.so
402 */
Jagger05c79c52016-01-31 18:00:51 +0100403 memMap_t mapData = {.start = 0 };
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200404 char *savePtr = NULL;
Anestis Bechtsoudis267f0d82016-01-08 16:02:50 +0200405 mapData.start = strtoull(strtok_r(pLine, " ", &savePtr), NULL, 16);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200406 mapData.end = strtoull(strtok_r(NULL, " ", &savePtr), NULL, 16);
407 mapData.base = strtoull(strtok_r(NULL, " ", &savePtr), NULL, 16);
408 char *mapName = strtok_r(NULL, " ", &savePtr);
409 memcpy(mapData.mapName, mapName, strlen(mapName));
410
411 /* Interaction with global Trie should mutex wrap to avoid threads races */
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200412 {
Robert Swiecki76ecd5e2016-03-16 14:57:03 +0100413 MX_SCOPED_LOCK(&hfuzz->sanCov_mutex);
Robert Swiecki5d6e7342016-03-16 15:36:11 +0100414
Anestis Bechtsoudis1fd10c72016-01-07 12:38:45 +0200415 /* Add entry to Trie with zero data if not already */
Jagger3db1d952016-03-10 02:02:46 +0100416 if (!sancov_trieSearch(hfuzz->covMetadata->children, mapData.mapName)) {
Robert Swiecki40ef8402016-03-10 15:14:13 +0100417 sancov_trieAdd(&hfuzz->covMetadata, mapData.mapName);
Anestis Bechtsoudis1fd10c72016-01-07 12:38:45 +0200418 }
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200419 }
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200420
Anestis Bechtsoudis0ddd0782016-12-28 18:33:28 +0200421 /* If no DSO number history (first run) or new DSO loaded, realloc local maps metadata buf */
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200422 if (prevMapsNum == 0 || prevMapsNum < mapsNum) {
Jaggerf49962d2016-07-21 22:49:54 +0200423 if ((mapsBuf =
424 util_Realloc(mapsBuf, (size_t) (mapsNum + 1) * sizeof(memMap_t))) == NULL) {
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200425 PLOG_E("realloc failed (sz=%" PRIu64 ")", (mapsNum + 1) * sizeof(memMap_t));
Jaggerf26b1b62016-03-19 01:59:30 +0100426 return false;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200427 }
428 }
Anestis Bechtsoudis1fd10c72016-01-07 12:38:45 +0200429
430 /* Add entry to local maps metadata array */
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200431 memcpy(&mapsBuf[mapsNum], &mapData, sizeof(memMap_t));
432
433 /* Increase loaded maps counter (includes non-instrumented DSOs too) */
434 mapsNum++;
435 }
436
437 /* Delete .sancov.map file */
Robert Swiecki8656cbb2016-03-30 19:06:37 +0200438 if (hfuzz->linux.pid == 0 && hfuzz->persistent == false) {
Jagger1ebc6dc2016-03-12 01:39:09 +0100439 unlink(covFile);
440 }
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200441
442 /* Create a quick index array with maps start addresses */
Jagger679c2052016-03-18 22:53:53 +0100443 startMapsIndex = util_Malloc(mapsNum * sizeof(uint64_t));
Jagger4fe18692016-04-22 23:15:07 +0200444 defer {
445 free(startMapsIndex);
446 };
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200447
448 /* Sort quick maps index */
Jagger3db1d952016-03-10 02:02:46 +0100449 qsort(mapsBuf, mapsNum, sizeof(memMap_t), sancov_qsortCmp);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200450 for (size_t i = 0; i < mapsNum; i++) {
451 startMapsIndex[i] = mapsBuf[i].start;
452 }
453
454 /* mmap() .sancov.raw file */
455 snprintf(covFile, sizeof(covFile), "%s/%s/%d.sancov.raw", hfuzz->workDir, _HF_SANCOV_DIR,
Anestis Bechtsoudisa7c56ce2016-02-07 12:53:20 +0200456 targetPid);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200457 dataBuf = files_mapFile(covFile, &dataFileSz, &dataFd, false);
458 if (dataBuf == NULL) {
459 LOG_E("Couldn't open and map '%s' in R/O mode", covFile);
Jaggerf26b1b62016-03-19 01:59:30 +0100460 return false;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200461 }
Jagger4fe18692016-04-22 23:15:07 +0200462 defer {
463 munmap(dataBuf, dataFileSz);
464 close(dataFd);
465 };
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200466
Robert Swiecki72d2bef2016-01-19 14:39:26 +0100467 /*
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200468 * Avoid cost of size checks inside raw data read loop by defining the read function
469 * & pivot size based on PC length.
470 */
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200471 uint64_t(*pReadRawBBAddrFunc) (const uint8_t *) = NULL;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200472 uint8_t pivot = 0;
473 if (is32bit) {
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200474 pReadRawBBAddrFunc = &util_getUINT32;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200475 pivot = 4;
476 } else {
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200477 pReadRawBBAddrFunc = &util_getUINT64;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200478 pivot = 8;
479 }
480
Robert Swiecki72d2bef2016-01-19 14:39:26 +0100481 /*
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200482 * Take advantage of data locality (next processed addr is very likely to belong
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200483 * to same map) to avoid Trie node search for each read entry.
484 */
485 node_t *curMap = NULL;
486 uint64_t prevIndex = 0;
487
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200488 /* Iterate over data buffer containing list of hit BB addresses */
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +0200489 while (pos < dataFileSz) {
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200490 uint64_t bbAddr = pReadRawBBAddrFunc(dataBuf + pos);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200491 pos += pivot;
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200492 /* Don't bother for zero BB addr (inserted checks without hit) */
493 if (bbAddr == 0x0) {
494 nZeroBBs++;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200495 continue;
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +0200496 } else {
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200497 /* Find best hit based on start addr & verify range for errors */
Jagger3db1d952016-03-10 02:02:46 +0100498 uint64_t bestFit = sancov_interpSearch(startMapsIndex, mapsNum, bbAddr);
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200499 if (bbAddr >= mapsBuf[bestFit].start && bbAddr < mapsBuf[bestFit].end) {
500 /* Increase exe/DSO total BB counter */
501 mapsBuf[bestFit].bbCnt++;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200502
503 /* Update current Trie node if map changed */
504 if (curMap == NULL || (prevIndex != bestFit)) {
505 prevIndex = bestFit;
506
507 /* Interaction with global Trie should mutex wrap to avoid threads races */
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200508 {
Robert Swiecki76ecd5e2016-03-16 14:57:03 +0100509 MX_SCOPED_LOCK(&hfuzz->sanCov_mutex);
Robert Swiecki5d6e7342016-03-16 15:36:11 +0100510
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200511 curMap =
Jagger3db1d952016-03-10 02:02:46 +0100512 sancov_trieSearch(hfuzz->covMetadata->children,
513 mapsBuf[bestFit].mapName);
Anestis Bechtsoudis1fd10c72016-01-07 12:38:45 +0200514 if (curMap == NULL) {
515 LOG_E("Corrupted Trie - '%s' not found", mapsBuf[bestFit].mapName);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200516 continue;
517 }
518
519 /* Maintain bitmaps only for exec/DSOs with coverage enabled - allocate on first use */
520 if (curMap->data.pBM == NULL) {
Anestis Bechtsoudis1fd10c72016-01-07 12:38:45 +0200521 LOG_D("Allocating bitmap for map '%s'", mapsBuf[bestFit].mapName);
Jagger3d977522016-08-21 19:15:59 +0200522 curMap->data.pBM = sancov_newBitmap(_HF_SANCOV_BITMAP_SIZE);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200523
Robert Swiecki72d2bef2016-01-19 14:39:26 +0100524 /*
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200525 * If bitmap allocation failed, unset cached Trie node ptr
526 * to execute this selection branch again.
527 */
528 if (curMap->data.pBM == NULL) {
529 curMap = NULL;
Anestis Bechtsoudis1fd10c72016-01-07 12:38:45 +0200530 continue;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200531 }
532 }
533 }
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200534 }
535
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200536 /* If new relative BB addr update DSO's bitmap */
537 uint32_t relAddr = (uint32_t) (bbAddr - mapsBuf[bestFit].base);
Jagger3db1d952016-03-10 02:02:46 +0100538 if (!sancov_queryBitmap(curMap->data.pBM, relAddr)) {
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200539
540 /* Interaction with global Trie should mutex wrap to avoid threads races */
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200541 {
Robert Swiecki76ecd5e2016-03-16 14:57:03 +0100542 MX_SCOPED_LOCK(&hfuzz->sanCov_mutex);
Robert Swiecki5d6e7342016-03-16 15:36:11 +0100543
Jagger3db1d952016-03-10 02:02:46 +0100544 sancov_setBitmap(curMap->data.pBM, relAddr);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200545 }
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200546
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200547 /* Also increase new BBs counter at worker's thread runtime data */
548 mapsBuf[bestFit].newBBCnt++;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200549 }
550 } else {
Robert Swiecki72d2bef2016-01-19 14:39:26 +0100551 /*
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200552 * Normally this should never get executed. If hit, sanitizer
553 * coverage data collection come across some kind of bug.
554 */
Robert Swiecki37778e02016-03-15 15:45:28 +0100555 LOG_E("Invalid BB addr (%#" PRIx64 ") at offset %" PRId64, bbAddr, (uint64_t) pos);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200556 }
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +0200557 }
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200558 nBBs++;
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +0200559 }
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200560
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200561 /* Finally iterate over all instrumented maps to sum-up the number of newly met BB addresses */
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200562 for (uint64_t i = 0; i < mapsNum; i++) {
Robert Swiecki142f9412016-03-14 19:22:01 +0100563 if (mapsBuf[i].bbCnt > 0) {
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200564 fuzzer->sanCovCnts.newBBCnt += mapsBuf[i].newBBCnt;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200565 } else {
566 noCovMapsNum++;
567 }
568 }
569
570 /* Successful parsing - update fuzzer worker's counters */
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200571 fuzzer->sanCovCnts.hitBBCnt = nBBs;
572 fuzzer->sanCovCnts.totalBBCnt = nBBs + nZeroBBs;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200573 fuzzer->sanCovCnts.dsoCnt = mapsNum;
574 fuzzer->sanCovCnts.iDsoCnt = mapsNum - noCovMapsNum; /* Instrumented DSOs */
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +0200575
Robert Swiecki8656cbb2016-03-30 19:06:37 +0200576 if (hfuzz->linux.pid == 0 && hfuzz->persistent == false) {
Jagger1ebc6dc2016-03-12 01:39:09 +0100577 unlink(covFile);
578 }
Jaggerf26b1b62016-03-19 01:59:30 +0100579 return true;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200580}
581
Jagger3db1d952016-03-10 02:02:46 +0100582static bool sancov_sanCovParse(honggfuzz_t * hfuzz, fuzzer_t * fuzzer)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200583{
584 int dataFd = -1;
585 uint8_t *dataBuf = NULL;
586 off_t dataFileSz = 0, pos = 0;
587 bool is32bit = true;
588 char covFile[PATH_MAX] = { 0 };
589 DIR *pSanCovDir = NULL;
Jagger247c3b42016-03-21 23:24:05 +0100590 pid_t targetPid = (hfuzz->linux.pid > 0) ? hfuzz->linux.pid : fuzzer->pid;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200591
592 snprintf(covFile, sizeof(covFile), "%s/%s/%s.%d.sancov", hfuzz->workDir, _HF_SANCOV_DIR,
Anestis Bechtsoudisa7c56ce2016-02-07 12:53:20 +0200593 files_basename(hfuzz->cmdline[0]), targetPid);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200594 if (!files_exists(covFile)) {
595 LOG_D("Target sancov file not found");
596 return false;
597 }
598
Anestis Bechtsoudisa7c56ce2016-02-07 12:53:20 +0200599 /* Local cache file suffix to use for file search of target pid data */
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200600 char pidFSuffix[13] = { 0 };
Anestis Bechtsoudisa7c56ce2016-02-07 12:53:20 +0200601 snprintf(pidFSuffix, sizeof(pidFSuffix), "%d.sancov", targetPid);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200602
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200603 /* Total BBs counter summarizes all DSOs */
604 uint64_t nBBs = 0;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200605
Anestis Bechtsoudisa7c56ce2016-02-07 12:53:20 +0200606 /* Iterate sancov dir for files generated against target pid */
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200607 snprintf(covFile, sizeof(covFile), "%s/%s", hfuzz->workDir, _HF_SANCOV_DIR);
608 pSanCovDir = opendir(covFile);
Jaggerf26b1b62016-03-19 01:59:30 +0100609 if (pSanCovDir == NULL) {
610 PLOG_E("opendir('%s')", covFile);
611 return false;
612 }
Jagger4fe18692016-04-22 23:15:07 +0200613 defer {
614 closedir(pSanCovDir);
615 };
Jaggerf26b1b62016-03-19 01:59:30 +0100616
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200617 struct dirent *pDir = NULL;
618 while ((pDir = readdir(pSanCovDir)) != NULL) {
Anestis Bechtsoudisa7c56ce2016-02-07 12:53:20 +0200619 /* Parse files with target's pid */
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200620 if (strstr(pDir->d_name, pidFSuffix)) {
621 snprintf(covFile, sizeof(covFile), "%s/%s/%s", hfuzz->workDir, _HF_SANCOV_DIR,
622 pDir->d_name);
623 dataBuf = files_mapFile(covFile, &dataFileSz, &dataFd, false);
624 if (dataBuf == NULL) {
625 LOG_E("Couldn't open and map '%s' in R/O mode", covFile);
Jaggerf26b1b62016-03-19 01:59:30 +0100626 return false;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200627 }
Jagger4fe18692016-04-22 23:15:07 +0200628 defer {
629 munmap(dataBuf, dataFileSz);
630 close(dataFd);
631 };
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200632
633 if (dataFileSz < 8) {
634 LOG_E("Coverage data file too short");
Jaggerf26b1b62016-03-19 01:59:30 +0100635 return false;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200636 }
637
638 /* Check magic values & derive PC length */
639 uint64_t magic = util_getUINT64(dataBuf);
640 if (magic == kMagic32) {
641 is32bit = true;
642 } else if (magic == kMagic64) {
643 is32bit = false;
644 } else {
645 LOG_E("Invalid coverage data file");
Jaggerf26b1b62016-03-19 01:59:30 +0100646 return false;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200647 }
648 pos += 8;
649
Robert Swiecki72d2bef2016-01-19 14:39:26 +0100650 /*
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200651 * Avoid cost of size checks inside raw data read loop by defining the read function
652 * & pivot size based on PC length.
653 */
654 uint64_t(*pReadRawBBAddrFunc) (const uint8_t *) = NULL;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200655 uint8_t pivot = 0;
656 if (is32bit) {
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200657 pReadRawBBAddrFunc = &util_getUINT32;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200658 pivot = 4;
659 } else {
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200660 pReadRawBBAddrFunc = &util_getUINT64;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200661 pivot = 8;
662 }
663
664 while (pos < dataFileSz) {
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200665 uint32_t bbAddr = pReadRawBBAddrFunc(dataBuf + pos);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200666 pos += pivot;
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200667 if (bbAddr == 0x0) {
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200668 continue;
669 }
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200670 nBBs++;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200671 }
672 }
673 }
674
675 /* Successful parsing - update fuzzer worker counters */
Anestis Bechtsoudis56e360f2016-01-11 14:29:17 +0200676 fuzzer->sanCovCnts.hitBBCnt = nBBs;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200677
Robert Swiecki8656cbb2016-03-30 19:06:37 +0200678 if (hfuzz->linux.pid == 0 && hfuzz->persistent == false) {
Jagger1ebc6dc2016-03-12 01:39:09 +0100679 unlink(covFile);
680 }
Jaggerf26b1b62016-03-19 01:59:30 +0100681 return true;
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200682}
683
Robert Swiecki72d2bef2016-01-19 14:39:26 +0100684/*
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200685 * Sanitizer coverage data are stored in FS can be parsed via two methods:
Robert Swiecki72d2bef2016-01-19 14:39:26 +0100686 * raw unpack & separate bin/DSO sancov file. Separate bin/DSO sancov file
687 * method is usually avoided since coverage data are lost if sanitizer unhandled
688 * signal. Additionally, the FS I/O overhead is bigger compared to raw unpack
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200689 * method which uses runtime data structures.
Robert Swiecki72d2bef2016-01-19 14:39:26 +0100690 *
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200691 * Enabled methods are controlled from sanitizer flags in arch.c
692 */
Jagger3db1d952016-03-10 02:02:46 +0100693void sancov_Analyze(honggfuzz_t * hfuzz, fuzzer_t * fuzzer)
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200694{
695 if (!hfuzz->useSanCov) {
696 return;
697 }
Robert Swiecki72d2bef2016-01-19 14:39:26 +0100698 /*
Anestis Bechtsoudis97633cc2016-01-13 16:25:57 +0200699 * For now supported methods are implemented in fail-over nature. This will
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200700 * change in the future when best method is concluded.
701 */
Jagger3db1d952016-03-10 02:02:46 +0100702 if (sancov_sanCovParseRaw(hfuzz, fuzzer) == false) {
703 sancov_sanCovParse(hfuzz, fuzzer);
Anestis Bechtsoudisa16f70f2016-01-03 13:03:21 +0200704 }
Anestis Bechtsoudisd76c3b82015-12-26 17:35:25 +0200705}
Jagger00265602016-03-10 02:36:27 +0100706
707bool sancov_Init(honggfuzz_t * hfuzz)
708{
Jagger9e7ccc12016-09-26 00:47:52 +0200709 if (hfuzz->useSanCov == false) {
710 return true;
711 }
712 sancov_trieCreate(&hfuzz->covMetadata);
713
Jagger99626d32016-09-26 00:50:14 +0200714 char sanCovOutDir[PATH_MAX] = { 0 };
715 snprintf(sanCovOutDir, sizeof(sanCovOutDir), "%s/%s", hfuzz->workDir, _HF_SANCOV_DIR);
716 if (!files_exists(sanCovOutDir)) {
717 if (mkdir(sanCovOutDir, S_IRWXU | S_IXGRP | S_IXOTH) != 0) {
718 PLOG_E("mkdir() '%s' failed", sanCovOutDir);
719 }
720 }
721
Jagger00265602016-03-10 02:36:27 +0100722 return true;
723}