diff options
author | Mark <mteffeteller@google.com> | 2023-06-21 23:30:18 +0000 |
---|---|---|
committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | 2023-06-21 23:30:18 +0000 |
commit | 54819157eaa66e14f2c68b54609bd6bfa360b708 (patch) | |
tree | 68cf332a40b94b2d28b256b19b916f99220bb0c4 /src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/FloatingPointMutatorFactory.java | |
parent | ba37c2e361c2ba91bacc47fcae5383c52e50f6be (diff) | |
parent | e73be1680dae58cb83d869104def1c59102d59b2 (diff) | |
download | jazzer-api-54819157eaa66e14f2c68b54609bd6bfa360b708.tar.gz |
Sync jazzer in AOSP with upstream repo (new SHA: 30decf81a147c66fa5a098072c38ab6924ba0aa6) am: 9350e0ab03 am: 99d9a79746 am: 34a8e5c8aa am: e73be1680d
Original change: https://android-review.googlesource.com/c/platform/external/jazzer-api/+/2627336
Change-Id: I1b97ed5cdcf2adda4d443148cc0d447974e51785
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/mutator/lang/FloatingPointMutatorFactory.java')
-rw-r--r-- | src/main/java/com/code_intelligence/jazzer/mutation/mutator/lang/FloatingPointMutatorFactory.java | 597 |
1 files changed, 597 insertions, 0 deletions
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"; + } + } +} |