Search

Maximizing the influence of a fixed size seed set in a graph was investigated intensively in the past decade. Two very relevant questions are 1) how to solve the influence maximization problem on very large graphs within short time and 2) how to compare possible findings with the current state-of-the-art in a fair manner. To solve the first problem, proxy-based influence maximization strategies emerged. However, today's graphs became too large to be solved quickly for many well-established proxy strategies, since they do not scale to such large graphs. In this paper we propose 1) a novel update scheme for iterative influence maximization strategies named Update Approximation (UA) capable of large influence spreads within a few seconds on billion-scale graphs. Further, we present 2) a generic benchmark suite (Influence Maximization Benchmarker --- IMB) to implement and evaluate influence maximization strategies, alongside with implementations for several established strategies. IMB allows for easy to use benchmarks for further research by the community.

Context-aware Recommender Systems (CARS) are becoming an integral part of the everyday life by providing users the ability to retrieve relevant information based on their contextual situation. To increase the predictive power considering many parameters, such as mood, hunger level and user preferences, information from heterogeneous sources should be leveraged. However, these data sources are typically isolated and unexplored and the efforts for integrating them are exacerbated by variety of data structures used for their modelling and costly pre-processing operations. We propose a Knowledge Graph-based approach to allow integration of data according to abstract semantic models for Points-of-Interests (POI)s recommendation scenarios. By enriching data with information about attributes, relationships and their meaning, additional knowledge can be derived from what already exists. We demonstrate the applicability of the proposed approach with a concrete example showing benefits of the retrieving the dispersed data with a unified access mechanism.

Control mechanisms of stream processing applications (SPAs) that ensure latency bounds at minimal runtime cost mostly target a specific infrastructure, e.g., homogeneous nodes. With the growing popularity of the Internet of Things, fog, and edge computing, SPAs are more often distributed on heterogeneous infrastructures, triggering the need for a holistic SPA-control that still considers heterogeneity. We therefore combine individual control mechanisms via the latency-distribution problem that seeks to distribute latency budgets to individually managed components of distributed SPAs for a lightweight yet effective end-to-end control. To this end, we introduce a hierarchical control architecture, give a formal definition of the latency-distribution problem, and provide both an ILP formulation to find an optimal solution as well as a heuristic approach, thereby enabling the combination of individual control mechanisms into one SPA while ensuring global cost minimality. Our evaluations show that both solutions are effective---while the heuristic approach is only slightly more costly than the optimal ILP solution, it significantly reduces runtime and communication overhead.

Network elements (e.g., switches), which intermit service, i.e., stop forwarding and transmission of data according to a repeating schedule, can be found in many real-time capable communication networks, e.g., communication networks with TDMA, Ethernet with Time-aware Shapers or low-power wireless networks. The behavior of those network elements depends on the (stationary) properties of the network elements, their schedule, and the current time, as well as the offered traffic load. If a networked real-time system generates traffic flows which are not synchronized to the schedules of the network elements, formal frameworks such as Network Calculus (NC) are highly valuable to derive deterministic guarantees for the communication. In this paper, we show the fundamental implications of modeling time-triggered network elements with service intermittence in NC. We identify two archetypes of network elements with intermittent service, and propose time-variant and time-invariant approaches to derive service curve formulations to model them. We evaluate the differences between time-variant and time-invariant service curves with respect to the overestimation of worst-case backlog and worst-case delay, and we identify schedule properties which influence the tightness of the derived bounds.

Converged networks support applications with completely different (real-time) requirements. The communication paradigms offered in converged networks are predominantly treated as separate entities from the perspective of traffic engineering, e.g., time-triggered traffic for closed-loop control systems, shaped traffic for multimedia-streaming applications, and best-effort traffic for non-time-critical IT applications. However, there are scenarios where applications benefit from considering time-triggered messages and non-time-triggered messages as complemental components of a single traffic flow. These applications have the property that time-triggered transmissions guarantee basic functionality (e.g., stability of a control system), and additional non-time-triggered transmissions improve the application's performance. We present how to model these so-called complemental traffic flows for this type of application using a traffic metric for the description of the non-time-triggered traffic part. Furthermore, we show that complemental flows are suitable for traffic engineering by presenting two different approaches for the problem of optimized joint routing and scheduling in converged networks with mixed integer linear programming. In our evaluations, we use an exemplary min-max objective for the joint routing and scheduling problem which yields an average reduction of the peak value of the traffic metric by 20-30% over constraint-based approaches.

