An Integrated Framework for Improving the Quality and Reliability of Software Upgrades

Despite major advances in the engineering of maintainable and robust software over the years, upgrading software remains a primitive and error-prone activity. In this dissertation, we argue that several problems with upgrading software are caused by a poor integration between upgrade deployment, testing, and problem reporting. To support this argument, we present a characterization of software upgrades resulting from a survey we conducted of 50 system administrators. Motivated by the survey results, we present Mirage, a distributed framework for integrating upgrade deployment, testing, and problem reporting into the overall upgrade development process. Mirage's deployment subsystem allows the vendor to deploy its upgrades in stages over clusters of users sharing similar environments. Staged deployment incorporates testing of the upgrade on the users' machines. It is effective in allowing the vendor to detect problems early and limit the dissemination of buggy upgrades. Oasis, the testing subsystem of Mirage, improves on current state-of-the-art concolic and symbolic engines by implementing a new heuristic to prioritize the exploration of new or affected code in the upgrade. Furthermore, interactive symbolic execution, a new approach exposing the problem of path exploration to the tester using a graphical user interface, can be used to develop new search heuristics or manually guide testing to important areas of the source code. In spite of all of these efforts, some bugs are bound to remain in the software when it is deployed, and will be discovered and reported only later by the users. With the last component of Mirage, we consider the problem of instrumenting programs to reproduce bugs effectively, while keeping user data private. In particular, we develop static and dynamic analysis techniques to minimize the amount of instrumentation, and therefore the overhead incurred by the users, while considerably speeding up debugging. By combining up-front testing, stage deployment, testing on user machines, and efficient reporting, Mirage successfully reduces the number of problems, minimizes the number of users affected, and shortens the time needed to fix remaining problems.

Exploitation de connaissances sémantiques externes dans les représentations vectorielles en recherche documentaire

Florian Seydoux

The work presented in this thesis deals with several problems met in information retrieval (IR), task which one can summarise as identifying, in a collection of "documents", a subset of documents carrying a sought information, i.e.. relevant for a request expressed by a user. In the case of textual documents, to which we limited ourselves within the framework of this thesis, a significant part of the difficulty lies in ambiguity inherent to human languages. The interaction with the user is also approached in our work, by studying a tool enabling a natural language access to a database. Finally, some techniques which permit the visualisation of large collections of documents are also presented. In this document we first of all describe the principal models of IR by highlighting the relations which exist with some manual technics of IR and document retrieval, developed during the past centuries. We present the principle of document indexing, allowing us to represent documents in a multidimensional space, and the use of this representation by a vectorial model. After having reviewed the principal improvements made these last years with vectorial research systems, including the preprocessings of collections, the indexing mechanism and measurements of similarities between documents, we detail some recent usecases of additional semantic resources (semantic dictionaries, thesaurus, networks, ontologies) reported in scientific literature for the indexing task. We then present more in detail the semantic indexing principle of textual documents by using a thesaurus, consisting in integrating in the document's representation space at least part of the informational contents of hierarchical semantic resources. We propose a general framework allowing us to describe and position various possible techniques to carry out the semantic indexing by adapting, if possible, the specificity of the descriptions resulting from the semantic resources to the data to be represented. We use this framework to describe three families of criteria usable for semantic indexing, each one having its own characteristics. For each of these families, we give the specific algorithms allowing the computation of the criteria. The first two families allow us to consider several criteria already known in feature selection. Moreover we show that, unfortunately, many of these criteria are in fact not very effective for the considered task. The third family allows us to introduce a completely new criterion, the Minimum Redundancy Cut criterion (MRC), built on the basis of the information theory and allowing us to obtain index terms having a probability of occurrence in the collection of documents as well balanced as possible. Finally, we treat the case of semantic index independent of the data (statically choosen), allowing a parameterisation of the level of generality of the index terms. Some of the criteria suggested for semantic indexing has been empirically evaluated. To judge their relevance, we used a well known vectorial system (the Smart IR system) and measured the performances of IR obtained with various reference collections. Those collections was indexed on the basis of the studied criterion, by taking into account the strongly structuring semantic relation of hyper/hyponymy ("is-a" relation), given by two different semantic resources. By comparing results obtained with the performances of a traditional indexing (using the lemmas of the words as representation space), we can show on one hand the relevance of the semantic indexings (in RD) and on the other hand the quality of the proposed criterion (MRC). Concerning man-machine interaction, we present a general outline allowing to build in a relatively fast and systematic way systems with mixed initiative, giving the human user a large (and natural) latitude in the control of the dialogue. This outline is usable in typical database research-task applications (where the database is hidden to the user, but the latter knows exactly which information they wish to find) as well as advice-task applications, for which the users does not necessarily have a precise idea of their needs, and uses the system not only for specifing their wishes, but also a set of propositions as a final result. We particularly stress the techniques allowing us to obtain a robust system, able to deal with speech recognizer failures. Concerning the visualisation of large textual data collections, we present an application of the correspondences analysis (allowing to highlight similarities and oppositions for various groups of entity, built on the basis of additional features present in the DB) to the case of patents data. In addition, we propose a method (based on the bootstrap replication principle) allowing us to determine a confidence interval for relative positionings of various groups, thus permit to immediately judge the reliability of the visually apparent similarities or oppositions.

EPFL2006

Active: a unified platform for building intelligent applications

Didier Guzzoni

