An efficient and precise dynamic slicing for concurrent component-oriented programs

2.1 Component-oriented programming

Component-Oriented programs have brought a revolutionary change in the style of software development where modular programming was enlightened rather than line-by-line code and assembling components rather than syntax-based programming based on their interface. COP can be referred to as interface-based programming whereas OOP is object-based programming. While OOPs emphasizes on the concept of classes and objects [11], COP focuses on compositions, and interfaces [26]. Major advantages of using COP:

1)

Abstraction: Only required functionality is mentioned, but the implementation of the components is not required.

2)

Complexity: The overall complexity of the program will decrease when well-designed components are integrated to form a new program.

3)

Reusability: In COP, we need to identify suitable components and they can be re-utilized many numbers of times.

COP helps in solving some issues and complexities of major software engineering industries such as frequent change of client requirements, software reusability, complexity in software development. Brown [28] presented the definition of a software component as “A component is a nontrivial, nearly independent, and replaceable part of a system that fulfills a clear function in the context of a well-defined architecture.” COP represents modular programming where each module is treated as a component whereas, in object-oriented programming, modules are treated as classes.

A program complying with the above definition and characteristics of COP can be achieved by using different component technologies like JavaBeans and Enterprise Java Beans (EJB), Distributed Component Object Model (DCOM), and .NET components.

2.2 Web scrapping

Web scraping is also referred to as data scrapping which is used for extracting data from websites. COP can be implemented better in web services, which provided application-oriented services on the web and enabling it as a programmable web rather than just an interactive web [26]. Though features of COP can be achieved by many component technologies or frameworks such as NET, EJB, the web service is the only technology that provides cross-platform, cross-programming language, and internet-firewall solutions to the inter-operable distributed computing.

Web services provide a viewpoint to develop distributed software by composition rather than by developing in traditional form of programming. This is the biggest example of re-usability where new application builds from existing components. These are the core motives behind COP and Component-Based Software Development (CBSD). One of the key features of COP is the self-deployability of components, which is very difficult to acquire in case of other component technologies. Hence, the features of COP can be well implemented and acquired by web services.

Some of the web services development tools are Microsoft .NET web service based on IIS server, Java Web Service Development Pack (JWSDP) but, in this paper, we have considered XAMPP, which is a free and open-source cross-platform web server solution stack package developed by Apache.

2.3 Concurrent COP

Concurrency can provide an easier path for making a more efficient digitized world by performing multiple tasks simultaneously. Accessing data from web service concurrently can lead to generating the results in lesser time [12]. Concurrency can be put into picture by using threads in the component technology i.e. for this work we have used XAMPP. Multithreaded programs run faster than single-threaded programs giving a better throughput [22]. But to implement the multithreaded programs, some challenges need to be handled such as debugging, testing, and synchronization. Such challenges have been overcome using web service application for a testing client and server-side scripts. The component technology tools used here are XAMPP and the scripting language used is PHP. Below in Fig. 1, there is an example showing how concurrency is handled in web service applications (here PHP scripts) programming.

OPEN IN VIEWER

The above example in Fig. 1 shows the creation and end of the series of threads. The threads are executing in parallel. All threads start at the same time and each finishes in a one-second gap between each thread. Given that the sleep time is being incremented on each new thread being spawned. It shows how concurrency could be handled in web service applications.

3.1 Slicing of procedure-oriented programs

Weiser has proposed program slicing for the first time in 1979 [1]. Weiser described program slicing, the process of extracting those lines of codes from a given program that may be affected by the point of interest. The point of interest is known as the “Slicing Criterion” at which the slice has to be estimated. The slicing criterion is considered as a pair s, V $>$ based on which slice needs to be found, where ‘s’ is the statement number and ‘V’ is a set of variables. In 1984, Weiser [3] introduced the inter-procedural program slicing algorithm which is an extension of the intra-procedural program slicing algorithm. The concept behind this is that inter-procedural slices can be obtained by the advancement of the existing algorithm over other procedures.

