This paper presents a novel covert timing channel (CTC) that enables a malicious entity to exfiltrate data from a benign cloud FPGA user without requiring dedicated outgoing messages from the cloud FPGA, minimizing the detection risk by both the victim and the cloud service provider. The proposed CTC exploits the handshake signals of the Advanced eXtensible Interface (AXI) protocol and interpacket delay of the Internet to establish the CTC from a cloud FieldProgrammable Gate Array (FPGA) to an off-cloud computer. This paper analyzes the bit-error rate (BER) of the AXI-based CTC under varying conditions and demonstrates its effectiveness in truly enabling remote power analysis attacks on cloud services, such as Amazon Web Services Elastic Compute Cloud (AWS EC2). The proposed CTC achieves a BER as low as 0.01988%.

Chromatic derivatives (CDs) and associated chromatic approximations (CAs) provide a numerically robust and powerful framework for digital processing of continuous-time/space signals, using not only the discrete signal amplitudes, but also higher order derivatives. Acquisition of CDs has so far been limited to software implementations. This paper presents field-programmable gate array (FPGA)-based digital hardware architectures suitable for the real-time acquisition of CDs, thus enabling CDs to be used for practical signal processing algorithm development in embedded systems. With 24 bits of fixed-point precision, the proposed hardware architectures provide approximate 116 dB accuracy in the frequency responses of FIR filters capturing the CDs, and 76.85 dB and 75.09 dB accuracy in signal reconstruction with synthetic and real audio signals using CDs up to order 28 degrees. The designs have been verified on an AMD Kintex UltraScale KCU105 FGPA device using bit-true cycle-accurate hardware co-simulation.

In equity investment management, sell side analysts serve an important role in forecasting metrics of companies’ financial performance. These estimates are often produced in an opaque manner, namely, the process upon which the estimate is initiated or revised is not directly observable. With multiple analysts covering the same company, and an analyst covering multiple companies, we have an n-m relationship. The systematic capture of analyst estimates provide a systematic and quantitative proxy for market sentiment. Thus far the academic literature analysing this dataset has resolved to use relatively simple methods for aggregating the individual estimates to arrive at a consensus estimate.In this paper we propose a novel method for aggregating analyst estimates utilising iterative filtering algorithms. This work is inspired by applications of such classes of algorithms to the robust aggregation of sensor network data and online reviews. We conduct experiments using real-world datasets to demonstrate the efficacy of this approach. The results suggest iterative filtering methods improve upon the forecast accuracy of the consensus forecast compared to the simple mean consensus.

Social rating systems are widely used for gathering user feedbacks on the quality of products, items, and services. Social rating systems accept various forms of numeric and non-numeric recommendations as input to their aggregation algorithm. Fuzzy recommendations, as one form of input recommendations, while common in areas such as stock market and educational systems, are challenging in terms of aggregation and scaling. Also, taking into account trust and experience of raters while aggregating fuzzy variables is another challenge that needs investigations. In this article, we propose a trust-based experience-aware method for aggregation of fuzzy recommendations. We propose to use trust and experience of raters along with the area under the curve of the membership of the fuzzy recommendations to compute a weight for recommendations. Then, we present an iterative algorithm to aggregate these computed weighted recommendations. We evaluate our method using a real-world dataset and compare its performance with three well-known iterative algorithms. The comparison results show the superiority of our method over other related approaches.

A method for acquisition of high bandwidth signals is presented as a typical example of a signal processing application of chromatic derivatives and approximations. Chromatic derivatives are numerically robust differential operators based on orthogonal polynomials. Theoretical formulations required for synthesising an analog chromatic derivative filterbank based on all-pass filters is presented. Such an analog filterbank with N +1 filters can be used for digital acquisition of high bandwidth signals by simultaneously sampling the outputs of the filterbank at a rate 2/(N + 1) of the Nyquist rate, resulting in samples of the signal and higher order chromatic derivatives up to order N, which in turn are used to reconstruct the original signal back. The value of the signal at any instant is obtained from only two nearest samples of the chromatic derivatives filterbank.

Authorization or access control limits the actions a user may perform on a computer system, based on predetermined access control policies, thus preventing access by illegitimate actors. Access control for the Internet of Things (IoT) should be tailored to take inherent IoT network scale and device resource constraints into consideration. However, common authorization systems in IoT employ conventional schemes, which suffer from overheads and centralization. Recent research trends suggest that blockchain has the potential to tackle the issues of access control in IoT. However, proposed solutions overlook the importance of building dynamic and flexible access control mechanisms. In this paper, we design a decentralized attribute-based access control mechanism with an auxiliary Trust and Reputation System (TRS) for IoT authorization. Our system progressively quantifies the trust and reputation scores of each node in the network and incorporates the scores into the access control mechanism to achieve dynamic and flexible access control. We design our system to run on a public blockchain, but we separate the storage of sensitive information, such as user’s attributes, to private sidechains for privacy preservation. We implement our solution in a public Rinkeby Ethereum test-network interconnected with a lab-scale testbed. Our evaluations consider various performance metrics to highlight the applicability of our solution for IoT contexts.

Side channel analysis attacks employ the emanated side channel information to deduce the secret keys from cryptographic implementations by analyzing the power traces during execution or scrutinizing faulty outputs. To be effective, a countermeasure must remove or conceal as many as possible side channels. However, many of the countermeasures against side channel attacks are applied independently. In this article, the authors present a novel countermeasure (referred to as QuadSeal ) against Power Analysis Attacks and Electromagentic Fault Injection Attacks (FIAs), which is an extension of the work proposed in Reference [27]. The proposed solution relies on algorithmically balancing both Hamming distances and Hamming weights (where the bit transitions on the registers and gates are balanced, and the total number of 1s and 0s are balanced) by the use of four identical circuits with differing inputs and modified SubByte tables. By randomly rotating the four encryptions, the system is protected against variations, path imbalances, and aging effects. After generating the ciphertext, the output of each circuit is compared against each other to detect any fault injections or to correct the faulty ciphertext to gain reliability. The proposed countermeasure allows components to be switched off to save power or to run four executions in parallel for high performance when resistance against power analysis attacks is not of high priority, which is not available with the existing countermeasures (except software based where source code can be changed). The proposed countermeasure is implemented for Advanced Encryption Standard (AES) and tested against Correlation Power Analysis and Mutual Information Attacks attacks (for up to a million traces), and none of the secret keys was found even after one million power traces (the unprotected AES circuit is vulnerable for power analysis attacks within 5,000 power traces). A detection circuit (referred to as C-FIA circuit) is operated using the algorithmic redundancy presented in four circuits of QuadSeal to mitigate Electromagnetic Fault Injection Attacks. Using Synopsys PrimeTime, we measured the power dissipation of QuadSeal registers and XOR gates to test the effectiveness of Quadruple balancing methodology. We tested the QuadSeal countermeasure with C-FIA circuit against Differential Fault Analysis Attacks up to one million traces; no bytes of the secret key were found. This is the smallest known circuit that is capable of withstanding power-based side channel attacks when electromagnetic injection attack resistance, process variations, path imbalances, and aging effects are considered.

