Causality analysis generates a dependency graph from system audit logs, which has emerged as an important solution for attack investigation. In the dependency graph, nodes represent system entities (e.g., processes and files) and edges represent dependencies among entities (e.g., a process writing to a file). Despite the promising early results, causality analysis often produces a large graph (> 100,000 edges) and it is a daunting task for security analysts to inspect such a large graph for attack investigation. To address challenges in attack investigation, we propose DEPCOMM, a graph summarization approach that generates a summary graph from a dependency graph by partitioning a large graph into process-centric communities and presenting summaries for each community. Specifically, each community consists of a set of intimate processes that cooperate with each other to accomplish certain system activities (e.g., file compression), and the resources (e.g., files) accessed by these processes. Within a community, DEPCOMM further identifies redundant edges caused by less-important and repetitive system activities, and perform compression on these edges. Finally, DEPCOMM generates the summary for each community using the InfoPaths that represent the information flows across communities. These InfoPaths are more likely to capture a set of attack-related processes that work together to achieve certain malicious goals. Our evaluations on real attacks ($\sim 150$ million events) demonstrate that DEPCOMM generates 18.4 communities on average for a dependency graph, which is $\sim 70 \times$ smaller than the original graph. Our compression further reduces the edges in each community to 32.1 on average. Compared with the 9 state-of-the-art community detection algorithms, on average, DEPCOMM achieves a $2.29\times$ better F1-score than these algorithms in detecting communities. Through cooperating with the automatic techniques HOLMES, DEPCOMM can identify attack-related communities by a recall of 96.2%. Our case studies on the real attacks also demonstrate DEPCOMM’s effectiveness in facilitating attack investigation.

Suppose that y = |Ax0| + η where x0∈ Rdis the target signal and η ∈ Rmis a noise vector. The aim of phase retrieval is to estimate x0from y. A popular model for estimating x0is the nonlinear least squares x̂ := argminx|||Ax| - y||2. One has already developed many efficient algorithms for solving the model, such as the seminal error reduction algorithm. In this paper, we present the estimation performance of the model with proving that ||x̂ - x0|| ≲ ||η||2/√m under the assumption of A being a Gaussian random matrix. We also prove the reconstruction error ||η||2/√m is sharp. For the case where x0is sparse, we study the estimation performance of both the nonlinear Lasso of phase retrieval and its unconstrained version. Our results are non-asymptotic, and we do not assume any distribution on the noise η. To the best of our knowledge, our results represent the first theoretical guarantee for the nonlinear least squares and for the nonlinear Lasso of phase retrieval.

The class of Fourier matrices is of special importance in compressed sensing (CS). This paper concerns deterministic construction of CS matrices from Fourier matrices. Using Katz' character sum estimation, we are able to design a deterministic procedure to select rows from a Fourier matrix to form a good CS matrix for sparse recovery. The sparsity bound in our construction is similar to that of binary CS matrices constructed by DeVore, which greatly improves previous results for CS matrices from Fourier matrices. Our approach also provides more flexibility in terms of the dimension of CS matrices. This paper also contains a useful improvement to Katz' character sum estimation for quadratic extensions, with an elementary and transparent proof. Based on this improvement, we construct a class of special CS matrices consisting of partial Fourier matrices whose columns are a union of orthonormal bases. As a consequence, our construction yields an approximately mutually unbiased bases from Fourier matrices which is of particular interest to quantum information theory. Some numerical examples are also included.