A Little Less Interaction, A Little More Action: A Modular Framework for Network Troubleshooting

An ideal network troubleshooting system would be an almost fully automated system, monitoring the whole network at once, feeding the results to a knowledge-based decision making system that suggests actions to the operator or corrects the failure automatically. Reality is quite the contrary: operators separated in their offices try to track down complex networking failures in their own way, which is generally a long sequence of manually edited parallel shell commands (mostly ping, traceroute, route, iperf, ofctl etc.). This process requires operators to be"masters of complexity"(which they often are) and continuous interaction. In this paper we aim at narrowing this huge gap between vision and reality by introducing a modular framework capable of (i) formalizing troubleshooting processes as the concatenation of executable functions [called Troubleshooting Graphs (TSGs)], (ii) executing these graphs via an interpreter, (iii) evaluating and navigating between the outputs of the functions and (iv) sharing troubleshooting know-hows in a formalized manner.

Introduction
Troubleshooting a communication network was never an easy problem. Finding causes of errors and failures, tracking down misconfigurations in the increasingly complex interconnection networks of heterogeneous networking devices is quite a challenge. What is more, the prevalence of increasingly complex software components, due to the upcoming software defined networks (SDNs), adds distributed software debugging as an additional issue to deal with. To cope with this increasing complexity, the networking research community suggests the use of knowledge-based decision support together with the standard network monitoring and diagnostic tools, and the conversion of troubleshooting into a highly automated process. Reality seems to reside very far away from this vision. Real operators tend to use the most basic diagnostic tools for monitoring the network, and rely on their own brilliance and programming skills when digging out the root causes of errors in an ad-hoc manner from the reports of these tools. Even if this approach works well in practice, it requires extremely skilled operators who can keep in mind all the details of the network under scrutiny and their continuous interaction usually is wasted on rummaging in the logs of the tools used by them.

State of the Art in Network Troubleshooting
From the great volume of related literature we highlight here the two main constituents of troubleshooting systems. The first is clearly the area of network monitoring and diagnostic tools, of which main purpose is to seek for symptoms of specific failures. The palette is very broad here, ranging from the most basic tools-like ping, traceroute, tcpdump, netstat, nmap [1] or GNU Debugger (GDB)-, through monitoring protocols-such as SNMP and RMON [1]-, configuration files and analyzers-such as Splat [2]-, performance measurement tools-such as iperf [1]-and packet analyzers-like Wireshark-, to the more complex ones-such as NetFlow, HSA [3,4] and ATPG [5]. On top of these, SDN specific tools have added a whole new segment targeted to investigate specific parts of the architecture. Tools such as Anteater [6], OFRewind [7], NetSight [8], VeriFlow [9], NICE [10], SOFT [11], FORTNOX [12] and OFTEN [13] all fill a niche in SDN troubleshooting.
One level up, the output symptoms of these tools can be aggregated and fed into different automatic reasoning solutions. The first representatives of these were created as early as the second half of the 1980s [14] targeting the discovery of failures in telecommunication networks. Early on, rule-based methods were used to resolve issues by using if-then statements [15]. Later case-based reasoning [16] and model-based [17] methods were developed. The former utilized a collection of previous cases as a basis for failure analysis, while the latter used models of structural and functional behavior to reason about network issues. Fault-symptom graphs [18] and dependency or causality graphs [19,20] introduced the concept of tracking failures using graphs that created connections between symptoms, detection and root causes. This concept led to the application of Bayesian networks [21,22] where belief-in the most probable failure root cause-propagation is based on a probabilistic model.

What We See in Current Practice
Despite the readily available set of advanced troubleshooting tools and decision support mechanisms, operators seem to use the most rudimentary tools (like ping, traceroute, tcpdump etc.) while they completely rely on their minds as a knowledge-base. For testing this, we conducted an in-house survey querying which type of problems local administrators run into most frequently and what network troubleshooting tools they use most commonly. The results that we found were completely in accordance with those outlined in [23]. Most problems were caused by connectivity issues that arose from a variety of reasons ranging from hardware failures to configuration changes that became necessary due to security issues. Used troubleshooting tools show similarities also: mostly simple task specific tools are utilized, in certain cases combining them in a script to explore typical failures. Network information is usually stored in simple spreadsheets and proprietary monitoring or troubleshooting tools are used only when they have a low cost-or are preferably free. We found that automatic tools are less frequently used and manual troubleshooting dominates problem solving.
To get a deeper sense of the process, think of an operator logging into different devices and running heterogeneous software tools (e.g. the tools listed above) to analyze the problem. Network conditions are monitored simultaneously in multiple shells and after a painful rummaging in the tools' outputs, new commands are evoked on new devices. We argue that this approach has its own merits and drawbacks. It is extremely flexible as the operator uses the tool of her choosing in the way and logic she sees fit. On the negative side, it is quite ineffective, unorganized and anything but re-usable. The operator's time is spent mostly on filtering and finding the correlation between the different outputs and keeping in mind the mapping between different shells and devices.

Design Principles of a Modular Framework for Network Troubleshooting
Instead of proposing a new troubleshooting tool or another decision support mechanism, we suggest here a framework 1 capable of combining existing (and future) special-purpose tools and reasoning methodologies in a modular fashion. Our concept builds on the observation that operators combine different troubleshooting tools to find out the root cause of a network issue. In the following sections, we go through the main notions that we use to describe such troubleshooting processes and the fundamentals of our framework capable of executing troubleshooting graphs (TSGs).

Nodes: Wrappers Around Troubleshooting Tools
The first thing we need is an abstraction that incorporates the basic elements of a troubleshooting process. Thus we define our nodes as wrappers around troubleshooting tools or smaller, processing functions. Nodes are considered as black boxes that hide their internal operation from the operator (see Fig. 1). Operators have three types of interfaces for communicating with nodes: inputs, on which the nodes execute operations (e.g. a text stream to process or clock ticks), configuration arguments and outputs for relaying information.
The outputs can relay the exact output of the wrapped tool or provide extra processing before generating their results. Nodes are also responsible for providing documentation for these interfaces.
Nodes have three stages of their life cycle: initialization, execution and termination. The initialization stage is where the environment setup of the node is done, including resource allocation and initial configuration. Nodes enter this stage of their life cycle only once. At the execution stage, nodes read the data arriving on their inputs and start the wrapped process or function. Analysis or modification on the wrapped tool's output is also performed  here. The node is constantly in this stage when it has been initialized but not yet been terminated. Finally, the node reaches the termination stage when it is being stopped. This stage is responsible for clearing up allocated resources and terminating wrapped processes. We identified two basic node types: processing nodes and display nodes. The first interprets its inputs andafter processing-it relays the results on its outputs. The second type only interprets input data and is responsible for creating a graphical representation for it, e.g. in the form of a chart or a graph.
For an example, consider a basic node wrapping the traceroute tool. The node outputs the trace (optionally from a remote machine) to a specific host every time we call it. Let's define first the node's interfaces: • Inputs: only a single input is needed for receiving an enabling signal. Each time this input changes, the node should call the traceroute command.
• Configuration arguments: we can simply choose to make these the same as the command line arguments of the traceroute command. If we want to run traceroute on a remote machine, we can add another argument to specify the remote host.
• Outputs: the node should output the results returned by the traceroute call on its first output. On the second output, it shows the last hop on the way to the specified target.
In the initialization stage, when requested, the node sets up connection to the remote host where traceroute should be run. At execution time, it calls the traceroute command and relays its unmodified result to the first output while analyzing it. If the analysis found the last hop, the node sends this information to its second output. In the termination stage, the ongoing processes are stopped and the connection to the remote host is closed, if it had been set up.

