\documentclass{article}
\usepackage[affil-it]{authblk}
\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
\usepackage{url}
\usepackage{hyperref}
\hypersetup{colorlinks=false,pdfborder={0 0 0}}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
  \errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}

\usepackage[utf8]{inputenc}
\usepackage[english]{babel}




\begin{document}

\title{Automata Based String Analysis  in JSAI}


\author{Gayathri Srinivasan}
\affil{Oakland University}



\date{\today}

\maketitle




\begin{quote}
\textbf{Abstract:}The Automata Based String Analysis in JSAI revolves around the idea of interfacing the Lib Stranger tool with the JSAI implementation. LibStranger stands for STRing AutomatoN GEneratoR Library \cite{Li_2012}. The LibStranger tool implemented in C language. LibStranger is an Automata-Based Symbolic String Analysis Library. You can use LibStranger to solve string constraints and/or compute pre and post-images of string manipulation operations such as concatenation and replacement. It can handle complex regular-expression based replace operations such as PHP's preg replace and approximate these operations in the presence of unbounded loops with high precision and smooth performance. In addition, LibStranger provides fast and precise modeling for common string functions such as trim, substring, toUpperCase and toLowerCase and complex sanitization functions such as PHP's addslashes and html specialchars. The Lib Stranger is built on top of the MONA \cite{monamanual2001,xml2001,powerforms2000,progress2000,dsdspec2000,trees2000}. MONA is a tool that translates formulas to finite-state automata. The formulas may express search patterns, temporal properties of reactive systems, parse tree constraints, etc. MONA analyses the automaton resulting from the compilation and prints out "valid" or a counter-example. MONA implements decision procedures for the Weak Second-order Theory of One or Two successors (WS1S/WS2S). The theory of one successor, known as WS1S, is a fragment of arithmetic augmented with second-order quantification over finite sets of natural numbers. Its first-order terms denote just natural numbers. The theory has no addition, since that would make it undecidable, but it has a unary operation +1, known as the successor function. WS2S is a generalization to tree structures. Since the theories are monadic second-order logics, we call our tool MONA. We interface the already available functionality of the tool with their specifications to do a backward string analysis of the java-script code to make it void of any code injection.  
\end{quote}

\section{Introduction}
Web applications are getting more an more popular these days with the advent of even replacing many of the existing desk top applications. With the development of the web-based solution it is notorious to have many hackers to get in-between the user and the system and exploit the vulnerabilities of the application. The Common Vulnerabilities Exposure (CVE) generally documents the top vulnerabilities that a web-application is exposed to, they have listed that the vulnerabilities has increased from 2 percent in 2001 to 45 percent in 2007 and is till increasing on a large scale, when the web-appliications are invloved. There were 3 main categories of vulnerabilities, HTML injection, Database code injection and Malicious File Execution. The HTML injection is that when the user injects a malicious content as a part of a user defined field. The database injection happens when the hacker injects a query along with a form data so as to introduce credentials of the hacker, which can in future aid him to login and make use of the functios provided. The Malicious File Execution is when the developer executes a file without validating its credentials, this will introduce bug inn the hosted platform there by crashing the entire system and teh data associated with the application. This was the list of vulnerabilities early in 2001, however the first two categories of the vulnerabilites are still in existince and proves threatful to the web application hosting platform. LibStranger tool is developed with a view to sliminate these kind of vulnerabilities existing in the web application development. The LibStranger implemented in C provided a rich set of functionalities for functioning with string automaton. The main focus on performing a backward analysis can be demonstrated with the help of the implementation available in these library. Complex sanitization functions available in the library aids in a concrete realization of the expected concept. The functions that forms the bridge for our analysis is discussed in the sections 4-5. Section 2-3 generalizes the specialities of LibStranger tool and focuses on the utility of that over our need, It also includes utilizing JNI (Java Native Interface) and SWIG (Smplified Wrapper Interface Generator). The main Implemetation of this existing module invloves identification of the appropriate functions for interfacing. The end result is interfacing of the approximated functions to the scala code, by using the interfacing tool. The final implementation generated will be effective to perform the backward analysis of a javascript code to verify its vulnerability. This can make the server end service provider be prepared of the situation and reject the vulnerable requests to avoid code injection \cite{Shahriar_2011}.

