1 // Copyright 2022 Code Intelligence GmbH 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 package com.example; 16 17 import com.code_intelligence.jazzer.api.Consumer3; 18 import com.code_intelligence.jazzer.api.Jazzer; 19 import java.util.Arrays; 20 import java.util.Objects; 21 import java.util.stream.Collectors; 22 23 // A fuzz target that shows how manually informing the fuzzer about important state can make a fuzz 24 // target much more effective. 25 // This is a Java version of the famous "maze game" discussed in 26 // "IJON: Exploring Deep State Spaces via Fuzzing", available at: 27 // https://wcventure.github.io/FuzzingPaper/Paper/SP20_IJON.pdf 28 public final class MazeFuzzer { 29 private static final String[] MAZE_STRING = new String[] { 30 " ███████████████████", 31 " █ █ █ █ █ █", 32 "█ █ █ █ ███ █ █ █ ███", 33 "█ █ █ █ █ █", 34 "█ █████ ███ ███ █ ███", 35 "█ █ █ █ █ █", 36 "█ ███ ███████ █ ███ █", 37 "█ █ █ █ █ █", 38 "███████ █ █ █████ ███", 39 "█ █ █ █ █", 40 "█ ███████ █ ███ ███ █", 41 "█ █ █ █ █ █ █", 42 "███ ███ █ ███ █ ███ █", 43 "█ █ █ █ █ █", 44 "█ ███████ █ █ █ █ █ █", 45 "█ █ █ █ █ █ █", 46 "█ █ █████████ ███ ███", 47 "█ █ █ █ █ █ █", 48 "█ █ █ ███ █████ ███ █", 49 "█ █ █ ", 50 "███████████████████ #", 51 }; 52 53 private static final char[][] MAZE = parseMaze(); 54 private static final char[][] REACHED_FIELDS = parseMaze(); 55 fuzzerTestOneInput(byte[] commands)56 public static void fuzzerTestOneInput(byte[] commands) { 57 executeCommands(commands, (x, y, won) -> { 58 if (won) { 59 throw new TreasureFoundException(commands); 60 } 61 // This is the key line that makes this fuzz target work: It instructs the fuzzer to track 62 // every new combination of x and y as a new feature. Without it, the fuzzer would be 63 // completely lost in the maze as guessing an escaping path by chance is close to impossible. 64 Jazzer.exploreState((byte) Objects.hash(x, y), 0); 65 if (REACHED_FIELDS[y][x] == ' ') { 66 // Fuzzer reached a new field in the maze, print its progress. 67 REACHED_FIELDS[y][x] = '.'; 68 System.out.println(renderMaze(REACHED_FIELDS)); 69 } 70 }); 71 } 72 73 private static class TreasureFoundException extends RuntimeException { TreasureFoundException(byte[] commands)74 TreasureFoundException(byte[] commands) { 75 super(renderPath(commands)); 76 } 77 } 78 executeCommands(byte[] commands, Consumer3<Byte, Byte, Boolean> callback)79 private static void executeCommands(byte[] commands, Consumer3<Byte, Byte, Boolean> callback) { 80 byte x = 0; 81 byte y = 0; 82 callback.accept(x, y, false); 83 84 for (byte command : commands) { 85 byte nextX = x; 86 byte nextY = y; 87 switch (command) { 88 case 'L': 89 nextX--; 90 break; 91 case 'R': 92 nextX++; 93 break; 94 case 'U': 95 nextY--; 96 break; 97 case 'D': 98 nextY++; 99 break; 100 default: 101 return; 102 } 103 char nextFieldType; 104 try { 105 nextFieldType = MAZE[nextY][nextX]; 106 } catch (IndexOutOfBoundsException e) { 107 // Fuzzer tried to walk through the exterior walls of the maze. 108 continue; 109 } 110 if (nextFieldType != ' ' && nextFieldType != '#') { 111 // Fuzzer tried to walk through the interior walls of the maze. 112 continue; 113 } 114 // Fuzzer performed a valid move. 115 x = nextX; 116 y = nextY; 117 callback.accept(x, y, nextFieldType == '#'); 118 } 119 } 120 parseMaze()121 private static char[][] parseMaze() { 122 return Arrays.stream(MazeFuzzer.MAZE_STRING).map(String::toCharArray).toArray(char[][] ::new); 123 } 124 renderMaze(char[][] maze)125 private static String renderMaze(char[][] maze) { 126 return Arrays.stream(maze).map(String::new).collect(Collectors.joining("\n", "\n", "\n")); 127 } 128 renderPath(byte[] commands)129 private static String renderPath(byte[] commands) { 130 char[][] mutableMaze = parseMaze(); 131 executeCommands(commands, (x, y, won) -> { 132 if (!won) { 133 mutableMaze[y][x] = '.'; 134 } 135 }); 136 return renderMaze(mutableMaze); 137 } 138 } 139