In recent years, Unmanned Aerial Vehicles (UAVs) (also called drones) networks have become increasingly popular in scenarios where rapid deployment, flexible mobility, and real-time data acquisition are crucial, such as disaster relief, environmental monitoring, military operations, and smart city infrastructure. However, due to their dynamic nature and dependence on wireless communication, they are intrinsically vulnerable to a variety of cyberattacks. In this work, we present DRUID , a decentralized scheme that silently identifies a compromised drone and selectively alters the messages it forwards. The scheme uses a combination of secret sharing and multipath routing to allow a pair of communicating drones, namely A and B , to detect the presence of a compromised drone along any route between them, thereby categorizing each route as either safe or compromised. The scheme operates iteratively and consists of three key modules: (i) an Information Retrieval Procedure that allows A to learn more about the topology, (ii) a binary search-like Identification Procedure, and (iii) if the previous module fails to identify the compromised drone, a Node Repositioning Procedure that relocates nodes closer to the compromised path. We validate DRUID on a large and diverse set of 178 731 graphs representing realistic UAV networks with different communication ranges. Comparing our scheme to previous work, experiments show that DRUID achieves a 97 % identification rate—up from the 54 % of the most recent alternative approach. We analyze the cost associated with the node repositioning procedure in terms of computation time and drone movement, and show that it generally takes a few seconds.

Security and privacy on the Internet rely on the Public Key Infrastructure (PKI), which is based on unlimited trust in a set of predefined certification authorities included in the users’ root stores. However, the architecture of the PKI is no longer appropriate for the current threat landscape and security principles. Specifically, the implicit and permanent trust given to certification authorities collides with the rising zero trust approach, a cyber-security model that mandates that trust must never be granted implicitly or permanently to any entity. This work offers a zero trust perspective on the PKI and root store composition. Using navigation datasets collected from users’ browsers and passive monitors, we analyze their actual needs and identify the portion of root stores that are useful for their activity. We propose several zero trust policies to manage root stores that shrink the large perimeter of trust allowed by commercial root stores. Our experiments show that less than half of the root certificates included in the Mozilla root store are indeed used for navigation, while only 14 cover 99% of the traffic of our users. Moreover, implementing such policies requires little effort for a company, providing a practical way for managing root stores with up-to-date security principles.

Email is a crucial technology used in daily interactions of citizens, enterprises and organizations with their respective governments. In this work we are concerned with the country-wide network architecture of mail domains of public administrations. We analyze a dataset of government mail domains in Italy, Germany, the United Kingdom and the United States of America in order to investigate the opportunities for a network attacker to violate security properties of email communication, including availability, in large portions of a country. Issues of this kind are particularly relevant in times of high international tension and in which every country should treat its networks as a potential target for other countries. We define a framework for describing the opportunities for a network attacker in the resolution of mail domain names, resolution of mail server names, access to a mail server. Based on this framework, we investigate in detail a number of issues related to redundancy and distribution of dependencies among networks and autonomous systems. We also analyze the usage in the access to mail domains of Route Origin Authorization (ROA), an important defensive technology for detecting attacks at the IP routing level. Our analysis allows gaining important insights into the actual network architecture of such an important piece of critical infrastructure as government mail domains.

In many natural environments, different forms of living organisms successfully accomplish the same task while being diverse in shape and behavior. This biodiversity is what made life capable of adapting to disrupting changes. Being able to reproduce biodiversity in artificial agents, while still optimizing them for a particular task, might increase their applicability to scenarios where human response to unexpected changes is not possible. In this work, we focus onVoxel-based Soft Robots(VSRs), a form of robots that grants great freedom in the design of both morphology and controller and is hence promising in terms of biodiversity. We useevolutionary computationfor optimizing, at the same time, morphology and controller of VSRs for the task of locomotion. We investigate experimentally whether three key factors—representation, Evolutionary Algorithm (EA), and environment—impact the emergence of biodiversity and if this occurs at the expense of effectiveness. We devise an automatic machine learning pipeline for systematically characterizing the morphology and behavior of robots resulting from the optimization process. We classify the robots into species and then measure biodiversity in populations of robots evolved in a multitude of conditions resulting from the combination of different morphology representations, controller representations, EAs, and environments. The experimental results suggest that, in general, EA and environment matter more than representation. We also propose a novel EA based on a speciation mechanism that operates on morphology and behavior descriptors and we show that it allows to jointly evolve morphology and controller of effective and diverse VSRs.

In many natural environments, there are different forms of living creatures that successfully accomplish the same task while being diverse in shape and behavior. This biodiversity is what made life capable of adapting to disrupting changes. Being able to reproduce biodiversity in non-biological agents, while still optimizing them for a particular task, might increase their applicability to scenarios where human response to unexpected changes is not possible.