\section{Tools and Implementation Overview}
The library has function implementation for generating a DFA to accept strings, these strings are defined in the function specification as a parameter. There are functions for generating an automata from another automata. Functions to describe automata transformations and many more. The base definition and data-structure for the constructing the DFA is derived from MONA library.The Mona Library provides the data-structures for the DFA construction and primary modeling with DFA based operations. The MONA library is linked along with the stranger library during the execution of the code. The linking process will bring together both the tool libraries and operational specifics of both MONA and LibStranger to work in-line with each other. This linking pose a challenge during our interfacing step, which will require us to write java wrapper classes for every function involving in the working of the code (when JNI is used). Luckily, this can be eliminated using the SWIG. The future work of this implementation will describe the details of the interfacing of the LibStrnager tool with the scala code.
\subsection{LibStranger}
The \textit{stranger.h} file in LibStranger library provides the list of all the functions available at our disposal. The letters are represented in a 8-bit ascii format with 1-bit reserved for replacement. The basic string operations can be performed by constructing DFA. There are specific functions that are required for the complete implementation of the scala code which will be discussed in the following sections. These functions can be utilized for performing a backward analysis of the javascript under consideration. an example scenario for the backward analysis would be considering a <script>
\subsection{Functions under consideration}
\subsubsection{CharAt():}
Returns the character at the "n" position within the string.
\\
\verb|//charAt(x)|
\\
\verb|var myString = 'jQuery FTW!!!';|
\\
\verb|console.log(myString.charAt(7));|
\\
\verb|//output: F|
\\
This has no precise module  in the LibStranger application, however necessary study is undertaken to find an equivalent functionality available. While dealing with the DFA and automata which generalizes the concept of the having a regular expression for the construction, it is difficult to extract a particularly specific value of a generalized solution.
\subsubsection{CharCodeAt():}
Returns the Unicode value of the character at position "n" within the string.
\\
\verb|//charAt(position)|
\\
\verb|var message="jquery4u"|
\\
\verb|//alerts "q"|
\\
\verb|alert(message.charAt(1))|
\\
This again expects us to provide a specific extraction of a regular expression operating on an automata. Study reveals that this kind of operation is considered ineffective when we have a generalized domain to operate with . However, this kind of function is necessary in analysing a java script code as this forms an elemental component of the need.
\subsubsection{Concat():}
Combines one or more strings (arguments v1, v2 etc) into the existing one and returns the combined string. Original string is not modified.
\\
\verb|//concat(v1, v2,..)|
\\
\verb|var message="Sam"|
\\
\verb|var final=message.concat(" is a"," hopeless romantic.")|
\\
\verb|//alerts "Sam is a hopeless romantic."|
\\
\verb|alert(final)|
\\
 The solution offered by the LibStranger tool for the concatenation is \verb| dfa_concat|.This returns a DFA that will accept the concatenated value of the provided DFA, the arguments for this function are 2 DFA's the var, which denotes the number of bits we use to represent our ASCII format, that we are making use of an UTF-8 format.
 \\
 \verb| DFA *dfa_concat(DFA *M1, DFA *M2, int var, int *indices);|
\subsubsection{FromCharCode():}
Returns a string created by using the specified sequence of Unicode values (arguments n1, n2 etc). Method of String object, not String instance. For example: String.fromCharCode().
\\
\verb|//fromCharCode(c1, c2,...)|
\\
\verb|console.log(String.fromCharCode(97,99,98,120,121,122))|
\\
\verb|//output: abcxyz|
\\
\verb|console.log(String.fromCharCode(72,69,76,76,79))|
\\
\verb|//output: HELLO|
\\
This again expects us to provide a specific extraction of a regular expression operating on an automata. Study reveals that this kind of operation is considered ineffective when we have a generalized domain to operate with . However, this kind of function is necessary in analysing a java script code as this forms an elemental component of the need.

\subsubsection{Indexof():}
Searches and (if found) returns the index number of the searched character or substring within the string. If not found, -1 is returned. "Start" is an optional argument specifying the position within string to begin the search. Default is 0.
\\
\verb|//indexOf(char/substring)|
\\
\verb|var sentence="Hi, my name is Sam!"|
\\
\verb|if (sentence.indexOf("Sam")!=-1)|
\\
\verb|alert("Sam is in there!")|
\\
This again expects us to provide a specific extraction of a regular expression operating on an automata. Study reveals that this kind of operation is considered ineffective when we have a generalized domain to operate with . However, this kind of function is necessary in analysing a java script code as this forms an elemental component of the need.

