← Back to branch summary

~ubuntu-branches/debian/sid/clamav/sid

« back to all changes in this revision

Viewing changes to .pc/0016-add-support-for-LLVM-3.5.patch/libclamav/c++/ClamBCRTChecks.cpp

  • Committer: Package Import Robot
  • Author(s): Andreas Cadhalpun, Andreas Cadhalpun, Sebastian Andrzej Siewior, Frans Spiesschaert
  • Date: 2014-10-15 06:50:20 UTC
  • mfrom: (1.3.13) (42.1.4 experimental)
  • Revision ID: package-import@ubuntu.com-20141015065020-0cpy1hdueggaw35s
Tags: 0.98.5~rc1+dfsg-1
http://bugs.debian.org/763634
[ Andreas Cadhalpun ]
* Import new upstream release candidate.
* Drop patches included upstream and update the others.
* Add 4 new symbols to libclamav6.symbols.
* Fix debian/copyright.
* Update lintian overrides.
* Update Standards-Version to 3.9.6 (no changes needed).
* Add Breaks and Replaces for old clamd package to clamdscan.
* Remove unnecessary shlibs:Depends from clamav-dbg.
* Add patches to support LLVM 3.5.

[ Sebastian Andrzej Siewior ]
* Add embedded copy of libmspack to be used as fallback, when libmspack-dev
  is not available.

