[FEATURE]hit_path support return hit NOT groupsv4.1.2

3 files changed, 306 insertions, 29 deletions

diff --git a/include/maat.h b/include/maat.h
index 0c440c3..b7cd2a9 100644
--- a/include/maat.h
+++ b/include/maat.h
@@ -30,6 +30,7 @@ struct maat;
 struct maat_hit_path {
     int Nth_scan;
     int vtable_id; // 0 is not a virtual table.
+    int NOT_flag;  // 1 means NOT clause(condition)
 	long long item_id;
 	long long sub_group_id;
 	long long top_group_id;
diff --git a/src/maat_compile.c b/src/maat_compile.c
index 513852f..e8cf867 100644
--- a/src/maat_compile.c
+++ b/src/maat_compile.c
@@ -30,6 +30,7 @@
 #define DEFAULT_GC_TIMEOUT_S 10
 #define MAX_SUPER_GROUP_CNT  128
 #define MAX_NOT_CLAUSE_NUM   8
+#define VTABLE_MAX_NOT_GROUP_NUM   8
 
 enum clause_not_flag {
     CLAUSE_NOT_FLAG_UNSET = 0,
@@ -148,6 +149,7 @@ struct maat_internal_hit_path {
 	long long group_id;
 	int Nth_scan;
 	int vtable_id;
+    int NOT_flag; // 1 means NOT clause
 };
 
 struct maat_compile_state {
@@ -1484,18 +1486,20 @@ void maat_compile_state_free(struct maat_compile_state *compile_state,
 }
 
 static void maat_compile_hit_path_add(UT_array *hit_paths, long long item_id,
-                                     long long group_id, int vtable_id, int Nth_scan)
+                                      long long group_id, int vtable_id, int NOT_flag,
+                                      int Nth_scan)
 {
     if (NULL == hit_paths || utarray_len(hit_paths) >= MAX_HIT_PATH_NUM) {
         return;
     }
     
 	struct maat_internal_hit_path new_path;
-
 	new_path.item_id = item_id;
 	new_path.Nth_scan = Nth_scan;
 	new_path.group_id = group_id;
 	new_path.vtable_id = vtable_id;
+    new_path.NOT_flag = NOT_flag;
+
 	utarray_push_back(hit_paths, &new_path);
 }
 
@@ -1572,6 +1576,7 @@ size_t compile_runtime_get_hit_paths(struct compile_runtime *compile_rt, int thr
             }
 
 			literal_id.vtable_id = hit_path_array[j].vtable_id;
+            literal_id.not_flag = hit_path_array[j].NOT_flag;
 			if (maat_compile_has_literal(compile, &literal_id)) {
                 if (hit_path_array[j].top_group_id < 0) {
                     hit_path_array[j].top_group_id = hit_path_array[j].sub_group_id;
@@ -1629,20 +1634,6 @@ static void maat_compile_state_update_indirect_hit_groups(UT_array *hit_group_ar
     }
 }
 
-static void maat_compile_state_update_hit_paths(struct maat_compile_state *compile_state,
-                                                struct maat_item *hit_items, size_t n_hit_items,
-                                                int vtable_id, int Nth_scan)
-{
-    if (NULL == compile_state) {
-        return;
-    }
-
-	for (size_t i = 0; i < n_hit_items; i++) {
-        maat_compile_hit_path_add(compile_state->internal_hit_paths, hit_items[i].item_id,
-                                  hit_items[i].group_id, vtable_id, Nth_scan);
-    }
-}
-
 static void exec_update_hit_clauses(struct maat_compile_state *compile_state,
                                     UT_array *clause_id_array)
 {
@@ -1703,10 +1694,11 @@ static inline int compare_group_id(const void *a, const void *b)
 	}
 }
 
-static int maat_compile_state_update_hit_not_clauses(struct maat_compile_state *compile_state,
-                                                     struct compile_runtime *compile_rt,
-                                                     long long *group_ids, size_t n_group_ids,
-                                                     int vtable_id)
+static size_t maat_compile_state_update_hit_not_clauses(struct maat_compile_state *compile_state,
+                                                        struct compile_runtime *compile_rt,
+                                                        long long *group_ids, size_t n_group_ids,
+                                                        int vtable_id, long long *NOT_group_ids_array,
+                                                        size_t NOT_group_ids_array_size)
 {
     if (NULL == compile_state || NULL == compile_rt) {
         return 0;
@@ -1716,8 +1708,10 @@ static int maat_compile_state_update_hit_not_clauses(struct maat_compile_state *
         qsort(group_ids, n_group_ids, sizeof(long long *), compare_group_id);
     }
 
-    int hit_group_cnt = 0;
+    size_t hit_NOT_group_cnt = 0;
     struct literal_clause *l2c_val = NULL, *tmp_l2c_val = NULL;
+
+    //NOTE: Each virtual table can reference up to VTABLE_MAX_NOT_GROUP_NUM groups
     HASH_ITER(hh, compile_rt->literal2not_clause_hash, l2c_val, tmp_l2c_val) {
         if (l2c_val->key.vtable_id != vtable_id) {
             continue;
@@ -1729,11 +1723,14 @@ static int maat_compile_state_update_hit_not_clauses(struct maat_compile_state *
             continue;
         }
 
+        if (hit_NOT_group_cnt < NOT_group_ids_array_size) {
+            NOT_group_ids_array[hit_NOT_group_cnt++] = l2c_val->key.group_id;
+        }
+
         exec_update_hit_clauses(compile_state, l2c_val->clause_ids);
-        hit_group_cnt++;
     }
 
-    return hit_group_cnt;
+    return hit_NOT_group_cnt;
 }
 
 void compile_runtime_ex_data_iterate(struct compile_runtime *compile_rt,
@@ -2278,10 +2275,12 @@ int maat_compile_state_update(int vtable_id, struct maat_item *hit_items,
     size_t super_group_cnt = group2group_runtime_get_super_groups(g2g_rt, hit_group_ids,
                                                                   hit_cnt, super_group_ids,
                                                                   MAX_SCANNER_HIT_GROUP_NUM);
-    if (1 == maat_inst->opts.hit_path_on) {
-        maat_compile_state_update_hit_paths(compile_state, hit_items, hit_cnt,
-                                            vtable_id, state->scan_cnt);
-    }    
+    if (1 == maat_inst->opts.hit_path_on && hit_cnt > 0) {
+        for (i = 0; i < hit_cnt; i++) {
+            maat_compile_hit_path_add(compile_state->internal_hit_paths, hit_items[i].item_id,
+                                      hit_items[i].group_id, vtable_id, 0, state->scan_cnt);
+        }
+    }
 
     if (1 == maat_inst->opts.hit_group_on) {
         maat_compile_state_update_direct_hit_groups(compile_state->direct_hit_groups,
@@ -2311,8 +2310,18 @@ int maat_compile_state_update(int vtable_id, struct maat_item *hit_items,
                                              hit_group_ids[i], vtable_id);
     }
 
-    int hit_not_cnt = maat_compile_state_update_hit_not_clauses(state->compile_state, compile_rt,
-                                                                hit_group_ids, hit_cnt, vtable_id);
+    long long hit_NOT_group_ids[VTABLE_MAX_NOT_GROUP_NUM];
+    size_t hit_not_cnt = maat_compile_state_update_hit_not_clauses(state->compile_state, compile_rt,
+                                                                   hit_group_ids, hit_cnt, vtable_id,
+                                                                   hit_NOT_group_ids, VTABLE_MAX_NOT_GROUP_NUM);
+    
+    if (1 == maat_inst->opts.hit_path_on && hit_not_cnt > 0) {
+        for (i = 0; i < hit_not_cnt; i++) {
+            maat_compile_hit_path_add(compile_state->internal_hit_paths, -1, hit_NOT_group_ids[i],
+                                      vtable_id, 1, state->scan_cnt);
+        }
+    }
+
     return (hit_cnt + hit_not_cnt);
 }
 
@@ -2407,6 +2416,7 @@ size_t maat_compile_state_get_internal_hit_paths(struct maat_compile_state *comp
             tmp_path.sub_group_id = internal_path->group_id;
             tmp_path.top_group_id = *p;
             tmp_path.vtable_id = internal_path->vtable_id;
+            tmp_path.NOT_flag = internal_path->NOT_flag;
             tmp_path.compile_id = -1;
 
            /* check if internal_path is duplicated from hit_path_array[] element */
diff --git a/test/maat_framework_gtest.cpp b/test/maat_framework_gtest.cpp
index 8e2d153..457512f 100644
--- a/test/maat_framework_gtest.cpp
+++ b/test/maat_framework_gtest.cpp
@@ -7197,6 +7197,272 @@ that the edges be all directed in the same direction.";
     state = NULL;
 }
 
+TEST_F(MaatCmdTest, HitPathHasNotGroup) {
+    const char *g2g_table_name = "GROUP2GROUP";
+	const char *g2c_table_name = "GROUP2COMPILE";
+	const char *compile_table_name = "COMPILE";
+	const char *http_sig_table_name = "HTTP_SIGNATURE";
+	const char *ip_table_name = "IP_CONFIG";
+	const char *keywords_table_name = "KEYWORDS_TABLE";
+    int thread_id = 0;
+    struct maat *maat_inst = MaatCmdTest::_shared_maat_inst;
+    struct maat_state *state = maat_state_new(maat_inst, thread_id);
+
+    /* compile1 */
+    long long compile1_id = maat_cmd_incrby(maat_inst, "TEST_SEQ", 1);
+    int ret = compile_table_set_line(maat_inst, compile_table_name, MAAT_OP_ADD, compile1_id,
+                                     "null", 2, 0);
+    EXPECT_EQ(ret, 1);
+
+    // !group1 -> compile1
+    long long group1_id = maat_cmd_incrby(maat_inst, "SEQUENCE_GROUP", 1);
+    ret = group2compile_table_set_line(maat_inst, g2c_table_name, MAAT_OP_ADD, group1_id,
+                                       compile1_id, 1, "HTTP_REQUEST_HEADER", 1, 0);
+    EXPECT_EQ(ret, 1);
+
+    // !(item1 -> group1) -> compile1
+    long long item1_id = maat_cmd_incrby(maat_inst, "SEQUENCE_REGION", 1);
+    ret = expr_table_set_line(maat_inst, http_sig_table_name, MAAT_OP_ADD, item1_id, group1_id,
+                              "math_theory", "URL", 0, 0, 0, 0); /*EXPR_TYPE_STRING MATCH_METHOD_SUB*/
+    EXPECT_EQ(ret, 1);
+
+    /* !(item1 -> group1) -> compile1
+                             /
+                    group21_/
+    */
+    long long group21_id = maat_cmd_incrby(maat_inst, "SEQUENCE_GROUP", 1);
+    ret = group2compile_table_set_line(maat_inst, g2c_table_name, MAAT_OP_ADD, group21_id,
+                                       compile1_id, 0, "HTTP_RESPONSE_HEADER", 2, 0);
+    EXPECT_EQ(ret, 1);
+
+    /* !(item1 -> group1) -> compile1
+                            /
+        group2 -> group21 _/
+    */
+    long long group2_id = maat_cmd_incrby(maat_inst, "SEQUENCE_GROUP", 1);
+    ret = group2group_table_set_line(maat_inst, g2g_table_name, MAAT_OP_ADD, group2_id,
+                                     group21_id, 0, 0);
+    EXPECT_EQ(ret, 1);
+
+    /*       !(item1 -> group1) -> compile1
+                                    /
+       item2 -> group2 -> group21 _/
+    */
+    long long item2_id = maat_cmd_incrby(maat_inst, "SEQUENCE_REGION", 1);
+    ret = expr_table_set_line(maat_inst, http_sig_table_name, MAAT_OP_ADD, item2_id, group2_id,
+                              "time=2020-02-12", "Cookie", 0, 0, 0, 0); /*EXPR_TYPE_STRING MATCH_METHOD_SUB*/
+    EXPECT_EQ(ret, 1);
+
+    /*
+          item1 -> group1 -> group11
+
+            !(item1 -> group1) -> compile1
+                                  /
+     item2 -> group2 -> group21 _/
+    */
+    long long group11_id = maat_cmd_incrby(maat_inst, "SEQUENCE_GROUP", 1);
+    ret = group2group_table_set_line(maat_inst, g2g_table_name, MAAT_OP_ADD, group1_id,
+                                     group11_id, 0, 0);
+    EXPECT_EQ(ret, 1);
+    
+    //item3 -> group3, group3 is not referenced by any compile.
+    long long item3_id = maat_cmd_incrby(maat_inst, "SEQUENCE_REGION", 1);
+    long long group3_id = maat_cmd_incrby(maat_inst, "SEQUENCE_GROUP", 1);
+    ret = ip_table_set_line(maat_inst, ip_table_name, MAAT_OP_ADD, item3_id, group3_id,
+                            IPv4, "220.181.38.158", "220.181.38.159", 0, 65535, 0);
+    EXPECT_EQ(ret, 1);
+
+    char temp[1024]={0};
+    //item4 -> group4, group4 is not referenced by any compile.
+    long long item4_id = maat_cmd_incrby(maat_inst, "SEQUENCE_REGION", 1);
+    long long group4_id = maat_cmd_incrby(maat_inst, "SEQUENCE_GROUP", 1);
+    ret = expr_table_set_line(maat_inst, keywords_table_name, MAAT_OP_ADD, item4_id, group4_id,
+                              str_escape(temp, sizeof(temp), "a finite and infinite"),
+                              NULL, 0, 0, 0, 0); /*EXPR_TYPE_STRING MATCH_METHOD_SUB*/
+    EXPECT_EQ(ret, 1);
+
+    sleep(WAIT_FOR_EFFECTIVE_S * 2);
+
+    const char* http_url = "en.wikipedia.org/wiki/Path_(chemistry_theory)";
+	const char* http_resp_hdr_cookie = "laptop=thinkpad X1 extrem;time=2020-02-12T15:34:00;"
+                                       "main[XWJOKE]=hoho; Hm_lvt_bbac0322e6ee13093f98d5c4b5a10912=1578874808;";
+
+    int http_req_table_id = maat_get_table_id(maat_inst, "HTTP_REQUEST_HEADER");
+    ASSERT_GT(http_req_table_id, 0);
+
+    ret = maat_state_set_scan_district(state, http_req_table_id, "URL", strlen("URL"));
+    EXPECT_EQ(ret, 0);
+
+    int Nth_scan = 0;
+
+    Nth_scan++;
+    long long results[ARRAY_SIZE] = {0};
+    size_t n_hit_result = 0;
+    ret = maat_scan_string(maat_inst, http_req_table_id, http_url, strlen(http_url),
+                           results, ARRAY_SIZE, &n_hit_result, state);
+    EXPECT_EQ(ret, MAAT_SCAN_HALF_HIT);
+
+    size_t scan_count = maat_state_get_scan_count(state);
+    EXPECT_EQ(scan_count, 1);
+
+    struct maat_hit_path hit_path[128];
+    memset(hit_path, 0, sizeof(hit_path));
+    int n_read = maat_state_get_hit_paths(state, hit_path, sizeof(hit_path));
+    EXPECT_EQ(n_read, 2);
+
+    int path_idx = 0;
+    EXPECT_EQ(hit_path[path_idx].Nth_scan, Nth_scan);
+	EXPECT_EQ(hit_path[path_idx].item_id, -1);
+	EXPECT_EQ(hit_path[path_idx].sub_group_id, group1_id);
+	EXPECT_EQ(hit_path[path_idx].top_group_id, group11_id);
+	EXPECT_EQ(hit_path[path_idx].vtable_id, http_req_table_id);
+    EXPECT_EQ(hit_path[path_idx].NOT_flag, 1);
+	EXPECT_EQ(hit_path[path_idx].compile_id, -1);
+
+    path_idx++;
+    EXPECT_EQ(hit_path[path_idx].Nth_scan, Nth_scan);
+	EXPECT_EQ(hit_path[path_idx].item_id, -1);
+	EXPECT_EQ(hit_path[path_idx].sub_group_id, group1_id);
+	EXPECT_EQ(hit_path[path_idx].top_group_id, -1);
+	EXPECT_EQ(hit_path[path_idx].vtable_id, http_req_table_id);
+    EXPECT_EQ(hit_path[path_idx].NOT_flag, 1);
+	EXPECT_EQ(hit_path[path_idx].compile_id, -1);
+
+    int http_res_table_id = maat_get_table_id(maat_inst, "HTTP_RESPONSE_HEADER");
+	ASSERT_GT(http_res_table_id, 0);
+
+    ret = maat_state_set_scan_district(state, http_res_table_id, "Cookie", strlen("Cookie"));
+    EXPECT_EQ(ret, 0);
+
+    Nth_scan++;
+    ret = maat_scan_string(maat_inst, http_res_table_id, http_resp_hdr_cookie,
+                           strlen(http_resp_hdr_cookie), results, ARRAY_SIZE,
+                           &n_hit_result, state);
+    EXPECT_EQ(ret, MAAT_SCAN_HIT);
+    EXPECT_EQ(n_hit_result, 1);
+    EXPECT_EQ(results[0], compile1_id);
+
+    scan_count = maat_state_get_scan_count(state);
+    EXPECT_EQ(scan_count, 2);
+
+    n_read = maat_state_get_hit_paths(state, hit_path, sizeof(hit_path));
+    EXPECT_EQ(n_read, 4);
+    
+    path_idx = 0;
+	EXPECT_EQ(hit_path[path_idx].Nth_scan, Nth_scan-1);
+	EXPECT_EQ(hit_path[path_idx].item_id, -1);
+	EXPECT_EQ(hit_path[path_idx].sub_group_id, group1_id);
+	EXPECT_EQ(hit_path[path_idx].top_group_id, group11_id);
+    EXPECT_EQ(hit_path[path_idx].NOT_flag, 1);
+    EXPECT_EQ(hit_path[path_idx].compile_id, -1);
+
+    path_idx++;
+    ASSERT_EQ(path_idx, 1);
+    EXPECT_EQ(hit_path[path_idx].Nth_scan, Nth_scan-1);
+	EXPECT_EQ(hit_path[path_idx].item_id, -1);
+	EXPECT_EQ(hit_path[path_idx].sub_group_id, group1_id);
+	EXPECT_EQ(hit_path[path_idx].top_group_id, group1_id);
+    EXPECT_EQ(hit_path[path_idx].NOT_flag, 1);
+    EXPECT_EQ(hit_path[path_idx].compile_id, compile1_id);
+
+    path_idx++;
+    ASSERT_EQ(path_idx, 2);
+	EXPECT_EQ(hit_path[path_idx].Nth_scan, Nth_scan);
+	EXPECT_EQ(hit_path[path_idx].item_id, item2_id);
+	EXPECT_EQ(hit_path[path_idx].sub_group_id, group2_id);
+	EXPECT_EQ(hit_path[path_idx].top_group_id, group21_id);
+	EXPECT_EQ(hit_path[path_idx].vtable_id, http_res_table_id);
+    EXPECT_EQ(hit_path[path_idx].NOT_flag, 0);
+	EXPECT_EQ(hit_path[path_idx].compile_id, compile1_id);
+
+    path_idx++;
+    ASSERT_EQ(path_idx, 3);
+	EXPECT_EQ(hit_path[path_idx].Nth_scan, Nth_scan);
+	EXPECT_EQ(hit_path[path_idx].item_id, item2_id);
+	EXPECT_EQ(hit_path[path_idx].sub_group_id, group2_id);
+	EXPECT_EQ(hit_path[path_idx].top_group_id, -1);
+	EXPECT_EQ(hit_path[path_idx].vtable_id, http_res_table_id);
+    EXPECT_EQ(hit_path[path_idx].NOT_flag, 0);
+	EXPECT_EQ(hit_path[path_idx].compile_id, -1);
+   
+    const char *keywords1 = "In math theory, a finite and infinite come up all the time.";
+    const char *keywords2= "a finite and infinite come up again.";
+
+    int keywords_table_id = maat_get_table_id(maat_inst, keywords_table_name);
+    ASSERT_GT(keywords_table_id, 0);
+
+    struct maat_stream *stream = maat_stream_new(maat_inst, keywords_table_id, state);
+    Nth_scan++;
+    ret = maat_stream_scan(stream, keywords1, strlen(keywords1), results, ARRAY_SIZE,
+                          &n_hit_result, state);
+    EXPECT_EQ(ret, MAAT_SCAN_HALF_HIT);
+    scan_count = maat_state_get_scan_count(state);
+    EXPECT_EQ(scan_count, 3);
+
+    n_read = maat_state_get_hit_paths(state, hit_path, sizeof(hit_path));
+    EXPECT_EQ(n_read, 5);
+
+    path_idx++;
+	ASSERT_EQ(path_idx, 4);
+	EXPECT_EQ(hit_path[path_idx].Nth_scan, Nth_scan);
+	EXPECT_EQ(hit_path[path_idx].item_id, item4_id);
+	EXPECT_EQ(hit_path[path_idx].sub_group_id, group4_id);
+	EXPECT_EQ(hit_path[path_idx].top_group_id, -1);
+	EXPECT_EQ(hit_path[path_idx].vtable_id, 0);
+    EXPECT_EQ(hit_path[path_idx].NOT_flag, 0);
+	EXPECT_EQ(hit_path[path_idx].compile_id, -1);
+
+    int ip_table_id = maat_get_table_id(maat_inst, ip_table_name);
+    ASSERT_GT(ip_table_id, 0);
+
+    Nth_scan++;
+    uint32_t ip_addr;
+    inet_pton(AF_INET, "220.181.38.158", &ip_addr);
+    uint16_t port = htons(17272);
+    ret = maat_scan_ipv4(maat_inst, ip_table_id, ip_addr, port, 6, results, ARRAY_SIZE,
+                         &n_hit_result, state);
+    EXPECT_EQ(ret, MAAT_SCAN_HALF_HIT);
+    scan_count = maat_state_get_scan_count(state);
+    EXPECT_EQ(scan_count, 4);
+ 
+    n_read = maat_state_get_hit_paths(state, hit_path, sizeof(hit_path));
+    EXPECT_EQ(n_read, 6);
+
+    path_idx++;
+	ASSERT_EQ(path_idx, 5);
+	EXPECT_EQ(hit_path[path_idx].Nth_scan, Nth_scan);
+	EXPECT_EQ(hit_path[path_idx].item_id, item3_id);
+	EXPECT_EQ(hit_path[path_idx].sub_group_id, group3_id);
+	EXPECT_EQ(hit_path[path_idx].top_group_id, -1);
+	EXPECT_EQ(hit_path[path_idx].vtable_id, 0);
+    EXPECT_EQ(hit_path[path_idx].NOT_flag, 0);
+	EXPECT_EQ(hit_path[path_idx].compile_id, -1);
+
+    Nth_scan++;   
+    ret = maat_stream_scan(stream, keywords2, strlen(keywords2), results, ARRAY_SIZE,
+                           &n_hit_result, state);
+    EXPECT_EQ(ret, MAAT_SCAN_HALF_HIT);
+    scan_count = maat_state_get_scan_count(state);
+    EXPECT_EQ(scan_count, 5);
+
+    n_read = maat_state_get_hit_paths(state, hit_path, sizeof(hit_path));
+    EXPECT_EQ(n_read, 7);
+
+    path_idx++;
+	ASSERT_EQ(path_idx, 6);
+	EXPECT_EQ(hit_path[path_idx].Nth_scan, Nth_scan);
+	EXPECT_EQ(hit_path[path_idx].item_id, item4_id);
+	EXPECT_EQ(hit_path[path_idx].sub_group_id, group4_id);
+	EXPECT_EQ(hit_path[path_idx].top_group_id, -1);
+	EXPECT_EQ(hit_path[path_idx].vtable_id, 0);
+    EXPECT_EQ(hit_path[path_idx].NOT_flag, 0);
+	EXPECT_EQ(hit_path[path_idx].compile_id, -1);
+
+    maat_stream_free(stream);
+    maat_state_free(state);
+    state = NULL;
+}
+
 TEST_F(MaatCmdTest, SameSuperGroupRefByMultiCompile) {
     char temp[1024]={0};
     int thread_id = 0;