Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Continued Examination Under 37 CFR 1.114
A request for continued examination under 37 CFR 1.114, including the fee set forth in 37 CFR 1.17(e), was filed in this application after final rejection. Since this application is eligible for continued examination under 37 CFR 1.114, and the fee set forth in 37 CFR 1.17(e) has been timely paid, the finality of the previous Office action has been withdrawn pursuant to 37 CFR 1.114. Applicant's submission filed on 01/13/2026 has been entered.
Response to Arguments
Remarks
The Examiner acknowledges the applicant’s cancellation of claims 6, and 13. The Examiner acknowledges the applicant’s amendments to claims 1, and 8. The Examiner acknowledges the applicant’s new claims 15-17.
Telephone Interview
The Examiner acknowledges the telephone interview held on 11/20/2025 with the applicant.
Final Office Action
The Examiner acknowledges and generally agrees with the summarization of the Final Rejection Office Action mailed on 08/26/2025.
Drawings
The Examiner acknowledges the amendments to the drawings regarding labeling appropriate figures as “prior art”. The Examiner notes that the applicant argues that the replacement drawings include Figs. 1, 2, 6C, and 6D, but in the amended drawings there is no Fig. 1, 6C, or 6D. The amended figures seem to instead be figures 2, 5A, 5B, and 5C. The Examiner withdraws the drawing objections due to the amendments.
35 U.S.C. 112
The Examiner acknowledges the amendments to claim 8, and withdraws the 112(b) rejection from claim 8 due to amendment to the claim.
35 U.S.C. 101
The Examiner acknowledges and has fully considered the applicant’s arguments.
The applicant argues, Remarks page 10 paragraph 1, that the claims recite additional elements or a combination of elements that imposes a meaningful limit on the judicial exception. The Examiner respectfully disagrees for at least the reasons in the Final Rejection Office Action mailed on 08/26/2025.
The applicant further argues, Remarks page 10 paragraph 2, that the claims are directed to a specific technological solution to a concrete technological problem, ReDoS attacks. The Examiner respectfully points to the Final Office Action mailed on 08/26/2025, page 7 paragraphs 2-3, where the Examiner points out that the additional element regarding an ReDoS attack is considered generally linking to a particular field of use, thus not considered amounting to significantly more than the abstract idea.
The applicant further argues, Remarks page 10 paragraph 2, that the claimed invention has a combination of technical components requiring processing capabilities of computer systems to execute real-time algorithmic determination, dynamic algorithm selection, parallel state set iterative updating, and Glushkov automaton generation with specific structural properties. The Examiner respectfully disagrees, the Examiner respectfully points out that computer systems executing real-time algorithmic determination is an unclaimed element, and the rest of the mentioned features are considered mathematical algorithms, see the Final Rejection Office Action dated 08/26/2025, pages 5-8.
The applicant further argues, Remarks page 11 paragraph 1, the claims recite the integration of three technical elements in combination. The first technical element, a first matching algorithm and a second matching algorithm. These are considered mathematical algorithms, see the Final Rejection Office Action dated 08/26/2025, pages 5-8. The second technical element, in the matching step, a second matching algorithm is applied. This is considered a mathematical algorithm, see the Final Rejection Office Action dated 08/26/2025, pages 5-8. The applicant further argues regarding the second technical element, “thereby suppressing an increase in match confirmation time”, seemingly as an additional element. The Examiner respectfully notes that this is considered merely an intended result of the mathematical algorithm, see new reasons for rejection below. Furthermore the applicant argues, the specification describes improvement is achieved through parallel state processing with iterative set updates which provides the technical means to ensure polynomial time complexity of O(n*m) versus the exponential O(2^n) complexity of conventional implementations, the Examiner respectfully notes that these are unclaimed elements. Furthermore the applicant argues, seemingly as the third technical element, in the matching step, “the first matching algorithm is applied in response to the regular expression pattern including the extended grammar so that a path is searched by selecting one of several next states that moves through each character starting from a starting state, an adjacent state to the current state is separately stored along with a position on the character string, when there is an acceptance path among paths progressed in a state selected first, matching is terminated, and when the acceptance path is not searched, a new path is searched based on a most recently stored state and position.” The Examiner respectfully points out that this is considered a mathematical algorithm, see the Final Rejection Office Action dated 08/26/2025, pages 5-8.
The applicant further argues, Remarks page 12 paragraph 2, additional elements are applied to fundamentally block ReDoS by preventing exponential time growth. The applicant continues, arguing that the Glushkov automata structure helps prevent ReDoS compared to Thompson automata. The applicant continues, arguing that the Classical matching algorithm blocks the exponential increase in matching time. The applicant continues, arguing that the improvement to computer system performance and security represents a practical application to computer technology. The applicant continues, arguing that the claims do not preempt all approaches to regex matching or ReDoS prevention. The applicant continues, arguing that the claimed invention imposes meaningful limits that integrate the judicial exception into a practical application that improves computer functionality. The Examiner respectfully disagrees. The Examiner respectfully points to the MPEP 2106.04 (I) regarding preemption is not a standalone test for determining eligibility. Furthermore, the Examiner respectfully points to the Final Rejection Office Action dated 08/26/2025, pages 5-8 regarding the claimed limitation regarding ReDoS attack merely generally linking to a particular field of use, thus not considered amounting to significantly more than the abstract idea. Furthermore, the Examiner respectfully suggests that the described computer system performance is not shown through the claims, and instead is merely mathematical algorithms which in a manner that merely “apply it” on a computer, see the Final Rejection Office Action dated 08/26/2025, pages 5-8, and MPEP 2106.04(a)(2)(III)(C). See new reasons for rejection below due to amendments to the claims.
35 U.S.C. 103
The applicant argues that the prior art of Stewart et al. (U.S. Patent Application Publication 2013/0246324 A1), hereinafter “Stewart”, in view of Hron (Faculty of Information Technology CTU in Prague, Department of Theoretical Computer Science, Backreferences in practical regular expressions, Martin Hron, 27 May 2020), hereinafter “Hron”, and Tsay (U.S. Patent 8751466 B1), hereinafter “Tsay” does not teach or suggest every element of the claimed invention. The applicant argues that the listed prior art fails to teach or suggest “all next states that move through each character starting from a starting state are simultaneously considered”. The Examiner respectfully disagrees for at least the reasons listed in the Final Rejection Office Action, page 4 paragraph 1, page 11 paragraph 3, and respectfully points to the attachment to that office action, dated 08/26/2025, labeled Breadth-First_Search_FootNote regarding breadth first search.
The applicant continues, arguing, in Remarks page 15 paragraph 2 – page 16 paragraph 4, that Hron does not teach, analyzing patterns to detect extended grammar presence, conditional algorithm selection, classical matching for non-extended patterns, and the specific combination of Classical + Spencer algorithms. The Examiner respectfully points out that analyzing patterns to detect extended grammar presence is an argument for an unclaimed element. The Examiner respectfully points to the Final Rejection Office Action dated 08/26/2025, pages 10-11 regarding Hron teaching different methods of regular expression matching, as well as reasonings why different methods work well with particular regular expressions. The Examiner, in the Final Rejection Office Action dated 08/26/2025 asserted that it would have been obvious to combine these different teachings of regular expression matching because it would have been obvious to try, the Examiner asserts that it would have been obvious to try due to the fact that Hron already teaches these different regular expression matchings on the condition of different types of regular expressions, it would have been obvious to one of ordinary skill in the art at the time the invention was made to combine these different methods of regex matching taught in Hron into a singular unit, since it has been held that forming in one piece an article, which has formerly been formed in two pieces and put together, involves only routine skill in the art. Howard v. Detroit Stove Works, 150 U.S. 164 (1893). The Examiner further respectfully points out that “classical matching for non-extended patterns”, is an unclaimed element. Claim 1 refers to a second matching algorithm that is used when the regular expression does not include extended grammar, in which “all next states that move through each character starting from a starting state are simultaneously considered, by algorithmically maintaining a set of current states, processing each possible transition one by one for every in the set of current states, and updating the set of current states to reflect new states transitioned to”, which the Examiner respectfully points to the Final Rejection dated 08/26/2025, pages 10-12 regarding mapping to this limitation. The Examiner also respectfully points out that “Classical + Spencer algorithms” is an argument for an unclaimed element.
The applicant continues, Remarks page 16 paragraph 5, arguing that Hron’s methods of regular expression matching are fundamentally different from the claimed invention’s hybrid approach of selecting between classical matching and spencer algorithm based on runtime pattern analysis. The Examiner respectfully points out that this is an argument for unclaimed elements.
The applicant continues, Remarks page 16 paragraph 6, arguing that there is no teaching, suggestion, or motivation in Hron to abandon memory automata approach for certain pattern types, implement a pre-matching grammar detection step, selectively apply Classical matching vs. Spencer algorithm based on pattern structure, or use Glushkov automata as the underlying NFA representation. The Examiner respectfully points out that, as shown in the Final Rejection Office Action dated 08/26/2025, Hron teaches different methods (which is mapped to the claimed methods in the Office Action) for different circumstances of regular expression matching. Furthermore, the Examiner respectfully points out that “implement a pre-matching grammar detection step” is an argument for an unclaimed element. Furthermore, the Examiner respectfully points out that “selectively apply classical matching vs. Spencer algorithm” is an argument for an unclaimed element, however, if the applicant is meaning the described first and second matching algorithm (as Classical vs. Spencer algorithm), the Examiner respectfully points to the claim mappings within the Final Rejection Office Action dated 08/26/2025, regarding the first and second matching algorithms. Furthermore, the Examiner respectfully points out that the Glushkov automata NFA representation isn’t claimed in the independent but rather is a limitation in dependent claims (thus seemingly not necessarily needing to be the underlying NFA representation). Regardless, the Examiner respectfully points to the Final Rejection Office Action dated 08/26/2025 pages 11, 12, and 17 for claim mappings regarding Glushkov automata construction.
The applicant further argues, Remarks page 17 paragraph 1, that Hron does not teach selecting between applying a first matching algorithm and a second matching algorithm in response to whether the regular expression corresponds to the extended regular expression or not because it would have been obvious to try. The applicant further argues that “obvious to try” requires finite, predictable solutions, not unbounded experimentation. The applicant continues, arguing that the claimed combination requires recognizing that Glushkov automata eliminates ReDoS for non-extended patterns when using classical matching, and extended grammar detection enables selective algorithm application. The Examiner respectfully points out that the claimed limitation regarding ReDoS is in the independent claim and the claimed limitation regarding Glushkov construction is not until a later dependent claim, thus “Glushkov automata eliminates ReDoS for non-extended patterns when using classical matching” is an argument for unclaimed elements. Furthermore, the Examiner respectfully points out that “grammar detection” is an argument for unclaimed elements. Furthermore, the Examiner respectfully points out that, as the applicant stated, “obvious to try” requires finite, predictable solutions, not unbounded experimentation. The Examiner respectfully points to the Final Rejection Office Action dated 08/26/2025 regarding Hron teaching specific (limited number) of methods that give reasonings for the specific matching methods (predictable solutions), thus it would have been obvious to try.
The applicant further argues, Remarks page 17 paragraph 2, that Hron teaches away from the claimed invention, stating that the memory automata tool being described as much more resistant to catastrophic backtracking when compared to existing implementations teaches away from abandoning memory automata in favor of hybrid classical/Spencer approach, furthermore stating that Hron demonstrates memory automata successfully prevent ReDoS across all pattern types tested. The Examiner respectfully disagrees. The Examiner respectfully points out that Hron teaches a variety of methods for regular expression matching, as shown in the Final Rejection Office Action dated 08/26/2025, and that not only is it an argument for unclaimed elements to suggest that the claimed limitations require no memory automata, as well as classical/spencer matching (unless referring to the first and second algorithms as classical/spencer), but also that Hron teaching a method is resistant to catastrophic backtracking doesn’t teach away from the claimed invention. As shown in the claim mappings of the Final Rejection Office Action dated 08/26/2025, Hron teaches various regular expression matching methods for specified different reasons.
The applicant continues, arguing, Remarks page 17 paragraph 3, that Stewart an Tsay are silent regarding matching step that selects between applying a first matching algorithm and a second matching algorithm in response to whether a regular expression pattern corresponds to an extended regular expression or not. The Examiner respectfully points out that as stated in the Final Rejection Office Action dated 08/26/2025, Hron teaches the different regular expression matching methods and gives specific reasonings as to why to use the different methods, and that it would have been obvious to try to combine these methods, see the Final Rejection Office Action dated 08/26/2025, page 12.
The applicant continues, arguing, Remarks page 17 paragraph 4 – page 18 paragraph 1, that the prior art references, alone or in combination, lack all the claimed elements of independent claim 1, and the claimed elements are more than a predictable variation of Stewart in view of Hron and Tsay. The applicant further continues, arguing that independent claim 8 is too patentably distinguishable from the listed prior art. The Examiner respectfully disagrees for at least the reasons listed above, and the reasons listed in the Final Rejection Office Action dated 08/26/2025. Furthermore, see new reasons for rejection below due to amendments to the claims.
Newly Added Claims
The Examiner acknowledges the newly added claims, 15-17.
Conclusion
The Examiner acknowledges the applicant’s conclusion statement.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-3, 8-10, and 15-17 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more.
Regarding claim 1, under the Alice Framework Step 1, claim 1 falls within the four statutory
categories of patentable subject matter identified by 35 USC 101: a process, machine, manufacture, or a composition of matter.
Under the Alice Framework Step 2A prong 1, claim 1 recites an abstract idea, including both a mental process and mathematical concept. Specifically, claim 1 recites the following mental process, mathematical relationships, and mathematical formulas:
“a step of generating a nondeterministic finite automata based on a regular expression pattern; and a matching step of checking an acceptance path for a character string with respect to the nondeterministic finite automata, wherein the regular expression pattern is expressed as a regular expression or an extended regular expression, and the extended regular expression is applied with an extended grammar including a capture group, a dereference, a forward search, or a combination thereof, wherein the matching step selects between applying a first matching algorithm and a second matching algorithm in response to whether the regular expression pattern corresponds to the extended regular expression or not, wherein in the matching step, the second matching algorithm is applied in response to the regular expression pattern not including the extended grammar so that all next states that move through each character starting from a starting state are simultaneously considered, by algorithmically maintaining a set of current states, processing each possible transition one by one for every state in the set of current states, and updating the set of current states to reflect new states transitioned to, and when a current state includes an acceptance state at a time when all characters are consumed, it is determined that there is the acceptance, wherein in the matching step, the first matching algorithm is applied in response to the regular expression pattern including the extended grammar so that a path is searched by selecting one of several next states that moves through each character starting from a starting state, when there is an acceptance path among paths progressed in a state selected first, matching is terminated, and when the acceptance path is not searched, a new path is searched based on a most recently stored state and position.”
Applicant’s specification, page 8 lines 17-23, show that regular expression patterns are described in mathematical relationships and formulas. Generating a nondeterministic finite automata based on a regular expression pattern, such as a Glushkov automata described in the specification, is transformed through mathematical formulas. See Glushkov, V. M. The abstract theory of automata, Russian Mathematical Surveys, volume 16, no. 5, oct 1961. The matching step described in the claim is done through a matching algorithm, which is considered mathematical relationships, see applicant’s specification, page 6 lines 1-2. Furthermore, the claim is considered a mental process because it can be done with the human mind, or by a human using a pen and paper, see applicant’s drawings, figures 2- 10.
It is noted that the Examiner does not give patentable weight to the preamble of claim 1 because deletion of the preamble phrase does not affect the steps of the claimed invention. See MPEP 2111.02 (II)(¶4).
Under the Alice Framework Step 2A prong 2 analysis, claim 1 recites an additional element of, “wherein the matching step blocks a regular expression denial of service (ReDoS) attack”. This additional element is merely generally linking to a particular field of use, see MPEP 2106.04(d). Furthermore, claim 1 recites an additional element of, “thereby suppressing an increase in match confirmation time”. This additional element is not a positively recited claim limitation, but is merely an intended result of the prior limitations. Furthermore, this additional element is merely a direct consequence of the abstract idea, not from an improved technology, see MPEP 2106.04(d)(1), MPEP 2111.04. Furthermore, claim 1 recites an additional element of, “an adjacent state to the current state is separately stored along with a position on the character string”. Merely storing information, such as storing an adjacent state, comprise insignificant extra-solution activity. For these reasons, the claim is not integrated into a practical application.
Under the Step 2B analysis, for at least the reasons cited in the Step 2A prong 2 analysis, claim 1, when considered as a whole does not amount to significantly more than the abstract idea. The mere general linking to a particular field of use does not amount to significantly more than an abstract idea. See MPEP 2106.05(I)(A)(iv). Furthermore, the additional element of “thereby suppressing an increase in match confirmation time” is merely a direct consequence of the abstract idea, not from an improved technology, and thus does not amount to significantly more than an abstract idea, see MPEP 2106.05(a)(II) regarding “an improvement in the abstract idea itself is not an improvement in technology”. Furthermore, the additional element of storing information, such as storing an unselected state, comprise well understood, routine, and conventional activity. See MPEP 2106.05(d)(II)(iv). For these reasons, the claim does not amount to significantly more than the abstract idea.
Claims 2-3 are rejected for at least the reasons set forth with respect to claim 1. Claims 2-3 merely further limit the mental process and mathematical concept set forth in claim 1. Claim 2 and claim 3 recite further limitations on transforming a regular expression into a nondeterministic finite automata, which is considered both a mathematical concept and a mental process, as referenced above. Claims 2-3 recite no further additional elements that would require further analysis under Step 2A prong 2 and Step 2B.
Claim 15 is rejected for at least the reasons set forth with respect to claim 1. Claim 15 merely further limits the mathematical concept set forth in claim 1.
Under the Alice Framework Step 2A prong 1, claim 15 recites an abstract idea, including a mathematical concept. Specifically, claim 15 recites the following, mathematical relationships, and mathematical formulas:
“wherein, in the second matching algorithm, all next states that move through each character starting from the starting state are simultaneously considered.”
Under the Alice Framework Step 2A prong 2 analysis, claim 15 recites an additional element of, “so that an exponential increase in matching time is blocked”. This additional element is not a positively recited claim limitation, but is merely an intended result of the prior limitation. Furthermore, this additional element is merely a direct consequence of the abstract idea, not from an improved technology, see MPEP 2106.04(d)(1), MPEP 2111.04. For these reasons, the claim is not integrated into a practical application.
Under the Step 2B analysis, for at least the reasons cited in the Step 2A prong 2 analysis, claim 15, when considered as a whole does not amount to significantly more than the abstract idea. The additional element of “so that an exponential increase in matching time is blocked” is merely a direct consequence of the abstract idea, not from an improved technology, and thus does not amount to significantly more than an abstract idea, see MPEP 2106.05(a)(II) regarding “an improvement in the abstract idea itself is not an improvement in technology”.
Claim 16 IS rejected for at least the reasons set forth with respect to claims 1 and 2. Claim merely further limit the mental process and mathematical concept set forth in claims 1 and 2. Claim 16 recite further limitations on transforming a regular expression into a nondeterministic finite automata, which is considered both a mathematical concept and a mental process, as referenced above. Claim 16 recite no further additional elements that would require further analysis under Step 2A prong 2 and Step 2B.
Claim 17 is rejected for at least the reasons set forth with respect to claim 1 and 3. Claim 17 merely further limits the mathematical concept set forth in claims 1 and 3.
Under the Alice Framework Step 2A prong 1, claim 17 recites an abstract idea, including a mathematical concept. Specifically, claim 17 recites the following, mathematical relationships, and mathematical formulas:
“wherein the selection between applying the first matching algorithm and the second matching algorithm in combination with the Glushkov automata.”
Under the Alice Framework Step 2A prong 2 analysis, claim 17 recites an additional element of, “fundamentally blocking the ReDoS attack”. This additional element is merely generally linking to a particular field of use, see MPEP 2106.04(d). Furthermore, claim 1 recites an additional element of, “automata prevents exponential time growth in match confirmation time”. This additional element is merely an intended result of the prior limitations. Furthermore, this additional element is merely a direct consequence of the abstract idea, not from an improved technology, see MPEP 2106.04(d)(1), MPEP 2111.04. For these reasons, the claim is not integrated into a practical application.
Under the Step 2B analysis, for at least the reasons cited in the Step 2A prong 2 analysis, claim 1, when considered as a whole does not amount to significantly more than the abstract idea. The mere general linking to a particular field of use does not amount to significantly more than an abstract idea. See MPEP 2106.05(I)(A)(iv). Furthermore, the additional element of “prevents exponential time growth in match confirmation time” is merely a direct consequence of the abstract idea, not from an improved technology, and thus does not amount to significantly more than an abstract idea, see MPEP 2106.05(a)(II) regarding “an improvement in the abstract idea itself is not an improvement in technology”.
Regarding claim 8, under the Alice Framework Step 1, claim 8 falls within the four statutory categories of patentable subject matter identified by 35 USC 101: a process, machine, manufacture, or a composition of matter.
Under the Alice Framework Step 2A prong 1, claims 8-10 recite an abstract idea, including both a mental process and mathematical concept. Claims 8-10 are directed to an apparatus that would practice the methods as in claims 1-3 respectively. The claim 1-3 analysis applies equally to claims 8-10. Under the Alice Framework Step 2A prong 2 analysis, the claims recite the additional elements of a “processor” and “memory”, however, the processor and memory that are added in claims 8-10 are merely generally linked to the mental process, mathematical relationships, and mathematical calculations in a manner that merely “apply it” on a computer. See MPEP 2106.04(a)(2)(III)(C). For these reasons, the claims are not integrated into a practical application. Under the Step 2B analysis, for at least the reasons cited in the Step 2A analysis, the claim when considered as a whole does not amount to significantly more than the abstract idea.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-3, 15-17 and 8-10 rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Regarding claim 1, claim 1 recites the limitation of: “thereby suppressing an increase in match confirmation time”. It is unclear what is being compared to for determining what would constitute whether there has or has not been a suppression of an increase in match confirmation time. Claims 2-3, and 15-17 inherit the same deficiency as claim 1 based on dependence.
Regarding claim 8, claim 8 recites the limitation of: “thereby suppressing an increase in match confirmation time”. It is unclear what is being compared to for determining what would constitute whether there has or has not been a suppression of an increase in match confirmation time. Claims 9-10 inherit the same deficiency as claim 8 based on dependence.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-3, and 6 are rejected under 35 U.S.C. 103 as being unpatentable over Hron, in view of Tsay.
With regards to claim 1, Hron teaches:
An automata processing method by an automata processing apparatus, the method comprising: (Section 3.1 ¶4 regarding a method for regular expression to nondeterministic finite automata transformation (NFA); 3.2 ¶1 and ¶2 regarding methods for searching and matching regular expressions in an NFA);
a step of generating a nondeterministic finite automata based on a regular expression pattern; (Section 3.2 ¶1 regarding constructing an NFA from a regular expression);
and a matching step of checking an acceptance path for a character string with respect to the nondeterministic finite automata, (Fig. 3.1 regarding a final state 6; Fig. 3.2 regarding a final state 6; Section 3.4 Example 3.2 regarding matching and finding a path to the final state 6);
wherein the regular expression pattern is expressed as a regular expression or an extended regular expression, (Section 3.2.3 ¶1 regarding an NFA search without backtracking working well with classical regular expressions; Section 3.3.2 ¶1 regarding supporting extended regular expression by including support for backreferences);
and the extended regular expression is applied with an extended grammar including a capture group, a dereference, a forward search, or a combination thereof, (Section 3.3.2 ¶1 regarding supporting extended regular expression by including support for backreferences; Section 3.3.2 ¶2 regarding additional support to other extensions including a look-ahead search, otherwise known as a forward search; Section 2.2.3 Definition 2.2 regarding inclusion of dereference support; Section 3.3.2 ¶1 regarding use of a capture group);
Wherein a first matching algorithm and a second matching algorithm according to whether the regular expression pattern corresponds to the extended regular expression or not (Section 3.2 ¶1 and ¶2 regarding different methods of regular expression matching; Section 3.2.3 ¶1 regarding an NFA search without backtracking working well with classical regular expressions; Section 3.2.2 regarding a backtracking method of matching especially good for extended regular expressions that support backreferences);
wherein in the matching step, the second matching algorithm is applied in response to the regular expression pattern not including the extended grammar (Section 3.2.3 ¶1 regarding NFA matching without backtracking working well for classical regular expressions);
so that all next states that move through each character starting from the starting state are simultaneously considered, by algorithmically maintaining a set of current states, processing each possible transition one by one for every state in the set of current states, and updating the set of current states to reflect new states transitioned to,(Section 3.2.3 ¶1 regarding NFA matching without backtracking, updating based on all possible transitions; Section 5.1.3 Algorithm 2 regarding a matching algorithm searching all paths simultaneously1);
and when a current state includes an acceptance state at a time when all characters are consumed, it is determined that there is the acceptance path, thereby suppressing an increase in match confirmation time, (Section 5.1.1 ¶1 regarding how algorithm 2 starts at an initial state, and transverses the set of configurations until reaching an accepting, final, state; MPEP 2111.04(I) suggests that patentable weight not be given to a limitation that simply expresses the intended result of a process step positively recited. Regardless, the Examiner interprets the result, “thereby suppressing an increase in match confirmation time” as a direct consequence of the prior limitation, thus mapping of the prior limitation, as shown above, would consequently result in the same manner);
wherein in the matching step, the first matching algorithm is applied in response to the regular expression pattern including the extended grammar (Section 3.3.2 ¶1 regarding supporting extended regular expression; Section 3.3 Algorithm 1 regarding a first algorithm utilizing backtracking for extended regular expressions; Section 3.3 ¶1 regarding a description of the method of recursive backtracking for regular expression matching);
so that a path is searched by selecting one of several next states that moves through each character starting from a starting state, (Section 3.3 ¶1 regarding a description of the method of recursive backtracking for regular expression matching);
when there is an acceptance path among paths progressed in a state selected first, matching is terminated, (Section 3.4.1.1 Example 3.2 regarding an example showing the method of backtracking, and regular expression matching with an NFA until reaching the final state);
and when the acceptance path is not searched, a new path is searched based on a most recently stored state and position. (Section 3.4.1.1 Example 3.2 regarding an example showing the method of backtracking, and regular expression matching with an NFA until reaching the final state);
Hron does not explicitly teach:
the matching step selects between applying
However, Hron does teach different methods of regular expression matching as referenced above. Hron also teaches that these different methods work well with particular regular expressions, such as matching without backtracking, as in classical matching, working well with classical regular expressions as referenced above.
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine the teachings of multiple regular expression matching methods as taught by Hron with applying a matching method for a particular regular expression as taught by Hron, because it would have been obvious to try. See MPEP 2141(III)(E). Furthermore, , it would have been obvious to one of ordinary skill in the art at the time the invention was made to combine these different methods of regex matching taught in Hron into a singular unit, the teachings of multiple regular expression matching methods as taught by Hron with applying a matching method for a particular regular expression as taught by Hron, since it has been held that forming in one piece an article, which has formerly been formed in two pieces and put together, involves only routine skill in the art. Howard v. Detroit Stove Works, 150 U.S. 164 (1893).
Hron does not explicitly teach:
an adjacent state to the current state is separately stored along with a position on the character string,
However, Hron does teach backtracking if a match on a current path fails, and trying another path (Section 3.3 ¶1 regarding a description of the method of recursive backtracking for regular expression matching), this would imply that the not yet searched paths, along with a position on the character string, are stored in order to backtrack to them and continue matching. Hron further teaches, storing already visited paths (Section 3.3.1 ¶2 regarding storing previously visited configurations). Separately storing an already visited path, or state, is simply an inversion of separately storing an adjacent state.
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to try storing an adjacent state along with a position on the character string instead of the previously done inverse of storing paths previously visited, as taught by Hron, because it would have been obvious to try. See MPEP 2141 (III)(E).
Hron does not explicitly teach:
and wherein the matching step blocks a regular expression denial of service (ReDoS) attack.
However, Tsay teaches:
and wherein the matching step blocks a regular expression denial of service (ReDoS) attack. (Column 13 lines 41-44 regarding matching step of a regular expression engine designed to withstand ReDoS attacks)
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine Hron with the teaching of Tsay to withstand regular expression denial of service (ReDoS) attacks. [Tsay: Column 13 lines 43-44].
With regards to claim 2, Hron in view of Tsay teaches the automata processing method of claim 1, as referenced above.
Hron further teaches:
wherein the step of generating the nondeterministic finite automata includes transforming each node to correspond to a character of the character string. (Fig. 3.1; Fig. 3.2; Section 3.1 ¶4 regarding Glushkov algorithm being an NFA construction algorithm to be used).
With regards to claim 3, Hron in view of Tsay teaches the automata processing method of claim 1, as referenced above.
Hron further teaches:
wherein the step of generating the nondeterministic finite automata includes transforming the regular expression pattern into a Glushkov automata according to a Glushkov construction. (Fig. Section 3.1 ¶4 regarding Glushkov algorithm being an NFA construction algorithm to be used).
With regards to claim 15, Hron in view of Tsay teaches the automata processing method of claim 1, as referenced above.
Hron further teaches:
wherein, in the second matching algorithm, all next states that move through each character starting from the starting state are simultaneously considered so that an exponential increase in matching time is blocked. (Section 3.2.3 ¶1 regarding NFA matching without backtracking, updating based on all possible transitions; Section 5.1.3 Algorithm 2 regarding a matching algorithm searching all paths simultaneously1; MPEP 2111.04(I) suggests that patentable weight not be given to a limitation that simply expresses the intended result of a process step positively recited. Regardless, the Examiner interprets the result, “so that an exponential increase in matching time is blocked” as a direct consequence of the prior limitation, thus mapping of the prior limitation, as shown above, would consequently result in the same manner).
With regards to claim 16, Hron in view of Tsay teaches the automata processing method of claim 2, as referenced above.
Hron further teaches:
wherein the transforming each node includes transforming each node to correspond to only one character to eliminate epsilon transitions. (Fig. Section 3.1 ¶4 regarding Glushkov2 algorithm3 being an NFA construction algorithm to be used).
With regards to claim 17, Hron in view of Tsay teaches the automata processing method of claim 3, as referenced above.
Hron further teaches:
wherein the first matching algorithm and the second matching algorithm in combination with the Glushkov automata prevents exponential time growth in match confirmation time. (Section 3.2 ¶1 and ¶2 regarding different methods of regular expression matching; Section 3.2.3 ¶1 regarding an NFA search without backtracking working well with classical regular expressions; Section 3.2.2 regarding a backtracking method of matching especially good for extended regular expressions that support backreferences; MPEP 2111.04(I) suggests that patentable weight not be given to a limitation that simply expresses the intended result of a process step positively recited. Regardless, the Examiner interprets the result, “prevents exponential time growth in match confirmation time” as a direct consequence of the prior limitation, thus mapping of the prior limitation, as shown above, would consequently result in the same manner).
Hron does not explicitly teach:
selection between applying
However, Hron does teach different methods of regular expression matching as referenced above. Hron also teaches that these different methods work well with particular regular expressions, such as matching without backtracking, as in classical matching, working well with classical regular expressions as referenced above.
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine the teachings of multiple regular expression matching methods as taught by Hron with applying a matching method for a particular regular expression as taught by Hron, because it would have been obvious to try. See MPEP 2141(III)(E). Furthermore, , it would have been obvious to one of ordinary skill in the art at the time the invention was made to combine these different methods of regex matching taught in Hron into a singular unit, the teachings of multiple regular expression matching methods as taught by Hron with applying a matching method for a particular regular expression as taught by Hron, since it has been held that forming in one piece an article, which has formerly been formed in two pieces and put together, involves only routine skill in the art. Howard v. Detroit Stove Works, 150 U.S. 164 (1893).
Hron does not explicitly teach:
thereby fundamentally blocking the ReDoS attack for both the extended regular expression and the regular expression.
However, Tsay teaches:
thereby fundamentally blocking the ReDoS attack for both the extended regular expression and the regular expression. (Column 13 lines 41-44 regarding matching step of a regular expression engine designed to withstand ReDoS attacks)
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine Hron with the teaching of Tsay to withstand regular expression denial of service (ReDoS) attacks. [Tsay: Column 13 lines 43-44].
Claims 8-10 are rejected under 35 U.S.C. 103 as being unpatentable over Stewart, in view of Hron, and in further view of Tsay.
With regards to claim 8, Stewart teaches:
An automata processing apparatus, comprising: (Fig. 1; Fig. 4; ¶0016 regarding the description of the apparatus of figure 1 having components configured to execute an automaton);
a processor; and (Fig. 1 item 102; ¶0026 regarding inclusion of a processor);
a memory configured to store a program executed by the processor, (Fig. 1 items 102, and 104; ¶0026 regarding inclusion of a memory component; ¶0082 regarding storing instructions for the processor to execute);
wherein the processor is configured to execute the program to generate a nondeterministic finite automata based on a regular expression pattern, (¶0026 regarding a pattern analyzer component incorporating a processor and memory to generate an automaton; ¶0097 regarding the pattern analyzer generating the automaton corresponding to the patterns based on common symbols between patterns; Figs. 3, and 4; ¶0029 regarding the pattern analyzer generating automaton 300 (Fig. 3), and automaton 300 being a nondeterministic finite automaton; ¶0033 regarding Fig. 4 as a nondeterministic finite automaton);
and perform matching to check an acceptance path for a character string with respect to the nondeterministic finite automata, (Table 1 and Table 2 on pages 3, and 4);
wherein the regular expression pattern is expressed as a regular expression, (¶0013 regarding use of regular expression syntax);
wherein the processor is further configured to execute the program to perform the matching (¶0016 regarding a processor configured to execute a searching method against an automaton);
wherein the processor is further configured to execute the program to apply the matching algorithm in response to the regular expression pattern not including the extended grammar (¶0013 regarding use of regular expression syntax; ¶0025 regarding an interpreter module incorporating a processor and memory; ¶0045 regarding the interpreter module searching and matching through different paths of an automaton simultaneously);
so that all the next states that move through each character starting from a starting state are simultaneously considered, by algorithmically maintaining a set of current states, processing each possible transition one by one for every state in the set of current states, and updating the set of current states to reflect new states transitioned to, (¶0025 regarding an interpreter module incorporating a processor and memory; ¶0045 regarding the interpreter module searching and matching through different paths of an automaton simultaneously);
and when a current state includes an acceptance state at a time when all characters are consumed, it is determined that there is the acceptance path thereby suppressing an increase in match confirmation time, (Table 1 and Table 2 on pages 3 and 4; MPEP 2111.04(I) suggests that patentable weight not be given to a limitation that simply expresses the intended result of a process step positively recited. Regardless, the Examiner interprets the result, “thereby suppressing an increase in match confirmation time” as a direct consequence of the prior limitation, thus mapping of the prior limitation, as shown above, would consequently result in the same manner);
wherein the processor is further configured to execute the program to apply the matching algorithm, (¶0025 regarding an interpreter module incorporating a processor and memory; ¶0045 regarding the interpreter module searching and matching through different paths of an automaton simultaneously);
Stewart does not explicitly teach:
or an extended regular expression
and the extended regular expression is applied with an extended grammar including a capture group, a dereference, a forward search, or a combination thereof,
by selecting between applying a first matching algorithm and a second matching algorithm in response to whether the regular expression pattern corresponds to the extended regular expression or not,
a first matching algorithm
However, Hron teaches:
or an extended regular expression as referenced above
and the extended regular expression is applied with an extended grammar including a capture group, a dereference, a forward search, or a combination thereof, as referenced above
by selecting between applying a first matching algorithm and a second matching algorithm in response to whether the regular expression pattern corresponds to the extended regular expression or not, as referenced above
a first matching algorithm as referenced above
Therefore, it would have been obvious before the effective filing date of the claimed invention
to one of ordinary skill in the art to which said subject matter pertains to combine Stewart with the
second matching algorithm of Hron because extensions, such as look-ahead, look-behind, or pattern
recursion, can also be implemented when using the backtracking approach (Hron: Section 3.3.2 ¶2),
furthermore, it would have been obvious before the effective filing date of the claimed invention to one
of ordinary skill in the art to which said subject matter pertains to combine Stewart with applying a first
or second matching algorithm as referenced above because one method works well for classical regular
expressions (Hron: Section 3.2.3 ¶1), and because with another method, extensions, such as look-
ahead, look-behind, or pattern recursion, can also be implemented when using the backtracking
approach (Hron: Section 3.3.2 ¶2), furthermore it would have been obvious before the effective filing
date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to
combine Stewart with the extended regular expression grammar of Hron because extensions
significantly increases the expressive power (Hron: Future work ¶2).
Furthermore, Stewart in view of Hron does not explicitly teach:
and wherein the matching blocks a regular expression denial of service (ReDoS) attack.
However, Tsay teaches:
and wherein the matching blocks a regular expression denial of service (ReDoS) attack. (Column 13 lines 41-44 regarding matching step of a regular expression engine designed to withstand ReDoS attacks)
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine Stewart in view of Hron with the teaching of Tsay to withstand regular expression denial of service (ReDoS) attacks. [Tsay: Column 13 lines 43-44].
Furthermore, Stewart does not explicitly teach:
the first matching algorithm in response to the regular expression pattern including the extended grammar,
so that a path is searched by selecting one of several next states that moves through each character starting from a starting state,
an adjacent state to the current state is separately stored along with a position on the character string,
when there is an acceptance path among paths progressed in a state selected first, matching is terminated,
and when the acceptance path is not searched, a new path is searched based on a most recently stored state and position,
However, Hron teaches:
the first matching algorithm in response to the regular expression pattern including the extended grammar, as referenced above
so that a path is searched by selecting one of several next states that moves through each character starting from a starting state, as referenced above
an adjacent state to the current state is separately stored along with a position on the character string, as referenced above
when there is an acceptance path among paths progressed in a state selected first, matching is terminated, as referenced above
and when the acceptance path is not searched, a new path is searched based on a most recently stored state and position, as referenced above
Therefore, it would have been obvious before the effective filing date of the claimed invention
to one of ordinary skill in the art to which said subject matter pertains to combine Stewart with the
extended expression matching method of Hron because extensions, such as look-ahead, look-behind,
or pattern recursion, can also be implemented when using the backtracking approach (Hron: Section
3.3.2 ¶2).
With regards to claim 9, Stewart in view of Hron in further view of Tsay teaches the automata
processing apparatus of claim 8, as referenced above.
Stewart further teaches:
wherein the processor is further configured to execute the program to generate the nondeterministic finite automata by transforming each node to correspond to a character of the character string. (Fig. 4; ¶0048 regarding a Glushkov NFA form is utilized. A Glushkov2 NFA is similar to a Thompson NFA construction, except a Glushkov NFA gets rid of empty (epsilon) transitions3 between states. A Thompson NFA construction has each node, or state, correspond to either a character from the character string or an epsilon. Since Glushkov gets rid of the epsilon transitions of Thompson, this would indicate that each node corresponds to a character).
With regards to claim 10, Stewart in view of Hron in further view of Tsay teaches the automata processing apparatus of claim 8, as referenced above.
Stewart further teaches:
wherein the processor is further configured to execute the program to transform the regular expression pattern into a Glushkov automata according to a Glushkov construction to generate the nondeterministic finite automata. (Fig. 4; ¶0048 regarding a Glushkov NFA form is utilized).
Prior Art Made of Record
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
Regular Expression Matching Can Be Simple And Fast, Russ Cox, January 2007
This document discusses Regular expressions, as well as a few grammar extensions such as lookahead, and backreferences. This document further talks about transforming a regular expression into an NFA, as well as two different methods to search and match the regular expression in an NFA, one method being search all paths simultaneously and another method utilizing backtracking. Lastly, this document discusses potentially combining the two methods of regular expression matching. However, this document does not explicitly discuss Glushkov NFA.
K. Namjoshi and G. Narlikar, "Robust and Fast Pattern Matching for Intrusion Detection," 2010 Proceedings IEEE INFOCOM, San Diego, CA, USA, 2010, pp. 1-9, doi: 10.
This document discusses regular extended expressions and extended regular expressions. This document discusses constructing an NFA from the regular expression. Furthermore, this document discusses different methods searching and matching, including searching/matching paths simultaneously and another method of searching/matching paths utilizing backtracking. However, this document does not explicitly discuss Glushkov NFA.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JEROME ANTHONY KLOSTERMAN II whose telephone number is (571)272-0541. The examiner can normally be reached Monday - Friday 8:30am - 3:30pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Andrew Caldwell can be reached at 571-272-3702. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/J.A.K./ Examiner, Art Unit 2182 /EMILY E LAROCQUE/ Primary Examiner, Art Unit 2182
1 https://web.archive.org/web/20210725163813/https://www.interviewcake.com/concept/java/bfsRegarding breadth first search algorithm
2 Simon Fraser universityengaging the world. CourSys. (2018, November). https://coursys.sfu.ca/2018fa-cmpt-384-d1/pages/GlushkovRE
Regarding Glushkov NFA construction, each symbol is an NFA state. Furthermore regarding Glushkov being epsilon free NFAs
3 TCS -TR-A-14-73 TCS technical report fast regular expression matching. (2014, May). https://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_14_73/tcstr_14_73.pdf
Regarding Glushkov NFA not having epsilon transition