Biblio

We introduce a novel framework for the stability analysis of discrete-time linear switching systems with switching sequences constrained by an automaton. The key element of the framework is the algebraic concept of multinorm, which associates a different norm per node of the automaton, and allows to exactly characterize stability. Building upon this tool, we develop the first arbitrarily accurate approximation schemes for estimating the constrained joint spectral radius ρˆ, that is the exponential growth rate of a switching system with constrained switching sequences. More precisely, given a relative accuracy r > 0, the algorithms compute an estimate of ρˆ within the range [ ˆρ, (1+r)ρˆ]. These algorithms amount to solve a well defined convex optimization program with known time-complexity, and whose size depends on the desired relative accuracy r > 0.

Given the ever increasing number of research tools to automatically generate inputs to test Android applications (or simply apps), researchers recently asked the question "Are we there yet?" (in terms of the practicality of the tools). By conducting an empirical study of the various tools, the researchers found that Monkey (the most widely used tool of this category in industrial settings) outperformed all of the research tools in the study. In this paper, we present two signi cant extensions of that study. First, we conduct the rst industrial case study of applying Monkey against WeChat, a popular  messenger app with over 762 million monthly active users, and report the empirical ndings on Monkey's limitations in an industrial setting. Second, we develop a new approach to address major limitations of Monkey and accomplish substantial code-coverage improvements over Monkey. We conclude the paper with empirical insights for future enhancements to both Monkey and our approach.

Container-based network emulation offers high fidelity and a scalable testing environment to bridge the gap between research ideas and real-world network applications. However, containers take their notions of time from the physical system clock, and thus the time-stamped events from different containers are multiplexed to reflect the scheduling serialization by the Linux operating system. Conjoining the emulator and other simulators is also challenging due to the difficulties of synchronizing the virtual simulation clock with the physical system clock. Virtual time systems for network emulation shed light on both issues. In this paper, we develop a lightweight container-based virtual time system in Linux Kernel. We use time dilation to trade time with system resources by precisely scaling the time of interactions between containers and physical devices. We develop a time freezer to enable the precise pause and resume of an emulation experiment, which offers the virtual time support to interface with simulators for close synchronization. We integrate the virtual time system into a software-defined networking emulator, Mininet, and evaluate the system accuracy, scalability, and overhead. Finally, we use the virtual-time-enabled emulation testbed to conduct a case study of equal-cost multi-path routing protocol analysis in a data center network.

