CN104899137A - Discovering method for defect mode in concurrent program - Google Patents

Abstract

The present invention belongs to the field of software fault diagnosis and provides an autonomously discovering method for a defect mode in a concurrent program, particularly a defect mode discovering method for mining system execution traces by using sequential patterns. According to the technical scheme provided by the invention, based on a plugged concurrent program, the execution of threads are dynamically scheduled during the operation of the plugged concurrent program; program execution information is collected in real time; a program trace sequence is stored as required; the execution sequence is mined; and the program defect pattern is autonomously discovered.

Description

A Defect Pattern Discovery Method for Concurrent Programs

technical field

The invention belongs to the field of software fault diagnosis, and is a method for autonomously discovering defect patterns of concurrent programs, in particular a method for discovering defect patterns using sequence pattern mining for system execution tracks.

Background technique

It is difficult to find concurrent program defects. Generally, the cause of the fault can only be judged according to the log information, while the ordinary monitoring system only detects the software behavior and cannot further judge whether the execution of the software is on the correct track (correct behavior). above.

The monitoring program based on aspect-oriented programming can separate monitoring logic and business logic, and can easily obtain the execution track of a parallel program system. Based on the acquired execution trajectories of concurrent program systems, sequential pattern mining technology can be used to mine these trajectories, which can effectively solve the problem of difficult fault diagnosis of concurrent programs and extract useful data from the massive data of concurrent program execution trajectories. information to obtain the key points of fault characteristics implied in the sequence set of historical concurrent program trajectories. This technique can effectively guarantee the security of concurrent software systems.

A typical implementation scheme of the prior art is as follows:

First, the fault/defect diagnosis program based on the expert system. Its main principle is to express the knowledge and experience of domain experts as production rules, and with the support of knowledge base and database, use various rules comprehensively to carry out a series of inferences. After the diagnostic program requires the user to input necessary information during operation, the final fault/defect or the most probable fault/defect can be found directly and quickly, and the user can further judge the result. But this method needs to establish a rule base, and use the rule base to judge and predict the state of the program trajectory. The main disadvantage of this method is that the degree of automation is not high, and the reusability of the method is poor.

Second, convenient and effective acquisition of program execution trace is a prerequisite for software fault/defect diagnosis. In terms of program execution trajectory acquisition, the University of California, Berkeley and Bell Labs jointly proposed the Dynamic Partial Order Reduction algorithm (Dynamic Partial Order Reduction, DPOR), which explores the interactive execution of threads, and proposes the concept of Persistent collections. To ensure the completeness of thread execution search. The algorithm uses depth-first search of the program state stack from the transition sequence executed by the initial state of the program, dynamically explores the interaction information between threads, and then uses this information to identify the backtracking point, so as to explore the optional path of the state space and obtain the program execution trajectory.

During the search process of the program state, the Persistent set of each state is calculated, so that all migration sequences in the program are not empty sequences, and all migrations in the feasible migration set in a certain state are independent of migrations in other migration sequences, ensuring that completeness of the search.

However, the main disadvantage of this algorithm is that it does not acquire and store the complete program trajectory sequence; it does not provide a basis for further analysis of the program trajectory sequence; it does not optimize for concurrent programs containing loops, and there will be repeated searches for migrations that have been searched. This will cause the low efficiency of the DPOR algorithm, which is reflected in the long total exploration time and single average exploration time of the algorithm.

Third, in terms of the discovery method of defect patterns, Cornell University in the United States proposed a sequential pattern mining algorithm (Sequential PAttern Mining, SPAM) to mine sequential patterns, and to mine sequence sets to obtain frequent patterns. The SPAM algorithm first stores the sequence information in the database bitmap, and then implements item set expansion at the item set level, and sequence expansion at the sequence level, and uses lattice theory to perform depth-first traversal on the database to find out the sequence pattern. The main disadvantage of the SPAM algorithm is that the user needs to set the minimum support threshold by himself. An improper support threshold may cause poor quality of the mined patterns; only a single type of sequence set can be processed, and the false positives are serious.

