Person:

Gwon, Youngjune

We describe a method of integrating Karhunen-Loève Transform (KLT) into compressive sensing, which can as a result improve the compression ratio without affecting the accuracy of decoding. We present two complementary results: 1) by using KLT to find an optimal basis for decoding we can drastically reduce the number of measurements for compressive sensing used in applications such as radio spectrum analysis; 2) by using compressive sensing we can estimate and recover the KLT basis from compressive measurements of an input signal. In particular, we propose CS-KLT, an online estimation algorithm to cope with nonstationarity of wireless channels in reality. We validate our results with empirical data collected from a wideband UHF spectrum and eld experiments to detect multiple radio transmitters, using software-defined radios.

We present a chip architecture for a compressive sensing based method that can be used in conjunction with the JTAG standard to detect IC Trojans. The proposed architecture compresses chip output resulting from a large number of test vectors applied to a circuit under test (CUT). We describe our designs in sensing leakage power, computing random linear combinations under compressive sensing, and piggybacking these new functionalities on JTAG. Our architecture achieves approximately a 10× speedup and 1000× reduction in output bandwidth while incurring a small area overhead.

Detecting Trojans in an integrated circuit (IC) is an important but hard problem. A Trojan is malicious hardware it can be extremely small in size and dormant until triggered by some unknown circuit state. To allow wake-up, a Trojan could draw a minimal amount of power, for example, to run a clock or a state machine, or to monitor a triggering event. We introduce DISTROY (Discover Trojan), a new approach that can effciently and reliably detect extremely small background power leakage that a Trojan creates and as a result, we can detect the Trojan. We formulate our method based on compressive sensing, a recent advance in signal processing, which can recover a signal using the number of measurements approximately proportional to its sparsity rather than size. We argue that circuit states in which the Trojan background power consumption stands out are rare, and thus sparse, so that we can apply compressive sensing. We describe how this is done in DISTROY so as to afford suffcient measurement statistics to detect the presence of Trojans. Finally, we present our initial simulation results that validate DISTROY and discuss the impact of our work in the field of hardware security.

We introduce Competing Mobile Network Game (CMNG), a stochastic game played by cognitive radio networks that compete for dominating an open spectrum access. Differentiated from existing approaches, we incorporate both communicator and jamming nodes to form a network for friendly coalition, integrate antijamming and jamming subgames into a stochastic framework, and apply Q-learning techniques to solve for an optimal channel access strategy. We empirically evaluate our Q-learning based strategies and find that Minimax-Q learning is more suitable for an aggressive environment than Nash-Q while Friend-or-foe Q-learning can provide the best solution under distributed mobile ad hoc networking scenarios in which the centralized control can hardly be available.

We present statistical screening of test vectors for detecting a Trojan, malicious circuitry hidden inside an integrated circuit (IC). When applied a test vector, a Trojan-embedded chip draws extra leakage current that is unfortunately too small for the detector in most cases and concealed by process variation related to chip fabrication. To remedy the problem, we formulate a statistical approach that can screen and select test vectors in detecting Trojans. We validate our approach analytically and with gate-level simulations and show that our screening method leads to a substantial reduction in false positives and false negatives when detecting IC Trojans of various sizes.

e propose a spectrum analyzer that leverages many networked commodity sensor nodes, each of which sam- ples its portion in a wideband spectrum. The sensors operate in parallel and transmit their measurements over a wireless network without performing any significant computations such as FFT. The measurements are forwarded to the backend of the system where spectrum analysis takes place. In particular, we propose a solution that compresses the raw measurements in a simple random linear projection and combines the compressed measurements from multiple sensors in-network. As a result, we achieve a substantial reduction in the network bandwidth requirement to operate the proposed system. We discover that the overall communication cost can be independent of the number of sensors and is affected only by sparsity of discretized spectrum under analysis. This principle founds the basis for a claim that our network-based spectrum analyzer can scale up the number of sensor nodes to process a very wide spectrum block potentially having a GHz bandwidth. We devise a novel recovery algorithm that systematically undoes compressive encoding and in-network combining done to the raw measurements, incorporating the least squares and l1-minimization decoding used in compressive sensing, and demonstrate that the algorithm can effectively restore an accurate estimate of the original data suitable for fine- rained spectrum analysis. We present mathematical analysis and empirical evaluation of the system with software-defined radios.

