69 lines
6.3 KiB
TeX
69 lines
6.3 KiB
TeX
% !TEX encoding = UTF-8
|
|
% !TEX spellcheck = en_GB
|
|
% !TEX root = ../paper.tex
|
|
\chapter{Related work}
|
|
\label{cha:state-art}
|
|
|
|
Program slicing was proposed \cite{Wei81} and iteratively improved until the proposal of the currently most used program representation structure, the SDG. Specifically, in the context of exceptions, multiple approaches have been attempted with varying degrees of success.
|
|
In the realm of academia, there exists no definite solution. One of the most relevant initial proposals was Allen and Horwitz (\cite{AllH03}), although it was not the first one targeting the Java programming language specifically (\cite{SinH98,SinHR99}).
|
|
|
|
In \cite{AllH03}, Allen et al. benefit from the existing proposals for \textit{return}, \textit{goto} and other unconditional jumps \cite{HorwitzRB88} to model the behaviour of \textit{throw} statements. Control flow inside \textit{try-catch-finally} statements was simulated, both for explicit \textit{throw} and all possible \textit{throws} nested inside a method call. In that work, unchecked exceptions were considered but regarded as ``worthless'' to include, due to the increase in size of the slices, which reduces their effectiveness. The reason for this decision, was the number of unchecked exceptions embedded in normal Java instructions, such as \texttt{NullException} in any instance field or method, \texttt{IndexOutOfBoundsException} in array accesses and countless others, which would entail an exhaustive analysis of the code looking for every potential instruction that may arise all kinds of unchecked exceptions. On top of that, handling \textit{unchecked} exceptions opens the problem of calling an API to which there is no analysable source code, either because the module was compiled before-hand or because it is part of a distributed system.
|
|
|
|
Chang et al. \cite{JoC04} present an alternative to the CFG by computing exception-induced control flow separately from the traditional control flow computation, but go no further into the ramifications it entails for the PDG and the SDG.
|
|
|
|
Jiang et al. \cite{JiaZSJ06} describe a solution specific for the exception system in C++, which differs from Java's implementation of exceptions. They reuse the idea of non-executable edges in \textit{throw} nodes, and introduce handling \textit{catch} nodes as a switch, each trying to catch the exception before deferring onto the next \textit{catch} or propagating it to the calling method. Their proposal is centred around the IECFG (Improved Exception Control-Flow Graph), which propagates control dependencies onto the PDG and then the SDG. Finally, in their SDG, each normal and exceptional return and their data output are connected to all \textit{catch} statements where the data may have arrived, which is fine for the example they propose, but could be inefficient if the method has many call nodes.
|
|
Prabhu et al. \cite{PraMB11} have worked specifically on the C++ exception framework, but without producing any notable improvement to the field that could be applicable to Java.
|
|
|
|
Finally, Jie et al. \cite{JieS11} introduced an Object-Oriented System Dependence Graph with exception handling (EOSDG), which represented a generic object-oriented language, with exception handling capabilities. Its broadness allows for the EOSDG to fit into both Java and C++. It uses concepts from Jiang \cite{JiaZSJ06}, such as cascading \textit{catch} statements, while adding explicit support for virtual calls, polymorphism and inheritance. Despite its reach, it does not solve the original underlying problems displayed in Allen's approach \cite{AllH03}, which is why our thesis is centred around Allen's contribution.
|
|
|
|
% \hrulefill
|
|
% \marginnote{Alternative explanation of \cite{AllH03}, with counter example. Maybe should move the counter example backwards.}
|
|
|
|
% In her\josep{their?} paper \added{\cite{pending}}, Horwitz \josep{et al.?} suggests treating exceptions in the following way:
|
|
% \begin{itemize}
|
|
% \item Statements are divided into statements, predicates (loops and conditional blocks) and pseudo-predicates (return and throw statements). Statements only have one successor in the CFG, predicates have two (one when the condition is true and another when false), pseudo-predicates have two, but the one labeled ``false'' is non-executable. The non-executable edge connects to the statement that would be executed if the unconditional jump was replaced by a ``nop''.
|
|
% \item \textit{try-catch-finally} blocks are treated differently, but it has fewer dependencies than needed. Each catch block is control-dependent on any statement that may throw the corresponding exception. The \josep{???}
|
|
% \end{itemize}
|
|
|
|
% \josep{Crea un entorno example}
|
|
% \begin{lstlisting}[title=Example]
|
|
% void main() {
|
|
% int x = 0;
|
|
% while (true) {
|
|
% try {
|
|
% f(x);
|
|
% } catch (ExceptionA e) {
|
|
% x--;
|
|
% } catch (ExceptionB e) {
|
|
% System.err.println(x);
|
|
% } catch (ExceptionC e) {
|
|
% System.out.println(x);
|
|
% }
|
|
% System.out.println(x);
|
|
% }
|
|
% }
|
|
|
|
% void f(x) {
|
|
% x--;
|
|
% if (x > 10)
|
|
% throw new ExceptionA();
|
|
% else if (x == 0)
|
|
% throw new ExceptionB();
|
|
% else if (x > 0)
|
|
% throw new ExceptionC();
|
|
% x++;
|
|
% System.out.println(x);
|
|
% }
|
|
|
|
% static class ExceptionA extends ExceptionC {}
|
|
% static class ExceptionB extends Exception {}
|
|
% static class ExceptionC extends Exception {}
|
|
% \end{lstlisting}
|
|
|
|
% In this example we can explore all the errors found with the current state of the art. \josep{Seria mucho más claro si tenemos un grafo con la soluciones propuesta para cada problema.}
|
|
|
|
% The first problem found is the lack of \texttt{catch} statements in the slice, as no edge is drawn from the catch. Some of the catch blocks will be included via data dependencies, but some may not be reached, though they are still necessary if the slice includes anything after a caught exception.
|
|
% Therefore, an extra control dependence must be introduced, in order to always include a ``catch'' statement in the slice if the ``throw'' statement is in the slice. In the example, only the catch statement from line 20 will be included \josep{con que criterio? no has definido el ejemplo. El lector no sabe como interpretar esta figura}, and if ExceptionC or ExceptionB were thrown, they would not be caught. That would not be a problem if the function $f$ was not executed again, but it is, making the slice incorrect.
|
|
|
|
% vim: set noexpandtab:ts=2:sw=2:wrap
|