Contents of the invention

The purpose of the present invention is to address the above deficiencies, on the basis of the traditional dynamic partial order simplification algorithm to obtain the concurrent program execution track and the SPAM algorithm for sequential pattern mining, aiming at the core steps of the algorithm, that is, to obtain the concurrent program track and to mine the track By discovering the defect mode, an improvement method involving these two steps is proposed, and the program defect mode can be found independently.

The technical solution of the present invention is based on an inserted concurrent program, dynamically schedules the execution of threads during its running, collects program execution information in real time, stores program track sequences as required, and mines the execution sequences to obtain defect patterns.

The present invention provides a method for discovering defect patterns of concurrent programs, comprising the following steps:

(1) Monitor the target program, and use the injection method of the aspect-oriented programming probe code to monitor the monitoring point in order to obtain status information;

(2) Use the dynamic label transfer algorithm DLT to schedule the execution of the target program with monitoring points, and obtain the status information of the monitoring points of the target program;

(3) Store the monitored state information in the database in the form of trajectory sequences, obtain the execution results of each trajectory sequence in the database, classify the trajectory sequences, and obtain the successful execution sequence set and the failure execution sequence set;

(4) In the successful execution sequence set and the failure execution sequence set, the sequence pattern mining algorithm ISPAM is used to mine, and the defect pattern of the target program is obtained.

In the above technical solution, the steps for obtaining status information described in step (1) are as follows:

Step 1. Based on the idea of aspect-oriented programming and the source program to be monitored, the user first defines monitoring points for the read and write operations of shared variables in the concurrent program to be monitored, and then the user adds several cut points at the monitoring points;

Step 2. The user defines the notification corresponding to each cut point, and defines the processing code to be executed for the notification. When the cut point matches, the processing code defined in the notification is before, after, or after the cut point. These 3 places near the point are executed, the transform() method in the notification will be used to store the line number in the parameter table array args of the monitored method in the source program, the content in the temporary variable meg of the serial number information, and the content in the execution environment The thread identifier is converted into monitoring site information and stored in the event class EventPO.

In the above technical solution, the algorithm input parameters of the dynamic label transfer algorithm DLT(S, T, t, SeS) described in step (2) include: global state stack S, global migration sequence set T, local migration t and initial The global sequence set SeS; the output parameters of the algorithm are: the global sequence set SeS; the steps are as follows:

Step 1, pop the top element of the stack in S and store it in state s, and store the current sequence in SeS into the sequence variable σ;

Step 2, update the backtracking information of s;

Step 3, if there is a migration element t of thread p in the feasible migration set s.enabled in the state of thread p and s, perform the following steps:

(3.1) Assign the thread p to the backtracking set s.backtrack of the state s;

(3.2) Create the migration set s.done that has been executed in state s, and set it to empty;

(3.3) If there is a thread q that is an element in the difference set between the backtracking set s.backtrack of state s and the migration set s.done that has been executed in state s, repeat the following steps until there is no such thread q :

(3.3.1) Add q to the migration set s.done that has been executed in state s;

(3.3.2) Delete thread q from the backtracking set s.backtrack of state s;

(3.3.3) Let p' be the thread that executes migration t _m , if thread p' belongs to s.done, and t _m belongs to s.enabled, then add t _m to the set s.retrieved;

(3.3.4) Set the migration performed by thread q in the feasible migration set s.enabled in state s to t _n ;

(3.3.5) Create the itemset is and initialize it to be empty, and add t _n to is;

(3.3.6) Add the itemset is to the sequence variable σ;

(3.3.7) Determine whether the state starting from state s and arriving after t _n migration is empty, if not, execute the following steps, otherwise do not execute:

(3.3.7.1) Set the state obtained after starting from state s and performing t _n migration as s';

