OpenRaiser/Intern-Atlas huggingface dataset:
Blockchain Trilemma Solver Algorand has Dilemma over Undecidable Messages
Venue: arXiv cs.CR 2019
Year: 2019

Recently, an ingenious protocol called Algorand has been proposed to overcome these limitations. Algorand uses an innovative process - called cryptographic sortition - to securely and unpredictably elect a set of voters from the network periodically. These voters are responsible for reaching consensus through a Byzantine Agreement (BA) protocol on one block per time, guaranteeing an overwhelming probability of linearity of the blockchain. In this paper, we present a security analysis of Algorand. To the best of our knowledge, it is the first security analysis as well as the first formal study on Algorand. We designed an attack scenario in which a group of malicious users tries to break the protocol, or at least limiting it to a reduced partition of network users, by exploiting a possible security flaw in the messages validation process of the BA. Since the source code or an official simulator for Algorand was not available at the time of our study, we created a simulator (which is available on request) to implement the protocol and assess the feasibility of our attack scenario. Our attack requires the attacker to have a trivial capability of establishing multiple connections with targeted nodes and costs practically nothing to the attacker. Our results show that it is possible to slow down the message validation process on honest nodes, which eventually forces them to choose default values on the consensus; leaving the targeted nodes behind in the chain as compared to the non-attacked nodes. Even though our results are subject to the real implementation assumption, the core concept of our attack remains valid.
Heterogeneous Network Motifs
Venue: arXiv cs.SI 2019
Year: 2019

Many real-world applications give rise to large heterogeneous networks where nodes and edges can be of any arbitrary type (e.g., user, web page, location). Special cases of such heterogeneous graphs include homogeneous graphs, bipartite, k-partite, signed, labeled graphs, among many others. In this work, we generalize the notion of network motifs to heterogeneous networks. In particular, small induced typed subgraphs called typed graphlets (heterogeneous network motifs) are introduced and shown to be the fundamental building blocks of complex heterogeneous networks. Typed graphlets are a powerful generalization of the notion of graphlet (network motif) to heterogeneous networks as they capture both the induced subgraph of interest and the types associated with the nodes in the induced subgraph. To address this problem, we propose a fast, parallel, and space-efficient framework for counting typed graphlets in large networks. We discover the existence of non-trivial combinatorial relationships between lower-order ($k-1$)-node typed graphlets and leverage them for deriving many of the $k$-node typed graphlets in $o(1)$ constant time. Thus, we avoid explicit enumeration of those typed graphlets. Notably, the time complexity matches the best untyped graphlet counting algorithm. The experiments demonstrate the effectiveness of the proposed framework in terms of runtime, space-efficiency, parallel speedup, and scalability as it is able to handle large-scale networks.
DeClassifier: Class-Inheritance Inference Engine for Optimized C++ Binaries
Venue: arXiv cs.CR 2019
Year: 2019

Recovering class inheritance from C++ binaries has several security benefits including problems such as decompilation and program hardening. Thanks to the optimization guidelines prescribed by the C++ standard, commercial C++ binaries tend to be optimized. While state-of-the-art class inheritance inference solutions are effective in dealing with unoptimized code, their efficacy is impeded by optimization. Particularly, constructor inlining--or worse exclusion--due to optimization render class inheritance recovery challenging. Further, while modern solutions such as MARX can successfully group classes within an inheritance sub-tree, they fail to establish directionality of inheritance, which is crucial for security-related applications (e.g. decompilation). We implemented a prototype of DeClassifier using Binary Analysis Platform (BAP) and evaluated DeClassifier against 16 binaries compiled using gcc under multiple optimization settings. We show that (1) DeClassifier can recover 94.5% and 71.4% true positive directed edges in the class hierarchy tree under O0 and O2 optimizations respectively, (2) a combination of ctor+dtor analysis provides much better inference than ctor only analysis.
Cloud-Net: An end-to-end Cloud Detection Algorithm for Landsat 8 Imagery
Venue: arXiv cs.CV 2019
Year: 2019

Cloud detection in satellite images is an important first-step in many remote sensing applications. This problem is more challenging when only a limited number of spectral bands are available. To address this problem, a deep learning-based algorithm is proposed in this paper. This algorithm consists of a Fully Convolutional Network (FCN) that is trained by multiple patches of Landsat 8 images. This network, which is called Cloud-Net, is capable of capturing global and local cloud features in an image using its convolutional blocks. Since the proposed method is an end-to-end solution, no complicated pre-processing step is required. Our experimental results prove that the proposed method outperforms the state-of-the-art method over a benchmark dataset by 8.7\% in Jaccard Index.
Fully-functional bidirectional Burrows-Wheeler indexes
Venue: arXiv cs.DS 2019
Year: 2019

