Search

We consider the following problem : we have a high-resolution street network of a given city, and low-resolution measurements of traffic within this city. We want to associate to each measurement the set of streets corresponding to the observed traffic. To do so, we take benefit of specific properties of these data to match measured links to links in the street network. We propose several success criteria for the obtained matching. They show that the matching algorithm generally performs very well, and they give complementary ways to detect data discrepancies that makes any matching highly dubious., Comment: arXiv admin comment: This version has been removed by arXiv administrators as the submitter did not have the rights to agree to the license at the time of submission

Empirical evidence suggests that algorithmic decisions driven by Machine Learning (ML) techniques threaten to discriminate against legally protected groups or create new sources of unfairness. This work supports the contextual approach to fairness in EU non-discrimination legal framework and aims at assessing up to what point we can assure legal fairness through fairness metrics and under fairness constraints. For that, we analyze the legal notion of non-discrimination and differential treatment with the fairness definition Demographic Parity (DP) through Conditional Demographic Disparity (CDD). We train and compare different classifiers with fairness constraints to assess whether it is possible to reduce bias in the prediction while enabling the contextual approach to judicial interpretation practiced under EU non-discrimination laws. Our experimental results on three scenarios show that the in-processing bias mitigation algorithm leads to different performances in each of them. Our experiments and analysis suggest that AI-assisted decision-making can be fair from a legal perspective depending on the case at hand and the legal justification. These preliminary results encourage future work which will involve further case studies, metrics, and fairness notions., Comment: Submitted at the 19th International Conference on Artificial Intelligence and Law - ICAIL 2023. Expected decision date is July 18, 2023

The AGATA tracking detector array represents a significant improvement over previous Compton suppressed arrays. The construction of AGATA led to numerous technological breakthroughs in order to meet the requirements and the challenges of building a mobile detector across Europe. This paper focuses on the design and implementation of the data acquisition system responsible of the readout and control of the germanium detectors of AGATA. Our system is highly versatile, capable of instrumenting AGATA and seamlessly adapting it to various configurations with a wide range of ancillary detectors and/or spectrometers. It consists of three main components: an autonomous and independent infrastructure, a dedicated application core ensuring overall consistency, and a high--performance software package providing a fully integrated data flow management including the setting-up, the supervision and the slow control of the instrument. In this paper, we present a comprehensive analysis of the system's design and performance, particularly under high-counting rate conditions.

Presently, gamma-ray tracking in germanium segmented detectors is realised by applying two advanced, complex algorithms. While they have already triggered an intensive R&D, they are still subject to further improvements. Making such algorithms effective, online in real time conditions and/or offline for deeper analysis, in data pipelines do require many additional software developments. This review paper gives an overview of the various bricks of software produced so far by the AGATA collaboration. It provides hints of what is foreseen for the next phases of the project up to its full configuration namely with 180 capsules in the array.

Be it for a malicious or legitimate purpose, packing, a transformation that consists in applying various operations like compression or encryption to a binary file, i.e. for making reverse engineering harder or obfuscating code, is widely employed since decades already. Particularly in the field of malware analysis where a stumbling block is evasion, it has proven effective and still gives a hard time to scientists who want to efficiently detect it. While already extensively covered in the scientific literature, it remains an open issue especially when considering its detection time and accuracy trade-off. Many approaches, including machine learning, have been proposed but most studies often restrict their scope (i.e. malware and PE files), rely on uncertain datasets (i.e. built based on a super-detector or using labels from an questionable source) and do no provide any open implementation, which makes comparing state-of-the-art solutions tedious. Considering the many challenges that packing implies, there exists room for improvement in the way it is addressed, especially when dealing with static detection techniques. In order to tackle with these challenges, we propose an experimental toolkit, aptly called the Packing Box, leveraging automation and containerization in an open source platform that brings a unified solution to the research community and we showcase it with some experiments including unbiased ground truth generation, data visualization, machine learning pipeline automation and performance of open source packing static detectors.