(3.3.7.2) Store the migration t' that is independent of the migration t and belongs to s.enabled into the s'.retrieved collection;

(3.3.7.3) Store the difference between s'.enabled and s'.retrieved in s'.enabled;

(3.3.7.4) Add migration t _n to migration sequence T;

(3.3.7.5) Push state s' into state stack S;

(3.3.7.6) Recursively call the DLT(S, T, t, SeS) algorithm;

(3.3.7.7) Remove the last sequence in T;

(3.3.8) Pop a state in S out of the stack;

Step 4, return the global sequence set SeS.

In the above technical solution, the steps of the sequential pattern mining algorithm ISPAM in step (4) are as follows:

Step 1: Set the candidate pattern set R and the top k defect pattern set L as empty sets, and set the global variable minsup to 0;

Step 2, converting the successful execution sequence set GS and the failure execution sequence set BS into vertical sequence data sets V(GS) and V(BS) respectively, and generating the item set list S _init in V(BS);

Step 3, for each item items in the itemset list S _init , complete the following steps:

(3.1) Calculate whether it is a frequent item, if it is:

(3.1.1) Call the SAVE() method to store the schema consisting of a single item into L;

(3.1.2) Add items to the R collection, S _init , a triplet composed of a collection of items after items in S _init ;

Step 4, if there is a tuple Belongs to the R set and the support of r is greater than or equal to minsup, then repeat the following steps until this condition is not met:

(4.1) Select the tuple of the pattern r with the highest support in the R set ;

(4.2) Expand the candidate pattern set R by calling the SEARCH() method, update the candidate pattern set R, and store the extended patterns in L by calling the SAVE() method;

(4.3) will tuple removed from R;

(4.4) will satisfy all in R tuples of conditions are removed from R;

Step 5, return the set L containing the top k defect patterns.

Compared with the prior art, the inventive method has the following advantages:

1. Insert and monitor the target source program, set the monitoring of the target program, and aim at the shortcomings of the DPOR algorithm for programs with many loops and low execution efficiency, eliminate the selection of independent migration, and retrieve the The migrations that have been performed are added to a special set to avoid repeated searches for migrations that have been executed, thereby simplifying the program that contains many loops and improving execution efficiency. During the selective search process, the trajectory sequence is recorded and the trajectory sequence Store it in the sequence set to get all the program trajectory sequences.

2. Aiming at the problem of poor pattern quality and too many patterns caused by the minimum support set by the user in the SPAM algorithm, the number of items k is introduced to specify the number of optimal pattern mining, which is transformed into the top k sequential pattern mining, and the top k items are obtained. The best defect explanation model for k items. Based on this, in order to achieve the purpose of reducing the search space, improving the efficiency of the algorithm, and solving the problem of false alarms, the concepts of successful execution sequence set, failure execution sequence set, and relative support are defined. The so-called successful execution sequence set refers to concurrent The execution result of the program conforms to the execution sequence set of the expected behavior of the program; the so-called failure execution sequence set refers to the execution sequence set whose execution result of the concurrent program does not meet the expected behavior of the program; the so-called relative support refers to the execution sequence set that frequently appears in the failure execution sequence A relative measure of sets that occur less frequently in successfully executed sequences. On this basis, the present invention proposes to calculate the relative support degree by comparing the same pattern in the successful execution sequence set and the failure execution sequence set in the mining process, so as to reduce the selection of patterns frequently appearing in the successful execution sequence set, thereby reducing the The method of defect false positive rate.

Description of drawings

Fig. 1 is the flowchart of the method of the present invention.

Detailed ways

This implementation uses a PC with Windows 7 operating system as a platform to develop a concurrent program defect detection program through MyEclipse. When the present invention is implemented, the user must install JDK above version 1.7 to obtain the new features provided by Java.

In addition, the following terms need to be defined:

(1) Monitoring site: refers to the status information of the monitored target program when it is running.