We describe the design and implementation of a system for executing search-and-replace text processing tasks automatically, based only on examples of the desired behavior. The examples consist of pairs describing the original string and the desired modified string. Their construction, thus, does not require any specific technical skill. The system constructs a solution to the specified task that can be used unchanged on popular existing software for text processing. The solution consists of a search pattern coupled with a replacement expression: the former is a regular expression which describes both the strings to be replaced and their portions to be reused in the latter, which describes how to build the modified strings. Our proposed system is internally based on genetic programming and implements a form of cooperative coevolution in which two separate populations are evolved independently, one for search patterns and the other for replacement expressions. We assess our proposal on six tasks of realistic complexity obtaining very good results, both in terms of absolute quality of the solutions and with respect to the challenging baselines considered.

Voxel-based soft robots (VSRs) are aggregations of elastic, cubic blocks that have sparkled the interest of Robotics and Artificial Life researchers. VSRs can move by varying the volume of individual blocks, according to control signals dictated by a controller, possibly based on inputs coming from sensors embedded in the blocks. Neural networks (NNs) have been used as centralized processing units for those sensing controllers, with weights optimized using evolutionary computation. This structuring breaks the intrinsic modularity of VSRs: decomposing a VSR into modules to be assembled in a different way is very hard.

Grammatical evolution (GE) is one of the most widespread techniques in evolutionary computation. Genotypes in GE are bit strings while phenotypes are strings, of a language defined by a user-provided context-free grammar. In this paper, we propose a novel procedure for mapping genotypes to phenotypes that we call weighted hierarchical GE (WHGE). WHGE imposes a form of hierarchy on the genotype and encodes grammar symbols with a varying number of bits based on the relative expressive power of those symbols. WHGE does not impose any constraint on the overall GE framework, in particular, WHGE may handle recursive grammars, uses the classical genetic operators, and does not need to define any bound in advance on the size of phenotypes. We assessed experimentally our proposal in depth on a set of challenging and carefully selected benchmarks, comparing the results of the standard GE framework as well as two of the most significant enhancements proposed in the literature: 1) position-independent GE and 2) structured GE. Our results show that WHGE delivers very good results in terms of fitness as well as in terms of the properties of the genotype-phenotype mapping procedure.

Context-free grammars are useful tools for modeling the solution space of problems that can be solved by optimization algorithms. For a given solution space, there exists an infinite number of grammars defining that space, and there are clues that changing the grammar may impact the effectiveness of the optimization. In this article, we investigate theoretically and experimentally the possibility of specializing a grammar in a problem, that is, of systematically improving the quality of the grammar for the given problem. To this end, we define the quality of a grammar for a problem in terms of the average fitness of the candidate solutions generated using that grammar. Theoretically, we demonstrate the following findings: 1) that a simple mutation operator employed in a (1 + 1)-EA setting can be used to specialize a grammar in a problem without changing the solution space defined by the grammar and 2) that three grammars of equal quality for a grammar-based version of the ONEMAX problem greatly vary in how they can be specialized with that (1 + 1)-EA, as the expected time required to obtain the same improvement in quality can vary exponentially among grammars. Then, experimentally, we validate the theoretical findings and extend them to other problems, grammars, and a more general version of the mutation operator.

Current signature detection mechanisms can be easily evaded by malware writers by applying obfuscation techniques. Employing morphing code techniques, attackers are able to generate several variants of one malicious sample, making the corresponding signature obsolete. Considering that the signature definition is a laborious process manually performed by security analysts, in this paper we propose a method, exploiting static analysis and Machine Learning classification algorithms, to identify whether a mobile application is modified by means of one or more morphing techniques. We perform experiments on a real-world dataset of Android applications (morphed and original), obtaining encouraging results in the obfuscation technique(s) identification.

WPA2 Enterprise is a fundamental technology for secure communication in enterprise wireless networks. A key requirement of this technology is that WiFi-enabled devices (i.e., supplicants) be correctly configured before connecting to the enterprise wireless network. Supplicants that are not configured correctly may fall prey of attacks aimed at stealing the network credentials very easily. Such credentials have an enormous value because they usually unlock access to all enterprise services.

The huge diffusion of malware in mobile platform is plaguing users. New malware proliferates at a very fast pace: as a matter of fact, to evade the signature-based mechanism implemented in current antimalware, the application of trivial obfuscation techniques to existing malware is sufficient. In this paper, we show how the application of several morphing techniques affects the effectiveness of two widespread malware detection approaches based on Machine Learning coupled respectively with static and dynamic analysis. We demonstrate experimentally that dynamic analysis-based detection performs equally well in evaluating obfuscated and non-obfuscated malware. On the other hand, static analysis-based detection is more accurate on non-obfuscated samples but is greatly negatively affected by obfuscation: however, we also show that this effect can be mitigated by using obfuscated samples also in the learning phase.

