[Bug translator/30395] New: Regex code has invalid memory reads caught by KASAN

[Bug translator/30395] New: Regex code has invalid memory reads caught by KASAN

[agentzh at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=30395

            Bug ID: 30395
           Summary: Regex code has invalid memory reads caught by KASAN
           Product: systemtap
           Version: unspecified
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: translator
          Assignee: systemtap at sourceware dot org
          Reporter: agentzh at gmail dot com
  Target Milestone: ---

Using the latest master branch of systemtap to run the following minimal .stp
scrpt with a KASAN-enabled Linux kernel (5.13.18 x86_64) yields a invalid
memory read error.

```
[  376.206051] stap_f0245f24e11ddd20c2e276120c521e3a_8363: loading out-of-tree
module taints kernel.
[  376.206169] stap_f0245f24e11ddd20c2e276120c521e3a_8363: module verification
failed: signature and/or required key missing - tainting kernel
[  376.601760] stap_f0245f24e11ddd20c2e276120c521e3a_8363 (a.stp): systemtap:
4.9/0.188, base: ffffffffc0b6b000, memory:
72data/56text/79ctx/524390net/366alloc kb, probes: 1
[  376.601791]
==================================================================
[  376.601802] BUG: KASAN: global-out-of-bounds in __stp_dfa0+0x826/0x850
[stap_f0245f24e11ddd20c2e276120c521e3a_8363]
[  376.601810] Read of size 1 at addr ffffffffc0b7ae86 by task stapio/8363

[  376.601819] CPU: 29 PID: 8363 Comm: stapio Tainted: G           OE    
5.13.18-orinc-Og+ #1
[  376.601822] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS
1.15.0-1.fc35 04/01/2014
[  376.601824] Call Trace:
[  376.601830]  dump_stack+0xa5/0xdc
[  376.601842]  print_address_description.constprop.0+0x18/0x130
[  376.601851]  ? __stp_dfa0+0x826/0x850
[stap_f0245f24e11ddd20c2e276120c521e3a_8363]
[  376.601856]  ? __stp_dfa0+0x826/0x850
[stap_f0245f24e11ddd20c2e276120c521e3a_8363]
[  376.601861]  kasan_report.cold+0x7f/0x111
[  376.601874]  ? __stp_dfa0+0x826/0x850
[stap_f0245f24e11ddd20c2e276120c521e3a_8363]
[  376.601881]  __stp_dfa0+0x826/0x850
[stap_f0245f24e11ddd20c2e276120c521e3a_8363]
[  376.601890]  probe_6374+0x148/0xd40
[stap_f0245f24e11ddd20c2e276120c521e3a_8363]
[  376.601896]  ? lock_is_held_type+0xe0/0x110
[  376.601917]  ? __stp_dfa0+0x850/0x850
[stap_f0245f24e11ddd20c2e276120c521e3a_8363]
[  376.601927]  enter_be_probe.constprop.0+0x3b8/0x690
[stap_f0245f24e11ddd20c2e276120c521e3a_8363]
[  376.601933]  ? _stp_error+0xd0/0xd0
[stap_f0245f24e11ddd20c2e276120c521e3a_8363]
[  376.601938]  ? lockdep_init_map_type+0x2c3/0x790
[  376.601945]  _stp_ctl_write_cmd.cold+0x1ab/0x2ec
[stap_f0245f24e11ddd20c2e276120c521e3a_8363]
[  376.601953]  ? _stp_cleanup_and_exit.part.0+0x720/0x720
[stap_f0245f24e11ddd20c2e276120c521e3a_8363]
[  376.601958]  ? lock_release+0x690/0x690
[  376.601961]  ? __cond_resched+0x15/0x30
[  376.601968]  ? selinux_file_permission+0x2f7/0x3e0
[  376.601983]  proc_reg_write+0x1a9/0x270
[  376.601994]  vfs_write+0x17b/0x7e0
[  376.602007]  ksys_write+0xe9/0x1b0
[  376.602011]  ? __ia32_sys_read+0xb0/0xb0
[  376.602015]  ? syscall_enter_from_user_mode+0x27/0x80
[  376.602021]  do_syscall_64+0x3d/0x80
[  376.602025]  entry_SYSCALL_64_after_hwframe+0x44/0xae
[  376.602028] RIP: 0033:0x7f835d8fc90f
[  376.602032] Code: 89 54 24 18 48 89 74 24 10 89 7c 24 08 e8 29 fd ff ff 48
8b 54 24 18 48 8b 74 24 10 41 89 c0 8b 7c 24 08 b8 01 00 00 00 0f 05 <48> 3d 00
f0 ff ff 77 31 44 89 c7 48 89 44 24 08 e8 5c fd ff ff 48
[  376.602035] RSP: 002b:00007fff529d3f50 EFLAGS: 00000293 ORIG_RAX:
0000000000000001
[  376.602042] RAX: ffffffffffffffda RBX: 0000000000000008 RCX:
00007f835d8fc90f
[  376.602045] RDX: 000000000000000c RSI: 00007fff529d3f80 RDI:
0000000000000004
[  376.602047] RBP: 0000000000008002 R08: 0000000000000000 R09:
00007f834d6fb700
[  376.602048] R10: 00007f834d6fb9d0 R11: 0000000000000293 R12:
000000000000000c
[  376.602050] R13: 0000000000000001 R14: 0000000000000000 R15:
00007fff529d4464

[  376.602064] The buggy address belongs to the variable:
[  376.602068]  _sub_I_65535_1+0x2906/0xa80
[stap_f0245f24e11ddd20c2e276120c521e3a_8363]

[  376.602074] Memory state around the buggy address:
[  376.602077]  ffffffffc0b7ad80: 06 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9
f9
[  376.602082]  ffffffffc0b7ae00: 00 f9 f9 f9 f9 f9 f9 f9 00 00 03 f9 f9 f9 f9
f9
[  376.602083] >ffffffffc0b7ae80: 06 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00
00
[  376.602085]                    ^
[  376.602087]  ffffffffc0b7af00: 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00
00
[  376.602089]  ffffffffc0b7af80: 00 01 f9 f9 f9 f9 f9 f9 00 00 04 f9 f9 f9 f9
f9
[  376.602090]
==================================================================
[  376.602092] Disabling lock debugging due to kernel taint
```

The stap script file that can always reproduce this error is like this:

```
probe oneshot {
    if ("32, 5" =~ "^([0-9]+), ([0-9]+)$") {
        println("matched: ", matched(1));
    }
}
```

The output of this script looks good:

```
matched: 32
```

But dmesg logs have the KASAN error as shown above. How to fix this, please?

-- 
You are receiving this mail because:
You are the assignee for the bug.

[Bug translator/30395] Regex code has invalid memory reads caught by KASAN

[agentzh at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=30395

--- Comment #1 from agentzh <agentzh at gmail dot com> ---
BTW, the master branch is at commit da9d1c42c9, which is the latest as of this
writing.

-- 
You are receiving this mail because:
You are the assignee for the bug.

[Bug translator/30395] Regex code has invalid memory reads caught by KASAN

[agentzh at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=30395

--- Comment #2 from agentzh <agentzh at gmail dot com> ---
This looks like an old bug. I can reproduce the same KASAN error with an older
stap version like 4.7.

-- 
You are receiving this mail because:
You are the assignee for the bug.

[Bug translator/30395] Regex code has invalid memory reads caught by KASAN

[agentzh at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=30395

--- Comment #3 from agentzh <agentzh at gmail dot com> ---
OK, I dug this up and found that the DFA generated by re2c used by the stap
translator indeed emits the wrong C code that will read beyond the \0 byte of
the constant C string.

Below is the bloody detail.

To make debugging easier, I minimized the original reproducer to the following
much simpler stap script:

```
probe oneshot {
    if ("3" =~ "^([0-9])$") {
        println("matched: ", matched(1));
    }
}
```

By inspecting the code location (like __stp_dfa0+0x356) given in the KASAN
report in the disassembly of the corresponding .ko file, I found that it should
be this machine instruction at fault:

```
/home/agentzh/git/systemtap-plus/test-regex/stap_1714_src.c:940
    switch (*YYCURSOR) {
    beed:   44 0f b6 65 02          movzx  r12d,BYTE PTR [rbp+0x2]
```

The YYCURSOR is a pointer pointing to the input string (in this case, the
literal C string "3"). Here, rbp points to the rsi, the 2nd argument of the
__stp_dfa0 function, i.e., the `str` parameter. And we already know that the
literal string "3" has only 2 bytes. So reading the 3rd byte via `[rbp+0x2]`
definitely leads to an invalid memory read.

The actual address given in the KASAN report might be off 1, but it is easy to
confirm by adding custom reading code around that location (this also confused
me at the beginning. alas).

Then I tried adding printk calls to the beginning of every state in the DFA of
the __stp_dfa0 function to confirm this further. (yes, I directly patched up
the generated stap_XXXX_src.c file generated by the stap translator and rebuild
the .ko to keep things easy.)

And the resulting dmesg output looks like this:

```
May 02 17:19:40 fed32-dev kernel: enter yystate0 pos=0 c=51
May 02 17:19:40 fed32-dev kernel: enter yystate3 pos=1 (c=0)
May 02 17:19:40 fed32-dev kernel: enter yystate5 pos=2
May 02 17:19:40 fed32-dev kernel:
==================================================================
May 02 17:19:40 fed32-dev kernel: BUG: KASAN: global-out-of-bounds in
__stp_dfa0+0x689/0x8ea [stap_1714]
...
```

We can see that the yystate5 moves YYCURSOR beyond the \0 byte and tries to
read it afterwards. And the KASAN report comes after yystate5 is entered.

One may wonder STAPSTRINGLEN is way larger than 2 bytes, but here it is a
constant C string that is allocated differently, i.e., inside the global data
section of the .ko (note the "global-out-of-bounds" word in the KASAN report).

One interesting thing is that we need special KASAN configuration options to
catch this issue. Unfortunately, the default KASAN options used by Fedora
kernels fail to do the job. Below are the KASAN options I used in the
reproducer:

```
CONFIG_KASAN_SHADOW_OFFSET=0xdffffc0000000000
CONFIG_HAVE_ARCH_KASAN=y
CONFIG_HAVE_ARCH_KASAN_VMALLOC=y
CONFIG_CC_HAS_KASAN_GENERIC=y
CONFIG_KASAN=y
CONFIG_KASAN_GENERIC=y
# CONFIG_KASAN_OUTLINE is not set
CONFIG_KASAN_INLINE=y
CONFIG_KASAN_STACK=y
CONFIG_KASAN_VMALLOC=y
# CONFIG_KASAN_MODULE_TEST is not set
```

Now that we know for sure it is a bug in the generated C code by stap's re2c
code emitter. But I still have no idea how to fix it in re2c. Maybe it's time
to upgrade to the latest version of the upstream re2c project. Thoughts?

-- 
You are receiving this mail because:
You are the assignee for the bug.

[Bug translator/30395] Regex code has invalid memory reads caught by KASAN

[agentzh at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=30395

--- Comment #4 from agentzh <agentzh at gmail dot com> ---
Just for a side note: Fedora's kernel-debug kernels do not enable KASAN at all.
I just checked and I'm shocked:

```
$ grep KASAN /boot/config-6.1.18-100.fc36.x86_64+debug
CONFIG_HAVE_ARCH_KASAN=y
CONFIG_HAVE_ARCH_KASAN_VMALLOC=y
CONFIG_CC_HAS_KASAN_GENERIC=y
# CONFIG_KASAN is not set
```

So we really need a KASAN-enabled kernel to reproduce the KASAN error report,
obviously :)

-- 
You are receiving this mail because:
You are the assignee for the bug.

[Bug translator/30395] Regex code has invalid memory reads caught by KASAN

[serhei at serhei dot io]

https://sourceware.org/bugzilla/show_bug.cgi?id=30395

Serhei Makarov <serhei at serhei dot io> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |serhei at serhei dot io

--- Comment #5 from Serhei Makarov <serhei at serhei dot io> ---
Taking a look at this problem. At first glance, it may be a case of
stapregex-dfa.cxx emit_final() needing to work differently when it is called as
a result of seeing the end NUL byte. It has some cases that continue on to the
next character if we accept in the middle of a string, which might be triggered
erroneously. Will need to go through the generated code more closely.

(The stapregex code is, in fact, a from-the-ground-up rewrite of the re2c
codebase which was... stylistically mismatched from our own coding style, to
put it mildly. So there is no option to 'just upgrade', alas.)

-- 
You are receiving this mail because:
You are the assignee for the bug.

[Bug translator/30395] Regex code has invalid memory reads caught by KASAN

[serhei at serhei dot io]

https://sourceware.org/bugzilla/show_bug.cgi?id=30395

--- Comment #6 from Serhei Makarov <serhei at serhei dot io> ---
There's a simple fix that I think will work, but I'll need to add a bit of code
to doublecheck/guard against the state 'to' doing anything except exiting on a
NUL. This shouldn't happen -- essentially, the below tweak feeds the DFA an
unending sequence of NULs, which it should terminate on soon-enough. (The extra
state transition is needed because of the rather fiddly TNFA bookkeeping I
added in 2017 to handle capture groups.)

Note that uncommenting STAPREGEX_DEBUG_DFA in stapregex-dfa.cxx will produce a
trace of visited states. I can clearly see how far it goes beyond the NUL when
matching against a statically allocated string :(

diff --git a/stapregex-dfa.cxx b/stapregex-dfa.cxx
index 3601b28dd..cae8e2494 100644
--- a/stapregex-dfa.cxx
+++ b/stapregex-dfa.cxx
@@ -1020,7 +1020,7 @@ span::emit_jump (translator_output *o, const dfa *d)
const

   if (to->accepts)
     {
-      emit_final(o, d);
+      emit_final(o, d, false /*saw_nul*/);
       return;
     }

@@ -1033,7 +1033,7 @@ span::emit_jump (translator_output *o, const dfa *d)
const
 /* Assuming the target DFA state of the span is a final state, emit code to
    cleanup tags and (if appropriate) exit with a final answer. */
 void
-span::emit_final (translator_output *o, const dfa *d) const
+span::emit_final (translator_output *o, const dfa *d, bool saw_nul) const
 {
   assert (to->accepts); // XXX: must guarantee correct usage of emit_final()

@@ -1087,6 +1087,11 @@ span::emit_final (translator_output *o, const dfa *d)
const
       o->indent(-1);
       o->newline() << "}";

+      if (saw_nul)
+          {
+              o->newline () << "/* XXX PROBLEM TRANSITION XXX */"; /* DEBUG */
+              o->newline () << "YYCURSOR--;"; /* SUGGESTED FIX: the next state
will encounter a repeated NUL */
+          }
       o->newline () << "goto yystate" << to->label << ";";
     }
 }
@@ -1119,10 +1124,11 @@ state::emit (translator_output *o, const dfa *d) const
       if (it->lb == '\0')
         {
           o->newline() << "case " << c_char('\0') << ":";
-          it->emit_final(o, d);
+          it->emit_final(o, d, true /* saw_nul */);
         }

       // Emit labels to handle all the other elements of the span:
diff --git a/stapregex-dfa.h b/stapregex-dfa.h
index c9a398fd7..065e1fe41 100644
--- a/stapregex-dfa.h
+++ b/stapregex-dfa.h
@@ -103,7 +103,7 @@ struct span {
   state_kernel *reach_pairs; // -- starting point for te_closure computation

   void emit_jump (translator_output *o, const dfa *d) const;
-  void emit_final (translator_output *o, const dfa *d) const;
+  void emit_final (translator_output *o, const dfa *d, bool saw_nul) const;
 };

 struct state {

-- 
You are receiving this mail because:
You are the assignee for the bug.

[Bug translator/30395] Regex code has invalid memory reads caught by KASAN

[serhei at serhei dot io]

https://sourceware.org/bugzilla/show_bug.cgi?id=30395

--- Comment #7 from Serhei Makarov <serhei at serhei dot io> ---
Pushed a fix. Will harden it slightly before I close the PR.

-- 
You are receiving this mail because:
You are the assignee for the bug.

[Bug translator/30395] Regex code has invalid memory reads caught by KASAN

[agentzh at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=30395

agentzh <agentzh at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|UNCONFIRMED                 |RESOLVED

--- Comment #8 from agentzh <agentzh at gmail dot com> ---
Confirmed that it was fixed by Serhei Makarov in commit 360aa454 etc.

-- 
You are receiving this mail because:
You are the assignee for the bug.