Approximate integer dividers suffer from unreasonably high worst-case relative errors (such as 50% or 100%), which can adversely affect the application-level output. In this paper, we propose WEID, which is a novel lightweight method to improve the worst-case relative errors in approximate integer dividers. We first present an in-depth analysis to gain insights into the cause of the high worst-case relative error. Based on our insights, we propose a novel method to detect when an error occurs in an approximate divider, and modify the output to reduce the error. Further, we present the hardware realization of WEID method and demonstrate that it can be generically coupled with several state-of-the-art approximate dividers. Our results show that for 32-by-16 dividers, WEID reduces worstcase relative errors from 100% to ~20%, while still achieving ~80% and ~70% reduction in delay and energy compared to an accurate array divider.

We propose a new error-configurable approximate unsigned integer multiplier named REALM. It incorporates a novel error-reduction method into the classical approximate log-based multiplier. Each power-of-two-interval of the input operands is partitioned into M×M segments, and an error-reduction factor for each segment is analytically determined. These error-reduction factors can be used across any power-of-two-interval, so we quantize only M2factors and store them in the form of read-only hardwired lookup tables to keep the resource overhead to a minimum. Error characterization of REALM shows that it achieves very low error bias (mostly ≤0.05%), along with lower mean error (from 0.4% to 1.6%), and lower peak error (from 2.08% to 7.4%) than the classical approximate log-based multiplier and its state-of-the-art derivatives (mean errors ≥2.6% and peak errors ≥7.8%). Synthesis results using TSMC 45nm standard-cell library show that REALM enables significant power-efficiency (66% to 86% reduction) and area-efficiency (50% to 76% reduction) when compared with the accurate integer multiplier. We show that REALM produces Pareto optimal design trade-offs in the design space of state-of-the-art approximate multipliers. Application-level evaluation of REALM demonstrates that it has negligible effect on the output quality.

Multiprocessor System-on-Chip (MPSoC) has become necessary due to the the billions of transistors available to the designer, the need for fast design turnaround times, and the power wall. Thus, present embedded systems are designed with MPSoCs, and one possible way MPSoCs can be realized is through Pipelined MPSoC (PMPSoC) architectures, which are used in applications from video surveillance to cryptosystems. Hardware Trojans (HTs) on PMPSoCs are a significant concern due to the damage caused by their stealth. An adversary could use HTs to extract secret information (data leakage) to modify functionality/data (functional modification) or make PMPSoCs deny service. In this article, we present PMPGuard, a mechanism that (1) detects the presence of hardware Trojans in Third Party Intellectual Property (3PIP) cores of PMPSoCs by continuous monitoring and testing and (2) recovers the system by switching the infected processor core with another one. We designed, implemented, and tested the system on a commercial cycle accurate multiprocessor simulation environment. Compared to the state-of-the-art system-level techniques that use Triple Modular Redundancy (TMR) and therefore incur at least 3× area and power overheads, our proposed system incurs about 2× area and 1.5× power overheads without any adverse impact on throughput.

Random execution time-based countermeasures against power analysis attacks have reduced resource overheads when compared to balancing power dissipation and masking countermeasures. The previous countermeasures on randomization use either a small number of clock frequencies or delays to randomize the execution. This paper presents a novel random frequency countermeasure (referred to as RFTC) using the dynamic reconfiguration ability of clock managers of Field-Programmable Gate Arrays -- FPGAs (such as Xilinx Mixed-Mode Clock Manager -- MMCM) which can change the frequency of operation at runtime. We show for the first time how Advanced Encryption Standard (AES) block cipher algorithm can be executed using randomly selected clock frequencies (amongst thousands of frequencies carefully chosen) generated within the FPGA to mitigate power analysis attack vulnerabilities. To test the effectiveness of the proposed clock randomization, Correlation Power analysis (CPA) attacks are performed on the collected power traces. Preprocessing methods, such as Dynamic Time Warping (DTW), Principal Component Analysis (PCA) and Fast Fourier Transform (FFT), based power analysis attacks are performed on the collected traces to test the effective removal of random execution. Compared to the state of the art, where there were 83 distinct finishing times for each encryption, the method described in this paper can have more than 60,000 distinct finishing times for each encryption, making it resistant against power analysis attacks when preprocessed and demonstrated to be secure up to four million traces.

We present a Hardware Trojan (HT) detection, identification and recovery mechanism for Multiprocessor Systems on Chips (MPSoCs). Our method utilizes on-line testing to mitigate the effects of hardware Trojans in a computing system using a Hardware Security Monitor (HSM), a trusted hardware module, and an On-line Test Procedure (OTP), a software module. The proposed approach focuses on mitigating hardware Trojans with a permanent impact on the computing system and enables MPSoCs to continue functioning in the presence of the hardware Trojans. We have successfully validated the proposed method by implementing known hardware Trojans from Trust-Hub on a Xilinx ML605 FPGA. The implementation incurred 4.5% area and 9.1% execution time overheads for a set of benchmark applications. Compared to the state of the art, the proposed mechanism's area and power overheads are significantly lower while the execution time overhead is slightly higher. State of the art systems utilizing differing cores have been shown to be effective in simulation environments, while the proposed mechanism has been implemented in FPGAs to illustrate that such a system can be realized in hardware.

