[analyzer] NullabilityChecker: Invariant violation should only be triggered for symbols.

[NoQ]

Summary

This false negative bug was exposed by D18860. The checker tries to detect the situation when a symbol previously passed through a _Nonnull-annotated function parameter is constrained to null later on the path, and suppress its warnings on such paths by setting a state-wide flag <InvariantViolated>. The detection for symbols being constrained to null is done, in particular, in checkDeadSymbols(), because that's the last moment when we see the symbol and therefore we have perfect knowledge of its constraints at this moment. The detection works by ascending the stack frame chain and seeing if any of the _Nonnull parameters has a null value in the current program state.

It turned out that such invariant violation detection in checkDeadSymbols() races with checkPreCall(). Suppose that we're stuffing a concrete null (rather than a symbol constrained to null) into the function. Depending on the result of the race, there would be two possible scenarios:

1. checkPreCall() fires first. In this case a valid warning will be issued that null is being passed through a parameter that is annotated as _Nonnull.
2. checkDeadSymbols() fires first. In this case it'll notice that a _Nonnull parameter of the call that we almost entered is equal to null and raise the <InvariantViolated> flag, suppressing all nullability warnings.

Which means that depending on "something" we either see or don't see a warning.

What is this "something"? Why are callbacks were called in different order? Easy: it's because checkDeadSymbols() weren't firing at all when there were no dead symbols. Now that zombie symbol bugs are fixed, we realize that it's always important to call checkDeadSymbols(), because we've no idea what symbols the checker may track. So after fixing zombie symbols in D18860, the race started resolving to scenario 2, resulting in more false negatives.

The bug is fixed by restricting the check to work with symbols only, not with concrete values. This works because by the time we reach the call, symbolic values should be either not constrained to null, or already replaced with concrete 0 (Loc) values. Though generally the code is a bit weird and might require more thought.

[NoQ]

It also seems that we still have a false negative under ARC, but i didn't bother investigating it. Just in case, i added -fobjc-arc run-lines to older tests to see if there's any difference, and it turned out that there's no difference.

[Szelethus]

Thanks for summarizing the problem so well in the summary! I should start doing that too.

lib/StaticAnalyzer/Checkers/NullabilityChecker.cpp

343–346 ↗

