1 //===- unittests/StaticAnalyzer/FalsePositiveRefutationBRVisitorTest.cpp --===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "CheckerRegistration.h" 10 #include "Reusables.h" 11 #include "clang/Frontend/CompilerInstance.h" 12 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 13 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 14 #include "clang/StaticAnalyzer/Core/Checker.h" 15 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 16 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 17 #include "clang/StaticAnalyzer/Frontend/AnalysisConsumer.h" 18 #include "clang/StaticAnalyzer/Frontend/CheckerRegistry.h" 19 #include "llvm/Config/llvm-config.h" 20 #include "gtest/gtest.h" 21 22 // FIXME: Use GTEST_SKIP() instead if GTest is updated to version 1.10.0 23 #ifdef LLVM_WITH_Z3 24 #define SKIP_WITHOUT_Z3 25 #else 26 #define SKIP_WITHOUT_Z3 return 27 #endif 28 29 namespace clang { 30 namespace ento { 31 namespace { 32 33 class FalsePositiveGenerator : public Checker<eval::Call> { 34 using Self = FalsePositiveGenerator; 35 const BuiltinBug FalsePositiveGeneratorBug{this, "FalsePositiveGenerator"}; 36 using HandlerFn = bool (Self::*)(const CallEvent &Call, 37 CheckerContext &) const; 38 CallDescriptionMap<HandlerFn> Callbacks = { 39 {{"reachedWithContradiction", 0}, &Self::reachedWithContradiction}, 40 {{"reachedWithNoContradiction", 0}, &Self::reachedWithNoContradiction}, 41 {{"reportIfCanBeTrue", 1}, &Self::reportIfCanBeTrue}, 42 }; 43 44 bool report(CheckerContext &C, ProgramStateRef State, 45 StringRef Description) const { 46 ExplodedNode *Node = C.generateNonFatalErrorNode(State); 47 if (!Node) 48 return false; 49 50 auto Report = std::make_unique<PathSensitiveBugReport>( 51 FalsePositiveGeneratorBug, Description, Node); 52 C.emitReport(std::move(Report)); 53 return true; 54 } 55 56 bool reachedWithNoContradiction(const CallEvent &, CheckerContext &C) const { 57 return report(C, C.getState(), "REACHED_WITH_NO_CONTRADICTION"); 58 } 59 60 bool reachedWithContradiction(const CallEvent &, CheckerContext &C) const { 61 return report(C, C.getState(), "REACHED_WITH_CONTRADICTION"); 62 } 63 64 // Similar to ExprInspectionChecker::analyzerEval except it emits warning only 65 // if the argument can be true. The report emits the report in the state where 66 // the assertion true. 67 bool reportIfCanBeTrue(const CallEvent &Call, CheckerContext &C) const { 68 // A specific instantiation of an inlined function may have more constrained 69 // values than can generally be assumed. Skip the check. 70 if (C.getPredecessor()->getLocationContext()->getStackFrame()->getParent()) 71 return false; 72 73 SVal AssertionVal = Call.getArgSVal(0); 74 if (AssertionVal.isUndef()) 75 return false; 76 77 ProgramStateRef State = C.getPredecessor()->getState(); 78 ProgramStateRef StTrue; 79 std::tie(StTrue, std::ignore) = 80 State->assume(AssertionVal.castAs<DefinedOrUnknownSVal>()); 81 if (StTrue) 82 return report(C, StTrue, "CAN_BE_TRUE"); 83 return false; 84 } 85 86 public: 87 bool evalCall(const CallEvent &Call, CheckerContext &C) const { 88 if (const HandlerFn *Callback = Callbacks.lookup(Call)) 89 return (this->*(*Callback))(Call, C); 90 return false; 91 } 92 }; 93 94 void addFalsePositiveGenerator(AnalysisASTConsumer &AnalysisConsumer, 95 AnalyzerOptions &AnOpts) { 96 AnOpts.CheckersAndPackages = {{"test.FalsePositiveGenerator", true}, 97 {"debug.ViewExplodedGraph", false}}; 98 AnalysisConsumer.AddCheckerRegistrationFn([](CheckerRegistry &Registry) { 99 Registry.addChecker<FalsePositiveGenerator>( 100 "test.FalsePositiveGenerator", "EmptyDescription", "EmptyDocsUri"); 101 }); 102 } 103 104 // C++20 use constexpr below. 105 const std::vector<std::string> LazyAssumeArgs{ 106 "-Xclang", "-analyzer-config", "-Xclang", "eagerly-assume=false"}; 107 const std::vector<std::string> LazyAssumeAndCrossCheckArgs{ 108 "-Xclang", "-analyzer-config", "-Xclang", "eagerly-assume=false", 109 "-Xclang", "-analyzer-config", "-Xclang", "crosscheck-with-z3=true"}; 110 111 TEST(FalsePositiveRefutationBRVisitor, UnSatInTheMiddleNoReport) { 112 SKIP_WITHOUT_Z3; 113 constexpr auto Code = R"( 114 void reachedWithContradiction(); 115 void reachedWithNoContradiction(); 116 void test(int x, int y) { 117 if (x * y == 0) 118 return; 119 reachedWithNoContradiction(); 120 if (x == 0) { 121 reachedWithContradiction(); 122 // x * y != 0 => x != 0 && y != 0 => contradict with x == 0 123 } 124 })"; 125 126 std::string Diags; 127 EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>( 128 Code, LazyAssumeAndCrossCheckArgs, Diags)); 129 EXPECT_EQ(Diags, 130 "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n"); 131 // Single warning. The second report was invalidated by the visitor. 132 133 // Without enabling the crosscheck-with-z3 both reports are displayed. 134 std::string Diags2; 135 EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>( 136 Code, LazyAssumeArgs, Diags2)); 137 EXPECT_EQ(Diags2, 138 "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n" 139 "test.FalsePositiveGenerator:REACHED_WITH_CONTRADICTION\n"); 140 } 141 142 TEST(FalsePositiveRefutationBRVisitor, UnSatAtErrorNodeWithNewSymbolNoReport) { 143 SKIP_WITHOUT_Z3; 144 constexpr auto Code = R"( 145 void reportIfCanBeTrue(bool); 146 void reachedWithNoContradiction(); 147 void test(int x, int y) { 148 if (x * y == 0) 149 return; 150 // We know that 'x * y': {[MIN,-1], [1,MAX]} 151 reachedWithNoContradiction(); 152 reportIfCanBeTrue(x == 0); // contradiction 153 // The function introduces the 'x == 0' constraint in the ErrorNode which 154 // leads to contradiction with the constraint of 'x * y'. 155 // Note that the new constraint was bound to a new symbol 'x'. 156 })"; 157 std::string Diags; 158 EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>( 159 Code, LazyAssumeAndCrossCheckArgs, Diags)); 160 EXPECT_EQ(Diags, 161 "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n"); 162 // Single warning. The second report was invalidated by the visitor. 163 164 // Without enabling the crosscheck-with-z3 both reports are displayed. 165 std::string Diags2; 166 EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>( 167 Code, LazyAssumeArgs, Diags2)); 168 EXPECT_EQ(Diags2, 169 "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n" 170 "test.FalsePositiveGenerator:CAN_BE_TRUE\n"); 171 } 172 173 TEST(FalsePositiveRefutationBRVisitor, 174 UnSatAtErrorNodeDueToRefinedConstraintNoReport) { 175 SKIP_WITHOUT_Z3; 176 constexpr auto Code = R"( 177 void reportIfCanBeTrue(bool); 178 void reachedWithNoContradiction(); 179 void test(unsigned x, unsigned n) { 180 if (n >= 1 && n <= 2) { 181 if (x >= 3) 182 return; 183 // x: [0,2] and n: [1,2] 184 int y = x + n; // y: '(x+n)' Which is in approximately between 1 and 4. 185 186 // Registers the symbol 'y' with the constraint [1, MAX] in the true 187 // branch. 188 if (y > 0) { 189 // Since the x: [0,2] and n: [1,2], the 'y' is indeed greater than 190 // zero. If we emit a warning here, the constraints on the BugPath is 191 // SAT. Therefore that report is NOT invalidated. 192 reachedWithNoContradiction(); // 'y' can be greater than zero. OK 193 194 // If we ask the analyzer whether the 'y' can be 5. It won't know, 195 // therefore, the state will be created where the 'y' expression is 5. 196 // Although, this assumption is false! 197 // 'y' can not be 5 if the maximal value of both x and n is 2. 198 // The BugPath which become UnSAT in the ErrorNode with a refined 199 // constraint, should be invalidated. 200 reportIfCanBeTrue(y == 5); 201 } 202 } 203 })"; 204 205 std::string Diags; 206 EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>( 207 Code, LazyAssumeAndCrossCheckArgs, Diags)); 208 EXPECT_EQ(Diags, 209 "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n"); 210 // Single warning. The second report was invalidated by the visitor. 211 212 // Without enabling the crosscheck-with-z3 both reports are displayed. 213 std::string Diags2; 214 EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>( 215 Code, LazyAssumeArgs, Diags2)); 216 EXPECT_EQ(Diags2, 217 "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n" 218 "test.FalsePositiveGenerator:CAN_BE_TRUE\n"); 219 } 220 221 } // namespace 222 } // namespace ento 223 } // namespace clang 224