Power-based side channel attacks are effective in revealing the secret keys of cryptographic algorithm implementations running on soft processor systems. This paper, for the first time, proposes a clock random execution methodology (referred to as SCRIP) to execute a soft processor core and most of the components (some components cannot be executed with a random clock frequency). An open source soft processor system (LowRISC which is based on the RISC-V Instruction Set Architecture) has been executed with the proposed SCRIP clock random execution methodology. Power analysis attacks (including preprocessing techniques to remove the effects of random execution) were carried out against the SCRIP LowRISC soft processor implementation to test the effects of random clock execution. SCRIP LowRISC implementation is shown to be secure for up to 300,000 encryptions, while the LowRISC implementation without SCRIP revealed the secret key within 1,000 encryptions. The result of information leakage test shows that the secret key cannot be recovered with 99.999% confidence level. Compared to other soft core processor countermeasures, SCRIP LowRISC implementation has the smallest complete soft processor system with 1.04× resource overhead (the smallest hardware masking countermeasure, which is applied to only the ALU of a RISC-V processor has 1.59× resource overhead, and the smallest balancing countermeasure soft processor, with the countermeasure applied only to the ALU and the memory, required 1.15× area overhead) where the security against power analysis attacks is applied to most components of the processor (including ALU, caches, Block RAM, Block RAM controller, bus interconnect and SD card interface). SCRIP LowRISC implementation is the first soft processor with a random execution-based countermeasure to withstand preprocessing methods (such as power trace alignment and noise filtering) which remove the effects of random execution.

BACKGROUND: Pairwise alignment of short DNA sequences with affine-gap scoring is a common processing step performed in a range of bioinformatics analyses. Dynamic programming (i.e. Smith-Waterman algorithm) is widely used for this purpose. Despite using data level parallelisation, pairwise alignment consumes much time. There are faster alignment algorithms but they suffer from the lack of accuracy. RESULTS: In this paper, we present MEM-Align, a fast semi-global alignment algorithm for short DNA sequences that allows for affine-gap scoring and exploit sequence similarity. In contrast to traditional alignment method (such as Smith-Waterman) where individual symbols are aligned, MEM-Align extracts Maximal Exact Matches (MEMs) using a bit-level parallel method and then looks for a subset of MEMs that forms the alignment using a novel dynamic programming method. MEM-Align tries to mimic alignment produced by Smith-Waterman. As a result, for 99.9% of input sequence pair, the computed alignment score is identical to the alignment score computed by Smith-Waterman. Yet MEM-Align is up to 14.5 times faster than the Smith-Waterman algorithm. Fast run-time is achieved by: (a) using a bit-level parallel method to extract MEMs; (b) processing MEMs rather than individual symbols; and, (c) applying heuristics. CONCLUSIONS: MEM-Align is a potential candidate to replace other pairwise alignment algorithms used in processes such as DNA read-mapping and Variant-Calling.

We consider the problem of data collection from a network of energy harvesting sensors, applied to tracking mobile assets in rural environments. Our application constraints favor a fair and energy-aware solution, with heavily duty-cycled sensor nodes communicating with powered base stations. We study a novel scheduling optimization problem for energy harvesting mobile sensor network, that maximizes the amount of collected data under the constraints of radio link quality and energy harvesting efficiency, while ensuring a fair data reception. We show that the problem is NP-complete and propose a heuristic algorithm to approximate the optimal scheduling solution in polynomial time. Moreover, our algorithm is flexible in handling progressive energy harvesting events, such as with solar panels, or opportunistic and bursty events, such as with Wireless Power Transfer. We use empirical link quality data, solar energy, and WPT efficiency to evaluate the proposed algorithm in extensive simulations and compare its performance to state-of-the-art. We show that our algorithm achieves high data reception rates, under different fairness and node lifetime constraints.

Online rating systems are widely accepted as means for quality assessment on the web and users increasingly rely on these systems when deciding to purchase an item online. This makes such rating systems frequent targets of attempted manipulation by posting unfair rating scores. Therefore, providing useful, realistic rating scores as well as detecting unfair behavior are both of very high importance. Existing solutions are mostly majority based, also employing temporal analysis and clustering techniques. However, they are still vulnerable to unfair ratings. They also ignore distances between options, the provenance of information, and different dimensions of cast rating scores while computing aggregate rating scores and trustworthiness of users. In this article, we propose a robust iterative algorithm which leverages information in the profile of users and provenance of information, and which takes into account the distance between options to provide both more robust and informative rating scores for items and trustworthiness of users. We also prove convergence of iterative ranking algorithms under very general assumptions, which are satisfied by the algorithm proposed in this article. We have implemented and tested our rating method using both simulated data as well as four real-world datasets from various applications of reputation systems. The experimental results demonstrate that our model provides realistic rating scores even in the presence of a massive amount of unfair ratings and outperforms the well-known ranking algorithms.

Billions of transistors on a chip and the power wall made embedded systems to be designed with Multiprocessor System-on-Chip (MPSoC) architectures. One utilization of MPSoCs is the Pipelined MPSoCs (PMPSoCs). As many reliable and safety critical systems are deployed with MPSoCs, denying their service would have adverse effects. One such possibility is the insertion of a hardware Trojan that performs Denial of Service (DoS) attacks. DoSGuard present a novel PMPSoC architecture that continues its execution in the presence of DoS Trojans in Third Party Intellectual Property (3PIP) cores. DoSGuard deploys two methods; one can detect the presence of Trojans and recover, and the other can also identify the 3PIPs under attack using buffer delays. While the state of the art incurs 3× area and power overheads, DoSGuard consumes 1.5M+3 area and leakage power (M is the number of cores in the base system) and a small (the power consumption of the monitoring system) dynamic power overheads. On a cycle accurate commercial multiprocessor simulator, DoSGuard takes 531 clock cycles to detect a DoS attack. With DoSGuard the throughput reduction due to a DoS attack varies with the application and the monitoring interval but is negligible (-3%) for real world scenarios, where millions of iterations take place.

Hardware Trojans are a major concern due to the damage caused by their stealth. One popular utilization of Multiprocessor System on Chips (MPSoCs) is the Pipelined MPSoC (PMPSoC) architectures. They are used in applications from video surveillance to consumer electronics. We present a method that detects the presence of Trojans in third party IP cores of PMPSoCs, by continuous monitoring and testing, and recovers by switching the infected core with another core. We implemented the system on a commercial cycle accurate multiprocessor simulation environment. Our system incurs about 2x area and leakage power, and 1.5x dynamic power overheads, without any adverse impact on throughput compared to the state of the art that uses Triple Modular Redundancy (TMR) and therefore incurs at least 3x overhead.

