In this paper, we introduce POPPY, a novel suite of privacy-preserving algorithms designed for computing spectral centrality measures over graphs distributed across mutually distrustful data centers. POPPY is the first approach that achieves together generality, accuracy, and scalability with respect to the number of participants. POPPY uses the CKKS fully homomorphic encryption scheme to support the arithmetic division operation over ciphertexts. POPPY consists of three variants: POPPYs, optimized for sparse graphs using SIMD operations; POPPYd, tailored for dense graphs through efficient encrypted matrix-vector multiplication; and POPPYh, a hybrid between POPPYs and POPPYd for coping with contexts involving a large number of remote nodes. In addition to its core algorithms, POPPY comes with a pruning strategy based on a new notion of node equivalence called INC-equivalence. Pruning is indeed of utmost importance when using fully homomorphic encryption in order to minimize the number of encrypted operations performed. The INC-equivalence notion allows us to eliminate redundant nodes efficiently and without any impact on the accuracy of the centrality scores. Our comprehensive theoretical analysis and empirical evaluation on real-world and synthetic datasets demonstrate that POPPY achieves together generality, accuracy, and scalability.

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.

The growing need for secure computation has spurred interest in cryptographic techniques that operate on encrypted data without revealing its content. Fully Homomorphic Encryption (FHE), especially LWE-based schemes, enables such processing while preserving confidentiality. Decentralized computing offers scalable resources without requiring in-house servers, but it relies heavily on the confidentiality guarantees of underlying schemes. While many existing protocols successfully protect input privacy, function confidentiality remains a largely overlooked but crucial aspect of secure delegated computation.In this work, we present a novel Oblivious Universal Function (OUF) scheme that enables a client to outsource computation of an arbitrary function to an untrusted server while hiding both the input data and the function being applied. Our construction leverages LWE-based FHE and a virtual-tape evaluation model to support composable, non-interactive, and reusable function execution. Crucially, the server remains oblivious not only to the encrypted inputs but also to the structure, type, and identity of the function it is executing. OUF thus bridges the gap between theoretical privacy guarantees and practical secure computation in decentralized environments.

In this paper, we introduce an adaptation of the counting sort algorithm that leverages the data obliviousness of the algorithm to enable the sorting of encrypted data using Fully Homomorphic Encryption (FHE). Our approach represents the first known sorting algorithm for encrypted data that does not rely on comparisons. The implementation takes advantage of some basic operations on TFHE's Look-Up-Tables (LUT). We have integrated these operations into RevoLUT, a comprehensive open-source library built on tfhe-rs. We demonstrate the effectiveness of our Blind Counting Sort algorithm by developing a top-k selection algorithm and applying it to privacy-preserving k-Nearest Neighbors classification. This proves to be approximately 4 times faster than state-of-the-art methods.

Graphs are a widely used data structure for collecting and analyzing relational data. However, when the graph structure is distributed across several parties, its analysis is challenging. In particular, due to the sensitivity of the data each party might want to keep their partial knowledge of the graph private, while still be willing to collaborate with the other parties for tasks of mutual benefit, such as data curation or the removal of poisoned data. To address this challenge, we propose Crypto'Graph, an efficient protocol for privacy-preserving link prediction on distributed graphs. More precisely, it allows parties partially sharing a graph with distributed links to infer the likelihood of formation of new links in the future. Through the use of cryptographic primitives, Crypto'Graph is able to compute the likelihood of these new links on the joint network without revealing the structure of the private graph of each party, even though they know the number of nodes they have, since they share the same graph in terms of nodes but not the same links. Crypto'Graph improves on previous works by enabling the computation of a diverse set of similarity metrics in parallel without any additional cost. The use of Crypto'Graph is illustrated for defense against graph poisoning attacks, in which potential adversarial links are identified without compromising the privacy of the graphs of individual parties. The effectiveness of Crypto'Graph in mitigating graph poisoning attacks and achieving high prediction accuracy on a node classification task using graph neural networks is demonstrated through extensive experimentation on two real-world datasets.

Ridesharing, in which drivers offer to share their rides, allows reduction of travel costs for both drivers and riders; such practice is increasingly popular. Modern ridesharing systems, enhanced with location-based features, have improved user experience by enabling drivers and riders to arrange a trip in near real time. However, the fine-grained nature of location data collected by the service providers and exchanged between users raises privacy issues that could disrupt the adoption of such systems. In this paper, we present SRide: a privacy-preserving protocol for ridesharing that addresses the matching problem for dynamic ridesharing systems. We design and implement a prototype of SRide that operates in four steps. First, it generalizes users spatiotemporal data of users. Next, it relies on a secure filtering protocol to compute feasible matches. Then, it uses an improved version of Priv-2SP-SP- a privacy-preserving protocol to compute meeting points for ridesharing- to compute a ridesharing score for each feasible pair. Finally, it computes the optimal assignment of drivers and riders based on their ridesharing scores. We conduct an experimental trace-driven evaluation of the proposed scheme to demonstrate its practical feasibility.

