\documentclass{sigplanconf}

\usepackage{amsmath}
\usepackage{graphicx}


\begin{document}

\special{papersize=8.5in,11in}
\setlength{\pdfpageheight}{\paperheight}
\setlength{\pdfpagewidth}{\paperwidth}

\conferenceinfo{CONF 'yy}{Month d--d, 20yy, City, ST, Country} 
\copyrightyear{20yy} 
\copyrightdata{978-1-nnnn-nnnn-n/yy/mm} 
\doi{nnnnnnn.nnnnnnn}

\title{Liquid Version Climber: an automated tool for upgrading complex software systems}
%\subtitle{Subtitle Text, if any}

\authorinfo{Christophe Pradal}
           {UMR AGAP, CIRAD and Inria, Montpellier, France}
           {christophe.pradal@cirad.fr}
\authorinfo{Sarah Cohen-Boulakia}
           {Inria, Montpellier, LRI CNRS 8623, U.Paris Sud, France} 
					 {cohen@lri.fr}
\authorinfo{Patrick Valduriez}
           {Inria and LIRMM, Montpellier, France}
           {Patrick.Valduriez@inria.fr}
\authorinfo{Dennis Shasha}
           {Courant Institute, New York University, USA\\Inria and LIRMM, Montpellier, France} 
					 {shasha@cs.nyu.edu}
					
\maketitle

\begin{abstract}
Suppose you are given a software system that is composed of a set of packages each at a particular version. 
You want to update some packages to their most recent versions possible, but you want your software to run after the upgrades, 
thus perhaps entailing changes to the versions of other packages.
One approach is trial and error, but that quickly ends in frustration.
We advocate a provenance-style approach in which tools like {\em ptrace}, {\em reprozip}, {\em pip}, and virtual machines 
combine to enable us to explore 
version combinations of different packages even on a variety of platforms. 
Our approach also
contributes to reproducibility by allowing the replay 
of an experiment from
a given configuration of software and data package-versions 
to work on a new configuration, thus helping to answer the question
of whether a particular result was an artifact of some logic bug
of some particular package-version.
Because the space of versions to explore grows exponentially with the number of packages, we have developed a memoizing algorithm that avoids exponential search while guaranteeing an optimum version combination.
We have ideas for more efficient algorithms under certain assumptions.

\end{abstract}

\section{Introduction}
Software systems are increasingly complex and compositional. This 
is particularly evident in the context 
of free and open source software which may involve very large groups of independently developed packages all evolving at different rates.  End-user scientists use software systems but they have neither the interest nor the technical skill to engage in any of the continuous development practices\cite{duvall07,larman04}  that are currently considered best practices. More likely, they find themselves needing to update some software system (often embedded in a workflow)  whose original developer has left. When they fail, they suffer from what has been called
"workflow analysis decay" \cite{zhao2012workflows} where scientific experiments relying on intertwined packages cannot be executed even only a few months after they have been developed. 

Ideally, such researchers want to create a running systems with certain chosen packages/data updated to recent versions. However, updating one package may entail changes in the versions of other packages. One approach to explore
this package-version space can be trial and error among version combinations, 
but that would be unsustainably time-consuming given the number of combinations to be tested. 
The goal of the \textit{Liquid Version Climber} system is to provide an intelligent automation of this version space exploration. 


The remainder of this paper is organized as follows. 
Section 2 provides a motivating example. 
Section 3 describes the Liquid Climber algorithm.
Section 4 describes the implementation substrate for protected execution
of configurations.
Section 5 shows a case study.
Section 6 places Liquid Climber  within related work. 
Section 7 concludes the paper.


\section{Motivating Example}

Consider a scientist Lucy who has designed a machine learning experiment
on image analysis in a given environment represented by  configuration C
that uses scikit-learn version 0.8, scikit-image version 0.4, SciPy
version V0.10.1, Numpy version 1.4.1, and Python version 2.6.
Scikit-learn and scikit-image depend on SciPy. Both scikit-learn,
scikit-image, and scipy depend on Numpy. All packages depend on
Python.  Configuration C works in that the experiment of Lucy
completes to execution with such versions of the scikit-learn, Numpy and
Python packages. Now, imagine that a new version of scikit-learn appears
(0.14) with new features that Lucy would like to use.
Lucy would thus like to upgrade
scikit-learn version 0.8 to 0.14. However, if scikit-learn is modified
in isolation (\textit{i.e.}, the other packages remain at the same
versions as in configuration C), the
new configuration will not work because scikit-learn 0.10 requires a
newer version of NumPy (  1.6.1 or greater) which in turn depnds on Python 2.7.

Even if release notes (when they are available) provides some dependency information, end-user scientist Lucy does not want to become a goddess of version dependencies. Instead, she'd like some easy-to-use software to figure out which versions to advance to when advancing and then to produce a configuration
she can use.
That's what the \textit{Liquid Version Climber } system aspires to be.

Building such a system entails achieving several capabilities:
\begin{enumerate}
\item To identify  the packages and versions of the original working configuration C. 

\item To combine and link different versions of the packages from C to form a new configuration C' (a new set of package-versions).

\item To execute such a new configuration C' and to detect where it failed if it fails.

\item To use failure information to find the best possible configuration
efficiently.
\end{enumerate}

\section{Algorithm}
In this section, we provide the main definitions underlying our approach
and then present the Liquid Climber algorithm.

\subsection{Definitions}

\paragraph{Queries}
Users express queries describing their desires (which packages to upgrade) and constraints (hereafter called query constraints). Queries are of the form: \textit{maximize versions of the following packages P1, P2, P3, ... Pk in that order (so it is more important for the user to maximize P1 than P2 ...) with the constraint
that Pi should be either version 1 through 3 and Pj should be version 2 through 7}.

\paragraph{Configurations.}
A configuration is a set of package-version pairs.
The initial configuration is given and works.\\ 

\noindent \textbf{Definition:} Two configurations are equal if they have the same versions for every package.\\ 

\noindent \textbf{Definition:} Suppose the packages to maximize
are P1, ... Pk in descending order of priority.
We say that configuration 
C' = P1.v1', P2.v2', ..., Pk.vk', ..., Pn.vn'
is lexicographically greater ($>$) than
C = P1.v1, P2.v2, ...., Pk.vk, ..., Pn.vn

if either P1.v1' $>$ P1.v1
or (P1.v1' = P1.v1 and P2.v2' $>$ P2.v2)
or ...
or (P1.v1' = P1.v1 and P2.v2' = P2.v2 and ... and Pk-1.vk-1' = Pk-1.vk-1
and Pk.vk' $>$ Pk.vk)\\
Notice that lexicographic comparison is indifferent to packages
that need not be maximized.

\noindent \textbf{Definition:} A configuration "works" if it executes to completion.\\ 

\subsection{Assumption}

In this short paper,
we limit ourselves to a single assumption to reduce the need to
do an exhaustive (and therefore exponential) 
search in the space of package-versions.
This gives us a polynomial but somewhat expensive algorithm.

\textbf{Pairwise/Global compatibility} 
(pairwise compatible implies 
global compatibility):
An execution using configuration
P1.v1, .... , Pn.vn works 
if for all i, j (1 $\leq$ i,j $\leq$ n) such that Pi calls 
Pj, no call from Pi.vi to Pj.vj crashes.

 
\subsection{LiquidClimber -- basic } 

\paragraph{Goal of Algorithm.}
The LiquidClimber algorithm ends with a configuration
that is lexicographically maximum (e.g. maximize
packages P1, P2 in that order)  and that satisfies the query constraints
on versions (e.g. only use versions 4, 5, and 6 of package P7).
The query constraints are used to form sourcemap but play
no other role in the algorithm.
The order of packages to maximize are encoded in todolist.

The variable {\em memo} keeps tracks of calls that have failed,
e.g. Pi.vi calling Pj.vj has failed.
If a configuration contains a pair of package-versions that have failed,
then that configuration will fail so will not need to be executed.




\begin{small}
\begin{verbatim}
current    := package version pairs in the initial 
              configuration
todolist   := packages requiring maximization in 
              descending order of priority
constraints := some query constraints on versions of 
               various packages
sourcemap := for each package the versions that 
             exist and satisfy query constraints
memo := calls for some Pi.vi to some Pj.vj that fail. 
             Initially this is empty

liquidclimber()
  for each package p in todolist in descending order of priority
      update current to the highest version of p that works 
      # use git binary on sourcemap
       if current has less than highest version of p 
       in sourcemap then 
        versionstodo = find all greater versions 
                         of p or major releases in 
                         ascending order of version 
                         number within sourcemap
       for each v in versionstodo in order
          temp := current with p set to v 
          ret := trytomakework(p, temp) 
          if ret is not null then # we've had success
             current:= ret

# adjust temp to make it work
# p is the package we're trying to push
trytomakework(p,temp)
  execute temp unless we know from memo that temp will fail
  if the execution of temp fails
    Find the first call, say from Pi.vi' to Pj.vj', 
    that fails
    Record in memo that Pi.vi' calling Pj.vj' fails
    if Pi == p or Pi is earlier than p in todolist then
      possible(Pi) = {vi'}
    if Pj == p or Pj is earlier than p in todolist then 
      possible(Pj) = {vj'}
    if neither Pi nor Pj belongs to the set {x | x = p
    or a package earlier than p in the todolist}
      possible(Pi) = {all versions of Pi in sourcemap}
      possible(Pj) = {all versions of Pj in sourcemap}
    for each configuration c that can
      be constructed from the cross-product of possible(Pi) 
        and possible(Pj) such that the version
        vi'' of Pi and vj'' of Pj has the property
        that (Pi.vi'',Pj.vj'') is not in memo
          ret = trytomakework(temp)
          if (ret is not null) then return ret
    end for
    return null
  else return temp # this configuration works
\end{verbatim}
\end{small}

\textbf{Theorem}: The algorithm finds the lexicographically maximum
configuration that works.

\textbf{Proof sketch}: 
The query constraints are taken into account by the construction of sourcemap.
Todolist is ordered from most important package to least.
Suppose that there is a another configuration 
C’’=P1.v1'', P2.v2'', ...., Pn.vn''
that is lexicographically greater and that also works.
We prove that 
P1.v1'', P2.v2'', ...., Pn.vn''
must have been tried by our algorithm.

Let Px be the first package in Q for which Px.Vx’’ $>$ Px.Vx’.
By construction of versionstodo, Px.vx’’ was tried by the algorithm.
If trytomakework did not succeed to make it work, 
there was some call from Pi.vi to Pj.vj that failed. 
But trytomakework will try all possible combinations between Pi and Pj
as long as those combinations don't affect previously optimized
packages or the package that is currently pushed (for which other
versions will be tried in the for each loop liquidclimber).
Done.

\textbf{Theorem}: If there are a maximum of M versions per package and n
packages, then the number of tests $ \le n*((n-1)) * M * M $

\textbf{Proof}: The number of possible calling pairs $\leq n*(n-1)$.
Equality holds only in the case that every package
calls every other package.
For each package Pi that calls package Pj, in the worst case, we might
have to test each version of Pi calling each version of Pj.
Each time such a call of the form Pi.vi calling Pj.vj
causes an error, we record that fact in memo. 
Once recorded, no configuration
that includes Pi.vi and Pj.vj will be executed.
So, for every such pair Pi and Pj, there need be only $M*M$ executions.
Done.

We have started here with the most minimal assumption.
Stronger assumptions could be considered (e.g., if Pi.vi calls Pj.vj
and fails, then any version greater than vi will fail on any version
less than vj).
Considering such stronger assumptions is part of our ongoing work.

\section{Implementation} 

Our implementation uses the following general strategy.
\begin{figure}
   \includegraphics[width=\columnwidth]{tapp_fig1.jpg}
   \caption{•}
\end{figure}

\begin{itemize}

\item Execute the original configuration C and then
 wrap all relevant parts of the execution into a virtual machine.
We call such a virtual machine {\em frozen} because all its versions are fixed in binary.
In addition, infer the package-versions used within the execution.
{\em Reprozip} allows us to do this by simply running the execution.

\item  Abstract from the package-versions in the frozen
virtual machine the ability to create
virtual machines having arbitrary versions of those same packages.
We call the result a {\em liquid virtual machine},
because it has no fixed binding to particular versions of packages. 
>From the liquid virtual machine, multiple frozen ones can be built each corresponding to a different configuration by pulling versions
from a repository like {\em git}.

\item 
Take a query consisting of packages whose 
versions should be maximized (in descending order of priority) and query constraints on the versions of some of these or other packages.
Use liquidclimber to find the lexicographically maximum
such configuration and freeze it.
Specifically, liquidclimber will call the operational subsystem with
a configuration {\em config} to try and the operational subsystem will:
\begin{small}
\begin{verbatim}


    Starting with the liquid virtual machine,
    create an isolated environment (e.g. VirtualEnv)
    for each package, version in config:
       Checkout the package at a given version
       Install this package with its dependencies in
        the isolated environment (pip install)
    Run the script using reprozip
    if the script succeeds report success
    else report failure and 
         the cause of failure (which call)
 
\end{verbatim}
\end{small}
\end{itemize}


\section{Experiments}

{\em Christophe: here what we would want would be just an example
that starts with our running example and without knowing anything
finds the right result. Something that looks as if it runs}

\section{Related Work}
Given a configuration of package-version
pairs of a software system, the general approach of 
Liquid Version Climbing is to upgrade certain packages Pupgrade
as much as possible given query constraints C. 
The packages constrained in C may overlap in any arbitrary way
with the packages in Pupgrade.

The first step in our approach is to capture the initial
configuration. Most tools that do that use some variant of  {\em ptrace}.
The particular tool we use is ReproZip \cite{reproziptapp}, 
though CARE \cite{care} or CDE-SP \cite{pham2014auditing} could 
have been used with some more enhancements.
These tools find the configuration that was used in the initial
execution. Our software must make explicit the package-versions
that are involved and then "liquify'' the packages.

The next issue is to discover how much upgrading we can
do of the packages in Pupgrade. 
Many excellent package managers are available such as Debian's Apt (with
front end tool Aptitude), and the P2 tool in Eclipse \cite{berre2009dependency}
Package managers fetch components with particular
versions from remote repositories
and perform the deployment, aborting
if there is a problem. 
Liquid Version Climber is a tool that searches for configurations satisfying
query constraints C to optimize Pugrade. Thus, it could use 
these package managers as components.
The essential novelty of Liquid Version Climber is that it explores the space
of possible configurations without requiring any a priori information
about package-version compatibilities. 

The project CUDF (Common Upgradeability Description Format) \cite{treinen2009common} assumes an input of
compatibility
dependencies, e.g. P1 version 8 depends on P2 version 18 or above and
P3 version 8 or above etc.
Given those, the system supports the user's being able to
state a request of the form 
Px version greater than 4 and Py version greater than 5.
CUDF thus has similar objectives and a similar query language
to ours. 
(CUDF is based on the very nice
theoretical work on dependency solving
in \cite{abate2012dependency} which we commend to the reader.)

However, there are two fundamental differences between our approach and CUDF. 
First, CUDF depends on having the CUDF information input by someone
or something. By contrast,
Liquid Version Climber discovers compatibilities
through execution.
Thus, CUDF assumes the pre-existence of
information that Liquid Version Climber learns.
Second, CUDF might be too conservative in that Pi.vi (package Pi version vi)
might be incompatible with Pj.vj, but only for an obscure reason that
is not relevant to a particular application.
Liquid Version Climber finds compatibilities empirically with respect to
the application of interest.\\ 

Operationally, Liquid Version Climber follows a 
generate-and-test paradigm. There is a long history of such work in large
software development projects using tools like
git bisect
to find logical bugs or performance bugs 
in single packages\cite{heger2013automated,chen2007keeping}.
Our essential novelty with respect to that work is that Liquid
Version Climber works on multiple packages that may have been developed
independently.\\


Last but not least, because our audience consists of natural scientists who have neither
the desire nor the training to become software developers, our tool
is meant to support an interface in which the user simply
states goals and the system is guaranteed to achieve
the best possible outcome.
In this way, it is completely compatible with good scientific
software practices, urged in for example in the paper \cite{softcarpentry}:
The software carpentry initiative recommends that scientists who develop their own
software follow some best practices, such as
writing readable well-formatted programs,
using version control, writing test cases, documenting
and using components as much as possible.
Liquid Version Climber requires only the use of components and some version 
control system. So Liquid Version Climber would be a 
good tool for a would-be software carpenter.

\section{Conclusion}

Liquid Version Climber is a collection of techniques 
that incorporate provenance-inspired tools to help software system users 
(such as natural scientists)
take an existing working configuration of package-versions 
and advance to more up-to-date working configurations. 
The goal is to do this rationally and efficiently while requiring minimal
user effort (give a query and let it rip).

Our basic approach is to gather the package-versions of the initial
configuration, abstract this so that arbitrary versions can be fetched,
establish an order of priority among packages, 
test configurations and learn from success or failure which other
configurations to test.
At the end we find a working configuration that is lexicographically,
(based on package priority) maximum.

Future work involves making this system more efficient
and easier to use.

\acks
This work was performed at the Institut
de Biologie Computationnelle (www.ibc-montpellier.fr) and has
been supported by the RecProv Project.
Support for Shasha through an INRIA International Chair and 
the U.S. National Science
Foundation under grants
DBI-0445666,
DBI-0421604,
NSF IOS-0922738,
MCB-0929339,
and
N2010 IOB-0519985 as well as U.S. NIH
2R01GM032877-25A1.
This support is greatly appreciated.

\bibliographystyle{abbrvnat}
\bibliography{bibtapp}
% The bibliography should be embedded for final submission.

%\begin{thebibliography}{}
%\softraggedright
%\end{thebibliography}


\end{document}