MOTIVATION: The Variant Call Format (VCF) is widely used to store data about genetic variation. Variant calling workflows detect potential variants in large numbers of short sequence reads generated by DNA sequencing and report them in VCF format. To evaluate the accuracy of variant callers, it is critical to correctly compare their output against a reference VCF file containing a gold standard set of variants. However, comparing VCF files is a complicated task as an individual genomic variant can be represented in several different ways and is therefore not necessarily reported in a unique way by different software. RESULTS: We introduce a VCF normalization method called Best Alignment Normalisation (BAN) that results in more accurate VCF file comparison. BAN applies all the variations in a VCF file to the reference genome to create a sample genome, and then recalls the variants by aligning this sample genome back with the reference genome. Since the purpose of BAN is to get an accurate result at the time of VCF comparison, we define a better normalization method as the one resulting in less disagreement between the outputs of different VCF comparators. AVAILABILITY AND IMPLEMENTATION: The BAN Linux bash script along with required software are publicly available on https://sites.google.com/site/banadf16. CONTACT: [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Power based side-channel attacks attempt to obtain the secret key from implementations of cryptographic algorithms, such as Advanced Encryption Standard (AES), by analyzing the power traces during execution. Such attacks employ statistical methods to find correlations of power traces with parts of the secret key. In order to be effective, a countermeasure must remove or conceal such a signature. Previous countermeasures have either removed dynamic power signatures or leakage power signatures, but have not demonstrated effectiveness against both. In this paper, for the first time, we propose a balance and rotate technique for block cipher based algorithms and demonstrate it on an AES circuitry to remove the signature of the secret key from both the static and dynamic components of the power traces and further demonstrate that the countermeasure can withstand the path imbalances and process variation effects. Our solution, relies on algorithmically balancing Hamming distances and Hamming weights (where the bit transitions on the registers and gates are balanced, and the total number of 1s and 0s are balanced) by the use of four identical circuits with differing inputs and modified SubByte tables. By randomly rotating the four encryptions, the system is protected against variations, path imbalances and aging effects. When resistance against power analysis attacks is not of high priority, the proposed countermeasure allows components to be switched off to save power, or to run four executions in parallel for high performance. The proposed countermeasure is implemented for AES and tested against CPA and MIA attacks (for up to a million traces) and none of the secret keys were found even after one million power traces (unprotected AES circuit revealed the secret key within 5,000 power traces). This is the smallest known circuit which is capable of withstanding power based side-channel attacks when variations, path imbalances and aging effects are considered.

Trust and reputation systems are widely employed in WSNs to help decision making processes by assessing trustworthiness of sensor nodes in a data aggregation process. However, in unattended and hostile environments, more sophisticated malicious attacks, such as collusion attacks, can distort the computed trust scores and lead to low quality or deceptive service as well as undermine the aggregation results. In this paper we propose a novel, local, collaborative-based trust framework for WSNs that is based on the concept of credibility propagation which we introduce. In our approach, trustworthiness of a sensor node depends on the amount of credibility that such a node receives from other nodes. In the process we also obtain an estimates of sensors' variances which allows us to estimate the true value of the signal using the Maximum Likelihood Estimation. Extensive experiments using both real-world and synthetic datasets demonstrate the efficiency and effectiveness of our approach.

The need for Multiprocessor Systems-on-Chip (MPSoCs) to satisfy performance demands of applications in embedded systems has enabled vendors to create different communication architectures for MPSoCs. It is a challenge to rapidly identify the best communication architecture and its best configuration, in terms of task mapping and buffer size, for a given application. In this paper, we propose a novel predictive methodology to first quickly predict the communication architecture and then iteratively search for the optimal configuration of the selected MPSoC architecture. A correction approach is applied at the end to make sure that the selected MPSoC architecture and its configuration is the best suited for the area and application latency constraints. Our exploration is significantly quicker than a Particle Swarm approach, achieving an improvement factor of 15 and 87 in solving time when using fresh hardware and existing hardware builds respectively. While our approach is mostly accurate in finding the optimal solution, certain inaccuracies are observed due to less accurate corrector.

Due to limited computational power and energy resources, aggregation of data from multiple sensor nodes done at the aggregating node is usually accomplished by simple methods such as averaging. However such aggregation is known to be highly vulnerable to node compromising attacks. Since WSN are usually unattended and without tamper resistant hardware, they are highly susceptible to such attacks. Thus, ascertaining trustworthiness of data and reputation of sensor nodes is crucial for WSN. As the performance of very low power processors dramatically improves, future aggregator nodes will be capable of performing more sophisticated data aggregation algorithms, thus making WSN less vulnerable. Iterative filtering algorithms hold great promise for such a purpose. Such algorithms simultaneously aggregate data from multiple sources and provide trust assessment of these sources, usually in a form of corresponding weight factors assigned to data provided by each source. In this paper we demonstrate that several existing iterative filtering algorithms, while significantly more robust against collusion attacks than the simple averaging methods, are nevertheless susceptive to a novel sophisticated collusion attack we introduce. To address this security issue, we propose an improvement for iterative filtering techniques by providing an initial approximation for such algorithms which makes them not only collusion robust, but also more accurate and faster converging.

Detection of high risk hosts and flows continues to be a significant problem in security monitoring of high throughput networks. A comprehensive risk assessment method should consider the risk propagation among risky hosts and flows. In this paper, this is achieved by introducing two novel concepts. First, an interdependency relationship among the risk scores of a network flow and its source and destination hosts. On the one hand, the risk score of a host depends on risky flows initiated by or terminated at the host. On the other hand, the risk score of a flow depends on the risk scores of its source and destination hosts. Second, which we call flow provenance, represents risk propagation among network flows which considers the likelihood that a particular flow is caused by the other flows. Based on these two concepts, we develop an iterative algorithm for computing the risk score of hosts and network flows. We give a rigorous proof that our algorithm rapidly converges to unique risk estimates, and provide its extensive empirical evaluation using two real-world data sets. Our evaluation shows that our method is effective in detecting high risk hosts and flows and is sufficiently efficient to be deployed in the high throughput networks.

