Sage Journals: Discover world-class research

Abstract

The assurance of software reliability of the CNC system is difficult to realize with the continuous increase in the computational complexity and software scale of the CNC system. Therefore, there is an increasing demand for efficient methods that are able to locate the defect codes quickly and accurately. This study proposes a practical fault location method which is based on the similar path set and artificial neural network (ANN). The detailed fault location process involves the following steps: (1) according to the execution information recorded by the monitor, the failed path is generated; (2) the similar path set is obtained from the control flow graph and the failed path; the ANN is trained by the learning sample which is composed of the failed path and the similar path set; (3) the defect code is judged by ANN. The results of the fault location experiment on the interpolation module showed that the proposed method located the software fault quickly and accurately without depending on the experience and intuition of maintainers.

1. Introduction

The development trend in the high speed, high precision, integration, and intelligence of the CNC system has led to the continuous increase of software scale and computational complexity. It is always a challenge to improve its reliability [1, 2]. Therefore, there is a high demand for efficient methods that are able to locate the defect codes quickly and accurately. Although the FMEA and FTA methods have been successfully used for analyzing faults of the machine body [2 –5], they cannot locate the defect codes effectively. When the software breaks down, the common methods for locating the fault are analyzing memory dump and inserting print statement [6], which largely depends on the experience and intuition of maintainers. As a result, they are not ideal methods for identifying the defect codes.

An important improvement in failure location is the conclusion that the fault will happen in the case of defect code being passed by execution trace [7]. Agrawal et al. [8, 9] proposed that the fault location can be obtained by subtracting successful set of sentences from the fault-set. However, this method fails to locate the defect code effectively. Renieris and Reiss [10] tried to use the “nearest neighbor” to locate the faults by comparing a failed path with a successful path that was most similar to the failed path. However, they can only choose the most similar path without taking other paths into consideration, which results in a poor failure location. Hence, these two methods are not effective at locating the fault quickly and effectively.

To overcome the shortcomings of the above methods, this study proposes a new method to locate the CNC system failure based on similar path set and ANN. When the CNC system works properly, the monitor keeps recording the input and output values and the execution paths of the software module. If a failure occurs, the failed path is generated according to the execution information recorded by the monitor. Then, the similar path set is obtained from the control flow graph and the failed path. Finally, the defect code is judged by ANN.

2. Structure of Software Fault Location of CNC System

Due to programming errors, some bugs can be easily introduced at the stage of software design; however, not all bugs can be excluded in the stage of software testing, which causes maintainers a lot of trouble. In order to reduce the economic loss caused by bugs, an efficient method that is able to locate the defect code quickly and accurately is highly required. It is well acknowledged that the execution path differs from the normal path when the failure occurrs, and these differences cover the detailed defect information.

This study proposes an innovative method in which the defect code can be located by ANN comparing the differences between the failed path and the similar path set. In the light of the airplane black box, each branch of software modules is inserted with a pile, and the monitor is designed accordingly. The structure of software fault location of CNC system is shown in Figure 1. When the CNC system works properly, the monitor keeps recording the input and output values and the execution path of software module. When the software of CNC system breaks down, the detailed fault location would involve the following steps.

The failed path is generated according to the execution information recorded by the monitor.

The control flow graph is established by analyzing the source codes of the software module.

The similar path set is obtained from the control flow graph and the failed path.

The feasibility of similar paths was judged by using the historical execution tracks recorded by the monitor.

The ANN is trained by the learning sample which is composed of a failed path and a similar path set.

Finally, the defect code is judged by inputting the virtual path into ANN.

Figure 1:

Structure of software fault location of CNC system.

3. Monitor of the CNC System

The black box can record the flight data and cockpit voice when the airplane is working [11]. If airplane crashed, the fault analysis can be carried out by replaying the information recorded by the black box. Similar to the airplane's black box, this study will design the software monitor which can help to locate defect codes of the CNC system. In this case, the monitoring of the CNC system should offer the same attractive features as the airplane black box. For example, when the CNC system is working, as much information as possible can be recorded. Moreover, the system recourse occupied by the monitor should be small enough to ensure the least interference towards the CNC system.