\subsubsection{LastIndexof():}
Searches and (if found) returns the index number of the searched character or substring within the string. Searches the string from end to beginning. If not found, -1 is returned. "Start" is an optional argument specifying the position within string to begin the search. Default is string.length-1.
\\
\verb|//lastIndexOf(substr, [start])|
\\
\verb|var myString = 'javascript rox';|
\\
\verb|console.log(myString.lastIndexOf('r'));|
\\
\verb|//output: 11|
\\
This again expects us to provide a specific extraction of a regular expression operating on an automata. Study reveals that this kind of operation is considered ineffective when we have a generalized domain to operate with . However, this kind of function is necessary in analysing a java script code as this forms an elemental component of the need.

\subsubsection{Match():}
Executes a search for a match within a string based on a regular expression. It returns an array of information or null if no match is found.
\\
\verb|//match(regexp) //select integers only|
\\
\verb|var intRegex = /[0-9 -()+]+$/;  |
\\
\verb|var myNumber = '999';|
\\
\verb|var myInt = myNumber.match(intRegex);|
\\
\verb|console.log(isInt);|
\\
\verb|//output: 999|
\\
\verb|var myString = '999 JS Coders';|
\\
\verb|var myInt = myString.match(intRegex);|
\\
\verb|console.log(isInt);|
\\
\verb|//output: null|
\\
The solution offered by the LibStranger tool is \verb| checkMembership|. This function performs the way we expect it in matching the components of the code with the essential part of the DFA. The input argument of the code is the DFA in which the match is to be made and the string to be matched for it's containment, the last two arguments are 8 and the indices parameter.
\\
\verb|  int checkMembership(DFA* M, char* string, int var, int* indices);|
\subsubsection{Replace():}
Searches and replaces the regular expression (or sub string) portion (match) with the replaced text instead.
\\
\verb|//replace(substr, replacetext)|
\\
\verb|var myString = '999 JavaScript Coders';|
\\
\verb|console.log(myString.replace(/JavaScript/i, "jQuery"));|
\\
\verb|//output: 999 jQuery Coders|
\\
\verb|//replace(regexp, replacetext)|
\\
\verb|var myString = '999 JavaScript Coders';|
\\
\verb|console.log(myString.replace(new RegExp( "999", "gi" ), "The"));|
\\
\verb|//output: The JavaScript Coders|
\\
The solution offered by the LibStranger tool is \verb| dfa_replace_char_with_string|. This function performs the way we expect with the components and the essential part of the DFA. The input argument of the code is the DFA in which the match is to be made and the string to be matched for it's containment, the last two arguments are 8 and the indices parameter.
\\
\verb|  DFA *dfa_replace_char_with_string(DFA *M, int var, int *oldIndices, char replacedChar, char *string);|

\subsubsection{Search():}
Tests for a match in a string. It returns the index of the match, or -1 if not found.
\\
\verb|//replace(substr, replacetext)|
\\
\verb|var myString = '999 JavaScript Coders';|
\\
\verb|console.log(myString.replace(/JavaScript/i, "jQuery"));|
\\
\verb|//output: 999 jQuery Coders|
\\
\verb|//replace(regexp, replacetext)|
\\
\verb|var myString = '999 JavaScript Coders';|
\\
\verb|console.log(myString.replace(new RegExp( "999", "gi" ), "The"));|
\\
\verb|//output: The JavaScript Coders|
\\
The solution offered by the LibStranger tool is \verb| checkMembership|. This function performs the way we expect it in matching the components of the code with the essential part of the DFA. The input argument of the code is the DFA in which the match is to be made and the string to be matched for it's containment, the last two arguments are 8 and the indices parameter.
\\
\verb|  int checkMembership(DFA* M, char* string, int var, int* indices);|
\subsubsection{Slice():}
Returns a substring of the string based on the "start" and "end" index arguments, NOT including the "end" index itself. "End" is optional, and if none is specified, the slice includes all characters from "start" to end of string.
\\
\verb|//slice(start, end)|
\\
\verb|var text="excellent"|
\\
\verb|text.slice(0,4) //returns "exce"|
\\
\verb|text.slice(2,4) //returns "ce"|
\\
There is no specific solution, however we can use normal C string operations do the necessary functionality and then to construct DFA's with the processed values. This will be of help in an adverse situation when we want to generalise the solution.
\subsubsection{Split():}
Splits a string into many according to the specified delimiter, and returns an array containing each element. The optional "limit" is an integer that lets you specify the maximum number of elements to return.
\\
\verb|//split(delimiter)|
\\
\verb|var message="Welcome to jQuery4u"|
\\
\verb|//word[0] contains "We"|
\\
\verb|//word[1] contains "lcome to jQuery4u"|
\\
\verb|var word=message.split("l")|
\\
There is no specific solution, however we can use normal C string operations do the necessary functionality and then to construct DFA's with the processed values. This will be of help in an adverse situation when we want to generalise the solution.
\subsubsection{SubString():}
Returns the characters in a string beginning at "start" and through the specified number of characters, "length". "Length" is optional, and if omitted, up to the end of the string is assumed.
\\
\verb|//substring(from, [to])|
\\
\verb|var myString = 'javascript rox';|
\\
\verb|myString = myString.substring(0,10);|
\\
\verb|console.log(myString)|
\\
\verb|//output: javascript|