Given a string $T$ on an alphabet of size $σ$, we describe a bidirectional Burrows-Wheeler index that takes $O(|T|\logσ)$ bits of space, and that supports the addition \emph{and removal} of one character, on the left or right side of any substring of $T$, in constant time. Previously known data structures that used the same space allowed constant-time addition to any substring of $T$, but they could support removal only from specific substrings of $T$. We also describe an index that supports bidirectional addition and removal in $O(\log{\log{|T|}})$ time, and that occupies a number of words proportional to the number of left and right extensions of the maximal repeats of $T$. We use such fully-functional indexes to implement bidirectional, frequency-aware, variable-order de Bruijn graphs in small space, with no upper bound on their order, and supporting natural criteria for increasing and decreasing the order during traversal.
On Decoding and Applications of Interleaved Goppa Codes
Venue: arXiv cs.IT 2019
Year: 2019

Goppa Codes are a well-known class of codes with, among others, applications in code-based cryptography. In this paper, we present a collaborative decoding algorithm for interleaved Goppa codes (IGC). Collaborative decoding increases the decoding radius beyond half of the designed minimum distance. We consider wild Goppa codes and show that we can collaboratively correct more errors for binary Goppa codes than the Patterson decoder. We propose a modified version of the McEliece cryptosystem using wild IGC based on a recently proposed system by Elleuch et al., analyze attacks on the system and present some parameters with the corresponding key sizes.
Approximating Spectral Clustering via Sampling: a Review
Venue: arXiv cs.LG 2019
Year: 2019

Spectral clustering refers to a family of unsupervised learning algorithms that compute a spectral embedding of the original data based on the eigenvectors of a similarity graph. This non-linear transformation of the data is both the key of these algorithms' success and their Achilles heel: forming a graph and computing its dominant eigenvectors can indeed be computationally prohibitive when dealing with more that a few tens of thousands of points. In this paper, we review the principal research efforts aiming to reduce this computational cost. We focus on methods that come with a theoretical control on the clustering performance and incorporate some form of sampling in their operation. Such methods abound in the machine learning, numerical linear algebra, and graph signal processing literature and, amongst others, include Nyström-approximation, landmarks, coarsening, coresets, and compressive spectral clustering. We present the approximation guarantees available for each and discuss practical merits and limitations. Surprisingly, despite the breadth of the literature explored, we conclude that there is still a gap between theory and practice: the most scalable methods are only intuitively motivated or loosely controlled, whereas those that come with end-to-end guarantees rely on strong assumptions or enable a limited gain of computation time.
Secure selections on encrypted multi-writer streams
Venue: arXiv cs.CR 2019
Year: 2019

Performing searches over encrypted data is a very current and active area. Several efficient solutions have been provided for the single-writer scenario in which all sensitive data originates with one party (the Data Owner) that encrypts it and uploads it to a public repository. Subsequently the Data Owner (or authorized clients, the Query Sources) accesses the encrypted data through a Query Processor which has direct access to the public encrypted repository. Motivated by the recent trend in pervasive data collection, we depart from this model and consider a multi-writer scenario in which data originates with several and mutually untrusted parties. In this new scenario the Data Owner provides public parameters so that each item of the generated data stream can be put into an encrypted stream; moreover, the Data Owner keeps some related secret information needed to generate tokens so that different subscribers can access different subsets of the encrypted stream in clear, as specified by corresponding access policies. We propose a new public-key scheme, Secure Selective Stream (SSS), built upon an Amortized Encryption Scheme (AOE), that can be used to encrypt each item in the stream so that the ciphertexts have size proportional to the un-encrypted data; moreover, encryption and decryption take time linear in the data item size. We provide constructions for SSS and AOE. We provide a game-based and an indistinguishability-based security notions for SSS, we prove that the SSS scheme is game-base secure given that the AOE scheme is game-based secure as well. We prove that AOE is secure under hardness assumptions in the bilinear setting. We provide an implementation in C++ all the basic operations in our multi-writer scenario using one round of communication.
Automatic Whole-body Bone Age Assessment Using Deep Hierarchical Features
Venue: arXiv cs.CV 2019
Year: 2019

Bone age assessment gives us evidence to analyze the children growth status and the rejuvenation involved chronological and biological ages. All the previous works consider left-hand X-ray image of a child in their works. In this paper, we carry out a study on estimating human age using whole-body bone CT images and a novel convolutional neural network. Our model with additional connections shows an effective way to generate a massive number of vital features while reducing overfitting influence on small training data in the medical image analysis research area. A dataset and a comparison with common deep architectures will be provided for future research in this field.
Learning for Multi-Model and Multi-Type Fitting
Venue: arXiv cs.CV 2019
Year: 2019