Ottenstein et al. [4] introduced a new form of computing program slicing, that is by traversing through the graph of a program rather than doing calculations by equations. They have developed an intermediate graph representation called Program Dependence Graph (PDG) which is confined to represent the program with one procedure. Hence, the intermediate graph PDG helps in providing effective resultant slice for the single-procedure program and not able to work out for inter-procedure programs with many procedures. In 1990, Horwitz et al. [5] developed another intermediate graph called System Dependence Graph (SDG), to model the dependencies among subprograms and developed a two-phase inter-procedural slicing algorithm to compute precise slices. To make the computation of interprocedural program slices more effective, they proposed a step-wise algorithm that traverses backward on the SDG.

3.2 Slicing of concurrent OOP

Many researchers have done intensive works in the slicing of the concurrent programming paradigm [30, 31, 32]. Zhao [18, 29] has proposed a slicing algorithm to compute slices of Java programs that are concurrent. He has proposed an intermediate graph representation called Multithreaded Dependence Graph (MTDG) for the multithreaded programs in Java which is the extension of System Dependency Graph (SDG). Though the paper has come up with the efficient computation of slices of multithreaded Java programs based on MTDG, still it is missing with the implementation issues of the same.

Krinke [30] proposed the context-sensitive approach for slicing concurrent programs correctly by taking time-sensitive information for computing slice. The author has proposed an intermediate graph namely threaded Interprocedural Dependency Graph (tIPDG) by introducing a new edge called interference edge. The problem of the shared variable in a different thread is solved in this approach. But, the slicing technique developed by the author is insufficient to find the slices where the serialization or inlining process is present.

Mohapatra et al. [19] developed an approach for computing slices of multithreaded object-oriented programs. In this technique, the intermediate representation graph developed was Concurrent System Dependence Graph (CSDG), and slices are computed based on this intermediate graph representation of the program. Basing on emerge and drop of dependencies during execution time, the edges of CSDG and are marked and unmarked. The new algorithm developed here is Marking-Based Dynamic Slicing (MBDS) which works efficiently by eliminating the use of trace files.

3.3 Slicing of concurrent AOP

Zhao et al. [20] presented the unique technique for computing a dynamic slice of Aspect-Oriented programs. For computing slice of Concurrent AOPs, Zhao proposed an intermediate graph called Aspect-Oriented System Dependence Graph (ASDG), which is constructed in three phases: an SDG for non-aspect code, an SDG for aspect code and several additional dependency edges for connectivity. This dependence graph is the extension of SDGs to represent aspect-oriented programs.

Ray et al. [21] improvised the existing dynamic slicing approach developed by Zhao et al. [20] to find the dynamic slices of concurrent aspect-oriented programs. The intermediate graph developed in this approach is named as Concurrent Aspect-Oriented System Dependence Graph (CASDG). The CASDG of a multithreaded AOP integrates dependence graphs for the non-aspect code, aspect code, and some new dependence edges used to connect the SDG and the dependence graph for aspect code. The slicing algorithm developed is the extension of the Node marking Dynamic Slicing (NMDS) algorithm [32] in which edges are marked or unmarked based on arising or ceasing during execution time.

Singh et al. [22] proposed a new context sensitivity approach for computing slices of concurrent AOP having multiple threads. The intermediate representation graph developed by the author is the Multithreaded Aspect-Oriented Dependence Graph (MAODG). A slicing algorithm is proposed which is based on the intermediate graph (MAODG) and a point of interest called slicing criterion as input to produce its slices. A slicing tool is implemented by designing a slicer and considering a sample example of an online auction system. They have computed the efficiency of their algorithm by comparing their approach with Ray et al. [21].

OPEN IN VIEWER