(On Diff #172274)

To me, "should've been handled" sounds like that could be translated to an assert.

Also, this doc seems confusing to me, but I might be wrong. You referenced the term "symbol" a couple types, but I don't see SymbolVal anywhere. Could you reword it a bit?

test/Analysis/nullability-arc.mm

1–2 ↗

(On Diff #172274)

Let's organize this into multiple lines!

// RUN: %clang_analyze_cc1 -w -verify %s -fobjc-arc \
// RUN:   -analyzer-checker=core,nullability -analyzer-output=text

test/Analysis/nullability.mm

3–4 ↗

(On Diff #172274)

These too. Especially these :D

[NoQ]

Fix comments, update comments.

Before i forget - also add invariant violation markers to the exploded graph, which helped me a lot with debugging this bug.

test/Analysis/nullability.mm

3–4 ↗

(On Diff #172274)

These two are in fact a bit annoying because the space after // RUN: is part of the run-line, so you can't break a single long flag into multiple lines without getting involved in an aesthetically unpleasant indentation.

[Szelethus]

I have no other objections, looks great!

test/Analysis/nullability.mm

3–4 ↗

(On Diff #172274)

Oh, this looks amazing now. :)

[NoQ]

Reverted as rC347956 due to http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/26658 - will have a look tomorrow.

=================================================================
==3106==ERROR: AddressSanitizer: stack-use-after-return on address 0x7f00737c6641 at pc 0x000000c4a555 bp 0x7ffcab19dd30 sp 0x7ffcab19d4e0
READ of size 11 at 0x7f00737c6641 thread T0
    #0 0xc4a554 in __asan_memcpy /b/sanitizer-x86_64-linux-fast/build/llvm/projects/compiler-rt/lib/asan/asan_interceptors_memintrinsics.cc:23
    #1 0x951fcce in operator<< /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/Support/raw_ostream.h:177:7
    #2 0x951fcce in clang::ento::retaincountchecker::CFRefLeakReport::createDescription(clang::ento::CheckerContext&, bool) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountDiagnostics.cpp:654
    #3 0x9520886 in clang::ento::retaincountchecker::CFRefLeakReport::CFRefLeakReport(clang::ento::retaincountchecker::CFRefBug&, clang::LangOptions const&, llvm::DenseMap<clang::ento::ExplodedNode const*, clang::ento::RetainSummary const*, llvm::DenseMapInfo<clang::ento::ExplodedNode const*>, llvm::detail::DenseMapPair<clang::ento::ExplodedNode const*, clang::ento::RetainSummary const*> > const&, clang::ento::ExplodedNode*, clang::ento::SymExpr const*, clang::ento::CheckerContext&, bool) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountDiagnostics.cpp:669:3
    #4 0x94fef2b in make_unique<clang::ento::retaincountchecker::CFRefLeakReport, clang::ento::retaincountchecker::CFRefBug &, const clang::LangOptions &, llvm::DenseMap<const clang::ento::ExplodedNode *, const clang::ento::RetainSummary *, llvm::DenseMapInfo<const clang::ento::ExplodedNode *>, llvm::detail::DenseMapPair<const clang::ento::ExplodedNode *, const clang::ento::RetainSummary *> > &, clang::ento::ExplodedNode *&, const clang::ento::SymExpr *&, clang::ento::CheckerContext &, const bool &> /b/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/ADT/STLExtras.h:1212:33
    #5 0x94fef2b in clang::ento::retaincountchecker::RetainCountChecker::checkReturnWithRetEffect(clang::ReturnStmt const*, clang::ento::CheckerContext&, clang::ento::ExplodedNode*, clang::ento::RetEffect, clang::ento::retaincountchecker::RefVal, clang::ento::SymExpr const*, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>) const /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountChecker.cpp:1061
    #6 0x94fbdce in clang::ento::retaincountchecker::RetainCountChecker::processReturn(clang::ReturnStmt const*, clang::ento::CheckerContext&) const /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountChecker.cpp:1027:10
    #7 0x9504c0e in clang::ento::retaincountchecker::RetainCountChecker::checkEndFunction(clang::ReturnStmt const*, clang::ento::CheckerContext&) const /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountChecker.cpp:1396:24
    #8 0x9785395 in operator() /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/include/clang/StaticAnalyzer/Core/CheckerManager.h:70:12
    #9 0x9785395 in clang::ento::CheckerManager::runCheckersForEndFunction(clang::ento::NodeBuilderContext&, clang::ento::ExplodedNodeSet&, clang::ento::ExplodedNode*, clang::ento::ExprEngine&, clang::ReturnStmt const*) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Core/CheckerManager.cpp:452
    #10 0x97f74d2 in clang::ento::ExprEngine::processEndOfFunction(clang::ento::NodeBuilderContext&, clang::ento::ExplodedNode*, clang::ReturnStmt const*) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp:2263:27
    #11 0x97a6582 in clang::ento::CoreEngine::HandleBlockEdge(clang::BlockEdge const&, clang::ento::ExplodedNode*) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp:238:12
    #12 0x97a54dd in clang::ento::CoreEngine::dispatchWorkItem(clang::ento::ExplodedNode*, clang::ProgramPoint, clang::ento::WorkListUnit const&) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp:160:7
    #13 0x97a4451 in clang::ento::CoreEngine::ExecuteWorkList(clang::LocationContext const*, unsigned int, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp:149:5
    #14 0x905a4f5 in ExecuteWorkList /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h:165:19
    #15 0x905a4f5 in RunPathSensitiveChecks /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp:741
    #16 0x905a4f5 in (anonymous namespace)::AnalysisConsumer::HandleCode(clang::Decl*, unsigned int, clang::ento::ExprEngine::InliningModes, llvm::DenseSet<clang::Decl const*, llvm::DenseMapInfo<clang::Decl const*> >*) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp:716
    #17 0x9040ea8 in HandleDeclsCallGraph /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp:507:5
    #18 0x9040ea8 in runAnalysisOnTranslationUnit /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp:554
    #19 0x9040ea8 in (anonymous namespace)::AnalysisConsumer::HandleTranslationUnit(clang::ASTContext&) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp:585
    #20 0x9a6e442 in clang::ParseAST(clang::Sema&, bool, bool) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/Parse/ParseAST.cpp:170:13
    #21 0x73a53dd in clang::FrontendAction::Execute() /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/Frontend/FrontendAction.cpp:917:8
    #22 0x729398e in clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/Frontend/CompilerInstance.cpp:968:11
    #23 0x75d3537 in clang::ExecuteCompilerInvocation(clang::CompilerInstance*) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:267:25
    #24 0xc9461e in cc1_main(llvm::ArrayRef<char const*>, char const*, void*) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/tools/driver/cc1_main.cpp:219:13
    #25 0xc8c8c6 in ExecuteCC1Tool /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/tools/driver/driver.cpp:310:12
    #26 0xc8c8c6 in main /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/tools/driver/driver.cpp:382
    #27 0x7f0076c752e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
    #28 0xb804a9 in _start (/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan/bin/clang-8+0xb804a9)

Address 0x7f00737c6641 is located in stack of thread T0 at offset 65 in frame
    #0 0x951d9ff in getPrettyTypeName(clang::QualType) /b/sanitizer-x86_64-linux-fast/build/llvm/tools/clang/lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountDiagnostics.cpp:34

  This frame has 2 object(s):
    [32, 40) 'QT'
    [64, 88) 'ref.tmp' (line 39) <== Memory access at offset 65 is inside this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-use-after-return /b/sanitizer-x86_64-linux-fast/build/llvm/projects/compiler-rt/lib/asan/asan_interceptors_memintrinsics.cc:23 in __asan_memcpy
Shadow bytes around the buggy address:
  0x0fe08e6f0c70: f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5
  0x0fe08e6f0c80: f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5
  0x0fe08e6f0c90: f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5
  0x0fe08e6f0ca0: f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5
  0x0fe08e6f0cb0: f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5 f5
=>0x0fe08e6f0cc0: f5 f5 f5 f5 f5 f5 f5 f5[f5]f5 f5 f5 f5 f5 f5 f5
  0x0fe08e6f0cd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe08e6f0ce0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe08e6f0cf0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe08e6f0d00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0fe08e6f0d10: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==3106==ABORTING

[NoQ]

Wasn't me: rC347970.

cfe/trunk/lib/StaticAnalyzer/Checkers/NullabilityChecker.cpp

NullabilityChecker::NullabilityBugVisitor::VisitNode(const ExplodedNode *N,
 
   // Generate the extra diagnostic.
   PathDiagnosticLocation Pos(S, BRC.getSourceManager(),
                              N->getLocationContext());
   return std::make_shared<PathDiagnosticEventPiece>(Pos, InfoText, true,
                                                     nullptr);
 }
 
-/// Returns true when the value stored at the given location is null
-/// and the passed in type is nonnnull.
+/// Returns true when the value stored at the given location has been
+/// constrained to null after being passed through an object of nonnnull type.
 static bool checkValueAtLValForInvariantViolation(ProgramStateRef State,
                                                   SVal LV, QualType T) {
   if (getNullabilityAnnotation(T) != Nullability::Nonnull)
     return false;
 
   auto RegionVal = LV.getAs<loc::MemRegionVal>();
   if (!RegionVal)
     return false;
 
-  auto StoredVal =
-  State->getSVal(RegionVal->getRegion()).getAs<DefinedOrUnknownSVal>();
-  if (!StoredVal)
+  // If the value was constrained to null *after* it was passed through that
+  // location, it could not have been a concrete pointer *when* it was passed.
+  // In that case we would have handled the situation when the value was
+  // bound to that location, by emitting (or not emitting) a report.
+  // Therefore we are only interested in symbolic regions that can be either
+  // null or non-null depending on the value of their respective symbol.
+  auto StoredVal = State->getSVal(*RegionVal).getAs<loc::MemRegionVal>();
+  if (!StoredVal || !isa<SymbolicRegion>(StoredVal->getRegion()))
     return false;
 
   if (getNullConstraint(*StoredVal, State) == NullConstraint::IsNull)
     return true;
 
   return false;
 }
 
void NullabilityChecker::checkBind(SVal L, SVal V, const Stmt *S,
   }
 }
 
 void NullabilityChecker::printState(raw_ostream &Out, ProgramStateRef State,
                                     const char *NL, const char *Sep) const {
 
   NullabilityMapTy B = State->get<NullabilityMap>();
 
+  if (State->get<InvariantViolated>())
+    Out << Sep << NL
+        << "Nullability invariant was violated, warnings suppressed." << NL;
+
   if (B.isEmpty())
     return;
 
+  if (!State->get<InvariantViolated>())
     Out << Sep << NL;
 
   for (NullabilityMapTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
     Out << I->first << " : ";
     I->second.print(Out);
     Out << NL;
   }
 }
 

cfe/trunk/test/Analysis/nullability-arc.mm

+// RUN: %clang_analyze_cc1 -w -analyzer-checker=core,nullability\
+// RUN:                       -analyzer-output=text -verify %s
+// RUN: %clang_analyze_cc1 -w -analyzer-checker=core,nullability\
+// RUN:                       -analyzer-output=text -verify %s -fobjc-arc
+
+#if !__has_feature(objc_arc)
+// expected-no-diagnostics
+#endif
+
+
+#define nil ((id)0)
+
+@interface Param
+@end
+
+@interface Base
+- (void)foo:(Param *_Nonnull)param;
+@end
+
+@interface Derived : Base
+@end
+
+@implementation Derived
+- (void)foo:(Param *)param {
+  // FIXME: Why do we not emit the warning under ARC?
+  [super foo:param];
+#if __has_feature(objc_arc)
+  // expected-warning@-2{{nil passed to a callee that requires a non-null 1st parameter}}
+  // expected-note@-3   {{nil passed to a callee that requires a non-null 1st parameter}}
+#endif
+
+  [self foo:nil];
+#if __has_feature(objc_arc)
+  // expected-note@-2{{Calling 'foo:'}}
+  // expected-note@-3{{Passing nil object reference via 1st parameter 'param'}}
+#endif
+}
+@end
+

cfe/trunk/test/Analysis/nullability.mm

-// RUN: %clang_analyze_cc1 -fblocks -analyzer-checker=core,nullability.NullPassedToNonnull,nullability.NullReturnedFromNonnull,nullability.NullablePassedToNonnull,nullability.NullableReturnedFromNonnull,nullability.NullableDereferenced -DNOSYSTEMHEADERS=0 -verify %s
-// RUN: %clang_analyze_cc1 -fblocks -analyzer-checker=core,nullability.NullPassedToNonnull,nullability.NullReturnedFromNonnull,nullability.NullablePassedToNonnull,nullability.NullableReturnedFromNonnull,nullability.NullableDereferenced -analyzer-config nullability:NoDiagnoseCallsToSystemHeaders=true -DNOSYSTEMHEADERS=1 -verify %s
+// RUN: %clang_analyze_cc1 -fblocks -verify %s -analyzer-checker=core \
+// RUN:   -analyzer-checker=nullability.NullPassedToNonnull \
+// RUN:   -analyzer-checker=nullability.NullReturnedFromNonnull \
+// RUN:   -analyzer-checker=nullability.NullablePassedToNonnull \
+// RUN:   -analyzer-checker=nullability.NullableReturnedFromNonnull \
+// RUN:   -analyzer-checker=nullability.NullableDereferenced \
+// RUN:   -DNOSYSTEMHEADERS=0
+
+// RUN: %clang_analyze_cc1 -fblocks -verify %s -analyzer-checker=core \
+// RUN:   -analyzer-checker=nullability.NullPassedToNonnull \
+// RUN:   -analyzer-checker=nullability.NullReturnedFromNonnull \
+// RUN:   -analyzer-checker=nullability.NullablePassedToNonnull \
+// RUN:   -analyzer-checker=nullability.NullableReturnedFromNonnull \
+// RUN:   -analyzer-checker=nullability.NullableDereferenced \
+// RUN:   -DNOSYSTEMHEADERS=1 \
+// RUN:   -analyzer-config nullability:NoDiagnoseCallsToSystemHeaders=true
+
+// RUN: %clang_analyze_cc1 -fblocks -verify %s -analyzer-checker=core\
+// RUN:   -analyzer-checker=nullability.NullPassedToNonnull\
+// RUN:   -analyzer-checker=nullability.NullReturnedFromNonnull\
+// RUN:   -analyzer-checker=nullability.NullablePassedToNonnull\
+// RUN:   -analyzer-checker=nullability.NullableReturnedFromNonnull\
+// RUN:   -analyzer-checker=nullability.NullableDereferenced\
+// RUN:   -DNOSYSTEMHEADERS=0 -fobjc-arc
+
+// RUN: %clang_analyze_cc1 -fblocks -verify %s -analyzer-checker=core\
+// RUN:   -analyzer-checker=nullability.NullPassedToNonnull\
+// RUN:   -analyzer-checker=nullability.NullReturnedFromNonnull\
+// RUN:   -analyzer-checker=nullability.NullablePassedToNonnull\
+// RUN:   -analyzer-checker=nullability.NullableReturnedFromNonnull\
+// RUN:   -analyzer-checker=nullability.NullableDereferenced\
+// RUN:   -DNOSYSTEMHEADERS=1 -fobjc-arc\
+// RUN:   -analyzer-config nullability:NoDiagnoseCallsToSystemHeaders=true
 
 #include "Inputs/system-header-simulator-for-nullability.h"
 
 @interface TestObject : NSObject
 - (int *_Nonnull)returnsNonnull;
 - (int *_Nullable)returnsNullable;
 - (int *)returnsUnspecified;
 - (void)takesNonnull:(int *_Nonnull)p;