Multi-model fitting has been extensively studied from the random sampling and clustering perspectives. Most assume that only a single type/class of model is present and their generalizations to fitting multiple types of models/structures simultaneously are non-trivial. The inherent challenges include choice of types and numbers of models, sampling imbalance and parameter tuning, all of which render conventional approaches ineffective. In this work, we formulate the multi-model multi-type fitting problem as one of learning deep feature embedding that is clustering-friendly. In other words, points of the same clusters are embedded closer together through the network. For inference, we apply K-means to cluster the data in the embedded feature space and model selection is enabled by analyzing the K-means residuals. Experiments are carried out on both synthetic and real world multi-type fitting datasets, producing state-of-the-art results. Comparisons are also made on single-type multi-model fitting tasks with promising results as well.
Multi-UAV Visual Coverage of Partially Known 3D Surfaces: Voronoi-based Initialization to Improve Local Optimizers
Venue: arXiv cs.RO 2019
Year: 2019

In this paper we study the problem of steering a team of Unmanned Aerial Vehicles (UAVs) toward a static configuration which maximizes the visibility of a 3D environment. The UAVs are assumed to be equipped with visual sensors constrained by a maximum sensing range and the prior knowledge on the environment is considered to be very sparse. To solve this problem on-line, derivative-free measurement-based optimization algorithms can be adopted, even though they are strongly limited by local optimality. To overcome this limitation, we propose to exploit the partial initial knowledge on the environment to find suitable initial configurations from which the agents start the local optimization. In particular, a constrained centroidal Voronoi tessellation on a coarse approximation of the surface to cover is proposed. The behavior of the agent is so based on a two-step optimization approach, where a stochastic optimization algorithm based on the on-line acquired information follows the geometrical-based initialization. The algorithm performance is evaluated in simulation and in particular the improvement on the solution brought by the Voronoi tessellation with respect to different initializations is analyzed.
Private Polynomial Computation for Noncolluding Coded Databases
Venue: arXiv cs.IT 2019
Year: 2019

We consider private polynomial computation (PPC) over noncolluding coded databases. In such a setting a user wishes to compute a multivariate polynomial of degree at most $g$ over $f$ variables (or messages) stored in multiple databases while revealing no information about the desired polynomial to the databases. We construct two novel PPC schemes, where the first is a generalization of our previous work in private linear computation for coded databases. In this scheme we consider Reed-Solomon coded databases with Lagrange encoding, which leverages ideas from recently proposed star-product private information retrieval and Lagrange coded computation. The second scheme considers the special case of coded databases with systematic Lagrange encoding. Both schemes yield improved rates compared to the best known schemes from the literature for a small number of messages, while in the asymptotic case the rates match.
Quality Measures for Speaker Verification with Short Utterances
Venue: arXiv cs.CV 2019
Year: 2019

The performances of the automatic speaker verification (ASV) systems degrade due to the reduction in the amount of speech used for enrollment and verification. Combining multiple systems based on different features and classifiers considerably reduces speaker verification error rate with short utterances. This work attempts to incorporate supplementary information during the system combination process. We use quality of the estimated model parameters as supplementary information. We introduce a class of novel quality measures formulated using the zero-order sufficient statistics used during the i-vector extraction process. We have used the proposed quality measures as side information for combining ASV systems based on Gaussian mixture model-universal background model (GMM-UBM) and i-vector. The proposed methods demonstrate considerable improvement in speaker recognition performance on NIST SRE corpora, especially in short duration conditions. We have also observed improvement over existing systems based on different duration-based quality measures.
Universal Dependency Parsing from Scratch
Venue: arXiv cs.CL 2019
Year: 2019

This paper describes Stanford's system at the CoNLL 2018 UD Shared Task. We introduce a complete neural pipeline system that takes raw text as input, and performs all tasks required by the shared task, ranging from tokenization and sentence segmentation, to POS tagging and dependency parsing. Our single system submission achieved very competitive performance on big treebanks. Moreover, after fixing an unfortunate bug, our corrected system would have placed the 2nd, 1st, and 3rd on the official evaluation metrics LAS,MLAS, and BLEX, and would have outperformed all submission systems on low-resource treebank categories on all metrics by a large margin. We further show the effectiveness of different model components through extensive ablation studies.
Big Data Platform Architecture Under The Background of Financial Technology
Venue: arXiv cs.CY 2019
Year: 2019

With the rise of the concept of financial technology, financial and technology gradually in-depth integration, scientific and technological means to become financial product innovation, improve financial efficiency and reduce financial transaction costs an important driving force. In this context, the new technology platform is from the business philosophy, business model, technical means, sales, internal management, and other dimensions to re-shape the financial industry. In this paper, the existing big data platform architecture technology innovation, adding space-time data elements, combined with the insurance industry for practical analysis, put forward a meaningful product circle and customer circle.
Abstract I/O Specification
Venue: arXiv cs.LO 2019
Year: 2019

