Method for the approximate matching of regular expressions, in particular for generating intervention workflows in a telecommunication network

摘要

A list of elements in a set of elements is matched by means of regular expressions that define respective groups of elements in the set by approximately matching by means of the regular expressions the list of elements by locating recurrences of the regular expressions in the list of elements with a maximum number of matching errors. The matching errors correspond to insertions deriving from the superposition of groups of elements related to different regular expressions. Each time the recurrence of one regular expression is located in the list, the group of elements defined by the regular expression thus located is removed from the list, while leaving in the list those elements corresponding to errors. The approximate matching can be performed by representing each regular expression in terms of Glushkov automata. The method is applicable, e.g., for generating workflows related to interventions on equipment such as equipment included in a telecommunication network or to attacks attempted against such equipment.

主权项

1. A method of automatically reconstructing a sequence of interventions by human operators on equipment, comprising:
recording in a log file events generated in the equipment as a result of the interventions performed by the operator, the events being recorded as sequences of elements in a list with each element having a timestamp, some of the events being superposed over each other in time; defining regular expressions representative of potential interventions on said equipment; approximate regular expression matching a sequence of elements in timestamp order in said list by locating an occurrence of one of said regular expressions in said list of elements with no more than a maximum number of matching errors and with the timestamps of said sequence of elements being within a predetermined value, each of said matching errors corresponding to an insertion within the sequence for one or more elements of the located regular expression and being associated with a regular expression different from the located regular expression; ascribing a group of elements in said sequence to the located regular expression if said located regular expression corresponds to said group but for the matching errors therein; removing from the list the group of elements defined by the regular expression located; leaving in said list those elements corresponding to said matching errors; and repeating said approximate regular expression matching, said ascribing, said removing, and said leaving in for a next sequence of elements in said list of elements.