(2) Notification: Refers to the code that should be executed when a clearly defined point (access point) in program execution is triggered by program execution.

(3) The state of a concurrent program: refers to the state consisting of the global state of all shared variables and the local state of each thread.

(4) Migration of concurrent programs: Refers to a visible operation performed by a thread to transfer the program from one state to the next.

(5) Vertical successful execution sequence set: refers to the successful execution sequence set in vertical format represented by a bitmap.

(6) Vertical invalidation execution sequence set: refers to the invalidation execution sequence set in vertical format represented by a bitmap.

Embodiments of the present invention relate to the following documents:

[1] Flanagan C, Godefroid P. Dynamic Partial-Order Reduction for Model Checking Software POPL'2005[M]. New York: ACM press, 2005.

[2] Ayres, J., Flannick, J., Gehrke, J., Yiu, T.. Sequential PAttern mining using a bitmap representation, Proc. 8th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD 2002) , July 23-26, 2002, Edmonton, Alberta, pp. 429-435 (2002).

The technical scheme of the present invention will be described below by taking the Java language on a PC to develop a concurrent program defect detection program under the JDK development environment as an example.

(1) Set up the monitoring target program.

In order to obtain the status information of concurrent program execution, it is first necessary to set the target program to be monitored. The specific method is: based on the idea of aspect-oriented programming, define monitoring points, pointcuts, and advice in the target program to be monitored, and use probe injection to monitor the monitoring points to obtain status information.

The definitions of related variables involved in the process of obtaining status information are shown in Table 1.

Table 1 Symbols in the process of obtaining status information symbolic name symbol type meaning meg string A temporary variable that stores the line number and serial number information in the parameter table array args transform() method Method for converting thread identifier and meg information in the execution environment into monitoring scene information EventPO kind A class that stores monitoring site information

The steps to obtain status information are as follows:

Step 1. Based on the idea of aspect-oriented programming and the source program to be monitored, the user first defines monitoring points for the read and write operations of shared variables in the concurrent program to be monitored, and then the user adds several cut points at the monitoring points;

Step 2. The user defines the notification corresponding to each cut point, and defines the processing code to be executed for the notification. When the cut point matches, the processing code defined in the notification is before, after, or after the cut point. These 3 places are executed near the point. The transform() method in the notification converts the content in the temporary variable meg and the thread identifier in the execution environment into monitoring site information, and stores it in the event class EventPO.

(2) Use the dynamic label transfer algorithm DLT to schedule the execution of the target program that sets the monitoring point.

The thread execution in the concurrent program to be monitored is scheduled by using the dynamic label transfer algorithm DLT proposed by the present invention.

The definitions of the relevant symbols used in this algorithm are shown in Table 2.

Table 2. Symbols in Dynamic Label Transfer Algorithm DLT symbolic name symbol type meaning update_backtrack_info The method defined in [1] Methods for Updating Backtrace Information the s program status A state consisting of the global state of shared variables and the local state of each thread SeS gather the set of all sequences enabled gather A set of feasible migrations in a certain state whose elements are feasible migrations p thread A thread in s.enabled t migrate A visible operation that causes a state transition σ sequence Current sequence in SeS t _m migrate This migration belongs to the migration in the feasible migration set s.enabled in the state s, and the thread that executes the migration is the thread in the migration set s.done that has been executed in the state s t _n migrate This migration belongs to the migration performed by thread q in the feasible migration set s.enabled in state s retrieved gather Store a collection of all migrations that can be executed in a certain state but are not necessary q thread a certain thread back track gather A traceback set in a certain state whose set elements are executable but not yet executed threads done gather A collection of migrations that have been executed in a certain state next(s,t) method Start from state s and perform t transition s' program status The state obtained after starting from state s and performing t _n transition T gather A collection of all migrations S the stack a stack of all states p' gather thread executing migration t _m is item set Itemsets added to the sequence variable σ t' migrate This migration belongs to s.enabled, independent of migration t

