diff options
author | Mark <mteffeteller@google.com> | 2023-06-22 00:59:06 +0000 |
---|---|---|
committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | 2023-06-22 00:59:06 +0000 |
commit | 33edd6723662ea34453766bfdca85dbfdd5342b8 (patch) | |
tree | 68cf332a40b94b2d28b256b19b916f99220bb0c4 /src/main/java/com/code_intelligence/jazzer/mutation | |
parent | ba37c2e361c2ba91bacc47fcae5383c52e50f6be (diff) | |
parent | f1ff6ce482549c51088d0a4b011d676904ad2506 (diff) | |
download | jazzer-api-master.tar.gz |
Sync jazzer in AOSP with upstream repo (new SHA: 30decf81a147c66fa5a098072c38ab6924ba0aa6) am: 9350e0ab03 am: 99d9a79746 am: 34a8e5c8aa am: e73be1680d am: 54819157ea am: f1ff6ce482HEADandroid-14.0.0_r51android-14.0.0_r50android-14.0.0_r37android-14.0.0_r36android-14.0.0_r35android-14.0.0_r34android-14.0.0_r33android-14.0.0_r32android-14.0.0_r31android-14.0.0_r30android-14.0.0_r29mastermainandroid14-qpr3-releaseandroid14-qpr2-s5-releaseandroid14-qpr2-s4-releaseandroid14-qpr2-s3-releaseandroid14-qpr2-s2-releaseandroid14-qpr2-s1-releaseandroid14-qpr2-release
Original change: https://android-review.googlesource.com/c/platform/external/jazzer-api/+/2627336
Change-Id: Iaaed944c1e9e457640f7055fc57e8678f90f4603
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>
Diffstat (limited to 'src/main/java/com/code_intelligence/jazzer/mutation')
68 files changed, 7521 insertions, 0 deletions
diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/ArgumentsMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/ArgumentsMutator.java new file mode 100644 index 00000000..fabda057 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/ArgumentsMutator.java @@ -0,0 +1,232 @@ +/* + * 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; + +import static com.code_intelligence.jazzer.mutation.mutator.Mutators.validateAnnotationUsage; +import static com.code_intelligence.jazzer.mutation.support.InputStreamSupport.extendWithReadExactly; +import static com.code_intelligence.jazzer.mutation.support.Preconditions.require; +import static com.code_intelligence.jazzer.mutation.support.StreamSupport.toArrayOrEmpty; +import static java.lang.String.format; +import static java.util.Arrays.stream; +import static java.util.Objects.requireNonNull; +import static java.util.stream.Collectors.joining; + +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.combinator.MutatorCombinators; +import com.code_intelligence.jazzer.mutation.combinator.ProductMutator; +import com.code_intelligence.jazzer.mutation.engine.SeededPseudoRandom; +import com.code_intelligence.jazzer.mutation.mutator.Mutators; +import com.code_intelligence.jazzer.mutation.support.InputStreamSupport.ReadExactlyInputStream; +import com.code_intelligence.jazzer.mutation.support.Preconditions; +import java.io.ByteArrayInputStream; +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; +import java.io.UncheckedIOException; +import java.lang.reflect.AnnotatedType; +import java.lang.reflect.InvocationTargetException; +import java.lang.reflect.Method; +import java.lang.reflect.Modifier; +import java.util.Optional; + +public final class ArgumentsMutator { + private final Object instance; + private final Method method; + private final ProductMutator productMutator; + private Object[] arguments; + + /** + * True if the arguments array has already been passed to a user-provided function or exposed + * via {@link #getArguments()} without going through {@link ProductMutator#detach(Object[])}. + * In this case the arguments may have been modified externally, which interferes with mutation, + * or could have been stored in static state that would be affected by future mutations. + * Arguments should either be detached or not be reused after being exposed, which is enforced by + * this variable. + */ + private boolean argumentsExposed; + + private ArgumentsMutator(Object instance, Method method, ProductMutator productMutator) { + this.instance = instance; + this.method = method; + this.productMutator = productMutator; + } + + private static String prettyPrintMethod(Method method) { + return format("%s.%s(%s)", method.getDeclaringClass().getName(), method.getName(), + stream(method.getAnnotatedParameterTypes()).map(Object::toString).collect(joining(", "))); + } + + public static ArgumentsMutator forInstanceMethodOrThrow(Object instance, Method method) { + return forInstanceMethod(Mutators.newFactory(), instance, method) + .orElseThrow(() + -> new IllegalArgumentException( + "Failed to construct mutator for " + prettyPrintMethod(method))); + } + + public static ArgumentsMutator forStaticMethodOrThrow(Method method) { + return forStaticMethod(Mutators.newFactory(), method) + .orElseThrow(() + -> new IllegalArgumentException( + "Failed to construct mutator for " + prettyPrintMethod(method))); + } + + public static Optional<ArgumentsMutator> forMethod(Method method) { + return forMethod(Mutators.newFactory(), null, method); + } + + public static Optional<ArgumentsMutator> forInstanceMethod( + MutatorFactory mutatorFactory, Object instance, Method method) { + require(!isStatic(method), "method must not be static"); + requireNonNull(instance, "instance must not be null"); + require(method.getDeclaringClass().isInstance(instance), + format("instance is a %s, expected %s", instance.getClass(), method.getDeclaringClass())); + return forMethod(mutatorFactory, instance, method); + } + + public static Optional<ArgumentsMutator> forStaticMethod( + MutatorFactory mutatorFactory, Method method) { + require(isStatic(method), "method must be static"); + return forMethod(mutatorFactory, null, method); + } + + public static Optional<ArgumentsMutator> forMethod( + MutatorFactory mutatorFactory, Object instance, Method method) { + require(method.getParameterCount() > 0, "Can't fuzz method without parameters: " + method); + for (AnnotatedType parameter : method.getAnnotatedParameterTypes()) { + validateAnnotationUsage(parameter); + } + return toArrayOrEmpty( + stream(method.getAnnotatedParameterTypes()).map(mutatorFactory::tryCreate), + SerializingMutator<?>[] ::new) + .map(MutatorCombinators::mutateProduct) + .map(productMutator -> ArgumentsMutator.create(instance, method, productMutator)); + } + + private static ArgumentsMutator create( + Object instance, Method method, ProductMutator productMutator) { + method.setAccessible(true); + + return new ArgumentsMutator(instance, method, productMutator); + } + + private static boolean isStatic(Method method) { + return Modifier.isStatic(method.getModifiers()); + } + + /** + * @throws UncheckedIOException if the underlying InputStream throws + */ + public void crossOver(InputStream data1, InputStream data2, long seed) { + try { + Object[] objects1 = productMutator.readExclusive(data1); + Object[] objects2 = productMutator.readExclusive(data2); + PseudoRandom prng = new SeededPseudoRandom(seed); + arguments = productMutator.crossOver(objects1, objects2, prng); + argumentsExposed = false; + } catch (IOException e) { + throw new UncheckedIOException(e); + } + } + + /** + * @return if the given input stream was consumed exactly + * @throws UncheckedIOException if the underlying InputStream throws + */ + public boolean read(ByteArrayInputStream data) { + try { + ReadExactlyInputStream is = extendWithReadExactly(data); + arguments = productMutator.readExclusive(is); + argumentsExposed = false; + return is.isConsumedExactly(); + } catch (IOException e) { + throw new UncheckedIOException(e); + } + } + + /** + * @throws UncheckedIOException if the underlying OutputStream throws + */ + public void write(OutputStream data) { + failIfArgumentsExposed(); + writeAny(data, arguments); + } + + /** + * @throws UncheckedIOException if the underlying OutputStream throws + */ + public void writeAny(OutputStream data, Object[] args) throws UncheckedIOException { + try { + productMutator.writeExclusive(args, data); + } catch (IOException e) { + throw new UncheckedIOException(e); + } + } + + public void init(long seed) { + init(new SeededPseudoRandom(seed)); + } + + void init(PseudoRandom prng) { + arguments = productMutator.init(prng); + argumentsExposed = false; + } + + public void mutate(long seed) { + mutate(new SeededPseudoRandom(seed)); + } + + void mutate(PseudoRandom prng) { + failIfArgumentsExposed(); + // TODO: Sometimes mutate the entire byte representation of the current value with libFuzzer's + // dictionary and TORC mutations. + productMutator.mutate(arguments, prng); + } + + public void invoke(boolean detach) throws Throwable { + Object[] invokeArguments; + if (detach) { + invokeArguments = productMutator.detach(arguments); + } else { + invokeArguments = arguments; + argumentsExposed = true; + } + try { + method.invoke(instance, invokeArguments); + } catch (IllegalAccessException e) { + throw new IllegalStateException("method should have been made accessible", e); + } catch (InvocationTargetException e) { + throw e.getCause(); + } + } + + public Object[] getArguments() { + argumentsExposed = true; + return arguments; + } + + @Override + public String toString() { + return "Arguments" + productMutator; + } + + private void failIfArgumentsExposed() { + Preconditions.check(!argumentsExposed, + "Arguments have previously been exposed to user-provided code without calling #detach and may have been modified"); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/BUILD.bazel new file mode 100644 index 00000000..9866c2c4 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/BUILD.bazel @@ -0,0 +1,16 @@ +java_library( + name = "mutation", + 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/combinator", + "//src/main/java/com/code_intelligence/jazzer/mutation/engine", + "//src/main/java/com/code_intelligence/jazzer/mutation/mutator", + "//src/main/java/com/code_intelligence/jazzer/mutation/support", + ], +) diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/AppliesTo.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/AppliesTo.java new file mode 100644 index 00000000..4d4c4a89 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/AppliesTo.java @@ -0,0 +1,40 @@ +/* + * 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.annotation; + +import static java.lang.annotation.ElementType.ANNOTATION_TYPE; +import static java.lang.annotation.RetentionPolicy.RUNTIME; + +import java.lang.annotation.Retention; +import java.lang.annotation.Target; + +/** + * A meta-annotation that limits the concrete types an annotation for type usages applies to. + */ +@Target(ANNOTATION_TYPE) +@Retention(RUNTIME) +public @interface AppliesTo { + /** + * The meta-annotated annotation can be applied to these classes. + */ + Class<?>[] value() default {}; + + /** + * The meta-annotated annotation can be applied to subclasses of these classes. + */ + Class<?>[] subClassesOf() default {}; +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/Ascii.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/Ascii.java new file mode 100644 index 00000000..190ada09 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/Ascii.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.annotation; + +import static java.lang.annotation.ElementType.TYPE_USE; +import static java.lang.annotation.RetentionPolicy.RUNTIME; + +import java.lang.annotation.Retention; +import java.lang.annotation.Target; + +@Target(TYPE_USE) +@Retention(RUNTIME) +@AppliesTo(String.class) +public @interface Ascii {} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/BUILD.bazel new file mode 100644 index 00000000..6d6c4da9 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/BUILD.bazel @@ -0,0 +1,5 @@ +java_library( + name = "annotation", + srcs = glob(["*.java"]), + visibility = ["//visibility:public"], +) diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/DoubleInRange.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/DoubleInRange.java new file mode 100644 index 00000000..27765879 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/DoubleInRange.java @@ -0,0 +1,32 @@ +/* + * 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.annotation; + +import static java.lang.annotation.ElementType.TYPE_USE; +import static java.lang.annotation.RetentionPolicy.RUNTIME; + +import java.lang.annotation.Retention; +import java.lang.annotation.Target; + +@Target(TYPE_USE) +@Retention(RUNTIME) +@AppliesTo({double.class, Double.class}) +public @interface DoubleInRange { + double min() default Double.NEGATIVE_INFINITY; + double max() default Double.POSITIVE_INFINITY; + boolean allowNaN() default true; +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/FloatInRange.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/FloatInRange.java new file mode 100644 index 00000000..ec54e026 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/FloatInRange.java @@ -0,0 +1,32 @@ +/* + * 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.annotation; + +import static java.lang.annotation.ElementType.TYPE_USE; +import static java.lang.annotation.RetentionPolicy.RUNTIME; + +import java.lang.annotation.Retention; +import java.lang.annotation.Target; + +@Target(TYPE_USE) +@Retention(RUNTIME) +@AppliesTo({float.class, Float.class}) +public @interface FloatInRange { + float min() default Float.NEGATIVE_INFINITY; + float max() default Float.POSITIVE_INFINITY; + boolean allowNaN() default true; +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/InRange.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/InRange.java new file mode 100644 index 00000000..a8dc8281 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/InRange.java @@ -0,0 +1,35 @@ +/* + * 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.annotation; + +import static java.lang.annotation.ElementType.TYPE_USE; +import static java.lang.annotation.RetentionPolicy.RUNTIME; + +import java.lang.annotation.ElementType; +import java.lang.annotation.Retention; +import java.lang.annotation.RetentionPolicy; +import java.lang.annotation.Target; + +@Target(TYPE_USE) +@Retention(RUNTIME) +@AppliesTo({byte.class, Byte.class, short.class, Short.class, int.class, Integer.class, long.class, + Long.class}) +public @interface InRange { + long min() default Long.MIN_VALUE; + + long max() default Long.MAX_VALUE; +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/NotNull.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/NotNull.java new file mode 100644 index 00000000..061eeffc --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/NotNull.java @@ -0,0 +1,29 @@ +/* + * 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.annotation; + +import static java.lang.annotation.ElementType.PARAMETER; +import static java.lang.annotation.ElementType.TYPE_USE; +import static java.lang.annotation.RetentionPolicy.RUNTIME; + +import java.lang.annotation.Retention; +import java.lang.annotation.Target; + +@Target({PARAMETER, TYPE_USE}) +@Retention(RUNTIME) +@AppliesTo(subClassesOf = Object.class) +public @interface NotNull {} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithLength.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithLength.java new file mode 100644 index 00000000..7cee23df --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithLength.java @@ -0,0 +1,33 @@ +/* + * 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.annotation; + +import static java.lang.annotation.ElementType.PARAMETER; +import static java.lang.annotation.ElementType.TYPE_USE; +import static java.lang.annotation.RetentionPolicy.RUNTIME; + +import java.lang.annotation.Retention; +import java.lang.annotation.Target; + +@Target(TYPE_USE) +@Retention(RUNTIME) +@AppliesTo(byte[].class) +public @interface WithLength { + int min() default 0; + + int max() default 1000; +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithSize.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithSize.java new file mode 100644 index 00000000..32233f4b --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithSize.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.annotation; + +import static java.lang.annotation.ElementType.TYPE_USE; +import static java.lang.annotation.RetentionPolicy.RUNTIME; + +import java.lang.annotation.Retention; +import java.lang.annotation.Target; +import java.util.List; +import java.util.Map; + +@Target(TYPE_USE) +@Retention(RUNTIME) +@AppliesTo({List.class, Map.class}) +public @interface WithSize { + int min() default 0; + + int max() default 1000; +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithUtf8Length.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithUtf8Length.java new file mode 100644 index 00000000..00b1f463 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/WithUtf8Length.java @@ -0,0 +1,43 @@ +/* + * 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.annotation; + +import static java.lang.annotation.ElementType.TYPE_USE; +import static java.lang.annotation.RetentionPolicy.RUNTIME; + +import java.lang.annotation.Retention; +import java.lang.annotation.Target; + +/** + * An annotation that applies to {@link String} to <strong>limit the length of the UTF-8 + * encoding</strong> of the string. In practical terms, this means that strings given this + * annotation will sometimes have a {@link String#length()} of less than + * {@code min} but will never exceed {@code max}. <p> Due to the fact that our String mutator is + * backed by the byte array mutator, it's difficult to know how many characters we'll get from the + * byte array we get from libfuzzer. Rather than reuse {@link WithLength} for strings which may give + * the impression that {@link String#length()} will return a value between {@code min} and {@code + * max}, we use this annotation to help make clear that the string consists of between + * {@code min} and {@code max} UTF-8 bytes, not necessarily (UTF-16) characters. + */ +@Target(TYPE_USE) +@Retention(RUNTIME) +@AppliesTo(String.class) +public @interface WithUtf8Length { + int min() default 0; + + int max() default 1000; +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/AnySource.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/AnySource.java new file mode 100644 index 00000000..9f802dfe --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/AnySource.java @@ -0,0 +1,40 @@ +/* + * 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.annotation.proto; + +import static java.lang.annotation.ElementType.TYPE_USE; +import static java.lang.annotation.RetentionPolicy.RUNTIME; + +import com.code_intelligence.jazzer.mutation.annotation.AppliesTo; +import com.google.protobuf.Message; +import com.google.protobuf.Message.Builder; +import java.lang.annotation.Retention; +import java.lang.annotation.Target; + +/** + * Controls the mutations of {@link com.google.protobuf.Any} fields in messages of the annotated + * type as well as its recursive message fields. + */ +@Target(TYPE_USE) +@Retention(RUNTIME) +@AppliesTo(subClassesOf = {Message.class, Builder.class}) +public @interface AnySource { + /** + * A non-empty list of {@link Message}s to use for {@link com.google.protobuf.Any} fields. + */ + Class<? extends Message>[] value(); +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/BUILD.bazel new file mode 100644 index 00000000..8ef6863b --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/BUILD.bazel @@ -0,0 +1,21 @@ +java_library( + name = "proto", + srcs = glob(["*.java"]), + visibility = ["//visibility:public"], + deps = [ + ":protobuf_runtime_compile_only", + "//src/main/java/com/code_intelligence/jazzer/mutation/annotation", + ], +) + +java_library( + name = "protobuf_runtime_compile_only", + # The proto mutator factory detects the presence of Protobuf at runtime and disables itself if + # it isn't found. Without something else bringing in the Protobuf runtime, there is no point in + # supporting proto mutations. + neverlink = True, + visibility = ["//src/main/java/com/code_intelligence/jazzer/mutation/mutator/proto:__pkg__"], + exports = [ + "@com_google_protobuf_protobuf_java//jar", + ], +) diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/WithDefaultInstance.java b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/WithDefaultInstance.java new file mode 100644 index 00000000..e26d73a2 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/annotation/proto/WithDefaultInstance.java @@ -0,0 +1,43 @@ +/* + * 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.annotation.proto; + +import static java.lang.annotation.ElementType.TYPE_USE; +import static java.lang.annotation.RetentionPolicy.RUNTIME; + +import com.code_intelligence.jazzer.mutation.annotation.AppliesTo; +import com.google.protobuf.DynamicMessage; +import com.google.protobuf.Message; +import java.lang.annotation.Retention; +import java.lang.annotation.Target; + +/** + * Provides a default instance to use as the base for mutations of the annotated {@link Message} or + * {@link DynamicMessage.Builder}. + */ +@Target(TYPE_USE) +@Retention(RUNTIME) +@AppliesTo(subClassesOf = {Message.class, Message.Builder.class}) +public @interface WithDefaultInstance { + /** + * The fully qualified name of a static method (e.g. + * {@code com.example.MyClass#getDefaultInstance}) with return type assignable to + * {@link com.google.protobuf.Message}, which returns a default instance that mutations should be + * based on. + */ + String value(); +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/api/BUILD.bazel new file mode 100644 index 00000000..cd5fe60e --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/BUILD.bazel @@ -0,0 +1,9 @@ +java_library( + name = "api", + srcs = glob(["*.java"]), + visibility = ["//visibility:public"], + deps = [ + "//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/api/ChainedMutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/ChainedMutatorFactory.java new file mode 100644 index 00000000..bf27e81b --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/ChainedMutatorFactory.java @@ -0,0 +1,48 @@ +/* + * 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.api; + +import static com.code_intelligence.jazzer.mutation.support.StreamSupport.findFirstPresent; +import static java.util.Arrays.asList; +import static java.util.Collections.unmodifiableList; + +import com.google.errorprone.annotations.CheckReturnValue; +import java.lang.reflect.AnnotatedType; +import java.util.List; +import java.util.Optional; + +/** + * A {@link MutatorFactory} that delegates to the given factories in order. + */ +public final class ChainedMutatorFactory extends MutatorFactory { + private final List<MutatorFactory> factories; + + /** + * Creates a {@link MutatorFactory} that delegates to the given factories in order. + * + * @param factories a possibly empty collection of factories + */ + public ChainedMutatorFactory(MutatorFactory... factories) { + this.factories = unmodifiableList(asList(factories)); + } + + @Override + @CheckReturnValue + public Optional<SerializingMutator<?>> tryCreate(AnnotatedType type, MutatorFactory parent) { + return findFirstPresent(factories.stream().map(factory -> factory.tryCreate(type, parent))); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/Debuggable.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/Debuggable.java new file mode 100644 index 00000000..df6f8288 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/Debuggable.java @@ -0,0 +1,46 @@ +/* + * 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.api; + +import static java.util.Collections.newSetFromMap; +import static java.util.Objects.requireNonNull; + +import java.util.IdentityHashMap; +import java.util.Set; +import java.util.function.Predicate; + +public interface Debuggable { + /** + * Returns a string representation of the object that is meant to be used to make assertions about + * its structure in tests. + * + * @param isInCycle evaluates to {@code true} if a cycle has been detected during recursive calls + * of this function. Must be called at most once with {@code this} as the single + * argument. Implementing classes that know that their current instance can never + * be contained in recursive substructures need not call this method. + */ + String toDebugString(Predicate<Debuggable> isInCycle); + + /** + * Returns a string representation of the given {@link Debuggable} that is meant to be used to + * make assertions about its structure in tests. + */ + static String getDebugString(Debuggable debuggable) { + Set<Debuggable> seen = newSetFromMap(new IdentityHashMap<>()); + return debuggable.toDebugString(child -> !seen.add(requireNonNull(child))); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/Detacher.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/Detacher.java new file mode 100644 index 00000000..d927e505 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/Detacher.java @@ -0,0 +1,44 @@ +/* + * 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.api; + +import com.google.errorprone.annotations.CheckReturnValue; + +/** + * Knows how to clone a {@code T} such that it shares no mutable state with the original. + */ +@FunctionalInterface +public interface Detacher<T> { + /** + * Returns an equal instance that shares no mutable state with {@code value}. + * + * <p>Implementations + * <ul> + * <li>MUST return an instance that {@link Object#equals(Object)} the argument; + * <li>MUST return an instance that cannot be used to mutate the state of the argument through + * its API (ignoring uses of {@link sun.misc.Unsafe}); + * <li>MUST return an instance that is not affected by any changes to the original value made + * by any mutator;</li> + * <li>MUST be accepted by mutator methods just like the original value;</li> + * <li>MAY return the argument itself if it is deeply immutable. + * </ul> + * + * @param value the instance to detach + * @return an equal instance that shares no mutable state with {@code value} + */ + @CheckReturnValue T detach(T value); +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/InPlaceMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/InPlaceMutator.java new file mode 100644 index 00000000..cf1b243d --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/InPlaceMutator.java @@ -0,0 +1,74 @@ +/* + * 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.api; + +/** + * Knows how to initialize and mutate (parts of) an existing object of type {@code T} in place and + * how to incorporate (cross over) parts of another object of the same type. + * + * <p>Certain types, such as immutable and primitive types, can not be mutated in place. For + * example, {@link java.util.List} can be mutated in place whereas {@link String} and {@code int} + * can't. In such cases, use {@link ValueMutator} instead. + * + * <p>Implementations + * <ul> + * <li>MAY weakly associate mutable state with the identity (not equality class) of objects they + * have been passed as arguments or returned from initialization functions; + * <li>MAY assume that they are only passed arguments that they have initialized or mutated;</li> + * <li>SHOULD use {@link com.code_intelligence.jazzer.mutation.support.WeakIdentityHashMap} for + * this purpose; + * <li>MUST otherwise be deeply immutable; + * <li>SHOULD override {@link Object#toString()} to return {@code + * Debuggable.getDebugString(this)}. + * </ul> + * + * @param <T> the reference type this mutator operates on + */ +public interface InPlaceMutator<T> extends Debuggable { + /** + * Implementations + * <ul> + * <li>MUST accept any mutable instance of {@code T}, not just those it creates itself. + * <li>SHOULD, when called repeatedly, initialize the object in ways that are likely to be + * distinct. + * </ul> + */ + void initInPlace(T reference, PseudoRandom prng); + + /** + * Implementations + * <ul> + * <li>MUST ensure that {@code reference} does not {@link Object#equals(Object)} the state it + * had prior to the call (if possible); + * <li>MUST accept any mutable instance of {@code T}, not just those it creates itself. + * <li>SHOULD, when called repeatedly, be able to eventually reach any valid state of the part + * of {@code T} governed by this mutator; + * </ul> + */ + void mutateInPlace(T reference, PseudoRandom prng); + + /** + * Implementations + * <ul> + * <li>MUST ensure that {@code reference} does not {@link Object#equals(Object)} the state it + * had prior to the call (if possible); + * <li>MUST accept any mutable instance of {@code T}, not just those it creates itself. + * <li>MUST NOT mutate {@code otherReference}</li> + * </ul> + */ + void crossOverInPlace(T reference, T otherReference, PseudoRandom prng); +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/MutatorFactory.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/MutatorFactory.java new file mode 100644 index 00000000..64771285 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/MutatorFactory.java @@ -0,0 +1,80 @@ +/* + * 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.api; + +import static com.code_intelligence.jazzer.mutation.support.Preconditions.require; +import static com.code_intelligence.jazzer.mutation.support.TypeSupport.asAnnotatedType; +import static java.lang.String.format; + +import com.google.errorprone.annotations.CheckReturnValue; +import java.lang.reflect.AnnotatedType; +import java.util.Optional; + +/** + * Instances of this class are not required to be thread safe, but are generally lightweight and can + * thus be created as needed. + */ +public abstract class MutatorFactory { + public final boolean canMutate(AnnotatedType type) { + return tryCreate(type).isPresent(); + } + + public final <T> SerializingMutator<T> createOrThrow(Class<T> clazz) { + return (SerializingMutator<T>) createOrThrow(asAnnotatedType(clazz)); + } + + public final SerializingMutator<?> createOrThrow(AnnotatedType type) { + Optional<SerializingMutator<?>> maybeMutator = tryCreate(type); + require(maybeMutator.isPresent(), "Failed to create mutator for " + type); + return maybeMutator.get(); + } + + public final SerializingInPlaceMutator<?> createInPlaceOrThrow(AnnotatedType type) { + Optional<SerializingInPlaceMutator<?>> maybeMutator = tryCreateInPlace(type); + require(maybeMutator.isPresent(), "Failed to create mutator for " + type); + return maybeMutator.get(); + } + + /** + * Tries to create a mutator for {@code type} and, if successful, asserts that it is an instance + * of {@link SerializingInPlaceMutator}. + */ + public final Optional<SerializingInPlaceMutator<?>> tryCreateInPlace(AnnotatedType type) { + return tryCreate(type).map(mutator -> { + require(mutator instanceof InPlaceMutator<?>, + format("Mutator for %s is not in-place: %s", type, mutator.getClass())); + return (SerializingInPlaceMutator<?>) mutator; + }); + } + + @CheckReturnValue + public final Optional<SerializingMutator<?>> tryCreate(AnnotatedType type) { + return tryCreate(type, this); + } + + /** + * Attempt to create a {@link SerializingMutator} for the given type. + * + * @param type the type to mutate + * @param factory the factory to use when creating submutators + * @return a {@link SerializingMutator} for the given {@code type}, or {@link Optional#empty()} + * if this factory can't create such mutators + */ + @CheckReturnValue + public abstract Optional<SerializingMutator<?>> tryCreate( + AnnotatedType type, MutatorFactory factory); +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/PseudoRandom.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/PseudoRandom.java new file mode 100644 index 00000000..3755a7b1 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/PseudoRandom.java @@ -0,0 +1,136 @@ +/* + * 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.api; + +import com.google.errorprone.annotations.DoNotMock; +import java.util.List; +import java.util.function.Supplier; + +@DoNotMock("Use TestSupport#mockPseudoRandom instead") +public interface PseudoRandom { + /** + * @return a uniformly random {@code boolean} + */ + boolean choice(); + + /** + * @return a {@code boolean} that is {@code true} with probability {@code 1/inverseFrequencyTrue} + */ + boolean trueInOneOutOf(int inverseFrequencyTrue); + + /** + * @throws IllegalArgumentException if {@code array.length == 0} + * @return an element from the given array at uniformly random index + */ + <T> T pickIn(T[] array); + + /** + * @throws IllegalArgumentException if {@code array.length == 0} + * @return an element from the given List at uniformly random index + */ + <T> T pickIn(List<T> array); + + /** + * @throws IllegalArgumentException if {@code array.length == 0} + * @return a uniformly random index valid for the given array + */ + <T> int indexIn(T[] array); + + /** + * @throws IllegalArgumentException if {@code list.size() == 0} + * @return a uniformly random index valid for the given list + */ + <T> int indexIn(List<T> list); + + /** + * Prefer {@link #indexIn(Object[])} and {@link #indexIn(List)}. + * + * @throws IllegalArgumentException if {@code range < 1} + * @return a uniformly random index in the range {@code [0, range-1]} + */ + int indexIn(int range); + + /** + * @throws IllegalArgumentException if {@code array.length < 2} + * @return a uniformly random index valid for the given array and different from + * {@code currentIndex} + */ + <T> int otherIndexIn(T[] array, int currentIndex); + + /** + * @throws IllegalArgumentException if {@code length < 2} + * @return a uniformly random {@code int} in the closed range {@code [0, length)} that is + * different from {@code currentIndex} + */ + int otherIndexIn(int range, int currentIndex); + + /** + * @return a uniformly random {@code int} in the closed range + * {@code [lowerInclusive, upperInclusive]}. + */ + int closedRange(int lowerInclusive, int upperInclusive); + + /** + * @return a uniformly random {@code long} in the closed range + * {@code [lowerInclusive, upperInclusive]}. + */ + long closedRange(long lowerInclusive, long upperInclusive); + + /** + * @return a uniformly random {@code float} in the closed range + * {@code [lowerInclusive, upperInclusive]}. + */ + float closedRange(float lowerInclusive, float upperInclusive); + + /** + * @return a uniformly random {@code double} in the closed range + * {@code [lowerInclusive, upperInclusive]}. + */ + double closedRange(double lowerInclusive, double upperInclusive); + + /** + * @return a random value in the closed range [0, upperInclusive] that is heavily biased towards + * being small + */ + int closedRangeBiasedTowardsSmall(int upperInclusive); + + /** + * @return a random value in the closed range [lowerInclusive, upperInclusive] that is heavily + * biased towards being small + */ + int closedRangeBiasedTowardsSmall(int lowerInclusive, int upperInclusive); + + /** + * Fills the given array with random bytes. + */ + void bytes(byte[] bytes); + + /** + * Use the given supplier to produce a value with probability {@code 1/inverseSupplierFrequency}, + * otherwise randomly return one of the given values. + * + * @return value produced by the supplier or one of the given values + */ + <T> T pickValue(T value, T otherValue, Supplier<T> supplier, int inverseSupplierFrequency); + + /** + * Returns a pseudorandom {@code long} value. + * + * @return a pseudorandom {@code long} value + */ + long nextLong(); +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/Serializer.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/Serializer.java new file mode 100644 index 00000000..b948b177 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/Serializer.java @@ -0,0 +1,116 @@ +/* + * 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.api; + +import static com.code_intelligence.jazzer.mutation.support.InputStreamSupport.extendWithZeros; + +import com.google.errorprone.annotations.CheckReturnValue; +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; + +/** + * Serializes and deserializes values of type {@code T>} to and from (in-memory or on disk) corpus + * entries. + * + * <p>Binary representations must by default be self-delimiting. For variable-length types, the + * {@link #readExclusive(InputStream)} and {@link #writeExclusive(Object, OutputStream)} methods can + * optionally be overriden to implement more compact representations that align with existing binary + * corpus entries. For example, a {@code Serializer<byte[]>} could implement these optional methods + * to read and write the raw bytes without preceding length information whenever it is used in an + * already delimited context. + */ +public interface Serializer<T> extends Detacher<T> { + /** + * Reads a {@code T} from an endless stream that is eventually 0. + * + * <p>Implementations + * <ul> + * <li>MUST not attempt to consume the entire stream; + * <li>MUST return a valid {@code T} and not throw for any (even garbage) stream; + * <li>SHOULD short-circuit the creation of nested structures upon reading null bytes. + * </ul> + * + * @param in an endless stream that eventually only reads null bytes + * @return a {@code T} constructed from the bytes read + * @throws IOException declared, but must not be thrown by implementations unless methods called + * on {@code in} do + */ + @CheckReturnValue T read(DataInputStream in) throws IOException; + + /** + * Writes a {@code T} to a stream in such a way that an equal object can be recovered from the + * written bytes via {@link #read(DataInputStream)}. + * + * <p>Since {@link #read(DataInputStream)} is called with an endless stream, the binary + * representation MUST be self-delimiting. For example, when writing out a list, first write its + * length. + * + * @param value the value to write + * @param out the stream to write to + * @throws IOException declared, but must not be thrown by implementations unless methods called + * on {@code out} do + */ + void write(T value, DataOutputStream out) throws IOException; + + /** + * Reads a {@code T} from a finite stream, potentially using a simpler representation than that + * read by {@link #read(DataInputStream)}. + * + * <p>The default implementations call extends the stream with null bytes and then calls + * {@link #read(DataInputStream)}. + * + * <p>Implementations + * <ul> + * <li>MUST return a valid {@code T} and not throw for any (even garbage) stream; + * <li>SHOULD short-circuit the creation of nested structures upon reading null bytes; + * <li>SHOULD naturally consume the entire stream. + * </ul> + * + * @param in a finite stream + * @return a {@code T} constructed from the bytes read + * @throws IOException declared, but must not be thrown by implementations unless methods called + * on {@code in} do + */ + @CheckReturnValue + default T readExclusive(InputStream in) throws IOException { + return read(new DataInputStream(extendWithZeros(in))); + } + + /** + * Writes a {@code T} to a stream in such a way that an equal object can be recovered from the + * written bytes via {@link #readExclusive(InputStream)}. + * + * <p>The default implementations calls through to {@link #read(DataInputStream)} and should only + * be overriden if {@link #readExclusive(InputStream)} is. + * + * <p>As opposed to {@link #read(DataInputStream)}, {@link #readExclusive(InputStream)} is called + * with a finite stream. The binary representation of a {@code T} value thus does not have to be + * self-delimiting, which can allow for simpler representations. For example, a {@code byte[]} can + * be written to the stream without prepending its length. + * + * @param value the value to write + * @param out the stream to write to + * @throws IOException declared, but must not be thrown by implementations unless methods called + * on {@code out} do + */ + default void writeExclusive(T value, OutputStream out) throws IOException { + write(value, new DataOutputStream(out)); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingInPlaceMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingInPlaceMutator.java new file mode 100644 index 00000000..b7bc4d4c --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingInPlaceMutator.java @@ -0,0 +1,76 @@ +/* + * 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.api; + +import static com.code_intelligence.jazzer.mutation.support.ExceptionSupport.asUnchecked; + +import com.google.errorprone.annotations.ForOverride; +import java.io.ByteArrayInputStream; +import java.io.IOException; +import java.io.InputStream; + +/** + * Combines an {@link InPlaceMutator} with a {@link Serializer} for objects of type {@code T}. + * + * <p>If {@code T} can't be mutated in place, implement {@link SerializingMutator} instead. + * + * <p>Implementing classes SHOULD be declared final. + */ +public abstract class SerializingInPlaceMutator<T> + extends SerializingMutator<T> implements InPlaceMutator<T> { + // ByteArrayInputStream#close is documented as being a no-op, so it is safe to reuse an instance + // here. + // TODO: Introduce a dedicated empty InputStream implementation. + private static final InputStream emptyInputStream = new ByteArrayInputStream(new byte[0]); + + /** + * Constructs a default instance of {@code T}. + * + * <p>The returned value is immediately passed to {@link #initInPlace(Object, PseudoRandom)}. + * + * <p>Implementing classes SHOULD provide a more efficient implementation. + * + * @return a default instance of {@code T} + */ + @ForOverride + protected T makeDefaultInstance() { + try { + return readExclusive(emptyInputStream); + } catch (IOException e) { + throw asUnchecked(e); + } + } + + @Override + public final T init(PseudoRandom prng) { + T value = makeDefaultInstance(); + initInPlace(value, prng); + return value; + } + + @Override + public final T mutate(T value, PseudoRandom prng) { + mutateInPlace(value, prng); + return value; + } + + @Override + public final T crossOver(T value, T otherValue, PseudoRandom prng) { + crossOverInPlace(value, otherValue, prng); + return value; + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingMutator.java new file mode 100644 index 00000000..58b2a49b --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/SerializingMutator.java @@ -0,0 +1,35 @@ +/* + * 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.api; + +import com.google.errorprone.annotations.DoNotMock; + +/** + * Combines a {@link ValueMutator} with a {@link Serializer} for objects of type {@code T}. + * + * <p>Implementing classes SHOULD be declared final. + * + * <p>This is the default fully-featured mutator type. If {@code T} can be mutated fully in place, + * consider implementing the more versatile {@link SerializingInPlaceMutator} instead. + */ +@DoNotMock("Use TestSupport#mockMutator instead") +public abstract class SerializingMutator<T> implements Serializer<T>, ValueMutator<T> { + @Override + public final String toString() { + return Debuggable.getDebugString(this); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/api/ValueMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/api/ValueMutator.java new file mode 100644 index 00000000..aa2b551e --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/api/ValueMutator.java @@ -0,0 +1,75 @@ +/* + * 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.api; + +import com.google.errorprone.annotations.CheckReturnValue; + +/** + * Knows how to initialize and mutate objects of type {@code T} and how to incorporate + * (cross over) parts of another object of the same type. + * + * <p>Certain types can be mutated fully in place. In such cases, prefer implementing the more + * versatile {@link InPlaceMutator} instead. + * + * <p>Implementations + * <ul> + * <li>MAY weakly associate mutable state with the identity (not equality class) of objects they + * have been passed as arguments or returned from initialization functions; + * <li>MAY assume that they are only passed arguments that they have initialized or mutated;</li> + * <li>SHOULD use {@link com.code_intelligence.jazzer.mutation.support.WeakIdentityHashMap} for + * this purpose; + * <li>MUST otherwise be deeply immutable; + * <li>SHOULD override {@link Object#toString()} to return {@code + * Debuggable.getDebugString(this)}. + * </ul> + * + * @param <T> the type this mutator operates on + */ +public interface ValueMutator<T> extends Debuggable { + /** + * Implementations + * <ul> + * <li>SHOULD, when called repeatedly, return a low amount of duplicates. + * </ul> + * + * @return an instance of {@code T} + */ + @CheckReturnValue T init(PseudoRandom prng); + + /** + * Implementations + * <ul> + * <li>MUST return a value that does not {@link Object#equals(Object)} the argument (if + * possible); + * <li>SHOULD, when called repeatedly, be able to eventually return any valid value of + * type {@code T}; + * <li>MAY mutate the argument. + * </ul> + */ + @CheckReturnValue T mutate(T value, PseudoRandom prng); + + /** + * Implementations + * <ul> + * <li>MUST return a value that does not {@link Object#equals(Object)} the arguments (if + * possible); + * <li>MAY mutate {@code value}. + * <li>MUST NOT mutate {@code otherValue}. + * </ul> + */ + @CheckReturnValue T crossOver(T value, T otherValue, PseudoRandom prng); +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/combinator/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/BUILD.bazel new file mode 100644 index 00000000..639a3d09 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/BUILD.bazel @@ -0,0 +1,11 @@ +java_library( + name = "combinator", + srcs = glob(["*.java"]), + visibility = ["//visibility:public"], + deps = [ + "//src/main/java/com/code_intelligence/jazzer/mutation/api", + "//src/main/java/com/code_intelligence/jazzer/mutation/support", + "@com_github_jhalterman_typetools//:typetools", + "@com_google_errorprone_error_prone_type_annotations//jar", + ], +) diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/combinator/MutatorCombinators.java b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/MutatorCombinators.java new file mode 100644 index 00000000..18fa0288 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/MutatorCombinators.java @@ -0,0 +1,516 @@ +/* + * 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.combinator; + +import static com.code_intelligence.jazzer.mutation.support.Preconditions.require; +import static com.code_intelligence.jazzer.mutation.support.Preconditions.requireNonNullElements; +import static java.util.Arrays.stream; +import static java.util.Objects.requireNonNull; +import static java.util.stream.Collectors.joining; + +import com.code_intelligence.jazzer.mutation.api.Debuggable; +import com.code_intelligence.jazzer.mutation.api.InPlaceMutator; +import com.code_intelligence.jazzer.mutation.api.PseudoRandom; +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.google.errorprone.annotations.ImmutableTypeParameter; +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; +import java.util.Arrays; +import java.util.function.BiConsumer; +import java.util.function.Consumer; +import java.util.function.Function; +import java.util.function.Predicate; +import java.util.function.Supplier; +import java.util.function.ToIntFunction; +import net.jodah.typetools.TypeResolver; + +public final class MutatorCombinators { + // Inverse frequency in which value mutator should be used in cross over. + private final static int INVERSE_PICK_VALUE_SUPPLIER_FREQUENCY = 100; + + private MutatorCombinators() {} + + public static <T, R> InPlaceMutator<T> mutateProperty( + Function<T, R> getter, SerializingMutator<R> mutator, BiConsumer<T, R> setter) { + requireNonNull(getter); + requireNonNull(mutator); + requireNonNull(setter); + return new InPlaceMutator<T>() { + @Override + public void initInPlace(T reference, PseudoRandom prng) { + setter.accept(reference, mutator.init(prng)); + } + + @Override + public void mutateInPlace(T reference, PseudoRandom prng) { + setter.accept(reference, mutator.mutate(getter.apply(reference), prng)); + } + + @Override + public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) { + // Most of the time cross over of properties should use one of the + // given values and only seldom use the property type specific cross + // over function. Other mutator combinators delegate to this one and + // don't cross over values themselves. + R referenceValue = getter.apply(reference); + R otherReferenceValue = getter.apply(otherReference); + R crossedOver = prng.pickValue(referenceValue, otherReferenceValue, + () + -> mutator.crossOver(referenceValue, otherReferenceValue, prng), + INVERSE_PICK_VALUE_SUPPLIER_FREQUENCY); + if (crossedOver == otherReferenceValue) { + // If otherReference was picked, it needs to be detached as mutating + // it is prohibited in cross over. + crossedOver = mutator.detach(crossedOver); + } + setter.accept(reference, crossedOver); + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + Class<?> owningType = + TypeResolver.resolveRawArguments(Function.class, getter.getClass())[0]; + return owningType.getSimpleName() + "." + mutator.toDebugString(isInCycle); + } + + @Override + public String toString() { + return Debuggable.getDebugString(this); + } + }; + } + + public static <T, R> InPlaceMutator<T> mutateViaView( + Function<T, R> map, InPlaceMutator<R> mutator) { + requireNonNull(map); + requireNonNull(mutator); + return new InPlaceMutator<T>() { + @Override + public void initInPlace(T reference, PseudoRandom prng) { + mutator.initInPlace(map.apply(reference), prng); + } + + @Override + public void mutateInPlace(T reference, PseudoRandom prng) { + mutator.mutateInPlace(map.apply(reference), prng); + } + + @Override + public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) { + mutator.crossOverInPlace(map.apply(reference), map.apply(otherReference), prng); + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + Class<?> owningType = TypeResolver.resolveRawArguments(Function.class, map.getClass())[0]; + return owningType.getSimpleName() + " via " + mutator.toDebugString(isInCycle); + } + + @Override + public String toString() { + return Debuggable.getDebugString(this); + } + }; + } + + /** + * Combines multiple in-place mutators for different parts of a {@code T} into one that picks one + * at random whenever it mutates. + * + * <p>Calling this method with no arguments returns a no-op mutator that may decrease fuzzing + * efficiency. + */ + @SafeVarargs + public static <T> InPlaceMutator<T> combine(InPlaceMutator<T>... partialMutators) { + requireNonNullElements(partialMutators); + if (partialMutators.length == 0) { + return new InPlaceMutator<T>() { + @Override + public void initInPlace(T reference, PseudoRandom prng) {} + + @Override + public void mutateInPlace(T reference, PseudoRandom prng) {} + + @Override + public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) {} + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return "{<empty>}"; + } + + @Override + public String toString() { + return Debuggable.getDebugString(this); + } + }; + } + + final InPlaceMutator<T>[] mutators = Arrays.copyOf(partialMutators, partialMutators.length); + return new InPlaceMutator<T>() { + @Override + public void initInPlace(T reference, PseudoRandom prng) { + for (InPlaceMutator<T> mutator : mutators) { + mutator.initInPlace(reference, prng); + } + } + + @Override + public void mutateInPlace(T reference, PseudoRandom prng) { + mutators[prng.indexIn(mutators)].mutateInPlace(reference, prng); + } + + @Override + public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) { + for (InPlaceMutator<T> mutator : mutators) { + mutator.crossOverInPlace(reference, otherReference, prng); + } + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return stream(mutators) + .map(mutator -> mutator.toDebugString(isInCycle)) + .collect(joining(", ", "{", "}")); + } + + @Override + public String toString() { + return Debuggable.getDebugString(this); + } + }; + } + + public static <T, R> SerializingMutator<R> mutateThenMap( + SerializingMutator<T> mutator, Function<T, R> map, Function<R, T> inverse) { + return new PostComposedMutator<T, R>(mutator, map, inverse) {}; + } + + public static <T, R> SerializingMutator<R> mutateThenMap(SerializingMutator<T> mutator, + Function<T, R> map, Function<R, T> inverse, Function<Predicate<Debuggable>, String> debug) { + return new PostComposedMutator<T, R>(mutator, map, inverse) { + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return debug.apply(isInCycle); + } + }; + } + + public static <T, @ImmutableTypeParameter R> SerializingMutator<R> mutateThenMapToImmutable( + SerializingMutator<T> mutator, Function<T, R> map, Function<R, T> inverse) { + return new PostComposedMutator<T, R>(mutator, map, inverse) { + @Override + public R detach(R value) { + return value; + } + }; + } + + public static <T, @ImmutableTypeParameter R> SerializingMutator<R> mutateThenMapToImmutable( + SerializingMutator<T> mutator, Function<T, R> map, Function<R, T> inverse, + Function<Predicate<Debuggable>, String> debug) { + return new PostComposedMutator<T, R>(mutator, map, inverse) { + @Override + public R detach(R value) { + return value; + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return debug.apply(isInCycle); + } + }; + } + + public static SerializingMutator<Integer> mutateIndices(int length) { + require(length > 1, "There should be at least two indices to choose from"); + return new SerializingMutator<Integer>() { + @Override + public Integer read(DataInputStream in) throws IOException { + return Math.floorMod(in.readInt(), length); + } + + @Override + public void write(Integer value, DataOutputStream out) throws IOException { + out.writeInt(value); + } + + @Override + public Integer detach(Integer value) { + return value; + } + + @Override + public Integer init(PseudoRandom prng) { + return prng.closedRange(0, length - 1); + } + + @Override + public Integer mutate(Integer value, PseudoRandom prng) { + return prng.otherIndexIn(length, value); + } + + @Override + public Integer crossOver(Integer value, Integer otherValue, PseudoRandom prng) { + return prng.choice() ? value : otherValue; + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return "mutateIndices(" + length + ")"; + } + }; + } + + /** + * Combines multiple mutators for potentially different types into one that mutates an + * {@code Object[]} containing one instance per mutator. + */ + @SuppressWarnings("rawtypes") + public static ProductMutator mutateProduct(SerializingMutator... mutators) { + return new ProductMutator(mutators); + } + + /** + * Mutates a sum type (e.g. a Protobuf oneof) in place, preferring to mutate the current state + * but occasionally switching to a different state. + * @param getState a function that returns the current state of the sum type as an index into + * {@code perStateMutators}, or -1 if the state is indeterminate. + * @param perStateMutators the mutators for each state + * @return a mutator that mutates the sum type in place + */ + @SafeVarargs + public static <T> InPlaceMutator<T> mutateSumInPlace( + ToIntFunction<T> getState, InPlaceMutator<T>... perStateMutators) { + final InPlaceMutator<T>[] mutators = Arrays.copyOf(perStateMutators, perStateMutators.length); + return new InPlaceMutator<T>() { + @Override + public void initInPlace(T reference, PseudoRandom prng) { + mutators[prng.indexIn(mutators)].initInPlace(reference, prng); + } + + @Override + public void mutateInPlace(T reference, PseudoRandom prng) { + int currentState = getState.applyAsInt(reference); + if (currentState == -1) { + // The value is in an indeterminate state, initialize it. + initInPlace(reference, prng); + } else if (prng.trueInOneOutOf(100) && mutators.length > 1) { + // Initialize to a different state. + mutators[prng.otherIndexIn(mutators, currentState)].initInPlace(reference, prng); + } else { + // Mutate within the current state. + mutators[currentState].mutateInPlace(reference, prng); + } + } + + @Override + public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) { + // Try to cross over in current state and leave state changes to the mutate step. + int currentState = getState.applyAsInt(reference); + int otherState = getState.applyAsInt(otherReference); + if (currentState == -1) { + // If reference is not initialized to a concrete state yet, try to do so in + // the state of other reference, as that's at least some progress. + if (otherState == -1) { + // If both states are indeterminate, cross over can not be performed. + return; + } + mutators[otherState].initInPlace(reference, prng); + } else if (currentState == otherState) { + mutators[currentState].crossOverInPlace(reference, otherReference, prng); + } + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return stream(mutators) + .map(mutator -> mutator.toDebugString(isInCycle)) + .collect(joining(" | ")); + } + }; + } + + /** + * @return a mutator that behaves identically to the provided one except that its {@link + * InPlaceMutator#initInPlace(Object, PseudoRandom)} is a no-op + */ + public static <T> InPlaceMutator<T> withoutInit(InPlaceMutator<T> mutator) { + return new InPlaceMutator<T>() { + @Override + public void initInPlace(T reference, PseudoRandom prng) { + // Intentionally left empty. + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return "WithoutInit(" + mutator.toDebugString(isInCycle) + ")"; + } + + @Override + public void mutateInPlace(T reference, PseudoRandom prng) { + mutator.mutateInPlace(reference, prng); + } + + @Override + public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) { + mutator.crossOverInPlace(reference, otherReference, prng); + } + }; + } + + /** + * Constructs a mutator that always returns the provided fixed value. + * + * <p>Note: This mutator explicitly breaks the contract of the init and mutate methods. Use + * sparingly as it may harm the overall effectivity of the mutator. + */ + public static <@ImmutableTypeParameter T> SerializingMutator<T> fixedValue(T value) { + return new SerializingMutator<T>() { + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return "FixedValue(" + value + ")"; + } + + @Override + public T read(DataInputStream in) { + return value; + } + + @Override + public void write(T value, DataOutputStream out) {} + + @Override + public T detach(T value) { + return value; + } + + @Override + public T init(PseudoRandom prng) { + return value; + } + + @Override + public T mutate(T value, PseudoRandom prng) { + return value; + } + + @Override + public T crossOver(T value, T otherValue, PseudoRandom prng) { + return value; + } + }; + } + + /** + * Assembles the parameters into a full implementation of {@link SerializingInPlaceMutator<T>}: + * + * @param registerSelf a callback that will receive the uninitialized mutator instance + * before {@code lazyMutator} is invoked. For simple cases this can + * just do nothing, but it is needed to implement mutators for + * structures that are self-referential (e.g. Protobuf message A having + * a field of type A). + * @param makeDefaultInstance constructs a mutable default instance of {@code T} + * @param serializer implementation of the {@link Serializer<T>} part + * @param lazyMutator supplies the implementation of the {@link InPlaceMutator<T>} part. + * This is guaranteed to be invoked exactly once and only after + * {@code registerSelf}. + */ + public static <T> SerializingInPlaceMutator<T> assemble( + Consumer<SerializingInPlaceMutator<T>> registerSelf, Supplier<T> makeDefaultInstance, + Serializer<T> serializer, Supplier<InPlaceMutator<T>> lazyMutator) { + return new DelegatingSerializingInPlaceMutator<>( + registerSelf, makeDefaultInstance, serializer, lazyMutator); + } + + private static class DelegatingSerializingInPlaceMutator<T> extends SerializingInPlaceMutator<T> { + private final Supplier<T> makeDefaultInstance; + private final Serializer<T> serializer; + private final InPlaceMutator<T> mutator; + + private DelegatingSerializingInPlaceMutator(Consumer<SerializingInPlaceMutator<T>> registerSelf, + Supplier<T> makeDefaultInstance, Serializer<T> serializer, + Supplier<InPlaceMutator<T>> lazyMutator) { + requireNonNull(makeDefaultInstance); + requireNonNull(serializer); + + registerSelf.accept(this); + this.makeDefaultInstance = makeDefaultInstance; + this.serializer = serializer; + this.mutator = lazyMutator.get(); + } + + @Override + public void initInPlace(T reference, PseudoRandom prng) { + mutator.initInPlace(reference, prng); + } + + @Override + public void mutateInPlace(T reference, PseudoRandom prng) { + mutator.mutateInPlace(reference, prng); + } + + @Override + public void crossOverInPlace(T reference, T otherReference, PseudoRandom prng) { + mutator.crossOverInPlace(reference, otherReference, prng); + } + + @Override + protected T makeDefaultInstance() { + return makeDefaultInstance.get(); + } + + @Override + public T read(DataInputStream in) throws IOException { + return serializer.read(in); + } + + @Override + public void write(T value, DataOutputStream out) throws IOException { + serializer.write(value, out); + } + + @Override + public T readExclusive(InputStream in) throws IOException { + return serializer.readExclusive(in); + } + + @Override + public void writeExclusive(T value, OutputStream out) throws IOException { + serializer.writeExclusive(value, out); + } + + @Override + public T detach(T value) { + return serializer.detach(value); + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + if (isInCycle.test(this)) { + return "(cycle)"; + } else { + return mutator.toDebugString(isInCycle); + } + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/combinator/PostComposedMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/PostComposedMutator.java new file mode 100644 index 00000000..ae8f97cc --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/PostComposedMutator.java @@ -0,0 +1,89 @@ +/* + * 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.combinator; + +import static java.util.Objects.requireNonNull; + +import com.code_intelligence.jazzer.mutation.api.Debuggable; +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.io.InputStream; +import java.io.OutputStream; +import java.util.function.Function; +import java.util.function.Predicate; +import net.jodah.typetools.TypeResolver; + +abstract class PostComposedMutator<T, R> extends SerializingMutator<R> { + private final SerializingMutator<T> mutator; + private final Function<T, R> map; + private final Function<R, T> inverse; + + PostComposedMutator(SerializingMutator<T> mutator, Function<T, R> map, Function<R, T> inverse) { + this.mutator = requireNonNull(mutator); + this.map = requireNonNull(map); + this.inverse = requireNonNull(inverse); + } + + @Override + public R detach(R value) { + return map.apply(mutator.detach(inverse.apply(value))); + } + + @Override + public final R init(PseudoRandom prng) { + return map.apply(mutator.init(prng)); + } + + @Override + public final R mutate(R value, PseudoRandom prng) { + return map.apply(mutator.mutate(inverse.apply(value), prng)); + } + + @Override + public R crossOver(R value, R otherValue, PseudoRandom prng) { + return map.apply(mutator.crossOver(inverse.apply(value), inverse.apply(otherValue), prng)); + } + + @Override + public final R read(DataInputStream in) throws IOException { + return map.apply(mutator.read(in)); + } + + @Override + public final void write(R value, DataOutputStream out) throws IOException { + mutator.write(inverse.apply(value), out); + } + + @Override + public final R readExclusive(InputStream in) throws IOException { + return map.apply(mutator.readExclusive(in)); + } + + @Override + public final void writeExclusive(R value, OutputStream out) throws IOException { + mutator.writeExclusive(inverse.apply(value), out); + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + Class<?> returnType = TypeResolver.resolveRawArguments(Function.class, map.getClass())[1]; + return mutator.toDebugString(isInCycle) + " -> " + returnType.getSimpleName(); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/combinator/ProductMutator.java b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/ProductMutator.java new file mode 100644 index 00000000..9057fd35 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/combinator/ProductMutator.java @@ -0,0 +1,138 @@ +/* + * 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.combinator; + +import static com.code_intelligence.jazzer.mutation.support.InputStreamSupport.extendWithZeros; +import static com.code_intelligence.jazzer.mutation.support.Preconditions.require; +import static com.code_intelligence.jazzer.mutation.support.Preconditions.requireNonNullElements; +import static java.util.Arrays.stream; +import static java.util.stream.Collectors.joining; + +import com.code_intelligence.jazzer.mutation.api.Debuggable; +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 java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; +import java.io.InputStream; +import java.io.OutputStream; +import java.util.Arrays; +import java.util.function.Predicate; + +@SuppressWarnings({"unchecked", "rawtypes"}) +public final class ProductMutator extends SerializingInPlaceMutator<Object[]> { + // Inverse frequency in which product type mutators should be used in cross over. + private final static int INVERSE_PICK_VALUE_SUPPLIER_FREQUENCY = 100; + + private final SerializingMutator[] mutators; + + ProductMutator(SerializingMutator[] mutators) { + requireNonNullElements(mutators); + require(mutators.length > 0, "mutators must not be empty"); + this.mutators = Arrays.copyOf(mutators, mutators.length); + } + + @Override + public Object[] read(DataInputStream in) throws IOException { + Object[] value = new Object[mutators.length]; + for (int i = 0; i < mutators.length; i++) { + value[i] = mutators[i].read(in); + } + return value; + } + + @Override + public Object[] readExclusive(InputStream in) throws IOException { + Object[] value = new Object[mutators.length]; + int lastIndex = mutators.length - 1; + DataInputStream endlessData = new DataInputStream(extendWithZeros(in)); + for (int i = 0; i < lastIndex; i++) { + value[i] = mutators[i].read(endlessData); + } + value[lastIndex] = mutators[lastIndex].readExclusive(in); + return value; + } + + @Override + public void write(Object[] value, DataOutputStream out) throws IOException { + for (int i = 0; i < mutators.length; i++) { + mutators[i].write(value[i], out); + } + } + + @Override + public void writeExclusive(Object[] value, OutputStream out) throws IOException { + DataOutputStream dataOut = new DataOutputStream(out); + int lastIndex = mutators.length - 1; + for (int i = 0; i < lastIndex; i++) { + mutators[i].write(value[i], dataOut); + } + mutators[lastIndex].writeExclusive(value[lastIndex], out); + } + + @Override + protected Object[] makeDefaultInstance() { + return new Object[mutators.length]; + } + + @Override + public void initInPlace(Object[] reference, PseudoRandom prng) { + for (int i = 0; i < mutators.length; i++) { + reference[i] = mutators[i].init(prng); + } + } + + @Override + public void mutateInPlace(Object[] reference, PseudoRandom prng) { + int i = prng.indexIn(mutators); + reference[i] = mutators[i].mutate(reference[i], prng); + } + + @Override + public void crossOverInPlace(Object[] reference, Object[] otherReference, PseudoRandom prng) { + for (int i = 0; i < mutators.length; i++) { + SerializingMutator mutator = mutators[i]; + Object value = reference[i]; + Object otherValue = otherReference[i]; + Object crossedOver = prng.pickValue(value, otherValue, + () -> mutator.crossOver(value, otherValue, prng), INVERSE_PICK_VALUE_SUPPLIER_FREQUENCY); + if (crossedOver == otherReference) { + // If otherReference was picked, it needs to be detached as mutating + // it is prohibited in cross over. + crossedOver = mutator.detach(crossedOver); + } + reference[i] = crossedOver; + } + } + + @Override + public Object[] detach(Object[] value) { + Object[] clone = new Object[mutators.length]; + for (int i = 0; i < mutators.length; i++) { + clone[i] = mutators[i].detach(value[i]); + } + return clone; + } + + @Override + public String toDebugString(Predicate<Debuggable> isInCycle) { + return stream(mutators) + .map(mutator -> mutator.toDebugString(isInCycle)) + .collect(joining(", ", "[", "]")); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/engine/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/engine/BUILD.bazel new file mode 100644 index 00000000..50bc180a --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/engine/BUILD.bazel @@ -0,0 +1,12 @@ +java_library( + name = "engine", + srcs = glob(["*.java"]), + visibility = [ + "//src/main/java/com/code_intelligence/jazzer/mutation:__pkg__", + "//src/test/java/com/code_intelligence/jazzer/mutation:__subpackages__", + ], + deps = [ + "//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/engine/SeededPseudoRandom.java b/src/main/java/com/code_intelligence/jazzer/mutation/engine/SeededPseudoRandom.java new file mode 100644 index 00000000..515f345b --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/engine/SeededPseudoRandom.java @@ -0,0 +1,288 @@ +/* + * 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.engine; + +import static com.code_intelligence.jazzer.mutation.support.Preconditions.require; + +import com.code_intelligence.jazzer.mutation.api.PseudoRandom; +import com.code_intelligence.jazzer.mutation.support.Preconditions; +import com.code_intelligence.jazzer.mutation.support.RandomSupport; +import java.util.List; +import java.util.SplittableRandom; +import java.util.function.Supplier; + +public final class SeededPseudoRandom implements PseudoRandom { + // We use SplittableRandom instead of Random since it doesn't incur unnecessary synchronization + // overhead and uses a much better RNG under the hood that can generate all long values. + private final SplittableRandom random; + + public SeededPseudoRandom(long seed) { + this.random = new SplittableRandom(seed); + } + + @Override + public boolean choice() { + return random.nextBoolean(); + } + + @Override + public boolean trueInOneOutOf(int inverseFrequencyTrue) { + // Ensure that the outcome of the choice isn't fixed. + require(inverseFrequencyTrue >= 2); + return indexIn(inverseFrequencyTrue) == 0; + } + + @Override + public <T> T pickIn(T[] array) { + return array[indexIn(array.length)]; + } + + @Override + public <T> T pickIn(List<T> list) { + return list.get(indexIn(list.size())); + } + + @Override + public <T> int indexIn(T[] array) { + return indexIn(array.length); + } + + @Override + public <T> int indexIn(List<T> list) { + return indexIn(list.size()); + } + + @Override + public int indexIn(int range) { + require(range >= 1); + // TODO: Replace random.nextInt(length) with the fast version of + // https://lemire.me/blog/2016/06/30/fast-random-shuffling/, which avoids a modulo operation. + // It's slightly more biased for large bounds, but indices and choices tend to be small and + // are generated frequently (e.g. when picking a submutator). + return random.nextInt(range); + } + + @Override + public <T> int otherIndexIn(T[] array, int currentIndex) { + return otherIndexIn(array.length, currentIndex); + } + + @Override + public int otherIndexIn(int range, int currentIndex) { + int otherIndex = currentIndex + closedRange(1, range - 1); + if (otherIndex < range) { + return otherIndex; + } else { + return otherIndex - range; + } + } + + @Override + public int closedRange(int lowerInclusive, int upperInclusive) { + require(lowerInclusive <= upperInclusive); + int range = upperInclusive - lowerInclusive + 1; + if (range > 0) { + return lowerInclusive + random.nextInt(range); + } else { + // The interval [lowerInclusive, upperInclusive] covers at least half of the + // [Integer.MIN_VALUE, Integer.MAX_VALUE] range, fall back to rejection sampling with an + // expected number of samples <= 2. + int r; + do { + r = random.nextInt(); + } while (r < lowerInclusive); + return r; + } + } + + @Override + public long closedRange(long lowerInclusive, long upperInclusive) { + require(lowerInclusive <= upperInclusive); + if (upperInclusive < Long.MAX_VALUE) { + // upperInclusive + 1 <= Long.MAX_VALUE + return random.nextLong(lowerInclusive, upperInclusive + 1); + } else if (lowerInclusive > 0) { + // upperInclusive + 1 - lowerInclusive <= Long.MAX_VALUE + return lowerInclusive + random.nextLong(upperInclusive + 1 - lowerInclusive); + } else { + // The interval [lowerInclusive, Long.MAX_VALUE] covers at least half of the + // [Long.MIN_VALUE, Long.MAX_VALUE] range, fall back to rejection sampling with an expected + // number of samples <= 2. + long r; + do { + r = random.nextLong(); + } while (r < lowerInclusive); + return r; + } + } + + // This function always returns a finite value + @Override + public float closedRange(float lowerInclusive, float upperInclusive) { + require(lowerInclusive <= upperInclusive); + if (lowerInclusive == upperInclusive) { + require(Double.isFinite(lowerInclusive)); + return lowerInclusive; + } + // Special case: [Float.NEGATIVE_INFINITY, -Float.MAX_VALUE] + if (lowerInclusive == Float.NEGATIVE_INFINITY && upperInclusive == -Float.MAX_VALUE) + return -Float.MAX_VALUE; + // Special case: [Float.MAX_VALUE, Float.POSITIVE_INFINITY] + if (lowerInclusive == Float.MAX_VALUE && upperInclusive == Float.POSITIVE_INFINITY) + return Float.MAX_VALUE; + float limitedLower = + lowerInclusive == Float.NEGATIVE_INFINITY ? -Float.MAX_VALUE : lowerInclusive; + float limitedUpper = + upperInclusive == Float.POSITIVE_INFINITY ? Float.MAX_VALUE : upperInclusive; + + // nextDouble(start, bound) is exclusive of bound, so we use Math.nextUp to extend the bound to + // the next representable double. The maximal possible range of a float is always finite when + // represented as a double. Therefore, we can safely use nextDouble and convert it to a float. + return (float) random.nextDouble((double) limitedLower, Math.nextUp((double) limitedUpper)); + } + + // This function always returns a finite value + @Override + public double closedRange(double lowerInclusive, double upperInclusive) { + require(lowerInclusive <= upperInclusive); + if (lowerInclusive == upperInclusive) { + require(Double.isFinite(lowerInclusive)); + return lowerInclusive; + } + // Special case: [Double.NEGATIVE_INFINITY, -Double.MAX_VALUE] + if (lowerInclusive == Double.NEGATIVE_INFINITY && upperInclusive == -Double.MAX_VALUE) + return -Double.MAX_VALUE; + // Special case: [Double.MAX_VALUE, Double.POSITIVE_INFINITY) + if (lowerInclusive == Double.MAX_VALUE && upperInclusive == Double.POSITIVE_INFINITY) + return Double.MAX_VALUE; + + // nextDouble(start, bound) cannot deal with infinite values, so we need to limit them + double limitedLower = + lowerInclusive == Double.NEGATIVE_INFINITY ? -Double.MAX_VALUE : lowerInclusive; + double limitedUpper = + upperInclusive == Double.POSITIVE_INFINITY ? Double.MAX_VALUE : upperInclusive; + + // After limiting, the range may contain only a single value: return that + if (limitedLower == limitedUpper) + return limitedLower; + + // random.nextDouble() is exclusive of the upper bound. To include the upper bound, + // we extend the bound to the next double value by using Math.nextUp(limitedUpper). + double nextUpper = + (limitedUpper == Double.MAX_VALUE) ? limitedUpper : Math.nextUp(limitedUpper); + + // This, however, leads to a problem when the upper bound is Double.MAX_VALUE, because the next + // double after that is Double.POSITIVE_INFINITY. This case is treated the same as infinite + // range case, in the else branch. + boolean couldExtendRange = nextUpper != limitedUpper; + + // nextDouble(start, bound) can only deal with finite ranges + if (Double.isFinite(nextUpper - limitedLower) && couldExtendRange) { + double result = random.nextDouble(limitedLower, nextUpper); + // Clamp random.nextDouble() to the upper bound. + // This is a workaround for RandomSupport.nextDouble() that causes it to + // return values greater than upper bound. + // See https://bugs.openjdk.org/browse/JDK-8281183 for a list of affected JDK versions. + if (result > limitedUpper) + result = limitedUpper; + return result; + } else { + // Ranges that exceeds the maximum representable double value, or ranges that could not be + // extended scale a random n from range [0; 1] onto the range [limitLower, limitUpper] + // limitedLower * (1 - n) + limitedUpper * n - is the same as: + // limitedLower + (limitedUpper - limitedLower) * n + // limitedLower + range * n + double n = random.nextDouble(0.0, Math.nextUp(1.0)); + return limitedLower * (1 - n) + limitedUpper * n; + } + } + + @Override + public void bytes(byte[] bytes) { + RandomSupport.nextBytes(random, bytes); + } + + @Override + public int closedRangeBiasedTowardsSmall(int upperInclusive) { + if (upperInclusive == 0) { + return 0; + } + Preconditions.require(upperInclusive > 0); + // Modified from (Apache-2.0) + // https://github.com/abseil/abseil-cpp/blob/2927340217c37328319b5869285a6dcdbc13e7a7/absl/random/zipf_distribution.h + // by inlining the values v = 1 and q = 2. + final double kd = upperInclusive; + final double hxm = zipf_h(kd + 0.5); + final double h0x5 = -1.0 / 1.5; + final double elogv_q = 1.0; + final double hx0_minus_hxm = (h0x5 - elogv_q) - hxm; + final double s = 0.46153846153846123; + double k; + while (true) { + final double v = random.nextDouble(); + final double u = hxm + v * hx0_minus_hxm; + final double x = zipf_hinv(u); + k = Math.floor(x + 0.5); + if (k > kd) { + continue; + } + if (k - x <= s) { + break; + } + final double h = zipf_h(k + 0.5); + final double r = zipf_pow_negative_q(1.0 + k); + if (u >= h - r) { + break; + } + } + return (int) k; + } + + @Override + public int closedRangeBiasedTowardsSmall(int lowerInclusive, int upperInclusive) { + return lowerInclusive + closedRangeBiasedTowardsSmall(upperInclusive - lowerInclusive); + } + + private static double zipf_h(double x) { + return -1.0 / (x + 1.0); + } + + private static double zipf_hinv(double x) { + return -1.0 + -1.0 / x; + } + + private static double zipf_pow_negative_q(double x) { + return 1.0 / (x * x); + } + + @Override + public <T> T pickValue( + T value, T otherValue, Supplier<T> supplier, int inverseSupplierFrequency) { + if (trueInOneOutOf(inverseSupplierFrequency)) { + return supplier.get(); + } else if (choice()) { + return value; + } else { + return otherValue; + } + } + + @Override + public long nextLong() { + return random.nextLong(); + } +} 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); + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/BUILD.bazel b/src/main/java/com/code_intelligence/jazzer/mutation/support/BUILD.bazel new file mode 100644 index 00000000..5765ceed --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/BUILD.bazel @@ -0,0 +1,11 @@ +java_library( + name = "support", + srcs = glob(["*.java"]), + visibility = [ + "//src/main/java/com/code_intelligence/jazzer/mutation:__subpackages__", + "//src/test/java/com/code_intelligence/jazzer/mutation:__subpackages__", + ], + deps = [ + "//src/main/java/com/code_intelligence/jazzer/mutation/annotation", + ], +) diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/ExceptionSupport.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/ExceptionSupport.java new file mode 100644 index 00000000..bd5f434b --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/ExceptionSupport.java @@ -0,0 +1,31 @@ +/* + * 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.support; + +public final class ExceptionSupport { + /** + * Allows throwing any {@link Throwable} unchanged as if it were an unchecked exception. + * + * <p>Example: {@code throw asUnchecked(new IOException())} + */ + @SuppressWarnings("unchecked") + public static <T extends Throwable> T asUnchecked(Throwable t) throws T { + throw(T) t; + } + + private ExceptionSupport() {} +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/InputStreamSupport.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/InputStreamSupport.java new file mode 100644 index 00000000..c643fea2 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/InputStreamSupport.java @@ -0,0 +1,256 @@ +/* + * 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.support; + +import static com.code_intelligence.jazzer.mutation.support.Preconditions.require; +import static java.lang.Math.max; +import static java.lang.Math.min; +import static java.util.Objects.requireNonNull; + +import java.io.ByteArrayInputStream; +import java.io.IOException; +import java.io.InputStream; +import java.util.ArrayDeque; +import java.util.Arrays; +import java.util.Queue; + +public final class InputStreamSupport { + public static byte[] readAllBytes(InputStream stream) throws IOException { + requireNonNull(stream); + Queue<byte[]> buffers = new ArrayDeque<>(); + int arrayLength = 0; + outer: + while (true) { + byte[] buffer = new byte[max(8192, stream.available())]; + buffers.add(buffer); + int off = 0; + while (off < buffer.length) { + int bytesRead = stream.read(buffer, off, buffer.length - off); + if (bytesRead == -1) { + break outer; + } + off += bytesRead; + arrayLength += bytesRead; + } + } + + byte[] result = new byte[arrayLength]; + int offset = 0; + byte[] buffer; + int remaining = arrayLength; + while ((buffer = buffers.poll()) != null) { + int toCopy = min(buffer.length, remaining); + System.arraycopy(buffer, 0, result, offset, toCopy); + remaining -= toCopy; + } + return result; + } + + private static final InputStream infiniteZerosStream = new ExtendWithNullInputStream(); + + /** + * @return an infinite stream consisting of 0s + */ + public static InputStream infiniteZeros() { + return infiniteZerosStream; + } + + /** + * @return {@code stream} extended with 0s to an infinite stream + */ + public static InputStream extendWithZeros(InputStream stream) { + if (stream instanceof ExtendWithNullInputStream) { + return stream; + } + return new ExtendWithNullInputStream(requireNonNull(stream)); + } + + public static final class ExtendWithNullInputStream extends InputStream { + private static final InputStream ALWAYS_EOF = new ByteArrayInputStream(new byte[0]); + private final InputStream stream; + private boolean eof; + + private ExtendWithNullInputStream() { + this.stream = ALWAYS_EOF; + this.eof = true; + } + + private ExtendWithNullInputStream(InputStream stream) { + this.stream = stream; + this.eof = false; + } + + @Override + public int read() throws IOException { + if (eof) { + return 0; + } + + int res = stream.read(); + if (res != -1) { + return res; + } else { + eof = true; + return 0; + } + } + + @Override + public int read(byte[] b, int off, int len) throws IOException { + if (eof) { + Arrays.fill(b, off, off + len, (byte) 0); + } else { + int bytesRead = stream.read(b, off, len); + if (bytesRead < len) { + eof = true; + Arrays.fill(b, max(off, off + bytesRead), off + len, (byte) 0); + } + } + return len; + } + + @Override + public int available() throws IOException { + if (eof) { + return Integer.MAX_VALUE; + } else { + return stream.available(); + } + } + + @Override + public void close() throws IOException { + stream.close(); + } + } + + /** + * @return a stream with the first {@code bytes} bytes of {@code stream} + */ + public static InputStream cap(InputStream stream, long bytes) { + requireNonNull(stream); + require(bytes >= 0, "bytes must be non-negative"); + return new CappedInputStream(stream, bytes); + } + + private static final class CappedInputStream extends InputStream { + private final InputStream stream; + private long remaining; + + CappedInputStream(InputStream stream, long remaining) { + this.stream = stream; + this.remaining = remaining; + } + + @Override + public int read() throws IOException { + if (remaining == 0) { + return -1; + } + + int res = stream.read(); + if (res != -1) { + --remaining; + } + return res; + } + + @Override + public int read(byte[] b, int off, int len) throws IOException { + if (remaining == 0) { + return -1; + } + + int res = stream.read(b, off, (int) min(len, remaining)); + if (res != -1) { + remaining -= res; + } + return res; + } + + @Override + public int available() throws IOException { + return (int) min(stream.available(), remaining); + } + + @Override + public void close() throws IOException { + stream.close(); + } + } + + /** + * Wraps a given stream with the functionality to detect if it was read exactly. + * To do so, the stream must provide an accurate implementation of {@link + * InputStream#available()}, hence it's restricted to {@link ByteArrayInputStream} for now. + * + * @return {@code stream} extended that detects if it was consumed exactly + */ + public static ReadExactlyInputStream extendWithReadExactly(ByteArrayInputStream stream) { + return new ReadExactlyInputStream(requireNonNull(stream)); + } + + public static final class ReadExactlyInputStream extends InputStream { + private final InputStream stream; + private boolean eof; + + private ReadExactlyInputStream(InputStream stream) { + this.stream = stream; + this.eof = false; + } + + public boolean isConsumedExactly() { + try { + // Forwards availability check to the underlying ByteInputStream, + // which is accurate for the number of available bytes. + return !eof && available() == 0; + } catch (IOException e) { + return false; + } + } + + @Override + public int read() throws IOException { + int res = stream.read(); + if (res == -1) { + eof = true; + } + return res; + } + + @Override + public int read(byte[] b, int off, int len) throws IOException { + int read = stream.read(b, off, len); + if (read < len) { + eof = true; + } + return read; + } + + @Override + public int available() throws IOException { + return stream.available(); + } + + @Override + public void close() throws IOException { + stream.close(); + } + } + + private InputStreamSupport() {} +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/ParameterHolder.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/ParameterHolder.java new file mode 100644 index 00000000..316a6dfd --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/ParameterHolder.java @@ -0,0 +1,63 @@ +/* + * 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.support; + +import static com.code_intelligence.jazzer.mutation.support.Preconditions.require; +import static java.util.stream.Collectors.toList; + +import java.lang.annotation.Annotation; +import java.lang.reflect.AnnotatedType; +import java.lang.reflect.Method; +import java.lang.reflect.Type; +import java.util.Arrays; +import java.util.List; + +/** + * A factory for {@link AnnotatedType} instances capturing method parameters. + * + * <p>Due to type erasure, this class can only be used by creating an anonymous subclass with a + * method called {@code foo} that takes exactly the desired parameter. + * + * <p>Example: {@code new ParameterHolder {void foo(@NotNull List<String> param)}.annotatedType} + */ +public abstract class ParameterHolder { + protected ParameterHolder() {} + + public AnnotatedType annotatedType() { + return getMethod().getAnnotatedParameterTypes()[0]; + } + + public Type type() { + return annotatedType().getType(); + } + + public Annotation[] parameterAnnotations() { + return getMethod().getParameterAnnotations()[0]; + } + + private Method getMethod() { + List<Method> foos = Arrays.stream(this.getClass().getDeclaredMethods()) + .filter(method -> method.getName().equals("foo")) + .collect(toList()); + require(foos.size() == 1, + this.getClass().getName() + " must define exactly one function named 'foo'"); + Method foo = foos.get(0); + require(foo.getParameterCount() == 1, + this.getClass().getName() + "#foo must define exactly one parameter"); + return foo; + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/Preconditions.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/Preconditions.java new file mode 100644 index 00000000..a77f65fb --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/Preconditions.java @@ -0,0 +1,55 @@ +/* + * 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.support; + +import static java.util.Objects.requireNonNull; + +public final class Preconditions { + private Preconditions() {} + + public static void check(boolean property) { + if (!property) { + throw new IllegalStateException(); + } + } + + public static void check(boolean property, String message) { + if (!property) { + throw new IllegalStateException(message); + } + } + + public static void require(boolean property) { + if (!property) { + throw new IllegalArgumentException(); + } + } + + public static void require(boolean property, String message) { + if (!property) { + throw new IllegalArgumentException(message); + } + } + + public static <T> T[] requireNonNullElements(T[] array) { + requireNonNull(array); + for (T element : array) { + requireNonNull(element, "array must not contain null elements"); + } + return array; + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/RandomSupport.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/RandomSupport.java new file mode 100644 index 00000000..5cfa765e --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/RandomSupport.java @@ -0,0 +1,64 @@ +/* + * 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.support; + +import java.util.SplittableRandom; + +public final class RandomSupport { + private RandomSupport() {} + + /** + * Polyfill for {@link SplittableRandom#nextBytes(byte[])}, which is not available in Java 8. + */ + public static void nextBytes(SplittableRandom random, byte[] bytes) { + // Taken from the implementation contract + // https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/RandomGenerator.html#nextBytes(byte%5B%5D) + // for interoperability with the RandomGenerator interface available as of Java 17. + int i = 0; + int len = bytes.length; + for (int words = len >> 3; words-- > 0;) { + long rnd = random.nextLong(); + for (int n = 8; n-- > 0; rnd >>>= Byte.SIZE) bytes[i++] = (byte) rnd; + } + if (i < len) + for (long rnd = random.nextLong(); i<len; rnd>>>= Byte.SIZE) bytes[i++] = (byte) rnd; + } + + /** + * Clamp function for integers, which Java does not yet have + * + * @param value the value you want to clamp + * @param min the minimum allowable value (inclusive) + * @param max the maximum allowable value (inclusive) + * @return Closest number to {@code value} within the range {@code [min, max]} + */ + public static int clamp(int value, int min, int max) { + return Math.min(Math.max(value, min), max); + } + + /** + * Clamp function for longs, which Java does not yet have + * + * @param value the value you want to clamp + * @param min the minimum allowable value (inclusive) + * @param max the maximum allowable value (inclusive) + * @return Closest number to {@code value} within the range {@code [min, max]} + */ + public static long clamp(long value, long min, long max) { + return Math.min(Math.max(value, min), max); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/StreamSupport.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/StreamSupport.java new file mode 100644 index 00000000..b61980c4 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/StreamSupport.java @@ -0,0 +1,72 @@ +/* + * 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.support; + +import static java.util.stream.Collectors.toList; + +import java.util.AbstractMap.SimpleEntry; +import java.util.List; +import java.util.NoSuchElementException; +import java.util.Optional; +import java.util.function.IntFunction; +import java.util.stream.Stream; + +public final class StreamSupport { + private StreamSupport() {} + + public static boolean[] toBooleanArray(Stream<Boolean> stream) { + List<Boolean> list = stream.collect(toList()); + boolean[] array = new boolean[list.size()]; + for (int i = 0; i < list.size(); i++) { + array[i] = list.get(i); + } + return array; + } + + /** + * @return the first present value, otherwise {@link Optional#empty()} + */ + public static <T> Optional<T> findFirstPresent(Stream<Optional<T>> stream) { + return stream.filter(Optional::isPresent).map(Optional::get).findFirst(); + } + + /** + * @return an array with the values if all {@link Optional}s are present, otherwise + * {@link Optional#empty()} + */ + public static <T> Optional<T[]> toArrayOrEmpty( + Stream<Optional<T>> stream, IntFunction<T[]> newArray) { + try { + return Optional.of(stream.map(Optional::get).toArray(newArray)); + } catch (NoSuchElementException e) { + return Optional.empty(); + } + } + + /** + * Return a stream containing the optional value if present, otherwise an empty stream. + * + * @return stream containing the optional value + */ + public static <T> Stream<T> getOrEmpty(Optional<T> optional) { + return optional.isPresent() ? Stream.of(optional.get()) : Stream.empty(); + } + + public static <K, V> SimpleEntry<K, V> entry(K key, V value) { + return new SimpleEntry<>(key, value); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/TypeHolder.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/TypeHolder.java new file mode 100644 index 00000000..e703f9f1 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/TypeHolder.java @@ -0,0 +1,43 @@ +/* + * 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.support; + +import java.lang.reflect.AnnotatedParameterizedType; +import java.lang.reflect.AnnotatedType; +import java.lang.reflect.Type; + +/** + * A factory for {@link AnnotatedType} instances capturing types. + * + * <p>Due to type erasure, this class can only be used by creating an anonymous subclass. + * + * <p>Example: {@code new TypeHolder<List<String>> {}.annotatedType} + * + * @param <T> the type to hold + */ +public abstract class TypeHolder<T> { + protected TypeHolder() {} + + public AnnotatedType annotatedType() { + return ((AnnotatedParameterizedType) this.getClass().getAnnotatedSuperclass()) + .getAnnotatedActualTypeArguments()[0]; + } + + public Type type() { + return annotatedType().getType(); + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/TypeSupport.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/TypeSupport.java new file mode 100644 index 00000000..8ce3aefc --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/TypeSupport.java @@ -0,0 +1,564 @@ +/* + * 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.support; + +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.Preconditions.requireNonNullElements; +import static java.util.Arrays.stream; +import static java.util.Objects.requireNonNull; +import static java.util.stream.Collectors.joining; +import static java.util.stream.Collectors.toSet; + +import com.code_intelligence.jazzer.mutation.annotation.NotNull; +import com.code_intelligence.jazzer.mutation.annotation.WithLength; +import java.lang.annotation.Annotation; +import java.lang.annotation.Inherited; +import java.lang.reflect.AnnotatedArrayType; +import java.lang.reflect.AnnotatedElement; +import java.lang.reflect.AnnotatedParameterizedType; +import java.lang.reflect.AnnotatedType; +import java.lang.reflect.AnnotatedTypeVariable; +import java.lang.reflect.AnnotatedWildcardType; +import java.lang.reflect.Array; +import java.lang.reflect.ParameterizedType; +import java.lang.reflect.Type; +import java.util.*; +import java.util.function.BiConsumer; +import java.util.function.Function; +import java.util.stream.Collectors; +import java.util.stream.Stream; + +public final class TypeSupport { + private static final Annotation NOT_NULL = + new TypeHolder<@NotNull String>() {}.annotatedType().getAnnotation(NotNull.class); + + private TypeSupport() {} + + public static boolean isPrimitive(AnnotatedType type) { + return isPrimitive(type.getType()); + } + + public static boolean isPrimitive(Type type) { + if (!(type instanceof Class<?>) ) { + return false; + } + return ((Class<?>) type).isPrimitive(); + } + + public static boolean isInheritable(Annotation annotation) { + return annotation.annotationType().getDeclaredAnnotation(Inherited.class) != null; + } + + /** + * Returns {@code type} as a {@code Class<? extends T>} if it is a subclass of T, otherwise + * empty. + * + * <p>This function also returns an empty {@link Optional} for more complex (e.g. parameterized) + * types. + */ + public static <T> Optional<Class<? extends T>> asSubclassOrEmpty( + AnnotatedType type, Class<T> superclass) { + if (!(type.getType() instanceof Class<?>) ) { + return Optional.empty(); + } + + Class<?> actualClazz = (Class<?>) type.getType(); + if (!superclass.isAssignableFrom(actualClazz)) { + return Optional.empty(); + } + + return Optional.of(actualClazz.asSubclass(superclass)); + } + + public static AnnotatedType asAnnotatedType(Class<?> clazz) { + requireNonNull(clazz); + return new AnnotatedType() { + @Override + public Type getType() { + return clazz; + } + + @Override + public <T extends Annotation> T getAnnotation(Class<T> annotationClass) { + return annotatedElementGetAnnotation(this, annotationClass); + } + + @Override + public Annotation[] getAnnotations() { + // No directly present annotations, look for inheritable present annotations on the + // superclass. + if (clazz.getSuperclass() == null) { + return new Annotation[0]; + } + return stream(clazz.getSuperclass().getAnnotations()) + .filter(TypeSupport::isInheritable) + .toArray(Annotation[] ::new); + } + + @Override + public Annotation[] getDeclaredAnnotations() { + // No directly present annotations. + return new Annotation[0]; + } + + @Override + public String toString() { + return annotatedTypeToString(this); + } + + @Override + public int hashCode() { + throw new UnsupportedOperationException( + "hashCode() is not supported as its behavior isn't specified"); + } + + @Override + public boolean equals(Object obj) { + throw new UnsupportedOperationException( + "equals() is not supported as its behavior isn't specified"); + } + }; + } + + /** + * Visits the individual classes and their directly present annotations that make up the given + * type. + * + * <p>Classes are visited in left-to-right order as they appear in the type definition, except + * that an array class is visited before its component class. + * + * @throws IllegalArgumentException if the given type contains a wildcard type or type variable + */ + public static void visitAnnotatedType( + AnnotatedType type, BiConsumer<Class<?>, Annotation[]> visitor) { + visitAnnotatedTypeInternal(type, visitor); + } + + private static Class<?> visitAnnotatedTypeInternal( + AnnotatedType type, BiConsumer<Class<?>, Annotation[]> visitor) { + Class<?> clazz; + if (type instanceof AnnotatedWildcardType) { + throw new IllegalArgumentException("Wildcard types are not supported: " + type); + } else if (type instanceof AnnotatedTypeVariable) { + throw new IllegalArgumentException("Type variables are not supported: " + type); + } else if (type instanceof AnnotatedParameterizedType) { + AnnotatedParameterizedType annotatedParameterizedType = (AnnotatedParameterizedType) type; + check(annotatedParameterizedType.getType() instanceof ParameterizedType); + Type rawType = ((ParameterizedType) annotatedParameterizedType.getType()).getRawType(); + check(rawType instanceof Class<?>); + clazz = (Class<?>) rawType; + + visitor.accept(clazz, type.getDeclaredAnnotations()); + for (AnnotatedType typeArgument : + annotatedParameterizedType.getAnnotatedActualTypeArguments()) { + visitAnnotatedTypeInternal(typeArgument, visitor); + } + } else if (type instanceof AnnotatedArrayType) { + AnnotatedArrayType arrayType = (AnnotatedArrayType) type; + + // Recursively determine the array class before visiting the component type. + Class<?> componentClass = + visitAnnotatedTypeInternal(arrayType.getAnnotatedGenericComponentType(), (c, a) -> {}); + clazz = Array.newInstance(componentClass, 0).getClass(); + visitor.accept(clazz, type.getDeclaredAnnotations()); + visitAnnotatedTypeInternal(arrayType.getAnnotatedGenericComponentType(), visitor); + } else { + check(type.getType() instanceof Class<?>); + clazz = (Class<?>) type.getType(); + + visitor.accept(clazz, type.getDeclaredAnnotations()); + } + return clazz; + } + + public static AnnotatedType notNull(AnnotatedType type) { + return withExtraAnnotations(type, NOT_NULL); + } + + /** + * Constructs an anonymous WithLength class that can be applied as an annotation to {@code type} + * with the given + * {@code min} and {@code max} values. + * @param type + * @param min + * @param max + * @return {@code type} with a `WithLength` annotation applied to it + */ + public static AnnotatedType withLength(AnnotatedType type, int min, int max) { + WithLength withLength = withLengthImplementation(min, max); + return withExtraAnnotations(type, withLength); + } + + private static WithLength withLengthImplementation(int min, int max) { + return new WithLength() { + @Override + public int min() { + return min; + } + + @Override + public int max() { + return max; + } + + @Override + public Class<? extends Annotation> annotationType() { + return WithLength.class; + } + + @Override + public boolean equals(Object o) { + if (!(o instanceof WithLength)) { + return false; + } + WithLength other = (WithLength) o; + return this.min() == other.min() && this.max() == other.max(); + } + + @Override + public int hashCode() { + int hash = 0; + hash += ("min".hashCode() * 127) ^ Integer.valueOf(this.min()).hashCode(); + hash += ("max".hashCode() * 127) ^ Integer.valueOf(this.max()).hashCode(); + return hash; + } + }; + } + + public static AnnotatedParameterizedType withTypeArguments( + AnnotatedType type, AnnotatedType... typeArguments) { + requireNonNull(type); + requireNonNullElements(typeArguments); + require(typeArguments.length > 0); + require(!(type instanceof AnnotatedParameterizedType || type instanceof AnnotatedTypeVariable + || type instanceof AnnotatedWildcardType || type instanceof AnnotatedArrayType), + "only plain annotated types are supported"); + require( + ((Class<?>) type.getType()).getEnclosingClass() == null, "nested classes aren't supported"); + + ParameterizedType filledRawType = new ParameterizedType() { + @Override + public Type[] getActualTypeArguments() { + return stream(typeArguments).map(AnnotatedType::getType).toArray(Type[] ::new); + } + + @Override + public Type getRawType() { + return type.getType(); + } + + @Override + public Type getOwnerType() { + // We require the class is top-level. + return null; + } + + @Override + public String toString() { + return getRawType() + + stream(getActualTypeArguments()).map(Type::toString).collect(joining(",", "<", ">")); + } + + @Override + public boolean equals(Object obj) { + if (!(obj instanceof ParameterizedType)) { + return false; + } + ParameterizedType other = (ParameterizedType) obj; + return getRawType().equals(other.getRawType()) && null == other.getOwnerType() + && Arrays.equals(getActualTypeArguments(), other.getActualTypeArguments()); + } + + @Override + public int hashCode() { + throw new UnsupportedOperationException( + "hashCode() is not supported as its behavior isn't specified"); + } + }; + + return new AnnotatedParameterizedType() { + @Override + public AnnotatedType[] getAnnotatedActualTypeArguments() { + return Arrays.copyOf(typeArguments, typeArguments.length); + } + + // @Override as of Java 9 + @SuppressWarnings("Since15") + public AnnotatedType getAnnotatedOwnerType() { + return null; + } + + @Override + public Type getType() { + return filledRawType; + } + + @Override + public <T extends Annotation> T getAnnotation(Class<T> annotationClass) { + return type.getAnnotation(annotationClass); + } + + @Override + public Annotation[] getAnnotations() { + return type.getAnnotations(); + } + + @Override + public Annotation[] getDeclaredAnnotations() { + return type.getDeclaredAnnotations(); + } + + @Override + public String toString() { + return annotatedTypeToString(this); + } + + @Override + public boolean equals(Object obj) { + if (!(obj instanceof AnnotatedParameterizedType)) { + return false; + } + AnnotatedParameterizedType other = (AnnotatedParameterizedType) obj; + // Can't call getAnnotatedOwnerType on Java 8, but since our own implementation always + // returns null, comparing getType().getOwnerType() via getType() is sufficient. + return Objects.equals(getType(), other.getType()) + && Arrays.equals( + getAnnotatedActualTypeArguments(), other.getAnnotatedActualTypeArguments()) + && Arrays.equals(getAnnotations(), other.getAnnotations()); + } + + @Override + public int hashCode() { + throw new UnsupportedOperationException( + "hashCode() is not supported as its behavior isn't specified"); + } + }; + } + + public static AnnotatedType withExtraAnnotations( + AnnotatedType base, Annotation... extraAnnotations) { + requireNonNull(base); + requireNonNullElements(extraAnnotations); + + if (extraAnnotations.length == 0) { + return base; + } + + require(!(base instanceof AnnotatedTypeVariable || base instanceof AnnotatedWildcardType), + "Adding annotations to AnnotatedTypeVariables or AnnotatedWildcardTypes is not supported"); + if (base instanceof AnnotatedArrayType) { + return new AugmentedArrayType((AnnotatedArrayType) base, extraAnnotations); + } else if (base instanceof AnnotatedParameterizedType) { + return new AugmentedParameterizedType((AnnotatedParameterizedType) base, extraAnnotations); + } else { + return new AugmentedAnnotatedType(base, extraAnnotations); + } + } + + private static String annotatedTypeToString(AnnotatedType annotatedType) { + String annotations = + stream(annotatedType.getAnnotations()).map(Annotation::toString).collect(joining(" ")); + if (annotations.isEmpty()) { + return annotatedType.getType().toString(); + } else { + return annotations + " " + annotatedType.getType(); + } + } + + private static <T extends Annotation> T annotatedElementGetAnnotation( + AnnotatedElement element, Class<T> annotationClass) { + requireNonNull(annotationClass); + return stream(element.getAnnotations()) + .filter(annotation -> annotationClass.equals(annotation.annotationType())) + .findFirst() + .map(annotationClass::cast) + .orElse(null); + } + + public static Optional<Class<?>> findFirstParentIfClass(AnnotatedType type, Class<?>... parents) { + if (!(type.getType() instanceof Class<?>) ) { + return Optional.empty(); + } + Class<?> clazz = (Class<?>) type.getType(); + return Stream.of(parents).filter(parent -> parent.isAssignableFrom(clazz)).findFirst(); + } + + public static Optional<AnnotatedType> parameterTypeIfParameterized( + AnnotatedType type, Class<?> expectedParent) { + return parameterTypesIfParameterized(type, expectedParent).flatMap(typeArguments -> { + if (typeArguments.size() != 1) { + return Optional.empty(); + } else { + AnnotatedType elementType = typeArguments.get(0); + if (!(elementType.getType() instanceof ParameterizedType) + && !(elementType.getType() instanceof Class)) { + return Optional.empty(); + } else { + return Optional.of(elementType); + } + } + }); + } + + public static Optional<List<AnnotatedType>> parameterTypesIfParameterized( + AnnotatedType type, Class<?> expectedParent) { + if (!(type instanceof AnnotatedParameterizedType)) { + return Optional.empty(); + } + Class<?> clazz = (Class<?>) ((ParameterizedType) type.getType()).getRawType(); + if (!expectedParent.isAssignableFrom(clazz)) { + return Optional.empty(); + } + + AnnotatedType[] typeArguments = + ((AnnotatedParameterizedType) type).getAnnotatedActualTypeArguments(); + if (typeArguments.length == 0) { + return Optional.empty(); + } + return Optional.of(Collections.unmodifiableList(Arrays.asList(typeArguments))); + } + + /** + * Whether {@code root} is contained in a directed cycle in the directed graph rooted at it and + * defined by the given {@code successors} function. + */ + public static <T> boolean containedInDirectedCycle(T root, Function<T, Stream<T>> successors) { + HashSet<T> traversed = new HashSet<>(); + ArrayDeque<T> toTraverse = new ArrayDeque<>(); + toTraverse.addLast(root); + T currentNode; + while ((currentNode = toTraverse.pollLast()) != null) { + if (traversed.add(currentNode)) { + successors.apply(currentNode).forEachOrdered(toTraverse::addLast); + } else if (currentNode.equals(root)) { + return true; + } + } + return false; + } + + private static class AugmentedArrayType + extends AugmentedAnnotatedType implements AnnotatedArrayType { + private AugmentedArrayType(AnnotatedArrayType base, Annotation[] extraAnnotations) { + super(base, extraAnnotations); + } + + @Override + public AnnotatedType getAnnotatedGenericComponentType() { + return ((AnnotatedArrayType) base).getAnnotatedGenericComponentType(); + } + + // @Override as of Java 9 + @SuppressWarnings("Since15") + public AnnotatedType getAnnotatedOwnerType() { + throw new UnsupportedOperationException("Not implemented"); + } + } + + private static class AugmentedParameterizedType + extends AugmentedAnnotatedType implements AnnotatedParameterizedType { + private AugmentedParameterizedType( + AnnotatedParameterizedType base, Annotation[] extraAnnotations) { + super(base, extraAnnotations); + } + + @Override + public AnnotatedType[] getAnnotatedActualTypeArguments() { + return ((AnnotatedParameterizedType) base).getAnnotatedActualTypeArguments(); + } + + // @Override as of Java 9 + @SuppressWarnings("Since15") + public AnnotatedType getAnnotatedOwnerType() { + throw new UnsupportedOperationException("Not implemented"); + } + } + + private static class AugmentedAnnotatedType implements AnnotatedType { + protected final AnnotatedType base; + private final Annotation[] extraAnnotations; + + private AugmentedAnnotatedType(AnnotatedType base, Annotation[] extraAnnotations) { + this.base = requireNonNull(base); + this.extraAnnotations = checkExtraAnnotations(base, extraAnnotations); + } + + private static Annotation[] checkExtraAnnotations( + AnnotatedElement base, Annotation[] extraAnnotations) { + requireNonNullElements(extraAnnotations); + Set<Class<? extends Annotation>> existingAnnotationTypes = + stream(base.getDeclaredAnnotations()) + .map(Annotation::annotationType) + .collect(Collectors.toCollection(HashSet::new)); + for (Annotation annotation : extraAnnotations) { + boolean added = existingAnnotationTypes.add(annotation.annotationType()); + require(added, annotation + " already directly present on " + base); + } + return extraAnnotations; + } + + @Override + public Type getType() { + return base.getType(); + } + + @Override + public <T extends Annotation> T getAnnotation(Class<T> annotationClass) { + return annotatedElementGetAnnotation(this, annotationClass); + } + + @Override + public Annotation[] getAnnotations() { + Set<Class<? extends Annotation>> directlyPresentTypes = + stream(getDeclaredAnnotations()).map(Annotation::annotationType).collect(toSet()); + return Stream + .concat( + // Directly present annotations. + stream(getDeclaredAnnotations()), + // Present but not directly present annotations, never added by us as we don't add + // annotations to the super class. + stream(base.getAnnotations()) + .filter( + annotation -> !directlyPresentTypes.contains(annotation.annotationType()))) + .toArray(Annotation[] ::new); + } + + @Override + public Annotation[] getDeclaredAnnotations() { + return Stream.concat(stream(base.getDeclaredAnnotations()), stream(extraAnnotations)) + .toArray(Annotation[] ::new); + } + + @Override + public String toString() { + return annotatedTypeToString(this); + } + + @Override + public boolean equals(Object obj) { + throw new UnsupportedOperationException( + "equals() is not supported as its behavior isn't specified"); + } + + @Override + public int hashCode() { + throw new UnsupportedOperationException( + "hashCode() is not supported as its behavior isn't specified"); + } + } +} diff --git a/src/main/java/com/code_intelligence/jazzer/mutation/support/WeakIdentityHashMap.java b/src/main/java/com/code_intelligence/jazzer/mutation/support/WeakIdentityHashMap.java new file mode 100644 index 00000000..0eef7c24 --- /dev/null +++ b/src/main/java/com/code_intelligence/jazzer/mutation/support/WeakIdentityHashMap.java @@ -0,0 +1,168 @@ +/* + * 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.support; + +import static java.util.stream.Collectors.toSet; + +import java.lang.ref.Reference; +import java.lang.ref.ReferenceQueue; +import java.lang.ref.WeakReference; +import java.util.AbstractMap.SimpleEntry; +import java.util.Collection; +import java.util.HashMap; +import java.util.Map; +import java.util.Objects; +import java.util.Set; + +/** + * An unoptimized version of a {@link java.util.WeakHashMap} with the semantics of a + * {@link java.util.IdentityHashMap}. + * + * <p>If this class ever becomes a bottleneck, e.g. because of the IdentityWeakReference + * allocations, it should be replaced by a copy of the * {@link java.util.WeakHashMap} code with all + * {@code equals} calls dropped and all {@code hashCode} * calls replaced with {@link + * System#identityHashCode}. + */ +public final class WeakIdentityHashMap<K, V> implements Map<K, V> { + private final HashMap<WeakReference<K>, V> map = new HashMap<>(); + private final ReferenceQueue<K> weaklyReachables = new ReferenceQueue<>(); + + @Override + public int size() { + removeNewWeaklyReachables(); + return map.size(); + } + + @Override + public boolean isEmpty() { + removeNewWeaklyReachables(); + return map.isEmpty(); + } + + @Override + public boolean containsKey(Object key) { + removeNewWeaklyReachables(); + return map.containsKey(new IdentityWeakReference<>(key)); + } + + @Override + public boolean containsValue(Object value) { + removeNewWeaklyReachables(); + return map.containsValue(value); + } + + @Override + public V get(Object key) { + removeNewWeaklyReachables(); + return map.get(new IdentityWeakReference<>(key)); + } + + @Override + public V put(K key, V value) { + removeNewWeaklyReachables(); + return map.put(new IdentityWeakReference<>(key, weaklyReachables), value); + } + + @Override + public V remove(Object key) { + removeNewWeaklyReachables(); + return map.remove(new IdentityWeakReference<>(key)); + } + + @Override + public void putAll(Map<? extends K, ? extends V> otherMap) { + removeNewWeaklyReachables(); + for (Entry<? extends K, ? extends V> entry : otherMap.entrySet()) { + map.put(new IdentityWeakReference<>(entry.getKey(), weaklyReachables), entry.getValue()); + } + } + + @Override + public void clear() { + map.clear(); + } + + @Override + public Set<K> keySet() { + removeNewWeaklyReachables(); + return map.keySet().stream().map(WeakReference::get).filter(Objects::nonNull).collect(toSet()); + } + + @Override + public Collection<V> values() { + removeNewWeaklyReachables(); + return map.values(); + } + + @Override + public Set<Entry<K, V>> entrySet() { + removeNewWeaklyReachables(); + return map.entrySet() + .stream() + .map(e -> new SimpleEntry<>(e.getKey().get(), e.getValue())) + .filter(e -> e.getKey() != null) + .collect(toSet()); + } + + void collectKeysForTesting() { + map.keySet().forEach(ref -> { + ref.clear(); + ref.enqueue(); + }); + } + + private void removeNewWeaklyReachables() { + Reference<? extends K> referent; + while ((referent = weaklyReachables.poll()) != null) { + map.remove(referent); + } + } + + private static final class IdentityWeakReference<T> extends WeakReference<T> { + private final int referentHashCode; + + public IdentityWeakReference(T referent) { + super(referent); + this.referentHashCode = System.identityHashCode(referent); + } + + public IdentityWeakReference(T referent, ReferenceQueue<? super T> queue) { + super(referent, queue); + this.referentHashCode = System.identityHashCode(referent); + } + + @Override + public boolean equals(Object other) { + if (this == other) { + return true; + } + if (!(other instanceof WeakReference)) { + return false; + } + T referent = get(); + if (referent == null) { + return false; + } + return referent == ((WeakReference<?>) other).get(); + } + + @Override + public int hashCode() { + return referentHashCode; + } + } +} |