We consider the automatic synthesis of an entity extractor, in the form of a regular expression, from examples of the desired extractions in an unstructured text stream. This is a long-standing problem for which many different approaches have been proposed, which all require the preliminary construction of a large dataset fully annotated by the user. In this paper, we propose an active learning approach aimed at minimizing the user annotation effort: the user annotates only one desired extraction and then merely answers extraction queries generated by the system. During the learning process, the system digs into the input text for selecting the most appropriate extraction query to be submitted to the user in order to improve the current extractor. We construct candidate solutions with genetic programming (GP) and select queries with a form of querying-by-committee, i.e., based on a measure of disagreement within the best candidate solutions. All the components of our system are carefully tailored to the peculiarities of active learning with GP and of entity extraction from unstructured text. We evaluate our proposal in depth, on a number of challenging datasets and based on a realistic estimate of the user effort involved in answering each single query. The results demonstrate high accuracy with significant savings in terms of computational effort, annotated characters, and execution time over a state-of-the-art baseline.

Unmanned Aerial Vehicles (UAVs) are becoming increasingly popular and the amount of UAV traffic in urban environments will largely increase in the future, due to profitable tasks which are particularly suited to UAVs, e.g., parcel delivery and surveillance, in particular in the context of smart cities. Trying to ensure the traffic safety and efficiency by acting on the UAV controller alone might be challenging, since the set of involved players (regulators, manufacturers, business users) is large and diversified. In this work, we address this problem by proposing a language for defining rules suitable for UAV traffic which can be enforced in a decentralized way by the UAVs themselves, without any need for communication and regardless of the UAV navigation algorithm. The language allows to express realistic rules, such as ``when cruising, keep a minimum altitude'', concisely and such that they can be processed online by each single UAV basing on its perception of the nearby environment. We experimentally validate the ability of our proposal to impact on the UAV traffic efficiency and safety by performing a large number of simulations with and without a set of realistic rules.

We consider the problem of the filtering of Twitter posts, that is, the hiding of those posts which the user prefers not to visualize on his/her timeline. We define a language for specifying filtering policies suitable for Twitter posts. The language allows each user to decide which posts to filter out based on his/her sensibility and preferences. Since average users may not have the skills necessary to translate their filtering needs into a set of rules, we also propose a method for inferring a policy automatically, based solely on examples of the desired filtering behavior. The method is based on an evolutionary approach driven by a multi-objective optimization scheme. We assess our proposal experimentally on a real Twitter dataset and the results are highly promising.

Consumer reviews are an important information resource for people and a fundamental part of everyday decision-making. Product reviews have an economical relevance which may attract malicious people to commit a review fraud, by writing false reviews. In this work, we investigate the possibility of generating hundreds of false restaurant reviews automatically and very quickly. We propose and evaluate a method for automatic generation of restaurant reviews tailored to the desired rating and restaurant category. A key feature of our work is the experimental evaluation which involves human users. We assessed the ability of our method to actually deceive users by presenting to them sets of reviews including a mix of genuine reviews and of machine-generated reviews. Users were not aware of the aim of the evaluation and the existence of machine-generated reviews. As it turns out, it is feasible to automatically generate realistic reviews which can manipulate the opinion of the user.

A large class of entity extraction tasks from text that is either semistructured or fully unstructured may be addressed by regular expressions, because in many practical cases the relevant entities follow an underlying syntactical pattern and this pattern may be described by a regular expression. In this work, we consider the long-standing problem of synthesizing such expressions automatically, based solely on examples of the desired behavior. We present the design and implementation of a system capable of addressing extraction tasks of realistic complexity. Our system is based on an evolutionary procedure carefully tailored to the specific needs of regular expression generation by examples. The procedure executes a search driven by a multiobjective optimization strategy aimed at simultaneously improving multiple performance indexes of candidate solutions while at the same time ensuring an adequate exploration of the huge solution space. We assess our proposal experimentally in great depth, on a number of challenging datasets. The accuracy of the obtained solutions seems to be adequate for practical usage and improves over earlier proposals significantly. Most importantly, our results are highly competitive even with respect to human operators. A prototype is available as a web application athttp://regex.inginf.units.it.

Presents corrections to typographical errors in the paper, "Inference of regular expressions for text extraction from examples," (Bartoli, A., et al), IEEE Trans. Knowl. Data Eng., vol. 28, no. 5, pp. 1217–1230, May 2016.