Looking at the literature survey, it has been found that the origin of slicing was introduced by Mark Weiser [1, 3]. Replacing mathematical calculation for the computation of slice through graphical representation was proposed by Otteinstein [4] and Hortitz [5] in the form of PDG and SDG. Zhao [18, 29] implemented slicing on other programming paradigms like an object-oriented program that is concurrent and proposed Multithreaded Dependency Graph (MTDG). However, the extension over it was proposed by Krinke [30], which takes time-sensitive information for computing slice. and most importantly, slicing through marking and un-marking of multithreaded object-oriented programs was created by Mohapatra et al. [19]. Zhao [20] also implemented slicing over Aspect-oriented programs by proposing Aspect-Oriented System Dependence Graph (ASDG). Ray et al. [21] improvised on the existing ASDG to be implemented on concurrent Aspect-Oriented Programs by proposing Node Marking Dynamic Slicing (NMDS) Algorithm. A slicing tool was developed by Singh et al. [22] for computation of slice of concurrent AOP by proposing a Multithreaded Aspect-Oriented Dependency Graph (MAODG). The gap found here is an implementation of slicing over Component-Oriented Programs (COP). This paper deals with the computation of slicing on COP that is concurrent by considering a case study that will be discussed in the next section.

5.1 Concurrent Control Flow Graph (CCFG)

In component-oriented programs, concurrency is handled by the use of threads. Control Flow Graph (CFG) can be constructed for each thread. Two components namely Hotel and Flight in the example case study shown in Fig. 2, are represented as a thread to execute independently and concurrently. However, the threads are independent but the interface scraps the data from three components to build up a new component. Hence, to represent the concurrent program, the collection of CFGs of each component will not suffice its requirement. So, additional edges are added into the CFG to represent communication among components referred to as Concurrent Component Flow Graph (CCFG). A CCFG is the integration of CFGs of all components along with new dependencies for connecting components with the interface. CFG for every single component is constructed from which two are represented as threads.

First, we construct the CFG [19] of each component and interface as in Fig. 2 shows the control flow/dependencies between components, threads, and interface. To interconnect the components and interfaces, a new dependency edge called Component Connect Edge (CCE) is developed. Another new edge called Thread Component Edge (TCE) is introduced, for connecting threads to more than one component simultaneously for more efficient results. To run the components concurrently, we need to execute two methods of a thread that is, start() method and the corresponding run() method. For all the components in the concurrent program, the process needs to be repeated.

OPEN IN VIEWER

Concurrent Component-Oriented programs are represented by extending the existing intermediate graph representation CmDG proposed by Pujari et al. [33] and named this intermediate representation as Concurrent Component-Oriented Dependency Graph (CCmDG). The CCmDG is constructed by the addition of data dependencies to the CCFG, as shown in Fig. 3. Concurrent Component-Oriented dynamic slicing is explained by considering a simple case study (example program) shown in Fig. 2 where an interface is designed to get connected with three components and access required data. Apart from that, two components are defined as thread, for concurrent execution of both. The CCmDG is a directed graph G = (N, E) where ‘N’ is the collection of nodes and ‘E’ collection of edges. Each node n belongs N represents the Line number in program code and each e that exists in E represents the occurrences of the dependencies in CCOP. Fig. 8 picturing the CCmDG contains the following types of edges.

•

Data Dependency Edge: r1 → dd r2 ∈ E, is said as a data dependency edge if there exist two nodes r1 and r2, where r1, r2 ∈ N transfers data from r1 to r2.

•

Control Dependency Edge: r1 → cd r2 ∈ E, is said as control dependency edge if there exist two nodes r1 and r2, where r1, r2 ∈ N such that there are transfer of control from r1 to r2.

•

Component Connect Edge: r1 → cce r2 ∈ E, is said as component connect edge if there exist two nodes r1 and r2, where r1,r2 ∈ N such that r1 ∈ interface, r2 ∈ component based on a predicate.

•

Thread Connect Edge: r1 → tce r2 ∈ E, is said as thread connect edge if there exist two nodes r1 and r2, where r1,r2 ∈ N such that r1 ∈ interface and is a thread calling node, r2 ∈ component which enters the run() method. Also, another dependency that can be found during runtime is thread dependency, that exists between the last statement of a thread and a statement of the interface once that thread is being called.

: Algorithm to generate CCmDG[] CCOP Codes A SDG G N, E $>$ 1. Construct the CCFG.