[ Frans Spiesschaert ]
* Updated Dutch Debconf template translation (Closes: #763634)

Show diffs side-by-side

added added

removed removed

Lines of Context:
.pc/0016-add-support-for-LLVM-3.5.patch/libclamav/c++/ClamBCRTChecks.cpp
 
1
/*
 
2
 *  Compile LLVM bytecode to ClamAV bytecode.
 
3
 *
 
4
 *  Copyright (C) 2009-2013 Sourcefire, Inc.
 
5
 *  Copyright (C) 2014 Cisco Systems, Inc. and/or its affiliates.
 
6
 *  All rights reserved.
 
7
 *
 
8
 *  Authors: Török Edvin, Kevin Lin
 
9
 *
 
10
 *  This program is free software; you can redistribute it and/or modify
 
11
 *  it under the terms of the GNU General Public License version 2 as
 
12
 *  published by the Free Software Foundation.
 
13
 *
 
14
 *  This program is distributed in the hope that it will be useful,
 
15
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
16
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
17
 *  GNU General Public License for more details.
 
18
 *
 
19
 *  You should have received a copy of the GNU General Public License
 
20
 *  along with this program; if not, write to the Free Software
 
21
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 
22
 *  MA 02110-1301, USA.
 
23
 */
 
24
#define DEBUG_TYPE "clambc-rtcheck"
 
25
#include "ClamBCModule.h"
 
26
#include "ClamBCDiagnostics.h"
 
27
#include "llvm30_compat.h" /* libclamav-specific */
 
28
#include "llvm/ADT/DenseSet.h"
 
29
#include "llvm/ADT/PostOrderIterator.h"
 
30
#include "llvm/ADT/SCCIterator.h"
 
31
#include "llvm/Analysis/CallGraph.h"
 
32
#include "llvm/Analysis/Verifier.h"
 
33
#if LLVM_VERSION < 32
 
34
#include "llvm/Analysis/DebugInfo.h"
 
35
#else
 
36
#include "llvm/DebugInfo.h"
 
37
#endif
 
38
#include "llvm/Analysis/Dominators.h"
 
39
#include "llvm/Analysis/ConstantFolding.h"
 
40
#if LLVM_VERSION < 29
 
41
//#include "llvm/Analysis/LiveValues.h" (unused)
 
42
#include "llvm/Analysis/PointerTracking.h"
 
43
#else
 
44
#include "llvm/Analysis/ValueTracking.h"
 
45
#include "PointerTracking.h" /* included from old LLVM source */
 
46
#endif
 
47
#include "llvm/Analysis/ScalarEvolution.h"
 
48
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
 
49
#include "llvm/Analysis/ScalarEvolutionExpander.h"
 
50
#include "llvm/Config/config.h"
 
51
#include "llvm/Pass.h"
 
52
#include "llvm/Support/CommandLine.h"
 
53
#include "llvm/Support/DataFlow.h"
 
54
#include "llvm/Support/InstIterator.h"
 
55
#include "llvm/Support/GetElementPtrTypeIterator.h"
 
56
#include "llvm/ADT/DepthFirstIterator.h"
 
57
#include "llvm/Transforms/Scalar.h"
 
58
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
59
#include "llvm/Support/Debug.h"
 
60
#if LLVM_VERSION < 32
 
61
#include "llvm/Target/TargetData.h"
 
62
#elif LLVM_VERSION < 33
 
63
#include "llvm/DataLayout.h"
 
64
#else
 
65
#include "llvm/IR/DataLayout.h"
 
66
#endif
 
67
#if LLVM_VERSION < 33
 
68
#include "llvm/DerivedTypes.h"
 
69
#include "llvm/Instructions.h"
 
70
#include "llvm/IntrinsicInst.h"
 
71
#include "llvm/Intrinsics.h"
 
72
#include "llvm/LLVMContext.h"
 
73
#include "llvm/Module.h"
 
74
#include "llvm/Support/InstVisitor.h"
 
75
#else
 
76
#include "llvm/IR/DerivedTypes.h"
 
77
#include "llvm/IR/Instructions.h"
 
78
#include "llvm/IR/IntrinsicInst.h"
 
79
#include "llvm/IR/Intrinsics.h"
 
80
#include "llvm/IR/LLVMContext.h"
 
81
#include "llvm/IR/Module.h"
 
82
#include "llvm/InstVisitor.h"
 
83
#endif
 
84
 
 
85
#define DEFINEPASS(passname) passname() : FunctionPass(ID)
 
86
 
 
87
using namespace llvm;
 
88
#if LLVM_VERSION < 29
 
89
/* function is succeeded in later LLVM with LLVM correspoding standalone */
 
90
static Value *GetUnderlyingObject(Value *P, TargetData *TD)
 
91
{
 
92
    return P->getUnderlyingObject();
 
93
}
 
94
#endif
 
95
 
 
96
namespace llvm {
 
97
  class PtrVerifier;
 
98
#if LLVM_VERSION >= 29
 
99
  void initializePtrVerifierPass(PassRegistry&);
 
100
#endif
 
101
 
 
102
  class PtrVerifier : public FunctionPass {
 
103
  private:
 
104
      DenseSet<Function*> badFunctions;
 
105
      std::vector<Instruction*> delInst;
 
106
      CallGraphNode *rootNode;
 
107
  public:
 
108
      static char ID;
 
109
      DEFINEPASS(PtrVerifier), rootNode(0), PT(), TD(), SE(), expander(),
 
110
          DT(), AbrtBB(), Changed(false), valid(false), EP() {
 
111
#if LLVM_VERSION >= 29
 
112
          initializePtrVerifierPass(*PassRegistry::getPassRegistry());
 
113
#endif
 
114
      }
 
115
 
 
116
      virtual bool runOnFunction(Function &F) {
 
117
          /*
 
118
#ifndef CLAMBC_COMPILER
 
119
          // Bytecode was already verified and had stack protector applied.
 
120
          // We get called again because ALL bytecode functions loaded are part of
 
121
          // the same module.
 
122
          if (F.hasFnAttr(Attribute::StackProtectReq))
 
123
              return false;
 
124
#endif
 
125
          */
 
126
 
 
127
          DEBUG(errs() << "Running on " << F.getName() << "\n");
 
128
          DEBUG(F.dump());
 
129
          Changed = false;
 
130
          BaseMap.clear();
 
131
          BoundsMap.clear();
 
132
          delInst.clear();
 
133
          AbrtBB = 0;
 
134
          valid = true;
 
135
 
 
136
          if (!rootNode) {
 
137
              rootNode = getAnalysis<CallGraph>().getRoot();
 
138
              // No recursive functions for now.
 
139
              // In the future we may insert runtime checks for stack depth.
 
140
              for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode),
 
141
                       E = scc_end(rootNode); SCCI != E; ++SCCI) {
 
142
                  const std::vector<CallGraphNode*> &nextSCC = *SCCI;
 
143
                  if (nextSCC.size() > 1 || SCCI.hasLoop()) {
 
144
                      errs() << "INVALID: Recursion detected, callgraph SCC components: ";
 
145
                      for (std::vector<CallGraphNode*>::const_iterator I = nextSCC.begin(),
 
146
                               E = nextSCC.end(); I != E; ++I) {
 
147
                          Function *FF = (*I)->getFunction();
 
148
                          if (FF) {
 
149
                              errs() << FF->getName() << ", ";
 
150
                              badFunctions.insert(FF);
 
151
                          }
 
152
                      }
 
153
                      if (SCCI.hasLoop())
 
154
                          errs() << "(self-loop)";
 
155
                      errs() << "\n";
 
156
                  }
 
157
                  // we could also have recursion via function pointers, but we don't
 
158
                  // allow calls to unknown functions, see runOnFunction() below
 
159
              }
 
160
          }
 
161
 
 
162
          BasicBlock::iterator It = F.getEntryBlock().begin();
 
163
          while (isa<AllocaInst>(It) || isa<PHINode>(It)) ++It;
 
164
          EP = &*It;
 
165
#if LLVM_VERSION < 32
 
166
          TD = &getAnalysis<TargetData>();
 
167
#else
 
168
          TD = &getAnalysis<DataLayout>();
 
169
#endif
 
170
          SE = &getAnalysis<ScalarEvolution>();
 
171
          PT = &getAnalysis<PointerTracking>();
 
172
          DT = &getAnalysis<DominatorTree>();
 
173
          expander = new SCEVExpander(*SE OPT("SCEVexpander"));
 
174
 
 
175
          std::vector<Instruction*> insns;
 
176
 
 
177
          BasicBlock *LastBB = 0;
 
178
          for (inst_iterator I=inst_begin(F),E=inst_end(F); I != E;++I) {
 
179
              Instruction *II = &*I;
 
180
              /* only appears in the libclamav version */
 
181
              if (II->getParent() != LastBB) {
 
182
                  LastBB = II->getParent();
 
183
                  if (DT->getNode(LastBB) == 0)
 
184
                      continue;
 
185
              }
 
186
              /* end-block */
 
187
              if (isa<LoadInst>(II) || isa<StoreInst>(II) || isa<MemIntrinsic>(II))
 
188
                  insns.push_back(II);
 
189
              else if (CallInst *CI = dyn_cast<CallInst>(II)) {
 
190
                  Value *V = CI->getCalledValue()->stripPointerCasts();
 
191
                  Function *F = dyn_cast<Function>(V);
 
192
                  if (!F) {
 
193
                      printLocation(CI, true);
 
194
                      errs() << "Could not determine call target\n";
 
195
                      valid = 0;
 
196
                      continue;
 
197
                  }
 
198
                  // this statement disable checks on user-defined CallInst
 
199
                  //if (!F->isDeclaration())
 
200
                  //continue;
 
201
                  insns.push_back(CI);
 
202
              }
 
203
          }
 
204
 
 
205
          for (unsigned Idx = 0; Idx < insns.size(); ++Idx) {
 
206
              Instruction *II = insns[Idx];
 
207
              DEBUG(dbgs() << "checking " << *II << "\n");
 
208
              if (LoadInst *LI = dyn_cast<LoadInst>(II)) {
 
209
                  constType *Ty = LI->getType();
 
210
                  valid &= validateAccess(LI->getPointerOperand(),
 
211
                                          TD->getTypeAllocSize(Ty), LI);
 
212
              } else if (StoreInst *SI = dyn_cast<StoreInst>(II)) {
 
213
                  constType *Ty = SI->getOperand(0)->getType();
 
214
                  valid &= validateAccess(SI->getPointerOperand(),
 
215
                                          TD->getTypeAllocSize(Ty), SI);
 
216
              } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(II)) {
 
217
                  valid &= validateAccess(MI->getDest(), MI->getLength(), MI);
 
218
                  if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) {
 
219
                      valid &= validateAccess(MTI->getSource(), MI->getLength(), MI);
 
220
                  }
 
221
              } else if (CallInst *CI = dyn_cast<CallInst>(II)) {
 
222
                  Value *V = CI->getCalledValue()->stripPointerCasts();
 
223
                  Function *F = cast<Function>(V);
 
224
                  constFunctionType *FTy = F->getFunctionType();
 
225
                  CallSite CS(CI);
 
226
                  if (F->getName().equals("memcmp") && FTy->getNumParams() == 3) {
 
227
                      valid &= validateAccess(CS.getArgument(0), CS.getArgument(2), CI);
 
228
                      valid &= validateAccess(CS.getArgument(1), CS.getArgument(2), CI);
 
229
                      continue;
 
230
                  }
 
231
                  unsigned i;
 
232
#ifdef CLAMBC_COMPILER
 
233
                  i = 0;
 
234
#else
 
235
                  i = 1;// skip hidden ctx*
 
236
#endif
 
237
                  for (;i<FTy->getNumParams();i++) {
 
238
                      if (isa<PointerType>(FTy->getParamType(i))) {
 
239
                          Value *Ptr = CS.getArgument(i);
 
240
                          if (i+1 >= FTy->getNumParams()) {
 
241
                              printLocation(CI, false);
 
242
                              errs() << "Call to external function with pointer parameter last"
 
243
                                  " cannot be analyzed\n";
 
244
                              errs() << *CI << "\n";
 
245
                              valid = 0;
 
246
                              break;
 
247
                          }
 
248
                          Value *Size = CS.getArgument(i+1);
 
249
                          if (!Size->getType()->isIntegerTy()) {
 
250
                              printLocation(CI, false);
 
251
                              errs() << "Pointer argument must be followed by integer argument"
 
252
                                  " representing its size\n";
 
253
                              errs() << *CI << "\n";
 
254
                              valid = 0;
 
255
                              break;
 
256
                          }
 
257
                          valid &= validateAccess(Ptr, Size, CI);
 
258
                      }
 
259
                  }
 
260
              }
 
261
          }
 
