0001: package com.reeltwo.jumble.mutation;
0002:
0003: import java.util.Arrays;
0004: import java.util.HashSet;
0005: import java.util.Set;
0006:
0007: import org.apache.bcel.Constants;
0008: import org.apache.bcel.classfile.Attribute;
0009: import org.apache.bcel.classfile.Constant;
0010: import org.apache.bcel.classfile.ConstantDouble;
0011: import org.apache.bcel.classfile.ConstantFloat;
0012: import org.apache.bcel.classfile.ConstantInteger;
0013: import org.apache.bcel.classfile.ConstantLong;
0014: import org.apache.bcel.classfile.ConstantNameAndType;
0015: import org.apache.bcel.classfile.ConstantPool;
0016: import org.apache.bcel.classfile.ConstantString;
0017: import org.apache.bcel.classfile.ConstantUtf8;
0018: import org.apache.bcel.classfile.JavaClass;
0019: import org.apache.bcel.classfile.Method;
0020: import org.apache.bcel.classfile.Unknown;
0021: import org.apache.bcel.generic.ACONST_NULL;
0022: import org.apache.bcel.generic.ARETURN;
0023: import org.apache.bcel.generic.ATHROW;
0024: import org.apache.bcel.generic.ArithmeticInstruction;
0025: import org.apache.bcel.generic.BIPUSH;
0026: import org.apache.bcel.generic.CPInstruction;
0027: import org.apache.bcel.generic.ConstantPoolGen;
0028: import org.apache.bcel.generic.DADD;
0029: import org.apache.bcel.generic.DCMPG;
0030: import org.apache.bcel.generic.DCONST;
0031: import org.apache.bcel.generic.DDIV;
0032: import org.apache.bcel.generic.DMUL;
0033: import org.apache.bcel.generic.DNEG;
0034: import org.apache.bcel.generic.DREM;
0035: import org.apache.bcel.generic.DRETURN;
0036: import org.apache.bcel.generic.DSUB;
0037: import org.apache.bcel.generic.DUP;
0038: import org.apache.bcel.generic.DUP2;
0039: import org.apache.bcel.generic.FADD;
0040: import org.apache.bcel.generic.FCMPG;
0041: import org.apache.bcel.generic.FCONST;
0042: import org.apache.bcel.generic.FDIV;
0043: import org.apache.bcel.generic.FMUL;
0044: import org.apache.bcel.generic.FNEG;
0045: import org.apache.bcel.generic.FREM;
0046: import org.apache.bcel.generic.FRETURN;
0047: import org.apache.bcel.generic.FSUB;
0048: import org.apache.bcel.generic.GETSTATIC;
0049: import org.apache.bcel.generic.IADD;
0050: import org.apache.bcel.generic.IAND;
0051: import org.apache.bcel.generic.ICONST;
0052: import org.apache.bcel.generic.IDIV;
0053: import org.apache.bcel.generic.IFEQ;
0054: import org.apache.bcel.generic.IFNE;
0055: import org.apache.bcel.generic.IFNONNULL;
0056: import org.apache.bcel.generic.IINC;
0057: import org.apache.bcel.generic.IMUL;
0058: import org.apache.bcel.generic.INEG;
0059: import org.apache.bcel.generic.INVOKESPECIAL;
0060: import org.apache.bcel.generic.INVOKESTATIC;
0061: import org.apache.bcel.generic.INVOKEVIRTUAL;
0062: import org.apache.bcel.generic.IOR;
0063: import org.apache.bcel.generic.IREM;
0064: import org.apache.bcel.generic.IRETURN;
0065: import org.apache.bcel.generic.ISHL;
0066: import org.apache.bcel.generic.ISHR;
0067: import org.apache.bcel.generic.ISUB;
0068: import org.apache.bcel.generic.IUSHR;
0069: import org.apache.bcel.generic.IXOR;
0070: import org.apache.bcel.generic.IfInstruction;
0071: import org.apache.bcel.generic.Instruction;
0072: import org.apache.bcel.generic.InstructionFactory;
0073: import org.apache.bcel.generic.InstructionHandle;
0074: import org.apache.bcel.generic.InstructionList;
0075: import org.apache.bcel.generic.LADD;
0076: import org.apache.bcel.generic.LAND;
0077: import org.apache.bcel.generic.LCONST;
0078: import org.apache.bcel.generic.LDC;
0079: import org.apache.bcel.generic.LDIV;
0080: import org.apache.bcel.generic.LMUL;
0081: import org.apache.bcel.generic.LNEG;
0082: import org.apache.bcel.generic.LOOKUPSWITCH;
0083: import org.apache.bcel.generic.LOR;
0084: import org.apache.bcel.generic.LREM;
0085: import org.apache.bcel.generic.LRETURN;
0086: import org.apache.bcel.generic.LSHL;
0087: import org.apache.bcel.generic.LSHR;
0088: import org.apache.bcel.generic.LSUB;
0089: import org.apache.bcel.generic.LUSHR;
0090: import org.apache.bcel.generic.LXOR;
0091: import org.apache.bcel.generic.MethodGen;
0092: import org.apache.bcel.generic.NOP;
0093: import org.apache.bcel.generic.POP;
0094: import org.apache.bcel.generic.POP2;
0095: import org.apache.bcel.generic.ReturnInstruction;
0096: import org.apache.bcel.generic.SIPUSH;
0097: import org.apache.bcel.generic.Select;
0098: import org.apache.bcel.generic.TABLESWITCH;
0099: import org.apache.bcel.generic.Type;
0100: import org.apache.bcel.util.ByteSequence;
0101: import org.apache.bcel.util.Repository;
0102: import org.apache.bcel.util.SyntheticRepository;
0103:
0104: /**
0105: * Given a class file can either count the number of possible
0106: * mutation points or perform a mutations. Mutations can be specified by number
0107: * or selected at random.
0108: *
0109: * @author Sean A. Irvine
0110: * @version $Revision:496 $
0111: */
0112: public class Mutater {
0113:
0114: /**
0115: * Maps -1 -> 1; 0 -> 1; 1 -> 0; 2 -> 3; 3 -> 4; 4 -> 5; 5
0116: * -> -1. This mapping is careful to handle use as boolean cases correctly.
0117: */
0118: private static final int[] ICONST_MAP = new int[] { 1, 1, 0, 3, 4,
0119: 5, -1 };
0120:
0121: /**
0122: * Table of mutatable instructions. If defined and not a NOP this gives the
0123: * mutated instruction to use.
0124: */
0125: private final Instruction[] mMutatable = new Instruction[256];
0126: {
0127: mMutatable[Constants.IADD] = new ISUB();
0128: mMutatable[Constants.ISUB] = new IADD();
0129: mMutatable[Constants.IMUL] = new IDIV();
0130: mMutatable[Constants.IDIV] = new IMUL();
0131: mMutatable[Constants.IREM] = new IMUL();
0132: mMutatable[Constants.IAND] = new IOR();
0133: mMutatable[Constants.IOR] = new IAND();
0134: mMutatable[Constants.IXOR] = new IAND();
0135: mMutatable[Constants.ISHL] = new ISHR();
0136: mMutatable[Constants.ISHR] = new ISHL();
0137: mMutatable[Constants.IUSHR] = new ISHL();
0138: mMutatable[Constants.LADD] = new LSUB();
0139: mMutatable[Constants.LSUB] = new LADD();
0140: mMutatable[Constants.LMUL] = new LDIV();
0141: mMutatable[Constants.LDIV] = new LMUL();
0142: mMutatable[Constants.LREM] = new LMUL();
0143: mMutatable[Constants.LAND] = new LOR();
0144: mMutatable[Constants.LOR] = new LAND();
0145: mMutatable[Constants.LXOR] = new LAND();
0146: mMutatable[Constants.LSHL] = new LSHR();
0147: mMutatable[Constants.LSHR] = new LSHL();
0148: mMutatable[Constants.LUSHR] = new LSHL();
0149: mMutatable[Constants.FADD] = new FSUB();
0150: mMutatable[Constants.FSUB] = new FADD();
0151: mMutatable[Constants.FMUL] = new FDIV();
0152: mMutatable[Constants.FDIV] = new FMUL();
0153: mMutatable[Constants.FREM] = new FMUL();
0154: mMutatable[Constants.DADD] = new DSUB();
0155: mMutatable[Constants.DSUB] = new DADD();
0156: mMutatable[Constants.DMUL] = new DDIV();
0157: mMutatable[Constants.DDIV] = new DMUL();
0158: mMutatable[Constants.DREM] = new DMUL();
0159: mMutatable[Constants.IF_ACMPEQ] = new NOP();
0160: mMutatable[Constants.IF_ACMPNE] = new NOP();
0161: mMutatable[Constants.IF_ICMPEQ] = new NOP();
0162: mMutatable[Constants.IF_ICMPGE] = new NOP();
0163: mMutatable[Constants.IF_ICMPGT] = new NOP();
0164: mMutatable[Constants.IF_ICMPLE] = new NOP();
0165: mMutatable[Constants.IF_ICMPLT] = new NOP();
0166: mMutatable[Constants.IF_ICMPNE] = new NOP();
0167: mMutatable[Constants.IFEQ] = new NOP();
0168: mMutatable[Constants.IFGE] = new NOP();
0169: mMutatable[Constants.IFGT] = new NOP();
0170: mMutatable[Constants.IFLE] = new NOP();
0171: mMutatable[Constants.IFLT] = new NOP();
0172: mMutatable[Constants.IFNE] = new NOP();
0173: mMutatable[Constants.IFNONNULL] = new NOP();
0174: mMutatable[Constants.IFNULL] = new NOP();
0175: }
0176:
0177: /** Set of methods to be ignored (i.e. never mutated). */
0178: private Set mIgnored;
0179:
0180: /** Should ICONST instructions be changed. */
0181: private boolean mMutateInlineConstants = false;
0182:
0183: /** Should return instructions be changed. */
0184: private boolean mMutateReturns = false;
0185:
0186: /** Should IINC instructions be changed. */
0187: private boolean mMutateIncrements = false;
0188:
0189: /** Should NEG instructions be changed */
0190: private boolean mMutateNegs = false;
0191:
0192: /** Should SWITCH instructions be changed */
0193: private boolean mMutateSwitch = false;
0194:
0195: /** Should the constant pool be changed. */
0196: private boolean mCPool = false;
0197:
0198: /** The most recent modification. */
0199: private String mModification = null;
0200:
0201: /** Count down for mutation to apply. */
0202: private int mCount = 0;
0203:
0204: //private Repository mRepository = null;
0205: private Repository mRepository = SyntheticRepository.getInstance();
0206:
0207: public Mutater() {
0208: setIgnoredMethods(null);
0209: }
0210:
0211: public Mutater(final int count) {
0212: this ();
0213: setMutationPoint(count);
0214: }
0215:
0216: public void setRepository(Repository repository) {
0217: mRepository = repository;
0218: }
0219:
0220: public void setMutationPoint(final int count) {
0221: mCount = count;
0222: mModification = null;
0223: }
0224:
0225: /**
0226: * Sets whether mutations should be made in the constant pool.
0227: *
0228: * @param v true to mutate the constant pool
0229: */
0230: public void setMutateCPool(final boolean v) {
0231: mCPool = v;
0232: }
0233:
0234: /**
0235: * Sets whether NEG instructions should be mutated.
0236: *
0237: * @param mutateNegs flag indicating whether to mutate NEG instructions.
0238: */
0239: public void setMutateNegs(boolean mutateNegs) {
0240: mMutateNegs = mutateNegs;
0241: final NOP nop = mMutateNegs ? new NOP() : null;
0242: mMutatable[Constants.INEG] = nop;
0243: mMutatable[Constants.DNEG] = nop;
0244: mMutatable[Constants.FNEG] = nop;
0245: mMutatable[Constants.LNEG] = nop;
0246: }
0247:
0248: /**
0249: * Sets whether SWITCH instructions should be mutated.
0250: *
0251: * @param mutateSwitch flag indicating whether to mutate SWITCH instructions.
0252: */
0253: public void setMutateSwitch(boolean mutateSwitch) {
0254: mMutateSwitch = mutateSwitch;
0255: final NOP nop = mMutateSwitch ? new NOP() : null;
0256: mMutatable[Constants.TABLESWITCH] = nop;
0257: mMutatable[Constants.LOOKUPSWITCH] = nop;
0258: }
0259:
0260: public void setMutateIncrements(final boolean v) {
0261: mMutateIncrements = v;
0262: if (mMutateIncrements) {
0263: mMutatable[Constants.IINC] = new NOP();
0264: } else {
0265: mMutatable[Constants.IINC] = null;
0266: }
0267: }
0268:
0269: /**
0270: * Set whether or not inline constants should be mutated.
0271: *
0272: * @param v true for mutation of inline constants
0273: */
0274: public void setMutateInlineConstants(final boolean v) {
0275: mMutateInlineConstants = v;
0276: final NOP nop = mMutateInlineConstants ? new NOP() : null;
0277: mMutatable[Constants.ICONST_0] = nop;
0278: mMutatable[Constants.ICONST_1] = nop;
0279: mMutatable[Constants.ICONST_2] = nop;
0280: mMutatable[Constants.ICONST_3] = nop;
0281: mMutatable[Constants.ICONST_4] = nop;
0282: mMutatable[Constants.ICONST_5] = nop;
0283: mMutatable[Constants.ICONST_M1] = nop;
0284: mMutatable[Constants.FCONST_0] = nop;
0285: mMutatable[Constants.FCONST_1] = nop;
0286: mMutatable[Constants.FCONST_2] = nop;
0287: mMutatable[Constants.DCONST_0] = nop;
0288: mMutatable[Constants.DCONST_1] = nop;
0289: mMutatable[Constants.LCONST_0] = nop;
0290: mMutatable[Constants.LCONST_1] = nop;
0291: mMutatable[Constants.BIPUSH] = nop;
0292: mMutatable[Constants.SIPUSH] = nop;
0293: }
0294:
0295: /**
0296: * Set whether or not return values should be mutated.
0297: *
0298: * @param v true to mutate return values
0299: */
0300: public void setMutateReturnValues(final boolean v) {
0301: mMutateReturns = v;
0302: final NOP nop = mMutateReturns ? new NOP() : null;
0303: mMutatable[Constants.ARETURN] = nop;
0304: mMutatable[Constants.DRETURN] = nop;
0305: mMutatable[Constants.FRETURN] = nop;
0306: mMutatable[Constants.IRETURN] = nop;
0307: mMutatable[Constants.LRETURN] = nop;
0308: }
0309:
0310: private static boolean checkAssertInstruction(
0311: final ConstantPoolGen cpg, final Instruction ins) {
0312: return ins instanceof INVOKEVIRTUAL
0313: && "desiredAssertionStatus"
0314: .equals(((INVOKEVIRTUAL) ins)
0315: .getMethodName(cpg));
0316: }
0317:
0318: /**
0319: * Is this an instruction we know how to mutate? Needs the entire chain since
0320: * in rare cases we need to examine context to see if mutation is allowable.
0321: * Returns the number of mutation points in the instruction (this can be
0322: * bigger than 1 (e.g. switch statements).
0323: *
0324: * @param ihs current instruction chain
0325: * @param offset position in chain
0326: * @param cpg constant pool
0327: * @return number of mutation points in the given instruction
0328: */
0329: private int isMutatable(final InstructionHandle[] ihs,
0330: final int offset, final ConstantPoolGen cpg) {
0331: final Instruction i = ihs[offset].getInstruction();
0332:
0333: // handle general mutability
0334: if (mMutatable[i.getOpcode()] == null) {
0335: return 0;
0336: }
0337:
0338: // handle special situation of .class invocations
0339: if (i instanceof ICONST && offset < ihs.length - 1) {
0340: final Instruction context = ihs[offset + 1]
0341: .getInstruction();
0342: if (context instanceof INVOKESTATIC
0343: && "class".equals(((INVOKESTATIC) context)
0344: .getMethodName(cpg))) {
0345: return 0;
0346: }
0347: }
0348:
0349: // handle special situation of .desiredAssertionStatus invocations
0350: // javac 1.5
0351: if (i instanceof ICONST) {
0352: if (offset >= 2
0353: && ((ICONST) i).getValue().intValue() == 1
0354: && checkAssertInstruction(cpg, ihs[offset - 2]
0355: .getInstruction())) {
0356: return 0;
0357: }
0358: if (offset >= 4
0359: && ((ICONST) i).getValue().intValue() == 0
0360: && checkAssertInstruction(cpg, ihs[offset - 4]
0361: .getInstruction())) {
0362: return 0;
0363: }
0364: }
0365: if (i instanceof IFNE
0366: && offset >= 1
0367: && checkAssertInstruction(cpg, ihs[offset - 1]
0368: .getInstruction())) {
0369: return 0;
0370: }
0371:
0372: // switch statements have multiple points
0373: if (i instanceof Select) {
0374: return ((Select) i).getMatchs().length;
0375: }
0376:
0377: // everything else 1 point
0378: return 1;
0379: }
0380:
0381: /**
0382: * Skip to the next valid instruction to examine. The primary reason for this
0383: * function is to attempt to skip over assertions.
0384: */
0385: private static int skipAhead(final InstructionHandle[] ihs,
0386: final ConstantPoolGen cp, int j) {
0387: final Instruction i = ihs[j++].getInstruction();
0388: if (i instanceof GETSTATIC) {
0389: final GETSTATIC gs = (GETSTATIC) i;
0390: if (gs.getFieldName(cp).equals("$noassert")
0391: || gs.getFieldName(cp).equals("assert")
0392: || gs.getFieldName(cp)
0393: .equals("$assertionsDisabled")) {
0394: // attempt to skip over a java 1.4 assert() statement
0395: // this works for code generated by jikes
0396: // $assertionsDisabled is used by javac 1.5
0397: // skip forwards to a ATHROW instruction, most likely it ends the assert
0398: while (!(ihs[j++].getInstruction() instanceof ATHROW)) {
0399: ; // do nothing
0400: }
0401: } else if (gs.getFieldName(cp).indexOf("class$") != -1) {
0402: // attempt to skip a ".class" reference (because it has a ifnonnull
0403: // test)
0404: if (ihs[j + 1].getInstruction() instanceof IFNONNULL) {
0405: j += 2;
0406: }
0407: }
0408: }
0409:
0410: return j;
0411: }
0412:
0413: /**
0414: * Set the names of all the methods to be ignored during mutation. Any method
0415: * named by a member of the given set will not be subject to mutation.
0416: *
0417: * @param ignore
0418: * Set of ignored methods
0419: */
0420: public void setIgnoredMethods(final Set ignore) {
0421: mIgnored = ignore == null ? new HashSet() : ignore;
0422: }
0423:
0424: private boolean checkNormalMethod(final Method m) {
0425: return m != null && !m.isNative()
0426: && !m.isAbstract()
0427: && !mIgnored.contains(m.getName())
0428: && m.getName().indexOf("access$") == -1
0429: // This next one appears to be how the Eclipse compiler handles enums, it is
0430: // the equivalent of the synthetic class generated by javac
0431: && m.getName().indexOf("$SWITCH_TABLE$") == -1
0432: /* && m.getLineNumberTable() != null */&& m.getCode() != null;
0433: /* && m.getLineNumberTable().getSourceLine(0) > 0; */
0434: }
0435:
0436: /** Records the first line in the code that uses a constant. */
0437: private int[] mConstantFirstRef = null;
0438:
0439: private void initConstantRef(final Method[] methods,
0440: final String className, final ConstantPoolGen cp) {
0441: if (mConstantFirstRef == null) {
0442: mConstantFirstRef = new int[cp.getSize()];
0443: Arrays.fill(mConstantFirstRef, -1);
0444: if (methods != null) {
0445: for (int i = 0; i < methods.length; i++) {
0446: final Method m = methods[i];
0447: if (checkNormalMethod(m)) {
0448: final InstructionList il = new MethodGen(m,
0449: className, cp).getInstructionList();
0450: if (il != null) {
0451: final InstructionHandle[] ihs = il
0452: .getInstructionHandles();
0453: for (int j = 0; j < ihs.length; j++) {
0454: final Instruction ins = ihs[j]
0455: .getInstruction();
0456: if (ins instanceof CPInstruction) {
0457: // skip those which are messages for Assertion Error
0458: if (ins instanceof LDC
0459: && j + 1 < ihs.length) {
0460: final Instruction i2 = ihs[j + 1]
0461: .getInstruction();
0462: if (i2 instanceof INVOKESPECIAL
0463: && ((INVOKESPECIAL) i2)
0464: .getReferenceType(
0465: cp)
0466: .toString()
0467: .equals(
0468: "java.lang.AssertionError")) {
0469: continue;
0470: }
0471: }
0472: final int index = ((CPInstruction) ins)
0473: .getIndex();
0474: if (mConstantFirstRef[index] == -1) {
0475: mConstantFirstRef[index] = (m
0476: .getLineNumberTable() != null ? m
0477: .getLineNumberTable()
0478: .getSourceLine(
0479: ihs[j]
0480: .getPosition())
0481: : 0);
0482: }
0483: }
0484: }
0485: }
0486: }
0487: }
0488: }
0489: }
0490: }
0491:
0492: /**
0493: * Test if a constant in the pool is mutatable.
0494: */
0495: private boolean isMutatable(final Constant c, final int i) {
0496: return mConstantFirstRef[i] != -1
0497: && c != null
0498: && (c instanceof ConstantString
0499: || c instanceof ConstantLong
0500: || c instanceof ConstantInteger
0501: || c instanceof ConstantFloat || c instanceof ConstantDouble);
0502: }
0503:
0504: /**
0505: * Count the number of mutation points in the constant pool.
0506: */
0507: private int countMutationPoints(final Method[] methods,
0508: final String className, final ConstantPoolGen cp) {
0509: initConstantRef(methods, className, cp);
0510: int count = 0;
0511: for (int i = 0; i < cp.getSize(); i++) {
0512: if (isMutatable(cp.getConstant(i), i)) {
0513: count++;
0514: }
0515: }
0516: return count;
0517: }
0518:
0519: /**
0520: * Count number of mutation points in a method.
0521: */
0522: private int countMutationPoints(final Method m,
0523: final String className, final ConstantPoolGen cp) {
0524: // check this is a method that it makes sense to mutate
0525: if (!checkNormalMethod(m)) {
0526: return 0;
0527: }
0528: final InstructionList il = new MethodGen(m, className, cp)
0529: .getInstructionList();
0530: final InstructionHandle[] ihs = il.getInstructionHandles();
0531: int count = 0;
0532: for (int j = 0; j < ihs.length; j = skipAhead(ihs, cp, j)) {
0533: count += isMutatable(ihs, j, cp);
0534: }
0535: il.dispose();
0536: return count;
0537: }
0538:
0539: /*
0540: * Look for the special case of a synthetic class used to support a
0541: * switch statement on an Enum. These classes are just an automatically
0542: * generated mapping between Enum ordinals and values in the switch
0543: * and it doesn't really make sense for them to be unit tested.
0544: */
0545: private boolean isSwitchClass(final String cl,
0546: final ConstantPool cpool) {
0547: if (cl.indexOf('$') == -1) {
0548: return false;
0549: }
0550: for (int i = 0; i < cpool.getLength(); i++) {
0551: final Constant c = cpool.getConstant(i);
0552: if (c instanceof ConstantNameAndType
0553: && ((ConstantNameAndType) c).getName(cpool)
0554: .startsWith("$SwitchMap")) {
0555: return true;
0556: }
0557: }
0558: return false;
0559: }
0560:
0561: /**
0562: * Compute the total number of possible mutation points in the class.
0563: */
0564: public int countMutationPoints(final String cl)
0565: throws ClassNotFoundException {
0566: final String className = fixName(cl);
0567: final JavaClass clazz = lookupClass(className);
0568:
0569: if (clazz == null) {
0570: return -1;
0571: }
0572: // if is an interface, return -1 to distinguish from 0 point classes
0573: if (clazz.isInterface()) {
0574: return -1;
0575: }
0576:
0577: final Method[] methods = clazz.getMethods();
0578: final ConstantPool cpool = clazz.getConstantPool();
0579:
0580: // check for synthetic class used by Enums
0581: if (isSwitchClass(cl, cpool)) {
0582: return 0;
0583: }
0584:
0585: final ConstantPoolGen cp = new ConstantPoolGen(cpool);
0586:
0587: int count = mCPool ? countMutationPoints(methods, className, cp)
0588: : 0;
0589: for (int i = 0; i < methods.length; i++) {
0590: count += countMutationPoints(methods[i], className, cp);
0591: }
0592: return count;
0593: }
0594:
0595: /** Mutate an ICONST instruction. */
0596: private static Instruction mutateICONST(final ICONST i,
0597: final ConstantPoolGen cp) {
0598: return new ICONST(ICONST_MAP[i.getValue().intValue() + 1]);
0599: }
0600:
0601: /** Mutate a FCONST instruction. */
0602: private static Instruction mutateFCONST(final FCONST i,
0603: final ConstantPoolGen cp) {
0604: final float v = i.getValue().floatValue();
0605: if (v == 0.0F) {
0606: return new FCONST(1.0F);
0607: } else {
0608: return new FCONST(0.0F);
0609: }
0610: }
0611:
0612: /** Mutate a DCONST instruction. */
0613: private static Instruction mutateDCONST(final DCONST i,
0614: final ConstantPoolGen cp) {
0615: final double v = i.getValue().doubleValue();
0616: if (v == 0.0) {
0617: return new DCONST(1.0);
0618: } else {
0619: return new DCONST(0.0);
0620: }
0621: }
0622:
0623: /** Mutate a LCONST instruction. */
0624: private static Instruction mutateLCONST(final LCONST i,
0625: final ConstantPoolGen cp) {
0626: final long v = i.getValue().longValue();
0627: if (v == 0L) {
0628: return new LCONST(1L);
0629: } else {
0630: return new LCONST(0L);
0631: }
0632: }
0633:
0634: /** Mutate a BIPUSH instruction. */
0635: private static Instruction mutateBIPUSH(final BIPUSH i,
0636: final ConstantPoolGen cp) {
0637: return new BIPUSH((byte) (i.getValue().byteValue() + 1));
0638: }
0639:
0640: /** Mutate a SIPUSH instruction. */
0641: private static Instruction mutateSIPUSH(final SIPUSH i,
0642: final ConstantPoolGen cp) {
0643: return new SIPUSH((byte) (i.getValue().shortValue() + 1));
0644: }
0645:
0646: /** Mutate an IINC instruction */
0647: private static Instruction mutateIINC(final IINC i,
0648: final ConstantPoolGen cp) {
0649: return new IINC(i.getIndex(), -i.getIncrement());
0650: }
0651:
0652: /**
0653: * Return a new integer instruction with the same parameter, but which differs
0654: * from the current instruction.
0655: */
0656: private Instruction mutateIntegerArithmetic(
0657: final ArithmeticInstruction current,
0658: final ConstantPoolGen cp) {
0659: return mMutatable[current.getOpcode()];
0660: }
0661:
0662: private InstructionList mutateRETURN(final ReturnInstruction ret,
0663: final InstructionFactory ifactory) {
0664: final InstructionList il = new InstructionList();
0665: if (ret instanceof IRETURN) {
0666: // maps 0->1 and anything else to 0, this is done without need
0667: // of any more stack space.
0668: final IFEQ ifeq = new IFEQ(null);
0669: il.append(ifeq);
0670: il.append(new ICONST(0));
0671: il.append(new IRETURN());
0672: il.append(new ICONST(1));
0673: ifeq.setTarget(il.getEnd());
0674: } else if (ret instanceof LRETURN) {
0675: // +1L
0676: il.append(new LCONST(1));
0677: il.append(new LADD());
0678: } else if (ret instanceof FRETURN) {
0679: // The following is complicated by the problem of NaNs. By default
0680: // the new value is -(x + 1), but this doesn't work for NaNs. But
0681: // for a NaN x != x is true, and we use this to detect them.
0682: il.append(new DUP());
0683: il.append(new DUP());
0684: il.append(new FCMPG());
0685: final IFEQ ifeq = new IFEQ(null);
0686: il.append(ifeq);
0687: il.append(new POP());
0688: il.append(new FCONST(0));
0689: il.append(new FCONST(1));
0690: ifeq.setTarget(il.getEnd());
0691: il.append(new FADD());
0692: il.append(new FNEG());
0693: } else if (ret instanceof DRETURN) {
0694: // The following is complicated by the problem of NaNs. By default
0695: // the new value is -(x + 1), but this doesn't work for NaNs. But
0696: // for a NaN x != x is true, and we use this to detect them.
0697: il.append(new DUP2());
0698: il.append(new DUP2());
0699: il.append(new DCMPG());
0700: final IFEQ ifeq = new IFEQ(null);
0701: il.append(ifeq);
0702: il.append(new POP2());
0703: il.append(new DCONST(0));
0704: il.append(new DCONST(1));
0705: ifeq.setTarget(il.getEnd());
0706: il.append(new DADD());
0707: il.append(new DNEG());
0708: } else if (ret instanceof ARETURN) {
0709: // if result is non-null make it null, otherwise hard case
0710: // for moment throw runtime exception
0711: final IFNONNULL ifnonnull = new IFNONNULL(null);
0712: il.append(ifnonnull);
0713: il.append(ifactory.createNew("java.lang.RuntimeException"));
0714: il.append(new DUP());
0715: il.append(ifactory.createInvoke(
0716: "java.lang.RuntimeException", "<init>", Type.VOID,
0717: new Type[0], Constants.INVOKESPECIAL));
0718: il.append(new ATHROW());
0719: il.append(new ACONST_NULL());
0720: ifnonnull.setTarget(il.getEnd());
0721: }
0722: return il;
0723: }
0724:
0725: /**
0726: * Produce a human description of an instruction.
0727: *
0728: * @param i
0729: * the instruction
0730: * @return description
0731: */
0732: private String describe(final Instruction i) {
0733: if (i instanceof IADD || i instanceof LADD || i instanceof FADD
0734: || i instanceof DADD) {
0735: return "+";
0736: }
0737: if (i instanceof ISUB || i instanceof LSUB || i instanceof FSUB
0738: || i instanceof DSUB) {
0739: return "-";
0740: }
0741: if (i instanceof IMUL || i instanceof LMUL || i instanceof FMUL
0742: || i instanceof DMUL) {
0743: return "*";
0744: }
0745: if (i instanceof IDIV || i instanceof LDIV || i instanceof FDIV
0746: || i instanceof DDIV) {
0747: return "/";
0748: }
0749: if (i instanceof IREM || i instanceof LREM || i instanceof FREM
0750: || i instanceof DREM) {
0751: return "%";
0752: }
0753: if (i instanceof IOR || i instanceof LOR) {
0754: return "|";
0755: }
0756: if (i instanceof IXOR || i instanceof LXOR) {
0757: return "^";
0758: }
0759: if (i instanceof IAND || i instanceof LAND) {
0760: return "&";
0761: }
0762: if (i instanceof ISHL || i instanceof LSHL) {
0763: return "<<";
0764: }
0765: if (i instanceof ISHR || i instanceof LSHR) {
0766: return ">>";
0767: }
0768: if (i instanceof IUSHR || i instanceof LUSHR) {
0769: return ">>>";
0770: }
0771: if (i instanceof ICONST) {
0772: return ((ICONST) i).getValue().toString();
0773: }
0774: if (i instanceof FCONST) {
0775: return ((FCONST) i).getValue().toString() + "F";
0776: }
0777: if (i instanceof DCONST) {
0778: return ((DCONST) i).getValue().toString() + "D";
0779: }
0780: if (i instanceof LCONST) {
0781: return ((LCONST) i).getValue().toString() + "L";
0782: }
0783: if (i instanceof BIPUSH) {
0784: final byte b = ((BIPUSH) i).getValue().byteValue();
0785: if (b >= ' ' && b <= '~') {
0786: return (b + " (" + (char) b + ")");
0787: }
0788: return "" + b;
0789: }
0790: if (i instanceof SIPUSH) {
0791: return ((SIPUSH) i).getValue().toString();
0792: }
0793: if (i instanceof ReturnInstruction) {
0794: return "changed return value (" + i.getName() + ")";
0795: }
0796:
0797: if (i instanceof IINC) {
0798: if (((IINC) i).getIncrement() >= 0) {
0799: return "+=";
0800: } else {
0801: return "-=";
0802: }
0803: }
0804: return "unknown";
0805: }
0806:
0807: /**
0808: * Return the most recent modification.
0809: *
0810: * @return description of modification
0811: */
0812: public String getModification() {
0813: return mModification;
0814: }
0815:
0816: private double mutateDouble(final double current) {
0817: // treatment of reals is complicated by potential underflow and the
0818: // special values like the infinities
0819: return Double.isNaN(current) || Double.isInfinite(current) ? 0
0820: : 2 * current + (current >= 0 ? 1 : -1);
0821: }
0822:
0823: /**
0824: * Handle mutations of the constant pool.
0825: */
0826: private void mutateConstant(final String className,
0827: final ConstantPoolGen cp, int i) {
0828: final Constant c = cp.getConstant(i);
0829: String mod = className + ":" + mConstantFirstRef[i] + ": CP["
0830: + i + "] ";
0831: if (c instanceof ConstantString) {
0832: // in this case need to actually step to the UTF8 constant for the string
0833: final int index = ((ConstantString) c).getStringIndex();
0834: final ConstantUtf8 utf = (ConstantUtf8) cp
0835: .getConstant(index);
0836: final String current = utf.getBytes();
0837: if ("__jumble__".equals(current)) {
0838: cp.setConstant(index, new ConstantUtf8("__jumble__"));
0839: mod = mod + "\"" + current + "\" -> \"__jumble__\"";
0840: } else {
0841: cp.setConstant(index, new ConstantUtf8("___jumble___"));
0842: mod = mod + "\"" + current + "\" -> \"___jumble___\"";
0843: }
0844: } else if (c instanceof ConstantLong) {
0845: final long current = ((ConstantLong) c).getBytes();
0846: cp.setConstant(i, new ConstantLong(current + 1));
0847: mod = mod + current + " -> " + (current + 1);
0848: } else if (c instanceof ConstantInteger) {
0849: final int current = ((ConstantInteger) c).getBytes();
0850: cp.setConstant(i, new ConstantInteger(current + 1));
0851: mod = mod + current + " -> " + (current + 1);
0852: } else if (c instanceof ConstantFloat) {
0853: final float current = ((ConstantFloat) c).getBytes();
0854: final float newValue = (float) mutateDouble(current);
0855: cp.setConstant(i, new ConstantFloat(newValue));
0856: mod = mod + current + " -> " + newValue;
0857: } else if (c instanceof ConstantDouble) {
0858: final double current = ((ConstantDouble) c).getBytes();
0859: final double newValue = mutateDouble(current);
0860: cp.setConstant(i, new ConstantDouble(newValue));
0861: mod = mod + current + " -> " + newValue;
0862: }
0863: mModification = mod;
0864: }
0865:
0866: private int jumble(Method[] methods, int methodidx,
0867: final String className, final ConstantPoolGen cp, int count) {
0868:
0869: // check if modification is appropriate
0870: Method m = methods[methodidx];
0871: if (count < 0 || !checkNormalMethod(m)) {
0872: return count;
0873: }
0874: final MethodGen mg = new MethodGen(m, className, cp);
0875: final InstructionList il = mg.getInstructionList();
0876: final InstructionHandle[] ihs = il.getInstructionHandles();
0877: final InstructionFactory ifactory = new InstructionFactory(cp);
0878:
0879: for (int j = 0; j < ihs.length; j = skipAhead(ihs, cp, j)) {
0880: final Instruction i = ihs[j].getInstruction();
0881: // TODO needs modification to support SWITCH
0882: final int points = isMutatable(ihs, j, cp);
0883: if (points != 0 && (count -= points) < 0) {
0884: // not count is < -1 only for a few instructions like TABLESWITCH
0885: int lineNumber = (m.getLineNumberTable() != null ? m
0886: .getLineNumberTable().getSourceLine(
0887: ihs[j].getPosition()) : 0);
0888: StringBuffer mod = new StringBuffer(className).append(
0889: ":").append(lineNumber).append(": ");
0890: if (i instanceof IfInstruction) {
0891: mod.append("negated conditional");
0892: ihs[j].setInstruction(((IfInstruction) i).negate());
0893: } else if (i instanceof INEG || i instanceof DNEG
0894: || i instanceof FNEG || i instanceof LNEG) {
0895: // Negation instruction
0896: mod.append("removed negation");
0897: ihs[j].setInstruction(new NOP());
0898: } else if (i instanceof ArithmeticInstruction) {
0899: // binary operand integer instruction
0900: final Instruction inew = mutateIntegerArithmetic(
0901: (ArithmeticInstruction) i, cp);
0902: ihs[j].setInstruction(inew);
0903: mod.append(describe(i) + " -> " + describe(inew));
0904: } else if (i instanceof ReturnInstruction) {
0905: mod.append(describe(i));
0906: il.insert(ihs[j], mutateRETURN(
0907: (ReturnInstruction) i, ifactory));
0908: } else if (i instanceof Select) {
0909: final Select select = (Select) i;
0910: final int index = -1 - count;
0911: // mutate by swapping target with default target, this is better than
0912: // swapping the case value itself because sometimes multiple cases
0913: // will branch to the same code
0914: final int[] matches = select.getMatchs();
0915: final InstructionHandle[] handles = select
0916: .getTargets();
0917: final InstructionHandle newDefHandle = handles[index];
0918: final InstructionHandle oldDefHandle = select
0919: .getTarget();
0920: if (newDefHandle == oldDefHandle) {
0921: // need to try harder to find a case we can swap with
0922: for (int k = 0; k < matches.length; k++) {
0923: if (k != index
0924: && newDefHandle != handles[k]) {
0925: mod.append("switched case "
0926: + matches[index]
0927: + " with case " + k);
0928: handles[index] = handles[k];
0929: handles[k] = newDefHandle;
0930: if (select instanceof TABLESWITCH) {
0931: ihs[j]
0932: .setInstruction(new TABLESWITCH(
0933: matches, handles,
0934: oldDefHandle));
0935: } else {
0936: ihs[j]
0937: .setInstruction(new LOOKUPSWITCH(
0938: matches, handles,
0939: oldDefHandle));
0940: }
0941: break;
0942: }
0943: }
0944: // still didn't find an option, just mutate the case value itself
0945: mod.append("switched case " + matches[index]
0946: + " -> " + ++matches[index]);
0947: if (select instanceof TABLESWITCH) {
0948: ihs[j].setInstruction(new TABLESWITCH(
0949: matches, handles, oldDefHandle));
0950: } else {
0951: ihs[j].setInstruction(new LOOKUPSWITCH(
0952: matches, handles, oldDefHandle));
0953: }
0954: } else {
0955: handles[index] = oldDefHandle;
0956: mod.append("switched case " + matches[index]
0957: + " with default case");
0958: if (select instanceof TABLESWITCH) {
0959: ihs[j].setInstruction(new TABLESWITCH(
0960: matches, handles, newDefHandle));
0961: } else {
0962: ihs[j].setInstruction(new LOOKUPSWITCH(
0963: matches, handles, newDefHandle));
0964: }
0965: }
0966: } else {
0967: final Instruction inew;
0968: if (i instanceof ICONST) {
0969: inew = mutateICONST((ICONST) i, cp);
0970: } else if (i instanceof FCONST) {
0971: inew = mutateFCONST((FCONST) i, cp);
0972: } else if (i instanceof DCONST) {
0973: inew = mutateDCONST((DCONST) i, cp);
0974: } else if (i instanceof LCONST) {
0975: inew = mutateLCONST((LCONST) i, cp);
0976: } else if (i instanceof BIPUSH) {
0977: inew = mutateBIPUSH((BIPUSH) i, cp);
0978: } else if (i instanceof SIPUSH) {
0979: inew = mutateSIPUSH((SIPUSH) i, cp);
0980: } else if (i instanceof IINC) {
0981: inew = mutateIINC((IINC) i, cp);
0982: } else {
0983: inew = null;
0984: }
0985: if (inew != null) {
0986: ihs[j].setInstruction(inew);
0987: mod.append(describe(i) + " -> "
0988: + describe(inew));
0989: }
0990: }
0991: mModification = mod.toString();
0992: //System.err.println("Made modification: " + mModification);
0993: break;
0994: }
0995: }
0996: //Remove LVTT attribute to fix LVTT class loading error.
0997: Attribute[] attribs = mg.getCodeAttributes();
0998: for (Attribute a : attribs) {
0999: if (a instanceof Unknown
1000: && ((Unknown) a).getName().equals(
1001: "LocalVariableTypeTable")) {
1002: mg.removeCodeAttribute(a);
1003: }
1004: }
1005:
1006: mg.setMaxStack(); // this is needed for the return mods
1007: methods[methodidx] = mg.getMethod();
1008: il.dispose();
1009: return count;
1010: }
1011:
1012: public JavaClass jumbler(String cn) throws ClassNotFoundException {
1013: JavaClass clazz = mRepository.loadClass(cn);
1014: return jumbler(clazz);
1015: }
1016:
1017: public JavaClass jumbler(final JavaClass clazz) {
1018: JavaClass ret = clazz.copy();
1019:
1020: Method[] methods = ret.getMethods();
1021: ConstantPoolGen cp = new ConstantPoolGen(ret.getConstantPool());
1022: int count = mCount;
1023: if (mCPool) {
1024: // first deal with constant pool
1025: initConstantRef(methods, ret.getClassName(), cp);
1026: for (int i = 0; i < cp.getSize(); i++) {
1027: if (isMutatable(cp.getConstant(i), i) && count-- == 0) {
1028: mutateConstant(ret.getClassName(), cp, i);
1029: }
1030: }
1031: }
1032: for (int i = 0; i < methods.length; i++) {
1033: count = jumble(methods, i, ret.getClassName(), cp, count);
1034: }
1035: ret.setConstantPool(cp.getFinalConstantPool());
1036: /*
1037: String s1 = printClass(clazz);
1038: String s2 = printClass(ret);
1039: if (!s1.equals(s2)) {
1040: System.err.println("==== Original class ====\n" + s1);
1041: System.err.println("==== Modified class ====\n" + s2);
1042: System.err.println("====");
1043: } else {
1044: System.err.println("==== No modification made ====");
1045: }
1046: */
1047: return ret;
1048: }
1049:
1050: protected static String printClass(JavaClass c) {
1051: StringBuffer sb = new StringBuffer();
1052: try {
1053: Method[] m = c.getMethods();
1054: for (int i = 0; i < m.length; i++) {
1055: sb.append(m[i].getName()).append("\n");
1056: ByteSequence code = new ByteSequence(m[i].getCode()
1057: .getCode());
1058: while (code.available() > 0) {
1059: sb.append("\t").append(
1060: Instruction.readInstruction(code)).append(
1061: "\n");
1062: }
1063: }
1064: } catch (Throwable e) {
1065: sb.append("Couldn't print class").append("\n");
1066: }
1067: return sb.toString();
1068: }
1069:
1070: /**
1071: * Gets the name of the method currently being mutated for the given class.
1072: *
1073: * @param cl
1074: * the name of the class to mutate
1075: * @return mutated method name
1076: */
1077: public String getMutatedMethodName(String cl)
1078: throws ClassNotFoundException {
1079: final String className = fixName(cl);
1080: final JavaClass clazz = lookupClass(className);
1081:
1082: if (clazz == null) {
1083: System.out
1084: .println("Error: could not retrieve " + className);
1085: return null;
1086: }
1087:
1088: final Method[] methods = clazz.getMethods();
1089: final ConstantPool cpool = clazz.getConstantPool();
1090: final ConstantPoolGen cp = new ConstantPoolGen(cpool);
1091: int count = mCPool ? countMutationPoints(methods, className, cp)
1092: : 0;
1093: for (int i = 0; i < methods.length; i++) {
1094: count += countMutationPoints(methods[i], className, cp);
1095:
1096: // Once we have gone past the mutation point,
1097: // then we have found the mutated method
1098: if (mCount < count) {
1099: return methods[i].getName() + methods[i].getSignature();
1100: }
1101: }
1102:
1103: // If we get here, then something went wrong
1104: throw new RuntimeException("Invalid mutation point");
1105: }
1106:
1107: private JavaClass lookupClass(String className) {
1108: try {
1109: JavaClass clazz = mRepository.findClass(className);
1110:
1111: if (clazz == null) {
1112: return mRepository.loadClass(className);
1113: } else {
1114: return clazz;
1115: }
1116: } catch (ClassNotFoundException ex) {
1117: return null;
1118: }
1119: }
1120:
1121: /**
1122: * Gets the mutation point, relative to the method being mutated. The method
1123: * is specified by <CODE>getMutatedMethodName(cl)</CODE>.
1124: *
1125: * @param cl
1126: * the class to to mutate.
1127: * @return the mutation point, relative to the mutated method.
1128: */
1129: public int getMethodRelativeMutationPoint(String cl)
1130: throws ClassNotFoundException {
1131: final String className = fixName(cl);
1132: final JavaClass clazz = lookupClass(className);
1133:
1134: if (clazz == null) {
1135: return -1;
1136: }
1137:
1138: final Method[] methods = clazz.getMethods();
1139: final ConstantPool cpool = clazz.getConstantPool();
1140: final ConstantPoolGen cp = new ConstantPoolGen(cpool);
1141: int count = mCPool ? countMutationPoints(methods, className, cp)
1142: : 0;
1143: for (int i = 0; i < methods.length; i++) {
1144: int oldCount = count;
1145: count += countMutationPoints(methods[i], className, cp);
1146: // Once we have gone past the mutation point,
1147: // then we have found the mutated method
1148: if (mCount < count) {
1149: return mCount - oldCount;
1150: }
1151: }
1152:
1153: // If we get here, then something went wrong
1154: throw new RuntimeException("Invalid mutation point");
1155: }
1156:
1157: /**
1158: * Lop off .class or .java from a string.
1159: *
1160: * @param className
1161: * name of the class
1162: * @return class name without extension
1163: */
1164: private static String fixName(final String className) {
1165: if (className.endsWith(".class")) {
1166: return className.substring(0, className.length() - 6)
1167: .replace('/', '.');
1168: } else if (className.endsWith(".java")) {
1169: return className.substring(0, className.length() - 5)
1170: .replace('/', '.');
1171: } else {
1172: return className.replace('/', '.');
1173: }
1174: }
1175:
1176: }
|