IINFCOM - Gestion

Institute

Related publications (95)

On the Efficiency of Polar-Like Decoding for Symmetric Codes

Kirill Ivanov, Rüdiger Urbanke

The recently introduced polar codes constitute a breakthrough in coding theory due to their capacity-achieving property. This goes hand in hand with a quasilinear construction, encoding, and successive cancellation list decoding procedures based on the Plotkin construction. The decoding algorithm can be applied with slight modifications to Reed-Muller or eBCH codes, that both achieve the capacity of erasure channels, although the list size needed for good performance grows too fast to make the decoding practical even for moderate block lengths. The key ingredient for proving the capacity-achieving property of Reed-Muller and eBCH codes is their group of symmetries. It can be plugged into the concept of Plotkin decomposition to design various permutation decoding algorithms. Although such techniques allow to outperform the straightforward polar-like decoding, the complexity stays impractical. In this paper, we show that although invariance under a large automorphism group is valuable in a theoretical sense, it also ensures that the list size needed for good performance grows exponentially. We further establish the bounds that arise if we sacrifice some of the symmetries. Although the theoretical analysis of the list decoding algorithm remains an open problem, our result provides an insight into the factors that impact the decoding complexity.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Watermarking-based Defense against Adversarial Attacks on Deep Neural Networks

James Richard Larus, Xiaoting Li, Dinghao Wu, Junjun Zhang

The vulnerability of deep neural networks to adversarial attacks has posed significant threats to real-world applications, especially security-critical ones. Given a well-trained model, slight modifications to the input samples can cause drastic changes in the predictions of the model. Many methods have been proposed to mitigate the issue. However, the majority of these defenses have proven to fail to resist all the adversarial attacks. This is mainly because the knowledge advantage of the attacker can help to either easily customize the information of the target model or create a surrogate model as a substitute to successfully construct the corresponding adversarial examples. In this paper, we propose a new defense mechanism that creates a knowledge gap between attackers and defenders by imposing a designed watermarking system into standard deep neural networks. The embedded watermark is data-independent and non-reproducible to an attacker, which improves randomization and security of the defense model without compromising performance on clean data, and thus yields knowledge disadvantage to prevent an attacker from crafting effective adversarial examples targeting the defensive model. We evaluate the performance of our watermarking defense using a wide range of watermarking algorithms against four state-of-the-art attacks on different datasets, and the experimental results validate its effectiveness.

IEEE2021

The Stability of Low-Density Parity-Check Codes and Some of its Consequences

Wei Liu, Rüdiger Urbanke

We study the stability of low-density parity-check codes under blockwise or bitwise maximum a posteriori decoding, where transmission takes place over a binary-input memoryless output-symmetric channel. Our study stems from the consideration of constructing universal capacity-achieving codes under low-complexity decoding algorithms, where universality refers to the fact that we are considering a family of channels with equal capacity. Consider, e.g., the right-regular sequence by Shokrollahi and the heavy-tail Poisson sequence by Luby et al. Both sequences are provably capacity-achieving under belief propagation decoding when transmission takes place over the binary erasure channel. In this paper we show that many existing capacity-achieving sequences of low-density parity-check codes are not universal under belief propagation decoding. We reveal that the key to showing this non-universality result is determined by the stability of the underlying codes. More concretely, for an ordered and complete channel family and a sequence of low-density parity-check code ensembles, we determine a stability threshold associated with them, which gives rise to a sufficient condition under which the sequence is not universal under belief propagation decoding. Moreover, we show that the same stability threshold applies to blockwise or bitwise maximum a posteriori decoding as well. We demonstrate how the stability threshold can determine an upper bound on the corresponding blockwise or bitwise maximum a posteriori threshold, revealing the operational significance of the stability threshold.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

On the Universality of Low-Density Parity-Check Block Codes

Wei Liu, Rüdiger Urbanke

An important class of modern channel codes is the capacity-achieving sequences of low-density parity-check block codes. Such sequences are usually designed for the binary erasure channel and are decoded by iterative message-passing algorithms. In this paper we investigate the universality of such sequences. We show that many existing capacity-achieving sequences designed for the binary erasure channel do not achieve the same capacity of many other binary-input memoryless output-symmetric channels under belief propagation decoding.

IEEE2020

, , , ,

