JP7800680B2 - Correction device, correction method, and correction program - Google Patents

Description

The present invention relates to a correction device, a correction method, and a correction program.

In the real world, regular expressions are implemented as regular expression engines and used in a variety of situations. For example, regular expression engines are used in web applications that have a screen for entering email addresses to verify whether the string entered by the user is an email address. Regular expression engines are also used, for example, to sanitize data sent from external sources, extract elements, and in standard libraries of general-purpose programming languages.

However, the analysis algorithm based on backtracking, which is used in many regular expression engines, has the disadvantage that it can take an enormous amount of time to process depending on the combination of the data to be analyzed and the regular expression. A cyber attack that exploits this drawback is known as Regular Expression Denial of Service (ReDoS) (Reference: "Regular expression Denial of Service - ReDoS", https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS).

A regular expression that runs in linear time on a regular expression engine relative to the length of the string to be matched is called a non-fragile regular expression. Conversely, a regular expression that runs in exponential time on a regular expression engine relative to the length of the string to be matched is called a vulnerable regular expression.

Conventionally, one known technology for eliminating the threat of ReDoS is RFixer, which corrects errors in the language accepted by regular expressions (see, for example, Non-Patent Document 1). Another known method is to obtain non-vulnerable regular expressions by first converting them into deterministic finite automata and then converting them back (see, for example, Non-Patent Document 2).

Rong Pan, Qinheping Hu, Gaowei Xu, and Loris D’Antoni. 2019. Automatic Repair of Regular Expressions. Proc. ACM Program. Lang. 3, OOPSLA, Article 139 (Oct. 2019), 29 pages. Brink van der Merwe, Nicolaas Weideman, and Martin Berglund. 2017. Turning Evil Regexes Harmless. In Proceedings of the South African Institute of Computer Scientists and Information Technologists (SAICSIT’17). Association for Computing Machinery, New York, NY, USA, Article 38, 10 pages.

However, conventional techniques have the problem that the readability of the modified regular expressions can be poor.

For example, there may be multiple candidate regular expressions for which vulnerabilities have been fixed. Even if the candidate regular expressions after correction share the same functionality as regular expressions, they may differ in terms of human readability, and it is not always possible to obtain a highly readable regular expression.

In order to solve the above-mentioned problems and achieve the objectives, the correction device is characterized by having a calculation unit that calculates a priority for each template in which at least a portion of the range characters in a first regular expression have been replaced with placeholders, based on at least one of the processing cost of each template as a regular expression or its properties as a string, and a conversion unit that converts each of the templates in descending order of priority into a second regular expression in which the vulnerability of the first regular expression has been eliminated.

The present invention can improve the readability of modified regular expressions.

FIG. 1 is a diagram illustrating an example of the configuration of a correction device according to the first embodiment. FIG. 2 is a diagram showing an example of the syntax of a regular expression. FIG. 3 is a diagram illustrating an example of cost information. FIG. 4 is a diagram showing examples of Positive Examples and Negative Examples. FIG. 5 is a diagram for explaining a method for generating a set of character strings. FIG. 6 is a diagram for explaining a method for synthesizing regular expressions. FIG. 7 is a diagram illustrating a method for calculating a score based on costs. FIG. 8 is a diagram illustrating a method for calculating a score based on the number of characters. FIG. 9 is a diagram illustrating a method for calculating a score based on the cost and the number of characters. FIG. 10 is a diagram illustrating a method for calculating a score based on the degree of deviation as a character string. FIG. 11 is a flowchart showing the flow of processing by the repair device according to the first embodiment. FIG. 12 is a flowchart showing the flow of the regular expression correction process. FIG. 13 is a flowchart showing the flow of template storage processing. FIG. 14 illustrates an example of a computer that executes a correction program.

The following describes in detail embodiments of the correction device, correction method, and correction program according to the present application, with reference to the accompanying drawings. Note that the present invention is not limited to the embodiments described below.

[Configuration of the first embodiment]
First, the configuration of a correction device according to the first embodiment will be described with reference to Fig. 1. Fig. 1 is a diagram showing an example of the configuration of a correction device according to the first embodiment. As shown in Fig. 1, a correction device 10 receives an input of a regular expression before correction, corrects the input regular expression, and outputs the corrected regular expression.

