Cryptographic approaches, such as secure multiparty computation, can be used to securely compute a function of a distributed graph without centralizing the data of each participant. However, the output of the protocol can leak sensitive information about the structure of the original graph. In particular, we propose an approach by which an adversary observing the result of a private protocol for the computation of the number of common neighbors between all pairs of vertices, can reconstruct the adjacency matrix of the graph. In fact, this can only be done up to co-squareness, a notion we introduce, as two different graphs can have the same matrix of common neighbors. To realize this, we consider two adversary models, one who observes the common neighbors matrix only and a more informed one that has partial knowledge of the original graph. Our results demonstrate that, from their common neighbors matrix, graphs can be reconstructed with high accuracy (up to co-squareness). The proposed reconstruction is also interesting in itself from the point of view of graph theory.

Insider threats are a growing concern for organizations due to the amount of damage that their members can inflict by combining their privileged access and domain knowledge. Nonetheless, the detection of such threats is challenging, precisely because of the ability of the authorized personnel to easily conduct malicious actions and because of the immense size and diversity of audit data produced by organizations in which the few malicious footprints are hidden. In this paper, we propose an unsupervised insider threat detection system based on audit data using Bayesian Gaussian Mixture Models. The proposed approach leverages a user-based model to optimize specific behaviors modelization and an automatic feature extraction system based on Word2Vec for ease of use in a real-life scenario. The solution distinguishes itself by not requiring data balancing nor to be trained only on normal instances, and by its little domain knowledge required to implement. Still, results indicate that the proposed method competes with state-of-the-art approaches that use stronger hypotheses, presenting a good recall of 88%, accuracy and true negative rate of 93%, and a false positive rate of 6.9%. For our experiments, we used the benchmark dataset CERT version 4.2.

Flow-sensitive labels used by dynamic enforcement mechanisms might themselves encode sensitive information, which can leak. Metalabels, employed to represent the sensitivity of labels, exhibit the same problem. This paper derives a new family of enforcers-k-Enf, for 2 ≤ k ≤ ∞-that uses label chains, where each label defines the sensitivity of its predecessor. These enforcers satisfy Block-safe Noninterference (BNI), which proscribes leaks from observing variables, label chains, and blocked executions. Theorems in this paper characterize where longer label chains can improve the permissiveness of dynamic enforcement mechanisms that satisfy BNI. These theorems depend on semantic attributes-k-precise, k-varying, and k-dependent-of such mechanisms, as well as on initialization, threat model, and lattice size.

Spam emails constitute a fast growing and costly problems associated with the Internet today. To fight effectively against spammers, it is not enough to block spam messages. Instead, it is necessary to analyze the behavior of spammer. This analysis is extremely difficult if the huge amount of spam messages is considered as a whole. Clustering spam emails into smaller groups according to their inherent similarity, facilitates discovering spam campaigns sent by a spammer, in order to analyze the spammer behavior. This paper proposes a methodology to group large sets of spam emails into spam campaigns, on the base of categorical attributes of spam messages. A new informative clustering algorithm, named Categorical Clustering Tree (CCTree), is introduced to cluster and characterize spam campaigns. The complexity of the algorithm is also analyzed and its efficiency has been proven.

Runtime monitoring is a widely used approach for the enforcement of security policies. It allows the safe execution of untrusted code by observing the execution and reacting if needed to prevent a violation of a user-defined security policy. Previous studies have determined that the set of security properties enforceable by monitors is greatly extended by giving the monitor some licence to transform its target execution. In this study, we present a new framework to model and study the behaviour of such monitors. In order to assure that the enforcement is meaningful, we bound the monitor's ability to transform the target execution by a restriction stating that any transformation must preserve equivalence between the monitor's input and output. We proceed by giving examples of meaningful equivalence relations and identify the security policies that are enforceable with their use. We also relate our work to previous work in this field. Finally, we investigate how an a priori knowledge of the target program's behaviour would increase the monitor's enforcement power.

Runtime monitoring is an increasingly popular method to ensure the safe execution of untrusted codes. Monitors observe and transform the execution of these codes, responding when needed to correct or prevent a violation of a user-defined security policy. Prior research has shown that the set of properties monitors can enforce correlates with the latitude they are given to transform and alter the target execution. But for enforcement to be meaningful this capacity must be constrained, otherwise the monitor can enforce any property, but not necessarily in a manner that is useful or desirable. However, such constraints have not been significantly addressed in prior work. In this article, we develop a new paradigm of security policy enforcement in which the behavior of the enforcement mechanism is restricted to ensure that valid aspects present in the execution are preserved notwithstanding any transformation it may perform. These restrictions capture the desired behavior of valid executions of the program, and are stated by way of a preorder over sequences. The resulting model is closer than previous ones to what would be expected of a real-life monitor, from which we demand a minimal footprint on both valid and invalid executions. We illustrate this framework with examples of real-life security properties. Since several different enforcement alternatives of the same property are made possible by the flexibility of this type of enforcement, our study also provides metrics that allow the user to compare monitors objectively and choose the best enforcement paradigm for a given situation.

Recently, attention has been given to formally characterize security policies that are enforceable by different kinds of security mechanisms. Since execution monitoring (EM) is a ubiquitous technique for enforcing security policies, this class of enforcement mechanisms has attracted the attention of the majority of authors characterizing security enforcement. A very important research problem is the characterization of security policies that are enforceable by execution monitors constrained by memory limitations. This paper contributes to give more precise answers to this research problem. To represent execution monitors constrained by memory limitations, we introduce a new class of automata that we call Bounded History Automata. Characterizing memory limitations gives rise to a precise taxonomy of security policies enforceable under such constraints.This work is in the same line as the research work advanced by Schneider [31], Ligatti et. al [1, 21] and Fong [12] on security enforcement. Our main contribution consists in (1) instantiating Fong's abstraction idea to deal with memory-limitations, (2) defining Bounded History Automata by applying our abstraction to both security automata and edit automata [1], and (3) Reasoning about the enforcement power of bounded history automata by investigating the enforcement of locally testable properties; a well studied class of languages that are recognizable by investigating local information. Our approach gives rise to a realistic evaluation of the enforcement power of execution monitoring. This evaluation is based on bounding the memory size used by the monitor to save execution history, and identifying the security policies enforceable under such constraint.

We address the formal analysis of authentication cryptographic protocols. We present a new verification algorithm that generates from the protocol description the set of possible flaws, if any, as well as the corresponding attack scenarios. This algorithm does not require any property or invariant specification. The algorithm involves three steps: extracting the protocol roles, modeling the intruder abilities and verification. In addition to the classical known intruder computational abilities such as encryption and decryption, we also consider those computations that result from different instrumentations of the protocol. The intruder abilities are modeled as a deductive system. The verification is based on the extracted roles as well as the deductive system. It consists in checking whether the intruder can answer all the challenges uttered by a particular role. If it is the case, an attack scenario is automatically constructed. The extracted proof system does not ensure the termination of deductions. For that purpose, we present a general transformation schema that allows one to automatically rewrite the non-terminating proof system into a terminating one. The transformation schema is shown to be correct. To exemplify the usefulness and efficiency of our approach, we illustrate it on the Woo and Lam (1992) authentication protocol. Abadi and Needham have shown that the protocol is insecure and they proposed a new corrected version. Thanks to this method we have discovered new unknown flaws in the Woo and Lam protocol and in the corrected version of Abadi and Needham.

This paper is concerned with the automatic exploitation of the parallelism detected in a sequential program. The target machine is a shared memory multiprocessor.