a.

Individual nodes are created for each statement of each component of the program.

b.

Add a Control Dependent edge, n1 → cd n2, if n1 transfers the control to n2.

c.

Add Call edges between each node of type submit and the pages during runtime specified in the associated call in the graph.

d.

Add a Component Connect edge to interconnect the components and interface of the program.

i.

Add a component-connect edge, n1 → cce n2, if n1 is the node of an interface and n2 is the node of a component based on the predicate.

e.

Add a Thread Connect edge to interconnect the multiple threads of the program for concurrent processing.

i.

Add a thread connect edge, n1 → tce n2, if n1 is the node of an interface and is a thread calling node, n2 ∈ component which enters to its run() method.

ii.

Also, another dependency that can be found during runtime is thread dependency, which exists between the last statement of a thread and a statement of the interface once that thread is being called.

f.

Add a Call edge, n1 → call n2, if n1 is a form submission node and n2 is the dynamic page which is to be reached.

2. Construct CCmDG.Add a Data Dependent edge, n1 → dd n2, if n2 is data-dependent on n1.

OPEN IN VIEWER

Figure 4.

CCmDG of the concurrent COP.

OPEN IN VIEWER

Figure 5.

Example case study.

5.3 Construction of CCmDG

CCmDG is the extension of CmDG and a collection of CFGs, which gives the information regarding the flow of controls, component connects, thread dependencies in a CCOP. Data dependency edges are added to CCFG to capture the complete flow of data throughout the system and acquire CCmDG. So, for a given case study of a Component-Oriented program Q, CCFG is constructed first, then CCmDG of Q is constructed based on CCFG. The process of construction of CCmDG of a CCOP can be carried out as shown in Algorithm 1.

Figure 3 shows the CCFG of the example program (Fig. 2). This graph reflects only the control dependencies, Component connect edge, and thread connect edge between the components and interface. Node i13 invokes node in the first component and collects the data, hence the edge is called component connect edge while nodes i23 and i24 are nodes that invoked two threads concurrently and the edge called thread connect edge, Thread1-Hotel and Thread2-Flight. CCFG is added with an additional dependency called data dependency to form CCmDG. Figure 4 shows the CCmDG of the example program (Fig. 2). The step by step process of the generation of CCmDG is explained in Algorithm 1. Initially, CCFG of each component and interface is created. Then interface and components are connected by different edges as CCE, TCE depending on the interconnectivity. If there is a call to another page, then the call edge is added to CCFG. Lastly, CCmDG is constructed by an additional data dependency edge to CCFG.

6.1 Proposed algorithm of concurrent COP slice

: Algorithm to find slice from CmDG[1] An CCmDG G N, E $>$ , a slicing criterion The Slice S for s.

Initialise TL1 = {s}, TL2 = {}, TL3 = {}, S = {s}

n represents current node

T ⁢ L ⁢ 1 ! = ϕ //phase1 each x → n //x is the source node for incoming edge to current node n T ⁢ L ⁢ 1 = T ⁢ L ⁢ 1 - { n } //remove the current node from TL1 x ∉ S S = S + { x } e ∉ {cce} or e ∉ {tce} //if e is edge between a to n, e is not component/thread edge T ⁢ L ⁢ 1 = T ⁢ L ⁢ 1 + { x } if e ∈ {cce} { x } → Call P //P represents node in another component T ⁢ L ⁢ 1 = T ⁢ L ⁢ 1 + { x } T ⁢ L ⁢ 2 = T ⁢ L ⁢ 2 + { P } if e ∈ {tce} { x } → Call Q //Q represents node in thread T ⁢ L ⁢ 1 = T ⁢ L ⁢ 1 + { x } T ⁢ L ⁢ 2 = T ⁢ L ⁢ 2 + { Q } T ⁢ L ⁢ 2 ! = ϕ //phase2 T ⁢ L ⁢ 2 = T ⁢ L ⁢ 2 - { n } //remove the current node in TL2 S = S + { n } each b → n //a is the source node for incoming edge to current node n b ∉ S S = S + { b } T ⁢ 3 ! = ϕ //phase3 T ⁢ 3 = T ⁢ 3 - { n } //remove the current node in T3 S = S + { n } each c → n //a is the source node for incoming edge to current node n c ∉ S S = S + { c } return S

