llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang-analysis Author: Utkarsh Saxena (usx95) <details> <summary>Changes</summary> Implement use-after-free detection in the lifetime safety analysis with two warning levels. - Added a `LifetimeSafetyReporter` interface for reporting lifetime safety issues - Created two warning levels: - Definite errors (reported with `-Wexperimental-lifetime-safety-permissive`) - Potential errors (reported with `-Wexperimental-lifetime-safety-strict`) - Implemented a `LifetimeChecker` class that analyzes loan propagation and expired loans to detect use-after-free issues. - Added tracking of use sites through a new `UseFact` class. - Enhanced the `ExpireFact` to track the expressions where objects are destroyed. - Added test cases for both definite and potential use-after-free scenarios. The implementation now tracks pointer uses and can determine when a pointer is dereferenced after its loan has been expired, with appropriate diagnostics. The two warning levels provide flexibility - definite errors for high-confidence issues and potential errors for cases that depend on control flow. --- Patch is 36.32 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/149731.diff 7 Files Affected: - (modified) clang/include/clang/Analysis/Analyses/LifetimeSafety.h (+49-3) - (modified) clang/include/clang/Basic/DiagnosticGroups.td (+8-1) - (modified) clang/include/clang/Basic/DiagnosticSemaKinds.td (+9-3) - (modified) clang/lib/Analysis/LifetimeSafety.cpp (+210-48) - (modified) clang/lib/Sema/AnalysisBasedWarnings.cpp (+30-2) - (added) clang/test/Sema/warn-lifetime-safety.cpp (+263) - (modified) clang/unittests/Analysis/LifetimeSafetyTest.cpp (+11-4) ``````````diff diff --git a/clang/include/clang/Analysis/Analyses/LifetimeSafety.h b/clang/include/clang/Analysis/Analyses/LifetimeSafety.h index 1c00558d32f63..bd7e76b1bc238 100644 --- a/clang/include/clang/Analysis/Analyses/LifetimeSafety.h +++ b/clang/include/clang/Analysis/Analyses/LifetimeSafety.h @@ -19,14 +19,35 @@ #define LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_H #include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" +#include "clang/Basic/SourceLocation.h" +#include "llvm/ADT/DenseMapInfo.h" +#include "llvm/ADT/ImmutableMap.h" #include "llvm/ADT/ImmutableSet.h" #include "llvm/ADT/StringMap.h" #include <memory> namespace clang::lifetimes { +/// Enum to track the confidence level of a potential error. +enum class Confidence { + None, + Maybe, // Reported as a potential error (-Wlifetime-safety-strict) + Definite // Reported as a definite error (-Wlifetime-safety-permissive) +}; + +class LifetimeSafetyReporter { +public: + LifetimeSafetyReporter() = default; + virtual ~LifetimeSafetyReporter() = default; + + virtual void reportUseAfterFree(const Expr *IssueExpr, const Expr *UseExpr, + SourceLocation FreeLoc, + Confidence Confidence) {} +}; + /// The main entry point for the analysis. -void runLifetimeSafetyAnalysis(AnalysisDeclContext &AC); +void runLifetimeSafetyAnalysis(AnalysisDeclContext &AC, + LifetimeSafetyReporter *Reporter); namespace internal { // Forward declarations of internal types. @@ -53,6 +74,7 @@ template <typename Tag> struct ID { IDBuilder.AddInteger(Value); } }; + template <typename Tag> inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, ID<Tag> ID) { return OS << ID.Value; @@ -66,6 +88,7 @@ using OriginID = ID<struct OriginTag>; // TODO(opt): Consider using a bitset to represent the set of loans. using LoanSet = llvm::ImmutableSet<LoanID>; using OriginSet = llvm::ImmutableSet<OriginID>; +using ExpiredLoanMap = llvm::ImmutableMap<LoanID, const Fact *>; /// A `ProgramPoint` identifies a location in the CFG by pointing to a specific /// `Fact`. identified by a lifetime-related event (`Fact`). @@ -78,7 +101,8 @@ using ProgramPoint = const Fact *; /// encapsulates the various dataflow analyses. class LifetimeSafetyAnalysis { public: - LifetimeSafetyAnalysis(AnalysisDeclContext &AC); + LifetimeSafetyAnalysis(AnalysisDeclContext &AC, + LifetimeSafetyReporter *Reporter); ~LifetimeSafetyAnalysis(); void run(); @@ -87,7 +111,7 @@ class LifetimeSafetyAnalysis { LoanSet getLoansAtPoint(OriginID OID, ProgramPoint PP) const; /// Returns the set of loans that have expired at a specific program point. - LoanSet getExpiredLoansAtPoint(ProgramPoint PP) const; + ExpiredLoanMap getExpiredLoansAtPoint(ProgramPoint PP) const; /// Finds the OriginID for a given declaration. /// Returns a null optional if not found. @@ -110,6 +134,7 @@ class LifetimeSafetyAnalysis { private: AnalysisDeclContext &AC; + LifetimeSafetyReporter *Reporter; std::unique_ptr<LifetimeFactory> Factory; std::unique_ptr<FactManager> FactMgr; std::unique_ptr<LoanPropagationAnalysis> LoanPropagation; @@ -118,4 +143,25 @@ class LifetimeSafetyAnalysis { } // namespace internal } // namespace clang::lifetimes +namespace llvm { +template <typename Tag> +struct DenseMapInfo<clang::lifetimes::internal::ID<Tag>> { + using ID = clang::lifetimes::internal::ID<Tag>; + + static inline ID getEmptyKey() { + return {DenseMapInfo<uint32_t>::getEmptyKey()}; + } + + static inline ID getTombstoneKey() { + return {DenseMapInfo<uint32_t>::getTombstoneKey()}; + } + + static unsigned getHashValue(const ID &Val) { + return DenseMapInfo<uint32_t>::getHashValue(Val.Value); + } + + static bool isEqual(const ID &LHS, const ID &RHS) { return LHS == RHS; } +}; +} // namespace llvm + #endif // LLVM_CLANG_ANALYSIS_ANALYSES_LIFETIMESAFETY_H diff --git a/clang/include/clang/Basic/DiagnosticGroups.td b/clang/include/clang/Basic/DiagnosticGroups.td index ccb18aa37447e..2edf4da435366 100644 --- a/clang/include/clang/Basic/DiagnosticGroups.td +++ b/clang/include/clang/Basic/DiagnosticGroups.td @@ -533,7 +533,14 @@ def Dangling : DiagGroup<"dangling", [DanglingAssignment, DanglingGsl, ReturnStackAddress]>; -def LifetimeSafety : DiagGroup<"experimental-lifetime-safety">; +def LifetimeSafetyPermissive : DiagGroup<"experimental-lifetime-safety-permissive">; +def LifetimeSafetyStrict : DiagGroup<"experimental-lifetime-safety-strict">; +def LifetimeSafety : DiagGroup<"experimental-lifetime-safety", + [LifetimeSafetyPermissive, LifetimeSafetyStrict]> { + code Documentation = [{ + Experimental warnings to detect use-after-free and related temporal safety bugs based on lifetime safety analysis. + }]; +} def DistributedObjectModifiers : DiagGroup<"distributed-object-modifiers">; def DllexportExplicitInstantiationDecl : DiagGroup<"dllexport-explicit-instantiation-decl">; diff --git a/clang/include/clang/Basic/DiagnosticSemaKinds.td b/clang/include/clang/Basic/DiagnosticSemaKinds.td index 4a213212f185f..181d564f097ca 100644 --- a/clang/include/clang/Basic/DiagnosticSemaKinds.td +++ b/clang/include/clang/Basic/DiagnosticSemaKinds.td @@ -10641,9 +10641,15 @@ def warn_dangling_reference_captured_by_unknown : Warning< "object whose reference is captured will be destroyed at the end of " "the full-expression">, InGroup<DanglingCapture>; -def warn_experimental_lifetime_safety_dummy_warning : Warning< - "todo: remove this warning after we have atleast one warning based on the lifetime analysis">, - InGroup<LifetimeSafety>, DefaultIgnore; +// Diagnostics based on the Lifetime safety analysis. +def warn_lifetime_safety_loan_expires_permissive : Warning< + "object whose reference is captured does not live long enough">, + InGroup<LifetimeSafetyPermissive>, DefaultIgnore; +def warn_lifetime_safety_loan_expires_strict : Warning< + "object whose reference is captured may not live long enough">, + InGroup<LifetimeSafetyStrict>, DefaultIgnore; +def note_lifetime_safety_used_here : Note<"later used here">; +def note_lifetime_safety_destroyed_here : Note<"destroyed here">; // For non-floating point, expressions of the form x == x or x != x // should result in a warning, since these always evaluate to a constant. diff --git a/clang/lib/Analysis/LifetimeSafety.cpp b/clang/lib/Analysis/LifetimeSafety.cpp index 94b8197bbf6f3..2cb88bc78d81a 100644 --- a/clang/lib/Analysis/LifetimeSafety.cpp +++ b/clang/lib/Analysis/LifetimeSafety.cpp @@ -45,10 +45,11 @@ struct Loan { /// is represented as empty LoanSet LoanID ID; AccessPath Path; - SourceLocation IssueLoc; + /// The expression that creates the loan, e.g., &x. + const Expr *IssueExpr; - Loan(LoanID id, AccessPath path, SourceLocation loc) - : ID(id), Path(path), IssueLoc(loc) {} + Loan(LoanID id, AccessPath path, const Expr *IssueExpr) + : ID(id), Path(path), IssueExpr(IssueExpr) {} }; /// An Origin is a symbolic identifier that represents the set of possible @@ -82,8 +83,8 @@ class LoanManager { public: LoanManager() = default; - Loan &addLoan(AccessPath Path, SourceLocation Loc) { - AllLoans.emplace_back(getNextLoanID(), Path, Loc); + Loan &addLoan(AccessPath Path, const Expr *IssueExpr) { + AllLoans.emplace_back(getNextLoanID(), Path, IssueExpr); return AllLoans.back(); } @@ -199,6 +200,8 @@ class Fact { AssignOrigin, /// An origin escapes the function by flowing into the return value. ReturnOfOrigin, + /// An origin is used (eg. dereferencing a pointer). + Use, /// A marker for a specific point in the code, for testing. TestPoint, }; @@ -242,12 +245,17 @@ class IssueFact : public Fact { class ExpireFact : public Fact { LoanID LID; + SourceLocation ExpiryLoc; public: static bool classof(const Fact *F) { return F->getKind() == Kind::Expire; } - ExpireFact(LoanID LID) : Fact(Kind::Expire), LID(LID) {} + ExpireFact(LoanID LID, SourceLocation ExpiryLoc) + : Fact(Kind::Expire), LID(LID), ExpiryLoc(ExpiryLoc) {} + LoanID getLoanID() const { return LID; } + SourceLocation getExpiryLoc() const { return ExpiryLoc; } + void dump(llvm::raw_ostream &OS) const override { OS << "Expire (LoanID: " << getLoanID() << ")\n"; } @@ -287,6 +295,24 @@ class ReturnOfOriginFact : public Fact { } }; +class UseFact : public Fact { + OriginID UsedOrigin; + const Expr *UseExpr; + +public: + static bool classof(const Fact *F) { return F->getKind() == Kind::Use; } + + UseFact(OriginID UsedOrigin, const Expr *UseExpr) + : Fact(Kind::Use), UsedOrigin(UsedOrigin), UseExpr(UseExpr) {} + + OriginID getUsedOrigin() const { return UsedOrigin; } + const Expr *getUseExpr() const { return UseExpr; } + + void dump(llvm::raw_ostream &OS) const override { + OS << "Use (OriginID: " << UsedOrigin << ")\n"; + } +}; + /// A dummy-fact used to mark a specific point in the code for testing. /// It is generated by recognizing a `void("__lifetime_test_point_...")` cast. class TestPointFact : public Fact { @@ -417,13 +443,17 @@ class FactGenerator : public ConstStmtVisitor<FactGenerator> { if (VD->hasLocalStorage()) { OriginID OID = FactMgr.getOriginMgr().getOrCreate(*UO); AccessPath AddrOfLocalVarPath(VD); - const Loan &L = FactMgr.getLoanMgr().addLoan(AddrOfLocalVarPath, - UO->getOperatorLoc()); + const Loan &L = + FactMgr.getLoanMgr().addLoan(AddrOfLocalVarPath, UO); CurrentBlockFacts.push_back( FactMgr.createFact<IssueFact>(L.ID, OID)); } } } + } else if (UO->getOpcode() == UO_Deref) { + // This is a pointer use, like '*p'. + OriginID OID = FactMgr.getOriginMgr().get(*UO->getSubExpr()); + CurrentBlockFacts.push_back(FactMgr.createFact<UseFact>(OID, UO)); } } @@ -492,7 +522,8 @@ class FactGenerator : public ConstStmtVisitor<FactGenerator> { // Check if the loan is for a stack variable and if that variable // is the one being destructed. if (LoanPath.D == DestructedVD) - CurrentBlockFacts.push_back(FactMgr.createFact<ExpireFact>(L.ID)); + CurrentBlockFacts.push_back(FactMgr.createFact<ExpireFact>( + L.ID, DtorOpt.getTriggerStmt()->getEndLoc())); } } @@ -616,6 +647,7 @@ class DataflowAnalysis { } } +protected: Lattice getState(ProgramPoint P) const { return PerPointStates.lookup(P); } Lattice getInState(const CFGBlock *B) const { return InStates.lookup(B); } @@ -663,6 +695,8 @@ class DataflowAnalysis { return D->transfer(In, *F->getAs<AssignOriginFact>()); case Fact::Kind::ReturnOfOrigin: return D->transfer(In, *F->getAs<ReturnOfOriginFact>()); + case Fact::Kind::Use: + return D->transfer(In, *F->getAs<UseFact>()); case Fact::Kind::TestPoint: return D->transfer(In, *F->getAs<TestPointFact>()); } @@ -674,6 +708,7 @@ class DataflowAnalysis { Lattice transfer(Lattice In, const ExpireFact &) { return In; } Lattice transfer(Lattice In, const AssignOriginFact &) { return In; } Lattice transfer(Lattice In, const ReturnOfOriginFact &) { return In; } + Lattice transfer(Lattice In, const UseFact &) { return In; } Lattice transfer(Lattice In, const TestPointFact &) { return In; } }; @@ -691,6 +726,20 @@ static llvm::ImmutableSet<T> join(llvm::ImmutableSet<T> A, return A; } +/// Checks if set A is a subset of set B. +template <typename T> +static bool isSubsetOf(const llvm::ImmutableSet<T> &A, + const llvm::ImmutableSet<T> &B) { + // Empty set is a subset of all sets. + if (A.isEmpty()) + return true; + + for (const T &Elem : A) + if (!B.contains(Elem)) + return false; + return true; +} + /// Computes the key-wise union of two ImmutableMaps. // TODO(opt): This key-wise join is a performance bottleneck. A more // efficient merge could be implemented using a Patricia Trie or HAMT @@ -698,7 +747,7 @@ static llvm::ImmutableSet<T> join(llvm::ImmutableSet<T> A, template <typename K, typename V, typename Joiner> static llvm::ImmutableMap<K, V> join(llvm::ImmutableMap<K, V> A, llvm::ImmutableMap<K, V> B, - typename llvm::ImmutableMap<K, V>::Factory &F, Joiner joinValues) { + typename llvm::ImmutableMap<K, V>::Factory &F, Joiner JoinValues) { if (A.getHeight() < B.getHeight()) std::swap(A, B); @@ -708,7 +757,7 @@ join(llvm::ImmutableMap<K, V> A, llvm::ImmutableMap<K, V> B, const K &Key = Entry.first; const V &ValB = Entry.second; if (const V *ValA = A.lookup(Key)) - A = F.add(A, Key, joinValues(*ValA, ValB)); + A = F.add(A, Key, JoinValues(*ValA, ValB)); else A = F.add(A, Key, ValB); } @@ -727,11 +776,7 @@ using OriginLoanMap = llvm::ImmutableMap<OriginID, LoanSet>; struct LifetimeFactory { OriginLoanMap::Factory OriginMapFactory; LoanSet::Factory LoanSetFactory; - - /// Creates a singleton set containing only the given loan ID. - LoanSet createLoanSet(LoanID LID) { - return LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID); - } + ExpiredLoanMap::Factory ExpiredLoanMapFactory; }; /// Represents the dataflow lattice for loan propagation. @@ -772,13 +817,15 @@ struct LoanPropagationLattice { class LoanPropagationAnalysis : public DataflowAnalysis<LoanPropagationAnalysis, LoanPropagationLattice, Direction::Forward> { - - LifetimeFactory &Factory; + OriginLoanMap::Factory &OriginLoanMapFactory; + LoanSet::Factory &LoanSetFactory; public: LoanPropagationAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F, - LifetimeFactory &Factory) - : DataflowAnalysis(C, AC, F), Factory(Factory) {} + LifetimeFactory &LFactory) + : DataflowAnalysis(C, AC, F), + OriginLoanMapFactory(LFactory.OriginMapFactory), + LoanSetFactory(LFactory.LoanSetFactory) {} using Base::transfer; @@ -790,9 +837,9 @@ class LoanPropagationAnalysis // TODO(opt): Keep the state small by removing origins which become dead. Lattice join(Lattice A, Lattice B) { OriginLoanMap JoinedOrigins = - utils::join(A.Origins, B.Origins, Factory.OriginMapFactory, - [this](LoanSet S1, LoanSet S2) { - return utils::join(S1, S2, Factory.LoanSetFactory); + utils::join(A.Origins, B.Origins, OriginLoanMapFactory, + [&](LoanSet S1, LoanSet S2) { + return utils::join(S1, S2, LoanSetFactory); }); return Lattice(JoinedOrigins); } @@ -801,8 +848,9 @@ class LoanPropagationAnalysis Lattice transfer(Lattice In, const IssueFact &F) { OriginID OID = F.getOriginID(); LoanID LID = F.getLoanID(); - return LoanPropagationLattice(Factory.OriginMapFactory.add( - In.Origins, OID, Factory.createLoanSet(LID))); + return LoanPropagationLattice(OriginLoanMapFactory.add( + In.Origins, OID, + LoanSetFactory.add(LoanSetFactory.getEmptySet(), LID))); } /// The destination origin's loan set is replaced by the source's. @@ -812,7 +860,7 @@ class LoanPropagationAnalysis OriginID SrcOID = F.getSrcOriginID(); LoanSet SrcLoans = getLoans(In, SrcOID); return LoanPropagationLattice( - Factory.OriginMapFactory.add(In.Origins, DestOID, SrcLoans)); + OriginLoanMapFactory.add(In.Origins, DestOID, SrcLoans)); } LoanSet getLoans(OriginID OID, ProgramPoint P) { @@ -823,7 +871,7 @@ class LoanPropagationAnalysis LoanSet getLoans(Lattice L, OriginID OID) { if (auto *Loans = L.Origins.lookup(OID)) return *Loans; - return Factory.LoanSetFactory.getEmptySet(); + return LoanSetFactory.getEmptySet(); } }; @@ -833,10 +881,11 @@ class LoanPropagationAnalysis /// The dataflow lattice for tracking the set of expired loans. struct ExpiredLattice { - LoanSet Expired; + /// Map from an expired `LoanID` to the `ExpireFact` that made it expire. + ExpiredLoanMap Expired; ExpiredLattice() : Expired(nullptr) {}; - explicit ExpiredLattice(LoanSet S) : Expired(S) {} + explicit ExpiredLattice(ExpiredLoanMap M) : Expired(M) {} bool operator==(const ExpiredLattice &Other) const { return Expired == Other.Expired; @@ -849,8 +898,8 @@ struct ExpiredLattice { OS << "ExpiredLattice State:\n"; if (Expired.isEmpty()) OS << " <empty>\n"; - for (const LoanID &LID : Expired) - OS << " Loan " << LID << " is expired\n"; + for (const auto &ID_ : Expired) + OS << " Loan " << ID_.first << " is expired\n"; } }; @@ -859,26 +908,28 @@ class ExpiredLoansAnalysis : public DataflowAnalysis<ExpiredLoansAnalysis, ExpiredLattice, Direction::Forward> { - LoanSet::Factory &Factory; + ExpiredLoanMap::Factory &Factory; public: ExpiredLoansAnalysis(const CFG &C, AnalysisDeclContext &AC, FactManager &F, LifetimeFactory &Factory) - : DataflowAnalysis(C, AC, F), Factory(Factory.LoanSetFactory) {} + : DataflowAnalysis(C, AC, F), Factory(Factory.ExpiredLoanMapFactory) {} using Base::transfer; StringRef getAnalysisName() const { return "ExpiredLoans"; } - Lattice getInitialState() { return Lattice(Factory.getEmptySet()); } + Lattice getInitialState() { return Lattice(Factory.getEmptyMap()); } - /// Merges two lattices by taking the union of the expired loan sets. - Lattice join(Lattice L1, Lattice L2) const { - return Lattice(utils::join(L1.Expired, L2.Expired, Factory)); + /// Merges two lattices by taking the union of the two expired loans. + Lattice join(Lattice L1, Lattice L2) { + return Lattice(utils::join(L1.Expired, L2.Expired, Factory, + // Take any ExpireFact to join the values. + [](const Fact *F, const Fact *) { return F; })); } Lattice transfer(Lattice In, const ExpireFact &F) { - return Lattice(Factory.add(In.Expired, F.getLoanID())); + return Lattice(Factory.add(In.Expired, F.getLoanID(), &F)); } // Removes the loan from the set of expired loans. @@ -910,15 +961,119 @@ class ExpiredLoansAnalysis Lattice transfer(Lattice In, const IssueFact &F) { return Lattice(Factory.remove(In.Expired, F.getLoanID())); } + + ExpiredLoanMap getExpiredLoans(ProgramPoint P) { return getState(P).Expired; } }; // ========================================================================= // -// TODO: -// - Modify loan expiry analysis to answer `bool isExpired(Loan L, Point P)` -// - Modify origin liveness analysis to answer `bool isLive(Origin O, Point P)` -// - Using the above three to perform the final error reporting. +// Lifetime checker and Error reporter // ========================================================================= // +/// Struct to store the complete context for a potential lifetime violation. +struct PendingWarning { + const Expr *IssueExpr; // Where the loan was originally issued. + SourceLocation ExpiryLoc; // Where the loan expired. + const Expr *UseExpr; // Where the origin holding this loan was used. + Confidence Level; +}; + +class LifetimeChecker { +private: + llvm::DenseMap<LoanID, PendingWarning> FinalWarningsMap; + LoanPropagationAnalysis &LoanPropagation; + ExpiredLoansAnalysis &ExpiredLoans; + FactManager &FactMgr; + AnalysisDeclContext &ADC; + LifetimeSafetyReporter *Reporter; + +public: + LifetimeChecker(LoanPropagationAnalysis &LPA, ExpiredLoansAnalysis &ELA, + FactManager &FM, AnalysisDeclContext &ADC, + LifetimeSafetyReporter *Reporter) + : LoanPropagation(LPA), ExpiredLoans(ELA), FactMgr(FM), ADC(ADC), + Reporter(Reporter) {} + + void run() { + llvm::TimeTraceScope TimeProfile("LifetimeChecker"); + for (const CFGBlock *B : *ADC.getAnalysis<PostOrderCFGView>()) + for (const Fact *F : FactMgr.getFacts(B)) + if (const auto *UF = F->getAs<UseFact>()) + checkUse(UF); ... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/149731 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