262
          if (badFunctions.count(&F))
 
263
              valid = 0;
 
264
 
 
265
          if (!valid) {
 
266
              DEBUG(F.dump());
 
267
              ClamBCModule::stop("Verification found errors!", &F);
 
268
              // replace function with call to abort
 
269
              std::vector<constType*>args;
 
270
              FunctionType* abrtTy = FunctionType::get(Type::getVoidTy(F.getContext()),args,false);
 
271
              Constant *func_abort = F.getParent()->getOrInsertFunction("abort", abrtTy);
 
272
 
 
273
              BasicBlock *BB = &F.getEntryBlock();
 
274
              Instruction *I = &*BB->begin();
 
275
              Instruction *UI = new UnreachableInst(F.getContext(), I);
 
276
              CallInst *AbrtC = CallInst::Create(func_abort, "", UI);
 
277
              AbrtC->setCallingConv(CallingConv::C);
 
278
              AbrtC->setTailCall(true);
 
279
#if LLVM_VERSION < 32
 
280
              AbrtC->setDoesNotReturn(true);
 
281
              AbrtC->setDoesNotThrow(true);
 
282
#else
 
283
              AbrtC->setDoesNotReturn();
 
284
              AbrtC->setDoesNotThrow();
 
285
#endif
 
286
              // remove all instructions from entry
 
287
              BasicBlock::iterator BBI = I, BBE=BB->end();
 
288
              while (BBI != BBE) {
 
289
                  if (!BBI->use_empty())
 
290
                      BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
 
291
                  BB->getInstList().erase(BBI++);
 
292
              }
 
293
          }
 
294
 
 
295
          // bb#9967 - deleting obsolete termination instructions
 
296
          for (unsigned i = 0; i < delInst.size(); ++i)
 
297
              delInst[i]->eraseFromParent();
 
298
 
 
299
          delete expander;
 
300
          return Changed;
 
301
      }
 
302
 
 
303
      virtual void releaseMemory() {
 
304
          badFunctions.clear();
 
305
      }
 
306
 
 
307
      virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
308
#if LLVM_VERSION < 32
 
309
          AU.addRequired<TargetData>();
 
310
#else
 
311
          AU.addRequired<DataLayout>();
 
312
#endif
 
313
          AU.addRequired<DominatorTree>();
 
314
          AU.addRequired<ScalarEvolution>();
 