The steps of the dynamic label transfer algorithm DLT (S, T, t, SeS) are as follows:

The input parameters of the algorithm are: the global state stack S, the global transition sequence set T, the local transition t and the initial global sequence set SeS. The output parameters of the algorithm are: global sequence set SeS.

(1) Pop the top element of S into the state s, store the current sequence in SeS into the sequence variable σ;

(2) Update the backtracking information of s;

(3) If there is a migration element t of thread p in the feasible migration set s.enabled in the state of thread p and s, perform the following steps:

(3.1) Assign the thread p to the backtracking set s.backtrack of the state s;

(3.2) Create the migration set s.done that has been executed in state s, and set it to empty;

(3.3) If there is a thread q that is an element in the difference set between the backtracking set s.backtrack of state s and the migration set s.done that has been executed in state s, repeat the following steps until there is no such thread q :

(3.3.1) Add q to the migration set s.done that has been executed in state s;

(3.3.2) Delete thread q from the backtracking set s.backtrack of state s;

(3.3.3) Let p' be the thread that executes migration t _m , if thread p' belongs to s.done, and t _m belongs to s.enabled, then add t _m to the set s.retrieved;

(3.3.4) Set the migration performed by thread q in the feasible migration set s.enabled in state s to t _n ;

(3.3.5) Create the itemset is and initialize it to be empty, and add t _n to is;

(3.3.6) Add the itemset is to the sequence variable σ;

(3.3.7) Determine whether the state starting from state s and arriving after t _n migration is empty, if not, execute the following steps, otherwise do not execute:

(3.3.7.1) Set the state obtained after starting from state s and performing t _n migration as s';

(3.3.7.2) Store the migration t' that is independent of the migration t and belongs to s.enabled into the s'.retrieved collection;

(3.3.7.3) Store the difference between s'.enabled and s'.retrieved in s'.enabled;

(3.3.7.4) Add migration t _n to migration sequence T;

(3.3.7.5) Push state s' into state stack S;

(3.3.7.6) Recursively call the DLT(S, T, t, SeS) algorithm;

(3.3.7.7) Remove the last sequence in T;

(3.3.8) Pop a state in S out of the stack;

(4) Return the global sequence set SeS.

Its specific algorithm is as follows.

(3) Store the monitored state information in the database in the form of trajectory sequence.

Store the state information acquired by monitoring in the event class EventPO, and store the information in the event class EventPO in the database SDB in the form of a track sequence through the Dao method. Class EventPO records each monitoring point event; class SequencePO records sequence information for each execution, including sequence id and sequence result status (status).

Use Hibernate to perform object relationship mapping ORM (Object Relationship Mapping, ORM) operation, and data access object DAO (Data Access Object, DAO) to operate the persistent object PO (persistent object, PO) in Java, and complete the data in EventPO and SequencePO Stored to the database SDB.

The event class EventPO is defined as follows:

public class EventPO {

Private int primaryKey; //Indicates the serial number of the item

Private int threadID; //Indicates the serial number of the thread

private String threadName;//Indicates the thread name

Private int methodLine;//Indicates the line where the monitored method is located

private String methodName;//Indicates the name of the monitored method

private int shareMemoryIndex;//Indicates the serial number of the shared memory

private String shareMemoryValue;//Indicates the value of shared memory

private Date date;//Indicates the operation date

Private int millisecond;//Indicates the operation time

private SequencePO sequence;//Indicates the sequence number it belongs to

}

In the above definition:

primaryKey represents the serial number of the item;

threadID represents the serial number of the thread;

threadName represents the thread name;

methodLine indicates the line where the monitored method is located;

methodName indicates the name of the monitored method;

shareMemoryIndex indicates the serial number of the shared memory;

shareMemoryValue represents the value of shared memory;

date represents the operation date;

millisecond indicates the operation time;

sequence indicates the sequence number it belongs to.

