Learning Software Constraints via Installation Attempts
  Modern software systems are expected to be secure and contain all the latest
features, even when new versions of software are released multiple times an
hour. Each system may include many interacting packages. The problem of
installing multiple dependent packages has been extensively studied in the
past, yielding some promising solutions that work well in practice. However,
these assume that the developers declare all the dependencies and conflicts
between the packages. Oftentimes, the entire repository structure may not be
known upfront, for example when packages are developed by different vendors. In
this paper, we present algorithms for learning dependencies, conflicts and
defective packages from installation attempts. Our algorithms use combinatorial
data structures to generate queries that test installations and discover the
entire dependency structure. A query that the algorithms make corresponds to
trying to install a subset of packages and getting a Boolean feedback on
whether all constraints were satisfied in this subset. Our goal is to minimize
the query complexity of the algorithms. We prove lower and upper bounds on the
number of queries that these algorithms require to make for different settings
of the problem.
