Automatic generation of assertions to detect potential security vulnerabilities in C programs that use union and pointer types

Type unions, pointer variables and function pointers are a long standing source of subtle security bugs in C program code. Their use can lead to hard-to-diagnose crashes or exploitable vulnerabilities that allow an attacker to attain privileged access over classified data. This paper describes an automatable framework for detecting such weaknesses in C programs statically, where possible, and for generating assertions that will detect them dynamically, in other cases. Exclusively based on analysis of the source code, it identifies required assertions using a type inference system supported by a custom made symbol table. In our preliminary findings, our type system was able to infer the correct type of unions in different scopes, without manual code annotations or rewriting. Whenever an evaluation is not possible or is difficult to resolve, appropriate runtime assertions are formed and inserted into the source code. The approach is demonstrated via a prototype C analysis tool.

Detecting attacks in encrypted networks using secret-sharing schemes

Secret-sharing schemes describe methods to securely share a secret among a group of participants. A properly constructed secret-sharing scheme guarantees that the share belonging to one participant does not reveal anything about the shares of others or even the secret itself. Besides being used to distribute a secret, secret-sharing schemes have also been used in secure multi-party computations and redundant residue number systems for error correction codes. In this paper, we propose that the secret-sharing scheme be used as a primitive in a Network-based Intrusion Detection System (NIDS) to detect attacks in encrypted Networks. Encrypted networks such as Virtual Private Networks (VPNs) fully encrypt network traffic which can include both malicious and non-malicious traffic. Traditional NIDS cannot monitor such encrypted traffic. We therefore describe how our work uses a combination of Shamir's secret-sharing scheme and randomised network proxies to enable a traditional NIDS to function normally in a VPN environment.

A Stochastic View of Optimal Regret through Minimax Duality

We study the regret of optimal strategies for online convex optimization games. Using von Neumann's minimax theorem, we show that the optimal regret in this adversarial setting is closely related to the behavior of the empirical minimization algorithm in a stochastic process setting: it is equal to the maximum, over joint distributions of the adversary's action sequence, of the difference between a sum of minimal expected losses and the minimal empirical loss. We show that the optimal regret has a natural geometric interpretation, since it can be viewed as the gap in Jensen's inequality for a concave functional--the minimizer over the player's actions of expected loss--defined on a set of probability distributions. We use this expression to obtain upper and lower bounds on the regret of an optimal strategy for a variety of online learning problems. Our method provides upper bounds without the need to construct a learning algorithm; the lower bounds provide explicit optimal strategies for the adversary. Peter L. Bartlett, Alexander Rakhlin

Design of decoupling networks for circulant symmetric antenna arrays

Small element spacing in compact arrays results in strong mutual coupling between array elements. Performance degradation associated with the strong coupling can be avoided through the introduction of a decoupling network consisting of interconnected reactive elements. We present a systematic design procedure for decoupling networks of symmetrical arrays with more than three elements and characterized by circulant scattering parameter matrices. The elements of the decoupling network are obtained through repeated decoupling of the characteristic eigenmodes of the array, which allows the calculation of element values using closed-form expressions.

Single-layer decoupling networks for circulant symmetric arrays

Reduced element spacing in antenna arrays gives rise to strong mutual coupling between array elements and may cause significant performance degradation. These effects can be alleviated by introducing a decoupling network consisting of interconnected reactive elements. The existing design approach for the synthesis of a decoupling network for circulant symmetric arrays allows calculation of element values using closed-form expressions, but the resulting circuit configuration requires multilayer technology for implementation. In this paper, a new structure for the decoupling of circulant symmetric arrays of more than four elements is presented. Element values are no longer obtained in closed form, but the resulting circuit is much simpler and can be implemented on a single layer.

Dual-frequency decoupling networks for compact antenna arrays

Decoupling networks can alleviate the effects of mutual coupling in antenna arrays. Conventional decoupling networks can provide decoupled and matched ports at a single frequency. This paper describes dual-frequency decoupling which is achieved by using a network of series or parallel resonant circuits instead of single reactive elements.

Design of compact coupled-line couplers

The size of rat-race and branch-line couplers can be reduced by using periodic loading or artificial transmission lines. The objective of this work is to extend the idea of size reduction through periodic loading to coupled-line 90° hybrids. A procedure for the extraction of the characteristic parameters of a coupled-line 4-port from a single set of S-parameters is described. This method can be employed to design of coupled artificial transmission line couplers of arbitrary geometry. The procedure is illustrated through the design a broadside-coupled stripline hybrid, periodically loaded with stubs. Measured results for a prototype coupler confirm the validity of the theory.

Multitask learning with expert advice

We consider the problem of prediction with expert advice in the setting where a forecaster is presented with several online prediction tasks. Instead of competing against the best expert separately on each task, we assume the tasks are related, and thus we expect that a few experts will perform well on the entire set of tasks. That is, our forecaster would like, on each task, to compete against the best expert chosen from a small set of experts. While we describe the “ideal” algorithm and its performance bound, we show that the computation required for this algorithm is as hard as computation of a matrix permanent. We present an efficient algorithm based on mixing priors, and prove a bound that is nearly as good for the sequential task presentation case. We also consider a harder case where the task may change arbitrarily from round to round, and we develop an efficient approximate randomized algorithm based on Markov chain Monte Carlo techniques.