Future in-vehicle recommendation systems will assist the driver or passenger in all situations before, along, and after a trip. Based on preferences and needs of the user and by taking the current situation and available context information into account, they will provide the right recommendation at the right time. Bosch is the world's largest automotive supplier, delivering a full range of products and services from power-train, infotainment, HMI, connected mobility, driver assistance to automated driving. This talk will present challenges, concepts and recent technical progress in in-vehicle recommendation systems developed at Bosch including details of a combined routing, charging, and point-of-interest (POI) recommendation system. There has been tremendous progress in the field of location-independent recommendation systems, such as recommending films, music, news or shopping articles. The ubiquity of user location information, provided by connected devices, has paved the way for location-based services (LBS), and their combination with social networks have extended these to location-based social network (LBSN) services, see [1, 6] for recent surveys about recommender systems in LBSN. In-vehicle recommendation systems go a step further by extending LBSN services with vehicle context and vehicle specific applications. This can support the user in various applications, such as routing (e.g. route and point of interest recommendation), infotainment (e.g. music or news recommendation), communication (finding a contact, fast call) and in-vehicle control (e.g. seat position, ambient light or HVAC settings). Out-of-vehicle assistance includes the control of connected devices in smart buildings such as alarm systems, heating, kitchen and entertainment devices. We present an important application of in-vehicle recommending systems, a combined routing, charging and POI recommender developed at Bosch. Routing and charging optimization for electric vehicles was described for optimizing the shortest feasible path [2], optimizing constrained shortest path [4], optimizing charging grid demand and opportunities [5], and optimizing minimum cost [3]. These approaches focus on single criteria based optimization. We describe the first system with combined route optimization, charging station search and POI recommendation. It optimizes three criteria: finding the optimal route with the optimal charging stations, so that the vehicle always has enough energy, and finding the optimal POIs along the route, where 'optimal' depends on the drivers preferences and rich context information covering user, vehicle and environment.

In continuous integration development environments, software engineers frequently integrate new or changed code with the mainline codebase. Merged code is then regression tested to help ensure that the codebase remains stable and that continuing engineering efforts can be performed more reliably. Continuous integration is advantageous because it can reduce the amount of code rework that is needed in later phases of development, and speed up overall development time. From a testing standpoint, however, continuous integration raises several challenges. Chief among these challenges are the costs, in terms and time and resources, associated with handling a constant flow of requests to execute tests. To help with this, organizations often utilize farms of servers to run tests in parallel, or execute tests "in the cloud", but even then, test suites tend to expand to utilize all available resources, and then continue to expand beyond that. We have been investigating strategies for applying regression testing in continuous integration development environments more cost-effectively. Our strategies are based on two well-researched techniques for improving the cost-effectiveness of regression testing – regression test selection (RTS) and test case prioritization (TCP). In the continuous integration context, however, traditional RTS and TCP techniques are difficult to apply, because these techniques rely on instrumentation and analyses that cannot easily be applied to fast-arriving streams of test suites. We have thus created new forms of RTS and TCP techniques that utilize relatively lightweight analyses, that can cope with the volume of test requests. To evaluate our techniques, we have conducted an empirical study on several large data sets. In this talk, I describe our techniques and the empirical results we have obtained in studying them.

The Internet of Things (IoT) envisions a huge number of networked sensors connected to the internet. These sensors collect large streams of data which serve as input to wide range of IoT applications and services such as e-health, e-commerce, and automotive services. Complex Event Processing (CEP) is a powerful tool that transforms streams of raw sensor data into meaningful information required by these IoT services. Often these streams of data collected by sensors carry privacy-sensitive information about the user. Thus, protecting privacy is of paramount importance in IoT services based on CEP.In this paper we present a novel pattern-level access control mechanism for CEP based services that conceals private information while minimizing the impact on useful non-sensitive information required by the services to provide a certain quality of service (QoS). The idea is to reorder events from the event stream to conceal privacy-sensitive event patterns while preserving non-privacy sensitive event patterns to maximize QoS. We propose two approaches, namely an ILP-based approach and a graph-based approach, calculating an optimal reordering of events. Our evaluation results show that these approaches are effective in concealing private patterns without significant loss of QoS.