Edges: Accessible Data Transfer
We use edges to describe the connections between nodes. Besides specifying the nodes to connect, the main feature required from edges is to provide accessibility for node outputs: information over the edges is observable and modifiable on demand by the operator. When access is provided to edges, the operator can see what is happening in the troubleshooting process on the lowest levels. When historical data is available on the edges, the operator can backtrack how network conditions changed during runtime. Modifiable edges provide the additional benefit of direct operator interaction with nodes, which is helpful for instant testing purposes. Let's take the example when our troubleshooting scenario is described as a path graph and the first node infrequently outputs data. In this case, the rest of the nodes are also executed rarely and it is quite hard to test whether our graph works as expected.  When having the option of modifying edge content, we can easily inject test data on the first edge instead of creating a test node that would supply the same data. This method also helps channeling-otherwise unobtainable-data into our system from the network environment.

The Troubleshooting Graph
Building on the concept of wrapper nodes and accessible edges, a TSG can be created that is able to describe troubleshooting processes as series of tools and transformations. The top part of Fig. 2 depicts a simple TSG that queries, in every five seconds, an SDN controller-accessible on the local machine-for topology information and displays it using a graph visualization node. A special grouping node, the View, creates a grouping consisting of a node and an output, in order for these to be displayed together.
Besides the simple concatenation of nodes, creating branches is possible through special purpose decision nodes. These nodes are processing nodes able to analyze incoming data and match against a specific criteria set. Such nodes can provide generalized decision making apparatus that can combine results arriving from different nodes and implement arbitrary decision functions to analyze and evaluate them. For example, such a function can validate the output of the ifconfig tool and decide whether or not each interface is configured correctly. Another example can be a function that accepts numerical inputs and computes a weighted combination of them, like nodes do in a Bayesian or neural network. We do not consider these decision functions as part of our tool, they can be added to the framework by operators or third parties in a modular fashion. We note that a large collection of decision functions can significantly shorten the creation time of effective branching TSGs.

A Language for Describing TSGs
For a text-based representation of TSGs, we define a simple Click-inspired [25] description language. Such language fits perfectly to our concept as we look at nodes as black boxes that have inputs, outputs and configuration arguments, which the language supports by default. Port-based explicit node linking is also a feature that we make good use of. Nodes can be defined by assigning an instance name to a wrapper node using the :: operator (see line 1 of Fig. 2). For simplicity, the instance name can be omitted if the node is not referenced in the code later on. Configuration arguments follow the node instance assignment in parentheses (see line 1). Nodes can be linked with edges by linking expressions, using the -> linking operator. Line 3 of the example shows a port-based explicit linking of the topology and view nodes. A linking operator always has the list of node outputs on its left side and the list of inputs on its right side, thus multiple edges can be created between two nodes in a single expression. Outputs and inputs are always referred to with their zero-based indices. In case only the 0 th input or output appears in a linking expression, one can omit its index, as depicted in line 1 of Fig. 2. In our language-unlike in Click-one can connect outputs to configuration arguments as well, which enables the flexible dynamic configuration of nodes. This uses the same syntax as the output-input linking. To distinguish between inputs and configuration arguments, a hyphen should be prepended to the one-based index of the configuration arguments (see lines 20-21 of Listing 1 for an example). We created a special linking operator, the -->, that can be used when connecting the node itself to a View, as used in line 2 of our example 2 . Terminating an expression (a node declaration or a series of linkings) should always be done with a semicolon.

Execution Framework for TSGs
To bring the TSG concept closer to implementation, we designed an execution framework capable of interpreting TSGs, executing them and providing intelligent navigation among the (possibly many) outputs of the tools used in the TSG.

Interpretation
Since a TSG is only a formal description, the framework provides a parser to interpret the graph. Two methods are available to accomplish this. The first option is building the graph by interpreting its definition written in our description language. Using this method, graphs can be saved and later reused and shared. The parser collects the nodes, their configuration arguments and the links between the nodes. Objects are created for nodes and edges. The framework assigns names to node and edge objects that uniquely identifies them. The second option is creating the graph incrementally at run time using a drag and drop method. This method has the benefit that the operator can monitor the output of the used tools and adjust her methodology to the results she has acquired until that point (which is fully in line with current practice). The parser creates the objects for the nodes and interconnections, and creates a description for these using the language. Run-time modification of the graph is provided by this functionality as well. These two methods provide flexibility while retaining the benefit of being able to store troubleshooting scenarios, situations.
In order to help writing a TSG definition file, the framework provides syntax highlighting to differentiate semantic units. Using the nodes' self-documentation capabilities, the framework is able to provide on-the-fly node documentation.

Execution
The TSG concept describes how to connect tools to each other but it does not deal with the problem of when and how a node's life cycle is managed and how a node is notified when its inputs are updated. After interpretation, the framework creates placeholders for nodes which they can then use for displaying graphical data. Once TSG execution is started, the framework is responsible for handling node execution, as depicted in Fig. 3. The framework creates a scheduler that handles a queue for registering node output changes. Each time an output has changed, the framework queries which nodes have that as their input. These destination nodes are then inserted to the end of the queue. Parallel to this, a simple scheduling mechanism is running that always takes the first item from the beginning of the queue and sends a signal to that node to enter into the execution stage. When the call returns, the scheduler moves to the next node in line and so on.

Navigation Options
The benefit of handling interconnected troubleshooting tools as a graph is that it creates a natural order in the troubleshooting process. In order to better manage the complex information set contained in the graph, the framework provides different apparatuses to aid observing the execution state and navigating through the graph. A special node class, a View, is available that can collect nodes or their outputs and group those to be displayed together. When a name appears without a class assignment, the interpreter assumes that it is a View. Layout of such groupings can be explicitly specified or left to the framework to create an automatic one. The framework provides methods for graph traversal by jumping through successive nodes and edges and offers a semantically ordered grouping for nodes and edges contained in the currently displayed TSG. It also provides a visualization method that creates a graphical representation of the TSG.

Recommendation System and Knowledge Sharing
The framework provides a recommendation system that is able to suggest new nodes for the operator, based on her current setup, by searching for similarities in a TSG repository. Operators can upload their existing TSGs to this repository hereby promoting knowledge sharing.

An Everyday Example
For showcasing our framework, we present here an everyday example that (or very similar cases), almost surely, appears in the practice of every operator. We set up a Mininet emulated network to create failures and compare manual troubleshooting with our TSG-based methodology. In our network, hosts are connected to servers via OpenFlow switches and ordinary routers-emulated as hosts having the ability to route between their interfaces. The switches act as simple layer 2 devices, we use only static routes and iptables is applied for creating firewall rules. SSH access is set up for every device in the network. We inject various network related errors to cause the most basic symptom of a network issue: a host on the network is not able to connect to a server. Emulated errors encompass hardware failures-link and port failures-, configuration errors-faulty configuration of hosts, misconfigured routes and firewall rules on routersand application level errors-misconfigured or unresponsive applications. Our task is to identify and correct the error: first in line with current practice and then, using our framework.

Current Practice
By applying manual troubleshooting using multiple shells to connect to different devices and running different troubleshooting tools, we made the following observations. We had to repeatedly log into devices when starting a new tool and for every new tool, a new terminal had to be opened. Processes running in currently open terminals could have been terminated in order to minimize the overpopulation of our environment but than we would have  Figure 4: Flow chart for troubleshooting the exemplary scenario.
lost information. We had to analyze the data provided by the tools ourselves and it took a considerable time when we were dealing with great amounts of data. Finally, we noticed that the list of applicable troubleshooting tools could be narrowed down to a minimum and then it did not matter what the root cause was, we ended up using the same tools in the same sequence to find the problem. Thus we came up with a flow chart for this troubleshooting scenario (see Fig. 4). One major problem with the multiple shell approach is that there is no clear way that the process-the steps to be taken-can be recorded and later reused.
To test connectivity we used ping. For checking the local host's configuration we applied the host, ifconfig and arp tools. Forwarding rules were queried by route, and firewall rules were retrieved using iptables. The steps shown in Fig. 4 could have been grouped together into a single shell script file for automation purposes but we found that method less clear and portable.

