Re: pcap_compile() errors in libpcap beta and CVS

[George Bakos <gbakos () ists dartmouth edu>]

It would appear that this is due to a change in optimize.c, as of the 1.73
checkin. In opt_peep(b), using a continue statement, rather than a break,
causes over-optimization in certain cases. It is possible, however I can't
see when, that the following backout patch may lead to less optimization.
Comments?

--- optimize.c Sat Nov 15 18:24:00 2003
+++ optimize.c.gb Tue Dec 16 15:21:51 2003
@@ -707,23 +707,23 @@
                         * any local dependencies.
                         */
                        if (ATOMELEM(b->out_use, X_ATOM))
-                               continue;
+                               break;
 
                        if (next->s.code != (BPF_LDX|BPF_MSH|BPF_B))
                                add = next;
                        else
                                add = this_op(next->next);
                        if (add == 0 || add->s.code != (BPF_ALU|BPF_ADD|BPF_X))
-                               continue;
+                               break;
 
                        tax = this_op(add->next);
                        if (tax == 0 || tax->s.code != (BPF_MISC|BPF_TAX))
-                               continue;
+                               break;
 
                        ild = this_op(tax->next);
                        if (ild == 0 || BPF_CLASS(ild->s.code) != BPF_LD ||
                            BPF_MODE(ild->s.code) != BPF_IND)
-                               continue;
+                               break;
                        /*
                         * XXX We need to check that X is not
                         * subsequently used.  We know we can eliminate the

<------ end ------->

On Wed, 10 Dec 2003 16:08:32 -0500
George Bakos <gbakos () ists dartmouth edu> wrote:

> I've noticed some strange behavior with the latest pcap_compile(). When
> building up complex filters, there is an error if multiple matches are
> performed on the same data offset while using arithmetic operators to form the
> match value. An example will explain better.
>
> The following filter is a match for ACK FIN or ACK SYN tcp segments. This is
> just a simple example to demonstrate the problem.
>
> tcpdump -d '(tcp[13] = (0x10 + 0x01)) or (tcp[13] = (0x10 + 0x02))'
> (000) ldh      [12]
> (001) jeq      #0x800           jt 2    jf 12
> (002) ldb      [23]
> (003) jeq      #0x6             jt 4    jf 12
> (004) ldh      [20]
> (005) jset     #0x1fff          jt 12   jf 6
> (006) ldxb     4*([14]&0xf)
> (007) ldb      [x + 27]
> (008) ldx      #0x11
> (009) jeq      x                jt 11   jf 10
> (010) jeq      x                jt 11   jf 12
> (011) ret      #68
> (012) ret      #0
>
> The error is visible at (010) - there should be ldx #0x12 before the jeq.
>
> If the same filter were built without the arithmetic operators, it compiles
> properly and avoids the extra ld step(s).
>
> tcpdump -d '(tcp[13] = 0x11) or (tcp[13] = 0x12)
> (000) ldh      [12]
> (001) jeq      #0x800           jt 2    jf 11
> (002) ldb      [23]
> (003) jeq      #0x6             jt 4    jf 11
> (004) ldh      [20]
> (005) jset     #0x1fff          jt 11   jf 6
> (006) ldxb     4*([14]&0xf)
> (007) ldb      [x + 27]
> (008) jeq      #0x11            jt 10   jf 9
> (009) jeq      #0x12            jt 10   jf 11
> (010) ret      #68
> (011) ret      #0
>
> Previous versions (0.7.2 here) of pcap_compile handled this correctly with or
> without the addition operation:
>
> tcpdump.oldpcap -d '(tcp[13] = (0x10 + 0x01)) or (tcp[13] = (0x10 + 0x02))'
> (000) ldh      [12]
> (001) jeq      #0x800           jt 2    jf 11
> (002) ldb      [23]
> (003) jeq      #0x6             jt 4    jf 11
> (004) ldh      [20]
> (005) jset     #0x1fff          jt 11   jf 6
> (006) ldxb     4*([14]&0xf)
> (007) ldb      [x + 27]
> (008) jeq      #0x11            jt 10   jf 9
> (009) jeq      #0x12            jt 10   jf 11
> (010) ret      #68
> (011) ret      #0
>
> With IDABench I use include statements & variable substitution to facilitate easier complex filter generation & 
> maintenance. The following composite filter now fails:
>
> tcp and !src net 129.170.248.0/23 and
> (
>  (tcp[13] & 0x3f != 0x02)
>  and
>  (tcp[13] & 0x3f != (0x02 + 0x10))
>  and
>  (tcp[13] & 0x3f != (0x10 + 0x01))
>  and
>  (tcp[13] & 0x3f != (0x10 + 0x08 + 0x01))
>  and
>  (tcp[13] & 0x3f != (0x10 + 0x08 + 0x01 + 0x20))
>  and
>  (tcp[13] & 0x3f != (0x10 + 0x04))
>  and
>  (tcp[13] & 0x3f != 0x10)
>  and
>  (tcp[13] & 0x3f != (0x10 + 0x08))
>  and
>  (tcp[13] & 0x3f != 0x04)
>  and
>  (tcp[13] & 0x3f != (0x20 + 0x10 + 0x01))
>  and
>  (tcp[13] & 0x3f != (0x20 + 0x10 + 0x08))
>  and
>  (tcp[13] & 0x3f != (0x20 + 0x10 + 0x08 + 0x04))
>  and
>  (tcp[13] & 0x3f != (0x10 + 0x08 + 0x04))
> )
>
> It compiles into:
> (000) ldh      [12]
> (001) jeq      #0x800           jt 2    jf 26
> (002) ldb      [23]
> (003) jeq      #0x6             jt 4    jf 26
> (004) ld       [26]
> (005) and      #0xfffffe00
> (006) jeq      #0x81aaf800      jt 26   jf 7
> (007) ldh      [20]
> (008) jset     #0x1fff          jt 26   jf 9
> (009) ldxb     4*([14]&0xf)
> (010) ldb      [x + 27]
> (011) and      #0x3f
> (012) jeq      #0x2             jt 26   jf 13
> (013) jeq      x                jt 26   jf 14
> (014) jeq      x                jt 26   jf 15
> (015) jeq      x                jt 26   jf 16
> (016) jeq      x                jt 26   jf 17
> (017) jeq      x                jt 26   jf 18
> (018) jeq      #0x10            jt 26   jf 19
> (019) jeq      x                jt 26   jf 20
> (020) jeq      #0x4             jt 26   jf 21
> (021) jeq      x                jt 26   jf 22
> (022) jeq      x                jt 26   jf 23
> (023) jeq      x                jt 26   jf 24
> (024) jeq      x                jt 26   jf 25
> (025) ret      #68
> (026) ret      #0
>
> My size of my hourly reports (and number of false positives) skyrocketed as you
> can imagine!
>
> Cheers.
>
> -- 
> George Bakos
> Institute for Security Technology Studies - IRIA
> Dartmouth College
> gbakos () ists dartmouth edu
> 603.646.0665 -voice
> 603.646.0666 -fax
> -
> This is the TCPDUMP workers list. It is archived at
> http://www.tcpdump.org/lists/workers/index.html
> To unsubscribe use mailto:tcpdump-workers-request () tcpdump org?body=unsubscribe


-- 
George Bakos
Institute for Security Technology Studies - IRIA
Dartmouth College
gbakos () ists dartmouth edu
603.646.0665 -voice
603.646.0666 -fax
-
This is the TCPDUMP workers list. It is archived at
http://www.tcpdump.org/lists/workers/index.html
To unsubscribe use mailto:tcpdump-workers-request () tcpdump org?body=unsubscribe