There is an increasing interest in the development of techniques for automatic relation extraction from unstructured text. The biomedical domain, in particular, is a sector that may greatly benefit from those techniques due to the huge and ever increasing amount of scientific publications describing observed phenomena of potential clinical interest. In this paper, we consider the problem of automatically identifying sentences that contain interactions between genes and proteins, based solely on a dictionary of genes and proteins and a small set of sample sentences in natural language. We propose an evolutionary technique for learning a classifier that is capable of detecting the desired sentences within scientific publications with high accuracy. The key feature of our proposal, that is internally based on Genetic Programming, is the construction of a model of the relevant syntax patterns in terms of standard part-of-speech annotations. The model consists of a set of regular expressions that are learned automatically despite the large alphabet size involved. We assess our approach on two realistic datasets and obtain 74% accuracy, a value sufficiently high to be of practical interest and that is in line with significant baseline methods.

We propose a system for continuous reauthentication of Web users based on the observed mouse dynamics. Key feature of our proposal is that no specific software needs to be installed on client machines, which allows to easily integrate continuous reauthentication capabilities into the existing infrastructure of large organizations. We assess our proposal with real data from 24 users, collected during normal working activity for several working days. We obtain accuracy in the order of 97%, which is aligned with earlier proposals requiring instrumentation of client workstations for intercepting all mouse activity-quite a strong requirement for large organizations. Our proposal may constitute an effective layer for a defense-in-depth strategy in several key scenarios: Web applications hosted in the cloud, where users authenticate with standard mechanisms, organizations which allow local users to access external Web applications, and enterprise applications hosted in local servers or private cloud facilities.

Regex golf has recently emerged as a specific kind of code golf, i.e., unstructured and informal programming competitions aimed at writing the shortest code solving a particular problem. A problem in regex golf consists in writing the shortest regular expression which matches all the strings in a given list and does not match any of the strings in another given list. The regular expression is expected to follow the syntax of a specified programming language, e.g., Javascript or PHP. In this paper, we propose a regex golf player internally based on Genetic Programming. We generate a population of candidate regular expressions represented as trees and evolve such population based on a multi-objective fitness which minimizes the errors and the length of the regular expression. We assess experimentally our player on a popular regex golf challenge consisting of 16 problems and compare our results against those of a recently proposed algorithm---the only one we are aware of.Our player obtains scores which improve over the baseline and are highly competitive also with respect to human players. The time for generating a solution is usually in the order of tens minutes, which is arguably comparable to the time required by human players.

We consider the problem of matching the topics of a scientific paper with those of possible publication venues for that paper. While every researcher knows the few top-level venues for his specific fields of interest, a venue recommendation system may be a significant aid when starting to explore a new research field. We propose a venue recommendation system which requires only title and abstract, differently from previous works which require full-text and reference list: hence, our system can be used even in the early stages of the authoring process and greatly simplifies the building and maintenance of the knowledge base necessary for generating meaningful recommendations. We assessed our proposal using a standard metric on a dataset of more than 58000 papers: the results show that our method provides recommendations whose quality is aligned with previous works, while requiring much less information from both the paper and the knowledge base.

Information extraction from printed documents is still a crucial problem in many interorganizational workflows. Solutions for other application domains, for example, the web, do not fit this peculiar scenario well, as printed documents do not carry any explicit structural or syntactical description. Moreover, printed documents usually lack any explicit indication about their source. We present a system, which we call PATO, for extracting predefined items from printed documents in a dynamic multisource scenario. PATO selects the source-specific wrapper required by each document, determines whether no suitable wrapper exists, and generates one when necessary. PATO assumes that the need for new source-specific wrappers is a part of normal system operation: new wrappers are generated online based on a few point-and-click operations performed by a human operator on a GUI. The role of operators is an integral part of the design and PATO may be configured to accommodate a broad range of automation levels. We show that PATO exhibits very good performance on a challenging data set composed of more than 600 printed documents drawn from three different application domains: invoices, datasheets of electronic components, and patents. We also perform an extensive analysis of the crucial tradeoff between accuracy and automation level.

Internet security threats often involve the fraudulent modification of a web site, often with the addition of new pages at URLs where no page should exist. Detecting the existence of such hidden URLs is very difficult because they do not appear during normal navigation and usually are not indexed by search engines. Most importantly, drive-by attacks leading users to hidden URLs, for example for phishing credentials, may fool even tech-savvy users, because such hidden URLs are increasingly hosted within trusted sites, thereby rendering HTTPS authentication ineffective. In this work, we propose an approach for detecting such URLs based only on their lexical features, which allows alerting the user before actually fetching the page. We assess our proposal on a dataset composed of thousands of URLs, with promising results.

Search-and-replace is a text processing task which may be largely automated with regular expressions: the user must describe with a specific formal language the regions to be modified (search pattern) and the corresponding desired changes (replacement expression). Writing and tuning the required expressions requires high familiarity with the corresponding formalism and is typically a lengthy, error-prone process.