Code Hunt (https://www.codehunt.com/) from Microsoft Research is a web-based serious gaming platform being popularly used for various programming contests. In this paper, we demonstrate preliminary statistical analysis of a Code Hunt data set that contains the programs written by students (only) worldwide during a contest over 48 hours. There are 259 users, 24 puzzles (organized into 4 sectors), and about 13,000 programs submitted by these users. Our analysis results can help improve the creation of puzzles in a future contest.

We present ConVenus, a system that performs rapid congestion verification of network updates in softwaredefined networks. ConVenus is a lightweight middleware between the SDN controller and network devices, and is capable to intercept flow updates from the controller and verify whether the amount of traffic in any links and switches exceeds the desired capacity. To enable online verification, ConVenus dynamically identifies the minimum set of flows and switches that are affected by each flow update, and creates a compact network model. ConVenus uses a four-phase simulation algorithm to quickly compute the throughput of every flow in the network model and report network congestion. The experimental results demonstrate that ConVenus manages to verify 90% of the updates in a network consisting of over 500 hosts and 80 switches within 5 milliseconds.

We study the Lp induced gain of discretetime linear switching systems with graph-constrained switching sequences. We first prove that, for stable systems in a minimal realization, for every p ≥ 1, the Lp-gain is exactly characterized through switching storage functions. These functions are shown to be the pth power of a norm. In order to consider general systems, we provide an algorithm for computing minimal realizations. These realizations are rectangular systems, with a state dimension that varies according to the mode of the system. We apply our tools to the study on the of L2-gain. We provide algorithms for its approximation, and provide a converse result for the existence of quadratic switching storage functions. We finally illustrate the results with a physically motivated example.

Our position is that a key component of securing cyber-physical systems (CPS) is to develop a theory of accountability that encompasses both control and computing systems. We envision that a unified theory of accountability in CPS can be built on a foundation of causal information flow analysis. This theory will support design and analysis of mechanisms at various stages of the accountability regime: attack detection, responsibility-assignment (e.g., attack identification or localization), and corrective measures (e.g., via resilient control) As an initial step in this direction, we summarize our results on attack detection in control systems. We use the Kullback-Liebler (KL) divergence as a causal information flow measure. We then recover, using information flow analyses, a set of existing results in the literature that were previously proved using different techniques. These results cover passive detection, stealthy attack characterization, and active detection. This research direction is related to recent work on accountability in computational systems [1], [2], [3], [4]. We envision that by casting accountability theories in computing and control systems in terms of causal information flow, we can provide a common foundation to develop a theory for CPS that compose elements from both domains.

We are witnessing a huge growth of cyber-physical systems, which are autonomous, mobile, endowed with sensing, controlled by software, and often wirelessly connected and Internet-enabled. They include factory automation systems, robotic assistants, self-driving cars, and wearable and implantable devices. Since they are increasingly often used in safety- or business-critical contexts, to mention invasive treatment or biometric authentication, there is an urgent need for modelling and verification technologies to support the design process, and hence improve the reliability and reduce production costs. This paper gives an overview of quantitative verification and synthesis techniques developed for cyber-physical systems, summarising recent achievements and future challenges in this important field.

In this paper, we investigate detectability and identifiability of attacks on linear dynamical systems that are subjected to external disturbances. We generalize a concept for a security index, which was previously introduced for static systems. The index exactly quantifies the resources necessary for targeted attacks to be undetectable and unidentifiable in the presence of disturbances. This information is useful for both risk assessment and for the design of anomaly detectors. Finally, we show how techniques from the fault detection literature can be used to decouple disturbances and to identify attacks, under certain sparsity constraints.

The theory of robust control models the controller-disturbance interaction as a game where disturbance is nonstrategic. The proviso of a deliberately malicious (strategic) attacker should be considered to increase the robustness of infrastructure systems. This has become especially important since many IT systems supporting critical functionalities are vulnerable to exploits by attackers. While the usefulness of game theory methods for modeling cyber-security is well established in the literature, new game theoretic models of cyber-physical security are needed for deriving useful insights on "optimal" attack plans and defender responses, both in terms of allocation of resources and operational strategies of these players. This whitepaper presents some progress and challenges in using game-theoretic models for security of infrastructure networks. Main insights from the following models are presented: (i) Network security game on flow networks under strategic edge disruptions; (ii) Interdiction problem on distribution networks under node disruptions; (iii) Inspection game to monitor commercial non-technical losses (e.g. energy diversion); and (iv) Interdependent security game of networked control systems under communication failures. These models can be used to analyze the attacker-defender interactions in a class of cyber-physical security scenarios.

In this paper a novel set-theoretic control framework for Cyber-Physical Systems is presented. By resorting to set-theoretic ideas, an anomaly detector module and a control remediation strategy are formally derived with the aim to contrast cyber False Data Injection (FDI) attacks affecting the communication channels. The resulting scheme ensures Uniformly Ultimate Boundedness and constraints fulfillment regardless of any admissible attack scenario.

Traffic signals were originally standalone hardware devices running on fixed schedules, but by now, they have evolved into complex networked systems. As a consequence, traffic signals have become susceptible to attacks through wireless interfaces or even remote attacks through the Internet. Indeed, recent studies have shown that many traffic lights deployed in practice have easily exploitable vulnerabilities, which allow an attacker to tamper with the configuration of the signal. Due to hardware-based failsafes, these vulnerabilities cannot be used to cause accidents. However, they may be used to cause disastrous traffic congestions. Building on Daganzo's well-known traffic model, we introduce an approach for evaluating vulnerabilities of transportation networks, identifying traffic signals that have the greatest impact on congestion and which, therefore, make natural targets for attacks. While we prove that finding an attack that maximally impacts congestion is NP-hard, we also exhibit a polynomial-time heuristic algorithm for computing approximately optimal attacks. We then use numerical experiments to show that our algorithm is extremely efficient in practice. Finally, we also evaluate our approach using the SUMO traffic simulator with a real-world transportation network, demonstrating vulnerabilities of this network. These simulation results extend the numerical experiments by showing that our algorithm is extremely efficient in a microsimulation model as well.

Fully automated vehicles will require new functionalities for perception, navigation and decision making -- an Autonomous Driving Intelligence (ADI). We consider architectural cases for such functionalities and investigate how they integrate with legacy platforms. The cases range from a robot replacing the driver -- with entire reuse of existing vehicle platforms, to a clean-slate design. Focusing on Heavy Commercial Vehicles (HCVs), we assess these cases from the perspectives of business, safety, dependability, verification, and realization. The original contributions of this paper are the classification of the architectural cases themselves and the analysis that follows. The analysis reveals that although full reuse of vehicle platforms is appealing, it will require explicitly dealing with the accidental complexity of the legacy platforms, including adding corresponding diagnostics and error handling to the ADI. The current fail-safe design of the platform will also tend to limit availability. Allowing changes to the platforms, will enable more optimized designs and fault-operational behaviour, but will require initial higher development cost and specific emphasis on partitioning and control to limit the influences of safety requirements. For all cases, the design and verification of the ADI will pose a grand challenge and relate to the evolution of the regulatory framework including safety standards.

Content-Centric Networking (CCN) has emerged as a clean-slate future Internet architecture to address the challenges faced by traditional IP network, such as mobility, scalable content distribution and security. As a novel networking paradigm, CCN is built on named data, not host address and decouples the content from location. By the in-network caching, consumer can fetch the interested content from the closest routers.

Privacy and security have been discussed in many occasions and in most cases, the importance that these two aspects play on the information system domain are mentioned often. Many times, research is carried out on the individual information security or privacy measures where it is commonly regarded with the focus on the particular measure or both privacy and security are regarded as a whole subject. However, there have been no attempts at establishing a proper method in categorizing any form of objects of protection. Through the review done on this paper, we would like to investigate the relationship between privacy and security and form a break down the aspects of privacy and security in order to provide better understanding through determining if a measure or methodology is security, privacy oriented or both. We would recommend that in further research, a further refined formulation should be formed in order to carry out this determination process. As a result, we propose a Privacy-Security Tree (PST) in this paper that distinguishes the privacy from security measures.

Automatic detection of TV advertisements is of paramount importance for various media monitoring agencies. Existing works in this domain have mostly focused on news channels using news specific features. Most commercial products use near copy detection algorithms instead of generic advertisement classification. A generic detector needs to handle inter-class and intra-class imbalances present in data due to variability in content aired across channels and frequent repetition of advertisements. Imbalances present in data make classifiers biased towards one of the classes and thus require special treatment. We propose to use tree of perceptrons to solve this problem. The training data available for each perceptron node is balanced using cluster based over-sampling and TOMEK link cleaning as we traverse the tree downwards. The trained perceptron node then passes the original unbalanced data to its children. This process is repeated recursively till we reach the leaf nodes. We call this new algorithm as "Progressively Balanced Perceptron Tree". We have also contributed a TV advertisements dataset consisting of 250 hours of videos recorded from five non-news TV channels of different genres. Experimentations on this dataset have shown that the proposed approach has comparatively superior and balanced performance with respect to six baseline methods. Our proposal generalizes well across channels, with varying training data sizes and achieved a top F1-score of 97% in detecting advertisements.

Spear-phishing attacks pose a serious threat to sensitive computer systems, since they sidestep technical security mechanisms by exploiting the carelessness of authorized users. A common way to mitigate such attacks is to use e-mail filters which block e-mails with a maliciousness score above a chosen threshold. Optimal choice of such a threshold involves a tradeoff between the risk from delivered malicious emails and the cost of blocking benign traffic. A further complicating factor is the strategic nature of an attacker, who may selectively target users offering the best value in terms of likelihood of success and resulting access privileges. Previous work on strategic threshold-selection considered a single organization choosing thresholds for all users. In reality, many organizations are potential targets of such attacks, and their incentives need not be well aligned. We therefore consider the problem of strategic threshold-selection by a collection of independent self-interested users. We characterize both Stackelberg multi-defender equilibria, corresponding to short-term strategic dynamics, as well as Nash equilibria of the simultaneous game between all users and the attacker, modeling long-term dynamics, and exhibit a polynomial-time algorithm for computing short-term (Stackelberg) equilibria. We find that while Stackelberg multi-defender equilibrium need not exist, Nash equilibrium always exists, and remarkably, both equilibria are unique and socially optimal.

Compared to conventional general-purpose processors, accelerator-rich architectures (ARAs) can provide orders-of-magnitude performance and energy gains. In this paper we design and implement the ARAPrototyper to enable rapid design space explorations for ARAs in real silicons and reduce the tedious prototyping efforts. First, ARAPrototyper provides a reusable baseline prototype with a highly customizable memory system, including interconnect between accelerators and buffers, interconnect between buffers and last-level cache (LLC) or DRAM, coherency choice at LLC or DRAM, and address translation support. To provide more insights into performance analysis, ARAPrototyper adds several performance counters on the accelerator side and leverages existing performance counters on the CPU side. Second, ARAPrototyper provides a clean interface to quickly integrate a user?s own accelerators written in high-level synthesis (HLS) code. Then, an ARA prototype can be automatically generated and mapped to a Xilinx Zynq SoC. To quickly develop applications that run seamlessly on the ARA prototype, ARAPrototyper provides a system software stack and abstracts the accelerators as software libraries for application developers. Our results demonstrate that ARAPrototyper enables a wide range of design space explorations for ARAs at manageable prototyping efforts and 4,000 to 10,000X faster evaluation time than full-system simulations. We believe that ARAPrototyper can be an attractive alternative for ARA design and evaluation.

Information security management is time-consuming and error-prone. Apart from day-to-day operations, organizations need to comply with industrial regulations or government directives. Thus, organizations are looking for security tools to automate security management tasks and daily operations. Security Content Automation Protocol (SCAP) is a suite of specifications that help to automate security management tasks such as vulnerability measurement and policy compliance evaluation. SCAP benchmark provides detailed guidance on setting the security configuration of network devices, operating systems, and applications. Organizations can use SCAP benchmark to perform automated configuration compliance assessment on network devices, operating systems, and applications. This paper discusses SCAP benchmark components and the development of a SCAP benchmark for automating Cisco router security configuration compliance.

Despite the growing promotion of the “open data” movement, the collection, cleaning, management, interpretation, and dissemination of open data is laborious and cost intensive, particularly for non-profits with limited resources. In this paper, we describe how non-profit organizations (NPOs) use open data, building on prior literature that focuses on understanding challenges that NPOs face. Based on 15 interviews of staff from 10 NPOs, our results suggest that NPOs use data to develop narratives to build a case for support from grantors and other stakeholders. We then present empirical results based on the usage of a data portal we created, which suggests that technologies should be designed to not only make data accessible, but also to facilitate communication and support relationships between expert data analysts and NPOs.

In this paper, we propose a novel Social Networking Service (SNS) for a regional community. The purpose of the SNS is to support and encourage people by making them aware beneficial social relations in the real world. The conventional SNSs can hardly deal with beneficial social relations, because they are implicit and dynamic. The proposed SNS is designed to provide positive information for two types of people: people who does community voluntary works, such as cleaning, as contributors, and people who receives benefit from them as beneficiary. This paper introduces the basic scheme based on the SNS for beneficial social relations, and evaluates the effectiveness of our scheme based on the result of the experimental studies. The experimental result shows the users of our SNS tend to consider the information about the voluntary works valuable if they have been performed in their living area, and it suggests that our proposed SNS system would work well in a regional community.

Staging is a program generation paradigm with a clean, well-investigated semantics which statically ensures that the generated code is always well-typed and well-scoped. Staging is often used for specializing programs to the known properties or parts of data to improve efficiency, but so far it has been limited to generating terms. This short paper describes our ongoing work on extending staging, with its strong safety guarantees, to generation of non-terms, focusing on ML-style modules. The purpose is to map out the promises and challenges, then to pose a question to solicit the community's expertise in evaluating how essential our extensions are for the purpose of applying staging beyond the realm of terms. We demonstrate our extensions' use in specializing functor applications to eliminate its (currently large) overhead in OCaml. We explain the challenges that those extensions bring in and identify a promising line of attack. Unexpectedly, however, it turns out that we can avoid module generation altogether by representing modules, possibly containing abstract types, as polymorphic records. With the help of first-class modules, module specialization reduces to ordinary term specialization, which can be done with conventional staging. The extent to which this hack generalizes is unclear. Thus we have a question to the community: is there a compelling use case for module generation? With these insights and questions, we offer a starting point for a long-term program in the next stage of staging research.

In Pixar's Finding Dory, we are introduced to a new character: Hank the Octopus. This is a very different character than Pixar has been asked to animate before. Our directors demanded both precise control and graceful, clean silhouettes. The reference artwork we were given showed complex curves between arms and body without any disjointed shapes or breaks in form. Video of Octopus in motion reveals an infinitely malleable creature capable of an enormous shape language. This art direction required a small group of TDs to create a control scheme that was sensible, flexible and with a new level of control in order for animators to bring Hank to life. We had to think deeply from the tips of the fingers all the way through how the tentacles connect to the mouth corners, and eye sockets. Each of this issues raised concerns around design, deformation and finally how the end user can manipulate such complexity effectively.