From 0277ce5ac94e37661e1d0b67e4f2e4d70f56ccb1 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 13:43:20 -0800 Subject: [PATCH 01/33] Add LLVM fuzzer harness --- src/apps/applib/include/aflHarness.h | 40 +++++++++++++++++++++++++++ src/apps/fuzzers/fuzzerCellToLatLng.c | 25 +++++++++-------- src/apps/fuzzers/fuzzerGridDisk.c | 31 ++++++++++----------- src/apps/fuzzers/fuzzerLatLngToCell.c | 34 +++++++++++------------ 4 files changed, 84 insertions(+), 46 deletions(-) create mode 100644 src/apps/applib/include/aflHarness.h diff --git a/src/apps/applib/include/aflHarness.h b/src/apps/applib/include/aflHarness.h new file mode 100644 index 0000000000..54c2a9d038 --- /dev/null +++ b/src/apps/applib/include/aflHarness.h @@ -0,0 +1,40 @@ +/* + * Copyright 2021 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file aflHarness.h + * @brief Adapter from LLVM fuzzer to AFL++ + */ +#ifndef AFLHARNESS_H +#define AFLHARNESS_H + +#include "utility.h" + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size); + +#define AFL_HARNESS_MAIN(expectedSize) int main(int argc, char *argv[]) {\ + if (argc != 2) {\ + error("Should have one argument (test case file)\n");\ + }\ + const char *filename = argv[1];\ + FILE *fp = fopen(filename, "rb");\ + uint8_t data[expectedSize];\ + if (fread(&data, expectedSize, 1, fp) != 1) {\ + error("Error reading\n");\ + }\ + fclose(fp);\ + return LLVMFuzzerTestOneInput(data, expectedSize);\ +} + +#endif // AFLHARNESS_H \ No newline at end of file diff --git a/src/apps/fuzzers/fuzzerCellToLatLng.c b/src/apps/fuzzers/fuzzerCellToLatLng.c index 35fba00e08..91a453db1a 100644 --- a/src/apps/fuzzers/fuzzerCellToLatLng.c +++ b/src/apps/fuzzers/fuzzerCellToLatLng.c @@ -17,25 +17,26 @@ * @brief Fuzzer program for cellToLatLng and cellToBoundary */ +#include "aflHarness.h" #include "h3api.h" #include "utility.h" -int main(int argc, char *argv[]) { - if (argc != 2) { - error("Should have one argument (test case file)\n"); - } - const char *filename = argv[1]; - FILE *fp = fopen(filename, "rb"); +typedef struct { H3Index index; - if (fread(&index, sizeof(H3Index), 1, fp) != 1) { - error("Error reading\n"); - } - fclose(fp); +} inputArgs; +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; LatLng geo; - H3_EXPORT(cellToLatLng)(index, &geo); + H3_EXPORT(cellToLatLng)(args->index, &geo); printf("%lf %lf\n", geo.lat, geo.lng); CellBoundary cellBoundary; - H3_EXPORT(cellToBoundary)(index, &cellBoundary); + H3_EXPORT(cellToBoundary)(args->index, &cellBoundary); printf("%d\n", cellBoundary.numVerts); + return 0; } + +AFL_HARNESS_MAIN(sizeof(inputArgs)); diff --git a/src/apps/fuzzers/fuzzerGridDisk.c b/src/apps/fuzzers/fuzzerGridDisk.c index 024166c180..863dc1b11e 100644 --- a/src/apps/fuzzers/fuzzerGridDisk.c +++ b/src/apps/fuzzers/fuzzerGridDisk.c @@ -17,29 +17,28 @@ * @brief Fuzzer program for gridDisk */ +#include "aflHarness.h" #include "h3api.h" #include "utility.h" -int main(int argc, char *argv[]) { - if (argc != 2) { - error("Should have one argument (test case file)\n"); - } - const char *filename = argv[1]; - FILE *fp = fopen(filename, "rb"); - struct { - H3Index index; - int k; - } args; - if (fread(&args, sizeof(args), 1, fp) != 1) { - error("Error reading\n"); - } - fclose(fp); +typedef struct { + H3Index index; + int64_t k; +} inputArgs; - int sz = H3_EXPORT(maxGridDiskSize)(args.k); +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + int64_t sz = H3_EXPORT(maxGridDiskSize)(args->k); H3Index *results = calloc(sizeof(H3Index), sz); if (results != NULL) { - H3_EXPORT(gridDisk)(args.index, args.k, results); + H3_EXPORT(gridDisk)(args->index, args->k, results); h3Println(results[0]); } free(results); + return 0; } + +AFL_HARNESS_MAIN(sizeof(inputArgs)); diff --git a/src/apps/fuzzers/fuzzerLatLngToCell.c b/src/apps/fuzzers/fuzzerLatLngToCell.c index 18141c5369..3b6ae7e108 100644 --- a/src/apps/fuzzers/fuzzerLatLngToCell.c +++ b/src/apps/fuzzers/fuzzerLatLngToCell.c @@ -17,29 +17,27 @@ * @brief Fuzzer program for latLngToCell */ +#include "aflHarness.h" #include "h3api.h" -#include "utility.h" -int main(int argc, char *argv[]) { - if (argc != 2) { - error("Should have one argument (test case file)\n"); - } - const char *filename = argv[1]; - FILE *fp = fopen(filename, "rb"); - struct args { - double lat; - double lng; - int res; - } args; - if (fread(&args, sizeof(args), 1, fp) != 1) { - error("Error reading\n"); - } - fclose(fp); +typedef struct { + double lat; + double lng; + int res; +} inputArgs; - LatLng g = {.lat = args.lat, .lng = args.lng}; +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + LatLng g = {.lat = args->lat, .lng = args->lng}; H3Index h; - H3Error e = H3_EXPORT(latLngToCell)(&g, args.res, &h); + H3Error e = H3_EXPORT(latLngToCell)(&g, args->res, &h); h3Println(e); h3Println(h); + return 0; } + +AFL_HARNESS_MAIN(sizeof(inputArgs)); From 1c8ec2e85c1b9b08435ca183d610ec08306c0876 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 13:48:37 -0800 Subject: [PATCH 02/33] Add AFL++ test case generator --- src/apps/applib/include/aflHarness.h | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) diff --git a/src/apps/applib/include/aflHarness.h b/src/apps/applib/include/aflHarness.h index 54c2a9d038..2c89f77a39 100644 --- a/src/apps/applib/include/aflHarness.h +++ b/src/apps/applib/include/aflHarness.h @@ -20,10 +20,34 @@ #define AFLHARNESS_H #include "utility.h" +#include int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size); +/** + * Generate a AFL++ test case file of the right size initialized to all zeroes. + * + * @param filename + * @param expectedSize + * @return int + */ +int generateTestCase(const char *filename, size_t expectedSize) { + FILE *fp = fopen(filename, "wb"); + uint8_t zero = 0; + if (fwrite(&zero, sizeof(zero), expectedSize, fp) != expectedSize) { + error("Error writing\n"); + } + fclose(fp); + return 0; +} + #define AFL_HARNESS_MAIN(expectedSize) int main(int argc, char *argv[]) {\ + if (argc == 3) {\ + if (strcmp(argv[1], "--generate") != 0) {\ + error("Invalid option (should be --generate, otherwise look at aflHarness.h to see options)");\ + }\ + return generateTestCase(argv[2], expectedSize);\ + }\ if (argc != 2) {\ error("Should have one argument (test case file)\n");\ }\ From b89c76b6fe585ce9db30d0b9707caed3b14c2ab5 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 13:58:09 -0800 Subject: [PATCH 03/33] Fuzz more gridDisk functions --- src/apps/fuzzers/README.md | 24 +++++++++++++--- src/apps/fuzzers/fuzzerGridDisk.c | 46 +++++++++++++++++++++++++++++++ 2 files changed, 66 insertions(+), 4 deletions(-) diff --git a/src/apps/fuzzers/README.md b/src/apps/fuzzers/README.md index 9b80530320..5f27799600 100644 --- a/src/apps/fuzzers/README.md +++ b/src/apps/fuzzers/README.md @@ -11,7 +11,15 @@ apt install afl-clang (There is also an afl-cov which looks interesting but isn't necessary.) -# Usage +# libFuzzer Usage + +[libFuzzer](https://www.llvm.org/docs/LibFuzzer.html) is one of the supported fuzzing drivers. + +This is the fuzzer used in [oss-fuzz](https://github.com/google/oss-fuzz/tree/master/projects/h3). + +# AFL Usage + +[AFL++](https://github.com/AFLplusplus/AFLplusplus) is one of the supported fuzzing drivers. You must compile with the instrumented compiler: @@ -20,15 +28,23 @@ CXX=afl-clang++ CC=afl-clang cmake . make fuzzers ``` +Generate a blank (zeroed) test case file. This will not be very interesting test case but is usedful +for having files of the right size. + +``` +fuzzerLatLngToCell --generate bytes16 +``` + An individual fuzzer run is invoked as follows. The argument is a file containing the number of bytes needed. ``` -fuzzerGeoToH3 bytes24 +fuzzerLatLngToCell bytes16 ``` To begin running the fuzzer, run the following. The testcase directory (`testcase_dir`) should contain a file -with at least the right number of bytes that the fuzzer will read (such as 16 for fuzzerKRing.) +with at least the right number of bytes that the fuzzer will read (this can be generated using the `--generate` +option above.) ``` -afl-fuzz -i testcase_dir -o findings_dir -- fuzzerGeoToH3 @@ +afl-fuzz -i testcase_dir -o findings_dir -- fuzzerLatLngToCell @@ ``` diff --git a/src/apps/fuzzers/fuzzerGridDisk.c b/src/apps/fuzzers/fuzzerGridDisk.c index 863dc1b11e..95dbdb473d 100644 --- a/src/apps/fuzzers/fuzzerGridDisk.c +++ b/src/apps/fuzzers/fuzzerGridDisk.c @@ -32,12 +32,58 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { } const inputArgs *args = (const inputArgs *)data; int64_t sz = H3_EXPORT(maxGridDiskSize)(args->k); + + // gridDisk H3Index *results = calloc(sizeof(H3Index), sz); if (results != NULL) { H3_EXPORT(gridDisk)(args->index, args->k, results); h3Println(results[0]); } free(results); + + results = calloc(sizeof(H3Index), sz); + if (results != NULL) { + H3_EXPORT(gridDiskUnsafe)(args->index, args->k, results); + h3Println(results[0]); + } + free(results); + + // TODO: use int64_t + int *distances = calloc(sizeof(int), sz); + results = calloc(sizeof(H3Index), sz); + if (results != NULL && distances != NULL) { + H3_EXPORT(gridDiskDistancesUnsafe) + (args->index, args->k, results, distances); + h3Println(results[0]); + } + free(results); + free(distances); + + distances = calloc(sizeof(int), sz); + results = calloc(sizeof(H3Index), sz); + if (results != NULL && distances != NULL) { + H3_EXPORT(gridDiskDistancesSafe) + (args->index, args->k, results, distances); + h3Println(results[0]); + } + free(results); + free(distances); + + distances = calloc(sizeof(int), sz); + results = calloc(sizeof(H3Index), sz); + if (results != NULL && distances != NULL) { + H3_EXPORT(gridDiskDistances)(args->index, args->k, results, distances); + h3Println(results[0]); + } + free(results); + free(distances); + + results = calloc(sizeof(H3Index), sz); + if (results != NULL) { + H3_EXPORT(gridRingUnsafe)(args->index, args->k, results); + h3Println(results[0]); + } + free(results); return 0; } From 79d2e2c58dcfafe865fbbb520d03ad6654a07eb8 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 14:01:15 -0800 Subject: [PATCH 04/33] add fuzzerH3SetToLinkedGeo --- CMakeLists.txt | 2 + src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c | 46 +++++++++++++++++++++++ 2 files changed, 48 insertions(+) create mode 100644 src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c diff --git a/CMakeLists.txt b/CMakeLists.txt index a356ad84d2..e4144f9e06 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -219,6 +219,7 @@ set(OTHER_SOURCE_FILES src/apps/fuzzers/fuzzerLatLngToCell.c src/apps/fuzzers/fuzzerCellToLatLng.c src/apps/fuzzers/fuzzerGridDisk.c + src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c src/apps/benchmarks/benchmarkPolygonToCells.c src/apps/benchmarks/benchmarkPolygon.c src/apps/benchmarks/benchmarkH3SetToLinkedGeo.c @@ -641,6 +642,7 @@ if(BUILD_FUZZERS) add_h3_fuzzer(fuzzerLatLngToCell src/apps/fuzzers/fuzzerLatLngToCell.c) add_h3_fuzzer(fuzzerCellToLatLng src/apps/fuzzers/fuzzerCellToLatLng.c) add_h3_fuzzer(fuzzerGridDisk src/apps/fuzzers/fuzzerGridDisk.c) + add_h3_fuzzer(fuzzerH3SetToLinkedGeo src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c) endif() if(BUILD_BENCHMARKS) diff --git a/src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c b/src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c new file mode 100644 index 0000000000..949278abde --- /dev/null +++ b/src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c @@ -0,0 +1,46 @@ +/* + * Copyright 2021 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for gridDisk + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +typedef struct { + H3Index h3Set[1024]; + int sz; +} inputArgs; + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + if (args->sz >= 1024) { + return 0; + } + + LinkedGeoPolygon polygon; + H3Error err = H3_EXPORT(h3SetToLinkedGeo)(args->h3Set, args->sz, &polygon); + if (!err) { + destroyLinkedPolygon(&polygon); + } + return 0; +} + +AFL_HARNESS_MAIN(sizeof(inputArgs)); From a28a80714b822480a0e0334d9614b46cbd9abf28 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 14:16:36 -0800 Subject: [PATCH 05/33] Add more fuzzers --- CMakeLists.txt | 10 +++++ src/apps/fuzzers/functions.md | 51 ++++++++++++++++++++++ src/apps/fuzzers/fuzzerCellArea.c | 41 ++++++++++++++++++ src/apps/fuzzers/fuzzerCellProperties.c | 52 +++++++++++++++++++++++ src/apps/fuzzers/fuzzerDistances.c | 42 ++++++++++++++++++ src/apps/fuzzers/fuzzerExactEdgeLength.c | 45 ++++++++++++++++++++ src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c | 4 +- src/apps/fuzzers/fuzzerIndexIO.c | 49 +++++++++++++++++++++ 8 files changed, 292 insertions(+), 2 deletions(-) create mode 100644 src/apps/fuzzers/functions.md create mode 100644 src/apps/fuzzers/fuzzerCellArea.c create mode 100644 src/apps/fuzzers/fuzzerCellProperties.c create mode 100644 src/apps/fuzzers/fuzzerDistances.c create mode 100644 src/apps/fuzzers/fuzzerExactEdgeLength.c create mode 100644 src/apps/fuzzers/fuzzerIndexIO.c diff --git a/CMakeLists.txt b/CMakeLists.txt index e4144f9e06..1b3197d9d4 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -220,6 +220,11 @@ set(OTHER_SOURCE_FILES src/apps/fuzzers/fuzzerCellToLatLng.c src/apps/fuzzers/fuzzerGridDisk.c src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c + src/apps/fuzzers/fuzzerDistances.c + src/apps/fuzzers/fuzzerCellArea.c + src/apps/fuzzers/fuzzerExactEdgeLength.c + src/apps/fuzzers/fuzzerCellProperties.c + src/apps/fuzzers/fuzzerIndexIO.c src/apps/benchmarks/benchmarkPolygonToCells.c src/apps/benchmarks/benchmarkPolygon.c src/apps/benchmarks/benchmarkH3SetToLinkedGeo.c @@ -643,6 +648,11 @@ if(BUILD_FUZZERS) add_h3_fuzzer(fuzzerCellToLatLng src/apps/fuzzers/fuzzerCellToLatLng.c) add_h3_fuzzer(fuzzerGridDisk src/apps/fuzzers/fuzzerGridDisk.c) add_h3_fuzzer(fuzzerH3SetToLinkedGeo src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c) + add_h3_fuzzer(fuzzerDistances src/apps/fuzzers/fuzzerDistances.c) + add_h3_fuzzer(fuzzerCellArea src/apps/fuzzers/fuzzerCellArea.c) + add_h3_fuzzer(fuzzerExactEdgeLength src/apps/fuzzers/fuzzerExactEdgeLength.c) + add_h3_fuzzer(fuzzerCellProperties src/apps/fuzzers/fuzzerCellProperties.c) + add_h3_fuzzer(fuzzerIndexIO src/apps/fuzzers/fuzzerIndexIO.c) endif() if(BUILD_BENCHMARKS) diff --git a/src/apps/fuzzers/functions.md b/src/apps/fuzzers/functions.md new file mode 100644 index 0000000000..ee77b2a3f2 --- /dev/null +++ b/src/apps/fuzzers/functions.md @@ -0,0 +1,51 @@ +This file is an index to where all the functions in the H3 public API are fuzzed. + +| Function | File or status +| -------- | -------------- +| latLngToCell | [fuzzerLatLngToCell](./fuzzerLatLngToCell.c) +| cellToLatLng | [fuzzerCellToLatLng](./fuzzerCellToLatLng.c) +| cellToBoundary | [fuzzerCellToLatLng](./fuzzerCellToLatLng.c) +| gridDisk | [fuzzerGridDisk](./fuzzerGridDisk.c) +| gridDiskDistances | [fuzzerGridDisk](./fuzzerGridDisk.c) +| gridRingUnsafe | [fuzzerGridDisk](./fuzzerGridDisk.c) +| polygonToCells | +| h3SetToMultiPolygon | [fuzzerH3SetToLinkedGeo](./fuzzerH3SetToLinkedGeo.c) +| degsToRads | Trivial +| radsToDegs | Trivial +| distance | [fuzzerDistances](./fuzzerDistances.c) +| getHexagonAreaAvg | Trivial +| cellArea | [fuzzerCellArea](./fuzzerCellArea.c) +| getHexagonEdgeLengthAvg | +| exactEdgeLength | [fuzzerExactEdgeLength](./fuzzerExactEdgeLength.c) +| getNumCells | Trivial +| getRes0Cells | Trivial +| getPentagons | +| getResolution | [fuzzerCellProperties](./fuzzerCellProperties.c) +| getBaseCellNumber | [fuzzerCellProperties](./fuzzerCellProperties.c) +| stringToH3 | [fuzzerIndexIO](./fuzzerIndexIO.c) +| h3ToString | [fuzzerIndexIO](./fuzzerIndexIO.c) +| isValidCell | [fuzzerCellProperties](./fuzzerCellProperties.c) +| cellToParent | +| cellToChildren | +| cellToCenterChild | +| compactCells | +| uncompactCells | +| isResClassIII | [fuzzerCellProperties](./fuzzerCellProperties.c) +| isPentagon | [fuzzerCellProperties](./fuzzerCellProperties.c) +| getIcosahedronFaces | [fuzzerCellProperties](./fuzzerCellProperties.c) +| areNeighborCells | +| cellsToDirectedEdge | +| isValidDirectedEdge | +| getDirectedEdgeOrigin | +| getDirectedEdgeDestination | +| directedEdgeToCells | +| originToDirectedEdges | +| directedEdgeToBoundary | +| cellToVertex | +| cellToVertexes | +| vertexToLatLng | +| isValidVertex | +| gridDistance | +| gridPathCells | +| experimentalH3ToLocalIj | +| experimentalLocalIjToH3 | \ No newline at end of file diff --git a/src/apps/fuzzers/fuzzerCellArea.c b/src/apps/fuzzers/fuzzerCellArea.c new file mode 100644 index 0000000000..d1ec774e1a --- /dev/null +++ b/src/apps/fuzzers/fuzzerCellArea.c @@ -0,0 +1,41 @@ +/* + * Copyright 2021 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for cellAreaRads2 + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +typedef struct { + H3Index index; +} inputArgs; + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + + printf("%f", H3_EXPORT(cellAreaRads2)(&args->index)); + printf("%f", H3_EXPORT(cellAreaKm2)(&args->index)); + printf("%f", H3_EXPORT(cellAreaM2)(&args->index)); + + return 0; +} + +AFL_HARNESS_MAIN(sizeof(inputArgs)); diff --git a/src/apps/fuzzers/fuzzerCellProperties.c b/src/apps/fuzzers/fuzzerCellProperties.c new file mode 100644 index 0000000000..da5632ba0d --- /dev/null +++ b/src/apps/fuzzers/fuzzerCellProperties.c @@ -0,0 +1,52 @@ +/* + * Copyright 2021 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for cell property functions + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +typedef struct { + H3Index index; +} inputArgs; + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + + printf("%d", H3_EXPORT(getResolution)(args->index)); + printf("%d", H3_EXPORT(getBaseCellNumber)(args->index)); + printf("%d", H3_EXPORT(isValidCell)(args->index)); + printf("%d", H3_EXPORT(isPentagon)(args->index)); + printf("%d", H3_EXPORT(isResClassIII)(args->index)); + + int faceCount; + H3Error err = H3_EXPORT(maxFaceCount)(args->index, &faceCount); + if (!err && faceCount > 0) { + int *out = calloc(faceCount, sizeof(int)); + H3_EXPORT(getIcosahedronFaces)(args->index, out); + printf("%d", out[0]); + free(out); + } + + return 0; +} + +AFL_HARNESS_MAIN(sizeof(inputArgs)); diff --git a/src/apps/fuzzers/fuzzerDistances.c b/src/apps/fuzzers/fuzzerDistances.c new file mode 100644 index 0000000000..9467ad644e --- /dev/null +++ b/src/apps/fuzzers/fuzzerDistances.c @@ -0,0 +1,42 @@ +/* + * Copyright 2021 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for distanceRads + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +typedef struct { + LatLng a; + LatLng b; +} inputArgs; + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + + printf("%f", H3_EXPORT(distanceRads)(&args->a, &args->b)); + printf("%f", H3_EXPORT(distanceKm)(&args->a, &args->b)); + printf("%f", H3_EXPORT(distanceM)(&args->a, &args->b)); + + return 0; +} + +AFL_HARNESS_MAIN(sizeof(inputArgs)); diff --git a/src/apps/fuzzers/fuzzerExactEdgeLength.c b/src/apps/fuzzers/fuzzerExactEdgeLength.c new file mode 100644 index 0000000000..fe4fb555c2 --- /dev/null +++ b/src/apps/fuzzers/fuzzerExactEdgeLength.c @@ -0,0 +1,45 @@ +/* + * Copyright 2021 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for exactEdgeLengthRads + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +typedef struct { + H3Index index; +} inputArgs; + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + + double distance; + H3_EXPORT(exactEdgeLengthRads)(args->index, &distance); + printf("%f", distance); + H3_EXPORT(exactEdgeLengthKm)(args->index, &distance); + printf("%f", distance); + H3_EXPORT(exactEdgeLengthM)(args->index, &distance); + printf("%f", distance); + + return 0; +} + +AFL_HARNESS_MAIN(sizeof(inputArgs)); diff --git a/src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c b/src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c index 949278abde..27a9b38d4b 100644 --- a/src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c +++ b/src/apps/fuzzers/fuzzerH3SetToLinkedGeo.c @@ -14,7 +14,7 @@ * limitations under the License. */ /** @file - * @brief Fuzzer program for gridDisk + * @brief Fuzzer program for h3SetToLinkedGeo */ #include "aflHarness.h" @@ -38,7 +38,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { LinkedGeoPolygon polygon; H3Error err = H3_EXPORT(h3SetToLinkedGeo)(args->h3Set, args->sz, &polygon); if (!err) { - destroyLinkedPolygon(&polygon); + H3_EXPORT(destroyLinkedPolygon)(&polygon); } return 0; } diff --git a/src/apps/fuzzers/fuzzerIndexIO.c b/src/apps/fuzzers/fuzzerIndexIO.c new file mode 100644 index 0000000000..0ca84f3827 --- /dev/null +++ b/src/apps/fuzzers/fuzzerIndexIO.c @@ -0,0 +1,49 @@ +/* + * Copyright 2021 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for h3ToString and stringToH3 + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +#define STRING_LENGTH 1024 + +typedef struct { + H3Index index; + char str[1024]; +} inputArgs; + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + inputArgs *args = (inputArgs *)data; + args->str[STRING_LENGTH - 1] = 0; + + char str[STRING_LENGTH]; + h3Println(H3_EXPORT(h3ToString)(&args->index, str, STRING_LENGTH)); + H3Index index; + H3Error err = H3_EXPORT(stringToH3)(&args->str, &index); + if (!err) { + h3Println(index); + } + + return 0; +} + +AFL_HARNESS_MAIN(sizeof(inputArgs)); From 9445cbb32af6d892d1e9cc94313e9b9240cf53e7 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 14:36:29 -0800 Subject: [PATCH 06/33] Additional fuzzers --- CMakeLists.txt | 4 ++ src/apps/fuzzers/functions.md | 10 ++--- src/apps/fuzzers/fuzzerCellArea.c | 6 +-- src/apps/fuzzers/fuzzerHierarchy.c | 61 ++++++++++++++++++++++++++++ src/apps/fuzzers/fuzzerResolutions.c | 48 ++++++++++++++++++++++ 5 files changed, 121 insertions(+), 8 deletions(-) create mode 100644 src/apps/fuzzers/fuzzerHierarchy.c create mode 100644 src/apps/fuzzers/fuzzerResolutions.c diff --git a/CMakeLists.txt b/CMakeLists.txt index 1b3197d9d4..f1b5796f55 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -225,6 +225,8 @@ set(OTHER_SOURCE_FILES src/apps/fuzzers/fuzzerExactEdgeLength.c src/apps/fuzzers/fuzzerCellProperties.c src/apps/fuzzers/fuzzerIndexIO.c + src/apps/fuzzers/fuzzerResolutions.c + src/apps/fuzzers/fuzzerHierarchy.c src/apps/benchmarks/benchmarkPolygonToCells.c src/apps/benchmarks/benchmarkPolygon.c src/apps/benchmarks/benchmarkH3SetToLinkedGeo.c @@ -653,6 +655,8 @@ if(BUILD_FUZZERS) add_h3_fuzzer(fuzzerExactEdgeLength src/apps/fuzzers/fuzzerExactEdgeLength.c) add_h3_fuzzer(fuzzerCellProperties src/apps/fuzzers/fuzzerCellProperties.c) add_h3_fuzzer(fuzzerIndexIO src/apps/fuzzers/fuzzerIndexIO.c) + add_h3_fuzzer(fuzzerResolutions src/apps/fuzzers/fuzzerResolutions.c) + add_h3_fuzzer(fuzzerHierarchy src/apps/fuzzers/fuzzerHierarchy.c) endif() if(BUILD_BENCHMARKS) diff --git a/src/apps/fuzzers/functions.md b/src/apps/fuzzers/functions.md index ee77b2a3f2..586dc8af6f 100644 --- a/src/apps/fuzzers/functions.md +++ b/src/apps/fuzzers/functions.md @@ -15,19 +15,19 @@ This file is an index to where all the functions in the H3 public API are fuzzed | distance | [fuzzerDistances](./fuzzerDistances.c) | getHexagonAreaAvg | Trivial | cellArea | [fuzzerCellArea](./fuzzerCellArea.c) -| getHexagonEdgeLengthAvg | +| getHexagonEdgeLengthAvg | Trivial | exactEdgeLength | [fuzzerExactEdgeLength](./fuzzerExactEdgeLength.c) | getNumCells | Trivial | getRes0Cells | Trivial -| getPentagons | +| getPentagons | [fuzzerResolutions](./fuzzerResolutions.c) | getResolution | [fuzzerCellProperties](./fuzzerCellProperties.c) | getBaseCellNumber | [fuzzerCellProperties](./fuzzerCellProperties.c) | stringToH3 | [fuzzerIndexIO](./fuzzerIndexIO.c) | h3ToString | [fuzzerIndexIO](./fuzzerIndexIO.c) | isValidCell | [fuzzerCellProperties](./fuzzerCellProperties.c) -| cellToParent | -| cellToChildren | -| cellToCenterChild | +| cellToParent | [fuzzerHierarchy](./fuzzerHierarchy.c) +| cellToChildren | [fuzzerHierarchy](./fuzzerHierarchy.c) +| cellToCenterChild | [fuzzerHierarchy](./fuzzerHierarchy.c) | compactCells | | uncompactCells | | isResClassIII | [fuzzerCellProperties](./fuzzerCellProperties.c) diff --git a/src/apps/fuzzers/fuzzerCellArea.c b/src/apps/fuzzers/fuzzerCellArea.c index d1ec774e1a..569a135ad1 100644 --- a/src/apps/fuzzers/fuzzerCellArea.c +++ b/src/apps/fuzzers/fuzzerCellArea.c @@ -31,9 +31,9 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { } const inputArgs *args = (const inputArgs *)data; - printf("%f", H3_EXPORT(cellAreaRads2)(&args->index)); - printf("%f", H3_EXPORT(cellAreaKm2)(&args->index)); - printf("%f", H3_EXPORT(cellAreaM2)(&args->index)); + printf("%f", H3_EXPORT(cellAreaRads2)(args->index)); + printf("%f", H3_EXPORT(cellAreaKm2)(args->index)); + printf("%f", H3_EXPORT(cellAreaM2)(args->index)); return 0; } diff --git a/src/apps/fuzzers/fuzzerHierarchy.c b/src/apps/fuzzers/fuzzerHierarchy.c new file mode 100644 index 0000000000..b309dce54d --- /dev/null +++ b/src/apps/fuzzers/fuzzerHierarchy.c @@ -0,0 +1,61 @@ +/* + * Copyright 2021 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for cellToLatLng and cellToBoundary + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +#define MAX_CHILDREN_DIFF 10 + +typedef struct { + H3Index index; + int parentRes; + int childRes; +} inputArgs; + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + + H3Index parent; + H3_EXPORT(cellToParent)(args->index, args->parentRes, &parent); + h3Println(parent); + + // TODO: Update with new API + H3Index child = H3_EXPORT(cellToCenterChild)(args->index, args->childRes); + h3Println(child); + + int resDiff = args->childRes - H3_EXPORT(getResolution)(args->index); + if (resDiff < MAX_CHILDREN_DIFF) { + int64_t childrenSize; + H3Error err = H3_EXPORT(cellToChildrenSize)(args->index, args->childRes, + &childrenSize); + if (!err) { + H3Index *children = calloc(childrenSize, sizeof(H3Index)); + H3_EXPORT(cellToChildren)(args->index, args->childRes, children); + h3Println(children[0]); + free(children); + } + } + return 0; +} + +AFL_HARNESS_MAIN(sizeof(inputArgs)); diff --git a/src/apps/fuzzers/fuzzerResolutions.c b/src/apps/fuzzers/fuzzerResolutions.c new file mode 100644 index 0000000000..6cd925fefa --- /dev/null +++ b/src/apps/fuzzers/fuzzerResolutions.c @@ -0,0 +1,48 @@ +/* + * Copyright 2021 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for resolution specific functions + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +typedef struct { + int res; +} inputArgs; + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + + // Do not perform bound checks + // printf("%f", H3_EXPORT(getHexagonAreaAvgKm2)(args->res)); + // printf("%f", H3_EXPORT(getHexagonAreaAvgM2)(args->res)); + // printf("%f", H3_EXPORT(getHexagonEdgeLengthAvgKm)(args->res)); + // printf("%f", H3_EXPORT(getHexagonEdgeLengthAvgM)(args->res)); + // printf("%llx", H3_EXPORT(getNumCells)(args->res)); + + H3Index pentagons[12]; + H3_EXPORT(getPentagons)(args->res, pentagons); + h3Println(pentagons[0]); + + return 0; +} + +AFL_HARNESS_MAIN(sizeof(inputArgs)); From f971dcfde1b45a7886b26d0ac16bf1da2c14a92b Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 14:40:36 -0800 Subject: [PATCH 07/33] add fuzzerVertexes --- CMakeLists.txt | 2 ++ src/apps/fuzzers/functions.md | 8 ++--- src/apps/fuzzers/fuzzerHierarchy.c | 2 +- src/apps/fuzzers/fuzzerVertexes.c | 48 ++++++++++++++++++++++++++++++ 4 files changed, 55 insertions(+), 5 deletions(-) create mode 100644 src/apps/fuzzers/fuzzerVertexes.c diff --git a/CMakeLists.txt b/CMakeLists.txt index f1b5796f55..fba5a8b7db 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -227,6 +227,7 @@ set(OTHER_SOURCE_FILES src/apps/fuzzers/fuzzerIndexIO.c src/apps/fuzzers/fuzzerResolutions.c src/apps/fuzzers/fuzzerHierarchy.c + src/apps/fuzzers/fuzzerVertexes.c src/apps/benchmarks/benchmarkPolygonToCells.c src/apps/benchmarks/benchmarkPolygon.c src/apps/benchmarks/benchmarkH3SetToLinkedGeo.c @@ -657,6 +658,7 @@ if(BUILD_FUZZERS) add_h3_fuzzer(fuzzerIndexIO src/apps/fuzzers/fuzzerIndexIO.c) add_h3_fuzzer(fuzzerResolutions src/apps/fuzzers/fuzzerResolutions.c) add_h3_fuzzer(fuzzerHierarchy src/apps/fuzzers/fuzzerHierarchy.c) + add_h3_fuzzer(fuzzerVertexes src/apps/fuzzers/fuzzerVertexes.c) endif() if(BUILD_BENCHMARKS) diff --git a/src/apps/fuzzers/functions.md b/src/apps/fuzzers/functions.md index 586dc8af6f..383693a17a 100644 --- a/src/apps/fuzzers/functions.md +++ b/src/apps/fuzzers/functions.md @@ -41,10 +41,10 @@ This file is an index to where all the functions in the H3 public API are fuzzed | directedEdgeToCells | | originToDirectedEdges | | directedEdgeToBoundary | -| cellToVertex | -| cellToVertexes | -| vertexToLatLng | -| isValidVertex | +| cellToVertex | [fuzzerVertexes](./fuzzerVertexes.c) +| cellToVertexes | [fuzzerVertexes](./fuzzerVertexes.c) +| vertexToLatLng | [fuzzerVertexes](./fuzzerVertexes.c) +| isValidVertex | [fuzzerVertexes](./fuzzerVertexes.c) | gridDistance | | gridPathCells | | experimentalH3ToLocalIj | diff --git a/src/apps/fuzzers/fuzzerHierarchy.c b/src/apps/fuzzers/fuzzerHierarchy.c index b309dce54d..6cb201aaaf 100644 --- a/src/apps/fuzzers/fuzzerHierarchy.c +++ b/src/apps/fuzzers/fuzzerHierarchy.c @@ -14,7 +14,7 @@ * limitations under the License. */ /** @file - * @brief Fuzzer program for cellToLatLng and cellToBoundary + * @brief Fuzzer program for cellToParent and cellToChildren functions */ #include "aflHarness.h" diff --git a/src/apps/fuzzers/fuzzerVertexes.c b/src/apps/fuzzers/fuzzerVertexes.c new file mode 100644 index 0000000000..e83daa3d68 --- /dev/null +++ b/src/apps/fuzzers/fuzzerVertexes.c @@ -0,0 +1,48 @@ +/* + * Copyright 2021 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for cellToVertex and related functions + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +typedef struct { + H3Index index; + int vertexNum; +} inputArgs; + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + + H3Index out; + H3_EXPORT(cellToVertex)(args->index, args->vertexNum, &out); + h3Println(out); + H3Index outArr[6]; + H3_EXPORT(cellToVertexes)(args->index, outArr); + h3Println(outArr[0]); + LatLng geo; + H3_EXPORT(vertexToLatLng)(args->index, &geo); + printf("%lf %lf\n", geo.lat, geo.lng); + printf("%d\n", H3_EXPORT(isValidVertex)(args->index)); + return 0; +} + +AFL_HARNESS_MAIN(sizeof(inputArgs)); From e0c8841cd7effa70bbab544390a2d7585ecd20cd Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 14:48:49 -0800 Subject: [PATCH 08/33] Add test-fuzzer script --- .github/workflows/test-fuzzer.yml | 42 +++++++++++++++++++++++++++++++ src/apps/fuzzers/README.md | 4 +-- 2 files changed, 44 insertions(+), 2 deletions(-) create mode 100644 .github/workflows/test-fuzzer.yml diff --git a/.github/workflows/test-fuzzer.yml b/.github/workflows/test-fuzzer.yml new file mode 100644 index 0000000000..6ced437e63 --- /dev/null +++ b/.github/workflows/test-fuzzer.yml @@ -0,0 +1,42 @@ +name: test-fuzzer + +on: + push: + branches: [master, stable-*] + pull_request: + branches: [master, stable-*] + +jobs: + tests: + name: Fuzzer Compilation ${{ matrix.compiler }} + runs-on: ubuntu-latest + env: + CC: ${{ matrix.compiler }} + + strategy: + matrix: + compiler: [clang, gcc] + + steps: + - uses: actions/[email protected] + + - name: Configure build + run: | + mkdir build + cd build + cmake -DCMAKE_BUILD_TYPE=Release .. + + - name: Build + run: | + cd build + make fuzzers + + - name: Run fuzzers once + run: | + cd build + for fuzzer in bin/fuzzers*; do + echo $fuzzer + $fuzzer --generate inputData + $fuzzer inputData + done + make benchmarks diff --git a/src/apps/fuzzers/README.md b/src/apps/fuzzers/README.md index 5f27799600..becb2882cd 100644 --- a/src/apps/fuzzers/README.md +++ b/src/apps/fuzzers/README.md @@ -32,13 +32,13 @@ Generate a blank (zeroed) test case file. This will not be very interesting test for having files of the right size. ``` -fuzzerLatLngToCell --generate bytes16 +fuzzerLatLngToCell --generate bytes24 ``` An individual fuzzer run is invoked as follows. The argument is a file containing the number of bytes needed. ``` -fuzzerLatLngToCell bytes16 +fuzzerLatLngToCell bytes24 ``` To begin running the fuzzer, run the following. The testcase directory (`testcase_dir`) should contain a file From 007b7c31006e84d393a1583b691307167b762ff9 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 14:51:57 -0800 Subject: [PATCH 09/33] Fix linux build --- src/apps/applib/include/aflHarness.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/apps/applib/include/aflHarness.h b/src/apps/applib/include/aflHarness.h index 2c89f77a39..55a0affa72 100644 --- a/src/apps/applib/include/aflHarness.h +++ b/src/apps/applib/include/aflHarness.h @@ -20,7 +20,7 @@ #define AFLHARNESS_H #include "utility.h" -#include +#include int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size); From 02abb9980337bd010acc100ded661266e23b15fe Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 14:54:42 -0800 Subject: [PATCH 10/33] Fix fuzzerIndexIO --- src/apps/fuzzers/fuzzerIndexIO.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/apps/fuzzers/fuzzerIndexIO.c b/src/apps/fuzzers/fuzzerIndexIO.c index 0ca84f3827..6916436ac9 100644 --- a/src/apps/fuzzers/fuzzerIndexIO.c +++ b/src/apps/fuzzers/fuzzerIndexIO.c @@ -36,9 +36,9 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { args->str[STRING_LENGTH - 1] = 0; char str[STRING_LENGTH]; - h3Println(H3_EXPORT(h3ToString)(&args->index, str, STRING_LENGTH)); + h3Println(H3_EXPORT(h3ToString)(args->index, str, STRING_LENGTH)); H3Index index; - H3Error err = H3_EXPORT(stringToH3)(&args->str, &index); + H3Error err = H3_EXPORT(stringToH3)(args->str, &index); if (!err) { h3Println(index); } From caedc908db3bdf9114be033f29e1f29879069228 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 15:11:33 -0800 Subject: [PATCH 11/33] test-fuzzer use subshell for ls --- .github/workflows/test-fuzzer.yml | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/.github/workflows/test-fuzzer.yml b/.github/workflows/test-fuzzer.yml index 6ced437e63..61e25c08cc 100644 --- a/.github/workflows/test-fuzzer.yml +++ b/.github/workflows/test-fuzzer.yml @@ -34,7 +34,7 @@ jobs: - name: Run fuzzers once run: | cd build - for fuzzer in bin/fuzzers*; do + for fuzzer in $(ls bin/fuzzers*); do echo $fuzzer $fuzzer --generate inputData $fuzzer inputData From de5a2c3e0c7b6c8bbd8d30af4fa9fe5b9bc285a6 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 15:17:15 -0800 Subject: [PATCH 12/33] Update test-fuzzer again --- .github/workflows/test-fuzzer.yml | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/.github/workflows/test-fuzzer.yml b/.github/workflows/test-fuzzer.yml index 61e25c08cc..cf0bb8217f 100644 --- a/.github/workflows/test-fuzzer.yml +++ b/.github/workflows/test-fuzzer.yml @@ -34,9 +34,8 @@ jobs: - name: Run fuzzers once run: | cd build - for fuzzer in $(ls bin/fuzzers*); do + for fuzzer in `ls bin/fuzzers*`; do echo $fuzzer $fuzzer --generate inputData $fuzzer inputData done - make benchmarks From 8bbc36a36d62045d91d0ef4666755a37e4d33dd3 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 15:18:24 -0800 Subject: [PATCH 13/33] Fix test-fuzzer again --- .github/workflows/test-fuzzer.yml | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/.github/workflows/test-fuzzer.yml b/.github/workflows/test-fuzzer.yml index cf0bb8217f..a83ab84b5f 100644 --- a/.github/workflows/test-fuzzer.yml +++ b/.github/workflows/test-fuzzer.yml @@ -34,7 +34,7 @@ jobs: - name: Run fuzzers once run: | cd build - for fuzzer in `ls bin/fuzzers*`; do + for fuzzer in bin/fuzzer*; do echo $fuzzer $fuzzer --generate inputData $fuzzer inputData From 021c9948b38abe06a8ee03e5d4f4f60ccddcecdc Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 21:17:59 -0800 Subject: [PATCH 14/33] fuzzerCompact --- CMakeLists.txt | 2 + src/apps/fuzzers/functions.md | 4 +- src/apps/fuzzers/fuzzerCompact.c | 76 ++++++++++++++++++++++++++++++++ src/apps/fuzzers/fuzzerIndexIO.c | 4 +- 4 files changed, 82 insertions(+), 4 deletions(-) create mode 100644 src/apps/fuzzers/fuzzerCompact.c diff --git a/CMakeLists.txt b/CMakeLists.txt index fba5a8b7db..b7ad1045dd 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -228,6 +228,7 @@ set(OTHER_SOURCE_FILES src/apps/fuzzers/fuzzerResolutions.c src/apps/fuzzers/fuzzerHierarchy.c src/apps/fuzzers/fuzzerVertexes.c + src/apps/fuzzers/fuzzerCompact.c src/apps/benchmarks/benchmarkPolygonToCells.c src/apps/benchmarks/benchmarkPolygon.c src/apps/benchmarks/benchmarkH3SetToLinkedGeo.c @@ -659,6 +660,7 @@ if(BUILD_FUZZERS) add_h3_fuzzer(fuzzerResolutions src/apps/fuzzers/fuzzerResolutions.c) add_h3_fuzzer(fuzzerHierarchy src/apps/fuzzers/fuzzerHierarchy.c) add_h3_fuzzer(fuzzerVertexes src/apps/fuzzers/fuzzerVertexes.c) + add_h3_fuzzer(fuzzerCompact src/apps/fuzzers/fuzzerCompact.c) endif() if(BUILD_BENCHMARKS) diff --git a/src/apps/fuzzers/functions.md b/src/apps/fuzzers/functions.md index 383693a17a..deb2a95741 100644 --- a/src/apps/fuzzers/functions.md +++ b/src/apps/fuzzers/functions.md @@ -28,8 +28,8 @@ This file is an index to where all the functions in the H3 public API are fuzzed | cellToParent | [fuzzerHierarchy](./fuzzerHierarchy.c) | cellToChildren | [fuzzerHierarchy](./fuzzerHierarchy.c) | cellToCenterChild | [fuzzerHierarchy](./fuzzerHierarchy.c) -| compactCells | -| uncompactCells | +| compactCells | [fuzzerCompact](./fuzzerCompact.c) +| uncompactCells | [fuzzerCompact](./fuzzerCompact.c) | isResClassIII | [fuzzerCellProperties](./fuzzerCellProperties.c) | isPentagon | [fuzzerCellProperties](./fuzzerCellProperties.c) | getIcosahedronFaces | [fuzzerCellProperties](./fuzzerCellProperties.c) diff --git a/src/apps/fuzzers/fuzzerCompact.c b/src/apps/fuzzers/fuzzerCompact.c new file mode 100644 index 0000000000..32ef261bf2 --- /dev/null +++ b/src/apps/fuzzers/fuzzerCompact.c @@ -0,0 +1,76 @@ +/* + * Copyright 2021 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for compactCells and uncompactCells + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(H3Index) + 1) { + return 0; + } + + uint8_t res = *data; + H3Index *input = (H3Index *)(data + 1); + size_t inputSize = (size - 1) / sizeof(H3Index); + + // fuzz compactCells + H3Index *compacted = calloc(inputSize, sizeof(H3Index)); + H3_EXPORT(compactCells)(input, compacted, inputSize); + h3Println(compacted[0]); + + // fuzz uncompactCells using output of above + int compactedCount = 0; + for (int i = 0; i < inputSize; i++) { + if (compacted[i] != H3_NULL) { + compactedCount++; + } + } + if (compactedCount < 2) { + int uncompactRes = 10; + int64_t uncompactedSize; + H3Error err = H3_EXPORT(uncompactCellsSize)( + compacted, inputSize, uncompactRes, &uncompactedSize); + if (!err) { + H3Index *uncompacted = calloc(uncompactedSize, sizeof(H3Index)); + H3_EXPORT(uncompactCells) + (compacted, compactedCount, uncompacted, uncompactedSize, + uncompactRes); + h3Println(uncompacted[0]); + free(uncompacted); + } + } + + // fuzz uncompactCells using the original input + int64_t uncompactedSize; + H3Error err = H3_EXPORT(uncompactCellsSize)(compacted, inputSize, res, + &uncompactedSize); + + if (!err) { + H3Index *uncompacted = calloc(uncompactedSize, sizeof(H3Index)); + H3_EXPORT(uncompactCells) + (compacted, compactedCount, uncompacted, uncompactedSize, res); + h3Println(uncompacted[0]); + free(uncompacted); + } + + return 0; +} + +AFL_HARNESS_MAIN(sizeof(H3Index) * 1024); diff --git a/src/apps/fuzzers/fuzzerIndexIO.c b/src/apps/fuzzers/fuzzerIndexIO.c index 6916436ac9..d7fd55af16 100644 --- a/src/apps/fuzzers/fuzzerIndexIO.c +++ b/src/apps/fuzzers/fuzzerIndexIO.c @@ -21,11 +21,11 @@ #include "h3api.h" #include "utility.h" -#define STRING_LENGTH 1024 +#define STRING_LENGTH 32 typedef struct { H3Index index; - char str[1024]; + char str[STRING_LENGTH]; } inputArgs; int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { From 2195863515cb70a6c3fc38cba4e45f78a9e61629 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Wed, 22 Dec 2021 21:23:39 -0800 Subject: [PATCH 15/33] Update readme --- src/apps/fuzzers/README.md | 76 ++++++++++++++++++++++++++++++----- src/apps/fuzzers/functions.md | 51 ----------------------- 2 files changed, 67 insertions(+), 60 deletions(-) delete mode 100644 src/apps/fuzzers/functions.md diff --git a/src/apps/fuzzers/README.md b/src/apps/fuzzers/README.md index becb2882cd..fbdab008aa 100644 --- a/src/apps/fuzzers/README.md +++ b/src/apps/fuzzers/README.md @@ -1,15 +1,61 @@ # Fuzzer harnesses for H3 This directory contains helper programs for testing the H3 library using the -''[American fuzzy lop](https://lcamtuf.coredump.cx/afl/)'' fuzzer. - -# Installation - -``` -apt install afl-clang -``` - -(There is also an afl-cov which looks interesting but isn't necessary.) +''[American fuzzy lop](https://lcamtuf.coredump.cx/afl/)'' or ''libFuzzer'' fuzzers. +Fuzzering is a technique for discovering crashes and other edge cases in code +such as the H3 core library. + +# Function coverage + +| Function | File or status +| -------- | -------------- +| latLngToCell | [fuzzerLatLngToCell](./fuzzerLatLngToCell.c) +| cellToLatLng | [fuzzerCellToLatLng](./fuzzerCellToLatLng.c) +| cellToBoundary | [fuzzerCellToLatLng](./fuzzerCellToLatLng.c) +| gridDisk | [fuzzerGridDisk](./fuzzerGridDisk.c) +| gridDiskDistances | [fuzzerGridDisk](./fuzzerGridDisk.c) +| gridRingUnsafe | [fuzzerGridDisk](./fuzzerGridDisk.c) +| polygonToCells | +| h3SetToMultiPolygon | [fuzzerH3SetToLinkedGeo](./fuzzerH3SetToLinkedGeo.c) +| degsToRads | Trivial +| radsToDegs | Trivial +| distance | [fuzzerDistances](./fuzzerDistances.c) +| getHexagonAreaAvg | Trivial +| cellArea | [fuzzerCellArea](./fuzzerCellArea.c) +| getHexagonEdgeLengthAvg | Trivial +| exactEdgeLength | [fuzzerExactEdgeLength](./fuzzerExactEdgeLength.c) +| getNumCells | Trivial +| getRes0Cells | Trivial +| getPentagons | [fuzzerResolutions](./fuzzerResolutions.c) +| getResolution | [fuzzerCellProperties](./fuzzerCellProperties.c) +| getBaseCellNumber | [fuzzerCellProperties](./fuzzerCellProperties.c) +| stringToH3 | [fuzzerIndexIO](./fuzzerIndexIO.c) +| h3ToString | [fuzzerIndexIO](./fuzzerIndexIO.c) +| isValidCell | [fuzzerCellProperties](./fuzzerCellProperties.c) +| cellToParent | [fuzzerHierarchy](./fuzzerHierarchy.c) +| cellToChildren | [fuzzerHierarchy](./fuzzerHierarchy.c) +| cellToCenterChild | [fuzzerHierarchy](./fuzzerHierarchy.c) +| compactCells | [fuzzerCompact](./fuzzerCompact.c) +| uncompactCells | [fuzzerCompact](./fuzzerCompact.c) +| isResClassIII | [fuzzerCellProperties](./fuzzerCellProperties.c) +| isPentagon | [fuzzerCellProperties](./fuzzerCellProperties.c) +| getIcosahedronFaces | [fuzzerCellProperties](./fuzzerCellProperties.c) +| areNeighborCells | +| cellsToDirectedEdge | +| isValidDirectedEdge | +| getDirectedEdgeOrigin | +| getDirectedEdgeDestination | +| directedEdgeToCells | +| originToDirectedEdges | +| directedEdgeToBoundary | +| cellToVertex | [fuzzerVertexes](./fuzzerVertexes.c) +| cellToVertexes | [fuzzerVertexes](./fuzzerVertexes.c) +| vertexToLatLng | [fuzzerVertexes](./fuzzerVertexes.c) +| isValidVertex | [fuzzerVertexes](./fuzzerVertexes.c) +| gridDistance | +| gridPathCells | +| experimentalH3ToLocalIj | +| experimentalLocalIjToH3 | # libFuzzer Usage @@ -21,6 +67,16 @@ This is the fuzzer used in [oss-fuzz](https://github.com/google/oss-fuzz/tree/ma [AFL++](https://github.com/AFLplusplus/AFLplusplus) is one of the supported fuzzing drivers. +## Installation + +``` +apt install afl-clang +``` + +(There is also an afl-cov which looks interesting but isn't necessary.) + +## Build + You must compile with the instrumented compiler: ``` @@ -41,6 +97,8 @@ An individual fuzzer run is invoked as follows. The argument is a file containin fuzzerLatLngToCell bytes24 ``` +## Run + To begin running the fuzzer, run the following. The testcase directory (`testcase_dir`) should contain a file with at least the right number of bytes that the fuzzer will read (this can be generated using the `--generate` option above.) diff --git a/src/apps/fuzzers/functions.md b/src/apps/fuzzers/functions.md deleted file mode 100644 index deb2a95741..0000000000 --- a/src/apps/fuzzers/functions.md +++ /dev/null @@ -1,51 +0,0 @@ -This file is an index to where all the functions in the H3 public API are fuzzed. - -| Function | File or status -| -------- | -------------- -| latLngToCell | [fuzzerLatLngToCell](./fuzzerLatLngToCell.c) -| cellToLatLng | [fuzzerCellToLatLng](./fuzzerCellToLatLng.c) -| cellToBoundary | [fuzzerCellToLatLng](./fuzzerCellToLatLng.c) -| gridDisk | [fuzzerGridDisk](./fuzzerGridDisk.c) -| gridDiskDistances | [fuzzerGridDisk](./fuzzerGridDisk.c) -| gridRingUnsafe | [fuzzerGridDisk](./fuzzerGridDisk.c) -| polygonToCells | -| h3SetToMultiPolygon | [fuzzerH3SetToLinkedGeo](./fuzzerH3SetToLinkedGeo.c) -| degsToRads | Trivial -| radsToDegs | Trivial -| distance | [fuzzerDistances](./fuzzerDistances.c) -| getHexagonAreaAvg | Trivial -| cellArea | [fuzzerCellArea](./fuzzerCellArea.c) -| getHexagonEdgeLengthAvg | Trivial -| exactEdgeLength | [fuzzerExactEdgeLength](./fuzzerExactEdgeLength.c) -| getNumCells | Trivial -| getRes0Cells | Trivial -| getPentagons | [fuzzerResolutions](./fuzzerResolutions.c) -| getResolution | [fuzzerCellProperties](./fuzzerCellProperties.c) -| getBaseCellNumber | [fuzzerCellProperties](./fuzzerCellProperties.c) -| stringToH3 | [fuzzerIndexIO](./fuzzerIndexIO.c) -| h3ToString | [fuzzerIndexIO](./fuzzerIndexIO.c) -| isValidCell | [fuzzerCellProperties](./fuzzerCellProperties.c) -| cellToParent | [fuzzerHierarchy](./fuzzerHierarchy.c) -| cellToChildren | [fuzzerHierarchy](./fuzzerHierarchy.c) -| cellToCenterChild | [fuzzerHierarchy](./fuzzerHierarchy.c) -| compactCells | [fuzzerCompact](./fuzzerCompact.c) -| uncompactCells | [fuzzerCompact](./fuzzerCompact.c) -| isResClassIII | [fuzzerCellProperties](./fuzzerCellProperties.c) -| isPentagon | [fuzzerCellProperties](./fuzzerCellProperties.c) -| getIcosahedronFaces | [fuzzerCellProperties](./fuzzerCellProperties.c) -| areNeighborCells | -| cellsToDirectedEdge | -| isValidDirectedEdge | -| getDirectedEdgeOrigin | -| getDirectedEdgeDestination | -| directedEdgeToCells | -| originToDirectedEdges | -| directedEdgeToBoundary | -| cellToVertex | [fuzzerVertexes](./fuzzerVertexes.c) -| cellToVertexes | [fuzzerVertexes](./fuzzerVertexes.c) -| vertexToLatLng | [fuzzerVertexes](./fuzzerVertexes.c) -| isValidVertex | [fuzzerVertexes](./fuzzerVertexes.c) -| gridDistance | -| gridPathCells | -| experimentalH3ToLocalIj | -| experimentalLocalIjToH3 | \ No newline at end of file From 4a65123c0d74d350851d10b770f893849656195d Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Thu, 23 Dec 2021 12:15:42 -0800 Subject: [PATCH 16/33] libFuzzer tests --- .github/workflows/test-fuzzer.yml | 35 +++++++++++++++++++++++++++- CMakeLists.txt | 10 ++++++++ src/apps/applib/include/aflHarness.h | 8 +++++++ 3 files changed, 52 insertions(+), 1 deletion(-) diff --git a/.github/workflows/test-fuzzer.yml b/.github/workflows/test-fuzzer.yml index a83ab84b5f..4c92f8cbcb 100644 --- a/.github/workflows/test-fuzzer.yml +++ b/.github/workflows/test-fuzzer.yml @@ -7,7 +7,7 @@ on: branches: [master, stable-*] jobs: - tests: + afl-tests: name: Fuzzer Compilation ${{ matrix.compiler }} runs-on: ubuntu-latest env: @@ -39,3 +39,36 @@ jobs: $fuzzer --generate inputData $fuzzer inputData done + + libfuzzer-test: + name: LibFuzzer Compilation ${{ matrix.compiler }} + runs-on: ubuntu-latest + env: + CC: ${{ matrix.compiler }} + + strategy: + matrix: + compiler: [clang] + + steps: + - uses: actions/[email protected] + + - name: Configure build + run: | + mkdir build + cd build + cmake -DCMAKE_BUILD_TYPE=Release -DENABLE_LIBFUZZER=ON .. + + - name: Build + run: | + cd build + make fuzzers + + - name: Run fuzzers once + run: | + cd build + for fuzzer in bin/fuzzer*; do + echo $fuzzer + # TODO: Increase + $fuzzer -runs 1000 + done diff --git a/CMakeLists.txt b/CMakeLists.txt index b7ad1045dd..7c717f8a5b 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -44,6 +44,9 @@ option(BUILD_BENCHMARKS "Build benchmarking applications." ON) option(BUILD_FUZZERS "Build fuzzer applications (for use with afl)." ON) option(BUILD_FILTERS "Build filter applications." ON) option(BUILD_GENERATORS "Build code generation applications." ON) +# If ON, libfuzzer settings are used to build the fuzzer harnesses. If OFF, a frontend +# for afl++ is provided instead. +option(ENABLE_LIBFUZZER "Build fuzzers with libFuzzer support." OFF) if(WIN32) # Use bash (usually from Git for Windows) for piping results @@ -89,6 +92,10 @@ if(NOT WIN32) # to fully enable coverage. list(APPEND H3_LINK_FLAGS $<$:--coverage>) endif() + if(ENABLE_LIBFUZZER) + list(APPEND H3_COMPILE_FLAGS -fsanitize=fuzzer,address,undefined) + list(APPEND H3_LINK_FLAGS -fsanitize=fuzzer,address,undefined) + endif() option(WARNINGS_AS_ERRORS "Warnings are treated as errors" OFF) if(WARNINGS_AS_ERRORS) @@ -645,6 +652,9 @@ if(BUILD_FUZZERS) macro(add_h3_fuzzer name srcfile) add_h3_executable(${name} ${srcfile} ${APP_SOURCE_FILES}) + if(ENABLE_LIBFUZZER) + target_compile_definitions(${name} PRIVATE H3_USE_LIBFUZZER) + endif() add_dependencies(fuzzers ${name}) endmacro() diff --git a/src/apps/applib/include/aflHarness.h b/src/apps/applib/include/aflHarness.h index 55a0affa72..450a344306 100644 --- a/src/apps/applib/include/aflHarness.h +++ b/src/apps/applib/include/aflHarness.h @@ -24,6 +24,8 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size); +#ifndef H3_USE_LIBFUZZER + /** * Generate a AFL++ test case file of the right size initialized to all zeroes. * @@ -61,4 +63,10 @@ int generateTestCase(const char *filename, size_t expectedSize) { return LLVMFuzzerTestOneInput(data, expectedSize);\ } +#else + +#define AFL_HARNESS_MAIN(expectedSize) + +#endif // H3_USE_LIBFUZZER + #endif // AFLHARNESS_H \ No newline at end of file From 1e7066ef035d1a80aeefc32259088b7db003cb2f Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Thu, 23 Dec 2021 12:17:14 -0800 Subject: [PATCH 17/33] reformat header --- CMakeLists.txt | 1 + src/apps/applib/include/aflHarness.h | 56 +++++++++++++++------------- 2 files changed, 31 insertions(+), 26 deletions(-) diff --git a/CMakeLists.txt b/CMakeLists.txt index 7c717f8a5b..116abee160 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -150,6 +150,7 @@ set(APP_SOURCE_FILES src/apps/applib/include/benchmark.h src/apps/applib/include/utility.h src/apps/applib/include/args.h + src/apps/applib/include/aflHarness.h src/apps/applib/lib/kml.c src/apps/applib/lib/utility.c src/apps/applib/lib/args.c) diff --git a/src/apps/applib/include/aflHarness.h b/src/apps/applib/include/aflHarness.h index 450a344306..a5ba47e639 100644 --- a/src/apps/applib/include/aflHarness.h +++ b/src/apps/applib/include/aflHarness.h @@ -19,19 +19,20 @@ #ifndef AFLHARNESS_H #define AFLHARNESS_H -#include "utility.h" #include +#include "utility.h" + int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size); #ifndef H3_USE_LIBFUZZER /** * Generate a AFL++ test case file of the right size initialized to all zeroes. - * - * @param filename - * @param expectedSize - * @return int + * + * @param filename + * @param expectedSize + * @return int */ int generateTestCase(const char *filename, size_t expectedSize) { FILE *fp = fopen(filename, "wb"); @@ -43,30 +44,33 @@ int generateTestCase(const char *filename, size_t expectedSize) { return 0; } -#define AFL_HARNESS_MAIN(expectedSize) int main(int argc, char *argv[]) {\ - if (argc == 3) {\ - if (strcmp(argv[1], "--generate") != 0) {\ - error("Invalid option (should be --generate, otherwise look at aflHarness.h to see options)");\ - }\ - return generateTestCase(argv[2], expectedSize);\ - }\ - if (argc != 2) {\ - error("Should have one argument (test case file)\n");\ - }\ - const char *filename = argv[1];\ - FILE *fp = fopen(filename, "rb");\ - uint8_t data[expectedSize];\ - if (fread(&data, expectedSize, 1, fp) != 1) {\ - error("Error reading\n");\ - }\ - fclose(fp);\ - return LLVMFuzzerTestOneInput(data, expectedSize);\ -} +#define AFL_HARNESS_MAIN(expectedSize) \ + int main(int argc, char *argv[]) { \ + if (argc == 3) { \ + if (strcmp(argv[1], "--generate") != 0) { \ + error( \ + "Invalid option (should be --generate, otherwise look at " \ + "aflHarness.h to see options)"); \ + } \ + return generateTestCase(argv[2], expectedSize); \ + } \ + if (argc != 2) { \ + error("Should have one argument (test case file)\n"); \ + } \ + const char *filename = argv[1]; \ + FILE *fp = fopen(filename, "rb"); \ + uint8_t data[expectedSize]; \ + if (fread(&data, expectedSize, 1, fp) != 1) { \ + error("Error reading\n"); \ + } \ + fclose(fp); \ + return LLVMFuzzerTestOneInput(data, expectedSize); \ + } #else #define AFL_HARNESS_MAIN(expectedSize) -#endif // H3_USE_LIBFUZZER +#endif // H3_USE_LIBFUZZER -#endif // AFLHARNESS_H \ No newline at end of file +#endif // AFLHARNESS_H \ No newline at end of file From 0ede7180d24ff6a89ddbd942edf37bf7c2c86ca0 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Thu, 23 Dec 2021 12:21:45 -0800 Subject: [PATCH 18/33] README updates --- src/apps/fuzzers/README.md | 31 ++++++++++++++++++++++++++----- 1 file changed, 26 insertions(+), 5 deletions(-) diff --git a/src/apps/fuzzers/README.md b/src/apps/fuzzers/README.md index fbdab008aa..fd3e3e7b0b 100644 --- a/src/apps/fuzzers/README.md +++ b/src/apps/fuzzers/README.md @@ -1,8 +1,10 @@ # Fuzzer harnesses for H3 This directory contains helper programs for testing the H3 library using the -''[American fuzzy lop](https://lcamtuf.coredump.cx/afl/)'' or ''libFuzzer'' fuzzers. -Fuzzering is a technique for discovering crashes and other edge cases in code +''[American fuzzy lop](https://lcamtuf.coredump.cx/afl/)''/ +''[AFL++](https://github.com/AFLplusplus/AFLplusplus)'' or +''[libFuzzer](https://www.llvm.org/docs/LibFuzzer.html)'' fuzzers. +Fuzzing is a technique for discovering crashes and other edge cases in code such as the H3 core library. # Function coverage @@ -59,13 +61,32 @@ such as the H3 core library. # libFuzzer Usage -[libFuzzer](https://www.llvm.org/docs/LibFuzzer.html) is one of the supported fuzzing drivers. +libFuzzer is one of the supported fuzzing drivers. This is the fuzzer used in [oss-fuzz](https://github.com/google/oss-fuzz/tree/master/projects/h3). +## Build + +You must build H3 with Clang and enable support for libFuzzer. + +``` +CC=clang cmake -DENABLE_LIBFUZZER=ON . +make fuzzers +``` + +## Run + +To begin fuzzing, execute the fuzzer binary: + +``` +fuzzerLatLngToCell +``` + +For command line options including how to specify a test corpus, consult the [libFuzzer documentation](https://www.llvm.org/docs/LibFuzzer.html#options). + # AFL Usage -[AFL++](https://github.com/AFLplusplus/AFLplusplus) is one of the supported fuzzing drivers. +AFL/AFL++ are supported fuzzing drivers. ## Installation @@ -84,7 +105,7 @@ CXX=afl-clang++ CC=afl-clang cmake . make fuzzers ``` -Generate a blank (zeroed) test case file. This will not be very interesting test case but is usedful +Generate a blank (zeroed) test case file. This will not be very a interesting test case but is usedful for having files of the right size. ``` From 65b4ef31264c742ba3b4fdaf6e47003cbdb5db68 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Thu, 23 Dec 2021 14:52:49 -0800 Subject: [PATCH 19/33] fuzzerDirectedEdge --- CMakeLists.txt | 2 ++ src/apps/fuzzers/README.md | 16 ++++----- src/apps/fuzzers/fuzzerDirectedEdge.c | 51 +++++++++++++++++++++++++++ 3 files changed, 61 insertions(+), 8 deletions(-) create mode 100644 src/apps/fuzzers/fuzzerDirectedEdge.c diff --git a/CMakeLists.txt b/CMakeLists.txt index 116abee160..c61cc29170 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -237,6 +237,7 @@ set(OTHER_SOURCE_FILES src/apps/fuzzers/fuzzerHierarchy.c src/apps/fuzzers/fuzzerVertexes.c src/apps/fuzzers/fuzzerCompact.c + src/apps/fuzzers/fuzzerDirectedEdge.c src/apps/benchmarks/benchmarkPolygonToCells.c src/apps/benchmarks/benchmarkPolygon.c src/apps/benchmarks/benchmarkH3SetToLinkedGeo.c @@ -672,6 +673,7 @@ if(BUILD_FUZZERS) add_h3_fuzzer(fuzzerHierarchy src/apps/fuzzers/fuzzerHierarchy.c) add_h3_fuzzer(fuzzerVertexes src/apps/fuzzers/fuzzerVertexes.c) add_h3_fuzzer(fuzzerCompact src/apps/fuzzers/fuzzerCompact.c) + add_h3_fuzzer(fuzzerDirectedEdge src/apps/fuzzers/fuzzerDirectedEdge.c) endif() if(BUILD_BENCHMARKS) diff --git a/src/apps/fuzzers/README.md b/src/apps/fuzzers/README.md index fd3e3e7b0b..7f83a05356 100644 --- a/src/apps/fuzzers/README.md +++ b/src/apps/fuzzers/README.md @@ -42,14 +42,14 @@ such as the H3 core library. | isResClassIII | [fuzzerCellProperties](./fuzzerCellProperties.c) | isPentagon | [fuzzerCellProperties](./fuzzerCellProperties.c) | getIcosahedronFaces | [fuzzerCellProperties](./fuzzerCellProperties.c) -| areNeighborCells | -| cellsToDirectedEdge | -| isValidDirectedEdge | -| getDirectedEdgeOrigin | -| getDirectedEdgeDestination | -| directedEdgeToCells | -| originToDirectedEdges | -| directedEdgeToBoundary | +| areNeighborCells | [fuzzerDirectedEdge](./fuzzerDirectedEdge.c) +| cellsToDirectedEdge | [fuzzerDirectedEdge](./fuzzerDirectedEdge.c) +| isValidDirectedEdge | [fuzzerDirectedEdge](./fuzzerDirectedEdge.c) +| getDirectedEdgeOrigin | [fuzzerDirectedEdge](./fuzzerDirectedEdge.c) +| getDirectedEdgeDestination | [fuzzerDirectedEdge](./fuzzerDirectedEdge.c) +| directedEdgeToCells | [fuzzerDirectedEdge](./fuzzerDirectedEdge.c) +| originToDirectedEdges | [fuzzerDirectedEdge](./fuzzerDirectedEdge.c) +| directedEdgeToBoundary | [fuzzerDirectedEdge](./fuzzerDirectedEdge.c) | cellToVertex | [fuzzerVertexes](./fuzzerVertexes.c) | cellToVertexes | [fuzzerVertexes](./fuzzerVertexes.c) | vertexToLatLng | [fuzzerVertexes](./fuzzerVertexes.c) diff --git a/src/apps/fuzzers/fuzzerDirectedEdge.c b/src/apps/fuzzers/fuzzerDirectedEdge.c new file mode 100644 index 0000000000..cfb2951206 --- /dev/null +++ b/src/apps/fuzzers/fuzzerDirectedEdge.c @@ -0,0 +1,51 @@ +/* + * Copyright 2021 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for cellsToDirectedEdge and related functions + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +typedef struct { + H3Index index; + H3Index index2; +} inputArgs; + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + + H3_EXPORT(areNeighborCells)(args->index, args->index2); + H3Index out; + H3_EXPORT(cellsToDirectedEdge)(args->index, args->index2, &out); + H3_EXPORT(isValidDirectedEdge)(args->index); + H3_EXPORT(getDirectedEdgeOrigin)(args->index, &out); + H3_EXPORT(getDirectedEdgeDestination)(args->index, &out); + H3Index out2[2]; + H3_EXPORT(directedEdgeToCells)(args->index, &out2); + H3Index out6[2]; + H3_EXPORT(originToDirectedEdges)(args->index, &out6); + CellBoundary bndry; + H3_EXPORT(directedEdgeToBoundary)(args->index, &bndry); + + return 0; +} + +AFL_HARNESS_MAIN(sizeof(inputArgs)); From 79b1f44a45ae4e5614c3792891eeb25fb70b79ac Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Thu, 23 Dec 2021 15:02:06 -0800 Subject: [PATCH 20/33] fuzzerLocalIj --- .github/workflows/test-fuzzer.yml | 4 +- CMakeLists.txt | 2 + src/apps/fuzzers/README.md | 8 ++-- src/apps/fuzzers/fuzzerDirectedEdge.c | 2 + src/apps/fuzzers/fuzzerLocalIj.c | 65 +++++++++++++++++++++++++++ 5 files changed, 75 insertions(+), 6 deletions(-) create mode 100644 src/apps/fuzzers/fuzzerLocalIj.c diff --git a/.github/workflows/test-fuzzer.yml b/.github/workflows/test-fuzzer.yml index 4c92f8cbcb..4222dcc300 100644 --- a/.github/workflows/test-fuzzer.yml +++ b/.github/workflows/test-fuzzer.yml @@ -69,6 +69,6 @@ jobs: cd build for fuzzer in bin/fuzzer*; do echo $fuzzer - # TODO: Increase - $fuzzer -runs 1000 + # TODO: Increase run count + $fuzzer -runs=1000 done diff --git a/CMakeLists.txt b/CMakeLists.txt index c61cc29170..c628d973ce 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -238,6 +238,7 @@ set(OTHER_SOURCE_FILES src/apps/fuzzers/fuzzerVertexes.c src/apps/fuzzers/fuzzerCompact.c src/apps/fuzzers/fuzzerDirectedEdge.c + src/apps/fuzzers/fuzzerLocalIj.c src/apps/benchmarks/benchmarkPolygonToCells.c src/apps/benchmarks/benchmarkPolygon.c src/apps/benchmarks/benchmarkH3SetToLinkedGeo.c @@ -674,6 +675,7 @@ if(BUILD_FUZZERS) add_h3_fuzzer(fuzzerVertexes src/apps/fuzzers/fuzzerVertexes.c) add_h3_fuzzer(fuzzerCompact src/apps/fuzzers/fuzzerCompact.c) add_h3_fuzzer(fuzzerDirectedEdge src/apps/fuzzers/fuzzerDirectedEdge.c) + add_h3_fuzzer(fuzzerLocalIj src/apps/fuzzers/fuzzerLocalIj.c) endif() if(BUILD_BENCHMARKS) diff --git a/src/apps/fuzzers/README.md b/src/apps/fuzzers/README.md index 7f83a05356..a28bff29a5 100644 --- a/src/apps/fuzzers/README.md +++ b/src/apps/fuzzers/README.md @@ -54,10 +54,10 @@ such as the H3 core library. | cellToVertexes | [fuzzerVertexes](./fuzzerVertexes.c) | vertexToLatLng | [fuzzerVertexes](./fuzzerVertexes.c) | isValidVertex | [fuzzerVertexes](./fuzzerVertexes.c) -| gridDistance | -| gridPathCells | -| experimentalH3ToLocalIj | -| experimentalLocalIjToH3 | +| gridDistance | [fuzzerLocalIj](./fuzzerLocalIj.c) +| gridPathCells | [fuzzerLocalIj](./fuzzerLocalIj.c) +| experimentalH3ToLocalIj | [fuzzerLocalIj](./fuzzerLocalIj.c) +| experimentalLocalIjToH3 | [fuzzerLocalIj](./fuzzerLocalIj.c) # libFuzzer Usage diff --git a/src/apps/fuzzers/fuzzerDirectedEdge.c b/src/apps/fuzzers/fuzzerDirectedEdge.c index cfb2951206..bdae564bab 100644 --- a/src/apps/fuzzers/fuzzerDirectedEdge.c +++ b/src/apps/fuzzers/fuzzerDirectedEdge.c @@ -32,6 +32,8 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { } const inputArgs *args = (const inputArgs *)data; + // Note that index and index2 need to be plausibly neighbors + // for most of these H3_EXPORT(areNeighborCells)(args->index, args->index2); H3Index out; H3_EXPORT(cellsToDirectedEdge)(args->index, args->index2, &out); diff --git a/src/apps/fuzzers/fuzzerLocalIj.c b/src/apps/fuzzers/fuzzerLocalIj.c new file mode 100644 index 0000000000..b86f4bfecf --- /dev/null +++ b/src/apps/fuzzers/fuzzerLocalIj.c @@ -0,0 +1,65 @@ +/* + * Copyright 2021 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for local IJ and related functions (gridDistance, + * gridPathCells) + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +typedef struct { + H3Index index; + H3Index index2; + int i; + int j; +} inputArgs; + +void testTwoIndexes(H3Index index, H3Index index2) { + int64_t distance; + H3_EXPORT(gridDistance)(index, index2, &distance); + int64_t size; + H3Error err = H3_EXPORT(gridPathCellsSize)(index, index2, &size); + if (!err) { + H3Index *output = calloc(size, sizeof(H3Index)); + H3_EXPORT(gridPathCells)(index, index2, output); + free(output); + } +} + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + + // Note that index and index2 need to be in the approximate area for these + // tests to make sense. + testTwoIndexes(args->index, args->index2); + H3Index out; + CoordIJ ij = {.i = args->i, .j = args->j}; + H3Error err = H3_EXPORT(experimentalLocalIjToH3)(args->index, &ij, &out); + if (!err) { + testTwoIndexes(args->index, out); + } + + H3_EXPORT(experimentalH3ToLocalIj)(args->index, args->index2, &ij); + + return 0; +} + +AFL_HARNESS_MAIN(sizeof(inputArgs)); From 25360efb945f3903e23d149dc722363fc267bc2a Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Thu, 23 Dec 2021 20:13:09 -0800 Subject: [PATCH 21/33] fix fuzzerDirectedEdge build --- src/apps/fuzzers/fuzzerDirectedEdge.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/apps/fuzzers/fuzzerDirectedEdge.c b/src/apps/fuzzers/fuzzerDirectedEdge.c index bdae564bab..5693376e39 100644 --- a/src/apps/fuzzers/fuzzerDirectedEdge.c +++ b/src/apps/fuzzers/fuzzerDirectedEdge.c @@ -41,9 +41,9 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { H3_EXPORT(getDirectedEdgeOrigin)(args->index, &out); H3_EXPORT(getDirectedEdgeDestination)(args->index, &out); H3Index out2[2]; - H3_EXPORT(directedEdgeToCells)(args->index, &out2); + H3_EXPORT(directedEdgeToCells)(args->index, out2); H3Index out6[2]; - H3_EXPORT(originToDirectedEdges)(args->index, &out6); + H3_EXPORT(originToDirectedEdges)(args->index, out6); CellBoundary bndry; H3_EXPORT(directedEdgeToBoundary)(args->index, &bndry); From ac4b918fbb2169509ec5709e0a0f2f8f0aee1bcc Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 26 Dec 2021 17:04:47 -0800 Subject: [PATCH 22/33] Fix fuzzer programs --- src/apps/fuzzers/fuzzerCompact.c | 9 +++++---- src/apps/fuzzers/fuzzerDirectedEdge.c | 2 +- src/apps/fuzzers/fuzzerIndexIO.c | 9 +++++---- 3 files changed, 11 insertions(+), 9 deletions(-) diff --git a/src/apps/fuzzers/fuzzerCompact.c b/src/apps/fuzzers/fuzzerCompact.c index 32ef261bf2..05740372dd 100644 --- a/src/apps/fuzzers/fuzzerCompact.c +++ b/src/apps/fuzzers/fuzzerCompact.c @@ -22,13 +22,13 @@ #include "utility.h" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { - if (size < sizeof(H3Index) + 1) { + if (size < sizeof(H3Index) * 2) { return 0; } uint8_t res = *data; - H3Index *input = (H3Index *)(data + 1); - size_t inputSize = (size - 1) / sizeof(H3Index); + H3Index *input = (H3Index *)(data + sizeof(H3Index)); + size_t inputSize = (size - sizeof(H3Index)) / sizeof(H3Index); // fuzz compactCells H3Index *compacted = calloc(inputSize, sizeof(H3Index)); @@ -43,7 +43,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { } } if (compactedCount < 2) { - int uncompactRes = 10; + int uncompactRes = 9; int64_t uncompactedSize; H3Error err = H3_EXPORT(uncompactCellsSize)( compacted, inputSize, uncompactRes, &uncompactedSize); @@ -69,6 +69,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { h3Println(uncompacted[0]); free(uncompacted); } + free(compacted); return 0; } diff --git a/src/apps/fuzzers/fuzzerDirectedEdge.c b/src/apps/fuzzers/fuzzerDirectedEdge.c index 5693376e39..d142022e02 100644 --- a/src/apps/fuzzers/fuzzerDirectedEdge.c +++ b/src/apps/fuzzers/fuzzerDirectedEdge.c @@ -42,7 +42,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { H3_EXPORT(getDirectedEdgeDestination)(args->index, &out); H3Index out2[2]; H3_EXPORT(directedEdgeToCells)(args->index, out2); - H3Index out6[2]; + H3Index out6[6]; H3_EXPORT(originToDirectedEdges)(args->index, out6); CellBoundary bndry; H3_EXPORT(directedEdgeToBoundary)(args->index, &bndry); diff --git a/src/apps/fuzzers/fuzzerIndexIO.c b/src/apps/fuzzers/fuzzerIndexIO.c index d7fd55af16..7d61e9d197 100644 --- a/src/apps/fuzzers/fuzzerIndexIO.c +++ b/src/apps/fuzzers/fuzzerIndexIO.c @@ -32,13 +32,14 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { if (size < sizeof(inputArgs)) { return 0; } - inputArgs *args = (inputArgs *)data; - args->str[STRING_LENGTH - 1] = 0; + inputArgs args; + memcpy(&args, data, sizeof(inputArgs)); + args.str[STRING_LENGTH - 1] = 0; char str[STRING_LENGTH]; - h3Println(H3_EXPORT(h3ToString)(args->index, str, STRING_LENGTH)); + h3Println(H3_EXPORT(h3ToString)(args.index, str, STRING_LENGTH)); H3Index index; - H3Error err = H3_EXPORT(stringToH3)(args->str, &index); + H3Error err = H3_EXPORT(stringToH3)(args.str, &index); if (!err) { h3Println(index); } From 1145bce8bbaa7d06c55d84c169e3e065744db898 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 26 Dec 2021 21:13:59 -0800 Subject: [PATCH 23/33] remove logging --- src/apps/fuzzers/fuzzerCellArea.c | 6 +++--- src/apps/fuzzers/fuzzerCellProperties.c | 11 +++++------ src/apps/fuzzers/fuzzerCellToLatLng.c | 2 -- src/apps/fuzzers/fuzzerDistances.c | 6 +++--- src/apps/fuzzers/fuzzerExactEdgeLength.c | 3 --- src/apps/fuzzers/fuzzerResolutions.c | 12 ++++++------ src/apps/fuzzers/fuzzerVertexes.c | 3 +-- 7 files changed, 18 insertions(+), 25 deletions(-) diff --git a/src/apps/fuzzers/fuzzerCellArea.c b/src/apps/fuzzers/fuzzerCellArea.c index 569a135ad1..0adb30fa12 100644 --- a/src/apps/fuzzers/fuzzerCellArea.c +++ b/src/apps/fuzzers/fuzzerCellArea.c @@ -31,9 +31,9 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { } const inputArgs *args = (const inputArgs *)data; - printf("%f", H3_EXPORT(cellAreaRads2)(args->index)); - printf("%f", H3_EXPORT(cellAreaKm2)(args->index)); - printf("%f", H3_EXPORT(cellAreaM2)(args->index)); + H3_EXPORT(cellAreaRads2)(args->index); + H3_EXPORT(cellAreaKm2)(args->index); + H3_EXPORT(cellAreaM2)(args->index); return 0; } diff --git a/src/apps/fuzzers/fuzzerCellProperties.c b/src/apps/fuzzers/fuzzerCellProperties.c index da5632ba0d..5cf0f40b8d 100644 --- a/src/apps/fuzzers/fuzzerCellProperties.c +++ b/src/apps/fuzzers/fuzzerCellProperties.c @@ -31,18 +31,17 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { } const inputArgs *args = (const inputArgs *)data; - printf("%d", H3_EXPORT(getResolution)(args->index)); - printf("%d", H3_EXPORT(getBaseCellNumber)(args->index)); - printf("%d", H3_EXPORT(isValidCell)(args->index)); - printf("%d", H3_EXPORT(isPentagon)(args->index)); - printf("%d", H3_EXPORT(isResClassIII)(args->index)); + H3_EXPORT(getResolution)(args->index); + H3_EXPORT(getBaseCellNumber)(args->index); + H3_EXPORT(isValidCell)(args->index); + H3_EXPORT(isPentagon)(args->index); + H3_EXPORT(isResClassIII)(args->index); int faceCount; H3Error err = H3_EXPORT(maxFaceCount)(args->index, &faceCount); if (!err && faceCount > 0) { int *out = calloc(faceCount, sizeof(int)); H3_EXPORT(getIcosahedronFaces)(args->index, out); - printf("%d", out[0]); free(out); } diff --git a/src/apps/fuzzers/fuzzerCellToLatLng.c b/src/apps/fuzzers/fuzzerCellToLatLng.c index 91a453db1a..9ab823b511 100644 --- a/src/apps/fuzzers/fuzzerCellToLatLng.c +++ b/src/apps/fuzzers/fuzzerCellToLatLng.c @@ -32,10 +32,8 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { const inputArgs *args = (const inputArgs *)data; LatLng geo; H3_EXPORT(cellToLatLng)(args->index, &geo); - printf("%lf %lf\n", geo.lat, geo.lng); CellBoundary cellBoundary; H3_EXPORT(cellToBoundary)(args->index, &cellBoundary); - printf("%d\n", cellBoundary.numVerts); return 0; } diff --git a/src/apps/fuzzers/fuzzerDistances.c b/src/apps/fuzzers/fuzzerDistances.c index 9467ad644e..fe5f1ec68d 100644 --- a/src/apps/fuzzers/fuzzerDistances.c +++ b/src/apps/fuzzers/fuzzerDistances.c @@ -32,9 +32,9 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { } const inputArgs *args = (const inputArgs *)data; - printf("%f", H3_EXPORT(distanceRads)(&args->a, &args->b)); - printf("%f", H3_EXPORT(distanceKm)(&args->a, &args->b)); - printf("%f", H3_EXPORT(distanceM)(&args->a, &args->b)); + H3_EXPORT(distanceRads)(&args->a, &args->b); + H3_EXPORT(distanceKm)(&args->a, &args->b); + H3_EXPORT(distanceM)(&args->a, &args->b); return 0; } diff --git a/src/apps/fuzzers/fuzzerExactEdgeLength.c b/src/apps/fuzzers/fuzzerExactEdgeLength.c index fe4fb555c2..93af11a391 100644 --- a/src/apps/fuzzers/fuzzerExactEdgeLength.c +++ b/src/apps/fuzzers/fuzzerExactEdgeLength.c @@ -33,11 +33,8 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { double distance; H3_EXPORT(exactEdgeLengthRads)(args->index, &distance); - printf("%f", distance); H3_EXPORT(exactEdgeLengthKm)(args->index, &distance); - printf("%f", distance); H3_EXPORT(exactEdgeLengthM)(args->index, &distance); - printf("%f", distance); return 0; } diff --git a/src/apps/fuzzers/fuzzerResolutions.c b/src/apps/fuzzers/fuzzerResolutions.c index 6cd925fefa..b8fbbe8fab 100644 --- a/src/apps/fuzzers/fuzzerResolutions.c +++ b/src/apps/fuzzers/fuzzerResolutions.c @@ -31,12 +31,12 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { } const inputArgs *args = (const inputArgs *)data; - // Do not perform bound checks - // printf("%f", H3_EXPORT(getHexagonAreaAvgKm2)(args->res)); - // printf("%f", H3_EXPORT(getHexagonAreaAvgM2)(args->res)); - // printf("%f", H3_EXPORT(getHexagonEdgeLengthAvgKm)(args->res)); - // printf("%f", H3_EXPORT(getHexagonEdgeLengthAvgM)(args->res)); - // printf("%llx", H3_EXPORT(getNumCells)(args->res)); + // TODO: Do not perform bound checks + // H3_EXPORT(getHexagonAreaAvgKm2)(args->res); + // H3_EXPORT(getHexagonAreaAvgM2)(args->res); + // H3_EXPORT(getHexagonEdgeLengthAvgKm)(args->res); + // H3_EXPORT(getHexagonEdgeLengthAvgM)(args->res); + // H3_EXPORT(getNumCells)(args->res); H3Index pentagons[12]; H3_EXPORT(getPentagons)(args->res, pentagons); diff --git a/src/apps/fuzzers/fuzzerVertexes.c b/src/apps/fuzzers/fuzzerVertexes.c index e83daa3d68..8f792876a1 100644 --- a/src/apps/fuzzers/fuzzerVertexes.c +++ b/src/apps/fuzzers/fuzzerVertexes.c @@ -40,8 +40,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { h3Println(outArr[0]); LatLng geo; H3_EXPORT(vertexToLatLng)(args->index, &geo); - printf("%lf %lf\n", geo.lat, geo.lng); - printf("%d\n", H3_EXPORT(isValidVertex)(args->index)); + H3_EXPORT(isValidVertex)(args->index); return 0; } From cd14266a0fd59de896d6ef8e920a86ea6b8449d4 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 26 Dec 2021 21:57:36 -0800 Subject: [PATCH 24/33] remove h3Println --- src/apps/fuzzers/fuzzerCompact.c | 3 --- src/apps/fuzzers/fuzzerGridDisk.c | 6 ------ src/apps/fuzzers/fuzzerHierarchy.c | 5 +---- src/apps/fuzzers/fuzzerIndexIO.c | 7 ++----- src/apps/fuzzers/fuzzerLatLngToCell.c | 4 +--- src/apps/fuzzers/fuzzerResolutions.c | 1 - src/apps/fuzzers/fuzzerVertexes.c | 2 -- 7 files changed, 4 insertions(+), 24 deletions(-) diff --git a/src/apps/fuzzers/fuzzerCompact.c b/src/apps/fuzzers/fuzzerCompact.c index 05740372dd..96d1c2e4ee 100644 --- a/src/apps/fuzzers/fuzzerCompact.c +++ b/src/apps/fuzzers/fuzzerCompact.c @@ -33,7 +33,6 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { // fuzz compactCells H3Index *compacted = calloc(inputSize, sizeof(H3Index)); H3_EXPORT(compactCells)(input, compacted, inputSize); - h3Println(compacted[0]); // fuzz uncompactCells using output of above int compactedCount = 0; @@ -52,7 +51,6 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { H3_EXPORT(uncompactCells) (compacted, compactedCount, uncompacted, uncompactedSize, uncompactRes); - h3Println(uncompacted[0]); free(uncompacted); } } @@ -66,7 +64,6 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { H3Index *uncompacted = calloc(uncompactedSize, sizeof(H3Index)); H3_EXPORT(uncompactCells) (compacted, compactedCount, uncompacted, uncompactedSize, res); - h3Println(uncompacted[0]); free(uncompacted); } free(compacted); diff --git a/src/apps/fuzzers/fuzzerGridDisk.c b/src/apps/fuzzers/fuzzerGridDisk.c index 95dbdb473d..b726289b13 100644 --- a/src/apps/fuzzers/fuzzerGridDisk.c +++ b/src/apps/fuzzers/fuzzerGridDisk.c @@ -37,14 +37,12 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { H3Index *results = calloc(sizeof(H3Index), sz); if (results != NULL) { H3_EXPORT(gridDisk)(args->index, args->k, results); - h3Println(results[0]); } free(results); results = calloc(sizeof(H3Index), sz); if (results != NULL) { H3_EXPORT(gridDiskUnsafe)(args->index, args->k, results); - h3Println(results[0]); } free(results); @@ -54,7 +52,6 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { if (results != NULL && distances != NULL) { H3_EXPORT(gridDiskDistancesUnsafe) (args->index, args->k, results, distances); - h3Println(results[0]); } free(results); free(distances); @@ -64,7 +61,6 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { if (results != NULL && distances != NULL) { H3_EXPORT(gridDiskDistancesSafe) (args->index, args->k, results, distances); - h3Println(results[0]); } free(results); free(distances); @@ -73,7 +69,6 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { results = calloc(sizeof(H3Index), sz); if (results != NULL && distances != NULL) { H3_EXPORT(gridDiskDistances)(args->index, args->k, results, distances); - h3Println(results[0]); } free(results); free(distances); @@ -81,7 +76,6 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { results = calloc(sizeof(H3Index), sz); if (results != NULL) { H3_EXPORT(gridRingUnsafe)(args->index, args->k, results); - h3Println(results[0]); } free(results); return 0; diff --git a/src/apps/fuzzers/fuzzerHierarchy.c b/src/apps/fuzzers/fuzzerHierarchy.c index 6cb201aaaf..67ea7e63f2 100644 --- a/src/apps/fuzzers/fuzzerHierarchy.c +++ b/src/apps/fuzzers/fuzzerHierarchy.c @@ -37,11 +37,9 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { H3Index parent; H3_EXPORT(cellToParent)(args->index, args->parentRes, &parent); - h3Println(parent); // TODO: Update with new API - H3Index child = H3_EXPORT(cellToCenterChild)(args->index, args->childRes); - h3Println(child); + H3_EXPORT(cellToCenterChild)(args->index, args->childRes); int resDiff = args->childRes - H3_EXPORT(getResolution)(args->index); if (resDiff < MAX_CHILDREN_DIFF) { @@ -51,7 +49,6 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { if (!err) { H3Index *children = calloc(childrenSize, sizeof(H3Index)); H3_EXPORT(cellToChildren)(args->index, args->childRes, children); - h3Println(children[0]); free(children); } } diff --git a/src/apps/fuzzers/fuzzerIndexIO.c b/src/apps/fuzzers/fuzzerIndexIO.c index 7d61e9d197..762ed71b6a 100644 --- a/src/apps/fuzzers/fuzzerIndexIO.c +++ b/src/apps/fuzzers/fuzzerIndexIO.c @@ -37,12 +37,9 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { args.str[STRING_LENGTH - 1] = 0; char str[STRING_LENGTH]; - h3Println(H3_EXPORT(h3ToString)(args.index, str, STRING_LENGTH)); + H3_EXPORT(h3ToString)(args.index, str, STRING_LENGTH); H3Index index; - H3Error err = H3_EXPORT(stringToH3)(args.str, &index); - if (!err) { - h3Println(index); - } + H3_EXPORT(stringToH3)(args.str, &index); return 0; } diff --git a/src/apps/fuzzers/fuzzerLatLngToCell.c b/src/apps/fuzzers/fuzzerLatLngToCell.c index 3b6ae7e108..657f77d5f8 100644 --- a/src/apps/fuzzers/fuzzerLatLngToCell.c +++ b/src/apps/fuzzers/fuzzerLatLngToCell.c @@ -33,10 +33,8 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { const inputArgs *args = (const inputArgs *)data; LatLng g = {.lat = args->lat, .lng = args->lng}; H3Index h; - H3Error e = H3_EXPORT(latLngToCell)(&g, args->res, &h); + H3_EXPORT(latLngToCell)(&g, args->res, &h); - h3Println(e); - h3Println(h); return 0; } diff --git a/src/apps/fuzzers/fuzzerResolutions.c b/src/apps/fuzzers/fuzzerResolutions.c index b8fbbe8fab..66e551ec74 100644 --- a/src/apps/fuzzers/fuzzerResolutions.c +++ b/src/apps/fuzzers/fuzzerResolutions.c @@ -40,7 +40,6 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { H3Index pentagons[12]; H3_EXPORT(getPentagons)(args->res, pentagons); - h3Println(pentagons[0]); return 0; } diff --git a/src/apps/fuzzers/fuzzerVertexes.c b/src/apps/fuzzers/fuzzerVertexes.c index 8f792876a1..2ff808b861 100644 --- a/src/apps/fuzzers/fuzzerVertexes.c +++ b/src/apps/fuzzers/fuzzerVertexes.c @@ -34,10 +34,8 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { H3Index out; H3_EXPORT(cellToVertex)(args->index, args->vertexNum, &out); - h3Println(out); H3Index outArr[6]; H3_EXPORT(cellToVertexes)(args->index, outArr); - h3Println(outArr[0]); LatLng geo; H3_EXPORT(vertexToLatLng)(args->index, &geo); H3_EXPORT(isValidVertex)(args->index); From 76532d872156e96acad5d0c47d984fe4ffb01e7a Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 2 Jan 2022 23:39:30 -0800 Subject: [PATCH 25/33] add fuzzerPoylgonToCells --- CMakeLists.txt | 2 + src/apps/fuzzers/README.md | 2 +- src/apps/fuzzers/fuzzerCompact.c | 4 +- src/apps/fuzzers/fuzzerPolygonToCells.c | 96 +++++++++++++++++++++++++ 4 files changed, 102 insertions(+), 2 deletions(-) create mode 100644 src/apps/fuzzers/fuzzerPolygonToCells.c diff --git a/CMakeLists.txt b/CMakeLists.txt index c628d973ce..c5f14c69c8 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -239,6 +239,7 @@ set(OTHER_SOURCE_FILES src/apps/fuzzers/fuzzerCompact.c src/apps/fuzzers/fuzzerDirectedEdge.c src/apps/fuzzers/fuzzerLocalIj.c + src/apps/fuzzers/fuzzerPolygonToCells.c src/apps/benchmarks/benchmarkPolygonToCells.c src/apps/benchmarks/benchmarkPolygon.c src/apps/benchmarks/benchmarkH3SetToLinkedGeo.c @@ -676,6 +677,7 @@ if(BUILD_FUZZERS) add_h3_fuzzer(fuzzerCompact src/apps/fuzzers/fuzzerCompact.c) add_h3_fuzzer(fuzzerDirectedEdge src/apps/fuzzers/fuzzerDirectedEdge.c) add_h3_fuzzer(fuzzerLocalIj src/apps/fuzzers/fuzzerLocalIj.c) + add_h3_fuzzer(fuzzerPolygonToCells src/apps/fuzzers/fuzzerPolygonToCells.c) endif() if(BUILD_BENCHMARKS) diff --git a/src/apps/fuzzers/README.md b/src/apps/fuzzers/README.md index a28bff29a5..0e96ff2884 100644 --- a/src/apps/fuzzers/README.md +++ b/src/apps/fuzzers/README.md @@ -17,7 +17,7 @@ such as the H3 core library. | gridDisk | [fuzzerGridDisk](./fuzzerGridDisk.c) | gridDiskDistances | [fuzzerGridDisk](./fuzzerGridDisk.c) | gridRingUnsafe | [fuzzerGridDisk](./fuzzerGridDisk.c) -| polygonToCells | +| polygonToCells | [fuzzerPoylgonToCells](./fuzzerPolygonToCells.c) | h3SetToMultiPolygon | [fuzzerH3SetToLinkedGeo](./fuzzerH3SetToLinkedGeo.c) | degsToRads | Trivial | radsToDegs | Trivial diff --git a/src/apps/fuzzers/fuzzerCompact.c b/src/apps/fuzzers/fuzzerCompact.c index 96d1c2e4ee..0f28ac50d1 100644 --- a/src/apps/fuzzers/fuzzerCompact.c +++ b/src/apps/fuzzers/fuzzerCompact.c @@ -21,12 +21,15 @@ #include "h3api.h" #include "utility.h" +const int MAX_UNCOMPACT_RES = 9; + int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { if (size < sizeof(H3Index) * 2) { return 0; } uint8_t res = *data; + uint8_t uncompactRes = (*(data + 1)) % (MAX_UNCOMPACT_RES + 1); H3Index *input = (H3Index *)(data + sizeof(H3Index)); size_t inputSize = (size - sizeof(H3Index)) / sizeof(H3Index); @@ -42,7 +45,6 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { } } if (compactedCount < 2) { - int uncompactRes = 9; int64_t uncompactedSize; H3Error err = H3_EXPORT(uncompactCellsSize)( compacted, inputSize, uncompactRes, &uncompactedSize); diff --git a/src/apps/fuzzers/fuzzerPolygonToCells.c b/src/apps/fuzzers/fuzzerPolygonToCells.c new file mode 100644 index 0000000000..2cddf499a0 --- /dev/null +++ b/src/apps/fuzzers/fuzzerPolygonToCells.c @@ -0,0 +1,96 @@ +/* + * Copyright 2022 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for polygonToCells and related functions + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +typedef struct { + int res; + int numHoles; + // repeating: num verts, verts +} inputArgs; + +const int MAX_RES = 15; +const int MAX_SZ = 4000000; +const int MAX_HOLES = 100; + +int populateGeoLoop(GeoLoop *g, const uint8_t *data, size_t *offset, + size_t size) { + if (size < *offset + sizeof(int)) { + return 1; + } + int numVerts = *(const int *)(data + *offset); + *offset = *offset + sizeof(int); + g->numVerts = numVerts; + if (size < *offset + sizeof(LatLng) * numVerts) { + return 1; + } + g->verts = (LatLng *)(data + *offset); + *offset = *offset + sizeof(LatLng) * numVerts; + return 0; +} + +void run(GeoPolygon *geoPolygon, int res) { + int64_t sz; + H3Error err = H3_EXPORT(maxPolygonToCellsSize)(geoPolygon, res, &sz); + if (!err && sz < MAX_SZ) { + if (sz < 0) { + printf("Oh no - sz is negative\n"); + } + H3Index *out = calloc(sz, sizeof(H3Index)); + H3_EXPORT(polygonToCells)(geoPolygon, res, out); + free(out); + } +} + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(inputArgs)) { + return 0; + } + const inputArgs *args = (const inputArgs *)data; + int res = args->res % (MAX_RES + 1); + + GeoPolygon geoPolygon; + geoPolygon.numHoles = args->numHoles % MAX_HOLES; + if (geoPolygon.numHoles < 0) { + return 0; + } + geoPolygon.holes = calloc(geoPolygon.numHoles, sizeof(GeoLoop)); + size_t offset = sizeof(inputArgs); + if (populateGeoLoop(&geoPolygon.geoloop, data, &offset, size)) { + free(geoPolygon.holes); + return 0; + } + for (int i = 0; i < geoPolygon.numHoles; i++) { + if (populateGeoLoop(&geoPolygon.holes[i], data, &offset, size)) { + free(geoPolygon.holes); + return 0; + } + } + + run(&geoPolygon, res); + geoPolygon.numHoles = 0; + run(&geoPolygon, res); + free(geoPolygon.holes); + + return 0; +} + +AFL_HARNESS_MAIN(sizeof(inputArgs)); From 84bc4e9cdac6b83f623605dbd522be5fcb8d5a80 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Mon, 3 Jan 2022 13:11:44 -0800 Subject: [PATCH 26/33] Update per review --- src/apps/fuzzers/fuzzerCompact.c | 40 +++++++++++++------------ src/apps/fuzzers/fuzzerPolygonToCells.c | 4 +++ 2 files changed, 25 insertions(+), 19 deletions(-) diff --git a/src/apps/fuzzers/fuzzerCompact.c b/src/apps/fuzzers/fuzzerCompact.c index 0f28ac50d1..bf38a69b8a 100644 --- a/src/apps/fuzzers/fuzzerCompact.c +++ b/src/apps/fuzzers/fuzzerCompact.c @@ -35,37 +35,39 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { // fuzz compactCells H3Index *compacted = calloc(inputSize, sizeof(H3Index)); - H3_EXPORT(compactCells)(input, compacted, inputSize); + H3Error compactErr = H3_EXPORT(compactCells)(input, compacted, inputSize); // fuzz uncompactCells using output of above - int compactedCount = 0; - for (int i = 0; i < inputSize; i++) { - if (compacted[i] != H3_NULL) { - compactedCount++; + if (!compactErr) { + int compactedCount = 0; + for (int i = 0; i < inputSize; i++) { + if (compacted[i] != H3_NULL) { + compactedCount++; + } } - } - if (compactedCount < 2) { - int64_t uncompactedSize; - H3Error err = H3_EXPORT(uncompactCellsSize)( - compacted, inputSize, uncompactRes, &uncompactedSize); - if (!err) { - H3Index *uncompacted = calloc(uncompactedSize, sizeof(H3Index)); - H3_EXPORT(uncompactCells) - (compacted, compactedCount, uncompacted, uncompactedSize, - uncompactRes); - free(uncompacted); + if (compactedCount < 2) { + int64_t uncompactedSize; + H3Error err = H3_EXPORT(uncompactCellsSize)( + compacted, inputSize, uncompactRes, &uncompactedSize); + if (!err) { + H3Index *uncompacted = calloc(uncompactedSize, sizeof(H3Index)); + H3_EXPORT(uncompactCells) + (compacted, compactedCount, uncompacted, uncompactedSize, + uncompactRes); + free(uncompacted); + } } } // fuzz uncompactCells using the original input int64_t uncompactedSize; - H3Error err = H3_EXPORT(uncompactCellsSize)(compacted, inputSize, res, - &uncompactedSize); + H3Error err = + H3_EXPORT(uncompactCellsSize)(input, inputSize, res, &uncompactedSize); if (!err) { H3Index *uncompacted = calloc(uncompactedSize, sizeof(H3Index)); H3_EXPORT(uncompactCells) - (compacted, compactedCount, uncompacted, uncompactedSize, res); + (input, inputSize, uncompacted, uncompactedSize, res); free(uncompacted); } free(compacted); diff --git a/src/apps/fuzzers/fuzzerPolygonToCells.c b/src/apps/fuzzers/fuzzerPolygonToCells.c index 2cddf499a0..1110d025ca 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCells.c +++ b/src/apps/fuzzers/fuzzerPolygonToCells.c @@ -25,6 +25,9 @@ typedef struct { int res; int numHoles; // repeating: num verts, verts + // We add a large fixed buffer so our test case generator for AL + // knows how large to make the file. + uint8_t buffer[1024]; } inputArgs; const int MAX_RES = 15; @@ -52,6 +55,7 @@ void run(GeoPolygon *geoPolygon, int res) { H3Error err = H3_EXPORT(maxPolygonToCellsSize)(geoPolygon, res, &sz); if (!err && sz < MAX_SZ) { if (sz < 0) { + // TODO: Check on this once rebased printf("Oh no - sz is negative\n"); } H3Index *out = calloc(sz, sizeof(H3Index)); From e04c62cc2720d3bf8b7e1c33fe8657c0a7c0fbb2 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Mon, 3 Jan 2022 14:17:06 -0800 Subject: [PATCH 27/33] Add comment on memcpy per review --- src/apps/fuzzers/fuzzerIndexIO.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/src/apps/fuzzers/fuzzerIndexIO.c b/src/apps/fuzzers/fuzzerIndexIO.c index 762ed71b6a..5a6ef36ac2 100644 --- a/src/apps/fuzzers/fuzzerIndexIO.c +++ b/src/apps/fuzzers/fuzzerIndexIO.c @@ -33,6 +33,9 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { return 0; } inputArgs args; + // Copy the input data array since we need to modify it on the next line + // to ensure it is zero terminated. (We are not interested in non-zero terminated + // bugs since that fails the contract.) memcpy(&args, data, sizeof(inputArgs)); args.str[STRING_LENGTH - 1] = 0; From 0016f1c5e3a779dc223e55f24327512535666ee7 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Mon, 3 Jan 2022 14:34:17 -0800 Subject: [PATCH 28/33] Fix potential crash in vertexRotations --- src/apps/fuzzers/fuzzerIndexIO.c | 4 ++-- src/apps/testapps/testBaseCells.c | 4 ++++ src/apps/testapps/testVertex.c | 7 +++++++ src/h3lib/lib/baseCells.c | 2 +- src/h3lib/lib/vertex.c | 24 ++++++++++++++++++------ 5 files changed, 32 insertions(+), 9 deletions(-) diff --git a/src/apps/fuzzers/fuzzerIndexIO.c b/src/apps/fuzzers/fuzzerIndexIO.c index 5a6ef36ac2..8746c94762 100644 --- a/src/apps/fuzzers/fuzzerIndexIO.c +++ b/src/apps/fuzzers/fuzzerIndexIO.c @@ -34,8 +34,8 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { } inputArgs args; // Copy the input data array since we need to modify it on the next line - // to ensure it is zero terminated. (We are not interested in non-zero terminated - // bugs since that fails the contract.) + // to ensure it is zero terminated. (We are not interested in non-zero + // terminated bugs since that fails the contract.) memcpy(&args, data, sizeof(inputArgs)); args.str[STRING_LENGTH - 1] = 0; diff --git a/src/apps/testapps/testBaseCells.c b/src/apps/testapps/testBaseCells.c index ff33018636..a317f12061 100644 --- a/src/apps/testapps/testBaseCells.c +++ b/src/apps/testapps/testBaseCells.c @@ -41,4 +41,8 @@ SUITE(baseCells) { t_assert(_baseCellToCCWrot60(16, -1) == INVALID_ROTATIONS, "should return invalid rotation for invalid face (negative)"); t_assert(_baseCellToCCWrot60(1, 0) == INVALID_ROTATIONS, "should return invalid rotation for base cell not appearing on face"); } + + TEST(isBaseCellPentagon_invalid) { + t_assert(_isBaseCellPentagon(-1) == false, "isBaseCellPentagon handles negative"); + } } diff --git a/src/apps/testapps/testVertex.c b/src/apps/testapps/testVertex.c index 4de950609b..7c752dd5fe 100644 --- a/src/apps/testapps/testVertex.c +++ b/src/apps/testapps/testVertex.c @@ -100,6 +100,13 @@ SUITE(Vertex) { "invalid pent vertex should return null index"); } + TEST(cellToVertex_invalid) { + H3Index invalid = 0xFFFFFFFFFFFFFFFF; + H3Index vert; + t_assert(H3_EXPORT(cellToVertex)(invalid, 3, &vert) == E_CELL_INVALID, + "Invalid cell returns error"); + } + TEST(isValidVertex_hex) { H3Index origin = 0x823d6ffffffffff; H3Index vert = 0x2222597fffffffff; diff --git a/src/h3lib/lib/baseCells.c b/src/h3lib/lib/baseCells.c index 5e3e11f8c8..57e6438559 100644 --- a/src/h3lib/lib/baseCells.c +++ b/src/h3lib/lib/baseCells.c @@ -822,7 +822,7 @@ const BaseCellData baseCellData[NUM_BASE_CELLS] = { /** @brief Return whether or not the indicated base cell is a pentagon. */ int _isBaseCellPentagon(int baseCell) { - if (baseCell < 0 || baseCell >= NUM_BASE_CELLS) { // LCOV_EXCL_BR_LINE + if (baseCell < 0 || baseCell >= NUM_BASE_CELLS) { // Base cells less than zero can not be represented in an index return false; } diff --git a/src/h3lib/lib/vertex.c b/src/h3lib/lib/vertex.c index 816f4b32f7..ff88d85195 100644 --- a/src/h3lib/lib/vertex.c +++ b/src/h3lib/lib/vertex.c @@ -47,12 +47,15 @@ static const PentagonDirectionFaces pentagonDirectionFaces[NUM_PENTAGONS] = { /** * Get the number of CCW rotations of the cell's vertex numbers * compared to the directional layout of its neighbors. - * @return Number of CCW rotations for the cell + * @param out Number of CCW rotations for the cell */ -static int vertexRotations(H3Index cell) { +static H3Error vertexRotations(H3Index cell, int *out) { // Get the face and other info for the origin FaceIJK fijk; - _h3ToFaceIjk(cell, &fijk); + H3Error err = _h3ToFaceIjk(cell, &fijk); + if (err) { + return err; + } int baseCell = H3_EXPORT(getBaseCellNumber)(cell); int cellLeadingDigit = _h3LeadingNonZeroDigit(cell); @@ -94,7 +97,8 @@ static int vertexRotations(H3Index cell) { ccwRot60 = (ccwRot60 + 1) % 6; } } - return ccwRot60; + *out = ccwRot60; + return E_SUCCESS; } /** @brief Hexagon direction to vertex number relationships (same face). @@ -124,7 +128,11 @@ int vertexNumForDirection(const H3Index origin, const Direction direction) { return INVALID_VERTEX_NUM; // Determine the vertex rotations for this cell - int rotations = vertexRotations(origin); + int rotations; + H3Error err = vertexRotations(origin, &rotations); + if (err) { + return INVALID_VERTEX_NUM; + } // Find the appropriate vertex, rotating CCW if necessary if (isPent) { @@ -163,7 +171,11 @@ Direction directionForVertexNum(const H3Index origin, const int vertexNum) { return INVALID_DIGIT; // Determine the vertex rotations for this cell - int rotations = vertexRotations(origin); + int rotations; + H3Error err = vertexRotations(origin, &rotations); + if (err) { + return INVALID_DIGIT; + } // Find the appropriate direction, rotating CW if necessary return isPent ? vertexNumToDirectionPent[(vertexNum + rotations) % From 4b4e6233ed97127c75e3cfe7cc8a9efe12ec7967 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Mon, 3 Jan 2022 15:02:15 -0800 Subject: [PATCH 29/33] Catch possible failure in getIcosahedronFaces --- src/apps/fuzzers/fuzzerGridDisk.c | 4 +++- src/apps/testapps/testGetIcosahedronFaces.c | 14 +++++++++++++- src/h3lib/lib/h3Index.c | 9 ++++++++- 3 files changed, 24 insertions(+), 3 deletions(-) diff --git a/src/apps/fuzzers/fuzzerGridDisk.c b/src/apps/fuzzers/fuzzerGridDisk.c index edce4ac15b..2611151459 100644 --- a/src/apps/fuzzers/fuzzerGridDisk.c +++ b/src/apps/fuzzers/fuzzerGridDisk.c @@ -26,6 +26,8 @@ typedef struct { int64_t k; } inputArgs; +const int64_t MAX_GRID_DISK_SIZE = 0x1000000000; + int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { if (size < sizeof(inputArgs)) { return 0; @@ -34,7 +36,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { int64_t sz; H3Error err = H3_EXPORT(maxGridDiskSize)(args->k, &sz); - if (err) { + if (err || sz > MAX_GRID_DISK_SIZE) { // Can't allocate return 0; } diff --git a/src/apps/testapps/testGetIcosahedronFaces.c b/src/apps/testapps/testGetIcosahedronFaces.c index 8322c0285c..73db7c0c68 100644 --- a/src/apps/testapps/testGetIcosahedronFaces.c +++ b/src/apps/testapps/testGetIcosahedronFaces.c @@ -139,6 +139,18 @@ SUITE(getIcosahedronFaces) { TEST(invalid) { H3Index invalid = 0xFFFFFFFFFFFFFFFF; int out; - t_assert(H3_EXPORT(getIcosahedronFaces)(invalid, &out) == E_CELL_INVALID, "Invalid cell"); + t_assert( + H3_EXPORT(getIcosahedronFaces)(invalid, &out) == E_CELL_INVALID, + "Invalid cell"); + } + + TEST(invalid2) { + H3Index invalid = 0x71330073003f004e; + int sz; + t_assertSuccess(H3_EXPORT(maxFaceCount)(invalid, &sz)); + int *faces = calloc(sz, sizeof(int)); + t_assert(H3_EXPORT(getIcosahedronFaces)(invalid, faces) == E_FAILED, + "Invalid cell"); + free(faces); } } diff --git a/src/h3lib/lib/h3Index.c b/src/h3lib/lib/h3Index.c index 68bb4a705a..f599c5bc59 100644 --- a/src/h3lib/lib/h3Index.c +++ b/src/h3lib/lib/h3Index.c @@ -986,7 +986,14 @@ H3Error H3_EXPORT(getIcosahedronFaces)(H3Index h3, int *out) { int pos = 0; // Find the first empty output position, or the first position // matching the current face - while (out[pos] != INVALID_FACE && out[pos] != face) pos++; + while (out[pos] != INVALID_FACE && out[pos] != face) { + pos++; + if (pos >= faceCount) { + // Mismatch between the heuristic used in maxFaceCount and + // calculation here - indicates an invalid index. + return E_FAILED; + } + } out[pos] = face; } return E_SUCCESS; From d501e51634805fb5c903cf34303055f1483ffe95 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Mon, 3 Jan 2022 15:11:41 -0800 Subject: [PATCH 30/33] Don't assert specific error in testVertex --- src/apps/testapps/testVertex.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/src/apps/testapps/testVertex.c b/src/apps/testapps/testVertex.c index 7c752dd5fe..4bb6c98fee 100644 --- a/src/apps/testapps/testVertex.c +++ b/src/apps/testapps/testVertex.c @@ -103,7 +103,8 @@ SUITE(Vertex) { TEST(cellToVertex_invalid) { H3Index invalid = 0xFFFFFFFFFFFFFFFF; H3Index vert; - t_assert(H3_EXPORT(cellToVertex)(invalid, 3, &vert) == E_CELL_INVALID, + // TODO: Assert specific error + t_assert(H3_EXPORT(cellToVertex)(invalid, 3, &vert) != E_SUCCESS, "Invalid cell returns error"); } From d3261563d6e4e062a23239cd15be1cfecc2e6492 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Tue, 11 Jan 2022 09:47:42 -0800 Subject: [PATCH 31/33] Add polygonToCellsNoHoles fuzzer --- CMakeLists.txt | 2 + src/apps/fuzzers/fuzzerPolygonToCells.c | 6 +- .../fuzzers/fuzzerPolygonToCellsNoHoles.c | 61 +++++++++++++++++++ 3 files changed, 67 insertions(+), 2 deletions(-) create mode 100644 src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c diff --git a/CMakeLists.txt b/CMakeLists.txt index c5f14c69c8..39ea6be037 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -240,6 +240,7 @@ set(OTHER_SOURCE_FILES src/apps/fuzzers/fuzzerDirectedEdge.c src/apps/fuzzers/fuzzerLocalIj.c src/apps/fuzzers/fuzzerPolygonToCells.c + src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c src/apps/benchmarks/benchmarkPolygonToCells.c src/apps/benchmarks/benchmarkPolygon.c src/apps/benchmarks/benchmarkH3SetToLinkedGeo.c @@ -678,6 +679,7 @@ if(BUILD_FUZZERS) add_h3_fuzzer(fuzzerDirectedEdge src/apps/fuzzers/fuzzerDirectedEdge.c) add_h3_fuzzer(fuzzerLocalIj src/apps/fuzzers/fuzzerLocalIj.c) add_h3_fuzzer(fuzzerPolygonToCells src/apps/fuzzers/fuzzerPolygonToCells.c) + add_h3_fuzzer(fuzzerPolygonToCellsNoHoles src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c) endif() if(BUILD_BENCHMARKS) diff --git a/src/apps/fuzzers/fuzzerPolygonToCells.c b/src/apps/fuzzers/fuzzerPolygonToCells.c index 1110d025ca..9bfaea53b0 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCells.c +++ b/src/apps/fuzzers/fuzzerPolygonToCells.c @@ -25,7 +25,7 @@ typedef struct { int res; int numHoles; // repeating: num verts, verts - // We add a large fixed buffer so our test case generator for AL + // We add a large fixed buffer so our test case generator for AFL // knows how large to make the file. uint8_t buffer[1024]; } inputArgs; @@ -65,6 +65,8 @@ void run(GeoPolygon *geoPolygon, int res) { } int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + // TODO: It is difficult for the fuzzer to generate inputs that are considered + // valid by this fuzzer. if (size < sizeof(inputArgs)) { return 0; } @@ -77,7 +79,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { return 0; } geoPolygon.holes = calloc(geoPolygon.numHoles, sizeof(GeoLoop)); - size_t offset = sizeof(inputArgs); + size_t offset = sizeof(inputArgs) - sizeof(args->buffer); if (populateGeoLoop(&geoPolygon.geoloop, data, &offset, size)) { free(geoPolygon.holes); return 0; diff --git a/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c b/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c new file mode 100644 index 0000000000..42b330939d --- /dev/null +++ b/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c @@ -0,0 +1,61 @@ +/* + * Copyright 2022 Uber Technologies, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** @file + * @brief Fuzzer program for polygonToCells and related functions, without holes + */ + +#include "aflHarness.h" +#include "h3api.h" +#include "utility.h" + +const int MAX_RES = 15; +const int MAX_SZ = 4000000; + +void run(GeoPolygon *geoPolygon, int res) { + int64_t sz; + H3Error err = H3_EXPORT(maxPolygonToCellsSize)(geoPolygon, res, &sz); + if (!err && sz < MAX_SZ) { + if (sz < 0) { + // TODO: Check on this once rebased + printf("Oh no - sz is negative\n"); + } + H3Index *out = calloc(sz, sizeof(H3Index)); + H3_EXPORT(polygonToCells)(geoPolygon, res, out); + free(out); + } +} + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(int)) { + return 0; + } + + uint8_t res = *data; + size_t vertsSize = size - 1; + int numVerts = vertsSize / sizeof(LatLng); + + GeoPolygon geoPolygon; + geoPolygon.numHoles = 0; + geoPolygon.holes = NULL; + geoPolygon.geoloop.numVerts = numVerts; + geoPolygon.geoloop.verts = (LatLng *)(data + 1); + + run(&geoPolygon, res); + + return 0; +} + +AFL_HARNESS_MAIN(sizeof(H3Index) * 1024); From 558a37f1633ede20fa0412f114793bc283f112a0 Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Tue, 11 Jan 2022 11:22:19 -0800 Subject: [PATCH 32/33] fix formatting --- src/apps/fuzzers/fuzzerPolygonToCells.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/apps/fuzzers/fuzzerPolygonToCells.c b/src/apps/fuzzers/fuzzerPolygonToCells.c index 9bfaea53b0..919f0852ae 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCells.c +++ b/src/apps/fuzzers/fuzzerPolygonToCells.c @@ -65,8 +65,8 @@ void run(GeoPolygon *geoPolygon, int res) { } int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { - // TODO: It is difficult for the fuzzer to generate inputs that are considered - // valid by this fuzzer. + // TODO: It is difficult for the fuzzer to generate inputs that are + // considered valid by this fuzzer. if (size < sizeof(inputArgs)) { return 0; } From c20e860f6e865d0fa8e623bcf769bb4853feea3e Mon Sep 17 00:00:00 2001 From: Isaac Brodsky Date: Sun, 23 Jan 2022 09:29:24 -0800 Subject: [PATCH 33/33] Mainly comment only changes --- src/apps/fuzzers/fuzzerPolygonToCells.c | 7 ++----- src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c | 5 +---- 2 files changed, 3 insertions(+), 9 deletions(-) diff --git a/src/apps/fuzzers/fuzzerPolygonToCells.c b/src/apps/fuzzers/fuzzerPolygonToCells.c index 919f0852ae..88b9b7fd01 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCells.c +++ b/src/apps/fuzzers/fuzzerPolygonToCells.c @@ -54,10 +54,6 @@ void run(GeoPolygon *geoPolygon, int res) { int64_t sz; H3Error err = H3_EXPORT(maxPolygonToCellsSize)(geoPolygon, res, &sz); if (!err && sz < MAX_SZ) { - if (sz < 0) { - // TODO: Check on this once rebased - printf("Oh no - sz is negative\n"); - } H3Index *out = calloc(sz, sizeof(H3Index)); H3_EXPORT(polygonToCells)(geoPolygon, res, out); free(out); @@ -66,7 +62,8 @@ void run(GeoPolygon *geoPolygon, int res) { int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { // TODO: It is difficult for the fuzzer to generate inputs that are - // considered valid by this fuzzer. + // considered valid by this fuzzer. fuzzerPolygonToCellsNoHoles.c + // is a workaround for that. if (size < sizeof(inputArgs)) { return 0; } diff --git a/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c b/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c index 42b330939d..17155b0bff 100644 --- a/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c +++ b/src/apps/fuzzers/fuzzerPolygonToCellsNoHoles.c @@ -28,10 +28,6 @@ void run(GeoPolygon *geoPolygon, int res) { int64_t sz; H3Error err = H3_EXPORT(maxPolygonToCellsSize)(geoPolygon, res, &sz); if (!err && sz < MAX_SZ) { - if (sz < 0) { - // TODO: Check on this once rebased - printf("Oh no - sz is negative\n"); - } H3Index *out = calloc(sz, sizeof(H3Index)); H3_EXPORT(polygonToCells)(geoPolygon, res, out); free(out); @@ -51,6 +47,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { geoPolygon.numHoles = 0; geoPolygon.holes = NULL; geoPolygon.geoloop.numVerts = numVerts; + // Offset by 1 since *data was used for `res`, above. geoPolygon.geoloop.verts = (LatLng *)(data + 1); run(&geoPolygon, res);