Azure / Azure/iotedgehubdev

Catastrophic Backtracking while using `Binds`

Open
#411 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
91
Forks
38
Avg merge
6m
Merged PRs (30d)
1

Description

Trying to use `Binds` in `createOptions` (binding Windows directory to Linux container) seems to raise catastrophic backtracking. The pattern responsible is MOUNT_WIN_REGEX
https://github.com/Azure/iotedgehubdev/blob/7eede7286a0603e565c8b183d090f2585521aae6/iotedgehubdev/compose_parser.py#L190

The following is the result of applying `MOUNT_WIN_REGEX` on different binds:
```
C:/:/app/ took 0.009343099998659454
C:/Folder1/:/app/ took 0.00018330000239075162
C:/Folder1/Folder2/:/app/ took 0.003711700002895668
C:/Folder1/Folder2/Folder3/:/app/ took 0.28317089999836753
C:/Folder1/Folder2/Folder3/Folder4/:/app/ took 18.772531900001923
```

as you can see, runtime grows exponentially. The fifth depth didn't return any result even after 5 minutes. This is the code I ran:
```
bind = "C:/"
counter = 1

def match(bind):

return regex.match(MOUNT_WIN_REGEX, bind)

while counter < 10:

result = timeit.timeit(lambda: match(f"{bind}:/app/"), number=1)
print(f"{bind}:/app/ took {result}")
bind += f"Folder{counter}/"
counter += 1
```

The reason seems to be the inline modifier `(?i)` in `MOUNT_MODE_REGEX`:
https://github.com/Azure/iotedgehubdev/blob/7eede7286a0603e565c8b183d090f2585521aae6/iotedgehubdev/constants.py#L48

The modifier somehow is propagated to the whole pattern. Removing the modifier will solve the catastrophic backtracking, but the pattern won't match paths with capital letters. By including the range `A-Z` in the pattern, the issue of backtracking resurfaces.

Suggestions:
- split the bind string by `:`, and apply smaller patterns on split strings instead of applying the huge regex patterns on the whole string
- instead of applying two huge regex patterns, break them up and use `if-elif` for pattern matching

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.