Returns the characters in a string between "from" and "to" indexes, NOT including "to" inself. "To" is optional, and if omitted, up to the end of the string is assumed.
\\
\verb|//substring(from, to)|
\\
\verb|var text="excellent"|
\\
\verb|text.substring(0,4) //returns "exce"|
\\
\verb|text.substring(2,4) //returns "ce"|
\\
There is no specific solution, however we can use normal C string operations do the necessary functionality and then to construct DFA's with the processed values. This will be of help in an adverse situation when we want to generalise the solution.
\subsubsection{Tolowercase():}
Returns the string with all of its characters converted to lowercase.
\\
\verb|//toLowerCase()|
\\
\verb|var myString = 'JAVASCRIPT ROX';|
\\
\verb|myString = myString.toLowerCase();|
\\
\verb|console.log(myString)|
\\
\verb|//output: javascript rox|
\\
The solution offered by the LibStranger tool is \verb| dfaToLowerCase|. This function performs the way we expect it in matching the components of the code with the essential part of the DFA. The input argument of the code is the DFA in which the match is to be made and the string to be matched for it's containment, the last two arguments are 8 and the indices parameter.
\\
\verb|  DFA* dfaToLowerCase(DFA* M, int var, int* indices);|

\subsubsection{Touppercase():}
Returns the string with all of its characters converted to uppercase.
\\
\verb|//toUpperCase()|
\\
\verb|var myString = 'javascript rox';|
\\
\verb|myString = myString.toUpperCase();|
\\
\verb|console.log(myString)|
\\
\verb|//output: JAVASCRIPT ROX|
\\
The solution offered by the LibStranger tool is \verb| dfaToUpperCase|. This function performs the way we expect it in matching the components of the code with the essential part of the DFA. The input argument of the code is the DFA in which the match is to be made and the string to be matched for it's containment, the last two arguments are 8 and the indices parameter.
\\
\verb|  DFA* dfaToUpperCase(DFA* M, int var, int* indices);|

\section{Fundamental Concept}
The fundamental concept behind the functioning of the entire system is based on the evaluation of the existing field entries in an application. The error pattern is recoginzed and the application entries are combined wit the error patterns. This is then evaluated for the intersection of the error pattern , if the intersection is evaluated to true then the proper steps are taken for sanitization of the operation. Sanitization can be done in 2 possible ways one is by match and block and the other one is by match and sanitize. The first category of match and block takes place for the most vulnerable category of input fields where the threat can be maximum intense. This way of sanitization will negotiate the application to cease it's function  when the particular category of input vulnerability is spotted. Te other kind of sanitization takes place when the attack pattern involved is responsible for a lower impact pattern and the avoidance can be done by merely removing the occuring attack pattern from the field involved. This occurence of the attack pattern is usually reported for the learning module which can enrich the data set by adding new pattern to the existing attack patters it has.  

\section{Conclusion}
This work is continued to deliver fruitful result in making use of the automata structure to provide the best possible use of the system to configure the scala code to perform at it's best in analsing the javascript application code.The SWIG which is the simple wrapper class Interface Generator is the one that will be used in the step to follow to complete the integration of the existing tool with that of the scala code which is more of the interfacing task.


















\documentclass[12pt,letterpaper]{article}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}

\newtheorem{clm}{Claim}

\author{Linyun Fu}
\title{CSCI 4020 Computer Algorithms Spring 2011\\
Problem Set 5}
\begin{document}
\maketitle
\section*{Chapter 7, Problem 7}
Consider a set of mobile computing clients in a certain town who each
need to be connected to one of several possible \emph{base stations}. We'll
suppose there are $n$ clients, with the position of each client specified
by its $(x, y)$ coordinates in the plane. There are also $k$ base stations; the
position of each of these is specified by $(x, y)$ coordinates as well.