The huge and ever increasing amount of text generated by Twitter users everyday embeds a wealth of information, in particular, about themes that become suddenly relevant to many users as well as about the sentiment polarity that users tend to associate with these themes. In this paper, we exploit both these opportunities and propose a method for: (i) detecting novel popular themes, i.e. events, (ii) summarizing these events by means of a concise yet meaningful representation, and (iii) assessing the prevalent sentiment polarity associated with each event, i.e., positive vs. negative. Our method is fully unsupervised and requires only a precompiled topic description in the form of set of potentially relevant keywords that might appear in the events of interest. We validate our proposal on a real corpus of about 8,000,000 tweets, by detecting, classifying and summarizing events related to three wide topics associated with tech-related brands.

Electronic devices capable of wireless communication are becoming ubiquitous. They enable a wide range of novel applications but these are often difficult to deploy in practice because wireless channels provide ample opportunities to attackers. A number of approaches have been proposed for building secure channels in these scenarios. An approach that would be simple, general and effective consists in establishing a shared secret between two devices by placing them in physical contact for a few seconds. This approach has not been exploited in practice due to the lack of common interfaces. We demonstrate the practical feasibility of the approach for devices equipped with a small LCD screen and cameras. We transfer secret keys between Android-based smartphones put in contact with each other for just a few seconds. The transfer occurs across a visual channel that cannot be intercepted.

We consider the automatic annotation of faces of people mentioned in news. News stories provide a constant flow of potentially useful image indexing information, due to their huge diffusion on the web and to the involvement of human operators in selecting relevant images for the stories. In this work we investigate the possibility of actually exploiting this wealth of information. We propose and evaluate a system for automatic face annotation of image news that is fully unsupervised and does not require any prior knowledge about topic or people involved. Key feature of our proposal is that it attempts to identify the essential piece of information -- how a person with a given name looks like -- by querying popular image search engines. Mining the web allows overcoming intrinsic limitations of approaches built above a predefined collection of stories: our system can potentially annotate people never handled before since its knowledge base is constantly expanded, as long as search engines keep on indexing the web. On the other hand, leveraging on image search engines forces to cope with the substantial amount of noise in search engine results. Our contribution shows experimentally that automatic face annotation may indeed be achieved based entirely on knowledge that lives in the web.

A key step in the understanding of printed documents is their classification based on the nature of information they contain and their layout. In this work we consider a dynamic scenario in which document classes are not known a priori and new classes can appear at any time. This open world setting is both realistic and highly challenging. We use an SVM-based classifier based only on image-level features and use a nearest-neighbor approach for detecting new classes. We assess our proposal on a real-world dataset composed of 562 invoices belonging to 68 different classes. These documents were digitalized after being handled by a corporate environment, thus they are quite noisy---e.g., big stamps and handwritten signatures at unfortunate positions and alike. The experimental results are highly promising.

Web site defacement, the process of introducing unauthorized modifications to a Web site, is a very common form of attack. In this paper we describe and evaluate experimentally a framework that may constitute the basis for a defacement detection service capable of monitoring thousands of remote Web sites systematically and automatically. In our framework an organization may join the service by simply providing the URLs of the resources to be monitored along with the contact point of an administrator. The monitored organization may thus take advantage of the service with just a few mouse clicks, without installing any software locally or changing its own daily operational processes. Our approach is based on anomaly detection and allows monitoring the integrity of many remote Web resources automatically while remaining fully decoupled from them, in particular, without requiring any prior knowledge about those resources. We evaluated our approach over a selection of dynamic resources and a set of publicly available defacements. The results are very satisfactory: all attacks are detected while keeping false positives to a minimum. We also assessed performance and scalability of our proposal and we found that it may indeed constitute the basis for actually deploying the proposed service on a large scale.

Hand-held devices have become widespread and provided with significant computing capabilities, which results in an increasing pressure for using these devices to perform tasks formerly limited to notebooks, like web browsing. Due to their small screens, however, hand-held devices cannot visualize directly documents that were not designed explicitly for small-screen rendering. Such documents may be rendered either at a scale too small to be useful, or at a scale that requires intensive scrolling operations by the user. Unfortunately, scrolling a small window across a large document with a hand-held device is quite cumbersome. In this paper we propose a scrolling system much simpler and more natural to use, based on the embedded camera-a component available in every modern hand-held device. We detect device motion by analyzing the video stream generated by the camera and then we transform the motion in a scrolling of the content rendered on the screen. This way, the user experiences the device screen like a small movable window on a larger virtual view, without requiring any dedicated motion-detection hardware. We performed an experimental evaluation aimed at assessing the effectiveness of the proposed system in the considered scenario, characterized by low image quality, unpredictable framed scene and soon. We performed an objective benchmark quantifying the accuracy of the detected trajectory and a subjective benchmark examining users' confidence with the proposed system. For the latter evaluation, we involved a panel of 20 subjects that executed a trajectory with our system and, as a comparison, with keyboard, mouse and touchpad. The results demonstrate that our approach is indeed practical.