A specification theory combines notions of specifications and implementations with a satisfaction relation, a refinement relation and a set of operators supporting stepwise design. We develop a complete specification framework for real-time systems using Timed I/O Automata as the specification formalism, with the semantics expressed in terms of Timed I/O Transition Systems. We provide constructs for refinement, consistency checking, logical and structural composition, and quotient of specifications -- all indispensable ingredients of a compositional design methodology. The theory is backed by rigorous proofs and is being implemented in the open-source tool ECDAR., Comment: Version submitted for review

Over past years, the manually methods to create detection rules were no longer practical in the anti-malware product since the number of malware threats has been growing. Thus, the turn to the machine learning approaches is a promising way to make the malware recognition more efficient. The traditional centralized machine learning requires a large amount of data to train a model with excellent performance. To boost the malware detection, the training data might be on various kind of data sources such as data on host, network and cloud-based anti-malware components, or even, data from different enterprises. To avoid the expenses of data collection as well as the leakage of private data, we present a federated learning system to identify malwares through the behavioural graphs, i.e., system call dependency graphs. It is based on a deep learning model including a graph autoencoder and a multi-classifier module. This model is trained by a secure learning protocol among clients to preserve the private data against the inference attacks. Using the model to identify malwares, we achieve the accuracy of 85\% for the homogeneous graph data and 93\% for the inhomogeneous graph data.

Malware analysis techniques are divided into static and dynamic analysis. Both techniques can be bypassed by circumvention techniques such as obfuscation. In a series of works, the authors have promoted the use of symbolic executions combined with machine learning to avoid such traps. Most of those works rely on natural graph-based representations that can then be plugged into graph-based learning algorithms such as Gspan. There are two main problems with this approach. The first one is in the cost of computing the graph. Indeed, working with graphs requires one to compute and representing the entire state-space of the file under analysis. As such computation is too cumbersome, the techniques often rely on developing strategies to compute a representative subgraph of the behaviors. Unfortunately, efficient graph-building strategies remain weakly explored. The second problem is in the classification itself. Graph-based machine learning algorithms rely on comparing the biggest common structures. This sidelines small but specific parts of the malware signature. In addition, it does not allow us to work with efficient algorithms such as support vector machine. We propose a new efficient open source toolchain for machine learning-based classification. We also explore how graph-kernel techniques can be used in the process. We focus on the 1-dimensional Weisfeiler-Lehman kernel, which can capture local similarities between graphs. Our experimental results show that our approach outperforms existing ones by an impressive factor.

Their highly adaptive nature and the combinatorial explosion of possible configurations makes testing context-oriented programs hard. We propose a methodology to automate the generation of test scenarios for developers of feature-based context-oriented programs. By using combinatorial interaction testing we generate a covering array from which a small but representative set of test scenarios can be inferred. By taking advantage of the explicit separation of contexts and features in such context-oriented programs, we can further rearrange the generated test scenarios to minimise the reconfiguration cost between subsequent scenarios. Finally, we explore how a previously generated test suite can be adapted incrementally when the system evolves to a new version. By validating these algorithms on a small use case, our initial results show that the proposed test generation approach is efficient and beneficial to developers to test and improve the design of context-oriented programs.

In recent years there has been a considerable effort in optimising formal methods for application to code. This has been driven by tools such as CPAChecker, DIVINE, and CBMC. At the same time tools such as Uppaal have been massively expanding the realm of more traditional model checking technologies to include strategy synthesis algorithms - an aspect becoming more and more needed as software becomes increasingly parallel. Instead of reimplementing the advances made by Uppaal in this area, we suggest in this paper to develop a bridge between the source code and the engine of Uppaal. Our approach uses the widespread intermediate language LLVM and makes recent advances of the Uppaal ecosystem readily available to analysis of source code., Comment: In Proceedings F-IDE 2021, arXiv:2108.02369