For each client, we wish to connect it to exactly one of the base
stations. Our choice of connections is constrained in the following ways.
There is a range parameter $r$ -- a client can only be connected to a base
station that is within distance $r$. There is also a \emph{load parameter} $L$ -- no
more than $L$ clients can be connected to any single base station.

Your goal is to design a polynomial-time algorithm for the following
problem. Given the positions of a set of clients and a set of base stations,
as well as the range and load parameters, decide whether every client can
be connected simultaneously to a base station, subject to the range and
load conditions in the previous paragraph.

\section*{Answer}
We denote the $n$ client nodes with $c_1, c_2, \dots, c_n$ and the $k$ base stations with $b_1, b_2, \dots, b_k$. We convert the problem into a maximum-flow problem in the following way.
\begin{itemize}
\item Add a source node $s$ and add an edge from it to each client node with capacity 1;
\item For each pair $(c_i, b_j)$, if the distance between $c_i$ and $b_j$ is within $r$, then add an edge from $c_i$ to $b_j$ with capacity 1;
\item Add a sink node $t$ and add an edge from each base station node to it with capacity $L$.
\end{itemize}

Then we find the maximum flow in this flow network. If the the size of the maximum flow is $n$, then it is possible to connect every client to a base station at the same time; otherwise it is impossible to achieve the goal. Figure~1 illustrates the above conversion scheme.\selectlanguage{english}
\begin{figure}
\begin{center}
\includegraphics[width=0.7\textwidth]{7.7.eps}
\caption{{Reducing the problem to a maximum-flow problem}}
\end{center}
\end{figure}

Next we prove that each solution to the problem corresponds to a maximum flow of size $n$ in the flow network and vice versa.

\begin{itemize}
\item Given a solution to the original problem, we know that each $c_i$ is connected to exactly one $b_j$, and each $b_j$ is connected from at most $L$ $c_i$'s. In the flow network, we let the edge from $c_i$ to $b_j$ carry flow of size 1 if $b_j$ is $c_i$'s base station, we also let the edge from $s$ to each $c_i$ carry flow of size 1 to meet conservation conditions. For the same reason, we let each edge from $b_j$ to $t$ carry flow of size $f^{\textrm{in}}b_j\le L$. Therefore we have a maximum flow of size $n$ since every edge going out from $s$ is saturated.
\item Given a maximum flow of size $n$ in the flow network, we know that each edge out from $s$ must be saturated, and each edge in to $t$ must carry a flow no more than $L$, so $f^{\textrm{in}}c_i=1$ for each $c_i$ and $f^{\textrm{out}}b_j\le L$ for each $b_j$, thus $f^{\textrm{out}}c_i=f^{\textrm{in}}c_i=1$ for each $c_i$, and $f^{\textrm{in}}b_j = f^{\textrm{out}}b_j\le L$ for each $b_j$, which means all the edges between $\{c_1, c_2, \dots, c_n\}$ and $\{b_1, b_2, \dots, b_k\}$ carrying flow of size 1 make a valid solution to the original problem.
\end{itemize}

The conversion is composed of adding nodes $s$ and $t$, connecting $s$ with $n$ nodes and $t$ with $k$ nodes, and assigning capacity values to all the edges in the flow network, which can be completed in polynomial time; the maximum-flow problem can also be solved in polynomial time. Therefore, the time complexity of the algorithm is polynomial.

\section*{Chapter 7, Problem 34}
\emph{Ad hoc networks}, made up of low-powered wireless devices, have been
proposed for situations like natural disasters in which the coordinators
of a rescue effort might want to monitor conditions in a hard-to-reach
area. The idea is that a large collection of these wireless devices could be
dropped into such an area from an airplane and then configured into a
functioning network.

Note that we're talking about (a) relatively inexpensive devices that
are (b) being dropped from an airplane into (c) dangerous territory; and
for the combination of reasons (a), (b), and (c), it becomes necessary to
include provisions for dealing with the failure of a reasonable number of
the nodes.

We'd like it to be the case that if one of the devices $v$ detects that it is in
danger of failing, it should transmit a representation of its current state to
some other device in the network. Each device has a limited transmitting
range -- say it can communicate with other devices that lie within $d$ meters
of it. Moreover, since we don't want it to try transmitting its state to a
device that has already failed, we should include some redundancy: A
device $v$ should have a set of $k$ other devices that it can potentially contact,
each within $d$ meters of it. We'll call this a \emph{back-up set} for device $v$.