We describe a method of integrating Karhunen-Loeve Transform (KLT) into compressive sensing, which can as a result leverage KLT’s optimality in revealing the sparsity of a signal. We present two complementary results: (1) by using the KLT to find the optimal basis for decoding we can drastically reduce the number of measurements for compressive sensing used in applications such as spectrum sensing; (2) by using compressive sensing we can compute the KLT basis directly from measurements of the input signal, with substantially fewer samples than the Nyquist rate. For a non-stationary signal, we suggest strategies in addressing the trade-off of incurring additional measurements for updating a KLT basis or compensating an obsolete KLT basis in signal recovery. We validate our results with field experiments to detect multiple radio transmitters and sense the UHF spectrums using software-defined radios.

We present a novel application of deep learning in networking. The envisioned system can learn the original flow characteristics such as a burst size and inter-burst gaps conceived at the source from packet sampling done at a receiverWi-Fi node. This problem is challenging because CSMA introduces complex, irregular alterations to the origin pattern of the flow in the presence of competing flows. Our approach is semi-supervised learning. We first work through multiple layers of feature extraction and subsampling from unlabeled flow measurements.We use a feature extractor based on sparse coding and dictionary learning, and our subsampler performs overlapping max pooling. Given the layers of learned feature mapping, we train SVM classifiers with deep feature representation resulted at the top layer. The proposed scheme has been evaluated empirically in a custom wireless simulator and OPNET. The results are promising that we achieve superior classification performance over ARMAX, Naïve Bayes classifiers, and Gaussian mixture models optimized by the EM algorithm.

We introduce Deep Sparse-coded Network (DSN), a deep architecture based on sparse coding and dictionary learning. Key advantage of our approach is two-fold. By interlacing max pooling with sparse coding layer, we achieve nonlinear activation analogous to neural networks, but suffering less from diminished gradients. We use a novel backpropagation algorithm to finetune our DSN beyond the pretraining by layer-by-layer sparse coding and dictionary learning. We build an experimental 4-layer DSN with the 1-regularized LARS and greedy-0 OMP and demonstrate superior performance over deep stacked autoencoder on CIFAR-10.

Sparse linear models pose dual views toward data that are embodied in compressive sensing and sparse coding. Despite mathematical equivalence, compressive sensing and sparse coding are two different classes of application for sparse linear models. Compressive sensing draws recoverable, low-dimensional compressed representations from a blind linear projection on data. Sparse coding enables the discovery of structural patterns underlying data in forced decomposition with a given dictionary of basis vectors. Sparsity is the common constraint that makes exact recovery possible for compressive sensing and allows forced decomposition to unveil meaningful features for sparse coding.

In this thesis, I build on compressive sensing and sparse coding to explore the problems for reconstructive and discriminative applications in sensing, wireless networking, and machine learning. Specifically, I aim to develop recovery and feature learning methods robust to complex data transformations and alterations. With a wideband spectrum sensing application for cognitive radios, I empirically demonstrate the resiliency of the proposed sparse recovery technique to linear and nonlinear distortions present in the mix of heavily subsampled RF measurements. I push beyond best-known efficiency for distributed compressive sensing and show feasibility of scaling the spectrum sensing application with constant communications cost.

I also focus on learning sparse feature representations for discriminative machine learning tasks. I build a classification pipeline based on both single-layer and multilayer sparse coding trained on various modalities of data including text, image, and time series. To take advantage of possible higher-level construct of features in data, I propose a deep architecture on multilayer sparse coding, namely Deep Sparse-coded Network (DSN). When I train DSN with layer-by-layer dictionary learning followed by the proposed DSN backpropagation algorithm for image and time-series classification, it leads to performance better than deep stacked autoencoder neural network.

In addition, I present Nearest Neighbor Sparse Coding (NNSC), an enhancement for sparse coding by imposing the nearest neighbor constraint in the sparse feature domain. Despite inferior reconstructive error, NNSC improves the classification performance of classical sparse coding.