Online rating systems are widely used to facilitate making decisions on the web. For fame or profit, people may try to manipulate such systems by posting unfair evaluations. Therefore, determining objective rating scores of products or services becomes a very important yet difficult problem. Existing solutions are mostly majority based, also employing temporal analysis and clustering techniques. However, they are still vulnerable to sophisticated collaborative attacks. In this paper we propose an iterative rating algorithm which is very robust against collusion attacks as well as random and biased raters. Unlike previous iterative methods, our method is not based on comparing submitted evaluations to an approximation of the final rating scores, and it entirely decouples credibility assessment of the cast evaluations from the ranking itself. This makes it more robust against sophisticated collusion attacks than the previous iterative filtering algorithms. We provide a rigorous proof of convergence of our algorithm based on the existence of a fixed point of a continuous mapping which also happens to be a stationary point of a constrained optimization objective. We have implemented and tested our rating method using both simulated data as well as real world movie rating data. Our tests demonstrate that our model calculates realistic rating scores even in the presence of massive collusion attacks and outperforms well-known algorithms in the area. The results of applying our algorithm on the real-world data obtained from MovieLens conforms highly with the rating scores given by Rotten Tomatoes movie critics as domain experts for movies.

Low-power compact sensor nodes are being increasingly used to collect trajectory data from moving objects such as wildlife. The size of this data can easily overwhelm the data storage available on these nodes. Moreover, the transmission of this extensive data over the wireless channel may prove to be difficult. The memory and energy constraints of these platforms underscores the need for lightweight online trajectory compression albeit without seriously affecting the accuracy of the mobility data. In this paper, we present a novel online Polygon Based Approximation (PBA) algorithm that uses regular polygons, the size of which is determined by the allowed spatial error, as the smallest spatial unit for approximating the raw GPS samples. PBA only stores the first GPS sample as a reference. Each subsequent point is approximated to the centre of the polygon containing the point. Furthermore, a coding scheme is proposed that encodes the relative position (distance and direction) of each polygon with respect to the preceding polygon in the trajectory. The resulting trajectory is thus a series of bit codes, that have pair-wise dependencies at the reference point. It is thus possible to easily reconstruct an approximation of the original trajectory by decoding the chain of codes starting with the first reference point. Encoding a single GPS sample is an O (1) operation, with an overall complexity of O (n). Moreover, PBA only requires the storage of two raw GPS samples in memory at any given time. The low complexity and small memory footprint of PBA make it particularly attractive for low-power sensor nodes. PBA is evaluated using GPS traces that capture the actual mobility of flying foxes in the wild. Our results demonstrate that PBA can achieve up to nine-fold memory savings as compared to Douglas-Peucker line simplification heuristic. While we present PBA in the context of low-power devices, it can be equally useful for other GPS-enabled devices such smartphones and car navigation units.

Advanced Encryption Standard (AES) is arguably the most popular symmetric block cipher algorithm. The commonly used mode of operation in AES is the Electronic Codebook (ECB) mode. In the past, side channel attacks (including power analysis based attacks) have been shown to be effective in breaking the secret keys used with AES, while AES is operating in the ECB mode. AES defines a number of advanced modes (namely Cipher Block Chaining - CBC, Cipher Feedback - CFB, Output Feedback - OFB, and Counter - CTR) of operations that are built on top of the EBC mode to enhance security via disassociating the encryption function from the plaintext or the secret key used. In this paper, we investigate the vulnerabilities against power analysis based side channel attacks of all such modes of operations, implemented on hardware circuits for low power and high speed embedded systems. Through such an investigation, we show that AES is vulnerable in all modes of operations against Correlation Power Analysis (CPA) attack, one of the strongest power analysis based side channel attacks. We also quantify the level of difficulty in breaking AES in different modes by calculating the number of power traces needed to arrive at the complete secret key. We conclude that the Counter mode of operation provides a balance in between area and power while maintaining adequate resistance for power analysis attacks than when used with other modes of operations. We show that the previous recommendations for the rate of change in the keys and vectors is grossly inadequate, and suggest that it must be changed at least every 210encryptions in CBC mode and 212encryptions in CFB, OFB and CTR modes in order to resist power analysis attacks.

Wi-Fi based fingerprinting systems, mostly utilize the Received Signal Strength Indicator (RSSI), which is known to be unreliable due to environmental and hardware effects. In this paper, we present a novel Wi-Fi fingerprinting system, exploiting the fine-grained information known as Channel State Information (CSI). The frequency diversity of CSI can be effectively utilized to represent a location in both frequency and spatial domain resulting in more accurate indoor localization. We propose a novel location signature CSI-MIMO that incorporates Multiple Input Multiple Output (MIMO) information and use both the magnitude and the phase of CSI of each sub-carrier. We experimentally evaluate the performance of CSI-MIMO fingerprinting using the k-nearest neighbor and the Bayes algorithm. The accuracy of the proposed CSI-MIMO is compared with Finegrained Indoor Fingerprinting System (FIFS) and a simple CSI-based system. The experimental result shows an accuracy improvement of 57% over FIFS with an accuracy of 0.95 meters.

Detection of high risk network flows and high risk hosts is becoming ever more important and more challenging. In order to selectively apply deep packet inspection (DPI) one has to isolate in real time high risk network activities within a huge number of monitored network flows. To help address this problem, we propose an iterative methodology for a simultaneous assessment of risk scores for both hosts and network flows. The proposed approach measures the risk scores of hosts and flows in an interdependent manner; thus, the risk score of a flow influences the risk score of its source and destination hosts, and also the risk score of a host is evaluated by taking into account the risk scores of flows initiated by or terminated at the host. Our experimental results show that such an approach not only effective in detecting high risk hosts and flows but, when deployed in high throughput networks, is also more efficient than PageRank based algorithms.

