netdev - [RFC PATCH 12/16] bpf: cfg: pretty print CFG and DOM

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Fri, 01 Jun 2018 02:33:19 -0700
From:   John Fastabend <john.fastabend@...il.com>
To:     alexei.starovoitov@...il.com, daniel@...earbox.net,
        davem@...emloft.net
Cc:     netdev@...r.kernel.org
Subject: [RFC PATCH 12/16] bpf: cfg: pretty print CFG and DOM

Add functions to pretty print the CFG and DOM table. We can also
add contrib scripts to print this dot format so tools can visualize
them. I at least found this helpful. Will add scripts in tools/bpf
follow up patch.

For development we are always printing these but should put these
noisy routines behind a verbose bit and/or only print when an error
has occured in bounded-loop logic.

Signed-off-by: John Fastabend <john.fastabend@...il.com>
---
 kernel/bpf/cfg.c      |   54 +++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/cfg.h      |    5 +++++
 kernel/bpf/verifier.c |    2 ++
 3 files changed, 61 insertions(+)

diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
index c67541c..0d50646 100644
--- a/kernel/bpf/cfg.c
+++ b/kernel/bpf/cfg.c
@@ -62,6 +62,60 @@ static struct bb_node *bb_next(struct cfg_node_allocator *allocator,
 	return (struct bb_node *)cfg_node_delink(allocator, &bb->link);
 }
 
+void cfg_pretty_print(struct bpf_verifier_env *env,
+		      struct cfg_node_allocator *allocator,
+		      struct bpf_subprog_info *subprog)
+{
+	void **bb_list = (void **)&subprog->bbs;
+	struct bb_node *bb, *exit_bb;
+
+	bb = entry_bb(bb_list);
+	exit_bb = exit_bb(bb_list);
+
+	bpf_verifier_log_write(env, "CFG: ");
+	while (bb && bb != exit_bb) {
+		struct bb_node *next_bb = bb_next(allocator, bb);
+		struct edge_node *e;
+
+		e = cfg_node_delink(allocator, &bb->e_succs);
+		while (e) {
+			struct bb_node *dst = e->dst;
+			int tail = next_bb->head - 1;
+			struct bb_node *dst_next;
+			int dst_tail;
+
+			dst_next = bb_next(allocator, dst);
+			dst_tail = dst_next ? dst_next->head - 1 : 65534;
+
+			bpf_verifier_log_write(env, " %i[%i,%i] -> %i[%i,%i] ",
+					       bb->idx, bb->head, tail, dst->idx, dst->head, dst_tail);
+			e = cfg_node_delink(allocator, &e->link);
+		}
+		bb = bb_next(allocator, bb);
+	}
+	bpf_verifier_log_write(env, "\n");
+}
+
+void dom_pretty_print(struct bpf_verifier_env *env,
+		      struct bpf_subprog_info *subprog)
+{
+	int lane_len, bb_num = subprog->bb_num - 2;
+	int i, j;
+
+	lane_len = BITS_TO_LONGS(bb_num);
+
+	bpf_verifier_log_write(env, "DOM:\n");
+	for (i = 0; i < bb_num; i++) {
+		for (j = 0; j < bb_num; j++) {
+			bpf_verifier_log_write(env, " %i ",
+			    test_bit(j,
+				     subprog->dtree + i * lane_len) ? 1 : 0);
+		}
+		bpf_verifier_log_write(env, "\n");
+	}
+	bpf_verifier_log_write(env, "\n");
+}
+
 struct dom_info {
 	u16 *dfs_parent;
 	u16 *dfs_order;
diff --git a/kernel/bpf/cfg.h b/kernel/bpf/cfg.h
index 8363406..44dcabb 100644
--- a/kernel/bpf/cfg.h
+++ b/kernel/bpf/cfg.h
@@ -37,6 +37,11 @@ bool subprog_has_loop(struct cfg_node_allocator *allocator,
 		      struct bpf_subprog_info *subprog);
 int subprog_has_irreduciable_loop(struct cfg_node_allocator *allocator,
 				  struct bpf_subprog_info *subprog);
+void cfg_pretty_print(struct bpf_verifier_env *env,
+		      struct cfg_node_allocator *allocator,
+		      struct bpf_subprog_info *subprog);
+void dom_pretty_print(struct bpf_verifier_env *env,
+		      struct bpf_subprog_info *subprog);
 int subprog_init_bb(struct cfg_node_allocator *allocator, void **bb_list,
 		    int subprog_start, int subprog_end);
 void subprog_free(struct bpf_subprog_info *subprog, int end_idx);
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 49895f3..610559a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -913,6 +913,8 @@ static int check_subprogs(struct bpf_verifier_env *env)
 						     &subprog[cur_subprog]);
 			if (ret < 0)
 				goto free_nodes;
+			cfg_pretty_print(env, &allocator, &subprog[cur_subprog]);
+			dom_pretty_print(env, &subprog[cur_subprog]);
 			ret = subprog_has_irreduciable_loop(&allocator,
 							&subprog[cur_subprog]);
 			if (ret < 0)