[analyzer] False negative in ArrayBoundV2 and TaintPropagation

[z1nke]

Example code: https://godbolt.org/z/xhbsaYex6

// clang-19 --analyze -Xanalyzer -analyzer-checker="alpha.security,optin.taint" test.c // clang-19 and above
// clang-18 --analyze -Xanalyzer -analyzer-checker="alpha.security" test.c             // clang-18 and below
#include <stdio.h>
#include <stdlib.h>

void foo1() {
  char buf[20];
  if (fgets(buf, sizeof(buf), stdin) == NULL)
    return;

  int idx = atoi(buf);
  buf[idx] = '\0'; // expect-warning
}

void foo2() {
  char buf[20];
  fgets(buf, sizeof(buf), stdin);
  int idx = atoi(buf);
  buf[idx] = '\0'; // expect-warning
}

Results:

// clang-19 and above
<source>:17:3: warning: Potential out of bound access to 'buf' with tainted index [alpha.security.ArrayBoundV2]
   17 |   buf[idx] = '\0'; // expect-warning
      |   ^~~~~~~~
1 warning generated.

// clang-18 and below
<source>:10:3: warning: Potential out of bound access to 'buf' with tainted index [alpha.security.ArrayBoundV2]
   10 |   buf[idx] = '\0'; // expect-warning
      |   ^~~~~~~~
<source>:17:3: warning: Potential out of bound access to 'buf' with tainted index [alpha.security.ArrayBoundV2]
   17 |   buf[idx] = '\0'; // expect-warning
      |   ^~~~~~~~
2 warnings generated.

I found that clang-19 version had a false negative in the foo1 test case.
After some debugging, I found there might be problem with the modeling of fgets in StdLibraryFunctionsChecker.

llvm-project/clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

Lines 2267 to 2280 in ab51ecc

	// char *fgets(char *restrict s, int n, FILE *restrict stream);
	addToFunctionSummaryMap(
	"fgets",
	Signature(ArgTypes{CharPtrRestrictTy, IntTy, FilePtrRestrictTy},
	RetType{CharPtrTy}),
	Summary(NoEvalCall)
	.Case({ReturnValueCondition(BO_EQ, ArgNo(0))},
	ErrnoMustNotBeChecked, GenericSuccessMsg)
	.Case({IsNull(Ret)}, ErrnoIrrelevant, GenericFailureMsg)
	.ArgConstraint(NotNull(ArgNo(0)))
	.ArgConstraint(ArgumentCondition(1, WithinRange, Range(0, IntMax)))
	.ArgConstraint(
	BufferSize(/*Buffer=*/ArgNo(0), /*BufSize=*/ArgNo(1)))
	.ArgConstraint(NotNull(ArgNo(2))));

I am not very familiar with function summary modeling. Should we add the following case for the fgets function here?

.Case({NotNull(Ret)}, ErrnoMustNotBeChecked, GenericSuccessMsg)

[llvmbot]

@llvm/issue-subscribers-clang-static-analyzer

Author: None (z1nke)

Example code: https://godbolt.org/z/xhbsaYex6 ```cpp // clang-19 --analyze -Xanalyzer -analyzer-checker="alpha.security,optin.taint" test.c // clang-19 and above // clang-18 --analyze -Xanalyzer -analyzer-checker="alpha.security" test.c // clang-18 and below #include <stdio.h> #include <stdlib.h>

void foo1() {
char buf[20];
if (fgets(buf, sizeof(buf), stdin) == NULL)
return;

int idx = atoi(buf);
buf[idx] = '\0'; // expect-warning
}

void foo2() {
char buf[20];
fgets(buf, sizeof(buf), stdin);
int idx = atoi(buf);
buf[idx] = '\0'; // expect-warning
}

Results:

// clang-19 and above
<source>:17:3: warning: Potential out of bound access to 'buf' with tainted index [alpha.security.ArrayBoundV2]
17 | buf[idx] = '\0'; // expect-warning
| ^~~~~~~~
1 warning generated.

// clang-18 and below
<source>:10:3: warning: Potential out of bound access to 'buf' with tainted index [alpha.security.ArrayBoundV2]
10 | buf[idx] = '\0'; // expect-warning
| ^~~~~~~~
<source>:17:3: warning: Potential out of bound access to 'buf' with tainted index [alpha.security.ArrayBoundV2]
17 | buf[idx] = '\0'; // expect-warning
| ^~~~~~~~
2 warnings generated.

I found that clang-19 version had a false negative in the `foo1` test case.  
After some debugging, I found there might be problem with the modeling of `fgets` in `StdLibraryFunctionsChecker`. 
https://github.com/llvm/llvm-project/blob/ab51eccf88f5321e7c60591c5546b254b6afab99/clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp#L2267-L2280

