CodePreverifier.java revision b9cc48a43ed984587c939d02fba5316bf5c0df6e
1/* 2 * ProGuard -- shrinking, optimization, obfuscation, and preverification 3 * of Java bytecode. 4 * 5 * Copyright (c) 2002-2013 Eric Lafortune (eric@graphics.cornell.edu) 6 * 7 * This program is free software; you can redistribute it and/or modify it 8 * under the terms of the GNU General Public License as published by the Free 9 * Software Foundation; either version 2 of the License, or (at your option) 10 * any later version. 11 * 12 * This program is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 15 * more details. 16 * 17 * You should have received a copy of the GNU General Public License along 18 * with this program; if not, write to the Free Software Foundation, Inc., 19 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 20 */ 21package proguard.preverify; 22 23import proguard.classfile.*; 24import proguard.classfile.attribute.*; 25import proguard.classfile.attribute.preverification.*; 26import proguard.classfile.attribute.visitor.AttributeVisitor; 27import proguard.classfile.editor.*; 28import proguard.classfile.instruction.*; 29import proguard.classfile.util.SimplifiedVisitor; 30import proguard.classfile.visitor.*; 31import proguard.evaluation.*; 32import proguard.evaluation.value.*; 33import proguard.optimize.evaluation.*; 34 35import java.util.*; 36 37/** 38 * This class can preverify methods in program class pools, according to a given 39 * specification. 40 * 41 * @author Eric Lafortune 42 */ 43public class CodePreverifier 44extends SimplifiedVisitor 45implements AttributeVisitor 46{ 47 //* 48 private static final boolean DEBUG = false; 49 /*/ 50 private static boolean DEBUG = true; 51 //*/ 52 53 54 private final boolean microEdition; 55 56 private final PartialEvaluator partialEvaluator = new PartialEvaluator(); 57 private final LivenessAnalyzer livenessAnalyzer = new LivenessAnalyzer(partialEvaluator); 58 private final CodeAttributeEditor codeAttributeEditor = new CodeAttributeEditor(); 59 60 61 /** 62 * Creates a new CodePreverifier. 63 */ 64 public CodePreverifier(boolean microEdition) 65 { 66 this.microEdition = microEdition; 67 } 68 69 70 // Implementations for AttributeVisitor. 71 72 public void visitAnyAttribute(Clazz clazz, Attribute attribute) {} 73 74 75 public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute) 76 { 77 // TODO: Remove this when the preverifier has stabilized. 78 // Catch any unexpected exceptions from the actual visiting method. 79 try 80 { 81 // Process the code. 82 visitCodeAttribute0(clazz, method, codeAttribute); 83 } 84 catch (RuntimeException ex) 85 { 86 System.err.println("Unexpected error while preverifying:"); 87 System.err.println(" Class = ["+clazz.getName()+"]"); 88 System.err.println(" Method = ["+method.getName(clazz)+method.getDescriptor(clazz)+"]"); 89 System.err.println(" Exception = ["+ex.getClass().getName()+"] ("+ex.getMessage()+")"); 90 91 throw ex; 92 } 93 } 94 95 96 public void visitCodeAttribute0(Clazz clazz, Method method, CodeAttribute codeAttribute) 97 { 98// DEBUG = 99// clazz.getName().equals("abc/Def") && 100// method.getName(clazz).equals("abc"); 101 102 ProgramClass programClass = (ProgramClass)clazz; 103 ProgramMethod programMethod = (ProgramMethod)method; 104 105 int codeLength = codeAttribute.u4codeLength; 106 107 // Evaluate the method. 108 //partialEvaluator.visitCodeAttribute(clazz, method, codeAttribute); 109 livenessAnalyzer.visitCodeAttribute(clazz, method, codeAttribute); 110 111 // We may have to remove unreachable code. 112 codeAttributeEditor.reset(codeLength); 113 114 // Collect the stack map frames. 115 List stackMapFrameList = new ArrayList(); 116 117 for (int offset = 0; offset < codeLength; offset++) 118 { 119 // Only store frames at the beginning of code blocks. 120 if (!partialEvaluator.isTraced(offset)) 121 { 122 // Mark the unreachable instruction for deletion. 123 codeAttributeEditor.deleteInstruction(offset); 124 } 125 else if (partialEvaluator.isBranchOrExceptionTarget(offset)) 126 { 127 // Convert the variable values to types. 128 VerificationType[] variableTypes = 129 correspondingVerificationTypes(programClass, 130 programMethod, 131 codeAttribute, 132 offset, 133 partialEvaluator.getVariablesBefore(offset)); 134 135 // Convert the stack values to types. 136 VerificationType[] stackTypes = 137 correspondingVerificationTypes(programClass, 138 programMethod, 139 codeAttribute, 140 offset, 141 partialEvaluator.getStackBefore(offset)); 142 // Create and store a new frame. 143 stackMapFrameList.add(new FullFrame(offset, 144 variableTypes, 145 stackTypes)); 146 } 147 } 148 149 // Compress the stack map frames if the target is not Java Micro Edition. 150 if (!microEdition && !stackMapFrameList.isEmpty()) 151 { 152 // Convert the initial variable values to types. 153 VerificationType[] initialVariables = 154 correspondingVerificationTypes(programClass, 155 programMethod, 156 codeAttribute, 157 PartialEvaluator.AT_METHOD_ENTRY, 158 partialEvaluator.getVariablesBefore(0)); 159 160 // Special case: the <init> method. 161 if (method.getName(programClass).equals(ClassConstants.INTERNAL_METHOD_NAME_INIT)) 162 { 163 initialVariables[0] = VerificationTypeFactory.createUninitializedThisType(); 164 } 165 166 compressStackMapFrames(initialVariables, 167 stackMapFrameList); 168 } 169 170 // Get the proper name for the attribute to be added/replaced/deleted. 171 String stackMapAttributeName = microEdition ? 172 ClassConstants.ATTR_StackMap : 173 ClassConstants.ATTR_StackMapTable; 174 175 int frameCount = stackMapFrameList.size(); 176 177 if (DEBUG) 178 { 179 Attribute originalStackMapAttribute = codeAttribute.getAttribute(clazz, 180 stackMapAttributeName); 181 182 if (originalStackMapAttribute != null) 183 { 184 int originalFrameCount = microEdition ? 185 ((StackMapAttribute)originalStackMapAttribute).u2stackMapFramesCount : 186 ((StackMapTableAttribute)originalStackMapAttribute).u2stackMapFramesCount; 187 188 StackMapFrame[] originalFrames = microEdition ? 189 ((StackMapAttribute)originalStackMapAttribute).stackMapFrames : 190 ((StackMapTableAttribute)originalStackMapAttribute).stackMapFrames; 191 192 if (frameCount != originalFrameCount || 193 !Arrays.equals(stackMapFrameList.toArray(), originalFrames)) 194 { 195 System.out.println("Original preverification ["+clazz.getName()+"]:"); 196 new ClassPrinter().visitProgramMethod(programClass, programMethod); 197 } 198 } 199 else if (frameCount != 0) 200 { 201 System.out.println("Original preverification empty ["+clazz.getName()+"."+method.getName(clazz)+"]"); 202 } 203 } 204 205 if (frameCount == 0) 206 { 207 // Remove any stack map (table) attribute from the code attribute. 208 new AttributesEditor(programClass, programMethod, codeAttribute, true).deleteAttribute(stackMapAttributeName); 209 } 210 else 211 { 212 Attribute stackMapAttribute; 213 214 // Create the appropriate attribute. 215 if (microEdition) 216 { 217 // Copy the frames into an array. 218 FullFrame[] stackMapFrames = new FullFrame[frameCount]; 219 stackMapFrameList.toArray(stackMapFrames); 220 221 // Put the frames into a stack map attribute. 222 stackMapAttribute = new StackMapAttribute(stackMapFrames); 223 } 224 else 225 { 226 // Copy the frames into an array. 227 StackMapFrame[] stackMapFrames = new StackMapFrame[frameCount]; 228 stackMapFrameList.toArray(stackMapFrames); 229 230 // Put the frames into a stack map table attribute. 231 stackMapAttribute = new StackMapTableAttribute(stackMapFrames); 232 } 233 234 // Fill out the name of the stack map attribute. 235 stackMapAttribute.u2attributeNameIndex = 236 new ConstantPoolEditor(programClass).addUtf8Constant(stackMapAttributeName); 237 238 // Add the new stack map (table) attribute to the code attribute. 239 new AttributesEditor(programClass, programMethod, codeAttribute, true).addAttribute(stackMapAttribute); 240 241 if (DEBUG) 242 { 243 System.out.println("Preverifier ["+programClass.getName()+"."+programMethod.getName(programClass)+"]:"); 244 stackMapAttribute.accept(programClass, programMethod, codeAttribute, new ClassPrinter()); 245 } 246 } 247 248 // Apply code modifications, deleting unreachable code. 249 codeAttributeEditor.visitCodeAttribute(clazz, method, codeAttribute); 250 } 251 252 253 // Small utility methods. 254 255 /** 256 * Creates and returns the verification types corresponding to the given 257 * variables. If necessary, class constants are added to the constant pool 258 * of the given class. 259 */ 260 private VerificationType[] correspondingVerificationTypes(ProgramClass programClass, 261 ProgramMethod programMethod, 262 CodeAttribute codeAttribute, 263 int offset, 264 TracedVariables variables) 265 { 266 int maximumVariablesSize = variables.size(); 267 int typeCount = 0; 268 int typeIndex = 0; 269 270 // Count the the number of verification types, ignoring any nulls at 271 // the end. 272 for (int index = 0; index < maximumVariablesSize; index++) 273 { 274 Value value = variables.getValue(index); 275 276 typeIndex++; 277 278 // Remember the maximum live type index. 279 if (value != null && 280 (offset == PartialEvaluator.AT_METHOD_ENTRY || 281 livenessAnalyzer.isAliveBefore(offset, index))) 282 { 283 typeCount = typeIndex; 284 285 // Category 2 types that are alive are stored as single entries. 286 if (value.isCategory2()) 287 { 288 index++; 289 } 290 } 291 } 292 293 // Create and fill out the verification types. 294 VerificationType[] types = new VerificationType[typeCount]; 295 296 typeIndex = 0; 297 298 // Note the slightly different terminating condition, because the 299 // types may have been truncated. 300 for (int index = 0; typeIndex < typeCount; index++) 301 { 302 Value value = variables.getValue(index); 303 Value producerValue = variables.getProducerValue(index); 304 305 // Fill out the type. 306 VerificationType type; 307 308 if (value != null && 309 (offset == PartialEvaluator.AT_METHOD_ENTRY || 310 livenessAnalyzer.isAliveBefore(offset, index))) 311 { 312 type = correspondingVerificationType(programClass, 313 programMethod, 314 codeAttribute, 315 offset, 316 index == 0, 317 value, 318 producerValue); 319 320 // Category 2 types that are alive are stored as single entries. 321 if (value.isCategory2()) 322 { 323 index++; 324 } 325 } 326 else 327 { 328 type = VerificationTypeFactory.createTopType(); 329 } 330 331 types[typeIndex++] = type; 332 } 333 334 return types; 335 } 336 337 338 /** 339 * Creates and returns the verification types corresponding to the given 340 * stack. If necessary, class constants are added to the constant pool 341 * of the given class. 342 */ 343 private VerificationType[] correspondingVerificationTypes(ProgramClass programClass, 344 ProgramMethod programMethod, 345 CodeAttribute codeAttribute, 346 int offset, 347 TracedStack stack) 348 { 349 int maximumStackSize = stack.size(); 350 int typeCount = 0; 351 352 // Count the the number of verification types. 353 for (int index = 0; index < maximumStackSize; index++) 354 { 355 // We have to work down from the top of the stack. 356 Value value = stack.getTop(index); 357 358 typeCount++; 359 360 // Category 2 types are stored as single entries. 361 if (value.isCategory2()) 362 { 363 index++; 364 } 365 } 366 367 // Create and fill out the verification types. 368 VerificationType[] types = new VerificationType[typeCount]; 369 370 int typeIndex = typeCount; 371 372 for (int index = 0; index < maximumStackSize; index++) 373 { 374 // We have to work down from the top of the stack. 375 Value value = stack.getTop(index); 376 Value producerValue = stack.getTopProducerValue(index); 377 378 // Fill out the type. 379 types[--typeIndex] = 380 correspondingVerificationType(programClass, 381 programMethod, 382 codeAttribute, 383 offset, 384 false, 385 value, 386 producerValue); 387 388 // Category 2 types are stored as single entries. 389 if (value.isCategory2()) 390 { 391 index++; 392 } 393 } 394 395 return types; 396 } 397 398 399 /** 400 * Creates and returns the verification type corresponding to the given 401 * value. If necessary, a class constant is added to the constant pool of 402 * the given class. 403 */ 404 private VerificationType correspondingVerificationType(ProgramClass programClass, 405 ProgramMethod programMethod, 406 CodeAttribute codeAttribute, 407 int offset, 408 boolean isVariable0, 409 Value value, 410 Value producerValue) 411 { 412 if (value == null) 413 { 414 return VerificationTypeFactory.createTopType(); 415 } 416 417 int type = value.computationalType(); 418 419 switch (type) 420 { 421 case Value.TYPE_INSTRUCTION_OFFSET: 422 case Value.TYPE_INTEGER: return VerificationTypeFactory.createIntegerType(); 423 case Value.TYPE_LONG: return VerificationTypeFactory.createLongType(); 424 case Value.TYPE_FLOAT: return VerificationTypeFactory.createFloatType(); 425 case Value.TYPE_DOUBLE: return VerificationTypeFactory.createDoubleType(); 426 case Value.TYPE_TOP: return VerificationTypeFactory.createTopType(); 427 case Value.TYPE_REFERENCE: 428 // Is it a Null type? 429 ReferenceValue referenceValue = value.referenceValue(); 430 if (referenceValue.isNull() == Value.ALWAYS) 431 { 432 return VerificationTypeFactory.createNullType(); 433 } 434 435 // Does the reference type have a single producer? 436 if (offset != PartialEvaluator.AT_METHOD_ENTRY) 437 { 438 InstructionOffsetValue producers = producerValue.instructionOffsetValue(); 439 if (producers.instructionOffsetCount() == 1) 440 { 441 int producerOffset = producers.instructionOffset(0); 442 443 // Follow any dup or swap instructions. 444 while (producerOffset != PartialEvaluator.AT_METHOD_ENTRY && 445 isDupOrSwap(codeAttribute.code[producerOffset])) 446 { 447 producers = partialEvaluator.getStackBefore(producerOffset).getTopProducerValue(0).instructionOffsetValue(); 448 producerOffset = producers.minimumValue(); 449 } 450 451 // Are we in an instance initialization method, 452 // before the super initialization, loading "this"? 453 if (partialEvaluator.isInitializer() && 454 offset <= partialEvaluator.superInitializationOffset() && 455 (isVariable0 || 456 producerOffset > PartialEvaluator.AT_METHOD_ENTRY && 457 codeAttribute.code[producerOffset] == InstructionConstants.OP_ALOAD_0)) 458 { 459 // It's an UninitializedThis type. 460 return VerificationTypeFactory.createUninitializedThisType(); 461 } 462 463 // Is the reference type newly created and still 464 // uninitialized? 465 if (producerOffset > PartialEvaluator.AT_METHOD_ENTRY && 466 offset <= partialEvaluator.initializationOffset(producerOffset)) 467 { 468 // It's an Uninitialized type. 469 return VerificationTypeFactory.createUninitializedType(producerOffset); 470 } 471 } 472 } 473 474 // It's an ordinary Object type. 475 return VerificationTypeFactory.createObjectType(createClassConstant(programClass, referenceValue)); 476 } 477 478 throw new IllegalArgumentException("Unknown computational type ["+type+"]"); 479 } 480 481 482 /** 483 * Finds or creates a class constant for the given reference value, and 484 * returns its index in the constant pool. 485 */ 486 private int createClassConstant(ProgramClass programClass, 487 ReferenceValue referenceValue) 488 { 489 return new ConstantPoolEditor(programClass).addClassConstant(referenceValue.getType(), 490 referenceValue.getReferencedClass()); 491 } 492 493 494 /** 495 * Compresses the given list of full frames, for use in a stack map table. 496 */ 497 private void compressStackMapFrames(VerificationType[] initialVariableTypes, 498 List stackMapFrameList) 499 { 500 int previousVariablesCount = initialVariableTypes.length; 501 VerificationType[] previousVariableTypes = initialVariableTypes; 502 503 int previousOffset = -1; 504 505 for (int index = 0; index < stackMapFrameList.size(); index++) 506 { 507 FullFrame fullFrame = (FullFrame)stackMapFrameList.get(index); 508 509 int variablesCount = fullFrame.variablesCount; 510 VerificationType[] variables = fullFrame.variables; 511 int stackCount = fullFrame.stackCount; 512 VerificationType[] stack = fullFrame.stack; 513 514 // Start computing the compressed frame. 515 // The default is the full frame. 516 StackMapFrame compressedFrame = fullFrame; 517 518 // Are all variables equal? 519 if (variablesCount == previousVariablesCount && 520 equalVerificationTypes(variables, previousVariableTypes, variablesCount)) 521 { 522 // Are the stacks equal? 523 //if (stackCount == previousStackCount && 524 // equalVerificationTypes(stack, previousStack, stackCount)) 525 //{ 526 // // Remove the identical frame. 527 // stackMapFrameList.remove(index--); 528 // 529 // // Move on to the next frame (at the same index). 530 // continue; 531 //} 532 // Is the new stack empty? 533 //else 534 if (stackCount == 0) 535 { 536 compressedFrame = new SameZeroFrame(); 537 } 538 // Does the new stack contain a single element? 539 else if (stackCount == 1) 540 { 541 compressedFrame = new SameOneFrame(stack[0]); 542 } 543 } 544 // Is the stack empty? 545 else if (stackCount == 0) 546 { 547 int additionalVariablesCount = variablesCount - previousVariablesCount; 548 549 // Are the variables chopped? 550 if (additionalVariablesCount < 0 && 551 additionalVariablesCount > -4 && 552 equalVerificationTypes(variables, previousVariableTypes, variablesCount)) 553 { 554 compressedFrame = new LessZeroFrame((byte)-additionalVariablesCount); 555 } 556 // Are the variables extended? 557 else if (//previousVariablesCount > 0 && 558 additionalVariablesCount > 0 && 559 additionalVariablesCount < 4 && 560 equalVerificationTypes(variables, previousVariableTypes, previousVariablesCount)) 561 { 562 // Copy the additional variables into an array. 563 VerificationType[] additionalVariables = new VerificationType[additionalVariablesCount]; 564 System.arraycopy(variables, variablesCount - additionalVariablesCount, 565 additionalVariables, 0, 566 additionalVariablesCount); 567 568 compressedFrame = new MoreZeroFrame(additionalVariables); 569 } 570 } 571 572 // Compress the instruction offset. 573 int offset = fullFrame.u2offsetDelta; 574 compressedFrame.u2offsetDelta = offset - previousOffset - 1; 575 previousOffset = offset; 576 577 // Remember this frame. 578 previousVariablesCount = fullFrame.variablesCount; 579 previousVariableTypes = fullFrame.variables; 580 581 // Replace the full frame. 582 stackMapFrameList.set(index, compressedFrame); 583 } 584 } 585 586 587 /** 588 * Returns whether the given arrays of verification types are equal, up to 589 * the given length. 590 */ 591 private boolean equalVerificationTypes(VerificationType[] types1, 592 VerificationType[] types2, 593 int length) 594 { 595 if (length > 0 && 596 (types1.length < length || 597 types2.length < length)) 598 { 599 return false; 600 } 601 602 for (int index = 0; index < length; index++) 603 { 604 if (!types1[index].equals(types2[index])) 605 { 606 return false; 607 } 608 } 609 610 return true; 611 } 612 613 614 /** 615 * Returns whether the given instruction opcode represents a dup or swap 616 * instruction (dup, dup_x1, dup_x2, dup2, dup2_x1, dup2_x2, swap). 617 */ 618 private boolean isDupOrSwap(int opcode) 619 { 620 return opcode >= InstructionConstants.OP_DUP && 621 opcode <= InstructionConstants.OP_SWAP; 622 } 623} 624