The paradigm of pipelined MPSoC (processors connected in a pipeline) is well suited to data flow nature of multimedia applications. Often design space exploration is performed to optimize execution time, latency or throughput of a pipelined MPSoC where the variants in the system are processor configurations due to customizable options in each of the processors. Since there can be billions of combinations of processor configurations (design points), the challenge is to quickly provide estimates of performance metrics of those design points. Hence, in this article, we propose analytical models to estimate execution time, latency and throughput of a pipelined MPSoC's design points, avoiding slow full-system cycle accurate simulations of all the design points. For effective use of these analytical models, latencies of individual processor configurations should be available. We propose two estimation methods (PS and PSP) to quickly gather latencies of processor configurations with reduced number of simulations. The PS method simulates all the processor configurations once, while the PSP method simulates only a subset of processor configurations and then uses a processor analytical model to estimate the latencies of the remaining processor configurations. We experimented with several pipelined MPSoCs executing typical multimedia applications (JPEG encoder/decoder, MP3 encoder and H.264 encoder). Our results show that the analytical models with PS and PSP methods had maximum absolute error of 12.95 percent and 18.67 percent respectively, and minimum fidelity of 0.93 and 0.88 respectively. The design spaces of the pipelined MPSoCs ranged from 1012to 1018design points, and hence simulation of all design points will take years and is infeasible. Compared to PS method, the PSP method reduced simulation time from days to several hours.

Discovering high risk network flows and hosts in a high throughput network is a challenging task of network monitoring. Emerging complicated attack scenarios such as DDoS attacks increase the complexity of tracking malicious and high risk network activities within a huge number of monitored network flows. To address this problem, we propose an iterative framework for assessing risk scores for hosts and network flows. To obtain risk scores of flows, we take into account two properties, flow attributes and flow provenance. Also, our iterative risk assessment measures the risk scores of hosts and flows based on an interdependency property where the risk score of a flow influences the risk of its source and destination hosts, and the risk score of a host is evaluated by risk scores of flows initiated by or terminated at the host. Moreover, the update mechanism in our framework allows flows to keep streaming into the system while our risk assessment method performs an online monitoring task. The experimental results show that our approach is effective in detecting high risk hosts and flows as well as sufficiently efficient to be deployed in high throughput networks compared to other algorithms.

Intermittent faults (IF) in chips are becoming commonplace with the current technology trend and the process scaling. In this paper, we first modify the well known birth-death Markov model so that availability can be calculated. We then show that the standard birth-death Markov model does not capture IF correctly, and create a novel Markov model for intermittent faults that is derived from the specific nature of such faults. The proposed model, for the first time, differentiates risky and normal components and therefore does not waste processing time for unnecessary testing procedures. Consequently, the availability of processors with the proposed model increases significantly compared to the traditional model (from 0.90 to 0.99 with a typical parameter set). In addition, the proposed model facilitates parameter space exploration. Positive effects were observed with varying parameters such as error rate, recovery time and test program length. It was concluded that choice of right testing parameters are vital for gaining optimal system availability and the new model supports achieving the same.

In this paper we introduce a novel sophisticated collusion attack scenario against a number of existing iterative filtering algorithms. To address this security issue, we propose an improvement for iterative filtering techniques by providing an initial approximation for such algorithms which makes them not only collusion robust, but also more accurate and faster converging.

Wireless sensor networks (WSNs) enable the collection of physical measurements over a large geographic area. It is often the case that we are interested in computing and tracking the spatial-average of the sensor measurements over a region of the WSN. Unfortunately, the standard average operation is not robust because it is highly susceptible to sensor faults and heterogeneous measurement noise. In this paper, we propose a computational efficient method to compute a weighted average (which we will call robust average) of sensor measurements, which appropriately takes sensor faults and sensor noise into consideration. We assume that the sensors in the WSN use random projections to compress the data and send the compressed data to the data fusion centre. Computational efficiency of our method is achieved by having the data fusion centre work directly with the compressed data streams. The key advantage of our proposed method is that the data fusion centre only needs to perform decompression once to compute the robust average, thus greatly reducing the computational requirements. We apply our proposed method to the data collected from two WSN deployments to demonstrate its efficiency and accuracy.

Worker selection is a significant and challenging issue in crowdsourcing systems. Such selection is usually based on an assessment of the reputation of the individual workers participating in such systems. However, assessing the credibility and adequacy of such calculated reputation is a real challe

Multiprocessor System-on-Chip (MPSoC) is an integral element in state-of-the-art embedded devices, ranging from low-end, mobile phones, PDAs, handheld medical devices up to high-end cars, avionics and robotics. Proper and safe functionality of such embedded systems is mandatory to avoid severe consequences, whereas security is absolutely necessary with “Cashless Wallets” forecasted to be the only means of financial transactions in the near future. Such a scenario places immense onus on the security experts where secure transactions using credit cards or mobile phones or any other embedded devices should not be revealing any footprint to the adversary. Side Channel Attacks (SCA) are considered as one of the most effective attacks on these embedded systems because of their effectiveness in realizing the secret information without physically disassembling the device. We propose an MPSoC architecture to prevent power analysis SCA where a dual-core algorithmic balancing is enforced by corrupting the balanced key and swapping the encryption rounds of a block-cipher at random places, random number of times. A case study using DES cryptography is performed. Our approach, CoRaS, alleviates performance by 0.1% and area by 3.6% compared to the state-of-the-art MPSoC solution, however enhances security and practicality by eliminating its weaknesses.

We consider the problem of on-chip L2 cache management and replacement policies. We propose a new adaptive cache replacement policy, called Dueling CLOCK (DC), that has several advantages over the Least Recently Used (LRU) cache replacement policy.

Estimation models play a vital role in many aspects of day to day life. Extremely complex estimation models are employed in the design space exploration of SoCs, and the efficacy of these estimation models is usually measured by the absolute error of the models compared to known actual results. Such absolute error based metrics can often result in over-designed estimation models, with a number of researchers suggesting that fidelity of an estimation model (correlation between the ordering of the estimated points and the ordering of the actual points) should be examined instead of, or in addition to, the absolute error. In this paper, for the first time, we propose four metrics to measure the fidelity of an estimation model, in particular for use in design space exploration. The first two are based on two well known rank correlation coefficients. The other two are weighted versions of the first two metrics, to give importance to points nearer the Pareto front. The proposed fidelity metrics range from -1 to 1, where a value of 1 reflects a perfect positive correlation while a value of -1 reflects a perfect negative correlation. The proposed fidelity metrics were calculated for a single processor estimation model and a multiprocessor estimation model to observe their behavior, and were compared against the models' absolute error. For the multiprocessor estimation model, even though the worst average and maximum absolute error of 6.40% and 16.61% respectively can be considered reasonable in design automation, the worst fidelity of 0.753 suggests that the multiprocessor estimation model may not be as good a model (compared to an estimation model with same or higher absolute errors but a fidelity of 0.95) as depicted by its absolute accuracy, leading to an over-designed estimation model.