315
          AU.addRequired<PointerTracking>();
 
316
          AU.addRequired<CallGraph>();
 
317
      }
 
318
 
 
319
      bool isValid() const { return valid; }
 
320
  private:
 
321
      PointerTracking *PT;
 
322
#if LLVM_VERSION < 32
 
323
      TargetData *TD;
 
324
#else
 
325
      DataLayout *TD;
 
326
#endif
 
327
      ScalarEvolution *SE;
 
328
      SCEVExpander *expander;
 
329
      DominatorTree *DT;
 
330
      DenseMap<Value*, Value*> BaseMap;
 
331
      DenseMap<Value*, Value*> BoundsMap;
 
332
      BasicBlock *AbrtBB;
 
333
      bool Changed;
 
334
      bool valid;
 
335
      Instruction *EP;
 
336
 
 
337
      Instruction *getInsertPoint(Value *V)
 
338
      {
 
339
          BasicBlock::iterator It = EP;
 
340
          if (Instruction *I = dyn_cast<Instruction>(V)) {
 
341
              It = I;
 
342
              ++It;
 
343
          }
 
344
          return &*It;
 
345
      }
 
346
 
 
347
      Value *getPointerBase(Value *Ptr)
 
348
      {
 
349
          if (BaseMap.count(Ptr))
 
350
              return BaseMap[Ptr];
 
351
          Value *P = Ptr->stripPointerCasts();
 
352
          if (BaseMap.count(P)) {
 
353
              return BaseMap[Ptr] = BaseMap[P];
 
354
          }
 
355
          Value *P2 = GetUnderlyingObject(P, TD);
 
356
          if (P2 != P) {
 
357
              Value *V = getPointerBase(P2);
 
358
              return BaseMap[Ptr] = V;
 
359
          }
 
360
 
 
361
          constType *P8Ty =
 
362
              PointerType::getUnqual(Type::getInt8Ty(Ptr->getContext()));
 
363
          if (PHINode *PN = dyn_cast<PHINode>(Ptr)) {
 
364
              BasicBlock::iterator It = PN;
 
365
              ++It;
 
366
              PHINode *newPN = PHINode::Create(P8Ty, HINT(PN->getNumIncomingValues()) ".verif.base", &*It);
 
367
              Changed = true;
 
368
              BaseMap[Ptr] = newPN;
 
369
 
 
370
              for (unsigned i=0;i<PN->getNumIncomingValues();i++) {
 
371
                  Value *Inc = PN->getIncomingValue(i);
 
372
                  Value *V = getPointerBase(Inc);
 
373
                  newPN->addIncoming(V, PN->getIncomingBlock(i));
 
374
              }
 
375
              return newPN;
 
376
          }
 
377
          if (SelectInst *SI = dyn_cast<SelectInst>(Ptr)) {
 
378
              BasicBlock::iterator It = SI;
 
379
              ++It;
 
380
              Value *TrueB = getPointerBase(SI->getTrueValue());
 
381
              Value *FalseB = getPointerBase(SI->getFalseValue());
 
382
              if (TrueB && FalseB) {
 
383
                  SelectInst *NewSI = SelectInst::Create(SI->getCondition(), TrueB,
 
384
                                                         FalseB, ".select.base", &*It);
 
385
                  Changed = true;
 
386
                  return BaseMap[Ptr] = NewSI;
 
387
              }
 
388
          }
 
389
          if (Ptr->getType() != P8Ty) {
 
390
              if (Constant *C = dyn_cast<Constant>(Ptr))
 
391
                  Ptr = ConstantExpr::getPointerCast(C, P8Ty);
 
392
              else {
 
393
                  Instruction *I = getInsertPoint(Ptr);
 
394
                  Ptr = new BitCastInst(Ptr, P8Ty, "", I);
 
395
              }
 
396
          }
 
397
          return BaseMap[Ptr] = Ptr;
 
398
      }
 
399
 
 
400
      Value* getValAtIdx(Function *F, unsigned Idx) {
 
401
          Value *Val= NULL;
 
402
 
 
403
          // check if accessed Idx is within function parameter list
 
404
          if (Idx < F->arg_size()) {
 
405
              Function::arg_iterator It = F->arg_begin();
 
406
              Function::arg_iterator ItEnd = F->arg_end();
 
407
              for (unsigned i = 0; i < Idx; ++i, ++It) {
 
408
                  // redundant check, should not be possible
 
409
                  if (It == ItEnd) {
 
410
                      // Houston, the impossible has become possible
 
411
                      //printDiagnostic("Idx is outside of Function parameters", F);
 
412
                      errs() << "Idx is outside of Function parameters\n";
 
413
                      errs() << *F << "\n";
 
414
                      //valid = 0;
 
415
                      break;
 
416
                  }
 
417
              }
 
418
              // retrieve value ptr of argument of F at Idx
 
419
              Val = &(*It);
 
420
          }
 
421
          else {
 
422
              // Idx is outside function parameter list
 
423
              //printDiagnostic("Idx is outside of Function parameters", F);
 
424
              errs() << "Idx is outside of Function parameters\n";
 
425
              errs() << *F << "\n";
 
426
              //valid = 0;
 
427
          }
 
428
          return Val;
 
429
      }
 