Web site defacement, the process of introducing unauthorized modifications to a Web site, is a very common form of attack. Detecting such events automatically is very difficult because Web pages are highly dynamic and their degree of dynamism may vary widely across different pages. In this paper we propose a novel detection approach based on genetic programming (GP), an established evolutionary computation paradigm for automatic generation of algorithms. What makes GP particularly attractive in this context is that it does not rely on any domain-specific knowledge, whose description and synthesis is invariably a hard job. In a preliminary learning phase, GP builds an algorithm based on a sequence of readings of the remote page to be monitored and on a sample set of attacks. Then, we monitor the remote page at regular intervals and apply that algorithm, which raises an alert when a suspect modification is found. We developed a prototype based on a broader Web detection framework we proposed earlier and we tested our approach over a dataset of 15 dynamic Web pages, observed for about a month, and a collection of real Web defacements. We compared the results to those of a solution we developed earlier, whose design embedded a substantial amount of domain specific knowledge, and the results clearly show that GP may be an effective approach for this job.

Symbolic regression is aimed at discovering mathematical expressions, in symbolic form, that fit a given sample of data points. While genetic programming (GP) constitutes a powerful tool for solving this class of problems, its effectiveness is still severely limited when the data sample requires different expressions in different regions of the input space - i.e., when the approximating function should be discontinuous. In this paper we present a new GP-based approach for symbolic regression of discontinuous functions in multivariate data-sets. We identify the portions of the input space that require different approximating functions by means of a new algorithm that we call hyper-volume error separation (HVES). To this end we run a preliminary GP evolution and partition the input space based on the error exhibited by the best individual across the data-set. Then we partition the data-set based on the partition of the input space and use each such partition for driving an independent, preliminary GP evolution. The populations resulting from such preliminary evolutions are finally merged and evolved again. We compared our approach to the standard GP search and to a GP search for discontinuous functions in univariate data-sets. Our results show that coupling HVES with GP is an effective approach and provides significant accuracy improvements while requiring less computational resources.

Composition of Internet-based services exported by different organizations has quickly become a key software paradigm for engineering and scientific communities. Although the scheduling of composite service invocations in such a multi-organization, multi-tiered and geographically dispersed environment may have strong impact on performance, this issue has not been explored very much so far. In this work we study the performance of the composite service and we take the perspective of the organizations involved in its implementation. We focus on the trade-off between the performance of the composite service and the global cost incurred at the participating organizations. We seek techniques for executing a given workload by minimizing such cost, while maintaining the performance delivered to clients to an acceptable level.

Organizations are increasingly aggregating their computing resources to form Internet-based grids specialized in specific application workflows and made available to other organizations. The scheduling of jobs in such grids may clearly have a substantial impact on performance, but finding effective scheduling policies is hard due to the very same nature of this scenario. Performance may greatly depend on a myriad of parameters whose values can hardly be determined in practice. Moreover, the load injected by users is typically unpredictable, performance of Internet links may vary widely during an execution and computing resources at participating organizations could also vary dynamically, perhaps because of additional workloads injected by other competing activities. In this paper we propose mechanisms and policies for controlling the scheduling of jobs in such a highly dynamic environment. We attempt to minimize the resource usage at the participating organizations while maintaining the performance delivered to clients at an acceptable level. Our approach consists of a form of admission control at the entrance point of the application workflow that is simple to deploy in practice and does not need any hook from the participating organizations. We simply vary dynamically the maximum number of jobs that can be injected within the grid, based on performance measures taken on line, and delay excess jobs. We have evaluated our proposal in detail, by simulation, focussing on its ability to adapt automatically to perturbations in the form of substantial and unexpected changes in the amount of computing resources available. We have found that our proposal is indeed capable of finding automatically a suitable trade-off between throughput and resource usage, even in such a dynamic scenario.

Abstract We propose a service replication framework for unreliable networks. The service exhibits the same consistency guarantees about the order of execution of operation requests as its non‐replicated implementation. Such guarantees are preserved in spite of server replica failure or network failure (either between server replicas or between a client and a server replica), and irrespective of when the failure occurs. Moreover, the service guarantees that in the case when a client sends an ‘update’ request multiple times, there is no risk that the request be executed multiple times. No hypotheses about the timing retransmission policy of clients are made, e.g. the very same request might even arrive at different server replicas simultaneously. All of these features make the proposed framework particularly suitable for interaction between remote programs, a scenario that is gaining increasing importance. We discuss a prototype implementation of our replication framework based on Tomcat, a very popular Java‐based Web server. The prototype comes into two flavors: replication of HTTP client session data and replication of a counter accessed as a Web service. Copyright © 2005 John Wiley & Sons, Ltd.