Today's software systems are increasingly required to be flexible which is achieved by providing various forms of loose coupling and configuration options. While loose coupling and configuration options facilitate quick adaptation to changing requirements, such flexibility increases the difficulty of system testing. It is often relatively straight-forward to create different configuration options as test cases, but it is typically much more difficult to formulate the expected system behavior, which is known as the oracle problem. NASA's GMSEC software bus is such a flexible system that serves as a central communication channel for software components based on a publish and subscribe architecture where several software components can be dynamically connected to the system. To cope with the difficulties in testing such a flexible software system, we present a metamorphic testing approach that explicitly addresses the test oracle problem. In this paper, we focus on testing the publish and subscribe functionality of GMSEC motivated by the fact that its middleware-based system architecture is the foundation of many of NASA's missions.

Continuous integration (CI) development environments allow soft-ware engineers to frequently integrate and test their code. While CI environments provide advantages, they also utilize non-trivial amounts of time and resources. To address this issue, researchers have adapted techniques for test case prioritization (TCP) to CI environments. To date, however, the techniques considered have operated on test suites, and have not achieved substantial improvements. Moreover, they can be inappropriate to apply when system build costs are high. In this work we explore an alternative: prioritization of commits. We use a lightweight approach based on test suite failure and execution history that is highly effcient; our approach "continuously" prioritizes commits that are waiting for execution in response to the arrival of each new commit and the completion of each previously scheduled commit. We have evaluated our approach on three non-trivial CI data sets. Our results show that our approach can be more effective than prior techniques.

When testing client-side web applications, it is important to consider different web-browser environments. Different properties of these environments such as web-browser types and underlying platforms may cause a web application to exhibit different types of failures. As web applications evolve, they must be regression tested across these different environments. Because there are many environments to consider this process can be expensive, resulting in delayed feedback about failures in applications. In this work, we propose six techniques for providing a developer with faster feedback on failures when regression testing web applications across different web-browser environments. Our techniques draw on methods used in test case prioritization; however, in our case we prioritize web-browser environments, based on information on recent and frequent failures. We evaluated our approach using four non-trivial and popular open-source web applications. Our results show that our techniques outperform two baseline methods, namely, no ordering and random ordering, in terms of the cost-effectiveness. The improvement rates ranged from -12.24% to 39.05% for no ordering, and from -0.04% to 45.85% for random ordering.

In today's online social networks such as Facebook, users increasingly share their location information as a popular type of personal information. However, since location data can leak privacy-sensitive information about individuals such as the type of places they like to visit, a number of location obfuscation mechanisms have been proposed to avoid such disclosure. These mechanisms publish bigger regions containing the actual user location in order to make it imprecise. Thus an attacker may find it hard to precisely locate the user in a privacy-sensitive place such as a hospital. In this paper, we show that state-of-the-art location obfuscation mechanisms do not provide privacy guarantees against attacks based on mobility prediction. In this regard, we design and demonstrate a mobility prediction attack that exploits location history information of users and show its effectiveness on a year-long real-world location dataset. In particular, our results show that such an attack can successfully de-obfuscate up to 50% of sensitive user visits with high precision (≥ 80%), even when the location history data used for the attack is already obfuscated. We also analyze the success of our mobility prediction attacks and suggest important design improvements for future location privacy mechanisms.