We recently proposed an approach for the specification and modular formal verification of the interactive (I/O) behavior of programs, based on an embedding of Petri nets into separation logic. While this approach is scalable and modular in terms of the I/O APIs available to a program, enables composing low-level I/O actions into high-level ones, and enables a convenient verification experience, it does not support high-level I/O actions that involve memory manipulation as well as low-level I/O (such as buffered I/O), or that are in fact "virtual I/O" actions that are implemented purely through memory manipulation. Furthermore, it does not allow rewriting an I/O specification into an equivalent one. In this paper, we propose a refined approach that does have these properties. The essential insight is to fix the set of places of the Petri net to be the set of separation logic assertions, thus making available the full power of separation logic for abstractly stating an arbitrary operation's specification in Petri net form, for composing operations into an I/O specification, and for equivalence reasoning on I/O specifications. Our refinement resolves the issue of the justification of the choice of Petri nets over other formalisms such as general state transition systems, in that it "refines them away" into the more essential constructs of separating conjunction and abstract nested triples. To enable a convenient treatment of input operations, we propose the use of prophecy variables to eliminate their non-determinism. We illustrate the approach through a number of example programs, including one where subroutines specified and verified using I/O specifications run as threads communicating through shared memory. The theory and examples of the paper have been machine-checked using the Iris library for program verification in the Coq proof assistant.
Smart contracts for the Internet of Things: opportunities and challenges
Venue: arXiv cs.CY 2019
Year: 2019

With the Internet of Things (IoT), Things are expected to live in different "domains" and "contexts" during their lifetime. Information generated by and associated with Things should be manageable by multiple, diverse stakeholders accordingly. Moreover, the scope of the information related to Things can range from private and confidential to public and auditable. Identification, security, and interoperability in this vivid environment are expected to be challenging. In this paper we discuss how smart contracts and blockchain technologies create the potential for a viable solution. To this end, we present smart contract-based solutions that improve security and information management, we identify new opportunities and challenges, and we provide security recommendations and guidelines.
Throttling Malware Families in 2D
Venue: arXiv cs.CR 2019
Year: 2019

Malicious software are categorized into families based on their static and dynamic characteristics, infection methods, and nature of threat. Visual exploration of malware instances and families in a low dimensional space helps in giving a first overview about dependencies and relationships among these instances, detecting their groups and isolating outliers. Furthermore, visual exploration of different sets of features is useful in assessing the quality of these sets to carry a valid abstract representation, which can be later used in classification and clustering algorithms to achieve a high accuracy. In this paper, we investigate one of the best dimensionality reduction techniques known as t-SNE to reduce the malware representation from a high dimensional space consisting of thousands of features to a low dimensional space. We experiment with different feature sets and depict malware clusters in 2-D. Surprisingly, t-SNE does not only provide nice 2-D drawings, but also dramatically increases the generalization power of SVM classifiers. Moreover, obtained results showed that cross-validation accuracy is much better using the 2-D embedded representation of samples than using the original high-dimensional representation.
Universally Decodable Matrices for Distributed Matrix-Vector Multiplication
Venue: arXiv cs.IT 2019
Year: 2019

Coded computation is an emerging research area that leverages concepts from erasure coding to mitigate the effect of stragglers (slow nodes) in distributed computation clusters, especially for matrix computation problems. In this work, we present a class of distributed matrix-vector multiplication schemes that are based on codes in the Rosenbloom-Tsfasman metric and universally decodable matrices. Our schemes take into account the inherent computation order within a worker node. In particular, they allow us to effectively leverage partial computations performed by stragglers (a feature that many prior works lack). An additional main contribution of our work is a companion matrix-based embedding of these codes that allows us to obtain sparse and numerically stable schemes for the problem at hand. Experimental results confirm the effectiveness of our techniques.
Lower Bound on the Sum-rate of Decremental Beam Selection Algorithm for Beamspace MIMO Systems
Venue: arXiv cs.IT 2019
Year: 2019

In general, the zero-forcing (ZF) precoding suffers from a severe receive signal-to-noise ratio (SNR) degradation in the high interference regime. However, recent evidences from realistic measurements demonstrated that millimeter wave (mmWave) systems are mainly noise-limited as high gain antennas behave as spatial filters to the interference signal. This makes ZF precoding equally attractive as that of other linear precoding counterparts. Considering ZF precoding, this paper aims to derive a lower bound on the sum-rate achieved by a decremental beam selection (BS) algorithm in a beamspace MIMO (B-MIMO) system operating at mmWave frequencies. This bound relates Frobenious norms of precoding matrices of full and reduced dimensional (i.e. after BS) B-MIMO systems through a deterministic square-hyperbolic function. Note that, both ZF precoding and decremental BS are not new concepts. However, the derived sum-rate bound provides a new insight to the topic. Given a particular full dimensional B-MIMO channel, the presented bound can be used to understand limits of BS algorithms.