Using TSGs
Now we show that the above process can be easily mapped 3 to a TSG, as most of the nodes are already identified by the processes and decisions on the flow chart (Fig. 4). We use extended wrapper nodes for the tools, so-on top of their basic functionality-we assume that Host, Ifconfig and Arp nodes provide means to exclude specified interfaces from their outputs, the Traceroute node is able to relay the last hop until which the traffic is traceable and the Route and Iptables nodes are capable of displaying only those rules that apply to certain IP addresses.
For brevity, Listing 1 shows only 4 the instructions used for creating a TSG that performs a connection test and if that is unsuccessful, checks the local machine's network configuration. This exemplary TSG is not complete: Listing 1: Formal description of the TSG. routes and firewall rules are not checked. Instructions for creating nodes for those tests, however, would be written using the same philosophy shown here. Decision nodes in the TSG take the same role as the decisions shown on the flow chart of Fig. 4, while the Decision-summary node interprets decisions in the TSG by signaling "error" codes with visual aids for the operator. (Decision nodes are only briefly discussed here, see Section 5.2 for more details.) In order to perform a connection test between the current host and a server, we use a wrapper node for the ping tool in line 1. Lines 2-3 create tests for checking the local host's configuration using the ifconfig and arp tools. In order to automatically evaluate these, we defined three Decision nodes. ping-decision checks whether the ping was successful. ifc-decision uses a custom function to validate the interface configuration returned by the ifconfig node-the loopback interface is ignored by the test for obvious reasons. The arp-decision node performs a simple check to test whether there are entries in the Address Resolution Protocol (ARP) cache. These Decision nodes are then connected with their respective wrapper nodes in lines 14-16. In order to check the local host's configuration only when the connection test was unsuccessful, we need to connect the ifconfig node to the negative output of the ping-decision node-line 18 implements that. If there are interfaces on the host that are correctly configured, we need to check whether the host can register the layer 2 addresses from its network. We defined a Function node in line 19 in order to retrieve the interface names from the output of the ifc-decision and fed these to the our Arp node. Finally, we defined a Decision-summary node in lines 23-25 to display information collected from every Decision node in a summarizing table. A possible output (generated with our prototype) of the Decision-summary node is shown in Fig. 5. The node gives the results of the individual decisions in the TSG as well as an overall evaluation of the current troubleshooting scenario.
This simple example attests that by using TSGs, we can achieve a state of automation where the parametrization of troubleshooting tools adapts to the current network situation and issue. When executing this TSG, the operator can recognize failure modes at a glance by looking at the error codes, or can further delve into details by navigating through the outputs of nodes. Using the navigation options provided by the framework, the operator can walk through the troubleshooting process in an orderly fashion. Results are going to be displayed according to the workflow, she laid out when she had designed the flow chart for locating the issue. Even more, the operator has the means to hide irrelevant data by grouping nodes and edges together with Views, or at runtime select only those, she deems relevant to the situation at hand.
By offering proper formalization, TSGs can be reused in similar scenarios. In some cases, the whole graph can be reused with only slight adjustments to the node configuration arguments to adapt to other network conditions. In other cases, subgraphs of the original TSG can be reused for testing different scenarios. Besides re-usability, TSGs can act as a technique to collect troubleshooting know-hows. Once a network problem is uncovered using a TSG, it automatically becomes a guideline for discovering future similar issues. By collecting a library of these, operators can greatly decrease problem solution times and the efficiency of knowledge transfer to new operators can also increase. If TSGs are not only collected within a closed environment-i.e. within a company-but are shared with a greater audience, they can prove to be beneficial for the whole networking community. If a wide TSG library is paired with problem descriptions and solutions, new nodes and test cases can be recommended to an operator, based on previous cases described by TSGs in the library.

Prototype
For proofing the concept of our framework, we created a prototype implementation named Epoxide using GNU Emacs as a platform. Emacs is an extensible, customizable text editor, its central concept, the buffer, is responsible for holding file contents, subprocess outputs, providing configuration interfaces, etc. By its extensible nature, Emacs offered a particularly good platform to build Epoxide upon. Emacs supports, via its advanced text manipulation and documentation functions, writing TSG definitions that we store in .tsg configuration files. We implemented our execution framework and wrapper nodes using Emacs's own Lisp dialect, Emacs Lisp. Nodes and their outputs are assigned to Emacs buffers for observability. Node interface and connection information is stored in buffer local variables. We note that while Emacs proved to be a good fit for our notions, the concept described in Section 3 can be implemented on other platforms as well.

Framework Functions
Opening a .tsg file in Emacs automatically loads Epoxide and interprets the TSG stored in it. After assigning node objects and outputs to buffers, nodes can write in these buffers directly during their execution stage. In our prototype implementation, nodes use other nodes' output buffers directly as their inputs. Thus TSG edges do not have independent objects.
Emacs's ElDoc package uses the nodes' self-documentation property to provide hints on node interfaces during TSG definition. When Emacs's Auto Complete package is installed, it can provide intelligent code completion for setting up nodes.
Once a TSG is running, there are two ways to modify edges and node configuration arguments. The first method is runtime TSG reconfiguration, which is provided via an Emacs widget based interface. It allows the addition of TSG edges and modification of static configuration arguments. Modifications are committed to the .tsg file as well. The second method a TSGs can be modified is by way of editing the .tsg file and reevaluating it. This method has the downside that buffer contents prior to the modification get lost.
Once a TSG is processed, execution is started. The framework stores events in a simple Emacs Lisp list and utilizes the timerfunctions package for scheduling node execution. Basic navigability among the created buffers is provided by Emacs key bindings. Epoxide supplies the apparatus to move from one node buffer to its output buffers or to the next node's buffer (in forward or backward direction). To traverse a TSG, a visualization can be used also, supported by the Emacs COGRE package. When the Graphviz external software is installed, the displayed graph can be drawn using an automatic layout for better visual clarity. Semantic grouping of the created buffers is provided using the Ibuffer package: a dynamic list is displayed that aggregates buffers based on their types and roles in the current context.
The current implementation of Epoxide provides a module for collecting TSG related data and supplying node recommendations. We created the instrumentation for basic case-based reasoning where currently available TSGs are considered as descriptions of previous troubleshooting cases. These TSGs are indexed and their data-together with information from the current TSG-is passed to a recommender. The recommender then can suggest nodes based on these pieces of data. We created an interface in the framework to which recommenders, developed by third parties, can connect as well. By now, we have implemented the most basic recommender that suggests the most popular nodes and displays them using Emacs's Ido package. Most popular nodes are computed by counting every node in all previously written TSGs and ordering them in the descending order of their cumulative count. Nodes that are already used in the current TSG, are excluded from the suggestion list.

Branching Nodes
When creating the apparatus that enables conditional branching in Epoxide, the most basic expectation was to (i) provide functionality to analyze and evaluate the output of any node and, based on the result, (ii) create branches in a TSG, the same way a decision would in a flow chart. Additionally, we wanted to have the ability to (iii) select among different inputs or to use a combination of them. This criterion was inspired by how nodes work in a Bayesian network: they receive the results of lower level nodes and calculate their outputs based on that. To satisfy these criteria, we implemented a single Decision node. Since nodes can be added to Epoxide in a modular fashion, this is only one possible implementation that satisfies our initial criteria. Operators are free to add their own version. A Decision-summary node was developed in conjunction, for summarizing the outputs of such nodes. Fig. 6 shows the schematics of our Decision node. The node can attach to any wrapper node 5 and incoming data is first verified (as per (i)): it is determined whether it complies with certain criteria. The node can use any function for verification that has at least one argument (the input) and can return false, when verification failed, or any string otherwise. When verification of the inputs is finished, further processing can be done using a second stage function, in accordance with (iii). An operator can use a function to select an input with, for example, the or function: the first of the inputs that passed verification is going to be the result of this stage. Other functions can implement more complex processing, like in the aforementioned Bayesian network example where the result would be a probability value. Such second stage functions should return a string in case of a positive decision or false otherwise. We defined two node outputs to relay these return values (as per (ii)). The first displays information in the positive case, the second in the negative. We implemented an additional output for interoperating with Decision-summary nodes.