Packing is an obfuscation technique widely used by malware to hide the content and behavior of a program. Much prior research has explored how to detect whether a program is packed. This research includes a broad variety of approaches such as entropy analysis, syntactic signatures and more recently machine learning classifiers using various features. However, no robust results have indicated which algorithms perform best, or which features are most significant. This is complicated by considering how to evaluate the results since accuracy, cost, generalization capabilities, and other measures are all reasonable. This work explores eleven different machine learning approaches using 119 features to understand: which features are most significant for packing detection; which algorithms offer the best performance; and which algorithms are most economical.

Linux users expect fresh packages in the official repositories of their distributions. Yet, due to philosophical divergences, the packages available in various distributions do not all have the same degree of freshness. Users therefore need to be informed as to those differences. Through quantitative empirical analyses, we assess and compare the freshness of 890 common packages in six mainstream Linux distributions. We find that at least one out of ten packages is outdated, but the proportion of outdated packages varies greatly between these distributions. Using the metrics of update delay and time lag, we find that the majority of packages are using versions less than 3 months behind the upstream in 5 of those 6 distributions. We contrast the user perception of package freshness with our analyses and order the considered distributions in terms of package freshness to help Linux users in choosing a distribution that most fits their needs and expectations.

Domain-specific quantitative modeling and analysis approaches are fundamental in scenarios in which qualitative approaches are inappropriate or unfeasible. In this paper, we present a tool-supported approach to quantitative graph-based security risk modeling and analysis based on attack-defense trees. Our approach is based on QFLan, a successful domain-specific approach to support quantitative modeling and analysis of highly configurable systems, whose domain-specific components have been decoupled to facilitate the instantiation of the QFLan approach in the domain of graph-based security risk modeling and analysis. Our approach incorporates distinctive features from three popular kinds of attack trees, namely enhanced attack trees, capabilities-based attack trees and attack countermeasure trees, into the domain-specific modeling language. The result is a new framework, called RisQFLan, to support quantitative security risk modeling and analysis based on attack-defense diagrams. By offering either exact or statistical verification of probabilistic attack scenarios, RisQFLan constitutes a significant novel contribution to the existing toolsets in that domain. We validate our approach by highlighting the additional features offered by RisQFLan in three illustrative case studies from seminal approaches to graph-based security risk modeling analysis based on attack trees.