A causal broadcast protocol was proposed earlier in [R. Baldoni (1998)]. Two extensions of the protocol were also proposed in order to improve its throughput and bandwidth utilization. We show that both extensions are not live, i.e., there may be execution patterns in which processes stop delivering messages. We also show that the algorithm for the second extension does not satisfy the requirements on which its correctness was established. Finally, we provide fixed versions of both extensions and prove their correctness.

We consider reliable multicast in distributed systems including mobile hosts (MHs) that communicate with a wired infrastructure by means of wireless links. Nearly all existing proposals are based on hand-off, i.e. whenever a MH switches cell, state information about this host travels across the wired network from the support station of the old cell to that of the new cell. However, we are not aware of any detailed performance analysis for hand-off based reliable multicast protocols: previous research in this area has focused mainly on correctness rather than on performance. We analyze in detail, by simulation, the performance of a proposal by Acharya and Badrinath that is based on hand-off and has been highly influential in the design of later protocols. Then, we compare this proposal with one by us that is based on an entirely different philosophy and is the only existing proposal not based on hand-off. Surprisingly, we found that our proposal outperforms the one by Acharya and Badrinath in all the aspects considered: latency, scalability, bandwidth usage efficiency and quickness in managing cell switches of MHs. Moreover, we found that this performance improvement is not obtained at the expense of increased resource requirements on MHs such as energy or memory. We believe that this performance and cost analysis allows us to gain insights into the design of reliable multicast protocols for distributed mobile systems.

Over the last years, many replica control protocols have been developed that take advantage of the ordering and reliability semantics of group communication primitives to simplify database system design and to improve performance. Although current solutions are able to mask site failures effectively, many of them are unable to cope with recovery of failed sites, merging of partitions, or joining of new sites. This paper addresses this important issue. It proposes efficient solutions for online system reconfiguration providing new sites with a current state of the database without interrupting transaction processing in the rest of the system. Furthermore, the paper analyzes the impact of cascading reconfigurations, and argues that they call be handled in an elegant way by extended forms of group communication.

We present the formal verification of a multicast protocol for mobile computing. The protocol supports reliable and totally ordered communication within a set of processes running on mobile hosts. Mobile hosts communicate with a wired infrastructure through wireless links. The protocol is specified in Calculus of Communicating Systems and checked using the Concurrency Workbench tool. The protocol was chosen as a case study to evaluate the usefulness of a methodology, by means of which a property is checked on a reduced system, where the reduction is driven by the formula expressing the property itself. The reduction is obtained by transforming the program into one having a smaller representation. The approach is based on a logic, the selective mu-calculus, which has the characteristic that each formula allows the immediate pointing out of the parts of the system that do not alter the truth value of the formula itself, and thus can be ignored. We show and discuss the experimental results obtained.

Reliable multicast is a powerful communication primitive for structuring distributed programs in which multiple processes must closely cooperate together. We propose a protocol for supporting reliable multicast in a distributed system that includes mobile hosts and evaluate the performance of our proposal through simulation We consider a scenario in which mobile hosts communicate with a wired infrastructure by means of wireless technology. Our proposal provides several novel features. The sender of each multicast may select among three increasingly strong delivery ordering guarantees: FIFO, causal, total. Movements do not trigger the transmission of any message in the wired network as no notion of hand-off is used. The set of senders and receivers (group) may be dynamic. The size of data structures at mobile hosts, the size of message headers, and the number of messages in the wired network for each multicast are all independent of the number of group members. The wireless network is assumed to provide only incomplete spatial coverage and message losses could occur even within cells. Movements are not negotiated and a mobile host that leaves a cell may enter any other cell, perhaps after a potentially long disconnection. The simulation results show that the proposed protocol has good performance and good scalability properties.

With reference to a distributed context consisting of computers connected by a local area network, we present the organization of a memory management system giving physical support to a uniform, persistent vision of storage according to a single address space paradigm. Our system implements a two-layer storage hierarchy in which the distributed secondary memory stores the valid data items and the primary memory supports a form of data caching, for fast processor access. The proposed system defines a small, powerful set of operations that allow application programs to exert explicit control over the memory management activities at the levels of physical storage allocation, data migration across the network, and the data movements between the secondary memory and the primary memory. The system, that has been implemented in prototype form, is assessed from a number of viewpoints. We show that the storage requirements of the information for memory management are negligible. Moreover, the number of messages necessary to determine the network location of a given data item is low and independent of both the network size and the past movements of this data item in the distributed storage.Copyright © 2000 John Wiley & Sons, Ltd.

