---
# System prepended metadata

title: IBM-NTU

---

# IBM-NTU

## Resource Constrained Pattern Matching

Paper link (NTU Template). https://www.overleaf.com/read/vpjhctznsksr

### Paper Structure 

1. Introduction
    * Importantce of pattern matching
        * as key component of deep packer inspection
    * Breif intro to pattern matching
        * different approaches and their pros, cons
        * resource consumption  
    * Deploy DPI on resource constrained is an issue
        * on smart NIC, for example
    * Shortcoming of prior work
        * DFA-based Rule Grouping requires much more memory
    * Intro and summarize Rule Balancer
    * Contribution

2. Background
    * Intro to Automaton-based pattern matching **(Ongoing**)
        * RegEx and pcre
        * DFA vs NFA, processing time and memory cost
    * Related Work
        * Rule grouping
        * Other complementary optimization approaches

3. Methodology
    * Problem Formulation
    :::danger
    Comment. So $k$ is the maximum number of $R_x$ ?
    :::
    :::success
    Response. Nope, it's the number of cores we have. 
    :::
    
    :::danger
    Comment. It looks like $R_1 \sim R_k$ are the input parameters, but it should be the output of your optimization problem. Please check.  
    :::
    :::success
    Response. They are inputs of our objective function and the output of the optimization. There is no contradiciton.  
    :::
    :::danger
    Comment. R is previously defined as regular expression, why are we using it "r" ?
    :::
    :::success
    Response. The captital letter R is used to represent **the set of regular expressions** while the small letter r is used to be a single regex.
    :::
    * Evolutionary Rule Balancer
        * Overview
        :::danger
        Comment. It is not clear of $a_i$. Is this a group or a rule?
        :::
        :::success
        Response. $a_i$ is the group ID for the $i$-th rule. The above sentence is the definition and the following is the explanation of the notation.
        :::
        :::danger
        Comment. "fitness of chromosome" would be a new concept for a reader. You might include some backgroudn explanation about the GA algorithm in high level. 
        :::
        :::success
        Response. Fix the order of the sentences
        :::
        :::danger
        Comment. Use vectorized image for 3.2 and 3.3
        :::
        :::success
        Response. What does vectorized image mean?
        :::
        :::danger
        Comment. Figures are not referenced in the text.
        :::
        :::success
        Response. Add reference in the context!
        :::
        * Regex Embedding
    * Case Study. NFA
        * Minimal Total NFA Size <--> Max-k Cut
        :::danger
        Comment. What is N?
        :::
        :::success
        Response. The number of states of NFA for input regular expressions, as explained in the table 3.1. Add more discriptions in the proposition.
        :::
        :::danger
        Comment. You may want to mention that K, the number of partitions, is given. 
        :::
        :::success
        Response. Yes, the number $k$ is supposed to be given. 
        :::
        :::danger
        Comment. This notation would be wrong, Please check. I think $V_i={r_{i_1}... r_{i_k}}$ would be correct. 
        :::
        :::success
        Response. The expression is correct. $k$ is the number of cores, not the maximal possible number of regex in a group.
        :::
        :::danger
        Comment. Can we simplify this equation? You can use references of previous equations. 
        :::
        :::success
        Response. Unfortunately, the answer is no. This is just direct corollary from the definition (3.7). We didn't make any concrete constrcution, So the expression cannot be simplified at the moment.
        :::
        :::danger
        Comment. What do you mean by "Hope to have" ? :) 
        :::
        :::success
        Response. Notice that the those paragraphs consists of not only the proofs, but also the motivations. The following expression is equivalent to reduce the problem to Max k-cut, which is our goal. That's why I said "Hope to have" :) 
        :::
        :::danger
        Comment. You may want to use different index for diferent i? r_{i,i} is a very confusion notation. 
        :::
        :::success
        Response. As a rule will be decomposed into many sub-patterns, I would like to use such notation. Maybe there is a more proper way to do so.
        :::
        :::danger
        Comment. This equation is very hard to follow. You may want to simplify the equation and put the details in the appendix. this comment applies to 3.13-3.15.
        :::
        :::success
        Response. Agree, still thinking ...
        :::
        * Minimal Largest NFA Size <--> Multi-depot Salesman 
        * Algorithm design
4. Experiment
    * Space-time tradeoff
    * Comparison of grouping algorithms
    * Evaluate NFA Size Estimator
    * Evaluate RegEx Embedding
5. Conclusion
