afl-cmin 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461
  1. #!/usr/bin/env bash
  2. #
  3. # american fuzzy lop - corpus minimization tool
  4. # ---------------------------------------------
  5. #
  6. # Written and maintained by Michal Zalewski <lcamtuf@google.com>
  7. #
  8. # Copyright 2014, 2015 Google Inc. All rights reserved.
  9. #
  10. # Licensed under the Apache License, Version 2.0 (the "License");
  11. # you may not use this file except in compliance with the License.
  12. # You may obtain a copy of the License at:
  13. #
  14. # http://www.apache.org/licenses/LICENSE-2.0
  15. #
  16. # This tool tries to find the smallest subset of files in the input directory
  17. # that still trigger the full range of instrumentation data points seen in
  18. # the starting corpus. This has two uses:
  19. #
  20. # - Screening large corpora of input files before using them as a seed for
  21. # afl-fuzz. The tool will remove functionally redundant files and likely
  22. # leave you with a much smaller set.
  23. #
  24. # (In this case, you probably also want to consider running afl-tmin on
  25. # the individual files later on to reduce their size.)
  26. #
  27. # - Minimizing the corpus generated organically by afl-fuzz, perhaps when
  28. # planning to feed it to more resource-intensive tools. The tool achieves
  29. # this by removing all entries that used to trigger unique behaviors in the
  30. # past, but have been made obsolete by later finds.
  31. #
  32. # Note that the tool doesn't modify the files themselves. For that, you want
  33. # afl-tmin.
  34. #
  35. # This script must use bash because other shells may have hardcoded limits on
  36. # array sizes.
  37. #
  38. echo "corpus minimization tool for afl-fuzz by <lcamtuf@google.com>"
  39. echo
  40. #########
  41. # SETUP #
  42. #########
  43. # Process command-line options...
  44. MEM_LIMIT=100
  45. TIMEOUT=none
  46. unset IN_DIR OUT_DIR STDIN_FILE EXTRA_PAR MEM_LIMIT_GIVEN \
  47. AFL_CMIN_CRASHES_ONLY AFL_CMIN_ALLOW_ANY QEMU_MODE
  48. while getopts "+i:o:f:m:t:eQC" opt; do
  49. case "$opt" in
  50. "i")
  51. IN_DIR="$OPTARG"
  52. ;;
  53. "o")
  54. OUT_DIR="$OPTARG"
  55. ;;
  56. "f")
  57. STDIN_FILE="$OPTARG"
  58. ;;
  59. "m")
  60. MEM_LIMIT="$OPTARG"
  61. MEM_LIMIT_GIVEN=1
  62. ;;
  63. "t")
  64. TIMEOUT="$OPTARG"
  65. ;;
  66. "e")
  67. EXTRA_PAR="$EXTRA_PAR -e"
  68. ;;
  69. "C")
  70. export AFL_CMIN_CRASHES_ONLY=1
  71. ;;
  72. "Q")
  73. EXTRA_PAR="$EXTRA_PAR -Q"
  74. test "$MEM_LIMIT_GIVEN" = "" && MEM_LIMIT=250
  75. QEMU_MODE=1
  76. ;;
  77. "?")
  78. exit 1
  79. ;;
  80. esac
  81. done
  82. shift $((OPTIND-1))
  83. TARGET_BIN="$1"
  84. if [ "$TARGET_BIN" = "" -o "$IN_DIR" = "" -o "$OUT_DIR" = "" ]; then
  85. cat 1>&2 <<_EOF_
  86. Usage: $0 [ options ] -- /path/to/target_app [ ... ]
  87. Required parameters:
  88. -i dir - input directory with the starting corpus
  89. -o dir - output directory for minimized files
  90. Execution control settings:
  91. -f file - location read by the fuzzed program (stdin)
  92. -m megs - memory limit for child process ($MEM_LIMIT MB)
  93. -t msec - run time limit for child process (none)
  94. -Q - use binary-only instrumentation (QEMU mode)
  95. Minimization settings:
  96. -C - keep crashing inputs, reject everything else
  97. -e - solve for edge coverage only, ignore hit counts
  98. For additional tips, please consult docs/README.
  99. _EOF_
  100. exit 1
  101. fi
  102. # Do a sanity check to discourage the use of /tmp, since we can't really
  103. # handle this safely from a shell script.
  104. if [ "$AFL_ALLOW_TMP" = "" ]; then
  105. echo "$IN_DIR" | grep -qE '^(/var)?/tmp/'
  106. T1="$?"
  107. echo "$TARGET_BIN" | grep -qE '^(/var)?/tmp/'
  108. T2="$?"
  109. echo "$OUT_DIR" | grep -qE '^(/var)?/tmp/'
  110. T3="$?"
  111. echo "$STDIN_FILE" | grep -qE '^(/var)?/tmp/'
  112. T4="$?"
  113. echo "$PWD" | grep -qE '^(/var)?/tmp/'
  114. T5="$?"
  115. if [ "$T1" = "0" -o "$T2" = "0" -o "$T3" = "0" -o "$T4" = "0" -o "$T5" = "0" ]; then
  116. echo "[-] Error: do not use this script in /tmp or /var/tmp." 1>&2
  117. exit 1
  118. fi
  119. fi
  120. # If @@ is specified, but there's no -f, let's come up with a temporary input
  121. # file name.
  122. TRACE_DIR="$OUT_DIR/.traces"
  123. if [ "$STDIN_FILE" = "" ]; then
  124. if echo "$*" | grep -qF '@@'; then
  125. STDIN_FILE="$TRACE_DIR/.cur_input"
  126. fi
  127. fi
  128. # Check for obvious errors.
  129. if [ ! "$MEM_LIMIT" = "none" ]; then
  130. if [ "$MEM_LIMIT" -lt "5" ]; then
  131. echo "[-] Error: dangerously low memory limit." 1>&2
  132. exit 1
  133. fi
  134. fi
  135. if [ ! "$TIMEOUT" = "none" ]; then
  136. if [ "$TIMEOUT" -lt "10" ]; then
  137. echo "[-] Error: dangerously low timeout." 1>&2
  138. exit 1
  139. fi
  140. fi
  141. if [ ! -f "$TARGET_BIN" -o ! -x "$TARGET_BIN" ]; then
  142. TNEW="`which "$TARGET_BIN" 2>/dev/null`"
  143. if [ ! -f "$TNEW" -o ! -x "$TNEW" ]; then
  144. echo "[-] Error: binary '$TARGET_BIN' not found or not executable." 1>&2
  145. exit 1
  146. fi
  147. TARGET_BIN="$TNEW"
  148. fi
  149. if [ "$AFL_SKIP_BIN_CHECK" = "" -a "$QEMU_MODE" = "" ]; then
  150. if ! grep -qF "__AFL_SHM_ID" "$TARGET_BIN"; then
  151. echo "[-] Error: binary '$TARGET_BIN' doesn't appear to be instrumented." 1>&2
  152. exit 1
  153. fi
  154. fi
  155. if [ ! -d "$IN_DIR" ]; then
  156. echo "[-] Error: directory '$IN_DIR' not found." 1>&2
  157. exit 1
  158. fi
  159. test -d "$IN_DIR/queue" && IN_DIR="$IN_DIR/queue"
  160. find "$OUT_DIR" -name 'id[:_]*' -maxdepth 1 -exec rm -- {} \; 2>/dev/null
  161. rm -rf "$TRACE_DIR" 2>/dev/null
  162. rmdir "$OUT_DIR" 2>/dev/null
  163. if [ -d "$OUT_DIR" ]; then
  164. echo "[-] Error: directory '$OUT_DIR' exists and is not empty - delete it first." 1>&2
  165. exit 1
  166. fi
  167. mkdir -m 700 -p "$TRACE_DIR" || exit 1
  168. if [ ! "$STDIN_FILE" = "" ]; then
  169. rm -f "$STDIN_FILE" || exit 1
  170. touch "$STDIN_FILE" || exit 1
  171. fi
  172. if [ "$AFL_PATH" = "" ]; then
  173. SHOWMAP="${0%/afl-cmin}/afl-showmap"
  174. else
  175. SHOWMAP="$AFL_PATH/afl-showmap"
  176. fi
  177. if [ ! -x "$SHOWMAP" ]; then
  178. echo "[-] Error: can't find 'afl-showmap' - please set AFL_PATH." 1>&2
  179. rm -rf "$TRACE_DIR"
  180. exit 1
  181. fi
  182. IN_COUNT=$((`ls -- "$IN_DIR" 2>/dev/null | wc -l`))
  183. if [ "$IN_COUNT" = "0" ]; then
  184. echo "[+] Hmm, no inputs in the target directory. Nothing to be done."
  185. rm -rf "$TRACE_DIR"
  186. exit 1
  187. fi
  188. FIRST_FILE=`ls "$IN_DIR" | head -1`
  189. # Make sure that we're not dealing with a directory.
  190. if [ -d "$IN_DIR/$FIRST_FILE" ]; then
  191. echo "[-] Error: The target directory contains subdirectories - please fix." 1>&2
  192. rm -rf "$TRACE_DIR"
  193. exit 1
  194. fi
  195. # Check for the more efficient way to copy files...
  196. if ln "$IN_DIR/$FIRST_FILE" "$TRACE_DIR/.link_test" 2>/dev/null; then
  197. CP_TOOL=ln
  198. else
  199. CP_TOOL=cp
  200. fi
  201. # Make sure that we can actually get anything out of afl-showmap before we
  202. # waste too much time.
  203. echo "[*] Testing the target binary..."
  204. if [ "$STDIN_FILE" = "" ]; then
  205. AFL_CMIN_ALLOW_ANY=1 "$SHOWMAP" -m "$MEM_LIMIT" -t "$TIMEOUT" -o "$TRACE_DIR/.run_test" -Z $EXTRA_PAR -- "$@" <"$IN_DIR/$FIRST_FILE"
  206. else
  207. cp "$IN_DIR/$FIRST_FILE" "$STDIN_FILE"
  208. AFL_CMIN_ALLOW_ANY=1 "$SHOWMAP" -m "$MEM_LIMIT" -t "$TIMEOUT" -o "$TRACE_DIR/.run_test" -Z $EXTRA_PAR -A "$STDIN_FILE" -- "$@" </dev/null
  209. fi
  210. FIRST_COUNT=$((`grep -c . "$TRACE_DIR/.run_test"`))
  211. if [ "$FIRST_COUNT" -gt "0" ]; then
  212. echo "[+] OK, $FIRST_COUNT tuples recorded."
  213. else
  214. echo "[-] Error: no instrumentation output detected (perhaps crash or timeout)." 1>&2
  215. test "$AFL_KEEP_TRACES" = "" && rm -rf "$TRACE_DIR"
  216. exit 1
  217. fi
  218. # Let's roll!
  219. #############################
  220. # STEP 1: COLLECTING TRACES #
  221. #############################
  222. echo "[*] Obtaining traces for input files in '$IN_DIR'..."
  223. (
  224. CUR=0
  225. if [ "$STDIN_FILE" = "" ]; then
  226. while read -r fn; do
  227. CUR=$((CUR+1))
  228. printf "\\r Processing file $CUR/$IN_COUNT... "
  229. "$SHOWMAP" -m "$MEM_LIMIT" -t "$TIMEOUT" -o "$TRACE_DIR/$fn" -Z $EXTRA_PAR -- "$@" <"$IN_DIR/$fn"
  230. done < <(ls "$IN_DIR")
  231. else
  232. while read -r fn; do
  233. CUR=$((CUR+1))
  234. printf "\\r Processing file $CUR/$IN_COUNT... "
  235. cp "$IN_DIR/$fn" "$STDIN_FILE"
  236. "$SHOWMAP" -m "$MEM_LIMIT" -t "$TIMEOUT" -o "$TRACE_DIR/$fn" -Z $EXTRA_PAR -A "$STDIN_FILE" -- "$@" </dev/null
  237. done < <(ls "$IN_DIR")
  238. fi
  239. )
  240. echo
  241. ##########################
  242. # STEP 2: SORTING TUPLES #
  243. ##########################
  244. # With this out of the way, we sort all tuples by popularity across all
  245. # datasets. The reasoning here is that we won't be able to avoid the files
  246. # that trigger unique tuples anyway, so we will want to start with them and
  247. # see what's left.
  248. echo "[*] Sorting trace sets (this may take a while)..."
  249. ls "$IN_DIR" | sed "s#^#$TRACE_DIR/#" | tr '\n' '\0' | xargs -0 -n 1 cat | \
  250. sort | uniq -c | sort -n >"$TRACE_DIR/.all_uniq"
  251. TUPLE_COUNT=$((`grep -c . "$TRACE_DIR/.all_uniq"`))
  252. echo "[+] Found $TUPLE_COUNT unique tuples across $IN_COUNT files."
  253. #####################################
  254. # STEP 3: SELECTING CANDIDATE FILES #
  255. #####################################
  256. # The next step is to find the best candidate for each tuple. The "best"
  257. # part is understood simply as the smallest input that includes a particular
  258. # tuple in its trace. Empirical evidence suggests that this produces smaller
  259. # datasets than more involved algorithms that could be still pulled off in
  260. # a shell script.
  261. echo "[*] Finding best candidates for each tuple..."
  262. CUR=0
  263. while read -r fn; do
  264. CUR=$((CUR+1))
  265. printf "\\r Processing file $CUR/$IN_COUNT... "
  266. sed "s#\$# $fn#" "$TRACE_DIR/$fn" >>"$TRACE_DIR/.candidate_list"
  267. done < <(ls -rS "$IN_DIR")
  268. echo
  269. ##############################
  270. # STEP 4: LOADING CANDIDATES #
  271. ##############################
  272. # At this point, we have a file of tuple-file pairs, sorted by file size
  273. # in ascending order (as a consequence of ls -rS). By doing sort keyed
  274. # only by tuple (-k 1,1) and configured to output only the first line for
  275. # every key (-s -u), we end up with the smallest file for each tuple.
  276. echo "[*] Sorting candidate list (be patient)..."
  277. sort -k1,1 -s -u "$TRACE_DIR/.candidate_list" | \
  278. sed 's/^/BEST_FILE[/;s/ /]="/;s/$/"/' >"$TRACE_DIR/.candidate_script"
  279. if [ ! -s "$TRACE_DIR/.candidate_script" ]; then
  280. echo "[-] Error: no traces obtained from test cases, check syntax!" 1>&2
  281. test "$AFL_KEEP_TRACES" = "" && rm -rf "$TRACE_DIR"
  282. exit 1
  283. fi
  284. # The sed command converted the sorted list to a shell script that populates
  285. # BEST_FILE[tuple]="fname". Let's load that!
  286. . "$TRACE_DIR/.candidate_script"
  287. ##########################
  288. # STEP 5: WRITING OUTPUT #
  289. ##########################
  290. # The final trick is to grab the top pick for each tuple, unless said tuple is
  291. # already set due to the inclusion of an earlier candidate; and then put all
  292. # tuples associated with the newly-added file to the "already have" list. The
  293. # loop works from least popular tuples and toward the most common ones.
  294. echo "[*] Processing candidates and writing output files..."
  295. CUR=0
  296. touch "$TRACE_DIR/.already_have"
  297. while read -r cnt tuple; do
  298. CUR=$((CUR+1))
  299. printf "\\r Processing tuple $CUR/$TUPLE_COUNT... "
  300. # If we already have this tuple, skip it.
  301. grep -q "^$tuple\$" "$TRACE_DIR/.already_have" && continue
  302. FN=${BEST_FILE[tuple]}
  303. $CP_TOOL "$IN_DIR/$FN" "$OUT_DIR/$FN"
  304. if [ "$((CUR % 5))" = "0" ]; then
  305. sort -u "$TRACE_DIR/$FN" "$TRACE_DIR/.already_have" >"$TRACE_DIR/.tmp"
  306. mv -f "$TRACE_DIR/.tmp" "$TRACE_DIR/.already_have"
  307. else
  308. cat "$TRACE_DIR/$FN" >>"$TRACE_DIR/.already_have"
  309. fi
  310. done <"$TRACE_DIR/.all_uniq"
  311. echo
  312. OUT_COUNT=`ls -- "$OUT_DIR" | wc -l`
  313. if [ "$OUT_COUNT" = "1" ]; then
  314. echo "[!] WARNING: All test cases had the same traces, check syntax!"
  315. fi
  316. echo "[+] Narrowed down to $OUT_COUNT files, saved in '$OUT_DIR'."
  317. echo
  318. test "$AFL_KEEP_TRACES" = "" && rm -rf "$TRACE_DIR"
  319. exit 0