diff options
Diffstat (limited to 'src/main/java/com/code_intelligence/jazzer/mutation/mutator')
26 files changed, 3738 insertions, 0 deletions
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/BUILD.bazel new file mode 100644 index 00000000..b922a86a --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/BUILD.bazel @@ -0,0 +1,14 @@ +java_library( + name = "mutator", + srcs = glob(["*.java"]), + visibility = ["//visibility:public"], + deps = [ + "//src/main/java/com/code_intelligence/jazzer/api", + "//src/main/java/com/code_intelligence/jazzer/mutation/annotation", + "//src/main/java/com/code_intelligence/jazzer/mutation/api", + "//src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection", + "//src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang", + "//src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto", + "//src/main/java/com/code_intelligence/jazzer/mutation/support", + ], +) diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/Mutators.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/Mutators.java new file mode 100644 index 00000000..fcc4d7ea --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/Mutators.java @@ -0,0 +1,81 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator; + +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.visitAnnotatedType; +import static java.lang.String.format; +import static java.util.Arrays.stream; +import static java.util.stream.Collectors.joining; + +import com.code_intelligence.jazzer.mutation.annotation.AppliesTo; +import com.code_intelligence.jazzer.mutation.api.ChainedMutatorFactory; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; +import com.code_intelligence.jazzer.mutation.mutator.collection.CollectionMutators; +import com.code_intelligence.jazzer.mutation.mutator.lang.LangMutators; +import com.code_intelligence.jazzer.mutation.mutator.proto.ProtoMutators; +import java.lang.annotation.Annotation; +import java.lang.reflect.AnnotatedType; + +public final class Mutators { + private Mutators() {} + + public static MutatorFactory newFactory() { + return new ChainedMutatorFactory( + LangMutators.newFactory(), CollectionMutators.newFactory(), ProtoMutators.newFactory()); + } + + /** + * Throws an exception if any annotation on {@code type} violates the restrictions of its + * {@link AppliesTo} meta-annotation. + */ + public static void validateAnnotationUsage(AnnotatedType type) { + visitAnnotatedType(type, (clazz, annotations) -> { + outer: + for (Annotation annotation : annotations) { + AppliesTo appliesTo = annotation.annotationType().getAnnotation(AppliesTo.class); + if (appliesTo == null) { + continue; + } + for (Class<?> allowedClass : appliesTo.value()) { + if (allowedClass == clazz) { + continue outer; + } + } + for (Class<?> allowedSuperClass : appliesTo.subClassesOf()) { + if (allowedSuperClass.isAssignableFrom(clazz)) { + continue outer; + } + } + + String helpText = ""; + if (appliesTo.value().length != 0) { + helpText = stream(appliesTo.value()).map(Class::getName).collect(joining(", ")); + } + if (appliesTo.subClassesOf().length != 0) { + if (!helpText.isEmpty()) { + helpText += "as well as "; + } + helpText += "subclasses of "; + helpText += stream(appliesTo.subClassesOf()).map(Class::getName).collect(joining(", ")); + } + // Use the simple name as our annotations live in a single package. + throw new IllegalArgumentException(format("%s does not apply to %s, only applies to %s", + annotation.annotationType().getSimpleName(), clazz.getName(), helpText)); + } + }); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/BUILD.bazel new file mode 100644 index 00000000..288b700a --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/BUILD.bazel @@ -0,0 +1,13 @@ +java_library( + name = "collection", + srcs = glob(["*.java"]), + visibility = [ + "//src/main/java/com/code_intelligence/jazzer/mutation/mutator:__pkg__", + "//src/test/java/com/code_intelligence/jazzer/mutation/mutator:__subpackages__", + ], + deps = [ + "//src/main/java/com/code_intelligence/jazzer/mutation/annotation", + "//src/main/java/com/code_intelligence/jazzer/mutation/api", + "//src/main/java/com/code_intelligence/jazzer/mutation/support", + ], +) diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkCrossOvers.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkCrossOvers.java new file mode 100644 index 00000000..c124f517 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkCrossOvers.java @@ -0,0 +1,226 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.collection; + +import com.code_intelligence.jazzer.mutation.api.PseudoRandom; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Iterator; +import java.util.LinkedHashMap; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; + +final class ChunkCrossOvers { + private ChunkCrossOvers() {} + + static <T> void insertChunk(List<T> list, List<T> otherList, int maxSize, PseudoRandom prng) { + int maxChunkSize = Math.min(maxSize - list.size(), Math.min(list.size(), otherList.size())); + withChunk(list, otherList, maxChunkSize, prng, + (fromPos, toPos, chunk) -> { list.addAll(toPos, chunk); }); + } + + static <T> void overwriteChunk(List<T> list, List<T> otherList, PseudoRandom prng) { + int maxChunkSize = Math.min(list.size(), otherList.size()); + withChunkElements(list, otherList, maxChunkSize, prng, list::set); + } + + static <T> void crossOverChunk( + List<T> list, List<T> otherList, SerializingMutator<T> elementMutator, PseudoRandom prng) { + int maxChunkSize = Math.min(list.size(), otherList.size()); + withChunkElements(list, otherList, maxChunkSize, prng, (toPos, element) -> { + list.set(toPos, elementMutator.crossOver(list.get(toPos), element, prng)); + }); + } + + @FunctionalInterface + private interface ChunkListOperation<T> { + void apply(int fromPos, int toPos, List<T> chunk); + } + + @FunctionalInterface + private interface ChunkListElementOperation<T> { + void apply(int toPos, T chunk); + } + + static private <T> void withChunk(List<T> list, List<T> otherList, int maxChunkSize, + PseudoRandom prng, ChunkListOperation<T> operation) { + if (maxChunkSize == 0) { + return; + } + int chunkSize = prng.closedRangeBiasedTowardsSmall(1, maxChunkSize); + int fromPos = prng.closedRange(0, otherList.size() - chunkSize); + int toPos = prng.closedRange(0, list.size() - chunkSize); + List<T> chunk = otherList.subList(fromPos, fromPos + chunkSize); + operation.apply(fromPos, toPos, chunk); + } + + static private <T> void withChunkElements(List<T> list, List<T> otherList, int maxChunkSize, + PseudoRandom prng, ChunkListElementOperation<T> operation) { + withChunk(list, otherList, maxChunkSize, prng, (fromPos, toPos, chunk) -> { + for (int i = 0; i < chunk.size(); i++) { + operation.apply(toPos + i, chunk.get(i)); + } + }); + } + + static <K, V> void insertChunk( + Map<K, V> map, Map<K, V> otherMap, int maxSize, PseudoRandom prng) { + int originalSize = map.size(); + int maxChunkSize = Math.min(maxSize - originalSize, otherMap.size()); + withChunk(map, otherMap, maxChunkSize, prng, (fromIterator, toIterator, chunkSize) -> { + // insertChunk only inserts new entries and does not overwrite existing + // ones. As skipping those entries would lead to fewer insertions than + // requested, loop over the rest of the map to fill the chunk. + while (map.size() < originalSize + chunkSize && fromIterator.hasNext()) { + Entry<K, V> entry = fromIterator.next(); + if (!map.containsKey(entry.getKey())) { + map.put(entry.getKey(), entry.getValue()); + } + } + }); + } + + static <K, V> void overwriteChunk(Map<K, V> map, Map<K, V> otherMap, PseudoRandom prng) { + int maxChunkSize = Math.min(map.size(), otherMap.size()); + withChunk(map, otherMap, maxChunkSize, prng, (fromIterator, toIterator, chunkSize) -> { + // As keys can not be overwritten, only removed and new ones added, this + // cross over overwrites the values. Removal of keys is handled by the + // removeChunk mutation. Value equality is not checked here. + for (int i = 0; i < chunkSize; i++) { + Entry<K, V> from = fromIterator.next(); + Entry<K, V> to = toIterator.next(); + to.setValue(from.getValue()); + } + }); + } + + static <K, V> void crossOverChunk(Map<K, V> map, Map<K, V> otherMap, + SerializingMutator<K> keyMutator, SerializingMutator<V> valueMutator, PseudoRandom prng) { + if (prng.choice()) { + crossOverChunkKeys(map, otherMap, keyMutator, prng); + } else { + crossOverChunkValues(map, otherMap, valueMutator, prng); + } + } + + private static <K, V> void crossOverChunkKeys( + Map<K, V> map, Map<K, V> otherMap, SerializingMutator<K> keyMutator, PseudoRandom prng) { + int maxChunkSize = Math.min(map.size(), otherMap.size()); + withChunk(map, otherMap, maxChunkSize, prng, (fromIterator, toIterator, chunkSize) -> { + Map<K, V> entriesToAdd = new LinkedHashMap<>(chunkSize); + for (int i = 0; i < chunkSize; i++) { + Entry<K, V> to = toIterator.next(); + Entry<K, V> from = fromIterator.next(); + + // The entry has to be removed from the map before the cross-over, as + // mutating its key could cause problems in subsequent lookups. + // Furthermore, no new entries may be added while using the iterator, + // so crossed-over keys are collected for later addition. + K key = to.getKey(); + V value = to.getValue(); + toIterator.remove(); + + // As cross-overs do not guarantee to mutate the given object, no + // checks if the crossed over key already exists in the map are + // performed. This potentially overwrites existing entries or + // generates equal keys. + // In case of cross over this behavior is acceptable. + K newKey = keyMutator.crossOver(key, from.getKey(), prng); + + // Prevent null keys, as those are not allowed in some map implementations. + if (newKey != null) { + entriesToAdd.put(newKey, value); + } + } + map.putAll(entriesToAdd); + }); + } + + private static <K, V> void crossOverChunkValues( + Map<K, V> map, Map<K, V> otherMap, SerializingMutator<V> valueMutator, PseudoRandom prng) { + int maxChunkSize = Math.min(map.size(), otherMap.size()); + withChunkElements(map, otherMap, maxChunkSize, prng, (fromEntry, toEntry) -> { + // As cross-overs do not guarantee to mutate the given object, no + // checks if a new value is produced are performed. + V newValue = valueMutator.crossOver(toEntry.getValue(), fromEntry.getValue(), prng); + + // The cross-over could have already mutated value, but explicitly set it + // through the iterator to be sure. + toEntry.setValue(newValue); + }); + } + + @FunctionalInterface + private interface ChunkMapOperation<K, V> { + void apply(Iterator<Entry<K, V>> fromIterator, Iterator<Entry<K, V>> toIterator, int chunkSize); + } + + @FunctionalInterface + private interface ChunkMapElementOperation<K, V> { + void apply(Entry<K, V> fromEntry, Entry<K, V> toEntry); + } + + static <K, V> void withChunk(Map<K, V> map, Map<K, V> otherMap, int maxChunkSize, + PseudoRandom prng, ChunkMapOperation<K, V> operation) { + int chunkSize = prng.closedRangeBiasedTowardsSmall(1, maxChunkSize); + int fromChunkOffset = prng.closedRange(0, otherMap.size() - chunkSize); + int toChunkOffset = prng.closedRange(0, map.size() - chunkSize); + Iterator<Entry<K, V>> fromIterator = otherMap.entrySet().iterator(); + for (int i = 0; i < fromChunkOffset; i++) { + fromIterator.next(); + } + Iterator<Entry<K, V>> toIterator = map.entrySet().iterator(); + for (int i = 0; i < toChunkOffset; i++) { + toIterator.next(); + } + operation.apply(fromIterator, toIterator, chunkSize); + } + + static <K, V> void withChunkElements(Map<K, V> map, Map<K, V> otherMap, int maxChunkSize, + PseudoRandom prng, ChunkMapElementOperation<K, V> operation) { + withChunk(map, otherMap, maxChunkSize, prng, (fromIterator, toIterator, chunkSize) -> { + for (int i = 0; i < chunkSize; i++) { + operation.apply(fromIterator.next(), toIterator.next()); + } + }); + } + + public enum CrossOverAction { + INSERT_CHUNK, + OVERWRITE_CHUNK, + CROSS_OVER_CHUNK, + NOOP; + + public static CrossOverAction pickRandomCrossOverAction( + Collection<?> reference, Collection<?> otherReference, int maxSize, PseudoRandom prng) { + List<CrossOverAction> actions = new ArrayList<>(); + if (reference.size() < maxSize && !otherReference.isEmpty()) { + actions.add(INSERT_CHUNK); + } + if (!reference.isEmpty() && !otherReference.isEmpty()) { + actions.add(OVERWRITE_CHUNK); + actions.add(CROSS_OVER_CHUNK); + } + if (actions.isEmpty()) { + return NOOP; // prevent NPE + } + return prng.pickIn(actions); + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkMutations.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkMutations.java new file mode 100644 index 00000000..d5260289 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ChunkMutations.java @@ -0,0 +1,243 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.collection; + +import com.code_intelligence.jazzer.mutation.api.PseudoRandom; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import com.code_intelligence.jazzer.mutation.api.ValueMutator; +import com.code_intelligence.jazzer.mutation.support.Preconditions; +import java.util.AbstractList; +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Set; +import java.util.function.Consumer; +import java.util.function.Supplier; + +// Based on (Apache-2.0) +// https://github.com/google/fuzztest/blob/f81257ed70ec7b9c191b633588cb6e39c42da5e4/fuzztest/internal/domains/container_mutation_helpers.h +@SuppressWarnings("unchecked") +final class ChunkMutations { + private static final int MAX_FAILED_INSERTION_ATTEMPTS = 100; + + private ChunkMutations() {} + + static <T> void deleteRandomChunk(List<T> list, int minSize, PseudoRandom prng) { + int oldSize = list.size(); + int minFinalSize = Math.max(minSize, oldSize / 2); + int chunkSize = prng.closedRangeBiasedTowardsSmall(1, oldSize - minFinalSize); + int chunkOffset = prng.closedRange(0, oldSize - chunkSize); + + list.subList(chunkOffset, chunkOffset + chunkSize).clear(); + } + + static <T> void deleteRandomChunk(Collection<T> collection, int minSize, PseudoRandom prng) { + int oldSize = collection.size(); + int minFinalSize = Math.max(minSize, oldSize / 2); + int chunkSize = prng.closedRangeBiasedTowardsSmall(1, oldSize - minFinalSize); + int chunkOffset = prng.closedRange(0, oldSize - chunkSize); + + Iterator<T> it = collection.iterator(); + for (int i = 0; i < chunkOffset; i++) { + it.next(); + } + for (int i = chunkOffset; i < chunkOffset + chunkSize; i++) { + it.next(); + it.remove(); + } + } + + static <T> void insertRandomChunk( + List<T> list, int maxSize, SerializingMutator<T> elementMutator, PseudoRandom prng) { + int oldSize = list.size(); + int chunkSize = prng.closedRangeBiasedTowardsSmall(1, maxSize - oldSize); + int chunkOffset = prng.closedRange(0, oldSize); + + T baseElement = elementMutator.init(prng); + T[] chunk = (T[]) new Object[chunkSize]; + for (int i = 0; i < chunk.length; i++) { + chunk[i] = elementMutator.detach(baseElement); + } + // ArrayList#addAll relies on Collection#toArray, but Arrays#asList returns a List whose + // toArray() always makes a copy. We avoid this by using a custom list implementation. + list.addAll(chunkOffset, new ArraySharingList<>(chunk)); + } + + static <T> boolean insertRandomChunk(Set<T> set, Consumer<T> addIfNew, int maxSize, + ValueMutator<T> elementMutator, PseudoRandom prng) { + int oldSize = set.size(); + int chunkSize = prng.closedRangeBiasedTowardsSmall(1, maxSize - oldSize); + return growBy(set, addIfNew, chunkSize, () -> elementMutator.init(prng)); + } + + static <T> void mutateRandomChunk(List<T> list, ValueMutator<T> mutator, PseudoRandom prng) { + int size = list.size(); + int chunkSize = prng.closedRangeBiasedTowardsSmall(1, size); + int chunkOffset = prng.closedRange(0, size - chunkSize); + + for (int i = chunkOffset; i < chunkOffset + chunkSize; i++) { + list.set(i, mutator.mutate(list.get(i), prng)); + } + } + + static <K, V, KW, VW> boolean mutateRandomKeysChunk( + Map<K, V> map, SerializingMutator<K> keyMutator, PseudoRandom prng) { + int originalSize = map.size(); + int chunkSize = prng.closedRangeBiasedTowardsSmall(1, originalSize); + int chunkOffset = prng.closedRange(0, originalSize - chunkSize); + + // To ensure that mutating keys actually results in the set of keys changing and not just their + // values (which is what #mutateRandomValuesChunk is for), we keep the keys to mutate in the + // map, try to add new keys (that are therefore distinct from the keys to mutate) and only + // remove the successfully mutated keys in the end. + ArrayDeque<KW> keysToMutate = new ArrayDeque<>(chunkSize); + ArrayDeque<VW> values = new ArrayDeque<>(chunkSize); + ArrayList<K> keysToRemove = new ArrayList<>(chunkSize); + Iterator<Map.Entry<K, V>> it = map.entrySet().iterator(); + for (int i = 0; i < chunkOffset; i++) { + it.next(); + } + for (int i = chunkOffset; i < chunkOffset + chunkSize; i++) { + Map.Entry<K, V> entry = it.next(); + // ArrayDeque cannot hold null elements, which requires us to replace null with a sentinel. + // Also detach the key as keys may be mutable and mutation could destroy them. + keysToMutate.add(boxNull(keyMutator.detach(entry.getKey()))); + values.add(boxNull(entry.getValue())); + keysToRemove.add(entry.getKey()); + } + + Consumer<K> addIfNew = key -> { + int sizeBeforeAdd = map.size(); + map.putIfAbsent(key, unboxNull(values.peekFirst())); + // The mutated key was new, try to mutate and add the next in line. + if (map.size() > sizeBeforeAdd) { + keysToMutate.removeFirst(); + values.removeFirst(); + } + }; + Supplier<K> nextCandidate = () -> { + // Mutate the next candidate in the queue. + K candidate = keyMutator.mutate(unboxNull(keysToMutate.removeFirst()), prng); + keysToMutate.addFirst(boxNull(candidate)); + return candidate; + }; + + growBy(map.keySet(), addIfNew, chunkSize, nextCandidate); + // Remove the original keys that were successfully mutated into new keys. Since the original + // keys have been kept in the map up to this point, all keys added were successfully mutated to + // be unequal to the original keys. + int grownBy = map.size() - originalSize; + keysToRemove.stream().limit(grownBy).forEach(map::remove); + return grownBy > 0; + } + + public static <K, V> void mutateRandomValuesChunk( + Map<K, V> map, ValueMutator<V> valueMutator, PseudoRandom prng) { + Collection<Map.Entry<K, V>> collection = map.entrySet(); + int oldSize = collection.size(); + int chunkSize = prng.closedRangeBiasedTowardsSmall(1, oldSize); + int chunkOffset = prng.closedRange(0, oldSize - chunkSize); + + Iterator<Map.Entry<K, V>> it = collection.iterator(); + for (int i = 0; i < chunkOffset; i++) { + it.next(); + } + for (int i = chunkOffset; i < chunkOffset + chunkSize; i++) { + Entry<K, V> entry = it.next(); + entry.setValue(valueMutator.mutate(entry.getValue(), prng)); + } + } + + static <T> boolean growBy( + Set<T> set, Consumer<T> addIfNew, int delta, Supplier<T> candidateSupplier) { + int oldSize = set.size(); + Preconditions.require(delta >= 0); + + final int targetSize = oldSize + delta; + int remainingAttempts = MAX_FAILED_INSERTION_ATTEMPTS; + int currentSize = set.size(); + while (currentSize < targetSize) { + // If addIfNew fails, the size of set will not increase. + addIfNew.accept(candidateSupplier.get()); + int newSize = set.size(); + if (newSize == currentSize && remainingAttempts-- == 0) { + return false; + } else { + currentSize = newSize; + } + } + return true; + } + + private static final Object BOXED_NULL = new Object(); + + private static <T, TW> TW boxNull(T object) { + return object != null ? (TW) object : (TW) BOXED_NULL; + } + + private static <T, TW> T unboxNull(TW object) { + return object != BOXED_NULL ? (T) object : null; + } + + public enum MutationAction { + DELETE_CHUNK, + INSERT_CHUNK, + MUTATE_CHUNK; + + public static MutationAction pickRandomMutationAction( + Collection<?> c, int minSize, int maxSize, PseudoRandom prng) { + List<MutationAction> actions = new ArrayList<>(); + if (c.size() > minSize) { + actions.add(DELETE_CHUNK); + } + if (c.size() < maxSize) { + actions.add(INSERT_CHUNK); + } + if (!c.isEmpty()) { + actions.add(MUTATE_CHUNK); + } + return prng.pickIn(actions); + } + } + + private static final class ArraySharingList<T> extends AbstractList<T> { + private final T[] array; + + ArraySharingList(T[] array) { + this.array = array; + } + + @Override + public T get(int i) { + return array[i]; + } + + @Override + public int size() { + return array.length; + } + + @Override + public Object[] toArray() { + return array; + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/CollectionMutators.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/CollectionMutators.java new file mode 100644 index 00000000..cf819f11 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/CollectionMutators.java @@ -0,0 +1,28 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.collection; + +import com.code_intelligence.jazzer.mutation.api.ChainedMutatorFactory; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; + +public final class CollectionMutators { + private CollectionMutators() {} + + public static MutatorFactory newFactory() { + return new ChainedMutatorFactory(new ListMutatorFactory(), new MapMutatorFactory()); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ListMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ListMutatorFactory.java new file mode 100644 index 00000000..86ecbd4f --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/ListMutatorFactory.java @@ -0,0 +1,167 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.collection; + +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.CrossOverAction.pickRandomCrossOverAction; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.crossOverChunk; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.insertChunk; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.overwriteChunk; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.MutationAction.pickRandomMutationAction; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.deleteRandomChunk; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.insertRandomChunk; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.mutateRandomChunk; +import static com.code_intelligence.jazzer.mutation.support.Preconditions.require; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.parameterTypeIfParameterized; +import static java.lang.Math.min; +import static java.lang.String.format; + +import com.code_intelligence.jazzer.mutation.annotation.WithSize; +import com.code_intelligence.jazzer.mutation.api.Debuggable; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; +import com.code_intelligence.jazzer.mutation.api.PseudoRandom; +import com.code_intelligence.jazzer.mutation.api.SerializingInPlaceMutator; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import com.code_intelligence.jazzer.mutation.support.RandomSupport; +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.lang.reflect.AnnotatedType; +import java.util.ArrayList; +import java.util.List; +import java.util.Optional; +import java.util.function.Predicate; +import java.util.stream.Collectors; + +final class ListMutatorFactory extends MutatorFactory { + @Override + public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) { + Optional<WithSize> withSize = Optional.ofNullable(type.getAnnotation(WithSize.class)); + int minSize = withSize.map(WithSize::min).orElse(ListMutator.DEFAULT_MIN_SIZE); + int maxSize = withSize.map(WithSize::max).orElse(ListMutator.DEFAULT_MAX_SIZE); + return parameterTypeIfParameterized(type, List.class) + .flatMap(factory::tryCreate) + .map(elementMutator -> new ListMutator<>(elementMutator, minSize, maxSize)); + } + + private static final class ListMutator<T> extends SerializingInPlaceMutator<List<T>> { + private static final int DEFAULT_MIN_SIZE = 0; + private static final int DEFAULT_MAX_SIZE = 1000; + + private final SerializingMutator<T> elementMutator; + private final int minSize; + private final int maxSize; + + ListMutator(SerializingMutator<T> elementMutator, int minSize, int maxSize) { + this.elementMutator = elementMutator; + this.minSize = minSize; + this.maxSize = maxSize; + require(maxSize >= 1, format("WithSize#max=%d needs to be greater than 0", maxSize)); + require(minSize >= 0, format("WithSize#min=%d needs to be positive", minSize)); + require(minSize <= maxSize, + format("WithSize#min=%d needs to be smaller or equal than WithSize#max=%d", minSize, + maxSize)); + } + + @Override + public List<T> read(DataInputStream in) throws IOException { + int size = RandomSupport.clamp(in.readInt(), minSize, maxSize); + ArrayList<T> list = new ArrayList<>(size); + for (int i = 0; i < size; i++) { + list.add(elementMutator.read(in)); + } + return list; + } + + @Override + public void write(List<T> list, DataOutputStream out) throws IOException { + out.writeInt(list.size()); + for (T element : list) { + elementMutator.write(element, out); + } + } + + @Override + protected List<T> makeDefaultInstance() { + return new ArrayList<>(maxInitialSize()); + } + + @Override + public void initInPlace(List<T> list, PseudoRandom prng) { + int targetSize = prng.closedRange(minInitialSize(), maxInitialSize()); + list.clear(); + for (int i = 0; i < targetSize; i++) { + list.add(elementMutator.init(prng)); + } + } + + @Override + public void mutateInPlace(List<T> list, PseudoRandom prng) { + switch (pickRandomMutationAction(list, minSize, maxSize, prng)) { + case DELETE_CHUNK: + deleteRandomChunk(list, minSize, prng); + break; + case INSERT_CHUNK: + insertRandomChunk(list, maxSize, elementMutator, prng); + break; + case MUTATE_CHUNK: + mutateRandomChunk(list, elementMutator, prng); + break; + default: + throw new IllegalStateException("unsupported action"); + } + } + + @Override + public void crossOverInPlace(List<T> reference, List<T> otherReference, PseudoRandom prng) { + // These cross-over functions don't remove entries, that is handled by + // the appropriate mutations on the result. + switch (pickRandomCrossOverAction(reference, otherReference, maxSize, prng)) { + case INSERT_CHUNK: + insertChunk(reference, otherReference, maxSize, prng); + break; + case OVERWRITE_CHUNK: + overwriteChunk(reference, otherReference, prng); + break; + case CROSS_OVER_CHUNK: + crossOverChunk(reference, otherReference, elementMutator, prng); + break; + default: + // Both lists are empty or could otherwise not be crossed over. + } + } + + @Override + public List<T> detach(List<T> value) { + return value.stream() + .map(elementMutator::detach) + .collect(Collectors.toCollection(() -> new ArrayList<>(value.size()))); + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return "List<" + elementMutator.toDebugString(isInCycle) + ">"; + } + + private int minInitialSize() { + return minSize; + } + + private int maxInitialSize() { + return min(maxSize, minSize + 1); + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/MapMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/MapMutatorFactory.java new file mode 100644 index 00000000..fca8b5cb --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/collection/MapMutatorFactory.java @@ -0,0 +1,205 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.collection; + +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.CrossOverAction.pickRandomCrossOverAction; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.crossOverChunk; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.insertChunk; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkCrossOvers.overwriteChunk; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.MutationAction.pickRandomMutationAction; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.deleteRandomChunk; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.growBy; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.insertRandomChunk; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.mutateRandomKeysChunk; +import static com.code_intelligence.jazzer.mutation.mutator.collection.ChunkMutations.mutateRandomValuesChunk; +import static com.code_intelligence.jazzer.mutation.support.Preconditions.check; +import static com.code_intelligence.jazzer.mutation.support.Preconditions.require; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.parameterTypesIfParameterized; +import static java.lang.Math.min; +import static java.lang.String.format; +import static java.util.stream.Collectors.toMap; + +import com.code_intelligence.jazzer.mutation.annotation.WithSize; +import com.code_intelligence.jazzer.mutation.api.Debuggable; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; +import com.code_intelligence.jazzer.mutation.api.PseudoRandom; +import com.code_intelligence.jazzer.mutation.api.SerializingInPlaceMutator; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import com.code_intelligence.jazzer.mutation.support.RandomSupport; +import com.code_intelligence.jazzer.mutation.support.StreamSupport; +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.lang.annotation.Annotation; +import java.lang.reflect.AnnotatedType; +import java.util.LinkedHashMap; +import java.util.Map; +import java.util.Optional; +import java.util.function.Predicate; +import java.util.stream.Collectors; + +final class MapMutatorFactory extends MutatorFactory { + @Override + public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) { + return parameterTypesIfParameterized(type, Map.class) + .map(parameterTypes + -> parameterTypes.stream() + .map(factory::tryCreate) + .flatMap(StreamSupport::getOrEmpty) + .collect(Collectors.toList())) + .map(elementMutators -> { + check(elementMutators.size() == 2); + int min = MapMutator.DEFAULT_MIN_SIZE; + int max = MapMutator.DEFAULT_MAX_SIZE; + for (Annotation annotation : type.getDeclaredAnnotations()) { + if (annotation instanceof WithSize) { + WithSize withSize = (WithSize) annotation; + min = withSize.min(); + max = withSize.max(); + } + } + return new MapMutator<>(elementMutators.get(0), elementMutators.get(1), min, max); + }); + } + + private static final class MapMutator<K, V> extends SerializingInPlaceMutator<Map<K, V>> { + private static final int DEFAULT_MIN_SIZE = 0; + private static final int DEFAULT_MAX_SIZE = 1000; + + private final SerializingMutator<K> keyMutator; + private final SerializingMutator<V> valueMutator; + private final int minSize; + private final int maxSize; + + MapMutator(SerializingMutator<K> keyMutator, SerializingMutator<V> valueMutator, int minSize, + int maxSize) { + this.keyMutator = keyMutator; + this.valueMutator = valueMutator; + this.minSize = Math.max(minSize, DEFAULT_MIN_SIZE); + this.maxSize = Math.min(maxSize, DEFAULT_MAX_SIZE); + + require(maxSize >= 1, format("WithSize#max=%d needs to be greater than 0", maxSize)); + // TODO: Add support for min > 0 to map. If min > 0, then #read can fail to construct + // sufficiently many distinct keys, but the mutation framework currently doesn't offer + // a way to handle this situation gracefully. It is also not clear what behavior users + // could reasonably expect in this situation in both regression test and fuzzing mode. + require(minSize == 0, "@WithSize#min != 0 is not yet supported for Map"); + } + + @Override + public Map<K, V> read(DataInputStream in) throws IOException { + int size = RandomSupport.clamp(in.readInt(), minSize, maxSize); + Map<K, V> map = new LinkedHashMap<>(size); + for (int i = 0; i < size; i++) { + map.put(keyMutator.read(in), valueMutator.read(in)); + } + // map may have less than size entries due to the potential for duplicates, but this is fine + // as we currently assert that minSize == 0. + return map; + } + + @Override + public void write(Map<K, V> map, DataOutputStream out) throws IOException { + out.writeInt(map.size()); + for (Map.Entry<K, V> entry : map.entrySet()) { + keyMutator.write(entry.getKey(), out); + valueMutator.write(entry.getValue(), out); + } + } + + @Override + protected Map<K, V> makeDefaultInstance() { + // Use a LinkedHashMap to ensure deterministic iteration order, which makes chunk-based + // mutations deterministic. The additional overhead compared to HashMap should be minimal. + return new LinkedHashMap<>(maxInitialSize()); + } + + @Override + public void initInPlace(Map<K, V> map, PseudoRandom prng) { + int targetSize = prng.closedRange(minInitialSize(), maxInitialSize()); + map.clear(); + growBy(map.keySet(), + key + -> map.putIfAbsent(key, valueMutator.init(prng)), + targetSize, () -> keyMutator.init(prng)); + if (map.size() < minSize) { + throw new IllegalStateException(String.format( + "Failed to create %d distinct elements of type %s to satisfy the @WithSize#minSize constraint on Map", + minSize, keyMutator)); + } + } + + @Override + public void mutateInPlace(Map<K, V> map, PseudoRandom prng) { + switch (pickRandomMutationAction(map.keySet(), minSize, maxSize, prng)) { + case DELETE_CHUNK: + deleteRandomChunk(map.keySet(), minSize, prng); + break; + case INSERT_CHUNK: + insertRandomChunk(map.keySet(), + key -> map.putIfAbsent(key, valueMutator.init(prng)), maxSize, keyMutator, prng); + break; + case MUTATE_CHUNK: + if (prng.choice() || !mutateRandomKeysChunk(map, keyMutator, prng)) { + mutateRandomValuesChunk(map, valueMutator, prng); + } + break; + default: + throw new IllegalStateException("unsupported action"); + } + } + + @Override + public void crossOverInPlace(Map<K, V> reference, Map<K, V> otherReference, PseudoRandom prng) { + switch ( + pickRandomCrossOverAction(reference.keySet(), otherReference.keySet(), maxSize, prng)) { + case INSERT_CHUNK: + insertChunk(reference, otherReference, maxSize, prng); + break; + case OVERWRITE_CHUNK: + overwriteChunk(reference, otherReference, prng); + break; + case CROSS_OVER_CHUNK: + crossOverChunk(reference, otherReference, keyMutator, valueMutator, prng); + break; + default: + // Both maps are empty or could otherwise not be crossed over. + } + } + + @Override + public Map<K, V> detach(Map<K, V> value) { + return value.entrySet().stream().collect(toMap(entry + -> keyMutator.detach(entry.getKey()), + entry -> valueMutator.detach(entry.getValue()))); + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return "Map<" + keyMutator.toDebugString(isInCycle) + "," + + valueMutator.toDebugString(isInCycle) + ">"; + } + + private int minInitialSize() { + return minSize; + } + + private int maxInitialSize() { + return min(maxSize, minSize + 1); + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BUILD.bazel new file mode 100644 index 00000000..5b234cee --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BUILD.bazel @@ -0,0 +1,16 @@ +java_library( + name = "lang", + srcs = glob(["*.java"]), + visibility = [ + "//src/main/java/com/code_intelligence/jazzer/mutation/mutator:__pkg__", + "//src/test/java/com/code_intelligence/jazzer/mutation/mutator:__subpackages__", + ], + deps = [ + "//src/main/java/com/code_intelligence/jazzer/mutation/annotation", + "//src/main/java/com/code_intelligence/jazzer/mutation/api", + "//src/main/java/com/code_intelligence/jazzer/mutation/combinator", + "//src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer", + "//src/main/java/com/code_intelligence/jazzer/mutation/support", + "@com_google_errorprone_error_prone_annotations//jar", + ], +) diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BooleanMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BooleanMutatorFactory.java new file mode 100644 index 00000000..a7dda971 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/BooleanMutatorFactory.java @@ -0,0 +1,79 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.lang; + +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.findFirstParentIfClass; + +import com.code_intelligence.jazzer.mutation.api.Debuggable; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; +import com.code_intelligence.jazzer.mutation.api.PseudoRandom; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import com.google.errorprone.annotations.Immutable; +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.lang.reflect.AnnotatedType; +import java.util.Optional; +import java.util.function.Predicate; + +final class BooleanMutatorFactory extends MutatorFactory { + @Override + public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) { + return findFirstParentIfClass(type, boolean.class, Boolean.class) + .map(parent -> BooleanMutator.INSTANCE); + } + + @Immutable + private static final class BooleanMutator extends SerializingMutator<Boolean> { + private static final BooleanMutator INSTANCE = new BooleanMutator(); + + @Override + public Boolean read(DataInputStream in) throws IOException { + return in.readBoolean(); + } + + @Override + public void write(Boolean value, DataOutputStream out) throws IOException { + out.writeBoolean(value); + } + + @Override + public Boolean init(PseudoRandom prng) { + return prng.choice(); + } + + @Override + public Boolean mutate(Boolean value, PseudoRandom prng) { + return !value; + } + + @Override + public Boolean crossOver(Boolean value, Boolean otherValue, PseudoRandom prng) { + return prng.choice() ? value : otherValue; + } + + @Override + public String toDebugString(Predicate<Debuggable> isInLoop) { + return "Boolean"; + } + + @Override + public Boolean detach(Boolean value) { + return value; + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/ByteArrayMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/ByteArrayMutatorFactory.java new file mode 100644 index 00000000..cdd0d881 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/ByteArrayMutatorFactory.java @@ -0,0 +1,227 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.lang; + +import static com.code_intelligence.jazzer.mutation.support.InputStreamSupport.readAllBytes; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.findFirstParentIfClass; + +import com.code_intelligence.jazzer.mutation.annotation.WithLength; +import com.code_intelligence.jazzer.mutation.api.Debuggable; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; +import com.code_intelligence.jazzer.mutation.api.PseudoRandom; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import com.code_intelligence.jazzer.mutation.mutator.libfuzzer.LibFuzzerMutator; +import com.code_intelligence.jazzer.mutation.support.RandomSupport; +import com.google.errorprone.annotations.Immutable; +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; +import java.lang.reflect.AnnotatedType; +import java.util.Arrays; +import java.util.Optional; +import java.util.function.Predicate; + +final class ByteArrayMutatorFactory extends MutatorFactory { + @Override + public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) { + Optional<WithLength> withLength = Optional.ofNullable(type.getAnnotation(WithLength.class)); + int minLength = withLength.map(WithLength::min).orElse(ByteArrayMutator.DEFAULT_MIN_LENGTH); + int maxLength = withLength.map(WithLength::max).orElse(ByteArrayMutator.DEFAULT_MAX_LENGTH); + + return findFirstParentIfClass(type, byte[].class) + .map(parent -> new ByteArrayMutator(minLength, maxLength)); + } + + @Immutable + private static final class ByteArrayMutator extends SerializingMutator<byte[]> { + private static final int DEFAULT_MIN_LENGTH = 0; + private static final int DEFAULT_MAX_LENGTH = 1000; + + private final int minLength; + + private final int maxLength; + + private ByteArrayMutator(int min, int max) { + this.minLength = min; + this.maxLength = max; + } + + @Override + public byte[] read(DataInputStream in) throws IOException { + int length = RandomSupport.clamp(in.readInt(), minLength, maxLength); + byte[] bytes = new byte[length]; + in.readFully(bytes); + return bytes; + } + + @Override + public byte[] readExclusive(InputStream in) throws IOException { + return readAllBytes(in); + } + + @Override + public void write(byte[] value, DataOutputStream out) throws IOException { + out.writeInt(value.length); + out.write(value); + } + + @Override + public void writeExclusive(byte[] value, OutputStream out) throws IOException { + out.write(value); + } + + @Override + public byte[] detach(byte[] value) { + return Arrays.copyOf(value, value.length); + } + + @Override + public byte[] init(PseudoRandom prng) { + int len = prng.closedRange(minInitialSize(), maxInitialSize()); + byte[] bytes = new byte[len]; + prng.bytes(bytes); + return bytes; + } + + private int minInitialSize() { + return minLength; + } + + private int maxInitialSize() { + // Allow some variation in length, but keep the initial elements well within reach of each + // other via a single mutation based on a Table of Recent Compares (ToRC) entry, which is + // currently limited to 64 bytes. + // Compared to List<T>, byte arrays can't result in recursive type hierarchies and thus don't + // to limit their expected initial size to be <= 1. + return Math.min(minLength + 16, maxLength); + } + + @Override + public byte[] mutate(byte[] value, PseudoRandom prng) { + int maxLengthIncrease = maxLength - value.length; + byte[] mutated = LibFuzzerMutator.mutateDefault(value, maxLengthIncrease); + return enforceLength(mutated); + } + + private byte[] enforceLength(byte[] mutated) { + // if the mutated array libfuzzer returns is too long or short, we truncate or extend it + // respectively. if we extend it, then copyOf will fill leftover bytes with 0 + if (mutated.length > maxLength) { + return Arrays.copyOf(mutated, maxLength); + } else if (mutated.length < minLength) { + return Arrays.copyOf(mutated, minLength); + } else { + return mutated; + } + } + + @Override + public byte[] crossOver(byte[] value, byte[] otherValue, PseudoRandom prng) { + // Passed in values are expected to already honor the min/max length constraints. + // As there does not seem to be an easy way to call libFuzzer's internal cross over + // algorithm, it is re-implemented in native Java. The algorithm is based on: + // https://github.com/llvm/llvm-project/blob/main/compiler-rt/lib/fuzzer/FuzzerMutate.cpp#L440 + // https://github.com/llvm/llvm-project/blob/main/compiler-rt/lib/fuzzer/FuzzerCrossOver.cpp#L19 + // + + if (value.length == 0 || otherValue.length == 0) { + return value; + } + + // TODO: Measure if this is fast enough. + byte[] out = null; + while (out == null) { + switch (prng.indexIn(3)) { + case 0: + out = intersect(value, otherValue, prng); + break; + case 1: + out = insertPart(value, otherValue, prng); + break; + case 2: + out = overwritePart(value, otherValue, prng); + break; + default: + throw new AssertionError("Invalid cross over function."); + } + } + return enforceLength(out); + } + + private static byte[] intersect(byte[] value, byte[] otherValue, PseudoRandom prng) { + int maxOutSize = prng.closedRange(0, Math.min(value.length, otherValue.length)); + byte[] out = new byte[maxOutSize]; + int outPos = 0; + int valuePos = 0; + int otherValuePos = 0; + boolean usingFirstValue = true; + while (outPos < out.length) { + if (usingFirstValue && valuePos < value.length) { + int extraSize = rndArraycopy(value, valuePos, out, outPos, prng); + outPos += extraSize; + valuePos += extraSize; + } else if (!usingFirstValue && otherValuePos < otherValue.length) { + int extraSize = rndArraycopy(otherValue, otherValuePos, out, outPos, prng); + outPos += extraSize; + otherValuePos += extraSize; + } + usingFirstValue = !usingFirstValue; + } + return out; + } + + private static int rndArraycopy( + byte[] val, int valPos, byte[] out, int outPos, PseudoRandom prng) { + int outSizeLeft = out.length - outPos; + int inSizeLeft = val.length - valPos; + int maxExtraSize = Math.min(outSizeLeft, inSizeLeft); + int extraSize = prng.closedRange(0, maxExtraSize); + System.arraycopy(val, valPos, out, outPos, extraSize); + return extraSize; + } + + private static byte[] insertPart(byte[] value, byte[] otherValue, PseudoRandom prng) { + int copySize = prng.closedRange(1, otherValue.length); + int f = otherValue.length - copySize; + int fromPos = f == 0 ? 0 : prng.indexIn(f); + int toPos = prng.indexIn(value.length); + int tailSize = value.length - toPos; + + byte[] out = new byte[value.length + copySize]; + System.arraycopy(value, 0, out, 0, toPos); + System.arraycopy(otherValue, fromPos, out, toPos, copySize); + System.arraycopy(value, toPos, out, toPos + copySize, tailSize); + return out; + } + + private static byte[] overwritePart(byte[] value, byte[] otherValue, PseudoRandom prng) { + int toPos = prng.indexIn(value.length); + int copySize = Math.min(prng.closedRange(1, value.length - toPos), otherValue.length); + int f = otherValue.length - copySize; + int fromPos = f == 0 ? 0 : prng.indexIn(f); + System.arraycopy(otherValue, fromPos, value, toPos, copySize); + return value; + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return "byte[]"; + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/EnumMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/EnumMutatorFactory.java new file mode 100644 index 00000000..80b9e6c9 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/EnumMutatorFactory.java @@ -0,0 +1,47 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.lang; + +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateIndices; +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateThenMap; +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateThenMapToImmutable; +import static com.code_intelligence.jazzer.mutation.support.Preconditions.require; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asSubclassOrEmpty; + +import com.code_intelligence.jazzer.mutation.api.Debuggable; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import java.lang.reflect.AnnotatedType; +import java.util.Optional; +import java.util.function.Predicate; + +final class EnumMutatorFactory extends MutatorFactory { + @Override + public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) { + return asSubclassOrEmpty(type, Enum.class).map(parent -> { + require(((Class<Enum<?>>) type.getType()).getEnumConstants().length > 1, + String.format( + "%s defines less than two enum constants and can't be mutated. Use a constant instead.", + parent)); + Enum<?>[] values = ((Class<Enum<?>>) type.getType()).getEnumConstants(); + return mutateThenMap(mutateIndices(values.length), + (index) + -> values[index], + Enum::ordinal, (Predicate<Debuggable> inCycle) -> "Enum<" + parent.getSimpleName() + ">"); + }); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/FloatingPointMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/FloatingPointMutatorFactory.java new file mode 100644 index 00000000..17890a9f --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/FloatingPointMutatorFactory.java @@ -0,0 +1,597 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.lang; + +import static com.code_intelligence.jazzer.mutation.support.Preconditions.require; +import static java.lang.String.format; + +import com.code_intelligence.jazzer.mutation.annotation.DoubleInRange; +import com.code_intelligence.jazzer.mutation.annotation.FloatInRange; +import com.code_intelligence.jazzer.mutation.api.Debuggable; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; +import com.code_intelligence.jazzer.mutation.api.PseudoRandom; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import com.code_intelligence.jazzer.mutation.mutator.libfuzzer.LibFuzzerMutator; +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.lang.annotation.Annotation; +import java.lang.reflect.AnnotatedType; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; +import java.util.Optional; +import java.util.function.DoubleFunction; +import java.util.function.Predicate; +import java.util.stream.DoubleStream; + +final class FloatingPointMutatorFactory extends MutatorFactory { + @SuppressWarnings("unchecked") + private static final DoubleFunction<Double>[] mathFunctions = + new DoubleFunction[] {Math::acos, Math::asin, Math::atan, Math::cbrt, Math::ceil, Math::cos, + Math::cosh, Math::exp, Math::expm1, Math::floor, Math::log, Math::log10, Math::log1p, + Math::rint, Math::sin, Math::sinh, Math::sqrt, Math::tan, Math::tanh, Math::toDegrees, + Math::toRadians, n -> n * 0.5, n -> n * 2.0, n -> n * 0.333333333333333, n -> n * 3.0}; + + @Override + public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) { + if (!(type.getType() instanceof Class)) { + return Optional.empty(); + } + Class<?> clazz = (Class<?>) type.getType(); + + if (clazz == float.class || clazz == Float.class) { + return Optional.of( + new FloatMutator(type, Float.NEGATIVE_INFINITY, Float.POSITIVE_INFINITY, true)); + } else if (clazz == double.class || clazz == Double.class) { + return Optional.of( + new DoubleMutator(type, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, true)); + } else { + return Optional.empty(); + } + } + + static final class FloatMutator extends SerializingMutator<Float> { + private static final int EXPONENT_INITIAL_BIT = 23; + private static final int MANTISSA_MASK = 0x7fffff; + private static final int EXPONENT_MASK = 0xff; + private static final int MANTISSA_RANDOM_WALK_RANGE = 1000; + private static final int EXPONENT_RANDOM_WALK_RANGE = Float.MAX_EXPONENT; + private static final int INVERSE_FREQUENCY_SPECIAL_VALUE = 1000; + + // Visible for testing. + final float minValue; + final float maxValue; + final boolean allowNaN; + private final float[] specialValues; + + FloatMutator(AnnotatedType type, float defaultMinValueForType, float defaultMaxValueForType, + boolean defaultAllowNaN) { + float minValue = defaultMinValueForType; + float maxValue = defaultMaxValueForType; + boolean allowNaN = defaultAllowNaN; + // InRange is not repeatable, so the loop body will apply at most once. + for (Annotation annotation : type.getAnnotations()) { + if (annotation instanceof FloatInRange) { + FloatInRange floatInRange = (FloatInRange) annotation; + minValue = floatInRange.min(); + maxValue = floatInRange.max(); + allowNaN = floatInRange.allowNaN(); + } + } + + require(minValue <= maxValue, + format("[%f, %f] is not a valid interval: %s", minValue, maxValue, type)); + require(minValue != maxValue, + format( + "[%f, %f] can not be mutated, use a constant instead: %s", minValue, maxValue, type)); + this.minValue = minValue; + this.maxValue = maxValue; + this.allowNaN = allowNaN; + this.specialValues = collectSpecialValues(minValue, maxValue); + } + + private float[] collectSpecialValues(float minValue, float maxValue) { + // stream of floats + List<Double> specialValues = + DoubleStream + .of(Float.NEGATIVE_INFINITY, Float.POSITIVE_INFINITY, 0.0f, -0.0f, Float.NaN, + Float.MAX_VALUE, Float.MIN_VALUE, -Float.MAX_VALUE, -Float.MIN_VALUE, + this.minValue, this.maxValue) + .filter(n -> (n >= minValue && n <= maxValue) || allowNaN && Double.isNaN(n)) + .distinct() + .sorted() + .collect(ArrayList::new, ArrayList::add, ArrayList::addAll); + + float[] specialValuesArray = new float[specialValues.size()]; + for (int i = 0; i < specialValues.size(); i++) { + specialValuesArray[i] = (float) (double) specialValues.get(i); + } + return specialValuesArray; + } + + public float mutateWithLibFuzzer(float value) { + return LibFuzzerMutator.mutateDefault(value, this, 0); + } + + @Override + public Float init(PseudoRandom prng) { + if (prng.choice()) { + return specialValues[prng.closedRange(0, specialValues.length - 1)]; + } else { + return prng.closedRange(minValue, maxValue); + } + } + + @Override + public Float mutate(Float value, PseudoRandom prng) { + float result; + // small chance to return a special value + if (prng.trueInOneOutOf(INVERSE_FREQUENCY_SPECIAL_VALUE)) { + result = specialValues[prng.closedRange(0, specialValues.length - 1)]; + } else { + switch (prng.closedRange(0, 5)) { + case 0: + result = mutateWithBitFlip(value, prng); + break; + case 1: + result = mutateExponent(value, prng); + break; + case 2: + result = mutateMantissa(value, prng); + break; + case 3: + result = mutateWithMathematicalFn(value, prng); + break; + case 4: + result = mutateWithLibFuzzer(value); + break; + case 5: // random in range cannot exceed the given bounds (and cannot be NaN) + result = prng.closedRange(minValue, maxValue); + break; + default: + throw new IllegalStateException("Unknown mutation case"); + } + } + result = forceInRange(result, minValue, maxValue, allowNaN); + + // Repeating values are not allowed. + if (Float.compare(result, value) == 0) { + if (Float.isNaN(result)) { + return prng.closedRange(minValue, maxValue); + } else { // Change the value to the neighboring float. + if (result > minValue && result < maxValue) { + return prng.choice() ? Math.nextAfter(result, Float.NEGATIVE_INFINITY) + : Math.nextAfter(result, Float.POSITIVE_INFINITY); + } else if (result > minValue) { + return Math.nextAfter(result, Float.NEGATIVE_INFINITY); + } else + return Math.nextAfter(result, Float.POSITIVE_INFINITY); + } + } + + return result; + } + + static float forceInRange(float value, float minValue, float maxValue, boolean allowNaN) { + if ((value >= minValue && value <= maxValue) || (Float.isNaN(value) && allowNaN)) + return value; + + // Clamp infinite values + if (value == Float.POSITIVE_INFINITY) + return maxValue; + if (value == Float.NEGATIVE_INFINITY) + return minValue; + + // From here on limits should be finite + float finiteMax = Math.min(Float.MAX_VALUE, maxValue); + float finiteMin = Math.max(-Float.MAX_VALUE, minValue); + + // If NaN was allowed, it was handled above. Replace it by the midpoint of the range. + if (Float.isNaN(value)) + return finiteMin * 0.5f + finiteMax * 0.5f; + + float range = finiteMax - finiteMin; + if (range == 0f) + return finiteMin; + + float diff = value - finiteMin; + + if (Float.isFinite(diff) && Float.isFinite(range)) { + return finiteMin + Math.abs(diff % range); + } + + // diff, range, or both are infinite: divide both by 2, reduce, and multiply by 2. + float halfDiff = value * 0.5f - finiteMin * 0.5f; + + return finiteMin + (halfDiff % (finiteMax * 0.5f - finiteMin * 0.5f)) * 2.0f; + } + + public float mutateWithMathematicalFn(float value, PseudoRandom prng) { + double result = prng.pickIn(mathFunctions).apply(value); + return (float) result; + } + + private float mutateWithBitFlip(float value, PseudoRandom prng) { + int bits = Float.floatToRawIntBits(value); + int bitToFlip = prng.closedRange(0, 31); + bits ^= 1L << bitToFlip; + return Float.intBitsToFloat(bits); + } + + private float mutateExponent(float value, PseudoRandom prng) { + int bits = Float.floatToRawIntBits(value); + int exponent = ((bits >> EXPONENT_INITIAL_BIT) & EXPONENT_MASK) + + prng.closedRange(0, EXPONENT_RANDOM_WALK_RANGE); + bits = (bits & ~(EXPONENT_MASK << EXPONENT_INITIAL_BIT)) + | ((exponent % EXPONENT_MASK) << EXPONENT_INITIAL_BIT); + return Float.intBitsToFloat(bits); + } + + private float mutateMantissa(float value, PseudoRandom prng) { + int bits = Float.floatToRawIntBits(value); + + int mantissa = bits & MANTISSA_MASK; + switch (prng.closedRange(0, 2)) { + case 0: // + + mantissa = + (mantissa + prng.closedRange(-MANTISSA_RANDOM_WALK_RANGE, MANTISSA_RANDOM_WALK_RANGE)) + % MANTISSA_MASK; + break; + case 1: // * + mantissa = + (mantissa * prng.closedRange(-MANTISSA_RANDOM_WALK_RANGE, MANTISSA_RANDOM_WALK_RANGE)) + % MANTISSA_MASK; + break; + case 2: // / + int divisor = prng.closedRange(2, MANTISSA_RANDOM_WALK_RANGE); + if (prng.choice()) { + divisor = -divisor; + } + mantissa = (mantissa / divisor); + break; + default: + throw new IllegalStateException("Unknown mutation case for mantissa"); + } + bits = (bits & ~MANTISSA_MASK) | mantissa; + return Float.intBitsToFloat(bits); + } + + @Override + public Float crossOver(Float value, Float otherValue, PseudoRandom prng) { + float result; + switch (prng.closedRange(0, 2)) { + case 0: + result = crossOverMean(value, otherValue); + break; + case 1: + result = crossOverExponent(value, otherValue); + break; + case 2: + result = crossOverMantissa(value, otherValue); + break; + default: + throw new IllegalStateException("Unknown mutation case"); + } + return forceInRange(result, minValue, maxValue, allowNaN); + } + + private float crossOverMean(float value, float otherValue) { + return (float) ((((double) value) + ((double) otherValue)) / 2.0); + } + + private float crossOverExponent(float value, float otherValue) { + int bits = Float.floatToRawIntBits(value); + int otherExponent = + Float.floatToRawIntBits(otherValue) & (EXPONENT_MASK << EXPONENT_INITIAL_BIT); + int bitsWithOtherExponent = (bits & ~(EXPONENT_MASK << EXPONENT_INITIAL_BIT)) | otherExponent; + return Float.intBitsToFloat(bitsWithOtherExponent); + } + + private float crossOverMantissa(float value, float otherValue) { + int bits = Float.floatToRawIntBits(value); + int otherMantissa = Float.floatToRawIntBits(otherValue) & MANTISSA_MASK; + int bitsWithOtherMantissa = (bits & ~MANTISSA_MASK) | otherMantissa; + return Float.intBitsToFloat(bitsWithOtherMantissa); + } + + @Override + public Float read(DataInputStream in) throws IOException { + return forceInRange(in.readFloat(), minValue, maxValue, allowNaN); + } + + @Override + public void write(Float value, DataOutputStream out) throws IOException { + out.writeFloat(value); + } + + @Override + public Float detach(Float value) { + return value; + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return "Float"; + } + } + + static final class DoubleMutator extends SerializingMutator<Double> { + private static final long MANTISSA_RANDOM_WALK_RANGE = 1000; + private static final int EXPONENT_RANDOM_WALK_RANGE = Double.MAX_EXPONENT; + private static final int INVERSE_FREQUENCY_SPECIAL_VALUE = 1000; + private static final long MANTISSA_MASK = 0xfffffffffffffL; + private static final long EXPONENT_MASK = 0x7ffL; + private static final int EXPONENT_INITIAL_BIT = 52; + + // Visible for testing + final double minValue; + final double maxValue; + final boolean allowNaN; + private final double[] specialValues; + + DoubleMutator(AnnotatedType type, double defaultMinValueForType, double defaultMaxValueForType, + boolean defaultAllowNaN) { + double minValue = defaultMinValueForType; + double maxValue = defaultMaxValueForType; + boolean allowNaN = defaultAllowNaN; + // InRange is not repeatable, so the loop body will apply at most once. + for (Annotation annotation : type.getAnnotations()) { + if (annotation instanceof DoubleInRange) { + DoubleInRange doubleInRange = (DoubleInRange) annotation; + minValue = doubleInRange.min(); + maxValue = doubleInRange.max(); + allowNaN = doubleInRange.allowNaN(); + } + } + + require(!Double.isNaN(minValue) && !Double.isNaN(maxValue), + format("[%f, %f] is not a valid interval: %s", minValue, maxValue, type)); + require(minValue <= maxValue, + format("[%f, %f] is not a valid interval: %s", minValue, maxValue, type)); + require(minValue != maxValue, + format( + "[%f, %f] can not be mutated, use a constant instead: %s", minValue, maxValue, type)); + this.minValue = minValue; + this.maxValue = maxValue; + this.allowNaN = allowNaN; + this.specialValues = collectSpecialValues(minValue, maxValue); + } + + private double[] collectSpecialValues(double minValue, double maxValue) { + double[] specialValues = new double[] {Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, + 0.0, -0.0, Double.NaN, Double.MAX_VALUE, Double.MIN_VALUE, -Double.MAX_VALUE, + -Double.MIN_VALUE, this.minValue, this.maxValue}; + return Arrays.stream(specialValues) + .boxed() + .filter(value -> (allowNaN && value.isNaN()) || (value >= minValue && value <= maxValue)) + .distinct() + .sorted() + .mapToDouble(Double::doubleValue) + .toArray(); + } + + public double mutateWithLibFuzzer(double value) { + return LibFuzzerMutator.mutateDefault(value, this, 0); + } + + @Override + public Double init(PseudoRandom prng) { + if (prng.choice()) { + return specialValues[prng.closedRange(0, specialValues.length - 1)]; + } else { + return prng.closedRange(minValue, maxValue); + } + } + + @Override + public Double mutate(Double value, PseudoRandom prng) { + double result; + // small chance to return a special value + if (prng.trueInOneOutOf(INVERSE_FREQUENCY_SPECIAL_VALUE)) { + result = specialValues[prng.closedRange(0, specialValues.length - 1)]; + } else { + switch (prng.closedRange(0, 5)) { + case 0: + result = mutateWithBitFlip(value, prng); + break; + case 1: + result = mutateExponent(value, prng); + break; + case 2: + result = mutateMantissa(value, prng); + break; + case 3: + result = mutateWithMathematicalFn(value, prng); + break; + case 4: + result = mutateWithLibFuzzer(value); + break; + case 5: // random in range cannot exceed the given bounds (and cannot be NaN) + result = prng.closedRange(minValue, maxValue); + break; + default: + throw new IllegalStateException("Unknown mutation case"); + } + } + result = forceInRange(result, minValue, maxValue, allowNaN); + + // Repeating values are not allowed. + if (Double.compare(result, value) == 0) { + if (Double.isNaN(result)) { + return prng.closedRange(minValue, maxValue); + } else { // Change the value to the neighboring float. + if (result > minValue && result < maxValue) { + return prng.choice() ? Math.nextAfter(result, Double.NEGATIVE_INFINITY) + : Math.nextAfter(result, Double.POSITIVE_INFINITY); + } else if (result > minValue) { + return Math.nextAfter(result, Double.NEGATIVE_INFINITY); + } else + return Math.nextAfter(result, Double.POSITIVE_INFINITY); + } + } + + return result; + } + + static double forceInRange(double value, double minValue, double maxValue, boolean allowNaN) { + if ((value >= minValue && value <= maxValue) || (Double.isNaN(value) && allowNaN)) { + return value; + } + + // Clamp infinite values + if (value == Double.POSITIVE_INFINITY) + return maxValue; + if (value == Double.NEGATIVE_INFINITY) + return minValue; + + // From here on limits should be finite + double finiteMax = Math.min(Double.MAX_VALUE, maxValue); + double finiteMin = Math.max(-Double.MAX_VALUE, minValue); + + // If NaN was allowed, it was handled above. + // Here we replace NaN by the middle of the clamped finite range. + if (Double.isNaN(value)) { + // maxValue or minValue may be infinite, so we need to clamp them. + return minValue + + (Math.min(Double.MAX_VALUE, maxValue) * 0.5 + - Math.max(-Double.MAX_VALUE, minValue) * 0.5); + } + + double range = finiteMax - finiteMin; + if (range == 0) + return finiteMin; + + double diff = value - finiteMin; + + if (Double.isFinite(diff) && Double.isFinite(range)) { + return finiteMin + Math.abs(diff % range); + } + + // diff, range, or both are infinite: divide both by 2, reduce, and multiply by 2. + double halfDiff = value * 0.5 - finiteMin * 0.5; + return finiteMin + (halfDiff % (finiteMax * 0.5 - finiteMin * 0.5)) * 2.0; + } + + public double mutateWithMathematicalFn(double value, PseudoRandom prng) { + return prng.pickIn(mathFunctions).apply(value); + } + + public static double mutateWithBitFlip(double value, PseudoRandom prng) { + long bits = Double.doubleToRawLongBits(value); + int bitToFlip = prng.closedRange(0, 63); + bits ^= 1L << bitToFlip; + return Double.longBitsToDouble(bits); + } + + private static double mutateExponent(double value, PseudoRandom prng) { + long bits = Double.doubleToRawLongBits(value); + long exponent = ((bits >> EXPONENT_INITIAL_BIT) & EXPONENT_MASK) + + prng.closedRange(0, EXPONENT_RANDOM_WALK_RANGE); + bits = (bits & ~(EXPONENT_MASK << EXPONENT_INITIAL_BIT)) + | ((exponent % EXPONENT_MASK) << EXPONENT_INITIAL_BIT); + return Double.longBitsToDouble(bits); + } + + public static double mutateMantissa(double value, PseudoRandom prng) { + long bits = Double.doubleToRawLongBits(value); + long mantissa = bits & MANTISSA_MASK; + switch (prng.closedRange(0, 2)) { + case 0: // + + mantissa = + (mantissa + prng.closedRange(-MANTISSA_RANDOM_WALK_RANGE, MANTISSA_RANDOM_WALK_RANGE)) + % MANTISSA_MASK; + break; + case 1: // * + mantissa = + (mantissa * prng.closedRange(-MANTISSA_RANDOM_WALK_RANGE, MANTISSA_RANDOM_WALK_RANGE)) + % MANTISSA_MASK; + break; + case 2: // / + long divisor = prng.closedRange(2, MANTISSA_RANDOM_WALK_RANGE); + if (prng.choice()) { + divisor = -divisor; + } + mantissa = (mantissa / divisor); + break; + default: + throw new IllegalStateException("Unknown mutation case for mantissa"); + } + bits = (bits & ~MANTISSA_MASK) | mantissa; + return Double.longBitsToDouble(bits); + } + + @Override + public Double crossOver(Double value, Double otherValue, PseudoRandom prng) { + double result; + switch (prng.closedRange(0, 2)) { + case 0: + result = crossOverMean(value, otherValue); + break; + case 1: + result = crossOverExponent(value, otherValue); + break; + case 2: + result = crossOverMantissa(value, otherValue); + break; + default: + throw new IllegalStateException("Unknown mutation case"); + } + return forceInRange(result, minValue, maxValue, allowNaN); + } + + private double crossOverMean(double value, double otherValue) { + return (value * 0.5) + (otherValue * 0.5); + } + + private double crossOverExponent(double value, double otherValue) { + long bits = Double.doubleToRawLongBits(value); + long otherExponent = + Double.doubleToRawLongBits(otherValue) & (EXPONENT_MASK << EXPONENT_INITIAL_BIT); + long bitsWithOtherExponent = + (bits & ~(EXPONENT_MASK << EXPONENT_INITIAL_BIT)) | otherExponent; + return Double.longBitsToDouble(bitsWithOtherExponent); + } + + private double crossOverMantissa(double value, double otherValue) { + long bits = Double.doubleToRawLongBits(value); + long otherMantissa = Double.doubleToRawLongBits(otherValue) & MANTISSA_MASK; + long bitsWithOtherMantissa = (bits & ~MANTISSA_MASK) | otherMantissa; + return Double.longBitsToDouble(bitsWithOtherMantissa); + } + + @Override + public Double read(DataInputStream in) throws IOException { + return forceInRange(in.readDouble(), minValue, maxValue, allowNaN); + } + + @Override + public void write(Double value, DataOutputStream out) throws IOException { + out.writeDouble(value); + } + + @Override + public Double detach(Double value) { + return value; + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return "Double"; + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/IntegralMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/IntegralMutatorFactory.java new file mode 100644 index 00000000..e701e6ad --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/IntegralMutatorFactory.java @@ -0,0 +1,399 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.lang; + +import static com.code_intelligence.jazzer.mutation.support.Preconditions.require; +import static java.lang.String.format; + +import com.code_intelligence.jazzer.mutation.annotation.InRange; +import com.code_intelligence.jazzer.mutation.api.Debuggable; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; +import com.code_intelligence.jazzer.mutation.api.PseudoRandom; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import com.code_intelligence.jazzer.mutation.mutator.libfuzzer.LibFuzzerMutator; +import com.google.errorprone.annotations.ForOverride; +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.lang.annotation.Annotation; +import java.lang.reflect.AnnotatedType; +import java.lang.reflect.ParameterizedType; +import java.util.Optional; +import java.util.function.Predicate; +import java.util.stream.LongStream; + +final class IntegralMutatorFactory extends MutatorFactory { + @Override + public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) { + if (!(type.getType() instanceof Class)) { + return Optional.empty(); + } + Class<?> clazz = (Class<?>) type.getType(); + + if (clazz == byte.class || clazz == Byte.class) { + return Optional.of(new AbstractIntegralMutator<Byte>(type, Byte.MIN_VALUE, Byte.MAX_VALUE) { + @Override + protected long mutateWithLibFuzzer(long value) { + return LibFuzzerMutator.mutateDefault((byte) value, this, 0); + } + + @Override + public Byte init(PseudoRandom prng) { + return (byte) initImpl(prng); + } + + @Override + public Byte mutate(Byte value, PseudoRandom prng) { + return (byte) mutateImpl(value, prng); + } + + @Override + public Byte crossOver(Byte value, Byte otherValue, PseudoRandom prng) { + return (byte) crossOverImpl(value, otherValue, prng); + } + + @Override + public Byte read(DataInputStream in) throws IOException { + return (byte) forceInRange(in.readByte()); + } + + @Override + public void write(Byte value, DataOutputStream out) throws IOException { + out.writeByte(value); + } + }); + } else if (clazz == short.class || clazz == Short.class) { + return Optional.of( + new AbstractIntegralMutator<Short>(type, Short.MIN_VALUE, Short.MAX_VALUE) { + @Override + protected long mutateWithLibFuzzer(long value) { + return LibFuzzerMutator.mutateDefault((short) value, this, 0); + } + + @Override + public Short init(PseudoRandom prng) { + return (short) initImpl(prng); + } + + @Override + public Short mutate(Short value, PseudoRandom prng) { + return (short) mutateImpl(value, prng); + } + + @Override + public Short crossOver(Short value, Short otherValue, PseudoRandom prng) { + return (short) crossOverImpl(value, otherValue, prng); + } + + @Override + public Short read(DataInputStream in) throws IOException { + return (short) forceInRange(in.readShort()); + } + + @Override + public void write(Short value, DataOutputStream out) throws IOException { + out.writeShort(value); + } + }); + } else if (clazz == int.class || clazz == Integer.class) { + return Optional.of( + new AbstractIntegralMutator<Integer>(type, Integer.MIN_VALUE, Integer.MAX_VALUE) { + @Override + protected long mutateWithLibFuzzer(long value) { + return LibFuzzerMutator.mutateDefault((int) value, this, 0); + } + + @Override + public Integer init(PseudoRandom prng) { + return (int) initImpl(prng); + } + + @Override + public Integer mutate(Integer value, PseudoRandom prng) { + return (int) mutateImpl(value, prng); + } + + @Override + public Integer crossOver(Integer value, Integer otherValue, PseudoRandom prng) { + return (int) crossOverImpl(value, otherValue, prng); + } + + @Override + public Integer read(DataInputStream in) throws IOException { + return (int) forceInRange(in.readInt()); + } + + @Override + public void write(Integer value, DataOutputStream out) throws IOException { + out.writeInt(value); + } + }); + } else if (clazz == long.class || clazz == Long.class) { + return Optional.of(new AbstractIntegralMutator<Long>(type, Long.MIN_VALUE, Long.MAX_VALUE) { + @Override + protected long mutateWithLibFuzzer(long value) { + return LibFuzzerMutator.mutateDefault(value, this, 0); + } + + @Override + public Long init(PseudoRandom prng) { + return initImpl(prng); + } + + @Override + public Long mutate(Long value, PseudoRandom prng) { + return mutateImpl(value, prng); + } + + @Override + public Long crossOver(Long value, Long otherValue, PseudoRandom prng) { + return crossOverImpl(value, otherValue, prng); + } + + @Override + public Long read(DataInputStream in) throws IOException { + return forceInRange(in.readLong()); + } + + @Override + public void write(Long value, DataOutputStream out) throws IOException { + out.writeLong(value); + } + }); + } else { + return Optional.empty(); + } + } + + // Based on + // https://github.com/google/fuzztest/blob/a663ded6c36f050fbdc634a8fc81d553068d71d7/fuzztest/internal/domain.h#L1447 + // SPDX: Apache-2.0 + // Copyright 2022 Google LLC + // + // Visible for testing. + static abstract class AbstractIntegralMutator<T extends Number> extends SerializingMutator<T> { + private static final long RANDOM_WALK_RANGE = 5; + private final long minValue; + private final long maxValue; + private final int largestMutableBitNegative; + private final int largestMutableBitPositive; + private final long[] specialValues; + + AbstractIntegralMutator( + AnnotatedType type, long defaultMinValueForType, long defaultMaxValueForType) { + long minValue = defaultMinValueForType; + long maxValue = defaultMaxValueForType; + // InRange is not repeatable, so the loop body will apply exactly once. + for (Annotation annotation : type.getAnnotations()) { + if (annotation instanceof InRange) { + InRange inRange = (InRange) annotation; + // Since we use a single annotation for all integral types and its min and max fields are + // longs, we have to ignore them if they are at their default values. + // + // This results in a small quirk that is probably acceptable: If someone specifies + // @InRange(max = Long.MAX_VALUE) on a byte, we will not fail but silently use + // Byte.MAX_VALUE instead. IDEs will warn about the redundant specification of the default + // value, so this should not be a problem in practice. + if (inRange.min() != Long.MIN_VALUE) { + require(inRange.min() >= defaultMinValueForType, + format("@InRange.min=%d is out of range: %s", inRange.min(), type.getType())); + minValue = inRange.min(); + } + if (inRange.max() != Long.MAX_VALUE) { + require(inRange.max() <= defaultMaxValueForType, + format("@InRange.max=%d is out of range: %s", inRange.max(), type.getType())); + maxValue = inRange.max(); + } + } + } + + require(minValue <= maxValue, + format("[%d, %d] is not a valid interval: %s", minValue, maxValue, type)); + require(minValue != maxValue, + format( + "[%d, %d] can not be mutated, use a constant instead: %s", minValue, maxValue, type)); + this.minValue = minValue; + this.maxValue = maxValue; + if (minValue >= 0) { + largestMutableBitNegative = 0; + largestMutableBitPositive = bitWidth(minValue ^ maxValue); + } else if (maxValue < 0) { + largestMutableBitNegative = bitWidth(minValue ^ maxValue); + largestMutableBitPositive = 0; + } else /* minValue < 0 && maxValue >= 0 */ { + largestMutableBitNegative = bitWidth(~minValue); + largestMutableBitPositive = bitWidth(maxValue); + } + this.specialValues = collectSpecialValues(minValue, maxValue); + } + + private static long[] collectSpecialValues(long minValue, long maxValue) { + // Special values can collide or not apply when @InRange is used, so filter appropriately and + // remove duplicates - we don't want to weigh certain special values higher than others. + return LongStream.of(0, 1, minValue, maxValue) + .filter(value -> value >= minValue) + .filter(value -> value <= maxValue) + .distinct() + .sorted() + .toArray(); + } + + private static int bitWidth(long value) { + return 64 - Long.numberOfLeadingZeros(value); + } + + protected final long initImpl(PseudoRandom prng) { + int sentinel = specialValues.length; + int choice = prng.closedRange(0, sentinel); + if (choice < sentinel) { + return specialValues[choice]; + } else { + return prng.closedRange(minValue, maxValue); + } + } + + protected final long mutateImpl(long value, PseudoRandom prng) { + final long previousValue = value; + // Mutate in a loop to verify that we really mutated. + do { + switch (prng.indexIn(4)) { + case 0: + value = bitFlip(value, prng); + break; + case 1: + value = randomWalk(value, prng); + break; + case 2: + value = prng.closedRange(minValue, maxValue); + break; + case 3: + // TODO: Replace this with a structure-aware dictionary/TORC search similar to fuzztest. + value = forceInRange(mutateWithLibFuzzer(value)); + break; + } + } while (value == previousValue); + return value; + } + + protected final long crossOverImpl(long x, long y, PseudoRandom prng) { + switch (prng.indexIn(3)) { + case 0: + return mean(x, y); + case 1: + return forceInRange(x ^ y); + case 2: + return bitmask(x, y, prng); + default: + throw new AssertionError("Invalid cross over function."); + } + } + + private long bitmask(long x, long y, PseudoRandom prng) { + long mask = prng.nextLong(); + return forceInRange((x & mask) | (y & ~mask)); + } + + private static long mean(long x, long y) { + // Add the common set bits (x & y) and the half of the sum of the + // differing bits together ((x ^ y) >> 1), the result will never exceed + // the sum of x and y as both parts of the calculation are guaranteed to + // be smaller than or equal to x and y. + long xor = x ^ y; + long mean = (x & y) + (xor >> 1); + // Round towards zero (add 1) if rounding is not exact (last xor bit is + // set) and result is negative (sign bit is set). + return mean + (1 & xor & (mean >>> 31)); + } + + @ForOverride protected abstract long mutateWithLibFuzzer(long value); + + /** + * Force value into the closed interval [minValue, maxValue] while preserving as many of its + * bits as possible (e.g. so that mutations that apply to the raw byte representation still have + * a good chance to actually mutate the value). Clamping would not have this property. + */ + protected final long forceInRange(long value) { + // Fast path for the common case. + if (value >= minValue && value <= maxValue) { + return value; + } + return forceInRange(value, minValue, maxValue); + } + + // Visible for testing. + static long forceInRange(long value, long minValue, long maxValue) { + long range = maxValue - minValue; + if (range > 0) { + return minValue + Math.abs((value - minValue) % range); + } else { + // [minValue, maxValue] covers at least half of the [Long.MIN_VALUE, Long.MAX_VALUE] range, + // so if value doesn't lie in [minValue, maxValue], it will after shifting once. + if (value >= minValue && value <= maxValue) { + return value; + } else { + return value + range; + } + } + } + + private long bitFlip(long value, PseudoRandom prng) { + int range = value >= 0 ? largestMutableBitPositive : largestMutableBitNegative; + value = value ^ (1L << prng.indexIn(range)); + // The bit flip may violate the range constraint, if so, mutate randomly. + if (value > maxValue || value < minValue) { + value = prng.closedRange(minValue, maxValue); + } + return value; + } + + private long randomWalk(long value, PseudoRandom prng) { + // Prevent overflows by averaging the individual bounds. + if (maxValue / 2 - minValue / 2 <= RANDOM_WALK_RANGE) { + value = prng.closedRange(minValue, maxValue); + } else { + // At this point we know that (using non-wrapping arithmetic): + // RANDOM_WALK_RANGE < maxValue/2 - minValue/2 <= Long.MAX_VALUE/2 - minValue/2, hence + // minValue/2 + RANDOM_WALK_RANGE < Long.MAX_VALUE/2, hence + // minValue + 2*RANDOM_WALK_RANGE < Long.MAX_VALUE. + // In particular, minValue + RANDOM_WALK_RANGE can't overflow, likewise for maxValue. + long lower = minValue; + if (value > lower + RANDOM_WALK_RANGE) { + lower = value - RANDOM_WALK_RANGE; + } + long upper = maxValue; + if (value < upper - RANDOM_WALK_RANGE) { + upper = value + RANDOM_WALK_RANGE; + } + value = prng.closedRange(lower, upper); + } + return value; + } + + @Override + public T detach(T value) { + // Always immutable. + return value; + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return ((Class<T>) ((ParameterizedType) this.getClass().getGenericSuperclass()) + .getActualTypeArguments()[0]) + .getSimpleName(); + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/LangMutators.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/LangMutators.java new file mode 100644 index 00000000..00ea8b47 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/LangMutators.java @@ -0,0 +1,30 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.lang; + +import com.code_intelligence.jazzer.mutation.api.ChainedMutatorFactory; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; + +public final class LangMutators { + private LangMutators() {} + + public static MutatorFactory newFactory() { + return new ChainedMutatorFactory(new NullableMutatorFactory(), new BooleanMutatorFactory(), + new FloatingPointMutatorFactory(), new IntegralMutatorFactory(), + new ByteArrayMutatorFactory(), new StringMutatorFactory(), new EnumMutatorFactory()); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/NullableMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/NullableMutatorFactory.java new file mode 100644 index 00000000..16e6a132 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/NullableMutatorFactory.java @@ -0,0 +1,126 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.lang; + +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.isPrimitive; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.notNull; +import static java.util.Arrays.stream; + +import com.code_intelligence.jazzer.mutation.api.Debuggable; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; +import com.code_intelligence.jazzer.mutation.api.PseudoRandom; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.lang.annotation.Annotation; +import java.lang.reflect.AnnotatedType; +import java.util.Optional; +import java.util.function.Predicate; + +final class NullableMutatorFactory extends MutatorFactory { + private static boolean isNotNullAnnotation(Annotation annotation) { + // There are many NotNull annotations in the wild (including our own) and we want to recognize + // them all. + return annotation.annotationType().getSimpleName().equals("NotNull"); + } + + @Override + public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) { + if (isPrimitive(type) + || stream(type.getAnnotations()).anyMatch(NullableMutatorFactory::isNotNullAnnotation)) { + return Optional.empty(); + } + return factory.tryCreate(notNull(type), factory).map(NullableMutator::new); + } + + private static final class NullableMutator<T> extends SerializingMutator<T> { + private static final int INVERSE_FREQUENCY_NULL = 100; + + private final SerializingMutator<T> mutator; + + NullableMutator(SerializingMutator<T> mutator) { + this.mutator = mutator; + } + + @Override + public T read(DataInputStream in) throws IOException { + if (in.readBoolean()) { + return mutator.read(in); + } else { + return null; + } + } + + @Override + public void write(T value, DataOutputStream out) throws IOException { + out.writeBoolean(value != null); + if (value != null) { + mutator.write(value, out); + } + } + + @Override + public T init(PseudoRandom prng) { + if (prng.trueInOneOutOf(INVERSE_FREQUENCY_NULL)) { + return null; + } else { + return mutator.init(prng); + } + } + + @Override + public T mutate(T value, PseudoRandom prng) { + if (value == null) { + return mutator.init(prng); + } else if (prng.trueInOneOutOf(INVERSE_FREQUENCY_NULL)) { + return null; + } else { + return mutator.mutate(value, prng); + } + } + + @Override + public T crossOver(T value, T otherValue, PseudoRandom prng) { + // Prefer to cross over actual values and only return null if + // both are null or at INVERSE_FREQUENCY_NULL probability. + if (value != null && otherValue != null) { + return mutator.crossOver(value, otherValue, prng); + } else if (value == null && otherValue == null) { + return null; + } else if (prng.trueInOneOutOf(INVERSE_FREQUENCY_NULL)) { + return null; + } else { + return value != null ? value : otherValue; + } + } + + @Override + public T detach(T value) { + if (value == null) { + return null; + } else { + return mutator.detach(value); + } + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return "Nullable<" + mutator.toDebugString(isInCycle) + ">"; + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/StringMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/StringMutatorFactory.java new file mode 100644 index 00000000..d77cb9d3 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/StringMutatorFactory.java @@ -0,0 +1,172 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.lang; + +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateThenMapToImmutable; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.*; + +import com.code_intelligence.jazzer.mutation.annotation.Ascii; +import com.code_intelligence.jazzer.mutation.annotation.WithUtf8Length; +import com.code_intelligence.jazzer.mutation.api.Debuggable; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import java.lang.reflect.AnnotatedType; +import java.nio.charset.StandardCharsets; +import java.util.Optional; +import java.util.function.Predicate; + +final class StringMutatorFactory extends MutatorFactory { + private static final int HEADER_MASK = 0b1100_0000; + private static final int BODY_MASK = 0b0011_1111; + private static final int CONTINUATION_HEADER = 0b1000_0000; + + private static final int DEFAULT_MIN_BYTES = 0; + + private static final int DEFAULT_MAX_BYTES = 1000; + + static void fixUpAscii(byte[] bytes) { + for (int i = 0; i < bytes.length; i++) { + bytes[i] &= 0x7F; + } + } + + // Based on + // https://github.com/google/libprotobuf-mutator/blob/af3bb18749db3559dc4968dd85319d05168d4b5e/src/utf8_fix.cc#L32 + // SPDX: Apache-2.0 + // Copyright 2022 Google LLC + static void fixUpUtf8(byte[] bytes) { + for (int pos = 0; pos < bytes.length;) { + // Leniently read a UTF-8 code point consisting of any byte viewed as the leading byte and up + // to three following bytes that have a continuation byte header. + // + // Since the upper two bits of a byte are 10 with probability 25%, this roughly results in + // the following distribution for characters: + // + // ASCII code point: 75% + // two-byte UTF-8: 18.75% + // three-byte UTF-8: ~4.7% + // four-byte UTF-8: ~1.2% + int scanPos = pos + 1; + int maxScanPos = Math.min(pos + 4, bytes.length); + + int codePoint = bytes[pos] & 0xFF; + for (; scanPos < maxScanPos; scanPos++) { + byte b = bytes[scanPos]; + if ((b & HEADER_MASK) != CONTINUATION_HEADER) { + break; + } + codePoint = (codePoint << 6) + (b & BODY_MASK); + } + + int size = scanPos - pos; + int nextPos = scanPos; + switch (size) { + case 1: + // Force code point to be ASCII. + codePoint &= 0x7F; + + bytes[pos] = (byte) codePoint; + break; + case 2: + codePoint &= 0x7FF; + if (codePoint <= 0x7F) { + // The code point encoding must not be longer than necessary, so fix up the code point + // to actually require two bytes without fixing too many bits. + codePoint |= 0x80; + } + + bytes[--scanPos] = (byte) (CONTINUATION_HEADER | (codePoint & BODY_MASK)); + codePoint >>= 6; + bytes[pos] = (byte) (0b1100_0000 | codePoint); + break; + case 3: + codePoint &= 0xFFFF; + if (codePoint <= 0x7FF) { + // The code point encoding must not be longer than necessary, so fix up the code point + // to actually require three bytes without fixing too many bits. + codePoint |= 0x800; + } + if (codePoint >= 0xD800 && codePoint <= 0xDFFF) { + // The code point must not be a low or high UTF-16 surrogate pair, which are not allowed + // in UTF-8. + codePoint |= (codePoint & ~0xF000) | 0xE000; + } + + bytes[--scanPos] = (byte) (CONTINUATION_HEADER | (codePoint & BODY_MASK)); + codePoint >>= 6; + bytes[--scanPos] = (byte) (CONTINUATION_HEADER | (codePoint & BODY_MASK)); + codePoint >>= 6; + bytes[pos] = (byte) (0b1110_0000 | codePoint); + break; + case 4: + codePoint &= 0x1FFFFF; + if (codePoint <= 0xFFFF) { + // The code point encoding must not be longer than necessary, so fix up the code point + // to actually require four bytes without fixing too many bits. + codePoint |= 0x100000; + } + if (codePoint > 0x10FFFF) { + // The code point must be in the valid Unicode range, so fix it up by clearing as few + // bits as possible. + codePoint &= ~0x10FFFF; + } + + bytes[--scanPos] = (byte) (CONTINUATION_HEADER | (codePoint & BODY_MASK)); + codePoint >>= 6; + bytes[--scanPos] = (byte) (CONTINUATION_HEADER | (codePoint & BODY_MASK)); + codePoint >>= 6; + bytes[--scanPos] = (byte) (CONTINUATION_HEADER | (codePoint & BODY_MASK)); + codePoint >>= 6; + bytes[pos] = (byte) (0b1111_0000 | codePoint); + break; + default: + throw new IllegalStateException("Not reached as scanPos <= pos + 4"); + } + + pos = nextPos; + } + } + + @Override + public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) { + Optional<WithUtf8Length> utf8Length = + Optional.ofNullable(type.getAnnotation(WithUtf8Length.class)); + int min = utf8Length.map(WithUtf8Length::min).orElse(DEFAULT_MIN_BYTES); + int max = utf8Length.map(WithUtf8Length::max).orElse(DEFAULT_MAX_BYTES); + + AnnotatedType innerByteArray = notNull(withLength(asAnnotatedType(byte[].class), min, max)); + + return findFirstParentIfClass(type, String.class) + .flatMap(parent -> factory.tryCreate(innerByteArray)) + .map(byteArrayMutator -> { + boolean fixUpAscii = type.getDeclaredAnnotation(Ascii.class) != null; + return mutateThenMapToImmutable((SerializingMutator<byte[]>) byteArrayMutator, + bytes + -> { + if (fixUpAscii) { + fixUpAscii(bytes); + } else { + fixUpUtf8(bytes); + } + return new String(bytes, StandardCharsets.UTF_8); + }, + string + -> string.getBytes(StandardCharsets.UTF_8), + (Predicate<Debuggable> inCycle) -> "String"); + }); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/BUILD.bazel new file mode 100644 index 00000000..284264bb --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/BUILD.bazel @@ -0,0 +1,15 @@ +java_library( + name = "libfuzzer", + srcs = ["LibFuzzerMutator.java"], + visibility = [ + # libFuzzer's mutators should only by used by mutators for primitive types as we want to get + # rid of this dependency eventually. + "//src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang:__pkg__", + "//src/test/java/com/code_intelligence/jazzer/mutation/mutator/lang:__subpackages__", + ], + deps = [ + "//src/main/java/com/code_intelligence/jazzer/mutation/api", + "//src/main/java/com/code_intelligence/jazzer/mutation/support", + "//src/main/java/com/code_intelligence/jazzer/runtime:mutator", + ], +) diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/LibFuzzerMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/LibFuzzerMutator.java new file mode 100644 index 00000000..c77c75e5 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/libfuzzer/LibFuzzerMutator.java @@ -0,0 +1,92 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.libfuzzer; + +import static com.code_intelligence.jazzer.mutation.support.Preconditions.require; + +import com.code_intelligence.jazzer.mutation.api.Serializer; +import com.code_intelligence.jazzer.runtime.Mutator; +import java.io.ByteArrayInputStream; +import java.io.ByteArrayOutputStream; +import java.io.IOException; +import java.util.Arrays; + +public final class LibFuzzerMutator { + /** + * Key name to give to {@link System#setProperty(String, String)} to control the size of the + * returned array for {@link #defaultMutateMock(byte[], int)}. Only used for testing purposes. + */ + public static final String MOCK_SIZE_KEY = "libfuzzermutator.mock.newsize"; + + public static byte[] mutateDefault(byte[] data, int maxSizeIncrease) { + byte[] mutatedBytes; + if (maxSizeIncrease == 0) { + mutatedBytes = data; + } else { + mutatedBytes = Arrays.copyOf(data, data.length + maxSizeIncrease); + } + int newSize = defaultMutate(mutatedBytes, data.length); + if (newSize == 0) { + // Mutation failed. This should happen very rarely. + return data; + } + return Arrays.copyOf(mutatedBytes, newSize); + } + + public static <T> T mutateDefault(T value, Serializer<T> serializer, int maxSizeIncrease) { + require(maxSizeIncrease >= 0); + ByteArrayOutputStream out = new ByteArrayOutputStream(); + try { + serializer.writeExclusive(value, out); + } catch (IOException e) { + throw new IllegalStateException( + "writeExclusive is not expected to throw if the underlying stream doesn't", e); + } + + byte[] mutatedBytes = mutateDefault(out.toByteArray(), maxSizeIncrease); + + try { + return serializer.readExclusive(new ByteArrayInputStream(mutatedBytes)); + } catch (IOException e) { + throw new IllegalStateException( + "readExclusive is not expected to throw if the underlying stream doesn't", e); + } + } + + private static int defaultMutate(byte[] buffer, int size) { + if (Mutator.SHOULD_MOCK) { + return defaultMutateMock(buffer, size); + } else { + return Mutator.defaultMutateNative(buffer, size); + } + } + + private static int defaultMutateMock(byte[] buffer, int size) { + String newSizeProp = System.getProperty(MOCK_SIZE_KEY); + int newSize = Math.min(buffer.length, size + 1); + if (newSizeProp != null) { + newSize = Integer.parseUnsignedInt(newSizeProp); + } + + for (int i = 0; i < newSize; i++) { + buffer[i] += i + 1; + } + return newSize; + } + + private LibFuzzerMutator() {} +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BUILD.bazel new file mode 100644 index 00000000..2c591709 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BUILD.bazel @@ -0,0 +1,16 @@ +java_library( + name = "proto", + srcs = glob(["*.java"]), + visibility = [ + "//src/main/java/com/code_intelligence/jazzer/mutation/mutator:__pkg__", + "//src/test/java/com/code_intelligence/jazzer/mutation/mutator/proto:__pkg__", + ], + deps = [ + "//src/main/java/com/code_intelligence/jazzer/mutation/annotation", + "//src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto", + "//src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto:protobuf_runtime_compile_only", + "//src/main/java/com/code_intelligence/jazzer/mutation/api", + "//src/main/java/com/code_intelligence/jazzer/mutation/combinator", + "//src/main/java/com/code_intelligence/jazzer/mutation/support", + ], +) diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderAdapters.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderAdapters.java new file mode 100644 index 00000000..12dcd406 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderAdapters.java @@ -0,0 +1,188 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.proto; + +import static java.util.Collections.singletonList; + +import com.google.protobuf.Descriptors.FieldDescriptor; +import com.google.protobuf.Message; +import com.google.protobuf.Message.Builder; +import java.util.AbstractList; +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; + +final class BuilderAdapters { + private BuilderAdapters() {} + + static <T extends Builder, U> List<U> makeMutableRepeatedFieldView( + T builder, FieldDescriptor field) { + return new AbstractList<U>() { + // O(1) + @Override + public U get(int index) { + return (U) builder.getRepeatedField(field, index); + } + + // O(1) + @Override + public int size() { + return builder.getRepeatedFieldCount(field); + } + + // O(1) + @Override + public boolean add(U element) { + builder.addRepeatedField(field, element); + return true; + } + + // O(1) + @Override + public void add(int index, U element) { + addAll(index, singletonList(element)); + } + + // O(size() + other.size()) + public boolean addAll(int index, Collection<? extends U> other) { + // This was benchmarked against the following implementation and found to be faster in all + // cases (up to 4x on lists of size 1000): + // + // for (U element : other) { + // builder.addRepeatedField(field, element); + // } + // Collections.rotate(subList(index, size()), other.size()); + int otherSize = other.size(); + if (otherSize == 0) { + return false; + } + + int originalSize = size(); + if (index == originalSize) { + for (U element : other) { + builder.addRepeatedField(field, element); + } + return true; + } + + int newSize = originalSize + otherSize; + ArrayList<U> temp = new ArrayList<>(newSize); + for (int i = 0; i < index; i++) { + temp.add((U) builder.getRepeatedField(field, i)); + } + temp.addAll(other); + for (int i = index; i < originalSize; i++) { + temp.add((U) builder.getRepeatedField(field, i)); + } + + replaceWith(temp); + return true; + } + + // O(1) + @Override + public U set(int index, U element) { + U previous = get(index); + builder.setRepeatedField(field, index, element); + return previous; + } + + // O(size()) + @Override + public U remove(int index) { + U removed = get(index); + removeRange(index, index + 1); + return removed; + } + + // O(size() - (toIndex - fromIndex)) + @Override + protected void removeRange(int fromIndex, int toIndex) { + int originalSize = size(); + int newSize = originalSize - (toIndex - fromIndex); + if (newSize == 0) { + builder.clearField(field); + return; + } + + // There is no way to remove individual repeated field entries without clearing the entire + // field, so we have to iterate over all entries and keep them in a temporary list. + ArrayList<U> temp = new ArrayList<>(newSize); + for (int i = 0; i < fromIndex; i++) { + temp.add((U) builder.getRepeatedField(field, i)); + } + for (int i = toIndex; i < originalSize; i++) { + temp.add((U) builder.getRepeatedField(field, i)); + } + + replaceWith(temp); + } + + private void replaceWith(ArrayList<U> temp) { + builder.clearField(field); + for (U element : temp) { + builder.addRepeatedField(field, element); + } + } + }; + } + + static <T extends Builder, U> U getPresentFieldOrNull(T builder, FieldDescriptor field) { + if (builder.hasField(field)) { + return (U) builder.getField(field); + } else { + return null; + } + } + + static <T extends Builder, U> void setFieldWithPresence( + T builder, FieldDescriptor field, U value) { + if (value == null) { + builder.clearField(field); + } else { + builder.setField(field, value); + } + } + + static <T extends Builder, K, V> Map<K, V> getMapField(T builder, FieldDescriptor field) { + int size = builder.getRepeatedFieldCount(field); + FieldDescriptor keyField = field.getMessageType().getFields().get(0); + FieldDescriptor valueField = field.getMessageType().getFields().get(1); + HashMap<K, V> map = new HashMap<>(size); + for (int i = 0; i < size; i++) { + Message entry = (Message) builder.getRepeatedField(field, i); + map.put((K) entry.getField(keyField), (V) entry.getField(valueField)); + } + return map; + } + + static <T extends Builder, K, V> void setMapField( + Builder builder, FieldDescriptor field, Map<K, V> map) { + builder.clearField(field); + FieldDescriptor keyField = field.getMessageType().getFields().get(0); + FieldDescriptor valueField = field.getMessageType().getFields().get(1); + Builder entryBuilder = builder.newBuilderForField(field); + for (Entry<K, V> entry : map.entrySet()) { + entryBuilder.setField(keyField, entry.getKey()); + entryBuilder.setField(valueField, entry.getValue()); + builder.addRepeatedField(field, entryBuilder.build()); + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorFactory.java new file mode 100644 index 00000000..85427c6f --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/BuilderMutatorFactory.java @@ -0,0 +1,451 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.proto; + +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.assemble; +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.combine; +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.fixedValue; +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateIndices; +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateProperty; +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateSumInPlace; +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateThenMapToImmutable; +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateViaView; +import static com.code_intelligence.jazzer.mutation.mutator.proto.BuilderAdapters.getMapField; +import static com.code_intelligence.jazzer.mutation.mutator.proto.BuilderAdapters.getPresentFieldOrNull; +import static com.code_intelligence.jazzer.mutation.mutator.proto.BuilderAdapters.makeMutableRepeatedFieldView; +import static com.code_intelligence.jazzer.mutation.mutator.proto.BuilderAdapters.setFieldWithPresence; +import static com.code_intelligence.jazzer.mutation.mutator.proto.BuilderAdapters.setMapField; +import static com.code_intelligence.jazzer.mutation.mutator.proto.TypeLibrary.getDefaultInstance; +import static com.code_intelligence.jazzer.mutation.mutator.proto.TypeLibrary.withoutInitIfRecursive; +import static com.code_intelligence.jazzer.mutation.support.InputStreamSupport.cap; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asAnnotatedType; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asSubclassOrEmpty; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.findFirstParentIfClass; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.notNull; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.withExtraAnnotations; +import static java.util.Arrays.stream; +import static java.util.Objects.requireNonNull; +import static java.util.function.UnaryOperator.identity; +import static java.util.stream.Collectors.groupingBy; +import static java.util.stream.Collectors.toList; +import static java.util.stream.Collectors.toMap; + +import com.code_intelligence.jazzer.mutation.annotation.proto.AnySource; +import com.code_intelligence.jazzer.mutation.annotation.proto.WithDefaultInstance; +import com.code_intelligence.jazzer.mutation.api.ChainedMutatorFactory; +import com.code_intelligence.jazzer.mutation.api.InPlaceMutator; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; +import com.code_intelligence.jazzer.mutation.api.Serializer; +import com.code_intelligence.jazzer.mutation.api.SerializingInPlaceMutator; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import com.code_intelligence.jazzer.mutation.support.Preconditions; +import com.google.protobuf.Any; +import com.google.protobuf.Descriptors.Descriptor; +import com.google.protobuf.Descriptors.EnumDescriptor; +import com.google.protobuf.Descriptors.EnumValueDescriptor; +import com.google.protobuf.Descriptors.FieldDescriptor; +import com.google.protobuf.Descriptors.FieldDescriptor.JavaType; +import com.google.protobuf.Descriptors.OneofDescriptor; +import com.google.protobuf.DynamicMessage; +import com.google.protobuf.InvalidProtocolBufferException; +import com.google.protobuf.Message; +import com.google.protobuf.Message.Builder; +import com.google.protobuf.UnknownFieldSet; +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; +import java.lang.annotation.Annotation; +import java.lang.reflect.AnnotatedType; +import java.util.HashMap; +import java.util.IdentityHashMap; +import java.util.LinkedHashMap; +import java.util.List; +import java.util.Map; +import java.util.Objects; +import java.util.Optional; +import java.util.stream.IntStream; +import java.util.stream.Stream; + +public final class BuilderMutatorFactory extends MutatorFactory { + private <T extends Builder, U> InPlaceMutator<T> mutatorForField( + FieldDescriptor field, Annotation[] annotations, MutatorFactory factory) { + factory = withDescriptorDependentMutatorFactoryIfNeeded(factory, field, annotations); + AnnotatedType typeToMutate = TypeLibrary.getTypeToMutate(field); + requireNonNull(typeToMutate, () -> "Java class not specified for " + field); + + InPlaceMutator<T> mutator; + if (field.isMapField()) { + SerializingInPlaceMutator<Map> underlyingMutator = + (SerializingInPlaceMutator<Map>) factory.createInPlaceOrThrow(typeToMutate); + mutator = mutateProperty(builder + -> getMapField(builder, field), + underlyingMutator, (builder, value) -> setMapField(builder, field, value)); + } else if (field.isRepeated()) { + SerializingInPlaceMutator<List<U>> underlyingMutator = + (SerializingInPlaceMutator<List<U>>) factory.createInPlaceOrThrow(typeToMutate); + mutator = + mutateViaView(builder -> makeMutableRepeatedFieldView(builder, field), underlyingMutator); + } else if (field.hasPresence()) { + SerializingMutator<U> underlyingMutator = + (SerializingMutator<U>) factory.createOrThrow(typeToMutate); + mutator = mutateProperty(builder + -> getPresentFieldOrNull(builder, field), + underlyingMutator, (builder, value) -> setFieldWithPresence(builder, field, value)); + } else { + SerializingMutator<U> underlyingMutator = + (SerializingMutator<U>) factory.createOrThrow(typeToMutate); + mutator = mutateProperty(builder + -> (U) builder.getField(field), + underlyingMutator, (builder, value) -> builder.setField(field, value)); + } + + // If recursive message fields (i.e. those that have themselves as transitive subfields) are + // initialized eagerly, they tend to nest very deeply, which easily results in stack overflows. + // We guard against that by making their init a no-op and instead initialize them layer by layer + // in mutations. + return withoutInitIfRecursive(mutator, field); + } + + private MutatorFactory withDescriptorDependentMutatorFactoryIfNeeded( + MutatorFactory originalFactory, FieldDescriptor field, Annotation[] annotations) { + if (field.getJavaType() == JavaType.ENUM) { + // Proto enum fields are special as their type (EnumValueDescriptor) does not encode their + // domain - we need the actual EnumDescriptor instance. + return new ChainedMutatorFactory(originalFactory, new MutatorFactory() { + @Override + public Optional<SerializingMutator<?>> tryCreate( + AnnotatedType type, MutatorFactory factory) { + return findFirstParentIfClass(type, EnumValueDescriptor.class).map(parent -> { + EnumDescriptor enumType = field.getEnumType(); + List<EnumValueDescriptor> values = enumType.getValues(); + String name = enumType.getName(); + if (values.size() == 1) { + // While we generally prefer to error out instead of creating a mutator that can't + // actually mutate its domain, we can't do that for proto enum fields as the user + // creating the fuzz test may not be in a position to modify the existing proto + // definition. + return fixedValue(values.get(0)); + } else { + return mutateThenMapToImmutable(mutateIndices(values.size()), values::get, + EnumValueDescriptor::getIndex, unused -> "Enum<" + name + ">"); + } + }); + } + }); + } else if (field.getJavaType() == JavaType.MESSAGE) { + Descriptor messageDescriptor; + if (field.isMapField()) { + // Map fields are represented as messages, but we mutate them as actual Java Maps. In case + // the values of the proto map are themselves messages, we need to mutate their type. + FieldDescriptor valueField = field.getMessageType().getFields().get(1); + if (valueField.getJavaType() != JavaType.MESSAGE) { + return originalFactory; + } + messageDescriptor = valueField.getMessageType(); + } else { + messageDescriptor = field.getMessageType(); + } + return new ChainedMutatorFactory(originalFactory, new MutatorFactory() { + @Override + public Optional<SerializingMutator<?>> tryCreate( + AnnotatedType type, MutatorFactory factory) { + return asSubclassOrEmpty(type, Message.Builder.class).flatMap(clazz -> { + // BuilderMutatorFactory only handles subclasses of Message.Builder and requests + // Message.Builder itself for message fields, which we handle here. + if (clazz != Message.Builder.class) { + return Optional.empty(); + } + // It is important that we use originalFactory here instead of factory: factory has this + // field-specific message mutator appended, but this mutator should only be used for + // this particular field and not any message subfields. + return Optional.of(makeBuilderMutator(originalFactory, + DynamicMessage.getDefaultInstance(messageDescriptor), annotations)); + }); + } + }); + } else { + return originalFactory; + } + } + + private <T extends Builder> Stream<InPlaceMutator<T>> mutatorsForFields( + Optional<OneofDescriptor> oneofField, List<FieldDescriptor> fields, Annotation[] annotations, + MutatorFactory factory) { + if (oneofField.isPresent()) { + // oneof fields are mutated as one as mutating them independently would cause the mutator to + // erratically switch between the different states. The individual fields are kept in the + // order in which they are defined in the .proto file. + OneofDescriptor oneofDescriptor = oneofField.get(); + + IdentityHashMap<FieldDescriptor, Integer> indexInOneof = + new IdentityHashMap<>(oneofDescriptor.getFieldCount()); + for (int i = 0; i < oneofDescriptor.getFieldCount(); i++) { + indexInOneof.put(oneofDescriptor.getField(i), i); + } + + return Stream.of(mutateSumInPlace( + (T builder) + -> { + FieldDescriptor setField = builder.getOneofFieldDescriptor(oneofDescriptor); + if (setField == null) { + return -1; + } else { + return indexInOneof.get(setField); + } + }, + // Mutating to the unset (-1) state is handled by the individual field mutators, which + // are created nullable as oneof fields report that they track presence. + fields.stream() + .map(field -> mutatorForField(field, annotations, factory)) + .toArray(InPlaceMutator[] ::new))); + } else { + // All non-oneof fields are mutated independently, using the order in which they are declared + // in the .proto file (which may not coincide with the order by field number). + return fields.stream().map(field -> mutatorForField(field, annotations, factory)); + } + } + + private static <M extends Message, B extends Builder> Serializer<B> makeBuilderSerializer( + M defaultInstance) { + return new Serializer<B>() { + @Override + public B read(DataInputStream in) throws IOException { + int length = Math.max(in.readInt(), 0); + return (B) parseLeniently(cap(in, length)); + } + + @Override + public B readExclusive(InputStream in) throws IOException { + return (B) parseLeniently(in); + } + + private Builder parseLeniently(InputStream in) throws IOException { + Builder builder = defaultInstance.toBuilder(); + try { + builder.mergeFrom(in); + } catch (InvalidProtocolBufferException ignored) { + // builder has been partially modified with what could be decoded before the parser error. + } + // We never want the fuzz test to see unknown fields and our mutations should never produce + // them. + builder.setUnknownFields(UnknownFieldSet.getDefaultInstance()); + // Required fields may not have been set at this point. We set them to default values to + // prevent an exception when built. + forceInitialized(builder); + return builder; + } + + private void forceInitialized(Builder builder) { + if (builder.isInitialized()) { + return; + } + for (FieldDescriptor field : builder.getDescriptorForType().getFields()) { + if (!field.isRequired()) { + continue; + } + if (field.getJavaType() == JavaType.MESSAGE) { + forceInitialized(builder.getFieldBuilder(field)); + } else if (!builder.hasField(field)) { + builder.setField(field, field.getDefaultValue()); + } + } + } + + @Override + public void write(Builder builder, DataOutputStream out) throws IOException { + Message message = builder.build(); + out.writeInt(message.getSerializedSize()); + message.writeTo(out); + } + + @Override + public void writeExclusive(Builder builder, OutputStream out) throws IOException { + builder.build().writeTo(out); + } + + @Override + public B detach(Builder builder) { + return (B) builder.build().toBuilder(); + } + }; + } + + /* + * Ensures that only a single instance is created per builder class and shared among all mutators + * that need it. This ensures that arbitrarily nested recursive structures such as a Protobuf + * message type that contains itself as a message field are representable as fixed-size mutator + * structures. + * + * Note: The resulting mutator structures may no longer form a tree: If A is a protobuf message + * type with a message field B and B in turn has a message field of type A, then the mutators for + * A and B will reference each other, forming a cycle. + */ + private final HashMap<CacheKey, SerializingMutator<? extends Builder>> internedMutators = + new HashMap<>(); + + private SerializingMutator<Any.Builder> mutatorForAny( + AnySource anySource, MutatorFactory factory) { + Map<String, Integer> typeUrlToIndex = + IntStream.range(0, anySource.value().length) + .boxed() + .collect(toMap(i -> getTypeUrl(getDefaultInstance(anySource.value()[i])), identity())); + + return assemble(mutator + -> internedMutators.put(new CacheKey(Any.getDescriptor(), anySource), mutator), + Any.getDefaultInstance()::toBuilder, makeBuilderSerializer(Any.getDefaultInstance()), + () + -> mutateSumInPlace( + // Corpus entries may contain Anys with arbitrary (and even invalid) messages, so we + // fall back to mutating the first message type if the type isn't recognized. + (Any.Builder builder) + -> typeUrlToIndex.getOrDefault(builder.getTypeUrl(), 0), + stream(anySource.value()) + .map(messageClass -> { + SerializingMutator<Message> messageMutator = + (SerializingMutator<Message>) factory.createOrThrow(notNull( + withExtraAnnotations(asAnnotatedType(messageClass), anySource))); + return mutateProperty( + (Any.Builder anyBuilder) + -> { + try { + return anyBuilder.build().unpack(messageClass); + } catch (InvalidProtocolBufferException e) { + // This can only happen if the corpus contains an invalid Any. + return getDefaultInstance(messageClass); + } + }, + messageMutator, + (Any.Builder any, Message message) -> { + any.setTypeUrl(getTypeUrl(message)); + any.setValue(message.toByteString()); + }); + }) + .toArray(InPlaceMutator[] ::new))); + } + + private static String getTypeUrl(Message message) { + // We only support the default "type.googleapis.com" prefix. + // https://github.com/protocolbuffers/protobuf/blob/main/src/google/protobuf/any.proto#L94 + return "type.googleapis.com/" + message.getDescriptorForType().getFullName(); + } + + @Override + public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) { + return asSubclassOrEmpty(type, Builder.class).flatMap(builderClass -> { + Message defaultInstance; + WithDefaultInstance withDefaultInstance = type.getAnnotation(WithDefaultInstance.class); + if (withDefaultInstance != null) { + defaultInstance = getDefaultInstance(withDefaultInstance); + } else if (builderClass == DynamicMessage.Builder.class) { + throw new IllegalArgumentException( + "To mutate a dynamic message, add a @WithDefaultInstance annotation specifying the" + + " fully qualified method name of a static method returning a default instance"); + } else if (builderClass == Message.Builder.class) { + // Handled by a custom mutator factory for message fields that is created in + // withDescriptorDependentMutatorFactoryIfNeeded. Without @WithDefaultInstance, + // BuilderMutatorFactory only handles proper subclasses, which correspond to generated + // message types. + return Optional.empty(); + } else { + defaultInstance = + getDefaultInstance((Class<? extends Message>) builderClass.getEnclosingClass()); + } + + return Optional.of( + makeBuilderMutator(factory, defaultInstance, type.getDeclaredAnnotations())); + }); + } + + private SerializingMutator<?> makeBuilderMutator( + MutatorFactory factory, Message defaultInstance, Annotation[] annotations) { + AnySource anySource = (AnySource) stream(annotations) + .filter(annotation -> annotation.annotationType() == AnySource.class) + .findFirst() + .orElse(null); + Preconditions.require(anySource == null || anySource.value().length > 0, + "@AnySource must list a non-empty list of classes"); + Descriptor descriptor = defaultInstance.getDescriptorForType(); + + CacheKey cacheKey = new CacheKey(descriptor, anySource); + if (internedMutators.containsKey(cacheKey)) { + return internedMutators.get(cacheKey); + } + + // If there is no @AnySource, mutate the Any.Builder fields just like a regular message. + // TODO: Determine whether we should show a warning in this case. + if (descriptor.equals(Any.getDescriptor()) && anySource != null) { + return mutatorForAny(anySource, factory); + } + + // assemble inserts the instance of the newly created builder mutator into the + // internedMutators map *before* recursively creating the mutators for its fields, which + // ensures that the recursion is finite (bounded by the total number of distinct message types + // that transitively occur as field types on the current message type). + return assemble(mutator + -> internedMutators.put(cacheKey, mutator), + defaultInstance::toBuilder, makeBuilderSerializer(defaultInstance), + () + -> combine( + descriptor.getFields() + .stream() + // Keep oneofs sorted by the first appearance of their fields in the + // .proto file. + .collect(groupingBy( + // groupingBy does not support null keys. We use getRealContainingOneof() + // instead of getContainingOneof() as the latter also reports oneofs for + // proto3 optional fields, which we handle separately. + fieldDescriptor + -> Optional.ofNullable(fieldDescriptor.getRealContainingOneof()), + LinkedHashMap::new, toList())) + .entrySet() + .stream() + .flatMap(entry + -> mutatorsForFields(entry.getKey(), entry.getValue(), + anySource == null ? new Annotation[0] : new Annotation[] {anySource}, + factory)) + .toArray(InPlaceMutator[] ::new))); + } + + private static final class CacheKey { + private final Descriptor descriptor; + private final AnySource anySource; + + private CacheKey(Descriptor descriptor, AnySource anySource) { + this.descriptor = descriptor; + this.anySource = anySource; + } + + @Override + public boolean equals(Object o) { + if (this == o) { + return true; + } + if (o == null || getClass() != o.getClass()) { + return false; + } + CacheKey cacheKey = (CacheKey) o; + return descriptor == cacheKey.descriptor && Objects.equals(anySource, cacheKey.anySource); + } + + @Override + public int hashCode() { + return 31 * System.identityHashCode(descriptor) + Objects.hashCode(anySource); + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ByteStringMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ByteStringMutatorFactory.java new file mode 100644 index 00000000..a01ffae6 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ByteStringMutatorFactory.java @@ -0,0 +1,41 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.proto; + +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateThenMapToImmutable; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asAnnotatedType; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.findFirstParentIfClass; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.notNull; + +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import com.google.protobuf.ByteString; +import java.lang.reflect.AnnotatedType; +import java.util.Optional; + +final class ByteStringMutatorFactory extends MutatorFactory { + ByteStringMutatorFactory() {} + + @Override + public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory factory) { + return findFirstParentIfClass(type, ByteString.class) + .flatMap(parent -> factory.tryCreate(notNull(asAnnotatedType(byte[].class)))) + .map(byteArrayMutator + -> mutateThenMapToImmutable((SerializingMutator<byte[]>) byteArrayMutator, + ByteString::copyFrom, ByteString::toByteArray)); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/MessageMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/MessageMutatorFactory.java new file mode 100644 index 00000000..eb3220f5 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/MessageMutatorFactory.java @@ -0,0 +1,52 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.proto; + +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.mutateThenMapToImmutable; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asAnnotatedType; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asSubclassOrEmpty; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.withExtraAnnotations; + +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; +import com.code_intelligence.jazzer.mutation.api.SerializingMutator; +import com.google.protobuf.Message; +import com.google.protobuf.Message.Builder; +import java.lang.reflect.AnnotatedType; +import java.util.Arrays; +import java.util.Optional; + +public final class MessageMutatorFactory extends MutatorFactory { + @Override + public Optional<SerializingMutator<?>> tryCreate( + AnnotatedType messageType, MutatorFactory factory) { + return asSubclassOrEmpty(messageType, Message.class) + // If the Message class doesn't have a nested Builder class, it is not a concrete generated + // message and we can't mutate it. + .flatMap(messageClass + -> Arrays.stream(messageClass.getDeclaredClasses()) + .filter(clazz -> clazz.getSimpleName().equals("Builder")) + .findFirst()) + .flatMap(builderClass + -> + // Forward the annotations (e.g. @NotNull) on the Message type to the Builder type. + factory.tryCreateInPlace( + withExtraAnnotations(asAnnotatedType(builderClass), messageType.getAnnotations()))) + .map(builderMutator + -> mutateThenMapToImmutable( + (SerializingMutator<Builder>) builderMutator, Builder::build, Message::toBuilder)); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ProtoMutators.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ProtoMutators.java new file mode 100644 index 00000000..acb25cd7 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/ProtoMutators.java @@ -0,0 +1,34 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.proto; + +import com.code_intelligence.jazzer.mutation.api.ChainedMutatorFactory; +import com.code_intelligence.jazzer.mutation.api.MutatorFactory; + +public final class ProtoMutators { + private ProtoMutators() {} + + public static MutatorFactory newFactory() { + try { + Class.forName("com.google.protobuf.Message"); + return new ChainedMutatorFactory( + new ByteStringMutatorFactory(), new MessageMutatorFactory(), new BuilderMutatorFactory()); + } catch (ClassNotFoundException e) { + return new ChainedMutatorFactory(); + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/TypeLibrary.java b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/TypeLibrary.java new file mode 100644 index 00000000..43338f14 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto/TypeLibrary.java @@ -0,0 +1,179 @@ +/* + * Copyright 2023 Code Intelligence GmbH + * + * 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. + */ + +package com.code_intelligence.jazzer.mutation.mutator.proto; + +import static com.code_intelligence.jazzer.mutation.combinator.MutatorCombinators.withoutInit; +import static com.code_intelligence.jazzer.mutation.support.Preconditions.check; +import static com.code_intelligence.jazzer.mutation.support.StreamSupport.entry; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asAnnotatedType; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.containedInDirectedCycle; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.notNull; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.withTypeArguments; +import static java.lang.String.format; +import static java.util.Collections.unmodifiableMap; +import static java.util.stream.Collectors.collectingAndThen; +import static java.util.stream.Collectors.toMap; + +import com.code_intelligence.jazzer.mutation.annotation.NotNull; +import com.code_intelligence.jazzer.mutation.annotation.proto.WithDefaultInstance; +import com.code_intelligence.jazzer.mutation.api.InPlaceMutator; +import com.code_intelligence.jazzer.mutation.support.TypeHolder; +import com.google.protobuf.ByteString; +import com.google.protobuf.Descriptors.Descriptor; +import com.google.protobuf.Descriptors.EnumValueDescriptor; +import com.google.protobuf.Descriptors.FieldDescriptor; +import com.google.protobuf.Descriptors.FieldDescriptor.JavaType; +import com.google.protobuf.DynamicMessage; +import com.google.protobuf.Message; +import com.google.protobuf.Message.Builder; +import java.lang.reflect.AnnotatedType; +import java.lang.reflect.Field; +import java.lang.reflect.InvocationTargetException; +import java.lang.reflect.Method; +import java.lang.reflect.Modifier; +import java.util.EnumMap; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.stream.Stream; + +final class TypeLibrary { + private static final AnnotatedType RAW_LIST = new TypeHolder<@NotNull List>() {}.annotatedType(); + private static final AnnotatedType RAW_MAP = new TypeHolder<@NotNull Map>() {}.annotatedType(); + private static final Map<JavaType, AnnotatedType> BASE_TYPE_WITH_PRESENCE = + Stream + .of(entry(JavaType.BOOLEAN, Boolean.class), entry(JavaType.BYTE_STRING, ByteString.class), + entry(JavaType.DOUBLE, Double.class), entry(JavaType.ENUM, EnumValueDescriptor.class), + entry(JavaType.FLOAT, Float.class), entry(JavaType.INT, Integer.class), + entry(JavaType.LONG, Long.class), entry(JavaType.MESSAGE, Message.class), + entry(JavaType.STRING, String.class)) + .collect(collectingAndThen(toMap(Entry::getKey, e -> asAnnotatedType(e.getValue())), + map -> unmodifiableMap(new EnumMap<>(map)))); + + private TypeLibrary() {} + + static <T extends Builder> AnnotatedType getTypeToMutate(FieldDescriptor field) { + if (field.isRequired()) { + return getBaseType(field); + } else if (field.isMapField()) { + // Map fields are represented as repeated message fields, so this check has to come before the + // one for regular repeated fields. + AnnotatedType keyType = getBaseType(field.getMessageType().getFields().get(0)); + AnnotatedType valueType = getBaseType(field.getMessageType().getFields().get(1)); + return withTypeArguments(RAW_MAP, keyType, valueType); + } else if (field.isRepeated()) { + return withTypeArguments(RAW_LIST, getBaseType(field)); + } else if (field.hasPresence()) { + return BASE_TYPE_WITH_PRESENCE.get(field.getJavaType()); + } else { + return getBaseType(field); + } + } + + private static <T extends Builder> AnnotatedType getBaseType(FieldDescriptor field) { + return notNull(BASE_TYPE_WITH_PRESENCE.get(field.getJavaType())); + } + + static <T> InPlaceMutator<T> withoutInitIfRecursive( + InPlaceMutator<T> mutator, FieldDescriptor field) { + if (field.isRequired() || !isRecursiveField(field)) { + return mutator; + } + return withoutInit(mutator); + } + + private static boolean isRecursiveField(FieldDescriptor field) { + return containedInDirectedCycle(field, f -> { + // For map fields, only the value can be a message. + FieldDescriptor realField = f.isMapField() ? f.getMessageType().getFields().get(1) : f; + if (realField.getJavaType() != JavaType.MESSAGE) { + return Stream.empty(); + } + return realField.getMessageType().getFields().stream(); + }); + } + + static Message getDefaultInstance(Class<? extends Message> messageClass) { + Method getDefaultInstance; + try { + getDefaultInstance = messageClass.getMethod("getDefaultInstance"); + check(Modifier.isStatic(getDefaultInstance.getModifiers())); + } catch (NoSuchMethodException e) { + throw new IllegalStateException( + format("Message class for builder type %s does not have a getDefaultInstance method", + messageClass.getName()), + e); + } + try { + return (Message) getDefaultInstance.invoke(null); + } catch (IllegalAccessException | InvocationTargetException e) { + throw new IllegalStateException( + format(getDefaultInstance + " isn't accessible or threw an exception"), e); + } + } + + static Message getDefaultInstance(WithDefaultInstance withDefaultInstance) { + String[] parts = withDefaultInstance.value().split("#"); + if (parts.length != 2) { + throw new IllegalArgumentException( + format("Expected @WithDefaultInstance(\"%s\") to specify a fully-qualified method name" + + " (e.g. com.example.MyClass#getDefaultInstance)", + withDefaultInstance.value())); + } + + Class<?> clazz; + try { + clazz = Class.forName(parts[0]); + } catch (ClassNotFoundException e) { + throw new IllegalArgumentException( + format("Failed to find class '%s' specified by @WithDefaultInstance(\"%s\")", parts[0], + withDefaultInstance.value()), + e); + } + + Method method; + try { + method = clazz.getDeclaredMethod(parts[1]); + method.setAccessible(true); + } catch (NoSuchMethodException e) { + throw new IllegalArgumentException( + format("Failed to find method specified by @WithDefaultInstance(\"%s\")", + withDefaultInstance.value()), + e); + } + if (!Modifier.isStatic(method.getModifiers())) { + throw new IllegalArgumentException( + format("Expected method specified by @WithDefaultInstance(\"%s\") to be static", + withDefaultInstance.value())); + } + if (!Message.class.isAssignableFrom(method.getReturnType())) { + throw new IllegalArgumentException(format( + "Expected return type of method specified by @WithDefaultInstance(\"%s\") to be a" + + " subtype of %s, got %s", + withDefaultInstance.value(), Message.class.getName(), method.getReturnType().getName())); + } + + try { + return (Message) method.invoke(null); + } catch (IllegalAccessException | InvocationTargetException e) { + throw new IllegalArgumentException( + format("Failed to execute method specified by @WithDefaultInstance(\"%s\")", + withDefaultInstance.value()), + e); + } + } +} |