Hi Jordan,
On ons, 2014-10-08 at 20:05 -0700, Jordan Rose wrote:
> + // First only check for errors. That way we will find problems even
> if one of
> + // the dimensions is unknown.
> + const Expr *SE;
> + QualType QT;
> + do {
> + // Check size expression.
> + SE = VLA->getSizeExpr();
> + State = checkSizeExpr(SE, State, C);
> + if (!State)
> + return;
> Seems like a worthy goal. If we're finding problems even if one
> dimension is unknown, though, is it worth finding problems in every
> size expression, rather than exiting early when we find a problem in
> the first one?
Good point. I'm not sure I solved this the correct way. It seems like
it only is possible to create one sink node so I had to call
getPredecessor(). Is that the right way or how should I do to emit
multiple errors?
> +
> + // Check next dimension.
> + QT = VLA->getElementType();
> + VLA = Ctx.getAsVariableArrayType(QT);
> + } while(VLA);
> Nitpick: can you put a space after the "while"? (here and below)
Ok.
> + // Record the state so far, in case one of the lengths is unknown.
> + C.addTransition(State);
> Unfortunately we can't actually do this—you end up recording
> two transitions here, rather than replacing the first one. Maybe the
> size calculation should be factored out into a helper function as
> well?
> + // Multiply the current size by the element size.
> + ArraySizeVal = SvalBuilder.evalBinOpNN(State, BO_Mul,
> ArrayLength,
> + ArraySizeVal.castAs<NonLoc>(), SizeTy);
> Can you add a FIXME in here to check for overflow? That's a security
> risk, really.
I've broken out the calculation and added the FIXME, but that got me
thinking. What is a too large size? If the size is larger than a size_t
can represent we surely got a problem. We will most likely run out of
stack space way before that, however.
> As for the tests, can you add some assertions that we really do
> multiply the size out correctly? For example, using a too-large index
> should warn, casting to char * and assigning outside the buffer should
> warn, and sizeof should give the right answer.
That turned out to be easier said than done. The analyzer doesn't seem
to handle sizeof on things that can't be resolved compile time (like
VLAs)? I've also added some FIXMEs for ArrayBoundV2. Casting to char *
works as expected.
Attached is a new version of the patch.
Cheers,
Daniel
Index: lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp
===================================================================
--- lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp (revision 219711)
+++ lib/StaticAnalyzer/Checkers/VLASizeChecker.cpp (working copy)
@@ -36,6 +36,16 @@ class VLASizeChecker : public Checker< c
const Expr *SizeE,
ProgramStateRef State,
CheckerContext &C) const;
+ SVal calculateSize(const VariableArrayType *VLA,
+ QualType QT,
+ ProgramStateRef State,
+ CheckerContext &C) const;
+ /// \brief Check the size expression for bugs.
+ ///
+ /// \returns The new state, or nullptr if a bug is found.
+ ProgramStateRef checkSizeExpr(const Expr *SizeE,
+ ProgramStateRef state,
+ CheckerContext &C) const;
public:
void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
};
@@ -48,7 +58,7 @@ void VLASizeChecker::reportBug(VLASize_K
// Generate an error node.
ExplodedNode *N = C.generateSink(State);
if (!N)
- return;
+ N = C.getPredecessor();
if (!BT)
BT.reset(new BuiltinBug(
@@ -92,25 +102,113 @@ void VLASizeChecker::checkPreStmt(const
if (!VLA)
return;
- // FIXME: Handle multi-dimensional VLAs.
- const Expr *SE = VLA->getSizeExpr();
- ProgramStateRef state = C.getState();
+ ProgramStateRef State = C.getState();
+ // First only check for errors. That way we will find problems even if one of
+ // the dimensions is unknown.
+ bool ErrorFound = false;
+ QualType QT;
+ do {
+ // Check size expression.
+ const Expr *SE = VLA->getSizeExpr();
+ ProgramStateRef NewState = checkSizeExpr(SE, State, C);
+ if (NewState)
+ State = NewState;
+ else
+ ErrorFound = true;
+
+ // Check next dimension.
+ QT = VLA->getElementType();
+ VLA = Ctx.getAsVariableArrayType(QT);
+ } while (VLA);
+
+ if (ErrorFound)
+ return;
+
+ // VLASizeChecker is responsible for defining the extent of the array being
+ // declared. We do this by multiplying the array lengths by the element size,
+ // then matching that with the array region's extent symbol.
+
+ VLA = Ctx.getAsVariableArrayType(VD->getType());
+ SVal ArraySizeVal = calculateSize(VLA, QT, State, C);
+ if (ArraySizeVal.isUnknown()) {
+ C.addTransition(State);
+ return;
+ }
+
+ // Finally, assume that the array's extent matches the given size.
+ SValBuilder &SvalBuilder = C.getSValBuilder();
+ const LocationContext *LC = C.getLocationContext();
+ DefinedOrUnknownSVal Extent =
+ State->getRegion(VD, LC)->getExtent(SvalBuilder);
+ DefinedOrUnknownSVal ArraySize = ArraySizeVal.castAs<DefinedOrUnknownSVal>();
+ DefinedOrUnknownSVal SizeIsKnown =
+ SvalBuilder.evalEQ(State, Extent, ArraySize);
+ State = State->assume(SizeIsKnown, true);
+
+ // Assume should not fail at this point.
+ assert(State);
+
+ // Remember our assumptions!
+ C.addTransition(State);
+}
+
+SVal VLASizeChecker::calculateSize(const VariableArrayType *VLA,
+ QualType QT,
+ ProgramStateRef State,
+ CheckerContext &C) const {
+
+ ASTContext &Ctx = C.getASTContext();
+ SValBuilder &SvalBuilder = C.getSValBuilder();
+
+ // Get the element size.
+ QualType SizeTy = Ctx.getSizeType();
+ CharUnits EleSize = Ctx.getTypeSizeInChars(QT);
+ SVal ArraySizeVal = SvalBuilder.makeIntVal(EleSize.getQuantity(), SizeTy);
+
+ do {
+ const Expr *SE = VLA->getSizeExpr();
+ SVal SizeV = State->getSVal(SE, C.getLocationContext());
+ assert(!SizeV.isUndef() && "The size should be defined.");
+ if (SizeV.isUnknown())
+ return UnknownVal();
+ DefinedSVal SizeD = SizeV.castAs<DefinedSVal>();
+
+ // Convert the array length to size_t.
+ NonLoc ArrayLength =
+ SvalBuilder.evalCast(SizeD, SizeTy, SE->getType()).castAs<NonLoc>();
+
+ // Multiply the current size by the element size.
+ ArraySizeVal = SvalBuilder.evalBinOpNN(State, BO_Mul, ArrayLength,
+ ArraySizeVal.castAs<NonLoc>(), SizeTy);
+ // FIXME: Add a check to see if the size overflows.
+
+ // Get next dimension.
+ QT = VLA->getElementType();
+ VLA = Ctx.getAsVariableArrayType(QT);
+ } while (VLA);
+
+ return ArraySizeVal;
+}
+
+ProgramStateRef VLASizeChecker::checkSizeExpr(const Expr *SE,
+ ProgramStateRef state,
+ CheckerContext &C) const {
SVal sizeV = state->getSVal(SE, C.getLocationContext());
if (sizeV.isUndef()) {
reportBug(VLA_Garbage, SE, state, C);
- return;
+ return nullptr;
}
// See if the size value is known. It can't be undefined because we would have
// warned about that already.
if (sizeV.isUnknown())
- return;
+ return state;
// Check if the size is tainted.
if (state->isTainted(sizeV)) {
reportBug(VLA_Tainted, SE, nullptr, C);
- return;
+ return nullptr;
}
// Check if the size is zero.
@@ -121,16 +219,12 @@ void VLASizeChecker::checkPreStmt(const
if (stateZero && !stateNotZero) {
reportBug(VLA_Zero, SE, stateZero, C);
- return;
+ return nullptr;
}
// From this point on, assume that the size is not zero.
state = stateNotZero;
- // VLASizeChecker is responsible for defining the extent of the array being
- // declared. We do this by multiplying the array length by the element size,
- // then matching that with the array region's extent symbol.
-
// Check if the size is negative.
SValBuilder &svalBuilder = C.getSValBuilder();
@@ -146,38 +240,11 @@ void VLASizeChecker::checkPreStmt(const
std::tie(StateNeg, StatePos) = CM.assumeDual(state, *LessThanZeroDVal);
if (StateNeg && !StatePos) {
reportBug(VLA_Negative, SE, state, C);
- return;
+ return nullptr;
}
state = StatePos;
}
-
- // Convert the array length to size_t.
- QualType SizeTy = Ctx.getSizeType();
- NonLoc ArrayLength =
- svalBuilder.evalCast(sizeD, SizeTy, SE->getType()).castAs<NonLoc>();
-
- // Get the element size.
- CharUnits EleSize = Ctx.getTypeSizeInChars(VLA->getElementType());
- SVal EleSizeVal = svalBuilder.makeIntVal(EleSize.getQuantity(), SizeTy);
-
- // Multiply the array length by the element size.
- SVal ArraySizeVal = svalBuilder.evalBinOpNN(
- state, BO_Mul, ArrayLength, EleSizeVal.castAs<NonLoc>(), SizeTy);
-
- // Finally, assume that the array's extent matches the given size.
- const LocationContext *LC = C.getLocationContext();
- DefinedOrUnknownSVal Extent =
- state->getRegion(VD, LC)->getExtent(svalBuilder);
- DefinedOrUnknownSVal ArraySize = ArraySizeVal.castAs<DefinedOrUnknownSVal>();
- DefinedOrUnknownSVal sizeIsKnown =
- svalBuilder.evalEQ(state, Extent, ArraySize);
- state = state->assume(sizeIsKnown, true);
-
- // Assume should not fail at this point.
- assert(state);
-
- // Remember our assumptions!
- C.addTransition(state);
+ return state;
}
void ento::registerVLASizeChecker(CheckerManager &mgr) {
Index: test/Analysis/vla.c
===================================================================
--- test/Analysis/vla.c (revision 219711)
+++ test/Analysis/vla.c (working copy)
@@ -1,4 +1,4 @@
-// RUN: %clang_cc1 -analyze -analyzer-checker=core -verify %s
+// RUN: %clang_cc1 -analyze -analyzer-checker=core,alpha.security.ArrayBoundV2 -verify %s
// Zero-sized VLAs.
void check_zero_sized_VLA(int x) {
@@ -84,3 +84,165 @@ void check_negative_sized_VLA_11(int x)
if (x > 0)
check_negative_sized_VLA_11_sub(x);
}
+
+// Multi-dimensional VLAs.
+
+void check_multi_dimension_VLA_1(void)
+{
+ int i = 2;
+ int j = 2;
+ char vla[i][j]; // no-warning
+}
+
+void check_multi_dimension_VLA_2(void)
+{
+ int i = 2;
+ int j = -2;
+ char vla[i][j]; // expected-warning{{Declared variable-length array (VLA) has negative size}}
+}
+
+void check_multi_dimension_VLA_3(void)
+{
+ int i = -2;
+ int j = 2;
+ char vla[i][j]; // expected-warning{{Declared variable-length array (VLA) has negative size}}
+}
+
+void check_multi_dimension_VLA_4(void)
+{
+ int i = 2;
+ int j = -2;
+ char vla[4][i][j]; // expected-warning{{Declared variable-length array (VLA) has negative size}}
+}
+
+void check_multi_dimension_VLA_5(void)
+{
+ int i = -2;
+ int j = 2;
+ char vla[4][i][j]; // expected-warning{{Declared variable-length array (VLA) has negative size}}
+}
+
+void check_multi_dimension_VLA_6(void)
+{
+ int i = 2;
+ int j = -2;
+ char vla[i][4][j];// expected-warning{{Declared variable-length array (VLA) has negative size}}
+}
+
+void check_multi_dimension_VLA_7(void)
+{
+ int i = -2;
+ int j = 2;
+ char vla[i][4][j]; // expected-warning{{Declared variable-length array (VLA) has negative size}}
+}
+
+void check_multi_dimension_VLA_8(void)
+{
+ int i = 2;
+ int j = -2;
+ char vla[i][j][4]; // expected-warning{{Declared variable-length array (VLA) has negative size}}
+}
+
+void check_multi_dimension_VLA_9(void)
+{
+ int i = -2;
+ int j = 2;
+ char vla[i][j][4]; // expected-warning{{Declared variable-length array (VLA) has negative size}}
+}
+
+// Test with one of the dimensions undefined
+extern int k;
+
+void check_multi_dimension_VLA_10(void)
+{
+ int i = 2;
+ char vla[i][k]; // no-warning
+}
+
+void check_multi_dimension_VLA_11(void)
+{
+ int i = -2;
+ char vla[i][k]; // expected-warning{{Declared variable-length array (VLA) has negative size}}
+}
+
+void check_multi_dimension_VLA_12(void)
+{
+ int i = -2;
+ char vla[k][i]; // expected-warning{{Declared variable-length array (VLA) has negative size}}
+}
+
+// Test multiple errors
+
+void check_multi_dimension_VLA_13(void)
+{
+ int i = -2;
+ int j = 0;
+ char vla[i][2][j]; // expected-warning{{Declared variable-length array (VLA) has negative size}} expected-warning{{Declared variable-length array (VLA) has zero size}}
+}
+
+void check_multi_dimension_VLA_14(void)
+{
+ int i = -2;
+ int j = 0;
+ char vla[i][k][j]; // expected-warning{{Declared variable-length array (VLA) has negative size}} expected-warning{{Declared variable-length array (VLA) has zero size}}
+}
+
+// Test calculated size
+
+void check_sizeof_VLA_1(void)
+{
+ int i = 10;
+ char vla[i];
+ char *p = &vla[0];
+ p[9] = 'A'; // no-warning
+ p[10] = 'A'; // expected-warning{{Out of bound memory access (access exceeds upper limit of memory block)}}
+}
+
+void check_sizeof_VLA_2(void) {
+ int i = 10;
+ char vla[i];
+ vla[10] = 'A'; // expected-warning{{Out of bound memory access (access exceeds upper limit of memory block)}}
+}
+
+void check_sizeof_VLA_3(void)
+{
+ int i = 10;
+ int j = 20;
+ char vla[i][j];
+ char *p = &vla[0][0];
+ p[199] = 'A'; // no-warning
+ p[200] = 'A'; // expected-warning{{Out of bound memory access (access exceeds upper limit of memory block)}}
+}
+
+void check_sizeof_VLA_4(void) {
+ int i = 10;
+ int j = 20;
+ char vla[i][j];
+ vla[10][20] = 'A'; // FIXME: we should warn here
+}
+
+void check_sizeof_VLA_5(void)
+{
+ struct st {
+ char buf[3];
+ };
+
+ int i = 10;
+ int j = 20;
+ struct st vla[i][j];
+ char *p = (char *) &vla[0][0];
+ p[599] = 'A'; // no-warning
+ p[600] = 'A'; // expected-warning{{Out of bound memory access (access exceeds upper limit of memory block)}}
+}
+
+void check_sizeof_VLA_6(void)
+{
+ struct st {
+ char buf[3];
+ };
+
+ int i = 10;
+ int j = 20;
+ struct st vla[i][j];
+ vla[10][20].buf[0] = 'A'; // FIXME: we should warn here
+}
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