As shown in Figure 2, the first step of designing the monitor of the CNC system is numbering the modules of each level. Each serial number corresponds to a layer of the module. Take the first 2 rows, for example; the main module in the first row is characterized as number “1”; in the second row, the module is marked as “1.1” for the compiler module, “1.2” for the interpolation module, “1.3” for the servo module, and so on. In the same way, the numbering continues until the module reaches the level of class or function. Also, the relationship between module name and its according number is stored in the database, which provides the base for the fault location.

Figure 2:

Number of CNC modules.

The second step of designing the monitor is piling up modules of each level and recording their execution paths. As presented in Figure 3, the paths include e₁e₂e₅e₆, e₁e₂e₅e₇, e₁e₃e₅e₆, e₁e₃e₅e₇, e₁e₄e₅e₆, and e₁e₄e₅e₇, and the piles are inserted into each branch of the software module. The array for m path [8] presents the execution path of the software module. If the execution trace covers any branch of the software module, the value of the corresponding element is “1”; otherwise, it is “0”. Take the execution path “e₁e₂e₅e₆”, for example. The obtained value of m path [8] is “1100110”. Therefore, the structure can present the running information of the software module as in Algorithm 1.

Algorithm 1:

Structure of running information.

Figure 3:

The simplified graph of module.

At work, the monitor instantiates the structure, when the execution trace arrives at the entrance of the software module. Then, the monitor assigns the element of the structure, and stores this structure in the database at the exit of the software module.

4. Similar Path Set

The detailed procedures for solving the similar path set involve analyzing the control flow graph established by the source code, searching for unconstrained edges, replacing the unconstrained edges of failure path, and judging the feasibility of similar paths.

4.1. Control Flow Graph

The control flow graph is a graphical representation of the program's control flow, by which the structure of the program can be conveniently analyzed. The control flow graph G = (N, E) consists of a set of nodes (N) and directed edges (E). The node represents the predicate of the program, and the directed edge represents the branch of the program. It is assumed that e₁ is the entry directed edge and that e_k is the exit directed edge of the control flow graph. That is, any other directed edges in the control flow graph can be reached by e₁ and e_k. The directed edge e_i dominates the directed edge e_j if every path from the entry directed edge e₁ to e_j contains e_i. The directed edge e_i implies the directed edge e_j if every path from the directed edge e_i to the exit directed edge e_k contains e_j. The directed edge e_u is an unconstrained edge only if e_u does not dominate any other directed edge and is not implied by any other directed edge in the control flow graph. In other words, if the directed edge e_u is unconstrained edge, there is at least one path from the entry directed edge e₁ to the exit directed edge e_k, which does not contain e_u.

4.2. Similar Path Set

The basic idea of the similar path set algorithm is shown in Figure 4. As shown in Figure 4, the path π_f is a failed path, and the path π₁ is a similar path. This similar path is generated by replacing the unconstrained directed edge in the failed path with other directed edges in the control flow graph. In this study, the distance is used to reflect the difference between two paths, which is denoted as dist(π_f, π₁). The larger the distance between two paths, the lower the similarity of the paths. The calculation steps of distance are shown as follows: the initial value of dist(π_f, π₁) is zero; only the unconstrained directed edge in the failed path is equal to that in the similar path; the dist(π_f, π₁) has no change; else if each of the unconstrained directed edges in the failed path can align with, but not equal to, that in the similar path, the dist(π_f, π₁) increases by 1; in another case, if each of the unconstrained directed edges in the failed path cannot align with that in the similar path, the dist(π_f, π₁) also increases by 1; eventually, the value of dist(π_f, π₁) is the distance between two paths.

Figure 4:

The basic idea of the similar path set.

As shown in Figure 5, the algorithm of the similar path set is based on “replacing the unconstrained directed edge → filling in blank of the discontinuous path.” The algorithm is performed as follows: firstly, the control flow graph, and the failed path are established according to the program module; secondly, all unconstrained directed edges are worked out from the control flow graph and the unconstrained directed edges in the failed path are marked out; the subpaths (π′ and π^″) can be obtained after breaking off the failed path π_f at the unconstrained directed edge; then, new similar paths can be achieved through combining subpaths (π′ and π^″) to a kind of subpaths which can replace the unconstrained directed edge; finally, the distance between the failed path and similar path is calculated, and a new similar path is added to the similar path set; this step continues until no other subpaths can be found in the control flow graph; this cycle continues until no other unconstrained edges in the failed path can be replaced. After the similar path set is built up, the feasibility of the similar path is verified. The test case of similar paths can be found in the execution information database because a large set of successful execution information was recorded by the monitor in the past.