Abstract A Private Information Retrieval (PIR) scheme is a protocol in which a user retrieves a record from a database while hiding which from the database administrators. PIR can be achieved using mutuallydistrustful replicated databases, trusted hardware, or cryptography. In this paper we focus on the later setting which is known as single-database computationally- Private Information Retrieval (cPIR). Classic cPIR protocols require that the database server executes an algorithm over all the database content at very low speeds which impairs their usage. In [1], given certain assumptions, realistic at the time, Sion and Carbunar showed that cPIR schemes were not practical and most likely would never be. To this day, this conclusion is widely accepted by researchers and practitioners. Using the paradigm shift introduced by lattice-based cryptography, we show that the conclusion of Sion and Carbunar is not valid anymore: cPIR is of practical value. This is achieved without compromising security, using standard crytosystems, and conservative parameter choices.

This paper presents a methodology to guide the evaluation of social distributed applications in mobile environments. Even when applications are already designed, they exhibit a number of tuning parameters upon which network operators can act in order to improve performance. Accordingly, evaluation can be a valuable tool to determine for a particular mobile application which is the most suitable parameters setup from a performance point of view. Our methodology can be of great interest in this tuning process, thus saving both time and money. The main novelty of this methodology is the use of diversification to recreate mobile environments using both synthetic and real mobility traces. Our work focuses on how micro-mobility may impact social distributed applications. The feasibility of the paper is showed through a realistic microblogging case study.

A secure location-based service requires that a mobile user certifies his position before gaining access to a resource. Currently, most of the existing solutions addressing this issue assume a trusted third party that can vouch for the position claimed by a user. However, as computation and communication capacities become ubiquitous with the large scale adoption of smartphones by individuals, we propose to leverage on these resources to solve this issue in a collaborative and private manner. More precisely, we introduce PROPS, for PRivacy-preserving lOcation Proof System, which allows users to generate proofs of location in a private and distributed way using neighboring nodes as witnesses. PROPS provides security properties such as unforgeability and non-transferability of the proofs, as well as resistance to classical localization attacks.

Carpooling is an appropriate solution to address traffic congestion and to reduce the ecological footprint of the car use. In this paper, we address an essential problem for providing dynamic carpooling: how to compute the shortest driver's and passenger's paths. Indeed, those two paths are synchronized in the sense that they have a common subpath between two points: the location where the passenger is picked up and the one where he is dropped off the car. The passenger path may include time-dependent public transportation parts before or after the common subpath. This defines the 2 Synchronization Points Shortest Path Problem (2SPSPP). We show that the 2SPSPP has a polynomial worst-case complexity. However, despite this polynomial complexity, one needs efficient algorithms to solve it in realistic transportation networks. We focus on efficient computation of optimal itineraries for solving the 2SPSPP, i.e. determining the (optimal) pick-up and drop-off points and the two synchronized paths that minimize the total traveling time. We also define restriction areas for reasonable pick-up and drop-off points and use them to guide the algorithms using heuristics based on landmarks. Experiments are conducted on real transportation networks. The results show the efficiency of the proposed algorithms and the interest of restriction areas for pick-up or drop-off points in terms of CPU time, in addition to its application interest.

Simulating human-centered pervasive systems requires accurate assumptions on the behavior of human groups. Recent models consider this behavior as a combination of both social and spatial factors. Yet, establishing accurate traces of human groups is difficult: current techniques capture either positions, or contacts, with a limited accuracy.

In this paper, we present a middleware architecture for dependable mobile systems and an experimentation platform for its evaluation. The proposed architecture includes three building blocks tailored for mobile cooperative applications: a Proximity Map, a Trust and Cooperation Oracle, and a Cooperative Data Backup service. To illustrate our platform, we developed a Distributed Black-box application, whose aim is to record critical data while tolerating the failure of a node, and implemented a hardware evaluation platform of mobile systems for experimenting with the application. We provide here some insights on the development of the platform, focusing on wireless communication emulation via signal attenuation.