This paper describes a rapid design methodology to create a pipeline of processors to execute streaming applications. The methodology seeks a system with the smallest area while its runtime is within a specified runtime constraint. Initially, a heuristic is used to rapidly explore a large number of processor configurations to find the near Pareto front of the design space, and then an exact integer linear programming (ILP) formulation (EIF) is used to find an optimal solution. A reduced ILP formulation (RIF) or the heuristic is used if the EIF does not find an optimal solution in a given time window. This design methodology was integrated into a commercial design flow and was evaluated on four benchmarks with design spaces containing up to 1016design points. For each benchmark, the near Pareto front was found in less than 3 h using the heuristic, while EIF took up to 16 h. The results show that the average area error of the heuristic and RIF was within 2.25% and 1.25% of the optimal design points for all the benchmarks, respectively. The heuristic is faster than RIF, while both the heuristic and RIF are significantly faster than EIF.

In this paper, we present a novel HitME (Hit-MEmory) buffer to reduce the energy consumption of memory hierarchy in embedded processors. The HitME buffer is a small direct-mapped cache memory that is added as additional memory into existing cache memory hierarchies. The HitME buffer is loaded only when there is a hit on L1 cache. Otherwise, L1 cache is updated from the memory and the processor's memory request is served directly from the L1 cache. The strategy works due to the fact that 90% of memory accesses are only accessed once, and these often pollute the cache. Energy reduction is achieved by reducing the number of accesses to the L1 cache memory. Experimental results show that the use of HitME buffer will reduce the L1 cache accesses resulting in a reduction in the energy consumption of the memory hierarchy. This decrease in L1 cache accesses reduces the cache system energy consumption by an average of 60.9% when compared to traditional L1 cache memory architecture and an energy reduction of 6.4% when compared to filter cache architecture for 70nm cache technology.

Standard approaches to evaluating and comparing information retrieval systems compute simple averages of performance statistics across individual topics to measure the overall system performance. However, topics vary in their ability to differentiate among systems based on their retrieval performance. At the same time, systems that perform well on discriminative queries demonstrate notable qualities that should be reflected in the systems' evaluation and ranking. This motivated research on alternative performance measures that are sensitive to the discriminative value of topics and the performance consistency of systems. In this paper we provide a mathematical formulation of a performance measure that postulates the dependence between the system and topic characteristics. We propose the Generalized Adaptive-Weight Mean (GAWM) measure and show how it can be computed as a fixed point of a function for which the Brouwer Fixed Point Theorem applies. This guarantees the existence of a scoring scheme that satisfies the starting axioms and can be used for ranking of both systems and topics. We apply our method to TREC experiments and compare the GAWM with the standard averages used in TREC.

Community Question Answering (cQA) services, such as Yahoo! Answers and MSN QnA, facilitate knowledge sharing through question answering by an online community of users. These services include incentive mechanisms to entice participation and self-regulate the quality of the content contributed by the users. In order to encourage quality contributions, community members are asked to nominate the ‘best’ among the answers provided to a question. The service then awards extra points to the author who provided the winning answer and to the voters who cast their vote for that answer. The best answers are typically selected by plurality voting, a scheme that is simple, yet vulnerable to random voting and collusion. We propose a weighted voting method that incorporates information about the voters’ behavior. It assigns a score to each voter that captures the level of agreement with other voters. It uses the voter scores to aggregate the votes and determine the best answer. The mathematical formulation leads to the application of the Brouwer Fixed Point Theorem which guarantees the existence of a voter scoring function that satisfies the starting axiom. We demonstrate the robustness of our approach through simulations and analysis of real cQA service data.

Side channel attack based upon the analysis of power traces is an effective way of obtaining the encryption key from secure processors. Power traces can be used to detect bitflips which betray the secure key. Balancing the bitflips with opposite bitflips have been proposed, by the use of opposite logic. This is an expensive solution, where the balancing processor continues to balance even when encryption is not carried out in the processor.

Agents from a community interact in pairwise transactions across discrete time. Each agent reports its evaluation of another agent with which it has just had a transaction to a central system. This system uses these time-sequences of experience evaluations to infer how much the agents trust each another. Our paper proposes rationality assumptions (also called axioms or constraints) that such inferences must obey, and proceeds to derive theorems implied by these assumptions. A basic representation theorem is proved. The system also uses these pairwise cross-agent trustworthiness to compute a reputation rank for each agent. Moreover, it provides with each reputation rank an estimate of the reliability, which we call weight of evidence. This paper is different from much of the current work in that it examines how a central system which computes trustworthiness, reputation and weight of evidence is constrained by such rationality postulates.

Modern application specific instruction set processors (ASIPs) have customizable caches, where the size, associativity and line size can all be customized to suit a particular application. To find the best cache size suited for a particular embedded system, the applications) is/are executed, traces obtained, and caches simulated. Typically, program trace files can range from a few megabytes to several gigabytes. Simulation of cache performance using large program trace files is a time consuming process. In this paper, a novel instruction cache simulation methodology that can operate directly on a compressed program trace file without the need for decompression is presented. This feature allowed our simulation methodology to have an average speed up of 9.67 times compared to the existing state of the art tool (Dinero IV cache simulator), for a range of applications from the Mediabench suite

Scratchpad memory has been introduced as a replacement for cache memory as it improves the performance of certain embedded systems. Additionally, it has also been demonstrated that scratchpad memory can significantly reduce the energy consumption of the memory hierarchy of embedded systems. This is significant, as the memory hierarchy consumes a substantial proportion of the total energy of an embedded system. This paper deals with optimization of the instruction memory scratchpad based on a methodology that uses a metric which we call the concomitance. This metric is used to find basic blocks which are executed frequently and in close proximity in time. Once such blocks are found, they are copied into the scratchpad memory at appropriate times; this is achieved using a special instruction inserted into the code at appropriate places. For a set of benchmarks taken from Mediabench, our scratchpad system consumed just 59% (avg) of the energy of the cache system, and 73% (avg) of the energy of the state of the art scratchpad system, while improving the overall performance. Compared to the state of the art method, the number of instructions copied into the scratchpad memory from the main memory is reduced by 88%.