Figure 5:

The algorithm of the similar path set.

5. ANN Recognition

An ANN is a programmed computational model that aims to replicate the neural structure and functioning of the human brain. Thus, it has the ability to generalize and learn [12 –14]. In order to improve previous fault location methods, we use ANN to find the defect code in the failed path. In this study, the input is the directed edge coverage of an execution path which indicates whether the directed edge in the failed path is covered by the execution path. The output is the result (success or failure) of the corresponding execution path. Once ANN has been trained, the coverage of the virtual execution path with only one directed edge in the failed path is used as an input to compute the suspicions of the corresponding directed edge in terms of its likelihood of containing a defect code. The larger the value of the output is, the more suspicious the directed edge seems to be. The directed edges in the failed path can then be ranked in a descending order of their suspiciousness, and the directed edge with the largest suspicion contains defect code.

5.1. Learning Sample of ANN

We constructed a three-layer BP ANN (backpropagation artificial neural network) with n input layer neurons (each of which corresponds to one of the directed edges in the failed path) and one output layer neuron (corresponding to the result (success or failure) of the execution path). In addition, there is a hidden layer with h units between the input and output layers, shown in Figure 6. In this paper, the input is expressed as $v = {[v_{1}, v_{2}, \dots, v_{i}, \dots, v_{n}]}^{T}$ with the ith unit v_i corresponding to the ith directed edge in the failed path π_f. If the execution path covers the ith directed edge in the failed path π_f, the ith unit v_i has a value of 1; otherwise, it has a value of 0. The output is expressed as y, which is the level of suspicion of the execution path.

Figure 6:

Structure of BP ANN.

Each neuron in the hidden layer uses the Log-Sigmoid function as its activation function. The output of the jth unit in the hidden layer is shown as follows:

\begin{matrix} g_{j} = f (\sum_{i = 0}^{n} w_{j i} v_{i}) = \frac{1}{1 + \exp (\sum_{i = 0}^{n} w_{j i} v_{i})} \\ (j = 1,2, \dots, h), \end{matrix}

(1)

where h is the number of neurons in the hidden layer and w_ji is the weight associated with the link connecting the ith neuron in the input layer and the jth neuron in the hidden layer.

The neuron in the output layer uses the line function as the activation function. The output of ANN is shown as follows:

y = f (\sum_{j = 0}^{h} w_{j} g_{j}) = \sum_{j = 0}^{h} w_{j} \times \frac{1}{1 + \exp (\sum_{i = 0}^{n} w_{j i} v_{i})},

(2)

where h is the number of units in the hidden layer and w_ji is the weight associated with the link connecting the ith neuron in the hidden layer and the neuron in the output layer.

When locating the software fault of CNC system, suppose that we have a failed path π_f with n directed edges, which can be expressed as π_f{(e₁)₁, …, (e_i)_j, …, (e_k)_n}. The directed edge (e_i)_j is the jth directed edge in the failed path π_f and is also the ith directed edge in the control flow graph. Suppose that the failed path π_f has m similar paths and that execution path π contains one failed path π_f and m similar paths. Let π_i, v_πi and y_πi, be the ith execution path, the coverage vector, and the execution result (success or failure), respectively. The coverage vector v_πi provides the information on how the failed path is covered by the similar path π_i. Here, the coverage is repressed in terms of which directed edges in the failed path are covered by the execution path π_i. The failed path and similar paths should be converted into the learning sample of ANN, which is shown in Figure 7.

Figure 7:

The schematic diagram of generation of the learning sample.

In this study, the ith learning sample can be expressed as (vⁱ, rⁱ), where vⁱ and rⁱ are the input vector and the output value of ANN, respectively. The input vⁱ in the ith learning sample can be expressed as vⁱ = [(v^πi)₁, (v^πi)₂, (v^πi)₃, …, (v^πi)_n], where