In Algorithm 2, we have extended a two-phase algorithm to three-phase to handle concurrency in COP. Here we have considered three transaction list TL1, TL2, TL3, for traversing interface edges, component edges, and thread edges respectively. Details of computing of slice are explained in the next section.

6.2 Slice computation

In our proposed intermediate graph CCmDG, the components and interface are interconnected by using new edges such as component connect edge (CCE) and thread connect edge (TCE). Working of our slicing algorithm is described by considering a case study as shown in Fig. 2. Considering the point of interest as node i25 and to reduce ambiguity in identifying nodes of different components and interface, alphabets a, b, c and i are attached with node numbers (alphabets a, b, c are for statement numbers in component 1, 2, 3 respectively and i for identifying statement in the interface). Hence, the list of nodes traversed in the initial state is given below:

In the first traverse, the algorithm restricts with slicing criterion and traverses backward along edges such as control flow, data flow, call edges except component connect edge (CCE), and thread connect edge. During this traversal, all vertices in CCmDG are being marked and added to slice and TL1, TL2, TL3 as per the type of edges that are being reached. Then in the second traversal, all the vertices in CCmDG stored in TL2 are traversed backward by the algorithm, along with the component connect edges (CCE) and pushed to the slice. Lastly, in the third traversal, the vertices present in TL3 have traversed backward along the thread connecting edges (TCE) and pushed to the slice. Hence, finally, we result in a slice which is having all the nodes encountered during the three traversals of CCmDG.

In the first step, the node that is reached in CCmDG are popped from TL1 and in case of its absence in S, it is added to the slice S. This is done by verifying all the incoming edges to the current node and the node is pushed to TL2 or TL3 depending on the type of edge encountered (CCE or TCE) and nevertheless, it is added to TL1 for further processing in Step 1. Hence, the list of vertices after the first step/traversal are:

In step 2, similarly, the vertices present in TL2 are traversed backward in CCmDG (which represents Component connect edge) and the node is popped from that list after traversal, added into slice S. The process could be carried out by verifying all incoming edges to the current node. The process is repeated until the list is empty. After the second traversal/step, the slice would contain such nodes:

In step 3, in the earlier process, all the vertices/nodes (which represent thread connect edge (TCE)) in TL3 are being encountered by verifying all incoming edges to the current node. The current node is popped out from the list after traversal and added to the slice S. Similar process is repeated until the list is empty. At last step/traversal the resultant slice is as such:

Hence for the given slicing criterion NDi25, the slice found is

6.3 Resultant slice

OPEN IN VIEWER

The resultant slice of the intermediate representation graph CCmDG of the concurrent COP is shown in Fig. 4. The marked nodes represent the resultant slice of the case study undertaken.

7.1 Experimental setup

PHP-Slicer is a partial tool developed for the automatic generation of CCmDG and slice computation. To develop the slicing tool, we have used a personal computer with the specification of Intel(R) Core i5-7200U processor, x64 based processor, the clock speed of 2.50 GHz, with an internal memory of 8 GB, Windows 10 Home Basic (64 bit) operating system. The result may vary if any other computational environment is used to reproduce our findings.

OPEN IN VIEWER

Figure 7 shows a block diagram of our Slicing tool PHP-Slicer, in which six packages are being studied and each program of the web application is analyzed to generate CCmDG. After the PHP script is loaded, the initial PHPScript Interpreter studies all the PHP statements and stores all functions and variables in the respective tables. Here data internal to the system are stored in an internal storage system and edges are also read to computes data, control dependencies within the statements. Next,HTMLScript Engine package finds out all HTML tags like input $>$ , table $>$ and form $>$ and a individual node is created for each statement. A call dependence edge is inserted in any of these statement contains a PHP script page call in between. This edge is inserted between the two matching nodes from the table that is generated during the PHPScript section. However, this package mainly identifies the control dependencies present within the HTML nodes.

