search

Igalia / pflua

Packet filtering in Lua
Other
313 stars 39 forks source link

Another automatically-found optimizer bug #126

Closed kbara closed 9 years ago

kbara commented 9 years ago 
The property was falsified.
--- Expanded:
{ "if",
  { "if",
    { "<",
      "len",
      { "uint32",
        { "+",
          "len",
          4294967295 } } },
    { "if",
      { "if",
        { "true" },
        { "true" },
        { "false" } },
      { "if",
        { ">=",
          "len",
          { "+",
            1,
            4 } },
        { "if",
          { ">=",
            "len",
            { "+",
              "len",
              4 } },
          { "if",
            { "!=",
              { "uint32",
                { "ntohs",
                  { "[]",
                    "len",
                    4 } } },
              0 },
            { "if",
              { "!=",
                35575672,
                0 },
              { "if",
                { ">=",
                  "len",
                  { "+",
                    { "uint32",
                      { "/",
                        4294967295,
                        35575672 } },
                    4 } },
                { "if",
                  { "!=",
                    { "uint32",
                      { "ntohs",
                        { "[]",
                          { "uint32",
                            { "/",
                              4294967295,
                              35575672 } },
                          4 } } },
                    0 },
                  { "if",
                    { ">=",
                      "len",
                      { "+",
                        { "uint32",
                          { "-",
                            { "uint32",
                              { "/",
                                { "uint32",
                                  { "+",
                                    { "uint32",
                                      { "+",
                                        2147483648,
                                        "len" } },
                                    { "uint32",
                                      { "ntohs",
                                        { "[]",
                                          1,
                                          4 } } } } },
                                { "uint32",
                                  { "ntohs",
                                    { "[]",
                                      "len",
                                      4 } } } } },
                            { "uint32",
                              { "/",
                                1,
                                { "uint32",
                                  { "ntohs",
                                    { "[]",
                                      { "uint32",
                                        { "/",
                                          4294967295,
                                          35575672 } },
                                      4 } } } } } } },
                        4 } },
                    { "<",
                      { "uint32",
                        { "ntohs",
                          { "[]",
                            { "uint32",
                              { "-",
                                { "uint32",
                                  { "/",
                                    { "uint32",
                                      { "+",
                                        { "uint32",
                                          { "+",
                                            2147483648,
                                            "len" } },
                                        { "uint32",
                                          { "ntohs",
                                            { "[]",
                                              1,
                                              4 } } } } },
                                    { "uint32",
                                      { "ntohs",
                                        { "[]",
                                          "len",
                                          4 } } } } },
                                { "uint32",
                                  { "/",
                                    1,
                                    { "uint32",
                                      { "ntohs",
                                        { "[]",
                                          { "uint32",
                                            { "/",
                                              4294967295,
                                              35575672 } },
                                          4 } } } } } } },
                            4 } } },
                      0 },
                    { "fail" } },
                  { "fail" } },
                { "fail" } },
              { "fail" } },
            { "fail" } },
          { "fail" } },
        { "fail" } },
      { "true" } },
    { "false" } },
  { "if",
    { "if",
      { "fail" },
      { "if",
        { "true" },
        { "false" },
        { "fail" } },
      { "if",
        { "if",
          { ">=",
            "len",
            { "+",
              4294967295,
              4 } },
          { "<",
            { "uint32",
              { "-",
                "len",
                "len" } },
            { "uint32",
              { "ntohs",
                { "[]",
                  4294967295,
                  4 } } } },
          { "fail" } },
        { "fail" },
        { "true" } } },
    { "false" },
    { "if",
      { "!=",
        "len",
        0 },
      { "if",
        { ">=",
          "len",
          { "+",
            { "uint32",
              { "+",
                1,
                { "uint32",
                  { "/",
                    "len",
                    "len" } } } },
            2 } },
        { "if",
          { ">=",
            "len",
            { "+",
              "len",
              4 } },
          { "if",
            { ">=",
              "len",
              { "+",
                { "uint32",
                  { "+",
                    { "ntohs",
                      { "[]",
                        { "uint32",
                          { "+",
                            1,
                            { "uint32",
                              { "/",
                                "len",
                                "len" } } } },
                        2 } },
                    { "uint32",
                      { "ntohs",
                        { "[]",
                          "len",
                          4 } } } } },
                2 } },
            { "<",
              { "ntohs",
                { "[]",
                  { "uint32",
                    { "+",
                      { "ntohs",
                        { "[]",
                          { "uint32",
                            { "+",
                              1,
                              { "uint32",
                                { "/",
                                  "len",
                                  "len" } } } },
                          2 } },
                      { "uint32",
                        { "ntohs",
                          { "[]",
                            "len",
                            4 } } } } },
                  2 } },
              "len" },
            { "fail" } },
          { "fail" } },
        { "fail" } },
      { "fail" } } },
  { "true" } }
--- Optimized:
{ "if",
  { ">=",
    "len",
    124 },
  { "if",
    { "if",
      { "<",
        "len",
        { "uint32",
          { "+",
            "len",
            4294967295 } } },
      { "if",
        { ">=",
          "len",
          { "+",
            "len",
            4 } },
        { "if",
          { "!=",
            { "ntohs",
              { "[]",
                "len",
                4 } },
            0 },
          { "if",
            { "!=",
              { "ntohs",
                { "[]",
                  120,
                  4 } },
              0 },
            { "if",
              { ">=",
                "len",
                { "+",
                  { "-",
                    { "/",
                      { "+",
                        { "+",
                          2147483648,
                          "len" },
                        { "ntohs",
                          { "[]",
                            1,
                            4 } } },
                      { "ntohs",
                        { "[]",
                          "len",
                          4 } } },
                    { "/",
                      1,
                      { "ntohs",
                        { "[]",
                          120,
                          4 } } } },
                  4 } },
              { "<",
                { "ntohs",
                  { "[]",
                    { "-",
                      { "/",
                        { "+",
                          { "+",
                            2147483648,
                            "len" },
                          { "ntohs",
                            { "[]",
                              1,
                              4 } } },
                        { "ntohs",
                          { "[]",
                            "len",
                            4 } } },
                      { "/",
                        1,
                        { "ntohs",
                          { "[]",
                            120,
                            4 } } } },
                    4 } },
                0 },
              { "fail" } },
            { "fail" } },
          { "fail" } },
        { "fail" } },
      { "false" } },
    { "fail" },
    { "true" } },
  { "fail" } }
On packet 13965: unoptimized was true, optimized was false
Rerun as: pflua-quickcheck --seed=344996622 --iterations=68798 properties/opt_eq_unopt data/wingolog.pcap
kbara commented 9 years ago

Reduction with creduce went badly.

% cat reduce126.sh 
#!/bin/bash
rm -f bug126out.txt
ulimit -t 1
pwd
if
        ! ~/igalia/pflua/tools/pflua-optimize --match-packet 13965 ~/igalia/pflua-bench/savefiles/wingolog.org.pcap bug126.ast > bug126out.txt && \
        grep "Packet results did not match" bug126out.txt
        then exit 0
        else exit 1
fi

LUA_PATH='~/igalia/pflua/src/?.lua;~/igalia/pflua/tests/?.lua' creduce --skip-initial-passes --verbose reduce126.sh bug126.ast

wc bug126.best bug126.orig
  111   556  5039 bug126.best
  238   556  7363 bug126.orig
wingo commented 9 years ago

did it work at all or did it just not produce good results?

kbara commented 9 years ago

It mangled the formatting, and was still about 5/7th of the size.

kbara commented 9 years ago

This bug hasn't been thoroughly investigated, but has been fixed by an optimizer change since it was reported.