(4) Obtain the execution results of each trajectory sequence in the database, classify the trajectory sequences, and obtain a successful execution sequence set and a failure execution sequence set.

Obtain the execution result status (status) in the track sequence, and determine whether the status of the sequence execution result in the concurrent program is lost or modified, or whether there is non-repeatable read, or whether to read "dirty" data, etc. according to the predefined failure result One, if yes, the execution result is invalid, classify the trajectory sequence, and obtain a successful execution sequence set and a failure execution sequence set.

(5) Concurrent program defect pattern mining based on trajectory sequence.

In the successful execution sequence set and the failure execution sequence set, the following improved sequence pattern mining algorithm ISPAM is used to mine the data set stored in the database to obtain the concurrent program defect pattern.

The meanings of the relevant variables of the sequential pattern mining algorithm ISPAM are shown in Table 3.

Table 3 Symbols in the sequential pattern mining algorithm ISPAM symbolic name symbol type meaning R gather set of candidate patterns L gather Collection of top k defect patterns minsup double variable minimum support GS gather Successful execution of the sequence set BS gather Failed Execution Sequence Set V(GS) gather Vertical successfully executed sequence set V(BS) gather Vertical Failure Execution Sequence Set S _init the list itemset list SAVE() method How to implement a stored procedure items item An entry in S _init Triad Extensible Sequence Record Tuple SEARCH() The method defined in [2] A method to implement the candidate set generation process r model A Candidate Pattern in Pattern Mining Process k integer variable number of patterns sup(r) method How to calculate the support of r bv(items) method Method for calculating whether items are frequent items

The steps of the sequential pattern mining algorithm ISPAM are as follows:

(1) Set the candidate pattern set R and the top k defect pattern set L as empty sets, and set the global variable minsup to 0;

(2) Step 2: Transform the successful execution sequence set GS and the failure execution sequence set BS into vertical sequence data sets V(GS) and V(BS) respectively, and generate the item set list S _init in V(BS);

(3) For each item in the itemset list S _init , complete the following steps:

(3.1) Calculate whether it is a frequent item, if it is:

(3.1.1) Call the SAVE() method to store the schema consisting of a single item into L;

(3.1.2) Add items to the R collection, S _init , a triplet composed of a collection of items after items in S _init ;

(4) If there is a tuple Belongs to the R set and the support of r is greater than or equal to minsup, then repeat the following steps until this condition is not met:

(4.1) Select the tuple of the pattern r with the highest support in the R set ;

(4.2) Expand the candidate pattern set R by calling the SEARCH() method, update the candidate pattern set R, and store the extended patterns in L by calling the SAVE() method;

(4.3) will tuple removed from R;

(4.4) will satisfy all in R tuples of conditions are removed from R;

(5) Return the set L containing the top k defect patterns.

Its specific algorithm is as follows.

Claims (4)

1. a defect mode discover method for concurrent program, is characterized in that the method comprises the following steps:

(1) monitoring objective program, uses the method for implanting of Aspect-oriented programming probe identification code to monitor control point to obtain status information;

(2) use the execution of dynamically labeled migration algorithm DLT to the target program arranging control point to dispatch, obtain the status information of the control point of target program;

(3) the status information monitored, store in a database with the form of track sets, obtain the execution result of every bar track sets in database, classify to track sets, succeeding to perform sequence sets and lost efficacy performs sequence sets;

(4) perform in sequence sets at successful execution sequence sets and inefficacy, utilize Sequential Pattern Mining Algorithm ISPAM to excavate, obtain target program defect mode.

2. the defect mode discover method of concurrent program according to claim 1, is characterized in that the step of the acquisition status information described in step (1) is as follows:

Step one, based on Aspect-oriented programming thought and source program to be monitored, for the read-write operation definition control point of shared variable in concurrent program to be monitored, then adds several point of contacts at control point place;