430
 
 
431
      Value* getPointerBounds(Value *Base) {
 
432
          if (BoundsMap.count(Base))
 
433
              return BoundsMap[Base];
 
434
          constType *I64Ty =
 
435
              Type::getInt64Ty(Base->getContext());
 
436
 
 
437
          if (Base->getType()->isPointerTy()) {
 
438
              if (Argument *A = dyn_cast<Argument>(Base)) {
 
439
                  Function *F = A->getParent();
 
440
                  const FunctionType *FT = F->getFunctionType();
 
441
 
 
442
                  bool checks = true;
 
443
                  // last argument check
 
444
                  if (A->getArgNo() == (FT->getNumParams()-1)) {
 
445
                      //printDiagnostic("pointer argument cannot be last argument", F);
 
446
                      errs() << "pointer argument cannot be last argument\n";
 
447
                      errs() << *F << "\n";
 
448
                      checks = false;
 
449
                  }
 
450
 
 
451
                  // argument after pointer MUST be a integer (unsigned probably too)
 
452
                  if (checks && !FT->getParamType(A->getArgNo()+1)->isIntegerTy()) {
 
453
                      //printDiagnostic("argument following pointer argument is not an integer", F);
 
454
                      errs() << "argument following pointer argument is not an integer\n";
 
455
                      errs() << *F << "\n";
 
456
                      checks = false;
 
457
                  }
 
458
 
 
459
                  if (checks)
 
460
                      return BoundsMap[Base] = getValAtIdx(F, A->getArgNo()+1);
 
461
              }
 
462
          }
 
463
 
 
464
#ifndef CLAMBC_COMPILER
 
465
          // first arg is hidden ctx
 
466
          if (Argument *A = dyn_cast<Argument>(Base)) {
 
467
              if (A->getArgNo() == 0) {
 
468
                  constType *Ty = cast<PointerType>(A->getType())->getElementType();
 
469
                  return ConstantInt::get(I64Ty, TD->getTypeAllocSize(Ty));
 
470
              }
 
471
          }
 
472
          if (LoadInst *LI = dyn_cast<LoadInst>(Base)) {
 
473
              Value *V = GetUnderlyingObject(LI->getPointerOperand()->stripPointerCasts(), TD);
 
474
              if (Argument *A = dyn_cast<Argument>(V)) {
 
475
                  if (A->getArgNo() == 0) {
 
476
                      // pointers from hidden ctx are trusted to be at least the
 
477
                      // size they say they are
 
478
                      constType *Ty = cast<PointerType>(LI->getType())->getElementType();
 
479
                      return ConstantInt::get(I64Ty, TD->getTypeAllocSize(Ty));
 
480
                  }
 
481
              }
 
482
          }
 
483
#endif
 
484
          if (PHINode *PN = dyn_cast<PHINode>(Base)) {
 
485
              BasicBlock::iterator It = PN;
 
486
              ++It;
 
487
              PHINode *newPN = PHINode::Create(I64Ty, HINT(PN->getNumIncomingValues()) ".verif.bounds", &*It);
 
488
              Changed = true;
 
489
              BoundsMap[Base] = newPN;
 
490
 
 
491
              bool good = true;
 
492
              for (unsigned i=0;i<PN->getNumIncomingValues();i++) {
 
493
                  Value *Inc = PN->getIncomingValue(i);
 
494
                  Value *B = getPointerBounds(Inc);
 
495
                  if (!B) {
 
496
                      good = false;
 
497
                      B = ConstantInt::get(newPN->getType(), 0);
 
498
                      DEBUG(dbgs() << "bounds not found while solving phi node: " << *Inc
 
499
                            << "\n");
 
500
                  }
 
501
                  newPN->addIncoming(B, PN->getIncomingBlock(i));
 
502
              }
 
503
              if (!good)
 
504
                  newPN = 0;
 
505
              return BoundsMap[Base] = newPN;
 
506
          }
 
507
          if (SelectInst *SI = dyn_cast<SelectInst>(Base)) {
 
508
              BasicBlock::iterator It = SI;
 
509
              ++It;
 
510
              Value *TrueB = getPointerBounds(SI->getTrueValue());
 
511
              Value *FalseB = getPointerBounds(SI->getFalseValue());
 
512
              if (TrueB && FalseB) {
 
513
                  SelectInst *NewSI = SelectInst::Create(SI->getCondition(), TrueB,
 
514
                                                         FalseB, ".select.bounds", &*It);
 
515
                  Changed = true;
 
516
                  return BoundsMap[Base] = NewSI;
 
517
              }
 
518
          }
 
519
 
 
520
          constType *Ty;
 
521
          Value *V = PT->computeAllocationCountValue(Base, Ty);
 
522
          if (!V) {
 
523
              Base = Base->stripPointerCasts();
 
524
              if (CallInst *CI = dyn_cast<CallInst>(Base)) {
 
525
                  Function *F = CI->getCalledFunction();
 
526
                  constFunctionType *FTy = F->getFunctionType();
 
527
                  // last operand is always size for this API call kind
 
528
                  if (F->isDeclaration() && FTy->getNumParams() > 0) {
 
529
                      CallSite CS(CI);
 
530
                      if (FTy->getParamType(FTy->getNumParams()-1)->isIntegerTy())
 
531
                          V = CS.getArgument(FTy->getNumParams()-1);
 
532
                  }
 
533
              }
 
534
              if (!V)
 
535
                  return BoundsMap[Base] = 0;
 
536
          } else {
 
537
              unsigned size = TD->getTypeAllocSize(Ty);
 
538
              if (size > 1) {
 
539
                  Constant *C = cast<Constant>(V);
 
540
                  C = ConstantExpr::getMul(C,
 
541
                                           ConstantInt::get(Type::getInt32Ty(C->getContext()),
 
542
                                                            size));
 
543
                  V = C;
 
544
              }
 
545
          }
 
546
          if (V->getType() != I64Ty) {
 
547
              if (Constant *C = dyn_cast<Constant>(V))
 
548
                  V = ConstantExpr::getZExt(C, I64Ty);
 
549
              else {
 
550
                  Instruction *I = getInsertPoint(V);
 
551
                  V = new ZExtInst(V, I64Ty, "", I);
 
552
              }
 
553
          }
 
554
          return BoundsMap[Base] = V;
 
555
      }
 
