Robust/src/IR/Flat/BCXPointsToCheckVRuntime.java

   1 package IR.Flat;
   2
   3 import Analysis.Disjoint.HeapAnalysis;
   4 import Analysis.Disjoint.Alloc;
   5 import IR.*;
   6
   7 import java.io.*;
   8 import java.util.*;
   9
  10
  11 // This BuildCode Extension (BCX) takes a heap analysis
  12 // with points-to information and generates checks at runtime
  13 // verifies the allocation site of objects pointed-to.  It
  14 // doesn't fully verify an analysis but it can reveal bugs!
  15
  16
  17 public class BCXPointsToCheckVRuntime implements BuildCodeExtension {
  18
  19   protected State        state;
  20   protected BuildCode    buildCode;
  21   protected TypeUtil     typeUtil;
  22   protected HeapAnalysis heapAnalysis;
  23
  24   protected ClassDescriptor cdObject;
  25
  26   protected TypeDescriptor stringType;
  27
  28   private boolean DEBUG = false;
  29
  30
  31
  32   public BCXPointsToCheckVRuntime( State        state,
  33                                    BuildCode    buildCode,
  34                                    TypeUtil     typeUtil,
  35                                    HeapAnalysis heapAnalysis ) {
  36     this.state        = state;
  37     this.buildCode    = buildCode;
  38     this.typeUtil     = typeUtil;
  39     this.heapAnalysis = heapAnalysis;
  40
  41     ClassDescriptor cdString = typeUtil.getClass( typeUtil.StringClass );
  42     assert cdString != null;
  43     stringType = new TypeDescriptor( cdString );
  44   }
  45
  46
  47   public void additionalIncludesMethodsHeader(PrintWriter outmethodheader) {
  48     outmethodheader.println( "#include<stdio.h>" );
  49     outmethodheader.println( "#include<execinfo.h>" );
  50   }
  51
  52
  53   public void additionalCodeAtTopFlatMethodBody(PrintWriter output, FlatMethod fm) {
  54
  55     output.println( "// Generating points-to checks for method params" );
  56
  57     for( int i = 0; i < fm.numParameters(); ++i ) {
  58       TempDescriptor td   = fm.getParameter( i );
  59       TypeDescriptor type = td.getType();
  60       if( type.isPtr() ) {
  61
  62         genAssertRuntimePtrVsHeapResults( output,
  63                                           fm,
  64                                           td,
  65                                           heapAnalysis.canPointToAfter( td, fm )
  66                                           );
  67
  68         if( DEBUG ) {
  69           System.out.println( "\nGenerating code for "+fm );
  70           System.out.println( "  arg "+td+" can point to "+heapAnalysis.canPointToAfter( td, fm ) );
  71         }
  72       }
  73     }
  74
  75     output.println( "// end method params" );
  76   }
  77
  78
  79   public void additionalCodePreNode(FlatMethod fm, FlatNode fn, PrintWriter output) {
  80
  81     TempDescriptor  lhs;
  82     TempDescriptor  rhs;
  83     FieldDescriptor fld;
  84     TempDescriptor  idx;
  85     TypeDescriptor  type;
  86     TempDescriptor  arg;
  87     TempDescriptor  ret;
  88
  89
  90     // for PRE-NODE checks, only look at pointers we are reading from because
  91     // pointers about to be set may be undefined and don't pass runtime checks nicely
  92
  93
  94     switch( fn.kind() ) {
  95
  96       case FKind.FlatOpNode: {
  97         FlatOpNode fon = (FlatOpNode) fn;
  98         if( fon.getOp().getOp() == Operation.ASSIGN ) {
  99           lhs = fon.getDest();
 100           rhs = fon.getLeft();
 101
 102           type = lhs.getType();
 103           if( type.isPtr() ) {
 104
 105             output.println( "// Generating points-to checks for pre-node op assign" );
 106
 107             genAssertRuntimePtrVsHeapResults( output,
 108                                               fm,
 109                                               rhs,
 110                                               heapAnalysis.canPointToAt( rhs, fn )
 111                                               );
 112
 113             output.println( "// end pre-node op assign" );
 114
 115
 116             if( DEBUG ) {
 117               System.out.println( "  before "+fn );
 118               System.out.println( "    "+rhs+" can point to "+heapAnalysis.canPointToAt( rhs, fn ) );
 119             }
 120           }
 121         }
 122       } break;
 123
 124
 125       case FKind.FlatCastNode: {
 126         FlatCastNode fcn = (FlatCastNode) fn;
 127         lhs = fcn.getDst();
 128         rhs = fcn.getSrc();
 129
 130         type = fcn.getType();
 131         if( type.isPtr() ) {
 132
 133           output.println( "// Generating points-to checks for pre-node cast" );
 134
 135           genAssertRuntimePtrVsHeapResults( output,
 136                                             fm,
 137                                             rhs,
 138                                             heapAnalysis.canPointToAt( rhs, fn )
 139                                             );
 140
 141           output.println( "// end pre-node cast" );
 142
 143
 144           if( DEBUG ) {
 145             System.out.println( "  before "+fn );
 146             System.out.println( "    "+rhs+" can point to "+heapAnalysis.canPointToAt( rhs, fn ) );
 147           }
 148         }
 149       } break;
 150
 151
 152       case FKind.FlatFieldNode: {
 153         FlatFieldNode ffn = (FlatFieldNode) fn;
 154         lhs = ffn.getDst();
 155         rhs = ffn.getSrc();
 156         fld = ffn.getField();
 157
 158         type = lhs.getType();
 159         if( type.isPtr() ) {
 160
 161           output.println( "// Generating points-to checks for pre-node field" );
 162
 163           genAssertRuntimePtrVsHeapResults( output,
 164                                             fm,
 165                                             rhs,
 166                                             heapAnalysis.canPointToAt( rhs, fn )
 167                                             );
 168
 169           genAssertRuntimePtrVsHeapResults( output,
 170                                             fm,
 171                                             rhs,
 172                                             fld,
 173                                             null,
 174                                             heapAnalysis.canPointToAt( rhs, fld, fn )
 175                                             );
 176
 177           output.println( "// end pre-node field" );
 178
 179
 180           if( DEBUG ) {
 181             System.out.println( "  before "+fn );
 182             System.out.println( "    "+rhs+" can point to "+heapAnalysis.canPointToAt( rhs, fn ) );
 183             System.out.println( "    "+rhs+"."+fld+" can point to "+heapAnalysis.canPointToAt( rhs, fld, fn ) );
 184           }
 185         }
 186       } break;
 187
 188
 189       case FKind.FlatElementNode: {
 190         FlatElementNode fen = (FlatElementNode) fn;
 191         lhs = fen.getDst();
 192         rhs = fen.getSrc();
 193         idx = fen.getIndex();
 194
 195         type = lhs.getType();
 196         if( type.isPtr() ) {
 197
 198           output.println( "// Generating points-to checks for pre-node element" );
 199
 200           genAssertRuntimePtrVsHeapResults( output,
 201                                             fm,
 202                                             rhs,
 203                                             heapAnalysis.canPointToAt( rhs, fn )
 204                                             );
 205
 206           genAssertRuntimePtrVsHeapResults( output,
 207                                             fm,
 208                                             rhs,
 209                                             null,
 210                                             idx,
 211                                             heapAnalysis.canPointToAtElement( rhs, fn )
 212                                             );
 213
 214           output.println( "// end pre-node element" );
 215
 216
 217           if( DEBUG ) {
 218             System.out.println( "  before "+fn );
 219             System.out.println( "    "+rhs+" can point to "+heapAnalysis.canPointToAt( rhs, fn ) );
 220             System.out.println( "    "+rhs+"["+idx+"] can point to "+heapAnalysis.canPointToAtElement( rhs, fn ) );
 221           }
 222         }
 223       } break;
 224
 225
 226       case FKind.FlatCall: {
 227         FlatCall fc = (FlatCall) fn;
 228
 229         FlatMethod fmCallee = state.getMethodFlat( fc.getMethod() );
 230
 231         boolean somethingChecked = false;
 232
 233         output.println( "// Generating points-to checks for pre-node call" );
 234
 235         for( int i = 0; i < fmCallee.numParameters(); ++i ) {
 236           arg  = fc.getArgMatchingParamIndex( fmCallee, i );
 237           type = arg.getType();
 238           if( type.isPtr() ) {
 239             genAssertRuntimePtrVsHeapResults( output,
 240                                               fm,
 241                                               arg,
 242                                               heapAnalysis.canPointToAt( arg, fn )
 243                                               );
 244             somethingChecked = true;
 245           }
 246         }
 247
 248         output.println( "// end pre-node call" );
 249
 250         if( DEBUG && somethingChecked ) {
 251
 252           System.out.println( "  before "+fn+":" );
 253
 254           for( int i = 0; i < fmCallee.numParameters(); ++i ) {
 255             arg  = fc.getArgMatchingParamIndex( fmCallee, i );
 256             type = arg.getType();
 257             if( type.isPtr() ) {
 258               System.out.println( "    arg "+arg+" can point to "+heapAnalysis.canPointToAt( arg, fn ) );
 259             }
 260           }
 261         }
 262       } break;
 263     }
 264   }
 265
 266
 267
 268   public void additionalCodePostNode(FlatMethod fm,
 269                                      FlatNode fn,
 270                                      PrintWriter output) {
 271
 272     TempDescriptor  lhs;
 273     TempDescriptor  rhs;
 274     FieldDescriptor fld;
 275     TempDescriptor  idx;
 276     TypeDescriptor  type;
 277     TempDescriptor  arg;
 278     TempDescriptor  ret;
 279
 280
 281
 282     switch( fn.kind() ) {
 283
 284
 285       case FKind.FlatLiteralNode: {
 286         FlatLiteralNode fln = (FlatLiteralNode) fn;
 287
 288         if( fln.getType().equals( stringType ) ) {
 289           lhs = fln.getDst();
 290
 291           output.println( "// Generating points-to checks for post-node string literal" );
 292
 293           genAssertRuntimePtrVsHeapResults( output,
 294                                             fm,
 295                                             lhs,
 296                                             heapAnalysis.canPointToAfter( lhs, fn )
 297                                             );
 298
 299           output.println( "// end post-node string literal" );
 300
 301
 302           if( DEBUG ) {
 303             System.out.println( "  after "+fn );
 304             System.out.println( "    "+lhs+" can point to "+heapAnalysis.canPointToAfter( lhs, fn ) );
 305           }
 306         }
 307       } break;
 308
 309
 310       case FKind.FlatOpNode: {
 311         FlatOpNode fon = (FlatOpNode) fn;
 312         if( fon.getOp().getOp() == Operation.ASSIGN ) {
 313           lhs = fon.getDest();
 314
 315           type = lhs.getType();
 316           if( type.isPtr() ) {
 317
 318             output.println( "// Generating points-to checks for post-node op assign" );
 319
 320             genAssertRuntimePtrVsHeapResults( output,
 321                                               fm,
 322                                               lhs,
 323                                               heapAnalysis.canPointToAfter( lhs, fn )
 324                                               );
 325
 326             output.println( "// end post-node op assign" );
 327
 328
 329             if( DEBUG ) {
 330               System.out.println( "  after "+fn );
 331               System.out.println( "    "+lhs+" can point to "+heapAnalysis.canPointToAfter( lhs, fn ) );
 332             }
 333           }
 334         }
 335       } break;
 336
 337
 338       case FKind.FlatCastNode: {
 339         FlatCastNode fcn = (FlatCastNode) fn;
 340         lhs = fcn.getDst();
 341
 342         type = fcn.getType();
 343         if( type.isPtr() ) {
 344
 345           output.println( "// Generating points-to checks for post-node cast" );
 346
 347           genAssertRuntimePtrVsHeapResults( output,
 348                                             fm,
 349                                             lhs,
 350                                             heapAnalysis.canPointToAfter( lhs, fn )
 351                                             );
 352
 353           output.println( "// end post-node cast" );
 354
 355
 356           if( DEBUG ) {
 357             System.out.println( "  after "+fn );
 358             System.out.println( "    "+lhs+" can point to "+heapAnalysis.canPointToAfter( lhs, fn ) );
 359           }
 360         }
 361       } break;
 362
 363
 364       case FKind.FlatFieldNode: {
 365         FlatFieldNode ffn = (FlatFieldNode) fn;
 366         lhs = ffn.getDst();
 367
 368         type = lhs.getType();
 369         if( type.isPtr() ) {
 370
 371           output.println( "// Generating points-to checks for post-node field" );
 372
 373           genAssertRuntimePtrVsHeapResults( output,
 374                                             fm,
 375                                             lhs,
 376                                             heapAnalysis.canPointToAfter( lhs, fn )
 377                                             );
 378
 379           output.println( "// end post-node field" );
 380
 381
 382           if( DEBUG ) {
 383             System.out.println( "  after "+fn );
 384             System.out.println( "    "+lhs+" can point to "+heapAnalysis.canPointToAfter( lhs, fn ) );
 385           }
 386         }
 387       } break;
 388
 389
 390       case FKind.FlatElementNode: {
 391         FlatElementNode fen = (FlatElementNode) fn;
 392         lhs = fen.getDst();
 393
 394         type = lhs.getType();
 395         if( type.isPtr() ) {
 396
 397           output.println( "// Generating points-to checks for post-node element" );
 398
 399           genAssertRuntimePtrVsHeapResults( output,
 400                                             fm,
 401                                             lhs,
 402                                             heapAnalysis.canPointToAfter( lhs, fn )
 403                                             );
 404
 405           output.println( "// end post-node element" );
 406
 407
 408           if( DEBUG ) {
 409             System.out.println( "  after "+fn );
 410             System.out.println( "    "+lhs+" can point to "+heapAnalysis.canPointToAfter( lhs, fn ) );
 411           }
 412         }
 413       } break;
 414
 415
 416       case FKind.FlatCall: {
 417         FlatCall fc = (FlatCall) fn;
 418         ret = fc.getReturnTemp();
 419
 420         FlatMethod fmCallee = state.getMethodFlat( fc.getMethod() );
 421
 422         boolean somethingChecked = false;
 423
 424         output.println( "// Generating points-to checks for post-node call" );
 425
 426         for( int i = 0; i < fmCallee.numParameters(); ++i ) {
 427           arg  = fc.getArgMatchingParamIndex( fmCallee, i );
 428           type = arg.getType();
 429           if( type.isPtr() ) {
 430             genAssertRuntimePtrVsHeapResults( output,
 431                                               fm,
 432                                               arg,
 433                                               heapAnalysis.canPointToAfter( arg, fn )
 434                                               );
 435             somethingChecked = true;
 436           }
 437         }
 438
 439         if( ret != null ) {
 440           type = ret.getType();
 441           if( type.isPtr() ) {
 442             genAssertRuntimePtrVsHeapResults( output,
 443                                               fm,
 444                                               ret,
 445                                               heapAnalysis.canPointToAfter( ret, fn )
 446                                               );
 447             somethingChecked = true;
 448           }
 449         }
 450
 451         output.println( "// end post-node call" );
 452
 453         if( DEBUG && somethingChecked ) {
 454
 455           System.out.println( "  after "+fn+":" );
 456
 457           for( int i = 0; i < fmCallee.numParameters(); ++i ) {
 458             arg  = fc.getArgMatchingParamIndex( fmCallee, i );
 459             type = arg.getType();
 460             if( type.isPtr() ) {
 461               System.out.println( "    arg "+arg+" can point to "+heapAnalysis.canPointToAfter( arg, fn ) );
 462             }
 463           }
 464
 465           if( ret != null ) {
 466             type = ret.getType();
 467             if( type.isPtr() ) {
 468               System.out.println( "    return temp "+ret+" can point to "+heapAnalysis.canPointToAfter( ret, fn ) );
 469             }
 470           }
 471
 472         }
 473       } break;
 474     }
 475   }
 476
 477
 478
 479   protected void
 480     printConditionFailed( PrintWriter output,
 481                           String      condition,
 482                           String      pointer ) {
 483
 484     // don't do this in the constructor of this extension object because
 485     // build code hasn't created any types or classes yet!
 486     if( cdObject == null ) {
 487       cdObject = typeUtil.getClass( typeUtil.ObjectClass );
 488       assert cdObject != null;
 489     }
 490
 491     output.println( "printf(\"[[[ CHECK VS HEAP RESULTS FAILED ]]] Condition for failure( "+
 492                     condition+" ) allocsite=%d at %s:%d\\n\", ((struct "+
 493                     cdObject.getSafeSymbol()+"*)"+
 494                     pointer+")->allocsite, __FILE__, __LINE__ );" );
 495
 496     // spit out the stack trace (so fancy!)
 497     output.println( "{" );
 498     output.println( "void* buffer[100];" );
 499     output.println( "char** strings;" );
 500     output.println( "int nptrs,j;" );
 501     output.println( "nptrs = backtrace(buffer, 100);" );
 502     output.println( "strings = backtrace_symbols(buffer, nptrs);" );
 503     output.println( "if (strings == NULL) {" );
 504     output.println( "  perror(\"backtrace_symbols\");" );
 505     output.println( "}" );
 506     output.println( "for (j = 0; j < nptrs; j++) {" );
 507     output.println( "  printf(\"%s\\n\", strings[j]);" );
 508     output.println( "}" );
 509     output.println( "}" );
 510   }
 511
 512
 513
 514
 515   protected void
 516     genAssertRuntimePtrVsHeapResults( PrintWriter    output,
 517                                       FlatMethod     context,
 518                                       TempDescriptor x,
 519                                       Set<Alloc>     targetsByAnalysis ) {
 520
 521     assert targetsByAnalysis != null;
 522
 523     output.println( "" );
 524     output.println( "// checks vs. heap results (DEBUG) for "+x );
 525
 526
 527     if( targetsByAnalysis == HeapAnalysis.DONTCARE_PTR ) {
 528       output.println( "// ANALYSIS DIDN'T CARE WHAT "+x+" POINTS-TO" );
 529       return;
 530     }
 531
 532     String ptr = buildCode.generateTemp( context, x );
 533
 534     String condition;
 535
 536     if( targetsByAnalysis.isEmpty() ) {
 537       condition = ptr+" != NULL";
 538
 539     } else {
 540       condition = ptr+" != NULL &&";
 541
 542       Iterator<Alloc> aItr = targetsByAnalysis.iterator();
 543       while( aItr.hasNext() ) {
 544         Alloc a = aItr.next();
 545         condition += ptr+"->allocsite != "+a.getUniqueAllocSiteID();
 546
 547         if( aItr.hasNext() ) {
 548           condition += " &&";
 549         }
 550       }
 551     }
 552
 553     output.println( "if( "+condition+" ) {" );
 554     printConditionFailed( output, condition, ptr );
 555     output.println( "}\n" );
 556   }
 557
 558
 559
 560   protected void
 561     genAssertRuntimePtrVsHeapResults( PrintWriter                    output,
 562                                       FlatMethod                     context,
 563                                       TempDescriptor                 x,
 564                                       FieldDescriptor                f, // this null OR
 565                                       TempDescriptor                 i, // this null
 566                                       Hashtable< Alloc, Set<Alloc> > targetsByAnalysis ) {
 567     // I assume when you invoke this method you already
 568     // invoked a check on just what x points to, don't duplicate
 569     // AND assume the check to x passed
 570
 571     assert targetsByAnalysis != null;
 572
 573     assert f == null || i == null;
 574
 575     if( f != null ) {
 576       output.println( "// checks vs. heap results (DEBUG) for "+x+"."+f );
 577     } else {
 578       output.println( "// checks vs. heap results (DEBUG) for "+x+"["+i+"]" );
 579     }
 580
 581
 582     if( targetsByAnalysis == HeapAnalysis.DONTCARE_DREF ) {
 583       output.println( "// ANALYSIS DIDN'T CARE WHAT "+x+" POINTS-TO" );
 584       return;
 585     }
 586
 587
 588     if( targetsByAnalysis.isEmpty() ) {
 589       output.println( "// Should have already checked "+x+" is NULL" );
 590
 591     } else {
 592       output.println( "{" );
 593
 594       // if the ptr is null, that's ok, if not check allocsite
 595       output.println( "if( "+
 596                       buildCode.generateTemp( context, x )+
 597                       " != NULL ) {" );
 598
 599       // precompute the allocsite, if any, of the object we will
 600       // get from hopping through the first ptr
 601       output.println( "int allocsiteOneHop = -1;" );
 602       output.println( buildCode.strObjType+"* objOneHop;" );
 603
 604       if( f != null ) {
 605         if( f.isStatic() ) {
 606
 607           // jjenista - DON'T DEAL WITH THIS RIGHT NOW
 608           //ClassDescriptor cdX = ;
 609           //output.println( "objOneHop = ("+buildCode.strObjType+"*) "+
 610           //
 611           //                "->"+f.getSafeSymbol()+";");
 612           output.println( "}" );
 613           output.println( "}" );
 614           return;
 615
 616         } else {
 617           output.println( "objOneHop = ("+buildCode.strObjType+"*) "+
 618                           buildCode.generateTemp( context, x )+
 619                           "->"+f.getSafeSymbol()+";");
 620         }
 621       } else {
 622         // element access
 623         output.println( "objOneHop = ("+buildCode.strObjType+"*) "+
 624                         "((struct "+x.getType().dereference().getSafeSymbol()+"**)"+
 625                         "(((void*) &("+buildCode.generateTemp( context, x )+"->___length___))+sizeof(int)))"+
 626                         "["+buildCode.generateTemp( context, i )+"];" );
 627       }
 628
 629       output.println( "if( objOneHop != NULL ) { allocsiteOneHop = objOneHop->allocsite; }" );
 630
 631       output.println( "switch( "+
 632                       buildCode.generateTemp( context, x )+
 633                       "->allocsite ) {" );
 634
 635       Iterator<Alloc> kItr = targetsByAnalysis.keySet().iterator();
 636       while( kItr.hasNext() ) {
 637         Alloc k = kItr.next();
 638
 639         output.print( "case "+
 640                       k.getUniqueAllocSiteID()+
 641                       ":" );
 642
 643         Set<Alloc> hopTargets = targetsByAnalysis.get( k );
 644         if( hopTargets == HeapAnalysis.DONTCARE_PTR ) {
 645           output.print( "/* ANALYSIS DOESN'T CARE */" );
 646
 647         } else {
 648           String condition = "allocsiteOneHop != -1";
 649
 650           if( !hopTargets.isEmpty() ) {
 651             condition += " && ";
 652           }
 653
 654           Iterator<Alloc> aItr = hopTargets.iterator();
 655           while( aItr.hasNext() ) {
 656             Alloc a = aItr.next();
 657
 658             condition +=
 659               "allocsiteOneHop != "+
 660               a.getUniqueAllocSiteID();
 661
 662             if( aItr.hasNext() ) {
 663               condition += " && ";
 664             }
 665           }
 666
 667           output.println( "if( "+condition+" ) {" );
 668           printConditionFailed( output, condition, "objOneHop" );
 669           output.println( "}" );
 670         }
 671
 672         output.println( "break;" );
 673       }
 674
 675       output.println( "default:" );
 676       output.println( "// the previous condition for "+x+
 677                       " should already report this failure point" );
 678       output.println( "break;" );
 679       output.println( "}" );
 680       output.println( "}" );
 681       output.println( "}\n" );
 682     }
 683   }
 684
 685
 686
 687
 688   public void printExtraArrayFields(PrintWriter outclassdefs) {}
 689   public void outputTransCode(PrintWriter output) {}
 690   public void buildCodeSetup() {}
 691   public void generateSizeArrayExtensions(PrintWriter outclassdefs) {}
 692   public void preCodeGenInitialization() {}
 693   public void postCodeGenCleanUp() {}
 694   public void additionalClassObjectFields(PrintWriter outclassdefs) {}
 695   public void additionalCodeGen(PrintWriter outmethodheader,
 696                                    PrintWriter outstructs,
 697                                    PrintWriter outmethod) {}
 698   public void additionalCodeAtTopOfMain(PrintWriter outmethod) {}
 699   public void additionalCodeForCommandLineArgs(PrintWriter outmethod, String argsVar) {}
 700   public void additionalCodeAtBottomOfMain(PrintWriter outmethod) {}
 701   public void additionalIncludesMethodsImplementation(PrintWriter outmethod) {}
 702   public void additionalIncludesStructsHeader(PrintWriter outstructs) {}
 703   public void additionalCodeAtTopMethodsImplementation(PrintWriter outmethod) {}
 704   public void additionalCodeNewObject(PrintWriter outmethod, String dstVar, FlatNew flatNew) {}
 705   public void additionalCodeNewStringLiteral(PrintWriter output, String dstVar) {}
 706 }