Recently, several approaches have been proposed to automatically model indoor environments. Most of such efforts principally rely on the crowd to sense data such as motion traces, images, and WiFi footprints. However, large datasets are usually required to derive precise indoor models which can negatively affect the energy efficiency of the mobile devices participating in the crowd-sensing system. Furthermore, the aforementioned data types are hardly suitable for deriving 3D indoor models. To overcome these challenges, we propose GraMap, a QoS-aware automatic indoor modeling approach through crowd-sensing 3D point clouds. GraMap exploits a recently-developed sensors fusion mechanism, namely Tango technology, to cooperatively collect point clouds from the crowd. Afterward, a set of backend servers extracts the required geometrical information to derive indoor models. For the sake of improving the energy efficiency of the mobile devices, GraMap performs data quality assurance along with 3D data compression. Specifically, we propose a probabilistic quality model---implemented on the mobile devices---to ensure high-quality of the captured point clouds. In this manner, we conserve energy via sidestepping the repetition of sensing queries due to uploading low-quality point clouds. Nevertheless, the resultant indoor models may still suffer from incompleteness and inaccuracies. Therefore, GraMap leverages formal grammars which encode design-time knowledge, i.e. structural information about the building, to enhance the quality of the derived models. To demonstrate the effectiveness of GraMap, we implemented a crowd-sensing Android App to collect point clouds from volunteers. We show that GraMap derives highly-accurate models while reducing the energy costs of pre-processing and reporting the point clouds.

In recent years, content-based publish/subscribe middleware has harnessed the power of Software-Defined Networking (SDN) to leverage performance gains in terms of throughput rates, end-to-end latency, etc. To this end, content filters are directly installed on the Ternary Content Addressable Memory (TCAM) of switches. Such a middleware assumes unlimited TCAM space to deploy content filters. However, in reality, TCAM is a scarce resource and the number of flow table entries available for publish/subscribe traffic is severely limited. While such a limitation poses severe problems for the deployment of publish/subscribe middleware in practice, it is yet to be addressed in literature.So, in this paper, we design a filter aggregation algorithm that merges content filters on individual switches to respect TCAM constraints while ensuring minimal increase in unnecessary network traffic. Our algorithm uses the knowledge of advertisements, subscriptions, and a global view of the network state to perform bandwidth-efficient aggregation decisions on necessary switches. We provide different flavors of this algorithm with varying degrees of accuracy and complexity and thoroughly evaluate their performances under realistic workload. Our evaluation results show that our designed aggregation algorithm successfully meets TCAM constraints on switches while also reducing unnecessary traffic introduced in the network due to aggregation as compared to a baseline approach by up to 99.9%.

Code offloading strives for increasing the energy efficiency and execution speed of mobile applications on resource-constrained mobile devices. First approaches considered only a code offloading between two (or three) tiers, executing code either locally on the mobile device or remotely on a powerful server in the vicinity or in a distant cloud. However, new execution environments comprise multiple tiers, containing highly distributed heterogeneous resources.We present in this paper our Code Bubbling Offload System (CoBOS). CoBOS targets n-tier environments containing highly distributed heterogeneous resources with different performance characteristics and cost implications. In such n-tier environments, it is very costly for a resource-constrained mobile device to gather a global view on available resources. As a result, we propose the novel concept of code bubbling. Code bubbling moves code dynamically and adaptively towards more powerful and more distant tiers, enabling an efficient and scalable code offloading in n-tier environments. Each tier makes autonomous decisions to execute code in the tier or forward it further to the next tier. To support such a recursive escalation of code along autonomous tiers, CoBOS offloads self-contained offload requests that possess all of the required information for the processing. Our real-world evaluation shows that CoBOS decreases the energy consumption by 77% and the execution time by 83% for code offloading in n-tier environments.

Software engineers use record/replay tools to capture use case scenarios that can serve as regression tests for web applications. Such tests, however, can be brittle in the face of code changes. Thus, researchers have sought automated approaches for repairing broken record/replay tests. To date, such approaches have operated by directly analyzing differences between the releases of web applications. Often, however, intermediate versions or commits exist between releases, and these represent finer-grained sequences of changes by which new releases evolve. In this paper, we present WATERFALL, an incremental test repair approach that applies test repair techniques iteratively across a sequence of fine-grained versions of a web application. The results of an empirical study on seven web applications show that our approach is substantially more effective than a coarse-grained approach (209% overall), while maintaining an acceptable level of overhead.

