Debian Codegraph @

share/analysis-scripts/estimate_difficulty.py

raw
1 #!/usr/bin/env python3
2 # -*- coding: utf-8 -*-
3 ##########################################################################
4 # #
5 # This file is part of Frama-C. #
6 # #
7 # Copyright (C) 2007-2022 #
8 # CEA (Commissariat à l'énergie atomique et aux énergies #
9 # alternatives) #
10 # #
11 # you can redistribute it and/or modify it under the terms of the GNU #
12 # Lesser General Public License as published by the Free Software #
13 # Foundation, version 2.1. #
14 # #
15 # It is distributed in the hope that it will be useful, #
16 # but WITHOUT ANY WARRANTY; without even the implied warranty of #
17 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the #
18 # GNU Lesser General Public License for more details. #
19 # #
20 # See the GNU Lesser General Public License version 2.1 #
21 # for more details (enclosed in the file licenses/LGPLv2.1). #
22 # #
23 ##########################################################################
24
25 """This script uses several heuristics to try and estimate the difficulty
26 of analyzing a new code base with Frama-C."""
27
28 import argparse
29 import json
30 import os
31 from pathlib import Path
32 import re
33 import subprocess
34 import tempfile
35
36 import build_callgraph
37 import source_filter
38
39 # TODO : avoid relativizing paths when introducing too many ".." ;
40 # TODO : accept directory as argument (--full-tree), and then do glob **/*.{c,i} inside
41 # TODO : try to check the presence of compiler builtins
42 # TODO : try to check for pragmas
43 # TODO : detect absence of 'main' function (library)
44
45 parser = argparse.ArgumentParser(
46 description="""
47 Estimates the difficulty of analyzing a given code base"""
48 )
49 parser.add_argument(
50 "--header-dirs",
51 "-d",
52 metavar="DIR",
53 nargs="+",
54 help="directories containing headers (default: .frama-c)",
55 )
56 parser.add_argument("files", nargs="+", help="source files")
57 args = vars(parser.parse_args())
58
59 header_dirs = args["header_dirs"]
60 if not header_dirs:
61 header_dirs = []
62 files = args["files"]
63
64 under_test = os.getenv("PTESTS_TESTING")
65
66 # gather information from several sources
67
68
69 def extract_keys(l):
70 return [list(key.keys())[0] for key in l]
71
72
73 def get_framac_libc_function_statuses(framac, framac_share):
74 if framac:
75 (_handler, metrics_tmpfile) = tempfile.mkstemp(prefix="fc_script_est_diff", suffix=".json")
76 if debug:
77 print("metrics_tmpfile: %s", metrics_tmpfile)
78 fc_runtime = framac_share / "libc" / "__fc_runtime.c"
79 fc_libc_headers = framac_share / "libc" / "__fc_libc.h"
80 subprocess.run(
81 [
82 framac,
83 "-no-autoload-plugins",
84 fc_runtime,
85 fc_libc_headers,
86 "-load-module",
87 "metrics",
88 "-metrics",
89 "-metrics-libc",
90 "-metrics-output",
91 metrics_tmpfile,
92 ],
93 stdout=subprocess.DEVNULL,
94 check=True,
95 )
96 with open(metrics_tmpfile) as f:
97 metrics_json = json.load(f)
98 os.remove(metrics_tmpfile)
99 else:
100 with open(framac_share / "libc_metrics.json") as f:
101 metrics_json = json.load(f)
102 defined = extract_keys(metrics_json["defined-functions"])
103 spec_only = extract_keys(metrics_json["specified-only-functions"])
104 return (defined, spec_only)
105
106
107 re_include = re.compile(r'\s*#\s*include\s*("|<)([^">]+)("|>)')
108
109
110 def grep_includes_in_file(filename):
111 file_content = source_filter.open_and_filter(filename, not under_test)
112 i = 0
113 for line in file_content.splitlines():
114 i += 1
115 m = re_include.match(line)
116 if m:
117 kind = m.group(1)
118 header = m.group(2)
119 yield (i, kind, header)
120
121
122 def get_includes(files):
123 quote_includes = {}
124 chevron_includes = {}
125 for filename in files:
126 for line, kind, header in grep_includes_in_file(filename):
127 if kind == "<":
128 includes = chevron_includes[header] if header in chevron_includes else []
129 else:
130 includes = quote_includes[header] if header in quote_includes else []
131 includes.append((filename, line))
132 if kind == "<":
133 chevron_includes[header] = includes
134 else:
135 quote_includes[header] = includes
136 return chevron_includes, quote_includes
137
138
139 debug = os.getenv("DEBUG")
140 verbose = False
141
142 framac_bin = os.getenv("FRAMAC_BIN")
143 if not framac_bin:
144 print(
145 "Running script in no-Frama-C mode (set FRAMAC_BIN to the directory containing frama-c if you want to use it)."
146 )
147 framac = None
148 script_dir = os.path.dirname(os.path.realpath(__file__))
149 framac_share = Path(script_dir) / "share"
150 else:
151 framac = Path(framac_bin) / "frama-c"
152 framac_share = Path(
153 subprocess.check_output([framac, "-no-autoload-plugins", "-print-share-path"]).decode()
154 )
155
156 print("Building callgraph...")
157 cg = build_callgraph.compute(files)
158
159 print("Computing data about libc/POSIX functions...")
160 libc_defined_functions, libc_specified_functions = get_framac_libc_function_statuses(
161 framac, framac_share
162 )
163
164 with open(framac_share / "compliance" / "c11_functions.json", encoding="utf-8") as f:
165 c11_functions = json.load(f)["data"]
166
167 with open(framac_share / "compliance" / "c11_headers.json", encoding="utf-8") as f:
168 c11_headers = json.load(f)["data"]
169
170 with open(framac_share / "compliance" / "posix_identifiers.json", encoding="utf-8") as f:
171 all_data = json.load(f)
172 posix_identifiers = all_data["data"]
173 posix_headers = all_data["headers"]
174
175 recursive_cycles = []
176 reported_recursive_pairs = set()
177 build_callgraph.compute_recursive_cycles(cg, recursive_cycles)
178 for (cycle_start_loc, cycle) in recursive_cycles:
179 # Note: in larger code bases, many cycles are reported for the same final
180 # function (e.g. for the calls 'g -> g', we may have 'f -> g -> g',
181 # 'h -> g -> g', etc; to minimize this, we print just the first one.
182 # This does not prevent 3-cycle repetitions, such as 'f -> g -> f',
183 # but these are less common.
184 if cycle[-1] in reported_recursive_pairs:
185 continue
186 reported_recursive_pairs.add(cycle[-1])
187 (filename, line) = cycle_start_loc
188 (x, y) = cycle[0]
189 pretty_cycle = f"{x} -> {y}"
190 for (x, y) in cycle[1:]:
191 pretty_cycle += f" -> {y}"
192 print(f"[recursion] found recursive cycle near {filename}:{line}: {pretty_cycle}")
193
194 callees = [callee for (_, callee) in list(cg.edges.keys())]
195 callees = set(callees)
196 used_headers = set()
197 print(f"Estimating difficulty for {len(callees)} function calls...")
198 warnings = 0
199
200 for callee in sorted(callees):
201
202 def callee_status(status, standard, reason):
203 global warnings
204 if status == "warning":
205 warnings += 1
206 if verbose or debug or status == "warning":
207 print(f"- {status}: {callee} ({standard}) {reason}")
208
209 try:
210 is_problematic = posix_identifiers[callee]["notes"]["fc-support"] == "problematic"
211 except KeyError:
212 is_problematic = False
213 if callee in posix_identifiers:
214 used_headers.add(posix_identifiers[callee]["header"])
215 status_emitted = False # to avoid re-emitting a message for functions in both C11 and POSIX
216 if callee in c11_functions:
217 standard = "C11"
218 # check that the callee is not a macro or type (e.g. va_arg);
219 # a few functions, such as strcpy_s, are in C11 but not in POSIX,
220 # so we must test membership before checking the POSIX type
221 if callee in posix_identifiers and posix_identifiers[callee]["id_type"] != "function":
222 continue
223 if (not is_problematic) and callee in libc_specified_functions:
224 callee_status("good", standard, "is specified in Frama-C's libc")
225 status_emitted = True
226 elif (not is_problematic) and callee in libc_defined_functions:
227 callee_status("ok", standard, "is defined in Frama-C's libc")
228 status_emitted = True
229 else:
230 if callee not in posix_identifiers:
231 callee_status("warning", standard, "has neither code nor spec in Frama-C's libc")
232 status_emitted = True
233 if not status_emitted and callee in posix_identifiers:
234 standard = "POSIX"
235 # check that the callee is not a macro or type (e.g. va_arg)
236 if posix_identifiers[callee]["id_type"] != "function":
237 continue
238 if (not is_problematic) and callee in libc_specified_functions:
239 callee_status("good", standard, "specified in Frama-C's libc")
240 status_emitted = True
241 elif (not is_problematic) and callee in libc_defined_functions:
242 callee_status("ok", standard, "defined in Frama-C's libc")
243 status_emitted = True
244 else:
245 # Some functions without specification are actually variadic
246 # (and possibly handled by the Variadic plug-in)
247 if "notes" in posix_identifiers[callee]:
248 if "variadic-plugin" in posix_identifiers[callee]["notes"]:
249 callee_status("ok", standard, "is handled by the Variadic plug-in")
250 status_emitted = True
251 elif is_problematic:
252 callee_status(
253 "warning",
254 standard,
255 "is known to be problematic for code analysis",
256 )
257 status_emitted = True
258 if not status_emitted:
259 callee_status("warning", standard, "has neither code nor spec in Frama-C's libc")
260
261 print(f"Function-related warnings: {warnings}")
262
263 if (verbose or debug) and used_headers:
264 print("used headers:")
265 for header in sorted(used_headers):
266 print(f" <{header}>")
267
268 (chevron_includes, quote_includes) = get_includes(files)
269
270
271 def is_local_header(header_dirs, header):
272 for d in header_dirs:
273 path = Path(d)
274 if Path(path / header).exists():
275 return True
276 return False
277
278
279 print(f"Estimating difficulty for {len(chevron_includes)} '#include <header>' directives...")
280 non_posix_headers = []
281 header_warnings = 0
282 for header in sorted(chevron_includes, key=str.casefold):
283 if header in posix_headers:
284 fc_support = posix_headers[header]["fc-support"]
285 if fc_support == "unsupported":
286 header_warnings += 1
287 print(f"- WARNING: included header <{header}> is explicitly unsupported by Frama-C")
288 else:
289 if verbose or debug:
290 c11_or_posix = "C11" if header in c11_headers else "POSIX"
291 print(f"- note: included {c11_or_posix} header ")
292 else:
293 if is_local_header(header_dirs, header):
294 if verbose or debug:
295 print(f"- ok: included header <{header}> seems to be available locally")
296 else:
297 non_posix_headers.append(header)
298 header_warnings += 1
299 print(f"- warning: included non-POSIX header <{header}>")
300 print(f"Header-related warnings: {header_warnings}")
301
302
303 # dynamic allocation
304
305 dynalloc_functions = set(["malloc", "calloc", "free", "realloc", "alloca", "mmap"])
306 dyncallees = dynalloc_functions.intersection(callees)
307 if dyncallees:
308 print(f"- note: calls to dynamic allocation functions: {', '.join(sorted(dyncallees))}")
309
310
311 # unsupported C11-specific features
312
313 c11_unsupported = [
314 "_Alignas",
315 "_Alignof",
316 "_Complex",
317 "_Generic",
318 "_Imaginary",
319 "alignas",
320 "alignof", # stdalign.h may use these symbols
321 ]
322
323 for keyword in c11_unsupported:
324 out = subprocess.Popen(
325 ["grep", "-n", "\\b" + keyword + "\\b"] + files + ["/dev/null"],
326 stdout=subprocess.PIPE,
327 stderr=subprocess.STDOUT,
328 )
329 lines = out.communicate()[0].decode("utf-8").splitlines()
330 if lines:
331 n = len(lines)
332 print(
333 f"- warning: found {n} line{'s' if n > 1 else ''} with occurrences of "
334 f"unsupported C11 construct '{keyword}'"
335 )
336
337 # assembly code
338
339 if "asm" in callees or "__asm" in callees or "__asm__" in callees:
340 print("- warning: code seems to contain inline assembly ('asm(...)')")