netdev - Re: [PATCH bpf-next 4/4] bpf: add self-check logic to liveness analysis

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]

Message-ID: <20181213043739.etbcowzxedevlsoy@ast-mbp.dhcp.thefacebook.com>
Date:   Wed, 12 Dec 2018 20:37:40 -0800
From:   Alexei Starovoitov <alexei.starovoitov@...il.com>
To:     Jakub Kicinski <jakub.kicinski@...ronome.com>
Cc:     Alexei Starovoitov <ast@...nel.org>,
        "David S . Miller" <davem@...emloft.net>, daniel@...earbox.net,
        ecree@...arflare.com, jiong.wang@...ronome.com,
        netdev@...r.kernel.org, kernel-team@...com
Subject: Re: [PATCH bpf-next 4/4] bpf: add self-check logic to liveness
 analysis

On Wed, Dec 12, 2018 at 05:21:35PM -0800, Jakub Kicinski wrote:
> On Tue, 11 Dec 2018 21:28:54 -0800, Alexei Starovoitov wrote:
> > 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>
> 
> > @@ -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;
> 
> Perhaps return; here?  Seeing any "done" flag in the state entry
> implies all regs and stack slots are "done", no?  Or even check if
> there are any DONE flags in clean_verifier_state() before the loop?

good idea. will do.

> > +		/* 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
> > + */
> 
> Little bike shedding - if I understand Ed's comment I feel the same way
> about "any state we see must be fully done".  Different call sites are
> logically different state lists in my mind, we effectively "inline" the
> functions in the verifier walk... 

yes, they are logically different, but implementation is only one state
list per insn. So comparing callsites is the "filter" of logical lists.