Cyber-physical systems (CPS), like the ones used in industrial automation systems, are highly time-sensitive applications demanding zero packet losses along with stringent real-time guarantees like bounded latency and jitter from the underlying network for communication. With the proliferation of IEEE 802.3 and IP networks, there is a desire to use these networks instead of the currently used field-buses for time-sensitive applications. However, these networking technologies, which originally were designed to provide best effort communication services, lack mechanisms for providing real-time guarantees. In this paper, we present Time-Sensitive Software-Defined Networks (TSSDN), which provide real-time guarantees for the time-triggered traffic in time-sensitive systems while also transporting non-time-sensitive traffic. TSSDN provides these guarantees by bounding the non-deterministic queuing delays for time-sensitive traffic. To this end, it exploits the logical centralization paradigm of software-defined networking to compute a transmission schedule for time-sensitive traffic initiated by the end systems based on a global view. In particular, we present various Integer Linear Program (ILP) formulations that solve the combined problem of routing and scheduling time-triggered traffic. Moreover, we show that end systems can comply with a given schedule with high precision using user-space packet processing frameworks. Our evaluations show that TSSDN has deterministic end-to-end delays (≤ 14 μs on our benchmark topology) with low and bounded jitter (≤ 7 μs).

With the vision of Internet of Things gaining popularity at a global level, efficient publish/subscribe middleware for communication within and across datacenters is extremely desirable. In this respect, the very popular Software-defined Networking (SDN), which enables publish/subscribe middleware to perform line-rate filtering of events directly on hardware, can prove to be very useful. While deploying content filters directly on switches of a software-defined network allows optimized paths, high throughput rates, and low end-to-end latency, it suffers from certain inherent limitations w.r.t. no. of bits available on hardware switches to represent these filters. Such a limitation affects expressiveness of filters, resulting in unnecessary traffic in the network.In this paper, we explore various techniques to represent content filters expressively while being limited by hardware. We implement and evaluate techniques that i) use workload, in terms of events and subscriptions, to represent content, and ii) efficiently select attributes to reduce redundancy in content. Moreover, these techniques complement each other and can be combined together to further enhance performance. Our detailed performance evaluations show the potential of these techniques in reducing unnecessary traffic when subjected to different workloads.

In recent years, the proliferation of highly dynamic graph-structured data streams fueled the demand for real-time data analytics. For instance, detecting recent trends in social networks enables new applications in areas such as disaster detection, business analytics or health-care. Parallel Complex Event Processing has evolved as the paradigm of choice to analyze data streams in a timely manner, where the incoming data streams are split and processed independently by parallel operator instances. However, the degree of parallelism is limited by the feasibility of splitting the data streams into independent parts such that correctness of event processing is still ensured. In this paper, we overcome this limitation for graph-structured data by further parallelizing individual operator instances using modern graph processing systems. These systems partition the graph data and execute graph algorithms in a highly parallel fashion, for instance using cloud resources. To this end, we propose a novel graph-based Complex Event Processing system GraphCEP and evaluate its performance in the setting of two case studies from the DEBS Grand Challenge 2016.

Recording the sequence of events that lead to a failure of a web application can be an effective aid for debugging. Nevertheless, a recording of an event sequence may include many events that are not related to a failure, and this may render debugging more difficult. To address this problem, we have adapted Delta Debugging to function on recordings of web applications, in a manner that lets it identify and discard portions of those recordings that do not influence the occurrence of a failure. We present the results of three empirical studies that show that (1) recording reduction can achieve significant reductions in recording size and replay time on actual web applications obtained from developer forums, (2) reduced recordings do in fact help programmers locate faults significantly more efficiently as, and no less effectively than non-reduced recordings, and (3) recording reduction produces even greater reductions on larger, more complex applications.

Realizing a communication middleware in a software-defined network can leverage significant performance gains in terms of latency, throughput and bandwidth efficiency. For example, filtering operations in an event-based middleware can be performed highly efficiently in the TCAM memory of switches enabling line-rate forwarding of events. A key challenge in a software-defined network, however, is to ensure high responsiveness of the control plane to dynamically changing communication interactions. In this paper, we propose a methodology for both vertical and horizontal scaling of the distributed control plane that is capable of improving the responsiveness by enabling concurrent network updates in the presence of high dynamics while ensuring consistent changes to the data plane of a communication middleware. In contrast to existing scaling approaches that aim for a general-purpose distributed control plane, our approach uses knowledge of the application semantics that is already available in the design of the data plane of a communication middleware, e.g. subscriptions and advertisements in an event-based middleware. By proposing a methodology for an application-aware control distribution, we show, in the context of PLEROMA, an event-based middleware, that application-awareness is significantly beneficial in avoiding the synchronization bottlenecks for ensuring consistency in the presence of concurrent network updates and thus greatly improves the responsiveness of the control plane.