Implementing Nodes
The modular architecture of Epoxide makes it possible for anyone to implement new nodes 6 . A node developerwho implements a node-has to create separate node definition files that contain Emacs Lisp code to provide selfdocumentation for nodes and implement the three life cycle stages via functions. For proper interaction with nodes, the node definition files and these functions should comply with a fixed naming scheme. Node self-documentation functions should provide information about node interfaces and could also implement validation functions to check the compliance of arguments with certain criteria. The functions implementing the separate node life cycle stages are called by the framework on specific occasions. The initialization function is evoked after the buffers belonging to the node are set up. The execution function is called every time a change occurs on any of the node's inputs. Finally, the termination function is invoked before the framework closes the buffers associated with the node. These functions can draw on common node functions provided by the framework. Epoxide implements functions for setting up node buffers with basic data, reading inputs and configuration arguments, writing outputs and handling remote access using Emacs's Transparent Remote Access, Multiple Protocols (TRAMP) package.

Case studies
The basic example shown in Section 4 demonstrated integration of troubleshooting tools originally developed for traditional networks. Although these can also be used to troubleshoot SDNs, tools created specifically for these networks can leverage the benefits of centralized network control.

Troubleshooting in SDNs
We implemented nodes to interact with POX, Floodlight and OpenDaylight controllers and Open vSwitch (OVS) switches. These nodes are able to collect dapatapath identifiers (DPIDs), flow statistics and topology information. Additionally, we created processing nodes for filtering flow statistics on a flow space 7 basis and for visualizing topology information. In order to aid controller debugging, we wrapped the GDB tool as well. To support other . .  Table-view node (bottom). controller platforms, a general node for accessing REST APIs was implemented, as well as other nodes that are able to filter specific parts of JSON-formatted textual data.

Table-view
To illustrate an SDN use-case, imagine the following scenario: a network consisting of SDN switches is given and an operator wants to monitor a certain traffic flow in the network. She can set up a TSG to solve this problem by first defining a node querying DPIDs from the controller on a timely basis, as depicted in the top part of Fig. 7. A Function node can then separate the list of available DPIDs and pass those to further nodes that query flow statistics from their assigned switches. With the addition of flow space filtering nodes, the operator can select only the flow under scrutiny and display the results in a table format, as depicted by the bottom part of Fig. 7. She can investigate further by adding nodes that query flow statistics from the controller and from the switches themselves, and compare the results with Decision nodes: this could reveal synchronization issues between the devices or misdirection of the traffic caused by a software failure. By connecting Gdb nodes with the Decision nodes, the operator can remotely connect to software switches or to the controller for an in-depth analyzation of the problem. 8

Troubleshooting in Service Function Chaining
One of the main goals of the UNIFY project 9 was to design a Service Function Chaining control plane architecture and implement a proof-of-concept prototype. Additionally, the project also introduces the concept of Service-Provider DevOps to combine the developer and operational workflows in carrier grade environments. DevOps results in faster deployment cycle of novel networking services. Instead of designing complex services as a whole, these services are assembled from atomic network functions. However, fast deployment cycles require faster testing phases 8  and troubleshooting in the operational environment. Even when a new service is created by re-using components of previous ones, it is still going to be different enough from earlier scenarios to implicate new troubleshooting challenges. In these cases, previous knowledge is not always directly applicable. By providing an integrated platform for running troubleshooting tools and an apparatus to automatize their execution, our tool makes the formation of new troubleshooting scenarios easier, thus enabling quicker service deployment. Epoxide has a central role in the multipurpose demonstrator showcasing major results of the project [27]. Using its dedicated and general purpose wrapper nodes, it orchestrates multiple components in a semi-automatic troubleshooting scenario. Epoxide needs to reveal a configuration error resulting in erroneous imbalance of the traffic loads of OpenFlow switches instantiated as network functions. The novel components, which Epoxide interacts with, include a flexible messaging bus (Double Decker), a tool that calculates aggregated performance metrics derived from data queried from hierarchical time series databases [Recursive Query Engine (RQE)], and a test packet generator for pinpointing errors in OpenFlow switches (AutoTPG). 10 Fig. 8 highlights the main system components and the sequence of interactions. First, a monitoring component detects the resource imbalance that automatically triggers the execution of the troubleshooting process in Epoxide that executes a TSG tailored for this scenario (step 1). In step 2, Epoxide asks the Recursive Query Engine to narrow down the location of the error to a subset of OpenFlow switches. After querying historical measurement data (steps 3-4), RQE returns a list of switches to Epoxide (step 5). In step 6, Epoxide starts and configures AutoTPG and asks it to test candidate switches one by one. AutoTPG tests correctness of the switches in steps 7-8 and returns the result to Epoxide in step 9. Finally, Epoxide queries the flow-entries of the erroneous switch (step 10), and presents those in tabular from to the user to help further investigating the problem manually.
The hundred-line long TSG of the demo contains a wrapper node for the messaging bus, but communicates with the other tools via Rest-api nodes. REST API calls request JSON-formatted inputs and emit JSON-formatted outputs. While most of the nodes discussed so far assumed unstructured plain text inputs and outputs, in this case we needed Json-filter nodes to prepare the outputs for post-processing, and Format nodes to assemble JSON-formatted inputs for the API calls. This example shows that there is not too much difference between a TSG processing structured JSON data and a TSG processing unstructured data line-by-line: similar filter nodes are necessary in both cases. The TSG also exemplifies the usage of a Tee node and the Command node. Similarly to its Unix counterpart, Tee copies its input text to its output link and saves the text in a file. Command is used for running an ssh command to modify the configuration of a remote network function.
Epoxide exhibits properties that make it an ideal testing and troubleshooting tool for Service Function Chaining. First, the TSG language is an enabler of fast hypotheses testing and small feedback cycles because it allows connecting existing special purpose troubleshooting tools at an abstract level. Second, the test generation process can be further shortened by simply re-using parts of existing .tsg definitions. Third, complex decision logics can be based on service-specific monitoring and troubleshooting tools by writing simple wrapper nodes around these tools.

Conclusion and Future Work
While our modular framework proposed here is capable of flexibly combining various troubleshooting tools for tracking down networking issues, and the TSG concept enables the accumulation and sharing of troubleshooting related knowledge, the current prototype implementation should be extended in many aspects. Of course, a large library of wrapper nodes should be added to incorporate more and more troubleshooting tools. Besides this natural option, we outline here some future directions, the framework could benefit from. Although present implementation supports the addition of new node recommenders, the currently implemented one provides only a basic functionality. We consider this a good basis to implement better recommenders. The first in line is a recommender that analyzes the current TSG and-by finding the most similar TSG from a collectionsuggests new nodes based on that. This concept could be further improved by tagging the TSGs as to what sort of problems they were used for finding out and taking into account the tags during recommendation. Suggestions could be made more relevant if the environment of the nodes were to be taken into consideration as well, and node configuration arguments could be suggested also.
To support our case-based reasoning approach, we imagine a repository of TSGs accessible by anyone for viewing old cases and uploading new ones. At the same time such a repository is set up, recommenders could be moved to the cloud as well, resulting in a more efficient computation of suggestions on a much greater collection of TSGs compared to a locally computed model.
Since case-based reasoning is not the cutting edge of decision support systems, we can use the TSG concept as a failure detection graph to be used as a Bayesian network, and make node suggestions based on that. Finding an applicable failure propagation model is key to this approach. We believe, we can take this concept even further by using a Bayesian network based method and combining it with active diagnostics-where new network tests are selected automatically depending on current results-for TSGs to be built with little operator intervention or totally unsupervised.

