| 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
| ||
|
Date: Tue, 11 Dec 2018 21:28:54 -0800
From: Alexei Starovoitov <ast@...nel.org>
To: "David S . Miller" <davem@...emloft.net>
CC: <daniel@...earbox.net>, <ecree@...arflare.com>,
<jakub.kicinski@...ronome.com>, <jiong.wang@...ronome.com>,
<netdev@...r.kernel.org>, <kernel-team@...com>
Subject: [PATCH bpf-next 4/4] bpf: add self-check logic to liveness analysis
introduce REG_LIVE_DONE to check the liveness propagation
and prepare the states for merging
See algorithm description in clean_live_states().
No difference in tests.
Signed-off-by: Alexei Starovoitov <ast@...nel.org>
---
include/linux/bpf_verifier.h | 1 +
kernel/bpf/verifier.c | 108 ++++++++++++++++++++++++++++++++++-
2 files changed, 108 insertions(+), 1 deletion(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index c736945be7c5..07a55073c809 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -38,6 +38,7 @@ enum bpf_reg_liveness {
REG_LIVE_NONE = 0, /* reg hasn't been read or written this branch */
REG_LIVE_READ, /* reg was read, so we're sensitive to initial value */
REG_LIVE_WRITTEN, /* reg was written first, screening off later reads */
+ REG_LIVE_DONE = 4, /* liveness won't be updating this register anymore */
};
struct bpf_reg_state {
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6e5ea4c4d8e7..9da0b3f8342a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -339,12 +339,14 @@ static char slot_type_char[] = {
static void print_liveness(struct bpf_verifier_env *env,
enum bpf_reg_liveness live)
{
- if (live & (REG_LIVE_READ | REG_LIVE_WRITTEN))
+ if (live & (REG_LIVE_READ | REG_LIVE_WRITTEN | REG_LIVE_DONE))
verbose(env, "_");
if (live & REG_LIVE_READ)
verbose(env, "r");
if (live & REG_LIVE_WRITTEN)
verbose(env, "w");
+ if (live & REG_LIVE_DONE)
+ verbose(env, "D");
}
static struct bpf_func_state *func(struct bpf_verifier_env *env,
@@ -1074,6 +1076,12 @@ static int mark_reg_read(struct bpf_verifier_env *env,
/* if read wasn't screened by an earlier write ... */
if (writes && state->live & REG_LIVE_WRITTEN)
break;
+ if (parent->live & REG_LIVE_DONE) {
+ verbose(env, "verifier BUG type %s var_off %lld off %d\n",
+ reg_type_str[parent->type],
+ parent->var_off.value, parent->off);
+ return -EFAULT;
+ }
/* ... then we depend on parent's value */
parent->live |= REG_LIVE_READ;
state = parent;
@@ -5021,6 +5029,102 @@ static bool check_ids(u32 old_id, u32 cur_id, struct idpair *idmap)
return false;
}
+static void clean_func_state(struct bpf_verifier_env *env,
+ struct bpf_func_state *st)
+{
+ enum bpf_reg_liveness live;
+ int i, j;
+
+ for (i = 0; i < BPF_REG_FP; i++) {
+ live = st->regs[i].live;
+ if (live & REG_LIVE_DONE)
+ continue;
+ /* liveness must not touch this register anymore */
+ st->regs[i].live |= REG_LIVE_DONE;
+ if (!(live & REG_LIVE_READ))
+ /* since the register is unused, clear its state
+ * to make further comparison simpler
+ */
+ __mark_reg_not_init(&st->regs[i]);
+ }
+
+ for (i = 0; i < st->allocated_stack / BPF_REG_SIZE; i++) {
+ live = st->stack[i].spilled_ptr.live;
+ if (live & REG_LIVE_DONE)
+ continue;
+ /* liveness must not touch this stack slot anymore */
+ st->stack[i].spilled_ptr.live |= REG_LIVE_DONE;
+ if (!(live & REG_LIVE_READ)) {
+ __mark_reg_not_init(&st->stack[i].spilled_ptr);
+ for (j = 0; j < BPF_REG_SIZE; j++)
+ st->stack[i].slot_type[j] = STACK_INVALID;
+ }
+ }
+}
+
+static void clean_verifier_state(struct bpf_verifier_env *env,
+ struct bpf_verifier_state *st)
+{
+ int i;
+
+ for (i = 0; i <= st->curframe; i++)
+ clean_func_state(env, st->frame[i]);
+}
+
+/* the parentage chains form a tree.
+ * the verifier states are added to state lists at given insn and
+ * pushed into state stack for future exploration.
+ * when the verifier reaches bpf_exit insn some of the verifer states
+ * stored in the state lists have their final liveness state already,
+ * but a lot of states will get revised from liveness point of view when
+ * the verifier explores other branches.
+ * Example:
+ * 1: r0 = 1
+ * 2: if r1 == 100 goto pc+1
+ * 3: r0 = 2
+ * 4: exit
+ * when the verifier reaches exit insn the register r0 in the state list of
+ * insn 2 will be seen as !REG_LIVE_READ. Then the verifier pops the other_branch
+ * of insn 2 and goes exploring further. At the insn 4 it will walk the
+ * parentage chain from insn 4 into insn 2 and will mark r0 as REG_LIVE_READ.
+ *
+ * Since the verifier pushes the branch states as it sees them while exploring
+ * the program the condition of walking the branch instruction for the second
+ * time means that all states below this branch were already explored and
+ * their final liveness markes are already propagated.
+ * Hence when the verifier completes the search of state list in is_state_visited()
+ * we can call this clean_live_states() function to mark all liveness states
+ * as REG_LIVE_DONE to indicate that 'parent' pointers of 'struct bpf_reg_state'
+ * will not be used.
+ * This function also clears the registers and stack for states that !READ
+ * to simplify state merging.
+ *
+ * Important note here that walking the same branch instruction in the callee
+ * doesn't meant that the states are DONE. The verifier has to compare
+ * the callsites
+ */
+static void clean_live_states(struct bpf_verifier_env *env, int insn,
+ struct bpf_verifier_state *cur)
+{
+ struct bpf_verifier_state_list *sl;
+ int i;
+
+ sl = env->explored_states[insn];
+ if (!sl)
+ return;
+
+ while (sl != STATE_LIST_MARK) {
+ if (sl->state.curframe != cur->curframe)
+ goto next;
+ for (i = 0; i <= cur->curframe; i++)
+ if (sl->state.frame[i]->callsite != cur->frame[i]->callsite)
+ goto next;
+ clean_verifier_state(env, &sl->state);
+next:
+ sl = sl->next;
+ }
+}
+
/* Returns true if (rold safe implies rcur safe) */
static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur,
struct idpair *idmap)
@@ -5354,11 +5458,13 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
err = propagate_liveness(env, &sl->state, cur);
if (err)
return err;
+ clean_live_states(env, insn_idx, cur);
return 1;
}
sl = sl->next;
states_cnt++;
}
+ clean_live_states(env, insn_idx, cur);
if (!env->allow_ptr_leaks && states_cnt > BPF_COMPLEXITY_LIMIT_STATES)
return 0;
--
2.17.1
Powered by blists - more mailing lists