[Proposal] introduce a new event in a Lua hook mechanism

[Sergey Bronnikov]

Hello,

### Abstract

Gathering source code coverage information is a well-known goal within software
engineering.

The first use case is the most popular - assess code coverage during
automated testing. Lua module `luacov` has been implemented for such purposes.
Unfortunately, `luacov` supports only line coverage and more fine-grained coverage like
branch coverage is not supported [5].

A lesser-known use case is coverage-guided fuzzing testing.
Fuzzing testing is quite popular nowadays; it is an increasingly common way to
improve software's robustness. Go has it built in to the standard
library, Python has Atheris, Java has Jazzer, and JavaScript has Jazzer.js, Ruby
has Ruzzy, etc. Lua deserves a good fuzzing engine, and good coverage feedback
would help achieve that goal. The use case was born out of a coverage-guided
Lua fuzzing engine `luzer` [1].

This proposal exists to request a new Lua hook event in a public Lua and Lua C API.

### Background

(Sorry for a wordy background section, but I'm sure it is important
for diving into context.)

A coverage-guided fuzzing engines use special instrumentation that very likely
improve the results. Let's consider a popular fuzzing engine LibFuzzer [2], it is
one of the most popular fuzzing engines for C/C++ projects.

For building a fuzzing test, written in C/C++, one need to pass a flag `-fsanitize=fuzzer` to
Clang compiler, this flag translates to a number of flags, that enables
compile-time instrumentation [3]:

- `-fsanitize-coverage-type=1`
- `-fsanitize-coverage-type=3`
- `-fsanitize-coverage=indirect-calls`
- `-fsanitize-coverage=stack-depth`
- `-fsanitize-coverage=pc-table`
- `-fsanitize-coverage=inline-8bit-counters`
- `-fsanitize-coverage=trace-cmp`

The last three flags are the most interesting for us:
`-fsanitize-coverage=inline-8bit-counters`, `-fsanitize-coverage=pc-table`,
`-fsanitize-coverage=trace-cmp`.

The fuzzing engine need to get coverage information to libFuzzer. The two primary
code coverage mechanisms are function `__sanitizer_cov_pcs_init()` (which registers a set
of program counters that might be visited) that enabled with
`-fsanitize-coverage=pc-table` and function `__sanitizer_cov_8bit_counters_init()`,
which registers an array of booleans that are to be incremented when a basic block is
visited, that enabled with `-fsanitize-coverage=inline-8bit-counters`.
Additionally, with `-fsanitize-coverage=inline-8bit-counters` the compiler will
insert inline counter increments on every edge. In short, compiler flags
`-fsanitize-coverage=inline-8bit-counters` and `-fsanitize-coverage=pc-table`
used for gathering a coverage.

The compiler flag `-fsanitize-coverage=trace-cmp` enables a feature with
tracing "compare" instructions, libFuzzer will intercept these instructions
and guide mutations based on the arguments of intercepted "compare" instructions.
This may slow down the fuzzing process, but is very likely will improve the results.

Let's back to a Lua. Lua has a hook mechanism [4] implemented in the `debug` library
that allows to register a function that will be called at specific events as
your program runs. This hook mechanism can be used a runtime instrumentation.
There are four kinds of events that can trigger a hook: "call" events happen
every time Lua calls a function; "return" events happen every time a function
returns; "line" events happen when Lua starts executing a new line of code; and
"count" events happen after a given number of instructions. This hook
mechanism is available in Lua C API as well as in Lua API.

The `debug` module, and existed Lua hook events can be used for a coverage-guided
fuzzing, but it is not enough to do it effectively.

Let's take a look to a Lua code with condition below:

```lua
if str == 'Hello, world!' then
   --[[...]]
end
```

Obviously, existed Lua hook events could not help here and fuzzing engine
will bruteforce variable `str` to get inside a condition. Value profiling
could help with passing conditions with constants.

### Proposal

Lua bytecode has three comparison bytecode instructions:

- `OP_EQ` (equality test)
- `OP_LE` (less than or equal to test)
- `OP_LT` (less than test)
- etc.

All comparison and test ops are immediately followed by
a JMP instruction, which holds the target of the conditional jump.

The following Lua code demonstrates two `LE` and `LT` bytecode instructions
and the following `JMP` instructions in  bytecode output.

```lua
if 1 <= 1 then
  --[ ... ]
elseif 1 > 2 then
  --[ ... ]
else
  --[ ... ]
end
```

The output:

```
$ luac -l op.lua

main <op.lua:0,0> (7 instructions at 0x5e76052e06d0)
0+ params, 2 slots, 1 upvalue, 0 locals, 2 constants, 0 functions
        1       [1]     LE              0 -1 -1 ; 1 1
        2       [1]     JMP             0 1     ; to 4
        3       [1]     JMP             0 3     ; to 7
        4       [3]     LT              0 -2 -1 ; 2 1
        5       [3]     JMP             0 1     ; to 7
        6       [3]     JMP             0 0     ; to 7
        7       [7]     RETURN          0 1
```