B List of Nodes Currently Implemented in Epoxide
Arp: queries the ARP cache by evoking the arp command.
Clock: provides a signal on a timely basis.
Command: wraps any shell commands. These are run as Emacs subprocesses.
Decision-summary: summarizes the results of connected Decision nodes.
Doubledecker: connects to a DoubleDecker broker and is able to receive and send messages to a partner or to a topic.
Emacs-buffer: provides options to channel information from any Emacs buffer to Epoxide.
Escape: queries NFFG topology information from Escape.
Filter: marks incoming text that matches a given regular expression.
Flow-space-filter: provides support to select only that flow space that is wished to be seen.
Flow-stat-<controller type>: provides functionality to query an OpenFlow controller for flow statistics of a specific switch given with its DPID.
Format: collects text from its inputs and reformats them.

Function:
wraps any Emacs Lisp function or nameless function.
Gdb: attaches a wrapped GDB to a running process.
Graph: provides graph visualization support.
Host: performs DNS lookup using the host shell-call.
Ifconfig: wraps the ifconfig shell command.
Iperf: wraps around the iperf command.

Json-filter:
finds the values belonging to a given key in a JSON expression.
Ping: wraps the ping command.
Rest-api: performs REST API calls.

Route:
wraps the route command. Tee: wraps around the Unix tee command: while forwarding incoming data it also saves it to a given file.
Topology-<controller type>: queries topology information from an OpenFlow controller.
Traceroute: wraps the traceroute process.


A novel approach in detecting code clones in Java using DFS

Article history: Received 9 January 2017 Received in revised form 5 April 2017 Accepted 7 April 2017 Code is the rudimentary element of any software. Code clones may be defined as the segments of the program which are akin to one another. The similarity may be either syntactic or semantic. Cloning is easy to implement but hard to detect. Many researches have been carried out in order to find the methods for detecting these clones of code as problems are encountered at the time of maintenance due to these clones in codes. This further increases the cost of maintenance. The objective of our work is to precisely detect the code clones. Here, an approach is proposed based on the Abstract Syntax Tree method. The purpose for adopting AST is that it gives better detection results as compared to other techniques and is considered to be the best approach for detecting type 3 code clones. Furthermore, AST offers syntactic knowledge which can be leveraged to filter certain types of clones. The results obtained clearly shows that the technique adopted is able to precisely detect the near-miss clones as compared to the tools namely NICAD and CLAN.

Introduction
*Code cloning is the act of copying the segments of code and pasting it to another place. At the first glimpse it seems to be a fascinating concept as the programmer doesn't need to write the same code again and again if the working of two code segments needs to be similar, but copy-paste strategy is a short term win.
Copying the code from one position and pasting it to another has various pitfalls which come into sight at the time of maintenance and testing of the software. If there are complications in the original code that was pasted it will be disseminated to the cloned/pasted segment too. For example, if a programmer makes any slight modification in the code and if the same change is not made in the cloned part then it may produce inconsistencies. In the large software systems it becomes really strenuous to uncover where this code has been reused. Searching in entire program is time consuming and practically an infeasible job. Clones produces bad impact on the design and also on the system improvement and modification as it is quite common that the person who developed the original system is not the one who is maintaining it. In the long run, the software may become so complex that even minor changes are hard to make. Clone detection came into existence to solve this problem.
With the help of clone detection technique, we can easily find out where the clone exists and can remove them beforehand so that they don't create any problem in future.
The studies reveal that almost (5-10 %) of the source of large computer programs is duplicated code (Baxter et al., 1998).

Types of code clones
There are various levels of clones as identified by Bellon et al. (2007). They are:  TYPE-1: the codes which are exactly similar to one other without any kind of difference in the source code are placed under Type-1 clones. They may also be termed as syntactically similar codes.  TYPE-2: the codes which are similar to each other except some of the changes in the white spaces, variable names, data type, arguments etc. are put under Type-2 code clones. They are also syntactically similar codes.  TYPE-3:the codes with further modifications allowed in the source code like some of the additional code lines may be added or the ones present in one may not be present in another but both performing the same function are placed under Type-3 code clones.
 TYPE-4: they are semantically or behaviorally similar code segments. They don't have anything common in the source code but the functions performed by them are exactly the similar of each other. The example of each kind of the clone is given in Table 1.

Root causes for code clones
A study by Kontogiannis et al. (1996) reveals why programmers just copy and paste the code. They identified the following reasons by observing the programmers in their daily practice:  Sometimes it may be due to the short time limits given to the programmers by the client for the development of the software.  Systems are modularized based on the principles such as minimizing coupling, information hiding and maximizing cohesion. In the end -at least for the systems written in ordinary programming languages-the system is composed of fixed set of modules (Koschke, 2007). Ideally, if the system needs to be updated, only few modifications will be required.  Another root cause is that programmers often reuse the copied text as a template and then customized the template in the pasted context (Koschke, 2007). Other potential reasons such as time pressure, educational deficiencies, development process, and short sightedness must also be investigated.  Phobia of fresh code.  Complexity of the system.

Clone detection methods
There are various methods of detecting the clones which includes:

Text based
They are language independent and provide an easy way to detect the clones among various programming languages. The major shortcoming of this method is that it can detect only Type-1 clones along with some of the Type-2 clones which minor changes such as different formatting style.

Token based
In this technique, the code is first of all transformed into the token sequence. After that the sequence is formed from some set of tokens which are then compared to find the clones. The major advantage of token based technique is that it is fast with higher recall values.

Syntax tree based
Here, we use the parser to build parse trees or abstract syntax trees from the source code. The trees thus obtained can be processed further using the tree-matching to find the clones. Roy et al. (2009) explained that the abstract syntax tree or parse tree contains the complete information about the source code. In order to find the clones using the syntax tree approach, the subtrees are compared and those which come out to be similar are considered as the clones. The code corresponding to these sub-trees are returned as clone pairs.

Graph based
A program dependency graph (PDG) represents control and data flow dependencies of a function of source code (Rattan et al., 2013). In other words, it considers the semantic information encoded in the dependency graph. Clones may be identified as isomorphic sub-graphs in a program dependency graph (Krinke, 2001).

Metrics based
In Metrics-based approach, a number of metrics are assessed for the code segments which can involve the number of lines, number of input statements, number of output statements, return statements, function calls etc. in each of the segments. The metric values are then compared instead of the source code directly. The two segments whose metrics values comes out to be similar to each other are considered as clone pairs.