Online discovery of similarity mappings

We consider the problem of choosing, sequentially, a map which assigns elements of a set A to a few elements of a set B. On each round, the algorithm suffers some cost associated with the chosen assignment, and the goal is to minimize the cumulative loss of these choices relative to the best map on the entire sequence. Even though the offline problem of finding the best map is provably hard, we show that there is an equivalent online approximation algorithm, Randomized Map Prediction (RMP), that is efficient and performs nearly as well. While drawing upon results from the "Online Prediction with Expert Advice" setting, we show how RMP can be utilized as an online approach to several standard batch problems. We apply RMP to online clustering as well as online feature selection and, surprisingly, RMP often outperforms the standard batch algorithms on these problems.

Optimal strategies and minimax lower bounds for online convex games

A number of learning problems can be cast as an Online Convex Game: on each round, a learner makes a prediction x from a convex set, the environment plays a loss function f, and the learner’s long-term goal is to minimize regret. Algorithms have been proposed by Zinkevich, when f is assumed to be convex, and Hazan et al., when f is assumed to be strongly convex, that have provably low regret. We consider these two settings and analyze such games from a minimax perspective, proving minimax strategies and lower bounds in each case. These results prove that the existing algorithms are essentially optimal.

Multitask learning with expert advice

We consider the problem of prediction with expert advice in the setting where a forecaster is presented with several online prediction tasks. Instead of competing against the best expert separately on each task, we assume the tasks are related, and thus we expect that a few experts will perform well on the entire set of tasks. That is, our forecaster would like, on each task, to compete against the best expert chosen from a small set of experts. While we describe the "ideal" algorithm and its performance bound, we show that the computation required for this algorithm is as hard as computation of a matrix permanent. We present an efficient algorithm based on mixing priors, and prove a bound that is nearly as good for the sequential task presentation case. We also consider a harder case where the task may change arbitrarily from round to round, and we develop an efficient approximate randomized algorithm based on Markov chain Monte Carlo techniques.

Beam steering with high front-to-back ratio and high directivity on small platforms using decoupled antenna pairs

Beam steering with high front-to-back ratio and high directivity on a small platform is proposed. Two closely spaced antenna pairs with eigenmode port decoupling are used as the basic radiating elements. Two orthogonal radiation patterns are obtained for each antenna pair. High front-to-back ratio and high directivity are achieved by combining the two orthogonal radiation patterns. With an infinite groundplane, a front-to-back ratio of 21 dB with a directivity of 9.8 dB can be achieved. Beam steering, at the expense of a slight decrease in directivity, is achieved by placing the two antenna pairs 0.5λ apart. The simulated half power beamwidth is 58°. A prototype was designed and the 2-D radiation patterns were measured. The prototype supports three directions of beam steering. The half power beamwidth was measured as 46°, 48°, and 50° for the three respective beam directions. The measured front-to-back ratio in azimuth plane is 8.5 dB, 8.0 dB and 7.6 dB, respectively.

A Regularization Approach to Metrical Task Systems

We address the problem of constructing randomized online algorithms for the Metrical Task Systems (MTS) problem on a metric δ against an oblivious adversary. Restricting our attention to the class of “work-based” algorithms, we provide a framework for designing algorithms that uses the technique of regularization. For the case when δ is a uniform metric, we exhibit two algorithms that arise from this framework, and we prove a bound on the competitive ratio of each. We show that the second of these algorithms is ln n + O(loglogn) competitive, which is the current state-of-the art for the uniform MTS problem.

Growing local participation through long term design

Our research explores the design of networked technologies to facilitate local suburban communications and to encourage people to engage with their local community. While there are many investigations of interaction designs for networked technologies, most research utilises small exercises, workshops or other short-term studies to investigate interaction designs. However, we have found these short-term methods to be ineffective in the context of understanding local community interaction. Moreover we find that people are resistant to putting their time into workshops and exercises, understandably so because these are academic practices, not local community practices. Our contribution is to detail a long term embedded design approach in which we interact with the community over the long term in the course of normal community goings-on with an evolving exploratory prototype. This paper discusses the embedded approach to working in the wild for extended field research.

Microstrip to parallel strip balun as spiral antenna feed

This paper presents the design and implementation of a microstrip to parallel strip balun which are frequently used as balanced antennas feed. This wideband balun transition is composed of a parallel strip which is connected to the spiral antenna and a microstrip line where the width of the ground plane is gradually reduced to eventually resemble the parallel strip. The taper accomplishes the mode and impedance transformation. This balun has significantly improved bandwidth characteristics. The entire circuit was fabricated on RT Duriod 5880 substrate. The circuit designs were simulated and optimised using CST Microwave Studio and the simulated results are compared with the measured results. The back-to-back microstrip to parallel strip has a return loss of better than 10 dB over a wide bandwidth from 1.75 to 15 GHz. The performance of the proposed balun was validated with the spiral antenna. The measured results were compared with the simulated results and it shows that the antenna operates well in wideband frequency range from 2.5 to 15 GHz.