By instrumenting `OP_EQ`, `OP_LE` and `OP_LT` instructions at runtime
we could collect information about Lua code flow and extract values
passed to comparison instructions.

It is proposed to introduce a new hook event "branch", that will trigger
a hook function on these three comparison instructions.
A function passed to a hook mechanism will be executed with three arguments:
first, second operand and a string with operation sign:

```lua
function hook_function(op_left, op_name, op_right)
    --[[ ... ]]
end

debug.sethook(hook_function, "b")
```

New hook event could help to make coverage feedback more useful for
a fuzzing engine, will help to "pass" conditions in a Lua code and
thus increase a code coverage of source code under test. Also, new hook event
could be used in `luacov` for a fine-grained coverage reports.

### Discussion

There is a poor man's implementation of a value profiling in Lua.
It could be implemented with a hook function that discovers upvalues
with `debug.getlocal()`.

The Lua code below demonstrate an idea:

```lua
local a, b = 1, 2
local function func()
  if a ~= b then
  end
  debug.sethook() -- Disable hook.
end

debug.sethook(function(...)
  for i = 1, 3 do
    print(debug.getlocal(2, i))
  end
end, "l")

func()
```

The output:

```
a       1
b       2
t       function: 0x55911575ef10
(*temporary)    function: 0x55911575e0f0
(*temporary)    l
(*temporary)    table: 0x55911575ee80
(*temporary)    1
(*temporary)    2
(*temporary)    table: 0x55911575ee80
```

The `debug.getlocal()` helped to extract a constants used in condition.
But this will guide mutations based on the all reachable variables, not an
arguments of compare instructions. It is not effective as it could be.

The proposed change with a new hook could be made by myself and without adding to upstream,
it is not that difficult (I actually have draft patches for 5.1, 5.2, 5.3).
The problem is that support for the hook is needed not only in the fuzzing module
itself and, but most importantly, it should be in the runtime too.
While it is not difficult to add support for the new hook to the fuzzing module
itself, there are difficulties with support in the runtime. I will need to
either supply patched interpreters and/or support patches and recommend users
to patch liblua used in their projects.
All this likely complicates the use of the module, and since some users will most
likely not do this, it reduces the efficiency of Lua fuzzing. I know that
the Lua language itself and its implementation designed to be efficient,
lightweight, embeddable and there is nothing superfluous there, but given
the arguments above, I suggest implementing the hook in the upstream.

### Instrumenting in other programming languages

#### Python

For Python there is is a coverage-guided fuzzing engine named Atheris [6].
It supports fuzzing of Python code, but also native extensions written for CPython.
Atheris is based off of libFuzzer.

How Atheris instrumenting Python source code for fuzzing
(in short: instrumenting is a combination of hook-based and
bytecode-based instrumentation approaches):

To collect information about Python code flow Atheris registers a tracer with CPython.
This tracer can keep track of every line reached and every function executed.
When Python 3.8 is used Atheris switches to opcode tracing, it allows to monitor
not only every line is visited and every function is called, but monitor
every operation that Python performs, and what arguments it uses.
This allows Atheris to find its way through `if` statements much better.

When a COMPARE_OP opcode is encountered, indicating a boolean comparison
between two values, Atheris inspects the types of the values. If the values
are bytes or Unicode, Atheris is able to report the comparison to libFuzzer
via `__sanitizer_weak_hook_memcmp`. For integer comparison, Atheris uses
the appropriate function to report integer comparisons, such as `__sanitizer_cov_trace_cmp8`.
However, performance measurements discovered that the surprising
best strategy is to convert both strings to utf-8, then compare those with
`__sanitizer_weak_hook_memcmp`. Even with the performance overhead of conversion,
libFuzzer makes progress much faster.

See more details about Atheris implementation in [7] and [8].

#### Java

For Java there is a coverage-guided, in-process fuzzer for the JVM platform named Jazzer [9].It is based on libFuzzer and brings many of its instrumentation-powered
mutation features to the JVM.

How Jazzer instrumenting JVM Bytecode for fuzzing
(in short: instrumenting is bytecode-based):

The JVM bytecode of a compiled Java class is much higher-level than the machine
code of an equivalent C/C++ binary. This makes it possible to instrument a JVM
application at runtime rather than at build-time, which means that neither the
code nor the build script requires any changes.

To obtain coverage information from the JVM fuzz target, the Jazzer
inserts bytecode instructions together with a unique ID at the beginning of
every basic block. When we enter a block, the previous basic block’s shifted ID
is XORed with the current ID to obtain an identifier for the control flow edge
between the two blocks.

Since coverage is not the only type of information that is used by libFuzzer to
guide its exploration of the fuzz target, Jazzer also instruments other JVM
constructs:

- bytecode-level compares, such as the `lcmp`, `if_*`, and `if*` opcodes
- higher-level method-based compares, such as `String#equal` or `Arrays#compare`
- switch statements (corresponding to the `lookupswitch` and `tableswitch` opcodes)
- integer divisions (corresponding to the `idiv` and `ldiv` opcodes and the
  `divideUnsigned` methods)
- constant array indices (corresponding to the `*aload` opcodes and `get*`
  methods on array-like objects)
 
See more details about Jazzer implementation in [10].

#### Ruby

For Ruby there is a coverage-guided fuzzer named Ruzzy [11].
Like Atheris, Ruzzy uses libFuzzer for its coverage instrumentation
and fuzzing engine.

How Ruzzy instrumenting Ruby source code for fuzzing
(in short: instrumenting is hook-based):

Ruby has event hooking as well. The `TracePoint` module is the official Ruby
API for listening for certain types of events like calling a function,
returning from a routine, executing a line of code, and many more. When these
events fire, you can execute a callback function to handle the event however
you’d like. Fortunately, the public Ruby C API provides access to this event
hooking functionality via the `rb_add_event_hook2` function. This function
takes a list of events to hook and a callback function to execute whenever one
of those events fires.

See more details about Ruzzy implementation in [12], [13] and [14].

### References

1. https://github.com/ligurio/luzer
2. https://clang.llvm.org/docs/SanitizerCoverage.html
3. https://llvm.org/docs/LibFuzzer.html
4. https://www.lua.org/pil/23.2.html
5. https://github.com/lunarmodules/luacov/issues/90
6. https://github.com/google/atheris
7. https://github.com/google/atheris/blob/master/hooking.md
8. https://security.googleblog.com/2020/12/how-atheris-python-fuzzer-works.html
9. https://github.com/CodeIntelligenceTesting/jazzer
10. https://www.code-intelligence.com/blog/java-fuzzing-with-jazzer
11. https://github.com/trailofbits/ruzzy
12. https://dl.acm.org/doi/10.1145/3675741.3675749
13. https://bugs.ruby-lang.org/issues/20448
14. https://github.com/trailofbits/ruzzy/issues/9

[Sean Conner]

It was thus said that the Great Sergey Bronnikov once stated:
> Hello,

Hello.

> Obviously, existed Lua hook events could not help here and fuzzing engine
> will bruteforce variable `str` to get inside a condition. Value profiling
> could help with passing conditions with constants.
>

> By instrumenting `OP_EQ`, `OP_LE` and `OP_LT` instructions at runtime we
> could collect information about Lua code flow and extract values passed to
> comparison instructions.
>
> It is proposed to introduce a new hook event "branch", that will trigger a
> hook function on these three comparison instructions. A function passed to
> a hook mechanism will be executed with three arguments: first, second
> operand and a string with operation sign:

That's not the only place where conditionals happen. Example:

local tab
local x = tab and tab.foo or ""

which produces:

1 [1] VARARGPREP 0
2 [2] LOADNIL 0 0 ; 1 out
3 [3] TEST 0 0
4 [3] JMP 3 ; to 8
5 [3] GETFIELD 1 0 0 ; "foo"
6 [3] TEST 1 1
7 [3] JMP 1 ; to 9
8 [3] LOADK 1 1 ; ""
9 [3] RETURN 2 1 1 ; 0 out

That is a common idiom in my Lua code.

-spc

[Martin Eden]

Hello Sergey and Sean,

Code doesn't need comparisons to behave conditionally. In some cases it
doesn't even need "or"'s:

do
  local f =
    function(a)
      if (a == 15) then
        error()
      end
    end

  f(15)
end

<~>

do
  local f =
    function(a)
      local t =
        {
          [15] = function() error() end,
        }
      local mt =
        {
          __index = function() return function() end end,
        }
      setmetatable(t, mt)
      t[a]()
    end

  f(15)
end

-- Martin

[Sergey Bronnikov]

Hi, Sean!

> That's not the only place where conditionals happen. Example:

Sure, I know, here is what I described in the original letter,

I need jump instructions that change control the flow of the Lua script.

Although, processing only the special JMP ins will look inconsistent.

Sergey

[Sergey Bronnikov]

Hi, Martin!

> Code doesn't need comparisons to behave conditionally. In some cases it

> doesn't even need "or"'s:

You are right. And without conditions (aka branches in control flow) covering code

is much easier.

Snippet A

code below has no any conditionals, with any function argument

all lines will be covered:

```

local function()

  local a = 1

  local b = 10

  for i = a, b do

     local c = a and true or b

  end

end

```

Snippet B

code below has a conditional inside a loop, the value can be passed as a function argument.

What value should be passed to cover a code inside a condition? How to guess it automatically?

```

local function f(c)

  local a = 1

  local b = 10

  for i = a, b do

    if i == c then

      -- <...>

    end

  end

end

f(??)

```

Sergey