New automotive modular multi-layered software organization particularly favors use and interoperability of components-off-the-shelf. However, the integration of software components is error-prone, if their coordination is not rigorously controlled. The risk of failure is increased with the possibility to multiplex software components with heterogeneous levels of criticality, observability. Most of dependability mechanisms, today, address locally errors within each component or report them to further diagnosis services. Instead, we consider a global wrapping-based approach to deal with multilevel properties to be checked on the complete multilayered system at runtime. In this paper, we introduce a framework to design robust software, from analysis to implementation issues, and we illustrate the methodology on simple case study.

In this work, we present a platform for testing algorithms on mobile systems. We advocate that the interest of the platform lies in many aspects: it shows that simulators are not accurate, especially with regards to wireless communication and delays assumptions. Such a platform can be used to refine simulators assumptions. Moreover, to the best of our knowledge, our platform is the first attempt to implement mobility patterns, that permit to test multiple distributed algorithms in the same movement configuration, allowing for reproducible experiments. Last, but not least, we want to open our platform to test other distributed and mobile algorithms, with the hope that it will open new problems and pose new challenges.

Abstract In this paper we present COSMOPEN, a reverse‐engineering tool optimized for the behavioural analysis of complex layered software. COSMOPENcombines cheap and non‐intrusive observation techniques with a versatile graph manipulation engine. By programming different graph manipulation scripts, the ‘focal length’ of our tool can be adapted to different abstraction levels. We illustrate how our tool can be used to extract high‐level behavioural models from a complex multi‐threaded platform (GNU/Linux, CORBA middleware). Copyright © 2009 John Wiley & Sons, Ltd.

The evolution of systems during operational lifetime is becoming a core assumption of the design. This is the case for resource constrained embedded systems. Such an evolution may be driven by environment or the execution context. The adequacy of the service delivery with respect to the current operational conditions depends on the ability to tune the software configuration accordingly. This is true for application services, but also for dependability services, in particular the fault tolerance software. This paper presents a design of fault tolerance software for its runtime adaptation. This design relies on a reflective framework and open component based software engineering (CBSE) techniques. We demonstrate in this paper the feasibility of adapting componentized fault tolerance at a meta-level of the application.

Autonomous robots offer alluring perspectives in numerous application domains: space rovers, satellites, medical assistants, tour guides, etc. However, a severe lack of trust in their dependability greatly reduces their possible usage. In particular, autonomous systems make extensive use of decisional mechanisms that are able to take complex and adaptative decisions, but are very hard to validate. This paper proposes a fault tolerance approach for decisional planning components, which are almost mandatory in complex autonomous systems. The proposed mechanisms focus on development faults in planning models and heuristics, through the use of diversification. The paper presents an implementation of these mechanisms on an existing autonomous robot architecture, and evaluates their impact on performance and reliability through the use of fault injection.

Mobile devices (e.g., laptops, PDAs, cell phones) are increasingly relied on but are used in contexts that put them at risk of physical damage, loss or theft. This paper discusses the dependability evaluation of a cooperative backup service for mobile devices. Participating devices leverage encounters with other devices to temporarily replicate critical data. Permanent backups are created when the participating devices are able to access the fixed infrastructure. Several data replication and scattering strategies are presented, including the use of erasure codes. A methodology to model and evaluate them using Petri nets and Markov chains is described. We demonstrate that our cooperative backup service decreases the probability of data loss by a factor up to the ad hoc to Internet connectivity ratio.

The past decade has seen an increasing use of complex computer systems made of third party components to develop mission critical applications. To insure the dependability of those systems in a sound and maintainable manner, technologies are needed to add fault-tolerance mechanisms transparently, while maintaining efficiency, high coverage, and evolvability. In this paper, we present a generic framework that addresses this problem and can be used within current industrial software. Our proposal is based on a limited set of core concepts inspired from plant biology and meta-object protocols. It provides separation of concerns for the implementation of adaptive fault tolerance strategies, while maintaining a global inter-level perception of the system runtime behavior. We demonstrate its practicality by using it to control the non-determinism of a CORBA/UNIX system.

The goal of this paper is to assess the value of simple features that are widely available in off-the-shelf CORBA and Java platforms for the implementation of fault-tolerance mechanisms in industry-grade systems. This work builds on knowledge gained at LAAS from previous work on the prototyping of reflective fault tolerant frameworks. We describe how we used the interception and state capture mechanisms that are available in CORBA and Java to implement a simple replication strategy on a small middleware-based system built upon GNU/Linux and JOrbacus. We discuss the benefits and the limits of the resulting system from a practical point of view.