Lifted (family-based) static analysis by abstract interpretation is capable of analyzing all variants of a program family simultaneously, in a single run without generating any of the variants explicitly. The elements of the underlying lifted analysis domain are tuples, which maintain one property per variant. Still, explicit property enumeration in tuples, one by one for all variants, immediately yields combinatorial explosion. This is particularly apparent in the case of program families that, apart from Boolean features, contain also numerical features with big domains, thus admitting astronomic configuration spaces. The key for an efficient lifted analysis is proper handling of variability-specific constructs of the language (e.g., feature-based runtime tests and #if directives). In this work, we introduce a new symbolic representation of the lifted abstract domain that can efficiently analyze program families with numerical features. This makes sharing between property elements corresponding to different variants explicitly possible. The elements of the new lifted domain are constraint-based decision trees, where decision nodes are labeled with linear constraints defined over numerical features and the leaf nodes belong to an existing single-program analysis domain. To illustrate the potential of this representation, we have implemented an experimental lifted static analyzer, called SPLNUM^2Analyzer, for inferring invariants of C programs. It uses existing numerical domains (e.g., intervals, octagons, polyhedra) from the APRON library as parameters. An empirical evaluation on benchmarks from SV-COMP and BusyBox yields promising preliminary results indicating that our decision trees-based approach is effective and outperforms the tuple-based approach, which is used as a baseline lifted analysis based on abstract interpretation.

The Advanced GAmma Tracking Array (AGATA) multi detector spectrometer will provide precise information for the study of the properties of the exotic nuclear matter (very unbalanced proton (Z) and neutron (N) numbers) along proton- and neutron- drip lines and of super-heavy nuclei. This is done using the latest technology of particle accelerators. The AGATA spectrometer consists of 180 high purity Germanium detectors. Each detector is segmented into 38 segments. The very harsh project requirements are to measure gamma ray energies with very high resolution (< 1x 10 -3) at a high detector counting rate (50 Kevents / sec / crystal). This results in a very high data transfer rate per crystal (5 to 8 Gbps). The 38 segments are sampled @ 100 MHz with 14 bits of resolution. The samples are continuously transferred to the CAP module which reduces the data rate from 64 Gbps to 5 Gbps. The CAP module also adds continuous monitoring data which results in total outgoing data rate of 10 Gbps. The STARE module is designed to fit between the CAP module and the computer farm. It will package the data from the CAP module and transmit it to the server farm using a 10 Gbps UDP connection with a delivery insurance mechanism implemented to ensure that all data is transferred.

Bots are frequently used in Github repositories to automate repetitive activities that are part of the distributed software development process. They communicate with human actors through comments. While detecting their presence is important for many reasons, no large and representative ground-truth dataset is available, nor are classification models to detect and validate bots on the basis of such a dataset. This paper proposes a ground-truth dataset, based on a manual analysis with high interrater agreement, of pull request and issue comments in 5,000 distinct Github accounts of which 527 have been identified as bots. Using this dataset we propose an automated classification model to detect bots, taking as main features the number of empty and non-empty comments of each account, the number of comment patterns, and the inequality between comments within comment patterns. We obtained a very high weighted average precision, recall and F1-score of 0.98 on a test set containing 40% of the data. We integrated the classification model into an open source command-line tool to allow practitioners to detect which accounts in a given Github repository actually correspond to bots., Comment: 16 pages, 11 figures

We develop a taxonomy of different behavioral specification theories and expose their algebraic properties. We start by clarifying what precisely constitutes a behavioral specification theory and then introduce logical and structural operations and develop the resulting algebraic properties. In order to motivate our developments, we give plenty of examples of behavioral specification theories with different operations.

The open-source Linux operating system is available through a wide variety of distributions, each containing a collection of installable software packages. It can be important to keep these packages as fresh as possible to benefit from new features, bug fixes and security patches. However, not all distributions place the same emphasis on package freshness. We conducted a survey in the first half of 2020 with 170 Linux users to gauge their perception of package freshness in the distributions they use, the value they place on package freshness and the reasons why they do so, and the methods they use to update packages. The results of this survey reveal that, for the aforementioned reasons, keeping packages up to date is an important concern to Linux users and that they install and update packages through their distribution's official repositories whenever possible, but often resort to third-party repositories and package managers for proprietary software and programming language libraries. Some distributions are perceived to be much quicker in deploying package updates than others. These results are valuable to assess the requirements and expectations of Linux users in terms of package freshness., Comment: 5 pages, 4 figures. Preprint to be published in the International Conference on Software Maintenance and Evolution (ICSME) 2020

In this work we present our work in developing a software verification tool for llvm-code - Lodin - that incorporates both explicit-state model checking, statistical model checking and symbolic state model checking algorithms.

Feature-based SPL analysis and family-based model checking have seen rapid development. Many model checking problems can be reduced to two-player games on finite graphs. A prominent example is mu-calculus model checking, which is generally done by translating to parity games, but also many quantitative model-checking problems can be reduced to (quantitative) games. In their FASE'20 paper, ter Beek et al.\ introduce parity games with variability in order to develop family-based mu-calculus model checking of featured transition systems. We generalize their model to general featured games and show how these may be analysed in a family-based manner. We introduce featured reachability games, featured minimum reachability games, featured discounted games, featured energy games, and featured parity games. We show how to compute winners and values of such games in a family-based manner. We also show that all these featured games admit optimal featured strategies, which project to optimal strategies for any product. Further, we develop family-based algorithms, using late splitting, to compute winners, values, and optimal strategies for all the featured games we have introduced.

We lay out a general method for computing branching distances between labeled transition systems. We translate the quantitative games used for defining these distances to other, path-building games which are amenable to methods from the theory of quantitative games. We then show for all common types of branching distances how the resulting path-building games can be solved. In the end, we achieve a method which can be used to compute all branching distances in the linear-time--branching-time spectrum.

A biclique of a graph $G$ is a maximal induced complete bipartite subgraph of $G$. The edge-biclique graph of $G$, $KB_e(G)$, is the edge-intersection graph of the bicliques of $G$. A graph $G$ diverges (resp. converges or is periodic) under an operator $H$ whenever $\lim_{k \rightarrow \infty}|V(H^k(G))|=\infty$ (resp. $\lim_{k \rightarrow \infty}H^k(G)=H^m(G)$ for some $m$ or $H^k(G)=H^{k+s}(G)$ for some $k$ and $s \geq 2$). The iterated edge-biclique graph of $G$, $KB_e^k(G)$, is the graph obtained by applying the edge-biclique operator $k$ successive times to $G$. In this paper, we first study the connectivity relation between $G$ and $KB_e(G)$. Next, we study the iterated edge-biclique operator $KB_e$. In particular, we give sufficient conditions for a graph to be convergent or divergent under the operator $KB_e$, we characterize the behavior of \textit{burgeon graphs} and we propose some general conjectures on the subject.

Neutrinoless double-beta decay is a key process in particle physics. Its experimental investigation is the only viable method that can establish the Majorana nature of neutrinos, providing at the same time a sensitive inclusive test of lepton number violation. CROSS (Cryogenic Rare-event Observatory with Surface Sensitivity) aims at developing and testing a new bolometric technology to be applied to future large-scale experiments searching for neutrinoless double-beta decay of the promising nuclei $^{100}$Mo and $^{130}$Te. The limiting factor in large-scale bolometric searches for this rare process is the background induced by surface radioactive contamination, as shown by the results of the CUORE experiment. The basic concept of CROSS consists of rejecting this challenging background component by pulse-shape discrimination, assisted by a proper coating of the faces of the crystal containing the isotope of interest and serving as energy absorber of the bolometric detector. In this paper, we demonstrate that ultra-pure superconductive Al films deposited on the crystal surfaces act successfully as pulse-shape modifiers, both with fast and slow phonon sensors. Rejection factors higher than 99.9% of $\alpha$ surface radioactivity have been demonstrated in a series of prototypes based on crystals of Li$_2$MoO$_4$ and TeO$_2$. We have also shown that point-like energy depositions can be identified up to a distance of $\sim 1$ mm from the coated surface. The present program envisions an intermediate experiment to be installed underground in the Canfranc laboratory (Spain) in a CROSS-dedicated facility. This experiment, comprising $\sim 3\times 10^{25}$ nuclei of $^{100}$Mo, will be a general test of the CROSS technology as well as a worldwide competitive search for neutrinoless double-beta decay, with sensitivity to the effective Majorana mass down to 70 meV in the most favorable conditions.

Distributed learning across a coalition of organizations allows the members of the coalition to train and share a model without sharing the data used to optimize this model. In this paper, we propose new secure architectures that guarantee preservation of data privacy, trustworthy sequence of iterative learning and equitable sharing of the learned model among each member of the coalition by using adequate encryption and blockchain mechanisms. We exemplify its deployment in the case of the distributed optimization of a deep learning convolutional neural network trained on medical images.

The concept of decomposition in computer science and engineering is considered a fundamental component of computational thinking and is prevalent in design of algorithms, software construction, hardware design, and more. We propose a simple and natural formalization of sequential decomposition, in which a task is decomposed into two sequential sub-tasks, with the first sub-task to be executed before the second sub-task is executed. These tasks are specified by means of input/output relations. We define and study decomposition problems, which is to decide whether a given specification can be sequentially decomposed. Our main result is that decomposition itself is a difficult computational problem. More specifically, we study decomposition problems in three settings: where the input task is specified explicitly, by means of Boolean circuits, and by means of automatic relations. We show that in the first setting decomposition is NP-complete, in the second setting it is NEXPTIME-complete, and in the third setting there is evidence to suggest that it is undecidable. Our results indicate that the intuitive idea of decomposition as a system-design approach requires further investigation. In particular, we show that adding a human to the loop by asking for a decomposition hint lowers the complexity of decomposition problems considerably.

Variability models allow effective building of many custom model variants for various configurations. Lifted model checking for a variability model is capable of verifying all its variants simultaneously in a single run by exploiting the similarities between the variants. The computational cost of lifted model checking still greatly depends on the number of variants (the size of configuration space), which is often huge. One of the most promising approaches to fighting the configuration space explosion problem in lifted model checking are variability abstractions. In this work, we define a novel game-based approach for variability-specific abstraction and refinement for lifted model checking of the full CTL, interpreted over 3-valued semantics. We propose a direct algorithm for solving a 3-valued (abstract) lifted model checking game. In case the result of model checking an abstract variability model is indefinite, we suggest a new notion of refinement, which eliminates indefinite results. This provides an iterative incremental variability-specific abstraction and refinement framework, where refinement is applied only where indefinite results exist and definite results from previous iterations are reused.

The pull-based development process has become prevalent on platforms such as GitHub as a form of distributed software development. Potential contributors can create and submit a set of changes to a software project through pull requests. These changes can be accepted, discussed or rejected by the maintainers of the software project, and can influence further contribution proposals. As such, it is important to examine the practices that encourage contributors to a project to submit pull requests. Specifically, we consider the impact of prior pull requests on the acceptance or rejection of subsequent pull requests. We also consider the potential effect of rejecting or ignoring pull requests on further contributions. In this preliminary research, we study three large projects on \textsf{GitHub}, using pull request data obtained through the \textsf{GitHub} API, and we perform empirical analyses to investigate the above questions. Our results show that continued contribution to a project is correlated with higher pull request acceptance rates and that pull request rejections lead to fewer future contributions., Comment: 6 pages. Presented at BENEVOL 2018 software evolution seminar, Delft, The Netherlands (11 December 2018). Published in open access CEUR Workshop Proceedings (ceur-ws.org). Researchsupported by the FRQ-FNRS collaborative research project R.60.04.18.F SECOHealth, the Excellence of Science project 30446992 SECO-ASSIST financed by FWO-Vlaanderen and F.R.S.-FNRS, and F.R.S.-FNRS Grant T.0017.18, CEUR Workshop Proceedings 2019

Analysis of a probabilistic system often requires to learn the joint probability distribution of its random variables. The computation of the exact distribution is usually an exhaustive precise analysis on all executions of the system. To avoid the high computational cost of such an exhaustive search, statistical analysis has been studied to efficiently obtain approximate estimates by analyzing only a small but representative subset of the system's behavior. In this paper we propose a hybrid statistical estimation method that combines precise and statistical analyses to estimate mutual information, Shannon entropy, and conditional entropy, together with their confidence intervals. We show how to combine the analyses on different components of a discrete system with different accuracy to obtain an estimate for the whole system. The new method performs weighted statistical analysis with different sample sizes over different components and dynamically finds their optimal sample sizes. Moreover, it can reduce sample sizes by using prior knowledge about systems and a new abstraction-then-sampling technique based on qualitative analysis. To apply the method to the source code of a system, we show how to decompose the code into components and to determine the analysis method for each component by overviewing the implementation of those techniques in the HyLeak tool. We demonstrate with case studies that the new method outperforms the state of the art in quantifying information leakage., Comment: Accepted by Formal Aspects of Computing