\begin{itemize}
\item[(a)] Suppose you're given a set of $n$ wireless devices, with positions
represented by an $(x, y)$ coordinate pair for each. Design an algorithm
that determines whether it is possible to choose a back-up set for
each device (i.e., $k$ other devices, each within $d$ meters), with the
further property that, for some parameter $b$, no device appears in
the back-up set of more than $b$ other devices. The algorithm should
output the back-up sets themselves, provided they can be found.

\item[(b)] The idea that, for each pair of devices $v$ and $w$, there's a strict
dichotomy between being ``in range'' or ``out of range'' is a simplified
abstraction. More accurately, there's a power decay function $f(\cdot)$ that
specifies, for a pair of devices at distance $\delta$, the signal strength $f(\delta)$
that they'll be able to achieve on their wireless connection. (We'll
assume that $f(\delta)$ decreases with increasing $\delta$.)

We might want to build this into our notion of back-up sets as
follows: among the $k$ devices in the back-up set of $v$, there should
be at least one that can be reached with very high signal strength,
at least one other that can be reached with moderately high signal
strength, and so forth. More concretely, we have values $p_1 \ge p_2 \ge\cdots \ge
p_k$, so that if the back-up set for $v$ consists of devices at distances
$d_1 \le d_2 \le \cdots\le d_k$, then we should have $f(d_j) \ge p_j$ for each $j$.

Give an algorithm that determines whether it is possible to
choose a back-up set for each device subject to this more detailed
condition, still requiring that no device should appear in the back-up
set of more than $b$ other devices. Again, the algorithm should output
the back-up sets themselves, provided they can be found.
\end{itemize}

\section*{Answer}