Computers have become affordable, small, omnipresent and are often connected to the Internet. However, despite the availability of such rich environments, user interfaces have not been adapted to fully leverage their potential. In our view, user interfaces will evolve to become more than simple tools that act using a click-and-act paradigm – people want software that can act as assistants to whom tasks can be delegated. This new type of software will provide us with more user-centric systems, able to interact naturally with human users and with the information environment. Although progress has been made in this direction over the last decade, current research in the field has shown that building intelligent assistants is a complex task that requires expertise in many fields, ranging from artificial intelligence to core software and hardware engineering. The difficulty of deeply integrating all the technologies and AI methodologies required to produce robust intelligent assistants has greatly limited the impact and widespread adoption of this form of software. In this thesis, we propose to design, implement and evaluate a new methodology and associated tool suite aimed to ease and accelerate the development of intelligent assistant software. Active, our solution, introduces the original concept of Active Ontologies, and combines it with a service oriented architecture to serve as the foundation for user-centric applications. The Active software suite features a programming editor, a runtime server and associated management tools. Using this unified platform, we developed techniques for rapidly creating intelligent assistant applications that weave together language processing, process modeling and dynamic service orchestration. To validate our approach, three prototypes have been implemented and evaluated. First, we created an assistant that helps mobile users retrieve data and access online services. The system allows users to fetch information through natural language dialog about restaurants, hotels, points of interest, flights status and weather forecasts. As a second prototype, we have implemented an assistant to help surgeons in the context of the operating room. The system uses a combination of voice and gesture recognition to help surgeons navigate through pre-operative information, visualize and control a live video stream coming from an endoscope mounted on a robotic arm. Lastly, we have created a system that helps organize meetings through emails and instant messages with the organizer and attendees. These three prototypes are deployed in very different application domains, and yet are built with the same tools and methods; this demonstrates the flexibility and versatility of our approach. We conducted a user study to validate our claim that, in specific domains, intelligent assistant software can perform better than conventional software approaches. First, we compared our mobile assistant against Google Mobile™, the leading commercially available search application for mobile users. We asked a population of users to accomplish ten travel-related tasks with both systems. Results show that, for the travel domain, our assistant-based system performs significantly better both in terms of effectiveness and time to completion than the more conventional, keyword-based search engine. In the medical domain, we asked a small population of surgeons to accomplish a set of tasks with our second prototype. After providing us with a positive feedback, surgeons used our prototype to discuss and experiment with innovative forms of user interaction in the context of the operating room. We also performed evaluations to support our claim that our unified approach accelerates the software development of intelligent assistants. First, we gave basic training on the Active platform to a population of software developers, asking them to go through a simple tutorial. Once trained, they were able to successfully program the core component of the mobile assistant prototype in under two hours. As a second validation, the meeting organizing assistant was designed, implemented and tested within three working days – comparable systems published in the literature were the product of significantly more time and resource investment. This demonstrates that a system encompassing numerous AI and software development aspects, including language processing, multiple modalities, contextual dialog, processing logic and backend services integration, can be rapidly implemented and tested using the Active framework. Our work shows that for many task-oriented domains, intelligent assistant applications can be significantly more effective than conventional systems. Through our Active Ontology approach and associated methodologies and tools, we have shown that complex intelligent assistant applications, perhaps for the first time, can be developed with low cost and high reliability. In addition to receiving a positive echo from the research world, our work is also causing ripples in the commercial world.

EPFL2008

Coordinating Agile Systems through the Model-based Execution of Temporal Plans

Thomas Léauté

Agile autonomous systems are emerging, such as unmanned aerial vehicles (UAVs), that must robustly perform tightly coordinated time-critical missions; for example, military surveillance or search-and-rescue scenarios. In the space domain, execution of temporally flexible plans has provided an enabler for achieving the desired coordination and robustness, in the context of space probes and planetary rovers, modeled as discrete systems. We address the challenge of extending plan execution to systems with continuous dynamics, such as air vehicles and robot manipulators, and that are controlled indirectly through the setting of continuous state variables. Systems with continuous dynamics are more challenging than discrete systems, because they require continuous, low-level control, and cannot be controlled by issuing simple sequences of discrete commands. Hence, manually controlling these systems (or plants) at a low level can become very costly, in terms of the number of human operators necessary to operate the plant. For example, in the case of a fleet of UAVs performing a search-and-rescue scenario, the traditional approach to controlling the UAVs involves providing series of close waypoints for each aircraft, which incurs a high workload for the human operators, when the fleet consists of a large number of vehicles. Our solution is a novel, model-based executive, called Sulu, that takes as input a qualitative state plan, specifying the desired evolution of the state of the system. This approach elevates the interaction between the human operator and the plant, to a more abstract level where the operator is able to “coach” the plant by qualitatively specifying the tasks, or activities, the plant must perform. These activities are described in a qualitative manner, because they specify regions in the plant’s state space in which the plant must be at a certain point in time. Time constraints are also described qualitatively, in the form of flexible temporal constraints between activities in the state plan. The design of low-level control inputs in order to meet this abstract goal specification is then delegated to the autonomous controller, hence decreasing the workload per human operator. This approach also provides robustness to the executive, by giving it room to adapt to disturbances and unforeseen events, while satisfying the qualitative constraints on the plant state, specified in the qualitative state plan. Sulu reasons on a model of the plant in order to dynamically generate near-optimal control sequences to fulfill the qualitative state plan. To achieve optimality and safety, Sulu plans into the future, framing the problem as a disjunctive linear programming problem. To achieve robustness to disturbances and maintain tractability, planning is folded within a receding horizon, continuous planning and execution framework. The key to performance is a problem reduction method based on constraint pruning. We benchmark performance using multi-UAV firefighting scenarios on a real-time, hardware-in-the-loop testbed.

Massachusetts Institute of Technology (MIT)2005