From e8a964bdb46349e4fa3433c8e5104d2a0f7f5c65 Mon Sep 17 00:00:00 2001 From: Zhongxing Xu Date: Sat, 22 Nov 2008 13:21:46 +0000 Subject: [PATCH] Initial support for checking out of bound memory access. Only support ConcreteInt index for now. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@59869 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../PathSensitive/BasicValueFactory.h | 1 + .../PathSensitive/ConstraintManager.h | 4 +++ .../Analysis/PathSensitive/GRExprEngine.h | 6 +--- .../clang/Analysis/PathSensitive/GRState.h | 6 ++++ include/clang/Analysis/PathSensitive/SVals.h | 3 ++ lib/Analysis/BasicConstraintManager.cpp | 27 ++++++++++++++ lib/Analysis/BasicValueFactory.cpp | 6 ++++ lib/Analysis/GRExprEngine.cpp | 9 +++-- lib/Analysis/RegionStore.cpp | 36 +++++++++++++++++++ lib/Analysis/SVals.cpp | 5 +++ 10 files changed, 96 insertions(+), 7 deletions(-) diff --git a/include/clang/Analysis/PathSensitive/BasicValueFactory.h b/include/clang/Analysis/PathSensitive/BasicValueFactory.h index 639ff5d92c..70fbe1de83 100644 --- a/include/clang/Analysis/PathSensitive/BasicValueFactory.h +++ b/include/clang/Analysis/PathSensitive/BasicValueFactory.h @@ -72,6 +72,7 @@ public: ASTContext& getContext() const { return Ctx; } const llvm::APSInt& getValue(const llvm::APSInt& X); + const llvm::APSInt& getValue(const llvm::APInt& X, bool isUnsigned); const llvm::APSInt& getValue(uint64_t X, unsigned BitWidth, bool isUnsigned); const llvm::APSInt& getValue(uint64_t X, QualType T); diff --git a/include/clang/Analysis/PathSensitive/ConstraintManager.h b/include/clang/Analysis/PathSensitive/ConstraintManager.h index 71ae247f57..3f2e60d3ef 100644 --- a/include/clang/Analysis/PathSensitive/ConstraintManager.h +++ b/include/clang/Analysis/PathSensitive/ConstraintManager.h @@ -34,6 +34,10 @@ public: virtual const GRState* Assume(const GRState* St, SVal Cond, bool Assumption, bool& isFeasible) = 0; + virtual const GRState* AssumeInBound(const GRState* St, SVal Idx, + SVal UpperBound, bool Assumption, + bool& isFeasible) = 0; + virtual const GRState* AddNE(const GRState* St, SymbolID sym, const llvm::APSInt& V) = 0; virtual const llvm::APSInt* getSymVal(const GRState* St, SymbolID sym) = 0; diff --git a/include/clang/Analysis/PathSensitive/GRExprEngine.h b/include/clang/Analysis/PathSensitive/GRExprEngine.h index 5ba61d8645..1b7d9bf6a3 100644 --- a/include/clang/Analysis/PathSensitive/GRExprEngine.h +++ b/include/clang/Analysis/PathSensitive/GRExprEngine.h @@ -468,11 +468,7 @@ protected: const GRState* AssumeInBound(const GRState* St, SVal Idx, SVal UpperBound, bool Assumption, bool& isFeasible) { - // FIXME: In this function, we will check if Idx can be in/out - // [0, UpperBound) according to the assumption. We can extend the - // interface to include a LowerBound parameter. - isFeasible = true; - return St; + return StateMgr.AssumeInBound(St, Idx, UpperBound, Assumption, isFeasible); } NodeTy* MakeNode(NodeSet& Dst, Stmt* S, NodeTy* Pred, const GRState* St, diff --git a/include/clang/Analysis/PathSensitive/GRState.h b/include/clang/Analysis/PathSensitive/GRState.h index 0a40998e39..68f7921db3 100644 --- a/include/clang/Analysis/PathSensitive/GRState.h +++ b/include/clang/Analysis/PathSensitive/GRState.h @@ -523,6 +523,12 @@ public: return ConstraintMgr->Assume(St, Cond, Assumption, isFeasible); } + const GRState* AssumeInBound(const GRState* St, SVal Idx, SVal UpperBound, + bool Assumption, bool& isFeasible) { + return ConstraintMgr->AssumeInBound(St, Idx, UpperBound, Assumption, + isFeasible); + } + const GRState* AddNE(const GRState* St, SymbolID sym, const llvm::APSInt& V) { return ConstraintMgr->AddNE(St, sym, V); } diff --git a/include/clang/Analysis/PathSensitive/SVals.h b/include/clang/Analysis/PathSensitive/SVals.h index 417a89adc8..16322f111f 100644 --- a/include/clang/Analysis/PathSensitive/SVals.h +++ b/include/clang/Analysis/PathSensitive/SVals.h @@ -173,6 +173,9 @@ public: static NonLoc MakeVal(BasicValueFactory& BasicVals, uint64_t X, QualType T); static NonLoc MakeVal(BasicValueFactory& BasicVals, IntegerLiteral* I); + + static NonLoc MakeVal(BasicValueFactory& BasicVals, const llvm::APInt& I, + bool isUnsigned); static NonLoc MakeIntTruthVal(BasicValueFactory& BasicVals, bool b); diff --git a/lib/Analysis/BasicConstraintManager.cpp b/lib/Analysis/BasicConstraintManager.cpp index b09d9de446..a359b23c54 100644 --- a/lib/Analysis/BasicConstraintManager.cpp +++ b/lib/Analysis/BasicConstraintManager.cpp @@ -69,6 +69,9 @@ public: const GRState* AssumeSymLE(const GRState* St, SymbolID sym, const llvm::APSInt& V, bool& isFeasible); + const GRState* AssumeInBound(const GRState* St, SVal Idx, SVal UpperBound, + bool Assumption, bool& isFeasible); + const GRState* AddEQ(const GRState* St, SymbolID sym, const llvm::APSInt& V); const GRState* AddNE(const GRState* St, SymbolID sym, const llvm::APSInt& V); @@ -83,6 +86,9 @@ public: void print(const GRState* St, std::ostream& Out, const char* nl, const char *sep); + +private: + BasicValueFactory& getBasicVals() { return StateMgr.getBasicVals(); } }; } // end anonymous namespace @@ -352,6 +358,27 @@ BasicConstraintManager::AssumeSymLE(const GRState* St, SymbolID sym, return St; } +const GRState* +BasicConstraintManager::AssumeInBound(const GRState* St, SVal Idx, + SVal UpperBound, bool Assumption, + bool& isFeasible) { + // Only support ConcreteInt for now. + if (!(isa(Idx) && isa(UpperBound))){ + isFeasible = true; + return St; + } + + const llvm::APSInt& Zero = getBasicVals().getZeroWithPtrWidth(false); + const llvm::APSInt& IdxV = cast(Idx).getValue(); + const llvm::APSInt& UBV = cast(UpperBound).getValue(); + + bool InBound = (Zero <= IdxV) && (IdxV < UBV); + + isFeasible = Assumption ? InBound : !InBound; + + return St; +} + static int ConstEqTyIndex = 0; static int ConstNotEqTyIndex = 0; diff --git a/lib/Analysis/BasicValueFactory.cpp b/lib/Analysis/BasicValueFactory.cpp index 5b7041bc43..7ce305e4cf 100644 --- a/lib/Analysis/BasicValueFactory.cpp +++ b/lib/Analysis/BasicValueFactory.cpp @@ -76,6 +76,12 @@ const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) { return *P; } +const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X, + bool isUnsigned) { + llvm::APSInt V(X, isUnsigned); + return getValue(V); +} + const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth, bool isUnsigned) { llvm::APSInt V(BitWidth, isUnsigned); diff --git a/lib/Analysis/GRExprEngine.cpp b/lib/Analysis/GRExprEngine.cpp index db325fb9f9..6de910fc17 100644 --- a/lib/Analysis/GRExprEngine.cpp +++ b/lib/Analysis/GRExprEngine.cpp @@ -1084,9 +1084,14 @@ const GRState* GRExprEngine::EvalLocation(Stmt* Ex, NodeTy* Pred, bool isFeasibleOutBound = false; const GRState* StOutBound = AssumeInBound(StNotNull, Idx, NumElements, false, isFeasibleOutBound); - StInBound = StOutBound = 0; // FIXME: squeltch warning. - // Report warnings ... + if (isFeasibleOutBound) { + // Report warning. + + StOutBound = 0; + } + + return isFeasibleInBound ? StInBound : NULL; } } diff --git a/lib/Analysis/RegionStore.cpp b/lib/Analysis/RegionStore.cpp index 6f632f4bc5..cc7715a98a 100644 --- a/lib/Analysis/RegionStore.cpp +++ b/lib/Analysis/RegionStore.cpp @@ -80,6 +80,8 @@ public: SVal getLValueElement(const GRState* St, SVal Base, SVal Offset); + SVal getSizeInElements(const GRState* St, const MemRegion* R); + SVal ArrayToPointer(SVal Array); std::pair @@ -257,6 +259,40 @@ SVal RegionStoreManager::getLValueElement(const GRState* St, return UnknownVal(); } +SVal RegionStoreManager::getSizeInElements(const GRState* St, + const MemRegion* R) { + if (const VarRegion* VR = dyn_cast(R)) { + // Get the type of the variable. + QualType T = VR->getType(getContext()); + + // It must be of array type. + const ConstantArrayType* CAT = cast(T.getTypePtr()); + + // return the size as signed integer. + return NonLoc::MakeVal(getBasicVals(), CAT->getSize(), false); + } + + if (const StringRegion* SR = dyn_cast(R)) { + // FIXME: Unsupported yet. + SR = 0; + return UnknownVal(); + } + + if (const AnonTypedRegion* ATR = dyn_cast(R)) { + // FIXME: Unsupported yet. + ATR = 0; + return UnknownVal(); + } + + if (const FieldRegion* FR = dyn_cast(R)) { + // FIXME: Unsupported yet. + FR = 0; + return UnknownVal(); + } + printf("kidn = %d\n", R->getKind()); + assert(0 && "Other regions are not supported yet."); +} + // Cast 'pointer to array' to 'pointer to the first element of array'. SVal RegionStoreManager::ArrayToPointer(SVal Array) { diff --git a/lib/Analysis/SVals.cpp b/lib/Analysis/SVals.cpp index 644f60d25a..764a05fe8f 100644 --- a/lib/Analysis/SVals.cpp +++ b/lib/Analysis/SVals.cpp @@ -253,6 +253,11 @@ NonLoc NonLoc::MakeVal(BasicValueFactory& BasicVals, IntegerLiteral* I) { I->getType()->isUnsignedIntegerType()))); } +NonLoc NonLoc::MakeVal(BasicValueFactory& BasicVals, const llvm::APInt& I, + bool isUnsigned) { + return nonloc::ConcreteInt(BasicVals.getValue(I, isUnsigned)); +} + NonLoc NonLoc::MakeIntTruthVal(BasicValueFactory& BasicVals, bool b) { return nonloc::ConcreteInt(BasicVals.getTruthValue(b)); } -- 2.40.0