556
 
 
557
      MDNode *getLocation(Instruction *I, bool &Approximate, unsigned MDDbgKind)
 
558
      {
 
559
          Approximate = false;
 
560
          if (MDNode *Dbg = I->getMetadata(MDDbgKind))
 
561
              return Dbg;
 
562
          if (!MDDbgKind)
 
563
              return 0;
 
564
          Approximate = true;
 
565
          BasicBlock::iterator It = I;
 
566
          while (It != I->getParent()->begin()) {
 
567
              --It;
 
568
              if (MDNode *Dbg = It->getMetadata(MDDbgKind))
 
569
                  return Dbg;
 
570
          }
 
571
          BasicBlock *BB = I->getParent();
 
572
          while ((BB = BB->getUniquePredecessor())) {
 
573
              It = BB->end();
 
574
              while (It != BB->begin()) {
 
575
                  --It;
 
576
                  if (MDNode *Dbg = It->getMetadata(MDDbgKind))
 
577
                      return Dbg;
 
578
              }
 
579
          }
 
580
          return 0;
 
581
      }
 
582
 
 
583
      bool insertCheck(const SCEV *Idx, const SCEV *Limit, Instruction *I,
 
584
                       bool strict)
 
585
      {
 
586
          if (isa<SCEVCouldNotCompute>(Idx) && isa<SCEVCouldNotCompute>(Limit)) {
 
587
              errs() << "Could not compute the index and the limit!: \n" << *I << "\n";
 
588
              return false;
 
589
          }
 
590
          if (isa<SCEVCouldNotCompute>(Idx)) {
 
591
              errs() << "Could not compute index: \n" << *I << "\n";
 
592
              return false;
 
593
          }
 
594
          if (isa<SCEVCouldNotCompute>(Limit)) {
 
595
              errs() << "Could not compute limit: " << *I << "\n";
 
596
              return false;
 
597
          }
 
598
          BasicBlock *BB = I->getParent();
 
599
          BasicBlock::iterator It = I;
 
600
          BasicBlock *newBB = SplitBlock(BB, &*It, this);
 
601
          PHINode *PN;
 
602
          unsigned MDDbgKind = I->getContext().getMDKindID("dbg");
 
603
          //verifyFunction(*BB->getParent());
 
604
          if (!AbrtBB) {
 
605
              std::vector<constType*>args;
 
606
              FunctionType* abrtTy = FunctionType::get(Type::getVoidTy(BB->getContext()),args,false);
 
607
              args.push_back(Type::getInt32Ty(BB->getContext()));
 
608
              FunctionType* rterrTy = FunctionType::get(Type::getInt32Ty(BB->getContext()),args,false);
 
609
              Constant *func_abort = BB->getParent()->getParent()->getOrInsertFunction("abort", abrtTy);
 
610
              Constant *func_rterr = BB->getParent()->getParent()->getOrInsertFunction("bytecode_rt_error",
 
611
                                                                                       rterrTy);
 
612
              AbrtBB = BasicBlock::Create(BB->getContext(), "rterr.trig", BB->getParent());
 
613
              
 
614
              PN = PHINode::Create(Type::getInt32Ty(BB->getContext()),HINT(1) "",
 
615
                                   AbrtBB);
 
616
              if (MDDbgKind) {
 
617
                  CallInst *RtErrCall = CallInst::Create(func_rterr, PN, "", AbrtBB);
 
618
                  RtErrCall->setCallingConv(CallingConv::C);
 
619
                  RtErrCall->setTailCall(true);
 
620
#if LLVM_VERSION < 32
 
621
                  RtErrCall->setDoesNotThrow(true);
 
622
#else
 
623
                  RtErrCall->setDoesNotThrow();
 
624
#endif
 
625
              }
 
626
              CallInst* AbrtC = CallInst::Create(func_abort, "", AbrtBB);
 
627
              AbrtC->setCallingConv(CallingConv::C);
 
628
              AbrtC->setTailCall(true);
 
629
#if LLVM_VERSION < 32
 
630
              AbrtC->setDoesNotReturn(true);
 
631
              AbrtC->setDoesNotThrow(true);
 
632
#else
 
633
              AbrtC->setDoesNotReturn();
 
634
              AbrtC->setDoesNotThrow();
 
635
#endif
 
636
              new UnreachableInst(BB->getContext(), AbrtBB);
 
637
              DT->addNewBlock(AbrtBB, BB);
 
638
              //verifyFunction(*BB->getParent());
 
639
          } else {
 
640
              PN = cast<PHINode>(AbrtBB->begin());
 
641
          }
 
642
          unsigned locationid = 0;
 
643
          bool Approximate;
 
644
          if (MDNode *Dbg = getLocation(I, Approximate, MDDbgKind)) {
 
645
              DILocation Loc(Dbg);
 
646
              locationid = Loc.getLineNumber() << 8;
 
647
              unsigned col = Loc.getColumnNumber();
 
648
              if (col > 254)
 
649
                  col = 254;
 
650
              if (Approximate)
 
651
                  col = 255;
 
652
              locationid |= col;
 
653
          }
 
654
          PN->addIncoming(ConstantInt::get(Type::getInt32Ty(BB->getContext()),
 
655
                                           locationid), BB);
 
656
          TerminatorInst *TI = BB->getTerminator();
 
657
          Value *IdxV = expander->expandCodeFor(Idx, Limit->getType(), TI);
 
658
          Value *LimitV = expander->expandCodeFor(Limit, Limit->getType(), TI);
 
659
          if (isa<Instruction>(IdxV) &&
 
660
              !DT->dominates(cast<Instruction>(IdxV)->getParent(),I->getParent())) {
 
661
              printLocation(I, true);
 
662
              errs() << "basic block with value [ " << IdxV->getName();
 
663
              errs() << " ] with limit [ " << LimitV->getName();
 
664
              errs() << " ] does not dominate" << *I << "\n";
 
665
              return false;
 
666
          }
 
667
          if (isa<Instruction>(LimitV) &&
 
668
              !DT->dominates(cast<Instruction>(LimitV)->getParent(),I->getParent())) {
 
669
              printLocation(I, true);
 
670
              errs() << "basic block with limit [" << LimitV->getName();
 
671
              errs() << " ] on value [ " << IdxV->getName();
 
672
              errs() << " ] does not dominate" << *I << "\n";
 
673
              return false;
 
674
          }
 
675
          Value *Cond = new ICmpInst(TI, strict ?
 
676
                                     ICmpInst::ICMP_ULT :
 
677
                                     ICmpInst::ICMP_ULE, IdxV, LimitV);
 
678
          BranchInst::Create(newBB, AbrtBB, Cond, TI);
 
679
          //TI->eraseFromParent();
 
680
          delInst.push_back(TI);
 
681
          // Update dominator info
 
682
          BasicBlock *DomBB =
 
683
              DT->findNearestCommonDominator(BB, DT->getNode(AbrtBB)->getIDom()->getBlock());
 
684
          DT->changeImmediateDominator(AbrtBB, DomBB);
 
685
          return true;
 
686
      }
 
