llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang Author: Ziqing Luo (ziqingluo-90) <details> <summary>Changes</summary> Integrate the TypeConstrainedPointers analysis results into UnsafeBufferReachableAnalysis. The final result is filtered with type-constrainted pointers. The pointer flow graph is untouched. Removing type-constrained pointers from the graph will introduce unsoundness. Final step for rdar://179151541&179151882 --- Full diff: https://github.com/llvm/llvm-project/pull/209354.diff 10 Files Affected: - (modified) clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp (+59-15) - (modified) clang/lib/ScalableStaticAnalysis/Core/WholeProgramAnalysis/AnalysisDriver.cpp (+7-11) - (modified) clang/test/Analysis/Scalable/PointerFlow/external-inline-function-in-multi-tu.test (+1-1) - (modified) clang/test/Analysis/Scalable/PointerFlow/lref-to-rref-cast.test (+1-1) - (modified) clang/test/Analysis/Scalable/PointerFlow/multi-decl-contributor.cpp (+1-1) - (modified) clang/test/Analysis/Scalable/PointerFlow/multi-dim-pointer-flow-constraint.test (+1-1) - (added) clang/test/Analysis/Scalable/TypeConstrainedPointers/unsafe-buffer-reachable-excludes-type-constrained-main.cpp (+40) - (added) clang/test/Analysis/Scalable/TypeConstrainedPointers/unsafe-buffer-reachable-excludes-type-constrained-new-delete.cpp (+74) - (added) clang/test/Analysis/Scalable/ssaf-analyzer/Outputs/empty-pairs.json (+26) - (modified) clang/test/Analysis/Scalable/ssaf-analyzer/analyzer.test (+5-5) ``````````diff diff --git a/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp b/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp index e404eb294ee4b..2d0a58f81a0f0 100644 --- a/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp +++ b/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp @@ -16,7 +16,9 @@ #include "clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h" #include "clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelFormat.h" #include "clang/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlowAnalysis.h" +#include "clang/ScalableStaticAnalysis/Analyses/TypeConstrainedPointers/TypeConstrainedPointers.h" #include "clang/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsage.h" +#include "clang/ScalableStaticAnalysis/Core/Model/EntityId.h" #include "clang/ScalableStaticAnalysis/Core/Serialization/JSONFormat.h" #include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/AnalysisRegistry.h" #include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/SummaryAnalysis.h" @@ -124,12 +126,21 @@ JSONFormat::AnalysisResultRegistry::Add<UnsafeBufferReachableAnalysisResult> serializeUnsafeBufferReachableAnalysisResult, deserializeUnsafeBufferReachableAnalysisResult); -/// Computes all the reachable "nodes" (pointers) in a pointer flow graph from a -/// provided starter node set. Specifically, the starter set is the unsafe -/// pointers found by `UnsafeBufferUsageAnalysis`. +/// \brief Computes pointers (EPLs) that satisfy a specific set of constraints. +/// +/// The pointers must satisfy all of the following constraints: +/// +/// 1. **C1 (Unsafe):** Any pointer in `UnsafeBufferUsageAnalysisResult` +/// is considered unsafe. +/// 2. **C2 (Reachable):** If a pointer is reachable from an unsafe pointer in +/// the pointer flow graph (provided by `PointerFlowAnalysisResult`), it is +/// also unsafe. +/// 3. **C3 (Transformable):** Any pointer associated with type-constrained +/// entities is NOT transformable. class UnsafeBufferReachableAnalysis : public DerivedAnalysis<UnsafeBufferReachableAnalysisResult, PointerFlowAnalysisResult, + TypeConstrainedPointersAnalysisResult, UnsafeBufferUsageAnalysisResult> { /// BoundsPropagationGraph adds bounds propagation semantics to the @@ -186,6 +197,7 @@ class UnsafeBufferReachableAnalysis }; std::map<EntityId, BoundsPropagationGraph> BPG; + const std::set<EntityId> *TypeConstrainedEntities = nullptr; // Use pointers for efficiency. EPLs are in tree-based containers that only // grow. So pointers to them are stable. @@ -207,18 +219,9 @@ class UnsafeBufferReachableAnalysis } } -public: - llvm::Error - initialize(const PointerFlowAnalysisResult &PtrFlowGraph, - const UnsafeBufferUsageAnalysisResult &Starter) override { - for (auto &[Id, SubGraph] : PtrFlowGraph.Edges) - BPG.try_emplace(Id, BoundsPropagationGraph(SubGraph)); - assert(getResult().Reachables.empty()); - getResult().Reachables.insert(Starter.begin(), Starter.end()); - return llvm::Error::success(); - } - - llvm::Expected<bool> step() override { + // Expand the initial set of C1 pointers in `getResult().Reachables` by + // computing and appending all reachable pointers, satisfying both C1 and C2. + void computeReachableUnsafePointers() { auto &Reachables = getResult().Reachables; // Simple DFS: std::vector<EPLPtr> Worklist; @@ -233,6 +236,47 @@ class UnsafeBufferReachableAnalysis updateReachablesWithOutgoings(Node, Worklist); } + } + + // Filter out non-transformable pointers from `getResult().Result`, leaving + // only those that satisfy C3. + void filterTransformablePointers() { + assert(TypeConstrainedEntities && + "The initialize(...) method should initialize " + "TypeConstrainedEntities to non-null"); + auto &Result = getResult().Reachables; + + for (auto &[Key, EPLs] : Result) { + for (auto ConstrainedEntityId : *TypeConstrainedEntities) { + // FIXME: optimization chance here. Since both sets are sorted, the + // next 'equal_range' search can ignore everything before + // `NonTransEPLs.second`. + auto NonTransEPLs = EPLs.equal_range(ConstrainedEntityId); + + EPLs.erase(NonTransEPLs.first, NonTransEPLs.second); + } + } + } + +public: + llvm::Error + initialize(const PointerFlowAnalysisResult &PtrFlowGraph, + const TypeConstrainedPointersAnalysisResult &TypeConstraints, + const UnsafeBufferUsageAnalysisResult &UnsafePtrs) override { + for (auto &[Id, SubGraph] : PtrFlowGraph.Edges) + BPG.try_emplace(Id, BoundsPropagationGraph(SubGraph)); + TypeConstrainedEntities = &TypeConstraints.Entities; + assert(getResult().Reachables.empty()); + // C1: all pointers in UnsafeBufferUsageAnalysisResult are unsafe + getResult().Reachables.insert(UnsafePtrs.begin(), UnsafePtrs.end()); + return llvm::Error::success(); + } + + llvm::Expected<bool> step() override { + // result meets C1 & C2: + computeReachableUnsafePointers(); + // result meets C1 & C2 & C3: + filterTransformablePointers(); // This is not an iterative algorithm so stop iteration by retruning false: return false; } diff --git a/clang/lib/ScalableStaticAnalysis/Core/WholeProgramAnalysis/AnalysisDriver.cpp b/clang/lib/ScalableStaticAnalysis/Core/WholeProgramAnalysis/AnalysisDriver.cpp index f60c916e10b67..5f7940bbb8bb5 100644 --- a/clang/lib/ScalableStaticAnalysis/Core/WholeProgramAnalysis/AnalysisDriver.cpp +++ b/clang/lib/ScalableStaticAnalysis/Core/WholeProgramAnalysis/AnalysisDriver.cpp @@ -103,23 +103,19 @@ AnalysisDriver::toposort(llvm::ArrayRef<AnalysisName> Roots) { llvm::Error AnalysisDriver::executeSummaryAnalysis(SummaryAnalysisBase &Summary, WPASuite &Suite) const { SummaryName SN = Summary.getSummaryName(); - auto DataIt = LU->Data.find(SN); - if (DataIt == LU->Data.end()) { - return ErrorBuilder::create(std::errc::invalid_argument, - "no data for analysis '{0}' in LUSummary", - Summary.getAnalysisName()) - .build(); - } if (auto Err = Summary.initialize()) { return Err; } - for (auto &[Id, EntitySummary] : DataIt->second) { - if (auto Err = Summary.add(Id, *EntitySummary)) { - return Err; + auto DataIt = LU->Data.find(SN); + + if (DataIt != LU->Data.end()) + for (auto &[Id, EntitySummary] : DataIt->second) { + if (auto Err = Summary.add(Id, *EntitySummary)) { + return Err; + } } - } if (auto Err = Summary.finalize()) { return Err; diff --git a/clang/test/Analysis/Scalable/PointerFlow/external-inline-function-in-multi-tu.test b/clang/test/Analysis/Scalable/PointerFlow/external-inline-function-in-multi-tu.test index b0ffc1b3cf947..f0e98f23273d9 100644 --- a/clang/test/Analysis/Scalable/PointerFlow/external-inline-function-in-multi-tu.test +++ b/clang/test/Analysis/Scalable/PointerFlow/external-inline-function-in-multi-tu.test @@ -4,7 +4,7 @@ // during bounds propagation. -// DEFINE: %{extract} = %clang_cc1 -fsyntax-only -I %t --ssaf-extract-summaries=PointerFlow,UnsafeBufferUsage +// DEFINE: %{extract} = %clang_cc1 -fsyntax-only -I %t --ssaf-extract-summaries=PointerFlow,UnsafeBufferUsage,TypeConstrainedPointers // RUN: rm -rf %t // RUN: mkdir -p %t diff --git a/clang/test/Analysis/Scalable/PointerFlow/lref-to-rref-cast.test b/clang/test/Analysis/Scalable/PointerFlow/lref-to-rref-cast.test index ca5df041240aa..fdb57741864e3 100644 --- a/clang/test/Analysis/Scalable/PointerFlow/lref-to-rref-cast.test +++ b/clang/test/Analysis/Scalable/PointerFlow/lref-to-rref-cast.test @@ -6,7 +6,7 @@ // Extract per-TU PointerFlow + UnsafeBufferUsage summaries. // RUN: %clang_cc1 -fsyntax-only %t/tu.cpp \ -// RUN: --ssaf-extract-summaries=PointerFlow,UnsafeBufferUsage \ +// RUN: --ssaf-extract-summaries=PointerFlow,UnsafeBufferUsage,TypeConstrainedPointers \ // RUN: --ssaf-tu-summary-file=%t/tu.summary.json \ // RUN: --ssaf-compilation-unit-id="tu-1" diff --git a/clang/test/Analysis/Scalable/PointerFlow/multi-decl-contributor.cpp b/clang/test/Analysis/Scalable/PointerFlow/multi-decl-contributor.cpp index 717a2875636b2..2d27026708eca 100644 --- a/clang/test/Analysis/Scalable/PointerFlow/multi-decl-contributor.cpp +++ b/clang/test/Analysis/Scalable/PointerFlow/multi-decl-contributor.cpp @@ -2,7 +2,7 @@ // RUN: %clang_cc1 -fsyntax-only %s \ -// RUN: --ssaf-extract-summaries=PointerFlow,UnsafeBufferUsage \ +// RUN: --ssaf-extract-summaries=PointerFlow,UnsafeBufferUsage,TypeConstrainedPointers \ // RUN: --ssaf-tu-summary-file=%t/tu.summary.json \ // RUN: --ssaf-compilation-unit-id="tu-1" diff --git a/clang/test/Analysis/Scalable/PointerFlow/multi-dim-pointer-flow-constraint.test b/clang/test/Analysis/Scalable/PointerFlow/multi-dim-pointer-flow-constraint.test index 511b375c05f6c..d057f3e4c2ef9 100644 --- a/clang/test/Analysis/Scalable/PointerFlow/multi-dim-pointer-flow-constraint.test +++ b/clang/test/Analysis/Scalable/PointerFlow/multi-dim-pointer-flow-constraint.test @@ -6,7 +6,7 @@ // RUN: %clang_cc1 -fsyntax-only %t/src.cpp \ -// RUN: --ssaf-extract-summaries=PointerFlow,UnsafeBufferUsage \ +// RUN: --ssaf-extract-summaries=PointerFlow,UnsafeBufferUsage,TypeConstrainedPointers \ // RUN: --ssaf-compilation-unit-id="tu-1" \ // RUN: --ssaf-tu-summary-file=%t/src.summary.json diff --git a/clang/test/Analysis/Scalable/TypeConstrainedPointers/unsafe-buffer-reachable-excludes-type-constrained-main.cpp b/clang/test/Analysis/Scalable/TypeConstrainedPointers/unsafe-buffer-reachable-excludes-type-constrained-main.cpp new file mode 100644 index 0000000000000..f7ab07f517c03 --- /dev/null +++ b/clang/test/Analysis/Scalable/TypeConstrainedPointers/unsafe-buffer-reachable-excludes-type-constrained-main.cpp @@ -0,0 +1,40 @@ +// Test that UnsafeBufferReachableAnalysis excludes type-constrained pointers + +// RUN: rm -rf %t && mkdir -p %t + +// RUN: %clang_cc1 -fsyntax-only %s \ +// RUN: --ssaf-extract-summaries=PointerFlow,UnsafeBufferUsage,TypeConstrainedPointers \ +// RUN: --ssaf-tu-summary-file=%t/tu.summary.json \ +// RUN: --ssaf-compilation-unit-id="tu-1" + +// RUN: clang-ssaf-linker %t/tu.summary.json -o %t/lu.json + +// RUN: clang-ssaf-analyzer %t/lu.json -o %t/wpa.json \ +// RUN: -a UnsafeBufferReachableAnalysisResult + +// RUN: FileCheck %s --input-file=%t/wpa.json + + +int main(int argc, char **argv) { + argv[5] = 0; // unsafe use of a type-constrained pointer + return 0; +} + +// 'q' is an ordinary unsafe pointer parameter and must remain in the result. +void foo(int *q) { + q[5] = 0; +} + +// CHECK-DAG: "id": [[Q_ID:[0-9]+]],{{([^]]|[[:space:]])+\],[[:space:]]+"suffix": "1",[[:space:]]+"usr": }}"c:@F@foo#*I#" +// CHECK-DAG: "id": [[ARGV_ID:[0-9]+]],{{([^]]|[[:space:]])+\],[[:space:]]+"suffix": "2",[[:space:]]+"usr": }}"c:@F@main{{.*}}" + +// 'argv' is reported as type-constrained. +// CHECK: "analysis_name": "TypeConstrainedPointersAnalysisResult" +// CHECK: "@": [[ARGV_ID]] + +// In the reachable result 'q' is present but 'argv' is not. +// CHECK: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// CHECK-DAG: {{\{[[:space:]]+}}"@": [[Q_ID]]{{[[:space:]]+\},[[:space:]]+1[[:space:]]+\]}} +// CHECK-NOT: "@": [[ARGV_ID]] + +// CHECK: "analysis_name" diff --git a/clang/test/Analysis/Scalable/TypeConstrainedPointers/unsafe-buffer-reachable-excludes-type-constrained-new-delete.cpp b/clang/test/Analysis/Scalable/TypeConstrainedPointers/unsafe-buffer-reachable-excludes-type-constrained-new-delete.cpp new file mode 100644 index 0000000000000..c5a7a17bbf381 --- /dev/null +++ b/clang/test/Analysis/Scalable/TypeConstrainedPointers/unsafe-buffer-reachable-excludes-type-constrained-new-delete.cpp @@ -0,0 +1,74 @@ +// Test that UnsafeBufferReachableAnalysis excludes the +// type-constrained pointers of 'operator new' / 'operator delete' +// overloads. +// +// RUN: rm -rf %t && mkdir -p %t + +// RUN: %clang_cc1 -fsyntax-only %s \ +// RUN: --ssaf-extract-summaries=PointerFlow,UnsafeBufferUsage,TypeConstrainedPointers \ +// RUN: --ssaf-tu-summary-file=%t/tu.summary.json \ +// RUN: --ssaf-compilation-unit-id="tu-1" + +// RUN: clang-ssaf-linker %t/tu.summary.json -o %t/lu.json + +// RUN: clang-ssaf-analyzer %t/lu.json -o %t/wpa.json \ +// RUN: -a UnsafeBufferReachableAnalysisResult + +// RUN: FileCheck %s --input-file=%t/wpa.json + +typedef __SIZE_TYPE__ size_t; + +// Return value and the 2nd parameter are type-constrained: +void *operator new(size_t size, void *place) noexcept { + int *new_local = (int *)place; + + return new_local; +} + +// The parameter is type-constrained: +void operator delete(void *ptr) noexcept { + int *delete_local = (int *)ptr; + + delete_local[5] = 0; +} + +void foo(int *p) { + void *r = ::operator new(10, p); + int *q = (int *)r; + + // 'q' is unsafe, it propagates along the path + // 'q -> r -> return_new -> new_local -> place' + // All pointers along the path are rechable but return_new and place + // are type-constrained. + q[5] = 0; + ::operator delete(q); +} + + +// CHECK: "id_table" +// CHECK-DAG: "id": [[NEW_RET:[0-9]+]],{{([^]]|[[:space:]])+\],[[:space:]]+"suffix": "0",[[:space:]]+"usr": }}"c:@F@operator new#l#*v#" +// CHECK-DAG: "id": [[NEW_PLACE:[0-9]+]],{{([^]]|[[:space:]])+\],[[:space:]]+"suffix": "2",[[:space:]]+"usr": }}"c:@F@operator new#l#*v#" +// CHECK-DAG: "id": [[DEL_PTR:[0-9]+]],{{([^]]|[[:space:]])+\],[[:space:]]+"suffix": "1",[[:space:]]+"usr": }}"c:@F@operator delete#*v#" + +// CHECK-DAG: "id": [[FOO_Q:[0-9]+]],{{([^]]|[[:space:]])+\],[[:space:]]+"suffix": "",[[:space:]]+"usr": "[^"]+}}foo#*I#@q" +// CHECK-DAG: "id": [[FOO_R:[0-9]+]],{{([^]]|[[:space:]])+\],[[:space:]]+"suffix": "",[[:space:]]+"usr": "[^"]+}}foo#*I#@r" +// CHECK-DAG: "id": [[NEW_LOCAL:[0-9]+]],{{([^]]|[[:space:]])+\],[[:space:]]+"suffix": "",[[:space:]]+"usr": "[^"]+}}operator new#l#*v#@new_local" +// CHECK-DAG: "id": [[DELETE_LOCAL:[0-9]+]],{{([^]]|[[:space:]])+\],[[:space:]]+"suffix": "",[[:space:]]+"usr": "[^"]+}}operator delete#*v#@delete_local" + +// The return and every new/delete parameter are reported as type-constrained. +// CHECK: "analysis_name": "TypeConstrainedPointersAnalysisResult" +// CHECK-DAG: "@": [[NEW_RET]] +// CHECK-DAG: "@": [[NEW_PLACE]] +// CHECK-DAG: "@": [[DEL_PTR]] + +// CHECK: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// CHECK-DAG: {{\{[[:space:]]+}}"@": [[FOO_Q]]{{[[:space:]]+\},[[:space:]]+1[[:space:]]+\]}} +// CHECK-DAG: {{\{[[:space:]]+}}"@": [[FOO_R]]{{[[:space:]]+\},[[:space:]]+1[[:space:]]+\]}} +// CHECK-DAG: {{\{[[:space:]]+}}"@": [[NEW_LOCAL]]{{[[:space:]]+\},[[:space:]]+1[[:space:]]+\]}} +// CHECK-DAG: {{\{[[:space:]]+}}"@": [[DELETE_LOCAL]]{{[[:space:]]+\},[[:space:]]+1[[:space:]]+\]}} + +// CHECK-NOT: {{"@": }}[[NEW_RET]]{{[[:space:]]}} +// CHECK-NOT: {{"@": }}[[NEW_PLACE]]{{[[:space:]]}} +// CHECK-NOT: {{"@": }}[[DEL_PTR]]{{[[:space:]]}} + +// CHECK: "analysis_name" diff --git a/clang/test/Analysis/Scalable/ssaf-analyzer/Outputs/empty-pairs.json b/clang/test/Analysis/Scalable/ssaf-analyzer/Outputs/empty-pairs.json new file mode 100644 index 0000000000000..2e59f60b3a3a6 --- /dev/null +++ b/clang/test/Analysis/Scalable/ssaf-analyzer/Outputs/empty-pairs.json @@ -0,0 +1,26 @@ +{ + "id_table": [ + { + "id": 0, + "name": { + "namespace": [ + { + "kind": "LinkUnit", + "name": "test.exe" + } + ], + "suffix": "", + "usr": "c:@F@foo#" + } + } + ], + "results": [ + { + "analysis_name": "PairsAnalysisResult", + "result": { + "pair_counts": [] + } + } + ], + "type": "WPASuite" +} diff --git a/clang/test/Analysis/Scalable/ssaf-analyzer/analyzer.test b/clang/test/Analysis/Scalable/ssaf-analyzer/analyzer.test index 0abdcef15a449..f76b2b78b52f4 100644 --- a/clang/test/Analysis/Scalable/ssaf-analyzer/analyzer.test +++ b/clang/test/Analysis/Scalable/ssaf-analyzer/analyzer.test @@ -15,13 +15,13 @@ // UNKNOWN: no analysis registered for 'AnalysisName(NoSuchAnalysis)' // ============================================================================ -// Error: valid analysis name but LUSummary lacks entity data for it +// Success: valid analysis name but LUSummary lacks entity data for it yields an +// empty result (missing data is not an error) // ============================================================================ -// RUN: not %clang-ssaf-analyzer-with-plugin %S/Inputs/lu-tags-only.json \ -// RUN: -o %t/missing-data.json -a PairsAnalysisResult 2>&1 \ -// RUN: | FileCheck %s --check-prefix=MISSING-DATA -// MISSING-DATA: no data for analysis 'AnalysisName(PairsAnalysisResult)' in LUSummary +// RUN: %clang-ssaf-analyzer-with-plugin %S/Inputs/lu-tags-only.json \ +// RUN: -o %t/empty-pairs.json -a PairsAnalysisResult +// RUN: diff %S/Outputs/empty-pairs.json %t/empty-pairs.json // ============================================================================ // Success: run TagsAnalysisResult only (single analysis) `````````` </details> https://github.com/llvm/llvm-project/pull/209354 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
