I seems to remember there was a discussion about this expression change from the original one at a point, but since I had not time to look at it, I always use my original to replace the FreeBSD one here. Since the original one had a little trouble to compile under 4.0-CURRENT now, JUST samll thing that KERNEL changed to _KERNEL, I decide to use the FreeBSD modified one, but got completed failure. The reason will discuss here: segment of code in /sys/net/bpf_filter.c: (I added two printf to show info.) ... case BPF_LD|BPF_H|BPF_ABS: k = pc->k; printf("k = %d, buflen = %d, b-k %d : k>b %d, s > b-k %d : reg % d\n", k, buflen, buflen-k, k > buflen, sizeof(short) > buflen - k, k + sizeof(short) > buflen); { int K = k; printf("K = %d, buflen = %d, b-K %d : K>b %d, s > b-K %d : reg % d\n", K, buflen, buflen-K, K > buflen, sizeof(short) > buflen - K, K + sizeof(short) > buflen) ; } /* real problem is HERE XXX */ if (k > buflen || sizeof(short) > buflen - k) { ... } else { ... } [1] /kernel: k = 6, buflen = 40, b-k 34 : k>b 0, s > b-k 0 : reg 0 [2] /kernel: K = 6, buflen = 40, b-K 34 : K>b 0, s > b-K 0 : reg 0 [3]/kernel: k = -1, buflen = 40, b-k 41 : k>b 1, s > b-k 0 : reg 0 [4]/kernel: K = -1, buflen = 40, b-K 41 : K>b 1, s > b-K 0 : reg 0 Two problems here: (1) this expression is not been compiled correctly somehow by compiler. in output line [4]; K>b shoud be false 0, but not true 1. (2) Critical part: This expression broken the original design in two place. <1> Since you defined all variables are u_int##, then you mean every var is positive #, then above expression is bogus. Translate this expression to real #: (A > 10 || 2 > 10 - A) === (A > 10 || A > 10 - 2) === (A > 10 || A > 8) === (A > 8) Here is go back to the original expression (A + 2 > 10) === (k + sizeof(short) > buflen) <2> The negtive k or pc->k was intended to be used n BPF filter. This seems too have changed in bpf.h from int to u_int. Also, the (k > buflen || sizeof(short) > buflen - k) increasing the complexity in brach statement which is very CPU cost. BPF is designed for light weight process. This incorrect expression has replaced every original expression through the bpf_filter.c. It need to alter back. Fix: If whoever make expression change agrees my explaination, please reply this PR before the formal release. Make sure we have time to change it back. Then I will send the "diff -c" for the patch.
State Changed From-To: open->feedback Does this problem still occur in newer versions of FreeBSD, such as 4.3-RELEASE?
Adding to Audit-Trail. On Sat, Jul 21, 2001 at 03:19:21PM -0700, Jin Guojun wrote: > mike@FreeBSD.org wrote: > > > Synopsis: Bad comparsion expression in bpf_filter.c > > > > State-Changed-From-To: open->feedback > > State-Changed-By: mike > > State-Changed-When: Sat Jul 21 13:01:31 PDT 2001 > > State-Changed-Why: > > > > Does this problem still occur in newer versions of FreeBSD, > > such as 4.3-RELEASE? > > > > http://www.FreeBSD.org/cgi/query-pr.cgi?pr=16644 > > I will make investigate on this one sometime later (probably in a month). > > -Jin > >
On Fri, 31 Aug 2001, Jin Guojun[ITG] wrote: > It is still there. I have replied this to the discussion and > got no response. For example, in line 220, ">" line is equal to > if (k > buflen || k + sizeof(int32_t) > buflen) { > or > if (k > buflen || k > buflen - sizeof(int32_t)) { > > if K > BUFLEN then K must > BUFLEN - 4 This doesn't follow. Example: K = 4U, BUFLEN = 2U, BUFLEN - 4 = UINT_MAX - 2. BUFLEN - 4 overflows. I'm not sure if this overflow can give undefined behaviour instead of UINT_MAX - 2. > so we only want to judge if (k > buflen - sizeof(int32_t)) { > which is the "<" of line 220 -- if (k + sizeof(int32_t) > buflen) { > > Right? rests are ditto. The original design is correct. No. Examples: (1) k = UINT_MAX - 2, buflen = 8U. Then k + sizeof(int32_t) = 2U, which is <= buflen. But k is much larger than buflen - sizeof(int32_t). Here arithmetic overflow occurs in the buffer overflow check and the buffer overflow check gives the wrong result. The overflow checks were rewritten in FreeBSD to avoid arithmetic overflow. (2) k = -2 (signed int, as in the original design), buflen = 8U. Then k + sizeof(int32_t) = 2U (no change). This is the same overflow as in (1). k first gets promoted to UINT_MAX - 2, then the addition overflows. > The real problem is at line 550. K is outside 0-BPF_MEMWORDS, not just >. > ... > 547c550 > < (p->k >= BPF_MEMWORDS || p->k < 0)) > --- > > p->k >= BPF_MEMWORDS) This patch is reversed (it gives the FreeBSD change). Here FreeBSD simplified the check instead of complicating it. p->k < 0 can't happen because p->k is unsigned. The compiler should optimize away the complication and generate identical code, but it migh warn about a bogus comparison of an unsigned value with 0. Bruce
Bruce Evans wrote: > On Fri, 31 Aug 2001, Jin Guojun[ITG] wrote: > > > It is still there. I have replied this to the discussion and > > got no response. For example, in line 220, ">" line is equal to > > if (k > buflen || k + sizeof(int32_t) > buflen) { > > or > > if (k > buflen || k > buflen - sizeof(int32_t)) { > > > > if K > BUFLEN then K must > BUFLEN - 4 > > This doesn't follow. Example: K = 4U, BUFLEN = 2U, BUFLEN - 4 = UINT_MAX - 2. > BUFLEN - 4 overflows. I'm not sure if this overflow can give undefined > behaviour instead of UINT_MAX - 2. > > > so we only want to judge if (k > buflen - sizeof(int32_t)) { > > which is the "<" of line 220 -- if (k + sizeof(int32_t) > buflen) { > > > > Right? rests are ditto. The original design is correct. > > No. Examples: > > (1) k = UINT_MAX - 2, buflen = 8U. Then k + sizeof(int32_t) = 2U, which > is <= buflen. But k is much larger than buflen - sizeof(int32_t). > Here arithmetic overflow occurs in the buffer overflow check and > the buffer overflow check gives the wrong result. The overflow > checks were rewritten in FreeBSD to avoid arithmetic overflow. > (2) k = -2 (signed int, as in the original design), buflen = 8U. Then > k + sizeof(int32_t) = 2U (no change). This is the same overflow as > in (1). k first gets promoted to UINT_MAX - 2, then the addition > overflows. > > > The real problem is at line 550. K is outside 0-BPF_MEMWORDS, not just >. > > ... > > 547c550 > > < (p->k >= BPF_MEMWORDS || p->k < 0)) > > --- > > > p->k >= BPF_MEMWORDS) > > This patch is reversed (it gives the FreeBSD change). Here FreeBSD > simplified the check instead of complicating it. p->k < 0 can't happen > because p->k is unsigned. The compiler should optimize away the > complication and generate identical code, but it migh warn about a > bogus comparison of an unsigned value with 0. > > Bruce The entire thing is messed up because the k is revised in the lastest BPF release. k is signed in the lastest release, and all above explanation is beased on signed K. It fixed the undefined overflow problem. Signed K does not work correctly, that is why you had above overflow issue. Overflow is wrong (not intended). Below is I explained to someone who asked about is: -------- original message ----------- Jonathan Lemon wrote: > Hello - > > I'm looking at bpf in FreeBSD, and it appears that our current > definition for the bpf_insn structure is: > > struct bpf_insn { > u_short code; > u_char jt; > u_char jf; > bpf_u_int32 k; > }; > > Note the last line has ``k'' being unsigned. In the LBL releases, > it seems that there was a bit of confusion on the definition of > this field: > > original berkeley release: long > LBL rev 1.34: bpf_u_int32 > LBL rev 1.36: bpf_int32 > > Not having the RCS logs for the file, its not entirely clear > for the differing definitions here. Is it intended that 'k' > may be negative in the bpf_insn structure? > -- > Jonathan Yes, k may have negtive value. I cannot recall when FreeBSD changed it, but I remember I read the email about it regarding some expression. They claimed make k non-negtive can fix their problem, I do not know what. Later sometime, I checked their expression which is bogus, so I send email to the bugs@freebsd.org, and explained that expression has nothing to do with int k or uint k. I asked them to change back because uint k breaks the kernel BPF functioning. No one was responsed. So, I put Kernel BPF patch on my web site in case some encounts problems. -Jin
There was a typo in the previous message I sent. < It fixed the undefined overflow problem. Signed K does not work correctly, ^^^^^ should be > It fixed the undefined overflow problem. Unsigned K does not work correctly, ^^^^^^^ -Jin Jin Guojun wrote: > Bruce Evans wrote: > > > On Fri, 31 Aug 2001, Jin Guojun[ITG] wrote: > > > > > It is still there. I have replied this to the discussion and > > > got no response. For example, in line 220, ">" line is equal to > > > if (k > buflen || k + sizeof(int32_t) > buflen) { > > > or > > > if (k > buflen || k > buflen - sizeof(int32_t)) { > > > > > > if K > BUFLEN then K must > BUFLEN - 4 > > > > This doesn't follow. Example: K = 4U, BUFLEN = 2U, BUFLEN - 4 = UINT_MAX - 2. > > BUFLEN - 4 overflows. I'm not sure if this overflow can give undefined > > behaviour instead of UINT_MAX - 2. > > > > > so we only want to judge if (k > buflen - sizeof(int32_t)) { > > > which is the "<" of line 220 -- if (k + sizeof(int32_t) > buflen) { > > > > > > Right? rests are ditto. The original design is correct. > > > > No. Examples: > > > > (1) k = UINT_MAX - 2, buflen = 8U. Then k + sizeof(int32_t) = 2U, which > > is <= buflen. But k is much larger than buflen - sizeof(int32_t). > > Here arithmetic overflow occurs in the buffer overflow check and > > the buffer overflow check gives the wrong result. The overflow > > checks were rewritten in FreeBSD to avoid arithmetic overflow. > > (2) k = -2 (signed int, as in the original design), buflen = 8U. Then > > k + sizeof(int32_t) = 2U (no change). This is the same overflow as > > in (1). k first gets promoted to UINT_MAX - 2, then the addition > > overflows. > > > > > The real problem is at line 550. K is outside 0-BPF_MEMWORDS, not just >. > > > ... > > > 547c550 > > > < (p->k >= BPF_MEMWORDS || p->k < 0)) > > > --- > > > > p->k >= BPF_MEMWORDS) > > > > This patch is reversed (it gives the FreeBSD change). Here FreeBSD > > simplified the check instead of complicating it. p->k < 0 can't happen > > because p->k is unsigned. The compiler should optimize away the > > complication and generate identical code, but it migh warn about a > > bogus comparison of an unsigned value with 0. > > > > Bruce > > The entire thing is messed up because the k is revised in the lastest BPF > release. > k is signed in the lastest release, and all above explanation is beased on signed > K. > It fixed the undefined overflow problem. Signed K does not work correctly, > that is why you had above overflow issue. Overflow is wrong (not intended). > Below is I explained to someone who asked about is: > > -------- original message ----------- > > Jonathan Lemon wrote: > > > Hello - > > > > I'm looking at bpf in FreeBSD, and it appears that our current > > definition for the bpf_insn structure is: > > > > struct bpf_insn { > > u_short code; > > u_char jt; > > u_char jf; > > bpf_u_int32 k; > > }; > > > > Note the last line has ``k'' being unsigned. In the LBL releases, > > it seems that there was a bit of confusion on the definition of > > this field: > > > > original berkeley release: long > > LBL rev 1.34: bpf_u_int32 > > LBL rev 1.36: bpf_int32 > > > > Not having the RCS logs for the file, its not entirely clear > > for the differing definitions here. Is it intended that 'k' > > may be negative in the bpf_insn structure? > > -- > > Jonathan > > Yes, k may have negtive value. I cannot recall when FreeBSD changed it, > but I remember I read the email about it regarding some expression. > They claimed make k non-negtive can fix their problem, I do not know what. > > Later sometime, I checked their expression which is bogus, so I send email > to the bugs@freebsd.org, and explained that expression has nothing to do > with int k or uint k. I asked them to change back because uint k breaks the > kernel BPF functioning. No one was responsed. > So, I put Kernel BPF patch on my web site in case some encounts problems. > > -Jin
State Changed From-To: feedback->closed Automatic feedback timeout. This PR remained unchanged in the feedback state for more than 4 months. If additional feedback that warrants the re-opening of this PR is available but not included in the audit trail, please include the feedback in a reply to this message (preserving the Subject line) and ask that the PR be re-opened.
State Changed From-To: closed->open It seems there is still an issue here. We probably need Bruce or Jonathan to say what the next step is.
Responsible Changed From-To: freebsd-bugs->csjp Please confirm that there is an issue.
Responsible Changed From-To: csjp->dwmalone I'll grab this PR and check what issues remain. I think I have enough of a handle on the problem to understand what's going on. David.
Responsible Changed From-To: dwmalone->freebsd-bugs over to the pool (approved by bugmeister)
This code has changed in fundamental ways since this PR was opened (18 years ago!). I quick perusal of the current code does show the same issue. Close the PR with a thank you for submitting this patch!