Proposed approach
Observing the advantages and disadvantages of various techniques developed so-far, here abstract Syntax Tree based approach is used to detect the code clones. Our approach will find the syntactic clones in linear time and space.
Here we used the Depth First Search (DFS) algorithm which is an algorithm for searching in a tree. One starts at the root and explores as far as possible along each branch before backtracking. The approach adopted is as follows: 1. Firstly the code will be passed into the ANTLR parser. ANTLR (another tool for language recognition is a parser generator that uses LL (*) for parsing (https:// en.wikipedia.org/wiki/ANTLR). ANTLR can generate lexers, parsers, tree parsers and combined lexer parsers (https:// en.wikipedia.org/wiki/ANTLR). The purpose of doing so is to obtain the syntax tree representation of the code. The example of AST formed for a particular code is ( Fig. 1  DFS (Depth First Search) is applied to both the trees in parallel.  Then for each of the node of the tree, convert it into the template. The procedure for template conversion is as follows:  Template conversion is the procedure of converting the source code into a new form which is uniform intermediate representation of source code.  Type 1 clones are exactly similar to each other so there is no need to convert them into templates.  For type 2 clones, the clone methods may contain difference in names of variables ,identifiers, data types, white spaces etc. for converting them into template, we can replace all the identifiers names into a common name as 'X' and all the data types into a common data type 'DATA'.  For type 3 and 4: in case of type 3-4 clone detection, various constructs like branches, iterations can also be changed. Therefore we need a general method for converting them into a form which is common. The method for the conversion is given in the Table 2:  Then for each node (converted into template) check if the children of the node in the tree exist.
If it exists, store them in prefix order in an array (apply this procedure on both the trees whose nodes are now present in the form of templates)  Compare the elements in both the arrays. If similar elements exist, store them in a separate list.
 Now, for all the elements/nodes which exist in the list, apply Levenshtein (1966) distance algorithm to find out the distance between the nodes.
 It is applied considering two nodes at a time and comparing them element-by-element.  If the two nodes comes out to be  Exactly similar, their cost will be set as 0 otherwise 1 in the opposite case.  Now for all the pairs of nodes in the tree whose Levenshtein (1966) distance/ cost comes out to be 0 are stored in an array and are marked as the clone pairs.

Results
The proposed approach has been tested on various open source software available. The implementation is done with the help of the selfcreated tool with input of JAVA project files. The tool is able to find out precisely Type1, Type 2 and Type 3 code clones. The project sources used is shown in the Table 3. The source codes of the above projects are fed into our system and the clones are detected in their source codes. The results obtained are as follows in Table 4. The results obtained in the form of clone pairs are in Table 5.

Comparison with existing tools
The tool developed using the proposed approach is being compared with the existing tools. The two tools are used other than the proposed one. They are NICAD and CLAN. They all are applied onto the projects. The results obtained are in Figs. 2 and 3.

Conclusion and future work
In this paper, we have proposed an approach to detect Type-1, 2 and 3 code clones. The proposed approach quickly detects Type-2 and 3 clones which normally are not being detected by all the existing approaches and if they do so, then not as precisely as the proposed approach.
In this approach we are able to feed only a single source code file at a time. For future work, we may apply the detection at the directory level which may contain multiple numbers of files in it and detects the clone pairs in them. Type-2 Tpye-1


Describing Natural Images Containing Novel Objects with Knowledge Guided Assitance

Images in the wild encapsulate rich knowledge about varied abstract concepts and cannot be sufficiently described with models built only using image-caption pairs containing selected objects. We propose to handle such a task with the guidance of a knowledge base that incorporate many abstract concepts. Our method is a two-step process where we first build a multi-entity-label image recognition model to predict abstract concepts as image labels and then leverage them in the second step as an external semantic attention and constrained inference in the caption generation model for describing images that depict unseen/novel objects. Evaluations show that our models outperform most of the prior work for out-of-domain captioning on MSCOCO and are useful for integration of knowledge and vision in general.

INTRODUCTION
Content on the Web is highly heterogeneous comprising mostly visual and textual modalities. In most cases, these modalities complement each other to illustrate the semantics of concepts and objects. Many approaches have leveraged such multi-view content for Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). Conference'17, July 2017, Washington, DC, USA © 2017 Copyright held by the owner/author(s). ACM ISBN 978-x-xxxx-xxxx-x/YY/MM. https://doi.org/10.1145/nnnnnnn.nnnnnnn grounding textual with visual information or vice versa. Natural language processing (NLP) tasks like monolingual word similarity [15] and language learning [8] were improved by grounding textual with visual information. The grounding of visual with textual information has shown improvement for existing computer vision (CV) tasks such as image annotation [27]. The aforementioned tasks can be further subdivided into two broad categories where the first category of tasks combines the semantics of multiple modalities to achieve common representation for representational tasks such as generation of descriptions for images or videos [30,31] and visual question answering [3]. While the second category of tasks leverages cross-modal semantics to identify the relationship between visual and textual content for attaining referential grounding [5].
Several approaches are proposed to solve varied tasks separately with methods from both categories. However, procedures from both categories can benefit by complementing each other. For example, many approaches for the representational task of generating captions for images are inspired by encoder-decoder architecture or its variations that encompass an attention mechanism [4] learn model using only (visual)image-(textual)caption parallel corpora. This causes the model to fail in describing those images which contain unseen/novel objects and concepts not part of parallel captions. Also, the vocabulary is limited to frequent words in the captions and often fails to incorporate rare or infrequent words. Given such challenges, we strive towards a solution that addresses the bottleneck in the aforementioned representational task.
Usage of structured information provided by a knowledge base (KB) [17] has shown to assist several textual tasks such as question answering over structured data [6], language modeling [1], and generation of factoid questions [24]. Our hypothesis is that caption generation for images containing unseen/novel objects can significantly benefit from employing structured information (henceforth called knowledge) provided by a KB.
Thus in this paper, we aim to address the task of generating captions that include unseen visual objects in images with our proposed solution termed as knowledge guided assistance (KGA). The aim of KGA is to operate as referential grounding by providing external semantic attention during training and also work as a dynamic constraint while inference of a caption generation model. In particular, KGA assists to generate captions for unseen/novel objects in images which lack parallel captions. This makes KGA differ from earlier approaches that perform similar task such as deep arXiv:1710.06303v1 [cs.CV] 17 Oct 2017 compositional captioning (DCC) [11] and novel object captioner (NOC) [29] by not depending solely on the corpus specific word semantics for next word prediction in a caption generation model. Also, when compared with constrained beam search (CBS) [2] KGA incorporates more information from textual caption data by not constraining solely on image tags. In this respect, KGA is closer to LSTM-C [33] which uses object classifiers and copying mechanism, but KGA diverges by using attention mechanism and dynamic weight transfer as opposed to word copying. Figure 1 presents an overview and the main contributions of this paper are summarized as follows: • We designed a novel approach to improve the representational task of caption generation including unseen/novel visual objects with the assistance from a knowledge base. • We created a multi-label image classifier for grounding depicted visual objects to knowledge base entities. • We conducted an extensive experimental evaluation showing effectiveness of KGA.

RELATED WORK
Our related work can be drawn from many closely aligned areas.

Grounding Natural Language in Images
The grounding of natural language in images is employed to comprehend objects and their relationships. Flickr30k Entities [22] is one such approach that augments the Flickr30k dataset images with bounding boxes using all noun phrases present in their parallel textual descriptions. We also leveraged textual descriptions for grounding in images, but to explicitly relate objects with their knowledge base entities. Other approaches [9,14] also tried to relate knowledge to images, but not by explicitly linking it to KB. However to extract visual knowledge for supporting tasks such as question answering and image retrieval.

Attention Mechanism in Caption Generation
Initially, attention mechanism was applied to tasks such as image caption generation [32] with two different possibilities i.e. soft and hard attention. Another recent improvement is seen in performing adaptive attention with visual sentinel [19] by identifying when to look inside an image for cues and not every time as aforementioned would do it. As both of the aforementioned approaches would look entire image to add global context, region-based attention [13] was proposed to experience visual perception where the attention shifting among the visual regions imposes a thread of visual ordering. Slightly, deviating from earlier visual feature centric approaches, the attribute based attention [34] extracted attributes from an image and used them as input vectors resembles our approach.

Dealing with Rare/OoV Words
Usage of external vocabulary or the structured data is becoming prominent in many neural network models. Goal of these approaches is to copy information from external sources whenever the neural network models fail to predict with certain confidence. Recently, a neural knowledge language model [1] was proposed to improve language modeling with external structured data to improve tasks which are dependent on entities and also extended for text generation [16]. Some approaches [10] have used copying mechanism to deal with out-of-vocabulary (OoV) words, while few adopted pointing mechanism [20]. Our approach for constrained inference fall in-line with such approaches, but rather prefer to enhance neural model weights than direct copying.

DESCRIBING IMAGES WITH NOVEL OBJECTS USING KNOWLEDGE GUIDED ASSISTANCE (KGA)
In this section, we present our caption generation model for generating captions for unseen/novel image objects with support from KGA. The core goal of KGA is to introduce external semantic attention (ESA) into the learning caption generation models and KGA also work as a constraint for transferring learned weights between seen and unseen semantic and word image labels during inference.

Caption Generation Model
Our image caption generation model (henceforth, KGA-CGM) combines three important components: a language model pre-trained on unpaired textual corpora, external semantic attention (ESA) and image features with a textual (T), semantic (S) and visual (V) layer (i.e. TSV layer) for predicting the next word in the sequence when learned using image-caption pairs. In the following, we present each of these components separately while Figure 2 presents the overall architecture of KGA-CGM.

Language
Model. This component is crucial to transfer the sentence structure for unseen visual objects. Language model is implemented with two long short-term memory (LSTM) [12] layers to predict the next word given previous words in a sentence. If − −− → w 1:L represent the input to the forward LSTM of layer-1 for capturing forward input sequences into hidden sequence vectors where L is the final time step. Then encoding of input word sequences into hidden layer-1 sequences at each time step t is achieved as follows: Similarly, layer-1 hidden sequences supplied as input to layer-2 are encoded as follows: where Θ represent hidden layer parameters. Finally, the encoded hidden sequence ( − → h 2 t ∈ R H ) at time step t is then used for predicting the probability distribution of the next word given by Equation 3.
The softmax layer is only used while training with unpaired textual corpora and not used when learned with image captions.

External Semantic Attention (ESA).
Attention mechanism was first introduced by Bahdanau et al. [4] in an encoder-decoder architecture. It was particularly useful for dynamically changing context while decoding. Later, the attention mechanism was extended to other tasks such as speech recognition [7] and multimodal  A language model implemented with a 2layer forward LSTM where L1-F and L2-F represents layer-1 and layer-2 respectively, a multi-word-label classifier to generate image visual features and multi-entity-label classifier to support ESA. w t represents the input caption word, c t the semantic attention, p t the output of probability distribution over all words and y t the predicted word at each time step t. BOS and EOS represent the special beginning and end of sentence tokens respectively.
representational tasks. A feasible case of multimodal representational task is image caption generation, where attention is perceived from two different aspects i.e. visual attention [32] and attribute attention [34]. Visual attention leveraged spatial image features, while attribute attention leveraged attributes obtained from an image.
Our objective from ESA is similar to attribute attention, but leverages entity annotations as semantic labels obtained using a multi-entity-label image classifier (discussed in the later section). Entity annotations obtained are analogous to image patches and attributes.
In formal terms, if ea i is an entity annotation label and e i ∈ R E the entity annotation vector among set of entity annotation vectors (i = 1, .., L) and β i the attention weight of e i then β i is calculated at each time step t using Equation 4.
where p t i given by Equation 5 and f (e i , h t ) represent scoring function which conditions on hidden state (h t ) of a caption language model. It can be observed that the scoring function f (e i , h t ) is crucial for deciding attention weights. Also, relevance of the hidden state with each entity annotation is calculated using Equation 6.
where h t ∈ R H , W he ∈ R H ×E is a bilinear parameter matrix. Once the attention weights are calculated, the soft attention weighted annotation vector of the context c, which is a dynamic representation of the caption at time step t is given by Equation 7 Here, c t ∈ R E and L represent the cardinality of entity class annotations per image-caption pair instance.

Image Features.
The image aligned with captions are used to extract visual features using multi-word-label image classifier (discussed more in later sections). To be consistent with other approaches [11,29] and for a fair comparison, our visual features (I ) also have each index corresponding to the probability of word-label annotation in the image.

TSV layer.
Once the output from all components is acquired, the TSV layer is employed to integrate their features i.e. textual (T ), semantic (S) and visual (V ) yielded by language model, ESA and images respectively. Thus, TSV acts as a transformation layer for molding three different feature spaces into a single common space for prediction of next word in the sequence.
If h 2 t ∈ R H , c t ∈ R E and I t ∈ R I represent vectors acquired at each time step t from language model, ESA and images respectively. Then the integration at TSV layer of KGA-CGM is provided by Equation 8.
where W h 2 t ∈ R vs×H ,W c t ∈ R vs×E and W I t ∈ R vs×I are linear conversion matrices and vs is the image-caption pair training dataset vocabulary size.
3.1.5 Word Prediction. The output from the TSV layer at each time step t is further used for predicting the next word in the sequence using a softmax layer given by Equation 9.

KGA-CGM Training
To learn parameters of KGA-CGM, first we freeze the parameters of the language model trained using unpaired textual corpora. Thus, enabling only those parameters to be learned with image-caption pairs emerging from ESA and TSV layer such as W he ,W h 2 t ,W c t and W I t . KGA-CGM is now trained to optimize the cost function that minimizes the sum of the negative log likelihood of the appropriate word at each time step given by Equation 10.
Where L (n) represent the length of sentence (i.e. caption) with beginning of sentence (BOS), end of sentence (EOS) tokens at n-th training sample and N as a number of samples used for training.

KGA-CGM Constrained Inference
Inference is not straightforward as in earlier image caption generation approaches [31]. Unseen/novel image objects have no parallel captions throughout training, hence they will never be generated in a caption during inference. Thus, unseen/novel objects require guidance from similar objects or external sources during inference. Earlier approaches such as DCC [11] have leveraged similar concepts (i.e image word-labels) to transfer weights between seen and unseen word-labels. However, similar labels are found only using word embeddings of textual corpora and are not constrained on images. This obstructs the view from an image leading to spurious results. We resolve such issues by constraining the weight transfer between seen and unseen image labels (i.e. both semantic and word) with help from KGA. As the first step, we identify closest similar word-label of unseen objects with their Glove embeddings [21] learned using unpaired textual corpora. Now, for transferring weights between seen and unseen image labels, we perform dynamic weight transfer during test image caption generation with help of entity annotation semantic labels (ea) provided by multi-entity-label image classifier. Whenever the word predicted by our KGA-CGM model is the closest similar word of an unseen object then the unseen object is checked for its presence in ea. If the unseen object is part of ea, then direct transfer of weights is performed between seen and unseen with W

LEARNING MULTI-LABEL IMAGE CLASSIFIERS
It can be perceived from earlier sections that the important constituents that influence KGA are the image semantic labels and features. Image features embody objects/actions/scenes identified in an image, while semantic labels capture the external semantic attention and entity class labels. In this section, we present the approach to extract both image features and semantic labels.

Multi-Word-label Image Classifier
To extract image features, emulating Hendricks et al. [11] a multiword-label classifier is built using the caption aligned to an image by extracting part-of-speech (POS) tags such as nouns, verbs and adjectives attained for each word. For example, the caption "A young child brushes his teeth at the sink" contains word-labels such as "young (JJ)", "child (NN)", "teeth (NN)" etc., that represent abstract concepts in an image. An image classifier is trained now with multiple word-labels using a sigmoid cross-entropy loss by fine-tuning VGG-16 [25] pre-trained on the training part of the ILSVRC-2012.

Multi-Entity-label Image Classifier
To extract semantic labels which are analogous to the word-labels, the multi-entity-label classifier is build with entity labels attained from a knowledge base annotation tool such as DBpedia spotlight 1 .
Considering the caption presented in the aforementioned section, entities extracted from the caption are "Brush 2 " and "Tooth 3 ", which will be treated as semantic labels. An image classifier is now trained with multiple entity-labels using sigmoid cross-entropy loss by fine-tuning VGG-16 [25] pre-trained on the training part of the ILSVRC-2012.

EXPERIMENTAL SETUP
In this section, we describe the experimental setup employed for our experiments.

Resources and Datasets
Our approaches are dependent on several resources such as toolkits etc., while datasets are utilized to conduct evaluations. In the following, resources, datasets and evaluation measures are presented.

Knowledge Bases (KBs).
There are several openly available KBs such as DBpedia 4 , Wikidata 5 , and YAGO 6 which cover general knowledge about entities and their relationships. We choose DBpedia as our KB for entity annotation, as it is one of the extensively used resource for semantic annotation and disambiguation [17].

Unseen Objects in Image-Caption Dataset.
To evaluate KGA-CGM, we use the subset of the MSCOCO [18] dataset proposed by Hendricks et al. [11]. The dataset is obtained by clustering 80 image object category labels into 8 clusters and then selecting one object from each cluster to be held out from the training set. Now the training set does not contain the images and sentences of those 8 objects represented by bottle, bus, couch, microwave, pizza, racket, suitcase and zebra. Thus making the MSCOCO training dataset to constitute 70,194 image-caption pairs. While validation set of 40504 image-caption pairs are again divided into 20252 each for testing and validation. Now, the goal of KGA-CGM is to generate caption for those test images which contain these 8 unseen object categories.

Evaluation Measures
To evaluate the representational task of caption generation, we use evaluation metrics same as earlier approaches [11,29,33] such as METEOR and also SPICE [2] to check the effectiveness of generated caption. CIDEr [28] metric is not used as it is required to calculate inverse document frequency used by this metric across the entire test set and not just unseen object subsets. F1-score is also calculated to measure the presence of unseen objects in the generated captions when compared against reference captions.

EXPERIMENTS
The experiments are conducted to evaluate the efficacy of the proposed approaches and their dependencies.

Implementing Multi-Label Classifiers
The key component of unseen image object caption generation is comprehending visual information. To realize it, we re-use existing and also build our own image multi-label classifier.
6.1.1 Multi-Word-Label Classifier. The principal role of the multiword-label classifier is to provide image features for caption generation. We use the pre-trained model [11] trained on the subset of MSCOCO using the approach presented earlier. The image features extracted represent the probabilities of 471 image labels occurring in a given image.

Multi-Entity-label Classifier.
The goal of multi-entity-label classifier is to recognize multiple semantic labels per image. To build the classifier, training set of MSCOCO dataset constituting 82,783 training image-caption pairs are used to extract around 812 unique labels with an average of 3.2 labels annotated per image. Additionally, features for the images are extracted using different layers such as pool5, fc6 and fc7 of VGG-16 [25] pre-trained on ILSVRC-2012 for fine-tuning with our semantic labels. Also, to comprehend the contribution of aforementioned layers to the accuracy of the classifier, we throughly analyzed separately the classifiers built using pool5, fc6 and fc7 as the initialization layers before finetuning. Our analysis revealed that pool5 features overfit even with regularization. To address this challenge, we trained a classifier with Caffe 7 by fine-tuning the layers above fc6 and fc7 which gave us an improvement in the accuracy as observed in Table 1. The classifier fine-tuned on fc6 features constitute two fully connected layers of 4096 and 812 neurons above fc6, with the first layer having 50% dropout and ReLU activation while the output layer comprises a sigmoid activation. Similarly, the classifier fine-tuned with fc7 features have an output layer of 812 neurons comprising a sigmoid activation. The loss function used during training is sigmoid crossentropy, while only sigmoid is used during prediction for exhibiting the presence of label probabilities. Figure 3 shows the predictions on the test dataset. It can be observed that fc6 gave the best result with an accuracy around 70% for top-12 and 74.4% top-16.

Entity-Label Embeddings
We presented that the acquisition of labels for multi-entity-label classifiers was obtained by the DBpedia spotlight entity annotation and disambiguation tool. These labels (i.e. entities) are expected to encapsulate general knowledge (e.g. encyclopedic knowledge) which is inter linked. Approaches [26] earlier have transformed such entities in a knowledge base into embeddings to capture their relational information for tasks such as knowledge base completion. In our research as well, we see the efficacy of these embeddings for caption generation. Entity embeddings leverages external semantic information to be used for attention. To obtain entity-label embeddings, we adopted the RDF2Vec [23] approach and generated 500 dimensional vector representations for all 812 labels used to represent images in the entire MSCOCO.
We further qualitatively evaluate these entity-label embeddings to check there affect on caption generation. Most images are respresented with more than one entity-label, thus providing multi-label information for each image. However, directly using their embeddings for ESA can affect caption generation if the label embeddings are not closely related. To check for their closely relatedness, we perform entity similarity. Table 2 shows the results of uneen/novel mscoco objects. It can be perceived from the Table 2 that most of the closely related entities always co-occur in an image as shown with few examples in the paper. Thus enhancing the caption generation model with ESA proven to be effective.
We also performed t-SNE visualization of all entity-labels to check how cluster together. It can be seen from the Figure 4 visualization some of the closely related objects which occur in the same context cluster close to each other.

Novel Objects Description
In this section, we evaluate KGA-CGM for unseen/novel image objects caption generation.
6.3.1 Implementation. One of the important component of KGA-CGM model is language model. Even though its weights are fixed during learning, the words in a caption are initially set with pretrained Glove [21] embeddings of 256 dimensions while the hidden layer dimensions are set to 512. Information about other components i.e. image features and semantic labels are already discussed in earlier sections. KGM-CGM is then trained with Adam optimizer with gradient clipping having maximum norm of 1.0 for about 15∼50 epochs. Validation data is used for fine tuning parameters and model selection.

Ablation Study.
To understand how different aspects of training KGA-CGM influence the unseen image objects caption generation, we perform ablation study by removing different components of KGA-CGM. Table 3 present the results obtained. It can  Table 4 shows the comparison of average scores based on METEOR, SPICE and F1 on all 8 unseen image objects with beam size 1 and greater than that (> 1). It can be noticed that KGA-CGM with beam size 1 was comparable to other approaches even though it used fixed vocabulary and image tags. For example, CBS [2] used expanded vocabulary of 21,689 when compared to 8802 by us. Also, our word-labels per image are fixed, while CBS uses a varying size of predicted image tags (T1-4). This makes it nondeterministic and can increase uncertainty, as varying tags will either increase or decrease the performance. In Table 5, we also present individual scores from all 8 unseen objects separately. Though our average scores were comparable to other approaches, for some of the unseen objects we attain state of the art results. We also add more analysis about the important components used in the KGA-CGM model in the Appendix.

Qualitative Analysis.
In the Table 6, sample predictions of our best KGA-CGM model is presented. It can be observed that entity-labels has shown an influence for caption generation. Since,   entities as image labels are already disambiguated, it attained high similarity in the prediction of a word thus adding useful semantics.

CONCLUSION AND FUTURE WORK
In this paper, we presented an approach to generate captions for images that lack parallel captions during training. Experimental results on unseen/novel image objects captioning exhibit that usage of structured information encapsulated in the form of relational knowledge (i.e KB) has unveiled a way to build connection between real world objects to their visual information. In future, we plan to expand our models to build multimedia knowledge bases that automatically can be queried based on relational information between images.

A APPENDIX
This appendix provides information on some of the quantitative and qualitative results of individual components in KGA-CGM. Also, more qualitative results of the generated captions on held-out MSCOCO objects is presented.

A.1 Language Model Hidden Layers
As presented in the paper, language model in our caption generation model (i.e KGA-CGM) is a 2-layer forward LSTM. For learning KGA-CGM with image-caption pairs, input caption word embeddings are chosen to be 256 dimensions, while the LSTM hidden layer dimensions for both layer-1 and layer-2 is selected as 512. However, varying hidden layer dimensions can show an influence on the caption generation results. In this section, we vary the hidden layer dimensions and analyze the consequences. Table 7 shows the METEOR, SPICE and F1 average measures on 8 unseen MSCOCO objects.

A.2 KGA-CGM More Qualitative Results
The attention weights (β t i ) of ESA contributes to the caption generation. Figure 5 visualizes the attention weights of the captions presented in the Table 6.  Table 6. X-axis labels represent generated captions and Y-axis labels are predicted entity-labels. Scores are normalized between 0 and 1.