The regular expressions in this embodiment are real-world extended regular expressions that conform to the syntax defined in Backus-Naur form (BNF). Figure 2 is a diagram showing an example of regular expression syntax. Regular expression r in Figure 2 is an example of a regular expression in this embodiment. Note that in the following explanation, "\" in a regular expression may be replaced with a backslash as appropriate.

In Figure 2, "C" is a set of characters, "x" is a string, and "i" is a natural number. The syntax in Figure 2 is used in existing regular expression engines (Reference: https://perldoc.perl.org/perlre.html).

Also, "." is a symbol that represents any single character. In other words, "." is syntactic sugar for the range character "[C]" in Figure 2. Also, a set of characters that does not match the range character "[C]" can be written as "[^C]". Also, the empty set is written as "[]", which means that it does not match any characters.

Returning to Figure 1, we will explain each part of the correction device 10. As shown in Figure 1, the correction device 10 has an interface unit 11, a memory unit 12, and a control unit 13.

The interface unit 11 is an interface for inputting, outputting, and communicating data. For example, the interface unit 11 accepts data input from input devices such as a keyboard and a mouse. Also, for example, the interface unit 11 outputs data to output devices such as a display and a speaker.

The interface unit 11 may also be a device for communicating over a network (e.g., a NIC (Network Interface Card)).

The memory unit 12 is a storage device such as an HDD (Hard Disk Drive), SSD (Solid State Drive), or optical disk. The memory unit 12 may also be a data-rewritable semiconductor memory such as RAM (Random Access Memory), flash memory, or NVSRAM (Non-Volatile Static Random Access Memory). The memory unit 12 stores the OS (Operating System) and various programs executed by the correction device 10.

The memory unit 12 stores replacement candidate syntax information 121. The replacement candidate syntax information 121 is a set of regular expression syntax to be replaced with range characters or holes in a regular expression or template.

For example, replacement candidate syntax information 121 is "□□, □|□, □*, (□), ＼i, (?=□), (?!□), (?<=□), (?<!□)". Here, "□" is a hole. Holes and templates will be explained later.

Cost information 122 is information that defines the cost of processing each regular expression operator. Cost information 122 also includes the cost of holes. The costs are used in calculating priorities, which will be described later. Figure 3 shows an example of cost information. Details of costs will be described later.

The control unit 13 controls the entire correction device 10. The control unit 13 is, for example, an electronic circuit such as a CPU (Central Processing Unit), MPU (Micro Processing Unit), or GPU (Graphics Processing Unit), or an integrated circuit such as an ASIC (Application Specific Integrated Circuit) or FPGA (Field Programmable Gate Array).

The control unit 13 also has an internal memory for storing programs and control data that define various processing procedures, and executes each process using the internal memory. The control unit 13 also functions as various processing units as various programs run. For example, the control unit 13 has a generation unit 131 and a synthesis unit 132.

The generation unit 131 generates Positive Examples, which are a set of strings that are accepted by the regular expression before modification, and Negative Examples, which are a set of strings that are rejected by the regular expression before modification.

Note that the Positive Examples are an example of the first set, and the Negative Examples are an example of the second set. The regular expression before correction is an example of the first regular expression.

Figure 4 shows examples of Positive Examples and Negative Examples. Here, we assume that the regular expression before correction is ".*.*=.*". In this case, "=", "abcd==", "==abcd", and "ab=c" included in the Positive Examples match the regular expression ".*.*=.*" (are accepted). On the other hand, "abc" included in the Negative Examples does not match the regular expression ".*.*=.*" (is rejected).

The generation unit 131 can enumerate all strings that combine characters up to a certain length, and classify each string as a Positive Example if it is accepted by the regular expression, or as a Negative Example if it is rejected. The generation unit 131 may also generate Positive Examples and Negative Examples using the method described in Non-Patent Document 1.

If all strings were simply listed, an explosive number of examples would be generated. To avoid this, the generation unit 131 may generate Positive Examples and Negative Examples from only the characters that appear in the regular expression before modification.

For example, if the regular expression is "ab[c-d]*", the generation unit 131 generates a candidate string by combining "a" and "b" with one character randomly selected from "[c,d]".

Figure 5 is a diagram explaining how to generate a set of strings. In the example of Figure 5, the regular expression before correction is ".*.*@example[.]com". In this case, the generation unit 131 classifies the strings "@example.com", "a@example.com", and "gc@example.com", which are accepted by the regular expression ".*.*@example[.]com", into Positive Examples. On the other hand, the generation unit 131 classifies the strings "example.com", "@.com", "@examplecom", "@example.", etc., which are rejected by the regular expression ".*.*@example[.]com", into Negative Examples.

The synthesis unit 132 synthesizes a modified regular expression, which is a regular expression in which the range characters in the pre-modification regular expression are replaced with a predetermined syntax, and which accepts character strings in the Positive Examples and rejects character strings in the Negative Examples. Note that the modified regular expression is an example of a second regular expression.

The processing by the synthesis unit 132 can be broadly divided into a step of creating a template and a step of assigning to the template.

In the template creation step, the synthesis unit 132 creates the template by replacing range characters in the regular expression with placeholders.

In the template assignment step, the synthesis unit 132 assigns a predetermined syntax to the placeholder to synthesize a non-vulnerable regular expression. Hereafter, the placeholder will be referred to as a hole and represented by a "□".

The synthesis unit 132 performs processing while maintaining a prioritized queue. Priorities are assigned to templates stored in the queue.

When the synthesis unit 132 retrieves an element from the queue, it prioritizes retrieving the stored template with the highest priority. At the start of processing, the synthesis unit 132 stores the unmodified regular expression in the queue as a template. Note that the unmodified regular expression stored in the queue will inevitably have the highest priority.

First, we will explain the steps of creating a template executed by the synthesis unit 132. If the template retrieved from the queue contains range characters, the synthesis unit 132 replaces the range characters contained in the template with holes. Note that range characters are represented, for example, as "[C]" or ".". On the other hand, if the template retrieved from the queue contains holes, the synthesis unit 132 may replace one of the holes with a specified syntax.

For example, the synthesis unit 132 creates templates "□*.*=.*", ".*□*=.*", and ".*.*=□*" by replacing the range characters of the unmodified regular expression ".*.*=.*" stored in the queue as a template, and stores them in the queue. Note that once a template has been extracted, it is discarded.

In this way, the synthesis unit 132 replaces at least some of the range characters in the pre-modification regular expression with holes, and synthesizes the modified regular expression based on a template in which the replaced holes are further replaced with a specified syntax.

Furthermore, the synthesis unit 132 can replace holes with syntax such as "□□", "□|□", "□*", "(□)", "＼i", "(?=□)", "(?!□)", "(?<=□)", or "(?<!□)" contained in the replacement candidate syntax information 121. In this case, the synthesis unit 132 synthesizes a modified regular expression based on a template in which the hole contained in the template has been replaced with one of the predetermined syntaxes containing holes, "□□", "□|□", "□*", "(□)", "＼i", "(?=□)", "(?!□)", "(?<=□)", or "(?<!□)" (where □ represents a hole).

Next, we will explain the steps of assigning to a template executed by the synthesis unit 132. Here, we assume that the synthesis unit 132 repeats the steps of creating a template, and creates, for example, the template "□*□*=.*" and stores it in the queue. For example, the synthesis unit 132 obtains the template "□*□*=.*" by replacing the range character "." on the left side of the template "□*.*=.*" with a hole.

The synthesis unit 132 searches for a range character assignment that satisfies the conditions for the holes contained in the template. For example, the synthesis unit 132 performs the search using a Satisfiability Modulo Theories (SMT) solver (e.g., the Z3 solver).

If the template is "□*□*=.*" and the Positive Examples and Negative Examples are as shown in Figure 4, the synthesis unit 132 can obtain the assignment "[]*[^=]*=.*" by searching. The synthesis unit 132 removes the empty set "[]" and obtains the regular expression "[^=]*=.*".

Here, the synthesis unit 132 functions as a conversion unit. That is, the synthesis unit 132 converts each template, in descending order of priority, into a modified regular expression in which the vulnerability of the pre-modification regular expression has been eliminated. For example, the synthesis unit 132 converts the template "□*□*=.*" into the regular expression "[^=]*=.*".

The regular expression "[^=]*=.*" accepts the Positive Examples in Figure 4 and rejects the Negative Examples. Furthermore, the regular expression "[^=]*=.*" contains at most one match for the same character, so it can be said to be invulnerable.

As a result, the synthesis unit 132 can convert the template into a modified regular expression, which is a regular expression in which the placeholders in the template are replaced with a specified syntax, and which accepts Positive Examples and rejects Negative Examples.

In this embodiment, as mentioned above, a regular expression that runs in linear time on a regular expression engine relative to the length of the string to be matched is called a non-fragile regular expression. Conversely, a regular expression that runs in, for example, exponential time on a regular expression engine relative to the length of the string to be matched is called a fragile regular expression.

The synthesis of robust regular expressions by the synthesis unit 132 utilizes the strongly one-unambiguous property devised by Koch and Scherzinger et al. (Reference: Christoph Koch and Stefanie Scherzinger. 2007. Attribute Grammars for Scalable Query Processing on XML Streams. The VLDB Journal 16, 3 (July 2007), 317-342.) which has been improved to accommodate real-world extensions.

Strongly one-unambiguous means that the next operation that the regular expression engine processes is uniquely determined once the character currently being parsed is determined.

Similarly, if the regular expression before modification is ".*.*@example[.]com", the synthesis unit 132 can obtain the non-vulnerable regular expression "[^@]*@example[.]com", as shown in Figure 6.

[Priority calculation]
The synthesis unit 132 calculates the priority when storing a regular expression or a template in a queue. At this time, the synthesis unit 132 functions as a calculation unit.

For each template in which at least some of the range characters in the first regular expression have been replaced with placeholders, the synthesis unit 132 calculates a priority based on at least one of the processing cost of each template as a regular expression or its properties as a string.

Cost information 122 is an example of the processing cost for a regular expression. Furthermore, the properties of the string include, for example, the number of characters (size, length), the degree of deviation or similarity from a specific string, etc.

The following describes examples of score calculation methods. The synthesis unit 132 may use each of the calculation methods described here individually, or may use a combination of the calculation methods. The smaller the score, the higher the priority. The synthesis unit 132 may use the inverse of the score or the value obtained by inverting the sign of the score as the priority.

Figure 7 is a diagram explaining a method for calculating a score based on cost. As shown in Figure 7, the synthesis unit 132 can calculate a priority (score) according to the cost of each regular expression operator included in a predetermined template.

The cost for each operator is as shown in Figure 3. For example, the cost increases depending on the complexity of handling the operator and holes. In the example in Figure 3, the cost of a fixed character is 0, and the cost of an operator that indicates any character (for example, a range character) is 1. Note that fixed characters such as "a", "1", and "/" are abbreviations for "[a]", "[1]", and "[/]", respectively, and are a type of range character, but their complexity is extremely low, so their cost is set to 0.

Furthermore, operators that select or repeat characters and strings have a cost of 3. Operators that obtain, reference, or search for specified strings or patterns (capture, backreference, various lookaheads, various lookbehinds, etc.) have a cost of 7.

A hole is one that is replaced with one of "□□, □|□, □*, (□), ＼i, (?=□), (?!□), (?<=□), (?<!□)" or assigned a range character as a search result. Therefore, the cost of a hole is set to 11, which is the sum of 7, the maximum cost of operators added after replacement, 1, the cost of a range character, and 3, the cost of a selection operator since one of them is selected.

Note that the method for determining costs is not limited to that described here and may be determined in any manner.

Returning to Figure 7, the template "(□|□)*.*=.*" contains two holes with a cost of 11, one capture with a cost of 7, one choice with a cost of 3, three repeats with a cost of 3, and two range characters with a cost of 1. Therefore, the synthesis unit 132 adds up the costs and calculates the score of the template "(□|□)*.*=.*" as 43.

In addition, the template "□*□*=.*" contains two holes with a cost of 11, three repetitions with a cost of 3, and one range character with a cost of 1. Therefore, the synthesis unit 132 adds up the costs and calculates the score of the template "□*□*=.*" as 32.

Furthermore, the template "(?=□)*@hoge＼.com" contains one hole with a cost of 11, one positive lookahead with a cost of 7, and one repetition with a cost of 3. Therefore, the synthesis unit 132 adds up the costs and calculates the score of the template "(?=□)*@hoge＼.com" as 21.

Figure 8 is a diagram explaining how to calculate a score based on the number of characters. As shown in Figure 8, the synthesis unit 132 calculates the priority according to the number of characters in the template.

As shown in Figure 8, the number of characters in the template "(□|□)*.*=.*" is 11, so the synthesis unit 132 calculates the score of the template "(□|□)*.*=.*" as 11.

Furthermore, since the number of characters in the template "□*□*=.*" is 7, the synthesis unit 132 calculates the score of the template "□*□*=.*" as 7.

Furthermore, since the number of characters in the template "(?=□)*@hoge＼.com" is 16, the synthesis unit 132 calculates the score of the template "(?=□)*@hoge＼.com" to be 16.

Figure 9 is a diagram illustrating a method for calculating a score based on cost and number of characters. As shown in Figure 9, the synthesis unit 132 may calculate a final score by multiplying the score based on cost described in Figure 7 by the score based on the number of characters described in Figure 8.

As shown in Figure 9, the cost-based score of the template "(□|□)*.*=.*" is 43, and the score based on the number of characters is 11, so the synthesis unit 132 multiplies each score to calculate a final score of 473.

Furthermore, since the cost-based score of the template "□*□*=.*" is 32 and the score based on the number of characters is 7, the synthesis unit 132 multiplies each score and calculates a final score of 224.

Furthermore, since the cost-based score of the template "(?=□)*@hoge＼.com" is 21 and the score based on the number of characters is 16, the synthesis unit 132 multiplies each score and calculates a final score of 336.

Figure 10 is a diagram explaining a method for calculating a score based on the degree of deviation as a string. Here, the synthesis unit 132 calculates the Levenshtein distance between the template and the regular expression before correction as the score. The Levenshtein distance is an example of the degree of deviation between strings. Note that the regular expression before correction is assumed to be ".*.* = .*".

As shown in Figure 10, the Levenshtein distance between the template "(□|□)*.*=.*" and the regular expression ".*.*＝.*" is 5, so the synthesis unit 132 calculates the score as 5.

In this case, the transformation can be done in five steps: "(□|□)*.*=.*" → "□|□)*.*＝.*" → "|□)*.*＝.*" → "□)*.*＝.*" → ")*.*＝.*" → ".*.*＝.*", so the Levenshtein distance is 5.

Furthermore, since the Levenshtein distance between the template "□*□*=.*" and the regular expression ".*.*＝.*" is 2, the synthesis unit 132 calculates the score as 2.

According to the method described here, the better the readability, the higher the priority (the lower the score). For example, the more costly an operator (lookahead, capture, etc.) is, the worse the readability is likely to be. Also, for example, the more characters there are, the worse the readability is likely to be. Also, for example, the more the corrected regular expression deviates from the regular expression before correction, the more difficult it will be for humans to decipher the meaning of the corrected regular expression, and the worse the readability is likely to be.

[Processing of the First Embodiment]
11 is a flowchart showing the flow of processing by the editing device according to the first embodiment. First, the editing device 10 receives input of a regular expression (step S10).

Next, the correction device 10 generates a set of strings (Positive Examples) that are accepted by the input regular expression (step S20). The correction device 10 also generates a set of strings (Negative Examples) that are rejected by the input regular expression (step S30).

For example, the modification device 10 can create an extended automaton from the input pre-modification regular expression and generate a set of strings that cover all paths of the extended automaton.

Next, the modification device 10 generates (synthesizes) a regular expression based on the input regular expression, the accepted string, and the rejected string (step S40). The modification device 10 then outputs the generated regular expression (step S50).

Figure 12 is a flowchart showing the flow of the regular expression synthesis process. The process in Figure 12 corresponds to step S40 in Figure 11. First, the correction device 10 stores the input regular expression in a queue as a template (step S401).

Next, the correction device 10 retrieves the template with the highest priority from the queue (step S402).

Next, the modification device 10 searches for an assignment of range characters to the hole that accepts accepted strings, rejects rejected strings, and satisfies the vulnerability conditions (step S403).

The modification device 10 determines whether an assignment exists for the search results (step S404). If an assignment does not exist for the search results (step S404, No), the modification device 10 replaces the range character with a hole or replaces the hole with a predetermined pattern (step S405). The predetermined pattern is, for example, a syntax such as "□□", "□|□", "□*", "(□)", "\i", "(?=□)", "(?!□)", "(?<=□)", or "(?<!□)". Note that if the input regular expression stored in the queue in step S401 becomes the target of the search in step S403, it is considered that no assignment exists (No) in step S404.

Then, the correction device 10 stores the template processed in step S405 in a queue (step S406). The processed template here is a template in which the range character has been replaced with a hole, or a template in which the hole has been replaced with a specified pattern.

On the other hand, if a search result assignment exists (step S404, Yes), the modification device 10 synthesizes a non-vulnerable regular expression based on the search result assignment (step S407).

Figure 13 is a flowchart showing the flow of the template storage process. The process in Figure 13 corresponds to step S406 in Figure 12. As shown in Figure 13, first, the correction device 10 calculates the score of the template (step S4061). The correction device 10 can calculate the score based on the cost, number of characters, the degree of deviation between the template and the original regular expression, etc.

Next, the editing device 10 determines the priority based on the score (step S4062). For example, the editing device 10 determines that the smaller the score, the higher the priority.

Then, the correction device 10 stores the template in a queue along with its priority (step S4063). The templates in the queue are retrieved in order of highest priority.

[Effects of the First Embodiment]
As described above, for each template in which at least some of the range characters in the first regular expression have been replaced with placeholders, the synthesis unit 132 calculates a priority based on at least one of the processing cost of the template as a regular expression and the properties of the template as a character string. The synthesis unit 132 converts each template in descending order of priority into a second regular expression in which the vulnerability of the first regular expression has been resolved. This makes it possible to improve the readability of the corrected regular expression.

The generation unit 131 also generates a first set, which is a set of strings accepted by the first regular expression, and a second set, which is a set of strings rejected by the first regular expression. The synthesis unit 132 converts the template into a second regular expression, which is a regular expression in which placeholders in the template are replaced with a predetermined syntax and which accepts strings in the first set and rejects strings in the second set.

The synthesis unit 132 calculates the priority according to the cost of each operator in the regular expression included in the predetermined template. This avoids the use of high-cost operators (lookahead, capture, etc.) in the modified regular expression as much as possible, thereby improving readability.

The synthesis unit 132 also calculates the priority based on the number of characters in the template. This allows the number of characters in the corrected regular expression to be reduced as much as possible, thereby improving readability.

The synthesis unit 132 calculates a priority based on the degree of deviation between the template and the first regular expression as character strings. This allows the corrected regular expression to be as close as possible to the original regular expression, thereby improving readability. Furthermore, the higher the priority, the more likely it is to be adopted as the final output in subsequent processing, thereby improving the readability of the corrected regular expression.

[System configuration, etc.]
Furthermore, the components of each device shown in the figure are functional concepts and do not necessarily have to be physically configured as shown. In other words, the specific form of distribution and integration of each device is not limited to that shown, and all or part of the devices can be functionally or physically distributed or integrated in any unit depending on various loads, usage conditions, etc. Furthermore, all or any part of the processing functions performed by each device can be realized by a CPU (Central Processing Unit) and a program analyzed and executed by the CPU, or can be realized as hardware using wired logic. Note that the program may be executed not only by the CPU but also by other processors such as a GPU.

Furthermore, among the processes described in this embodiment, all or part of the processes described as being performed automatically can be performed manually, or all or part of the processes described as being performed manually can be performed automatically using known methods. In addition, the information, including the processing procedures, control procedures, specific names, various data, and parameters shown in the above documents and drawings, can be changed as desired unless otherwise specified.

[program]
In one embodiment, the correction device 10 can be implemented by installing a correction program that executes the above-described correction process as package software or online software on a desired computer. For example, by executing the above-described correction program on an information processing device, the information processing device can function as the correction device 10. The information processing device referred to here includes desktop and notebook personal computers. Other information processing devices also include mobile communication terminals such as smartphones, mobile phones, and PHS (Personal Handyphone Systems), as well as slate terminals such as PDAs (Personal Digital Assistants).

The correction device 10 can also be implemented as a correction server device that uses a terminal device used by a user as a client and provides services related to the above correction processing to the client. For example, the correction server device is implemented as a server device that provides a correction service that takes an uncorrected regular expression as input and outputs a corrected regular expression. In this case, the correction server device may be implemented as a web server, or as a cloud that provides services related to the above correction processing through outsourcing.

Figure 14 is a diagram showing an example of a computer that executes a patch program. The computer 1000 has, for example, memory 1010 and a CPU 1020. The computer 1000 also has a hard disk drive interface 1030, a disk drive interface 1040, a serial port interface 1050, a video adapter 1060, and a network interface 1070. Each of these components is connected by a bus 1080.

The memory 1010 includes a ROM (Read Only Memory) 1011 and a RAM (Random Access Memory) 1012. The ROM 1011 stores a boot program such as a BIOS (Basic Input Output System). The hard disk drive interface 1030 is connected to a hard disk drive 1090. The disk drive interface 1040 is connected to a disk drive 1100. A removable storage medium such as a magnetic disk or optical disk is inserted into the disk drive 1100. The serial port interface 1050 is connected to a mouse 1110 and a keyboard 1120, for example. The video adapter 1060 is connected to a display 1130, for example.

The hard disk drive 1090 stores, for example, an OS 1091, an application program 1092, a program module 1093, and program data 1094. That is, the programs that define each process of the modification device 10 are implemented as program modules 1093 in which computer-executable code is written. The program modules 1093 are stored, for example, on the hard disk drive 1090. For example, a program module 1093 for executing processes similar to the functional configuration of the modification device 10 is stored on the hard disk drive 1090. The hard disk drive 1090 may be replaced by an SSD (Solid State Drive).

In addition, the setting data used in the processing of the above-described embodiment is stored as program data 1094, for example, in memory 1010 or hard disk drive 1090. Then, the CPU 1020 reads the program module 1093 or program data 1094 stored in memory 1010 or hard disk drive 1090 into RAM 1012 as needed, and executes the processing of the above-described embodiment.

The program module 1093 and program data 1094 may not necessarily be stored on the hard disk drive 1090, but may also be stored on a removable storage medium, for example, and read by the CPU 1020 via the disk drive 1100, etc. Alternatively, the program module 1093 and program data 1094 may be stored on another computer connected via a network (such as a LAN (Local Area Network), WAN (Wide Area Network)). The program module 1093 and program data 1094 may then be read by the CPU 1020 from the other computer via the network interface 1070.

REFERENCE SIGNS LIST 10 Correction device 11 Interface unit 12 Storage unit 13 Control unit 121 Replacement candidate syntax information 122 Cost information 131 Generation unit 132 Synthesis unit

Claims (6)

a calculation unit that calculates a priority for each template in which at least a part of range characters in a first regular expression is replaced with a placeholder, in accordance with a cost of each operator of the regular expression included in the template that is determined in advance ;
a conversion unit that converts each of the templates in descending order of priority into a second regular expression that eliminates the vulnerability of the first regular expression;
A repair device comprising: a generator that generates a first set of strings that are accepted by a first regular expression and a second set of strings that are rejected by the first regular expression;
2. The correction device according to claim 1, wherein the conversion unit converts the template into the second regular expression, which is a regular expression in which the placeholder in the template is replaced with a predetermined syntax, and which accepts character strings in the first set and rejects character strings in the second set. The correction device described in claim 1 or 2, characterized in that the calculation unit calculates the priority based on the number of characters in the template. The correction device described in claim 1 or 2, characterized in that the calculation unit calculates the priority based on the degree of deviation between the template and the first regular expression as character strings. A repair method performed by a repair device, comprising:
a calculation step of calculating a priority for each template in which at least a part of range characters in a first regular expression is replaced with a placeholder, in accordance with a predetermined cost for each operator of the regular expression included in the template ;
a conversion step of converting each of the templates in descending order of priority into a second regular expression in which the vulnerability of the first regular expression is eliminated;
A correction method comprising: a calculation step of calculating a priority for each template obtained by replacing at least a part of range characters in a first regular expression with a placeholder, in accordance with a predetermined cost for each operator of the regular expression included in the template ;
a conversion step of converting each of the templates in descending order of priority into a second regular expression in which the vulnerability of the first regular expression is eliminated;
A fix program characterized by causing a computer to execute the following.