\subsection*{Problem (a)}
We convert the original problem into a maximum-flow problem in the following way.
\begin{itemize}
\item For each wireless device, create two nodes, namely $v_i$ and $v_i'$ ($i=1, 2, \dots, n$);
\item Create the source node $s$ and the sink node $t$;
\item For each node $v_i$, create an edge from $s$ to $v_i$ with capacity $k$;
\item For every pair $(v_i, v_j')$ such that $i \ne j$, if the distance between device $i$ and $j$ is within $d$, then create an edge from $v_i$ to $v_j'$ with capacity 1;
\item For each node $v_j'$, create an edge from $v_j'$ to $t$ with capacity $b$.
\end{itemize}

Then we find the maximum flow in the this flow network. If the size of the maximum flow is not $nk$, then we know that the required back-up sets do not exist; otherwise the edges between $\{v_1, v_2, \dots, v_n\}$ and $\{v_1', v_2', \dots, v_n'\}$ that carry flow of size 1 make a valid solution to the original problem, i.e., if edge $(v_i, v_j')$ carries flow of size 1, then device $j$ is in device $i$'s back-up set. Figure~2 illustrates the above conversion.\selectlanguage{english}
\begin{figure}
\begin{center}
\includegraphics[width=0.7\textwidth]{7.34a.eps}
\caption{{Reducing problem (a) to maximum-flow problem}}
\end{center}
\end{figure}

Next we prove that each solution to the problem corresponds to a maximum flow of size $nk$ in the flow network and vice versa.
\begin{itemize}
\item Given a solution to the original problem, we know that each device finds $k$ other devices within a distance of $d$, and no device is in the back-up sets of more than $b$ other devices. In the flow network, we let the edge from $v_i$ to $v_j'$ carry flow of size 1 if device $i$ finds $j$ as one of its back-up devices. We then let the edge from $s$ to each $v_i$ carry flow of size $k$ to meet conservation conditions, because $f^{\textrm{out}}v_i = k$ for each $i$. For the same reason, we let the edge from $v_j'$ to $t$ carry flow of size $f^{\textrm{in}}v_j'$ for each $j$. Since no device is in the back-up sets of more than $b$ other devices, no edge from $v_j'$ to $t$ carry flow of size more than $b$. Therefore, it is a maximum flow of size $nk$ in the flow network since every edge going out from $s$ is saturated.
\item Given a maximum flow of size $nk$ in the flow network, we let device $j$ in $i$'s back-up set if the edge from $v_i$ to $v_j'$ carries flow of size 1. We know that every edge out from $s$ must be saturated, so $f^{\textrm{in}}v_i=k$ for each $i$, therefore $f^{\textrm{out}}v_i=f^{\textrm{in}}v_i=k$ for each $i$,  which means each device finds its $k$ back-up devices,  and the fact that $f^{\textrm{out}}v_j'\le b$ for each $j$ yields that $f^{\textrm{in}}v_j'=f^{\textrm{out}}v_j'\le b$ for each $j$, which means no device appears in the back-up sets of more than $b$ other devices. 
\end{itemize}

The conversion consists of creating $2n+2$ nodes and $O(n^2)$ edges with designated capacities, which can be computed in polynomial time. Since the maximum-flow problem is solvable in polynomial time, the overall time complexity is polynomial.

\subsection*{Problem (b)}
For the sake of simplicity, we made the following definition about \emph{level-$l$ back-up devices}. i.e., if device $j$ is a back-up device for device $i$ and the distance between $i$ and $j$, which is $\delta$, satisfies $p_l\le f(\delta)< p_{l-1}$ ($p_0=+\infty$), then we say $j$ is a \emph{level-$l$ back-up} of $i$. The highest level is level 1 since it has the most strict constraint on distance. The original problem is equivalent to the following problem.
\begin{quote}
Determine whether each device can find at least one level-1 back-up, at least two back-ups of level 2 or above, $\dots$, and at least $k-1$ back-ups of level-$(k-1)$ or above, and totally $k$ back-ups of level-$k$ or above; no device is allowed in the back-up sets of more than $b$ other devices.
\end{quote}

We convert the original problem into a maximum-flow problem in the following way.
\begin{itemize}
\item For each wireless device $i$, create $3k+1$ nodes, namely $u_{il}$, $v_{il}$ and $v_{il}'$  for $l = 1, 2, \dots, k$, and $v_i'$. We use $S_l$ to denote the subgraph containing all the nodes $v_{il}$ and $v_{il}'$ ($i = 1, 2, \dots, n$) hereafter;
\item Create the source node $s$ and the sink node $t$;
\item For each node $u_{i1}$, create an edge from $s$ to $u_{i1}$ with capacity $k$;
\item For each node $u_{il}$, create an edge from $u_{il}$ to $v_{il}$ with capacity $k+1-l$, i.e., $u_{i1}$ to $v_{i1}$ with capacity $k$, $u_{i2}$ to $v_{i2}$ with capacity $k-1$, $\dots$, $u_{ik}$ to $v_{ik}$ with capacity $1$;
\item Create an edge from $u_{il}$ to $u_{i(l+1)}$ with capacity $k-l$ for each $l$ from 1 to $k-1$, i.e., $u_{i1}$ to $u_{i2}$ with capacity $k-1$, $u_{i2}$ to $u_{i3}$ with capacity $k-2$, $\dots$, $u_{i(k-1)}$ to $u_{ik}$ with capacity $1$;
\item For each pair $(v_{i1}, v_{j1}')$ such that $i\ne j$ in $S_1$, if the distance between $v_{i1}$ and $v_{j1}'$, $\delta$, satisfies $f(\delta)\ge p_1$, then create an edge from $v_{i1}$ to $v_{j1}'$ with capacity 1;
\item For each subgraph $S_l$ in $\{S_2, S_3, \dots, S_k\}$, create edges between $v_{il}$'s and $v_{jl}'$'s satisfying $p_l\le f(\delta)<p_{l-1}$ with capacity 1, where $\delta$ is the distance between some pair $(v_{il}, v_{jl}')$;
\item For each node $v_{jl}'$, create an edge from $v_{jl}'$ to $v_j'$ with capacity $n$ (or infinity);
\item For each node $v_j'$, create an edge from $v_j'$ to $t$ with capacity $b$.
\end{itemize}

Then we find the maximum flow in the this flow network. If the size of the maximum flow is not $nk$, then we know that the required back-up sets do not exist; otherwise the edges in $S_1, S_2, \dots, S_k$ that carry flow of size 1 make a valid solution to the original problem, i.e., edges in $S_l$ indicate each device's level-$l$ back-up device(s). Figure~3 illustrates the above conversion.\selectlanguage{english}
\begin{figure}
\begin{center}
\includegraphics[width=\textwidth]{7.34b.eps}
\caption{{Reducing problem (b) to maximum-flow problem}}
\end{center}
\end{figure}

Next we prove that each solution to the problem corresponds to a maximum flow of size $nk$ in the flow network and vice versa.

\begin{itemize}
\item Given a solution to the original problem, we know that each device finds 
\begin{itemize}
\item at least one level-1 back-up, 
\item at least two back-ups of level 2 or above, 

$\dots$, 

\item at least $k-1$ back-ups of level $k-1$ or above, and 
\item totally $k$ back-ups of level $k$ or above, 
\end{itemize}
and no device is in the back-up sets of more than $b$ other devices. We let the edge from $v_{il}$ to $v_{jl}'$ (in subgraph $S_l$) carry flow of size 1 if device $j$ is one of device $i$'s level-$l$ back-ups. So for each $i=1,2,\dots,n$, we have
\begin{align}
\nonumber f^{\textrm{out}}v_{i1} & \ge 1\\\nonumber
f^{\textrm{out}}v_{i1}+f^{\textrm{out}}v_{i2} & \ge 2\\\nonumber
\dots & \dots \dots \\\nonumber
f^{\textrm{out}}v_{i1}+f^{\textrm{out}}v_{i2}+\dots+f^{\textrm{out}}v_{i(k-1)} & \ge k-1\\\nonumber
f^{\textrm{out}}v_{i1}+f^{\textrm{out}}v_{i2}+\dots+f^{\textrm{out}}v_{ik} & = k
\end{align}
therefore 
\begin{align}
\nonumber f^{\textrm{out}}v_{ik} & \le 1\\\nonumber
f^{\textrm{out}}v_{i(k-1)} + f^{\textrm{out}}v_{i(k)}& \le 2\\\nonumber
\dots & \dots \dots\\\nonumber
f^{\textrm{out}}v_{i2} + f^{\textrm{out}}v_{i3} + \dots + f^{\textrm{out}}v_{i(k)} & \le k-1\\\nonumber
f^{\textrm{out}}v_{i1}+f^{\textrm{out}}v_{i2}+\dots+f^{\textrm{out}}v_{ik} & = k
\end{align}
Therefore we can let each edge from $u_{il}$ to $v_{il}$ carry flow of size $f^{\textrm{out}}v_{il}$ and each edge from $u_{il}$ to $u_{i(l+1)}$ carry flow of size $f^{\textrm{out}}u_{i(l+1)}$ to meet conservation conditions while still meeting capacity conditions, and we have $f^{\textrm{out}}u_{ik} = k$ for all $i$. Then we let the edge from $s$ to each $u_{ik}$ carry flow of size $k$ to meet conservation conditions. We also let the edge from $v_{jl}'$ to $v_j'$ carry flow of size $f^{\textrm{in}}v_{jl}'$ for the same reason. Since no device is in the back-up sets of more than $b$ other devices, we have $f^{\textrm{in}}v_{j}' \le b$ for all $j$, so we can let each edge from  $v_j'$ to $t$ carry flow of size $f^{\textrm{in}}v_{j}'$ to meet conservation conditions while still meeting capacity conditions. Now we have a flow saturating all the edges out from $s$, which is a maximum flow of size $nk$.
\item Given a maximum flow of size $nk$ in the flow network, we let device $j$ in device $i$'s back-up set if the edge from $v_{il}$ to $v_{jl}'$ carries flow of size 1 for some $l$. Now we prove this is a valid solution. We know that every edge out from $s$ must be saturated, so $f^{\textrm{in}}u_{il}=k$ for each $i$, therefore $f^{\textrm{out}}u_{il}=k$ for each $i$, so 
\begin{align*}
f^{\textrm{in}}v_{i1}+f^{\textrm{in}}v_{i2}+\dots+f^{\textrm{in}}v_{ik} = k
\end{align*} 
for each $i$, so 
\begin{align*}
f^{\textrm{out}}v_{i1}+f^{\textrm{out}}v_{i2}+\dots+f^{\textrm{out}}v_{ik} = k
\end{align*} 
which means every device finds its $k$ back-up devices. Since 
\begin{align*}
f^{\textrm{out}}v_{i(k-l+1)} + f^{\textrm{out}}v_{i(k-l+2)} + \dots + f^{\textrm{out}}v_{i(k-1)} + f^{\textrm{out}}v_{ik} \le l
\end{align*}
for each $l$, there are at least $k-l$ back-up devices of level $k-l$ or above. On the other hand, since $f^{\textrm{in}}v_j'=f^{\textrm{out}}v_j'\le b$ for each $j$, and $f^{\textrm{in}}v_j'$ is the total number of times that device $j$ acts as some other device's back-up, this means no device appears in the back-up sets of more than $b$ other devices. 
\end{itemize}

The conversion consists of creating $3kn+n+2$ nodes and $O(kn^2)$ edges with designated capacities, which can be computed in polynomial time. Since the maximum-flow problem is solvable in polynomial time, the overall time complexity is polynomial.

\end{document}

\selectlanguage{english}
\FloatBarrier
\bibliographystyle{plain}
\bibliography{bibliography/converted_to_latex.bib%
}

\end{document}

