Author: Ziqing Luo Date: 2026-08-29T18:43:26-07:00 New Revision: b3a2fa281ee7b3ff3bc3ad69b761412aab563fe5
URL: https://github.com/llvm/llvm-project/commit/b3a2fa281ee7b3ff3bc3ad69b761412aab563fe5 DIFF: https://github.com/llvm/llvm-project/commit/b3a2fa281ee7b3ff3bc3ad69b761412aab563fe5.diff LOG: [SSAF][PointerFlow] Change unsafe-buffer reachability analysis back to simple graph search (#218209) Because of #218207, we no longer need unsafe-buffer reachability analysis to "uncompress" pointer flow graphs. It can go back to simple DFS. Since it deals with large data, simplicity is important. In addition, unit tests for the "compressed" pointer flow graph DFS are moved to lit tests because they are no longer suitable as WPA unit tests. As lit tests, they are end-to-end tests where the extractor is involved and is responsible for generating "uncompressed" graphs. Final step of rdar://183529483 Added: clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-cast-cycle.test Modified: clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp clang/unittests/ScalableStaticAnalysis/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp Removed: ################################################################################ diff --git a/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp b/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp index 4c92a37a078d1..4fc6d058de368 100644 --- a/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp +++ b/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp @@ -145,56 +145,16 @@ class UnsafeBufferReachableAnalysis TypeConstrainedPointersAnalysisResult, UnsafeBufferUsageAnalysisResult> { - /// BoundsPropagationGraph adds bounds propagation semantics to the - /// pointer-flow graph, which represents the set of static pointer assignment - /// sites collected from the source code. Consider the following example: - /// - /// void f(int ***p, int **q) { - /// *p = q; - /// (**p)[5] = 0; - /// } - /// - /// There is one static pointer assignment thus one pointer-flow edge: (p, 2) - /// -> (q, 1). In terms of bounds propagation, this assignment implies that if - /// 'p' at pointer level 2 requires bounds, 'q' at pointer level 1 must also - /// have them. Furthermore, this relationship propagates to deeper indirection - /// levels: if 'p' at level 3 requires bounds, so does 'q' at level 2. - /// - /// In the example above, `(**p)` requires bounds (due to the array index), - /// and therefore `*q` must require bounds as well. - /// - /// To generalize the idea, the BoundsPropagationGraph is defined as a super - /// graph of the input pointer-flow graph by: - /// - /// For each edge (src, i) -> (dest, j) in the pointer-flow graph, the - /// BoundsPropagationGraph has a finite set of edges - /// {(src, i + d) -> (dest, j + d) | 0 <= d < UB}, where UB is an upper - /// bound based on the maximum pointer level the pointer type can have. struct BoundsPropagationGraph { - private: EdgeSet PointerFlows; - public: - BoundsPropagationGraph(EdgeSet PointerFlows) - : PointerFlows(std::move(PointerFlows)) {} - /// Returns the EntityPointerLevelSet that are reachable from \p Src by /// one edge in the BoundsPropagationGraph. EntityPointerLevelSet getDestNodes(const EntityPointerLevel &Src) const { - unsigned SrcPtrLv = Src.getPointerLevel(); - EntityPointerLevelSet Result; - - for (unsigned P = 1; P <= SrcPtrLv; ++P) { - auto I = PointerFlows.find(buildEntityPointerLevel(Src.getEntity(), P)); - - if (I != PointerFlows.end()) { - unsigned Delta = SrcPtrLv - P; - for (const auto &EPL : I->second) - Result.insert(buildEntityPointerLevel( - EPL.getEntity(), EPL.getPointerLevel() + Delta)); - } - } - return Result; + auto I = PointerFlows.find(Src); + if (I == PointerFlows.end()) + return {}; + return I->second; } }; @@ -265,7 +225,8 @@ class UnsafeBufferReachableAnalysis FilteredDstRange.end()); } if (!FilteredSubGraph.empty()) - BPG.try_emplace(Id, std::move(FilteredSubGraph)); + BPG.try_emplace(Id, + BoundsPropagationGraph{std::move(FilteredSubGraph)}); } // Filter out type-constrained pointers from `UnsafePtrs`: diff --git a/clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-cast-cycle.test b/clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-cast-cycle.test new file mode 100644 index 0000000000000..f64c043f855a9 --- /dev/null +++ b/clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-cast-cycle.test @@ -0,0 +1,52 @@ +// Regression test: UnsafeBufferReachableAnalysis used to hang on +// +// void f(char **a, char ***b, int i, int j) { +// a[i][j] = 0; // 'a' is unsafe at levels 1 and 2 +// a = *b; // (a, 1) -> (b, 2) +// b = (char ***)*a; // (b, 1) -> (a, 2) +// } +// +// RUN: rm -rf %t && mkdir -p %t +// RUN: split-file %s %t + +// RUN: %clang_cc1 -fsyntax-only %t/src.cpp \ +// RUN: --ssaf-extract-summaries=PointerFlow,UnsafeBufferUsage,TypeConstrainedPointers \ +// RUN: --ssaf-compilation-unit-id="tu-1" \ +// RUN: --ssaf-tu-summary-file=%t/src.summary.json + +// RUN: clang-ssaf-linker %t/src.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_Ln - a reachable-set entry closing as "}, n ]", i.e. pointer level n. +// RUN: sed -e 's|$NS|{{([^]]\|[[:space:]])+\\],}}|g' \ +// RUN: -e 's|$WS|{{[[:space:]]+}}|g' \ +// RUN: -e 's|$PTR_L1|{{[[:space:]]+\\},[[:space:]]+1[[:space:]]+\\]}}|g' \ +// RUN: -e 's|$PTR_L2|{{[[:space:]]+\\},[[:space:]]+2[[:space:]]+\\]}}|g' \ +// RUN: -e 's|$PTR_L3|{{[[:space:]]+\\},[[:space:]]+3[[:space:]]+\\]}}|g' \ +// RUN: %s | FileCheck - --input-file=%t/wpa.json + +//--- src.cpp +void f(char **a, char ***b, int i, int j) { + a[i][j] = 0; // 'a' is unsafe at levels 1 and 2 + a = *b; // (a, 1) -> (b, 2) + b = (char ***)*a; // (b, 1) -> (a, 2) +} + +// Capture the entity ids for parameters 'a' (suffix "1") and 'b' (suffix "2"). +// CHECK-DAG: "id": [[a_ID:[0-9]+]],$NS$WS"suffix": "1",$WS"usr": "c:@F@f#**C#*S0_#I#I#" +// CHECK-DAG: "id": [[b_ID:[0-9]+]],$NS$WS"suffix": "2",$WS"usr": "c:@F@f#**C#*S0_#I#I#" + +// The reachable set is exactly {(a, 1), (a, 2), (b, 2), (b, 3)} +// CHECK: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// CHECK: "@": [[a_ID]]$PTR_L1 +// CHECK: "@": [[a_ID]]$PTR_L2 +// CHECK: "@": [[b_ID]]$PTR_L2 +// CHECK: "@": [[b_ID]]$PTR_L3 +// CHECK-NOT: "@": +// CHECK: "analysis_name": diff --git a/clang/unittests/ScalableStaticAnalysis/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp b/clang/unittests/ScalableStaticAnalysis/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp index cf5420b35e7dc..b057b6b1ed5bf 100644 --- a/clang/unittests/ScalableStaticAnalysis/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp +++ b/clang/unittests/ScalableStaticAnalysis/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp @@ -6,24 +6,43 @@ // //===----------------------------------------------------------------------===// +#include "../FindDecl.h" #include "../TestFixture.h" +#include "clang/Frontend/ASTUnit.h" +#include "clang/Frontend/SSAFOptions.h" #include "clang/ScalableStaticAnalysis/Analyses/EntityPointerLevel/EntityPointerLevel.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/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.h" +#include "clang/ScalableStaticAnalysis/Core/ASTEntityMapping.h" +#include "clang/ScalableStaticAnalysis/Core/EntityLinker/EntityLinker.h" #include "clang/ScalableStaticAnalysis/Core/EntityLinker/LUSummary.h" +#include "clang/ScalableStaticAnalysis/Core/EntityLinker/LUSummaryEncoding.h" +#include "clang/ScalableStaticAnalysis/Core/EntityLinker/TUSummaryEncoding.h" #include "clang/ScalableStaticAnalysis/Core/Model/BuildNamespace.h" #include "clang/ScalableStaticAnalysis/Core/Model/EntityId.h" #include "clang/ScalableStaticAnalysis/Core/Model/EntityLinkage.h" #include "clang/ScalableStaticAnalysis/Core/Model/EntityName.h" +#include "clang/ScalableStaticAnalysis/Core/Serialization/JSONFormat.h" +#include "clang/ScalableStaticAnalysis/Core/TUSummary/ExtractorRegistry.h" +#include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummary.h" +#include "clang/ScalableStaticAnalysis/Core/TUSummary/TUSummaryBuilder.h" #include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/AnalysisDriver.h" #include "clang/ScalableStaticAnalysis/Core/WholeProgramAnalysis/WPASuite.h" +#include "clang/Tooling/Tooling.h" #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/ScopeExit.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/Path.h" +#include "llvm/Testing/Support/Error.h" #include "gtest/gtest.h" #include <map> #include <memory> #include <optional> +#include <set> +#include <string> using namespace clang; using namespace ssaf; @@ -205,31 +224,6 @@ TEST_F(UnsafeBufferReachableAnalysisTest, LinearChain) { EXPECT_EQ(Reachables.size(), 4u); } -// Linear chain: (a,1) -> (b,2), (b,1) -> (c,2), (c,1) -> (d,2). -// Start from {(a,2)} => {(a,2), (b,3), (c,4), (d,5)} -TEST_F(UnsafeBufferReachableAnalysisTest, LinearChain2) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ - {{{'a', 1}, {'b', 2}}, {{'b', 1}, {'c', 2}}, {{'c', 1}, {'d', 2}}}, - /* StarterLayout */ {{'a', 2}}, __LINE__); - EXPECT_EQ(Reachables.size(), 4u); - EXPECT_EQ(Reachables, - (std::set<Node>{{'a', 2}, {'b', 3}, {'c', 4}, {'d', 5}})); -} - -// Linear chain: (a,1) -> (b,2), (b,4) -> (c,1) -> (d,1). -// Start from {(a,2)} => {(a,2), (b,3)} (halted at (b,3) — no key (b,j<=3)) -TEST_F(UnsafeBufferReachableAnalysisTest, LinearChain3) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ - {{{'a', 1}, {'b', 2}}, {{'b', 4}, {'c', 1}}, {{'c', 1}, {'d', 1}}}, - /* StarterLayout */ {{'a', 2}}, __LINE__); - EXPECT_EQ(Reachables.size(), 2u); - EXPECT_EQ(Reachables, (std::set<Node>{{'a', 2}, {'b', 3}})); -} - // Linear chain: (a,1) -> (b,1) -> (c,1) -> (d,1). // Start from mid-chain {(c,1)} => {(c,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, LinearChainFromMiddle) { @@ -257,35 +251,6 @@ TEST_F(UnsafeBufferReachableAnalysisTest, Diamond) { EXPECT_EQ(Reachables.size(), 4u); } -// Diamond: (a,1) -> (b,2), (a,1) -> (c,2), (b,1) -> (d,2), (c,1) -> (d,2). -// Start from {(a,2)} => {(a,2), (b,3), (c,3), (d,4)} -TEST_F(UnsafeBufferReachableAnalysisTest, Diamond2) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ - {{{'a', 1}, {'b', 2}}, - {{'a', 1}, {'c', 2}}, - {{'b', 1}, {'d', 2}}, - {{'c', 1}, {'d', 2}}}, - /* StarterLayout */ {{'a', 2}}, __LINE__); - EXPECT_EQ(Reachables, - (std::set<Node>{{'a', 2}, {'b', 3}, {'c', 3}, {'d', 4}})); -} - -// DisconnectedDiamond: (a,1) -> (b,2), (a,1) -> (c,2), (b,5) -> (d,1), (c,5) -> -// (d,1). Start from {(a,2)} => {(a,2), (b,3), (c,3)} -TEST_F(UnsafeBufferReachableAnalysisTest, DisconnectedDiamond) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ - {{{'a', 1}, {'b', 2}}, - {{'a', 1}, {'c', 2}}, - {{'b', 5}, {'d', 1}}, - {{'c', 5}, {'d', 1}}}, - /* StarterLayout */ {{'a', 2}}, __LINE__); - EXPECT_EQ(Reachables, (std::set<Node>{{'a', 2}, {'b', 3}, {'c', 3}})); -} - // Diamond: (a,1) -> (b,1), (a,1) -> (c,1), (b,1) -> (d,1), (c,1) -> (d,1). // Start from one branch {(b,1)} => {(b,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, DiamondFromBranch) { @@ -314,17 +279,6 @@ TEST_F(UnsafeBufferReachableAnalysisTest, DisconnectedSubgraphs) { EXPECT_TRUE(Reachables.count({'b', 1})); } -// Disconnected subgraphs: (a,1) -> (b,1), (c,1) -> (d,1). -// Start from tail {(b,1)} => {(b,1)} -TEST_F(UnsafeBufferReachableAnalysisTest, DisconnectedSubgraphs2) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ {{{'a', 1}, {'b', 1}}, {{'c', 1}, {'d', 1}}}, - /* StarterLayout */ {{'b', 1}}, __LINE__); - EXPECT_EQ(Reachables.size(), 1u); - EXPECT_TRUE(Reachables.count({'b', 1})); -} - // Cycle: (a,1) -> (b,1) -> (c,1) -> (d,1) -> (a,1). // Start from {(c,1)} => {(a,1), (b,1), (c,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, Cycle) { @@ -343,36 +297,6 @@ TEST_F(UnsafeBufferReachableAnalysisTest, Cycle) { EXPECT_TRUE(Reachables.count({'d', 1})); } -// Cycle: (a,1) -> (b,1) -> (c,1) -> (d,1) -> (a,1). -// Start from {(c,2)} => {(a,2), (b,2), (c,2), (d,2)} -TEST_F(UnsafeBufferReachableAnalysisTest, Cycle2) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ - {{{'a', 1}, {'b', 1}}, - {{'b', 1}, {'c', 1}}, - {{'c', 1}, {'d', 1}}, - {{'d', 1}, {'a', 1}}}, - /* StarterLayout */ {{'c', 2}}, __LINE__); - EXPECT_EQ(Reachables, - (std::set<Node>{{'a', 2}, {'b', 2}, {'c', 2}, {'d', 2}})); -} - -// Cycle: (a,1) -> (b,2) -> (c,3) -> (d,4) -> (a,1). -// Start from {(a,2)} => {(a,2), (b,3), (c,4), (d,5)} -TEST_F(UnsafeBufferReachableAnalysisTest, Cycle3) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ - {{{'a', 1}, {'b', 2}}, - {{'b', 2}, {'c', 3}}, - {{'c', 3}, {'d', 4}}, - {{'d', 4}, {'a', 1}}}, - /* StarterLayout */ {{'a', 2}}, __LINE__); - EXPECT_EQ(Reachables, - (std::set<Node>{{'a', 2}, {'b', 3}, {'c', 4}, {'d', 5}})); -} - // Empty graph: no edges, start from {(a,1)} => {(a,1)} TEST_F(UnsafeBufferReachableAnalysisTest, EmptyGraph) { auto Reachables = singlePartition( @@ -394,29 +318,6 @@ TEST_F(UnsafeBufferReachableAnalysisTest, StarFromHub) { EXPECT_EQ(Reachables.size(), 4u); } -// Star: (a,1) -> (b,2), (a,1) -> (c,2), (a,1) -> (d,2). -// Start from {(a,2)} => {(a,2), (b,3), (c,3), (d,3)} -TEST_F(UnsafeBufferReachableAnalysisTest, StarFromHub2) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ - {{{'a', 1}, {'b', 2}}, {{'a', 1}, {'c', 2}}, {{'a', 1}, {'d', 2}}}, - /* StarterLayout */ {{'a', 2}}, __LINE__); - EXPECT_EQ(Reachables, - (std::set<Node>{{'a', 2}, {'b', 3}, {'c', 3}, {'d', 3}})); -} - -// Star: (a,2) -> (b,1), (a,2) -> (c,1), (a,2) -> (d,1). -// Start from {(a,1)} => {(a,1)} -TEST_F(UnsafeBufferReachableAnalysisTest, StarFromHub3) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ - {{{'a', 2}, {'b', 1}}, {{'a', 2}, {'c', 1}}, {{'a', 2}, {'d', 1}}}, - /* StarterLayout */ {{'a', 1}}, __LINE__); - EXPECT_EQ(Reachables, (std::set<Node>{{'a', 1}})); -} - // Star: (a,1) -> (b,1), (a,1) -> (c,1), (a,1) -> (d,1). // Start from leaf {(c,1)} => {(c,1)} TEST_F(UnsafeBufferReachableAnalysisTest, StarFromLeaf) { @@ -442,17 +343,6 @@ TEST_F(UnsafeBufferReachableAnalysisTest, ReverseStarFromSource) { EXPECT_TRUE(Reachables.count({'d', 1})); } -// Reverse star: (a,1) -> (d,2), (b,1) -> (d,2), (c,1) -> (d,2). -// Start from {(a,2)} => {(a,2), (d,3)} -TEST_F(UnsafeBufferReachableAnalysisTest, ReverseStarFromSource2) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ - {{{'a', 1}, {'d', 2}}, {{'b', 1}, {'d', 2}}, {{'c', 1}, {'d', 2}}}, - /* StarterLayout */ {{'a', 2}}, __LINE__); - EXPECT_EQ(Reachables, (std::set<Node>{{'a', 2}, {'d', 3}})); -} - // Reverse star: (a,1) -> (d,1), (b,1) -> (d,1), (c,1) -> (d,1). // Start from sink {(d,1)} => {(d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, ReverseStarFromSink) { @@ -465,17 +355,6 @@ TEST_F(UnsafeBufferReachableAnalysisTest, ReverseStarFromSink) { EXPECT_TRUE(Reachables.count({'d', 1})); } -// Reverse star: (a,1) -> (d,1), (b,1) -> (d,1), (c,1) -> (d,1). -// Start from sink {(d,2)} => {(d,2)} -TEST_F(UnsafeBufferReachableAnalysisTest, ReverseStarFromSink2) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ - {{{'a', 1}, {'d', 1}}, {{'b', 1}, {'d', 1}}, {{'c', 1}, {'d', 1}}}, - /* StarterLayout */ {{'d', 2}}, __LINE__); - EXPECT_EQ(Reachables, (std::set<Node>{{'d', 2}})); -} - // Self-loop: (a,1) -> (b,1) -> (b,1) -> (c,1) -> (d,1). // Start from {(a,1)} => {(a,1), (b,1), (c,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromRoot) { @@ -490,21 +369,6 @@ TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromRoot) { EXPECT_EQ(Reachables.size(), 4u); } -// Self-loop: (a,1) -> (b,1) -> (b,1) -> (c,2) -> (d,2). -// Start from {(a,2)} => {(a,2), (b,2), (c,3), (d,4)} -TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromRoot2) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ - {{{'a', 1}, {'b', 1}}, - {{'b', 1}, {'b', 1}}, - {{'b', 1}, {'c', 2}}, - {{'c', 1}, {'d', 2}}}, - /* StarterLayout */ {{'a', 2}}, __LINE__); - EXPECT_EQ(Reachables, - (std::set<Node>{{'a', 2}, {'b', 2}, {'c', 3}, {'d', 4}})); -} - // Self-loop: (a,1) -> (b,1) -> (b,1) -> (c,1) -> (d,1). // Start from {(b,1)} => {(b,1), (c,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromLoopNode) { @@ -522,20 +386,6 @@ TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromLoopNode) { EXPECT_TRUE(Reachables.count({'d', 1})); } -// Self-loop: (a,1) -> (b,1) -> (b,1) -> (c,2) -> (d,2). -// Start from {(b,2)} => {(b,2), (c,3), (d,4)} -TEST_F(UnsafeBufferReachableAnalysisTest, SelfLoopFromLoopNode2) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ - {{{'a', 1}, {'b', 1}}, - {{'b', 1}, {'b', 1}}, - {{'b', 1}, {'c', 2}}, - {{'c', 1}, {'d', 2}}}, - /* StarterLayout */ {{'b', 2}}, __LINE__); - EXPECT_EQ(Reachables, (std::set<Node>{{'b', 2}, {'c', 3}, {'d', 4}})); -} - // Multiple starters: (a,1) -> (b,1), (c,1) -> (d,1) (disconnected). // Start from {(a,1), (c,1)} => {(a,1), (b,1), (c,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, MultipleStartersBothChains) { @@ -546,17 +396,6 @@ TEST_F(UnsafeBufferReachableAnalysisTest, MultipleStartersBothChains) { EXPECT_EQ(Reachables.size(), 4u); } -// Multiple starters: (a,1) -> (b,2), (c,1) -> (d,2). -// Start from {(a,2), (c,2)} => {(a,2), (b,3), (c,2), (d,3)} -TEST_F(UnsafeBufferReachableAnalysisTest, MultipleStartersBothChains2) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c', 'd'}, - /* EdgeLayout */ {{{'a', 1}, {'b', 2}}, {{'c', 1}, {'d', 2}}}, - /* StarterLayout */ {{'a', 2}, {'c', 2}}, __LINE__); - EXPECT_EQ(Reachables, - (std::set<Node>{{'a', 2}, {'b', 3}, {'c', 2}, {'d', 3}})); -} - // Multiple starters: (a,1) -> (b,1), (c,1) -> (d,1) (disconnected). // Start from leaves {(b,1), (d,1)} => {(b,1), (d,1)} TEST_F(UnsafeBufferReachableAnalysisTest, MultipleStartersLeaves) { @@ -569,14 +408,379 @@ TEST_F(UnsafeBufferReachableAnalysisTest, MultipleStartersLeaves) { EXPECT_TRUE(Reachables.count({'d', 1})); } -// Multi-key, same source entity: (a,1) -> (b,1), (a,2) -> (c,1). -// Start from {(a,3)} => {(a,3), (b,3), (c,2)} -TEST_F(UnsafeBufferReachableAnalysisTest, MultipleKeysSameEntity) { - auto Reachables = singlePartition( - /* EntityDomain */ {'a', 'b', 'c'}, - /* EdgeLayout */ {{{'a', 1}, {'b', 1}}, {{'a', 2}, {'c', 1}}}, - /* StarterLayout */ {{'a', 3}}, __LINE__); - EXPECT_EQ(Reachables, (std::set<Node>{{'a', 3}, {'b', 3}, {'c', 2}})); +// TODO: If one day we have good ways to query json in lit tests, move unit +// tests below to lit tests. + +// Test harness for taking source code as input, driving all the separate tools +// (extractors and linking) up until UnsafeBufferReachableAnalysis. +class UnsafeBufferReachableAnalysisSourceTest : public TestFixture { +protected: + using Node = std::pair<std::string, unsigned>; + + llvm::SmallString<128> TestDir; + + void SetUp() override { + std::error_code EC = llvm::sys::fs::createUniqueDirectory( + "unsafe-buffer-reachable-test", TestDir); + ASSERT_FALSE(EC) << "Failed to create temp directory: " << EC.message(); + } + + void TearDown() override { llvm::sys::fs::remove_directories(TestDir); } + + llvm::SmallString<128> makePath(llvm::StringRef FileName) const { + llvm::SmallString<128> Path = TestDir; + llvm::sys::path::append(Path, FileName); + return Path; + } + + std::optional<std::set<Node>> computeReachables(llvm::StringRef Code, + unsigned Line) { + std::unique_ptr<ASTUnit> AST = tooling::buildASTFromCodeWithArgs( + Code, {"-Wno-unused-value", "-Wno-int-to-pointer-cast"}); + if (!AST) { + ADD_FAILURE_AT(__FILE__, Line) << "failed to build AST"; + return std::nullopt; + } + + SSAFOptions Opts; + TUSummary TUSum(llvm::Triple("fake-unittest-triple"), + BuildNamespace(BuildNamespaceKind::CompilationUnit, "tu")); + TUSummaryBuilder Builder(TUSum, Opts); + + for (llvm::StringRef ExtractorName : + {PointerFlowEntitySummary::Name, UnsafeBufferUsageEntitySummary::Name, + TypeConstrainedPointersEntitySummary::Name}) { + std::unique_ptr<TUSummaryExtractor> Extractor = + makeTUSummaryExtractor(ExtractorName, Builder); + if (!Extractor) { + ADD_FAILURE_AT(__FILE__, Line) + << "failed to find extractor '" << ExtractorName << "'"; + return std::nullopt; + } + Extractor->HandleTranslationUnit(AST->getASTContext()); + } + + JSONFormat Format; + llvm::SmallString<128> TUPath = makePath("tu.json"); + if (auto Err = Format.writeTUSummary(TUSum, TUPath)) { + ADD_FAILURE_AT(__FILE__, Line) << llvm::toString(std::move(Err)); + return std::nullopt; + } + + auto TUEncOrErr = Format.readTUSummaryEncoding(TUPath); + if (!TUEncOrErr) { + ADD_FAILURE_AT(__FILE__, Line) << llvm::toString(TUEncOrErr.takeError()); + return std::nullopt; + } + + EntityLinker Linker(llvm::Triple("fake-unittest-triple"), + NestedBuildNamespace(BuildNamespace( + BuildNamespaceKind::LinkUnit, "lu"))); + if (auto Err = Linker.link( + std::make_unique<TUSummaryEncoding>(std::move(*TUEncOrErr)))) { + ADD_FAILURE_AT(__FILE__, Line) << llvm::toString(std::move(Err)); + return std::nullopt; + } + LUSummaryEncoding LUEnc = std::move(Linker).takeOutput(); + + llvm::SmallString<128> LUPath = makePath("lu.json"); + if (auto Err = Format.writeLUSummaryEncoding(LUEnc, LUPath)) { + ADD_FAILURE_AT(__FILE__, Line) << llvm::toString(std::move(Err)); + return std::nullopt; + } + + // TearDown() removes the whole TestDir, but clean up these two + // intermediate files as soon as we're done with them. + auto Cleanup = llvm::scope_exit([&] { + llvm::sys::fs::remove(TUPath); + llvm::sys::fs::remove(LUPath); + }); + + auto LUOrErr = Format.readLUSummary(LUPath); + if (!LUOrErr) { + ADD_FAILURE_AT(__FILE__, Line) << llvm::toString(LUOrErr.takeError()); + return std::nullopt; + } + + AnalysisDriver Driver(std::make_unique<LUSummary>(std::move(*LUOrErr))); + auto WPAOrErr = + Driver.run<PointerFlowAnalysisResult, UnsafeBufferUsageAnalysisResult, + TypeConstrainedPointersAnalysisResult, + UnsafeBufferReachableAnalysisResult>(); + if (!WPAOrErr) { + ADD_FAILURE_AT(__FILE__, Line) << llvm::toString(WPAOrErr.takeError()); + return std::nullopt; + } + auto ROrErr = WPAOrErr->get<UnsafeBufferReachableAnalysisResult>(); + if (!ROrErr) { + ADD_FAILURE_AT(__FILE__, Line) << llvm::toString(ROrErr.takeError()); + return std::nullopt; + } + + std::map<EntityId, std::string> IdToParamName; + if (const FunctionDecl *FD = findFnByName("f", AST->getASTContext())) { + for (const ParmVarDecl *PVD : FD->parameters()) { + std::optional<EntityName> EN = getEntityName(PVD); + if (!EN) + continue; + WPAOrErr->getIdTable().forEach( + [&](const EntityName &Candidate, EntityId Id) { + if (getSuffix(Candidate) == getSuffix(*EN)) + IdToParamName[Id] = PVD->getNameAsString(); + }); + } + } + + std::set<Node> Result; + for (const auto &[Id, EPLs] : ROrErr->Reachables) { + for (const EntityPointerLevel &EPL : EPLs) { + auto NameIt = IdToParamName.find(EPL.getEntity()); + if (NameIt == IdToParamName.end()) { + ADD_FAILURE_AT(__FILE__, Line) + << "reachable entity has no known source-level name"; + continue; + } + Result.insert({NameIt->second, EPL.getPointerLevel()}); + } + } + return Result; + } +}; + +// graph: (a,2)->(b,3)->(c,4)->(d,5) +TEST_F(UnsafeBufferReachableAnalysisSourceTest, LinearChain) { + auto Reachables = computeReachables(R"cpp( + void f(char **a, char ***b, char ****c, char *****d, int i) { + a = *b; + b = *c; + c = *d; + (*a)[i] = 0; // starter: (a,2) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, + (std::set<Node>{{"a", 2}, {"b", 3}, {"c", 4}, {"d", 5}})); +} + +// graph: (a,2)->(b,3); (b,4)->(c,1)->(d,1) +TEST_F(UnsafeBufferReachableAnalysisSourceTest, LinearChainDisconnected) { + auto Reachables = computeReachables(R"cpp( + void f(char ***a, char ****b, char *c, char *d, int i) { + a = *b; + ***b = c; + c = d; + (*a)[i] = 0; // starter: (a,2) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, (std::set<Node>{{"a", 2}, {"b", 3}})); +} + +// graph: (a,2)->{(b,3),(c,3)}->(d,4) +TEST_F(UnsafeBufferReachableAnalysisSourceTest, Diamond) { + auto Reachables = computeReachables(R"cpp( + void f(char **a, char ***b, char ***c, char ****d, int i) { + a = *b; + a = *c; + b = *d; + c = *d; + (*a)[i] = 0; // starter: (a,2) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, + (std::set<Node>{{"a", 2}, {"b", 3}, {"c", 3}, {"d", 4}})); +} + +// graph: (a,2)->{(b,3),(c,3)}; {(b,5),(c,5)}->(d,1) +TEST_F(UnsafeBufferReachableAnalysisSourceTest, DisconnectedDiamond) { + auto Reachables = computeReachables(R"cpp( + void f(char ****a, char *****b, char *****c, char *d, int i) { + a = *b; + a = *c; + ****b = d; + ****c = d; + (*a)[i] = 0; // starter: (a,2) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, (std::set<Node>{{"a", 2}, {"b", 3}, {"c", 3}})); +} + +// graph: (a,1)->(b,1); (c,1)->(d,1) +TEST_F(UnsafeBufferReachableAnalysisSourceTest, DisconnectedSubgraphs) { + auto Reachables = computeReachables(R"cpp( + void f(char *a, char *b, char *c, char *d, int i) { + a = b; + c = d; + b[i] = 0; // starter: (b,1) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, (std::set<Node>{{"b", 1}})); +} + +// graph: (a,2)->(b,2)->(c,2)->(d,2)->(a,2) +TEST_F(UnsafeBufferReachableAnalysisSourceTest, Cycle) { + auto Reachables = computeReachables(R"cpp( + void f(char **a, char **b, char **c, char **d, int i) { + a = b; + b = c; + c = d; + d = a; + (*c)[i] = 0; // starter: (c,2) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, + (std::set<Node>{{"a", 2}, {"b", 2}, {"c", 2}, {"d", 2}})); +} + +// graph: (a,2)->(b,3)->(c,4)->(d,5)->(a,1) +TEST_F(UnsafeBufferReachableAnalysisSourceTest, CycleIncreasing) { + auto Reachables = computeReachables(R"cpp( + void f(char **a, char ***b, char ****c, char *****d, int i) { + a = *b; + *b = **c; + **c = ***d; + ***d = a; + (*a)[i] = 0; // starter: (a,2) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, + (std::set<Node>{{"a", 2}, {"b", 3}, {"c", 4}, {"d", 5}})); +} + +// graph: (a,2)->{(b,3),(c,3),(d,3)} +TEST_F(UnsafeBufferReachableAnalysisSourceTest, StarFromHub) { + auto Reachables = computeReachables(R"cpp( + void f(char **a, char ***b, char ***c, char ***d, int i) { + a = *b; + a = *c; + a = *d; + (*a)[i] = 0; // starter: (a,2) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, + (std::set<Node>{{"a", 2}, {"b", 3}, {"c", 3}, {"d", 3}})); +} + +// graph: (a,2)->{(b,1),(c,1),(d,1)} +TEST_F(UnsafeBufferReachableAnalysisSourceTest, StarFromHubBelowEdge) { + auto Reachables = computeReachables(R"cpp( + void f(char **a, char *b, char *c, char *d, int i) { + *a = b; + *a = c; + *a = d; + a[i] = 0; // starter: (a,1) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, (std::set<Node>{{"a", 1}})); +} + +// graph: {(a,2),(b,2),(c,2)}->(d,3) +TEST_F(UnsafeBufferReachableAnalysisSourceTest, ReverseStarFromSource) { + auto Reachables = computeReachables(R"cpp( + void f(char **a, char **b, char **c, char ***d, int i) { + a = *d; + b = *d; + c = *d; + (*a)[i] = 0; // starter: (a,2) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, (std::set<Node>{{"a", 2}, {"d", 3}})); +} + +// graph: {(a,2),(b,2),(c,2)}->(d,2) +TEST_F(UnsafeBufferReachableAnalysisSourceTest, ReverseStarFromSink) { + auto Reachables = computeReachables(R"cpp( + void f(char **a, char **b, char **c, char **d, int i) { + a = d; + b = d; + c = d; + (*d)[i] = 0; // starter: (d,2) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, (std::set<Node>{{"d", 2}})); +} + +// graph: (a,2)->(b,2)->(b,2)->(c,3)->(d,4) +TEST_F(UnsafeBufferReachableAnalysisSourceTest, SelfLoopFromRoot) { + auto Reachables = computeReachables(R"cpp( + void f(char **a, char **b, char ***c, char ****d, int i) { + a = b; + b = b; + b = *c; + c = *d; + (*a)[i] = 0; // starter: (a,2) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, + (std::set<Node>{{"a", 2}, {"b", 2}, {"c", 3}, {"d", 4}})); +} + +// graph: (b,2)->(b,2)->(c,3)->(d,4) +TEST_F(UnsafeBufferReachableAnalysisSourceTest, SelfLoopFromLoopNode) { + auto Reachables = computeReachables(R"cpp( + void f(char **a, char **b, char ***c, char ****d, int i) { + a = b; + b = b; + b = *c; + c = *d; + (*b)[i] = 0; // starter: (b,2) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, (std::set<Node>{{"b", 2}, {"c", 3}, {"d", 4}})); +} + +// graph: (a,2)->(b,3); (c,2)->(d,3) +TEST_F(UnsafeBufferReachableAnalysisSourceTest, MultipleStarters) { + auto Reachables = computeReachables(R"cpp( + void f(char **a, char ***b, char **c, char ***d, int i) { + a = *b; + c = *d; + (*a)[i] = 0; // starter: (a,2) + (*c)[i] = 0; // starter: (c,2) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, + (std::set<Node>{{"a", 2}, {"b", 3}, {"c", 2}, {"d", 3}})); +} + +// graph: (a,3)->{(b,3),(c,2)} +TEST_F(UnsafeBufferReachableAnalysisSourceTest, MultipleKeysSameEntity) { + auto Reachables = computeReachables(R"cpp( + void f(char ***a, char ***b, char **c, int i) { + a = b; + *a = c; + (**a)[i] = 0; // starter: (a,3) + } + )cpp", + __LINE__); + ASSERT_TRUE(Reachables); + EXPECT_EQ(*Reachables, (std::set<Node>{{"a", 3}, {"b", 3}, {"c", 2}})); } } // namespace _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
