* [Bug translator/30395] Regex code has invalid memory reads caught by KASAN
2023-04-27 5:09 [Bug translator/30395] New: Regex code has invalid memory reads caught by KASAN agentzh at gmail dot com
@ 2023-04-27 5:10 ` agentzh at gmail dot com
2023-04-28 2:20 ` agentzh at gmail dot com
` (6 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: agentzh at gmail dot com @ 2023-04-27 5:10 UTC (permalink / raw)
To: systemtap
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.
^ permalink raw reply [flat|nested] 9+ messages in thread* [Bug translator/30395] Regex code has invalid memory reads caught by KASAN
2023-04-27 5:09 [Bug translator/30395] New: Regex code has invalid memory reads caught by KASAN agentzh at gmail dot com
2023-04-27 5:10 ` [Bug translator/30395] " agentzh at gmail dot com
@ 2023-04-28 2:20 ` agentzh at gmail dot com
2023-05-03 0:42 ` agentzh at gmail dot com
` (5 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: agentzh at gmail dot com @ 2023-04-28 2:20 UTC (permalink / raw)
To: systemtap
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.
^ permalink raw reply [flat|nested] 9+ messages in thread* [Bug translator/30395] Regex code has invalid memory reads caught by KASAN
2023-04-27 5:09 [Bug translator/30395] New: Regex code has invalid memory reads caught by KASAN agentzh at gmail dot com
2023-04-27 5:10 ` [Bug translator/30395] " agentzh at gmail dot com
2023-04-28 2:20 ` agentzh at gmail dot com
@ 2023-05-03 0:42 ` agentzh at gmail dot com
2023-05-03 0:46 ` agentzh at gmail dot com
` (4 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: agentzh at gmail dot com @ 2023-05-03 0:42 UTC (permalink / raw)
To: systemtap
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.
^ permalink raw reply [flat|nested] 9+ messages in thread* [Bug translator/30395] Regex code has invalid memory reads caught by KASAN
2023-04-27 5:09 [Bug translator/30395] New: Regex code has invalid memory reads caught by KASAN agentzh at gmail dot com
` (2 preceding siblings ...)
2023-05-03 0:42 ` agentzh at gmail dot com
@ 2023-05-03 0:46 ` agentzh at gmail dot com
2023-05-03 13:55 ` serhei at serhei dot io
` (3 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: agentzh at gmail dot com @ 2023-05-03 0:46 UTC (permalink / raw)
To: systemtap
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.
^ permalink raw reply [flat|nested] 9+ messages in thread* [Bug translator/30395] Regex code has invalid memory reads caught by KASAN
2023-04-27 5:09 [Bug translator/30395] New: Regex code has invalid memory reads caught by KASAN agentzh at gmail dot com
` (3 preceding siblings ...)
2023-05-03 0:46 ` agentzh at gmail dot com
@ 2023-05-03 13:55 ` serhei at serhei dot io
2023-05-05 16:12 ` serhei at serhei dot io
` (2 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: serhei at serhei dot io @ 2023-05-03 13:55 UTC (permalink / raw)
To: systemtap
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.
^ permalink raw reply [flat|nested] 9+ messages in thread* [Bug translator/30395] Regex code has invalid memory reads caught by KASAN
2023-04-27 5:09 [Bug translator/30395] New: Regex code has invalid memory reads caught by KASAN agentzh at gmail dot com
` (4 preceding siblings ...)
2023-05-03 13:55 ` serhei at serhei dot io
@ 2023-05-05 16:12 ` serhei at serhei dot io
2023-05-08 12:17 ` serhei at serhei dot io
2023-05-09 19:55 ` agentzh at gmail dot com
7 siblings, 0 replies; 9+ messages in thread
From: serhei at serhei dot io @ 2023-05-05 16:12 UTC (permalink / raw)
To: systemtap
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.
^ permalink raw reply [flat|nested] 9+ messages in thread* [Bug translator/30395] Regex code has invalid memory reads caught by KASAN
2023-04-27 5:09 [Bug translator/30395] New: Regex code has invalid memory reads caught by KASAN agentzh at gmail dot com
` (5 preceding siblings ...)
2023-05-05 16:12 ` serhei at serhei dot io
@ 2023-05-08 12:17 ` serhei at serhei dot io
2023-05-09 19:55 ` agentzh at gmail dot com
7 siblings, 0 replies; 9+ messages in thread
From: serhei at serhei dot io @ 2023-05-08 12:17 UTC (permalink / raw)
To: systemtap
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.
^ permalink raw reply [flat|nested] 9+ messages in thread* [Bug translator/30395] Regex code has invalid memory reads caught by KASAN
2023-04-27 5:09 [Bug translator/30395] New: Regex code has invalid memory reads caught by KASAN agentzh at gmail dot com
` (6 preceding siblings ...)
2023-05-08 12:17 ` serhei at serhei dot io
@ 2023-05-09 19:55 ` agentzh at gmail dot com
7 siblings, 0 replies; 9+ messages in thread
From: agentzh at gmail dot com @ 2023-05-09 19:55 UTC (permalink / raw)
To: systemtap
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.
^ permalink raw reply [flat|nested] 9+ messages in thread