I am not very familiar with function summary modeling. Should we add the following case for the `fgets` function here?
```cpp
.Case({NotNull(Ret)}, ErrnoMustNotBeChecked, GenericSuccessMsg)

[steakhal]

Thanks for the report. Your investigation helped a lot.
@balazske I think this one is for you. This ties to the StdLibraryFnChecker.
Apparently, in the following example, the ReturnValueCondition(BO_EQ, ArgNo(0)) of the "fgets" summary does not apply, which prevents a transition on the "success" case when the summary gets evaluated.

This means that after the summary applies, we only have a single branch, representing the failure case which soon sinks within when reaches the early-return in the example.

struct _IO_FILE;
typedef struct _IO_FILE FILE;
extern FILE *stdin;
extern char *fgets(char *__restrict __s, int __n, FILE *__restrict __stream);
extern int atoi(const char *__nptr);
#define NULL ((void*)0)

void foo1() {
  char buf[20];
  if (fgets(buf, sizeof(buf), stdin) == NULL) return;
  int idx = atoi(buf);
  buf[idx] = '\0';
}

We should figure out why does the ComparisonConstraint created by the ReturnValueCondition return NULL state; but when I dumped, even the value we assume true is already 0 S32b, thus even the sval builder constant folded the query to false without even reaching the ProgramState::assume.

Could you please continue the investigation @balazske?

[Flandini]

@steakhal @balazske I looked into this. The memory space of the base of the memory regions of the return of fgets and its first argument are different so this:

llvm-project/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

Lines 953 to 967 in 104ad92

	// If the two regions are from different known memory spaces they cannot be
	// equal. Also, assume that no symbolic region (whose memory space is
	// unknown) is on the stack.
	if (LeftMS != RightMS &&
	((LeftMS != UnknownMS && RightMS != UnknownMS) ||
	(isa<StackSpaceRegion>(LeftMS) || isa<StackSpaceRegion>(RightMS)))) {
	switch (op) {
	default:
	return UnknownVal();
	case BO_EQ:
	return makeTruthVal(false, resultTy);
	case BO_NE:
	return makeTruthVal(true, resultTy);
	}
	}

returns 0 for evalBinOpLL and evalBinOp.

I get this in gdb for the different memory spaces, left is for the return value, right is for the first argument:

(gdb) p *LeftMS
$83 = {<clang::ento::MemRegion> = {<llvm::FoldingSetBase::Node> = {NextInFoldingSetBucket = 0x0}, _vptr$MemRegion = 0x5555640d3e20 <vtable for clang::ento::UnknownSpaceRegion+16>, 
    kind = clang::ento::MemRegion::UnknownSpaceRegionKind, cachedOffset = std::optional [no contained value]}, Mgr = @0x5555643716e0}
(gdb) p *RightMS
$84 = {<clang::ento::MemRegion> = {<llvm::FoldingSetBase::Node> = {NextInFoldingSetBucket = 0x0}, _vptr$MemRegion = 0x5555640d3ef8 <vtable for clang::ento::StackLocalsSpaceRegion+16>, 
    kind = clang::ento::MemRegion::StackLocalsSpaceRegionKind, cachedOffset = std::optional [no contained value]}, Mgr = @0x5555643716e0}

and

(gdb) p lhs.dump()
&SymRegion{conj_$5{char *, LC1, S907, #1}}$85 = void
(gdb) p rhs.dump()
&Element{buf,0 S64b,char}$86 = void

means ComparisonConstraint::apply returns null for the constraint here:

llvm-project/clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

Lines 1148 to 1151 in 2302142

	if (auto CompV = SVB.evalBinOp(State, Op, V, OtherV, CondT)
	.getAs<DefinedOrUnknownSVal>())
	State = State->assume(*CompV, true);
	return State;

and then no transition is made since this part of StdLibraryFunctionsChecker::checkPostCall skips adding a transition for this state/constraint taking lines 1378 and 1385:

llvm-project/clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp

Lines 1373 to 1385 in 2302142

	for (const SummaryCase &Case : Summary.getCases()) {
	ProgramStateRef NewState = State;
	for (const ValueConstraintPtr &Constraint : Case.getConstraints()) {
	NewState = Constraint->apply(NewState, Call, Summary, C);
	if (!NewState)
	break;
	}
	if (NewState)
	NewState = Case.getErrnoConstraint().apply(NewState, Call, Summary, C);
	if (!NewState)
	continue;

I would be happy to fix this, but I'm not sure what the best fix would be. My first thought is to try to make the return SVal the same as the first argument in the environment for this case, thoughts?

[steakhal]

@steakhal @balazske I looked into this. The memory space of the base of the memory regions of the return of fgets and its first argument are different so this:

llvm-project/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

Lines 953 to 967 in 104ad92

To me, the condition looks fishy.
There are two different reasons why we can have Unknown memory spaces:

1. Because the MemRegion represents a pointer or reference parameter of a top-level function. This case it's fair to assume that the pointer can't alias with any pointers pointing to any of the local variables of our current function - but I can't find where would it check if the stack is for the current function.

2. The result of opaque function calls, result in a SymbolicRegion with a conjured symbol. In this case it would be unfair to assume any aliasing or the lack of. This is the bug in our case, because we can't introduce the aliasing relationship due to this specific check - despite that is the whole point of this evalBinOpLL call in this case.

I think evalBinOpLL should not return false for our case.

BTW you can check if a memregion is a symbregion of a conjured symbol by using this:

auto IsConjuredSymbolic = [](const MemRegion *R) {
  const auto *SymReg = llvm::dyn_cast<SymbolicRegion>(R);
  return SymReg && isa<SymbolConjured>(SymReg->getSymbol());
};

[balazske]

I looked at this case, for me looks like the "point 2" above is the bug here. The comment (in the shown SimpleSValBuilder.cpp code) says "Also, assume that no symbolic region (whose memory space is unknown) is on the stack.". Here exactly this is the case, the original return value is symbolic and should be equal to a stack variable. Adding a .Case({NotNull(Ret)} is probably not a good fix because this makes a new execution branch even if the other one was applied too.