Step 2, define the notice that each point of contact is corresponding, define the process code that this notice need perform simultaneously, when point of contact is mated, in notice, the process code of definition is before point of contact, or after point of contact, or this 3 place performs near point of contact, transform () method in notice converts the content being used for depositing in the temporary variable meg of the line number comprised in the parameter list array args of monitored method in source program, sequence number information and the thread identifier in execution environment to monitoring site information, and stored in event class EventPO.

3. the defect mode discover method of concurrent program according to claim 1, it is characterized in that the dynamically labeled migration algorithm DLT (S described in step (2), T, t, SeS) algorithm input parameter has: global state stack S, overall situation migration series collection T, local migration t and initial global sequence collection SeS; Algorithm output parameter has: global sequence collection SeS; Its step is as follows:

Step one, pops stored in state s by the stack top element in S, by the current sequence in SeS stored in sequence variables σ;

Step 2, upgrades the traceback information of s;

Step 3, if a migration element t of s.enabled thread p is gathered in feasible migration under there is thread p and s state, performs following steps:

(3.1) by thread p assignment to the retraceable set s.backtrack of state s;

(3.2) the migration set s.done performed under creation state s, and be set to sky;

(3.3) if the element in the difference set of the migration set s.done performed under there is the retraceable set s.backtrack and state s that a certain thread q is state s, following steps are repeated, until there is not such thread q:

(3.3.1) q is added in the migration set s.done performed under state s;

(3.3.2) from the retraceable set s.backtrack of state s, thread q is deleted;

(3.3.3) p ' is established to perform migration t _mthread, if thread p ' belongs to s.done, and t _mbelong to s.enabled, then by t _madd in set s.retrieved;

(3.3.4) migration that migration set s.enabled thread q feasible under s state performs is set to t _n;

(3.3.5) create item collection is and be initialized as sky, and by t _nadd in is;

(3.3.6) item being collected is adds in sequence variables σ;

(3.3.7) judge from state s and perform t _nwhether the state arrived after migration is null value, if not, then perform following steps, otherwise do not perform:

(3.3.7.1) will from state s and perform t _nthe state obtained after migration is set to s';

(3.3.7.2) migration t' in s.enabled will be belonged to stored in s'.retrieved set independent of migration t;

(3.3.7.3) difference set gathered by s'.enabled and s'.retrieved is stored in s'.enabled;

(3.3.7.4) t will be moved _nbe added in migration series T;

(3.3.7.5) state s' is pressed in state stack S;

(3.3.7.6) recursive call DLT (S, T, t, SeS) algorithm;

(3.3.7.7) sequence of last in T is shifted out;

(3.3.8) state of in S is popped;

Step 4, returns global sequence collection SeS.

4. the defect mode discover method of concurrent program according to claim 1, is characterized in that the step of Sequential Pattern Mining Algorithm ISPAM in step (4) is as follows:

Step one, is set to empty set by the set L of candidate pattern set R and a front k defect mode, and to arrange global variable minsup be 0;

Step 2, is separately converted to vertical series data set V (GS) and V (BS) by successful execution sequence sets GS and the execution sequence sets BS that lost efficacy, generates V (BS) middle term collection list S _init;

Step 3, for item collection list S _initin each items, complete following steps:

(3.1) whether calculate it is frequent episode, if:

(3.1.1) SAVE () method is called to the pattern storage be made up of single item in L;

(3.1.2) add-ins items is gathered at R, S _init, S _initin the tlv triple of set composition of item after items;

, if there is tuple in step 4 belong to R set and the support of r is more than or equal to minsup, then repeat to do following steps, until do not meet this condition:

(4.1) tuple having the pattern r of the highest support in R set is selected ;

(4.2) by calling SEARCH () method, candidate pattern set R being expanded, upgrading candidate pattern set R, and be stored in L by expanding mode invocation the SAVE () method obtained;

(4.3) by tuple remove from R;

(4.4) by R all meet the tuple of condition removes from R;

Step 5, returns the set L containing a front k defect mode.