687
 
 
688
      static void MakeCompatible(ScalarEvolution *SE, const SCEV*& LHS, const SCEV*& RHS)
 
689
      {
 
690
          if (const SCEVZeroExtendExpr *ZL = dyn_cast<SCEVZeroExtendExpr>(LHS))
 
691
              LHS = ZL->getOperand();
 
692
          if (const SCEVZeroExtendExpr *ZR = dyn_cast<SCEVZeroExtendExpr>(RHS))
 
693
              RHS = ZR->getOperand();
 
694
 
 
695
          constType* LTy = SE->getEffectiveSCEVType(LHS->getType());
 
696
          constType *RTy = SE->getEffectiveSCEVType(RHS->getType());
 
697
          if (SE->getTypeSizeInBits(RTy) > SE->getTypeSizeInBits(LTy))
 
698
              LTy = RTy;
 
699
          LHS = SE->getNoopOrZeroExtend(LHS, LTy);
 
700
          RHS = SE->getNoopOrZeroExtend(RHS, LTy);
 
701
      }
 
702
 
 
703
      bool checkCond(Instruction *ICI, Instruction *I, bool equal)
 
704
      {
 
705
          for (Value::use_iterator JU=ICI->use_begin(),JUE=ICI->use_end();
 
706
               JU != JUE; ++JU) {
 
707
              Value *JU_V = *JU;
 
708
              if (BranchInst *BI = dyn_cast<BranchInst>(JU_V)) {
 
709
                  if (!BI->isConditional())
 
710
                      continue;
 
711
                  BasicBlock *S = BI->getSuccessor(equal);
 
712
                  if (DT->dominates(S, I->getParent()))
 
713
                      return true;
 
714
              }
 
715
              if (BinaryOperator *BI = dyn_cast<BinaryOperator>(JU_V)) {
 
716
                  if (BI->getOpcode() == Instruction::Or &&
 
717
                      checkCond(BI, I, equal))
 
718
                      return true;
 
719
                  if (BI->getOpcode() == Instruction::And &&
 
720
                      checkCond(BI, I, !equal))
 
721
                      return true;
 
722
              }
 
723
          }
 
724
          return false;
 
725
      }
 
726
 
 
727
      bool checkCondition(Instruction *CI, Instruction *I)
 
728
      {
 
729
          for (Value::use_iterator U=CI->use_begin(),UE=CI->use_end();
 
730
               U != UE; ++U) {
 
731
              Value *U_V = *U;
 
732
              if (ICmpInst *ICI = dyn_cast<ICmpInst>(U_V)) {
 
733
                  if (ICI->getOperand(0)->stripPointerCasts() == CI &&
 
734
                      isa<ConstantPointerNull>(ICI->getOperand(1))) {
 
735
                      if (checkCond(ICI, I, ICI->getPredicate() == ICmpInst::ICMP_EQ))
 
736
                          return true;
 
737
                  }
 
738
              }
 
739
          }
 
740
          return false;
 
741
      }
 
742
 
 
743
      bool validateAccess(Value *Pointer, Value *Length, Instruction *I)
 