Th3r2 party software is now in reasingly used in systems with hhm dependability requirements. Thq evolution of system development raises new h czM55LcO in parti ular regarding thg implementation of faulttoleran e. As systems are often built of bla k-box omponents, some ru ial aspe ts of thczz behzz5 regarding repli ation annot be h cWM ThW is also true to some extent for open-sour e omponents as mastering thste internal behnal c is sometimes very tri ky (e.g. OS and ORBs). During thi last de ade refle tion ho emerged as a very fruitful paradigm for dis iplined management of non-fun tional aspe ts, among wh h fault-toleran e. In thcW paper we dis uss hs to apply refle tion to multi-layer systems for implementing faulttoleran e in an independent and prin ipled manner. We analyze thl onne tions between thw underlying assumptions of fault-toleran e strategies and different layers of a system. Based on thcW multi-layer analysis we shcz hc thz requirements of a family of repli ation algorithz an be addressed on a on rete arhcz ture, resulting in whWLchMWLchchhO5Lzchzc tion.

This paper presents research work performed on the development and the verification of dependable reflective systems based on MetaObject Protocols (MOPS). We describe our experience, we draw the lessons learned from both a design and a validation viewpoint, and we discuss some possible future trends on this topic. The main originality of this work relies on the combination of both design and validation issues for the development of reflective systems, which has led to the definition of a reflective framework for the next generation of fault-tolerant systems. This framework includes: 1) the specification of a MetaObject Protocol suited to the implementation of fault-tolerant systems and 2) the definition of a general test strategy to guide its verification. The proposed approach is generic and solves many issues related to the use and evolution of system platforms with dependability requirements. Two different instances of the specified MOP have been implemented in order to study the impact of the MOP architecture in the development of a reflective fault-tolerant system. As far as the test strategy is concerned, a different testing level is associated with each reflective mechanism defined in the MOP. For each testing level, we characterize the test objectives and the required test environments. According to this experience, several new research challenges are finally identified.

The objective of this work is to define, implement and illustrate a portable serialization technique for CORBA objects. We propose an approach based on reflection: through open compilers facilities the internal state of CORBA objects is obtained and transformed into a language independent format using CORBA mechanisms. This state can be restored and used by objects developed using different languages and running on different software platforms. A tool was developed and applied to a Chat application as a case study. The proposed technique is used to exchange state information between a C++ and a Java incarnation of this CORBA service. An observer tool enables the object state to be displayed and analyzed by the user. The applicability of this technique to various domains is discussed. Beyond the interest of language reflection, we finally advocate that operating system and middleware reflection would also be powerful concepts to extend the work presented in this paper.

We present the principles of multi-level reflection as an enabling technology for the design and implementation of adaptive fault tolerant systems. By exhibiting the structural and behavioral aspects of a software component, the reflection paradigm enables the design and implementation of appropriate non-functional mechanisms at a meta-level. The separation of concerns provided by reflective architectures makes reflection a perfect match for fault tolerance mechanisms. However, in order to provide the necessary and sufficient information for error detection and recovery, reflection must be applied to all system layers in an orthogonal manner. This is the main motivation behind the notion of multi-level reflection that is introduced. We describe the basic concepts of this new architectural paradigm, and illustrate them with concrete examples. We also discuss some practical work that has recently been carried out to start implementing the proposed framework.

The use of reflection is becoming popular today for the implementation of non-functional mechanisms such as fault tolerance. The main benefits of reflection are separation of concerns between the application and the mechanisms and transparency from the application programmer point of view. Unfortunately, metaobject protocols (MOPs) available today are not satisfactory with respect to necessary features needed for implementing fault tolerance mechanisms. Previously, we proposed a specialised MOP based on Corba, well adapted for such mechanisms (M.-O. Killijian and J.C. Fabre, 1998). We deliberately focus on the implementation of this metaobject protocol using compile-time reflection and its use for implementing distributed fault tolerance. We present the design and the implementation of a fault-tolerant Corba system using this metaobject together with some preliminary experimental results. From the lessons learnt from this work, we briefly address the benefits of reflection in other layers of a system for dependability issues.

The use of metalevel architectures for the implementation of fault-tolerant systems is today very appealing. Nevertheless, all such fault-tolerant systems have used a general-purpose metaobject protocol (MOP) or are based on restricted reflective features of some object-oriented language. According to our past experience, we define in this paper a suitable metaobject protocol, called FT-MOP for building fault-tolerant systems. We explain how to realize a specialized runtime MOP using compile-time reflection. This MOP is CORBA compliant: it enables the execution and the state evolution of CORBA objects to be controlled and enables the fault tolerance metalevel to be developed as CORBA software.