Programming languages and systems have failed to address the security implications of the increasingly frequent use of public libraries to construct modern software. Most languages provide tools and online repositories to publish, import, and use libraries; however, this double-edged sword can incorporate a large quantity of unknown, unchecked, and unverified code into an application. The risk is real, as demonstrated by malevolent actors who have repeatedly inserted malware into popular open-source libraries. This paper proposes a solution: enclosures, a new programming language construct for library isolation that provides a developer with fine-grain control over the resources that a library can access, even for libraries with complex inter-library dependencies. The programming abstraction is language-independent and could be added to most languages. These languages would then be able to take advantage of hardware isolation mechanisms that are effective across language boundaries. The enclosure policies are enforced at run time by LitterBox, a language-independent framework that uses hardware mechanisms to provide uniform and robust isolation guarantees, even for libraries written in unsafe languages. LitterBox currently supports both Intel VT-x (with general-purpose extended page tables) and the emerging Intel Memory Protection Keys (MPK). We describe an enclosure implementation for the Go and Python languages. Our evaluation demonstrates that the Go implementation can protect sensitive data in real-world applications constructed using complex untrusted libraries with deep dependencies. It requires minimal code refactoring and incurs acceptable performance overhead. The Python implementation demonstrates LitterBox’s ability to support dynamic languages.

2021

Constructing a provably adversarially-robust classifier from a high accuracy one

Rüdiger Urbanke

Modern machine learning models with very high accuracy have been shown to be vulnerable to small, adversarially chosen perturbations of the input. Given black-box access to a high-accuracy classifier f, we show how to construct a new classifier g that has high accuracy and is also robust to adversarial L2-bounded perturbations. Our algorithm builds upon the framework of randomized smoothing that has been recently shown to outperform all previous defenses against L2-bounded adversaries. Using techniques like random partitions and doubling dimension, we are able to bound the adversarial error of g in terms of the optimum error. In this paper we focus on our conceptual contribution, but we do present two examples to illustrate our framework. We will argue that, under some assumptions, our bounds are optimal for these cases.

ADDISON-WESLEY PUBL CO2020

The ASPLOS 2020 Online Conference Experience: CS Pioneered It, Should We Use It?

James Richard Larus

2020

Improved decoding of second-order Reed-Muller codes

Kirill Ivanov, Rüdiger Urbanke

In this paper, we consider low-complexity decoding of second-order Reed-Muller codes. A class of polynomial-time algorithms, based on the projections onto first-order codes, is studied. An old representative of this class, originally developed for binary symmetric channel, is brought back to life and applied for AWGN channel. Some improvements are proposed, which bring the performance closer to ML bound with lower complexity compared to other algorithms. Another potentially fruitful property is returning the list of codewords. In addition, a simple method for complexity reduction and its impact on the performance are demonstrated.

IEEE2019

Dynamic program slicing can significantly reduce the amount of code developers need to inspect by focusing only on program statements relevant to their investigation. However, this technique is still not ready for production-level use either in terms of runtime or storage efficiency. We propose statistical program slicing, a novel hybrid dynamic-static slicing approach which explores the tradeoffs between runtime overhead, accuracy, and storage costs. Our technique relies on modern hardware support for control-flow tracing and selective heap memory instrumentation distributed across multiple executions, combined with static program analysis for data-flow tracking.

IEEE2019

, ,

We consider the primitive relay channel, where the source sends a message to the relay and to the destination, and the relay helps the communication by transmitting an additional message to the destination via a separate channel. Two well-known coding techniques have been introduced for this setting: decode-and-forward and compress-and-forward. In decode-and-forward, the relay completely decodes the message and sends some information to the destination; in compress-and-forward, the relay does not decode, and it sends a compressed version of the received signal to the destination using Wyner-Ziv coding. In this paper, we present a novel coding paradigm that provides an improved achievable rate for the primitive relay channel. The idea is to combine compress-and-forward and decode-and-forward via a chaining construction. We transmit over pairs of blocks: in the first block, we use compress-and-forward; and, in the second block, we use decode-and-forward. More specifically, in the first block, the relay does not decode, it compresses the received signal via Wyner-Ziv, and it sends only part of the compression to the destination. In the second block, the relay completely decodes the message, it sends some information to the destination, and it also sends the remaining part of the compression coming from the first block. By doing so, we are able to strictly outperform both compress-and-forward and decode-and-forward. Note that the proposed coding scheme can be implemented with polar codes. As such, it has the typical attractive properties of polar coding schemes, namely, quasi-linear encoding and decoding complexity, and error probability that decays at super-polynomial speed. As a running example, we take into account the special case of the erasure relay channel, and we provide a comparison between the rates achievable by our proposed scheme and the existing upper and lower bounds.

2019