Repository: avast/yaramod (language: python)

Issue:
Regular expression idiom (a|b|) accepted by yara but not yaramod
A regular expression with an alternation having the empty string as one possibility, such as `(a|b|)`, produces a parse error in yaramod but is accepted by yara and works as expected. The python code below demonstrates the incompatibility.

As a workaround, the equivalent expression `(a|b)?` is accepted by both yara and yaramod.

```python
import yaramod
import yara

def test_rule(rule_txt, samples):
    try:
        ym = yaramod.Yaramod(yaramod.Features.AllCurrent)
        ym_file = ym.parse_string(rule_txt)
        print('\tyaramod successful parse')
    except yaramod.ParserError as e:
        print(f'\tyaramod failed parse: {str(e)}')

    try:
        rule = yara.compile(source=rule_txt)
        print('\tyara successful parse')
        for sample_txt in samples:
            if not rule.match(data=sample_txt):
                print(f'\tsample {sample} did not match!')
                return
        print('\tall samples matched as expected')
    except yara.Error as e:
        print(f'\tyara failed parse: {str(e)}')


GOOD_RULE = """
rule good {
strings:
    $re = /a(b|c|d)?z/
condition:
    $re
}
"""
BAD_RULE = """
rule bad {
strings:
    $re = /a(b|c|d|)z/
condition:
    $re
}
"""
SAMPLES = ["az", "abz", "acz", "adz"]

print('GOOD_RULE')
test_rule(GOOD_RULE, SAMPLES)
print('BAD_RULE')
test_rule(BAD_RULE, SAMPLES)
```


Discussion / hints:
Script output:
```
GOOD_RULE
	yaramod successful parse
	yara successful parse
	all samples matched as expected
BAD_RULE
	yaramod failed parse: Error at 4.20: Syntax error: Unexpected ), expected one of (, regexp ^, regexp $, regexp ., regexp escaped character, regexp ., regexp \w, regexp \W, regexp \s, regexp \S, regexp \d, regexp \D, regexp \b, regexp \B, regexp class
	yara successful parse
	all samples matched as expected
```
Also ran into this bug while parsing the rule at https://github.com/Neo23x0/signature-base/blob/master/yara/exploit_cve_2021_31166.yar

```python
>>> import yaramod
>>> y = yaramod.Yaramod(yaramod.Features.AllCurrent)
>>> yara_file = y.parse_file('Downloads/src/git/signature-base/yara/exploit_cve_2021_31166.yar')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
yaramod.ParserError: Error at Downloads/src/git/signature-base/yara/exploit_cve_2021_31166.yar:10.71: Syntax error: Unexpected ), expected one of (, regexp ^, regexp $, regexp ., regexp escaped character, regexp ., regexp \w, regexp \W, regexp \s, regexp \S, regexp \d, regexp \D, regexp \b, regexp \B, regexp class
>>>
```

Fix patch:
diff --git a/src/parser/parser_driver.cpp b/src/parser/parser_driver.cpp
index 16e89631..3827222b 100644
--- a/src/parser/parser_driver.cpp
+++ b/src/parser/parser_driver.cpp
@@ -993,6 +993,12 @@ void ParserDriver::defineGrammar()
 			std::shared_ptr<RegexpUnit> concat = std::make_shared<RegexpConcat>(args[2].getMultipleRegexpUnits());
 			return std::make_shared<RegexpOr>(std::move(arg), std::move(concat));
 		})
+		.production("regexp_or", "REGEXP_OR", [](auto&& args) -> Value {
+			// Special case in which we end alternation with empty string (like /(a|b|)/) which needs to be handled this way
+			// otherwise the grammar produces shift-reduce conflicts
+			std::shared_ptr<RegexpUnit> arg = std::move(args[0].getRegexpUnit());
+			return std::make_shared<RegexpOr>(std::move(arg), std::make_shared<RegexpText>(""));
+		})
 		;
 
 	_parser.rule("regexp_concat") // vector<shared_ptr<RegexpUnit>>


Test patch:
diff --git a/tests/cpp/parser_tests.cpp b/tests/cpp/parser_tests.cpp
index 7b5665ac..f6fe0602 100644
--- a/tests/cpp/parser_tests.cpp
+++ b/tests/cpp/parser_tests.cpp
@@ -1440,6 +1440,40 @@ rule regexp_with_unescaped_square_brackets_inside_class
 	EXPECT_EQ(input_text, driver.getParsedFile().getTextFormatted());
 }
 
+TEST_F(ParserTests,
+RegexpWithEmptyAlternationGroupWorks) {
+	prepareInput(
+R"(
+rule regexp_with_empty_alternation_group
+{
+	strings:
+		$1 = /(a|b|)/
+	condition:
+		all of them
+}
+)");
+
+	EXPECT_TRUE(driver.parse(input));
+	ASSERT_EQ(1u, driver.getParsedFile().getRules().size());
+
+	const auto& rule = driver.getParsedFile().getRules()[0];
+	EXPECT_EQ("regexp_with_empty_alternation_group", rule->getName());
+	EXPECT_EQ(Rule::Modifier::None, rule->getModifier());
+
+	auto strings = rule->getStrings();
+	ASSERT_EQ(1u, strings.size());
+
+	auto regexp1 = strings[0];
+	EXPECT_TRUE(regexp1->isRegexp());
+	EXPECT_EQ("$1", regexp1->getIdentifier());
+	EXPECT_EQ(R"(/(a|b|)/)", regexp1->getText());
+
+	EXPECT_EQ("all", rule->getCondition()->getFirstTokenIt()->getPureText());
+	EXPECT_EQ("them", rule->getCondition()->getLastTokenIt()->getPureText());
+
+	EXPECT_EQ(input_text, driver.getParsedFile().getTextFormatted());
+}
+
 TEST_F(ParserTests,
 InvalidCuckooRuleAccessTokenStream) {
 	prepareInput(