\begin{matrix} {(v^{i})}_{j} = {\begin{matrix} 0, & if the j th directed edge is not \\ covered by execution path π_{i}, \\ 1, & if the j th directed edge is \\ covered by execution path π_{i} \end{matrix} \\ (0 < i < m + 1, 0 < j < n) . \end{matrix}

(3)

The value of rⁱ depends on whether the execution path π_i succeeds or fails. It has a value of 1 if the execution path π_i fails and a value of 0 if the execution path succeeds:

\begin{matrix} r^{i} = {\begin{cases} 1, & if execution path π_{i} succeeds, \\ 0, & if execution path π_{i} fails \end{cases} \\ (0 < i < m + 1) . \end{matrix}

(4)

5.2. The Identify of BP ANN

Once ANN is trained, it has learned good mapping between the input (the execution path) and the output (the corresponding execution result), and it can identify whether a new execution path is a fault path. Moreover, it can judge whether an execution edge in the failed path contains a bug. To do so, this paper uses a set of virtual execution paths {v¹, v², …, vⁿ} as the input to ANN, which covers only one directed edge in the failed path. The set of virtual paths can be expressed by {(1, 0, 0, …, 0), (0, 1, 0, …, 0), (0, 0, 1, …, 0), …, (0, 0, 0, …, 1)}, as shown in Figure 8.

Figure 8:

The suspicious computation of the directed edges.

After inputting the virtual path into the ANN, the output of ANN is the level of suspicion of the corresponding directed edge in a failed path. The larger the value of suspicion is, the more likely the directed edge will be faulty. Virtual paths are inputted into the ANN in order, and the suspicion of the directed edges is obtained, which is expressed by {r¹, r², r³, …, rⁿ}. All directed edges are ranked in order of suspiciousness, and the directed edge with the largest value of suspicion is the fault edge.

6. Analysis of Fault Location of CNC Software

In virtual axis machine tool [15], the experiment on fault location of CNC software was carried out. The principle of NURBS interpolation can be found in [16 –18], and the control flow graph of NURBS interpolation was shown in Figure 9. Also, the bug was injected into the program of NURBS interpolation beforehand, and the defect code was the 25th line code. The piles were inserted in each branch of the program, and array for m path [11] denoted the execution paths. In the working process of NURBS interpolation, the execution information recorded by the monitor was written in the database.

Figure 9:

The control flow graph.

While interpolating the NURBS curve (Figure 10), the program for NURBS interpolation failed (Figure 11), expressing the chord error as larger than the defined maximal chord error. To provide a detailed description of NURBS interpolation, the interpolation parameters were defined as follows: the control points were {(5, 5, 4), (25, 40, 9), (50, 70, 16), (60, 100, 22), (70, 73, 30), (50, 57, 37), (112, 40, 41)}; the weight vector was {1, 1.2, 1, 1.25, 0.9, 0.85, 1}; the knot vector was {0, 0, 0, 0, 0.4531, 0.5485, 0.6306, 1, 1, 1, 1}; the speed command was 4 m/s; the sampling time was 2 ms; the maximal allowable acceleration/deceleration was 5 m/s²; the maximal allowable chord error was 2 μm. When the interpolation point was at u = 0.5747, the chord error in Figure 11 was 2.419 μm, which was larger than the maximum allowed chord error. Hence, when the interpolated point was at u = 0.5747, the program encountered failure.

Figure 10:

NURBS curve.

Figure 11:

Diagram of interpolation error.

The location for the above fault involved the following steps. To begin with, the control flow graph (Figure 9) was generated according to the program of NURBS interpolation. Next, the failed path π_f was identified as {e₁ e₂ e₄ e₈ e₉ e₁₁} through analysis of the execution information reordered by the monitor. Then, all of the unconstrained edges in the control flow graph were determined, according to the relationship between the edges. The unconstrained edges were (e₄ e₅ e₆ e₇ e₉ e₁₀), and only (e₄ e₉) were in the failed path π_f. After that, by breaking off the failed path at the unconstrained edges (e₄, e₉) and by combining other unconstrained edges with subpaths (π′ and π^″), the similar path set was established as follows: π₁{e₁ e₂ e₅ e₈ e₉ e₁₁}, π₂{e₁ e₃ e₆ e₈ e₉ e₁₁}, π₃{e₁ e₃ e₇ e₈ e₉ e₁₁}, π₄{e₁ e₂ e₄ e₈ e₁₀ e₁₁}, π₅{e₁ e₂ e₅ e₈ e₁₀ e₁₁}, π₆{e₁ e₃ e₆ e₈ e₁₀ e₁₁}, and π₇{e₁ e₃ e₇ e₈ e₁₀ e₁₁}, and all of the obtained distances between similar paths and failed paths were 1. According to the execution information recorded by monitor in the past, only the similar paths (π₁, π₂, π₃, π₅, π₇) were feasible. Finally, the defect code was identified by ANN.

As mentioned above, there were five similar paths and one failed path. So, the learning sample of BP ANN in this experiment can be expressed as {(1, 1, 0, 1, 1, 1), 0}, {(1, 0, 0, 1, 1, 1), 0}, {(1, 1, 0, 1, 0, 1), 0}, {(1, 0, 0, 1, 0, 1), 0}, and {(1, 1, 1, 1, 1, 1), 1}. In BP ANN, the input layer had six neurons corresponding to six directed edges, and the output layer had only one neuron. In addition, the hidden layer had four neurons. Each neuron in the hidden layer used the Log-Sigmoid function as the activation function, and the neuron in the output layer used the line function as the activation function. In BP ANN, both the learning rate and prediction accuracy were set to 0.01, while the maximum iteration number was set to 200. At each iteration, BP ANN calculated the average output error and adjusted every weight. The BP ANN was carried out based on MATLAB, and the average output error at each iteration was shown in Figure 12. After 95 iterations, the average output error was 0.0098252.

Figure 12:

The average output error in training ANN.

After BP ANN was trained, the virtual execution paths such as (1, 0, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0), (0, 0, 0, 1, 0, 0), (0, 0, 0, 0, 1, 0), and (0, 0, 0, 0, 0, 1) were input, respectively, to the BP ANN. The output of BP ANN was suspicious of the directed edge, which was shown in Table 1.

Table 1:

Suspicions of the failed path.

Directed edge	e ₁	e ₂	e ₄	e ₈	e ₉	e ₁₁

Suspiciousness	0.0708	0.1046	0.7227	0.0708	0.4458	0.0708

As indicated in Table 1, the directed edge with the largest degree of suspicion was e₄. The directed edge e₄ included the codes in the twenty-fifth and twenty-sixth lines. The program code in the twenty-fifth line was deleted by the program slicing technique because this code had nothing to do with calculating the results of NURBS interpolation. Therefore, the program code in the twenty-sixth line was defect code, and the result was consistent with the code in which the bug was previously inserted. ANN can simulate certain behaviors of biological nervous systems and has the ability to learn and make judgments. So, the proposed method was able to locate the software fault quickly and accurately without dependence on the experience and intuition of maintainers. Hence, this method was effective in software fault location of the CNC system.

7. Conclusions

In summary, the application of a similar path set and ANN is very effective in establishing the fault location in the CNC software. The monitor can record the execution information in real-time during the operation of the CNC software. When the CNC software fails, the fault location can be carried out by the algorithm of the similar path set and ANN, and the experiment regarding the fault location of the NURBS interpolation module is carried out. The results of the above experiments show that the proposed method is a quick and accurate method in locating the fault in the CNC software without depending on the experience and intuition of maintainers.

This paper proposes a good foundation for self-repair of CNC software, especially for reliability self-growth of CNC software. The subsequent work is ongoing. The whole research will integrate the fault self-location, fault self-repair, and reliability self-growth, which will greatly improve the software reliability of the CNC system.

Footnotes

Acknowledgments

This paper is supported by the State Key Science and Technology Special Projects for Advanced CNC Machine Tools and Basal Manufacturing Equipments (no. 2012ZX04011021) and by the Natural Science Foundation of Zhejiang Province (no. Y1110708).

References

Wang

Y. Q.

Jia

Y. Z.

, and Yu

J. Y.

, “Field failure database of CNC lathes,” International Journal of Quality & Reliability Management, vol. 16, no. 4, pp. 330–343, 1999.

Vinod

Gurusamy

, and Sasikumar

, “Design and analysis of power failure detector module for control of axis runaway in CNC machines during unprecedented power failures,” International Journal of Machine Tools and Manufacture, vol. 46, no. 12–13, pp. 1610–1616, 2006.

Wang

Jia

, and Jiang

, “Early failure analysis of machining centers: a case study,” Reliability Engineering and System Safety, vol. 72, no. 1, pp. 91–97, 2001.

Lee

S. S.

Lee

J. H.

, and Park

I. K.

, “Reliability assessment approach using failure mode analysis in machining center,” Key Engineering Materials, vol. 321–323, pp. 1535–1538, 2006.

Wang

, and Hua

, “Reliability analysis and improvement of ATCs of CNC lathes,” Applied Mechanics and Materials, vol. 37–38, pp. 939–943, 2010.

Wong

W. E.

and Debroy

, “Software fault localization,” IEEE Reliability Society Annual Technology Report, 2009.

Harrold

M. J.

Rothermel

, and Sayre

, “Empirical investigation of the relationship between spectra differences and regression faults,” Software Test Verif Reliab, vol. 10, pp. 171–194, 2000.

Agrawal

Demillo

R. A.

, and Spafford

E. H.

, “Debugging with dynamic slicing and backtracking,” Software Practice and Experience, vol. 23, no. 6, pp. 589–616, 1993.

Agrawal

Horgan

J. R.

London

, and Wong

W. E.

, “Fault localization using execution slices and dataflow tests,” in Proceedings of the 6th International Symposium on Software Reliability Engineering, pp. 143–151, Toulouse, France, October 1995.

10.

Renieris

and Reiss

S. P.

, “Fault localization with nearest neighbor queries,” in Proceeding of the 18th IEEE International Conference on Automated Software Engineering (ASE '03), pp. 30–39, Montreal, Canada, October 2003.

11.

Ashish

and Chougule

S. B.

, “Wireless flight data recorder (FDR) for airplanes,” in Proceeding of International Conference on Materials Science and Information Technology, Singapore, September 2011.

12.

Chu

S. R.

Shoureshi

, and Tenorio

, “Neural networks for system identification,” IEEE Control Systems Magazine, vol. 10, no. 3, pp. 31–35, 1990.

13.

Rafiq

M. Y.

Bugmann

, and Easterbrook

D. J.

, “Neural network design for engineering applications,” Computers and Structures, vol. 79, no. 17, pp. 1541–1552, 2001.

14.

Duer

, “Diagnostic system with an artificial neural network in diagnostics of an analogue technical object,” Neural Computing and Applications, vol. 19, no. 1, pp. 55–60, 2010.

15.

Zhao

Zhang

, and Wang

, “Study on the dynamic characteristics of a virtual-axis hybrid polishing machine tool by flexible multibody dynamics,” Journal of Engineering Manufacture B, vol. 218, no. 9, pp. 1067–1076, 2004.

16.

Farouki

R. T.

and Tsai

Y.-F.

, “Exact Taylor series coefficients for variable-feedrate CNC curve interpolators,” CAD Computer Aided Design, vol. 33, no. 2, pp. 155–165, 2001.

17.

Yong

and Narayanaswami

, “A parametric interpolator with confined chord errors, acceleration and deceleration for NC machining,” CAD Computer Aided Design, vol. 35, no. 13, pp. 1249–1259, 2003.

18.

Liu

Ahmad

Yamazaki

, and Mori

, “Adaptive interpolation scheme for NURBS curves with the integration of machining dynamics,” International Journal of Machine Tools and Manufacture, vol. 45, no. 4–5, pp. 433–444, 2005.

Software Fault Location of CNC System Based on Similar Path Set and Artificial Neural Network

Abstract

1. Introduction

2. Structure of Software Fault Location of CNC System

3. Monitor of the CNC System

4. Similar Path Set

4.1. Control Flow Graph

4.2. Similar Path Set

5. ANN Recognition

5.1. Learning Sample of ANN

5.2. The Identify of BP ANN

6. Analysis of Fault Location of CNC Software

7. Conclusions

Footnotes

Acknowledgments

References