2013 technical reports

A Decision Making Model for Collaborative Malware Detection Networks

Carol J. Fung, Disney Y. Lam, and Raouf Boutaba

The increased sophistication and evasiveness of malware has brought tremendous challenges to vendors of antivirus systems. Various malware detection approaches have been proposed and deployed to detect and remove malware. However, it is challenging for a single security vendor to analyze all malware and to provide up-to-date protection, e.g., a signature database. In this paper, we investigate the effectiveness of collaboration amongst various antivirus systems and propose a distributed collaborative malware detection network (CMDN). We design a novel collaborative malware detection decision model, RevMatch, where collaborative malware detection decisions are made based on the scanning history with multiple antivirus systems. We evaluate our system on realworld malware data sets and show that collaborative malware detection
techniques can improve detection accuracy significantly. Furthermore, RevMatch outperforms existing decision models in terms of detection quality, runtime efficiency, and robustness against insider attacks.

April 12, 2013

A Decision Making Model for Collaborative Malware Detection Networks (PDF)

Runtime Verification with Controllable Time Predictability and Memory Utilization

Ramy Medha, Deepak Kumar, Borzoo Bonakdarpour and Sebastian Fischmeister

 (The goal of runtime verification is to inspect the well-being
of a system by employing a monitor during its execution.
Such monitoring imposes costs in terms of resource utiliza-
tion. Memory usage and predictability of the monitor invo-
cations are among the indicators of the quality of a moni-
toring solution, especially in the context of embedded sys-
tems. In this paper, we propose a novel control-theoretic
approach for co-ordinating time predictability and memory
utilization in runtime monitoring of real-time embedded sys-
tems. In particular, we design a PID controller and four
fuzzy controllers with different optimization control objec-
tives. Our approach controls the frequency of when the mon-
itor should be invoked by incorporating a bounded memory
buffer that stores events that need to be monitored. The
controllers attempt to improve time predictability and max-
imize memory utilization, while ensuring the soundness of
the monitor simultaneously. Unlike the existing approaches
based on static analysis, our approach is highly scalable and
well-suited for reactive systems that are required to react to
stimuli from the environment in a timely fashion. Our thor-
ough experiments using two case studies (a laser beam stabi-
lizer for aircraft tracking, and a Bluetooth mobile payment
system) demonstrate the advantages of using controllers to
achieve low variation in the frequency of monitor invoca-
tions, while maintaining maximum memory utilization in
highly non-linear environments.

May 16, 2013

Runtime Verification with Controllable Time Predictability and Memory Utilization (PDF)

Affect Control Processes: Probabilistic and Decision Theoretic Affective Control in Human-Computer Interaction

Jesse Hoey, Tobias Schröder and Areej Alhothali

Affect Control Theory is a mathematical representation of the interactions between two persons, in which it is posited that people behave in a way so as to minimize the amount of
defection between their cultural emotional sentiments and the transient emotional sentiments that are created by each
situation. Affect control theory presents a maximum likelihood solution in which optimal behaviours or identities can be predicted based on past interactions. Here, we formulate a probabilistic and decision theoretic model of the same underlying principles, and show this to be a generalization of
the basic theory. The new model, called BayesAct, is more expressive than the original theory, as it can maintain multiple hypotheses about behaviours and identities simultaneously as a probability distribution, and can make value-directed action choices. This allows the model to generate affectively believable interactions with people by learning about their identity, predicting their behaviours, and taking actions that are simultaneously goal-directed and a
ffect-sensitive. We demonstrate this generalisation with a set of simulations. We then show how our model can be used as an emotional
\plug-in" for systems that interact with humans. We demonstrate human-interactive capability by eliciting knowledge from 37 participants with a survey, and then using this knowledge to build a simple demonstrative intelligent tutoring application. We present results from a pilot study with 20 participants using the application.

June 21, 2013

Affect Control Processes: Probabilistic and Decision Theoretic Affective Control in Human-Computer Interaction (PDF)

Improved Visualization of Relational Logic Models

Atulan Zaman, Iman Kazerani, Medha Patki, Bhargava Guntoori, Derek Rayside

The Alloy Analyzer includes a visualizer tool for presenting counter-examples to the user. This visualizer tool contains a wide array of settings and a "Magic Layout" feature to automatically infer values for these settings based on a static analysis of the specification being visualized.  We improve both the visualizer itself and the Magic Layout feature.  For example, expert users often use colour to distinguish changes of state when visualizing specifications of dynamic systems, but previously Magic Layout was not sophisticated enough to infer where state changes might be represented in the specification.  We have also improved the way in which the visualizer distinguishes different but related types of atoms, as well improved the visual consistency between different frames of a projection.  Finally, a quantitative evaluation is done to compare how much better the new inferred theme compares to the default theme, and a qualitative evaluation of how the inferred theme compares to the expert made themes.

August 27, 2013

Improved Visualization of Relational Logic Models (PDF)

Zone-based Synthesis of Timed Models with Strict Phased Fault Recovery

Fathiyeh Faghih and Borzoo Bonakdarpour

In this paper, we focus on efficient synthesis of fault-tolerant timed models from their fault-intolerant version. Although the complexity of the synthesis problem is known to be polynomial time in the size of the time-abstract bisimulation of the input model, the state of the art currently lacks synthesis algorithms that can be efficiently implemented.We propose an algorithm that takes a timed automaton, a set of fault actions, and a set of safety and bounded-time response properties as input, and utilizes a space-efficient symbolic representation of the timed automaton (called the zone graph) to synthesize a fault-tolerant timed automaton as output. The output automaton satisfies strict phased recovery, where it is guaranteed that
the output model behaves similarly to the input model in the absence of faults and in the presence of faults, fault recovery is achieved in two phases, each satisfying certain safety and timing constraints. Our algorithm is fully implemented and we
report encouraging experimental results.

July 25, 2013

Zone-based Synthesis of Timed Models with Strict Phased Fault Recovery (PDF)

Generating Multiple Diverse Counterexamples for an EFSM

Alma L. Juarez Dominguez and Nancy A. Day

Model checking is a powerful technique for debugging a system description because it generates a counterexample showing a path of the system that fails a property. Instead of the traditional cycle of find bug –fix bug – re-run model checker, often we would like to study multiple bugs before fixing the model to help isolate the cause of the error and to improve the user’s experience by avoiding iterations of this cycle. However, the set of all counterexamples is often too large to generate or comprehend, and several counterexamples may be caused by the same error.We present a novel method of using a model checker to generate a set of diverse counterexamples to an invariant of an extended finite state machine (EFSM) model. The goal is that each diverse counterexample reveals distinct information about a bug in the model. We use the modelling abstractions of control states and transitions of an EFSM to define whether two counterexamples are equivalent or not. Our method reduces the set of counterexamples on-the-fly and can be used with any LTL model checker.

September 6, 2013

Generating Multiple Diverse Counterexamples for an EFSM (PDF)

Dynamic Sum-Product Networks

Mazen Melibari, Pascal Poupart, Edward Lank

Inference in dynamic graphical models is known to be hard, except for models with low treewidth structure. This restricts severely the expressive power of these kinds of models. In this document we are proposing a new type of dynamic graphical model that allows one to model complex stochastic processes with unbounded treewidth while guaranteeing tractable exact inference. The proposed dynamic model is an extension of a relatively new graphical model, named Sum-Product Network, that was introduced in 2011. The document also discusses the plan to develop a Bayesian non-parametric version of the model and an application in the area of activity recognition.

September 12, 2013

Dynamic Sum-Product Networks (PDF)

Implicit Surfaces Seminar, Spring 2012

Khodakhast Bibak, Chun Liu, Hamideh Vosoughpour, Grace Yao, Zainab AlMeraj, Alex Pytel,William Cowan and Stephen Mann

Implicit surfaces are one technique for surface modelling in computer graphics.In this report, we survey some implicit surface papers, present some projects using implicit surfaces, and give our evaluation of this work.

September 25, 2013

Implicit Surfaces Seminar, Spring 2012 (PDF)

A Study of Two Implicit Data Interpolation Schemes

 Stephen Mann

Implicit surfaces are one technique for surface modelling in computer graphics. The are several implicit surface schemes to
interpolate point data. In this report, I study two schemes, one by Turk and O’Brien, the other by Shen, and test how well they
work. Further, although Shen derives a linear version of his scheme, he only implemented a constant version. In this report, I
implemented and tested the constant and linear variations of Shen’s scheme.

September 25, 2013

A Study of Two Implicit Data Interpolation Schemes (PDF)

chameleondb: a WorkloadAware Robust RDF Data Management System

Güneş Aluç, M. Tamer Özsu, Khuzaima Daudjee and Olaf Hartig

The Resource Description Framework (RDF) is a World Wide Web Consortium (W3C) standard for the conceptual modelling of web resources, and SPARQL is the standard query language for RDF. As RDF is becoming more widely utilized, RDF data management systems are being exposed to workloads that are much more diverse and dynamic than they were designed to support, for which they are unable to provide consistently good performance. The problem arises because these systems are workload-agnostic; that is, they rely on a database structure and types of indexes that are fixed a priori, which cannot be modified at runtime.

In this paper, we introduce chameleon-db, which is a workload-aware RDF data management system that we have developed. chameleon-db automatically and periodically adjusts its layout of the RDF database to optimize for queries so that they can be executed efficiently. Since one cannot afford to stop processing queries, we propose a novel design that enables partitions to be concurrently updated. We demonstrate that chameleon-db can achieve robust performance across a diverse spectrum of query workloads, outperforming its competitors by up to two orders of magnitude, and that it can easily adapt to changing workloads.

Sept 27, 2013

chameleondb: a WorkloadAware Robust RDF Data Management System (PDF)

Latency Amplification: Characterizing the Impact of Web Page Content on Load Times

Catalin Avram, Kenneth Salem, Bernard Wong

Web users like sites that load quickly. Longer web page load times translate to reduced user satisfaction and loss of revenue and mindshare. The time required to load a given web page is difficult to predict because it is a complex function of many factors, such as the latencies associated with the network requests used to retrieve that content from remote servers.   However, one of the most important factors is the page content, including the scripts, images, style sheets and other objects that are present on the page.  In this paper we propose a simple metric for characterizing the content of a web page in terms of its impact on page loading times.   This metric, called the latency amplification factor (LAF), characterizes the content of a web page in terms of how it affects the page load time.   The LAF of a web page can be estimated quickly and easily, and we describe a lightweight method for doing so.  In addition, we propose an extended version of the basic LAF metric, called CLAF, that relates page load time to underlying request latencies in the presence of content delivery networks.  We estimated LAFs for a variety of popular web sites, and found that they varied substantially. To validate our approach for estimating LAFs, we compared estimated LAFs against measured LAFs and found that our methodology, though simple, gave reasonably accurate estimates.

October 1, 2013

Latency Amplification: Characterizing the Impact of Web Page Content on Load Times (PDF)

pWeb: A P2P Web Hosting Framework

Reaz Ahmed, Md. Faizul Bari, Raouf Boutaba, Shihabur R Chowdhury, Bertrand Mathieu, and Alexander Pokluda

In recent years, we have seen a major shift in the dominant computing platforms used by Internet users. Mobile computing platforms such as smartphones are quickly becoming the primary way many Internet users connect to the web. Furthermore, increasingly more web content is produced and consumed by these devices. This paper introduces pWeb, a novel peer-to-peer web hosting framework that aims to keep content near its point of production and consumption. pWeb will tap into the explosion of resources offered by these mobile devices as well as other Internet connected devices such as set-top boxes, home gateways, etc. that are also sharply increasing in number. In addition to benefiting end-users, pWeb also has the potential to benefit Internet Service Providers by reducing the amount of inter-AS traffic. pWeb is supported by our industry partners, Bell Canada Enterprises, Inc.and Orange Labs, and builds on our previous work on naming,routing and searching in peer-to-peer networks.

October 09, 2013

pWeb: A P2P Web Hosting Framework (PDF)

Advanced pWeb Features

Md. Faizul Bari, Shihabur Rahman Chowdhury, Alexander Pokluda, Reaz Ahmed, and Raouf Boutaba

This technical report describes five crucial components of pWeb. First, we give a review of the pWeb system architecture in Part I; second, we explain the architecture and design components of our file system in Part II; third, we describe how peers host and access dynamic content using light-weight HTTP servers and client-side scripts in Part III; forth, we present XML data management and access capabilities in Part IV; and finally, we conclude by providing a demo of our client software implementation in Part V.

October 9, 2013

Advanced pWeb Features (PDF)

On the Hyperspectral Modelling of Light Interaction with Human Skin

T. Francis Chen, Gladimir V. G. Baranoski, Bradley Kimmel, Erik Miranda

The exploration of the hyperspectral domain offers a host of new research and application possibilities in terms of material appearance modelling. In this paper, we address these prospects with respect to human skin, one of the most ubiquitous materials portrayed in synthetic imaging. We present a novel hyperspectral skin appearance model that takes into account the optical and structural characteristics of this complex organ as well as the particle nature of its main light-attenuation agents to enable the predictive rendering of its appearance attributes in the ultraviolet, visible and infrared regions of the light spectrum. Accordingly, it has a broad scope of applications involving hyperspectral skin imaging for entertainment, aesthetic, educational and biomedical purposes. The predictions of the proposed model are quantitatively and qualitatively evaluated through comparisons with measured data. In addition, its effectiveness is further illustrated through the generation of images depicting distinct trends in the variation of skin appearance attributes detected under visible and non-visible light.

December 19, 2014

On the Hyperspectral Modelling of Light Interaction with Human Skin (PDF)

pWeb Peer-to-Peer Web Hosting Communication System and Dynamic Web Hosting

Alexander Pokluda, Abdalla Aartail, Md. Faizul Bari, Reaz Ahmed, and Raouf Boutaba

During the main phase of this project we identified and provided solution for the major challenges related to peer-to-peer (P2P) web hosting. More specifically, our solutions for naming, availability, ranking, indexing and dynamic web-hosting have been provided in previous reports. In this report we present a more concrete view of the pWeb infrastructure and address the issues related to a real-life deployment of the system.

First we provide an overview of the light-weight P2P communication protocol between pWeb clients for signaling and media streaming in Part~I. In Part~II we provide an architectural overview of pWeb system and show the mapping of the abstract components in pWeb architecture to real life devices and technologies. In order to make pWeb compatible with the existing web technology we have developed a DNS gateway. In Part~II Section~\ref{s:dnsgw}, we provide the design and implementation of this DNS gateway. For efficient indexing and fast discovery of end-user devices and multimedia content, we have developed a cloud-based solution for crawling, indexing and searching. We present this component in Part~II  section~\ref{s:crawler}.

As the project evolved, we felt the necessity of developing a working application prototype to demonstrate the effectiveness of the proposed architecture. Hence, we developed a Android application to capture and host videos from end user devices. Although this was not an original goal of this extension, we are including the design and implementation of this application in Part~III of this report. We also present the installation and usage guides for various components in the pWeb architecture in Appendix~A and Appendix~B.

October 9, 2013

pWeb Peer-to-Peer Web Hosting Communication System and Dynamic Web Hosting (PDF)

Using Storage to Minimize Carbon Footprint of Diesel Generators for Unreliable Grids

Sahil Singla, Yashar Ghiassi-Farrokhfal, and Srinivasan Keshav

Although modern society is critically reliant on power grids, even modern power grids are subject to unavoidable outages. The situation in developing countries is even worse, with frequent load shedding lasting several hours a day due to a large power supply- demand gap. The standard solution for residences is, therefore, to backup grid power with local generation from a diesel generator (genset). When carbon emission matters, a hybrid battery-genset is preferable to a genset only system. Designing such a hybrid system is entangled with the tradeoff between cost and carbon emission. Towards the analysis of such a hybrid system, we first compute the minimum required battery size for eliminating the use of genset. Such a battery must guarantee a target loss of power probability for an unreliable grid. We then compute the minimum required battery for a given genset and a target allowable carbon footprint. Drawing on recent results, we model both problems as buffer sizing problems that can be addressed
using stochastic network calculus. Specifically, a numerical study shows that, for a neighbourhood of 100 homes, we are able to estimate the carbon footprint reduction, compared to an exact numerical analysis, within a factor of 1:7.

November 27, 2013

Using Storage to Minimize Carbon Footprint of Diesel Generators for Unreliable Grids (PDF)

Live API Documentation

Siddharth Subramanian, Laura Inozemtseva and Reid Holmes

Application Programming Interfaces (APIs) provide powerful
abstraction mechanisms that enable complex functionality
to be used by client programs. However, this abstraction
does not come for free: understanding how to use an API can
be difficult. While API documentation can help, it is often
insufficient on its own. Online sites like Stack Overflow and
Github Gists have grown to fill the gap between traditional
API documentation and more example-based resources. Un-
fortunately, these two important classes of documentation
are independent.

In this paper we describe an iterative, deductive method
of linking source code examples to API documentation. We
also present an implementation of this method, called Baker,
that is highly precise (0.97) and supports both Java and
JavaScript. Baker can be used to enhance traditional API
documentation with up-to-date source code examples; it can
also be used to incorporate links to the API documentation
into the code snippets that use the API

November 21, 2013

Live API Documentation (PDF)

Towards a Realistic Performance Analysis of Storage Systems in Smart Grids

Y. Ghiassi-Farrokhfal, S. Keshav and C. Rosenberg

Energy storage devices (ESDs) such as lithium-ion batteries and flywheels have the potential to revolutionize the electricity grid by allowing the smoothing of variable-energy generator output, and
the time-shifting of demand away from peak times. Numerous recent investigations have studied the impact of ESDs on energy systems, but usually by assuming ideal ESD behaviour, such as infinite ESD charging and discharging rates, and zero self-discharge. However, real-life ESDs are far from ideal. We
investigate the effect of non-ideal ESD behaviour on system performance, presenting an analytical ESD model that retains much of the simplicity of an ideal ESD, yet captures many (though not all) non-ideal behaviours. This allows us to compute performance bounds for systems using non-ideal ESDs using
standard teletraffic techniques. We provide performance results for five widely used ESD technologies and show that our models can closely approximate numerically computed performance bounds.

December 2, 2013

Towards a Realistic Performance Analysis of Storage Systems in Smart Grids (PDF)

Unsupervised Bayesian Learning of HMM Transition Parameters by Moment Matching

Farheen Omar and Pascal Poupart

Hidden Markov Models (HMMs) provide a simple framework to model the generative process of some types of sequential of data. We consider the challenging problem of estimating the parameters of an HMM incrementally by doing a constant amount of computation per observation. We propose an online moment matching algorithm for Bayesian learning of transition parameters of an HMM. While moment matching suggests that learning is done approximately, we show that the algorithm performs exact Bayesian learning for an implicit prior. The algorithm exploits the fact that only the first, second and third order moments of the prior need to be specified before any data is observed. After each observation, moment matching implicitly specifies additional moments in the prior. Hence, the algorithm specifies the moments of the prior incrementally as they become needed in the computation. Therefore the overall computation is exact with respect to the resulting prior. The algorithm performs a constant amount of computation per observation in contrast to other methods such as naive exact Bayesian learning where the computation grows exponentially and Gibbs Sampling where an approximate solution is obtained after multiple iterations. We demonstrate the performance of the algorithm by comparing it to exact Bayesian Learning and Gibbs Sampling onsynthetic data as well as real data for HMMs that arise in activity recognition

October 30, 2013

Unsupervised Bayesian Learning of HMM Transition Parameters by Moment Matching (PDF)

Real-Time Distributed Control for Smart Electric Vehicle Chargers: From a Static to a Dynamic Study

Omid Ardakanian, S. Keshav, and Catherine Rosenberg

At high penetrations, uncontrolled electric vehicle (EV) charging has the potential to cause line and transformer congestion in the distribution network. Instead of upgrading components to higher nameplate ratings, we investigate the use of real-time control to limit EV load to the available capacity in the network. Inspired by rate control algorithms in computer networks such as TCP, we design a measurement-based, real-time, distributed, stable, efficient, and fair charging algorithm using the dual-decomposition approach. We show through extensive numerical simulations and power flow analysis on a test distribution network that this algorithm operates successfully in both static and dynamic settings, despite changes in home loads and the number of connected EVs. We find that our algorithm rapidly converges from large disturbances to a stable operating point. We show that in a test setting, for an acceptable level of overload, only 70 EVs could be fully charged without control, whereas up to around 700 EVs can be fully charged using our control algorithm. This compares well with the maximum supportable population of approximately 900 EVs. Our work also provides engineering guidelines for choosing the control parameters and setpoints in a distribution network.

November 6, 2013

Real-Time Distributed Control for Smart Electric Vehicle Chargers: From a Static to a Dynamic Study (PDF)