We propose a multicast protocol for a distributed system that includes mobile hosts. The protocol guarantees reliable delivery, i.e. delivery of every multicast and absence of duplicates. The sender of each multicast may select among three increasingly strong delivery ordering guarantees: FIFO, causal, total. We make loose assumptions on the underlying computing system: (i) we consider an unreliable wireless network i.e. one that provides only incomplete spatial coverage and such that messages could be lost even within cells (e.g., due to physical obstructions); (ii) movements are unpredictable, i.e. a user that leaves a cell may enter any other cell, perhaps after a potentially long disconnection. Our solution does not store any sensible state information at mobile support stations, thus movements do not trigger the transmission query message in the wired network and no notion of hand-off is used. Furthermore, movements at inopportune times can cause only occasional performance penalty but do not affect correctness. Weak assumptions on the underlying computing system, absence of state information at mobile support stations and loose mobility assumptions, contribute to improve the reliability of applications deployed over the proposed protocol.

We consider network applications that are based on the process group paradigm. When such applications are deployed over networks that are subject to failures, they may partition across several disconnected clusters resulting in multiple views of the group's current composition to exist concurrently. Application semantics determine which operations, if any, can be performed in different partitions without compromising consistency. For certain application classes, most (possibly all) operations need to be confined to a single primary partition while other partitions are allowed to service only a (possibly empty) subset of the operations. We propose a mechanism for deciding when a view constitutes the primary partition for the group. Our solution is highly flexible and has the following novel features: each group member can establish if it belongs to the primary partition or not, based solely on local information; the group can be dynamic as processes voluntarily join and leave it; the selection rule for establishing the primary partition need not be universal but can be decided on a per-application basis and can be modified at run time; the primary partition can be re-established even after total failures. Layering our solution on top of a partitionable group membership service allows a wide range of applications with different and possibly conflicting notions of "primary partition" to be supported on a common computing base.

Assembling a collection of typed data into a form suitable for being sent across a network (marshalling) is one of the basic functionalities of any distributed system. This job is typically done by means of pieces of code (stubs) tailored to each type and linked to every process that needs them. This paper presents a novel approach where it is a single module, called the Marshalling Machine (MM), that performs marshalling by using a description of the data structure to be transferred. Such a description is in fact a program written in a simple assembly-like language specialized for marshalling, and MM is an interpreter for this language. The design and implementation of both MM and its language are discussed in detail. The performance of a prototype is analysed, and it is shown that the potential performance loss intrinsic to this interpreted approach is unlikely to be a practical issue. The reason is because, essentially, the cost of decoding instructions of the MM language is negligible compared to the fixed costs of the entire message-passing machinery. Motivations for this work are the potential advantages of an MM-based run-time system over a traditional approach based on compiled stubs. These advantages are discussed extensively, and include greater flexibility, simpler generation of distributed programs, a smaller number of memory-to-memory copies in the message-passing machinery, and elegant accommodation of services whose interface is discovered at run-time. © 1997 by John Wiley & Sons, Ltd.

Distributed systems constructed using off-the-shelf communication infrastructures are becoming common vehicles for doing business in many important application domains. Large geographic extent due to increased globalization, increased probability of failures, and highly dynamic loads all contribute toward a partitionable and asynchronous characterization for these systems. In this paper, we consider the problem of developing reliable applications to be deployed in partitionable asynchronous distributed systems. What makes this task difficult is guaranteeing the consistency of shared state despite asynchrony, failures, and recoveries, including the formation and merging of partitions. While view synchrony within process groups is a powerful paradigm that can significantly simplify reasoning about asynchrony and failures, it is insufficient for coping with recoveries and merging of partitions after repairs. We first give an abstract characterization for shared state management in partitionable asynchronous distributed systems and then show how views can be enriched to convey structural and historical information relevant to the group's activity. The resulting, paradigm, called enriched view synchrony, can be implemented efficiently and leads to a simple programming methodology for solving shared state management in the presence of partitions.

View synchrony has been proposed as a programming paradigm for developing reliable distributed applications. The paradigm is particularly attractive when the underlying computing system is asynchronous and prone to complex failure scenarios including partitions. View synchrony encourages a programming style where groups of processes cooperate closely in order to maintain some form of shared state among them. In this paper we examine the technical problems that arise in shared state management when programming applications using view synchrony. We identify three classes of problems corresponding to state transfer upon group joins, state recreation after total failures and state merging after partition unions. We argue that shared state problems are inherent to any implementation, and without explicit support, attempts to solve them may easily obscure much of the simplicity and elegance of view synchrony. Finally, we propose an extension to the traditional view synchrony model based on the notion of subviews that addresses the problems raised by shared state management.