https://github.com/ziqingluo-90 updated https://github.com/llvm/llvm-project/pull/218209
>From 1993e9673edfeef8058428b4aae2946564363fae Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Fri, 21 Aug 2026 18:22:03 -0700 Subject: [PATCH 1/3] [SSAF][PointerFlow] Change unsafe-buffer reachability analysis back to simple graph search Because of commit 30cd4297b, 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 graphs 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 --- .../UnsafeBufferUsageAnalysis.cpp | 50 +-- .../unsafe-buffer-reachable-cast-cycle.test | 52 +++ .../unsafe-buffer-reachable-topologies.test | 367 ++++++++++++++++++ .../UnsafeBufferReachableAnalysisTest.cpp | 190 --------- 4 files changed, 424 insertions(+), 235 deletions(-) create mode 100644 clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-cast-cycle.test create mode 100644 clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-topologies.test diff --git a/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp b/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp index 4c92a37a078d1..90a0e3633151a 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,7 @@ 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..46a3092b801ea --- /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/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-topologies.test b/clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-topologies.test new file mode 100644 index 0000000000000..397b7df48b51e --- /dev/null +++ b/clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-topologies.test @@ -0,0 +1,367 @@ +// End-to-end tests of UnsafeBufferReachableAnalysis. Testing against +// pointer flow graphs of different shapes. +// +// RUN: rm -rf %t && mkdir -p %t +// RUN: split-file %s %t + +// The extract -> link -> analyze -> check pipeline is defined once and reused; +// each topology only redefines its source name and FileCheck prefix. +// +// The CHECK lines use readable tokens instead of inline FileCheck regex; the +// sed below expands them into regex on the fly and pipes the result straight +// into FileCheck (no intermediate file): +// $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. +// +// DEFINE: %{name} = +// DEFINE: %{prefix} = +// DEFINE: %{check} = \ +// DEFINE: %clang_cc1 -fsyntax-only -Wno-self-assign %t/%{name}.cpp \ +// DEFINE: --ssaf-extract-summaries=PointerFlow,UnsafeBufferUsage,TypeConstrainedPointers \ +// DEFINE: --ssaf-compilation-unit-id=%{name} \ +// DEFINE: --ssaf-tu-summary-file=%t/%{name}.summary.json && \ +// DEFINE: clang-ssaf-linker %t/%{name}.summary.json -o %t/%{name}.lu.json && \ +// DEFINE: clang-ssaf-analyzer %t/%{name}.lu.json -o %t/%{name}.wpa.json \ +// DEFINE: -a UnsafeBufferReachableAnalysisResult && \ +// DEFINE: sed -e 's|$NS|{{([^]]\|[[:space:]])+\],}}|g' \ +// DEFINE: -e 's|$WS|{{[[:space:]]+}}|g' \ +// DEFINE: -e 's|$PTR_L1|{{[[:space:]]+\\},[[:space:]]+1[[:space:]]+\\]}}|g' \ +// DEFINE: -e 's|$PTR_L2|{{[[:space:]]+\\},[[:space:]]+2[[:space:]]+\\]}}|g' \ +// DEFINE: -e 's|$PTR_L3|{{[[:space:]]+\\},[[:space:]]+3[[:space:]]+\\]}}|g' \ +// DEFINE: -e 's|$PTR_L4|{{[[:space:]]+\\},[[:space:]]+4[[:space:]]+\\]}}|g' \ +// DEFINE: -e 's|$PTR_L5|{{[[:space:]]+\\},[[:space:]]+5[[:space:]]+\\]}}|g' \ +// DEFINE: %s \ +// DEFINE: | FileCheck - --check-prefix=%{prefix} --input-file=%t/%{name}.wpa.json + +// REDEFINE: %{name} = linear_chain +// REDEFINE: %{prefix} = CHAIN +// RUN: %{check} +//--- linear_chain.cpp +// (a,1)->(b,2), (b,1)->(c,2), (c,1)->(d,2); start (a,2). +// Result: {(a,2),(b,3),(c,4),(d,5)}. +void f(char **a, char ***b, char ****c, char *****d, int i) { + a = *b; + b = *c; + c = *d; + (*a)[i] = 0; // starter: (a,2) +} +// CHAIN-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" +// CHAIN-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" +// CHAIN-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" +// CHAIN-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" +// CHAIN: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// CHAIN: "@": [[A]]$PTR_L2 +// CHAIN: "@": [[B]]$PTR_L3 +// CHAIN: "@": [[C]]$PTR_L4 +// CHAIN: "@": [[D]]$PTR_L5 +// CHAIN-NOT: "@": +// CHAIN: "analysis_name": + +// REDEFINE: %{name} = linear_chain_disconnected +// REDEFINE: %{prefix} = CHAINDISC +// RUN: %{check} +//--- linear_chain_disconnected.cpp +// (a,1)->(b,2), (b,4)->(c,1), (c,1)->(d,1); start (a,2). +// Result: {(a,2),(b,3)}. +void f(char ***a, char ****b, char *c, char *d, int i) { + a = *b; + ***b = c; + c = d; + (*a)[i] = 0; // starter: (a,2) +} +// CHAINDISC-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" +// CHAINDISC-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" +// CHAINDISC: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// CHAINDISC: "@": [[A]]$PTR_L2 +// CHAINDISC: "@": [[B]]$PTR_L3 +// CHAINDISC-NOT: "@": +// CHAINDISC: "analysis_name": + +// REDEFINE: %{name} = diamond +// REDEFINE: %{prefix} = DIAMOND +// RUN: %{check} +//--- diamond.cpp +// (a,1)->(b,2), (a,1)->(c,2), (b,1)->(d,2), (c,1)->(d,2); start (a,2). +// Result: {(a,2),(b,3),(c,3),(d,4)}. +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) +} +// DIAMOND-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" +// DIAMOND-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" +// DIAMOND-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" +// DIAMOND-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" +// DIAMOND: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// DIAMOND: "@": [[A]]$PTR_L2 +// DIAMOND: "@": [[B]]$PTR_L3 +// DIAMOND: "@": [[C]]$PTR_L3 +// DIAMOND: "@": [[D]]$PTR_L4 +// DIAMOND-NOT: "@": +// DIAMOND: "analysis_name": + +// REDEFINE: %{name} = disconnected_diamond +// REDEFINE: %{prefix} = DISCONN +// RUN: %{check} +//--- disconnected_diamond.cpp +// (a,1)->(b,2), (a,1)->(c,2), (b,5)->(d,1), (c,5)->(d,1); start (a,2). +// Result: {(a,2),(b,3),(c,3)}. +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) +} +// DISCONN-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" +// DISCONN-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" +// DISCONN-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" +// DISCONN: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// DISCONN: "@": [[A]]$PTR_L2 +// DISCONN: "@": [[B]]$PTR_L3 +// DISCONN: "@": [[C]]$PTR_L3 +// DISCONN-NOT: "@": +// DISCONN: "analysis_name": + +// REDEFINE: %{name} = disconnected_subgraphs +// REDEFINE: %{prefix} = DISCONNSUB +// RUN: %{check} +//--- disconnected_subgraphs.cpp +// (a,1)->(b,1), (c,1)->(d,1); start from tail (b,1). +// Result: {(b,1)}. +void f(char *a, char *b, char *c, char *d, int i) { + a = b; + c = d; + b[i] = 0; // starter: (b,1) +} +// DISCONNSUB-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" +// DISCONNSUB: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// DISCONNSUB: "@": [[B]]$PTR_L1 +// DISCONNSUB-NOT: "@": +// DISCONNSUB: "analysis_name": + +// REDEFINE: %{name} = cycle +// REDEFINE: %{prefix} = CYCLE +// RUN: %{check} +//--- cycle.cpp +// (a,1)->(b,1)->(c,1)->(d,1)->(a,1); start (c,2). +// Result: {(a,2),(b,2),(c,2),(d,2)}. +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) +} +// CYCLE-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" +// CYCLE-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" +// CYCLE-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" +// CYCLE-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" +// CYCLE: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// CYCLE: "@": [[A]]$PTR_L2 +// CYCLE: "@": [[B]]$PTR_L2 +// CYCLE: "@": [[C]]$PTR_L2 +// CYCLE: "@": [[D]]$PTR_L2 +// CYCLE-NOT: "@": +// CYCLE: "analysis_name": + +// REDEFINE: %{name} = cycle_increasing +// REDEFINE: %{prefix} = CYCLEINC +// RUN: %{check} +//--- cycle_increasing.cpp +// (a,1)->(b,2)->(c,3)->(d,4)->(a,1); start (a,2). +// Result: {(a,2),(b,3),(c,4),(d,5)}. +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) +} +// CYCLEINC-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" +// CYCLEINC-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" +// CYCLEINC-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" +// CYCLEINC-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" +// CYCLEINC: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// CYCLEINC: "@": [[A]]$PTR_L2 +// CYCLEINC: "@": [[B]]$PTR_L3 +// CYCLEINC: "@": [[C]]$PTR_L4 +// CYCLEINC: "@": [[D]]$PTR_L5 +// CYCLEINC-NOT: "@": +// CYCLEINC: "analysis_name": + +// REDEFINE: %{name} = star_from_hub +// REDEFINE: %{prefix} = HUB +// RUN: %{check} +//--- star_from_hub.cpp +// (a,1)->(b,2), (a,1)->(c,2), (a,1)->(d,2); start (a,2). +// Result: {(a,2),(b,3),(c,3),(d,3)}. +void f(char **a, char ***b, char ***c, char ***d, int i) { + a = *b; + a = *c; + a = *d; + (*a)[i] = 0; // starter: (a,2) +} +// HUB-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" +// HUB-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" +// HUB-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" +// HUB-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" +// HUB: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// HUB: "@": [[A]]$PTR_L2 +// HUB: "@": [[B]]$PTR_L3 +// HUB: "@": [[C]]$PTR_L3 +// HUB: "@": [[D]]$PTR_L3 +// HUB-NOT: "@": +// HUB: "analysis_name": + +// REDEFINE: %{name} = star_from_hub_below_edge +// REDEFINE: %{prefix} = HUBBELOW +// RUN: %{check} +//--- star_from_hub_below_edge.cpp +// (a,2)->(b,1), (a,2)->(c,1), (a,2)->(d,1); start (a,1). +// Result: {(a,1)}. +void f(char **a, char *b, char *c, char *d, int i) { + *a = b; + *a = c; + *a = d; + a[i] = 0; // starter: (a,1) +} +// HUBBELOW-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" +// HUBBELOW: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// HUBBELOW: "@": [[A]]$PTR_L1 +// HUBBELOW-NOT: "@": +// HUBBELOW: "analysis_name": + +// REDEFINE: %{name} = reverse_star_from_source +// REDEFINE: %{prefix} = REVSRC +// RUN: %{check} +//--- reverse_star_from_source.cpp +// (a,1)->(d,2), (b,1)->(d,2), (c,1)->(d,2); start (a,2). +// Result: {(a,2),(d,3)}. +void f(char **a, char **b, char **c, char ***d, int i) { + a = *d; + b = *d; + c = *d; + (*a)[i] = 0; // starter: (a,2) +} +// REVSRC-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" +// REVSRC-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" +// REVSRC: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// REVSRC: "@": [[A]]$PTR_L2 +// REVSRC: "@": [[D]]$PTR_L3 +// REVSRC-NOT: "@": +// REVSRC: "analysis_name": + +// REDEFINE: %{name} = reverse_star_from_sink +// REDEFINE: %{prefix} = REVSINK +// RUN: %{check} +//--- reverse_star_from_sink.cpp +// (a,1)->(d,1), (b,1)->(d,1), (c,1)->(d,1); start sink (d,2). +// Result: {(d,2)}. +void f(char **a, char **b, char **c, char **d, int i) { + a = d; + b = d; + c = d; + (*d)[i] = 0; // starter: (d,2) +} +// REVSINK-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" +// REVSINK: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// REVSINK: "@": [[D]]$PTR_L2 +// REVSINK-NOT: "@": +// REVSINK: "analysis_name": + +// REDEFINE: %{name} = self_loop_from_root +// REDEFINE: %{prefix} = LOOPROOT +// RUN: %{check} +//--- self_loop_from_root.cpp +// (a,1)->(b,1), (b,1)->(b,1), (b,1)->(c,2), (c,1)->(d,2); start (a,2). +// Result: {(a,2),(b,2),(c,3),(d,4)}. +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) +} +// LOOPROOT-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" +// LOOPROOT-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" +// LOOPROOT-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" +// LOOPROOT-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" +// LOOPROOT: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// LOOPROOT: "@": [[A]]$PTR_L2 +// LOOPROOT: "@": [[B]]$PTR_L2 +// LOOPROOT: "@": [[C]]$PTR_L3 +// LOOPROOT: "@": [[D]]$PTR_L4 +// LOOPROOT-NOT: "@": +// LOOPROOT: "analysis_name": + +// REDEFINE: %{name} = self_loop_from_loop_node +// REDEFINE: %{prefix} = LOOPNODE +// RUN: %{check} +//--- self_loop_from_loop_node.cpp +// Same graph as self_loop_from_root; start on the loop node (b,2). +// Result: {(b,2),(c,3),(d,4)}. +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) +} +// LOOPNODE-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" +// LOOPNODE-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" +// LOOPNODE-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" +// LOOPNODE: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// LOOPNODE: "@": [[B]]$PTR_L2 +// LOOPNODE: "@": [[C]]$PTR_L3 +// LOOPNODE: "@": [[D]]$PTR_L4 +// LOOPNODE-NOT: "@": +// LOOPNODE: "analysis_name": + +// REDEFINE: %{name} = multiple_starters +// REDEFINE: %{prefix} = MULTISTART +// RUN: %{check} +//--- multiple_starters.cpp +// (a,1)->(b,2), (c,1)->(d,2); start {(a,2),(c,2)}. +// Result: {(a,2),(b,3),(c,2),(d,3)}. +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) +} +// MULTISTART-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" +// MULTISTART-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" +// MULTISTART-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" +// MULTISTART-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" +// MULTISTART: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// MULTISTART: "@": [[A]]$PTR_L2 +// MULTISTART: "@": [[B]]$PTR_L3 +// MULTISTART: "@": [[C]]$PTR_L2 +// MULTISTART: "@": [[D]]$PTR_L3 +// MULTISTART-NOT: "@": +// MULTISTART: "analysis_name": + +// REDEFINE: %{name} = multiple_keys_same_entity +// REDEFINE: %{prefix} = MULTIKEY +// RUN: %{check} +//--- multiple_keys_same_entity.cpp +// (a,1)->(b,1), (a,2)->(c,1); start (a,3). +// Result: {(a,3),(b,3),(c,2)}. +void f(char ***a, char ***b, char **c, int i) { + a = b; + *a = c; + (**a)[i] = 0; // starter: (a,3) +} +// MULTIKEY-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" +// MULTIKEY-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" +// MULTIKEY-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" +// MULTIKEY: "analysis_name": "UnsafeBufferReachableAnalysisResult" +// MULTIKEY: "@": [[A]]$PTR_L3 +// MULTIKEY: "@": [[B]]$PTR_L3 +// MULTIKEY: "@": [[C]]$PTR_L2 +// MULTIKEY-NOT: "@": +// MULTIKEY: "analysis_name": diff --git a/clang/unittests/ScalableStaticAnalysis/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp b/clang/unittests/ScalableStaticAnalysis/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp index cf5420b35e7dc..64486d1a22226 100644 --- a/clang/unittests/ScalableStaticAnalysis/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp +++ b/clang/unittests/ScalableStaticAnalysis/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp @@ -205,31 +205,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 +232,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 +260,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 +278,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 +299,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 +324,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 +336,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 +350,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 +367,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 +377,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 +389,4 @@ 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}})); -} - } // namespace >From 48f081aa8a30d729d022b6d495250ab5d477a869 Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Thu, 27 Aug 2026 12:01:13 -0700 Subject: [PATCH 2/3] fix clang-format --- .../Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp | 3 ++- .../PointerFlow/unsafe-buffer-reachable-cast-cycle.test | 2 +- 2 files changed, 3 insertions(+), 2 deletions(-) diff --git a/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp b/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp index 90a0e3633151a..4fc6d058de368 100644 --- a/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp +++ b/clang/lib/ScalableStaticAnalysis/Analyses/UnsafeBufferUsage/UnsafeBufferUsageAnalysis.cpp @@ -225,7 +225,8 @@ class UnsafeBufferReachableAnalysis FilteredDstRange.end()); } if (!FilteredSubGraph.empty()) - BPG.try_emplace(Id, BoundsPropagationGraph{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 index 46a3092b801ea..f64c043f855a9 100644 --- a/clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-cast-cycle.test +++ b/clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-cast-cycle.test @@ -42,7 +42,7 @@ void f(char **a, char ***b, int i, int j) { // 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)} +// 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 >From 6b858d98e700b075ce71f560f5635b4963432d0d Mon Sep 17 00:00:00 2001 From: Ziqing Luo <[email protected]> Date: Sat, 29 Aug 2026 16:33:12 -0700 Subject: [PATCH 3/3] change lit-tests to unit tests because there is no way to FileCheck json completely --- .../unsafe-buffer-reachable-topologies.test | 367 ---------------- .../UnsafeBufferReachableAnalysisTest.cpp | 394 ++++++++++++++++++ 2 files changed, 394 insertions(+), 367 deletions(-) delete mode 100644 clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-topologies.test diff --git a/clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-topologies.test b/clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-topologies.test deleted file mode 100644 index 397b7df48b51e..0000000000000 --- a/clang/test/Analysis/Scalable/PointerFlow/unsafe-buffer-reachable-topologies.test +++ /dev/null @@ -1,367 +0,0 @@ -// End-to-end tests of UnsafeBufferReachableAnalysis. Testing against -// pointer flow graphs of different shapes. -// -// RUN: rm -rf %t && mkdir -p %t -// RUN: split-file %s %t - -// The extract -> link -> analyze -> check pipeline is defined once and reused; -// each topology only redefines its source name and FileCheck prefix. -// -// The CHECK lines use readable tokens instead of inline FileCheck regex; the -// sed below expands them into regex on the fly and pipes the result straight -// into FileCheck (no intermediate file): -// $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. -// -// DEFINE: %{name} = -// DEFINE: %{prefix} = -// DEFINE: %{check} = \ -// DEFINE: %clang_cc1 -fsyntax-only -Wno-self-assign %t/%{name}.cpp \ -// DEFINE: --ssaf-extract-summaries=PointerFlow,UnsafeBufferUsage,TypeConstrainedPointers \ -// DEFINE: --ssaf-compilation-unit-id=%{name} \ -// DEFINE: --ssaf-tu-summary-file=%t/%{name}.summary.json && \ -// DEFINE: clang-ssaf-linker %t/%{name}.summary.json -o %t/%{name}.lu.json && \ -// DEFINE: clang-ssaf-analyzer %t/%{name}.lu.json -o %t/%{name}.wpa.json \ -// DEFINE: -a UnsafeBufferReachableAnalysisResult && \ -// DEFINE: sed -e 's|$NS|{{([^]]\|[[:space:]])+\],}}|g' \ -// DEFINE: -e 's|$WS|{{[[:space:]]+}}|g' \ -// DEFINE: -e 's|$PTR_L1|{{[[:space:]]+\\},[[:space:]]+1[[:space:]]+\\]}}|g' \ -// DEFINE: -e 's|$PTR_L2|{{[[:space:]]+\\},[[:space:]]+2[[:space:]]+\\]}}|g' \ -// DEFINE: -e 's|$PTR_L3|{{[[:space:]]+\\},[[:space:]]+3[[:space:]]+\\]}}|g' \ -// DEFINE: -e 's|$PTR_L4|{{[[:space:]]+\\},[[:space:]]+4[[:space:]]+\\]}}|g' \ -// DEFINE: -e 's|$PTR_L5|{{[[:space:]]+\\},[[:space:]]+5[[:space:]]+\\]}}|g' \ -// DEFINE: %s \ -// DEFINE: | FileCheck - --check-prefix=%{prefix} --input-file=%t/%{name}.wpa.json - -// REDEFINE: %{name} = linear_chain -// REDEFINE: %{prefix} = CHAIN -// RUN: %{check} -//--- linear_chain.cpp -// (a,1)->(b,2), (b,1)->(c,2), (c,1)->(d,2); start (a,2). -// Result: {(a,2),(b,3),(c,4),(d,5)}. -void f(char **a, char ***b, char ****c, char *****d, int i) { - a = *b; - b = *c; - c = *d; - (*a)[i] = 0; // starter: (a,2) -} -// CHAIN-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" -// CHAIN-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" -// CHAIN-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" -// CHAIN-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" -// CHAIN: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// CHAIN: "@": [[A]]$PTR_L2 -// CHAIN: "@": [[B]]$PTR_L3 -// CHAIN: "@": [[C]]$PTR_L4 -// CHAIN: "@": [[D]]$PTR_L5 -// CHAIN-NOT: "@": -// CHAIN: "analysis_name": - -// REDEFINE: %{name} = linear_chain_disconnected -// REDEFINE: %{prefix} = CHAINDISC -// RUN: %{check} -//--- linear_chain_disconnected.cpp -// (a,1)->(b,2), (b,4)->(c,1), (c,1)->(d,1); start (a,2). -// Result: {(a,2),(b,3)}. -void f(char ***a, char ****b, char *c, char *d, int i) { - a = *b; - ***b = c; - c = d; - (*a)[i] = 0; // starter: (a,2) -} -// CHAINDISC-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" -// CHAINDISC-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" -// CHAINDISC: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// CHAINDISC: "@": [[A]]$PTR_L2 -// CHAINDISC: "@": [[B]]$PTR_L3 -// CHAINDISC-NOT: "@": -// CHAINDISC: "analysis_name": - -// REDEFINE: %{name} = diamond -// REDEFINE: %{prefix} = DIAMOND -// RUN: %{check} -//--- diamond.cpp -// (a,1)->(b,2), (a,1)->(c,2), (b,1)->(d,2), (c,1)->(d,2); start (a,2). -// Result: {(a,2),(b,3),(c,3),(d,4)}. -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) -} -// DIAMOND-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" -// DIAMOND-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" -// DIAMOND-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" -// DIAMOND-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" -// DIAMOND: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// DIAMOND: "@": [[A]]$PTR_L2 -// DIAMOND: "@": [[B]]$PTR_L3 -// DIAMOND: "@": [[C]]$PTR_L3 -// DIAMOND: "@": [[D]]$PTR_L4 -// DIAMOND-NOT: "@": -// DIAMOND: "analysis_name": - -// REDEFINE: %{name} = disconnected_diamond -// REDEFINE: %{prefix} = DISCONN -// RUN: %{check} -//--- disconnected_diamond.cpp -// (a,1)->(b,2), (a,1)->(c,2), (b,5)->(d,1), (c,5)->(d,1); start (a,2). -// Result: {(a,2),(b,3),(c,3)}. -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) -} -// DISCONN-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" -// DISCONN-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" -// DISCONN-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" -// DISCONN: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// DISCONN: "@": [[A]]$PTR_L2 -// DISCONN: "@": [[B]]$PTR_L3 -// DISCONN: "@": [[C]]$PTR_L3 -// DISCONN-NOT: "@": -// DISCONN: "analysis_name": - -// REDEFINE: %{name} = disconnected_subgraphs -// REDEFINE: %{prefix} = DISCONNSUB -// RUN: %{check} -//--- disconnected_subgraphs.cpp -// (a,1)->(b,1), (c,1)->(d,1); start from tail (b,1). -// Result: {(b,1)}. -void f(char *a, char *b, char *c, char *d, int i) { - a = b; - c = d; - b[i] = 0; // starter: (b,1) -} -// DISCONNSUB-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" -// DISCONNSUB: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// DISCONNSUB: "@": [[B]]$PTR_L1 -// DISCONNSUB-NOT: "@": -// DISCONNSUB: "analysis_name": - -// REDEFINE: %{name} = cycle -// REDEFINE: %{prefix} = CYCLE -// RUN: %{check} -//--- cycle.cpp -// (a,1)->(b,1)->(c,1)->(d,1)->(a,1); start (c,2). -// Result: {(a,2),(b,2),(c,2),(d,2)}. -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) -} -// CYCLE-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" -// CYCLE-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" -// CYCLE-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" -// CYCLE-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" -// CYCLE: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// CYCLE: "@": [[A]]$PTR_L2 -// CYCLE: "@": [[B]]$PTR_L2 -// CYCLE: "@": [[C]]$PTR_L2 -// CYCLE: "@": [[D]]$PTR_L2 -// CYCLE-NOT: "@": -// CYCLE: "analysis_name": - -// REDEFINE: %{name} = cycle_increasing -// REDEFINE: %{prefix} = CYCLEINC -// RUN: %{check} -//--- cycle_increasing.cpp -// (a,1)->(b,2)->(c,3)->(d,4)->(a,1); start (a,2). -// Result: {(a,2),(b,3),(c,4),(d,5)}. -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) -} -// CYCLEINC-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" -// CYCLEINC-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" -// CYCLEINC-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" -// CYCLEINC-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" -// CYCLEINC: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// CYCLEINC: "@": [[A]]$PTR_L2 -// CYCLEINC: "@": [[B]]$PTR_L3 -// CYCLEINC: "@": [[C]]$PTR_L4 -// CYCLEINC: "@": [[D]]$PTR_L5 -// CYCLEINC-NOT: "@": -// CYCLEINC: "analysis_name": - -// REDEFINE: %{name} = star_from_hub -// REDEFINE: %{prefix} = HUB -// RUN: %{check} -//--- star_from_hub.cpp -// (a,1)->(b,2), (a,1)->(c,2), (a,1)->(d,2); start (a,2). -// Result: {(a,2),(b,3),(c,3),(d,3)}. -void f(char **a, char ***b, char ***c, char ***d, int i) { - a = *b; - a = *c; - a = *d; - (*a)[i] = 0; // starter: (a,2) -} -// HUB-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" -// HUB-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" -// HUB-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" -// HUB-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" -// HUB: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// HUB: "@": [[A]]$PTR_L2 -// HUB: "@": [[B]]$PTR_L3 -// HUB: "@": [[C]]$PTR_L3 -// HUB: "@": [[D]]$PTR_L3 -// HUB-NOT: "@": -// HUB: "analysis_name": - -// REDEFINE: %{name} = star_from_hub_below_edge -// REDEFINE: %{prefix} = HUBBELOW -// RUN: %{check} -//--- star_from_hub_below_edge.cpp -// (a,2)->(b,1), (a,2)->(c,1), (a,2)->(d,1); start (a,1). -// Result: {(a,1)}. -void f(char **a, char *b, char *c, char *d, int i) { - *a = b; - *a = c; - *a = d; - a[i] = 0; // starter: (a,1) -} -// HUBBELOW-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" -// HUBBELOW: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// HUBBELOW: "@": [[A]]$PTR_L1 -// HUBBELOW-NOT: "@": -// HUBBELOW: "analysis_name": - -// REDEFINE: %{name} = reverse_star_from_source -// REDEFINE: %{prefix} = REVSRC -// RUN: %{check} -//--- reverse_star_from_source.cpp -// (a,1)->(d,2), (b,1)->(d,2), (c,1)->(d,2); start (a,2). -// Result: {(a,2),(d,3)}. -void f(char **a, char **b, char **c, char ***d, int i) { - a = *d; - b = *d; - c = *d; - (*a)[i] = 0; // starter: (a,2) -} -// REVSRC-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" -// REVSRC-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" -// REVSRC: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// REVSRC: "@": [[A]]$PTR_L2 -// REVSRC: "@": [[D]]$PTR_L3 -// REVSRC-NOT: "@": -// REVSRC: "analysis_name": - -// REDEFINE: %{name} = reverse_star_from_sink -// REDEFINE: %{prefix} = REVSINK -// RUN: %{check} -//--- reverse_star_from_sink.cpp -// (a,1)->(d,1), (b,1)->(d,1), (c,1)->(d,1); start sink (d,2). -// Result: {(d,2)}. -void f(char **a, char **b, char **c, char **d, int i) { - a = d; - b = d; - c = d; - (*d)[i] = 0; // starter: (d,2) -} -// REVSINK-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" -// REVSINK: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// REVSINK: "@": [[D]]$PTR_L2 -// REVSINK-NOT: "@": -// REVSINK: "analysis_name": - -// REDEFINE: %{name} = self_loop_from_root -// REDEFINE: %{prefix} = LOOPROOT -// RUN: %{check} -//--- self_loop_from_root.cpp -// (a,1)->(b,1), (b,1)->(b,1), (b,1)->(c,2), (c,1)->(d,2); start (a,2). -// Result: {(a,2),(b,2),(c,3),(d,4)}. -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) -} -// LOOPROOT-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" -// LOOPROOT-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" -// LOOPROOT-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" -// LOOPROOT-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" -// LOOPROOT: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// LOOPROOT: "@": [[A]]$PTR_L2 -// LOOPROOT: "@": [[B]]$PTR_L2 -// LOOPROOT: "@": [[C]]$PTR_L3 -// LOOPROOT: "@": [[D]]$PTR_L4 -// LOOPROOT-NOT: "@": -// LOOPROOT: "analysis_name": - -// REDEFINE: %{name} = self_loop_from_loop_node -// REDEFINE: %{prefix} = LOOPNODE -// RUN: %{check} -//--- self_loop_from_loop_node.cpp -// Same graph as self_loop_from_root; start on the loop node (b,2). -// Result: {(b,2),(c,3),(d,4)}. -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) -} -// LOOPNODE-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" -// LOOPNODE-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" -// LOOPNODE-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" -// LOOPNODE: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// LOOPNODE: "@": [[B]]$PTR_L2 -// LOOPNODE: "@": [[C]]$PTR_L3 -// LOOPNODE: "@": [[D]]$PTR_L4 -// LOOPNODE-NOT: "@": -// LOOPNODE: "analysis_name": - -// REDEFINE: %{name} = multiple_starters -// REDEFINE: %{prefix} = MULTISTART -// RUN: %{check} -//--- multiple_starters.cpp -// (a,1)->(b,2), (c,1)->(d,2); start {(a,2),(c,2)}. -// Result: {(a,2),(b,3),(c,2),(d,3)}. -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) -} -// MULTISTART-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" -// MULTISTART-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" -// MULTISTART-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" -// MULTISTART-DAG: "id": [[D:[0-9]+]],$NS$WS"suffix": "4" -// MULTISTART: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// MULTISTART: "@": [[A]]$PTR_L2 -// MULTISTART: "@": [[B]]$PTR_L3 -// MULTISTART: "@": [[C]]$PTR_L2 -// MULTISTART: "@": [[D]]$PTR_L3 -// MULTISTART-NOT: "@": -// MULTISTART: "analysis_name": - -// REDEFINE: %{name} = multiple_keys_same_entity -// REDEFINE: %{prefix} = MULTIKEY -// RUN: %{check} -//--- multiple_keys_same_entity.cpp -// (a,1)->(b,1), (a,2)->(c,1); start (a,3). -// Result: {(a,3),(b,3),(c,2)}. -void f(char ***a, char ***b, char **c, int i) { - a = b; - *a = c; - (**a)[i] = 0; // starter: (a,3) -} -// MULTIKEY-DAG: "id": [[A:[0-9]+]],$NS$WS"suffix": "1" -// MULTIKEY-DAG: "id": [[B:[0-9]+]],$NS$WS"suffix": "2" -// MULTIKEY-DAG: "id": [[C:[0-9]+]],$NS$WS"suffix": "3" -// MULTIKEY: "analysis_name": "UnsafeBufferReachableAnalysisResult" -// MULTIKEY: "@": [[A]]$PTR_L3 -// MULTIKEY: "@": [[B]]$PTR_L3 -// MULTIKEY: "@": [[C]]$PTR_L2 -// MULTIKEY-NOT: "@": -// MULTIKEY: "analysis_name": diff --git a/clang/unittests/ScalableStaticAnalysis/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp b/clang/unittests/ScalableStaticAnalysis/WholeProgramAnalysis/UnsafeBufferReachableAnalysisTest.cpp index 64486d1a22226..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; @@ -389,4 +408,379 @@ TEST_F(UnsafeBufferReachableAnalysisTest, MultipleStartersLeaves) { EXPECT_TRUE(Reachables.count({'d', 1})); } +// 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
