| 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: Fri, 11 May 2018 16:11:30 +0100
From: Jiong Wang <jiong.wang@...ronome.com>
To: John Fastabend <john.fastabend@...il.com>,
alexei.starovoitov@...il.com, daniel@...earbox.net
Cc: netdev@...r.kernel.org, oss-drivers@...ronome.com
Subject: Re: [RFC bpf-next 04/10] bpf: cfg: detect loop use domination
information
On 10/05/2018 19:17, John Fastabend wrote:
> On 05/07/2018 03:22 AM, Jiong Wang wrote:
>> If one bb is dominating its predecessor, then there is loop.
>>
>> Signed-off-by: Jiong Wang <jiong.wang@...ronome.com>
>> ---
>> kernel/bpf/cfg.c | 22 ++++++++++++++++++++++
>> kernel/bpf/cfg.h | 1 +
>> kernel/bpf/verifier.c | 8 ++++++++
>> 3 files changed, 31 insertions(+)
>>
>> diff --git a/kernel/bpf/cfg.c b/kernel/bpf/cfg.c
>> index b50937a..90692e4 100644
>> --- a/kernel/bpf/cfg.c
>> +++ b/kernel/bpf/cfg.c
>> @@ -568,6 +568,28 @@ int subprog_build_dom_info(struct bpf_subprog_info *subprog)
>> return ret;
>> }
>>
>> +bool subprog_has_loop(struct bpf_subprog_info *subprog)
>> +{
>> + int lane_len = BITS_TO_LONGS(subprog->bb_num - 2);
>> + struct list_head *bb_list = &subprog->bbs;
>> + struct bb_node *bb, *entry_bb;
>> + struct edge_node *e;
>> +
>> + entry_bb = entry_bb(bb_list);
>> + bb = bb_next(entry_bb);
>> + list_for_each_entry_from(bb, &exit_bb(bb_list)->l, l)
>> + list_for_each_entry(e, &bb->e_prevs, l) {
>> + struct bb_node *latch = e->src;
>> +
>> + if (latch != entry_bb &&
>> + test_bit(bb->idx,
>> + subprog->dtree + latch->idx * lane_len))
>> + return true;
>> + }
>> +
>> + return false;
>> +}
>> +
> Because we are using this to guard against loops we need to detect
> all loops not just reducible loops. And because (assuming my understanding
> is correct) Tarjan's algorithm will only detect all loops when the
> graph is reducible we need additional tests.
Hi John,
Yes, the current DOM based loop detection can't detect irreducible loop.
And I feel both the first and second approaches you listed below are good,
might worth implementing both and measure which one is with less overhead.
I could give a try on approach 2. The alg given by Eric Stoltz might be a
good choice (https://compilers.iecc.com/comparch/article/94-01-053). We
have dom info now, so could do another DFS, and see if the head of one
back-edge doesn't dom the tail that there is multiple entries to the loop.
I guess the first approach is with less overhead as there is no existing
DFS pass to reuse after dom build that we need a new pass for approach 2.
Regards,
Jiong
>
> There are a couple options to fix this with varying levels of complexity.
> Because I'm using this to build loop info structures to find induction
> variables and show termination. After the loop structures are built we
> could search for any back-edges not in valid loops. This would be similar
> to the existing back-edge detection code but with an extra check to
> allow edges that have been validated. I would need to check that this
> doesn't have any escapes before actually proposing it though.
>
> The other method would be to properly test for reducibility using one of
> the algorithms for this. I think the most intuitive is to remove back-edges
> and test the graph is acyclic. This would be run before the dom tree is
> built. This is IMO what we should do, it seems the most "correct" way to
> do this.
>
> The most complex would be to handle irreducible programs using some of the
> more complex methods. I really don't think this is necessary but in theory
> at least we could use something like Havlak-Tarjan algorithm and allow
> some programs with irreducible loops. This is likely overkill especially
> in a first iteration.
>
> Here is a sample that fails without this series, using original back-edge
> detection, but is allowed with this patch,
>
> SEC("classifier_tc_mark")
> int _tc_mark(struct __sk_buff *ctx)
> {
> void *data = (void *)(unsigned long)ctx->data;
> void *data_end = (void *)(unsigned long)ctx->data_end;
> void *data_meta = (void *)(unsigned long)ctx->data_meta;
> struct meta_info *meta = data_meta;
> volatile int mark = ctx->mark;
>
> mark += 1;
>
> if (meta + 1 > data) {
> B:
> mark += 2;
>
> if (mark < ctx->mark * 3)
> goto C;
> } else if (meta < data) {
> C:
> mark += 1;
> if (mark < 1000)
> goto B;
> }
>
> return TC_ACT_OK;
> }
>
> A more concise example could be made but I just hacked on one of the
> sample programs. This generates the CFG as follows (I have a patch
> on top of your stack to print the CFG and DOM tables)
>
> CFG: 65535[-1,-1] -> 0[0,9] 0[0,9] -> 3[20,20] 0[0,9] -> 1[10,18] 1[10,18] -> 4[21,28] 1[10,18] -> 2[19,19] 2[19,19] -> 5[29,30] 3[20,20] -> 5[29,30] 3[20,20] -> 4[21,28] 4[21,28] -> 1[10,18] 4[21,28] -> 5[29,30] 5[29,30] -> 65534[31,65534]
> DOM:
> 1 0 0 0 0 0
> 1 1 0 0 0 0
> 1 1 1 0 0 0
> 1 0 0 1 0 0
> 1 0 0 0 1 0
> 1 0 0 0 0 1
>
>
> Here we have the loop 1[10,18]->4[21,28] and the back-edge 4[21,28]->1[10,18].
> The notation is #idx[head_insn,tail_insn]. The above can then be imported
> into dot notation and graphed if needed.
>
> Jiong, please verify this analysis is correct.
>
> Thanks,
> John
>
Powered by blists - more mailing lists