From 6ae8a3600656c478d27f25639bed765f4fe71732 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Fri, 13 Mar 2009 16:32:54 +0000 Subject: [PATCH] Add a hack in the analyzer to recover some path-sensitivity at branch conditions. Currently the analyzer does not reason well about promotions/truncations of symbolic values, so at branch conditions when we see: if (condition) and condition is something like a 'short' or 'char', essentially ignore the promotion to 'int' so that we track constraints on the original symbolic value. We only ignore the casts if the underlying type has the same or fewer bits as the converted type. This fixes: git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@66899 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/GRExprEngine.cpp | 59 +++++++++++++++++++++++++++- test/Analysis/misc-ps-eager-assume.m | 49 +++++++++++++++++++++++ 2 files changed, 107 insertions(+), 1 deletion(-) diff --git a/lib/Analysis/GRExprEngine.cpp b/lib/Analysis/GRExprEngine.cpp index 6ff01fc5c9..6d360ed503 100644 --- a/lib/Analysis/GRExprEngine.cpp +++ b/lib/Analysis/GRExprEngine.cpp @@ -540,6 +540,45 @@ const GRState* GRExprEngine::MarkBranch(const GRState* state, } } +/// RecoverCastedSymbol - A helper function for ProcessBranch that is used +/// to try to recover some path-sensitivity for casts of symbolic +/// integers that promote their values (which are currently not tracked well). +/// This function returns the SVal bound to Condition->IgnoreCasts if all the +// cast(s) did was sign-extend the original value. +static SVal RecoverCastedSymbol(GRStateManager& StateMgr, const GRState* state, + Stmt* Condition, ASTContext& Ctx) { + + Expr *Ex = dyn_cast(Condition); + if (!Ex) + return UnknownVal(); + + uint64_t bits = 0; + bool bitsInit = false; + + while (CastExpr *CE = dyn_cast(Ex)) { + QualType T = CE->getType(); + + if (!T->isIntegerType()) + return UnknownVal(); + + uint64_t newBits = Ctx.getTypeSize(T); + if (!bitsInit || newBits < bits) { + bitsInit = true; + bits = newBits; + } + + Ex = CE->getSubExpr(); + } + + // We reached a non-cast. Is it a symbolic value? + QualType T = Ex->getType(); + + if (!bitsInit || !T->isIntegerType() || Ctx.getTypeSize(T) > bits) + return UnknownVal(); + + return StateMgr.GetSVal(state, Ex); +} + void GRExprEngine::ProcessBranch(Stmt* Condition, Stmt* Term, BranchNodeBuilder& builder) { @@ -563,10 +602,28 @@ void GRExprEngine::ProcessBranch(Stmt* Condition, Stmt* Term, default: break; - case SVal::UnknownKind: + case SVal::UnknownKind: { + if (Expr *Ex = dyn_cast(Condition)) { + if (Ex->getType()->isIntegerType()) { + // Try to recover some path-sensitivity. Right now casts of symbolic + // integers that promote their values are currently not tracked well. + // If 'Condition' is such an expression, try and recover the + // underlying value and use that instead. + SVal recovered = RecoverCastedSymbol(getStateManager(), + builder.getState(), Condition, + getContext()); + + if (!recovered.isUnknown()) { + V = recovered; + break; + } + } + } + builder.generateNode(MarkBranch(PrevState, Term, true), true); builder.generateNode(MarkBranch(PrevState, Term, false), false); return; + } case SVal::UndefinedKind: { NodeTy* N = builder.generateNode(PrevState, true); diff --git a/test/Analysis/misc-ps-eager-assume.m b/test/Analysis/misc-ps-eager-assume.m index 48d5b8f9d2..c36ae8f4d6 100644 --- a/test/Analysis/misc-ps-eager-assume.m +++ b/test/Analysis/misc-ps-eager-assume.m @@ -1,5 +1,34 @@ // RUN: clang -analyze -checker-cfref --analyzer-store=region -analyzer-constraints=range --verify -fblocks %s -analyzer-eagerly-assume +// Delta-reduced header stuff (needed for test cases). +typedef signed char BOOL; +typedef unsigned int NSUInteger; +typedef struct _NSZone NSZone; +@class NSInvocation, NSMethodSignature, NSCoder, NSString, NSEnumerator; +@protocol NSObject - (BOOL)isEqual:(id)object; +- (oneway void)release; +@end @protocol NSCopying - (id)copyWithZone:(NSZone *)zone; +@end @protocol NSMutableCopying - (id)mutableCopyWithZone:(NSZone *)zone; +@end @protocol NSCoding - (void)encodeWithCoder:(NSCoder *)aCoder; +@end @interface NSObject {} ++ (id)alloc; +@end typedef struct {} +NSFastEnumerationState; +@protocol NSFastEnumeration - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)stackbuf count:(NSUInteger)len; +@end @interface NSArray : NSObject - (NSUInteger)count; +@end @interface NSMutableArray : NSArray - (void)addObject:(id)anObject; +- (BOOL)isEqualToString:(NSString *)aString; +@end @interface NSAutoreleasePool : NSObject {} +- (void)drain; +- (id)init; +@end + +// This test case tests that (x != 0) is eagerly evaluated before stored to +// 'y'. This test case complements recoverCastedSymbol (see below) because +// the symbolic expression is stored to 'y' (which is a short instead of an +// int). recoverCastedSymbol() only recovers path-sensitivity when the +// symbolic expression is literally the branch condition. +// void handle_assign_of_condition(int x) { // The cast to 'short' causes us to lose symbolic constraint. short y = (x != 0); @@ -12,3 +41,23 @@ void handle_assign_of_condition(int x) { } } +// From +// +// In this test case, 'needsAnArray' is a signed char. The analyzer tracks +// a symbolic value for this variable, but in the branch condition it is +// promoted to 'int'. Currently the analyzer doesn't reason well about +// promotions of symbolic values, so this test case tests the logic in +// 'recoverCastedSymbol()' (GRExprEngine.cpp) to test that we recover +// path-sensitivity and use the symbol for 'needsAnArray' in the branch +// condition. +// +void handle_symbolic_cast_in_condition(void) { + NSAutoreleasePool* pool = [[NSAutoreleasePool alloc] init]; + + BOOL needsAnArray = [@"aString" isEqualToString:@"anotherString"]; + NSMutableArray* array = needsAnArray ? [[NSMutableArray alloc] init] : 0; + if(needsAnArray) + [array release]; + + [pool drain]; +} -- 2.40.0