Modern embedded system execute a single application or a class of applications repeatedly. A new emerging methodology of designing embedded system utilizes configurable processors where the cache size, associativity, and line size can be chosen by the designer. In this paper, a method is given to rapidly find the L1 cache miss rate of an application. An energy model and an execution time model are developed to find the best cache configuration for the given embedded application. Using benchmarks from Mediabench, we find that our method is on average 45 times faster to explore the design space, compared to Dinero IV while still having 100% accuracy.

A method to both reduce energy and improve performance in a processor-based embedded system is described in this paper. Comprising of a scratchpad memory instead of an instruction cache, the target system dynamically (at runtime) copies into the scratchpad code segments that are determined to be beneficial (in terms of energy efficiency and/or speed) to execute from the scratchpad. We develop a heuristic algorithm to select such code segments based on a metric, called concomitance. Concomitance is derived from the temporal relationships of instructions. A hardware controller is designed and implemented for managing the scratchpad memory. Strategically placed custom instructions in the program inform the hardware controller when to copy instructions from the main memory to the scratchpad. A novel heuristic algorithm is implemented for determining locations within the program where to insert these custom instructions. For a set of realistic benchmarks, experimental results indicate the method uses 41.9% lower energy (on average) and improves performance by 40.0% (on average) when compared to a traditional cache system which is identical in size

Abstract In this paper we devise some technical tools for dealing with problems connected with the philosophical view usually called mathematical instrumentalism. These tools are interesting in their own right, independently of their philosophical consequences. For example, we show that even though the fragment of Peanos Arithmetic known as IΣ1 is a conservative extension of the equational theory of Primitive Recursive Arithmetic (PRA). IΣ1 has a super-exponential speed-up over PRA. On the other hand, theories studied in the Program of Reverse Mathematics that formalize powerful mathematical principles have only polynomial speed-up over IΣ1.

We propose a methodology for energy reduction and performance improvement. The target system comprises of an instruction scratchpad memory instead of an instruction cache. Highly utilized code segments are copied into the scratchpad memory, and are executed from the scratchpad. The copying of code segments from main memory to the scratchpad is performed during runtime. A custom hardware controller is used to manage the copying process. The hardware controller is activated by strategically placed custom instructions within the executing program. These custom instructions inform the hardware controller when to copy during program execution. Novel heuristic algorithms are implemented to determine locations within the program to insert these custom instructions, as well as to choose the best sets of code segments to be copied to the scratchpad memory. For a set of realistic benchmarks, experimental results indicate the method uses 50.7% lower energy (on average) and improves performance by 53.2% (on average) when compared to a traditional cache system which is identical in size. Cache systems compared had sizes ranging from 256 to 16K bytes and associativities ranging from 1 to 32.

While it is commonly accepted that computability on a Turing machine in polynomial time represents a correct formalization of the notion of a feasibly computable function, there is no similar agreement on how to extend this notion on functionals , that is, what functionals should be considered feasible. One possible paradigm was introduced by Mehlhorn, who extended Cobham's definition of feasible functions to type 2 functionals. Subsequently, this class of functionals (with inessential changes of the definition) was studied by Townsend who calls this class POLY , and by Kapron and Cook who call the same class basic feasible functionals . Kapron and Cook gave an oracle Turing machine model characterisation of this class. In this article, we demonstrate that the class of basic feasible functionals has recursion theoretic properties which naturally generalise the corresponding properties of the class of feasible functions, thus giving further evidence that the notion of feasibility of functionals mentioned above is correctly chosen. We also improve the Kapron and Cook result on machine representation.Our proofs are based on essential applications of logic. We introduce a weak fragment of second order arithmetic with second order variables ranging over functions from N N which suitably characterises basic feasible functionals, and show that it is a useful tool for investigating the properties of basic feasible functionals. In particular, we provide an example how one can extract feasible programs from mathematical proofs that use nonfeasible functions.

A new contribution to generalized sampling of bandlimited signals based on the so-called chromatic derivative operators was recently introduced by Ignjatovic (see Kromos Technology, Los Altos, CA. [Online] Tech. Rep. 1, 2001). Chromatic derivatives are linear combinations of the ordinary derivatives, where the coefficients of the combination are derived from orthogonal polynomial theory. This article describes the connection between these operators and the well-established ideas of perfect reconstruction and biorthogonality in analog filter banks.

Abstract In this paper we characterize the well-known computational complexity classes of the polynomial time hierarchy as classes of provably recursive functions (with graphs of suitable bounded complexity) of some second order theories with weak comprehension axiom schemas but without any induction schemas (Theorem 6). We also find a natural relationship between our theories and the theories of bounded arithmetic (Lemmas 4 and 5). Our proofs use a technique which enables us to “speed up” induction without increasing the bounded complexity of the induction formulas. This technique is also used to obtain an interpretability result for the theories of bounded arithmetic (Theorem 4).

Abstract In the first part of this paper we discuss some aspects of Detlefsen's attempt to save Hilbert's Program from the consequences of Gödel's Second Incompleteness Theorem. His arguments are based on his interpretation of the long standing and well-known controversy on what, exactly, finitistic means are. In his paper [1] Detlefsen takes the position that there is a form of theω-rule which is a finitistically valid means of proof, sufficient to prove the consistency of elementary number theoryZ. On the other hand, he claims thatZwith its first-order logic is not strong enough to allow a formalization of such anω-rule. This would explain why the unprovability of Con(Z) inZdoes not imply that the consistency ofZcannot be proved by finitistic means. We show that Detlefsen's proposal is unacceptable as originally formulated in [1], but that a reasonable modification of the rule he suggest leads to a partial program already studied for many years. We investigate the scope of such a program in terms of proof-theoretic reducibilities. We also show that this partial program encompasses mathematically important theories studied in the “Reverse Mathematics” program. In order to investigate the provability with such a modified rule, we define new consistency and provability predicates which are weaker than the usual ones. We then investigate their properties, including a few that have no apparent philosophical significance but compare interestingly with the properties of the program based on the iteration of ourω-rule. We determine some of the limitations of such programs, pointing out that these limitations partly explain why partial programs that have been successfully carried out use quite different and substantially more radical extensions of finitistic methods with more general forms of restricted reasoning.

The primary aim of this paper is to introduce higher type analogues of some familiar parallel complexity classes, and to show that these higher type classes can be characterised in significantly different ways. Recursion-theoretic, proof-theoretic and machine-theoretic characterisations are given for various classes, providing evidence of their naturalness.>