As our work deals with remote sites, the Scrapper part takes care of all the external or remote server connectivity and extraction from the HTML engine. This part consists of the Remote Server analyzer (connectivity), the Request Action Engine (Extraction) acts as a crawler. And at last, the scrapped data is collected in an internal storage system in a localhost server. Lastly, the data from the 3 engines i.e local PHP script engine, remote action engine, and internal storage are input to CCmDG to generate the graph. The graph is provided as input to a web slicer tool, which results in generating slice based on a slicing criterion provided. The proposed tool enables us to generate the slice as per the point of interest.

7.3 Case study

Five case studies are observed to verify the competence of our proposed PHPSlicer tool. In each of the case studies, a CCmDG has been generated for each PHP page that we have taken and have computed slices according to slicing criteria. The case studies that are considered are presented in Table 1.

7.4 Findings

Table 2 shows the details of CCmDG generated for each PHP page. The table shows the size of each case study and the number of PHP pages content in it. The CCmDG generator has created the CCmDG for each case study project. In column number three of Table 2, we present the number of nodes created in the CCmDG followed by the number of edges and time taken by the tool to generate each CCmDG. From Table 2 we can observe that as the size of the component increases, the size of CCmDG is also increasing. And, hence the time taken by our tool to generate the CCmDG is also increasing with larger size components.

In the literature, we cannot find any existing work in the field of slicing of COPs. To present the efficiency of our proposed work we have considered the trivial slicing technique proposed by Weiser [1], which is termed as Weiser’s algorithm. In Weiser’s algorithm for computing slices, no constraint or restriction is imposed while traversing backward from the slicing criterion and identifying the nodes of SDG to be present in a slice or not. It means that according to his slicing algorithm, the slices are computed by a blind backward traversal from the slicing criterion to all reachable nodes of the SDG. But, in our proposed slicing algorithm we check the context-sensitive nodes while finding the slice. The context-sensitive slicing [22] ensures that while backward traversal in a given SDG, we must consider only that function from where we have entered into the current function. It restricts the blind traversal into all functions.

Evaluation Parameters:

1)

Average Slice Size: Suppose there is n number of slices compute where s 1 , s 2 , s 3 , … , s n denotes the size of individual slices. The size of a slice represents the number of nodes or statements present in that slice. Then, the average slice size is computed as,

Average Slice Size = 1 n ⁢ ∑ i = 1 n s i(1)

2)

Average Slice Time: Suppose there is n number of slices computed where t 1 , t 2 , t 3 , … , t n denotes the time taken to compute individual slices. Then, the average slice time is computed as,

Average Slice Time = 1 n ⁢ ∑ i = 1 n t i(2)

In the experimental study, we have computed many slices by using both Weiser’s algorithm and our CCmDS algorithm taking different slicing criteria. For summarization of our findings, the average slice size and average slice time are calculated by dividing their summation in each slice by the number of the computed slice. All the observations for case studies are listed in Table 3.

OPEN IN VIEWER

Figure 8.

Comparison of average slice size.

7.5.1 Implications

In this section, based on the average slice size, we have compared the result of our experiment. The case studies that have been considered in our experiment behaves similarly. We observed that the average slice size computed by the CCmDS algorithm is smaller than slices computer by Weiser’s algorithm for all case study projects, as shown in Fig. 8. To compile it, our proposed algorithm CCmDS generates 11% smaller slices compared to that of Weiser’s algorithm.

Then, by taking average slice computation time into account the two algorithms are compared and came to be observed that our algorithm computes slices much speedier than the Weiser’s algorithm, as shown in Fig. 9. From our five case studies, we found that our CCmDS algorithm generates slices of 31.91% speedier than the Weiser’s algorithm.

OPEN IN VIEWER

After the total observation we can deduce these points:

•

The slice produced by our proposed CCmDS algorithm is smaller in size compared to that of the slices produced by Weiser’s algorithm. Hence the slice is more precise.