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 namespace clang { 23 namespace ento { 24 namespace { 25 26 class FalsePositiveGenerator : public Checker<eval::Call> { 27 using Self = FalsePositiveGenerator; 28 const BuiltinBug FalsePositiveGeneratorBug{this, "FalsePositiveGenerator"}; 29 using HandlerFn = bool (Self::*)(const CallEvent &Call, 30 CheckerContext &) const; 31 CallDescriptionMap<HandlerFn> Callbacks = { 32 {{"reachedWithContradiction", 0}, &Self::reachedWithContradiction}, 33 {{"reachedWithNoContradiction", 0}, &Self::reachedWithNoContradiction}, 34 {{"reportIfCanBeTrue", 1}, &Self::reportIfCanBeTrue}, 35 }; 36 37 bool report(CheckerContext &C, ProgramStateRef State, 38 StringRef Description) const { 39 ExplodedNode *Node = C.generateNonFatalErrorNode(State); 40 if (!Node) 41 return false; 42 43 auto Report = std::make_unique<PathSensitiveBugReport>( 44 FalsePositiveGeneratorBug, Description, Node); 45 C.emitReport(std::move(Report)); 46 return true; 47 } 48 49 bool reachedWithNoContradiction(const CallEvent &, CheckerContext &C) const { 50 return report(C, C.getState(), "REACHED_WITH_NO_CONTRADICTION"); 51 } 52 53 bool reachedWithContradiction(const CallEvent &, CheckerContext &C) const { 54 return report(C, C.getState(), "REACHED_WITH_CONTRADICTION"); 55 } 56 57 // Similar to ExprInspectionChecker::analyzerEval except it emits warning only 58 // if the argument can be true. The report emits the report in the state where 59 // the assertion true. 60 bool reportIfCanBeTrue(const CallEvent &Call, CheckerContext &C) const { 61 // A specific instantiation of an inlined function may have more constrained 62 // values than can generally be assumed. Skip the check. 63 if (C.getPredecessor()->getLocationContext()->getStackFrame()->getParent()) 64 return false; 65 66 SVal AssertionVal = Call.getArgSVal(0); 67 if (AssertionVal.isUndef()) 68 return false; 69 70 ProgramStateRef State = C.getPredecessor()->getState(); 71 ProgramStateRef StTrue; 72 std::tie(StTrue, std::ignore) = 73 State->assume(AssertionVal.castAs<DefinedOrUnknownSVal>()); 74 if (StTrue) 75 return report(C, StTrue, "CAN_BE_TRUE"); 76 return false; 77 } 78 79 public: 80 bool evalCall(const CallEvent &Call, CheckerContext &C) const { 81 if (const HandlerFn *Callback = Callbacks.lookup(Call)) 82 return (this->*(*Callback))(Call, C); 83 return false; 84 } 85 }; 86 87 void addFalsePositiveGenerator(AnalysisASTConsumer &AnalysisConsumer, 88 AnalyzerOptions &AnOpts) { 89 AnOpts.CheckersAndPackages = {{"test.FalsePositiveGenerator", true}, 90 {"debug.ViewExplodedGraph", false}}; 91 AnalysisConsumer.AddCheckerRegistrationFn([](CheckerRegistry &Registry) { 92 Registry.addChecker<FalsePositiveGenerator>( 93 "test.FalsePositiveGenerator", "EmptyDescription", "EmptyDocsUri"); 94 }); 95 } 96 97 class FalsePositiveRefutationBRVisitorTestBase : public testing::Test { 98 public: 99 void SetUp() override { 100 #ifndef LLVM_WITH_Z3 101 GTEST_SKIP() << "Requires the LLVM_ENABLE_Z3_SOLVER cmake option."; 102 #endif 103 } 104 }; 105 106 // C++20 use constexpr below. 107 const std::vector<std::string> LazyAssumeArgs{ 108 "-Xclang", "-analyzer-config", "-Xclang", "eagerly-assume=false"}; 109 const std::vector<std::string> LazyAssumeAndCrossCheckArgs{ 110 "-Xclang", "-analyzer-config", "-Xclang", "eagerly-assume=false", 111 "-Xclang", "-analyzer-config", "-Xclang", "crosscheck-with-z3=true"}; 112 113 TEST_F(FalsePositiveRefutationBRVisitorTestBase, UnSatInTheMiddleNoReport) { 114 constexpr auto Code = R"( 115 void reachedWithContradiction(); 116 void reachedWithNoContradiction(); 117 void test(int x, int y) { 118 if (x * y == 0) 119 return; 120 reachedWithNoContradiction(); 121 if (x == 0) { 122 reachedWithContradiction(); 123 // x * y != 0 => x != 0 && y != 0 => contradict with x == 0 124 } 125 })"; 126 127 std::string Diags; 128 EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>( 129 Code, LazyAssumeAndCrossCheckArgs, Diags)); 130 EXPECT_EQ(Diags, 131 "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n"); 132 // Single warning. The second report was invalidated by the visitor. 133 134 // Without enabling the crosscheck-with-z3 both reports are displayed. 135 std::string Diags2; 136 EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>( 137 Code, LazyAssumeArgs, Diags2)); 138 EXPECT_EQ(Diags2, 139 "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n" 140 "test.FalsePositiveGenerator:REACHED_WITH_CONTRADICTION\n"); 141 } 142 143 TEST_F(FalsePositiveRefutationBRVisitorTestBase, 144 UnSatAtErrorNodeWithNewSymbolNoReport) { 145 constexpr auto Code = R"( 146 void reportIfCanBeTrue(bool); 147 void reachedWithNoContradiction(); 148 void test(int x, int y) { 149 if (x * y == 0) 150 return; 151 // We know that 'x * y': {[MIN,-1], [1,MAX]} 152 reachedWithNoContradiction(); 153 reportIfCanBeTrue(x == 0); // contradiction 154 // The function introduces the 'x == 0' constraint in the ErrorNode which 155 // leads to contradiction with the constraint of 'x * y'. 156 // Note that the new constraint was bound to a new symbol 'x'. 157 })"; 158 std::string Diags; 159 EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>( 160 Code, LazyAssumeAndCrossCheckArgs, Diags)); 161 EXPECT_EQ(Diags, 162 "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n"); 163 // Single warning. The second report was invalidated by the visitor. 164 165 // Without enabling the crosscheck-with-z3 both reports are displayed. 166 std::string Diags2; 167 EXPECT_TRUE(runCheckerOnCodeWithArgs<addFalsePositiveGenerator>( 168 Code, LazyAssumeArgs, Diags2)); 169 EXPECT_EQ(Diags2, 170 "test.FalsePositiveGenerator:REACHED_WITH_NO_CONTRADICTION\n" 171 "test.FalsePositiveGenerator:CAN_BE_TRUE\n"); 172 } 173 174 TEST_F(FalsePositiveRefutationBRVisitorTestBase, 175 UnSatAtErrorNodeDueToRefinedConstraintNoReport) { 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