1 19 20 25 26 package soot.jimple.toolkits.annotation.arraycheck; 27 import soot.options.*; 28 29 import soot.*; 30 import soot.util.*; 31 import soot.toolkits.graph.*; 32 import soot.jimple.*; 33 import soot.jimple.internal.*; 34 import soot.jimple.toolkits.callgraph.*; 35 import java.util.*; 36 37 40 41 public class RectangularArrayFinder extends SceneTransformer 42 { 43 public RectangularArrayFinder( Singletons.Global g ) {} 44 public static RectangularArrayFinder v() { return G.v().soot_jimple_toolkits_annotation_arraycheck_RectangularArrayFinder(); } 45 46 private ExtendedHashMutableDirectedGraph agraph = 47 new ExtendedHashMutableDirectedGraph(); 48 49 private Set falseSet = new HashSet(); 50 private Set trueSet = new HashSet(); 51 private CallGraph cg; 52 53 protected void internalTransform(String phaseName, Map opts) 54 { 55 Scene sc = Scene.v(); 56 57 cg = sc.getCallGraph(); 58 59 Date start = new Date(); 60 if (Options.v().verbose()) 61 G.v().out.println("[ra] Finding rectangular arrays, start on "+start); 62 63 Chain appClasses = sc.getApplicationClasses(); 64 65 Iterator classIt = appClasses.iterator(); 66 67 while (classIt.hasNext()) 68 { 69 SootClass c = (SootClass)classIt.next(); 70 71 Iterator methodIt = c.methodIterator(); 72 73 while (methodIt.hasNext()) 74 { 75 SootMethod method = (SootMethod)methodIt.next(); 76 77 if (!method.isConcrete()) 78 continue; 79 80 if (!sc.getReachableMethods().contains(method)) 81 continue; 82 83 recoverRectArray(method); 84 addInfoFromMethod(method); 85 } 86 } 87 88 122 123 124 if (agraph.containsNode(BoolValue.v(false))) 125 { 126 List changedNodeList = new ArrayList(); 127 128 List startNodes = agraph.getSuccsOf(BoolValue.v(false)); 129 130 falseSet.addAll(startNodes); 131 changedNodeList.addAll(startNodes); 132 133 while (!changedNodeList.isEmpty()) 134 { 135 Object node = changedNodeList.remove(0); 136 137 List succs = agraph.getSuccsOf(node); 138 139 Iterator succsIt = succs.iterator(); 140 141 while (succsIt.hasNext()) 142 { 143 Object succ = succsIt.next(); 144 145 if (!falseSet.contains(succ)) 146 { 147 falseSet.add(succ); 148 changedNodeList.add(succ); 149 } 150 } 151 } 152 } 153 154 155 if (agraph.containsNode(BoolValue.v(true))) 156 { 157 List changedNodeList = new ArrayList(); 158 159 List startNodes = agraph.getSuccsOf(BoolValue.v(true)); 160 161 Iterator nodesIt = startNodes.iterator(); 162 while (nodesIt.hasNext()) 163 { 164 Object node = nodesIt.next(); 165 if (falseSet.contains(node)) 166 continue; 167 168 changedNodeList.add(node); 169 trueSet.add(node); 170 } 171 172 while (!changedNodeList.isEmpty()) 173 { 174 Object node = changedNodeList.remove(0); 175 176 List succs = agraph.getSuccsOf(node); 177 178 Iterator succsIt = succs.iterator(); 179 180 while (succsIt.hasNext()) 181 { 182 Object succ = succsIt.next(); 183 184 if (falseSet.contains(succ)) 185 continue; 186 187 if (trueSet.contains(succ)) 188 continue; 189 190 trueSet.add(succ); 191 changedNodeList.add(succ); 192 } 193 } 194 } 195 196 197 198 if (Options.v().debug()) 199 { 200 G.v().out.println("Rectangular Array :"); 201 { 202 Iterator nodeIt = trueSet.iterator(); 203 while (nodeIt.hasNext()) 204 { 205 Object node = nodeIt.next(); 206 207 G.v().out.println(node); 208 } 209 } 210 211 G.v().out.println("\nNon-rectangular Array :"); 212 { 213 Iterator nodeIt = falseSet.iterator(); 214 while (nodeIt.hasNext()) 215 { 216 Object node = nodeIt.next(); 217 218 G.v().out.println(node); 219 } 220 } 221 } 222 223 Date finish = new Date(); 224 if (Options.v().verbose()) 225 { 226 long runtime = finish.getTime() - start.getTime(); 227 long mins = runtime/60000; 228 long secs = (runtime%60000)/1000; 229 G.v().out.println("[ra] Rectangular array finder finishes." 230 +" It took "+mins+" mins and "+secs+" secs."); 231 } 232 } 233 234 private void addInfoFromMethod(SootMethod method) 235 { 236 if (Options.v().verbose()) 237 G.v().out.println("[ra] Operating "+method.getSignature()); 238 239 boolean needTransfer = true; 240 241 Body body = method.getActiveBody(); 242 243 Set tmpNode = new HashSet(); 244 245 246 247 boolean trackReturn = false; 248 Type rtnType = method.getReturnType(); 249 250 if (rtnType instanceof ArrayType) 251 { 252 if (((ArrayType)rtnType).numDimensions > 1) 253 { 254 trackReturn = true; 255 needTransfer = true; 256 } 257 } 258 259 Set arrayLocal = new HashSet(); 260 261 262 263 Chain locals = body.getLocals(); 264 Iterator localIt = locals.iterator(); 265 while (localIt.hasNext()) 266 { 267 Local local = (Local)localIt.next(); 268 269 Type type = local.getType(); 270 271 if (type instanceof ArrayType) 272 { 273 if ( ((ArrayType)type).numDimensions > 1) 274 { 275 arrayLocal.add(local); 276 } 277 else 278 tmpNode.add(new MethodLocal(method, local)); 279 } 280 } 281 282 283 ExtendedHashMutableDirectedGraph ehmdg = new ExtendedHashMutableDirectedGraph(); 284 285 Iterator unitIt = body.getUnits().snapshotIterator(); 286 287 while (unitIt.hasNext()) 288 { 289 Stmt s = (Stmt)unitIt.next(); 290 291 292 if (s.containsInvokeExpr()) 293 { 294 InvokeExpr iexpr = (InvokeExpr)s.getInvokeExpr(); 295 296 int argnum = iexpr.getArgCount(); 297 298 for (int i=0; i<argnum; i++) 299 { 300 Value arg = iexpr.getArg(i); 301 if (! arrayLocal.contains(arg)) 302 continue; 303 304 needTransfer = true; 305 306 307 MethodLocal ml = new MethodLocal(method, (Local)arg); 308 309 Iterator targetIt = new Targets( cg.edgesOutOf(s) ); 310 311 while (targetIt.hasNext()) 312 { 313 SootMethod target = (SootMethod)targetIt.next(); 314 315 MethodParameter mp = new MethodParameter(target, i); 316 317 318 ehmdg.addMutualEdge(ml, mp); 319 } 320 } 321 } 322 323 324 325 if (trackReturn && (s instanceof ReturnStmt)) 326 { 327 Value op = ((ReturnStmt)s).getOp(); 328 329 if (op instanceof Local) 330 { 331 ehmdg.addMutualEdge(new MethodLocal(method, (Local)op), new MethodReturn(method)); 332 } 333 } 334 335 336 if (s instanceof DefinitionStmt) 337 { 338 Value leftOp = ((DefinitionStmt)s).getLeftOp(); 339 Value rightOp = ((DefinitionStmt)s).getRightOp(); 340 341 if (! (leftOp.getType() instanceof ArrayType) 342 && ! (rightOp.getType() instanceof ArrayType)) 343 continue; 344 345 Object from = null; 346 Object to = null; 347 348 349 if ((leftOp instanceof Local) && (rightOp instanceof Local)) 350 { 351 if (arrayLocal.contains(leftOp) && arrayLocal.contains(rightOp)) 352 { 353 int leftDims = ((ArrayType)((Local)leftOp).getType()).numDimensions; 354 int rightDims = ((ArrayType)((Local)rightOp).getType()).numDimensions; 355 356 to = new MethodLocal(method, (Local)leftOp); 357 from = new MethodLocal(method, (Local)rightOp); 358 ehmdg.addMutualEdge(from, to); 359 360 if (leftDims != rightDims) 361 ehmdg.addEdge(BoolValue.v(false), from); 362 } 363 else 364 if (! arrayLocal.contains(leftOp)) 365 { 366 ehmdg.addEdge(BoolValue.v(false), new MethodLocal(method, (Local)rightOp)); 367 } 368 } 369 else 370 if ((leftOp instanceof Local) && (rightOp instanceof ParameterRef)) 371 { 372 if (arrayLocal.contains(leftOp)) 373 { 374 to = new MethodLocal(method, (Local)leftOp); 375 int index = ((ParameterRef)rightOp).getIndex(); 376 from = new MethodParameter(method, index); 377 ehmdg.addMutualEdge(from, to); 378 379 needTransfer = true; 380 } 381 } 382 else 383 if ((leftOp instanceof Local) && (rightOp instanceof ArrayRef)) 384 { 385 Local base = (Local)((ArrayRef)rightOp).getBase(); 386 387 388 if (arrayLocal.contains(base)) 389 { 390 391 to = new ArrayReferenceNode(method, (Local)base); 392 from = new MethodLocal(method, (Local)base); 393 ehmdg.addMutualEdge(from, to); 394 395 396 tmpNode.add(to); 397 398 399 from = to; 400 to = new MethodLocal(method, (Local)leftOp); 401 ehmdg.addMutualEdge(from, to); 402 } 403 } 404 else 405 if ((leftOp instanceof ArrayRef) && (rightOp instanceof Local)) 406 { 407 Local base = (Local)((ArrayRef)leftOp).getBase(); 408 409 if (arrayLocal.contains(base)) 410 { 411 412 Object suspect = new MethodLocal(method, (Local)rightOp); 413 Object arrRef = new ArrayReferenceNode(method, (Local)base); 414 415 boolean doNothing = false; 416 417 blocklabel: 418 { 419 if (!ehmdg.containsNode(suspect)) 420 break blocklabel; 421 422 List succs = ehmdg.getSuccsOf(suspect); 423 List preds = ehmdg.getSuccsOf(suspect); 424 425 Set neighbor = new HashSet(); 426 427 neighbor.addAll(succs); 428 neighbor.addAll(preds); 429 430 if (neighbor.size() != 1) 431 break blocklabel; 432 433 Object neighborOne = (neighbor.toArray())[0]; 434 435 if (arrRef.equals(neighborOne)) 436 doNothing = true; 437 } 438 439 if (!doNothing) 440 ehmdg.addEdge(BoolValue.v(false), new MethodLocal(method, base)); 441 } 442 } 443 else 444 if ((leftOp instanceof Local) && (rightOp instanceof InvokeExpr)) 445 { 446 if (arrayLocal.contains(leftOp)) 447 { 448 to = new MethodLocal(method, (Local)leftOp); 449 450 Iterator targetIt = new Targets( cg.edgesOutOf(s) ); 451 452 while (targetIt.hasNext()) 453 { 454 SootMethod target = (SootMethod)targetIt.next(); 455 456 ehmdg.addMutualEdge(new MethodReturn(target), to); 457 } 458 } 459 } 460 else 461 462 if ((leftOp instanceof FieldRef) && (rightOp instanceof Local)) 463 { 464 if (arrayLocal.contains(rightOp)) 465 { 466 Type ftype = ((FieldRef)leftOp).getType(); 467 Type ltype = ((Local)rightOp).getType(); 468 469 to = ((FieldRef)leftOp).getField(); 470 from = new MethodLocal(method, (Local)rightOp); 471 472 ehmdg.addMutualEdge(from, to); 473 474 if (!ftype.equals(ltype)) 475 { 476 ehmdg.addEdge(BoolValue.v(false), to); 477 } 478 479 needTransfer = true; 480 } 481 } 482 else 483 if ((leftOp instanceof Local) && (rightOp instanceof FieldRef)) 484 { 485 if (arrayLocal.contains(leftOp)) 486 { 487 Type ftype = ((FieldRef)rightOp).getType(); 488 Type ltype = ((Local)leftOp).getType(); 489 490 to = new MethodLocal(method, (Local)leftOp); 491 from = ((FieldRef)rightOp).getField(); 492 493 ehmdg.addMutualEdge(from, to); 494 495 if (!ftype.equals(ltype)) 496 { 497 ehmdg.addEdge(BoolValue.v(false), to); 498 } 499 500 needTransfer = true; 501 } 502 } 503 else 504 if ((leftOp instanceof Local) && ((rightOp instanceof NewArrayExpr)||(rightOp instanceof NewMultiArrayExpr))) 505 { 506 if (arrayLocal.contains(leftOp)) 507 { 508 ehmdg.addEdge(BoolValue.v(true), new MethodLocal(method, (Local)leftOp)); 509 } 510 } 511 else 512 if ((leftOp instanceof Local) && (rightOp instanceof CastExpr)) 513 514 { 515 Local rOp = (Local)((CastExpr)rightOp).getOp(); 516 517 to = new MethodLocal(method, (Local)leftOp); 518 from = new MethodLocal(method, rOp); 519 520 if (arrayLocal.contains(leftOp) && arrayLocal.contains(rOp)) 521 { 522 ArrayType lat = (ArrayType)leftOp.getType(); 523 ArrayType rat = (ArrayType)rOp.getType(); 524 525 if (lat.numDimensions == rat.numDimensions) 526 { 527 ehmdg.addMutualEdge(from, to); 528 } 529 else 530 { 531 ehmdg.addEdge(BoolValue.v(false), from); 532 ehmdg.addEdge(BoolValue.v(false), to); 533 } 534 } 535 else 536 if (arrayLocal.contains(leftOp)) 537 { 538 ehmdg.addEdge(BoolValue.v(false), to); 539 } 540 else 541 if (arrayLocal.contains(rOp)) 542 { 543 ehmdg.addEdge(BoolValue.v(false), from); 544 } 545 } 546 } 547 } 548 549 550 551 if (needTransfer) 552 { 553 Iterator tmpNodeIt = tmpNode.iterator(); 554 555 while (tmpNodeIt.hasNext()) 556 { 557 ehmdg.skipNode(tmpNodeIt.next()); 558 } 559 560 561 agraph.mergeWith(ehmdg); 562 } 563 564 } 565 566 private void recoverRectArray(SootMethod method) 567 { 568 Body body = method.getActiveBody(); 569 HashSet malocal = new HashSet(); 570 571 Chain locals = body.getLocals(); 572 Iterator localsIt = locals.iterator(); 573 while (localsIt.hasNext()) 574 { 575 Local local = (Local)localsIt.next(); 576 Type type = local.getType(); 577 if (!(type instanceof ArrayType)) 578 continue; 579 580 if (((ArrayType)type).numDimensions == 2) 581 malocal.add(local); 582 } 583 584 if (malocal.size() == 0) 585 return; 586 587 Chain units = body.getUnits(); 588 589 Stmt stmt = (Stmt)units.getFirst(); 590 591 while (true) 592 { 593 if (stmt == null) 594 break; 595 596 597 if (!stmt.fallsThrough()) 598 break; 599 600 searchblock: 601 { 602 603 if (!(stmt instanceof AssignStmt)) 604 break searchblock; 605 606 Value leftOp = ((AssignStmt)stmt).getLeftOp(); 607 Value rightOp = ((AssignStmt)stmt).getRightOp(); 608 609 if (!malocal.contains(leftOp) || !(rightOp instanceof NewArrayExpr)) 610 break searchblock; 611 612 Local local = (Local)leftOp; 613 614 NewArrayExpr naexpr = (NewArrayExpr)rightOp; 615 616 Value size = naexpr.getSize(); 617 if (!(size instanceof IntConstant)) 618 break searchblock; 619 620 int firstdim = ((IntConstant)size).value; 621 if (firstdim > 100) 622 break searchblock; 623 624 ArrayType localtype = (ArrayType)local.getType(); 625 Type basetype = localtype.baseType; 626 627 Local[] tmplocals = new Local[firstdim]; 628 629 int seconddim = lookforPattern(units, stmt, 630 firstdim, local, 631 basetype, tmplocals); 632 633 if (seconddim >= 0) 634 transferPattern(units, stmt, 635 firstdim, seconddim, 636 local, basetype, tmplocals); 637 } 638 639 stmt = (Stmt)units.getSuccOf(stmt); 640 } 641 } 642 643 646 private int lookforPattern(Chain units, Stmt startpoint, 647 int firstdim, Local local, 648 Type basetype, Local[] tmplocals) 649 { 650 651 659 660 int seconddim = -1; 661 int curdim = 0; 662 Object curtmp = local; 664 Stmt curstmt = startpoint; 665 666 int fault = 99; 667 int state = 1; 668 669 while (true) 670 { 671 curstmt = (Stmt)units.getSuccOf(curstmt); 672 if (curstmt == null) 673 return -1; 674 675 if (!(curstmt instanceof AssignStmt)) 676 return -1; 677 678 Value leftOp = ((AssignStmt)curstmt).getLeftOp(); 679 Value rightOp = ((AssignStmt)curstmt).getRightOp(); 680 681 switch (state) 682 { 683 684 case 0: 685 break; 686 687 case 1: 688 689 { 690 state = fault; 691 692 if (!(rightOp instanceof NewArrayExpr)) 693 break; 694 695 NewArrayExpr naexpr = (NewArrayExpr)rightOp; 696 Type type = naexpr.getBaseType(); 697 Value size = naexpr.getSize(); 698 699 if (!type.equals(basetype)) 700 break; 701 702 if (!(size instanceof IntConstant)) 703 break; 704 705 if (curdim == 0) 706 seconddim = ((IntConstant)size).value; 707 else 708 { 709 if (((IntConstant)size).value != seconddim) 710 break; 711 } 712 713 curtmp = leftOp; 714 715 state = 2; 716 } 717 break; 718 719 case 2: 720 { 721 state = fault; 722 723 if (!(leftOp instanceof ArrayRef)) 724 break; 725 726 Value base = ((ArrayRef)leftOp).getBase(); 727 Value idx = ((ArrayRef)leftOp).getIndex(); 728 729 730 if (base.equals(curtmp)) 731 state = 2; 732 else 733 734 if (base.equals(local)) 735 { 736 if (!(idx instanceof IntConstant)) 737 break; 738 739 if (curdim != ((IntConstant)idx).value) 740 break; 741 742 if (!rightOp.equals(curtmp)) 743 break; 744 745 tmplocals[curdim] = (Local)curtmp; 746 747 curdim++; 748 749 if (curdim >= firstdim) 750 state = 3; 751 else 752 state = 1; 753 } 754 } 755 break; 756 757 case 3: 758 return seconddim; 759 760 761 default: 762 return -1; 763 } 764 } 765 } 766 767 private void transferPattern(Chain units, Stmt startpoint, 768 int firstdim, int seconddim, 769 Local local, Type basetype, 770 Local[] tmplocals) 771 { 772 773 { 774 775 ArrayType atype = (ArrayType)local.getType(); 776 List sizes = new ArrayList(2); 777 sizes.add(IntConstant.v(firstdim)); 778 sizes.add(IntConstant.v(seconddim)); 779 Value nmexpr = new JNewMultiArrayExpr(atype, sizes); 780 781 ((AssignStmt)startpoint).setRightOp(nmexpr); 782 } 783 784 { 785 int pos = 0; 786 int curdim = 0; 787 Local tmpcur = local; 788 789 Stmt curstmt = (Stmt)units.getSuccOf(startpoint); 790 791 while (curdim < firstdim) 792 { 793 Value leftOp = ((AssignStmt)curstmt).getLeftOp(); 794 Value rightOp = ((AssignStmt)curstmt).getRightOp(); 795 796 if (tmplocals[curdim].equals(leftOp) && (rightOp instanceof NewArrayExpr)) 797 { 798 ArrayRef arexpr = new JArrayRef(local, IntConstant.v(curdim)); 799 ((AssignStmt)curstmt).setRightOp(arexpr); 800 tmpcur = (Local)leftOp; 801 } 802 else 803 if ((leftOp instanceof ArrayRef) && (rightOp.equals(tmpcur))) 804 { 805 806 Stmt tmpstmt = curstmt; 807 curstmt = (Stmt)units.getSuccOf(curstmt); 808 units.remove(tmpstmt); 809 810 curdim++; 811 } 812 else 813 curstmt = (Stmt)units.getSuccOf(curstmt); 814 } 815 } 816 } 817 818 819 public boolean isRectangular(Object obj) 820 { 821 if (trueSet.contains(obj)) 822 return true; 823 else 824 return false; 825 } 826 } 827 828 829 | Popular Tags |