Branch data Line data Source code
1 : : /* Modeling API uses and misuses via state machines.
2 : : Copyright (C) 2019-2025 Free Software Foundation, Inc.
3 : : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it
8 : : under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but
13 : : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : : General Public License for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : #ifndef GCC_ANALYZER_SM_H
22 : : #define GCC_ANALYZER_SM_H
23 : :
24 : : /* Utility functions for use by state machines. */
25 : :
26 : : namespace ana {
27 : :
28 : : class state_machine;
29 : : class sm_context;
30 : : class pending_diagnostic;
31 : : class analyzer_state_graph;
32 : :
33 : : extern bool any_pointer_p (tree expr);
34 : : extern bool any_pointer_p (const svalue *sval);
35 : :
36 : : /* An abstract base class for a state machine describing an API.
37 : : Manages a set of state objects, and has various virtual functions
38 : : for pattern-matching on statements. */
39 : :
40 : : class state_machine : public log_user
41 : : {
42 : : public:
43 : : /* States are represented by immutable objects, owned by the state
44 : : machine. */
45 : : class state
46 : : {
47 : : public:
48 : 181724 : state (const char *name, unsigned id) : m_name (name), m_id (id) {}
49 : 135681 : virtual ~state () {}
50 : :
51 : 6304 : const char *get_name () const { return m_name; }
52 : : virtual void dump_to_pp (pretty_printer *pp) const;
53 : : virtual std::unique_ptr<json::value> to_json () const;
54 : :
55 : 11241248 : unsigned get_id () const { return m_id; }
56 : :
57 : : private:
58 : : const char *m_name;
59 : : unsigned m_id;
60 : : };
61 : : typedef const state_machine::state *state_t;
62 : :
63 : : state_machine (const char *name, logger *logger);
64 : 23183 : virtual ~state_machine () {}
65 : :
66 : : /* Should states be inherited from a parent region to a child region,
67 : : when first accessing a child region?
68 : : For example we should inherit the taintedness of a subregion,
69 : : but we should not inherit the "malloc:non-null" state of a field
70 : : within a heap-allocated struct. */
71 : : virtual bool inherited_state_p () const = 0;
72 : :
73 : : /* A vfunc for more general handling of inheritance. */
74 : : virtual state_t
75 : 6596477 : alt_get_inherited_state (const sm_state_map &,
76 : : const svalue *,
77 : : const extrinsic_state &) const
78 : : {
79 : 6596477 : return nullptr;
80 : : }
81 : :
82 : : virtual bool
83 : 3530310 : has_alt_get_inherited_state_p () const
84 : : {
85 : 3530310 : return false;
86 : : }
87 : :
88 : 4356226 : virtual state_machine::state_t get_default_state (const svalue *) const
89 : : {
90 : 4356226 : return m_start;
91 : : }
92 : :
93 : 2710857 : const char *get_name () const { return m_name; }
94 : :
95 : : state_t get_state_by_name (const char *name) const;
96 : :
97 : : /* Return true if STMT is a function call recognized by this sm. */
98 : : virtual bool on_stmt (sm_context &sm_ctxt,
99 : : const supernode *node,
100 : : const gimple *stmt) const = 0;
101 : :
102 : 144126 : virtual void on_phi (sm_context &sm_ctxt ATTRIBUTE_UNUSED,
103 : : const supernode *node ATTRIBUTE_UNUSED,
104 : : const gphi *phi ATTRIBUTE_UNUSED,
105 : : tree rhs ATTRIBUTE_UNUSED) const
106 : : {
107 : 144126 : }
108 : :
109 : 90606 : virtual void on_condition (sm_context &sm_ctxt ATTRIBUTE_UNUSED,
110 : : const supernode *node ATTRIBUTE_UNUSED,
111 : : const gimple *stmt ATTRIBUTE_UNUSED,
112 : : const svalue *lhs ATTRIBUTE_UNUSED,
113 : : enum tree_code op ATTRIBUTE_UNUSED,
114 : : const svalue *rhs ATTRIBUTE_UNUSED) const
115 : : {
116 : 90606 : }
117 : :
118 : : virtual void
119 : 37416 : on_bounded_ranges (sm_context &sm_ctxt ATTRIBUTE_UNUSED,
120 : : const supernode *node ATTRIBUTE_UNUSED,
121 : : const gimple *stmt ATTRIBUTE_UNUSED,
122 : : const svalue &sval ATTRIBUTE_UNUSED,
123 : : const bounded_ranges &ranges ATTRIBUTE_UNUSED) const
124 : : {
125 : 37416 : }
126 : :
127 : : virtual void
128 : 140856 : on_pop_frame (sm_state_map *smap ATTRIBUTE_UNUSED,
129 : : const frame_region *frame_reg ATTRIBUTE_UNUSED) const
130 : : {
131 : 140856 : }
132 : :
133 : : /* Return true if it safe to discard the given state (to help
134 : : when simplifying state objects).
135 : : States that need leak detection should return false. */
136 : : virtual bool can_purge_p (state_t s) const = 0;
137 : :
138 : : /* Called when VAR leaks (and !can_purge_p). */
139 : : virtual std::unique_ptr<pending_diagnostic>
140 : : on_leak (tree var ATTRIBUTE_UNUSED,
141 : : const program_state *old_state,
142 : : const program_state *new_state) const;
143 : :
144 : : /* Return true if S should be reset to "start" for values passed (or reachable
145 : : from) calls to unknown functions. IS_MUTABLE is true for pointers as
146 : : non-const, false if only passed as const-pointers.
147 : :
148 : : For example, in sm-malloc.cc, an on-stack ptr doesn't stop being
149 : : stack-allocated when passed to an unknown fn, but a malloc-ed pointer
150 : : could be freed when passed to an unknown fn (unless passed as "const"). */
151 : 2791 : virtual bool reset_when_passed_to_unknown_fn_p (state_t s ATTRIBUTE_UNUSED,
152 : : bool is_mutable) const
153 : : {
154 : 2791 : return is_mutable;
155 : : }
156 : :
157 : : /* Attempt to get a state for the merger of STATE_A and STATE_B,
158 : : or return nullptr if merging shouldn't occur, so that differences
159 : : between sm-state will lead to separate exploded nodes.
160 : :
161 : : Most state machines will only merge equal states, but can
162 : : override maybe_get_merged_states_nonequal to support mergers
163 : : of certain non-equal states. */
164 : 484556 : state_t maybe_get_merged_state (state_t state_a,
165 : : state_t state_b) const
166 : : {
167 : 484556 : if (state_a == state_b)
168 : : return state_a;
169 : 197951 : return maybe_get_merged_states_nonequal (state_a, state_b);
170 : : }
171 : :
172 : : /* Base implementation of hook for maybe_get_merged_state on non-equal
173 : : states. */
174 : : virtual state_t
175 : 15901 : maybe_get_merged_states_nonequal (state_t state_a ATTRIBUTE_UNUSED,
176 : : state_t state_b ATTRIBUTE_UNUSED) const
177 : : {
178 : : /* By default, non-equal sm states should inhibit merger of enodes. */
179 : 15901 : return nullptr;
180 : : }
181 : :
182 : : void validate (state_t s) const;
183 : :
184 : : void dump_to_pp (pretty_printer *pp) const;
185 : :
186 : : std::unique_ptr<json::object> to_json () const;
187 : :
188 : 16903 : state_t get_start_state () const { return m_start; }
189 : :
190 : : virtual void
191 : : add_state_to_state_graph (analyzer_state_graph &out_state_graph,
192 : : const svalue &sval,
193 : : state_machine::state_t state) const;
194 : :
195 : : virtual void
196 : : add_global_state_to_state_graph (analyzer_state_graph &out_state_graph,
197 : : state_machine::state_t state) const;
198 : :
199 : : protected:
200 : : state_t add_state (const char *name);
201 : 46039 : state_t add_custom_state (state *s)
202 : : {
203 : 46039 : m_states.safe_push (s);
204 : 2659 : return s;
205 : : }
206 : :
207 : 181704 : unsigned alloc_state_id () { return m_next_state_id++; }
208 : :
209 : : private:
210 : : DISABLE_COPY_AND_ASSIGN (state_machine);
211 : :
212 : : const char *m_name;
213 : :
214 : : /* States are owned by the state_machine. */
215 : : auto_delete_vec<state> m_states;
216 : :
217 : : unsigned m_next_state_id;
218 : :
219 : : protected:
220 : : /* Must be inited after m_next_state_id. */
221 : : state_t m_start;
222 : : };
223 : :
224 : : /* Abstract base class for state machines to pass to
225 : : sm_context::on_custom_transition for handling non-standard transitions
226 : : (e.g. adding a node and edge to simulate registering a callback and having
227 : : the callback be called later). */
228 : :
229 : 10 : class custom_transition
230 : : {
231 : : public:
232 : 10 : virtual ~custom_transition () {}
233 : : virtual void impl_transition (exploded_graph *eg,
234 : : exploded_node *src_enode,
235 : : int sm_idx) = 0;
236 : : };
237 : :
238 : : /* Abstract base class giving an interface for the state machine to call
239 : : the checker engine, at a particular stmt. */
240 : :
241 : : class sm_context
242 : : {
243 : : public:
244 : 2310419 : virtual ~sm_context () {}
245 : :
246 : : /* Get the fndecl used at call, or NULL_TREE.
247 : : Use in preference to gimple_call_fndecl (and gimple_call_addr_fndecl),
248 : : since it can look through function pointer assignments and
249 : : other callback handling. */
250 : : virtual tree get_fndecl_for_call (const gcall &call) = 0;
251 : :
252 : : /* Get the old state of VAR at STMT. */
253 : : virtual state_machine::state_t get_state (const gimple *stmt,
254 : : tree var) = 0;
255 : : virtual state_machine::state_t get_state (const gimple *stmt,
256 : : const svalue *) = 0;
257 : : /* Set the next state of VAR to be TO, recording the "origin" of the
258 : : state as ORIGIN.
259 : : Use STMT for location information. */
260 : : virtual void set_next_state (const gimple *stmt,
261 : : tree var,
262 : : state_machine::state_t to,
263 : : tree origin = NULL_TREE) = 0;
264 : : virtual void set_next_state (const gimple *stmt,
265 : : const svalue *var,
266 : : state_machine::state_t to,
267 : : tree origin = NULL_TREE) = 0;
268 : :
269 : : /* Called by state_machine in response to pattern matches:
270 : : if VAR is in state FROM, transition it to state TO, potentially
271 : : recording the "origin" of the state as ORIGIN.
272 : : Use NODE and STMT for location information. */
273 : 10078 : void on_transition (const supernode *node ATTRIBUTE_UNUSED,
274 : : const gimple *stmt,
275 : : tree var,
276 : : state_machine::state_t from,
277 : : state_machine::state_t to,
278 : : tree origin = NULL_TREE)
279 : : {
280 : 10078 : state_machine::state_t current = get_state (stmt, var);
281 : 10078 : if (current == from)
282 : 1568 : set_next_state (stmt, var, to, origin);
283 : 10078 : }
284 : :
285 : 37635 : void on_transition (const supernode *node ATTRIBUTE_UNUSED,
286 : : const gimple *stmt,
287 : : const svalue *var,
288 : : state_machine::state_t from,
289 : : state_machine::state_t to,
290 : : tree origin = NULL_TREE)
291 : : {
292 : 37635 : state_machine::state_t current = get_state (stmt, var);
293 : 37635 : if (current == from)
294 : 687 : set_next_state (stmt, var, to, origin);
295 : 37635 : }
296 : :
297 : : /* Called by state_machine in response to pattern matches:
298 : : issue a diagnostic D using NODE and STMT for location information. */
299 : : virtual void warn (const supernode *node, const gimple *stmt,
300 : : tree var,
301 : : std::unique_ptr<pending_diagnostic> d) = 0;
302 : : virtual void warn (const supernode *node, const gimple *stmt,
303 : : const svalue *var,
304 : : std::unique_ptr<pending_diagnostic> d) = 0;
305 : :
306 : : /* For use when generating trees when creating pending_diagnostics, so that
307 : : rather than e.g.
308 : : "double-free of '<unknown>'"
309 : : we can print:
310 : : "double-free of 'inbuf.data'". */
311 : 0 : virtual tree get_diagnostic_tree (tree expr)
312 : : {
313 : 0 : return expr;
314 : : }
315 : : virtual tree get_diagnostic_tree (const svalue *) = 0;
316 : :
317 : : virtual state_machine::state_t get_global_state () const = 0;
318 : : virtual void set_global_state (state_machine::state_t) = 0;
319 : :
320 : : virtual void clear_all_per_svalue_state () = 0;
321 : :
322 : : /* A vfunc for handling custom transitions, such as when registering
323 : : a signal handler. */
324 : : virtual void on_custom_transition (custom_transition *transition) = 0;
325 : :
326 : : /* If STMT is an assignment known to assign zero to its LHS, return
327 : : the LHS.
328 : : Otherwise return NULL_TREE. */
329 : : virtual tree is_zero_assignment (const gimple *stmt) = 0;
330 : :
331 : 0 : virtual path_context *get_path_context () const
332 : : {
333 : 0 : return nullptr;
334 : : }
335 : :
336 : : /* Are we handling an external function with unknown side effects? */
337 : 0 : virtual bool unknown_side_effects_p () const { return false; }
338 : :
339 : : virtual const program_state *get_old_program_state () const = 0;
340 : : virtual const program_state *get_new_program_state () const = 0;
341 : :
342 : : const region_model *get_old_region_model () const;
343 : :
344 : : protected:
345 : 2311197 : sm_context (int sm_idx, const state_machine &sm)
346 : 2311197 : : m_sm_idx (sm_idx), m_sm (sm) {}
347 : :
348 : : int m_sm_idx;
349 : : const state_machine &m_sm;
350 : : };
351 : :
352 : :
353 : : /* The various state_machine subclasses are hidden in their respective
354 : : implementation files. */
355 : :
356 : : extern std::vector<std::unique_ptr<state_machine>>
357 : : make_checkers (logger *logger);
358 : :
359 : : extern std::unique_ptr<state_machine> make_malloc_state_machine (logger *);
360 : : extern std::unique_ptr<state_machine> make_fileptr_state_machine (logger *);
361 : : extern std::unique_ptr<state_machine> make_taint_state_machine (logger *);
362 : : extern std::unique_ptr<state_machine> make_sensitive_state_machine (logger *);
363 : : extern std::unique_ptr<state_machine> make_signal_state_machine (logger *);
364 : : extern std::unique_ptr<state_machine> make_pattern_test_state_machine (logger *);
365 : : extern std::unique_ptr<state_machine> make_va_list_state_machine (logger *);
366 : : extern std::unique_ptr<state_machine> make_fd_state_machine (logger *);
367 : :
368 : : } // namespace ana
369 : :
370 : : #endif /* GCC_ANALYZER_SM_H */
|