diff options
| author | Eduard Zingerman <eddyz87@gmail.com> | 2023-10-24 03:09:15 +0300 |
|---|---|---|
| committer | Alexei Starovoitov <ast@kernel.org> | 2023-10-23 21:49:32 -0700 |
| commit | 2a0992829ea3864939d917a5c7b48be6629c6217 (patch) | |
| tree | 98866f206e4d928574a096f12956cce039718a25 /kernel/bounds.c | |
| parent | 389ede06c2974b2f878a7ebff6b0f4f707f9db74 (diff) | |
| download | linux-stable-2a0992829ea3864939d917a5c7b48be6629c6217.tar.gz linux-stable-2a0992829ea3864939d917a5c7b48be6629c6217.tar.bz2 linux-stable-2a0992829ea3864939d917a5c7b48be6629c6217.zip | |
bpf: correct loop detection for iterators convergence
It turns out that .branches > 0 in is_state_visited() is not a
sufficient condition to identify if two verifier states form a loop
when iterators convergence is computed. This commit adds logic to
distinguish situations like below:
(I) initial (II) initial
| |
V V
.---------> hdr ..
| | |
| V V
| .------... .------..
| | | | |
| V V V V
| ... ... .-> hdr ..
| | | | | |
| V V | V V
| succ <- cur | succ <- cur
| | | |
| V | V
| ... | ...
| | | |
'----' '----'
For both (I) and (II) successor 'succ' of the current state 'cur' was
previously explored and has branches count at 0. However, loop entry
'hdr' corresponding to 'succ' might be a part of current DFS path.
If that is the case 'succ' and 'cur' are members of the same loop
and have to be compared exactly.
Co-developed-by: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Co-developed-by: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Reviewed-by: Andrii Nakryiko <andrii@kernel.org>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://lore.kernel.org/r/20231024000917.12153-6-eddyz87@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Diffstat (limited to 'kernel/bounds.c')
0 files changed, 0 insertions, 0 deletions