Author: Ziqing Luo Date: 2026-08-15T18:04:10-07:00 New Revision: cbb56261423435e4e3d6dadca89ddb95be5bd977
URL: https://github.com/llvm/llvm-project/commit/cbb56261423435e4e3d6dadca89ddb95be5bd977 DIFF: https://github.com/llvm/llvm-project/commit/cbb56261423435e4e3d6dadca89ddb95be5bd977.diff LOG: [SSAF][UnsafeBufferAnalysis] Filter out type-constrained pointers from reachable unsafe pointers (#209354) Integrate the TypeConstrainedPointers analysis results into UnsafeBufferReachableAnalysis. The final result is filtered to exclude type-constrained pointers. The pointer flow graph is untouched. Removing type-constrained pointers from the graph would introduce unsoundness. Final step for rdar://179151541 and rdar://179151882 Added: clang/test/Analysis/Scalable/TypeConstrainedPointers/unsafe-buffer-reachable-excludes-type-constrained-main.cpp clang/test/Analysis/Scalable/TypeConstrainedPointers/unsafe-buffer-reachable-excludes-type-constrained-new-delete.cpp clang/test/Analysis/Scalable/ssaf-analyzer/Outputs/empty-pairs.json Modified: clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp clang/test/Analysis/Scalable/PointerFlow/external-inline-function-in-multi-tu.test clang/test/Analysis/Scalable/PointerFlow/lref-to-rref-cast.test clang/test/Analysis/Scalable/PointerFlow/multi-decl-contributor.cpp clang/test/Analysis/Scalable/PointerFlow/multi-dim-pointer-flow-constraint.test Removed: ################################################################################ diff --git a/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp b/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp index e404eb294ee4b..664eba23f3bb0 100644 --- a/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp +++ b/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp @@ -15,11 +15,16 @@ #include "SSAFAnalysesCommon.h" #include "clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.h" #include "clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevelFormat.h" +#include "clang/ScalableStaticAnalysis/Analyses/PointerFlow/PointerFlow.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" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Support/Error.h" #include "llvm/Support/JSON.h" #include <memory> @@ -124,12 +129,20 @@ 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 (Constrained):** Type-constrained entities are NOT unsafe. class UnsafeBufferReachableAnalysis : public DerivedAnalysis<UnsafeBufferReachableAnalysisResult, PointerFlowAnalysisResult, + TypeConstrainedPointersAnalysisResult, UnsafeBufferUsageAnalysisResult> { /// BoundsPropagationGraph adds bounds propagation semantics to the @@ -159,11 +172,11 @@ class UnsafeBufferReachableAnalysis /// bound based on the maximum pointer level the pointer type can have. struct BoundsPropagationGraph { private: - const std::map<EntityPointerLevel, EntityPointerLevelSet> &PointerFlows; + EdgeSet PointerFlows; public: - BoundsPropagationGraph(const EdgeSet &PointerFlows) - : PointerFlows(PointerFlows) {} + BoundsPropagationGraph(EdgeSet PointerFlows) + : PointerFlows(std::move(PointerFlows)) {} /// Returns the EntityPointerLevelSet that are reachable from \p Src by /// one edge in the BoundsPropagationGraph. @@ -207,18 +220,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 +237,52 @@ class UnsafeBufferReachableAnalysis updateReachablesWithOutgoings(Node, Worklist); } + } + +public: + llvm::Error + initialize(const PointerFlowAnalysisResult &PtrFlowGraph, + const TypeConstrainedPointersAnalysisResult &TypeConstraints, + const UnsafeBufferUsageAnalysisResult &UnsafePtrs) override { + auto HasNoTypeConstraint = + [&TypeConstraints](const EntityPointerLevel &EPL) { + return !TypeConstraints.contains(EPL.getEntity()); + }; + + // Filter out edges involving type-constrained pointers from `PtrFlowGraph`: + for (auto &[Id, SubGraph] : PtrFlowGraph.Edges) { + EdgeSet FilteredSubGraph; + + for (const auto &[Src, Dsts] : SubGraph) { + if (TypeConstraints.contains(Src.getEntity())) + continue; + + auto FilteredDstRange = + llvm::make_filter_range(Dsts, HasNoTypeConstraint); + + if (!FilteredDstRange.empty()) + FilteredSubGraph[Src].insert(FilteredDstRange.begin(), + FilteredDstRange.end()); + } + if (!FilteredSubGraph.empty()) + BPG.try_emplace(Id, std::move(FilteredSubGraph)); + } + + // Filter out type-constrained pointers from `UnsafePtrs`: + for (auto &[Contributor, EPLs] : UnsafePtrs) { + auto FilteredRange = llvm::make_filter_range(EPLs, HasNoTypeConstraint); + + getResult().Reachables[Contributor].insert(FilteredRange.begin(), + FilteredRange.end()); + } + return llvm::Error::success(); + } + + llvm::Expected<bool> step() override { + // Compute the reachable EPLs from the C1 unsafe pointers over the + // pointer-flow graph; both are already C3-filtered, so the result + // satisfies C1, C2, and C3. + computeReachableUnsafePointers(); // This is not an iterative algorithm so stop iteration by retruning false: return false; } 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..95eff21fbb0e5 --- /dev/null +++ b/clang/test/Analysis/Scalable/TypeConstrainedPointers/unsafe-buffer-reachable-excludes-type-constrained-main.cpp @@ -0,0 +1,60 @@ +// 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 + +// The CHECK lines below use readable tokens instead of inline FileCheck regex. +// Expand the tokens into regex, then run FileCheck on the expanded copy: +// $NS - skip the "namespace" array, up to its closing ']'. +// $WS - whitespace, possibly spanning newlines. +// $PTR_L1 - a reachable-set entry closing as "}, 1 ]", i.e. pointer level 1. +// RUN: sed -e 's|$NS|{{([^]]\|[[:space:]])+\\],}}|g' \ +// RUN: -e 's|$WS|{{[[:space:]]+}}|g' \ +// RUN: -e 's|$PTR_L1|{{[[:space:]]+\\},[[:space:]]+1[[:space:]]+\\]}}|g' \ +// RUN: %s > %t/checks.txt +// RUN: FileCheck %t/checks.txt --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]+]],$NS$WS"suffix": "1",$WS"usr": "c:@F@foo#*I#" +// CHECK-DAG: "id": [[ARGV_ID:[0-9]+]],$NS$WS"suffix": "2",$WS"usr": "c:@F@main{{.*}}" + +// Contributor function ids: +// CHECK-DAG: "id": [[CONTRIBUTOR_FOO:[0-9]+]],$NS$WS"suffix": "",$WS"usr": "c:@F@foo#*I#" +// CHECK-DAG: "id": [[CONTRIBUTOR_MAIN:[0-9]+]],$NS$WS"suffix": "",$WS"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" + +// 'foo' contributes unsafe pointer 'q'. +// CHECK: "@": [[CONTRIBUTOR_FOO]]$WS},$WS[ +// CHECK: "@": [[Q_ID]]$PTR_L1 +// CHECK-NOT: "@": + +// 'main' contributes nothing: 'argv' is type-constrained and excluded. +// CHECK: "@": [[CONTRIBUTOR_MAIN]]$WS},$WS[ +// 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..798b714e14af2 --- /dev/null +++ b/clang/test/Analysis/Scalable/TypeConstrainedPointers/unsafe-buffer-reachable-excludes-type-constrained-new-delete.cpp @@ -0,0 +1,112 @@ +// 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 + +// The CHECK lines below use readable tokens instead of inline FileCheck regex. +// Expand the tokens into regex, then run FileCheck on the expanded copy: +// $NS - skip the "namespace" array, up to its closing ']'. +// $WS - whitespace, possibly spanning newlines. +// $PTR_L1 - a reachable-set entry closing as "}, 1 ]", i.e. pointer level 1. +// RUN: sed -e 's|$NS|{{([^]]\|[[:space:]])+\\],}}|g' \ +// RUN: -e 's|$WS|{{[[:space:]]+}}|g' \ +// RUN: -e 's|$PTR_L1|{{[[:space:]]+\\},[[:space:]]+1[[:space:]]+\\]}}|g' \ +// RUN: %s > %t/checks.txt +// RUN: FileCheck %t/checks.txt --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 and the original propagation path is + // 'q -> r -> return_new -> new_local -> place'. However, since 'return_new' + // (also 'place') is type-constrained, it is removed from the graph, resulting + // in no path from 'q' to 'new_local'. + q[5] = 0; + ::operator delete(q); +} + +void bar() { + char * x, *y; + + // 'x' cannot be reached from an unsafe pointer because the + // parameter of 'delete' is type-constrained: + ::operator delete(x); + y[5] = 5; +} + +// Save entity IDs in variables: +// CHECK: "id_table" +// CHECK-DAG: "id": [[NEW_RET:[0-9]+]],$NS$WS"suffix": "0",$WS"usr": "c:@F@operator new#{{[^#]+}}#*v#" +// CHECK-DAG: "id": [[NEW_PLACE:[0-9]+]],$NS$WS"suffix": "2",$WS"usr": "c:@F@operator new#{{[^#]+}}#*v#" +// CHECK-DAG: "id": [[DEL_PTR:[0-9]+]],$NS$WS"suffix": "1",$WS"usr": "c:@F@operator delete#*v#" + +// CHECK-DAG: "id": [[FOO_Q:[0-9]+]],$NS$WS"suffix": "",$WS"usr": "{{[^"]+}}foo#*I#@q" +// CHECK-DAG: "id": [[FOO_R:[0-9]+]],$NS$WS"suffix": "",$WS"usr": "{{[^"]+}}foo#*I#@r" +// CHECK-DAG: "id": [[NEW_LOCAL:[0-9]+]],$NS$WS"suffix": "",$WS"usr": "{{[^"]+}}operator new#{{[^#]+}}#*v#@new_local" +// CHECK-DAG: "id": [[DELETE_LOCAL:[0-9]+]],$NS$WS"suffix": "",$WS"usr": "{{[^"]+}}operator delete#*v#@delete_local" +// CHECK-DAG: "id": [[BAR_Y:[0-9]+]],$NS$WS"suffix": "",$WS"usr": "{{[^"]+}}bar#@y" +// CHECK-DAG: "id": [[BAR_X:[0-9]+]],$NS$WS"suffix": "",$WS"usr": "{{[^"]+}}bar#@x" + +// Contributor function ids: +// CHECK-DAG: "id": [[CONTRIBUTOR_BAR:[0-9]+]],$NS$WS"suffix": "",$WS"usr": "c:@F@bar#" +// CHECK-DAG: "id": [[CONTRIBUTOR_FOO:[0-9]+]],$NS$WS"suffix": "",$WS"usr": "c:@F@foo#*I#" +// CHECK-DAG: "id": [[CONTRIBUTOR_DELETE:[0-9]+]],$NS$WS"suffix": "",$WS"usr": "c:@F@operator delete#*v#" + +// 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" + +// 'bar' contributes unsafe pointer 'y' but not 'x': +// CHECK: "@": [[CONTRIBUTOR_BAR]]$WS},$WS[ +// CHECK: "@": [[BAR_Y]]$PTR_L1 +// CHECK-NOT: "@": [[BAR_X]]$PTR_L1 + +// 'foo' contributes unsafe pointers 'q' and 'r': +// CHECK: "@": [[CONTRIBUTOR_FOO]]$WS},$WS[ +// CHECK-DAG: "@": [[FOO_Q]]$PTR_L1 +// CHECK-DAG: "@": [[FOO_R]]$PTR_L1 +// CHECK-NOT: "@": + +// 'operator delete' contributes unsafe pointer 'delete_local': +// CHECK: "@": [[CONTRIBUTOR_DELETE]]$WS},$WS[ +// CHECK-DAG: "@": [[DELETE_LOCAL]]$PTR_L1 + +// The type-constrained pointers never appear in the reachable result: +// CHECK-NOT: "@": [[NEW_RET]]$WS +// CHECK-NOT: "@": [[NEW_PLACE]]$WS +// CHECK-NOT: "@": [[DEL_PTR]]$WS +// CHECK-NOT: "@": [[NEW_LOCAL]]$WS + +// 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" +} _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