In continuous integration development environments, software engineers frequently integrate new or changed code with the mainline codebase. This can reduce the amount of code rework that is needed as systems evolve and speed up development time. While continuous integration processes traditionally require that extensive testing be performed following the actual submission of code to the codebase, it is also important to ensure that enough testing is performed prior to code submission to avoid breaking builds and delaying the fast feedback that makes continuous integration desirable. In this work, we present algorithms that make continuous integration processes more cost-effective. In an initial pre-submit phase of testing, developers specify modules to be tested, and we use regression test selection techniques to select a subset of the test suites for those modules that render that phase more cost-effective. In a subsequent post-submit phase of testing, where dependent modules as well as changed modules are tested, we use test case prioritization techniques to ensure that failures are reported more quickly. In both cases, the techniques we utilize are novel, involving algorithms that are relatively inexpensive and do not rely on code coverage information -- two requirements for conducting testing cost-effectively in this context. To evaluate our approach, we conducted an empirical study on a large data set from Google that we make publicly available. The results of our study show that our selection and prioritization techniques can each lead to cost-effectiveness improvements in the continuous integration process.

Software complexity has increased the need for automated software testing. Most research on automating testing, however, has focused on creating test input data. While careful selection of input data is necessary to reach faulty states in a system under test, test oracles are needed to actually detect failures. In this work, we describe Dodona, a system that supports the generation of test oracles. Dodona ranks program variables based on the interactions and dependencies observed between them during program execution. Using this ranking, Dodona proposes a set of variables to be monitored, that can be used by engineers to construct assertion-based oracles. Our empirical study of Dodona reveals that it is more effective and efficient than the current state-of-the-art approach for generating oracle data sets, and can often yield oracles that are almost as effective as oracles hand-crafted by engineers without support.

The relevance of graphical functions in vehicular applications has increased significantly during the few last years. Modern cars are equipped with multiple displays used by different applications such as speedometer or navigation system. However, so far applications are restricted to using dedicated displays. In order to increase flexibility, the requirement of sharing displays between applications has emerged. Sharing displays leads to safety and security concerns since safety-critical applications as the dashboard warning lights share the same displays with uncritical or untrusted applications like the navigation system or third-party applications. To guarantee the safe and secure sharing of displays, we present a formal model for defining and controlling the access to display areas in this paper. We prove the validity of this model, and present a proof-of-concept implementation to demonstrate the feasibility of our concept.

Despite decades of work by researchers and practitioners on numerous software quality assurance techniques, testing remains one of the most widely practiced and studied approaches for assessing and improving software quality. Our goal, in this paper, is to provide an accounting of some of the most successful research performed in software testing since the year 2000, and to present what appear to be some of the most significant challenges and opportunities in this area. To be more inclusive in this effort, and to go beyond our own personal opinions and biases, we began by contacting over 50 of our colleagues who are active in the testing research area, and asked them what they believed were (1) the most significant contributions to software testing since 2000 and (2) the greatest open challenges and opportunities for future research in this area. While our colleagues’ input (consisting of about 30 responses) helped guide our choice of topics to cover and ultimately the writing of this paper, we by no means claim that our paper represents all the relevant and noteworthy research performed in the area of software testing in the time period considered—a task that would require far more space and time than we have available. Nevertheless, we hope that the approach we followed helps this paper better reflect not only our views, but also those of the software testing community in general.

Concurrent programs are prone to various classes of difficult-to-detect faults, of which data races are particularly prevalent. Prior work has attempted to increase the cost-effectiveness of approaches for testing for data races by employing race detection techniques, but to date, no work has considered cost-effective approaches for re-testing for races as programs evolve. In this paper we present SimRT, an automated regression testing framework for use in detecting races introduced by code modifications. SimRT employs a regression test selection technique, focused on sets of program elements related to race detection, to reduce the number of test cases that must be run on a changed program to detect races that occur due to code modifications, and it employs a test case prioritization technique to improve the rate at which such races are detected. Our empirical study of SimRT reveals that it is more efficient and effective for revealing races than other approaches, and that its constituent test selection and prioritization components each contribute to its performance.