744
      {
 
745
          // get base
 
746
          Value *Base = getPointerBase(Pointer);
 
747
 
 
748
          Value *SBase = Base->stripPointerCasts();
 
749
          // get bounds
 
750
          Value *Bounds = getPointerBounds(SBase);
 
751
          if (!Bounds) {
 
752
              printLocation(I, true);
 
753
              errs() << "no bounds for base ";
 
754
              printValue(SBase);
 
755
              errs() << " while checking access to ";
 
756
              printValue(Pointer);
 
757
              errs() << " of length ";
 
758
              printValue(Length);
 
759
              errs() << "\n";
 
760
 
 
761
              return false;
 
762
          }
 
763
 
 
764
          // checks if a NULL pointer check (returned from function) is made:
 
765
          if (CallInst *CI = dyn_cast<CallInst>(Base->stripPointerCasts())) {
 
766
              // by checking if use is in the same block (i.e. no branching decisions)
 
767
              if (I->getParent() == CI->getParent()) {
 
768
                  printLocation(I, true);
 
769
                  errs() << "no null pointer check of pointer ";
 
770
                  printValue(Base, false, true);
 
771
                  errs() << " obtained by function call";
 
772
                  errs() << " before use in same block\n";
 
773
                  return false;
 
774
              }
 
775
              // by checking if a conditional contains the values in question somewhere
 
776
              // between their usage
 
777
              if (!checkCondition(CI, I)) {
 
778
                  printLocation(I, true);
 
779
                  errs() << "no null pointer check of pointer ";
 
780
                  printValue(Base, false, true);
 
781
                  errs() << " obtained by function call";
 
782
                  errs() << " before use\n";
 
783
                  return false;
 
784
              }
 
785
          }
 
786
 
 
787
      constType *I64Ty =
 
788
          Type::getInt64Ty(Base->getContext());
 
789
      const SCEV *SLen = SE->getSCEV(Length);
 
790
      const SCEV *OffsetP = SE->getMinusSCEV(SE->getSCEV(Pointer),
 
791
                                             SE->getSCEV(Base));
 
792
      SLen = SE->getNoopOrZeroExtend(SLen, I64Ty);
 
793
      OffsetP = SE->getNoopOrZeroExtend(OffsetP, I64Ty);
 
794
      const SCEV *Limit = SE->getSCEV(Bounds);
 
795
      Limit = SE->getNoopOrZeroExtend(Limit, I64Ty);
 
796
 
 
797
      DEBUG(dbgs() << "Checking access to " << *Pointer << " of length " <<
 
798
            *Length << "\n");
 
799
      if (OffsetP == Limit) {
 
800
          printLocation(I, true);
 
801
          errs() << "OffsetP == Limit: " << *OffsetP << "\n";
 
802
          errs() << " while checking access to ";
 
803
          printValue(Pointer);
 
804
          errs() << " of length ";
 
805
          printValue(Length);
 
806
          errs() << "\n";
 
807
          return false;
 
808
      }
 
809
 
 
810
      if (SLen == Limit) {
 
811
          if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(OffsetP)) {
 
812
              if (SC->isZero())
 
813
                  return true;
 
814
          }
 
815
          errs() << "SLen == Limit: " << *SLen << "\n";
 
816
          errs() << " while checking access to " << *Pointer << " of length "
 
817
                 << *Length << " at " << *I << "\n";
 
818
          return false;
 
819
      }
 
820
 
 
821
      bool valid = true;
 
822
      SLen = SE->getAddExpr(OffsetP, SLen);
 
823
      // check that offset + slen <= limit;
 
824
      // umax(offset+slen, limit) == limit is a sufficient (but not necessary
 
825
      // condition)
 
826
      const SCEV *MaxL = SE->getUMaxExpr(SLen, Limit);
 
827
      if (MaxL != Limit) {
 
828
          DEBUG(dbgs() << "MaxL != Limit: " << *MaxL << ", " << *Limit << "\n");
 
829
          valid &= insertCheck(SLen, Limit, I, false);
 
830
      }
 
831
 
 
832
      //TODO: nullpointer check
 
833
      const SCEV *Max = SE->getUMaxExpr(OffsetP, Limit);
 
834
      if (Max == Limit)
 
835
          return valid;
 
836
      DEBUG(dbgs() << "Max != Limit: " << *Max << ", " << *Limit << "\n");
 
837
 
 
838
      // check that offset < limit
 
839
      valid &= insertCheck(OffsetP, Limit, I, true);
 
840
      return valid;
 
841
      }
 
842
 
 
843
      bool validateAccess(Value *Pointer, unsigned size, Instruction *I)
 
844
      {
 
845
          return validateAccess(Pointer,
 
846
                                ConstantInt::get(Type::getInt32Ty(Pointer->getContext()),
 
847
                                                 size), I);
 
848
      }
 
849
 
 
850
  };
 
851
    char PtrVerifier::ID;
 
852
 
 
853
} /* end namespace llvm */
 
854
#if LLVM_VERSION >= 29
 
855
INITIALIZE_PASS_BEGIN(PtrVerifier, "", "", false, false)
 
856
#if LLVM_VERSION < 32
 
857
INITIALIZE_PASS_DEPENDENCY(TargetData)
 
858
#else
 
859
INITIALIZE_PASS_DEPENDENCY(DataLayout)
 
860
#endif
 
861
INITIALIZE_PASS_DEPENDENCY(DominatorTree)
 
862
INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
 
863
#if LLVM_VERSION < 34
 
864
INITIALIZE_AG_DEPENDENCY(CallGraph)
 
865
#else
 
866
INITIALIZE_PASS_DEPENDENCY(CallGraph)
 
867
#endif
 
868
INITIALIZE_PASS_DEPENDENCY(PointerTracking)
 
869
INITIALIZE_PASS_END(PtrVerifier, "clambc-rtchecks", "ClamBC RTchecks", false, false)
 
870
#endif
 
871
 
 
872
 
 
873
llvm::Pass *createClamBCRTChecks()
 
874
{
 
875
    return new PtrVerifier();
 
876
}