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 .
DETAILED ACTION
Status of the Application
Claims 1-5 have been examined in this application. This communication is the first action on the merits.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 8/15/2025 is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Claim Objections
Claim 2 is objected to because of the following informalities: claim 2 recites “RWS1U”. Neither the pending claims nor the Specification describe what the acronym “RWS1U” stands for. Appropriate correction and/or clarification is required. For Examination purposes and in light of the claims/claimed invention and the Specification, the Examiner considers RWS1U to stand for “Real world strong 1-unambiguity”.
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-5 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.
Claim 1 is directed towards a device, thus meeting the Step 1 eligibility criterion. Claim 1 does recite the abstract concept of a mental concept – i.e. mental process that can be performed in the human mind or using pen/paper, including an observation/evaluation/judgment, which has been identified as an abstract idea by the MPEP: determine whether a regular expression follows a syntax designated in advance / determine whether a condition indicating the processing time when the regular expression analyzes a character string is linear with respect to a length of the character string is satisfied.
This judicial exception is not integrated into a practical application. Claim 1 includes the additional element of processing circuitry, which represents a generic element. The additional element does not improve the functioning of the computing device or another technology/technical field, or apply or use the judicial exception in some other meaningful way beyond generally linking its use to a particular technological environment. The claim is directed to an abstract idea.
Claim 1 does not include additional elements that are sufficient to amount to significantly more than the judicial exception, because as noted above, the claimed computing element represents a generic computing element; it is recited at a high level of generality. The additional element does not improve the functioning of the computing device or another technology/technical field, or apply or use the judicial exception in some other meaningful way beyond generally linking its use to a particular technological environment. Therefore, Claim 1 does not amount to significantly more than the abstract idea itself. The claim is not patent eligible.
Independent claims 4, 5 are directed to a method and CRM, respectively, for performing similar claimed limitations to those of claim 1. Claims 4, 5 perform the claimed limitations using only generic components of a networked computer system. Therefore, claims 4, 5 are directed to an abstract idea
without significantly more for the reasons given in the discussion of claim 1.
Remaining dependent claims 2-3 further recite and narrow the abstract ideas of independent claim 1. The claims further recite the additional element of using RWS1U to repair and secure regular expressions against vulnerabilities (see the claimed limitations of claims 2 and 3), which does no more than apply or link the use of the recited judicial exception to a particular technological environment/field of use. The additional element does not, alone or in combination with the other additional element, improve the functioning of the computing device or another technology/technical field, or apply or use the judicial exception in some other meaningful way beyond generally linking its use to a particular technological environment. Therefore, the claims above do not amount to significantly more than the abstract idea itself. The claims are not patent eligible.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1, 2, 3, 4 are rejected under 35 U.S.C. 102 (a) (1) as being unpatentable over the Non-Patent Literature of “Automatic Repair of Vulnerable Regular Expressions” (Version1, Oct. 2020).
As per Claims 1, 4, the Non-Patent Literature discloses a device and method comprising:
Processing circuitry configured to: determine whether a regular expression follows a syntax designated in advance; determine whether a condition indicating the processing time when the regular expression analyzes a character string is linear with respect to a length of the character string is satisfied. (the circuitry represents a generic computing element that performs the claimed limitations. At least: page 2, lines 1-5; the engine is construed as the circuitry. At least: page 5, last 3 paras; page 2, second para: “We note that the repair problem is trivial for pure regular expressions and can be done by applying the standard powerset construction to translate the given expression to an equivalent deterministic finite automaton (DFA) and translate the DFA back to a regular expression via the standard
state-removal method [Sipser 1997]. While the resulting regular expression can be exponentially
larger, it is easy to see that it is invulnerable as the backtracking matching algorithm would only
take time linear in the input string length. Unfortunately, the DFA translation approach cannot be
applied to real-world regular expressions because real-world regular expressions are not regular
as remarked above and therefore there may be no DFA equivalent to the given expression. Another
issue which makes the problem highly non-trivial is the fact that the problem of deciding
the equivalence of real-world regular expressions is undecidable (in fact, with just the backreference
extension) [Freydenberger 2013]. This precludes the adoption of synthesis techniques that
require equivalence queries such as the L* algorithm [Angluin 1987].”)
As per Claim 2, the Non-Patent Literature discloses :
The processing circuitry is further configured to determine that the condition is satisfied when the regular expression satisfies RWS1U. (RWS1U is described in the Spec. as “RWS1U ensures that the processing time when the regular expression analyzes the character string is linear with respect to the length of the character string. “ – Spec, para 84. The Non-Patent Literature teaches the concept of ensuring that the processing time when the regular expression analyzes the character string is linear with respect to the length of the character string – at least page 5, last 3 paras; page 2, second para)
As per Claim 3, the Non-Patent Literature discloses :
convert the regular expression subjected to removal of lookahead and addition of brackets into a nondeterministic finite automaton, and determines that the condition is satisfied in a case where there is no vertex on the nondeterministic finite automaton such that there are different paths that can reach a same character only through the brackets and transition of an empty character. (at least: page 18 – last 3 paras, page 10: “In the translation process shown in Fig. 3, we maintain a global map I from capturing group indexes to states. I is initially empty and is updated whenever a capturing group (A )8 is encountered so that I(8) is set to be the initial state of the NFA constructed from A . First(@) is defined as follows: d0 ∈ First(@) iff d ∈ Ψ∗, 0 ∈ Σ, and there is a d0-labeled path from the state @. We define
d0♮ = 0, and First (@)♮ = {0 | d0 ∈ First (@)}.”, page 13: “Input: a regular expression A , a set of positive examples %, a set of negative examples #Output: a regular expression that satisfies the LTP and is consistent with % and #1: function Repair(A, %, #) 2: Q←{ A } 3: while Q is not empty do
4: t←Q.pop() 5: if % ⊆ !(t⊤) and # ∩ !(t⊥) = ∅ then 6: Φ←getInvulnerableConstraint(t, %, # )
7: if Φ is satisfiable then 8: return solution(t, Φ) 9: Q.push(expandHoles(t)) 10: Q.push(addHoles(t))”), page 6: “A positive (resp. negative) lookahead (?=A ) (resp. (?!A )) attempts to match A without any character consumption, and proceeds if the match succeeds (resp. fails) and backtracks otherwise. A”)
Claim Rejections - 35 USC § 103
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.
Claim 5 is rejected under 35 U.S.C. 103 as being unpatentable in view of the Non-Patent Literature of “Automatic Repair of Vulnerable Regular Expressions” (Version1, Oct. 2020) in further view of Chandramouli (20190018905).
As per Claim 5, the Non-Patent Literature teaches:
determining whether a regular expression follows a syntax designated in advance; determining whether a condition indicating the processing time when the regular expression analyzes a character string is linear with respect to a length of the character string is satisfied. (At least: page 5, last 3 paras; page 2, second para: “We note that the repair problem is trivial for pure regular expressions and can be done by applying the standard powerset construction to translate the given expression to an equivalent deterministic finite automaton (DFA) and translate the DFA back to a regular expression via the standard
state-removal method [Sipser 1997]. While the resulting regular expression can be exponentially
larger, it is easy to see that it is invulnerable as the backtracking matching algorithm would only
take time linear in the input string length. Unfortunately, the DFA translation approach cannot be
applied to real-world regular expressions because real-world regular expressions are not regular
as remarked above and therefore there may be no DFA equivalent to the given expression. Another
issue which makes the problem highly non-trivial is the fact that the problem of deciding
the equivalence of real-world regular expressions is undecidable (in fact, with just the backreference
extension) [Freydenberger 2013]. This precludes the adoption of synthesis techniques that
require equivalence queries such as the L* algorithm [Angluin 1987].”)
Chandramouli further teaches a non-transitory computer-readable recording medium storing therein a verification program that causes a computer to execute a process – at least: para 23.
It would have been obvious for someone skilled in the art at the time of the filing of the
invention to modify the Non-Patent Literature’s existing features, with Chandramouli’s feature of a non-transitory computer-readable recording medium storing therein a verification program that causes a computer to execute a process, since the CRM carries or stores computer-executable instructions and/or data structures – Chandramouli, para 23. Furthermore, the claimed invention is merely a
combination of old elements, and in the combination each element merely would have performed the
same function as it did separately, and one of ordinary skill in the art would have recognized that the
results of the combination were predictable.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
Billa (20200019404) teaches a memory including a non-deterministic finite automata (NFA) buffer configured to store a plurality of instructions defining an ordered sequence of instructions of at least a portion of an NFA graph, the portion of the NFA graph comprising a plurality of nodes arranged along a plurality of paths; and an NFA engine implemented in circuitry, the NFA engine comprising one or more NFA threads implemented in circuitry, each of the NFA threads comprising: a program counter storing a value defining a next instruction of the plurality of instructions; and a payload offset memory storing a value defining a position of a current symbol in an ordered sequence of symbols of a payload segment of payload data, the NFA engine further comprising a processing unit configured to: determine the current symbol and one or more subsequent symbols of the payload segment that satisfy a match condition specified by a subset of instructions of the plurality of instructions for a path of the plurality of paths, the subset of instructions comprising the next instruction and one or more subsequent instructions of the plurality of instructions; and in response to determining the current symbol and the one or more subsequent symbols of the payload segment that satisfy the match condition, output an indication that the payload data has resulted in a match. However, it lacks the combination of claimed elements of pending independent claims 1/4/5.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Alexandru Cirnu whose telephone number is (571) 272-7775. The examiner can normally be reached on 8:00 AM - 5:00 PM. 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, Ilana Spar can be reached on (571) 270-7537. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free).
/Alexandru Cirnu/
Primary Patent Examiner, Art Unit 3622
9/4/2026
Prosecution Insights