pure-lua pipeline 'not' broken: length checks are too large

[kbara]

91e367c, branch pflangprop
% ../tools/pflua-quickcheck --seed=885398570 --iterations=393 properties/pflua_pipelines_match data/wingolog.pcap
The property was falsified.
The pflang expression was not tcp port 59054 and the packet number 2852
BPF: true, pure-lua: false
Rerun as: pflua-quickcheck --seed=885398570 --iterations=393 properties/pflua_pipelines_match data/wingolog.pcap

Packet 2852 has source port 80 and destination port 60686; neither are 59054, so it should match. In the BPF pipeline it does; in the purely-lua pipeline, it doesn't.

[kbara]

This appears to be related to the packet length. Packet 2852 has length 54. The lua function returned starts by checking if length < 34 for the expression "tcp port 59054", and checking if length < 58 for the expression "not tcp port 59054".

% ./pflua-compile "tcp port 59054"
return function(P,length)
   if length < 34 then return false end
   local var1 = cast("uint16_t*", P+12)[0]
   if var1 == 8 then
      if P[23] ~= 6 then return false end
      if band(cast("uint16_t*", P+20)[0],65311) ~= 0 then return false end
      local var7 = lshift(band(P[14],15),2)
      local var8 = (var7 + 16)
      if var8 > length then return false end
      if cast("uint16_t*", P+(var7 + 14))[0] == 44774 then return true end
      if (var7 + 18) > length then return false end
      return cast("uint16_t*", P+var8)[0] == 44774
   else
      if length < 56 then return false end
      if var1 ~= 56710 then return false end
      local var24 = P[20]
      if var24 == 6 then goto L22 end
      do
         if var24 ~= 44 then return false end
         if P[54] == 6 then goto L22 end
         return false
      end
::L22::
      if cast("uint16_t*", P+54)[0] == 44774 then return true end
      if length < 58 then return false end
      return cast("uint16_t*", P+56)[0] == 44774
   end
end

vs

return function(P,length)
   if length < 58 then return false end
   local var1 = cast("uint16_t*", P+12)[0]
   if var1 == 8 then
      if P[23] ~= 6 then return true end
      if band(cast("uint16_t*", P+20)[0],65311) ~= 0 then return false end
      local var7 = lshift(band(P[14],15),2)
      local var8 = (var7 + 16)
      if var8 > length then return false end
      if cast("uint16_t*", P+(var7 + 14))[0] == 44774 then return false end
      if (var7 + 18) > length then return false end
      return cast("uint16_t*", P+var8)[0] ~= 44774
   else
      if var1 ~= 56710 then return false end
      local var24 = P[20]
      if var24 == 6 then goto L22 end
      do
         if var24 ~= 44 then return true end
         if P[54] == 6 then goto L22 end
         return true
      end
::L22::
      if cast("uint16_t*", P+54)[0] == 44774 then return false end
      return cast("uint16_t*", P+56)[0] ~= 44774
   end
end

[kbara]

More similar examples, from 53fa5ea suggest that 'not' should not necessarily have a minimum length.
Packet 790 also has length 54; there was no explicit 'tcp' in the filter.

The property was falsified.
The pflang expression was not port 17820 and the packet number 790
BPF: true, pure-lua: false
Rerun as: pflua-quickcheck --seed=637261113 --iterations=81 properties/pflua_pipelines_match data/wingolog.pcap

---

And here's a stranger example; packet 2367 is protocol AoE, ATA over Ethernet, a layer-2 protocol that does not have port numbers. The packet length is 32. "tcp port (somenumber)" checks length < 34; "not tcp port (somenumber)" checks length < 58.

The property was falsified.
The pflang expression was not tcp port 49410 and the packet number 2367
BPF: true, pure-lua: false
Rerun as: pflua-quickcheck --seed=38582848 --iterations=859 properties/pflua_pipelines_match data/wingolog.pcap

---

A third example, on a normal tcp (which is not igrp) packet of length 54:

The property was falsified.
The pflang expression was not igrp and the packet number 3839
BPF: true, pure-lua: false
Rerun as: pflua-quickcheck --seed=285294557 --iterations=547 properties/pflua_pipelines_match data/wingolog.pcap

Once again, it seems length-related; a filter of "igrp" checks for length < 34, while "not igrp" checks for length < 55. However, something which is not igrp could reasonably have any length.

[kbara]

This appears to be an optimizer bug; when the filter is compiled with optimizations disabled, it disappears.

[kbara]

As @andywingo correctly analyzed, it's a length hoisting bug, to be precise. Commenting out expr = simplify(lhoist(expr)) makes it disappear.

[kbara]

It appears it's actually deeper than that after all. With length hoisting disabled, in the tests/ directory:

% ../tools/pflua-quickcheck --seed=939666196 --iterations=7 properties/pflua_pipelines_match data/wingolog.pcap
Git revision fe14b172075d791e1ab59bf683ce9db3354eb45f
The property was falsified.
The pflang expression was not rarp[181]  > 163 and the packet number 15638
BPF: true, pure-lua: false
Rerun as: pflua-quickcheck --seed=939666196 --iterations=7 properties/pflua_pipelines_match data/wingolog.pcap

This included the following:

--- a/src/pf/optimize.lua
+++ b/src/pf/optimize.lua
@@ -727,7 +727,7 @@ function optimize_inner(expr)
    expr = simplify(expr)
    expr = simplify(cfold(expr, {}))
    expr = simplify(infer_ranges(expr))
-   expr = simplify(lhoist(expr))
+   --expr = simplify(lhoist(expr))
    clear_cache()
    return expr
 end

[kbara]

#181 fixed this.